991 lines · cpp
1//===- SafeStack.cpp - Safe Stack Insertion -------------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This pass splits the stack into the safe stack (kept as-is for LLVM backend)10// and the unsafe stack (explicitly allocated and managed through the runtime11// support library).12//13// http://clang.llvm.org/docs/SafeStack.html14//15//===----------------------------------------------------------------------===//16 17#include "llvm/CodeGen/SafeStack.h"18#include "SafeStackLayout.h"19#include "llvm/ADT/APInt.h"20#include "llvm/ADT/ArrayRef.h"21#include "llvm/ADT/SmallPtrSet.h"22#include "llvm/ADT/SmallVector.h"23#include "llvm/ADT/Statistic.h"24#include "llvm/Analysis/AssumptionCache.h"25#include "llvm/Analysis/BranchProbabilityInfo.h"26#include "llvm/Analysis/DomTreeUpdater.h"27#include "llvm/Analysis/InlineCost.h"28#include "llvm/Analysis/LoopInfo.h"29#include "llvm/Analysis/ScalarEvolution.h"30#include "llvm/Analysis/ScalarEvolutionExpressions.h"31#include "llvm/Analysis/StackLifetime.h"32#include "llvm/Analysis/TargetLibraryInfo.h"33#include "llvm/CodeGen/TargetLowering.h"34#include "llvm/CodeGen/TargetPassConfig.h"35#include "llvm/CodeGen/TargetSubtargetInfo.h"36#include "llvm/IR/Argument.h"37#include "llvm/IR/Attributes.h"38#include "llvm/IR/ConstantRange.h"39#include "llvm/IR/Constants.h"40#include "llvm/IR/DIBuilder.h"41#include "llvm/IR/DataLayout.h"42#include "llvm/IR/DerivedTypes.h"43#include "llvm/IR/Dominators.h"44#include "llvm/IR/Function.h"45#include "llvm/IR/IRBuilder.h"46#include "llvm/IR/InstIterator.h"47#include "llvm/IR/Instruction.h"48#include "llvm/IR/Instructions.h"49#include "llvm/IR/IntrinsicInst.h"50#include "llvm/IR/Intrinsics.h"51#include "llvm/IR/MDBuilder.h"52#include "llvm/IR/Metadata.h"53#include "llvm/IR/Module.h"54#include "llvm/IR/Type.h"55#include "llvm/IR/Use.h"56#include "llvm/IR/Value.h"57#include "llvm/InitializePasses.h"58#include "llvm/Pass.h"59#include "llvm/Support/Casting.h"60#include "llvm/Support/Debug.h"61#include "llvm/Support/ErrorHandling.h"62#include "llvm/Support/raw_ostream.h"63#include "llvm/Target/TargetMachine.h"64#include "llvm/Transforms/Utils/BasicBlockUtils.h"65#include "llvm/Transforms/Utils/Cloning.h"66#include "llvm/Transforms/Utils/Local.h"67#include <algorithm>68#include <cassert>69#include <cstdint>70#include <optional>71#include <string>72 73using namespace llvm;74using namespace llvm::safestack;75 76#define DEBUG_TYPE "safe-stack"77 78STATISTIC(NumFunctions, "Total number of functions");79STATISTIC(NumUnsafeStackFunctions, "Number of functions with unsafe stack");80STATISTIC(NumUnsafeStackRestorePointsFunctions,81 "Number of functions that use setjmp or exceptions");82 83STATISTIC(NumAllocas, "Total number of allocas");84STATISTIC(NumUnsafeStaticAllocas, "Number of unsafe static allocas");85STATISTIC(NumUnsafeDynamicAllocas, "Number of unsafe dynamic allocas");86STATISTIC(NumUnsafeByValArguments, "Number of unsafe byval arguments");87STATISTIC(NumUnsafeStackRestorePoints, "Number of setjmps and landingpads");88 89/// Use __safestack_pointer_address even if the platform has a faster way of90/// access safe stack pointer.91static cl::opt<bool>92 SafeStackUsePointerAddress("safestack-use-pointer-address",93 cl::init(false), cl::Hidden);94 95static cl::opt<bool> ClColoring("safe-stack-coloring",96 cl::desc("enable safe stack coloring"),97 cl::Hidden, cl::init(true));98 99namespace {100 101/// The SafeStack pass splits the stack of each function into the safe102/// stack, which is only accessed through memory safe dereferences (as103/// determined statically), and the unsafe stack, which contains all104/// local variables that are accessed in ways that we can't prove to105/// be safe.106class SafeStack {107 Function &F;108 const TargetLoweringBase &TL;109 const DataLayout &DL;110 DomTreeUpdater *DTU;111 ScalarEvolution &SE;112 113 Type *StackPtrTy;114 Type *IntPtrTy;115 Type *Int32Ty;116 117 Value *UnsafeStackPtr = nullptr;118 119 /// Unsafe stack alignment. Each stack frame must ensure that the stack is120 /// aligned to this value. We need to re-align the unsafe stack if the121 /// alignment of any object on the stack exceeds this value.122 ///123 /// 16 seems like a reasonable upper bound on the alignment of objects that we124 /// might expect to appear on the stack on most common targets.125 static constexpr Align StackAlignment = Align::Constant<16>();126 127 /// Return the value of the stack canary.128 Value *getStackGuard(IRBuilder<> &IRB, Function &F);129 130 /// Load stack guard from the frame and check if it has changed.131 void checkStackGuard(IRBuilder<> &IRB, Function &F, Instruction &RI,132 AllocaInst *StackGuardSlot, Value *StackGuard);133 134 /// Find all static allocas, dynamic allocas, return instructions and135 /// stack restore points (exception unwind blocks and setjmp calls) in the136 /// given function and append them to the respective vectors.137 void findInsts(Function &F, SmallVectorImpl<AllocaInst *> &StaticAllocas,138 SmallVectorImpl<AllocaInst *> &DynamicAllocas,139 SmallVectorImpl<Argument *> &ByValArguments,140 SmallVectorImpl<Instruction *> &Returns,141 SmallVectorImpl<Instruction *> &StackRestorePoints);142 143 /// Calculate the allocation size of a given alloca. Returns 0 if the144 /// size can not be statically determined.145 uint64_t getStaticAllocaAllocationSize(const AllocaInst* AI);146 147 /// Allocate space for all static allocas in \p StaticAllocas,148 /// replace allocas with pointers into the unsafe stack.149 ///150 /// \returns A pointer to the top of the unsafe stack after all unsafe static151 /// allocas are allocated.152 Value *moveStaticAllocasToUnsafeStack(IRBuilder<> &IRB, Function &F,153 ArrayRef<AllocaInst *> StaticAllocas,154 ArrayRef<Argument *> ByValArguments,155 Instruction *BasePointer,156 AllocaInst *StackGuardSlot);157 158 /// Generate code to restore the stack after all stack restore points159 /// in \p StackRestorePoints.160 ///161 /// \returns A local variable in which to maintain the dynamic top of the162 /// unsafe stack if needed.163 AllocaInst *164 createStackRestorePoints(IRBuilder<> &IRB, Function &F,165 ArrayRef<Instruction *> StackRestorePoints,166 Value *StaticTop, bool NeedDynamicTop);167 168 /// Replace all allocas in \p DynamicAllocas with code to allocate169 /// space dynamically on the unsafe stack and store the dynamic unsafe stack170 /// top to \p DynamicTop if non-null.171 void moveDynamicAllocasToUnsafeStack(Function &F, Value *UnsafeStackPtr,172 AllocaInst *DynamicTop,173 ArrayRef<AllocaInst *> DynamicAllocas);174 175 bool IsSafeStackAlloca(const Value *AllocaPtr, uint64_t AllocaSize);176 177 bool IsMemIntrinsicSafe(const MemIntrinsic *MI, const Use &U,178 const Value *AllocaPtr, uint64_t AllocaSize);179 bool IsAccessSafe(Value *Addr, uint64_t Size, const Value *AllocaPtr,180 uint64_t AllocaSize);181 182 bool ShouldInlinePointerAddress(CallInst &CI);183 void TryInlinePointerAddress();184 185public:186 SafeStack(Function &F, const TargetLoweringBase &TL, const DataLayout &DL,187 DomTreeUpdater *DTU, ScalarEvolution &SE)188 : F(F), TL(TL), DL(DL), DTU(DTU), SE(SE),189 StackPtrTy(DL.getAllocaPtrType(F.getContext())),190 IntPtrTy(DL.getIntPtrType(F.getContext())),191 Int32Ty(Type::getInt32Ty(F.getContext())) {}192 193 // Run the transformation on the associated function.194 // Returns whether the function was changed.195 bool run();196};197 198uint64_t SafeStack::getStaticAllocaAllocationSize(const AllocaInst* AI) {199 uint64_t Size = DL.getTypeAllocSize(AI->getAllocatedType());200 if (AI->isArrayAllocation()) {201 auto C = dyn_cast<ConstantInt>(AI->getArraySize());202 if (!C)203 return 0;204 Size *= C->getZExtValue();205 }206 return Size;207}208 209bool SafeStack::IsAccessSafe(Value *Addr, uint64_t AccessSize,210 const Value *AllocaPtr, uint64_t AllocaSize) {211 const SCEV *AddrExpr = SE.getSCEV(Addr);212 const auto *Base = dyn_cast<SCEVUnknown>(SE.getPointerBase(AddrExpr));213 if (!Base || Base->getValue() != AllocaPtr) {214 LLVM_DEBUG(215 dbgs() << "[SafeStack] "216 << (isa<AllocaInst>(AllocaPtr) ? "Alloca " : "ByValArgument ")217 << *AllocaPtr << "\n"218 << "SCEV " << *AddrExpr << " not directly based on alloca\n");219 return false;220 }221 222 const SCEV *Expr = SE.removePointerBase(AddrExpr);223 uint64_t BitWidth = SE.getTypeSizeInBits(Expr->getType());224 ConstantRange AccessStartRange = SE.getUnsignedRange(Expr);225 ConstantRange SizeRange =226 ConstantRange(APInt(BitWidth, 0), APInt(BitWidth, AccessSize));227 ConstantRange AccessRange = AccessStartRange.add(SizeRange);228 ConstantRange AllocaRange =229 ConstantRange(APInt(BitWidth, 0), APInt(BitWidth, AllocaSize));230 bool Safe = AllocaRange.contains(AccessRange);231 232 LLVM_DEBUG(233 dbgs() << "[SafeStack] "234 << (isa<AllocaInst>(AllocaPtr) ? "Alloca " : "ByValArgument ")235 << *AllocaPtr << "\n"236 << " Access " << *Addr << "\n"237 << " SCEV " << *Expr238 << " U: " << SE.getUnsignedRange(Expr)239 << ", S: " << SE.getSignedRange(Expr) << "\n"240 << " Range " << AccessRange << "\n"241 << " AllocaRange " << AllocaRange << "\n"242 << " " << (Safe ? "safe" : "unsafe") << "\n");243 244 return Safe;245}246 247bool SafeStack::IsMemIntrinsicSafe(const MemIntrinsic *MI, const Use &U,248 const Value *AllocaPtr,249 uint64_t AllocaSize) {250 if (auto MTI = dyn_cast<MemTransferInst>(MI)) {251 if (MTI->getRawSource() != U && MTI->getRawDest() != U)252 return true;253 } else {254 if (MI->getRawDest() != U)255 return true;256 }257 258 auto Len = MI->getLengthInBytes();259 // Non-constant size => unsafe. FIXME: try SCEV getRange.260 if (!Len) return false;261 return IsAccessSafe(U, Len->getZExtValue(), AllocaPtr, AllocaSize);262}263 264/// Check whether a given allocation must be put on the safe265/// stack or not. The function analyzes all uses of AI and checks whether it is266/// only accessed in a memory safe way (as decided statically).267bool SafeStack::IsSafeStackAlloca(const Value *AllocaPtr, uint64_t AllocaSize) {268 // Go through all uses of this alloca and check whether all accesses to the269 // allocated object are statically known to be memory safe and, hence, the270 // object can be placed on the safe stack.271 SmallPtrSet<const Value *, 16> Visited;272 SmallVector<const Value *, 8> WorkList;273 WorkList.push_back(AllocaPtr);274 275 // A DFS search through all uses of the alloca in bitcasts/PHI/GEPs/etc.276 while (!WorkList.empty()) {277 const Value *V = WorkList.pop_back_val();278 for (const Use &UI : V->uses()) {279 auto I = cast<const Instruction>(UI.getUser());280 assert(V == UI.get());281 282 switch (I->getOpcode()) {283 case Instruction::Load:284 if (!IsAccessSafe(UI, DL.getTypeStoreSize(I->getType()), AllocaPtr,285 AllocaSize))286 return false;287 break;288 289 case Instruction::VAArg:290 // "va-arg" from a pointer is safe.291 break;292 case Instruction::Store:293 if (V == I->getOperand(0)) {294 // Stored the pointer - conservatively assume it may be unsafe.295 LLVM_DEBUG(dbgs()296 << "[SafeStack] Unsafe alloca: " << *AllocaPtr297 << "\n store of address: " << *I << "\n");298 return false;299 }300 301 if (!IsAccessSafe(UI, DL.getTypeStoreSize(I->getOperand(0)->getType()),302 AllocaPtr, AllocaSize))303 return false;304 break;305 306 case Instruction::Ret:307 // Information leak.308 return false;309 310 case Instruction::Call:311 case Instruction::Invoke: {312 const CallBase &CS = *cast<CallBase>(I);313 314 if (I->isLifetimeStartOrEnd())315 continue;316 317 if (const MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) {318 if (!IsMemIntrinsicSafe(MI, UI, AllocaPtr, AllocaSize)) {319 LLVM_DEBUG(dbgs()320 << "[SafeStack] Unsafe alloca: " << *AllocaPtr321 << "\n unsafe memintrinsic: " << *I << "\n");322 return false;323 }324 continue;325 }326 327 // LLVM 'nocapture' attribute is only set for arguments whose address328 // is not stored, passed around, or used in any other non-trivial way.329 // We assume that passing a pointer to an object as a 'nocapture330 // readnone' argument is safe.331 // FIXME: a more precise solution would require an interprocedural332 // analysis here, which would look at all uses of an argument inside333 // the function being called.334 auto B = CS.arg_begin(), E = CS.arg_end();335 for (const auto *A = B; A != E; ++A)336 if (A->get() == V)337 if (!(CS.doesNotCapture(A - B) && (CS.doesNotAccessMemory(A - B) ||338 CS.doesNotAccessMemory()))) {339 LLVM_DEBUG(dbgs() << "[SafeStack] Unsafe alloca: " << *AllocaPtr340 << "\n unsafe call: " << *I << "\n");341 return false;342 }343 continue;344 }345 346 default:347 if (Visited.insert(I).second)348 WorkList.push_back(cast<const Instruction>(I));349 }350 }351 }352 353 // All uses of the alloca are safe, we can place it on the safe stack.354 return true;355}356 357Value *SafeStack::getStackGuard(IRBuilder<> &IRB, Function &F) {358 Value *StackGuardVar = TL.getIRStackGuard(IRB);359 Module *M = F.getParent();360 361 if (!StackGuardVar) {362 TL.insertSSPDeclarations(*M);363 return IRB.CreateIntrinsic(Intrinsic::stackguard, {});364 }365 366 return IRB.CreateLoad(StackPtrTy, StackGuardVar, "StackGuard");367}368 369void SafeStack::findInsts(Function &F,370 SmallVectorImpl<AllocaInst *> &StaticAllocas,371 SmallVectorImpl<AllocaInst *> &DynamicAllocas,372 SmallVectorImpl<Argument *> &ByValArguments,373 SmallVectorImpl<Instruction *> &Returns,374 SmallVectorImpl<Instruction *> &StackRestorePoints) {375 for (Instruction &I : instructions(&F)) {376 if (auto AI = dyn_cast<AllocaInst>(&I)) {377 ++NumAllocas;378 379 uint64_t Size = getStaticAllocaAllocationSize(AI);380 if (IsSafeStackAlloca(AI, Size))381 continue;382 383 if (AI->isStaticAlloca()) {384 ++NumUnsafeStaticAllocas;385 StaticAllocas.push_back(AI);386 } else {387 ++NumUnsafeDynamicAllocas;388 DynamicAllocas.push_back(AI);389 }390 } else if (auto RI = dyn_cast<ReturnInst>(&I)) {391 if (CallInst *CI = I.getParent()->getTerminatingMustTailCall())392 Returns.push_back(CI);393 else394 Returns.push_back(RI);395 } else if (auto CI = dyn_cast<CallInst>(&I)) {396 // setjmps require stack restore.397 if (CI->getCalledFunction() && CI->canReturnTwice())398 StackRestorePoints.push_back(CI);399 } else if (auto LP = dyn_cast<LandingPadInst>(&I)) {400 // Exception landing pads require stack restore.401 StackRestorePoints.push_back(LP);402 } else if (auto II = dyn_cast<IntrinsicInst>(&I)) {403 if (II->getIntrinsicID() == Intrinsic::gcroot)404 report_fatal_error(405 "gcroot intrinsic not compatible with safestack attribute");406 }407 }408 for (Argument &Arg : F.args()) {409 if (!Arg.hasByValAttr())410 continue;411 uint64_t Size = DL.getTypeStoreSize(Arg.getParamByValType());412 if (IsSafeStackAlloca(&Arg, Size))413 continue;414 415 ++NumUnsafeByValArguments;416 ByValArguments.push_back(&Arg);417 }418}419 420AllocaInst *421SafeStack::createStackRestorePoints(IRBuilder<> &IRB, Function &F,422 ArrayRef<Instruction *> StackRestorePoints,423 Value *StaticTop, bool NeedDynamicTop) {424 assert(StaticTop && "The stack top isn't set.");425 426 if (StackRestorePoints.empty())427 return nullptr;428 429 // We need the current value of the shadow stack pointer to restore430 // after longjmp or exception catching.431 432 // FIXME: On some platforms this could be handled by the longjmp/exception433 // runtime itself.434 435 AllocaInst *DynamicTop = nullptr;436 if (NeedDynamicTop) {437 // If we also have dynamic alloca's, the stack pointer value changes438 // throughout the function. For now we store it in an alloca.439 DynamicTop = IRB.CreateAlloca(StackPtrTy, /*ArraySize=*/nullptr,440 "unsafe_stack_dynamic_ptr");441 IRB.CreateStore(StaticTop, DynamicTop);442 }443 444 // Restore current stack pointer after longjmp/exception catch.445 for (Instruction *I : StackRestorePoints) {446 ++NumUnsafeStackRestorePoints;447 448 IRB.SetInsertPoint(I->getNextNode());449 Value *CurrentTop =450 DynamicTop ? IRB.CreateLoad(StackPtrTy, DynamicTop) : StaticTop;451 IRB.CreateStore(CurrentTop, UnsafeStackPtr);452 }453 454 return DynamicTop;455}456 457void SafeStack::checkStackGuard(IRBuilder<> &IRB, Function &F, Instruction &RI,458 AllocaInst *StackGuardSlot, Value *StackGuard) {459 Value *V = IRB.CreateLoad(StackPtrTy, StackGuardSlot);460 Value *Cmp = IRB.CreateICmpNE(StackGuard, V);461 462 auto SuccessProb = BranchProbabilityInfo::getBranchProbStackProtector(true);463 auto FailureProb = BranchProbabilityInfo::getBranchProbStackProtector(false);464 MDNode *Weights = MDBuilder(F.getContext())465 .createBranchWeights(SuccessProb.getNumerator(),466 FailureProb.getNumerator());467 Instruction *CheckTerm =468 SplitBlockAndInsertIfThen(Cmp, &RI, /* Unreachable */ true, Weights, DTU);469 IRBuilder<> IRBFail(CheckTerm);470 // FIXME: respect -fsanitize-trap / -ftrap-function here?471 const char *StackChkFailName =472 TL.getLibcallName(RTLIB::STACKPROTECTOR_CHECK_FAIL);473 if (!StackChkFailName) {474 F.getContext().emitError(475 "no libcall available for stackprotector check fail");476 return;477 }478 479 FunctionCallee StackChkFail =480 F.getParent()->getOrInsertFunction(StackChkFailName, IRB.getVoidTy());481 IRBFail.CreateCall(StackChkFail, {});482}483 484/// We explicitly compute and set the unsafe stack layout for all unsafe485/// static alloca instructions. We save the unsafe "base pointer" in the486/// prologue into a local variable and restore it in the epilogue.487Value *SafeStack::moveStaticAllocasToUnsafeStack(488 IRBuilder<> &IRB, Function &F, ArrayRef<AllocaInst *> StaticAllocas,489 ArrayRef<Argument *> ByValArguments, Instruction *BasePointer,490 AllocaInst *StackGuardSlot) {491 if (StaticAllocas.empty() && ByValArguments.empty())492 return BasePointer;493 494 DIBuilder DIB(*F.getParent());495 496 StackLifetime SSC(F, StaticAllocas, StackLifetime::LivenessType::May);497 static const StackLifetime::LiveRange NoColoringRange(1, true);498 if (ClColoring)499 SSC.run();500 501 for (const auto *I : SSC.getMarkers()) {502 auto *Op = dyn_cast<Instruction>(I->getOperand(1));503 const_cast<IntrinsicInst *>(I)->eraseFromParent();504 // Remove the operand bitcast, too, if it has no more uses left.505 if (Op && Op->use_empty())506 Op->eraseFromParent();507 }508 509 // Unsafe stack always grows down.510 StackLayout SSL(StackAlignment);511 if (StackGuardSlot) {512 Type *Ty = StackGuardSlot->getAllocatedType();513 Align Align = std::max(DL.getPrefTypeAlign(Ty), StackGuardSlot->getAlign());514 SSL.addObject(StackGuardSlot, getStaticAllocaAllocationSize(StackGuardSlot),515 Align, SSC.getFullLiveRange());516 }517 518 for (Argument *Arg : ByValArguments) {519 Type *Ty = Arg->getParamByValType();520 uint64_t Size = DL.getTypeStoreSize(Ty);521 if (Size == 0)522 Size = 1; // Don't create zero-sized stack objects.523 524 // Ensure the object is properly aligned.525 Align Align = DL.getPrefTypeAlign(Ty);526 if (auto A = Arg->getParamAlign())527 Align = std::max(Align, *A);528 SSL.addObject(Arg, Size, Align, SSC.getFullLiveRange());529 }530 531 for (AllocaInst *AI : StaticAllocas) {532 Type *Ty = AI->getAllocatedType();533 uint64_t Size = getStaticAllocaAllocationSize(AI);534 if (Size == 0)535 Size = 1; // Don't create zero-sized stack objects.536 537 // Ensure the object is properly aligned.538 Align Align = std::max(DL.getPrefTypeAlign(Ty), AI->getAlign());539 540 SSL.addObject(AI, Size, Align,541 ClColoring ? SSC.getLiveRange(AI) : NoColoringRange);542 }543 544 SSL.computeLayout();545 Align FrameAlignment = SSL.getFrameAlignment();546 547 // FIXME: tell SSL that we start at a less-then-MaxAlignment aligned location548 // (AlignmentSkew).549 if (FrameAlignment > StackAlignment) {550 // Re-align the base pointer according to the max requested alignment.551 IRB.SetInsertPoint(BasePointer->getNextNode());552 BasePointer = cast<Instruction>(IRB.CreateIntToPtr(553 IRB.CreateAnd(554 IRB.CreatePtrToInt(BasePointer, IntPtrTy),555 ConstantInt::get(IntPtrTy, ~(FrameAlignment.value() - 1))),556 StackPtrTy));557 }558 559 IRB.SetInsertPoint(BasePointer->getNextNode());560 561 if (StackGuardSlot) {562 unsigned Offset = SSL.getObjectOffset(StackGuardSlot);563 Value *Off =564 IRB.CreatePtrAdd(BasePointer, ConstantInt::get(Int32Ty, -Offset));565 Value *NewAI =566 IRB.CreateBitCast(Off, StackGuardSlot->getType(), "StackGuardSlot");567 568 // Replace alloc with the new location.569 StackGuardSlot->replaceAllUsesWith(NewAI);570 StackGuardSlot->eraseFromParent();571 }572 573 for (Argument *Arg : ByValArguments) {574 unsigned Offset = SSL.getObjectOffset(Arg);575 MaybeAlign Align(SSL.getObjectAlignment(Arg));576 Type *Ty = Arg->getParamByValType();577 578 uint64_t Size = DL.getTypeStoreSize(Ty);579 if (Size == 0)580 Size = 1; // Don't create zero-sized stack objects.581 582 Value *Off =583 IRB.CreatePtrAdd(BasePointer, ConstantInt::get(Int32Ty, -Offset));584 Value *NewArg = IRB.CreateBitCast(Off, Arg->getType(),585 Arg->getName() + ".unsafe-byval");586 587 // Replace alloc with the new location.588 replaceDbgDeclare(Arg, BasePointer, DIB, DIExpression::ApplyOffset,589 -Offset);590 Arg->replaceAllUsesWith(NewArg);591 IRB.SetInsertPoint(cast<Instruction>(NewArg)->getNextNode());592 IRB.CreateMemCpy(Off, Align, Arg, Arg->getParamAlign(), Size);593 }594 595 // Allocate space for every unsafe static AllocaInst on the unsafe stack.596 for (AllocaInst *AI : StaticAllocas) {597 IRB.SetInsertPoint(AI);598 unsigned Offset = SSL.getObjectOffset(AI);599 600 replaceDbgDeclare(AI, BasePointer, DIB, DIExpression::ApplyOffset, -Offset);601 replaceDbgValueForAlloca(AI, BasePointer, DIB, -Offset);602 603 // Replace uses of the alloca with the new location.604 // Insert address calculation close to each use to work around PR27844.605 std::string Name = std::string(AI->getName()) + ".unsafe";606 while (!AI->use_empty()) {607 Use &U = *AI->use_begin();608 Instruction *User = cast<Instruction>(U.getUser());609 610 // Drop lifetime markers now that this is no longer an alloca.611 // SafeStack has already performed its own stack coloring.612 if (User->isLifetimeStartOrEnd()) {613 User->eraseFromParent();614 continue;615 }616 617 Instruction *InsertBefore;618 if (auto *PHI = dyn_cast<PHINode>(User))619 InsertBefore = PHI->getIncomingBlock(U)->getTerminator();620 else621 InsertBefore = User;622 623 IRBuilder<> IRBUser(InsertBefore);624 Value *Off =625 IRBUser.CreatePtrAdd(BasePointer, ConstantInt::get(Int32Ty, -Offset));626 Value *Replacement =627 IRBUser.CreateAddrSpaceCast(Off, AI->getType(), Name);628 629 if (auto *PHI = dyn_cast<PHINode>(User))630 // PHI nodes may have multiple incoming edges from the same BB (why??),631 // all must be updated at once with the same incoming value.632 PHI->setIncomingValueForBlock(PHI->getIncomingBlock(U), Replacement);633 else634 U.set(Replacement);635 }636 637 AI->eraseFromParent();638 }639 640 // Re-align BasePointer so that our callees would see it aligned as641 // expected.642 // FIXME: no need to update BasePointer in leaf functions.643 unsigned FrameSize = alignTo(SSL.getFrameSize(), StackAlignment);644 645 MDBuilder MDB(F.getContext());646 SmallVector<Metadata *, 2> Data;647 Data.push_back(MDB.createString("unsafe-stack-size"));648 Data.push_back(MDB.createConstant(ConstantInt::get(Int32Ty, FrameSize)));649 MDNode *MD = MDTuple::get(F.getContext(), Data);650 F.setMetadata(LLVMContext::MD_annotation, MD);651 652 // Update shadow stack pointer in the function epilogue.653 IRB.SetInsertPoint(BasePointer->getNextNode());654 655 Value *StaticTop =656 IRB.CreatePtrAdd(BasePointer, ConstantInt::get(Int32Ty, -FrameSize),657 "unsafe_stack_static_top");658 IRB.CreateStore(StaticTop, UnsafeStackPtr);659 return StaticTop;660}661 662void SafeStack::moveDynamicAllocasToUnsafeStack(663 Function &F, Value *UnsafeStackPtr, AllocaInst *DynamicTop,664 ArrayRef<AllocaInst *> DynamicAllocas) {665 DIBuilder DIB(*F.getParent());666 667 for (AllocaInst *AI : DynamicAllocas) {668 IRBuilder<> IRB(AI);669 670 // Compute the new SP value (after AI).671 Value *ArraySize = AI->getArraySize();672 if (ArraySize->getType() != IntPtrTy)673 ArraySize = IRB.CreateIntCast(ArraySize, IntPtrTy, false);674 675 Type *Ty = AI->getAllocatedType();676 uint64_t TySize = DL.getTypeAllocSize(Ty);677 Value *Size = IRB.CreateMul(ArraySize, ConstantInt::get(IntPtrTy, TySize));678 679 Value *SP = IRB.CreatePtrToInt(IRB.CreateLoad(StackPtrTy, UnsafeStackPtr),680 IntPtrTy);681 SP = IRB.CreateSub(SP, Size);682 683 // Align the SP value to satisfy the AllocaInst, type and stack alignments.684 auto Align = std::max(std::max(DL.getPrefTypeAlign(Ty), AI->getAlign()),685 StackAlignment);686 687 Value *NewTop = IRB.CreateIntToPtr(688 IRB.CreateAnd(SP,689 ConstantInt::get(IntPtrTy, ~uint64_t(Align.value() - 1))),690 StackPtrTy);691 692 // Save the stack pointer.693 IRB.CreateStore(NewTop, UnsafeStackPtr);694 if (DynamicTop)695 IRB.CreateStore(NewTop, DynamicTop);696 697 Value *NewAI = IRB.CreatePointerCast(NewTop, AI->getType());698 if (AI->hasName() && isa<Instruction>(NewAI))699 NewAI->takeName(AI);700 701 replaceDbgDeclare(AI, NewAI, DIB, DIExpression::ApplyOffset, 0);702 AI->replaceAllUsesWith(NewAI);703 AI->eraseFromParent();704 }705 706 if (!DynamicAllocas.empty()) {707 // Now go through the instructions again, replacing stacksave/stackrestore.708 for (Instruction &I : llvm::make_early_inc_range(instructions(&F))) {709 auto *II = dyn_cast<IntrinsicInst>(&I);710 if (!II)711 continue;712 713 if (II->getIntrinsicID() == Intrinsic::stacksave) {714 IRBuilder<> IRB(II);715 Instruction *LI = IRB.CreateLoad(StackPtrTy, UnsafeStackPtr);716 LI->takeName(II);717 II->replaceAllUsesWith(LI);718 II->eraseFromParent();719 } else if (II->getIntrinsicID() == Intrinsic::stackrestore) {720 IRBuilder<> IRB(II);721 Instruction *SI = IRB.CreateStore(II->getArgOperand(0), UnsafeStackPtr);722 SI->takeName(II);723 assert(II->use_empty());724 II->eraseFromParent();725 }726 }727 }728}729 730bool SafeStack::ShouldInlinePointerAddress(CallInst &CI) {731 Function *Callee = CI.getCalledFunction();732 if (CI.hasFnAttr(Attribute::AlwaysInline) &&733 isInlineViable(*Callee).isSuccess())734 return true;735 if (Callee->isInterposable() || Callee->hasFnAttribute(Attribute::NoInline) ||736 CI.isNoInline())737 return false;738 return true;739}740 741void SafeStack::TryInlinePointerAddress() {742 auto *CI = dyn_cast<CallInst>(UnsafeStackPtr);743 if (!CI)744 return;745 746 if(F.hasOptNone())747 return;748 749 Function *Callee = CI->getCalledFunction();750 if (!Callee || Callee->isDeclaration())751 return;752 753 if (!ShouldInlinePointerAddress(*CI))754 return;755 756 InlineFunctionInfo IFI;757 InlineFunction(*CI, IFI);758}759 760bool SafeStack::run() {761 assert(F.hasFnAttribute(Attribute::SafeStack) &&762 "Can't run SafeStack on a function without the attribute");763 assert(!F.isDeclaration() && "Can't run SafeStack on a function declaration");764 765 ++NumFunctions;766 767 SmallVector<AllocaInst *, 16> StaticAllocas;768 SmallVector<AllocaInst *, 4> DynamicAllocas;769 SmallVector<Argument *, 4> ByValArguments;770 SmallVector<Instruction *, 4> Returns;771 772 // Collect all points where stack gets unwound and needs to be restored773 // This is only necessary because the runtime (setjmp and unwind code) is774 // not aware of the unsafe stack and won't unwind/restore it properly.775 // To work around this problem without changing the runtime, we insert776 // instrumentation to restore the unsafe stack pointer when necessary.777 SmallVector<Instruction *, 4> StackRestorePoints;778 779 // Find all static and dynamic alloca instructions that must be moved to the780 // unsafe stack, all return instructions and stack restore points.781 findInsts(F, StaticAllocas, DynamicAllocas, ByValArguments, Returns,782 StackRestorePoints);783 784 if (StaticAllocas.empty() && DynamicAllocas.empty() &&785 ByValArguments.empty() && StackRestorePoints.empty())786 return false; // Nothing to do in this function.787 788 if (!StaticAllocas.empty() || !DynamicAllocas.empty() ||789 !ByValArguments.empty())790 ++NumUnsafeStackFunctions; // This function has the unsafe stack.791 792 if (!StackRestorePoints.empty())793 ++NumUnsafeStackRestorePointsFunctions;794 795 IRBuilder<> IRB(&F.front(), F.begin()->getFirstInsertionPt());796 // Calls must always have a debug location, or else inlining breaks. So797 // we explicitly set a artificial debug location here.798 if (DISubprogram *SP = F.getSubprogram())799 IRB.SetCurrentDebugLocation(800 DILocation::get(SP->getContext(), SP->getScopeLine(), 0, SP));801 if (SafeStackUsePointerAddress) {802 const char *SafestackPointerAddressName =803 TL.getLibcallName(RTLIB::SAFESTACK_POINTER_ADDRESS);804 if (!SafestackPointerAddressName) {805 F.getContext().emitError(806 "no libcall available for safestack pointer address");807 return false;808 }809 810 FunctionCallee Fn = F.getParent()->getOrInsertFunction(811 SafestackPointerAddressName, IRB.getPtrTy(0));812 UnsafeStackPtr = IRB.CreateCall(Fn);813 } else {814 UnsafeStackPtr = TL.getSafeStackPointerLocation(IRB);815 }816 817 // Load the current stack pointer (we'll also use it as a base pointer).818 // FIXME: use a dedicated register for it ?819 Instruction *BasePointer =820 IRB.CreateLoad(StackPtrTy, UnsafeStackPtr, false, "unsafe_stack_ptr");821 assert(BasePointer->getType() == StackPtrTy);822 823 AllocaInst *StackGuardSlot = nullptr;824 // FIXME: implement weaker forms of stack protector.825 if (F.hasFnAttribute(Attribute::StackProtect) ||826 F.hasFnAttribute(Attribute::StackProtectStrong) ||827 F.hasFnAttribute(Attribute::StackProtectReq)) {828 Value *StackGuard = getStackGuard(IRB, F);829 StackGuardSlot = IRB.CreateAlloca(StackPtrTy, nullptr);830 IRB.CreateStore(StackGuard, StackGuardSlot);831 832 for (Instruction *RI : Returns) {833 IRBuilder<> IRBRet(RI);834 checkStackGuard(IRBRet, F, *RI, StackGuardSlot, StackGuard);835 }836 }837 838 // The top of the unsafe stack after all unsafe static allocas are839 // allocated.840 Value *StaticTop = moveStaticAllocasToUnsafeStack(841 IRB, F, StaticAllocas, ByValArguments, BasePointer, StackGuardSlot);842 843 // Safe stack object that stores the current unsafe stack top. It is updated844 // as unsafe dynamic (non-constant-sized) allocas are allocated and freed.845 // This is only needed if we need to restore stack pointer after longjmp846 // or exceptions, and we have dynamic allocations.847 // FIXME: a better alternative might be to store the unsafe stack pointer848 // before setjmp / invoke instructions.849 AllocaInst *DynamicTop = createStackRestorePoints(850 IRB, F, StackRestorePoints, StaticTop, !DynamicAllocas.empty());851 852 // Handle dynamic allocas.853 moveDynamicAllocasToUnsafeStack(F, UnsafeStackPtr, DynamicTop,854 DynamicAllocas);855 856 // Restore the unsafe stack pointer before each return.857 for (Instruction *RI : Returns) {858 IRB.SetInsertPoint(RI);859 IRB.CreateStore(BasePointer, UnsafeStackPtr);860 }861 862 TryInlinePointerAddress();863 864 LLVM_DEBUG(dbgs() << "[SafeStack] safestack applied\n");865 return true;866}867 868class SafeStackLegacyPass : public FunctionPass {869 const TargetMachine *TM = nullptr;870 871public:872 static char ID; // Pass identification, replacement for typeid..873 874 SafeStackLegacyPass() : FunctionPass(ID) {875 initializeSafeStackLegacyPassPass(*PassRegistry::getPassRegistry());876 }877 878 void getAnalysisUsage(AnalysisUsage &AU) const override {879 AU.addRequired<TargetPassConfig>();880 AU.addRequired<TargetLibraryInfoWrapperPass>();881 AU.addRequired<AssumptionCacheTracker>();882 AU.addPreserved<DominatorTreeWrapperPass>();883 }884 885 bool runOnFunction(Function &F) override {886 LLVM_DEBUG(dbgs() << "[SafeStack] Function: " << F.getName() << "\n");887 888 if (!F.hasFnAttribute(Attribute::SafeStack)) {889 LLVM_DEBUG(dbgs() << "[SafeStack] safestack is not requested"890 " for this function\n");891 return false;892 }893 894 if (F.isDeclaration()) {895 LLVM_DEBUG(dbgs() << "[SafeStack] function definition"896 " is not available\n");897 return false;898 }899 900 TM = &getAnalysis<TargetPassConfig>().getTM<TargetMachine>();901 auto *TL = TM->getSubtargetImpl(F)->getTargetLowering();902 if (!TL)903 report_fatal_error("TargetLowering instance is required");904 905 auto *DL = &F.getDataLayout();906 auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);907 auto &ACT = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);908 909 // Compute DT and LI only for functions that have the attribute.910 // This is only useful because the legacy pass manager doesn't let us911 // compute analyzes lazily.912 913 DominatorTree *DT;914 bool ShouldPreserveDominatorTree;915 std::optional<DominatorTree> LazilyComputedDomTree;916 917 // Do we already have a DominatorTree available from the previous pass?918 // Note that we should *NOT* require it, to avoid the case where we end up919 // not needing it, but the legacy PM would have computed it for us anyways.920 if (auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>()) {921 DT = &DTWP->getDomTree();922 ShouldPreserveDominatorTree = true;923 } else {924 // Otherwise, we need to compute it.925 LazilyComputedDomTree.emplace(F);926 DT = &*LazilyComputedDomTree;927 ShouldPreserveDominatorTree = false;928 }929 930 // Likewise, lazily compute loop info.931 LoopInfo LI(*DT);932 933 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);934 935 ScalarEvolution SE(F, TLI, ACT, *DT, LI);936 937 return SafeStack(F, *TL, *DL, ShouldPreserveDominatorTree ? &DTU : nullptr,938 SE)939 .run();940 }941};942 943} // end anonymous namespace944 945PreservedAnalyses SafeStackPass::run(Function &F,946 FunctionAnalysisManager &FAM) {947 LLVM_DEBUG(dbgs() << "[SafeStack] Function: " << F.getName() << "\n");948 949 if (!F.hasFnAttribute(Attribute::SafeStack)) {950 LLVM_DEBUG(dbgs() << "[SafeStack] safestack is not requested"951 " for this function\n");952 return PreservedAnalyses::all();953 }954 955 if (F.isDeclaration()) {956 LLVM_DEBUG(dbgs() << "[SafeStack] function definition"957 " is not available\n");958 return PreservedAnalyses::all();959 }960 961 auto *TL = TM->getSubtargetImpl(F)->getTargetLowering();962 if (!TL)963 report_fatal_error("TargetLowering instance is required");964 965 auto &DL = F.getDataLayout();966 967 // preserve DominatorTree968 auto &DT = FAM.getResult<DominatorTreeAnalysis>(F);969 auto &SE = FAM.getResult<ScalarEvolutionAnalysis>(F);970 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);971 972 bool Changed = SafeStack(F, *TL, DL, &DTU, SE).run();973 974 if (!Changed)975 return PreservedAnalyses::all();976 PreservedAnalyses PA;977 PA.preserve<DominatorTreeAnalysis>();978 return PA;979}980 981char SafeStackLegacyPass::ID = 0;982 983INITIALIZE_PASS_BEGIN(SafeStackLegacyPass, DEBUG_TYPE,984 "Safe Stack instrumentation pass", false, false)985INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)986INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)987INITIALIZE_PASS_END(SafeStackLegacyPass, DEBUG_TYPE,988 "Safe Stack instrumentation pass", false, false)989 990FunctionPass *llvm::createSafeStackPass() { return new SafeStackLegacyPass(); }991