From: Richard Biener <rguenther@suse.de>
To: gcc-patches@gcc.gnu.org
Subject: [PATCH] tree-optimization/97806 - fix PRE expression post order
Date: Thu, 12 Nov 2020 11:00:38 +0100 (CET) [thread overview]
Message-ID: <nycvar.YFH.7.76.2011121100260.9842@elmra.sevgm.obk> (raw)
This fixes the postorder compute for the case of multiple
expression leaders for a value.
Bootstrapped and tested on x86_64-unknown-linux-gnu, pushed.
2020-11-12 Richard Biener <rguenther@suse.de>
PR tree-optimization/97806
* tree-ssa-pre.c (pre_expr_DFS): New overload for visiting
values, visiting all leaders for a value. Use a bitmap
for visited values.
(sorted_array_from_bitmap_set): Walk over values and adjust.
* gcc.dg/pr97806.c: New testcase.
---
gcc/testsuite/gcc.dg/pr97806.c | 16 ++++++++
gcc/tree-ssa-pre.c | 70 +++++++++++++++++++---------------
2 files changed, 56 insertions(+), 30 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/pr97806.c
diff --git a/gcc/testsuite/gcc.dg/pr97806.c b/gcc/testsuite/gcc.dg/pr97806.c
new file mode 100644
index 00000000000..9ec3299c0b1
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr97806.c
@@ -0,0 +1,16 @@
+/* { dg-do compile } */
+/* { dg-options "-O2" } */
+
+int b;
+long c;
+int g();
+void h(long *);
+void i(long *);
+void d() {
+ int e, f = b - e;
+ if (g())
+ h(&c + f);
+ else
+ i(&c + f);
+ __builtin_memset(0, 0, f * 8);
+}
diff --git a/gcc/tree-ssa-pre.c b/gcc/tree-ssa-pre.c
index 10d223bd365..eb181735e7f 100644
--- a/gcc/tree-ssa-pre.c
+++ b/gcc/tree-ssa-pre.c
@@ -805,16 +805,36 @@ bitmap_set_free (bitmap_set_t set)
bitmap_clear (&set->values);
}
+static void
+pre_expr_DFS (pre_expr expr, bitmap_set_t set, bitmap expr_visited,
+ bitmap val_visited, vec<pre_expr> &post);
+
+/* DFS walk leaders of VAL to their operands with leaders in SET, collecting
+ expressions in SET in postorder into POST. */
+
+static void
+pre_expr_DFS (unsigned val, bitmap_set_t set, bitmap expr_visited,
+ bitmap val_visited, vec<pre_expr> &post)
+{
+ unsigned int i;
+ bitmap_iterator bi;
+
+ /* Iterate over all leaders and DFS recurse. Borrowed from
+ bitmap_find_leader. */
+ bitmap exprset = value_expressions[val];
+ EXECUTE_IF_AND_IN_BITMAP (exprset, &set->expressions, 0, i, bi)
+ pre_expr_DFS (expression_for_id (i),
+ set, expr_visited, val_visited, post);
+}
/* DFS walk EXPR to its operands with leaders in SET, collecting
expressions in SET in postorder into POST. */
static void
-pre_expr_DFS (pre_expr expr, bitmap_set_t set, bitmap visited,
- hash_set<int_hash<unsigned int, 0> > &leader_set,
- vec<pre_expr> &post)
+pre_expr_DFS (pre_expr expr, bitmap_set_t set, bitmap expr_visited,
+ bitmap val_visited, vec<pre_expr> &post)
{
- if (!bitmap_set_bit (visited, get_expression_id (expr)))
+ if (!bitmap_set_bit (expr_visited, get_expression_id (expr)))
return;
switch (expr->kind)
@@ -829,12 +849,9 @@ pre_expr_DFS (pre_expr expr, bitmap_set_t set, bitmap visited,
unsigned int op_val_id = VN_INFO (nary->op[i])->value_id;
/* If we already found a leader for the value we've
recursed already. Avoid the costly bitmap_find_leader. */
- if (!leader_set.add (op_val_id))
- {
- pre_expr leader = bitmap_find_leader (set, op_val_id);
- if (leader)
- pre_expr_DFS (leader, set, visited, leader_set, post);
- }
+ if (bitmap_bit_p (&set->values, op_val_id)
+ && bitmap_set_bit (val_visited, op_val_id))
+ pre_expr_DFS (op_val_id, set, expr_visited, val_visited, post);
}
break;
}
@@ -854,12 +871,10 @@ pre_expr_DFS (pre_expr expr, bitmap_set_t set, bitmap visited,
if (!op[n] || TREE_CODE (op[n]) != SSA_NAME)
continue;
unsigned op_val_id = VN_INFO (op[n])->value_id;
- if (!leader_set.add (op_val_id))
- {
- pre_expr leader = bitmap_find_leader (set, op_val_id);
- if (leader)
- pre_expr_DFS (leader, set, visited, leader_set, post);
- }
+ if (bitmap_bit_p (&set->values, op_val_id)
+ && bitmap_set_bit (val_visited, op_val_id))
+ pre_expr_DFS (op_val_id,
+ set, expr_visited, val_visited, post);
}
}
break;
@@ -879,20 +894,15 @@ sorted_array_from_bitmap_set (bitmap_set_t set)
vec<pre_expr> result;
/* Pre-allocate enough space for the array. */
- size_t len = bitmap_count_bits (&set->expressions);
- result.create (len);
- hash_set<int_hash<unsigned int, 0> > leader_set (2*len);
-
- auto_bitmap visited (&grand_bitmap_obstack);
- bitmap_tree_view (visited);
- FOR_EACH_EXPR_ID_IN_SET (set, i, bi)
- {
- pre_expr expr = expression_for_id (i);
- /* Hoist insertion calls us with a value-set we have to and with,
- do so. */
- if (bitmap_set_contains_value (set, get_expr_value_id (expr)))
- pre_expr_DFS (expr, set, visited, leader_set, result);
- }
+ result.create (bitmap_count_bits (&set->expressions));
+
+ auto_bitmap expr_visited (&grand_bitmap_obstack);
+ auto_bitmap val_visited (&grand_bitmap_obstack);
+ bitmap_tree_view (expr_visited);
+ bitmap_tree_view (val_visited);
+ FOR_EACH_VALUE_ID_IN_SET (set, i, bi)
+ if (bitmap_set_bit (val_visited, i))
+ pre_expr_DFS (i, set, expr_visited, val_visited, result);
return result;
}
--
2.26.2
reply other threads:[~2020-11-12 10:00 UTC|newest]
Thread overview: [no followups] expand[flat|nested] mbox.gz Atom feed
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=nycvar.YFH.7.76.2011121100260.9842@elmra.sevgm.obk \
--to=rguenther@suse.de \
--cc=gcc-patches@gcc.gnu.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).