[Qemu-devel] [RFC][PATCH v0 1/8] Compute additional liveness information for register allocator.

[Kirill Batuzov]

Compute next use for each operation argument.

Signed-off-by: Kirill Batuzov <address@hidden>
---
 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