On Sun, Nov 22, 2020 at 12:13:46PM -0800, Linus Torvalds wrote:
> On Sun, Nov 22, 2020 at 11:57 AM Luc Van Oostenryck
> <luc.vanoostenryck@xxxxxxxxx> wrote:
> >
> > In the case here with your example, the if-conversion doesn't happen
> > because the phi-sources is not defined in the top block because of
> > the OR:
>
> Ahh. Yes, it's more obvious with a more realistic test-case that
> actually translates one set of bits to another set of bits (which is
> something we do in the kernel for various reasons - different bit
> "namespaces", for example user interfaces etc):
>
> #define BIT1 4
> #define BIT1x 16
>
> #define BIT2 8
> #define BIT2x 32
>
> int translate_bits(int x)
> {
> int y = 0;
> if (x & BIT1)
> y |= BIT1x;
> if (x & BIT2)
> y |= BIT2x;
> return y;
> }
>
> and the first one gets nicely translated as
>
> and.32 %r2 <- %arg1, $4
> select.32 %r14(y) <- %r2, $16, $0
>
> but then the second one doesn't for the reason you mention.
One thing that can be done (but probably excessive) is something
like the patch below: each time a phi-source is 'blocked' by
it's defining instruction, try to move this instruction up.
With this, we get the expected result for your patch:
translate_bits:
and.32 %r2 <- %arg1, $4
select.32 %r14(y) <- %r2, $16, $0
and.32 %r7 <- %arg1, $8
or.32 %r10 <- %r14(y), $32
select.32 %r13(y) <- %r7, %r10, %r14(y)
ret.32 %r13(y)
It gives very good result in all sort of code but sadly it
doesn't improve the context imbalance warnings, it even
make them (very) slightly worse.
>From be38aca2a4ca3fc0911da9187e2ea58a379824cc Mon Sep 17 00:00:00 2001
From: Luc Van Oostenryck <luc.vanoostenryck@xxxxxxxxx>
Date: Sun, 22 Nov 2020 22:49:13 +0100
Subject: [PATCH] move up instructions blocking if-conversion
---
linearize.h | 6 +++++
simplify.c | 65 +++++++++++++++++++++++++++++++++++++++++++++++++++--
2 files changed, 69 insertions(+), 2 deletions(-)
diff --git a/linearize.h b/linearize.h
index 31c754e200c2..dcd4359eb2a6 100644
--- a/linearize.h
+++ b/linearize.h
@@ -300,6 +300,12 @@ static inline void replace_bb_in_list(struct basic_block_list **list,
replace_ptr_list_entry((struct ptr_list **)list, old, new, count);
}
+static inline void replace_insn(struct instruction *old, struct instruction *new)
+{
+ replace_ptr_list_entry((struct ptr_list **)&old->bb->insns, old, new, 1);
+}
+
+
struct entrypoint {
struct symbol *name;
struct symbol_list *syms;
diff --git a/simplify.c b/simplify.c
index a0e23d6de01f..7d5e0d9bcb3a 100644
--- a/simplify.c
+++ b/simplify.c
@@ -46,11 +46,69 @@
#include "linearize.h"
#include "flow.h"
#include "symbol.h"
+#include "flowgraph.h"
///
// Utilities
// ^^^^^^^^^
+///
+// check if a pseudo is defined in a BB
+//
+// :note: this could also use the liveness information if available.
+//
+static inline bool is_defined_at(pseudo_t src, struct basic_block *bb)
+{
+ if (src->type != PSEUDO_REG)
+ return true;
+ return domtree_dominates(src->def->bb, bb);
+}
+
+///
+// move an instruction at the end of the given BB
+static void move_insn(struct instruction *insn, struct basic_block *bb)
+{
+ struct instruction *last = delete_last_instruction(&bb->insns);
+ insn->bb = bb;
+ add_instruction(&bb->insns, insn);
+ add_instruction(&bb->insns, last);
+}
+
+///
+// move an instruction into a BB if all its arguments are defined there
+static bool try_to_move_insn(struct instruction *insn, struct basic_block *bb)
+{
+ static struct instruction NOP; // will later be ignore because !ep
+
+ if (!bb || bb == insn->bb)
+ return 0;
+
+ switch (insn->opcode) {
+ case OP_SEL:
+ if (!is_defined_at(insn->src3, bb))
+ return 0;
+ case OP_ADD: case OP_SUB:
+ case OP_ASR: case OP_LSR: case OP_SHL:
+ case OP_AND: case OP_XOR: case OP_OR:
+ case OP_BINCMP ... OP_BINCMP_END:
+ case OP_FPCMP ... OP_FPCMP_END:
+ case OP_FADD: case OP_FSUB:
+ // basically, all the binops but multiply and divide, just because
+ if (!is_defined_at(insn->src2, bb))
+ return 0;
+ case OP_UNOP ... OP_UNOP_END:
+ if (!is_defined_at(insn->src1, bb))
+ return 0;
+ break;
+ default:
+ return 0;
+ }
+ replace_insn(insn, &NOP);
+ move_insn(insn, bb);
+ repeat_phase |= REPEAT_CSE;
+ return 1;
+}
+
///
// find the trivial parent for a phi-source
static struct basic_block *phi_parent(struct basic_block *source, pseudo_t pseudo)
@@ -58,8 +116,11 @@ static struct basic_block *phi_parent(struct basic_block *source, pseudo_t pseud
/* Can't go upwards if the pseudo is defined in the bb it came from.. */
if (pseudo->type == PSEUDO_REG) {
struct instruction *def = pseudo->def;
- if (def->bb == source)
- return source;
+ if (def->bb == source) {
+ // unless we can move the defining instruction up
+ if (!try_to_move_insn(def, source->idom))
+ return source;
+ }
}
if (bb_list_size(source->children) != 1 || bb_list_size(source->parents) != 1)
return source;
--
2.29.2
