public inbox for gcc-cvs@sourceware.org
help / color / mirror / Atom feed
* [gcc(refs/users/aoliva/heads/testme)] [PR105665] ivopts: check defs of names in base for undefs
@ 2022-05-28 0:09 Alexandre Oliva
0 siblings, 0 replies; 11+ messages in thread
From: Alexandre Oliva @ 2022-05-28 0:09 UTC (permalink / raw)
To: gcc-cvs
https://gcc.gnu.org/g:781277269a6c76123d8ca5b38dbe9ab63a0fd699
commit 781277269a6c76123d8ca5b38dbe9ab63a0fd699
Author: Alexandre Oliva <oliva@adacore.com>
Date: Thu May 26 09:38:31 2022 -0300
[PR105665] ivopts: check defs of names in base for undefs
The patch for PR 100810 tested for undefined SSA_NAMEs appearing
directly in the base expression of the potential IV candidate, but
that's not enough. The testcase for PR105665 shows an undefined
SSA_NAME has the same ill effect if it's referenced as an PHI_NODE arg
in the referenced SSA_NAME. The variant of that test shows it can be
further removed from the referenced SSA_NAME.
Turning the test for undefined SSA_NAMES into a recursive search,
skipping cycles and other duplicates, avoids the problem.
for gcc/ChangeLog
PR tree-optimization/105665
PR tree-optimization/100810
* tree-ssa-loop-ivopts.cc (find_ssa_undef): Take pointer set
as argument, use it to avoid duplicates. Recurse on SSA_NAMEs
mentioned in each def.
(add_candidate_1): Start the search with an empty pointer set.
for gcc/testsuite/ChangeLog
PR tree-optimization/105665
PR tree-optimization/100810
* gcc.dg/torture/pr105665.c: New.
Diff:
---
gcc/testsuite/gcc.dg/torture/pr105665.c | 20 +++++++++++++
gcc/tree-ssa-loop-ivopts.cc | 51 +++++++++++++++++++++++++++++----
2 files changed, 65 insertions(+), 6 deletions(-)
diff --git a/gcc/testsuite/gcc.dg/torture/pr105665.c b/gcc/testsuite/gcc.dg/torture/pr105665.c
new file mode 100644
index 00000000000..34cfc658434
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/torture/pr105665.c
@@ -0,0 +1,20 @@
+/* { dg-do run } */
+
+int a, b, c[1], d[2], *e = c;
+int main() {
+ int f = 0;
+ for (; b < 2; b++) {
+ int g;
+ if (f)
+ g++, b = 40;
+ a = d[b * b];
+ for (f = 0; f < 3; f++) {
+ if (e)
+ break;
+ g--;
+ if (a)
+ a = g;
+ }
+ }
+ return 0;
+}
diff --git a/gcc/tree-ssa-loop-ivopts.cc b/gcc/tree-ssa-loop-ivopts.cc
index 81b536f9304..adf9010ad67 100644
--- a/gcc/tree-ssa-loop-ivopts.cc
+++ b/gcc/tree-ssa-loop-ivopts.cc
@@ -3071,14 +3071,52 @@ get_loop_invariant_expr (struct ivopts_data *data, tree inv_expr)
return *slot;
}
-/* Find the first undefined SSA name in *TP. */
+/* Find the first undefined SSA name in *TP. Use PSET_, a
+ hash_set<tree>*, to avoid cycles and to skip other duplicates. */
static tree
-find_ssa_undef (tree *tp, int *walk_subtrees, void *)
+find_ssa_undef (tree *tp, int *walk_subtrees, void *pset_)
{
- if (TREE_CODE (*tp) == SSA_NAME
- && ssa_undefined_value_p (*tp, false))
- return *tp;
+ auto pset = static_cast<hash_set<tree> *> (pset_);
+
+ if (TREE_CODE (*tp) == SSA_NAME)
+ {
+ if (ssa_defined_default_def_p (*tp))
+ return NULL;
+
+ if (ssa_undefined_value_p (*tp, false))
+ return *tp;
+
+ /* If we've already visited this SSA_NAME and got to it again,
+ we know we didn't find it to be undefined, otherwise we'd
+ have stopped the walk then. */
+ if (pset && pset->add (*tp))
+ return NULL;
+
+ gimple *def_stmt = SSA_NAME_DEF_STMT (*tp);
+ /* ssa_undefined_value_p must have caught nop defs above. */
+ gcc_checking_assert (!gimple_nop_p (def_stmt));
+
+ /* No need to follow these: uses' undefinedness does not
+ propagate to defs. ??? Even inlined calls? */
+ if (is_gimple_call (def_stmt)
+ || is_a <gasm *> (def_stmt))
+ return NULL;
+
+ ssa_op_iter iter;
+ use_operand_p use_p;
+
+ FOR_EACH_PHI_OR_STMT_USE (use_p, def_stmt, iter, SSA_OP_USE)
+ {
+ tree use = USE_FROM_PTR (use_p);
+
+ int wsub = 1;
+ tree result = find_ssa_undef (&use, &wsub, pset);
+ if (result)
+ return result;
+ }
+ }
+
if (!EXPR_P (*tp))
*walk_subtrees = 0;
return NULL;
@@ -3114,7 +3152,8 @@ add_candidate_1 (struct ivopts_data *data, tree base, tree step, bool important,
/* If BASE contains undefined SSA names make sure we only record
the original IV. */
bool involves_undefs = false;
- if (walk_tree (&base, find_ssa_undef, NULL, NULL))
+ hash_set<tree> pset;
+ if (walk_tree (&base, find_ssa_undef, &pset, NULL))
{
if (pos != IP_ORIGINAL)
return NULL;
^ permalink raw reply [flat|nested] 11+ messages in thread
* [gcc(refs/users/aoliva/heads/testme)] [PR105665] ivopts: check defs of names in base for undefs
@ 2022-06-02 11:58 Alexandre Oliva
0 siblings, 0 replies; 11+ messages in thread
From: Alexandre Oliva @ 2022-06-02 11:58 UTC (permalink / raw)
To: gcc-cvs
https://gcc.gnu.org/g:58da319e5e66673ffcb77eecfc8e8a0f2f78ed60
commit 58da319e5e66673ffcb77eecfc8e8a0f2f78ed60
Author: Alexandre Oliva <oliva@adacore.com>
Date: Wed Jun 1 19:32:38 2022 -0300
[PR105665] ivopts: check defs of names in base for undefs
The patch for PR 100810 tested for undefined SSA_NAMEs appearing
directly in the base expression of the potential IV candidate, but
that's not enough. The testcase for PR105665 shows an undefined
SSA_NAME has the same ill effect if it's referenced as an PHI_NODE arg
in the referenced SSA_NAME. The variant of that test shows it can be
further removed from the referenced SSA_NAME.
To avoid deep recursion, precompute maybe-undefined SSA_NAMEs: start
from known-undefined nonvirtual default defs, and propagate them to
any PHI nodes reached by a maybe-undefined arg, as long as there
aren't intervening non-PHI uses, that would imply the maybe-undefined
name must be defined at that point, otherwise it would invoke
undefined behavior. Also test for intervening non-PHI uses of DEFs in
the base expr.
The test for intervening uses implemented herein relies on dominance;
this could be further extended, regarding conditional uses in every
path leading to a point as an unconditional use dominating that point,
but I haven't implemented that.
for gcc/ChangeLog
PR tree-optimization/105665
PR tree-optimization/100810
* tree-ssa-loop-ivopts.cc
(ssa_name_maybe_undef_p, ssa_name_set_maybe_undef): New.
(ssa_name_any_use_dominates_bb_p, mark_ssa_maybe_undefs): New.
(find_ssa_undef): Check precomputed flag and intervening uses.
(tree_ssa_iv_optimize): Call mark_ssa_maybe_undefs.
for gcc/testsuite/ChangeLog
PR tree-optimization/105665
PR tree-optimization/100810
* gcc.dg/torture/pr105665.c: New.
Diff:
---
gcc/testsuite/gcc.dg/torture/pr105665.c | 20 +++++
gcc/tree-ssa-loop-ivopts.cc | 125 +++++++++++++++++++++++++++++++-
2 files changed, 141 insertions(+), 4 deletions(-)
diff --git a/gcc/testsuite/gcc.dg/torture/pr105665.c b/gcc/testsuite/gcc.dg/torture/pr105665.c
new file mode 100644
index 00000000000..34cfc658434
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/torture/pr105665.c
@@ -0,0 +1,20 @@
+/* { dg-do run } */
+
+int a, b, c[1], d[2], *e = c;
+int main() {
+ int f = 0;
+ for (; b < 2; b++) {
+ int g;
+ if (f)
+ g++, b = 40;
+ a = d[b * b];
+ for (f = 0; f < 3; f++) {
+ if (e)
+ break;
+ g--;
+ if (a)
+ a = g;
+ }
+ }
+ return 0;
+}
diff --git a/gcc/tree-ssa-loop-ivopts.cc b/gcc/tree-ssa-loop-ivopts.cc
index 81b536f9304..549168aebd6 100644
--- a/gcc/tree-ssa-loop-ivopts.cc
+++ b/gcc/tree-ssa-loop-ivopts.cc
@@ -3071,13 +3071,129 @@ get_loop_invariant_expr (struct ivopts_data *data, tree inv_expr)
return *slot;
}
-/* Find the first undefined SSA name in *TP. */
+/* Return TRUE iff VAR is marked as maybe-undefined. See
+ mark_ssa_maybe_undefs. */
+
+static inline bool
+ssa_name_maybe_undef_p (tree var)
+{
+ gcc_checking_assert (TREE_CODE (var) == SSA_NAME);
+ return TREE_VISITED (var);
+}
+
+/* Set (or clear, depending on VALUE) VAR's maybe-undefined mark. */
+
+static inline void
+ssa_name_set_maybe_undef (tree var, bool value = true)
+{
+ gcc_checking_assert (TREE_CODE (var) == SSA_NAME);
+ TREE_VISITED (var) = value;
+}
+
+/* Return TRUE iff there are any non-PHI uses of VAR that dominate the
+ end of BB. If we return TRUE and BB is a loop header, then VAR we
+ be assumed to be defined within the loop, even if it is marked as
+ maybe-undefined. */
+
+static inline bool
+ssa_name_any_use_dominates_bb_p (tree var, basic_block bb)
+{
+ imm_use_iterator iter;
+ use_operand_p use_p;
+ FOR_EACH_IMM_USE_FAST (use_p, iter, var)
+ {
+ if (is_a <gphi *> (USE_STMT (use_p))
+ || is_gimple_debug (USE_STMT (use_p)))
+ continue;
+ basic_block dombb = gimple_bb (USE_STMT (use_p));
+ if (dominated_by_p (CDI_DOMINATORS, bb, dombb))
+ return true;
+ }
+
+ return false;
+}
+
+/* Mark as maybe_undef any SSA_NAMEs that are unsuitable as ivopts
+ candidates for potentially involving undefined behavior. */
+
+static void
+mark_ssa_maybe_undefs (void)
+{
+ auto_vec<tree> queue;
+
+ /* Scan all SSA_NAMEs, marking the definitely-undefined ones as
+ maybe-undefined and queuing them for propagation, while clearing
+ the mark on others. */
+ unsigned int i;
+ tree var;
+ FOR_EACH_SSA_NAME (i, var, cfun)
+ {
+ if (SSA_NAME_IS_VIRTUAL_OPERAND (var)
+ || !ssa_undefined_value_p (var, false))
+ ssa_name_set_maybe_undef (var, false);
+ else
+ {
+ ssa_name_set_maybe_undef (var);
+ queue.safe_push (var);
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "marking _%i as maybe-undef\n",
+ SSA_NAME_VERSION (var));
+ }
+ }
+
+ /* Now propagate maybe-undefined from a DEF to any other PHI that
+ uses it, as long as there isn't any intervening use of DEF. */
+ while (!queue.is_empty ())
+ {
+ var = queue.pop ();
+ imm_use_iterator iter;
+ use_operand_p use_p;
+ FOR_EACH_IMM_USE_FAST (use_p, iter, var)
+ {
+ /* Any uses of VAR that aren't PHI args imply VAR must be
+ defined, otherwise undefined behavior would have been
+ definitely invoked. Only PHI args may hold
+ maybe-undefined values without invoking undefined
+ behavior for that reason alone. */
+ if (!is_a <gphi *> (USE_STMT (use_p)))
+ continue;
+ gphi *phi = as_a <gphi *> (USE_STMT (use_p));
+
+ tree def = gimple_phi_result (phi);
+ if (ssa_name_maybe_undef_p (def))
+ continue;
+
+ /* Look for any uses of the maybe-unused SSA_NAME that
+ dominates the block that reaches the incoming block
+ corresponding to the PHI arg in which it is mentioned.
+ That means we can assume the SSA_NAME is defined in that
+ path, so we only mark a PHI result as maybe-undef if we
+ find an unused reaching SSA_NAME. */
+ int idx = phi_arg_index_from_use (use_p);
+ basic_block bb = gimple_phi_arg_edge (phi, idx)->src;
+ if (ssa_name_any_use_dominates_bb_p (var, bb))
+ continue;
+
+ ssa_name_set_maybe_undef (def);
+ queue.safe_push (def);
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "marking _%i as maybe-undef because of _%i\n",
+ SSA_NAME_VERSION (def), SSA_NAME_VERSION (var));
+ }
+ }
+}
+
+/* Return *TP if it is an SSA_NAME marked with TREE_VISITED, i.e., as
+ unsuitable as ivopts candidates for potentially involving undefined
+ behavior. */
static tree
-find_ssa_undef (tree *tp, int *walk_subtrees, void *)
+find_ssa_undef (tree *tp, int *walk_subtrees, void *bb_)
{
+ basic_block bb = (basic_block) bb_;
if (TREE_CODE (*tp) == SSA_NAME
- && ssa_undefined_value_p (*tp, false))
+ && ssa_name_maybe_undef_p (*tp)
+ && !ssa_name_any_use_dominates_bb_p (*tp, bb))
return *tp;
if (!EXPR_P (*tp))
*walk_subtrees = 0;
@@ -3114,7 +3230,7 @@ add_candidate_1 (struct ivopts_data *data, tree base, tree step, bool important,
/* If BASE contains undefined SSA names make sure we only record
the original IV. */
bool involves_undefs = false;
- if (walk_tree (&base, find_ssa_undef, NULL, NULL))
+ if (walk_tree (&base, find_ssa_undef, data->current_loop->header, NULL))
{
if (pos != IP_ORIGINAL)
return NULL;
@@ -8192,6 +8308,7 @@ tree_ssa_iv_optimize (void)
auto_bitmap toremove;
tree_ssa_iv_optimize_init (&data);
+ mark_ssa_maybe_undefs ();
/* Optimize the loops starting with the innermost ones. */
for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
^ permalink raw reply [flat|nested] 11+ messages in thread
* [gcc(refs/users/aoliva/heads/testme)] [PR105665] ivopts: check defs of names in base for undefs
@ 2022-06-02 1:27 Alexandre Oliva
0 siblings, 0 replies; 11+ messages in thread
From: Alexandre Oliva @ 2022-06-02 1:27 UTC (permalink / raw)
To: gcc-cvs
https://gcc.gnu.org/g:2f1dfd38f0d9a7acb9c14dfbb32145822294bb53
commit 2f1dfd38f0d9a7acb9c14dfbb32145822294bb53
Author: Alexandre Oliva <oliva@adacore.com>
Date: Wed Jun 1 19:32:38 2022 -0300
[PR105665] ivopts: check defs of names in base for undefs
The patch for PR 100810 tested for undefined SSA_NAMEs appearing
directly in the base expression of the potential IV candidate, but
that's not enough. The testcase for PR105665 shows an undefined
SSA_NAME has the same ill effect if it's referenced as an PHI_NODE arg
in the referenced SSA_NAME. The variant of that test shows it can be
further removed from the referenced SSA_NAME.
To avoid deep recursion, precompute maybe-undefined SSA_NAMEs: start
from known-undefined nonvirtual default defs, and propagate them to
any PHI nodes reached by a maybe-undefined arg, as long as there
aren't intervening non-PHI uses, that would imply the maybe-undefined
name must be defined at that point, otherwise it would invoke
undefined behavior. Also test for intervening non-PHI uses of DEFs in
the base expr.
The test for intervening uses implemented herein relies on dominance;
this could be further extended, regarding conditional uses in every
path leading to a point as an unconditional use dominating that point,
but I haven't implemented that.
for gcc/ChangeLog
PR tree-optimization/105665
PR tree-optimization/100810
* tree-ssa-loop-ivopts.cc
(ssa_name_maybe_undef_p, ssa_name_set_maybe_undef): New.
(ssa_name_any_use_dominates_bb_p, mark_ssa_maybe_undefs): New.
(find_ssa_undef): Check precomputed flag and intervening uses.
(tree_ssa_iv_optimize): Call mark_ssa_maybe_undefs.
for gcc/testsuite/ChangeLog
PR tree-optimization/105665
PR tree-optimization/100810
* gcc.dg/torture/pr105665.c: New.
Diff:
---
gcc/testsuite/gcc.dg/torture/pr105665.c | 20 ++++++
gcc/tree-ssa-loop-ivopts.cc | 124 ++++++++++++++++++++++++++++++--
2 files changed, 140 insertions(+), 4 deletions(-)
diff --git a/gcc/testsuite/gcc.dg/torture/pr105665.c b/gcc/testsuite/gcc.dg/torture/pr105665.c
new file mode 100644
index 00000000000..34cfc658434
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/torture/pr105665.c
@@ -0,0 +1,20 @@
+/* { dg-do run } */
+
+int a, b, c[1], d[2], *e = c;
+int main() {
+ int f = 0;
+ for (; b < 2; b++) {
+ int g;
+ if (f)
+ g++, b = 40;
+ a = d[b * b];
+ for (f = 0; f < 3; f++) {
+ if (e)
+ break;
+ g--;
+ if (a)
+ a = g;
+ }
+ }
+ return 0;
+}
diff --git a/gcc/tree-ssa-loop-ivopts.cc b/gcc/tree-ssa-loop-ivopts.cc
index 81b536f9304..f20a985d7ca 100644
--- a/gcc/tree-ssa-loop-ivopts.cc
+++ b/gcc/tree-ssa-loop-ivopts.cc
@@ -3071,13 +3071,128 @@ get_loop_invariant_expr (struct ivopts_data *data, tree inv_expr)
return *slot;
}
-/* Find the first undefined SSA name in *TP. */
+/* Return TRUE iff VAR is marked as maybe-undefined. See
+ mark_ssa_maybe_undefs. */
+
+static inline bool
+ssa_name_maybe_undef_p (tree var)
+{
+ gcc_checking_assert (TREE_CODE (var) == SSA_NAME);
+ return TREE_VISITED (var);
+}
+
+/* Set (or clear, depending on VALUE) VAR's maybe-undefined mark. */
+
+static inline void
+ssa_name_set_maybe_undef (tree var, bool value = true)
+{
+ gcc_checking_assert (TREE_CODE (var) == SSA_NAME);
+ TREE_VISITED (var) = value;
+}
+
+/* Return TRUE iff there are any non-PHI uses of VAR that dominate the
+ end of BB. If we return TRUE and BB is a loop header, then VAR we
+ be assumed to be defined within the loop, even if it is marked as
+ maybe-undefined. */
+
+static inline bool
+ssa_name_any_use_dominates_bb_p (tree var, basic_block bb)
+{
+ imm_use_iterator iter;
+ use_operand_p use_p;
+ FOR_EACH_IMM_USE_FAST (use_p, iter, var)
+ {
+ if (is_a <gphi *> (USE_STMT (use_p)))
+ continue;
+ basic_block dombb = gimple_bb (USE_STMT (use_p));
+ if (dominated_by_p (CDI_DOMINATORS, bb, dombb))
+ return true;
+ }
+
+ return false;
+}
+
+/* Mark as maybe_undef any SSA_NAMEs that are unsuitable as ivopts
+ candidates for potentially involving undefined behavior. */
+
+static void
+mark_ssa_maybe_undefs (void)
+{
+ auto_vec<tree> queue;
+
+ /* Scan all SSA_NAMEs, marking the definitely-undefined ones as
+ maybe-undefined and queuing them for propagation, while clearing
+ the mark on others. */
+ unsigned int i;
+ tree var;
+ FOR_EACH_SSA_NAME (i, var, cfun)
+ {
+ if (SSA_NAME_IS_VIRTUAL_OPERAND (var)
+ || !ssa_undefined_value_p (var, false))
+ ssa_name_set_maybe_undef (var, false);
+ else
+ {
+ ssa_name_set_maybe_undef (var);
+ queue.safe_push (var);
+ if (dump_file)
+ fprintf (dump_file, "marking _%i as maybe-undef\n",
+ SSA_NAME_VERSION (var));
+ }
+ }
+
+ /* Now propagate maybe-undefined from a DEF to any other PHI that
+ uses it, as long as there isn't any intervening use of DEF. */
+ while (!queue.is_empty ())
+ {
+ var = queue.pop ();
+ imm_use_iterator iter;
+ use_operand_p use_p;
+ FOR_EACH_IMM_USE_FAST (use_p, iter, var)
+ {
+ /* Any uses of VAR that aren't PHI args imply VAR must be
+ defined, otherwise undefined behavior would have been
+ definitely invoked. Only PHI args may hold
+ maybe-undefined values without invoking undefined
+ behavior for that reason alone. */
+ if (!is_a <gphi *> (USE_STMT (use_p)))
+ continue;
+ gphi *phi = as_a <gphi *> (USE_STMT (use_p));
+
+ tree def = gimple_phi_result (phi);
+ if (ssa_name_maybe_undef_p (def))
+ continue;
+
+ /* Look for any uses of the maybe-unused SSA_NAME that
+ dominates the block that reaches the incoming block
+ corresponding to the PHI arg in which it is mentioned.
+ That means we can assume the SSA_NAME is defined in that
+ path, so we only mark a PHI result as maybe-undef if we
+ find an unused reaching SSA_NAME. */
+ int idx = phi_arg_index_from_use (use_p);
+ basic_block bb = gimple_phi_arg_edge (phi, idx)->src;
+ if (ssa_name_any_use_dominates_bb_p (var, bb))
+ continue;
+
+ ssa_name_set_maybe_undef (def);
+ queue.safe_push (def);
+ if (dump_file)
+ fprintf (dump_file, "marking _%i as maybe-undef because of _%i\n",
+ SSA_NAME_VERSION (def), SSA_NAME_VERSION (var));
+ }
+ }
+}
+
+/* Return *TP if it is an SSA_NAME marked with TREE_VISITED, i.e., as
+ unsuitable as ivopts candidates for potentially involving undefined
+ behavior. */
static tree
-find_ssa_undef (tree *tp, int *walk_subtrees, void *)
+find_ssa_undef (tree *tp, int *walk_subtrees, void *bb_)
{
+ basic_block bb = (basic_block) bb_;
if (TREE_CODE (*tp) == SSA_NAME
- && ssa_undefined_value_p (*tp, false))
+ && ssa_name_maybe_undef_p (*tp)
+ && !ssa_name_any_use_dominates_bb_p (*tp, bb))
return *tp;
if (!EXPR_P (*tp))
*walk_subtrees = 0;
@@ -3114,7 +3229,7 @@ add_candidate_1 (struct ivopts_data *data, tree base, tree step, bool important,
/* If BASE contains undefined SSA names make sure we only record
the original IV. */
bool involves_undefs = false;
- if (walk_tree (&base, find_ssa_undef, NULL, NULL))
+ if (walk_tree (&base, find_ssa_undef, data->current_loop->header, NULL))
{
if (pos != IP_ORIGINAL)
return NULL;
@@ -8192,6 +8307,7 @@ tree_ssa_iv_optimize (void)
auto_bitmap toremove;
tree_ssa_iv_optimize_init (&data);
+ mark_ssa_maybe_undefs ();
/* Optimize the loops starting with the innermost ones. */
for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
^ permalink raw reply [flat|nested] 11+ messages in thread
* [gcc(refs/users/aoliva/heads/testme)] [PR105665] ivopts: check defs of names in base for undefs
@ 2022-05-28 4:45 Alexandre Oliva
0 siblings, 0 replies; 11+ messages in thread
From: Alexandre Oliva @ 2022-05-28 4:45 UTC (permalink / raw)
To: gcc-cvs
https://gcc.gnu.org/g:0f6179f2b85698b94e5a494920f0b282f414ea46
commit 0f6179f2b85698b94e5a494920f0b282f414ea46
Author: Alexandre Oliva <oliva@adacore.com>
Date: Thu May 26 09:38:31 2022 -0300
[PR105665] ivopts: check defs of names in base for undefs
The patch for PR 100810 tested for undefined SSA_NAMEs appearing
directly in the base expression of the potential IV candidate, but
that's not enough. The testcase for PR105665 shows an undefined
SSA_NAME has the same ill effect if it's referenced as an PHI_NODE arg
in the referenced SSA_NAME. The variant of that test shows it can be
further removed from the referenced SSA_NAME.
To avoid deep recursion, precompute SSA_NAMEs deemed unsuitable
candidates, so that we can skip them with a flag test.
for gcc/ChangeLog
PR tree-optimization/105665
PR tree-optimization/100810
* tree-ssa-loop-ivopts.cc (mark_ssa_undefs): Precompute
unsuitability of SSA_NAMEs in TREE_VISITED.
(find_ssa_undef): Check the precomputed flag.
(tree_ssa_iv_optimize): Call mark_ssa_undefs.
for gcc/testsuite/ChangeLog
PR tree-optimization/105665
PR tree-optimization/100810
* gcc.dg/torture/pr105665.c: New.
Diff:
---
gcc/testsuite/gcc.dg/torture/pr105665.c | 20 +++++++++++
gcc/tree-ssa-loop-ivopts.cc | 61 +++++++++++++++++++++++++++++++--
2 files changed, 79 insertions(+), 2 deletions(-)
diff --git a/gcc/testsuite/gcc.dg/torture/pr105665.c b/gcc/testsuite/gcc.dg/torture/pr105665.c
new file mode 100644
index 00000000000..34cfc658434
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/torture/pr105665.c
@@ -0,0 +1,20 @@
+/* { dg-do run } */
+
+int a, b, c[1], d[2], *e = c;
+int main() {
+ int f = 0;
+ for (; b < 2; b++) {
+ int g;
+ if (f)
+ g++, b = 40;
+ a = d[b * b];
+ for (f = 0; f < 3; f++) {
+ if (e)
+ break;
+ g--;
+ if (a)
+ a = g;
+ }
+ }
+ return 0;
+}
diff --git a/gcc/tree-ssa-loop-ivopts.cc b/gcc/tree-ssa-loop-ivopts.cc
index 81b536f9304..af508818522 100644
--- a/gcc/tree-ssa-loop-ivopts.cc
+++ b/gcc/tree-ssa-loop-ivopts.cc
@@ -3071,13 +3071,69 @@ get_loop_invariant_expr (struct ivopts_data *data, tree inv_expr)
return *slot;
}
-/* Find the first undefined SSA name in *TP. */
+/* Mark as TREE_VISITED any SSA_NAMEs that are unsuitable as ivopts
+ candidates for potentially involving undefined behavior. */
+
+static void
+mark_ssa_undefs (void)
+{
+ auto_vec<tree> queue;
+
+ unsigned int i;
+ tree var;
+ FOR_EACH_SSA_NAME (i, var, cfun)
+ {
+ if (SSA_NAME_IS_VIRTUAL_OPERAND (var)
+ || !ssa_undefined_value_p (var, false))
+ TREE_VISITED (var) = false;
+ else
+ {
+ TREE_VISITED (var) = true;
+ queue.safe_push (var);
+ if (dump_file)
+ fprintf (dump_file, "marking _%i as undef\n",
+ SSA_NAME_VERSION (var));
+ }
+ }
+
+ while (!queue.is_empty ())
+ {
+ var = queue.pop ();
+ gimple *stmt;
+ imm_use_iterator iter;
+ FOR_EACH_IMM_USE_STMT (stmt, iter, var)
+ {
+ if (is_gimple_call (stmt) || is_a <gasm *> (stmt))
+ continue;
+
+ def_operand_p defvar;
+ ssa_op_iter diter;
+ FOR_EACH_PHI_OR_STMT_DEF (defvar, stmt, diter, SSA_OP_DEF)
+ {
+ gcc_checking_assert (is_gimple_assign (stmt)
+ || is_a <gphi *> (stmt));
+ tree def = DEF_FROM_PTR (defvar);
+ if (TREE_VISITED (def))
+ continue;
+ TREE_VISITED (def) = true;
+ queue.safe_push (def);
+ if (dump_file)
+ fprintf (dump_file, "Marking _%i as undef because of _%i\n",
+ SSA_NAME_VERSION (def), SSA_NAME_VERSION (var));
+ }
+ }
+ }
+}
+
+/* Return *TP if it is an SSA_NAME marked with TREE_VISITED, i.e., as
+ unsuitable as ivopts candidates for potentially involving undefined
+ behavior. */
static tree
find_ssa_undef (tree *tp, int *walk_subtrees, void *)
{
if (TREE_CODE (*tp) == SSA_NAME
- && ssa_undefined_value_p (*tp, false))
+ && TREE_VISITED (*tp))
return *tp;
if (!EXPR_P (*tp))
*walk_subtrees = 0;
@@ -8192,6 +8248,7 @@ tree_ssa_iv_optimize (void)
auto_bitmap toremove;
tree_ssa_iv_optimize_init (&data);
+ mark_ssa_undefs ();
/* Optimize the loops starting with the innermost ones. */
for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
^ permalink raw reply [flat|nested] 11+ messages in thread
* [gcc(refs/users/aoliva/heads/testme)] [PR105665] ivopts: check defs of names in base for undefs
@ 2022-05-28 0:11 Alexandre Oliva
0 siblings, 0 replies; 11+ messages in thread
From: Alexandre Oliva @ 2022-05-28 0:11 UTC (permalink / raw)
To: gcc-cvs
https://gcc.gnu.org/g:7ed250b1b302b05171cd5d670cb326f27d89bef0
commit 7ed250b1b302b05171cd5d670cb326f27d89bef0
Author: Alexandre Oliva <oliva@adacore.com>
Date: Thu May 26 09:38:31 2022 -0300
[PR105665] ivopts: check defs of names in base for undefs
The patch for PR 100810 tested for undefined SSA_NAMEs appearing
directly in the base expression of the potential IV candidate, but
that's not enough. The testcase for PR105665 shows an undefined
SSA_NAME has the same ill effect if it's referenced as an PHI_NODE arg
in the referenced SSA_NAME. The variant of that test shows it can be
further removed from the referenced SSA_NAME.
Turning the test for undefined SSA_NAMES into a recursive search,
skipping cycles and other duplicates, avoids the problem.
for gcc/ChangeLog
PR tree-optimization/105665
PR tree-optimization/100810
* tree-ssa-loop-ivopts.cc (find_ssa_undef): Take pointer set
as argument, use it to avoid duplicates. Recurse on SSA_NAMEs
mentioned in each def.
(add_candidate_1): Start the search with an empty pointer set.
for gcc/testsuite/ChangeLog
PR tree-optimization/105665
PR tree-optimization/100810
* gcc.dg/torture/pr105665.c: New.
Diff:
---
gcc/testsuite/gcc.dg/torture/pr105665.c | 20 +++++++++++++
gcc/tree-ssa-loop-ivopts.cc | 52 +++++++++++++++++++++++++++++----
2 files changed, 66 insertions(+), 6 deletions(-)
diff --git a/gcc/testsuite/gcc.dg/torture/pr105665.c b/gcc/testsuite/gcc.dg/torture/pr105665.c
new file mode 100644
index 00000000000..34cfc658434
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/torture/pr105665.c
@@ -0,0 +1,20 @@
+/* { dg-do run } */
+
+int a, b, c[1], d[2], *e = c;
+int main() {
+ int f = 0;
+ for (; b < 2; b++) {
+ int g;
+ if (f)
+ g++, b = 40;
+ a = d[b * b];
+ for (f = 0; f < 3; f++) {
+ if (e)
+ break;
+ g--;
+ if (a)
+ a = g;
+ }
+ }
+ return 0;
+}
diff --git a/gcc/tree-ssa-loop-ivopts.cc b/gcc/tree-ssa-loop-ivopts.cc
index 81b536f9304..8902702cbbb 100644
--- a/gcc/tree-ssa-loop-ivopts.cc
+++ b/gcc/tree-ssa-loop-ivopts.cc
@@ -3071,14 +3071,53 @@ get_loop_invariant_expr (struct ivopts_data *data, tree inv_expr)
return *slot;
}
-/* Find the first undefined SSA name in *TP. */
+/* Find the first undefined SSA name in *TP. Use PSET_, a
+ hash_set<tree>*, to avoid cycles and to skip other duplicates. */
static tree
-find_ssa_undef (tree *tp, int *walk_subtrees, void *)
+find_ssa_undef (tree *tp, int *walk_subtrees, void *pset_)
{
- if (TREE_CODE (*tp) == SSA_NAME
- && ssa_undefined_value_p (*tp, false))
- return *tp;
+ auto pset = static_cast<hash_set<tree> *> (pset_);
+
+ if (TREE_CODE (*tp) == SSA_NAME)
+ {
+ if (ssa_defined_default_def_p (*tp))
+ return NULL;
+
+ if (ssa_undefined_value_p (*tp, false))
+ return *tp;
+
+ /* If we've already visited this SSA_NAME and got to it again,
+ we know we didn't find it to be undefined, otherwise we'd
+ have stopped the walk then. */
+ if (pset && pset->add (*tp))
+ return NULL;
+
+ gimple *def_stmt = SSA_NAME_DEF_STMT (*tp);
+ /* ssa_undefined_value_p must have caught nop defs above. */
+ gcc_checking_assert (!gimple_nop_p (def_stmt));
+
+ /* No need to follow these: uses' undefinedness does not
+ propagate to defs. ??? Even inlined calls? */
+ if (is_gimple_call (def_stmt) || is_a <gasm *> (def_stmt))
+ return NULL;
+ gcc_checking_assert (is_gimple_assign (def_stmt)
+ || is_a <gphi *> (def_stmt));
+
+ ssa_op_iter iter;
+ use_operand_p use_p;
+
+ FOR_EACH_PHI_OR_STMT_USE (use_p, def_stmt, iter, SSA_OP_USE)
+ {
+ tree use = USE_FROM_PTR (use_p);
+
+ int wsub = 1;
+ tree result = find_ssa_undef (&use, &wsub, pset);
+ if (result)
+ return result;
+ }
+ }
+
if (!EXPR_P (*tp))
*walk_subtrees = 0;
return NULL;
@@ -3114,7 +3153,8 @@ add_candidate_1 (struct ivopts_data *data, tree base, tree step, bool important,
/* If BASE contains undefined SSA names make sure we only record
the original IV. */
bool involves_undefs = false;
- if (walk_tree (&base, find_ssa_undef, NULL, NULL))
+ hash_set<tree> pset;
+ if (walk_tree (&base, find_ssa_undef, &pset, NULL))
{
if (pos != IP_ORIGINAL)
return NULL;
^ permalink raw reply [flat|nested] 11+ messages in thread
* [gcc(refs/users/aoliva/heads/testme)] [PR105665] ivopts: check defs of names in base for undefs
@ 2022-05-26 15:46 Alexandre Oliva
0 siblings, 0 replies; 11+ messages in thread
From: Alexandre Oliva @ 2022-05-26 15:46 UTC (permalink / raw)
To: gcc-cvs
https://gcc.gnu.org/g:8b85376e8c4279e620d7c9793776b42b9575b9ff
commit 8b85376e8c4279e620d7c9793776b42b9575b9ff
Author: Alexandre Oliva <oliva@adacore.com>
Date: Thu May 26 09:15:53 2022 -0300
[PR105665] ivopts: check defs of names in base for undefs
Diff:
---
gcc/testsuite/gcc.dg/torture/pr105665.c | 2 +-
gcc/tree-ssa-loop-ivopts.cc | 22 ++++++++++++++++++----
2 files changed, 19 insertions(+), 5 deletions(-)
diff --git a/gcc/testsuite/gcc.dg/torture/pr105665.c b/gcc/testsuite/gcc.dg/torture/pr105665.c
index 12f0b78a4b4..34cfc658434 100644
--- a/gcc/testsuite/gcc.dg/torture/pr105665.c
+++ b/gcc/testsuite/gcc.dg/torture/pr105665.c
@@ -6,7 +6,7 @@ int main() {
for (; b < 2; b++) {
int g;
if (f)
- b = 40;
+ g++, b = 40;
a = d[b * b];
for (f = 0; f < 3; f++) {
if (e)
diff --git a/gcc/tree-ssa-loop-ivopts.cc b/gcc/tree-ssa-loop-ivopts.cc
index 5b1c7340f77..654a0432ef4 100644
--- a/gcc/tree-ssa-loop-ivopts.cc
+++ b/gcc/tree-ssa-loop-ivopts.cc
@@ -3074,13 +3074,24 @@ get_loop_invariant_expr (struct ivopts_data *data, tree inv_expr)
/* Find the first undefined SSA name in *TP. */
static tree
-find_ssa_undef (tree *tp, int *walk_subtrees, void *)
+find_ssa_undef (tree *tp, int *walk_subtrees, void *pset_)
{
+ auto pset = static_cast<hash_set<tree> *> (pset_);
+
if (TREE_CODE (*tp) == SSA_NAME)
{
+ if (ssa_defined_default_def_p (*tp))
+ return NULL;
+
if (ssa_undefined_value_p (*tp, false))
return *tp;
+ /* If we've already visited this SSA_NAME and got to it again,
+ we know we didn't find it to be undefined, otherwise we'd
+ have stopped the walk then. */
+ if (pset && pset->add (*tp))
+ return NULL;
+
gimple *def_stmt = SSA_NAME_DEF_STMT (*tp);
/* ssa_undefined_value_p must have caught nop defs above. */
gcc_checking_assert (!gimple_nop_p (def_stmt));
@@ -3092,8 +3103,10 @@ find_ssa_undef (tree *tp, int *walk_subtrees, void *)
{
tree use = USE_FROM_PTR (use_p);
- if (ssa_undefined_value_p (use, false))
- return use;
+ int wsub = 1;
+ tree result = find_ssa_undef (&use, &wsub, pset);
+ if (result)
+ return result;
}
}
@@ -3132,7 +3145,8 @@ add_candidate_1 (struct ivopts_data *data, tree base, tree step, bool important,
/* If BASE contains undefined SSA names make sure we only record
the original IV. */
bool involves_undefs = false;
- if (walk_tree (&base, find_ssa_undef, NULL, NULL))
+ hash_set<tree> pset;
+ if (walk_tree (&base, find_ssa_undef, &pset, NULL))
{
if (pos != IP_ORIGINAL)
return NULL;
^ permalink raw reply [flat|nested] 11+ messages in thread
* [gcc(refs/users/aoliva/heads/testme)] [PR105665] ivopts: check defs of names in base for undefs
@ 2022-05-26 15:46 Alexandre Oliva
0 siblings, 0 replies; 11+ messages in thread
From: Alexandre Oliva @ 2022-05-26 15:46 UTC (permalink / raw)
To: gcc-cvs
https://gcc.gnu.org/g:e90f0f0296d12932b2ec3660b296328c11f73cb3
commit e90f0f0296d12932b2ec3660b296328c11f73cb3
Author: Alexandre Oliva <oliva@adacore.com>
Date: Thu May 26 09:38:31 2022 -0300
[PR105665] ivopts: check defs of names in base for undefs
Diff:
---
gcc/testsuite/gcc.dg/torture/pr105665.c | 20 ++++++++++++++++++++
gcc/tree-ssa-loop-ivopts.cc | 24 +++++++++++++++++++++---
2 files changed, 41 insertions(+), 3 deletions(-)
diff --git a/gcc/testsuite/gcc.dg/torture/pr105665.c b/gcc/testsuite/gcc.dg/torture/pr105665.c
new file mode 100644
index 00000000000..12f0b78a4b4
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/torture/pr105665.c
@@ -0,0 +1,20 @@
+/* { dg-do run } */
+
+int a, b, c[1], d[2], *e = c;
+int main() {
+ int f = 0;
+ for (; b < 2; b++) {
+ int g;
+ if (f)
+ b = 40;
+ a = d[b * b];
+ for (f = 0; f < 3; f++) {
+ if (e)
+ break;
+ g--;
+ if (a)
+ a = g;
+ }
+ }
+ return 0;
+}
diff --git a/gcc/tree-ssa-loop-ivopts.cc b/gcc/tree-ssa-loop-ivopts.cc
index 81b536f9304..5b1c7340f77 100644
--- a/gcc/tree-ssa-loop-ivopts.cc
+++ b/gcc/tree-ssa-loop-ivopts.cc
@@ -3076,9 +3076,27 @@ get_loop_invariant_expr (struct ivopts_data *data, tree inv_expr)
static tree
find_ssa_undef (tree *tp, int *walk_subtrees, void *)
{
- if (TREE_CODE (*tp) == SSA_NAME
- && ssa_undefined_value_p (*tp, false))
- return *tp;
+ if (TREE_CODE (*tp) == SSA_NAME)
+ {
+ if (ssa_undefined_value_p (*tp, false))
+ return *tp;
+
+ gimple *def_stmt = SSA_NAME_DEF_STMT (*tp);
+ /* ssa_undefined_value_p must have caught nop defs above. */
+ gcc_checking_assert (!gimple_nop_p (def_stmt));
+
+ ssa_op_iter iter;
+ use_operand_p use_p;
+
+ FOR_EACH_PHI_OR_STMT_USE (use_p, def_stmt, iter, SSA_OP_USE)
+ {
+ tree use = USE_FROM_PTR (use_p);
+
+ if (ssa_undefined_value_p (use, false))
+ return use;
+ }
+ }
+
if (!EXPR_P (*tp))
*walk_subtrees = 0;
return NULL;
^ permalink raw reply [flat|nested] 11+ messages in thread
* [gcc(refs/users/aoliva/heads/testme)] [PR105665] ivopts: check defs of names in base for undefs
@ 2022-05-26 14:29 Alexandre Oliva
0 siblings, 0 replies; 11+ messages in thread
From: Alexandre Oliva @ 2022-05-26 14:29 UTC (permalink / raw)
To: gcc-cvs
https://gcc.gnu.org/g:956d7d6e6f657359550824e6363f75575fee6817
commit 956d7d6e6f657359550824e6363f75575fee6817
Author: Alexandre Oliva <oliva@adacore.com>
Date: Thu May 26 09:15:53 2022 -0300
[PR105665] ivopts: check defs of names in base for undefs
Diff:
---
gcc/testsuite/gcc.dg/torture/pr105665.c | 2 +-
gcc/tree-ssa-loop-ivopts.cc | 22 ++++++++++++++++++----
2 files changed, 19 insertions(+), 5 deletions(-)
diff --git a/gcc/testsuite/gcc.dg/torture/pr105665.c b/gcc/testsuite/gcc.dg/torture/pr105665.c
index 12f0b78a4b4..34cfc658434 100644
--- a/gcc/testsuite/gcc.dg/torture/pr105665.c
+++ b/gcc/testsuite/gcc.dg/torture/pr105665.c
@@ -6,7 +6,7 @@ int main() {
for (; b < 2; b++) {
int g;
if (f)
- b = 40;
+ g++, b = 40;
a = d[b * b];
for (f = 0; f < 3; f++) {
if (e)
diff --git a/gcc/tree-ssa-loop-ivopts.cc b/gcc/tree-ssa-loop-ivopts.cc
index 2e8cd486cc0..a834714181d 100644
--- a/gcc/tree-ssa-loop-ivopts.cc
+++ b/gcc/tree-ssa-loop-ivopts.cc
@@ -3074,13 +3074,24 @@ get_loop_invariant_expr (struct ivopts_data *data, tree inv_expr)
/* Find the first undefined SSA name in *TP. */
static tree
-find_ssa_undef (tree *tp, int *walk_subtrees, void *)
+find_ssa_undef (tree *tp, int *walk_subtrees, void *pset_)
{
+ auto pset = static_cast<hash_set<tree> *> (pset_);
+
if (TREE_CODE (*tp) == SSA_NAME)
{
+ if (ssa_defined_default_def_p (*tp))
+ return NULL;
+
if (ssa_undefined_value_p (*tp, false))
return *tp;
+ /* If we've already visited this SSA_NAME and got to it again,
+ we know we didn't find it to be undefined, otherwise we'd
+ have stopped the walk then. */
+ if (pset && pset->add (*tp))
+ return NULL;
+
gimple *def_stmt = SSA_NAME_DEF_STMT (*tp);
/* ssa_undefined_value_p must have caught nop defs above. */
gcc_checking_assert (!gimple_nop_p (def_stmt));
@@ -3092,8 +3103,10 @@ find_ssa_undef (tree *tp, int *walk_subtrees, void *)
{
tree use = USE_FROM_PTR (use_p);
- if (ssa_undefined_value_p (use, false))
- return use;
+ int wsub = 1;
+ tree result = find_ssa_undef (&use, &wsub, pset);
+ if (result)
+ return result;
}
}
@@ -3132,7 +3145,8 @@ add_candidate_1 (struct ivopts_data *data, tree base, tree step, bool important,
/* If BASE contains undefined SSA names make sure we only record
the original IV. */
bool involves_undefs = false;
- if (walk_tree (&base, find_ssa_undef, NULL, NULL))
+ hash_set<tree> pset;
+ if (walk_tree (&base, find_ssa_undef, &pset, NULL))
{
if (pos != IP_ORIGINAL)
return NULL;
^ permalink raw reply [flat|nested] 11+ messages in thread
* [gcc(refs/users/aoliva/heads/testme)] [PR105665] ivopts: check defs of names in base for undefs
@ 2022-05-26 13:11 Alexandre Oliva
0 siblings, 0 replies; 11+ messages in thread
From: Alexandre Oliva @ 2022-05-26 13:11 UTC (permalink / raw)
To: gcc-cvs
https://gcc.gnu.org/g:38cb5568ce3b8bfae001df066f5c5e9d1a7fe649
commit 38cb5568ce3b8bfae001df066f5c5e9d1a7fe649
Author: Alexandre Oliva <oliva@adacore.com>
Date: Thu May 26 09:15:53 2022 -0300
[PR105665] ivopts: check defs of names in base for undefs
Diff:
---
gcc/testsuite/gcc.dg/torture/pr105665.c | 2 +-
gcc/tree-ssa-loop-ivopts.cc | 19 +++++++++++++++----
2 files changed, 16 insertions(+), 5 deletions(-)
diff --git a/gcc/testsuite/gcc.dg/torture/pr105665.c b/gcc/testsuite/gcc.dg/torture/pr105665.c
index 12f0b78a4b4..34cfc658434 100644
--- a/gcc/testsuite/gcc.dg/torture/pr105665.c
+++ b/gcc/testsuite/gcc.dg/torture/pr105665.c
@@ -6,7 +6,7 @@ int main() {
for (; b < 2; b++) {
int g;
if (f)
- b = 40;
+ g++, b = 40;
a = d[b * b];
for (f = 0; f < 3; f++) {
if (e)
diff --git a/gcc/tree-ssa-loop-ivopts.cc b/gcc/tree-ssa-loop-ivopts.cc
index 2e8cd486cc0..e68968efc5f 100644
--- a/gcc/tree-ssa-loop-ivopts.cc
+++ b/gcc/tree-ssa-loop-ivopts.cc
@@ -3074,10 +3074,18 @@ get_loop_invariant_expr (struct ivopts_data *data, tree inv_expr)
/* Find the first undefined SSA name in *TP. */
static tree
-find_ssa_undef (tree *tp, int *walk_subtrees, void *)
+find_ssa_undef (tree *tp, int *walk_subtrees, void *pset_)
{
+ auto pset = static_cast<hash_set<tree> *> (pset_);
+
if (TREE_CODE (*tp) == SSA_NAME)
{
+ /* If we've already visited this SSA_NAME and got to it again,
+ we know we didn't find it to be undefined, otherwise we'd
+ have stopped the walk then. */
+ if (pset && pset->add (*tp))
+ return NULL;
+
if (ssa_undefined_value_p (*tp, false))
return *tp;
@@ -3092,8 +3100,10 @@ find_ssa_undef (tree *tp, int *walk_subtrees, void *)
{
tree use = USE_FROM_PTR (use_p);
- if (ssa_undefined_value_p (use, false))
- return use;
+ int wsub = 1;
+ tree result = find_ssa_undef (&use, &wsub, pset);
+ if (result)
+ return result;
}
}
@@ -3132,7 +3142,8 @@ add_candidate_1 (struct ivopts_data *data, tree base, tree step, bool important,
/* If BASE contains undefined SSA names make sure we only record
the original IV. */
bool involves_undefs = false;
- if (walk_tree (&base, find_ssa_undef, NULL, NULL))
+ hash_set<tree> pset;
+ if (walk_tree (&base, find_ssa_undef, &pset, NULL))
{
if (pos != IP_ORIGINAL)
return NULL;
^ permalink raw reply [flat|nested] 11+ messages in thread
* [gcc(refs/users/aoliva/heads/testme)] [PR105665] ivopts: check defs of names in base for undefs
@ 2022-05-26 12:49 Alexandre Oliva
0 siblings, 0 replies; 11+ messages in thread
From: Alexandre Oliva @ 2022-05-26 12:49 UTC (permalink / raw)
To: gcc-cvs
https://gcc.gnu.org/g:ab0624ba523cb6118ef65962603bc150de66f6e3
commit ab0624ba523cb6118ef65962603bc150de66f6e3
Author: Alexandre Oliva <oliva@adacore.com>
Date: Thu May 26 09:15:53 2022 -0300
[PR105665] ivopts: check defs of names in base for undefs
Diff:
---
gcc/tree-ssa-loop-ivopts.cc | 19 +++++++++++++++----
1 file changed, 15 insertions(+), 4 deletions(-)
diff --git a/gcc/tree-ssa-loop-ivopts.cc b/gcc/tree-ssa-loop-ivopts.cc
index 2e8cd486cc0..e68968efc5f 100644
--- a/gcc/tree-ssa-loop-ivopts.cc
+++ b/gcc/tree-ssa-loop-ivopts.cc
@@ -3074,10 +3074,18 @@ get_loop_invariant_expr (struct ivopts_data *data, tree inv_expr)
/* Find the first undefined SSA name in *TP. */
static tree
-find_ssa_undef (tree *tp, int *walk_subtrees, void *)
+find_ssa_undef (tree *tp, int *walk_subtrees, void *pset_)
{
+ auto pset = static_cast<hash_set<tree> *> (pset_);
+
if (TREE_CODE (*tp) == SSA_NAME)
{
+ /* If we've already visited this SSA_NAME and got to it again,
+ we know we didn't find it to be undefined, otherwise we'd
+ have stopped the walk then. */
+ if (pset && pset->add (*tp))
+ return NULL;
+
if (ssa_undefined_value_p (*tp, false))
return *tp;
@@ -3092,8 +3100,10 @@ find_ssa_undef (tree *tp, int *walk_subtrees, void *)
{
tree use = USE_FROM_PTR (use_p);
- if (ssa_undefined_value_p (use, false))
- return use;
+ int wsub = 1;
+ tree result = find_ssa_undef (&use, &wsub, pset);
+ if (result)
+ return result;
}
}
@@ -3132,7 +3142,8 @@ add_candidate_1 (struct ivopts_data *data, tree base, tree step, bool important,
/* If BASE contains undefined SSA names make sure we only record
the original IV. */
bool involves_undefs = false;
- if (walk_tree (&base, find_ssa_undef, NULL, NULL))
+ hash_set<tree> pset;
+ if (walk_tree (&base, find_ssa_undef, &pset, NULL))
{
if (pos != IP_ORIGINAL)
return NULL;
^ permalink raw reply [flat|nested] 11+ messages in thread
* [gcc(refs/users/aoliva/heads/testme)] [PR105665] ivopts: check defs of names in base for undefs
@ 2022-05-26 12:49 Alexandre Oliva
0 siblings, 0 replies; 11+ messages in thread
From: Alexandre Oliva @ 2022-05-26 12:49 UTC (permalink / raw)
To: gcc-cvs
https://gcc.gnu.org/g:e8e1a5d53833bab3774ca287381b84c5df1226ee
commit e8e1a5d53833bab3774ca287381b84c5df1226ee
Author: Alexandre Oliva <oliva@adacore.com>
Date: Thu May 26 09:38:31 2022 -0300
[PR105665] ivopts: check defs of names in base for undefs
Diff:
---
gcc/testsuite/gcc.dg/torture/pr105665.c | 20 ++++++++++++++++++++
gcc/tree-ssa-loop-ivopts.cc | 24 +++++++++++++++++++++---
2 files changed, 41 insertions(+), 3 deletions(-)
diff --git a/gcc/testsuite/gcc.dg/torture/pr105665.c b/gcc/testsuite/gcc.dg/torture/pr105665.c
new file mode 100644
index 00000000000..12f0b78a4b4
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/torture/pr105665.c
@@ -0,0 +1,20 @@
+/* { dg-do run } */
+
+int a, b, c[1], d[2], *e = c;
+int main() {
+ int f = 0;
+ for (; b < 2; b++) {
+ int g;
+ if (f)
+ b = 40;
+ a = d[b * b];
+ for (f = 0; f < 3; f++) {
+ if (e)
+ break;
+ g--;
+ if (a)
+ a = g;
+ }
+ }
+ return 0;
+}
diff --git a/gcc/tree-ssa-loop-ivopts.cc b/gcc/tree-ssa-loop-ivopts.cc
index 81b536f9304..2e8cd486cc0 100644
--- a/gcc/tree-ssa-loop-ivopts.cc
+++ b/gcc/tree-ssa-loop-ivopts.cc
@@ -3076,9 +3076,27 @@ get_loop_invariant_expr (struct ivopts_data *data, tree inv_expr)
static tree
find_ssa_undef (tree *tp, int *walk_subtrees, void *)
{
- if (TREE_CODE (*tp) == SSA_NAME
- && ssa_undefined_value_p (*tp, false))
- return *tp;
+ if (TREE_CODE (*tp) == SSA_NAME)
+ {
+ if (ssa_undefined_value_p (*tp, false))
+ return *tp;
+
+ gimple *def_stmt = SSA_NAME_DEF_STMT (*tp);
+ /* ssa_undefined_value_p must have caught nop defs above. */
+ gcc_checking_assert (!gimple_nop_p (def_stmt));
+
+ ssa_op_iter iter;
+ use_operand_p use_p;
+
+ FOR_EACH_PHI_OR_STMT_USE (use_p, def_stmt, iter, SSA_OP_ALL_USES)
+ {
+ tree use = USE_FROM_PTR (use_p);
+
+ if (ssa_undefined_value_p (use, false))
+ return use;
+ }
+ }
+
if (!EXPR_P (*tp))
*walk_subtrees = 0;
return NULL;
^ permalink raw reply [flat|nested] 11+ messages in thread
end of thread, other threads:[~2022-06-02 11:58 UTC | newest]
Thread overview: 11+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-05-28 0:09 [gcc(refs/users/aoliva/heads/testme)] [PR105665] ivopts: check defs of names in base for undefs Alexandre Oliva
-- strict thread matches above, loose matches on Subject: below --
2022-06-02 11:58 Alexandre Oliva
2022-06-02 1:27 Alexandre Oliva
2022-05-28 4:45 Alexandre Oliva
2022-05-28 0:11 Alexandre Oliva
2022-05-26 15:46 Alexandre Oliva
2022-05-26 15:46 Alexandre Oliva
2022-05-26 14:29 Alexandre Oliva
2022-05-26 13:11 Alexandre Oliva
2022-05-26 12:49 Alexandre Oliva
2022-05-26 12:49 Alexandre Oliva
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).