[PR,tree-optimization/71691] Fix unswitching in presence of maybe-undef SSA_NAMEs (take 2)
diff mbox

Message ID 50a9aa36-16ff-49f0-59fb-9bb08733b94a@redhat.com
State New
Headers show

Commit Message

Aldy Hernandez Jan. 27, 2017, 11:20 a.m. UTC
On 01/26/2017 07:29 AM, Richard Biener wrote:
> On Thu, Jan 26, 2017 at 1:04 PM, Aldy Hernandez <aldyh@redhat.com> wrote:
>> On 01/24/2017 07:23 AM, Richard Biener wrote:

> Your initial on-demand approach is fine to catch some of the cases but it
> will not handle those for which we'd need post-dominance.
>
> I guess we can incrementally add that.

No complaints from me.

This is my initial on-demand approach, with a few fixes you've commented 
on throughout.

As you can see, there is still an #if 0 wrt to using your suggested 
conservative handling of memory loads, which I'm not entirely convinced 
of, as it pessimizes gcc.dg/loop-unswitch-1.c.  If you feel strongly 
about it, I can enable the code again.

Also, I enhanced gcc.dg/loop-unswitch-1.c to verify that we're actually 
unswitching something.  It seems kinda silly that we have various 
unswitch tests, but we don't actually check whether we have unswitched 
anything.  This test was the only one in the *unswitch*.c set that I saw 
was actually being unswitched.  Of course, if you don't agree with my 
#if 0 above, I will remove this change to the test.

Finally, are we even guaranteed to unswitch in loop-unswitch-1.c across 
architectures?  If not, again, I can remove the one-liner.

How does this look for trunk?

Aldy
gcc/

	PR tree-optimization/71691
	* bitmap.h (class auto_bitmap): New.
	* tree-ssa-defined-or-undefined.c: New file.
	* tree-ssa-defined-or-undefined.h: New file.
	* Makefile.in (tree-ssa-defined-or-undefined.o): New.
	* tree-ssa-loop-unswitch.c (tree_may_unswitch_on): Add
	defined_or_undefined parameter.  Use defined_or_undefined instead
	of ssa_undefined_value_p.
	(tree_unswitch_single_loop): Instantiate defined_or_undefined
	variable.

Comments

Richard Biener Jan. 30, 2017, 3:03 p.m. UTC | #1
On Fri, Jan 27, 2017 at 12:20 PM, Aldy Hernandez <aldyh@redhat.com> wrote:
> On 01/26/2017 07:29 AM, Richard Biener wrote:
>>
>> On Thu, Jan 26, 2017 at 1:04 PM, Aldy Hernandez <aldyh@redhat.com> wrote:
>>>
>>> On 01/24/2017 07:23 AM, Richard Biener wrote:
>
>
>> Your initial on-demand approach is fine to catch some of the cases but it
>> will not handle those for which we'd need post-dominance.
>>
>> I guess we can incrementally add that.
>
>
> No complaints from me.
>
> This is my initial on-demand approach, with a few fixes you've commented on
> throughout.
>
> As you can see, there is still an #if 0 wrt to using your suggested
> conservative handling of memory loads, which I'm not entirely convinced of,
> as it pessimizes gcc.dg/loop-unswitch-1.c.  If you feel strongly about it, I
> can enable the code again.

It is really required -- fortunately loop-unswitch-1.c is one of the cases where
the post-dom / always-executed bits help .  The comparison is inside the
loop header and thus always executed when the loop enters, so inserrting it
on the preheader edge is fine.

> Also, I enhanced gcc.dg/loop-unswitch-1.c to verify that we're actually
> unswitching something.  It seems kinda silly that we have various unswitch
> tests, but we don't actually check whether we have unswitched anything.

Heh.  It probably was added for an ICE...

> This test was the only one in the *unswitch*.c set that I saw was actually
> being unswitched.  Of course, if you don't agree with my #if 0 above, I will
> remove this change to the test.
>
> Finally, are we even guaranteed to unswitch in loop-unswitch-1.c across
> architectures?  If not, again, I can remove the one-liner.

I think so.

>
> How does this look for trunk?

With a unswitch-local solution I meant to not add new files but put the
defined_or_undefined class (well, or rather a single function...) into
tree-ssa-loop-unswitch.c.

@@ -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);

as I said, moving this (now more expensive check) after

      if (def_bb
          && flow_bb_inside_loop_p (loop, def_bb))
        return NULL_TREE;

this cheap check would be better.  It should avoid 99% of all calls I bet.

You can recover the loop-unswitch-1.c case by passing down
the using stmt and checking its BB against loop_header (the only
block that we trivially know is always executed when entering the region).
Or do that check in the caller, like

        if (bb != loop->header
           && ssa_undefined_value_p (use, true) /
defined_or_undefined->is_maybe_undefined (use))

+      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;

You should never run into virtual operands (you only walk SSA_OP_USEs).

You can stop walking at stmts that dominate the region header,
like with

+      gimple *def = SSA_NAME_DEF_STMT (t);
        /* Uses in stmts always executed when the region header
executes are fine.  */
        if (dominated_by_p (CDI_DOMINATORS, loop_header, gimple_bb (def)))
          continue;

and the bail out for PARM_DECLs is wrong:

+      /* 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;

needs to be a continue; rather than a return false.


Otherwise looks ok and sorry for the continuing delays in reviewing this...

Thanks,
Richard.

> Aldy
>

Patch
diff mbox

diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 821584a..e0de276 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -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 \
diff --git a/gcc/bitmap.h b/gcc/bitmap.h
index 196738b..f158b44 100644
--- a/gcc/bitmap.h
+++ b/gcc/bitmap.h
@@ -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 */
diff --git a/gcc/testsuite/gcc.dg/loop-unswitch-1.c b/gcc/testsuite/gcc.dg/loop-unswitch-1.c
index 930364c..f6fc41d 100644
--- a/gcc/testsuite/gcc.dg/loop-unswitch-1.c
+++ b/gcc/testsuite/gcc.dg/loop-unswitch-1.c
@@ -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" } } */
diff --git a/gcc/testsuite/gcc.dg/loop-unswitch-5.c b/gcc/testsuite/gcc.dg/loop-unswitch-5.c
new file mode 100644
index 0000000..b41e853
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/loop-unswitch-5.c
@@ -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;
+}
diff --git a/gcc/tree-ssa-defined-or-undefined.c b/gcc/tree-ssa-defined-or-undefined.c
new file mode 100644
index 0000000..0ee91e5
--- /dev/null
+++ b/gcc/tree-ssa-defined-or-undefined.c
@@ -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;
+}
diff --git a/gcc/tree-ssa-defined-or-undefined.h b/gcc/tree-ssa-defined-or-undefined.h
new file mode 100644
index 0000000..aef0908
--- /dev/null
+++ b/gcc/tree-ssa-defined-or-undefined.h
@@ -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
diff --git a/gcc/tree-ssa-loop-unswitch.c b/gcc/tree-ssa-loop-unswitch.c
index 92599fb..4452373 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
 
@@ -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)