Nystrom points to analysis
From Open64 Wiki
Contents |
Objective
Alias analysis is a key prerequisite for enabling advanced and more aggressive program optimization. The goal of this effort is to extend the alias analysis infrastructure within the Open64 compiler with a more precise and scalable points-to analysis algorithm to replace the current Steensgard-based alias classification analysis. We have designed and implemented an Andersen-style pointer analysis algorithm that is flow-insensitive, field-sensitive, and context-sensitive.
Background
The alias analysis is an Andersen(or inclusion)-style points-to analysis modeled after the work done by Nystrom[1]. We felt that anything less precise than an inclusion-style model (e.g. a unification-based model ala Steensgard or Das) puts the Open64 compiler behind the curve. Nystrom's work is the only work we found that explored the combination of inclusion, field-sensitivity and context-sensitivity. The data published on the technique seems to indicate that the approach is scalable. Despite the large amount of research into points-to based solutions to the alias analysis problem this is still very much an open research problem. We believe that Nystrom's work provides sufficient knobs to constrain growth of the constraint graph such that we can achieve a reasonably precise solution for large applications in an acceptable amount of time (and space).
Overview
Our implementation is an adaptation of the Fulcra pointer analysis framework [1]. The points-to information is compactly represented as a constraint graph (CG), where the nodes correspond to symbol- offsets (thus, achieving field sensitivity), while the edges model the constraints. Points-to sets are maintained on each node. During IPL, a constraint graph is generated for each PU and solved intra- procedurally using a variation of the method described in [2]. During IPA, an inter-procedural CG is built by connecting the CG of each PU. An iterative top-down bottom-up traversal of the call graph is performed to solve the CG for the whole program, resulting in the final points-to solution. In BE, a mapping from WHIRL nodes to alias tags provides an interface from a node to its points-to set. All alias query interfaces have been modified to perform alias queries using these alias tags.
As a high-level goal, the new alias analysis algorithm will need to co-exist with the current alias analysis
algorithm until such time as it is sufficiently vetted to replace the original. In addition we would like to
encourage future exploration of this space by making the implementation of alternative alias analysis
algorithms as straight forward as possible. The discussion of the design is divided into two spaces: details
of integration within the Open64 framework and details of the alias analysis algorithm itself.
Detailed Design
Terminology
Before we start discussing the changes to the existing implementation, some terms are defined. This will hopefully help avoid confusion with the existing alias analysis functionality and/or class objects.
Existing terms:
* IPA_CALL_GRAPH : The current call graph constructed during IPA. * ALIAS_CLASSIFICATION: Implements simplified version of Steensgaard's unification algorithm. * ALIAS_RULE: Performs the alias analysis and performs language specific alias checks. * Appears to be the primary interface to alias queries for WOPT. * ALIAS_MANAGER - The primary interface between the alias analysis machinery and LNO/CG * POINTS_TO - Class that contains points-to analysis results. Handle passed to * ALIAS_MANAGER and ALIAS_RULE alias queries. The result of the Steensgard analysis manifests as an intra- and inter-procedural "alias class" fields in this object.
New terms:
* AliasAnalyzer: The new class that provide the interface to the alias analysis solution. This provides a mapping from the WN to an AliasTag (see below) * NystromAliasAnalyzer: The class that will provide an implementation of the AliasAnalyzer interface. That implementation will be through an inclusion-style constraint graph. * ConstraintGraph: A graph to model the Andersen’s constraints * ConstraintGraphNode: A constraint graph node corresponding to <ST, offset> * ConstraintGraphNodeId: Each ConstraintGraphNode has a unique id. The points-to solutions are maintained as a sparse bit-set of these ids on each node * ConstraintGraphEdge: An edge within the constraint graph to model copy, load, store and/or skew constraints * AliasTag: An id contained in POINTS_TO used to query the AliasAnalyzer results. In the context of ystromAliasAnalyzer, the AliasTag corresponds to a points-to set (set ofConstraintGraphNodeIds)
Open64 Integration
This section discusses the integration of the new alias analysis algorithm into the Open64 infrastructure. The following figure illustrates the phase ordering for the alias analysis within an –ipa compile. For a non-ipa compile, the points-to solution will be computed for each PU within BE.
IPL
the initial constraint graph is constructed and solved intra-procedurally (in Create_Alias_Manager) and is passed to IPA_LINK via the existing summary mechanism. The constraint graph summary consists of the following additional tables:
* WN_MAP_CGNODE: A new predefined map from WN to ConstraintGraphNodeId. The ids are local to the PU. * SUMMARY_CONSTRAINT_GRAPH_NODE: Table mapping ConstraintGraphNodeId to ConstraintGraphNode. This also records the points-to solution (sparse bit-set of ConstraintGraphNodeIds) for each node. * SUMMARY_CONSTRAINT_GRAPH_EDGE: Table to represent edges in the constraint graph. * SUMMARY_CONSTRAINT_GRAPH_CALLSITE: Maps call sites to ConstraintGraphNodeIds corresponding to actuals/returns
At the end of IPL, the WN_MAP_CGNODE, SUMMARY_CONSTRAINT_GRAPH_NODE, and SUMMARY_CONSTRAINT_GRAPH_EDGE tables are dumped into the .B file.
IPA_LINK
The core of the inter-procedural NystromAliasAnalysis is performed during IPA_LINK. The inputs to the analysis are the IPA_CALL_GRAPH and the global constraint graph that is constructed via summary. The alias analysis operates solely from the summary information provided by IPL and will have no need to reference the IR directly. The IPA_LINK phase remaps the per-PU ConstraintGraphNodeIds to a global ConstraintGraphNodeIds.
The inter-procedural NystromAliasAnalysis is performed immediately before the current IPAA (or mod- ref) phase. Unlike the current alias classification which is performed after inlining, by performing this analysis prior to inlining we have more control over the scalability of the algorithm as we control the size of procedure summaries during the bottom up traversal of the call graph.(more on this below).
The points-to solution is conveyed from IPA_LINK to BE via the.I files. As each PU is emitted into the .I file a new SUMMARY_CONSTRAINT_GRAPH_NODE table is assembled adding only those ConstraintGraphNodes that are referenced by the current PU. Thus, only the portion of the points-to solution that is actually referenced by PUs in the .I file is emitted. In addition the per-PU WN_MAP_CGNODE map is updated with the global ConstraintGraphNodeId.
BE
Within BE all components have access to the points-to solution via the existing ALIAS_MANAGER interface. The ALIAS_MANAGER accesses the alias analysis result through an instantiation of the AliasAnalyzer class. This class is instantiated once and used throughout BE by all instantiations of the ALIAS_MANAGER.
The ALIAS_MANAGER maintains a mapping, via an "alias id", between a WN* and a POINTS_TO*. The mapping is transient and is recreated for each invocation of the ALIAS manger. When making use of (Nystrom)AliasAnalyzer a mapping from a WN to an AliasTag that will be deposited into the POINTS_TO object at the time it is created. More specifically, the AliasTag is added to the ALIAS_INFO class.
Note that we will have to maintain this map across all IR translations (into and out of CODEREP) and lowerings that occur within BE.
Behavior under -ipa
Under -ipa, the NystromAliasAnalyzer class instantiated by the first instantiation of the ALIAS_MANAGER will provide access to the points-to solution computed during IPA_LINK. The WN_MAP_CGNODE and SUMMARY_CONSTRAINT_GRAPH_NODE table are provided via the .I file. The latter table gets the relevant points-to set, symbol being referenced, etc. from the corresponding ConstraintGraphNode.
Behavior under -O2/-O3 (w/o -ipa)
When not in -ipa mode, the points-to solution is computed during the first instantiation of the NystromAliasAnalyzer class. From that solution the WN_MAP_CGNODE and the SUMMARY_CONSTRAINT_GRAPH_NODE table for each PU is constructed.
More on ALIAS_MANAGER
The key changes to interface into the NystromAliasAnalyzer for alias analysis queries is done within the appropriate ALIAS_RULE methods, e.g.Alias_Memop_By_Analysis(). In general, all existing ALIAS_MANAGER, ALIAS_RULE interfaces as they exist today are supported.
It is also quite common to manufacture POINTS_TO objects from a <ST, offset, size> tuple. A side-effect of this action will also cause new AliasTag to be manufactured by the AliasAnalyzer object for purposes of answering alias queries.
What about current "alias class"?
The current intra- and inter-procedural alias class fields will co-exist in the POINTS_TO object with the new AliasTag. When the new AliasAnalysis implementation is sufficiently vetted we will consider removing the alias class functionality.
Flow-sensitive Alias
Today we perform a flow-senstive refinement of an otherwise flow-insensitive alias analysis in SSA. The only change to the POINTS_TO object underlying a vsym is the mapping into AliasAnalyzer. When an an ST is mapped to a vsym the POINTS_TO::Meet() will merge the points-to set of the ST into the vsym.
AliasAnalyzer
The AliasAnalyzer class (be/com/alias_analyzer.h) will serve as the interface class between the ALIAS_MANAGER and the alias analysis result. The intent is that each alias analysis method will implement the interface provided by the AliasAnalyzer class, facilitating easy experimentation with alternative approaches.
The initial interface may be un-intentionally biased by the fact that our approach is using a points-to formulation to solve the alias analysis problem. Alternate approaches may require minor adjustments to this interface.
Nystrom's Algorithm
The implementation is roughly based on Nystrom's algorithm written within the IMPACT compiler. The solution is based on the Wave/Deep propagation paper [2]. (be/com/constraint_graph_solver.cxx)
Constraint Graph
The key data structure underlying inclusion-style points-to formulation is the constraint graph (be/ com/constraint_graph.h). Our constraint graph implementation is based on Nystrom's implementation. There are a number of differences between our implementation and Nystrom's implementation in the IMPACTcompiler, these will be discussed in more detail below. The constraint graph, ConstraintGraph is a directed graph comprised of nodes, ConstraintGraphNode and edges, ConstraintGraphEdge.
There are transient periods of time during which the graph may contain cycles, namely when new copy/ skew edges are being inserted. We employ Nuutila's algorithm [2] during the solution process to locate and collapse SCCs. During this process skew cycles will be transformed into self-cycles and eventually be transformed to use either fine-grained or symbol strides (see [1]).
Constraint Graph Nodes
There are a number of key differences from Nystrom's implementation, which are primarily motivated by the need to reduce complexity and potentially improve compile time. Nystrom's implementation was intended to be a research test bed and his results afford us the opportunity to simplify the implementation based on his findings.
Rather than having a single node in the constraint graph represent a symbol and placing field offsets on the edges themselves, we chose to have a node in our constraint graph correspond to a <symbol, offset> tuple. In addition, each node will carry explicit points-to set of node ids (ConstraintGraphNodeIds) which can be mapped to the corresponding ConstraintGraphNode. The benefit of this is that we can actually eliminate the need for explicit address edges from the graph. The downside is that it has implications to context sensitivity.
Associated with each symbol is a global stride (or modulus) that facilitates precision in the presence of non-unit strided access of a symbol. We define the special ConstraintGraphNode <symbol, -1> to represent field -insensitive access to the symbol. The goal of this node is to further simplify the implementation by eliminating the need to carry explicit source and target strides on graph edges and allow the use of bitset representation of the points-to solution rather than explicit "address of" edges.
Constraint Graph Edges
We implement the following edge types: copy, skew, load and store. The primary difference with Nystrom's implementation is that points-to relationships are represented as explicit sets on each node rather than "address" edges. The goal here is to provide more efficient propagation of points-to updates across copy edges. Note that we still have to crack the points-to sets in order to propagate across skew edges and when processing load/store edges to add copy edges.
Solving a Constraint Graph
Solving the constraint graph is an iterative process. Our approach, is divided into three phases:
1. Cycle detection - As previously mentioned in order to converge to a solution we require that the
constraint graph be acyclic. We employ Nuutila's algorithm to detect SCCs.
2. Points-to propagation - Here we propagate points-to sets across existing copy/skew edges 3. New edge insertion - Here we process all load/store constraint edges and add new copy edges that
result from the modifications to points-to sets in the previous phase.
The solution process terminates if during the final phase, no new edges are added to the constraint graph.
Inter-procedural Points-To Driver
The main driver for the inter-procedural points-to solution is modeled after the algorithm proposed by Nystrom. The driver is divided into two major parts. The first part constructs a solution preview and refines the call graph. The forward solution preview is motivated by the fact that indirect function call targets are passed downward from caller to callee, so commonly we can resolve indirect call targets without complete summarization. The second phase is a standard bottom up summarization, where we solve the constraint-graph as we go. In general, employing the solution preview has been shown to reduce the number of iterations required during summarization.
Options The following new options have been added for tracing/triaging.
* -OPT:alias=nystrom to enable (default is disabled) * -ttALI options * 0x1: trace the solver * 0x2 text dump of the constraint graph after building * 0x4 : text dump of constraint graph after solve * 0x8: vcg dump of constraint graph before/after solve * 0x10 emit trace of ‘aliased()’ queries * -OPT:alias_query_limit=n, where n is the upper-bound on alias analysis query beyond which 'may' alias is returned.
Nystrom Down designs
Quality Plan
Metrics for nystrom points to analysis
1. Correctness
2. Alias query precisness
3. Performance improvment
Reference
FULCRA POINTER ANALYSIS FRAMEWORK, PHD thesis, ERIK MATTHEW NYSTROM
