TDF Guide, Issue 4.0

January 1998

assign(e1, e2)

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

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))). 

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.

11.1.1. Examples of transformations

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

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

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))
	)
)

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

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

11.1.2. Programs with undefined values