Combining analyses, combining optimizations.
Modern optimizing compilers use several passes over a program's intermediate representation to generate good code. Many of these optimizations exhibit a phase-ordering problem. Getting the best code may require iterating optimizations until a fixed point is reached. Combining these phases can lead to the discovery of more facts about the program, exposing more opportunities for optimization. This article presents a framework for describing optimizations. It shows how to combine two such frameworks and how to reason about the properties of the resulting framework. The structure of the frame work provides insight into when a combination yields better results. To make the ideas more concrete, this article presents a framework for combining constant propagation, value numbering, and unreachable-code elimination. It is an open question as to what other frameworks can be combined in this way.
Introduction
Modern optimizing compilers make several passes over a program's intermediate representation to generate
good code. Many of these optimizations exhibit a phase ordering problem. Different facts are discovered
(and different code generated) depending on the order in which the optimizations are executed. Getting
the best code requires iterating several optimizations until a fixed point is reached. We will show that
by combining optimization passes the compiler discovers more facts about the program, giving more
opportunities for optimization.
This has been shown in an ad hoc way in previous work - for example Wegman and Zadeck presented
an algorithm to combine constant propagation and unreachable code elimination [10]. This paper provides
a more formal basis for describing combinations and shows when and why these combinations yield better
results. We present a proof that the simple iterative technique efficiently solves these combined optimiza-
tions. Finally, we combine Conditional Constant Propagation (CCP) and Global Value Numbering (GVN)
to get an optimization that is more than the sum of its parts [10, 1].

Overview

2.1 Intermediate Representations
Before we describe our algorithms, we need to describe our programs. A program is represented by a
Control Flow Graph (CFG), where the edges denote flow of control and the vertices are basic blocks. Basic
blocks contain a set of assignment statements and a special final statement that may be a Return, an If
or empty (fall through). Program variables are always written in lower case letters (e.g., x, y). To simplify
the presentation, we restrict the program to integer arithmetic. The set of all integers is represented by
N .
Assignment statements have a single function on the right-hand side and a variable on the left. The
function op is of small constant arity (i.e., x / aopb). op may be a constant or the identity function,
and is limited to being a k-ary function. This is a reasonable assumption for our application. We run
This work has been supported by ARPA through ONR grant N00014-91-J-1989.
the algorithm over a low-level compiler intermediate representation, with k - 3. We call the set of op
functions OP .
We assume the program has been converted into Static Single Assignment (SSA) form [3]. In the original
program, names are assigned values at multiple definition points. In the SSA form, each name corresponds
to a single definition point. By convention, we generate the new names of SSA form by adding subscripts
to the original names. This makes the relationship textually obvious to a human reader. Wherever two
definitions of the same original variable reach a merge point in the program's control flow, a OE-function
is inserted in the SSA form. The OE-function defines a unique name for the merged value. This is written
Since expressions only occur on the right-hand side of assignments, every expression is associated with
an assigned variable. There is a one-to-one correlation between variables and expressions; the variable
name can be used as a direct map to the expression that defines it. In our implementation we require this
mapping to be fast. 1 Finally, we define N to be the number of statements in the SSA form. The SSA form
can be quadratic in the size of the original code; the community's practical experience to date with SSA
has shown that it is usually linear or nearly linear in the size of the original code.
2.2 Monotone Analysis Frameworks
In order to combine several optimizations we first describe them in a common monotone analysis frame-work
[2, 6, 8]. Briefly, a monotone analysis framework is:
ffl A set of inferences we make about the program, described as a complete lattice
with height d, where:
- A is an arbitrary set of inferences.
are distinguished elements of A, usually called "top" and "bottom" respectively.
- u is the meet operator such that for any a; b 2 A,
a
a
a u (b u
a
a
- d is the length of the longest chain in L.
ffl A set of k-ary monotone functions F used to approximate the program, defined as F ' ff : L 7! Lg
containing the identity function ' and closed under composition and pointwise meet.
ffl A map F from program primitives to approximation functions. In generally, all the approximation
functions are simple tables, mapping lattice elements to lattice elements. 2 We do not
directly map the CFG in the framework because some frameworks do not maintain a correspondence
with the CFG. Incidentally, this means our solutions are not directly comparable to a meet over all
paths (MOP) solution like that described by Kam and Ullman [6]. Our value numbering solution is
such a framework.
In fact, our implementation replaces the variable name with a pointer to the expression that defines the variable. Performing
the mapping requires a single pointer lookup.
2 Some of our mappings take into account information from the CFG. Here we are taking some notational liberty by defining
the mapping from only OP to F . We correct this in our implementation by using an operator-level (instead of basic-block
level) Program Dependence Graph (PDG) in SSA form. [4, 7] Such a representation does not have a CFG or any basic blocks.
Control information is encoded as inputs to functions like any other program variable.
We say that awb if and only if a u only if awb and a 6= b. Because the lattice
is complete, u is closed on A. H The lattice height d is the largest n such that a sequence of elements
in L form a chain: x We require that L have the finite descending
chain property - that is, d must be bounded by a constant. For the problems we will examine, d will be
quite small (usually 2 or 3).
We assume that we can compute f 2 F in time O(k), where k is the largest number of inputs to any
function in F . Since k - 3 in our implementation, we can compute f in constant time.
2.3 Monotone Analysis Problems
Applying a monotone analysis framework to a specific program instantiates a monotone analysis problem -
a set of simultaneous equations derived directly from the program. Variables in the equations correspond
to points of interest in the program; each expression in the program defines its own variable. Associated
with each variable is a single inference. Program analysis substitutes approximation functions (chosen from
F using fl) for the actual program primitive functions and solves the equations over the approximation
functions. (In effect, analysis "runs" an approximate version of the program.) By design, the equations
have a minimal solution called the Greatest Fixed Point (gfp) [2, 9]. 3
Functions in F represent complete programs via composition. Monotonicity gives us some special
properties: the composition of monotonic functions is also monotonic. Also the composition is a function
onto L:
To solve the set of equations, we can set each variable to ? and then repeatedly compute and propagate
local solutions. In effect, the variables "run downhill" to the solution. The limit to k-ary approximation
functions ensures that we can compute quickly and that we do not propagate changes too far. The bound
on chain length limits the number of forward, or downhill, steps to a finite number. Monotonicity ensures
that running downhill locally cannot improve the global solution. This means that the first solution we
find is also the best solution. We will prove this formally in Section 4.
2.4 Combining Frameworks
Given any two frameworks, A and B, a framework that combines them yields better information if and
only if their solutions interact. The solution to A must rely on the solution to must rely
on the solution to A. If they are not interdependent, a careful ordering produces the same answers as the
combined framework.
To combine two frameworks, we combine the sets of equations from each framework. The equations of
A implicitly reference facts derived by the equations of B, and vice-versa. We make explicit the implicit
references to the equations from the other set. We must prove that the combined equations are still
monotonic and therefore represent a monotone analysis framework. The combined framework still has a
maximal solution; it may not be equal to the combined maximal solution of the individual problems. If,
in fact, it is identical to the combination of the individual solutions, we have gained nothing by combining
the frameworks (i.e., it was not profitable).
To demonstrate these ideas more clearly, we will work an extended example - combining simple
constant propagation and unreachable code elimination. These optimizations are well known and widely
used. Wegman and Zadeck have shown an algorithm that combines them [10]. It is instructive to compare
3 The properties described in Section 2.2 ensure the existence of a gfp [9]. These systems of equations can be solved using
many techniques. These techniques vary widely in efficiency. The more expensive techniques can solve some systems of
equations that the less efficient cannot. In general, the difference in efficiency has led classical compilers to use the least
expensive method that will solve a given problem.
their algorithm with our framework-based approach. As a final exercise, we combine CCP with partition-based
GVN [1]. to obtain a new optimization strictly more powerful than any number of repetitions of the
separate optimizations. The combination runs in O(N 2 ) time. This is faster than any previous algorithm.
In our technique, the equations are derived directly from the intermediate representation. For the
purposes of this paper, the intermediate representation is the equations. We use a technique from abstract
interpretation, and associate an approximation function chosen from F with every primitive function in
the program. Because the form of the equations restricted (see Section 2.2), we can find the maximal
solution using an iterative technique in time O(nk 2 d) where n is the number of equations to solve (often
equal to N , the number of statements in the program), k is largest number of inputs to any one function,
and d is the height of the lattice.
3 Simple Constant Propagation
Simple constant propagation looks for program expressions that compute the same value on all executions
of the program. It can be cast in a monotone analysis framework. It conservatively approximates the
program's control flow by assuming that all basic blocks are executable. Thus, control flow has no explicit
expression in the data-flow equations. Each assignment defines an expression and a variable. The inference
the variable holds tells us whether the expression computes a constant.
For our inferences we use the standard constant propagation lattice L c with the elements f?, integer
constants, ?g shown in Figure 1. The meet operator u is also defined in Figure 1. The notation
means "if c 0 is equal to c 1 then c 0 else ?". For every primitive function in the program

l
l l
A
A
c
c c

Figure

1 The constant propagation lattice L c and meet operator
we need a corresponding monotonic function f 2 F . For OE-functions we use the meet operator. We extend
the other primitives to handle ? and ?. As an example look at . The corresponding
function is by replacing op with +. The application f op
(?,?) is
? instead of ?, meaning that applying a function to undefined inputs yields undefined results (as opposed
to unknown results). 4 This embodies the idea that we do not propagate information until all the facts are
known.
For functions with zero elements we use a more precise (and more complex) extension. Multiply is
extended in Figure 3 so that f
(0; ?) is 0 rather than ?. This reflects our intuition that zero times
anything is zero. As shown in the figure, the function results are monotonically decreasing 5 both left to
right and top to bottom. Thus f
is a monotonic function, but maintains information in more cases than
the corresponding function without the special case for zero.
In

Figure

4 we generate the equations for a small program in SSA form. For every variable x in the
program we have an equation defining V x . For the assignment "x 0 / 1" we generate the equation V
Unknown values are values that cannot be discovered at compile time. There are many unknown values in a typical program.
The compiler must emit code to compute these values at run time. For undefined values, the compiler can choose any value
it wants.
5 Two integers are incomparable in the lattice, thus 0 is neither greater than nor less than c 0 \Theta c 1 .

Figure

Extending functions to L c
f
f

Figure

Extending multiply to L c
In this case "1" is a constant function from F . Because V x0 is cumbersome, we will write x 0 instead. The
different uses of x 0 will be obvious from context.
For the OE-functions we use the meet operator. The function 6= : N \Theta N 7! N returns 0 if the inputs
are equal, and 1 if the inputs are not equal. We extend 6= to f 6=
as shown in Figure 2. Assume that the
loop controlling predicate pred() is beyond the ability of the compiler to analyze, possibly a keyboard read.
Solving the equations by inspection yields x In short, no new constants are found.
Program Equations
int x 0 /
do

Figure

4 Simple Constant Propagation Example
4 Finding the Greatest Fixed Point
In this section we show that the iterative technique works on monotone analysis frameworks. That is,
we show that initializing a system of monotonic equations to ? and successively solving the equations
eventually yields the gfp. We start with Tarski [9], who proved that every monotone function f : L 7! L
has a gfp in a complete lattice L.
Since f is monotone, successive applications of f to ? descend monotonically:
The lattice is bounded so a fixed point eventually reached. We cannot have
because gfp is the greatest fixed point (and u is a fixed point). Suppose we have the reverse
situation, u. Then the applications of f must form a descending chain that falls past the gfp.
There must be some i such that \Delta \Delta \Delta. By the monotonicity of f we have
a contradiction. Therefore
successive applications of f to ? yield the gfp.
We now need to represent a system of monotonic equations as a simple monotonic function f . We
extend the lattice L to tuples in lattice ~ L. We define ~ L to be a lattice whose elements are n-tuples of L
elements. We use the notation fx to refer to a tuple of L elements. We define ~ L's
meet operator as element-wise meet over L elements:
~x ~ u
~ L is a complete lattice with the finite descending chain property. We define ~
as a monotonic
function that is a collection of monotonic functions f 7! L from the tuple lattice to the regular lattice:
~
Therefore
f (~x) defines a system of monotonic equations:
Each of the functions f takes an n-length tuple of L elements. In the problems that we are
solving, we require that only k (0 - k - n) elements from L are actually used. That is, f i takes as
input a k-sized subset of ~x. Unfortunately the solution technique of repeatedly applying ~
f until a fixed
point is reached is very inefficient. ~
L has a lattice height of O(nd), and each computation of ~
f might take
O(nk) work for a running time of O(n 2 kd). The next section presents a more efficient technique based on
evaluating the single variable formulation (f i rather than ~
f).
To provide efficient solutions, we solve these equations
f(~x) with a simple worklist iterative
technique [5]. The sparseness of the equations makes the algorithm efficient.
1. Initialize all equation variables x i to ?.
2. Place all equations on a worklist w.
3. While w is not do empty do:
(a) Remove an equation "y worklist w.
(b) Solve for y i using the values of other x i variables.
(c) If the solution for y i changes, set x i to y i and place all equations that use x i back on w.
The functions f i are all monotonic. As the inputs to the functions drop in the lattice, the defined variable
can only go lower in the lattice. Because the lattice has height d, a variable can drop (and change) at the
most d times. Each function (expression in the program) is on the worklist once per time an input drops
in the lattice, or O(kd) times. Each time a function is removed from the worklist it takes time O(k) to
evaluate. Total evaluation time per function is O(k 2 d), and the total running time is O(nk 2 d).
For simple constant propagation, the number of equations n is the number of statements N in the SSA
form of the program. If k, the arity of the functions, is small and d is 2, the running time is O(N ).
5 Unreachable Code Elimination
We do the same analysis for unreachable code elimination that we did for simple constant propagation.
We seek to determine if any code in the program is not executable, either because a control-flow test is
based on a constant value or because no other code jumps to it. Our inferences are to determine whether
or not a section of code is reachable, expressed as a two-element lattice L u with elements fU , Rg. U is
unreachable, R is reachable. We define the functions similar to boolean or and and in Figure 5.
During this analysis the only constant facts available are literal constants. So we define 6j to return U if
both inputs are textually equal and R otherwise.
U U R
R R R
U U U
R U R

Figure

5 Or, And defined over L u
In

Figure

6 we generate the equations for the same example as before. For readability we define F
as a synonym for 0 and T as any integer other than 0. The starting statement S 0 is clearly reachable.
Statement S 1 is reachable if we can fall into it from S 0 or we can reach the bottom of the loop (statement
and the loop predicate is not always false. The remaining equations are generated in a similar fashion.
Our equations are compositions of monotonic functions, and are monotonic.
Because b and pred are not literal constants all the 6j tests must return R. The solution is straightfor-
ward: everything is reachable.
Program Equations
int x 0 /
do
\Delta(pred 6j F)

Figure

6 Unreachable code elimination example
If we look closely at this example we can see that when the program is run, x 0 is set to 1, the if's
predicate b is always false, and the consequent of the if test (S 4 ) is never executed. Neither simple constant
propagation nor unreachable code elimination discovers these facts because each analysis needs a fact that
can only be discovered by the other.
6 Combining Analyses
To improve the results of optimization we would like to combine these two analyses. To do this, we need a
framework that allows us to describe the combined system, to reason about its properties, and to answer
some critical questions. In particular we would like to know: is the combined transformation correct -
that is, does it retain the meaning-preserving properties of the original separate transformations? Is the
combination profitable - that is, can it discover facts and improve code in ways that the separate techniques
cannot?
If the combined framework is monotonic, then we know a gfp exists, and we can find it efficiently. We
combine analyses by unioning the set of equations and making explicit the implicit references between the
equations. Unioning equations makes a bigger set of unrelated equations. However, the equations remain
monotonic so this is safe.
However, if the analyses do not interact there is no profit in combining them. We make the analyses
interact by replacing implicit references with functions that take inputs from one of the original frameworks
and produce outputs in the other. The reachable equations for S 3 and S 4 use the variable b, which is defined
in the constant propagation equations. Instead of testing b against a literal constant we test against an
We replace the 6j function with - : L c \Theta N 7! L u defined in Figure 7. The - function is an
example of a function that mixes inputs and outputs between the frameworks. - takes an input from the
c framework and returns a result in the L u framework.
The meaning of - is easily determined. If we know that the test is not a constant (i.e., ?) then both
exit paths are reachable. Otherwise the test is a constant and only one exit path is reachable. At first
glance this function looks non-monotonic, but F and T are not comparable in L c .
The important question to answer is:
Are the functions that represent interactions between frameworks monotonic?
If they are, then the combined framework is monotonic and we can use all the tools developed to handle
monotonic frameworks. If the original frameworks are monotonic and these transfer functions are mono-
tonic, then the combined framework is monotonic. In combining two frameworks, the implementor must
prove this property. Fortunately, reasoning about the monotonicity of these transfer functions is no harder
than reasoning about the original frameworks. The transfer functions we use in our examples can be
represented with small tables. We determine the functions are monotonic by inspection.
6.1 Profitability of Combined Frameworks
When is the combined framework profitable? It is profitable when the gfp solution computes a value for
a mixed function that is higher in the output lattice than the implicit function that the mixed function
replaced. If the mixed function's solution is the same as the implicit function's, the equations using the
mixed function have no better results than when they use the implicit function. This means the combined
solution fares no better than when the implicit functions were used, which implies the combined solution
is no better than the individual solutions.
If we have functions from framework L c to framework L u but not vice-versa, we have a simple phase-
ordering problem. We can solve the L c framework before the L u framework and achieve results equal to
F U R U R
Testing a predicate
Unreached code computes ?

Figure

7 Mixed functions for the combined equations
a combined framework. The combined framework is only profitable if we also have functions from L u to
c and the combined gfp improves on these mixed functions' results.
Back to our example: unreachable code always computes ?, so each of the constant propagation
equations gets an explicit reference to the appropriate reachable variable. The reachable variable is used
as an input to the monotonic infix function [ defined in Figure 7.
Instead of one equation per statement we have two equations per statement. Each equation has grown
by, at most, a constant amount. So, the total size of all equations has grown by a constant factor, and
remains linear in the number of statements.
Program Equations
int x 0 /
do
pred
\Delta(pred - F)

Figure

8 Combined example
6.2 An Example
The complete new equations are given in Figure 8. Solving the equations is straightforward but tedious.
A solution using the iterative technique given in Section 4 is presented in Figure 9. In this example the
boxed terms represent y i in step 3b (the variable being computed).
The main points of interests are the interactions between the separate analyses in the equations for x 1 ,
Time 0: x 3 (along with all other variables) is initialized to ? or U .
Time 4: x 1 meets x 0 and x 3 to get the value 1.
Time is a constant F .
Time 8: S 4 is left marked unreachable (U). Since S 4 did not change values, the equation setting x 2 is
never placed on the worklist.
Time 10: x 3 meets x 1 and x 2 to get the value 1. Since x 3 changed from ? to 1 users of x 3 (including x 1 's
go back on the worklist.
Time 14: x 1 's original value remains unchanged.
The solution stabilizes. Statement S 3 is marked unreachable and x 3 is known to be a constant 1. These
facts are not found by the individual analyses. Repeated applications of these separate analyses cannot
pred S 7

Figure

9 Solving the combined example
discover any more new facts because each new application starts out with no more facts than the first
analysis did. However the combined framework does finds these facts.
The conditional constant propagation algorithm of Wegman and Zadeck discovers these same facts [10].
The improved solution (more knowledge) derives from the interaction made explicit in the equations.
Specifically, the combined framework exposes unreachable code precisely because the reachablity equations
rely on an assumption made by the constant propagation equations and vice-versa. The assumption is
optimistic 6 in the sense that it is not justified by the facts at hand, but must be proven correct. If the
assumption is not correct, the equations must be re-evaluated in light of the new (more pessimistic, but
more correct) information. However, if the assumption is correct, something new may be discovered.
Thus the reason CCP is an improvement over simple constant propagation and unreachable code
elimination is that there are interactions. If, in combining frameworks, no implicit interactions are made
explicit, the combined framework can not discover addition facts. In such a case the combined framework
consists of two independent sets of equations.
7 Global Value Numbering
We can formulate a monotone analysis framework for finding congruent expressions. We define two expressions
to be congruent [1] when:
ffl The two expressions are the same expression (reflexivity).
ffl They compute equivalent functions on congruent inputs.
ffl They compute the same constant.
ffl One is an identity function on the other.
6 Wegman and Zadeck use the term optimistic assumption.
functions arise from direct copies in the input language, from algebraic identities (addition of
zero), or from merging congruent values in OE-functions. 7
Congruence is a relation that holds between pairs of expressions, so a program of size N has O(N 2 )
inferences (and O(N 2 ) equations to solve). We can derive equations involving constant inferences, reachable
inferences, and congruence inferences in a straightforward manner. The equations do interact, so there is
a benefit in solving the combined problem.
Our inferences are whether or not two expressions are congruent, expressed as a two-element lattice
Lj with elements fj, 6jg. We overload the functions + and \Delta to work with Lj elements in the usual way
as shown in Figure 5. We write C xy for a variable that determines whether expression x is congruent to
expression y, x op for the primitive function at expression x, and x i for the ith input to x op .
The basic congruence equation between expressions x and y looks like:
Reflexive
Equal functions on congruent inputs
are the same constant
Add of a zero
Add is commutative
Merge of congruent values
multiply by 1
The tests of function values (i.e., x are fixed by the program and can be pre-computed before we
solve the general problem. The equations are still complex, but there are a fixed number of special cases,
one special case per kind of algebraic identity. The number of inputs to the equation defining C xy is thus
fixed by some constant k. All the functions involved in the equation are monotonic, and the composition
of these functions is also monotonic. Thus we can use the algorithm in Section 4, and achieve a running
time of O(nk 2 d). Since and d are constants, running time is O(N 2 ).
We make GVN interact with CCP by modifying the C xy equations to use computed constants instead
of textual constants, and noting that undefined values can be congruent to anything.
As before
Either is undefined or both compute same constant
Add of a zero
These congruence equations clearly use values from the L c lattice. We add mixed functions for the reverse
direction by defining the subtraction of congruent values to yield 0, and the compare of congruent values
to yield T . 8
Since we have mixed functions going both to and from Lj and L c elements, we have the opportunity
to find more congruencies, constants and unreachable code than can be found with separate analyses.

Figure

is an example of such code.
Having solved our combined problem, what do we do with the results? If the N 2 C xy congruencies
form an equivalence relation we have a fairly obvious strategy: pick one expression from each partition to
represent all the expressions in that partition. Build a new program from the selected expressions (dropping
unreachable code and using constants where possible). However, partitions might contain expressions that
7 This is a slightly stronger notion of congruence than Alpern, Wegman and Zadeck use. They do not allow for identity
functions.
8 If, during the course of solving the equations, the subtract is of the constants 5 and 3 yielding 2, and the constants are
considered congruent we have a conflict. Instead of choosing between 2 or 0 we leave the subtract expression at ?. The
situation is temporary as 5 and 3 cannot remain congruent.
f
int is the constant 1
int is defined but unknown
int is congruent to z here
predicate
if( y 6= z ) ==if we know y and z are congruent
==then we do not destroy the constant at x
know x is a constant
==then we do not destroy the y-z congruence
printf("x is %dnn",x); ==x is always 1 here

Figure

subtle congruence, a little dead code
are algebraic identities of another expression in the same partition. These expressions should not be
selected to represent the partition.
In the presence of undefined variables the resulting congruencies do not have to form an equivalence
relation. This is because we define an expression x with being congruent to all other expressions.
Such an expression x starts out being congruent to both the constant 3 and the constant 4. If x drops
below ? the problem is resolved as the equations are solved. If x remains at ? (because x is undefined)
the congruencies between x and 3 and 4 remain. This can lead to some unusual behavior. In the code
in

Figure

both tests against x are the constant T . The analysis shows that both print statements are
always reached. 9
f
int x; ==x is undefined

Figure

Using undefined variables
Most language standards fail to address this particular aspect of using an undefined variable. We
believe our interpretation is correct given the facts at hand. The unusual behavior can be avoided by
having the analysis look for congruence relations that do not form equivalence relations. Then an arbitrary
congruence can be broken (some C xy variable set to 6j) and the analysis proceed until another (lower) fixed
point is reached. This process can continue until an equivalence relation is formed. In the worst case, all
congruencies are broken, and the result is clearly a trivial equivalence relation. This process of breaking
congruencies is forcing the analysis to choose between having x congruent to 3 and x congruent to 4.
9 And the moral of the story is: using undefined variables can lead to unexpected results.

Summary

In this paper, we have shown how to combine two code improvement techniques. We assume that the original
transformations can be encoded as monotone analysis frameworks. In our model, we can combine two
frameworks, reason about the monotonicity of the combined framework, and solve the combined framework
efficiently. Furthermore, the structure of the combined framework shows when a combination can produce
better results than repeated application of the original transformations, and, equally important, when it
cannot.
To illustrate these points, we showed how to combine constant propagation with unreachable code elimination
to derive an algorithm with properties similar to the conditional constant propagation algorithm
presented by Wegman and Zadeck [10]. Because the combined framework includes transfer functions that
take constant values into reachability and reachability values back into the constant propagation, it can
discover more constants and more unreachable code than repeated applications of the original transformations

Finally, we showed how to combine constant propagation, unreachable code elimination, and global
value numbering. It is an open question as to what other frameworks can be combined and are profitable
to combine. The asymptotic complexity of the presented analysis is O(N 2 ). It can discover more facts
than separate applications of the three transformations.
In general, combining two frameworks is important when it removes a phase ordering problem. The
monotone analysis framework for the combined problem will run in O(nk 2 d) time, where n is the number
of equations, k is the arity of the functions used in the equations, and d is the height of the inference
lattice.



--R

Detecting equality of variables in programs.
Systematic design of program analysis frameworks.
An efficient method of computing static single assignment form.
The program dependence graph and its use in optimization.
Flow Analysis of Computer Programs.
Monotone data flow analysis frameworks.
Dependence flow graphs: An algebraic approach to program dependencies.
A unified approach to path problems.
A lattice-theoretical fixpoint theorem and it's applications
Constant propagation with conditional branches.
--TR
The program dependence graph and its use in optimization
Detecting equality of variables in programs
An efficient method of computing static single assignment form
Constant propagation with conditional branches
A Unified Approach to Path Problems
Flow Analysis of Computer Programs
Systematic design of program analysis frameworks
Dependence Flow Graphs: An Algebraic Approach to Program Dependencies

--CTR
Rebecca Hasti , Susan Horwitz, Using static single assignment form to improve flow-insensitive pointer analysis, ACM SIGPLAN Notices, v.33 n.5, p.97-105, May 1998
On the decidability of phase ordering problem in optimizing compilation, Proceedings of the 3rd conference on Computing frontiers, May 03-05, 2006, Ischia, Italy
Joel Auslander , Matthai Philipose , Craig Chambers , Susan J. Eggers , Brian N. Bershad, Fast, effective dynamic compilation, ACM SIGPLAN Notices, v.31 n.5, p.149-159, May 1996
Dipanwita Sarkar , Oscar Waddell , R. Kent Dybvig, A nanopass infrastructure for compiler education, ACM SIGPLAN Notices, v.39 n.9, September 2004
Alexandre Lenart , Christopher Sadler , Sandeep K. S. Gupta, SSA-based flow-sensitive type analysis: combining constant and type propagation, Proceedings of the 2000 ACM symposium on Applied computing, p.813-817, March 2000, Como, Italy
Bjorn De Sutter , Bruno De Bus , Koen De Bosschere , Saumya Debray, Combining Global Code and Data Compaction, ACM SIGPLAN Notices, v.36 n.8, p.29-38, Aug. 2001
Min Zhao , Bruce Childers , Mary Lou Soffa, Predicting the impact of optimizations for embedded systems, ACM SIGPLAN Notices, v.38 n.7, July
Keith D. Cooper , Alexander Grosul , Timothy J. Harvey , Steve Reeves , Devika Subramanian , Linda Torczon , Todd Waterman, Exploring the structure of the space of compilation sequences using randomized search algorithms, The Journal of Supercomputing, v.36 n.2, p.135-151, May       2006
Virgil Palanciuc , Dragos Badea, A spill code minimization technique: application in the metrowerks starcore C compiler, International Journal of Parallel Programming, v.32 n.6, p.475-499, December 2004
Wankang Zhao , Baosheng Cai , David Whalley , Mark W. Bailey , Robert van Engelen , Xin Yuan , Jason D. Hiser , Jack W. Davidson , Kyle Gallivan , Douglas L. Jones, VISTA: a system for interactive code improvement, ACM SIGPLAN Notices, v.37 n.7, July 2002
Sorin Lerner , David Grove , Craig Chambers, Composing dataflow analyses and transformations, ACM SIGPLAN Notices, v.37 n.1, p.270-282, Jan. 2002
Roberto Giacobazzi , Francesca Scozzari, A logical model for relational abstract domains, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.5, p.1067-1109, Sept. 1998
Matthew B. Dwyer , Lori A. Clarke , Jamieson M. Cobleigh , Gleb Naumovich, Flow analysis for verifying properties of concurrent software systems, ACM Transactions on Software Engineering and Methodology (TOSEM), v.13 n.4, p.359-430, October 2004
Keith D. Cooper , Li Xu, An efficient static analysis algorithm to detect redundant memory operations, ACM SIGPLAN Notices, v.38 n.2 supplement, p.97-107, February
Keith D. Cooper , L. Taylor Simpson , Christopher A. Vick, Operator strength reduction, ACM Transactions on Programming Languages and Systems (TOPLAS), v.23 n.5, p.603-625, September 2001
Jeffrey Dean , Greg DeFouw , David Grove , Vassily Litvinov , Craig Chambers, Vortex: an optimizing compiler for object-oriented languages, ACM SIGPLAN Notices, v.31 n.10, p.83-100, Oct. 1996
Thomas Kistler , Michael Franz, Continuous program optimization: A case study, ACM Transactions on Programming Languages and Systems (TOPLAS), v.25 n.4, p.500-548, July
optimizing compilers;value numbering;data-flow analysis;constant propagation