diff options
Diffstat (limited to 'contrib/llvm/lib/Analysis/TypeBasedAliasAnalysis.cpp')
| -rw-r--r-- | contrib/llvm/lib/Analysis/TypeBasedAliasAnalysis.cpp | 654 |
1 files changed, 315 insertions, 339 deletions
diff --git a/contrib/llvm/lib/Analysis/TypeBasedAliasAnalysis.cpp b/contrib/llvm/lib/Analysis/TypeBasedAliasAnalysis.cpp index 4e9c6f6..805f3ef 100644 --- a/contrib/llvm/lib/Analysis/TypeBasedAliasAnalysis.cpp +++ b/contrib/llvm/lib/Analysis/TypeBasedAliasAnalysis.cpp @@ -121,15 +121,13 @@ // //===----------------------------------------------------------------------===// -#include "llvm/Analysis/Passes.h" -#include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/Analysis/TypeBasedAliasAnalysis.h" +#include "llvm/Analysis/TargetLibraryInfo.h" +#include "llvm/ADT/SetVector.h" #include "llvm/IR/Constants.h" #include "llvm/IR/LLVMContext.h" -#include "llvm/IR/Metadata.h" #include "llvm/IR/Module.h" -#include "llvm/Pass.h" #include "llvm/Support/CommandLine.h" -#include "llvm/ADT/SetVector.h" using namespace llvm; // A handy option for disabling TBAA functionality. The same effect can also be @@ -138,199 +136,138 @@ using namespace llvm; static cl::opt<bool> EnableTBAA("enable-tbaa", cl::init(true)); namespace { - /// TBAANode - This is a simple wrapper around an MDNode which provides a - /// higher-level interface by hiding the details of how alias analysis - /// information is encoded in its operands. - class TBAANode { - const MDNode *Node; - - public: - TBAANode() : Node(nullptr) {} - explicit TBAANode(const MDNode *N) : Node(N) {} - - /// getNode - Get the MDNode for this TBAANode. - const MDNode *getNode() const { return Node; } - - /// getParent - Get this TBAANode's Alias tree parent. - TBAANode getParent() const { - if (Node->getNumOperands() < 2) - return TBAANode(); - MDNode *P = dyn_cast_or_null<MDNode>(Node->getOperand(1)); - if (!P) - return TBAANode(); - // Ok, this node has a valid parent. Return it. - return TBAANode(P); - } - - /// TypeIsImmutable - Test if this TBAANode represents a type for objects - /// which are not modified (by any means) in the context where this - /// AliasAnalysis is relevant. - bool TypeIsImmutable() const { - if (Node->getNumOperands() < 3) - return false; - ConstantInt *CI = mdconst::dyn_extract<ConstantInt>(Node->getOperand(2)); - if (!CI) - return false; - return CI->getValue()[0]; - } - }; - - /// This is a simple wrapper around an MDNode which provides a - /// higher-level interface by hiding the details of how alias analysis - /// information is encoded in its operands. - class TBAAStructTagNode { - /// This node should be created with createTBAAStructTagNode. - const MDNode *Node; +/// TBAANode - This is a simple wrapper around an MDNode which provides a +/// higher-level interface by hiding the details of how alias analysis +/// information is encoded in its operands. +class TBAANode { + const MDNode *Node; + +public: + TBAANode() : Node(nullptr) {} + explicit TBAANode(const MDNode *N) : Node(N) {} + + /// getNode - Get the MDNode for this TBAANode. + const MDNode *getNode() const { return Node; } + + /// getParent - Get this TBAANode's Alias tree parent. + TBAANode getParent() const { + if (Node->getNumOperands() < 2) + return TBAANode(); + MDNode *P = dyn_cast_or_null<MDNode>(Node->getOperand(1)); + if (!P) + return TBAANode(); + // Ok, this node has a valid parent. Return it. + return TBAANode(P); + } - public: - explicit TBAAStructTagNode(const MDNode *N) : Node(N) {} + /// TypeIsImmutable - Test if this TBAANode represents a type for objects + /// which are not modified (by any means) in the context where this + /// AliasAnalysis is relevant. + bool TypeIsImmutable() const { + if (Node->getNumOperands() < 3) + return false; + ConstantInt *CI = mdconst::dyn_extract<ConstantInt>(Node->getOperand(2)); + if (!CI) + return false; + return CI->getValue()[0]; + } +}; - /// Get the MDNode for this TBAAStructTagNode. - const MDNode *getNode() const { return Node; } +/// This is a simple wrapper around an MDNode which provides a +/// higher-level interface by hiding the details of how alias analysis +/// information is encoded in its operands. +class TBAAStructTagNode { + /// This node should be created with createTBAAStructTagNode. + const MDNode *Node; - const MDNode *getBaseType() const { - return dyn_cast_or_null<MDNode>(Node->getOperand(0)); - } - const MDNode *getAccessType() const { - return dyn_cast_or_null<MDNode>(Node->getOperand(1)); - } - uint64_t getOffset() const { - return mdconst::extract<ConstantInt>(Node->getOperand(2))->getZExtValue(); - } - /// TypeIsImmutable - Test if this TBAAStructTagNode represents a type for - /// objects which are not modified (by any means) in the context where this - /// AliasAnalysis is relevant. - bool TypeIsImmutable() const { - if (Node->getNumOperands() < 4) - return false; - ConstantInt *CI = mdconst::dyn_extract<ConstantInt>(Node->getOperand(3)); - if (!CI) - return false; - return CI->getValue()[0]; - } - }; - - /// This is a simple wrapper around an MDNode which provides a - /// higher-level interface by hiding the details of how alias analysis - /// information is encoded in its operands. - class TBAAStructTypeNode { - /// This node should be created with createTBAAStructTypeNode. - const MDNode *Node; - - public: - TBAAStructTypeNode() : Node(nullptr) {} - explicit TBAAStructTypeNode(const MDNode *N) : Node(N) {} - - /// Get the MDNode for this TBAAStructTypeNode. - const MDNode *getNode() const { return Node; } - - /// Get this TBAAStructTypeNode's field in the type DAG with - /// given offset. Update the offset to be relative to the field type. - TBAAStructTypeNode getParent(uint64_t &Offset) const { - // Parent can be omitted for the root node. - if (Node->getNumOperands() < 2) - return TBAAStructTypeNode(); +public: + explicit TBAAStructTagNode(const MDNode *N) : Node(N) {} - // Fast path for a scalar type node and a struct type node with a single - // field. - if (Node->getNumOperands() <= 3) { - uint64_t Cur = Node->getNumOperands() == 2 - ? 0 - : mdconst::extract<ConstantInt>(Node->getOperand(2)) - ->getZExtValue(); - Offset -= Cur; - MDNode *P = dyn_cast_or_null<MDNode>(Node->getOperand(1)); - if (!P) - return TBAAStructTypeNode(); - return TBAAStructTypeNode(P); - } + /// Get the MDNode for this TBAAStructTagNode. + const MDNode *getNode() const { return Node; } - // Assume the offsets are in order. We return the previous field if - // the current offset is bigger than the given offset. - unsigned TheIdx = 0; - for (unsigned Idx = 1; Idx < Node->getNumOperands(); Idx += 2) { - uint64_t Cur = mdconst::extract<ConstantInt>(Node->getOperand(Idx + 1)) - ->getZExtValue(); - if (Cur > Offset) { - assert(Idx >= 3 && - "TBAAStructTypeNode::getParent should have an offset match!"); - TheIdx = Idx - 2; - break; - } - } - // Move along the last field. - if (TheIdx == 0) - TheIdx = Node->getNumOperands() - 2; - uint64_t Cur = mdconst::extract<ConstantInt>(Node->getOperand(TheIdx + 1)) - ->getZExtValue(); + const MDNode *getBaseType() const { + return dyn_cast_or_null<MDNode>(Node->getOperand(0)); + } + const MDNode *getAccessType() const { + return dyn_cast_or_null<MDNode>(Node->getOperand(1)); + } + uint64_t getOffset() const { + return mdconst::extract<ConstantInt>(Node->getOperand(2))->getZExtValue(); + } + /// TypeIsImmutable - Test if this TBAAStructTagNode represents a type for + /// objects which are not modified (by any means) in the context where this + /// AliasAnalysis is relevant. + bool TypeIsImmutable() const { + if (Node->getNumOperands() < 4) + return false; + ConstantInt *CI = mdconst::dyn_extract<ConstantInt>(Node->getOperand(3)); + if (!CI) + return false; + return CI->getValue()[0]; + } +}; + +/// This is a simple wrapper around an MDNode which provides a +/// higher-level interface by hiding the details of how alias analysis +/// information is encoded in its operands. +class TBAAStructTypeNode { + /// This node should be created with createTBAAStructTypeNode. + const MDNode *Node; + +public: + TBAAStructTypeNode() : Node(nullptr) {} + explicit TBAAStructTypeNode(const MDNode *N) : Node(N) {} + + /// Get the MDNode for this TBAAStructTypeNode. + const MDNode *getNode() const { return Node; } + + /// Get this TBAAStructTypeNode's field in the type DAG with + /// given offset. Update the offset to be relative to the field type. + TBAAStructTypeNode getParent(uint64_t &Offset) const { + // Parent can be omitted for the root node. + if (Node->getNumOperands() < 2) + return TBAAStructTypeNode(); + + // Fast path for a scalar type node and a struct type node with a single + // field. + if (Node->getNumOperands() <= 3) { + uint64_t Cur = Node->getNumOperands() == 2 + ? 0 + : mdconst::extract<ConstantInt>(Node->getOperand(2)) + ->getZExtValue(); Offset -= Cur; - MDNode *P = dyn_cast_or_null<MDNode>(Node->getOperand(TheIdx)); + MDNode *P = dyn_cast_or_null<MDNode>(Node->getOperand(1)); if (!P) return TBAAStructTypeNode(); return TBAAStructTypeNode(P); } - }; -} - -namespace { - /// TypeBasedAliasAnalysis - This is a simple alias analysis - /// implementation that uses TypeBased to answer queries. - class TypeBasedAliasAnalysis : public ImmutablePass, - public AliasAnalysis { - public: - static char ID; // Class identification, replacement for typeinfo - TypeBasedAliasAnalysis() : ImmutablePass(ID) { - initializeTypeBasedAliasAnalysisPass(*PassRegistry::getPassRegistry()); - } - bool doInitialization(Module &M) override; - - /// getAdjustedAnalysisPointer - This method is used when a pass implements - /// an analysis interface through multiple inheritance. If needed, it - /// should override this to adjust the this pointer as needed for the - /// specified pass info. - void *getAdjustedAnalysisPointer(const void *PI) override { - if (PI == &AliasAnalysis::ID) - return (AliasAnalysis*)this; - return this; + // Assume the offsets are in order. We return the previous field if + // the current offset is bigger than the given offset. + unsigned TheIdx = 0; + for (unsigned Idx = 1; Idx < Node->getNumOperands(); Idx += 2) { + uint64_t Cur = mdconst::extract<ConstantInt>(Node->getOperand(Idx + 1)) + ->getZExtValue(); + if (Cur > Offset) { + assert(Idx >= 3 && + "TBAAStructTypeNode::getParent should have an offset match!"); + TheIdx = Idx - 2; + break; + } } - - bool Aliases(const MDNode *A, const MDNode *B) const; - bool PathAliases(const MDNode *A, const MDNode *B) const; - - private: - void getAnalysisUsage(AnalysisUsage &AU) const override; - AliasResult alias(const MemoryLocation &LocA, - const MemoryLocation &LocB) override; - bool pointsToConstantMemory(const MemoryLocation &Loc, - bool OrLocal) override; - ModRefBehavior getModRefBehavior(ImmutableCallSite CS) override; - ModRefBehavior getModRefBehavior(const Function *F) override; - ModRefResult getModRefInfo(ImmutableCallSite CS, - const MemoryLocation &Loc) override; - ModRefResult getModRefInfo(ImmutableCallSite CS1, - ImmutableCallSite CS2) override; - }; -} // End of anonymous namespace - -// Register this pass... -char TypeBasedAliasAnalysis::ID = 0; -INITIALIZE_AG_PASS(TypeBasedAliasAnalysis, AliasAnalysis, "tbaa", - "Type-Based Alias Analysis", false, true, false) - -ImmutablePass *llvm::createTypeBasedAliasAnalysisPass() { - return new TypeBasedAliasAnalysis(); -} - -bool TypeBasedAliasAnalysis::doInitialization(Module &M) { - InitializeAliasAnalysis(this, &M.getDataLayout()); - return true; -} - -void -TypeBasedAliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { - AU.setPreservesAll(); - AliasAnalysis::getAnalysisUsage(AU); + // Move along the last field. + if (TheIdx == 0) + TheIdx = Node->getNumOperands() - 2; + uint64_t Cur = mdconst::extract<ConstantInt>(Node->getOperand(TheIdx + 1)) + ->getZExtValue(); + Offset -= Cur; + MDNode *P = dyn_cast_or_null<MDNode>(Node->getOperand(TheIdx)); + if (!P) + return TBAAStructTypeNode(); + return TBAAStructTypeNode(P); + } +}; } /// Check the first operand of the tbaa tag node, if it is a MDNode, we treat @@ -342,145 +279,36 @@ static bool isStructPathTBAA(const MDNode *MD) { return isa<MDNode>(MD->getOperand(0)) && MD->getNumOperands() >= 3; } -/// Aliases - Test whether the type represented by A may alias the -/// type represented by B. -bool -TypeBasedAliasAnalysis::Aliases(const MDNode *A, - const MDNode *B) const { - // Make sure that both MDNodes are struct-path aware. - if (isStructPathTBAA(A) && isStructPathTBAA(B)) - return PathAliases(A, B); - - // Keep track of the root node for A and B. - TBAANode RootA, RootB; - - // Climb the tree from A to see if we reach B. - for (TBAANode T(A); ; ) { - if (T.getNode() == B) - // B is an ancestor of A. - return true; - - RootA = T; - T = T.getParent(); - if (!T.getNode()) - break; - } - - // Climb the tree from B to see if we reach A. - for (TBAANode T(B); ; ) { - if (T.getNode() == A) - // A is an ancestor of B. - return true; - - RootB = T; - T = T.getParent(); - if (!T.getNode()) - break; - } - - // Neither node is an ancestor of the other. - - // If they have different roots, they're part of different potentially - // unrelated type systems, so we must be conservative. - if (RootA.getNode() != RootB.getNode()) - return true; - - // If they have the same root, then we've proved there's no alias. - return false; -} - -/// Test whether the struct-path tag represented by A may alias the -/// struct-path tag represented by B. -bool -TypeBasedAliasAnalysis::PathAliases(const MDNode *A, - const MDNode *B) const { - // Verify that both input nodes are struct-path aware. - assert(isStructPathTBAA(A) && "MDNode A is not struct-path aware."); - assert(isStructPathTBAA(B) && "MDNode B is not struct-path aware."); - - // Keep track of the root node for A and B. - TBAAStructTypeNode RootA, RootB; - TBAAStructTagNode TagA(A), TagB(B); - - // TODO: We need to check if AccessType of TagA encloses AccessType of - // TagB to support aggregate AccessType. If yes, return true. - - // Start from the base type of A, follow the edge with the correct offset in - // the type DAG and adjust the offset until we reach the base type of B or - // until we reach the Root node. - // Compare the adjusted offset once we have the same base. - - // Climb the type DAG from base type of A to see if we reach base type of B. - const MDNode *BaseA = TagA.getBaseType(); - const MDNode *BaseB = TagB.getBaseType(); - uint64_t OffsetA = TagA.getOffset(), OffsetB = TagB.getOffset(); - for (TBAAStructTypeNode T(BaseA); ; ) { - if (T.getNode() == BaseB) - // Base type of A encloses base type of B, check if the offsets match. - return OffsetA == OffsetB; - - RootA = T; - // Follow the edge with the correct offset, OffsetA will be adjusted to - // be relative to the field type. - T = T.getParent(OffsetA); - if (!T.getNode()) - break; - } - - // Reset OffsetA and climb the type DAG from base type of B to see if we reach - // base type of A. - OffsetA = TagA.getOffset(); - for (TBAAStructTypeNode T(BaseB); ; ) { - if (T.getNode() == BaseA) - // Base type of B encloses base type of A, check if the offsets match. - return OffsetA == OffsetB; - - RootB = T; - // Follow the edge with the correct offset, OffsetB will be adjusted to - // be relative to the field type. - T = T.getParent(OffsetB); - if (!T.getNode()) - break; - } - - // Neither node is an ancestor of the other. - - // If they have different roots, they're part of different potentially - // unrelated type systems, so we must be conservative. - if (RootA.getNode() != RootB.getNode()) - return true; - - // If they have the same root, then we've proved there's no alias. - return false; -} - -AliasResult TypeBasedAliasAnalysis::alias(const MemoryLocation &LocA, - const MemoryLocation &LocB) { +AliasResult TypeBasedAAResult::alias(const MemoryLocation &LocA, + const MemoryLocation &LocB) { if (!EnableTBAA) - return AliasAnalysis::alias(LocA, LocB); + return AAResultBase::alias(LocA, LocB); // Get the attached MDNodes. If either value lacks a tbaa MDNode, we must // be conservative. const MDNode *AM = LocA.AATags.TBAA; - if (!AM) return AliasAnalysis::alias(LocA, LocB); + if (!AM) + return AAResultBase::alias(LocA, LocB); const MDNode *BM = LocB.AATags.TBAA; - if (!BM) return AliasAnalysis::alias(LocA, LocB); + if (!BM) + return AAResultBase::alias(LocA, LocB); // If they may alias, chain to the next AliasAnalysis. if (Aliases(AM, BM)) - return AliasAnalysis::alias(LocA, LocB); + return AAResultBase::alias(LocA, LocB); // Otherwise return a definitive result. return NoAlias; } -bool TypeBasedAliasAnalysis::pointsToConstantMemory(const MemoryLocation &Loc, - bool OrLocal) { +bool TypeBasedAAResult::pointsToConstantMemory(const MemoryLocation &Loc, + bool OrLocal) { if (!EnableTBAA) - return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal); + return AAResultBase::pointsToConstantMemory(Loc, OrLocal); const MDNode *M = Loc.AATags.TBAA; - if (!M) return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal); + if (!M) + return AAResultBase::pointsToConstantMemory(Loc, OrLocal); // If this is an "immutable" type, we can assume the pointer is pointing // to constant memory. @@ -488,80 +316,82 @@ bool TypeBasedAliasAnalysis::pointsToConstantMemory(const MemoryLocation &Loc, (isStructPathTBAA(M) && TBAAStructTagNode(M).TypeIsImmutable())) return true; - return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal); + return AAResultBase::pointsToConstantMemory(Loc, OrLocal); } -AliasAnalysis::ModRefBehavior -TypeBasedAliasAnalysis::getModRefBehavior(ImmutableCallSite CS) { +FunctionModRefBehavior +TypeBasedAAResult::getModRefBehavior(ImmutableCallSite CS) { if (!EnableTBAA) - return AliasAnalysis::getModRefBehavior(CS); + return AAResultBase::getModRefBehavior(CS); - ModRefBehavior Min = UnknownModRefBehavior; + FunctionModRefBehavior Min = FMRB_UnknownModRefBehavior; // If this is an "immutable" type, we can assume the call doesn't write // to memory. if (const MDNode *M = CS.getInstruction()->getMetadata(LLVMContext::MD_tbaa)) if ((!isStructPathTBAA(M) && TBAANode(M).TypeIsImmutable()) || (isStructPathTBAA(M) && TBAAStructTagNode(M).TypeIsImmutable())) - Min = OnlyReadsMemory; + Min = FMRB_OnlyReadsMemory; - return ModRefBehavior(AliasAnalysis::getModRefBehavior(CS) & Min); + return FunctionModRefBehavior(AAResultBase::getModRefBehavior(CS) & Min); } -AliasAnalysis::ModRefBehavior -TypeBasedAliasAnalysis::getModRefBehavior(const Function *F) { +FunctionModRefBehavior TypeBasedAAResult::getModRefBehavior(const Function *F) { // Functions don't have metadata. Just chain to the next implementation. - return AliasAnalysis::getModRefBehavior(F); + return AAResultBase::getModRefBehavior(F); } -AliasAnalysis::ModRefResult -TypeBasedAliasAnalysis::getModRefInfo(ImmutableCallSite CS, - const MemoryLocation &Loc) { +ModRefInfo TypeBasedAAResult::getModRefInfo(ImmutableCallSite CS, + const MemoryLocation &Loc) { if (!EnableTBAA) - return AliasAnalysis::getModRefInfo(CS, Loc); + return AAResultBase::getModRefInfo(CS, Loc); if (const MDNode *L = Loc.AATags.TBAA) if (const MDNode *M = CS.getInstruction()->getMetadata(LLVMContext::MD_tbaa)) if (!Aliases(L, M)) - return NoModRef; + return MRI_NoModRef; - return AliasAnalysis::getModRefInfo(CS, Loc); + return AAResultBase::getModRefInfo(CS, Loc); } -AliasAnalysis::ModRefResult -TypeBasedAliasAnalysis::getModRefInfo(ImmutableCallSite CS1, - ImmutableCallSite CS2) { +ModRefInfo TypeBasedAAResult::getModRefInfo(ImmutableCallSite CS1, + ImmutableCallSite CS2) { if (!EnableTBAA) - return AliasAnalysis::getModRefInfo(CS1, CS2); + return AAResultBase::getModRefInfo(CS1, CS2); if (const MDNode *M1 = CS1.getInstruction()->getMetadata(LLVMContext::MD_tbaa)) if (const MDNode *M2 = CS2.getInstruction()->getMetadata(LLVMContext::MD_tbaa)) if (!Aliases(M1, M2)) - return NoModRef; + return MRI_NoModRef; - return AliasAnalysis::getModRefInfo(CS1, CS2); + return AAResultBase::getModRefInfo(CS1, CS2); } bool MDNode::isTBAAVtableAccess() const { if (!isStructPathTBAA(this)) { - if (getNumOperands() < 1) return false; + if (getNumOperands() < 1) + return false; if (MDString *Tag1 = dyn_cast<MDString>(getOperand(0))) { - if (Tag1->getString() == "vtable pointer") return true; + if (Tag1->getString() == "vtable pointer") + return true; } return false; } // For struct-path aware TBAA, we use the access type of the tag. - if (getNumOperands() < 2) return false; + if (getNumOperands() < 2) + return false; MDNode *Tag = cast_or_null<MDNode>(getOperand(1)); - if (!Tag) return false; + if (!Tag) + return false; if (MDString *Tag1 = dyn_cast<MDString>(Tag->getOperand(0))) { - if (Tag1->getString() == "vtable pointer") return true; + if (Tag1->getString() == "vtable pointer") + return true; } - return false; + return false; } MDNode *MDNode::getMostGenericTBAA(MDNode *A, MDNode *B) { @@ -575,9 +405,11 @@ MDNode *MDNode::getMostGenericTBAA(MDNode *A, MDNode *B) { bool StructPath = isStructPathTBAA(A) && isStructPathTBAA(B); if (StructPath) { A = cast_or_null<MDNode>(A->getOperand(1)); - if (!A) return nullptr; + if (!A) + return nullptr; B = cast_or_null<MDNode>(B->getOperand(1)); - if (!B) return nullptr; + if (!B) + return nullptr; } SmallSetVector<MDNode *, 4> PathA; @@ -604,7 +436,7 @@ MDNode *MDNode::getMostGenericTBAA(MDNode *A, MDNode *B) { int IB = PathB.size() - 1; MDNode *Ret = nullptr; - while (IA >= 0 && IB >=0) { + while (IA >= 0 && IB >= 0) { if (PathA[IA] == PathB[IB]) Ret = PathA[IA]; else @@ -644,3 +476,147 @@ void Instruction::getAAMetadata(AAMDNodes &N, bool Merge) const { N.NoAlias = getMetadata(LLVMContext::MD_noalias); } +/// Aliases - Test whether the type represented by A may alias the +/// type represented by B. +bool TypeBasedAAResult::Aliases(const MDNode *A, const MDNode *B) const { + // Make sure that both MDNodes are struct-path aware. + if (isStructPathTBAA(A) && isStructPathTBAA(B)) + return PathAliases(A, B); + + // Keep track of the root node for A and B. + TBAANode RootA, RootB; + + // Climb the tree from A to see if we reach B. + for (TBAANode T(A);;) { + if (T.getNode() == B) + // B is an ancestor of A. + return true; + + RootA = T; + T = T.getParent(); + if (!T.getNode()) + break; + } + + // Climb the tree from B to see if we reach A. + for (TBAANode T(B);;) { + if (T.getNode() == A) + // A is an ancestor of B. + return true; + + RootB = T; + T = T.getParent(); + if (!T.getNode()) + break; + } + + // Neither node is an ancestor of the other. + + // If they have different roots, they're part of different potentially + // unrelated type systems, so we must be conservative. + if (RootA.getNode() != RootB.getNode()) + return true; + + // If they have the same root, then we've proved there's no alias. + return false; +} + +/// Test whether the struct-path tag represented by A may alias the +/// struct-path tag represented by B. +bool TypeBasedAAResult::PathAliases(const MDNode *A, const MDNode *B) const { + // Verify that both input nodes are struct-path aware. + assert(isStructPathTBAA(A) && "MDNode A is not struct-path aware."); + assert(isStructPathTBAA(B) && "MDNode B is not struct-path aware."); + + // Keep track of the root node for A and B. + TBAAStructTypeNode RootA, RootB; + TBAAStructTagNode TagA(A), TagB(B); + + // TODO: We need to check if AccessType of TagA encloses AccessType of + // TagB to support aggregate AccessType. If yes, return true. + + // Start from the base type of A, follow the edge with the correct offset in + // the type DAG and adjust the offset until we reach the base type of B or + // until we reach the Root node. + // Compare the adjusted offset once we have the same base. + + // Climb the type DAG from base type of A to see if we reach base type of B. + const MDNode *BaseA = TagA.getBaseType(); + const MDNode *BaseB = TagB.getBaseType(); + uint64_t OffsetA = TagA.getOffset(), OffsetB = TagB.getOffset(); + for (TBAAStructTypeNode T(BaseA);;) { + if (T.getNode() == BaseB) + // Base type of A encloses base type of B, check if the offsets match. + return OffsetA == OffsetB; + + RootA = T; + // Follow the edge with the correct offset, OffsetA will be adjusted to + // be relative to the field type. + T = T.getParent(OffsetA); + if (!T.getNode()) + break; + } + + // Reset OffsetA and climb the type DAG from base type of B to see if we reach + // base type of A. + OffsetA = TagA.getOffset(); + for (TBAAStructTypeNode T(BaseB);;) { + if (T.getNode() == BaseA) + // Base type of B encloses base type of A, check if the offsets match. + return OffsetA == OffsetB; + + RootB = T; + // Follow the edge with the correct offset, OffsetB will be adjusted to + // be relative to the field type. + T = T.getParent(OffsetB); + if (!T.getNode()) + break; + } + + // Neither node is an ancestor of the other. + + // If they have different roots, they're part of different potentially + // unrelated type systems, so we must be conservative. + if (RootA.getNode() != RootB.getNode()) + return true; + + // If they have the same root, then we've proved there's no alias. + return false; +} + +TypeBasedAAResult TypeBasedAA::run(Function &F, AnalysisManager<Function> *AM) { + return TypeBasedAAResult(AM->getResult<TargetLibraryAnalysis>(F)); +} + +char TypeBasedAA::PassID; + +char TypeBasedAAWrapperPass::ID = 0; +INITIALIZE_PASS_BEGIN(TypeBasedAAWrapperPass, "tbaa", + "Type-Based Alias Analysis", false, true) +INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) +INITIALIZE_PASS_END(TypeBasedAAWrapperPass, "tbaa", "Type-Based Alias Analysis", + false, true) + +ImmutablePass *llvm::createTypeBasedAAWrapperPass() { + return new TypeBasedAAWrapperPass(); +} + +TypeBasedAAWrapperPass::TypeBasedAAWrapperPass() : ImmutablePass(ID) { + initializeTypeBasedAAWrapperPassPass(*PassRegistry::getPassRegistry()); +} + +bool TypeBasedAAWrapperPass::doInitialization(Module &M) { + Result.reset(new TypeBasedAAResult( + getAnalysis<TargetLibraryInfoWrapperPass>().getTLI())); + return false; +} + +bool TypeBasedAAWrapperPass::doFinalization(Module &M) { + Result.reset(); + return false; +} + +void TypeBasedAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesAll(); + AU.addRequired<TargetLibraryInfoWrapperPass>(); +} |
