LLVM  16.0.0git
MemoryTaggingSupport.cpp
Go to the documentation of this file.
1 //== MemoryTaggingSupport.cpp - helpers for memory tagging implementations ===//
2 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
3 // See https://llvm.org/LICENSE.txt for license information.
4 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
5 //
6 //===----------------------------------------------------------------------===//
7 //
8 // This file declares common infrastructure for HWAddressSanitizer and
9 // Aarch64StackTagging.
10 //
11 //===----------------------------------------------------------------------===//
12 
14 
15 #include "llvm/Analysis/CFG.h"
19 #include "llvm/IR/BasicBlock.h"
20 #include "llvm/IR/IntrinsicInst.h"
22 
23 namespace llvm {
24 namespace memtag {
25 namespace {
26 bool maybeReachableFromEachOther(const SmallVectorImpl<IntrinsicInst *> &Insts,
27  const DominatorTree *DT, const LoopInfo *LI,
28  size_t MaxLifetimes) {
29  // If we have too many lifetime ends, give up, as the algorithm below is N^2.
30  if (Insts.size() > MaxLifetimes)
31  return true;
32  for (size_t I = 0; I < Insts.size(); ++I) {
33  for (size_t J = 0; J < Insts.size(); ++J) {
34  if (I == J)
35  continue;
36  if (isPotentiallyReachable(Insts[I], Insts[J], nullptr, DT, LI))
37  return true;
38  }
39  }
40  return false;
41 }
42 } // namespace
43 
45  const LoopInfo &LI, const Instruction *Start,
47  const SmallVectorImpl<Instruction *> &RetVec,
48  llvm::function_ref<void(Instruction *)> Callback) {
49  if (Ends.size() == 1 && PDT.dominates(Ends[0], Start)) {
50  Callback(Ends[0]);
51  return true;
52  }
54  for (auto *End : Ends) {
55  EndBlocks.insert(End->getParent());
56  }
57  SmallVector<Instruction *, 8> ReachableRetVec;
58  unsigned NumCoveredExits = 0;
59  for (auto *RI : RetVec) {
60  if (!isPotentiallyReachable(Start, RI, nullptr, &DT, &LI))
61  continue;
62  ReachableRetVec.push_back(RI);
63  // If there is an end in the same basic block as the return, we know for
64  // sure that the return is covered. Otherwise, we can check whether there
65  // is a way to reach the RI from the start of the lifetime without passing
66  // through an end.
67  if (EndBlocks.count(RI->getParent()) > 0 ||
68  !isPotentiallyReachable(Start, RI, &EndBlocks, &DT, &LI)) {
69  ++NumCoveredExits;
70  }
71  }
72  // If there's a mix of covered and non-covered exits, just put the untag
73  // on exits, so we avoid the redundancy of untagging twice.
74  if (NumCoveredExits == ReachableRetVec.size()) {
75  for (auto *End : Ends)
76  Callback(End);
77  } else {
78  for (auto *RI : ReachableRetVec)
79  Callback(RI);
80  // We may have inserted untag outside of the lifetime interval.
81  // Signal the caller to remove the lifetime end call for this alloca.
82  return false;
83  }
84  return true;
85 }
86 
88  const SmallVectorImpl<IntrinsicInst *> &LifetimeEnd,
89  const DominatorTree *DT, const LoopInfo *LI,
90  size_t MaxLifetimes) {
91  // An alloca that has exactly one start and end in every possible execution.
92  // If it has multiple ends, they have to be unreachable from each other, so
93  // at most one of them is actually used for each execution of the function.
94  return LifetimeStart.size() == 1 &&
95  (LifetimeEnd.size() == 1 ||
96  (LifetimeEnd.size() > 0 &&
97  !maybeReachableFromEachOther(LifetimeEnd, DT, LI, MaxLifetimes)));
98 }
99 
101  if (isa<ReturnInst>(Inst)) {
102  if (CallInst *CI = Inst.getParent()->getTerminatingMustTailCall())
103  return CI;
104  return &Inst;
105  }
106  if (isa<ResumeInst, CleanupReturnInst>(Inst)) {
107  return &Inst;
108  }
109  return nullptr;
110 }
111 
113  if (CallInst *CI = dyn_cast<CallInst>(&Inst)) {
114  if (CI->canReturnTwice()) {
115  Info.CallsReturnTwice = true;
116  }
117  }
118  if (AllocaInst *AI = dyn_cast<AllocaInst>(&Inst)) {
119  if (isInterestingAlloca(*AI)) {
120  Info.AllocasToInstrument[AI].AI = AI;
121  }
122  return;
123  }
124  auto *II = dyn_cast<IntrinsicInst>(&Inst);
125  if (II && (II->getIntrinsicID() == Intrinsic::lifetime_start ||
126  II->getIntrinsicID() == Intrinsic::lifetime_end)) {
127  AllocaInst *AI = findAllocaForValue(II->getArgOperand(1));
128  if (!AI) {
129  Info.UnrecognizedLifetimes.push_back(&Inst);
130  return;
131  }
132  if (!isInterestingAlloca(*AI))
133  return;
134  if (II->getIntrinsicID() == Intrinsic::lifetime_start)
135  Info.AllocasToInstrument[AI].LifetimeStart.push_back(II);
136  else
137  Info.AllocasToInstrument[AI].LifetimeEnd.push_back(II);
138  return;
139  }
140  if (auto *DVI = dyn_cast<DbgVariableIntrinsic>(&Inst)) {
141  for (Value *V : DVI->location_ops()) {
142  if (auto *AI = dyn_cast_or_null<AllocaInst>(V)) {
143  if (!isInterestingAlloca(*AI))
144  continue;
145  AllocaInfo &AInfo = Info.AllocasToInstrument[AI];
146  auto &DVIVec = AInfo.DbgVariableIntrinsics;
147  if (DVIVec.empty() || DVIVec.back() != DVI)
148  DVIVec.push_back(DVI);
149  }
150  }
151  }
152  Instruction *ExitUntag = getUntagLocationIfFunctionExit(Inst);
153  if (ExitUntag)
154  Info.RetVec.push_back(ExitUntag);
155 }
156 
158  return (AI.getAllocatedType()->isSized() &&
159  // FIXME: instrument dynamic allocas, too
160  AI.isStaticAlloca() &&
161  // alloca() may be called with 0 size, ignore it.
163  // We are only interested in allocas not promotable to registers.
164  // Promotable allocas are common under -O0.
165  !isAllocaPromotable(&AI) &&
166  // inalloca allocas are not treated as static, and we don't want
167  // dynamic alloca instrumentation for them as well.
168  !AI.isUsedWithInAlloca() &&
169  // swifterror allocas are register promoted by ISel
170  !AI.isSwiftError()) &&
171  // safe allocas are not interesting
172  !(SSI && SSI->isSafe(AI));
173 }
174 
176  auto DL = AI.getModule()->getDataLayout();
177  return *AI.getAllocationSizeInBits(DL) / 8;
178 }
179 
181  const Align NewAlignment = std::max(Info.AI->getAlign(), Alignment);
182  Info.AI->setAlignment(NewAlignment);
183  auto &Ctx = Info.AI->getFunction()->getContext();
184 
185  uint64_t Size = getAllocaSizeInBytes(*Info.AI);
186  uint64_t AlignedSize = alignTo(Size, Alignment);
187  if (Size == AlignedSize)
188  return;
189 
190  // Add padding to the alloca.
191  Type *AllocatedType =
192  Info.AI->isArrayAllocation()
193  ? ArrayType::get(
194  Info.AI->getAllocatedType(),
195  cast<ConstantInt>(Info.AI->getArraySize())->getZExtValue())
196  : Info.AI->getAllocatedType();
197  Type *PaddingType = ArrayType::get(Type::getInt8Ty(Ctx), AlignedSize - Size);
198  Type *TypeWithPadding = StructType::get(AllocatedType, PaddingType);
199  auto *NewAI = new AllocaInst(TypeWithPadding, Info.AI->getAddressSpace(),
200  nullptr, "", Info.AI);
201  NewAI->takeName(Info.AI);
202  NewAI->setAlignment(Info.AI->getAlign());
203  NewAI->setUsedWithInAlloca(Info.AI->isUsedWithInAlloca());
204  NewAI->setSwiftError(Info.AI->isSwiftError());
205  NewAI->copyMetadata(*Info.AI);
206 
207  Value *NewPtr = NewAI;
208 
209  // TODO: Remove when typed pointers dropped
210  if (Info.AI->getType() != NewAI->getType())
211  NewPtr = new BitCastInst(NewAI, Info.AI->getType(), "", Info.AI);
212 
213  Info.AI->replaceAllUsesWith(NewPtr);
214  Info.AI->eraseFromParent();
215  Info.AI = NewAI;
216 }
217 
218 } // namespace memtag
219 } // namespace llvm
llvm::alignTo
uint64_t alignTo(uint64_t Size, Align A)
Returns a multiple of A needed to store Size bytes.
Definition: Alignment.h:156
StackSafetyAnalysis.h
llvm::Type::isSized
bool isSized(SmallPtrSetImpl< Type * > *Visited=nullptr) const
Return true if it makes sense to take the size of this type.
Definition: Type.h:283
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::Instruction::getModule
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:69
llvm::StructType::get
static StructType * get(LLVMContext &Context, ArrayRef< Type * > Elements, bool isPacked=false)
This static method is the primary way to create a literal StructType.
Definition: Type.cpp:406
llvm::StackSafetyGlobalInfo::isSafe
bool isSafe(const AllocaInst &AI) const
Definition: StackSafetyAnalysis.cpp:966
IntrinsicInst.h
llvm::memtag::AllocaInfo::DbgVariableIntrinsics
SmallVector< DbgVariableIntrinsic *, 2 > DbgVariableIntrinsics
Definition: MemoryTaggingSupport.h:54
llvm::BitCastInst
This class represents a no-op cast from one type to another.
Definition: Instructions.h:5256
llvm::SmallVector< Instruction *, 8 >
llvm::memtag::StackInfo::CallsReturnTwice
bool CallsReturnTwice
Definition: MemoryTaggingSupport.h:61
ValueTracking.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
llvm::memtag::forAllReachableExits
bool forAllReachableExits(const DominatorTree &DT, const PostDominatorTree &PDT, const LoopInfo &LI, const Instruction *Start, const SmallVectorImpl< IntrinsicInst * > &Ends, const SmallVectorImpl< Instruction * > &RetVec, llvm::function_ref< void(Instruction *)> Callback)
Definition: MemoryTaggingSupport.cpp:44
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
llvm::max
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:337
llvm::Type::getInt8Ty
static IntegerType * getInt8Ty(LLVMContext &C)
Definition: Type.cpp:237
llvm::memtag::StackInfo::RetVec
SmallVector< Instruction *, 8 > RetVec
Definition: MemoryTaggingSupport.h:60
llvm::AllocaInst::isStaticAlloca
bool isStaticAlloca() const
Return true if this alloca is in the entry block of the function and is a constant size.
Definition: Instructions.cpp:1507
PostDominators.h
llvm::AllocaInst::getAllocatedType
Type * getAllocatedType() const
Return the type that is being allocated by the instruction.
Definition: Instructions.h:115
MemoryTaggingSupport.h
llvm::isPotentiallyReachable
bool isPotentiallyReachable(const Instruction *From, const Instruction *To, const SmallPtrSetImpl< BasicBlock * > *ExclusionSet=nullptr, const DominatorTree *DT=nullptr, const LoopInfo *LI=nullptr)
Determine whether instruction 'To' is reachable from 'From', without passing through any blocks in Ex...
Definition: CFG.cpp:231
llvm::Instruction
Definition: Instruction.h:42
Info
Analysis containing CSE Info
Definition: CSEInfo.cpp:27
llvm::Align
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:39
llvm::AllocaInst::getAllocationSizeInBits
Optional< TypeSize > getAllocationSizeInBits(const DataLayout &DL) const
Get allocation size in bits.
Definition: Instructions.cpp:59
llvm::AllocaInst::isSwiftError
bool isSwiftError() const
Return true if this alloca is used as a swifterror argument to a call.
Definition: Instructions.h:147
llvm::function_ref
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLFunctionalExtras.h:36
BasicBlock.h
uint64_t
llvm::memtag::StackInfo::UnrecognizedLifetimes
SmallVector< Instruction *, 4 > UnrecognizedLifetimes
Definition: MemoryTaggingSupport.h:59
llvm::memtag::StackInfoBuilder::isInterestingAlloca
bool isInterestingAlloca(const AllocaInst &AI)
Definition: MemoryTaggingSupport.cpp:157
PromoteMemToReg.h
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::ArrayType::get
static ArrayType * get(Type *ElementType, uint64_t NumElements)
This static method is the primary way to construct an ArrayType.
Definition: Type.cpp:638
llvm::memtag::AllocaInfo
Definition: MemoryTaggingSupport.h:50
llvm::SmallPtrSetImpl::count
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:383
CFG.h
llvm::LoopInfo
Definition: LoopInfo.h:1108
llvm::PostDominatorTree
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
Definition: PostDominators.h:28
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::memtag::StackInfoBuilder::visit
void visit(Instruction &Inst)
Definition: MemoryTaggingSupport.cpp:112
llvm::memtag::isStandardLifetime
bool isStandardLifetime(const SmallVectorImpl< IntrinsicInst * > &LifetimeStart, const SmallVectorImpl< IntrinsicInst * > &LifetimeEnd, const DominatorTree *DT, const LoopInfo *LI, size_t MaxLifetimes)
Definition: MemoryTaggingSupport.cpp:87
llvm::memtag::alignAndPadAlloca
void alignAndPadAlloca(memtag::AllocaInfo &Info, llvm::Align Align)
Definition: MemoryTaggingSupport.cpp:180
llvm::memtag::StackInfo::AllocasToInstrument
MapVector< AllocaInst *, AllocaInfo > AllocasToInstrument
Definition: MemoryTaggingSupport.h:58
llvm::AllocaInst::isUsedWithInAlloca
bool isUsedWithInAlloca() const
Return true if this alloca is used as an inalloca argument to a call.
Definition: Instructions.h:137
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:91
llvm::memtag::getAllocaSizeInBytes
uint64_t getAllocaSizeInBytes(const AllocaInst &AI)
Definition: MemoryTaggingSupport.cpp:175
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
llvm::Module::getDataLayout
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.cpp:399
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1474
llvm::AllocaInst
an instruction to allocate memory on the stack
Definition: Instructions.h:59
llvm::BasicBlock::getTerminatingMustTailCall
const CallInst * getTerminatingMustTailCall() const
Returns the call instruction marked 'musttail' prior to the terminating return instruction of this ba...
Definition: BasicBlock.cpp:151
llvm::PostDominatorTree::dominates
bool dominates(const Instruction *I1, const Instruction *I2) const
Return true if I1 dominates I2.
Definition: PostDominators.cpp:54
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::isAllocaPromotable
bool isAllocaPromotable(const AllocaInst *AI)
Return true if this alloca is legal for promotion.
Definition: PromoteMemoryToRegister.cpp:63
llvm::memtag::getUntagLocationIfFunctionExit
Instruction * getUntagLocationIfFunctionExit(Instruction &Inst)
Definition: MemoryTaggingSupport.cpp:100
llvm::findAllocaForValue
AllocaInst * findAllocaForValue(Value *V, bool OffsetZero=false)
Returns unique alloca where the value comes from, or nullptr.
Definition: ValueTracking.cpp:4648
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:365