Blame | Last modification | View Log | RSS feed
<!-- Crown Copyright (c) 1998 -->
<HTML>
<HEAD>
<TITLE>TDF transformations</TITLE>
</HEAD>
<BODY TEXT="#000000" BGCOLOR="#FFFFFF" LINK="#0000FF" VLINK="#400080" ALINK="#FF0000">
<A NAME=S83>
<H1>TDF Guide, Issue 4.0 </H1>
<A HREF="guide14.html">
<H3>January 1998</H3>
<IMG SRC="../images/next.gif" ALT="next section"></A>
<A HREF="guide12.html">
<IMG SRC="../images/prev.gif" ALT="previous section"></A>
<A HREF="guide1.html"><IMG SRC="../images/top.gif" ALT="current document"></A>
<A HREF="../index.html"><IMG SRC="../images/home.gif" ALT="TenDRA home page">
</A>
<IMG SRC="../images/no_index.gif" ALT="document index"><P>
<HR>
<DL>
<DT><A HREF="#S84"><B>11.1 </B> - Transformations as definitions</A><DD>
<DT><A HREF="#S85"><B>11.1.1 </B> - Examples of transformations</A><DD>
<DT><A HREF="#S86"><B>11.1.2 </B> - Programs with undefined values</A><DD>
</DL>
<HR>
<H1>11 <A NAME=0>TDF transformations</H1>
TDF to TDF transformations form the basis of most of the tools of
TDF, including translators. TDF has a rich set of easily performed
transformations; this is mainly due to its algebraic nature, the liberality
of its sequencing rules, and the ease with which one can introduce
new names over limited scopes. For example, a translator is always
free to transform:<P>
<PRE>
assign(e1, e2)
</PRE>
to:<P>
<PRE>
identify(empty, new_tag, e1, assign(obtain_tag(new_tag), e2))
</PRE>
i.e. identify the evaluation of the left-hand side of the assignment
with a new TAG and use that TAG as the left-hand operand of a new
assignment in the body of the identification. Note that the reverse
transformation is only valid if the evaluation of e1 does not side-effect
the evaluation of e2. A producer would have had to use the second
form if it wished to evaluate e1 before e2. The definition of assign
allows its operands to be evaluated in any order while identify insists
that the evaluation of its <I>definition</I> is conceptually complete
before starting on its<I> body</I>.<P>
Why would a translator wish to make the more complicated form from
the simpler one? This would usually depend on the particular forms
of e1 and e2 as well as the machine idioms available for implementing
the assignment. If, for example, the joint evaluation of e1 and e2
used more evaluation registers than is available, the transformation
is probably a good idea. It would not necessarily commit one to putting
the new tag value into the stack; some other more global criteria
might lead one to allocate it into a register disjoint from the evaluation
registers. In general, this kind of transformation is used to modify
the operands of TDF constructions so that the code-production phase
of the translator can just "churn the handle" knowing that
the operands are already in the correct form for the machine idioms.<P>
Transformations like this are also used to give optimisations which
are largely independent of the target architecture. In general, provided
that the sequencing rules are not violated, any EXP construction,
F(X), say, where X is some inner EXP, can be replaced by:<P>
<PRE>
identify(empty, new_tag, X, F(obtain_tag(new_tag))).
</PRE>
This includes the extraction of expressions which are constant over
a loop; if F was some repeat construction and one can show that the
EXP X is invariant over the repeat, the transformation does the constant
extraction.<P>
Most of the transformations performed by translators are of the above
form, but there are many others. Particular machine idioms might lead
to transformations like changing a test (i>=1) to (i>0) because
the test against zero is faster; replacing multiplication by a constant
integer by shifts and adds because multiplication is slow; and so
on. Target independent transformations include things like procedure
inlining and loop unrolling. Often these target independent transformations
can be profitably done in terms of the TOKENs of an LPI; loop unrolling
is an obvious example.<P>
<A NAME=S84>
<HR><H2>11.1. <A NAME=4>Transformations as definitions</H2>
As well being a vehicle for expressing optimisation, TDF transformations
can be used as the basis for defining TDF. In principle, if we were
to define all of the allowable transformations of the TDF constructions,
we would have a complete definition of TDF as the initial model of
the TDF algebra. This would be a fairly impracticable project, since
the totality of the rules including all the simple constructs would
be very unwieldy, difficult to check for inconsistencies and would
not add much illumination to the definition. However, knowledge of
allowable transformations of TDF can often answer questions of the
meaning of diverse constructs by relating them to a single construct.
What follows is an alphabet of generic transformations which can often
help to answer knotty questions. Here, E[X \ Y] denotes an EXP E with
all internal occurrences of X replaced by Y.<P>
<PRE>
If F is any non order-specifying
<A NAME=footnote79 HREF="footnote.html#79">*</A> EXP constructor and E is one of the EXP operands of F, then:
</PRE>
F(... , E, ...) xde identify(empty, newtag, E, F(... , obtain_tag(newtag),
...)) If E is a non side-effecting
<A NAME=footnote80 HREF="footnote.html#80">*</A>
EXP and none of the variables used in E are assigned to in B: identify(v,
tag, E, B) xde B[obtain_tag(tag) \ E] If all uses of tg in B are
of the form contents(shape(E), obtain_tag(tg)): variable(v, tg, E,
B) xde identify(v, nt, E, B[contents(shape(E), obtain_tag(tg)) \
obtain_tag(nt)]) sequence((S<I>1</I>, ... , S<I>n</I>), sequence((P<I>1</I>,
..., P<I>m</I>), R) xdb sequence((S<I>1</I>, ..., S<I>n</I>, P<I>1</I>,
..., P<I>m</I>), R) If S<I>i</I> = sequence((P<I>1</I>, ..., P<I>m</I>),
R) : sequence((S<I>1</I>, ... , S<I>n</I>), T) xdb sequence((S<I>1</I>,
..., S<I>i-1</I>, P<I>1</I>, ..., P<I>m</I>, R, S<I>i+1</I>, ...,
S<I>n</I>), T) E xdb sequence(( ), E) If D is either identify or
variable: D(v, tag, sequence((S<I>1</I>, ..., S<I>n</I>), R), B) xde
sequence((S<I>1</I>, ..., S<I>n</I>), D(v, tag, R, B) ) If S<I>i</I>
is an EXP BOTTOM , then: sequence((S<I>1</I>, S<I>2</I>, ... S<I>n</I>),
R) xde sequence((S<I>1</I>, ... S<I>i-1</I>), S<I>i</I>) If E is
an EXP BOTTOM, and if D is either identify or variable: D(v, tag,
E, B) xde E If S<I>i</I> is make_top(), then: sequence((S<I>1</I>,
S<I>2</I>, ... S<I>n</I>), R) xdb sequence((S<I>1</I>, ... S<I>i-1</I>,
S<I>i+1</I>, ...S<I>n</I>), R) If S<I>n</I> is an EXP TOP: sequence((S<I>1</I>,
... S<I>n</I>), make_top()) xdb sequence((S<I>1
</I>, ..., S<I>n-1</I>), S<I>n</I>) If E is an EXP TOP and E is not
side-effecting then E xde make_top() If C is some non order-specifying
and non side-effecting constructor, and S<I>i</I> is C(P<I>1</I>,...,
P<I>m</I>) where P<I>1..m</I> are the EXP operands of C: sequence((S<I>1</I>,
..., S<I>n</I>), R) xde sequence((S<I>1</I>, ..., S<I>i-1</I>, P<I>1</I>,
..., P<I>m</I>, S<I>i+1</I>, ..., S<I>n</I>), R) If none of the S<I>i</I>
use the label L: conditional(L, sequence((S<I>1</I>, ..., S<I>n</I>),
R), A) xde sequence((S<I>1</I>, ..., S<I>n</I>), conditional(L,
R, A)) If there are no uses of L in X
<A NAME=footnote81 HREF="footnote.html#81">*</A>:
conditional(L, X, Y) xde X conditional(L, E , goto(Z)) xde E[L \
Z] If EXP X contains no use of the LABEL L: conditional(L, conditional(M,
X, Y), Z) xde conditional(M, X, conditional(L, Y, Z)) repeat(L,
I, E) xde sequence( (I), repeat(L, make_top(), E)) repeat(L, make_top(),
E) xde conditional(Z, E[L \ Z], repeat(L, make_top(), E)) If there
are no uses of L in E: repeat(L, make_top(), sequence((S, E), make_top())
xde conditional(Z, S[L \ Z], repeat(L, make_top(), sequence((E,
S), make_top()) ) ) If f is a procedure defined
<A NAME=footnote82 HREF="footnote.html#82">*</A>
as: make_proc(rshape, formal<I>1..n</I>, vtg , B( return R<I>1</I>,
..., return R<I>m</I>)) where: formal<I>i</I> = make_tagshacc(s<I>i</I>,
v<I>i</I>, tg<I>i</I>) and B is an EXP with all of its internal return
constructors indicated parametrically then, if A<I>i</I> has SHAPE
s<I>i</I>
apply_proc(rshape, f, (A<I>1</I>, ... , A<I>n</I>), V) xde variable(
empty, newtag, make_value((rshape=BOTTOM)? TOP: rshape), labelled(
(L), variable(v<I>1</I>, tg<I>1</I>, A<I>1</I>, ... , variable(v<I>n</I>,
tg<I>n</I>, A<I>n</I>, variable(empty, vtg, V, B(sequence( assign(obtain_tag(newtag),
R<I>1</I>), goto(L)) , ... , sequence( assign(obtain_tag(newtag),
R<I>m</I>), goto(L)) ) ) ), contents(rshape, obtain_tag(newtag))
) ) assign(E, make_top()) xde sequence( (E), make_top()) contents(TOP,
E) xde sequence((E), make_top()) make_value(TOP) xde make_top()
component(s, contents(COMPOUND(S), E), D) xde contents(s, add_to_ptr(E,
D)) make_compound(S, ((E<I>1</I>, D<I>1</I>), ..., (E<I>n</I>, D<I>n</I>))
) xde variable(empty, nt, make_value(COMPOUND(S)), sequence( (
assign(add_to_ptr(obtain_tag(nt), D<I>1</I>), E<I>1</I>), ... ,
assign(add_to_ptr(obtain_tag(nt), D<I>n</I>), E<I>n</I>) ), contents(S,
obtain_tag(nt)) ) )
<A NAME=S85>
<H3>11.1.1. Examples of transformations</H3>
Any of these transformations may be performed by the TDF translators.
The most important is probably {A} which allows one to reduce all
of the EXP operands of suitable constructors to obtain_tags. The expansion
rules for identification, {G}, {H} and {I}, gives definition to complicated
operands as well as strangely formed ones, e.g. return(... return(X)...).
Rule {A} also illustrates neatly the lack of ordering constraints
on the evaluation of operands. For example, mult(et, exp1, exp2) could
be expanded by applications of {A} to either:<P>
<PRE>
identify(empty, t1, exp1,
identify(empty, t2, exp2, mult(et, obtain_tag(t1), obtain_tag(t2))) )
</PRE>
or:<P>
<PRE>
identify(empty, t2, exp2,
identify(empty, t1, exp1, mult(et, obtain_tag(t1), obtain_tag(t2))) )
</PRE>
Both orderings of the evaluations of exp1 and exp2 are acceptable,
regardless of any side-effects in them. There is no requirement that
both expansions should produce the same answer for the multiplications;
the only person who can say whether either result is "wrong"
is the person who specified the program.<P>
Many of these transformations often only come into play when some
previous transformation reveals some otherwise hidden information.
For example, after procedure in-lining given by {U} or loop un-rolling
given by {S}, a translator can often deduce the behaviour of a _test
constructor, replacing it by either a make_top or a goto. This may
allow one to apply either {J} or {H} to eliminate dead code in sequences
and in turn {N} or {P} to eliminate entire conditions and so on.<P>
Application of transformations can also give expansions which are
rather pathological in the sense that a producer is very unlikely
to form them. For example, a procedure which returns no result would
have result statements of the form return(make_top()). In-lining such
a procedure by {U} would have a form like:<P>
<PRE>
variable(empty, nt, make_shape(TOP),
labelled( (L),
... sequence((assign(obtain_tag(nt), make_top())),
goto(L)) ...
contents(TOP, obtain_tag(nt))
)
)
</PRE>
The rules {V}, {W} and {X} allow this to be replaced by:<P>
<PRE>
variable(empty, nt, make_top(),
labelled( (L),
... sequence((obtain_tag(nt)), goto(L)) ...
sequence((obtain_tag(nt)), make_top())
)
)
</PRE>
The obtain_tags can be eliminated by rule {M} and then the sequences
by {F}. Sucessive applications of {C} and {B} then give:<P>
<PRE>
labelled( (L),
... goto(L) ...
make_top()
)
</PRE>
<A NAME=S86>
<H3>11.1.2. Programs with undefined values</H3>
The definitions of most of the constructors in the TDF specification
are predicated by some conditions; if these conditions are not met
the effect and result of the constructor is not defined for all possible
platforms<A NAME=footnote83 HREF="footnote.html#83">*</A>. Any value
which is dependent on the effect or result of an undefined construction
is also undefined. This is not the same as saying that a program is
undefined if it can construct an undefined value - the dynamics of
the program might be such that the offending construction is never
obeyed.<P>
<P>
<HR>
<P><I>Part of the <A HREF="../index.html">TenDRA Web</A>.<BR>Crown
Copyright © 1998.</I></P>
</BODY>
</HTML>