LLVM API Documentation

Verifier.cpp

Go to the documentation of this file.
00001 //===-- Verifier.cpp - Implement the Module Verifier -------------*- C++ -*-==//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file defines the function verifier interface, that can be used for some
00011 // sanity checking of input to the system.
00012 //
00013 // Note that this does not provide full `Java style' security and verifications,
00014 // instead it just tries to ensure that code is well-formed.
00015 //
00016 //  * Both of a binary operator's parameters are of the same type
00017 //  * Verify that the indices of mem access instructions match other operands
00018 //  * Verify that arithmetic and other things are only performed on first-class
00019 //    types.  Verify that shifts & logicals only happen on integrals f.e.
00020 //  * All of the constants in a switch statement are of the correct type
00021 //  * The code is in valid SSA form
00022 //  * It should be illegal to put a label into any other type (like a structure)
00023 //    or to return one. [except constant arrays!]
00024 //  * Only phi nodes can be self referential: 'add int %0, %0 ; <int>:0' is bad
00025 //  * PHI nodes must have an entry for each predecessor, with no extras.
00026 //  * PHI nodes must be the first thing in a basic block, all grouped together
00027 //  * PHI nodes must have at least one entry
00028 //  * All basic blocks should only end with terminator insts, not contain them
00029 //  * The entry node to a function must not have predecessors
00030 //  * All Instructions must be embedded into a basic block
00031 //  * Functions cannot take a void-typed parameter
00032 //  * Verify that a function's argument list agrees with it's declared type.
00033 //  * It is illegal to specify a name for a void value.
00034 //  * It is illegal to have a internal global value with no initializer
00035 //  * It is illegal to have a ret instruction that returns a value that does not
00036 //    agree with the function return value type.
00037 //  * Function call argument types match the function prototype
00038 //  * All other things that are tested by asserts spread about the code...
00039 //
00040 //===----------------------------------------------------------------------===//
00041 
00042 #include "llvm/Analysis/Verifier.h"
00043 #include "llvm/Assembly/Writer.h"
00044 #include "llvm/CallingConv.h"
00045 #include "llvm/Constants.h"
00046 #include "llvm/Pass.h"
00047 #include "llvm/Module.h"
00048 #include "llvm/ModuleProvider.h"
00049 #include "llvm/DerivedTypes.h"
00050 #include "llvm/InlineAsm.h"
00051 #include "llvm/Instructions.h"
00052 #include "llvm/Intrinsics.h"
00053 #include "llvm/PassManager.h"
00054 #include "llvm/SymbolTable.h"
00055 #include "llvm/Analysis/Dominators.h"
00056 #include "llvm/Support/CFG.h"
00057 #include "llvm/Support/InstVisitor.h"
00058 #include "llvm/ADT/StringExtras.h"
00059 #include "llvm/ADT/STLExtras.h"
00060 #include <algorithm>
00061 #include <iostream>
00062 #include <sstream>
00063 #include <cstdarg>
00064 using namespace llvm;
00065 
00066 namespace {  // Anonymous namespace for class
00067 
00068   struct Verifier : public FunctionPass, InstVisitor<Verifier> {
00069     bool Broken;          // Is this module found to be broken?
00070     bool RealPass;        // Are we not being run by a PassManager?
00071     VerifierFailureAction action;
00072                           // What to do if verification fails.
00073     Module *Mod;          // Module we are verifying right now
00074     ETForest *EF;     // ET-Forest, caution can be null!
00075     std::stringstream msgs;  // A stringstream to collect messages
00076 
00077     /// InstInThisBlock - when verifying a basic block, keep track of all of the
00078     /// instructions we have seen so far.  This allows us to do efficient
00079     /// dominance checks for the case when an instruction has an operand that is
00080     /// an instruction in the same block.
00081     std::set<Instruction*> InstsInThisBlock;
00082 
00083     Verifier()
00084         : Broken(false), RealPass(true), action(AbortProcessAction),
00085           EF(0), msgs( std::ios::app | std::ios::out ) {}
00086     Verifier( VerifierFailureAction ctn )
00087         : Broken(false), RealPass(true), action(ctn), EF(0),
00088           msgs( std::ios::app | std::ios::out ) {}
00089     Verifier(bool AB )
00090         : Broken(false), RealPass(true),
00091           action( AB ? AbortProcessAction : PrintMessageAction), EF(0),
00092           msgs( std::ios::app | std::ios::out ) {}
00093     Verifier(ETForest &ef)
00094       : Broken(false), RealPass(false), action(PrintMessageAction),
00095         EF(&ef), msgs( std::ios::app | std::ios::out ) {}
00096 
00097 
00098     bool doInitialization(Module &M) {
00099       Mod = &M;
00100       verifySymbolTable(M.getSymbolTable());
00101 
00102       // If this is a real pass, in a pass manager, we must abort before
00103       // returning back to the pass manager, or else the pass manager may try to
00104       // run other passes on the broken module.
00105       if (RealPass)
00106         abortIfBroken();
00107       return false;
00108     }
00109 
00110     bool runOnFunction(Function &F) {
00111       // Get dominator information if we are being run by PassManager
00112       if (RealPass) EF = &getAnalysis<ETForest>();
00113       visit(F);
00114       InstsInThisBlock.clear();
00115 
00116       // If this is a real pass, in a pass manager, we must abort before
00117       // returning back to the pass manager, or else the pass manager may try to
00118       // run other passes on the broken module.
00119       if (RealPass)
00120         abortIfBroken();
00121 
00122       return false;
00123     }
00124 
00125     bool doFinalization(Module &M) {
00126       // Scan through, checking all of the external function's linkage now...
00127       for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) {
00128         visitGlobalValue(*I);
00129 
00130         // Check to make sure function prototypes are okay.
00131         if (I->isExternal()) visitFunction(*I);
00132       }
00133 
00134       for (Module::global_iterator I = M.global_begin(), E = M.global_end(); 
00135            I != E; ++I)
00136         visitGlobalVariable(*I);
00137 
00138       // If the module is broken, abort at this time.
00139       abortIfBroken();
00140       return false;
00141     }
00142 
00143     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
00144       AU.setPreservesAll();
00145       if (RealPass)
00146         AU.addRequired<ETForest>();
00147     }
00148 
00149     /// abortIfBroken - If the module is broken and we are supposed to abort on
00150     /// this condition, do so.
00151     ///
00152     void abortIfBroken() {
00153       if (Broken)
00154       {
00155         msgs << "Broken module found, ";
00156         switch (action)
00157         {
00158           case AbortProcessAction:
00159             msgs << "compilation aborted!\n";
00160             std::cerr << msgs.str();
00161             abort();
00162           case ThrowExceptionAction:
00163             msgs << "verification terminated.\n";
00164             throw msgs.str();
00165           case PrintMessageAction:
00166             msgs << "verification continues.\n";
00167             std::cerr << msgs.str();
00168             break;
00169           case ReturnStatusAction:
00170             break;
00171         }
00172       }
00173     }
00174 
00175 
00176     // Verification methods...
00177     void verifySymbolTable(SymbolTable &ST);
00178     void visitGlobalValue(GlobalValue &GV);
00179     void visitGlobalVariable(GlobalVariable &GV);
00180     void visitFunction(Function &F);
00181     void visitBasicBlock(BasicBlock &BB);
00182     void visitPHINode(PHINode &PN);
00183     void visitBinaryOperator(BinaryOperator &B);
00184     void visitShiftInst(ShiftInst &SI);
00185     void visitExtractElementInst(ExtractElementInst &EI);
00186     void visitInsertElementInst(InsertElementInst &EI);
00187     void visitShuffleVectorInst(ShuffleVectorInst &EI);
00188     void visitVAArgInst(VAArgInst &VAA) { visitInstruction(VAA); }
00189     void visitCallInst(CallInst &CI);
00190     void visitGetElementPtrInst(GetElementPtrInst &GEP);
00191     void visitLoadInst(LoadInst &LI);
00192     void visitStoreInst(StoreInst &SI);
00193     void visitInstruction(Instruction &I);
00194     void visitTerminatorInst(TerminatorInst &I);
00195     void visitReturnInst(ReturnInst &RI);
00196     void visitSwitchInst(SwitchInst &SI);
00197     void visitSelectInst(SelectInst &SI);
00198     void visitUserOp1(Instruction &I);
00199     void visitUserOp2(Instruction &I) { visitUserOp1(I); }
00200     void visitIntrinsicFunctionCall(Intrinsic::ID ID, CallInst &CI);
00201 
00202     void VerifyIntrinsicPrototype(Function *F, ...);
00203 
00204     void WriteValue(const Value *V) {
00205       if (!V) return;
00206       if (isa<Instruction>(V)) {
00207         msgs << *V;
00208       } else {
00209         WriteAsOperand (msgs, V, true, true, Mod);
00210         msgs << "\n";
00211       }
00212     }
00213 
00214     void WriteType(const Type* T ) {
00215       if ( !T ) return;
00216       WriteTypeSymbolic(msgs, T, Mod );
00217     }
00218 
00219 
00220     // CheckFailed - A check failed, so print out the condition and the message
00221     // that failed.  This provides a nice place to put a breakpoint if you want
00222     // to see why something is not correct.
00223     void CheckFailed(const std::string &Message,
00224                      const Value *V1 = 0, const Value *V2 = 0,
00225                      const Value *V3 = 0, const Value *V4 = 0) {
00226       msgs << Message << "\n";
00227       WriteValue(V1);
00228       WriteValue(V2);
00229       WriteValue(V3);
00230       WriteValue(V4);
00231       Broken = true;
00232     }
00233 
00234     void CheckFailed( const std::string& Message, const Value* V1,
00235                       const Type* T2, const Value* V3 = 0 ) {
00236       msgs << Message << "\n";
00237       WriteValue(V1);
00238       WriteType(T2);
00239       WriteValue(V3);
00240       Broken = true;
00241     }
00242   };
00243 
00244   RegisterOpt<Verifier> X("verify", "Module Verifier");
00245 } // End anonymous namespace
00246 
00247 
00248 // Assert - We know that cond should be true, if not print an error message.
00249 #define Assert(C, M) \
00250   do { if (!(C)) { CheckFailed(M); return; } } while (0)
00251 #define Assert1(C, M, V1) \
00252   do { if (!(C)) { CheckFailed(M, V1); return; } } while (0)
00253 #define Assert2(C, M, V1, V2) \
00254   do { if (!(C)) { CheckFailed(M, V1, V2); return; } } while (0)
00255 #define Assert3(C, M, V1, V2, V3) \
00256   do { if (!(C)) { CheckFailed(M, V1, V2, V3); return; } } while (0)
00257 #define Assert4(C, M, V1, V2, V3, V4) \
00258   do { if (!(C)) { CheckFailed(M, V1, V2, V3, V4); return; } } while (0)
00259 
00260 
00261 void Verifier::visitGlobalValue(GlobalValue &GV) {
00262   Assert1(!GV.isExternal() || GV.hasExternalLinkage(),
00263           "Global is external, but doesn't have external linkage!", &GV);
00264   Assert1(!GV.hasAppendingLinkage() || isa<GlobalVariable>(GV),
00265           "Only global variables can have appending linkage!", &GV);
00266 
00267   if (GV.hasAppendingLinkage()) {
00268     GlobalVariable &GVar = cast<GlobalVariable>(GV);
00269     Assert1(isa<ArrayType>(GVar.getType()->getElementType()),
00270             "Only global arrays can have appending linkage!", &GV);
00271   }
00272 }
00273 
00274 void Verifier::visitGlobalVariable(GlobalVariable &GV) {
00275   if (GV.hasInitializer())
00276     Assert1(GV.getInitializer()->getType() == GV.getType()->getElementType(),
00277             "Global variable initializer type does not match global "
00278             "variable type!", &GV);
00279 
00280   visitGlobalValue(GV);
00281 }
00282 
00283 
00284 // verifySymbolTable - Verify that a function or module symbol table is ok
00285 //
00286 void Verifier::verifySymbolTable(SymbolTable &ST) {
00287 
00288   // Loop over all of the values in all type planes in the symbol table.
00289   for (SymbolTable::plane_const_iterator PI = ST.plane_begin(),
00290        PE = ST.plane_end(); PI != PE; ++PI)
00291     for (SymbolTable::value_const_iterator VI = PI->second.begin(),
00292          VE = PI->second.end(); VI != VE; ++VI) {
00293       Value *V = VI->second;
00294       // Check that there are no void typed values in the symbol table.  Values
00295       // with a void type cannot be put into symbol tables because they cannot
00296       // have names!
00297       Assert1(V->getType() != Type::VoidTy,
00298         "Values with void type are not allowed to have names!", V);
00299     }
00300 }
00301 
00302 // visitFunction - Verify that a function is ok.
00303 //
00304 void Verifier::visitFunction(Function &F) {
00305   Assert1(!F.isVarArg() || F.getCallingConv() == CallingConv::C,
00306           "Varargs functions must have C calling conventions!", &F);
00307 
00308   // Check function arguments.
00309   const FunctionType *FT = F.getFunctionType();
00310   unsigned NumArgs = F.getArgumentList().size();
00311 
00312   Assert2(FT->getNumParams() == NumArgs,
00313           "# formal arguments must match # of arguments for function type!",
00314           &F, FT);
00315   Assert1(F.getReturnType()->isFirstClassType() ||
00316           F.getReturnType() == Type::VoidTy,
00317           "Functions cannot return aggregate values!", &F);
00318 
00319   // Check that the argument values match the function type for this function...
00320   unsigned i = 0;
00321   for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I, ++i) {
00322     Assert2(I->getType() == FT->getParamType(i),
00323             "Argument value does not match function argument type!",
00324             I, FT->getParamType(i));
00325     // Make sure no aggregates are passed by value.
00326     Assert1(I->getType()->isFirstClassType(),
00327             "Functions cannot take aggregates as arguments by value!", I);
00328    }
00329 
00330   if (!F.isExternal()) {
00331     verifySymbolTable(F.getSymbolTable());
00332 
00333     // Check the entry node
00334     BasicBlock *Entry = &F.getEntryBlock();
00335     Assert1(pred_begin(Entry) == pred_end(Entry),
00336             "Entry block to function must not have predecessors!", Entry);
00337   }
00338 }
00339 
00340 
00341 // verifyBasicBlock - Verify that a basic block is well formed...
00342 //
00343 void Verifier::visitBasicBlock(BasicBlock &BB) {
00344   InstsInThisBlock.clear();
00345 
00346   // Ensure that basic blocks have terminators!
00347   Assert1(BB.getTerminator(), "Basic Block does not have terminator!", &BB);
00348 
00349   // Check constraints that this basic block imposes on all of the PHI nodes in
00350   // it.
00351   if (isa<PHINode>(BB.front())) {
00352     std::vector<BasicBlock*> Preds(pred_begin(&BB), pred_end(&BB));
00353     std::sort(Preds.begin(), Preds.end());
00354     PHINode *PN;
00355     for (BasicBlock::iterator I = BB.begin(); (PN = dyn_cast<PHINode>(I));++I) {
00356 
00357       // Ensure that PHI nodes have at least one entry!
00358       Assert1(PN->getNumIncomingValues() != 0,
00359               "PHI nodes must have at least one entry.  If the block is dead, "
00360               "the PHI should be removed!", PN);
00361       Assert1(PN->getNumIncomingValues() == Preds.size(),
00362               "PHINode should have one entry for each predecessor of its "
00363               "parent basic block!", PN);
00364 
00365       // Get and sort all incoming values in the PHI node...
00366       std::vector<std::pair<BasicBlock*, Value*> > Values;
00367       Values.reserve(PN->getNumIncomingValues());
00368       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
00369         Values.push_back(std::make_pair(PN->getIncomingBlock(i),
00370                                         PN->getIncomingValue(i)));
00371       std::sort(Values.begin(), Values.end());
00372 
00373       for (unsigned i = 0, e = Values.size(); i != e; ++i) {
00374         // Check to make sure that if there is more than one entry for a
00375         // particular basic block in this PHI node, that the incoming values are
00376         // all identical.
00377         //
00378         Assert4(i == 0 || Values[i].first  != Values[i-1].first ||
00379                 Values[i].second == Values[i-1].second,
00380                 "PHI node has multiple entries for the same basic block with "
00381                 "different incoming values!", PN, Values[i].first,
00382                 Values[i].second, Values[i-1].second);
00383 
00384         // Check to make sure that the predecessors and PHI node entries are
00385         // matched up.
00386         Assert3(Values[i].first == Preds[i],
00387                 "PHI node entries do not match predecessors!", PN,
00388                 Values[i].first, Preds[i]);
00389       }
00390     }
00391   }
00392 }
00393 
00394 void Verifier::visitTerminatorInst(TerminatorInst &I) {
00395   // Ensure that terminators only exist at the end of the basic block.
00396   Assert1(&I == I.getParent()->getTerminator(),
00397           "Terminator found in the middle of a basic block!", I.getParent());
00398   visitInstruction(I);
00399 }
00400 
00401 void Verifier::visitReturnInst(ReturnInst &RI) {
00402   Function *F = RI.getParent()->getParent();
00403   if (RI.getNumOperands() == 0)
00404     Assert2(F->getReturnType() == Type::VoidTy,
00405             "Found return instr that returns void in Function of non-void "
00406             "return type!", &RI, F->getReturnType());
00407   else
00408     Assert2(F->getReturnType() == RI.getOperand(0)->getType(),
00409             "Function return type does not match operand "
00410             "type of return inst!", &RI, F->getReturnType());
00411 
00412   // Check to make sure that the return value has necessary properties for
00413   // terminators...
00414   visitTerminatorInst(RI);
00415 }
00416 
00417 void Verifier::visitSwitchInst(SwitchInst &SI) {
00418   // Check to make sure that all of the constants in the switch instruction
00419   // have the same type as the switched-on value.
00420   const Type *SwitchTy = SI.getCondition()->getType();
00421   for (unsigned i = 1, e = SI.getNumCases(); i != e; ++i)
00422     Assert1(SI.getCaseValue(i)->getType() == SwitchTy,
00423             "Switch constants must all be same type as switch value!", &SI);
00424 
00425   visitTerminatorInst(SI);
00426 }
00427 
00428 void Verifier::visitSelectInst(SelectInst &SI) {
00429   Assert1(SI.getCondition()->getType() == Type::BoolTy,
00430           "Select condition type must be bool!", &SI);
00431   Assert1(SI.getTrueValue()->getType() == SI.getFalseValue()->getType(),
00432           "Select values must have identical types!", &SI);
00433   Assert1(SI.getTrueValue()->getType() == SI.getType(),
00434           "Select values must have same type as select instruction!", &SI);
00435   visitInstruction(SI);
00436 }
00437 
00438 
00439 /// visitUserOp1 - User defined operators shouldn't live beyond the lifetime of
00440 /// a pass, if any exist, it's an error.
00441 ///
00442 void Verifier::visitUserOp1(Instruction &I) {
00443   Assert1(0, "User-defined operators should not live outside of a pass!", &I);
00444 }
00445 
00446 /// visitPHINode - Ensure that a PHI node is well formed.
00447 ///
00448 void Verifier::visitPHINode(PHINode &PN) {
00449   // Ensure that the PHI nodes are all grouped together at the top of the block.
00450   // This can be tested by checking whether the instruction before this is
00451   // either nonexistent (because this is begin()) or is a PHI node.  If not,
00452   // then there is some other instruction before a PHI.
00453   Assert2(&PN.getParent()->front() == &PN || isa<PHINode>(PN.getPrev()),
00454           "PHI nodes not grouped at top of basic block!",
00455           &PN, PN.getParent());
00456 
00457   // Check that all of the operands of the PHI node have the same type as the
00458   // result.
00459   for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
00460     Assert1(PN.getType() == PN.getIncomingValue(i)->getType(),
00461             "PHI node operands are not the same type as the result!", &PN);
00462 
00463   // All other PHI node constraints are checked in the visitBasicBlock method.
00464 
00465   visitInstruction(PN);
00466 }
00467 
00468 void Verifier::visitCallInst(CallInst &CI) {
00469   Assert1(isa<PointerType>(CI.getOperand(0)->getType()),
00470           "Called function must be a pointer!", &CI);
00471   const PointerType *FPTy = cast<PointerType>(CI.getOperand(0)->getType());
00472   Assert1(isa<FunctionType>(FPTy->getElementType()),
00473           "Called function is not pointer to function type!", &CI);
00474 
00475   const FunctionType *FTy = cast<FunctionType>(FPTy->getElementType());
00476 
00477   // Verify that the correct number of arguments are being passed
00478   if (FTy->isVarArg())
00479     Assert1(CI.getNumOperands()-1 >= FTy->getNumParams(),
00480             "Called function requires more parameters than were provided!",&CI);
00481   else
00482     Assert1(CI.getNumOperands()-1 == FTy->getNumParams(),
00483             "Incorrect number of arguments passed to called function!", &CI);
00484 
00485   // Verify that all arguments to the call match the function type...
00486   for (unsigned i = 0, e = FTy->getNumParams(); i != e; ++i)
00487     Assert3(CI.getOperand(i+1)->getType() == FTy->getParamType(i),
00488             "Call parameter type does not match function signature!",
00489             CI.getOperand(i+1), FTy->getParamType(i), &CI);
00490 
00491   if (Function *F = CI.getCalledFunction())
00492     if (Intrinsic::ID ID = (Intrinsic::ID)F->getIntrinsicID())
00493       visitIntrinsicFunctionCall(ID, CI);
00494 
00495   visitInstruction(CI);
00496 }
00497 
00498 /// visitBinaryOperator - Check that both arguments to the binary operator are
00499 /// of the same type!
00500 ///
00501 void Verifier::visitBinaryOperator(BinaryOperator &B) {
00502   Assert1(B.getOperand(0)->getType() == B.getOperand(1)->getType(),
00503           "Both operands to a binary operator are not of the same type!", &B);
00504 
00505   // Check that logical operators are only used with integral operands.
00506   if (B.getOpcode() == Instruction::And || B.getOpcode() == Instruction::Or ||
00507       B.getOpcode() == Instruction::Xor) {
00508     Assert1(B.getType()->isIntegral() ||
00509             (isa<PackedType>(B.getType()) && 
00510              cast<PackedType>(B.getType())->getElementType()->isIntegral()),
00511             "Logical operators only work with integral types!", &B);
00512     Assert1(B.getType() == B.getOperand(0)->getType(),
00513             "Logical operators must have same type for operands and result!",
00514             &B);
00515   } else if (isa<SetCondInst>(B)) {
00516     // Check that setcc instructions return bool
00517     Assert1(B.getType() == Type::BoolTy,
00518             "setcc instructions must return boolean values!", &B);
00519   } else {
00520     // Arithmetic operators only work on integer or fp values
00521     Assert1(B.getType() == B.getOperand(0)->getType(),
00522             "Arithmetic operators must have same type for operands and result!",
00523             &B);
00524     Assert1(B.getType()->isInteger() || B.getType()->isFloatingPoint() ||
00525             isa<PackedType>(B.getType()),
00526             "Arithmetic operators must have integer, fp, or packed type!", &B);
00527   }
00528 
00529   visitInstruction(B);
00530 }
00531 
00532 void Verifier::visitShiftInst(ShiftInst &SI) {
00533   Assert1(SI.getType()->isInteger(),
00534           "Shift must return an integer result!", &SI);
00535   Assert1(SI.getType() == SI.getOperand(0)->getType(),
00536           "Shift return type must be same as first operand!", &SI);
00537   Assert1(SI.getOperand(1)->getType() == Type::UByteTy,
00538           "Second operand to shift must be ubyte type!", &SI);
00539   visitInstruction(SI);
00540 }
00541 
00542 void Verifier::visitExtractElementInst(ExtractElementInst &EI) {
00543   Assert1(ExtractElementInst::isValidOperands(EI.getOperand(0),
00544                                               EI.getOperand(1)),
00545           "Invalid extractelement operands!", &EI);
00546   visitInstruction(EI);
00547 }
00548 
00549 void Verifier::visitInsertElementInst(InsertElementInst &IE) {
00550   Assert1(InsertElementInst::isValidOperands(IE.getOperand(0),
00551                                              IE.getOperand(1),
00552                                              IE.getOperand(2)),
00553           "Invalid insertelement operands!", &IE);
00554   visitInstruction(IE);
00555 }
00556 
00557 void Verifier::visitShuffleVectorInst(ShuffleVectorInst &SV) {
00558   Assert1(ShuffleVectorInst::isValidOperands(SV.getOperand(0), SV.getOperand(1),
00559                                              SV.getOperand(2)),
00560           "Invalid shufflevector operands!", &SV);
00561   Assert1(SV.getType() == SV.getOperand(0)->getType(),
00562           "Result of shufflevector must match first operand type!", &SV);
00563   
00564   // Check to see if Mask is valid.
00565   if (const ConstantPacked *MV = dyn_cast<ConstantPacked>(SV.getOperand(2))) {
00566     for (unsigned i = 0, e = MV->getNumOperands(); i != e; ++i) {
00567       Assert1(isa<ConstantUInt>(MV->getOperand(i)) ||
00568               isa<UndefValue>(MV->getOperand(i)),
00569               "Invalid shufflevector shuffle mask!", &SV);
00570     }
00571   } else {
00572     Assert1(isa<UndefValue>(SV.getOperand(2)) || 
00573             isa<ConstantAggregateZero>(SV.getOperand(2)),
00574             "Invalid shufflevector shuffle mask!", &SV);
00575   }
00576   
00577   visitInstruction(SV);
00578 }
00579 
00580 void Verifier::visitGetElementPtrInst(GetElementPtrInst &GEP) {
00581   const Type *ElTy =
00582     GetElementPtrInst::getIndexedType(GEP.getOperand(0)->getType(),
00583                    std::vector<Value*>(GEP.idx_begin(), GEP.idx_end()), true);
00584   Assert1(ElTy, "Invalid indices for GEP pointer type!", &GEP);
00585   Assert2(PointerType::get(ElTy) == GEP.getType(),
00586           "GEP is not of right type for indices!", &GEP, ElTy);
00587   visitInstruction(GEP);
00588 }
00589 
00590 void Verifier::visitLoadInst(LoadInst &LI) {
00591   const Type *ElTy =
00592     cast<PointerType>(LI.getOperand(0)->getType())->getElementType();
00593   Assert2(ElTy == LI.getType(),
00594           "Load result type does not match pointer operand type!", &LI, ElTy);
00595   visitInstruction(LI);
00596 }
00597 
00598 void Verifier::visitStoreInst(StoreInst &SI) {
00599   const Type *ElTy =
00600     cast<PointerType>(SI.getOperand(1)->getType())->getElementType();
00601   Assert2(ElTy == SI.getOperand(0)->getType(),
00602           "Stored value type does not match pointer operand type!", &SI, ElTy);
00603   visitInstruction(SI);
00604 }
00605 
00606 
00607 /// verifyInstruction - Verify that an instruction is well formed.
00608 ///
00609 void Verifier::visitInstruction(Instruction &I) {
00610   BasicBlock *BB = I.getParent();
00611   Assert1(BB, "Instruction not embedded in basic block!", &I);
00612 
00613   if (!isa<PHINode>(I)) {   // Check that non-phi nodes are not self referential
00614     for (Value::use_iterator UI = I.use_begin(), UE = I.use_end();
00615          UI != UE; ++UI)
00616       Assert1(*UI != (User*)&I ||
00617               !EF->dominates(&BB->getParent()->getEntryBlock(), BB),
00618               "Only PHI nodes may reference their own value!", &I);
00619   }
00620 
00621   // Check that void typed values don't have names
00622   Assert1(I.getType() != Type::VoidTy || !I.hasName(),
00623           "Instruction has a name, but provides a void value!", &I);
00624 
00625   // Check that the return value of the instruction is either void or a legal
00626   // value type.
00627   Assert1(I.getType() == Type::VoidTy || I.getType()->isFirstClassType(),
00628           "Instruction returns a non-scalar type!", &I);
00629 
00630   // Check that all uses of the instruction, if they are instructions
00631   // themselves, actually have parent basic blocks.  If the use is not an
00632   // instruction, it is an error!
00633   for (User::use_iterator UI = I.use_begin(), UE = I.use_end();
00634        UI != UE; ++UI) {
00635     Assert1(isa<Instruction>(*UI), "Use of instruction is not an instruction!",
00636             *UI);
00637     Instruction *Used = cast<Instruction>(*UI);
00638     Assert2(Used->getParent() != 0, "Instruction referencing instruction not"
00639             " embeded in a basic block!", &I, Used);
00640   }
00641 
00642   for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) {
00643     // Check to make sure that the "address of" an intrinsic function is never
00644     // taken.
00645     Assert1(I.getOperand(i) != 0, "Instruction has null operand!", &I);
00646     if (Function *F = dyn_cast<Function>(I.getOperand(i))) {
00647       Assert1(!F->isIntrinsic() || (i == 0 && isa<CallInst>(I)),
00648               "Cannot take the address of an intrinsic!", &I);
00649     } else if (BasicBlock *OpBB = dyn_cast<BasicBlock>(I.getOperand(i))) {
00650       Assert1(OpBB->getParent() == BB->getParent(),
00651               "Referring to a basic block in another function!", &I);
00652     } else if (Argument *OpArg = dyn_cast<Argument>(I.getOperand(i))) {
00653       Assert1(OpArg->getParent() == BB->getParent(),
00654               "Referring to an argument in another function!", &I);
00655     } else if (Instruction *Op = dyn_cast<Instruction>(I.getOperand(i))) {
00656       BasicBlock *OpBlock = Op->getParent();
00657 
00658       // Check that a definition dominates all of its uses.
00659       if (!isa<PHINode>(I)) {
00660         // Invoke results are only usable in the normal destination, not in the
00661         // exceptional destination.
00662         if (InvokeInst *II = dyn_cast<InvokeInst>(Op))
00663           OpBlock = II->getNormalDest();
00664         else if (OpBlock == BB) {
00665           // If they are in the same basic block, make sure that the definition
00666           // comes before the use.
00667           Assert2(InstsInThisBlock.count(Op) ||
00668                   !EF->dominates(&BB->getParent()->getEntryBlock(), BB),
00669                   "Instruction does not dominate all uses!", Op, &I);
00670         }
00671 
00672         // Definition must dominate use unless use is unreachable!
00673         Assert2(EF->dominates(OpBlock, BB) ||
00674                 !EF->dominates(&BB->getParent()->getEntryBlock(), BB),
00675                 "Instruction does not dominate all uses!", Op, &I);
00676       } else {
00677         // PHI nodes are more difficult than other nodes because they actually
00678         // "use" the value in the predecessor basic blocks they correspond to.
00679         BasicBlock *PredBB = cast<BasicBlock>(I.getOperand(i+1));
00680         Assert2(EF->dominates(OpBlock, PredBB) ||
00681                 !EF->dominates(&BB->getParent()->getEntryBlock(), PredBB),
00682                 "Instruction does not dominate all uses!", Op, &I);
00683       }
00684     } else if (isa<InlineAsm>(I.getOperand(i))) {
00685       Assert1(i == 0 && isa<CallInst>(I),
00686               "Cannot take the address of an inline asm!", &I);
00687     }
00688   }
00689   InstsInThisBlock.insert(&I);
00690 }
00691 
00692 /// visitIntrinsicFunction - Allow intrinsics to be verified in different ways.
00693 ///
00694 void Verifier::visitIntrinsicFunctionCall(Intrinsic::ID ID, CallInst &CI) {
00695   Function *IF = CI.getCalledFunction();
00696   const FunctionType *FTy = IF->getFunctionType();
00697   Assert1(IF->isExternal(), "Intrinsic functions should never be defined!", IF);
00698   
00699 #define GET_INTRINSIC_VERIFIER
00700 #include "llvm/Intrinsics.gen"
00701 #undef GET_INTRINSIC_VERIFIER
00702 }
00703 
00704 /// VerifyIntrinsicPrototype - TableGen emits calls to this function into
00705 /// Intrinsics.gen.  This implements a little state machine that verifies the
00706 /// prototype of intrinsics.
00707 void Verifier::VerifyIntrinsicPrototype(Function *F, ...) {
00708   va_list VA;
00709   va_start(VA, F);
00710   
00711   const FunctionType *FTy = F->getFunctionType();
00712   
00713   // Note that "arg#0" is the return type.
00714   for (unsigned ArgNo = 0; 1; ++ArgNo) {
00715     int TypeID = va_arg(VA, int);
00716 
00717     if (TypeID == -1) {
00718       if (ArgNo != FTy->getNumParams()+1)
00719         CheckFailed("Intrinsic prototype has too many arguments!", F);
00720       break;
00721     }
00722 
00723     if (ArgNo == FTy->getNumParams()+1) {
00724       CheckFailed("Intrinsic prototype has too few arguments!", F);
00725       break;
00726     }
00727     
00728     const Type *Ty;
00729     if (ArgNo == 0) 
00730       Ty = FTy->getReturnType();
00731     else
00732       Ty = FTy->getParamType(ArgNo-1);
00733     
00734     if (Ty->getTypeID() != TypeID) {
00735       if (ArgNo == 0)
00736         CheckFailed("Intrinsic prototype has incorrect result type!", F);
00737       else
00738         CheckFailed("Intrinsic parameter #" + utostr(ArgNo-1) + " is wrong!",F);
00739       break;
00740     }
00741 
00742     // If this is a packed argument, verify the number and type of elements.
00743     if (TypeID == Type::PackedTyID) {
00744       const PackedType *PTy = cast<PackedType>(Ty);
00745       if (va_arg(VA, int) != PTy->getElementType()->getTypeID()) {
00746         CheckFailed("Intrinsic prototype has incorrect vector element type!",F);
00747         break;
00748       }
00749 
00750       if ((unsigned)va_arg(VA, int) != PTy->getNumElements()) {
00751         CheckFailed("Intrinsic prototype has incorrect number of "
00752                     "vector elements!",F);
00753         break;
00754       }
00755     }
00756   }
00757 
00758   va_end(VA);
00759 }
00760 
00761 
00762 //===----------------------------------------------------------------------===//
00763 //  Implement the public interfaces to this file...
00764 //===----------------------------------------------------------------------===//
00765 
00766 FunctionPass *llvm::createVerifierPass(VerifierFailureAction action) {
00767   return new Verifier(action);
00768 }
00769 
00770 
00771 // verifyFunction - Create
00772 bool llvm::verifyFunction(const Function &f, VerifierFailureAction action) {
00773   Function &F = const_cast<Function&>(f);
00774   assert(!F.isExternal() && "Cannot verify external functions");
00775 
00776   FunctionPassManager FPM(new ExistingModuleProvider(F.getParent()));
00777   Verifier *V = new Verifier(action);
00778   FPM.add(V);
00779   FPM.run(F);
00780   return V->Broken;
00781 }
00782 
00783 /// verifyModule - Check a module for errors, printing messages on stderr.
00784 /// Return true if the module is corrupt.
00785 ///
00786 bool llvm::verifyModule(const Module &M, VerifierFailureAction action) {
00787   PassManager PM;
00788   Verifier *V = new Verifier(action);
00789   PM.add(V);
00790   PM.run((Module&)M);
00791   return V->Broken;
00792 }
00793 
00794 // vim: sw=2