Re: Placement of memory loads

On 2009-11-05, YuGr <tetra2005@googlemail.com> wrote:
> Hi,
>
> I want to figure out the best way to place initial memory loads in generated
> code.
>
> My current approach is very simple and inefficient. I do a liveness analysis
> and then insert memory loads for all undefined variables in the beginning of
> initial basic block. Here is an example (both x and y are global):
> int main() {
> x = x + 1;
> //A lot of code
> y = y + 1;
> }
> I see that both x and y belong to initial block's Live_in and insert loads:
> int main() {
> load x;
> load y;
> x = x + 1;
> //A lot of code
> y = y + 1;
> }


Strange, old-schoolish approach to compiling. Loading from memory into
registers is a low level concept, variables high level.


Why not single-store-assignment or something?


How about generating a new temporary for each intermediate expression,
including loads. Then assign registers to temporaries.


    x = x + 1;
    y = y + x;


becomes something like:


    t1 := x
    t2 := t1 + 1 /* x understood to live in t2 now */
    x := t2
    t3 := y
    t4 := t3 + t2
    y := t4


Now you have a lot of freedom in moving around the loads and stores.
Of course, you can't move an instruction in front of one which produces
an operand which that instruction needs. But this rearrangement is valid:


    t3 := y /* moved way up */
    t1 := x
    t2 := t1 + 1
    t4 := t3 + t2
    y := t4
    x := t2 /* moved way down */


Of course, if accessing x and y is considered a visible side effect because
they are some kind of specially qualified object in the source language, like
``volatile'', the above moves would not be correct; the accesses must remain in
the order: load x, store x, load y, store y. For that you can have some fence
instruction.


    fence
    t1 := x
    t2 := t1 + 1 /* x understood to live in t2 now */
    x := t2
    fence /* separates full expressions */
    t3 := y
    t4 := t3 + t2
    y := t4
    fence


No load or store can be moved across a fence if the variable is qualified
as volatile.

Return to the comp.compilers page.
Search the comp.compilers archives again.