Information Technology Reference
In-Depth Information
Structure of the Article.
After introducing our preliminaries in Section 2,
we recall in Section 3 the essence of intraprocedural PRE under the perspective
of soundness and completeness. Central are then Section 4, 5, and 6, where we
consider PRE in the interprocedural, explicitly parallel and the object-oriented
setting under the perspective of soundness and completeness, and particularly,
under the one of reusability. We will demonstrate that the rationale underlying
the SE-transformation leading to sound and complete PRE in the intraprocedu-
ral setting is generally not robust with respect to paradigm changes. In Section
7 we discuss in terms of safety properties the inherent reasons causing the miss-
ing robustness of this rationale, and how to cope with it on the analysis and
transformation level. In Section 8, nally, we present our conclusions.
2 Preliminaries
In optimization programs are commonly represented by directed
flow graphs
G
, and a unique
start node
s
and
end node
e
, which are assumed to have no incoming and outgoing edges, respec-
tively (cf. [8,34,35,36]). Following [17] we here consider
edge-labeled
flow graphs
G
=(
N; E;
s
;
e
)withnodeset
N
,edgeset
E
represent the elementary statements like assignments
of the underlying program, while the nodes represent program points (cf. Fig-
ure 1). Unlabeled edges are assumed to represent the empty statement \skip."
As usual, the control flow is interpreted nondeterministically in order to avoid
undecidabilities.
For a node
, i.e., the edges of
G
n
andanedge
e
of
G
,let
pred
(
n
)and
succ
(
n
) denote the set of all
immediate predecessors and successors of
n
, and let
source
(
e
)and
dest
(
e
)denote
the source node and the destination node of
e
.A
nite path
in
G
is a sequence
(
e
1
;:::;e
q
)ofedgessuchthat
dest
(
e
j
)=
source
(
e
j
+1
)for
j2f
1
;:::;q−
1
g
.Itis
a path from
m
to
n
,if
source
(
e
1
)=
m
and
dest
(
e
q
)=
n
. Additionally, let
P
[
m; n
]
denote the set of all nite paths from
.
Without loss of generality we assume that every node
m
to
n
n
of
G
lies on a path
from its entry
s
to its exit
e
,andthat
is free of
critical edges
, i.e., of edges
leading directly from a branch node to a join node.
3
Programs with procedures or procedures with parallel statements can be
represented in the same fashion by
flow graph systems
, where every procedure
is represented by a separate flow graph, and by
parallel flow graphs
,wherethe
components of a parallel statement are separated by two parallels as illustrated
by Figure 4 and Figure 7, respectively.
G
3 The Intraprocedural Setting
PRE has originally been developed for the
intraprocedural
setting (cf. [32]), which
can be considered the basic setting of program optimization (cf. [35]). Intrapro-
3
The impact of critical edges on code motion has been investigated in detail in [40].
Note that they can always be eliminated by edge splitting, i.e., by inserting a new
node on them.
Search WWH ::
Custom Search