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