Make the SSA register tracker understand RSP

[pgoodman]

At the moment, 6_track_ssa_vars.cc ignores the stack pointer as an operand; however, in hindsight this might not have been the best solution.

As far as I recall, part of the motivation for this was to prevent copy propagations across changes to the stack pointer, but in practice, this shouldn't be a real concern because the copy propagation step already handles this in a general way for all other registers.

The drawback of excluding the stack pointer from SSA tracking (and therefore copy propagation) is that it introduces extra virtual registers and instructions to handle memory reads/writes to the stack, (i.e. requiring an LEA to compute the memory address, then reading/writing to that address), where only one instruction need be used.

If this can't be applied for all cases, then perhaps it could be applied for the case where there is at least one fragment in a fragment partition such that the fragment's stack is marked as invalid. This would mean moving a minor analysis step forward (from 9_allocate_slots.cc).

[pgoodman]

I think this could be a reasonably high-priority task, as it definitely affects the quality of generated code.

[pgoodman]

This paper roughly describes Granary's SSA construction. A key difference between the two is how the paper's approach and Granary go about replacing / removing PHI nodes. In Granary's code, replacement happens by overwriting the memory in-place using C++'s placement new syntax. Also, Granary introduces an a form of alias that is a stand-in for "uncertainty" during the SSA construction process.

That is, we process one block at a time, and if we see some dependency on a register, but no definition of that register, then we add the register as a control PHI node in the incoming registers to a fragment. Later, we perform the same PHI trivialization step as in the paper, but instead of replacing trivial PHIs, we overwrite them with alias nodes.

[pgoodman]

Another thing to look into would be to drop the distinction between uses and defs in SSAInstruction as it only seems to get in the way later on.

[pgoodman]

Suggestion approach: test changes using gtest. For example:

make clean test GRANARY_TARGET=test
./bin/test_granary_user/granary.out --gtest_filter=<something here>

What would be good would be to create a small assembly test case in test/arch/x86-64/. For example, see this and this for an example. Two tests should be sufficient: one test that does something like:

push rdi
push rdi
mov rax, [rsp + 8]
lea rsp, [rsp + 16]
ret

And then something more tricky that makes granary think the stack is invalid. For example:

mov rax, 8
sub rsp, rax  // Shift by an unknown amount.
...

[pgoodman]

What you're looking for in testing is

1. That things still work.
2. When you look at the generated code (run with --debug_log_fragments) then you see that the instruction mov rax, [rsp + 8] remains, and hasn't been split into two or more instructions (where one computes lea <reg>, [rsp + 8].