* [PATCH 00/16] instructions killing & operands usage
@ 2017-02-16 4:56 Luc Van Oostenryck
2017-02-16 4:56 ` [PATCH 01/16] add killing of OP_SLICEs Luc Van Oostenryck
` (15 more replies)
0 siblings, 16 replies; 17+ messages in thread
From: Luc Van Oostenryck @ 2017-02-16 4:56 UTC (permalink / raw)
To: linux-sparse; +Cc: Christopher Li, Luc Van Oostenryck
This serie aims at solving a number of problems caused by
imcomplete, missing or wrong handling of operands usage when
killing an instruction
Luc Van Oostenryck (16):
add killing of OP_SLICEs
add killing of OP_PHISOURCEs
add helper kill_use_list()
fix killing of OP_PHIs
fix clear_phi(), replace it by kill_instruction()
remove unused clear_phi()
fix killing of otherwise not-handled instructions
kill_instruction() may need to be forced or not
add killing of pure calls
fix killing OP_CALL via pointers
add killing of non-volatile loads
add killing of stores
fix killing of rewritten loads
use kill_instruction() when killing an OP_PHI during CSE
use kill_instruction() when killing any instructions during CSE
fix OP_PHI usage in try_to_simplify_bb()
cse.c | 15 +--------
flow.c | 7 ++--
flow.h | 11 +++++-
simplify.c | 73 +++++++++++++++++++++++++++++++---------
validation/kill-cse.c | 21 ++++++++++++
validation/kill-load.c | 17 ++++++++++
validation/kill-phi-node.c | 9 +++++
validation/kill-phi-ttsbb.c | 28 +++++++++++++++
validation/kill-phisrc.c | 21 ++++++++++++
validation/kill-pure-call.c | 17 ++++++++++
validation/kill-rewritten-load.c | 16 +++++++++
validation/kill-slice.c | 19 +++++++++++
validation/kill-store.c | 16 +++++++++
13 files changed, 236 insertions(+), 34 deletions(-)
create mode 100644 validation/kill-cse.c
create mode 100644 validation/kill-load.c
create mode 100644 validation/kill-phi-ttsbb.c
create mode 100644 validation/kill-phisrc.c
create mode 100644 validation/kill-pure-call.c
create mode 100644 validation/kill-rewritten-load.c
create mode 100644 validation/kill-slice.c
create mode 100644 validation/kill-store.c
--
2.11.0
^ permalink raw reply [flat|nested] 17+ messages in thread
* [PATCH 01/16] add killing of OP_SLICEs
2017-02-16 4:56 [PATCH 00/16] instructions killing & operands usage Luc Van Oostenryck
@ 2017-02-16 4:56 ` Luc Van Oostenryck
2017-02-16 4:56 ` [PATCH 02/16] add killing of OP_PHISOURCEs Luc Van Oostenryck
` (14 subsequent siblings)
15 siblings, 0 replies; 17+ messages in thread
From: Luc Van Oostenryck @ 2017-02-16 4:56 UTC (permalink / raw)
To: linux-sparse; +Cc: Christopher Li, Luc Van Oostenryck
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
simplify.c | 1 +
validation/kill-slice.c | 19 +++++++++++++++++++
2 files changed, 20 insertions(+)
create mode 100644 validation/kill-slice.c
diff --git a/simplify.c b/simplify.c
index 2a1f0b200..90e45bf1a 100644
--- a/simplify.c
+++ b/simplify.c
@@ -203,6 +203,7 @@ void kill_instruction(struct instruction *insn)
case OP_PTRCAST:
case OP_SETVAL:
case OP_NOT: case OP_NEG:
+ case OP_SLICE:
kill_use(&insn->src1);
break;
diff --git a/validation/kill-slice.c b/validation/kill-slice.c
new file mode 100644
index 000000000..00db0e0f7
--- /dev/null
+++ b/validation/kill-slice.c
@@ -0,0 +1,19 @@
+struct bar {
+ int x;
+ int y[2];
+};
+struct bar bar(void);
+
+int foo(void)
+{
+ int x = bar().x;
+ return x & 0;
+}
+
+/*
+ * check-name: kill-slice
+ * check-command: test-linearize -Wno-decl $file
+ * check-output-ignore
+ *
+ * check-output-excludes: slice\\.
+ */
--
2.11.0
^ permalink raw reply related [flat|nested] 17+ messages in thread
* [PATCH 02/16] add killing of OP_PHISOURCEs
2017-02-16 4:56 [PATCH 00/16] instructions killing & operands usage Luc Van Oostenryck
2017-02-16 4:56 ` [PATCH 01/16] add killing of OP_SLICEs Luc Van Oostenryck
@ 2017-02-16 4:56 ` Luc Van Oostenryck
2017-02-16 4:56 ` [PATCH 03/16] add helper kill_use_list() Luc Van Oostenryck
` (13 subsequent siblings)
15 siblings, 0 replies; 17+ messages in thread
From: Luc Van Oostenryck @ 2017-02-16 4:56 UTC (permalink / raw)
To: linux-sparse; +Cc: Christopher Li, Luc Van Oostenryck
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
simplify.c | 3 +++
validation/kill-phisrc.c | 21 +++++++++++++++++++++
2 files changed, 24 insertions(+)
create mode 100644 validation/kill-phisrc.c
diff --git a/simplify.c b/simplify.c
index 90e45bf1a..ced63bfa3 100644
--- a/simplify.c
+++ b/simplify.c
@@ -210,6 +210,9 @@ void kill_instruction(struct instruction *insn)
case OP_PHI:
clear_phi(insn);
break;
+ case OP_PHISOURCE:
+ kill_use(&insn->phi_src);
+ break;
case OP_SYMADDR:
repeat_phase |= REPEAT_SYMBOL_CLEANUP;
diff --git a/validation/kill-phisrc.c b/validation/kill-phisrc.c
new file mode 100644
index 000000000..f00dbed24
--- /dev/null
+++ b/validation/kill-phisrc.c
@@ -0,0 +1,21 @@
+int foo(int a, int b)
+{
+ int r = a + b;
+
+ if (a && 0) {
+ int s = r;
+ if (b)
+ s = 0;
+ (void) s;
+ }
+
+ return 0;
+}
+
+/*
+ * check-name: kill-phisrc
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-ignore
+ * check-output-excludes: add\\.
+ */
--
2.11.0
^ permalink raw reply related [flat|nested] 17+ messages in thread
* [PATCH 03/16] add helper kill_use_list()
2017-02-16 4:56 [PATCH 00/16] instructions killing & operands usage Luc Van Oostenryck
2017-02-16 4:56 ` [PATCH 01/16] add killing of OP_SLICEs Luc Van Oostenryck
2017-02-16 4:56 ` [PATCH 02/16] add killing of OP_PHISOURCEs Luc Van Oostenryck
@ 2017-02-16 4:56 ` Luc Van Oostenryck
2017-02-16 4:56 ` [PATCH 04/16] fix killing of OP_PHIs Luc Van Oostenryck
` (12 subsequent siblings)
15 siblings, 0 replies; 17+ messages in thread
From: Luc Van Oostenryck @ 2017-02-16 4:56 UTC (permalink / raw)
To: linux-sparse; +Cc: Christopher Li, Luc Van Oostenryck
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
simplify.c | 10 ++++++++++
1 file changed, 10 insertions(+)
diff --git a/simplify.c b/simplify.c
index ced63bfa3..d4e730894 100644
--- a/simplify.c
+++ b/simplify.c
@@ -182,6 +182,16 @@ void kill_use(pseudo_t *usep)
}
}
+static void kill_use_list(struct pseudo_list *list)
+{
+ pseudo_t p;
+ FOR_EACH_PTR(list, p) {
+ if (p == VOID)
+ continue;
+ kill_use(THIS_ADDRESS(p));
+ } END_FOR_EACH_PTR(p);
+}
+
void kill_instruction(struct instruction *insn)
{
if (!insn || !insn->bb)
--
2.11.0
^ permalink raw reply related [flat|nested] 17+ messages in thread
* [PATCH 04/16] fix killing of OP_PHIs
2017-02-16 4:56 [PATCH 00/16] instructions killing & operands usage Luc Van Oostenryck
` (2 preceding siblings ...)
2017-02-16 4:56 ` [PATCH 03/16] add helper kill_use_list() Luc Van Oostenryck
@ 2017-02-16 4:56 ` Luc Van Oostenryck
2017-02-16 4:56 ` [PATCH 05/16] fix clear_phi(), replace it by kill_instruction() Luc Van Oostenryck
` (11 subsequent siblings)
15 siblings, 0 replies; 17+ messages in thread
From: Luc Van Oostenryck @ 2017-02-16 4:56 UTC (permalink / raw)
To: linux-sparse; +Cc: Christopher Li, Luc Van Oostenryck
OP_PHIs were killed by calling clear_phi() but this function
only replaces the phi node's sources by VOID without adjusting
the usage of these sources.
Fix this by instead calling kill_use() on each of the sources
via the newly created helper kill_use_list().
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
simplify.c | 2 +-
validation/kill-phi-node.c | 9 +++++++++
2 files changed, 10 insertions(+), 1 deletion(-)
diff --git a/simplify.c b/simplify.c
index d4e730894..17f1e2b61 100644
--- a/simplify.c
+++ b/simplify.c
@@ -218,7 +218,7 @@ void kill_instruction(struct instruction *insn)
break;
case OP_PHI:
- clear_phi(insn);
+ kill_use_list(insn->phi_list);
break;
case OP_PHISOURCE:
kill_use(&insn->phi_src);
diff --git a/validation/kill-phi-node.c b/validation/kill-phi-node.c
index 88de9f962..cff62b649 100644
--- a/validation/kill-phi-node.c
+++ b/validation/kill-phi-node.c
@@ -9,6 +9,15 @@ void foo(int a, int *b, unsigned int g)
d = 8;
}
+int bar(void);
+int bar(void)
+{
+ int i;
+ for (i = 0; i; i--)
+ ;
+ return 0;
+}
+
/*
* check-name: kill-phi-node
* check-command: test-linearize $file
--
2.11.0
^ permalink raw reply related [flat|nested] 17+ messages in thread
* [PATCH 05/16] fix clear_phi(), replace it by kill_instruction()
2017-02-16 4:56 [PATCH 00/16] instructions killing & operands usage Luc Van Oostenryck
` (3 preceding siblings ...)
2017-02-16 4:56 ` [PATCH 04/16] fix killing of OP_PHIs Luc Van Oostenryck
@ 2017-02-16 4:56 ` Luc Van Oostenryck
2017-02-16 4:56 ` [PATCH 06/16] remove unused clear_phi() Luc Van Oostenryck
` (10 subsequent siblings)
15 siblings, 0 replies; 17+ messages in thread
From: Luc Van Oostenryck @ 2017-02-16 4:56 UTC (permalink / raw)
To: linux-sparse; +Cc: Christopher Li, Luc Van Oostenryck
clear_phi() only replaces a phi-node's sources by VOID
without adjusting the usage of these sources.
As such it can't be used for cleaning things before
removing an OP_PHI.
Fix this by replacing calls to clear_phi() by calls
to kill_instruction().
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
simplify.c | 6 +++---
1 file changed, 3 insertions(+), 3 deletions(-)
diff --git a/simplify.c b/simplify.c
index 17f1e2b61..ddd0aa9c5 100644
--- a/simplify.c
+++ b/simplify.c
@@ -110,7 +110,7 @@ static int if_convert_phi(struct instruction *insn)
* the conditional branch too.
*/
insert_select(source, br, insn, p1, p2);
- clear_phi(insn);
+ kill_instruction(insn);
return REPEAT_CSE;
}
@@ -140,7 +140,7 @@ static int clean_up_phi(struct instruction *insn)
if (same) {
pseudo_t pseudo = last ? last->src1 : VOID;
convert_instruction_target(insn, pseudo);
- clear_phi(insn);
+ kill_instruction(insn);
return REPEAT_CSE;
}
@@ -1142,7 +1142,7 @@ int simplify_instruction(struct instruction *insn)
return simplify_cast(insn);
case OP_PHI:
if (dead_insn(insn, NULL, NULL, NULL)) {
- clear_phi(insn);
+ kill_use_list(insn->phi_list);
return REPEAT_CSE;
}
return clean_up_phi(insn);
--
2.11.0
^ permalink raw reply related [flat|nested] 17+ messages in thread
* [PATCH 06/16] remove unused clear_phi()
2017-02-16 4:56 [PATCH 00/16] instructions killing & operands usage Luc Van Oostenryck
` (4 preceding siblings ...)
2017-02-16 4:56 ` [PATCH 05/16] fix clear_phi(), replace it by kill_instruction() Luc Van Oostenryck
@ 2017-02-16 4:56 ` Luc Van Oostenryck
2017-02-16 4:56 ` [PATCH 07/16] fix killing of otherwise not-handled instructions Luc Van Oostenryck
` (9 subsequent siblings)
15 siblings, 0 replies; 17+ messages in thread
From: Luc Van Oostenryck @ 2017-02-16 4:56 UTC (permalink / raw)
To: linux-sparse; +Cc: Christopher Li, Luc Van Oostenryck
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
simplify.c | 10 ----------
1 file changed, 10 deletions(-)
diff --git a/simplify.c b/simplify.c
index ddd0aa9c5..82ae97ae9 100644
--- a/simplify.c
+++ b/simplify.c
@@ -26,16 +26,6 @@ static struct basic_block *phi_parent(struct basic_block *source, pseudo_t pseud
return first_basic_block(source->parents);
}
-static void clear_phi(struct instruction *insn)
-{
- pseudo_t phi;
-
- insn->bb = NULL;
- FOR_EACH_PTR(insn->phi_list, phi) {
- *THIS_ADDRESS(phi) = VOID;
- } END_FOR_EACH_PTR(phi);
-}
^ permalink raw reply related [flat|nested] 17+ messages in thread
* [PATCH 07/16] fix killing of otherwise not-handled instructions
2017-02-16 4:56 [PATCH 00/16] instructions killing & operands usage Luc Van Oostenryck
` (5 preceding siblings ...)
2017-02-16 4:56 ` [PATCH 06/16] remove unused clear_phi() Luc Van Oostenryck
@ 2017-02-16 4:56 ` Luc Van Oostenryck
2017-02-16 4:57 ` [PATCH 08/16] kill_instruction() may need to be forced or not Luc Van Oostenryck
` (8 subsequent siblings)
15 siblings, 0 replies; 17+ messages in thread
From: Luc Van Oostenryck @ 2017-02-16 4:56 UTC (permalink / raw)
To: linux-sparse; +Cc: Christopher Li, Luc Van Oostenryck
The instructions which are otherwise not handled in
kill_instruction() were simply ignored but they must
still have their ->bb set to NULL.
Fix this by separating the default case from OP_ENTRY,
the only kind that must be ignored in all circonstances.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
simplify.c | 4 +++-
1 file changed, 3 insertions(+), 1 deletion(-)
diff --git a/simplify.c b/simplify.c
index 82ae97ae9..1fbad1060 100644
--- a/simplify.c
+++ b/simplify.c
@@ -228,9 +228,11 @@ void kill_instruction(struct instruction *insn)
break;
case OP_ENTRY:
- default:
/* ignore */
return;
+
+ default:
+ break;
}
insn->bb = NULL;
--
2.11.0
^ permalink raw reply related [flat|nested] 17+ messages in thread
* [PATCH 08/16] kill_instruction() may need to be forced or not
2017-02-16 4:56 [PATCH 00/16] instructions killing & operands usage Luc Van Oostenryck
` (6 preceding siblings ...)
2017-02-16 4:56 ` [PATCH 07/16] fix killing of otherwise not-handled instructions Luc Van Oostenryck
@ 2017-02-16 4:57 ` Luc Van Oostenryck
2017-02-16 4:57 ` [PATCH 09/16] add killing of pure calls Luc Van Oostenryck
` (7 subsequent siblings)
15 siblings, 0 replies; 17+ messages in thread
From: Luc Van Oostenryck @ 2017-02-16 4:57 UTC (permalink / raw)
To: linux-sparse; +Cc: Christopher Li, Luc Van Oostenryck
There is essentially three cases where kill_instruction() is
called:
1) when implicitely removing an instruction via
kill_use()/remove_usage() once all users of (the target of)
this instruction have been removed and so this instruction
become unneeded.
2) when explicitely removing a specific instruction.
3) when explicitely removing all instructions in a basic block
because it became unreachable.
For 'pure' instructions, like the arithmetic operators, these
three cases can be handled exactly the same but for instructions
having side-effects, special care is needed.
For them case 1) should do nothing while cases 2) & 3) should
remove the instruction and adjust the usage of its operands like
for normal instructions.
To handle this gracefully:
- rename kill_instruction() into kill_insn()
- add a new argument ('force') to kill_insn()
- create kill_instruction() & kill_instruction_force() as inline
functions calling kill_insn() with 'force' set respectively to 0 & 1.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
flow.c | 3 +--
flow.h | 11 ++++++++++-
simplify.c | 11 ++++++++++-
3 files changed, 21 insertions(+), 4 deletions(-)
diff --git a/flow.c b/flow.c
index ef07b6db9..8409fac60 100644
--- a/flow.c
+++ b/flow.c
@@ -759,13 +759,12 @@ void kill_bb(struct basic_block *bb)
struct basic_block *child, *parent;
FOR_EACH_PTR(bb->insns, insn) {
- kill_instruction(insn);
+ kill_instruction_force(insn);
kill_defs(insn);
/*
* We kill unreachable instructions even if they
* otherwise aren't "killable" (e.g. volatile loads)
*/
- insn->bb = NULL;
} END_FOR_EACH_PTR(insn);
bb->insns = NULL;
diff --git a/flow.h b/flow.h
index 370aaddf1..31ed80d40 100644
--- a/flow.h
+++ b/flow.h
@@ -23,9 +23,18 @@ extern int simplify_instruction(struct instruction *);
extern void kill_bb(struct basic_block *);
extern void kill_use(pseudo_t *);
-extern void kill_instruction(struct instruction *);
extern void kill_unreachable_bbs(struct entrypoint *ep);
+extern void kill_insn(struct instruction *, int force);
+static inline void kill_instruction(struct instruction *insn)
+{
+ kill_insn(insn, 0);
+}
+static inline void kill_instruction_force(struct instruction *insn)
+{
+ kill_insn(insn, 1);
+}
+
void check_access(struct instruction *insn);
void convert_load_instruction(struct instruction *, pseudo_t);
void rewrite_load_instruction(struct instruction *, struct pseudo_list *);
diff --git a/simplify.c b/simplify.c
index 1fbad1060..b8944f0f7 100644
--- a/simplify.c
+++ b/simplify.c
@@ -182,7 +182,16 @@ static void kill_use_list(struct pseudo_list *list)
} END_FOR_EACH_PTR(p);
}
-void kill_instruction(struct instruction *insn)
+/*
+ * kill an instruction:
+ * - remove it from its bb
+ * - remove the usage of all its operands
+ * If forse is zero, the normal case, the function only for
+ * instructions free of (possible) side-effects. Otherwise
+ * the function does that unconditionally (must only be used
+ * for unreachable instructions.
+ */
+void kill_insn(struct instruction *insn, int force)
{
if (!insn || !insn->bb)
return;
--
2.11.0
^ permalink raw reply related [flat|nested] 17+ messages in thread
* [PATCH 09/16] add killing of pure calls
2017-02-16 4:56 [PATCH 00/16] instructions killing & operands usage Luc Van Oostenryck
` (7 preceding siblings ...)
2017-02-16 4:57 ` [PATCH 08/16] kill_instruction() may need to be forced or not Luc Van Oostenryck
@ 2017-02-16 4:57 ` Luc Van Oostenryck
2017-02-16 4:57 ` [PATCH 10/16] fix killing OP_CALL via pointers Luc Van Oostenryck
` (6 subsequent siblings)
15 siblings, 0 replies; 17+ messages in thread
From: Luc Van Oostenryck @ 2017-02-16 4:57 UTC (permalink / raw)
To: linux-sparse; +Cc: Christopher Li, Luc Van Oostenryck
OP_CALL were ignored by kill_instruction() but there are two cases
were something can or must be done:
1) if the function is pure, it is free of side-effects and can thus
be optimized away like others instructions.
2) if force-killed then we need to adjust the usage of all the arguments.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
simplify.c | 11 +++++++++++
validation/kill-pure-call.c | 17 +++++++++++++++++
2 files changed, 28 insertions(+)
create mode 100644 validation/kill-pure-call.c
diff --git a/simplify.c b/simplify.c
index b8944f0f7..cacf81f9f 100644
--- a/simplify.c
+++ b/simplify.c
@@ -236,6 +236,17 @@ void kill_insn(struct instruction *insn, int force)
kill_use(&insn->cond);
break;
+ case OP_CALL:
+ if (!force) {
+ /* a "pure" function can be killed too */
+ if (!(insn->func->type == PSEUDO_SYM))
+ return;
+ if (!(insn->func->sym->ctype.modifiers & MOD_PURE))
+ return;
+ }
+ kill_use_list(insn->arguments);
+ break;
+
case OP_ENTRY:
/* ignore */
return;
diff --git a/validation/kill-pure-call.c b/validation/kill-pure-call.c
new file mode 100644
index 000000000..d3f78c026
--- /dev/null
+++ b/validation/kill-pure-call.c
@@ -0,0 +1,17 @@
+int side(int a);
+int pure(int a) __attribute__((pure));
+
+int keep(int a) { return side(a) && 0; }
+int kill(int a) { return pure(a) && 0; }
+
+/*
+ * check-name: kill-pure-call
+ * check-command: test-linearize -Wno-decl $file
+ * check-description:
+ * See that the call is optimized away but only
+ * when the function is "pure".
+ *
+ * check-output-ignore
+ * check-output-contains: call\\..* side
+ * check-output-excludes: call\\..* pure
+ */
--
2.11.0
^ permalink raw reply related [flat|nested] 17+ messages in thread
* [PATCH 10/16] fix killing OP_CALL via pointers
2017-02-16 4:56 [PATCH 00/16] instructions killing & operands usage Luc Van Oostenryck
` (8 preceding siblings ...)
2017-02-16 4:57 ` [PATCH 09/16] add killing of pure calls Luc Van Oostenryck
@ 2017-02-16 4:57 ` Luc Van Oostenryck
2017-02-16 4:57 ` [PATCH 11/16] add killing of non-volatile loads Luc Van Oostenryck
` (5 subsequent siblings)
15 siblings, 0 replies; 17+ messages in thread
From: Luc Van Oostenryck @ 2017-02-16 4:57 UTC (permalink / raw)
To: linux-sparse; +Cc: Christopher Li, Luc Van Oostenryck
When killing an OP_CALL corresponding to a function pointer
the ->func field needs also to have its usage adjusted.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
simplify.c | 2 ++
1 file changed, 2 insertions(+)
diff --git a/simplify.c b/simplify.c
index cacf81f9f..b80d05b87 100644
--- a/simplify.c
+++ b/simplify.c
@@ -245,6 +245,8 @@ void kill_insn(struct instruction *insn, int force)
return;
}
kill_use_list(insn->arguments);
+ if (insn->func->type == PSEUDO_REG)
+ kill_use(&insn->func);
break;
case OP_ENTRY:
--
2.11.0
^ permalink raw reply related [flat|nested] 17+ messages in thread
* [PATCH 11/16] add killing of non-volatile loads
2017-02-16 4:56 [PATCH 00/16] instructions killing & operands usage Luc Van Oostenryck
` (9 preceding siblings ...)
2017-02-16 4:57 ` [PATCH 10/16] fix killing OP_CALL via pointers Luc Van Oostenryck
@ 2017-02-16 4:57 ` Luc Van Oostenryck
2017-02-16 4:57 ` [PATCH 12/16] add killing of stores Luc Van Oostenryck
` (4 subsequent siblings)
15 siblings, 0 replies; 17+ messages in thread
From: Luc Van Oostenryck @ 2017-02-16 4:57 UTC (permalink / raw)
To: linux-sparse; +Cc: Christopher Li, Luc Van Oostenryck
OP_LOADs were ignored by kill_instruction() but there are two cases
were something can or must be done:
1) if the is not a volatile one, it is free of side-effects and can thus
be optimized away like others instructions.
2) if force-killed then we need to adjust the usage of its operand.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
simplify.c | 6 ++++++
validation/kill-load.c | 17 +++++++++++++++++
2 files changed, 23 insertions(+)
create mode 100644 validation/kill-load.c
diff --git a/simplify.c b/simplify.c
index b80d05b87..a27f6a33a 100644
--- a/simplify.c
+++ b/simplify.c
@@ -249,6 +249,12 @@ void kill_insn(struct instruction *insn, int force)
kill_use(&insn->func);
break;
+ case OP_LOAD:
+ if (!force && insn->type->ctype.modifiers & MOD_VOLATILE)
+ return;
+ kill_use(&insn->src);
+ break;
+
case OP_ENTRY:
/* ignore */
return;
diff --git a/validation/kill-load.c b/validation/kill-load.c
new file mode 100644
index 000000000..45fb83e4b
--- /dev/null
+++ b/validation/kill-load.c
@@ -0,0 +1,17 @@
+int keep(volatile int *p) { return *p && 0; }
+int kill(int *p, int i) { return *p && 0; }
+void ind(volatile int *p,int i) { int v = i++; if (i && 0) p[v]; }
+
+
+/*
+ * check-name: kill-load
+ * check-command: test-linearize -Wno-decl $file
+ * check-description:
+ * Check that loads are optimized away but only
+ * when needed:
+ * - non-volatile
+ * - bb unreachable.
+ *
+ * check-output-ignore
+ * check-output-pattern-1-times: load\\.
+ */
--
2.11.0
^ permalink raw reply related [flat|nested] 17+ messages in thread
* [PATCH 12/16] add killing of stores
2017-02-16 4:56 [PATCH 00/16] instructions killing & operands usage Luc Van Oostenryck
` (10 preceding siblings ...)
2017-02-16 4:57 ` [PATCH 11/16] add killing of non-volatile loads Luc Van Oostenryck
@ 2017-02-16 4:57 ` Luc Van Oostenryck
2017-02-16 4:57 ` [PATCH 13/16] fix killing of rewritten loads Luc Van Oostenryck
` (3 subsequent siblings)
15 siblings, 0 replies; 17+ messages in thread
From: Luc Van Oostenryck @ 2017-02-16 4:57 UTC (permalink / raw)
To: linux-sparse; +Cc: Christopher Li, Luc Van Oostenryck
OP_STOREs were ignored by kill_instruction() but if it is force-killed
because the basic block it belong became unreachable then we need to
adjust the usage of its operands.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
simplify.c | 7 +++++++
validation/kill-store.c | 16 ++++++++++++++++
2 files changed, 23 insertions(+)
create mode 100644 validation/kill-store.c
diff --git a/simplify.c b/simplify.c
index a27f6a33a..804467f0d 100644
--- a/simplify.c
+++ b/simplify.c
@@ -255,6 +255,13 @@ void kill_insn(struct instruction *insn, int force)
kill_use(&insn->src);
break;
+ case OP_STORE:
+ if (!force)
+ return;
+ kill_use(&insn->src);
+ kill_use(&insn->target);
+ break;
+
case OP_ENTRY:
/* ignore */
return;
diff --git a/validation/kill-store.c b/validation/kill-store.c
new file mode 100644
index 000000000..8f7253226
--- /dev/null
+++ b/validation/kill-store.c
@@ -0,0 +1,16 @@
+void keep(int *p) { *p = 0; }
+void kill(int *p, int i) { if (i && 0) *p = 0; }
+void dead(int *p, int i) { int v = i++; if (i && 0) p[v] = 0; }
+
+
+/*
+ * check-name: kill-store
+ * check-command: test-linearize -Wno-decl $file
+ * check-description:
+ * Check that stores are optimized away but only
+ * when needed:
+ * - bb unreachable.
+ *
+ * check-output-ignore
+ * check-output-pattern-1-times: store\\.
+ */
--
2.11.0
^ permalink raw reply related [flat|nested] 17+ messages in thread
* [PATCH 13/16] fix killing of rewritten loads
2017-02-16 4:56 [PATCH 00/16] instructions killing & operands usage Luc Van Oostenryck
` (11 preceding siblings ...)
2017-02-16 4:57 ` [PATCH 12/16] add killing of stores Luc Van Oostenryck
@ 2017-02-16 4:57 ` Luc Van Oostenryck
2017-02-16 4:57 ` [PATCH 14/16] use kill_instruction() when killing an OP_PHI during CSE Luc Van Oostenryck
` (2 subsequent siblings)
15 siblings, 0 replies; 17+ messages in thread
From: Luc Van Oostenryck @ 2017-02-16 4:57 UTC (permalink / raw)
To: linux-sparse; +Cc: Christopher Li, Luc Van Oostenryck
OP_LOADs removed by rewrite_load_instruction() had their ->bb simply
set to NULL the usage of its operand was not adjusted.
Fix that by calling kill_instruction().
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
flow.c | 2 +-
validation/kill-rewritten-load.c | 16 ++++++++++++++++
2 files changed, 17 insertions(+), 1 deletion(-)
create mode 100644 validation/kill-rewritten-load.c
diff --git a/flow.c b/flow.c
index 8409fac60..fbac9336c 100644
--- a/flow.c
+++ b/flow.c
@@ -401,7 +401,7 @@ void rewrite_load_instruction(struct instruction *insn, struct pseudo_list *domi
* pseudo.
*/
FOR_EACH_PTR(dominators, phi) {
- phi->def->bb = NULL;
+ kill_instruction(phi->def);
} END_FOR_EACH_PTR(phi);
convert_load_instruction(insn, new);
return;
diff --git a/validation/kill-rewritten-load.c b/validation/kill-rewritten-load.c
new file mode 100644
index 000000000..31b895e53
--- /dev/null
+++ b/validation/kill-rewritten-load.c
@@ -0,0 +1,16 @@
+int foo(int i)
+{
+ i++;
+ if (i && 0)
+ i;
+ return 0;
+}
+
+
+/*
+ * check-name: kill-rewritten-load
+ * check-command: test-linearize -Wno-decl $file
+ * check-output-ignore
+ *
+ * check-output-excludes: add\\.
+ */
--
2.11.0
^ permalink raw reply related [flat|nested] 17+ messages in thread
* [PATCH 14/16] use kill_instruction() when killing an OP_PHI during CSE
2017-02-16 4:56 [PATCH 00/16] instructions killing & operands usage Luc Van Oostenryck
` (12 preceding siblings ...)
2017-02-16 4:57 ` [PATCH 13/16] fix killing of rewritten loads Luc Van Oostenryck
@ 2017-02-16 4:57 ` Luc Van Oostenryck
2017-02-16 4:57 ` [PATCH 15/16] use kill_instruction() when killing any instructions " Luc Van Oostenryck
2017-02-16 4:57 ` [PATCH 16/16] fix OP_PHI usage in try_to_simplify_bb() Luc Van Oostenryck
15 siblings, 0 replies; 17+ messages in thread
From: Luc Van Oostenryck @ 2017-02-16 4:57 UTC (permalink / raw)
To: linux-sparse; +Cc: Christopher Li, Luc Van Oostenryck
cse_one_instruction() contains some code to be executed when
an OP_PHI is eliminated. This code is roughly equivalent to
what is done in kill_instruction() for OP_PHI but not complete
since it doesn't recursively try to kill others instructions
which are used only by this OP_PHI.
Fix this and avoid duplicated code by replacing this code by
a call to kill_instruction().
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
cse.c | 10 +---------
1 file changed, 1 insertion(+), 9 deletions(-)
diff --git a/cse.c b/cse.c
index e8fbe344f..165b862af 100644
--- a/cse.c
+++ b/cse.c
@@ -252,15 +252,7 @@ static struct instruction * cse_one_instruction(struct instruction *insn, struct
convert_instruction_target(insn, def->target);
if (insn->opcode == OP_PHI) {
- /* Remove the instruction from PHI users */
- pseudo_t phi;
- FOR_EACH_PTR(insn->phi_list, phi) {
- struct pseudo_user *pu;
- FOR_EACH_PTR(phi->users, pu) {
- if (pu->insn == insn)
- DELETE_CURRENT_PTR(pu);
- } END_FOR_EACH_PTR(pu);
- } END_FOR_EACH_PTR(phi);
+ kill_instruction(insn);
}
insn->opcode = OP_NOP;
--
2.11.0
^ permalink raw reply related [flat|nested] 17+ messages in thread
* [PATCH 15/16] use kill_instruction() when killing any instructions during CSE
2017-02-16 4:56 [PATCH 00/16] instructions killing & operands usage Luc Van Oostenryck
` (13 preceding siblings ...)
2017-02-16 4:57 ` [PATCH 14/16] use kill_instruction() when killing an OP_PHI during CSE Luc Van Oostenryck
@ 2017-02-16 4:57 ` Luc Van Oostenryck
2017-02-16 4:57 ` [PATCH 16/16] fix OP_PHI usage in try_to_simplify_bb() Luc Van Oostenryck
15 siblings, 0 replies; 17+ messages in thread
From: Luc Van Oostenryck @ 2017-02-16 4:57 UTC (permalink / raw)
To: linux-sparse; +Cc: Christopher Li, Luc Van Oostenryck
Instructions removed during CSE had their ->bb simply set to NULL
and the usage of their operand was not adjusted.
Fix that by calling kill_instruction().
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
cse.c | 7 +------
validation/kill-cse.c | 21 +++++++++++++++++++++
2 files changed, 22 insertions(+), 6 deletions(-)
create mode 100644 validation/kill-cse.c
diff --git a/cse.c b/cse.c
index 165b862af..048a3eb79 100644
--- a/cse.c
+++ b/cse.c
@@ -251,12 +251,7 @@ static struct instruction * cse_one_instruction(struct instruction *insn, struct
{
convert_instruction_target(insn, def->target);
- if (insn->opcode == OP_PHI) {
- kill_instruction(insn);
- }
-
- insn->opcode = OP_NOP;
- insn->bb = NULL;
+ kill_instruction(insn);
repeat_phase |= REPEAT_CSE;
return def;
}
diff --git a/validation/kill-cse.c b/validation/kill-cse.c
new file mode 100644
index 000000000..2e2b10246
--- /dev/null
+++ b/validation/kill-cse.c
@@ -0,0 +1,21 @@
+int foo(int a)
+{
+ return ((a == 0) + 1) != ((a == 0) + 1);
+}
+
+/*
+ * check-name: kill-cse
+ * check-description:
+ * Verify that instructions removed at CSE are
+ * properly adjust the usage of their operands.
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-start
+foo:
+.L0:
+ <entry-point>
+ ret.32 $0
+
+
+ * check-output-end
+ */
--
2.11.0
^ permalink raw reply related [flat|nested] 17+ messages in thread
* [PATCH 16/16] fix OP_PHI usage in try_to_simplify_bb()
2017-02-16 4:56 [PATCH 00/16] instructions killing & operands usage Luc Van Oostenryck
` (14 preceding siblings ...)
2017-02-16 4:57 ` [PATCH 15/16] use kill_instruction() when killing any instructions " Luc Van Oostenryck
@ 2017-02-16 4:57 ` Luc Van Oostenryck
15 siblings, 0 replies; 17+ messages in thread
From: Luc Van Oostenryck @ 2017-02-16 4:57 UTC (permalink / raw)
To: linux-sparse; +Cc: Christopher Li, Luc Van Oostenryck
In try_to_simplify_bb(), simplification is attempted when a constant
phisrc whose corresponding phi-node control a conditional branch.
In this case, for the path between the phisrc and the conditional
branch, the following OP_PHI is sort of unneeded since the constant
determine which branch will be taken.
If this simplification can be made, it means that the OP_PHI
doesn't depend anymore on the constant phisrc. In fact the OP_PHI's bb
won't be anymore reachable from the constant phisrc's bb.
But currently, the OP_PHI usage is not adjusted and this leads to all
sort of oddities and causes to miss further simplifications.
The situation can be more concretly seen on test-linearize's output,
here an extract of Linux's kernel/futex.c:get_futex_key().
.L594:
...
br %r1294, .L651, .L656
.L651:
phisrc.32 %phi85 <- $1
br .L649
.L656:
...
and.64 %r1340 <- %r1339, $1
phisrc.32 %phi87 <- %r1340
phi.32 %r1343 <- %phi85, %phi87
br %r1343, .L649, .L648
The constant phisrc is %phi85 in .L651, the OP_PHI and the conditional
branch are .L656's last instructions (which have been packed with its
now unique parent which is sign of a problem). One can see that the
OP_PHi seems to depend on %phi85 (it's in its phi_list) but in fact
depends only on %phi87 (.L656 can't be reached from .L651 where %phi85
is defined since after the simplification .L651 directly branches to
one of the .L656's children, here .L649).
The fix consists in adjusting the OP_PHI's usage when the
simplification is made.
On the same code extract we can now see that the situation is more
"normal". In fact the OP_PHI have now been able to be optimized away
together, as well as .L651:
.L594:
...
br %r1294, .L649, .L656
.L656:
...
and.64 %r1340 <- %r1339, $1
br %r1340, .L649, .L648
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
flow.c | 2 ++
validation/kill-phi-ttsbb.c | 28 ++++++++++++++++++++++++++++
2 files changed, 30 insertions(+)
create mode 100644 validation/kill-phi-ttsbb.c
diff --git a/flow.c b/flow.c
index fbac9336c..088c21785 100644
--- a/flow.c
+++ b/flow.c
@@ -121,6 +121,8 @@ static int try_to_simplify_bb(struct basic_block *bb, struct instruction *first,
continue;
changed |= rewrite_branch(source, &br->bb_true, bb, target);
changed |= rewrite_branch(source, &br->bb_false, bb, target);
+ if (changed)
+ kill_use(THIS_ADDRESS(phi));
} END_FOR_EACH_PTR(phi);
return changed;
}
diff --git a/validation/kill-phi-ttsbb.c b/validation/kill-phi-ttsbb.c
new file mode 100644
index 000000000..178a65d19
--- /dev/null
+++ b/validation/kill-phi-ttsbb.c
@@ -0,0 +1,28 @@
+int def(void);
+void use(int);
+
+static int foo(int a, int b)
+{
+ int c;
+
+ if (a)
+ c = 1;
+ else
+ c = def();
+
+ if (c)
+ use(1);
+ else
+ use(0);
+}
+
+/*
+ * check-name: kill-phi-ttsbb
+ * check-description:
+ * Verify if OP_PHI usage is adjusted after successful try_to_simplify_bb()
+ * check-command: test-linearize $file
+ * check-output-ignore
+ *
+ * check-output-excludes: phi\\.
+ * check-output-excludes: phisrc\\.
+ */
--
2.11.0
^ permalink raw reply related [flat|nested] 17+ messages in thread
end of thread, other threads:[~2017-02-16 4:57 UTC | newest]
Thread overview: 17+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2017-02-16 4:56 [PATCH 00/16] instructions killing & operands usage Luc Van Oostenryck
2017-02-16 4:56 ` [PATCH 01/16] add killing of OP_SLICEs Luc Van Oostenryck
2017-02-16 4:56 ` [PATCH 02/16] add killing of OP_PHISOURCEs Luc Van Oostenryck
2017-02-16 4:56 ` [PATCH 03/16] add helper kill_use_list() Luc Van Oostenryck
2017-02-16 4:56 ` [PATCH 04/16] fix killing of OP_PHIs Luc Van Oostenryck
2017-02-16 4:56 ` [PATCH 05/16] fix clear_phi(), replace it by kill_instruction() Luc Van Oostenryck
2017-02-16 4:56 ` [PATCH 06/16] remove unused clear_phi() Luc Van Oostenryck
2017-02-16 4:56 ` [PATCH 07/16] fix killing of otherwise not-handled instructions Luc Van Oostenryck
2017-02-16 4:57 ` [PATCH 08/16] kill_instruction() may need to be forced or not Luc Van Oostenryck
2017-02-16 4:57 ` [PATCH 09/16] add killing of pure calls Luc Van Oostenryck
2017-02-16 4:57 ` [PATCH 10/16] fix killing OP_CALL via pointers Luc Van Oostenryck
2017-02-16 4:57 ` [PATCH 11/16] add killing of non-volatile loads Luc Van Oostenryck
2017-02-16 4:57 ` [PATCH 12/16] add killing of stores Luc Van Oostenryck
2017-02-16 4:57 ` [PATCH 13/16] fix killing of rewritten loads Luc Van Oostenryck
2017-02-16 4:57 ` [PATCH 14/16] use kill_instruction() when killing an OP_PHI during CSE Luc Van Oostenryck
2017-02-16 4:57 ` [PATCH 15/16] use kill_instruction() when killing any instructions " Luc Van Oostenryck
2017-02-16 4:57 ` [PATCH 16/16] fix OP_PHI usage in try_to_simplify_bb() Luc Van Oostenryck
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.