Re: [epsilon-devel] How to write a simple code generation which is not terrible

[Luca Saiu]

This is an update for people who are reading the list.
On 2019-01-31 at 19:00 +0100, Luca Saiu wrote:

> Good.  I didn't think you could make use of this, with your variables
> not in registers.

I've spoken to José since writing this.  It turns out that stack
operands will be very convenient in his use case as well.  In the mean
time I found another excellent argument for stack operands, which are
not only convenient, but actually *better* performing than some
hand-written code.

This example is about read access to a variable with chained environments
implementing closures.

This was my first implementation:

early-header-c
  code
    struct environment
    {
      struct environment *upper;
      jitter_int values [];
    };
  end
end

state-struct-runtime-c
  code
    struct environment *env;
  end
end

# Read a variable and push it onto the main stack.
# The literal arguments are, respectively, a depth and an index.
instruction push-variable (?n 0 1, ?n 0 1 2 3 4 5)
  code
    int i;
    const int depth = JITTER_ARGN0;
    const int index = JITTER_ARGN1;
    jitter_int res;
    for (i = 0; i < depth; i ++)
      JITTER_STATE_RUNTIME_FIELD(env) = JITTER_STATE_RUNTIME_FIELD(env)->upper;
    res = jitter_state_runtime.env->values [index];
    JITTER_PUSH_MAINSTACK(res);
  end
end

It turns out that this generates suboptimal code:
# 0x4230a8: push-variable/n0/n1 (15 bytes):
    0x00007fc1334fe5e1 49 8b 41 10              movq   0x10(%r9),%rax
    0x00007fc1334fe5e5 48 83 c5 08              addq   $0x8,%rbp
    0x00007fc1334fe5e9 48 89 75 00              movq   %rsi,0x0(%rbp)
    0x00007fc1334fe5ed 48 89 c6                 movq   %rax,%rsi
The local variable is read into the temporary %rax, and *then* it's
pushed: the content of %rax will go to the TOS, after the TOS goes to
memory.

It is better to *first* adjust the stack, by leaving the TOS
unspecified, and then reading the variable into it:

instruction push-variable (?n 0 1, ?n 0 1 2 3 4 5)
  code
    int i;
    const int depth = JITTER_ARGN0;
    const int index = JITTER_ARGN1;
    jitter_int res;
    for (i = 0; i < depth; i ++)
      JITTER_STATE_RUNTIME_FIELD(env) = JITTER_STATE_RUNTIME_FIELD(env)->upper;
    res = jitter_state_runtime.env->values [index];
    JITTER_PUSH_MAINSTACK(res);
  end
end

This generates optimal code:
    0x00007f56eb77e5e1 48 89 75 08              movq   %rsi,0x8(%rbp)
    0x00007f56eb77e5e5 49 8b 71 10              movq   0x10(%r9),%rsi
    0x00007f56eb77e5e9 48 83 c5 08              addq   $0x8,%rbp

The optimization would come for free if the stack operand were implicit.
So I've become strongly convinced that this is the right solution:

instruction read-variable (?n 0 1, ?n 0 1 2 3 4 5, !RS)
  code
    const int depth = JITTER_INPUT0;
    const int index = JITTER_INPUT1;
    jitter_int res;
    int i;
    for (i = 0; i < depth; i ++)
      JITTER_STATE_RUNTIME_FIELD(env) = JITTER_STATE_RUNTIME_FIELD(env)->upper;
    res = jitter_state_runtime.env->values [index];
    JITTER_OUTPUT2 = res;
  end
end

Stack operands will come.

-- 
Luca Saiu
* GNU epsilon:           http://www.gnu.org/software/epsilon
* My personal web site:  http://ageinghacker.net

I support everyone's freedom of mocking any opinion or belief, no
matter how deeply held, with open disrespect and the same unrelented
enthusiasm of a toddler who has just learned the word "poo".

signature.asc
Description: PGP signature