[Qemu-devel] [PATCH 0/4] tcg: Remove unreachable code

[Qemu-devel] [PATCH 0/4] tcg: Remove unreachable code

[Richard Henderson]

I've been meaning to add a trivial cleanup pass like this for some time.

There have occasionally been instaces within front ends wherein we want
to raise an invalid operand exception (or some such) deep within a set
of subroutines.  And without a longjmp (or some such) back to the top
level of the translator loop we must return a dummy value so that we
produce valid tcg code following the exception.

While we still probably have to return a dummy value, we can clean up
the dead code that follows the exception.

In addition, when optimization is able to fold a conditional branch,
the original code sequence:

	brcond x,y,$L1
	goto_tb
	mov pc,foo
	exit_tb $1
        set_label $L1
        goto_tb 
        mov pc,bar
        exit_tb $2

The initial brcond is either folded to br, or removed as a never taken
branch, which leaves one of the two sets of goto_tb ... exit_tb unreachable.

With this we can completely remove the code for the dead branch.

While I do not expect this to have any noticable effect, this dead
code could get in the way of some other changes that I'm planning.


r~


Richard Henderson (4):
  tcg: Renumber TCG_CALL_* flags
  tcg: Add TCG_CALL_NO_RETURN
  tcg: Reference count labels
  tcg: Add reachable_code_pass

 include/exec/helper-head.h | 13 ++++++
 include/exec/helper-tcg.h  | 21 ++++++---
 tcg/tcg-op.h               |  1 +
 tcg/tcg.h                  | 11 +++--
 tcg/tcg-op.c               |  2 +
 tcg/tcg.c                  | 96 ++++++++++++++++++++++++++++++++++++++
 6 files changed, 133 insertions(+), 11 deletions(-)

-- 
2.17.2

[Qemu-devel] [PATCH 1/4] tcg: Renumber TCG_CALL_* flags

[Richard Henderson]

Previously, the low 4 bits were used for TCG_CALL_TYPE_MASK,
which was removed in 6a18ae2d2947532d5c26439548afa0481c4529f9.

Signed-off-by: Richard Henderson <richard.henderson@linaro.org>
---
 tcg/tcg.h | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

diff --git a/tcg/tcg.h b/tcg/tcg.h
index 73737dc671..e94f805370 100644
--- a/tcg/tcg.h
+++ b/tcg/tcg.h
@@ -464,11 +464,11 @@ typedef TCGv_ptr TCGv_env;
 /* call flags */
 /* Helper does not read globals (either directly or through an exception). It
    implies TCG_CALL_NO_WRITE_GLOBALS. */
-#define TCG_CALL_NO_READ_GLOBALS    0x0010
+#define TCG_CALL_NO_READ_GLOBALS    0x0001
 /* Helper does not write globals */
-#define TCG_CALL_NO_WRITE_GLOBALS   0x0020
+#define TCG_CALL_NO_WRITE_GLOBALS   0x0002
 /* Helper can be safely suppressed if the return value is not used. */
-#define TCG_CALL_NO_SIDE_EFFECTS    0x0040
+#define TCG_CALL_NO_SIDE_EFFECTS    0x0004
 
 /* convenience version of most used call flags */
 #define TCG_CALL_NO_RWG         TCG_CALL_NO_READ_GLOBALS
-- 
2.17.2

[Qemu-devel] [PATCH 2/4] tcg: Add TCG_CALL_NO_RETURN

[Richard Henderson]

Remember which helpers have been marked noreturn.

Signed-off-by: Richard Henderson <richard.henderson@linaro.org>
---
 include/exec/helper-head.h | 13 +++++++++++++
 include/exec/helper-tcg.h  | 21 ++++++++++++++-------
 tcg/tcg.h                  |  2 ++
 3 files changed, 29 insertions(+), 7 deletions(-)

diff --git a/include/exec/helper-head.h b/include/exec/helper-head.h
index 276dd5afce..ab4f8b6623 100644
--- a/include/exec/helper-head.h
+++ b/include/exec/helper-head.h
@@ -108,6 +108,19 @@
 #define dh_is_signed_env dh_is_signed_ptr
 #define dh_is_signed(t) dh_is_signed_##t
 
+#define dh_callflag_i32  0
+#define dh_callflag_s32  0
+#define dh_callflag_int  0
+#define dh_callflag_i64  0
+#define dh_callflag_s64  0
+#define dh_callflag_f16  0
+#define dh_callflag_f32  0
+#define dh_callflag_f64  0
+#define dh_callflag_ptr  0
+#define dh_callflag_void 0
+#define dh_callflag_noreturn TCG_CALL_NO_RETURN
+#define dh_callflag(t) glue(dh_callflag_, dh_alias(t))
+
 #define dh_sizemask(t, n) \
   ((dh_is_64bit(t) << (n*2)) | (dh_is_signed(t) << (n*2+1)))
 
diff --git a/include/exec/helper-tcg.h b/include/exec/helper-tcg.h
index b3bdb0c399..268e0f804b 100644
--- a/include/exec/helper-tcg.h
+++ b/include/exec/helper-tcg.h
@@ -11,36 +11,43 @@
 #define str(s) #s
 
 #define DEF_HELPER_FLAGS_0(NAME, FLAGS, ret) \
-  { .func = HELPER(NAME), .name = str(NAME), .flags = FLAGS, \
+  { .func = HELPER(NAME), .name = str(NAME), \
+    .flags = FLAGS | dh_callflag(ret), \
     .sizemask = dh_sizemask(ret, 0) },
 
 #define DEF_HELPER_FLAGS_1(NAME, FLAGS, ret, t1) \
-  { .func = HELPER(NAME), .name = str(NAME), .flags = FLAGS, \
+  { .func = HELPER(NAME), .name = str(NAME), \
+    .flags = FLAGS | dh_callflag(ret), \
     .sizemask = dh_sizemask(ret, 0) | dh_sizemask(t1, 1) },
 
 #define DEF_HELPER_FLAGS_2(NAME, FLAGS, ret, t1, t2) \
-  { .func = HELPER(NAME), .name = str(NAME), .flags = FLAGS, \
+  { .func = HELPER(NAME), .name = str(NAME), \
+    .flags = FLAGS | dh_callflag(ret), \
     .sizemask = dh_sizemask(ret, 0) | dh_sizemask(t1, 1) \
     | dh_sizemask(t2, 2) },
 
 #define DEF_HELPER_FLAGS_3(NAME, FLAGS, ret, t1, t2, t3) \
-  { .func = HELPER(NAME), .name = str(NAME), .flags = FLAGS, \
+  { .func = HELPER(NAME), .name = str(NAME), \
+    .flags = FLAGS | dh_callflag(ret), \
     .sizemask = dh_sizemask(ret, 0) | dh_sizemask(t1, 1) \
     | dh_sizemask(t2, 2) | dh_sizemask(t3, 3) },
 
 #define DEF_HELPER_FLAGS_4(NAME, FLAGS, ret, t1, t2, t3, t4) \
-  { .func = HELPER(NAME), .name = str(NAME), .flags = FLAGS, \
+  { .func = HELPER(NAME), .name = str(NAME), \
+    .flags = FLAGS | dh_callflag(ret), \
     .sizemask = dh_sizemask(ret, 0) | dh_sizemask(t1, 1) \
     | dh_sizemask(t2, 2) | dh_sizemask(t3, 3) | dh_sizemask(t4, 4) },
 
 #define DEF_HELPER_FLAGS_5(NAME, FLAGS, ret, t1, t2, t3, t4, t5) \
-  { .func = HELPER(NAME), .name = str(NAME), .flags = FLAGS, \
+  { .func = HELPER(NAME), .name = str(NAME), \
+    .flags = FLAGS | dh_callflag(ret), \
     .sizemask = dh_sizemask(ret, 0) | dh_sizemask(t1, 1) \
     | dh_sizemask(t2, 2) | dh_sizemask(t3, 3) | dh_sizemask(t4, 4) \
     | dh_sizemask(t5, 5) },
 
 #define DEF_HELPER_FLAGS_6(NAME, FLAGS, ret, t1, t2, t3, t4, t5, t6) \
-  { .func = HELPER(NAME), .name = str(NAME), .flags = FLAGS, \
+  { .func = HELPER(NAME), .name = str(NAME), \
+    .flags = FLAGS | dh_callflag(ret), \
     .sizemask = dh_sizemask(ret, 0) | dh_sizemask(t1, 1) \
     | dh_sizemask(t2, 2) | dh_sizemask(t3, 3) | dh_sizemask(t4, 4) \
     | dh_sizemask(t5, 5) | dh_sizemask(t6, 6) },
diff --git a/tcg/tcg.h b/tcg/tcg.h
index e94f805370..6b6bc75c82 100644
--- a/tcg/tcg.h
+++ b/tcg/tcg.h
@@ -469,6 +469,8 @@ typedef TCGv_ptr TCGv_env;
 #define TCG_CALL_NO_WRITE_GLOBALS   0x0002
 /* Helper can be safely suppressed if the return value is not used. */
 #define TCG_CALL_NO_SIDE_EFFECTS    0x0004
+/* Helper is QEMU_NORETURN.  */
+#define TCG_CALL_NO_RETURN          0x0008
 
 /* convenience version of most used call flags */
 #define TCG_CALL_NO_RWG         TCG_CALL_NO_READ_GLOBALS
-- 
2.17.2

[Qemu-devel] [PATCH 3/4] tcg: Reference count labels

[Richard Henderson]

Increment when adding branches, and decrement when removing them.

Signed-off-by: Richard Henderson <richard.henderson@linaro.org>
---
 tcg/tcg-op.h |  1 +
 tcg/tcg.h    |  3 ++-
 tcg/tcg-op.c |  2 ++
 tcg/tcg.c    | 20 ++++++++++++++++++++
 4 files changed, 25 insertions(+), 1 deletion(-)

diff --git a/tcg/tcg-op.h b/tcg/tcg-op.h
index db4e9188f4..7007ec0d4d 100644
--- a/tcg/tcg-op.h
+++ b/tcg/tcg-op.h
@@ -260,6 +260,7 @@ static inline void gen_set_label(TCGLabel *l)
 
 static inline void tcg_gen_br(TCGLabel *l)
 {
+    l->refs++;
     tcg_gen_op1(INDEX_op_br, label_arg(l));
 }
 
diff --git a/tcg/tcg.h b/tcg/tcg.h
index 6b6bc75c82..c6caeeb42b 100644
--- a/tcg/tcg.h
+++ b/tcg/tcg.h
@@ -246,7 +246,8 @@ typedef struct TCGRelocation {
 
 typedef struct TCGLabel {
     unsigned has_value : 1;
-    unsigned id : 31;
+    unsigned id : 15;
+    unsigned refs : 16;
     union {
         uintptr_t value;
         tcg_insn_unit *value_ptr;
diff --git a/tcg/tcg-op.c b/tcg/tcg-op.c
index 1ad095cc35..bab889662d 100644
--- a/tcg/tcg-op.c
+++ b/tcg/tcg-op.c
@@ -240,6 +240,7 @@ void tcg_gen_brcond_i32(TCGCond cond, TCGv_i32 arg1, TCGv_i32 arg2, TCGLabel *l)
     if (cond == TCG_COND_ALWAYS) {
         tcg_gen_br(l);
     } else if (cond != TCG_COND_NEVER) {
+        l->refs++;
         tcg_gen_op4ii_i32(INDEX_op_brcond_i32, arg1, arg2, cond, label_arg(l));
     }
 }
@@ -1405,6 +1406,7 @@ void tcg_gen_brcond_i64(TCGCond cond, TCGv_i64 arg1, TCGv_i64 arg2, TCGLabel *l)
     if (cond == TCG_COND_ALWAYS) {
         tcg_gen_br(l);
     } else if (cond != TCG_COND_NEVER) {
+        l->refs++;
         if (TCG_TARGET_REG_BITS == 32) {
             tcg_gen_op6ii_i32(INDEX_op_brcond2_i32, TCGV_LOW(arg1),
                               TCGV_HIGH(arg1), TCGV_LOW(arg2),
diff --git a/tcg/tcg.c b/tcg/tcg.c
index 17c193791f..31b9b58240 100644
--- a/tcg/tcg.c
+++ b/tcg/tcg.c
@@ -2191,6 +2191,26 @@ static void process_op_defs(TCGContext *s)
 
 void tcg_op_remove(TCGContext *s, TCGOp *op)
 {
+    TCGLabel *label;
+
+    switch (op->opc) {
+    case INDEX_op_br:
+        label = arg_label(op->args[0]);
+        label->refs--;
+        break;
+    case INDEX_op_brcond_i32:
+    case INDEX_op_brcond_i64:
+        label = arg_label(op->args[3]);
+        label->refs--;
+        break;
+    case INDEX_op_brcond2_i32:
+        label = arg_label(op->args[5]);
+        label->refs--;
+        break;
+    default:
+        break;
+    }
+
     QTAILQ_REMOVE(&s->ops, op, link);
     QTAILQ_INSERT_TAIL(&s->free_ops, op, link);
     s->nb_ops--;
-- 
2.17.2

[Qemu-devel] [PATCH 4/4] tcg: Add reachable_code_pass

[Richard Henderson]

Delete trivially dead code that follows unconditional branches and
noreturn helpers.  These can occur either via optimization or via
the structure of a target's translator following an exception.

Signed-off-by: Richard Henderson <richard.henderson@linaro.org>
---
 tcg/tcg.c | 76 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 76 insertions(+)

diff --git a/tcg/tcg.c b/tcg/tcg.c
index 31b9b58240..ffbf8f01ad 100644
--- a/tcg/tcg.c
+++ b/tcg/tcg.c
@@ -2301,6 +2301,81 @@ static void tcg_la_bb_end(TCGContext *s)
     }
 }
 
+/* Reachable analysis : remove unreachable code.  */
+static void reachable_code_pass(TCGContext *s)
+{
+    TCGOp *op, *op_next;
+    bool dead = false;
+
+    QTAILQ_FOREACH_SAFE(op, &s->ops, link, op_next) {
+        bool remove = dead;
+        TCGLabel *label;
+        int call_flags;
+
+        switch (op->opc) {
+        case INDEX_op_set_label:
+            label = arg_label(op->args[0]);
+            if (label->refs == 0) {
+                /*
+                 * While there is an occasional backward branch, virtually
+                 * all branches generated by the translators are forward.
+                 * Which means that generally we will have already removed
+                 * all references to the label that will be, and there is
+                 * little to be gained by iterating.
+                 */
+                remove = true;
+            } else {
+                /* Once we see a label, insns become live again.  */
+                dead = false;
+                remove = false;
+
+                /*
+                 * Optimization can fold conditional branches to unconditional.
+                 * If we find a label with one reference which is preceeded by
+                 * an unconditional branch to it, remove both.  This needed to
+                 * wait until the dead code in between them was removed.
+                 */
+                if (label->refs == 1) {
+                    TCGOp *op_prev = QTAILQ_PREV(op, TCGOpHead, link);
+                    if (op_prev->opc == INDEX_op_br &&
+                        label == arg_label(op_prev->args[0])) {
+                        tcg_op_remove(s, op_prev);
+                        remove = true;
+                    }
+                }
+            }
+            break;
+
+        case INDEX_op_br:
+        case INDEX_op_exit_tb:
+        case INDEX_op_goto_ptr:
+            /* Unconditional branches; everything following is dead.  */
+            dead = true;
+            break;
+
+        case INDEX_op_call:
+            /* Notice noreturn helper calls, raising exceptions.  */
+            call_flags = op->args[TCGOP_CALLO(op) + TCGOP_CALLI(op) + 1];
+            if (call_flags & TCG_CALL_NO_RETURN) {
+                dead = true;
+            }
+            break;
+
+        case INDEX_op_insn_start:
+            /* Never remove -- we need to keep these for unwind.  */
+            remove = false;
+            break;
+
+        default:
+            break;
+        }
+
+        if (remove) {
+            tcg_op_remove(s, op);
+        }
+    }
+}
+
 /* Liveness analysis : update the opc_arg_life array to tell if a
    given input arguments is dead. Instructions updating dead
    temporaries are removed. */
@@ -3537,6 +3612,7 @@ int tcg_gen_code(TCGContext *s, TranslationBlock *tb)
     atomic_set(&prof->la_time, prof->la_time - profile_getclock());
 #endif
 
+    reachable_code_pass(s);
     liveness_pass_1(s);
 
     if (s->nb_indirects > 0) {
-- 
2.17.2

Re: [Qemu-devel] [PATCH 0/4] tcg: Remove unreachable code

[no-reply]

Hi,

This series seems to have some coding style problems. See output below for
more information:

Message-id: 20181126230450.672-1-richard.henderson@linaro.org
Subject: [Qemu-devel] [PATCH 0/4] tcg: Remove unreachable code
Type: series

=== TEST SCRIPT BEGIN ===
#!/bin/bash

BASE=base
n=1
total=$(git log --oneline $BASE.. | wc -l)
failed=0

git config --local diff.renamelimit 0
git config --local diff.renames True
git config --local diff.algorithm histogram

commits="$(git log --format=%H --reverse $BASE..)"
for c in $commits; do
    echo "Checking PATCH $n/$total: $(git log -n 1 --format=%s $c)..."
    if ! git show $c --format=email | ./scripts/checkpatch.pl --mailback -; then
        failed=1
        echo
    fi
    n=$((n+1))
done

exit $failed
=== TEST SCRIPT END ===

Updating 3c8cf5a9c21ff8782164d1def7f44bd888713384
From https://github.com/patchew-project/qemu
 * [new tag]         patchew/20181128.181700.1038782556965887223.atsushi.nemoto@sord.co.jp -> patchew/20181128.181700.1038782556965887223.atsushi.nemoto@sord.co.jp
Switched to a new branch 'test'
f76b3bd tcg: Add reachable_code_pass
81bb184 tcg: Reference count labels
5599b43 tcg: Add TCG_CALL_NO_RETURN
d27ec83 tcg: Renumber TCG_CALL_* flags

=== OUTPUT BEGIN ===
Checking PATCH 1/4: tcg: Renumber TCG_CALL_* flags...
Checking PATCH 2/4: tcg: Add TCG_CALL_NO_RETURN...
Checking PATCH 3/4: tcg: Reference count labels...
ERROR: spaces prohibited around that ':' (ctx:WxW)
#83: FILE: tcg/tcg.h:249:
+    unsigned id : 15;
                 ^

ERROR: spaces prohibited around that ':' (ctx:WxW)
#84: FILE: tcg/tcg.h:250:
+    unsigned refs : 16;
                   ^

total: 2 errors, 0 warnings, 56 lines checked

Your patch has style problems, please review.  If any of these errors
are false positives report them to the maintainer, see
CHECKPATCH in MAINTAINERS.

Checking PATCH 4/4: tcg: Add reachable_code_pass...
=== OUTPUT END ===

Test command exited with code: 1


---
Email generated automatically by Patchew [http://patchew.org/].
Please send your feedback to patchew-devel@redhat.com

Re: [Qemu-devel] [PATCH 4/4] tcg: Add reachable_code_pass

[Emilio G. Cota]

On Mon, Nov 26, 2018 at 15:04:50 -0800, Richard Henderson wrote:
> Delete trivially dead code that follows unconditional branches and
> noreturn helpers.  These can occur either via optimization or via
> the structure of a target's translator following an exception.
> 
> Signed-off-by: Richard Henderson <richard.henderson@linaro.org>
> ---
(snip)
> +                /*
> +                 * Optimization can fold conditional branches to unconditional.
> +                 * If we find a label with one reference which is preceeded by

s/preceeded/preceded/

Reviewed-by: Emilio G. Cota <cota@braap.org>

for the series.

Thanks,

		E.