LCOV - code coverage report
Current view: top level - lib/IR - Verifier.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 1767 1845 95.8 %
Date: 2018-07-13 00:08:38 Functions: 294 412 71.4 %
Legend: Lines: hit not hit

          Line data    Source code
       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             : //  * Landingpad instructions must be in a function with a personality function.
      43             : //  * All other things that are tested by asserts spread about the code...
      44             : //
      45             : //===----------------------------------------------------------------------===//
      46             : 
      47             : #include "llvm/IR/Verifier.h"
      48             : #include "llvm/ADT/APFloat.h"
      49             : #include "llvm/ADT/APInt.h"
      50             : #include "llvm/ADT/ArrayRef.h"
      51             : #include "llvm/ADT/DenseMap.h"
      52             : #include "llvm/ADT/MapVector.h"
      53             : #include "llvm/ADT/Optional.h"
      54             : #include "llvm/ADT/STLExtras.h"
      55             : #include "llvm/ADT/SmallPtrSet.h"
      56             : #include "llvm/ADT/SmallSet.h"
      57             : #include "llvm/ADT/SmallVector.h"
      58             : #include "llvm/ADT/StringExtras.h"
      59             : #include "llvm/ADT/StringMap.h"
      60             : #include "llvm/ADT/StringRef.h"
      61             : #include "llvm/ADT/Twine.h"
      62             : #include "llvm/ADT/ilist.h"
      63             : #include "llvm/BinaryFormat/Dwarf.h"
      64             : #include "llvm/IR/Argument.h"
      65             : #include "llvm/IR/Attributes.h"
      66             : #include "llvm/IR/BasicBlock.h"
      67             : #include "llvm/IR/CFG.h"
      68             : #include "llvm/IR/CallSite.h"
      69             : #include "llvm/IR/CallingConv.h"
      70             : #include "llvm/IR/Comdat.h"
      71             : #include "llvm/IR/Constant.h"
      72             : #include "llvm/IR/ConstantRange.h"
      73             : #include "llvm/IR/Constants.h"
      74             : #include "llvm/IR/DataLayout.h"
      75             : #include "llvm/IR/DebugInfo.h"
      76             : #include "llvm/IR/DebugInfoMetadata.h"
      77             : #include "llvm/IR/DebugLoc.h"
      78             : #include "llvm/IR/DerivedTypes.h"
      79             : #include "llvm/IR/Dominators.h"
      80             : #include "llvm/IR/Function.h"
      81             : #include "llvm/IR/GlobalAlias.h"
      82             : #include "llvm/IR/GlobalValue.h"
      83             : #include "llvm/IR/GlobalVariable.h"
      84             : #include "llvm/IR/InlineAsm.h"
      85             : #include "llvm/IR/InstVisitor.h"
      86             : #include "llvm/IR/InstrTypes.h"
      87             : #include "llvm/IR/Instruction.h"
      88             : #include "llvm/IR/Instructions.h"
      89             : #include "llvm/IR/IntrinsicInst.h"
      90             : #include "llvm/IR/Intrinsics.h"
      91             : #include "llvm/IR/LLVMContext.h"
      92             : #include "llvm/IR/Metadata.h"
      93             : #include "llvm/IR/Module.h"
      94             : #include "llvm/IR/ModuleSlotTracker.h"
      95             : #include "llvm/IR/PassManager.h"
      96             : #include "llvm/IR/Statepoint.h"
      97             : #include "llvm/IR/Type.h"
      98             : #include "llvm/IR/Use.h"
      99             : #include "llvm/IR/User.h"
     100             : #include "llvm/IR/Value.h"
     101             : #include "llvm/Pass.h"
     102             : #include "llvm/Support/AtomicOrdering.h"
     103             : #include "llvm/Support/Casting.h"
     104             : #include "llvm/Support/CommandLine.h"
     105             : #include "llvm/Support/Debug.h"
     106             : #include "llvm/Support/ErrorHandling.h"
     107             : #include "llvm/Support/MathExtras.h"
     108             : #include "llvm/Support/raw_ostream.h"
     109             : #include <algorithm>
     110             : #include <cassert>
     111             : #include <cstdint>
     112             : #include <memory>
     113             : #include <string>
     114             : #include <utility>
     115             : 
     116             : using namespace llvm;
     117             : 
     118             : namespace llvm {
     119             : 
     120       96119 : struct VerifierSupport {
     121             :   raw_ostream *OS;
     122             :   const Module &M;
     123             :   ModuleSlotTracker MST;
     124             :   const DataLayout &DL;
     125             :   LLVMContext &Context;
     126             : 
     127             :   /// Track the brokenness of the module while recursively visiting.
     128             :   bool Broken = false;
     129             :   /// Broken debug info can be "recovered" from by stripping the debug info.
     130             :   bool BrokenDebugInfo = false;
     131             :   /// Whether to treat broken debug info as an error.
     132             :   bool TreatBrokenDebugInfoAsError = true;
     133             : 
     134       96385 :   explicit VerifierSupport(raw_ostream *OS, const Module &M)
     135       96385 :       : OS(OS), M(M), MST(&M), DL(M.getDataLayout()), Context(M.getContext()) {}
     136             : 
     137             : private:
     138           8 :   void Write(const Module *M) {
     139          16 :     *OS << "; ModuleID = '" << M->getModuleIdentifier() << "'\n";
     140           8 :   }
     141             : 
     142         399 :   void Write(const Value *V) {
     143         399 :     if (!V)
     144             :       return;
     145         397 :     if (isa<Instruction>(V)) {
     146         267 :       V->print(*OS, MST);
     147         267 :       *OS << '\n';
     148             :     } else {
     149         130 :       V->printAsOperand(*OS, true, MST);
     150         130 :       *OS << '\n';
     151             :     }
     152             :   }
     153             : 
     154             :   void Write(ImmutableCallSite CS) {
     155          37 :     Write(CS.getInstruction());
     156             :   }
     157             : 
     158         195 :   void Write(const Metadata *MD) {
     159         195 :     if (!MD)
     160             :       return;
     161         190 :     MD->print(*OS, MST, &M);
     162         190 :     *OS << '\n';
     163             :   }
     164             : 
     165             :   template <class T> void Write(const MDTupleTypedArrayWrapper<T> &MD) {
     166           0 :     Write(MD.get());
     167             :   }
     168             : 
     169           7 :   void Write(const NamedMDNode *NMD) {
     170           7 :     if (!NMD)
     171             :       return;
     172           7 :     NMD->print(*OS, MST);
     173           7 :     *OS << '\n';
     174             :   }
     175             : 
     176           2 :   void Write(Type *T) {
     177           2 :     if (!T)
     178             :       return;
     179           2 :     *OS << ' ' << *T;
     180             :   }
     181             : 
     182             :   void Write(const Comdat *C) {
     183             :     if (!C)
     184             :       return;
     185             :     *OS << *C;
     186             :   }
     187             : 
     188           3 :   void Write(const APInt *AI) {
     189           3 :     if (!AI)
     190             :       return;
     191           3 :     *OS << *AI << '\n';
     192             :   }
     193             : 
     194          10 :   void Write(const unsigned i) { *OS << i << '\n'; }
     195             : 
     196             :   template <typename T> void Write(ArrayRef<T> Vs) {
     197          28 :     for (const T &V : Vs)
     198          12 :       Write(V);
     199             :   }
     200             : 
     201             :   template <typename T1, typename... Ts>
     202          75 :   void WriteTs(const T1 &V1, const Ts &... Vs) {
     203         570 :     Write(V1);
     204         172 :     WriteTs(Vs...);
     205          75 :   }
     206             : 
     207             :   template <typename... Ts> void WriteTs() {}
     208             : 
     209             : public:
     210             :   /// A check failed, so printout out the condition and the message.
     211             :   ///
     212             :   /// This provides a nice place to put a breakpoint if you want to see why
     213             :   /// something is not correct.
     214         360 :   void CheckFailed(const Twine &Message) {
     215         360 :     if (OS)
     216             :       *OS << Message << '\n';
     217         360 :     Broken = true;
     218         360 :   }
     219             : 
     220             :   /// A check failed (with values to print).
     221             :   ///
     222             :   /// This calls the Message-only version so that the above is easier to set a
     223             :   /// breakpoint on.
     224             :   template <typename T1, typename... Ts>
     225         340 :   void CheckFailed(const Twine &Message, const T1 &V1, const Ts &... Vs) {
     226         340 :     CheckFailed(Message);
     227         340 :     if (OS)
     228         320 :       WriteTs(V1, Vs...);
     229         340 :   }
     230             : 
     231             :   /// A debug info check failed.
     232         106 :   void DebugInfoCheckFailed(const Twine &Message) {
     233         106 :     if (OS)
     234             :       *OS << Message << '\n';
     235         106 :     Broken |= TreatBrokenDebugInfoAsError;
     236         106 :     BrokenDebugInfo = true;
     237         106 :   }
     238             : 
     239             :   /// A debug info check failed (with values to print).
     240             :   template <typename T1, typename... Ts>
     241         104 :   void DebugInfoCheckFailed(const Twine &Message, const T1 &V1,
     242             :                             const Ts &... Vs) {
     243         104 :     DebugInfoCheckFailed(Message);
     244         104 :     if (OS)
     245         101 :       WriteTs(V1, Vs...);
     246         104 :   }
     247             : };
     248             : 
     249             : } // namespace llvm
     250             : 
     251             : namespace {
     252             : 
     253      288357 : class Verifier : public InstVisitor<Verifier>, VerifierSupport {
     254             :   friend class InstVisitor<Verifier>;
     255             : 
     256             :   DominatorTree DT;
     257             : 
     258             :   /// When verifying a basic block, keep track of all of the
     259             :   /// instructions we have seen so far.
     260             :   ///
     261             :   /// This allows us to do efficient dominance checks for the case when an
     262             :   /// instruction has an operand that is an instruction in the same block.
     263             :   SmallPtrSet<Instruction *, 16> InstsInThisBlock;
     264             : 
     265             :   /// Keep track of the metadata nodes that have been checked already.
     266             :   SmallPtrSet<const Metadata *, 32> MDNodes;
     267             : 
     268             :   /// Keep track which DISubprogram is attached to which function.
     269             :   DenseMap<const DISubprogram *, const Function *> DISubprogramAttachments;
     270             : 
     271             :   /// Track all DICompileUnits visited.
     272             :   SmallPtrSet<const Metadata *, 2> CUVisited;
     273             : 
     274             :   /// The result type for a landingpad.
     275             :   Type *LandingPadResultTy;
     276             : 
     277             :   /// Whether we've seen a call to @llvm.localescape in this function
     278             :   /// already.
     279             :   bool SawFrameEscape;
     280             : 
     281             :   /// Whether the current function has a DISubprogram attached to it.
     282             :   bool HasDebugInfo = false;
     283             : 
     284             :   /// Stores the count of how many objects were passed to llvm.localescape for a
     285             :   /// given function and the largest index passed to llvm.localrecover.
     286             :   DenseMap<Function *, std::pair<unsigned, unsigned>> FrameEscapeInfo;
     287             : 
     288             :   // Maps catchswitches and cleanuppads that unwind to siblings to the
     289             :   // terminators that indicate the unwind, used to detect cycles therein.
     290             :   MapVector<Instruction *, TerminatorInst *> SiblingFuncletInfo;
     291             : 
     292             :   /// Cache of constants visited in search of ConstantExprs.
     293             :   SmallPtrSet<const Constant *, 32> ConstantExprVisited;
     294             : 
     295             :   /// Cache of declarations of the llvm.experimental.deoptimize.<ty> intrinsic.
     296             :   SmallVector<const Function *, 4> DeoptimizeDeclarations;
     297             : 
     298             :   // Verify that this GlobalValue is only used in this module.
     299             :   // This map is used to avoid visiting uses twice. We can arrive at a user
     300             :   // twice, if they have multiple operands. In particular for very large
     301             :   // constant expressions, we can arrive at a particular user many times.
     302             :   SmallPtrSet<const Value *, 32> GlobalValueVisited;
     303             : 
     304             :   // Keeps track of duplicate function argument debug info.
     305             :   SmallVector<const DILocalVariable *, 16> DebugFnArgs;
     306             : 
     307             :   TBAAVerifier TBAAVerifyHelper;
     308             : 
     309             :   void checkAtomicMemAccessSize(Type *Ty, const Instruction *I);
     310             : 
     311             : public:
     312       96385 :   explicit Verifier(raw_ostream *OS, bool ShouldTreatBrokenDebugInfoAsError,
     313             :                     const Module &M)
     314       96385 :       : VerifierSupport(OS, M), LandingPadResultTy(nullptr),
     315      289155 :         SawFrameEscape(false), TBAAVerifyHelper(this) {
     316       96385 :     TreatBrokenDebugInfoAsError = ShouldTreatBrokenDebugInfoAsError;
     317       96385 :   }
     318             : 
     319             :   bool hasBrokenDebugInfo() const { return BrokenDebugInfo; }
     320             : 
     321     1063344 :   bool verify(const Function &F) {
     322             :     assert(F.getParent() == &M &&
     323             :            "An instance of this class only works with a specific module!");
     324             : 
     325             :     // First ensure the function is well-enough formed to compute dominance
     326             :     // information, and directly compute a dominance tree. We don't rely on the
     327             :     // pass manager to provide this as it isolates us from a potentially
     328             :     // out-of-date dominator tree and makes it significantly more complex to run
     329             :     // this code outside of a pass manager.
     330             :     // FIXME: It's really gross that we have to cast away constness here.
     331     1063344 :     if (!F.empty())
     332      781446 :       DT.recalculate(const_cast<Function &>(F));
     333             : 
     334     2206544 :     for (const BasicBlock &BB : F) {
     335     2286404 :       if (!BB.empty() && BB.back().isTerminator())
     336             :         continue;
     337             : 
     338           3 :       if (OS) {
     339           0 :         *OS << "Basic Block in function '" << F.getName()
     340           0 :             << "' does not have terminator!\n";
     341           0 :         BB.printAsOperand(*OS, true, MST);
     342           0 :         *OS << "\n";
     343             :       }
     344             :       return false;
     345             :     }
     346             : 
     347     1063341 :     Broken = false;
     348             :     // FIXME: We strip const here because the inst visitor strips const.
     349     1063341 :     visit(const_cast<Function &>(F));
     350     1063341 :     verifySiblingFuncletUnwinds();
     351     1063341 :     InstsInThisBlock.clear();
     352             :     DebugFnArgs.clear();
     353     1063341 :     LandingPadResultTy = nullptr;
     354     1063341 :     SawFrameEscape = false;
     355             :     SiblingFuncletInfo.clear();
     356             : 
     357     1063341 :     return !Broken;
     358             :   }
     359             : 
     360             :   /// Verify the module that this instance of \c Verifier was initialized with.
     361       95463 :   bool verify() {
     362       95463 :     Broken = false;
     363             : 
     364             :     // Collect all declarations of the llvm.experimental.deoptimize intrinsic.
     365     1253339 :     for (const Function &F : M)
     366     1062413 :       if (F.getIntrinsicID() == Intrinsic::experimental_deoptimize)
     367          45 :         DeoptimizeDeclarations.push_back(&F);
     368             : 
     369             :     // Now that we've visited every function, verify that we never asked to
     370             :     // recover a frame index that wasn't escaped.
     371       95463 :     verifyFrameRecoverIndices();
     372      345790 :     for (const GlobalVariable &GV : M.globals())
     373      154864 :       visitGlobalVariable(GV);
     374             : 
     375      193934 :     for (const GlobalAlias &GA : M.aliases())
     376        3008 :       visitGlobalAlias(GA);
     377             : 
     378      228951 :     for (const NamedMDNode &NMD : M.named_metadata())
     379       38025 :       visitNamedMDNode(NMD);
     380             : 
     381      218246 :     for (const StringMapEntry<Comdat> &SMEC : M.getComdatSymbolTable())
     382       27320 :       visitComdat(SMEC.getValue());
     383             : 
     384       95463 :     visitModuleFlags(M);
     385       95463 :     visitModuleIdents(M);
     386             : 
     387       95463 :     verifyCompileUnits();
     388             : 
     389       95463 :     verifyDeoptimizeCallingConvs();
     390       95463 :     DISubprogramAttachments.clear();
     391       95463 :     return !Broken;
     392             :   }
     393             : 
     394             : private:
     395             :   // Verification methods...
     396             :   void visitGlobalValue(const GlobalValue &GV);
     397             :   void visitGlobalVariable(const GlobalVariable &GV);
     398             :   void visitGlobalAlias(const GlobalAlias &GA);
     399             :   void visitAliaseeSubExpr(const GlobalAlias &A, const Constant &C);
     400             :   void visitAliaseeSubExpr(SmallPtrSetImpl<const GlobalAlias *> &Visited,
     401             :                            const GlobalAlias &A, const Constant &C);
     402             :   void visitNamedMDNode(const NamedMDNode &NMD);
     403             :   void visitMDNode(const MDNode &MD);
     404             :   void visitMetadataAsValue(const MetadataAsValue &MD, Function *F);
     405             :   void visitValueAsMetadata(const ValueAsMetadata &MD, Function *F);
     406             :   void visitComdat(const Comdat &C);
     407             :   void visitModuleIdents(const Module &M);
     408             :   void visitModuleFlags(const Module &M);
     409             :   void visitModuleFlag(const MDNode *Op,
     410             :                        DenseMap<const MDString *, const MDNode *> &SeenIDs,
     411             :                        SmallVectorImpl<const MDNode *> &Requirements);
     412             :   void visitFunction(const Function &F);
     413             :   void visitBasicBlock(BasicBlock &BB);
     414             :   void visitRangeMetadata(Instruction &I, MDNode *Range, Type *Ty);
     415             :   void visitDereferenceableMetadata(Instruction &I, MDNode *MD);
     416             : 
     417             :   template <class Ty> bool isValidMetadataArray(const MDTuple &N);
     418             : #define HANDLE_SPECIALIZED_MDNODE_LEAF(CLASS) void visit##CLASS(const CLASS &N);
     419             : #include "llvm/IR/Metadata.def"
     420             :   void visitDIScope(const DIScope &N);
     421             :   void visitDIVariable(const DIVariable &N);
     422             :   void visitDILexicalBlockBase(const DILexicalBlockBase &N);
     423             :   void visitDITemplateParameter(const DITemplateParameter &N);
     424             : 
     425             :   void visitTemplateParams(const MDNode &N, const Metadata &RawParams);
     426             : 
     427             :   // InstVisitor overrides...
     428             :   using InstVisitor<Verifier>::visit;
     429             :   void visit(Instruction &I);
     430             : 
     431             :   void visitTruncInst(TruncInst &I);
     432             :   void visitZExtInst(ZExtInst &I);
     433             :   void visitSExtInst(SExtInst &I);
     434             :   void visitFPTruncInst(FPTruncInst &I);
     435             :   void visitFPExtInst(FPExtInst &I);
     436             :   void visitFPToUIInst(FPToUIInst &I);
     437             :   void visitFPToSIInst(FPToSIInst &I);
     438             :   void visitUIToFPInst(UIToFPInst &I);
     439             :   void visitSIToFPInst(SIToFPInst &I);
     440             :   void visitIntToPtrInst(IntToPtrInst &I);
     441             :   void visitPtrToIntInst(PtrToIntInst &I);
     442             :   void visitBitCastInst(BitCastInst &I);
     443             :   void visitAddrSpaceCastInst(AddrSpaceCastInst &I);
     444             :   void visitPHINode(PHINode &PN);
     445             :   void visitBinaryOperator(BinaryOperator &B);
     446             :   void visitICmpInst(ICmpInst &IC);
     447             :   void visitFCmpInst(FCmpInst &FC);
     448             :   void visitExtractElementInst(ExtractElementInst &EI);
     449             :   void visitInsertElementInst(InsertElementInst &EI);
     450             :   void visitShuffleVectorInst(ShuffleVectorInst &EI);
     451         629 :   void visitVAArgInst(VAArgInst &VAA) { visitInstruction(VAA); }
     452             :   void visitCallInst(CallInst &CI);
     453             :   void visitInvokeInst(InvokeInst &II);
     454             :   void visitGetElementPtrInst(GetElementPtrInst &GEP);
     455             :   void visitLoadInst(LoadInst &LI);
     456             :   void visitStoreInst(StoreInst &SI);
     457             :   void verifyDominatesUse(Instruction &I, unsigned i);
     458             :   void visitInstruction(Instruction &I);
     459             :   void visitTerminatorInst(TerminatorInst &I);
     460             :   void visitBranchInst(BranchInst &BI);
     461             :   void visitReturnInst(ReturnInst &RI);
     462             :   void visitSwitchInst(SwitchInst &SI);
     463             :   void visitIndirectBrInst(IndirectBrInst &BI);
     464             :   void visitSelectInst(SelectInst &SI);
     465             :   void visitUserOp1(Instruction &I);
     466             :   void visitUserOp2(Instruction &I) { visitUserOp1(I); }
     467             :   void visitIntrinsicCallSite(Intrinsic::ID ID, CallSite CS);
     468             :   void visitConstrainedFPIntrinsic(ConstrainedFPIntrinsic &FPI);
     469             :   void visitDbgIntrinsic(StringRef Kind, DbgInfoIntrinsic &DII);
     470             :   void visitDbgLabelIntrinsic(StringRef Kind, DbgLabelInst &DLI);
     471             :   void visitAtomicCmpXchgInst(AtomicCmpXchgInst &CXI);
     472             :   void visitAtomicRMWInst(AtomicRMWInst &RMWI);
     473             :   void visitFenceInst(FenceInst &FI);
     474             :   void visitAllocaInst(AllocaInst &AI);
     475             :   void visitExtractValueInst(ExtractValueInst &EVI);
     476             :   void visitInsertValueInst(InsertValueInst &IVI);
     477             :   void visitEHPadPredecessors(Instruction &I);
     478             :   void visitLandingPadInst(LandingPadInst &LPI);
     479             :   void visitResumeInst(ResumeInst &RI);
     480             :   void visitCatchPadInst(CatchPadInst &CPI);
     481             :   void visitCatchReturnInst(CatchReturnInst &CatchReturn);
     482             :   void visitCleanupPadInst(CleanupPadInst &CPI);
     483             :   void visitFuncletPadInst(FuncletPadInst &FPI);
     484             :   void visitCatchSwitchInst(CatchSwitchInst &CatchSwitch);
     485             :   void visitCleanupReturnInst(CleanupReturnInst &CRI);
     486             : 
     487             :   void verifyCallSite(CallSite CS);
     488             :   void verifySwiftErrorCallSite(CallSite CS, const Value *SwiftErrorVal);
     489             :   void verifySwiftErrorValue(const Value *SwiftErrorVal);
     490             :   void verifyMustTailCall(CallInst &CI);
     491             :   bool performTypeCheck(Intrinsic::ID ID, Function *F, Type *Ty, int VT,
     492             :                         unsigned ArgNo, std::string &Suffix);
     493             :   bool verifyAttributeCount(AttributeList Attrs, unsigned Params);
     494             :   void verifyAttributeTypes(AttributeSet Attrs, bool IsFunction,
     495             :                             const Value *V);
     496             :   void verifyParameterAttrs(AttributeSet Attrs, Type *Ty, const Value *V);
     497             :   void verifyFunctionAttrs(FunctionType *FT, AttributeList Attrs,
     498             :                            const Value *V);
     499             :   void verifyFunctionMetadata(ArrayRef<std::pair<unsigned, MDNode *>> MDs);
     500             : 
     501             :   void visitConstantExprsRecursively(const Constant *EntryC);
     502             :   void visitConstantExpr(const ConstantExpr *CE);
     503             :   void verifyStatepoint(ImmutableCallSite CS);
     504             :   void verifyFrameRecoverIndices();
     505             :   void verifySiblingFuncletUnwinds();
     506             : 
     507             :   void verifyFragmentExpression(const DbgInfoIntrinsic &I);
     508             :   template <typename ValueOrMetadata>
     509             :   void verifyFragmentExpression(const DIVariable &V,
     510             :                                 DIExpression::FragmentInfo Fragment,
     511             :                                 ValueOrMetadata *Desc);
     512             :   void verifyFnArgs(const DbgInfoIntrinsic &I);
     513             : 
     514             :   /// Module-level debug info verification...
     515             :   void verifyCompileUnits();
     516             : 
     517             :   /// Module-level verification that all @llvm.experimental.deoptimize
     518             :   /// declarations share the same calling convention.
     519             :   void verifyDeoptimizeCallingConvs();
     520             : };
     521             : 
     522             : } // end anonymous namespace
     523             : 
     524             : /// We know that cond should be true, if not print an error message.
     525             : #define Assert(C, ...) \
     526             :   do { if (!(C)) { CheckFailed(__VA_ARGS__); return; } } while (false)
     527             : 
     528             : /// We know that a debug info condition should be true, if not print
     529             : /// an error message.
     530             : #define AssertDI(C, ...) \
     531             :   do { if (!(C)) { DebugInfoCheckFailed(__VA_ARGS__); return; } } while (false)
     532             : 
     533     6030201 : void Verifier::visit(Instruction &I) {
     534    26454367 :   for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i)
     535    20424166 :     Assert(I.getOperand(i) != nullptr, "Operand is null", &I);
     536     6030201 :   InstVisitor<Verifier>::visit(I);
     537             : }
     538             : 
     539             : // Helper to recursively iterate over indirect users. By
     540             : // returning false, the callback can ask to stop recursing
     541             : // further.
     542     1480391 : static void forEachUser(const Value *User,
     543             :                         SmallPtrSet<const Value *, 32> &Visited,
     544             :                         llvm::function_ref<bool(const Value *)> Callback) {
     545     1480391 :   if (!Visited.insert(User).second)
     546             :     return;
     547     2522731 :   for (const Value *TheNextUser : User->materialized_users())
     548     1121485 :     if (Callback(TheNextUser))
     549      259191 :       forEachUser(TheNextUser, Visited, Callback);
     550             : }
     551             : 
     552     1221205 : void Verifier::visitGlobalValue(const GlobalValue &GV) {
     553     1221209 :   Assert(!GV.isDeclaration() || GV.hasValidDeclarationLinkage(),
     554             :          "Global is external, but doesn't have external or weak linkage!", &GV);
     555             : 
     556     1221203 :   Assert(GV.getAlignment() <= Value::MaximumAlignment,
     557             :          "huge alignment values are unsupported", &GV);
     558     1224967 :   Assert(!GV.hasAppendingLinkage() || isa<GlobalVariable>(GV),
     559             :          "Only global variables can have appending linkage!", &GV);
     560             : 
     561     1221203 :   if (GV.hasAppendingLinkage()) {
     562        3764 :     const GlobalVariable *GVar = dyn_cast<GlobalVariable>(&GV);
     563        7529 :     Assert(GVar && GVar->getValueType()->isArrayTy(),
     564             :            "Only global arrays can have appending linkage!", GVar);
     565             :   }
     566             : 
     567     1220320 :   if (GV.isDeclarationForLinker())
     568      311357 :     Assert(!GV.hasComdat(), "Declaration may not be in a Comdat!", &GV);
     569             : 
     570     1221200 :   if (GV.hasDLLImportStorageClass()) {
     571        1812 :     Assert(!GV.isDSOLocal(),
     572             :            "GlobalValue with DLLImport Storage is dso_local!", &GV);
     573             : 
     574        3624 :     Assert((GV.isDeclaration() && GV.hasExternalLinkage()) ||
     575             :                GV.hasAvailableExternallyLinkage(),
     576             :            "Global is marked as dllimport, but not external", &GV);
     577             :   }
     578             : 
     579             :   if (GV.hasLocalLinkage())
     580       95250 :     Assert(GV.isDSOLocal(),
     581             :            "GlobalValue with private or internal linkage must be dso_local!",
     582             :            &GV);
     583             : 
     584     1221200 :   if (!GV.hasDefaultVisibility() && !GV.hasExternalWeakLinkage())
     585        8007 :     Assert(GV.isDSOLocal(),
     586             :            "GlobalValue with non default visibility must be dso_local!", &GV);
     587             : 
     588     3563885 :   forEachUser(&GV, GlobalValueVisited, [&](const Value *V) -> bool {
     589     1121485 :     if (const Instruction *I = dyn_cast<Instruction>(V)) {
     590      858581 :       if (!I->getParent() || !I->getParent()->getParent())
     591      862296 :         CheckFailed("Global is referenced by parentless instruction!", &GV, &M,
     592             :                     I);
     593     1717162 :       else if (I->getParent()->getParent()->getParent() != &M)
     594           4 :         CheckFailed("Global is referenced in a different module!", &GV, &M, I,
     595           2 :                     I->getParent()->getParent(),
     596           2 :                     I->getParent()->getParent()->getParent());
     597      862294 :       return false;
     598      262904 :     } else if (const Function *F = dyn_cast<Function>(V)) {
     599        7426 :       if (F->getParent() != &M)
     600           4 :         CheckFailed("Global is used by function in a different module", &GV, &M,
     601           2 :                     F, F->getParent());
     602        3713 :       return false;
     603             :     }
     604      259191 :     return true;
     605             :   });
     606             : }
     607             : 
     608      154864 : void Verifier::visitGlobalVariable(const GlobalVariable &GV) {
     609      154864 :   if (GV.hasInitializer()) {
     610      154872 :     Assert(GV.getInitializer()->getType() == GV.getValueType(),
     611             :            "Global variable initializer type does not match global "
     612             :            "variable type!",
     613             :            &GV);
     614             :     // If the global has common linkage, it must have a zero initializer and
     615             :     // cannot be constant.
     616      126066 :     if (GV.hasCommonLinkage()) {
     617       15312 :       Assert(GV.getInitializer()->isNullValue(),
     618             :              "'common' global must have a zero initializer!", &GV);
     619       15312 :       Assert(!GV.isConstant(), "'common' global may not be marked constant!",
     620             :              &GV);
     621       15313 :       Assert(!GV.hasComdat(), "'common' global may not be in a Comdat!", &GV);
     622             :     }
     623             :   }
     624             : 
     625      154863 :   if (GV.hasName() && (GV.getName() == "llvm.global_ctors" ||
     626      145552 :                        GV.getName() == "llvm.global_dtors")) {
     627        5058 :     Assert(!GV.hasInitializer() || GV.hasAppendingLinkage(),
     628             :            "invalid linkage for intrinsic global variable", &GV);
     629             :     // Don't worry about emitting an error for it not being an array,
     630             :     // visitGlobalValue will complain on appending non-array.
     631        2532 :     if (ArrayType *ATy = dyn_cast<ArrayType>(GV.getValueType())) {
     632        2532 :       StructType *STy = dyn_cast<StructType>(ATy->getElementType());
     633             :       PointerType *FuncPtrTy =
     634        2532 :           FunctionType::get(Type::getVoidTy(Context), false)->getPointerTo();
     635             :       // FIXME: Reject the 2-field form in LLVM 4.0.
     636        2534 :       Assert(STy &&
     637             :                  (STy->getNumElements() == 2 || STy->getNumElements() == 3) &&
     638             :                  STy->getTypeAtIndex(0u)->isIntegerTy(32) &&
     639             :                  STy->getTypeAtIndex(1) == FuncPtrTy,
     640             :              "wrong type for intrinsic global variable", &GV);
     641        2531 :       if (STy->getNumElements() == 3) {
     642        2329 :         Type *ETy = STy->getTypeAtIndex(2);
     643        2330 :         Assert(ETy->isPointerTy() &&
     644             :                    cast<PointerType>(ETy)->getElementType()->isIntegerTy(8),
     645             :                "wrong type for intrinsic global variable", &GV);
     646             :       }
     647             :     }
     648             :   }
     649             : 
     650      154861 :   if (GV.hasName() && (GV.getName() == "llvm.used" ||
     651      147493 :                        GV.getName() == "llvm.compiler.used")) {
     652        2401 :     Assert(!GV.hasInitializer() || GV.hasAppendingLinkage(),
     653             :            "invalid linkage for intrinsic global variable", &GV);
     654        1202 :     Type *GVType = GV.getValueType();
     655             :     if (ArrayType *ATy = dyn_cast<ArrayType>(GVType)) {
     656        1201 :       PointerType *PTy = dyn_cast<PointerType>(ATy->getElementType());
     657           4 :       Assert(PTy, "wrong type for intrinsic global variable", &GV);
     658        1199 :       if (GV.hasInitializer()) {
     659        1196 :         const Constant *Init = GV.getInitializer();
     660             :         const ConstantArray *InitArray = dyn_cast<ConstantArray>(Init);
     661           4 :         Assert(InitArray, "wrong initalizer for intrinsic global variable",
     662             :                Init);
     663       20778 :         for (Value *Op : InitArray->operands()) {
     664        9195 :           Value *V = Op->stripPointerCastsNoFollowAliases();
     665        9198 :           Assert(isa<GlobalVariable>(V) || isa<Function>(V) ||
     666             :                      isa<GlobalAlias>(V),
     667             :                  "invalid llvm.used member", V);
     668        9194 :           Assert(V->hasName(), "members of llvm.used must be named", V);
     669             :         }
     670             :       }
     671             :     }
     672             :   }
     673             : 
     674             :   // Visit any debug info attachments.
     675             :   SmallVector<MDNode *, 1> MDs;
     676      154857 :   GV.getMetadata(LLVMContext::MD_dbg, MDs);
     677      161655 :   for (auto *MD : MDs) {
     678             :     if (auto *GVE = dyn_cast<DIGlobalVariableExpression>(MD))
     679        3399 :       visitDIGlobalVariableExpression(*GVE);
     680             :     else
     681           2 :       AssertDI(false, "!dbg attachment of global variable must be a "
     682             :                       "DIGlobalVariableExpression");
     683             :   }
     684             : 
     685      154856 :   if (!GV.hasInitializer()) {
     686       28798 :     visitGlobalValue(GV);
     687       28798 :     return;
     688             :   }
     689             : 
     690             :   // Walk any aggregate initializers looking for bitcasts between address spaces
     691      126058 :   visitConstantExprsRecursively(GV.getInitializer());
     692             : 
     693      126058 :   visitGlobalValue(GV);
     694             : }
     695             : 
     696        3008 : void Verifier::visitAliaseeSubExpr(const GlobalAlias &GA, const Constant &C) {
     697             :   SmallPtrSet<const GlobalAlias*, 4> Visited;
     698        3008 :   Visited.insert(&GA);
     699        3008 :   visitAliaseeSubExpr(Visited, GA, C);
     700        3008 : }
     701             : 
     702        6111 : void Verifier::visitAliaseeSubExpr(SmallPtrSetImpl<const GlobalAlias*> &Visited,
     703             :                                    const GlobalAlias &GA, const Constant &C) {
     704             :   if (const auto *GV = dyn_cast<GlobalValue>(&C)) {
     705        3043 :     Assert(!GV->isDeclarationForLinker(), "Alias must point to a definition",
     706             :            &GA);
     707             : 
     708             :     if (const auto *GA2 = dyn_cast<GlobalAlias>(GV)) {
     709          69 :       Assert(Visited.insert(GA2).second, "Aliases cannot form a cycle", &GA);
     710             : 
     711           2 :       Assert(!GA2->isInterposable(), "Alias cannot point to an interposable alias",
     712             :              &GA);
     713             :     } else {
     714             :       // Only continue verifying subexpressions of GlobalAliases.
     715             :       // Do not recurse into global initializers.
     716             :       return;
     717             :     }
     718             :   }
     719             : 
     720             :   if (const auto *CE = dyn_cast<ConstantExpr>(&C))
     721        1444 :     visitConstantExprsRecursively(CE);
     722             : 
     723       12476 :   for (const Use &U : C.operands()) {
     724        3103 :     Value *V = &*U;
     725             :     if (const auto *GA2 = dyn_cast<GlobalAlias>(V))
     726          72 :       visitAliaseeSubExpr(Visited, GA, *GA2->getAliasee());
     727             :     else if (const auto *C2 = dyn_cast<Constant>(V))
     728        3031 :       visitAliaseeSubExpr(Visited, GA, *C2);
     729             :   }
     730             : }
     731             : 
     732        3008 : void Verifier::visitGlobalAlias(const GlobalAlias &GA) {
     733           0 :   Assert(GlobalAlias::isValidLinkage(GA.getLinkage()),
     734             :          "Alias should have private, internal, linkonce, weak, linkonce_odr, "
     735             :          "weak_odr, or external linkage!",
     736             :          &GA);
     737             :   const Constant *Aliasee = GA.getAliasee();
     738           0 :   Assert(Aliasee, "Aliasee cannot be NULL!", &GA);
     739        3008 :   Assert(GA.getType() == Aliasee->getType(),
     740             :          "Alias and aliasee types should match!", &GA);
     741             : 
     742        1308 :   Assert(isa<GlobalValue>(Aliasee) || isa<ConstantExpr>(Aliasee),
     743             :          "Aliasee should be either GlobalValue or ConstantExpr", &GA);
     744             : 
     745        3008 :   visitAliaseeSubExpr(GA, *Aliasee);
     746             : 
     747        3008 :   visitGlobalValue(GA);
     748             : }
     749             : 
     750       38025 : void Verifier::visitNamedMDNode(const NamedMDNode &NMD) {
     751             :   // There used to be various other llvm.dbg.* nodes, but we don't support
     752             :   // upgrading them and we want to reserve the namespace for future uses.
     753       69329 :   if (NMD.getName().startswith("llvm.dbg."))
     754        6723 :     AssertDI(NMD.getName() == "llvm.dbg.cu",
     755             :              "unrecognized named metadata node in the llvm.dbg namespace",
     756             :              &NMD);
     757      164427 :   for (const MDNode *MD : NMD.operands()) {
     758       63205 :     if (NMD.getName() == "llvm.dbg.cu")
     759       16643 :       AssertDI(MD && isa<DICompileUnit>(MD), "invalid compile unit", &NMD, MD);
     760             : 
     761       63198 :     if (!MD)
     762           0 :       continue;
     763             : 
     764       63198 :     visitMDNode(*MD);
     765             :   }
     766             : }
     767             : 
     768      513230 : void Verifier::visitMDNode(const MDNode &MD) {
     769             :   // Only visit each node once.  Metadata can be mutually recursive, so this
     770             :   // avoids infinite recursion here, as well as being an optimization.
     771      513230 :   if (!MDNodes.insert(&MD).second)
     772             :     return;
     773             : 
     774      498090 :   switch (MD.getMetadataID()) {
     775           0 :   default:
     776           0 :     llvm_unreachable("Invalid MDNode subclass");
     777             :   case Metadata::MDTupleKind:
     778             :     break;
     779             : #define HANDLE_SPECIALIZED_MDNODE_LEAF(CLASS)                                  \
     780             :   case Metadata::CLASS##Kind:                                                  \
     781             :     visit##CLASS(cast<CLASS>(MD));                                             \
     782             :     break;
     783             : #include "llvm/IR/Metadata.def"
     784             :   }
     785             : 
     786     2638149 :   for (const Metadata *Op : MD.operands()) {
     787      796368 :     if (!Op)
     788      210593 :       continue;
     789      585775 :     Assert(!isa<LocalAsMetadata>(Op), "Invalid operand for global metadata!",
     790             :            &MD, Op);
     791      308004 :     if (auto *N = dyn_cast<MDNode>(Op)) {
     792      308004 :       visitMDNode(*N);
     793      308004 :       continue;
     794             :     }
     795      106247 :     if (auto *V = dyn_cast<ValueAsMetadata>(Op)) {
     796      106247 :       visitValueAsMetadata(*V, nullptr);
     797      106247 :       continue;
     798             :     }
     799             :   }
     800             : 
     801             :   // Check these last, so we diagnose problems in operands first.
     802      249045 :   Assert(!MD.isTemporary(), "Expected no forward declarations!", &MD);
     803           0 :   Assert(MD.isResolved(), "All nodes should be resolved!", &MD);
     804             : }
     805             : 
     806      119374 : void Verifier::visitValueAsMetadata(const ValueAsMetadata &MD, Function *F) {
     807      226644 :   Assert(MD.getValue(), "Expected valid value", &MD);
     808      238748 :   Assert(!MD.getValue()->getType()->isMetadataTy(),
     809             :          "Unexpected metadata round-trip through values", &MD, MD.getValue());
     810             : 
     811      119374 :   auto *L = dyn_cast<LocalAsMetadata>(&MD);
     812      119374 :   if (!L)
     813             :     return;
     814             : 
     815       12104 :   Assert(F, "function-local metadata used outside a function", L);
     816             : 
     817             :   // If this was an instruction, bb, or argument, verify that it is in the
     818             :   // function that we expect.
     819             :   Function *ActualF = nullptr;
     820       24208 :   if (Instruction *I = dyn_cast<Instruction>(L->getValue())) {
     821       10348 :     Assert(I->getParent(), "function-local metadata not in basic block", L, I);
     822       10348 :     ActualF = I->getParent()->getParent();
     823             :   } else if (BasicBlock *BB = dyn_cast<BasicBlock>(L->getValue()))
     824           0 :     ActualF = BB->getParent();
     825             :   else if (Argument *A = dyn_cast<Argument>(L->getValue()))
     826        1756 :     ActualF = A->getParent();
     827             :   assert(ActualF && "Unimplemented function local metadata case!");
     828             : 
     829       12104 :   Assert(ActualF == F, "function-local metadata used in wrong function", L);
     830             : }
     831             : 
     832       45791 : void Verifier::visitMetadataAsValue(const MetadataAsValue &MDV, Function *F) {
     833       45791 :   Metadata *MD = MDV.getMetadata();
     834             :   if (auto *N = dyn_cast<MDNode>(MD)) {
     835       30461 :     visitMDNode(*N);
     836       30461 :     return;
     837             :   }
     838             : 
     839             :   // Only visit each node once.  Metadata can be mutually recursive, so this
     840             :   // avoids infinite recursion here, as well as being an optimization.
     841       15330 :   if (!MDNodes.insert(MD).second)
     842             :     return;
     843             : 
     844             :   if (auto *V = dyn_cast<ValueAsMetadata>(MD))
     845       13127 :     visitValueAsMetadata(*V, F);
     846             : }
     847             : 
     848       62890 : static bool isType(const Metadata *MD) { return !MD || isa<DIType>(MD); }
     849       31107 : static bool isScope(const Metadata *MD) { return !MD || isa<DIScope>(MD); }
     850        1103 : static bool isDINode(const Metadata *MD) { return !MD || isa<DINode>(MD); }
     851             : 
     852       40838 : void Verifier::visitDILocation(const DILocation &N) {
     853       40838 :   AssertDI(N.getRawScope() && isa<DILocalScope>(N.getRawScope()),
     854             :            "location requires a valid scope", &N, N.getRawScope());
     855       40838 :   if (auto *IA = N.getRawInlinedAt())
     856        2021 :     AssertDI(isa<DILocation>(IA), "inlined-at should be a location", &N, IA);
     857             :   if (auto *SP = dyn_cast<DISubprogram>(N.getRawScope()))
     858       29703 :     AssertDI(SP->isDefinition(), "scope points into the type hierarchy", &N);
     859             : }
     860             : 
     861          52 : void Verifier::visitGenericDINode(const GenericDINode &N) {
     862          52 :   AssertDI(N.getTag(), "invalid tag", &N);
     863             : }
     864             : 
     865       17146 : void Verifier::visitDIScope(const DIScope &N) {
     866       17146 :   if (auto *F = N.getRawFile())
     867        9947 :     AssertDI(isa<DIFile>(F), "invalid file", &N, F);
     868             : }
     869             : 
     870         767 : void Verifier::visitDISubrange(const DISubrange &N) {
     871         767 :   AssertDI(N.getTag() == dwarf::DW_TAG_subrange_type, "invalid tag", &N);
     872         767 :   auto Count = N.getCount();
     873         768 :   AssertDI(Count, "Count must either be a signed constant or a DIVariable",
     874             :            &N);
     875        1457 :   AssertDI(!Count.is<ConstantInt*>() ||
     876             :                Count.get<ConstantInt*>()->getSExtValue() >= -1,
     877             :            "invalid subrange count", &N);
     878             : }
     879             : 
     880       24650 : void Verifier::visitDIEnumerator(const DIEnumerator &N) {
     881       24650 :   AssertDI(N.getTag() == dwarf::DW_TAG_enumerator, "invalid tag", &N);
     882             : }
     883             : 
     884        5951 : void Verifier::visitDIBasicType(const DIBasicType &N) {
     885       11902 :   AssertDI(N.getTag() == dwarf::DW_TAG_base_type ||
     886             :                N.getTag() == dwarf::DW_TAG_unspecified_type,
     887             :            "invalid tag", &N);
     888             : }
     889             : 
     890       11585 : void Verifier::visitDIDerivedType(const DIDerivedType &N) {
     891             :   // Common scope checks.
     892       11585 :   visitDIScope(N);
     893             : 
     894       23170 :   AssertDI(N.getTag() == dwarf::DW_TAG_typedef ||
     895             :                N.getTag() == dwarf::DW_TAG_pointer_type ||
     896             :                N.getTag() == dwarf::DW_TAG_ptr_to_member_type ||
     897             :                N.getTag() == dwarf::DW_TAG_reference_type ||
     898             :                N.getTag() == dwarf::DW_TAG_rvalue_reference_type ||
     899             :                N.getTag() == dwarf::DW_TAG_const_type ||
     900             :                N.getTag() == dwarf::DW_TAG_volatile_type ||
     901             :                N.getTag() == dwarf::DW_TAG_restrict_type ||
     902             :                N.getTag() == dwarf::DW_TAG_atomic_type ||
     903             :                N.getTag() == dwarf::DW_TAG_member ||
     904             :                N.getTag() == dwarf::DW_TAG_inheritance ||
     905             :                N.getTag() == dwarf::DW_TAG_friend,
     906             :            "invalid tag", &N);
     907       11585 :   if (N.getTag() == dwarf::DW_TAG_ptr_to_member_type) {
     908           0 :     AssertDI(isType(N.getRawExtraData()), "invalid pointer to member type", &N,
     909             :              N.getRawExtraData());
     910             :   }
     911             : 
     912           0 :   AssertDI(isScope(N.getRawScope()), "invalid scope", &N, N.getRawScope());
     913           8 :   AssertDI(isType(N.getRawBaseType()), "invalid base type", &N,
     914             :            N.getRawBaseType());
     915             : 
     916       11581 :   if (N.getDWARFAddressSpace()) {
     917          50 :     AssertDI(N.getTag() == dwarf::DW_TAG_pointer_type ||
     918             :                  N.getTag() == dwarf::DW_TAG_reference_type,
     919             :              "DWARF address space only applies to pointer or reference types",
     920             :              &N);
     921             :   }
     922             : }
     923             : 
     924             : /// Detect mutually exclusive flags.
     925             : static bool hasConflictingReferenceFlags(unsigned Flags) {
     926       28075 :   return ((Flags & DINode::FlagLValueReference) &&
     927       56150 :           (Flags & DINode::FlagRValueReference)) ||
     928       28075 :          ((Flags & DINode::FlagTypePassByValue) &&
     929             :           (Flags & DINode::FlagTypePassByReference));
     930             : }
     931             : 
     932        1081 : void Verifier::visitTemplateParams(const MDNode &N, const Metadata &RawParams) {
     933        1081 :   auto *Params = dyn_cast<MDTuple>(&RawParams);
     934        1084 :   AssertDI(Params, "invalid template params", &N, &RawParams);
     935        5389 :   for (Metadata *Op : Params->operands()) {
     936        1079 :     AssertDI(Op && isa<DITemplateParameter>(Op), "invalid template parameter",
     937             :              &N, Params, Op);
     938             :   }
     939             : }
     940             : 
     941        5561 : void Verifier::visitDICompositeType(const DICompositeType &N) {
     942             :   // Common scope checks.
     943        5561 :   visitDIScope(N);
     944             : 
     945       11122 :   AssertDI(N.getTag() == dwarf::DW_TAG_array_type ||
     946             :                N.getTag() == dwarf::DW_TAG_structure_type ||
     947             :                N.getTag() == dwarf::DW_TAG_union_type ||
     948             :                N.getTag() == dwarf::DW_TAG_enumeration_type ||
     949             :                N.getTag() == dwarf::DW_TAG_class_type ||
     950             :                N.getTag() == dwarf::DW_TAG_variant_part,
     951             :            "invalid tag", &N);
     952             : 
     953           0 :   AssertDI(isScope(N.getRawScope()), "invalid scope", &N, N.getRawScope());
     954           0 :   AssertDI(isType(N.getRawBaseType()), "invalid base type", &N,
     955             :            N.getRawBaseType());
     956             : 
     957       10104 :   AssertDI(!N.getRawElements() || isa<MDTuple>(N.getRawElements()),
     958             :            "invalid composite elements", &N, N.getRawElements());
     959           0 :   AssertDI(isType(N.getRawVTableHolder()), "invalid vtable holder", &N,
     960             :            N.getRawVTableHolder());
     961        5563 :   AssertDI(!hasConflictingReferenceFlags(N.getFlags()),
     962             :            "invalid reference flags", &N);
     963             : 
     964        5560 :   if (N.isVector()) {
     965             :     const DINodeArray Elements = N.getElements();
     966          80 :     AssertDI(Elements.size() == 1 &&
     967             :              Elements[0]->getTag() == dwarf::DW_TAG_subrange_type,
     968             :              "invalid vector, expected one element of type subrange", &N);
     969             :   }
     970             : 
     971        5559 :   if (auto *Params = N.getRawTemplateParams())
     972         505 :     visitTemplateParams(N, *Params);
     973             : 
     974       11118 :   if (N.getTag() == dwarf::DW_TAG_class_type ||
     975             :       N.getTag() == dwarf::DW_TAG_union_type) {
     976        1052 :     AssertDI(N.getFile() && !N.getFile()->getFilename().empty(),
     977             :              "class/union requires a filename", &N, N.getFile());
     978             :   }
     979             : 
     980        5559 :   if (auto *D = N.getRawDiscriminator()) {
     981          15 :     AssertDI(isa<DIDerivedType>(D) && N.getTag() == dwarf::DW_TAG_variant_part,
     982             :              "discriminator can only appear on variant part");
     983             :   }
     984             : }
     985             : 
     986        8559 : void Verifier::visitDISubroutineType(const DISubroutineType &N) {
     987        8559 :   AssertDI(N.getTag() == dwarf::DW_TAG_subroutine_type, "invalid tag", &N);
     988        8559 :   if (auto *Types = N.getRawTypeArray()) {
     989        8488 :     AssertDI(isa<MDTuple>(Types), "invalid composite elements", &N, Types);
     990       61133 :     for (Metadata *Ty : N.getTypeArray()->operands()) {
     991           0 :       AssertDI(isType(Ty), "invalid subroutine type ref", &N, Types, Ty);
     992             :     }
     993             :   }
     994        8559 :   AssertDI(!hasConflictingReferenceFlags(N.getFlags()),
     995             :            "invalid reference flags", &N);
     996             : }
     997             : 
     998        9033 : void Verifier::visitDIFile(const DIFile &N) {
     999        9035 :   AssertDI(N.getTag() == dwarf::DW_TAG_file_type, "invalid tag", &N);
    1000             :   Optional<DIFile::ChecksumInfo<StringRef>> Checksum = N.getChecksum();
    1001        9033 :   if (Checksum) {
    1002         571 :     AssertDI(Checksum->Kind <= DIFile::ChecksumKind::CSK_Last,
    1003             :              "invalid checksum kind", &N);
    1004             :     size_t Size;
    1005         571 :     switch (Checksum->Kind) {
    1006         548 :     case DIFile::CSK_MD5:
    1007             :       Size = 32;
    1008         548 :       break;
    1009          23 :     case DIFile::CSK_SHA1:
    1010             :       Size = 40;
    1011          23 :       break;
    1012             :     }
    1013         572 :     AssertDI(Checksum->Value.size() == Size, "invalid checksum length", &N);
    1014         571 :     AssertDI(Checksum->Value.find_if_not(llvm::isHexDigit) == StringRef::npos,
    1015             :              "invalid checksum", &N);
    1016             :   }
    1017             : }
    1018             : 
    1019        8373 : void Verifier::visitDICompileUnit(const DICompileUnit &N) {
    1020        8373 :   AssertDI(N.isDistinct(), "compile units must be distinct", &N);
    1021        8373 :   AssertDI(N.getTag() == dwarf::DW_TAG_compile_unit, "invalid tag", &N);
    1022             : 
    1023             :   // Don't bother verifying the compilation directory or producer string
    1024             :   // as those could be empty.
    1025       16746 :   AssertDI(N.getRawFile() && isa<DIFile>(N.getRawFile()), "invalid file", &N,
    1026             :            N.getRawFile());
    1027        8373 :   AssertDI(!N.getFile()->getFilename().empty(), "invalid filename", &N,
    1028             :            N.getFile());
    1029             : 
    1030        8373 :   AssertDI((N.getEmissionKind() <= DICompileUnit::LastEmissionKind),
    1031             :            "invalid emission kind", &N);
    1032             : 
    1033        8373 :   if (auto *Array = N.getRawEnumTypes()) {
    1034        6816 :     AssertDI(isa<MDTuple>(Array), "invalid enum list", &N, Array);
    1035       14916 :     for (Metadata *Op : N.getEnumTypes()->operands()) {
    1036             :       auto *Enum = dyn_cast_or_null<DICompositeType>(Op);
    1037         428 :       AssertDI(Enum && Enum->getTag() == dwarf::DW_TAG_enumeration_type,
    1038             :                "invalid enum type", &N, N.getEnumTypes(), Op);
    1039             :     }
    1040             :   }
    1041        8373 :   if (auto *Array = N.getRawRetainedTypes()) {
    1042        2864 :     AssertDI(isa<MDTuple>(Array), "invalid retained type list", &N, Array);
    1043       10449 :     for (Metadata *Op : N.getRetainedTypes()->operands()) {
    1044        1764 :       AssertDI(Op && (isa<DIType>(Op) ||
    1045             :                       (isa<DISubprogram>(Op) &&
    1046             :                        !cast<DISubprogram>(Op)->isDefinition())),
    1047             :                "invalid retained type", &N, Op);
    1048             :     }
    1049             :   }
    1050        8371 :   if (auto *Array = N.getRawGlobalVariables()) {
    1051        4129 :     AssertDI(isa<MDTuple>(Array), "invalid global variable list", &N, Array);
    1052       20374 :     for (Metadata *Op : N.getGlobalVariables()->operands()) {
    1053        8082 :       AssertDI(Op && (isa<DIGlobalVariableExpression>(Op)),
    1054             :                "invalid global variable ref", &N, Op);
    1055             :     }
    1056             :   }
    1057        8370 :   if (auto *Array = N.getRawImportedEntities()) {
    1058        2102 :     AssertDI(isa<MDTuple>(Array), "invalid imported entity list", &N, Array);
    1059        7315 :     for (Metadata *Op : N.getImportedEntities()->operands()) {
    1060        2074 :       AssertDI(Op && isa<DIImportedEntity>(Op), "invalid imported entity ref",
    1061             :                &N, Op);
    1062             :     }
    1063             :   }
    1064        8370 :   if (auto *Array = N.getRawMacros()) {
    1065          77 :     AssertDI(isa<MDTuple>(Array), "invalid macro list", &N, Array);
    1066        3415 :     for (Metadata *Op : N.getMacros()->operands()) {
    1067        1087 :       AssertDI(Op && isa<DIMacroNode>(Op), "invalid macro ref", &N, Op);
    1068             :     }
    1069             :   }
    1070        8370 :   CUVisited.insert(&N);
    1071             : }
    1072             : 
    1073       13961 : void Verifier::visitDISubprogram(const DISubprogram &N) {
    1074       13980 :   AssertDI(N.getTag() == dwarf::DW_TAG_subprogram, "invalid tag", &N);
    1075           0 :   AssertDI(isScope(N.getRawScope()), "invalid scope", &N, N.getRawScope());
    1076       13961 :   if (auto *F = N.getRawFile())
    1077       13274 :     AssertDI(isa<DIFile>(F), "invalid file", &N, F);
    1078             :   else
    1079         695 :     AssertDI(N.getLine() == 0, "line specified with no file", &N, N.getLine());
    1080       13957 :   if (auto *T = N.getRawType())
    1081       13298 :     AssertDI(isa<DISubroutineType>(T), "invalid subroutine type", &N, T);
    1082           0 :   AssertDI(isType(N.getRawContainingType()), "invalid containing type", &N,
    1083             :            N.getRawContainingType());
    1084             :   if (auto *Params = N.getRawTemplateParams())
    1085         576 :     visitTemplateParams(N, *Params);
    1086       13955 :   if (auto *S = N.getRawDeclaration())
    1087        3098 :     AssertDI(isa<DISubprogram>(S) && !cast<DISubprogram>(S)->isDefinition(),
    1088             :              "invalid subprogram declaration", &N, S);
    1089       13955 :   if (auto *RawNode = N.getRawRetainedNodes()) {
    1090        9533 :     auto *Node = dyn_cast<MDTuple>(RawNode);
    1091        9533 :     AssertDI(Node, "invalid retained nodes list", &N, RawNode);
    1092       33538 :     for (Metadata *Op : Node->operands()) {
    1093        9648 :       AssertDI(Op && (isa<DILocalVariable>(Op) || isa<DILabel>(Op)),
    1094             :                "invalid retained nodes, expected DILocalVariable or DILabel",
    1095             :                &N, Node, Op);
    1096             :     }
    1097             :   }
    1098       13955 :   AssertDI(!hasConflictingReferenceFlags(N.getFlags()),
    1099             :            "invalid reference flags", &N);
    1100             : 
    1101       13955 :   auto *Unit = N.getRawUnit();
    1102       13955 :   if (N.isDefinition()) {
    1103             :     // Subprogram definitions (not part of the type hierarchy).
    1104       10797 :     AssertDI(N.isDistinct(), "subprogram definitions must be distinct", &N);
    1105       10809 :     AssertDI(Unit, "subprogram definitions must have a compile unit", &N);
    1106       10785 :     AssertDI(isa<DICompileUnit>(Unit), "invalid unit type", &N, Unit);
    1107             :   } else {
    1108             :     // Subprogram declarations (part of the type hierarchy).
    1109        3158 :     AssertDI(!Unit, "subprogram declarations must not have a compile unit", &N);
    1110             :   }
    1111             : 
    1112       13943 :   if (auto *RawThrownTypes = N.getRawThrownTypes()) {
    1113          32 :     auto *ThrownTypes = dyn_cast<MDTuple>(RawThrownTypes);
    1114          33 :     AssertDI(ThrownTypes, "invalid thrown types list", &N, RawThrownTypes);
    1115         170 :     for (Metadata *Op : ThrownTypes->operands())
    1116          38 :       AssertDI(Op && isa<DIType>(Op), "invalid thrown type", &N, ThrownTypes,
    1117             :                Op);
    1118             :   }
    1119             : }
    1120             : 
    1121        5372 : void Verifier::visitDILexicalBlockBase(const DILexicalBlockBase &N) {
    1122        5372 :   AssertDI(N.getTag() == dwarf::DW_TAG_lexical_block, "invalid tag", &N);
    1123        5372 :   AssertDI(N.getRawScope() && isa<DILocalScope>(N.getRawScope()),
    1124             :            "invalid local scope", &N, N.getRawScope());
    1125             :   if (auto *SP = dyn_cast<DISubprogram>(N.getRawScope()))
    1126        2884 :     AssertDI(SP->isDefinition(), "scope points into the type hierarchy", &N);
    1127             : }
    1128             : 
    1129        4337 : void Verifier::visitDILexicalBlock(const DILexicalBlock &N) {
    1130        4337 :   visitDILexicalBlockBase(N);
    1131             : 
    1132        4337 :   AssertDI(N.getLine() || !N.getColumn(),
    1133             :            "cannot have column info without line info", &N);
    1134             : }
    1135             : 
    1136             : void Verifier::visitDILexicalBlockFile(const DILexicalBlockFile &N) {
    1137        1035 :   visitDILexicalBlockBase(N);
    1138             : }
    1139             : 
    1140         512 : void Verifier::visitDINamespace(const DINamespace &N) {
    1141         512 :   AssertDI(N.getTag() == dwarf::DW_TAG_namespace, "invalid tag", &N);
    1142         512 :   if (auto *S = N.getRawScope())
    1143           0 :     AssertDI(isa<DIScope>(S), "invalid scope ref", &N, S);
    1144             : }
    1145             : 
    1146        1130 : void Verifier::visitDIMacro(const DIMacro &N) {
    1147        2260 :   AssertDI(N.getMacinfoType() == dwarf::DW_MACINFO_define ||
    1148             :                N.getMacinfoType() == dwarf::DW_MACINFO_undef,
    1149             :            "invalid macinfo type", &N);
    1150        1130 :   AssertDI(!N.getName().empty(), "anonymous macro", &N);
    1151             :   if (!N.getValue().empty()) {
    1152             :     assert(N.getValue().data()[0] != ' ' && "Macro value has a space prefix");
    1153             :   }
    1154             : }
    1155             : 
    1156          94 : void Verifier::visitDIMacroFile(const DIMacroFile &N) {
    1157          94 :   AssertDI(N.getMacinfoType() == dwarf::DW_MACINFO_start_file,
    1158             :            "invalid macinfo type", &N);
    1159          94 :   if (auto *F = N.getRawFile())
    1160          94 :     AssertDI(isa<DIFile>(F), "invalid file", &N, F);
    1161             : 
    1162          94 :   if (auto *Array = N.getRawElements()) {
    1163          80 :     AssertDI(isa<MDTuple>(Array), "invalid macro list", &N, Array);
    1164         514 :     for (Metadata *Op : N.getElements()->operands()) {
    1165         118 :       AssertDI(Op && isa<DIMacroNode>(Op), "invalid macro ref", &N, Op);
    1166             :     }
    1167             :   }
    1168             : }
    1169             : 
    1170         162 : void Verifier::visitDIModule(const DIModule &N) {
    1171         162 :   AssertDI(N.getTag() == dwarf::DW_TAG_module, "invalid tag", &N);
    1172         162 :   AssertDI(!N.getName().empty(), "anonymous module", &N);
    1173             : }
    1174             : 
    1175         859 : void Verifier::visitDITemplateParameter(const DITemplateParameter &N) {
    1176           0 :   AssertDI(isType(N.getRawType()), "invalid type ref", &N, N.getRawType());
    1177             : }
    1178             : 
    1179         412 : void Verifier::visitDITemplateTypeParameter(const DITemplateTypeParameter &N) {
    1180         412 :   visitDITemplateParameter(N);
    1181             : 
    1182         412 :   AssertDI(N.getTag() == dwarf::DW_TAG_template_type_parameter, "invalid tag",
    1183             :            &N);
    1184             : }
    1185             : 
    1186         447 : void Verifier::visitDITemplateValueParameter(
    1187             :     const DITemplateValueParameter &N) {
    1188         447 :   visitDITemplateParameter(N);
    1189             : 
    1190         894 :   AssertDI(N.getTag() == dwarf::DW_TAG_template_value_parameter ||
    1191             :                N.getTag() == dwarf::DW_TAG_GNU_template_template_param ||
    1192             :                N.getTag() == dwarf::DW_TAG_GNU_template_parameter_pack,
    1193             :            "invalid tag", &N);
    1194             : }
    1195             : 
    1196       24452 : void Verifier::visitDIVariable(const DIVariable &N) {
    1197       24452 :   if (auto *S = N.getRawScope())
    1198           0 :     AssertDI(isa<DIScope>(S), "invalid scope", &N, S);
    1199       24452 :   if (auto *F = N.getRawFile())
    1200       21532 :     AssertDI(isa<DIFile>(F), "invalid file", &N, F);
    1201             : }
    1202             : 
    1203       11533 : void Verifier::visitDIGlobalVariable(const DIGlobalVariable &N) {
    1204             :   // Checks common to all variables.
    1205       11533 :   visitDIVariable(N);
    1206             : 
    1207       11533 :   AssertDI(N.getTag() == dwarf::DW_TAG_variable, "invalid tag", &N);
    1208       11533 :   AssertDI(!N.getName().empty(), "missing global variable name", &N);
    1209          12 :   AssertDI(isType(N.getRawType()), "invalid type ref", &N, N.getRawType());
    1210       11529 :   AssertDI(N.getType(), "missing global variable type", &N);
    1211       11525 :   if (auto *Member = N.getRawStaticDataMemberDeclaration()) {
    1212         330 :     AssertDI(isa<DIDerivedType>(Member),
    1213             :              "invalid static data member declaration", &N, Member);
    1214             :   }
    1215             : }
    1216             : 
    1217       12919 : void Verifier::visitDILocalVariable(const DILocalVariable &N) {
    1218             :   // Checks common to all variables.
    1219       12919 :   visitDIVariable(N);
    1220             : 
    1221           0 :   AssertDI(isType(N.getRawType()), "invalid type ref", &N, N.getRawType());
    1222       12919 :   AssertDI(N.getTag() == dwarf::DW_TAG_variable, "invalid tag", &N);
    1223       12919 :   AssertDI(N.getRawScope() && isa<DILocalScope>(N.getRawScope()),
    1224             :            "local variable requires a valid scope", &N, N.getRawScope());
    1225             : }
    1226             : 
    1227          57 : void Verifier::visitDILabel(const DILabel &N) {
    1228          57 :   if (auto *S = N.getRawScope())
    1229           0 :     AssertDI(isa<DIScope>(S), "invalid scope", &N, S);
    1230          57 :   if (auto *F = N.getRawFile())
    1231          57 :     AssertDI(isa<DIFile>(F), "invalid file", &N, F);
    1232             : 
    1233          57 :   AssertDI(N.getTag() == dwarf::DW_TAG_label, "invalid tag", &N);
    1234          57 :   AssertDI(N.getRawScope() && isa<DILocalScope>(N.getRawScope()),
    1235             :            "label requires a valid scope", &N, N.getRawScope());
    1236             : }
    1237             : 
    1238       12003 : void Verifier::visitDIExpression(const DIExpression &N) {
    1239       12006 :   AssertDI(N.isValid(), "invalid expression", &N);
    1240             : }
    1241             : 
    1242        7452 : void Verifier::visitDIGlobalVariableExpression(
    1243             :     const DIGlobalVariableExpression &GVE) {
    1244           0 :   AssertDI(GVE.getVariable(), "missing variable");
    1245             :   if (auto *Var = GVE.getVariable())
    1246        7452 :     visitDIGlobalVariable(*Var);
    1247        7452 :   if (auto *Expr = GVE.getExpression()) {
    1248        7452 :     visitDIExpression(*Expr);
    1249        7452 :     if (auto Fragment = Expr->getFragmentInfo())
    1250          82 :       verifyFragmentExpression(*GVE.getVariable(), *Fragment, &GVE);
    1251             :   }
    1252             : }
    1253             : 
    1254         106 : void Verifier::visitDIObjCProperty(const DIObjCProperty &N) {
    1255         106 :   AssertDI(N.getTag() == dwarf::DW_TAG_APPLE_property, "invalid tag", &N);
    1256         106 :   if (auto *T = N.getRawType())
    1257           0 :     AssertDI(isType(T), "invalid type ref", &N, T);
    1258         106 :   if (auto *F = N.getRawFile())
    1259          80 :     AssertDI(isa<DIFile>(F), "invalid file", &N, F);
    1260             : }
    1261             : 
    1262        1103 : void Verifier::visitDIImportedEntity(const DIImportedEntity &N) {
    1263        2206 :   AssertDI(N.getTag() == dwarf::DW_TAG_imported_module ||
    1264             :                N.getTag() == dwarf::DW_TAG_imported_declaration,
    1265             :            "invalid tag", &N);
    1266        1103 :   if (auto *S = N.getRawScope())
    1267           0 :     AssertDI(isa<DIScope>(S), "invalid scope for imported entity", &N, S);
    1268           0 :   AssertDI(isDINode(N.getRawEntity()), "invalid imported entity", &N,
    1269             :            N.getRawEntity());
    1270             : }
    1271             : 
    1272       27320 : void Verifier::visitComdat(const Comdat &C) {
    1273             :   // The Module is invalid if the GlobalValue has private linkage.  Entities
    1274             :   // with private linkage don't have entries in the symbol table.
    1275       27320 :   if (const GlobalValue *GV = M.getNamedValue(C.getName()))
    1276       27078 :     Assert(!GV->hasPrivateLinkage(), "comdat global value has private linkage",
    1277             :            GV);
    1278             : }
    1279             : 
    1280       95463 : void Verifier::visitModuleIdents(const Module &M) {
    1281       95463 :   const NamedMDNode *Idents = M.getNamedMetadata("llvm.ident");
    1282       95463 :   if (!Idents)
    1283             :     return;
    1284             : 
    1285             :   // llvm.ident takes a list of metadata entry. Each entry has only one string.
    1286             :   // Scan each llvm.ident entry and make sure that this requirement is met.
    1287       38774 :   for (const MDNode *N : Idents->operands()) {
    1288       13119 :     Assert(N->getNumOperands() == 1,
    1289             :            "incorrect number of operands in llvm.ident metadata", N);
    1290           6 :     Assert(dyn_cast_or_null<MDString>(N->getOperand(0)),
    1291             :            ("invalid value for llvm.ident metadata entry operand"
    1292             :             "(the operand should be a string)"),
    1293             :            N->getOperand(0));
    1294             :   }
    1295             : }
    1296             : 
    1297       95463 : void Verifier::visitModuleFlags(const Module &M) {
    1298       95463 :   const NamedMDNode *Flags = M.getModuleFlagsMetadata();
    1299      175384 :   if (!Flags) return;
    1300             : 
    1301             :   // Scan each flag, and track the flags and requirements.
    1302             :   DenseMap<const MDString*, const MDNode*> SeenIDs;
    1303             :   SmallVector<const MDNode*, 16> Requirements;
    1304       45074 :   for (const MDNode *MDN : Flags->operands())
    1305       29532 :     visitModuleFlag(MDN, SeenIDs, Requirements);
    1306             : 
    1307             :   // Validate that the requirements in the module are valid.
    1308       15574 :   for (const MDNode *Requirement : Requirements) {
    1309          16 :     const MDString *Flag = cast<MDString>(Requirement->getOperand(0));
    1310             :     const Metadata *ReqValue = Requirement->getOperand(1);
    1311             : 
    1312             :     const MDNode *Op = SeenIDs.lookup(Flag);
    1313          16 :     if (!Op) {
    1314           2 :       CheckFailed("invalid requirement on flag, flag is not present in module",
    1315             :                   Flag);
    1316           3 :       continue;
    1317             :     }
    1318             : 
    1319          16 :     if (Op->getOperand(2) != ReqValue) {
    1320           2 :       CheckFailed(("invalid requirement on flag, "
    1321             :                    "flag does not have the required value"),
    1322             :                   Flag);
    1323           1 :       continue;
    1324             :     }
    1325             :   }
    1326             : }
    1327             : 
    1328             : void
    1329       29532 : Verifier::visitModuleFlag(const MDNode *Op,
    1330             :                           DenseMap<const MDString *, const MDNode *> &SeenIDs,
    1331             :                           SmallVectorImpl<const MDNode *> &Requirements) {
    1332             :   // Each module flag should have three arguments, the merge behavior (a
    1333             :   // constant int), the flag ID (an MDString), and the value.
    1334       29547 :   Assert(Op->getNumOperands() == 3,
    1335             :          "incorrect number of operands in module flag", Op);
    1336             :   Module::ModFlagBehavior MFB;
    1337       29531 :   if (!Module::isValidModFlagBehavior(Op->getOperand(0), MFB)) {
    1338           7 :     Assert(
    1339             :         mdconst::dyn_extract_or_null<ConstantInt>(Op->getOperand(0)),
    1340             :         "invalid behavior operand in module flag (expected constant integer)",
    1341             :         Op->getOperand(0));
    1342           2 :     Assert(false,
    1343             :            "invalid behavior operand in module flag (unexpected constant)",
    1344             :            Op->getOperand(0));
    1345             :   }
    1346       59056 :   MDString *ID = dyn_cast_or_null<MDString>(Op->getOperand(1));
    1347       29530 :   Assert(ID, "invalid ID operand in module flag (expected metadata string)",
    1348             :          Op->getOperand(1));
    1349             : 
    1350             :   // Sanity check the values for behaviors with additional requirements.
    1351       29526 :   switch (MFB) {
    1352             :   case Module::Error:
    1353             :   case Module::Warning:
    1354             :   case Module::Override:
    1355             :     // These behavior types accept any value.
    1356             :     break;
    1357             : 
    1358        1234 :   case Module::Max: {
    1359           2 :     Assert(mdconst::dyn_extract_or_null<ConstantInt>(Op->getOperand(2)),
    1360             :            "invalid value for 'max' module flag (expected constant integer)",
    1361             :            Op->getOperand(2));
    1362             :     break;
    1363             :   }
    1364             : 
    1365          19 :   case Module::Require: {
    1366             :     // The value should itself be an MDNode with two operands, a flag ID (an
    1367             :     // MDString), and a value.
    1368             :     MDNode *Value = dyn_cast<MDNode>(Op->getOperand(2));
    1369          22 :     Assert(Value && Value->getNumOperands() == 2,
    1370             :            "invalid value for 'require' module flag (expected metadata pair)",
    1371             :            Op->getOperand(2));
    1372          19 :     Assert(isa<MDString>(Value->getOperand(0)),
    1373             :            ("invalid value for 'require' module flag "
    1374             :             "(first value operand should be a string)"),
    1375             :            Value->getOperand(0));
    1376             : 
    1377             :     // Append it to the list of requirements, to check once all module flags are
    1378             :     // scanned.
    1379          16 :     Requirements.push_back(Value);
    1380          16 :     break;
    1381             :   }
    1382             : 
    1383          56 :   case Module::Append:
    1384             :   case Module::AppendUnique: {
    1385             :     // These behavior types require the operand be an MDNode.
    1386           4 :     Assert(isa<MDNode>(Op->getOperand(2)),
    1387             :            "invalid value for 'append'-type module flag "
    1388             :            "(expected a metadata node)",
    1389             :            Op->getOperand(2));
    1390             :     break;
    1391             :   }
    1392             :   }
    1393             : 
    1394             :   // Unless this is a "requires" flag, check the ID is unique.
    1395       29520 :   if (MFB != Module::Require) {
    1396       59008 :     bool Inserted = SeenIDs.insert(std::make_pair(ID, Op)).second;
    1397       29505 :     Assert(Inserted,
    1398             :            "module flag identifiers must be unique (or of 'require' type)", ID);
    1399             :   }
    1400             : 
    1401       29519 :   if (ID->getString() == "wchar_size") {
    1402             :     ConstantInt *Value
    1403        9505 :       = mdconst::dyn_extract_or_null<ConstantInt>(Op->getOperand(2));
    1404           0 :     Assert(Value, "wchar_size metadata requires constant integer argument");
    1405             :   }
    1406             : 
    1407       29519 :   if (ID->getString() == "Linker Options") {
    1408             :     // If the llvm.linker.options named metadata exists, we assume that the
    1409             :     // bitcode reader has upgraded the module flag. Otherwise the flag might
    1410             :     // have been created by a client directly.
    1411          19 :     Assert(M.getNamedMetadata("llvm.linker.options"),
    1412             :            "'Linker Options' named metadata no longer supported");
    1413             :   }
    1414             : }
    1415             : 
    1416             : /// Return true if this attribute kind only applies to functions.
    1417             : static bool isFuncOnlyAttr(Attribute::AttrKind Kind) {
    1418             :   switch (Kind) {
    1419             :   case Attribute::NoReturn:
    1420             :   case Attribute::NoCfCheck:
    1421             :   case Attribute::NoUnwind:
    1422             :   case Attribute::NoInline:
    1423             :   case Attribute::AlwaysInline:
    1424             :   case Attribute::OptimizeForSize:
    1425             :   case Attribute::StackProtect:
    1426             :   case Attribute::StackProtectReq:
    1427             :   case Attribute::StackProtectStrong:
    1428             :   case Attribute::SafeStack:
    1429             :   case Attribute::ShadowCallStack:
    1430             :   case Attribute::NoRedZone:
    1431             :   case Attribute::NoImplicitFloat:
    1432             :   case Attribute::Naked:
    1433             :   case Attribute::InlineHint:
    1434             :   case Attribute::StackAlignment:
    1435             :   case Attribute::UWTable:
    1436             :   case Attribute::NonLazyBind:
    1437             :   case Attribute::ReturnsTwice:
    1438             :   case Attribute::SanitizeAddress:
    1439             :   case Attribute::SanitizeHWAddress:
    1440             :   case Attribute::SanitizeThread:
    1441             :   case Attribute::SanitizeMemory:
    1442             :   case Attribute::MinSize:
    1443             :   case Attribute::NoDuplicate:
    1444             :   case Attribute::Builtin:
    1445             :   case Attribute::NoBuiltin:
    1446             :   case Attribute::Cold:
    1447             :   case Attribute::OptForFuzzing:
    1448             :   case Attribute::OptimizeNone:
    1449             :   case Attribute::JumpTable:
    1450             :   case Attribute::Convergent:
    1451             :   case Attribute::ArgMemOnly:
    1452             :   case Attribute::NoRecurse:
    1453             :   case Attribute::InaccessibleMemOnly:
    1454             :   case Attribute::InaccessibleMemOrArgMemOnly:
    1455             :   case Attribute::AllocSize:
    1456             :   case Attribute::Speculatable:
    1457             :   case Attribute::StrictFP:
    1458             :     return true;
    1459             :   default:
    1460             :     break;
    1461             :   }
    1462             :   return false;
    1463             : }
    1464             : 
    1465             : /// Return true if this is a function attribute that can also appear on
    1466             : /// arguments.
    1467             : static bool isFuncOrArgAttr(Attribute::AttrKind Kind) {
    1468      165941 :   return Kind == Attribute::ReadOnly || Kind == Attribute::WriteOnly ||
    1469             :          Kind == Attribute::ReadNone;
    1470             : }
    1471             : 
    1472     1121557 : void Verifier::verifyAttributeTypes(AttributeSet Attrs, bool IsFunction,
    1473             :                                     const Value *V) {
    1474     4823288 :   for (Attribute A : Attrs) {
    1475     3701732 :     if (A.isStringAttribute())
    1476     2248153 :       continue;
    1477             : 
    1478     1453579 :     if (isFuncOnlyAttr(A.getKindAsEnum())) {
    1479      972234 :       if (!IsFunction) {
    1480           5 :         CheckFailed("Attribute '" + A.getAsString() +
    1481             :                         "' only applies to functions!",
    1482             :                     V);
    1483           2 :         return;
    1484             :       }
    1485      647286 :     } else if (IsFunction && !isFuncOrArgAttr(A.getKindAsEnum())) {
    1486           0 :       CheckFailed("Attribute '" + A.getAsString() +
    1487             :                       "' does not apply to functions!",
    1488             :                   V);
    1489           0 :       return;
    1490             :     }
    1491             :   }
    1492             : }
    1493             : 
    1494             : // VerifyParameterAttrs - Check the given attributes for an argument or return
    1495             : // value of the specified type.  The value V is printed in error messages.
    1496     2659371 : void Verifier::verifyParameterAttrs(AttributeSet Attrs, Type *Ty,
    1497             :                                     const Value *V) {
    1498     2659371 :   if (!Attrs.hasAttributes())
    1499     2402582 :     return;
    1500             : 
    1501      256801 :   verifyAttributeTypes(Attrs, /*IsFunction=*/false, V);
    1502             : 
    1503             :   // Check for mutually incompatible attributes.  Only inreg is compatible with
    1504             :   // sret.
    1505             :   unsigned AttrCount = 0;
    1506      256801 :   AttrCount += Attrs.hasAttribute(Attribute::ByVal);
    1507      256801 :   AttrCount += Attrs.hasAttribute(Attribute::InAlloca);
    1508      508531 :   AttrCount += Attrs.hasAttribute(Attribute::StructRet) ||
    1509      251730 :                Attrs.hasAttribute(Attribute::InReg);
    1510      256801 :   AttrCount += Attrs.hasAttribute(Attribute::Nest);
    1511      256805 :   Assert(AttrCount <= 1, "Attributes 'byval', 'inalloca', 'inreg', 'nest', "
    1512             :                          "and 'sret' are incompatible!",
    1513             :          V);
    1514             : 
    1515      256798 :   Assert(!(Attrs.hasAttribute(Attribute::InAlloca) &&
    1516             :            Attrs.hasAttribute(Attribute::ReadOnly)),
    1517             :          "Attributes "
    1518             :          "'inalloca and readonly' are incompatible!",
    1519             :          V);
    1520             : 
    1521      256796 :   Assert(!(Attrs.hasAttribute(Attribute::StructRet) &&
    1522             :            Attrs.hasAttribute(Attribute::Returned)),
    1523             :          "Attributes "
    1524             :          "'sret and returned' are incompatible!",
    1525             :          V);
    1526             : 
    1527      300150 :   Assert(!(Attrs.hasAttribute(Attribute::ZExt) &&
    1528             :            Attrs.hasAttribute(Attribute::SExt)),
    1529             :          "Attributes "
    1530             :          "'zeroext and signext' are incompatible!",
    1531             :          V);
    1532             : 
    1533      257711 :   Assert(!(Attrs.hasAttribute(Attribute::ReadNone) &&
    1534             :            Attrs.hasAttribute(Attribute::ReadOnly)),
    1535             :          "Attributes "
    1536             :          "'readnone and readonly' are incompatible!",
    1537             :          V);
    1538             : 
    1539      257713 :   Assert(!(Attrs.hasAttribute(Attribute::ReadNone) &&
    1540             :            Attrs.hasAttribute(Attribute::WriteOnly)),
    1541             :          "Attributes "
    1542             :          "'readnone and writeonly' are incompatible!",
    1543             :          V);
    1544             : 
    1545      270502 :   Assert(!(Attrs.hasAttribute(Attribute::ReadOnly) &&
    1546             :            Attrs.hasAttribute(Attribute::WriteOnly)),
    1547             :          "Attributes "
    1548             :          "'readonly and writeonly' are incompatible!",
    1549             :          V);
    1550             : 
    1551      256794 :   Assert(!(Attrs.hasAttribute(Attribute::NoInline) &&
    1552             :            Attrs.hasAttribute(Attribute::AlwaysInline)),
    1553             :          "Attributes "
    1554             :          "'noinline and alwaysinline' are incompatible!",
    1555             :          V);
    1556             : 
    1557      256794 :   AttrBuilder IncompatibleAttrs = AttributeFuncs::typeIncompatible(Ty);
    1558      513596 :   Assert(!AttrBuilder(Attrs).overlaps(IncompatibleAttrs),
    1559             :          "Wrong types for attribute: " +
    1560             :              AttributeSet::get(Context, IncompatibleAttrs).getAsString(),
    1561             :          V);
    1562             : 
    1563             :   if (PointerType *PTy = dyn_cast<PointerType>(Ty)) {
    1564             :     SmallPtrSet<Type*, 4> Visited;
    1565      150088 :     if (!PTy->getElementType()->isSized(&Visited)) {
    1566        1193 :       Assert(!Attrs.hasAttribute(Attribute::ByVal) &&
    1567             :                  !Attrs.hasAttribute(Attribute::InAlloca),
    1568             :              "Attributes 'byval' and 'inalloca' do not support unsized types!",
    1569             :              V);
    1570             :     }
    1571      300174 :     if (!isa<PointerType>(PTy->getElementType()))
    1572      145485 :       Assert(!Attrs.hasAttribute(Attribute::SwiftError),
    1573             :              "Attribute 'swifterror' only applies to parameters "
    1574             :              "with pointer to pointer type!",
    1575             :              V);
    1576             :   } else {
    1577      106704 :     Assert(!Attrs.hasAttribute(Attribute::ByVal),
    1578             :            "Attribute 'byval' only applies to parameters with pointer type!",
    1579             :            V);
    1580      106705 :     Assert(!Attrs.hasAttribute(Attribute::SwiftError),
    1581             :            "Attribute 'swifterror' only applies to parameters "
    1582             :            "with pointer type!",
    1583             :            V);
    1584             :   }
    1585             : }
    1586             : 
    1587             : // Check parameter attributes against a function type.
    1588             : // The value V is printed in error messages.
    1589     1670559 : void Verifier::verifyFunctionAttrs(FunctionType *FT, AttributeList Attrs,
    1590             :                                    const Value *V) {
    1591     1670559 :   if (Attrs.isEmpty())
    1592      805850 :     return;
    1593             : 
    1594             :   bool SawNest = false;
    1595             :   bool SawReturned = false;
    1596             :   bool SawSRet = false;
    1597             :   bool SawSwiftSelf = false;
    1598             :   bool SawSwiftError = false;
    1599             : 
    1600             :   // Verify return value attributes.
    1601      939043 :   AttributeSet RetAttrs = Attrs.getRetAttributes();
    1602      939043 :   Assert((!RetAttrs.hasAttribute(Attribute::ByVal) &&
    1603             :           !RetAttrs.hasAttribute(Attribute::Nest) &&
    1604             :           !RetAttrs.hasAttribute(Attribute::StructRet) &&
    1605             :           !RetAttrs.hasAttribute(Attribute::NoCapture) &&
    1606             :           !RetAttrs.hasAttribute(Attribute::Returned) &&
    1607             :           !RetAttrs.hasAttribute(Attribute::InAlloca) &&
    1608             :           !RetAttrs.hasAttribute(Attribute::SwiftSelf) &&
    1609             :           !RetAttrs.hasAttribute(Attribute::SwiftError)),
    1610             :          "Attributes 'byval', 'inalloca', 'nest', 'sret', 'nocapture', "
    1611             :          "'returned', 'swiftself', and 'swifterror' do not apply to return "
    1612             :          "values!",
    1613             :          V);
    1614      939043 :   Assert((!RetAttrs.hasAttribute(Attribute::ReadOnly) &&
    1615             :           !RetAttrs.hasAttribute(Attribute::WriteOnly) &&
    1616             :           !RetAttrs.hasAttribute(Attribute::ReadNone)),
    1617             :          "Attribute '" + RetAttrs.getAsString() +
    1618             :              "' does not apply to function returns",
    1619             :          V);
    1620     1878086 :   verifyParameterAttrs(RetAttrs, FT->getReturnType(), V);
    1621             : 
    1622             :   // Verify parameter attributes.
    1623     5249126 :   for (unsigned i = 0, e = FT->getNumParams(); i != e; ++i) {
    1624     1685525 :     Type *Ty = FT->getParamType(i);
    1625     1685525 :     AttributeSet ArgAttrs = Attrs.getParamAttributes(i);
    1626             : 
    1627     1685525 :     verifyParameterAttrs(ArgAttrs, Ty, V);
    1628             : 
    1629     1685525 :     if (ArgAttrs.hasAttribute(Attribute::Nest)) {
    1630         252 :       Assert(!SawNest, "More than one parameter has attribute nest!", V);
    1631             :       SawNest = true;
    1632             :     }
    1633             : 
    1634     1685525 :     if (ArgAttrs.hasAttribute(Attribute::Returned)) {
    1635        2184 :       Assert(!SawReturned, "More than one parameter has attribute returned!",
    1636             :              V);
    1637        4368 :       Assert(Ty->canLosslesslyBitCastTo(FT->getReturnType()),
    1638             :              "Incompatible argument and return types for 'returned' attribute",
    1639             :              V);
    1640             :       SawReturned = true;
    1641             :     }
    1642             : 
    1643     1685525 :     if (ArgAttrs.hasAttribute(Attribute::StructRet)) {
    1644        5071 :       Assert(!SawSRet, "Cannot have multiple 'sret' parameters!", V);
    1645        5070 :       Assert(i == 0 || i == 1,
    1646             :              "Attribute 'sret' is not on first or second parameter!", V);
    1647             :       SawSRet = true;
    1648             :     }
    1649             : 
    1650     1685523 :     if (ArgAttrs.hasAttribute(Attribute::SwiftSelf)) {
    1651         648 :       Assert(!SawSwiftSelf, "Cannot have multiple 'swiftself' parameters!", V);
    1652             :       SawSwiftSelf = true;
    1653             :     }
    1654             : 
    1655     1685522 :     if (ArgAttrs.hasAttribute(Attribute::SwiftError)) {
    1656         960 :       Assert(!SawSwiftError, "Cannot have multiple 'swifterror' parameters!",
    1657             :              V);
    1658             :       SawSwiftError = true;
    1659             :     }
    1660             : 
    1661     1685521 :     if (ArgAttrs.hasAttribute(Attribute::InAlloca)) {
    1662         432 :       Assert(i == FT->getNumParams() - 1,
    1663             :              "inalloca isn't on the last parameter!", V);
    1664             :     }
    1665             :   }
    1666             : 
    1667      939038 :   if (!Attrs.hasAttributes(AttributeList::FunctionIndex))
    1668             :     return;
    1669             : 
    1670      864756 :   verifyAttributeTypes(Attrs.getFnAttributes(), /*IsFunction=*/true, V);
    1671             : 
    1672      864756 :   Assert(!(Attrs.hasFnAttribute(Attribute::ReadNone) &&
    1673             :            Attrs.hasFnAttribute(Attribute::ReadOnly)),
    1674             :          "Attributes 'readnone and readonly' are incompatible!", V);
    1675             : 
    1676     1017926 :   Assert(!(Attrs.hasFnAttribute(Attribute::ReadNone) &&
    1677             :            Attrs.hasFnAttribute(Attribute::WriteOnly)),
    1678             :          "Attributes 'readnone and writeonly' are incompatible!", V);
    1679             : 
    1680      876786 :   Assert(!(Attrs.hasFnAttribute(Attribute::ReadOnly) &&
    1681             :            Attrs.hasFnAttribute(Attribute::WriteOnly)),
    1682             :          "Attributes 'readonly and writeonly' are incompatible!", V);
    1683             : 
    1684     1017921 :   Assert(!(Attrs.hasFnAttribute(Attribute::ReadNone) &&
    1685             :            Attrs.hasFnAttribute(Attribute::InaccessibleMemOrArgMemOnly)),
    1686             :          "Attributes 'readnone and inaccessiblemem_or_argmemonly' are "
    1687             :          "incompatible!",
    1688             :          V);
    1689             : 
    1690     1017921 :   Assert(!(Attrs.hasFnAttribute(Attribute::ReadNone) &&
    1691             :            Attrs.hasFnAttribute(Attribute::InaccessibleMemOnly)),
    1692             :          "Attributes 'readnone and inaccessiblememonly' are incompatible!", V);
    1693             : 
    1694      967699 :   Assert(!(Attrs.hasFnAttribute(Attribute::NoInline) &&
    1695             :            Attrs.hasFnAttribute(Attribute::AlwaysInline)),
    1696             :          "Attributes 'noinline and alwaysinline' are incompatible!", V);
    1697             : 
    1698      864753 :   if (Attrs.hasFnAttribute(Attribute::OptimizeNone)) {
    1699       69865 :     Assert(Attrs.hasFnAttribute(Attribute::NoInline),
    1700             :            "Attribute 'optnone' requires 'noinline'!", V);
    1701             : 
    1702       69865 :     Assert(!Attrs.hasFnAttribute(Attribute::OptimizeForSize),
    1703             :            "Attributes 'optsize and optnone' are incompatible!", V);
    1704             : 
    1705       69865 :     Assert(!Attrs.hasFnAttribute(Attribute::MinSize),
    1706             :            "Attributes 'minsize and optnone' are incompatible!", V);
    1707             :   }
    1708             : 
    1709      864753 :   if (Attrs.hasFnAttribute(Attribute::JumpTable)) {
    1710          19 :     const GlobalValue *GV = cast<GlobalValue>(V);
    1711          20 :     Assert(GV->hasGlobalUnnamedAddr(),
    1712             :            "Attribute 'jumptable' requires 'unnamed_addr'", V);
    1713             :   }
    1714             : 
    1715      864752 :   if (Attrs.hasFnAttribute(Attribute::AllocSize)) {
    1716             :     std::pair<unsigned, Optional<unsigned>> Args =
    1717          83 :         Attrs.getAllocSizeArgs(AttributeList::FunctionIndex);
    1718             : 
    1719         124 :     auto CheckParam = [&](StringRef Name, unsigned ParamNo) {
    1720         248 :       if (ParamNo >= FT->getNumParams()) {
    1721          10 :         CheckFailed("'allocsize' " + Name + " argument is out of bounds", V);
    1722           3 :         return false;
    1723             :       }
    1724             : 
    1725         242 :       if (!FT->getParamType(ParamNo)->isIntegerTy()) {
    1726           4 :         CheckFailed("'allocsize' " + Name +
    1727           2 :                         " argument must refer to an integer parameter",
    1728             :                     V);
    1729           2 :         return false;
    1730             :       }
    1731             : 
    1732             :       return true;
    1733          83 :     };
    1734             : 
    1735         166 :     if (!CheckParam("element size", Args.first))
    1736             :       return;
    1737             : 
    1738         122 :     if (Args.second && !CheckParam("number of elements", *Args.second))
    1739             :       return;
    1740             :   }
    1741             : }
    1742             : 
    1743     1063327 : void Verifier::verifyFunctionMetadata(
    1744             :     ArrayRef<std::pair<unsigned, MDNode *>> MDs) {
    1745     1095883 :   for (const auto &Pair : MDs) {
    1746       16282 :     if (Pair.first == LLVMContext::MD_prof) {
    1747        1016 :       MDNode *MD = Pair.second;
    1748        1021 :       Assert(MD->getNumOperands() >= 2,
    1749             :              "!prof annotations should have no less than 2 operands", MD);
    1750             : 
    1751             :       // Check first operand.
    1752        1015 :       Assert(MD->getOperand(0) != nullptr, "first operand should not be null",
    1753             :              MD);
    1754        1016 :       Assert(isa<MDString>(MD->getOperand(0)),
    1755             :              "expected string with name of the !prof annotation", MD);
    1756             :       MDString *MDS = cast<MDString>(MD->getOperand(0));
    1757        1014 :       StringRef ProfName = MDS->getString();
    1758           2 :       Assert(ProfName.equals("function_entry_count") ||
    1759             :                  ProfName.equals("synthetic_function_entry_count"),
    1760             :              "first operand should be 'function_entry_count'"
    1761             :              " or 'synthetic_function_entry_count'",
    1762             :              MD);
    1763             : 
    1764             :       // Check second operand.
    1765        2026 :       Assert(MD->getOperand(1) != nullptr, "second operand should not be null",
    1766             :              MD);
    1767        1014 :       Assert(isa<ConstantAsMetadata>(MD->getOperand(1)),
    1768             :              "expected integer argument to function_entry_count", MD);
    1769             :     }
    1770             :   }
    1771             : }
    1772             : 
    1773      235605 : void Verifier::visitConstantExprsRecursively(const Constant *EntryC) {
    1774      235605 :   if (!ConstantExprVisited.insert(EntryC).second)
    1775       67208 :     return;
    1776             : 
    1777             :   SmallVector<const Constant *, 16> Stack;
    1778      168397 :   Stack.push_back(EntryC);
    1779             : 
    1780      528528 :   while (!Stack.empty()) {
    1781             :     const Constant *C = Stack.pop_back_val();
    1782             : 
    1783             :     // Check this constant expression.
    1784             :     if (const auto *CE = dyn_cast<ConstantExpr>(C))
    1785      117981 :       visitConstantExpr(CE);
    1786             : 
    1787      454577 :     if (const auto *GV = dyn_cast<GlobalValue>(C)) {
    1788             :       // Global Values get visited separately, but we do need to make sure
    1789             :       // that the global value is in the correct module
    1790       94446 :       Assert(GV->getParent() == &M, "Referencing global in another module!",
    1791             :              EntryC, &M, GV, GV->getParent());
    1792       94446 :       continue;
    1793             :     }
    1794             : 
    1795             :     // Visit all sub-expressions.
    1796     1348100 :     for (const Use &U : C->operands()) {
    1797      408365 :       const auto *OpC = dyn_cast<Constant>(U);
    1798      408365 :       if (!OpC)
    1799      217172 :         continue;
    1800      407824 :       if (!ConstantExprVisited.insert(OpC).second)
    1801      216090 :         continue;
    1802      191734 :       Stack.push_back(OpC);
    1803             :     }
    1804             :   }
    1805             : }
    1806             : 
    1807      117981 : void Verifier::visitConstantExpr(const ConstantExpr *CE) {
    1808      235962 :   if (CE->getOpcode() == Instruction::BitCast)
    1809       90636 :     Assert(CastInst::castIsValid(Instruction::BitCast, CE->getOperand(0),
    1810             :                                  CE->getType()),
    1811             :            "Invalid bitcast", CE);
    1812             : 
    1813      235962 :   if (CE->getOpcode() == Instruction::IntToPtr ||
    1814             :       CE->getOpcode() == Instruction::PtrToInt) {
    1815             :     auto *PtrTy = CE->getOpcode() == Instruction::IntToPtr
    1816        5225 :                       ? CE->getType()
    1817             :                       : CE->getOperand(0)->getType();
    1818             :     StringRef Msg = CE->getOpcode() == Instruction::IntToPtr
    1819             :                         ? "inttoptr not supported for non-integral pointers"
    1820        3565 :                         : "ptrtoint not supported for non-integral pointers";
    1821        7136 :     Assert(
    1822             :         !DL.isNonIntegralPointerType(cast<PointerType>(PtrTy->getScalarType())),
    1823             :         Msg);
    1824             :   }
    1825             : }
    1826             : 
    1827             : bool Verifier::verifyAttributeCount(AttributeList Attrs, unsigned Params) {
    1828             :   // There shouldn't be more attribute sets than there are parameters plus the
    1829             :   // function and return value.
    1830     1670561 :   return Attrs.getNumAttrSets() <= Params + 2;
    1831             : }
    1832             : 
    1833             : /// Verify that statepoint intrinsic is well formed.
    1834         702 : void Verifier::verifyStatepoint(ImmutableCallSite CS) {
    1835             :   assert(CS.getCalledFunction() &&
    1836             :          CS.getCalledFunction()->getIntrinsicID() ==
    1837             :            Intrinsic::experimental_gc_statepoint);
    1838             : 
    1839             :   const Instruction &CI = *CS.getInstruction();
    1840             : 
    1841         703 :   Assert(!CS.doesNotAccessMemory() && !CS.onlyReadsMemory() &&
    1842             :          !CS.onlyAccessesArgMemory(),
    1843             :          "gc.statepoint must read and write all memory to preserve "
    1844             :          "reordering restrictions required by safepoint semantics",
    1845             :          &CI);
    1846             : 
    1847             :   const Value *IDV = CS.getArgument(0);
    1848         702 :   Assert(isa<ConstantInt>(IDV), "gc.statepoint ID must be a constant integer",
    1849             :          &CI);
    1850             : 
    1851             :   const Value *NumPatchBytesV = CS.getArgument(1);
    1852         702 :   Assert(isa<ConstantInt>(NumPatchBytesV),
    1853             :          "gc.statepoint number of patchable bytes must be a constant integer",
    1854             :          &CI);
    1855             :   const int64_t NumPatchBytes =
    1856             :       cast<ConstantInt>(NumPatchBytesV)->getSExtValue();
    1857             :   assert(isInt<32>(NumPatchBytes) && "NumPatchBytesV is an i32!");
    1858         702 :   Assert(NumPatchBytes >= 0, "gc.statepoint number of patchable bytes must be "
    1859             :                              "positive",
    1860             :          &CI);
    1861             : 
    1862         702 :   const Value *Target = CS.getArgument(2);
    1863         702 :   auto *PT = dyn_cast<PointerType>(Target->getType());
    1864        1404 :   Assert(PT && PT->getElementType()->isFunctionTy(),
    1865             :          "gc.statepoint callee must be of function pointer type", &CI, Target);
    1866             :   FunctionType *TargetFuncType = cast<FunctionType>(PT->getElementType());
    1867             : 
    1868             :   const Value *NumCallArgsV = CS.getArgument(3);
    1869         702 :   Assert(isa<ConstantInt>(NumCallArgsV),
    1870             :          "gc.statepoint number of arguments to underlying call "
    1871             :          "must be constant integer",
    1872             :          &CI);
    1873         702 :   const int NumCallArgs = cast<ConstantInt>(NumCallArgsV)->getZExtValue();
    1874         702 :   Assert(NumCallArgs >= 0,
    1875             :          "gc.statepoint number of arguments to underlying call "
    1876             :          "must be positive",
    1877             :          &CI);
    1878        1404 :   const int NumParams = (int)TargetFuncType->getNumParams();
    1879         702 :   if (TargetFuncType->isVarArg()) {
    1880           6 :     Assert(NumCallArgs >= NumParams,
    1881             :            "gc.statepoint mismatch in number of vararg call args", &CI);
    1882             : 
    1883             :     // TODO: Remove this limitation
    1884          12 :     Assert(TargetFuncType->getReturnType()->isVoidTy(),
    1885             :            "gc.statepoint doesn't support wrapping non-void "
    1886             :            "vararg functions yet",
    1887             :            &CI);
    1888             :   } else
    1889         696 :     Assert(NumCallArgs == NumParams,
    1890             :            "gc.statepoint mismatch in number of call args", &CI);
    1891             : 
    1892             :   const Value *FlagsV = CS.getArgument(4);
    1893         702 :   Assert(isa<ConstantInt>(FlagsV),
    1894             :          "gc.statepoint flags must be constant integer", &CI);
    1895             :   const uint64_t Flags = cast<ConstantInt>(FlagsV)->getZExtValue();
    1896         702 :   Assert((Flags & ~(uint64_t)StatepointFlags::MaskAll) == 0,
    1897             :          "unknown flag used in gc.statepoint flags argument", &CI);
    1898             : 
    1899             :   // Verify that the types of the call parameter arguments match
    1900             :   // the type of the wrapped callee.
    1901         910 :   for (int i = 0; i < NumParams; i++) {
    1902         104 :     Type *ParamType = TargetFuncType->getParamType(i);
    1903         208 :     Type *ArgType = CS.getArgument(5 + i)->getType();
    1904         104 :     Assert(ArgType == ParamType,
    1905             :            "gc.statepoint call argument does not match wrapped "
    1906             :            "function type",
    1907             :            &CI);
    1908             :   }
    1909             : 
    1910             :   const int EndCallArgsInx = 4 + NumCallArgs;
    1911             : 
    1912         702 :   const Value *NumTransitionArgsV = CS.getArgument(EndCallArgsInx+1);
    1913         702 :   Assert(isa<ConstantInt>(NumTransitionArgsV),
    1914             :          "gc.statepoint number of transition arguments "
    1915             :          "must be constant integer",
    1916             :          &CI);
    1917             :   const int NumTransitionArgs =
    1918         702 :       cast<ConstantInt>(NumTransitionArgsV)->getZExtValue();
    1919         702 :   Assert(NumTransitionArgs >= 0,
    1920             :          "gc.statepoint number of transition arguments must be positive", &CI);
    1921         702 :   const int EndTransitionArgsInx = EndCallArgsInx + 1 + NumTransitionArgs;
    1922             : 
    1923         702 :   const Value *NumDeoptArgsV = CS.getArgument(EndTransitionArgsInx+1);
    1924         703 :   Assert(isa<ConstantInt>(NumDeoptArgsV),
    1925             :          "gc.statepoint number of deoptimization arguments "
    1926             :          "must be constant integer",
    1927             :          &CI);
    1928         701 :   const int NumDeoptArgs = cast<ConstantInt>(NumDeoptArgsV)->getZExtValue();
    1929         701 :   Assert(NumDeoptArgs >= 0, "gc.statepoint number of deoptimization arguments "
    1930             :                             "must be positive",
    1931             :          &CI);
    1932             : 
    1933         701 :   const int ExpectedNumArgs =
    1934         701 :       7 + NumCallArgs + NumTransitionArgs + NumDeoptArgs;
    1935         701 :   Assert(ExpectedNumArgs <= (int)CS.arg_size(),
    1936             :          "gc.statepoint too few arguments according to length fields", &CI);
    1937             : 
    1938             :   // Check that the only uses of this gc.statepoint are gc.result or
    1939             :   // gc.relocate calls which are tied to this statepoint and thus part
    1940             :   // of the same statepoint sequence
    1941        2315 :   for (const User *U : CI.users()) {
    1942         807 :     const CallInst *Call = dyn_cast<const CallInst>(U);
    1943         807 :     Assert(Call, "illegal use of statepoint token", &CI, U);
    1944             :     if (!Call) continue;
    1945           0 :     Assert(isa<GCRelocateInst>(Call) || isa<GCResultInst>(Call),
    1946             :            "gc.result or gc.relocate are the only value uses "
    1947             :            "of a gc.statepoint",
    1948             :            &CI, U);
    1949             :     if (isa<GCResultInst>(Call)) {
    1950         218 :       Assert(Call->getArgOperand(0) == &CI,
    1951             :              "gc.result connected to wrong gc.statepoint", &CI, Call);
    1952             :     } else if (isa<GCRelocateInst>(Call)) {
    1953        1396 :       Assert(Call->getArgOperand(0) == &CI,
    1954             :              "gc.relocate connected to wrong gc.statepoint", &CI, Call);
    1955             :     }
    1956             :   }
    1957             : 
    1958             :   // Note: It is legal for a single derived pointer to be listed multiple
    1959             :   // times.  It's non-optimal, but it is legal.  It can also happen after
    1960             :   // insertion if we strip a bitcast away.
    1961             :   // Note: It is really tempting to check that each base is relocated and
    1962             :   // that a derived pointer is never reused as a base pointer.  This turns
    1963             :   // out to be problematic since optimizations run after safepoint insertion
    1964             :   // can recognize equality properties that the insertion logic doesn't know
    1965             :   // about.  See example statepoint.ll in the verifier subdirectory
    1966             : }
    1967             : 
    1968       95463 : void Verifier::verifyFrameRecoverIndices() {
    1969      191018 :   for (auto &Counts : FrameEscapeInfo) {
    1970          93 :     Function *F = Counts.first;
    1971          93 :     unsigned EscapedObjectCount = Counts.second.first;
    1972          93 :     unsigned MaxRecoveredIndex = Counts.second.second;
    1973          94 :     Assert(MaxRecoveredIndex <= EscapedObjectCount,
    1974             :            "all indices passed to llvm.localrecover must be less than the "
    1975             :            "number of arguments passed ot llvm.localescape in the parent "
    1976             :            "function",
    1977             :            F);
    1978             :   }
    1979             : }
    1980             : 
    1981         381 : static Instruction *getSuccPad(TerminatorInst *Terminator) {
    1982             :   BasicBlock *UnwindDest;
    1983             :   if (auto *II = dyn_cast<InvokeInst>(Terminator))
    1984             :     UnwindDest = II->getUnwindDest();
    1985             :   else if (auto *CSI = dyn_cast<CatchSwitchInst>(Terminator))
    1986             :     UnwindDest = CSI->getUnwindDest();
    1987             :   else
    1988             :     UnwindDest = cast<CleanupReturnInst>(Terminator)->getUnwindDest();
    1989         381 :   return UnwindDest->getFirstNonPHI();
    1990             : }
    1991             : 
    1992     1063341 : void Verifier::verifySiblingFuncletUnwinds() {
    1993             :   SmallPtrSet<Instruction *, 8> Visited;
    1994             :   SmallPtrSet<Instruction *, 8> Active;
    1995     1063705 :   for (const auto &Pair : SiblingFuncletInfo) {
    1996         368 :     Instruction *PredPad = Pair.first;
    1997         368 :     if (Visited.count(PredPad))
    1998             :       continue;
    1999         327 :     Active.insert(PredPad);
    2000         327 :     TerminatorInst *Terminator = Pair.second;
    2001             :     do {
    2002         374 :       Instruction *SuccPad = getSuccPad(Terminator);
    2003         374 :       if (Active.count(SuccPad)) {
    2004             :         // Found a cycle; report error
    2005           4 :         Instruction *CyclePad = SuccPad;
    2006             :         SmallVector<Instruction *, 8> CycleNodes;
    2007             :         do {
    2008           7 :           CycleNodes.push_back(CyclePad);
    2009           7 :           TerminatorInst *CycleTerminator = SiblingFuncletInfo[CyclePad];
    2010           7 :           if (CycleTerminator != CyclePad)
    2011           5 :             CycleNodes.push_back(CycleTerminator);
    2012           7 :           CyclePad = getSuccPad(CycleTerminator);
    2013           7 :         } while (CyclePad != SuccPad);
    2014           8 :         Assert(false, "EH pads can't handle each other's exceptions",
    2015             :                ArrayRef<Instruction *>(CycleNodes));
    2016             :       }
    2017             :       // Don't re-walk a node we've already checked
    2018         370 :       if (!Visited.insert(SuccPad).second)
    2019             :         break;
    2020             :       // Walk to this successor if it has a map entry.
    2021             :       PredPad = SuccPad;
    2022         332 :       auto TermI = SiblingFuncletInfo.find(PredPad);
    2023         332 :       if (TermI == SiblingFuncletInfo.end())
    2024             :         break;
    2025          47 :       Terminator = TermI->second;
    2026          47 :       Active.insert(PredPad);
    2027             :     } while (true);
    2028             :     // Each node only has one successor, so we've walked all the active
    2029             :     // nodes' successors.
    2030         323 :     Active.clear();
    2031             :   }
    2032             : }
    2033             : 
    2034             : // visitFunction - Verify that a function is ok.
    2035             : //
    2036     1063341 : void Verifier::visitFunction(const Function &F) {
    2037     1063341 :   visitGlobalValue(F);
    2038             : 
    2039             :   // Check function arguments.
    2040     1063341 :   FunctionType *FT = F.getFunctionType();
    2041     1063341 :   unsigned NumArgs = F.arg_size();
    2042             : 
    2043     2117231 :   Assert(&Context == &F.getContext(),
    2044             :          "Function context does not match Module context!", &F);
    2045             : 
    2046     1063341 :   Assert(!F.hasCommonLinkage(), "Functions may not have common linkage", &F);
    2047     2126682 :   Assert(FT->getNumParams() == NumArgs,
    2048             :          "# formal arguments must match # of arguments for function type!", &F,
    2049             :          FT);
    2050      367029 :   Assert(F.getReturnType()->isFirstClassType() ||
    2051             :              F.getReturnType()->isVoidTy() || F.getReturnType()->isStructTy(),
    2052             :          "Functions cannot return aggregate values!", &F);
    2053             : 
    2054     1066840 :   Assert(!F.hasStructRetAttr() || F.getReturnType()->isVoidTy(),
    2055             :          "Invalid struct return type!", &F);
    2056             : 
    2057     1063341 :   AttributeList Attrs = F.getAttributes();
    2058             : 
    2059     2126682 :   Assert(verifyAttributeCount(Attrs, FT->getNumParams()),
    2060             :          "Attribute after last parameter!", &F);
    2061             : 
    2062             :   // Check function attributes.
    2063     1063341 :   verifyFunctionAttrs(FT, Attrs, &F);
    2064             : 
    2065             :   // On function declarations/definitions, we do not support the builtin
    2066             :   // attribute. We do not check this in VerifyFunctionAttrs since that is
    2067             :   // checking for Attributes that can/can not ever be on functions.
    2068     1063343 :   Assert(!Attrs.hasFnAttribute(Attribute::Builtin),
    2069             :          "Attribute 'builtin' can only be applied to a callsite.", &F);
    2070             : 
    2071             :   // Check that this function meets the restrictions on this calling convention.
    2072             :   // Sometimes varargs is used for perfectly forwarding thunks, so some of these
    2073             :   // restrictions can be lifted.
    2074     1063339 :   switch (F.getCallingConv()) {
    2075             :   default:
    2076             :   case CallingConv::C:
    2077             :     break;
    2078             :   case CallingConv::AMDGPU_KERNEL:
    2079             :   case CallingConv::SPIR_KERNEL:
    2080       56115 :     Assert(F.getReturnType()->isVoidTy(),
    2081             :            "Calling convention requires void return type", &F);
    2082             :     LLVM_FALLTHROUGH;
    2083             :   case CallingConv::AMDGPU_VS:
    2084             :   case CallingConv::AMDGPU_HS:
    2085             :   case CallingConv::AMDGPU_GS:
    2086             :   case CallingConv::AMDGPU_PS:
    2087             :   case CallingConv::AMDGPU_CS:
    2088       60392 :     Assert(!F.hasStructRetAttr(),
    2089             :            "Calling convention does not allow sret", &F);
    2090             :     LLVM_FALLTHROUGH;
    2091             :   case CallingConv::Fast:
    2092             :   case CallingConv::Cold:
    2093             :   case CallingConv::Intel_OCL_BI:
    2094             :   case CallingConv::PTX_Kernel:
    2095             :   case CallingConv::PTX_Device:
    2096       64293 :     Assert(!F.isVarArg(), "Calling convention does not support varargs or "
    2097             :                           "perfect forwarding!",
    2098             :            &F);
    2099             :     break;
    2100             :   }
    2101             : 
    2102     3189990 :   bool isLLVMdotName = F.getName().size() >= 5 &&
    2103     2016466 :                        F.getName().substr(0, 5) == "llvm.";
    2104             : 
    2105             :   // Check that the argument values match the function type for this function...
    2106             :   unsigned i = 0;
    2107     2922565 :   for (const Argument &Arg : F.args()) {
    2108     3718474 :     Assert(Arg.getType() == FT->getParamType(i),
    2109             :            "Argument value does not match function argument type!", &Arg,
    2110             :            FT->getParamType(i));
    2111           0 :     Assert(Arg.getType()->isFirstClassType(),
    2112             :            "Function arguments must have first-class types!", &Arg);
    2113     1859237 :     if (!isLLVMdotName) {
    2114     1494080 :       Assert(!Arg.getType()->isMetadataTy(),
    2115             :              "Function takes metadata but isn't an intrinsic", &Arg, &F);
    2116     1494082 :       Assert(!Arg.getType()->isTokenTy(),
    2117             :              "Function takes token but isn't an intrinsic", &Arg, &F);
    2118             :     }
    2119             : 
    2120             :     // Check that swifterror argument is only used by loads and stores.
    2121     1859235 :     if (Attrs.hasParamAttribute(i, Attribute::SwiftError)) {
    2122         541 :       verifySwiftErrorValue(&Arg);
    2123             :     }
    2124             :     ++i;
    2125             :   }
    2126             : 
    2127     1063328 :   if (!isLLVMdotName)
    2128      873535 :     Assert(!F.getReturnType()->isTokenTy(),
    2129             :            "Functions returns a token but isn't an intrinsic", &F);
    2130             : 
    2131             :   // Get the function metadata attachments.
    2132             :   SmallVector<std::pair<unsigned, MDNode *>, 4> MDs;
    2133     1063327 :   F.getAllMetadata(MDs);
    2134             :   assert(F.hasMetadata() != MDs.empty() && "Bit out-of-sync");
    2135     1063327 :   verifyFunctionMetadata(MDs);
    2136             : 
    2137             :   // Check validity of the personality function
    2138     1063327 :   if (F.hasPersonalityFn()) {
    2139        7662 :     auto *Per = dyn_cast<Function>(F.getPersonalityFn()->stripPointerCasts());
    2140        3831 :     if (Per)
    2141        3542 :       Assert(Per->getParent() == F.getParent(),
    2142             :              "Referencing personality function in another module!",
    2143             :              &F, F.getParent(), Per, Per->getParent());
    2144             :   }
    2145             : 
    2146     1063326 :   if (F.isMaterializable()) {
    2147             :     // Function has a body somewhere we can't see.
    2148         222 :     Assert(MDs.empty(), "unmaterialized function cannot have metadata", &F,
    2149             :            MDs.empty() ? nullptr : MDs.front().second);
    2150     1063105 :   } else if (F.isDeclaration()) {
    2151      281820 :     for (const auto &I : MDs) {
    2152          75 :       AssertDI(I.first != LLVMContext::MD_dbg,
    2153             :                "function declaration may not have a !dbg attachment", &F);
    2154          74 :       Assert(I.first != LLVMContext::MD_prof,
    2155             :              "function declaration may not have a !prof attachment", &F);
    2156             : 
    2157             :       // Verify the metadata itself.
    2158          72 :       visitMDNode(*I.second);
    2159             :     }
    2160      281674 :     Assert(!F.hasPersonalityFn(),
    2161             :            "Function declaration shouldn't have a personality routine", &F);
    2162             :   } else {
    2163             :     // Verify that this function (which has a body) is not named "llvm.*".  It
    2164             :     // is not legal to define intrinsics.
    2165      781437 :     Assert(!isLLVMdotName, "llvm intrinsics cannot be defined!", &F);
    2166             : 
    2167             :     // Check the entry node
    2168      781428 :     const BasicBlock *Entry = &F.getEntryBlock();
    2169      781429 :     Assert(pred_empty(Entry),
    2170             :            "Entry block to function must not have predecessors!", Entry);
    2171             : 
    2172             :     // The address of the entry block cannot be taken, unless it is dead.
    2173     1562854 :     if (Entry->hasAddressTaken()) {
    2174           0 :       Assert(!BlockAddress::lookup(Entry)->isConstantUsed(),
    2175             :              "blockaddress may not be used with the entry block!", Entry);
    2176             :     }
    2177             : 
    2178             :     unsigned NumDebugAttachments = 0, NumProfAttachments = 0;
    2179             :     // Visit metadata attachments.
    2180      813831 :     for (const auto &I : MDs) {
    2181             :       // Verify that the attachment is legal.
    2182       16207 :       switch (I.first) {
    2183             :       default:
    2184             :         break;
    2185        9458 :       case LLVMContext::MD_dbg: {
    2186        9458 :         ++NumDebugAttachments;
    2187        9463 :         AssertDI(NumDebugAttachments == 1,
    2188             :                  "function must have a single !dbg attachment", &F, I.second);
    2189       18915 :         AssertDI(isa<DISubprogram>(I.second),
    2190             :                  "function !dbg attachment must be a subprogram", &F, I.second);
    2191        9456 :         auto *SP = cast<DISubprogram>(I.second);
    2192       18912 :         const Function *&AttachedTo = DISubprogramAttachments[SP];
    2193        9458 :         AssertDI(!AttachedTo || AttachedTo == &F,
    2194             :                  "DISubprogram attached to more than one function", SP, &F);
    2195        9454 :         AttachedTo = &F;
    2196        9454 :         break;
    2197             :       }
    2198        1015 :       case LLVMContext::MD_prof:
    2199        1015 :         ++NumProfAttachments;
    2200        1016 :         Assert(NumProfAttachments == 1,
    2201             :                "function must have a single !prof attachment", &F, I.second);
    2202             :         break;
    2203             :       }
    2204             : 
    2205             :       // Verify the metadata itself.
    2206       16202 :       visitMDNode(*I.second);
    2207             :     }
    2208             :   }
    2209             : 
    2210             :   // If this function is actually an intrinsic, verify that it is only used in
    2211             :   // direct call/invokes, never having its "address taken".
    2212             :   // Only do this if the module is materialized, otherwise we don't have all the
    2213             :   // uses.
    2214     1252673 :   if (F.getIntrinsicID() && F.getParent()->isMaterialized()) {
    2215             :     const User *U;
    2216      189352 :     if (F.hasAddressTaken(&U))
    2217           2 :       Assert(false, "Invalid user of intrinsic instruction!", U);
    2218             :   }
    2219             : 
    2220     1063315 :   auto *N = F.getSubprogram();
    2221     1063315 :   HasDebugInfo = (N != nullptr);
    2222     1063315 :   if (!HasDebugInfo)
    2223             :     return;
    2224             : 
    2225             :   // Check that all !dbg attachments lead to back to N (or, at least, another
    2226             :   // subprogram that describes the same function).
    2227             :   //
    2228             :   // FIXME: Check this incrementally while visiting !dbg attachments.
    2229             :   // FIXME: Only check when N is the canonical subprogram for F.
    2230             :   SmallPtrSet<const MDNode *, 32> Seen;
    2231       30175 :   for (auto &BB : F)
    2232      142045 :     for (auto &I : BB) {
    2233             :       // Be careful about using DILocation here since we might be dealing with
    2234             :       // broken code (this is the Verifier after all).
    2235             :       DILocation *DL =
    2236      121323 :           dyn_cast_or_null<DILocation>(I.getDebugLoc().getAsMDNode());
    2237      121323 :       if (!DL)
    2238      142745 :         continue;
    2239       90855 :       if (!Seen.insert(DL).second)
    2240       52100 :         continue;
    2241             : 
    2242       77510 :       DILocalScope *Scope = DL->getInlinedAtScope();
    2243       64783 :       if (Scope && !Seen.insert(Scope).second)
    2244       26028 :         continue;
    2245             : 
    2246       25454 :       DISubprogram *SP = Scope ? Scope->getSubprogram() : nullptr;
    2247             : 
    2248             :       // Scope and SP could be the same MDNode and we don't want to skip
    2249             :       // validation in that case
    2250       16408 :       if (SP && ((Scope != SP) && !Seen.insert(SP).second))
    2251        3681 :         continue;
    2252             : 
    2253             :       // FIXME: Once N is canonical, check "SP == &N".
    2254        9050 :       AssertDI(SP->describes(&F),
    2255             :                "!dbg attachment points at wrong subprogram for function", N, &F,
    2256             :                &I, DL, Scope, SP);
    2257             :     }
    2258             : }
    2259             : 
    2260             : // verifyBasicBlock - Verify that a basic block is well formed...
    2261             : //
    2262     1143200 : void Verifier::visitBasicBlock(BasicBlock &BB) {
    2263     1143200 :   InstsInThisBlock.clear();
    2264             : 
    2265             :   // Ensure that basic blocks have terminators!
    2266     1143200 :   Assert(BB.getTerminator(), "Basic Block does not have terminator!", &BB);
    2267             : 
    2268             :   // Check constraints that this basic block imposes on all of the PHI nodes in
    2269             :   // it.
    2270     1143200 :   if (isa<PHINode>(BB.front())) {
    2271             :     SmallVector<BasicBlock*, 8> Preds(pred_begin(&BB), pred_end(&BB));
    2272             :     SmallVector<std::pair<BasicBlock*, Value*>, 8> Values;
    2273             :     llvm::sort(Preds.begin(), Preds.end());
    2274       57435 :     for (const PHINode &PN : BB.phis()) {
    2275             :       // Ensure that PHI nodes have at least one entry!
    2276       80224 :       Assert(PN.getNumIncomingValues() != 0,
    2277             :              "PHI nodes must have at least one entry.  If the block is dead, "
    2278             :              "the PHI should be removed!",
    2279             :              &PN);
    2280      160448 :       Assert(PN.getNumIncomingValues() == Preds.size(),
    2281             :              "PHINode should have one entry for each predecessor of its "
    2282             :              "parent basic block!",
    2283             :              &PN);
    2284             : 
    2285             :       // Get and sort all incoming values in the PHI node...
    2286             :       Values.clear();
    2287       80224 :       Values.reserve(PN.getNumIncomingValues());
    2288      408518 :       for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
    2289      164147 :         Values.push_back(
    2290      328294 :             std::make_pair(PN.getIncomingBlock(i), PN.getIncomingValue(i)));
    2291             :       llvm::sort(Values.begin(), Values.end());
    2292             : 
    2293      244370 :       for (unsigned i = 0, e = Values.size(); i != e; ++i) {
    2294             :         // Check to make sure that if there is more than one entry for a
    2295             :         // particular basic block in this PHI node, that the incoming values are
    2296             :         // all identical.
    2297             :         //
    2298      331994 :         Assert(i == 0 || Values[i].first != Values[i - 1].first ||
    2299             :                    Values[i].second == Values[i - 1].second,
    2300             :                "PHI node has multiple entries for the same basic block with "
    2301             :                "different incoming values!",
    2302             :                &PN, Values[i].first, Values[i].second, Values[i - 1].second);
    2303             : 
    2304             :         // Check to make sure that the predecessors and PHI node entries are
    2305             :         // matched up.
    2306      492438 :         Assert(Values[i].first == Preds[i],
    2307             :                "PHI node entries do not match predecessors!", &PN,
    2308             :                Values[i].first, Preds[i]);
    2309             :       }
    2310             :     }
    2311             :   }
    2312             : 
    2313             :   // Check that all instructions have their parent pointers set up correctly.
    2314     7173398 :   for (auto &I : BB)
    2315             :   {
    2316     6030199 :     Assert(I.getParent() == &BB, "Instruction has bogus parent pointer!");
    2317             :   }
    2318             : }
    2319             : 
    2320     1143183 : void Verifier::visitTerminatorInst(TerminatorInst &I) {
    2321             :   // Ensure that terminators only exist at the end of the basic block.
    2322     2286366 :   Assert(&I == I.getParent()->getTerminator(),
    2323             :          "Terminator found in the middle of a basic block!", I.getParent());
    2324     1143183 :   visitInstruction(I);
    2325             : }
    2326             : 
    2327      326825 : void Verifier::visitBranchInst(BranchInst &BI) {
    2328      326825 :   if (BI.isConditional()) {
    2329      133049 :     Assert(BI.getCondition()->getType()->isIntegerTy(1),
    2330             :            "Branch condition is not 'i1' type!", &BI, BI.getCondition());
    2331             :   }
    2332      326824 :   visitTerminatorInst(BI);
    2333             : }
    2334             : 
    2335      789617 : void Verifier::visitReturnInst(ReturnInst &RI) {
    2336      789617 :   Function *F = RI.getParent()->getParent();
    2337             :   unsigned N = RI.getNumOperands();
    2338      789617 :   if (F->getReturnType()->isVoidTy())
    2339      268419 :     Assert(N == 0,
    2340             :            "Found return instr that returns non-void in Function of void "
    2341             :            "return type!",
    2342             :            &RI, F->getReturnType());
    2343             :   else
    2344     1042396 :     Assert(N == 1 && F->getReturnType() == RI.getOperand(0)->getType(),
    2345             :            "Function return type does not match operand "
    2346             :            "type of return inst!",
    2347             :            &RI, F->getReturnType());
    2348             : 
    2349             :   // Check to make sure that the return value has necessary properties for
    2350             :   // terminators...
    2351      789617 :   visitTerminatorInst(RI);
    2352             : }
    2353             : 
    2354        4067 : void Verifier::visitSwitchInst(SwitchInst &SI) {
    2355             :   // Check to make sure that all of the constants in the switch instruction
    2356             :   // have the same type as the switched-on value.
    2357        4067 :   Type *SwitchTy = SI.getCondition()->getType();
    2358             :   SmallPtrSet<ConstantInt*, 32> Constants;
    2359       26556 :   for (auto &Case : SI.cases()) {
    2360       18422 :     Assert(Case.getCaseValue()->getType() == SwitchTy,
    2361             :            "Switch constants must all be same type as switch value!", &SI);
    2362       18422 :     Assert(Constants.insert(Case.getCaseValue()).second,
    2363             :            "Duplicate integer as switch case", &SI, Case.getCaseValue());
    2364             :   }
    2365             : 
    2366        4067 :   visitTerminatorInst(SI);
    2367             : }
    2368             : 
    2369         744 : void Verifier::visitIndirectBrInst(IndirectBrInst &BI) {
    2370        1488 :   Assert(BI.getAddress()->getType()->isPointerTy(),
    2371             :          "Indirectbr operand must have pointer type!", &BI);
    2372        2830 :   for (unsigned i = 0, e = BI.getNumDestinations(); i != e; ++i)
    2373        4172 :     Assert(BI.getDestination(i)->getType()->isLabelTy(),
    2374             :            "Indirectbr destinations must all have pointer type!", &BI);
    2375             : 
    2376         744 :   visitTerminatorInst(BI);
    2377             : }
    2378             : 
    2379       96976 : void Verifier::visitSelectInst(SelectInst &SI) {
    2380       96976 :   Assert(!SelectInst::areInvalidOperands(SI.getOperand(0), SI.getOperand(1),
    2381             :                                          SI.getOperand(2)),
    2382             :          "Invalid operands for select instruction!", &SI);
    2383             : 
    2384       96976 :   Assert(SI.getTrueValue()->getType() == SI.getType(),
    2385             :          "Select values must have same type as select instruction!", &SI);
    2386       96976 :   visitInstruction(SI);
    2387             : }
    2388             : 
    2389             : /// visitUserOp1 - User defined operators shouldn't live beyond the lifetime of
    2390             : /// a pass, if any exist, it's an error.
    2391             : ///
    2392             : void Verifier::visitUserOp1(Instruction &I) {
    2393           0 :   Assert(false, "User-defined operators should not live outside of a pass!", &I);
    2394             : }
    2395             : 
    2396       42221 : void Verifier::visitTruncInst(TruncInst &I) {
    2397             :   // Get the source and destination types
    2398       42221 :   Type *SrcTy = I.getOperand(0)->getType();
    2399       42221 :   Type *DestTy = I.getType();
    2400             : 
    2401             :   // Get the size of the types in bits, we'll need this later
    2402       42221 :   unsigned SrcBitSize = SrcTy->getScalarSizeInBits();
    2403       42221 :   unsigned DestBitSize = DestTy->getScalarSizeInBits();
    2404             : 
    2405       42221 :   Assert(SrcTy->isIntOrIntVectorTy(), "Trunc only operates on integer", &I);
    2406       42221 :   Assert(DestTy->isIntOrIntVectorTy(), "Trunc only produces integer", &I);
    2407       42221 :   Assert(SrcTy->isVectorTy() == DestTy->isVectorTy(),
    2408             :          "trunc source and destination must both be a vector or neither", &I);
    2409       42221 :   Assert(SrcBitSize > DestBitSize, "DestTy too big for Trunc", &I);
    2410             : 
    2411       42221 :   visitInstruction(I);
    2412             : }
    2413             : 
    2414       59966 : void Verifier::visitZExtInst(ZExtInst &I) {
    2415             :   // Get the source and destination types
    2416       59966 :   Type *SrcTy = I.getOperand(0)->getType();
    2417       59966 :   Type *DestTy = I.getType();
    2418             : 
    2419             :   // Get the size of the types in bits, we'll need this later
    2420       59966 :   Assert(SrcTy->isIntOrIntVectorTy(), "ZExt only operates on integer", &I);
    2421       59966 :   Assert(DestTy->isIntOrIntVectorTy(), "ZExt only produces an integer", &I);
    2422       59966 :   Assert(SrcTy->isVectorTy() == DestTy->isVectorTy(),
    2423             :          "zext source and destination must both be a vector or neither", &I);
    2424       59966 :   unsigned SrcBitSize = SrcTy->getScalarSizeInBits();
    2425       59966 :   unsigned DestBitSize = DestTy->getScalarSizeInBits();
    2426             : 
    2427       59966 :   Assert(SrcBitSize < DestBitSize, "Type too small for ZExt", &I);
    2428             : 
    2429       59966 :   visitInstruction(I);
    2430             : }
    2431             : 
    2432       59516 : void Verifier::visitSExtInst(SExtInst &I) {
    2433             :   // Get the source and destination types
    2434       59516 :   Type *SrcTy = I.getOperand(0)->getType();
    2435       59516 :   Type *DestTy = I.getType();
    2436             : 
    2437             :   // Get the size of the types in bits, we'll need this later
    2438       59516 :   unsigned SrcBitSize = SrcTy->getScalarSizeInBits();
    2439       59516 :   unsigned DestBitSize = DestTy->getScalarSizeInBits();
    2440             : 
    2441       59516 :   Assert(SrcTy->isIntOrIntVectorTy(), "SExt only operates on integer", &I);
    2442       59516 :   Assert(DestTy->isIntOrIntVectorTy(), "SExt only produces an integer", &I);
    2443       59516 :   Assert(SrcTy->isVectorTy() == DestTy->isVectorTy(),
    2444             :          "sext source and destination must both be a vector or neither", &I);
    2445       59516 :   Assert(SrcBitSize < DestBitSize, "Type too small for SExt", &I);
    2446             : 
    2447       59516 :   visitInstruction(I);
    2448             : }
    2449             : 
    2450        4559 : void Verifier::visitFPTruncInst(FPTruncInst &I) {
    2451             :   // Get the source and destination types
    2452        4559 :   Type *SrcTy = I.getOperand(0)->getType();
    2453        4559 :   Type *DestTy = I.getType();
    2454             :   // Get the size of the types in bits, we'll need this later
    2455        4559 :   unsigned SrcBitSize = SrcTy->getScalarSizeInBits();
    2456        4559 :   unsigned DestBitSize = DestTy->getScalarSizeInBits();
    2457             : 
    2458           0 :   Assert(SrcTy->isFPOrFPVectorTy(), "FPTrunc only operates on FP", &I);
    2459           0 :   Assert(DestTy->isFPOrFPVectorTy(), "FPTrunc only produces an FP", &I);
    2460        4559 :   Assert(SrcTy->isVectorTy() == DestTy->isVectorTy(),
    2461             :          "fptrunc source and destination must both be a vector or neither", &I);
    2462        4559 :   Assert(SrcBitSize > DestBitSize, "DestTy too big for FPTrunc", &I);
    2463             : 
    2464        4559 :   visitInstruction(I);
    2465             : }
    2466             : 
    2467       10101 : void Verifier::visitFPExtInst(FPExtInst &I) {
    2468             :   // Get the source and destination types
    2469       10101 :   Type *SrcTy = I.getOperand(0)->getType();
    2470       10101 :   Type *DestTy = I.getType();
    2471             : 
    2472             :   // Get the size of the types in bits, we'll need this later
    2473       10101 :   unsigned SrcBitSize = SrcTy->getScalarSizeInBits();
    2474       10101 :   unsigned DestBitSize = DestTy->getScalarSizeInBits();
    2475             : 
    2476           0 :   Assert(SrcTy->isFPOrFPVectorTy(), "FPExt only operates on FP", &I);
    2477           0 :   Assert(DestTy->isFPOrFPVectorTy(), "FPExt only produces an FP", &I);
    2478       10101 :   Assert(SrcTy->isVectorTy() == DestTy->isVectorTy(),
    2479             :          "fpext source and destination must both be a vector or neither", &I);
    2480       10101 :   Assert(SrcBitSize < DestBitSize, "DestTy too small for FPExt", &I);
    2481             : 
    2482       10101 :   visitInstruction(I);
    2483             : }
    2484             : 
    2485        8726 : void Verifier::visitUIToFPInst(UIToFPInst &I) {
    2486             :   // Get the source and destination types
    2487        8726 :   Type *SrcTy = I.getOperand(0)->getType();
    2488        8726 :   Type *DestTy = I.getType();
    2489             : 
    2490             :   bool SrcVec = SrcTy->isVectorTy();
    2491             :   bool DstVec = DestTy->isVectorTy();
    2492             : 
    2493        8726 :   Assert(SrcVec == DstVec,
    2494             :          "UIToFP source and dest must both be vector or scalar", &I);
    2495        8726 :   Assert(SrcTy->isIntOrIntVectorTy(),
    2496             :          "UIToFP source must be integer or integer vector", &I);
    2497           0 :   Assert(DestTy->isFPOrFPVectorTy(), "UIToFP result must be FP or FP vector",
    2498             :          &I);
    2499             : 
    2500        8726 :   if (SrcVec && DstVec)
    2501        4015 :     Assert(cast<VectorType>(SrcTy)->getNumElements() ==
    2502             :                cast<VectorType>(DestTy)->getNumElements(),
    2503             :            "UIToFP source and dest vector length mismatch", &I);
    2504             : 
    2505        8726 :   visitInstruction(I);
    2506             : }
    2507             : 
    2508       14493 : void Verifier::visitSIToFPInst(SIToFPInst &I) {
    2509             :   // Get the source and destination types
    2510       14493 :   Type *SrcTy = I.getOperand(0)->getType();
    2511       14493 :   Type *DestTy = I.getType();
    2512             : 
    2513             :   bool SrcVec = SrcTy->isVectorTy();
    2514             :   bool DstVec = DestTy->isVectorTy();
    2515             : 
    2516       14493 :   Assert(SrcVec == DstVec,
    2517             :          "SIToFP source and dest must both be vector or scalar", &I);
    2518       14493 :   Assert(SrcTy->isIntOrIntVectorTy(),
    2519             :          "SIToFP source must be integer or integer vector", &I);
    2520           0 :   Assert(DestTy->isFPOrFPVectorTy(), "SIToFP result must be FP or FP vector",
    2521             :          &I);
    2522             : 
    2523       14493 :   if (SrcVec && DstVec)
    2524        4893 :     Assert(cast<VectorType>(SrcTy)->getNumElements() ==
    2525             :                cast<VectorType>(DestTy)->getNumElements(),
    2526             :            "SIToFP source and dest vector length mismatch", &I);
    2527             : 
    2528       14493 :   visitInstruction(I);
    2529             : }
    2530             : 
    2531        6319 : void Verifier::visitFPToUIInst(FPToUIInst &I) {
    2532             :   // Get the source and destination types
    2533        6319 :   Type *SrcTy = I.getOperand(0)->getType();
    2534        6319 :   Type *DestTy = I.getType();
    2535             : 
    2536             :   bool SrcVec = SrcTy->isVectorTy();
    2537             :   bool DstVec = DestTy->isVectorTy();
    2538             : 
    2539        6319 :   Assert(SrcVec == DstVec,
    2540             :          "FPToUI source and dest must both be vector or scalar", &I);
    2541           0 :   Assert(SrcTy->isFPOrFPVectorTy(), "FPToUI source must be FP or FP vector",
    2542             :          &I);
    2543        6319 :   Assert(DestTy->isIntOrIntVectorTy(),
    2544             :          "FPToUI result must be integer or integer vector", &I);
    2545             : 
    2546        6319 :   if (SrcVec && DstVec)
    2547        2132 :     Assert(cast<VectorType>(SrcTy)->getNumElements() ==
    2548             :                cast<VectorType>(DestTy)->getNumElements(),
    2549             :            "FPToUI source and dest vector length mismatch", &I);
    2550             : 
    2551        6319 :   visitInstruction(I);
    2552             : }
    2553             : 
    2554        8773 : void Verifier::visitFPToSIInst(FPToSIInst &I) {
    2555             :   // Get the source and destination types
    2556        8773 :   Type *SrcTy = I.getOperand(0)->getType();
    2557        8773 :   Type *DestTy = I.getType();
    2558             : 
    2559             :   bool SrcVec = SrcTy->isVectorTy();
    2560             :   bool DstVec = DestTy->isVectorTy();
    2561             : 
    2562        8773 :   Assert(SrcVec == DstVec,
    2563             :          "FPToSI source and dest must both be vector or scalar", &I);
    2564           0 :   Assert(SrcTy->isFPOrFPVectorTy(), "FPToSI source must be FP or FP vector",
    2565             :          &I);
    2566        8773 :   Assert(DestTy->isIntOrIntVectorTy(),
    2567             :          "FPToSI result must be integer or integer vector", &I);
    2568             : 
    2569        8773 :   if (SrcVec && DstVec)
    2570        2605 :     Assert(cast<VectorType>(SrcTy)->getNumElements() ==
    2571             :                cast<VectorType>(DestTy)->getNumElements(),
    2572             :            "FPToSI source and dest vector length mismatch", &I);
    2573             : 
    2574        8773 :   visitInstruction(I);
    2575             : }
    2576             : 
    2577        8204 : void Verifier::visitPtrToIntInst(PtrToIntInst &I) {
    2578             :   // Get the source and destination types
    2579        8204 :   Type *SrcTy = I.getOperand(0)->getType();
    2580        8204 :   Type *DestTy = I.getType();
    2581             : 
    2582        8204 :   Assert(SrcTy->isPtrOrPtrVectorTy(), "PtrToInt source must be pointer", &I);
    2583             : 
    2584             :   if (auto *PTy = dyn_cast<PointerType>(SrcTy->getScalarType()))
    2585        8207 :     Assert(!DL.isNonIntegralPointerType(PTy),
    2586             :            "ptrtoint not supported for non-integral pointers");
    2587             : 
    2588        8201 :   Assert(DestTy->isIntOrIntVectorTy(), "PtrToInt result must be integral", &I);
    2589        8201 :   Assert(SrcTy->isVectorTy() == DestTy->isVectorTy(), "PtrToInt type mismatch",
    2590             :          &I);
    2591             : 
    2592        8201 :   if (SrcTy->isVectorTy()) {
    2593             :     VectorType *VSrc = dyn_cast<VectorType>(SrcTy);
    2594             :     VectorType *VDest = dyn_cast<VectorType>(DestTy);
    2595          56 :     Assert(VSrc->getNumElements() == VDest->getNumElements(),
    2596             :            "PtrToInt Vector width mismatch", &I);
    2597             :   }
    2598             : 
    2599        8201 :   visitInstruction(I);
    2600             : }
    2601             : 
    2602       21563 : void Verifier::visitIntToPtrInst(IntToPtrInst &I) {
    2603             :   // Get the source and destination types
    2604       21563 :   Type *SrcTy = I.getOperand(0)->getType();
    2605       21563 :   Type *DestTy = I.getType();
    2606             : 
    2607       21563 :   Assert(SrcTy->isIntOrIntVectorTy(),
    2608             :          "IntToPtr source must be an integral", &I);
    2609       21563 :   Assert(DestTy->isPtrOrPtrVectorTy(), "IntToPtr result must be a pointer", &I);
    2610             : 
    2611             :   if (auto *PTy = dyn_cast<PointerType>(DestTy->getScalarType()))
    2612       21565 :     Assert(!DL.isNonIntegralPointerType(PTy),
    2613             :            "inttoptr not supported for non-integral pointers");
    2614             : 
    2615       21561 :   Assert(SrcTy->isVectorTy() == DestTy->isVectorTy(), "IntToPtr type mismatch",
    2616             :          &I);
    2617       21561 :   if (SrcTy->isVectorTy()) {
    2618             :     VectorType *VSrc = dyn_cast<VectorType>(SrcTy);
    2619             :     VectorType *VDest = dyn_cast<VectorType>(DestTy);
    2620          51 :     Assert(VSrc->getNumElements() == VDest->getNumElements(),
    2621             :            "IntToPtr Vector width mismatch", &I);
    2622             :   }
    2623       21561 :   visitInstruction(I);
    2624             : }
    2625             : 
    2626      355323 : void Verifier::visitBitCastInst(BitCastInst &I) {
    2627      710646 :   Assert(
    2628             :       CastInst::castIsValid(Instruction::BitCast, I.getOperand(0), I.getType()),
    2629             :       "Invalid bitcast", &I);
    2630      355323 :   visitInstruction(I);
    2631             : }
    2632             : 
    2633        1727 : void Verifier::visitAddrSpaceCastInst(AddrSpaceCastInst &I) {
    2634        1727 :   Type *SrcTy = I.getOperand(0)->getType();
    2635        1727 :   Type *DestTy = I.getType();
    2636             : 
    2637        1727 :   Assert(SrcTy->isPtrOrPtrVectorTy(), "AddrSpaceCast source must be a pointer",
    2638             :          &I);
    2639        1727 :   Assert(DestTy->isPtrOrPtrVectorTy(), "AddrSpaceCast result must be a pointer",
    2640             :          &I);
    2641        1727 :   Assert(SrcTy->getPointerAddressSpace() != DestTy->getPointerAddressSpace(),
    2642             :          "AddrSpaceCast must be between different address spaces", &I);
    2643        1727 :   if (SrcTy->isVectorTy())
    2644          37 :     Assert(SrcTy->getVectorNumElements() == DestTy->getVectorNumElements(),
    2645             :            "AddrSpaceCast vector pointer number of elements mismatch", &I);
    2646        1727 :   visitInstruction(I);
    2647             : }
    2648             : 
    2649             : /// visitPHINode - Ensure that a PHI node is well formed.
    2650             : ///
    2651       80225 : void Verifier::visitPHINode(PHINode &PN) {
    2652             :   // Ensure that the PHI nodes are all grouped together at the top of the block.
    2653             :   // This can be tested by checking whether the instruction before this is
    2654             :   // either nonexistent (because this is begin()) or is a PHI node.  If not,
    2655             :   // then there is some other instruction before a PHI.
    2656      183241 :   Assert(&PN == &PN.getParent()->front() ||
    2657             :              isa<PHINode>(--BasicBlock::iterator(&PN)),
    2658             :          "PHI nodes not grouped at top of basic block!", &PN, PN.getParent());
    2659             : 
    2660             :   // Check that a PHI doesn't yield a Token.
    2661      160449 :   Assert(!PN.getType()->isTokenTy(), "PHI nodes cannot have token type!");
    2662             : 
    2663             :   // Check that all of the values of the PHI node have the same type as the
    2664             :   // result, and that the incoming blocks are really basic blocks.
    2665      408513 :   for (Value *IncValue : PN.incoming_values()) {
    2666      164145 :     Assert(PN.getType() == IncValue->getType(),
    2667             :            "PHI node operands are not the same type as the result!", &PN);
    2668             :   }
    2669             : 
    2670             :   // All other PHI node constraints are checked in the visitBasicBlock method.
    2671             : 
    2672       80223 :   visitInstruction(PN);
    2673             : }
    2674             : 
    2675      607219 : void Verifier::verifyCallSite(CallSite CS) {
    2676      607219 :   Instruction *I = CS.getInstruction();
    2677             : 
    2678     1214449 :   Assert(CS.getCalledValue()->getType()->isPointerTy(),
    2679             :          "Called function must be a pointer!", I);
    2680             :   PointerType *FPTy = cast<PointerType>(CS.getCalledValue()->getType());
    2681             : 
    2682     1214438 :   Assert(FPTy->getElementType()->isFunctionTy(),
    2683             :          "Called function is not pointer to function type!", I);
    2684             : 
    2685      607219 :   Assert(FPTy->getElementType() == CS.getFunctionType(),
    2686             :          "Called function is not the same type as the call!", I);
    2687             : 
    2688             :   FunctionType *FTy = CS.getFunctionType();
    2689             : 
    2690             :   // Verify that the correct number of arguments are being passed
    2691      607219 :   if (FTy->isVarArg())
    2692       41086 :     Assert(CS.arg_size() >= FTy->getNumParams(),
    2693             :            "Called function requires more parameters than were provided!", I);
    2694             :   else
    2695     1173353 :     Assert(CS.arg_size() == FTy->getNumParams(),
    2696             :            "Incorrect number of arguments passed to called function!", I);
    2697             : 
    2698             :   // Verify that all arguments to the call match the function type.
    2699     2343853 :   for (unsigned i = 0, e = FTy->getNumParams(); i != e; ++i)
    2700     2258826 :     Assert(CS.getArgument(i)->getType() == FTy->getParamType(i),
    2701             :            "Call parameter type does not match function signature!",
    2702             :            CS.getArgument(i), FTy->getParamType(i), I);
    2703             : 
    2704      607220 :   AttributeList Attrs = CS.getAttributes();
    2705             : 
    2706     1214440 :   Assert(verifyAttributeCount(Attrs, CS.arg_size()),
    2707             :          "Attribute after last parameter!", I);
    2708             : 
    2709      607220 :   if (Attrs.hasAttribute(AttributeList::FunctionIndex, Attribute::Speculatable)) {
    2710             :     // Don't allow speculatable on call sites, unless the underlying function
    2711             :     // declaration is also speculatable.
    2712             :     Function *Callee
    2713             :       = dyn_cast<Function>(CS.getCalledValue()->stripPointerCasts());
    2714         322 :     Assert(Callee && Callee->isSpeculatable(),
    2715             :            "speculatable attribute may not apply to call sites", I);
    2716             :   }
    2717             : 
    2718             :   // Verify call attributes.
    2719      607218 :   verifyFunctionAttrs(FTy, Attrs, I);
    2720             : 
    2721             :   // Conservatively check the inalloca argument.
    2722             :   // We have a bug if we can find that there is an underlying alloca without
    2723             :   // inalloca.
    2724      607218 :   if (CS.hasInAllocaArgument()) {
    2725         178 :     Value *InAllocaArg = CS.getArgument(FTy->getNumParams() - 1);
    2726         178 :     if (auto AI = dyn_cast<AllocaInst>(InAllocaArg->stripInBoundsOffsets()))
    2727         134 :       Assert(AI->isUsedWithInAlloca(),
    2728             :              "inalloca argument for call has mismatched alloca", AI, I);
    2729             :   }
    2730             : 
    2731             :   // For each argument of the callsite, if it has the swifterror argument,
    2732             :   // make sure the underlying alloca/parameter it comes from has a swifterror as
    2733             :   // well.
    2734     3473256 :   for (unsigned i = 0, e = FTy->getNumParams(); i != e; ++i)
    2735     1129412 :     if (CS.paramHasAttr(i, Attribute::SwiftError)) {
    2736         422 :       Value *SwiftErrorArg = CS.getArgument(i);
    2737         694 :       if (auto AI = dyn_cast<AllocaInst>(SwiftErrorArg->stripInBoundsOffsets())) {
    2738         274 :         Assert(AI->isSwiftError(),
    2739             :                "swifterror argument for call has mismatched alloca", AI, I);
    2740         272 :         continue;
    2741             :       }
    2742         298 :       auto ArgI = dyn_cast<Argument>(SwiftErrorArg);
    2743         149 :       Assert(ArgI, "swifterror argument should come from an alloca or parameter", SwiftErrorArg, I);
    2744         149 :       Assert(ArgI->hasSwiftErrorAttr(),
    2745             :              "swifterror argument for call has mismatched parameter", ArgI, I);
    2746             :     }
    2747             : 
    2748      607216 :   if (FTy->isVarArg()) {
    2749             :     // FIXME? is 'nest' even legal here?
    2750             :     bool SawNest = false;
    2751             :     bool SawReturned = false;
    2752             : 
    2753      140347 :     for (unsigned Idx = 0; Idx < FTy->getNumParams(); ++Idx) {
    2754       33087 :       if (Attrs.hasParamAttribute(Idx, Attribute::Nest))
    2755             :         SawNest = true;
    2756       33087 :       if (Attrs.hasParamAttribute(Idx, Attribute::Returned))
    2757             :         SawReturned = true;
    2758             :     }
    2759             : 
    2760             :     // Check attributes on the varargs part.
    2761       90145 :     for (unsigned Idx = FTy->getNumParams(); Idx < CS.arg_size(); ++Idx) {
    2762       34803 :       Type *Ty = CS.getArgument(Idx)->getType();
    2763       34803 :       AttributeSet ArgAttrs = Attrs.getParamAttributes(Idx);
    2764       34803 :       verifyParameterAttrs(ArgAttrs, Ty, I);
    2765             : 
    2766       34803 :       if (ArgAttrs.hasAttribute(Attribute::Nest)) {
    2767          11 :         Assert(!SawNest, "More than one parameter has attribute nest!", I);
    2768             :         SawNest = true;
    2769             :       }
    2770             : 
    2771       34803 :       if (ArgAttrs.hasAttribute(Attribute::Returned)) {
    2772           0 :         Assert(!SawReturned, "More than one parameter has attribute returned!",
    2773             :                I);
    2774           0 :         Assert(Ty->canLosslesslyBitCastTo(FTy->getReturnType()),
    2775             :                "Incompatible argument and return types for 'returned' "
    2776             :                "attribute",
    2777             :                I);
    2778             :         SawReturned = true;
    2779             :       }
    2780             : 
    2781       34804 :       Assert(!ArgAttrs.hasAttribute(Attribute::StructRet),
    2782             :              "Attribute 'sret' cannot be used for vararg call arguments!", I);
    2783             : 
    2784       34802 :       if (ArgAttrs.hasAttribute(Attribute::InAlloca))
    2785           2 :         Assert(Idx == CS.arg_size() - 1, "inalloca isn't on the last argument!",
    2786             :                I);
    2787             :     }
    2788             :   }
    2789             : 
    2790             :   // Verify that there's no metadata unless it's a direct call to an intrinsic.
    2791             :   if (CS.getCalledFunction() == nullptr ||
    2792      868045 :       !CS.getCalledFunction()->getName().startswith("llvm.")) {
    2793     1166473 :     for (Type *ParamTy : FTy->params()) {
    2794      440446 :       Assert(!ParamTy->isMetadataTy(),
    2795             :              "Function has metadata parameter but isn't an intrinsic", I);
    2796      440446 :       Assert(!ParamTy->isTokenTy(),
    2797             :              "Function has token parameter but isn't an intrinsic", I);
    2798             :     }
    2799             :   }
    2800             : 
    2801             :   // Verify that indirect calls don't return tokens.
    2802             :   if (CS.getCalledFunction() == nullptr)
    2803      121605 :     Assert(!FTy->getReturnType()->isTokenTy(),
    2804             :            "Return type cannot be token for indirect call!");
    2805             : 
    2806             :   if (Function *F = CS.getCalledFunction())
    2807      546412 :     if (Intrinsic::ID ID = (Intrinsic::ID)F->getIntrinsicID())
    2808      319582 :       visitIntrinsicCallSite(ID, CS);
    2809             : 
    2810             :   // Verify that a callsite has at most one "deopt", at most one "funclet" and
    2811             :   // at most one "gc-transition" operand bundle.
    2812             :   bool FoundDeoptBundle = false, FoundFuncletBundle = false,
    2813             :        FoundGCTransitionBundle = false;
    2814      609855 :   for (unsigned i = 0, e = CS.getNumOperandBundles(); i < e; ++i) {
    2815        2644 :     OperandBundleUse BU = CS.getOperandBundleAt(i);
    2816        2644 :     uint32_t Tag = BU.getTagID();
    2817        2644 :     if (Tag == LLVMContext::OB_deopt) {
    2818        1295 :       Assert(!FoundDeoptBundle, "Multiple deopt operand bundles", I);
    2819             :       FoundDeoptBundle = true;
    2820        1352 :     } else if (Tag == LLVMContext::OB_gc_transition) {
    2821           7 :       Assert(!FoundGCTransitionBundle, "Multiple gc-transition operand bundles",
    2822             :              I);
    2823             :       FoundGCTransitionBundle = true;
    2824        1346 :     } else if (Tag == LLVMContext::OB_funclet) {
    2825        1095 :       Assert(!FoundFuncletBundle, "Multiple funclet operand bundles", I);
    2826             :       FoundFuncletBundle = true;
    2827        1095 :       Assert(BU.Inputs.size() == 1,
    2828             :              "Expected exactly one funclet bundle operand", I);
    2829        1095 :       Assert(isa<FuncletPadInst>(BU.Inputs.front()),
    2830             :              "Funclet bundle operands should correspond to a FuncletPadInst",
    2831             :              I);
    2832             :     }
    2833             :   }
    2834             : 
    2835             :   // Verify that each inlinable callsite of a debug-info-bearing function in a
    2836             :   // debug-info-bearing function has a debug location attached to it. Failure to
    2837             :   // do so causes assertion failures when the inliner sets up inline scope info.
    2838     1238476 :   if (I->getFunction()->getSubprogram() && CS.getCalledFunction() &&
    2839       24054 :       CS.getCalledFunction()->getSubprogram())
    2840        4988 :     AssertDI(I->getDebugLoc(), "inlinable function call in a function with "
    2841             :                                "debug info must have a !dbg location",
    2842             :              I);
    2843             : 
    2844      607209 :   visitInstruction(*I);
    2845             : }
    2846             : 
    2847             : /// Two types are "congruent" if they are identical, or if they are both pointer
    2848             : /// types with different pointee types and the same address space.
    2849             : static bool isTypeCongruent(Type *L, Type *R) {
    2850        1004 :   if (L == R)
    2851             :     return true;
    2852             :   PointerType *PL = dyn_cast<PointerType>(L);
    2853             :   PointerType *PR = dyn_cast<PointerType>(R);
    2854          58 :   if (!PL || !PR)
    2855             :     return false;
    2856          56 :   return PL->getAddressSpace() == PR->getAddressSpace();
    2857             : }
    2858             : 
    2859        1056 : static AttrBuilder getParameterABIAttributes(int I, AttributeList Attrs) {
    2860             :   static const Attribute::AttrKind ABIAttrs[] = {
    2861             :       Attribute::StructRet, Attribute::ByVal, Attribute::InAlloca,
    2862             :       Attribute::InReg, Attribute::Returned, Attribute::SwiftSelf,
    2863             :       Attribute::SwiftError};
    2864             :   AttrBuilder Copy;
    2865       15840 :   for (auto AK : ABIAttrs) {
    2866        7392 :     if (Attrs.hasParamAttribute(I, AK))
    2867         155 :       Copy.addAttribute(AK);
    2868             :   }
    2869        1056 :   if (Attrs.hasParamAttribute(I, Attribute::Alignment))
    2870           2 :     Copy.addAlignmentAttr(Attrs.getParamAlignment(I));
    2871        1056 :   return Copy;
    2872             : }
    2873             : 
    2874         521 : void Verifier::verifyMustTailCall(CallInst &CI) {
    2875         533 :   Assert(!CI.isInlineAsm(), "cannot use musttail call with inline asm", &CI);
    2876             : 
    2877             :   // - The caller and callee prototypes must match.  Pointer types of
    2878             :   //   parameters or return types may differ in pointee type, but not
    2879             :   //   address space.
    2880         520 :   Function *F = CI.getParent()->getParent();
    2881             :   FunctionType *CallerTy = F->getFunctionType();
    2882         520 :   FunctionType *CalleeTy = CI.getFunctionType();
    2883         313 :   if (!CI.getCalledFunction() || !CI.getCalledFunction()->isIntrinsic()) {
    2884        1417 :     Assert(CallerTy->getNumParams() == CalleeTy->getNumParams(),
    2885             :            "cannot guarantee tail call due to mismatched parameter counts",
    2886             :            &CI);
    2887         957 :     for (int I = 0, E = CallerTy->getNumParams(); I != E; ++I) {
    2888         987 :       Assert(
    2889             :           isTypeCongruent(CallerTy->getParamType(I), CalleeTy->getParamType(I)),
    2890             :           "cannot guarantee tail call due to mismatched parameter types", &CI);
    2891             :     }
    2892             :   }
    2893         519 :   Assert(CallerTy->isVarArg() == CalleeTy->isVarArg(),
    2894             :          "cannot guarantee tail call due to mismatched varargs", &CI);
    2895        1079 :   Assert(isTypeCongruent(CallerTy->getReturnType(), CalleeTy->getReturnType()),
    2896             :          "cannot guarantee tail call due to mismatched return types", &CI);
    2897             : 
    2898             :   // - The calling conventions of the caller and callee must match.
    2899         517 :   Assert(F->getCallingConv() == CI.getCallingConv(),
    2900             :          "cannot guarantee tail call due to mismatched calling conv", &CI);
    2901             : 
    2902             :   // - All ABI-impacting function attributes, such as sret, byval, inreg,
    2903             :   //   returned, and inalloca, must match.
    2904         515 :   AttributeList CallerAttrs = F->getAttributes();
    2905         515 :   AttributeList CalleeAttrs = CI.getAttributes();
    2906        1554 :   for (int I = 0, E = CallerTy->getNumParams(); I != E; ++I) {
    2907         528 :     AttrBuilder CallerABIAttrs = getParameterABIAttributes(I, CallerAttrs);
    2908         528 :     AttrBuilder CalleeABIAttrs = getParameterABIAttributes(I, CalleeAttrs);
    2909         536 :     Assert(CallerABIAttrs == CalleeABIAttrs,
    2910             :            "cannot guarantee tail call due to mismatched ABI impacting "
    2911             :            "function attributes",
    2912             :            &CI, CI.getOperand(I));
    2913             :   }
    2914             : 
    2915             :   // - The call must immediately precede a :ref:`ret <i_ret>` instruction,
    2916             :   //   or a pointer bitcast followed by a ret instruction.
    2917             :   // - The ret instruction must return the (possibly bitcasted) value
    2918             :   //   produced by the call or void.
    2919         511 :   Value *RetVal = &CI;
    2920             :   Instruction *Next = CI.getNextNode();
    2921             : 
    2922             :   // Handle the optional bitcast.
    2923         511 :   if (BitCastInst *BI = dyn_cast_or_null<BitCastInst>(Next)) {
    2924          47 :     Assert(BI->getOperand(0) == RetVal,
    2925             :            "bitcast following musttail call must use the call", BI);
    2926             :     RetVal = BI;
    2927             :     Next = BI->getNextNode();
    2928             :   }
    2929             : 
    2930             :   // Check the return.
    2931         511 :   ReturnInst *Ret = dyn_cast_or_null<ReturnInst>(Next);
    2932         512 :   Assert(Ret, "musttail call must precede a ret with an optional bitcast",
    2933             :          &CI);
    2934         205 :   Assert(!Ret->getReturnValue() || Ret->getReturnValue() == RetVal,
    2935             :          "musttail call result must be returned", Ret);
    2936             : }
    2937             : 
    2938      600279 : void Verifier::visitCallInst(CallInst &CI) {
    2939      600279 :   verifyCallSite(&CI);
    2940             : 
    2941      600280 :   if (CI.isMustTailCall())
    2942         521 :     verifyMustTailCall(CI);
    2943      600280 : }
    2944             : 
    2945        6940 : void Verifier::visitInvokeInst(InvokeInst &II) {
    2946        6940 :   verifyCallSite(&II);
    2947             : 
    2948             :   // Verify that the first non-PHI instruction of the unwind destination is an
    2949             :   // exception handling instruction.
    2950        6947 :   Assert(
    2951             :       II.getUnwindDest()->isEHPad(),
    2952             :       "The unwind destination does not have an exception handling instruction!",
    2953             :       &II);
    2954             : 
    2955        6933 :   visitTerminatorInst(II);
    2956             : }
    2957             : 
    2958             : /// visitBinaryOperator - Check that both arguments to the binary operator are
    2959             : /// of the same type!
    2960             : ///
    2961      597128 : void Verifier::visitBinaryOperator(BinaryOperator &B) {
    2962     1194256 :   Assert(B.getOperand(0)->getType() == B.getOperand(1)->getType(),
    2963             :          "Both operands to a binary operator are not of the same type!", &B);
    2964             : 
    2965      597128 :   switch (B.getOpcode()) {
    2966             :   // Check that integer arithmetic operators are only used with
    2967             :   // integral operands.
    2968      289892 :   case Instruction::Add:
    2969             :   case Instruction::Sub:
    2970             :   case Instruction::Mul:
    2971             :   case Instruction::SDiv:
    2972             :   case Instruction::UDiv:
    2973             :   case Instruction::SRem:
    2974             :   case Instruction::URem:
    2975      579784 :     Assert(B.getType()->isIntOrIntVectorTy(),
    2976             :            "Integer arithmetic operators only work with integral types!", &B);
    2977      289892 :     Assert(B.getType() == B.getOperand(0)->getType(),
    2978             :            "Integer arithmetic operators must have same type "
    2979             :            "for operands and result!",
    2980             :            &B);
    2981             :     break;
    2982             :   // Check that floating-point arithmetic operators are only used with
    2983             :   // floating-point operands.
    2984      118486 :   case Instruction::FAdd:
    2985             :   case Instruction::FSub:
    2986             :   case Instruction::FMul:
    2987             :   case Instruction::FDiv:
    2988             :   case Instruction::FRem:
    2989      118486 :     Assert(B.getType()->isFPOrFPVectorTy(),
    2990             :            "Floating-point arithmetic operators only work with "
    2991             :            "floating-point types!",
    2992             :            &B);
    2993      118486 :     Assert(B.getType() == B.getOperand(0)->getType(),
    2994             :            "Floating-point arithmetic operators must have same type "
    2995             :            "for operands and result!",
    2996             :            &B);
    2997             :     break;
    2998             :   // Check that logical operators are only used with integral operands.
    2999      118320 :   case Instruction::And:
    3000             :   case Instruction::Or:
    3001             :   case Instruction::Xor:
    3002      236640 :     Assert(B.getType()->isIntOrIntVectorTy(),
    3003             :            "Logical operators only work with integral types!", &B);
    3004      118320 :     Assert(B.getType() == B.getOperand(0)->getType(),
    3005             :            "Logical operators must have same type for operands and result!",
    3006             :            &B);
    3007             :     break;
    3008       70430 :   case Instruction::Shl:
    3009             :   case Instruction::LShr:
    3010             :   case Instruction::AShr:
    3011      140860 :     Assert(B.getType()->isIntOrIntVectorTy(),
    3012             :            "Shifts only work with integral types!", &B);
    3013       70430 :     Assert(B.getType() == B.getOperand(0)->getType(),
    3014             :            "Shift return type must be same as operands!", &B);
    3015             :     break;
    3016           0 :   default:
    3017           0 :     llvm_unreachable("Unknown BinaryOperator opcode!");
    3018             :   }
    3019             : 
    3020      597128 :   visitInstruction(B);
    3021             : }
    3022             : 
    3023      216126 : void Verifier::visitICmpInst(ICmpInst &IC) {
    3024             :   // Check that the operands are the same type
    3025      216126 :   Type *Op0Ty = IC.getOperand(0)->getType();
    3026      216126 :   Type *Op1Ty = IC.getOperand(1)->getType();
    3027      216126 :   Assert(Op0Ty == Op1Ty,
    3028             :          "Both operands to ICmp instruction are not of the same type!", &IC);
    3029             :   // Check that the operands are the right type
    3030      216126 :   Assert(Op0Ty->isIntOrIntVectorTy() || Op0Ty->isPtrOrPtrVectorTy(),
    3031             :          "Invalid operand types for ICmp instruction", &IC);
    3032             :   // Check that the predicate is valid.
    3033      216126 :   Assert(IC.isIntPredicate(),
    3034             :          "Invalid predicate in ICmp instruction!", &IC);
    3035             : 
    3036      216126 :   visitInstruction(IC);
    3037             : }
    3038             : 
    3039       30522 : void Verifier::visitFCmpInst(FCmpInst &FC) {
    3040             :   // Check that the operands are the same type
    3041       30522 :   Type *Op0Ty = FC.getOperand(0)->getType();
    3042       30522 :   Type *Op1Ty = FC.getOperand(1)->getType();
    3043       30522 :   Assert(Op0Ty == Op1Ty,
    3044             :          "Both operands to FCmp instruction are not of the same type!", &FC);
    3045             :   // Check that the operands are the right type
    3046           0 :   Assert(Op0Ty->isFPOrFPVectorTy(),
    3047             :          "Invalid operand types for FCmp instruction", &FC);
    3048             :   // Check that the predicate is valid.
    3049       30522 :   Assert(FC.isFPPredicate(),
    3050             :          "Invalid predicate in FCmp instruction!", &FC);
    3051             : 
    3052       30522 :   visitInstruction(FC);
    3053             : }
    3054             : 
    3055      103103 : void Verifier::visitExtractElementInst(ExtractElementInst &EI) {
    3056      103103 :   Assert(
    3057             :       ExtractElementInst::isValidOperands(EI.getOperand(0), EI.getOperand(1)),
    3058             :       "Invalid extractelement operands!", &EI);
    3059      103103 :   visitInstruction(EI);
    3060             : }
    3061             : 
    3062      104142 : void Verifier::visitInsertElementInst(InsertElementInst &IE) {
    3063      104142 :   Assert(InsertElementInst::isValidOperands(IE.getOperand(0), IE.getOperand(1),
    3064             :                                             IE.getOperand(2)),
    3065             :          "Invalid insertelement operands!", &IE);
    3066      104142 :   visitInstruction(IE);
    3067             : }
    3068             : 
    3069      140589 : void Verifier::visitShuffleVectorInst(ShuffleVectorInst &SV) {
    3070      140589 :   Assert(ShuffleVectorInst::isValidOperands(SV.getOperand(0), SV.getOperand(1),
    3071             :                                             SV.getOperand(2)),
    3072             :          "Invalid shufflevector operands!", &SV);
    3073      140589 :   visitInstruction(SV);
    3074             : }
    3075             : 
    3076      405112 : void Verifier::visitGetElementPtrInst(GetElementPtrInst &GEP) {
    3077             :   Type *TargetTy = GEP.getPointerOperandType()->getScalarType();
    3078             : 
    3079      405113 :   Assert(isa<PointerType>(TargetTy),
    3080             :          "GEP base pointer is not a vector or a vector of pointers", &GEP);
    3081      405112 :   Assert(GEP.getSourceElementType()->isSized(), "GEP into unsized type!", &GEP);
    3082             : 
    3083             :   SmallVector<Value*, 16> Idxs(GEP.idx_begin(), GEP.idx_end());
    3084      966791 :   Assert(all_of(
    3085             :       Idxs, [](Value* V) { return V->getType()->isIntOrIntVectorTy(); }),
    3086             :       "GEP indexes must be integers", &GEP);
    3087             :   Type *ElTy =
    3088      405111 :       GetElementPtrInst::getIndexedType(GEP.getSourceElementType(), Idxs);
    3089      405111 :   Assert(ElTy, "Invalid indices for GEP pointer type!", &GEP);
    3090             : 
    3091      810222 :   Assert(GEP.getType()->isPtrOrPtrVectorTy() &&
    3092             :              GEP.getResultElementType() == ElTy,
    3093             :          "GEP is not of right type for indices!", &GEP, ElTy);
    3094             : 
    3095      405111 :   if (GEP.getType()->isVectorTy()) {
    3096             :     // Additional checks for vector GEPs.
    3097             :     unsigned GEPWidth = GEP.getType()->getVectorNumElements();
    3098        1262 :     if (GEP.getPointerOperandType()->isVectorTy())
    3099         483 :       Assert(GEPWidth == GEP.getPointerOperandType()->getVectorNumElements(),
    3100             :              "Vector GEP result width doesn't match operand's", &GEP);
    3101        4580 :     for (Value *Idx : Idxs) {
    3102        1659 :       Type *IndexTy = Idx->getType();
    3103        1659 :       if (IndexTy->isVectorTy()) {
    3104             :         unsigned IndexWidth = IndexTy->getVectorNumElements();
    3105        1380 :         Assert(IndexWidth == GEPWidth, "Invalid GEP index vector width", &GEP);
    3106             :       }
    3107        1659 :       Assert(IndexTy->isIntOrIntVectorTy(),
    3108             :              "All GEP indices should be of integer type");
    3109             :     }
    3110             :   }
    3111      405111 :   visitInstruction(GEP);
    3112             : }
    3113             : 
    3114          48 : static bool isContiguous(const ConstantRange &A, const ConstantRange &B) {
    3115          95 :   return A.getUpper() == B.getLower() || A.getLower() == B.getUpper();
    3116             : }
    3117             : 
    3118        8521 : void Verifier::visitRangeMetadata(Instruction &I, MDNode *Range, Type *Ty) {
    3119             :   assert(Range && Range == I.getMetadata(LLVMContext::MD_range) &&
    3120             :          "precondition violation");
    3121             : 
    3122        8521 :   unsigned NumOperands = Range->getNumOperands();
    3123        8539 :   Assert(NumOperands % 2 == 0, "Unfinished range!", Range);
    3124        8520 :   unsigned NumRanges = NumOperands / 2;
    3125        8522 :   Assert(NumRanges >= 1, "It should have at least one range!", Range);
    3126             : 
    3127       17022 :   ConstantRange LastRange(1); // Dummy initial value
    3128       25632 :   for (unsigned i = 0; i < NumRanges; ++i) {
    3129             :     ConstantInt *Low =
    3130       17138 :         mdconst::dyn_extract<ConstantInt>(Range->getOperand(2 * i));
    3131        8582 :     Assert(Low, "The lower limit must be an integer!", Low);
    3132             :     ConstantInt *High =
    3133       17136 :         mdconst::dyn_extract<ConstantInt>(Range->getOperand(2 * i + 1));
    3134        8569 :     Assert(High, "The upper limit must be an integer!", High);
    3135        8570 :     Assert(High->getType() == Low->getType() && High->getType() == Ty,
    3136             :            "Range types must match instruction type!", &I);
    3137             : 
    3138             :     APInt HighV = High->getValue();
    3139        8564 :     APInt LowV = Low->getValue();
    3140       34249 :     ConstantRange CurRange(LowV, HighV);
    3141        8573 :     Assert(!CurRange.isEmptySet() && !CurRange.isFullSet(),
    3142             :            "Range must not be empty!", Range);
    3143        8563 :     if (i != 0) {
    3144          54 :       Assert(CurRange.intersectWith(LastRange).isEmptySet(),
    3145             :              "Intervals are overlapping", Range);
    3146          49 :       Assert(LowV.sgt(LastRange.getLower()), "Intervals are not in order",
    3147             :              Range);
    3148          49 :       Assert(!isContiguous(CurRange, LastRange), "Intervals are contiguous",
    3149             :              Range);
    3150             :     }
    3151       25671 :     LastRange = ConstantRange(LowV, HighV);
    3152             :   }
    3153        8506 :   if (NumRanges > 2) {
    3154             :     APInt FirstLow =
    3155           2 :         mdconst::dyn_extract<ConstantInt>(Range->getOperand(0))->getValue();
    3156             :     APInt FirstHigh =
    3157           2 :         mdconst::dyn_extract<ConstantInt>(Range->getOperand(1))->getValue();
    3158           6 :     ConstantRange FirstRange(FirstLow, FirstHigh);
    3159           5 :     Assert(FirstRange.intersectWith(LastRange).isEmptySet(),
    3160             :            "Intervals are overlapping", Range);
    3161           2 :     Assert(!isContiguous(FirstRange, LastRange), "Intervals are contiguous",
    3162             :            Range);
    3163             :   }
    3164             : }
    3165             : 
    3166       28282 : void Verifier::checkAtomicMemAccessSize(Type *Ty, const Instruction *I) {
    3167       28282 :   unsigned Size = DL.getTypeSizeInBits(Ty);
    3168       28282 :   Assert(Size >= 8, "atomic memory access' size must be byte-sized", Ty, I);
    3169       28282 :   Assert(!(Size & (Size - 1)),
    3170             :          "atomic memory access' operand must have a power-of-two size", Ty, I);
    3171             : }
    3172             : 
    3173      784737 : void Verifier::visitLoadInst(LoadInst &LI) {
    3174      784737 :   PointerType *PTy = dyn_cast<PointerType>(LI.getOperand(0)->getType());
    3175           2 :   Assert(PTy, "Load operand must be a pointer.", &LI);
    3176      784737 :   Type *ElTy = LI.getType();
    3177      784737 :   Assert(LI.getAlignment() <= Value::MaximumAlignment,
    3178             :          "huge alignment values are unsupported", &LI);
    3179      784738 :   Assert(ElTy->isSized(), "loading unsized types is not allowed", &LI);
    3180      784736 :   if (LI.isAtomic()) {
    3181        3669 :     Assert(LI.getOrdering() != AtomicOrdering::Release &&
    3182             :                LI.getOrdering() != AtomicOrdering::AcquireRelease,
    3183             :            "Load cannot have Release ordering", &LI);
    3184        3669 :     Assert(LI.getAlignment() != 0,
    3185             :            "Atomic load must specify explicit alignment", &LI);
    3186        3671 :     Assert(ElTy->isIntOrPtrTy() || ElTy->isFloatingPointTy(),
    3187             :            "atomic load operand must have integer, pointer, or floating point "
    3188             :            "type!",
    3189             :            ElTy, &LI);
    3190        3668 :     checkAtomicMemAccessSize(ElTy, &LI);
    3191             :   } else {
    3192      781067 :     Assert(LI.getSyncScopeID() == SyncScope::System,
    3193             :            "Non-atomic load cannot have SynchronizationScope specified", &LI);
    3194             :   }
    3195             : 
    3196      784735 :   visitInstruction(LI);
    3197             : }
    3198             : 
    3199      666361 : void Verifier::visitStoreInst(StoreInst &SI) {
    3200      666361 :   PointerType *PTy = dyn_cast<PointerType>(SI.getOperand(1)->getType());
    3201           2 :   Assert(PTy, "Store operand must be a pointer.", &SI);
    3202      666361 :   Type *ElTy = PTy->getElementType();
    3203      666361 :   Assert(ElTy == SI.getOperand(0)->getType(),
    3204             :          "Stored value type does not match pointer operand type!", &SI, ElTy);
    3205      666361 :   Assert(SI.getAlignment() <= Value::MaximumAlignment,
    3206             :          "huge alignment values are unsupported", &SI);
    3207      666362 :   Assert(ElTy->isSized(), "storing unsized types is not allowed", &SI);
    3208      666360 :   if (SI.isAtomic()) {
    3209        3136 :     Assert(SI.getOrdering() != AtomicOrdering::Acquire &&
    3210             :                SI.getOrdering() != AtomicOrdering::AcquireRelease,
    3211             :            "Store cannot have Acquire ordering", &SI);
    3212        3136 :     Assert(SI.getAlignment() != 0,
    3213             :            "Atomic store must specify explicit alignment", &SI);
    3214        3138 :     Assert(ElTy->isIntOrPtrTy() || ElTy->isFloatingPointTy(),
    3215             :            "atomic store operand must have integer, pointer, or floating point "
    3216             :            "type!",
    3217             :            ElTy, &SI);
    3218        3135 :     checkAtomicMemAccessSize(ElTy, &SI);
    3219             :   } else {
    3220      663224 :     Assert(SI.getSyncScopeID() == SyncScope::System,
    3221             :            "Non-atomic store cannot have SynchronizationScope specified", &SI);
    3222             :   }
    3223      666359 :   visitInstruction(SI);
    3224             : }
    3225             : 
    3226             : /// Check that SwiftErrorVal is used as a swifterror argument in CS.
    3227         421 : void Verifier::verifySwiftErrorCallSite(CallSite CS,
    3228             :                                         const Value *SwiftErrorVal) {
    3229             :   unsigned Idx = 0;
    3230        1783 :   for (CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end();
    3231        1783 :        I != E; ++I, ++Idx) {
    3232        1362 :     if (*I == SwiftErrorVal) {
    3233         421 :       Assert(CS.paramHasAttr(Idx, Attribute::SwiftError),
    3234             :              "swifterror value when used in a callsite should be marked "
    3235             :              "with swifterror attribute",
    3236             :               SwiftErrorVal, CS);
    3237             :     }
    3238             :   }
    3239             : }
    3240             : 
    3241         809 : void Verifier::verifySwiftErrorValue(const Value *SwiftErrorVal) {
    3242             :   // Check that swifterror value is only used by loads, stores, or as
    3243             :   // a swifterror argument.
    3244        3805 :   for (const User *U : SwiftErrorVal->users()) {
    3245           3 :     Assert(isa<LoadInst>(U) || isa<StoreInst>(U) || isa<CallInst>(U) ||
    3246             :            isa<InvokeInst>(U),
    3247             :            "swifterror value can only be loaded and stored from, or "
    3248             :            "as a swifterror argument!",
    3249             :            SwiftErrorVal, U);
    3250             :     // If it is used by a store, check it is the second operand.
    3251             :     if (auto StoreI = dyn_cast<StoreInst>(U))
    3252         449 :       Assert(StoreI->getOperand(1) == SwiftErrorVal,
    3253             :              "swifterror value should be the second operand when used "
    3254             :              "by stores", SwiftErrorVal, U);
    3255             :     if (auto CallI = dyn_cast<CallInst>(U))
    3256         840 :       verifySwiftErrorCallSite(const_cast<CallInst*>(CallI), SwiftErrorVal);
    3257        1093 :     if (auto II = dyn_cast<InvokeInst>(U))
    3258           2 :       verifySwiftErrorCallSite(const_cast<InvokeInst*>(II), SwiftErrorVal);
    3259             :   }
    3260             : }
    3261             : 
    3262      394827 : void Verifier::visitAllocaInst(AllocaInst &AI) {
    3263             :   SmallPtrSet<Type*, 4> Visited;
    3264             :   PointerType *PTy = AI.getType();
    3265             :   // TODO: Relax this restriction?
    3266      394844 :   Assert(PTy->getAddressSpace() == DL.getAllocaAddrSpace(),
    3267             :          "Allocation instruction pointer not in the stack address space!",
    3268             :          &AI);
    3269      394813 :   Assert(AI.getAllocatedType()->isSized(&Visited),
    3270             :          "Cannot allocate unsized type", &AI);
    3271      789614 :   Assert(AI.getArraySize()->getType()->isIntegerTy(),
    3272             :          "Alloca array size must have integer type", &AI);
    3273      394807 :   Assert(AI.getAlignment() <= Value::MaximumAlignment,
    3274             :          "huge alignment values are unsupported", &AI);
    3275             : 
    3276      394807 :   if (AI.isSwiftError()) {
    3277         268 :     verifySwiftErrorValue(&AI);
    3278             :   }
    3279             : 
    3280      394807 :   visitInstruction(AI);
    3281             : }
    3282             : 
    3283        4230 : void Verifier::visitAtomicCmpXchgInst(AtomicCmpXchgInst &CXI) {
    3284             : 
    3285             :   // FIXME: more conditions???
    3286        4230 :   Assert(CXI.getSuccessOrdering() != AtomicOrdering::NotAtomic,
    3287             :          "cmpxchg instructions must be atomic.", &CXI);
    3288        4230 :   Assert(CXI.getFailureOrdering() != AtomicOrdering::NotAtomic,
    3289             :          "cmpxchg instructions must be atomic.", &CXI);
    3290        4230 :   Assert(CXI.getSuccessOrdering() != AtomicOrdering::Unordered,
    3291             :          "cmpxchg instructions cannot be unordered.", &CXI);
    3292        4230 :   Assert(CXI.getFailureOrdering() != AtomicOrdering::Unordered,
    3293             :          "cmpxchg instructions cannot be unordered.", &CXI);
    3294        4230 :   Assert(!isStrongerThan(CXI.getFailureOrdering(), CXI.getSuccessOrdering()),
    3295             :          "cmpxchg instructions failure argument shall be no stronger than the "
    3296             :          "success argument",
    3297             :          &CXI);
    3298        4230 :   Assert(CXI.getFailureOrdering() != AtomicOrdering::Release &&
    3299             :              CXI.getFailureOrdering() != AtomicOrdering::AcquireRelease,
    3300             :          "cmpxchg failure ordering cannot include release semantics", &CXI);
    3301             : 
    3302        4230 :   PointerType *PTy = dyn_cast<PointerType>(CXI.getOperand(0)->getType());
    3303           0 :   Assert(PTy, "First cmpxchg operand must be a pointer.", &CXI);
    3304        4230 :   Type *ElTy = PTy->getElementType();
    3305           0 :   Assert(ElTy->isIntOrPtrTy(),
    3306             :          "cmpxchg operand must have integer or pointer type", ElTy, &CXI);
    3307        4230 :   checkAtomicMemAccessSize(ElTy, &CXI);
    3308        4230 :   Assert(ElTy == CXI.getOperand(1)->getType(),
    3309             :          "Expected value type does not match pointer operand type!", &CXI,
    3310             :          ElTy);
    3311        4230 :   Assert(ElTy == CXI.getOperand(2)->getType(),
    3312             :          "Stored value type does not match pointer operand type!", &CXI, ElTy);
    3313        4230 :   visitInstruction(CXI);
    3314             : }
    3315             : 
    3316       17249 : void Verifier::visitAtomicRMWInst(AtomicRMWInst &RMWI) {
    3317       17249 :   Assert(RMWI.getOrdering() != AtomicOrdering::NotAtomic,
    3318             :          "atomicrmw instructions must be atomic.", &RMWI);
    3319       17249 :   Assert(RMWI.getOrdering() != AtomicOrdering::Unordered,
    3320             :          "atomicrmw instructions cannot be unordered.", &RMWI);
    3321       17249 :   PointerType *PTy = dyn_cast<PointerType>(RMWI.getOperand(0)->getType());
    3322           0 :   Assert(PTy, "First atomicrmw operand must be a pointer.", &RMWI);
    3323       17249 :   Type *ElTy = PTy->getElementType();
    3324       17249 :   Assert(ElTy->isIntegerTy(), "atomicrmw operand must have integer type!",
    3325             :          &RMWI, ElTy);
    3326       17249 :   checkAtomicMemAccessSize(ElTy, &RMWI);
    3327       17249 :   Assert(ElTy == RMWI.getOperand(1)->getType(),
    3328             :          "Argument value type does not match pointer operand type!", &RMWI,
    3329             :          ElTy);
    3330       17249 :   Assert(AtomicRMWInst::FIRST_BINOP <= RMWI.getOperation() &&
    3331             :              RMWI.getOperation() <= AtomicRMWInst::LAST_BINOP,
    3332             :          "Invalid binary operation!", &RMWI);
    3333       17249 :   visitInstruction(RMWI);
    3334             : }
    3335             : 
    3336        1896 : void Verifier::visitFenceInst(FenceInst &FI) {
    3337             :   const AtomicOrdering Ordering = FI.getOrdering();
    3338        1896 :   Assert(Ordering == AtomicOrdering::Acquire ||
    3339             :              Ordering == AtomicOrdering::Release ||
    3340             :              Ordering == AtomicOrdering::AcquireRelease ||
    3341             :              Ordering == AtomicOrdering::SequentiallyConsistent,
    3342             :          "fence instructions may only have acquire, release, acq_rel, or "
    3343             :          "seq_cst ordering.",
    3344             :          &FI);
    3345        1896 :   visitInstruction(FI);
    3346             : }
    3347             : 
    3348       30199 : void Verifier::visitExtractValueInst(ExtractValueInst &EVI) {
    3349       30199 :   Assert(ExtractValueInst::getIndexedType(EVI.getAggregateOperand()->getType(),
    3350             :                                           EVI.getIndices()) == EVI.getType(),
    3351             :          "Invalid ExtractValueInst operands!", &EVI);
    3352             : 
    3353       30199 :   visitInstruction(EVI);
    3354             : }
    3355             : 
    3356        5363 : void Verifier::visitInsertValueInst(InsertValueInst &IVI) {
    3357       10726 :   Assert(ExtractValueInst::getIndexedType(IVI.getAggregateOperand()->getType(),
    3358             :                                           IVI.getIndices()) ==
    3359             :              IVI.getOperand(1)->getType(),
    3360             :          "Invalid InsertValueInst operands!", &IVI);
    3361             : 
    3362        5363 :   visitInstruction(IVI);
    3363             : }
    3364             : 
    3365             : static Value *getParentPad(Value *EHPad) {
    3366             :   if (auto *FPI = dyn_cast<FuncletPadInst>(EHPad))
    3367             :     return FPI->getParentPad();
    3368             : 
    3369             :   return cast<CatchSwitchInst>(EHPad)->getParentPad();
    3370             : }
    3371             : 
    3372        6558 : void Verifier::visitEHPadPredecessors(Instruction &I) {
    3373             :   assert(I.isEHPad());
    3374             : 
    3375        6558 :   BasicBlock *BB = I.getParent();
    3376        6558 :   Function *F = BB->getParent();
    3377             : 
    3378       11543 :   Assert(BB != &F->getEntryBlock(), "EH pad cannot be in entry block.", &I);
    3379             : 
    3380        6558 :   if (auto *LPI = dyn_cast<LandingPadInst>(&I)) {
    3381             :     // The landingpad instruction defines its parent as a landing pad block. The
    3382             :     // landing pad block may be branched to only by the unwind edge of an
    3383             :     // invoke.
    3384       13742 :     for (BasicBlock *PredBB : predecessors(BB)) {
    3385             :       const auto *II = dyn_cast<InvokeInst>(PredBB->getTerminator());
    3386       10792 :       Assert(II && II->getUnwindDest() == BB && II->getNormalDest() != BB,
    3387             :              "Block containing LandingPadInst must be jumped to "
    3388             :              "only by the unwind edge of an invoke.",
    3389             :              LPI);
    3390             :     }
    3391        4173 :     return;
    3392             :   }
    3393        2384 :   if (auto *CPI = dyn_cast<CatchPadInst>(&I)) {
    3394         803 :     if (!pred_empty(BB))
    3395        2410 :       Assert(BB->getUniquePredecessor() == CPI->getCatchSwitch()->getParent(),
    3396             :              "Block containg CatchPadInst must be jumped to "
    3397             :              "only by its catchswitch.",
    3398             :              CPI);
    3399        1606 :     Assert(BB != CPI->getCatchSwitch()->getUnwindDest(),
    3400             :            "Catchswitch cannot unwind to one of its catchpads",
    3401             :            CPI->getCatchSwitch(), CPI);
    3402             :     return;
    3403             :   }
    3404             : 
    3405             :   // Verify that each pred has a legal terminator with a legal to/from EH
    3406             :   // pad relationship.
    3407        1581 :   Instruction *ToPad = &I;
    3408             :   Value *ToPadParent = getParentPad(ToPad);
    3409        5084 :   for (BasicBlock *PredBB : predecessors(BB)) {
    3410        1930 :     TerminatorInst *TI = PredBB->getTerminator();
    3411             :     Value *FromPad;
    3412        1930 :     if (auto *II = dyn_cast<InvokeInst>(TI)) {
    3413        3076 :       Assert(II->getUnwindDest() == BB && II->getNormalDest() != BB,
    3414             :              "EH pad must be jumped to via an unwind edge", ToPad, II);
    3415        1537 :       if (auto Bundle = II->getOperandBundle(LLVMContext::OB_funclet))
    3416         372 :         FromPad = Bundle->Inputs[0];
    3417             :       else
    3418        1165 :         FromPad = ConstantTokenNone::get(II->getContext());
    3419         393 :     } else if (auto *CRI = dyn_cast<CleanupReturnInst>(TI)) {
    3420         205 :       FromPad = CRI->getOperand(0);
    3421         209 :       Assert(FromPad != ToPadParent, "A cleanupret must exit its cleanup", CRI);
    3422             :     } else if (auto *CSI = dyn_cast<CatchSwitchInst>(TI)) {
    3423         188 :       FromPad = CSI;
    3424             :     } else {
    3425           0 :       Assert(false, "EH pad must be jumped to via an unwind edge", ToPad, TI);
    3426             :     }
    3427             : 
    3428             :     // The edge may exit from zero or more nested pads.
    3429             :     SmallSet<Value *, 8> Seen;
    3430        1372 :     for (;; FromPad = getParentPad(FromPad)) {
    3431        2617 :       Assert(FromPad != ToPad,
    3432             :              "EH pad cannot handle exceptions raised within it", FromPad, TI);
    3433        2611 :       if (FromPad == ToPadParent) {
    3434             :         // This is a legal unwind edge.
    3435             :         break;
    3436             :       }
    3437         691 :       Assert(!isa<ConstantTokenNone>(FromPad),
    3438             :              "A single unwind edge may only enter one EH pad", TI);
    3439         688 :       Assert(Seen.insert(FromPad).second,
    3440             :              "EH pad jumps through a cycle of pads", FromPad);
    3441             :     }
    3442             :   }
    3443             : }
    3444             : 
    3445        4174 : void Verifier::visitLandingPadInst(LandingPadInst &LPI) {
    3446             :   // The landingpad instruction is ill-formed if it doesn't have any clauses and
    3447             :   // isn't a cleanup.
    3448        6275 :   Assert(LPI.getNumClauses() > 0 || LPI.isCleanup(),
    3449             :          "LandingPadInst needs at least one clause or to be a cleanup.", &LPI);
    3450             : 
    3451        4174 :   visitEHPadPredecessors(LPI);
    3452             : 
    3453        4174 :   if (!LandingPadResultTy)
    3454        2712 :     LandingPadResultTy = LPI.getType();
    3455             :   else
    3456        1463 :     Assert(LandingPadResultTy == LPI.getType(),
    3457             :            "The landingpad instruction should have a consistent result type "
    3458             :            "inside a function.",
    3459             :            &LPI);
    3460             : 
    3461        4173 :   Function *F = LPI.getParent()->getParent();
    3462        4173 :   Assert(F->hasPersonalityFn(),
    3463             :          "LandingPadInst needs to be in a function with a personality.", &LPI);
    3464             : 
    3465             :   // The landingpad instruction must be the first non-PHI instruction in the
    3466             :   // block.
    3467        4173 :   Assert(LPI.getParent()->getLandingPadInst() == &LPI,
    3468             :          "LandingPadInst not the first non-PHI instruction in the block.",
    3469             :          &LPI);
    3470             : 
    3471        8633 :   for (unsigned i = 0, e = LPI.getNumClauses(); i < e; ++i) {
    3472             :     Constant *Clause = LPI.getClause(i);
    3473        2230 :     if (LPI.isCatch(i)) {
    3474        2117 :       Assert(isa<PointerType>(Clause->getType()),
    3475             :              "Catch operand does not have pointer type!", &LPI);
    3476             :     } else {
    3477             :       Assert(LPI.isFilter(i), "Clause is neither catch nor filter!", &LPI);
    3478         113 :       Assert(isa<ConstantArray>(Clause) || isa<ConstantAggregateZero>(Clause),
    3479             :              "Filter operand is not an array of constants!", &LPI);
    3480             :     }
    3481             :   }
    3482             : 
    3483        4173 :   visitInstruction(LPI);
    3484             : }
    3485             : 
    3486         966 : void Verifier::visitResumeInst(ResumeInst &RI) {
    3487        1933 :   Assert(RI.getFunction()->hasPersonalityFn(),
    3488             :          "ResumeInst needs to be in a function with a personality.", &RI);
    3489             : 
    3490         965 :   if (!LandingPadResultTy)
    3491           2 :     LandingPadResultTy = RI.getValue()->getType();
    3492             :   else
    3493         963 :     Assert(LandingPadResultTy == RI.getValue()->getType(),
    3494             :            "The resume instruction should have a consistent result type "
    3495             :            "inside a function.",
    3496             :            &RI);
    3497             : 
    3498         965 :   visitTerminatorInst(RI);
    3499             : }
    3500             : 
    3501         805 : void Verifier::visitCatchPadInst(CatchPadInst &CPI) {
    3502         805 :   BasicBlock *BB = CPI.getParent();
    3503             : 
    3504         805 :   Function *F = BB->getParent();
    3505         806 :   Assert(F->hasPersonalityFn(),
    3506             :          "CatchPadInst needs to be in a function with a personality.", &CPI);
    3507             : 
    3508           2 :   Assert(isa<CatchSwitchInst>(CPI.getParentPad()),
    3509             :          "CatchPadInst needs to be directly nested in a CatchSwitchInst.",
    3510             :          CPI.getParentPad());
    3511             : 
    3512             :   // The catchpad instruction must be the first non-PHI instruction in the
    3513             :   // block.
    3514         803 :   Assert(BB->getFirstNonPHI() == &CPI,
    3515             :          "CatchPadInst not the first non-PHI instruction in the block.", &CPI);
    3516             : 
    3517         803 :   visitEHPadPredecessors(CPI);
    3518         803 :   visitFuncletPadInst(CPI);
    3519             : }
    3520             : 
    3521         594 : void Verifier::visitCatchReturnInst(CatchReturnInst &CatchReturn) {
    3522           4 :   Assert(isa<CatchPadInst>(CatchReturn.getOperand(0)),
    3523             :          "CatchReturnInst needs to be provided a CatchPad", &CatchReturn,
    3524             :          CatchReturn.getOperand(0));
    3525             : 
    3526         592 :   visitTerminatorInst(CatchReturn);
    3527             : }
    3528             : 
    3529         837 : void Verifier::visitCleanupPadInst(CleanupPadInst &CPI) {
    3530         837 :   BasicBlock *BB = CPI.getParent();
    3531             : 
    3532         837 :   Function *F = BB->getParent();
    3533         838 :   Assert(F->hasPersonalityFn(),
    3534             :          "CleanupPadInst needs to be in a function with a personality.", &CPI);
    3535             : 
    3536             :   // The cleanuppad instruction must be the first non-PHI instruction in the
    3537             :   // block.
    3538         836 :   Assert(BB->getFirstNonPHI() == &CPI,
    3539             :          "CleanupPadInst not the first non-PHI instruction in the block.",
    3540             :          &CPI);
    3541             : 
    3542             :   auto *ParentPad = CPI.getParentPad();
    3543         838 :   Assert(isa<ConstantTokenNone>(ParentPad) || isa<FuncletPadInst>(ParentPad),
    3544             :          "CleanupPadInst has an invalid parent.", &CPI);
    3545             : 
    3546         835 :   visitEHPadPredecessors(CPI);
    3547         835 :   visitFuncletPadInst(CPI);
    3548             : }
    3549             : 
    3550        1638 : void Verifier::visitFuncletPadInst(FuncletPadInst &FPI) {
    3551        1638 :   User *FirstUser = nullptr;
    3552             :   Value *FirstUnwindPad = nullptr;
    3553        3276 :   SmallVector<FuncletPadInst *, 8> Worklist({&FPI});
    3554             :   SmallSet<FuncletPadInst *, 8> Seen;
    3555             : 
    3556        3523 :   while (!Worklist.empty()) {
    3557        1888 :     FuncletPadInst *CurrentPad = Worklist.pop_back_val();
    3558        1892 :     Assert(Seen.insert(CurrentPad).second,
    3559             :            "FuncletPadInst must not be nested within itself", CurrentPad);
    3560             :     Value *UnresolvedAncestorPad = nullptr;
    3561        9738 :     for (User *U : CurrentPad->users()) {
    3562             :       BasicBlock *UnwindDest;
    3563             :       if (auto *CRI = dyn_cast<CleanupReturnInst>(U)) {
    3564             :         UnwindDest = CRI->getUnwindDest();
    3565             :       } else if (auto *CSI = dyn_cast<CatchSwitchInst>(U)) {
    3566             :         // We allow catchswitch unwind to caller to nest
    3567             :         // within an outer pad that unwinds somewhere else,
    3568             :         // because catchswitch doesn't have a nounwind variant.
    3569             :         // See e.g. SimplifyCFGOpt::SimplifyUnreachable.
    3570         143 :         if (CSI->unwindsToCaller())
    3571         102 :           continue;
    3572             :         UnwindDest = CSI->getUnwindDest();
    3573             :       } else if (auto *II = dyn_cast<InvokeInst>(U)) {
    3574             :         UnwindDest = II->getUnwindDest();
    3575         900 :       } else if (isa<CallInst>(U)) {
    3576             :         // Calls which don't unwind may be found inside funclet
    3577             :         // pads that unwind somewhere else.  We don't *require*
    3578             :         // such calls to be annotated nounwind.
    3579         900 :         continue;
    3580         844 :       } else if (auto *CPI = dyn_cast<CleanupPadInst>(U)) {
    3581             :         // The unwind dest for a cleanup can only be found by
    3582             :         // recursive search.  Add it to the worklist, and we'll
    3583             :         // search for its first use that determines where it unwinds.
    3584         252 :         Worklist.push_back(CPI);
    3585         252 :         continue;
    3586             :       } else {
    3587           0 :         Assert(isa<CatchReturnInst>(U), "Bogus funclet pad use", U);
    3588         592 :         continue;
    3589             :       }
    3590             : 
    3591             :       Value *UnwindPad;
    3592             :       bool ExitsFPI;
    3593         786 :       if (UnwindDest) {
    3594             :         UnwindPad = UnwindDest->getFirstNonPHI();
    3595           1 :         if (!cast<Instruction>(UnwindPad)->isEHPad())
    3596           1 :           continue;
    3597             :         Value *UnwindParent = getParentPad(UnwindPad);
    3598             :         // Ignore unwind edges that don't exit CurrentPad.
    3599         785 :         if (UnwindParent == CurrentPad)
    3600         349 :           continue;
    3601             :         // Determine whether the original funclet pad is exited,
    3602             :         // and if we are scanning nested pads determine how many
    3603             :         // of them are exited so we can stop searching their
    3604             :         // children.
    3605             :         Value *ExitedPad = CurrentPad;
    3606             :         ExitsFPI = false;
    3607             :         do {
    3608         505 :           if (ExitedPad == &FPI) {
    3609             :             ExitsFPI = true;
    3610             :             // Now we can resolve any ancestors of CurrentPad up to
    3611             :             // FPI, but not including FPI since we need to make sure
    3612             :             // to check all direct users of FPI for consistency.
    3613             :             UnresolvedAncestorPad = &FPI;
    3614             :             break;
    3615             :           }
    3616             :           Value *ExitedParent = getParentPad(ExitedPad);
    3617         111 :           if (ExitedParent == UnwindParent) {
    3618             :             // ExitedPad is the ancestor-most pad which this unwind
    3619             :             // edge exits, so we can resolve up to it, meaning that
    3620             :             // ExitedParent is the first ancestor still unresolved.
    3621             :             UnresolvedAncestorPad = ExitedParent;
    3622             :             break;
    3623             :           }
    3624             :           ExitedPad = ExitedParent;
    3625          69 :         } while (!isa<ConstantTokenNone>(ExitedPad));
    3626             :       } else {
    3627             :         // Unwinding to caller exits all pads.
    3628         407 :         UnwindPad = ConstantTokenNone::get(FPI.getContext());
    3629             :         ExitsFPI = true;
    3630             :         UnresolvedAncestorPad = &FPI;
    3631             :       }
    3632             : 
    3633         843 :       if (ExitsFPI) {
    3634             :         // This unwind edge exits FPI.  Make sure it agrees with other
    3635             :         // such edges.
    3636         801 :         if (FirstUser) {
    3637          83 :           Assert(UnwindPad == FirstUnwindPad, "Unwind edges out of a funclet "
    3638             :                                               "pad must have the same unwind "
    3639             :                                               "dest",
    3640             :                  &FPI, U, FirstUser);
    3641             :         } else {
    3642         720 :           FirstUser = U;
    3643             :           FirstUnwindPad = UnwindPad;
    3644             :           // Record cleanup sibling unwinds for verifySiblingFuncletUnwinds
    3645        1619 :           if (isa<CleanupPadInst>(&FPI) && !isa<ConstantTokenNone>(UnwindPad) &&
    3646             :               getParentPad(UnwindPad) == getParentPad(&FPI))
    3647         205 :             SiblingFuncletInfo[&FPI] = cast<TerminatorInst>(U);
    3648             :         }
    3649             :       }
    3650             :       // Make sure we visit all uses of FPI, but for nested pads stop as
    3651             :       // soon as we know where they unwind to.
    3652         841 :       if (CurrentPad != &FPI)
    3653             :         break;
    3654             :     }
    3655        1885 :     if (UnresolvedAncestorPad) {
    3656         788 :       if (CurrentPad == UnresolvedAncestorPad) {
    3657             :         // When CurrentPad is FPI itself, we don't mark it as resolved even if
    3658             :         // we've found an unwind edge that exits it, because we need to verify
    3659             :         // all direct uses of FPI.
    3660             :         assert(CurrentPad == &FPI);
    3661         676 :         continue;
    3662             :       }
    3663             :       // Pop off the worklist any nested pads that we've found an unwind
    3664             :       // destination for.  The pads on the worklist are the uncles,
    3665             :       // great-uncles, etc. of CurrentPad.  We've found an unwind destination
    3666             :       // for all ancestors of CurrentPad up to but not including
    3667             :       // UnresolvedAncestorPad.
    3668             :       Value *ResolvedPad = CurrentPad;
    3669         114 :       while (!Worklist.empty()) {
    3670          40 :         Value *UnclePad = Worklist.back();
    3671             :         Value *AncestorPad = getParentPad(UnclePad);
    3672             :         // Walk ResolvedPad up the ancestor list until we either find the
    3673             :         // uncle's parent or the last resolved ancestor.
    3674          46 :         while (ResolvedPad != AncestorPad) {
    3675             :           Value *ResolvedParent = getParentPad(ResolvedPad);
    3676          44 :           if (ResolvedParent == UnresolvedAncestorPad) {
    3677             :             break;
    3678             :           }
    3679             :           ResolvedPad = ResolvedParent;
    3680             :         }
    3681             :         // If the resolved ancestor search didn't find the uncle's parent,
    3682             :         // then the uncle is not yet resolved.
    3683          40 :         if (ResolvedPad != AncestorPad)
    3684             :           break;
    3685             :         // This uncle is resolved, so pop it from the worklist.
    3686             :         Worklist.pop_back();
    3687             :       }
    3688             :     }
    3689             :   }
    3690             : 
    3691        1635 :   if (FirstUnwindPad) {
    3692         718 :     if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(FPI.getParentPad())) {
    3693             :       BasicBlock *SwitchUnwindDest = CatchSwitch->getUnwindDest();
    3694             :       Value *SwitchUnwindPad;
    3695             :       if (SwitchUnwindDest)
    3696             :         SwitchUnwindPad = SwitchUnwindDest->getFirstNonPHI();
    3697             :       else
    3698          17 :         SwitchUnwindPad = ConstantTokenNone::get(FPI.getContext());
    3699          77 :       Assert(SwitchUnwindPad == FirstUnwindPad,
    3700             :              "Unwind edges out of a catch must have the same unwind dest as "
    3701             :              "the parent catchswitch",
    3702             :              &FPI, FirstUser, CatchSwitch);
    3703             :     }
    3704             :   }
    3705             : 
    3706        1632 :   visitInstruction(FPI);
    3707             : }
    3708             : 
    3709         749 : void Verifier::visitCatchSwitchInst(CatchSwitchInst &CatchSwitch) {
    3710         749 :   BasicBlock *BB = CatchSwitch.getParent();
    3711             : 
    3712         749 :   Function *F = BB->getParent();
    3713         753 :   Assert(F->hasPersonalityFn(),
    3714             :          "CatchSwitchInst needs to be in a function with a personality.",
    3715             :          &CatchSwitch);
    3716             : 
    3717             :   // The catchswitch instruction must be the first non-PHI instruction in the
    3718             :   // block.
    3719         748 :   Assert(BB->getFirstNonPHI() == &CatchSwitch,
    3720             :          "CatchSwitchInst not the first non-PHI instruction in the block.",
    3721             :          &CatchSwitch);
    3722             : 
    3723         748 :   auto *ParentPad = CatchSwitch.getParentPad();
    3724         750 :   Assert(isa<ConstantTokenNone>(ParentPad) || isa<FuncletPadInst>(ParentPad),
    3725             :          "CatchSwitchInst has an invalid parent.", ParentPad);
    3726             : 
    3727             :   if (BasicBlock *UnwindDest = CatchSwitch.getUnwindDest()) {
    3728             :     Instruction *I = UnwindDest->getFirstNonPHI();
    3729         191 :     Assert(I->isEHPad() && !isa<LandingPadInst>(I),
    3730             :            "CatchSwitchInst must unwind to an EH block which is not a "
    3731             :            "landingpad.",
    3732             :            &CatchSwitch);
    3733             : 
    3734             :     // Record catchswitch sibling unwinds for verifySiblingFuncletUnwinds
    3735         191 :     if (getParentPad(I) == ParentPad)
    3736         166 :       SiblingFuncletInfo[&CatchSwitch] = &CatchSwitch;
    3737             :   }
    3738             : 
    3739         747 :   Assert(CatchSwitch.getNumHandlers() != 0,
    3740             :          "CatchSwitchInst cannot have empty handler list", &CatchSwitch);
    3741             : 
    3742        2352 :   for (BasicBlock *Handler : CatchSwitch.handlers()) {
    3743         804 :     Assert(isa<CatchPadInst>(Handler->getFirstNonPHI()),
    3744             :            "CatchSwitchInst handlers must be catchpads", &CatchSwitch, Handler);
    3745             :   }
    3746             : 
    3747         746 :   visitEHPadPredecessors(CatchSwitch);
    3748         746 :   visitTerminatorInst(CatchSwitch);
    3749             : }
    3750             : 
    3751         592 : void Verifier::visitCleanupReturnInst(CleanupReturnInst &CRI) {
    3752           6 :   Assert(isa<CleanupPadInst>(CRI.getOperand(0)),
    3753             :          "CleanupReturnInst needs to be provided a CleanupPad", &CRI,
    3754             :          CRI.getOperand(0));
    3755             : 
    3756         204 :   if (BasicBlock *UnwindDest = CRI.getUnwindDest()) {
    3757             :     Instruction *I = UnwindDest->getFirstNonPHI();
    3758         204 :     Assert(I->isEHPad() && !isa<LandingPadInst>(I),
    3759             :            "CleanupReturnInst must unwind to an EH block which is not a "
    3760             :            "landingpad.",
    3761             :            &CRI);
    3762             :   }
    3763             : 
    3764         589 :   visitTerminatorInst(CRI);
    3765             : }
    3766             : 
    3767     4805005 : void Verifier::verifyDominatesUse(Instruction &I, unsigned i) {
    3768     9610010 :   Instruction *Op = cast<Instruction>(I.getOperand(i));
    3769             :   // If the we have an invalid invoke, don't try to compute the dominance.
    3770             :   // We already reject it in the invoke specific checks and the dominance
    3771             :   // computation doesn't handle multiple edges.
    3772             :   if (InvokeInst *II = dyn_cast<InvokeInst>(Op)) {
    3773        1204 :     if (II->getNormalDest() == II->getUnwindDest())
    3774     4305469 :       return;
    3775             :   }
    3776             : 
    3777             :   // Quick check whether the def has already been encountered in the same block.
    3778             :   // PHI nodes are not checked to prevent accepting preceeding PHIs, because PHI
    3779             :   // uses are defined to happen on the incoming edge, not at the instruction.
    3780             :   //
    3781             :   // FIXME: If this operand is a MetadataAsValue (wrapping a LocalAsMetadata)
    3782             :   // wrapping an SSA value, assert that we've already encountered it.  See
    3783             :   // related FIXME in Mapper::mapLocalAsMetadata in ValueMapper.cpp.
    3784     4805003 :   if (!isa<PHINode>(I) && InstsInThisBlock.count(Op))
    3785             :     return;
    3786             : 
    3787             :   const Use &U = I.getOperandUse(i);
    3788      499560 :   Assert(DT.dominates(Op, U),
    3789             :          "Instruction does not dominate all uses!", Op, &I);
    3790             : }
    3791             : 
    3792          98 : void Verifier::visitDereferenceableMetadata(Instruction& I, MDNode* MD) {
    3793         198 :   Assert(I.getType()->isPointerTy(), "dereferenceable, dereferenceable_or_null "
    3794             :          "apply only to pointer types", &I);
    3795          98 :   Assert(isa<LoadInst>(I),
    3796             :          "dereferenceable, dereferenceable_or_null apply only to load"
    3797             :          " instructions, use attributes for calls or invokes", &I);
    3798          96 :   Assert(MD->getNumOperands() == 1, "dereferenceable, dereferenceable_or_null "
    3799             :          "take one operand!", &I);
    3800             :   ConstantInt *CI = mdconst::dyn_extract<ConstantInt>(MD->getOperand(0));
    3801          94 :   Assert(CI && CI->getType()->isIntegerTy(64), "dereferenceable, "
    3802             :          "dereferenceable_or_null metadata value must be an i64!", &I);
    3803             : }
    3804             : 
    3805             : /// verifyInstruction - Verify that an instruction is well formed.
    3806             : ///
    3807     6037070 : void Verifier::visitInstruction(Instruction &I) {
    3808     6037070 :   BasicBlock *BB = I.getParent();
    3809     6037070 :   Assert(BB, "Instruction not embedded in basic block!", &I);
    3810             : 
    3811     6037070 :   if (!isa<PHINode>(I)) {   // Check that non-phi nodes are not self referential
    3812    10610187 :     for (User *U : I.users()) {
    3813     4653342 :       Assert(U != (User *)&I || !DT.isReachableFromEntry(BB),
    3814             :              "Only PHI nodes may reference their own value!", &I);
    3815             :     }
    3816             :   }
    3817             : 
    3818             :   // Check that void typed values don't have names
    3819    14136942 :   Assert(!I.getType()->isVoidTy() || !I.hasName(),
    3820             :          "Instruction has a name, but provides a void value!", &I);
    3821             : 
    3822             :   // Check that the return value of the instruction is either void or a legal
    3823             :   // value type.
    3824     6037069 :   Assert(I.getType()->isVoidTy() || I.getType()->isFirstClassType(),
    3825             :          "Instruction returns a non-scalar type!", &I);
    3826             : 
    3827             :   // Check that the instruction doesn't produce metadata. Calls are already
    3828             :   // checked against the callee type.
    3829     6037069 :   Assert(!I.getType()->isMetadataTy() || isa<CallInst>(I) || isa<InvokeInst>(I),
    3830             :          "Invalid use of metadata!", &I);
    3831             : 
    3832             :   // Check that all uses of the instruction, if they are instructions
    3833             :   // themselves, actually have parent basic blocks.  If the use is not an
    3834             :   // instruction, it is an error!
    3835    10839358 :   for (Use &U : I.uses()) {
    3836     9604578 :     if (Instruction *Used = dyn_cast<Instruction>(U.getUser()))
    3837     4802289 :       Assert(Used->getParent() != nullptr,
    3838             :              "Instruction referencing"
    3839             :              " instruction not embedded in a basic block!",
    3840             :              &I, Used);
    3841             :     else {
    3842           0 :       CheckFailed("Use of instruction is not an instruction!", U);
    3843           0 :       return;
    3844             :     }
    3845             :   }
    3846             : 
    3847    26519947 :   for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) {
    3848    20482894 :     Assert(I.getOperand(i) != nullptr, "Instruction has null operand!", &I);
    3849             : 
    3850             :     // Check to make sure that only first-class-values are operands to
    3851             :     // instructions.
    3852    10241447 :     if (!I.getOperand(i)->getType()->isFirstClassType()) {
    3853           0 :       Assert(false, "Instruction operands must be first-class values!", &I);
    3854             :     }
    3855             : 
    3856    10241447 :     if (Function *F = dyn_cast<Function>(I.getOperand(i))) {
    3857             :       // Check to make sure that the "address of" an intrinsic function is never
    3858             :       // taken.
    3859      879489 :       Assert(
    3860             :           !F->isIntrinsic() ||
    3861             :               i == (isa<CallInst>(I) ? e - 1 : isa<InvokeInst>(I) ? e - 3 : 0),
    3862             :           "Cannot take the address of an intrinsic!", &I);
    3863      879489 :       Assert(
    3864             :           !F->isIntrinsic() || isa<CallInst>(I) ||
    3865             :               F->getIntrinsicID() == Intrinsic::donothing ||
    3866             :               F->getIntrinsicID() == Intrinsic::coro_resume ||
    3867             :               F->getIntrinsicID() == Intrinsic::coro_destroy ||
    3868             :               F->getIntrinsicID() == Intrinsic::experimental_patchpoint_void ||
    3869             :               F->getIntrinsicID() == Intrinsic::experimental_patchpoint_i64 ||
    3870             :               F->getIntrinsicID() == Intrinsic::experimental_gc_statepoint,
    3871             :           "Cannot invoke an intrinsic other than donothing, patchpoint, "
    3872             :           "statepoint, coro_resume or coro_destroy",
    3873             :           &I);
    3874      557714 :       Assert(F->getParent() == &M, "Referencing function in another module!",
    3875             :              &I, &M, F, F->getParent());
    3876             :     } else if (BasicBlock *OpBB = dyn_cast<BasicBlock>(I.getOperand(i))) {
    3877      513980 :       Assert(OpBB->getParent() == BB->getParent(),
    3878             :              "Referring to a basic block in another function!", &I);
    3879             :     } else if (Argument *OpArg = dyn_cast<Argument>(I.getOperand(i))) {
    3880     1538936 :       Assert(OpArg->getParent() == BB->getParent(),
    3881             :              "Referring to an argument in another function!", &I);
    3882     7630812 :     } else if (GlobalValue *GV = dyn_cast<GlobalValue>(I.getOperand(i))) {
    3883      190161 :       Assert(GV->getParent() == &M, "Referencing global in another module!", &I,
    3884             :              &M, GV, GV->getParent());
    3885     7440651 :     } else if (isa<Instruction>(I.getOperand(i))) {
    3886     4805005 :       verifyDominatesUse(I, i);
    3887     2635646 :     } else if (isa<InlineAsm>(I.getOperand(i))) {
    3888      102150 :       Assert((i + 1 == e && isa<CallInst>(I)) ||
    3889             :                  (i + 3 == e && isa<InvokeInst>(I)),
    3890             :              "Cannot take the address of an inline asm!", &I);
    3891             :     } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(I.getOperand(i))) {
    3892      224526 :       if (CE->getType()->isPtrOrPtrVectorTy() ||
    3893        2774 :           !DL.getNonIntegralAddressSpaces().empty()) {
    3894             :         // If we have a ConstantExpr pointer, we need to see if it came from an
    3895             :         // illegal bitcast.  If the datalayout string specifies non-integral
    3896             :         // address spaces then we also need to check for illegal ptrtoint and
    3897             :         // inttoptr expressions.
    3898      108103 :         visitConstantExprsRecursively(CE);
    3899             :       }
    3900             :     }
    3901             :   }
    3902             : 
    3903      244776 :   if (MDNode *MD = I.getMetadata(LLVMContext::MD_fpmath)) {
    3904         400 :     Assert(I.getType()->isFPOrFPVectorTy(),
    3905             :            "fpmath requires a floating point result!", &I);
    3906         399 :     Assert(MD->getNumOperands() == 1, "fpmath takes one operand!", &I);
    3907             :     if (ConstantFP *CFP0 =
    3908             :             mdconst::dyn_extract_or_null<ConstantFP>(MD->getOperand(0))) {
    3909             :       const APFloat &Accuracy = CFP0->getValueAPF();
    3910         395 :       Assert(&Accuracy.getSemantics() == &APFloat::IEEEsingle(),
    3911             :              "fpmath accuracy must have float type", &I);
    3912         787 :       Assert(Accuracy.isFiniteNonZero() && !Accuracy.isNegative(),
    3913             :              "fpmath accuracy not a positive number!", &I);
    3914             :     } else {
    3915           2 :       Assert(false, "invalid fpmath accuracy!", &I);
    3916             :     }
    3917             :   }
    3918             : 
    3919      244768 :   if (MDNode *Range = I.getMetadata(LLVMContext::MD_range)) {
    3920        8524 :     Assert(isa<LoadInst>(I) || isa<CallInst>(I) || isa<InvokeInst>(I),
    3921             :            "Ranges are only for loads, calls and invokes!", &I);
    3922        8521 :     visitRangeMetadata(I, Range, I.getType());
    3923             :   }
    3924             : 
    3925      244767 :   if (I.getMetadata(LLVMContext::MD_nonnull)) {
    3926          86 :     Assert(I.getType()->isPointerTy(), "nonnull applies only to pointer types",
    3927             :            &I);
    3928          43 :     Assert(isa<LoadInst>(I),
    3929             :            "nonnull applies only to load instructions, use attributes"
    3930             :            " for calls or invokes",
    3931             :            &I);
    3932             :   }
    3933             : 
    3934      244767 :   if (MDNode *MD = I.getMetadata(LLVMContext::MD_dereferenceable))
    3935          56 :     visitDereferenceableMetadata(I, MD);
    3936             : 
    3937      244767 :   if (MDNode *MD = I.getMetadata(LLVMContext::MD_dereferenceable_or_null))
    3938          42 :     visitDereferenceableMetadata(I, MD);
    3939             : 
    3940      244767 :   if (MDNode *TBAA = I.getMetadata(LLVMContext::MD_tbaa))
    3941       35374 :     TBAAVerifyHelper.visitTBAAMetadata(I, TBAA);
    3942             : 
    3943      244767 :   if (MDNode *AlignMD = I.getMetadata(LLVMContext::MD_align)) {
    3944          45 :     Assert(I.getType()->isPointerTy(), "align applies only to pointer types",
    3945             :            &I);
    3946          22 :     Assert(isa<LoadInst>(I), "align applies only to load instructions, "
    3947             :            "use attributes for calls or invokes", &I);
    3948          21 :     Assert(AlignMD->getNumOperands() == 1, "align takes one operand!", &I);
    3949             :     ConstantInt *CI = mdconst::dyn_extract<ConstantInt>(AlignMD->getOperand(0));
    3950          22 :     Assert(CI && CI->getType()->isIntegerTy(64),
    3951             :            "align metadata value must be an i64!", &I);
    3952             :     uint64_t Align = CI->getZExtValue();
    3953           2 :     Assert(isPowerOf2_64(Align),
    3954             :            "align metadata value must be a power of 2!", &I);
    3955          17 :     Assert(Align <= Value::MaximumAlignment,
    3956             :            "alignment is larger that implementation defined limit", &I);
    3957             :   }
    3958             : 
    3959     6037045 :   if (MDNode *N = I.getDebugLoc().getAsMDNode()) {
    3960       95301 :     AssertDI(isa<DILocation>(N), "invalid !dbg metadata attachment", &I, N);
    3961       95293 :     visitMDNode(*N);
    3962             :   }
    3963             : 
    3964             :   if (auto *DII = dyn_cast<DbgInfoIntrinsic>(&I))
    3965       14434 :     verifyFragmentExpression(*DII);
    3966             : 
    3967     6037041 :   InstsInThisBlock.insert(&I);
    3968             : }
    3969             : 
    3970             : /// Allow intrinsics to be verified in different ways.
    3971      319582 : void Verifier::visitIntrinsicCallSite(Intrinsic::ID ID, CallSite CS) {
    3972      319582 :   Function *IF = CS.getCalledFunction();
    3973      319648 :   Assert(IF->isDeclaration(), "Intrinsic functions should never be defined!",
    3974             :          IF);
    3975             : 
    3976             :   // Verify that the intrinsic prototype lines up with what the .td files
    3977             :   // describe.
    3978      319582 :   FunctionType *IFTy = IF->getFunctionType();
    3979             :   bool IsVarArg = IFTy->isVarArg();
    3980             : 
    3981             :   SmallVector<Intrinsic::IITDescriptor, 8> Table;
    3982      319582 :   getIntrinsicInfoTableEntries(ID, Table);
    3983             :   ArrayRef<Intrinsic::IITDescriptor> TableRef = Table;
    3984             : 
    3985             :   SmallVector<Type *, 4> ArgTys;
    3986      639166 :   Assert(!Intrinsic::matchIntrinsicType(IFTy->getReturnType(),
    3987             :                                         TableRef, ArgTys),
    3988             :          "Intrinsic has incorrect return type!", IF);
    3989     1323396 :   for (unsigned i = 0, e = IFTy->getNumParams(); i != e; ++i)
    3990     1368529 :     Assert(!Intrinsic::matchIntrinsicType(IFTy->getParamType(i),
    3991             :                                           TableRef, ArgTys),
    3992             :            "Intrinsic has incorrect argument type!", IF);
    3993             : 
    3994             :   // Verify if the intrinsic call matches the vararg property.
    3995      319561 :   if (IsVarArg)
    3996        2729 :     Assert(!Intrinsic::matchIntrinsicVarArg(IsVarArg, TableRef),
    3997             :            "Intrinsic was not defined with variable arguments!", IF);
    3998             :   else
    3999      316834 :     Assert(!Intrinsic::matchIntrinsicVarArg(IsVarArg, TableRef),
    4000             :            "Callsite was not defined with variable arguments!", IF);
    4001             : 
    4002             :   // All descriptors should be absorbed by now.
    4003      319559 :   Assert(TableRef.empty(), "Intrinsic has too few arguments!", IF);
    4004             : 
    4005             :   // Now that we have the intrinsic ID and the actual argument types (and we
    4006             :   // know they are legal for the intrinsic!) get the intrinsic name through the
    4007             :   // usual means.  This allows us to verify the mangling of argument types into
    4008             :   // the name.
    4009      319559 :   const std::string ExpectedName = Intrinsic::getName(ID, ArgTys);
    4010      319559 :   Assert(ExpectedName == IF->getName(),
    4011             :          "Intrinsic name not mangled correctly for type arguments! "
    4012             :          "Should be: " +
    4013             :              ExpectedName,
    4014             :          IF);
    4015             : 
    4016             :   // If the intrinsic takes MDNode arguments, verify that they are either global
    4017             :   // or are local to *this* function.
    4018     1011555 :   for (Value *V : CS.args())
    4019             :     if (auto *MD = dyn_cast<MetadataAsValue>(V))
    4020       45791 :       visitMetadataAsValue(*MD, CS.getCaller());
    4021             : 
    4022      319559 :   switch (ID) {
    4023             :   default:
    4024             :     break;
    4025         116 :   case Intrinsic::coro_id: {
    4026         116 :     auto *InfoArg = CS.getArgOperand(3)->stripPointerCasts();
    4027         116 :     if (isa<ConstantPointerNull>(InfoArg))
    4028             :       break;
    4029             :     auto *GV = dyn_cast<GlobalVariable>(InfoArg);
    4030          33 :     Assert(GV && GV->isConstant() && GV->hasDefinitiveInitializer(),
    4031             :       "info argument of llvm.coro.begin must refer to an initialized "
    4032             :       "constant");
    4033             :     Constant *Init = GV->getInitializer();
    4034          66 :     Assert(isa<ConstantStruct>(Init) || isa<ConstantArray>(Init),
    4035             :       "info argument of llvm.coro.begin must refer to either a struct or "
    4036             :       "an array");
    4037             :     break;
    4038             :   }
    4039        7866 :   case Intrinsic::ctlz:  // llvm.ctlz
    4040             :   case Intrinsic::cttz:  // llvm.cttz
    4041       15734 :     Assert(isa<ConstantInt>(CS.getArgOperand(1)),
    4042             :            "is_zero_undef argument of bit counting intrinsics must be a "
    4043             :            "constant int",
    4044             :            CS);
    4045             :     break;
    4046             :   case Intrinsic::experimental_constrained_fadd:
    4047             :   case Intrinsic::experimental_constrained_fsub:
    4048             :   case Intrinsic::experimental_constrained_fmul:
    4049             :   case Intrinsic::experimental_constrained_fdiv:
    4050             :   case Intrinsic::experimental_constrained_frem:
    4051             :   case Intrinsic::experimental_constrained_fma:
    4052             :   case Intrinsic::experimental_constrained_sqrt:
    4053             :   case Intrinsic::experimental_constrained_pow:
    4054             :   case Intrinsic::experimental_constrained_powi:
    4055             :   case Intrinsic::experimental_constrained_sin:
    4056             :   case Intrinsic::experimental_constrained_cos:
    4057             :   case Intrinsic::experimental_constrained_exp:
    4058             :   case Intrinsic::experimental_constrained_exp2:
    4059             :   case Intrinsic::experimental_constrained_log:
    4060             :   case Intrinsic::experimental_constrained_log10:
    4061             :   case Intrinsic::experimental_constrained_log2:
    4062             :   case Intrinsic::experimental_constrained_rint:
    4063             :   case Intrinsic::experimental_constrained_nearbyint:
    4064         303 :     visitConstrainedFPIntrinsic(
    4065             :         cast<ConstrainedFPIntrinsic>(*CS.getInstruction()));
    4066         303 :     break;
    4067        7678 :   case Intrinsic::dbg_declare: // llvm.dbg.declare
    4068       15356 :     Assert(isa<MetadataAsValue>(CS.getArgOperand(0)),
    4069             :            "invalid llvm.dbg.declare intrinsic call 1", CS);
    4070        7678 :     visitDbgIntrinsic("declare", cast<DbgInfoIntrinsic>(*CS.getInstruction()));
    4071        7678 :     break;
    4072             :   case Intrinsic::dbg_addr: // llvm.dbg.addr
    4073          23 :     visitDbgIntrinsic("addr", cast<DbgInfoIntrinsic>(*CS.getInstruction()));
    4074          23 :     break;
    4075             :   case Intrinsic::dbg_value: // llvm.dbg.value
    4076        6678 :     visitDbgIntrinsic("value", cast<DbgInfoIntrinsic>(*CS.getInstruction()));
    4077        6678 :     break;
    4078             :   case Intrinsic::dbg_label: // llvm.dbg.label
    4079          57 :     visitDbgLabelIntrinsic("label", cast<DbgLabelInst>(*CS.getInstruction()));
    4080          57 :     break;
    4081             :   case Intrinsic::memcpy:
    4082             :   case Intrinsic::memmove:
    4083             :   case Intrinsic::memset: {
    4084             :     const auto *MI = cast<MemIntrinsic>(CS.getInstruction());
    4085             :     auto IsValidAlignment = [&](unsigned Alignment) -> bool {
    4086       31310 :       return Alignment == 0 || isPowerOf2_32(Alignment);
    4087             :     };
    4088           0 :     Assert(IsValidAlignment(MI->getDestAlignment()),
    4089             :            "alignment of arg 0 of memory intrinsic must be 0 or a power of 2",
    4090             :            CS);
    4091             :     if (const auto *MTI = dyn_cast<MemTransferInst>(MI)) {
    4092           0 :       Assert(IsValidAlignment(MTI->getSourceAlignment()),
    4093             :              "alignment of arg 1 of memory intrinsic must be 0 or a power of 2",
    4094             :              CS);
    4095             :     }
    4096       35000 :     Assert(isa<ConstantInt>(CS.getArgOperand(3)),
    4097             :            "isvolatile argument of memory intrinsics must be a constant int",
    4098             :            CS);
    4099             :     break;
    4100             :   }
    4101             :   case Intrinsic::memcpy_element_unordered_atomic:
    4102             :   case Intrinsic::memmove_element_unordered_atomic:
    4103             :   case Intrinsic::memset_element_unordered_atomic: {
    4104             :     const auto *AMI = cast<AtomicMemIntrinsic>(CS.getInstruction());
    4105             : 
    4106             :     ConstantInt *ElementSizeCI =
    4107             :         dyn_cast<ConstantInt>(AMI->getRawElementSizeInBytes());
    4108          25 :     Assert(ElementSizeCI,
    4109             :            "element size of the element-wise unordered atomic memory "
    4110             :            "intrinsic must be a constant int",
    4111             :            CS);
    4112             :     const APInt &ElementSizeVal = ElementSizeCI->getValue();
    4113         376 :     Assert(ElementSizeVal.isPowerOf2(),
    4114             :            "element size of the element-wise atomic memory intrinsic "
    4115             :            "must be a power of 2",
    4116             :            CS);
    4117             : 
    4118             :     if (auto *LengthCI = dyn_cast<ConstantInt>(AMI->getLength())) {
    4119             :       uint64_t Length = LengthCI->getZExtValue();
    4120             :       uint64_t ElementSize = AMI->getElementSizeInBytes();
    4121         356 :       Assert((Length % ElementSize) == 0,
    4122             :              "constant length must be a multiple of the element size in the "
    4123             :              "element-wise atomic memory intrinsic",
    4124             :              CS);
    4125             :     }
    4126             : 
    4127         627 :     auto IsValidAlignment = [&](uint64_t Alignment) {
    4128        1244 :       return isPowerOf2_64(Alignment) && ElementSizeVal.ule(Alignment);
    4129         994 :     };
    4130         367 :     uint64_t DstAlignment = AMI->getDestAlignment();
    4131         373 :     Assert(IsValidAlignment(DstAlignment),
    4132             :            "incorrect alignment of the destination argument", CS);
    4133             :     if (const auto *AMT = dyn_cast<AtomicMemTransferInst>(AMI)) {
    4134         260 :       uint64_t SrcAlignment = AMT->getSourceAlignment();
    4135         264 :       Assert(IsValidAlignment(SrcAlignment),
    4136             :              "incorrect alignment of the source argument", CS);
    4137             :     }
    4138         357 :     break;
    4139             :   }
    4140          50 :   case Intrinsic::gcroot:
    4141             :   case Intrinsic::gcwrite:
    4142             :   case Intrinsic::gcread:
    4143          50 :     if (ID == Intrinsic::gcroot) {
    4144             :       AllocaInst *AI =
    4145          30 :         dyn_cast<AllocaInst>(CS.getArgOperand(0)->stripPointerCasts());
    4146           0 :       Assert(AI, "llvm.gcroot parameter #1 must be an alloca.", CS);
    4147          60 :       Assert(isa<Constant>(CS.getArgOperand(1)),
    4148             :              "llvm.gcroot parameter #2 must be a constant.", CS);
    4149          60 :       if (!AI->getAllocatedType()->isPointerTy()) {
    4150           2 :         Assert(!isa<ConstantPointerNull>(CS.getArgOperand(1)),
    4151             :                "llvm.gcroot parameter #1 must either be a pointer alloca, "
    4152             :                "or argument #2 must be a non-null constant.",
    4153             :                CS);
    4154             :       }
    4155             :     }
    4156             : 
    4157          99 :     Assert(CS.getParent()->getParent()->hasGC(),
    4158             :            "Enclosing function does not use GC.", CS);
    4159             :     break;
    4160          29 :   case Intrinsic::init_trampoline:
    4161          58 :     Assert(isa<Function>(CS.getArgOperand(1)->stripPointerCasts()),
    4162             :            "llvm.init_trampoline parameter #2 must resolve to a function.",
    4163             :            CS);
    4164             :     break;
    4165         662 :   case Intrinsic::prefetch:
    4166        3310 :     Assert(isa<ConstantInt>(CS.getArgOperand(1)) &&
    4167             :                isa<ConstantInt>(CS.getArgOperand(2)) &&
    4168             :                cast<ConstantInt>(CS.getArgOperand(1))->getZExtValue() < 2 &&
    4169             :                cast<ConstantInt>(CS.getArgOperand(2))->getZExtValue() < 4,
    4170             :            "invalid arguments to llvm.prefetch", CS);
    4171             :     break;
    4172         655 :   case Intrinsic::stackprotector:
    4173         655 :     Assert(isa<AllocaInst>(CS.getArgOperand(1)->stripPointerCasts()),
    4174             :            "llvm.stackprotector parameter #2 must resolve to an alloca.", CS);
    4175             :     break;
    4176        7235 :   case Intrinsic::lifetime_start:
    4177             :   case Intrinsic::lifetime_end:
    4178             :   case Intrinsic::invariant_start:
    4179       14470 :     Assert(isa<ConstantInt>(CS.getArgOperand(0)),
    4180             :            "size argument of memory use markers must be a constant integer",
    4181             :            CS);
    4182             :     break;
    4183          59 :   case Intrinsic::invariant_end:
    4184         118 :     Assert(isa<ConstantInt>(CS.getArgOperand(1)),
    4185             :            "llvm.invariant.end parameter #2 must be a constant integer", CS);
    4186             :     break;
    4187             : 
    4188             :   case Intrinsic::localescape: {
    4189             :     BasicBlock *BB = CS.getParent();
    4190         195 :     Assert(BB == &BB->getParent()->front(),
    4191             :            "llvm.localescape used outside of entry block", CS);
    4192          97 :     Assert(!SawFrameEscape,
    4193             :            "multiple calls to llvm.localescape in one function", CS);
    4194         215 :     for (Value *Arg : CS.args()) {
    4195         121 :       if (isa<ConstantPointerNull>(Arg))
    4196           0 :         continue; // Null values are allowed as placeholders.
    4197             :       auto *AI = dyn_cast<AllocaInst>(Arg->stripPointerCasts());
    4198         121 :       Assert(AI && AI->isStaticAlloca(),
    4199             :              "llvm.localescape only accepts static allocas", CS);
    4200             :     }
    4201         188 :     FrameEscapeInfo[BB->getParent()].first = CS.getNumArgOperands();
    4202          94 :     SawFrameEscape = true;
    4203          94 :     break;
    4204             :   }
    4205         108 :   case Intrinsic::localrecover: {
    4206         108 :     Value *FnArg = CS.getArgOperand(0)->stripPointerCasts();
    4207         108 :     Function *Fn = dyn_cast<Function>(FnArg);
    4208         118 :     Assert(Fn && !Fn->isDeclaration(),
    4209             :            "llvm.localrecover first "
    4210             :            "argument must be function defined in this module",
    4211             :            CS);
    4212         105 :     auto *IdxArg = dyn_cast<ConstantInt>(CS.getArgOperand(2));
    4213           2 :     Assert(IdxArg, "idx argument of llvm.localrecover must be a constant int",
    4214             :            CS);
    4215         104 :     auto &Entry = FrameEscapeInfo[Fn];
    4216         104 :     Entry.second = unsigned(
    4217         312 :         std::max(uint64_t(Entry.second), IdxArg->getLimitedValue(~0U) + 1));
    4218         104 :     break;
    4219             :   }
    4220             : 
    4221             :   case Intrinsic::experimental_gc_statepoint:
    4222         637 :     Assert(!CS.isInlineAsm(),
    4223             :            "gc.statepoint support for inline assembly unimplemented", CS);
    4224        1407 :     Assert(CS.getParent()->getParent()->hasGC(),
    4225             :            "Enclosing function does not use GC.", CS);
    4226             : 
    4227         702 :     verifyStatepoint(CS);
    4228         702 :     break;
    4229             :   case Intrinsic::experimental_gc_result: {
    4230         218 :     Assert(CS.getParent()->getParent()->hasGC(),
    4231             :            "Enclosing function does not use GC.", CS);
    4232             :     // Are we tied to a statepoint properly?
    4233         109 :     CallSite StatepointCS(CS.getArgOperand(0));
    4234             :     const Function *StatepointFn =
    4235         109 :       StatepointCS.getInstruction() ? StatepointCS.getCalledFunction() : nullptr;
    4236         109 :     Assert(StatepointFn && StatepointFn->isDeclaration() &&
    4237             :                StatepointFn->getIntrinsicID() ==
    4238             :                    Intrinsic::experimental_gc_statepoint,
    4239             :            "gc.result operand #1 must be from a statepoint", CS,
    4240             :            CS.getArgOperand(0));
    4241             : 
    4242             :     // Assert that result type matches wrapped callee.
    4243             :     const Value *Target = StatepointCS.getArgument(2);
    4244         109 :     auto *PT = cast<PointerType>(Target->getType());
    4245         109 :     auto *TargetFuncType = cast<FunctionType>(PT->getElementType());
    4246         218 :     Assert(CS.getType() == TargetFuncType->getReturnType(),
    4247             :            "gc.result result type does not match wrapped callee", CS);
    4248             :     break;
    4249             :   }
    4250         775 :   case Intrinsic::experimental_gc_relocate: {
    4251         780 :     Assert(CS.getNumArgOperands() == 3, "wrong number of arguments", CS);
    4252             : 
    4253         776 :     Assert(isa<PointerType>(CS.getType()->getScalarType()),
    4254             :            "gc.relocate must return a pointer or a vector of pointers", CS);
    4255             : 
    4256             :     // Check that this relocate is correctly tied to the statepoint
    4257             : 
    4258             :     // This is case for relocate on the unwinding path of an invoke statepoint
    4259             :     if (LandingPadInst *LandingPad =
    4260         774 :           dyn_cast<LandingPadInst>(CS.getArgOperand(0))) {
    4261             : 
    4262             :       const BasicBlock *InvokeBB =
    4263         150 :           LandingPad->getParent()->getUniquePredecessor();
    4264             : 
    4265             :       // Landingpad relocates should have only one predecessor with invoke
    4266             :       // statepoint terminator
    4267          75 :       Assert(InvokeBB, "safepoints should have unique landingpads",
    4268             :              LandingPad->getParent());
    4269          75 :       Assert(InvokeBB->getTerminator(), "safepoint block should be well formed",
    4270             :              InvokeBB);
    4271          75 :       Assert(isStatepoint(InvokeBB->getTerminator()),
    4272             :              "gc relocate should be linked to a statepoint", InvokeBB);
    4273             :     }
    4274             :     else {
    4275             :       // In all other cases relocate should be tied to the statepoint directly.
    4276             :       // This covers relocates on a normal return path of invoke statepoint and
    4277             :       // relocates of a call statepoint.
    4278         699 :       auto Token = CS.getArgOperand(0);
    4279         699 :       Assert(isa<Instruction>(Token) && isStatepoint(cast<Instruction>(Token)),
    4280             :              "gc relocate is incorrectly tied to the statepoint", CS, Token);
    4281             :     }
    4282             : 
    4283             :     // Verify rest of the relocate arguments.
    4284             : 
    4285             :     ImmutableCallSite StatepointCS(
    4286         774 :         cast<GCRelocateInst>(*CS.getInstruction()).getStatepoint());
    4287             : 
    4288             :     // Both the base and derived must be piped through the safepoint.
    4289         774 :     Value* Base = CS.getArgOperand(1);
    4290         774 :     Assert(isa<ConstantInt>(Base),
    4291             :            "gc.relocate operand #2 must be integer offset", CS);
    4292             : 
    4293         774 :     Value* Derived = CS.getArgOperand(2);
    4294         774 :     Assert(isa<ConstantInt>(Derived),
    4295             :            "gc.relocate operand #3 must be integer offset", CS);
    4296             : 
    4297         774 :     const int BaseIndex = cast<ConstantInt>(Base)->getZExtValue();
    4298         774 :     const int DerivedIndex = cast<ConstantInt>(Derived)->getZExtValue();
    4299             :     // Check the bounds
    4300         774 :     Assert(0 <= BaseIndex && BaseIndex < (int)StatepointCS.arg_size(),
    4301             :            "gc.relocate: statepoint base index out of bounds", CS);
    4302        1548 :     Assert(0 <= DerivedIndex && DerivedIndex < (int)StatepointCS.arg_size(),
    4303             :            "gc.relocate: statepoint derived index out of bounds", CS);
    4304             : 
    4305             :     // Check that BaseIndex and DerivedIndex fall within the 'gc parameters'
    4306             :     // section of the statepoint's argument.
    4307         774 :     Assert(StatepointCS.arg_size() > 0,
    4308             :            "gc.statepoint: insufficient arguments");
    4309         774 :     Assert(isa<ConstantInt>(StatepointCS.getArgument(3)),
    4310             :            "gc.statement: number of call arguments must be constant integer");
    4311             :     const unsigned NumCallArgs =
    4312         774 :         cast<ConstantInt>(StatepointCS.getArgument(3))->getZExtValue();
    4313         775 :     Assert(StatepointCS.arg_size() > NumCallArgs + 5,
    4314             :            "gc.statepoint: mismatch in number of call arguments");
    4315         773 :     Assert(isa<ConstantInt>(StatepointCS.getArgument(NumCallArgs + 5)),
    4316             :            "gc.statepoint: number of transition arguments must be "
    4317             :            "a constant integer");
    4318             :     const int NumTransitionArgs =
    4319             :         cast<ConstantInt>(StatepointCS.getArgument(NumCallArgs + 5))
    4320             :             ->getZExtValue();
    4321         773 :     const int DeoptArgsStart = 4 + NumCallArgs + 1 + NumTransitionArgs + 1;
    4322         774 :     Assert(isa<ConstantInt>(StatepointCS.getArgument(DeoptArgsStart)),
    4323             :            "gc.statepoint: number of deoptimization arguments must be "
    4324             :            "a constant integer");
    4325             :     const int NumDeoptArgs =
    4326             :         cast<ConstantInt>(StatepointCS.getArgument(DeoptArgsStart))
    4327         772 :             ->getZExtValue();
    4328         772 :     const int GCParamArgsStart = DeoptArgsStart + 1 + NumDeoptArgs;
    4329         772 :     const int GCParamArgsEnd = StatepointCS.arg_size();
    4330         772 :     Assert(GCParamArgsStart <= BaseIndex && BaseIndex < GCParamArgsEnd,
    4331             :            "gc.relocate: statepoint base index doesn't fall within the "
    4332             :            "'gc parameters' section of the statepoint call",
    4333             :            CS);
    4334         772 :     Assert(GCParamArgsStart <= DerivedIndex && DerivedIndex < GCParamArgsEnd,
    4335             :            "gc.relocate: statepoint derived index doesn't fall within the "
    4336             :            "'gc parameters' section of the statepoint call",
    4337             :            CS);
    4338             : 
    4339             :     // Relocated value must be either a pointer type or vector-of-pointer type,
    4340             :     // but gc_relocate does not need to return the same pointer type as the
    4341             :     // relocated pointer. It can be casted to the correct type later if it's
    4342             :     // desired. However, they must have the same address space and 'vectorness'
    4343             :     GCRelocateInst &Relocate = cast<GCRelocateInst>(*CS.getInstruction());
    4344        1545 :     Assert(Relocate.getDerivedPtr()->getType()->isPtrOrPtrVectorTy(),
    4345             :            "gc.relocate: relocated value must be a gc pointer", CS);
    4346             : 
    4347             :     auto ResultType = CS.getType();
    4348         771 :     auto DerivedType = Relocate.getDerivedPtr()->getType();
    4349         771 :     Assert(ResultType->isVectorTy() == DerivedType->isVectorTy(),
    4350             :            "gc.relocate: vector relocates to vector and pointer to pointer",
    4351             :            CS);
    4352         772 :     Assert(
    4353             :         ResultType->getPointerAddressSpace() ==
    4354             :             DerivedType->getPointerAddressSpace(),
    4355             :         "gc.relocate: relocating a pointer shouldn't change its address space",
    4356             :         CS);
    4357         770 :     break;
    4358             :   }
    4359          58 :   case Intrinsic::eh_exceptioncode:
    4360             :   case Intrinsic::eh_exceptionpointer: {
    4361          60 :     Assert(isa<CatchPadInst>(CS.getArgOperand(0)),
    4362             :            "eh.exceptionpointer argument must be a catchpad", CS);
    4363             :     break;
    4364             :   }
    4365             :   case Intrinsic::masked_load: {
    4366        1239 :     Assert(CS.getType()->isVectorTy(), "masked_load: must return a vector", CS);
    4367             : 
    4368        1239 :     Value *Ptr = CS.getArgOperand(0);
    4369             :     //Value *Alignment = CS.getArgOperand(1);
    4370        1239 :     Value *Mask = CS.getArgOperand(2);
    4371        1239 :     Value *PassThru = CS.getArgOperand(3);
    4372        2478 :     Assert(Mask->getType()->isVectorTy(),
    4373             :            "masked_load: mask must be vector", CS);
    4374             : 
    4375             :     // DataTy is the overloaded type
    4376        1239 :     Type *DataTy = cast<PointerType>(Ptr->getType())->getElementType();
    4377        1239 :     Assert(DataTy == CS.getType(),
    4378             :            "masked_load: return must match pointer type", CS);
    4379        1239 :     Assert(PassThru->getType() == DataTy,
    4380             :            "masked_load: pass through and data type must match", CS);
    4381        1239 :     Assert(Mask->getType()->getVectorNumElements() ==
    4382             :            DataTy->getVectorNumElements(),
    4383             :            "masked_load: vector mask must be same length as data", CS);
    4384             :     break;
    4385             :   }
    4386         719 :   case Intrinsic::masked_store: {
    4387         719 :     Value *Val = CS.getArgOperand(0);
    4388         719 :     Value *Ptr = CS.getArgOperand(1);
    4389             :     //Value *Alignment = CS.getArgOperand(2);
    4390         719 :     Value *Mask = CS.getArgOperand(3);
    4391        1438 :     Assert(Mask->getType()->isVectorTy(),
    4392             :            "masked_store: mask must be vector", CS);
    4393             : 
    4394             :     // DataTy is the overloaded type
    4395         719 :     Type *DataTy = cast<PointerType>(Ptr->getType())->getElementType();
    4396         719 :     Assert(DataTy == Val->getType(),
    4397             :            "masked_store: storee must match pointer type", CS);
    4398         719 :     Assert(Mask->getType()->getVectorNumElements() ==
    4399             :            DataTy->getVectorNumElements(),
    4400             :            "masked_store: vector mask must be same length as data", CS);
    4401             :     break;
    4402             :   }
    4403             : 
    4404             :   case Intrinsic::experimental_guard: {
    4405         760 :     Assert(CS.isCall(), "experimental_guard cannot be invoked", CS);
    4406         759 :     Assert(CS.countOperandBundlesOfType(LLVMContext::OB_deopt) == 1,
    4407             :            "experimental_guard must have exactly one "
    4408             :            "\"deopt\" operand bundle");
    4409             :     break;
    4410             :   }
    4411             : 
    4412             :   case Intrinsic::experimental_deoptimize: {
    4413          62 :     Assert(CS.isCall(), "experimental_deoptimize cannot be invoked", CS);
    4414          61 :     Assert(CS.countOperandBundlesOfType(LLVMContext::OB_deopt) == 1,
    4415             :            "experimental_deoptimize must have exactly one "
    4416             :            "\"deopt\" operand bundle");
    4417          59 :     Assert(CS.getType() == CS.getInstruction()->getFunction()->getReturnType(),
    4418             :            "experimental_deoptimize return type must match caller return type");
    4419             : 
    4420          59 :     if (CS.isCall()) {
    4421             :       auto *DeoptCI = CS.getInstruction();
    4422             :       auto *RI = dyn_cast<ReturnInst>(DeoptCI->getNextNode());
    4423           1 :       Assert(RI,
    4424             :              "calls to experimental_deoptimize must be followed by a return");
    4425             : 
    4426          58 :       if (!CS.getType()->isVoidTy() && RI)
    4427          46 :         Assert(RI->getReturnValue() == DeoptCI,
    4428             :                "calls to experimental_deoptimize must be followed by a return "
    4429             :                "of the value computed by experimental_deoptimize");
    4430             :     }
    4431             : 
    4432             :     break;
    4433             :   }
    4434             :   };
    4435             : }
    4436             : 
    4437             : /// Carefully grab the subprogram from a local scope.
    4438             : ///
    4439             : /// This carefully grabs the subprogram from a local scope, avoiding the
    4440             : /// built-in assertions that would typically fire.
    4441             : static DISubprogram *getSubprogram(Metadata *LocalScope) {
    4442       35675 :   if (!LocalScope)
    4443             :     return nullptr;
    4444             : 
    4445             :   if (auto *SP = dyn_cast<DISubprogram>(LocalScope))
    4446             :     return SP;
    4447             : 
    4448             :   if (auto *LB = dyn_cast<DILexicalBlockBase>(LocalScope))
    4449             :     return getSubprogram(LB->getRawScope());
    4450             : 
    4451             :   // Just return null; broken scope chains are checked elsewhere.
    4452             :   assert(!isa<DILocalScope>(LocalScope) && "Unknown type of local scope");
    4453             :   return nullptr;
    4454             : }
    4455             : 
    4456         303 : void Verifier::visitConstrainedFPIntrinsic(ConstrainedFPIntrinsic &FPI) {
    4457         303 :   unsigned NumOperands = FPI.getNumArgOperands();
    4458         303 :   Assert(((NumOperands == 5 && FPI.isTernaryOp()) ||
    4459             :           (NumOperands == 3 && FPI.isUnaryOp()) || (NumOperands == 4)),
    4460             :            "invalid arguments for constrained FP intrinsic", &FPI);
    4461         606 :   Assert(isa<MetadataAsValue>(FPI.getArgOperand(NumOperands-1)),
    4462             :          "invalid exception behavior argument", &FPI);
    4463         606 :   Assert(isa<MetadataAsValue>(FPI.getArgOperand(NumOperands-2)),
    4464             :          "invalid rounding mode argument", &FPI);
    4465         305 :   Assert(FPI.getRoundingMode() != ConstrainedFPIntrinsic::rmInvalid,
    4466             :          "invalid rounding mode argument", &FPI);
    4467         303 :   Assert(FPI.getExceptionBehavior() != ConstrainedFPIntrinsic::ebInvalid,
    4468             :          "invalid exception behavior argument", &FPI);
    4469             : }
    4470             : 
    4471       14379 : void Verifier::visitDbgIntrinsic(StringRef Kind, DbgInfoIntrinsic &DII) {
    4472       28758 :   auto *MD = cast<MetadataAsValue>(DII.getArgOperand(0))->getMetadata();
    4473         130 :   AssertDI(isa<ValueAsMetadata>(MD) ||
    4474             :              (isa<MDNode>(MD) && !cast<MDNode>(MD)->getNumOperands()),
    4475             :          "invalid llvm.dbg." + Kind + " intrinsic address/value", &DII, MD);
    4476       14379 :   AssertDI(isa<DILocalVariable>(DII.getRawVariable()),
    4477             :          "invalid llvm.dbg." + Kind + " intrinsic variable", &DII,
    4478             :          DII.getRawVariable());
    4479       14377 :   AssertDI(isa<DIExpression>(DII.getRawExpression()),
    4480             :          "invalid llvm.dbg." + Kind + " intrinsic expression", &DII,
    4481             :          DII.getRawExpression());
    4482             : 
    4483             :   // Ignore broken !dbg attachments; they're checked elsewhere.
    4484       14373 :   if (MDNode *N = DII.getDebugLoc().getAsMDNode())
    4485       14369 :     if (!isa<DILocation>(N))
    4486             :       return;
    4487             : 
    4488       14371 :   BasicBlock *BB = DII.getParent();
    4489       14371 :   Function *F = BB ? BB->getParent() : nullptr;
    4490             : 
    4491             :   // The scopes for variables and !dbg attachments must agree.
    4492       14371 :   DILocalVariable *Var = DII.getVariable();
    4493       14371 :   DILocation *Loc = DII.getDebugLoc();
    4494       14375 :   AssertDI(Loc, "llvm.dbg." + Kind + " intrinsic requires a !dbg attachment",
    4495             :            &DII, BB, F);
    4496             : 
    4497       14367 :   DISubprogram *VarSP = getSubprogram(Var->getRawScope());
    4498             :   DISubprogram *LocSP = getSubprogram(Loc->getRawScope());
    4499       14367 :   if (!VarSP || !LocSP)
    4500             :     return; // Broken scope chains are checked elsewhere.
    4501             : 
    4502       14371 :   AssertDI(VarSP == LocSP, "mismatched subprogram between llvm.dbg." + Kind +
    4503             :                                " variable and !dbg attachment",
    4504             :            &DII, BB, F, Var, Var->getScope()->getSubprogram(), Loc,
    4505             :            Loc->getScope()->getSubprogram());
    4506             : 
    4507       14365 :   verifyFnArgs(DII);
    4508             : }
    4509             : 
    4510          57 : void Verifier::visitDbgLabelIntrinsic(StringRef Kind, DbgLabelInst &DLI) {
    4511          57 :   AssertDI(isa<DILabel>(DLI.getRawVariable()),
    4512             :          "invalid llvm.dbg." + Kind + " intrinsic variable", &DLI,
    4513             :          DLI.getRawVariable());
    4514             : 
    4515             :   // Ignore broken !dbg attachments; they're checked elsewhere.
    4516          57 :   if (MDNode *N = DLI.getDebugLoc().getAsMDNode())
    4517          57 :     if (!isa<DILocation>(N))
    4518             :       return;
    4519             : 
    4520          57 :   BasicBlock *BB = DLI.getParent();
    4521          57 :   Function *F = BB ? BB->getParent() : nullptr;
    4522             : 
    4523             :   // The scopes for variables and !dbg attachments must agree.
    4524          57 :   DILabel *Label = DLI.getLabel();
    4525          57 :   DILocation *Loc = DLI.getDebugLoc();
    4526          57 :   Assert(Loc, "llvm.dbg." + Kind + " intrinsic requires a !dbg attachment",
    4527             :          &DLI, BB, F);
    4528             : 
    4529          57 :   DISubprogram *LabelSP = getSubprogram(Label->getRawScope());
    4530             :   DISubprogram *LocSP = getSubprogram(Loc->getRawScope());
    4531          57 :   if (!LabelSP || !LocSP)
    4532             :     return;
    4533             : 
    4534          57 :   AssertDI(LabelSP == LocSP, "mismatched subprogram between llvm.dbg." + Kind +
    4535             :                              " label and !dbg attachment",
    4536             :            &DLI, BB, F, Label, Label->getScope()->getSubprogram(), Loc,
    4537             :            Loc->getScope()->getSubprogram());
    4538             : }
    4539             : 
    4540       14434 : void Verifier::verifyFragmentExpression(const DbgInfoIntrinsic &I) {
    4541             :   if (dyn_cast<DbgLabelInst>(&I))
    4542       14050 :     return;
    4543             : 
    4544             :   DILocalVariable *V = dyn_cast_or_null<DILocalVariable>(I.getRawVariable());
    4545             :   DIExpression *E = dyn_cast_or_null<DIExpression>(I.getRawExpression());
    4546             : 
    4547             :   // We don't know whether this intrinsic verified correctly.
    4548       14377 :   if (!V || !E || !E->isValid())
    4549             :     return;
    4550             : 
    4551             :   // Nothing to do if this isn't a DW_OP_LLVM_fragment expression.
    4552             :   auto Fragment = E->getFragmentInfo();
    4553       14372 :   if (!Fragment)
    4554             :     return;
    4555             : 
    4556             :   // The frontend helps out GDB by emitting the members of local anonymous
    4557             :   // unions as artificial local variables with shared storage. When SROA splits
    4558             :   // the storage for artificial local variables that are smaller than the entire
    4559             :   // union, the overhang piece will be outside of the allotted space for the
    4560             :   // variable and this check fails.
    4561             :   // FIXME: Remove this check as soon as clang stops doing this; it hides bugs.
    4562         392 :   if (V->isArtificial())
    4563             :     return;
    4564             : 
    4565         384 :   verifyFragmentExpression(*V, *Fragment, &I);
    4566             : }
    4567             : 
    4568             : template <typename ValueOrMetadata>
    4569         466 : void Verifier::verifyFragmentExpression(const DIVariable &V,
    4570             :                                         DIExpression::FragmentInfo Fragment,
    4571             :                                         ValueOrMetadata *Desc) {
    4572             :   // If there's no size, the type is broken, but that should be checked
    4573             :   // elsewhere.
    4574         466 :   auto VarSize = V.getSizeInBits();
    4575         466 :   if (!VarSize)
    4576             :     return;
    4577             : 
    4578         466 :   unsigned FragSize = Fragment.SizeInBits;
    4579         466 :   unsigned FragOffset = Fragment.OffsetInBits;
    4580         467 :   AssertDI(FragSize + FragOffset <= *VarSize,
    4581             :          "fragment is larger than or outside of variable", Desc, &V);
    4582         465 :   AssertDI(FragSize != *VarSize, "fragment covers entire variable", Desc, &V);
    4583             : }
    4584             : 
    4585       14365 : void Verifier::verifyFnArgs(const DbgInfoIntrinsic &I) {
    4586             :   // This function does not take the scope of noninlined function arguments into
    4587             :   // account. Don't run it if current function is nodebug, because it may
    4588             :   // contain inlined debug intrinsics.
    4589       14365 :   if (!HasDebugInfo)
    4590        8044 :     return;
    4591             : 
    4592             :   // For performance reasons only check non-inlined ones.
    4593             :   if (I.getDebugLoc()->getInlinedAt())
    4594             :     return;
    4595             : 
    4596       13204 :   DILocalVariable *Var = I.getVariable();
    4597       13204 :   AssertDI(Var, "dbg intrinsic without variable");
    4598             : 
    4599             :   unsigned ArgNo = Var->getArg();
    4600       13204 :   if (!ArgNo)
    4601             :     return;
    4602             : 
    4603             :   // Verify there are no duplicate function argument debug info entries.
    4604             :   // These will cause hard-to-debug assertions in the DWARF backend.
    4605        6322 :   if (DebugFnArgs.size() < ArgNo)
    4606        5738 :     DebugFnArgs.resize(ArgNo, nullptr);
    4607             : 
    4608       12644 :   auto *Prev = DebugFnArgs[ArgNo - 1];
    4609        6322 :   DebugFnArgs[ArgNo - 1] = Var;
    4610        6323 :   AssertDI(!Prev || (Prev == Var), "conflicting debug info for argument", &I,
    4611             :            Prev, Var);
    4612             : }
    4613             : 
    4614       95463 : void Verifier::verifyCompileUnits() {
    4615             :   // When more than one Module is imported into the same context, such as during
    4616             :   // an LTO build before linking the modules, ODR type uniquing may cause types
    4617             :   // to point to a different CU. This check does not make sense in this case.
    4618       95463 :   if (M.getContext().isODRUniquingDebugTypes())
    4619       23647 :     return;
    4620      143656 :   auto *CUs = M.getNamedMetadata("llvm.dbg.cu");
    4621             :   SmallPtrSet<const Metadata *, 2> Listed;
    4622       71828 :   if (CUs)
    4623        4809 :     Listed.insert(CUs->op_begin(), CUs->op_end());
    4624       78124 :   for (auto *CU : CUVisited)
    4625        6308 :     AssertDI(Listed.count(CU), "DICompileUnit not listed in llvm.dbg.cu", CU);
    4626       71816 :   CUVisited.clear();
    4627             : }
    4628             : 
    4629       95463 : void Verifier::verifyDeoptimizeCallingConvs() {
    4630       95463 :   if (DeoptimizeDeclarations.empty())
    4631       95433 :     return;
    4632             : 
    4633          31 :   const Function *First = DeoptimizeDeclarations[0];
    4634          57 :   for (auto *F : makeArrayRef(DeoptimizeDeclarations).slice(1)) {
    4635          15 :     Assert(First->getCallingConv() == F->getCallingConv(),
    4636             :            "All llvm.experimental.deoptimize declarations must have the same "
    4637             :            "calling convention",
    4638             :            First, F);
    4639             :   }
    4640             : }
    4641             : 
    4642             : //===----------------------------------------------------------------------===//
    4643             : //  Implement the public interfaces to this file...
    4644             : //===----------------------------------------------------------------------===//
    4645             : 
    4646         657 : bool llvm::verifyFunction(const Function &f, raw_ostream *OS) {
    4647             :   Function &F = const_cast<Function &>(f);
    4648             : 
    4649             :   // Don't use a raw_null_ostream.  Printing IR is expensive.
    4650        1314 :   Verifier V(OS, /*ShouldTreatBrokenDebugInfoAsError=*/true, *f.getParent());
    4651             : 
    4652             :   // Note that this function's return value is inverted from what you would
    4653             :   // expect of a function called "verify".
    4654        1314 :   return !V.verify(F);
    4655             : }
    4656             : 
    4657       38000 : bool llvm::verifyModule(const Module &M, raw_ostream *OS,
    4658             :                         bool *BrokenDebugInfo) {
    4659             :   // Don't use a raw_null_ostream.  Printing IR is expensive.
    4660       76000 :   Verifier V(OS, /*ShouldTreatBrokenDebugInfoAsError=*/!BrokenDebugInfo, M);
    4661             : 
    4662             :   bool Broken = false;
    4663      359494 :   for (const Function &F : M)
    4664      321494 :     Broken |= !V.verify(F);
    4665             : 
    4666       38000 :   Broken |= !V.verify();
    4667       38000 :   if (BrokenDebugInfo)
    4668        3519 :     *BrokenDebugInfo = V.hasBrokenDebugInfo();
    4669             :   // Note that this function's return value is inverted from what you would
    4670             :   // expect of a function called "verify".
    4671       38000 :   return Broken;
    4672             : }
    4673             : 
    4674             : namespace {
    4675             : 
    4676      115352 : struct VerifierLegacyPass : public FunctionPass {
    4677             :   static char ID;
    4678             : 
    4679             :   std::unique_ptr<Verifier> V;
    4680             :   bool FatalErrors = true;
    4681             : 
    4682         237 :   VerifierLegacyPass() : FunctionPass(ID) {
    4683          79 :     initializeVerifierLegacyPassPass(*PassRegistry::getPassRegistry());
    4684          79 :   }
    4685             :   explicit VerifierLegacyPass(bool FatalErrors)
    4686       57869 :       : FunctionPass(ID),
    4687      115738 :         FatalErrors(FatalErrors) {
    4688       57869 :     initializeVerifierLegacyPassPass(*PassRegistry::getPassRegistry());
    4689             :   }
    4690             : 
    4691       57728 :   bool doInitialization(Module &M) override {
    4692       57728 :     V = llvm::make_unique<Verifier>(
    4693      115456 :         &dbgs(), /*ShouldTreatBrokenDebugInfoAsError=*/false, M);
    4694       57728 :     return false;
    4695             :   }
    4696             : 
    4697      526293 :   bool runOnFunction(Function &F) override {
    4698      526293 :     if (!V->verify(F) && FatalErrors)
    4699           0 :       report_fatal_error("Broken function found, compilation aborted!");
    4700             : 
    4701      526293 :     return false;
    4702             :   }
    4703             : 
    4704       57463 :   bool doFinalization(Module &M) override {
    4705             :     bool HasErrors = false;
    4706      798382 :     for (Function &F : M)
    4707      740919 :       if (F.isDeclaration())
    4708      214900 :         HasErrors |= !V->verify(F);
    4709             : 
    4710       57463 :     HasErrors |= !V->verify();
    4711      114888 :     if (FatalErrors && (HasErrors || V->hasBrokenDebugInfo()))
    4712           0 :       report_fatal_error("Broken module found, compilation aborted!");
    4713       57463 :     return false;
    4714             :   }
    4715             : 
    4716       57719 :   void getAnalysisUsage(AnalysisUsage &AU) const override {
    4717             :     AU.setPreservesAll();
    4718       57719 :   }
    4719             : };
    4720             : 
    4721             : } // end anonymous namespace
    4722             : 
    4723             : /// Helper to issue failure from the TBAA verification
    4724          27 : template <typename... Tys> void TBAAVerifier::CheckFailed(Tys &&... Args) {
    4725          27 :   if (Diagnostic)
    4726          25 :     return Diagnostic->CheckFailed(Args...);
    4727             : }
    4728             : 
    4729             : #define AssertTBAA(C, ...)                                                     \
    4730             :   do {                                                                         \
    4731             :     if (!(C)) {                                                                \
    4732             :       CheckFailed(__VA_ARGS__);                                                \
    4733             :       return false;                                                            \
    4734             :     }                                                                          \
    4735             :   } while (false)
    4736             : 
    4737             : /// Verify that \p BaseNode can be used as the "base type" in the struct-path
    4738             : /// TBAA scheme.  This means \p BaseNode is either a scalar node, or a
    4739             : /// struct-type node describing an aggregate data structure (like a struct).
    4740             : TBAAVerifier::TBAABaseNodeSummary
    4741       55394 : TBAAVerifier::verifyTBAABaseNode(Instruction &I, const MDNode *BaseNode,
    4742             :                                  bool IsNewFormat) {
    4743       55394 :   if (BaseNode->getNumOperands() < 2) {
    4744           0 :     CheckFailed("Base nodes must have at least two operands", &I, BaseNode);
    4745           0 :     return {true, ~0u};
    4746             :   }
    4747             : 
    4748       55394 :   auto Itr = TBAABaseNodes.find(BaseNode);
    4749       55394 :   if (Itr != TBAABaseNodes.end())
    4750       49992 :     return Itr->second;
    4751             : 
    4752        5402 :   auto Result = verifyTBAABaseNodeImpl(I, BaseNode, IsNewFormat);
    4753        5402 :   auto InsertResult = TBAABaseNodes.insert({BaseNode, Result});
    4754             :   (void)InsertResult;
    4755             :   assert(InsertResult.second && "We just checked!");
    4756        5402 :   return Result;
    4757             : }
    4758             : 
    4759             : TBAAVerifier::TBAABaseNodeSummary
    4760        5402 : TBAAVerifier::verifyTBAABaseNodeImpl(Instruction &I, const MDNode *BaseNode,
    4761             :                                      bool IsNewFormat) {
    4762             :   const TBAAVerifier::TBAABaseNodeSummary InvalidNode = {true, ~0u};
    4763             : 
    4764        5402 :   if (BaseNode->getNumOperands() == 2) {
    4765             :     // Scalar nodes can only be accessed at offset 0.
    4766        1006 :     return isValidScalarTBAANode(BaseNode)
    4767             :                ? TBAAVerifier::TBAABaseNodeSummary({false, 0})
    4768        1006 :                : InvalidNode;
    4769             :   }
    4770             : 
    4771        4396 :   if (IsNewFormat) {
    4772         234 :     if (BaseNode->getNumOperands() % 3 != 0) {
    4773           0 :       CheckFailed("Access tag nodes must have the number of operands that is a "
    4774             :                   "multiple of 3!", BaseNode);
    4775           0 :       return InvalidNode;
    4776             :     }
    4777             :   } else {
    4778        4162 :     if (BaseNode->getNumOperands() % 2 != 1) {
    4779           1 :       CheckFailed("Struct tag nodes must have an odd number of operands!",
    4780             :                   BaseNode);
    4781           1 :       return InvalidNode;
    4782             :     }
    4783             :   }
    4784             : 
    4785             :   // Check the type size field.
    4786        4395 :   if (IsNewFormat) {
    4787             :     auto *TypeSizeNode = mdconst::dyn_extract_or_null<ConstantInt>(
    4788             :         BaseNode->getOperand(1));
    4789             :     if (!TypeSizeNode) {
    4790           0 :       CheckFailed("Type size nodes must be constants!", &I, BaseNode);
    4791           0 :       return InvalidNode;
    4792             :     }
    4793             :   }
    4794             : 
    4795             :   // Check the type name field. In the new format it can be anything.
    4796        8556 :   if (!IsNewFormat && !isa<MDString>(BaseNode->getOperand(0))) {
    4797           1 :     CheckFailed("Struct tag nodes have a string as their first operand",
    4798             :                 BaseNode);
    4799           1 :     return InvalidNode;
    4800             :   }
    4801             : 
    4802             :   bool Failed = false;
    4803             : 
    4804             :   Optional<APInt> PrevOffset;
    4805             :   unsigned BitWidth = ~0u;
    4806             : 
    4807             :   // We've already checked that BaseNode is not a degenerate root node with one
    4808             :   // operand in \c verifyTBAABaseNode, so this loop should run at least once.
    4809        4394 :   unsigned FirstFieldOpNo = IsNewFormat ? 3 : 1;
    4810        4394 :   unsigned NumOpsPerField = IsNewFormat ? 3 : 2;
    4811       20878 :   for (unsigned Idx = FirstFieldOpNo; Idx < BaseNode->getNumOperands();
    4812        8242 :            Idx += NumOpsPerField) {
    4813             :     const MDOperand &FieldTy = BaseNode->getOperand(Idx);
    4814        8242 :     const MDOperand &FieldOffset = BaseNode->getOperand(Idx + 1);
    4815           1 :     if (!isa<MDNode>(FieldTy)) {
    4816           1 :       CheckFailed("Incorrect field entry in struct type node!", &I, BaseNode);
    4817             :       Failed = true;
    4818           1 :       continue;
    4819             :     }
    4820             : 
    4821             :     auto *OffsetEntryCI =
    4822             :         mdconst::dyn_extract_or_null<ConstantInt>(FieldOffset);
    4823           0 :     if (!OffsetEntryCI) {
    4824           0 :       CheckFailed("Offset entries must be constants!", &I, BaseNode);
    4825             :       Failed = true;
    4826           0 :       continue;
    4827             :     }
    4828             : 
    4829        8241 :     if (BitWidth == ~0u)
    4830             :       BitWidth = OffsetEntryCI->getBitWidth();
    4831             : 
    4832        8242 :     if (OffsetEntryCI->getBitWidth() != BitWidth) {
    4833           1 :       CheckFailed(
    4834           2 :           "Bitwidth between the offsets and struct type entries must match", &I,
    4835             :           BaseNode);
    4836             :       Failed = true;
    4837           1 :       continue;
    4838             :     }
    4839             : 
    4840             :     // NB! As far as I can tell, we generate a non-strictly increasing offset
    4841             :     // sequence only from structs that have zero size bit fields.  When
    4842             :     // recursing into a contained struct in \c getFieldNodeFromTBAABaseNode we
    4843             :     // pick the field lexically the latest in struct type metadata node.  This
    4844             :     // mirrors the actual behavior of the alias analysis implementation.
    4845             :     bool IsAscending =
    4846       12267 :         !PrevOffset || PrevOffset->ule(OffsetEntryCI->getValue());
    4847             : 
    4848             :     if (!IsAscending) {
    4849           1 :       CheckFailed("Offsets must be increasing!", &I, BaseNode);
    4850             :       Failed = true;
    4851             :     }
    4852             : 
    4853             :     PrevOffset = OffsetEntryCI->getValue();
    4854             : 
    4855        8240 :     if (IsNewFormat) {
    4856         114 :       auto *MemberSizeNode = mdconst::dyn_extract_or_null<ConstantInt>(
    4857             :           BaseNode->getOperand(Idx + 2));
    4858           0 :       if (!MemberSizeNode) {
    4859           0 :         CheckFailed("Member size entries must be constants!", &I, BaseNode);
    4860             :         Failed = true;
    4861           0 :         continue;
    4862             :       }
    4863             :     }
    4864             :   }
    4865             : 
    4866             :   return Failed ? InvalidNode
    4867        4394 :                 : TBAAVerifier::TBAABaseNodeSummary(false, BitWidth);
    4868             : }
    4869             : 
    4870             : static bool IsRootTBAANode(const MDNode *MD) {
    4871       98099 :   return MD->getNumOperands() < 2;
    4872             : }
    4873             : 
    4874        8106 : static bool IsScalarTBAANodeImpl(const MDNode *MD,
    4875             :                                  SmallPtrSetImpl<const MDNode *> &Visited) {
    4876        8106 :   if (MD->getNumOperands() != 2 && MD->getNumOperands() != 3)
    4877             :     return false;
    4878             : 
    4879        7782 :   if (!isa<MDString>(MD->getOperand(0)))
    4880             :     return false;
    4881             : 
    4882        7599 :   if (MD->getNumOperands() == 3) {
    4883             :     auto *Offset = mdconst::dyn_extract<ConstantInt>(MD->getOperand(2));
    4884        6185 :     if (!(Offset && Offset->isZero() && isa<MDString>(MD->getOperand(0))))
    4885             :       return false;
    4886             :   }
    4887             : 
    4888             :   auto *Parent = dyn_cast_or_null<MDNode>(MD->getOperand(1));
    4889       22748 :   return Parent && Visited.insert(Parent).second &&
    4890        2702 :          (IsRootTBAANode(Parent) || IsScalarTBAANodeImpl(Parent, Visited));
    4891             : }
    4892             : 
    4893       91535 : bool TBAAVerifier::isValidScalarTBAANode(const MDNode *MD) {
    4894       91535 :   auto ResultIt = TBAAScalarNodes.find(MD);
    4895       91535 :   if (ResultIt != TBAAScalarNodes.end())
    4896       86131 :     return ResultIt->second;
    4897             : 
    4898             :   SmallPtrSet<const MDNode *, 4> Visited;
    4899        5404 :   bool Result = IsScalarTBAANodeImpl(MD, Visited);
    4900        5404 :   auto InsertResult = TBAAScalarNodes.insert({MD, Result});
    4901             :   (void)InsertResult;
    4902             :   assert(InsertResult.second && "Just checked!");
    4903             : 
    4904             :   return Result;
    4905             : }
    4906             : 
    4907             : /// Returns the field node at the offset \p Offset in \p BaseNode.  Update \p
    4908             : /// Offset in place to be the offset within the field node returned.
    4909             : ///
    4910             : /// We assume we've okayed \p BaseNode via \c verifyTBAABaseNode.
    4911       54777 : MDNode *TBAAVerifier::getFieldNodeFromTBAABaseNode(Instruction &I,
    4912             :                                                    const MDNode *BaseNode,
    4913             :                                                    APInt &Offset,
    4914             :                                                    bool IsNewFormat) {
    4915             :   assert(BaseNode->getNumOperands() >= 2 && "Invalid base node!");
    4916             : 
    4917             :   // Scalar nodes have only one possible "field" -- their parent in the access
    4918             :   // hierarchy.  Offset must be zero at this point, but our caller is supposed
    4919             :   // to Assert that.
    4920       54777 :   if (BaseNode->getNumOperands() == 2)
    4921        5332 :     return cast<MDNode>(BaseNode->getOperand(1));
    4922             : 
    4923       49445 :   unsigned FirstFieldOpNo = IsNewFormat ? 3 : 1;
    4924       49445 :   unsigned NumOpsPerField = IsNewFormat ? 3 : 2;
    4925      159021 :   for (unsigned Idx = FirstFieldOpNo; Idx < BaseNode->getNumOperands();
    4926       54788 :            Idx += NumOpsPerField) {
    4927             :     auto *OffsetEntryCI =
    4928       55551 :         mdconst::extract<ConstantInt>(BaseNode->getOperand(Idx + 1));
    4929       55551 :     if (OffsetEntryCI->getValue().ugt(Offset)) {
    4930         763 :       if (Idx == FirstFieldOpNo) {
    4931           1 :         CheckFailed("Could not find TBAA parent in struct type node", &I,
    4932           2 :                     BaseNode, &Offset);
    4933           1 :         return nullptr;
    4934             :       }
    4935             : 
    4936         762 :       unsigned PrevIdx = Idx - NumOpsPerField;
    4937             :       auto *PrevOffsetEntryCI =
    4938         762 :           mdconst::extract<ConstantInt>(BaseNode->getOperand(PrevIdx + 1));
    4939         762 :       Offset -= PrevOffsetEntryCI->getValue();
    4940        1524 :       return cast<MDNode>(BaseNode->getOperand(PrevIdx));
    4941             :     }
    4942             :   }
    4943             : 
    4944       48682 :   unsigned LastIdx = BaseNode->getNumOperands() - NumOpsPerField;
    4945       48682 :   auto *LastOffsetEntryCI = mdconst::extract<ConstantInt>(
    4946             :       BaseNode->getOperand(LastIdx + 1));
    4947       48682 :   Offset -= LastOffsetEntryCI->getValue();
    4948       97364 :   return cast<MDNode>(BaseNode->getOperand(LastIdx));
    4949             : }
    4950             : 
    4951             : static bool isNewFormatTBAATypeNode(llvm::MDNode *Type) {
    4952       35756 :   if (!Type || Type->getNumOperands() < 3)
    4953             :     return false;
    4954             : 
    4955             :   // In the new format type nodes shall have a reference to the parent type as
    4956             :   // its first operand.
    4957             :   MDNode *Parent = dyn_cast_or_null<MDNode>(Type->getOperand(0));
    4958             :   if (!Parent)
    4959             :     return false;
    4960             : 
    4961             :   return true;
    4962             : }
    4963             : 
    4964       35757 : bool TBAAVerifier::visitTBAAMetadata(Instruction &I, const MDNode *MD) {
    4965       35757 :   AssertTBAA(isa<LoadInst>(I) || isa<StoreInst>(I) || isa<CallInst>(I) ||
    4966             :                  isa<VAArgInst>(I) || isa<AtomicRMWInst>(I) ||
    4967             :                  isa<AtomicCmpXchgInst>(I),
    4968             :              "This instruction shall not have a TBAA access tag!", &I);
    4969             : 
    4970             :   bool IsStructPathTBAA =
    4971       71513 :       isa<MDNode>(MD->getOperand(0)) && MD->getNumOperands() >= 3;
    4972             : 
    4973           1 :   AssertTBAA(
    4974             :       IsStructPathTBAA,
    4975             :       "Old-style TBAA is no longer allowed, use struct-path TBAA instead", &I);
    4976             : 
    4977       35756 :   MDNode *BaseNode = dyn_cast_or_null<MDNode>(MD->getOperand(0));
    4978       35756 :   MDNode *AccessType = dyn_cast_or_null<MDNode>(MD->getOperand(1));
    4979             : 
    4980             :   bool IsNewFormat = isNewFormatTBAATypeNode(AccessType);
    4981             : 
    4982             :   if (IsNewFormat) {
    4983         611 :     AssertTBAA(MD->getNumOperands() == 4 || MD->getNumOperands() == 5,
    4984             :                "Access tag metadata must have either 4 or 5 operands", &I, MD);
    4985             :   } else {
    4986       35145 :     AssertTBAA(MD->getNumOperands() < 5,
    4987             :                "Struct tag metadata must have either 3 or 4 operands", &I, MD);
    4988             :   }
    4989             : 
    4990             :   // Check the access size field.
    4991       35752 :   if (IsNewFormat) {
    4992             :     auto *AccessSizeNode = mdconst::dyn_extract_or_null<ConstantInt>(
    4993             :         MD->getOperand(3));
    4994           0 :     AssertTBAA(AccessSizeNode, "Access size field must be a constant", &I, MD);
    4995             :   }
    4996             : 
    4997             :   // Check the immutability flag.
    4998       35752 :   unsigned ImmutabilityFlagOpNo = IsNewFormat ? 4 : 3;
    4999       35752 :   if (MD->getNumOperands() == ImmutabilityFlagOpNo + 1) {
    5000             :     auto *IsImmutableCI = mdconst::dyn_extract_or_null<ConstantInt>(
    5001             :         MD->getOperand(ImmutabilityFlagOpNo));
    5002           1 :     AssertTBAA(IsImmutableCI,
    5003             :                "Immutability tag on struct tag metadata must be a constant",
    5004             :                &I, MD);
    5005         850 :     AssertTBAA(
    5006             :         IsImmutableCI->isZero() || IsImmutableCI->isOne(),
    5007             :         "Immutability part of the struct tag metadata must be either 0 or 1",
    5008             :         &I, MD);
    5009             :   }
    5010             : 
    5011       35750 :   AssertTBAA(BaseNode && AccessType,
    5012             :              "Malformed struct tag metadata: base and access-type "
    5013             :              "should be non-null and point to Metadata nodes",
    5014             :              &I, MD, BaseNode, AccessType);
    5015             : 
    5016       35749 :   if (!IsNewFormat) {
    5017       35140 :     AssertTBAA(isValidScalarTBAANode(AccessType),
    5018             :                "Access type node must be a valid scalar type", &I, MD,
    5019             :                AccessType);
    5020             :   }
    5021             : 
    5022       35742 :   auto *OffsetCI = mdconst::dyn_extract_or_null<ConstantInt>(MD->getOperand(2));
    5023           1 :   AssertTBAA(OffsetCI, "Offset must be constant integer", &I, MD);
    5024             : 
    5025             :   APInt Offset = OffsetCI->getValue();
    5026             :   bool SeenAccessTypeInPath = false;
    5027             : 
    5028             :   SmallPtrSet<MDNode *, 4> StructPath;
    5029             : 
    5030      235812 :   for (/* empty */; BaseNode && !IsRootTBAANode(BaseNode);
    5031       54777 :        BaseNode = getFieldNodeFromTBAABaseNode(I, BaseNode, Offset,
    5032             :                                                IsNewFormat)) {
    5033       55395 :     if (!StructPath.insert(BaseNode).second) {
    5034           1 :       CheckFailed("Cycle detected in struct path", &I, MD);
    5035          10 :       return false;
    5036             :     }
    5037             : 
    5038             :     bool Invalid;
    5039             :     unsigned BaseNodeBitWidth;
    5040      110788 :     std::tie(Invalid, BaseNodeBitWidth) = verifyTBAABaseNode(I, BaseNode,
    5041       55394 :                                                              IsNewFormat);
    5042             : 
    5043             :     // If the base node is invalid in itself, then we've already printed all the
    5044             :     // errors we wanted to print.
    5045       55394 :     if (Invalid)
    5046             :       return false;
    5047             : 
    5048       55389 :     SeenAccessTypeInPath |= BaseNode == AccessType;
    5049             : 
    5050       55389 :     if (isValidScalarTBAANode(BaseNode) || BaseNode == AccessType)
    5051       54370 :       AssertTBAA(Offset == 0, "Offset not zero at the point of scalar access",
    5052             :                  &I, MD, &Offset);
    5053             : 
    5054       55388 :     AssertTBAA(BaseNodeBitWidth == Offset.getBitWidth() ||
    5055             :                    (BaseNodeBitWidth == 0 && Offset == 0) ||
    5056             :                    (IsNewFormat && BaseNodeBitWidth == ~0u),
    5057             :                "Access bit-width not the same as description bit-width", &I, MD,
    5058             :                BaseNodeBitWidth, Offset.getBitWidth());
    5059             : 
    5060       55386 :     if (IsNewFormat && SeenAccessTypeInPath)
    5061             :       break;
    5062             :   }
    5063             : 
    5064       35732 :   AssertTBAA(SeenAccessTypeInPath, "Did not see access type in access path!",
    5065             :              &I, MD);
    5066             :   return true;
    5067             : }
    5068             : 
    5069             : char VerifierLegacyPass::ID = 0;
    5070      256020 : INITIALIZE_PASS(VerifierLegacyPass, "verify", "Module Verifier", false, false)
    5071             : 
    5072       57869 : FunctionPass *llvm::createVerifierPass(bool FatalErrors) {
    5073      115738 :   return new VerifierLegacyPass(FatalErrors);
    5074             : }
    5075             : 
    5076             : AnalysisKey VerifierAnalysis::Key;
    5077        1383 : VerifierAnalysis::Result VerifierAnalysis::run(Module &M,
    5078             :                                                ModuleAnalysisManager &) {
    5079             :   Result Res;
    5080        1383 :   Res.IRBroken = llvm::verifyModule(M, &dbgs(), &Res.DebugInfoBroken);
    5081        1383 :   return Res;
    5082             : }
    5083             : 
    5084           9 : VerifierAnalysis::Result VerifierAnalysis::run(Function &F,
    5085             :                                                FunctionAnalysisManager &) {
    5086           9 :   return { llvm::verifyFunction(F, &dbgs()), false };
    5087             : }
    5088             : 
    5089        1624 : PreservedAnalyses VerifierPass::run(Module &M, ModuleAnalysisManager &AM) {
    5090        1624 :   auto Res = AM.getResult<VerifierAnalysis>(M);
    5091        1624 :   if (FatalErrors && (Res.IRBroken || Res.DebugInfoBroken))
    5092           0 :     report_fatal_error("Broken module found, compilation aborted!");
    5093             : 
    5094        1624 :   return PreservedAnalyses::all();
    5095             : }
    5096             : 
    5097          10 : PreservedAnalyses VerifierPass::run(Function &F, FunctionAnalysisManager &AM) {
    5098          10 :   auto res = AM.getResult<VerifierAnalysis>(F);
    5099          10 :   if (res.IRBroken && FatalErrors)
    5100           0 :     report_fatal_error("Broken function found, compilation aborted!");
    5101             : 
    5102          10 :   return PreservedAnalyses::all();
    5103             : }

Generated by: LCOV version 1.13