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