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