Fix ICE in loop unrolling

Fix ICE in loop unrolling

[Sebastian Pop]

[-- Attachment #1: Type: text/plain, Size: 1976 bytes --]

Hi,

fixing one of the bugs of the loop distribution, I ended up fixing a
bug in the loop unrolling: try_unroll_loop_completely leaves the exit
edges and does not update correctly the dominators information, so gcc
ends in an ICE just after the modified code in update_ssa that uses
this information.  The proposed patch uses the exact same mechanism to
remove the unused edges as in tree_transform_and_unroll_loop.

I suspect that it is possible to come up with a testcase that triggers
this ICE, without needing loop distribution, but I can't figure out a
testcase just now.

Regstrapped on amd64-linux.  Okay for trunk?


---------- Forwarded message ----------
From:  <spop@gcc13.fsffrance.org>
Date: Nov 7, 2007 5:08 PM
Subject: [regtest] Results for 827_unroll.diff.asc on x86_64-unknown-linux-gnu
To: sebpop@gmail.com


Checker: (2007_11_07_23_08_41): (cat
/home/spop/trunk-tester/state/testing/patched/report
there are no regressions with your patch.
Checker: (2007_11_07_23_08_41): tac)
Checker: (2007_11_07_23_08_41): FAILs with patched version:
Checker: (2007_11_07_23_08_41): (cat
/home/spop/trunk-tester/state/testing/patched/failed
gcc.sum gcc.c-torture/execute/mayalias-2.c
gcc.sum gcc.c-torture/execute/mayalias-3.c
gcc.sum gcc.dg/torture/builtin-pow-mpfr-1.c
libmudflap.sum libmudflap.c++/pass41-frag.cxx
libstdc++.sum abi_check
Checker: (2007_11_07_23_08_41): tac)
Checker: (2007_11_07_23_08_41): FAILs with pristine version:
Checker: (2007_11_07_23_08_41): (cat
/home/spop/trunk-tester/state/trunk/129967/failed
gcc.sum gcc.c-torture/execute/mayalias-2.c
gcc.sum gcc.c-torture/execute/mayalias-3.c
gcc.sum gcc.dg/torture/builtin-pow-mpfr-1.c
libmudflap.sum libmudflap.c++/pass41-frag.cxx
libstdc++.sum abi_check
Checker: (2007_11_07_23_08_41): tac)
Checker: (2007_11_07_23_08_41): The files used for the validation of
your patch are stored in
/home/spop/trunk-tester/state/patched/2007_11_07_23_08_41 on the
tester machine.



-- 
Sebastian
AMD - GNU Tools

[-- Attachment #2: 827_unroll.diff.asc --]
[-- Type: text/plain, Size: 1590 bytes --]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

2007-11-03  Sebastian Pop  <sebastian.pop@amd.com>

	* tree-ssa-loop-ivcanon.c (try_unroll_loop_completely): Remove
	unused edges after loop duplication.

email:sebpop@gmail.com
branch:trunk
revision:HEAD
configure:
make:
check:

Index: tree-ssa-loop-ivcanon.c
===================================================================
- --- tree-ssa-loop-ivcanon.c	(revision 129581)
+++ tree-ssa-loop-ivcanon.c	(working copy)
@@ -222,6 +222,9 @@ try_unroll_loop_completely (struct loop 
   if (n_unroll)
     {
       sbitmap wont_exit;
+      edge e;
+      unsigned i;
+      VEC (edge, heap) *to_remove = NULL;
 
       old_cond = COND_EXPR_COND (cond);
       COND_EXPR_COND (cond) = dont_exit;
@@ -234,7 +237,7 @@ try_unroll_loop_completely (struct loop 
 
       if (!tree_duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
 					       n_unroll, wont_exit,
- -					       exit, NULL,
+					       exit, &to_remove,
 					       DLTHE_FLAG_UPDATE_FREQ
 					       | DLTHE_FLAG_COMPLETTE_PEEL))
 	{
@@ -244,6 +247,14 @@ try_unroll_loop_completely (struct loop 
 	  free (wont_exit);
 	  return false;
 	}
+
+      for (i = 0; VEC_iterate (edge, to_remove, i, e); i++)
+	{
+	  bool ok = remove_path (e);
+	  gcc_assert (ok);
+	}
+
+      VEC_free (edge, heap, to_remove);
       free (wont_exit);
       free_original_copy_tables ();
     }
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)

iD8DBQFHMcAZF6VcDuI4GrsRAjx9AJ49N5NPjbLJr927MlkrsON1aIUjtwCfUFeL
WnfxgA9DYy1Nrbiq46+hV8I=
=NlcR
-----END PGP SIGNATURE-----

Re: Fix ICE in loop unrolling

[Zdenek Dvorak]

Hi,

> fixing one of the bugs of the loop distribution, I ended up fixing a
> bug in the loop unrolling: try_unroll_loop_completely leaves the exit
> edges

that is intentional.

> and does not update correctly the dominators information,

Since it does not remove the exit edges, there is nothing to
update.

> so gcc
> ends in an ICE just after the modified code in update_ssa that uses
> this information.

This is suspicious, though.  Can you send me a testcase?

> The proposed patch uses the exact same mechanism to
> remove the unused edges as in tree_transform_and_unroll_loop.

Although I thing the bug must be elsewhere, rewriting the function that
way is a good idea, anyway:

>  
>        old_cond = COND_EXPR_COND (cond);
>        COND_EXPR_COND (cond) = dont_exit;

Please remove also the unnecessary changes of the exit condition.

Zdenek

Re: Fix ICE in loop unrolling

[Sebastian Pop]

[-- Attachment #1: Type: text/plain, Size: 616 bytes --]

On Nov 7, 2007 10:41 PM, Zdenek Dvorak <rakdver@kam.mff.cuni.cz> wrote:
> > The proposed patch uses the exact same mechanism to
> > remove the unused edges as in tree_transform_and_unroll_loop.
>
> Although I thing the bug must be elsewhere, rewriting the function that
> way is a good idea, anyway:
>
> >
> >        old_cond = COND_EXPR_COND (cond);
> >        COND_EXPR_COND (cond) = dont_exit;
>
> Please remove also the unnecessary changes of the exit condition.
>

Here is an update of the patch with your suggestion also implemented.
Regstrapped on amd64-linux.  Okay for trunk?

-- 
Sebastian
AMD - GNU Tools

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 835_unroll_ice.diff --]
[-- Type: text/x-patch; name=835_unroll_ice.diff, Size: 2210 bytes --]

email:sebpop@gmail.com
branch:trunk
revision:HEAD
configure:
make:
check:

Index: tree-ssa-loop-ivcanon.c
===================================================================
--- tree-ssa-loop-ivcanon.c	(revision 130095)
+++ tree-ssa-loop-ivcanon.c	(working copy)
@@ -163,7 +163,7 @@ try_unroll_loop_completely (struct loop 
 			    enum unroll_level ul)
 {
   unsigned HOST_WIDE_INT n_unroll, ninsns, max_unroll, unr_insns;
-  tree old_cond, cond, dont_exit, do_exit;
+  tree cond;
 
   if (loop->inner)
     return false;
@@ -207,50 +207,44 @@ try_unroll_loop_completely (struct loop 
 	}
     }
 
-  if (exit->flags & EDGE_TRUE_VALUE)
-    {
-      dont_exit = boolean_false_node;
-      do_exit = boolean_true_node;
-    }
-  else
-    {
-      dont_exit = boolean_true_node;
-      do_exit = boolean_false_node;
-    }
-  cond = last_stmt (exit->src);
-    
   if (n_unroll)
     {
       sbitmap wont_exit;
+      edge e;
+      unsigned i;
+      VEC (edge, heap) *to_remove = NULL;
 
-      old_cond = COND_EXPR_COND (cond);
-      COND_EXPR_COND (cond) = dont_exit;
-      update_stmt (cond);
       initialize_original_copy_tables ();
-
       wont_exit = sbitmap_alloc (n_unroll + 1);
       sbitmap_ones (wont_exit);
       RESET_BIT (wont_exit, 0);
 
       if (!tree_duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
 					       n_unroll, wont_exit,
-					       exit, NULL,
+					       exit, &to_remove,
 					       DLTHE_FLAG_UPDATE_FREQ
 					       | DLTHE_FLAG_COMPLETTE_PEEL))
 	{
-	  COND_EXPR_COND (cond) = old_cond;
-	  update_stmt (cond);
           free_original_copy_tables ();
 	  free (wont_exit);
 	  return false;
 	}
+
+      for (i = 0; VEC_iterate (edge, to_remove, i, e); i++)
+	{
+	  bool ok = remove_path (e);
+	  gcc_assert (ok);
+	}
+
+      VEC_free (edge, heap, to_remove);
       free (wont_exit);
       free_original_copy_tables ();
     }
-  
-  COND_EXPR_COND (cond) = do_exit;
-  update_stmt (cond);
 
+  cond = last_stmt (exit->src);
+  COND_EXPR_COND (cond) = (exit->flags & EDGE_TRUE_VALUE) ? boolean_true_node
+    : boolean_false_node;
+  update_stmt (cond);
   update_ssa (TODO_update_ssa);
 
   if (dump_file && (dump_flags & TDF_DETAILS))

Re: Fix ICE in loop unrolling

[Zdenek Dvorak]

Hi,

> Here is an update of the patch with your suggestion also implemented.
> Regstrapped on amd64-linux.  Okay for trunk?

this is OK.  It would be also nice to replace this:

> +  cond = last_stmt (exit->src);
> +  COND_EXPR_COND (cond) = (exit->flags & EDGE_TRUE_VALUE) ? boolean_true_node
> +    : boolean_false_node;
> +  update_stmt (cond);
>    update_ssa (TODO_update_ssa);

by removing the non-exit edge.  That will completely remove the loop,
though, and I am not sure whether the code using this function would to
handle this correcly (we definitely do not want to do that in stage 3,
unless there turns out to be some PR requiring it).

Zdenek