LLVM  15.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"
18 #include "llvm/IR/BasicBlock.h"
19 #include "llvm/IR/IntrinsicInst.h"
20 
21 namespace llvm {
22 namespace memtag {
23 namespace {
24 bool maybeReachableFromEachOther(const SmallVectorImpl<IntrinsicInst *> &Insts,
25  const DominatorTree *DT, const LoopInfo *LI,
26  size_t MaxLifetimes) {
27  // If we have too many lifetime ends, give up, as the algorithm below is N^2.
28  if (Insts.size() > MaxLifetimes)
29  return true;
30  for (size_t I = 0; I < Insts.size(); ++I) {
31  for (size_t J = 0; J < Insts.size(); ++J) {
32  if (I == J)
33  continue;
34  if (isPotentiallyReachable(Insts[I], Insts[J], nullptr, DT, LI))
35  return true;
36  }
37  }
38  return false;
39 }
40 } // namespace
41 
43  const LoopInfo &LI, const Instruction *Start,
45  const SmallVectorImpl<Instruction *> &RetVec,
46  llvm::function_ref<void(Instruction *)> Callback) {
47  if (Ends.size() == 1 && PDT.dominates(Ends[0], Start)) {
48  Callback(Ends[0]);
49  return true;
50  }
52  for (auto *End : Ends) {
53  EndBlocks.insert(End->getParent());
54  }
55  SmallVector<Instruction *, 8> ReachableRetVec;
56  unsigned NumCoveredExits = 0;
57  for (auto *RI : RetVec) {
58  if (!isPotentiallyReachable(Start, RI, nullptr, &DT, &LI))
59  continue;
60  ReachableRetVec.push_back(RI);
61  // If there is an end in the same basic block as the return, we know for
62  // sure that the return is covered. Otherwise, we can check whether there
63  // is a way to reach the RI from the start of the lifetime without passing
64  // through an end.
65  if (EndBlocks.count(RI->getParent()) > 0 ||
66  !isPotentiallyReachable(Start, RI, &EndBlocks, &DT, &LI)) {
67  ++NumCoveredExits;
68  }
69  }
70  // If there's a mix of covered and non-covered exits, just put the untag
71  // on exits, so we avoid the redundancy of untagging twice.
72  if (NumCoveredExits == ReachableRetVec.size()) {
73  for (auto *End : Ends)
74  Callback(End);
75  } else {
76  for (auto *RI : ReachableRetVec)
77  Callback(RI);
78  // We may have inserted untag outside of the lifetime interval.
79  // Signal the caller to remove the lifetime end call for this alloca.
80  return false;
81  }
82  return true;
83 }
84 
86  const SmallVectorImpl<IntrinsicInst *> &LifetimeEnd,
87  const DominatorTree *DT, const LoopInfo *LI,
88  size_t MaxLifetimes) {
89  // An alloca that has exactly one start and end in every possible execution.
90  // If it has multiple ends, they have to be unreachable from each other, so
91  // at most one of them is actually used for each execution of the function.
92  return LifetimeStart.size() == 1 &&
93  (LifetimeEnd.size() == 1 ||
94  (LifetimeEnd.size() > 0 &&
95  !maybeReachableFromEachOther(LifetimeEnd, DT, LI, MaxLifetimes)));
96 }
97 
99  if (isa<ReturnInst>(Inst)) {
100  if (CallInst *CI = Inst.getParent()->getTerminatingMustTailCall())
101  return CI;
102  return &Inst;
103  }
104  if (isa<ResumeInst, CleanupReturnInst>(Inst)) {
105  return &Inst;
106  }
107  return nullptr;
108 }
109 
111  if (CallInst *CI = dyn_cast<CallInst>(&Inst)) {
112  if (CI->canReturnTwice()) {
113  Info.CallsReturnTwice = true;
114  }
115  }
116  if (AllocaInst *AI = dyn_cast<AllocaInst>(&Inst)) {
117  if (IsInterestingAlloca(*AI)) {
118  Info.AllocasToInstrument[AI].AI = AI;
119  }
120  return;
121  }
122  auto *II = dyn_cast<IntrinsicInst>(&Inst);
123  if (II && (II->getIntrinsicID() == Intrinsic::lifetime_start ||
124  II->getIntrinsicID() == Intrinsic::lifetime_end)) {
125  AllocaInst *AI = findAllocaForValue(II->getArgOperand(1));
126  if (!AI) {
127  Info.UnrecognizedLifetimes.push_back(&Inst);
128  return;
129  }
130  if (!IsInterestingAlloca(*AI))
131  return;
132  if (II->getIntrinsicID() == Intrinsic::lifetime_start)
133  Info.AllocasToInstrument[AI].LifetimeStart.push_back(II);
134  else
135  Info.AllocasToInstrument[AI].LifetimeEnd.push_back(II);
136  return;
137  }
138  if (auto *DVI = dyn_cast<DbgVariableIntrinsic>(&Inst)) {
139  for (Value *V : DVI->location_ops()) {
140  if (auto *AI = dyn_cast_or_null<AllocaInst>(V)) {
141  if (!IsInterestingAlloca(*AI))
142  continue;
143  AllocaInfo &AInfo = Info.AllocasToInstrument[AI];
144  auto &DVIVec = AInfo.DbgVariableIntrinsics;
145  if (DVIVec.empty() || DVIVec.back() != DVI)
146  DVIVec.push_back(DVI);
147  }
148  }
149  }
150  Instruction *ExitUntag = getUntagLocationIfFunctionExit(Inst);
151  if (ExitUntag)
152  Info.RetVec.push_back(ExitUntag);
153 }
154 
156  auto DL = AI.getModule()->getDataLayout();
157  return *AI.getAllocationSizeInBits(DL) / 8;
158 }
159 
161  const Align NewAlignment = std::max(Info.AI->getAlign(), Alignment);
162  Info.AI->setAlignment(NewAlignment);
163  auto &Ctx = Info.AI->getFunction()->getContext();
164 
165  uint64_t Size = getAllocaSizeInBytes(*Info.AI);
166  uint64_t AlignedSize = alignTo(Size, Alignment);
167  if (Size == AlignedSize)
168  return;
169 
170  // Add padding to the alloca.
171  Type *AllocatedType =
172  Info.AI->isArrayAllocation()
173  ? ArrayType::get(
174  Info.AI->getAllocatedType(),
175  cast<ConstantInt>(Info.AI->getArraySize())->getZExtValue())
176  : Info.AI->getAllocatedType();
177  Type *PaddingType = ArrayType::get(Type::getInt8Ty(Ctx), AlignedSize - Size);
178  Type *TypeWithPadding = StructType::get(AllocatedType, PaddingType);
179  auto *NewAI =
180  new AllocaInst(TypeWithPadding, Info.AI->getType()->getAddressSpace(),
181  nullptr, "", Info.AI);
182  NewAI->takeName(Info.AI);
183  NewAI->setAlignment(Info.AI->getAlign());
184  NewAI->setUsedWithInAlloca(Info.AI->isUsedWithInAlloca());
185  NewAI->setSwiftError(Info.AI->isSwiftError());
186  NewAI->copyMetadata(*Info.AI);
187 
188  auto *NewPtr = new BitCastInst(NewAI, Info.AI->getType(), "", Info.AI);
189  Info.AI->replaceAllUsesWith(NewPtr);
190  Info.AI->eraseFromParent();
191  Info.AI = NewAI;
192 }
193 
194 } // namespace memtag
195 } // 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
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
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:65
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
IntrinsicInst.h
llvm::memtag::AllocaInfo::DbgVariableIntrinsics
SmallVector< DbgVariableIntrinsic *, 2 > DbgVariableIntrinsics
Definition: MemoryTaggingSupport.h:53
llvm::BitCastInst
This class represents a no-op cast from one type to another.
Definition: Instructions.h:5212
llvm::SmallVector< Instruction *, 8 >
llvm::memtag::StackInfo::CallsReturnTwice
bool CallsReturnTwice
Definition: MemoryTaggingSupport.h:60
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:42
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:59
PostDominators.h
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:232
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:57
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:58
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:49
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:1102
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:110
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:85
llvm::memtag::alignAndPadAlloca
void alignAndPadAlloca(memtag::AllocaInfo &Info, llvm::Align Align)
Definition: MemoryTaggingSupport.cpp:160
llvm::memtag::StackInfo::AllocasToInstrument
MapVector< AllocaInst *, AllocaInfo > AllocasToInstrument
Definition: MemoryTaggingSupport.h:57
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:91
llvm::memtag::getAllocaSizeInBytes
uint64_t getAllocaSizeInBytes(const AllocaInst &AI)
Definition: MemoryTaggingSupport.cpp:155
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:398
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1461
llvm::AllocaInst
an instruction to allocate memory on the stack
Definition: Instructions.h:58
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::memtag::getUntagLocationIfFunctionExit
Instruction * getUntagLocationIfFunctionExit(Instruction &Inst)
Definition: MemoryTaggingSupport.cpp:98
llvm::findAllocaForValue
AllocaInst * findAllocaForValue(Value *V, bool OffsetZero=false)
Returns unique alloca where the value comes from, or nullptr.
Definition: ValueTracking.cpp:4599
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