Compute next use for each operation argument. Signed-off-by: Kirill Batuzov <batuz...@ispras.ru> --- tcg/tcg.c | 73 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++----- tcg/tcg.h | 4 +++ 2 files changed, 71 insertions(+), 6 deletions(-)
diff --git a/tcg/tcg.c b/tcg/tcg.c index 8748c05..821ffa7 100644 --- a/tcg/tcg.c +++ b/tcg/tcg.c @@ -24,6 +24,7 @@ /* define it to use liveness analysis (better code) */ #define USE_LIVENESS_ANALYSIS +#define USE_ADVANCED_REGALLOC #include "config.h" @@ -1177,7 +1178,8 @@ static inline void tcg_la_func_end(TCGContext *s, uint8_t *dead_temps) /* liveness analysis: end of basic block: globals are live, temps are dead, local temps are live. */ -static inline void tcg_la_bb_end(TCGContext *s, uint8_t *dead_temps) +static inline void tcg_la_bb_end(TCGContext *s, uint8_t *dead_temps, + int *temp_next_use) { int i; TCGTemp *ts; @@ -1185,10 +1187,14 @@ static inline void tcg_la_bb_end(TCGContext *s, uint8_t *dead_temps) memset(dead_temps, 0, s->nb_globals); ts = &s->temps[s->nb_globals]; for(i = s->nb_globals; i < s->nb_temps; i++) { - if (ts->temp_local) + if (ts->temp_local) { dead_temps[i] = 0; - else + } else { dead_temps[i] = 1; +#ifdef USE_ADVANCED_REGALLOC + temp_next_use[i] = -1; +#endif + } ts++; } } @@ -1201,18 +1207,30 @@ static void tcg_liveness_analysis(TCGContext *s) int i, op_index, nb_args, nb_iargs, nb_oargs, arg, nb_ops; TCGOpcode op; TCGArg *args; + int *next_use_ptr = NULL; const TCGOpDef *def; uint8_t *dead_temps; + int *temp_next_use = NULL; unsigned int dead_iargs; - + gen_opc_ptr++; /* skip end */ nb_ops = gen_opc_ptr - gen_opc_buf; s->op_dead_iargs = tcg_malloc(nb_ops * sizeof(uint16_t)); + +#ifdef USE_ADVANCED_REGALLOC + nb_args = gen_opparam_ptr - gen_opparam_buf; + s->param_next_use = tcg_malloc(nb_args * sizeof(s->param_next_use[0])); + next_use_ptr = s->param_next_use + nb_args; +#endif dead_temps = tcg_malloc(s->nb_temps); memset(dead_temps, 1, s->nb_temps); +#ifdef USE_ADVANCED_REGALLOC + temp_next_use = tcg_malloc(s->nb_temps * sizeof(temp_next_use[0])); + memset(temp_next_use, -1, s->nb_temps * sizeof(temp_next_use[0])); +#endif args = gen_opparam_ptr; op_index = nb_ops - 1; @@ -1226,9 +1244,11 @@ static void tcg_liveness_analysis(TCGContext *s) nb_args = args[-1]; args -= nb_args; + next_use_ptr -= nb_args; nb_iargs = args[0] & 0xffff; nb_oargs = args[0] >> 16; args++; + next_use_ptr++; call_flags = args[nb_oargs + nb_iargs]; /* pure functions can be removed if their result is not @@ -1244,10 +1264,23 @@ static void tcg_liveness_analysis(TCGContext *s) } else { do_not_remove_call: +#ifdef USE_ADVANCED_REGALLOC + for (i = 0; i < nb_iargs + nb_oargs; i++) { + if (!dead_temps[args[i]]) { + next_use_ptr[i] = temp_next_use[args[i]]; + } else { + next_use_ptr[i] = -1; + } + } +#endif + /* output args are dead */ for(i = 0; i < nb_oargs; i++) { arg = args[i]; dead_temps[arg] = 1; +#ifdef USE_ADVANCED_REGALLOC + temp_next_use[arg] = -1; +#endif } if (!(call_flags & TCG_CALL_CONST)) { @@ -1263,36 +1296,48 @@ static void tcg_liveness_analysis(TCGContext *s) if (dead_temps[arg]) { dead_iargs |= (1 << i); } +#ifdef USE_ADVANCED_REGALLOC + temp_next_use[arg] = op_index; +#endif dead_temps[arg] = 0; } } s->op_dead_iargs[op_index] = dead_iargs; } args--; + next_use_ptr--; } break; case INDEX_op_set_label: args--; + next_use_ptr--; /* mark end of basic block */ - tcg_la_bb_end(s, dead_temps); + tcg_la_bb_end(s, dead_temps, temp_next_use); break; case INDEX_op_debug_insn_start: args -= def->nb_args; + next_use_ptr -= def->nb_args; break; case INDEX_op_nopn: nb_args = args[-1]; args -= nb_args; + next_use_ptr -= nb_args; break; case INDEX_op_discard: args--; + next_use_ptr--; /* mark the temporary as dead */ dead_temps[args[0]] = 1; +#ifdef USE_ADVANCED_REGALLOC + temp_next_use[args[0]] = -1; +#endif break; case INDEX_op_end: break; /* XXX: optimize by hardcoding common cases (e.g. triadic ops) */ default: args -= def->nb_args; + next_use_ptr -= def->nb_args; nb_iargs = def->nb_iargs; nb_oargs = def->nb_oargs; @@ -1312,15 +1357,28 @@ static void tcg_liveness_analysis(TCGContext *s) } else { do_not_remove: +#ifdef USE_ADVANCED_REGALLOC + for (i = 0; i < nb_iargs + nb_oargs; i++) { + if (!dead_temps[args[i]]) { + next_use_ptr[i] = temp_next_use[args[i]]; + } else { + next_use_ptr[i] = -1; + } + } +#endif + /* output args are dead */ for(i = 0; i < nb_oargs; i++) { arg = args[i]; dead_temps[arg] = 1; +#ifdef USE_ADVANCED_REGALLOC + temp_next_use[arg] = -1; +#endif } /* if end of basic block, update */ if (def->flags & TCG_OPF_BB_END) { - tcg_la_bb_end(s, dead_temps); + tcg_la_bb_end(s, dead_temps, temp_next_use); } else if (def->flags & TCG_OPF_CALL_CLOBBER) { /* globals are live */ memset(dead_temps, 0, s->nb_globals); @@ -1333,6 +1391,9 @@ static void tcg_liveness_analysis(TCGContext *s) if (dead_temps[arg]) { dead_iargs |= (1 << i); } +#ifdef USE_ADVANCED_REGALLOC + temp_next_use[arg] = op_index; +#endif dead_temps[arg] = 0; } s->op_dead_iargs[op_index] = dead_iargs; diff --git a/tcg/tcg.h b/tcg/tcg.h index cecef63..d8bfa2c 100644 --- a/tcg/tcg.h +++ b/tcg/tcg.h @@ -288,10 +288,14 @@ struct TCGContext { /* liveness analysis */ uint16_t *op_dead_iargs; /* for each operation, each bit tells if the corresponding input argument is dead */ + int *param_next_use; /* for each operation argument tells where it's + next used is (USE_ADVANCED_REGALLOC only) */ /* tells in which temporary a given register is. It does not take into account fixed registers */ int reg_to_temp[TCG_TARGET_NB_REGS]; + /* tells where the next use of a given reg appears */ + int reg_next_use[TCG_TARGET_NB_REGS]; TCGRegSet reserved_regs; tcg_target_long current_frame_offset; tcg_target_long frame_start; -- 1.7.4.1