@@ -1507,6 +1507,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 \
@@ -802,4 +802,25 @@ bmp_iter_and_compl (bitmap_iterator *bi, unsigned *bit_no)
bmp_iter_and_compl (&(ITER), &(BITNUM)); \
bmp_iter_next (&(ITER), &(BITNUM)))
+/* A class that ties the lifetime of a bitmap to its scope. */
+class auto_bitmap
+{
+ public:
+ auto_bitmap () { bits = BITMAP_ALLOC (NULL); }
+ ~auto_bitmap () { BITMAP_FREE (bits); }
+ // Allow calling bitmap functions on our bitmap.
+ operator bitmap () { return bits; }
+
+ private:
+ // Prevent making a copy that references our bitmap.
+ auto_bitmap (const auto_bitmap &);
+ auto_bitmap &operator = (const auto_bitmap &);
+#if __cplusplus >= 201103L
+ auto_bitmap (auto_bitmap &&);
+ auto_bitmap &operator = (auto_bitmap &&);
+#endif
+
+ bitmap bits;
+};
+
#endif /* GCC_BITMAP_H */
@@ -1,6 +1,6 @@
/* For PR rtl-optimization/27735 */
/* { dg-do compile } */
-/* { dg-options "-O2 -funswitch-loops" } */
+/* { dg-options "-O2 -funswitch-loops -fdump-tree-unswitch-details" } */
void set_color(void);
void xml_colorize_line(unsigned int *p, int state)
@@ -32,3 +32,5 @@ parse_tag: ;
}
}
+/* Test that we actually unswitched something. */
+/* { dg-final { scan-tree-dump ";; Unswitching loop" "unswitch" } } */
new file mode 100644
@@ -0,0 +1,51 @@
+/* PR middle-end/71691 */
+/* { dg-do run } */
+/* { dg-options "-fno-tree-vrp -O2 -funswitch-loops -fdump-tree-unswitch-details" } */
+
+/* Note: The -fno-tree-vrp above is only there to avoid VRP papering
+ over the problem. */
+
+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 ();
+ return 0;
+}
new file mode 100644
@@ -0,0 +1,118 @@
+/* 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) 2017 Free Software Foundation, Inc.
+ Contributed by Aldy Hernandez <aldyh@redhat.com>.
+
+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 "ssa.h"
+#include "tree-ssa.h"
+#include "cfgloop.h"
+#include "tree-ssa-defined-or-undefined.h"
+
+/* Return TRUE if an SSA_NAME maybe undefined. */
+
+bool
+defined_or_undefined::is_maybe_undefined (const tree name)
+{
+ auto_bitmap visited_ssa;
+ auto_vec<tree> worklist;
+ worklist.safe_push (name);
+ bitmap_set_bit (visited_ssa, SSA_NAME_VERSION (name));
+ while (!worklist.is_empty ())
+ {
+ tree t = worklist.pop ();
+
+ /* If it's obviously undefined, avoid further computations. */
+ if (ssa_undefined_value_p (t, true))
+ return true;
+
+ /* A PARM_DECL will not have an SSA_NAME_DEF_STMT. Parameters
+ get their initial value from function entry. */
+ if (SSA_NAME_VAR (t) && TREE_CODE (SSA_NAME_VAR (t)) == PARM_DECL)
+ return false;
+
+ gimple *def = SSA_NAME_DEF_STMT (t);
+
+ /* Check that all the PHI args are fully defined. */
+ if (gphi *phi = dyn_cast <gphi *> (def))
+ {
+ if (virtual_operand_p (PHI_RESULT (phi)))
+ continue;
+ for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i)
+ {
+ tree t = gimple_phi_arg_def (phi, i);
+ /* If an SSA has already been seen, it may be a loop,
+ but we can continue and ignore this use. Otherwise,
+ add the SSA_NAME to the queue and visit it later. */
+ if (TREE_CODE (t) == SSA_NAME
+ && bitmap_set_bit (visited_ssa, SSA_NAME_VERSION (t)))
+ worklist.safe_push (t);
+ }
+ continue;
+ }
+
+ /* Handle calls and memory loads conservatively. */
+ if (!is_gimple_assign (def)
+#if 0
+ /*
+ This will inhibit unswitching in the presence of memory loads,
+ which causes gcc.dg/loop_unswitch-1.c to FAIL because we no longer
+ unswitch:
+
+ for (;;) {
+ c = *p;
+ ...
+ if (c)
+ stuff;
+ else
+ other_stuff;
+ }
+ */
+ || (gimple_assign_single_p (def)
+ && gimple_vuse (def)))
+#endif
+ )
+ return true;
+
+ /* Check that any SSA names used to define NAME are also fully
+ defined. */
+ use_operand_p use_p;
+ ssa_op_iter iter;
+ FOR_EACH_SSA_USE_OPERAND (use_p, def, iter, SSA_OP_USE)
+ {
+ tree t = USE_FROM_PTR (use_p);
+ /* If an SSA has already been seen, it may be a loop,
+ but we can continue and ignore this use. Otherwise,
+ add the SSA_NAME to the queue and visit it later. */
+ if (bitmap_set_bit (visited_ssa, SSA_NAME_VERSION (t)))
+ worklist.safe_push (t);
+ }
+ }
+ return false;
+}
new file mode 100644
@@ -0,0 +1,59 @@
+/* Simple class for identifying SSA_NAMEs that are either fully defined
+ or maybe undefined.
+
+ Copyright (C) 2017 Free Software Foundation, Inc.
+ Contributed by Aldy Hernandez <aldyh@redhat.com>.
+
+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
+{
+ private:
+ // Entry block of the current loop.
+ basic_block loop_entry;
+ vec<basic_block> loop_region;
+ public:
+ defined_or_undefined (struct loop *loop)
+ { loop_entry = loop->header; }
+ /* Note: We could implement a variant of this class that does not
+ need loop info. Until such need arises, leave this
+ unimplemented. */
+ defined_or_undefined ();
+ // Return TRUE if SSA is maybe undefined.
+ bool is_maybe_undefined (tree ssa);
+ // Return TRUE if SSA is definitely defined.
+ bool is_defined (tree ssa) { return !is_maybe_undefined (ssa); }
+};
+
+#endif // GCC_TREE_SSA_DEFINED_OR_UNDEFINED_H
@@ -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
@@ -77,7 +78,8 @@ along with GCC; see the file COPYING3. If not see
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 tree tree_may_unswitch_on (basic_block, struct loop *,
+ 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);
@@ -113,7 +115,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,
+ defined_or_undefined *defined_or_undefined)
{
gimple *last, *def;
gcond *stmt;
@@ -138,7 +141,7 @@ tree_may_unswitch_on (basic_block bb, struct loop *loop)
{
/* Unswitching on undefined values would introduce undefined
behavior that the original program might never exercise. */
- if (ssa_undefined_value_p (use, true))
+ if (defined_or_undefined->is_maybe_undefined (use))
return NULL_TREE;
def = SSA_NAME_DEF_STMT (use);
def_bb = gimple_bb (def);
@@ -200,6 +203,7 @@ tree_unswitch_single_loop (struct loop *loop, int num)
gimple *stmt;
bool changed = false;
HOST_WIDE_INT iterations;
+ defined_or_undefined defined_or_undefined (loop);
/* Perform initial tests if unswitch is eligible. */
if (num == 0)
@@ -243,7 +247,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 +367,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)