question on register spill behavior

Hi All,

I am not so on top of the inner workings of the register spill
behavior. Can the spill code be placed in an inner scope of where the
register is defined? An example,

<code>
x = .. //suppose it's allocated a register
if(..) {
//can spill code for 'x' placed here??
...
.. = x;
foo();
}
... = x;
</code>

It seems nothing forbids it. My question is, with the existing spill
algorithm in popular compilers (e.g. GCC), can the above scenario
happen? And how often do they happen? In most cases, register spill
code seems to be at the beginning of a function (pushs) and end of a
function (pops).

Thanks,
Bin

BX <bxin@acm.org> writes:
> I am not so on top of the inner workings of the register spill
>behavior. Can the spill code be placed in an inner scope of where the
>register is defined? An example,
>
><code>
>x = .. //suppose it's allocated a register
>if(..) {
> //can spill code for 'x' placed here??
> ...
> .. = x;
> foo();
>}
>.. = x;
></code>

That is called live range splitting.

Without live range splitting colouring register allocators spill a
live range completely (loading it right before every use and storing
it right after every def, possibly with some optimizations limited to
basic blocks).

> It seems nothing forbids it. My question is, with the existing spill
>algorithm in popular compilers (e.g. GCC), can the above scenario
>happen?

Classically, GCC used a simple colouring register allocator without
live range splitting. They have done a lot in the last years, but
AFAIK all attempts to improve the register allocator have failed.

I don't know if other compilers use live-range splitting, but I guess
that some do.

> In most cases, register spill code seems to be at the beginning of a
>function (pushs) and end of a function (pops).

Yes, that's my impression of gcc, too: It spills the callee-saved
registers on entry and refills them on exit, and never saves and
restores caller-saved registers around calls (but instead uses them
only for live ranges that don't survive calls), and then allocates
live ranges into the now-free register ranges.

- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/

"BX" <bxin@acm.org> wrote
> I am not so on top of the inner workings of the register spill
> behavior. Can the spill code be placed in an inner scope of where the
> register is defined? An example,
>
> <code>
> x = .. //suppose it's allocated a register
> if(..) {
> //can spill code for 'x' placed here??
> ...
> .. = x;
> foo();
> }
> .. = x;
> </code>
>
> It seems nothing forbids it. My question is, with the existing spill
> algorithm in popular compilers (e.g. GCC), can the above scenario
> happen? And how often do they happen? In most cases, register spill
> code seems to be at the beginning of a function (pushs) and end of a
> function (pops).
>

this depends some on the compiler, as noted.
I don't know as much about gcc or friends, but I can answer for my compiler
(a relatively unknown project that few have probably heard of, or would care
if they knew...).

actually, I have several compiler cores, which use rather different ways of
managing registers.

in my case, for my older/simpler compiler, register spilling/flushing is
done whenever it is needed, and so is done whenever it could become
potentially ambiguous, which is typically:
before labels or jumps, before function calls, ...

the compiler state is internally kept flexible, and operation is linear, so
the compiler is like "this might not be safe", and then just flushes stuff,
with state being rebuilt following said flush...

there are slight variations, which differ some on what exactly they flush
and how they flush it, with one of the more "hardcore" versions being used
for function calls (basically, it flushes all caller-save registers, makes
sure everything is properly written out to the stack and variables, the
stack pointer points to the base of the arguments, ...).


so, in the if example above, it would do a partial flush just after
evaluating the conditional, but before the conditional jump.


my newer compiler core (never was fully completed), uses a different
approach, where at the lowest level flushing is not possible (in cases where
it would be needed, instead, the state has to be explicitly saved, but may
delay being restored until actually referenced again). in this system,
usually efficient management of registers is done in the "middle compiler"
(which uses SSA), however, this stage does not really keep track of specific
registers, more just a certain number of certain types (for example, x86: 3
temp GPRs, 3 'var' GPRs, 8 temp SSE regs).

at this stage, the middle compiler is responsible for making sure that any
temp registers are saved before any operations which are allowed to destroy
them (such as function calls), and that any "flexible" state (such as
variables that may change within blocks) are kept in sync prior to
entering/exiting the block.

this compiler does make internal use of a 'phi' operator (basically, it just
makes sure that multiple outputs go to the same place), however, phi is
actually generated implicitly (the input language is RPN based, and so phi
operations are inferred, although some usage restrictions are placed on the
RPN-based input).


but, again, in this case state will be flushed in more or less the same
places: jumps or labels, and function calls (or potentially when using
certain special operations, although most of these special operations take a
"preserve everything" route, trying to behave best as possible like an
atomic operation...).

or such...

Thank you both.

Just to make this message a little bit more than a waste of your eye-
ball movement, I just want to give a little background on my
question. I was doing a project on dependence analysis. In this
context, the example I gave above will give me a sort of spurious
control dependence for the last use of 'x' value after the branch (if
loaded from spill register in the branch). So, if these kind of spill
are common, then it will definitely make a negative impact on the
dependence results. One can probably work around this, but it's kind
of interesting to see how compilers optimizations and architecture-
level conventions can slightly "change" the program semantics, or at
least give headaches to writing program analysis.

Bin