public inbox for gcc-cvs@sourceware.org
help / color / mirror / Atom feed
* [gcc r12-8624] [PR105665] ivopts: check defs of names in base for undefs
@ 2022-07-27 9:24 Richard Biener
0 siblings, 0 replies; only message in thread
From: Richard Biener @ 2022-07-27 9:24 UTC (permalink / raw)
To: gcc-cvs
https://gcc.gnu.org/g:4ca164a6372412a1b3dc62b6fbde77d338e22bd4
commit r12-8624-g4ca164a6372412a1b3dc62b6fbde77d338e22bd4
Author: Alexandre Oliva <oliva@adacore.com>
Date: Fri Jun 3 03:59:03 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.
(cherry picked from commit be2861fe8c527a5952257462ceca899bb43b1452)
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] only message in thread
only message in thread, other threads:[~2022-07-27 9:24 UTC | newest]
Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-07-27 9:24 [gcc r12-8624] [PR105665] ivopts: check defs of names in base for undefs Richard Biener
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).