Reserve the frame register in RegAlloc when needed

[dylanmckay]

The AVR stack frame register is the Y pointer register (R29:R28).

The stack frame register only needs to be used if a function has spills, otherwise the register allocator is free to do with it as it pleases.

The way this optimization is currently achieved is the definition of a nasty hack.

We define several global variables inside the register allocator (see RegAllocGreedy.cpp), which are externally set in the AVR backend when a stack spill is generated.

The reason this problem is so hard is because we tell if we need to reserve the frame pointer based on whether or not there were any registers spilled in a function. We only know that once register allocation runs. If we let regalloc run without telling it about the reserved register, it will use it.

Ideally the register allocator would support this by default.

[dylanmckay]

This issue is stopping us from using any other register allocator than RegAllocGreedy.cpp, because the other allocators don't support our hacks.

[bootchk]

The AVR ISR does not mention a frame pointer and modern gcc by default does not use a frame pointer. Wiki and elsewhere says a frame pointer is a convenience that enables debuggers to print nice stack traces. I don't think llvm requires a frame pointer. Is it just the AVR backend that introduces the notion of frame pointer? Why?

Also, if #161 fixes this, shouldn't this issue be closed (unless we DO need a frame pointer?)

[dylanmckay]

If we don't actually need the frame pointer, that's great!

I'll investigate this one I get home :)

[bootchk]

A stack frame is the portion of the stack allocated for a function call. A frame pointer points to a frame. A compiler MAY dedicate a register to a frame pointer. A compiler MAY push a frame pointer onto the stack as part of a frame, letting a debugger walk the frames and produce a back trace (a call stack.) Such a scheme is old-school, since modern compilers/frameworks (like recent gcc and llvm) can use several other schemes letting debuggers work.

http://yosefk.com/blog/getting-the-call-stack-without-a-frame-pointer.html

So whether avr-llvm needs to use a dedicated frame pointer register might depend only on what other (old-school) tools you want to play friendly with.

I don’t think you need a dedicated frame pointer register to support register spills.

I could be mistaken.

[dylanmckay]

@bootchk: From what I can tell, we still need a frame pointer in the case of variable sized allocas. If we push arbitrary sizes values onto the stack, the only way (as far as I can tell) is to store the frame pointer and restore it afterwards.

I quickly checked Mips and ARM, and they both have frame pointers for this specific case.

[dylanmckay]

Your comments made me think a bit more, any why our backend does this and no others do.

We reserve the Y register if a function has spills. This is super conservative, and I'm pretty sure does not need to be done. Spills by themselves become push/pop instructions, which do not require a frame pointer.

The hack mentioned in this issue is just a workaround so that we can reserve the FP in the case we have spills. I think it should be sufficient to remove the hack.