lib/IR/Verifier.cpp

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