Re: [patch i386]: Combine memory and indirect jump

[Kai Tietz <ktietz70 at googlemail dot com>]

2014-06-13 17:58 GMT+02:00 Jeff Law <law@redhat.com>:
> On 06/13/14 09:56, Richard Henderson wrote:
>>
>> On 06/13/2014 08:36 AM, Jeff Law wrote:
>>>
>>> So you may have answered this already, but why can't this be a combiner
>>> pattern?
>>
>>
>> Until pass_duplicate_computed_gotos, we (intentionally) have a single
>> indirect
>> branch in the entire function.  This vastly reduces the size of the CFG.
>
> Ah, the factoring bits.  Should have known.
>
>
>>
>> Peep2 is currently running before d_c_g, so currently Kai can't solve this
>> problem in peep2.
>>
>> I don't think peep2 should run after sched2, but I'll bet we can reorder
>> things
>> a bit so that d_c_g runs before peep2.
>
> Yea, seems worth a try.
>
> jeff
>

Well, I tested to put the second sched2 pass before the sched2 pass.
That works in general.  There are just some opportunties which weren't
caught then.  I attached a sample, which demonstrates that pretty
well.  I noticed that I had to put that pass behind reload blocks was
necessary for better hit-rate of the peephole optimization.

Kai

// PR 51840/
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

enum {
  S_atop   = 0,
  S_atop_f = 1,
  S_atop_t = 2,
  S_limit  = 3
};

enum {
  I_a_dec        = 0,
  I_a_non_zero_p = 1,
  I_jmp_if_true  = 2,
  I_exit         = 3,
  I_limit        = 4
};


typedef struct {
  uint64_t a0;
} vm_state_t;


__attribute__((noinline, noclone)) void exec_code(vm_state_t *state, uint8_t *code) {
  static void (* volatile const vm_dispatch[S_limit][I_limit]) = {
    //dispatch for [S_atop = 0][..] with four unique destination labels
    {&&atop__a_dec,
     &&atop__a_non_zero_p,
     &&fixme,
     &&atop__exit},

    //dispatch for [S_atop_f = 1][..] with two unique destination labels
    {&&fixme,
     &&fixme,
     &&atop_f__jmp_if_true,
     &&fixme},

    //dispatch for [S_atop_t = 2][..] with two unique destination labels
    {&&fixme,
     &&fixme,
     &&atop_t__jmp_if_true,
     &&fixme}
  };

  printf("atop__a_dec:         %p\n", &&atop__a_dec);
  printf("atop__a_non_zero_p:  %p\n", &&atop__a_non_zero_p);
  printf("atop__exit:          %p\n", &&atop__exit);
  printf("atop_f__jmp_if_true: %p\n", &&atop_f__jmp_if_true);
  printf("atop_t__jmp_if_true: %p\n", &&atop_t__jmp_if_true);
  printf("fixme:               %p\n", &&fixme);

  volatile uint64_t atop = state->a0;
  volatile int64_t inst_offset=0;

  goto *(vm_dispatch[S_atop][code[inst_offset]]);

 atop__a_dec: {
    printf("atop = %ld\n", atop);
    --atop;
    volatile uint64_t next_inst = code[inst_offset + 1];
    inst_offset += 1;
    goto *(vm_dispatch[S_atop][next_inst]);
  }

 atop__a_non_zero_p: {
    volatile uint64_t next_inst = code[inst_offset + 1];
    inst_offset += 1;
    if (atop != 0) {
      goto *(vm_dispatch[S_atop_t][next_inst]);
    } else {
      goto *(vm_dispatch[S_atop_f][next_inst]);
    }
  }

 atop_f__jmp_if_true: {
    volatile uint64_t next_inst = code[inst_offset + 2];
    inst_offset += 2;
    goto *(vm_dispatch[S_atop][next_inst]);
  }

 atop_t__jmp_if_true: {
    int64_t offset = (int8_t) code[inst_offset + 1];
    uint64_t next_inst = code[inst_offset + offset];
    inst_offset += offset;
    goto *(vm_dispatch[S_atop][next_inst]);
  }

 atop__exit: {
    state->a0 = atop;
    return;
  }

 fixme: {
    printf("Dispatch logic ERROR\n");
    exit(EXIT_FAILURE);
  }
}

int main(void)u
{
  vm_state_t state;
  state.a0     = 10;
  uint8_t code[] = {I_a_dec,           //decrement top of stack
		    I_a_non_zero_p,    //true if top of stack is non-zero
		    I_jmp_if_true, -2, //if true jump back to decrement
		    I_exit};           //otherwise exit

  exec_code(&state, code);
  return EXIT_SUCCESS;
}