Use the following explicit tree notation for the intermediate representation.
C(k) is a constant, R(r) a processor register, M(e) a word load from memory address e, ADD addition, and SHL(e,2) a left shift by two bits. MOVE(destination,source) assigns either a processor register or the computer memory word designated by M. Parentheses show complete tree structure, so these displays specify trees rather than already shared Directed acyclic graphs.Let be the constant base memory address of the global array
a, and the constant offset of local i from the frame pointer fp. Each integer occupies four bytes, and array indices are zero-based; a fixed nonzero lower bound can instead be absorbed into . Local t is represented by R(t). After replacing multiplication by four with a left shift, the three trees are:MOVE(R(t),
M(ADD(C(A),
SHL(M(ADD(C(A),
SHL(M(ADD(R(fp),C(I))),2))),2))))
MOVE(M(ADD(C(A),
SHL(M(ADD(C(A),
SHL(M(ADD(R(fp),C(I))),2))),2))),
M(ADD(C(A),SHL(M(ADD(R(fp),C(I))),2))))
MOVE(M(ADD(C(A),SHL(M(ADD(R(fp),C(I))),2))),
R(t))Every
M(ADD(R(fp),C(I))) loads i; the next enclosing M loads a[i]; the outermost M in the first tree loads a[a[i]]. Each array index is converted to a byte offset by a left shift of two bits. The address rule used in all three trees is The source language's array bounds checks are omitted as requested.The useful repeated program expressions, nested inside one another, are the memory address of
a[i], its value, and the memory address of a[a[i]]. Materialize each maximal reusable tree at the level at which it is shared, using fresh temporary variables u, v, and w:MOVE(R(u), ADD(C(A),SHL(M(ADD(R(fp),C(I))),2)))
MOVE(R(v), M(R(u)))
MOVE(R(w), ADD(C(A),SHL(R(v),2)))
MOVE(R(t), M(R(w)))
MOVE(M(R(w)), R(v))
MOVE(M(R(u)), R(t))Thus
u is a saved memory address, v the old integer value of a[i], w the second saved memory address, and t the old value at that second location. The two large address trees occur both in loads and as store destinations. After extracting them, the repeated load of a[i] inside the second address and as the middle assignment's source becomes v. Extracting every smaller nested tree again would add no benefit.The relevant alias analysis facts are that local
i does not occupy any location written through global a, that frame pointer fp and base stay fixed, and that t,u,v,w are distinct processor registers or otherwise nonoverlapping temporary variables. There are no intervening calls, volatile memory accesses, or concurrent changes. Under these assumptions, loading i once remains valid even across the array stores. Before the middle store, no array location has yet changed, so both its target memory address and its source value can be computed and saved earlier.No assumption that the two array locations are distinct is required. The middle store may change
a[i] when its target coincides with it, but v is not loaded again afterwards: only the saved address u is needed for the final store. It would be unsound to retain an arbitrary array load across an aliasing store and then treat it as the new contents; that is not what these trees do.For a language with a true global array, a distinct local variable, and no arbitrary means of fabricating pointers to unrelated storage, these facts follow simply from declarations and the stack frame layout. Accesses must denote valid array elements. In an unrestricted low-level language with overlapping storage, arbitrary pointer arithmetic or unchecked out-of-range accesses, that conclusion requires extra guarantees. Omitting emitted array bounds checks does not itself prove that all memory addresses are valid. If denotes a word load, the saved quantities are
Here is a literal instruction selection for the trees in part (b), with the temporary variables allocated to processor registers.
MOV r,#k loads an arbitrary constant in one instruction. LD and ST load and store one four-byte word; [r] denotes zero-offset access. LSL is a left shift. We use conventional base-plus-immediate access for the fixed local offset I.MOV rb, #A
LD ri, [fp + I]
LSL ru, ri, #2
ADD ru, rb, ru
LD rv, [ru]
LSL rw, rv, #2
ADD rw, rb, rw
LD rt, [rw]
ST rv, [rw]
ST rt, [ru]The first four instructions construct
u, the fifth obtains v, the next two construct w, and the last three perform the remaining load and the two stores. Each destructive update of ru or rw reuses a processor register whose previous value is no longer needed. We assume enough processor registers to avoid a register spill.If the target offers only the explicitly mentioned two-register register-offset addressing and lacks base-plus-immediate access, replace the one local load by
MOV rk,#I; LD ri,[fp+rk]; all other conclusions are unchanged. A zero processor register or a zero-offset load supplies the notation [ru] and [rw] as usual. This direct translation takes ten instructions with immediate local addressing, or eleven with the stated replacement. Thus These are instruction counts for the specified abstract target, not measured execution times.The target's register-offset addressing already performs the addition of the array base and a scaled index as part of each load or store. Materializing a maximal common address expression into a processor register introduces an explicit
ADD that this addressing mode could have supplied. Here the extra address temporary variables save no arithmetic that the memory instructions need to perform separately.Instead keep the scaled indices, share the loaded old value of
a[i], and fold the base addition into each memory operand:MOV rb, #A
LD ri, [fp + I]
LSL rj, ri, #2
LD rv, [rb + rj]
LSL rk, rv, #2
LD rt, [rb + rk]
ST rv, [rb + rk]
ST rt, [rb + rj]rj remains the original index's byte offset, rv is its old element, and rk remains the second element's byte offset. Both stores use those saved offsets. Folding address additions into the memory instructions removes two instructions, reducing ten to eight, or eleven to nine if the local load requires the alternative sequence described in part (c). ThereforeThis illustrates why common subexpression elimination must interact with instruction selection: a larger repeated tree is not automatically a better value to materialize. A useful refinement retains common scaled-index trees, or propagates the address addition trees back into their memory uses. The calculation establishes an instruction-count improvement under the stated instruction set architecture; scheduling and actual timing depend on further machine details.
The source rewrite already saves the old
a[i] in register-allocated t. Denote the original integer index by , its original element by , and the original element there by . The second fragment first sets t=j, then writes to a[i0], and finally writes to a[j]. Thus it performs the same intended swap without needing to recompute the second memory address from a possibly modified array element.For completeness, the first fragment is also correct when the two locations might alias. If , its middle store changes only
a[j], so the final a[i] still denotes the first location. If , then , and the supposed swap is a no-op in both fragments. There is no need to assume distinct locations.For the second fragment, common subexpression elimination of maximal addresses gives, using
z for the second address:MOVE(R(u), ADD(C(A),SHL(M(ADD(R(fp),C(I))),2)))
MOVE(R(t), M(R(u)))
MOVE(R(z), ADD(C(A),SHL(R(t),2)))
MOVE(M(R(u)), M(R(z)))
MOVE(M(R(z)), R(t))The nested memory-to-memory assignment requires an additional scratch processor register
rv on a reduced instruction set computer. A direct translation is therefore:MOV rb, #A
LD ri, [fp + I]
LSL ru, ri, #2
ADD ru, rb, ru
LD rt, [ru]
LSL rz, rt, #2
ADD rz, rb, rz
LD rv, [rz]
ST rv, [ru]
ST rt, [rz]The same compiler need not produce any better code: this has the same ten-instruction count as part (c). It still performs two element loads, two element stores, two shifts and two separately materialized address additions, plus the base and local-index setup. The processor register roles and store order differ, but the work is the same. The corresponding folding of register-offset addressing removes both
ADD instructions here too, yielding the same eight-instruction count as part (d).The key alias analysis advantage available in both fragments is that
i remains unchanged by the array stores. In the second fragment, t is also unchanged after its first assignment because it lives in a processor register. Its name alone does not produce a further saving beyond what the first fragment's common subexpression elimination already achieves. Exact instruction selection is not uniquely prescribed by the paper; these explicit translations demonstrate why the claimed source-level efficiency advantage does not follow: Articles by others on the same topic
There are currently no matching articles.