The nodes when adding or removing uses of a variable incurs vir- of the CFG and the dominance relation form a tree. A depth-first search DFS , e. Furthermore, it subdivides the edges for clean-sheet designs. In the next section we give a summary of control-flow graphs, dominance, SSA and liveness. The main contribu- back edge u, v where v is an ancestor of u in the DFS tree. Section 4 provides additional details on op- forward edge u, v where u is an ancestor of v in the timization and extension of the algorithm.
The main focus DFS tree and u, v is not a tree edge. Finally, Section 7 contrasts this paper with other work, and Section 8 concludes. Figure 1 sketches the different edge types in a DFS. Since back edges play a major role in this This section introduces the notation used in this paper and paper, we dedicate some notation to them: presents the theoretical foundations we will use. To avoid confusion, parents are called parents in the DFS tree and immediate dominators in the dominance tree; an- 2.
Normally, the nodes of the CFG are the basic blocks of a Reducible Control Flow A control-flow graph is called re- procedure each associated with a list of instructions. To create irreducible control flow, loops 1. Either v contains an instruction. Because of its structural properties, the class of re- 2. This is because the vast ma- argument. This can be ex- gram representation property used in many compilers nowa- pressed as the existence of a reaching definition, i.
In SSA form, each scalar variable is defined only once existence of a path from a definition to this point. To construct SSA form, the n defi- nitions of a variable are replaced by n definitions of n dif- 2. This can be ferent variables, first. At control flow join points one may expressed as the existence of an upward exposed use, have to disambiguate which of the new variables to use.
See Figure 2 for an exam- non-strict programs. In such a case, an upward exposed use ple. We use the following notation: def a denotes the node at the entry of the CFG is a potential bug in the program in the control-flow graph where variable a is defined. Fur- that usually lets the compiler dump a warning message use thermore, uses a denotes the set of all control-flow graph of a potentially undefined variable.
With our assumption nodes where a is used. Definition 2. A variable a is live-in at a node q if there exists a path from q to a node u where a is used and that path does not contain def a. Figure 2. In a strict program with a CFG V, E, r every We present a decision procedure for the question whether a path from r to a use of a variable contains a definition of variable is live-in at a certain control-flow node.
To avoid this variable. Under SSA, because there is only a single notational overhead we will from now on consider the live- static definition per variable, strictness is equivalent to the in query of variable a at node q.
The CFG node def a dominance property: each use of a variable is dominated by where a is defined will be abbreviated by d. Furthermore, its definition. The basic idea of the al- Phi-Functions gorithm is simple. However, the paths relevant for live- z. In fact, when leaving sence can be checked efficiently. This im- tally compose it of back-edge-free subpaths. The following plies the following definition: section summarizes the basic concepts of our investigation.
Section 3. A variable x is used at a node v if: its correctness proof. Hence, a Simple Paths The first observation considers paths that second part of our precomputation constructs for each node do not contain back edges. If such a path starts at some q a set Tq that contains all back edge targets relevant for node q strictly dominated by d and ends at u, all nodes on this query.
For this precomputation to make sense, these Tq the path are strictly dominated by d. Especially, the path must be independent of variables.
Thus, they must contain cannot contain d. Hence, the existence of a back-edge-free all relevant back edge targets for any variable. The first question is, given a specific query q, a , how do This gives rise to the reduced graph Ge of G which contains we decide which back edge targets of Tq to consider? Appar- everything from G but the back edges. If there is a path from ently, this choice depends on the variable or more precisely q to u in the reduced graph we say that u is reduced reachable on its dominance subtree.
Consider again node 10 but now from q. All back edge targets 8, 5, 2 are reachable from For each The problem is that 2 is not strictly dominated by def w. Thus, even if 2 is reachable from 10, reaching 4 from 2 re- quires passing def w since 4 is dominated by 2. Therefore, Definition 4. However, this condition is not strong enough as we will Paths Containing Back Edges Of course, for the com- see in the next example. Assume we want to test for x being pleteness of our algorithm we must also handle back edges: live-in at 4.
Although x is live-in at 10 no use of x is reduced reachable However, x is not at all live at 4. The problem is that to from However, the use of x at 9 is reduced reachable reach 8 on a path from 4 the path must leave the dominance from node 8, which is the target of the back edge 10, 8.
If a variable is live-in but no use is reduced reachable there must be some back edge target from which the use is reduced The Main Principle The two last examples have in com- reachable.
Thus, they always contain the definition previous example. One must traverse the back edge to 8, a of the variable and do not comply with the requirements of tree edge and a cross edge to 6, and finally the back edge Definition 2. The dominance subtree however depends on reaching the use in 5.
That seems to be contradictory to the statement that we want to precompute the Tq sets independently of variables. Definition 5. Hence, in each step, we will only add back edge targets 7 that will provide new reachability information. Further- more, this will establish the property mentioned above, as will be shown in Theorem 1.
Section 5. An example CFG compute the Tq efficiently. Considering the loop in line 3 and the on the sets Rv and Tv being precomputed for each node v. Note that this set from t. Then we use these nodes in T q,a and the precomputed Rv to test for Let p be the strictly d-dominated path.
In the triv- reachability of a use. Otherwise, given by Algorithm 1. HAL-Inria Publications, software Hide details. Abstract : Liveness analysis is an important analysis in optimizing compilers. Liveness information is used in several optimizations and is mandatory during the code-generation phase.
Two drawbacks of conventional liveness analyses are that their computations are fairly expensive and their results are easily invalidated by program transformations. Authors: Advanced Search Include Citations. Citations: 9 - 2 self. Abstract Liveness analysis is an important analysis in optimizing compilers. Keyphrases ssa-form program fast liveness checking liveness analysis program transformation liveness information code-generation phase industrial strength compiler ssa destruction pas conventional data-flow approach ssa-form property vast majority analysis result conventional liveness analysis several optimization important analysis average speed-up control-flow graph net time liveness computation circumvent data-flow equation common program major advantage integer part spec benchmark.
Authors: Advanced Search Include Citations. Abstract Liveness analysis is an important analysis in optimizing compilers. Keyphrases fast liveness ssa-form program liveness analysis program transformation liveness information code-generation phase industrial strength compiler ssa destruction pas conventional data-flow approach ssa-form property vast majority analysis result conventional liveness analysis several optimization important analysis common program average speed-up control-flow graph net time liveness computation circumvent data-flow equation major advantage integer part spec benchmark.
0コメント