llvm/llvm/lib/IR/Verifier.cpp

//===-- Verifier.cpp - Implement the Module Verifier -----------------------==//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file defines the function verifier interface, that can be used for some
// basic correctness checking of input to the system.
//
// Note that this does not provide full `Java style' security and verifications,
// instead it just tries to ensure that code is well-formed.
//
//  * Both of a binary operator's parameters are of the same type
//  * Verify that the indices of mem access instructions match other operands
//  * Verify that arithmetic and other things are only performed on first-class
//    types.  Verify that shifts & logicals only happen on integrals f.e.
//  * All of the constants in a switch statement are of the correct type
//  * The code is in valid SSA form
//  * It should be illegal to put a label into any other type (like a structure)
//    or to return one. [except constant arrays!]
//  * Only phi nodes can be self referential: 'add i32 %0, %0 ; <int>:0' is bad
//  * PHI nodes must have an entry for each predecessor, with no extras.
//  * PHI nodes must be the first thing in a basic block, all grouped together
//  * All basic blocks should only end with terminator insts, not contain them
//  * The entry node to a function must not have predecessors
//  * All Instructions must be embedded into a basic block
//  * Functions cannot take a void-typed parameter
//  * Verify that a function's argument list agrees with it's declared type.
//  * It is illegal to specify a name for a void value.
//  * It is illegal to have a internal global value with no initializer
//  * It is illegal to have a ret instruction that returns a value that does not
//    agree with the function return value type.
//  * Function call argument types match the function prototype
//  * A landing pad is defined by a landingpad instruction, and can be jumped to
//    only by the unwind edge of an invoke instruction.
//  * A landingpad instruction must be the first non-PHI instruction in the
//    block.
//  * Landingpad instructions must be in a function with a personality function.
//  * Convergence control intrinsics are introduced in ConvergentOperations.rst.
//    The applied restrictions are too numerous to list here.
//  * The convergence entry intrinsic and the loop heart must be the first
//    non-PHI instruction in their respective block. This does not conflict with
//    the landing pads, since these two kinds cannot occur in the same block.
//  * All other things that are tested by asserts spread about the code...
//
//===----------------------------------------------------------------------===//

#include "llvm/IR/Verifier.h"
#include "llvm/ADT/APFloat.h"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/ADT/StringMap.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/ADT/Twine.h"
#include "llvm/BinaryFormat/Dwarf.h"
#include "llvm/IR/Argument.h"
#include "llvm/IR/AttributeMask.h"
#include "llvm/IR/Attributes.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/CallingConv.h"
#include "llvm/IR/Comdat.h"
#include "llvm/IR/Constant.h"
#include "llvm/IR/ConstantRange.h"
#include "llvm/IR/ConstantRangeList.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/ConvergenceVerifier.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DebugInfo.h"
#include "llvm/IR/DebugInfoMetadata.h"
#include "llvm/IR/DebugLoc.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/EHPersonalities.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/GCStrategy.h"
#include "llvm/IR/GlobalAlias.h"
#include "llvm/IR/GlobalValue.h"
#include "llvm/IR/GlobalVariable.h"
#include "llvm/IR/InlineAsm.h"
#include "llvm/IR/InstVisitor.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Intrinsics.h"
#include "llvm/IR/IntrinsicsAArch64.h"
#include "llvm/IR/IntrinsicsAMDGPU.h"
#include "llvm/IR/IntrinsicsARM.h"
#include "llvm/IR/IntrinsicsNVPTX.h"
#include "llvm/IR/IntrinsicsWebAssembly.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/MemoryModelRelaxationAnnotations.h"
#include "llvm/IR/Metadata.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/ModuleSlotTracker.h"
#include "llvm/IR/PassManager.h"
#include "llvm/IR/ProfDataUtils.h"
#include "llvm/IR/Statepoint.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Use.h"
#include "llvm/IR/User.h"
#include "llvm/IR/VFABIDemangler.h"
#include "llvm/IR/Value.h"
#include "llvm/InitializePasses.h"
#include "llvm/Pass.h"
#include "llvm/Support/AMDGPUAddrSpace.h"
#include "llvm/Support/AtomicOrdering.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/ModRef.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <memory>
#include <optional>
#include <string>
#include <utility>

usingnamespacellvm;

static cl::opt<bool> VerifyNoAliasScopeDomination(
    "verify-noalias-scope-decl-dom", cl::Hidden, cl::init(false),
    cl::desc("Ensure that llvm.experimental.noalias.scope.decl for identical "
             "scopes are not dominating"));

namespace llvm {

struct VerifierSupport { … };

} // namespace llvm

namespace {

class Verifier : public InstVisitor<Verifier>, VerifierSupport { … };

} // end anonymous namespace

/// We know that cond should be true, if not print an error message.
#define Check(C, ...) …

/// We know that a debug info condition should be true, if not print
/// an error message.
#define CheckDI(C, ...) …

void Verifier::visitDbgRecords(Instruction &I) { … }

void Verifier::visit(Instruction &I) { … }

// Helper to iterate over indirect users. By returning false, the callback can ask to stop traversing further.
static void forEachUser(const Value *User,
                        SmallPtrSet<const Value *, 32> &Visited,
                        llvm::function_ref<bool(const Value *)> Callback) { … }

void Verifier::visitGlobalValue(const GlobalValue &GV) { … }

void Verifier::visitGlobalVariable(const GlobalVariable &GV) { … }

void Verifier::visitAliaseeSubExpr(const GlobalAlias &GA, const Constant &C) { … }

void Verifier::visitAliaseeSubExpr(SmallPtrSetImpl<const GlobalAlias*> &Visited,
                                   const GlobalAlias &GA, const Constant &C) { … }

void Verifier::visitGlobalAlias(const GlobalAlias &GA) { … }

void Verifier::visitGlobalIFunc(const GlobalIFunc &GI) { … }

void Verifier::visitNamedMDNode(const NamedMDNode &NMD) { … }

void Verifier::visitMDNode(const MDNode &MD, AreDebugLocsAllowed AllowLocs) { … }

void Verifier::visitValueAsMetadata(const ValueAsMetadata &MD, Function *F) { … }

void Verifier::visitDIArgList(const DIArgList &AL, Function *F) { … }

void Verifier::visitMetadataAsValue(const MetadataAsValue &MDV, Function *F) { … }

static bool isType(const Metadata *MD) { … }
static bool isScope(const Metadata *MD) { … }
static bool isDINode(const Metadata *MD) { … }

void Verifier::visitDILocation(const DILocation &N) { … }

void Verifier::visitGenericDINode(const GenericDINode &N) { … }

void Verifier::visitDIScope(const DIScope &N) { … }

void Verifier::visitDISubrange(const DISubrange &N) { … }

void Verifier::visitDIGenericSubrange(const DIGenericSubrange &N) { … }

void Verifier::visitDIEnumerator(const DIEnumerator &N) { … }

void Verifier::visitDIBasicType(const DIBasicType &N) { … }

void Verifier::visitDIStringType(const DIStringType &N) { … }

void Verifier::visitDIDerivedType(const DIDerivedType &N) { … }

/// Detect mutually exclusive flags.
static bool hasConflictingReferenceFlags(unsigned Flags) { … }

void Verifier::visitTemplateParams(const MDNode &N, const Metadata &RawParams) { … }

void Verifier::visitDICompositeType(const DICompositeType &N) { … }

void Verifier::visitDISubroutineType(const DISubroutineType &N) { … }

void Verifier::visitDIFile(const DIFile &N) { … }

void Verifier::visitDICompileUnit(const DICompileUnit &N) { … }

void Verifier::visitDISubprogram(const DISubprogram &N) { … }

void Verifier::visitDILexicalBlockBase(const DILexicalBlockBase &N) { … }

void Verifier::visitDILexicalBlock(const DILexicalBlock &N) { … }

void Verifier::visitDILexicalBlockFile(const DILexicalBlockFile &N) { … }

void Verifier::visitDICommonBlock(const DICommonBlock &N) { … }

void Verifier::visitDINamespace(const DINamespace &N) { … }

void Verifier::visitDIMacro(const DIMacro &N) { … }

void Verifier::visitDIMacroFile(const DIMacroFile &N) { … }

void Verifier::visitDIModule(const DIModule &N) { … }

void Verifier::visitDITemplateParameter(const DITemplateParameter &N) { … }

void Verifier::visitDITemplateTypeParameter(const DITemplateTypeParameter &N) { … }

void Verifier::visitDITemplateValueParameter(
    const DITemplateValueParameter &N) { … }

void Verifier::visitDIVariable(const DIVariable &N) { … }

void Verifier::visitDIGlobalVariable(const DIGlobalVariable &N) { … }

void Verifier::visitDILocalVariable(const DILocalVariable &N) { … }

void Verifier::visitDIAssignID(const DIAssignID &N) { … }

void Verifier::visitDILabel(const DILabel &N) { … }

void Verifier::visitDIExpression(const DIExpression &N) { … }

void Verifier::visitDIGlobalVariableExpression(
    const DIGlobalVariableExpression &GVE) { … }

void Verifier::visitDIObjCProperty(const DIObjCProperty &N) { … }

void Verifier::visitDIImportedEntity(const DIImportedEntity &N) { … }

void Verifier::visitComdat(const Comdat &C) { … }

void Verifier::visitModuleIdents() { … }

void Verifier::visitModuleCommandLines() { … }

void Verifier::visitModuleFlags() { … }

void
Verifier::visitModuleFlag(const MDNode *Op,
                          DenseMap<const MDString *, const MDNode *> &SeenIDs,
                          SmallVectorImpl<const MDNode *> &Requirements) { … }

void Verifier::visitModuleFlagCGProfileEntry(const MDOperand &MDO) { … }

void Verifier::verifyAttributeTypes(AttributeSet Attrs, const Value *V) { … }

// VerifyParameterAttrs - Check the given attributes for an argument or return
// value of the specified type.  The value V is printed in error messages.
void Verifier::verifyParameterAttrs(AttributeSet Attrs, Type *Ty,
                                    const Value *V) { … }

void Verifier::checkUnsignedBaseTenFuncAttr(AttributeList Attrs, StringRef Attr,
                                            const Value *V) { … }

// Check parameter attributes against a function type.
// The value V is printed in error messages.
void Verifier::verifyFunctionAttrs(FunctionType *FT, AttributeList Attrs,
                                   const Value *V, bool IsIntrinsic,
                                   bool IsInlineAsm) { … }

void Verifier::verifyFunctionMetadata(
    ArrayRef<std::pair<unsigned, MDNode *>> MDs) { … }

void Verifier::visitConstantExprsRecursively(const Constant *EntryC) { … }

void Verifier::visitConstantExpr(const ConstantExpr *CE) { … }

void Verifier::visitConstantPtrAuth(const ConstantPtrAuth *CPA) { … }

bool Verifier::verifyAttributeCount(AttributeList Attrs, unsigned Params) { … }

void Verifier::verifyInlineAsmCall(const CallBase &Call) { … }

/// Verify that statepoint intrinsic is well formed.
void Verifier::verifyStatepoint(const CallBase &Call) { … }

void Verifier::verifyFrameRecoverIndices() { … }

static Instruction *getSuccPad(Instruction *Terminator) { … }

void Verifier::verifySiblingFuncletUnwinds() { … }

// visitFunction - Verify that a function is ok.
//
void Verifier::visitFunction(const Function &F) { … }

// verifyBasicBlock - Verify that a basic block is well formed...
//
void Verifier::visitBasicBlock(BasicBlock &BB) { … }

void Verifier::visitTerminator(Instruction &I) { … }

void Verifier::visitBranchInst(BranchInst &BI) { … }

void Verifier::visitReturnInst(ReturnInst &RI) { … }

void Verifier::visitSwitchInst(SwitchInst &SI) { … }

void Verifier::visitIndirectBrInst(IndirectBrInst &BI) { … }

void Verifier::visitCallBrInst(CallBrInst &CBI) { … }

void Verifier::visitSelectInst(SelectInst &SI) { … }

/// visitUserOp1 - User defined operators shouldn't live beyond the lifetime of
/// a pass, if any exist, it's an error.
///
void Verifier::visitUserOp1(Instruction &I) { … }

void Verifier::visitTruncInst(TruncInst &I) { … }

void Verifier::visitZExtInst(ZExtInst &I) { … }

void Verifier::visitSExtInst(SExtInst &I) { … }

void Verifier::visitFPTruncInst(FPTruncInst &I) { … }

void Verifier::visitFPExtInst(FPExtInst &I) { … }

void Verifier::visitUIToFPInst(UIToFPInst &I) { … }

void Verifier::visitSIToFPInst(SIToFPInst &I) { … }

void Verifier::visitFPToUIInst(FPToUIInst &I) { … }

void Verifier::visitFPToSIInst(FPToSIInst &I) { … }

void Verifier::visitPtrToIntInst(PtrToIntInst &I) { … }

void Verifier::visitIntToPtrInst(IntToPtrInst &I) { … }

void Verifier::visitBitCastInst(BitCastInst &I) { … }

void Verifier::visitAddrSpaceCastInst(AddrSpaceCastInst &I) { … }

/// visitPHINode - Ensure that a PHI node is well formed.
///
void Verifier::visitPHINode(PHINode &PN) { … }

void Verifier::visitCallBase(CallBase &Call) { … }

void Verifier::verifyTailCCMustTailAttrs(const AttrBuilder &Attrs,
                                         StringRef Context) { … }

/// Two types are "congruent" if they are identical, or if they are both pointer
/// types with different pointee types and the same address space.
static bool isTypeCongruent(Type *L, Type *R) { … }

static AttrBuilder getParameterABIAttributes(LLVMContext& C, unsigned I, AttributeList Attrs) { … }

void Verifier::verifyMustTailCall(CallInst &CI) { … }

void Verifier::visitCallInst(CallInst &CI) { … }

void Verifier::visitInvokeInst(InvokeInst &II) { … }

/// visitUnaryOperator - Check the argument to the unary operator.
///
void Verifier::visitUnaryOperator(UnaryOperator &U) { … }

/// visitBinaryOperator - Check that both arguments to the binary operator are
/// of the same type!
///
void Verifier::visitBinaryOperator(BinaryOperator &B) { … }

void Verifier::visitICmpInst(ICmpInst &IC) { … }

void Verifier::visitFCmpInst(FCmpInst &FC) { … }

void Verifier::visitExtractElementInst(ExtractElementInst &EI) { … }

void Verifier::visitInsertElementInst(InsertElementInst &IE) { … }

void Verifier::visitShuffleVectorInst(ShuffleVectorInst &SV) { … }

void Verifier::visitGetElementPtrInst(GetElementPtrInst &GEP) { … }

static bool isContiguous(const ConstantRange &A, const ConstantRange &B) { … }

/// Verify !range and !absolute_symbol metadata. These have the same
/// restrictions, except !absolute_symbol allows the full set.
void Verifier::verifyRangeMetadata(const Value &I, const MDNode *Range,
                                   Type *Ty, bool IsAbsoluteSymbol) { … }

void Verifier::visitRangeMetadata(Instruction &I, MDNode *Range, Type *Ty) { … }

void Verifier::checkAtomicMemAccessSize(Type *Ty, const Instruction *I) { … }

void Verifier::visitLoadInst(LoadInst &LI) { … }

void Verifier::visitStoreInst(StoreInst &SI) { … }

/// Check that SwiftErrorVal is used as a swifterror argument in CS.
void Verifier::verifySwiftErrorCall(CallBase &Call,
                                    const Value *SwiftErrorVal) { … }

void Verifier::verifySwiftErrorValue(const Value *SwiftErrorVal) { … }

void Verifier::visitAllocaInst(AllocaInst &AI) { … }

void Verifier::visitAtomicCmpXchgInst(AtomicCmpXchgInst &CXI) { … }

void Verifier::visitAtomicRMWInst(AtomicRMWInst &RMWI) { … }

void Verifier::visitFenceInst(FenceInst &FI) { … }

void Verifier::visitExtractValueInst(ExtractValueInst &EVI) { … }

void Verifier::visitInsertValueInst(InsertValueInst &IVI) { … }

static Value *getParentPad(Value *EHPad) { … }

void Verifier::visitEHPadPredecessors(Instruction &I) { … }

void Verifier::visitLandingPadInst(LandingPadInst &LPI) { … }

void Verifier::visitResumeInst(ResumeInst &RI) { … }

void Verifier::visitCatchPadInst(CatchPadInst &CPI) { … }

void Verifier::visitCatchReturnInst(CatchReturnInst &CatchReturn) { … }

void Verifier::visitCleanupPadInst(CleanupPadInst &CPI) { … }

void Verifier::visitFuncletPadInst(FuncletPadInst &FPI) { … }

void Verifier::visitCatchSwitchInst(CatchSwitchInst &CatchSwitch) { … }

void Verifier::visitCleanupReturnInst(CleanupReturnInst &CRI) { … }

void Verifier::verifyDominatesUse(Instruction &I, unsigned i) { … }

void Verifier::visitDereferenceableMetadata(Instruction& I, MDNode* MD) { … }

void Verifier::visitProfMetadata(Instruction &I, MDNode *MD) { … }

void Verifier::visitDIAssignIDMetadata(Instruction &I, MDNode *MD) { … }

void Verifier::visitMMRAMetadata(Instruction &I, MDNode *MD) { … }

void Verifier::visitCallStackMetadata(MDNode *MD) { … }

void Verifier::visitMemProfMetadata(Instruction &I, MDNode *MD) { … }

void Verifier::visitCallsiteMetadata(Instruction &I, MDNode *MD) { … }

void Verifier::visitAnnotationMetadata(MDNode *Annotation) { … }

void Verifier::visitAliasScopeMetadata(const MDNode *MD) { … }

void Verifier::visitAliasScopeListMetadata(const MDNode *MD) { … }

void Verifier::visitAccessGroupMetadata(const MDNode *MD) { … }

/// verifyInstruction - Verify that an instruction is well formed.
///
void Verifier::visitInstruction(Instruction &I) { … }

/// Allow intrinsics to be verified in different ways.
void Verifier::visitIntrinsicCall(Intrinsic::ID ID, CallBase &Call) { … }

/// Carefully grab the subprogram from a local scope.
///
/// This carefully grabs the subprogram from a local scope, avoiding the
/// built-in assertions that would typically fire.
static DISubprogram *getSubprogram(Metadata *LocalScope) { … }

void Verifier::visit(DbgLabelRecord &DLR) { … }

void Verifier::visit(DbgVariableRecord &DVR) { … }

void Verifier::visitVPIntrinsic(VPIntrinsic &VPI) { … }

void Verifier::visitConstrainedFPIntrinsic(ConstrainedFPIntrinsic &FPI) { … }

void Verifier::visitDbgIntrinsic(StringRef Kind, DbgVariableIntrinsic &DII) { … }

void Verifier::visitDbgLabelIntrinsic(StringRef Kind, DbgLabelInst &DLI) { … }

void Verifier::verifyFragmentExpression(const DbgVariableIntrinsic &I) { … }
void Verifier::verifyFragmentExpression(const DbgVariableRecord &DVR) { … }

template <typename ValueOrMetadata>
void Verifier::verifyFragmentExpression(const DIVariable &V,
                                        DIExpression::FragmentInfo Fragment,
                                        ValueOrMetadata *Desc) { … }

void Verifier::verifyFnArgs(const DbgVariableIntrinsic &I) { … }
void Verifier::verifyFnArgs(const DbgVariableRecord &DVR) { … }

void Verifier::verifyNotEntryValue(const DbgVariableIntrinsic &I) { … }
void Verifier::verifyNotEntryValue(const DbgVariableRecord &DVR) { … }

void Verifier::verifyCompileUnits() { … }

void Verifier::verifyDeoptimizeCallingConvs() { … }

void Verifier::verifyAttachedCallBundle(const CallBase &Call,
                                        const OperandBundleUse &BU) { … }

void Verifier::verifyNoAliasScopeDecl() { … }

//===----------------------------------------------------------------------===//
//  Implement the public interfaces to this file...
//===----------------------------------------------------------------------===//

bool llvm::verifyFunction(const Function &f, raw_ostream *OS) { … }

bool llvm::verifyModule(const Module &M, raw_ostream *OS,
                        bool *BrokenDebugInfo) { … }

namespace {

struct VerifierLegacyPass : public FunctionPass { … };

} // end anonymous namespace

/// Helper to issue failure from the TBAA verification
template <typename... Tys> void TBAAVerifier::CheckFailed(Tys &&... Args) { … }

#define CheckTBAA(C, ...) …

/// Verify that \p BaseNode can be used as the "base type" in the struct-path
/// TBAA scheme.  This means \p BaseNode is either a scalar node, or a
/// struct-type node describing an aggregate data structure (like a struct).
TBAAVerifier::TBAABaseNodeSummary
TBAAVerifier::verifyTBAABaseNode(Instruction &I, const MDNode *BaseNode,
                                 bool IsNewFormat) { … }

TBAAVerifier::TBAABaseNodeSummary
TBAAVerifier::verifyTBAABaseNodeImpl(Instruction &I, const MDNode *BaseNode,
                                     bool IsNewFormat) { … }

static bool IsRootTBAANode(const MDNode *MD) { … }

static bool IsScalarTBAANodeImpl(const MDNode *MD,
                                 SmallPtrSetImpl<const MDNode *> &Visited) { … }

bool TBAAVerifier::isValidScalarTBAANode(const MDNode *MD) { … }

/// Returns the field node at the offset \p Offset in \p BaseNode.  Update \p
/// Offset in place to be the offset within the field node returned.
///
/// We assume we've okayed \p BaseNode via \c verifyTBAABaseNode.
MDNode *TBAAVerifier::getFieldNodeFromTBAABaseNode(Instruction &I,
                                                   const MDNode *BaseNode,
                                                   APInt &Offset,
                                                   bool IsNewFormat) { … }

static bool isNewFormatTBAATypeNode(llvm::MDNode *Type) { … }

bool TBAAVerifier::visitTBAAMetadata(Instruction &I, const MDNode *MD) { … }

char VerifierLegacyPass::ID = …;
INITIALIZE_PASS(…)

FunctionPass *llvm::createVerifierPass(bool FatalErrors) { … }

AnalysisKey VerifierAnalysis::Key;
VerifierAnalysis::Result VerifierAnalysis::run(Module &M,
                                               ModuleAnalysisManager &) { … }

VerifierAnalysis::Result VerifierAnalysis::run(Function &F,
                                               FunctionAnalysisManager &) { … }

PreservedAnalyses VerifierPass::run(Module &M, ModuleAnalysisManager &AM) { … }

PreservedAnalyses VerifierPass::run(Function &F, FunctionAnalysisManager &AM) { … }