LLVM 19.0.0git
Go to the documentation of this file.
1//===- BoundsChecking.cpp - Instrumentation for run-time bounds checking --===//
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
10#include "llvm/ADT/Statistic.h"
11#include "llvm/ADT/Twine.h"
16#include "llvm/IR/BasicBlock.h"
17#include "llvm/IR/Constants.h"
18#include "llvm/IR/DataLayout.h"
19#include "llvm/IR/Function.h"
20#include "llvm/IR/IRBuilder.h"
22#include "llvm/IR/Instruction.h"
24#include "llvm/IR/Intrinsics.h"
25#include "llvm/IR/Value.h"
28#include "llvm/Support/Debug.h"
30#include <cstdint>
31#include <utility>
33using namespace llvm;
35#define DEBUG_TYPE "bounds-checking"
37static cl::opt<bool> SingleTrapBB("bounds-checking-single-trap",
38 cl::desc("Use one trap block per function"));
40static cl::opt<bool> DebugTrapBB("bounds-checking-unique-traps",
41 cl::desc("Always use one trap per check"));
43STATISTIC(ChecksAdded, "Bounds checks added");
44STATISTIC(ChecksSkipped, "Bounds checks skipped");
45STATISTIC(ChecksUnable, "Bounds checks unable to add");
49/// Gets the conditions under which memory accessing instructions will overflow.
51/// \p Ptr is the pointer that will be read/written, and \p InstVal is either
52/// the result from the load or the value being stored. It is used to determine
53/// the size of memory block that is touched.
55/// Returns the condition under which the access will overflow.
57 const DataLayout &DL, TargetLibraryInfo &TLI,
58 ObjectSizeOffsetEvaluator &ObjSizeEval,
59 BuilderTy &IRB, ScalarEvolution &SE) {
60 TypeSize NeededSize = DL.getTypeStoreSize(InstVal->getType());
61 LLVM_DEBUG(dbgs() << "Instrument " << *Ptr << " for " << Twine(NeededSize)
62 << " bytes\n");
64 SizeOffsetValue SizeOffset = ObjSizeEval.compute(Ptr);
66 if (!SizeOffset.bothKnown()) {
67 ++ChecksUnable;
68 return nullptr;
69 }
71 Value *Size = SizeOffset.Size;
72 Value *Offset = SizeOffset.Offset;
73 ConstantInt *SizeCI = dyn_cast<ConstantInt>(Size);
75 Type *IndexTy = DL.getIndexType(Ptr->getType());
76 Value *NeededSizeVal = IRB.CreateTypeSize(IndexTy, NeededSize);
78 auto SizeRange = SE.getUnsignedRange(SE.getSCEV(Size));
79 auto OffsetRange = SE.getUnsignedRange(SE.getSCEV(Offset));
80 auto NeededSizeRange = SE.getUnsignedRange(SE.getSCEV(NeededSizeVal));
82 // three checks are required to ensure safety:
83 // . Offset >= 0 (since the offset is given from the base ptr)
84 // . Size >= Offset (unsigned)
85 // . Size - Offset >= NeededSize (unsigned)
86 //
87 // optimization: if Size >= 0 (signed), skip 1st check
88 // FIXME: add NSW/NUW here? -- we dont care if the subtraction overflows
89 Value *ObjSize = IRB.CreateSub(Size, Offset);
90 Value *Cmp2 = SizeRange.getUnsignedMin().uge(OffsetRange.getUnsignedMax())
91 ? ConstantInt::getFalse(Ptr->getContext())
93 Value *Cmp3 = SizeRange.sub(OffsetRange)
94 .getUnsignedMin()
95 .uge(NeededSizeRange.getUnsignedMax())
96 ? ConstantInt::getFalse(Ptr->getContext())
97 : IRB.CreateICmpULT(ObjSize, NeededSizeVal);
98 Value *Or = IRB.CreateOr(Cmp2, Cmp3);
99 if ((!SizeCI || SizeCI->getValue().slt(0)) &&
100 !SizeRange.getSignedMin().isNonNegative()) {
101 Value *Cmp1 = IRB.CreateICmpSLT(Offset, ConstantInt::get(IndexTy, 0));
102 Or = IRB.CreateOr(Cmp1, Or);
103 }
105 return Or;
108/// Adds run-time bounds checks to memory accessing instructions.
110/// \p Or is the condition that should guard the trap.
112/// \p GetTrapBB is a callable that returns the trap BB to use on failure.
113template <typename GetTrapBBT>
114static void insertBoundsCheck(Value *Or, BuilderTy &IRB, GetTrapBBT GetTrapBB) {
115 // check if the comparison is always false
116 ConstantInt *C = dyn_cast_or_null<ConstantInt>(Or);
117 if (C) {
118 ++ChecksSkipped;
119 // If non-zero, nothing to do.
120 if (!C->getZExtValue())
121 return;
122 }
123 ++ChecksAdded;
126 BasicBlock *OldBB = SplitI->getParent();
127 BasicBlock *Cont = OldBB->splitBasicBlock(SplitI);
128 OldBB->getTerminator()->eraseFromParent();
130 if (C) {
131 // If we have a constant zero, unconditionally branch.
132 // FIXME: We should really handle this differently to bypass the splitting
133 // the block.
134 BranchInst::Create(GetTrapBB(IRB), OldBB);
135 return;
136 }
138 // Create the conditional branch.
139 BranchInst::Create(GetTrapBB(IRB), Cont, Or, OldBB);
143 ScalarEvolution &SE) {
144 if (F.hasFnAttribute(Attribute::NoSanitizeBounds))
145 return false;
147 const DataLayout &DL = F.getDataLayout();
148 ObjectSizeOpts EvalOpts;
149 EvalOpts.RoundToAlign = true;
150 EvalOpts.EvalMode = ObjectSizeOpts::Mode::ExactUnderlyingSizeAndOffset;
151 ObjectSizeOffsetEvaluator ObjSizeEval(DL, &TLI, F.getContext(), EvalOpts);
153 // check HANDLE_MEMORY_INST in include/llvm/Instruction.def for memory
154 // touching instructions
156 for (Instruction &I : instructions(F)) {
157 Value *Or = nullptr;
158 BuilderTy IRB(I.getParent(), BasicBlock::iterator(&I), TargetFolder(DL));
159 if (LoadInst *LI = dyn_cast<LoadInst>(&I)) {
160 if (!LI->isVolatile())
161 Or = getBoundsCheckCond(LI->getPointerOperand(), LI, DL, TLI,
162 ObjSizeEval, IRB, SE);
163 } else if (StoreInst *SI = dyn_cast<StoreInst>(&I)) {
164 if (!SI->isVolatile())
165 Or = getBoundsCheckCond(SI->getPointerOperand(), SI->getValueOperand(),
166 DL, TLI, ObjSizeEval, IRB, SE);
167 } else if (AtomicCmpXchgInst *AI = dyn_cast<AtomicCmpXchgInst>(&I)) {
168 if (!AI->isVolatile())
169 Or =
170 getBoundsCheckCond(AI->getPointerOperand(), AI->getCompareOperand(),
171 DL, TLI, ObjSizeEval, IRB, SE);
172 } else if (AtomicRMWInst *AI = dyn_cast<AtomicRMWInst>(&I)) {
173 if (!AI->isVolatile())
174 Or = getBoundsCheckCond(AI->getPointerOperand(), AI->getValOperand(),
175 DL, TLI, ObjSizeEval, IRB, SE);
176 }
177 if (Or)
178 TrapInfo.push_back(std::make_pair(&I, Or));
179 }
181 // Create a trapping basic block on demand using a callback. Depending on
182 // flags, this will either create a single block for the entire function or
183 // will create a fresh block every time it is called.
184 BasicBlock *TrapBB = nullptr;
185 auto GetTrapBB = [&TrapBB](BuilderTy &IRB) {
186 Function *Fn = IRB.GetInsertBlock()->getParent();
187 auto DebugLoc = IRB.getCurrentDebugLocation();
190 if (TrapBB && SingleTrapBB && !DebugTrapBB)
191 return TrapBB;
193 TrapBB = BasicBlock::Create(Fn->getContext(), "trap", Fn);
194 IRB.SetInsertPoint(TrapBB);
196 Intrinsic::ID IntrID = DebugTrapBB ? Intrinsic::ubsantrap : Intrinsic::trap;
197 auto *F = Intrinsic::getDeclaration(Fn->getParent(), IntrID);
199 CallInst *TrapCall;
200 if (DebugTrapBB) {
201 TrapCall =
202 IRB.CreateCall(F, ConstantInt::get(IRB.getInt8Ty(), Fn->size()));
203 } else {
204 TrapCall = IRB.CreateCall(F, {});
205 }
207 TrapCall->setDoesNotReturn();
208 TrapCall->setDoesNotThrow();
209 TrapCall->setDebugLoc(DebugLoc);
210 IRB.CreateUnreachable();
212 return TrapBB;
213 };
215 // Add the checks.
216 for (const auto &Entry : TrapInfo) {
217 Instruction *Inst = Entry.first;
219 insertBoundsCheck(Entry.second, IRB, GetTrapBB);
220 }
222 return !TrapInfo.empty();
226 auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
227 auto &SE = AM.getResult<ScalarEvolutionAnalysis>(F);
229 if (!addBoundsChecking(F, TLI, SE))
230 return PreservedAnalyses::all();
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Expand Atomic instructions
static void insertBoundsCheck(Value *Or, BuilderTy &IRB, GetTrapBBT GetTrapBB)
Adds run-time bounds checks to memory accessing instructions.
static cl::opt< bool > DebugTrapBB("bounds-checking-unique-traps", cl::desc("Always use one trap per check"))
static Value * getBoundsCheckCond(Value *Ptr, Value *InstVal, const DataLayout &DL, TargetLibraryInfo &TLI, ObjectSizeOffsetEvaluator &ObjSizeEval, BuilderTy &IRB, ScalarEvolution &SE)
Gets the conditions under which memory accessing instructions will overflow.
static bool addBoundsChecking(Function &F, TargetLibraryInfo &TLI, ScalarEvolution &SE)
static cl::opt< bool > SingleTrapBB("bounds-checking-single-trap", cl::desc("Use one trap block per function"))
This file contains the declarations for the subclasses of Constant, which represent the different fla...
#define LLVM_DEBUG(X)
Definition: Debug.h:101
uint64_t Size
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
Definition: Statistic.h:167
bool slt(const APInt &RHS) const
Signed less than comparison.
Definition: APInt.h:1110
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:253
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:405
An instruction that atomically checks whether a specified value is in a memory location,...
Definition: Instructions.h:495
an instruction that atomically reads a memory location, combines it with another value,...
Definition: Instructions.h:696
LLVM Basic Block Representation.
Definition: BasicBlock.h:61
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:202
BasicBlock * splitBasicBlock(iterator I, const Twine &BBName="", bool Before=false)
Split the basic block into two basic blocks at the specified instruction.
Definition: BasicBlock.cpp:575
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:209
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:167
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.h:229
static BranchInst * Create(BasicBlock *IfTrue, InsertPosition InsertBefore=nullptr)
void setDoesNotReturn()
Definition: InstrTypes.h:2009
void setDoesNotThrow()
Definition: InstrTypes.h:2016
This class represents a function call, abstracting a target machine's calling convention.
This is the shared class of boolean and integer constants.
Definition: Constants.h:81
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:857
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:146
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:110
A debug info location.
Definition: DebugLoc.h:33
size_t size() const
Definition: Function.h:821
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function.
Definition: Function.cpp:358
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:656
Value * CreateICmpULT(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:2262
BasicBlock::iterator GetInsertPoint() const
Definition: IRBuilder.h:172
Value * CreateTypeSize(Type *DstType, TypeSize Size)
Create an expression which evaluates to the number of units in Size at runtime.
Definition: IRBuilder.cpp:105
Value * CreateSub(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1349
Value * CreateOr(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1502
Value * CreateICmpSLT(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:2278
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:2671
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:92
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:473
An instruction for reading from memory.
Definition: Instructions.h:174
Evaluate the size and offset of an object pointed to by a Value*.
SizeOffsetValue compute(Value *V)
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:111
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition: Analysis.h:114
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:117
Analysis pass that exposes the ScalarEvolution for a function.
The main scalar evolution driver.
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
ConstantRange getUnsignedRange(const SCEV *S)
Determine the unsigned range for a particular SCEV.
bool empty() const
Definition: SmallVector.h:94
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
An instruction for storing to memory.
Definition: Instructions.h:290
TargetFolder - Create constants with target dependent folding.
Definition: TargetFolder.h:34
Analysis pass providing the TargetLibraryInfo.
Provides information about what library functions are available for the current target.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
LLVM Value Representation.
Definition: Value.h:74
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
const ParentTy * getParent() const
Definition: ilist_node.h:32
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
Function * getDeclaration(Module *M, ID id, ArrayRef< Type * > Tys=std::nullopt)
Create or insert an LLVM Function declaration for an intrinsic, and return it.
Definition: Function.cpp:1513
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
@ Offset
Definition: DWP.cpp:480
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
@ Or
Bitwise or logical OR of integers.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Various options to control the behavior of getObjectSize.
Mode EvalMode
How we want to evaluate this object's size.
bool RoundToAlign
Whether to round the result up to the alignment of allocas, byval arguments, and global variables.
bool bothKnown() const