Version 9 (modified by dias, 9 years ago) (diff)


Stack Layout

The old approach

In the old code generator, most of the pipeline refers to variables by name. In fact, we have a phase ordering problem: no compiler phase can name a stack slot until stack layout has been fixed. But stack layout can only be fixed at the end of the pipeline. The consequence of this approach is that we have to provide special treatment for code that must refer to stack slots (e.g. parameter passing in calling conventions, or spills and reloads). In particular, we defined special instructions for CopyIn and CopyOut of function arguments. Every stage of the back end must cope with these special cases.

The new approach

A better approach is to introduce a unique name for each stack slot, then treat the name as the addressing expression for the slot. At the end of the pipeline, we choose a stack layout, then replace each stack slot with its offset from the stack pointer. The benefit is that we break the phase-ordering problem: any phase of the compiler can name a stack slot.

For example

The current conversion from STG to CMM leaves stack management completely implicit. The consequence is that a number of things must happen all at once:

  • The stack is laid out.
  • CopyIn and CopyOut nodes are converted to the appropriate moves, loads and stores, as required by the calling conventions.
  • The stack pointer is adjusted to conventional locations before and after function calls.
  • The return address is pushed on the stack at call sites.

And of course, none of the argument-passing or stack-adjusting instructions are available during optimization, before the stack layout is fixed.

A much better approach is to give symbolic names to locations on the stack, lower all the argument passing and stack adjusting to the actual data-movement instructions, and replace the names later when the final stack layout is fixed.

For example

f(x) {
   y = x;

   call g(x) returning to L;


should be compiled to

   x = m[stack(f, 1)]; // copy the argument from stack area `f' to local x
   y = x;


   sp = stack(L, 1); // Make room on the stack for the arguments
   m[stack(L, 1)] = L; // copy the return address
   m[stack(L, 0)] = x; // copy the argument
   call g();


The exact syntax will probably be a bit different, but there's the gist of it.

But how do we map the stack slots to actual hardware locations? As it turns out, it is quite common in GHC that the first definition of a variable comes when its value is returned from a function call. If the value is returned on the stack, then an important optimization is to avoid copying that value to some other local location on the stack. How is that achieved? By making sure the location where the value is returned is defined as its local location.

For example,

f() {
  x = g();

If g() returns x on the stack, we would like the return location to be x's stack slot for the rest of the procedure. Issues raised by this:

  • Stack holes where return addresses were stored. Such a hole can be filled with a variable that can't be stored in a convenient return slot.
  • Stack allocation must be based on control flow -- how else would you know if x has already been placed or if it can be stored on the bottom of the stack?

Attachments (2)

Download all attachments as: .zip