Optimization Under the Perspective of Soundness, Completeness, and Reusability - Correct System Design: Recent Insights and Advances - page 300

The impact on the reusability of the as-early-as-possible placing strategy,
however, is setting-dependent. While for semantic PRE only completeness is af-
fected, 11 in the interprocedural and explicitly parallel setting even soundness is
aected for the less ambitious syntactic PRE. Interprocedurally, in its strong, ex-
plicitly parallel, even in its weak variant. This directly shows that the successful
extension of the analyses computing the properties involved in the as-early-as-
possible placing strategy is a necessary, however, not a sucient condition for
its transferrability. In fact, on the transformation level setting and paradigm
specic adaptations are required in order to accommodate their specics. In the
following section we will discuss this by means of the interprocedural and the
explicitly parallel setting.
Remedies: Adaptations of the Placing Strategy. Essentially, there are
two general ways for coping with the problems showing up with the as-early-as-
possible placing strategy in advanced settings. First, dropping generality of the
transformation while preserving computational optimality for a subset of pro-
grams; second, dropping computational optimality while preserving generality
of the transformation. In practice both ways have been taken.
Starting with IPRE, in [14] the rst way has been taken. The application
of the ISE-transformation is restricted to programs where the program it pro-
duces obeys a canonicity constraint. Intraprocedurally, this constraint holds for
every program subjected to the SE-transformation. Intuitively, it requires that
insertions are used on every program continuation (note that this constraint is
violated in the example of Figure 6!). Canonicity is quite a natural constraint,
and can easily be checked. Moreover, it characterizes a situation met by a large
class of interprocedural programs, where there is no dierence to the intrapro-
cedural setting.
In [33] the second way has been taken. The motion of computations is heuris-
tically limited in order to avoid anomalies of the transformation. This way, gen-
erality of the transformation is preserved. However, heuristics are often overly
restrictive, and unnecessarily reduce the transformational power of an algorithm
based on them. As discussed in [14] this also applies to the heuristics controlling
the IPRE-transformation proposed in [33].
Considering now PPRE, in [27] the second way has been taken. Intuitively,
the motion of computations from parallel program parts, where they are possi-
bly for free, to sequential program parts, where they denitely count, is limited
to situations, where occurrences of the computation under consideration are re-
moved from every component of a parallel statement. 12 This guarantees that also
the \bottleneck" component is improved. The modications required to achieve
this behaviour are actually limited to the treatment of synchronization of par-
allel components. They can completely be hidden inside the generic algorithm
computing the xed point solution of a DFA problem (cf. [27]). The nal trans-
11 In particular, for semantic PRE a dierence between \motion"-based and \place-
ment"-based PRE-techniques shows up (cf. [25]).
12 A similar modication has been used in [12] in order to avoid anomalies when ex-
tending partial dead-code elimination (cf. [22]) to the parallel setting.