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