A Control-Flow Normalization Algorithm and its Complexity.
A single method for normalizing the control-flow of programs to facilitate program transformations, program analysis, and automatic parallelization is presented. While previous methods result in programs whose control flowgraphs are reducible, programs normalized by this technique satisfy a stronger condition than reducibility and are therefore simpler in their syntax and structure than with previous methods. In particular, all control-flow cycles are normalized into single-entry, single-exit while loops and all GOTOs are eliminated. Furthermore, the method avoids problems of code replication that are characteristic of node-splitting techniques. This restructuring obviates the control dependence graph, since afterwards control dependence relations are manifest in the syntax tree of the program. Transformations that effect this normalization are presented, and the complexity of the method is studied.
Introduction
The problem we are considering here is the normalization of the control-flow
of programs with the goal of facilitating program transformations, program
This work was supported in part by the National Science Foundation under Grant
No. NSF MIP-8410110, the U.S. Department of Energy under Grant No. DE-FG02-
85ER25001, the Office of Naval Research under Grant No. ONR N00014-88-K-0686, the
U.S. Air Force Office of Scientific Research under Grant No. AFOSR-F49620-86-C-
0136, and by a donation from the IBM Corporation.
analysis, and automatic parallelization. There are several ways in which our
technique makes these processes easier.
First, it reduces the number of syntactic constructions that must be treated
by the system of analysis or transformation. This lessens the complexity of
many compilation algorithms, which are often driven by the structure of the
program. If the program structure is highly regular, the number of cases and
conditions that must be considered to analyze or parallelize the program is
simply decreased.
Second, it converts all control-flow cycles into single-entry, single-exit while
loops and eliminates all branching instructions. These may have dramatic consequences
on compilation. For example, loops that contain exit branches are
difficult to parallelize since the number of iterations they will perform is unknown
prior to their execution. Likewise, goto's may be used to create cycles of
control-flow. These hidden loops may cause a loss of parallelism, both because
the loops they describe are missed by techniques of parallelization that apply
only to do loops, and also because the control-flow of other loops and sometimes
entire subroutines may be disturbed by such cycles. Similarly the use of goto's
makes program transformations and analyses more difficult and inefficient in
general, for the reason that the simple compositionality of control-flow is lost.
In terms of semantics, we may say that in the absence of goto's, a direct semantics
may be given, whereas in their presence, a continuation semantics is
needed. The increased complexity of a continuation semantics is translated to
increased complexity in any program analysis that models the semantics, e.g.,
abstract interpretation or dataflow analysis.
Third, our technique obviates the control dependence graph. Much effort
is spent in traditional parallelizing compilers in the treatment of control dependences
[3]. We will argue that when the control-flow of a program is properly
normalized, control dependence relations are so manifest in the syntax tree of
the normalized program that there is no need for a separate representation of
such dependences. Similarly, the method makes it unnecessary to perform interval
analysis as part of dataflow analysis, because after normalization the internal
structure of a program is obvious and trivial. It may therefore be used to simplify
the implementation of dataflow analysis since pathological flowgraphs [38]
will not exist.
Unnormalized programs may arise in several ways. First, unstructured programs
can be written in languages such as Common Lisp, Fortran, Pascal or
C. Second, the compiler itself may produce unstructured code when it applies
classical program transformations such as tail recursion elimination [14]. For an
example see figures 1 and 2. Other transformations such as recursion splitting
[22] result in even more complex output than the tail recursion elimination. If
we wish the compiler to work always with a normalized program, we may apply
normalization following such transformations.
A lot of work has been done in the normalization of the control-flow of programs
[10, 47, 12, 5]. All of these techniques result in programs with reducible
(defun f
(lambda
(begin
(cond ((null? x) y)
(f (car x) y)))))))

Figure

1: A sample of recursive Lisp program
(defun f
(lambda
(begin
I 1 (cond ((null? x) (set! r y) (go I 2
I 2 (return r))))

Figure

2: After tail recursion elimination
control flowgraphs. However, the method of normalization presented here results
in programs which are more highly regular than those produced by these
methods. In other words, a condition much stronger than reducibility is satisfied
by the control flowgraphs that result from our method. Furthermore, while
some previous methods of control-flow normalization result in excessive code
replication, we will show below that code replication is necessary under our
method only for the elimination of irreducibility, a condition that is rare even
in unstructured programs.
2 Presentation of the Normalization Method
Our normalization works by transforming a program into a system of simultaneous
equations, whose unknowns represent the continuations associated with
program labels. The solution of this system of equations is the normalized form
of the program. The effect of this is to detect all of the loops and to eliminate
all pathological syntactic constructions that the program contains. Williams
and Ossher [47] have proved that such an elimination is necessary and sufficient
to obtain a structured form of the program. A theorem of B-ohm and Jacopini
[13] says that we may transform any program into another one where only the
following three control structures are used:
Assignment
Conditional
ffl Iteration
However, their theorem is not constructive in that it does not give a method
for deriving such a program. The technique presented below does exactly this
in a simple and efficient way. Normalizing the control-flow of a program consists
of transforming this program into another equivalent one where only the three
foregoing control structures are used.
The input language we treat has a Lisp-like syntax and includes branching
instructions (goto's) and labels at the top-level of procedures. We applied this
method to Fortran 77 and Le-Lisp [16] [6], and are applying it to Common Lisp,
and C [25].
The output language contains single-entry, single-exit while loops but neither
goto's nor labels, and represents the normalized form of the program.
2.1 Denotational Semantics
The semantics of a programming language is a precise mathematical specification
of the meaning of programs in the language [42, 45, 40]. The idea of this
approach is to define functions which map syntactic constructs into algebraic
ones. This method is based on Scott and Strachey's work and has been used to
define languages like ALGOL 60 [31], PASCAL [45], and CLU [39]. Our input
language contains branching instructions. Simple jumps make the semantics of
programs more complex because we lose the compositionality of the semantics
of commands. We must then switch from a direct semantics to a semantics with
continuations. The theory of continuations was developed by C. Wadsworth
and L. Morris independently. This notion originated from the "tail function" of
Mazurkiewicz [30].
2.1.1 Continuations
Continuations are a powerful tool because they allow us to give a straightforward
meaning to branches, exceptions and errors, and because they allow us to regain
a degree of the compositionality we lose by having branches. The continuation
of an instruction I is a function which, when applied to a store, gives the final
result of the program when its execution begins with this instruction I. The
result is a new store (state of memory). Usually continuations are associated
with each point of a program. In our approach a point will represent a program
label.
The author provides, for the interested reader, a denotational semantics with
continuations for the primitive expressions of our language [7, 8]. The language
is described in the following section.
2.2

Abstract

Cste 2 Cste Constants
Commands or expressions
lambda 2 Proc Lambda expressions
(while Cmd)
where unop is a unary operator such as \Gamma; not; and biop is a binary operator
such as +,-,*,/,and, . For the purpose of simplicity, the grammar
includes only scalar variables. The normalization method we are presenting has
been applied to Fortran and Lisp programs [6, 24], and is by no means restricted
to the treatment of scalar data; nor does it require restrictions upon side effects
and aliasing.
2.3 Continuation Equations
For a procedure P we may give a syntactic representation to the continuation
associated with each program label I i . We will call it x i .

Figure

3 illustrates a sample of a Lisp program. We obtain from this program
the system of continuations equations of figure 4. x 0 is the source continuation
(it contains the solution of the system after its resolution) and x 1 , x 2 , x 3 , and x 4
are the continuations associated with the labels I 1 , I 2 , I 3 , and I 4 respectively.
unknowns of the system.
The only control structures used in these systems are the three proposed
by B-ohm and Jacopini [13]. The solution to this system will represent the
normalized form of the procedure. In the next section we will present the method
we choose to solve this system.
2.4 Gaussian Elimination-Like Resolution
A straightforward Gaussian elimination-like resolution method may be used to
solve the system of continuation equations. This method yields a solution with
(defun h
(lambda (i j
(begin
I 2 (if (? i 10) (go I 3
I 1 (set! j 1)
I 4 (set! i (+ j k))
I 3 i)))

Figure

3: Sample of Lisp program

Figure

4: Continuation equations of the program in figure 3
is the number of equations (or unknowns). But the
solution we are presenting is a refinement of this method. We will see later
in this paper that this refinement improves the complexity considerably. The
Gaussian elimination method consists of the substitution and the elimination of
each unknown, where it appears in the system. We want to satisfy two criteria.
The first is to minimize the code size; this is accomplished by factorization.
The second is to convert every control-flow cycle into a while loop, and this
is accomplished by derecursivation. Solving this system in the style of Gaussian
elimination and performing these transformations along the way gives the
normalized form of the program.
2.5 Transformations
If we look at the continuation equations we have built, we may remark that
they contain no branches and have a regular structure. In general an equation
has the following form:
The true and false parts of the if statement may contain other if state-
ments, or the if statement may be absent altogether. Let us present below the
transformations we use to solve the system.
2.5.1 Pre-calculation
This is in effect a sub-transformation useful for the transformations presented in
the rest of the paper. It puts the boolean expression of a conditional statement
into a new temporary variable. The temporary is defined once and only once in
the program. For example, the following statement
will become, after pre-calculation,
pred 1 Exp)
(if pred 1 (begin Cmd 1
2.5.2 If Distribution
Like pre-calculation, this sub-transformation is useful for the transformations
presented in the rest of the paper. It rewrites an if statement containing
continuation variables into a sequence of two if statements. The first contains
the condition that is captured in a temporary variable (by pre-calculation),
and the second one contains only the continuation variables controlled by the
temporary variable. The if condition is saved in a temporary variable, not
only to avoid multiple computations of it, but also to guarantee a correct result,
since its arguments may be affected by Cmd i . As an example let us consider
the equation x i
after if distribution, the equation is
pred 1 Exp)
(if pred 1 (begin Cmd 1 )
(if pred 1 x
2.5.3 Factorization
One unknown may appear several times in a single equation. To avoid increasing
the code size during the elimination process, we factor this equation. Two
different factorization may be used to factor an unknown: factorization with
boolean expressions, and factorization with selector variables.
Factorization with Boolean Expressions
This consists of assembling all the conditionals (boolean expressions) governing
one unknown (using if distribution) and replacing the equation by one
in which the unknown appears only once. Consider a continuation equation
whose form is:
x j is guarded by the boolean expression (or Exp (not true. Then we
can rewrite the equation:
pred 1 Exp) (if pred 1 Cmd 1 Cmd 2 )
(if (or pred 1 (not pred 1
This is equivalent to
pred 1 Exp) (if pred 1 Cmd 1 Cmd 2
Now if we add another nesting level of if and another unknown x k
(begin (if Exp 2
(begin Cmd 3 x j )))))
x j is guarded by (or Exp 1 (and (not Exp 1 ) (not Exp 2 ))) and x k is guarded by
(and (not We can then rewrite the equation as:
pred 1
(if pred 1
(begin (set! pred 2 Exp 2 ) (if pred 2
(begin Cmd 3 ))))
(if (and (not pred 1
To build the selection tree
(if (and (not pred 1
we order the unknowns appearing inside x i in increasing order of number of
appearances. In this case x k appears once inside x i but x j appears twice. Thus
x k will be treated first in the selection tree. In case the number of appearances
of all unknowns are the same, they are taken in order of their appearance inside
the equation. This heuristic order allows us to create boolean expressions of
manageable size in the case of several if nesting levels.
Factorization with Selector Expressions
This consists of replacing each unknown by assignment to a selector variable.
A single, integer value is associated with each unknown and a case statement
is added that sends control to the appropriate continuation. Consider the same
continuation equation than above:
we add a variable selector and assign it a value for each unknown in the equation.
x j is replaced by (set! selector 1). Then we can rewrite the equation:
(begin Cmd 2 (set! selector 1)))
(if (= selector 1) x j )):
Now if we add another nesting level of if and another unknown x k
(begin (if Exp 2
(begin Cmd 3 x j )))))
We rewrite the equation using the selector variable as follows:
(begin (if Exp 2 (begin Cmd 2 (set! selector 2))
(begin Cmd 3 (set! selector 1)))))
(if (= selector1) x j (if (= selector 2)x k )))
Of course, the order in which we place the unknowns in the selection tree is
irrelevant, since the guard is in any case simply a test for the value of the
selector. To compare these two methods and to measure their respective cost,
we have run an experiment that normalizes the scientific computations of the
Perfect Club [34]. See figures 24 and 25 in section 5.
2.5.4 Derecursivation
Derecursivation, like T 1 Hecht's transformation [20], consists of making a loop
explicit. A self-recursive equation has this form:
Intuitively this equation is a loop whose entry is the instruction labeled by
x i and whose condition of iteration is the condition that leads to x i . In this
case we iterate the loop until Exp becomes false, in which case we perform the
begin form associated with the false part of the if.
The fixed point of the above equation is:
(begin Cmd (set! pred 1 Exp)
(if pred 1 Cmd 1 Cmd 2 )
pred 1
The semantics of the while statement is to iterate the begin form contained
inside the while form until pred 1 is false. It has the semantics of a repeat;
therefore, it supposes that the loop body is performed at least once.
Consider an equation with another level of if nesting
(begin (if Exp 2
(begin Cmd 3 x k )
Again here we must study the boolean expressions guarding each continuation
inside the equation. x j is guarded by Exp 1 , x k is guarded by (and (not
finally x i is guarded by (and (not Exp 1 ) (not Exp 2 )). The
latter condition represents the exit condition of the while loop induced by the
continuation
pred 1
(if pred 1 Cmd 2
(begin (set! pred 2
(if pred 2 Cmd 3 Cmd 4 )))
(and (not pred 1 ) (not pred 2 ))))
(if pred 1 x j (begin (if pred 2 x k ))))
2.5.5 Substitution and Elimination (T 0
consists of substituting an unknown in the continuations system
and of eliminating its equation from this system. However, Hecht [20] performs
T 2 on unknowns that have only a single use in the system. The T 0
transformation
is not constrained by this condition since it replaces an unknown anywhere
it appears in the system (i.e., an unknown may be replaced in several different
2 is performed after we have checked that the unknown we
are eliminating is non-recursive (which in this case should be derecursivated
first) and that the equations where it appears are factorized (to avoid several
substitutions of the same unknown in a single equation). If our system is

Figure

5: Elimination of x 2 from the system in figure 4
then after the substitution of x j in x i and its elimination from the system, we
will obtain the following equivalent system.
(begin Cmd 3 x k )))
Each application of the T 0
transformation reduces the number n of unknowns
in the system, into n \Gamma 1.
2.6 Example of Resolution
The system of continuation equations resulting from the program in figure 3
is presented in figure 4. To solve this system we use the transformations presented
above. We may begin the resolution by eliminating x 2 , which appears
in the equation of x 0 and x 4 . The equivalent system after its elimination is
in figure 5. The next step may be to eliminate x 1 from the resulting system.
The equivalent system is in figure 6. Since x 4 is recursive, we want to apply
the derecursivation transformation to create the corresponding while loop and
the elimination transformation to replace and eliminate the unknown from the
system. The resultant systems are in figure 7 and figure 8, respectively. At this
point, x 3 appears twice in x 0 ; we then need to factor x 0 . The resultant system
is shown in figure 9. And finally, after the substitution and elimination of x 3 ,
we obtain the normalized form in figure 10.
2.7 Structure of the Original Program
When we build the continuation equations, we attempt to preserve as much as
possible the original structure of the program. That is to say, if the input procedure
contains control constructs that are already normalized (by normalized
we mean that there are neither branching instructions leaving this construct,
nor branching instructions entering it), the construct is preserved and not re-
normalized. In figure 11, the while loop is already normalized. The associated

Figure

Elimination of x 1 from the system in figure 5
pred 1 (? i 10))
(if (not pred 1
(not pred 1

Figure

7: Derecursivation of x 4 from the system in figure 6
(begin (while (begin (set! i (+ j k)) (set! pred 1 (? i 10))
(if (not pred 1
(not pred 1 ))) x 3 ))))

Figure

8: Elimination of x 4 from the system in figure 7
pred 2 (? i 10))
(if (not pred 2 )
(while (begin (set! i (+ j k)) (set! pred 1 (? i 10))
(if (not pred 1 pred 1 )))))

Figure

9: Factorization of x 0 from the system in figure 8
(defun h
(lambda (i j
(begin
pred 2 (? i 10))
(if (not pred 2 )
(begin
(while
(begin
pred 1 (? i 10))
(if (not pred 1 )
(not pred 1 )))

Figure

10: Normalized form of the program in figure 3
continuation equations system is in figure 12. The while is treated as if it were
an assignment statement. Now, if we look at the program in figure 13, the while
loop has an exit from inside it. In this case, the while loop is first rewritten
in terms of goto's and if's as shown in figure 14, and then converted into a
normalized form.
3 Order of Resolution
In the system of figure 4 above, we eliminated the unknowns in an arbitrary
order. But it is easy to see that the quality of the normalized form of the
program, in terms of code size, depends upon the order in which the unknowns
are eliminated from the system. To give an idea of the importance of this order,
let us take the previous system of equations in figure 4 and try to eliminate the
unknowns in a different order. Let us choose the following order of resolution:
The system after elimination of x 1 is in figure 15. The variable
x 3 , and x 4 now occur in the equation for x 2 . The elimination of x 4 leads to
the equivalent system in figure 16. x 2 is recursive; after its derecursivation and
substitution we obtain the system in figure 17. And finally after the elimination
of x 3 , we obtain the normalized program in figure 18.
Of course the programs in figures 10 and are semantically equivalent, but
the second one does not contain any replicated code and the body of the while
loop is restrained strictly to the code dependent upon it; i.e., no code is inside
the loop body that does not need to be.
(defun f
(lambda (j i a b n)
(begin
I 1 (set! i 1)
(while (begin
(set! a (+ b j))

Figure

11: Program containing a normalized control structure

Figure

12: Continuation equations system of the program in figure 11
(defun g
(lambda (j i a b n)
(begin
I 1 (set! i 1)
(while (begin
(set! a (+ b j))
I 2 (set! b (+ j 1))

Figure

13: Program containing a non-normalized control structure
(defun g
(lambda (j i a b n)
(begin
I 1 (set! i 1)
(if (! g n) (go G 1
I 2 (set! b (+ j 1))

Figure

14: Equivalent form of the program in figure 13

Figure

15: Elimination of x 1 from the system in figure 4

Figure

Elimination of x 4 from the system in figure 15
(while (begin (set! pred 1 (? i 10))
(if (not pred 1
(not pred 1 ))) x 3

Figure

17: Elimination of x 2 from the system in figure
(defun h
(lambda (i j
(begin
(while (begin
pred 1 (? i 10))
(if (not pred 1 )
(not pred 1 )))

Figure

normalized form of the program in figure 3
We observe from this that the order of resolution has an important impact
on the running time of the resolution process and on the code replication. The
order of resolution we propose is as follows: first, sort in an extended topological
order the nodes of the graph associated with the equations, and second,
move the loop headers in this order so that they appear after the unknowns
representing their bodies. Note that our algorithm is slightly different from the
classical method of interval analysis. The normalization method makes use of
the strongly connected component, and of the topological sort of the acyclic continuations
flowgraph to solve the system of continuations. In the next sections
we describe the elimination order of the unknowns.
3.1 Graph and Topological Sort
The graph E) associated with the system of equations represents the
control flowgraph of the program and is defined by taking the nodes as the
unknowns of the system and by creating an edge when the unknown x j
appears inside the equation x i . jN are the number of nodes
and edges. For example, the graph associated with the system of equations in
figure 4 is in figure 19.
A topological ordering of the nodes of such a graph is a labeling of the
nodes with integers Of course this graph must be acyclic for this
ordering to be meaningful. Since, in general, our input graphs contain cycles,
we order the nodes by first eliminating the back and cross edges of the graph
and sorting the resulting graph in a topological order. We call this the extended
topological sort of the graph. By visiting the graph nodes in a depth-first order,
the complexity of the combined algorithm is kept to O(n
In figure 19, x 2 is a single loop header and its body consists of the unknowns
x 1 and x 4 . An extended topological order is The next step
Figure

19: Graph associated with the system in figure 4
now is to reorder the loop headers. x 2 must appear after x 1 and x 4 (the two
unknowns in its body). The order of resolution used
in the previous example follows this order.
3.2 Algorithm to Find the Order of Resolution
Input: A list H of loop headers
A list b h of labels in the body of each loop header h
A list L of unknowns ordered in extended topological order
Output: Ordered list of unknowns.
For each unknown x i in L
Then
ffl Delete x i from L and insert it immediately after all the
unknowns constituting the body of the loop designated by
x i . These unknowns are given by b x i
3.3 Algorithm for Resolution of the System
Input: Ordered list of unknowns L
Output: Source label whose equation represents the normalized form
of the program.
1. Select the first unknown x i from L
2. If x i is self-recursive
Then
ffl Derecursivate x i (apply
For each x j such that x i is an element of the unknown set of
ffl Factorize the occurrences of x i in x j
ffl Substitute x i in x j (apply T 0
3. If L non-empty goto 1.
3.4 Example
Let us consider now the irreducible program in figure 20. We do not give
the details of all the transformations performed on the continuation equations
system but present only the system in figure 21 and the associated continuation
graph in figure ??. There are two nested loops in this graph whose headers are
. The order of resolution is normalized
form relative to this order is in figure 23.
(defun g
(lambda (i j x)
(begin
I 1 (if (? i
I 2 (set! x i)
I 3 (set! i (+ i 1))
(if (? x i)
(begin (if (? x
(go I 5
I 4 (set! j 1)
I 5 (set! j 2))))

Figure

20: Irreducible program

Figure

21: Continuation equations of the program in figure 20

Figure

22: Continuation graph of the system in figure 21
(defun g
(lambda (i j x)
(begin
(while (begin
pred 1 (? i 0))
(if (not pred 1 )
(while
(begin
pred 2 (? x i))
(if pred 2 (begin (set! pred 3 (? x j))))
(and pred 2 pred 3 ))))
(and (not pred 1 ) (and pred 2 (not pred 3 )))))
(if (and pred 2 (or pred 1 (not pred 3 )))

Figure

23: Normalized form of the irreducible program in figure 20
4 Complexity
In this section, we will analyze the complexity of the normalization method by
counting the number of transformations necessary to solve a system of continuations
equations. A complete time - and space - complexity study would involve
us in details of data structures that are beyond the scope of this paper. However,
the analysis below reveals the most important aspects of the complexity of the
normalization algorithm and can be extended to a complete one by considering
the cost of applying individual transformations to a chosen representation of
the program. Let S be a system of continuation equations and E) the
graph associated with S. i 2 N . Let jN
In i represents the set of nodes entering the node i or, alternatively, the set
of unknowns in whose equation i appears.
d(j; i) is the degree of multiplicity of the edge (j; i), i.e., the number of times
appears in the equation of j.
n s is the total number of substitutions performed during the resolution pro-
cess; n f represents the number of factorizations, and n d the number of derecur-
sivations.
4.1 Number of Substitutions
We will show that the number of substitutions performed during resolution
does not exceed the number of unknowns n in the system, in the case that G is
reducible.
Theorem 1 G reducible ) each equation is substituted only once in the system
S.
Proof: Let In
This means that i appears (at least once) in the equation of k. We want
to substitute the unknown i in the system. As we have seen in the algorithm,
before any substitution of an equation of i into k, k is factorized so that i occurs
only once in the equation of k. Several cases may appear:
substituted for only once in the system.
In this case i appears in several equations of the system. It may be inside
a loop whose header is h, or may itself represent the header of a loop 1 , or
finally may be neither of these two cases. Let s be the source node of the
graph.
Case 1: The simplest case is when i has several predecessors
and is neither a loop header, nor inside a loop. In accordance
with the resolution order we have chosen, the predecessors of
i will be treated before i itself. When we come to substitute
i, it will appear in the equation of its nearest dominator h [2].
After factorization of h, i will appear only once in h, and will
be substituted for only once.
Case 2: i is in a loop whose header is h but i and h are distinct.
In this case, by the order we have chosen and the fact that G
is reducible, all of the predecessors of i in the loop (except for
will be treated before i itself. When we come to substitute
i, it will appear only in the equation of h by the fact that h
dominates i. And after the factorization of h, i will appear only
once in the system and will therefore be replaced only once by
substitution.
Case 3: i is a loop header. According to the resolution order
we have described earlier, we treat every node inside the loop
before the header. Let h be the header of the innermost loop
containing the i loop (or s, if there is no such loop). When we
treat i, it will therefore be a self-recursive variable that appears
is reducible, for every control-flow cycle of G there is a unique loop header that
dominates every node in the body of the loop.
also in the equation of h (or s). After derecursivation of i and
factorization of h, i is substituted for only once in the system.
Since we have n equations in the system,
n:In an irreducible graph, our method may replicate code. In the worst case,
without any preliminary factorization, the number of substitutions for the unknown
i will be bounded by the number of its predecessors.
Theorem 2 G irreducible ) each unknown is substituted at most n times.
Proof: In the first step of the elimination the first unknown is substituted
in the worst case, times. The second time, it is substituted n\Gamma2 times, since
after the first substitution one unknown is definitely eliminated from the system
and so on, until we eliminate all the unknowns. The number of substitution is
then
):Note that this bound is very conservative, as it assumes that the control
flowgraph of the program is a clique!
4.2 Number of Factorizations
If we look at the algorithm of resolution above in section 3.3, we see that a
factorization is applied to each predecessor x j of x i before substituting x i . The
factorization is of course unnecessary if x i occurs only once in an equation. It
must be noted that applying one single step of factorization on each x j has the
effect of reducing the instances of all the occurrences in x j to one (the degree of
each edge between x j and every occurrence of x j is 1). The number of instances
of a variable inside an equation is bounded by n, and a single factorization step
is able to reduce these instances to one. In the worst case a factorization is
necessary before every substitution; therefore n f - n s .
4.3 Number of Derecursivations
A derecursivation is performed every time a node has itself as an occurrence.
The number of derecursivation depends then upon the number of loop headers
in the entire graph. In the worst case, every node in the graph is a loop header;
then
Again this is a very conservative bound.
In summary, the number of transformations performed in the case of a reducible
flowgraph is on the order of the number of continuation equations in
the system. Of course, in this study, the complexity does not take into account
the size of the continuation equations, nor the time necessary during substitu-
tion, to find within the equation the unknown for which to substitute, nor in
factorization the cost of collecting and simplifying boolean conditions.
5 Application of the Normalization Process
The normalization method that we have presented has been put to several uses
in projects with which the author has been involved: PAF [44] and MIPRAC
[24].
PAF is an experimental Fortran parallelizer developed at the University of
Paris 6 (France). In PAF the normalization method has two applications. The
first is to convert every cycle (explicit or implicit) into while loops, which are
themselves transformed into do loops whenever possible [9], and finally into
doall loops when the dependences permit it. In other words, even when a
programmer writes loops using goto's, or writes unstructured do loops, they
are made eligible for parallelization by normalization. The second purpose is
vectorization. In order to vectorize statements that are conditionally executed
in a loop, one must attach boolean variables (mode vectors) to the statements
[29, 48, 17, 32]. By control-flow normalization we may accomplish this easily
for any program.
MIPRAC is a multilingual compiler for shared memory machines being implemented
at the University of Illinois. Its applications of the normalization
method are much more ambitious.
First, it allows us to write a genuinely multilingual compiler. MIPRAC
accepts programs in Common Lisp, C, Scheme, and Fortran. Together these four
languages contain many control structures, such as do, dolist, dotime, loop,
cond, block, return, break, case, switch, exit, for, while, goto, continue,
if, and pause. After normalization only three control-structures remain: begin,
if, and while. Moreover, the intermediate form is properly structured. In other
words, multilinguality in MIPRAC means that programs from various languages
all have a simple, structured representation in MIPRAC's intermediate form,
and this is accomplished by normalization.
The second application is to simplify program analysis. In effect, normalization
allows programs that require a continuation semantics (because of goto's)
to be converted into programs that may be given a direct semantics. For ex-
ample, a program with goto's might have as its meaning a function of type
normalization the same program
would have as its meaning a function of type Store ! Store. This simplification
shows up when we write an analysis of the program as well. Whereas an abstract
interpretation of the unnormalized program might be a function of type
(where -
Store is an abstraction of memory),
an abstract interpretation of the normalized program could be a function of
Store. This makes the analysis simpler to implement and more
efficient. The reader may contrast the interprocedural analysis, where continuations
are used [22], to that where direct semantics are applied to programs
whose procedures bodies are normalized [23].
The third application is to simplify program transformations. When restructuring
an expression, we do not need to be concerned with branches into the
middle of, and out from the middle of the expression: control flows into and out
of the expression in an orderly way. The reader may look at Harrison's work
[21] to see the difficulties that we may encounter for program transformations
such as exit-loop parallelization and recursion splitting [22], when they are performed
on a code that is not so structured. By control-flow normalization, we
effectively make while- and do- loop transformations applicable to all iterative
structures by replacing arbitrary control-flow cycles by single-entry single-exit
loops, and by reducing the number of different syntactic structures.
Program points after normalization are quite different than program points
in the program text known to the user. This problem is fairly easily solved by
observing that any expression in a normalized program comes from exactly one
expression in the source, and then a map from the transformed program to the
original source is well-defined and can be maintained.
As stated in section 2.5.3, we compared, by running experiments on the Perfect
code, the factorization using boolean expressions and selector expres-
sions. We measured the number of boolean expressions and selector expressions
generated, and the code replication that results with and without factorization.
See figures 24 and 25.
Column EBN gives the number of expressions present in the program before
normalization. Column EANF gives the number of expressions in the program
after normalization with factorization. Column BEXP gives the number of
boolean expressions that are added during factorization. Column SEXP gives
the number of selector expressions (a selector expression is an assignment of a
selector variable) that are added during factorization. Column BEXP/EANF
gives the ratio of these counts. Likewise for the ratio SEXP/EANF. Column
EAN gives the number of expressions in the program after normalization without
represents the growth of code when
factorization is performed and EBN is the growth when the code
is normalized with no factorization. Note that when factorization is not used,
neither boolean nor selector expressions are added to the program by the normal-
ization. The factorization with boolean expressions requires that every predicate
guarding a conditional statement is stored in a temporary variable (see transformation
of if distribution above). These temporary variables are not necessary
when the factorization with selector expressions is performed. That is the reason
why EBN for the same code has different value, when the factorization is
performed using selector expressions versus when using boolean expressions.
The average ratio of boolean expressions BEXP created over the total number
of expressions in the program EANF is 0.01. The average ratio of selector
expressions SEXP created over the total number of expressions in the program
EANF is 0.004. If we compare GF with G, we may see that GF is always smaller
than the G (except when factorizing TRFD with selector expressions), and that
the boolean expressions that are created have a reasonable size. For some codes,
GF is negative; this is due to the fact that the normalization process simplifies
the source code and produces a compact form of the code (for example all of
the labels and goto's in the source code are eliminated.
N.B. In Miprac Fortran, C and CL front-ends translate every loop using
goto's and labels. 2 Therefore the column EBN includes all these labels and
goto's added by the front-ends. This accounts for much of the negative code
growth.
It is clear when we look at these measures, that factorizing with selector
expressions results in less code growth than factorizing with boolean expres-
sions. Although in both cases the growth seems to be manageable. The main
reason for the small number of boolean expressions is that we use an heuristic
order that allows us to create boolean expressions of manageable size in the
case of several if nesting levels. Miprac does not use a phase of boolean expression
simplification; rather, factorization with selector expressions is used so
that excessive boolean expressions are not created. It appears, however, that
the boolean expressions generated by the normalization are small enough that
simplification would not be a major expense.
6 Position of Our Work
Several techniques exist for structuring flowgraphs [13, 28, 33, 11, 12, 5]. Most
of these techniques consist of modifications such eliminating goto statements,
adding control-flow variables, copying code, creating and calling procedures and
adding levels of iteration. Each of them may be appropriate for some cases;
however the programs they produce are often less regular than those produced
by our method and often contain more replicated code [27]. None presents a
simple comprehensive algorithm for the normalization of all control flowgraphs.
We present, below, a limited overview of each of these methods; however, we
emphasize Kennedy's method [5], since it is the most recent and the closest to
our own method.
B-ohm and Jacopini [13] present two normalization methods of flow diagrams.
They decompose the flow diagrams into base diagrams of three types or two
types. These methods, like ours, add boolean variables, but they replicate code
2 The motivations for that is first, a single representation of source code written in three
different languages and, second a uniform representation of loops that have goto's and break's
in and out of them.
Code EBN EANF BEXP EAN BEXP/EAN GF G
MDG 13870 13648 43 19342 0.003 -222 5472
MIGRATION 43369 42716 154 43899 0.003 -653 530
Total 426648 416968 4915 605491 0.01 -10774 178843

Figure

24: Factorization with Boolean Expressions
Code EBN EANF SEXP EAN BEXP/EAN GF G
MIGRATION 42349 41912 178 42632 0.004 -437 283
Total 414088 401772 1868 587513 0.004 -12316 173425

Figure

25: Factorization with Selector Expressions
even in normalizing reducible flowgraphs. Furthermore, the authors do not
present a simple algorithm, but rather describe the method by pattern-matching
of flowgraphs, which could be complex and costly to implement.
Knuth and Floyd [28] study program transformations that eliminate goto
statements without introducing new variables or modifying the sequence of the
program computations. The first possibility is to eliminate the goto's by introducing
procedures; this is sometimes quite a clean solution, except that the
procedure-calling overhead may be important in programs that involve many
loop iterations. The second possibility is to write a flowchart according to the
BNF they have defined. Both methods replicate code in normalizing reducible
flowgraphs. The authors declare that these methods do not suffice to eliminate
goto's in all programs.
Peterson, Kasami and Tokura [33] define a well-formed program as a program
in which loops and conditional statements are properly nested and have a single
entry. To obtain such a program they use a node splitting transformation that
may replicate code, or procedure calls in case the code replication is too big.
The method replicates code in normalizing reducible flowgraphs (no bound is
given on the size of the resulting program) and the resulting programs have
multiple-exit loops, and branches that exit several nested control structures.
Ashcroft and Manna [11] introduce two transformations to translate programs
with goto's into programs without. The first one adds temporary variables
and the second adds logical variables to the program. The first method
replicates code in normalizing reducible flowgraphs, and both methods result in
loops with multiple exits.
Baker [12] concentrates on making programs more understandable rather
than on eliminating the goto statements entirely. Some goto statements are
generated when they give a clearer description of the control-flow. Some syntactic
restrictions are imposed upon the input program as well. The algorithm
is divided in two steps: locating the loops in the flowgraph and adding branching
statements. The first step uses the classical notion of dominators [2] after
building the depth-first spanning tree of the flowgraph. The second step of the
algorithm adds branching statements to the basic form of the program generated
in the first step. The algorithm can be extended to handle irreducible graphs.
The shortcomings of Baker's method are first, that some goto's remain, second,
the loops may be left with multiple exits, and third that the number of control
forms is greater than with our method, so that the resultant syntax is still fairly
complex.
Allen and Kennedy's method for converting control dependences to data
dependences is called if conversion [5]. The primary goal of this transformation
is to transform programs for the purpose of vectorization. It takes every do
loop of a program and transforms each of its statement into a guarded one.
Beyond this goal, this transformation may be useful in applications such as
code structuring and goto elimination. If conversion is performed in three
steps. The first step analyzes the branches in the code, classifying them as
GOTO 300
200

Figure

26: A Program with no cycles
either exit branches, backward branches or forward branches. The second step
is branch relocation and the last step is branch removal. An exit branch is
defined to be one that terminates a loop. A forward branch is defined to be one
whose target is at the same loop nesting level, and which precedes the target
(lexically). A backward branch is defined to be one whose target is at the same
loop nesting level, and which follows the target (lexically). Branch relocation
moves a branch out of a loop until the branch and its target are at the same
loop nest level. Branch removal eliminates forward branches by attaching guard
expressions to targets.
If conversion has goals similar to our normalization method. Its shortcomings
are presented below along with differences between it and our work. The
examples that are used below are taken from Allen and Kennedy's paper [5] and
are written in a Fortran-like syntax. The normalized forms are also written in
this same syntax in order to make the differences more apparent.
The first problem with if conversion is that backward branches are improperly
identified as those whose targets precede them (lexically). Thus the
program in figure 26 is treated in the reference paper [5] as a cycle; the if
conversion algorithm detects GOTO 100 as being a backward branch. But if we
follow carefully the control-flow of the code, there is no loop in this program.
The program obtained after if conversion is in figure 27. With our method,
some factorization was performed since two different paths could be taken to
arrive to label 300. The final normalized form is shown in figure 28; it is written
in a Fortran-like syntax to facilitate the comparison.
The second problem with if conversion is its ad-hoc treatment of irreducible
programs. Let us take an example. The program in figure 29 is transformed
after if conversion into the program of figure 30. A boolean variable is used
to record which branches are taken to reach statements in the loop body. The
resulting program contains a goto, and the cycle of control-flow has not been replaced
by a structured loop. A subsequent transformation (not described in the
reference paper [5]) must be used to replace this backward branch by a while
loop. By contrast, our method produces the program of figure 31, using a uniform
treatment of reducible and irreducible flowgraphs (since the flowgraph is
irreducible, there is some code replication). Notice that if conversion has introduced
an additional loop-carried dependence (on the variable BB1) that is not
/* GOTO 300 has been eliminated */
200 IF (.NOT. BB1 .AND. BR1) S2
IF (.NOT. BB1 .AND. BR1 .AND. Y) THEN
GOTO 100

Figure

27: The Program of figure 26 after if conversion
IF PRED-162 THEN
IF (.NOT. (PRED-162 .AND.PRED-164. Y))) S1

Figure

28: Normalized form of the program in figure 26
present in the program of figure 31. This dependence may inhibit parallelization
of the loop.
The third problem with if conversion is the extra generation of boolean
expressions guarding each statement of the program. The program in figure
is equivalent after if conversion to the one in figure 33. Now, if we look at the
normalized form in figure 34 corresponding to the the program in figure 32, we
can see that in the latter form, a straightforward dataflow analysis would be
more accurate for two reasons. First, the statement 5 is not
guarded by any condition, and therefore we may easily conclude that it is the
only definition of the array B that reaches out of the program. Whereas the
program in figure 33 necessitates a deeper analysis that accounts for boolean
guards to arrive at the same conclusion. Second, it is very easy to see from the
control structure of the program in figure 34 that the definition of the variable
X in statement (2) is reached only by the (last) definition on the statement (1)
200

Figure

29: Example of an irreducible code
200
IF (Y) THEN
GOTO 100

Figure

30: If conversion of the program in figure 29
IF PRED-50 THEN
IF (.NOT. PRED-50 .AND.NOT. PRED-52))
REPEAT
UNTIL PRED-52

Figure

Normalized form of the program in figure 29

Figure

Reachable uses
IF (.NOT. BR1)
IF (.NOT. BR1)
IF (.NOT. BR1)
IF ((.NOT. BR1) .AND.(NOT. BR2))
.OR.NOT. BR1 .AND.NOT. BR2))

Figure

33: If conversion of the program in figure
and not by any previous definitions of X. Again, in the if converted code, a
deeper analysis is necessary and perhaps a conservative decision would have to
be taken.
7 Related Application of the Gaussian Elimination-
like Method
There are several problems closely related to control-flow normalization that
make use of Gaussian elimination resolution. These include global flow analysis
[19, 20], shortest path problems [15, 18, 26] and conversion of finite automata
to regular expressions [41]. The fundamental framework of these problems is to
build a system of equations based on regions of a flowgraph and to solve this system
using the Gaussian resolution. In the following we give an overview of some
methods: Allen and Cocke's interval analysis, Hecht and Ullman's analysis, Tar-
jan's interval analysis, and finally Graham and Wegman's analysis. The latter
three are improvements to the first one. In the literature these algorithms are
IF (.NOT. PRED-20) THEN
IF (.NOT. PRED-22)
IF (.NOT.NOT. PRED-20) .AND. PRED-22))

Figure

34: Normalized form of the program in figure
called elimination algorithms. Ryder and Paull present a comparison of these
four algorithms [38]. They are, in general, described for a specific implementa-
tion, and therefore it is difficult to see their common points and differences. Our
goal is to give a presentation of these algorithms describing their complexity and
performances.
We want to emphasize that the following four algorithms are not methods
for program normalization, but rather, are presented to show the reader that the
Gaussian elimination-like solution of systems is widely used in similar problems
and that several improvements of its complexity have been studied. These
algorithms are used for global dataflow analysis. e represents the number of
edges in the flowgraph and is assumed to be in order O(n), where n in the
number of nodes of the flowgraph.
7.1 Allen and Cocke Method
This method, known as Interval Analysis, was introduced by Allen and Cocke
[35]. It does not treat irreducible graphs, but it can be adjusted to handle
them. The equations it uses are quite different from ours. They represent the
dataflow equations of the program. They describe the reaching definitions of
each variable of the program [4, 38]. The Allen and Cocke algorithm consists
of the iteration of three phases: a partitioning algorithm that finds single entry
regions in the dependency graph, elimination of the dataflow equations, and
finally propagation.
The elimination process turns out to be the application of successive substitution
and loop-breaking transformations. The latter transformation is equivalent
to the derecursivation transformation we have described earlier in the paper.
The unknowns of the system are eliminated in the natural order in which each
node of the graph is added to an interval.
During propagation, back-substitutions are performed to propagate global
dataflow side effects to the regions where they apply. It consists of finding
variable correspondences and substituting interval head variables solutions into
reduced equations. The process of reducing the system into a smaller one produces
an O(n 2 ) solution.
7.2 Hecht and Ullman Method
This algorithm is also applicable only to reducible graphs. It takes as input
a system of equations analogous to the one described in the Allen and Cocke
algorithm, and its dependency graph (i.e., the control flowgraph). The elimination
process is directed by the region of the graph, much as the Allen and
Cocke algorithm, and consists of applying the transformations T 1 and T 2 , as
described in the paper earlier, to these regions. The search for common factors
in the reduced equations allows a saving in the calculation [1, 37, 46]. This
improvement provides a complexity of O(n log n) rather than a O(n 2 ) Allen and
Cocke's complexity.
7.3 Tarjan Method
The Tarjan method uses a different notion of intervals from the above methods;
in a sense they represent the loops in the control flowgraph. When calculating
these intervals an implicit order arises, as in the Allen and Cocke method. This
order will be used to calculate the reduced equations. It is clear that this order
will follow one of the depth-first orders of the graph. The resolution like Hecht's
method is based upon the T 1 and T 2 transformations as shown above, and T 3
transformation that is the composition of the two previous ones. Again this
method is applied to reducible flowgraphs. For such a graph the algorithm
requires a time of O(nff(n)) where ff is the inverse of Ackerman's function. A
simpler algorithm that runs in O(n log n) exists [43].
7.4 Graham and Wegman Method
This algorithm is close to Tarjan's interval analysis; but it handles irreducible
graphs without the need for eliminating the irreducibility. The notion of intervals
is called here S-sets [19]. They represent the loops in the flowgraph.
The S-sets are defined by a numbering of the nodes of the dependency graph
associated with the equations; this numbering is performed using a depth-first
order. The elimination process is performed using three transformations similar
to those of the Hecht and Ullman algorithm named S 1 , S 2 and S 3 . The
application of these transformations is restricted to nodes that have only one
predecessor. S 1 as T 1 consists of loop-breaking (derecursivation in our frame-
work). S 2 consists of a substitution of a node that has several successors. Then
transformations are necessary to eliminate a node that has k successors.
The substitution is performed the same way as in the Hecht and Ullman algo-
rithm: each term is substituted successively, rather than substituting the entire
right hand side of an equation at once, such as in the Allen and Cocke algorithm.
Finally, S 3 eliminates a node that has no successors. This algorithm runs in a
time O(n log n).
7.5 Conclusion
All the algorithms we have presented are refinement to a Gaussian elimination-
like algorithm. There are two relationships between the work described above
and ours. First, each of the above methods uses a Gaussian elimination method
that is similar in some respects to ours. Second, each of them solves a dataflow
analysis problem, and much of the difficulty of doing so comes from the irregular
structure of the underlying control flowgraph. Using a method like ours, this
structure can be made more regular, with the result that the analysis algorithm
is made simpler; the normalization of a program anticipates much of the computation
of dataflow solutions for the program, so solving a dataflow problem can
be much more efficient. Further, the normalization process is performed once on
the program, but the simplifications affect both forward and backward dataflow
problems to be solved for the program. This is because the backward flowgraph
of a normalized program is also normalized, whereas a flowgraph that is merely
structured, may be unstructured when its edges are reversed. Finally, even
though closures may still be required for loops, especially for non-fast problems
[19, 43], these will be simpler than for a non-normalized program.
8 Conclusion
In this paper we have presented an algebraic framework for normalization of
control-flow. This framework has made it easy for us to prove that our transformations
preserve the semantics of programs. It is applicable to a variety of
languages and is more powerful than existing methods in several respects.
First, in methods based upon node-splitting [12], and if conversion [5], some
branching instructions remain after transformations, and code replication may
occur even when normalizing programs whose flowgraphs are reducible. Our
method eliminates all branching instructions and replicates code only when
eliminating irreducibility, a rare condition even in unstructured programs.
Second, while previous methods result in programs with reducible flow-
graphs, our method yields programs whose control flowgraphs are more highly
structured yet; in particular, all control-flow cycles are normalized into single-
entry, single-exit while loops. Such loops may be further transformed into
conventional do loops by induction variable recognition [6, 9]. This makes our
method particularly helpful in automatic parallelization, where highly regular
loop structures are essential [32], [22]. It simplifies both forward and backward
dataflow analyses by transforming a program to one with an obvious, trivial
internal structure.
Third, our method makes the separate representation of control dependences
unnecessary. In a program normalized by our method, control dependences are,
in effect, represented directly by the syntax tree since each conditional structure
contains all the expressions it controls. Since the analysis of control dependences
is central to the work of parallelizing programs [3], this is a significant simplification

This work has been implemented in PAF [44], a parallelizer of Fortran programs
written at the University of Paris 6, and in MIPRAC, a multilingual
parallelizer of programs at the University of Illinois. In Miprac, we measured
on a handful of examples, that the ratio of the total normalization time to the total
compilation time is approximately 0:02. The total compilation time includes
parsing, normalization, interprocedural analysis, intraprocedural dataflow analysis
and some restructuring. The average compilation time for these examples
was 18.5 seconds. We expect for the ratio to decrease when the time measure
will take into account additional passes of Miprac that are currently being
implemented.

Acknowledgments

I wish to thank Luddy Harrison for his helpful ideas and suggestions to
improve this paper. I also thank the anonymous referees for their comments on
earlier drafts of this paper.



--R

The Design and Analysis of Computer Algorithms.
The Theory of Parsing
An overview of the ptran analysis system for multiprocessing.
A program data flow analysis procedure.
Conversion of control dependence to data dependence.
Restructuration des Programmes Fortran en Vue de leur Parallelisation.
Normalization of program control flow.
A control-flow normalization algorithm and its complex- ity

The translation of 'goto' programs to 'while' programs.
Translating program schemas to while-schemas
An algorithm for structuring flowgraphs.
Flow diagrams

An algebra for network routing problems.

The kaps-1: An advanced source-to-source vectorizer for the s-1 mark iia supercomputer
Shortest path.
Fast and usually linear algorithm for global flow analysis.
Flow Analysis of Computer Programs.





Efficient algorithms for shortest paths in sparse networks.
Structured programming with goto statements.
Notes on avoiding go to statements.
The structure of an advanced vectorized for pipelined processors.
Proving algorithms by tail functions.
The mathematical semantics of algol 60.
Advanced compiler optimizations for super- computers
On the capabilities of while
Perfect club report.

Combinatorial Algorithms - Theory and Practice
Incremental data flow analysis based on a unified model of elimination algorithms.
Elimination algorithms for data flow analysis.
A denotational Semantics of CLU.
Denotational Semantics.
Representation of events in nerve nets and finite automata.
Denotational Semantics: The Schott-Strachey Approach to Programming Language Theory
Fast algorithms for solving path problems.
Paf: un paralleliseur automatique pour fortran.
The denotational semantics of programming languages.
Fast algorithms for the elimination of common subexpres- sions
Conversion of unstructured flow diagrams to structured.
Optimizing Supercompilers for Supercomputers.
--TR
Advanced compiler optimizations for supercomputers
Elimination algorithms for data flow analysis
Automatic recognition of induction variables and recurrence relations by abstract interpretation
A Fast and Usually Linear Algorithm for Global Flow Analysis
Efficient Algorithms for Shortest Paths in Sparse Networks
An Algorithm for Structuring Flowgraphs
Fast Algorithms for Solving Path Problems
Structured Programming with <italic>go to</italic> Statements
A program data flow analysis procedure
The denotational semantics of programming languages
On the capabilities of while, repeat, and exit statements
Flow diagrams, turing machines and languages with only two formation rules
Algorithm 97: Shortest path
Denotational Semantics
Flow Analysis of Computer Programs
Incremental data flow analysis
Conversion of control dependence to data dependence
Theory of Parsing, Translation and Compiling
The Design of Automatic Parallelizers for Symbolic and Numeric Programs
An optimizing compiler for lexically scoped LISP
A DENOTATIONAL SEMANTICS OF CLU
Optimizing supercompilers for supercomputers

--CTR
J. A. Bergstra , T. B. Dinesh , J. Field , J. Heering, Toward a complete transformational toolkit for compilers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.19 n.5, p.639-684, Sept. 1997
Fubo Zhang , Erik H. D'Hollander, Using Hammock Graphs to Structure Programs, IEEE Transactions on Software Engineering, v.30 n.4, p.231-245, April 2004
M. G. J. van den Brand , P. Klint , C. Verhoef, Reverse engineering and system renovationan annotated bibliography, ACM SIGSOFT Software Engineering Notes, v.22 n.1, p.57-68, Jan. 1997
Todd A. Proebsting , Scott A. Watterson, Krakatoa: decompilation in java (dose bytecode reveal source?), Proceedings of the 3rd conference on USENIX Conference on Object-Oriented Technologies (COOTS), p.14-14, June 16-20, 1997, Portland, Oregon
Johan Janssen , Henk Corporaal, Making graphs reducible with controlled node splitting, ACM Transactions on Programming Languages and Systems (TOPLAS), v.19 n.6, p.1031-1052, Nov. 1997
Larry Carter , Jeanne Ferrante , Clark Thomborson, Folklore confirmed: reducible flow graphs are exponentially larger, ACM SIGPLAN Notices, v.38 n.1, p.106-114, January
Baowen Xu , Ju Qian , Xiaofang Zhang , Zhongqiang Wu , Lin Chen, A brief survey of program slicing, ACM SIGSOFT Software Engineering Notes, v.30 n.2, March 2005
Peng Zhao , Jos Nelson Amaral, Ablego: a function outlining and partial inlining framework: Research Articles, SoftwarePractice & Experience, v.37 n.5, p.465-491, April 2007
J. Koehler , R. Hauser , S. Sendall , M. Wahler, Declarative techniques for model-driven business process integration, IBM Systems Journal, v.44 n.1, p.47-65, January 2005
node-splitting techniques;parallel algorithms;automatic parallelization;control dependence relations;control flowgraphs;complexity;graph theory;control-flow cycles;computational complexity;syntax tree;GOTOs;structured programming;control-flow normalization algorithm