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