* [PATCH 1/8] extract add_dominator() from find_dominating_parents()
2017-04-13 16:55 [PATCH 0/8] avoid creating orphaned OP_PHISRCs Luc Van Oostenryck
@ 2017-04-13 16:55 ` Luc Van Oostenryck
2017-04-13 16:55 ` [PATCH 2/8] add helper add_load_dominators() Luc Van Oostenryck
` (7 subsequent siblings)
8 siblings, 0 replies; 10+ messages in thread
From: Luc Van Oostenryck @ 2017-04-13 16:55 UTC (permalink / raw)
To: linux-sparse; +Cc: Christopher Li, Luc Van Oostenryck
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
flow.c | 19 ++++++++++++-------
flow.h | 1 +
memops.c | 8 +-------
3 files changed, 14 insertions(+), 14 deletions(-)
diff --git a/flow.c b/flow.c
index 45bae773e..50507a5e7 100644
--- a/flow.c
+++ b/flow.c
@@ -374,8 +374,6 @@ static int find_dominating_parents(pseudo_t pseudo, struct instruction *insn,
FOR_EACH_PTR(bb->parents, parent) {
struct instruction *one;
- struct instruction *br;
- pseudo_t phi;
FOR_EACH_PTR_REVERSE(parent->insns, one) {
int dominance;
@@ -403,15 +401,22 @@ no_dominance:
found_dominator:
if (dominators && phisrc_in_bb(*dominators, parent))
continue;
- br = delete_last_instruction(&parent->insns);
- phi = alloc_phi(parent, one->target, one->type);
- phi->ident = phi->ident ? : pseudo->ident;
- add_instruction(&parent->insns, br);
- use_pseudo(insn, phi, add_pseudo(dominators, phi));
+ add_dominator(dominators, insn, one, pseudo->ident);
} END_FOR_EACH_PTR(parent);
return 1;
}
+void add_dominator(struct pseudo_list **phi_list, struct instruction *insn,
+ struct instruction *dom, struct ident *ident)
+{
+ struct basic_block *bb = dom->bb;
+ struct instruction *br = delete_last_instruction(&bb->insns);
+ pseudo_t phi = alloc_phi(bb, dom->target, dom->type);
+ phi->ident = phi->ident ? : ident ? : dom->target->ident;
+ add_instruction(&bb->insns, br);
+ use_pseudo(insn, phi, add_pseudo(phi_list, phi));
+}
+
/*
* We should probably sort the phi list just to make it easier to compare
* later for equality.
diff --git a/flow.h b/flow.h
index 31ed80d40..800585547 100644
--- a/flow.h
+++ b/flow.h
@@ -38,6 +38,7 @@ static inline void kill_instruction_force(struct instruction *insn)
void check_access(struct instruction *insn);
void convert_load_instruction(struct instruction *, pseudo_t);
void rewrite_load_instruction(struct instruction *, struct pseudo_list *);
+void add_dominator(struct pseudo_list **, struct instruction *, struct instruction *, struct ident*);
int dominates(pseudo_t pseudo, struct instruction *insn, struct instruction *dom, int local);
extern void clear_liveness(struct entrypoint *ep);
diff --git a/memops.c b/memops.c
index 187a63284..ac43b6a0a 100644
--- a/memops.c
+++ b/memops.c
@@ -24,8 +24,6 @@ static int find_dominating_parents(pseudo_t pseudo, struct instruction *insn,
FOR_EACH_PTR(bb->parents, parent) {
struct instruction *one;
- struct instruction *br;
- pseudo_t phi;
FOR_EACH_PTR_REVERSE(parent->insns, one) {
int dominance;
@@ -51,11 +49,7 @@ no_dominance:
continue;
found_dominator:
- br = delete_last_instruction(&parent->insns);
- phi = alloc_phi(parent, one->target, one->type);
- phi->ident = phi->ident ? : one->target->ident;
- add_instruction(&parent->insns, br);
- use_pseudo(insn, phi, add_pseudo(dominators, phi));
+ add_dominator(dominators, insn, one, NULL);
} END_FOR_EACH_PTR(parent);
return 1;
}
--
2.12.0
^ permalink raw reply related [flat|nested] 10+ messages in thread* [PATCH 2/8] add helper add_load_dominators()
2017-04-13 16:55 [PATCH 0/8] avoid creating orphaned OP_PHISRCs Luc Van Oostenryck
2017-04-13 16:55 ` [PATCH 1/8] extract add_dominator() from find_dominating_parents() Luc Van Oostenryck
@ 2017-04-13 16:55 ` Luc Van Oostenryck
2017-04-13 16:55 ` [PATCH 3/8] remove test on initial phi->ident Luc Van Oostenryck
` (6 subsequent siblings)
8 siblings, 0 replies; 10+ messages in thread
From: Luc Van Oostenryck @ 2017-04-13 16:55 UTC (permalink / raw)
To: linux-sparse; +Cc: Christopher Li, Luc Van Oostenryck
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
flow.c | 12 ++++++++++++
flow.h | 1 +
2 files changed, 13 insertions(+)
diff --git a/flow.c b/flow.c
index 50507a5e7..25a5bffbe 100644
--- a/flow.c
+++ b/flow.c
@@ -417,6 +417,18 @@ void add_dominator(struct pseudo_list **phi_list, struct instruction *insn,
use_pseudo(insn, phi, add_pseudo(phi_list, phi));
}
+struct pseudo_list *add_load_dominators(struct instruction *insn, struct instruction_list *doms,
+ struct ident *ident)
+{
+ struct pseudo_list *phi_list = NULL;
+ struct instruction *dom;
+
+ FOR_EACH_PTR(doms, dom) {
+ add_dominator(&phi_list, insn, dom, ident);
+ } END_FOR_EACH_PTR(dom);
+ return phi_list;
+}
+
/*
* We should probably sort the phi list just to make it easier to compare
* later for equality.
diff --git a/flow.h b/flow.h
index 800585547..a6d0881c2 100644
--- a/flow.h
+++ b/flow.h
@@ -39,6 +39,7 @@ void check_access(struct instruction *insn);
void convert_load_instruction(struct instruction *, pseudo_t);
void rewrite_load_instruction(struct instruction *, struct pseudo_list *);
void add_dominator(struct pseudo_list **, struct instruction *, struct instruction *, struct ident*);
+struct pseudo_list *add_load_dominators(struct instruction *, struct instruction_list *, struct ident*);
int dominates(pseudo_t pseudo, struct instruction *insn, struct instruction *dom, int local);
extern void clear_liveness(struct entrypoint *ep);
--
2.12.0
^ permalink raw reply related [flat|nested] 10+ messages in thread* [PATCH 3/8] remove test on initial phi->ident
2017-04-13 16:55 [PATCH 0/8] avoid creating orphaned OP_PHISRCs Luc Van Oostenryck
2017-04-13 16:55 ` [PATCH 1/8] extract add_dominator() from find_dominating_parents() Luc Van Oostenryck
2017-04-13 16:55 ` [PATCH 2/8] add helper add_load_dominators() Luc Van Oostenryck
@ 2017-04-13 16:55 ` Luc Van Oostenryck
2017-04-13 16:55 ` [PATCH 4/8] avoid phisrc orphaned by simplify_loads() Luc Van Oostenryck
` (5 subsequent siblings)
8 siblings, 0 replies; 10+ messages in thread
From: Luc Van Oostenryck @ 2017-04-13 16:55 UTC (permalink / raw)
To: linux-sparse; +Cc: Christopher Li, Luc Van Oostenryck
The code used to be like:
pseudo_t phi = alloc_phi(...);
phi->ident = phi->ident ? : ...
but this new allocated phi can never have an identifier.
Change this by removing the test and directly assigning the
other part of the conditional.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
flow.c | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/flow.c b/flow.c
index 25a5bffbe..aa7a6586f 100644
--- a/flow.c
+++ b/flow.c
@@ -412,7 +412,7 @@ void add_dominator(struct pseudo_list **phi_list, struct instruction *insn,
struct basic_block *bb = dom->bb;
struct instruction *br = delete_last_instruction(&bb->insns);
pseudo_t phi = alloc_phi(bb, dom->target, dom->type);
- phi->ident = phi->ident ? : ident ? : dom->target->ident;
+ phi->ident = ident ? : dom->target->ident;
add_instruction(&bb->insns, br);
use_pseudo(insn, phi, add_pseudo(phi_list, phi));
}
--
2.12.0
^ permalink raw reply related [flat|nested] 10+ messages in thread* [PATCH 4/8] avoid phisrc orphaned by simplify_loads()
2017-04-13 16:55 [PATCH 0/8] avoid creating orphaned OP_PHISRCs Luc Van Oostenryck
` (2 preceding siblings ...)
2017-04-13 16:55 ` [PATCH 3/8] remove test on initial phi->ident Luc Van Oostenryck
@ 2017-04-13 16:55 ` Luc Van Oostenryck
2017-04-13 16:55 ` [PATCH 5/8] avoid phisrc orphaned by find_dominating_stores() Luc Van Oostenryck
` (4 subsequent siblings)
8 siblings, 0 replies; 10+ messages in thread
From: Luc Van Oostenryck @ 2017-04-13 16:55 UTC (permalink / raw)
To: linux-sparse; +Cc: Christopher Li, Luc Van Oostenryck
simplify_loads() calls find_dominating_parents() which can
add an OP_PHISRC in each BB it visits and the corresponding
%phi are collected in a list.
Then, depending on find_dominating_parents()'s returned
value, either an OP_PHI is created with this list as phi_list,
or no such OP_PHI is created and the phi_list is discarded.
In the later case, the added OP_PHISRCs are of no use but are
left there nevertheless.
These orphaned OP_PHISRCs can only bring confusion later.
It seems also (but I can't strictly confirm this) that this can
sometimes happen at each CSE-simplification cycle, creating one
more such OP_PHISRC at each cycle, into each concerned BB.
Not good.
Change this by not creating these OP_PHISRC but instead just
collecting their source pseudo. And then only created them
together with the corresponding OP_PHI, or simply discarding
the list, depending on the returned value.
The situation can clearly be seen with the following code:
struct s { void *x, *z; };
extern void use(struct s *);
void *foo(struct s *s)
{
if (s->x == s->z)
use(s);
return s->x;
}
which was linearized as:
foo:
load.64 %r2 <- 0[%arg1]
load.64 %r4 <- 8[%arg1]
seteq.32 %r5 <- %r4, %r2
-> phisrc.64 %phi2 <- %r2
-> phisrc.64 %phi3 <- %r2
cbr %r5, .L1, .L2
.L1:
push.64 %arg1
call use
br .L2
.L2:
load.64 %r8 <- 0[%arg1]
ret.64 %r8
and is now simply linearized as:
foo:
load.64 %r2 <- 0[%arg1]
load.64 %r4 <- 8[%arg1]
seteq.32 %r5 <- %r4, %r2
cbr %r5, .L1, .L2
.L1:
push.64 %arg1
call use
br .L2
.L2:
load.64 %r8 <- 0[%arg1]
ret.64 %r8
Note: this situation seems to have existed since a long time
but have been made worse by the patch:
(5636cd5cb "missing load simplification")
Fixes: 5636cd5cbf816f30ee57d580ec4debd8e0bd7581
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
memops.c | 10 ++++++----
validation/linear/phisrc-orphan-ld.c | 22 ++++++++++++++++++++++
2 files changed, 28 insertions(+), 4 deletions(-)
create mode 100644 validation/linear/phisrc-orphan-ld.c
diff --git a/memops.c b/memops.c
index ac43b6a0a..39469e260 100644
--- a/memops.c
+++ b/memops.c
@@ -17,7 +17,7 @@
#include "flow.h"
static int find_dominating_parents(pseudo_t pseudo, struct instruction *insn,
- struct basic_block *bb, unsigned long generation, struct pseudo_list **dominators,
+ struct basic_block *bb, unsigned long generation, struct instruction_list **dominators,
int local)
{
struct basic_block *parent;
@@ -49,7 +49,7 @@ no_dominance:
continue;
found_dominator:
- add_dominator(dominators, insn, one, NULL);
+ add_instruction(dominators, one);
} END_FOR_EACH_PTR(parent);
return 1;
}
@@ -83,7 +83,7 @@ static void simplify_loads(struct basic_block *bb)
struct instruction *dom;
pseudo_t pseudo = insn->src;
int local = local_pseudo(pseudo);
- struct pseudo_list *dominators;
+ struct instruction_list *dominators;
unsigned long generation;
/* Check for illegal offsets.. */
@@ -115,6 +115,7 @@ static void simplify_loads(struct basic_block *bb)
bb->generation = generation;
dominators = NULL;
if (find_dominating_parents(pseudo, insn, bb, generation, &dominators, local)) {
+ struct pseudo_list *phi_list;
/* This happens with initial assignments to structures etc.. */
if (!dominators) {
if (local) {
@@ -123,7 +124,8 @@ static void simplify_loads(struct basic_block *bb)
}
goto next_load;
}
- rewrite_load_instruction(insn, dominators);
+ phi_list = add_load_dominators(insn, dominators, NULL);
+ rewrite_load_instruction(insn, phi_list);
}
}
next_load:
diff --git a/validation/linear/phisrc-orphan-ld.c b/validation/linear/phisrc-orphan-ld.c
new file mode 100644
index 000000000..a10aedba6
--- /dev/null
+++ b/validation/linear/phisrc-orphan-ld.c
@@ -0,0 +1,22 @@
+struct s {
+ void *x;
+ void *z;
+};
+
+extern void use(struct s *);
+
+void *foo(struct s *s)
+{
+ if (s->x == s->z)
+ use(s);
+
+ return s->x;
+}
+
+/*
+ * check-name: phisrc orphaned (loads)
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-ignore
+ * check-output-excludes: phisrc
+ */
--
2.12.0
^ permalink raw reply related [flat|nested] 10+ messages in thread* [PATCH 5/8] avoid phisrc orphaned by find_dominating_stores()
2017-04-13 16:55 [PATCH 0/8] avoid creating orphaned OP_PHISRCs Luc Van Oostenryck
` (3 preceding siblings ...)
2017-04-13 16:55 ` [PATCH 4/8] avoid phisrc orphaned by simplify_loads() Luc Van Oostenryck
@ 2017-04-13 16:55 ` Luc Van Oostenryck
2017-04-13 16:55 ` [PATCH 6/8] integrate add_load_dominators() into rewrite_load_instruction() Luc Van Oostenryck
` (3 subsequent siblings)
8 siblings, 0 replies; 10+ messages in thread
From: Luc Van Oostenryck @ 2017-04-13 16:55 UTC (permalink / raw)
To: linux-sparse; +Cc: Christopher Li, Luc Van Oostenryck
Note: this is the dual of the preceding patch, only for stores
instead of loads.
find_dominating_stores() call find_dominating_parents() which can
add an OP_PHISRC in each BB it visits and the corresponding
%phi are collected in a list. Then, depending on the returned
value, an OP_PHI is created with this list as phi_list.
However, it could that because of the returned value, no such
OP_PHI is created and thus the newly created OP_PHISRC stay
there but are of no use.
It seems also (but I can't strictly confirm this) that this can
sometimes happen at each CSE-simplification cycle, creating one
more such OP_PHISRC at each cycle, into each concerned BB.
Not good.
Change this by not creating these OP_PHISRC but instead just
collecting their source pseudo. And then only created them
together with the corresponding OP_PHI, or simply discarding
the list, depending on the returned value.
The situation can clearly be seen with the following code:
extern void abort(void);
extern int bar;
int foo(void)
{
if (bar)
abort();
return bar;
}
which was linearized as:
foo:
load.32 %r1 <- 0[bar]
> phisrc.32 %phi2(bar) <- %r1
cbr %r1, .L1, .L2
.L1:
call abort
br .L2
.L2:
load.32 %r2 <- 0[bar]
ret.32 %r2
and is now linearized as:
foo:
load.32 %r1 <- 0[bar]
cbr %r1, .L1, .L2
.L1:
call abort
br .L2
.L2:
load.32 %r2 <- 0[bar]
ret.32 %r2
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
flow.c | 20 +++++++++++---------
validation/linear/phisrc-orphan-st.c | 17 +++++++++++++++++
2 files changed, 28 insertions(+), 9 deletions(-)
create mode 100644 validation/linear/phisrc-orphan-st.c
diff --git a/flow.c b/flow.c
index aa7a6586f..678f9ba86 100644
--- a/flow.c
+++ b/flow.c
@@ -352,19 +352,19 @@ int dominates(pseudo_t pseudo, struct instruction *insn, struct instruction *dom
return 1;
}
-static int phisrc_in_bb(struct pseudo_list *list, struct basic_block *bb)
+static int phisrc_in_bb(struct instruction_list *list, struct basic_block *bb)
{
- pseudo_t p;
- FOR_EACH_PTR(list, p) {
- if (p->def->bb == bb)
+ struct instruction *def;
+ FOR_EACH_PTR(list, def) {
+ if (def->bb == bb)
return 1;
- } END_FOR_EACH_PTR(p);
+ } END_FOR_EACH_PTR(def);
return 0;
}
static int find_dominating_parents(pseudo_t pseudo, struct instruction *insn,
- struct basic_block *bb, unsigned long generation, struct pseudo_list **dominators,
+ struct basic_block *bb, unsigned long generation, struct instruction_list **dominators,
int local)
{
struct basic_block *parent;
@@ -401,7 +401,7 @@ no_dominance:
found_dominator:
if (dominators && phisrc_in_bb(*dominators, parent))
continue;
- add_dominator(dominators, insn, one, pseudo->ident);
+ add_instruction(dominators, one);
} END_FOR_EACH_PTR(parent);
return 1;
}
@@ -472,7 +472,8 @@ static int find_dominating_stores(pseudo_t pseudo, struct instruction *insn,
{
struct basic_block *bb = insn->bb;
struct instruction *one, *dom = NULL;
- struct pseudo_list *dominators;
+ struct instruction_list *dominators;
+ struct pseudo_list *phi_list;
int partial;
/* Unreachable load? Undo it */
@@ -534,7 +535,8 @@ found:
* have to turn the load into a phi-node of the
* dominators.
*/
- rewrite_load_instruction(insn, dominators);
+ phi_list = add_load_dominators(insn, dominators, pseudo->ident);
+ rewrite_load_instruction(insn, phi_list);
return 1;
}
diff --git a/validation/linear/phisrc-orphan-st.c b/validation/linear/phisrc-orphan-st.c
new file mode 100644
index 000000000..e5b3a3a46
--- /dev/null
+++ b/validation/linear/phisrc-orphan-st.c
@@ -0,0 +1,17 @@
+extern void abort(void);
+extern int bar;
+
+int foo(void)
+{
+ if (bar)
+ abort();
+ return bar;
+}
+
+/*
+ * check-name: phisrc orphaned (stores)
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-ignore
+ * check-output-excludes: phisrc
+ */
--
2.12.0
^ permalink raw reply related [flat|nested] 10+ messages in thread* [PATCH 6/8] integrate add_load_dominators() into rewrite_load_instruction()
2017-04-13 16:55 [PATCH 0/8] avoid creating orphaned OP_PHISRCs Luc Van Oostenryck
` (4 preceding siblings ...)
2017-04-13 16:55 ` [PATCH 5/8] avoid phisrc orphaned by find_dominating_stores() Luc Van Oostenryck
@ 2017-04-13 16:55 ` Luc Van Oostenryck
2017-04-13 16:55 ` [PATCH 7/8] check duplicated phi-nodes directly on dominators Luc Van Oostenryck
` (2 subsequent siblings)
8 siblings, 0 replies; 10+ messages in thread
From: Luc Van Oostenryck @ 2017-04-13 16:55 UTC (permalink / raw)
To: linux-sparse; +Cc: Christopher Li, Luc Van Oostenryck
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
flow.c | 12 ++++++++----
flow.h | 4 +---
memops.c | 4 +---
3 files changed, 10 insertions(+), 10 deletions(-)
diff --git a/flow.c b/flow.c
index 678f9ba86..b64a3f74a 100644
--- a/flow.c
+++ b/flow.c
@@ -406,6 +406,7 @@ found_dominator:
return 1;
}
+static
void add_dominator(struct pseudo_list **phi_list, struct instruction *insn,
struct instruction *dom, struct ident *ident)
{
@@ -417,6 +418,7 @@ void add_dominator(struct pseudo_list **phi_list, struct instruction *insn,
use_pseudo(insn, phi, add_pseudo(phi_list, phi));
}
+static
struct pseudo_list *add_load_dominators(struct instruction *insn, struct instruction_list *doms,
struct ident *ident)
{
@@ -433,10 +435,14 @@ struct pseudo_list *add_load_dominators(struct instruction *insn, struct instruc
* We should probably sort the phi list just to make it easier to compare
* later for equality.
*/
-void rewrite_load_instruction(struct instruction *insn, struct pseudo_list *dominators)
+void rewrite_load_instruction(struct instruction *insn, struct instruction_list *doms,
+ struct ident *ident)
{
+ struct pseudo_list *dominators;
pseudo_t new, phi;
+ dominators = add_load_dominators(insn, doms, ident);
+
/*
* Check for somewhat common case of duplicate
* phi nodes.
@@ -473,7 +479,6 @@ static int find_dominating_stores(pseudo_t pseudo, struct instruction *insn,
struct basic_block *bb = insn->bb;
struct instruction *one, *dom = NULL;
struct instruction_list *dominators;
- struct pseudo_list *phi_list;
int partial;
/* Unreachable load? Undo it */
@@ -535,8 +540,7 @@ found:
* have to turn the load into a phi-node of the
* dominators.
*/
- phi_list = add_load_dominators(insn, dominators, pseudo->ident);
- rewrite_load_instruction(insn, phi_list);
+ rewrite_load_instruction(insn, dominators, pseudo->ident);
return 1;
}
diff --git a/flow.h b/flow.h
index a6d0881c2..99bfcc879 100644
--- a/flow.h
+++ b/flow.h
@@ -37,9 +37,7 @@ static inline void kill_instruction_force(struct instruction *insn)
void check_access(struct instruction *insn);
void convert_load_instruction(struct instruction *, pseudo_t);
-void rewrite_load_instruction(struct instruction *, struct pseudo_list *);
-void add_dominator(struct pseudo_list **, struct instruction *, struct instruction *, struct ident*);
-struct pseudo_list *add_load_dominators(struct instruction *, struct instruction_list *, struct ident*);
+void rewrite_load_instruction(struct instruction *, struct instruction_list *, struct ident*);
int dominates(pseudo_t pseudo, struct instruction *insn, struct instruction *dom, int local);
extern void clear_liveness(struct entrypoint *ep);
diff --git a/memops.c b/memops.c
index 39469e260..bbb1831af 100644
--- a/memops.c
+++ b/memops.c
@@ -115,7 +115,6 @@ static void simplify_loads(struct basic_block *bb)
bb->generation = generation;
dominators = NULL;
if (find_dominating_parents(pseudo, insn, bb, generation, &dominators, local)) {
- struct pseudo_list *phi_list;
/* This happens with initial assignments to structures etc.. */
if (!dominators) {
if (local) {
@@ -124,8 +123,7 @@ static void simplify_loads(struct basic_block *bb)
}
goto next_load;
}
- phi_list = add_load_dominators(insn, dominators, NULL);
- rewrite_load_instruction(insn, phi_list);
+ rewrite_load_instruction(insn, dominators, NULL);
}
}
next_load:
--
2.12.0
^ permalink raw reply related [flat|nested] 10+ messages in thread* [PATCH 7/8] check duplicated phi-nodes directly on dominators
2017-04-13 16:55 [PATCH 0/8] avoid creating orphaned OP_PHISRCs Luc Van Oostenryck
` (5 preceding siblings ...)
2017-04-13 16:55 ` [PATCH 6/8] integrate add_load_dominators() into rewrite_load_instruction() Luc Van Oostenryck
@ 2017-04-13 16:55 ` Luc Van Oostenryck
2017-04-13 16:55 ` [PATCH 8/8] avoid creating unneeded phi-sources Luc Van Oostenryck
2017-05-18 17:04 ` [PATCH 0/8] avoid creating orphaned OP_PHISRCs Luc Van Oostenryck
8 siblings, 0 replies; 10+ messages in thread
From: Luc Van Oostenryck @ 2017-04-13 16:55 UTC (permalink / raw)
To: linux-sparse; +Cc: Christopher Li, Luc Van Oostenryck
Now that add_load_dominators() is integrated into
rewrite_load_instruction() we can check for duplicated
phi sources directly in the dominators list instead
to have to check the corresponding phi sources.
This is a preparatory step for the next patch where
unneeded phi sources are not created anymore.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
flow.c | 11 ++++++-----
1 file changed, 6 insertions(+), 5 deletions(-)
diff --git a/flow.c b/flow.c
index b64a3f74a..d705abe2e 100644
--- a/flow.c
+++ b/flow.c
@@ -439,6 +439,7 @@ void rewrite_load_instruction(struct instruction *insn, struct instruction_list
struct ident *ident)
{
struct pseudo_list *dominators;
+ struct instruction *dom;
pseudo_t new, phi;
dominators = add_load_dominators(insn, doms, ident);
@@ -447,12 +448,12 @@ void rewrite_load_instruction(struct instruction *insn, struct instruction_list
* Check for somewhat common case of duplicate
* phi nodes.
*/
- new = first_pseudo(dominators)->def->src1;
- FOR_EACH_PTR(dominators, phi) {
- if (new != phi->def->src1)
+ new = first_instruction(doms)->target;
+ FOR_EACH_PTR(doms, dom) {
+ if (new != dom->target)
goto complex_phi;
- new->ident = new->ident ? : phi->ident;
- } END_FOR_EACH_PTR(phi);
+ new->ident = new->ident ? : ident ? : dom->target->ident;
+ } END_FOR_EACH_PTR(dom);
/*
* All the same pseudo - mark the phi-nodes unused
--
2.12.0
^ permalink raw reply related [flat|nested] 10+ messages in thread* [PATCH 8/8] avoid creating unneeded phi-sources
2017-04-13 16:55 [PATCH 0/8] avoid creating orphaned OP_PHISRCs Luc Van Oostenryck
` (6 preceding siblings ...)
2017-04-13 16:55 ` [PATCH 7/8] check duplicated phi-nodes directly on dominators Luc Van Oostenryck
@ 2017-04-13 16:55 ` Luc Van Oostenryck
2017-05-18 17:04 ` [PATCH 0/8] avoid creating orphaned OP_PHISRCs Luc Van Oostenryck
8 siblings, 0 replies; 10+ messages in thread
From: Luc Van Oostenryck @ 2017-04-13 16:55 UTC (permalink / raw)
To: linux-sparse; +Cc: Christopher Li, Luc Van Oostenryck
In rewrite_load_instruction(), it's tested if the dominators
are in fact all the same and if they are, as there is then no
need for a phi-node, the newly created OP_PHISRCs are killed
and the unique dominator is used in place of the phi-node.
But in this case, it's a waste to have created the OP_PHISRCs
as they are destroyed just after being created.
Fix this by basically switching the order 'creating phi sources'
and 'checking for uniqueness'. If the dominators are found to be
all the same then use this unique dominator as the loaded value
and no OP_PHISRC need to be created.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
flow.c | 17 ++++++++---------
validation/loop-linearization.c | 30 +++++++++++++++---------------
2 files changed, 23 insertions(+), 24 deletions(-)
diff --git a/flow.c b/flow.c
index d705abe2e..317074545 100644
--- a/flow.c
+++ b/flow.c
@@ -440,9 +440,7 @@ void rewrite_load_instruction(struct instruction *insn, struct instruction_list
{
struct pseudo_list *dominators;
struct instruction *dom;
- pseudo_t new, phi;
-
- dominators = add_load_dominators(insn, doms, ident);
+ pseudo_t new;
/*
* Check for somewhat common case of duplicate
@@ -456,17 +454,18 @@ void rewrite_load_instruction(struct instruction *insn, struct instruction_list
} END_FOR_EACH_PTR(dom);
/*
- * All the same pseudo - mark the phi-nodes unused
- * and convert the load into a LNOP and replace the
- * pseudo.
+ * All the same pseudo - convert the load into a pseudo.
*/
- FOR_EACH_PTR(dominators, phi) {
- kill_instruction(phi->def);
- } END_FOR_EACH_PTR(phi);
convert_load_instruction(insn, new);
return;
complex_phi:
+ /*
+ * Not identical pseudos - create a phisrc for each
+ * dominators and convert the load into a phi-node.
+ */
+ dominators = add_load_dominators(insn, doms, ident);
+
/* We leave symbol pseudos with a bogus usage list here */
if (insn->src->type != PSEUDO_SYM)
kill_use(&insn->src);
diff --git a/validation/loop-linearization.c b/validation/loop-linearization.c
index d53366bde..ab731dc15 100644
--- a/validation/loop-linearization.c
+++ b/validation/loop-linearization.c
@@ -39,11 +39,11 @@ static int fdo(void)
ffor:
.L0:
<entry-point>
- phisrc.32 %phi5(i) <- $0
+ phisrc.32 %phi3(i) <- $0
br .L4
.L4:
- phi.32 %r1(i) <- %phi5(i), %phi6(i)
+ phi.32 %r1(i) <- %phi3(i), %phi4(i)
setlt.32 %r2 <- %r1(i), $10
cbr %r2, .L1, .L3
@@ -58,7 +58,7 @@ ffor:
.L2:
add.32 %r7 <- %r1(i), $1
- phisrc.32 %phi6(i) <- %r7
+ phisrc.32 %phi4(i) <- %r7
br .L4
.L3:
@@ -73,11 +73,11 @@ ffor:
fwhile:
.L8:
<entry-point>
- phisrc.32 %phi11(i) <- $0
+ phisrc.32 %phi7(i) <- $0
br .L12
.L12:
- phi.32 %r8(i) <- %phi11(i), %phi12(i)
+ phi.32 %r8(i) <- %phi7(i), %phi8(i)
setlt.32 %r9 <- %r8(i), $10
cbr %r9, .L9, .L11
@@ -87,51 +87,51 @@ fwhile:
cbr %r11, .L14, .L13
.L13:
- phisrc.32 %phi7(return) <- $0
+ phisrc.32 %phi5(return) <- $0
br .L15
.L14:
add.32 %r14 <- %r8(i), $1
- phisrc.32 %phi12(i) <- %r14
+ phisrc.32 %phi8(i) <- %r14
br .L12
.L11:
- phisrc.32 %phi8(return) <- $1
+ phisrc.32 %phi6(return) <- $1
br .L15
.L15:
- phi.32 %r12 <- %phi7(return), %phi8(return)
+ phi.32 %r12 <- %phi5(return), %phi6(return)
ret.32 %r12
fdo:
.L16:
<entry-point>
- phisrc.32 %phi16(i) <- $0
+ phisrc.32 %phi11(i) <- $0
br .L17
.L17:
- phi.32 %r15(i) <- %phi16(i), %phi17(i)
+ phi.32 %r15(i) <- %phi11(i), %phi12(i)
push.32 %r15(i)
call.32 %r16 <- p
cbr %r16, .L18, .L20
.L20:
- phisrc.32 %phi13(return) <- $0
+ phisrc.32 %phi9(return) <- $0
br .L22
.L18:
add.32 %r19 <- %r15(i), $1
setlt.32 %r20 <- %r15(i), $10
- phisrc.32 %phi17(i) <- %r19
+ phisrc.32 %phi12(i) <- %r19
cbr %r20, .L17, .L19
.L19:
- phisrc.32 %phi14(return) <- $1
+ phisrc.32 %phi10(return) <- $1
br .L22
.L22:
- phi.32 %r17 <- %phi13(return), %phi14(return)
+ phi.32 %r17 <- %phi9(return), %phi10(return)
ret.32 %r17
--
2.12.0
^ permalink raw reply related [flat|nested] 10+ messages in thread* Re: [PATCH 0/8] avoid creating orphaned OP_PHISRCs
2017-04-13 16:55 [PATCH 0/8] avoid creating orphaned OP_PHISRCs Luc Van Oostenryck
` (7 preceding siblings ...)
2017-04-13 16:55 ` [PATCH 8/8] avoid creating unneeded phi-sources Luc Van Oostenryck
@ 2017-05-18 17:04 ` Luc Van Oostenryck
8 siblings, 0 replies; 10+ messages in thread
From: Luc Van Oostenryck @ 2017-05-18 17:04 UTC (permalink / raw)
To: linux-sparse
Another problem with the creation and placement of phi-nodes
is with some code like:
#define CHECK(t, c, N) \
t = ptr[N]; \
if (t) \
c++;
int foo(int *ptr);
int foo(int *ptr)
{
int c = 0;
int t;
CHECK(t, c, 0x000);
CHECK(t, c, 0x001);
return c;
}
which will be linearized as:
foo:
load.32 %r2 <- 0[%arg1]
phisrc.32 %phi2(c) <- $0
phisrc.32 %phi5(c) <- $0
cbr %r2, .L1, .L2
.L1:
phisrc.32 %phi3(c) <- $1
phisrc.32 %phi6(c) <- $1
br .L2
.L2:
load.32 %r7 <- 4[%arg1]
cbr %r7, .L3, .L4
.L3:
phi.32 %r9 <- %phi5(c), %phi6(c)
add.32 %r10 <- %r9, $1
phisrc.32 %phi4(c) <- %r10
br .L4
.L4:
phi.32 %r11 <- %phi2(c), %phi3(c), %phi4(c)
ret.32 %r11
This is with the last phi-node and the placement of its phisrcs.
- .L4 has 2 parents, .L2 & .L3, so the phi-node should have 2 sources
- the 2 sources should be placed (at the end of) .L2 & L3
- only %phi4 is really well placed
- %phi3 is not placed at .L2 but before (which is fine too)
- the real problem is with %phi2: all paths to .L4 go where %phi3
& %phi4 are defined, so %phi2 is in fact dead and should never
be a source for the last phi-node.
There is worst though, here the CHECK is only two times.
If called N times, the last phi-node will have N sources
(while still having only 2 reaching paths), quadratic behaviour
thus (at N=300, the show_instruction() buffer is too small, at
N=2000 it needs 50 secs of processing).
Note that the CHECK macro is called here with the array ptr and the
problem may seem a bit artificial since it's like a manual loop
unrolling, but I can very well imagine some similar code called
not on the array elements but on a few functions (checking for
some ressources availability for example).
-- Luc
^ permalink raw reply [flat|nested] 10+ messages in thread