LLVM 18.0.0git
Lint.cpp
Go to the documentation of this file.
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"
40#include "llvm/ADT/Twine.h"
46#include "llvm/Analysis/Loads.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"
58#include "llvm/IR/Dominators.h"
59#include "llvm/IR/Function.h"
61#include "llvm/IR/InstVisitor.h"
62#include "llvm/IR/InstrTypes.h"
63#include "llvm/IR/Instruction.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"
73#include <cassert>
74#include <cstdint>
75#include <iterator>
76#include <string>
77
78using namespace llvm;
79
80namespace {
81namespace MemRef {
82static const unsigned Read = 1;
83static const unsigned Write = 2;
84static const unsigned Callee = 4;
85static const unsigned Branchee = 8;
86} // end namespace MemRef
87
88class Lint : public InstVisitor<Lint> {
89 friend class InstVisitor<Lint>;
90
92
93 void visitCallBase(CallBase &CB);
94 void visitMemoryReference(Instruction &I, const MemoryLocation &Loc,
95 MaybeAlign Alignment, Type *Ty, unsigned Flags);
96
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);
115
116 Value *findValue(Value *V, bool OffsetOk) const;
117 Value *findValueImpl(Value *V, bool OffsetOk,
118 SmallPtrSetImpl<Value *> &Visited) const;
119
120public:
121 Module *Mod;
122 const DataLayout *DL;
123 AliasAnalysis *AA;
124 AssumptionCache *AC;
125 DominatorTree *DT;
127
128 std::string Messages;
129 raw_string_ostream MessagesStr;
130
131 Lint(Module *Mod, const DataLayout *DL, AliasAnalysis *AA,
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>(V)) {
141 MessagesStr << *V << '\n';
142 } else {
143 V->printAsOperand(MessagesStr, true, 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({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
176void 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
185void Lint::visitCallBase(CallBase &I) {
186 Value *Callee = I.getCalledOperand();
187
188 visitMemoryReference(I, MemoryLocation::getAfter(Callee), std::nullopt,
189 nullptr, MemRef::Callee);
190
191 if (Function *F = dyn_cast<Function>(findValue(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(ArgNo))
237 continue;
238 // Skip readnone arguments since those are guaranteed not to be
239 // dereferenced anyway.
240 if (I.doesNotAccessMemory(ArgNo))
241 continue;
242 if (AI != BI && (*BI)->getType()->isPointerTy()) {
243 AliasResult Result = AA->alias(*AI, *BI);
244 Check(Result != AliasResult::MustAlias &&
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(DL->getTypeStoreSize(Ty)));
256 visitMemoryReference(I, Loc, DL->getABITypeAlign(Ty), Ty,
257 MemRef::Read | MemRef::Write);
258 }
259 }
260 }
261 }
262
263 if (const auto *CI = dyn_cast<CallInst>(&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(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>(&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>(&I);
290 visitMemoryReference(I, MemoryLocation::getForDest(MCI),
291 MCI->getDestAlign(), nullptr, MemRef::Write);
292 visitMemoryReference(I, MemoryLocation::getForSource(MCI),
293 MCI->getSourceAlign(), nullptr, 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.
299 if (const ConstantInt *Len =
300 dyn_cast<ConstantInt>(findValue(MCI->getLength(),
301 /*OffsetOk=*/false)))
302 if (Len->getValue().isIntN(32))
303 Size = LocationSize::precise(Len->getValue().getZExtValue());
304 Check(AA->alias(MCI->getSource(), Size, MCI->getDest(), Size) !=
306 "Undefined behavior: memcpy source and destination overlap", &I);
307 break;
308 }
309 case Intrinsic::memcpy_inline: {
310 MemCpyInlineInst *MCII = cast<MemCpyInlineInst>(&I);
311 const uint64_t Size = MCII->getLength()->getValue().getLimitedValue();
312 visitMemoryReference(I, MemoryLocation::getForDest(MCII),
313 MCII->getDestAlign(), nullptr, MemRef::Write);
314 visitMemoryReference(I, MemoryLocation::getForSource(MCII),
315 MCII->getSourceAlign(), nullptr, 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.
321 Check(AA->alias(MCII->getSource(), LS, MCII->getDest(), LS) !=
323 "Undefined behavior: memcpy source and destination overlap", &I);
324 break;
325 }
326 case Intrinsic::memmove: {
327 MemMoveInst *MMI = cast<MemMoveInst>(&I);
328 visitMemoryReference(I, MemoryLocation::getForDest(MMI),
329 MMI->getDestAlign(), nullptr, MemRef::Write);
330 visitMemoryReference(I, MemoryLocation::getForSource(MMI),
331 MMI->getSourceAlign(), nullptr, MemRef::Read);
332 break;
333 }
334 case Intrinsic::memset: {
335 MemSetInst *MSI = cast<MemSetInst>(&I);
336 visitMemoryReference(I, MemoryLocation::getForDest(MSI),
337 MSI->getDestAlign(), nullptr, MemRef::Write);
338 break;
339 }
340 case Intrinsic::memset_inline: {
341 MemSetInlineInst *MSII = cast<MemSetInlineInst>(&I);
342 visitMemoryReference(I, MemoryLocation::getForDest(MSII),
343 MSII->getDestAlign(), nullptr, 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, MemoryLocation::getForArgument(&I, 0, TLI),
353 std::nullopt, nullptr, MemRef::Read | MemRef::Write);
354 break;
355 case Intrinsic::vacopy:
356 visitMemoryReference(I, MemoryLocation::getForArgument(&I, 0, TLI),
357 std::nullopt, nullptr, MemRef::Write);
358 visitMemoryReference(I, MemoryLocation::getForArgument(&I, 1, TLI),
359 std::nullopt, nullptr, MemRef::Read);
360 break;
361 case Intrinsic::vaend:
362 visitMemoryReference(I, MemoryLocation::getForArgument(&I, 0, TLI),
363 std::nullopt, nullptr, 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, MemoryLocation::getForArgument(&I, 0, TLI),
371 std::nullopt, nullptr, MemRef::Read | MemRef::Write);
372 break;
373 case Intrinsic::get_active_lane_mask:
374 if (auto *TripCount = dyn_cast<ConstantInt>(I.getArgOperand(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
383void 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.
396void 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(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>(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;
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.
449 MaybeAlign BaseAlign;
450
451 if (AllocaInst *AI = dyn_cast<AllocaInst>(Base)) {
452 Type *ATy = AI->getAllocatedType();
453 if (!AI->isArrayAllocation() && ATy->isSized())
454 BaseSize = DL->getTypeAllocSize(ATy);
455 BaseAlign = AI->getAlign();
456 } else if (GlobalVariable *GV = dyn_cast<GlobalVariable>(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(GTy);
463 BaseAlign = GV->getAlign();
464 if (!BaseAlign && GTy->isSized())
465 BaseAlign = DL->getABITypeAlign(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
485void Lint::visitLoadInst(LoadInst &I) {
486 visitMemoryReference(I, MemoryLocation::get(&I), I.getAlign(), I.getType(),
487 MemRef::Read);
488}
489
490void Lint::visitStoreInst(StoreInst &I) {
491 visitMemoryReference(I, MemoryLocation::get(&I), I.getAlign(),
492 I.getOperand(0)->getType(), MemRef::Write);
493}
494
495void 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
500void 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
505void Lint::visitLShr(BinaryOperator &I) {
506 if (ConstantInt *CI = dyn_cast<ConstantInt>(findValue(I.getOperand(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
512void Lint::visitAShr(BinaryOperator &I) {
513 if (ConstantInt *CI =
514 dyn_cast<ConstantInt>(findValue(I.getOperand(1), /*OffsetOk=*/false)))
515 Check(CI->getValue().ult(cast<IntegerType>(I.getType())->getBitWidth()),
516 "Undefined result: Shift count out of range", &I);
517}
518
519void Lint::visitShl(BinaryOperator &I) {
520 if (ConstantInt *CI =
521 dyn_cast<ConstantInt>(findValue(I.getOperand(1), /*OffsetOk=*/false)))
522 Check(CI->getValue().ult(cast<IntegerType>(I.getType())->getBitWidth()),
523 "Undefined result: Shift count out of range", &I);
524}
525
526static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT,
527 AssumptionCache *AC) {
528 // Assume undef could be zero.
529 if (isa<UndefValue>(V))
530 return true;
531
532 VectorType *VecTy = dyn_cast<VectorType>(V->getType());
533 if (!VecTy) {
534 KnownBits Known =
535 computeKnownBits(V, DL, 0, AC, dyn_cast<Instruction>(V), DT);
536 return Known.isZero();
537 }
538
539 // Per-component check doesn't work with zeroinitializer
540 Constant *C = dyn_cast<Constant>(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>(VecTy)->getNumElements();
550 I != N; ++I) {
551 Constant *Elem = C->getAggregateElement(I);
552 if (isa<UndefValue>(Elem))
553 return true;
554
555 KnownBits Known = computeKnownBits(Elem, DL);
556 if (Known.isZero())
557 return true;
558 }
559
560 return false;
561}
562
563void Lint::visitSDiv(BinaryOperator &I) {
564 Check(!isZero(I.getOperand(1), I.getModule()->getDataLayout(), DT, AC),
565 "Undefined behavior: Division by zero", &I);
566}
567
568void Lint::visitUDiv(BinaryOperator &I) {
569 Check(!isZero(I.getOperand(1), I.getModule()->getDataLayout(), DT, AC),
570 "Undefined behavior: Division by zero", &I);
571}
572
573void Lint::visitSRem(BinaryOperator &I) {
574 Check(!isZero(I.getOperand(1), I.getModule()->getDataLayout(), DT, AC),
575 "Undefined behavior: Division by zero", &I);
576}
577
578void Lint::visitURem(BinaryOperator &I) {
579 Check(!isZero(I.getOperand(1), I.getModule()->getDataLayout(), DT, AC),
580 "Undefined behavior: Division by zero", &I);
581}
582
583void Lint::visitAllocaInst(AllocaInst &I) {
584 if (isa<ConstantInt>(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
592void Lint::visitVAArgInst(VAArgInst &I) {
593 visitMemoryReference(I, MemoryLocation::get(&I), std::nullopt, nullptr,
594 MemRef::Read | MemRef::Write);
595}
596
597void Lint::visitIndirectBrInst(IndirectBrInst &I) {
598 visitMemoryReference(I, MemoryLocation::getAfter(I.getAddress()),
599 std::nullopt, nullptr, MemRef::Branchee);
600
601 Check(I.getNumDestinations() != 0,
602 "Undefined behavior: indirectbr with no destinations", &I);
603}
604
605void Lint::visitExtractElementInst(ExtractElementInst &I) {
606 if (ConstantInt *CI = dyn_cast<ConstantInt>(findValue(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
614void Lint::visitInsertElementInst(InsertElementInst &I) {
615 if (ConstantInt *CI = dyn_cast<ConstantInt>(findValue(I.getOperand(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
622void 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.
638Value *Lint::findValue(Value *V, bool OffsetOk) const {
640 return findValueImpl(V, OffsetOk, Visited);
641}
642
643/// findValueImpl - Implementation helper for findValue.
644Value *Lint::findValueImpl(Value *V, bool OffsetOk,
645 SmallPtrSetImpl<Value *> &Visited) const {
646 // Detect self-referential values.
647 if (!Visited.insert(V).second)
648 return UndefValue::get(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>(V)) {
657 BasicBlock::iterator BBI = L->getIterator();
658 BasicBlock *BB = L->getParent();
659 SmallPtrSet<BasicBlock *, 4> VisitedBlocks;
660 for (;;) {
661 if (!VisitedBlocks.insert(BB).second)
662 break;
663 if (Value *U =
665 return findValueImpl(U, OffsetOk, Visited);
666 if (BBI != BB->begin())
667 break;
668 BB = BB->getUniquePredecessor();
669 if (!BB)
670 break;
671 BBI = BB->end();
672 }
673 } else if (PHINode *PN = dyn_cast<PHINode>(V)) {
674 if (Value *W = PN->hasConstantValue())
675 return findValueImpl(W, OffsetOk, Visited);
676 } else if (CastInst *CI = dyn_cast<CastInst>(V)) {
677 if (CI->isNoopCast(*DL))
678 return findValueImpl(CI->getOperand(0), OffsetOk, Visited);
679 } else if (ExtractValueInst *Ex = dyn_cast<ExtractValueInst>(V)) {
680 if (Value *W =
681 FindInsertedValue(Ex->getAggregateOperand(), Ex->getIndices()))
682 if (W != V)
683 return findValueImpl(W, OffsetOk, Visited);
684 } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
685 // Same as above, but for ConstantExpr instead of Instruction.
686 if (Instruction::isCast(CE->getOpcode())) {
688 CE->getOperand(0)->getType(), CE->getType(),
689 *DL))
690 return findValueImpl(CE->getOperand(0), OffsetOk, Visited);
691 }
692 }
693
694 // As a last resort, try SimplifyInstruction or constant folding.
695 if (Instruction *Inst = dyn_cast<Instruction>(V)) {
696 if (Value *W = simplifyInstruction(Inst, {*DL, TLI, DT, AC}))
697 return findValueImpl(W, OffsetOk, Visited);
698 } else if (auto *C = dyn_cast<Constant>(V)) {
699 Value *W = ConstantFoldConstant(C, *DL, TLI);
700 if (W != V)
701 return findValueImpl(W, OffsetOk, Visited);
702 }
703
704 return V;
705}
706
708 auto *Mod = F.getParent();
709 auto *DL = &F.getParent()->getDataLayout();
710 auto *AA = &AM.getResult<AAManager>(F);
711 auto *AC = &AM.getResult<AssumptionAnalysis>(F);
712 auto *DT = &AM.getResult<DominatorTreeAnalysis>(F);
713 auto *TLI = &AM.getResult<TargetLibraryAnalysis>(F);
714 Lint L(Mod, DL, AA, AC, DT, TLI);
715 L.visit(F);
716 dbgs() << L.MessagesStr.str();
717 return PreservedAnalyses::all();
718}
719
720//===----------------------------------------------------------------------===//
721// Implement the public interfaces to this file...
722//===----------------------------------------------------------------------===//
723
724/// lintFunction - Check a function for errors, printing messages on stderr.
725///
727 Function &F = const_cast<Function &>(f);
728 assert(!F.isDeclaration() && "Cannot lint external functions");
729
731 FAM.registerPass([&] { return TargetLibraryAnalysis(); });
732 FAM.registerPass([&] { return DominatorTreeAnalysis(); });
733 FAM.registerPass([&] { return AssumptionAnalysis(); });
734 FAM.registerPass([&] {
735 AAManager AA;
739 return AA;
740 });
741 LintPass().run(F, FAM);
742}
743
744/// lintModule - Check a module for errors, printing messages on stderr.
745///
746void llvm::lintModule(const Module &M) {
747 for (const Function &F : M) {
748 if (!F.isDeclaration())
750 }
751}
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
This file implements a class to represent arbitrary precision integral constant values and operations...
This is the interface for LLVM's primary stateless and local alias analysis.
This file contains the declarations for the subclasses of Constant, which represent the different fla...
uint64_t Size
#define Check(C,...)
Definition: Lint.cpp:168
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
Definition: Lint.cpp:526
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
This file provides utility analysis objects describing memory locations.
#define T1
Module.h This file contains the declarations for the Module class.
Module * Mod
FunctionAnalysisManager FAM
This header defines various interfaces for pass management in LLVM.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This is the interface for a metadata-based scoped no-alias analysis.
This file defines the SmallPtrSet class.
This is the interface for a metadata-based TBAA.
A manager for alias analyses.
void registerFunctionAnalysis()
Register a specific AA result.
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB)
The main low level interface to the alias analysis implementation.
uint64_t getLimitedValue(uint64_t Limit=UINT64_MAX) const
If this value is smaller than the specified limit, return it, otherwise return the limit value.
Definition: APInt.h:453
The possible results of an alias query.
Definition: AliasAnalysis.h:82
@ PartialAlias
The two locations alias, but only due to a partial overlap.
@ MustAlias
The two locations precisely alias each other.
an instruction to allocate memory on the stack
Definition: Instructions.h:58
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:649
bool registerPass(PassBuilderT &&PassBuilder)
Register an analysis pass with the manager.
Definition: PassManager.h:865
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:803
This class represents an incoming formal argument to a Function.
Definition: Argument.h:28
bool hasNoAliasAttr() const
Return true if this argument has the noalias attribute.
Definition: Function.cpp:263
bool onlyReadsMemory() const
Return true if this argument has the readonly or readnone attribute.
Definition: Function.cpp:299
Type * getParamStructRetType() const
If this is an sret argument, return its type.
Definition: Function.cpp:227
bool hasStructRetAttr() const
Return true if this argument has the sret attribute.
Definition: Function.cpp:278
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
A function analysis which provides an AssumptionCache.
A cache of @llvm.assume calls within a function.
bool hasParamAttr(unsigned ArgNo, Attribute::AttrKind Kind) const
Return true if the attribute exists for the given argument.
Definition: Attributes.h:767
AttributeSet getAttributes(unsigned Index) const
The attributes for the specified index are returned.
Analysis pass providing a never-invalidated alias analysis result.
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
iterator end()
Definition: BasicBlock.h:442
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:429
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
Definition: BasicBlock.cpp:497
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:165
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1227
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:451
static bool isNoopCast(Instruction::CastOps Opcode, Type *SrcTy, Type *DstTy, const DataLayout &DL)
A no-op cast is one that can be effected without changing any bits.
A constant value that is initialized with an expression using other constant values.
Definition: Constants.h:1002
This is the shared class of boolean and integer constants.
Definition: Constants.h:78
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:136
This is an important base class in LLVM.
Definition: Constant.h:41
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:110
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:278
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:165
This instruction extracts a single (scalar) element from a VectorType value.
This instruction extracts a struct member or array element value from an aggregate value.
Indirect Branch Instruction.
This instruction inserts a single (scalar) element into a VectorType value.
Base class for instruction visitors.
Definition: InstVisitor.h:78
RetTy visitIndirectBrInst(IndirectBrInst &I)
Definition: InstVisitor.h:235
RetTy visitExtractElementInst(ExtractElementInst &I)
Definition: InstVisitor.h:191
RetTy visitCallBase(CallBase &I)
Definition: InstVisitor.h:267
void visitFunction(Function &F)
Definition: InstVisitor.h:142
RetTy visitUnreachableInst(UnreachableInst &I)
Definition: InstVisitor.h:241
RetTy visitReturnInst(ReturnInst &I)
Definition: InstVisitor.h:226
RetTy visitStoreInst(StoreInst &I)
Definition: InstVisitor.h:170
RetTy visitInsertElementInst(InsertElementInst &I)
Definition: InstVisitor.h:192
RetTy visitAllocaInst(AllocaInst &I)
Definition: InstVisitor.h:168
RetTy visitLoadInst(LoadInst &I)
Definition: InstVisitor.h:169
RetTy visitVAArgInst(VAArgInst &I)
Definition: InstVisitor.h:190
bool isCast() const
Definition: Instruction.h:242
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:47
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: Lint.cpp:707
An instruction for reading from memory.
Definition: Instructions.h:177
bool hasValue() const
static LocationSize precise(uint64_t Value)
TypeSize getValue() const
bool isZero() const
static constexpr LocationSize afterPointer()
Any location after the base pointer (but still within the underlying object).
This class wraps the llvm.memcpy.inline intrinsic.
ConstantInt * getLength() const
This class wraps the llvm.memcpy intrinsic.
Value * getLength() const
Value * getDest() const
This is just like getRawDest, but it strips off any cast instructions (including addrspacecast) that ...
MaybeAlign getDestAlign() const
This class wraps the llvm.memmove intrinsic.
This class wraps the llvm.memset.inline intrinsic.
This class wraps the llvm.memset and llvm.memset.inline intrinsics.
MaybeAlign getSourceAlign() const
Value * getSource() const
This is just like getRawSource, but it strips off any cast instructions that feed it,...
Representation for a specific memory location.
static MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
static MemoryLocation getForSource(const MemTransferInst *MTI)
Return a location representing the source of a memory transfer.
LocationSize Size
The maximum size of the location, in address-units, or UnknownSize if the size is not known.
static MemoryLocation getAfter(const Value *Ptr, const AAMDNodes &AATags=AAMDNodes())
Return a location that may access any location after Ptr, while remaining within the underlying objec...
const Value * Ptr
The address of the start of the location.
static MemoryLocation getForDest(const MemIntrinsic *MI)
Return a location representing the destination of a memory set or transfer.
static MemoryLocation getForArgument(const CallBase *Call, unsigned ArgIdx, const TargetLibraryInfo *TLI)
Return a location representing a particular argument of a call.
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:172
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:178
Return a value (possibly void), from a function.
Analysis pass providing a never-invalidated alias analysis result.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:345
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:366
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:451
An instruction for storing to memory.
Definition: Instructions.h:301
Analysis pass providing the TargetLibraryInfo.
Provides information about what library functions are available for the current target.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
Analysis pass providing a never-invalidated alias analysis result.
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:255
bool isSized(SmallPtrSetImpl< Type * > *Visited=nullptr) const
Return true if it makes sense to take the size of this type.
Definition: Type.h:302
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1724
This function has undefined behavior.
This class represents the va_arg llvm instruction, which returns an argument of the specified type gi...
LLVM Value Representation.
Definition: Value.h:74
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
A raw_ostream that writes to an std::string.
Definition: raw_ostream.h:642
Definition: Lint.cpp:81
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
@ CE
Windows NT (Windows on ARM)
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
@ Offset
Definition: DWP.cpp:440
Value * GetPointerBaseWithConstantOffset(Value *Ptr, int64_t &Offset, const DataLayout &DL, bool AllowNonInbounds=true)
Analyze the specified pointer to see if it can be expressed as a base pointer plus a constant offset.
const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=6)
This method strips off any GEP address adjustments and pointer casts from the specified value,...
Value * FindAvailableLoadedValue(LoadInst *Load, BasicBlock *ScanBB, BasicBlock::iterator &ScanFrom, unsigned MaxInstsToScan=DefMaxInstsToScan, AAResults *AA=nullptr, bool *IsLoadCSE=nullptr, unsigned *NumScanedInst=nullptr)
Scan backwards to see if we have the value of the given load available locally within a small number ...
Definition: Loads.cpp:453
Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
Constant * ConstantFoldConstant(const Constant *C, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr)
ConstantFoldConstant - Fold the constant using the specified DataLayout.
Value * FindInsertedValue(Value *V, ArrayRef< unsigned > idx_range, Instruction *InsertBefore=nullptr)
Given an aggregate and an sequence of indices, see if the scalar value indexed is already around as a...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
void lintModule(const Module &M)
Lint a module.
Definition: Lint.cpp:746
cl::opt< unsigned > DefMaxInstsToScan
The default number of maximum instructions to scan in the block, used by FindAvailableLoadedValue().
@ Mod
The access may modify the value stored in memory.
void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
Align commonAlignment(Align A, uint64_t Offset)
Returns the alignment that satisfies both alignments.
Definition: Alignment.h:212
void lintFunction(const Function &F)
lintFunction - Check a function for errors, printing messages on stderr.
Definition: Lint.cpp:726
#define N
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:39
bool isZero() const
Returns true if value is all zero.
Definition: KnownBits.h:72
This struct is a compact representation of a valid (power of two) or undefined (0) alignment.
Definition: Alignment.h:117