The holy GCC

After running the benchmarks compiled using llvm-gcc and making sure that the technique was working, it was time to modify gcc. In order to take advantage of gcc's optimizations, I changed my strategy a little bit and modified the RTL generation phase to generate code for upward growing stack. Modifying code generation phase was still inevitable, because our target was x86 that only supported downward growing stack and some instructions should have been augmented with extra instructions to work properly when stack grew upward.

One of the instructions in x86 which is difficult to transform for upward growing stack, is RET <16-bit Integer>. This instruction pops the return address from the stack and internally increments the stack pointer (SP) by the value of its operand and then jumps to the popped return address. When stack grows upward, the stack pointer should be decremented rather than incremented. Now if we replace this instruction with an instruction that decrements the stack pointer and a normal (with no operand) RET instruction, the value that the RET reads is not the correct return address, because the stack pointer no longer points to the return address.

A solution to this problem is using a set of instructions to read the return address and store it in a temporary register, decrement the stack pointer and jump indirectly to the temporary register. We use ECX as the temporary register, because it is a volatile register that is assumed to be clobbered after a function call and it is not used to return values to the caller too.

The value that is decremented from the stack pointer should be <RET operand> minus 4. The reason is that the stack pointer is decremented by 4 after all CALL instructions (refer to this article). The SP is adjusted to compensate the amount added to it by a RET instruction. Now that we remove the RET instruction the SP should not be adjusted after CALLs to these functions. By subtracting 4 from the value, we eliminate the effect of the SP adjustment after the CALL instructions.

If you are interested in the details of instruction augmentation for reverse stack, you can take a look at this article.