X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FVMCore%2FVerifier.cpp;h=cf812a8fffefe30f8622cc965e540d1db7b6c580;hb=e81561909d128c6e2d8033cb5465a49b2596b26a;hp=a9bcbd5f8f278186151d6c1360d9b73e28638ec1;hpb=30768ac3c2395d5b2047ec84e1b8f4330ba2658f;p=oota-llvm.git diff --git a/lib/VMCore/Verifier.cpp b/lib/VMCore/Verifier.cpp index a9bcbd5f8f2..cf812a8fffe 100644 --- a/lib/VMCore/Verifier.cpp +++ b/lib/VMCore/Verifier.cpp @@ -1,25 +1,25 @@ //===-- Verifier.cpp - Implement the Module Verifier -------------*- C++ -*-==// -// +// // The LLVM Compiler Infrastructure // // This file was developed by the LLVM research group and is distributed under // the University of Illinois Open Source License. See LICENSE.TXT for details. -// +// //===----------------------------------------------------------------------===// // // This file defines the function verifier interface, that can be used for some // sanity checking of input to the system. // -// Note that this does not provide full 'java style' security and verifications, -// instead it just tries to ensure that code is well formed. +// Note that this does not provide full `Java style' security and verifications, +// instead it just tries to ensure that code is well-formed. // -// * Both of a binary operator's parameters are the same type +// * Both of a binary operator's parameters are of the same type // * Verify that the indices of mem access instructions match other operands -// * Verify that arithmetic and other things are only performed on first class +// * Verify that arithmetic and other things are only performed on first-class // types. Verify that shifts & logicals only happen on integrals f.e. -// . All of the constants in a switch statement are of the correct type +// * All of the constants in a switch statement are of the correct type // * The code is in valid SSA form -// . It should be illegal to put a label into any other type (like a structure) +// * It should be illegal to put a label into any other type (like a structure) // or to return one. [except constant arrays!] // * Only phi nodes can be self referential: 'add int %0, %0 ; :0' is bad // * PHI nodes must have an entry for each predecessor, with no extras. @@ -28,7 +28,7 @@ // * All basic blocks should only end with terminator insts, not contain them // * The entry node to a function must not have predecessors // * All Instructions must be embedded into a basic block -// . Function's cannot take a void typed parameter +// * Functions cannot take a void-typed parameter // * Verify that a function's argument list agrees with it's declared type. // * It is illegal to specify a name for a void value. // * It is illegal to have a internal global value with no initializer @@ -41,37 +41,59 @@ #include "llvm/Analysis/Verifier.h" #include "llvm/Assembly/Writer.h" +#include "llvm/CallingConv.h" +#include "llvm/Constants.h" #include "llvm/Pass.h" #include "llvm/Module.h" +#include "llvm/ModuleProvider.h" #include "llvm/DerivedTypes.h" -#include "llvm/iPHINode.h" -#include "llvm/iTerminators.h" -#include "llvm/iOther.h" -#include "llvm/iOperators.h" -#include "llvm/iMemory.h" -#include "llvm/SymbolTable.h" -#include "llvm/PassManager.h" +#include "llvm/InlineAsm.h" +#include "llvm/Instructions.h" #include "llvm/Intrinsics.h" +#include "llvm/PassManager.h" +#include "llvm/SymbolTable.h" #include "llvm/Analysis/Dominators.h" #include "llvm/Support/CFG.h" #include "llvm/Support/InstVisitor.h" -#include "Support/STLExtras.h" +#include "llvm/Support/Streams.h" +#include "llvm/ADT/StringExtras.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/Support/Compiler.h" #include +#include using namespace llvm; namespace { // Anonymous namespace for class - struct Verifier : public FunctionPass, InstVisitor { + struct VISIBILITY_HIDDEN + Verifier : public FunctionPass, InstVisitor { bool Broken; // Is this module found to be broken? bool RealPass; // Are we not being run by a PassManager? - bool AbortBroken; // If broken, should it or should it not abort? - Module *Mod; // Module we are verifying right now - DominatorSet *DS; // Dominator set, caution can be null! - - Verifier() : Broken(false), RealPass(true), AbortBroken(true), DS(0) {} - Verifier(bool AB) : Broken(false), RealPass(true), AbortBroken(AB), DS(0) {} - Verifier(DominatorSet &ds) - : Broken(false), RealPass(false), AbortBroken(false), DS(&ds) {} + VerifierFailureAction action; + // What to do if verification fails. + Module *Mod; // Module we are verifying right now + ETForest *EF; // ET-Forest, caution can be null! + std::stringstream msgs; // A stringstream to collect messages + + /// InstInThisBlock - when verifying a basic block, keep track of all of the + /// instructions we have seen so far. This allows us to do efficient + /// dominance checks for the case when an instruction has an operand that is + /// an instruction in the same block. + std::set InstsInThisBlock; + + Verifier() + : Broken(false), RealPass(true), action(AbortProcessAction), + EF(0), msgs( std::ios::app | std::ios::out ) {} + Verifier( VerifierFailureAction ctn ) + : Broken(false), RealPass(true), action(ctn), EF(0), + msgs( std::ios::app | std::ios::out ) {} + Verifier(bool AB ) + : Broken(false), RealPass(true), + action( AB ? AbortProcessAction : PrintMessageAction), EF(0), + msgs( std::ios::app | std::ios::out ) {} + Verifier(ETForest &ef) + : Broken(false), RealPass(false), action(PrintMessageAction), + EF(&ef), msgs( std::ios::app | std::ios::out ) {} bool doInitialization(Module &M) { @@ -81,66 +103,99 @@ namespace { // Anonymous namespace for class // If this is a real pass, in a pass manager, we must abort before // returning back to the pass manager, or else the pass manager may try to // run other passes on the broken module. - // if (RealPass) - abortIfBroken(); + return abortIfBroken(); return false; } bool runOnFunction(Function &F) { // Get dominator information if we are being run by PassManager - if (RealPass) DS = &getAnalysis(); + if (RealPass) EF = &getAnalysis(); visit(F); + InstsInThisBlock.clear(); // If this is a real pass, in a pass manager, we must abort before // returning back to the pass manager, or else the pass manager may try to // run other passes on the broken module. - // if (RealPass) - abortIfBroken(); + return abortIfBroken(); return false; } bool doFinalization(Module &M) { // Scan through, checking all of the external function's linkage now... - for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) + for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) { visitGlobalValue(*I); - for (Module::giterator I = M.gbegin(), E = M.gend(); I != E; ++I) - visitGlobalValue(*I); + // Check to make sure function prototypes are okay. + if (I->isExternal()) visitFunction(*I); + } + + for (Module::global_iterator I = M.global_begin(), E = M.global_end(); + I != E; ++I) + visitGlobalVariable(*I); // If the module is broken, abort at this time. - abortIfBroken(); - return false; + return abortIfBroken(); } virtual void getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesAll(); if (RealPass) - AU.addRequired(); + AU.addRequired(); } - // abortIfBroken - If the module is broken and we are supposed to abort on - // this condition, do so. - // - void abortIfBroken() const { - if (Broken && AbortBroken) { - std::cerr << "Broken module found, compilation aborted!\n"; - abort(); + /// abortIfBroken - If the module is broken and we are supposed to abort on + /// this condition, do so. + /// + bool abortIfBroken() { + if (Broken) { + msgs << "Broken module found, "; + switch (action) { + case AbortProcessAction: + msgs << "compilation aborted!\n"; + cerr << msgs.str(); + abort(); + case PrintMessageAction: + msgs << "verification continues.\n"; + cerr << msgs.str(); + return false; + case ReturnStatusAction: + msgs << "compilation terminated.\n"; + return Broken; + } } + return false; } // Verification methods... void verifySymbolTable(SymbolTable &ST); void visitGlobalValue(GlobalValue &GV); + void visitGlobalVariable(GlobalVariable &GV); void visitFunction(Function &F); void visitBasicBlock(BasicBlock &BB); + void visitTruncInst(TruncInst &I); + void visitZExtInst(ZExtInst &I); + void visitSExtInst(SExtInst &I); + void visitFPTruncInst(FPTruncInst &I); + void visitFPExtInst(FPExtInst &I); + void visitFPToUIInst(FPToUIInst &I); + void visitFPToSIInst(FPToSIInst &I); + void visitUIToFPInst(UIToFPInst &I); + void visitSIToFPInst(SIToFPInst &I); + void visitIntToPtrInst(IntToPtrInst &I); + void visitPtrToIntInst(PtrToIntInst &I); + void visitBitCastInst(BitCastInst &I); void visitPHINode(PHINode &PN); void visitBinaryOperator(BinaryOperator &B); + void visitICmpInst(ICmpInst &IC); + void visitFCmpInst(FCmpInst &FC); void visitShiftInst(ShiftInst &SI); - void visitVANextInst(VANextInst &VAN) { visitInstruction(VAN); } + void visitExtractElementInst(ExtractElementInst &EI); + void visitInsertElementInst(InsertElementInst &EI); + void visitShuffleVectorInst(ShuffleVectorInst &EI); void visitVAArgInst(VAArgInst &VAA) { visitInstruction(VAA); } void visitCallInst(CallInst &CI); void visitGetElementPtrInst(GetElementPtrInst &GEP); @@ -149,41 +204,55 @@ namespace { // Anonymous namespace for class void visitInstruction(Instruction &I); void visitTerminatorInst(TerminatorInst &I); void visitReturnInst(ReturnInst &RI); + void visitSwitchInst(SwitchInst &SI); + void visitSelectInst(SelectInst &SI); void visitUserOp1(Instruction &I); void visitUserOp2(Instruction &I) { visitUserOp1(I); } void visitIntrinsicFunctionCall(Intrinsic::ID ID, CallInst &CI); + void VerifyIntrinsicPrototype(Function *F, ...); void WriteValue(const Value *V) { if (!V) return; if (isa(V)) { - std::cerr << *V; - } else if (const Type *Ty = dyn_cast(V)) { - WriteTypeSymbolic(std::cerr, Ty, Mod); + msgs << *V; } else { - WriteAsOperand (std::cerr, V, true, true, Mod); - std::cerr << "\n"; + WriteAsOperand(msgs, V, true, Mod); + msgs << "\n"; } } + void WriteType(const Type* T ) { + if ( !T ) return; + WriteTypeSymbolic(msgs, T, Mod ); + } + // CheckFailed - A check failed, so print out the condition and the message // that failed. This provides a nice place to put a breakpoint if you want // to see why something is not correct. - // void CheckFailed(const std::string &Message, const Value *V1 = 0, const Value *V2 = 0, const Value *V3 = 0, const Value *V4 = 0) { - std::cerr << Message << "\n"; + msgs << Message << "\n"; WriteValue(V1); WriteValue(V2); WriteValue(V3); WriteValue(V4); Broken = true; } + + void CheckFailed( const std::string& Message, const Value* V1, + const Type* T2, const Value* V3 = 0 ) { + msgs << Message << "\n"; + WriteValue(V1); + WriteType(T2); + WriteValue(V3); + Broken = true; + } }; - RegisterOpt X("verify", "Module Verifier"); + RegisterPass X("verify", "Module Verifier"); } // End anonymous namespace @@ -201,8 +270,16 @@ namespace { // Anonymous namespace for class void Verifier::visitGlobalValue(GlobalValue &GV) { - Assert1(!GV.isExternal() || GV.hasExternalLinkage(), - "Global is external, but doesn't have external linkage!", &GV); + Assert1(!GV.isExternal() || + GV.hasExternalLinkage() || + GV.hasDLLImportLinkage() || + GV.hasExternalWeakLinkage(), + "Global is external, but doesn't have external or dllimport or weak linkage!", + &GV); + + Assert1(!GV.hasDLLImportLinkage() || GV.isExternal(), + "Global is marked as dllimport, but not external", &GV); + Assert1(!GV.hasAppendingLinkage() || isa(GV), "Only global variables can have appending linkage!", &GV); @@ -213,28 +290,38 @@ void Verifier::visitGlobalValue(GlobalValue &GV) { } } +void Verifier::visitGlobalVariable(GlobalVariable &GV) { + if (GV.hasInitializer()) + Assert1(GV.getInitializer()->getType() == GV.getType()->getElementType(), + "Global variable initializer type does not match global " + "variable type!", &GV); + + visitGlobalValue(GV); +} + + // verifySymbolTable - Verify that a function or module symbol table is ok // void Verifier::verifySymbolTable(SymbolTable &ST) { - // Loop over all of the types in the symbol table... - for (SymbolTable::iterator TI = ST.begin(), TE = ST.end(); TI != TE; ++TI) - for (SymbolTable::type_iterator I = TI->second.begin(), - E = TI->second.end(); I != E; ++I) { - Value *V = I->second; + // Loop over all of the values in all type planes in the symbol table. + for (SymbolTable::plane_const_iterator PI = ST.plane_begin(), + PE = ST.plane_end(); PI != PE; ++PI) + for (SymbolTable::value_const_iterator VI = PI->second.begin(), + VE = PI->second.end(); VI != VE; ++VI) { + Value *V = VI->second; // Check that there are no void typed values in the symbol table. Values // with a void type cannot be put into symbol tables because they cannot // have names! Assert1(V->getType() != Type::VoidTy, - "Values with void type are not allowed to have names!", V); + "Values with void type are not allowed to have names!", V); } } - // visitFunction - Verify that a function is ok. // void Verifier::visitFunction(Function &F) { - // Check function arguments... + // Check function arguments. const FunctionType *FT = F.getFunctionType(); unsigned NumArgs = F.getArgumentList().size(); @@ -245,12 +332,35 @@ void Verifier::visitFunction(Function &F) { F.getReturnType() == Type::VoidTy, "Functions cannot return aggregate values!", &F); + // Check that this function meets the restrictions on this calling convention. + switch (F.getCallingConv()) { + default: + break; + case CallingConv::C: + break; + case CallingConv::CSRet: + Assert1(FT->getReturnType() == Type::VoidTy && + FT->getNumParams() > 0 && isa(FT->getParamType(0)), + "Invalid struct-return function!", &F); + break; + case CallingConv::Fast: + case CallingConv::Cold: + case CallingConv::X86_FastCall: + Assert1(!F.isVarArg(), + "Varargs functions must have C calling conventions!", &F); + break; + } + // Check that the argument values match the function type for this function... unsigned i = 0; - for (Function::aiterator I = F.abegin(), E = F.aend(); I != E; ++I, ++i) + for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I, ++i) { Assert2(I->getType() == FT->getParamType(i), "Argument value does not match function argument type!", I, FT->getParamType(i)); + // Make sure no aggregates are passed by value. + Assert1(I->getType()->isFirstClassType(), + "Functions cannot take aggregates as arguments by value!", I); + } if (!F.isExternal()) { verifySymbolTable(F.getSymbolTable()); @@ -266,26 +376,27 @@ void Verifier::visitFunction(Function &F) { // verifyBasicBlock - Verify that a basic block is well formed... // void Verifier::visitBasicBlock(BasicBlock &BB) { + InstsInThisBlock.clear(); + + // Ensure that basic blocks have terminators! + Assert1(BB.getTerminator(), "Basic Block does not have terminator!", &BB); + // Check constraints that this basic block imposes on all of the PHI nodes in // it. if (isa(BB.front())) { std::vector Preds(pred_begin(&BB), pred_end(&BB)); std::sort(Preds.begin(), Preds.end()); - - for (BasicBlock::iterator I = BB.begin(); - PHINode *PN = dyn_cast(I); ++I) { + PHINode *PN; + for (BasicBlock::iterator I = BB.begin(); (PN = dyn_cast(I));++I) { // Ensure that PHI nodes have at least one entry! Assert1(PN->getNumIncomingValues() != 0, "PHI nodes must have at least one entry. If the block is dead, " "the PHI should be removed!", PN); - Assert1(PN->getNumIncomingValues() >= Preds.size(), - "PHINode has more entries than the basic block has predecessors!", - PN); - Assert1(PN->getNumIncomingValues() <= Preds.size(), - "PHINode has less entries than the basic block has predecessors!", - PN); - + Assert1(PN->getNumIncomingValues() == Preds.size(), + "PHINode should have one entry for each predecessor of its " + "parent basic block!", PN); + // Get and sort all incoming values in the PHI node... std::vector > Values; Values.reserve(PN->getNumIncomingValues()); @@ -293,7 +404,7 @@ void Verifier::visitBasicBlock(BasicBlock &BB) { Values.push_back(std::make_pair(PN->getIncomingBlock(i), PN->getIncomingValue(i))); std::sort(Values.begin(), Values.end()); - + for (unsigned i = 0, e = Values.size(); i != e; ++i) { // Check to make sure that if there is more than one entry for a // particular basic block in this PHI node, that the incoming values are @@ -304,18 +415,15 @@ void Verifier::visitBasicBlock(BasicBlock &BB) { "PHI node has multiple entries for the same basic block with " "different incoming values!", PN, Values[i].first, Values[i].second, Values[i-1].second); - + // Check to make sure that the predecessors and PHI node entries are // matched up. Assert3(Values[i].first == Preds[i], "PHI node entries do not match predecessors!", PN, - Values[i].first, Preds[i]); + Values[i].first, Preds[i]); } } } - - // Ensure that basic blocks have terminators! - Assert1(BB.getTerminator(), "Basic Block does not have terminator!", &BB); } void Verifier::visitTerminatorInst(TerminatorInst &I) { @@ -328,9 +436,9 @@ void Verifier::visitTerminatorInst(TerminatorInst &I) { void Verifier::visitReturnInst(ReturnInst &RI) { Function *F = RI.getParent()->getParent(); if (RI.getNumOperands() == 0) - Assert1(F->getReturnType() == Type::VoidTy, - "Function returns no value, but ret instruction found that does!", - &RI); + Assert2(F->getReturnType() == Type::VoidTy, + "Found return instr that returns void in Function of non-void " + "return type!", &RI, F->getReturnType()); else Assert2(F->getReturnType() == RI.getOperand(0)->getType(), "Function return type does not match operand " @@ -341,15 +449,200 @@ void Verifier::visitReturnInst(ReturnInst &RI) { visitTerminatorInst(RI); } -// visitUserOp1 - User defined operators shouldn't live beyond the lifetime of a -// pass, if any exist, it's an error. -// +void Verifier::visitSwitchInst(SwitchInst &SI) { + // Check to make sure that all of the constants in the switch instruction + // have the same type as the switched-on value. + const Type *SwitchTy = SI.getCondition()->getType(); + for (unsigned i = 1, e = SI.getNumCases(); i != e; ++i) + Assert1(SI.getCaseValue(i)->getType() == SwitchTy, + "Switch constants must all be same type as switch value!", &SI); + + visitTerminatorInst(SI); +} + +void Verifier::visitSelectInst(SelectInst &SI) { + Assert1(SI.getCondition()->getType() == Type::BoolTy, + "Select condition type must be bool!", &SI); + Assert1(SI.getTrueValue()->getType() == SI.getFalseValue()->getType(), + "Select values must have identical types!", &SI); + Assert1(SI.getTrueValue()->getType() == SI.getType(), + "Select values must have same type as select instruction!", &SI); + visitInstruction(SI); +} + + +/// visitUserOp1 - User defined operators shouldn't live beyond the lifetime of +/// a pass, if any exist, it's an error. +/// void Verifier::visitUserOp1(Instruction &I) { - Assert1(0, "User-defined operators should not live outside of a pass!", - &I); + Assert1(0, "User-defined operators should not live outside of a pass!", &I); +} + +void Verifier::visitTruncInst(TruncInst &I) { + // Get the source and destination types + const Type *SrcTy = I.getOperand(0)->getType(); + const Type *DestTy = I.getType(); + + // Get the size of the types in bits, we'll need this later + unsigned SrcBitSize = SrcTy->getPrimitiveSizeInBits(); + unsigned DestBitSize = DestTy->getPrimitiveSizeInBits(); + + Assert1(SrcTy->isIntegral(), "Trunc only operates on integer", &I); + Assert1(DestTy->isIntegral(),"Trunc only produces integral", &I); + Assert1(SrcBitSize > DestBitSize,"DestTy too big for Trunc", &I); + + visitInstruction(I); +} + +void Verifier::visitZExtInst(ZExtInst &I) { + // Get the source and destination types + const Type *SrcTy = I.getOperand(0)->getType(); + const Type *DestTy = I.getType(); + + // Get the size of the types in bits, we'll need this later + unsigned SrcBitSize = SrcTy->getPrimitiveSizeInBits(); + unsigned DestBitSize = DestTy->getPrimitiveSizeInBits(); + + Assert1(SrcTy->isIntegral(),"ZExt only operates on integral", &I); + Assert1(DestTy->isInteger(),"ZExt only produces an integer", &I); + Assert1(SrcBitSize < DestBitSize,"Type too small for ZExt", &I); + + visitInstruction(I); } -// visitPHINode - Ensure that a PHI node is well formed. +void Verifier::visitSExtInst(SExtInst &I) { + // Get the source and destination types + const Type *SrcTy = I.getOperand(0)->getType(); + const Type *DestTy = I.getType(); + + // Get the size of the types in bits, we'll need this later + unsigned SrcBitSize = SrcTy->getPrimitiveSizeInBits(); + unsigned DestBitSize = DestTy->getPrimitiveSizeInBits(); + + Assert1(SrcTy->isIntegral(),"SExt only operates on integral", &I); + Assert1(DestTy->isInteger(),"SExt only produces an integer", &I); + Assert1(SrcBitSize < DestBitSize,"Type too small for SExt", &I); + + visitInstruction(I); +} + +void Verifier::visitFPTruncInst(FPTruncInst &I) { + // Get the source and destination types + const Type *SrcTy = I.getOperand(0)->getType(); + const Type *DestTy = I.getType(); + // Get the size of the types in bits, we'll need this later + unsigned SrcBitSize = SrcTy->getPrimitiveSizeInBits(); + unsigned DestBitSize = DestTy->getPrimitiveSizeInBits(); + + Assert1(SrcTy->isFloatingPoint(),"FPTrunc only operates on FP", &I); + Assert1(DestTy->isFloatingPoint(),"FPTrunc only produces an FP", &I); + Assert1(SrcBitSize > DestBitSize,"DestTy too big for FPTrunc", &I); + + visitInstruction(I); +} + +void Verifier::visitFPExtInst(FPExtInst &I) { + // Get the source and destination types + const Type *SrcTy = I.getOperand(0)->getType(); + const Type *DestTy = I.getType(); + + // Get the size of the types in bits, we'll need this later + unsigned SrcBitSize = SrcTy->getPrimitiveSizeInBits(); + unsigned DestBitSize = DestTy->getPrimitiveSizeInBits(); + + Assert1(SrcTy->isFloatingPoint(),"FPExt only operates on FP", &I); + Assert1(DestTy->isFloatingPoint(),"FPExt only produces an FP", &I); + Assert1(SrcBitSize < DestBitSize,"DestTy too small for FPExt", &I); + + visitInstruction(I); +} + +void Verifier::visitUIToFPInst(UIToFPInst &I) { + // Get the source and destination types + const Type *SrcTy = I.getOperand(0)->getType(); + const Type *DestTy = I.getType(); + + Assert1(SrcTy->isIntegral(),"UInt2FP source must be integral", &I); + Assert1(DestTy->isFloatingPoint(),"UInt2FP result must be FP", &I); + + visitInstruction(I); +} + +void Verifier::visitSIToFPInst(SIToFPInst &I) { + // Get the source and destination types + const Type *SrcTy = I.getOperand(0)->getType(); + const Type *DestTy = I.getType(); + + Assert1(SrcTy->isIntegral(),"SInt2FP source must be integral", &I); + Assert1(DestTy->isFloatingPoint(),"SInt2FP result must be FP", &I); + + visitInstruction(I); +} + +void Verifier::visitFPToUIInst(FPToUIInst &I) { + // Get the source and destination types + const Type *SrcTy = I.getOperand(0)->getType(); + const Type *DestTy = I.getType(); + + Assert1(SrcTy->isFloatingPoint(),"FP2UInt source must be FP", &I); + Assert1(DestTy->isIntegral(),"FP2UInt result must be integral", &I); + + visitInstruction(I); +} + +void Verifier::visitFPToSIInst(FPToSIInst &I) { + // Get the source and destination types + const Type *SrcTy = I.getOperand(0)->getType(); + const Type *DestTy = I.getType(); + + Assert1(SrcTy->isFloatingPoint(),"FPToSI source must be FP", &I); + Assert1(DestTy->isIntegral(),"FP2ToI result must be integral", &I); + + visitInstruction(I); +} + +void Verifier::visitPtrToIntInst(PtrToIntInst &I) { + // Get the source and destination types + const Type *SrcTy = I.getOperand(0)->getType(); + const Type *DestTy = I.getType(); + + Assert1(isa(SrcTy), "PtrToInt source must be pointer", &I); + Assert1(DestTy->isIntegral(), "PtrToInt result must be integral", &I); + + visitInstruction(I); +} + +void Verifier::visitIntToPtrInst(IntToPtrInst &I) { + // Get the source and destination types + const Type *SrcTy = I.getOperand(0)->getType(); + const Type *DestTy = I.getType(); + + Assert1(SrcTy->isIntegral(), "IntToPtr source must be an integral", &I); + Assert1(isa(DestTy), "IntToPtr result must be a pointer",&I); + + visitInstruction(I); +} + +void Verifier::visitBitCastInst(BitCastInst &I) { + // Get the source and destination types + const Type *SrcTy = I.getOperand(0)->getType(); + const Type *DestTy = I.getType(); + + // Get the size of the types in bits, we'll need this later + unsigned SrcBitSize = SrcTy->getPrimitiveSizeInBits(); + unsigned DestBitSize = DestTy->getPrimitiveSizeInBits(); + + // BitCast implies a no-op cast of type only. No bits change. + // However, you can't cast pointers to anything but pointers. + Assert1(isa(DestTy) == isa(DestTy), + "Bitcast requires both operands to be pointer or neither", &I); + Assert1(SrcBitSize == DestBitSize, "Bitcast requies types of same width", &I); + + visitInstruction(I); +} + +/// visitPHINode - Ensure that a PHI node is well formed. +/// void Verifier::visitPHINode(PHINode &PN) { // Ensure that the PHI nodes are all grouped together at the top of the block. // This can be tested by checking whether the instruction before this is @@ -389,9 +682,9 @@ void Verifier::visitCallInst(CallInst &CI) { // Verify that all arguments to the call match the function type... for (unsigned i = 0, e = FTy->getNumParams(); i != e; ++i) - Assert2(CI.getOperand(i+1)->getType() == FTy->getParamType(i), + Assert3(CI.getOperand(i+1)->getType() == FTy->getParamType(i), "Call parameter type does not match function signature!", - CI.getOperand(i+1), FTy->getParamType(i)); + CI.getOperand(i+1), FTy->getParamType(i), &CI); if (Function *F = CI.getCalledFunction()) if (Intrinsic::ID ID = (Intrinsic::ID)F->getIntrinsicID()) @@ -400,9 +693,9 @@ void Verifier::visitCallInst(CallInst &CI) { visitInstruction(CI); } -// visitBinaryOperator - Check that both arguments to the binary operator are -// of the same type! -// +/// visitBinaryOperator - Check that both arguments to the binary operator are +/// of the same type! +/// void Verifier::visitBinaryOperator(BinaryOperator &B) { Assert1(B.getOperand(0)->getType() == B.getOperand(1)->getType(), "Both operands to a binary operator are not of the same type!", &B); @@ -410,7 +703,9 @@ void Verifier::visitBinaryOperator(BinaryOperator &B) { // Check that logical operators are only used with integral operands. if (B.getOpcode() == Instruction::And || B.getOpcode() == Instruction::Or || B.getOpcode() == Instruction::Xor) { - Assert1(B.getType()->isIntegral(), + Assert1(B.getType()->isIntegral() || + (isa(B.getType()) && + cast(B.getType())->getElementType()->isIntegral()), "Logical operators only work with integral types!", &B); Assert1(B.getType() == B.getOperand(0)->getType(), "Logical operators must have same type for operands and result!", @@ -424,13 +719,41 @@ void Verifier::visitBinaryOperator(BinaryOperator &B) { Assert1(B.getType() == B.getOperand(0)->getType(), "Arithmetic operators must have same type for operands and result!", &B); - Assert1(B.getType()->isInteger() || B.getType()->isFloatingPoint(), - "Arithmetic operators must have integer or fp type!", &B); + Assert1(B.getType()->isInteger() || B.getType()->isFloatingPoint() || + isa(B.getType()), + "Arithmetic operators must have integer, fp, or packed type!", &B); } - + visitInstruction(B); } +void Verifier::visitICmpInst(ICmpInst& IC) { + // Check that the operands are the same type + const Type* Op0Ty = IC.getOperand(0)->getType(); + const Type* Op1Ty = IC.getOperand(1)->getType(); + Assert1(Op0Ty == Op1Ty, + "Both operands to ICmp instruction are not of the same type!", &IC); + // Check that the operands are the right type + Assert1(Op0Ty->isIntegral() || Op0Ty->getTypeID() == Type::PointerTyID || + (isa(Op0Ty) && + cast(Op0Ty)->getElementType()->isIntegral()), + "Invalid operand types for ICmp instruction", &IC); + visitInstruction(IC); +} + +void Verifier::visitFCmpInst(FCmpInst& FC) { + // Check that the operands are the same type + const Type* Op0Ty = FC.getOperand(0)->getType(); + const Type* Op1Ty = FC.getOperand(1)->getType(); + Assert1(Op0Ty == Op1Ty, + "Both operands to FCmp instruction are not of the same type!", &FC); + // Check that the operands are the right type + Assert1(Op0Ty->isFloatingPoint() || (isa(Op0Ty) && + cast(Op0Ty)->getElementType()->isFloatingPoint()), + "Invalid operand types for FCmp instruction", &FC); + visitInstruction(FC); +} + void Verifier::visitShiftInst(ShiftInst &SI) { Assert1(SI.getType()->isInteger(), "Shift must return an integer result!", &SI); @@ -441,6 +764,44 @@ void Verifier::visitShiftInst(ShiftInst &SI) { visitInstruction(SI); } +void Verifier::visitExtractElementInst(ExtractElementInst &EI) { + Assert1(ExtractElementInst::isValidOperands(EI.getOperand(0), + EI.getOperand(1)), + "Invalid extractelement operands!", &EI); + visitInstruction(EI); +} + +void Verifier::visitInsertElementInst(InsertElementInst &IE) { + Assert1(InsertElementInst::isValidOperands(IE.getOperand(0), + IE.getOperand(1), + IE.getOperand(2)), + "Invalid insertelement operands!", &IE); + visitInstruction(IE); +} + +void Verifier::visitShuffleVectorInst(ShuffleVectorInst &SV) { + Assert1(ShuffleVectorInst::isValidOperands(SV.getOperand(0), SV.getOperand(1), + SV.getOperand(2)), + "Invalid shufflevector operands!", &SV); + Assert1(SV.getType() == SV.getOperand(0)->getType(), + "Result of shufflevector must match first operand type!", &SV); + + // Check to see if Mask is valid. + if (const ConstantPacked *MV = dyn_cast(SV.getOperand(2))) { + for (unsigned i = 0, e = MV->getNumOperands(); i != e; ++i) { + Assert1(isa(MV->getOperand(i)) || + isa(MV->getOperand(i)), + "Invalid shufflevector shuffle mask!", &SV); + } + } else { + Assert1(isa(SV.getOperand(2)) || + isa(SV.getOperand(2)), + "Invalid shufflevector shuffle mask!", &SV); + } + + visitInstruction(SV); +} + void Verifier::visitGetElementPtrInst(GetElementPtrInst &GEP) { const Type *ElTy = GetElementPtrInst::getIndexedType(GEP.getOperand(0)->getType(), @@ -468,16 +829,17 @@ void Verifier::visitStoreInst(StoreInst &SI) { } -// verifyInstruction - Verify that an instruction is well formed. -// +/// verifyInstruction - Verify that an instruction is well formed. +/// void Verifier::visitInstruction(Instruction &I) { - BasicBlock *BB = I.getParent(); + BasicBlock *BB = I.getParent(); Assert1(BB, "Instruction not embedded in basic block!", &I); if (!isa(I)) { // Check that non-phi nodes are not self referential for (Value::use_iterator UI = I.use_begin(), UE = I.use_end(); UI != UE; ++UI) - Assert1(*UI != (User*)&I, + Assert1(*UI != (User*)&I || + !EF->dominates(&BB->getParent()->getEntryBlock(), BB), "Only PHI nodes may reference their own value!", &I); } @@ -485,10 +847,14 @@ void Verifier::visitInstruction(Instruction &I) { Assert1(I.getType() != Type::VoidTy || !I.hasName(), "Instruction has a name, but provides a void value!", &I); + // Check that the return value of the instruction is either void or a legal + // value type. + Assert1(I.getType() == Type::VoidTy || I.getType()->isFirstClassType(), + "Instruction returns a non-scalar type!", &I); + // Check that all uses of the instruction, if they are instructions // themselves, actually have parent basic blocks. If the use is not an // instruction, it is an error! - // for (User::use_iterator UI = I.use_begin(), UE = I.use_end(); UI != UE; ++UI) { Assert1(isa(*UI), "Use of instruction is not an instruction!", @@ -499,91 +865,127 @@ void Verifier::visitInstruction(Instruction &I) { } for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) { - // Check to make sure that the "address of" an intrinsic function is never - // taken. - if (Function *F = dyn_cast(I.getOperand(i))) + Assert1(I.getOperand(i) != 0, "Instruction has null operand!", &I); + + // Check to make sure that only first-class-values are operands to + // instructions. + Assert1(I.getOperand(i)->getType()->isFirstClassType(), + "Instruction operands must be first-class values!", &I); + + if (Function *F = dyn_cast(I.getOperand(i))) { + // Check to make sure that the "address of" an intrinsic function is never + // taken. Assert1(!F->isIntrinsic() || (i == 0 && isa(I)), "Cannot take the address of an intrinsic!", &I); - - else if (Instruction *Op = dyn_cast(I.getOperand(i))) { + } else if (BasicBlock *OpBB = dyn_cast(I.getOperand(i))) { + Assert1(OpBB->getParent() == BB->getParent(), + "Referring to a basic block in another function!", &I); + } else if (Argument *OpArg = dyn_cast(I.getOperand(i))) { + Assert1(OpArg->getParent() == BB->getParent(), + "Referring to an argument in another function!", &I); + } else if (Instruction *Op = dyn_cast(I.getOperand(i))) { BasicBlock *OpBlock = Op->getParent(); - // Invoke results are only usable in the normal destination, not in the - // exceptional destination. - if (InvokeInst *II = dyn_cast(Op)) - OpBlock = II->getNormalDest(); // Check that a definition dominates all of its uses. - // if (!isa(I)) { + // Invoke results are only usable in the normal destination, not in the + // exceptional destination. + if (InvokeInst *II = dyn_cast(Op)) + OpBlock = II->getNormalDest(); + else if (OpBlock == BB) { + // If they are in the same basic block, make sure that the definition + // comes before the use. + Assert2(InstsInThisBlock.count(Op) || + !EF->dominates(&BB->getParent()->getEntryBlock(), BB), + "Instruction does not dominate all uses!", Op, &I); + } + // Definition must dominate use unless use is unreachable! - Assert2(DS->dominates(OpBlock, BB) || - !DS->dominates(&BB->getParent()->getEntryBlock(), BB), + Assert2(EF->dominates(OpBlock, BB) || + !EF->dominates(&BB->getParent()->getEntryBlock(), BB), "Instruction does not dominate all uses!", Op, &I); } else { // PHI nodes are more difficult than other nodes because they actually // "use" the value in the predecessor basic blocks they correspond to. BasicBlock *PredBB = cast(I.getOperand(i+1)); - Assert2(DS->dominates(OpBlock, PredBB) || - !DS->dominates(&BB->getParent()->getEntryBlock(), PredBB), + Assert2(EF->dominates(OpBlock, PredBB) || + !EF->dominates(&BB->getParent()->getEntryBlock(), PredBB), "Instruction does not dominate all uses!", Op, &I); } + } else if (isa(I.getOperand(i))) { + Assert1(i == 0 && isa(I), + "Cannot take the address of an inline asm!", &I); } } + InstsInThisBlock.insert(&I); } /// visitIntrinsicFunction - Allow intrinsics to be verified in different ways. +/// void Verifier::visitIntrinsicFunctionCall(Intrinsic::ID ID, CallInst &CI) { Function *IF = CI.getCalledFunction(); - const FunctionType *FT = IF->getFunctionType(); Assert1(IF->isExternal(), "Intrinsic functions should never be defined!", IF); - unsigned NumArgs = 0; - - // FIXME: this should check the return type of each intrinsic as well, also - // arguments! - switch (ID) { - case Intrinsic::va_start: - Assert1(CI.getParent()->getParent()->getFunctionType()->isVarArg(), - "llvm.va_start intrinsic may only occur in function with variable" - " args!", &CI); - NumArgs = 0; - break; - case Intrinsic::va_end: NumArgs = 1; break; - case Intrinsic::va_copy: NumArgs = 1; break; - - case Intrinsic::setjmp: NumArgs = 1; break; - case Intrinsic::longjmp: NumArgs = 2; break; - case Intrinsic::sigsetjmp: NumArgs = 2; break; - case Intrinsic::siglongjmp: NumArgs = 2; break; - - case Intrinsic::dbg_stoppoint: NumArgs = 4; break; - case Intrinsic::dbg_region_start:NumArgs = 1; break; - case Intrinsic::dbg_region_end: NumArgs = 1; break; - case Intrinsic::dbg_func_start: NumArgs = 1; break; - case Intrinsic::dbg_declare: NumArgs = 1; break; - - case Intrinsic::alpha_ctlz: NumArgs = 1; break; - case Intrinsic::alpha_cttz: NumArgs = 1; break; - case Intrinsic::alpha_ctpop: NumArgs = 1; break; - case Intrinsic::alpha_umulh: NumArgs = 2; break; - case Intrinsic::alpha_vecop: NumArgs = 4; break; - case Intrinsic::alpha_pup: NumArgs = 3; break; - case Intrinsic::alpha_bytezap: NumArgs = 2; break; - case Intrinsic::alpha_bytemanip: NumArgs = 3; break; - case Intrinsic::alpha_dfpbop: NumArgs = 3; break; - case Intrinsic::alpha_dfpuop: NumArgs = 2; break; - case Intrinsic::alpha_unordered: NumArgs = 2; break; - case Intrinsic::alpha_uqtodfp: NumArgs = 2; break; - case Intrinsic::alpha_uqtosfp: NumArgs = 2; break; - case Intrinsic::alpha_dfptosq: NumArgs = 2; break; - case Intrinsic::alpha_sfptosq: NumArgs = 2; break; - - case Intrinsic::not_intrinsic: - assert(0 && "Invalid intrinsic!"); NumArgs = 0; break; + +#define GET_INTRINSIC_VERIFIER +#include "llvm/Intrinsics.gen" +#undef GET_INTRINSIC_VERIFIER +} + +/// VerifyIntrinsicPrototype - TableGen emits calls to this function into +/// Intrinsics.gen. This implements a little state machine that verifies the +/// prototype of intrinsics. +void Verifier::VerifyIntrinsicPrototype(Function *F, ...) { + va_list VA; + va_start(VA, F); + + const FunctionType *FTy = F->getFunctionType(); + + // Note that "arg#0" is the return type. + for (unsigned ArgNo = 0; 1; ++ArgNo) { + int TypeID = va_arg(VA, int); + + if (TypeID == -1) { + if (ArgNo != FTy->getNumParams()+1) + CheckFailed("Intrinsic prototype has too many arguments!", F); + break; + } + + if (ArgNo == FTy->getNumParams()+1) { + CheckFailed("Intrinsic prototype has too few arguments!", F); + break; + } + + const Type *Ty; + if (ArgNo == 0) + Ty = FTy->getReturnType(); + else + Ty = FTy->getParamType(ArgNo-1); + + if (Ty->getTypeID() != TypeID) { + if (ArgNo == 0) + CheckFailed("Intrinsic prototype has incorrect result type!", F); + else + CheckFailed("Intrinsic parameter #" + utostr(ArgNo-1) + " is wrong!",F); + break; + } + + // If this is a packed argument, verify the number and type of elements. + if (TypeID == Type::PackedTyID) { + const PackedType *PTy = cast(Ty); + if (va_arg(VA, int) != PTy->getElementType()->getTypeID()) { + CheckFailed("Intrinsic prototype has incorrect vector element type!",F); + break; + } + + if ((unsigned)va_arg(VA, int) != PTy->getNumElements()) { + CheckFailed("Intrinsic prototype has incorrect number of " + "vector elements!",F); + break; + } + } } - Assert1(FT->getNumParams() == NumArgs || (FT->getNumParams() < NumArgs && - FT->isVarArg()), - "Illegal # arguments for intrinsic function!", IF); + va_end(VA); } @@ -591,35 +993,36 @@ void Verifier::visitIntrinsicFunctionCall(Intrinsic::ID ID, CallInst &CI) { // Implement the public interfaces to this file... //===----------------------------------------------------------------------===// -FunctionPass *llvm::createVerifierPass() { - return new Verifier(); +FunctionPass *llvm::createVerifierPass(VerifierFailureAction action) { + return new Verifier(action); } -// verifyFunction - Create -bool llvm::verifyFunction(const Function &f) { - Function &F = (Function&)f; +// verifyFunction - Create +bool llvm::verifyFunction(const Function &f, VerifierFailureAction action) { + Function &F = const_cast(f); assert(!F.isExternal() && "Cannot verify external functions"); - DominatorSet DS; - DS.doInitialization(*F.getParent()); - DS.runOnFunction(F); - - Verifier V(DS); - V.runOnFunction(F); - - DS.doFinalization(*F.getParent()); - - return V.Broken; + FunctionPassManager FPM(new ExistingModuleProvider(F.getParent())); + Verifier *V = new Verifier(action); + FPM.add(V); + FPM.run(F); + return V->Broken; } -// verifyModule - Check a module for errors, printing messages on stderr. -// Return true if the module is corrupt. -// -bool llvm::verifyModule(const Module &M) { +/// verifyModule - Check a module for errors, printing messages on stderr. +/// Return true if the module is corrupt. +/// +bool llvm::verifyModule(const Module &M, VerifierFailureAction action, + std::string *ErrorInfo) { PassManager PM; - Verifier *V = new Verifier(); + Verifier *V = new Verifier(action); PM.add(V); PM.run((Module&)M); + + if (ErrorInfo && V->Broken) + *ErrorInfo = V->msgs.str(); return V->Broken; } + +// vim: sw=2