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