[Qemu-devel] [PATCH 2/6] Add copy and constant propagation.

[Kirill Batuzov <batuzovk@ispras.ru>]

Make tcg_constant_folding do copy and constant propagation. It is a
preparational work before actual constant folding.

Signed-off-by: Kirill Batuzov <batuzovk@ispras.ru>
---
 tcg/optimize.c |  123 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 123 insertions(+), 0 deletions(-)

diff --git a/tcg/optimize.c b/tcg/optimize.c
index cf31d18..a761c51 100644
--- a/tcg/optimize.c
+++ b/tcg/optimize.c
@@ -31,22 +31,139 @@
 #include "qemu-common.h"
 #include "tcg-op.h"
 
+typedef enum {
+    TCG_TEMP_UNDEF = 0,
+    TCG_TEMP_CONST,
+    TCG_TEMP_COPY,
+    TCG_TEMP_ANY
+} tcg_temp_state;
+
+static int mov_to_movi(int op)
+{
+    switch (op) {
+    case INDEX_op_mov_i32: return INDEX_op_movi_i32;
+#if TCG_TARGET_REG_BITS == 64
+    case INDEX_op_mov_i64: return INDEX_op_movi_i64;
+#endif
+    default:
+        fprintf(stderr, "Unrecognized operation %d in mov_to_movi.\n", op);
+        tcg_abort();
+    }
+}
+
+/* Reset TEMP's state to TCG_TEMP_ANY.  If TEMP was a representative of some
+   class of equivalent temp's, a new representative should be chosen in this
+   class. */
+static void reset_temp(tcg_temp_state *state, tcg_target_ulong *vals,
+                       TCGArg temp, int nb_temps, int nb_globals)
+{
+    int i;
+    TCGArg new_base;
+    new_base = (TCGArg)-1;
+    for (i = nb_globals; i < nb_temps; i++) {
+        if (state[i] == TCG_TEMP_COPY && vals[i] == temp) {
+            if (new_base == ((TCGArg)-1)) {
+                new_base = (TCGArg)i;
+                state[i] = TCG_TEMP_ANY;
+            } else {
+                vals[i] = new_base;
+            }
+        }
+    }
+    for (i = 0; i < nb_globals; i++) {
+        if (state[i] == TCG_TEMP_COPY && vals[i] == temp) {
+            if (new_base == ((TCGArg)-1)) {
+                state[i] = TCG_TEMP_ANY;
+            } else {
+                vals[i] = new_base;
+            }
+        }
+    }
+    state[temp] = TCG_TEMP_ANY;
+}
+
+/* Propagate constants and copies, fold constant expressions. */
 static TCGArg *tcg_constant_folding(TCGContext *s, uint16_t *tcg_opc_ptr,
                                     TCGArg *args, TCGOpDef *tcg_op_defs)
 {
     int i, nb_ops, op_index, op, nb_temps, nb_globals;
     const TCGOpDef *def;
     TCGArg *gen_args;
+    /* Array VALS has an element for each temp.
+       If this temp holds a constant then its value is kept in VALS' element.
+       If this temp is a copy of other ones then this equivalence class'
+       representative is kept in VALS' element.
+       If this temp is neither copy nor constant then corresponding VALS'
+       element is unused. */
+    static tcg_target_ulong vals[TCG_MAX_TEMPS];
+    static tcg_temp_state state[TCG_MAX_TEMPS];
 
     nb_temps = s->nb_temps;
     nb_globals = s->nb_globals;
+    memset(state, 0, nb_temps * sizeof(tcg_temp_state));
 
     nb_ops = tcg_opc_ptr - gen_opc_buf;
     gen_args = args;
     for (op_index = 0; op_index < nb_ops; op_index++) {
         op = gen_opc_buf[op_index];
         def = &tcg_op_defs[op];
+        /* Do copy propagation */
+        if (op != INDEX_op_call) {
+            for (i = def->nb_oargs; i < def->nb_oargs + def->nb_iargs; i++) {
+                if (state[args[i]] == TCG_TEMP_COPY
+                    && !(def->args_ct[i].ct & TCG_CT_IALIAS)
+                    && (def->args_ct[i].ct & TCG_CT_REG)) {
+                    args[i] = vals[args[i]];
+                }
+            }
+        }
+
+        /* Propagate constants through copy operations and do constant
+           folding.  Constants will be substituted to arguments by register
+           allocator where needed and possible.  Also detect copies. */
         switch (op) {
+        case INDEX_op_mov_i32:
+#if TCG_TARGET_REG_BITS == 64
+        case INDEX_op_mov_i64:
+#endif
+            if ((state[args[1]] == TCG_TEMP_COPY
+                && vals[args[1]] == args[0])
+                || args[0] == args[1]) {
+                args += 2;
+                gen_opc_buf[op_index] = INDEX_op_nop;
+                break;
+            }
+            if (state[args[1]] != TCG_TEMP_CONST) {
+                reset_temp(state, vals, args[0], nb_temps, nb_globals);
+                if (args[1] >= s->nb_globals) {
+                    state[args[0]] = TCG_TEMP_COPY;
+                    vals[args[0]] = args[1];
+                }
+                gen_args[0] = args[0];
+                gen_args[1] = args[1];
+                gen_args += 2;
+                args += 2;
+                break;
+            } else {
+                /* Source argument is constant.  Rewrite the operation and
+                   let movi case handle it. */
+                op = mov_to_movi(op);
+                gen_opc_buf[op_index] = op;
+                args[1] = vals[args[1]];
+                /* fallthrough */
+            }
+        case INDEX_op_movi_i32:
+#if TCG_TARGET_REG_BITS == 64
+        case INDEX_op_movi_i64:
+#endif
+            reset_temp(state, vals, args[0], nb_temps, nb_globals);
+            state[args[0]] = TCG_TEMP_CONST;
+            vals[args[0]] = args[1];
+            gen_args[0] = args[0];
+            gen_args[1] = args[1];
+            gen_args += 2;
+            args += 2;
+            break;
         case INDEX_op_call:
         case INDEX_op_jmp:
         case INDEX_op_br:
@@ -55,6 +172,7 @@ static TCGArg *tcg_constant_folding(TCGContext *s, uint16_t *tcg_opc_ptr,
 #if TCG_TARGET_REG_BITS == 64
         case INDEX_op_brcond_i64:
 #endif
+            memset(state, 0, nb_temps * sizeof(tcg_temp_state));
             i = (op == INDEX_op_call) ?
                 (args[0] >> 16) + (args[0] & 0xffff) + 3 :
                 def->nb_args;
@@ -66,6 +184,11 @@ static TCGArg *tcg_constant_folding(TCGContext *s, uint16_t *tcg_opc_ptr,
             }
             break;
         default:
+            /* Default case: we do know nothing about operation so no
+               propagation is done.  We only trash output args.  */
+            for (i = 0; i < def->nb_oargs; i++) {
+                reset_temp(state, vals, args[i], nb_temps, nb_globals);
+            }
             for (i = 0; i < def->nb_args; i++) {
                 gen_args[i] = args[i];
             }
-- 
1.7.4.1