Index: include/llvm/Analysis/CFLOnDemandAliasAnalysis.h =================================================================== --- /dev/null +++ include/llvm/Analysis/CFLOnDemandAliasAnalysis.h @@ -0,0 +1,120 @@ +//===- CFLAliasAnalysis.h - CFL-Based Alias Analysis Interface ---*- C++ -*-==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// \file +/// This is the interface for LLVM's primary stateless and local alias analysis. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_CFLONDEMANDALIASANALYSIS_H +#define LLVM_ANALYSIS_CFLONDEMANDALIASANALYSIS_H + +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/None.h" +#include "llvm/ADT/Optional.h" +#include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/Module.h" +#include "llvm/IR/ValueHandle.h" +#include "llvm/Pass.h" +#include + +namespace llvm { + +class CFLODAAResult : public AAResultBase { + friend AAResultBase; + + struct FunctionInfo; + +public: + explicit CFLODAAResult(); + CFLODAAResult(CFLODAAResult &&Arg); + ~CFLODAAResult(); + + /// 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; } + + /// \brief Inserts the given Function into the cache. + void scan(Function *Fn); + void rescan(Function *Fn); /// Rebuild information after transformations + + void evict(Function *Fn); + + /// \brief Ensures that the given function is available in the cache. + /// Returns the appropriate entry from the cache. + FunctionInfo *ensureCached(Function *Fn); + Optional getCached(Function *Fn); + + AliasResult query(const MemoryLocation &LocA, const MemoryLocation &LocB); + + AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB) { + if (LocA.Ptr == LocB.Ptr) + return LocA.Size == LocB.Size ? MustAlias : PartialAlias; + AliasResult QueryResult = query(LocA, LocB); + return QueryResult; + } + void setActiveFunction(Function*); + +private: + AliasResult query(Function * Fn, Value * ValA, Value * ValB); + + /// \brief Cached mapping of Functions to their equivalence class. + /// 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; + Function *ActiveFunction = nullptr; + + /// Builds the graph + StratifiedSets for a function. + std::unique_ptr buildSetsFrom(Function *F); +}; + +/// Analysis pass providing a never-invalidated alias analysis result. +/// +/// FIXME: We really should refactor CFL to use the analysis more heavily, and +/// in particular to leverage invalidation to trigger re-computation of sets. +class CFLODAA : public AnalysisInfoMixin { + friend AnalysisInfoMixin ; + static char PassID; + +public: + typedef CFLODAAResult Result; + CFLODAAResult run(Function &F, AnalysisManager *AM); +}; + +/// Legacy wrapper pass to provide the CFLODAAResult object. +class CFLODAAWrapperPass : public ImmutablePass { + std::unique_ptr Result; + +public: + static char ID; + + CFLODAAWrapperPass(); + + CFLODAAResult &getResult() { return *Result; } + const CFLODAAResult &getResult() const { return *Result; } + + bool doInitialization(Module &M) override; + bool doFinalization(Module &M) override; + void getAnalysisUsage(AnalysisUsage &AU) const override; +}; + +//===--------------------------------------------------------------------===// +// +// createCFLOnDemandAAWrapperPass - This pass implements a set-based approach to +// alias analysis. +// +ImmutablePass *createCFLOnDemandAAWrapperPass(); +FunctionPass *createCFLOnDemandAARebuildPass(); +} + +#endif Index: include/llvm/Analysis/LabeledBidirectionalGraph.h =================================================================== --- /dev/null +++ include/llvm/Analysis/LabeledBidirectionalGraph.h @@ -0,0 +1,143 @@ +//===- LabeledBidirectionalGraph.h -----------------------------------------==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines a simple labeled, bidirectional graph expressed with +// adjacency lists. +// +//===----------------------------------------------------------------------===// + +#ifndef LABELEDBIDRECTIONALGRAPH_H +#define LABELEDBIDRECTIONALGRAPH_H 1 + +#include +#include + +namespace llvm { + +// Set building requires a Labeled bidirectional graph. +template class LabeledBidirectionalGraph { +public: + typedef std::size_t Node; + + struct Edge { + EdgeTypeT Type; + Node Other; + + Edge(EdgeTypeT Type, Node Other) : Type(Type), Other(Other) {} + + bool operator==(Edge E) const { + return Type == E.Type && Other == E.Other; + } + + bool operator!=(Edge E) const { return !operator==(E); } + }; + +private: + typedef SmallVector EdgesVectorType; + struct NodeImpl { + EdgesVectorType Edges; + }; + + std::vector NodeImpls; + + const NodeImpl &getNode(Node N) const { return NodeImpls[N]; } + NodeImpl &getNode(Node N) { return NodeImpls[N]; } +#ifndef NDEBUG + unsigned EdgeCount = 0; +#endif + +public: + bool inbounds(Node NodeIndex) const { return NodeIndex < NodeImpls.size(); } + + // ----- Actual graph-related things ----- // + + LabeledBidirectionalGraph() {} + + LabeledBidirectionalGraph(LabeledBidirectionalGraph &&Other) + : NodeImpls(std::move(Other.NodeImpls)) {} + + LabeledBidirectionalGraph(const LabeledBidirectionalGraph &G) { + NodeImpls = G.NodeImpls; + } + + LabeledBidirectionalGraph &operator=(const LabeledBidirectionalGraph &G) { + NodeImpls = G.NodeImpls; + return *this; + } + + LabeledBidirectionalGraph & + operator=(LabeledBidirectionalGraph &&Other) { + NodeImpls = std::move(Other.NodeImpls); + return *this; + } + + Node addNode() { + auto Index = NodeImpls.size(); + auto NewNode = Node(Index); + NodeImpls.push_back(NodeImpl()); + return NewNode; + } + + void addEdge(Node From, Node To, EdgeTypeT Label, EdgeTypeT ReverseLabel) { + assert(inbounds(From)); + assert(inbounds(To)); + getNode(From).Edges.emplace_back(Label, To); + getNode(To).Edges.emplace_back(ReverseLabel, From); + } + void addEdge(Node From, Node To, EdgeTypeT Label) { + assert(inbounds(From)); + assert(inbounds(To)); + auto &FromNode = getNode(From); + FromNode.Edges.emplace_back(Label, To); + } + + bool empty() const { return NodeImpls.empty(); } + std::size_t size() const { return NodeImpls.size(); } + + const EdgesVectorType &edges(Node N) const { + assert(inbounds(N)); + return NodeImpls[N].Edges; + } + + bool hasEdgeType(Node N, EdgeTypeT Type) const { + for (auto &E : edges(N)) + if (E.Type == Type) + return true; + return false; + } + bool hasEdge(Node N, Node Other, EdgeTypeT Type) const { + assert(inbounds(N)); + for (auto &E : edges(N)) + if (E.Type == Type && E.Other == Other) + return true; + return false; + } + Optional firstSuccessorByType(Node N, EdgeTypeT Type) const { + for (auto &E : edges(N)) + if (E.Type == Type) + return E.Other; + return None; + } + + /// An adaptor to support range-based for iteration over nodes. + class NodeIterator { + Node Current; + + public: + NodeIterator(size_t Current) : Current(static_cast(Current)) {} + void operator++() { ++Current; } + Node operator*() { return Current; } + bool operator==(NodeIterator E) { return Current == E.Current; } + bool operator!=(NodeIterator E) { return Current != E.Current; } + }; + NodeIterator begin() const { return NodeIterator(0); } + NodeIterator end() const { return NodeIterator(size()); } +}; +} +#endif Index: include/llvm/InitializePasses.h =================================================================== --- include/llvm/InitializePasses.h +++ include/llvm/InitializePasses.h @@ -87,6 +87,8 @@ void initializeCFGViewerPass(PassRegistry&); void initializeCFLAndersAAWrapperPassPass(PassRegistry&); void initializeCFLSteensAAWrapperPassPass(PassRegistry&); +void initializeCFLODAAWrapperPassPass(PassRegistry&); +void initializeCFLODAARebuildPassPass(PassRegistry&); void initializeCallGraphDOTPrinterPass(PassRegistry&); void initializeCallGraphPrinterLegacyPassPass(PassRegistry&); void initializeCallGraphViewerPass(PassRegistry&); Index: include/llvm/LinkAllPasses.h =================================================================== --- include/llvm/LinkAllPasses.h +++ include/llvm/LinkAllPasses.h @@ -21,6 +21,7 @@ #include "llvm/Analysis/BasicAliasAnalysis.h" #include "llvm/Analysis/CFLAndersAliasAnalysis.h" #include "llvm/Analysis/CFLSteensAliasAnalysis.h" +#include "llvm/Analysis/CFLOnDemandAliasAnalysis.h" #include "llvm/Analysis/CallPrinter.h" #include "llvm/Analysis/DomPrinter.h" #include "llvm/Analysis/GlobalsModRef.h" @@ -76,6 +77,7 @@ (void) llvm::createCallGraphViewerPass(); (void) llvm::createCFGSimplificationPass(); (void) llvm::createCFLAndersAAWrapperPass(); + (void) llvm::createCFLOnDemandAAWrapperPass(); (void) llvm::createCFLSteensAAWrapperPass(); (void) llvm::createStructurizeCFGPass(); (void) llvm::createConstantMergePass(); Index: lib/Analysis/AliasAnalysis.cpp =================================================================== --- lib/Analysis/AliasAnalysis.cpp +++ lib/Analysis/AliasAnalysis.cpp @@ -29,6 +29,7 @@ #include "llvm/Analysis/CFG.h" #include "llvm/Analysis/CFLAndersAliasAnalysis.h" #include "llvm/Analysis/CFLSteensAliasAnalysis.h" +#include "llvm/Analysis/CFLOnDemandAliasAnalysis.h" #include "llvm/Analysis/CaptureTracking.h" #include "llvm/Analysis/GlobalsModRef.h" #include "llvm/Analysis/ObjCARCAliasAnalysis.h" @@ -558,6 +559,7 @@ INITIALIZE_PASS_DEPENDENCY(BasicAAWrapperPass) INITIALIZE_PASS_DEPENDENCY(CFLAndersAAWrapperPass) INITIALIZE_PASS_DEPENDENCY(CFLSteensAAWrapperPass) +INITIALIZE_PASS_DEPENDENCY(CFLODAAWrapperPass) INITIALIZE_PASS_DEPENDENCY(ExternalAAWrapperPass) INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass) INITIALIZE_PASS_DEPENDENCY(ObjCARCAAWrapperPass) @@ -612,6 +614,8 @@ AAR->addAAResult(WrapperPass->getResult()); if (auto *WrapperPass = getAnalysisIfAvailable()) AAR->addAAResult(WrapperPass->getResult()); + if (auto *WrapperPass = getAnalysisIfAvailable()) + AAR->addAAResult(WrapperPass->getResult()); // If available, run an external AA providing callback over the results as // well. @@ -638,6 +642,7 @@ AU.addUsedIfAvailable(); AU.addUsedIfAvailable(); AU.addUsedIfAvailable(); + AU.addUsedIfAvailable(); AU.addUsedIfAvailable(); } @@ -664,6 +669,8 @@ AAR.addAAResult(WrapperPass->getResult()); if (auto *WrapperPass = P.getAnalysisIfAvailable()) AAR.addAAResult(WrapperPass->getResult()); + if (auto *WrapperPass = P.getAnalysisIfAvailable()) + AAR.addAAResult(WrapperPass->getResult()); return AAR; } @@ -707,4 +714,5 @@ AU.addUsedIfAvailable(); AU.addUsedIfAvailable(); AU.addUsedIfAvailable(); + AU.addUsedIfAvailable(); } Index: lib/Analysis/Analysis.cpp =================================================================== --- lib/Analysis/Analysis.cpp +++ lib/Analysis/Analysis.cpp @@ -36,6 +36,7 @@ initializeCFGOnlyPrinterPass(Registry); initializeCFLAndersAAWrapperPassPass(Registry); initializeCFLSteensAAWrapperPassPass(Registry); + initializeCFLODAAWrapperPassPass(Registry); initializeDependenceAnalysisWrapperPassPass(Registry); initializeDelinearizationPass(Registry); initializeDemandedBitsWrapperPassPass(Registry); Index: lib/Analysis/CFLOnDemandAliasAnalysis.cpp =================================================================== --- /dev/null +++ lib/Analysis/CFLOnDemandAliasAnalysis.cpp @@ -0,0 +1,2937 @@ +//===- CFLOnDemandAliasAnalysis.cpp - CFL-Based Alias-Analysis Implementation=// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This analysis is a variation of that implemented in CFLAliasAnalysis.cpp but +// differs in how globals and unknown functions are handled, how +// cross-procedural information is handled, and retains the "on-demand" search +// aspect to improve precision. +// +// This file implements a CFL-based context-insensitive alias analysis +// algorithm. It does not depend on types. The algorithm is a mixture of the one +// described in "Demand-driven alias analysis for C" by Xin Zheng and Radu +// Rugina, and "Fast algorithms for Dyck-CFL-reachability with applications to +// Alias Analysis" by Zhang Q, Lyu M R, Yuan H, and Su Z. -- to summarize the +// papers, we build a graph of the uses of a variable, where each node is a +// memory location, and each edge is an action that happened on that memory +// location. The "actions" can be one of Dereference, Reference, AssignTo, or +// AssignFrom. +// +// An alias exists if there are certain paths in this graph whose labels are +// described be a context free language. The details are described below. +// +// We perform a compression on this graph which reduces the number of nodes +// without sacrificing precision. This compression reduces the cost of searching +// for paths in the graph. In compressed form, graphs frequently reduce to a +// "simple" form where path searches can be done in unit time. +// +// We then force nodes of the graph into an equivalence relation. This relation +// allows for unit-time tests for no-alias avoiding the need to search the graph +// for paths at all. +// +// We exnted to a cross-procedural analysis by maintaining two graphs which make +// different assumptions about formal arguments. We can copy the optimistic +// graoh of a called into the caller when it is below some size limit. Otherwise +// we make pessimestic assumptions about the effects of a function call on +// pointer parameters and return values. +// +// As an aide in debugging, we retain an uncompressed graph and support an +// option +// to do path analysis on that graph to confirm the same result. +// +// There are four distinct parts of this implementation +// -- code that builds the pointer abstraction graph from the input IR +// -- code which compresses these graphs and computes equivalence class +// approximations +// -- code which does on-demand exploration of the graph. +// -- code to integrate with alias analysis framework and pass manager +// +// The key top-level classes defined here: +// PointerGraph -- the graph which abstracts operatons on pointers +// GraphBuilder -- the functions to build the PointerGraph from the base IR +// GraphInfo -- the information retained from GraphBuilder that is used +// later during alias analysis and cross-procedural use in other +// functions +// Combiner -- functions used to compress the "full" graph to reduce the +// cost of later queries +// Searcher -- state and functions used to directly search a PointerGraph +// for paths which imply aliases +// CFLODAAResult::FunctionInfo -- all the information retained for a +// function +// +//===----------------------------------------------------------------------===// + +// N.B. AliasAnalysis as a whole is phrased as a FunctionPass at the moment, and +// CFLODAA is interprocedural. This is *technically* A Bad Thing, because +// FunctionPasses are only allowed to inspect the Function that they're being +// run on. Realistically, this likely isn't a problem until we allow +// FunctionPasses to run concurrently. + +#ifdef NDEBUG +#define ENABLE_EXPERIMENTS 0 +#define DEBUG_SEARCH 0 +#else +// Enable the extra features needed to experiment with on-demand searching +// if the uncompress pointer graph. +#define ENABLE_EXPERIMENTS 1 +// Enable debugging messages for searching the graph. +#define DEBUG_SEARCH 0 +// When compressing, combine all aliases of the heap node into the node. +// This will loose precision. +#define COMPRESS_HEAP_ALIASES 1 +// Retain the uncompress graph so we can compare searches on that graph +// to searches on the compressed graph. This provides both validation +// of the correctness of the compression and measurement of loss of precision. +#define SEARCH_FULL_GRAPH 1 +#endif + +#include "llvm/Analysis/CFLOnDemandAliasAnalysis.h" + +#include "llvm/ADT/BitVector.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/None.h" +#include "llvm/ADT/Optional.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/Analysis/LabeledBidirectionalGraph.h" +#include "llvm/IR/Constants.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/InstVisitor.h" +#include "llvm/IR/Instructions.h" +#include "llvm/Pass.h" +#include "llvm/Support/Allocator.h" +#include "llvm/Support/Compiler.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/ErrorHandling.h" +#ifndef NDEBUG +#include "llvm/Support/FileSystem.h" +#endif +#include "llvm/Support/Format.h" +#ifndef NDEBUG +#include "llvm/Support/GraphWriter.h" +#endif +#include "llvm/Support/raw_ostream.h" +#include +#include +#include +#include +#include +#include +#include +#include + +using namespace llvm; + +static cl::opt FunctionReporting("cfl-stats", cl::Hidden, + cl::init(false)); + +/// This option sets a thrshold on the size of compressed graphs associated +/// with called functions which are willing to inline into the caller. +static cl::opt InlineLimit("cfl-inline-limit", cl::Hidden, + cl::init(50)); +/// Disable searching of the compressed graph to find more precision. +static cl::opt DisableSearch("cfl-no-search", cl::Hidden, + cl::init(false)); + +/// Given "p+i" where "i" is an integer, we by default +/// assume that "i" does not index outside of the object referenced by "p" +/// unless this option is specified. +static cl::opt UnsafeAddressing("cfl-unsafe-addressing", cl::Hidden, + cl::init(false)); + +/// A debugging a option which prints very lightweight status about phase entry +static cl::opt ShowStatus("cfl-status", cl::Hidden, cl::init(false)); +/// Print diagnostic note when untested IR features when first encountered. +static cl::opt ShowUntested("clf-untested", cl::Hidden, cl::init(false)); +/// As a validation aid, do graph search on the full graph when it is available. +static cl::opt FullGraphSearch("cfl-full-graph", cl::Hidden, + cl::init(false)); +/// Disable the use of "address bases" to refine equivalence classes for +/// fast path alias analysis +static cl::opt DontUseAddressBases("cfl-no-address-bases", cl::Hidden, + cl::init(false)); +#ifndef NDEBUG +static cl::opt DebugDump("cfl-dump", cl::Hidden, cl::init(false)); +/// Dump "non-simple" graphs for debugging. +static cl::opt DebugDumpNonSimple("cfl-dump-non-simple", cl::Hidden, + cl::init(false)); +/// Don't try to print instructions as labels for graph dumps. At some points +/// in compilation instructions won't print propertly and the compilation +/// will fault. +static cl::opt NoLabels("cfl-no-labels", cl::Hidden, cl::init(false)); + +/// Limit debug output to a specific analysis pass based on internal numbering. +static cl::opt + DebugOnly("cfl-debug", cl::Hidden, + cl::init(std::numeric_limits::max())); +#endif + +#define DEBUG_TYPE "cfl-od-aa" + +#ifdef LLVM_ENABLE_STATS +STATISTIC(MaxGraphSize, "Maximum compressed graph"); +STATISTIC(TotalGraphSize, "Total size of compressed graphs (edges)"); +#endif +STATISTIC(QueryCalls, "Number of calls to query()"); +STATISTIC(FastkNoAlias, "Number of NoAlias results on fast path"); +#if ENABLE_EXPERIMENTS +STATISTIC(SearchOps, "Number Search Steps"); +STATISTIC(FullSearchOps, "Number Full Graph Search Steps"); +STATISTIC(SimpleNoAlias, "Number of NoAlias results for Simple Graphs"); +STATISTIC(SlowNoAlias, "Number of NoAlias results on compressed search path"); +#ifdef LLVM_ENABLE_STAS +STATISTIC(FastViaAddressRoots, + "Number of NoAlias results absed on address roots"); +#endif +STATISTIC(FullNoAlias, "Number of NoALias Results on full path"); +STATISTIC(NoNodeForValue, + "Number of times there was no graph node for a value"); +#endif +STATISTIC(NumInstructions, "Number of instructions analyzed"); + +#ifndef NDEBUG +namespace { +/// This provieds a numbering scheme for calls to the analysis to +/// allow debug information to be limited to a specific pass. +int FunctionNumber = 0; +/// Map a function to a number for debugging use +DenseMap DebugNumber; +int NextFunctionNumber = 0; +void setDebugFlag() { + if (DebugOnly.getNumOccurrences()) + llvm::DebugFlag = (DebugOnly.getValue() == (unsigned)FunctionNumber); +} +void setDebugFlag(Function *Fn) { + FunctionNumber = DebugNumber[Fn]; + setDebugFlag(); +} +void dumpCFG(const Function &F) { + + std::string Filename = ("aa/cfg." + F.getName() + ".txt").str(); + errs() << "Writing '" << Filename << "'...\n"; + + std::error_code EC; + raw_fd_ostream File(Filename, EC, sys::fs::F_Text); + if (EC) { + errs() << "Unable top open " << Filename << "\n"; + return; + } + F.print(File); +} +} +#endif + +// A few macros for repeateed debugging/diagnostic actions. +#define DEBUG_MSG(x) DEBUG(dbgs() << x << '\n') +#define DEBUG_INST(x, y) DEBUG(dbgs() << x; y.dump()) +#define DEBUG_ONCE(x) \ + DEBUG({ \ + bool once = false; \ + if (!once) { \ + once = true; \ + dbgs() << x; \ + } \ + }) + +#define STATUS_MSG(x) \ + if (ShowStatus) \ + dbgs() << x << '\n' + +#define UNTESTED(x) \ + do { \ + static bool once = true; \ + if (once && ShowUntested) { \ + once = false; \ + dbgs() << x << '\n'; \ + } \ + } while (0) + +namespace { +/// Edges can be one of these "Labels" -- each Label must have an inverse +/// Label (Assign has Assign; Reference has Dereference) unless it use +/// in an transient manner. +enum class EdgeType { + /// The Label assigned when assigning from or to a value. For example, in: + /// %b = getelementptr %a, 0 + /// The relationships are %b assignFrom %a, and %a assignTo %b. + AssignTo, + AssignFrom, + + /// The edge used when we have an edge going from some "address" to a Value. + /// We create a single "dereference" for a pointer value. We then assign + /// from that to uses. + /// + /// Examples of this include: + /// %b = load %a (%a Derefer X , X assignTo %b) + /// %b = extractelement %a, 0 ... same + Dereference, + + /// The inverse of a Dereference + /// %b = load %a (%a Dereference X) (X refernce %a) + /// %b = extractelement %a, 0 ... same + Reference, + + /// Transient used during construction + /// store p, v (assign v to the unique dereference of p + /// will generate (p Dereference X) (v AssignTo X) + Store, +}; + +/// Edges come in pairs, return the label of the inverse edge given a label +EdgeType flipLabel(EdgeType Initial) { + switch (Initial) { + case EdgeType::AssignTo: + return EdgeType::AssignFrom; + case EdgeType::AssignFrom: + return EdgeType::AssignTo; + case EdgeType::Dereference: + return EdgeType::Reference; + case EdgeType::Reference: + return EdgeType::Dereference; + case EdgeType::Store: + assert(0 && "Unexpected edge type in flipLabel"); + return Initial; + } + llvm_unreachable("Incomplete coverage of EdgeType enum"); +} + +#ifndef NDEBUG +inline raw_ostream &operator<<(raw_ostream &Out, EdgeType Label) { + const char *str; + switch (Label) { + case EdgeType::AssignTo: + str = "assign"; + break; + case EdgeType::AssignFrom: + str = "assign from"; + break; + case EdgeType::Dereference: + str = "deref"; + break; + case EdgeType::Reference: + str = "ref"; + break; + case EdgeType::Store: + str = "store"; + break; + } + return Out << str; +} +#endif + +typedef LabeledBidirectionalGraph GraphT; +typedef GraphT::Node Node; +typedef DenseMap NodeMapT; + +/// This is the information we store about a node in the program IR. Two nodes +/// are not aliased if they have difference Class values or if the Address +/// fields are different and neither is NOT_ADDRESS_ROOT +struct AliasEquivInfo { + static const unsigned NOT_ADDRESS_ROOT = 0; + unsigned Class; + unsigned Address; + AliasEquivInfo(unsigned Class, unsigned Address = NOT_ADDRESS_ROOT) + : Class(Class), Address(Address) {} +}; +typedef DenseMap AliasEquivClassMap; + +/// A specialization of a labeled bidirectional graph +/// used to represent pointer operations in a function. +class PointerGraph : public GraphT { +public: + /// A sentinel used when no valid Node value is available. + static const Node NOT_A_NODE = std::numeric_limits::max(); + + /// The special node denoted "unknown" memory. This node has a particular + /// pessimestic structure. + Node Heap = NOT_A_NODE; + /// For var-args functions, denotes the block holding the parameters + Node VarArgs = NOT_A_NODE; + /// Partial map of Value* to Nodes + NodeMapT Map; + /// Nodes corresponding to formal arguments. Will be NOT_A_NODE + /// for non-pointer arguments + SmallVector FormalArguments; + /// Collection of GlobalValues used in a function or in a called + /// function whose graph is inlined. + SmallVector GlobalsValues; + /// Nodes whose values may be returned from this function + SmallVector ReturnedNodes; + + void addEdgeAndInverse(Node From, Node To, EdgeType Type) { + addEdge(From, To, Type, flipLabel(Type)); + } + + Node findOrCreateNode(Value *Val) { + + // Non-pointer values are assumed to refer to anywhere + // and this is modeled by mapping them to that unqiue Heap nodes + if (!Val->getType()->isPointerTy()) { + return Heap; + } + auto Pair = Map.insert(std::make_pair(Val, Node())); + auto &Iter = Pair.first; + if (Pair.second) { + auto NewNode = addNode(); + if (isa(Val)) { + // Addresses of globals values may be assigned into heap memory by + // other other functions so we model that directly. + addEdge(NewNode, Heap, EdgeType::AssignTo, EdgeType::AssignFrom); + GlobalsValues.push_back(Val); + } + Iter->second = NewNode; + } + return Iter->second; + } + + /// Initialize the unique heap nodes which is it's own dereference + /// and which is assigned to itself. We model unknown effects of called + /// functions and the calling context by assigning values to and from the heap + Node createHeap() { + if (Heap == NOT_A_NODE) { + Heap = addNode(); + assert(Heap == 0 && + "Heap node expected to be first node in PointerGraph"); + addEdge(Heap, Heap, EdgeType::AssignTo, EdgeType::AssignFrom); + addEdge(Heap, Heap, EdgeType::Dereference, EdgeType::Reference); + } + return Heap; + } + + /// Return the node corresponding to a value if it exists + Optional getNode(Value *V) const { + auto Iter = Map.find(V); + if (Iter == Map.end()) + return None; + return Iter->second; + } + + /// Return the "dereference" of a node, if it exists + /// There will be at most one such node. + Optional getDeref(Node N) const { + return firstSuccessorByType(N, EdgeType::Dereference); + } + + /// Return the unique dereference successor of a node, + /// creating it if it does not already exist + Node findOrCreateDeref(Node N) { + if (auto Deref = getDeref(N)) + return *Deref; + auto Deref = addNode(); + addEdge(N, Deref, EdgeType::Dereference, EdgeType::Reference); + return Deref; + } + +#if ENABLE_EXPERIMENTS + /// A pointer graph is "simple" when every non-heap node has every + /// AssignTo edge and every Dereference pointing to the unique Heap node. + /// In a simple graph, we can simplify the search to just the two nodes + /// involved + bool isSimple() { + assert(Heap == 0); + for (auto N : nonHeapNodes()) { + for (auto E : edges(N)) { + if (E.Other != Heap) + return false; + if (E.Type != EdgeType::Dereference && E.Type != EdgeType::AssignTo) + return false; + } + } + return true; + } + /// In a "simple" graph, every node that is not the heap + /// has only AssignTo and Dereference edges which point to the heap + /// and no other edges. In this case, we can simplify the search: + /// two non-heap nodes are not aliased + /// a non-heap node aliases the heap if there is an assign edge to the heap + bool simpleMayAlias(Node A, Node B); +#endif + + /// A node N is an AddressRoot if it is not assigned from some other + /// node and is not the dereference of some other node. + bool isAddressRoot(Node N) { + for (auto E : edges(N)) + if (E.Type == EdgeType::AssignFrom || E.Type == EdgeType::Reference) + return false; + return true; + } + + /// Simple wrapper that iterates over all nodes except the Heap node. + class NonHeapNodes { + size_t N; + + public: + NonHeapNodes(const PointerGraph &G) : N(G.size()) {} + NodeIterator begin() { return NodeIterator(1); } + NodeIterator end() { return NodeIterator(N); } + }; + NonHeapNodes nonHeapNodes() const { return NonHeapNodes(*this); } + + /// Perform compression on a graph to yield a new graph. + /// When \p ForInlining is true, then separate heuristics are used + /// for that scenario + PointerGraph compress(bool ForInlining); + +#ifndef NDEBUG + void dump(const Function &F, const AliasEquivClassMap *AliasEquivClass, + const class Combiner *DoCombining, const char *label, + bool PrintValues = true, Node ONLY_A = NOT_A_NODE, + Node ONLY_B = NOT_A_NODE) const; + /// Debugging aide: validate structure of the graph + void check(const char *label, const Function &Fn) const; +#endif +}; + +/// Information computed from the base IR and retained for alias analysis +/// and subsequence cross-procedure use. +class GraphInfo { +public: + /// The summary of pointer operations for a function. + PointerGraph Graph; + /// An equivalence relation on Values which conservatively approximates the + /// alias relation. If two values map to different classes, they are not + /// aliased + AliasEquivClassMap AliasEquivClass; + + /// Return true if we A and B are known to be in distinct alias + /// equivalence classes. + bool distinctAliasEquivalenceClassses(Value *A, Value *B) { + auto AIter = AliasEquivClass.find(A); + if (AIter == AliasEquivClass.end()) + return false; + auto BIter = AliasEquivClass.find(B); + if (BIter == AliasEquivClass.end()) + return false; + if (AIter->second.Class != BIter->second.Class) + return true; + if (!DontUseAddressBases) { + // same class and same address root? + if (AIter->second.Address == BIter->second.Address) + return false; + // both are actually address roots? + if (AIter->second.Address != AliasEquivInfo::NOT_ADDRESS_ROOT && + BIter->second.Address != AliasEquivInfo::NOT_ADDRESS_ROOT) { +#ifndef ENABLE_EXPERIMENTS + FastViaAddressRoots += 1; +#endif + return true; + } + } + return false; + } +}; + +struct BuilderEdge; + +/// This class does combining of nodes into equivalence classes supporting +/// an precise reduction aimed at just reducing graph size and an imprecise +/// scenario used to reduce query cost. +class Combiner { + const PointerGraph &G; + static const Node MULTIPLE_SOURCES = (PointerGraph::NOT_A_NODE - 1); + + struct Info { + /// State used to implement a disjoint-set union-find algorithm + Node Parent = PointerGraph::NOT_A_NODE; + bool isRoot() { return Parent == PointerGraph::NOT_A_NODE; } + + /// We maintain an invariant that all Dereference edges from one + /// node class refer to the same node class, combining as needed. + Node Deref = PointerGraph::NOT_A_NODE; + + /// We mark nodes "live" if they are needed in an output graph. + /// The exact semantics depend on whether we are compressiong for inlining + /// or alias testing. + bool IsLive = false; + + /// Used to find the unique class which is the source of + /// AssignTo edges into the current class + Node Src; + + /// Final alias class number + unsigned AliasClassNumber; + Info() {} + Info(Node Deref) : Deref(Deref) {} + }; + std::vector NodeInfo; + + /// Initialize NodeInfo and record dereference nodes + void initialize() { + NodeInfo.clear(); + NodeInfo.reserve(G.size()); + for (Node I : G) { + Node Deref = PointerGraph::NOT_A_NODE; + if (auto D = G.getDeref(I)) + Deref = *D; + NodeInfo.emplace_back(Deref); + } + } + + /// Return the root node for set containing A and perform + /// path compression on the tree. + Node getComponent(Node A) { + Node Root = A; + SmallVector Path; + for (;;) { + auto &Info = NodeInfo[Root]; + if (Info.isRoot()) + break; + Path.push_back(Root); + Root = Info.Parent; + } + + // Path compression to reduce future query costs. + for (auto Cur : Path) + NodeInfo[Cur].Parent = Root; + + return Root; + } + /// Return true if these nodes are in the same equivalence class. + bool sameClass(Node C1, Node C2) { + return getComponent(C1) == getComponent(C2); + } + /// Combine the components containing the single node and return + /// true a change is made. + bool combine(Node C1, Node C2) { + C1 = getComponent(C1); + C2 = getComponent(C2); + if (C1 == C2) + return false; + + // This guarantees that the heap node 0 is a root + if (C1 > C2) + std::swap(C1, C2); + DEBUG_MSG("combine N" << C2 << " -> N" << C1); + assert(NodeInfo[C1].isRoot()); + assert(NodeInfo[C2].isRoot()); + auto D2 = NodeInfo[C2].Deref; + NodeInfo[C2].Parent = C1; + if (D2 != PointerGraph::NOT_A_NODE) { + auto D1 = NodeInfo[C1].Deref; + if (D1 == PointerGraph::NOT_A_NODE) + NodeInfo[C1].Deref = D2; + else + combine(D1, D2); + } + return true; + } + + /// The number of classes after all combining. + unsigned NumClasses = 0; + + /// Assign unique numbers to each final class which holds a live node. + void numberRoots() { + for (Node I : G) + if (NodeInfo[I].IsLive) + NodeInfo[getComponent(I)].IsLive = true; + + for (Node I : G) + if (NodeInfo[I].isRoot() && NodeInfo[I].IsLive) + NodeInfo[I].AliasClassNumber = NumClasses++; + } + + /// Mark as IsLive those nodes which are needed either for inlining + /// or for query support depending on the parameter. + void trimDead(bool TrimToFormals); + + /// Walk the "heap" and nodes connected to it by assignment to find nodes + /// which are indistinguishable from the heap from an alias perspective. + void walkHeap(); + + /// Find unique assignment values into a equivalence class of nodes to allow + /// combining of assignment chains. + void walkAssignTrees(); + + /// Look at AssignFrom edges that target N and return the unique + /// source of those edges if there is one. MULTIPLE_SOURCES if there + /// are more than one source and NOT_A_NODE if there are none. + Node uniqueSource(Node N); + +public: + Combiner(const PointerGraph &G) : G(G){}; + /// Combine nodes connected via assignment and + /// Dereferences from the common class + void doCombiningForEquivClasses(); + + /// Combine nodes to reduce size but without loss of CFL precision + void doCombiningForSize(bool TrimForInlining); + + /// Return the final number of classes. + unsigned getNumClasses() const { return NumClasses; } + + /// Get the equivalence class number for a graph node. + Node getIndex(Node Node) const { + while (NodeInfo[Node].Parent != PointerGraph::NOT_A_NODE) + Node = NodeInfo[Node].Parent; + auto &Info = NodeInfo[Node]; + if (Info.IsLive) + return NodeInfo[Node].AliasClassNumber; + return PointerGraph::NOT_A_NODE; + }; +}; + +/// This class translate the IR of a function into the GraphInfo +class GraphBuilder : public GraphInfo { + Function *Fn; + CFLODAAResult &Analysis; + /// This graph will be used for callers who want to model the effects of call. + PointerGraph GraphToInline; +#if ENABLE_EXPERIMENTS + /// This is the uncompressed graph used to verify optimizations. + PointerGraph FullGraph; +#endif + + /// Build the full graph from the input Function. + void buildGraph(); + + /// Process one instruction and add its effects to the graph. + void addInstructionToGraph(Instruction &Inst); + + /// Get the edges of a ConstantExpr as if it was an Instruction. This + /// function also acts on any nested ConstantExprs, adding the edges + /// of those to the given SmallVector as well. + void constexprToEdges(ConstantExpr &CExprToCollapse, + SmallVectorImpl &Results); + + void addEdgeToGraph(BuilderEdge E); + // Gets edges of the given Instruction*, writing them to the SmallVector*. + void argsToEdges(CFLODAAResult &, Instruction *, + SmallVectorImpl &); + + // Gets edges of the given ConstantExpr*, writing them to the SmallVector*. + void argsToEdges(CFLODAAResult &, ConstantExpr *, + SmallVectorImpl &); + + // Convert to pessimestic assumptions for pointer parameters that they + // are initialized from the heap. + void convertFormalArgumentsToHeap(); + + // Support for compressing the graph by combining nodes and for + // determing equivalance classes + Combiner DoCombining; + + static bool hasUsefulEdges(Instruction *Inst); + static bool hasUsefulEdges(ConstantExpr *CE); + + // Some instructions need to have their users tracked. Instructions like + // `add` require you to get the users of the Instruction* itself, other + // instructions like `store` require you to get the users of the first + // operand. This function gets the "proper" value to track for each + // type of instruction we support. + static Optional getTargetValue(Instruction *Inst); + +public: + GraphBuilder(Function *Fn, CFLODAAResult &Analysis) + : Fn(Fn), Analysis(Analysis), DoCombining(Graph) {} + + /// Build the abstract pointer operation graph and reduce it to an + /// approximate equivalence relation expressed as a mapping of Value* to + /// numbers. + void buildGraphAndEquivalences(); +#ifndef NDEBUG + const Combiner &getCombiner() { return DoCombining; } +#endif + PointerGraph &getGraphToInline() { return GraphToInline; } +#if ENABLE_EXPERIMENTS + PointerGraph &getFullGraph() { return FullGraph; } +#endif + GraphInfo &getGraph() { return *this; } +}; +} + +/// Information needed during alias analysis. +struct AliasInfo : public GraphInfo { + const char *DebugLabel; +#if ENABLE_EXPERIMENTS + /// True when the graph is "simple" accoring to the definition above. + bool SimpleGraph; + /// As we discover aliases between nodes, we can reuse them + /// in subsequent queries. + DenseMap> AliasMem; + + /// True if we have fully resolved the aliases of some node. + std::vector AliasesKnown; +#endif + +#if !ENABLE_EXPERIMENTS + /// Constructor for compressed graph. + AliasInfo(GraphInfo *Graph) { + AliasEquivClass = std::move(Graph->AliasEquivClass); + } +#else + AliasInfo(GraphInfo *Graph) + : GraphInfo(std::move(*Graph)), DebugLabel(""), + AliasesKnown(GraphInfo::Graph.size(), false) { + SimpleGraph = this->Graph.isSimple(); + } + /// Constructor for the "full graph". + AliasInfo(PointerGraph *Graph) + : DebugLabel("full"), AliasesKnown(Graph->size(), false) { + GraphInfo::Graph = std::move(*Graph); + SimpleGraph = false; + } +#endif + // True if the two values may refer to the same memory location and + // false otherwise. + bool mayAlias(Value *p1, Value *p2); +#if ENABLE_EXPERIMENTS + // Diagnostic only, count number of search steps. + unsigned SearchCount = 0; +#endif +}; + +/// Information we have about a function and keep around to enable +/// alias testing. +struct CFLODAAResult::FunctionInfo : public AliasInfo { + + /// This graph will be used for callers who want + /// to model the effects of call. + PointerGraph GraphToInline; +#if SEARCH_FULL_GRAPH + /// The uncompressed graph, used to validate the compression and to + /// measure loss of procession. + AliasInfo FullInfo; +#endif + +#ifndef NDEBUG + /// Name of the function, for diagnostic output only. + std::string FunctionName; +#endif + FunctionInfo(GraphBuilder *Info) + : AliasInfo(&Info->getGraph()), + GraphToInline(std::move(Info->getGraphToInline())) +#if SEARCH_FULL_GRAPH + , + FullInfo(&Info->getFullGraph()) +#endif + { + } + +#ifndef NDEBUG + /// Per function count of number of queries + unsigned QueryCount = 0; + /// Per function number of MayAlias calls + unsigned MayAliasCount = 0; + /// Report per-function diagnostics. + void report(Function *F); +#endif +}; + +//===----------------------------------------------------------------------===// +// +// +// Code related to building an abstract pointer operation graph +// +// +//===----------------------------------------------------------------------===// + +void GraphBuilder::buildGraphAndEquivalences() { + + DEBUG(DebugDump = true); +#ifndef NDEBUG + if (DebugDump) + dumpCFG(*Fn); +#endif + + // Build the "full" operation graph. + buildGraph(); + + // Compress down to equivalence classes + DoCombining.doCombiningForEquivClasses(); +#ifndef NDEBUG + if (DebugDumpNonSimple && !Graph.isSimple()) + Graph.dump(*Fn, &AliasEquivClass, &DoCombining, ""); +#endif + + // Save map of Values to equivance class information. + for (const auto &P : Graph.Map) { + auto V = P.first; + auto N = P.second; + auto C = DoCombining.getIndex(N); + unsigned Address = AliasEquivInfo::NOT_ADDRESS_ROOT; + if (Graph.isAddressRoot(N)) + Address = N; + AliasEquivClass.insert(std::make_pair(V, AliasEquivInfo(C, Address))); + } + +#ifdef LLVM_ENABLE_STATS + // Compute graph size for statistics. + unsigned S = Graph.size(); + for (size_t N = 0; N < Graph.size(); ++N) + S += Graph.edges(N).size(); + + TotalGraphSize += S; + MaxGraphSize = std::max(MaxGraphSize, S); +#endif +} + +void GraphBuilder::buildGraph() { + + Graph.createHeap(); + + // Create nodes for formal arguments. + for (auto &Arg : Fn->args()) { + Node ArgNode = (Arg.getType()->isPointerTy() ? Graph.findOrCreateNode(&Arg) + : PointerGraph::NOT_A_NODE); + Graph.FormalArguments.push_back(ArgNode); + } + + // Create nodes and edges for each instruction and called function. + for (auto &Bb : Fn->getBasicBlockList()) + for (auto &Inst : Bb.getInstList()) + addInstructionToGraph(Inst); + +#ifndef NDEBUG + Graph.check("full", *Fn); +#endif + + // Save a compressed version of this graph for later inlining. + GraphToInline = Graph.compress(/*TrimForInlining*/ true); +#ifndef NDEBUG + GraphToInline.check("inline", *Fn); + if (DebugDump) + GraphToInline.dump(*Fn, nullptr, nullptr, "-inline"); +#endif + + // Make pessimestic assumptions about formal parameters. + convertFormalArgumentsToHeap(); +#ifndef NDEBUG + if (DebugDump) + Graph.dump(*Fn, nullptr, nullptr, "-full"); +#endif +#if SEARCH_FULL_GRAPH + if (FullGraphSearch) { + FullGraph = std::move(Graph); + Graph = FullGraph.compress(/*TrimForInlining*/ false); + } else +#endif + Graph = Graph.compress(/*TrimForInlining*/ false); +#ifndef NDEBUG + Graph.check("final", *Fn); +#endif +} + +namespace { +/// Encodes the notion of a "use" while we are building +/// the pointer abstraction graph. +struct BuilderEdge { + + /// Storing HEAP_VALUE to either From or To refers to an "unknown" value and + /// it will be translated into the Heap node. + constexpr static Value *const HEAP_VALUE = nullptr; + Value *From; + Value *To; + EdgeType Type; + + BuilderEdge(Value *From, Value *To, EdgeType Type) + : From(From), To(To), Type(Type) {} +}; +} + +// Given an Instruction, this will add it to the graph, along with any +// Instructions that are potentially only available from said Instruction +// For example, given the following line: +// %0 = load i16* getelementptr ([1 x i16]* @a, 0, 0), align 2 +// addInstructionToGraph would add both the `load` and `getelementptr` +// instructions to the graph appropriately. +void GraphBuilder::addInstructionToGraph(Instruction &Inst) { + NumInstructions += 1; +#ifndef NDEBUG + if (!NoLabels) + DEBUG_INST("add: " << (void *)&Inst << ' ', Inst); +#endif + if (!hasUsefulEdges(&Inst)) + return; + + SmallVector Edges; + + // Based on isntruction type, get a list of edges that should be + // part of the graph. This list is a little more general in form than + // the final graph. + argsToEdges(Analysis, &Inst, Edges); + + // In the case of an unused alloca (or similar), edges may be empty. Remember + // that it exists so we can potentially answer NoAlias. + if (Edges.empty()) { + auto MaybeVal = getTargetValue(&Inst); + assert(MaybeVal.hasValue()); + auto *Target = *MaybeVal; + DEBUG_MSG("\tedges empty, target"); + Graph.findOrCreateNode(Target); + return; + } + + if (isa(&Inst)) { + assert(Edges.size() == 1); + auto *From = Edges[0].From; + if (From->getType()->isPointerTy()) + Graph.ReturnedNodes.push_back(Graph.findOrCreateNode(From)); + // TODO: assign to heap? + return; + } + + // Find ConstantExpr's referneced by this Instruction. + SmallVector ConstantExprs; + for (const BuilderEdge &E : Edges) { + if (E.To != BuilderEdge::HEAP_VALUE) + if (auto *Constexpr = dyn_cast(E.To)) + ConstantExprs.push_back(Constexpr); + if (E.From != BuilderEdge::HEAP_VALUE) + if (auto *Constexpr = dyn_cast(E.From)) + ConstantExprs.push_back(Constexpr); + } + + // Avoid creating nodes which are single-source assignments by mapping + // this value to the same as the source. + if (Edges.size() == 1 && ConstantExprs.empty()) { + auto E = Edges[0]; + if (E.From == &Inst && E.To != BuilderEdge::HEAP_VALUE && + E.Type == EdgeType::AssignFrom && + Graph.Map.find(E.From) == Graph.Map.end()) { + Graph.Map[E.From] = Graph.findOrCreateNode(Edges[0].To); + return; + } + } + + for (const BuilderEdge &E : Edges) + addEdgeToGraph(E); + + // Walk the ConstantExpr looking for + for (ConstantExpr *CE : ConstantExprs) { + Edges.clear(); + constexprToEdges(*CE, Edges); + for (auto &Edge : Edges) + addEdgeToGraph(Edge); + } +} + +namespace { + +/// Get the edges the graph should have, based on an Instruction. +class GetEdgesVisitor : public InstVisitor { + + /// We give access to this result for cross-procedural cases + /// where we inline the graph for corresponding to the called function + CFLODAAResult &AA; + /// The graph we are currently building to handle cases where it + /// is expedient to directly add edges. + PointerGraph &Graph; + /// We capture the effecits of an instruciton as a set of + /// edges which will be added to Graph. + SmallVectorImpl &Output; + +public: + GetEdgesVisitor(CFLODAAResult &AA, PointerGraph &Graph, + SmallVectorImpl &Output) + : AA(AA), Graph(Graph), Output(Output) {} + + void visitInstruction(Instruction &) { + llvm_unreachable("Unsupported instruction encountered"); + } + + void visitReturnInst(ReturnInst &Inst) { + if (Inst.getNumOperands()) { + auto *Ptr = Inst.getOperand(0); + Output.emplace_back(Ptr, &Inst, EdgeType::AssignTo); + } + } + + void visitPtrToIntInst(PtrToIntInst &Inst) { + auto *Ptr = BuilderEdge::HEAP_VALUE; + Output.emplace_back(Inst.getOperand(0), Ptr, EdgeType::AssignTo); + } + + void visitIntToPtrInst(IntToPtrInst &Inst) { + auto *Ptr = BuilderEdge::HEAP_VALUE; + Output.emplace_back(Ptr, &Inst, EdgeType::AssignTo); + } + + void visitCastInst(CastInst &Inst) { + Output.emplace_back(&Inst, Inst.getOperand(0), EdgeType::AssignFrom); + } + + void visitBinaryOperator(BinaryOperator &Inst) { + Output.emplace_back(&Inst, Inst.getOperand(0), EdgeType::AssignFrom); + Output.emplace_back(&Inst, Inst.getOperand(1), EdgeType::AssignFrom); + } + + void visitAtomicCmpXchgInst(AtomicCmpXchgInst &Inst) { + auto *Ptr = Inst.getPointerOperand(); + auto *Val = Inst.getNewValOperand(); + Output.emplace_back(Val, Ptr, EdgeType::Store); + } + + void visitAtomicRMWInst(AtomicRMWInst &Inst) { + auto *Ptr = Inst.getPointerOperand(); + auto *Val = Inst.getValOperand(); + Output.emplace_back(Val, Ptr, EdgeType::Store); + } + + void visitPHINode(PHINode &Inst) { + for (Value *Val : Inst.incoming_values()) + Output.emplace_back(&Inst, Val, EdgeType::AssignFrom); + } + + void visitGetElementPtrInst(GetElementPtrInst &Inst) { + auto *Op = Inst.getPointerOperand(); + Output.emplace_back(&Inst, Op, EdgeType::AssignFrom); + if (isa(&Inst)) + return; + + // We assume here that the other inputs to the operations are + // values which do not change the object that is referenced. We can + // ignore them be cause we don't attempt to differentiate locations + // within an object. + if (Inst.isInBounds() || !UnsafeAddressing) + return; + + for (auto I = Inst.idx_begin(), E = Inst.idx_end(); I != E; ++I) + Output.emplace_back(&Inst, *I, EdgeType::AssignFrom); + } + + void visitSelectInst(SelectInst &Inst) { + // Condition is not processed here (The actual statement producing + // the condition result is processed elsewhere). For select, the + // condition is evaluated, but not loaded, stored, or assigned + // simply as a result of being the condition of a select. + + auto *TrueVal = Inst.getTrueValue(); + Output.emplace_back(&Inst, TrueVal, EdgeType::AssignFrom); + auto *FalseVal = Inst.getFalseValue(); + Output.emplace_back(&Inst, FalseVal, EdgeType::AssignFrom); + + // we don't have to worry about the condition (or any control dependence) + // since a pointer value would be cast to int and hence escaped. + } + + void visitAllocaInst(AllocaInst &) {} + + void visitLoadInst(LoadInst &Inst) { + auto *Ptr = Inst.getPointerOperand(); + auto *Val = &Inst; + Output.emplace_back(Val, Ptr, EdgeType::Reference); + } + + void visitStoreInst(StoreInst &Inst) { + auto *Ptr = Inst.getPointerOperand(); + auto *Val = Inst.getValueOperand(); + Output.emplace_back(Val, Ptr, EdgeType::Store); + } + + void visitVAArgInst(VAArgInst &Inst) { + // cdc: todo + // We can't fully model va_arg here. For *Ptr = Inst.getOperand(0), it + // does + // two things: + // 1. Loads a value from *((T*)*Ptr). + // 2. Increments (stores to) *Ptr by some target-specific amount. + // For now, we'll handle this like a landingpad instruction (by placing + // the + // result in its own group, and having that group alias externals). + assert(0 && "unexpected VAArgInst"); + auto *Val = &Inst; + auto *Ptr = BuilderEdge::HEAP_VALUE; + Output.emplace_back(Ptr, Val, EdgeType::AssignTo); + } + + static bool isFunctionExternal(Function *Fn) { + return !Fn->hasExactDefinition(); + } + + // Returns possible functions called by the Inst* into the given + // SmallVectorImpl. Returns true if targets found, false otherwise. + // This is templated because InvokeInst/CallInst give us the same + // set of functions that we care about, and I don't like repeating + // myself. + template + static bool getPossibleTargets(Inst *Call, + SmallVectorImpl &Output) { + if (auto *Fn = Call->getCalledFunction()) { + Output.push_back(Fn); + return true; + } + + // TODO: If the call is indirect, we might be able to enumerate all + // potential targets of the call and return them, rather than just failing. + return false; + } + + bool + tryInterproceduralAnalysis(Function *Fn, Value *FuncValue, + const iterator_range &Args); + bool handleIntrinsic(Intrinsic::ID ID, Value *FuncValue, + const iterator_range &Args); + template void visitCallLikeInst(InstT &Inst); + + void visitCallInst(CallInst &Inst); + void visitInvokeInst(InvokeInst &Inst) { visitCallLikeInst(Inst); } + + // Because vectors/aggregates are immutable and unaddressable, + // there's nothing we can do to coax a value out of them, other + // than calling Extract{Element,Value}. We can effectively treat + // them as pointers to arbitrary memory locations we can store in + // and load from. + void visitExtractElementInst(ExtractElementInst &Inst) { + UNTESTED("CFL -- ExtractElementInst"); + auto *Ptr = Inst.getVectorOperand(); + auto *Val = &Inst; + Output.emplace_back(Val, Ptr, EdgeType::Reference); + } + + void visitInsertElementInst(InsertElementInst &Inst) { + UNTESTED("CFL -- InsertElementInst"); + auto *Vec = Inst.getOperand(0); + auto *Val = Inst.getOperand(1); + Output.emplace_back(&Inst, Vec, EdgeType::AssignFrom); + Output.emplace_back(&Inst, Val, EdgeType::Dereference); + } + + void visitLandingPadInst(LandingPadInst &Inst) { + UNTESTED("CFL -- LandingPadInst"); + // Exceptions come from "nowhere", from our analysis' perspective. + // So we place the instruction its own group, noting that said group may + // alias externals + Output.emplace_back(&Inst, &Inst, EdgeType::AssignFrom); + } + + void visitInsertValueInst(InsertValueInst &Inst) { + UNTESTED("CFL -- InsertValueInst"); + auto *Agg = Inst.getOperand(0); + auto *Val = Inst.getOperand(1); + Output.emplace_back(&Inst, Agg, EdgeType::Store); + Output.emplace_back(&Inst, Val, EdgeType::Dereference); + } + + void visitExtractValueInst(ExtractValueInst &Inst) { + UNTESTED("CFL -- ExtractValueInst"); + auto *Ptr = Inst.getAggregateOperand(); + Output.emplace_back(&Inst, Ptr, EdgeType::Reference); + } + + void visitShuffleVectorInst(ShuffleVectorInst &Inst) { + UNTESTED("CFL -- ShuffleVectorInst"); + auto *From1 = Inst.getOperand(0); + auto *From2 = Inst.getOperand(1); + Output.emplace_back(&Inst, From1, EdgeType::AssignFrom); + Output.emplace_back(&Inst, From2, EdgeType::AssignFrom); + } + + void visitConstantExpr(ConstantExpr *CE) { + switch (CE->getOpcode()) { + default: + llvm_unreachable("Unknown instruction type encountered!"); +// Build the switch statement using the Instruction.def file. +#define HANDLE_INST(NUM, OPCODE, CLASS) \ + case Instruction::OPCODE: \ + visit##OPCODE(*(CLASS *)CE); \ + break; +#include "llvm/IR/Instruction.def" + } + } +}; + +void GraphBuilder::argsToEdges(CFLODAAResult &Analysis, Instruction *Inst, + SmallVectorImpl &Output) { + assert(hasUsefulEdges(Inst) && + "Expected instructions to have 'useful' edges"); + GetEdgesVisitor v(Analysis, Graph, Output); + v.visit(Inst); +} + +void GraphBuilder::argsToEdges(CFLODAAResult &Analysis, ConstantExpr *CE, + SmallVectorImpl &Output) { + assert(hasUsefulEdges(CE) && "Expected constant expr to have 'useful' edges"); + GetEdgesVisitor v(Analysis, Graph, Output); + v.visitConstantExpr(CE); +} + +void GetEdgesVisitor::visitCallInst(CallInst &Inst) { + if (auto *F = Inst.getCalledFunction()) { + if (F->getIntrinsicID() == Intrinsic::vastart) { + if (auto *Op = Inst.getArgOperand(0)) { + // This operation initalize the result to hold a pointer + // into the block of memory on the stack holding parameteters. + if (Graph.VarArgs == PointerGraph::NOT_A_NODE) { + Graph.VarArgs = Graph.addNode(); + Graph.addEdge(Graph.Heap, Graph.findOrCreateDeref(Graph.VarArgs), + EdgeType::AssignTo, EdgeType::AssignFrom); + } + auto From = Graph.VarArgs; + auto To = Graph.findOrCreateDeref(Graph.findOrCreateNode(Op)); + Graph.addEdge(From, To, EdgeType::AssignTo, EdgeType::AssignFrom); + return; + } + } + } + visitCallLikeInst(Inst); +} + +template void GetEdgesVisitor::visitCallLikeInst(InstT &Inst) { + + if (isNoAliasCall(&Inst)) + return; + + SmallVector Targets; + if (getPossibleTargets(&Inst, Targets) && Targets.size() == 1) { + + // If we can resolve the target, or a set of possible targets + // we can handle them as intrinstics or via inlining. + auto TryInterprocedural = [this, &Inst](Function *Fn) { + if (Intrinsic::ID ID = Fn->getIntrinsicID()) { + if (handleIntrinsic(ID, &Inst, Inst.arg_operands())) + return true; + } else if (!Fn->isDeclaration()) { + if (tryInterproceduralAnalysis(Fn, &Inst, Inst.arg_operands())) + return true; + } + return false; + }; + + // If we handle all targets, we are done, otherwise fall through + // to the pessimestic case + if (std::all_of(Targets.begin(), Targets.end(), TryInterprocedural)) + return; + } + + // Because the function is opaque, we need to note that anything + // could have happened to the arguments, and that the result could alias + // just about anything, too. + auto *HeapPtr = BuilderEdge::HEAP_VALUE; + for (Value *V : Inst.arg_operands()) + if (V->getType()->isPointerTy()) + Output.emplace_back(V, HeapPtr, EdgeType::AssignTo); + if (Inst.getType()->isPointerTy()) + Output.emplace_back(HeapPtr, &Inst, EdgeType::AssignTo); +} + +bool GetEdgesVisitor::handleIntrinsic( + Intrinsic::ID ID, llvm::Value *FuncValue, + const iterator_range &Args) { + + bool HasPointerArg = false; + for (auto &Arg : Args) { + if (Arg->getType()->isPointerTy()) + HasPointerArg = true; + } + + switch (ID) { + case Intrinsic::memmove: + case Intrinsic::memcpy: { + auto Iter = Args.begin(); + auto &Dest = *(*Iter++); + auto &Source = *(*Iter); + // *Dest = *Source + Graph.addEdge(Graph.findOrCreateDeref(Graph.findOrCreateNode(&Source)), + Graph.findOrCreateDeref(Graph.findOrCreateNode(&Dest)), + EdgeType::AssignTo, EdgeType::AssignFrom); + return true; + } + case Intrinsic::vacopy: { + auto Iter = Args.begin(); + auto &Dest = *(*Iter++); + auto &Source = *(*Iter); + Graph.addEdge(Graph.findOrCreateNode(&Source), + Graph.findOrCreateNode(&Dest), EdgeType::AssignTo, + EdgeType::AssignFrom); + return true; + } + case Intrinsic::dbg_value: + case Intrinsic::dbg_declare: + case Intrinsic::memset: + case Intrinsic::lifetime_start: + case Intrinsic::lifetime_end: + case Intrinsic::invariant_start: + case Intrinsic::invariant_end: + case Intrinsic::eh_typeid_for: + case Intrinsic::vaend: + case Intrinsic::vastart: + case Intrinsic::objectsize: + case Intrinsic::stackrestore: + case Intrinsic::prefetch: + case Intrinsic::x86_sse_stmxcsr: + return true; + case Intrinsic::fabs: + default: + if (HasPointerArg) { + dbgs() << "unhandled intrinsic "; + FuncValue->dump(); + } + return false; + } +} + +bool GetEdgesVisitor::tryInterproceduralAnalysis( + Function *Fn, Value *FuncValue, + const iterator_range &Args) { + + auto InfoPtr = AA.ensureCached(Fn); + if (InfoPtr == nullptr) { + DEBUG_MSG("no inline, recursive: " << Fn->getName()); + // TODO -- handle direct recursion + return false; + } + + if (Fn->isVarArg()) { + // TODO -- handle var args + DEBUG_MSG("no inline, var args: " << Fn->getName()); + return false; + } + + // Copy the "GraphToInline" from the called function + // to the caller and then assign actuals to formals + // and returned values to the return node. + + auto &CalledGraph = InfoPtr->GraphToInline; + assert(CalledGraph.VarArgs == PointerGraph::NOT_A_NODE); + if (CalledGraph.size() > InlineLimit) { + DEBUG_MSG("no inline, size: " << CalledGraph.size() << " " + << Fn->getName()); + return false; + } + + std::vector InlineNodeMap(CalledGraph.size(), + Node(PointerGraph::NOT_A_NODE)); + InlineNodeMap[CalledGraph.Heap] = Graph.Heap; + + // Map common global references to their existing nodes, if any. + for (auto Global : CalledGraph.GlobalsValues) { + auto New = Graph.findOrCreateNode(Global); + auto Old = CalledGraph.getNode(Global); + assert(Old.hasValue()); + InlineNodeMap[*Old] = New; + if (auto NewDeref = Graph.getDeref(New)) + if (auto OldDeref = CalledGraph.getDeref(*Old)) + InlineNodeMap[*OldDeref] = *NewDeref; + } + + // Create new nodes for non-globals in the inline graph. + auto InlineNodeMapIter = InlineNodeMap.begin(); + for (Node N : CalledGraph) { + auto &Image = *InlineNodeMapIter; + ++InlineNodeMapIter; + if (Image != PointerGraph::NOT_A_NODE) + continue; + const auto &Edges = CalledGraph.edges(N); + if (Edges.size() == 1 && Edges[0].Type == EdgeType::Dereference) + continue; + Image = Graph.addNode(); + } + // Create new nodes for the return nodes in the called graph. + for (Node R : CalledGraph.ReturnedNodes) { + auto &Image = InlineNodeMap[R]; + if (Image != PointerGraph::NOT_A_NODE) + continue; + Image = Graph.addNode(); + } + + // Build edges for the copy of the graph. + for (Node N : CalledGraph) { + auto NewN = InlineNodeMap[N]; + if (NewN == PointerGraph::NOT_A_NODE) + continue; + + DEBUG_MSG("inline N" << N << " -> N" << NewN); + for (auto E : CalledGraph.edges(N)) { + auto NewOther = InlineNodeMap[E.Other]; + if (NewOther == PointerGraph::NOT_A_NODE) + continue; + if (NewN == NewOther && NewN == Graph.Heap) + continue; + if (E.Type == EdgeType::Dereference) + if (auto Deref = Graph.getDeref(NewN)) { + assert(*Deref == NewOther); + continue; + } + Graph.addEdge(NewN, NewOther, E.Type); + } + } + + // Simulate assignment of actuals to formals. + auto FormalsIter = CalledGraph.FormalArguments.begin(); + for (auto &Arg : Args) { + if (FormalsIter == CalledGraph.FormalArguments.end()) + break; + + Value *ArgVal = &*Arg; + auto Formal = *FormalsIter++; + bool ActualIsPointer = ArgVal->getType()->isPointerTy(); + Node ActualNode = Graph.Heap; + if (Formal == PointerGraph::NOT_A_NODE) { + if (!ActualIsPointer) + continue; + Formal = Graph.Heap; + } else { + Formal = InlineNodeMap[Formal]; + if (Formal == PointerGraph::NOT_A_NODE) { + // A formal which is simply dereferenced but + // never assigned to any other value is ignored. + continue; + } + } + if (!ActualIsPointer) + ActualNode = Graph.Heap; + else + ActualNode = Graph.findOrCreateNode(ArgVal); + Graph.addEdge(ActualNode, Formal, EdgeType::AssignTo, EdgeType::AssignFrom); + } + + /// Simulate assignment of the return value. + Node Result = + (FuncValue->getType()->isPointerTy() ? Graph.findOrCreateNode(FuncValue) + : Graph.Heap); + for (auto R : CalledGraph.ReturnedNodes) + Graph.addEdge(InlineNodeMap[R], Result, EdgeType::AssignTo, + EdgeType::AssignFrom); + return true; +} + +/// For a given instruction, we need to know which Value* to get the +/// users of in order to build our graph. In some cases (i.e. add), +/// we simply need the Instruction*. In other cases (i.e. store), +/// finding the users of the Instruction* is useless; we need to find +/// the users of the first operand. This handles determining which +/// value to follow for us. +/// +/// Note: we *need* to keep this in sync with GetEdgesVisitor. Add +/// something to GetEdgesVisitor, add it here -- remove something from +/// GetEdgesVisitor, remove it here. +class GetTargetValueVisitor + : public InstVisitor { +public: + Value *visitInstruction(Instruction &Inst) { return &Inst; } + + Value *visitStoreInst(StoreInst &Inst) { return Inst.getPointerOperand(); } + + Value *visitAtomicCmpXchgInst(AtomicCmpXchgInst &Inst) { + return Inst.getPointerOperand(); + } + + Value *visitAtomicRMWInst(AtomicRMWInst &Inst) { + return Inst.getPointerOperand(); + } + + Value *visitInsertElementInst(InsertElementInst &Inst) { + return Inst.getOperand(0); + } + + Value *visitInsertValueInst(InsertValueInst &Inst) { + return Inst.getAggregateOperand(); + } +}; + +} // anonymous namespace + +Optional GraphBuilder::getTargetValue(Instruction *Inst) { + GetTargetValueVisitor V; + return V.visit(Inst); +} + +bool GraphBuilder::hasUsefulEdges(Instruction *Inst) { + // There are certain instructions (i.e. FenceInst, etc.) that we ignore. + bool IsNonInvokeTerminator = isa(Inst) && + !isa(Inst) && !isa(Inst); + return !isa(Inst) && !isa(Inst) && !IsNonInvokeTerminator; +} + +bool GraphBuilder::hasUsefulEdges(ConstantExpr *CE) { + // ConstantExpr doesn't have terminators, invokes, or fences, so only needs + // to check for compares. + return CE->getOpcode() != Instruction::ICmp && + CE->getOpcode() != Instruction::FCmp; +} + +// TODO: should this simply test the type of the value? We perhaps simply ignore +// non-pointer constatns. +static bool canSkipAddingToSets(Value *Val) { + // Constants can share instances, which may falsely unify multiple + // sets, e.g. in + // store i32* null, i32** %ptr1 + // store i32* null, i32** %ptr2 + // clearly ptr1 and ptr2 should not be unified into the same set, so + // we should filter out the (potentially shared) instance to + // i32* null. + if (isa(Val)) { + bool Container = isa(Val) || isa(Val) || + isa(Val); + // TODO: Because all of these things are constant, we can determine whether + // the data is *actually* mutable at graph building time. This will probably + // come for free/cheap with offset awareness. + bool CanStoreMutableData = + isa(Val) || isa(Val) || Container; + return !CanStoreMutableData; + } + + return false; +} + +void GraphBuilder::addEdgeToGraph(BuilderEdge E) { + if (E.Type == EdgeType::Reference || E.Type == EdgeType::AssignFrom) { + std::swap(E.From, E.To); + E.Type = flipLabel(E.Type); + } + // Generally we ignore assignments from constants + // to avoid tangling parts of the graph with + // values which are not pointers. + if (E.From != BuilderEdge::HEAP_VALUE && canSkipAddingToSets(E.From)) { + // Build the derference incase the source address is a global variable + // that we want to inlcude in the analysis. + if (E.Type == EdgeType::Store) + Graph.findOrCreateDeref(Graph.findOrCreateNode(E.To)); + return; + } + // There should be only one "*p" node for a given 'p' + // so rewrite p ->deref q to be p -> deref *p -> assign q. + auto From = + (E.From != BuilderEdge::HEAP_VALUE ? Graph.findOrCreateNode(E.From) + : Graph.Heap); + auto To = (E.To != BuilderEdge::HEAP_VALUE ? Graph.findOrCreateNode(E.To) + : Graph.Heap); + + if (E.Type == EdgeType::Dereference) { + // x = *p, we create the '*p' node and the assign it to the node for 'x'. + From = Graph.findOrCreateDeref(From); + E.Type = EdgeType::AssignTo; + } else if (E.Type == EdgeType::Store) { + // *p = x, we create the '*p' node and assign the value 'x' to it. + To = Graph.findOrCreateDeref(To); + E.Type = EdgeType::AssignTo; + } + + if (To != Graph.Heap || From != Graph.Heap) { + auto FlippedLabel = flipLabel(E.Type); + DEBUG_MSG("edge (" << From << "," << To << ") " << E.Type); + Graph.addEdge(From, To, E.Type, FlippedLabel); + } +} + +void GraphBuilder::constexprToEdges(ConstantExpr &CExprToCollapse, + SmallVectorImpl &Results) { + SmallVector Worklist; + Worklist.push_back(&CExprToCollapse); + + SmallVector ConstexprEdges; + SmallPtrSet Visited; + while (!Worklist.empty()) { + auto *CExpr = Worklist.pop_back_val(); + + if (!hasUsefulEdges(CExpr)) + continue; + + ConstexprEdges.clear(); + argsToEdges(Analysis, CExpr, ConstexprEdges); + for (auto &Edge : ConstexprEdges) { + if (Edge.From != BuilderEdge::HEAP_VALUE) + if (auto *Nested = dyn_cast(Edge.From)) + if (Visited.insert(Nested).second) + Worklist.push_back(Nested); + + if (Edge.To != BuilderEdge::HEAP_VALUE) + if (auto *Nested = dyn_cast(Edge.To)) + if (Visited.insert(Nested).second) + Worklist.push_back(Nested); + } + + Results.append(ConstexprEdges.begin(), ConstexprEdges.end()); + } +} + +void GraphBuilder::convertFormalArgumentsToHeap() { + + // To model an arbitrary call, we assume formal paramters are + // initialized from heap with special handling of var-args. + + auto FormalP = Graph.FormalArguments.begin(); + for (auto &Arg : Fn->args()) { + auto ArgNode = *FormalP++; + if (ArgNode == PointerGraph::NOT_A_NODE) + continue; + if (!Arg.hasNoAliasAttr()) { + Graph.addEdgeAndInverse(Graph.Heap, ArgNode, EdgeType::AssignTo); + continue; + } + // Here we model no-alias as pointing to a unique + // abstract location which is then tangled with the heap + // this allows the pointer value to be stored in a local + // temporary and read out of that temporary without losing + // the no-alias property. On the other hand, it allows the value + // to be stored in a local variable and then reused and it is not + // clear of the value retains the no-alias property once it has + // been filtered through another programmer-visible name. + auto Deref = Graph.findOrCreateDeref(ArgNode); + Graph.addEdgeAndInverse(Deref, Graph.Heap, EdgeType::AssignTo); + Graph.addEdgeAndInverse(Graph.Heap, Deref, EdgeType::AssignTo); + } +} + +//===----------------------------------------------------------------------===// +// +// +// Code related to compressing an abstract pointer operation graph +// +// +//===----------------------------------------------------------------------===// +namespace { +template +void transform_vector(const T1 &Input, T2 &Output, UnaryOp Op) { + std::transform(Input.begin(), Input.end(), std::back_inserter(Output), Op); +} +} + +PointerGraph PointerGraph::compress(bool TrimForInlining) { + Combiner Combiner(*this); + // Determine the equivalence classes. + Combiner.doCombiningForSize(TrimForInlining); + + PointerGraph Compressed; + Compressed.createHeap(); + assert(Combiner.getIndex(Heap) == Compressed.Heap); + // Add a node for each non-heap equivalence class. + for (unsigned i = 1; i < Combiner.getNumClasses(); i++) + Compressed.addNode(); + + DEBUG_MSG("compressed size = " << Compressed.size()); + // Build edges between compressed nodes. + for (auto I : *this) { + auto NewI = Combiner.getIndex(I); + if (NewI == PointerGraph::NOT_A_NODE) + continue; + + DEBUG_MSG("compress N" << I << " -> N" << NewI); + for (auto E : edges(I)) { + auto NewOther = Combiner.getIndex(E.Other); + if (NewI == NewOther || NewOther == PointerGraph::NOT_A_NODE) + continue; + if (!Compressed.hasEdge(NewI, NewOther, E.Type)) + Compressed.addEdge(NewI, NewOther, E.Type); + } + } + + // Map an existing node to its image. + auto NewNode = [&Combiner](Node N) { + if (N == PointerGraph::NOT_A_NODE) + return N; + return static_cast(Combiner.getIndex(N)); + }; + // Build the list of node references in the compressed graph. + transform_vector(FormalArguments, Compressed.FormalArguments, NewNode); + transform_vector(ReturnedNodes, Compressed.ReturnedNodes, NewNode); + + // Bbuild the output Map of IR nodes to graph nodes. + for (auto Pair : Map) { + assert(inbounds(Pair.second)); + Pair.second = static_cast(Combiner.getIndex(Pair.second)); + if (Pair.second != NOT_A_NODE) { + assert(Compressed.inbounds(Pair.second)); + Compressed.Map.insert(Pair); + } + } + return Compressed; +} + +std::unique_ptr +CFLODAAResult::buildSetsFrom(Function *Fn) { + GraphBuilder Builder(Fn, *this); + Builder.buildGraphAndEquivalences(); +#ifndef NDEBUG + if (DebugDump) { + Builder.Graph.dump(*Fn, &Builder.AliasEquivClass, &Builder.getCombiner(), + "-cmp"); + Builder.getGraphToInline().dump(*Fn, nullptr, nullptr, "-inline"); + } +#endif + auto Ptr = make_unique(&Builder); +#ifndef NDEBUG + Ptr->FunctionName = Fn->getName(); +#endif + return Ptr; +} + +void Combiner::doCombiningForEquivClasses() { + initialize(); + + // Treat all nodes as live. + for (auto &I : NodeInfo) + I.IsLive = true; + + // Exhaustively combine along AssignTo edges. + for (Node I : G) { + Node Deref = NodeInfo[I].Deref; + for (auto E : G.edges(I)) { + if (E.Type == EdgeType::AssignTo) { + combine(I, E.Other); + } else if (E.Type == EdgeType::Dereference) { + // Each class has a unique dereference and we combine nodes + // to preserve this. + if (E.Other != Deref) + combine(E.Other, Deref); + } + } + } + numberRoots(); +} + +void Combiner::doCombiningForSize(bool TrimForInlining) { + DEBUG_MSG("do combining " << TrimForInlining); + initialize(); + trimDead(TrimForInlining); + + // Find nodes which are statically known to be aliases to the Heap node + // and combine them with the heap. + DEBUG_MSG("walk heap"); + walkHeap(); + + // Look for nodes which are simply copies of some other node and combine + // them with that node. + DEBUG_MSG("walk assign trees"); + walkAssignTrees(); + + numberRoots(); +} + +void Combiner::walkHeap() { + + // Find all nodes which are memory aliases of the heap + // and all nodes which are reachable from those nodes + // Any node reachable along a path + // DA = (AssignTo* Deref) + // Starting at a node already in the heap, or, if COMPRESS_HEAP_ALIASES, + // along a path: + // DF = (AssignFrom+ AssigntTo* Deref) + + // We build the maximal set H which is initialized + // to the heap node and is closed in that + // Y \in H if there is X \in H such that DA(X,Y) + // and + // Y \in H if there exists X \in H and DF(X,Y) + + // We have the following sets associated with + // a node which are incrementally explore by associating state bits + // with a node: + // DA_To(X) ==> Y in H, (AssignTo*)(Y,X) + // when we find Z such that there is Y \in DA_To and Deref(Y,Z) + // then we add Z to H. + + // Similarly, when COMPRESS_HEAP_ALIASES + // DF_From(X) ==> Y \in H, (AssignFrom*)(Y,X) + // DF_To(X) ==> Y \in DF_From, (AssignTo*)(Y,X) + // when we find Z such that there is Y \in DF_To and Deref(Y,Z) + // then we add Z to H + + // We also look for nodes X which are part of assignment + // cycles: DA_To(x) & DF_From(X) and force those nodes into the heap. + + // Note: the combining done by DF is imprecise because + // it combines nodes which are not aliases making the + // relation more transitive, however perhaps we can + // precompue AliasMem for heap nodes ? + + enum HeapStates { + DF_From = 1, + DF_To = 2, + DA_To = 4, + D_Heap = 16, + D_OnQueue = 32, + }; + + std::vector State(G.size(), 0); + std::vector WorkList; + WorkList.reserve(G.size()); + +#ifndef NDEBUG + auto dump = [&State](Node N) { + dbgs() << "N" << N; + auto S = State[N]; + if (S & D_Heap) + dbgs() << " Heap"; + if (S & DF_From) + dbgs() << " from"; + if (S & DA_To) + dbgs() << " a_to"; + if (S & D_OnQueue) + dbgs() << " onqueue "; + if (S & ~(D_Heap | DF_From | DF_To | DA_To | D_OnQueue)) + dbgs() << " invalid"; + dbgs() << "\n"; + }; +#endif + + // If Src is any of WhenState, add ToState to Dest + // also add Dest to queue if it changes. + auto Push = [&State, &WorkList](unsigned WhenState, Node Src, + unsigned ToState, Node Dest) { + if (State[Src] & WhenState) { + auto &DestState = State[Dest]; + if ((DestState & ToState) != ToState) { + DestState |= ToState; + if (!(DestState & D_OnQueue)) { + DestState |= D_OnQueue; + WorkList.push_back(Dest); + } + } + } + }; + + State[G.Heap] = D_Heap | D_OnQueue; + WorkList.push_back(G.Heap); + + while (!WorkList.empty()) { + auto Current = WorkList.back(); + DEBUG(dump(Current)); + WorkList.pop_back(); + auto &CurrentState = State[Current]; + CurrentState &= ~D_OnQueue; + + // Cycles of assignments involving the heap are collapsed + unsigned Cycle = DA_To | DF_From; + if ((CurrentState & Cycle) == Cycle) + CurrentState |= D_Heap; + + if (CurrentState & D_Heap) + combine(G.Heap, Current); + + for (auto E : G.edges(Current)) { + if (!NodeInfo[E.Other].IsLive) + continue; + + switch (E.Type) { + case EdgeType::Dereference: + Push(DF_From | DA_To | D_Heap, Current, D_Heap, E.Other); +#if COMPRESS_HEAP_ALIASES + Push(DF_To, Current, D_Heap, E.Other); +#endif + break; + case EdgeType::AssignTo: + Push(DA_To | D_Heap, Current, DA_To, E.Other); + if (E.Other == G.Heap) + Push(DA_To, Current, D_Heap, Current); +#if COMPRESS_HEAP_ALIASES + Push(DF_From | DF_To, Current, DF_To, E.Other); +#endif + break; + case EdgeType::AssignFrom: + Push(DF_From | D_Heap, Current, DF_From, E.Other); + break; + default: + break; + } + } + } + + DEBUG({ + State[G.Heap] &= ~D_OnQueue; + for (size_t N = 0; N < G.size(); N++) { + auto S = State[N]; + if (S == 0) + continue; + dump(N); + assert(!(S & D_OnQueue) && "Unexpected elemnt should have been on queue"); + } + }); +} + +void Combiner::trimDead(bool TrimForInlining) { + + // We treat a node as "dead" if it is not reachable from a formal parameter + // or a return point except on paths which pass through the heap. If not + // inlining, then nodes reachable from the IR are also live. If inlining, + // globals are kept live. + + NodeInfo[G.Heap].IsLive = true; + std::vector WorkList; + WorkList.reserve(G.size()); + auto MarkLive = [this, &WorkList](Node N) { + assert(N < G.size()); + auto &IsLive = NodeInfo[N].IsLive; + if (!IsLive) { + IsLive = true; + WorkList.push_back(N); + } + }; + + for (auto N : G.FormalArguments) + if (N != PointerGraph::NOT_A_NODE) + MarkLive(N); + for (auto N : G.ReturnedNodes) + MarkLive(N); + + if (!TrimForInlining) { + // Mark Live anything reachable from a Value* + for (const auto &Pair : G.Map) + MarkLive(Pair.second); + } else { + // Retuan global variables even when reducing to just formals + for (auto GV : G.GlobalsValues) + MarkLive(G.Map.lookup(GV)); + } + + // Every node connected to a live node is also live. + while (!WorkList.empty()) { + auto Current = WorkList.back(); + WorkList.pop_back(); + for (auto E : G.edges(Current)) + MarkLive(E.Other); + } + DEBUG({ + dbgs() << "Dead nodes:"; + for (size_t N = 0; N < G.size(); ++N) + if (!NodeInfo[N].IsLive) + dbgs() << " " << N; + dbgs() << '\n'; + }); +} + +Node Combiner::uniqueSource(Node N) { + Node C = getComponent(N); + if (C == 0) + // Don't pull an assignment into the heap + return PointerGraph::NOT_A_NODE; + + // Verify input edges are just assignments from a + // singe equivalence class source. + Node Src = PointerGraph::NOT_A_NODE; + for (auto E : G.edges(N)) { + Node ESrc = getComponent(E.Other); + if (ESrc == C) + continue; + + switch (E.Type) { + case EdgeType::AssignFrom: + if (Src == PointerGraph::NOT_A_NODE) + Src = ESrc; + else if (Src != ESrc) + return MULTIPLE_SOURCES; + break; + case EdgeType::AssignTo: + case EdgeType::Dereference: + break; + case EdgeType::Reference: + return MULTIPLE_SOURCES; + default: + llvm_unreachable_internal(); + } + } + return Src; +} + +void Combiner::walkAssignTrees() { + + // Find nodes which have a unique assignment source and combine them with + // that node, repeat until convergence. + bool Changed; + do { + for (auto &Info : NodeInfo) + Info.Src = PointerGraph::NOT_A_NODE; + for (Node N = 1; N < G.size(); ++N) { + auto C = getComponent(N); + if (C == 0) // Heap + continue; + auto Src = uniqueSource(N); + if (Src == PointerGraph::NOT_A_NODE) + continue; + DEBUG_MSG("assign N" << N << " =C" << C << " Src=C" << Src); + auto &CSrc = NodeInfo[C].Src; + if (CSrc == PointerGraph::NOT_A_NODE) + CSrc = Src; + else if (CSrc != Src) + CSrc = MULTIPLE_SOURCES; + } + Changed = false; + for (Node N1 = 1; N1 < G.size(); ++N1) { + auto &Info = NodeInfo[N1]; + if (Info.isRoot() && Info.Src != PointerGraph::NOT_A_NODE && + Info.Src != MULTIPLE_SOURCES) { + auto C = getComponent(N1); + DEBUG_MSG("assign final N" << N1 << " =C" << C << " Src=C" << Info.Src); + if (combine(C, Info.Src)) + Changed = true; + } + } + } while (Changed); +} + +#ifndef NDEBUG +// Verify certain structural properties hold for the specified graph. +void PointerGraph::check(const char *label, const Function &Fn) const { + bool failed = false; + for (Node N : *this) { + // At most one Derference edge. + unsigned DerefCount = 0; + for (auto E : edges(N)) { + if (E.Type == EdgeType::Dereference) + DerefCount += 1; + if (!inbounds(E.Other)) { + dbgs() << "bad edge reference from " << N << " to " << E.Other << '\n'; + assert(0 && "Bad graph"); + } + // Verify that the graph is bi-directional. + auto Flipped = flipLabel(E.Type); + auto &OtherEdges = edges(E.Other); + auto Count = + std::count_if(OtherEdges.begin(), OtherEdges.end(), + [Flipped, N](GraphT::Edge Edge) { + return Edge.Other == N && Edge.Type == Flipped; + }); + if (!Count) { + dbgs() << label << ": Missing from node N" << E.Other << " to N" << N + << " kind " << Flipped << '\n'; + failed = true; + } + } + if (DerefCount > 1) { + dbgs() << label << ": Multiple derefence edges leaving N" << N << '\n'; + failed = true; + } + } + if (failed) { + dump(Fn, nullptr, nullptr, "-failed"); + assert(0 && "Failed checkgraph"); + } +} +#endif + +void CFLODAAResult::scan(Function *Fn) { + DEBUG(ShowStatus = true); + STATUS_MSG("scanning " << Fn->getName()); + auto InsertPair = Cache.insert(std::make_pair(Fn, nullptr)); + (void)InsertPair; + assert(InsertPair.second && + "Trying to scan a function that has already been cached"); + +#ifndef NDEBUG + auto Save = FunctionNumber; + FunctionNumber = NextFunctionNumber++; + DebugNumber[Fn] = FunctionNumber; + auto SaveFlag = llvm::DebugFlag; + setDebugFlag(); +#endif + auto Info = buildSetsFrom(Fn); +#ifndef NDEBUG + FunctionNumber = Save; + llvm::DebugFlag = SaveFlag; +#endif + Cache[Fn] = std::move(Info); +} + +void CFLODAAResult::rescan(Function *Fn) { + if (ShowStatus) + dbgs() << "Rescanning " << Fn->getName() << '\n'; +} + +void CFLODAAResult::evict(Function *Fn) { Cache.erase(Fn); } + +// Ensures that the given function is available in the cache. +// Returns the appropriate entry from the cache. +CFLODAAResult::FunctionInfo *CFLODAAResult::ensureCached(Function *Fn) { + auto Iter = Cache.find(Fn); + if (Iter == Cache.end()) { + scan(Fn); + Iter = Cache.find(Fn); + assert(Iter != Cache.end()); + assert(Iter->second); + } + return Iter->second.get(); +} + +void CFLODAAResult::setActiveFunction(Function *Fn) { + if (ActiveFunction && ActiveFunction != Fn) { + STATUS_MSG("Analyzing " << Fn->getName()); + } + ActiveFunction = Fn; +} + +Optional CFLODAAResult::getCached(Function *Fn) { + auto Iter = Cache.find(Fn); + if (Iter == Cache.end()) + return None; + return Iter->second.get(); +} + +// Try to go from a Value* to a containing Function*. +static Function *parentFunctionOfValue(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; +} + +AliasResult CFLODAAResult::query(const MemoryLocation &LocA, + const MemoryLocation &LocB) { + QueryCalls += 1; + + auto *ValA = const_cast(LocA.Ptr); + auto *ValB = const_cast(LocB.Ptr); + + auto MaybeFnA = parentFunctionOfValue(ValA); + auto MaybeFnB = parentFunctionOfValue(ValB); + if (!MaybeFnA && !MaybeFnB) { + // The only times this is known to happen are when globals + InlineAsm + // are involved + DEBUG( + dbgs() << "CFLODAA: could not extract parent function information.\n"); + return MayAlias; + } + + Function *Fn = nullptr; + if (MaybeFnA) { + Fn = MaybeFnA; + assert((!MaybeFnB || MaybeFnB == MaybeFnA) && + "Interprocedural queries not supported"); + } else { + Fn = MaybeFnB; + } + + setActiveFunction(Fn); // Diagnostic only + + AliasResult Result = query(Fn, ValA, ValB); +#if SEARCH_FULL_GRAPH + // Search on the full graph if it is available but limited total work... + if (FullGraphSearch && FullSearchOps < 10000000) { + auto &Info = *ensureCached(Fn); + bool FullResult = Info.FullInfo.mayAlias(ValA, ValB); + if (Result == MayAlias) { + if (!FullResult) + FullNoAlias += 1; + } else if (FullResult) { + FunctionNumber = DebugNumber[Fn]; + errs() << "Failed CFL Verification of Compressed Info\n"; + errs() << " Full=" << (FullResult ? "May Alias" : "No Alias") + << '\n'; + errs() << " Compressed=" + << (Result == MayAlias ? "May Alias" : "No Alias") << '\n'; + auto List = [Info](Value *V) { + if (auto NumA = Info.Graph.getNode(V)) + errs() << " C" << *NumA; + if (auto NumAF = Info.FullInfo.Graph.getNode(V)) + errs() << " F" << *NumAF; + errs() << ": "; + V->print(errs()); + errs() << '\n'; + }; + List(ValA); + List(ValB); + bool PrintValues = false; + Info.Graph.dump(*Fn, &Info.AliasEquivClass, nullptr, "-v", PrintValues, + *Info.Graph.getNode(ValA), *Info.Graph.getNode(ValB)); + Info.FullInfo.Graph.dump(*Fn, nullptr, nullptr, "-v-full", PrintValues, + *Info.FullInfo.Graph.getNode(ValA), + *Info.FullInfo.Graph.getNode(ValB)); + dumpCFG(*Fn); + assert(Result == FullResult && + "Failed CFL verification of compressed info"); + } + } +#endif + return Result; +} + +AliasResult CFLODAAResult::query(Function *Fn, Value *ValA, Value *ValB) { + assert(Fn != nullptr); + auto &Info = *ensureCached(Fn); + +#ifndef NDEBUG + setDebugFlag(Fn); + Info.QueryCount += 1; +#endif + + // The fast path ... we can prove without searching that the + // pointers refere to distinct memory. + if (Info.distinctAliasEquivalenceClassses(ValA, ValB)) { + FastkNoAlias += 1; + return NoAlias; + } + +#if ENABLE_EXPERIMENTS + auto NodeA = Info.Graph.getNode(ValA); + if (!NodeA.hasValue()) { + NoNodeForValue += 1; + return MayAlias; + } + auto NodeB = Info.Graph.getNode(ValB); + if (!NodeB.hasValue()) { + NoNodeForValue += 1; + return MayAlias; + } + if (*NodeA == *NodeB) + return MayAlias; + + // Check for the simple graph heuristic + if (Info.SimpleGraph) { + if (Info.Graph.simpleMayAlias(*NodeA, *NodeB)) + return MayAlias; + SimpleNoAlias += 1; + return NoAlias; + } + + // Do the path-search on the graph looking for a path which + // establishes an may-alias + if (Info.mayAlias(ValA, ValB)) { + Info.MayAliasCount += 1; + return MayAlias; + } + + // No such path, no alias. + SlowNoAlias += 1; + return NoAlias; +#else + return MayAlias; +#endif +} + +#if ENABLE_EXPERIMENTS +bool PointerGraph::simpleMayAlias(Node A, Node B) { + Node NonHeap; + if (A != Heap) { + if (B != Heap) { + return false; + } + NonHeap = A; + } else + NonHeap = B; + return hasEdge(NonHeap, Heap, EdgeType::AssignTo); +} +#endif + +//===----------------------------------------------------------------------===// +// +// +// Code related to searching a PointerGraph for an alias inducing path. +// +// +//===----------------------------------------------------------------------===// +#if ENABLE_EXPERIMENTS +namespace { +/// States which summarize path to a given node. +enum class State { + /// Path via only AssignFrom. + AssignFromOnlyPath = 1, + /// Path via only AssignFrom, after one memory alias. + AssignFromOnlyPathAfterMemAlias = 2, + /// A path which ends with AssignTo edges. + AssignToPath = 3, + /// A path which ends with AssignTo edges, after one memory alias + AssignToPathAfterMemAlias = 4 +}; + +#if DEBUG_SEARCH +const char *name(State s) { + switch (s) { + case State::AssignToPath: + return "AssignToPath"; + case State::AssignFromOnlyPath: + return "AssignFromOnly"; + case State::AssignToPathAfterMemAlias: + return "AssignTo,After"; + case State::AssignFromOnlyPathAfterMemAlias: + return "AssignFrom,After"; + } + llvm_unreachable("unkown State"); +} +#endif + +/// This class manages the queue of to-be-explored-states which is basically +/// the collection of states augmented with a set which notes which states +/// have already been seen. +class StateQueue { + typedef GraphT::Node Node; + + /// The to-be-explored elements. + struct StateQueueElement { + /// The current node. + Node N; + /// The target 'end' node of the path + Node S; + /// A characterization of the path so far to 'N' + State C; + /// A level which relates to the number of Reference/Dereference + /// nodes traversed as we explore the exists of memory aliases. This is + /// used as a priority to search paths without aliases before looking for + /// more aliases. + int Level; + bool operator==(const StateQueueElement &E) const { + return E.N == N && E.S == S && E.C == C; + } + bool operator<(const StateQueueElement &E) const { return Level < E.Level; } + }; + struct Hash { + size_t operator()(const StateQueueElement &E) const { + size_t Key = E.N << 17 | E.S << 2 | unsigned(E.C); + return std::hash()(Key); + } + }; + + std::priority_queue WorkList; + std::unordered_set Seen; + +public: + bool push(Node N, Node S, State C, int Level) { + StateQueueElement E{N, S, C, Level}; + if (!Seen.insert(E).second) + return false; +#if DEBUG_SEARCH + DEBUG_MSG(" push " << N << ' ' << S << ' ' << name(C)); +#endif + WorkList.push(E); + return true; + } + void pop(Node *N, Node *S, State *C, int *Level) { + StateQueueElement E = WorkList.top(); + *N = E.N; + *S = E.S; + *C = E.C; + *Level = E.Level; +#if DEBUG_SEARCH + DEBUG_MSG("pop " << E.N << ' ' << E.S << ' ' << name(E.C)); +#endif + WorkList.pop(); + } + bool empty() const { return WorkList.empty(); } +}; + +/// This class encapsulate the logic of exploring the pointer graph +/// for the existence of paths whose labels satisfy the CFL given by +/// the following rules +/// V = (AssignFrom M?)* M? (AssignTo M?)* +/// M = Reference V Derefernce +/// Note that we remember nodes X,Y connected by a path M in the +/// the set AliasMem and this set can be reused across different +/// invocations. +/// +/// For the relations above we denote V(x,y) to indicate that there is a path +/// from x to y whose labels are language defined by V. Similarly for M. +/// +/// Intuitively, two pointers p1 and p2 are aliased they refer +/// to the same memorhy location. This is observed as path from some +/// address (global variable or malloc call) which reaches the nodes +/// corresponding to p1 and p2 through assignment paths. The path +/// V then walks backwards from p1 to this source address and forward +/// to node p2. +/// +/// This basic idea is then extend bu finding abstract "memory" locations +/// which might be the same because there addresses have a common value. +/// Since the analysis is flow insensitive, a path of assignments may enter +/// one memory node and then continue from any aliased location. This is the +/// role of the M relation above. +/// +/// Given two values p1, p2 with corresponding nodes n1, n2, we attempt to +/// prove that V(n1,n2) exists by exhaustively search for such a path. We record +/// triples of the form (n1,s1,c) which capture the existence of a path +/// starting at "s1" which reaches "n1" where "c" indicates where in the +/// expansion of V this path corresponds to. To illustrate: +/// +/// V = (AssignFrom M? )* M? (AssignTo M? )* +/// 1 2 3 4 +/// Which are explained as +/// 1 -- AssignFromOnlyPath --- we have only seeen AssignFrom operations +/// and maybe some M transitions, and an M transition may be next +/// 2 -- AssignFromOnlyPathAfterMemAlias -- we have only seen AssignFrom +/// operations and have just made an M transition +/// 3 -- AssignToPath -- we have seen at least one AssignTo operations +/// and may have a M transition +/// 4 -- AssignToPathAfterMemAlias -- we have seen at least one AssignTo +/// operation and just had an M transition. +/// We process every such triple to create new triples based on the edges +/// incident to the node. If we process a tuple of the form (n2,n1,*) then +/// we have establish the basic question and can report p1 and p2 are aliased. +/// If we exhaust the search, we have determined they are not aliased. +/// +/// To accomplish the M transition, whenever we process a node n1 in +/// states AssignFromOnlyPath (1) or AssignToPath (2), and the node n1 has +/// a reference source, n2 (i.e., there is an edge (n1,n2, Reference) and +/// by construction also an edge (n2,n1,Dereference)). Then we include the sate +/// (n2,n2, AssignFromOnlyPath) which will identify nodes "m2" where V(n2,m2) +/// When ever we process a state (n2,m2,*), we look for nodes n3 and m3 which +/// are dereferences of n2 and m2 respectively. We can add (n3,m3) to M. +/// When we add a pair to M, we can examine the states which are known n3, and +/// use that to add new states for m3. +/// +/// When an alias does exist, the order in which we visit nodes effects the +/// number of noes visited. This initial implementation makes no attempt to +/// exploit this fact. +/// +/// TODO -- is the definition of V actually correct? If so, how is +/// the middle M? transition handled? +class Searcher { + + /// The alias graph we are searching. + AliasInfo &Info; + + /// These nodes are the original question is (N0,S0) \in V + /// We will start teh search form N0 looking for S0. + Node N0, S0; + + /// The queue of (n,s,c) triples still to be processed. + StateQueue W; + + /// This map implements the projection from all visited triples + /// to those with a particular first node. + typedef std::pair ReachElt; + DenseMap> Reach; + + /// Add (N,S,C) to the set of triples to be explored. + void propagate(Node N, Node S, State C, int Level) { + assert(Info.Graph.inbounds(N)); + if (W.push(N, S, C, Level)) + // First time it has been seen + Reach[N].emplace_back(S, C); + }; + + /// This tracks Derefence nodes we have explored. If we fail to find + /// a path, then the aliases for these nodes are fully known and in future + /// search calls we don't need to look for more memory aliases. + SmallVector DerefencesChecked; + +public: + Searcher(AliasInfo &Info) : Info(Info) {} + void init(Node N, Node S) { + N0 = N; + S0 = S; + + // There is a bug in the paper where they fail to + // initialize the Reach[] set with the starting + // information. This is fixed by calling propagate instead + // of push here to initialize. This bug manifests on a path + // which begins with transition to a memory alias. + propagate(N, N, State::AssignFromOnlyPath, 0); + } + + /// Process one node on the queue and indicate whether + /// we have learned anything. This interface allows the client + /// to control/limit/interleave the search. This structure is intended + /// to at some point allow searches to be interleaved but that is not + /// currently done. + enum class SearchStatus { CONTINUE, NO_ALIAS, MAY_ALIAS }; + SearchStatus advance(); +}; +} + +Searcher::SearchStatus Searcher::advance() { + if (W.empty()) + return SearchStatus::NO_ALIAS; + + SearchOps += 1; + Node N, S; + State C; + int Level; + W.pop(&N, &S, &C, &Level); + + // Have we reached a path to the + // original end node? + if (N == S0 && S == N0) { + // We are not done processing here so clear the status flag since + // we don't know all of the aliases for these Derference nodes. + for (auto D : DerefencesChecked) + Info.AliasesKnown[D] = false; + return SearchStatus::MAY_ALIAS; + } + + // See if we have discovered a new element in the M releation + if (auto N1 = Info.Graph.getDeref(N)) + if (auto S1 = Info.Graph.getDeref(S)) + if (*N1 != *S1 && Info.AliasMem[*S1].insert(*N1).second) { +// Discovered a memory alias +#if DEBUG_SEARCH + DEBUG_MSG(" alias " << *N1 << " and " << *S1); +#endif + // Continue value search associated with S1 from new alias N1 + SmallVector ToPropagate; + for (const auto &R : Reach[*S1]) { + if (R.second == State::AssignFromOnlyPath) + ToPropagate.emplace_back(R.first, + State::AssignFromOnlyPathAfterMemAlias); + else if (R.second == State::AssignToPath) + ToPropagate.emplace_back(R.first, State::AssignToPathAfterMemAlias); + } + for (const auto &R : ToPropagate) + propagate(*N1, R.first, R.second, Level + 1); + } + + // Propagate state to adjacent nodes + switch (C) { + case State::AssignFromOnlyPath: + case State::AssignFromOnlyPathAfterMemAlias: { + for (const auto &E : Info.Graph.edges(N)) { + if (E.Type == EdgeType::AssignFrom) + propagate(E.Other, S, State::AssignFromOnlyPath, Level); + else if (E.Type == EdgeType::AssignTo) + propagate(E.Other, S, State::AssignToPath, Level); + } + if (C == State::AssignFromOnlyPath) { + auto Iter = Info.AliasMem.find(N); + if (Iter != Info.AliasMem.end()) + for (auto M : Iter->second) + propagate(M, S, State::AssignFromOnlyPathAfterMemAlias, Level); + } + break; + } + case State::AssignToPath: + case State::AssignToPathAfterMemAlias: { + for (const auto &E : Info.Graph.edges(N)) + if (E.Type == EdgeType::AssignTo) + propagate(E.Other, S, State::AssignToPath, Level); + if (C == State::AssignToPath) { + auto Iter = Info.AliasMem.find(N); + if (Iter != Info.AliasMem.end()) + for (auto M : Iter->second) + propagate(M, S, State::AssignToPathAfterMemAlias, Level); + } + break; + } + } + + // Jump to an alias of N if its aliases are not known and it + // has an Reference edge (which identifies an "address"). + if (C == State::AssignFromOnlyPath || C == State::AssignToPath) + for (auto E : Info.Graph.edges(N)) + if (E.Type == EdgeType::Reference && !Info.AliasesKnown[E.Other]) { + // Remember that we have explored alias for this node. + Info.AliasesKnown[E.Other] = true; + DerefencesChecked.push_back(E.Other); + // Exploring aliases is a lower priorty than continunie to search + // for value paths at this level + int Priority = Level - 1; + propagate(E.Other, E.Other, State::AssignFromOnlyPath, Priority); + } + + return SearchStatus::CONTINUE; +} + +// p1 and p2 are two address associated with memory locations +// we try to prove they may not be the same location +bool AliasInfo::mayAlias(Value *p1, Value *p2) { + if (DisableSearch) + return true; + if (p1 == p2) + return true; + + // The alias information degrades as transformations are performed + // on the underly IR and so here we may conservative assumptions. + auto N0 = Graph.getNode(p1); + if (!N0.hasValue()) + return true; + auto S0 = Graph.getNode(p2); + if (!S0.hasValue()) + return true; + if (*N0 == *S0) + return true; + assert(Graph.inbounds(*N0)); + assert(Graph.inbounds(*S0)); + +#if DEBUG_SEARCH + DEBUG_INST(DebugLabel << "p1 = " << *N0 << ": ", (*p1)); + DEBUG_INST(DebugLabel << "p2 = " << *S0 << ": ", (*p2)); +#endif + +#ifdef LLVM_ENABLE_STATS + auto CountInit = SearchOps.getValue(); +#endif + Searcher Search(*this); + Search.init(*N0, *S0); + + Searcher::SearchStatus Status; + do { + Status = Search.advance(); + } while (Status == Searcher::SearchStatus::CONTINUE); + +#ifdef LLVM_ENABLE_STATS + auto NumSteps = SearchOps - CountInit; + SearchCount += NumSteps; + if (*DebugLabel) { + SearchOps -= NumSteps; + FullSearchOps += NumSteps; + } +#endif + + if (Status == Searcher::SearchStatus::NO_ALIAS) { +#if DEBUG_SEARCH + DEBUG_MSG("CFL no alias"); +#endif + return false; + } + return true; +} +#endif + +CFLODAAResult CFLODAA::run(Function &F, AnalysisManager *AM) { + return CFLODAAResult(); +} + +CFLODAAResult::CFLODAAResult() : AAResultBase() {} +CFLODAAResult::CFLODAAResult(CFLODAAResult &&Arg) + : AAResultBase(std::move(Arg)) {} +CFLODAAResult::~CFLODAAResult() { + if (!FunctionReporting) { + return; + } +#ifndef NDEBUG + for (auto &P : Cache) + if (P.second) + P.second->report(P.first); +#endif +} + +#ifndef NDEBUG +void CFLODAAResult::FunctionInfo::report(Function *F) { +#if ENABLE_EXPERIMENTS + dbgs() << format("%5d", QueryCount) + << format(" %5.1f%% ", 100 * MayAliasCount / double(QueryCount)) + << (SimpleGraph ? "simple" : " ") << " steps " + << format(" %6d ", SearchCount); + dbgs() << " CFL "; + dbgs() << DebugNumber[F]; + dbgs() << ' ' << FunctionName << '\n'; +#endif +} +#endif + +char CFLODAA::PassID; +char CFLODAAWrapperPass::ID = 0; + +INITIALIZE_PASS(CFLODAAWrapperPass, "cfl-od-aa", + "CFL-Based On Demand Alias Analysis", false, true) + +ImmutablePass *llvm::createCFLOnDemandAAWrapperPass() { + return new CFLODAAWrapperPass(); +} + +CFLODAAWrapperPass::CFLODAAWrapperPass() : ImmutablePass(ID) { + initializeCFLODAAWrapperPassPass(*PassRegistry::getPassRegistry()); +} + +bool CFLODAAWrapperPass::doInitialization(Module &M) { + Result.reset(new CFLODAAResult()); + return false; +} + +bool CFLODAAWrapperPass::doFinalization(Module &M) { + Result.reset(); + return false; +} + +void CFLODAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesAll(); +} + +namespace { +struct CFLODAARebuildPass : public FunctionPass { + static char ID; + CFLODAARebuildPass() : FunctionPass(ID) { + llvm::initializeCFLODAARebuildPassPass(*PassRegistry::getPassRegistry()); + } + bool runOnFunction(Function &F) override { + if (skipFunction(F)) + return false; + auto R = &getAnalysis().getResult(); + R->rescan(&F); + return true; + } + + void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.addRequired(); + AU.setPreservesAll(); + } +}; +} +char CFLODAARebuildPass::ID = 0; +INITIALIZE_PASS_BEGIN(CFLODAARebuildPass, "cfl-rebuild", + "Rebuild CFL AA information", false, false) +INITIALIZE_PASS_DEPENDENCY(CFLODAAWrapperPass) +INITIALIZE_PASS_END(CFLODAARebuildPass, "cfl-rebuild", + "Rebuild CFL AA information", false, false) +FunctionPass *llvm::createCFLOnDemandAARebuildPass() { + return new CFLODAARebuildPass(); +} +#ifndef NDEBUG +namespace { + +/// This class finds connected components of the graph with +/// the heap node logically removed. +class SplitHeapComponents { + const PointerGraph &G; + /// All nodes in a connected component have + /// the same non-zero value under this map. This + /// is also used as "visited" flag for graph traversal. + std::vector Component; + SmallVector Worklist; + + void collectComponent(Node N, unsigned Number) { + Worklist.push_back(N); + while(!Worklist.empty()) { + N = Worklist.pop_back_val(); + Component[N] = Number; + for (auto E : G.edges(N)) + if (!Component[E.Other]) + Worklist.push_back(E.Other); + } + } + +public: + SplitHeapComponents(const PointerGraph &G) : G(G) {} + + unsigned doLabeling() { + Component.resize(G.size(), 0); + + // Force the heap to be in its own compmonent + unsigned NumComponent = 1; + Component[G.Heap] = NumComponent; + for (Node N = 1; N < G.size(); N++) { + if (Component[N] == 0) { + ++NumComponent; + collectComponent(N, NumComponent); + } + } + return NumComponent; + } + unsigned getComponent(Node N) const { return Component[N]; } +}; + +// Generate a ".dot" file for the graph for visualization. +// Node labels will include equivalence class information when its available. +void PointerGraph::dump(const Function &F, + const AliasEquivClassMap *AliasEquivClass, + const Combiner *DoCombining, const char *label, + bool PrintValues, Node ONLY_A, Node ONLY_B) const { + + std::vector NodeToValue(size()); + for (const auto &P : Map) { + assert(inbounds(P.second)); + NodeToValue[P.second] = P.first; + } + + std::stringstream Buffer; + Buffer << "aa/" << FunctionNumber << '_' << F.getName().str() << label + << ".dot"; + std::string Filename = Buffer.str(); + errs() << "Writing '" << Filename << "'...\n"; + + std::error_code EC; + raw_fd_ostream File(Filename, EC, sys::fs::F_Text); + if (EC) { + errs() << "Unable top open " << Filename << "\n"; + return; + } + File << "digraph " << DOT::EscapeString(F.getName()) << " {\n"; + + // Split the graph into components by removing the heap node + // and treating its connected component with its own copy of the + // heap as a separate graph to aide readability. + SplitHeapComponents Splitter(*this); + auto NumComponents = Splitter.doLabeling(); + std::vector Active(NumComponents, (ONLY_A == NOT_A_NODE ? 1 : 0)); + if (ONLY_A != NOT_A_NODE) { + Active[Splitter.getComponent(ONLY_A)] = 1; + Active[Splitter.getComponent(ONLY_B)] = 1; + } + auto IsActive = [&](Node N) { return Active[Splitter.getComponent(N)]; }; + + for (unsigned H = 1; H <= NumComponents; ++H) + if (Active[H]) + File << "H" << H << " [label=\"heap\"];\n"; + + for (auto I : nonHeapNodes()) { + if (!IsActive(I)) + continue; + + File << "N" << I; + File << " [label=\"" << I << " "; + + auto V = NodeToValue[I]; + if (AliasEquivClass) { + auto AliasIter = AliasEquivClass->find(V); + if (AliasIter != AliasEquivClass->end()) { + File << ", " << AliasIter->second.Class << ": "; + } else if (DoCombining) { + auto C = DoCombining->getIndex(I); + if (C != PointerGraph::NOT_A_NODE) + File << ", " << C << ": "; + } + } + if (I == 0) { + File << " heap"; + } else if (V && !NoLabels && PrintValues) { + std::string Result; + raw_string_ostream TempStream(Result); + if (isa(V)) + TempStream << "function " << V->getName(); + else + V->print(TempStream); + for (auto C : Result) { + if (C == '"') { + File << '\\'; + } + File << C; + } + } else { + File << " N" << I; + } + File << "\"]"; + File << ";\n"; + } + + if (!ReturnedNodes.empty()) { + // Build implicit edges to a "return" node from + // nodes which are returned from the function + File << "R [Label=\"ret\"];\n"; + for (auto R : ReturnedNodes) + if (IsActive(R)) + File << " N" << R << " -> R;\n"; + } + + for (auto Edge : edges(Heap)) { + if (Edge.Other == Heap) + continue; + auto Label = Edge.Type; + if (Label == EdgeType::Reference || Label == EdgeType::AssignFrom) + continue; + if (!IsActive(Edge.Other)) + continue; + unsigned C = Splitter.getComponent(Edge.Other); + File << "H" << C << " -> N" << Edge.Other << " [label=\"" << Label + << "\"];\n"; + } + + for (auto I : nonHeapNodes()) { + if (!IsActive(I)) + continue; + + for (auto Edge : edges(I)) { + auto Label = Edge.Type; + if (Label == EdgeType::Reference || Label == EdgeType::AssignFrom) + continue; + + File << " N" << I; + if (Edge.Other == Heap) { + // Connect to this commponents heap + unsigned C = Splitter.getComponent(I); + File << " -> H" << C; + } else { + File << " -> N" << Edge.Other; + } + File << " [label=\"" << Label << "\"];\n"; + } + } + File << "}\n"; +} +} +#endif + +#ifndef NDEBUG +void CFL_On_Demand_report() { + static unsigned LastQueryCalls = 0; + static unsigned LastNoNode = 0; + if (QueryCalls > LastQueryCalls) { + dbgs() << "CFL Report" << QueryCalls.getValue() - LastQueryCalls + << " queries " << NoNodeForValue.getValue() - LastNoNode + << " no node\n"; + LastNoNode = NoNodeForValue; + LastQueryCalls = QueryCalls; + } +} +#endif Index: lib/Analysis/CMakeLists.txt =================================================================== --- lib/Analysis/CMakeLists.txt +++ lib/Analysis/CMakeLists.txt @@ -13,6 +13,7 @@ CFGPrinter.cpp CFLAndersAliasAnalysis.cpp CFLSteensAliasAnalysis.cpp + CFLOnDemandAliasAnalysis.cpp CGSCCPassManager.cpp CallGraph.cpp CallGraphSCCPass.cpp Index: lib/CodeGen/TargetPassConfig.cpp =================================================================== --- lib/CodeGen/TargetPassConfig.cpp +++ lib/CodeGen/TargetPassConfig.cpp @@ -16,6 +16,7 @@ #include "llvm/Analysis/BasicAliasAnalysis.h" #include "llvm/Analysis/CFLAndersAliasAnalysis.h" +#include "llvm/Analysis/CFLOnDemandAliasAnalysis.h" #include "llvm/Analysis/CFLSteensAliasAnalysis.h" #include "llvm/Analysis/CallGraphSCCPass.h" #include "llvm/Analysis/Passes.h" @@ -111,7 +112,7 @@ cl::desc("Run live interval analysis earlier in the pipeline")); // Experimental option to use CFL-AA in codegen -enum class CFLAAType { None, Steensgaard, Andersen, Both }; +enum class CFLAAType { None, Steensgaard, Andersen, Both, OnDemand }; static cl::opt UseCFLAA( "use-cfl-aa-in-codegen", cl::init(CFLAAType::None), cl::Hidden, cl::desc("Enable the new, experimental CFL alias analysis in CodeGen"), @@ -122,6 +123,8 @@ "Enable inclusion-based CFL-AA"), clEnumValN(CFLAAType::Both, "both", "Enable both variants of CFL-AA"), + clEnumValN(CFLAAType::OnDemand, "on-demand", + "Enable On-Demand variant of CFL-AA"), clEnumValEnd)); /// Allow standard passes to be disabled by command line options. This supports @@ -431,6 +434,9 @@ addPass(createCFLAndersAAWrapperPass()); addPass(createCFLSteensAAWrapperPass()); break; + case CFLAAType::OnDemand: + addPass(createCFLOnDemandAAWrapperPass()); + break; default: break; } Index: lib/Passes/PassBuilder.cpp =================================================================== --- lib/Passes/PassBuilder.cpp +++ lib/Passes/PassBuilder.cpp @@ -25,6 +25,7 @@ #include "llvm/Analysis/BlockFrequencyInfoImpl.h" #include "llvm/Analysis/BranchProbabilityInfo.h" #include "llvm/Analysis/CFLAndersAliasAnalysis.h" +#include "llvm/Analysis/CFLOnDemandAliasAnalysis.h" #include "llvm/Analysis/CFLSteensAliasAnalysis.h" #include "llvm/Analysis/CGSCCPassManager.h" #include "llvm/Analysis/CallGraph.h" Index: lib/Transforms/IPO/PassManagerBuilder.cpp =================================================================== --- lib/Transforms/IPO/PassManagerBuilder.cpp +++ lib/Transforms/IPO/PassManagerBuilder.cpp @@ -17,6 +17,7 @@ #include "llvm/ADT/SmallVector.h" #include "llvm/Analysis/BasicAliasAnalysis.h" #include "llvm/Analysis/CFLAndersAliasAnalysis.h" +#include "llvm/Analysis/CFLOnDemandAliasAnalysis.h" #include "llvm/Analysis/CFLSteensAliasAnalysis.h" #include "llvm/Analysis/GlobalsModRef.h" #include "llvm/Analysis/InlineCost.h" @@ -82,7 +83,7 @@ "vectorizer instead of before")); // Experimental option to use CFL-AA -enum class CFLAAType { None, Steensgaard, Andersen, Both }; +enum class CFLAAType { None, Steensgaard, Andersen, Both, OnDemand }; static cl::opt UseCFLAA("use-cfl-aa", cl::init(CFLAAType::None), cl::Hidden, cl::desc("Enable the new, experimental CFL alias analysis"), @@ -93,6 +94,8 @@ "Enable inclusion-based CFL-AA"), clEnumValN(CFLAAType::Both, "both", "Enable both variants of CFL-AA"), + clEnumValN(CFLAAType::OnDemand, "on-demand", + "Enable on-demand variant of CFL-aa"), clEnumValEnd)); static cl::opt @@ -209,6 +212,9 @@ PM.add(createCFLSteensAAWrapperPass()); PM.add(createCFLAndersAAWrapperPass()); break; + case CFLAAType::OnDemand: + PM.add(createCFLOnDemandAAWrapperPass()); + break; default: break; }