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