LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

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