12. TDF transformations

  1. 12.1. Transformations as definitions
  2. 12.2. Examples of transformations
  3. 12.3. Programs with undefined values

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:

assign(e1, e2)

to:

identify(empty, new_tag, e1, assign(obtain_tag(new_tag), e2))

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 definition is conceptually complete before starting on its body.

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.

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:

identify(empty, new_tag, X, F(obtain_tag(new_tag))).

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.

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.

12.1. Transformations as definitions

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.

If F is any non order-specifying [i] EXP constructor and E is one of the EXP operands of F, then:

F(..., E, ...) xde identify(empty, newtag, E, F(..., obtain_tag(newtag), ...))

If E is a non side-effecting [j] 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((S1, ..., Sn),
         sequence((P1, ..., Pm), R) xdb
         sequence((S1, ..., Sn, P1, ..., Pm), R)

If Si = sequence((P1, ..., Pm), R):

sequence((S1, ..., Sn), T) xdb
         sequence((S1, ...,
                  Si-1, P1, ..., Pm, R,
                  Si+1, ..., Sn), T) E xdb sequence((), E)

If D is either identify or variable:

D(v, tag, sequence((S1, ..., Sn), R), B) xde
                   sequence((S1, ..., Sn), D(v, tag, R, B))

If Si is an EXP BOTTOM, then:

sequence((S1, S2, ... Sn), R) xde
sequence((S1, ...  Si - 1), Si)

If E is an EXP BOTTOM, and if D is either identify or variable:

D(v, tag, E, B) xde E

If Si is make_top(), then:

sequence((S1,
S2, ...  Sn), R) xdb
sequence((S1, ...  Si - 1,
Si + 1, ...Sn), R)

If Sn is an EXP TOP:

sequence((S1, ...
          Sn), make_top()) xdb sequence((S1, ...,
          Sn - 1), Sn)

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 Si is C(P1,..., Pm) where P1..m are the EXP operands of C:

sequence((S1, ..., Sn), R) xde
sequence((S1, ..., Si - 1, P1,
          ..., Pm, Si + 1, ..., Sn), R)

If none of the Si use the label L:

conditional(L,
            sequence((S1, ..., Sn), R), A) xde
            sequence((S1, ..., Sn), conditional(L, R, A))

If there are no uses of L in X: [k]

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 [l] as:

make_proc(rshape, formal1 .. n, vtg,
          B(return R1, ..., return Rm))

where:

formali = make_tagshacc(si, vi, tgi)

and B is an EXP with all of its internal return constructors indicated parametrically then:

if Ai has SHAPE si apply_proc(rshape, f, (A1, ..., An), V) xde
variable(empty, newtag, make_value((rshape=BOTTOM) ?  TOP : rshape),
         labelled((L), variable(v1, tg1, A1, ...,
                  variable(vn, tgn, An,
                  variable(empty, vtg, V,
                  B(sequence(assign(obtain_tag(newtag), R1), goto(L)),
                    ...,
                    sequence(assign(obtain_tag(newtag), Rm), 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, ((E1, D1), ..., (En, Dn))) xde variable(empty, nt, make_value(COMPOUND(S)),
    sequence((assign(add_to_ptr(obtain_tag(nt), D1), E1), ...,
              assign(add_to_ptr(obtain_tag(nt), Dn), En)),
             contents(S, obtain_tag(nt))))

12.2. Examples of transformations

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:

identify(empty, t1, exp1, identify(empty, t2, exp2, mult(et, obtain_tag(t1), obtain_tag(t2))))

or:

identify(empty, t2, exp2, identify(empty, t1, exp1, mult(et, obtain_tag(t1), obtain_tag(t2))))

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.

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.

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:

variable(empty, nt, make_shape(TOP),
         labelled((L),
         ... sequence((assign(obtain_tag(nt), make_top())),
goto(L)) ...
         contents(TOP, obtain_tag(nt))
         )
)

The rules {V}, {W} and {X} allow this to be replaced by:

variable(empty, nt, make_top(),
         labelled((L),
         ... sequence((obtain_tag(nt)), goto(L)) ...
         sequence((obtain_tag(nt)), make_top())
         )
)

The obtain_tags can be eliminated by rule {M} and then the sequences by {F}. Sucessive applications of {C} and {B} then give:

labelled((L),
         ... goto(L) ...
         make_top()
        )

12.3. Programs with undefined values

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. [m] 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.

  1. [i]

    The order-specifying constructors are conditional, identify, repeat, labelled, sequence and variable.

  2. [j]

    A sufficient condition for not side-effecting in this sense is that there are no apply_procs or local_allocs in E; that any assignments in E are to variables defined in E; and that any branches in E are to labels defined in conditionals in E.

  3. [k]

    There are analogous rules for labelled and repeat with unused LABELs.

  4. [l]

    This has to be modified if B contains any uses of local_free_all or last_local.

  5. [m]

    However, we may find that the mapping of a constraint allows extra relationships for a class of architectures which do not hold in all generality; this may mean that some constructions are defined on this class while still being undefined in others (see section 13).