[v3,5/9] tcg: Reorg TCGOp chaining

Instead of using -1 as end of chain, use 0, and link through the 0
entry as a fully circular double-linked list.

Signed-off-by: Richard Henderson <rth@twiddle.net>
---
 include/exec/gen-icount.h |  2 +-
 tcg/optimize.c            |  8 ++------
 tcg/tcg-op.c              |  2 +-
 tcg/tcg.c                 | 32 ++++++++++++--------------------
 tcg/tcg.h                 | 20 ++++++++++++--------
 5 files changed, 28 insertions(+), 36 deletions(-)

On 2016-06-23 20:48, Richard Henderson wrote:
> Instead of using -1 as end of chain, use 0, and link through the 0
> entry as a fully circular double-linked list.
> 
> Signed-off-by: Richard Henderson <rth@twiddle.net>
> ---
>  include/exec/gen-icount.h |  2 +-
>  tcg/optimize.c            |  8 ++------
>  tcg/tcg-op.c              |  2 +-
>  tcg/tcg.c                 | 32 ++++++++++++--------------------
>  tcg/tcg.h                 | 20 ++++++++++++--------
>  5 files changed, 28 insertions(+), 36 deletions(-)
> 
> diff --git a/include/exec/gen-icount.h b/include/exec/gen-icount.h
> index a011324..5f16077 100644
> --- a/include/exec/gen-icount.h
> +++ b/include/exec/gen-icount.h
> @@ -59,7 +59,7 @@ static void gen_tb_end(TranslationBlock *tb, int num_insns)
>      }
>  
>      /* Terminate the linked list.  */
> -    tcg_ctx.gen_op_buf[tcg_ctx.gen_last_op_idx].next = -1;
> +    tcg_ctx.gen_op_buf[tcg_ctx.gen_op_buf[0].prev].next = 0;
>  }
>  
>  static inline void gen_io_start(void)
> diff --git a/tcg/optimize.c b/tcg/optimize.c
> index c0d975b..8df7fc7 100644
> --- a/tcg/optimize.c
> +++ b/tcg/optimize.c
> @@ -103,11 +103,7 @@ static TCGOp *insert_op_before(TCGContext *s, TCGOp *old_op,
>          .prev = prev,
>          .next = next
>      };
> -    if (prev >= 0) {
> -        s->gen_op_buf[prev].next = oi;
> -    } else {
> -        s->gen_first_op_idx = oi;
> -    }
> +    s->gen_op_buf[prev].next = oi;
>      old_op->prev = oi;
>  
>      return new_op;
> @@ -583,7 +579,7 @@ void tcg_optimize(TCGContext *s)
>      nb_globals = s->nb_globals;
>      reset_all_temps(nb_temps);
>  
> -    for (oi = s->gen_first_op_idx; oi >= 0; oi = oi_next) {
> +    for (oi = s->gen_op_buf[0].next; oi != 0; oi = oi_next) {
>          tcg_target_ulong mask, partmask, affected;
>          int nb_oargs, nb_iargs, i;
>          TCGArg tmp;
> diff --git a/tcg/tcg-op.c b/tcg/tcg-op.c
> index 569cdc6..62d91b4 100644
> --- a/tcg/tcg-op.c
> +++ b/tcg/tcg-op.c
> @@ -52,7 +52,7 @@ static void tcg_emit_op(TCGContext *ctx, TCGOpcode opc, int args)
>      int pi = oi - 1;
>  
>      tcg_debug_assert(oi < OPC_BUF_SIZE);
> -    ctx->gen_last_op_idx = oi;
> +    ctx->gen_op_buf[0].prev = oi;
>      ctx->gen_next_op_idx = ni;
>  
>      ctx->gen_op_buf[oi] = (TCGOp){
> diff --git a/tcg/tcg.c b/tcg/tcg.c
> index 400e69c..bb1efe2 100644
> --- a/tcg/tcg.c
> +++ b/tcg/tcg.c
> @@ -437,9 +437,9 @@ void tcg_func_start(TCGContext *s)
>      s->goto_tb_issue_mask = 0;
>  #endif
>  
> -    s->gen_first_op_idx = 0;
> -    s->gen_last_op_idx = -1;
> -    s->gen_next_op_idx = 0;
> +    s->gen_op_buf[0].next = 1;
> +    s->gen_op_buf[0].prev = 0;
> +    s->gen_next_op_idx = 1;
>      s->gen_next_parm_idx = 0;
>  
>      s->be = tcg_malloc(sizeof(TCGBackendData));
> @@ -868,7 +868,7 @@ void tcg_gen_callN(TCGContext *s, void *func, TCGArg ret,
>      /* Make sure the calli field didn't overflow.  */
>      tcg_debug_assert(s->gen_op_buf[i].calli == real_args);
>  
> -    s->gen_last_op_idx = i;
> +    s->gen_op_buf[0].prev = i;
>      s->gen_next_op_idx = i + 1;
>      s->gen_next_parm_idx = pi;
>  
> @@ -1004,7 +1004,7 @@ void tcg_dump_ops(TCGContext *s)
>      TCGOp *op;
>      int oi;
>  
> -    for (oi = s->gen_first_op_idx; oi >= 0; oi = op->next) {
> +    for (oi = s->gen_op_buf[0].next; oi != 0; oi = op->next) {
>          int i, k, nb_oargs, nb_iargs, nb_cargs;
>          const TCGOpDef *def;
>          const TCGArg *args;
> @@ -1016,7 +1016,7 @@ void tcg_dump_ops(TCGContext *s)
>          args = &s->gen_opparam_buf[op->args];
>  
>          if (c == INDEX_op_insn_start) {
> -            qemu_log("%s ----", oi != s->gen_first_op_idx ? "\n" : "");
> +            qemu_log("%s ----", oi != s->gen_op_buf[0].next ? "\n" : "");
>  
>              for (i = 0; i < TARGET_INSN_START_WORDS; ++i) {
>                  target_ulong a;
> @@ -1287,18 +1287,10 @@ void tcg_op_remove(TCGContext *s, TCGOp *op)
>      int next = op->next;
>      int prev = op->prev;
>  
> -    if (next >= 0) {
> -        s->gen_op_buf[next].prev = prev;
> -    } else {
> -        s->gen_last_op_idx = prev;
> -    }
> -    if (prev >= 0) {
> -        s->gen_op_buf[prev].next = next;
> -    } else {
> -        s->gen_first_op_idx = next;
> -    }
> +    s->gen_op_buf[next].prev = prev;
> +    s->gen_op_buf[prev].next = next;
>  
> -    memset(op, -1, sizeof(*op));
> +    memset(op, 0, sizeof(*op));

Doing so means you can remove the op at gen_op_buf[0]. The doubled
linked list is still valid, but then I guess you can't assume anymore
that the first op is gen_op_buf[0], as it is done elsewhere your patch.

I guess it's unlikely to happen that we have to remove the first op.
Maybe adding an assert there is enough?


>  #ifdef CONFIG_PROFILER
>      s->del_op_count++;
> @@ -1344,7 +1336,7 @@ static void tcg_liveness_analysis(TCGContext *s)
>      mem_temps = tcg_malloc(s->nb_temps);
>      tcg_la_func_end(s, dead_temps, mem_temps);
>  
> -    for (oi = s->gen_last_op_idx; oi >= 0; oi = oi_prev) {
> +    for (oi = s->gen_op_buf[0].prev; oi != 0; oi = oi_prev) {
>          int i, nb_iargs, nb_oargs;
>          TCGOpcode opc_new, opc_new2;
>          bool have_opc_new2;
> @@ -2321,7 +2313,7 @@ int tcg_gen_code(TCGContext *s, TranslationBlock *tb)
>      {
>          int n;
>  
> -        n = s->gen_last_op_idx + 1;
> +        n = s->gen_op_buf[0].prev + 1;
>          s->op_count += n;
>          if (n > s->op_count_max) {
>              s->op_count_max = n;
> @@ -2380,7 +2372,7 @@ int tcg_gen_code(TCGContext *s, TranslationBlock *tb)
>      tcg_out_tb_init(s);
>  
>      num_insns = -1;
> -    for (oi = s->gen_first_op_idx; oi >= 0; oi = oi_next) {
> +    for (oi = s->gen_op_buf[0].next; oi != 0; oi = oi_next) {
>          TCGOp * const op = &s->gen_op_buf[oi];
>          TCGArg * const args = &s->gen_opparam_buf[op->args];
>          TCGOpcode opc = op->opc;
> diff --git a/tcg/tcg.h b/tcg/tcg.h
> index cc14560..49b396d 100644
> --- a/tcg/tcg.h
> +++ b/tcg/tcg.h
> @@ -520,17 +520,21 @@ typedef struct TCGOp {
>      unsigned callo  : 2;
>      unsigned calli  : 6;
>  
> -    /* Index of the arguments for this op, or -1 for zero-operand ops.  */
> -    signed args     : 16;
> +    /* Index of the arguments for this op, or 0 for zero-operand ops.  */
> +    unsigned args   : 16;
>  
> -    /* Index of the prex/next op, or -1 for the end of the list.  */
> -    signed prev     : 16;
> -    signed next     : 16;
> +    /* Index of the prex/next op, or 0 for the end of the list.  */

It's not introduced by your patch, but you might want to fix the typo
prex -> prev.

> +    unsigned prev   : 16;
> +    unsigned next   : 16;
>  } TCGOp;
>  
> -QEMU_BUILD_BUG_ON(NB_OPS > 0xff);
> -QEMU_BUILD_BUG_ON(OPC_BUF_SIZE >= 0x7fff);
> -QEMU_BUILD_BUG_ON(OPPARAM_BUF_SIZE >= 0x7fff);
> +/* Make sure operands fit in the bitfields above.  */
> +QEMU_BUILD_BUG_ON(NB_OPS > (1 << 8));
> +QEMU_BUILD_BUG_ON(OPC_BUF_SIZE > (1 << 16));
> +QEMU_BUILD_BUG_ON(OPPARAM_BUF_SIZE > (1 << 16));
> +
> +/* Make sure that we don't overflow 64 bits without noticing.  */
> +QEMU_BUILD_BUG_ON(sizeof(TCGOp) > 8);
>  
>  struct TCGContext {
>      uint8_t *pool_cur, *pool_end;

It seems that gen_first_op_idx and gen_last_op_idx are now unused.
Shouldn't they be removed?

On 07/25/2016 04:53 PM, Aurelien Jarno wrote:
> On 2016-06-23 20:48, Richard Henderson wrote:
>> @@ -1287,18 +1287,10 @@ void tcg_op_remove(TCGContext *s, TCGOp *op)
>>      int next = op->next;
>>      int prev = op->prev;
>>
>> -    if (next >= 0) {
>> -        s->gen_op_buf[next].prev = prev;
>> -    } else {
>> -        s->gen_last_op_idx = prev;
>> -    }
>> -    if (prev >= 0) {
>> -        s->gen_op_buf[prev].next = next;
>> -    } else {
>> -        s->gen_first_op_idx = next;
>> -    }
>> +    s->gen_op_buf[next].prev = prev;
>> +    s->gen_op_buf[prev].next = next;
>>
>> -    memset(op, -1, sizeof(*op));
>> +    memset(op, 0, sizeof(*op));
>
> Doing so means you can remove the op at gen_op_buf[0]. The doubled
> linked list is still valid, but then I guess you can't assume anymore
> that the first op is gen_op_buf[0], as it is done elsewhere your patch.
>
> I guess it's unlikely to happen that we have to remove the first op.
> Maybe adding an assert there is enough?

Assert added.

>> -    /* Index of the prex/next op, or -1 for the end of the list.  */
>> -    signed prev     : 16;
>> -    signed next     : 16;
>> +    /* Index of the prex/next op, or 0 for the end of the list.  */
>
> It's not introduced by your patch, but you might want to fix the typo
> prex -> prev.

Fixed.

> It seems that gen_first_op_idx and gen_last_op_idx are now unused.
> Shouldn't they be removed?

Yep, fixed.


r~