Subversion Repositories tendra.SVN

Rev

Rev 2 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
2 7u83 1 
<!-- Crown Copyright (c) 1998 -->
2 
<HTML>
3 
<HEAD>
4 
<TITLE>TDF transformations</TITLE>
5 
</HEAD>
6 
<BODY TEXT="#000000" BGCOLOR="#FFFFFF" LINK="#0000FF" VLINK="#400080" ALINK="#FF0000">
7 
<A NAME=S83>
8 
<H1>TDF Guide, Issue 4.0 </H1>
9 
<A HREF="guide14.html">
10 
<H3>January 1998</H3>
11 
<IMG SRC="../images/next.gif" ALT="next section"></A>
12 
<A HREF="guide12.html">
13 
<IMG SRC="../images/prev.gif" ALT="previous section"></A>
14 
<A HREF="guide1.html"><IMG SRC="../images/top.gif" ALT="current document"></A>
15 
<A HREF="../index.html"><IMG SRC="../images/home.gif" ALT="TenDRA home page">
16 
</A>
17 
<IMG SRC="../images/no_index.gif" ALT="document index"><P>
18 
<HR>
19 
<DL>
20 
<DT><A HREF="#S84"><B>11.1 </B> - Transformations as definitions</A><DD>
21 
<DT><A HREF="#S85"><B>11.1.1 </B> - Examples of transformations</A><DD>
22 
<DT><A HREF="#S86"><B>11.1.2 </B> - Programs with undefined values</A><DD>
23 
</DL>
24 
<HR>
25 
<H1>11  <A NAME=0>TDF transformations</H1>
26 
TDF to TDF transformations form the basis of most of the tools of
27 
TDF, including translators. TDF has a rich set of easily performed
28 
transformations; this is mainly due to its algebraic nature, the liberality
29 
of its sequencing rules, and the ease with which one can introduce
30 
new names over limited scopes. For example, a translator is always
31 
free to transform:<P>
32 
<PRE>
33 
assign(e1, e2)
34 
</PRE>
35 
to:<P>
36 
<PRE>
37 
identify(empty, new_tag, e1, assign(obtain_tag(new_tag), e2))
38 
</PRE>
39 
i.e. identify the evaluation of the left-hand side of the assignment
40 
with a new TAG and use that TAG as the left-hand operand of a new
41 
assignment in the body of the identification. Note that the reverse
42 
transformation is only valid if the evaluation of e1 does not side-effect
43 
the evaluation of e2. A producer would have had to use the second
44 
form if it wished to evaluate e1 before e2. The definition of assign
45 
allows its operands to be evaluated in any order while identify insists
46 
that the evaluation of its <I>definition</I> is conceptually complete
47 
before starting on its<I> body</I>.<P>
48 
Why would a translator wish to make the more complicated form from
49 
the simpler one? This would usually depend on the particular forms
50 
of e1 and e2 as well as the machine idioms available for implementing
51 
the assignment. If, for example, the joint evaluation of e1 and e2
52 
used more evaluation registers than is available, the transformation
53 
is probably a good idea. It would not necessarily commit one to putting
54 
the new tag value into the stack; some other more global criteria
55 
might lead one to allocate it into a register disjoint from the evaluation
56 
registers. In general, this kind of transformation is used to modify
57 
the operands of TDF constructions so that the code-production phase
58 
of the translator can just &quot;churn the handle&quot; knowing that
59 
the operands are already in the correct form for the machine idioms.<P>
60 
Transformations like this are also used to give optimisations which
61 
are largely independent of the target architecture. In general, provided
62 
that the sequencing rules are not violated, any EXP construction,
63 
F(X), say, where X is some inner EXP, can be replaced by:<P>
64 
<PRE>
65 
 identify(empty, new_tag, X, F(obtain_tag(new_tag))).
66 
</PRE>
67 
This includes the extraction of expressions which are constant over
68 
a loop; if F was some repeat construction and one can show that the
69 
EXP X is invariant over the repeat, the transformation does the constant
70 
extraction.<P>
71 
Most of the transformations performed by translators are of the above
72 
form, but there are many others. Particular machine idioms might lead
73 
to transformations like changing a test (i&gt;=1) to (i&gt;0) because
74 
the test against zero is faster; replacing multiplication by a constant
75 
integer by shifts and adds because multiplication is slow; and so
76 
on. Target independent transformations include things like procedure
77 
inlining and loop unrolling. Often these target independent transformations
78 
can be profitably done in terms of the TOKENs of an LPI; loop unrolling
79 
is an obvious example.<P>
80 
<A NAME=S84>
81 
<HR><H2>11.1. <A NAME=4>Transformations as definitions</H2>
82 
As well being a vehicle for expressing optimisation, TDF transformations
83 
can be used as the basis for defining TDF. In principle, if we were
84 
to define all of the allowable transformations of the TDF constructions,
85 
we would have a complete definition of TDF as the initial model of
86 
the TDF algebra. This would be a fairly impracticable project, since
87 
the totality of the rules including all the simple constructs would
88 
be very unwieldy, difficult to check for inconsistencies and would
89 
not add much illumination to the definition. However, knowledge of
90 
allowable transformations of TDF can often answer questions of the
91 
meaning of diverse constructs by relating them to a single construct.
92 
What follows is an alphabet of generic transformations which can often
93 
help to answer knotty questions. Here, E[X \ Y] denotes an EXP E with
94 
all internal occurrences of X replaced by Y.<P>
95 
<PRE>
96 
If F is any non order-specifying
97 
<A NAME=footnote79 HREF="footnote.html#79">*</A> EXP constructor and E is one of the EXP operands of F, then:
98 
</PRE>
99 
F(... , E, ...) xde  identify(empty, newtag, E, F(... , obtain_tag(newtag),
100 
...)) If E is a non side-effecting
101 
<A NAME=footnote80 HREF="footnote.html#80">*</A>
102 
EXP and none of the variables used in E are assigned to in B:  identify(v,
103 
tag, E, B) xde  B[obtain_tag(tag) \ E] If all uses of tg in B are
104 
of the form contents(shape(E), obtain_tag(tg)): variable(v, tg, E,
105 
B)  xde  identify(v, nt, E, B[contents(shape(E), obtain_tag(tg)) \
106 
obtain_tag(nt)])  sequence((S<I>1</I>, ... , S<I>n</I>), sequence((P<I>1</I>,
107 
..., P<I>m</I>), R)  xdb  sequence((S<I>1</I>, ..., S<I>n</I>, P<I>1</I>,
108 
..., P<I>m</I>), R) If S<I>i</I> = sequence((P<I>1</I>, ..., P<I>m</I>),
109 
R) : sequence((S<I>1</I>, ... , S<I>n</I>), T) xdb  sequence((S<I>1</I>,
110 
..., S<I>i-1</I>, P<I>1</I>, ..., P<I>m</I>, R, S<I>i+1</I>, ...,
111 
S<I>n</I>), T) E xdb  sequence(( ), E) If D is either identify or
112 
variable: D(v, tag, sequence((S<I>1</I>, ..., S<I>n</I>), R), B) xde
113 
sequence((S<I>1</I>, ..., S<I>n</I>), D(v, tag, R, B) ) If S<I>i</I>
114 
is an EXP BOTTOM , then: sequence((S<I>1</I>, S<I>2</I>, ... S<I>n</I>),
115 
R) xde  sequence((S<I>1</I>, ... S<I>i-1</I>), S<I>i</I>) If E is
116 
an EXP BOTTOM, and if D is either identify or variable: D(v, tag,
117 
E, B) xde  E If S<I>i</I> is make_top(), then: sequence((S<I>1</I>,
118 
S<I>2</I>, ... S<I>n</I>), R) xdb  sequence((S<I>1</I>, ... S<I>i-1</I>,
119 
S<I>i+1</I>, ...S<I>n</I>), R) If S<I>n</I> is an EXP TOP: sequence((S<I>1</I>,
120 
... S<I>n</I>), make_top()) xdb  sequence((S<I>1
121 
</I>, ..., S<I>n-1</I>), S<I>n</I>) If E is an EXP TOP and E is not
122 
side-effecting then E xde  make_top() If C is some non order-specifying
123 
and non side-effecting constructor, and S<I>i</I> is C(P<I>1</I>,...,
124 
P<I>m</I>) where P<I>1..m</I> are the EXP operands of C: sequence((S<I>1</I>,
125 
..., S<I>n</I>), R) xde sequence((S<I>1</I>, ..., S<I>i-1</I>, P<I>1</I>,
126 
..., P<I>m</I>, S<I>i+1</I>, ..., S<I>n</I>), R) If none of the S<I>i</I>
127 
use the label L:  conditional(L, sequence((S<I>1</I>, ..., S<I>n</I>),
128 
R), A)  xde  sequence((S<I>1</I>, ..., S<I>n</I>), conditional(L,
129 
R, A)) If there are no uses of L in X
130 
<A NAME=footnote81 HREF="footnote.html#81">*</A>:
131 
conditional(L, X, Y) xde  X conditional(L, E , goto(Z)) xde  E[L \
132 
Z] If EXP X contains no use of the LABEL L:  conditional(L, conditional(M,
133 
X, Y), Z)  xde  conditional(M, X, conditional(L, Y, Z))  repeat(L,
134 
I, E) xde  sequence( (I), repeat(L,  make_top(), E)) repeat(L, make_top(),
135 
E) xde  conditional(Z, E[L \ Z], repeat(L, make_top(), E)) If there
136 
are no uses of L in E: repeat(L, make_top(), sequence((S, E), make_top())
137 
xde  conditional(Z, S[L \ Z],   repeat(L, make_top(), sequence((E,
138 
S), make_top()) ) ) If f is a procedure defined
139 
<A NAME=footnote82 HREF="footnote.html#82">*</A>
140 
as:  make_proc(rshape, formal<I>1..n</I>, vtg , B( return R<I>1</I>,
141 
..., return R<I>m</I>)) where: formal<I>i</I> = make_tagshacc(s<I>i</I>,
142 
v<I>i</I>, tg<I>i</I>) and B is an EXP with all of its internal return
143 
constructors indicated parametrically then, if A<I>i</I> has SHAPE
144 
s<I>i</I>
145 
apply_proc(rshape, f, (A<I>1</I>, ... , A<I>n</I>), V)  xde  variable(
146 
empty, newtag, make_value((rshape=BOTTOM)? TOP: rshape),  labelled(
147 
(L),    variable(v<I>1</I>, tg<I>1</I>, A<I>1</I>, ... , variable(v<I>n</I>,
148 
tg<I>n</I>, A<I>n</I>, variable(empty, vtg, V,     B(sequence( assign(obtain_tag(newtag),
149 
R<I>1</I>), goto(L)) , ... ,       sequence( assign(obtain_tag(newtag),
150 
R<I>m</I>), goto(L))     )    )    ),    contents(rshape, obtain_tag(newtag))
151 
)       ) assign(E, make_top()) xde  sequence( (E), make_top()) contents(TOP,
152 
E) xde  sequence((E), make_top()) make_value(TOP) xde  make_top()
153 
component(s, contents(COMPOUND(S), E), D)  xde contents(s, add_to_ptr(E,
154 
D))  make_compound(S, ((E<I>1</I>, D<I>1</I>), ..., (E<I>n</I>, D<I>n</I>))
155 
) xde  variable(empty, nt, make_value(COMPOUND(S)), sequence(    (
156 
assign(add_to_ptr(obtain_tag(nt), D<I>1</I>), E<I>1</I>), ... ,
157 
assign(add_to_ptr(obtain_tag(nt), D<I>n</I>), E<I>n</I>) ),   contents(S,
158 
obtain_tag(nt))  )      )
159 
<A NAME=S85>
160 
<H3>11.1.1. Examples of transformations</H3>
161 
Any of these transformations may be performed by the TDF translators.
162 
The most important is probably {A} which allows one to reduce all
163 
of the EXP operands of suitable constructors to obtain_tags. The expansion
164 
rules for identification, {G}, {H} and {I}, gives definition to complicated
165 
operands as well as strangely formed ones, e.g.  return(... return(X)...).
166 
Rule {A} also illustrates neatly the lack of ordering constraints
167 
on the evaluation of operands. For example, mult(et, exp1, exp2) could
168 
be expanded by applications of {A} to either:<P>
169 
<PRE>
170 
identify(empty, t1, exp1,
171 
	 identify(empty, t2, exp2, mult(et, obtain_tag(t1), obtain_tag(t2))) )
172 
</PRE>
173 
or:<P>
174 
<PRE>
175 
identify(empty, t2, exp2,
176 
	 identify(empty, t1, exp1, mult(et, obtain_tag(t1), obtain_tag(t2))) )
177 
</PRE>
178 
Both orderings of the evaluations of exp1 and exp2 are acceptable,
179 
regardless of any side-effects in them. There is no requirement that
180 
both expansions should produce the same answer for the multiplications;
181 
the only person who can say whether either result is &quot;wrong&quot;
182 
is the person who specified the program.<P>
183 
Many of these transformations often only come into play when some
184 
previous transformation reveals some otherwise hidden information.
185 
For example, after procedure in-lining given by {U} or loop un-rolling
186 
given by {S}, a translator can often deduce the behaviour of a _test
187 
constructor, replacing it by either a make_top or a goto. This may
188 
allow one to apply either {J} or {H} to eliminate dead code in sequences
189 
and in turn {N} or {P} to eliminate entire conditions and so on.<P>
190 
Application of transformations can also give expansions which are
191 
rather pathological in the sense that a producer is very unlikely
192 
to form them. For example, a procedure which returns no result would
193 
have result statements of the form return(make_top()). In-lining such
194 
a procedure by {U} would have a form like:<P>
195 
<PRE>
196 
variable(empty, nt, make_shape(TOP),
197 
	labelled( (L),
198 
	... sequence((assign(obtain_tag(nt), make_top())),
199 
goto(L)) ...
200 
	contents(TOP, obtain_tag(nt))
201 
	)
202 
)
203 
</PRE>
204 
The rules {V}, {W} and {X} allow this to be replaced by:<P>
205 
<PRE>
206 
variable(empty, nt, make_top(),
207 
	labelled( (L),
208 
	... sequence((obtain_tag(nt)), goto(L)) ...
209 
	sequence((obtain_tag(nt)), make_top())
210 
	)
211 
)
212 
</PRE>
213 
The obtain_tags can be eliminated by rule {M} and then the sequences
214 
by {F}. Sucessive applications of {C} and {B} then give:<P>
215 
<PRE>
216 
labelled( (L),
217 
	... goto(L) ...
218 
	make_top()
219 
	)
220 
 
221 
</PRE>
222 
<A NAME=S86>
223 
<H3>11.1.2. Programs with undefined values</H3>
224 
The definitions of most of the constructors in the TDF specification
225 
are predicated by some conditions; if these conditions are not met
226 
the effect and result of the constructor is not defined for all possible
227 
platforms<A NAME=footnote83 HREF="footnote.html#83">*</A>. Any value
228 
which is dependent on the effect or result of an undefined construction
229 
is also undefined. This is not the same as saying that a program is
230 
undefined if it can construct an undefined value - the dynamics of
231 
the program might be such that the offending construction is never
232 
obeyed.<P>
233 
<P>
234 
<HR>
235 
<P><I>Part of the <A HREF="../index.html">TenDRA Web</A>.<BR>Crown
236 
Copyright &copy; 1998.</I></P>
237 
</BODY>
238 
</HTML>