第1页 / 共40页
第2页 / 共40页
第3页 / 共40页
第4页 / 共40页
第5页 / 共40页
第6页 / 共40页
第7页 / 共40页
第8页 / 共40页
一篇很好关于编译原理的论文.pdf
Efficiently Computing Static Single
Assignment Form and the Control
Dependence Graph
JEANNE FERRANTE,
RON CYTRON,
MARK N. WEGMAN
IBM Research Division
BARRY K. ROSEN,
and
and
F. KENNETH ZADECK
Brown University
influence
compilers,
optimization
to the point
data structure
flow propertiee
choices directly
the power and efficiency
program optimization.
that
A poor choice of data structure
advanced
features
In optimizing
practical
compilation
static single assignment
data flow and control
lends efficiency
structures
discouraged their use. We present new algorithms
for arbitrary
flow graphs. The algorithms
may have other applications. We also give analytical
data structures
strong evidence that
of
or slow
Recently,
form and the control dependence graph have been proposed to represent
techniques
these
and their
size have
compute these data structures
frontiers,
that
evidence that all of these
This paper
thus presents
construction
that efficiently
use dominance
can inhibit
become undesirable.
of programs. Each of these previously
and experimental
program.
class of program optimization.
to a useful
the difficulty
in the size of the original
use in optimization.
can be of practical
these structures
a new concept
are attractive,
optimization
are usually
and power
unrelated
Although
both of
potential
of
their
control
linear
Categories
and
Constructs—control
D.3.4
Manipulation]:
Programming-program
[Programming
transformation
Subject
Descriptors:
D .3.3
[Programming
structures;
data types and structures;
procedures,
Languages]:
functions
Language
and subroutines;
Languages]:
Algorithms—analysis
Processors—compilers;
of algorithms;
1.2.2 [Artificial
optimization;
I. 1.2
Intelligence]:
[Algebraic
Automatic
Languages
(Jan. 1989).
of Computing
ac!drwses: R. i3yiru:I,
“An Efficient Method
version of this paper,
supported by the IBM Corporation,
the 16th ACM Symposium on principles
Static Single Assign-
of
A preliminary
ment Form, ” appeared in the conference Record of
Programming
F. K. Zadeck’s work on this paper was partially
the office of
Naval Research, and the Defense Advanced Research Projects Agency under contract NOCIO14-83-
K-0146 and ARPA order 6320, Amendment
Authors’
J. Ferrante,
IBM Research Division,
cal Sciences Department,
F. K. Zadeck, Computer Science Department,
02912.
Permission
not made or distributed
of the publication
Association
specific permission.
@ 1991 ACM 0164-0925/91/1000-0451
1.
and M. N. Wegman, Computer Sciences Department,
Heights, NY 10598; B. K. Rosen, Mathemati-
P. O. Box 218, Yorktown
the copies are
notice and the title
of the
a fee and/or
fee all or part of this material
advantage,
P. O. Box 704, Yorktown
IBM Research Division,
is granted provided that
the ACM copyright
and its date appear, and notice is given that
Heights, NY 10598;
Providence, RI
P.O. Box 1910, Brown University,
for Computing Machinery.
copying is by permission
for direct commercial
To copy otherwise,
to copy without
or to republish,
requires
$01.50
ACM Transact~ons on Programmmg Languages and Systems, VO1 13, NO 4, October,
le91, Pages 451.490
Static Single Assignment Form and the Control Dependence Graph
.
453
Orlgmal
Intermediate
Code
Opt Imlzed
Intermediate
Code
J
P()+P~+P~-+
T
. . . Pn
Fig, 1. Vertical
arrows represent
arrows represent
optimizations,
translation
to/from static single assignment
form, Horizontal
V+4
+-V+5
V+-6
--V+7
VI-4
V2*6
+ vi
+5
+-- V2
+7
Fig. 2.
Straight-line
code and its single assignment
version.
if
P
then
else
V -
4
V +- 6
/*
IJse V several
times.
*/
if
P
then
else
VI
+
V2 +
4
6
v~ e- q5(vf, V2)
/* Use V~ several
tines.
*/
Fig.3.
if-then-else
anditssingle
assignment
version.
to the @-function
indicate
Subsequent
uses of V become
by new variables
one assignment
program.
This
to Vi.
simplifies
Vl, Vz, V3,
Indeed,
there
operands
point.
replaced
just
entire
An especially
the next
clear
subsection
example
sketches
is constant
this
application.
to V reach
assignments
which
uses of V3. The old variable
...,
and each use of Vi
one assignment
is only
thle join
V is thus
by
in the
is reached
to Vi
the record
keeping
propagation
for several
optirnizations.
based on SSA form [501;
1.1 Constant
Propagation
3. The else branch
use of Q tells
includes
a compiler
If Q is the constant
to this
true
to the join point.
a
point
are really
uses of
account
without
to understand
the constant
but
4.
the
SSA form,
SSA form,
[49]. With
elaborate
version
of Figure
4 is a more
the else branch
Figure
test of Q, and propagating
that
true,
Such
processing
the algorithm
then
possibilities
is either
can
costly
never
all uses of V after
is fast and simple.
the constant
falls
through
the join
into
be taken
[48] or difficult
Initially,
the algorithm
assumes
followed
unknown
assumptions
that
variable
at
run
value
time)
(denoted
and
that
T). Worklists
they
until
that
each
each edge is unexecutable
variable
are initialized
with
appropriately,
is constant
(i. e., never
an as-yet
and the
finds
of
branch
are corrected
P is not constant
stabilize.
Suppose
_L) and, hence,
the algorithm
that
either
(denoted
ACM Transactions
on Programming
Languages
and Systems, Vol. 13. No. 4, October
1991.
454
.
Ron Cytron et al
if
P
then
do V +-
end
else
do V +
4
6
if
P
then
else
+- 4
do Vi
end
do V2 +- 6
if Q then
return
if
Q then
return
end
. . . +V+5
end
4(V1,
V3 +
. . . +- V3+S
V2)
Fig
4,
Example
ofconstant
propagation
conditional
and the
may betaken.
statements
are notified
value,
that
the assumption
they
to the
4with
combines
thanks
isassociated
with
the inedge
The outedges
of
the test ofP are marked
reach
they
VI
about
are uses of4.
is changed
(Each
single
Vz. The
of
assignment
second
thejoin
are processed. When
VI +4
is
from T to 4, and all uses of
a use of
use ofVl
the
property.)
of
how-
is indeed
In
particular,
the @function,
corresponds
to falling
that
operand
point
the else branch.
So long as this
edge is considered
uses T for
the
second
operand,
no matter
about
Vz. Combining
4 with
T yields
4,
unexecutable,
is currently
of V~ are
what
so uses
the
as-
assumed
to be uses of 4. Eventually,
the assumption
from T to a known
lead to the discovery
constant
or
that
the
and then
the 6 at Vz combines
to true
would
have
no effect
to
second
with
on the
~ . A change
inedge
of
the 4 at VI
assumption
to either
the join
to yield
on the other
hand, would
propagation
two different
of
They would
algorithms,
constants
thus
decide
sketched
The algorithm
just
the outer
executable,
processed,
VI
this
@function
ever,
through
algorithm
sumed
tentatively
change
would
followed,
change
constant
ments
point.
[501, but
particular,
variable
efficiently.
possible
linear
in
essentially
still
about Q may
L
can be
at V~. A
point
false
or
L
at V3. Traditional
see that
all uses after
these uses.
at
the SSA program
the original
a +-function
how to obtain
nonlinear
behavior
assign-
the join
program.
it sees
In
for
every
SSA form
is still
is typically
to V seem to “reach”
that V is not constant
is linear
in the size of
in the size of
to place
inefficient
paper
This
shows
this
size might
be nonlinear
it would
be safe but
at every
join
point.
but
is unlikely
of
size
in practice.
the
original
in the SSA size.
the
linear
When
~-functions
are placed
carefully,
The size of
program;
the SSA program
the
time
to
do the work
is
1.2 Where
to Place @-Functions
glance,
careful
placement
might
seem to require
the enumeration
of
two
first
At
pairs
are
intrinsically
nance
ties to later
fi-ontier
of assignment
statements
assignments
for each variable.
reach
a common
to V that
In fact,
nonlinear.
however,
of each node in the control
is enough
it
flow graph.
sections, we sketch
the method
here.
Checking
point might
to look
whether
there
seem to be
at
the
domi-
Leaving
the technicali-
ACM Transactions
on Programming
Languages
and Systems, Vol
13, No 4, October
1991
Static Single Assignment Form and the Control Dependence Graph
.
455
Suppose
that
a variable
use of V will
the
X be the basic
or a use of
to V. Let
V has just
be either
VI
value
one assignment
a use of
from the most
the value
recent
block
of code that
the value
of V when
along
entered
control
X + Y,
along
flows
the code in Y will
Y. When
by V..
If Y # X, but
case X is said to strictly
all paths
dominate
to Y must
Y),
go through
the code in Y will
still
node
any
dominated
from X it may be. Eventually,
strictly
a node Z not
strictly
dominated
Z sees VI
so that
Then
of a @-function
along
Z is said to be in
for V.
then
by X will
however,
by X. Suppose
one inedge
dominance
general,
the
In
in the original
program,
V.
assigns
at entry
execution
to the
the
of
to V, so X
any edge X + 1{ to a
see VI and be
X (in
a [ways
no
control may be able
such
along
of X and is
how many
how
Z is the first
see V.
and no matter
see Vl,
always
but may
frontier
no matter
any
determine
so that
program
assignment
will
basic block
unaffected
which
see VI.
matter
to reach
node on a path,
inedge.
another
clearly
in
need
assignments
complex
the dominance
frontier
Indeed,
how far
of every
to V may
appear
flow may
in the
original
be, we can place
program
~-functions
the control
frontier
of every
node that
assigns
to V,
then
node where
a +-function
has already
been placed,
The same concept
also be used to compute
conditions
dependent
statement
skipped.
optimization,
affecting
on a branch
to execute
information
Such
and program
of dominance
control
frontiers
dependence
used for computing
[20, 24], which
statement
execution.
Informally,
if one edge from the
branch
while
another
is vital
analysis
edge
can
for detection
[28].
for V by finding
the dominance
and so on.
SSA form can
those
identify
is control
that
causes
a statement
definitely
the
cause
of parallelism
statement
to be
[2], program
1.3 Outline
of
the Rest of
the Paper
2 reviews
3 explains
Section
Section
also considers
adjusted
concept
SSA form (Section
Section
7 explains
algorithms
structures.
experiments
rithms
presents
and time
with
representation
the
SSA form and sketches
of control
variants
to deal with
and formalizes
of SSA form as defined
these
variants.
Section
dominance
frontiers.
how to construct
here. Our
flow by a directed
it. This
graph,
section
can be
tree
Then we show how to compute
4 reviews
dominator
algorithm
the
are linear
We also give evidence
in the
5) and the control
how to translate
dependence
graph
(Section
6) efficiently.
out of SSA form. Section
8 shows that
size of programs
restricted
to certain
our
control
FORTRAN
programs.
of general
linear
Section
behavior
9 summarizes
bounds,
compares
our
technique
with
other
by reporting
the
techniques,
on
algo-
and
some conclusions.
2. CONTROL
FLOW GRAPHS
leaves
statements
The
basic blocks, where
and
indicated
jZow graph
and two additional
the
of a program
are organized
program
block
flow enters
at
last
its
basic
into
a basic
statement
(not
block
necessarily
its first
at
[1, 36]. Basic
maximal)
statement
blocks
are
by the column
is a directed
of numbers
graph whose
in parentheses
in Figure
nodes are the basic blocks
5. A control
of a program
nodes, Entry
and Exit.
There
is an edge from Entry
to
ACM Transactions
on Programming
Languages
and Systems, Vol. 13, No, 4, October
1991
456
.
Ron Cytron
et al.
I
1+1
J+
K+l
L+-1
repeat
if
(P)
then
do
J-
if
I
(Q)
then
else
K-K+
2
3
L t
L -
I
end
else
KtK+2
J,K, L)
(I,
(R)
then
(S)
L +- L + 4
print
repeat
if
until
1-1+6
until
(T)
(1)
(1)
(1)
(1)
(2)
(2)
(3)
(3)
(3)
(4)
(5)
(6)
(6)
(7)
(8)
(9)
(9)
(10)
(11)
(12)
(12)
49
10
11
@IEl--&
Fig
5
Simple pro~amand
itscontrol
flow graph
the program
that
can exit
dependence
The
to Exit.
and there
For
can be entered,
the program.
reasons
in Section
graph
the
the basic blocks. We assume
and explained
other
edges
of
is an edge to
to
is
related
6,
there
represent
that
of control
from any basic block
at which
any basic block
Exit
the representation
also an edge from Entry
transfers
of control
node is on a path
successor
SZLCC(X)
with more
predecessor
assignment
when
that
control
For
of X is any
is the set of all
of
nonnegative
is a join
in Entry
the program
flow graph
explicitly
appear
than
any
of
e,,
sequence
(denoted
1< j < J.
(node
J + 1 nodes
. . . . eJ)
(We write
or edge) may
(jumps)
between
from Entry
node
successors
and on a path
Y with
an edge
to Exit.
For
X + Y in
one successor
of X;
is a branch
similarly
node;
for predecessors.
a node with more
node.
Finally,
to represent
is entered.
This
each variable
whatever
assignment
in the code. Throughout
value
the
is treated
this
paper,
is considered
variable
graph,
each
each node X, a
and
the
A node
one
an
have
the ones
the
to have
may
just
CFG denotes
than
like
the program
under
integer
J, a path
discussion.
length
of
J in CFG consists
(denoted
Xo,
runs
., XJ)
from
and a sequence
for
XJ_,
to X,
of
all
e,
that
such
eJ: X~_l ~ X~. ) As is usual with
occur
several
times.
The
null
sequences,
with
path,
of a
J edges
j with
one item
J = O,
is
ACM Transactions on Programmmg
Languages and Systems, Vol 13, No 4, October
1991
458
0
Ron Cytron et al.
I
1-1
J+
Kti
L+-1
repeat
+-1
+-l
11-1
Jl
Kl
L1tl
repeat
#(13,11)
-
- @(J4, JI)
12
J2
K2 +
if
(P)
then
do
J+
if
I
(Q)
then
else
L +-- 2
L +--- 3
K-K+
I
end
else
K+--K+2
(I,
J,K, L)
L+-L+4
(R)
then
(S)
print
repeat
if
until
1+1+6
until
(T)
L2
if
+-
(P)
then
end
else
-
J4
-
K5
L6
+
print(12,
repeat
L7
if
L9
until
13-12+6
(T)
until
l#J(K~,K~)
4(L9, L1)
12
do
-
(Q)
then
else
L3
L4
t
2
+- 3
@(L3, L4)
-
+K2+1
J3
if
L5
K3
K2+2
K4
+-
#( J3, J2)
@(K3, K4)
~(L2,L~)
J4, K5, L6)
+- @(L~,L~)
(R)
then
+ @(L8, L7)
(S)
L8
-L7+4
Fig.6
Simple program anditsSSAform.
predecessor.
supportl
@(R, S,...)
qifunction
of control
the ordinary
are useful
Ifcontrol
remembers
is just
uses only
just
before
reaches
value
J“ while
the
one ofthe
entering
Xfromits
executing
the
operands,
X. Any
of
jth
predecessor,
then
the run-time
the
jth
o-functions
operand.
in X. The value
Each
execution
of
of a
but which
d-functions
one depends
in X are executed
statements
for special
in X. Some variants
For example,
purposes.
of d-functions
each @function
on the flow
before
here
can be tagged
as defined
this
support.
lWhen SSA form is used only as an intermediate
provide
correctness
ending with
another
has no +-functions,
incidentally
code that
that
the semantics
intermediate
parameter
For us,
of
steps in a sequence of program transformations
beginning
Others
[6, 11, 521 have found it useful
to give @
encodes j, under
various
restrictions
on the control
flow.
form (Figure
of @ are only
1), there is no need actually
assessing
important
when
to
the
and
ACM Transactions
on Programming
Languages
and Systems, Vol. 13, No 4, October
1991
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
