1 | //===-- Lint.cpp - Check for common errors in LLVM IR ---------------------===// |
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 statically checks for common and easily-identified constructs |
10 | // which produce undefined or likely unintended behavior in LLVM IR. |
11 | // |
12 | // It is not a guarantee of correctness, in two ways. First, it isn't |
13 | // comprehensive. There are checks which could be done statically which are |
14 | // not yet implemented. Some of these are indicated by TODO comments, but |
15 | // those aren't comprehensive either. Second, many conditions cannot be |
16 | // checked statically. This pass does no dynamic instrumentation, so it |
17 | // can't check for all possible problems. |
18 | // |
19 | // Another limitation is that it assumes all code will be executed. A store |
20 | // through a null pointer in a basic block which is never reached is harmless, |
21 | // but this pass will warn about it anyway. This is the main reason why most |
22 | // of these checks live here instead of in the Verifier pass. |
23 | // |
24 | // Optimization passes may make conditions that this pass checks for more or |
25 | // less obvious. If an optimization pass appears to be introducing a warning, |
26 | // it may be that the optimization pass is merely exposing an existing |
27 | // condition in the code. |
28 | // |
29 | // This code may be run before instcombine. In many cases, instcombine checks |
30 | // for the same kinds of things and turns instructions with undefined behavior |
31 | // into unreachable (or equivalent). Because of this, this pass makes some |
32 | // effort to look through bitcasts and so on. |
33 | // |
34 | //===----------------------------------------------------------------------===// |
35 | |
36 | #include "llvm/Analysis/Lint.h" |
37 | #include "llvm/ADT/APInt.h" |
38 | #include "llvm/ADT/ArrayRef.h" |
39 | #include "llvm/ADT/SmallPtrSet.h" |
40 | #include "llvm/ADT/Twine.h" |
41 | #include "llvm/Analysis/AliasAnalysis.h" |
42 | #include "llvm/Analysis/AssumptionCache.h" |
43 | #include "llvm/Analysis/BasicAliasAnalysis.h" |
44 | #include "llvm/Analysis/ConstantFolding.h" |
45 | #include "llvm/Analysis/InstructionSimplify.h" |
46 | #include "llvm/Analysis/Loads.h" |
47 | #include "llvm/Analysis/MemoryLocation.h" |
48 | #include "llvm/Analysis/ScopedNoAliasAA.h" |
49 | #include "llvm/Analysis/TargetLibraryInfo.h" |
50 | #include "llvm/Analysis/TypeBasedAliasAnalysis.h" |
51 | #include "llvm/Analysis/ValueTracking.h" |
52 | #include "llvm/IR/Argument.h" |
53 | #include "llvm/IR/BasicBlock.h" |
54 | #include "llvm/IR/Constant.h" |
55 | #include "llvm/IR/Constants.h" |
56 | #include "llvm/IR/DataLayout.h" |
57 | #include "llvm/IR/DerivedTypes.h" |
58 | #include "llvm/IR/Dominators.h" |
59 | #include "llvm/IR/Function.h" |
60 | #include "llvm/IR/GlobalVariable.h" |
61 | #include "llvm/IR/InstVisitor.h" |
62 | #include "llvm/IR/InstrTypes.h" |
63 | #include "llvm/IR/Instruction.h" |
64 | #include "llvm/IR/Instructions.h" |
65 | #include "llvm/IR/IntrinsicInst.h" |
66 | #include "llvm/IR/Module.h" |
67 | #include "llvm/IR/PassManager.h" |
68 | #include "llvm/IR/Type.h" |
69 | #include "llvm/IR/Value.h" |
70 | #include "llvm/Support/Casting.h" |
71 | #include "llvm/Support/KnownBits.h" |
72 | #include "llvm/Support/raw_ostream.h" |
73 | #include <cassert> |
74 | #include <cstdint> |
75 | #include <iterator> |
76 | #include <string> |
77 | |
78 | using namespace llvm; |
79 | |
80 | static const char LintAbortOnErrorArgName[] = "lint-abort-on-error" ; |
81 | static cl::opt<bool> |
82 | LintAbortOnError(LintAbortOnErrorArgName, cl::init(Val: false), |
83 | cl::desc("In the Lint pass, abort on errors." )); |
84 | |
85 | namespace { |
86 | namespace MemRef { |
87 | static const unsigned Read = 1; |
88 | static const unsigned Write = 2; |
89 | static const unsigned Callee = 4; |
90 | static const unsigned Branchee = 8; |
91 | } // end namespace MemRef |
92 | |
93 | class Lint : public InstVisitor<Lint> { |
94 | friend class InstVisitor<Lint>; |
95 | |
96 | void visitFunction(Function &F); |
97 | |
98 | void visitCallBase(CallBase &CB); |
99 | void visitMemoryReference(Instruction &I, const MemoryLocation &Loc, |
100 | MaybeAlign Alignment, Type *Ty, unsigned Flags); |
101 | |
102 | void visitReturnInst(ReturnInst &I); |
103 | void visitLoadInst(LoadInst &I); |
104 | void visitStoreInst(StoreInst &I); |
105 | void visitXor(BinaryOperator &I); |
106 | void visitSub(BinaryOperator &I); |
107 | void visitLShr(BinaryOperator &I); |
108 | void visitAShr(BinaryOperator &I); |
109 | void visitShl(BinaryOperator &I); |
110 | void visitSDiv(BinaryOperator &I); |
111 | void visitUDiv(BinaryOperator &I); |
112 | void visitSRem(BinaryOperator &I); |
113 | void visitURem(BinaryOperator &I); |
114 | void visitAllocaInst(AllocaInst &I); |
115 | void visitVAArgInst(VAArgInst &I); |
116 | void visitIndirectBrInst(IndirectBrInst &I); |
117 | void visitExtractElementInst(ExtractElementInst &I); |
118 | void visitInsertElementInst(InsertElementInst &I); |
119 | void visitUnreachableInst(UnreachableInst &I); |
120 | |
121 | Value *findValue(Value *V, bool OffsetOk) const; |
122 | Value *findValueImpl(Value *V, bool OffsetOk, |
123 | SmallPtrSetImpl<Value *> &Visited) const; |
124 | |
125 | public: |
126 | Module *Mod; |
127 | const DataLayout *DL; |
128 | AliasAnalysis *AA; |
129 | AssumptionCache *AC; |
130 | DominatorTree *DT; |
131 | TargetLibraryInfo *TLI; |
132 | |
133 | std::string Messages; |
134 | raw_string_ostream MessagesStr; |
135 | |
136 | Lint(Module *Mod, const DataLayout *DL, AliasAnalysis *AA, |
137 | AssumptionCache *AC, DominatorTree *DT, TargetLibraryInfo *TLI) |
138 | : Mod(Mod), DL(DL), AA(AA), AC(AC), DT(DT), TLI(TLI), |
139 | MessagesStr(Messages) {} |
140 | |
141 | void WriteValues(ArrayRef<const Value *> Vs) { |
142 | for (const Value *V : Vs) { |
143 | if (!V) |
144 | continue; |
145 | if (isa<Instruction>(Val: V)) { |
146 | MessagesStr << *V << '\n'; |
147 | } else { |
148 | V->printAsOperand(O&: MessagesStr, PrintType: true, M: Mod); |
149 | MessagesStr << '\n'; |
150 | } |
151 | } |
152 | } |
153 | |
154 | /// A check failed, so printout out the condition and the message. |
155 | /// |
156 | /// This provides a nice place to put a breakpoint if you want to see why |
157 | /// something is not correct. |
158 | void CheckFailed(const Twine &Message) { MessagesStr << Message << '\n'; } |
159 | |
160 | /// A check failed (with values to print). |
161 | /// |
162 | /// This calls the Message-only version so that the above is easier to set |
163 | /// a breakpoint on. |
164 | template <typename T1, typename... Ts> |
165 | void CheckFailed(const Twine &Message, const T1 &V1, const Ts &... Vs) { |
166 | CheckFailed(Message); |
167 | WriteValues(Vs: {V1, Vs...}); |
168 | } |
169 | }; |
170 | } // end anonymous namespace |
171 | |
172 | // Check - We know that cond should be true, if not print an error message. |
173 | #define Check(C, ...) \ |
174 | do { \ |
175 | if (!(C)) { \ |
176 | CheckFailed(__VA_ARGS__); \ |
177 | return; \ |
178 | } \ |
179 | } while (false) |
180 | |
181 | void Lint::visitFunction(Function &F) { |
182 | // This isn't undefined behavior, it's just a little unusual, and it's a |
183 | // fairly common mistake to neglect to name a function. |
184 | Check(F.hasName() || F.hasLocalLinkage(), |
185 | "Unusual: Unnamed function with non-local linkage" , &F); |
186 | |
187 | // TODO: Check for irreducible control flow. |
188 | } |
189 | |
190 | void Lint::visitCallBase(CallBase &I) { |
191 | Value *Callee = I.getCalledOperand(); |
192 | |
193 | visitMemoryReference(I, Loc: MemoryLocation::getAfter(Ptr: Callee), Alignment: std::nullopt, |
194 | Ty: nullptr, Flags: MemRef::Callee); |
195 | |
196 | if (Function *F = dyn_cast<Function>(Val: findValue(V: Callee, |
197 | /*OffsetOk=*/false))) { |
198 | Check(I.getCallingConv() == F->getCallingConv(), |
199 | "Undefined behavior: Caller and callee calling convention differ" , |
200 | &I); |
201 | |
202 | FunctionType *FT = F->getFunctionType(); |
203 | unsigned NumActualArgs = I.arg_size(); |
204 | |
205 | Check(FT->isVarArg() ? FT->getNumParams() <= NumActualArgs |
206 | : FT->getNumParams() == NumActualArgs, |
207 | "Undefined behavior: Call argument count mismatches callee " |
208 | "argument count" , |
209 | &I); |
210 | |
211 | Check(FT->getReturnType() == I.getType(), |
212 | "Undefined behavior: Call return type mismatches " |
213 | "callee return type" , |
214 | &I); |
215 | |
216 | // Check argument types (in case the callee was casted) and attributes. |
217 | // TODO: Verify that caller and callee attributes are compatible. |
218 | Function::arg_iterator PI = F->arg_begin(), PE = F->arg_end(); |
219 | auto AI = I.arg_begin(), AE = I.arg_end(); |
220 | for (; AI != AE; ++AI) { |
221 | Value *Actual = *AI; |
222 | if (PI != PE) { |
223 | Argument *Formal = &*PI++; |
224 | Check(Formal->getType() == Actual->getType(), |
225 | "Undefined behavior: Call argument type mismatches " |
226 | "callee parameter type" , |
227 | &I); |
228 | |
229 | // Check that noalias arguments don't alias other arguments. This is |
230 | // not fully precise because we don't know the sizes of the dereferenced |
231 | // memory regions. |
232 | if (Formal->hasNoAliasAttr() && Actual->getType()->isPointerTy()) { |
233 | AttributeList PAL = I.getAttributes(); |
234 | unsigned ArgNo = 0; |
235 | for (auto *BI = I.arg_begin(); BI != AE; ++BI, ++ArgNo) { |
236 | // Skip ByVal arguments since they will be memcpy'd to the callee's |
237 | // stack so we're not really passing the pointer anyway. |
238 | if (PAL.hasParamAttr(ArgNo, Attribute::ByVal)) |
239 | continue; |
240 | // If both arguments are readonly, they have no dependence. |
241 | if (Formal->onlyReadsMemory() && I.onlyReadsMemory(OpNo: ArgNo)) |
242 | continue; |
243 | // Skip readnone arguments since those are guaranteed not to be |
244 | // dereferenced anyway. |
245 | if (I.doesNotAccessMemory(OpNo: ArgNo)) |
246 | continue; |
247 | if (AI != BI && (*BI)->getType()->isPointerTy()) { |
248 | AliasResult Result = AA->alias(V1: *AI, V2: *BI); |
249 | Check(Result != AliasResult::MustAlias && |
250 | Result != AliasResult::PartialAlias, |
251 | "Unusual: noalias argument aliases another argument" , &I); |
252 | } |
253 | } |
254 | } |
255 | |
256 | // Check that an sret argument points to valid memory. |
257 | if (Formal->hasStructRetAttr() && Actual->getType()->isPointerTy()) { |
258 | Type *Ty = Formal->getParamStructRetType(); |
259 | MemoryLocation Loc( |
260 | Actual, LocationSize::precise(Value: DL->getTypeStoreSize(Ty))); |
261 | visitMemoryReference(I, Loc, Alignment: DL->getABITypeAlign(Ty), Ty, |
262 | Flags: MemRef::Read | MemRef::Write); |
263 | } |
264 | } |
265 | } |
266 | } |
267 | |
268 | if (const auto *CI = dyn_cast<CallInst>(Val: &I)) { |
269 | if (CI->isTailCall()) { |
270 | const AttributeList &PAL = CI->getAttributes(); |
271 | unsigned ArgNo = 0; |
272 | for (Value *Arg : I.args()) { |
273 | // Skip ByVal arguments since they will be memcpy'd to the callee's |
274 | // stack anyway. |
275 | if (PAL.hasParamAttr(ArgNo++, Attribute::ByVal)) |
276 | continue; |
277 | Value *Obj = findValue(V: Arg, /*OffsetOk=*/true); |
278 | Check(!isa<AllocaInst>(Obj), |
279 | "Undefined behavior: Call with \"tail\" keyword references " |
280 | "alloca" , |
281 | &I); |
282 | } |
283 | } |
284 | } |
285 | |
286 | if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Val: &I)) |
287 | switch (II->getIntrinsicID()) { |
288 | default: |
289 | break; |
290 | |
291 | // TODO: Check more intrinsics |
292 | |
293 | case Intrinsic::memcpy: { |
294 | MemCpyInst *MCI = cast<MemCpyInst>(Val: &I); |
295 | visitMemoryReference(I, Loc: MemoryLocation::getForDest(MI: MCI), |
296 | Alignment: MCI->getDestAlign(), Ty: nullptr, Flags: MemRef::Write); |
297 | visitMemoryReference(I, Loc: MemoryLocation::getForSource(MTI: MCI), |
298 | Alignment: MCI->getSourceAlign(), Ty: nullptr, Flags: MemRef::Read); |
299 | |
300 | // Check that the memcpy arguments don't overlap. The AliasAnalysis API |
301 | // isn't expressive enough for what we really want to do. Known partial |
302 | // overlap is not distinguished from the case where nothing is known. |
303 | auto Size = LocationSize::afterPointer(); |
304 | if (const ConstantInt *Len = |
305 | dyn_cast<ConstantInt>(Val: findValue(V: MCI->getLength(), |
306 | /*OffsetOk=*/false))) |
307 | if (Len->getValue().isIntN(N: 32)) |
308 | Size = LocationSize::precise(Value: Len->getValue().getZExtValue()); |
309 | Check(AA->alias(MCI->getSource(), Size, MCI->getDest(), Size) != |
310 | AliasResult::MustAlias, |
311 | "Undefined behavior: memcpy source and destination overlap" , &I); |
312 | break; |
313 | } |
314 | case Intrinsic::memcpy_inline: { |
315 | MemCpyInlineInst *MCII = cast<MemCpyInlineInst>(Val: &I); |
316 | const uint64_t Size = MCII->getLength()->getValue().getLimitedValue(); |
317 | visitMemoryReference(I, Loc: MemoryLocation::getForDest(MI: MCII), |
318 | Alignment: MCII->getDestAlign(), Ty: nullptr, Flags: MemRef::Write); |
319 | visitMemoryReference(I, Loc: MemoryLocation::getForSource(MTI: MCII), |
320 | Alignment: MCII->getSourceAlign(), Ty: nullptr, Flags: MemRef::Read); |
321 | |
322 | // Check that the memcpy arguments don't overlap. The AliasAnalysis API |
323 | // isn't expressive enough for what we really want to do. Known partial |
324 | // overlap is not distinguished from the case where nothing is known. |
325 | const LocationSize LS = LocationSize::precise(Value: Size); |
326 | Check(AA->alias(MCII->getSource(), LS, MCII->getDest(), LS) != |
327 | AliasResult::MustAlias, |
328 | "Undefined behavior: memcpy source and destination overlap" , &I); |
329 | break; |
330 | } |
331 | case Intrinsic::memmove: { |
332 | MemMoveInst *MMI = cast<MemMoveInst>(Val: &I); |
333 | visitMemoryReference(I, Loc: MemoryLocation::getForDest(MI: MMI), |
334 | Alignment: MMI->getDestAlign(), Ty: nullptr, Flags: MemRef::Write); |
335 | visitMemoryReference(I, Loc: MemoryLocation::getForSource(MTI: MMI), |
336 | Alignment: MMI->getSourceAlign(), Ty: nullptr, Flags: MemRef::Read); |
337 | break; |
338 | } |
339 | case Intrinsic::memset: { |
340 | MemSetInst *MSI = cast<MemSetInst>(Val: &I); |
341 | visitMemoryReference(I, Loc: MemoryLocation::getForDest(MI: MSI), |
342 | Alignment: MSI->getDestAlign(), Ty: nullptr, Flags: MemRef::Write); |
343 | break; |
344 | } |
345 | case Intrinsic::memset_inline: { |
346 | MemSetInlineInst *MSII = cast<MemSetInlineInst>(Val: &I); |
347 | visitMemoryReference(I, Loc: MemoryLocation::getForDest(MI: MSII), |
348 | Alignment: MSII->getDestAlign(), Ty: nullptr, Flags: MemRef::Write); |
349 | break; |
350 | } |
351 | |
352 | case Intrinsic::vastart: |
353 | // vastart in non-varargs function is rejected by the verifier |
354 | visitMemoryReference(I, Loc: MemoryLocation::getForArgument(Call: &I, ArgIdx: 0, TLI), |
355 | Alignment: std::nullopt, Ty: nullptr, Flags: MemRef::Read | MemRef::Write); |
356 | break; |
357 | case Intrinsic::vacopy: |
358 | visitMemoryReference(I, Loc: MemoryLocation::getForArgument(Call: &I, ArgIdx: 0, TLI), |
359 | Alignment: std::nullopt, Ty: nullptr, Flags: MemRef::Write); |
360 | visitMemoryReference(I, Loc: MemoryLocation::getForArgument(Call: &I, ArgIdx: 1, TLI), |
361 | Alignment: std::nullopt, Ty: nullptr, Flags: MemRef::Read); |
362 | break; |
363 | case Intrinsic::vaend: |
364 | visitMemoryReference(I, Loc: MemoryLocation::getForArgument(Call: &I, ArgIdx: 0, TLI), |
365 | Alignment: std::nullopt, Ty: nullptr, Flags: MemRef::Read | MemRef::Write); |
366 | break; |
367 | |
368 | case Intrinsic::stackrestore: |
369 | // Stackrestore doesn't read or write memory, but it sets the |
370 | // stack pointer, which the compiler may read from or write to |
371 | // at any time, so check it for both readability and writeability. |
372 | visitMemoryReference(I, Loc: MemoryLocation::getForArgument(Call: &I, ArgIdx: 0, TLI), |
373 | Alignment: std::nullopt, Ty: nullptr, Flags: MemRef::Read | MemRef::Write); |
374 | break; |
375 | case Intrinsic::get_active_lane_mask: |
376 | if (auto *TripCount = dyn_cast<ConstantInt>(Val: I.getArgOperand(i: 1))) |
377 | Check(!TripCount->isZero(), |
378 | "get_active_lane_mask: operand #2 " |
379 | "must be greater than 0" , |
380 | &I); |
381 | break; |
382 | } |
383 | } |
384 | |
385 | void Lint::visitReturnInst(ReturnInst &I) { |
386 | Function *F = I.getParent()->getParent(); |
387 | Check(!F->doesNotReturn(), |
388 | "Unusual: Return statement in function with noreturn attribute" , &I); |
389 | |
390 | if (Value *V = I.getReturnValue()) { |
391 | Value *Obj = findValue(V, /*OffsetOk=*/true); |
392 | Check(!isa<AllocaInst>(Obj), "Unusual: Returning alloca value" , &I); |
393 | } |
394 | } |
395 | |
396 | // TODO: Check that the reference is in bounds. |
397 | // TODO: Check readnone/readonly function attributes. |
398 | void Lint::visitMemoryReference(Instruction &I, const MemoryLocation &Loc, |
399 | MaybeAlign Align, Type *Ty, unsigned Flags) { |
400 | // If no memory is being referenced, it doesn't matter if the pointer |
401 | // is valid. |
402 | if (Loc.Size.isZero()) |
403 | return; |
404 | |
405 | Value *Ptr = const_cast<Value *>(Loc.Ptr); |
406 | Value *UnderlyingObject = findValue(V: Ptr, /*OffsetOk=*/true); |
407 | Check(!isa<ConstantPointerNull>(UnderlyingObject), |
408 | "Undefined behavior: Null pointer dereference" , &I); |
409 | Check(!isa<UndefValue>(UnderlyingObject), |
410 | "Undefined behavior: Undef pointer dereference" , &I); |
411 | Check(!isa<ConstantInt>(UnderlyingObject) || |
412 | !cast<ConstantInt>(UnderlyingObject)->isMinusOne(), |
413 | "Unusual: All-ones pointer dereference" , &I); |
414 | Check(!isa<ConstantInt>(UnderlyingObject) || |
415 | !cast<ConstantInt>(UnderlyingObject)->isOne(), |
416 | "Unusual: Address one pointer dereference" , &I); |
417 | |
418 | if (Flags & MemRef::Write) { |
419 | if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(Val: UnderlyingObject)) |
420 | Check(!GV->isConstant(), "Undefined behavior: Write to read-only memory" , |
421 | &I); |
422 | Check(!isa<Function>(UnderlyingObject) && |
423 | !isa<BlockAddress>(UnderlyingObject), |
424 | "Undefined behavior: Write to text section" , &I); |
425 | } |
426 | if (Flags & MemRef::Read) { |
427 | Check(!isa<Function>(UnderlyingObject), "Unusual: Load from function body" , |
428 | &I); |
429 | Check(!isa<BlockAddress>(UnderlyingObject), |
430 | "Undefined behavior: Load from block address" , &I); |
431 | } |
432 | if (Flags & MemRef::Callee) { |
433 | Check(!isa<BlockAddress>(UnderlyingObject), |
434 | "Undefined behavior: Call to block address" , &I); |
435 | } |
436 | if (Flags & MemRef::Branchee) { |
437 | Check(!isa<Constant>(UnderlyingObject) || |
438 | isa<BlockAddress>(UnderlyingObject), |
439 | "Undefined behavior: Branch to non-blockaddress" , &I); |
440 | } |
441 | |
442 | // Check for buffer overflows and misalignment. |
443 | // Only handles memory references that read/write something simple like an |
444 | // alloca instruction or a global variable. |
445 | int64_t Offset = 0; |
446 | if (Value *Base = GetPointerBaseWithConstantOffset(Ptr, Offset, DL: *DL)) { |
447 | // OK, so the access is to a constant offset from Ptr. Check that Ptr is |
448 | // something we can handle and if so extract the size of this base object |
449 | // along with its alignment. |
450 | uint64_t BaseSize = MemoryLocation::UnknownSize; |
451 | MaybeAlign BaseAlign; |
452 | |
453 | if (AllocaInst *AI = dyn_cast<AllocaInst>(Val: Base)) { |
454 | Type *ATy = AI->getAllocatedType(); |
455 | if (!AI->isArrayAllocation() && ATy->isSized()) |
456 | BaseSize = DL->getTypeAllocSize(Ty: ATy); |
457 | BaseAlign = AI->getAlign(); |
458 | } else if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Val: Base)) { |
459 | // If the global may be defined differently in another compilation unit |
460 | // then don't warn about funky memory accesses. |
461 | if (GV->hasDefinitiveInitializer()) { |
462 | Type *GTy = GV->getValueType(); |
463 | if (GTy->isSized()) |
464 | BaseSize = DL->getTypeAllocSize(Ty: GTy); |
465 | BaseAlign = GV->getAlign(); |
466 | if (!BaseAlign && GTy->isSized()) |
467 | BaseAlign = DL->getABITypeAlign(Ty: GTy); |
468 | } |
469 | } |
470 | |
471 | // Accesses from before the start or after the end of the object are not |
472 | // defined. |
473 | Check(!Loc.Size.hasValue() || BaseSize == MemoryLocation::UnknownSize || |
474 | (Offset >= 0 && Offset + Loc.Size.getValue() <= BaseSize), |
475 | "Undefined behavior: Buffer overflow" , &I); |
476 | |
477 | // Accesses that say that the memory is more aligned than it is are not |
478 | // defined. |
479 | if (!Align && Ty && Ty->isSized()) |
480 | Align = DL->getABITypeAlign(Ty); |
481 | if (BaseAlign && Align) |
482 | Check(*Align <= commonAlignment(*BaseAlign, Offset), |
483 | "Undefined behavior: Memory reference address is misaligned" , &I); |
484 | } |
485 | } |
486 | |
487 | void Lint::visitLoadInst(LoadInst &I) { |
488 | visitMemoryReference(I, Loc: MemoryLocation::get(LI: &I), Align: I.getAlign(), Ty: I.getType(), |
489 | Flags: MemRef::Read); |
490 | } |
491 | |
492 | void Lint::visitStoreInst(StoreInst &I) { |
493 | visitMemoryReference(I, Loc: MemoryLocation::get(SI: &I), Align: I.getAlign(), |
494 | Ty: I.getOperand(i_nocapture: 0)->getType(), Flags: MemRef::Write); |
495 | } |
496 | |
497 | void Lint::visitXor(BinaryOperator &I) { |
498 | Check(!isa<UndefValue>(I.getOperand(0)) || !isa<UndefValue>(I.getOperand(1)), |
499 | "Undefined result: xor(undef, undef)" , &I); |
500 | } |
501 | |
502 | void Lint::visitSub(BinaryOperator &I) { |
503 | Check(!isa<UndefValue>(I.getOperand(0)) || !isa<UndefValue>(I.getOperand(1)), |
504 | "Undefined result: sub(undef, undef)" , &I); |
505 | } |
506 | |
507 | void Lint::visitLShr(BinaryOperator &I) { |
508 | if (ConstantInt *CI = dyn_cast<ConstantInt>(Val: findValue(V: I.getOperand(i_nocapture: 1), |
509 | /*OffsetOk=*/false))) |
510 | Check(CI->getValue().ult(cast<IntegerType>(I.getType())->getBitWidth()), |
511 | "Undefined result: Shift count out of range" , &I); |
512 | } |
513 | |
514 | void Lint::visitAShr(BinaryOperator &I) { |
515 | if (ConstantInt *CI = |
516 | dyn_cast<ConstantInt>(Val: findValue(V: I.getOperand(i_nocapture: 1), /*OffsetOk=*/false))) |
517 | Check(CI->getValue().ult(cast<IntegerType>(I.getType())->getBitWidth()), |
518 | "Undefined result: Shift count out of range" , &I); |
519 | } |
520 | |
521 | void Lint::visitShl(BinaryOperator &I) { |
522 | if (ConstantInt *CI = |
523 | dyn_cast<ConstantInt>(Val: findValue(V: I.getOperand(i_nocapture: 1), /*OffsetOk=*/false))) |
524 | Check(CI->getValue().ult(cast<IntegerType>(I.getType())->getBitWidth()), |
525 | "Undefined result: Shift count out of range" , &I); |
526 | } |
527 | |
528 | static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, |
529 | AssumptionCache *AC) { |
530 | // Assume undef could be zero. |
531 | if (isa<UndefValue>(Val: V)) |
532 | return true; |
533 | |
534 | VectorType *VecTy = dyn_cast<VectorType>(Val: V->getType()); |
535 | if (!VecTy) { |
536 | KnownBits Known = |
537 | computeKnownBits(V, DL, Depth: 0, AC, CxtI: dyn_cast<Instruction>(Val: V), DT); |
538 | return Known.isZero(); |
539 | } |
540 | |
541 | // Per-component check doesn't work with zeroinitializer |
542 | Constant *C = dyn_cast<Constant>(Val: V); |
543 | if (!C) |
544 | return false; |
545 | |
546 | if (C->isZeroValue()) |
547 | return true; |
548 | |
549 | // For a vector, KnownZero will only be true if all values are zero, so check |
550 | // this per component |
551 | for (unsigned I = 0, N = cast<FixedVectorType>(Val: VecTy)->getNumElements(); |
552 | I != N; ++I) { |
553 | Constant *Elem = C->getAggregateElement(Elt: I); |
554 | if (isa<UndefValue>(Val: Elem)) |
555 | return true; |
556 | |
557 | KnownBits Known = computeKnownBits(V: Elem, DL); |
558 | if (Known.isZero()) |
559 | return true; |
560 | } |
561 | |
562 | return false; |
563 | } |
564 | |
565 | void Lint::visitSDiv(BinaryOperator &I) { |
566 | Check(!isZero(I.getOperand(1), I.getModule()->getDataLayout(), DT, AC), |
567 | "Undefined behavior: Division by zero" , &I); |
568 | } |
569 | |
570 | void Lint::visitUDiv(BinaryOperator &I) { |
571 | Check(!isZero(I.getOperand(1), I.getModule()->getDataLayout(), DT, AC), |
572 | "Undefined behavior: Division by zero" , &I); |
573 | } |
574 | |
575 | void Lint::visitSRem(BinaryOperator &I) { |
576 | Check(!isZero(I.getOperand(1), I.getModule()->getDataLayout(), DT, AC), |
577 | "Undefined behavior: Division by zero" , &I); |
578 | } |
579 | |
580 | void Lint::visitURem(BinaryOperator &I) { |
581 | Check(!isZero(I.getOperand(1), I.getModule()->getDataLayout(), DT, AC), |
582 | "Undefined behavior: Division by zero" , &I); |
583 | } |
584 | |
585 | void Lint::visitAllocaInst(AllocaInst &I) { |
586 | if (isa<ConstantInt>(Val: I.getArraySize())) |
587 | // This isn't undefined behavior, it's just an obvious pessimization. |
588 | Check(&I.getParent()->getParent()->getEntryBlock() == I.getParent(), |
589 | "Pessimization: Static alloca outside of entry block" , &I); |
590 | |
591 | // TODO: Check for an unusual size (MSB set?) |
592 | } |
593 | |
594 | void Lint::visitVAArgInst(VAArgInst &I) { |
595 | visitMemoryReference(I, Loc: MemoryLocation::get(VI: &I), Align: std::nullopt, Ty: nullptr, |
596 | Flags: MemRef::Read | MemRef::Write); |
597 | } |
598 | |
599 | void Lint::visitIndirectBrInst(IndirectBrInst &I) { |
600 | visitMemoryReference(I, Loc: MemoryLocation::getAfter(Ptr: I.getAddress()), |
601 | Align: std::nullopt, Ty: nullptr, Flags: MemRef::Branchee); |
602 | |
603 | Check(I.getNumDestinations() != 0, |
604 | "Undefined behavior: indirectbr with no destinations" , &I); |
605 | } |
606 | |
607 | void Lint::(ExtractElementInst &I) { |
608 | if (ConstantInt *CI = dyn_cast<ConstantInt>(Val: findValue(V: I.getIndexOperand(), |
609 | /*OffsetOk=*/false))) |
610 | Check( |
611 | CI->getValue().ult( |
612 | cast<FixedVectorType>(I.getVectorOperandType())->getNumElements()), |
613 | "Undefined result: extractelement index out of range" , &I); |
614 | } |
615 | |
616 | void Lint::visitInsertElementInst(InsertElementInst &I) { |
617 | if (ConstantInt *CI = dyn_cast<ConstantInt>(Val: findValue(V: I.getOperand(i_nocapture: 2), |
618 | /*OffsetOk=*/false))) |
619 | Check(CI->getValue().ult( |
620 | cast<FixedVectorType>(I.getType())->getNumElements()), |
621 | "Undefined result: insertelement index out of range" , &I); |
622 | } |
623 | |
624 | void Lint::visitUnreachableInst(UnreachableInst &I) { |
625 | // This isn't undefined behavior, it's merely suspicious. |
626 | Check(&I == &I.getParent()->front() || |
627 | std::prev(I.getIterator())->mayHaveSideEffects(), |
628 | "Unusual: unreachable immediately preceded by instruction without " |
629 | "side effects" , |
630 | &I); |
631 | } |
632 | |
633 | /// findValue - Look through bitcasts and simple memory reference patterns |
634 | /// to identify an equivalent, but more informative, value. If OffsetOk |
635 | /// is true, look through getelementptrs with non-zero offsets too. |
636 | /// |
637 | /// Most analysis passes don't require this logic, because instcombine |
638 | /// will simplify most of these kinds of things away. But it's a goal of |
639 | /// this Lint pass to be useful even on non-optimized IR. |
640 | Value *Lint::findValue(Value *V, bool OffsetOk) const { |
641 | SmallPtrSet<Value *, 4> Visited; |
642 | return findValueImpl(V, OffsetOk, Visited); |
643 | } |
644 | |
645 | /// findValueImpl - Implementation helper for findValue. |
646 | Value *Lint::findValueImpl(Value *V, bool OffsetOk, |
647 | SmallPtrSetImpl<Value *> &Visited) const { |
648 | // Detect self-referential values. |
649 | if (!Visited.insert(Ptr: V).second) |
650 | return UndefValue::get(T: V->getType()); |
651 | |
652 | // TODO: Look through sext or zext cast, when the result is known to |
653 | // be interpreted as signed or unsigned, respectively. |
654 | // TODO: Look through eliminable cast pairs. |
655 | // TODO: Look through calls with unique return values. |
656 | // TODO: Look through vector insert/extract/shuffle. |
657 | V = OffsetOk ? getUnderlyingObject(V) : V->stripPointerCasts(); |
658 | if (LoadInst *L = dyn_cast<LoadInst>(Val: V)) { |
659 | BasicBlock::iterator BBI = L->getIterator(); |
660 | BasicBlock *BB = L->getParent(); |
661 | SmallPtrSet<BasicBlock *, 4> VisitedBlocks; |
662 | BatchAAResults BatchAA(*AA); |
663 | for (;;) { |
664 | if (!VisitedBlocks.insert(Ptr: BB).second) |
665 | break; |
666 | if (Value *U = |
667 | FindAvailableLoadedValue(Load: L, ScanBB: BB, ScanFrom&: BBI, MaxInstsToScan: DefMaxInstsToScan, AA: &BatchAA)) |
668 | return findValueImpl(V: U, OffsetOk, Visited); |
669 | if (BBI != BB->begin()) |
670 | break; |
671 | BB = BB->getUniquePredecessor(); |
672 | if (!BB) |
673 | break; |
674 | BBI = BB->end(); |
675 | } |
676 | } else if (PHINode *PN = dyn_cast<PHINode>(Val: V)) { |
677 | if (Value *W = PN->hasConstantValue()) |
678 | return findValueImpl(V: W, OffsetOk, Visited); |
679 | } else if (CastInst *CI = dyn_cast<CastInst>(Val: V)) { |
680 | if (CI->isNoopCast(DL: *DL)) |
681 | return findValueImpl(V: CI->getOperand(i_nocapture: 0), OffsetOk, Visited); |
682 | } else if (ExtractValueInst *Ex = dyn_cast<ExtractValueInst>(Val: V)) { |
683 | if (Value *W = |
684 | FindInsertedValue(V: Ex->getAggregateOperand(), idx_range: Ex->getIndices())) |
685 | if (W != V) |
686 | return findValueImpl(V: W, OffsetOk, Visited); |
687 | } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Val: V)) { |
688 | // Same as above, but for ConstantExpr instead of Instruction. |
689 | if (Instruction::isCast(Opcode: CE->getOpcode())) { |
690 | if (CastInst::isNoopCast(Opcode: Instruction::CastOps(CE->getOpcode()), |
691 | SrcTy: CE->getOperand(i_nocapture: 0)->getType(), DstTy: CE->getType(), |
692 | DL: *DL)) |
693 | return findValueImpl(V: CE->getOperand(i_nocapture: 0), OffsetOk, Visited); |
694 | } |
695 | } |
696 | |
697 | // As a last resort, try SimplifyInstruction or constant folding. |
698 | if (Instruction *Inst = dyn_cast<Instruction>(Val: V)) { |
699 | if (Value *W = simplifyInstruction(I: Inst, Q: {*DL, TLI, DT, AC})) |
700 | return findValueImpl(V: W, OffsetOk, Visited); |
701 | } else if (auto *C = dyn_cast<Constant>(Val: V)) { |
702 | Value *W = ConstantFoldConstant(C, DL: *DL, TLI); |
703 | if (W != V) |
704 | return findValueImpl(V: W, OffsetOk, Visited); |
705 | } |
706 | |
707 | return V; |
708 | } |
709 | |
710 | PreservedAnalyses LintPass::run(Function &F, FunctionAnalysisManager &AM) { |
711 | auto *Mod = F.getParent(); |
712 | auto *DL = &F.getParent()->getDataLayout(); |
713 | auto *AA = &AM.getResult<AAManager>(IR&: F); |
714 | auto *AC = &AM.getResult<AssumptionAnalysis>(IR&: F); |
715 | auto *DT = &AM.getResult<DominatorTreeAnalysis>(IR&: F); |
716 | auto *TLI = &AM.getResult<TargetLibraryAnalysis>(IR&: F); |
717 | Lint L(Mod, DL, AA, AC, DT, TLI); |
718 | L.visit(F); |
719 | dbgs() << L.MessagesStr.str(); |
720 | if (LintAbortOnError && !L.MessagesStr.str().empty()) |
721 | report_fatal_error(reason: Twine("Linter found errors, aborting. (enabled by --" ) + |
722 | LintAbortOnErrorArgName + ")" , |
723 | gen_crash_diag: false); |
724 | return PreservedAnalyses::all(); |
725 | } |
726 | |
727 | //===----------------------------------------------------------------------===// |
728 | // Implement the public interfaces to this file... |
729 | //===----------------------------------------------------------------------===// |
730 | |
731 | /// lintFunction - Check a function for errors, printing messages on stderr. |
732 | /// |
733 | void llvm::lintFunction(const Function &f) { |
734 | Function &F = const_cast<Function &>(f); |
735 | assert(!F.isDeclaration() && "Cannot lint external functions" ); |
736 | |
737 | FunctionAnalysisManager FAM; |
738 | FAM.registerPass(PassBuilder: [&] { return TargetLibraryAnalysis(); }); |
739 | FAM.registerPass(PassBuilder: [&] { return DominatorTreeAnalysis(); }); |
740 | FAM.registerPass(PassBuilder: [&] { return AssumptionAnalysis(); }); |
741 | FAM.registerPass(PassBuilder: [&] { |
742 | AAManager AA; |
743 | AA.registerFunctionAnalysis<BasicAA>(); |
744 | AA.registerFunctionAnalysis<ScopedNoAliasAA>(); |
745 | AA.registerFunctionAnalysis<TypeBasedAA>(); |
746 | return AA; |
747 | }); |
748 | LintPass().run(F, AM&: FAM); |
749 | } |
750 | |
751 | /// lintModule - Check a module for errors, printing messages on stderr. |
752 | /// |
753 | void llvm::lintModule(const Module &M) { |
754 | for (const Function &F : M) { |
755 | if (!F.isDeclaration()) |
756 | lintFunction(f: F); |
757 | } |
758 | } |
759 | |