Register spilling in caller saved backend

Hey,

I’m playing around with a backend with no callee saved registers and noticed more spilling than seems needed. I tried digging into the spilling code but with limited success. I also tried removing all the callee saved registers in the X86 backend and saw the same effect (basically making CSRs equal to CSR_NoRegs). So I seem to be misunderstanding something or missing something simple, and thought I’d ask.

Consider this program as an example:

volatile int x;

int attribute((noinline)) foo() { return x; }

int main() {
for (int i = 0; i < 10; ++i) {
foo();
}
}

The resultant output code spills ‘i’ within the loop (I have to compile with -fno-unroll-loops else the loop and ‘i’ gets optimized away) while ‘i’ is assigned to a register that is used nowhere else in the generated program and I would consider ‘foo’ easy to analyse. At the call site of ‘foo’ the debugging output reports that the stack pointer and return value registers are “imp-use” and “imp-def” and no other registers are used.

Should the spilling have occurred? Or this due to some feature in the backend that is missing?

Thanks,

Jacques

int main() {
  for (int i = 0; i < 10; ++i) {
    foo();
  }
}

The resultant output code spills 'i' within the loop (I have to
compile with -fno-unroll-loops else the loop and 'i' gets optimi! zed
away) while 'i' is assigned to a register that is used nowhere else in
the generated program and I would consider 'foo' easy to analyse. At
the call site of 'foo' the debugging output reports that the stack
pointer and return value registers are "imp-use" and "imp-def" and no
other registers are used.

When a function (such as main() in this case) is compiled, all calls to
functions are assumed to clobber all caller saved registers. Since your
backend said that all registers are caller saved, then the compiler has
not choice but to spill 'i' around the call to foo(), since it may
trash the register 'i' is allocated to.

Should the spilling have occurred? Or this due to some feature in the
backend that is missing?

This is totally as expected when you have no callee saved registers.

Peter

Hi Jacques,

Could you attach the MachineInstr before and after register allocation?

This is hard to give an answer without seeing the actual CFG and live-ranges.

Thanks,
Q.

What are you expectating here? Are you expecting the backend to recognize that foo doesn’t actually clobber any registers? I don’t believe we do that today. Without callee saved registers, if the value ‘i’ needs to be preserved across the call, it will need to be spilled. There’s no register we can put it in without it being clobbered.

Yes that was what I was hoping for as it seems that all the information is
there to do that. So at the moment if there is a case such as this then the
backend should have some designated callee saved registers. That makes
sense if that information isn't being used at the moment then we can't know
if the register will be clobbered or not and have to assume it will.

Thanks

Hi Jacques,

Looked at the MIs you sent me and +1 to all that Philip said.
I is live across the call of foo, and since we do not have any CSR to preserve it, we must spill.

Cheers,
Q.

Note that it would be very unusual to have no callee saved registers.

Historically (pre-RISC), it was normal to pass arguments on the stack and have ALL registers callee saved. Or maybe to have just one or two registers that could be clobbered by the called function, or linkage code.

Some IBM compilers did this. We called it register resurrection.
Basically you need a call graph, so this is limited to interprocedural
optimization or statically defined called functions (locally defined
like your example here is ok too, provided you are not compiling for
a shared library, since locally defined functions can be overridden).
You then need to do register allocation on the functions in the call
graph from the leaves up. You can then promote some of the caller
saved registers for function foo() to callee saved if they were never
clobbered within foo(). This allows callers of foo() to see extra
callee saved registers at foo() call points. Of course, you have to
assume the worst when you encounter recursion in your call graph.

Peter