contrib/llvm/lib/IR/Verifier.cpp

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