Re: register allocation: basic blocks, liveness and next use

kphillips <kevin.phillips83@yahoo.com> writes:


> Many thanks for the suggestions given. I will definitely analyse the
> pros and cons and hopefully come up with a solution. It does look
> strange that no book pointed this out. But at least I know that I'm on
> the right track. Once again, thanks for your help.


Actually, it's not strange to me at all that no book you read pointed
this out. It's at the level of detail that is often skipped. (see
below) It has no theoretical implications and at the practical level
any of Max's suggestions will work equally well. I worked on lots of
code generators in the days when this was a relevant issue and each
author picked a different one of the possibilities, mostly without
thinking that it was worth commenting on. (Actually, I think each of
the compilers I worked on did explain the exact choices made, but only
in the parts of the code where the choices were implemented.)


Reaching back into the dim recesses of my brain, I recall that Bob
Freiberghouse (author of optimizing PL/I, FORTRAN, et. al. compilers)
used different numbering schemes for temporaries which could cross a
basic block boundary and ones that could not. Ones within a block
were given positive numbers and were always freed by the end of the
block. Ones that could cross a basic block were given negative
numbers and explicitly freed by an instruction which marked their last
use. If I recall correctly, for temporary allocation a call did not
break a basic block. However, for other optimizations it did.


Fred Chow (author of Pascal, C, et. al. compilers) treated temporaries
like variables, but had a local numbering scheme for all variable uses
within a basic block and a global numbering scheme for uses of a
variable without respect to block boundaries. From any given use, one
could always access both numbering schemes. I believe calls always
broke basic blocks.


My recollection of other compilers is more sketchy, as I did
significantly more work on the above suites than on PCC, GCC, or any
other compilers. However, the issue was well on the mind of C
compiler writers as you will find that the standard (at one time at
least) talked about which values had to be preserved/restored over
setjmp/longjmp calls. The motivation for that was to allow
temporaries to be kept in registers across calls.


In general, most compilers that I have seen treat temporaries like
variables. That is generally fairly simple to implement and is easy
to get semantically correct. If one uses that as the general case,
but then detects and special cases the temporaries which live entirely
in one basic block, one gets most of the easy-to-find important cases.


I've seen more divergence in whether a call breaks a block or not.
There are definite advantages both ways. The problem with calls is
the semantics that often get layered on top of them, such as non-local
gotos (exceptions or signals) or aliasing and non-local reference
issues.


below: While I am not surprised you haven't found a book that covered
that aspect, I suspect that it isn't that it is never addressed in
compiler texts. For example, I would be willing to bet that Bob
Morgan's book covers it, as did Bill Wulf's book, and the book on the
VAX PL/I compiler. I would also be surprised if it wasn't addressed
somewhere in Steve Muchnick's book. I know that Fred Chow's PhD
thesis explains the choices he made in that area. Unfortunately, most
of those books are either old or not at the introductory level.
Moreover, I think there are many fine compiler texts that wouldn't be
better if they mentioned that kind of detail. I suspect most student
compilers implement languages where not breaking a block at a call
boundary solves the problem and they don't have any semantics where
doing that causes things to break.


Hope this helps,
-Chris


******************************************************************************
Chris Clark Internet: christopher.f.clark@compiler-resources.com
Compiler Resources, Inc. or: compres@world.std.com
23 Bailey Rd Web Site: http://world.std.com/~compres
Berlin, MA 01503 voice: (508) 435-5016
USA fax: (978) 838-0263 (24 hours)
------------------------------------------------------------------------------

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