1113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman//===-- Lint.cpp - Check for common errors in LLVM IR ---------------------===// 2113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman// 3113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman// The LLVM Compiler Infrastructure 4113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman// 5113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman// This file is distributed under the University of Illinois Open Source 6113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman// License. See LICENSE.TXT for details. 7113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman// 8113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman//===----------------------------------------------------------------------===// 9113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman// 10113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman// This pass statically checks for common and easily-identified constructs 11113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman// which produce undefined or likely unintended behavior in LLVM IR. 12113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman// 13113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman// It is not a guarantee of correctness, in two ways. First, it isn't 14113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman// comprehensive. There are checks which could be done statically which are 15113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman// not yet implemented. Some of these are indicated by TODO comments, but 16113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman// those aren't comprehensive either. Second, many conditions cannot be 17113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman// checked statically. This pass does no dynamic instrumentation, so it 18113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman// can't check for all possible problems. 19113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman// 20113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman// Another limitation is that it assumes all code will be executed. A store 21113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman// through a null pointer in a basic block which is never reached is harmless, 22d3b6e41ffb6aae6a1efc31b0a9f9050234570841Dan Gohman// but this pass will warn about it anyway. This is the main reason why most 23d3b6e41ffb6aae6a1efc31b0a9f9050234570841Dan Gohman// of these checks live here instead of in the Verifier pass. 240883355976328699815a7e3ef2efba2a9fd81e02Dan Gohman// 25113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman// Optimization passes may make conditions that this pass checks for more or 26113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman// less obvious. If an optimization pass appears to be introducing a warning, 27113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman// it may be that the optimization pass is merely exposing an existing 28113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman// condition in the code. 29113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman// 30113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman// This code may be run before instcombine. In many cases, instcombine checks 31113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman// for the same kinds of things and turns instructions with undefined behavior 32113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman// into unreachable (or equivalent). Because of this, this pass makes some 33113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman// effort to look through bitcasts and so on. 34113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman// 35113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman//===----------------------------------------------------------------------===// 36113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman 37d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Analysis/Lint.h" 38d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/STLExtras.h" 39113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman#include "llvm/Analysis/AliasAnalysis.h" 40ff26d4e9ceabb48463cc1aaeccfd1784fb52f755Dan Gohman#include "llvm/Analysis/ConstantFolding.h" 41ff26d4e9ceabb48463cc1aaeccfd1784fb52f755Dan Gohman#include "llvm/Analysis/Dominators.h" 42d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Analysis/InstructionSimplify.h" 43ff26d4e9ceabb48463cc1aaeccfd1784fb52f755Dan Gohman#include "llvm/Analysis/Loads.h" 44d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Analysis/Passes.h" 45113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman#include "llvm/Analysis/ValueTracking.h" 46113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman#include "llvm/Assembly/Writer.h" 470b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/DataLayout.h" 480b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Function.h" 490b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/IntrinsicInst.h" 5084bcf93e0fd225de2217d1b712c01586a633a6d8Chandler Carruth#include "llvm/InstVisitor.h" 51d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Pass.h" 52d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/PassManager.h" 53113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman#include "llvm/Support/CallSite.h" 54113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman#include "llvm/Support/Debug.h" 55113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman#include "llvm/Support/raw_ostream.h" 56d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Target/TargetLibraryInfo.h" 57113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohmanusing namespace llvm; 58113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman 59113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohmannamespace { 605b61b3818a3aadb928485571d69e5bccc52e1d5bDan Gohman namespace MemRef { 615b61b3818a3aadb928485571d69e5bccc52e1d5bDan Gohman static unsigned Read = 1; 625b61b3818a3aadb928485571d69e5bccc52e1d5bDan Gohman static unsigned Write = 2; 635b61b3818a3aadb928485571d69e5bccc52e1d5bDan Gohman static unsigned Callee = 4; 645b61b3818a3aadb928485571d69e5bccc52e1d5bDan Gohman static unsigned Branchee = 8; 655b61b3818a3aadb928485571d69e5bccc52e1d5bDan Gohman } 665b61b3818a3aadb928485571d69e5bccc52e1d5bDan Gohman 67113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman class Lint : public FunctionPass, public InstVisitor<Lint> { 68113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman friend class InstVisitor<Lint>; 69113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman 70be02b20a8f9e9503733df945968e48562714dd32Dan Gohman void visitFunction(Function &F); 71be02b20a8f9e9503733df945968e48562714dd32Dan Gohman 72113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman void visitCallSite(CallSite CS); 73aec2a0dbce170c658af428e76187e4361a4a1caaDan Gohman void visitMemoryReference(Instruction &I, Value *Ptr, 743da848bbda62b25c12335998aaa44ab361f0bf15Dan Gohman uint64_t Size, unsigned Align, 75db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *Ty, unsigned Flags); 76113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman 77113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman void visitCallInst(CallInst &I); 78113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman void visitInvokeInst(InvokeInst &I); 79113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman void visitReturnInst(ReturnInst &I); 80113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman void visitLoadInst(LoadInst &I); 81113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman void visitStoreInst(StoreInst &I); 82be02b20a8f9e9503733df945968e48562714dd32Dan Gohman void visitXor(BinaryOperator &I); 83be02b20a8f9e9503733df945968e48562714dd32Dan Gohman void visitSub(BinaryOperator &I); 84dd98c4d1859a318e7586f87031db44b215476020Dan Gohman void visitLShr(BinaryOperator &I); 85dd98c4d1859a318e7586f87031db44b215476020Dan Gohman void visitAShr(BinaryOperator &I); 86dd98c4d1859a318e7586f87031db44b215476020Dan Gohman void visitShl(BinaryOperator &I); 87113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman void visitSDiv(BinaryOperator &I); 88113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman void visitUDiv(BinaryOperator &I); 89113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman void visitSRem(BinaryOperator &I); 90113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman void visitURem(BinaryOperator &I); 91113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman void visitAllocaInst(AllocaInst &I); 92113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman void visitVAArgInst(VAArgInst &I); 93113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman void visitIndirectBrInst(IndirectBrInst &I); 94dd98c4d1859a318e7586f87031db44b215476020Dan Gohman void visitExtractElementInst(ExtractElementInst &I); 95dd98c4d1859a318e7586f87031db44b215476020Dan Gohman void visitInsertElementInst(InsertElementInst &I); 96be02b20a8f9e9503733df945968e48562714dd32Dan Gohman void visitUnreachableInst(UnreachableInst &I); 97113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman 98ff26d4e9ceabb48463cc1aaeccfd1784fb52f755Dan Gohman Value *findValue(Value *V, bool OffsetOk) const; 9917d95965cbf529f96277130b75c018f5f3873b66Dan Gohman Value *findValueImpl(Value *V, bool OffsetOk, 10017d95965cbf529f96277130b75c018f5f3873b66Dan Gohman SmallPtrSet<Value *, 4> &Visited) const; 101ff26d4e9ceabb48463cc1aaeccfd1784fb52f755Dan Gohman 102113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman public: 103113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman Module *Mod; 104113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman AliasAnalysis *AA; 105ff26d4e9ceabb48463cc1aaeccfd1784fb52f755Dan Gohman DominatorTree *DT; 1063574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmow DataLayout *TD; 107618c1dbd293d15ee19f61b1156ab8086ad28311aChad Rosier TargetLibraryInfo *TLI; 108113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman 109113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman std::string Messages; 110113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman raw_string_ostream MessagesStr; 111113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman 112113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman static char ID; // Pass identification, replacement for typeid 113081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson Lint() : FunctionPass(ID), MessagesStr(Messages) { 114081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeLintPass(*PassRegistry::getPassRegistry()); 115081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 116113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman 117113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman virtual bool runOnFunction(Function &F); 118113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman 119113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman virtual void getAnalysisUsage(AnalysisUsage &AU) const { 120113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman AU.setPreservesAll(); 121113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman AU.addRequired<AliasAnalysis>(); 122618c1dbd293d15ee19f61b1156ab8086ad28311aChad Rosier AU.addRequired<TargetLibraryInfo>(); 123ff26d4e9ceabb48463cc1aaeccfd1784fb52f755Dan Gohman AU.addRequired<DominatorTree>(); 124113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman } 125113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman virtual void print(raw_ostream &O, const Module *M) const {} 126113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman 127113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman void WriteValue(const Value *V) { 128113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman if (!V) return; 129113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman if (isa<Instruction>(V)) { 130113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman MessagesStr << *V << '\n'; 131113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman } else { 132113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman WriteAsOperand(MessagesStr, V, true, Mod); 133113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman MessagesStr << '\n'; 134113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman } 135113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman } 136113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman 137113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman // CheckFailed - A check failed, so print out the condition and the message 138113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman // that failed. This provides a nice place to put a breakpoint if you want 139113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman // to see why something is not correct. 140113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman void CheckFailed(const Twine &Message, 141113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman const Value *V1 = 0, const Value *V2 = 0, 142113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman const Value *V3 = 0, const Value *V4 = 0) { 143113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman MessagesStr << Message.str() << "\n"; 144113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman WriteValue(V1); 145113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman WriteValue(V2); 146113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman WriteValue(V3); 147113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman WriteValue(V4); 148113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman } 149113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman }; 150113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman} 151113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman 152113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohmanchar Lint::ID = 0; 1532ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_BEGIN(Lint, "lint", "Statically lint-checks LLVM IR", 1542ab36d350293c77fc8941ce1023e4899df7e3a82Owen Anderson false, true) 155618c1dbd293d15ee19f61b1156ab8086ad28311aChad RosierINITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo) 1562ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(DominatorTree) 1572ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_AG_DEPENDENCY(AliasAnalysis) 1582ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_END(Lint, "lint", "Statically lint-checks LLVM IR", 1592ab36d350293c77fc8941ce1023e4899df7e3a82Owen Anderson false, true) 160113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman 161113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman// Assert - We know that cond should be true, if not print an error message. 162113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman#define Assert(C, M) \ 163113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman do { if (!(C)) { CheckFailed(M); return; } } while (0) 164113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman#define Assert1(C, M, V1) \ 165113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman do { if (!(C)) { CheckFailed(M, V1); return; } } while (0) 166113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman#define Assert2(C, M, V1, V2) \ 167113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman do { if (!(C)) { CheckFailed(M, V1, V2); return; } } while (0) 168113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman#define Assert3(C, M, V1, V2, V3) \ 169113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman do { if (!(C)) { CheckFailed(M, V1, V2, V3); return; } } while (0) 170113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman#define Assert4(C, M, V1, V2, V3, V4) \ 171113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman do { if (!(C)) { CheckFailed(M, V1, V2, V3, V4); return; } } while (0) 172113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman 173113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman// Lint::run - This is the main Analysis entry point for a 174113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman// function. 175113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman// 176113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohmanbool Lint::runOnFunction(Function &F) { 177113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman Mod = F.getParent(); 178113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman AA = &getAnalysis<AliasAnalysis>(); 179ff26d4e9ceabb48463cc1aaeccfd1784fb52f755Dan Gohman DT = &getAnalysis<DominatorTree>(); 1803574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmow TD = getAnalysisIfAvailable<DataLayout>(); 181618c1dbd293d15ee19f61b1156ab8086ad28311aChad Rosier TLI = &getAnalysis<TargetLibraryInfo>(); 182113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman visit(F); 183113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman dbgs() << MessagesStr.str(); 184a0f7ff334f86926356491ec78ab3066247dc93b1Dan Gohman Messages.clear(); 185113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman return false; 186113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman} 187113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman 188be02b20a8f9e9503733df945968e48562714dd32Dan Gohmanvoid Lint::visitFunction(Function &F) { 189be02b20a8f9e9503733df945968e48562714dd32Dan Gohman // This isn't undefined behavior, it's just a little unusual, and it's a 190be02b20a8f9e9503733df945968e48562714dd32Dan Gohman // fairly common mistake to neglect to name a function. 191be02b20a8f9e9503733df945968e48562714dd32Dan Gohman Assert1(F.hasName() || F.hasLocalLinkage(), 192be02b20a8f9e9503733df945968e48562714dd32Dan Gohman "Unusual: Unnamed function with non-local linkage", &F); 1930ce249911b85e076defd9a895b8197af02091d2dDan Gohman 1940ce249911b85e076defd9a895b8197af02091d2dDan Gohman // TODO: Check for irreducible control flow. 195113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman} 196113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman 197113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohmanvoid Lint::visitCallSite(CallSite CS) { 198113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman Instruction &I = *CS.getInstruction(); 199113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman Value *Callee = CS.getCalledValue(); 200113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman 201f3a925dc7a14ade42da442b49c304c064954c1d4Dan Gohman visitMemoryReference(I, Callee, AliasAnalysis::UnknownSize, 202f3a925dc7a14ade42da442b49c304c064954c1d4Dan Gohman 0, 0, MemRef::Callee); 203113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman 204ff26d4e9ceabb48463cc1aaeccfd1784fb52f755Dan Gohman if (Function *F = dyn_cast<Function>(findValue(Callee, /*OffsetOk=*/false))) { 205113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman Assert1(CS.getCallingConv() == F->getCallingConv(), 206be02b20a8f9e9503733df945968e48562714dd32Dan Gohman "Undefined behavior: Caller and callee calling convention differ", 207be02b20a8f9e9503733df945968e48562714dd32Dan Gohman &I); 208113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman 209db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner FunctionType *FT = F->getFunctionType(); 210113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman unsigned NumActualArgs = unsigned(CS.arg_end()-CS.arg_begin()); 211113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman 212113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman Assert1(FT->isVarArg() ? 213113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman FT->getNumParams() <= NumActualArgs : 214113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman FT->getNumParams() == NumActualArgs, 215be02b20a8f9e9503733df945968e48562714dd32Dan Gohman "Undefined behavior: Call argument count mismatches callee " 216be02b20a8f9e9503733df945968e48562714dd32Dan Gohman "argument count", &I); 217113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman 218545d00645c224e3734a11a6b9b95c8f153de1d8dDan Gohman Assert1(FT->getReturnType() == I.getType(), 219545d00645c224e3734a11a6b9b95c8f153de1d8dDan Gohman "Undefined behavior: Call return type mismatches " 220545d00645c224e3734a11a6b9b95c8f153de1d8dDan Gohman "callee return type", &I); 221545d00645c224e3734a11a6b9b95c8f153de1d8dDan Gohman 222aec2a0dbce170c658af428e76187e4361a4a1caaDan Gohman // Check argument types (in case the callee was casted) and attributes. 2230ce249911b85e076defd9a895b8197af02091d2dDan Gohman // TODO: Verify that caller and callee attributes are compatible. 224aec2a0dbce170c658af428e76187e4361a4a1caaDan Gohman Function::arg_iterator PI = F->arg_begin(), PE = F->arg_end(); 225aec2a0dbce170c658af428e76187e4361a4a1caaDan Gohman CallSite::arg_iterator AI = CS.arg_begin(), AE = CS.arg_end(); 226aec2a0dbce170c658af428e76187e4361a4a1caaDan Gohman for (; AI != AE; ++AI) { 227aec2a0dbce170c658af428e76187e4361a4a1caaDan Gohman Value *Actual = *AI; 228aec2a0dbce170c658af428e76187e4361a4a1caaDan Gohman if (PI != PE) { 229aec2a0dbce170c658af428e76187e4361a4a1caaDan Gohman Argument *Formal = PI++; 230aec2a0dbce170c658af428e76187e4361a4a1caaDan Gohman Assert1(Formal->getType() == Actual->getType(), 231aec2a0dbce170c658af428e76187e4361a4a1caaDan Gohman "Undefined behavior: Call argument type mismatches " 232aec2a0dbce170c658af428e76187e4361a4a1caaDan Gohman "callee parameter type", &I); 23310e7726e6c317b2fe08533d555ef07b4c206aee2Dan Gohman 234c1f1efdd1a835feae3213495af8a5720ff700c38Dan Gohman // Check that noalias arguments don't alias other arguments. This is 235c1f1efdd1a835feae3213495af8a5720ff700c38Dan Gohman // not fully precise because we don't know the sizes of the dereferenced 236c1f1efdd1a835feae3213495af8a5720ff700c38Dan Gohman // memory regions. 237aec2a0dbce170c658af428e76187e4361a4a1caaDan Gohman if (Formal->hasNoAliasAttr() && Actual->getType()->isPointerTy()) 238f3b8c7659979ff481e7a15fa3406b280e425cf0dDan Gohman for (CallSite::arg_iterator BI = CS.arg_begin(); BI != AE; ++BI) 2394a2a3eab2dcca16d61e16d3566eb936683ff9753Dan Gohman if (AI != BI && (*BI)->getType()->isPointerTy()) { 2404a2a3eab2dcca16d61e16d3566eb936683ff9753Dan Gohman AliasAnalysis::AliasResult Result = AA->alias(*AI, *BI); 2414a2a3eab2dcca16d61e16d3566eb936683ff9753Dan Gohman Assert1(Result != AliasAnalysis::MustAlias && 2424a2a3eab2dcca16d61e16d3566eb936683ff9753Dan Gohman Result != AliasAnalysis::PartialAlias, 2434a2a3eab2dcca16d61e16d3566eb936683ff9753Dan Gohman "Unusual: noalias argument aliases another argument", &I); 2444a2a3eab2dcca16d61e16d3566eb936683ff9753Dan Gohman } 24510e7726e6c317b2fe08533d555ef07b4c206aee2Dan Gohman 24610e7726e6c317b2fe08533d555ef07b4c206aee2Dan Gohman // Check that an sret argument points to valid memory. 247aec2a0dbce170c658af428e76187e4361a4a1caaDan Gohman if (Formal->hasStructRetAttr() && Actual->getType()->isPointerTy()) { 248db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *Ty = 249aec2a0dbce170c658af428e76187e4361a4a1caaDan Gohman cast<PointerType>(Formal->getType())->getElementType(); 250aec2a0dbce170c658af428e76187e4361a4a1caaDan Gohman visitMemoryReference(I, Actual, AA->getTypeStoreSize(Ty), 251aec2a0dbce170c658af428e76187e4361a4a1caaDan Gohman TD ? TD->getABITypeAlignment(Ty) : 0, 252aec2a0dbce170c658af428e76187e4361a4a1caaDan Gohman Ty, MemRef::Read | MemRef::Write); 253aec2a0dbce170c658af428e76187e4361a4a1caaDan Gohman } 254aec2a0dbce170c658af428e76187e4361a4a1caaDan Gohman } 255aec2a0dbce170c658af428e76187e4361a4a1caaDan Gohman } 256113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman } 257113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman 258113b3e2c6e30efd7c852d31e98b2d21778e52d1eDan Gohman if (CS.isCall() && cast<CallInst>(CS.getInstruction())->isTailCall()) 259113b3e2c6e30efd7c852d31e98b2d21778e52d1eDan Gohman for (CallSite::arg_iterator AI = CS.arg_begin(), AE = CS.arg_end(); 260113b3e2c6e30efd7c852d31e98b2d21778e52d1eDan Gohman AI != AE; ++AI) { 261ff26d4e9ceabb48463cc1aaeccfd1784fb52f755Dan Gohman Value *Obj = findValue(*AI, /*OffsetOk=*/true); 262078f8595b5ddc6cf55cc32ceeb82c67d39b3f200Dan Gohman Assert1(!isa<AllocaInst>(Obj), 263113b3e2c6e30efd7c852d31e98b2d21778e52d1eDan Gohman "Undefined behavior: Call with \"tail\" keyword references " 264078f8595b5ddc6cf55cc32ceeb82c67d39b3f200Dan Gohman "alloca", &I); 265113b3e2c6e30efd7c852d31e98b2d21778e52d1eDan Gohman } 266113b3e2c6e30efd7c852d31e98b2d21778e52d1eDan Gohman 267113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman 268113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(&I)) 269113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman switch (II->getIntrinsicID()) { 270113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman default: break; 271113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman 272113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman // TODO: Check more intrinsics 273113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman 274113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman case Intrinsic::memcpy: { 275113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman MemCpyInst *MCI = cast<MemCpyInst>(&I); 276aec2a0dbce170c658af428e76187e4361a4a1caaDan Gohman // TODO: If the size is known, use it. 277f3a925dc7a14ade42da442b49c304c064954c1d4Dan Gohman visitMemoryReference(I, MCI->getDest(), AliasAnalysis::UnknownSize, 278f3a925dc7a14ade42da442b49c304c064954c1d4Dan Gohman MCI->getAlignment(), 0, 27913ec30b6a1184c590ed93d81764a0314202abeafDan Gohman MemRef::Write); 280f3a925dc7a14ade42da442b49c304c064954c1d4Dan Gohman visitMemoryReference(I, MCI->getSource(), AliasAnalysis::UnknownSize, 281f3a925dc7a14ade42da442b49c304c064954c1d4Dan Gohman MCI->getAlignment(), 0, 2825b61b3818a3aadb928485571d69e5bccc52e1d5bDan Gohman MemRef::Read); 283113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman 284be02b20a8f9e9503733df945968e48562714dd32Dan Gohman // Check that the memcpy arguments don't overlap. The AliasAnalysis API 285be02b20a8f9e9503733df945968e48562714dd32Dan Gohman // isn't expressive enough for what we really want to do. Known partial 286be02b20a8f9e9503733df945968e48562714dd32Dan Gohman // overlap is not distinguished from the case where nothing is known. 2873da848bbda62b25c12335998aaa44ab361f0bf15Dan Gohman uint64_t Size = 0; 288113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman if (const ConstantInt *Len = 289ff26d4e9ceabb48463cc1aaeccfd1784fb52f755Dan Gohman dyn_cast<ConstantInt>(findValue(MCI->getLength(), 290ff26d4e9ceabb48463cc1aaeccfd1784fb52f755Dan Gohman /*OffsetOk=*/false))) 291113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman if (Len->getValue().isIntN(32)) 292113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman Size = Len->getValue().getZExtValue(); 293113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman Assert1(AA->alias(MCI->getSource(), Size, MCI->getDest(), Size) != 294113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman AliasAnalysis::MustAlias, 295be02b20a8f9e9503733df945968e48562714dd32Dan Gohman "Undefined behavior: memcpy source and destination overlap", &I); 296113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman break; 297113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman } 298113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman case Intrinsic::memmove: { 299113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman MemMoveInst *MMI = cast<MemMoveInst>(&I); 300aec2a0dbce170c658af428e76187e4361a4a1caaDan Gohman // TODO: If the size is known, use it. 301f3a925dc7a14ade42da442b49c304c064954c1d4Dan Gohman visitMemoryReference(I, MMI->getDest(), AliasAnalysis::UnknownSize, 302f3a925dc7a14ade42da442b49c304c064954c1d4Dan Gohman MMI->getAlignment(), 0, 30313ec30b6a1184c590ed93d81764a0314202abeafDan Gohman MemRef::Write); 304f3a925dc7a14ade42da442b49c304c064954c1d4Dan Gohman visitMemoryReference(I, MMI->getSource(), AliasAnalysis::UnknownSize, 305f3a925dc7a14ade42da442b49c304c064954c1d4Dan Gohman MMI->getAlignment(), 0, 3065b61b3818a3aadb928485571d69e5bccc52e1d5bDan Gohman MemRef::Read); 307113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman break; 308113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman } 309113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman case Intrinsic::memset: { 310113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman MemSetInst *MSI = cast<MemSetInst>(&I); 311aec2a0dbce170c658af428e76187e4361a4a1caaDan Gohman // TODO: If the size is known, use it. 312f3a925dc7a14ade42da442b49c304c064954c1d4Dan Gohman visitMemoryReference(I, MSI->getDest(), AliasAnalysis::UnknownSize, 313f3a925dc7a14ade42da442b49c304c064954c1d4Dan Gohman MSI->getAlignment(), 0, 3145b61b3818a3aadb928485571d69e5bccc52e1d5bDan Gohman MemRef::Write); 315113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman break; 316113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman } 317113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman 318113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman case Intrinsic::vastart: 319be02b20a8f9e9503733df945968e48562714dd32Dan Gohman Assert1(I.getParent()->getParent()->isVarArg(), 320be02b20a8f9e9503733df945968e48562714dd32Dan Gohman "Undefined behavior: va_start called in a non-varargs function", 321be02b20a8f9e9503733df945968e48562714dd32Dan Gohman &I); 322be02b20a8f9e9503733df945968e48562714dd32Dan Gohman 323f3a925dc7a14ade42da442b49c304c064954c1d4Dan Gohman visitMemoryReference(I, CS.getArgument(0), AliasAnalysis::UnknownSize, 324f3a925dc7a14ade42da442b49c304c064954c1d4Dan Gohman 0, 0, MemRef::Read | MemRef::Write); 325113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman break; 326113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman case Intrinsic::vacopy: 327f3a925dc7a14ade42da442b49c304c064954c1d4Dan Gohman visitMemoryReference(I, CS.getArgument(0), AliasAnalysis::UnknownSize, 328f3a925dc7a14ade42da442b49c304c064954c1d4Dan Gohman 0, 0, MemRef::Write); 329f3a925dc7a14ade42da442b49c304c064954c1d4Dan Gohman visitMemoryReference(I, CS.getArgument(1), AliasAnalysis::UnknownSize, 330f3a925dc7a14ade42da442b49c304c064954c1d4Dan Gohman 0, 0, MemRef::Read); 331113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman break; 332113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman case Intrinsic::vaend: 333f3a925dc7a14ade42da442b49c304c064954c1d4Dan Gohman visitMemoryReference(I, CS.getArgument(0), AliasAnalysis::UnknownSize, 334f3a925dc7a14ade42da442b49c304c064954c1d4Dan Gohman 0, 0, MemRef::Read | MemRef::Write); 335113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman break; 336882ddb492d9d5497514ac5c084686f07716115e8Dan Gohman 337882ddb492d9d5497514ac5c084686f07716115e8Dan Gohman case Intrinsic::stackrestore: 338882ddb492d9d5497514ac5c084686f07716115e8Dan Gohman // Stackrestore doesn't read or write memory, but it sets the 339882ddb492d9d5497514ac5c084686f07716115e8Dan Gohman // stack pointer, which the compiler may read from or write to 340882ddb492d9d5497514ac5c084686f07716115e8Dan Gohman // at any time, so check it for both readability and writeability. 341f3a925dc7a14ade42da442b49c304c064954c1d4Dan Gohman visitMemoryReference(I, CS.getArgument(0), AliasAnalysis::UnknownSize, 342f3a925dc7a14ade42da442b49c304c064954c1d4Dan Gohman 0, 0, MemRef::Read | MemRef::Write); 343882ddb492d9d5497514ac5c084686f07716115e8Dan Gohman break; 344113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman } 345113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman} 346113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman 347113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohmanvoid Lint::visitCallInst(CallInst &I) { 348113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman return visitCallSite(&I); 349113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman} 350113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman 351113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohmanvoid Lint::visitInvokeInst(InvokeInst &I) { 352113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman return visitCallSite(&I); 353113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman} 354113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman 355113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohmanvoid Lint::visitReturnInst(ReturnInst &I) { 356113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman Function *F = I.getParent()->getParent(); 357113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman Assert1(!F->doesNotReturn(), 358be02b20a8f9e9503733df945968e48562714dd32Dan Gohman "Unusual: Return statement in function with noreturn attribute", 359be02b20a8f9e9503733df945968e48562714dd32Dan Gohman &I); 360292fc87fe2f1611e7c83a61796ab71db6a0f7d97Dan Gohman 361292fc87fe2f1611e7c83a61796ab71db6a0f7d97Dan Gohman if (Value *V = I.getReturnValue()) { 362ff26d4e9ceabb48463cc1aaeccfd1784fb52f755Dan Gohman Value *Obj = findValue(V, /*OffsetOk=*/true); 363078f8595b5ddc6cf55cc32ceeb82c67d39b3f200Dan Gohman Assert1(!isa<AllocaInst>(Obj), 364078f8595b5ddc6cf55cc32ceeb82c67d39b3f200Dan Gohman "Unusual: Returning alloca value", &I); 365292fc87fe2f1611e7c83a61796ab71db6a0f7d97Dan Gohman } 366113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman} 367113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman 368aec2a0dbce170c658af428e76187e4361a4a1caaDan Gohman// TODO: Check that the reference is in bounds. 3690ce249911b85e076defd9a895b8197af02091d2dDan Gohman// TODO: Check readnone/readonly function attributes. 370113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohmanvoid Lint::visitMemoryReference(Instruction &I, 3713da848bbda62b25c12335998aaa44ab361f0bf15Dan Gohman Value *Ptr, uint64_t Size, unsigned Align, 372db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *Ty, unsigned Flags) { 373aec2a0dbce170c658af428e76187e4361a4a1caaDan Gohman // If no memory is being referenced, it doesn't matter if the pointer 374aec2a0dbce170c658af428e76187e4361a4a1caaDan Gohman // is valid. 375aec2a0dbce170c658af428e76187e4361a4a1caaDan Gohman if (Size == 0) 376aec2a0dbce170c658af428e76187e4361a4a1caaDan Gohman return; 377aec2a0dbce170c658af428e76187e4361a4a1caaDan Gohman 378ff26d4e9ceabb48463cc1aaeccfd1784fb52f755Dan Gohman Value *UnderlyingObject = findValue(Ptr, /*OffsetOk=*/true); 379be02b20a8f9e9503733df945968e48562714dd32Dan Gohman Assert1(!isa<ConstantPointerNull>(UnderlyingObject), 380be02b20a8f9e9503733df945968e48562714dd32Dan Gohman "Undefined behavior: Null pointer dereference", &I); 381be02b20a8f9e9503733df945968e48562714dd32Dan Gohman Assert1(!isa<UndefValue>(UnderlyingObject), 382be02b20a8f9e9503733df945968e48562714dd32Dan Gohman "Undefined behavior: Undef pointer dereference", &I); 383aec2a0dbce170c658af428e76187e4361a4a1caaDan Gohman Assert1(!isa<ConstantInt>(UnderlyingObject) || 384aec2a0dbce170c658af428e76187e4361a4a1caaDan Gohman !cast<ConstantInt>(UnderlyingObject)->isAllOnesValue(), 385aec2a0dbce170c658af428e76187e4361a4a1caaDan Gohman "Unusual: All-ones pointer dereference", &I); 386aec2a0dbce170c658af428e76187e4361a4a1caaDan Gohman Assert1(!isa<ConstantInt>(UnderlyingObject) || 387aec2a0dbce170c658af428e76187e4361a4a1caaDan Gohman !cast<ConstantInt>(UnderlyingObject)->isOne(), 388aec2a0dbce170c658af428e76187e4361a4a1caaDan Gohman "Unusual: Address one pointer dereference", &I); 389113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman 3905b61b3818a3aadb928485571d69e5bccc52e1d5bDan Gohman if (Flags & MemRef::Write) { 3915b61b3818a3aadb928485571d69e5bccc52e1d5bDan Gohman if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(UnderlyingObject)) 3925b61b3818a3aadb928485571d69e5bccc52e1d5bDan Gohman Assert1(!GV->isConstant(), 3935b61b3818a3aadb928485571d69e5bccc52e1d5bDan Gohman "Undefined behavior: Write to read-only memory", &I); 3945b61b3818a3aadb928485571d69e5bccc52e1d5bDan Gohman Assert1(!isa<Function>(UnderlyingObject) && 3955b61b3818a3aadb928485571d69e5bccc52e1d5bDan Gohman !isa<BlockAddress>(UnderlyingObject), 3965b61b3818a3aadb928485571d69e5bccc52e1d5bDan Gohman "Undefined behavior: Write to text section", &I); 3975b61b3818a3aadb928485571d69e5bccc52e1d5bDan Gohman } 3985b61b3818a3aadb928485571d69e5bccc52e1d5bDan Gohman if (Flags & MemRef::Read) { 3995b61b3818a3aadb928485571d69e5bccc52e1d5bDan Gohman Assert1(!isa<Function>(UnderlyingObject), 4005b61b3818a3aadb928485571d69e5bccc52e1d5bDan Gohman "Unusual: Load from function body", &I); 4015b61b3818a3aadb928485571d69e5bccc52e1d5bDan Gohman Assert1(!isa<BlockAddress>(UnderlyingObject), 4025b61b3818a3aadb928485571d69e5bccc52e1d5bDan Gohman "Undefined behavior: Load from block address", &I); 4035b61b3818a3aadb928485571d69e5bccc52e1d5bDan Gohman } 4045b61b3818a3aadb928485571d69e5bccc52e1d5bDan Gohman if (Flags & MemRef::Callee) { 4055b61b3818a3aadb928485571d69e5bccc52e1d5bDan Gohman Assert1(!isa<BlockAddress>(UnderlyingObject), 4065b61b3818a3aadb928485571d69e5bccc52e1d5bDan Gohman "Undefined behavior: Call to block address", &I); 4075b61b3818a3aadb928485571d69e5bccc52e1d5bDan Gohman } 4085b61b3818a3aadb928485571d69e5bccc52e1d5bDan Gohman if (Flags & MemRef::Branchee) { 4095b61b3818a3aadb928485571d69e5bccc52e1d5bDan Gohman Assert1(!isa<Constant>(UnderlyingObject) || 4105b61b3818a3aadb928485571d69e5bccc52e1d5bDan Gohman isa<BlockAddress>(UnderlyingObject), 4115b61b3818a3aadb928485571d69e5bccc52e1d5bDan Gohman "Undefined behavior: Branch to non-blockaddress", &I); 4125b61b3818a3aadb928485571d69e5bccc52e1d5bDan Gohman } 4135b61b3818a3aadb928485571d69e5bccc52e1d5bDan Gohman 414c7c42f71aad7d33892de73d6d6397e38814b0e97Duncan Sands // Check for buffer overflows and misalignment. 415a070d2a0355c4993240b5206ebc1d517c151331dDan Gohman // Only handles memory references that read/write something simple like an 416a070d2a0355c4993240b5206ebc1d517c151331dDan Gohman // alloca instruction or a global variable. 417a070d2a0355c4993240b5206ebc1d517c151331dDan Gohman int64_t Offset = 0; 418a070d2a0355c4993240b5206ebc1d517c151331dDan Gohman if (Value *Base = GetPointerBaseWithConstantOffset(Ptr, Offset, TD)) { 419a070d2a0355c4993240b5206ebc1d517c151331dDan Gohman // OK, so the access is to a constant offset from Ptr. Check that Ptr is 420a070d2a0355c4993240b5206ebc1d517c151331dDan Gohman // something we can handle and if so extract the size of this base object 421a070d2a0355c4993240b5206ebc1d517c151331dDan Gohman // along with its alignment. 422a070d2a0355c4993240b5206ebc1d517c151331dDan Gohman uint64_t BaseSize = AliasAnalysis::UnknownSize; 423a070d2a0355c4993240b5206ebc1d517c151331dDan Gohman unsigned BaseAlign = 0; 424a070d2a0355c4993240b5206ebc1d517c151331dDan Gohman 425a070d2a0355c4993240b5206ebc1d517c151331dDan Gohman if (AllocaInst *AI = dyn_cast<AllocaInst>(Base)) { 426a070d2a0355c4993240b5206ebc1d517c151331dDan Gohman Type *ATy = AI->getAllocatedType(); 427a070d2a0355c4993240b5206ebc1d517c151331dDan Gohman if (TD && !AI->isArrayAllocation() && ATy->isSized()) 428a070d2a0355c4993240b5206ebc1d517c151331dDan Gohman BaseSize = TD->getTypeAllocSize(ATy); 429a070d2a0355c4993240b5206ebc1d517c151331dDan Gohman BaseAlign = AI->getAlignment(); 430a070d2a0355c4993240b5206ebc1d517c151331dDan Gohman if (TD && BaseAlign == 0 && ATy->isSized()) 431a070d2a0355c4993240b5206ebc1d517c151331dDan Gohman BaseAlign = TD->getABITypeAlignment(ATy); 432a070d2a0355c4993240b5206ebc1d517c151331dDan Gohman } else if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Base)) { 433a070d2a0355c4993240b5206ebc1d517c151331dDan Gohman // If the global may be defined differently in another compilation unit 434a070d2a0355c4993240b5206ebc1d517c151331dDan Gohman // then don't warn about funky memory accesses. 435a070d2a0355c4993240b5206ebc1d517c151331dDan Gohman if (GV->hasDefinitiveInitializer()) { 436a070d2a0355c4993240b5206ebc1d517c151331dDan Gohman Type *GTy = GV->getType()->getElementType(); 437a070d2a0355c4993240b5206ebc1d517c151331dDan Gohman if (TD && GTy->isSized()) 438a070d2a0355c4993240b5206ebc1d517c151331dDan Gohman BaseSize = TD->getTypeAllocSize(GTy); 439a070d2a0355c4993240b5206ebc1d517c151331dDan Gohman BaseAlign = GV->getAlignment(); 440a070d2a0355c4993240b5206ebc1d517c151331dDan Gohman if (TD && BaseAlign == 0 && GTy->isSized()) 441a070d2a0355c4993240b5206ebc1d517c151331dDan Gohman BaseAlign = TD->getABITypeAlignment(GTy); 44200edf4c1d8a691543faf5adf7b05558497d38abbDuncan Sands } 443113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman } 444a070d2a0355c4993240b5206ebc1d517c151331dDan Gohman 445a070d2a0355c4993240b5206ebc1d517c151331dDan Gohman // Accesses from before the start or after the end of the object are not 446a070d2a0355c4993240b5206ebc1d517c151331dDan Gohman // defined. 447a070d2a0355c4993240b5206ebc1d517c151331dDan Gohman Assert1(Size == AliasAnalysis::UnknownSize || 448a070d2a0355c4993240b5206ebc1d517c151331dDan Gohman BaseSize == AliasAnalysis::UnknownSize || 449a070d2a0355c4993240b5206ebc1d517c151331dDan Gohman (Offset >= 0 && Offset + Size <= BaseSize), 450a070d2a0355c4993240b5206ebc1d517c151331dDan Gohman "Undefined behavior: Buffer overflow", &I); 451a070d2a0355c4993240b5206ebc1d517c151331dDan Gohman 452a070d2a0355c4993240b5206ebc1d517c151331dDan Gohman // Accesses that say that the memory is more aligned than it is are not 453a070d2a0355c4993240b5206ebc1d517c151331dDan Gohman // defined. 454a070d2a0355c4993240b5206ebc1d517c151331dDan Gohman if (TD && Align == 0 && Ty && Ty->isSized()) 455a070d2a0355c4993240b5206ebc1d517c151331dDan Gohman Align = TD->getABITypeAlignment(Ty); 456a070d2a0355c4993240b5206ebc1d517c151331dDan Gohman Assert1(!BaseAlign || Align <= MinAlign(BaseAlign, Offset), 457a070d2a0355c4993240b5206ebc1d517c151331dDan Gohman "Undefined behavior: Memory reference address is misaligned", &I); 458113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman } 459113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman} 460113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman 461113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohmanvoid Lint::visitLoadInst(LoadInst &I) { 462aec2a0dbce170c658af428e76187e4361a4a1caaDan Gohman visitMemoryReference(I, I.getPointerOperand(), 463aec2a0dbce170c658af428e76187e4361a4a1caaDan Gohman AA->getTypeStoreSize(I.getType()), I.getAlignment(), 464aec2a0dbce170c658af428e76187e4361a4a1caaDan Gohman I.getType(), MemRef::Read); 465113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman} 466113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman 467113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohmanvoid Lint::visitStoreInst(StoreInst &I) { 468aec2a0dbce170c658af428e76187e4361a4a1caaDan Gohman visitMemoryReference(I, I.getPointerOperand(), 469aec2a0dbce170c658af428e76187e4361a4a1caaDan Gohman AA->getTypeStoreSize(I.getOperand(0)->getType()), 470aec2a0dbce170c658af428e76187e4361a4a1caaDan Gohman I.getAlignment(), 471aec2a0dbce170c658af428e76187e4361a4a1caaDan Gohman I.getOperand(0)->getType(), MemRef::Write); 472113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman} 473113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman 474be02b20a8f9e9503733df945968e48562714dd32Dan Gohmanvoid Lint::visitXor(BinaryOperator &I) { 475be02b20a8f9e9503733df945968e48562714dd32Dan Gohman Assert1(!isa<UndefValue>(I.getOperand(0)) || 476be02b20a8f9e9503733df945968e48562714dd32Dan Gohman !isa<UndefValue>(I.getOperand(1)), 477be02b20a8f9e9503733df945968e48562714dd32Dan Gohman "Undefined result: xor(undef, undef)", &I); 478be02b20a8f9e9503733df945968e48562714dd32Dan Gohman} 479be02b20a8f9e9503733df945968e48562714dd32Dan Gohman 480be02b20a8f9e9503733df945968e48562714dd32Dan Gohmanvoid Lint::visitSub(BinaryOperator &I) { 481be02b20a8f9e9503733df945968e48562714dd32Dan Gohman Assert1(!isa<UndefValue>(I.getOperand(0)) || 482be02b20a8f9e9503733df945968e48562714dd32Dan Gohman !isa<UndefValue>(I.getOperand(1)), 483be02b20a8f9e9503733df945968e48562714dd32Dan Gohman "Undefined result: sub(undef, undef)", &I); 484be02b20a8f9e9503733df945968e48562714dd32Dan Gohman} 485be02b20a8f9e9503733df945968e48562714dd32Dan Gohman 486dd98c4d1859a318e7586f87031db44b215476020Dan Gohmanvoid Lint::visitLShr(BinaryOperator &I) { 487dd98c4d1859a318e7586f87031db44b215476020Dan Gohman if (ConstantInt *CI = 488ff26d4e9ceabb48463cc1aaeccfd1784fb52f755Dan Gohman dyn_cast<ConstantInt>(findValue(I.getOperand(1), /*OffsetOk=*/false))) 489dd98c4d1859a318e7586f87031db44b215476020Dan Gohman Assert1(CI->getValue().ult(cast<IntegerType>(I.getType())->getBitWidth()), 490be02b20a8f9e9503733df945968e48562714dd32Dan Gohman "Undefined result: Shift count out of range", &I); 491dd98c4d1859a318e7586f87031db44b215476020Dan Gohman} 492dd98c4d1859a318e7586f87031db44b215476020Dan Gohman 493dd98c4d1859a318e7586f87031db44b215476020Dan Gohmanvoid Lint::visitAShr(BinaryOperator &I) { 494dd98c4d1859a318e7586f87031db44b215476020Dan Gohman if (ConstantInt *CI = 495ff26d4e9ceabb48463cc1aaeccfd1784fb52f755Dan Gohman dyn_cast<ConstantInt>(findValue(I.getOperand(1), /*OffsetOk=*/false))) 496dd98c4d1859a318e7586f87031db44b215476020Dan Gohman Assert1(CI->getValue().ult(cast<IntegerType>(I.getType())->getBitWidth()), 497be02b20a8f9e9503733df945968e48562714dd32Dan Gohman "Undefined result: Shift count out of range", &I); 498dd98c4d1859a318e7586f87031db44b215476020Dan Gohman} 499dd98c4d1859a318e7586f87031db44b215476020Dan Gohman 500dd98c4d1859a318e7586f87031db44b215476020Dan Gohmanvoid Lint::visitShl(BinaryOperator &I) { 501dd98c4d1859a318e7586f87031db44b215476020Dan Gohman if (ConstantInt *CI = 502ff26d4e9ceabb48463cc1aaeccfd1784fb52f755Dan Gohman dyn_cast<ConstantInt>(findValue(I.getOperand(1), /*OffsetOk=*/false))) 503dd98c4d1859a318e7586f87031db44b215476020Dan Gohman Assert1(CI->getValue().ult(cast<IntegerType>(I.getType())->getBitWidth()), 504be02b20a8f9e9503733df945968e48562714dd32Dan Gohman "Undefined result: Shift count out of range", &I); 505dd98c4d1859a318e7586f87031db44b215476020Dan Gohman} 506dd98c4d1859a318e7586f87031db44b215476020Dan Gohman 5073574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmowstatic bool isZero(Value *V, DataLayout *TD) { 508be02b20a8f9e9503733df945968e48562714dd32Dan Gohman // Assume undef could be zero. 509be02b20a8f9e9503733df945968e48562714dd32Dan Gohman if (isa<UndefValue>(V)) return true; 510be02b20a8f9e9503733df945968e48562714dd32Dan Gohman 511113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman unsigned BitWidth = cast<IntegerType>(V->getType())->getBitWidth(); 51226c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola APInt KnownZero(BitWidth, 0), KnownOne(BitWidth, 0); 51326c8dcc692fb2addd475446cfff24d6a4e958bcaRafael Espindola ComputeMaskedBits(V, KnownZero, KnownOne, TD); 514113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman return KnownZero.isAllOnesValue(); 515113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman} 516113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman 517113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohmanvoid Lint::visitSDiv(BinaryOperator &I) { 518be02b20a8f9e9503733df945968e48562714dd32Dan Gohman Assert1(!isZero(I.getOperand(1), TD), 519be02b20a8f9e9503733df945968e48562714dd32Dan Gohman "Undefined behavior: Division by zero", &I); 520113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman} 521113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman 522113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohmanvoid Lint::visitUDiv(BinaryOperator &I) { 523be02b20a8f9e9503733df945968e48562714dd32Dan Gohman Assert1(!isZero(I.getOperand(1), TD), 524be02b20a8f9e9503733df945968e48562714dd32Dan Gohman "Undefined behavior: Division by zero", &I); 525113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman} 526113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman 527113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohmanvoid Lint::visitSRem(BinaryOperator &I) { 528be02b20a8f9e9503733df945968e48562714dd32Dan Gohman Assert1(!isZero(I.getOperand(1), TD), 529be02b20a8f9e9503733df945968e48562714dd32Dan Gohman "Undefined behavior: Division by zero", &I); 530113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman} 531113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman 532113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohmanvoid Lint::visitURem(BinaryOperator &I) { 533be02b20a8f9e9503733df945968e48562714dd32Dan Gohman Assert1(!isZero(I.getOperand(1), TD), 534be02b20a8f9e9503733df945968e48562714dd32Dan Gohman "Undefined behavior: Division by zero", &I); 535113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman} 536113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman 537113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohmanvoid Lint::visitAllocaInst(AllocaInst &I) { 538113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman if (isa<ConstantInt>(I.getArraySize())) 539113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman // This isn't undefined behavior, it's just an obvious pessimization. 540113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman Assert1(&I.getParent()->getParent()->getEntryBlock() == I.getParent(), 541be02b20a8f9e9503733df945968e48562714dd32Dan Gohman "Pessimization: Static alloca outside of entry block", &I); 5420ce249911b85e076defd9a895b8197af02091d2dDan Gohman 5430ce249911b85e076defd9a895b8197af02091d2dDan Gohman // TODO: Check for an unusual size (MSB set?) 544113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman} 545113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman 546113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohmanvoid Lint::visitVAArgInst(VAArgInst &I) { 547f3a925dc7a14ade42da442b49c304c064954c1d4Dan Gohman visitMemoryReference(I, I.getOperand(0), AliasAnalysis::UnknownSize, 0, 0, 5485b61b3818a3aadb928485571d69e5bccc52e1d5bDan Gohman MemRef::Read | MemRef::Write); 549113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman} 550113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman 551113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohmanvoid Lint::visitIndirectBrInst(IndirectBrInst &I) { 552f3a925dc7a14ade42da442b49c304c064954c1d4Dan Gohman visitMemoryReference(I, I.getAddress(), AliasAnalysis::UnknownSize, 0, 0, 553f3a925dc7a14ade42da442b49c304c064954c1d4Dan Gohman MemRef::Branchee); 554a8afb2a623b8644f9460be66d99c073579e23df0Dan Gohman 555a8afb2a623b8644f9460be66d99c073579e23df0Dan Gohman Assert1(I.getNumDestinations() != 0, 556a8afb2a623b8644f9460be66d99c073579e23df0Dan Gohman "Undefined behavior: indirectbr with no destinations", &I); 557113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman} 558113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman 559dd98c4d1859a318e7586f87031db44b215476020Dan Gohmanvoid Lint::visitExtractElementInst(ExtractElementInst &I) { 560dd98c4d1859a318e7586f87031db44b215476020Dan Gohman if (ConstantInt *CI = 561ff26d4e9ceabb48463cc1aaeccfd1784fb52f755Dan Gohman dyn_cast<ConstantInt>(findValue(I.getIndexOperand(), 562ff26d4e9ceabb48463cc1aaeccfd1784fb52f755Dan Gohman /*OffsetOk=*/false))) 563dd98c4d1859a318e7586f87031db44b215476020Dan Gohman Assert1(CI->getValue().ult(I.getVectorOperandType()->getNumElements()), 564be02b20a8f9e9503733df945968e48562714dd32Dan Gohman "Undefined result: extractelement index out of range", &I); 565dd98c4d1859a318e7586f87031db44b215476020Dan Gohman} 566dd98c4d1859a318e7586f87031db44b215476020Dan Gohman 567dd98c4d1859a318e7586f87031db44b215476020Dan Gohmanvoid Lint::visitInsertElementInst(InsertElementInst &I) { 568dd98c4d1859a318e7586f87031db44b215476020Dan Gohman if (ConstantInt *CI = 569ff26d4e9ceabb48463cc1aaeccfd1784fb52f755Dan Gohman dyn_cast<ConstantInt>(findValue(I.getOperand(2), 570ff26d4e9ceabb48463cc1aaeccfd1784fb52f755Dan Gohman /*OffsetOk=*/false))) 571dd98c4d1859a318e7586f87031db44b215476020Dan Gohman Assert1(CI->getValue().ult(I.getType()->getNumElements()), 572be02b20a8f9e9503733df945968e48562714dd32Dan Gohman "Undefined result: insertelement index out of range", &I); 573be02b20a8f9e9503733df945968e48562714dd32Dan Gohman} 574be02b20a8f9e9503733df945968e48562714dd32Dan Gohman 575be02b20a8f9e9503733df945968e48562714dd32Dan Gohmanvoid Lint::visitUnreachableInst(UnreachableInst &I) { 576be02b20a8f9e9503733df945968e48562714dd32Dan Gohman // This isn't undefined behavior, it's merely suspicious. 577be02b20a8f9e9503733df945968e48562714dd32Dan Gohman Assert1(&I == I.getParent()->begin() || 578be02b20a8f9e9503733df945968e48562714dd32Dan Gohman prior(BasicBlock::iterator(&I))->mayHaveSideEffects(), 579be02b20a8f9e9503733df945968e48562714dd32Dan Gohman "Unusual: unreachable immediately preceded by instruction without " 580be02b20a8f9e9503733df945968e48562714dd32Dan Gohman "side effects", &I); 581dd98c4d1859a318e7586f87031db44b215476020Dan Gohman} 582dd98c4d1859a318e7586f87031db44b215476020Dan Gohman 583ff26d4e9ceabb48463cc1aaeccfd1784fb52f755Dan Gohman/// findValue - Look through bitcasts and simple memory reference patterns 584ff26d4e9ceabb48463cc1aaeccfd1784fb52f755Dan Gohman/// to identify an equivalent, but more informative, value. If OffsetOk 585ff26d4e9ceabb48463cc1aaeccfd1784fb52f755Dan Gohman/// is true, look through getelementptrs with non-zero offsets too. 586ff26d4e9ceabb48463cc1aaeccfd1784fb52f755Dan Gohman/// 587ff26d4e9ceabb48463cc1aaeccfd1784fb52f755Dan Gohman/// Most analysis passes don't require this logic, because instcombine 588ff26d4e9ceabb48463cc1aaeccfd1784fb52f755Dan Gohman/// will simplify most of these kinds of things away. But it's a goal of 589ff26d4e9ceabb48463cc1aaeccfd1784fb52f755Dan Gohman/// this Lint pass to be useful even on non-optimized IR. 590ff26d4e9ceabb48463cc1aaeccfd1784fb52f755Dan GohmanValue *Lint::findValue(Value *V, bool OffsetOk) const { 59117d95965cbf529f96277130b75c018f5f3873b66Dan Gohman SmallPtrSet<Value *, 4> Visited; 59217d95965cbf529f96277130b75c018f5f3873b66Dan Gohman return findValueImpl(V, OffsetOk, Visited); 59317d95965cbf529f96277130b75c018f5f3873b66Dan Gohman} 59417d95965cbf529f96277130b75c018f5f3873b66Dan Gohman 59517d95965cbf529f96277130b75c018f5f3873b66Dan Gohman/// findValueImpl - Implementation helper for findValue. 59617d95965cbf529f96277130b75c018f5f3873b66Dan GohmanValue *Lint::findValueImpl(Value *V, bool OffsetOk, 59717d95965cbf529f96277130b75c018f5f3873b66Dan Gohman SmallPtrSet<Value *, 4> &Visited) const { 59817d95965cbf529f96277130b75c018f5f3873b66Dan Gohman // Detect self-referential values. 59917d95965cbf529f96277130b75c018f5f3873b66Dan Gohman if (!Visited.insert(V)) 60017d95965cbf529f96277130b75c018f5f3873b66Dan Gohman return UndefValue::get(V->getType()); 60117d95965cbf529f96277130b75c018f5f3873b66Dan Gohman 602ff26d4e9ceabb48463cc1aaeccfd1784fb52f755Dan Gohman // TODO: Look through sext or zext cast, when the result is known to 603ff26d4e9ceabb48463cc1aaeccfd1784fb52f755Dan Gohman // be interpreted as signed or unsigned, respectively. 604aec2a0dbce170c658af428e76187e4361a4a1caaDan Gohman // TODO: Look through eliminable cast pairs. 605ff26d4e9ceabb48463cc1aaeccfd1784fb52f755Dan Gohman // TODO: Look through calls with unique return values. 606ff26d4e9ceabb48463cc1aaeccfd1784fb52f755Dan Gohman // TODO: Look through vector insert/extract/shuffle. 607bd1801b5553c8be3960255a92738464e0010b6f6Dan Gohman V = OffsetOk ? GetUnderlyingObject(V, TD) : V->stripPointerCasts(); 608ff26d4e9ceabb48463cc1aaeccfd1784fb52f755Dan Gohman if (LoadInst *L = dyn_cast<LoadInst>(V)) { 609ff26d4e9ceabb48463cc1aaeccfd1784fb52f755Dan Gohman BasicBlock::iterator BBI = L; 610ff26d4e9ceabb48463cc1aaeccfd1784fb52f755Dan Gohman BasicBlock *BB = L->getParent(); 61113ec30b6a1184c590ed93d81764a0314202abeafDan Gohman SmallPtrSet<BasicBlock *, 4> VisitedBlocks; 612ff26d4e9ceabb48463cc1aaeccfd1784fb52f755Dan Gohman for (;;) { 61313ec30b6a1184c590ed93d81764a0314202abeafDan Gohman if (!VisitedBlocks.insert(BB)) break; 614ff26d4e9ceabb48463cc1aaeccfd1784fb52f755Dan Gohman if (Value *U = FindAvailableLoadedValue(L->getPointerOperand(), 615ff26d4e9ceabb48463cc1aaeccfd1784fb52f755Dan Gohman BB, BBI, 6, AA)) 61617d95965cbf529f96277130b75c018f5f3873b66Dan Gohman return findValueImpl(U, OffsetOk, Visited); 61713ec30b6a1184c590ed93d81764a0314202abeafDan Gohman if (BBI != BB->begin()) break; 61813ec30b6a1184c590ed93d81764a0314202abeafDan Gohman BB = BB->getUniquePredecessor(); 619ff26d4e9ceabb48463cc1aaeccfd1784fb52f755Dan Gohman if (!BB) break; 620ff26d4e9ceabb48463cc1aaeccfd1784fb52f755Dan Gohman BBI = BB->end(); 621ff26d4e9ceabb48463cc1aaeccfd1784fb52f755Dan Gohman } 622aec2a0dbce170c658af428e76187e4361a4a1caaDan Gohman } else if (PHINode *PN = dyn_cast<PHINode>(V)) { 623ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands if (Value *W = PN->hasConstantValue()) 62423a19572b2839ee3a6a3520d60d62a465cec7d53Duncan Sands if (W != V) 62523a19572b2839ee3a6a3520d60d62a465cec7d53Duncan Sands return findValueImpl(W, OffsetOk, Visited); 626ff26d4e9ceabb48463cc1aaeccfd1784fb52f755Dan Gohman } else if (CastInst *CI = dyn_cast<CastInst>(V)) { 627ece6c6bb6329748b92403c06ac87f45c43485911Chandler Carruth if (CI->isNoopCast(TD ? TD->getIntPtrType(V->getContext()) : 628ece6c6bb6329748b92403c06ac87f45c43485911Chandler Carruth Type::getInt64Ty(V->getContext()))) 62917d95965cbf529f96277130b75c018f5f3873b66Dan Gohman return findValueImpl(CI->getOperand(0), OffsetOk, Visited); 630ff26d4e9ceabb48463cc1aaeccfd1784fb52f755Dan Gohman } else if (ExtractValueInst *Ex = dyn_cast<ExtractValueInst>(V)) { 631ff26d4e9ceabb48463cc1aaeccfd1784fb52f755Dan Gohman if (Value *W = FindInsertedValue(Ex->getAggregateOperand(), 632fc6d3a49867cd38954dc40936a88f1907252c6d2Jay Foad Ex->getIndices())) 633ff26d4e9ceabb48463cc1aaeccfd1784fb52f755Dan Gohman if (W != V) 63417d95965cbf529f96277130b75c018f5f3873b66Dan Gohman return findValueImpl(W, OffsetOk, Visited); 635aec2a0dbce170c658af428e76187e4361a4a1caaDan Gohman } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) { 636aec2a0dbce170c658af428e76187e4361a4a1caaDan Gohman // Same as above, but for ConstantExpr instead of Instruction. 637aec2a0dbce170c658af428e76187e4361a4a1caaDan Gohman if (Instruction::isCast(CE->getOpcode())) { 638aec2a0dbce170c658af428e76187e4361a4a1caaDan Gohman if (CastInst::isNoopCast(Instruction::CastOps(CE->getOpcode()), 639aec2a0dbce170c658af428e76187e4361a4a1caaDan Gohman CE->getOperand(0)->getType(), 640aec2a0dbce170c658af428e76187e4361a4a1caaDan Gohman CE->getType(), 641ece6c6bb6329748b92403c06ac87f45c43485911Chandler Carruth TD ? TD->getIntPtrType(V->getContext()) : 642aec2a0dbce170c658af428e76187e4361a4a1caaDan Gohman Type::getInt64Ty(V->getContext()))) 643aec2a0dbce170c658af428e76187e4361a4a1caaDan Gohman return findValueImpl(CE->getOperand(0), OffsetOk, Visited); 644aec2a0dbce170c658af428e76187e4361a4a1caaDan Gohman } else if (CE->getOpcode() == Instruction::ExtractValue) { 645d30aa5a1edac5256573e8d76dd155df3d3fdec84Jay Foad ArrayRef<unsigned> Indices = CE->getIndices(); 646fc6d3a49867cd38954dc40936a88f1907252c6d2Jay Foad if (Value *W = FindInsertedValue(CE->getOperand(0), Indices)) 647aec2a0dbce170c658af428e76187e4361a4a1caaDan Gohman if (W != V) 648aec2a0dbce170c658af428e76187e4361a4a1caaDan Gohman return findValueImpl(W, OffsetOk, Visited); 649aec2a0dbce170c658af428e76187e4361a4a1caaDan Gohman } 650ff26d4e9ceabb48463cc1aaeccfd1784fb52f755Dan Gohman } 651ff26d4e9ceabb48463cc1aaeccfd1784fb52f755Dan Gohman 652ff26d4e9ceabb48463cc1aaeccfd1784fb52f755Dan Gohman // As a last resort, try SimplifyInstruction or constant folding. 653ff26d4e9ceabb48463cc1aaeccfd1784fb52f755Dan Gohman if (Instruction *Inst = dyn_cast<Instruction>(V)) { 654618c1dbd293d15ee19f61b1156ab8086ad28311aChad Rosier if (Value *W = SimplifyInstruction(Inst, TD, TLI, DT)) 655d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands return findValueImpl(W, OffsetOk, Visited); 656ff26d4e9ceabb48463cc1aaeccfd1784fb52f755Dan Gohman } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) { 657aab8e28d5e470711d80276bbf717408c3ab966fdChad Rosier if (Value *W = ConstantFoldConstantExpression(CE, TD, TLI)) 658ff26d4e9ceabb48463cc1aaeccfd1784fb52f755Dan Gohman if (W != V) 65917d95965cbf529f96277130b75c018f5f3873b66Dan Gohman return findValueImpl(W, OffsetOk, Visited); 660ff26d4e9ceabb48463cc1aaeccfd1784fb52f755Dan Gohman } 661ff26d4e9ceabb48463cc1aaeccfd1784fb52f755Dan Gohman 662ff26d4e9ceabb48463cc1aaeccfd1784fb52f755Dan Gohman return V; 663ff26d4e9ceabb48463cc1aaeccfd1784fb52f755Dan Gohman} 664ff26d4e9ceabb48463cc1aaeccfd1784fb52f755Dan Gohman 665113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman//===----------------------------------------------------------------------===// 666113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman// Implement the public interfaces to this file... 667113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman//===----------------------------------------------------------------------===// 668113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman 669113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan GohmanFunctionPass *llvm::createLintPass() { 670113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman return new Lint(); 671113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman} 672113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman 673113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman/// lintFunction - Check a function for errors, printing messages on stderr. 674113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman/// 675113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohmanvoid llvm::lintFunction(const Function &f) { 676113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman Function &F = const_cast<Function&>(f); 677113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman assert(!F.isDeclaration() && "Cannot lint external functions"); 678113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman 679113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman FunctionPassManager FPM(F.getParent()); 680113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman Lint *V = new Lint(); 681113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman FPM.add(V); 682113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman FPM.run(F); 683113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman} 684113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman 685113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman/// lintModule - Check a module for errors, printing messages on stderr. 686113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman/// 687a0f7ff334f86926356491ec78ab3066247dc93b1Dan Gohmanvoid llvm::lintModule(const Module &M) { 688113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman PassManager PM; 689113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman Lint *V = new Lint(); 690113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman PM.add(V); 691113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman PM.run(const_cast<Module&>(M)); 692113902e9fba5f4baf3de3c6ac0241d49ffdfa55cDan Gohman} 693