Index: llvm/trunk/include/llvm/IR/Verifier.h =================================================================== --- llvm/trunk/include/llvm/IR/Verifier.h +++ llvm/trunk/include/llvm/IR/Verifier.h @@ -23,6 +23,10 @@ #include "llvm/IR/PassManager.h" +namespace { +struct VerifierSupport; +} + namespace llvm { class Function; @@ -31,6 +35,41 @@ class Module; class raw_ostream; +/// Verify that the TBAA Metadatas are valid. +class TBAAVerifier { + VerifierSupport *Diagnostic = nullptr; + + /// Helper to diagnose a failure + template void CheckFailed(Tys &&... Args); + + /// Cache of TBAA base nodes that have already been visited. This cachce maps + /// a node that has been visited to a pair (IsInvalid, BitWidth) where + /// + /// \c IsInvalid is true iff the node is invalid. + /// \c BitWidth, if non-zero, is the bitwidth of the integer used to denoting + /// the offset of the access. If zero, only a zero offset is allowed. + /// + /// \c BitWidth has no meaning if \c IsInvalid is true. + typedef std::pair TBAABaseNodeSummary; + DenseMap TBAABaseNodes; + + /// \name Helper functions used by \c visitTBAAMetadata. + /// @{ + MDNode *getFieldNodeFromTBAABaseNode(Instruction &I, MDNode *BaseNode, + APInt &Offset); + TBAAVerifier::TBAABaseNodeSummary verifyTBAABaseNode(Instruction &I, + MDNode *BaseNode); + TBAABaseNodeSummary verifyTBAABaseNodeImpl(Instruction &I, MDNode *BaseNode); + /// @} + +public: + TBAAVerifier(VerifierSupport *Diagnostic = nullptr) + : Diagnostic(Diagnostic) {} + // Visit an instruction and return true if it is valid, return false it an + // invalid TBAA is attached. + bool visitTBAAMetadata(Instruction &I, MDNode *MD); +}; + /// \brief Check a function for errors, useful for use when debugging a /// pass. /// Index: llvm/trunk/lib/IR/Verifier.cpp =================================================================== --- llvm/trunk/lib/IR/Verifier.cpp +++ llvm/trunk/lib/IR/Verifier.cpp @@ -293,16 +293,7 @@ // constant expressions, we can arrive at a particular user many times. SmallPtrSet GlobalValueVisited; - /// Cache of TBAA base nodes that have already been visited. This cachce maps - /// a node that has been visited to a pair (IsInvalid, BitWidth) where - /// - /// \c IsInvalid is true iff the node is invalid. - /// \c BitWidth, if non-zero, is the bitwidth of the integer used to denoting - /// the offset of the access. If zero, only a zero offset is allowed. - /// - /// \c BitWidth has no meaning if \c IsInvalid is true. - typedef std::pair TBAABaseNodeSummary; - DenseMap TBAABaseNodes; + TBAAVerifier TBAAVerifyHelper; void checkAtomicMemAccessSize(Type *Ty, const Instruction *I); @@ -310,7 +301,7 @@ explicit Verifier(raw_ostream *OS, bool ShouldTreatBrokenDebugInfoAsError, const Module &M) : VerifierSupport(OS, M), LandingPadResultTy(nullptr), - SawFrameEscape(false) { + SawFrameEscape(false), TBAAVerifyHelper(this) { TreatBrokenDebugInfoAsError = ShouldTreatBrokenDebugInfoAsError; } @@ -410,15 +401,6 @@ void visitBasicBlock(BasicBlock &BB); void visitRangeMetadata(Instruction &I, MDNode *Range, Type *Ty); void visitDereferenceableMetadata(Instruction &I, MDNode *MD); - void visitTBAAMetadata(Instruction &I, MDNode *MD); - - /// \name Helper functions used by \c visitTBAAMetadata. - /// @{ - MDNode *getFieldNodeFromTBAABaseNode(Instruction &I, MDNode *BaseNode, - APInt &Offset); - TBAABaseNodeSummary verifyTBAABaseNode(Instruction &I, MDNode *BaseNode); - TBAABaseNodeSummary verifyTBAABaseNodeImpl(Instruction &I, MDNode *BaseNode); - /// @} template bool isValidMetadataArray(const MDTuple &N); #define HANDLE_SPECIALIZED_MDNODE_LEAF(CLASS) void visit##CLASS(const CLASS &N); @@ -3700,247 +3682,6 @@ "dereferenceable_or_null metadata value must be an i64!", &I); } -/// 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). -Verifier::TBAABaseNodeSummary Verifier::verifyTBAABaseNode(Instruction &I, - MDNode *BaseNode) { - if (BaseNode->getNumOperands() < 2) { - CheckFailed("Base nodes must have at least two operands", &I, BaseNode); - return {true, ~0u}; - } - - auto Itr = TBAABaseNodes.find(BaseNode); - if (Itr != TBAABaseNodes.end()) - return Itr->second; - - auto Result = verifyTBAABaseNodeImpl(I, BaseNode); - auto InsertResult = TBAABaseNodes.insert({BaseNode, Result}); - (void)InsertResult; - assert(InsertResult.second && "We just checked!"); - return Result; -} - -Verifier::TBAABaseNodeSummary -Verifier::verifyTBAABaseNodeImpl(Instruction &I, MDNode *BaseNode) { - const Verifier::TBAABaseNodeSummary InvalidNode = {true, ~0u}; - - if (BaseNode->getNumOperands() == 2) { - // This is a scalar base node. - if (!BaseNode->getOperand(0) || !BaseNode->getOperand(1)) { - CheckFailed("Null operands in scalar type nodes!", &I, BaseNode); - return InvalidNode; - } - if (!isa(BaseNode->getOperand(1))) { - CheckFailed("Invalid parent operand in scalar TBAA node", &I, BaseNode); - return InvalidNode; - } - if (!isa(BaseNode->getOperand(0))) { - CheckFailed("Invalid name operand in scalar TBAA node", &I, BaseNode); - return InvalidNode; - } - - // Scalar nodes can only be accessed at offset 0. - return {false, 0}; - } - - if (BaseNode->getNumOperands() % 2 != 1) { - CheckFailed("Struct tag nodes must have an odd number of operands!", - BaseNode); - return InvalidNode; - } - - bool Failed = false; - - Optional PrevOffset; - unsigned BitWidth = ~0u; - - // We've already checked that BaseNode is not a degenerate root node with one - // operand in \c verifyTBAABaseNode, so this loop should run at least once. - for (unsigned Idx = 1; Idx < BaseNode->getNumOperands(); Idx += 2) { - const MDOperand &FieldTy = BaseNode->getOperand(Idx); - const MDOperand &FieldOffset = BaseNode->getOperand(Idx + 1); - if (!isa(FieldTy)) { - CheckFailed("Incorrect field entry in struct type node!", &I, BaseNode); - Failed = true; - continue; - } - - auto *OffsetEntryCI = - mdconst::dyn_extract_or_null(FieldOffset); - if (!OffsetEntryCI) { - CheckFailed("Offset entries must be constants!", &I, BaseNode); - Failed = true; - continue; - } - - if (BitWidth == ~0u) - BitWidth = OffsetEntryCI->getBitWidth(); - - if (OffsetEntryCI->getBitWidth() != BitWidth) { - CheckFailed( - "Bitwidth between the offsets and struct type entries must match", &I, - BaseNode); - Failed = true; - continue; - } - - // NB! As far as I can tell, we generate a non-strictly increasing offset - // sequence only from structs that have zero size bit fields. When - // recursing into a contained struct in \c getFieldNodeFromTBAABaseNode we - // pick the field lexically the latest in struct type metadata node. This - // mirrors the actual behavior of the alias analysis implementation. - bool IsAscending = - !PrevOffset || PrevOffset->ule(OffsetEntryCI->getValue()); - - if (!IsAscending) { - CheckFailed("Offsets must be increasing!", &I, BaseNode); - Failed = true; - } - - PrevOffset = OffsetEntryCI->getValue(); - } - - return Failed ? InvalidNode : Verifier::TBAABaseNodeSummary(false, BitWidth); -} - -static bool IsRootTBAANode(const MDNode *MD) { - return MD->getNumOperands() < 2; -} - -static bool IsScalarTBAANodeImpl(const MDNode *MD, - SmallPtrSetImpl &Visited) { - if (MD->getNumOperands() == 2) - return true; - - if (MD->getNumOperands() != 3) - return false; - - auto *Offset = mdconst::dyn_extract(MD->getOperand(2)); - if (!(Offset && Offset->isZero() && isa(MD->getOperand(0)))) - return false; - - auto *Parent = dyn_cast(MD->getOperand(1)); - return Visited.insert(Parent).second && - (IsRootTBAANode(Parent) || IsScalarTBAANodeImpl(Parent, Visited)); -} - -static bool IsScalarTBAANode(const MDNode *MD) { - SmallPtrSet Visited; - return IsScalarTBAANodeImpl(MD, Visited); -} - -/// 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 *Verifier::getFieldNodeFromTBAABaseNode(Instruction &I, MDNode *BaseNode, - APInt &Offset) { - assert(BaseNode->getNumOperands() >= 2 && "Invalid base node!"); - - // Scalar nodes have only one possible "field" -- their parent in the access - // hierarchy. Offset must be zero at this point, but our caller is supposed - // to Assert that. - if (BaseNode->getNumOperands() == 2) - return cast(BaseNode->getOperand(1)); - - for (unsigned Idx = 1; Idx < BaseNode->getNumOperands(); Idx += 2) { - auto *OffsetEntryCI = - mdconst::extract(BaseNode->getOperand(Idx + 1)); - if (OffsetEntryCI->getValue().ugt(Offset)) { - if (Idx == 1) { - CheckFailed("Could not find TBAA parent in struct type node", &I, - BaseNode, &Offset); - return nullptr; - } - - auto *PrevOffsetEntryCI = - mdconst::extract(BaseNode->getOperand(Idx - 1)); - Offset -= PrevOffsetEntryCI->getValue(); - return cast(BaseNode->getOperand(Idx - 2)); - } - } - - auto *LastOffsetEntryCI = mdconst::extract( - BaseNode->getOperand(BaseNode->getNumOperands() - 1)); - - Offset -= LastOffsetEntryCI->getValue(); - return cast(BaseNode->getOperand(BaseNode->getNumOperands() - 2)); -} - -void Verifier::visitTBAAMetadata(Instruction &I, MDNode *MD) { - bool IsStructPathTBAA = - isa(MD->getOperand(0)) && MD->getNumOperands() >= 3; - - Assert(IsStructPathTBAA, - "Old-style TBAA is no longer allowed, use struct-path TBAA instead", - &I); - - Assert(MD->getNumOperands() < 5, - "Struct tag metadata must have either 3 or 4 operands", &I, MD); - - MDNode *BaseNode = dyn_cast_or_null(MD->getOperand(0)); - MDNode *AccessType = dyn_cast_or_null(MD->getOperand(1)); - - if (MD->getNumOperands() == 4) { - auto *IsImmutableCI = - mdconst::dyn_extract_or_null(MD->getOperand(3)); - Assert(IsImmutableCI, - "Immutability tag on struct tag metadata must be a constant", &I, - MD); - Assert(IsImmutableCI->isZero() || IsImmutableCI->isOne(), - "Immutability part of the struct tag metadata must be either 0 or 1", - &I, MD); - } - - Assert(BaseNode && AccessType, - "Malformed struct tag metadata: base and access-type " - "should be non-null and point to Metadata nodes", - &I, MD, BaseNode, AccessType); - - Assert(IsScalarTBAANode(AccessType), "Access type node must be scalar", &I, - MD, AccessType); - - auto *OffsetCI = mdconst::dyn_extract_or_null(MD->getOperand(2)); - Assert(OffsetCI, "Offset must be constant integer", &I, MD); - - APInt Offset = OffsetCI->getValue(); - bool SeenAccessTypeInPath = false; - - SmallPtrSet StructPath; - - for (/* empty */; BaseNode && !IsRootTBAANode(BaseNode); - BaseNode = getFieldNodeFromTBAABaseNode(I, BaseNode, Offset)) { - if (!StructPath.insert(BaseNode).second) { - CheckFailed("Cycle detected in struct path", &I, MD); - return; - } - - bool Invalid; - unsigned BaseNodeBitWidth; - std::tie(Invalid, BaseNodeBitWidth) = verifyTBAABaseNode(I, BaseNode); - - // If the base node is invalid in itself, then we've already printed all the - // errors we wanted to print. - if (Invalid) - return; - - SeenAccessTypeInPath |= BaseNode == AccessType; - - if (IsScalarTBAANode(BaseNode) || BaseNode == AccessType) - Assert(Offset == 0, "Offset not zero at the point of scalar access", &I, - MD, &Offset); - - Assert(BaseNodeBitWidth == Offset.getBitWidth() || - (BaseNodeBitWidth == 0 && Offset == 0), - "Access bit-width not the same as description bit-width", &I, MD, - BaseNodeBitWidth, Offset.getBitWidth()); - } - - Assert(SeenAccessTypeInPath, "Did not see access type in access path!", &I, - MD); -} - /// verifyInstruction - Verify that an instruction is well formed. /// void Verifier::visitInstruction(Instruction &I) { @@ -4076,13 +3817,8 @@ if (MDNode *MD = I.getMetadata(LLVMContext::MD_dereferenceable_or_null)) visitDereferenceableMetadata(I, MD); - if (MDNode *TBAA = I.getMetadata(LLVMContext::MD_tbaa)) { - Assert(isa(I) || isa(I) || isa(I) || - isa(I) || isa(I) || - isa(I), - "TBAA is only for loads, stores and calls!", &I); - visitTBAAMetadata(I, TBAA); - } + if (MDNode *TBAA = I.getMetadata(LLVMContext::MD_tbaa)) + TBAAVerifyHelper.visitTBAAMetadata(I, TBAA); if (MDNode *AlignMD = I.getMetadata(LLVMContext::MD_align)) { Assert(I.getType()->isPointerTy(), "align applies only to pointer types", @@ -4746,6 +4482,270 @@ } // end anonymous namespace +/// Helper to issue failure from the TBAA verification +template void TBAAVerifier::CheckFailed(Tys &&... Args) { + if (Diagnostic) + return Diagnostic->CheckFailed(Args...); +} + +#define AssertTBAA(C, ...) \ + do { \ + if (!(C)) { \ + CheckFailed(__VA_ARGS__); \ + return false; \ + } \ + } while (false) + +/// 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, MDNode *BaseNode) { + if (BaseNode->getNumOperands() < 2) { + CheckFailed("Base nodes must have at least two operands", &I, BaseNode); + return {true, ~0u}; + } + + auto Itr = TBAABaseNodes.find(BaseNode); + if (Itr != TBAABaseNodes.end()) + return Itr->second; + + auto Result = verifyTBAABaseNodeImpl(I, BaseNode); + auto InsertResult = TBAABaseNodes.insert({BaseNode, Result}); + (void)InsertResult; + assert(InsertResult.second && "We just checked!"); + return Result; +} + +TBAAVerifier::TBAABaseNodeSummary +TBAAVerifier::verifyTBAABaseNodeImpl(Instruction &I, MDNode *BaseNode) { + const TBAAVerifier::TBAABaseNodeSummary InvalidNode = {true, ~0u}; + + if (BaseNode->getNumOperands() == 2) { + // This is a scalar base node. + if (!BaseNode->getOperand(0) || !BaseNode->getOperand(1)) { + CheckFailed("Null operands in scalar type nodes!", &I, BaseNode); + return InvalidNode; + } + if (!isa(BaseNode->getOperand(1))) { + CheckFailed("Invalid parent operand in scalar TBAA node", &I, BaseNode); + return InvalidNode; + } + if (!isa(BaseNode->getOperand(0))) { + CheckFailed("Invalid name operand in scalar TBAA node", &I, BaseNode); + return InvalidNode; + } + + // Scalar nodes can only be accessed at offset 0. + return {false, 0}; + } + + if (BaseNode->getNumOperands() % 2 != 1) { + CheckFailed("Struct tag nodes must have an odd number of operands!", + BaseNode); + return InvalidNode; + } + + bool Failed = false; + + Optional PrevOffset; + unsigned BitWidth = ~0u; + + // We've already checked that BaseNode is not a degenerate root node with one + // operand in \c verifyTBAABaseNode, so this loop should run at least once. + for (unsigned Idx = 1; Idx < BaseNode->getNumOperands(); Idx += 2) { + const MDOperand &FieldTy = BaseNode->getOperand(Idx); + const MDOperand &FieldOffset = BaseNode->getOperand(Idx + 1); + if (!isa(FieldTy)) { + CheckFailed("Incorrect field entry in struct type node!", &I, BaseNode); + Failed = true; + continue; + } + + auto *OffsetEntryCI = + mdconst::dyn_extract_or_null(FieldOffset); + if (!OffsetEntryCI) { + CheckFailed("Offset entries must be constants!", &I, BaseNode); + Failed = true; + continue; + } + + if (BitWidth == ~0u) + BitWidth = OffsetEntryCI->getBitWidth(); + + if (OffsetEntryCI->getBitWidth() != BitWidth) { + CheckFailed( + "Bitwidth between the offsets and struct type entries must match", &I, + BaseNode); + Failed = true; + continue; + } + + // NB! As far as I can tell, we generate a non-strictly increasing offset + // sequence only from structs that have zero size bit fields. When + // recursing into a contained struct in \c getFieldNodeFromTBAABaseNode we + // pick the field lexically the latest in struct type metadata node. This + // mirrors the actual behavior of the alias analysis implementation. + bool IsAscending = + !PrevOffset || PrevOffset->ule(OffsetEntryCI->getValue()); + + if (!IsAscending) { + CheckFailed("Offsets must be increasing!", &I, BaseNode); + Failed = true; + } + + PrevOffset = OffsetEntryCI->getValue(); + } + + return Failed ? InvalidNode + : TBAAVerifier::TBAABaseNodeSummary(false, BitWidth); +} + +static bool IsRootTBAANode(const MDNode *MD) { + return MD->getNumOperands() < 2; +} + +static bool IsScalarTBAANodeImpl(const MDNode *MD, + SmallPtrSetImpl &Visited) { + if (MD->getNumOperands() == 2) + return true; + + if (MD->getNumOperands() != 3) + return false; + + auto *Offset = mdconst::dyn_extract(MD->getOperand(2)); + if (!(Offset && Offset->isZero() && isa(MD->getOperand(0)))) + return false; + + auto *Parent = dyn_cast(MD->getOperand(1)); + return Visited.insert(Parent).second && + (IsRootTBAANode(Parent) || IsScalarTBAANodeImpl(Parent, Visited)); +} + +static bool IsScalarTBAANode(const MDNode *MD) { + SmallPtrSet Visited; + return IsScalarTBAANodeImpl(MD, Visited); +} + +/// 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, + MDNode *BaseNode, + APInt &Offset) { + assert(BaseNode->getNumOperands() >= 2 && "Invalid base node!"); + + // Scalar nodes have only one possible "field" -- their parent in the access + // hierarchy. Offset must be zero at this point, but our caller is supposed + // to Assert that. + if (BaseNode->getNumOperands() == 2) + return cast(BaseNode->getOperand(1)); + + for (unsigned Idx = 1; Idx < BaseNode->getNumOperands(); Idx += 2) { + auto *OffsetEntryCI = + mdconst::extract(BaseNode->getOperand(Idx + 1)); + if (OffsetEntryCI->getValue().ugt(Offset)) { + if (Idx == 1) { + CheckFailed("Could not find TBAA parent in struct type node", &I, + BaseNode, &Offset); + return nullptr; + } + + auto *PrevOffsetEntryCI = + mdconst::extract(BaseNode->getOperand(Idx - 1)); + Offset -= PrevOffsetEntryCI->getValue(); + return cast(BaseNode->getOperand(Idx - 2)); + } + } + + auto *LastOffsetEntryCI = mdconst::extract( + BaseNode->getOperand(BaseNode->getNumOperands() - 1)); + + Offset -= LastOffsetEntryCI->getValue(); + return cast(BaseNode->getOperand(BaseNode->getNumOperands() - 2)); +} + +bool TBAAVerifier::visitTBAAMetadata(Instruction &I, MDNode *MD) { + AssertTBAA(isa(I) || isa(I) || isa(I) || + isa(I) || isa(I) || + isa(I), + "TBAA is only for loads, stores and calls!", &I); + + bool IsStructPathTBAA = + isa(MD->getOperand(0)) && MD->getNumOperands() >= 3; + + AssertTBAA( + IsStructPathTBAA, + "Old-style TBAA is no longer allowed, use struct-path TBAA instead", &I); + + AssertTBAA(MD->getNumOperands() < 5, + "Struct tag metadata must have either 3 or 4 operands", &I, MD); + + MDNode *BaseNode = dyn_cast_or_null(MD->getOperand(0)); + MDNode *AccessType = dyn_cast_or_null(MD->getOperand(1)); + + if (MD->getNumOperands() == 4) { + auto *IsImmutableCI = + mdconst::dyn_extract_or_null(MD->getOperand(3)); + AssertTBAA(IsImmutableCI, + "Immutability tag on struct tag metadata must be a constant", &I, + MD); + AssertTBAA( + IsImmutableCI->isZero() || IsImmutableCI->isOne(), + "Immutability part of the struct tag metadata must be either 0 or 1", + &I, MD); + } + + AssertTBAA(BaseNode && AccessType, + "Malformed struct tag metadata: base and access-type " + "should be non-null and point to Metadata nodes", + &I, MD, BaseNode, AccessType); + + AssertTBAA(IsScalarTBAANode(AccessType), "Access type node must be scalar", + &I, MD, AccessType); + + auto *OffsetCI = mdconst::dyn_extract_or_null(MD->getOperand(2)); + AssertTBAA(OffsetCI, "Offset must be constant integer", &I, MD); + + APInt Offset = OffsetCI->getValue(); + bool SeenAccessTypeInPath = false; + + SmallPtrSet StructPath; + + for (/* empty */; BaseNode && !IsRootTBAANode(BaseNode); + BaseNode = getFieldNodeFromTBAABaseNode(I, BaseNode, Offset)) { + if (!StructPath.insert(BaseNode).second) { + CheckFailed("Cycle detected in struct path", &I, MD); + return false; + } + + bool Invalid; + unsigned BaseNodeBitWidth; + std::tie(Invalid, BaseNodeBitWidth) = verifyTBAABaseNode(I, BaseNode); + + // If the base node is invalid in itself, then we've already printed all the + // errors we wanted to print. + if (Invalid) + return false; + + SeenAccessTypeInPath |= BaseNode == AccessType; + + if (IsScalarTBAANode(BaseNode) || BaseNode == AccessType) + AssertTBAA(Offset == 0, "Offset not zero at the point of scalar access", + &I, MD, &Offset); + + AssertTBAA(BaseNodeBitWidth == Offset.getBitWidth() || + (BaseNodeBitWidth == 0 && Offset == 0), + "Access bit-width not the same as description bit-width", &I, MD, + BaseNodeBitWidth, Offset.getBitWidth()); + } + + AssertTBAA(SeenAccessTypeInPath, "Did not see access type in access path!", + &I, MD); + return true; +} + char VerifierLegacyPass::ID = 0; INITIALIZE_PASS(VerifierLegacyPass, "verify", "Module Verifier", false, false)