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/IR/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/IR/CFG.h"
  55 #include "llvm/IR/CallSite.h"
  56 #include "llvm/IR/CallingConv.h"
  57 #include "llvm/IR/ConstantRange.h"
  58 #include "llvm/IR/Constants.h"
  59 #include "llvm/IR/DataLayout.h"
  60 #include "llvm/IR/DebugInfo.h"
  61 #include "llvm/IR/DerivedTypes.h"
  62 #include "llvm/IR/Dominators.h"
  63 #include "llvm/IR/InlineAsm.h"
  64 #include "llvm/IR/InstIterator.h"
  65 #include "llvm/IR/InstVisitor.h"
  66 #include "llvm/IR/IntrinsicInst.h"
  67 #include "llvm/IR/LLVMContext.h"
  68 #include "llvm/IR/Metadata.h"
  69 #include "llvm/IR/Module.h"
  70 #include "llvm/IR/PassManager.h"
  71 #include "llvm/IR/Statepoint.h"
  72 #include "llvm/Pass.h"
  73 #include "llvm/Support/CommandLine.h"
  74 #include "llvm/Support/Debug.h"
  75 #include "llvm/Support/ErrorHandling.h"
  76 #include "llvm/Support/raw_ostream.h"
  77 #include <algorithm>
  78 #include <cstdarg>
  79 using namespace llvm;
  80
  81 static cl::opt<bool> VerifyDebugInfo("verify-debug-info", cl::init(true));
  82
  83 namespace {
  84 struct VerifierSupport {
  85   raw_ostream &OS;
  86   const Module *M;
  87
  88   /// \brief Track the brokenness of the module while recursively visiting.
  89   bool Broken;
  90   bool EverBroken;
  91
  92   explicit VerifierSupport(raw_ostream &OS)
  93       : OS(OS), M(nullptr), Broken(false), EverBroken(false) {}
  94
  95 private:
  96   void Write(const Value *V) {
  97     if (!V)
  98       return;
  99     if (isa<Instruction>(V)) {
 100       OS << *V << '\n';
 101     } else {
 102       V->printAsOperand(OS, true, M);
 103       OS << '\n';
 104     }
 105   }
 106
 107   void Write(const Metadata *MD) {
 108     if (!MD)
 109       return;
 110     MD->print(OS, M);
 111     OS << '\n';
 112   }
 113
 114   void Write(const NamedMDNode *NMD) {
 115     if (!NMD)
 116       return;
 117     NMD->print(OS);
 118     OS << '\n';
 119   }
 120
 121   void Write(Type *T) {
 122     if (!T)
 123       return;
 124     OS << ' ' << *T;
 125   }
 126
 127   void Write(const Comdat *C) {
 128     if (!C)
 129       return;
 130     OS << *C;
 131   }
 132
 133   template <typename T1, typename... Ts>
 134   void WriteTs(const T1 &V1, const Ts &... Vs) {
 135     Write(V1);
 136     WriteTs(Vs...);
 137   }
 138
 139   template <typename... Ts> void WriteTs() {}
 140
 141 public:
 142   /// \brief A check failed, so printout out the condition and the message.
 143   ///
 144   /// This provides a nice place to put a breakpoint if you want to see why
 145   /// something is not correct.
 146   void CheckFailed(const Twine &Message) {
 147     OS << Message << '\n';
 148     EverBroken = Broken = true;
 149   }
 150
 151   /// \brief A check failed (with values to print).
 152   ///
 153   /// This calls the Message-only version so that the above is easier to set a
 154   /// breakpoint on.
 155   template <typename T1, typename... Ts>
 156   void CheckFailed(const Twine &Message, const T1 &V1, const Ts &... Vs) {
 157     CheckFailed(Message);
 158     WriteTs(V1, Vs...);
 159   }
 160 };
 161
 162 class Verifier : public InstVisitor<Verifier>, VerifierSupport {
 163   friend class InstVisitor<Verifier>;
 164
 165   LLVMContext *Context;
 166   DominatorTree DT;
 167
 168   /// \brief When verifying a basic block, keep track of all of the
 169   /// instructions we have seen so far.
 170   ///
 171   /// This allows us to do efficient dominance checks for the case when an
 172   /// instruction has an operand that is an instruction in the same block.
 173   SmallPtrSet<Instruction *, 16> InstsInThisBlock;
 174
 175   /// \brief Keep track of the metadata nodes that have been checked already.
 176   SmallPtrSet<const Metadata *, 32> MDNodes;
 177
 178   /// \brief The personality function referenced by the LandingPadInsts.
 179   /// All LandingPadInsts within the same function must use the same
 180   /// personality function.
 181   const Value *PersonalityFn;
 182
 183   /// \brief Whether we've seen a call to @llvm.frameescape in this function
 184   /// already.
 185   bool SawFrameEscape;
 186
 187   /// Stores the count of how many objects were passed to llvm.frameescape for a
 188   /// given function and the largest index passed to llvm.framerecover.
 189   DenseMap<Function *, std::pair<unsigned, unsigned>> FrameEscapeInfo;
 190
 191 public:
 192   explicit Verifier(raw_ostream &OS)
 193       : VerifierSupport(OS), Context(nullptr), PersonalityFn(nullptr),
 194         SawFrameEscape(false) {}
 195
 196   bool verify(const Function &F) {
 197     M = F.getParent();
 198     Context = &M->getContext();
 199
 200     // First ensure the function is well-enough formed to compute dominance
 201     // information.
 202     if (F.empty()) {
 203       OS << "Function '" << F.getName()
 204          << "' does not contain an entry block!\n";
 205       return false;
 206     }
 207     for (Function::const_iterator I = F.begin(), E = F.end(); I != E; ++I) {
 208       if (I->empty() || !I->back().isTerminator()) {
 209         OS << "Basic Block in function '" << F.getName()
 210            << "' does not have terminator!\n";
 211         I->printAsOperand(OS, true);
 212         OS << "\n";
 213         return false;
 214       }
 215     }
 216
 217     // Now directly compute a dominance tree. We don't rely on the pass
 218     // manager to provide this as it isolates us from a potentially
 219     // out-of-date dominator tree and makes it significantly more complex to
 220     // run this code outside of a pass manager.
 221     // FIXME: It's really gross that we have to cast away constness here.
 222     DT.recalculate(const_cast<Function &>(F));
 223
 224     Broken = false;
 225     // FIXME: We strip const here because the inst visitor strips const.
 226     visit(const_cast<Function &>(F));
 227     InstsInThisBlock.clear();
 228     PersonalityFn = nullptr;
 229     SawFrameEscape = false;
 230
 231     return !Broken;
 232   }
 233
 234   bool verify(const Module &M) {
 235     this->M = &M;
 236     Context = &M.getContext();
 237     Broken = false;
 238
 239     // Scan through, checking all of the external function's linkage now...
 240     for (Module::const_iterator I = M.begin(), E = M.end(); I != E; ++I) {
 241       visitGlobalValue(*I);
 242
 243       // Check to make sure function prototypes are okay.
 244       if (I->isDeclaration())
 245         visitFunction(*I);
 246     }
 247
 248     // Now that we've visited every function, verify that we never asked to
 249     // recover a frame index that wasn't escaped.
 250     verifyFrameRecoverIndices();
 251
 252     for (Module::const_global_iterator I = M.global_begin(), E = M.global_end();
 253          I != E; ++I)
 254       visitGlobalVariable(*I);
 255
 256     for (Module::const_alias_iterator I = M.alias_begin(), E = M.alias_end();
 257          I != E; ++I)
 258       visitGlobalAlias(*I);
 259
 260     for (Module::const_named_metadata_iterator I = M.named_metadata_begin(),
 261                                                E = M.named_metadata_end();
 262          I != E; ++I)
 263       visitNamedMDNode(*I);
 264
 265     for (const StringMapEntry<Comdat> &SMEC : M.getComdatSymbolTable())
 266       visitComdat(SMEC.getValue());
 267
 268     visitModuleFlags(M);
 269     visitModuleIdents(M);
 270
 271     // Verify debug info last.
 272     verifyDebugInfo();
 273
 274     return !Broken;
 275   }
 276
 277 private:
 278   // Verification methods...
 279   void visitGlobalValue(const GlobalValue &GV);
 280   void visitGlobalVariable(const GlobalVariable &GV);
 281   void visitGlobalAlias(const GlobalAlias &GA);
 282   void visitAliaseeSubExpr(const GlobalAlias &A, const Constant &C);
 283   void visitAliaseeSubExpr(SmallPtrSetImpl<const GlobalAlias *> &Visited,
 284                            const GlobalAlias &A, const Constant &C);
 285   void visitNamedMDNode(const NamedMDNode &NMD);
 286   void visitMDNode(const MDNode &MD);
 287   void visitMetadataAsValue(const MetadataAsValue &MD, Function *F);
 288   void visitValueAsMetadata(const ValueAsMetadata &MD, Function *F);
 289   void visitComdat(const Comdat &C);
 290   void visitModuleIdents(const Module &M);
 291   void visitModuleFlags(const Module &M);
 292   void visitModuleFlag(const MDNode *Op,
 293                        DenseMap<const MDString *, const MDNode *> &SeenIDs,
 294                        SmallVectorImpl<const MDNode *> &Requirements);
 295   void visitFunction(const Function &F);
 296   void visitBasicBlock(BasicBlock &BB);
 297   void visitRangeMetadata(Instruction& I, MDNode* Range, Type* Ty);
 298
 299 #define HANDLE_SPECIALIZED_MDNODE_LEAF(CLASS) void visit##CLASS(const CLASS &N);
 300 #include "llvm/IR/Metadata.def"
 301
 302   // InstVisitor overrides...
 303   using InstVisitor<Verifier>::visit;
 304   void visit(Instruction &I);
 305
 306   void visitTruncInst(TruncInst &I);
 307   void visitZExtInst(ZExtInst &I);
 308   void visitSExtInst(SExtInst &I);
 309   void visitFPTruncInst(FPTruncInst &I);
 310   void visitFPExtInst(FPExtInst &I);
 311   void visitFPToUIInst(FPToUIInst &I);
 312   void visitFPToSIInst(FPToSIInst &I);
 313   void visitUIToFPInst(UIToFPInst &I);
 314   void visitSIToFPInst(SIToFPInst &I);
 315   void visitIntToPtrInst(IntToPtrInst &I);
 316   void visitPtrToIntInst(PtrToIntInst &I);
 317   void visitBitCastInst(BitCastInst &I);
 318   void visitAddrSpaceCastInst(AddrSpaceCastInst &I);
 319   void visitPHINode(PHINode &PN);
 320   void visitBinaryOperator(BinaryOperator &B);
 321   void visitICmpInst(ICmpInst &IC);
 322   void visitFCmpInst(FCmpInst &FC);
 323   void visitExtractElementInst(ExtractElementInst &EI);
 324   void visitInsertElementInst(InsertElementInst &EI);
 325   void visitShuffleVectorInst(ShuffleVectorInst &EI);
 326   void visitVAArgInst(VAArgInst &VAA) { visitInstruction(VAA); }
 327   void visitCallInst(CallInst &CI);
 328   void visitInvokeInst(InvokeInst &II);
 329   void visitGetElementPtrInst(GetElementPtrInst &GEP);
 330   void visitLoadInst(LoadInst &LI);
 331   void visitStoreInst(StoreInst &SI);
 332   void verifyDominatesUse(Instruction &I, unsigned i);
 333   void visitInstruction(Instruction &I);
 334   void visitTerminatorInst(TerminatorInst &I);
 335   void visitBranchInst(BranchInst &BI);
 336   void visitReturnInst(ReturnInst &RI);
 337   void visitSwitchInst(SwitchInst &SI);
 338   void visitIndirectBrInst(IndirectBrInst &BI);
 339   void visitSelectInst(SelectInst &SI);
 340   void visitUserOp1(Instruction &I);
 341   void visitUserOp2(Instruction &I) { visitUserOp1(I); }
 342   void visitIntrinsicFunctionCall(Intrinsic::ID ID, CallInst &CI);
 343   template <class DbgIntrinsicTy>
 344   void visitDbgIntrinsic(StringRef Kind, DbgIntrinsicTy &DII);
 345   void visitAtomicCmpXchgInst(AtomicCmpXchgInst &CXI);
 346   void visitAtomicRMWInst(AtomicRMWInst &RMWI);
 347   void visitFenceInst(FenceInst &FI);
 348   void visitAllocaInst(AllocaInst &AI);
 349   void visitExtractValueInst(ExtractValueInst &EVI);
 350   void visitInsertValueInst(InsertValueInst &IVI);
 351   void visitLandingPadInst(LandingPadInst &LPI);
 352
 353   void VerifyCallSite(CallSite CS);
 354   void verifyMustTailCall(CallInst &CI);
 355   bool PerformTypeCheck(Intrinsic::ID ID, Function *F, Type *Ty, int VT,
 356                         unsigned ArgNo, std::string &Suffix);
 357   bool VerifyIntrinsicType(Type *Ty, ArrayRef<Intrinsic::IITDescriptor> &Infos,
 358                            SmallVectorImpl<Type *> &ArgTys);
 359   bool VerifyIntrinsicIsVarArg(bool isVarArg,
 360                                ArrayRef<Intrinsic::IITDescriptor> &Infos);
 361   bool VerifyAttributeCount(AttributeSet Attrs, unsigned Params);
 362   void VerifyAttributeTypes(AttributeSet Attrs, unsigned Idx, bool isFunction,
 363                             const Value *V);
 364   void VerifyParameterAttrs(AttributeSet Attrs, unsigned Idx, Type *Ty,
 365                             bool isReturnValue, const Value *V);
 366   void VerifyFunctionAttrs(FunctionType *FT, AttributeSet Attrs,
 367                            const Value *V);
 368
 369   void VerifyConstantExprBitcastType(const ConstantExpr *CE);
 370   void VerifyStatepoint(ImmutableCallSite CS);
 371   void verifyFrameRecoverIndices();
 372
 373   // Module-level debug info verification...
 374   void verifyDebugInfo();
 375   void processInstructions(DebugInfoFinder &Finder);
 376   void processCallInst(DebugInfoFinder &Finder, const CallInst &CI);
 377 };
 378 } // End anonymous namespace
 379
 380 // Assert - We know that cond should be true, if not print an error message.
 381 #define Assert(C, ...) \
 382   do { if (!(C)) { CheckFailed(__VA_ARGS__); return; } } while (0)
 383
 384 void Verifier::visit(Instruction &I) {
 385   for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i)
 386     Assert(I.getOperand(i) != nullptr, "Operand is null", &I);
 387   InstVisitor<Verifier>::visit(I);
 388 }
 389
 390
 391 void Verifier::visitGlobalValue(const GlobalValue &GV) {
 392   Assert(!GV.isDeclaration() || GV.hasExternalLinkage() ||
 393              GV.hasExternalWeakLinkage(),
 394          "Global is external, but doesn't have external or weak linkage!", &GV);
 395
 396   Assert(GV.getAlignment() <= Value::MaximumAlignment,
 397          "huge alignment values are unsupported", &GV);
 398   Assert(!GV.hasAppendingLinkage() || isa<GlobalVariable>(GV),
 399          "Only global variables can have appending linkage!", &GV);
 400
 401   if (GV.hasAppendingLinkage()) {
 402     const GlobalVariable *GVar = dyn_cast<GlobalVariable>(&GV);
 403     Assert(GVar && GVar->getType()->getElementType()->isArrayTy(),
 404            "Only global arrays can have appending linkage!", GVar);
 405   }
 406 }
 407
 408 void Verifier::visitGlobalVariable(const GlobalVariable &GV) {
 409   if (GV.hasInitializer()) {
 410     Assert(GV.getInitializer()->getType() == GV.getType()->getElementType(),
 411            "Global variable initializer type does not match global "
 412            "variable type!",
 413            &GV);
 414
 415     // If the global has common linkage, it must have a zero initializer and
 416     // cannot be constant.
 417     if (GV.hasCommonLinkage()) {
 418       Assert(GV.getInitializer()->isNullValue(),
 419              "'common' global must have a zero initializer!", &GV);
 420       Assert(!GV.isConstant(), "'common' global may not be marked constant!",
 421              &GV);
 422       Assert(!GV.hasComdat(), "'common' global may not be in a Comdat!", &GV);
 423     }
 424   } else {
 425     Assert(GV.hasExternalLinkage() || GV.hasExternalWeakLinkage(),
 426            "invalid linkage type for global declaration", &GV);
 427   }
 428
 429   if (GV.hasName() && (GV.getName() == "llvm.global_ctors" ||
 430                        GV.getName() == "llvm.global_dtors")) {
 431     Assert(!GV.hasInitializer() || GV.hasAppendingLinkage(),
 432            "invalid linkage for intrinsic global variable", &GV);
 433     // Don't worry about emitting an error for it not being an array,
 434     // visitGlobalValue will complain on appending non-array.
 435     if (ArrayType *ATy = dyn_cast<ArrayType>(GV.getType()->getElementType())) {
 436       StructType *STy = dyn_cast<StructType>(ATy->getElementType());
 437       PointerType *FuncPtrTy =
 438           FunctionType::get(Type::getVoidTy(*Context), false)->getPointerTo();
 439       // FIXME: Reject the 2-field form in LLVM 4.0.
 440       Assert(STy &&
 441                  (STy->getNumElements() == 2 || STy->getNumElements() == 3) &&
 442                  STy->getTypeAtIndex(0u)->isIntegerTy(32) &&
 443                  STy->getTypeAtIndex(1) == FuncPtrTy,
 444              "wrong type for intrinsic global variable", &GV);
 445       if (STy->getNumElements() == 3) {
 446         Type *ETy = STy->getTypeAtIndex(2);
 447         Assert(ETy->isPointerTy() &&
 448                    cast<PointerType>(ETy)->getElementType()->isIntegerTy(8),
 449                "wrong type for intrinsic global variable", &GV);
 450       }
 451     }
 452   }
 453
 454   if (GV.hasName() && (GV.getName() == "llvm.used" ||
 455                        GV.getName() == "llvm.compiler.used")) {
 456     Assert(!GV.hasInitializer() || GV.hasAppendingLinkage(),
 457            "invalid linkage for intrinsic global variable", &GV);
 458     Type *GVType = GV.getType()->getElementType();
 459     if (ArrayType *ATy = dyn_cast<ArrayType>(GVType)) {
 460       PointerType *PTy = dyn_cast<PointerType>(ATy->getElementType());
 461       Assert(PTy, "wrong type for intrinsic global variable", &GV);
 462       if (GV.hasInitializer()) {
 463         const Constant *Init = GV.getInitializer();
 464         const ConstantArray *InitArray = dyn_cast<ConstantArray>(Init);
 465         Assert(InitArray, "wrong initalizer for intrinsic global variable",
 466                Init);
 467         for (unsigned i = 0, e = InitArray->getNumOperands(); i != e; ++i) {
 468           Value *V = Init->getOperand(i)->stripPointerCastsNoFollowAliases();
 469           Assert(isa<GlobalVariable>(V) || isa<Function>(V) ||
 470                      isa<GlobalAlias>(V),
 471                  "invalid llvm.used member", V);
 472           Assert(V->hasName(), "members of llvm.used must be named", V);
 473         }
 474       }
 475     }
 476   }
 477
 478   Assert(!GV.hasDLLImportStorageClass() ||
 479              (GV.isDeclaration() && GV.hasExternalLinkage()) ||
 480              GV.hasAvailableExternallyLinkage(),
 481          "Global is marked as dllimport, but not external", &GV);
 482
 483   if (!GV.hasInitializer()) {
 484     visitGlobalValue(GV);
 485     return;
 486   }
 487
 488   // Walk any aggregate initializers looking for bitcasts between address spaces
 489   SmallPtrSet<const Value *, 4> Visited;
 490   SmallVector<const Value *, 4> WorkStack;
 491   WorkStack.push_back(cast<Value>(GV.getInitializer()));
 492
 493   while (!WorkStack.empty()) {
 494     const Value *V = WorkStack.pop_back_val();
 495     if (!Visited.insert(V).second)
 496       continue;
 497
 498     if (const User *U = dyn_cast<User>(V)) {
 499       WorkStack.append(U->op_begin(), U->op_end());
 500     }
 501
 502     if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
 503       VerifyConstantExprBitcastType(CE);
 504       if (Broken)
 505         return;
 506     }
 507   }
 508
 509   visitGlobalValue(GV);
 510 }
 511
 512 void Verifier::visitAliaseeSubExpr(const GlobalAlias &GA, const Constant &C) {
 513   SmallPtrSet<const GlobalAlias*, 4> Visited;
 514   Visited.insert(&GA);
 515   visitAliaseeSubExpr(Visited, GA, C);
 516 }
 517
 518 void Verifier::visitAliaseeSubExpr(SmallPtrSetImpl<const GlobalAlias*> &Visited,
 519                                    const GlobalAlias &GA, const Constant &C) {
 520   if (const auto *GV = dyn_cast<GlobalValue>(&C)) {
 521     Assert(!GV->isDeclaration(), "Alias must point to a definition", &GA);
 522
 523     if (const auto *GA2 = dyn_cast<GlobalAlias>(GV)) {
 524       Assert(Visited.insert(GA2).second, "Aliases cannot form a cycle", &GA);
 525
 526       Assert(!GA2->mayBeOverridden(), "Alias cannot point to a weak alias",
 527              &GA);
 528     } else {
 529       // Only continue verifying subexpressions of GlobalAliases.
 530       // Do not recurse into global initializers.
 531       return;
 532     }
 533   }
 534
 535   if (const auto *CE = dyn_cast<ConstantExpr>(&C))
 536     VerifyConstantExprBitcastType(CE);
 537
 538   for (const Use &U : C.operands()) {
 539     Value *V = &*U;
 540     if (const auto *GA2 = dyn_cast<GlobalAlias>(V))
 541       visitAliaseeSubExpr(Visited, GA, *GA2->getAliasee());
 542     else if (const auto *C2 = dyn_cast<Constant>(V))
 543       visitAliaseeSubExpr(Visited, GA, *C2);
 544   }
 545 }
 546
 547 void Verifier::visitGlobalAlias(const GlobalAlias &GA) {
 548   Assert(!GA.getName().empty(), "Alias name cannot be empty!", &GA);
 549   Assert(GlobalAlias::isValidLinkage(GA.getLinkage()),
 550          "Alias should have private, internal, linkonce, weak, linkonce_odr, "
 551          "weak_odr, or external linkage!",
 552          &GA);
 553   const Constant *Aliasee = GA.getAliasee();
 554   Assert(Aliasee, "Aliasee cannot be NULL!", &GA);
 555   Assert(GA.getType() == Aliasee->getType(),
 556          "Alias and aliasee types should match!", &GA);
 557
 558   Assert(isa<GlobalValue>(Aliasee) || isa<ConstantExpr>(Aliasee),
 559          "Aliasee should be either GlobalValue or ConstantExpr", &GA);
 560
 561   visitAliaseeSubExpr(GA, *Aliasee);
 562
 563   visitGlobalValue(GA);
 564 }
 565
 566 void Verifier::visitNamedMDNode(const NamedMDNode &NMD) {
 567   for (unsigned i = 0, e = NMD.getNumOperands(); i != e; ++i) {
 568     MDNode *MD = NMD.getOperand(i);
 569     if (!MD)
 570       continue;
 571
 572     if (NMD.getName() == "llvm.dbg.cu") {
 573       Assert(isa<MDCompileUnit>(MD), "invalid compile unit", &NMD, MD);
 574     }
 575
 576     visitMDNode(*MD);
 577   }
 578 }
 579
 580 void Verifier::visitMDNode(const MDNode &MD) {
 581   // Only visit each node once.  Metadata can be mutually recursive, so this
 582   // avoids infinite recursion here, as well as being an optimization.
 583   if (!MDNodes.insert(&MD).second)
 584     return;
 585
 586   switch (MD.getMetadataID()) {
 587   default:
 588     llvm_unreachable("Invalid MDNode subclass");
 589   case Metadata::MDTupleKind:
 590     break;
 591 #define HANDLE_SPECIALIZED_MDNODE_LEAF(CLASS)                                  \
 592   case Metadata::CLASS##Kind:                                                  \
 593     visit##CLASS(cast<CLASS>(MD));                                             \
 594     break;
 595 #include "llvm/IR/Metadata.def"
 596   }
 597
 598   for (unsigned i = 0, e = MD.getNumOperands(); i != e; ++i) {
 599     Metadata *Op = MD.getOperand(i);
 600     if (!Op)
 601       continue;
 602     Assert(!isa<LocalAsMetadata>(Op), "Invalid operand for global metadata!",
 603            &MD, Op);
 604     if (auto *N = dyn_cast<MDNode>(Op)) {
 605       visitMDNode(*N);
 606       continue;
 607     }
 608     if (auto *V = dyn_cast<ValueAsMetadata>(Op)) {
 609       visitValueAsMetadata(*V, nullptr);
 610       continue;
 611     }
 612   }
 613
 614   // Check these last, so we diagnose problems in operands first.
 615   Assert(!MD.isTemporary(), "Expected no forward declarations!", &MD);
 616   Assert(MD.isResolved(), "All nodes should be resolved!", &MD);
 617 }
 618
 619 void Verifier::visitValueAsMetadata(const ValueAsMetadata &MD, Function *F) {
 620   Assert(MD.getValue(), "Expected valid value", &MD);
 621   Assert(!MD.getValue()->getType()->isMetadataTy(),
 622          "Unexpected metadata round-trip through values", &MD, MD.getValue());
 623
 624   auto *L = dyn_cast<LocalAsMetadata>(&MD);
 625   if (!L)
 626     return;
 627
 628   Assert(F, "function-local metadata used outside a function", L);
 629
 630   // If this was an instruction, bb, or argument, verify that it is in the
 631   // function that we expect.
 632   Function *ActualF = nullptr;
 633   if (Instruction *I = dyn_cast<Instruction>(L->getValue())) {
 634     Assert(I->getParent(), "function-local metadata not in basic block", L, I);
 635     ActualF = I->getParent()->getParent();
 636   } else if (BasicBlock *BB = dyn_cast<BasicBlock>(L->getValue()))
 637     ActualF = BB->getParent();
 638   else if (Argument *A = dyn_cast<Argument>(L->getValue()))
 639     ActualF = A->getParent();
 640   assert(ActualF && "Unimplemented function local metadata case!");
 641
 642   Assert(ActualF == F, "function-local metadata used in wrong function", L);
 643 }
 644
 645 void Verifier::visitMetadataAsValue(const MetadataAsValue &MDV, Function *F) {
 646   Metadata *MD = MDV.getMetadata();
 647   if (auto *N = dyn_cast<MDNode>(MD)) {
 648     visitMDNode(*N);
 649     return;
 650   }
 651
 652   // Only visit each node once.  Metadata can be mutually recursive, so this
 653   // avoids infinite recursion here, as well as being an optimization.
 654   if (!MDNodes.insert(MD).second)
 655     return;
 656
 657   if (auto *V = dyn_cast<ValueAsMetadata>(MD))
 658     visitValueAsMetadata(*V, F);
 659 }
 660
 661 void Verifier::visitMDLocation(const MDLocation &N) {
 662   Assert(N.getRawScope() && isa<MDLocalScope>(N.getRawScope()),
 663          "location requires a valid scope", &N, N.getRawScope());
 664   if (auto *IA = N.getRawInlinedAt())
 665     Assert(isa<MDLocation>(IA), "inlined-at should be a location", &N, IA);
 666 }
 667
 668 void Verifier::visitGenericDebugNode(const GenericDebugNode &N) {
 669   Assert(N.getTag(), "invalid tag", &N);
 670 }
 671
 672 void Verifier::visitMDSubrange(const MDSubrange &N) {
 673   Assert(N.getTag() == dwarf::DW_TAG_subrange_type, "invalid tag", &N);
 674 }
 675
 676 void Verifier::visitMDEnumerator(const MDEnumerator &N) {
 677   Assert(N.getTag() == dwarf::DW_TAG_enumerator, "invalid tag", &N);
 678 }
 679
 680 void Verifier::visitMDBasicType(const MDBasicType &N) {
 681   Assert(N.getTag() == dwarf::DW_TAG_base_type ||
 682              N.getTag() == dwarf::DW_TAG_unspecified_type,
 683          "invalid tag", &N);
 684 }
 685
 686 void Verifier::visitMDDerivedType(const MDDerivedType &N) {
 687   Assert(N.getTag() == dwarf::DW_TAG_typedef ||
 688              N.getTag() == dwarf::DW_TAG_pointer_type ||
 689              N.getTag() == dwarf::DW_TAG_ptr_to_member_type ||
 690              N.getTag() == dwarf::DW_TAG_reference_type ||
 691              N.getTag() == dwarf::DW_TAG_rvalue_reference_type ||
 692              N.getTag() == dwarf::DW_TAG_const_type ||
 693              N.getTag() == dwarf::DW_TAG_volatile_type ||
 694              N.getTag() == dwarf::DW_TAG_restrict_type ||
 695              N.getTag() == dwarf::DW_TAG_member ||
 696              N.getTag() == dwarf::DW_TAG_inheritance ||
 697              N.getTag() == dwarf::DW_TAG_friend,
 698          "invalid tag", &N);
 699 }
 700
 701 void Verifier::visitMDCompositeType(const MDCompositeType &N) {
 702   Assert(N.getTag() == dwarf::DW_TAG_array_type ||
 703              N.getTag() == dwarf::DW_TAG_structure_type ||
 704              N.getTag() == dwarf::DW_TAG_union_type ||
 705              N.getTag() == dwarf::DW_TAG_enumeration_type ||
 706              N.getTag() == dwarf::DW_TAG_subroutine_type ||
 707              N.getTag() == dwarf::DW_TAG_class_type,
 708          "invalid tag", &N);
 709 }
 710
 711 void Verifier::visitMDSubroutineType(const MDSubroutineType &N) {
 712   Assert(N.getTag() == dwarf::DW_TAG_subroutine_type, "invalid tag", &N);
 713 }
 714
 715 void Verifier::visitMDFile(const MDFile &N) {
 716   Assert(N.getTag() == dwarf::DW_TAG_file_type, "invalid tag", &N);
 717 }
 718
 719 void Verifier::visitMDCompileUnit(const MDCompileUnit &N) {
 720   Assert(N.getTag() == dwarf::DW_TAG_compile_unit, "invalid tag", &N);
 721 }
 722
 723 void Verifier::visitMDSubprogram(const MDSubprogram &N) {
 724   Assert(N.getTag() == dwarf::DW_TAG_subprogram, "invalid tag", &N);
 725 }
 726
 727 void Verifier::visitMDLexicalBlock(const MDLexicalBlock &N) {
 728   Assert(N.getTag() == dwarf::DW_TAG_lexical_block, "invalid tag", &N);
 729 }
 730
 731 void Verifier::visitMDLexicalBlockFile(const MDLexicalBlockFile &N) {
 732   Assert(N.getTag() == dwarf::DW_TAG_lexical_block, "invalid tag", &N);
 733 }
 734
 735 void Verifier::visitMDNamespace(const MDNamespace &N) {
 736   Assert(N.getTag() == dwarf::DW_TAG_namespace, "invalid tag", &N);
 737 }
 738
 739 void Verifier::visitMDTemplateTypeParameter(const MDTemplateTypeParameter &N) {
 740   Assert(N.getTag() == dwarf::DW_TAG_template_type_parameter, "invalid tag",
 741          &N);
 742 }
 743
 744 void Verifier::visitMDTemplateValueParameter(
 745     const MDTemplateValueParameter &N) {
 746   Assert(N.getTag() == dwarf::DW_TAG_template_value_parameter ||
 747              N.getTag() == dwarf::DW_TAG_GNU_template_template_param ||
 748              N.getTag() == dwarf::DW_TAG_GNU_template_parameter_pack,
 749          "invalid tag", &N);
 750 }
 751
 752 void Verifier::visitMDGlobalVariable(const MDGlobalVariable &N) {
 753   Assert(N.getTag() == dwarf::DW_TAG_variable, "invalid tag", &N);
 754 }
 755
 756 void Verifier::visitMDLocalVariable(const MDLocalVariable &N) {
 757   Assert(N.getTag() == dwarf::DW_TAG_auto_variable ||
 758              N.getTag() == dwarf::DW_TAG_arg_variable,
 759          "invalid tag", &N);
 760 }
 761
 762 void Verifier::visitMDExpression(const MDExpression &N) {
 763   Assert(N.isValid(), "invalid expression", &N);
 764 }
 765
 766 void Verifier::visitMDObjCProperty(const MDObjCProperty &N) {
 767   Assert(N.getTag() == dwarf::DW_TAG_APPLE_property, "invalid tag", &N);
 768 }
 769
 770 void Verifier::visitMDImportedEntity(const MDImportedEntity &N) {
 771   Assert(N.getTag() == dwarf::DW_TAG_imported_module ||
 772              N.getTag() == dwarf::DW_TAG_imported_declaration,
 773          "invalid tag", &N);
 774 }
 775
 776 void Verifier::visitComdat(const Comdat &C) {
 777   // The Module is invalid if the GlobalValue has private linkage.  Entities
 778   // with private linkage don't have entries in the symbol table.
 779   if (const GlobalValue *GV = M->getNamedValue(C.getName()))
 780     Assert(!GV->hasPrivateLinkage(), "comdat global value has private linkage",
 781            GV);
 782 }
 783
 784 void Verifier::visitModuleIdents(const Module &M) {
 785   const NamedMDNode *Idents = M.getNamedMetadata("llvm.ident");
 786   if (!Idents)
 787     return;
 788
 789   // llvm.ident takes a list of metadata entry. Each entry has only one string.
 790   // Scan each llvm.ident entry and make sure that this requirement is met.
 791   for (unsigned i = 0, e = Idents->getNumOperands(); i != e; ++i) {
 792     const MDNode *N = Idents->getOperand(i);
 793     Assert(N->getNumOperands() == 1,
 794            "incorrect number of operands in llvm.ident metadata", N);
 795     Assert(dyn_cast_or_null<MDString>(N->getOperand(0)),
 796            ("invalid value for llvm.ident metadata entry operand"
 797             "(the operand should be a string)"),
 798            N->getOperand(0));
 799   }
 800 }
 801
 802 void Verifier::visitModuleFlags(const Module &M) {
 803   const NamedMDNode *Flags = M.getModuleFlagsMetadata();
 804   if (!Flags) return;
 805
 806   // Scan each flag, and track the flags and requirements.
 807   DenseMap<const MDString*, const MDNode*> SeenIDs;
 808   SmallVector<const MDNode*, 16> Requirements;
 809   for (unsigned I = 0, E = Flags->getNumOperands(); I != E; ++I) {
 810     visitModuleFlag(Flags->getOperand(I), SeenIDs, Requirements);
 811   }
 812
 813   // Validate that the requirements in the module are valid.
 814   for (unsigned I = 0, E = Requirements.size(); I != E; ++I) {
 815     const MDNode *Requirement = Requirements[I];
 816     const MDString *Flag = cast<MDString>(Requirement->getOperand(0));
 817     const Metadata *ReqValue = Requirement->getOperand(1);
 818
 819     const MDNode *Op = SeenIDs.lookup(Flag);
 820     if (!Op) {
 821       CheckFailed("invalid requirement on flag, flag is not present in module",
 822                   Flag);
 823       continue;
 824     }
 825
 826     if (Op->getOperand(2) != ReqValue) {
 827       CheckFailed(("invalid requirement on flag, "
 828                    "flag does not have the required value"),
 829                   Flag);
 830       continue;
 831     }
 832   }
 833 }
 834
 835 void
 836 Verifier::visitModuleFlag(const MDNode *Op,
 837                           DenseMap<const MDString *, const MDNode *> &SeenIDs,
 838                           SmallVectorImpl<const MDNode *> &Requirements) {
 839   // Each module flag should have three arguments, the merge behavior (a
 840   // constant int), the flag ID (an MDString), and the value.
 841   Assert(Op->getNumOperands() == 3,
 842          "incorrect number of operands in module flag", Op);
 843   Module::ModFlagBehavior MFB;
 844   if (!Module::isValidModFlagBehavior(Op->getOperand(0), MFB)) {
 845     Assert(
 846         mdconst::dyn_extract_or_null<ConstantInt>(Op->getOperand(0)),
 847         "invalid behavior operand in module flag (expected constant integer)",
 848         Op->getOperand(0));
 849     Assert(false,
 850            "invalid behavior operand in module flag (unexpected constant)",
 851            Op->getOperand(0));
 852   }
 853   MDString *ID = dyn_cast_or_null<MDString>(Op->getOperand(1));
 854   Assert(ID, "invalid ID operand in module flag (expected metadata string)",
 855          Op->getOperand(1));
 856
 857   // Sanity check the values for behaviors with additional requirements.
 858   switch (MFB) {
 859   case Module::Error:
 860   case Module::Warning:
 861   case Module::Override:
 862     // These behavior types accept any value.
 863     break;
 864
 865   case Module::Require: {
 866     // The value should itself be an MDNode with two operands, a flag ID (an
 867     // MDString), and a value.
 868     MDNode *Value = dyn_cast<MDNode>(Op->getOperand(2));
 869     Assert(Value && Value->getNumOperands() == 2,
 870            "invalid value for 'require' module flag (expected metadata pair)",
 871            Op->getOperand(2));
 872     Assert(isa<MDString>(Value->getOperand(0)),
 873            ("invalid value for 'require' module flag "
 874             "(first value operand should be a string)"),
 875            Value->getOperand(0));
 876
 877     // Append it to the list of requirements, to check once all module flags are
 878     // scanned.
 879     Requirements.push_back(Value);
 880     break;
 881   }
 882
 883   case Module::Append:
 884   case Module::AppendUnique: {
 885     // These behavior types require the operand be an MDNode.
 886     Assert(isa<MDNode>(Op->getOperand(2)),
 887            "invalid value for 'append'-type module flag "
 888            "(expected a metadata node)",
 889            Op->getOperand(2));
 890     break;
 891   }
 892   }
 893
 894   // Unless this is a "requires" flag, check the ID is unique.
 895   if (MFB != Module::Require) {
 896     bool Inserted = SeenIDs.insert(std::make_pair(ID, Op)).second;
 897     Assert(Inserted,
 898            "module flag identifiers must be unique (or of 'require' type)", ID);
 899   }
 900 }
 901
 902 void Verifier::VerifyAttributeTypes(AttributeSet Attrs, unsigned Idx,
 903                                     bool isFunction, const Value *V) {
 904   unsigned Slot = ~0U;
 905   for (unsigned I = 0, E = Attrs.getNumSlots(); I != E; ++I)
 906     if (Attrs.getSlotIndex(I) == Idx) {
 907       Slot = I;
 908       break;
 909     }
 910
 911   assert(Slot != ~0U && "Attribute set inconsistency!");
 912
 913   for (AttributeSet::iterator I = Attrs.begin(Slot), E = Attrs.end(Slot);
 914          I != E; ++I) {
 915     if (I->isStringAttribute())
 916       continue;
 917
 918     if (I->getKindAsEnum() == Attribute::NoReturn ||
 919         I->getKindAsEnum() == Attribute::NoUnwind ||
 920         I->getKindAsEnum() == Attribute::NoInline ||
 921         I->getKindAsEnum() == Attribute::AlwaysInline ||
 922         I->getKindAsEnum() == Attribute::OptimizeForSize ||
 923         I->getKindAsEnum() == Attribute::StackProtect ||
 924         I->getKindAsEnum() == Attribute::StackProtectReq ||
 925         I->getKindAsEnum() == Attribute::StackProtectStrong ||
 926         I->getKindAsEnum() == Attribute::NoRedZone ||
 927         I->getKindAsEnum() == Attribute::NoImplicitFloat ||
 928         I->getKindAsEnum() == Attribute::Naked ||
 929         I->getKindAsEnum() == Attribute::InlineHint ||
 930         I->getKindAsEnum() == Attribute::StackAlignment ||
 931         I->getKindAsEnum() == Attribute::UWTable ||
 932         I->getKindAsEnum() == Attribute::NonLazyBind ||
 933         I->getKindAsEnum() == Attribute::ReturnsTwice ||
 934         I->getKindAsEnum() == Attribute::SanitizeAddress ||
 935         I->getKindAsEnum() == Attribute::SanitizeThread ||
 936         I->getKindAsEnum() == Attribute::SanitizeMemory ||
 937         I->getKindAsEnum() == Attribute::MinSize ||
 938         I->getKindAsEnum() == Attribute::NoDuplicate ||
 939         I->getKindAsEnum() == Attribute::Builtin ||
 940         I->getKindAsEnum() == Attribute::NoBuiltin ||
 941         I->getKindAsEnum() == Attribute::Cold ||
 942         I->getKindAsEnum() == Attribute::OptimizeNone ||
 943         I->getKindAsEnum() == Attribute::JumpTable) {
 944       if (!isFunction) {
 945         CheckFailed("Attribute '" + I->getAsString() +
 946                     "' only applies to functions!", V);
 947         return;
 948       }
 949     } else if (I->getKindAsEnum() == Attribute::ReadOnly ||
 950                I->getKindAsEnum() == Attribute::ReadNone) {
 951       if (Idx == 0) {
 952         CheckFailed("Attribute '" + I->getAsString() +
 953                     "' does not apply to function returns");
 954         return;
 955       }
 956     } else if (isFunction) {
 957       CheckFailed("Attribute '" + I->getAsString() +
 958                   "' does not apply to functions!", V);
 959       return;
 960     }
 961   }
 962 }
 963
 964 // VerifyParameterAttrs - Check the given attributes for an argument or return
 965 // value of the specified type.  The value V is printed in error messages.
 966 void Verifier::VerifyParameterAttrs(AttributeSet Attrs, unsigned Idx, Type *Ty,
 967                                     bool isReturnValue, const Value *V) {
 968   if (!Attrs.hasAttributes(Idx))
 969     return;
 970
 971   VerifyAttributeTypes(Attrs, Idx, false, V);
 972
 973   if (isReturnValue)
 974     Assert(!Attrs.hasAttribute(Idx, Attribute::ByVal) &&
 975                !Attrs.hasAttribute(Idx, Attribute::Nest) &&
 976                !Attrs.hasAttribute(Idx, Attribute::StructRet) &&
 977                !Attrs.hasAttribute(Idx, Attribute::NoCapture) &&
 978                !Attrs.hasAttribute(Idx, Attribute::Returned) &&
 979                !Attrs.hasAttribute(Idx, Attribute::InAlloca),
 980            "Attributes 'byval', 'inalloca', 'nest', 'sret', 'nocapture', and "
 981            "'returned' do not apply to return values!",
 982            V);
 983
 984   // Check for mutually incompatible attributes.  Only inreg is compatible with
 985   // sret.
 986   unsigned AttrCount = 0;
 987   AttrCount += Attrs.hasAttribute(Idx, Attribute::ByVal);
 988   AttrCount += Attrs.hasAttribute(Idx, Attribute::InAlloca);
 989   AttrCount += Attrs.hasAttribute(Idx, Attribute::StructRet) ||
 990                Attrs.hasAttribute(Idx, Attribute::InReg);
 991   AttrCount += Attrs.hasAttribute(Idx, Attribute::Nest);
 992   Assert(AttrCount <= 1, "Attributes 'byval', 'inalloca', 'inreg', 'nest', "
 993                          "and 'sret' are incompatible!",
 994          V);
 995
 996   Assert(!(Attrs.hasAttribute(Idx, Attribute::InAlloca) &&
 997            Attrs.hasAttribute(Idx, Attribute::ReadOnly)),
 998          "Attributes "
 999          "'inalloca and readonly' are incompatible!",
1000          V);
1001
1002   Assert(!(Attrs.hasAttribute(Idx, Attribute::StructRet) &&
1003            Attrs.hasAttribute(Idx, Attribute::Returned)),
1004          "Attributes "
1005          "'sret and returned' are incompatible!",
1006          V);
1007
1008   Assert(!(Attrs.hasAttribute(Idx, Attribute::ZExt) &&
1009            Attrs.hasAttribute(Idx, Attribute::SExt)),
1010          "Attributes "
1011          "'zeroext and signext' are incompatible!",
1012          V);
1013
1014   Assert(!(Attrs.hasAttribute(Idx, Attribute::ReadNone) &&
1015            Attrs.hasAttribute(Idx, Attribute::ReadOnly)),
1016          "Attributes "
1017          "'readnone and readonly' are incompatible!",
1018          V);
1019
1020   Assert(!(Attrs.hasAttribute(Idx, Attribute::NoInline) &&
1021            Attrs.hasAttribute(Idx, Attribute::AlwaysInline)),
1022          "Attributes "
1023          "'noinline and alwaysinline' are incompatible!",
1024          V);
1025
1026   Assert(!AttrBuilder(Attrs, Idx)
1027               .hasAttributes(AttributeFuncs::typeIncompatible(Ty, Idx), Idx),
1028          "Wrong types for attribute: " +
1029              AttributeFuncs::typeIncompatible(Ty, Idx).getAsString(Idx),
1030          V);
1031
1032   if (PointerType *PTy = dyn_cast<PointerType>(Ty)) {
1033     SmallPtrSet<const Type*, 4> Visited;
1034     if (!PTy->getElementType()->isSized(&Visited)) {
1035       Assert(!Attrs.hasAttribute(Idx, Attribute::ByVal) &&
1036                  !Attrs.hasAttribute(Idx, Attribute::InAlloca),
1037              "Attributes 'byval' and 'inalloca' do not support unsized types!",
1038              V);
1039     }
1040   } else {
1041     Assert(!Attrs.hasAttribute(Idx, Attribute::ByVal),
1042            "Attribute 'byval' only applies to parameters with pointer type!",
1043            V);
1044   }
1045 }
1046
1047 // VerifyFunctionAttrs - Check parameter attributes against a function type.
1048 // The value V is printed in error messages.
1049 void Verifier::VerifyFunctionAttrs(FunctionType *FT, AttributeSet Attrs,
1050                                    const Value *V) {
1051   if (Attrs.isEmpty())
1052     return;
1053
1054   bool SawNest = false;
1055   bool SawReturned = false;
1056   bool SawSRet = false;
1057
1058   for (unsigned i = 0, e = Attrs.getNumSlots(); i != e; ++i) {
1059     unsigned Idx = Attrs.getSlotIndex(i);
1060
1061     Type *Ty;
1062     if (Idx == 0)
1063       Ty = FT->getReturnType();
1064     else if (Idx-1 < FT->getNumParams())
1065       Ty = FT->getParamType(Idx-1);
1066     else
1067       break;  // VarArgs attributes, verified elsewhere.
1068
1069     VerifyParameterAttrs(Attrs, Idx, Ty, Idx == 0, V);
1070
1071     if (Idx == 0)
1072       continue;
1073
1074     if (Attrs.hasAttribute(Idx, Attribute::Nest)) {
1075       Assert(!SawNest, "More than one parameter has attribute nest!", V);
1076       SawNest = true;
1077     }
1078
1079     if (Attrs.hasAttribute(Idx, Attribute::Returned)) {
1080       Assert(!SawReturned, "More than one parameter has attribute returned!",
1081              V);
1082       Assert(Ty->canLosslesslyBitCastTo(FT->getReturnType()),
1083              "Incompatible "
1084              "argument and return types for 'returned' attribute",
1085              V);
1086       SawReturned = true;
1087     }
1088
1089     if (Attrs.hasAttribute(Idx, Attribute::StructRet)) {
1090       Assert(!SawSRet, "Cannot have multiple 'sret' parameters!", V);
1091       Assert(Idx == 1 || Idx == 2,
1092              "Attribute 'sret' is not on first or second parameter!", V);
1093       SawSRet = true;
1094     }
1095
1096     if (Attrs.hasAttribute(Idx, Attribute::InAlloca)) {
1097       Assert(Idx == FT->getNumParams(), "inalloca isn't on the last parameter!",
1098              V);
1099     }
1100   }
1101
1102   if (!Attrs.hasAttributes(AttributeSet::FunctionIndex))
1103     return;
1104
1105   VerifyAttributeTypes(Attrs, AttributeSet::FunctionIndex, true, V);
1106
1107   Assert(
1108       !(Attrs.hasAttribute(AttributeSet::FunctionIndex, Attribute::ReadNone) &&
1109         Attrs.hasAttribute(AttributeSet::FunctionIndex, Attribute::ReadOnly)),
1110       "Attributes 'readnone and readonly' are incompatible!", V);
1111
1112   Assert(
1113       !(Attrs.hasAttribute(AttributeSet::FunctionIndex, Attribute::NoInline) &&
1114         Attrs.hasAttribute(AttributeSet::FunctionIndex,
1115                            Attribute::AlwaysInline)),
1116       "Attributes 'noinline and alwaysinline' are incompatible!", V);
1117
1118   if (Attrs.hasAttribute(AttributeSet::FunctionIndex,
1119                          Attribute::OptimizeNone)) {
1120     Assert(Attrs.hasAttribute(AttributeSet::FunctionIndex, Attribute::NoInline),
1121            "Attribute 'optnone' requires 'noinline'!", V);
1122
1123     Assert(!Attrs.hasAttribute(AttributeSet::FunctionIndex,
1124                                Attribute::OptimizeForSize),
1125            "Attributes 'optsize and optnone' are incompatible!", V);
1126
1127     Assert(!Attrs.hasAttribute(AttributeSet::FunctionIndex, Attribute::MinSize),
1128            "Attributes 'minsize and optnone' are incompatible!", V);
1129   }
1130
1131   if (Attrs.hasAttribute(AttributeSet::FunctionIndex,
1132                          Attribute::JumpTable)) {
1133     const GlobalValue *GV = cast<GlobalValue>(V);
1134     Assert(GV->hasUnnamedAddr(),
1135            "Attribute 'jumptable' requires 'unnamed_addr'", V);
1136   }
1137 }
1138
1139 void Verifier::VerifyConstantExprBitcastType(const ConstantExpr *CE) {
1140   if (CE->getOpcode() != Instruction::BitCast)
1141     return;
1142
1143   Assert(CastInst::castIsValid(Instruction::BitCast, CE->getOperand(0),
1144                                CE->getType()),
1145          "Invalid bitcast", CE);
1146 }
1147
1148 bool Verifier::VerifyAttributeCount(AttributeSet Attrs, unsigned Params) {
1149   if (Attrs.getNumSlots() == 0)
1150     return true;
1151
1152   unsigned LastSlot = Attrs.getNumSlots() - 1;
1153   unsigned LastIndex = Attrs.getSlotIndex(LastSlot);
1154   if (LastIndex <= Params
1155       || (LastIndex == AttributeSet::FunctionIndex
1156           && (LastSlot == 0 || Attrs.getSlotIndex(LastSlot - 1) <= Params)))
1157     return true;
1158
1159   return false;
1160 }
1161
1162 /// \brief Verify that statepoint intrinsic is well formed.
1163 void Verifier::VerifyStatepoint(ImmutableCallSite CS) {
1164   assert(CS.getCalledFunction() &&
1165          CS.getCalledFunction()->getIntrinsicID() ==
1166            Intrinsic::experimental_gc_statepoint);
1167
1168   const Instruction &CI = *CS.getInstruction();
1169
1170   Assert(!CS.doesNotAccessMemory() && !CS.onlyReadsMemory(),
1171          "gc.statepoint must read and write memory to preserve "
1172          "reordering restrictions required by safepoint semantics",
1173          &CI);
1174
1175   const Value *Target = CS.getArgument(0);
1176   const PointerType *PT = dyn_cast<PointerType>(Target->getType());
1177   Assert(PT && PT->getElementType()->isFunctionTy(),
1178          "gc.statepoint callee must be of function pointer type", &CI, Target);
1179   FunctionType *TargetFuncType = cast<FunctionType>(PT->getElementType());
1180
1181   const Value *NumCallArgsV = CS.getArgument(1);
1182   Assert(isa<ConstantInt>(NumCallArgsV),
1183          "gc.statepoint number of arguments to underlying call "
1184          "must be constant integer",
1185          &CI);
1186   const int NumCallArgs = cast<ConstantInt>(NumCallArgsV)->getZExtValue();
1187   Assert(NumCallArgs >= 0,
1188          "gc.statepoint number of arguments to underlying call "
1189          "must be positive",
1190          &CI);
1191   const int NumParams = (int)TargetFuncType->getNumParams();
1192   if (TargetFuncType->isVarArg()) {
1193     Assert(NumCallArgs >= NumParams,
1194            "gc.statepoint mismatch in number of vararg call args", &CI);
1195
1196     // TODO: Remove this limitation
1197     Assert(TargetFuncType->getReturnType()->isVoidTy(),
1198            "gc.statepoint doesn't support wrapping non-void "
1199            "vararg functions yet",
1200            &CI);
1201   } else
1202     Assert(NumCallArgs == NumParams,
1203            "gc.statepoint mismatch in number of call args", &CI);
1204
1205   const Value *Unused = CS.getArgument(2);
1206   Assert(isa<ConstantInt>(Unused) && cast<ConstantInt>(Unused)->isNullValue(),
1207          "gc.statepoint parameter #3 must be zero", &CI);
1208
1209   // Verify that the types of the call parameter arguments match
1210   // the type of the wrapped callee.
1211   for (int i = 0; i < NumParams; i++) {
1212     Type *ParamType = TargetFuncType->getParamType(i);
1213     Type *ArgType = CS.getArgument(3+i)->getType();
1214     Assert(ArgType == ParamType,
1215            "gc.statepoint call argument does not match wrapped "
1216            "function type",
1217            &CI);
1218   }
1219   const int EndCallArgsInx = 2+NumCallArgs;
1220   const Value *NumDeoptArgsV = CS.getArgument(EndCallArgsInx+1);
1221   Assert(isa<ConstantInt>(NumDeoptArgsV),
1222          "gc.statepoint number of deoptimization arguments "
1223          "must be constant integer",
1224          &CI);
1225   const int NumDeoptArgs = cast<ConstantInt>(NumDeoptArgsV)->getZExtValue();
1226   Assert(NumDeoptArgs >= 0, "gc.statepoint number of deoptimization arguments "
1227                             "must be positive",
1228          &CI);
1229
1230   Assert(4 + NumCallArgs + NumDeoptArgs <= (int)CS.arg_size(),
1231          "gc.statepoint too few arguments according to length fields", &CI);
1232
1233   // Check that the only uses of this gc.statepoint are gc.result or
1234   // gc.relocate calls which are tied to this statepoint and thus part
1235   // of the same statepoint sequence
1236   for (const User *U : CI.users()) {
1237     const CallInst *Call = dyn_cast<const CallInst>(U);
1238     Assert(Call, "illegal use of statepoint token", &CI, U);
1239     if (!Call) continue;
1240     Assert(isGCRelocate(Call) || isGCResult(Call),
1241            "gc.result or gc.relocate are the only value uses"
1242            "of a gc.statepoint",
1243            &CI, U);
1244     if (isGCResult(Call)) {
1245       Assert(Call->getArgOperand(0) == &CI,
1246              "gc.result connected to wrong gc.statepoint", &CI, Call);
1247     } else if (isGCRelocate(Call)) {
1248       Assert(Call->getArgOperand(0) == &CI,
1249              "gc.relocate connected to wrong gc.statepoint", &CI, Call);
1250     }
1251   }
1252
1253   // Note: It is legal for a single derived pointer to be listed multiple
1254   // times.  It's non-optimal, but it is legal.  It can also happen after
1255   // insertion if we strip a bitcast away.
1256   // Note: It is really tempting to check that each base is relocated and
1257   // that a derived pointer is never reused as a base pointer.  This turns
1258   // out to be problematic since optimizations run after safepoint insertion
1259   // can recognize equality properties that the insertion logic doesn't know
1260   // about.  See example statepoint.ll in the verifier subdirectory
1261 }
1262
1263 void Verifier::verifyFrameRecoverIndices() {
1264   for (auto &Counts : FrameEscapeInfo) {
1265     Function *F = Counts.first;
1266     unsigned EscapedObjectCount = Counts.second.first;
1267     unsigned MaxRecoveredIndex = Counts.second.second;
1268     Assert(MaxRecoveredIndex <= EscapedObjectCount,
1269            "all indices passed to llvm.framerecover must be less than the "
1270            "number of arguments passed ot llvm.frameescape in the parent "
1271            "function",
1272            F);
1273   }
1274 }
1275
1276 // visitFunction - Verify that a function is ok.
1277 //
1278 void Verifier::visitFunction(const Function &F) {
1279   // Check function arguments.
1280   FunctionType *FT = F.getFunctionType();
1281   unsigned NumArgs = F.arg_size();
1282
1283   Assert(Context == &F.getContext(),
1284          "Function context does not match Module context!", &F);
1285
1286   Assert(!F.hasCommonLinkage(), "Functions may not have common linkage", &F);
1287   Assert(FT->getNumParams() == NumArgs,
1288          "# formal arguments must match # of arguments for function type!", &F,
1289          FT);
1290   Assert(F.getReturnType()->isFirstClassType() ||
1291              F.getReturnType()->isVoidTy() || F.getReturnType()->isStructTy(),
1292          "Functions cannot return aggregate values!", &F);
1293
1294   Assert(!F.hasStructRetAttr() || F.getReturnType()->isVoidTy(),
1295          "Invalid struct return type!", &F);
1296
1297   AttributeSet Attrs = F.getAttributes();
1298
1299   Assert(VerifyAttributeCount(Attrs, FT->getNumParams()),
1300          "Attribute after last parameter!", &F);
1301
1302   // Check function attributes.
1303   VerifyFunctionAttrs(FT, Attrs, &F);
1304
1305   // On function declarations/definitions, we do not support the builtin
1306   // attribute. We do not check this in VerifyFunctionAttrs since that is
1307   // checking for Attributes that can/can not ever be on functions.
1308   Assert(!Attrs.hasAttribute(AttributeSet::FunctionIndex, Attribute::Builtin),
1309          "Attribute 'builtin' can only be applied to a callsite.", &F);
1310
1311   // Check that this function meets the restrictions on this calling convention.
1312   // Sometimes varargs is used for perfectly forwarding thunks, so some of these
1313   // restrictions can be lifted.
1314   switch (F.getCallingConv()) {
1315   default:
1316   case CallingConv::C:
1317     break;
1318   case CallingConv::Fast:
1319   case CallingConv::Cold:
1320   case CallingConv::Intel_OCL_BI:
1321   case CallingConv::PTX_Kernel:
1322   case CallingConv::PTX_Device:
1323     Assert(!F.isVarArg(), "Calling convention does not support varargs or "
1324                           "perfect forwarding!",
1325            &F);
1326     break;
1327   }
1328
1329   bool isLLVMdotName = F.getName().size() >= 5 &&
1330                        F.getName().substr(0, 5) == "llvm.";
1331
1332   // Check that the argument values match the function type for this function...
1333   unsigned i = 0;
1334   for (Function::const_arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E;
1335        ++I, ++i) {
1336     Assert(I->getType() == FT->getParamType(i),
1337            "Argument value does not match function argument type!", I,
1338            FT->getParamType(i));
1339     Assert(I->getType()->isFirstClassType(),
1340            "Function arguments must have first-class types!", I);
1341     if (!isLLVMdotName)
1342       Assert(!I->getType()->isMetadataTy(),
1343              "Function takes metadata but isn't an intrinsic", I, &F);
1344   }
1345
1346   if (F.isMaterializable()) {
1347     // Function has a body somewhere we can't see.
1348   } else if (F.isDeclaration()) {
1349     Assert(F.hasExternalLinkage() || F.hasExternalWeakLinkage(),
1350            "invalid linkage type for function declaration", &F);
1351   } else {
1352     // Verify that this function (which has a body) is not named "llvm.*".  It
1353     // is not legal to define intrinsics.
1354     Assert(!isLLVMdotName, "llvm intrinsics cannot be defined!", &F);
1355
1356     // Check the entry node
1357     const BasicBlock *Entry = &F.getEntryBlock();
1358     Assert(pred_empty(Entry),
1359            "Entry block to function must not have predecessors!", Entry);
1360
1361     // The address of the entry block cannot be taken, unless it is dead.
1362     if (Entry->hasAddressTaken()) {
1363       Assert(!BlockAddress::lookup(Entry)->isConstantUsed(),
1364              "blockaddress may not be used with the entry block!", Entry);
1365     }
1366   }
1367
1368   // If this function is actually an intrinsic, verify that it is only used in
1369   // direct call/invokes, never having its "address taken".
1370   if (F.getIntrinsicID()) {
1371     const User *U;
1372     if (F.hasAddressTaken(&U))
1373       Assert(0, "Invalid user of intrinsic instruction!", U);
1374   }
1375
1376   Assert(!F.hasDLLImportStorageClass() ||
1377              (F.isDeclaration() && F.hasExternalLinkage()) ||
1378              F.hasAvailableExternallyLinkage(),
1379          "Function is marked as dllimport, but not external.", &F);
1380 }
1381
1382 // verifyBasicBlock - Verify that a basic block is well formed...
1383 //
1384 void Verifier::visitBasicBlock(BasicBlock &BB) {
1385   InstsInThisBlock.clear();
1386
1387   // Ensure that basic blocks have terminators!
1388   Assert(BB.getTerminator(), "Basic Block does not have terminator!", &BB);
1389
1390   // Check constraints that this basic block imposes on all of the PHI nodes in
1391   // it.
1392   if (isa<PHINode>(BB.front())) {
1393     SmallVector<BasicBlock*, 8> Preds(pred_begin(&BB), pred_end(&BB));
1394     SmallVector<std::pair<BasicBlock*, Value*>, 8> Values;
1395     std::sort(Preds.begin(), Preds.end());
1396     PHINode *PN;
1397     for (BasicBlock::iterator I = BB.begin(); (PN = dyn_cast<PHINode>(I));++I) {
1398       // Ensure that PHI nodes have at least one entry!
1399       Assert(PN->getNumIncomingValues() != 0,
1400              "PHI nodes must have at least one entry.  If the block is dead, "
1401              "the PHI should be removed!",
1402              PN);
1403       Assert(PN->getNumIncomingValues() == Preds.size(),
1404              "PHINode should have one entry for each predecessor of its "
1405              "parent basic block!",
1406              PN);
1407
1408       // Get and sort all incoming values in the PHI node...
1409       Values.clear();
1410       Values.reserve(PN->getNumIncomingValues());
1411       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
1412         Values.push_back(std::make_pair(PN->getIncomingBlock(i),
1413                                         PN->getIncomingValue(i)));
1414       std::sort(Values.begin(), Values.end());
1415
1416       for (unsigned i = 0, e = Values.size(); i != e; ++i) {
1417         // Check to make sure that if there is more than one entry for a
1418         // particular basic block in this PHI node, that the incoming values are
1419         // all identical.
1420         //
1421         Assert(i == 0 || Values[i].first != Values[i - 1].first ||
1422                    Values[i].second == Values[i - 1].second,
1423                "PHI node has multiple entries for the same basic block with "
1424                "different incoming values!",
1425                PN, Values[i].first, Values[i].second, Values[i - 1].second);
1426
1427         // Check to make sure that the predecessors and PHI node entries are
1428         // matched up.
1429         Assert(Values[i].first == Preds[i],
1430                "PHI node entries do not match predecessors!", PN,
1431                Values[i].first, Preds[i]);
1432       }
1433     }
1434   }
1435
1436   // Check that all instructions have their parent pointers set up correctly.
1437   for (auto &I : BB)
1438   {
1439     Assert(I.getParent() == &BB, "Instruction has bogus parent pointer!");
1440   }
1441 }
1442
1443 void Verifier::visitTerminatorInst(TerminatorInst &I) {
1444   // Ensure that terminators only exist at the end of the basic block.
1445   Assert(&I == I.getParent()->getTerminator(),
1446          "Terminator found in the middle of a basic block!", I.getParent());
1447   visitInstruction(I);
1448 }
1449
1450 void Verifier::visitBranchInst(BranchInst &BI) {
1451   if (BI.isConditional()) {
1452     Assert(BI.getCondition()->getType()->isIntegerTy(1),
1453            "Branch condition is not 'i1' type!", &BI, BI.getCondition());
1454   }
1455   visitTerminatorInst(BI);
1456 }
1457
1458 void Verifier::visitReturnInst(ReturnInst &RI) {
1459   Function *F = RI.getParent()->getParent();
1460   unsigned N = RI.getNumOperands();
1461   if (F->getReturnType()->isVoidTy())
1462     Assert(N == 0,
1463            "Found return instr that returns non-void in Function of void "
1464            "return type!",
1465            &RI, F->getReturnType());
1466   else
1467     Assert(N == 1 && F->getReturnType() == RI.getOperand(0)->getType(),
1468            "Function return type does not match operand "
1469            "type of return inst!",
1470            &RI, F->getReturnType());
1471
1472   // Check to make sure that the return value has necessary properties for
1473   // terminators...
1474   visitTerminatorInst(RI);
1475 }
1476
1477 void Verifier::visitSwitchInst(SwitchInst &SI) {
1478   // Check to make sure that all of the constants in the switch instruction
1479   // have the same type as the switched-on value.
1480   Type *SwitchTy = SI.getCondition()->getType();
1481   SmallPtrSet<ConstantInt*, 32> Constants;
1482   for (SwitchInst::CaseIt i = SI.case_begin(), e = SI.case_end(); i != e; ++i) {
1483     Assert(i.getCaseValue()->getType() == SwitchTy,
1484            "Switch constants must all be same type as switch value!", &SI);
1485     Assert(Constants.insert(i.getCaseValue()).second,
1486            "Duplicate integer as switch case", &SI, i.getCaseValue());
1487   }
1488
1489   visitTerminatorInst(SI);
1490 }
1491
1492 void Verifier::visitIndirectBrInst(IndirectBrInst &BI) {
1493   Assert(BI.getAddress()->getType()->isPointerTy(),
1494          "Indirectbr operand must have pointer type!", &BI);
1495   for (unsigned i = 0, e = BI.getNumDestinations(); i != e; ++i)
1496     Assert(BI.getDestination(i)->getType()->isLabelTy(),
1497            "Indirectbr destinations must all have pointer type!", &BI);
1498
1499   visitTerminatorInst(BI);
1500 }
1501
1502 void Verifier::visitSelectInst(SelectInst &SI) {
1503   Assert(!SelectInst::areInvalidOperands(SI.getOperand(0), SI.getOperand(1),
1504                                          SI.getOperand(2)),
1505          "Invalid operands for select instruction!", &SI);
1506
1507   Assert(SI.getTrueValue()->getType() == SI.getType(),
1508          "Select values must have same type as select instruction!", &SI);
1509   visitInstruction(SI);
1510 }
1511
1512 /// visitUserOp1 - User defined operators shouldn't live beyond the lifetime of
1513 /// a pass, if any exist, it's an error.
1514 ///
1515 void Verifier::visitUserOp1(Instruction &I) {
1516   Assert(0, "User-defined operators should not live outside of a pass!", &I);
1517 }
1518
1519 void Verifier::visitTruncInst(TruncInst &I) {
1520   // Get the source and destination types
1521   Type *SrcTy = I.getOperand(0)->getType();
1522   Type *DestTy = I.getType();
1523
1524   // Get the size of the types in bits, we'll need this later
1525   unsigned SrcBitSize = SrcTy->getScalarSizeInBits();
1526   unsigned DestBitSize = DestTy->getScalarSizeInBits();
1527
1528   Assert(SrcTy->isIntOrIntVectorTy(), "Trunc only operates on integer", &I);
1529   Assert(DestTy->isIntOrIntVectorTy(), "Trunc only produces integer", &I);
1530   Assert(SrcTy->isVectorTy() == DestTy->isVectorTy(),
1531          "trunc source and destination must both be a vector or neither", &I);
1532   Assert(SrcBitSize > DestBitSize, "DestTy too big for Trunc", &I);
1533
1534   visitInstruction(I);
1535 }
1536
1537 void Verifier::visitZExtInst(ZExtInst &I) {
1538   // Get the source and destination types
1539   Type *SrcTy = I.getOperand(0)->getType();
1540   Type *DestTy = I.getType();
1541
1542   // Get the size of the types in bits, we'll need this later
1543   Assert(SrcTy->isIntOrIntVectorTy(), "ZExt only operates on integer", &I);
1544   Assert(DestTy->isIntOrIntVectorTy(), "ZExt only produces an integer", &I);
1545   Assert(SrcTy->isVectorTy() == DestTy->isVectorTy(),
1546          "zext source and destination must both be a vector or neither", &I);
1547   unsigned SrcBitSize = SrcTy->getScalarSizeInBits();
1548   unsigned DestBitSize = DestTy->getScalarSizeInBits();
1549
1550   Assert(SrcBitSize < DestBitSize, "Type too small for ZExt", &I);
1551
1552   visitInstruction(I);
1553 }
1554
1555 void Verifier::visitSExtInst(SExtInst &I) {
1556   // Get the source and destination types
1557   Type *SrcTy = I.getOperand(0)->getType();
1558   Type *DestTy = I.getType();
1559
1560   // Get the size of the types in bits, we'll need this later
1561   unsigned SrcBitSize = SrcTy->getScalarSizeInBits();
1562   unsigned DestBitSize = DestTy->getScalarSizeInBits();
1563
1564   Assert(SrcTy->isIntOrIntVectorTy(), "SExt only operates on integer", &I);
1565   Assert(DestTy->isIntOrIntVectorTy(), "SExt only produces an integer", &I);
1566   Assert(SrcTy->isVectorTy() == DestTy->isVectorTy(),
1567          "sext source and destination must both be a vector or neither", &I);
1568   Assert(SrcBitSize < DestBitSize, "Type too small for SExt", &I);
1569
1570   visitInstruction(I);
1571 }
1572
1573 void Verifier::visitFPTruncInst(FPTruncInst &I) {
1574   // Get the source and destination types
1575   Type *SrcTy = I.getOperand(0)->getType();
1576   Type *DestTy = I.getType();
1577   // Get the size of the types in bits, we'll need this later
1578   unsigned SrcBitSize = SrcTy->getScalarSizeInBits();
1579   unsigned DestBitSize = DestTy->getScalarSizeInBits();
1580
1581   Assert(SrcTy->isFPOrFPVectorTy(), "FPTrunc only operates on FP", &I);
1582   Assert(DestTy->isFPOrFPVectorTy(), "FPTrunc only produces an FP", &I);
1583   Assert(SrcTy->isVectorTy() == DestTy->isVectorTy(),
1584          "fptrunc source and destination must both be a vector or neither", &I);
1585   Assert(SrcBitSize > DestBitSize, "DestTy too big for FPTrunc", &I);
1586
1587   visitInstruction(I);
1588 }
1589
1590 void Verifier::visitFPExtInst(FPExtInst &I) {
1591   // Get the source and destination types
1592   Type *SrcTy = I.getOperand(0)->getType();
1593   Type *DestTy = I.getType();
1594
1595   // Get the size of the types in bits, we'll need this later
1596   unsigned SrcBitSize = SrcTy->getScalarSizeInBits();
1597   unsigned DestBitSize = DestTy->getScalarSizeInBits();
1598
1599   Assert(SrcTy->isFPOrFPVectorTy(), "FPExt only operates on FP", &I);
1600   Assert(DestTy->isFPOrFPVectorTy(), "FPExt only produces an FP", &I);
1601   Assert(SrcTy->isVectorTy() == DestTy->isVectorTy(),
1602          "fpext source and destination must both be a vector or neither", &I);
1603   Assert(SrcBitSize < DestBitSize, "DestTy too small for FPExt", &I);
1604
1605   visitInstruction(I);
1606 }
1607
1608 void Verifier::visitUIToFPInst(UIToFPInst &I) {
1609   // Get the source and destination types
1610   Type *SrcTy = I.getOperand(0)->getType();
1611   Type *DestTy = I.getType();
1612
1613   bool SrcVec = SrcTy->isVectorTy();
1614   bool DstVec = DestTy->isVectorTy();
1615
1616   Assert(SrcVec == DstVec,
1617          "UIToFP source and dest must both be vector or scalar", &I);
1618   Assert(SrcTy->isIntOrIntVectorTy(),
1619          "UIToFP source must be integer or integer vector", &I);
1620   Assert(DestTy->isFPOrFPVectorTy(), "UIToFP result must be FP or FP vector",
1621          &I);
1622
1623   if (SrcVec && DstVec)
1624     Assert(cast<VectorType>(SrcTy)->getNumElements() ==
1625                cast<VectorType>(DestTy)->getNumElements(),
1626            "UIToFP source and dest vector length mismatch", &I);
1627
1628   visitInstruction(I);
1629 }
1630
1631 void Verifier::visitSIToFPInst(SIToFPInst &I) {
1632   // Get the source and destination types
1633   Type *SrcTy = I.getOperand(0)->getType();
1634   Type *DestTy = I.getType();
1635
1636   bool SrcVec = SrcTy->isVectorTy();
1637   bool DstVec = DestTy->isVectorTy();
1638
1639   Assert(SrcVec == DstVec,
1640          "SIToFP source and dest must both be vector or scalar", &I);
1641   Assert(SrcTy->isIntOrIntVectorTy(),
1642          "SIToFP source must be integer or integer vector", &I);
1643   Assert(DestTy->isFPOrFPVectorTy(), "SIToFP result must be FP or FP vector",
1644          &I);
1645
1646   if (SrcVec && DstVec)
1647     Assert(cast<VectorType>(SrcTy)->getNumElements() ==
1648                cast<VectorType>(DestTy)->getNumElements(),
1649            "SIToFP source and dest vector length mismatch", &I);
1650
1651   visitInstruction(I);
1652 }
1653
1654 void Verifier::visitFPToUIInst(FPToUIInst &I) {
1655   // Get the source and destination types
1656   Type *SrcTy = I.getOperand(0)->getType();
1657   Type *DestTy = I.getType();
1658
1659   bool SrcVec = SrcTy->isVectorTy();
1660   bool DstVec = DestTy->isVectorTy();
1661
1662   Assert(SrcVec == DstVec,
1663          "FPToUI source and dest must both be vector or scalar", &I);
1664   Assert(SrcTy->isFPOrFPVectorTy(), "FPToUI source must be FP or FP vector",
1665          &I);
1666   Assert(DestTy->isIntOrIntVectorTy(),
1667          "FPToUI result must be integer or integer vector", &I);
1668
1669   if (SrcVec && DstVec)
1670     Assert(cast<VectorType>(SrcTy)->getNumElements() ==
1671                cast<VectorType>(DestTy)->getNumElements(),
1672            "FPToUI source and dest vector length mismatch", &I);
1673
1674   visitInstruction(I);
1675 }
1676
1677 void Verifier::visitFPToSIInst(FPToSIInst &I) {
1678   // Get the source and destination types
1679   Type *SrcTy = I.getOperand(0)->getType();
1680   Type *DestTy = I.getType();
1681
1682   bool SrcVec = SrcTy->isVectorTy();
1683   bool DstVec = DestTy->isVectorTy();
1684
1685   Assert(SrcVec == DstVec,
1686          "FPToSI source and dest must both be vector or scalar", &I);
1687   Assert(SrcTy->isFPOrFPVectorTy(), "FPToSI source must be FP or FP vector",
1688          &I);
1689   Assert(DestTy->isIntOrIntVectorTy(),
1690          "FPToSI result must be integer or integer vector", &I);
1691
1692   if (SrcVec && DstVec)
1693     Assert(cast<VectorType>(SrcTy)->getNumElements() ==
1694                cast<VectorType>(DestTy)->getNumElements(),
1695            "FPToSI source and dest vector length mismatch", &I);
1696
1697   visitInstruction(I);
1698 }
1699
1700 void Verifier::visitPtrToIntInst(PtrToIntInst &I) {
1701   // Get the source and destination types
1702   Type *SrcTy = I.getOperand(0)->getType();
1703   Type *DestTy = I.getType();
1704
1705   Assert(SrcTy->getScalarType()->isPointerTy(),
1706          "PtrToInt source must be pointer", &I);
1707   Assert(DestTy->getScalarType()->isIntegerTy(),
1708          "PtrToInt result must be integral", &I);
1709   Assert(SrcTy->isVectorTy() == DestTy->isVectorTy(), "PtrToInt type mismatch",
1710          &I);
1711
1712   if (SrcTy->isVectorTy()) {
1713     VectorType *VSrc = dyn_cast<VectorType>(SrcTy);
1714     VectorType *VDest = dyn_cast<VectorType>(DestTy);
1715     Assert(VSrc->getNumElements() == VDest->getNumElements(),
1716            "PtrToInt Vector width mismatch", &I);
1717   }
1718
1719   visitInstruction(I);
1720 }
1721
1722 void Verifier::visitIntToPtrInst(IntToPtrInst &I) {
1723   // Get the source and destination types
1724   Type *SrcTy = I.getOperand(0)->getType();
1725   Type *DestTy = I.getType();
1726
1727   Assert(SrcTy->getScalarType()->isIntegerTy(),
1728          "IntToPtr source must be an integral", &I);
1729   Assert(DestTy->getScalarType()->isPointerTy(),
1730          "IntToPtr result must be a pointer", &I);
1731   Assert(SrcTy->isVectorTy() == DestTy->isVectorTy(), "IntToPtr type mismatch",
1732          &I);
1733   if (SrcTy->isVectorTy()) {
1734     VectorType *VSrc = dyn_cast<VectorType>(SrcTy);
1735     VectorType *VDest = dyn_cast<VectorType>(DestTy);
1736     Assert(VSrc->getNumElements() == VDest->getNumElements(),
1737            "IntToPtr Vector width mismatch", &I);
1738   }
1739   visitInstruction(I);
1740 }
1741
1742 void Verifier::visitBitCastInst(BitCastInst &I) {
1743   Assert(
1744       CastInst::castIsValid(Instruction::BitCast, I.getOperand(0), I.getType()),
1745       "Invalid bitcast", &I);
1746   visitInstruction(I);
1747 }
1748
1749 void Verifier::visitAddrSpaceCastInst(AddrSpaceCastInst &I) {
1750   Type *SrcTy = I.getOperand(0)->getType();
1751   Type *DestTy = I.getType();
1752
1753   Assert(SrcTy->isPtrOrPtrVectorTy(), "AddrSpaceCast source must be a pointer",
1754          &I);
1755   Assert(DestTy->isPtrOrPtrVectorTy(), "AddrSpaceCast result must be a pointer",
1756          &I);
1757   Assert(SrcTy->getPointerAddressSpace() != DestTy->getPointerAddressSpace(),
1758          "AddrSpaceCast must be between different address spaces", &I);
1759   if (SrcTy->isVectorTy())
1760     Assert(SrcTy->getVectorNumElements() == DestTy->getVectorNumElements(),
1761            "AddrSpaceCast vector pointer number of elements mismatch", &I);
1762   visitInstruction(I);
1763 }
1764
1765 /// visitPHINode - Ensure that a PHI node is well formed.
1766 ///
1767 void Verifier::visitPHINode(PHINode &PN) {
1768   // Ensure that the PHI nodes are all grouped together at the top of the block.
1769   // This can be tested by checking whether the instruction before this is
1770   // either nonexistent (because this is begin()) or is a PHI node.  If not,
1771   // then there is some other instruction before a PHI.
1772   Assert(&PN == &PN.getParent()->front() ||
1773              isa<PHINode>(--BasicBlock::iterator(&PN)),
1774          "PHI nodes not grouped at top of basic block!", &PN, PN.getParent());
1775
1776   // Check that all of the values of the PHI node have the same type as the
1777   // result, and that the incoming blocks are really basic blocks.
1778   for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
1779     Assert(PN.getType() == PN.getIncomingValue(i)->getType(),
1780            "PHI node operands are not the same type as the result!", &PN);
1781   }
1782
1783   // All other PHI node constraints are checked in the visitBasicBlock method.
1784
1785   visitInstruction(PN);
1786 }
1787
1788 void Verifier::VerifyCallSite(CallSite CS) {
1789   Instruction *I = CS.getInstruction();
1790
1791   Assert(CS.getCalledValue()->getType()->isPointerTy(),
1792          "Called function must be a pointer!", I);
1793   PointerType *FPTy = cast<PointerType>(CS.getCalledValue()->getType());
1794
1795   Assert(FPTy->getElementType()->isFunctionTy(),
1796          "Called function is not pointer to function type!", I);
1797   FunctionType *FTy = cast<FunctionType>(FPTy->getElementType());
1798
1799   // Verify that the correct number of arguments are being passed
1800   if (FTy->isVarArg())
1801     Assert(CS.arg_size() >= FTy->getNumParams(),
1802            "Called function requires more parameters than were provided!", I);
1803   else
1804     Assert(CS.arg_size() == FTy->getNumParams(),
1805            "Incorrect number of arguments passed to called function!", I);
1806
1807   // Verify that all arguments to the call match the function type.
1808   for (unsigned i = 0, e = FTy->getNumParams(); i != e; ++i)
1809     Assert(CS.getArgument(i)->getType() == FTy->getParamType(i),
1810            "Call parameter type does not match function signature!",
1811            CS.getArgument(i), FTy->getParamType(i), I);
1812
1813   AttributeSet Attrs = CS.getAttributes();
1814
1815   Assert(VerifyAttributeCount(Attrs, CS.arg_size()),
1816          "Attribute after last parameter!", I);
1817
1818   // Verify call attributes.
1819   VerifyFunctionAttrs(FTy, Attrs, I);
1820
1821   // Conservatively check the inalloca argument.
1822   // We have a bug if we can find that there is an underlying alloca without
1823   // inalloca.
1824   if (CS.hasInAllocaArgument()) {
1825     Value *InAllocaArg = CS.getArgument(FTy->getNumParams() - 1);
1826     if (auto AI = dyn_cast<AllocaInst>(InAllocaArg->stripInBoundsOffsets()))
1827       Assert(AI->isUsedWithInAlloca(),
1828              "inalloca argument for call has mismatched alloca", AI, I);
1829   }
1830
1831   if (FTy->isVarArg()) {
1832     // FIXME? is 'nest' even legal here?
1833     bool SawNest = false;
1834     bool SawReturned = false;
1835
1836     for (unsigned Idx = 1; Idx < 1 + FTy->getNumParams(); ++Idx) {
1837       if (Attrs.hasAttribute(Idx, Attribute::Nest))
1838         SawNest = true;
1839       if (Attrs.hasAttribute(Idx, Attribute::Returned))
1840         SawReturned = true;
1841     }
1842
1843     // Check attributes on the varargs part.
1844     for (unsigned Idx = 1 + FTy->getNumParams(); Idx <= CS.arg_size(); ++Idx) {
1845       Type *Ty = CS.getArgument(Idx-1)->getType();
1846       VerifyParameterAttrs(Attrs, Idx, Ty, false, I);
1847
1848       if (Attrs.hasAttribute(Idx, Attribute::Nest)) {
1849         Assert(!SawNest, "More than one parameter has attribute nest!", I);
1850         SawNest = true;
1851       }
1852
1853       if (Attrs.hasAttribute(Idx, Attribute::Returned)) {
1854         Assert(!SawReturned, "More than one parameter has attribute returned!",
1855                I);
1856         Assert(Ty->canLosslesslyBitCastTo(FTy->getReturnType()),
1857                "Incompatible argument and return types for 'returned' "
1858                "attribute",
1859                I);
1860         SawReturned = true;
1861       }
1862
1863       Assert(!Attrs.hasAttribute(Idx, Attribute::StructRet),
1864              "Attribute 'sret' cannot be used for vararg call arguments!", I);
1865
1866       if (Attrs.hasAttribute(Idx, Attribute::InAlloca))
1867         Assert(Idx == CS.arg_size(), "inalloca isn't on the last argument!", I);
1868     }
1869   }
1870
1871   // Verify that there's no metadata unless it's a direct call to an intrinsic.
1872   if (CS.getCalledFunction() == nullptr ||
1873       !CS.getCalledFunction()->getName().startswith("llvm.")) {
1874     for (FunctionType::param_iterator PI = FTy->param_begin(),
1875            PE = FTy->param_end(); PI != PE; ++PI)
1876       Assert(!(*PI)->isMetadataTy(),
1877              "Function has metadata parameter but isn't an intrinsic", I);
1878   }
1879
1880   visitInstruction(*I);
1881 }
1882
1883 /// Two types are "congruent" if they are identical, or if they are both pointer
1884 /// types with different pointee types and the same address space.
1885 static bool isTypeCongruent(Type *L, Type *R) {
1886   if (L == R)
1887     return true;
1888   PointerType *PL = dyn_cast<PointerType>(L);
1889   PointerType *PR = dyn_cast<PointerType>(R);
1890   if (!PL || !PR)
1891     return false;
1892   return PL->getAddressSpace() == PR->getAddressSpace();
1893 }
1894
1895 static AttrBuilder getParameterABIAttributes(int I, AttributeSet Attrs) {
1896   static const Attribute::AttrKind ABIAttrs[] = {
1897       Attribute::StructRet, Attribute::ByVal, Attribute::InAlloca,
1898       Attribute::InReg, Attribute::Returned};
1899   AttrBuilder Copy;
1900   for (auto AK : ABIAttrs) {
1901     if (Attrs.hasAttribute(I + 1, AK))
1902       Copy.addAttribute(AK);
1903   }
1904   if (Attrs.hasAttribute(I + 1, Attribute::Alignment))
1905     Copy.addAlignmentAttr(Attrs.getParamAlignment(I + 1));
1906   return Copy;
1907 }
1908
1909 void Verifier::verifyMustTailCall(CallInst &CI) {
1910   Assert(!CI.isInlineAsm(), "cannot use musttail call with inline asm", &CI);
1911
1912   // - The caller and callee prototypes must match.  Pointer types of
1913   //   parameters or return types may differ in pointee type, but not
1914   //   address space.
1915   Function *F = CI.getParent()->getParent();
1916   auto GetFnTy = [](Value *V) {
1917     return cast<FunctionType>(
1918         cast<PointerType>(V->getType())->getElementType());
1919   };
1920   FunctionType *CallerTy = GetFnTy(F);
1921   FunctionType *CalleeTy = GetFnTy(CI.getCalledValue());
1922   Assert(CallerTy->getNumParams() == CalleeTy->getNumParams(),
1923          "cannot guarantee tail call due to mismatched parameter counts", &CI);
1924   Assert(CallerTy->isVarArg() == CalleeTy->isVarArg(),
1925          "cannot guarantee tail call due to mismatched varargs", &CI);
1926   Assert(isTypeCongruent(CallerTy->getReturnType(), CalleeTy->getReturnType()),
1927          "cannot guarantee tail call due to mismatched return types", &CI);
1928   for (int I = 0, E = CallerTy->getNumParams(); I != E; ++I) {
1929     Assert(
1930         isTypeCongruent(CallerTy->getParamType(I), CalleeTy->getParamType(I)),
1931         "cannot guarantee tail call due to mismatched parameter types", &CI);
1932   }
1933
1934   // - The calling conventions of the caller and callee must match.
1935   Assert(F->getCallingConv() == CI.getCallingConv(),
1936          "cannot guarantee tail call due to mismatched calling conv", &CI);
1937
1938   // - All ABI-impacting function attributes, such as sret, byval, inreg,
1939   //   returned, and inalloca, must match.
1940   AttributeSet CallerAttrs = F->getAttributes();
1941   AttributeSet CalleeAttrs = CI.getAttributes();
1942   for (int I = 0, E = CallerTy->getNumParams(); I != E; ++I) {
1943     AttrBuilder CallerABIAttrs = getParameterABIAttributes(I, CallerAttrs);
1944     AttrBuilder CalleeABIAttrs = getParameterABIAttributes(I, CalleeAttrs);
1945     Assert(CallerABIAttrs == CalleeABIAttrs,
1946            "cannot guarantee tail call due to mismatched ABI impacting "
1947            "function attributes",
1948            &CI, CI.getOperand(I));
1949   }
1950
1951   // - The call must immediately precede a :ref:`ret <i_ret>` instruction,
1952   //   or a pointer bitcast followed by a ret instruction.
1953   // - The ret instruction must return the (possibly bitcasted) value
1954   //   produced by the call or void.
1955   Value *RetVal = &CI;
1956   Instruction *Next = CI.getNextNode();
1957
1958   // Handle the optional bitcast.
1959   if (BitCastInst *BI = dyn_cast_or_null<BitCastInst>(Next)) {
1960     Assert(BI->getOperand(0) == RetVal,
1961            "bitcast following musttail call must use the call", BI);
1962     RetVal = BI;
1963     Next = BI->getNextNode();
1964   }
1965
1966   // Check the return.
1967   ReturnInst *Ret = dyn_cast_or_null<ReturnInst>(Next);
1968   Assert(Ret, "musttail call must be precede a ret with an optional bitcast",
1969          &CI);
1970   Assert(!Ret->getReturnValue() || Ret->getReturnValue() == RetVal,
1971          "musttail call result must be returned", Ret);
1972 }
1973
1974 void Verifier::visitCallInst(CallInst &CI) {
1975   VerifyCallSite(&CI);
1976
1977   if (CI.isMustTailCall())
1978     verifyMustTailCall(CI);
1979
1980   if (Function *F = CI.getCalledFunction())
1981     if (Intrinsic::ID ID = (Intrinsic::ID)F->getIntrinsicID())
1982       visitIntrinsicFunctionCall(ID, CI);
1983 }
1984
1985 void Verifier::visitInvokeInst(InvokeInst &II) {
1986   VerifyCallSite(&II);
1987
1988   // Verify that there is a landingpad instruction as the first non-PHI
1989   // instruction of the 'unwind' destination.
1990   Assert(II.getUnwindDest()->isLandingPad(),
1991          "The unwind destination does not have a landingpad instruction!", &II);
1992
1993   if (Function *F = II.getCalledFunction())
1994     // TODO: Ideally we should use visitIntrinsicFunction here. But it uses
1995     //       CallInst as an input parameter. It not woth updating this whole
1996     //       function only to support statepoint verification.
1997     if (F->getIntrinsicID() == Intrinsic::experimental_gc_statepoint)
1998       VerifyStatepoint(ImmutableCallSite(&II));
1999
2000   visitTerminatorInst(II);
2001 }
2002
2003 /// visitBinaryOperator - Check that both arguments to the binary operator are
2004 /// of the same type!
2005 ///
2006 void Verifier::visitBinaryOperator(BinaryOperator &B) {
2007   Assert(B.getOperand(0)->getType() == B.getOperand(1)->getType(),
2008          "Both operands to a binary operator are not of the same type!", &B);
2009
2010   switch (B.getOpcode()) {
2011   // Check that integer arithmetic operators are only used with
2012   // integral operands.
2013   case Instruction::Add:
2014   case Instruction::Sub:
2015   case Instruction::Mul:
2016   case Instruction::SDiv:
2017   case Instruction::UDiv:
2018   case Instruction::SRem:
2019   case Instruction::URem:
2020     Assert(B.getType()->isIntOrIntVectorTy(),
2021            "Integer arithmetic operators only work with integral types!", &B);
2022     Assert(B.getType() == B.getOperand(0)->getType(),
2023            "Integer arithmetic operators must have same type "
2024            "for operands and result!",
2025            &B);
2026     break;
2027   // Check that floating-point arithmetic operators are only used with
2028   // floating-point operands.
2029   case Instruction::FAdd:
2030   case Instruction::FSub:
2031   case Instruction::FMul:
2032   case Instruction::FDiv:
2033   case Instruction::FRem:
2034     Assert(B.getType()->isFPOrFPVectorTy(),
2035            "Floating-point arithmetic operators only work with "
2036            "floating-point types!",
2037            &B);
2038     Assert(B.getType() == B.getOperand(0)->getType(),
2039            "Floating-point arithmetic operators must have same type "
2040            "for operands and result!",
2041            &B);
2042     break;
2043   // Check that logical operators are only used with integral operands.
2044   case Instruction::And:
2045   case Instruction::Or:
2046   case Instruction::Xor:
2047     Assert(B.getType()->isIntOrIntVectorTy(),
2048            "Logical operators only work with integral types!", &B);
2049     Assert(B.getType() == B.getOperand(0)->getType(),
2050            "Logical operators must have same type for operands and result!",
2051            &B);
2052     break;
2053   case Instruction::Shl:
2054   case Instruction::LShr:
2055   case Instruction::AShr:
2056     Assert(B.getType()->isIntOrIntVectorTy(),
2057            "Shifts only work with integral types!", &B);
2058     Assert(B.getType() == B.getOperand(0)->getType(),
2059            "Shift return type must be same as operands!", &B);
2060     break;
2061   default:
2062     llvm_unreachable("Unknown BinaryOperator opcode!");
2063   }
2064
2065   visitInstruction(B);
2066 }
2067
2068 void Verifier::visitICmpInst(ICmpInst &IC) {
2069   // Check that the operands are the same type
2070   Type *Op0Ty = IC.getOperand(0)->getType();
2071   Type *Op1Ty = IC.getOperand(1)->getType();
2072   Assert(Op0Ty == Op1Ty,
2073          "Both operands to ICmp instruction are not of the same type!", &IC);
2074   // Check that the operands are the right type
2075   Assert(Op0Ty->isIntOrIntVectorTy() || Op0Ty->getScalarType()->isPointerTy(),
2076          "Invalid operand types for ICmp instruction", &IC);
2077   // Check that the predicate is valid.
2078   Assert(IC.getPredicate() >= CmpInst::FIRST_ICMP_PREDICATE &&
2079              IC.getPredicate() <= CmpInst::LAST_ICMP_PREDICATE,
2080          "Invalid predicate in ICmp instruction!", &IC);
2081
2082   visitInstruction(IC);
2083 }
2084
2085 void Verifier::visitFCmpInst(FCmpInst &FC) {
2086   // Check that the operands are the same type
2087   Type *Op0Ty = FC.getOperand(0)->getType();
2088   Type *Op1Ty = FC.getOperand(1)->getType();
2089   Assert(Op0Ty == Op1Ty,
2090          "Both operands to FCmp instruction are not of the same type!", &FC);
2091   // Check that the operands are the right type
2092   Assert(Op0Ty->isFPOrFPVectorTy(),
2093          "Invalid operand types for FCmp instruction", &FC);
2094   // Check that the predicate is valid.
2095   Assert(FC.getPredicate() >= CmpInst::FIRST_FCMP_PREDICATE &&
2096              FC.getPredicate() <= CmpInst::LAST_FCMP_PREDICATE,
2097          "Invalid predicate in FCmp instruction!", &FC);
2098
2099   visitInstruction(FC);
2100 }
2101
2102 void Verifier::visitExtractElementInst(ExtractElementInst &EI) {
2103   Assert(
2104       ExtractElementInst::isValidOperands(EI.getOperand(0), EI.getOperand(1)),
2105       "Invalid extractelement operands!", &EI);
2106   visitInstruction(EI);
2107 }
2108
2109 void Verifier::visitInsertElementInst(InsertElementInst &IE) {
2110   Assert(InsertElementInst::isValidOperands(IE.getOperand(0), IE.getOperand(1),
2111                                             IE.getOperand(2)),
2112          "Invalid insertelement operands!", &IE);
2113   visitInstruction(IE);
2114 }
2115
2116 void Verifier::visitShuffleVectorInst(ShuffleVectorInst &SV) {
2117   Assert(ShuffleVectorInst::isValidOperands(SV.getOperand(0), SV.getOperand(1),
2118                                             SV.getOperand(2)),
2119          "Invalid shufflevector operands!", &SV);
2120   visitInstruction(SV);
2121 }
2122
2123 void Verifier::visitGetElementPtrInst(GetElementPtrInst &GEP) {
2124   Type *TargetTy = GEP.getPointerOperandType()->getScalarType();
2125
2126   Assert(isa<PointerType>(TargetTy),
2127          "GEP base pointer is not a vector or a vector of pointers", &GEP);
2128   Assert(cast<PointerType>(TargetTy)->getElementType()->isSized(),
2129          "GEP into unsized type!", &GEP);
2130   Assert(GEP.getPointerOperandType()->isVectorTy() ==
2131              GEP.getType()->isVectorTy(),
2132          "Vector GEP must return a vector value", &GEP);
2133
2134   SmallVector<Value*, 16> Idxs(GEP.idx_begin(), GEP.idx_end());
2135   Type *ElTy =
2136     GetElementPtrInst::getIndexedType(GEP.getPointerOperandType(), Idxs);
2137   Assert(ElTy, "Invalid indices for GEP pointer type!", &GEP);
2138
2139   Assert(GEP.getType()->getScalarType()->isPointerTy() &&
2140              cast<PointerType>(GEP.getType()->getScalarType())
2141                      ->getElementType() == ElTy,
2142          "GEP is not of right type for indices!", &GEP, ElTy);
2143
2144   if (GEP.getPointerOperandType()->isVectorTy()) {
2145     // Additional checks for vector GEPs.
2146     unsigned GepWidth = GEP.getPointerOperandType()->getVectorNumElements();
2147     Assert(GepWidth == GEP.getType()->getVectorNumElements(),
2148            "Vector GEP result width doesn't match operand's", &GEP);
2149     for (unsigned i = 0, e = Idxs.size(); i != e; ++i) {
2150       Type *IndexTy = Idxs[i]->getType();
2151       Assert(IndexTy->isVectorTy(), "Vector GEP must have vector indices!",
2152              &GEP);
2153       unsigned IndexWidth = IndexTy->getVectorNumElements();
2154       Assert(IndexWidth == GepWidth, "Invalid GEP index vector width", &GEP);
2155     }
2156   }
2157   visitInstruction(GEP);
2158 }
2159
2160 static bool isContiguous(const ConstantRange &A, const ConstantRange &B) {
2161   return A.getUpper() == B.getLower() || A.getLower() == B.getUpper();
2162 }
2163
2164 void Verifier::visitRangeMetadata(Instruction& I,
2165                                   MDNode* Range, Type* Ty) {
2166   assert(Range &&
2167          Range == I.getMetadata(LLVMContext::MD_range) &&
2168          "precondition violation");
2169
2170   unsigned NumOperands = Range->getNumOperands();
2171   Assert(NumOperands % 2 == 0, "Unfinished range!", Range);
2172   unsigned NumRanges = NumOperands / 2;
2173   Assert(NumRanges >= 1, "It should have at least one range!", Range);
2174
2175   ConstantRange LastRange(1); // Dummy initial value
2176   for (unsigned i = 0; i < NumRanges; ++i) {
2177     ConstantInt *Low =
2178         mdconst::dyn_extract<ConstantInt>(Range->getOperand(2 * i));
2179     Assert(Low, "The lower limit must be an integer!", Low);
2180     ConstantInt *High =
2181         mdconst::dyn_extract<ConstantInt>(Range->getOperand(2 * i + 1));
2182     Assert(High, "The upper limit must be an integer!", High);
2183     Assert(High->getType() == Low->getType() && High->getType() == Ty,
2184            "Range types must match instruction type!", &I);
2185
2186     APInt HighV = High->getValue();
2187     APInt LowV = Low->getValue();
2188     ConstantRange CurRange(LowV, HighV);
2189     Assert(!CurRange.isEmptySet() && !CurRange.isFullSet(),
2190            "Range must not be empty!", Range);
2191     if (i != 0) {
2192       Assert(CurRange.intersectWith(LastRange).isEmptySet(),
2193              "Intervals are overlapping", Range);
2194       Assert(LowV.sgt(LastRange.getLower()), "Intervals are not in order",
2195              Range);
2196       Assert(!isContiguous(CurRange, LastRange), "Intervals are contiguous",
2197              Range);
2198     }
2199     LastRange = ConstantRange(LowV, HighV);
2200   }
2201   if (NumRanges > 2) {
2202     APInt FirstLow =
2203         mdconst::dyn_extract<ConstantInt>(Range->getOperand(0))->getValue();
2204     APInt FirstHigh =
2205         mdconst::dyn_extract<ConstantInt>(Range->getOperand(1))->getValue();
2206     ConstantRange FirstRange(FirstLow, FirstHigh);
2207     Assert(FirstRange.intersectWith(LastRange).isEmptySet(),
2208            "Intervals are overlapping", Range);
2209     Assert(!isContiguous(FirstRange, LastRange), "Intervals are contiguous",
2210            Range);
2211   }
2212 }
2213
2214 void Verifier::visitLoadInst(LoadInst &LI) {
2215   PointerType *PTy = dyn_cast<PointerType>(LI.getOperand(0)->getType());
2216   Assert(PTy, "Load operand must be a pointer.", &LI);
2217   Type *ElTy = PTy->getElementType();
2218   Assert(ElTy == LI.getType(),
2219          "Load result type does not match pointer operand type!", &LI, ElTy);
2220   Assert(LI.getAlignment() <= Value::MaximumAlignment,
2221          "huge alignment values are unsupported", &LI);
2222   if (LI.isAtomic()) {
2223     Assert(LI.getOrdering() != Release && LI.getOrdering() != AcquireRelease,
2224            "Load cannot have Release ordering", &LI);
2225     Assert(LI.getAlignment() != 0,
2226            "Atomic load must specify explicit alignment", &LI);
2227     if (!ElTy->isPointerTy()) {
2228       Assert(ElTy->isIntegerTy(), "atomic load operand must have integer type!",
2229              &LI, ElTy);
2230       unsigned Size = ElTy->getPrimitiveSizeInBits();
2231       Assert(Size >= 8 && !(Size & (Size - 1)),
2232              "atomic load operand must be power-of-two byte-sized integer", &LI,
2233              ElTy);
2234     }
2235   } else {
2236     Assert(LI.getSynchScope() == CrossThread,
2237            "Non-atomic load cannot have SynchronizationScope specified", &LI);
2238   }
2239
2240   visitInstruction(LI);
2241 }
2242
2243 void Verifier::visitStoreInst(StoreInst &SI) {
2244   PointerType *PTy = dyn_cast<PointerType>(SI.getOperand(1)->getType());
2245   Assert(PTy, "Store operand must be a pointer.", &SI);
2246   Type *ElTy = PTy->getElementType();
2247   Assert(ElTy == SI.getOperand(0)->getType(),
2248          "Stored value type does not match pointer operand type!", &SI, ElTy);
2249   Assert(SI.getAlignment() <= Value::MaximumAlignment,
2250          "huge alignment values are unsupported", &SI);
2251   if (SI.isAtomic()) {
2252     Assert(SI.getOrdering() != Acquire && SI.getOrdering() != AcquireRelease,
2253            "Store cannot have Acquire ordering", &SI);
2254     Assert(SI.getAlignment() != 0,
2255            "Atomic store must specify explicit alignment", &SI);
2256     if (!ElTy->isPointerTy()) {
2257       Assert(ElTy->isIntegerTy(),
2258              "atomic store operand must have integer type!", &SI, ElTy);
2259       unsigned Size = ElTy->getPrimitiveSizeInBits();
2260       Assert(Size >= 8 && !(Size & (Size - 1)),
2261              "atomic store operand must be power-of-two byte-sized integer",
2262              &SI, ElTy);
2263     }
2264   } else {
2265     Assert(SI.getSynchScope() == CrossThread,
2266            "Non-atomic store cannot have SynchronizationScope specified", &SI);
2267   }
2268   visitInstruction(SI);
2269 }
2270
2271 void Verifier::visitAllocaInst(AllocaInst &AI) {
2272   SmallPtrSet<const Type*, 4> Visited;
2273   PointerType *PTy = AI.getType();
2274   Assert(PTy->getAddressSpace() == 0,
2275          "Allocation instruction pointer not in the generic address space!",
2276          &AI);
2277   Assert(PTy->getElementType()->isSized(&Visited),
2278          "Cannot allocate unsized type", &AI);
2279   Assert(AI.getArraySize()->getType()->isIntegerTy(),
2280          "Alloca array size must have integer type", &AI);
2281   Assert(AI.getAlignment() <= Value::MaximumAlignment,
2282          "huge alignment values are unsupported", &AI);
2283
2284   visitInstruction(AI);
2285 }
2286
2287 void Verifier::visitAtomicCmpXchgInst(AtomicCmpXchgInst &CXI) {
2288
2289   // FIXME: more conditions???
2290   Assert(CXI.getSuccessOrdering() != NotAtomic,
2291          "cmpxchg instructions must be atomic.", &CXI);
2292   Assert(CXI.getFailureOrdering() != NotAtomic,
2293          "cmpxchg instructions must be atomic.", &CXI);
2294   Assert(CXI.getSuccessOrdering() != Unordered,
2295          "cmpxchg instructions cannot be unordered.", &CXI);
2296   Assert(CXI.getFailureOrdering() != Unordered,
2297          "cmpxchg instructions cannot be unordered.", &CXI);
2298   Assert(CXI.getSuccessOrdering() >= CXI.getFailureOrdering(),
2299          "cmpxchg instructions be at least as constrained on success as fail",
2300          &CXI);
2301   Assert(CXI.getFailureOrdering() != Release &&
2302              CXI.getFailureOrdering() != AcquireRelease,
2303          "cmpxchg failure ordering cannot include release semantics", &CXI);
2304
2305   PointerType *PTy = dyn_cast<PointerType>(CXI.getOperand(0)->getType());
2306   Assert(PTy, "First cmpxchg operand must be a pointer.", &CXI);
2307   Type *ElTy = PTy->getElementType();
2308   Assert(ElTy->isIntegerTy(), "cmpxchg operand must have integer type!", &CXI,
2309          ElTy);
2310   unsigned Size = ElTy->getPrimitiveSizeInBits();
2311   Assert(Size >= 8 && !(Size & (Size - 1)),
2312          "cmpxchg operand must be power-of-two byte-sized integer", &CXI, ElTy);
2313   Assert(ElTy == CXI.getOperand(1)->getType(),
2314          "Expected value type does not match pointer operand type!", &CXI,
2315          ElTy);
2316   Assert(ElTy == CXI.getOperand(2)->getType(),
2317          "Stored value type does not match pointer operand type!", &CXI, ElTy);
2318   visitInstruction(CXI);
2319 }
2320
2321 void Verifier::visitAtomicRMWInst(AtomicRMWInst &RMWI) {
2322   Assert(RMWI.getOrdering() != NotAtomic,
2323          "atomicrmw instructions must be atomic.", &RMWI);
2324   Assert(RMWI.getOrdering() != Unordered,
2325          "atomicrmw instructions cannot be unordered.", &RMWI);
2326   PointerType *PTy = dyn_cast<PointerType>(RMWI.getOperand(0)->getType());
2327   Assert(PTy, "First atomicrmw operand must be a pointer.", &RMWI);
2328   Type *ElTy = PTy->getElementType();
2329   Assert(ElTy->isIntegerTy(), "atomicrmw operand must have integer type!",
2330          &RMWI, ElTy);
2331   unsigned Size = ElTy->getPrimitiveSizeInBits();
2332   Assert(Size >= 8 && !(Size & (Size - 1)),
2333          "atomicrmw operand must be power-of-two byte-sized integer", &RMWI,
2334          ElTy);
2335   Assert(ElTy == RMWI.getOperand(1)->getType(),
2336          "Argument value type does not match pointer operand type!", &RMWI,
2337          ElTy);
2338   Assert(AtomicRMWInst::FIRST_BINOP <= RMWI.getOperation() &&
2339              RMWI.getOperation() <= AtomicRMWInst::LAST_BINOP,
2340          "Invalid binary operation!", &RMWI);
2341   visitInstruction(RMWI);
2342 }
2343
2344 void Verifier::visitFenceInst(FenceInst &FI) {
2345   const AtomicOrdering Ordering = FI.getOrdering();
2346   Assert(Ordering == Acquire || Ordering == Release ||
2347              Ordering == AcquireRelease || Ordering == SequentiallyConsistent,
2348          "fence instructions may only have "
2349          "acquire, release, acq_rel, or seq_cst ordering.",
2350          &FI);
2351   visitInstruction(FI);
2352 }
2353
2354 void Verifier::visitExtractValueInst(ExtractValueInst &EVI) {
2355   Assert(ExtractValueInst::getIndexedType(EVI.getAggregateOperand()->getType(),
2356                                           EVI.getIndices()) == EVI.getType(),
2357          "Invalid ExtractValueInst operands!", &EVI);
2358
2359   visitInstruction(EVI);
2360 }
2361
2362 void Verifier::visitInsertValueInst(InsertValueInst &IVI) {
2363   Assert(ExtractValueInst::getIndexedType(IVI.getAggregateOperand()->getType(),
2364                                           IVI.getIndices()) ==
2365              IVI.getOperand(1)->getType(),
2366          "Invalid InsertValueInst operands!", &IVI);
2367
2368   visitInstruction(IVI);
2369 }
2370
2371 void Verifier::visitLandingPadInst(LandingPadInst &LPI) {
2372   BasicBlock *BB = LPI.getParent();
2373
2374   // The landingpad instruction is ill-formed if it doesn't have any clauses and
2375   // isn't a cleanup.
2376   Assert(LPI.getNumClauses() > 0 || LPI.isCleanup(),
2377          "LandingPadInst needs at least one clause or to be a cleanup.", &LPI);
2378
2379   // The landingpad instruction defines its parent as a landing pad block. The
2380   // landing pad block may be branched to only by the unwind edge of an invoke.
2381   for (pred_iterator I = pred_begin(BB), E = pred_end(BB); I != E; ++I) {
2382     const InvokeInst *II = dyn_cast<InvokeInst>((*I)->getTerminator());
2383     Assert(II && II->getUnwindDest() == BB && II->getNormalDest() != BB,
2384            "Block containing LandingPadInst must be jumped to "
2385            "only by the unwind edge of an invoke.",
2386            &LPI);
2387   }
2388
2389   // The landingpad instruction must be the first non-PHI instruction in the
2390   // block.
2391   Assert(LPI.getParent()->getLandingPadInst() == &LPI,
2392          "LandingPadInst not the first non-PHI instruction in the block.",
2393          &LPI);
2394
2395   // The personality functions for all landingpad instructions within the same
2396   // function should match.
2397   if (PersonalityFn)
2398     Assert(LPI.getPersonalityFn() == PersonalityFn,
2399            "Personality function doesn't match others in function", &LPI);
2400   PersonalityFn = LPI.getPersonalityFn();
2401
2402   // All operands must be constants.
2403   Assert(isa<Constant>(PersonalityFn), "Personality function is not constant!",
2404          &LPI);
2405   for (unsigned i = 0, e = LPI.getNumClauses(); i < e; ++i) {
2406     Constant *Clause = LPI.getClause(i);
2407     if (LPI.isCatch(i)) {
2408       Assert(isa<PointerType>(Clause->getType()),
2409              "Catch operand does not have pointer type!", &LPI);
2410     } else {
2411       Assert(LPI.isFilter(i), "Clause is neither catch nor filter!", &LPI);
2412       Assert(isa<ConstantArray>(Clause) || isa<ConstantAggregateZero>(Clause),
2413              "Filter operand is not an array of constants!", &LPI);
2414     }
2415   }
2416
2417   visitInstruction(LPI);
2418 }
2419
2420 void Verifier::verifyDominatesUse(Instruction &I, unsigned i) {
2421   Instruction *Op = cast<Instruction>(I.getOperand(i));
2422   // If the we have an invalid invoke, don't try to compute the dominance.
2423   // We already reject it in the invoke specific checks and the dominance
2424   // computation doesn't handle multiple edges.
2425   if (InvokeInst *II = dyn_cast<InvokeInst>(Op)) {
2426     if (II->getNormalDest() == II->getUnwindDest())
2427       return;
2428   }
2429
2430   const Use &U = I.getOperandUse(i);
2431   Assert(InstsInThisBlock.count(Op) || DT.dominates(Op, U),
2432          "Instruction does not dominate all uses!", Op, &I);
2433 }
2434
2435 /// verifyInstruction - Verify that an instruction is well formed.
2436 ///
2437 void Verifier::visitInstruction(Instruction &I) {
2438   BasicBlock *BB = I.getParent();
2439   Assert(BB, "Instruction not embedded in basic block!", &I);
2440
2441   if (!isa<PHINode>(I)) {   // Check that non-phi nodes are not self referential
2442     for (User *U : I.users()) {
2443       Assert(U != (User *)&I || !DT.isReachableFromEntry(BB),
2444              "Only PHI nodes may reference their own value!", &I);
2445     }
2446   }
2447
2448   // Check that void typed values don't have names
2449   Assert(!I.getType()->isVoidTy() || !I.hasName(),
2450          "Instruction has a name, but provides a void value!", &I);
2451
2452   // Check that the return value of the instruction is either void or a legal
2453   // value type.
2454   Assert(I.getType()->isVoidTy() || I.getType()->isFirstClassType(),
2455          "Instruction returns a non-scalar type!", &I);
2456
2457   // Check that the instruction doesn't produce metadata. Calls are already
2458   // checked against the callee type.
2459   Assert(!I.getType()->isMetadataTy() || isa<CallInst>(I) || isa<InvokeInst>(I),
2460          "Invalid use of metadata!", &I);
2461
2462   // Check that all uses of the instruction, if they are instructions
2463   // themselves, actually have parent basic blocks.  If the use is not an
2464   // instruction, it is an error!
2465   for (Use &U : I.uses()) {
2466     if (Instruction *Used = dyn_cast<Instruction>(U.getUser()))
2467       Assert(Used->getParent() != nullptr,
2468              "Instruction referencing"
2469              " instruction not embedded in a basic block!",
2470              &I, Used);
2471     else {
2472       CheckFailed("Use of instruction is not an instruction!", U);
2473       return;
2474     }
2475   }
2476
2477   for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) {
2478     Assert(I.getOperand(i) != nullptr, "Instruction has null operand!", &I);
2479
2480     // Check to make sure that only first-class-values are operands to
2481     // instructions.
2482     if (!I.getOperand(i)->getType()->isFirstClassType()) {
2483       Assert(0, "Instruction operands must be first-class values!", &I);
2484     }
2485
2486     if (Function *F = dyn_cast<Function>(I.getOperand(i))) {
2487       // Check to make sure that the "address of" an intrinsic function is never
2488       // taken.
2489       Assert(
2490           !F->isIntrinsic() ||
2491               i == (isa<CallInst>(I) ? e - 1 : isa<InvokeInst>(I) ? e - 3 : 0),
2492           "Cannot take the address of an intrinsic!", &I);
2493       Assert(
2494           !F->isIntrinsic() || isa<CallInst>(I) ||
2495               F->getIntrinsicID() == Intrinsic::donothing ||
2496               F->getIntrinsicID() == Intrinsic::experimental_patchpoint_void ||
2497               F->getIntrinsicID() == Intrinsic::experimental_patchpoint_i64 ||
2498               F->getIntrinsicID() == Intrinsic::experimental_gc_statepoint,
2499           "Cannot invoke an intrinsinc other than"
2500           " donothing or patchpoint",
2501           &I);
2502       Assert(F->getParent() == M, "Referencing function in another module!",
2503              &I);
2504     } else if (BasicBlock *OpBB = dyn_cast<BasicBlock>(I.getOperand(i))) {
2505       Assert(OpBB->getParent() == BB->getParent(),
2506              "Referring to a basic block in another function!", &I);
2507     } else if (Argument *OpArg = dyn_cast<Argument>(I.getOperand(i))) {
2508       Assert(OpArg->getParent() == BB->getParent(),
2509              "Referring to an argument in another function!", &I);
2510     } else if (GlobalValue *GV = dyn_cast<GlobalValue>(I.getOperand(i))) {
2511       Assert(GV->getParent() == M, "Referencing global in another module!", &I);
2512     } else if (isa<Instruction>(I.getOperand(i))) {
2513       verifyDominatesUse(I, i);
2514     } else if (isa<InlineAsm>(I.getOperand(i))) {
2515       Assert((i + 1 == e && isa<CallInst>(I)) ||
2516                  (i + 3 == e && isa<InvokeInst>(I)),
2517              "Cannot take the address of an inline asm!", &I);
2518     } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(I.getOperand(i))) {
2519       if (CE->getType()->isPtrOrPtrVectorTy()) {
2520         // If we have a ConstantExpr pointer, we need to see if it came from an
2521         // illegal bitcast (inttoptr <constant int> )
2522         SmallVector<const ConstantExpr *, 4> Stack;
2523         SmallPtrSet<const ConstantExpr *, 4> Visited;
2524         Stack.push_back(CE);
2525
2526         while (!Stack.empty()) {
2527           const ConstantExpr *V = Stack.pop_back_val();
2528           if (!Visited.insert(V).second)
2529             continue;
2530
2531           VerifyConstantExprBitcastType(V);
2532
2533           for (unsigned I = 0, N = V->getNumOperands(); I != N; ++I) {
2534             if (ConstantExpr *Op = dyn_cast<ConstantExpr>(V->getOperand(I)))
2535               Stack.push_back(Op);
2536           }
2537         }
2538       }
2539     }
2540   }
2541
2542   if (MDNode *MD = I.getMetadata(LLVMContext::MD_fpmath)) {
2543     Assert(I.getType()->isFPOrFPVectorTy(),
2544            "fpmath requires a floating point result!", &I);
2545     Assert(MD->getNumOperands() == 1, "fpmath takes one operand!", &I);
2546     if (ConstantFP *CFP0 =
2547             mdconst::dyn_extract_or_null<ConstantFP>(MD->getOperand(0))) {
2548       APFloat Accuracy = CFP0->getValueAPF();
2549       Assert(Accuracy.isFiniteNonZero() && !Accuracy.isNegative(),
2550              "fpmath accuracy not a positive number!", &I);
2551     } else {
2552       Assert(false, "invalid fpmath accuracy!", &I);
2553     }
2554   }
2555
2556   if (MDNode *Range = I.getMetadata(LLVMContext::MD_range)) {
2557     Assert(isa<LoadInst>(I) || isa<CallInst>(I) || isa<InvokeInst>(I),
2558            "Ranges are only for loads, calls and invokes!", &I);
2559     visitRangeMetadata(I, Range, I.getType());
2560   }
2561
2562   if (I.getMetadata(LLVMContext::MD_nonnull)) {
2563     Assert(I.getType()->isPointerTy(), "nonnull applies only to pointer types",
2564            &I);
2565     Assert(isa<LoadInst>(I),
2566            "nonnull applies only to load instructions, use attributes"
2567            " for calls or invokes",
2568            &I);
2569   }
2570
2571   if (MDNode *N = I.getDebugLoc().getAsMDNode()) {
2572     Assert(isa<MDLocation>(N), "invalid !dbg metadata attachment", &I, N);
2573     visitMDNode(*N);
2574   }
2575
2576   InstsInThisBlock.insert(&I);
2577 }
2578
2579 /// VerifyIntrinsicType - Verify that the specified type (which comes from an
2580 /// intrinsic argument or return value) matches the type constraints specified
2581 /// by the .td file (e.g. an "any integer" argument really is an integer).
2582 ///
2583 /// This return true on error but does not print a message.
2584 bool Verifier::VerifyIntrinsicType(Type *Ty,
2585                                    ArrayRef<Intrinsic::IITDescriptor> &Infos,
2586                                    SmallVectorImpl<Type*> &ArgTys) {
2587   using namespace Intrinsic;
2588
2589   // If we ran out of descriptors, there are too many arguments.
2590   if (Infos.empty()) return true;
2591   IITDescriptor D = Infos.front();
2592   Infos = Infos.slice(1);
2593
2594   switch (D.Kind) {
2595   case IITDescriptor::Void: return !Ty->isVoidTy();
2596   case IITDescriptor::VarArg: return true;
2597   case IITDescriptor::MMX:  return !Ty->isX86_MMXTy();
2598   case IITDescriptor::Metadata: return !Ty->isMetadataTy();
2599   case IITDescriptor::Half: return !Ty->isHalfTy();
2600   case IITDescriptor::Float: return !Ty->isFloatTy();
2601   case IITDescriptor::Double: return !Ty->isDoubleTy();
2602   case IITDescriptor::Integer: return !Ty->isIntegerTy(D.Integer_Width);
2603   case IITDescriptor::Vector: {
2604     VectorType *VT = dyn_cast<VectorType>(Ty);
2605     return !VT || VT->getNumElements() != D.Vector_Width ||
2606            VerifyIntrinsicType(VT->getElementType(), Infos, ArgTys);
2607   }
2608   case IITDescriptor::Pointer: {
2609     PointerType *PT = dyn_cast<PointerType>(Ty);
2610     return !PT || PT->getAddressSpace() != D.Pointer_AddressSpace ||
2611            VerifyIntrinsicType(PT->getElementType(), Infos, ArgTys);
2612   }
2613
2614   case IITDescriptor::Struct: {
2615     StructType *ST = dyn_cast<StructType>(Ty);
2616     if (!ST || ST->getNumElements() != D.Struct_NumElements)
2617       return true;
2618
2619     for (unsigned i = 0, e = D.Struct_NumElements; i != e; ++i)
2620       if (VerifyIntrinsicType(ST->getElementType(i), Infos, ArgTys))
2621         return true;
2622     return false;
2623   }
2624
2625   case IITDescriptor::Argument:
2626     // Two cases here - If this is the second occurrence of an argument, verify
2627     // that the later instance matches the previous instance.
2628     if (D.getArgumentNumber() < ArgTys.size())
2629       return Ty != ArgTys[D.getArgumentNumber()];
2630
2631     // Otherwise, if this is the first instance of an argument, record it and
2632     // verify the "Any" kind.
2633     assert(D.getArgumentNumber() == ArgTys.size() && "Table consistency error");
2634     ArgTys.push_back(Ty);
2635
2636     switch (D.getArgumentKind()) {
2637     case IITDescriptor::AK_Any:        return false; // Success
2638     case IITDescriptor::AK_AnyInteger: return !Ty->isIntOrIntVectorTy();
2639     case IITDescriptor::AK_AnyFloat:   return !Ty->isFPOrFPVectorTy();
2640     case IITDescriptor::AK_AnyVector:  return !isa<VectorType>(Ty);
2641     case IITDescriptor::AK_AnyPointer: return !isa<PointerType>(Ty);
2642     }
2643     llvm_unreachable("all argument kinds not covered");
2644
2645   case IITDescriptor::ExtendArgument: {
2646     // This may only be used when referring to a previous vector argument.
2647     if (D.getArgumentNumber() >= ArgTys.size())
2648       return true;
2649
2650     Type *NewTy = ArgTys[D.getArgumentNumber()];
2651     if (VectorType *VTy = dyn_cast<VectorType>(NewTy))
2652       NewTy = VectorType::getExtendedElementVectorType(VTy);
2653     else if (IntegerType *ITy = dyn_cast<IntegerType>(NewTy))
2654       NewTy = IntegerType::get(ITy->getContext(), 2 * ITy->getBitWidth());
2655     else
2656       return true;
2657
2658     return Ty != NewTy;
2659   }
2660   case IITDescriptor::TruncArgument: {
2661     // This may only be used when referring to a previous vector argument.
2662     if (D.getArgumentNumber() >= ArgTys.size())
2663       return true;
2664
2665     Type *NewTy = ArgTys[D.getArgumentNumber()];
2666     if (VectorType *VTy = dyn_cast<VectorType>(NewTy))
2667       NewTy = VectorType::getTruncatedElementVectorType(VTy);
2668     else if (IntegerType *ITy = dyn_cast<IntegerType>(NewTy))
2669       NewTy = IntegerType::get(ITy->getContext(), ITy->getBitWidth() / 2);
2670     else
2671       return true;
2672
2673     return Ty != NewTy;
2674   }
2675   case IITDescriptor::HalfVecArgument:
2676     // This may only be used when referring to a previous vector argument.
2677     return D.getArgumentNumber() >= ArgTys.size() ||
2678            !isa<VectorType>(ArgTys[D.getArgumentNumber()]) ||
2679            VectorType::getHalfElementsVectorType(
2680                          cast<VectorType>(ArgTys[D.getArgumentNumber()])) != Ty;
2681   case IITDescriptor::SameVecWidthArgument: {
2682     if (D.getArgumentNumber() >= ArgTys.size())
2683       return true;
2684     VectorType * ReferenceType =
2685       dyn_cast<VectorType>(ArgTys[D.getArgumentNumber()]);
2686     VectorType *ThisArgType = dyn_cast<VectorType>(Ty);
2687     if (!ThisArgType || !ReferenceType ||
2688         (ReferenceType->getVectorNumElements() !=
2689          ThisArgType->getVectorNumElements()))
2690       return true;
2691     return VerifyIntrinsicType(ThisArgType->getVectorElementType(),
2692                                Infos, ArgTys);
2693   }
2694   case IITDescriptor::PtrToArgument: {
2695     if (D.getArgumentNumber() >= ArgTys.size())
2696       return true;
2697     Type * ReferenceType = ArgTys[D.getArgumentNumber()];
2698     PointerType *ThisArgType = dyn_cast<PointerType>(Ty);
2699     return (!ThisArgType || ThisArgType->getElementType() != ReferenceType);
2700   }
2701   case IITDescriptor::VecOfPtrsToElt: {
2702     if (D.getArgumentNumber() >= ArgTys.size())
2703       return true;
2704     VectorType * ReferenceType =
2705       dyn_cast<VectorType> (ArgTys[D.getArgumentNumber()]);
2706     VectorType *ThisArgVecTy = dyn_cast<VectorType>(Ty);
2707     if (!ThisArgVecTy || !ReferenceType ||
2708         (ReferenceType->getVectorNumElements() !=
2709          ThisArgVecTy->getVectorNumElements()))
2710       return true;
2711     PointerType *ThisArgEltTy =
2712       dyn_cast<PointerType>(ThisArgVecTy->getVectorElementType());
2713     if (!ThisArgEltTy)
2714       return true;
2715     return (!(ThisArgEltTy->getElementType() ==
2716             ReferenceType->getVectorElementType()));
2717   }
2718   }
2719   llvm_unreachable("unhandled");
2720 }
2721
2722 /// \brief Verify if the intrinsic has variable arguments.
2723 /// This method is intended to be called after all the fixed arguments have been
2724 /// verified first.
2725 ///
2726 /// This method returns true on error and does not print an error message.
2727 bool
2728 Verifier::VerifyIntrinsicIsVarArg(bool isVarArg,
2729                                   ArrayRef<Intrinsic::IITDescriptor> &Infos) {
2730   using namespace Intrinsic;
2731
2732   // If there are no descriptors left, then it can't be a vararg.
2733   if (Infos.empty())
2734     return isVarArg;
2735
2736   // There should be only one descriptor remaining at this point.
2737   if (Infos.size() != 1)
2738     return true;
2739
2740   // Check and verify the descriptor.
2741   IITDescriptor D = Infos.front();
2742   Infos = Infos.slice(1);
2743   if (D.Kind == IITDescriptor::VarArg)
2744     return !isVarArg;
2745
2746   return true;
2747 }
2748
2749 /// visitIntrinsicFunction - Allow intrinsics to be verified in different ways.
2750 ///
2751 void Verifier::visitIntrinsicFunctionCall(Intrinsic::ID ID, CallInst &CI) {
2752   Function *IF = CI.getCalledFunction();
2753   Assert(IF->isDeclaration(), "Intrinsic functions should never be defined!",
2754          IF);
2755
2756   // Verify that the intrinsic prototype lines up with what the .td files
2757   // describe.
2758   FunctionType *IFTy = IF->getFunctionType();
2759   bool IsVarArg = IFTy->isVarArg();
2760
2761   SmallVector<Intrinsic::IITDescriptor, 8> Table;
2762   getIntrinsicInfoTableEntries(ID, Table);
2763   ArrayRef<Intrinsic::IITDescriptor> TableRef = Table;
2764
2765   SmallVector<Type *, 4> ArgTys;
2766   Assert(!VerifyIntrinsicType(IFTy->getReturnType(), TableRef, ArgTys),
2767          "Intrinsic has incorrect return type!", IF);
2768   for (unsigned i = 0, e = IFTy->getNumParams(); i != e; ++i)
2769     Assert(!VerifyIntrinsicType(IFTy->getParamType(i), TableRef, ArgTys),
2770            "Intrinsic has incorrect argument type!", IF);
2771
2772   // Verify if the intrinsic call matches the vararg property.
2773   if (IsVarArg)
2774     Assert(!VerifyIntrinsicIsVarArg(IsVarArg, TableRef),
2775            "Intrinsic was not defined with variable arguments!", IF);
2776   else
2777     Assert(!VerifyIntrinsicIsVarArg(IsVarArg, TableRef),
2778            "Callsite was not defined with variable arguments!", IF);
2779
2780   // All descriptors should be absorbed by now.
2781   Assert(TableRef.empty(), "Intrinsic has too few arguments!", IF);
2782
2783   // Now that we have the intrinsic ID and the actual argument types (and we
2784   // know they are legal for the intrinsic!) get the intrinsic name through the
2785   // usual means.  This allows us to verify the mangling of argument types into
2786   // the name.
2787   const std::string ExpectedName = Intrinsic::getName(ID, ArgTys);
2788   Assert(ExpectedName == IF->getName(),
2789          "Intrinsic name not mangled correctly for type arguments! "
2790          "Should be: " +
2791              ExpectedName,
2792          IF);
2793
2794   // If the intrinsic takes MDNode arguments, verify that they are either global
2795   // or are local to *this* function.
2796   for (unsigned i = 0, e = CI.getNumArgOperands(); i != e; ++i)
2797     if (auto *MD = dyn_cast<MetadataAsValue>(CI.getArgOperand(i)))
2798       visitMetadataAsValue(*MD, CI.getParent()->getParent());
2799
2800   switch (ID) {
2801   default:
2802     break;
2803   case Intrinsic::ctlz:  // llvm.ctlz
2804   case Intrinsic::cttz:  // llvm.cttz
2805     Assert(isa<ConstantInt>(CI.getArgOperand(1)),
2806            "is_zero_undef argument of bit counting intrinsics must be a "
2807            "constant int",
2808            &CI);
2809     break;
2810   case Intrinsic::dbg_declare: // llvm.dbg.declare
2811     Assert(isa<MetadataAsValue>(CI.getArgOperand(0)),
2812            "invalid llvm.dbg.declare intrinsic call 1", &CI);
2813     visitDbgIntrinsic("declare", cast<DbgDeclareInst>(CI));
2814     break;
2815   case Intrinsic::dbg_value: // llvm.dbg.value
2816     visitDbgIntrinsic("value", cast<DbgValueInst>(CI));
2817     break;
2818   case Intrinsic::memcpy:
2819   case Intrinsic::memmove:
2820   case Intrinsic::memset: {
2821     ConstantInt *AlignCI = dyn_cast<ConstantInt>(CI.getArgOperand(3));
2822     Assert(AlignCI,
2823            "alignment argument of memory intrinsics must be a constant int",
2824            &CI);
2825     const APInt &AlignVal = AlignCI->getValue();
2826     Assert(AlignCI->isZero() || AlignVal.isPowerOf2(),
2827            "alignment argument of memory intrinsics must be a power of 2", &CI);
2828     Assert(isa<ConstantInt>(CI.getArgOperand(4)),
2829            "isvolatile argument of memory intrinsics must be a constant int",
2830            &CI);
2831     break;
2832   }
2833   case Intrinsic::gcroot:
2834   case Intrinsic::gcwrite:
2835   case Intrinsic::gcread:
2836     if (ID == Intrinsic::gcroot) {
2837       AllocaInst *AI =
2838         dyn_cast<AllocaInst>(CI.getArgOperand(0)->stripPointerCasts());
2839       Assert(AI, "llvm.gcroot parameter #1 must be an alloca.", &CI);
2840       Assert(isa<Constant>(CI.getArgOperand(1)),
2841              "llvm.gcroot parameter #2 must be a constant.", &CI);
2842       if (!AI->getType()->getElementType()->isPointerTy()) {
2843         Assert(!isa<ConstantPointerNull>(CI.getArgOperand(1)),
2844                "llvm.gcroot parameter #1 must either be a pointer alloca, "
2845                "or argument #2 must be a non-null constant.",
2846                &CI);
2847       }
2848     }
2849
2850     Assert(CI.getParent()->getParent()->hasGC(),
2851            "Enclosing function does not use GC.", &CI);
2852     break;
2853   case Intrinsic::init_trampoline:
2854     Assert(isa<Function>(CI.getArgOperand(1)->stripPointerCasts()),
2855            "llvm.init_trampoline parameter #2 must resolve to a function.",
2856            &CI);
2857     break;
2858   case Intrinsic::prefetch:
2859     Assert(isa<ConstantInt>(CI.getArgOperand(1)) &&
2860                isa<ConstantInt>(CI.getArgOperand(2)) &&
2861                cast<ConstantInt>(CI.getArgOperand(1))->getZExtValue() < 2 &&
2862                cast<ConstantInt>(CI.getArgOperand(2))->getZExtValue() < 4,
2863            "invalid arguments to llvm.prefetch", &CI);
2864     break;
2865   case Intrinsic::stackprotector:
2866     Assert(isa<AllocaInst>(CI.getArgOperand(1)->stripPointerCasts()),
2867            "llvm.stackprotector parameter #2 must resolve to an alloca.", &CI);
2868     break;
2869   case Intrinsic::lifetime_start:
2870   case Intrinsic::lifetime_end:
2871   case Intrinsic::invariant_start:
2872     Assert(isa<ConstantInt>(CI.getArgOperand(0)),
2873            "size argument of memory use markers must be a constant integer",
2874            &CI);
2875     break;
2876   case Intrinsic::invariant_end:
2877     Assert(isa<ConstantInt>(CI.getArgOperand(1)),
2878            "llvm.invariant.end parameter #2 must be a constant integer", &CI);
2879     break;
2880
2881   case Intrinsic::frameescape: {
2882     BasicBlock *BB = CI.getParent();
2883     Assert(BB == &BB->getParent()->front(),
2884            "llvm.frameescape used outside of entry block", &CI);
2885     Assert(!SawFrameEscape,
2886            "multiple calls to llvm.frameescape in one function", &CI);
2887     for (Value *Arg : CI.arg_operands()) {
2888       auto *AI = dyn_cast<AllocaInst>(Arg->stripPointerCasts());
2889       Assert(AI && AI->isStaticAlloca(),
2890              "llvm.frameescape only accepts static allocas", &CI);
2891     }
2892     FrameEscapeInfo[BB->getParent()].first = CI.getNumArgOperands();
2893     SawFrameEscape = true;
2894     break;
2895   }
2896   case Intrinsic::framerecover: {
2897     Value *FnArg = CI.getArgOperand(0)->stripPointerCasts();
2898     Function *Fn = dyn_cast<Function>(FnArg);
2899     Assert(Fn && !Fn->isDeclaration(),
2900            "llvm.framerecover first "
2901            "argument must be function defined in this module",
2902            &CI);
2903     auto *IdxArg = dyn_cast<ConstantInt>(CI.getArgOperand(2));
2904     Assert(IdxArg, "idx argument of llvm.framerecover must be a constant int",
2905            &CI);
2906     auto &Entry = FrameEscapeInfo[Fn];
2907     Entry.second = unsigned(
2908         std::max(uint64_t(Entry.second), IdxArg->getLimitedValue(~0U) + 1));
2909     break;
2910   }
2911
2912   case Intrinsic::eh_parentframe: {
2913     auto *AI = dyn_cast<AllocaInst>(CI.getArgOperand(0)->stripPointerCasts());
2914     Assert(AI && AI->isStaticAlloca(),
2915            "llvm.eh.parentframe requires a static alloca", &CI);
2916     break;
2917   }
2918
2919   case Intrinsic::eh_unwindhelp: {
2920     auto *AI = dyn_cast<AllocaInst>(CI.getArgOperand(0)->stripPointerCasts());
2921     Assert(AI && AI->isStaticAlloca(),
2922            "llvm.eh.unwindhelp requires a static alloca", &CI);
2923     break;
2924   }
2925
2926   case Intrinsic::experimental_gc_statepoint:
2927     Assert(!CI.isInlineAsm(),
2928            "gc.statepoint support for inline assembly unimplemented", &CI);
2929
2930     VerifyStatepoint(ImmutableCallSite(&CI));
2931     break;
2932   case Intrinsic::experimental_gc_result_int:
2933   case Intrinsic::experimental_gc_result_float:
2934   case Intrinsic::experimental_gc_result_ptr:
2935   case Intrinsic::experimental_gc_result: {
2936     // Are we tied to a statepoint properly?
2937     CallSite StatepointCS(CI.getArgOperand(0));
2938     const Function *StatepointFn =
2939       StatepointCS.getInstruction() ? StatepointCS.getCalledFunction() : nullptr;
2940     Assert(StatepointFn && StatepointFn->isDeclaration() &&
2941                StatepointFn->getIntrinsicID() ==
2942                    Intrinsic::experimental_gc_statepoint,
2943            "gc.result operand #1 must be from a statepoint", &CI,
2944            CI.getArgOperand(0));
2945
2946     // Assert that result type matches wrapped callee.
2947     const Value *Target = StatepointCS.getArgument(0);
2948     const PointerType *PT = cast<PointerType>(Target->getType());
2949     const FunctionType *TargetFuncType =
2950       cast<FunctionType>(PT->getElementType());
2951     Assert(CI.getType() == TargetFuncType->getReturnType(),
2952            "gc.result result type does not match wrapped callee", &CI);
2953     break;
2954   }
2955   case Intrinsic::experimental_gc_relocate: {
2956     Assert(CI.getNumArgOperands() == 3, "wrong number of arguments", &CI);
2957
2958     // Check that this relocate is correctly tied to the statepoint
2959
2960     // This is case for relocate on the unwinding path of an invoke statepoint
2961     if (ExtractValueInst *ExtractValue =
2962           dyn_cast<ExtractValueInst>(CI.getArgOperand(0))) {
2963       Assert(isa<LandingPadInst>(ExtractValue->getAggregateOperand()),
2964              "gc relocate on unwind path incorrectly linked to the statepoint",
2965              &CI);
2966
2967       const BasicBlock *invokeBB =
2968         ExtractValue->getParent()->getUniquePredecessor();
2969
2970       // Landingpad relocates should have only one predecessor with invoke
2971       // statepoint terminator
2972       Assert(invokeBB, "safepoints should have unique landingpads",
2973              ExtractValue->getParent());
2974       Assert(invokeBB->getTerminator(), "safepoint block should be well formed",
2975              invokeBB);
2976       Assert(isStatepoint(invokeBB->getTerminator()),
2977              "gc relocate should be linked to a statepoint", invokeBB);
2978     }
2979     else {
2980       // In all other cases relocate should be tied to the statepoint directly.
2981       // This covers relocates on a normal return path of invoke statepoint and
2982       // relocates of a call statepoint
2983       auto Token = CI.getArgOperand(0);
2984       Assert(isa<Instruction>(Token) && isStatepoint(cast<Instruction>(Token)),
2985              "gc relocate is incorrectly tied to the statepoint", &CI, Token);
2986     }
2987
2988     // Verify rest of the relocate arguments
2989
2990     GCRelocateOperands ops(&CI);
2991     ImmutableCallSite StatepointCS(ops.statepoint());
2992
2993     // Both the base and derived must be piped through the safepoint
2994     Value* Base = CI.getArgOperand(1);
2995     Assert(isa<ConstantInt>(Base),
2996            "gc.relocate operand #2 must be integer offset", &CI);
2997
2998     Value* Derived = CI.getArgOperand(2);
2999     Assert(isa<ConstantInt>(Derived),
3000            "gc.relocate operand #3 must be integer offset", &CI);
3001
3002     const int BaseIndex = cast<ConstantInt>(Base)->getZExtValue();
3003     const int DerivedIndex = cast<ConstantInt>(Derived)->getZExtValue();
3004     // Check the bounds
3005     Assert(0 <= BaseIndex && BaseIndex < (int)StatepointCS.arg_size(),
3006            "gc.relocate: statepoint base index out of bounds", &CI);
3007     Assert(0 <= DerivedIndex && DerivedIndex < (int)StatepointCS.arg_size(),
3008            "gc.relocate: statepoint derived index out of bounds", &CI);
3009
3010     // Check that BaseIndex and DerivedIndex fall within the 'gc parameters'
3011     // section of the statepoint's argument
3012     Assert(StatepointCS.arg_size() > 0,
3013            "gc.statepoint: insufficient arguments");
3014     Assert(isa<ConstantInt>(StatepointCS.getArgument(1)),
3015            "gc.statement: number of call arguments must be constant integer");
3016     const unsigned NumCallArgs =
3017       cast<ConstantInt>(StatepointCS.getArgument(1))->getZExtValue();
3018     Assert(StatepointCS.arg_size() > NumCallArgs+3,
3019            "gc.statepoint: mismatch in number of call arguments");
3020     Assert(isa<ConstantInt>(StatepointCS.getArgument(NumCallArgs+3)),
3021            "gc.statepoint: number of deoptimization arguments must be "
3022            "a constant integer");
3023     const int NumDeoptArgs =
3024       cast<ConstantInt>(StatepointCS.getArgument(NumCallArgs + 3))->getZExtValue();
3025     const int GCParamArgsStart = NumCallArgs + NumDeoptArgs + 4;
3026     const int GCParamArgsEnd = StatepointCS.arg_size();
3027     Assert(GCParamArgsStart <= BaseIndex && BaseIndex < GCParamArgsEnd,
3028            "gc.relocate: statepoint base index doesn't fall within the "
3029            "'gc parameters' section of the statepoint call",
3030            &CI);
3031     Assert(GCParamArgsStart <= DerivedIndex && DerivedIndex < GCParamArgsEnd,
3032            "gc.relocate: statepoint derived index doesn't fall within the "
3033            "'gc parameters' section of the statepoint call",
3034            &CI);
3035
3036     // Assert that the result type matches the type of the relocated pointer
3037     GCRelocateOperands Operands(&CI);
3038     Assert(Operands.derivedPtr()->getType() == CI.getType(),
3039            "gc.relocate: relocating a pointer shouldn't change its type", &CI);
3040     break;
3041   }
3042   };
3043 }
3044
3045 template <class DbgIntrinsicTy>
3046 void Verifier::visitDbgIntrinsic(StringRef Kind, DbgIntrinsicTy &DII) {
3047   auto *MD = cast<MetadataAsValue>(DII.getArgOperand(0))->getMetadata();
3048   Assert(isa<ValueAsMetadata>(MD) ||
3049              (isa<MDNode>(MD) && !cast<MDNode>(MD)->getNumOperands()),
3050          "invalid llvm.dbg." + Kind + " intrinsic address/value", &DII, MD);
3051   Assert(isa<MDLocalVariable>(DII.getRawVariable()),
3052          "invalid llvm.dbg." + Kind + " intrinsic variable", &DII,
3053          DII.getRawVariable());
3054   Assert(isa<MDExpression>(DII.getRawExpression()),
3055          "invalid llvm.dbg." + Kind + " intrinsic expression", &DII,
3056          DII.getRawExpression());
3057 }
3058
3059 void Verifier::verifyDebugInfo() {
3060   // Run the debug info verifier only if the regular verifier succeeds, since
3061   // sometimes checks that have already failed will cause crashes here.
3062   if (EverBroken || !VerifyDebugInfo)
3063     return;
3064
3065   DebugInfoFinder Finder;
3066   Finder.processModule(*M);
3067   processInstructions(Finder);
3068
3069   // Verify Debug Info.
3070   //
3071   // NOTE:  The loud braces are necessary for MSVC compatibility.
3072   for (DICompileUnit CU : Finder.compile_units()) {
3073     Assert(CU.Verify(), "DICompileUnit does not Verify!", CU);
3074   }
3075   for (DISubprogram S : Finder.subprograms()) {
3076     Assert(S.Verify(), "DISubprogram does not Verify!", S);
3077   }
3078   for (DIGlobalVariable GV : Finder.global_variables()) {
3079     Assert(GV.Verify(), "DIGlobalVariable does not Verify!", GV);
3080   }
3081   for (DIType T : Finder.types()) {
3082     Assert(T.Verify(), "DIType does not Verify!", T);
3083   }
3084   for (DIScope S : Finder.scopes()) {
3085     Assert(S.Verify(), "DIScope does not Verify!", S);
3086   }
3087 }
3088
3089 void Verifier::processInstructions(DebugInfoFinder &Finder) {
3090   for (const Function &F : *M)
3091     for (auto I = inst_begin(&F), E = inst_end(&F); I != E; ++I) {
3092       if (MDNode *MD = I->getMetadata(LLVMContext::MD_dbg))
3093         Finder.processLocation(*M, DILocation(MD));
3094       if (const CallInst *CI = dyn_cast<CallInst>(&*I))
3095         processCallInst(Finder, *CI);
3096     }
3097 }
3098
3099 void Verifier::processCallInst(DebugInfoFinder &Finder, const CallInst &CI) {
3100   if (Function *F = CI.getCalledFunction())
3101     if (Intrinsic::ID ID = (Intrinsic::ID)F->getIntrinsicID())
3102       switch (ID) {
3103       case Intrinsic::dbg_declare:
3104         Finder.processDeclare(*M, cast<DbgDeclareInst>(&CI));
3105         break;
3106       case Intrinsic::dbg_value:
3107         Finder.processValue(*M, cast<DbgValueInst>(&CI));
3108         break;
3109       default:
3110         break;
3111       }
3112 }
3113
3114 //===----------------------------------------------------------------------===//
3115 //  Implement the public interfaces to this file...
3116 //===----------------------------------------------------------------------===//
3117
3118 bool llvm::verifyFunction(const Function &f, raw_ostream *OS) {
3119   Function &F = const_cast<Function &>(f);
3120   assert(!F.isDeclaration() && "Cannot verify external functions");
3121
3122   raw_null_ostream NullStr;
3123   Verifier V(OS ? *OS : NullStr);
3124
3125   // Note that this function's return value is inverted from what you would
3126   // expect of a function called "verify".
3127   return !V.verify(F);
3128 }
3129
3130 bool llvm::verifyModule(const Module &M, raw_ostream *OS) {
3131   raw_null_ostream NullStr;
3132   Verifier V(OS ? *OS : NullStr);
3133
3134   bool Broken = false;
3135   for (Module::const_iterator I = M.begin(), E = M.end(); I != E; ++I)
3136     if (!I->isDeclaration() && !I->isMaterializable())
3137       Broken |= !V.verify(*I);
3138
3139   // Note that this function's return value is inverted from what you would
3140   // expect of a function called "verify".
3141   return !V.verify(M) || Broken;
3142 }
3143
3144 namespace {
3145 struct VerifierLegacyPass : public FunctionPass {
3146   static char ID;
3147
3148   Verifier V;
3149   bool FatalErrors;
3150
3151   VerifierLegacyPass() : FunctionPass(ID), V(dbgs()), FatalErrors(true) {
3152     initializeVerifierLegacyPassPass(*PassRegistry::getPassRegistry());
3153   }
3154   explicit VerifierLegacyPass(bool FatalErrors)
3155       : FunctionPass(ID), V(dbgs()), FatalErrors(FatalErrors) {
3156     initializeVerifierLegacyPassPass(*PassRegistry::getPassRegistry());
3157   }
3158
3159   bool runOnFunction(Function &F) override {
3160     if (!V.verify(F) && FatalErrors)
3161       report_fatal_error("Broken function found, compilation aborted!");
3162
3163     return false;
3164   }
3165
3166   bool doFinalization(Module &M) override {
3167     if (!V.verify(M) && FatalErrors)
3168       report_fatal_error("Broken module found, compilation aborted!");
3169
3170     return false;
3171   }
3172
3173   void getAnalysisUsage(AnalysisUsage &AU) const override {
3174     AU.setPreservesAll();
3175   }
3176 };
3177 }
3178
3179 char VerifierLegacyPass::ID = 0;
3180 INITIALIZE_PASS(VerifierLegacyPass, "verify", "Module Verifier", false, false)
3181
3182 FunctionPass *llvm::createVerifierPass(bool FatalErrors) {
3183   return new VerifierLegacyPass(FatalErrors);
3184 }
3185
3186 PreservedAnalyses VerifierPass::run(Module &M) {
3187   if (verifyModule(M, &dbgs()) && FatalErrors)
3188     report_fatal_error("Broken module found, compilation aborted!");
3189
3190   return PreservedAnalyses::all();
3191 }
3192
3193 PreservedAnalyses VerifierPass::run(Function &F) {
3194   if (verifyFunction(F, &dbgs()) && FatalErrors)
3195     report_fatal_error("Broken function found, compilation aborted!");
3196
3197   return PreservedAnalyses::all();
3198 }