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

Generated by: LCOV version 1.13