lib/IR/Verifier.cpp

   1 //===-- Verifier.cpp - Implement the Module Verifier -----------------------==//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines the function verifier interface, that can be used for some
  11 // sanity checking of input to the system.
  12 //
  13 // Note that this does not provide full `Java style' security and verifications,
  14 // instead it just tries to ensure that code is well-formed.
  15 //
  16 //  * Both of a binary operator's parameters are of the same type
  17 //  * Verify that the indices of mem access instructions match other operands
  18 //  * Verify that arithmetic and other things are only performed on first-class
  19 //    types.  Verify that shifts & logicals only happen on integrals f.e.
  20 //  * All of the constants in a switch statement are of the correct type
  21 //  * The code is in valid SSA form
  22 //  * It should be illegal to put a label into any other type (like a structure)
  23 //    or to return one. [except constant arrays!]
  24 //  * Only phi nodes can be self referential: 'add i32 %0, %0 ; <int>:0' is bad
  25 //  * PHI nodes must have an entry for each predecessor, with no extras.
  26 //  * PHI nodes must be the first thing in a basic block, all grouped together
  27 //  * PHI nodes must have at least one entry
  28 //  * All basic blocks should only end with terminator insts, not contain them
  29 //  * The entry node to a function must not have predecessors
  30 //  * All Instructions must be embedded into a basic block
  31 //  * Functions cannot take a void-typed parameter
  32 //  * Verify that a function's argument list agrees with it's declared type.
  33 //  * It is illegal to specify a name for a void value.
  34 //  * It is illegal to have a internal global value with no initializer
  35 //  * It is illegal to have a ret instruction that returns a value that does not
  36 //    agree with the function return value type.
  37 //  * Function call argument types match the function prototype
  38 //  * A landing pad is defined by a landingpad instruction, and can be jumped to
  39 //    only by the unwind edge of an invoke instruction.
  40 //  * A landingpad instruction must be the first non-PHI instruction in the
  41 //    block.
  42 //  * All landingpad instructions must use the same personality function with
  43 //    the same function.
  44 //  * All other things that are tested by asserts spread about the code...
  45 //
  46 //===----------------------------------------------------------------------===//
  47
  48 #include "llvm/Analysis/Verifier.h"
  49 #include "llvm/ADT/STLExtras.h"
  50 #include "llvm/ADT/SetVector.h"
  51 #include "llvm/ADT/SmallPtrSet.h"
  52 #include "llvm/ADT/SmallVector.h"
  53 #include "llvm/ADT/StringExtras.h"
  54 #include "llvm/Analysis/Dominators.h"
  55 #include "llvm/Assembly/Writer.h"
  56 #include "llvm/DebugInfo.h"
  57 #include "llvm/IR/CallingConv.h"
  58 #include "llvm/IR/Constants.h"
  59 #include "llvm/IR/DerivedTypes.h"
  60 #include "llvm/IR/InlineAsm.h"
  61 #include "llvm/IR/IntrinsicInst.h"
  62 #include "llvm/IR/LLVMContext.h"
  63 #include "llvm/IR/Metadata.h"
  64 #include "llvm/IR/Module.h"
  65 #include "llvm/InstVisitor.h"
  66 #include "llvm/Pass.h"
  67 #include "llvm/PassManager.h"
  68 #include "llvm/Support/CFG.h"
  69 #include "llvm/Support/CallSite.h"
  70 #include "llvm/Support/CommandLine.h"
  71 #include "llvm/Support/ConstantRange.h"
  72 #include "llvm/Support/Debug.h"
  73 #include "llvm/Support/ErrorHandling.h"
  74 #include "llvm/Support/raw_ostream.h"
  75 #include <algorithm>
  76 #include <cstdarg>
  77 using namespace llvm;
  78
  79 static cl::opt<bool> DisableDebugInfoVerifier("disable-debug-info-verifier",
  80                                               cl::init(false));
  81
  82 namespace {  // Anonymous namespace for class
  83   struct PreVerifier : public FunctionPass {
  84     static char ID; // Pass ID, replacement for typeid
  85
  86     PreVerifier() : FunctionPass(ID) {
  87       initializePreVerifierPass(*PassRegistry::getPassRegistry());
  88     }
  89
  90     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  91       AU.setPreservesAll();
  92     }
  93
  94     // Check that the prerequisites for successful DominatorTree construction
  95     // are satisfied.
  96     bool runOnFunction(Function &F) {
  97       bool Broken = false;
  98
  99       for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) {
 100         if (I->empty() || !I->back().isTerminator()) {
 101           dbgs() << "Basic Block in function '" << F.getName()
 102                  << "' does not have terminator!\n";
 103           WriteAsOperand(dbgs(), I, true);
 104           dbgs() << "\n";
 105           Broken = true;
 106         }
 107       }
 108
 109       if (Broken)
 110         report_fatal_error("Broken module, no Basic Block terminator!");
 111
 112       return false;
 113     }
 114   };
 115 }
 116
 117 char PreVerifier::ID = 0;
 118 INITIALIZE_PASS(PreVerifier, "preverify", "Preliminary module verification",
 119                 false, false)
 120 static char &PreVerifyID = PreVerifier::ID;
 121
 122 namespace {
 123   struct Verifier : public FunctionPass, public InstVisitor<Verifier> {
 124     static char ID; // Pass ID, replacement for typeid
 125     bool Broken;          // Is this module found to be broken?
 126     VerifierFailureAction action;
 127                           // What to do if verification fails.
 128     Module *Mod;          // Module we are verifying right now
 129     LLVMContext *Context; // Context within which we are verifying
 130     DominatorTree *DT;    // Dominator Tree, caution can be null!
 131
 132     std::string Messages;
 133     raw_string_ostream MessagesStr;
 134
 135     /// InstInThisBlock - when verifying a basic block, keep track of all of the
 136     /// instructions we have seen so far.  This allows us to do efficient
 137     /// dominance checks for the case when an instruction has an operand that is
 138     /// an instruction in the same block.
 139     SmallPtrSet<Instruction*, 16> InstsInThisBlock;
 140
 141     /// MDNodes - keep track of the metadata nodes that have been checked
 142     /// already.
 143     SmallPtrSet<MDNode *, 32> MDNodes;
 144
 145     /// PersonalityFn - The personality function referenced by the
 146     /// LandingPadInsts. All LandingPadInsts within the same function must use
 147     /// the same personality function.
 148     const Value *PersonalityFn;
 149
 150     Verifier()
 151       : FunctionPass(ID), Broken(false),
 152         action(AbortProcessAction), Mod(0), Context(0), DT(0),
 153         MessagesStr(Messages), PersonalityFn(0) {
 154       initializeVerifierPass(*PassRegistry::getPassRegistry());
 155     }
 156     explicit Verifier(VerifierFailureAction ctn)
 157       : FunctionPass(ID), Broken(false), action(ctn), Mod(0),
 158         Context(0), DT(0), MessagesStr(Messages), PersonalityFn(0) {
 159       initializeVerifierPass(*PassRegistry::getPassRegistry());
 160     }
 161
 162     bool doInitialization(Module &M) {
 163       Mod = &M;
 164       Context = &M.getContext();
 165
 166       // We must abort before returning back to the pass manager, or else the
 167       // pass manager may try to run other passes on the broken module.
 168       return abortIfBroken();
 169     }
 170
 171     bool runOnFunction(Function &F) {
 172       // Get dominator information if we are being run by PassManager
 173       DT = &getAnalysis<DominatorTree>();
 174
 175       Mod = F.getParent();
 176       if (!Context) Context = &F.getContext();
 177
 178       visit(F);
 179       InstsInThisBlock.clear();
 180       PersonalityFn = 0;
 181
 182       // We must abort before returning back to the pass manager, or else the
 183       // pass manager may try to run other passes on the broken module.
 184       return abortIfBroken();
 185     }
 186
 187     bool doFinalization(Module &M) {
 188       // Scan through, checking all of the external function's linkage now...
 189       for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) {
 190         visitGlobalValue(*I);
 191
 192         // Check to make sure function prototypes are okay.
 193         if (I->isDeclaration()) visitFunction(*I);
 194       }
 195
 196       for (Module::global_iterator I = M.global_begin(), E = M.global_end();
 197            I != E; ++I)
 198         visitGlobalVariable(*I);
 199
 200       for (Module::alias_iterator I = M.alias_begin(), E = M.alias_end();
 201            I != E; ++I)
 202         visitGlobalAlias(*I);
 203
 204       for (Module::named_metadata_iterator I = M.named_metadata_begin(),
 205            E = M.named_metadata_end(); I != E; ++I)
 206         visitNamedMDNode(*I);
 207
 208       visitModuleFlags(M);
 209
 210       // Verify Debug Info.
 211       verifyDebugInfo(M);
 212
 213       // If the module is broken, abort at this time.
 214       return abortIfBroken();
 215     }
 216
 217     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 218       AU.setPreservesAll();
 219       AU.addRequiredID(PreVerifyID);
 220       AU.addRequired<DominatorTree>();
 221     }
 222
 223     /// abortIfBroken - If the module is broken and we are supposed to abort on
 224     /// this condition, do so.
 225     ///
 226     bool abortIfBroken() {
 227       if (!Broken) return false;
 228       MessagesStr << "Broken module found, ";
 229       switch (action) {
 230       case AbortProcessAction:
 231         MessagesStr << "compilation aborted!\n";
 232         dbgs() << MessagesStr.str();
 233         // Client should choose different reaction if abort is not desired
 234         abort();
 235       case PrintMessageAction:
 236         MessagesStr << "verification continues.\n";
 237         dbgs() << MessagesStr.str();
 238         return false;
 239       case ReturnStatusAction:
 240         MessagesStr << "compilation terminated.\n";
 241         return true;
 242       }
 243       llvm_unreachable("Invalid action");
 244     }
 245
 246
 247     // Verification methods...
 248     void visitGlobalValue(GlobalValue &GV);
 249     void visitGlobalVariable(GlobalVariable &GV);
 250     void visitGlobalAlias(GlobalAlias &GA);
 251     void visitNamedMDNode(NamedMDNode &NMD);
 252     void visitMDNode(MDNode &MD, Function *F);
 253     void visitModuleFlags(Module &M);
 254     void visitModuleFlag(MDNode *Op, DenseMap<MDString*, MDNode*> &SeenIDs,
 255                          SmallVectorImpl<MDNode*> &Requirements);
 256     void visitFunction(Function &F);
 257     void visitBasicBlock(BasicBlock &BB);
 258     using InstVisitor<Verifier>::visit;
 259
 260     void visit(Instruction &I);
 261
 262     void visitTruncInst(TruncInst &I);
 263     void visitZExtInst(ZExtInst &I);
 264     void visitSExtInst(SExtInst &I);
 265     void visitFPTruncInst(FPTruncInst &I);
 266     void visitFPExtInst(FPExtInst &I);
 267     void visitFPToUIInst(FPToUIInst &I);
 268     void visitFPToSIInst(FPToSIInst &I);
 269     void visitUIToFPInst(UIToFPInst &I);
 270     void visitSIToFPInst(SIToFPInst &I);
 271     void visitIntToPtrInst(IntToPtrInst &I);
 272     void visitPtrToIntInst(PtrToIntInst &I);
 273     void visitBitCastInst(BitCastInst &I);
 274     void visitPHINode(PHINode &PN);
 275     void visitBinaryOperator(BinaryOperator &B);
 276     void visitICmpInst(ICmpInst &IC);
 277     void visitFCmpInst(FCmpInst &FC);
 278     void visitExtractElementInst(ExtractElementInst &EI);
 279     void visitInsertElementInst(InsertElementInst &EI);
 280     void visitShuffleVectorInst(ShuffleVectorInst &EI);
 281     void visitVAArgInst(VAArgInst &VAA) { visitInstruction(VAA); }
 282     void visitCallInst(CallInst &CI);
 283     void visitInvokeInst(InvokeInst &II);
 284     void visitGetElementPtrInst(GetElementPtrInst &GEP);
 285     void visitLoadInst(LoadInst &LI);
 286     void visitStoreInst(StoreInst &SI);
 287     void verifyDominatesUse(Instruction &I, unsigned i);
 288     void visitInstruction(Instruction &I);
 289     void visitTerminatorInst(TerminatorInst &I);
 290     void visitBranchInst(BranchInst &BI);
 291     void visitReturnInst(ReturnInst &RI);
 292     void visitSwitchInst(SwitchInst &SI);
 293     void visitIndirectBrInst(IndirectBrInst &BI);
 294     void visitSelectInst(SelectInst &SI);
 295     void visitUserOp1(Instruction &I);
 296     void visitUserOp2(Instruction &I) { visitUserOp1(I); }
 297     void visitIntrinsicFunctionCall(Intrinsic::ID ID, CallInst &CI);
 298     void visitAtomicCmpXchgInst(AtomicCmpXchgInst &CXI);
 299     void visitAtomicRMWInst(AtomicRMWInst &RMWI);
 300     void visitFenceInst(FenceInst &FI);
 301     void visitAllocaInst(AllocaInst &AI);
 302     void visitExtractValueInst(ExtractValueInst &EVI);
 303     void visitInsertValueInst(InsertValueInst &IVI);
 304     void visitLandingPadInst(LandingPadInst &LPI);
 305
 306     void VerifyCallSite(CallSite CS);
 307     bool PerformTypeCheck(Intrinsic::ID ID, Function *F, Type *Ty,
 308                           int VT, unsigned ArgNo, std::string &Suffix);
 309     bool VerifyIntrinsicType(Type *Ty,
 310                              ArrayRef<Intrinsic::IITDescriptor> &Infos,
 311                              SmallVectorImpl<Type*> &ArgTys);
 312     bool VerifyAttributeCount(AttributeSet Attrs, unsigned Params);
 313     void VerifyAttributeTypes(AttributeSet Attrs, unsigned Idx,
 314                               bool isFunction, const Value *V);
 315     void VerifyParameterAttrs(AttributeSet Attrs, unsigned Idx, Type *Ty,
 316                               bool isReturnValue, const Value *V);
 317     void VerifyFunctionAttrs(FunctionType *FT, AttributeSet Attrs,
 318                              const Value *V);
 319
 320     void verifyDebugInfo(Module &M);
 321
 322     void WriteValue(const Value *V) {
 323       if (!V) return;
 324       if (isa<Instruction>(V)) {
 325         MessagesStr << *V << '\n';
 326       } else {
 327         WriteAsOperand(MessagesStr, V, true, Mod);
 328         MessagesStr << '\n';
 329       }
 330     }
 331
 332     void WriteType(Type *T) {
 333       if (!T) return;
 334       MessagesStr << ' ' << *T;
 335     }
 336
 337
 338     // CheckFailed - A check failed, so print out the condition and the message
 339     // that failed.  This provides a nice place to put a breakpoint if you want
 340     // to see why something is not correct.
 341     void CheckFailed(const Twine &Message,
 342                      const Value *V1 = 0, const Value *V2 = 0,
 343                      const Value *V3 = 0, const Value *V4 = 0) {
 344       MessagesStr << Message.str() << "\n";
 345       WriteValue(V1);
 346       WriteValue(V2);
 347       WriteValue(V3);
 348       WriteValue(V4);
 349       Broken = true;
 350     }
 351
 352     void CheckFailed(const Twine &Message, const Value *V1,
 353                      Type *T2, const Value *V3 = 0) {
 354       MessagesStr << Message.str() << "\n";
 355       WriteValue(V1);
 356       WriteType(T2);
 357       WriteValue(V3);
 358       Broken = true;
 359     }
 360
 361     void CheckFailed(const Twine &Message, Type *T1,
 362                      Type *T2 = 0, Type *T3 = 0) {
 363       MessagesStr << Message.str() << "\n";
 364       WriteType(T1);
 365       WriteType(T2);
 366       WriteType(T3);
 367       Broken = true;
 368     }
 369   };
 370 } // End anonymous namespace
 371
 372 char Verifier::ID = 0;
 373 INITIALIZE_PASS_BEGIN(Verifier, "verify", "Module Verifier", false, false)
 374 INITIALIZE_PASS_DEPENDENCY(PreVerifier)
 375 INITIALIZE_PASS_DEPENDENCY(DominatorTree)
 376 INITIALIZE_PASS_END(Verifier, "verify", "Module Verifier", false, false)
 377
 378 // Assert - We know that cond should be true, if not print an error message.
 379 #define Assert(C, M) \
 380   do { if (!(C)) { CheckFailed(M); return; } } while (0)
 381 #define Assert1(C, M, V1) \
 382   do { if (!(C)) { CheckFailed(M, V1); return; } } while (0)
 383 #define Assert2(C, M, V1, V2) \
 384   do { if (!(C)) { CheckFailed(M, V1, V2); return; } } while (0)
 385 #define Assert3(C, M, V1, V2, V3) \
 386   do { if (!(C)) { CheckFailed(M, V1, V2, V3); return; } } while (0)
 387 #define Assert4(C, M, V1, V2, V3, V4) \
 388   do { if (!(C)) { CheckFailed(M, V1, V2, V3, V4); return; } } while (0)
 389
 390 void Verifier::visit(Instruction &I) {
 391   for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i)
 392     Assert1(I.getOperand(i) != 0, "Operand is null", &I);
 393   InstVisitor<Verifier>::visit(I);
 394 }
 395
 396
 397 void Verifier::visitGlobalValue(GlobalValue &GV) {
 398   Assert1(!GV.isDeclaration() ||
 399           GV.isMaterializable() ||
 400           GV.hasExternalLinkage() ||
 401           GV.hasDLLImportLinkage() ||
 402           GV.hasExternalWeakLinkage() ||
 403           (isa<GlobalAlias>(GV) &&
 404            (GV.hasLocalLinkage() || GV.hasWeakLinkage())),
 405   "Global is external, but doesn't have external or dllimport or weak linkage!",
 406           &GV);
 407
 408   Assert1(!GV.hasDLLImportLinkage() || GV.isDeclaration(),
 409           "Global is marked as dllimport, but not external", &GV);
 410
 411   Assert1(!GV.hasAppendingLinkage() || isa<GlobalVariable>(GV),
 412           "Only global variables can have appending linkage!", &GV);
 413
 414   if (GV.hasAppendingLinkage()) {
 415     GlobalVariable *GVar = dyn_cast<GlobalVariable>(&GV);
 416     Assert1(GVar && GVar->getType()->getElementType()->isArrayTy(),
 417             "Only global arrays can have appending linkage!", GVar);
 418   }
 419
 420   Assert1(!GV.hasLinkOnceODRAutoHideLinkage() || GV.hasDefaultVisibility(),
 421           "linkonce_odr_auto_hide can only have default visibility!",
 422           &GV);
 423 }
 424
 425 void Verifier::visitGlobalVariable(GlobalVariable &GV) {
 426   if (GV.hasInitializer()) {
 427     Assert1(GV.getInitializer()->getType() == GV.getType()->getElementType(),
 428             "Global variable initializer type does not match global "
 429             "variable type!", &GV);
 430
 431     // If the global has common linkage, it must have a zero initializer and
 432     // cannot be constant.
 433     if (GV.hasCommonLinkage()) {
 434       Assert1(GV.getInitializer()->isNullValue(),
 435               "'common' global must have a zero initializer!", &GV);
 436       Assert1(!GV.isConstant(), "'common' global may not be marked constant!",
 437               &GV);
 438     }
 439   } else {
 440     Assert1(GV.hasExternalLinkage() || GV.hasDLLImportLinkage() ||
 441             GV.hasExternalWeakLinkage(),
 442             "invalid linkage type for global declaration", &GV);
 443   }
 444
 445   if (GV.hasName() && (GV.getName() == "llvm.global_ctors" ||
 446                        GV.getName() == "llvm.global_dtors")) {
 447     Assert1(!GV.hasInitializer() || GV.hasAppendingLinkage(),
 448             "invalid linkage for intrinsic global variable", &GV);
 449     // Don't worry about emitting an error for it not being an array,
 450     // visitGlobalValue will complain on appending non-array.
 451     if (ArrayType *ATy = dyn_cast<ArrayType>(GV.getType())) {
 452       StructType *STy = dyn_cast<StructType>(ATy->getElementType());
 453       PointerType *FuncPtrTy =
 454           FunctionType::get(Type::getVoidTy(*Context), false)->getPointerTo();
 455       Assert1(STy && STy->getNumElements() == 2 &&
 456               STy->getTypeAtIndex(0u)->isIntegerTy(32) &&
 457               STy->getTypeAtIndex(1) == FuncPtrTy,
 458               "wrong type for intrinsic global variable", &GV);
 459     }
 460   }
 461
 462   if (GV.hasName() && (GV.getName() == "llvm.used" ||
 463                        GV.getName() == "llvm.compiler.used")) {
 464     Assert1(!GV.hasInitializer() || GV.hasAppendingLinkage(),
 465             "invalid linkage for intrinsic global variable", &GV);
 466     Type *GVType = GV.getType()->getElementType();
 467     if (ArrayType *ATy = dyn_cast<ArrayType>(GVType)) {
 468       PointerType *PTy = dyn_cast<PointerType>(ATy->getElementType());
 469       Assert1(PTy, "wrong type for intrinsic global variable", &GV);
 470       if (GV.hasInitializer()) {
 471         Constant *Init = GV.getInitializer();
 472         ConstantArray *InitArray = dyn_cast<ConstantArray>(Init);
 473         Assert1(InitArray, "wrong initalizer for intrinsic global variable",
 474                 Init);
 475         for (unsigned i = 0, e = InitArray->getNumOperands(); i != e; ++i) {
 476           Value *V = Init->getOperand(i)->stripPointerCastsNoFollowAliases();
 477           Assert1(
 478               isa<GlobalVariable>(V) || isa<Function>(V) || isa<GlobalAlias>(V),
 479               "invalid llvm.used member", V);
 480           Assert1(V->hasName(), "members of llvm.used must be named", V);
 481         }
 482       }
 483     }
 484   }
 485
 486   visitGlobalValue(GV);
 487 }
 488
 489 void Verifier::visitGlobalAlias(GlobalAlias &GA) {
 490   Assert1(!GA.getName().empty(),
 491           "Alias name cannot be empty!", &GA);
 492   Assert1(GA.hasExternalLinkage() || GA.hasLocalLinkage() ||
 493           GA.hasWeakLinkage(),
 494           "Alias should have external or external weak linkage!", &GA);
 495   Assert1(GA.getAliasee(),
 496           "Aliasee cannot be NULL!", &GA);
 497   Assert1(GA.getType() == GA.getAliasee()->getType(),
 498           "Alias and aliasee types should match!", &GA);
 499   Assert1(!GA.hasUnnamedAddr(), "Alias cannot have unnamed_addr!", &GA);
 500
 501   Constant *Aliasee = GA.getAliasee();
 502
 503   if (!isa<GlobalValue>(Aliasee)) {
 504     ConstantExpr *CE = dyn_cast<ConstantExpr>(Aliasee);
 505     Assert1(CE &&
 506             (CE->getOpcode() == Instruction::BitCast ||
 507              CE->getOpcode() == Instruction::GetElementPtr) &&
 508             isa<GlobalValue>(CE->getOperand(0)),
 509             "Aliasee should be either GlobalValue or bitcast of GlobalValue",
 510             &GA);
 511
 512     if (CE->getOpcode() == Instruction::BitCast) {
 513       unsigned SrcAS = CE->getOperand(0)->getType()->getPointerAddressSpace();
 514       unsigned DstAS = CE->getType()->getPointerAddressSpace();
 515
 516       Assert1(SrcAS == DstAS,
 517               "Alias bitcasts cannot be between different address spaces",
 518               &GA);
 519     }
 520   }
 521
 522   const GlobalValue* Resolved = GA.resolveAliasedGlobal(/*stopOnWeak*/ false);
 523   Assert1(Resolved,
 524           "Aliasing chain should end with function or global variable", &GA);
 525
 526   visitGlobalValue(GA);
 527 }
 528
 529 void Verifier::visitNamedMDNode(NamedMDNode &NMD) {
 530   for (unsigned i = 0, e = NMD.getNumOperands(); i != e; ++i) {
 531     MDNode *MD = NMD.getOperand(i);
 532     if (!MD)
 533       continue;
 534
 535     Assert1(!MD->isFunctionLocal(),
 536             "Named metadata operand cannot be function local!", MD);
 537     visitMDNode(*MD, 0);
 538   }
 539 }
 540
 541 void Verifier::visitMDNode(MDNode &MD, Function *F) {
 542   // Only visit each node once.  Metadata can be mutually recursive, so this
 543   // avoids infinite recursion here, as well as being an optimization.
 544   if (!MDNodes.insert(&MD))
 545     return;
 546
 547   for (unsigned i = 0, e = MD.getNumOperands(); i != e; ++i) {
 548     Value *Op = MD.getOperand(i);
 549     if (!Op)
 550       continue;
 551     if (isa<Constant>(Op) || isa<MDString>(Op))
 552       continue;
 553     if (MDNode *N = dyn_cast<MDNode>(Op)) {
 554       Assert2(MD.isFunctionLocal() || !N->isFunctionLocal(),
 555               "Global metadata operand cannot be function local!", &MD, N);
 556       visitMDNode(*N, F);
 557       continue;
 558     }
 559     Assert2(MD.isFunctionLocal(), "Invalid operand for global metadata!", &MD, Op);
 560
 561     // If this was an instruction, bb, or argument, verify that it is in the
 562     // function that we expect.
 563     Function *ActualF = 0;
 564     if (Instruction *I = dyn_cast<Instruction>(Op))
 565       ActualF = I->getParent()->getParent();
 566     else if (BasicBlock *BB = dyn_cast<BasicBlock>(Op))
 567       ActualF = BB->getParent();
 568     else if (Argument *A = dyn_cast<Argument>(Op))
 569       ActualF = A->getParent();
 570     assert(ActualF && "Unimplemented function local metadata case!");
 571
 572     Assert2(ActualF == F, "function-local metadata used in wrong function",
 573             &MD, Op);
 574   }
 575 }
 576
 577 void Verifier::visitModuleFlags(Module &M) {
 578   const NamedMDNode *Flags = M.getModuleFlagsMetadata();
 579   if (!Flags) return;
 580
 581   // Scan each flag, and track the flags and requirements.
 582   DenseMap<MDString*, MDNode*> SeenIDs;
 583   SmallVector<MDNode*, 16> Requirements;
 584   for (unsigned I = 0, E = Flags->getNumOperands(); I != E; ++I) {
 585     visitModuleFlag(Flags->getOperand(I), SeenIDs, Requirements);
 586   }
 587
 588   // Validate that the requirements in the module are valid.
 589   for (unsigned I = 0, E = Requirements.size(); I != E; ++I) {
 590     MDNode *Requirement = Requirements[I];
 591     MDString *Flag = cast<MDString>(Requirement->getOperand(0));
 592     Value *ReqValue = Requirement->getOperand(1);
 593
 594     MDNode *Op = SeenIDs.lookup(Flag);
 595     if (!Op) {
 596       CheckFailed("invalid requirement on flag, flag is not present in module",
 597                   Flag);
 598       continue;
 599     }
 600
 601     if (Op->getOperand(2) != ReqValue) {
 602       CheckFailed(("invalid requirement on flag, "
 603                    "flag does not have the required value"),
 604                   Flag);
 605       continue;
 606     }
 607   }
 608 }
 609
 610 void Verifier::visitModuleFlag(MDNode *Op, DenseMap<MDString*, MDNode*>&SeenIDs,
 611                                SmallVectorImpl<MDNode*> &Requirements) {
 612   // Each module flag should have three arguments, the merge behavior (a
 613   // constant int), the flag ID (an MDString), and the value.
 614   Assert1(Op->getNumOperands() == 3,
 615           "incorrect number of operands in module flag", Op);
 616   ConstantInt *Behavior = dyn_cast<ConstantInt>(Op->getOperand(0));
 617   MDString *ID = dyn_cast<MDString>(Op->getOperand(1));
 618   Assert1(Behavior,
 619           "invalid behavior operand in module flag (expected constant integer)",
 620           Op->getOperand(0));
 621   unsigned BehaviorValue = Behavior->getZExtValue();
 622   Assert1(ID,
 623           "invalid ID operand in module flag (expected metadata string)",
 624           Op->getOperand(1));
 625
 626   // Sanity check the values for behaviors with additional requirements.
 627   switch (BehaviorValue) {
 628   default:
 629     Assert1(false,
 630             "invalid behavior operand in module flag (unexpected constant)",
 631             Op->getOperand(0));
 632     break;
 633
 634   case Module::Error:
 635   case Module::Warning:
 636   case Module::Override:
 637     // These behavior types accept any value.
 638     break;
 639
 640   case Module::Require: {
 641     // The value should itself be an MDNode with two operands, a flag ID (an
 642     // MDString), and a value.
 643     MDNode *Value = dyn_cast<MDNode>(Op->getOperand(2));
 644     Assert1(Value && Value->getNumOperands() == 2,
 645             "invalid value for 'require' module flag (expected metadata pair)",
 646             Op->getOperand(2));
 647     Assert1(isa<MDString>(Value->getOperand(0)),
 648             ("invalid value for 'require' module flag "
 649              "(first value operand should be a string)"),
 650             Value->getOperand(0));
 651
 652     // Append it to the list of requirements, to check once all module flags are
 653     // scanned.
 654     Requirements.push_back(Value);
 655     break;
 656   }
 657
 658   case Module::Append:
 659   case Module::AppendUnique: {
 660     // These behavior types require the operand be an MDNode.
 661     Assert1(isa<MDNode>(Op->getOperand(2)),
 662             "invalid value for 'append'-type module flag "
 663             "(expected a metadata node)", Op->getOperand(2));
 664     break;
 665   }
 666   }
 667
 668   // Unless this is a "requires" flag, check the ID is unique.
 669   if (BehaviorValue != Module::Require) {
 670     bool Inserted = SeenIDs.insert(std::make_pair(ID, Op)).second;
 671     Assert1(Inserted,
 672             "module flag identifiers must be unique (or of 'require' type)",
 673             ID);
 674   }
 675 }
 676
 677 void Verifier::VerifyAttributeTypes(AttributeSet Attrs, unsigned Idx,
 678                                     bool isFunction, const Value *V) {
 679   unsigned Slot = ~0U;
 680   for (unsigned I = 0, E = Attrs.getNumSlots(); I != E; ++I)
 681     if (Attrs.getSlotIndex(I) == Idx) {
 682       Slot = I;
 683       break;
 684     }
 685
 686   assert(Slot != ~0U && "Attribute set inconsistency!");
 687
 688   for (AttributeSet::iterator I = Attrs.begin(Slot), E = Attrs.end(Slot);
 689          I != E; ++I) {
 690     if (I->isStringAttribute())
 691       continue;
 692
 693     if (I->getKindAsEnum() == Attribute::NoReturn ||
 694         I->getKindAsEnum() == Attribute::NoUnwind ||
 695         I->getKindAsEnum() == Attribute::NoInline ||
 696         I->getKindAsEnum() == Attribute::AlwaysInline ||
 697         I->getKindAsEnum() == Attribute::OptimizeForSize ||
 698         I->getKindAsEnum() == Attribute::StackProtect ||
 699         I->getKindAsEnum() == Attribute::StackProtectReq ||
 700         I->getKindAsEnum() == Attribute::StackProtectStrong ||
 701         I->getKindAsEnum() == Attribute::NoRedZone ||
 702         I->getKindAsEnum() == Attribute::NoImplicitFloat ||
 703         I->getKindAsEnum() == Attribute::Naked ||
 704         I->getKindAsEnum() == Attribute::InlineHint ||
 705         I->getKindAsEnum() == Attribute::StackAlignment ||
 706         I->getKindAsEnum() == Attribute::UWTable ||
 707         I->getKindAsEnum() == Attribute::NonLazyBind ||
 708         I->getKindAsEnum() == Attribute::ReturnsTwice ||
 709         I->getKindAsEnum() == Attribute::SanitizeAddress ||
 710         I->getKindAsEnum() == Attribute::SanitizeThread ||
 711         I->getKindAsEnum() == Attribute::SanitizeMemory ||
 712         I->getKindAsEnum() == Attribute::MinSize ||
 713         I->getKindAsEnum() == Attribute::NoDuplicate ||
 714         I->getKindAsEnum() == Attribute::Builtin ||
 715         I->getKindAsEnum() == Attribute::NoBuiltin ||
 716         I->getKindAsEnum() == Attribute::Cold) {
 717       if (!isFunction) {
 718         CheckFailed("Attribute '" + I->getAsString() +
 719                     "' only applies to functions!", V);
 720         return;
 721       }
 722     } else if (I->getKindAsEnum() == Attribute::ReadOnly ||
 723                I->getKindAsEnum() == Attribute::ReadNone) {
 724       if (Idx == 0) {
 725         CheckFailed("Attribute '" + I->getAsString() +
 726                     "' does not apply to function returns");
 727         return;
 728       }
 729     } else if (isFunction) {
 730       CheckFailed("Attribute '" + I->getAsString() +
 731                   "' does not apply to functions!", V);
 732       return;
 733     }
 734   }
 735 }
 736
 737 // VerifyParameterAttrs - Check the given attributes for an argument or return
 738 // value of the specified type.  The value V is printed in error messages.
 739 void Verifier::VerifyParameterAttrs(AttributeSet Attrs, unsigned Idx, Type *Ty,
 740                                     bool isReturnValue, const Value *V) {
 741   if (!Attrs.hasAttributes(Idx))
 742     return;
 743
 744   VerifyAttributeTypes(Attrs, Idx, false, V);
 745
 746   if (isReturnValue)
 747     Assert1(!Attrs.hasAttribute(Idx, Attribute::ByVal) &&
 748             !Attrs.hasAttribute(Idx, Attribute::Nest) &&
 749             !Attrs.hasAttribute(Idx, Attribute::StructRet) &&
 750             !Attrs.hasAttribute(Idx, Attribute::NoCapture) &&
 751             !Attrs.hasAttribute(Idx, Attribute::Returned),
 752             "Attribute 'byval', 'nest', 'sret', 'nocapture', and 'returned' "
 753             "do not apply to return values!", V);
 754
 755   // Check for mutually incompatible attributes.
 756   Assert1(!((Attrs.hasAttribute(Idx, Attribute::ByVal) &&
 757              Attrs.hasAttribute(Idx, Attribute::Nest)) ||
 758             (Attrs.hasAttribute(Idx, Attribute::ByVal) &&
 759              Attrs.hasAttribute(Idx, Attribute::StructRet)) ||
 760             (Attrs.hasAttribute(Idx, Attribute::Nest) &&
 761              Attrs.hasAttribute(Idx, Attribute::StructRet))), "Attributes "
 762           "'byval, nest, and sret' are incompatible!", V);
 763
 764   Assert1(!((Attrs.hasAttribute(Idx, Attribute::ByVal) &&
 765              Attrs.hasAttribute(Idx, Attribute::Nest)) ||
 766             (Attrs.hasAttribute(Idx, Attribute::ByVal) &&
 767              Attrs.hasAttribute(Idx, Attribute::InReg)) ||
 768             (Attrs.hasAttribute(Idx, Attribute::Nest) &&
 769              Attrs.hasAttribute(Idx, Attribute::InReg))), "Attributes "
 770           "'byval, nest, and inreg' are incompatible!", V);
 771
 772   Assert1(!(Attrs.hasAttribute(Idx, Attribute::StructRet) &&
 773             Attrs.hasAttribute(Idx, Attribute::Returned)), "Attributes "
 774           "'sret and returned' are incompatible!", V);
 775
 776   Assert1(!(Attrs.hasAttribute(Idx, Attribute::ZExt) &&
 777             Attrs.hasAttribute(Idx, Attribute::SExt)), "Attributes "
 778           "'zeroext and signext' are incompatible!", V);
 779
 780   Assert1(!(Attrs.hasAttribute(Idx, Attribute::ReadNone) &&
 781             Attrs.hasAttribute(Idx, Attribute::ReadOnly)), "Attributes "
 782           "'readnone and readonly' are incompatible!", V);
 783
 784   Assert1(!(Attrs.hasAttribute(Idx, Attribute::NoInline) &&
 785             Attrs.hasAttribute(Idx, Attribute::AlwaysInline)), "Attributes "
 786           "'noinline and alwaysinline' are incompatible!", V);
 787
 788   Assert1(!AttrBuilder(Attrs, Idx).
 789             hasAttributes(AttributeFuncs::typeIncompatible(Ty, Idx), Idx),
 790           "Wrong types for attribute: " +
 791           AttributeFuncs::typeIncompatible(Ty, Idx).getAsString(Idx), V);
 792
 793   if (PointerType *PTy = dyn_cast<PointerType>(Ty))
 794     Assert1(!Attrs.hasAttribute(Idx, Attribute::ByVal) ||
 795             PTy->getElementType()->isSized(),
 796             "Attribute 'byval' does not support unsized types!", V);
 797   else
 798     Assert1(!Attrs.hasAttribute(Idx, Attribute::ByVal),
 799             "Attribute 'byval' only applies to parameters with pointer type!",
 800             V);
 801 }
 802
 803 // VerifyFunctionAttrs - Check parameter attributes against a function type.
 804 // The value V is printed in error messages.
 805 void Verifier::VerifyFunctionAttrs(FunctionType *FT, AttributeSet Attrs,
 806                                    const Value *V) {
 807   if (Attrs.isEmpty())
 808     return;
 809
 810   bool SawNest = false;
 811   bool SawReturned = false;
 812
 813   for (unsigned i = 0, e = Attrs.getNumSlots(); i != e; ++i) {
 814     unsigned Idx = Attrs.getSlotIndex(i);
 815
 816     Type *Ty;
 817     if (Idx == 0)
 818       Ty = FT->getReturnType();
 819     else if (Idx-1 < FT->getNumParams())
 820       Ty = FT->getParamType(Idx-1);
 821     else
 822       break;  // VarArgs attributes, verified elsewhere.
 823
 824     VerifyParameterAttrs(Attrs, Idx, Ty, Idx == 0, V);
 825
 826     if (Idx == 0)
 827       continue;
 828
 829     if (Attrs.hasAttribute(Idx, Attribute::Nest)) {
 830       Assert1(!SawNest, "More than one parameter has attribute nest!", V);
 831       SawNest = true;
 832     }
 833
 834     if (Attrs.hasAttribute(Idx, Attribute::Returned)) {
 835       Assert1(!SawReturned, "More than one parameter has attribute returned!",
 836               V);
 837       Assert1(Ty->canLosslesslyBitCastTo(FT->getReturnType()), "Incompatible "
 838               "argument and return types for 'returned' attribute", V);
 839       SawReturned = true;
 840     }
 841
 842     if (Attrs.hasAttribute(Idx, Attribute::StructRet))
 843       Assert1(Idx == 1, "Attribute sret is not on first parameter!", V);
 844   }
 845
 846   if (!Attrs.hasAttributes(AttributeSet::FunctionIndex))
 847     return;
 848
 849   VerifyAttributeTypes(Attrs, AttributeSet::FunctionIndex, true, V);
 850
 851   Assert1(!(Attrs.hasAttribute(AttributeSet::FunctionIndex,
 852                                Attribute::ReadNone) &&
 853             Attrs.hasAttribute(AttributeSet::FunctionIndex,
 854                                Attribute::ReadOnly)),
 855           "Attributes 'readnone and readonly' are incompatible!", V);
 856
 857   Assert1(!(Attrs.hasAttribute(AttributeSet::FunctionIndex,
 858                                Attribute::NoInline) &&
 859             Attrs.hasAttribute(AttributeSet::FunctionIndex,
 860                                Attribute::AlwaysInline)),
 861           "Attributes 'noinline and alwaysinline' are incompatible!", V);
 862 }
 863
 864 bool Verifier::VerifyAttributeCount(AttributeSet Attrs, unsigned Params) {
 865   if (Attrs.getNumSlots() == 0)
 866     return true;
 867
 868   unsigned LastSlot = Attrs.getNumSlots() - 1;
 869   unsigned LastIndex = Attrs.getSlotIndex(LastSlot);
 870   if (LastIndex <= Params
 871       || (LastIndex == AttributeSet::FunctionIndex
 872           && (LastSlot == 0 || Attrs.getSlotIndex(LastSlot - 1) <= Params)))
 873     return true;
 874
 875   return false;
 876 }
 877
 878 // visitFunction - Verify that a function is ok.
 879 //
 880 void Verifier::visitFunction(Function &F) {
 881   // Check function arguments.
 882   FunctionType *FT = F.getFunctionType();
 883   unsigned NumArgs = F.arg_size();
 884
 885   Assert1(Context == &F.getContext(),
 886           "Function context does not match Module context!", &F);
 887
 888   Assert1(!F.hasCommonLinkage(), "Functions may not have common linkage", &F);
 889   Assert2(FT->getNumParams() == NumArgs,
 890           "# formal arguments must match # of arguments for function type!",
 891           &F, FT);
 892   Assert1(F.getReturnType()->isFirstClassType() ||
 893           F.getReturnType()->isVoidTy() ||
 894           F.getReturnType()->isStructTy(),
 895           "Functions cannot return aggregate values!", &F);
 896
 897   Assert1(!F.hasStructRetAttr() || F.getReturnType()->isVoidTy(),
 898           "Invalid struct return type!", &F);
 899
 900   AttributeSet Attrs = F.getAttributes();
 901
 902   Assert1(VerifyAttributeCount(Attrs, FT->getNumParams()),
 903           "Attribute after last parameter!", &F);
 904
 905   // Check function attributes.
 906   VerifyFunctionAttrs(FT, Attrs, &F);
 907
 908   // On function declarations/definitions, we do not support the builtin
 909   // attribute. We do not check this in VerifyFunctionAttrs since that is
 910   // checking for Attributes that can/can not ever be on functions.
 911   Assert1(!Attrs.hasAttribute(AttributeSet::FunctionIndex,
 912                               Attribute::Builtin),
 913           "Attribute 'builtin' can only be applied to a callsite.", &F);
 914
 915   // Check that this function meets the restrictions on this calling convention.
 916   switch (F.getCallingConv()) {
 917   default:
 918     break;
 919   case CallingConv::C:
 920     break;
 921   case CallingConv::Fast:
 922   case CallingConv::Cold:
 923   case CallingConv::X86_FastCall:
 924   case CallingConv::X86_ThisCall:
 925   case CallingConv::Intel_OCL_BI:
 926   case CallingConv::PTX_Kernel:
 927   case CallingConv::PTX_Device:
 928     Assert1(!F.isVarArg(),
 929             "Varargs functions must have C calling conventions!", &F);
 930     break;
 931   }
 932
 933   bool isLLVMdotName = F.getName().size() >= 5 &&
 934                        F.getName().substr(0, 5) == "llvm.";
 935
 936   // Check that the argument values match the function type for this function...
 937   unsigned i = 0;
 938   for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end();
 939        I != E; ++I, ++i) {
 940     Assert2(I->getType() == FT->getParamType(i),
 941             "Argument value does not match function argument type!",
 942             I, FT->getParamType(i));
 943     Assert1(I->getType()->isFirstClassType(),
 944             "Function arguments must have first-class types!", I);
 945     if (!isLLVMdotName)
 946       Assert2(!I->getType()->isMetadataTy(),
 947               "Function takes metadata but isn't an intrinsic", I, &F);
 948   }
 949
 950   if (F.isMaterializable()) {
 951     // Function has a body somewhere we can't see.
 952   } else if (F.isDeclaration()) {
 953     Assert1(F.hasExternalLinkage() || F.hasDLLImportLinkage() ||
 954             F.hasExternalWeakLinkage(),
 955             "invalid linkage type for function declaration", &F);
 956   } else {
 957     // Verify that this function (which has a body) is not named "llvm.*".  It
 958     // is not legal to define intrinsics.
 959     Assert1(!isLLVMdotName, "llvm intrinsics cannot be defined!", &F);
 960
 961     // Check the entry node
 962     BasicBlock *Entry = &F.getEntryBlock();
 963     Assert1(pred_begin(Entry) == pred_end(Entry),
 964             "Entry block to function must not have predecessors!", Entry);
 965
 966     // The address of the entry block cannot be taken, unless it is dead.
 967     if (Entry->hasAddressTaken()) {
 968       Assert1(!BlockAddress::get(Entry)->isConstantUsed(),
 969               "blockaddress may not be used with the entry block!", Entry);
 970     }
 971   }
 972
 973   // If this function is actually an intrinsic, verify that it is only used in
 974   // direct call/invokes, never having its "address taken".
 975   if (F.getIntrinsicID()) {
 976     const User *U;
 977     if (F.hasAddressTaken(&U))
 978       Assert1(0, "Invalid user of intrinsic instruction!", U);
 979   }
 980 }
 981
 982 // verifyBasicBlock - Verify that a basic block is well formed...
 983 //
 984 void Verifier::visitBasicBlock(BasicBlock &BB) {
 985   InstsInThisBlock.clear();
 986
 987   // Ensure that basic blocks have terminators!
 988   Assert1(BB.getTerminator(), "Basic Block does not have terminator!", &BB);
 989
 990   // Check constraints that this basic block imposes on all of the PHI nodes in
 991   // it.
 992   if (isa<PHINode>(BB.front())) {
 993     SmallVector<BasicBlock*, 8> Preds(pred_begin(&BB), pred_end(&BB));
 994     SmallVector<std::pair<BasicBlock*, Value*>, 8> Values;
 995     std::sort(Preds.begin(), Preds.end());
 996     PHINode *PN;
 997     for (BasicBlock::iterator I = BB.begin(); (PN = dyn_cast<PHINode>(I));++I) {
 998       // Ensure that PHI nodes have at least one entry!
 999       Assert1(PN->getNumIncomingValues() != 0,
1000               "PHI nodes must have at least one entry.  If the block is dead, "
1001               "the PHI should be removed!", PN);
1002       Assert1(PN->getNumIncomingValues() == Preds.size(),
1003               "PHINode should have one entry for each predecessor of its "
1004               "parent basic block!", PN);
1005
1006       // Get and sort all incoming values in the PHI node...
1007       Values.clear();
1008       Values.reserve(PN->getNumIncomingValues());
1009       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
1010         Values.push_back(std::make_pair(PN->getIncomingBlock(i),
1011                                         PN->getIncomingValue(i)));
1012       std::sort(Values.begin(), Values.end());
1013
1014       for (unsigned i = 0, e = Values.size(); i != e; ++i) {
1015         // Check to make sure that if there is more than one entry for a
1016         // particular basic block in this PHI node, that the incoming values are
1017         // all identical.
1018         //
1019         Assert4(i == 0 || Values[i].first  != Values[i-1].first ||
1020                 Values[i].second == Values[i-1].second,
1021                 "PHI node has multiple entries for the same basic block with "
1022                 "different incoming values!", PN, Values[i].first,
1023                 Values[i].second, Values[i-1].second);
1024
1025         // Check to make sure that the predecessors and PHI node entries are
1026         // matched up.
1027         Assert3(Values[i].first == Preds[i],
1028                 "PHI node entries do not match predecessors!", PN,
1029                 Values[i].first, Preds[i]);
1030       }
1031     }
1032   }
1033 }
1034
1035 void Verifier::visitTerminatorInst(TerminatorInst &I) {
1036   // Ensure that terminators only exist at the end of the basic block.
1037   Assert1(&I == I.getParent()->getTerminator(),
1038           "Terminator found in the middle of a basic block!", I.getParent());
1039   visitInstruction(I);
1040 }
1041
1042 void Verifier::visitBranchInst(BranchInst &BI) {
1043   if (BI.isConditional()) {
1044     Assert2(BI.getCondition()->getType()->isIntegerTy(1),
1045             "Branch condition is not 'i1' type!", &BI, BI.getCondition());
1046   }
1047   visitTerminatorInst(BI);
1048 }
1049
1050 void Verifier::visitReturnInst(ReturnInst &RI) {
1051   Function *F = RI.getParent()->getParent();
1052   unsigned N = RI.getNumOperands();
1053   if (F->getReturnType()->isVoidTy())
1054     Assert2(N == 0,
1055             "Found return instr that returns non-void in Function of void "
1056             "return type!", &RI, F->getReturnType());
1057   else
1058     Assert2(N == 1 && F->getReturnType() == RI.getOperand(0)->getType(),
1059             "Function return type does not match operand "
1060             "type of return inst!", &RI, F->getReturnType());
1061
1062   // Check to make sure that the return value has necessary properties for
1063   // terminators...
1064   visitTerminatorInst(RI);
1065 }
1066
1067 void Verifier::visitSwitchInst(SwitchInst &SI) {
1068   // Check to make sure that all of the constants in the switch instruction
1069   // have the same type as the switched-on value.
1070   Type *SwitchTy = SI.getCondition()->getType();
1071   IntegerType *IntTy = cast<IntegerType>(SwitchTy);
1072   IntegersSubsetToBB Mapping;
1073   std::map<IntegersSubset::Range, unsigned> RangeSetMap;
1074   for (SwitchInst::CaseIt i = SI.case_begin(), e = SI.case_end(); i != e; ++i) {
1075     IntegersSubset CaseRanges = i.getCaseValueEx();
1076     for (unsigned ri = 0, rie = CaseRanges.getNumItems(); ri < rie; ++ri) {
1077       IntegersSubset::Range r = CaseRanges.getItem(ri);
1078       Assert1(((const APInt&)r.getLow()).getBitWidth() == IntTy->getBitWidth(),
1079               "Switch constants must all be same type as switch value!", &SI);
1080       Assert1(((const APInt&)r.getHigh()).getBitWidth() == IntTy->getBitWidth(),
1081               "Switch constants must all be same type as switch value!", &SI);
1082       Mapping.add(r);
1083       RangeSetMap[r] = i.getCaseIndex();
1084     }
1085   }
1086
1087   IntegersSubsetToBB::RangeIterator errItem;
1088   if (!Mapping.verify(errItem)) {
1089     unsigned CaseIndex = RangeSetMap[errItem->first];
1090     SwitchInst::CaseIt i(&SI, CaseIndex);
1091     Assert2(false, "Duplicate integer as switch case", &SI, i.getCaseValueEx());
1092   }
1093
1094   visitTerminatorInst(SI);
1095 }
1096
1097 void Verifier::visitIndirectBrInst(IndirectBrInst &BI) {
1098   Assert1(BI.getAddress()->getType()->isPointerTy(),
1099           "Indirectbr operand must have pointer type!", &BI);
1100   for (unsigned i = 0, e = BI.getNumDestinations(); i != e; ++i)
1101     Assert1(BI.getDestination(i)->getType()->isLabelTy(),
1102             "Indirectbr destinations must all have pointer type!", &BI);
1103
1104   visitTerminatorInst(BI);
1105 }
1106
1107 void Verifier::visitSelectInst(SelectInst &SI) {
1108   Assert1(!SelectInst::areInvalidOperands(SI.getOperand(0), SI.getOperand(1),
1109                                           SI.getOperand(2)),
1110           "Invalid operands for select instruction!", &SI);
1111
1112   Assert1(SI.getTrueValue()->getType() == SI.getType(),
1113           "Select values must have same type as select instruction!", &SI);
1114   visitInstruction(SI);
1115 }
1116
1117 /// visitUserOp1 - User defined operators shouldn't live beyond the lifetime of
1118 /// a pass, if any exist, it's an error.
1119 ///
1120 void Verifier::visitUserOp1(Instruction &I) {
1121   Assert1(0, "User-defined operators should not live outside of a pass!", &I);
1122 }
1123
1124 void Verifier::visitTruncInst(TruncInst &I) {
1125   // Get the source and destination types
1126   Type *SrcTy = I.getOperand(0)->getType();
1127   Type *DestTy = I.getType();
1128
1129   // Get the size of the types in bits, we'll need this later
1130   unsigned SrcBitSize = SrcTy->getScalarSizeInBits();
1131   unsigned DestBitSize = DestTy->getScalarSizeInBits();
1132
1133   Assert1(SrcTy->isIntOrIntVectorTy(), "Trunc only operates on integer", &I);
1134   Assert1(DestTy->isIntOrIntVectorTy(), "Trunc only produces integer", &I);
1135   Assert1(SrcTy->isVectorTy() == DestTy->isVectorTy(),
1136           "trunc source and destination must both be a vector or neither", &I);
1137   Assert1(SrcBitSize > DestBitSize,"DestTy too big for Trunc", &I);
1138
1139   visitInstruction(I);
1140 }
1141
1142 void Verifier::visitZExtInst(ZExtInst &I) {
1143   // Get the source and destination types
1144   Type *SrcTy = I.getOperand(0)->getType();
1145   Type *DestTy = I.getType();
1146
1147   // Get the size of the types in bits, we'll need this later
1148   Assert1(SrcTy->isIntOrIntVectorTy(), "ZExt only operates on integer", &I);
1149   Assert1(DestTy->isIntOrIntVectorTy(), "ZExt only produces an integer", &I);
1150   Assert1(SrcTy->isVectorTy() == DestTy->isVectorTy(),
1151           "zext source and destination must both be a vector or neither", &I);
1152   unsigned SrcBitSize = SrcTy->getScalarSizeInBits();
1153   unsigned DestBitSize = DestTy->getScalarSizeInBits();
1154
1155   Assert1(SrcBitSize < DestBitSize,"Type too small for ZExt", &I);
1156
1157   visitInstruction(I);
1158 }
1159
1160 void Verifier::visitSExtInst(SExtInst &I) {
1161   // Get the source and destination types
1162   Type *SrcTy = I.getOperand(0)->getType();
1163   Type *DestTy = I.getType();
1164
1165   // Get the size of the types in bits, we'll need this later
1166   unsigned SrcBitSize = SrcTy->getScalarSizeInBits();
1167   unsigned DestBitSize = DestTy->getScalarSizeInBits();
1168
1169   Assert1(SrcTy->isIntOrIntVectorTy(), "SExt only operates on integer", &I);
1170   Assert1(DestTy->isIntOrIntVectorTy(), "SExt only produces an integer", &I);
1171   Assert1(SrcTy->isVectorTy() == DestTy->isVectorTy(),
1172           "sext source and destination must both be a vector or neither", &I);
1173   Assert1(SrcBitSize < DestBitSize,"Type too small for SExt", &I);
1174
1175   visitInstruction(I);
1176 }
1177
1178 void Verifier::visitFPTruncInst(FPTruncInst &I) {
1179   // Get the source and destination types
1180   Type *SrcTy = I.getOperand(0)->getType();
1181   Type *DestTy = I.getType();
1182   // Get the size of the types in bits, we'll need this later
1183   unsigned SrcBitSize = SrcTy->getScalarSizeInBits();
1184   unsigned DestBitSize = DestTy->getScalarSizeInBits();
1185
1186   Assert1(SrcTy->isFPOrFPVectorTy(),"FPTrunc only operates on FP", &I);
1187   Assert1(DestTy->isFPOrFPVectorTy(),"FPTrunc only produces an FP", &I);
1188   Assert1(SrcTy->isVectorTy() == DestTy->isVectorTy(),
1189           "fptrunc source and destination must both be a vector or neither",&I);
1190   Assert1(SrcBitSize > DestBitSize,"DestTy too big for FPTrunc", &I);
1191
1192   visitInstruction(I);
1193 }
1194
1195 void Verifier::visitFPExtInst(FPExtInst &I) {
1196   // Get the source and destination types
1197   Type *SrcTy = I.getOperand(0)->getType();
1198   Type *DestTy = I.getType();
1199
1200   // Get the size of the types in bits, we'll need this later
1201   unsigned SrcBitSize = SrcTy->getScalarSizeInBits();
1202   unsigned DestBitSize = DestTy->getScalarSizeInBits();
1203
1204   Assert1(SrcTy->isFPOrFPVectorTy(),"FPExt only operates on FP", &I);
1205   Assert1(DestTy->isFPOrFPVectorTy(),"FPExt only produces an FP", &I);
1206   Assert1(SrcTy->isVectorTy() == DestTy->isVectorTy(),
1207           "fpext source and destination must both be a vector or neither", &I);
1208   Assert1(SrcBitSize < DestBitSize,"DestTy too small for FPExt", &I);
1209
1210   visitInstruction(I);
1211 }
1212
1213 void Verifier::visitUIToFPInst(UIToFPInst &I) {
1214   // Get the source and destination types
1215   Type *SrcTy = I.getOperand(0)->getType();
1216   Type *DestTy = I.getType();
1217
1218   bool SrcVec = SrcTy->isVectorTy();
1219   bool DstVec = DestTy->isVectorTy();
1220
1221   Assert1(SrcVec == DstVec,
1222           "UIToFP source and dest must both be vector or scalar", &I);
1223   Assert1(SrcTy->isIntOrIntVectorTy(),
1224           "UIToFP source must be integer or integer vector", &I);
1225   Assert1(DestTy->isFPOrFPVectorTy(),
1226           "UIToFP result must be FP or FP vector", &I);
1227
1228   if (SrcVec && DstVec)
1229     Assert1(cast<VectorType>(SrcTy)->getNumElements() ==
1230             cast<VectorType>(DestTy)->getNumElements(),
1231             "UIToFP source and dest vector length mismatch", &I);
1232
1233   visitInstruction(I);
1234 }
1235
1236 void Verifier::visitSIToFPInst(SIToFPInst &I) {
1237   // Get the source and destination types
1238   Type *SrcTy = I.getOperand(0)->getType();
1239   Type *DestTy = I.getType();
1240
1241   bool SrcVec = SrcTy->isVectorTy();
1242   bool DstVec = DestTy->isVectorTy();
1243
1244   Assert1(SrcVec == DstVec,
1245           "SIToFP source and dest must both be vector or scalar", &I);
1246   Assert1(SrcTy->isIntOrIntVectorTy(),
1247           "SIToFP source must be integer or integer vector", &I);
1248   Assert1(DestTy->isFPOrFPVectorTy(),
1249           "SIToFP result must be FP or FP vector", &I);
1250
1251   if (SrcVec && DstVec)
1252     Assert1(cast<VectorType>(SrcTy)->getNumElements() ==
1253             cast<VectorType>(DestTy)->getNumElements(),
1254             "SIToFP source and dest vector length mismatch", &I);
1255
1256   visitInstruction(I);
1257 }
1258
1259 void Verifier::visitFPToUIInst(FPToUIInst &I) {
1260   // Get the source and destination types
1261   Type *SrcTy = I.getOperand(0)->getType();
1262   Type *DestTy = I.getType();
1263
1264   bool SrcVec = SrcTy->isVectorTy();
1265   bool DstVec = DestTy->isVectorTy();
1266
1267   Assert1(SrcVec == DstVec,
1268           "FPToUI source and dest must both be vector or scalar", &I);
1269   Assert1(SrcTy->isFPOrFPVectorTy(), "FPToUI source must be FP or FP vector",
1270           &I);
1271   Assert1(DestTy->isIntOrIntVectorTy(),
1272           "FPToUI result must be integer or integer vector", &I);
1273
1274   if (SrcVec && DstVec)
1275     Assert1(cast<VectorType>(SrcTy)->getNumElements() ==
1276             cast<VectorType>(DestTy)->getNumElements(),
1277             "FPToUI source and dest vector length mismatch", &I);
1278
1279   visitInstruction(I);
1280 }
1281
1282 void Verifier::visitFPToSIInst(FPToSIInst &I) {
1283   // Get the source and destination types
1284   Type *SrcTy = I.getOperand(0)->getType();
1285   Type *DestTy = I.getType();
1286
1287   bool SrcVec = SrcTy->isVectorTy();
1288   bool DstVec = DestTy->isVectorTy();
1289
1290   Assert1(SrcVec == DstVec,
1291           "FPToSI source and dest must both be vector or scalar", &I);
1292   Assert1(SrcTy->isFPOrFPVectorTy(),
1293           "FPToSI source must be FP or FP vector", &I);
1294   Assert1(DestTy->isIntOrIntVectorTy(),
1295           "FPToSI result must be integer or integer vector", &I);
1296
1297   if (SrcVec && DstVec)
1298     Assert1(cast<VectorType>(SrcTy)->getNumElements() ==
1299             cast<VectorType>(DestTy)->getNumElements(),
1300             "FPToSI source and dest vector length mismatch", &I);
1301
1302   visitInstruction(I);
1303 }
1304
1305 void Verifier::visitPtrToIntInst(PtrToIntInst &I) {
1306   // Get the source and destination types
1307   Type *SrcTy = I.getOperand(0)->getType();
1308   Type *DestTy = I.getType();
1309
1310   Assert1(SrcTy->getScalarType()->isPointerTy(),
1311           "PtrToInt source must be pointer", &I);
1312   Assert1(DestTy->getScalarType()->isIntegerTy(),
1313           "PtrToInt result must be integral", &I);
1314   Assert1(SrcTy->isVectorTy() == DestTy->isVectorTy(),
1315           "PtrToInt type mismatch", &I);
1316
1317   if (SrcTy->isVectorTy()) {
1318     VectorType *VSrc = dyn_cast<VectorType>(SrcTy);
1319     VectorType *VDest = dyn_cast<VectorType>(DestTy);
1320     Assert1(VSrc->getNumElements() == VDest->getNumElements(),
1321           "PtrToInt Vector width mismatch", &I);
1322   }
1323
1324   visitInstruction(I);
1325 }
1326
1327 void Verifier::visitIntToPtrInst(IntToPtrInst &I) {
1328   // Get the source and destination types
1329   Type *SrcTy = I.getOperand(0)->getType();
1330   Type *DestTy = I.getType();
1331
1332   Assert1(SrcTy->getScalarType()->isIntegerTy(),
1333           "IntToPtr source must be an integral", &I);
1334   Assert1(DestTy->getScalarType()->isPointerTy(),
1335           "IntToPtr result must be a pointer",&I);
1336   Assert1(SrcTy->isVectorTy() == DestTy->isVectorTy(),
1337           "IntToPtr type mismatch", &I);
1338   if (SrcTy->isVectorTy()) {
1339     VectorType *VSrc = dyn_cast<VectorType>(SrcTy);
1340     VectorType *VDest = dyn_cast<VectorType>(DestTy);
1341     Assert1(VSrc->getNumElements() == VDest->getNumElements(),
1342           "IntToPtr Vector width mismatch", &I);
1343   }
1344   visitInstruction(I);
1345 }
1346
1347 void Verifier::visitBitCastInst(BitCastInst &I) {
1348   // Get the source and destination types
1349   Type *SrcTy = I.getOperand(0)->getType();
1350   Type *DestTy = I.getType();
1351
1352   // Get the size of the types in bits, we'll need this later
1353   unsigned SrcBitSize = SrcTy->getPrimitiveSizeInBits();
1354   unsigned DestBitSize = DestTy->getPrimitiveSizeInBits();
1355
1356   // BitCast implies a no-op cast of type only. No bits change.
1357   // However, you can't cast pointers to anything but pointers.
1358   Assert1(SrcTy->isPointerTy() == DestTy->isPointerTy(),
1359           "Bitcast requires both operands to be pointer or neither", &I);
1360   Assert1(SrcBitSize == DestBitSize, "Bitcast requires types of same width",&I);
1361
1362   // Disallow aggregates.
1363   Assert1(!SrcTy->isAggregateType(),
1364           "Bitcast operand must not be aggregate", &I);
1365   Assert1(!DestTy->isAggregateType(),
1366           "Bitcast type must not be aggregate", &I);
1367
1368   visitInstruction(I);
1369 }
1370
1371 /// visitPHINode - Ensure that a PHI node is well formed.
1372 ///
1373 void Verifier::visitPHINode(PHINode &PN) {
1374   // Ensure that the PHI nodes are all grouped together at the top of the block.
1375   // This can be tested by checking whether the instruction before this is
1376   // either nonexistent (because this is begin()) or is a PHI node.  If not,
1377   // then there is some other instruction before a PHI.
1378   Assert2(&PN == &PN.getParent()->front() ||
1379           isa<PHINode>(--BasicBlock::iterator(&PN)),
1380           "PHI nodes not grouped at top of basic block!",
1381           &PN, PN.getParent());
1382
1383   // Check that all of the values of the PHI node have the same type as the
1384   // result, and that the incoming blocks are really basic blocks.
1385   for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
1386     Assert1(PN.getType() == PN.getIncomingValue(i)->getType(),
1387             "PHI node operands are not the same type as the result!", &PN);
1388   }
1389
1390   // All other PHI node constraints are checked in the visitBasicBlock method.
1391
1392   visitInstruction(PN);
1393 }
1394
1395 void Verifier::VerifyCallSite(CallSite CS) {
1396   Instruction *I = CS.getInstruction();
1397
1398   Assert1(CS.getCalledValue()->getType()->isPointerTy(),
1399           "Called function must be a pointer!", I);
1400   PointerType *FPTy = cast<PointerType>(CS.getCalledValue()->getType());
1401
1402   Assert1(FPTy->getElementType()->isFunctionTy(),
1403           "Called function is not pointer to function type!", I);
1404   FunctionType *FTy = cast<FunctionType>(FPTy->getElementType());
1405
1406   // Verify that the correct number of arguments are being passed
1407   if (FTy->isVarArg())
1408     Assert1(CS.arg_size() >= FTy->getNumParams(),
1409             "Called function requires more parameters than were provided!",I);
1410   else
1411     Assert1(CS.arg_size() == FTy->getNumParams(),
1412             "Incorrect number of arguments passed to called function!", I);
1413
1414   // Verify that all arguments to the call match the function type.
1415   for (unsigned i = 0, e = FTy->getNumParams(); i != e; ++i)
1416     Assert3(CS.getArgument(i)->getType() == FTy->getParamType(i),
1417             "Call parameter type does not match function signature!",
1418             CS.getArgument(i), FTy->getParamType(i), I);
1419
1420   AttributeSet Attrs = CS.getAttributes();
1421
1422   Assert1(VerifyAttributeCount(Attrs, CS.arg_size()),
1423           "Attribute after last parameter!", I);
1424
1425   // Verify call attributes.
1426   VerifyFunctionAttrs(FTy, Attrs, I);
1427
1428   if (FTy->isVarArg()) {
1429     // FIXME? is 'nest' even legal here?
1430     bool SawNest = false;
1431     bool SawReturned = false;
1432
1433     for (unsigned Idx = 1; Idx < 1 + FTy->getNumParams(); ++Idx) {
1434       if (Attrs.hasAttribute(Idx, Attribute::Nest))
1435         SawNest = true;
1436       if (Attrs.hasAttribute(Idx, Attribute::Returned))
1437         SawReturned = true;
1438     }
1439
1440     // Check attributes on the varargs part.
1441     for (unsigned Idx = 1 + FTy->getNumParams(); Idx <= CS.arg_size(); ++Idx) {
1442       Type *Ty = CS.getArgument(Idx-1)->getType();
1443       VerifyParameterAttrs(Attrs, Idx, Ty, false, I);
1444
1445       if (Attrs.hasAttribute(Idx, Attribute::Nest)) {
1446         Assert1(!SawNest, "More than one parameter has attribute nest!", I);
1447         SawNest = true;
1448       }
1449
1450       if (Attrs.hasAttribute(Idx, Attribute::Returned)) {
1451         Assert1(!SawReturned, "More than one parameter has attribute returned!",
1452                 I);
1453         Assert1(Ty->canLosslesslyBitCastTo(FTy->getReturnType()),
1454                 "Incompatible argument and return types for 'returned' "
1455                 "attribute", I);
1456         SawReturned = true;
1457       }
1458
1459       Assert1(!Attrs.hasAttribute(Idx, Attribute::StructRet),
1460               "Attribute 'sret' cannot be used for vararg call arguments!", I);
1461     }
1462   }
1463
1464   // Verify that there's no metadata unless it's a direct call to an intrinsic.
1465   if (CS.getCalledFunction() == 0 ||
1466       !CS.getCalledFunction()->getName().startswith("llvm.")) {
1467     for (FunctionType::param_iterator PI = FTy->param_begin(),
1468            PE = FTy->param_end(); PI != PE; ++PI)
1469       Assert1(!(*PI)->isMetadataTy(),
1470               "Function has metadata parameter but isn't an intrinsic", I);
1471   }
1472
1473   // If the call site has the 'builtin' attribute, verify that it's applied to a
1474   // direct call to a function with the 'nobuiltin' attribute.
1475   if (CS.hasFnAttr(Attribute::Builtin))
1476     Assert1(CS.getCalledFunction() &&
1477             CS.getCalledFunction()->hasFnAttribute(Attribute::NoBuiltin),
1478             "Attribute 'builtin' can only be used in a call to a function with "
1479             "the 'nobuiltin' attribute.", I);
1480
1481   visitInstruction(*I);
1482 }
1483
1484 void Verifier::visitCallInst(CallInst &CI) {
1485   VerifyCallSite(&CI);
1486
1487   if (Function *F = CI.getCalledFunction())
1488     if (Intrinsic::ID ID = (Intrinsic::ID)F->getIntrinsicID())
1489       visitIntrinsicFunctionCall(ID, CI);
1490 }
1491
1492 void Verifier::visitInvokeInst(InvokeInst &II) {
1493   VerifyCallSite(&II);
1494
1495   // Verify that there is a landingpad instruction as the first non-PHI
1496   // instruction of the 'unwind' destination.
1497   Assert1(II.getUnwindDest()->isLandingPad(),
1498           "The unwind destination does not have a landingpad instruction!",&II);
1499
1500   visitTerminatorInst(II);
1501 }
1502
1503 /// visitBinaryOperator - Check that both arguments to the binary operator are
1504 /// of the same type!
1505 ///
1506 void Verifier::visitBinaryOperator(BinaryOperator &B) {
1507   Assert1(B.getOperand(0)->getType() == B.getOperand(1)->getType(),
1508           "Both operands to a binary operator are not of the same type!", &B);
1509
1510   switch (B.getOpcode()) {
1511   // Check that integer arithmetic operators are only used with
1512   // integral operands.
1513   case Instruction::Add:
1514   case Instruction::Sub:
1515   case Instruction::Mul:
1516   case Instruction::SDiv:
1517   case Instruction::UDiv:
1518   case Instruction::SRem:
1519   case Instruction::URem:
1520     Assert1(B.getType()->isIntOrIntVectorTy(),
1521             "Integer arithmetic operators only work with integral types!", &B);
1522     Assert1(B.getType() == B.getOperand(0)->getType(),
1523             "Integer arithmetic operators must have same type "
1524             "for operands and result!", &B);
1525     break;
1526   // Check that floating-point arithmetic operators are only used with
1527   // floating-point operands.
1528   case Instruction::FAdd:
1529   case Instruction::FSub:
1530   case Instruction::FMul:
1531   case Instruction::FDiv:
1532   case Instruction::FRem:
1533     Assert1(B.getType()->isFPOrFPVectorTy(),
1534             "Floating-point arithmetic operators only work with "
1535             "floating-point types!", &B);
1536     Assert1(B.getType() == B.getOperand(0)->getType(),
1537             "Floating-point arithmetic operators must have same type "
1538             "for operands and result!", &B);
1539     break;
1540   // Check that logical operators are only used with integral operands.
1541   case Instruction::And:
1542   case Instruction::Or:
1543   case Instruction::Xor:
1544     Assert1(B.getType()->isIntOrIntVectorTy(),
1545             "Logical operators only work with integral types!", &B);
1546     Assert1(B.getType() == B.getOperand(0)->getType(),
1547             "Logical operators must have same type for operands and result!",
1548             &B);
1549     break;
1550   case Instruction::Shl:
1551   case Instruction::LShr:
1552   case Instruction::AShr:
1553     Assert1(B.getType()->isIntOrIntVectorTy(),
1554             "Shifts only work with integral types!", &B);
1555     Assert1(B.getType() == B.getOperand(0)->getType(),
1556             "Shift return type must be same as operands!", &B);
1557     break;
1558   default:
1559     llvm_unreachable("Unknown BinaryOperator opcode!");
1560   }
1561
1562   visitInstruction(B);
1563 }
1564
1565 void Verifier::visitICmpInst(ICmpInst &IC) {
1566   // Check that the operands are the same type
1567   Type *Op0Ty = IC.getOperand(0)->getType();
1568   Type *Op1Ty = IC.getOperand(1)->getType();
1569   Assert1(Op0Ty == Op1Ty,
1570           "Both operands to ICmp instruction are not of the same type!", &IC);
1571   // Check that the operands are the right type
1572   Assert1(Op0Ty->isIntOrIntVectorTy() || Op0Ty->getScalarType()->isPointerTy(),
1573           "Invalid operand types for ICmp instruction", &IC);
1574   // Check that the predicate is valid.
1575   Assert1(IC.getPredicate() >= CmpInst::FIRST_ICMP_PREDICATE &&
1576           IC.getPredicate() <= CmpInst::LAST_ICMP_PREDICATE,
1577           "Invalid predicate in ICmp instruction!", &IC);
1578
1579   visitInstruction(IC);
1580 }
1581
1582 void Verifier::visitFCmpInst(FCmpInst &FC) {
1583   // Check that the operands are the same type
1584   Type *Op0Ty = FC.getOperand(0)->getType();
1585   Type *Op1Ty = FC.getOperand(1)->getType();
1586   Assert1(Op0Ty == Op1Ty,
1587           "Both operands to FCmp instruction are not of the same type!", &FC);
1588   // Check that the operands are the right type
1589   Assert1(Op0Ty->isFPOrFPVectorTy(),
1590           "Invalid operand types for FCmp instruction", &FC);
1591   // Check that the predicate is valid.
1592   Assert1(FC.getPredicate() >= CmpInst::FIRST_FCMP_PREDICATE &&
1593           FC.getPredicate() <= CmpInst::LAST_FCMP_PREDICATE,
1594           "Invalid predicate in FCmp instruction!", &FC);
1595
1596   visitInstruction(FC);
1597 }
1598
1599 void Verifier::visitExtractElementInst(ExtractElementInst &EI) {
1600   Assert1(ExtractElementInst::isValidOperands(EI.getOperand(0),
1601                                               EI.getOperand(1)),
1602           "Invalid extractelement operands!", &EI);
1603   visitInstruction(EI);
1604 }
1605
1606 void Verifier::visitInsertElementInst(InsertElementInst &IE) {
1607   Assert1(InsertElementInst::isValidOperands(IE.getOperand(0),
1608                                              IE.getOperand(1),
1609                                              IE.getOperand(2)),
1610           "Invalid insertelement operands!", &IE);
1611   visitInstruction(IE);
1612 }
1613
1614 void Verifier::visitShuffleVectorInst(ShuffleVectorInst &SV) {
1615   Assert1(ShuffleVectorInst::isValidOperands(SV.getOperand(0), SV.getOperand(1),
1616                                              SV.getOperand(2)),
1617           "Invalid shufflevector operands!", &SV);
1618   visitInstruction(SV);
1619 }
1620
1621 void Verifier::visitGetElementPtrInst(GetElementPtrInst &GEP) {
1622   Type *TargetTy = GEP.getPointerOperandType()->getScalarType();
1623
1624   Assert1(isa<PointerType>(TargetTy),
1625     "GEP base pointer is not a vector or a vector of pointers", &GEP);
1626   Assert1(cast<PointerType>(TargetTy)->getElementType()->isSized(),
1627           "GEP into unsized type!", &GEP);
1628   Assert1(GEP.getPointerOperandType()->isVectorTy() ==
1629           GEP.getType()->isVectorTy(), "Vector GEP must return a vector value",
1630           &GEP);
1631
1632   SmallVector<Value*, 16> Idxs(GEP.idx_begin(), GEP.idx_end());
1633   Type *ElTy =
1634     GetElementPtrInst::getIndexedType(GEP.getPointerOperandType(), Idxs);
1635   Assert1(ElTy, "Invalid indices for GEP pointer type!", &GEP);
1636
1637   Assert2(GEP.getType()->getScalarType()->isPointerTy() &&
1638           cast<PointerType>(GEP.getType()->getScalarType())->getElementType()
1639           == ElTy, "GEP is not of right type for indices!", &GEP, ElTy);
1640
1641   if (GEP.getPointerOperandType()->isVectorTy()) {
1642     // Additional checks for vector GEPs.
1643     unsigned GepWidth = GEP.getPointerOperandType()->getVectorNumElements();
1644     Assert1(GepWidth == GEP.getType()->getVectorNumElements(),
1645             "Vector GEP result width doesn't match operand's", &GEP);
1646     for (unsigned i = 0, e = Idxs.size(); i != e; ++i) {
1647       Type *IndexTy = Idxs[i]->getType();
1648       Assert1(IndexTy->isVectorTy(),
1649               "Vector GEP must have vector indices!", &GEP);
1650       unsigned IndexWidth = IndexTy->getVectorNumElements();
1651       Assert1(IndexWidth == GepWidth, "Invalid GEP index vector width", &GEP);
1652     }
1653   }
1654   visitInstruction(GEP);
1655 }
1656
1657 static bool isContiguous(const ConstantRange &A, const ConstantRange &B) {
1658   return A.getUpper() == B.getLower() || A.getLower() == B.getUpper();
1659 }
1660
1661 void Verifier::visitLoadInst(LoadInst &LI) {
1662   PointerType *PTy = dyn_cast<PointerType>(LI.getOperand(0)->getType());
1663   Assert1(PTy, "Load operand must be a pointer.", &LI);
1664   Type *ElTy = PTy->getElementType();
1665   Assert2(ElTy == LI.getType(),
1666           "Load result type does not match pointer operand type!", &LI, ElTy);
1667   if (LI.isAtomic()) {
1668     Assert1(LI.getOrdering() != Release && LI.getOrdering() != AcquireRelease,
1669             "Load cannot have Release ordering", &LI);
1670     Assert1(LI.getAlignment() != 0,
1671             "Atomic load must specify explicit alignment", &LI);
1672     if (!ElTy->isPointerTy()) {
1673       Assert2(ElTy->isIntegerTy(),
1674               "atomic store operand must have integer type!",
1675               &LI, ElTy);
1676       unsigned Size = ElTy->getPrimitiveSizeInBits();
1677       Assert2(Size >= 8 && !(Size & (Size - 1)),
1678               "atomic store operand must be power-of-two byte-sized integer",
1679               &LI, ElTy);
1680     }
1681   } else {
1682     Assert1(LI.getSynchScope() == CrossThread,
1683             "Non-atomic load cannot have SynchronizationScope specified", &LI);
1684   }
1685
1686   if (MDNode *Range = LI.getMetadata(LLVMContext::MD_range)) {
1687     unsigned NumOperands = Range->getNumOperands();
1688     Assert1(NumOperands % 2 == 0, "Unfinished range!", Range);
1689     unsigned NumRanges = NumOperands / 2;
1690     Assert1(NumRanges >= 1, "It should have at least one range!", Range);
1691
1692     ConstantRange LastRange(1); // Dummy initial value
1693     for (unsigned i = 0; i < NumRanges; ++i) {
1694       ConstantInt *Low = dyn_cast<ConstantInt>(Range->getOperand(2*i));
1695       Assert1(Low, "The lower limit must be an integer!", Low);
1696       ConstantInt *High = dyn_cast<ConstantInt>(Range->getOperand(2*i + 1));
1697       Assert1(High, "The upper limit must be an integer!", High);
1698       Assert1(High->getType() == Low->getType() &&
1699               High->getType() == ElTy, "Range types must match load type!",
1700               &LI);
1701
1702       APInt HighV = High->getValue();
1703       APInt LowV = Low->getValue();
1704       ConstantRange CurRange(LowV, HighV);
1705       Assert1(!CurRange.isEmptySet() && !CurRange.isFullSet(),
1706               "Range must not be empty!", Range);
1707       if (i != 0) {
1708         Assert1(CurRange.intersectWith(LastRange).isEmptySet(),
1709                 "Intervals are overlapping", Range);
1710         Assert1(LowV.sgt(LastRange.getLower()), "Intervals are not in order",
1711                 Range);
1712         Assert1(!isContiguous(CurRange, LastRange), "Intervals are contiguous",
1713                 Range);
1714       }
1715       LastRange = ConstantRange(LowV, HighV);
1716     }
1717     if (NumRanges > 2) {
1718       APInt FirstLow =
1719         dyn_cast<ConstantInt>(Range->getOperand(0))->getValue();
1720       APInt FirstHigh =
1721         dyn_cast<ConstantInt>(Range->getOperand(1))->getValue();
1722       ConstantRange FirstRange(FirstLow, FirstHigh);
1723       Assert1(FirstRange.intersectWith(LastRange).isEmptySet(),
1724               "Intervals are overlapping", Range);
1725       Assert1(!isContiguous(FirstRange, LastRange), "Intervals are contiguous",
1726               Range);
1727     }
1728
1729
1730   }
1731
1732   visitInstruction(LI);
1733 }
1734
1735 void Verifier::visitStoreInst(StoreInst &SI) {
1736   PointerType *PTy = dyn_cast<PointerType>(SI.getOperand(1)->getType());
1737   Assert1(PTy, "Store operand must be a pointer.", &SI);
1738   Type *ElTy = PTy->getElementType();
1739   Assert2(ElTy == SI.getOperand(0)->getType(),
1740           "Stored value type does not match pointer operand type!",
1741           &SI, ElTy);
1742   if (SI.isAtomic()) {
1743     Assert1(SI.getOrdering() != Acquire && SI.getOrdering() != AcquireRelease,
1744             "Store cannot have Acquire ordering", &SI);
1745     Assert1(SI.getAlignment() != 0,
1746             "Atomic store must specify explicit alignment", &SI);
1747     if (!ElTy->isPointerTy()) {
1748       Assert2(ElTy->isIntegerTy(),
1749               "atomic store operand must have integer type!",
1750               &SI, ElTy);
1751       unsigned Size = ElTy->getPrimitiveSizeInBits();
1752       Assert2(Size >= 8 && !(Size & (Size - 1)),
1753               "atomic store operand must be power-of-two byte-sized integer",
1754               &SI, ElTy);
1755     }
1756   } else {
1757     Assert1(SI.getSynchScope() == CrossThread,
1758             "Non-atomic store cannot have SynchronizationScope specified", &SI);
1759   }
1760   visitInstruction(SI);
1761 }
1762
1763 void Verifier::visitAllocaInst(AllocaInst &AI) {
1764   PointerType *PTy = AI.getType();
1765   Assert1(PTy->getAddressSpace() == 0,
1766           "Allocation instruction pointer not in the generic address space!",
1767           &AI);
1768   Assert1(PTy->getElementType()->isSized(), "Cannot allocate unsized type",
1769           &AI);
1770   Assert1(AI.getArraySize()->getType()->isIntegerTy(),
1771           "Alloca array size must have integer type", &AI);
1772   visitInstruction(AI);
1773 }
1774
1775 void Verifier::visitAtomicCmpXchgInst(AtomicCmpXchgInst &CXI) {
1776   Assert1(CXI.getOrdering() != NotAtomic,
1777           "cmpxchg instructions must be atomic.", &CXI);
1778   Assert1(CXI.getOrdering() != Unordered,
1779           "cmpxchg instructions cannot be unordered.", &CXI);
1780   PointerType *PTy = dyn_cast<PointerType>(CXI.getOperand(0)->getType());
1781   Assert1(PTy, "First cmpxchg operand must be a pointer.", &CXI);
1782   Type *ElTy = PTy->getElementType();
1783   Assert2(ElTy->isIntegerTy(),
1784           "cmpxchg operand must have integer type!",
1785           &CXI, ElTy);
1786   unsigned Size = ElTy->getPrimitiveSizeInBits();
1787   Assert2(Size >= 8 && !(Size & (Size - 1)),
1788           "cmpxchg operand must be power-of-two byte-sized integer",
1789           &CXI, ElTy);
1790   Assert2(ElTy == CXI.getOperand(1)->getType(),
1791           "Expected value type does not match pointer operand type!",
1792           &CXI, ElTy);
1793   Assert2(ElTy == CXI.getOperand(2)->getType(),
1794           "Stored value type does not match pointer operand type!",
1795           &CXI, ElTy);
1796   visitInstruction(CXI);
1797 }
1798
1799 void Verifier::visitAtomicRMWInst(AtomicRMWInst &RMWI) {
1800   Assert1(RMWI.getOrdering() != NotAtomic,
1801           "atomicrmw instructions must be atomic.", &RMWI);
1802   Assert1(RMWI.getOrdering() != Unordered,
1803           "atomicrmw instructions cannot be unordered.", &RMWI);
1804   PointerType *PTy = dyn_cast<PointerType>(RMWI.getOperand(0)->getType());
1805   Assert1(PTy, "First atomicrmw operand must be a pointer.", &RMWI);
1806   Type *ElTy = PTy->getElementType();
1807   Assert2(ElTy->isIntegerTy(),
1808           "atomicrmw operand must have integer type!",
1809           &RMWI, ElTy);
1810   unsigned Size = ElTy->getPrimitiveSizeInBits();
1811   Assert2(Size >= 8 && !(Size & (Size - 1)),
1812           "atomicrmw operand must be power-of-two byte-sized integer",
1813           &RMWI, ElTy);
1814   Assert2(ElTy == RMWI.getOperand(1)->getType(),
1815           "Argument value type does not match pointer operand type!",
1816           &RMWI, ElTy);
1817   Assert1(AtomicRMWInst::FIRST_BINOP <= RMWI.getOperation() &&
1818           RMWI.getOperation() <= AtomicRMWInst::LAST_BINOP,
1819           "Invalid binary operation!", &RMWI);
1820   visitInstruction(RMWI);
1821 }
1822
1823 void Verifier::visitFenceInst(FenceInst &FI) {
1824   const AtomicOrdering Ordering = FI.getOrdering();
1825   Assert1(Ordering == Acquire || Ordering == Release ||
1826           Ordering == AcquireRelease || Ordering == SequentiallyConsistent,
1827           "fence instructions may only have "
1828           "acquire, release, acq_rel, or seq_cst ordering.", &FI);
1829   visitInstruction(FI);
1830 }
1831
1832 void Verifier::visitExtractValueInst(ExtractValueInst &EVI) {
1833   Assert1(ExtractValueInst::getIndexedType(EVI.getAggregateOperand()->getType(),
1834                                            EVI.getIndices()) ==
1835           EVI.getType(),
1836           "Invalid ExtractValueInst operands!", &EVI);
1837
1838   visitInstruction(EVI);
1839 }
1840
1841 void Verifier::visitInsertValueInst(InsertValueInst &IVI) {
1842   Assert1(ExtractValueInst::getIndexedType(IVI.getAggregateOperand()->getType(),
1843                                            IVI.getIndices()) ==
1844           IVI.getOperand(1)->getType(),
1845           "Invalid InsertValueInst operands!", &IVI);
1846
1847   visitInstruction(IVI);
1848 }
1849
1850 void Verifier::visitLandingPadInst(LandingPadInst &LPI) {
1851   BasicBlock *BB = LPI.getParent();
1852
1853   // The landingpad instruction is ill-formed if it doesn't have any clauses and
1854   // isn't a cleanup.
1855   Assert1(LPI.getNumClauses() > 0 || LPI.isCleanup(),
1856           "LandingPadInst needs at least one clause or to be a cleanup.", &LPI);
1857
1858   // The landingpad instruction defines its parent as a landing pad block. The
1859   // landing pad block may be branched to only by the unwind edge of an invoke.
1860   for (pred_iterator I = pred_begin(BB), E = pred_end(BB); I != E; ++I) {
1861     const InvokeInst *II = dyn_cast<InvokeInst>((*I)->getTerminator());
1862     Assert1(II && II->getUnwindDest() == BB && II->getNormalDest() != BB,
1863             "Block containing LandingPadInst must be jumped to "
1864             "only by the unwind edge of an invoke.", &LPI);
1865   }
1866
1867   // The landingpad instruction must be the first non-PHI instruction in the
1868   // block.
1869   Assert1(LPI.getParent()->getLandingPadInst() == &LPI,
1870           "LandingPadInst not the first non-PHI instruction in the block.",
1871           &LPI);
1872
1873   // The personality functions for all landingpad instructions within the same
1874   // function should match.
1875   if (PersonalityFn)
1876     Assert1(LPI.getPersonalityFn() == PersonalityFn,
1877             "Personality function doesn't match others in function", &LPI);
1878   PersonalityFn = LPI.getPersonalityFn();
1879
1880   // All operands must be constants.
1881   Assert1(isa<Constant>(PersonalityFn), "Personality function is not constant!",
1882           &LPI);
1883   for (unsigned i = 0, e = LPI.getNumClauses(); i < e; ++i) {
1884     Value *Clause = LPI.getClause(i);
1885     Assert1(isa<Constant>(Clause), "Clause is not constant!", &LPI);
1886     if (LPI.isCatch(i)) {
1887       Assert1(isa<PointerType>(Clause->getType()),
1888               "Catch operand does not have pointer type!", &LPI);
1889     } else {
1890       Assert1(LPI.isFilter(i), "Clause is neither catch nor filter!", &LPI);
1891       Assert1(isa<ConstantArray>(Clause) || isa<ConstantAggregateZero>(Clause),
1892               "Filter operand is not an array of constants!", &LPI);
1893     }
1894   }
1895
1896   visitInstruction(LPI);
1897 }
1898
1899 void Verifier::verifyDominatesUse(Instruction &I, unsigned i) {
1900   Instruction *Op = cast<Instruction>(I.getOperand(i));
1901   // If the we have an invalid invoke, don't try to compute the dominance.
1902   // We already reject it in the invoke specific checks and the dominance
1903   // computation doesn't handle multiple edges.
1904   if (InvokeInst *II = dyn_cast<InvokeInst>(Op)) {
1905     if (II->getNormalDest() == II->getUnwindDest())
1906       return;
1907   }
1908
1909   const Use &U = I.getOperandUse(i);
1910   Assert2(InstsInThisBlock.count(Op) || DT->dominates(Op, U),
1911           "Instruction does not dominate all uses!", Op, &I);
1912 }
1913
1914 /// verifyInstruction - Verify that an instruction is well formed.
1915 ///
1916 void Verifier::visitInstruction(Instruction &I) {
1917   BasicBlock *BB = I.getParent();
1918   Assert1(BB, "Instruction not embedded in basic block!", &I);
1919
1920   if (!isa<PHINode>(I)) {   // Check that non-phi nodes are not self referential
1921     for (Value::use_iterator UI = I.use_begin(), UE = I.use_end();
1922          UI != UE; ++UI)
1923       Assert1(*UI != (User*)&I || !DT->isReachableFromEntry(BB),
1924               "Only PHI nodes may reference their own value!", &I);
1925   }
1926
1927   // Check that void typed values don't have names
1928   Assert1(!I.getType()->isVoidTy() || !I.hasName(),
1929           "Instruction has a name, but provides a void value!", &I);
1930
1931   // Check that the return value of the instruction is either void or a legal
1932   // value type.
1933   Assert1(I.getType()->isVoidTy() ||
1934           I.getType()->isFirstClassType(),
1935           "Instruction returns a non-scalar type!", &I);
1936
1937   // Check that the instruction doesn't produce metadata. Calls are already
1938   // checked against the callee type.
1939   Assert1(!I.getType()->isMetadataTy() ||
1940           isa<CallInst>(I) || isa<InvokeInst>(I),
1941           "Invalid use of metadata!", &I);
1942
1943   // Check that all uses of the instruction, if they are instructions
1944   // themselves, actually have parent basic blocks.  If the use is not an
1945   // instruction, it is an error!
1946   for (User::use_iterator UI = I.use_begin(), UE = I.use_end();
1947        UI != UE; ++UI) {
1948     if (Instruction *Used = dyn_cast<Instruction>(*UI))
1949       Assert2(Used->getParent() != 0, "Instruction referencing instruction not"
1950               " embedded in a basic block!", &I, Used);
1951     else {
1952       CheckFailed("Use of instruction is not an instruction!", *UI);
1953       return;
1954     }
1955   }
1956
1957   for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) {
1958     Assert1(I.getOperand(i) != 0, "Instruction has null operand!", &I);
1959
1960     // Check to make sure that only first-class-values are operands to
1961     // instructions.
1962     if (!I.getOperand(i)->getType()->isFirstClassType()) {
1963       Assert1(0, "Instruction operands must be first-class values!", &I);
1964     }
1965
1966     if (Function *F = dyn_cast<Function>(I.getOperand(i))) {
1967       // Check to make sure that the "address of" an intrinsic function is never
1968       // taken.
1969       Assert1(!F->isIntrinsic() || i == (isa<CallInst>(I) ? e-1 : 0),
1970               "Cannot take the address of an intrinsic!", &I);
1971       Assert1(!F->isIntrinsic() || isa<CallInst>(I) ||
1972               F->getIntrinsicID() == Intrinsic::donothing,
1973               "Cannot invoke an intrinsinc other than donothing", &I);
1974       Assert1(F->getParent() == Mod, "Referencing function in another module!",
1975               &I);
1976     } else if (BasicBlock *OpBB = dyn_cast<BasicBlock>(I.getOperand(i))) {
1977       Assert1(OpBB->getParent() == BB->getParent(),
1978               "Referring to a basic block in another function!", &I);
1979     } else if (Argument *OpArg = dyn_cast<Argument>(I.getOperand(i))) {
1980       Assert1(OpArg->getParent() == BB->getParent(),
1981               "Referring to an argument in another function!", &I);
1982     } else if (GlobalValue *GV = dyn_cast<GlobalValue>(I.getOperand(i))) {
1983       Assert1(GV->getParent() == Mod, "Referencing global in another module!",
1984               &I);
1985     } else if (isa<Instruction>(I.getOperand(i))) {
1986       verifyDominatesUse(I, i);
1987     } else if (isa<InlineAsm>(I.getOperand(i))) {
1988       Assert1((i + 1 == e && isa<CallInst>(I)) ||
1989               (i + 3 == e && isa<InvokeInst>(I)),
1990               "Cannot take the address of an inline asm!", &I);
1991     }
1992   }
1993
1994   if (MDNode *MD = I.getMetadata(LLVMContext::MD_fpmath)) {
1995     Assert1(I.getType()->isFPOrFPVectorTy(),
1996             "fpmath requires a floating point result!", &I);
1997     Assert1(MD->getNumOperands() == 1, "fpmath takes one operand!", &I);
1998     Value *Op0 = MD->getOperand(0);
1999     if (ConstantFP *CFP0 = dyn_cast_or_null<ConstantFP>(Op0)) {
2000       APFloat Accuracy = CFP0->getValueAPF();
2001       Assert1(Accuracy.isFiniteNonZero() && !Accuracy.isNegative(),
2002               "fpmath accuracy not a positive number!", &I);
2003     } else {
2004       Assert1(false, "invalid fpmath accuracy!", &I);
2005     }
2006   }
2007
2008   MDNode *MD = I.getMetadata(LLVMContext::MD_range);
2009   Assert1(!MD || isa<LoadInst>(I), "Ranges are only for loads!", &I);
2010
2011   InstsInThisBlock.insert(&I);
2012 }
2013
2014 /// VerifyIntrinsicType - Verify that the specified type (which comes from an
2015 /// intrinsic argument or return value) matches the type constraints specified
2016 /// by the .td file (e.g. an "any integer" argument really is an integer).
2017 ///
2018 /// This return true on error but does not print a message.
2019 bool Verifier::VerifyIntrinsicType(Type *Ty,
2020                                    ArrayRef<Intrinsic::IITDescriptor> &Infos,
2021                                    SmallVectorImpl<Type*> &ArgTys) {
2022   using namespace Intrinsic;
2023
2024   // If we ran out of descriptors, there are too many arguments.
2025   if (Infos.empty()) return true;
2026   IITDescriptor D = Infos.front();
2027   Infos = Infos.slice(1);
2028
2029   switch (D.Kind) {
2030   case IITDescriptor::Void: return !Ty->isVoidTy();
2031   case IITDescriptor::MMX:  return !Ty->isX86_MMXTy();
2032   case IITDescriptor::Metadata: return !Ty->isMetadataTy();
2033   case IITDescriptor::Half: return !Ty->isHalfTy();
2034   case IITDescriptor::Float: return !Ty->isFloatTy();
2035   case IITDescriptor::Double: return !Ty->isDoubleTy();
2036   case IITDescriptor::Integer: return !Ty->isIntegerTy(D.Integer_Width);
2037   case IITDescriptor::Vector: {
2038     VectorType *VT = dyn_cast<VectorType>(Ty);
2039     return VT == 0 || VT->getNumElements() != D.Vector_Width ||
2040            VerifyIntrinsicType(VT->getElementType(), Infos, ArgTys);
2041   }
2042   case IITDescriptor::Pointer: {
2043     PointerType *PT = dyn_cast<PointerType>(Ty);
2044     return PT == 0 || PT->getAddressSpace() != D.Pointer_AddressSpace ||
2045            VerifyIntrinsicType(PT->getElementType(), Infos, ArgTys);
2046   }
2047
2048   case IITDescriptor::Struct: {
2049     StructType *ST = dyn_cast<StructType>(Ty);
2050     if (ST == 0 || ST->getNumElements() != D.Struct_NumElements)
2051       return true;
2052
2053     for (unsigned i = 0, e = D.Struct_NumElements; i != e; ++i)
2054       if (VerifyIntrinsicType(ST->getElementType(i), Infos, ArgTys))
2055         return true;
2056     return false;
2057   }
2058
2059   case IITDescriptor::Argument:
2060     // Two cases here - If this is the second occurrence of an argument, verify
2061     // that the later instance matches the previous instance.
2062     if (D.getArgumentNumber() < ArgTys.size())
2063       return Ty != ArgTys[D.getArgumentNumber()];
2064
2065     // Otherwise, if this is the first instance of an argument, record it and
2066     // verify the "Any" kind.
2067     assert(D.getArgumentNumber() == ArgTys.size() && "Table consistency error");
2068     ArgTys.push_back(Ty);
2069
2070     switch (D.getArgumentKind()) {
2071     case IITDescriptor::AK_AnyInteger: return !Ty->isIntOrIntVectorTy();
2072     case IITDescriptor::AK_AnyFloat:   return !Ty->isFPOrFPVectorTy();
2073     case IITDescriptor::AK_AnyVector:  return !isa<VectorType>(Ty);
2074     case IITDescriptor::AK_AnyPointer: return !isa<PointerType>(Ty);
2075     }
2076     llvm_unreachable("all argument kinds not covered");
2077
2078   case IITDescriptor::ExtendVecArgument:
2079     // This may only be used when referring to a previous vector argument.
2080     return D.getArgumentNumber() >= ArgTys.size() ||
2081            !isa<VectorType>(ArgTys[D.getArgumentNumber()]) ||
2082            VectorType::getExtendedElementVectorType(
2083                        cast<VectorType>(ArgTys[D.getArgumentNumber()])) != Ty;
2084
2085   case IITDescriptor::TruncVecArgument:
2086     // This may only be used when referring to a previous vector argument.
2087     return D.getArgumentNumber() >= ArgTys.size() ||
2088            !isa<VectorType>(ArgTys[D.getArgumentNumber()]) ||
2089            VectorType::getTruncatedElementVectorType(
2090                          cast<VectorType>(ArgTys[D.getArgumentNumber()])) != Ty;
2091   }
2092   llvm_unreachable("unhandled");
2093 }
2094
2095 /// visitIntrinsicFunction - Allow intrinsics to be verified in different ways.
2096 ///
2097 void Verifier::visitIntrinsicFunctionCall(Intrinsic::ID ID, CallInst &CI) {
2098   Function *IF = CI.getCalledFunction();
2099   Assert1(IF->isDeclaration(), "Intrinsic functions should never be defined!",
2100           IF);
2101
2102   // Verify that the intrinsic prototype lines up with what the .td files
2103   // describe.
2104   FunctionType *IFTy = IF->getFunctionType();
2105   Assert1(!IFTy->isVarArg(), "Intrinsic prototypes are not varargs", IF);
2106
2107   SmallVector<Intrinsic::IITDescriptor, 8> Table;
2108   getIntrinsicInfoTableEntries(ID, Table);
2109   ArrayRef<Intrinsic::IITDescriptor> TableRef = Table;
2110
2111   SmallVector<Type *, 4> ArgTys;
2112   Assert1(!VerifyIntrinsicType(IFTy->getReturnType(), TableRef, ArgTys),
2113           "Intrinsic has incorrect return type!", IF);
2114   for (unsigned i = 0, e = IFTy->getNumParams(); i != e; ++i)
2115     Assert1(!VerifyIntrinsicType(IFTy->getParamType(i), TableRef, ArgTys),
2116             "Intrinsic has incorrect argument type!", IF);
2117   Assert1(TableRef.empty(), "Intrinsic has too few arguments!", IF);
2118
2119   // Now that we have the intrinsic ID and the actual argument types (and we
2120   // know they are legal for the intrinsic!) get the intrinsic name through the
2121   // usual means.  This allows us to verify the mangling of argument types into
2122   // the name.
2123   Assert1(Intrinsic::getName(ID, ArgTys) == IF->getName(),
2124           "Intrinsic name not mangled correctly for type arguments!", IF);
2125
2126   // If the intrinsic takes MDNode arguments, verify that they are either global
2127   // or are local to *this* function.
2128   for (unsigned i = 0, e = CI.getNumArgOperands(); i != e; ++i)
2129     if (MDNode *MD = dyn_cast<MDNode>(CI.getArgOperand(i)))
2130       visitMDNode(*MD, CI.getParent()->getParent());
2131
2132   switch (ID) {
2133   default:
2134     break;
2135   case Intrinsic::ctlz:  // llvm.ctlz
2136   case Intrinsic::cttz:  // llvm.cttz
2137     Assert1(isa<ConstantInt>(CI.getArgOperand(1)),
2138             "is_zero_undef argument of bit counting intrinsics must be a "
2139             "constant int", &CI);
2140     break;
2141   case Intrinsic::dbg_declare: {  // llvm.dbg.declare
2142     Assert1(CI.getArgOperand(0) && isa<MDNode>(CI.getArgOperand(0)),
2143                 "invalid llvm.dbg.declare intrinsic call 1", &CI);
2144     MDNode *MD = cast<MDNode>(CI.getArgOperand(0));
2145     Assert1(MD->getNumOperands() == 1,
2146                 "invalid llvm.dbg.declare intrinsic call 2", &CI);
2147   } break;
2148   case Intrinsic::memcpy:
2149   case Intrinsic::memmove:
2150   case Intrinsic::memset:
2151     Assert1(isa<ConstantInt>(CI.getArgOperand(3)),
2152             "alignment argument of memory intrinsics must be a constant int",
2153             &CI);
2154     Assert1(isa<ConstantInt>(CI.getArgOperand(4)),
2155             "isvolatile argument of memory intrinsics must be a constant int",
2156             &CI);
2157     break;
2158   case Intrinsic::gcroot:
2159   case Intrinsic::gcwrite:
2160   case Intrinsic::gcread:
2161     if (ID == Intrinsic::gcroot) {
2162       AllocaInst *AI =
2163         dyn_cast<AllocaInst>(CI.getArgOperand(0)->stripPointerCasts());
2164       Assert1(AI, "llvm.gcroot parameter #1 must be an alloca.", &CI);
2165       Assert1(isa<Constant>(CI.getArgOperand(1)),
2166               "llvm.gcroot parameter #2 must be a constant.", &CI);
2167       if (!AI->getType()->getElementType()->isPointerTy()) {
2168         Assert1(!isa<ConstantPointerNull>(CI.getArgOperand(1)),
2169                 "llvm.gcroot parameter #1 must either be a pointer alloca, "
2170                 "or argument #2 must be a non-null constant.", &CI);
2171       }
2172     }
2173
2174     Assert1(CI.getParent()->getParent()->hasGC(),
2175             "Enclosing function does not use GC.", &CI);
2176     break;
2177   case Intrinsic::init_trampoline:
2178     Assert1(isa<Function>(CI.getArgOperand(1)->stripPointerCasts()),
2179             "llvm.init_trampoline parameter #2 must resolve to a function.",
2180             &CI);
2181     break;
2182   case Intrinsic::prefetch:
2183     Assert1(isa<ConstantInt>(CI.getArgOperand(1)) &&
2184             isa<ConstantInt>(CI.getArgOperand(2)) &&
2185             cast<ConstantInt>(CI.getArgOperand(1))->getZExtValue() < 2 &&
2186             cast<ConstantInt>(CI.getArgOperand(2))->getZExtValue() < 4,
2187             "invalid arguments to llvm.prefetch",
2188             &CI);
2189     break;
2190   case Intrinsic::stackprotector:
2191     Assert1(isa<AllocaInst>(CI.getArgOperand(1)->stripPointerCasts()),
2192             "llvm.stackprotector parameter #2 must resolve to an alloca.",
2193             &CI);
2194     break;
2195   case Intrinsic::lifetime_start:
2196   case Intrinsic::lifetime_end:
2197   case Intrinsic::invariant_start:
2198     Assert1(isa<ConstantInt>(CI.getArgOperand(0)),
2199             "size argument of memory use markers must be a constant integer",
2200             &CI);
2201     break;
2202   case Intrinsic::invariant_end:
2203     Assert1(isa<ConstantInt>(CI.getArgOperand(1)),
2204             "llvm.invariant.end parameter #2 must be a constant integer", &CI);
2205     break;
2206   }
2207 }
2208
2209 void Verifier::verifyDebugInfo(Module &M) {
2210   // Verify Debug Info.
2211   if (!DisableDebugInfoVerifier) {
2212     DebugInfoFinder Finder;
2213     Finder.processModule(M);
2214
2215     for (DebugInfoFinder::iterator I = Finder.compile_unit_begin(),
2216          E = Finder.compile_unit_end(); I != E; ++I)
2217       Assert1(DICompileUnit(*I).Verify(), "DICompileUnit does not Verify!", *I);
2218     for (DebugInfoFinder::iterator I = Finder.subprogram_begin(),
2219          E = Finder.subprogram_end(); I != E; ++I)
2220       Assert1(DISubprogram(*I).Verify(), "DISubprogram does not Verify!", *I);
2221     for (DebugInfoFinder::iterator I = Finder.global_variable_begin(),
2222          E = Finder.global_variable_end(); I != E; ++I)
2223       Assert1(DIGlobalVariable(*I).Verify(),
2224               "DIGlobalVariable does not Verify!", *I);
2225     for (DebugInfoFinder::iterator I = Finder.type_begin(),
2226          E = Finder.type_end(); I != E; ++I)
2227       Assert1(DIType(*I).Verify(), "DIType does not Verify!", *I);
2228     for (DebugInfoFinder::iterator I = Finder.scope_begin(),
2229          E = Finder.scope_end(); I != E; ++I)
2230       Assert1(DIScope(*I).Verify(), "DIScope does not Verify!", *I);
2231   }
2232 }
2233
2234 //===----------------------------------------------------------------------===//
2235 //  Implement the public interfaces to this file...
2236 //===----------------------------------------------------------------------===//
2237
2238 FunctionPass *llvm::createVerifierPass(VerifierFailureAction action) {
2239   return new Verifier(action);
2240 }
2241
2242
2243 /// verifyFunction - Check a function for errors, printing messages on stderr.
2244 /// Return true if the function is corrupt.
2245 ///
2246 bool llvm::verifyFunction(const Function &f, VerifierFailureAction action) {
2247   Function &F = const_cast<Function&>(f);
2248   assert(!F.isDeclaration() && "Cannot verify external functions");
2249
2250   FunctionPassManager FPM(F.getParent());
2251   Verifier *V = new Verifier(action);
2252   FPM.add(V);
2253   FPM.run(F);
2254   return V->Broken;
2255 }
2256
2257 /// verifyModule - Check a module for errors, printing messages on stderr.
2258 /// Return true if the module is corrupt.
2259 ///
2260 bool llvm::verifyModule(const Module &M, VerifierFailureAction action,
2261                         std::string *ErrorInfo) {
2262   PassManager PM;
2263   Verifier *V = new Verifier(action);
2264   PM.add(V);
2265   PM.run(const_cast<Module&>(M));
2266
2267   if (ErrorInfo && V->Broken)
2268     *ErrorInfo = V->MessagesStr.str();
2269   return V->Broken;
2270 }