Index: llvm/trunk/include/llvm/Analysis/CFLAndersAliasAnalysis.h =================================================================== --- llvm/trunk/include/llvm/Analysis/CFLAndersAliasAnalysis.h +++ llvm/trunk/include/llvm/Analysis/CFLAndersAliasAnalysis.h @@ -15,33 +15,86 @@ #ifndef LLVM_ANALYSIS_CFLANDERSALIASANALYSIS_H #define LLVM_ANALYSIS_CFLANDERSALIASANALYSIS_H +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/Optional.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/IR/Function.h" +#include "llvm/IR/ValueHandle.h" #include "llvm/Pass.h" +#include namespace llvm { +class TargetLibraryInfo; + namespace cflaa { struct AliasSummary; } class CFLAndersAAResult : public AAResultBase { friend AAResultBase; + class FunctionInfo; public: - explicit CFLAndersAAResult(); + explicit CFLAndersAAResult(const TargetLibraryInfo &); + CFLAndersAAResult(CFLAndersAAResult &&); + ~CFLAndersAAResult(); + + /// Handle invalidation events from the new pass manager. + /// By definition, this result is stateless and so remains valid. + bool invalidate(Function &, const PreservedAnalyses &) { return false; } + /// Evict the given function from cache + void evict(const Function &Fn); /// \brief Get the alias summary for the given function /// Return nullptr if the summary is not found or not available - const cflaa::AliasSummary *getAliasSummary(Function &Fn) { - // Dummy implementation - return nullptr; - } - - AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB) { - // Dummy implementation - return AAResultBase::alias(LocA, LocB); - } + const cflaa::AliasSummary *getAliasSummary(const Function &); + + AliasResult query(const MemoryLocation &, const MemoryLocation &); + AliasResult alias(const MemoryLocation &, const MemoryLocation &); + +private: + struct FunctionHandle final : public CallbackVH { + FunctionHandle(Function *Fn, CFLAndersAAResult *Result) + : CallbackVH(Fn), Result(Result) { + assert(Fn != nullptr); + assert(Result != nullptr); + } + + void deleted() override { removeSelfFromCache(); } + void allUsesReplacedWith(Value *) override { removeSelfFromCache(); } + + private: + CFLAndersAAResult *Result; + + void removeSelfFromCache() { + assert(Result != nullptr); + auto *Val = getValPtr(); + Result->evict(*cast(Val)); + setValPtr(nullptr); + } + }; + + /// \brief Ensures that the given function is available in the cache. + /// Returns the appropriate entry from the cache. + const Optional &ensureCached(const Function &); + + /// \brief Inserts the given Function into the cache. + void scan(const Function &); + + /// \brief Build summary for a given function + FunctionInfo buildInfoFrom(const Function &); + + const TargetLibraryInfo &TLI; + + /// \brief Cached mapping of Functions to their StratifiedSets. + /// If a function's sets are currently being built, it is marked + /// in the cache as an Optional without a value. This way, if we + /// have any kind of recursion, it is discernable from a function + /// that simply has empty sets. + DenseMap> Cache; + + std::forward_list Handles; }; /// Analysis pass providing a never-invalidated alias analysis result. Index: llvm/trunk/lib/Analysis/AliasAnalysisSummary.h =================================================================== --- llvm/trunk/lib/Analysis/AliasAnalysisSummary.h +++ llvm/trunk/lib/Analysis/AliasAnalysisSummary.h @@ -114,11 +114,11 @@ unsigned DerefLevel; }; -inline bool operator==(InterfaceValue lhs, InterfaceValue rhs) { - return lhs.Index == rhs.Index && lhs.DerefLevel == rhs.DerefLevel; +inline bool operator==(InterfaceValue LHS, InterfaceValue RHS) { + return LHS.Index == RHS.Index && LHS.DerefLevel == RHS.DerefLevel; } -inline bool operator!=(InterfaceValue lhs, InterfaceValue rhs) { - return !(lhs == rhs); +inline bool operator!=(InterfaceValue LHS, InterfaceValue RHS) { + return !(LHS == RHS); } /// We use ExternalRelation to describe an externally visible aliasing relations @@ -150,6 +150,26 @@ }; Optional instantiateInterfaceValue(InterfaceValue, CallSite); +inline bool operator==(InstantiatedValue LHS, InstantiatedValue RHS) { + return LHS.Val == RHS.Val && LHS.DerefLevel == RHS.DerefLevel; +} +inline bool operator!=(InstantiatedValue LHS, InstantiatedValue RHS) { + return !(LHS == RHS); +} +inline bool operator<(InstantiatedValue LHS, InstantiatedValue RHS) { + return std::less()(LHS.Val, RHS.Val) || + (LHS.Val == RHS.Val && LHS.DerefLevel < RHS.DerefLevel); +} +inline bool operator>(InstantiatedValue LHS, InstantiatedValue RHS) { + return RHS < LHS; +} +inline bool operator<=(InstantiatedValue LHS, InstantiatedValue RHS) { + return !(RHS < LHS); +} +inline bool operator>=(InstantiatedValue LHS, InstantiatedValue RHS) { + return !(LHS < RHS); +} + /// This is the result of instantiating ExternalRelation at a particular /// callsite struct InstantiatedRelation { Index: llvm/trunk/lib/Analysis/CFLAndersAliasAnalysis.cpp =================================================================== --- llvm/trunk/lib/Analysis/CFLAndersAliasAnalysis.cpp +++ llvm/trunk/lib/Analysis/CFLAndersAliasAnalysis.cpp @@ -16,6 +16,24 @@ // precise analysis result. The precision of this analysis is roughly the same // as that of an one level context-sensitive Andersen's algorithm. // +// The algorithm used here is based on recursive state machine matching scheme +// proposed in "Demand-driven alias analysis for C" by Xin Zheng and Radu +// Rugina. The general idea is to extend the tranditional transitive closure +// algorithm to perform CFL matching along the way: instead of recording +// "whether X is reachable from Y", we keep track of "whether X is reachable +// from Y at state Z", where the "state" field indicates where we are in the CFL +// matching process. To understand the matching better, it is advisable to have +// the state machine shown in Figure 3 of the paper available when reading the +// codes: all we do here is to selectively expand the transitive closure by +// discarding edges that are not recognized by the state machine. +// +// There is one difference between our current implementation and the one +// described in the paper: out algorithm eagerly computes all alias pairs after +// the CFLGraph is built, while in the paper the authors did the computation in +// a demand-driven fashion. We did not implement the demand-driven algorithm due +// to the additional coding complexity and higher memory profile, but if we +// found it necessary we may switch to it eventually. +// //===----------------------------------------------------------------------===// // N.B. AliasAnalysis as a whole is phrased as a FunctionPass at the moment, and @@ -26,6 +44,7 @@ #include "llvm/Analysis/CFLAndersAliasAnalysis.h" #include "CFLGraph.h" +#include "llvm/ADT/DenseSet.h" #include "llvm/Pass.h" using namespace llvm; @@ -33,12 +52,395 @@ #define DEBUG_TYPE "cfl-anders-aa" -CFLAndersAAResult::CFLAndersAAResult() = default; +CFLAndersAAResult::CFLAndersAAResult(const TargetLibraryInfo &TLI) : TLI(TLI) {} +CFLAndersAAResult::CFLAndersAAResult(CFLAndersAAResult &&RHS) + : AAResultBase(std::move(RHS)), TLI(RHS.TLI) {} +CFLAndersAAResult::~CFLAndersAAResult() {} + +static const Function *parentFunctionOfValue(const Value *Val) { + if (auto *Inst = dyn_cast(Val)) { + auto *Bb = Inst->getParent(); + return Bb->getParent(); + } + + if (auto *Arg = dyn_cast(Val)) + return Arg->getParent(); + return nullptr; +} + +namespace { + +enum class MatchState : uint8_t { + FlowFrom = 0, // S1 in the paper + FlowFromMemAlias, // S2 in the paper + FlowTo, // S3 in the paper + FlowToMemAlias // S4 in the paper +}; + +// We use ReachabilitySet to keep track of value aliases (The nonterminal "V" in +// the paper) during the analysis. +class ReachabilitySet { + typedef std::bitset<4> StateSet; + typedef DenseMap ValueStateMap; + typedef DenseMap ValueReachMap; + ValueReachMap ReachMap; + +public: + typedef ValueStateMap::const_iterator const_valuestate_iterator; + typedef ValueReachMap::const_iterator const_value_iterator; + + // Insert edge 'From->To' at state 'State' + bool insert(InstantiatedValue From, InstantiatedValue To, MatchState State) { + auto &States = ReachMap[To][From]; + auto Idx = static_cast(State); + if (!States.test(Idx)) { + States.set(Idx); + return true; + } + return false; + } + + // Return the set of all ('From', 'State') pair for a given node 'To' + iterator_range + reachableValueAliases(InstantiatedValue V) const { + auto Itr = ReachMap.find(V); + if (Itr == ReachMap.end()) + return make_range(const_valuestate_iterator(), + const_valuestate_iterator()); + return make_range(Itr->second.begin(), + Itr->second.end()); + } + + iterator_range value_mappings() const { + return make_range(ReachMap.begin(), ReachMap.end()); + } +}; + +// We use AliasMemSet to keep track of all memory aliases (the nonterminal "M" +// in the paper) during the analysis. +class AliasMemSet { + typedef DenseSet MemSet; + typedef DenseMap MemMapType; + MemMapType MemMap; + +public: + typedef MemSet::const_iterator const_mem_iterator; + + bool insert(InstantiatedValue LHS, InstantiatedValue RHS) { + // Top-level values can never be memory aliases because one cannot take the + // addresses of them + assert(LHS.DerefLevel > 0 && RHS.DerefLevel > 0); + return MemMap[LHS].insert(RHS).second; + } + + const MemSet *getMemoryAliases(InstantiatedValue V) const { + auto Itr = MemMap.find(V); + if (Itr == MemMap.end()) + return nullptr; + return &Itr->second; + } +}; + +struct WorkListItem { + InstantiatedValue From; + InstantiatedValue To; + MatchState State; +}; +} + +class CFLAndersAAResult::FunctionInfo { + /// Map a value to other values that may alias it + /// Since the alias relation is symmetric, to save some space we assume values + /// are properly ordered: if a and b alias each other, and a < b, then b is in + /// AliasMap[a] but not vice versa. + DenseMap> AliasMap; + + /// Summary of externally visible effects. + AliasSummary Summary; + +public: + FunctionInfo(const ReachabilitySet &); + + bool mayAlias(const Value *LHS, const Value *RHS) const; + const AliasSummary &getAliasSummary() const { return Summary; } +}; + +CFLAndersAAResult::FunctionInfo::FunctionInfo(const ReachabilitySet &ReachSet) { + for (const auto &OuterMapping : ReachSet.value_mappings()) { + // AliasMap only cares about top-level values + if (OuterMapping.first.DerefLevel > 0) + continue; + + auto Val = OuterMapping.first.Val; + auto &AliasList = AliasMap[Val]; + for (const auto &InnerMapping : OuterMapping.second) { + // Again, AliasMap only cares about top-level values + if (InnerMapping.first.DerefLevel == 0) + AliasList.push_back(InnerMapping.first.Val); + } + + // Sort AliasList for faster lookup + std::sort(AliasList.begin(), AliasList.end(), std::less()); + } + + // TODO: Populate function summary here +} + +bool CFLAndersAAResult::FunctionInfo::mayAlias(const Value *LHS, + const Value *RHS) const { + assert(LHS && RHS); + + auto Itr = AliasMap.find(LHS); + if (Itr == AliasMap.end()) + return false; + + // TODO: Check AliasAttrs before drawing any conclusions + + return std::binary_search(Itr->second.begin(), Itr->second.end(), RHS, + std::less()); +} + +static void propagate(InstantiatedValue From, InstantiatedValue To, + MatchState State, ReachabilitySet &ReachSet, + std::vector &WorkList) { + if (From == To) + return; + if (ReachSet.insert(From, To, State)) + WorkList.push_back(WorkListItem{From, To, State}); +} + +static void initializeWorkList(std::vector &WorkList, + ReachabilitySet &ReachSet, + const CFLGraph &Graph) { + for (const auto &Mapping : Graph.value_mappings()) { + auto Val = Mapping.first; + auto &ValueInfo = Mapping.second; + assert(ValueInfo.getNumLevels() > 0); + + // Insert all immediate assignment neighbors to the worklist + for (unsigned I = 0, E = ValueInfo.getNumLevels(); I < E; ++I) { + auto Src = InstantiatedValue{Val, I}; + // If there's an assignment edge from X to Y, it means Y is reachable from + // X at S2 and X is reachable from Y at S1 + for (auto &Edge : ValueInfo.getNodeInfoAtLevel(I).Edges) { + propagate(Edge.Other, Src, MatchState::FlowFrom, ReachSet, WorkList); + propagate(Src, Edge.Other, MatchState::FlowTo, ReachSet, WorkList); + } + } + } +} + +static Optional getNodeBelow(const CFLGraph &Graph, + InstantiatedValue V) { + auto NodeBelow = InstantiatedValue{V.Val, V.DerefLevel + 1}; + if (Graph.getNode(NodeBelow)) + return NodeBelow; + return None; +} + +static void processWorkListItem(const WorkListItem &Item, const CFLGraph &Graph, + ReachabilitySet &ReachSet, AliasMemSet &MemSet, + std::vector &WorkList) { + auto FromNode = Item.From; + auto ToNode = Item.To; + + auto NodeInfo = Graph.getNode(ToNode); + assert(NodeInfo != nullptr); + + // TODO: propagate AliasAttr as well + // TODO: propagate field offsets + + // FIXME: Here is a neat trick we can do: since both ReachSet and MemSet holds + // relations that are symmetric, we could actually cut the storage by half by + // sorting FromNode and ToNode before insertion happens. + + // The newly added value alias pair may pontentially generate more memory + // alias pairs. Check for them here. + auto FromNodeBelow = getNodeBelow(Graph, FromNode); + auto ToNodeBelow = getNodeBelow(Graph, ToNode); + if (FromNodeBelow && ToNodeBelow && + MemSet.insert(*FromNodeBelow, *ToNodeBelow)) { + propagate(*FromNodeBelow, *ToNodeBelow, MatchState::FlowFromMemAlias, + ReachSet, WorkList); + for (const auto &Mapping : ReachSet.reachableValueAliases(*FromNodeBelow)) { + auto Src = Mapping.first; + if (Mapping.second.test(static_cast(MatchState::FlowFrom))) + propagate(Src, *ToNodeBelow, MatchState::FlowFromMemAlias, ReachSet, + WorkList); + if (Mapping.second.test(static_cast(MatchState::FlowTo))) + propagate(Src, *ToNodeBelow, MatchState::FlowToMemAlias, ReachSet, + WorkList); + } + } + + // This is the core of the state machine walking algorithm. We expand ReachSet + // based on which state we are at (which in turn dictates what edges we + // should examine) + // From a high-level point of view, the state machine here guarantees two + // properties: + // - If *X and *Y are memory aliases, then X and Y are value aliases + // - If Y is an alias of X, then reverse assignment edges (if there is any) + // should precede any assignment edges on the path from X to Y. + switch (Item.State) { + case MatchState::FlowFrom: { + for (const auto &RevAssignEdge : NodeInfo->ReverseEdges) + propagate(FromNode, RevAssignEdge.Other, MatchState::FlowFrom, ReachSet, + WorkList); + for (const auto &AssignEdge : NodeInfo->Edges) + propagate(FromNode, AssignEdge.Other, MatchState::FlowTo, ReachSet, + WorkList); + if (auto AliasSet = MemSet.getMemoryAliases(ToNode)) { + for (const auto &MemAlias : *AliasSet) + propagate(FromNode, MemAlias, MatchState::FlowFromMemAlias, ReachSet, + WorkList); + } + break; + } + case MatchState::FlowFromMemAlias: { + for (const auto &RevAssignEdge : NodeInfo->ReverseEdges) + propagate(FromNode, RevAssignEdge.Other, MatchState::FlowFrom, ReachSet, + WorkList); + for (const auto &AssignEdge : NodeInfo->Edges) + propagate(FromNode, AssignEdge.Other, MatchState::FlowTo, ReachSet, + WorkList); + break; + } + case MatchState::FlowTo: { + for (const auto &AssignEdge : NodeInfo->Edges) + propagate(FromNode, AssignEdge.Other, MatchState::FlowTo, ReachSet, + WorkList); + if (auto AliasSet = MemSet.getMemoryAliases(ToNode)) { + for (const auto &MemAlias : *AliasSet) + propagate(FromNode, MemAlias, MatchState::FlowToMemAlias, ReachSet, + WorkList); + } + break; + } + case MatchState::FlowToMemAlias: { + for (const auto &AssignEdge : NodeInfo->Edges) + propagate(FromNode, AssignEdge.Other, MatchState::FlowTo, ReachSet, + WorkList); + break; + } + } +} + +CFLAndersAAResult::FunctionInfo +CFLAndersAAResult::buildInfoFrom(const Function &Fn) { + CFLGraphBuilder GraphBuilder( + *this, TLI, + // Cast away the constness here due to GraphBuilder's API requirement + const_cast(Fn)); + auto &Graph = GraphBuilder.getCFLGraph(); + + ReachabilitySet ReachSet; + AliasMemSet MemSet; + + std::vector WorkList, NextList; + initializeWorkList(WorkList, ReachSet, Graph); + // TODO: make sure we don't stop before the fix point is reached + while (!WorkList.empty()) { + for (const auto &Item : WorkList) + processWorkListItem(Item, Graph, ReachSet, MemSet, NextList); + + NextList.swap(WorkList); + NextList.clear(); + } + + return FunctionInfo(ReachSet); +} + +void CFLAndersAAResult::scan(const Function &Fn) { + auto InsertPair = Cache.insert(std::make_pair(&Fn, Optional())); + (void)InsertPair; + assert(InsertPair.second && + "Trying to scan a function that has already been cached"); + + // Note that we can't do Cache[Fn] = buildSetsFrom(Fn) here: the function call + // may get evaluated after operator[], potentially triggering a DenseMap + // resize and invalidating the reference returned by operator[] + auto FunInfo = buildInfoFrom(Fn); + Cache[&Fn] = std::move(FunInfo); + Handles.push_front(FunctionHandle(const_cast(&Fn), this)); +} + +void CFLAndersAAResult::evict(const Function &Fn) { Cache.erase(&Fn); } + +const Optional & +CFLAndersAAResult::ensureCached(const Function &Fn) { + auto Iter = Cache.find(&Fn); + if (Iter == Cache.end()) { + scan(Fn); + Iter = Cache.find(&Fn); + assert(Iter != Cache.end()); + assert(Iter->second.hasValue()); + } + return Iter->second; +} + +const AliasSummary *CFLAndersAAResult::getAliasSummary(const Function &Fn) { + auto &FunInfo = ensureCached(Fn); + if (FunInfo.hasValue()) + return &FunInfo->getAliasSummary(); + else + return nullptr; +} + +AliasResult CFLAndersAAResult::query(const MemoryLocation &LocA, + const MemoryLocation &LocB) { + auto *ValA = LocA.Ptr; + auto *ValB = LocB.Ptr; + + if (!ValA->getType()->isPointerTy() || !ValB->getType()->isPointerTy()) + return NoAlias; + + auto *Fn = parentFunctionOfValue(ValA); + if (!Fn) { + Fn = parentFunctionOfValue(ValB); + if (!Fn) { + // The only times this is known to happen are when globals + InlineAsm are + // involved + DEBUG(dbgs() + << "CFLAndersAA: could not extract parent function information.\n"); + return MayAlias; + } + } else { + assert(!parentFunctionOfValue(ValB) || parentFunctionOfValue(ValB) == Fn); + } + + assert(Fn != nullptr); + auto &FunInfo = ensureCached(*Fn); + + // AliasMap lookup + if (FunInfo->mayAlias(ValA, ValB)) + return MayAlias; + return NoAlias; +} + +AliasResult CFLAndersAAResult::alias(const MemoryLocation &LocA, + const MemoryLocation &LocB) { + if (LocA.Ptr == LocB.Ptr) + return LocA.Size == LocB.Size ? MustAlias : PartialAlias; + + // Comparisons between global variables and other constants should be + // handled by BasicAA. + // CFLAndersAA may report NoAlias when comparing a GlobalValue and + // ConstantExpr, but every query needs to have at least one Value tied to a + // Function, and neither GlobalValues nor ConstantExprs are. + if (isa(LocA.Ptr) && isa(LocB.Ptr)) + return AAResultBase::alias(LocA, LocB); + + AliasResult QueryResult = query(LocA, LocB); + if (QueryResult == MayAlias) + return AAResultBase::alias(LocA, LocB); + + return QueryResult; +} char CFLAndersAA::PassID; CFLAndersAAResult CFLAndersAA::run(Function &F, AnalysisManager &AM) { - return CFLAndersAAResult(); + return CFLAndersAAResult(AM.getResult(F)); } char CFLAndersAAWrapperPass::ID = 0; @@ -53,8 +455,12 @@ initializeCFLAndersAAWrapperPassPass(*PassRegistry::getPassRegistry()); } -void CFLAndersAAWrapperPass::initializePass() {} +void CFLAndersAAWrapperPass::initializePass() { + auto &TLIWP = getAnalysis(); + Result.reset(new CFLAndersAAResult(TLIWP.getTLI())); +} void CFLAndersAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesAll(); + AU.addRequired(); } Index: llvm/trunk/lib/Analysis/CFLGraph.h =================================================================== --- llvm/trunk/lib/Analysis/CFLGraph.h +++ llvm/trunk/lib/Analysis/CFLGraph.h @@ -45,7 +45,7 @@ typedef std::vector EdgeList; struct NodeInfo { - EdgeList Edges; + EdgeList Edges, ReverseEdges; AliasAttrs Attr; }; @@ -77,12 +77,6 @@ typedef DenseMap ValueMap; ValueMap ValueImpls; - const NodeInfo *getNode(Node N) const { - auto Itr = ValueImpls.find(N.Val); - if (Itr == ValueImpls.end() || Itr->second.getNumLevels() <= N.DerefLevel) - return nullptr; - return &Itr->second.getNodeInfoAtLevel(N.DerefLevel); - } NodeInfo *getNode(Node N) { auto Itr = ValueImpls.find(N.Val); if (Itr == ValueImpls.end() || Itr->second.getNumLevels() <= N.DerefLevel) @@ -108,11 +102,20 @@ } void addEdge(Node From, Node To, int64_t Offset = 0) { - assert(getNode(To) != nullptr); - auto *FromInfo = getNode(From); assert(FromInfo != nullptr); + auto *ToInfo = getNode(To); + assert(ToInfo != nullptr); + FromInfo->Edges.push_back(Edge{To}); + ToInfo->ReverseEdges.push_back(Edge{From}); + } + + const NodeInfo *getNode(Node N) const { + auto Itr = ValueImpls.find(N.Val); + if (Itr == ValueImpls.end() || Itr->second.getNumLevels() <= N.DerefLevel) + return nullptr; + return &Itr->second.getNodeInfoAtLevel(N.DerefLevel); } AliasAttrs attrFor(Node N) const { @@ -203,16 +206,24 @@ } } - void addDerefEdge(Value *From, Value *To) { + void addDerefEdge(Value *From, Value *To, bool IsRead) { assert(From != nullptr && To != nullptr); if (!From->getType()->isPointerTy() || !To->getType()->isPointerTy()) return; addNode(From); addNode(To); - Graph.addNode(InstantiatedValue{From, 1}); - Graph.addEdge(InstantiatedValue{From, 1}, InstantiatedValue{To, 0}); + if (IsRead) { + Graph.addNode(InstantiatedValue{From, 1}); + Graph.addEdge(InstantiatedValue{From, 1}, InstantiatedValue{To, 0}); + } else { + Graph.addNode(InstantiatedValue{To, 1}); + Graph.addEdge(InstantiatedValue{From, 0}, InstantiatedValue{To, 1}); + } } + void addLoadEdge(Value *From, Value *To) { addDerefEdge(From, To, true); } + void addStoreEdge(Value *From, Value *To) { addDerefEdge(From, To, false); } + public: GetEdgesVisitor(CFLGraphBuilder &Builder) : AA(Builder.Analysis), TLI(Builder.TLI), Graph(Builder.Graph), @@ -256,13 +267,13 @@ void visitAtomicCmpXchgInst(AtomicCmpXchgInst &Inst) { auto *Ptr = Inst.getPointerOperand(); auto *Val = Inst.getNewValOperand(); - addDerefEdge(Ptr, Val); + addStoreEdge(Val, Ptr); } void visitAtomicRMWInst(AtomicRMWInst &Inst) { auto *Ptr = Inst.getPointerOperand(); auto *Val = Inst.getValOperand(); - addDerefEdge(Ptr, Val); + addStoreEdge(Val, Ptr); } void visitPHINode(PHINode &Inst) { @@ -292,13 +303,13 @@ void visitLoadInst(LoadInst &Inst) { auto *Ptr = Inst.getPointerOperand(); auto *Val = &Inst; - addDerefEdge(Ptr, Val); + addLoadEdge(Ptr, Val); } void visitStoreInst(StoreInst &Inst) { auto *Ptr = Inst.getPointerOperand(); auto *Val = Inst.getValueOperand(); - addDerefEdge(Ptr, Val); + addStoreEdge(Val, Ptr); } void visitVAArgInst(VAArgInst &Inst) { @@ -419,14 +430,14 @@ void visitExtractElementInst(ExtractElementInst &Inst) { auto *Ptr = Inst.getVectorOperand(); auto *Val = &Inst; - addDerefEdge(Ptr, Val); + addLoadEdge(Ptr, Val); } void visitInsertElementInst(InsertElementInst &Inst) { auto *Vec = Inst.getOperand(0); auto *Val = Inst.getOperand(1); addAssignEdge(Vec, &Inst); - addDerefEdge(&Inst, Val); + addStoreEdge(Val, &Inst); } void visitLandingPadInst(LandingPadInst &Inst) { @@ -440,12 +451,12 @@ auto *Agg = Inst.getOperand(0); auto *Val = Inst.getOperand(1); addAssignEdge(Agg, &Inst); - addDerefEdge(&Inst, Val); + addStoreEdge(Val, &Inst); } void visitExtractValueInst(ExtractValueInst &Inst) { auto *Ptr = Inst.getAggregateOperand(); - addDerefEdge(Ptr, &Inst); + addLoadEdge(Ptr, &Inst); } void visitShuffleVectorInst(ShuffleVectorInst &Inst) { Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/Andersen/assign.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/Andersen/assign.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/Andersen/assign.ll @@ -0,0 +1,24 @@ +; This testcase ensures that CFL AA handles assignment in an inclusion-based +; manner + +; RUN: opt < %s -disable-basicaa -cfl-anders-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -aa-pipeline=cfl-anders-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s + +; CHECK-LABEL: Function: test_assign +; CHECK: NoAlias: i64* %a, i64* %b +; CHECK: NoAlias: i32* %c, i64* %b +; CHECK: NoAlias: i32* %d, i64* %a +; CHECK: NoAlias: i32* %c, i32* %d +; CHECK: MayAlias: i32* %e, i64* %a +; CHECK: MayAlias: i32* %e, i64* %b +; CHECK: MayAlias: i32* %c, i32* %e +; CHECK: MayAlias: i32* %d, i32* %e +define void @test_assign(i1 %cond) { + %a = alloca i64, align 8 + %b = alloca i64, align 8 + + %c = bitcast i64* %a to i32* + %d = bitcast i64* %b to i32* + %e = select i1 %cond, i32* %c, i32* %d + ret void +} \ No newline at end of file Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/Andersen/assign2.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/Andersen/assign2.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/Andersen/assign2.ll @@ -0,0 +1,23 @@ +; This testcase ensures that CFL AA handles assignment in an inclusion-based +; manner + +; RUN: opt < %s -disable-basicaa -cfl-anders-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -aa-pipeline=cfl-anders-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s + +; CHECK-LABEL: Function: test_assign2 +; CHECK: NoAlias: i32* %b, i64* %a +; CHECK: NoAlias: i32* %b, i32* %c +; CHECK: NoAlias: i32* %b, i32* %d +; CHECK: MayAlias: i32* %e, i64* %a +; CHECK: MayAlias: i32* %b, i32* %e +; CHECK: MayAlias: i32* %c, i32* %e +; CHECK: MayAlias: i32* %d, i32* %e +define void @test_assign2(i1 %cond) { + %a = alloca i64, align 8 + %b = alloca i32, align 4 + + %c = bitcast i64* %a to i32* + %d = bitcast i64* %a to i32* + %e = select i1 %cond, i32* %c, i32* %b + ret void +} \ No newline at end of file Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/Andersen/cycle.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/Andersen/cycle.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/Andersen/cycle.ll @@ -0,0 +1,34 @@ +; This testcase ensures that CFL AA handles assignment cycles correctly + +; RUN: opt < %s -disable-basicaa -cfl-anders-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -aa-pipeline=cfl-anders-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s + +; CHECK-LABEL: Function: test_cycle +; CHECK: NoAlias: i64* %a, i64** %b +; CHECK: NoAlias: i64* %a, i64*** %c +; CHECK: NoAlias: i64** %b, i64*** %c +; CHECK: NoAlias: i64* %a, i64**** %d +; CHECK: NoAlias: i64** %b, i64**** %d +; CHECK: NoAlias: i64*** %c, i64**** %d +; CHECK: NoAlias: i64* %a, i64* %e +; CHECK: NoAlias: i64* %e, i64** %b +; CHECK: NoAlias: i64* %e, i64*** %c +; CHECK: MayAlias: i64* %a, i64* %f +; CHECK: NoAlias: i64* %f, i64** %b +; CHECK: NoAlias: i64* %f, i64*** %c +; CHECK: MayAlias: i64* %f, i64**** %d +; CHECK: MayAlias: i64* %e, i64* %f +define void @test_cycle() { + %a = alloca i64, align 8 + %b = alloca i64*, align 8 + %c = alloca i64**, align 8 + %d = alloca i64***, align 8 + store i64* %a, i64** %b + store i64** %b, i64*** %c + store i64*** %c, i64**** %d + + %e = bitcast i64**** %d to i64* + store i64* %e, i64** %b + %f = load i64*, i64** %b + ret void +} Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/Andersen/memalias.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/Andersen/memalias.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/Andersen/memalias.ll @@ -0,0 +1,21 @@ +; This testcase ensures that CFL AA correctly handles simple memory alias +; pattern + +; RUN: opt < %s -disable-basicaa -cfl-anders-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -aa-pipeline=cfl-anders-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s + +; CHECK-LABEL: Function: test_memalias +; CHECK: NoAlias: i64* %a, i64** %b +; CHECK: NoAlias: i32** %c, i64* %a +; CHECK: MayAlias: i32* %d, i64* %a +; CHECK: NoAlias: i32* %d, i64** %b +; CHECK: NoAlias: i32* %d, i32** %c +define void @test_memalias() { + %a = alloca i64, align 8 + %b = alloca i64*, align 8 + store i64* %a, i64** %b + + %c = bitcast i64** %b to i32** + %d = load i32*, i32** %c + ret void +} \ No newline at end of file