From 92169b2aecd4794b7eee21f869228967245c87e2 Mon Sep 17 00:00:00 2001 From: Luc Van Oostenryck Date: Sat, 2 Jan 2021 22:30:40 +0100 Subject: add testcases for stores simplifications Signed-off-by: Luc Van Oostenryck --- validation/memops/kill-dead-store-parent0.c | 15 +++++++++++++++ validation/memops/kill-dead-store-parent2.c | 26 ++++++++++++++++++++++++++ validation/memops/kill-redundant-store0.c | 14 ++++++++++++++ 3 files changed, 55 insertions(+) create mode 100644 validation/memops/kill-dead-store-parent0.c create mode 100644 validation/memops/kill-dead-store-parent2.c create mode 100644 validation/memops/kill-redundant-store0.c diff --git a/validation/memops/kill-dead-store-parent0.c b/validation/memops/kill-dead-store-parent0.c new file mode 100644 index 00000000..1413134b --- /dev/null +++ b/validation/memops/kill-dead-store-parent0.c @@ -0,0 +1,15 @@ +void foo(int *ptr, int p) +{ + if (p) + *ptr = 1; + *ptr = 0; +} + +/* + * check-name: kill-dead-store-parent0 + * check-command: test-linearize -Wno-decl $file + * check-known-to-fail + * + * check-output-ignore + * check-output-pattern(1): store + */ diff --git a/validation/memops/kill-dead-store-parent2.c b/validation/memops/kill-dead-store-parent2.c new file mode 100644 index 00000000..b563fd31 --- /dev/null +++ b/validation/memops/kill-dead-store-parent2.c @@ -0,0 +1,26 @@ +int ladder02(int *ptr, int p, int x) +{ + *ptr = x++; + if (p) + goto l11; + else + goto l12; +l11: + *ptr = x++; + goto l20; +l12: + *ptr = x++; + goto l20; +l20: + *ptr = x++; + return *ptr; +} + +/* + * check-name: kill-dead-store-parent2 + * check-command: test-linearize -Wno-decl $file + * check-known-to-fail + * + * check-output-ignore + * check-output-pattern(1): store + */ diff --git a/validation/memops/kill-redundant-store0.c b/validation/memops/kill-redundant-store0.c new file mode 100644 index 00000000..e911166d --- /dev/null +++ b/validation/memops/kill-redundant-store0.c @@ -0,0 +1,14 @@ +void foo(int *ptr) +{ + int i = *ptr; + *ptr = i; +} + +/* + * check-name: kill-redundant-store0 + * check-command: test-linearize -Wno-decl $file + * check-known-to-fail + * + * check-output-ignore + * check-output-excludes: store + */ -- cgit 1.2.3-korg From 74d910d66998c7c63f0b05bcac7287b46043c720 Mon Sep 17 00:00:00 2001 From: Luc Van Oostenryck Date: Tue, 1 Dec 2020 00:10:35 +0100 Subject: extract try_to_kill_store() from kill_dominated_stores() Move the test/replace part of the store simplification in a separate function so that it can be reused. Signed-off-by: Luc Van Oostenryck --- memops.c | 30 +++++++++++++++++++----------- 1 file changed, 19 insertions(+), 11 deletions(-) diff --git a/memops.c b/memops.c index ff54208e..31fd2d3e 100644 --- a/memops.c +++ b/memops.c @@ -204,6 +204,23 @@ next_load: } END_FOR_EACH_PTR_REVERSE(insn); } +static bool try_to_kill_store(pseudo_t pseudo, struct instruction *insn, + struct instruction *dom, int local) +{ + int dominance = dominates(pseudo, insn, dom, local); + + if (dominance) { + /* possible partial dominance? */ + if (dominance < 0) + return false; + if (dom->opcode == OP_LOAD) + return false; + /* Yeehaa! Found one! */ + kill_instruction_force(dom); + } + return true; +} + static void kill_dominated_stores(struct basic_block *bb) { struct instruction *insn; @@ -223,19 +240,10 @@ static void kill_dominated_stores(struct basic_block *bb) local = local_pseudo(pseudo); RECURSE_PTR_REVERSE(insn, dom) { - int dominance; if (!dom->bb) continue; - dominance = dominates(pseudo, insn, dom, local); - if (dominance) { - /* possible partial dominance? */ - if (dominance < 0) - goto next_store; - if (dom->opcode == OP_LOAD) - goto next_store; - /* Yeehaa! Found one! */ - kill_instruction_force(dom); - } + if (!try_to_kill_store(pseudo, insn, dom, local)) + goto next_store; } END_FOR_EACH_PTR_REVERSE(dom); /* OK, we should check the parents now */ -- cgit 1.2.3-korg From fece51c37252e654cd46eda5fd12938b4be7deff Mon Sep 17 00:00:00 2001 From: Luc Van Oostenryck Date: Tue, 1 Dec 2020 00:00:43 +0100 Subject: volatile stores are never dead so they shouldn't be killed. Signed-off-by: Luc Van Oostenryck --- memops.c | 2 ++ 1 file changed, 2 insertions(+) diff --git a/memops.c b/memops.c index 31fd2d3e..8020f2e6 100644 --- a/memops.c +++ b/memops.c @@ -215,6 +215,8 @@ static bool try_to_kill_store(pseudo_t pseudo, struct instruction *insn, return false; if (dom->opcode == OP_LOAD) return false; + if (dom->is_volatile) + return false; /* Yeehaa! Found one! */ kill_instruction_force(dom); } -- cgit 1.2.3-korg From e0c12f39daec8b2d13fb84e80033f7d9052374c7 Mon Sep 17 00:00:00 2001 From: Luc Van Oostenryck Date: Tue, 1 Dec 2020 00:10:35 +0100 Subject: kill parent's dead stores too kill_dominated_stores() identify and remove dead stores (stores unneeded because the same location is overwritten later by another store) only when both stores are in the same basic block. Slightly improve this by also handling the case when the dead store is in a parent BB of the "live" store. Signed-off-by: Luc Van Oostenryck --- memops.c | 16 ++++++++++++++++ validation/memops/kill-dead-store-parent0.c | 1 - validation/memops/kill-dead-store-parent2.c | 1 - 3 files changed, 16 insertions(+), 2 deletions(-) diff --git a/memops.c b/memops.c index 8020f2e6..44d90754 100644 --- a/memops.c +++ b/memops.c @@ -231,6 +231,7 @@ static void kill_dominated_stores(struct basic_block *bb) if (!insn->bb) continue; if (insn->opcode == OP_STORE) { + struct basic_block *par; struct instruction *dom; pseudo_t pseudo = insn->src; int local; @@ -249,6 +250,21 @@ static void kill_dominated_stores(struct basic_block *bb) } END_FOR_EACH_PTR_REVERSE(dom); /* OK, we should check the parents now */ + FOR_EACH_PTR(bb->parents, par) { + + if (bb_list_size(par->children) != 1) + goto next_parent; + FOR_EACH_PTR(par->insns, dom) { + if (!dom->bb) + continue; + if (dom == insn) + goto next_parent; + if (!try_to_kill_store(pseudo, insn, dom, local)) + goto next_parent; + } END_FOR_EACH_PTR(dom); +next_parent: + ; + } END_FOR_EACH_PTR(par); } next_store: /* Do the next one */; diff --git a/validation/memops/kill-dead-store-parent0.c b/validation/memops/kill-dead-store-parent0.c index 1413134b..c1b2466c 100644 --- a/validation/memops/kill-dead-store-parent0.c +++ b/validation/memops/kill-dead-store-parent0.c @@ -8,7 +8,6 @@ void foo(int *ptr, int p) /* * check-name: kill-dead-store-parent0 * check-command: test-linearize -Wno-decl $file - * check-known-to-fail * * check-output-ignore * check-output-pattern(1): store diff --git a/validation/memops/kill-dead-store-parent2.c b/validation/memops/kill-dead-store-parent2.c index b563fd31..4f7b9dd9 100644 --- a/validation/memops/kill-dead-store-parent2.c +++ b/validation/memops/kill-dead-store-parent2.c @@ -19,7 +19,6 @@ l20: /* * check-name: kill-dead-store-parent2 * check-command: test-linearize -Wno-decl $file - * check-known-to-fail * * check-output-ignore * check-output-pattern(1): store -- cgit 1.2.3-korg From 23109ddefaadf1a476ea47d123994e5f073f701e Mon Sep 17 00:00:00 2001 From: Luc Van Oostenryck Date: Tue, 1 Dec 2020 23:46:56 +0100 Subject: kill redundant stores (local) A store is called 'redundant' when the corresponding location already contains the value that will be stored. This patch removes such stores in the case where the memops which make them redundant is in the same basic block. Signed-off-by: Luc Van Oostenryck --- memops.c | 5 +++++ validation/memops/kill-redundant-store0.c | 1 - 2 files changed, 5 insertions(+), 1 deletion(-) diff --git a/memops.c b/memops.c index 44d90754..f734f6eb 100644 --- a/memops.c +++ b/memops.c @@ -213,6 +213,11 @@ static bool try_to_kill_store(pseudo_t pseudo, struct instruction *insn, /* possible partial dominance? */ if (dominance < 0) return false; + if (insn->target == dom->target && insn->bb == dom->bb) { + // found a memop which makes the store redundant + kill_instruction_force(insn); + return false; + } if (dom->opcode == OP_LOAD) return false; if (dom->is_volatile) diff --git a/validation/memops/kill-redundant-store0.c b/validation/memops/kill-redundant-store0.c index e911166d..8819938f 100644 --- a/validation/memops/kill-redundant-store0.c +++ b/validation/memops/kill-redundant-store0.c @@ -7,7 +7,6 @@ void foo(int *ptr) /* * check-name: kill-redundant-store0 * check-command: test-linearize -Wno-decl $file - * check-known-to-fail * * check-output-ignore * check-output-excludes: store -- cgit 1.2.3-korg