Re: register allocation for alias values???

Christian Bau <christian.bau@cbau.freeserve.co.uk>
8 Jun 2003 21:58:18 -0400

          From comp.compilers

Related articles
register allocation for alias values??? wzhang@cse.psu.edu (Wei Zhang) (2003-06-05)
Re: register allocation for alias values??? christian.bau@cbau.freeserve.co.uk (Christian Bau) (2003-06-08)
| List of all articles for this month |

From: Christian Bau <christian.bau@cbau.freeserve.co.uk>
Newsgroups: comp.compilers
Date: 8 Jun 2003 21:58:18 -0400
Organization: Compilers Central
References: <Pine.BSI.4.40.0306031049380.7260-100000@tom.iecc.com> 03-06-040
Keywords: registers, optimize
Posted-Date: 08 Jun 2003 21:58:17 EDT

  "Wei Zhang" <wzhang@cse.psu.edu> wrote:


> I have a question about the register allocation for alias values mentioned
> in the paper "Unified Management of Registers and Cache Using Liveness and
> Cache Bypass", in PLDI 89.
>
> For array and pointer-intensive codes,
> since the compiler cannot solve the alias problem,
    *************************************************


The compiler just has to do its best to determine which accesses
through pointers will definitely read/write a value, which will
definitely not read/write a value, and which maay or may not write a
value.


> how are those values allocated to registers? Are the
> registers required to be flushed for every store to guarantee the
> correctness of the program? For RISC architecture, since all the operands
> (except ld/st) need to be fetched from the register, so how are those
> problems solved
> (Flush at every store is too expensive)?
    ****************************************


Cost doesn't matter if that is the only thing the compiler can do to
guarantee correctness. But that is not RISC specific, memory access is
expensive on all architectures.


But first: If you never take the address of an object then it cannot
be accessed through a pointer. If you take the address, and keep track
of where the address goes, you may know which pointers can and which
can't access the object. C and C++ have rules that allow the compiler
sometimes to deduce that that pointers cannot legaly alias. C99 has a
new feature (restrict pointers and const restrict pointers) that allow
the compiler to deduce much more.


If a register contains a value that should be stored in memory, but
hasn't been stored yet, and a pointer read access might read that memory
location, then the register has to be stored. If the pointer read access
_definitely_ accesses that memory location then instead of reading from
memory the compiler can use the register.


If a register contains a copy of a value in memory, and a pointer write
access might write to that memory location, then the compiler must
forget that the register contains a copy of that memory location,
because it might not be true anymore.


If a register contains a value that should be stored in memory, but
hasn't been stored yet, and a pointer read access might write to that
memory location, but possibly might write to another location, then
things are bad: You have to both store the register, and forget that it
contains a copy of the memory location.


So it is important that the compiler collects and deduces as much
aliasing information as possible. Even if complete knowledge is not
possible in many cases, every bit helps.



Post a followup to this message

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