@@ -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;
@@ -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;
Compute next use for each operation argument. Signed-off-by: Kirill Batuzov <batuzovk@ispras.ru> --- tcg/tcg.c | 73 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++----- tcg/tcg.h | 4 +++ 2 files changed, 71 insertions(+), 6 deletions(-)