X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FVMCore%2FVerifier.cpp;h=38fbabb6c9baa2b3678a53c31d823d90a2710ab3;hb=bc2a99b4803487202e5521839b7a9e4d5869e5c8;hp=edd3da1a0075f917f9b2b931dceb4e1801e05e75;hpb=e1f0cf179f14d3d764bb39979707a6cabb99443d;p=oota-llvm.git diff --git a/lib/VMCore/Verifier.cpp b/lib/VMCore/Verifier.cpp index edd3da1a007..38fbabb6c9b 100644 --- a/lib/VMCore/Verifier.cpp +++ b/lib/VMCore/Verifier.cpp @@ -10,16 +10,16 @@ // 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 @@ -53,8 +53,9 @@ #include "llvm/Analysis/Dominators.h" #include "llvm/Support/CFG.h" #include "llvm/Support/InstVisitor.h" -#include "Support/STLExtras.h" +#include "llvm/ADT/STLExtras.h" #include +#include #include using namespace llvm; @@ -64,21 +65,27 @@ namespace { // Anonymous namespace for class bool Broken; // Is this module found to be broken? bool RealPass; // Are we not being run by a PassManager? VerifierFailureAction action; - // What to do if verification fails. + // What to do if verification fails. Module *Mod; // Module we are verifying right now DominatorSet *DS; // Dominator set, 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), + : Broken(false), RealPass(true), action(AbortProcessAction), DS(0), msgs( std::ios_base::app | std::ios_base::out ) {} Verifier( VerifierFailureAction ctn ) - : Broken(false), RealPass(true), action(ctn), DS(0), + : Broken(false), RealPass(true), action(ctn), DS(0), msgs( std::ios_base::app | std::ios_base::out ) {} Verifier(bool AB ) - : Broken(false), RealPass(true), + : Broken(false), RealPass(true), action( AB ? AbortProcessAction : PrintMessageAction), DS(0), - msgs( std::ios_base::app | std::ios_base::out ) {} + msgs( std::ios_base::app | std::ios_base::out ) {} Verifier(DominatorSet &ds) : Broken(false), RealPass(false), action(PrintMessageAction), DS(&ds), msgs( std::ios_base::app | std::ios_base::out ) {} @@ -100,6 +107,7 @@ namespace { // Anonymous namespace for class // Get dominator information if we are being run by PassManager if (RealPass) DS = &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 @@ -112,9 +120,13 @@ namespace { // Anonymous namespace for class 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); + // Check to make sure function prototypes are okay. + if (I->isExternal()) visitFunction(*I); + } + for (Module::giterator I = M.gbegin(), E = M.gend(); I != E; ++I) visitGlobalValue(*I); @@ -136,22 +148,22 @@ namespace { // Anonymous namespace for class if (Broken) { msgs << "Broken module found, "; - switch (action) - { - case AbortProcessAction: - msgs << "compilation aborted!\n"; - std::cerr << msgs.str(); - abort(); - case ThrowExceptionAction: - msgs << "verification terminated.\n"; - throw msgs.str(); - case PrintMessageAction: - msgs << "verification continues.\n"; - std::cerr << msgs.str(); - break; - case ReturnStatusAction: - break; - } + switch (action) + { + case AbortProcessAction: + msgs << "compilation aborted!\n"; + std::cerr << msgs.str(); + abort(); + case ThrowExceptionAction: + msgs << "verification terminated.\n"; + throw msgs.str(); + case PrintMessageAction: + msgs << "verification continues.\n"; + std::cerr << msgs.str(); + break; + case ReturnStatusAction: + break; + } } } @@ -173,6 +185,7 @@ 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); } @@ -183,14 +196,17 @@ namespace { // Anonymous namespace for class if (!V) return; if (isa(V)) { msgs << *V; - } else if (const Type *Ty = dyn_cast(V)) { - WriteTypeSymbolic(msgs, Ty, Mod); } else { WriteAsOperand (msgs, V, true, 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 @@ -205,6 +221,15 @@ namespace { // Anonymous namespace for class 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"); @@ -240,21 +265,21 @@ void Verifier::visitGlobalValue(GlobalValue &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) { @@ -271,10 +296,14 @@ void Verifier::visitFunction(Function &F) { // 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::aiterator I = F.abegin(), E = F.aend(); 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()); @@ -290,25 +319,23 @@ void Verifier::visitFunction(Function &F) { // verifyBasicBlock - Verify that a basic block is well formed... // void Verifier::visitBasicBlock(BasicBlock &BB) { + InstsInThisBlock.clear(); + // 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; @@ -365,6 +392,17 @@ void Verifier::visitReturnInst(ReturnInst &RI) { visitTerminatorInst(RI); } +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); @@ -372,6 +410,7 @@ void Verifier::visitSelectInst(SelectInst &SI) { "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); } @@ -459,8 +498,9 @@ 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); @@ -562,7 +602,8 @@ void Verifier::visitInstruction(Instruction &I) { else if (OpBlock == BB) { // If they are in the same basic block, make sure that the definition // comes before the use. - Assert2(DS->dominates(Op, &I), + Assert2(InstsInThisBlock.count(Op) || + !DS->dominates(&BB->getParent()->getEntryBlock(), BB), "Instruction does not dominate all uses!", Op, &I); } @@ -580,6 +621,7 @@ void Verifier::visitInstruction(Instruction &I) { } } } + InstsInThisBlock.insert(&I); } /// visitIntrinsicFunction - Allow intrinsics to be verified in different ways. @@ -629,7 +671,7 @@ void Verifier::visitIntrinsicFunctionCall(Intrinsic::ID ID, CallInst &CI) { "Illegal # arguments for intrinsic function!", IF); Assert1(FT->getParamType(0)->isFirstClassType(), "First argument not a first class type!", IF); - Assert1(FT->getParamType(1)->getPrimitiveID() == Type::PointerTyID, + Assert1(isa(FT->getParamType(1)), "Second argument not a pointer!", IF); NumArgs = 2; break; @@ -644,25 +686,46 @@ void Verifier::visitIntrinsicFunctionCall(Intrinsic::ID ID, CallInst &CI) { NumArgs = 1; break; - case Intrinsic:: readio: { - const Type * ParamType = FT->getParamType(0); - const Type * ReturnType = FT->getReturnType(); + case Intrinsic::readio: { + const PointerType *ParamType = dyn_cast(FT->getParamType(0)); + const Type *ReturnType = FT->getReturnType(); Assert1(FT->getNumParams() == 1, "Illegal # arguments for intrinsic function!", IF); - Assert1(isa(ParamType), - "First argument not a pointer!", IF); - Assert1(((cast(ParamType)->getElementType()) == ReturnType), + Assert1(ParamType, "First argument not a pointer!", IF); + Assert1(ParamType->getElementType() == ReturnType, "Pointer type doesn't match return type!", IF); NumArgs = 1; break; } + case Intrinsic::isunordered: + Assert1(FT->getNumParams() == 2, + "Illegal # arguments for intrinsic function!", IF); + Assert1(FT->getReturnType() == Type::BoolTy, + "Return type is not bool!", IF); + Assert1(FT->getParamType(0) == FT->getParamType(1), + "Arguments must be of the same type!", IF); + Assert1(FT->getParamType(0)->isFloatingPoint(), + "Argument is not a floating point type!", IF); + NumArgs = 2; + 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::gcroot: + Assert1(FT->getNumParams() == 2, + "Illegal # arguments for intrinsic function!", IF); + Assert1(isa(CI.getOperand(2)), + "Second argument to llvm.gcroot must be a constant!", &CI); + NumArgs = 2; + break; + case Intrinsic::gcread: NumArgs = 2; break; + case Intrinsic::gcwrite: NumArgs = 3; break; + case Intrinsic::dbg_stoppoint: NumArgs = 4; break; case Intrinsic::dbg_region_start:NumArgs = 1; break; case Intrinsic::dbg_region_end: NumArgs = 1; break; @@ -673,22 +736,6 @@ void Verifier::visitIntrinsicFunctionCall(Intrinsic::ID ID, CallInst &CI) { case Intrinsic::memmove: NumArgs = 4; break; case Intrinsic::memset: NumArgs = 4; 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; } @@ -730,3 +777,5 @@ bool llvm::verifyModule(const Module &M, VerifierFailureAction action) { PM.run((Module&)M); return V->Broken; } + +// vim: sw=2