LCOV - code coverage report
Current view: top level - lib/IR - Verifier.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 1768 1845 95.8 %
Date: 2018-06-17 00:07:59 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       95615 : 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       95879 :   explicit VerifierSupport(raw_ostream *OS, const Module &M)
     135       95879 :       : 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         400 :   void Write(const Value *V) {
     143         400 :     if (!V)
     144             :       return;
     145         398 :     if (isa<Instruction>(V)) {
     146         267 :       V->print(*OS, MST);
     147         267 :       *OS << '\n';
     148             :     } else {
     149         131 :       V->printAsOperand(*OS, true, MST);
     150         131 :       *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         571 :     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         361 :   void CheckFailed(const Twine &Message) {
     215         361 :     if (OS)
     216             :       *OS << Message << '\n';
     217         361 :     Broken = true;
     218         361 :   }
     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         341 :   void CheckFailed(const Twine &Message, const T1 &V1, const Ts &... Vs) {
     226         341 :     CheckFailed(Message);
     227         341 :     if (OS)
     228         321 :       WriteTs(V1, Vs...);
     229         341 :   }
     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      286845 : 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       95879 :   explicit Verifier(raw_ostream *OS, bool ShouldTreatBrokenDebugInfoAsError,
     313             :                     const Module &M)
     314       95879 :       : VerifierSupport(OS, M), LandingPadResultTy(nullptr),
     315      287637 :         SawFrameEscape(false), TBAAVerifyHelper(this) {
     316       95879 :     TreatBrokenDebugInfoAsError = ShouldTreatBrokenDebugInfoAsError;
     317       95879 :   }
     318             : 
     319             :   bool hasBrokenDebugInfo() const { return BrokenDebugInfo; }
     320             : 
     321     1045202 :   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     1045202 :     if (!F.empty())
     332      769284 :       DT.recalculate(const_cast<Function &>(F));
     333             : 
     334     2172186 :     for (const BasicBlock &BB : F) {
     335     2253972 :       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     1045199 :     Broken = false;
     348             :     // FIXME: We strip const here because the inst visitor strips const.
     349     1045199 :     visit(const_cast<Function &>(F));
     350     1045199 :     verifySiblingFuncletUnwinds();
     351     1045199 :     InstsInThisBlock.clear();
     352             :     DebugFnArgs.clear();
     353     1045199 :     LandingPadResultTy = nullptr;
     354     1045199 :     SawFrameEscape = false;
     355             :     SiblingFuncletInfo.clear();
     356             : 
     357     1045199 :     return !Broken;
     358             :   }
     359             : 
     360             :   /// Verify the module that this instance of \c Verifier was initialized with.
     361       94959 :   bool verify() {
     362       94959 :     Broken = false;
     363             : 
     364             :     // Collect all declarations of the llvm.experimental.deoptimize intrinsic.
     365     1234413 :     for (const Function &F : M)
     366     1044495 :       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       94959 :     verifyFrameRecoverIndices();
     372      344276 :     for (const GlobalVariable &GV : M.globals())
     373      154358 :       visitGlobalVariable(GV);
     374             : 
     375      192862 :     for (const GlobalAlias &GA : M.aliases())
     376        2944 :       visitGlobalAlias(GA);
     377             : 
     378      228798 :     for (const NamedMDNode &NMD : M.named_metadata())
     379       38880 :       visitNamedMDNode(NMD);
     380             : 
     381      217127 :     for (const StringMapEntry<Comdat> &SMEC : M.getComdatSymbolTable())
     382       27209 :       visitComdat(SMEC.getValue());
     383             : 
     384       94959 :     visitModuleFlags(M);
     385       94959 :     visitModuleIdents(M);
     386             : 
     387       94959 :     verifyCompileUnits();
     388             : 
     389       94959 :     verifyDeoptimizeCallingConvs();
     390       94959 :     DISubprogramAttachments.clear();
     391       94959 :     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         626 :   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     5804098 : void Verifier::visit(Instruction &I) {
     534    25542660 :   for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i)
     535    19738562 :     Assert(I.getOperand(i) != nullptr, "Operand is null", &I);
     536     5804098 :   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     1460803 : static void forEachUser(const Value *User,
     543             :                         SmallPtrSet<const Value *, 32> &Visited,
     544             :                         llvm::function_ref<bool(const Value *)> Callback) {
     545     1460803 :   if (!Visited.insert(User).second)
     546             :     return;
     547     2465944 :   for (const Value *TheNextUser : User->materialized_users())
     548     1083782 :     if (Callback(TheNextUser))
     549      258316 :       forEachUser(TheNextUser, Visited, Callback);
     550             : }
     551             : 
     552     1202493 : void Verifier::visitGlobalValue(const GlobalValue &GV) {
     553     1202497 :   Assert(!GV.isDeclaration() || GV.hasValidDeclarationLinkage(),
     554             :          "Global is external, but doesn't have external or weak linkage!", &GV);
     555             : 
     556     1202491 :   Assert(GV.getAlignment() <= Value::MaximumAlignment,
     557             :          "huge alignment values are unsupported", &GV);
     558     1206245 :   Assert(!GV.hasAppendingLinkage() || isa<GlobalVariable>(GV),
     559             :          "Only global variables can have appending linkage!", &GV);
     560             : 
     561     1202491 :   if (GV.hasAppendingLinkage()) {
     562        3754 :     const GlobalVariable *GVar = dyn_cast<GlobalVariable>(&GV);
     563        7509 :     Assert(GVar && GVar->getValueType()->isArrayTy(),
     564             :            "Only global arrays can have appending linkage!", GVar);
     565             :   }
     566             : 
     567     1201602 :   if (GV.isDeclarationForLinker())
     568      305301 :     Assert(!GV.hasComdat(), "Declaration may not be in a Comdat!", &GV);
     569             : 
     570     1202488 :   if (GV.hasDLLImportStorageClass()) {
     571        1806 :     Assert(!GV.isDSOLocal(),
     572             :            "GlobalValue with DLLImport Storage is dso_local!", &GV);
     573             : 
     574        3612 :     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       95161 :     Assert(GV.isDSOLocal(),
     581             :            "GlobalValue with private or internal linkage must be dso_local!",
     582             :            &GV);
     583             : 
     584     1202487 :   if (!GV.hasDefaultVisibility() && !GV.hasExternalWeakLinkage())
     585        7855 :     Assert(GV.isDSOLocal(),
     586             :            "GlobalValue with non default visibility must be dso_local!", &GV);
     587             : 
     588     3488756 :   forEachUser(&GV, GlobalValueVisited, [&](const Value *V) -> bool {
     589     1083782 :     if (const Instruction *I = dyn_cast<Instruction>(V)) {
     590      821767 :       if (!I->getParent() || !I->getParent()->getParent())
     591      825468 :         CheckFailed("Global is referenced by parentless instruction!", &GV, &M,
     592             :                     I);
     593     1643534 :       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      825466 :       return false;
     598      262015 :     } else if (const Function *F = dyn_cast<Function>(V)) {
     599        7398 :       if (F->getParent() != &M)
     600           4 :         CheckFailed("Global is used by function in a different module", &GV, &M,
     601           2 :                     F, F->getParent());
     602        3699 :       return false;
     603             :     }
     604      258316 :     return true;
     605             :   });
     606             : }
     607             : 
     608      154358 : void Verifier::visitGlobalVariable(const GlobalVariable &GV) {
     609      154358 :   if (GV.hasInitializer()) {
     610      154366 :     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      125645 :     if (GV.hasCommonLinkage()) {
     617       15150 :       Assert(GV.getInitializer()->isNullValue(),
     618             :              "'common' global must have a zero initializer!", &GV);
     619       15150 :       Assert(!GV.isConstant(), "'common' global may not be marked constant!",
     620             :              &GV);
     621       15151 :       Assert(!GV.hasComdat(), "'common' global may not be in a Comdat!", &GV);
     622             :     }
     623             :   }
     624             : 
     625      154357 :   if (GV.hasName() && (GV.getName() == "llvm.global_ctors" ||
     626      145079 :                        GV.getName() == "llvm.global_dtors")) {
     627        5063 :     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        2533 :     if (ArrayType *ATy = dyn_cast<ArrayType>(GV.getValueType())) {
     632        2533 :       StructType *STy = dyn_cast<StructType>(ATy->getElementType());
     633             :       PointerType *FuncPtrTy =
     634        2533 :           FunctionType::get(Type::getVoidTy(Context), false)->getPointerTo();
     635             :       // FIXME: Reject the 2-field form in LLVM 4.0.
     636        2535 :       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        2532 :       if (STy->getNumElements() == 3) {
     642        2318 :         Type *ETy = STy->getTypeAtIndex(2);
     643        2319 :         Assert(ETy->isPointerTy() &&
     644             :                    cast<PointerType>(ETy)->getElementType()->isIntegerTy(8),
     645             :                "wrong type for intrinsic global variable", &GV);
     646             :       }
     647             :     }
     648             :   }
     649             : 
     650      154355 :   if (GV.hasName() && (GV.getName() == "llvm.used" ||
     651      147022 :                        GV.getName() == "llvm.compiler.used")) {
     652        2379 :     Assert(!GV.hasInitializer() || GV.hasAppendingLinkage(),
     653             :            "invalid linkage for intrinsic global variable", &GV);
     654        1191 :     Type *GVType = GV.getValueType();
     655             :     if (ArrayType *ATy = dyn_cast<ArrayType>(GVType)) {
     656        1190 :       PointerType *PTy = dyn_cast<PointerType>(ATy->getElementType());
     657           4 :       Assert(PTy, "wrong type for intrinsic global variable", &GV);
     658        1188 :       if (GV.hasInitializer()) {
     659        1185 :         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       20670 :         for (Value *Op : InitArray->operands()) {
     664        9152 :           Value *V = Op->stripPointerCastsNoFollowAliases();
     665        9155 :           Assert(isa<GlobalVariable>(V) || isa<Function>(V) ||
     666             :                      isa<GlobalAlias>(V),
     667             :                  "invalid llvm.used member", V);
     668        9151 :           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      154351 :   GV.getMetadata(LLVMContext::MD_dbg, MDs);
     677      161135 :   for (auto *MD : MDs) {
     678             :     if (auto *GVE = dyn_cast<DIGlobalVariableExpression>(MD))
     679        3392 :       visitDIGlobalVariableExpression(*GVE);
     680             :     else
     681           2 :       AssertDI(false, "!dbg attachment of global variable must be a "
     682             :                       "DIGlobalVariableExpression");
     683             :   }
     684             : 
     685      154350 :   if (!GV.hasInitializer()) {
     686       28713 :     visitGlobalValue(GV);
     687       28713 :     return;
     688             :   }
     689             : 
     690             :   // Walk any aggregate initializers looking for bitcasts between address spaces
     691      125637 :   visitConstantExprsRecursively(GV.getInitializer());
     692             : 
     693      125637 :   visitGlobalValue(GV);
     694             : }
     695             : 
     696        2944 : void Verifier::visitAliaseeSubExpr(const GlobalAlias &GA, const Constant &C) {
     697             :   SmallPtrSet<const GlobalAlias*, 4> Visited;
     698        2944 :   Visited.insert(&GA);
     699        2944 :   visitAliaseeSubExpr(Visited, GA, C);
     700        2944 : }
     701             : 
     702        6046 : void Verifier::visitAliaseeSubExpr(SmallPtrSetImpl<const GlobalAlias*> &Visited,
     703             :                                    const GlobalAlias &GA, const Constant &C) {
     704             :   if (const auto *GV = dyn_cast<GlobalValue>(&C)) {
     705        2979 :     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        1443 :     visitConstantExprsRecursively(CE);
     722             : 
     723       12472 :   for (const Use &U : C.operands()) {
     724        3102 :     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        3030 :       visitAliaseeSubExpr(Visited, GA, *C2);
     729             :   }
     730             : }
     731             : 
     732        2944 : 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        2944 :   Assert(GA.getType() == Aliasee->getType(),
     740             :          "Alias and aliasee types should match!", &GA);
     741             : 
     742        1307 :   Assert(isa<GlobalValue>(Aliasee) || isa<ConstantExpr>(Aliasee),
     743             :          "Aliasee should be either GlobalValue or ConstantExpr", &GA);
     744             : 
     745        2944 :   visitAliaseeSubExpr(GA, *Aliasee);
     746             : 
     747        2944 :   visitGlobalValue(GA);
     748             : }
     749             : 
     750       38880 : 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       70829 :   if (NMD.getName().startswith("llvm.dbg."))
     754        6933 :     AssertDI(NMD.getName() == "llvm.dbg.cu",
     755             :              "unrecognized named metadata node in the llvm.dbg namespace",
     756             :              &NMD);
     757      166774 :   for (const MDNode *MD : NMD.operands()) {
     758       63951 :     if (NMD.getName() == "llvm.dbg.cu")
     759       17051 :       AssertDI(MD && isa<DICompileUnit>(MD), "invalid compile unit", &NMD, MD);
     760             : 
     761       63944 :     if (!MD)
     762           0 :       continue;
     763             : 
     764       63944 :     visitMDNode(*MD);
     765             :   }
     766             : }
     767             : 
     768      514360 : 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      514360 :   if (!MDNodes.insert(&MD).second)
     772             :     return;
     773             : 
     774      502622 :   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     2673637 :   for (const Metadata *Op : MD.operands()) {
     787      807442 :     if (!Op)
     788      215411 :       continue;
     789      592031 :     Assert(!isa<LocalAsMetadata>(Op), "Invalid operand for global metadata!",
     790             :            &MD, Op);
     791      310420 :     if (auto *N = dyn_cast<MDNode>(Op)) {
     792      310420 :       visitMDNode(*N);
     793      310420 :       continue;
     794             :     }
     795      106501 :     if (auto *V = dyn_cast<ValueAsMetadata>(Op)) {
     796      106501 :       visitValueAsMetadata(*V, nullptr);
     797      106501 :       continue;
     798             :     }
     799             :   }
     800             : 
     801             :   // Check these last, so we diagnose problems in operands first.
     802      251311 :   Assert(!MD.isTemporary(), "Expected no forward declarations!", &MD);
     803           0 :   Assert(MD.isResolved(), "All nodes should be resolved!", &MD);
     804             : }
     805             : 
     806      119368 : void Verifier::visitValueAsMetadata(const ValueAsMetadata &MD, Function *F) {
     807      226831 :   Assert(MD.getValue(), "Expected valid value", &MD);
     808      238736 :   Assert(!MD.getValue()->getType()->isMetadataTy(),
     809             :          "Unexpected metadata round-trip through values", &MD, MD.getValue());
     810             : 
     811      119368 :   auto *L = dyn_cast<LocalAsMetadata>(&MD);
     812      119368 :   if (!L)
     813             :     return;
     814             : 
     815       11905 :   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       23810 :   if (Instruction *I = dyn_cast<Instruction>(L->getValue())) {
     821       10149 :     Assert(I->getParent(), "function-local metadata not in basic block", L, I);
     822       10149 :     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       11905 :   Assert(ActualF == F, "function-local metadata used in wrong function", L);
     830             : }
     831             : 
     832       44742 : void Verifier::visitMetadataAsValue(const MetadataAsValue &MDV, Function *F) {
     833       44742 :   Metadata *MD = MDV.getMetadata();
     834             :   if (auto *N = dyn_cast<MDNode>(MD)) {
     835       29767 :     visitMDNode(*N);
     836       29767 :     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       14975 :   if (!MDNodes.insert(MD).second)
     842             :     return;
     843             : 
     844             :   if (auto *V = dyn_cast<ValueAsMetadata>(MD))
     845       12867 :     visitValueAsMetadata(*V, F);
     846             : }
     847             : 
     848       63862 : static bool isType(const Metadata *MD) { return !MD || isa<DIType>(MD); }
     849       32140 : 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       40324 : void Verifier::visitDILocation(const DILocation &N) {
     853       40324 :   AssertDI(N.getRawScope() && isa<DILocalScope>(N.getRawScope()),
     854             :            "location requires a valid scope", &N, N.getRawScope());
     855       40324 :   if (auto *IA = N.getRawInlinedAt())
     856        2023 :     AssertDI(isa<DILocation>(IA), "inlined-at should be a location", &N, IA);
     857             :   if (auto *SP = dyn_cast<DISubprogram>(N.getRawScope()))
     858       29240 :     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       18346 : void Verifier::visitDIScope(const DIScope &N) {
     866       18346 :   if (auto *F = N.getRawFile())
     867       11155 :     AssertDI(isa<DIFile>(F), "invalid file", &N, F);
     868             : }
     869             : 
     870         761 : void Verifier::visitDISubrange(const DISubrange &N) {
     871         761 :   AssertDI(N.getTag() == dwarf::DW_TAG_subrange_type, "invalid tag", &N);
     872         761 :   auto Count = N.getCount();
     873         762 :   AssertDI(Count, "Count must either be a signed constant or a DIVariable",
     874             :            &N);
     875        1454 :   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        6392 : void Verifier::visitDIBasicType(const DIBasicType &N) {
     885       12784 :   AssertDI(N.getTag() == dwarf::DW_TAG_base_type ||
     886             :                N.getTag() == dwarf::DW_TAG_unspecified_type,
     887             :            "invalid tag", &N);
     888             : }
     889             : 
     890       12536 : void Verifier::visitDIDerivedType(const DIDerivedType &N) {
     891             :   // Common scope checks.
     892       12536 :   visitDIScope(N);
     893             : 
     894       25072 :   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       12536 :   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       12532 :   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       28099 :   return ((Flags & DINode::FlagLValueReference) &&
     927       56198 :           (Flags & DINode::FlagRValueReference)) ||
     928       28099 :          ((Flags & DINode::FlagTypePassByValue) &&
     929             :           (Flags & DINode::FlagTypePassByReference));
     930             : }
     931             : 
     932        1078 : void Verifier::visitTemplateParams(const MDNode &N, const Metadata &RawParams) {
     933        1078 :   auto *Params = dyn_cast<MDTuple>(&RawParams);
     934        1081 :   AssertDI(Params, "invalid template params", &N, &RawParams);
     935        5374 :   for (Metadata *Op : Params->operands()) {
     936        1076 :     AssertDI(Op && isa<DITemplateParameter>(Op), "invalid template parameter",
     937             :              &N, Params, Op);
     938             :   }
     939             : }
     940             : 
     941        5810 : void Verifier::visitDICompositeType(const DICompositeType &N) {
     942             :   // Common scope checks.
     943        5810 :   visitDIScope(N);
     944             : 
     945       11620 :   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       10617 :   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        5812 :   AssertDI(!hasConflictingReferenceFlags(N.getFlags()),
     962             :            "invalid reference flags", &N);
     963             : 
     964        5809 :   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        5808 :   if (auto *Params = N.getRawTemplateParams())
     972         502 :     visitTemplateParams(N, *Params);
     973             : 
     974       11616 :   if (N.getTag() == dwarf::DW_TAG_class_type ||
     975             :       N.getTag() == dwarf::DW_TAG_union_type) {
     976        1060 :     AssertDI(N.getFile() && !N.getFile()->getFilename().empty(),
     977             :              "class/union requires a filename", &N, N.getFile());
     978             :   }
     979             : 
     980        5808 :   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        8501 : void Verifier::visitDISubroutineType(const DISubroutineType &N) {
     987        8501 :   AssertDI(N.getTag() == dwarf::DW_TAG_subroutine_type, "invalid tag", &N);
     988        8501 :   if (auto *Types = N.getRawTypeArray()) {
     989        8430 :     AssertDI(isa<MDTuple>(Types), "invalid composite elements", &N, Types);
     990       60813 :     for (Metadata *Ty : N.getTypeArray()->operands()) {
     991           0 :       AssertDI(isType(Ty), "invalid subroutine type ref", &N, Types, Ty);
     992             :     }
     993             :   }
     994        8501 :   AssertDI(!hasConflictingReferenceFlags(N.getFlags()),
     995             :            "invalid reference flags", &N);
     996             : }
     997             : 
     998        9519 : void Verifier::visitDIFile(const DIFile &N) {
     999        9521 :   AssertDI(N.getTag() == dwarf::DW_TAG_file_type, "invalid tag", &N);
    1000             :   Optional<DIFile::ChecksumInfo<StringRef>> Checksum = N.getChecksum();
    1001        9519 :   if (Checksum) {
    1002         569 :     AssertDI(Checksum->Kind <= DIFile::ChecksumKind::CSK_Last,
    1003             :              "invalid checksum kind", &N);
    1004             :     size_t Size;
    1005         569 :     switch (Checksum->Kind) {
    1006         546 :     case DIFile::CSK_MD5:
    1007             :       Size = 32;
    1008         546 :       break;
    1009          23 :     case DIFile::CSK_SHA1:
    1010             :       Size = 40;
    1011          23 :       break;
    1012             :     }
    1013         570 :     AssertDI(Checksum->Value.size() == Size, "invalid checksum length", &N);
    1014         569 :     AssertDI(Checksum->Value.find_if_not(llvm::isHexDigit) == StringRef::npos,
    1015             :              "invalid checksum", &N);
    1016             :   }
    1017             : }
    1018             : 
    1019        8577 : void Verifier::visitDICompileUnit(const DICompileUnit &N) {
    1020        8577 :   AssertDI(N.isDistinct(), "compile units must be distinct", &N);
    1021        8577 :   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       17154 :   AssertDI(N.getRawFile() && isa<DIFile>(N.getRawFile()), "invalid file", &N,
    1026             :            N.getRawFile());
    1027        8577 :   AssertDI(!N.getFile()->getFilename().empty(), "invalid filename", &N,
    1028             :            N.getFile());
    1029             : 
    1030        8577 :   AssertDI((N.getEmissionKind() <= DICompileUnit::LastEmissionKind),
    1031             :            "invalid emission kind", &N);
    1032             : 
    1033        8577 :   if (auto *Array = N.getRawEnumTypes()) {
    1034        7037 :     AssertDI(isa<MDTuple>(Array), "invalid enum list", &N, Array);
    1035       15358 :     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        8577 :   if (auto *Array = N.getRawRetainedTypes()) {
    1042        3097 :     AssertDI(isa<MDTuple>(Array), "invalid retained type list", &N, Array);
    1043       12886 :     for (Metadata *Op : N.getRetainedTypes()->operands()) {
    1044        2427 :       AssertDI(Op && (isa<DIType>(Op) ||
    1045             :                       (isa<DISubprogram>(Op) &&
    1046             :                        !cast<DISubprogram>(Op)->isDefinition())),
    1047             :                "invalid retained type", &N, Op);
    1048             :     }
    1049             :   }
    1050        8575 :   if (auto *Array = N.getRawGlobalVariables()) {
    1051        4111 :     AssertDI(isa<MDTuple>(Array), "invalid global variable list", &N, Array);
    1052       20317 :     for (Metadata *Op : N.getGlobalVariables()->operands()) {
    1053        8068 :       AssertDI(Op && (isa<DIGlobalVariableExpression>(Op)),
    1054             :                "invalid global variable ref", &N, Op);
    1055             :     }
    1056             :   }
    1057        8574 :   if (auto *Array = N.getRawImportedEntities()) {
    1058        2094 :     AssertDI(isa<MDTuple>(Array), "invalid imported entity list", &N, Array);
    1059        7299 :     for (Metadata *Op : N.getImportedEntities()->operands()) {
    1060        2074 :       AssertDI(Op && isa<DIImportedEntity>(Op), "invalid imported entity ref",
    1061             :                &N, Op);
    1062             :     }
    1063             :   }
    1064        8574 :   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        8574 :   CUVisited.insert(&N);
    1071             : }
    1072             : 
    1073       13794 : void Verifier::visitDISubprogram(const DISubprogram &N) {
    1074       13813 :   AssertDI(N.getTag() == dwarf::DW_TAG_subprogram, "invalid tag", &N);
    1075           0 :   AssertDI(isScope(N.getRawScope()), "invalid scope", &N, N.getRawScope());
    1076       13794 :   if (auto *F = N.getRawFile())
    1077       13118 :     AssertDI(isa<DIFile>(F), "invalid file", &N, F);
    1078             :   else
    1079         684 :     AssertDI(N.getLine() == 0, "line specified with no file", &N, N.getLine());
    1080       13790 :   if (auto *T = N.getRawType())
    1081       13142 :     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       13788 :   if (auto *S = N.getRawDeclaration())
    1087        3098 :     AssertDI(isa<DISubprogram>(S) && !cast<DISubprogram>(S)->isDefinition(),
    1088             :              "invalid subprogram declaration", &N, S);
    1089       13788 :   if (auto *RawNode = N.getRawRetainedNodes()) {
    1090        9382 :     auto *Node = dyn_cast<MDTuple>(RawNode);
    1091        9382 :     AssertDI(Node, "invalid retained nodes list", &N, RawNode);
    1092       32252 :     for (Metadata *Op : Node->operands()) {
    1093        8992 :       AssertDI(Op && (isa<DILocalVariable>(Op) || isa<DILabel>(Op)),
    1094             :                "invalid retained nodes, expected DILocalVariable or DILabel",
    1095             :                &N, Node, Op);
    1096             :     }
    1097             :   }
    1098       13788 :   AssertDI(!hasConflictingReferenceFlags(N.getFlags()),
    1099             :            "invalid reference flags", &N);
    1100             : 
    1101       13788 :   auto *Unit = N.getRawUnit();
    1102       13788 :   if (N.isDefinition()) {
    1103             :     // Subprogram definitions (not part of the type hierarchy).
    1104       10631 :     AssertDI(N.isDistinct(), "subprogram definitions must be distinct", &N);
    1105       10643 :     AssertDI(Unit, "subprogram definitions must have a compile unit", &N);
    1106       10619 :     AssertDI(isa<DICompileUnit>(Unit), "invalid unit type", &N, Unit);
    1107             :   } else {
    1108             :     // Subprogram declarations (part of the type hierarchy).
    1109        3157 :     AssertDI(!Unit, "subprogram declarations must not have a compile unit", &N);
    1110             :   }
    1111             : 
    1112       13776 :   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        5331 : void Verifier::visitDILexicalBlockBase(const DILexicalBlockBase &N) {
    1122        5331 :   AssertDI(N.getTag() == dwarf::DW_TAG_lexical_block, "invalid tag", &N);
    1123        5331 :   AssertDI(N.getRawScope() && isa<DILocalScope>(N.getRawScope()),
    1124             :            "invalid local scope", &N, N.getRawScope());
    1125             :   if (auto *SP = dyn_cast<DISubprogram>(N.getRawScope()))
    1126        2859 :     AssertDI(SP->isDefinition(), "scope points into the type hierarchy", &N);
    1127             : }
    1128             : 
    1129        4296 : void Verifier::visitDILexicalBlock(const DILexicalBlock &N) {
    1130        4296 :   visitDILexicalBlockBase(N);
    1131             : 
    1132        4296 :   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         518 : void Verifier::visitDINamespace(const DINamespace &N) {
    1141         518 :   AssertDI(N.getTag() == dwarf::DW_TAG_namespace, "invalid tag", &N);
    1142         518 :   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         429 : void Verifier::visitDIModule(const DIModule &N) {
    1171         429 :   AssertDI(N.getTag() == dwarf::DW_TAG_module, "invalid tag", &N);
    1172         429 :   AssertDI(!N.getName().empty(), "anonymous module", &N);
    1173             : }
    1174             : 
    1175         856 : void Verifier::visitDITemplateParameter(const DITemplateParameter &N) {
    1176           0 :   AssertDI(isType(N.getRawType()), "invalid type ref", &N, N.getRawType());
    1177             : }
    1178             : 
    1179         415 : void Verifier::visitDITemplateTypeParameter(const DITemplateTypeParameter &N) {
    1180         415 :   visitDITemplateParameter(N);
    1181             : 
    1182         415 :   AssertDI(N.getTag() == dwarf::DW_TAG_template_type_parameter, "invalid tag",
    1183             :            &N);
    1184             : }
    1185             : 
    1186         441 : void Verifier::visitDITemplateValueParameter(
    1187             :     const DITemplateValueParameter &N) {
    1188         441 :   visitDITemplateParameter(N);
    1189             : 
    1190         882 :   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       24046 : void Verifier::visitDIVariable(const DIVariable &N) {
    1197       24046 :   if (auto *S = N.getRawScope())
    1198           0 :     AssertDI(isa<DIScope>(S), "invalid scope", &N, S);
    1199       24046 :   if (auto *F = N.getRawFile())
    1200       21151 :     AssertDI(isa<DIFile>(F), "invalid file", &N, F);
    1201             : }
    1202             : 
    1203       11512 : void Verifier::visitDIGlobalVariable(const DIGlobalVariable &N) {
    1204             :   // Checks common to all variables.
    1205       11512 :   visitDIVariable(N);
    1206             : 
    1207       11512 :   AssertDI(N.getTag() == dwarf::DW_TAG_variable, "invalid tag", &N);
    1208       11512 :   AssertDI(!N.getName().empty(), "missing global variable name", &N);
    1209          12 :   AssertDI(isType(N.getRawType()), "invalid type ref", &N, N.getRawType());
    1210       11508 :   AssertDI(N.getType(), "missing global variable type", &N);
    1211       11504 :   if (auto *Member = N.getRawStaticDataMemberDeclaration()) {
    1212         324 :     AssertDI(isa<DIDerivedType>(Member),
    1213             :              "invalid static data member declaration", &N, Member);
    1214             :   }
    1215             : }
    1216             : 
    1217       12534 : void Verifier::visitDILocalVariable(const DILocalVariable &N) {
    1218             :   // Checks common to all variables.
    1219       12534 :   visitDIVariable(N);
    1220             : 
    1221           0 :   AssertDI(isType(N.getRawType()), "invalid type ref", &N, N.getRawType());
    1222       12534 :   AssertDI(N.getTag() == dwarf::DW_TAG_variable, "invalid tag", &N);
    1223       12534 :   AssertDI(N.getRawScope() && isa<DILocalScope>(N.getRawScope()),
    1224             :            "local variable requires a valid scope", &N, N.getRawScope());
    1225             : }
    1226             : 
    1227          54 : void Verifier::visitDILabel(const DILabel &N) {
    1228          54 :   if (auto *S = N.getRawScope())
    1229           0 :     AssertDI(isa<DIScope>(S), "invalid scope", &N, S);
    1230          54 :   if (auto *F = N.getRawFile())
    1231          54 :     AssertDI(isa<DIFile>(F), "invalid file", &N, F);
    1232             : 
    1233          54 :   AssertDI(N.getTag() == dwarf::DW_TAG_label, "invalid tag", &N);
    1234          54 :   AssertDI(N.getRawScope() && isa<DILocalScope>(N.getRawScope()),
    1235             :            "label requires a valid scope", &N, N.getRawScope());
    1236             : }
    1237             : 
    1238       11925 : void Verifier::visitDIExpression(const DIExpression &N) {
    1239       11928 :   AssertDI(N.isValid(), "invalid expression", &N);
    1240             : }
    1241             : 
    1242        7438 : void Verifier::visitDIGlobalVariableExpression(
    1243             :     const DIGlobalVariableExpression &GVE) {
    1244           0 :   AssertDI(GVE.getVariable(), "missing variable");
    1245             :   if (auto *Var = GVE.getVariable())
    1246        7438 :     visitDIGlobalVariable(*Var);
    1247        7438 :   if (auto *Expr = GVE.getExpression()) {
    1248        7438 :     visitDIExpression(*Expr);
    1249        7438 :     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       27209 : 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       27209 :   if (const GlobalValue *GV = M.getNamedValue(C.getName()))
    1276       26974 :     Assert(!GV->hasPrivateLinkage(), "comdat global value has private linkage",
    1277             :            GV);
    1278             : }
    1279             : 
    1280       94959 : void Verifier::visitModuleIdents(const Module &M) {
    1281       94959 :   const NamedMDNode *Idents = M.getNamedMetadata("llvm.ident");
    1282       94959 :   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       39417 :   for (const MDNode *N : Idents->operands()) {
    1288       13332 :     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       94959 : void Verifier::visitModuleFlags(const Module &M) {
    1298       94959 :   const NamedMDNode *Flags = M.getModuleFlagsMetadata();
    1299      174210 :   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       45582 :   for (const MDNode *MDN : Flags->operands())
    1305       29874 :     visitModuleFlag(MDN, SeenIDs, Requirements);
    1306             : 
    1307             :   // Validate that the requirements in the module are valid.
    1308       15734 :   for (const MDNode *Requirement : Requirements) {
    1309          13 :     const MDString *Flag = cast<MDString>(Requirement->getOperand(0));
    1310             :     const Metadata *ReqValue = Requirement->getOperand(1);
    1311             : 
    1312             :     const MDNode *Op = SeenIDs.lookup(Flag);
    1313          13 :     if (!Op) {
    1314           2 :       CheckFailed("invalid requirement on flag, flag is not present in module",
    1315             :                   Flag);
    1316           3 :       continue;
    1317             :     }
    1318             : 
    1319          13 :     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       29874 : 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       29889 :   Assert(Op->getNumOperands() == 3,
    1335             :          "incorrect number of operands in module flag", Op);
    1336             :   Module::ModFlagBehavior MFB;
    1337       29873 :   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       59740 :   MDString *ID = dyn_cast_or_null<MDString>(Op->getOperand(1));
    1347       29872 :   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       29868 :   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        1226 :   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          16 :   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          19 :     Assert(Value && Value->getNumOperands() == 2,
    1370             :            "invalid value for 'require' module flag (expected metadata pair)",
    1371             :            Op->getOperand(2));
    1372          16 :     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          13 :     Requirements.push_back(Value);
    1380          13 :     break;
    1381             :   }
    1382             : 
    1383          50 :   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       29862 :   if (MFB != Module::Require) {
    1396       59698 :     bool Inserted = SeenIDs.insert(std::make_pair(ID, Op)).second;
    1397       29850 :     Assert(Inserted,
    1398             :            "module flag identifiers must be unique (or of 'require' type)", ID);
    1399             :   }
    1400             : 
    1401       29861 :   if (ID->getString() == "wchar_size") {
    1402             :     ConstantInt *Value
    1403        9718 :       = mdconst::dyn_extract_or_null<ConstantInt>(Op->getOperand(2));
    1404           0 :     Assert(Value, "wchar_size metadata requires constant integer argument");
    1405             :   }
    1406             : 
    1407       29861 :   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      161940 :   return Kind == Attribute::ReadOnly || Kind == Attribute::WriteOnly ||
    1469             :          Kind == Attribute::ReadNone;
    1470             : }
    1471             : 
    1472     1088642 : void Verifier::verifyAttributeTypes(AttributeSet Attrs, bool IsFunction,
    1473             :                                     const Value *V) {
    1474     4679805 :   for (Attribute A : Attrs) {
    1475     3591164 :     if (A.isStringAttribute())
    1476     2205689 :       continue;
    1477             : 
    1478     1385475 :     if (isFuncOnlyAttr(A.getKindAsEnum())) {
    1479      955831 :       if (!IsFunction) {
    1480           5 :         CheckFailed("Attribute '" + A.getAsString() +
    1481             :                         "' only applies to functions!",
    1482             :                     V);
    1483           2 :         return;
    1484             :       }
    1485      591584 :     } 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     2606086 : void Verifier::verifyParameterAttrs(AttributeSet Attrs, Type *Ty,
    1497             :                                     const Value *V) {
    1498     2606086 :   if (!Attrs.hasAttributes())
    1499     2368171 :     return;
    1500             : 
    1501      237927 :   verifyAttributeTypes(Attrs, /*IsFunction=*/false, V);
    1502             : 
    1503             :   // Check for mutually incompatible attributes.  Only inreg is compatible with
    1504             :   // sret.
    1505             :   unsigned AttrCount = 0;
    1506      237927 :   AttrCount += Attrs.hasAttribute(Attribute::ByVal);
    1507      237927 :   AttrCount += Attrs.hasAttribute(Attribute::InAlloca);
    1508      470680 :   AttrCount += Attrs.hasAttribute(Attribute::StructRet) ||
    1509      232753 :                Attrs.hasAttribute(Attribute::InReg);
    1510      237927 :   AttrCount += Attrs.hasAttribute(Attribute::Nest);
    1511      237931 :   Assert(AttrCount <= 1, "Attributes 'byval', 'inalloca', 'inreg', 'nest', "
    1512             :                          "and 'sret' are incompatible!",
    1513             :          V);
    1514             : 
    1515      237924 :   Assert(!(Attrs.hasAttribute(Attribute::InAlloca) &&
    1516             :            Attrs.hasAttribute(Attribute::ReadOnly)),
    1517             :          "Attributes "
    1518             :          "'inalloca and readonly' are incompatible!",
    1519             :          V);
    1520             : 
    1521      237922 :   Assert(!(Attrs.hasAttribute(Attribute::StructRet) &&
    1522             :            Attrs.hasAttribute(Attribute::Returned)),
    1523             :          "Attributes "
    1524             :          "'sret and returned' are incompatible!",
    1525             :          V);
    1526             : 
    1527      279732 :   Assert(!(Attrs.hasAttribute(Attribute::ZExt) &&
    1528             :            Attrs.hasAttribute(Attribute::SExt)),
    1529             :          "Attributes "
    1530             :          "'zeroext and signext' are incompatible!",
    1531             :          V);
    1532             : 
    1533      238776 :   Assert(!(Attrs.hasAttribute(Attribute::ReadNone) &&
    1534             :            Attrs.hasAttribute(Attribute::ReadOnly)),
    1535             :          "Attributes "
    1536             :          "'readnone and readonly' are incompatible!",
    1537             :          V);
    1538             : 
    1539      238778 :   Assert(!(Attrs.hasAttribute(Attribute::ReadNone) &&
    1540             :            Attrs.hasAttribute(Attribute::WriteOnly)),
    1541             :          "Attributes "
    1542             :          "'readnone and writeonly' are incompatible!",
    1543             :          V);
    1544             : 
    1545      251306 :   Assert(!(Attrs.hasAttribute(Attribute::ReadOnly) &&
    1546             :            Attrs.hasAttribute(Attribute::WriteOnly)),
    1547             :          "Attributes "
    1548             :          "'readonly and writeonly' are incompatible!",
    1549             :          V);
    1550             : 
    1551      237920 :   Assert(!(Attrs.hasAttribute(Attribute::NoInline) &&
    1552             :            Attrs.hasAttribute(Attribute::AlwaysInline)),
    1553             :          "Attributes "
    1554             :          "'noinline and alwaysinline' are incompatible!",
    1555             :          V);
    1556             : 
    1557      237920 :   AttrBuilder IncompatibleAttrs = AttributeFuncs::typeIncompatible(Ty);
    1558      475848 :   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      134545 :     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      269088 :     if (!isa<PointerType>(PTy->getElementType()))
    1572      129967 :       Assert(!Attrs.hasAttribute(Attribute::SwiftError),
    1573             :              "Attribute 'swifterror' only applies to parameters "
    1574             :              "with pointer to pointer type!",
    1575             :              V);
    1576             :   } else {
    1577      103373 :     Assert(!Attrs.hasAttribute(Attribute::ByVal),
    1578             :            "Attribute 'byval' only applies to parameters with pointer type!",
    1579             :            V);
    1580      103374 :     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     1630546 : void Verifier::verifyFunctionAttrs(FunctionType *FT, AttributeList Attrs,
    1590             :                                    const Value *V) {
    1591     1630546 :   if (Attrs.isEmpty())
    1592      779878 :     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      909778 :   AttributeSet RetAttrs = Attrs.getRetAttributes();
    1602      909778 :   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      909778 :   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     1819556 :   verifyParameterAttrs(RetAttrs, FT->getReturnType(), V);
    1621             : 
    1622             :   // Verify parameter attributes.
    1623     5142624 :   for (unsigned i = 0, e = FT->getNumParams(); i != e; ++i) {
    1624     1661539 :     Type *Ty = FT->getParamType(i);
    1625     1661539 :     AttributeSet ArgAttrs = Attrs.getParamAttributes(i);
    1626             : 
    1627     1661539 :     verifyParameterAttrs(ArgAttrs, Ty, V);
    1628             : 
    1629     1661539 :     if (ArgAttrs.hasAttribute(Attribute::Nest)) {
    1630         249 :       Assert(!SawNest, "More than one parameter has attribute nest!", V);
    1631             :       SawNest = true;
    1632             :     }
    1633             : 
    1634     1661539 :     if (ArgAttrs.hasAttribute(Attribute::Returned)) {
    1635        2176 :       Assert(!SawReturned, "More than one parameter has attribute returned!",
    1636             :              V);
    1637        4352 :       Assert(Ty->canLosslesslyBitCastTo(FT->getReturnType()),
    1638             :              "Incompatible argument and return types for 'returned' attribute",
    1639             :              V);
    1640             :       SawReturned = true;
    1641             :     }
    1642             : 
    1643     1661539 :     if (ArgAttrs.hasAttribute(Attribute::StructRet)) {
    1644        5174 :       Assert(!SawSRet, "Cannot have multiple 'sret' parameters!", V);
    1645        5173 :       Assert(i == 0 || i == 1,
    1646             :              "Attribute 'sret' is not on first or second parameter!", V);
    1647             :       SawSRet = true;
    1648             :     }
    1649             : 
    1650     1661537 :     if (ArgAttrs.hasAttribute(Attribute::SwiftSelf)) {
    1651         648 :       Assert(!SawSwiftSelf, "Cannot have multiple 'swiftself' parameters!", V);
    1652             :       SawSwiftSelf = true;
    1653             :     }
    1654             : 
    1655     1661536 :     if (ArgAttrs.hasAttribute(Attribute::SwiftError)) {
    1656         960 :       Assert(!SawSwiftError, "Cannot have multiple 'swifterror' parameters!",
    1657             :              V);
    1658             :       SawSwiftError = true;
    1659             :     }
    1660             : 
    1661     1661535 :     if (ArgAttrs.hasAttribute(Attribute::InAlloca)) {
    1662         423 :       Assert(i == FT->getNumParams() - 1,
    1663             :              "inalloca isn't on the last parameter!", V);
    1664             :     }
    1665             :   }
    1666             : 
    1667      909773 :   if (!Attrs.hasAttributes(AttributeList::FunctionIndex))
    1668             :     return;
    1669             : 
    1670      850715 :   verifyAttributeTypes(Attrs.getFnAttributes(), /*IsFunction=*/true, V);
    1671             : 
    1672      850715 :   Assert(!(Attrs.hasFnAttribute(Attribute::ReadNone) &&
    1673             :            Attrs.hasFnAttribute(Attribute::ReadOnly)),
    1674             :          "Attributes 'readnone and readonly' are incompatible!", V);
    1675             : 
    1676      999819 :   Assert(!(Attrs.hasFnAttribute(Attribute::ReadNone) &&
    1677             :            Attrs.hasFnAttribute(Attribute::WriteOnly)),
    1678             :          "Attributes 'readnone and writeonly' are incompatible!", V);
    1679             : 
    1680      862741 :   Assert(!(Attrs.hasFnAttribute(Attribute::ReadOnly) &&
    1681             :            Attrs.hasFnAttribute(Attribute::WriteOnly)),
    1682             :          "Attributes 'readonly and writeonly' are incompatible!", V);
    1683             : 
    1684      999814 :   Assert(!(Attrs.hasFnAttribute(Attribute::ReadNone) &&
    1685             :            Attrs.hasFnAttribute(Attribute::InaccessibleMemOrArgMemOnly)),
    1686             :          "Attributes 'readnone and inaccessiblemem_or_argmemonly' are "
    1687             :          "incompatible!",
    1688             :          V);
    1689             : 
    1690      999814 :   Assert(!(Attrs.hasFnAttribute(Attribute::ReadNone) &&
    1691             :            Attrs.hasFnAttribute(Attribute::InaccessibleMemOnly)),
    1692             :          "Attributes 'readnone and inaccessiblememonly' are incompatible!", V);
    1693             : 
    1694      952703 :   Assert(!(Attrs.hasFnAttribute(Attribute::NoInline) &&
    1695             :            Attrs.hasFnAttribute(Attribute::AlwaysInline)),
    1696             :          "Attributes 'noinline and alwaysinline' are incompatible!", V);
    1697             : 
    1698      850712 :   if (Attrs.hasFnAttribute(Attribute::OptimizeNone)) {
    1699       69086 :     Assert(Attrs.hasFnAttribute(Attribute::NoInline),
    1700             :            "Attribute 'optnone' requires 'noinline'!", V);
    1701             : 
    1702       69086 :     Assert(!Attrs.hasFnAttribute(Attribute::OptimizeForSize),
    1703             :            "Attributes 'optsize and optnone' are incompatible!", V);
    1704             : 
    1705       69086 :     Assert(!Attrs.hasFnAttribute(Attribute::MinSize),
    1706             :            "Attributes 'minsize and optnone' are incompatible!", V);
    1707             :   }
    1708             : 
    1709      850712 :   if (Attrs.hasFnAttribute(Attribute::JumpTable)) {
    1710          16 :     const GlobalValue *GV = cast<GlobalValue>(V);
    1711          17 :     Assert(GV->hasGlobalUnnamedAddr(),
    1712             :            "Attribute 'jumptable' requires 'unnamed_addr'", V);
    1713             :   }
    1714             : 
    1715      850711 :   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     1045185 : void Verifier::verifyFunctionMetadata(
    1744             :     ArrayRef<std::pair<unsigned, MDNode *>> MDs) {
    1745     1077137 :   for (const auto &Pair : MDs) {
    1746       15980 :     if (Pair.first == LLVMContext::MD_prof) {
    1747        1014 :       MDNode *MD = Pair.second;
    1748        1019 :       Assert(MD->getNumOperands() >= 2,
    1749             :              "!prof annotations should have no less than 2 operands", MD);
    1750             : 
    1751             :       // Check first operand.
    1752        1013 :       Assert(MD->getOperand(0) != nullptr, "first operand should not be null",
    1753             :              MD);
    1754        1014 :       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        1012 :       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        2022 :       Assert(MD->getOperand(1) != nullptr, "second operand should not be null",
    1766             :              MD);
    1767        1012 :       Assert(isa<ConstantAsMetadata>(MD->getOperand(1)),
    1768             :              "expected integer argument to function_entry_count", MD);
    1769             :     }
    1770             :   }
    1771             : }
    1772             : 
    1773      235062 : void Verifier::visitConstantExprsRecursively(const Constant *EntryC) {
    1774      235062 :   if (!ConstantExprVisited.insert(EntryC).second)
    1775       67054 :     return;
    1776             : 
    1777             :   SmallVector<const Constant *, 16> Stack;
    1778      168008 :   Stack.push_back(EntryC);
    1779             : 
    1780      527185 :   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      117743 :       visitConstantExpr(CE);
    1786             : 
    1787      453385 :     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       94208 :       Assert(GV->getParent() == &M, "Referencing global in another module!",
    1791             :              EntryC, &M, GV, GV->getParent());
    1792       94208 :       continue;
    1793             :     }
    1794             : 
    1795             :     // Visit all sub-expressions.
    1796     1344398 :     for (const Use &U : C->operands()) {
    1797      407230 :       const auto *OpC = dyn_cast<Constant>(U);
    1798      407230 :       if (!OpC)
    1799      216596 :         continue;
    1800      406695 :       if (!ConstantExprVisited.insert(OpC).second)
    1801      215526 :         continue;
    1802      191169 :       Stack.push_back(OpC);
    1803             :     }
    1804             :   }
    1805             : }
    1806             : 
    1807      117743 : void Verifier::visitConstantExpr(const ConstantExpr *CE) {
    1808      235486 :   if (CE->getOpcode() == Instruction::BitCast)
    1809       90444 :     Assert(CastInst::castIsValid(Instruction::BitCast, CE->getOperand(0),
    1810             :                                  CE->getType()),
    1811             :            "Invalid bitcast", CE);
    1812             : 
    1813      235486 :   if (CE->getOpcode() == Instruction::IntToPtr ||
    1814             :       CE->getOpcode() == Instruction::PtrToInt) {
    1815             :     auto *PtrTy = CE->getOpcode() == Instruction::IntToPtr
    1816        5210 :                       ? CE->getType()
    1817             :                       : CE->getOperand(0)->getType();
    1818             :     StringRef Msg = CE->getOpcode() == Instruction::IntToPtr
    1819             :                         ? "inttoptr not supported for non-integral pointers"
    1820        3554 :                         : "ptrtoint not supported for non-integral pointers";
    1821        7114 :     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     1630548 :   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       94959 : void Verifier::verifyFrameRecoverIndices() {
    1969      190008 :   for (auto &Counts : FrameEscapeInfo) {
    1970          91 :     Function *F = Counts.first;
    1971          91 :     unsigned EscapedObjectCount = Counts.second.first;
    1972          91 :     unsigned MaxRecoveredIndex = Counts.second.second;
    1973          92 :     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         365 : 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         365 :   return UnwindDest->getFirstNonPHI();
    1990             : }
    1991             : 
    1992     1045199 : void Verifier::verifySiblingFuncletUnwinds() {
    1993             :   SmallPtrSet<Instruction *, 8> Visited;
    1994             :   SmallPtrSet<Instruction *, 8> Active;
    1995     1045547 :   for (const auto &Pair : SiblingFuncletInfo) {
    1996         352 :     Instruction *PredPad = Pair.first;
    1997         352 :     if (Visited.count(PredPad))
    1998             :       continue;
    1999         314 :     Active.insert(PredPad);
    2000         314 :     TerminatorInst *Terminator = Pair.second;
    2001             :     do {
    2002         358 :       Instruction *SuccPad = getSuccPad(Terminator);
    2003         358 :       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         354 :       if (!Visited.insert(SuccPad).second)
    2019             :         break;
    2020             :       // Walk to this successor if it has a map entry.
    2021             :       PredPad = SuccPad;
    2022         318 :       auto TermI = SiblingFuncletInfo.find(PredPad);
    2023         318 :       if (TermI == SiblingFuncletInfo.end())
    2024             :         break;
    2025          44 :       Terminator = TermI->second;
    2026          44 :       Active.insert(PredPad);
    2027             :     } while (true);
    2028             :     // Each node only has one successor, so we've walked all the active
    2029             :     // nodes' successors.
    2030         310 :     Active.clear();
    2031             :   }
    2032             : }
    2033             : 
    2034             : // visitFunction - Verify that a function is ok.
    2035             : //
    2036     1045199 : void Verifier::visitFunction(const Function &F) {
    2037     1045199 :   visitGlobalValue(F);
    2038             : 
    2039             :   // Check function arguments.
    2040     1045199 :   FunctionType *FT = F.getFunctionType();
    2041     1045199 :   unsigned NumArgs = F.arg_size();
    2042             : 
    2043     2081113 :   Assert(&Context == &F.getContext(),
    2044             :          "Function context does not match Module context!", &F);
    2045             : 
    2046     1045199 :   Assert(!F.hasCommonLinkage(), "Functions may not have common linkage", &F);
    2047     2090398 :   Assert(FT->getNumParams() == NumArgs,
    2048             :          "# formal arguments must match # of arguments for function type!", &F,
    2049             :          FT);
    2050      363935 :   Assert(F.getReturnType()->isFirstClassType() ||
    2051             :              F.getReturnType()->isVoidTy() || F.getReturnType()->isStructTy(),
    2052             :          "Functions cannot return aggregate values!", &F);
    2053             : 
    2054     1048802 :   Assert(!F.hasStructRetAttr() || F.getReturnType()->isVoidTy(),
    2055             :          "Invalid struct return type!", &F);
    2056             : 
    2057     1045199 :   AttributeList Attrs = F.getAttributes();
    2058             : 
    2059     2090398 :   Assert(verifyAttributeCount(Attrs, FT->getNumParams()),
    2060             :          "Attribute after last parameter!", &F);
    2061             : 
    2062             :   // Check function attributes.
    2063     1045199 :   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     1045201 :   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     1045197 :   switch (F.getCallingConv()) {
    2075             :   default:
    2076             :   case CallingConv::C:
    2077             :     break;
    2078             :   case CallingConv::AMDGPU_KERNEL:
    2079             :   case CallingConv::SPIR_KERNEL:
    2080       56240 :     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       59971 :     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       63781 :     Assert(!F.isVarArg(), "Calling convention does not support varargs or "
    2097             :                           "perfect forwarding!",
    2098             :            &F);
    2099             :     break;
    2100             :   }
    2101             : 
    2102     3135564 :   bool isLLVMdotName = F.getName().size() >= 5 &&
    2103     1980724 :                        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     2875198 :   for (const Argument &Arg : F.args()) {
    2108     3660024 :     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     1830012 :     if (!isLLVMdotName) {
    2114     1465919 :       Assert(!Arg.getType()->isMetadataTy(),
    2115             :              "Function takes metadata but isn't an intrinsic", &Arg, &F);
    2116     1465921 :       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     1830010 :     if (Attrs.hasParamAttribute(i, Attribute::SwiftError)) {
    2122         541 :       verifySwiftErrorValue(&Arg);
    2123             :     }
    2124             :     ++i;
    2125             :   }
    2126             : 
    2127     1045186 :   if (!isLLVMdotName)
    2128      860447 :     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     1045185 :   F.getAllMetadata(MDs);
    2134             :   assert(F.hasMetadata() != MDs.empty() && "Bit out-of-sync");
    2135     1045185 :   verifyFunctionMetadata(MDs);
    2136             : 
    2137             :   // Check validity of the personality function
    2138     1045185 :   if (F.hasPersonalityFn()) {
    2139        7526 :     auto *Per = dyn_cast<Function>(F.getPersonalityFn()->stripPointerCasts());
    2140        3763 :     if (Per)
    2141        3528 :       Assert(Per->getParent() == F.getParent(),
    2142             :              "Referencing personality function in another module!",
    2143             :              &F, F.getParent(), Per, Per->getParent());
    2144             :   }
    2145             : 
    2146     1045184 :   if (F.isMaterializable()) {
    2147             :     // Function has a body somewhere we can't see.
    2148         219 :     Assert(MDs.empty(), "unmaterialized function cannot have metadata", &F,
    2149             :            MDs.empty() ? nullptr : MDs.front().second);
    2150     1044966 :   } else if (F.isDeclaration()) {
    2151      275843 :     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      275697 :     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      769275 :     Assert(!isLLVMdotName, "llvm intrinsics cannot be defined!", &F);
    2166             : 
    2167             :     // Check the entry node
    2168      769266 :     const BasicBlock *Entry = &F.getEntryBlock();
    2169      769267 :     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     1538530 :     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      801065 :     for (const auto &I : MDs) {
    2181             :       // Verify that the attachment is legal.
    2182       15905 :       switch (I.first) {
    2183             :       default:
    2184             :         break;
    2185        9292 :       case LLVMContext::MD_dbg: {
    2186        9292 :         ++NumDebugAttachments;
    2187        9297 :         AssertDI(NumDebugAttachments == 1,
    2188             :                  "function must have a single !dbg attachment", &F, I.second);
    2189       18583 :         AssertDI(isa<DISubprogram>(I.second),
    2190             :                  "function !dbg attachment must be a subprogram", &F, I.second);
    2191        9290 :         auto *SP = cast<DISubprogram>(I.second);
    2192       18580 :         const Function *&AttachedTo = DISubprogramAttachments[SP];
    2193        9292 :         AssertDI(!AttachedTo || AttachedTo == &F,
    2194             :                  "DISubprogram attached to more than one function", SP, &F);
    2195        9288 :         AttachedTo = &F;
    2196        9288 :         break;
    2197             :       }
    2198        1013 :       case LLVMContext::MD_prof:
    2199        1013 :         ++NumProfAttachments;
    2200        1014 :         Assert(NumProfAttachments == 1,
    2201             :                "function must have a single !prof attachment", &F, I.second);
    2202             :         break;
    2203             :       }
    2204             : 
    2205             :       // Verify the metadata itself.
    2206       15900 :       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     1229481 :   if (F.getIntrinsicID() && F.getParent()->isMaterialized()) {
    2215             :     const User *U;
    2216      184302 :     if (F.hasAddressTaken(&U))
    2217           2 :       Assert(false, "Invalid user of intrinsic instruction!", U);
    2218             :   }
    2219             : 
    2220     1045173 :   auto *N = F.getSubprogram();
    2221     1045173 :   HasDebugInfo = (N != nullptr);
    2222     1045173 :   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       29747 :   for (auto &BB : F)
    2232      140478 :     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      120018 :           dyn_cast_or_null<DILocation>(I.getDebugLoc().getAsMDNode());
    2237      120018 :       if (!DL)
    2238      141315 :         continue;
    2239       89832 :       if (!Seen.insert(DL).second)
    2240       51607 :         continue;
    2241             : 
    2242       76450 :       DILocalScope *Scope = DL->getInlinedAtScope();
    2243       63893 :       if (Scope && !Seen.insert(Scope).second)
    2244       25668 :         continue;
    2245             : 
    2246       25114 :       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       16225 :       if (SP && ((Scope != SP) && !Seen.insert(SP).second))
    2251        3668 :         continue;
    2252             : 
    2253             :       // FIXME: Once N is canonical, check "SP == &N".
    2254        8893 :       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     1126984 : void Verifier::visitBasicBlock(BasicBlock &BB) {
    2263     1126984 :   InstsInThisBlock.clear();
    2264             : 
    2265             :   // Ensure that basic blocks have terminators!
    2266     1126984 :   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     1126984 :   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       56390 :     for (const PHINode &PN : BB.phis()) {
    2275             :       // Ensure that PHI nodes have at least one entry!
    2276       78548 :       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      157096 :       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       78548 :       Values.reserve(PN.getNumIncomingValues());
    2288      400424 :       for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
    2289      160938 :         Values.push_back(
    2290      321876 :             std::make_pair(PN.getIncomingBlock(i), PN.getIncomingValue(i)));
    2291             :       llvm::sort(Values.begin(), Values.end());
    2292             : 
    2293      239485 :       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      325719 :         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      482811 :         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     6931079 :   for (auto &I : BB)
    2315             :   {
    2316     5804096 :     Assert(I.getParent() == &BB, "Instruction has bogus parent pointer!");
    2317             :   }
    2318             : }
    2319             : 
    2320     1126967 : void Verifier::visitTerminatorInst(TerminatorInst &I) {
    2321             :   // Ensure that terminators only exist at the end of the basic block.
    2322     2253934 :   Assert(&I == I.getParent()->getTerminator(),
    2323             :          "Terminator found in the middle of a basic block!", I.getParent());
    2324     1126967 :   visitInstruction(I);
    2325             : }
    2326             : 
    2327      323150 : void Verifier::visitBranchInst(BranchInst &BI) {
    2328      323150 :   if (BI.isConditional()) {
    2329      131390 :     Assert(BI.getCondition()->getType()->isIntegerTy(1),
    2330             :            "Branch condition is not 'i1' type!", &BI, BI.getCondition());
    2331             :   }
    2332      323149 :   visitTerminatorInst(BI);
    2333             : }
    2334             : 
    2335      777394 : void Verifier::visitReturnInst(ReturnInst &RI) {
    2336      777394 :   Function *F = RI.getParent()->getParent();
    2337             :   unsigned N = RI.getNumOperands();
    2338      777394 :   if (F->getReturnType()->isVoidTy())
    2339      267051 :     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     1020686 :     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      777394 :   visitTerminatorInst(RI);
    2352             : }
    2353             : 
    2354        4018 : 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        4018 :   Type *SwitchTy = SI.getCondition()->getType();
    2358             :   SmallPtrSet<ConstantInt*, 32> Constants;
    2359       26293 :   for (auto &Case : SI.cases()) {
    2360       18257 :     Assert(Case.getCaseValue()->getType() == SwitchTy,
    2361             :            "Switch constants must all be same type as switch value!", &SI);
    2362       18257 :     Assert(Constants.insert(Case.getCaseValue()).second,
    2363             :            "Duplicate integer as switch case", &SI, Case.getCaseValue());
    2364             :   }
    2365             : 
    2366        4018 :   visitTerminatorInst(SI);
    2367             : }
    2368             : 
    2369         735 : void Verifier::visitIndirectBrInst(IndirectBrInst &BI) {
    2370        1470 :   Assert(BI.getAddress()->getType()->isPointerTy(),
    2371             :          "Indirectbr operand must have pointer type!", &BI);
    2372        2806 :   for (unsigned i = 0, e = BI.getNumDestinations(); i != e; ++i)
    2373        4142 :     Assert(BI.getDestination(i)->getType()->isLabelTy(),
    2374             :            "Indirectbr destinations must all have pointer type!", &BI);
    2375             : 
    2376         735 :   visitTerminatorInst(BI);
    2377             : }
    2378             : 
    2379       91243 : void Verifier::visitSelectInst(SelectInst &SI) {
    2380       91243 :   Assert(!SelectInst::areInvalidOperands(SI.getOperand(0), SI.getOperand(1),
    2381             :                                          SI.getOperand(2)),
    2382             :          "Invalid operands for select instruction!", &SI);
    2383             : 
    2384       91243 :   Assert(SI.getTrueValue()->getType() == SI.getType(),
    2385             :          "Select values must have same type as select instruction!", &SI);
    2386       91243 :   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       39807 : void Verifier::visitTruncInst(TruncInst &I) {
    2397             :   // Get the source and destination types
    2398       39807 :   Type *SrcTy = I.getOperand(0)->getType();
    2399       39807 :   Type *DestTy = I.getType();
    2400             : 
    2401             :   // Get the size of the types in bits, we'll need this later
    2402       39807 :   unsigned SrcBitSize = SrcTy->getScalarSizeInBits();
    2403       39807 :   unsigned DestBitSize = DestTy->getScalarSizeInBits();
    2404             : 
    2405       39807 :   Assert(SrcTy->isIntOrIntVectorTy(), "Trunc only operates on integer", &I);
    2406       39807 :   Assert(DestTy->isIntOrIntVectorTy(), "Trunc only produces integer", &I);
    2407       39807 :   Assert(SrcTy->isVectorTy() == DestTy->isVectorTy(),
    2408             :          "trunc source and destination must both be a vector or neither", &I);
    2409       39807 :   Assert(SrcBitSize > DestBitSize, "DestTy too big for Trunc", &I);
    2410             : 
    2411       39807 :   visitInstruction(I);
    2412             : }
    2413             : 
    2414       57388 : void Verifier::visitZExtInst(ZExtInst &I) {
    2415             :   // Get the source and destination types
    2416       57388 :   Type *SrcTy = I.getOperand(0)->getType();
    2417       57388 :   Type *DestTy = I.getType();
    2418             : 
    2419             :   // Get the size of the types in bits, we'll need this later
    2420       57388 :   Assert(SrcTy->isIntOrIntVectorTy(), "ZExt only operates on integer", &I);
    2421       57388 :   Assert(DestTy->isIntOrIntVectorTy(), "ZExt only produces an integer", &I);
    2422       57388 :   Assert(SrcTy->isVectorTy() == DestTy->isVectorTy(),
    2423             :          "zext source and destination must both be a vector or neither", &I);
    2424       57388 :   unsigned SrcBitSize = SrcTy->getScalarSizeInBits();
    2425       57388 :   unsigned DestBitSize = DestTy->getScalarSizeInBits();
    2426             : 
    2427       57388 :   Assert(SrcBitSize < DestBitSize, "Type too small for ZExt", &I);
    2428             : 
    2429       57388 :   visitInstruction(I);
    2430             : }
    2431             : 
    2432       58608 : void Verifier::visitSExtInst(SExtInst &I) {
    2433             :   // Get the source and destination types
    2434       58608 :   Type *SrcTy = I.getOperand(0)->getType();
    2435       58608 :   Type *DestTy = I.getType();
    2436             : 
    2437             :   // Get the size of the types in bits, we'll need this later
    2438       58608 :   unsigned SrcBitSize = SrcTy->getScalarSizeInBits();
    2439       58608 :   unsigned DestBitSize = DestTy->getScalarSizeInBits();
    2440             : 
    2441       58608 :   Assert(SrcTy->isIntOrIntVectorTy(), "SExt only operates on integer", &I);
    2442       58608 :   Assert(DestTy->isIntOrIntVectorTy(), "SExt only produces an integer", &I);
    2443       58608 :   Assert(SrcTy->isVectorTy() == DestTy->isVectorTy(),
    2444             :          "sext source and destination must both be a vector or neither", &I);
    2445       58608 :   Assert(SrcBitSize < DestBitSize, "Type too small for SExt", &I);
    2446             : 
    2447       58608 :   visitInstruction(I);
    2448             : }
    2449             : 
    2450        4450 : void Verifier::visitFPTruncInst(FPTruncInst &I) {
    2451             :   // Get the source and destination types
    2452        4450 :   Type *SrcTy = I.getOperand(0)->getType();
    2453        4450 :   Type *DestTy = I.getType();
    2454             :   // Get the size of the types in bits, we'll need this later
    2455        4450 :   unsigned SrcBitSize = SrcTy->getScalarSizeInBits();
    2456        4450 :   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        4450 :   Assert(SrcTy->isVectorTy() == DestTy->isVectorTy(),
    2461             :          "fptrunc source and destination must both be a vector or neither", &I);
    2462        4450 :   Assert(SrcBitSize > DestBitSize, "DestTy too big for FPTrunc", &I);
    2463             : 
    2464        4450 :   visitInstruction(I);
    2465             : }
    2466             : 
    2467       10012 : void Verifier::visitFPExtInst(FPExtInst &I) {
    2468             :   // Get the source and destination types
    2469       10012 :   Type *SrcTy = I.getOperand(0)->getType();
    2470       10012 :   Type *DestTy = I.getType();
    2471             : 
    2472             :   // Get the size of the types in bits, we'll need this later
    2473       10012 :   unsigned SrcBitSize = SrcTy->getScalarSizeInBits();
    2474       10012 :   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       10012 :   Assert(SrcTy->isVectorTy() == DestTy->isVectorTy(),
    2479             :          "fpext source and destination must both be a vector or neither", &I);
    2480       10012 :   Assert(SrcBitSize < DestBitSize, "DestTy too small for FPExt", &I);
    2481             : 
    2482       10012 :   visitInstruction(I);
    2483             : }
    2484             : 
    2485        8216 : void Verifier::visitUIToFPInst(UIToFPInst &I) {
    2486             :   // Get the source and destination types
    2487        8216 :   Type *SrcTy = I.getOperand(0)->getType();
    2488        8216 :   Type *DestTy = I.getType();
    2489             : 
    2490             :   bool SrcVec = SrcTy->isVectorTy();
    2491             :   bool DstVec = DestTy->isVectorTy();
    2492             : 
    2493        8216 :   Assert(SrcVec == DstVec,
    2494             :          "UIToFP source and dest must both be vector or scalar", &I);
    2495        8216 :   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        8216 :   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        8216 :   visitInstruction(I);
    2506             : }
    2507             : 
    2508       14170 : void Verifier::visitSIToFPInst(SIToFPInst &I) {
    2509             :   // Get the source and destination types
    2510       14170 :   Type *SrcTy = I.getOperand(0)->getType();
    2511       14170 :   Type *DestTy = I.getType();
    2512             : 
    2513             :   bool SrcVec = SrcTy->isVectorTy();
    2514             :   bool DstVec = DestTy->isVectorTy();
    2515             : 
    2516       14170 :   Assert(SrcVec == DstVec,
    2517             :          "SIToFP source and dest must both be vector or scalar", &I);
    2518       14170 :   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       14170 :   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       14170 :   visitInstruction(I);
    2529             : }
    2530             : 
    2531        5888 : void Verifier::visitFPToUIInst(FPToUIInst &I) {
    2532             :   // Get the source and destination types
    2533        5888 :   Type *SrcTy = I.getOperand(0)->getType();
    2534        5888 :   Type *DestTy = I.getType();
    2535             : 
    2536             :   bool SrcVec = SrcTy->isVectorTy();
    2537             :   bool DstVec = DestTy->isVectorTy();
    2538             : 
    2539        5888 :   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        5888 :   Assert(DestTy->isIntOrIntVectorTy(),
    2544             :          "FPToUI result must be integer or integer vector", &I);
    2545             : 
    2546        5888 :   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        5888 :   visitInstruction(I);
    2552             : }
    2553             : 
    2554        8609 : void Verifier::visitFPToSIInst(FPToSIInst &I) {
    2555             :   // Get the source and destination types
    2556        8609 :   Type *SrcTy = I.getOperand(0)->getType();
    2557        8609 :   Type *DestTy = I.getType();
    2558             : 
    2559             :   bool SrcVec = SrcTy->isVectorTy();
    2560             :   bool DstVec = DestTy->isVectorTy();
    2561             : 
    2562        8609 :   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        8609 :   Assert(DestTy->isIntOrIntVectorTy(),
    2567             :          "FPToSI result must be integer or integer vector", &I);
    2568             : 
    2569        8609 :   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        8609 :   visitInstruction(I);
    2575             : }
    2576             : 
    2577        8092 : void Verifier::visitPtrToIntInst(PtrToIntInst &I) {
    2578             :   // Get the source and destination types
    2579        8092 :   Type *SrcTy = I.getOperand(0)->getType();
    2580        8092 :   Type *DestTy = I.getType();
    2581             : 
    2582        8092 :   Assert(SrcTy->isPtrOrPtrVectorTy(), "PtrToInt source must be pointer", &I);
    2583             : 
    2584             :   if (auto *PTy = dyn_cast<PointerType>(SrcTy->getScalarType()))
    2585        8095 :     Assert(!DL.isNonIntegralPointerType(PTy),
    2586             :            "ptrtoint not supported for non-integral pointers");
    2587             : 
    2588        8089 :   Assert(DestTy->isIntOrIntVectorTy(), "PtrToInt result must be integral", &I);
    2589        8089 :   Assert(SrcTy->isVectorTy() == DestTy->isVectorTy(), "PtrToInt type mismatch",
    2590             :          &I);
    2591             : 
    2592        8089 :   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        8089 :   visitInstruction(I);
    2600             : }
    2601             : 
    2602        6776 : void Verifier::visitIntToPtrInst(IntToPtrInst &I) {
    2603             :   // Get the source and destination types
    2604        6776 :   Type *SrcTy = I.getOperand(0)->getType();
    2605        6776 :   Type *DestTy = I.getType();
    2606             : 
    2607        6776 :   Assert(SrcTy->isIntOrIntVectorTy(),
    2608             :          "IntToPtr source must be an integral", &I);
    2609        6776 :   Assert(DestTy->isPtrOrPtrVectorTy(), "IntToPtr result must be a pointer", &I);
    2610             : 
    2611             :   if (auto *PTy = dyn_cast<PointerType>(DestTy->getScalarType()))
    2612        6778 :     Assert(!DL.isNonIntegralPointerType(PTy),
    2613             :            "inttoptr not supported for non-integral pointers");
    2614             : 
    2615        6774 :   Assert(SrcTy->isVectorTy() == DestTy->isVectorTy(), "IntToPtr type mismatch",
    2616             :          &I);
    2617        6774 :   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        6774 :   visitInstruction(I);
    2624             : }
    2625             : 
    2626      311502 : void Verifier::visitBitCastInst(BitCastInst &I) {
    2627      623004 :   Assert(
    2628             :       CastInst::castIsValid(Instruction::BitCast, I.getOperand(0), I.getType()),
    2629             :       "Invalid bitcast", &I);
    2630      311502 :   visitInstruction(I);
    2631             : }
    2632             : 
    2633        1698 : void Verifier::visitAddrSpaceCastInst(AddrSpaceCastInst &I) {
    2634        1698 :   Type *SrcTy = I.getOperand(0)->getType();
    2635        1698 :   Type *DestTy = I.getType();
    2636             : 
    2637        1698 :   Assert(SrcTy->isPtrOrPtrVectorTy(), "AddrSpaceCast source must be a pointer",
    2638             :          &I);
    2639        1698 :   Assert(DestTy->isPtrOrPtrVectorTy(), "AddrSpaceCast result must be a pointer",
    2640             :          &I);
    2641        1698 :   Assert(SrcTy->getPointerAddressSpace() != DestTy->getPointerAddressSpace(),
    2642             :          "AddrSpaceCast must be between different address spaces", &I);
    2643        1698 :   if (SrcTy->isVectorTy())
    2644          37 :     Assert(SrcTy->getVectorNumElements() == DestTy->getVectorNumElements(),
    2645             :            "AddrSpaceCast vector pointer number of elements mismatch", &I);
    2646        1698 :   visitInstruction(I);
    2647             : }
    2648             : 
    2649             : /// visitPHINode - Ensure that a PHI node is well formed.
    2650             : ///
    2651       78549 : 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      179258 :   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      157097 :   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      400419 :   for (Value *IncValue : PN.incoming_values()) {
    2666      160936 :     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       78547 :   visitInstruction(PN);
    2673             : }
    2674             : 
    2675      585349 : void Verifier::verifyCallSite(CallSite CS) {
    2676      585349 :   Instruction *I = CS.getInstruction();
    2677             : 
    2678     1170709 :   Assert(CS.getCalledValue()->getType()->isPointerTy(),
    2679             :          "Called function must be a pointer!", I);
    2680             :   PointerType *FPTy = cast<PointerType>(CS.getCalledValue()->getType());
    2681             : 
    2682     1170698 :   Assert(FPTy->getElementType()->isFunctionTy(),
    2683             :          "Called function is not pointer to function type!", I);
    2684             : 
    2685      585349 :   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      585349 :   if (FTy->isVarArg())
    2692       41024 :     Assert(CS.arg_size() >= FTy->getNumParams(),
    2693             :            "Called function requires more parameters than were provided!", I);
    2694             :   else
    2695     1129674 :     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     2293682 :   for (unsigned i = 0, e = FTy->getNumParams(); i != e; ++i)
    2700     2245968 :     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      585349 :   AttributeList Attrs = CS.getAttributes();
    2705             : 
    2706     1170698 :   Assert(verifyAttributeCount(Attrs, CS.arg_size()),
    2707             :          "Attribute after last parameter!", I);
    2708             : 
    2709      585349 :   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      585347 :   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      585347 :   if (CS.hasInAllocaArgument()) {
    2725         175 :     Value *InAllocaArg = CS.getArgument(FTy->getNumParams() - 1);
    2726         175 :     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     3416656 :   for (unsigned i = 0, e = FTy->getNumParams(); i != e; ++i)
    2735     1122983 :     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      585345 :   if (FTy->isVarArg()) {
    2749             :     // FIXME? is 'nest' even legal here?
    2750             :     bool SawNest = false;
    2751             :     bool SawReturned = false;
    2752             : 
    2753      140237 :     for (unsigned Idx = 0; Idx < FTy->getNumParams(); ++Idx) {
    2754       33071 :       if (Attrs.hasParamAttribute(Idx, Attribute::Nest))
    2755             :         SawNest = true;
    2756       33071 :       if (Attrs.hasParamAttribute(Idx, Attribute::Returned))
    2757             :         SawReturned = true;
    2758             :     }
    2759             : 
    2760             :     // Check attributes on the varargs part.
    2761       90046 :     for (unsigned Idx = FTy->getNumParams(); Idx < CS.arg_size(); ++Idx) {
    2762       34769 :       Type *Ty = CS.getArgument(Idx)->getType();
    2763       34769 :       AttributeSet ArgAttrs = Attrs.getParamAttributes(Idx);
    2764       34769 :       verifyParameterAttrs(ArgAttrs, Ty, I);
    2765             : 
    2766       34769 :       if (ArgAttrs.hasAttribute(Attribute::Nest)) {
    2767          11 :         Assert(!SawNest, "More than one parameter has attribute nest!", I);
    2768             :         SawNest = true;
    2769             :       }
    2770             : 
    2771       34769 :       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       34770 :       Assert(!ArgAttrs.hasAttribute(Attribute::StructRet),
    2782             :              "Attribute 'sret' cannot be used for vararg call arguments!", I);
    2783             : 
    2784       34768 :       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      826565 :       !CS.getCalledFunction()->getName().startswith("llvm.")) {
    2793     1162007 :     for (Type *ParamTy : FTy->params()) {
    2794      439143 :       Assert(!ParamTy->isMetadataTy(),
    2795             :              "Function has metadata parameter but isn't an intrinsic", I);
    2796      439143 :       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      120801 :     Assert(!FTy->getReturnType()->isTokenTy(),
    2804             :            "Return type cannot be token for indirect call!");
    2805             : 
    2806             :   if (Function *F = CS.getCalledFunction())
    2807      524943 :     if (Intrinsic::ID ID = (Intrinsic::ID)F->getIntrinsicID())
    2808      299580 :       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      587897 :   for (unsigned i = 0, e = CS.getNumOperandBundles(); i < e; ++i) {
    2815        2557 :     OperandBundleUse BU = CS.getOperandBundleAt(i);
    2816        2557 :     uint32_t Tag = BU.getTagID();
    2817        2557 :     if (Tag == LLVMContext::OB_deopt) {
    2818        1295 :       Assert(!FoundDeoptBundle, "Multiple deopt operand bundles", I);
    2819             :       FoundDeoptBundle = true;
    2820        1265 :     } else if (Tag == LLVMContext::OB_gc_transition) {
    2821           7 :       Assert(!FoundGCTransitionBundle, "Multiple gc-transition operand bundles",
    2822             :              I);
    2823             :       FoundGCTransitionBundle = true;
    2824        1259 :     } else if (Tag == LLVMContext::OB_funclet) {
    2825        1074 :       Assert(!FoundFuncletBundle, "Multiple funclet operand bundles", I);
    2826             :       FoundFuncletBundle = true;
    2827        1074 :       Assert(BU.Inputs.size() == 1,
    2828             :              "Expected exactly one funclet bundle operand", I);
    2829        1074 :       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     1194225 :   if (I->getFunction()->getSubprogram() && CS.getCalledFunction() &&
    2839       23545 :       CS.getCalledFunction()->getSubprogram())
    2840        4950 :     AssertDI(I->getDebugLoc(), "inlinable function call in a function with "
    2841             :                                "debug info must have a !dbg location",
    2842             :              I);
    2843             : 
    2844      585338 :   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         996 :   if (L == R)
    2851             :     return true;
    2852             :   PointerType *PL = dyn_cast<PointerType>(L);
    2853             :   PointerType *PR = dyn_cast<PointerType>(R);
    2854          57 :   if (!PL || !PR)
    2855             :     return false;
    2856          55 :   return PL->getAddressSpace() == PR->getAddressSpace();
    2857             : }
    2858             : 
    2859        1048 : 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       15720 :   for (auto AK : ABIAttrs) {
    2866        7336 :     if (Attrs.hasParamAttribute(I, AK))
    2867         149 :       Copy.addAttribute(AK);
    2868             :   }
    2869        1048 :   if (Attrs.hasParamAttribute(I, Attribute::Alignment))
    2870           2 :     Copy.addAlignmentAttr(Attrs.getParamAlignment(I));
    2871        1048 :   return Copy;
    2872             : }
    2873             : 
    2874         517 : void Verifier::verifyMustTailCall(CallInst &CI) {
    2875         529 :   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         516 :   Function *F = CI.getParent()->getParent();
    2881             :   FunctionType *CallerTy = F->getFunctionType();
    2882         516 :   FunctionType *CalleeTy = CI.getFunctionType();
    2883         310 :   if (!CI.getCalledFunction() || !CI.getCalledFunction()->isIntrinsic()) {
    2884        1405 :     Assert(CallerTy->getNumParams() == CalleeTy->getNumParams(),
    2885             :            "cannot guarantee tail call due to mismatched parameter counts",
    2886             :            &CI);
    2887         949 :     for (int I = 0, E = CallerTy->getNumParams(); I != E; ++I) {
    2888         978 :       Assert(
    2889             :           isTypeCongruent(CallerTy->getParamType(I), CalleeTy->getParamType(I)),
    2890             :           "cannot guarantee tail call due to mismatched parameter types", &CI);
    2891             :     }
    2892             :   }
    2893         515 :   Assert(CallerTy->isVarArg() == CalleeTy->isVarArg(),
    2894             :          "cannot guarantee tail call due to mismatched varargs", &CI);
    2895        1071 :   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         513 :   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         511 :   AttributeList CallerAttrs = F->getAttributes();
    2905         511 :   AttributeList CalleeAttrs = CI.getAttributes();
    2906        1542 :   for (int I = 0, E = CallerTy->getNumParams(); I != E; ++I) {
    2907         524 :     AttrBuilder CallerABIAttrs = getParameterABIAttributes(I, CallerAttrs);
    2908         524 :     AttrBuilder CalleeABIAttrs = getParameterABIAttributes(I, CalleeAttrs);
    2909         532 :     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         507 :   Value *RetVal = &CI;
    2920             :   Instruction *Next = CI.getNextNode();
    2921             : 
    2922             :   // Handle the optional bitcast.
    2923         507 :   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         507 :   ReturnInst *Ret = dyn_cast_or_null<ReturnInst>(Next);
    2932         508 :   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      578503 : void Verifier::visitCallInst(CallInst &CI) {
    2939      578503 :   verifyCallSite(&CI);
    2940             : 
    2941      578503 :   if (CI.isMustTailCall())
    2942         517 :     verifyMustTailCall(CI);
    2943      578503 : }
    2944             : 
    2945        6846 : void Verifier::visitInvokeInst(InvokeInst &II) {
    2946        6846 :   verifyCallSite(&II);
    2947             : 
    2948             :   // Verify that the first non-PHI instruction of the unwind destination is an
    2949             :   // exception handling instruction.
    2950        6853 :   Assert(
    2951             :       II.getUnwindDest()->isEHPad(),
    2952             :       "The unwind destination does not have an exception handling instruction!",
    2953             :       &II);
    2954             : 
    2955        6839 :   visitTerminatorInst(II);
    2956             : }
    2957             : 
    2958             : /// visitBinaryOperator - Check that both arguments to the binary operator are
    2959             : /// of the same type!
    2960             : ///
    2961      576430 : void Verifier::visitBinaryOperator(BinaryOperator &B) {
    2962     1152860 :   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      576430 :   switch (B.getOpcode()) {
    2966             :   // Check that integer arithmetic operators are only used with
    2967             :   // integral operands.
    2968      281798 :   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      563596 :     Assert(B.getType()->isIntOrIntVectorTy(),
    2976             :            "Integer arithmetic operators only work with integral types!", &B);
    2977      281798 :     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      114979 :   case Instruction::FAdd:
    2985             :   case Instruction::FSub:
    2986             :   case Instruction::FMul:
    2987             :   case Instruction::FDiv:
    2988             :   case Instruction::FRem:
    2989      114979 :     Assert(B.getType()->isFPOrFPVectorTy(),
    2990             :            "Floating-point arithmetic operators only work with "
    2991             :            "floating-point types!",
    2992             :            &B);
    2993      114979 :     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      113667 :   case Instruction::And:
    3000             :   case Instruction::Or:
    3001             :   case Instruction::Xor:
    3002      227334 :     Assert(B.getType()->isIntOrIntVectorTy(),
    3003             :            "Logical operators only work with integral types!", &B);
    3004      113667 :     Assert(B.getType() == B.getOperand(0)->getType(),
    3005             :            "Logical operators must have same type for operands and result!",
    3006             :            &B);
    3007             :     break;
    3008       65986 :   case Instruction::Shl:
    3009             :   case Instruction::LShr:
    3010             :   case Instruction::AShr:
    3011      131972 :     Assert(B.getType()->isIntOrIntVectorTy(),
    3012             :            "Shifts only work with integral types!", &B);
    3013       65986 :     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      576430 :   visitInstruction(B);
    3021             : }
    3022             : 
    3023      212919 : void Verifier::visitICmpInst(ICmpInst &IC) {
    3024             :   // Check that the operands are the same type
    3025      212919 :   Type *Op0Ty = IC.getOperand(0)->getType();
    3026      212919 :   Type *Op1Ty = IC.getOperand(1)->getType();
    3027      212919 :   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      212919 :   Assert(Op0Ty->isIntOrIntVectorTy() || Op0Ty->isPtrOrPtrVectorTy(),
    3031             :          "Invalid operand types for ICmp instruction", &IC);
    3032             :   // Check that the predicate is valid.
    3033      212919 :   Assert(IC.isIntPredicate(),
    3034             :          "Invalid predicate in ICmp instruction!", &IC);
    3035             : 
    3036      212919 :   visitInstruction(IC);
    3037             : }
    3038             : 
    3039       29164 : void Verifier::visitFCmpInst(FCmpInst &FC) {
    3040             :   // Check that the operands are the same type
    3041       29164 :   Type *Op0Ty = FC.getOperand(0)->getType();
    3042       29164 :   Type *Op1Ty = FC.getOperand(1)->getType();
    3043       29164 :   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       29164 :   Assert(FC.isFPPredicate(),
    3050             :          "Invalid predicate in FCmp instruction!", &FC);
    3051             : 
    3052       29164 :   visitInstruction(FC);
    3053             : }
    3054             : 
    3055       78692 : void Verifier::visitExtractElementInst(ExtractElementInst &EI) {
    3056       78692 :   Assert(
    3057             :       ExtractElementInst::isValidOperands(EI.getOperand(0), EI.getOperand(1)),
    3058             :       "Invalid extractelement operands!", &EI);
    3059       78692 :   visitInstruction(EI);
    3060             : }
    3061             : 
    3062      101482 : void Verifier::visitInsertElementInst(InsertElementInst &IE) {
    3063      101482 :   Assert(InsertElementInst::isValidOperands(IE.getOperand(0), IE.getOperand(1),
    3064             :                                             IE.getOperand(2)),
    3065             :          "Invalid insertelement operands!", &IE);
    3066      101482 :   visitInstruction(IE);
    3067             : }
    3068             : 
    3069      136437 : void Verifier::visitShuffleVectorInst(ShuffleVectorInst &SV) {
    3070      136437 :   Assert(ShuffleVectorInst::isValidOperands(SV.getOperand(0), SV.getOperand(1),
    3071             :                                             SV.getOperand(2)),
    3072             :          "Invalid shufflevector operands!", &SV);
    3073      136437 :   visitInstruction(SV);
    3074             : }
    3075             : 
    3076      379194 : void Verifier::visitGetElementPtrInst(GetElementPtrInst &GEP) {
    3077             :   Type *TargetTy = GEP.getPointerOperandType()->getScalarType();
    3078             : 
    3079      379195 :   Assert(isa<PointerType>(TargetTy),
    3080             :          "GEP base pointer is not a vector or a vector of pointers", &GEP);
    3081      379194 :   Assert(GEP.getSourceElementType()->isSized(), "GEP into unsized type!", &GEP);
    3082             : 
    3083             :   SmallVector<Value*, 16> Idxs(GEP.idx_begin(), GEP.idx_end());
    3084      914698 :   Assert(all_of(
    3085             :       Idxs, [](Value* V) { return V->getType()->isIntOrIntVectorTy(); }),
    3086             :       "GEP indexes must be integers", &GEP);
    3087             :   Type *ElTy =
    3088      379193 :       GetElementPtrInst::getIndexedType(GEP.getSourceElementType(), Idxs);
    3089      379193 :   Assert(ElTy, "Invalid indices for GEP pointer type!", &GEP);
    3090             : 
    3091      758386 :   Assert(GEP.getType()->isPtrOrPtrVectorTy() &&
    3092             :              GEP.getResultElementType() == ElTy,
    3093             :          "GEP is not of right type for indices!", &GEP, ElTy);
    3094             : 
    3095      379193 :   if (GEP.getType()->isVectorTy()) {
    3096             :     // Additional checks for vector GEPs.
    3097             :     unsigned GEPWidth = GEP.getType()->getVectorNumElements();
    3098        1259 :     if (GEP.getPointerOperandType()->isVectorTy())
    3099         480 :       Assert(GEPWidth == GEP.getPointerOperandType()->getVectorNumElements(),
    3100             :              "Vector GEP result width doesn't match operand's", &GEP);
    3101        4571 :     for (Value *Idx : Idxs) {
    3102        1656 :       Type *IndexTy = Idx->getType();
    3103        1656 :       if (IndexTy->isVectorTy()) {
    3104             :         unsigned IndexWidth = IndexTy->getVectorNumElements();
    3105        1377 :         Assert(IndexWidth == GEPWidth, "Invalid GEP index vector width", &GEP);
    3106             :       }
    3107        1656 :       Assert(IndexTy->isIntOrIntVectorTy(),
    3108             :              "All GEP indices should be of integer type");
    3109             :     }
    3110             :   }
    3111      379193 :   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        8490 : void Verifier::visitRangeMetadata(Instruction &I, MDNode *Range, Type *Ty) {
    3119             :   assert(Range && Range == I.getMetadata(LLVMContext::MD_range) &&
    3120             :          "precondition violation");
    3121             : 
    3122        8490 :   unsigned NumOperands = Range->getNumOperands();
    3123        8508 :   Assert(NumOperands % 2 == 0, "Unfinished range!", Range);
    3124        8489 :   unsigned NumRanges = NumOperands / 2;
    3125        8491 :   Assert(NumRanges >= 1, "It should have at least one range!", Range);
    3126             : 
    3127       16960 :   ConstantRange LastRange(1); // Dummy initial value
    3128       25539 :   for (unsigned i = 0; i < NumRanges; ++i) {
    3129             :     ConstantInt *Low =
    3130       17076 :         mdconst::dyn_extract<ConstantInt>(Range->getOperand(2 * i));
    3131        8551 :     Assert(Low, "The lower limit must be an integer!", Low);
    3132             :     ConstantInt *High =
    3133       17074 :         mdconst::dyn_extract<ConstantInt>(Range->getOperand(2 * i + 1));
    3134        8538 :     Assert(High, "The upper limit must be an integer!", High);
    3135        8539 :     Assert(High->getType() == Low->getType() && High->getType() == Ty,
    3136             :            "Range types must match instruction type!", &I);
    3137             : 
    3138             :     APInt HighV = High->getValue();
    3139        8533 :     APInt LowV = Low->getValue();
    3140       34125 :     ConstantRange CurRange(LowV, HighV);
    3141        8542 :     Assert(!CurRange.isEmptySet() && !CurRange.isFullSet(),
    3142             :            "Range must not be empty!", Range);
    3143        8532 :     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       25578 :     LastRange = ConstantRange(LowV, HighV);
    3152             :   }
    3153        8475 :   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       26785 : void Verifier::checkAtomicMemAccessSize(Type *Ty, const Instruction *I) {
    3167       26785 :   unsigned Size = DL.getTypeSizeInBits(Ty);
    3168       26785 :   Assert(Size >= 8, "atomic memory access' size must be byte-sized", Ty, I);
    3169       26785 :   Assert(!(Size & (Size - 1)),
    3170             :          "atomic memory access' operand must have a power-of-two size", Ty, I);
    3171             : }
    3172             : 
    3173      761000 : void Verifier::visitLoadInst(LoadInst &LI) {
    3174      761000 :   PointerType *PTy = dyn_cast<PointerType>(LI.getOperand(0)->getType());
    3175           2 :   Assert(PTy, "Load operand must be a pointer.", &LI);
    3176      761000 :   Type *ElTy = LI.getType();
    3177      761000 :   Assert(LI.getAlignment() <= Value::MaximumAlignment,
    3178             :          "huge alignment values are unsupported", &LI);
    3179      761001 :   Assert(ElTy->isSized(), "loading unsized types is not allowed", &LI);
    3180      760999 :   if (LI.isAtomic()) {
    3181        3592 :     Assert(LI.getOrdering() != AtomicOrdering::Release &&
    3182             :                LI.getOrdering() != AtomicOrdering::AcquireRelease,
    3183             :            "Load cannot have Release ordering", &LI);
    3184        3592 :     Assert(LI.getAlignment() != 0,
    3185             :            "Atomic load must specify explicit alignment", &LI);
    3186        7186 :     Assert(ElTy->isIntegerTy() || ElTy->isPointerTy() ||
    3187             :                ElTy->isFloatingPointTy(),
    3188             :            "atomic load operand must have integer, pointer, or floating point "
    3189             :            "type!",
    3190             :            ElTy, &LI);
    3191        3591 :     checkAtomicMemAccessSize(ElTy, &LI);
    3192             :   } else {
    3193      757407 :     Assert(LI.getSyncScopeID() == SyncScope::System,
    3194             :            "Non-atomic load cannot have SynchronizationScope specified", &LI);
    3195             :   }
    3196             : 
    3197      760998 :   visitInstruction(LI);
    3198             : }
    3199             : 
    3200      662282 : void Verifier::visitStoreInst(StoreInst &SI) {
    3201      662282 :   PointerType *PTy = dyn_cast<PointerType>(SI.getOperand(1)->getType());
    3202           2 :   Assert(PTy, "Store operand must be a pointer.", &SI);
    3203      662282 :   Type *ElTy = PTy->getElementType();
    3204      662282 :   Assert(ElTy == SI.getOperand(0)->getType(),
    3205             :          "Stored value type does not match pointer operand type!", &SI, ElTy);
    3206      662282 :   Assert(SI.getAlignment() <= Value::MaximumAlignment,
    3207             :          "huge alignment values are unsupported", &SI);
    3208      662283 :   Assert(ElTy->isSized(), "storing unsized types is not allowed", &SI);
    3209      662281 :   if (SI.isAtomic()) {
    3210        2962 :     Assert(SI.getOrdering() != AtomicOrdering::Acquire &&
    3211             :                SI.getOrdering() != AtomicOrdering::AcquireRelease,
    3212             :            "Store cannot have Acquire ordering", &SI);
    3213        2962 :     Assert(SI.getAlignment() != 0,
    3214             :            "Atomic store must specify explicit alignment", &SI);
    3215        5926 :     Assert(ElTy->isIntegerTy() || ElTy->isPointerTy() ||
    3216             :                ElTy->isFloatingPointTy(),
    3217             :            "atomic store operand must have integer, pointer, or floating point "
    3218             :            "type!",
    3219             :            ElTy, &SI);
    3220        2961 :     checkAtomicMemAccessSize(ElTy, &SI);
    3221             :   } else {
    3222      659319 :     Assert(SI.getSyncScopeID() == SyncScope::System,
    3223             :            "Non-atomic store cannot have SynchronizationScope specified", &SI);
    3224             :   }
    3225      662280 :   visitInstruction(SI);
    3226             : }
    3227             : 
    3228             : /// Check that SwiftErrorVal is used as a swifterror argument in CS.
    3229         421 : void Verifier::verifySwiftErrorCallSite(CallSite CS,
    3230             :                                         const Value *SwiftErrorVal) {
    3231             :   unsigned Idx = 0;
    3232        1783 :   for (CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end();
    3233        1783 :        I != E; ++I, ++Idx) {
    3234        1362 :     if (*I == SwiftErrorVal) {
    3235         421 :       Assert(CS.paramHasAttr(Idx, Attribute::SwiftError),
    3236             :              "swifterror value when used in a callsite should be marked "
    3237             :              "with swifterror attribute",
    3238             :               SwiftErrorVal, CS);
    3239             :     }
    3240             :   }
    3241             : }
    3242             : 
    3243         809 : void Verifier::verifySwiftErrorValue(const Value *SwiftErrorVal) {
    3244             :   // Check that swifterror value is only used by loads, stores, or as
    3245             :   // a swifterror argument.
    3246        3805 :   for (const User *U : SwiftErrorVal->users()) {
    3247           3 :     Assert(isa<LoadInst>(U) || isa<StoreInst>(U) || isa<CallInst>(U) ||
    3248             :            isa<InvokeInst>(U),
    3249             :            "swifterror value can only be loaded and stored from, or "
    3250             :            "as a swifterror argument!",
    3251             :            SwiftErrorVal, U);
    3252             :     // If it is used by a store, check it is the second operand.
    3253             :     if (auto StoreI = dyn_cast<StoreInst>(U))
    3254         449 :       Assert(StoreI->getOperand(1) == SwiftErrorVal,
    3255             :              "swifterror value should be the second operand when used "
    3256             :              "by stores", SwiftErrorVal, U);
    3257             :     if (auto CallI = dyn_cast<CallInst>(U))
    3258         840 :       verifySwiftErrorCallSite(const_cast<CallInst*>(CallI), SwiftErrorVal);
    3259        1093 :     if (auto II = dyn_cast<InvokeInst>(U))
    3260           2 :       verifySwiftErrorCallSite(const_cast<InvokeInst*>(II), SwiftErrorVal);
    3261             :   }
    3262             : }
    3263             : 
    3264      392041 : void Verifier::visitAllocaInst(AllocaInst &AI) {
    3265             :   SmallPtrSet<Type*, 4> Visited;
    3266             :   PointerType *PTy = AI.getType();
    3267             :   // TODO: Relax this restriction?
    3268      392058 :   Assert(PTy->getAddressSpace() == DL.getAllocaAddrSpace(),
    3269             :          "Allocation instruction pointer not in the stack address space!",
    3270             :          &AI);
    3271      392027 :   Assert(AI.getAllocatedType()->isSized(&Visited),
    3272             :          "Cannot allocate unsized type", &AI);
    3273      784042 :   Assert(AI.getArraySize()->getType()->isIntegerTy(),
    3274             :          "Alloca array size must have integer type", &AI);
    3275      392021 :   Assert(AI.getAlignment() <= Value::MaximumAlignment,
    3276             :          "huge alignment values are unsupported", &AI);
    3277             : 
    3278      392021 :   if (AI.isSwiftError()) {
    3279         268 :     verifySwiftErrorValue(&AI);
    3280             :   }
    3281             : 
    3282      392021 :   visitInstruction(AI);
    3283             : }
    3284             : 
    3285        4095 : void Verifier::visitAtomicCmpXchgInst(AtomicCmpXchgInst &CXI) {
    3286             : 
    3287             :   // FIXME: more conditions???
    3288        4095 :   Assert(CXI.getSuccessOrdering() != AtomicOrdering::NotAtomic,
    3289             :          "cmpxchg instructions must be atomic.", &CXI);
    3290        4095 :   Assert(CXI.getFailureOrdering() != AtomicOrdering::NotAtomic,
    3291             :          "cmpxchg instructions must be atomic.", &CXI);
    3292        4095 :   Assert(CXI.getSuccessOrdering() != AtomicOrdering::Unordered,
    3293             :          "cmpxchg instructions cannot be unordered.", &CXI);
    3294        4095 :   Assert(CXI.getFailureOrdering() != AtomicOrdering::Unordered,
    3295             :          "cmpxchg instructions cannot be unordered.", &CXI);
    3296        4095 :   Assert(!isStrongerThan(CXI.getFailureOrdering(), CXI.getSuccessOrdering()),
    3297             :          "cmpxchg instructions failure argument shall be no stronger than the "
    3298             :          "success argument",
    3299             :          &CXI);
    3300        4095 :   Assert(CXI.getFailureOrdering() != AtomicOrdering::Release &&
    3301             :              CXI.getFailureOrdering() != AtomicOrdering::AcquireRelease,
    3302             :          "cmpxchg failure ordering cannot include release semantics", &CXI);
    3303             : 
    3304        4095 :   PointerType *PTy = dyn_cast<PointerType>(CXI.getOperand(0)->getType());
    3305           0 :   Assert(PTy, "First cmpxchg operand must be a pointer.", &CXI);
    3306        4095 :   Type *ElTy = PTy->getElementType();
    3307        4095 :   Assert(ElTy->isIntegerTy() || ElTy->isPointerTy(),
    3308             :         "cmpxchg operand must have integer or pointer type",
    3309             :          ElTy, &CXI);
    3310        4095 :   checkAtomicMemAccessSize(ElTy, &CXI);
    3311        4095 :   Assert(ElTy == CXI.getOperand(1)->getType(),
    3312             :          "Expected value type does not match pointer operand type!", &CXI,
    3313             :          ElTy);
    3314        4095 :   Assert(ElTy == CXI.getOperand(2)->getType(),
    3315             :          "Stored value type does not match pointer operand type!", &CXI, ElTy);
    3316        4095 :   visitInstruction(CXI);
    3317             : }
    3318             : 
    3319       16138 : void Verifier::visitAtomicRMWInst(AtomicRMWInst &RMWI) {
    3320       16138 :   Assert(RMWI.getOrdering() != AtomicOrdering::NotAtomic,
    3321             :          "atomicrmw instructions must be atomic.", &RMWI);
    3322       16138 :   Assert(RMWI.getOrdering() != AtomicOrdering::Unordered,
    3323             :          "atomicrmw instructions cannot be unordered.", &RMWI);
    3324       16138 :   PointerType *PTy = dyn_cast<PointerType>(RMWI.getOperand(0)->getType());
    3325           0 :   Assert(PTy, "First atomicrmw operand must be a pointer.", &RMWI);
    3326       16138 :   Type *ElTy = PTy->getElementType();
    3327       16138 :   Assert(ElTy->isIntegerTy(), "atomicrmw operand must have integer type!",
    3328             :          &RMWI, ElTy);
    3329       16138 :   checkAtomicMemAccessSize(ElTy, &RMWI);
    3330       16138 :   Assert(ElTy == RMWI.getOperand(1)->getType(),
    3331             :          "Argument value type does not match pointer operand type!", &RMWI,
    3332             :          ElTy);
    3333       16138 :   Assert(AtomicRMWInst::FIRST_BINOP <= RMWI.getOperation() &&
    3334             :              RMWI.getOperation() <= AtomicRMWInst::LAST_BINOP,
    3335             :          "Invalid binary operation!", &RMWI);
    3336       16138 :   visitInstruction(RMWI);
    3337             : }
    3338             : 
    3339        1854 : void Verifier::visitFenceInst(FenceInst &FI) {
    3340             :   const AtomicOrdering Ordering = FI.getOrdering();
    3341        1854 :   Assert(Ordering == AtomicOrdering::Acquire ||
    3342             :              Ordering == AtomicOrdering::Release ||
    3343             :              Ordering == AtomicOrdering::AcquireRelease ||
    3344             :              Ordering == AtomicOrdering::SequentiallyConsistent,
    3345             :          "fence instructions may only have acquire, release, acq_rel, or "
    3346             :          "seq_cst ordering.",
    3347             :          &FI);
    3348        1854 :   visitInstruction(FI);
    3349             : }
    3350             : 
    3351       29907 : void Verifier::visitExtractValueInst(ExtractValueInst &EVI) {
    3352       29907 :   Assert(ExtractValueInst::getIndexedType(EVI.getAggregateOperand()->getType(),
    3353             :                                           EVI.getIndices()) == EVI.getType(),
    3354             :          "Invalid ExtractValueInst operands!", &EVI);
    3355             : 
    3356       29907 :   visitInstruction(EVI);
    3357             : }
    3358             : 
    3359        5628 : void Verifier::visitInsertValueInst(InsertValueInst &IVI) {
    3360       11256 :   Assert(ExtractValueInst::getIndexedType(IVI.getAggregateOperand()->getType(),
    3361             :                                           IVI.getIndices()) ==
    3362             :              IVI.getOperand(1)->getType(),
    3363             :          "Invalid InsertValueInst operands!", &IVI);
    3364             : 
    3365        5628 :   visitInstruction(IVI);
    3366             : }
    3367             : 
    3368             : static Value *getParentPad(Value *EHPad) {
    3369             :   if (auto *FPI = dyn_cast<FuncletPadInst>(EHPad))
    3370             :     return FPI->getParentPad();
    3371             : 
    3372             :   return cast<CatchSwitchInst>(EHPad)->getParentPad();
    3373             : }
    3374             : 
    3375        6440 : void Verifier::visitEHPadPredecessors(Instruction &I) {
    3376             :   assert(I.isEHPad());
    3377             : 
    3378        6440 :   BasicBlock *BB = I.getParent();
    3379        6440 :   Function *F = BB->getParent();
    3380             : 
    3381       11353 :   Assert(BB != &F->getEntryBlock(), "EH pad cannot be in entry block.", &I);
    3382             : 
    3383        6440 :   if (auto *LPI = dyn_cast<LandingPadInst>(&I)) {
    3384             :     // The landingpad instruction defines its parent as a landing pad block. The
    3385             :     // landing pad block may be branched to only by the unwind edge of an
    3386             :     // invoke.
    3387       13574 :     for (BasicBlock *PredBB : predecessors(BB)) {
    3388             :       const auto *II = dyn_cast<InvokeInst>(PredBB->getTerminator());
    3389       10680 :       Assert(II && II->getUnwindDest() == BB && II->getNormalDest() != BB,
    3390             :              "Block containing LandingPadInst must be jumped to "
    3391             :              "only by the unwind edge of an invoke.",
    3392             :              LPI);
    3393             :     }
    3394        4117 :     return;
    3395             :   }
    3396        2322 :   if (auto *CPI = dyn_cast<CatchPadInst>(&I)) {
    3397         787 :     if (!pred_empty(BB))
    3398        2362 :       Assert(BB->getUniquePredecessor() == CPI->getCatchSwitch()->getParent(),
    3399             :              "Block containg CatchPadInst must be jumped to "
    3400             :              "only by its catchswitch.",
    3401             :              CPI);
    3402        1574 :     Assert(BB != CPI->getCatchSwitch()->getUnwindDest(),
    3403             :            "Catchswitch cannot unwind to one of its catchpads",
    3404             :            CPI->getCatchSwitch(), CPI);
    3405             :     return;
    3406             :   }
    3407             : 
    3408             :   // Verify that each pred has a legal terminator with a legal to/from EH
    3409             :   // pad relationship.
    3410        1535 :   Instruction *ToPad = &I;
    3411             :   Value *ToPadParent = getParentPad(ToPad);
    3412        4938 :   for (BasicBlock *PredBB : predecessors(BB)) {
    3413        1876 :     TerminatorInst *TI = PredBB->getTerminator();
    3414             :     Value *FromPad;
    3415        1876 :     if (auto *II = dyn_cast<InvokeInst>(TI)) {
    3416        3000 :       Assert(II->getUnwindDest() == BB && II->getNormalDest() != BB,
    3417             :              "EH pad must be jumped to via an unwind edge", ToPad, II);
    3418        1499 :       if (auto Bundle = II->getOperandBundle(LLVMContext::OB_funclet))
    3419         360 :         FromPad = Bundle->Inputs[0];
    3420             :       else
    3421        1139 :         FromPad = ConstantTokenNone::get(II->getContext());
    3422         377 :     } else if (auto *CRI = dyn_cast<CleanupReturnInst>(TI)) {
    3423         198 :       FromPad = CRI->getOperand(0);
    3424         202 :       Assert(FromPad != ToPadParent, "A cleanupret must exit its cleanup", CRI);
    3425             :     } else if (auto *CSI = dyn_cast<CatchSwitchInst>(TI)) {
    3426         179 :       FromPad = CSI;
    3427             :     } else {
    3428           0 :       Assert(false, "EH pad must be jumped to via an unwind edge", ToPad, TI);
    3429             :     }
    3430             : 
    3431             :     // The edge may exit from zero or more nested pads.
    3432             :     SmallSet<Value *, 8> Seen;
    3433        1328 :     for (;; FromPad = getParentPad(FromPad)) {
    3434        2541 :       Assert(FromPad != ToPad,
    3435             :              "EH pad cannot handle exceptions raised within it", FromPad, TI);
    3436        2535 :       if (FromPad == ToPadParent) {
    3437             :         // This is a legal unwind edge.
    3438             :         break;
    3439             :       }
    3440         669 :       Assert(!isa<ConstantTokenNone>(FromPad),
    3441             :              "A single unwind edge may only enter one EH pad", TI);
    3442         666 :       Assert(Seen.insert(FromPad).second,
    3443             :              "EH pad jumps through a cycle of pads", FromPad);
    3444             :     }
    3445             :   }
    3446             : }
    3447             : 
    3448        4118 : void Verifier::visitLandingPadInst(LandingPadInst &LPI) {
    3449             :   // The landingpad instruction is ill-formed if it doesn't have any clauses and
    3450             :   // isn't a cleanup.
    3451        6182 :   Assert(LPI.getNumClauses() > 0 || LPI.isCleanup(),
    3452             :          "LandingPadInst needs at least one clause or to be a cleanup.", &LPI);
    3453             : 
    3454        4118 :   visitEHPadPredecessors(LPI);
    3455             : 
    3456        4118 :   if (!LandingPadResultTy)
    3457        2672 :     LandingPadResultTy = LPI.getType();
    3458             :   else
    3459        1447 :     Assert(LandingPadResultTy == LPI.getType(),
    3460             :            "The landingpad instruction should have a consistent result type "
    3461             :            "inside a function.",
    3462             :            &LPI);
    3463             : 
    3464        4117 :   Function *F = LPI.getParent()->getParent();
    3465        4117 :   Assert(F->hasPersonalityFn(),
    3466             :          "LandingPadInst needs to be in a function with a personality.", &LPI);
    3467             : 
    3468             :   // The landingpad instruction must be the first non-PHI instruction in the
    3469             :   // block.
    3470        4117 :   Assert(LPI.getParent()->getLandingPadInst() == &LPI,
    3471             :          "LandingPadInst not the first non-PHI instruction in the block.",
    3472             :          &LPI);
    3473             : 
    3474        8533 :   for (unsigned i = 0, e = LPI.getNumClauses(); i < e; ++i) {
    3475             :     Constant *Clause = LPI.getClause(i);
    3476        2208 :     if (LPI.isCatch(i)) {
    3477        2102 :       Assert(isa<PointerType>(Clause->getType()),
    3478             :              "Catch operand does not have pointer type!", &LPI);
    3479             :     } else {
    3480             :       Assert(LPI.isFilter(i), "Clause is neither catch nor filter!", &LPI);
    3481         106 :       Assert(isa<ConstantArray>(Clause) || isa<ConstantAggregateZero>(Clause),
    3482             :              "Filter operand is not an array of constants!", &LPI);
    3483             :     }
    3484             :   }
    3485             : 
    3486        4117 :   visitInstruction(LPI);
    3487             : }
    3488             : 
    3489         962 : void Verifier::visitResumeInst(ResumeInst &RI) {
    3490        1925 :   Assert(RI.getFunction()->hasPersonalityFn(),
    3491             :          "ResumeInst needs to be in a function with a personality.", &RI);
    3492             : 
    3493         961 :   if (!LandingPadResultTy)
    3494           2 :     LandingPadResultTy = RI.getValue()->getType();
    3495             :   else
    3496         959 :     Assert(LandingPadResultTy == RI.getValue()->getType(),
    3497             :            "The resume instruction should have a consistent result type "
    3498             :            "inside a function.",
    3499             :            &RI);
    3500             : 
    3501         961 :   visitTerminatorInst(RI);
    3502             : }
    3503             : 
    3504         789 : void Verifier::visitCatchPadInst(CatchPadInst &CPI) {
    3505         789 :   BasicBlock *BB = CPI.getParent();
    3506             : 
    3507         789 :   Function *F = BB->getParent();
    3508         790 :   Assert(F->hasPersonalityFn(),
    3509             :          "CatchPadInst needs to be in a function with a personality.", &CPI);
    3510             : 
    3511           2 :   Assert(isa<CatchSwitchInst>(CPI.getParentPad()),
    3512             :          "CatchPadInst needs to be directly nested in a CatchSwitchInst.",
    3513             :          CPI.getParentPad());
    3514             : 
    3515             :   // The catchpad instruction must be the first non-PHI instruction in the
    3516             :   // block.
    3517         787 :   Assert(BB->getFirstNonPHI() == &CPI,
    3518             :          "CatchPadInst not the first non-PHI instruction in the block.", &CPI);
    3519             : 
    3520         787 :   visitEHPadPredecessors(CPI);
    3521         787 :   visitFuncletPadInst(CPI);
    3522             : }
    3523             : 
    3524         587 : void Verifier::visitCatchReturnInst(CatchReturnInst &CatchReturn) {
    3525           4 :   Assert(isa<CatchPadInst>(CatchReturn.getOperand(0)),
    3526             :          "CatchReturnInst needs to be provided a CatchPad", &CatchReturn,
    3527             :          CatchReturn.getOperand(0));
    3528             : 
    3529         585 :   visitTerminatorInst(CatchReturn);
    3530             : }
    3531             : 
    3532         807 : void Verifier::visitCleanupPadInst(CleanupPadInst &CPI) {
    3533         807 :   BasicBlock *BB = CPI.getParent();
    3534             : 
    3535         807 :   Function *F = BB->getParent();
    3536         808 :   Assert(F->hasPersonalityFn(),
    3537             :          "CleanupPadInst needs to be in a function with a personality.", &CPI);
    3538             : 
    3539             :   // The cleanuppad instruction must be the first non-PHI instruction in the
    3540             :   // block.
    3541         806 :   Assert(BB->getFirstNonPHI() == &CPI,
    3542             :          "CleanupPadInst not the first non-PHI instruction in the block.",
    3543             :          &CPI);
    3544             : 
    3545             :   auto *ParentPad = CPI.getParentPad();
    3546         808 :   Assert(isa<ConstantTokenNone>(ParentPad) || isa<FuncletPadInst>(ParentPad),
    3547             :          "CleanupPadInst has an invalid parent.", &CPI);
    3548             : 
    3549         805 :   visitEHPadPredecessors(CPI);
    3550         805 :   visitFuncletPadInst(CPI);
    3551             : }
    3552             : 
    3553        1592 : void Verifier::visitFuncletPadInst(FuncletPadInst &FPI) {
    3554        1592 :   User *FirstUser = nullptr;
    3555             :   Value *FirstUnwindPad = nullptr;
    3556        3184 :   SmallVector<FuncletPadInst *, 8> Worklist({&FPI});
    3557             :   SmallSet<FuncletPadInst *, 8> Seen;
    3558             : 
    3559        3422 :   while (!Worklist.empty()) {
    3560        1833 :     FuncletPadInst *CurrentPad = Worklist.pop_back_val();
    3561        1837 :     Assert(Seen.insert(CurrentPad).second,
    3562             :            "FuncletPadInst must not be nested within itself", CurrentPad);
    3563             :     Value *UnresolvedAncestorPad = nullptr;
    3564        9488 :     for (User *U : CurrentPad->users()) {
    3565             :       BasicBlock *UnwindDest;
    3566             :       if (auto *CRI = dyn_cast<CleanupReturnInst>(U)) {
    3567             :         UnwindDest = CRI->getUnwindDest();
    3568             :       } else if (auto *CSI = dyn_cast<CatchSwitchInst>(U)) {
    3569             :         // We allow catchswitch unwind to caller to nest
    3570             :         // within an outer pad that unwinds somewhere else,
    3571             :         // because catchswitch doesn't have a nounwind variant.
    3572             :         // See e.g. SimplifyCFGOpt::SimplifyUnreachable.
    3573         143 :         if (CSI->unwindsToCaller())
    3574         102 :           continue;
    3575             :         UnwindDest = CSI->getUnwindDest();
    3576             :       } else if (auto *II = dyn_cast<InvokeInst>(U)) {
    3577             :         UnwindDest = II->getUnwindDest();
    3578         873 :       } else if (isa<CallInst>(U)) {
    3579             :         // Calls which don't unwind may be found inside funclet
    3580             :         // pads that unwind somewhere else.  We don't *require*
    3581             :         // such calls to be annotated nounwind.
    3582         873 :         continue;
    3583         828 :       } else if (auto *CPI = dyn_cast<CleanupPadInst>(U)) {
    3584             :         // The unwind dest for a cleanup can only be found by
    3585             :         // recursive search.  Add it to the worklist, and we'll
    3586             :         // search for its first use that determines where it unwinds.
    3587         243 :         Worklist.push_back(CPI);
    3588         243 :         continue;
    3589             :       } else {
    3590           0 :         Assert(isa<CatchReturnInst>(U), "Bogus funclet pad use", U);
    3591         585 :         continue;
    3592             :       }
    3593             : 
    3594             :       Value *UnwindPad;
    3595             :       bool ExitsFPI;
    3596         767 :       if (UnwindDest) {
    3597             :         UnwindPad = UnwindDest->getFirstNonPHI();
    3598           1 :         if (!cast<Instruction>(UnwindPad)->isEHPad())
    3599           1 :           continue;
    3600             :         Value *UnwindParent = getParentPad(UnwindPad);
    3601             :         // Ignore unwind edges that don't exit CurrentPad.
    3602         766 :         if (UnwindParent == CurrentPad)
    3603         340 :           continue;
    3604             :         // Determine whether the original funclet pad is exited,
    3605             :         // and if we are scanning nested pads determine how many
    3606             :         // of them are exited so we can stop searching their
    3607             :         // children.
    3608             :         Value *ExitedPad = CurrentPad;
    3609             :         ExitsFPI = false;
    3610             :         do {
    3611         495 :           if (ExitedPad == &FPI) {
    3612             :             ExitsFPI = true;
    3613             :             // Now we can resolve any ancestors of CurrentPad up to
    3614             :             // FPI, but not including FPI since we need to make sure
    3615             :             // to check all direct users of FPI for consistency.
    3616             :             UnresolvedAncestorPad = &FPI;
    3617             :             break;
    3618             :           }
    3619             :           Value *ExitedParent = getParentPad(ExitedPad);
    3620         111 :           if (ExitedParent == UnwindParent) {
    3621             :             // ExitedPad is the ancestor-most pad which this unwind
    3622             :             // edge exits, so we can resolve up to it, meaning that
    3623             :             // ExitedParent is the first ancestor still unresolved.
    3624             :             UnresolvedAncestorPad = ExitedParent;
    3625             :             break;
    3626             :           }
    3627             :           ExitedPad = ExitedParent;
    3628          69 :         } while (!isa<ConstantTokenNone>(ExitedPad));
    3629             :       } else {
    3630             :         // Unwinding to caller exits all pads.
    3631         399 :         UnwindPad = ConstantTokenNone::get(FPI.getContext());
    3632             :         ExitsFPI = true;
    3633             :         UnresolvedAncestorPad = &FPI;
    3634             :       }
    3635             : 
    3636         825 :       if (ExitsFPI) {
    3637             :         // This unwind edge exits FPI.  Make sure it agrees with other
    3638             :         // such edges.
    3639         783 :         if (FirstUser) {
    3640          83 :           Assert(UnwindPad == FirstUnwindPad, "Unwind edges out of a funclet "
    3641             :                                               "pad must have the same unwind "
    3642             :                                               "dest",
    3643             :                  &FPI, U, FirstUser);
    3644             :         } else {
    3645         702 :           FirstUser = U;
    3646             :           FirstUnwindPad = UnwindPad;
    3647             :           // Record cleanup sibling unwinds for verifySiblingFuncletUnwinds
    3648        1579 :           if (isa<CleanupPadInst>(&FPI) && !isa<ConstantTokenNone>(UnwindPad) &&
    3649             :               getParentPad(UnwindPad) == getParentPad(&FPI))
    3650         198 :             SiblingFuncletInfo[&FPI] = cast<TerminatorInst>(U);
    3651             :         }
    3652             :       }
    3653             :       // Make sure we visit all uses of FPI, but for nested pads stop as
    3654             :       // soon as we know where they unwind to.
    3655         823 :       if (CurrentPad != &FPI)
    3656             :         break;
    3657             :     }
    3658        1830 :     if (UnresolvedAncestorPad) {
    3659         770 :       if (CurrentPad == UnresolvedAncestorPad) {
    3660             :         // When CurrentPad is FPI itself, we don't mark it as resolved even if
    3661             :         // we've found an unwind edge that exits it, because we need to verify
    3662             :         // all direct uses of FPI.
    3663             :         assert(CurrentPad == &FPI);
    3664         658 :         continue;
    3665             :       }
    3666             :       // Pop off the worklist any nested pads that we've found an unwind
    3667             :       // destination for.  The pads on the worklist are the uncles,
    3668             :       // great-uncles, etc. of CurrentPad.  We've found an unwind destination
    3669             :       // for all ancestors of CurrentPad up to but not including
    3670             :       // UnresolvedAncestorPad.
    3671             :       Value *ResolvedPad = CurrentPad;
    3672         114 :       while (!Worklist.empty()) {
    3673          40 :         Value *UnclePad = Worklist.back();
    3674             :         Value *AncestorPad = getParentPad(UnclePad);
    3675             :         // Walk ResolvedPad up the ancestor list until we either find the
    3676             :         // uncle's parent or the last resolved ancestor.
    3677          46 :         while (ResolvedPad != AncestorPad) {
    3678             :           Value *ResolvedParent = getParentPad(ResolvedPad);
    3679          44 :           if (ResolvedParent == UnresolvedAncestorPad) {
    3680             :             break;
    3681             :           }
    3682             :           ResolvedPad = ResolvedParent;
    3683             :         }
    3684             :         // If the resolved ancestor search didn't find the uncle's parent,
    3685             :         // then the uncle is not yet resolved.
    3686          40 :         if (ResolvedPad != AncestorPad)
    3687             :           break;
    3688             :         // This uncle is resolved, so pop it from the worklist.
    3689             :         Worklist.pop_back();
    3690             :       }
    3691             :     }
    3692             :   }
    3693             : 
    3694        1589 :   if (FirstUnwindPad) {
    3695         700 :     if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(FPI.getParentPad())) {
    3696             :       BasicBlock *SwitchUnwindDest = CatchSwitch->getUnwindDest();
    3697             :       Value *SwitchUnwindPad;
    3698             :       if (SwitchUnwindDest)
    3699             :         SwitchUnwindPad = SwitchUnwindDest->getFirstNonPHI();
    3700             :       else
    3701          17 :         SwitchUnwindPad = ConstantTokenNone::get(FPI.getContext());
    3702          74 :       Assert(SwitchUnwindPad == FirstUnwindPad,
    3703             :              "Unwind edges out of a catch must have the same unwind dest as "
    3704             :              "the parent catchswitch",
    3705             :              &FPI, FirstUser, CatchSwitch);
    3706             :     }
    3707             :   }
    3708             : 
    3709        1586 :   visitInstruction(FPI);
    3710             : }
    3711             : 
    3712         733 : void Verifier::visitCatchSwitchInst(CatchSwitchInst &CatchSwitch) {
    3713         733 :   BasicBlock *BB = CatchSwitch.getParent();
    3714             : 
    3715         733 :   Function *F = BB->getParent();
    3716         737 :   Assert(F->hasPersonalityFn(),
    3717             :          "CatchSwitchInst needs to be in a function with a personality.",
    3718             :          &CatchSwitch);
    3719             : 
    3720             :   // The catchswitch instruction must be the first non-PHI instruction in the
    3721             :   // block.
    3722         732 :   Assert(BB->getFirstNonPHI() == &CatchSwitch,
    3723             :          "CatchSwitchInst not the first non-PHI instruction in the block.",
    3724             :          &CatchSwitch);
    3725             : 
    3726         732 :   auto *ParentPad = CatchSwitch.getParentPad();
    3727         734 :   Assert(isa<ConstantTokenNone>(ParentPad) || isa<FuncletPadInst>(ParentPad),
    3728             :          "CatchSwitchInst has an invalid parent.", ParentPad);
    3729             : 
    3730             :   if (BasicBlock *UnwindDest = CatchSwitch.getUnwindDest()) {
    3731             :     Instruction *I = UnwindDest->getFirstNonPHI();
    3732         182 :     Assert(I->isEHPad() && !isa<LandingPadInst>(I),
    3733             :            "CatchSwitchInst must unwind to an EH block which is not a "
    3734             :            "landingpad.",
    3735             :            &CatchSwitch);
    3736             : 
    3737             :     // Record catchswitch sibling unwinds for verifySiblingFuncletUnwinds
    3738         182 :     if (getParentPad(I) == ParentPad)
    3739         157 :       SiblingFuncletInfo[&CatchSwitch] = &CatchSwitch;
    3740             :   }
    3741             : 
    3742         731 :   Assert(CatchSwitch.getNumHandlers() != 0,
    3743             :          "CatchSwitchInst cannot have empty handler list", &CatchSwitch);
    3744             : 
    3745        2304 :   for (BasicBlock *Handler : CatchSwitch.handlers()) {
    3746         788 :     Assert(isa<CatchPadInst>(Handler->getFirstNonPHI()),
    3747             :            "CatchSwitchInst handlers must be catchpads", &CatchSwitch, Handler);
    3748             :   }
    3749             : 
    3750         730 :   visitEHPadPredecessors(CatchSwitch);
    3751         730 :   visitTerminatorInst(CatchSwitch);
    3752             : }
    3753             : 
    3754         577 : void Verifier::visitCleanupReturnInst(CleanupReturnInst &CRI) {
    3755           6 :   Assert(isa<CleanupPadInst>(CRI.getOperand(0)),
    3756             :          "CleanupReturnInst needs to be provided a CleanupPad", &CRI,
    3757             :          CRI.getOperand(0));
    3758             : 
    3759         197 :   if (BasicBlock *UnwindDest = CRI.getUnwindDest()) {
    3760             :     Instruction *I = UnwindDest->getFirstNonPHI();
    3761         197 :     Assert(I->isEHPad() && !isa<LandingPadInst>(I),
    3762             :            "CleanupReturnInst must unwind to an EH block which is not a "
    3763             :            "landingpad.",
    3764             :            &CRI);
    3765             :   }
    3766             : 
    3767         574 :   visitTerminatorInst(CRI);
    3768             : }
    3769             : 
    3770     4568274 : void Verifier::verifyDominatesUse(Instruction &I, unsigned i) {
    3771     9136548 :   Instruction *Op = cast<Instruction>(I.getOperand(i));
    3772             :   // If the we have an invalid invoke, don't try to compute the dominance.
    3773             :   // We already reject it in the invoke specific checks and the dominance
    3774             :   // computation doesn't handle multiple edges.
    3775             :   if (InvokeInst *II = dyn_cast<InvokeInst>(Op)) {
    3776        1198 :     if (II->getNormalDest() == II->getUnwindDest())
    3777     4074580 :       return;
    3778             :   }
    3779             : 
    3780             :   // Quick check whether the def has already been encountered in the same block.
    3781             :   // PHI nodes are not checked to prevent accepting preceeding PHIs, because PHI
    3782             :   // uses are defined to happen on the incoming edge, not at the instruction.
    3783             :   //
    3784             :   // FIXME: If this operand is a MetadataAsValue (wrapping a LocalAsMetadata)
    3785             :   // wrapping an SSA value, assert that we've already encountered it.  See
    3786             :   // related FIXME in Mapper::mapLocalAsMetadata in ValueMapper.cpp.
    3787     4568272 :   if (!isa<PHINode>(I) && InstsInThisBlock.count(Op))
    3788             :     return;
    3789             : 
    3790             :   const Use &U = I.getOperandUse(i);
    3791      493718 :   Assert(DT.dominates(Op, U),
    3792             :          "Instruction does not dominate all uses!", Op, &I);
    3793             : }
    3794             : 
    3795          80 : void Verifier::visitDereferenceableMetadata(Instruction& I, MDNode* MD) {
    3796         162 :   Assert(I.getType()->isPointerTy(), "dereferenceable, dereferenceable_or_null "
    3797             :          "apply only to pointer types", &I);
    3798          80 :   Assert(isa<LoadInst>(I),
    3799             :          "dereferenceable, dereferenceable_or_null apply only to load"
    3800             :          " instructions, use attributes for calls or invokes", &I);
    3801          78 :   Assert(MD->getNumOperands() == 1, "dereferenceable, dereferenceable_or_null "
    3802             :          "take one operand!", &I);
    3803             :   ConstantInt *CI = mdconst::dyn_extract<ConstantInt>(MD->getOperand(0));
    3804          76 :   Assert(CI && CI->getType()->isIntegerTy(64), "dereferenceable, "
    3805             :          "dereferenceable_or_null metadata value must be an i64!", &I);
    3806             : }
    3807             : 
    3808             : /// verifyInstruction - Verify that an instruction is well formed.
    3809             : ///
    3810     5810873 : void Verifier::visitInstruction(Instruction &I) {
    3811     5810873 :   BasicBlock *BB = I.getParent();
    3812     5810873 :   Assert(BB, "Instruction not embedded in basic block!", &I);
    3813             : 
    3814     5810873 :   if (!isa<PHINode>(I)) {   // Check that non-phi nodes are not self referential
    3815    10151782 :     for (User *U : I.users()) {
    3816     4419458 :       Assert(U != (User *)&I || !DT.isReachableFromEntry(BB),
    3817             :              "Only PHI nodes may reference their own value!", &I);
    3818             :     }
    3819             :   }
    3820             : 
    3821             :   // Check that void typed values don't have names
    3822    13662849 :   Assert(!I.getType()->isVoidTy() || !I.hasName(),
    3823             :          "Instruction has a name, but provides a void value!", &I);
    3824             : 
    3825             :   // Check that the return value of the instruction is either void or a legal
    3826             :   // value type.
    3827     5810872 :   Assert(I.getType()->isVoidTy() || I.getType()->isFirstClassType(),
    3828             :          "Instruction returns a non-scalar type!", &I);
    3829             : 
    3830             :   // Check that the instruction doesn't produce metadata. Calls are already
    3831             :   // checked against the callee type.
    3832     5810872 :   Assert(!I.getType()->isMetadataTy() || isa<CallInst>(I) || isa<InvokeInst>(I),
    3833             :          "Invalid use of metadata!", &I);
    3834             : 
    3835             :   // Check that all uses of the instruction, if they are instructions
    3836             :   // themselves, actually have parent basic blocks.  If the use is not an
    3837             :   // instruction, it is an error!
    3838    10376481 :   for (Use &U : I.uses()) {
    3839     9131218 :     if (Instruction *Used = dyn_cast<Instruction>(U.getUser()))
    3840     4565609 :       Assert(Used->getParent() != nullptr,
    3841             :              "Instruction referencing"
    3842             :              " instruction not embedded in a basic block!",
    3843             :              &I, Used);
    3844             :     else {
    3845           0 :       CheckFailed("Use of instruction is not an instruction!", U);
    3846           0 :       return;
    3847             :     }
    3848             :   }
    3849             : 
    3850    25607332 :   for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) {
    3851    19796476 :     Assert(I.getOperand(i) != nullptr, "Instruction has null operand!", &I);
    3852             : 
    3853             :     // Check to make sure that only first-class-values are operands to
    3854             :     // instructions.
    3855     9898238 :     if (!I.getOperand(i)->getType()->isFirstClassType()) {
    3856           0 :       Assert(false, "Instruction operands must be first-class values!", &I);
    3857             :     }
    3858             : 
    3859     9898238 :     if (Function *F = dyn_cast<Function>(I.getOperand(i))) {
    3860             :       // Check to make sure that the "address of" an intrinsic function is never
    3861             :       // taken.
    3862      837892 :       Assert(
    3863             :           !F->isIntrinsic() ||
    3864             :               i == (isa<CallInst>(I) ? e - 1 : isa<InvokeInst>(I) ? e - 3 : 0),
    3865             :           "Cannot take the address of an intrinsic!", &I);
    3866      837892 :       Assert(
    3867             :           !F->isIntrinsic() || isa<CallInst>(I) ||
    3868             :               F->getIntrinsicID() == Intrinsic::donothing ||
    3869             :               F->getIntrinsicID() == Intrinsic::coro_resume ||
    3870             :               F->getIntrinsicID() == Intrinsic::coro_destroy ||
    3871             :               F->getIntrinsicID() == Intrinsic::experimental_patchpoint_void ||
    3872             :               F->getIntrinsicID() == Intrinsic::experimental_patchpoint_i64 ||
    3873             :               F->getIntrinsicID() == Intrinsic::experimental_gc_statepoint,
    3874             :           "Cannot invoke an intrinsic other than donothing, patchpoint, "
    3875             :           "statepoint, coro_resume or coro_destroy",
    3876             :           &I);
    3877      536146 :       Assert(F->getParent() == &M, "Referencing function in another module!",
    3878             :              &I, &M, F, F->getParent());
    3879             :     } else if (BasicBlock *OpBB = dyn_cast<BasicBlock>(I.getOperand(i))) {
    3880      508002 :       Assert(OpBB->getParent() == BB->getParent(),
    3881             :              "Referring to a basic block in another function!", &I);
    3882             :     } else if (Argument *OpArg = dyn_cast<Argument>(I.getOperand(i))) {
    3883     1538142 :       Assert(OpArg->getParent() == BB->getParent(),
    3884             :              "Referring to an argument in another function!", &I);
    3885     7315943 :     } else if (GlobalValue *GV = dyn_cast<GlobalValue>(I.getOperand(i))) {
    3886      189052 :       Assert(GV->getParent() == &M, "Referencing global in another module!", &I,
    3887             :              &M, GV, GV->getParent());
    3888     7126891 :     } else if (isa<Instruction>(I.getOperand(i))) {
    3889     4568274 :       verifyDominatesUse(I, i);
    3890     2558617 :     } else if (isa<InlineAsm>(I.getOperand(i))) {
    3891      101428 :       Assert((i + 1 == e && isa<CallInst>(I)) ||
    3892             :                  (i + 3 == e && isa<InvokeInst>(I)),
    3893             :              "Cannot take the address of an inline asm!", &I);
    3894             :     } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(I.getOperand(i))) {
    3895      224239 :       if (CE->getType()->isPtrOrPtrVectorTy() ||
    3896        2759 :           !DL.getNonIntegralAddressSpaces().empty()) {
    3897             :         // If we have a ConstantExpr pointer, we need to see if it came from an
    3898             :         // illegal bitcast.  If the datalayout string specifies non-integral
    3899             :         // address spaces then we also need to check for illegal ptrtoint and
    3900             :         // inttoptr expressions.
    3901      107982 :         visitConstantExprsRecursively(CE);
    3902             :       }
    3903             :     }
    3904             :   }
    3905             : 
    3906      205558 :   if (MDNode *MD = I.getMetadata(LLVMContext::MD_fpmath)) {
    3907         400 :     Assert(I.getType()->isFPOrFPVectorTy(),
    3908             :            "fpmath requires a floating point result!", &I);
    3909         399 :     Assert(MD->getNumOperands() == 1, "fpmath takes one operand!", &I);
    3910             :     if (ConstantFP *CFP0 =
    3911             :             mdconst::dyn_extract_or_null<ConstantFP>(MD->getOperand(0))) {
    3912             :       const APFloat &Accuracy = CFP0->getValueAPF();
    3913         395 :       Assert(&Accuracy.getSemantics() == &APFloat::IEEEsingle(),
    3914             :              "fpmath accuracy must have float type", &I);
    3915         787 :       Assert(Accuracy.isFiniteNonZero() && !Accuracy.isNegative(),
    3916             :              "fpmath accuracy not a positive number!", &I);
    3917             :     } else {
    3918           2 :       Assert(false, "invalid fpmath accuracy!", &I);
    3919             :     }
    3920             :   }
    3921             : 
    3922      205550 :   if (MDNode *Range = I.getMetadata(LLVMContext::MD_range)) {
    3923        8493 :     Assert(isa<LoadInst>(I) || isa<CallInst>(I) || isa<InvokeInst>(I),
    3924             :            "Ranges are only for loads, calls and invokes!", &I);
    3925        8490 :     visitRangeMetadata(I, Range, I.getType());
    3926             :   }
    3927             : 
    3928      205549 :   if (I.getMetadata(LLVMContext::MD_nonnull)) {
    3929          66 :     Assert(I.getType()->isPointerTy(), "nonnull applies only to pointer types",
    3930             :            &I);
    3931          33 :     Assert(isa<LoadInst>(I),
    3932             :            "nonnull applies only to load instructions, use attributes"
    3933             :            " for calls or invokes",
    3934             :            &I);
    3935             :   }
    3936             : 
    3937      205549 :   if (MDNode *MD = I.getMetadata(LLVMContext::MD_dereferenceable))
    3938          46 :     visitDereferenceableMetadata(I, MD);
    3939             : 
    3940      205549 :   if (MDNode *MD = I.getMetadata(LLVMContext::MD_dereferenceable_or_null))
    3941          34 :     visitDereferenceableMetadata(I, MD);
    3942             : 
    3943      205549 :   if (MDNode *TBAA = I.getMetadata(LLVMContext::MD_tbaa))
    3944       35715 :     TBAAVerifyHelper.visitTBAAMetadata(I, TBAA);
    3945             : 
    3946      205549 :   if (MDNode *AlignMD = I.getMetadata(LLVMContext::MD_align)) {
    3947          41 :     Assert(I.getType()->isPointerTy(), "align applies only to pointer types",
    3948             :            &I);
    3949          20 :     Assert(isa<LoadInst>(I), "align applies only to load instructions, "
    3950             :            "use attributes for calls or invokes", &I);
    3951          19 :     Assert(AlignMD->getNumOperands() == 1, "align takes one operand!", &I);
    3952             :     ConstantInt *CI = mdconst::dyn_extract<ConstantInt>(AlignMD->getOperand(0));
    3953          20 :     Assert(CI && CI->getType()->isIntegerTy(64),
    3954             :            "align metadata value must be an i64!", &I);
    3955             :     uint64_t Align = CI->getZExtValue();
    3956           2 :     Assert(isPowerOf2_64(Align),
    3957             :            "align metadata value must be a power of 2!", &I);
    3958          15 :     Assert(Align <= Value::MaximumAlignment,
    3959             :            "alignment is larger that implementation defined limit", &I);
    3960             :   }
    3961             : 
    3962     5810848 :   if (MDNode *N = I.getDebugLoc().getAsMDNode()) {
    3963       94265 :     AssertDI(isa<DILocation>(N), "invalid !dbg metadata attachment", &I, N);
    3964       94257 :     visitMDNode(*N);
    3965             :   }
    3966             : 
    3967             :   if (auto *DII = dyn_cast<DbgInfoIntrinsic>(&I))
    3968       14092 :     verifyFragmentExpression(*DII);
    3969             : 
    3970     5810844 :   InstsInThisBlock.insert(&I);
    3971             : }
    3972             : 
    3973             : /// Allow intrinsics to be verified in different ways.
    3974      299580 : void Verifier::visitIntrinsicCallSite(Intrinsic::ID ID, CallSite CS) {
    3975      299580 :   Function *IF = CS.getCalledFunction();
    3976      299646 :   Assert(IF->isDeclaration(), "Intrinsic functions should never be defined!",
    3977             :          IF);
    3978             : 
    3979             :   // Verify that the intrinsic prototype lines up with what the .td files
    3980             :   // describe.
    3981      299580 :   FunctionType *IFTy = IF->getFunctionType();
    3982             :   bool IsVarArg = IFTy->isVarArg();
    3983             : 
    3984             :   SmallVector<Intrinsic::IITDescriptor, 8> Table;
    3985      299580 :   getIntrinsicInfoTableEntries(ID, Table);
    3986             :   ArrayRef<Intrinsic::IITDescriptor> TableRef = Table;
    3987             : 
    3988             :   SmallVector<Type *, 4> ArgTys;
    3989      599162 :   Assert(!Intrinsic::matchIntrinsicType(IFTy->getReturnType(),
    3990             :                                         TableRef, ArgTys),
    3991             :          "Intrinsic has incorrect return type!", IF);
    3992     1278314 :   for (unsigned i = 0, e = IFTy->getNumParams(); i != e; ++i)
    3993     1358373 :     Assert(!Intrinsic::matchIntrinsicType(IFTy->getParamType(i),
    3994             :                                           TableRef, ArgTys),
    3995             :            "Intrinsic has incorrect argument type!", IF);
    3996             : 
    3997             :   // Verify if the intrinsic call matches the vararg property.
    3998      299559 :   if (IsVarArg)
    3999        2726 :     Assert(!Intrinsic::matchIntrinsicVarArg(IsVarArg, TableRef),
    4000             :            "Intrinsic was not defined with variable arguments!", IF);
    4001             :   else
    4002      296835 :     Assert(!Intrinsic::matchIntrinsicVarArg(IsVarArg, TableRef),
    4003             :            "Callsite was not defined with variable arguments!", IF);
    4004             : 
    4005             :   // All descriptors should be absorbed by now.
    4006      299557 :   Assert(TableRef.empty(), "Intrinsic has too few arguments!", IF);
    4007             : 
    4008             :   // Now that we have the intrinsic ID and the actual argument types (and we
    4009             :   // know they are legal for the intrinsic!) get the intrinsic name through the
    4010             :   // usual means.  This allows us to verify the mangling of argument types into
    4011             :   // the name.
    4012      299557 :   const std::string ExpectedName = Intrinsic::getName(ID, ArgTys);
    4013      299557 :   Assert(ExpectedName == IF->getName(),
    4014             :          "Intrinsic name not mangled correctly for type arguments! "
    4015             :          "Should be: " +
    4016             :              ExpectedName,
    4017             :          IF);
    4018             : 
    4019             :   // If the intrinsic takes MDNode arguments, verify that they are either global
    4020             :   // or are local to *this* function.
    4021      986472 :   for (Value *V : CS.args())
    4022             :     if (auto *MD = dyn_cast<MetadataAsValue>(V))
    4023       44742 :       visitMetadataAsValue(*MD, CS.getCaller());
    4024             : 
    4025      299557 :   switch (ID) {
    4026             :   default:
    4027             :     break;
    4028         116 :   case Intrinsic::coro_id: {
    4029         116 :     auto *InfoArg = CS.getArgOperand(3)->stripPointerCasts();
    4030         116 :     if (isa<ConstantPointerNull>(InfoArg))
    4031             :       break;
    4032             :     auto *GV = dyn_cast<GlobalVariable>(InfoArg);
    4033          33 :     Assert(GV && GV->isConstant() && GV->hasDefinitiveInitializer(),
    4034             :       "info argument of llvm.coro.begin must refer to an initialized "
    4035             :       "constant");
    4036             :     Constant *Init = GV->getInitializer();
    4037          66 :     Assert(isa<ConstantStruct>(Init) || isa<ConstantArray>(Init),
    4038             :       "info argument of llvm.coro.begin must refer to either a struct or "
    4039             :       "an array");
    4040             :     break;
    4041             :   }
    4042        7858 :   case Intrinsic::ctlz:  // llvm.ctlz
    4043             :   case Intrinsic::cttz:  // llvm.cttz
    4044       15718 :     Assert(isa<ConstantInt>(CS.getArgOperand(1)),
    4045             :            "is_zero_undef argument of bit counting intrinsics must be a "
    4046             :            "constant int",
    4047             :            CS);
    4048             :     break;
    4049             :   case Intrinsic::experimental_constrained_fadd:
    4050             :   case Intrinsic::experimental_constrained_fsub:
    4051             :   case Intrinsic::experimental_constrained_fmul:
    4052             :   case Intrinsic::experimental_constrained_fdiv:
    4053             :   case Intrinsic::experimental_constrained_frem:
    4054             :   case Intrinsic::experimental_constrained_fma:
    4055             :   case Intrinsic::experimental_constrained_sqrt:
    4056             :   case Intrinsic::experimental_constrained_pow:
    4057             :   case Intrinsic::experimental_constrained_powi:
    4058             :   case Intrinsic::experimental_constrained_sin:
    4059             :   case Intrinsic::experimental_constrained_cos:
    4060             :   case Intrinsic::experimental_constrained_exp:
    4061             :   case Intrinsic::experimental_constrained_exp2:
    4062             :   case Intrinsic::experimental_constrained_log:
    4063             :   case Intrinsic::experimental_constrained_log10:
    4064             :   case Intrinsic::experimental_constrained_log2:
    4065             :   case Intrinsic::experimental_constrained_rint:
    4066             :   case Intrinsic::experimental_constrained_nearbyint:
    4067         303 :     visitConstrainedFPIntrinsic(
    4068             :         cast<ConstrainedFPIntrinsic>(*CS.getInstruction()));
    4069         303 :     break;
    4070        7633 :   case Intrinsic::dbg_declare: // llvm.dbg.declare
    4071       15266 :     Assert(isa<MetadataAsValue>(CS.getArgOperand(0)),
    4072             :            "invalid llvm.dbg.declare intrinsic call 1", CS);
    4073        7633 :     visitDbgIntrinsic("declare", cast<DbgInfoIntrinsic>(*CS.getInstruction()));
    4074        7633 :     break;
    4075             :   case Intrinsic::dbg_addr: // llvm.dbg.addr
    4076          20 :     visitDbgIntrinsic("addr", cast<DbgInfoIntrinsic>(*CS.getInstruction()));
    4077          20 :     break;
    4078             :   case Intrinsic::dbg_value: // llvm.dbg.value
    4079        6387 :     visitDbgIntrinsic("value", cast<DbgInfoIntrinsic>(*CS.getInstruction()));
    4080        6387 :     break;
    4081             :   case Intrinsic::dbg_label: // llvm.dbg.label
    4082          54 :     visitDbgLabelIntrinsic("label", cast<DbgLabelInst>(*CS.getInstruction()));
    4083          54 :     break;
    4084             :   case Intrinsic::memcpy:
    4085             :   case Intrinsic::memmove:
    4086             :   case Intrinsic::memset: {
    4087             :     const auto *MI = cast<MemIntrinsic>(CS.getInstruction());
    4088             :     auto IsValidAlignment = [&](unsigned Alignment) -> bool {
    4089       30998 :       return Alignment == 0 || isPowerOf2_32(Alignment);
    4090             :     };
    4091           0 :     Assert(IsValidAlignment(MI->getDestAlignment()),
    4092             :            "alignment of arg 0 of memory intrinsic must be 0 or a power of 2",
    4093             :            CS);
    4094             :     if (const auto *MTI = dyn_cast<MemTransferInst>(MI)) {
    4095           0 :       Assert(IsValidAlignment(MTI->getSourceAlignment()),
    4096             :              "alignment of arg 1 of memory intrinsic must be 0 or a power of 2",
    4097             :              CS);
    4098             :     }
    4099       34684 :     Assert(isa<ConstantInt>(CS.getArgOperand(3)),
    4100             :            "isvolatile argument of memory intrinsics must be a constant int",
    4101             :            CS);
    4102             :     break;
    4103             :   }
    4104             :   case Intrinsic::memcpy_element_unordered_atomic:
    4105             :   case Intrinsic::memmove_element_unordered_atomic:
    4106             :   case Intrinsic::memset_element_unordered_atomic: {
    4107             :     const auto *AMI = cast<AtomicMemIntrinsic>(CS.getInstruction());
    4108             : 
    4109             :     ConstantInt *ElementSizeCI =
    4110             :         dyn_cast<ConstantInt>(AMI->getRawElementSizeInBytes());
    4111          25 :     Assert(ElementSizeCI,
    4112             :            "element size of the element-wise unordered atomic memory "
    4113             :            "intrinsic must be a constant int",
    4114             :            CS);
    4115             :     const APInt &ElementSizeVal = ElementSizeCI->getValue();
    4116         376 :     Assert(ElementSizeVal.isPowerOf2(),
    4117             :            "element size of the element-wise atomic memory intrinsic "
    4118             :            "must be a power of 2",
    4119             :            CS);
    4120             : 
    4121             :     if (auto *LengthCI = dyn_cast<ConstantInt>(AMI->getLength())) {
    4122             :       uint64_t Length = LengthCI->getZExtValue();
    4123             :       uint64_t ElementSize = AMI->getElementSizeInBytes();
    4124         356 :       Assert((Length % ElementSize) == 0,
    4125             :              "constant length must be a multiple of the element size in the "
    4126             :              "element-wise atomic memory intrinsic",
    4127             :              CS);
    4128             :     }
    4129             : 
    4130         627 :     auto IsValidAlignment = [&](uint64_t Alignment) {
    4131        1244 :       return isPowerOf2_64(Alignment) && ElementSizeVal.ule(Alignment);
    4132         994 :     };
    4133         367 :     uint64_t DstAlignment = AMI->getDestAlignment();
    4134         373 :     Assert(IsValidAlignment(DstAlignment),
    4135             :            "incorrect alignment of the destination argument", CS);
    4136             :     if (const auto *AMT = dyn_cast<AtomicMemTransferInst>(AMI)) {
    4137         260 :       uint64_t SrcAlignment = AMT->getSourceAlignment();
    4138         264 :       Assert(IsValidAlignment(SrcAlignment),
    4139             :              "incorrect alignment of the source argument", CS);
    4140             :     }
    4141         357 :     break;
    4142             :   }
    4143          41 :   case Intrinsic::gcroot:
    4144             :   case Intrinsic::gcwrite:
    4145             :   case Intrinsic::gcread:
    4146          41 :     if (ID == Intrinsic::gcroot) {
    4147             :       AllocaInst *AI =
    4148          27 :         dyn_cast<AllocaInst>(CS.getArgOperand(0)->stripPointerCasts());
    4149           0 :       Assert(AI, "llvm.gcroot parameter #1 must be an alloca.", CS);
    4150          54 :       Assert(isa<Constant>(CS.getArgOperand(1)),
    4151             :              "llvm.gcroot parameter #2 must be a constant.", CS);
    4152          54 :       if (!AI->getAllocatedType()->isPointerTy()) {
    4153           2 :         Assert(!isa<ConstantPointerNull>(CS.getArgOperand(1)),
    4154             :                "llvm.gcroot parameter #1 must either be a pointer alloca, "
    4155             :                "or argument #2 must be a non-null constant.",
    4156             :                CS);
    4157             :       }
    4158             :     }
    4159             : 
    4160          81 :     Assert(CS.getParent()->getParent()->hasGC(),
    4161             :            "Enclosing function does not use GC.", CS);
    4162             :     break;
    4163          29 :   case Intrinsic::init_trampoline:
    4164          58 :     Assert(isa<Function>(CS.getArgOperand(1)->stripPointerCasts()),
    4165             :            "llvm.init_trampoline parameter #2 must resolve to a function.",
    4166             :            CS);
    4167             :     break;
    4168         659 :   case Intrinsic::prefetch:
    4169        3295 :     Assert(isa<ConstantInt>(CS.getArgOperand(1)) &&
    4170             :                isa<ConstantInt>(CS.getArgOperand(2)) &&
    4171             :                cast<ConstantInt>(CS.getArgOperand(1))->getZExtValue() < 2 &&
    4172             :                cast<ConstantInt>(CS.getArgOperand(2))->getZExtValue() < 4,
    4173             :            "invalid arguments to llvm.prefetch", CS);
    4174             :     break;
    4175         655 :   case Intrinsic::stackprotector:
    4176         655 :     Assert(isa<AllocaInst>(CS.getArgOperand(1)->stripPointerCasts()),
    4177             :            "llvm.stackprotector parameter #2 must resolve to an alloca.", CS);
    4178             :     break;
    4179        7277 :   case Intrinsic::lifetime_start:
    4180             :   case Intrinsic::lifetime_end:
    4181             :   case Intrinsic::invariant_start:
    4182       14554 :     Assert(isa<ConstantInt>(CS.getArgOperand(0)),
    4183             :            "size argument of memory use markers must be a constant integer",
    4184             :            CS);
    4185             :     break;
    4186          59 :   case Intrinsic::invariant_end:
    4187         118 :     Assert(isa<ConstantInt>(CS.getArgOperand(1)),
    4188             :            "llvm.invariant.end parameter #2 must be a constant integer", CS);
    4189             :     break;
    4190             : 
    4191             :   case Intrinsic::localescape: {
    4192             :     BasicBlock *BB = CS.getParent();
    4193         189 :     Assert(BB == &BB->getParent()->front(),
    4194             :            "llvm.localescape used outside of entry block", CS);
    4195          94 :     Assert(!SawFrameEscape,
    4196             :            "multiple calls to llvm.localescape in one function", CS);
    4197         209 :     for (Value *Arg : CS.args()) {
    4198         118 :       if (isa<ConstantPointerNull>(Arg))
    4199           0 :         continue; // Null values are allowed as placeholders.
    4200             :       auto *AI = dyn_cast<AllocaInst>(Arg->stripPointerCasts());
    4201         118 :       Assert(AI && AI->isStaticAlloca(),
    4202             :              "llvm.localescape only accepts static allocas", CS);
    4203             :     }
    4204         182 :     FrameEscapeInfo[BB->getParent()].first = CS.getNumArgOperands();
    4205          91 :     SawFrameEscape = true;
    4206          91 :     break;
    4207             :   }
    4208         105 :   case Intrinsic::localrecover: {
    4209         105 :     Value *FnArg = CS.getArgOperand(0)->stripPointerCasts();
    4210         105 :     Function *Fn = dyn_cast<Function>(FnArg);
    4211         115 :     Assert(Fn && !Fn->isDeclaration(),
    4212             :            "llvm.localrecover first "
    4213             :            "argument must be function defined in this module",
    4214             :            CS);
    4215         102 :     auto *IdxArg = dyn_cast<ConstantInt>(CS.getArgOperand(2));
    4216           2 :     Assert(IdxArg, "idx argument of llvm.localrecover must be a constant int",
    4217             :            CS);
    4218         101 :     auto &Entry = FrameEscapeInfo[Fn];
    4219         101 :     Entry.second = unsigned(
    4220         303 :         std::max(uint64_t(Entry.second), IdxArg->getLimitedValue(~0U) + 1));
    4221         101 :     break;
    4222             :   }
    4223             : 
    4224             :   case Intrinsic::experimental_gc_statepoint:
    4225         637 :     Assert(!CS.isInlineAsm(),
    4226             :            "gc.statepoint support for inline assembly unimplemented", CS);
    4227        1407 :     Assert(CS.getParent()->getParent()->hasGC(),
    4228             :            "Enclosing function does not use GC.", CS);
    4229             : 
    4230         702 :     verifyStatepoint(CS);
    4231         702 :     break;
    4232             :   case Intrinsic::experimental_gc_result: {
    4233         218 :     Assert(CS.getParent()->getParent()->hasGC(),
    4234             :            "Enclosing function does not use GC.", CS);
    4235             :     // Are we tied to a statepoint properly?
    4236         109 :     CallSite StatepointCS(CS.getArgOperand(0));
    4237             :     const Function *StatepointFn =
    4238         109 :       StatepointCS.getInstruction() ? StatepointCS.getCalledFunction() : nullptr;
    4239         109 :     Assert(StatepointFn && StatepointFn->isDeclaration() &&
    4240             :                StatepointFn->getIntrinsicID() ==
    4241             :                    Intrinsic::experimental_gc_statepoint,
    4242             :            "gc.result operand #1 must be from a statepoint", CS,
    4243             :            CS.getArgOperand(0));
    4244             : 
    4245             :     // Assert that result type matches wrapped callee.
    4246             :     const Value *Target = StatepointCS.getArgument(2);
    4247         109 :     auto *PT = cast<PointerType>(Target->getType());
    4248         109 :     auto *TargetFuncType = cast<FunctionType>(PT->getElementType());
    4249         218 :     Assert(CS.getType() == TargetFuncType->getReturnType(),
    4250             :            "gc.result result type does not match wrapped callee", CS);
    4251             :     break;
    4252             :   }
    4253         775 :   case Intrinsic::experimental_gc_relocate: {
    4254         780 :     Assert(CS.getNumArgOperands() == 3, "wrong number of arguments", CS);
    4255             : 
    4256         776 :     Assert(isa<PointerType>(CS.getType()->getScalarType()),
    4257             :            "gc.relocate must return a pointer or a vector of pointers", CS);
    4258             : 
    4259             :     // Check that this relocate is correctly tied to the statepoint
    4260             : 
    4261             :     // This is case for relocate on the unwinding path of an invoke statepoint
    4262             :     if (LandingPadInst *LandingPad =
    4263         774 :           dyn_cast<LandingPadInst>(CS.getArgOperand(0))) {
    4264             : 
    4265             :       const BasicBlock *InvokeBB =
    4266         150 :           LandingPad->getParent()->getUniquePredecessor();
    4267             : 
    4268             :       // Landingpad relocates should have only one predecessor with invoke
    4269             :       // statepoint terminator
    4270          75 :       Assert(InvokeBB, "safepoints should have unique landingpads",
    4271             :              LandingPad->getParent());
    4272          75 :       Assert(InvokeBB->getTerminator(), "safepoint block should be well formed",
    4273             :              InvokeBB);
    4274          75 :       Assert(isStatepoint(InvokeBB->getTerminator()),
    4275             :              "gc relocate should be linked to a statepoint", InvokeBB);
    4276             :     }
    4277             :     else {
    4278             :       // In all other cases relocate should be tied to the statepoint directly.
    4279             :       // This covers relocates on a normal return path of invoke statepoint and
    4280             :       // relocates of a call statepoint.
    4281         699 :       auto Token = CS.getArgOperand(0);
    4282         699 :       Assert(isa<Instruction>(Token) && isStatepoint(cast<Instruction>(Token)),
    4283             :              "gc relocate is incorrectly tied to the statepoint", CS, Token);
    4284             :     }
    4285             : 
    4286             :     // Verify rest of the relocate arguments.
    4287             : 
    4288             :     ImmutableCallSite StatepointCS(
    4289         774 :         cast<GCRelocateInst>(*CS.getInstruction()).getStatepoint());
    4290             : 
    4291             :     // Both the base and derived must be piped through the safepoint.
    4292         774 :     Value* Base = CS.getArgOperand(1);
    4293         774 :     Assert(isa<ConstantInt>(Base),
    4294             :            "gc.relocate operand #2 must be integer offset", CS);
    4295             : 
    4296         774 :     Value* Derived = CS.getArgOperand(2);
    4297         774 :     Assert(isa<ConstantInt>(Derived),
    4298             :            "gc.relocate operand #3 must be integer offset", CS);
    4299             : 
    4300         774 :     const int BaseIndex = cast<ConstantInt>(Base)->getZExtValue();
    4301         774 :     const int DerivedIndex = cast<ConstantInt>(Derived)->getZExtValue();
    4302             :     // Check the bounds
    4303         774 :     Assert(0 <= BaseIndex && BaseIndex < (int)StatepointCS.arg_size(),
    4304             :            "gc.relocate: statepoint base index out of bounds", CS);
    4305        1548 :     Assert(0 <= DerivedIndex && DerivedIndex < (int)StatepointCS.arg_size(),
    4306             :            "gc.relocate: statepoint derived index out of bounds", CS);
    4307             : 
    4308             :     // Check that BaseIndex and DerivedIndex fall within the 'gc parameters'
    4309             :     // section of the statepoint's argument.
    4310         774 :     Assert(StatepointCS.arg_size() > 0,
    4311             :            "gc.statepoint: insufficient arguments");
    4312         774 :     Assert(isa<ConstantInt>(StatepointCS.getArgument(3)),
    4313             :            "gc.statement: number of call arguments must be constant integer");
    4314             :     const unsigned NumCallArgs =
    4315         774 :         cast<ConstantInt>(StatepointCS.getArgument(3))->getZExtValue();
    4316         775 :     Assert(StatepointCS.arg_size() > NumCallArgs + 5,
    4317             :            "gc.statepoint: mismatch in number of call arguments");
    4318         773 :     Assert(isa<ConstantInt>(StatepointCS.getArgument(NumCallArgs + 5)),
    4319             :            "gc.statepoint: number of transition arguments must be "
    4320             :            "a constant integer");
    4321             :     const int NumTransitionArgs =
    4322             :         cast<ConstantInt>(StatepointCS.getArgument(NumCallArgs + 5))
    4323             :             ->getZExtValue();
    4324         773 :     const int DeoptArgsStart = 4 + NumCallArgs + 1 + NumTransitionArgs + 1;
    4325         774 :     Assert(isa<ConstantInt>(StatepointCS.getArgument(DeoptArgsStart)),
    4326             :            "gc.statepoint: number of deoptimization arguments must be "
    4327             :            "a constant integer");
    4328             :     const int NumDeoptArgs =
    4329             :         cast<ConstantInt>(StatepointCS.getArgument(DeoptArgsStart))
    4330         772 :             ->getZExtValue();
    4331         772 :     const int GCParamArgsStart = DeoptArgsStart + 1 + NumDeoptArgs;
    4332         772 :     const int GCParamArgsEnd = StatepointCS.arg_size();
    4333         772 :     Assert(GCParamArgsStart <= BaseIndex && BaseIndex < GCParamArgsEnd,
    4334             :            "gc.relocate: statepoint base index doesn't fall within the "
    4335             :            "'gc parameters' section of the statepoint call",
    4336             :            CS);
    4337         772 :     Assert(GCParamArgsStart <= DerivedIndex && DerivedIndex < GCParamArgsEnd,
    4338             :            "gc.relocate: statepoint derived index doesn't fall within the "
    4339             :            "'gc parameters' section of the statepoint call",
    4340             :            CS);
    4341             : 
    4342             :     // Relocated value must be either a pointer type or vector-of-pointer type,
    4343             :     // but gc_relocate does not need to return the same pointer type as the
    4344             :     // relocated pointer. It can be casted to the correct type later if it's
    4345             :     // desired. However, they must have the same address space and 'vectorness'
    4346             :     GCRelocateInst &Relocate = cast<GCRelocateInst>(*CS.getInstruction());
    4347        1545 :     Assert(Relocate.getDerivedPtr()->getType()->isPtrOrPtrVectorTy(),
    4348             :            "gc.relocate: relocated value must be a gc pointer", CS);
    4349             : 
    4350             :     auto ResultType = CS.getType();
    4351         771 :     auto DerivedType = Relocate.getDerivedPtr()->getType();
    4352         771 :     Assert(ResultType->isVectorTy() == DerivedType->isVectorTy(),
    4353             :            "gc.relocate: vector relocates to vector and pointer to pointer",
    4354             :            CS);
    4355         772 :     Assert(
    4356             :         ResultType->getPointerAddressSpace() ==
    4357             :             DerivedType->getPointerAddressSpace(),
    4358             :         "gc.relocate: relocating a pointer shouldn't change its address space",
    4359             :         CS);
    4360         770 :     break;
    4361             :   }
    4362          58 :   case Intrinsic::eh_exceptioncode:
    4363             :   case Intrinsic::eh_exceptionpointer: {
    4364          60 :     Assert(isa<CatchPadInst>(CS.getArgOperand(0)),
    4365             :            "eh.exceptionpointer argument must be a catchpad", CS);
    4366             :     break;
    4367             :   }
    4368             :   case Intrinsic::masked_load: {
    4369        1239 :     Assert(CS.getType()->isVectorTy(), "masked_load: must return a vector", CS);
    4370             : 
    4371        1239 :     Value *Ptr = CS.getArgOperand(0);
    4372             :     //Value *Alignment = CS.getArgOperand(1);
    4373        1239 :     Value *Mask = CS.getArgOperand(2);
    4374        1239 :     Value *PassThru = CS.getArgOperand(3);
    4375        2478 :     Assert(Mask->getType()->isVectorTy(),
    4376             :            "masked_load: mask must be vector", CS);
    4377             : 
    4378             :     // DataTy is the overloaded type
    4379        1239 :     Type *DataTy = cast<PointerType>(Ptr->getType())->getElementType();
    4380        1239 :     Assert(DataTy == CS.getType(),
    4381             :            "masked_load: return must match pointer type", CS);
    4382        1239 :     Assert(PassThru->getType() == DataTy,
    4383             :            "masked_load: pass through and data type must match", CS);
    4384        1239 :     Assert(Mask->getType()->getVectorNumElements() ==
    4385             :            DataTy->getVectorNumElements(),
    4386             :            "masked_load: vector mask must be same length as data", CS);
    4387             :     break;
    4388             :   }
    4389         719 :   case Intrinsic::masked_store: {
    4390         719 :     Value *Val = CS.getArgOperand(0);
    4391         719 :     Value *Ptr = CS.getArgOperand(1);
    4392             :     //Value *Alignment = CS.getArgOperand(2);
    4393         719 :     Value *Mask = CS.getArgOperand(3);
    4394        1438 :     Assert(Mask->getType()->isVectorTy(),
    4395             :            "masked_store: mask must be vector", CS);
    4396             : 
    4397             :     // DataTy is the overloaded type
    4398         719 :     Type *DataTy = cast<PointerType>(Ptr->getType())->getElementType();
    4399         719 :     Assert(DataTy == Val->getType(),
    4400             :            "masked_store: storee must match pointer type", CS);
    4401         719 :     Assert(Mask->getType()->getVectorNumElements() ==
    4402             :            DataTy->getVectorNumElements(),
    4403             :            "masked_store: vector mask must be same length as data", CS);
    4404             :     break;
    4405             :   }
    4406             : 
    4407             :   case Intrinsic::experimental_guard: {
    4408         760 :     Assert(CS.isCall(), "experimental_guard cannot be invoked", CS);
    4409         759 :     Assert(CS.countOperandBundlesOfType(LLVMContext::OB_deopt) == 1,
    4410             :            "experimental_guard must have exactly one "
    4411             :            "\"deopt\" operand bundle");
    4412             :     break;
    4413             :   }
    4414             : 
    4415             :   case Intrinsic::experimental_deoptimize: {
    4416          62 :     Assert(CS.isCall(), "experimental_deoptimize cannot be invoked", CS);
    4417          61 :     Assert(CS.countOperandBundlesOfType(LLVMContext::OB_deopt) == 1,
    4418             :            "experimental_deoptimize must have exactly one "
    4419             :            "\"deopt\" operand bundle");
    4420          59 :     Assert(CS.getType() == CS.getInstruction()->getFunction()->getReturnType(),
    4421             :            "experimental_deoptimize return type must match caller return type");
    4422             : 
    4423          59 :     if (CS.isCall()) {
    4424             :       auto *DeoptCI = CS.getInstruction();
    4425             :       auto *RI = dyn_cast<ReturnInst>(DeoptCI->getNextNode());
    4426           1 :       Assert(RI,
    4427             :              "calls to experimental_deoptimize must be followed by a return");
    4428             : 
    4429          58 :       if (!CS.getType()->isVoidTy() && RI)
    4430          46 :         Assert(RI->getReturnValue() == DeoptCI,
    4431             :                "calls to experimental_deoptimize must be followed by a return "
    4432             :                "of the value computed by experimental_deoptimize");
    4433             :     }
    4434             : 
    4435             :     break;
    4436             :   }
    4437             :   };
    4438             : }
    4439             : 
    4440             : /// Carefully grab the subprogram from a local scope.
    4441             : ///
    4442             : /// This carefully grabs the subprogram from a local scope, avoiding the
    4443             : /// built-in assertions that would typically fire.
    4444             : static DISubprogram *getSubprogram(Metadata *LocalScope) {
    4445       34945 :   if (!LocalScope)
    4446             :     return nullptr;
    4447             : 
    4448             :   if (auto *SP = dyn_cast<DISubprogram>(LocalScope))
    4449             :     return SP;
    4450             : 
    4451             :   if (auto *LB = dyn_cast<DILexicalBlockBase>(LocalScope))
    4452             :     return getSubprogram(LB->getRawScope());
    4453             : 
    4454             :   // Just return null; broken scope chains are checked elsewhere.
    4455             :   assert(!isa<DILocalScope>(LocalScope) && "Unknown type of local scope");
    4456             :   return nullptr;
    4457             : }
    4458             : 
    4459         303 : void Verifier::visitConstrainedFPIntrinsic(ConstrainedFPIntrinsic &FPI) {
    4460         303 :   unsigned NumOperands = FPI.getNumArgOperands();
    4461         303 :   Assert(((NumOperands == 5 && FPI.isTernaryOp()) ||
    4462             :           (NumOperands == 3 && FPI.isUnaryOp()) || (NumOperands == 4)),
    4463             :            "invalid arguments for constrained FP intrinsic", &FPI);
    4464         606 :   Assert(isa<MetadataAsValue>(FPI.getArgOperand(NumOperands-1)),
    4465             :          "invalid exception behavior argument", &FPI);
    4466         606 :   Assert(isa<MetadataAsValue>(FPI.getArgOperand(NumOperands-2)),
    4467             :          "invalid rounding mode argument", &FPI);
    4468         305 :   Assert(FPI.getRoundingMode() != ConstrainedFPIntrinsic::rmInvalid,
    4469             :          "invalid rounding mode argument", &FPI);
    4470         303 :   Assert(FPI.getExceptionBehavior() != ConstrainedFPIntrinsic::ebInvalid,
    4471             :          "invalid exception behavior argument", &FPI);
    4472             : }
    4473             : 
    4474       14040 : void Verifier::visitDbgIntrinsic(StringRef Kind, DbgInfoIntrinsic &DII) {
    4475       28080 :   auto *MD = cast<MetadataAsValue>(DII.getArgOperand(0))->getMetadata();
    4476         129 :   AssertDI(isa<ValueAsMetadata>(MD) ||
    4477             :              (isa<MDNode>(MD) && !cast<MDNode>(MD)->getNumOperands()),
    4478             :          "invalid llvm.dbg." + Kind + " intrinsic address/value", &DII, MD);
    4479       14040 :   AssertDI(isa<DILocalVariable>(DII.getRawVariable()),
    4480             :          "invalid llvm.dbg." + Kind + " intrinsic variable", &DII,
    4481             :          DII.getRawVariable());
    4482       14038 :   AssertDI(isa<DIExpression>(DII.getRawExpression()),
    4483             :          "invalid llvm.dbg." + Kind + " intrinsic expression", &DII,
    4484             :          DII.getRawExpression());
    4485             : 
    4486             :   // Ignore broken !dbg attachments; they're checked elsewhere.
    4487       14034 :   if (MDNode *N = DII.getDebugLoc().getAsMDNode())
    4488       14030 :     if (!isa<DILocation>(N))
    4489             :       return;
    4490             : 
    4491       14032 :   BasicBlock *BB = DII.getParent();
    4492       14032 :   Function *F = BB ? BB->getParent() : nullptr;
    4493             : 
    4494             :   // The scopes for variables and !dbg attachments must agree.
    4495       14032 :   DILocalVariable *Var = DII.getVariable();
    4496       14032 :   DILocation *Loc = DII.getDebugLoc();
    4497       14036 :   AssertDI(Loc, "llvm.dbg." + Kind + " intrinsic requires a !dbg attachment",
    4498             :            &DII, BB, F);
    4499             : 
    4500       14028 :   DISubprogram *VarSP = getSubprogram(Var->getRawScope());
    4501             :   DISubprogram *LocSP = getSubprogram(Loc->getRawScope());
    4502       14028 :   if (!VarSP || !LocSP)
    4503             :     return; // Broken scope chains are checked elsewhere.
    4504             : 
    4505       14032 :   AssertDI(VarSP == LocSP, "mismatched subprogram between llvm.dbg." + Kind +
    4506             :                                " variable and !dbg attachment",
    4507             :            &DII, BB, F, Var, Var->getScope()->getSubprogram(), Loc,
    4508             :            Loc->getScope()->getSubprogram());
    4509             : 
    4510       14026 :   verifyFnArgs(DII);
    4511             : }
    4512             : 
    4513          54 : void Verifier::visitDbgLabelIntrinsic(StringRef Kind, DbgLabelInst &DLI) {
    4514          54 :   AssertDI(isa<DILabel>(DLI.getRawVariable()),
    4515             :          "invalid llvm.dbg." + Kind + " intrinsic variable", &DLI,
    4516             :          DLI.getRawVariable());
    4517             : 
    4518             :   // Ignore broken !dbg attachments; they're checked elsewhere.
    4519          54 :   if (MDNode *N = DLI.getDebugLoc().getAsMDNode())
    4520          54 :     if (!isa<DILocation>(N))
    4521             :       return;
    4522             : 
    4523          54 :   BasicBlock *BB = DLI.getParent();
    4524          54 :   Function *F = BB ? BB->getParent() : nullptr;
    4525             : 
    4526             :   // The scopes for variables and !dbg attachments must agree.
    4527          54 :   DILabel *Label = DLI.getLabel();
    4528          54 :   DILocation *Loc = DLI.getDebugLoc();
    4529          54 :   Assert(Loc, "llvm.dbg." + Kind + " intrinsic requires a !dbg attachment",
    4530             :          &DLI, BB, F);
    4531             : 
    4532          54 :   DISubprogram *LabelSP = getSubprogram(Label->getRawScope());
    4533             :   DISubprogram *LocSP = getSubprogram(Loc->getRawScope());
    4534          54 :   if (!LabelSP || !LocSP)
    4535             :     return;
    4536             : 
    4537          54 :   AssertDI(LabelSP == LocSP, "mismatched subprogram between llvm.dbg." + Kind +
    4538             :                              " label and !dbg attachment",
    4539             :            &DLI, BB, F, Label, Label->getScope()->getSubprogram(), Loc,
    4540             :            Loc->getScope()->getSubprogram());
    4541             : }
    4542             : 
    4543       14092 : void Verifier::verifyFragmentExpression(const DbgInfoIntrinsic &I) {
    4544             :   if (dyn_cast<DbgLabelInst>(&I))
    4545       13717 :     return;
    4546             : 
    4547             :   DILocalVariable *V = dyn_cast_or_null<DILocalVariable>(I.getRawVariable());
    4548             :   DIExpression *E = dyn_cast_or_null<DIExpression>(I.getRawExpression());
    4549             : 
    4550             :   // We don't know whether this intrinsic verified correctly.
    4551       14038 :   if (!V || !E || !E->isValid())
    4552             :     return;
    4553             : 
    4554             :   // Nothing to do if this isn't a DW_OP_LLVM_fragment expression.
    4555             :   auto Fragment = E->getFragmentInfo();
    4556       14033 :   if (!Fragment)
    4557             :     return;
    4558             : 
    4559             :   // The frontend helps out GDB by emitting the members of local anonymous
    4560             :   // unions as artificial local variables with shared storage. When SROA splits
    4561             :   // the storage for artificial local variables that are smaller than the entire
    4562             :   // union, the overhang piece will be outside of the allotted space for the
    4563             :   // variable and this check fails.
    4564             :   // FIXME: Remove this check as soon as clang stops doing this; it hides bugs.
    4565         383 :   if (V->isArtificial())
    4566             :     return;
    4567             : 
    4568         375 :   verifyFragmentExpression(*V, *Fragment, &I);
    4569             : }
    4570             : 
    4571             : template <typename ValueOrMetadata>
    4572         457 : void Verifier::verifyFragmentExpression(const DIVariable &V,
    4573             :                                         DIExpression::FragmentInfo Fragment,
    4574             :                                         ValueOrMetadata *Desc) {
    4575             :   // If there's no size, the type is broken, but that should be checked
    4576             :   // elsewhere.
    4577         457 :   auto VarSize = V.getSizeInBits();
    4578         457 :   if (!VarSize)
    4579             :     return;
    4580             : 
    4581         457 :   unsigned FragSize = Fragment.SizeInBits;
    4582         457 :   unsigned FragOffset = Fragment.OffsetInBits;
    4583         458 :   AssertDI(FragSize + FragOffset <= *VarSize,
    4584             :          "fragment is larger than or outside of variable", Desc, &V);
    4585         456 :   AssertDI(FragSize != *VarSize, "fragment covers entire variable", Desc, &V);
    4586             : }
    4587             : 
    4588       14026 : void Verifier::verifyFnArgs(const DbgInfoIntrinsic &I) {
    4589             :   // This function does not take the scope of noninlined function arguments into
    4590             :   // account. Don't run it if current function is nodebug, because it may
    4591             :   // contain inlined debug intrinsics.
    4592       14026 :   if (!HasDebugInfo)
    4593        7736 :     return;
    4594             : 
    4595             :   // For performance reasons only check non-inlined ones.
    4596             :   if (I.getDebugLoc()->getInlinedAt())
    4597             :     return;
    4598             : 
    4599       12869 :   DILocalVariable *Var = I.getVariable();
    4600       12869 :   AssertDI(Var, "dbg intrinsic without variable");
    4601             : 
    4602             :   unsigned ArgNo = Var->getArg();
    4603       12869 :   if (!ArgNo)
    4604             :     return;
    4605             : 
    4606             :   // Verify there are no duplicate function argument debug info entries.
    4607             :   // These will cause hard-to-debug assertions in the DWARF backend.
    4608        6291 :   if (DebugFnArgs.size() < ArgNo)
    4609        5712 :     DebugFnArgs.resize(ArgNo, nullptr);
    4610             : 
    4611       12582 :   auto *Prev = DebugFnArgs[ArgNo - 1];
    4612        6291 :   DebugFnArgs[ArgNo - 1] = Var;
    4613        6292 :   AssertDI(!Prev || (Prev == Var), "conflicting debug info for argument", &I,
    4614             :            Prev, Var);
    4615             : }
    4616             : 
    4617       94959 : void Verifier::verifyCompileUnits() {
    4618             :   // When more than one Module is imported into the same context, such as during
    4619             :   // an LTO build before linking the modules, ODR type uniquing may cause types
    4620             :   // to point to a different CU. This check does not make sense in this case.
    4621       94959 :   if (M.getContext().isODRUniquingDebugTypes())
    4622       23348 :     return;
    4623      143246 :   auto *CUs = M.getNamedMetadata("llvm.dbg.cu");
    4624             :   SmallPtrSet<const Metadata *, 2> Listed;
    4625       71623 :   if (CUs)
    4626        5062 :     Listed.insert(CUs->op_begin(), CUs->op_end());
    4627       78166 :   for (auto *CU : CUVisited)
    4628        6555 :     AssertDI(Listed.count(CU), "DICompileUnit not listed in llvm.dbg.cu", CU);
    4629       71611 :   CUVisited.clear();
    4630             : }
    4631             : 
    4632       94959 : void Verifier::verifyDeoptimizeCallingConvs() {
    4633       94959 :   if (DeoptimizeDeclarations.empty())
    4634       94929 :     return;
    4635             : 
    4636          31 :   const Function *First = DeoptimizeDeclarations[0];
    4637          57 :   for (auto *F : makeArrayRef(DeoptimizeDeclarations).slice(1)) {
    4638          15 :     Assert(First->getCallingConv() == F->getCallingConv(),
    4639             :            "All llvm.experimental.deoptimize declarations must have the same "
    4640             :            "calling convention",
    4641             :            First, F);
    4642             :   }
    4643             : }
    4644             : 
    4645             : //===----------------------------------------------------------------------===//
    4646             : //  Implement the public interfaces to this file...
    4647             : //===----------------------------------------------------------------------===//
    4648             : 
    4649         657 : bool llvm::verifyFunction(const Function &f, raw_ostream *OS) {
    4650             :   Function &F = const_cast<Function &>(f);
    4651             : 
    4652             :   // Don't use a raw_null_ostream.  Printing IR is expensive.
    4653        1314 :   Verifier V(OS, /*ShouldTreatBrokenDebugInfoAsError=*/true, *f.getParent());
    4654             : 
    4655             :   // Note that this function's return value is inverted from what you would
    4656             :   // expect of a function called "verify".
    4657        1314 :   return !V.verify(F);
    4658             : }
    4659             : 
    4660       37654 : bool llvm::verifyModule(const Module &M, raw_ostream *OS,
    4661             :                         bool *BrokenDebugInfo) {
    4662             :   // Don't use a raw_null_ostream.  Printing IR is expensive.
    4663       75308 :   Verifier V(OS, /*ShouldTreatBrokenDebugInfoAsError=*/!BrokenDebugInfo, M);
    4664             : 
    4665             :   bool Broken = false;
    4666      353910 :   for (const Function &F : M)
    4667      316256 :     Broken |= !V.verify(F);
    4668             : 
    4669       37654 :   Broken |= !V.verify();
    4670       37654 :   if (BrokenDebugInfo)
    4671        3489 :     *BrokenDebugInfo = V.hasBrokenDebugInfo();
    4672             :   // Note that this function's return value is inverted from what you would
    4673             :   // expect of a function called "verify".
    4674       37654 :   return Broken;
    4675             : }
    4676             : 
    4677             : namespace {
    4678             : 
    4679      115028 : struct VerifierLegacyPass : public FunctionPass {
    4680             :   static char ID;
    4681             : 
    4682             :   std::unique_ptr<Verifier> V;
    4683             :   bool FatalErrors = true;
    4684             : 
    4685         231 :   VerifierLegacyPass() : FunctionPass(ID) {
    4686          77 :     initializeVerifierLegacyPassPass(*PassRegistry::getPassRegistry());
    4687          77 :   }
    4688             :   explicit VerifierLegacyPass(bool FatalErrors)
    4689       57707 :       : FunctionPass(ID),
    4690      115414 :         FatalErrors(FatalErrors) {
    4691       57707 :     initializeVerifierLegacyPassPass(*PassRegistry::getPassRegistry());
    4692             :   }
    4693             : 
    4694       57568 :   bool doInitialization(Module &M) override {
    4695       57568 :     V = llvm::make_unique<Verifier>(
    4696      115136 :         &dbgs(), /*ShouldTreatBrokenDebugInfoAsError=*/false, M);
    4697       57568 :     return false;
    4698             :   }
    4699             : 
    4700      518404 :   bool runOnFunction(Function &F) override {
    4701      518404 :     if (!V->verify(F) && FatalErrors)
    4702           0 :       report_fatal_error("Broken function found, compilation aborted!");
    4703             : 
    4704      518404 :     return false;
    4705             :   }
    4706             : 
    4707       57305 :   bool doFinalization(Module &M) override {
    4708             :     bool HasErrors = false;
    4709      785544 :     for (Function &F : M)
    4710      728239 :       if (F.isDeclaration())
    4711      209885 :         HasErrors |= !V->verify(F);
    4712             : 
    4713       57305 :     HasErrors |= !V->verify();
    4714      114568 :     if (FatalErrors && (HasErrors || V->hasBrokenDebugInfo()))
    4715           0 :       report_fatal_error("Broken module found, compilation aborted!");
    4716       57305 :     return false;
    4717             :   }
    4718             : 
    4719       57559 :   void getAnalysisUsage(AnalysisUsage &AU) const override {
    4720             :     AU.setPreservesAll();
    4721       57559 :   }
    4722             : };
    4723             : 
    4724             : } // end anonymous namespace
    4725             : 
    4726             : /// Helper to issue failure from the TBAA verification
    4727          27 : template <typename... Tys> void TBAAVerifier::CheckFailed(Tys &&... Args) {
    4728          27 :   if (Diagnostic)
    4729          25 :     return Diagnostic->CheckFailed(Args...);
    4730             : }
    4731             : 
    4732             : #define AssertTBAA(C, ...)                                                     \
    4733             :   do {                                                                         \
    4734             :     if (!(C)) {                                                                \
    4735             :       CheckFailed(__VA_ARGS__);                                                \
    4736             :       return false;                                                            \
    4737             :     }                                                                          \
    4738             :   } while (false)
    4739             : 
    4740             : /// Verify that \p BaseNode can be used as the "base type" in the struct-path
    4741             : /// TBAA scheme.  This means \p BaseNode is either a scalar node, or a
    4742             : /// struct-type node describing an aggregate data structure (like a struct).
    4743             : TBAAVerifier::TBAABaseNodeSummary
    4744       55466 : TBAAVerifier::verifyTBAABaseNode(Instruction &I, const MDNode *BaseNode,
    4745             :                                  bool IsNewFormat) {
    4746       55466 :   if (BaseNode->getNumOperands() < 2) {
    4747           0 :     CheckFailed("Base nodes must have at least two operands", &I, BaseNode);
    4748           0 :     return {true, ~0u};
    4749             :   }
    4750             : 
    4751       55466 :   auto Itr = TBAABaseNodes.find(BaseNode);
    4752       55466 :   if (Itr != TBAABaseNodes.end())
    4753       50061 :     return Itr->second;
    4754             : 
    4755        5405 :   auto Result = verifyTBAABaseNodeImpl(I, BaseNode, IsNewFormat);
    4756        5405 :   auto InsertResult = TBAABaseNodes.insert({BaseNode, Result});
    4757             :   (void)InsertResult;
    4758             :   assert(InsertResult.second && "We just checked!");
    4759        5405 :   return Result;
    4760             : }
    4761             : 
    4762             : TBAAVerifier::TBAABaseNodeSummary
    4763        5405 : TBAAVerifier::verifyTBAABaseNodeImpl(Instruction &I, const MDNode *BaseNode,
    4764             :                                      bool IsNewFormat) {
    4765             :   const TBAAVerifier::TBAABaseNodeSummary InvalidNode = {true, ~0u};
    4766             : 
    4767        5405 :   if (BaseNode->getNumOperands() == 2) {
    4768             :     // Scalar nodes can only be accessed at offset 0.
    4769        1014 :     return isValidScalarTBAANode(BaseNode)
    4770             :                ? TBAAVerifier::TBAABaseNodeSummary({false, 0})
    4771        1014 :                : InvalidNode;
    4772             :   }
    4773             : 
    4774        4391 :   if (IsNewFormat) {
    4775         234 :     if (BaseNode->getNumOperands() % 3 != 0) {
    4776           0 :       CheckFailed("Access tag nodes must have the number of operands that is a "
    4777             :                   "multiple of 3!", BaseNode);
    4778           0 :       return InvalidNode;
    4779             :     }
    4780             :   } else {
    4781        4157 :     if (BaseNode->getNumOperands() % 2 != 1) {
    4782           1 :       CheckFailed("Struct tag nodes must have an odd number of operands!",
    4783             :                   BaseNode);
    4784           1 :       return InvalidNode;
    4785             :     }
    4786             :   }
    4787             : 
    4788             :   // Check the type size field.
    4789        4390 :   if (IsNewFormat) {
    4790             :     auto *TypeSizeNode = mdconst::dyn_extract_or_null<ConstantInt>(
    4791             :         BaseNode->getOperand(1));
    4792             :     if (!TypeSizeNode) {
    4793           0 :       CheckFailed("Type size nodes must be constants!", &I, BaseNode);
    4794           0 :       return InvalidNode;
    4795             :     }
    4796             :   }
    4797             : 
    4798             :   // Check the type name field. In the new format it can be anything.
    4799        8546 :   if (!IsNewFormat && !isa<MDString>(BaseNode->getOperand(0))) {
    4800           1 :     CheckFailed("Struct tag nodes have a string as their first operand",
    4801             :                 BaseNode);
    4802           1 :     return InvalidNode;
    4803             :   }
    4804             : 
    4805             :   bool Failed = false;
    4806             : 
    4807             :   Optional<APInt> PrevOffset;
    4808             :   unsigned BitWidth = ~0u;
    4809             : 
    4810             :   // We've already checked that BaseNode is not a degenerate root node with one
    4811             :   // operand in \c verifyTBAABaseNode, so this loop should run at least once.
    4812        4389 :   unsigned FirstFieldOpNo = IsNewFormat ? 3 : 1;
    4813        4389 :   unsigned NumOpsPerField = IsNewFormat ? 3 : 2;
    4814       20863 :   for (unsigned Idx = FirstFieldOpNo; Idx < BaseNode->getNumOperands();
    4815        8237 :            Idx += NumOpsPerField) {
    4816             :     const MDOperand &FieldTy = BaseNode->getOperand(Idx);
    4817        8237 :     const MDOperand &FieldOffset = BaseNode->getOperand(Idx + 1);
    4818           1 :     if (!isa<MDNode>(FieldTy)) {
    4819           1 :       CheckFailed("Incorrect field entry in struct type node!", &I, BaseNode);
    4820             :       Failed = true;
    4821           1 :       continue;
    4822             :     }
    4823             : 
    4824             :     auto *OffsetEntryCI =
    4825             :         mdconst::dyn_extract_or_null<ConstantInt>(FieldOffset);
    4826           0 :     if (!OffsetEntryCI) {
    4827           0 :       CheckFailed("Offset entries must be constants!", &I, BaseNode);
    4828             :       Failed = true;
    4829           0 :       continue;
    4830             :     }
    4831             : 
    4832        8236 :     if (BitWidth == ~0u)
    4833             :       BitWidth = OffsetEntryCI->getBitWidth();
    4834             : 
    4835        8237 :     if (OffsetEntryCI->getBitWidth() != BitWidth) {
    4836           1 :       CheckFailed(
    4837           2 :           "Bitwidth between the offsets and struct type entries must match", &I,
    4838             :           BaseNode);
    4839             :       Failed = true;
    4840           1 :       continue;
    4841             :     }
    4842             : 
    4843             :     // NB! As far as I can tell, we generate a non-strictly increasing offset
    4844             :     // sequence only from structs that have zero size bit fields.  When
    4845             :     // recursing into a contained struct in \c getFieldNodeFromTBAABaseNode we
    4846             :     // pick the field lexically the latest in struct type metadata node.  This
    4847             :     // mirrors the actual behavior of the alias analysis implementation.
    4848             :     bool IsAscending =
    4849       12262 :         !PrevOffset || PrevOffset->ule(OffsetEntryCI->getValue());
    4850             : 
    4851             :     if (!IsAscending) {
    4852           1 :       CheckFailed("Offsets must be increasing!", &I, BaseNode);
    4853             :       Failed = true;
    4854             :     }
    4855             : 
    4856             :     PrevOffset = OffsetEntryCI->getValue();
    4857             : 
    4858        8235 :     if (IsNewFormat) {
    4859         114 :       auto *MemberSizeNode = mdconst::dyn_extract_or_null<ConstantInt>(
    4860             :           BaseNode->getOperand(Idx + 2));
    4861           0 :       if (!MemberSizeNode) {
    4862           0 :         CheckFailed("Member size entries must be constants!", &I, BaseNode);
    4863             :         Failed = true;
    4864           0 :         continue;
    4865             :       }
    4866             :     }
    4867             :   }
    4868             : 
    4869             :   return Failed ? InvalidNode
    4870        4389 :                 : TBAAVerifier::TBAABaseNodeSummary(false, BitWidth);
    4871             : }
    4872             : 
    4873             : static bool IsRootTBAANode(const MDNode *MD) {
    4874       98511 :   return MD->getNumOperands() < 2;
    4875             : }
    4876             : 
    4877        8105 : static bool IsScalarTBAANodeImpl(const MDNode *MD,
    4878             :                                  SmallPtrSetImpl<const MDNode *> &Visited) {
    4879        8105 :   if (MD->getNumOperands() != 2 && MD->getNumOperands() != 3)
    4880             :     return false;
    4881             : 
    4882        7781 :   if (!isa<MDString>(MD->getOperand(0)))
    4883             :     return false;
    4884             : 
    4885        7598 :   if (MD->getNumOperands() == 3) {
    4886             :     auto *Offset = mdconst::dyn_extract<ConstantInt>(MD->getOperand(2));
    4887        6176 :     if (!(Offset && Offset->isZero() && isa<MDString>(MD->getOperand(0))))
    4888             :       return false;
    4889             :   }
    4890             : 
    4891             :   auto *Parent = dyn_cast_or_null<MDNode>(MD->getOperand(1));
    4892       22745 :   return Parent && Visited.insert(Parent).second &&
    4893        2698 :          (IsRootTBAANode(Parent) || IsScalarTBAANodeImpl(Parent, Visited));
    4894             : }
    4895             : 
    4896       91956 : bool TBAAVerifier::isValidScalarTBAANode(const MDNode *MD) {
    4897       91956 :   auto ResultIt = TBAAScalarNodes.find(MD);
    4898       91956 :   if (ResultIt != TBAAScalarNodes.end())
    4899       86549 :     return ResultIt->second;
    4900             : 
    4901             :   SmallPtrSet<const MDNode *, 4> Visited;
    4902        5407 :   bool Result = IsScalarTBAANodeImpl(MD, Visited);
    4903        5407 :   auto InsertResult = TBAAScalarNodes.insert({MD, Result});
    4904             :   (void)InsertResult;
    4905             :   assert(InsertResult.second && "Just checked!");
    4906             : 
    4907             :   return Result;
    4908             : }
    4909             : 
    4910             : /// Returns the field node at the offset \p Offset in \p BaseNode.  Update \p
    4911             : /// Offset in place to be the offset within the field node returned.
    4912             : ///
    4913             : /// We assume we've okayed \p BaseNode via \c verifyTBAABaseNode.
    4914       54849 : MDNode *TBAAVerifier::getFieldNodeFromTBAABaseNode(Instruction &I,
    4915             :                                                    const MDNode *BaseNode,
    4916             :                                                    APInt &Offset,
    4917             :                                                    bool IsNewFormat) {
    4918             :   assert(BaseNode->getNumOperands() >= 2 && "Invalid base node!");
    4919             : 
    4920             :   // Scalar nodes have only one possible "field" -- their parent in the access
    4921             :   // hierarchy.  Offset must be zero at this point, but our caller is supposed
    4922             :   // to Assert that.
    4923       54849 :   if (BaseNode->getNumOperands() == 2)
    4924        5351 :     return cast<MDNode>(BaseNode->getOperand(1));
    4925             : 
    4926       49498 :   unsigned FirstFieldOpNo = IsNewFormat ? 3 : 1;
    4927       49498 :   unsigned NumOpsPerField = IsNewFormat ? 3 : 2;
    4928      159180 :   for (unsigned Idx = FirstFieldOpNo; Idx < BaseNode->getNumOperands();
    4929       54841 :            Idx += NumOpsPerField) {
    4930             :     auto *OffsetEntryCI =
    4931       55604 :         mdconst::extract<ConstantInt>(BaseNode->getOperand(Idx + 1));
    4932       55604 :     if (OffsetEntryCI->getValue().ugt(Offset)) {
    4933         763 :       if (Idx == FirstFieldOpNo) {
    4934           1 :         CheckFailed("Could not find TBAA parent in struct type node", &I,
    4935           2 :                     BaseNode, &Offset);
    4936           1 :         return nullptr;
    4937             :       }
    4938             : 
    4939         762 :       unsigned PrevIdx = Idx - NumOpsPerField;
    4940             :       auto *PrevOffsetEntryCI =
    4941         762 :           mdconst::extract<ConstantInt>(BaseNode->getOperand(PrevIdx + 1));
    4942         762 :       Offset -= PrevOffsetEntryCI->getValue();
    4943        1524 :       return cast<MDNode>(BaseNode->getOperand(PrevIdx));
    4944             :     }
    4945             :   }
    4946             : 
    4947       48735 :   unsigned LastIdx = BaseNode->getNumOperands() - NumOpsPerField;
    4948       48735 :   auto *LastOffsetEntryCI = mdconst::extract<ConstantInt>(
    4949             :       BaseNode->getOperand(LastIdx + 1));
    4950       48735 :   Offset -= LastOffsetEntryCI->getValue();
    4951       97470 :   return cast<MDNode>(BaseNode->getOperand(LastIdx));
    4952             : }
    4953             : 
    4954             : static bool isNewFormatTBAATypeNode(llvm::MDNode *Type) {
    4955       36097 :   if (!Type || Type->getNumOperands() < 3)
    4956             :     return false;
    4957             : 
    4958             :   // In the new format type nodes shall have a reference to the parent type as
    4959             :   // its first operand.
    4960             :   MDNode *Parent = dyn_cast_or_null<MDNode>(Type->getOperand(0));
    4961             :   if (!Parent)
    4962             :     return false;
    4963             : 
    4964             :   return true;
    4965             : }
    4966             : 
    4967       36098 : bool TBAAVerifier::visitTBAAMetadata(Instruction &I, const MDNode *MD) {
    4968       36098 :   AssertTBAA(isa<LoadInst>(I) || isa<StoreInst>(I) || isa<CallInst>(I) ||
    4969             :                  isa<VAArgInst>(I) || isa<AtomicRMWInst>(I) ||
    4970             :                  isa<AtomicCmpXchgInst>(I),
    4971             :              "This instruction shall not have a TBAA access tag!", &I);
    4972             : 
    4973             :   bool IsStructPathTBAA =
    4974       72195 :       isa<MDNode>(MD->getOperand(0)) && MD->getNumOperands() >= 3;
    4975             : 
    4976           1 :   AssertTBAA(
    4977             :       IsStructPathTBAA,
    4978             :       "Old-style TBAA is no longer allowed, use struct-path TBAA instead", &I);
    4979             : 
    4980       36097 :   MDNode *BaseNode = dyn_cast_or_null<MDNode>(MD->getOperand(0));
    4981       36097 :   MDNode *AccessType = dyn_cast_or_null<MDNode>(MD->getOperand(1));
    4982             : 
    4983             :   bool IsNewFormat = isNewFormatTBAATypeNode(AccessType);
    4984             : 
    4985             :   if (IsNewFormat) {
    4986         611 :     AssertTBAA(MD->getNumOperands() == 4 || MD->getNumOperands() == 5,
    4987             :                "Access tag metadata must have either 4 or 5 operands", &I, MD);
    4988             :   } else {
    4989       35486 :     AssertTBAA(MD->getNumOperands() < 5,
    4990             :                "Struct tag metadata must have either 3 or 4 operands", &I, MD);
    4991             :   }
    4992             : 
    4993             :   // Check the access size field.
    4994       36093 :   if (IsNewFormat) {
    4995             :     auto *AccessSizeNode = mdconst::dyn_extract_or_null<ConstantInt>(
    4996             :         MD->getOperand(3));
    4997           0 :     AssertTBAA(AccessSizeNode, "Access size field must be a constant", &I, MD);
    4998             :   }
    4999             : 
    5000             :   // Check the immutability flag.
    5001       36093 :   unsigned ImmutabilityFlagOpNo = IsNewFormat ? 4 : 3;
    5002       36093 :   if (MD->getNumOperands() == ImmutabilityFlagOpNo + 1) {
    5003             :     auto *IsImmutableCI = mdconst::dyn_extract_or_null<ConstantInt>(
    5004             :         MD->getOperand(ImmutabilityFlagOpNo));
    5005           1 :     AssertTBAA(IsImmutableCI,
    5006             :                "Immutability tag on struct tag metadata must be a constant",
    5007             :                &I, MD);
    5008         886 :     AssertTBAA(
    5009             :         IsImmutableCI->isZero() || IsImmutableCI->isOne(),
    5010             :         "Immutability part of the struct tag metadata must be either 0 or 1",
    5011             :         &I, MD);
    5012             :   }
    5013             : 
    5014       36091 :   AssertTBAA(BaseNode && AccessType,
    5015             :              "Malformed struct tag metadata: base and access-type "
    5016             :              "should be non-null and point to Metadata nodes",
    5017             :              &I, MD, BaseNode, AccessType);
    5018             : 
    5019       36090 :   if (!IsNewFormat) {
    5020       35481 :     AssertTBAA(isValidScalarTBAANode(AccessType),
    5021             :                "Access type node must be a valid scalar type", &I, MD,
    5022             :                AccessType);
    5023             :   }
    5024             : 
    5025       36083 :   auto *OffsetCI = mdconst::dyn_extract_or_null<ConstantInt>(MD->getOperand(2));
    5026           1 :   AssertTBAA(OffsetCI, "Offset must be constant integer", &I, MD);
    5027             : 
    5028             :   APInt Offset = OffsetCI->getValue();
    5029             :   bool SeenAccessTypeInPath = false;
    5030             : 
    5031             :   SmallPtrSet<MDNode *, 4> StructPath;
    5032             : 
    5033      236710 :   for (/* empty */; BaseNode && !IsRootTBAANode(BaseNode);
    5034       54849 :        BaseNode = getFieldNodeFromTBAABaseNode(I, BaseNode, Offset,
    5035             :                                                IsNewFormat)) {
    5036       55467 :     if (!StructPath.insert(BaseNode).second) {
    5037           1 :       CheckFailed("Cycle detected in struct path", &I, MD);
    5038          10 :       return false;
    5039             :     }
    5040             : 
    5041             :     bool Invalid;
    5042             :     unsigned BaseNodeBitWidth;
    5043      110932 :     std::tie(Invalid, BaseNodeBitWidth) = verifyTBAABaseNode(I, BaseNode,
    5044       55466 :                                                              IsNewFormat);
    5045             : 
    5046             :     // If the base node is invalid in itself, then we've already printed all the
    5047             :     // errors we wanted to print.
    5048       55466 :     if (Invalid)
    5049             :       return false;
    5050             : 
    5051       55461 :     SeenAccessTypeInPath |= BaseNode == AccessType;
    5052             : 
    5053       55461 :     if (isValidScalarTBAANode(BaseNode) || BaseNode == AccessType)
    5054       54442 :       AssertTBAA(Offset == 0, "Offset not zero at the point of scalar access",
    5055             :                  &I, MD, &Offset);
    5056             : 
    5057       55460 :     AssertTBAA(BaseNodeBitWidth == Offset.getBitWidth() ||
    5058             :                    (BaseNodeBitWidth == 0 && Offset == 0) ||
    5059             :                    (IsNewFormat && BaseNodeBitWidth == ~0u),
    5060             :                "Access bit-width not the same as description bit-width", &I, MD,
    5061             :                BaseNodeBitWidth, Offset.getBitWidth());
    5062             : 
    5063       55458 :     if (IsNewFormat && SeenAccessTypeInPath)
    5064             :       break;
    5065             :   }
    5066             : 
    5067       36073 :   AssertTBAA(SeenAccessTypeInPath, "Did not see access type in access path!",
    5068             :              &I, MD);
    5069             :   return true;
    5070             : }
    5071             : 
    5072             : char VerifierLegacyPass::ID = 0;
    5073      254616 : INITIALIZE_PASS(VerifierLegacyPass, "verify", "Module Verifier", false, false)
    5074             : 
    5075       57707 : FunctionPass *llvm::createVerifierPass(bool FatalErrors) {
    5076      115414 :   return new VerifierLegacyPass(FatalErrors);
    5077             : }
    5078             : 
    5079             : AnalysisKey VerifierAnalysis::Key;
    5080        1372 : VerifierAnalysis::Result VerifierAnalysis::run(Module &M,
    5081             :                                                ModuleAnalysisManager &) {
    5082             :   Result Res;
    5083        1372 :   Res.IRBroken = llvm::verifyModule(M, &dbgs(), &Res.DebugInfoBroken);
    5084        1372 :   return Res;
    5085             : }
    5086             : 
    5087           9 : VerifierAnalysis::Result VerifierAnalysis::run(Function &F,
    5088             :                                                FunctionAnalysisManager &) {
    5089           9 :   return { llvm::verifyFunction(F, &dbgs()), false };
    5090             : }
    5091             : 
    5092        1610 : PreservedAnalyses VerifierPass::run(Module &M, ModuleAnalysisManager &AM) {
    5093        1610 :   auto Res = AM.getResult<VerifierAnalysis>(M);
    5094        1610 :   if (FatalErrors && (Res.IRBroken || Res.DebugInfoBroken))
    5095           0 :     report_fatal_error("Broken module found, compilation aborted!");
    5096             : 
    5097        1610 :   return PreservedAnalyses::all();
    5098             : }
    5099             : 
    5100          10 : PreservedAnalyses VerifierPass::run(Function &F, FunctionAnalysisManager &AM) {
    5101          10 :   auto res = AM.getResult<VerifierAnalysis>(F);
    5102          10 :   if (res.IRBroken && FatalErrors)
    5103           0 :     report_fatal_error("Broken function found, compilation aborted!");
    5104             : 
    5105          10 :   return PreservedAnalyses::all();
    5106             : }

Generated by: LCOV version 1.13