🚀 go-pugleaf

In article <4355@tekcrl.LABS.TEK.COM> stevev@tekchips.LABS.TEK.COM (Steve Vegdahl) writes:
>The register allocator generally wants to do all of one computation, then
>all of the next, etc. to minimize the number of concurrently live variables.
>The instruction scheduler generally wants to interleave "unrelated"
>compuations to minimize the effects of memory latency and such.  This issue
>came up when we were considering instruction scheduling for our 88000 Scheme
>compiler.  (See our paper in the ASPLOS-III proceedings).
>
>What happens in practice when register allocation is done first, is that the
>register assignments introduce a lot of artificial constraints on the
>scheduler, causing it to do a much poorer job.  In other words, the
>assignment of common registers to computations that could otherwise be
>interleaved  makes such interleaving impossible.
We dealt with this problem in the Cerberus multiprocessor simulator by
simply having the register allocator get registers from the scratch pile
in a round-robin manner, instead of starting upwards from R0 in the search
for a free one each time.  This minimized the number of "false dependencies"
and allowed a postprocessing scheduler to work quite well.  In the limit
of large register counts it of course is perfect (256 registers is effectively
an infinite number, but in practice is worked quite well at 16 or 32 registers.
If one is constrained to do the scheduling in a machine dependent postprocessor
with the register allocation done in a PCC or GCC like portable compiler this
technique is quite useful and produces well scheduled code.

brooks@maddog.llnl.gov, brooks@maddog.uucp