[PR tree-optimization/71691] Fix unswitching in presence of maybe-undefined SSA_NAMEs
Jeff Law
law@redhat.com
Thu Aug 18 17:30:00 GMT 2016
So to recap, the problem with this BZ is we have a maybe-undefined
SSA_NAME in the IL. That maybe-undefined name is used as a condition
inside a loop and we unswitch that condition.
tree-ssa-loop-unswitch.c already tries to avoid doing that, but uses the
optimistic ssa_undefined_value_p function.
Essentially ssa_undefined_value_p just checks to see if the SSA_NAME is
set from a real statement. It doesn't look at the operands of that
statement to see if they're undefined, nor does it walk the use-def
chains of the RHS operands. In short, it's totally inappropriate for
unswitching's needs.
This patch introduces a new class where we can ask if a particular
SSA_NAME is defined or may be undefined. Only the latter interface is
currently used and I wouldn't object if we wanted to avoid the former
interface until we needed it (it's just a trivial bitmap test, so we're
not losing any real knowledge of how to implement it).
We walk the CFG in dominator order. For each block we walk the PHIs and
mark the LHS as defined IFF all the RHS arguments are defined. Then we
walk the statements and mark their LHSs as defined IIFF all the RHS
arguments are defined.
This gives us a conservative solution to the may be undefined question.
We do not try to keep this information up-to-date as statements or CFG
are updated -- queries on newly added SSA_NAMEs always return
may-be-undefined.
This information is ephemeral and not kept up-to-date. We perform the
analysis in the class's constructor and tear down the resulting bitmap
in the class's destructor.
Bootstrapped and regression tested on x86_64-linux-gnu.
Ok for the trunk?
Jeff
-------------- next part --------------
PR tree-optimization/71691
* Makefile.in (OBJS): Add tree-ssa-defined-or-undefined.
* tree-ssa-defined-or-undefined.h: New file.
* tree-ssa-defined-or-undefined.c: New file.
* tree-ssa-loop-unswitch.c: Include tree-ssa-defined-or-undefined.h
(tree_ssa_unswitch_loops): Create a defined_or_undefined class instance
and pass it to tree_unswitch_single_loop.
(tree_unswitch_single_loop): Pass instance down through recursive calls
and into tree_may_unswitch_on.
(tree_may_unswitch_on): Use defined_or_undefined instance rather than
ssa_undefined_value_p.
PR tree-optimization/71691
* gcc.c-torture/execute/pr71691.c: New test.
diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 7a0160f..9e881b8 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1491,6 +1491,7 @@ OBJS = \
tree-ssa-coalesce.o \
tree-ssa-copy.o \
tree-ssa-dce.o \
+ tree-ssa-defined-or-undefined.o \
tree-ssa-dom.o \
tree-ssa-dse.o \
tree-ssa-forwprop.o \
diff --git a/gcc/testsuite/gcc.c-torture/execute/pr71691.c b/gcc/testsuite/gcc.c-torture/execute/pr71691.c
new file mode 100644
index 0000000..2c5dbb6
--- /dev/null
+++ b/gcc/testsuite/gcc.c-torture/execute/pr71691.c
@@ -0,0 +1,45 @@
+char b;
+short f;
+unsigned e;
+int g = 20;
+
+void
+foo ()
+{
+ int l, h;
+ for (l = 0; l <= 7; l++)
+ {
+ int j = 38;
+ if (g)
+ h = 0;
+ for (; h <= 7; h++)
+ {
+ int i, k = b % (j % 4);
+ g = f;
+ for (;;)
+ {
+ j = 6 || b;
+ if (e)
+ {
+ for (; j; --j)
+ if (k)
+ __builtin_printf ("%d", 9);
+ if (i)
+ __builtin_printf ("%d", j);
+ }
+ if (l)
+ continue;
+ break;
+ }
+ i = f || b;
+ }
+ }
+}
+
+int
+main ()
+{
+ foo ();
+ exit (0);
+}
+
diff --git a/gcc/tree-ssa-defined-or-undefined.c b/gcc/tree-ssa-defined-or-undefined.c
new file mode 100644
index 0000000..50de443
--- /dev/null
+++ b/gcc/tree-ssa-defined-or-undefined.c
@@ -0,0 +1,128 @@
+/* Simple class for classifying SSA_NAMEs that are either fully defined
+ or possibly undefined.
+
+ This is meant to support conservative analysis for optimization purposes,
+ not for generating warnings. The analysis for generating warnings is
+ deeper to avoid generation of false positives.
+
+ Copyright (C) 2001-2016 Free Software Foundation, Inc.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 3, or (at your option)
+any later version.
+
+GCC is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3. If not see
+<http://www.gnu.org/licenses/>. */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "backend.h"
+#include "tree.h"
+#include "gimple.h"
+#include "tree-pass.h"
+#include "ssa.h"
+#include "gimple-pretty-print.h"
+#include "diagnostic-core.h"
+#include "fold-const.h"
+#include "gimple-iterator.h"
+#include "tree-ssa.h"
+#include "params.h"
+#include "tree-cfg.h"
+#include "tree-ssa-defined-or-undefined.h"
+
+/* Analyze the current function to determine the SSA_NAMEs that are
+ fully defined and those which may be undefined. */
+
+defined_or_undefined::defined_or_undefined (void)
+{
+ m_defined_names = BITMAP_ALLOC (NULL);
+
+ /* We can just do a dominator walk of the CFG analyzing each statement
+ in each block. If a statement uses a possibly undefined value, then
+ all results of this statement are considered possibly undefined.
+
+ This may give overly conservative results for loops, but that's safe. */
+ walk_bbs (ENTRY_BLOCK_PTR_FOR_FN (cfun));
+}
+
+/* Walk the PHIs and statements within BB to determine the defined/undefined
+ status of each SSA_NAME set in BB. Then recurse into dominator children. */
+
+void
+defined_or_undefined::walk_bbs (basic_block bb)
+{
+ /* Walk each PHI. The LHS of the PHI is only considered fully defined
+ if each RHS argument is fully defined. */
+ gphi_iterator gsi;
+ for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ {
+ gphi *phi = gsi.phi ();
+ unsigned int i;
+ for (i = 0; i < gimple_phi_num_args (phi); i++)
+ {
+ tree arg = gimple_phi_arg_def (phi, i);
+ if (TREE_CODE (arg) == SSA_NAME && is_maybe_undefined (arg))
+ break;
+ }
+
+ if (i == gimple_phi_num_args (phi))
+ bitmap_set_bit (m_defined_names,
+ SSA_NAME_VERSION (gimple_phi_result (phi)));
+ }
+
+ /* Similarly for all the statements in the block. The outputs are
+ considered fully defined if and only iff all the inputs are
+ fully defined. */
+ gimple_stmt_iterator si;
+ for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
+ if (!gimple_uses_undefined_value_p (gsi_stmt (si)))
+ {
+ tree def;
+ ssa_op_iter iter;
+
+ FOR_EACH_SSA_TREE_OPERAND (def, gsi_stmt (si), iter, SSA_OP_ALL_DEFS)
+ bitmap_set_bit (m_defined_names, SSA_NAME_VERSION (def));
+ }
+
+ /* Recurse into the dominator children of BB. */
+ basic_block son;
+ for (son = first_dom_son (CDI_DOMINATORS, bb);
+ son;
+ son = next_dom_son (CDI_DOMINATORS, son))
+ walk_bbs (son);
+}
+
+defined_or_undefined::~defined_or_undefined (void)
+{
+ BITMAP_FREE (m_defined_names);
+}
+
+/* Return TRUE if T (an SSA_NAME) is possibly undefined in this function,
+ false otherwise. SSA_NAMEs not encountered during the initial
+ analysis will be considered undefined. */
+
+bool
+defined_or_undefined::is_maybe_undefined (tree t)
+{
+ return !bitmap_bit_p (m_defined_names, SSA_NAME_VERSION (t));
+}
+
+/* Return TRUE if T (an SSA_NAME) is defined in this function,
+ false otherwise. SSA_NAMEs not encountered during the initial
+ analysis will be considered undefined. */
+
+bool
+defined_or_undefined::is_defined (tree t)
+{
+ return bitmap_bit_p (m_defined_names, SSA_NAME_VERSION (t));
+}
diff --git a/gcc/tree-ssa-defined-or-undefined.h b/gcc/tree-ssa-defined-or-undefined.h
new file mode 100644
index 0000000..e0f98e7
--- /dev/null
+++ b/gcc/tree-ssa-defined-or-undefined.h
@@ -0,0 +1,64 @@
+/* Simple class for identifying SSA_NAMEs that are either fully defined
+ or maybe undefined.
+
+ Copyright (C) 2001-2016 Free Software Foundation, Inc.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 3, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3. If not see
+<http://www.gnu.org/licenses/>. */
+
+#ifndef GCC_TREE_SSA_DEFINED_OR_UNDEFINED_H
+#define GCC_TREE_SSA_DEFINED_OR_UNDEFINED_H
+
+/* Simple class for identifying SSA_NAMEs that are either fully defined
+ or maybe undefined.
+
+ This is meant to support conservative analysis for optimization purposes,
+ not for generating warnings. The analysis for generating warnings is
+ deeper to avoid generation of false positives.
+
+ Instantiation of this class triggers analysis which is not kept up-to-date
+ as changes in the IL or CFG are made.
+
+ Queries will return the conservative result (maybe undefined) for SSA_NAMEs
+ that were not encountered during the initial analysis. */
+
+class defined_or_undefined
+{
+ public:
+ defined_or_undefined ();
+ ~defined_or_undefined ();
+
+ /* Return TRUE if T (an SSA_NAME) is possibly undefined in this function,
+ false otherwise. SSA_NAMEs not encountered during the initial
+ analysis will be considered undefined. */
+ bool is_maybe_undefined (tree);
+
+ /* Return TRUE if T (an SSA_NAME) is defined in this function,
+ false otherwise. SSA_NAMEs not encountered during the initial
+ analysis will be considered undefined. */
+ bool is_defined (tree);
+
+ private:
+ /* We do not allow copying this object or initializing one
+ from another. */
+ defined_or_undefined& operator= (const defined_or_undefined&);
+ defined_or_undefined (const defined_or_undefined&);
+
+ void walk_bbs (basic_block);
+ bitmap m_defined_names;
+};
+
+#endif /* GCC_TREE_SSA_DEFINED_OR_UNDEFINED */
diff --git a/gcc/tree-ssa-loop-unswitch.c b/gcc/tree-ssa-loop-unswitch.c
index 40905af..fb94807 100644
--- a/gcc/tree-ssa-loop-unswitch.c
+++ b/gcc/tree-ssa-loop-unswitch.c
@@ -38,6 +38,7 @@ along with GCC; see the file COPYING3. If not see
#include "gimple-iterator.h"
#include "cfghooks.h"
#include "tree-ssa-loop-manip.h"
+#include "tree-ssa-defined-or-undefined.h"
/* This file implements the loop unswitching, i.e. transformation of loops like
@@ -76,8 +77,10 @@ along with GCC; see the file COPYING3. If not see
shape. */
static struct loop *tree_unswitch_loop (struct loop *, basic_block, tree);
-static bool tree_unswitch_single_loop (struct loop *, int);
-static tree tree_may_unswitch_on (basic_block, struct loop *);
+static bool tree_unswitch_single_loop (struct loop *, int,
+ class defined_or_undefined *);
+static tree tree_may_unswitch_on (basic_block, struct loop *,
+ class defined_or_undefined *);
static bool tree_unswitch_outer_loop (struct loop *);
static edge find_loop_guard (struct loop *);
static bool empty_bb_without_guard_p (struct loop *, basic_block);
@@ -93,13 +96,14 @@ tree_ssa_unswitch_loops (void)
{
struct loop *loop;
bool changed = false;
+ class defined_or_undefined defined_or_undefined;
/* Go through all loops starting from innermost. */
FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
{
if (!loop->inner)
/* Unswitch innermost loop. */
- changed |= tree_unswitch_single_loop (loop, 0);
+ changed |= tree_unswitch_single_loop (loop, 0, &defined_or_undefined);
else
changed |= tree_unswitch_outer_loop (loop);
}
@@ -113,7 +117,8 @@ tree_ssa_unswitch_loops (void)
basic blocks (for what it means see comments below). */
static tree
-tree_may_unswitch_on (basic_block bb, struct loop *loop)
+tree_may_unswitch_on (basic_block bb, struct loop *loop,
+ class defined_or_undefined *defined_or_undefined)
{
gimple *last, *def;
gcond *stmt;
@@ -137,8 +142,9 @@ tree_may_unswitch_on (basic_block bb, struct loop *loop)
FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
{
/* Unswitching on undefined values would introduce undefined
- behavior that the original program might never exercise. */
- if (ssa_undefined_value_p (use, true))
+ behavior that the original program might never exercise. Note
+ carefully we can not unswitch on a maybe undefined value. */
+ if (defined_or_undefined->is_maybe_undefined (use))
return NULL_TREE;
def = SSA_NAME_DEF_STMT (use);
def_bb = gimple_bb (def);
@@ -191,7 +197,8 @@ simplify_using_entry_checks (struct loop *loop, tree cond)
grow exponentially. */
static bool
-tree_unswitch_single_loop (struct loop *loop, int num)
+tree_unswitch_single_loop (struct loop *loop, int num,
+ class defined_or_undefined *defined_or_undefined)
{
basic_block *bbs;
struct loop *nloop;
@@ -243,7 +250,7 @@ tree_unswitch_single_loop (struct loop *loop, int num)
{
/* Find a bb to unswitch on. */
for (; i < loop->num_nodes; i++)
- if ((cond = tree_may_unswitch_on (bbs[i], loop)))
+ if ((cond = tree_may_unswitch_on (bbs[i], loop, defined_or_undefined)))
break;
if (i == loop->num_nodes)
@@ -363,7 +370,8 @@ tree_unswitch_single_loop (struct loop *loop, int num)
/* Find a bb to unswitch on. */
for (; found < loop->num_nodes; found++)
if ((bbs[found]->flags & BB_REACHABLE)
- && (cond = tree_may_unswitch_on (bbs[found], loop)))
+ && (cond = tree_may_unswitch_on (bbs[found], loop,
+ defined_or_undefined)))
break;
if (found == loop->num_nodes)
@@ -391,8 +399,8 @@ tree_unswitch_single_loop (struct loop *loop, int num)
free_original_copy_tables ();
/* Invoke itself on modified loops. */
- tree_unswitch_single_loop (nloop, num + 1);
- tree_unswitch_single_loop (loop, num + 1);
+ tree_unswitch_single_loop (nloop, num + 1, defined_or_undefined);
+ tree_unswitch_single_loop (loop, num + 1, defined_or_undefined);
free (bbs);
return true;
}
More information about the Gcc-patches
mailing list