aboutsummaryrefslogtreecommitdiffstatshomepage
diff options
authorLuc Van Oostenryck <luc.vanoostenryck@gmail.com>2017-04-29 01:48:15 +0200
committerLuc Van Oostenryck <luc.vanoostenryck@gmail.com>2018-09-01 21:42:45 +0200
commita8a310fa690e5d5caea4be27397554eba1155505 (patch)
treea3309ae213000b770f80bc0a88afe8552106dd52
parent9bcea8b22d8a40523ecac8786e3b651e351f2663 (diff)
downloadsparse-dev-a8a310fa690e5d5caea4be27397554eba1155505.tar.gz
trivial-phi: remove more complex trivial phi-nodes
In a set of related phi-nodes and phi-sources if all phi-sources but one correspond to the target of one of the phi-sources, then no phi-nodes is needed and all %phis can be replaced by the unique source. For example, code like: int test(void); int foo(int a) { while (test()) a ^= 0; return a; } used to produce an IR with a phi-node for 'a', like: foo: phisrc.32 %phi2(a) <- %arg1 br .L4 .L4: phi.32 %r7(a) <- %phi2(a), %phi3(a) call.32 %r1 <- test cbr %r1, .L2, .L5 .L2: phisrc.32 %phi3(a) <- %r7(a) br .L4 .L5: ret.32 %r7(a) but since 'a ^= 0' is a no-op, the value of 'a' is in fact never mofified. This can be seen in the phi-node where its second operand (%phi3) is the same as its target (%r7). So the only possible value for 'a' is the one from the first operand, its initial value (%arg1). Once this trivial phi-nodes is removed, the IR is the expected: foo: br .L4 .L4: call.32 %r1 <- test cbr %r1, .L4, .L5 .L5: ret.32 %arg1 Removing these trivial phi-nodes will usually trigger other simplifications, especially those concerning the CFG. Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
-rw-r--r--simplify.c19
-rw-r--r--validation/optim/trivial-phis.c1
2 files changed, 17 insertions, 3 deletions
diff --git a/simplify.c b/simplify.c
index 1fa46548..696d9d58 100644
--- a/simplify.c
+++ b/simplify.c
@@ -180,11 +180,17 @@ static int if_convert_phi(struct instruction *insn)
//
// A phi-node is trivial if it has a single possible result:
// # all operands are the same
+// # the operands are themselves defined by a chain or cycle of phi-nodes
+// and the set of all operands involved contains a single value
+// not defined by these phi-nodes
// Since the result is unique, these phi-nodes can be removed.
-static pseudo_t trivial_phi(pseudo_t pseudo, struct instruction *insn)
+static pseudo_t trivial_phi(pseudo_t pseudo, struct instruction *insn, struct pseudo_list **list)
{
+ pseudo_t target = insn->target;
pseudo_t phi;
+ add_pseudo(list, target);
+
FOR_EACH_PTR(insn->phi_list, phi) {
struct instruction *def;
pseudo_t src;
@@ -203,6 +209,14 @@ static pseudo_t trivial_phi(pseudo_t pseudo, struct instruction *insn)
}
if (src == pseudo)
continue;
+ if (src == target)
+ continue;
+ if (DEF_OPCODE(def, src) == OP_PHI) {
+ if (pseudo_in_list(*list, src))
+ continue;
+ if ((pseudo = trivial_phi(pseudo, def, list)))
+ continue;
+ }
return NULL;
} END_FOR_EACH_PTR(phi);
@@ -211,9 +225,10 @@ static pseudo_t trivial_phi(pseudo_t pseudo, struct instruction *insn)
static int clean_up_phi(struct instruction *insn)
{
+ struct pseudo_list *list = NULL;
pseudo_t pseudo;
- if ((pseudo = trivial_phi(NULL, insn))) {
+ if ((pseudo = trivial_phi(NULL, insn, &list))) {
convert_instruction_target(insn, pseudo);
kill_instruction(insn);
return REPEAT_CSE;
diff --git a/validation/optim/trivial-phis.c b/validation/optim/trivial-phis.c
index 754affb7..8af093c1 100644
--- a/validation/optim/trivial-phis.c
+++ b/validation/optim/trivial-phis.c
@@ -7,7 +7,6 @@ void foo(int a)
/*
* check-name: trivial phis
* check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
*
* check-output-ignore
* check-output-excludes: phi\\.