[PATCH] Detect loops in find_comparison_args

[Paolo Bonzini]

Il 24/07/2012 22:17, Sandra Loosemore ha scritto:
> I was looking to see what needs to be done to un-stick this previously
> submitted patch:
> 
> http://gcc.gnu.org/ml/gcc-patches/2012-05/msg01419.html
> 
> Paolo's suggestion was to re-write this to use a "tortoise-and-hare"
> algorithm to detect the circularity, rather than Andrew's solution of
> using a pointer_set to keep track of already-visited states.
> 
> Having spent a couple hours scratching my head over how to do the
> suggested re-write, I'm thinking that Andrew's proposed patch is really
> the better solution after all.  This isn't a linked list we're
> traversing, it's an iterative computation,

This doesn't really matter, because the tortoise-and-hare algorithm _is_ really about iterative computation (following a linked list uses "x = x->next" as the iterative computation).  However...

> so doing the
> tortoise-and-hare thing either requires a lot of extra recomputation
> even in the normal case where it terminates quickly, or building some
> data structures to track already-visited states.  And, if we're going to
> build data structures, why not use ones we already have a convenient
> library for?  What else are such libraries for but to consolidate common
> code and make it easier to express such idioms?  IMO, that's a
> lighter-weight solution than further complicating this code, and I feel
> much more confident that it'll squash an entire class of lurking bugs
> without introducing new ones.

... it's a lot simpler than this: I didn't notice that the check is within
a nested loop, so you cannot simply treat the outer "while" as the function
being iterated.  This indeed makes it more practical to use a pointer_set
to track the visited values.

What I'm worried about is the extra cost of malloc-ing and free-ing the
pointer set.  Perhaps you can skip the pointer set creation in the common
case where find_comparison_args does not iterate?  Something like this:

Index: cse.c
===================================================================
--- cse.c	(revisione 189837)
+++ cse.c	(copia locale)
@@ -2897,6 +2897,8 @@ find_comparison_args (enum rtx_code code
 		      enum machine_mode *pmode1, enum machine_mode *pmode2)
 {
   rtx arg1, arg2;
+  rtx x = NULL;
+  int i = 0;
 
   arg1 = *parg1, arg2 = *parg2;
 
@@ -2905,15 +2907,24 @@ find_comparison_args (enum rtx_code code
   while (arg2 == CONST0_RTX (GET_MODE (arg1)))
     {
       /* Set nonzero when we find something of interest.  */
-      rtx x = 0;
       int reverse_code = 0;
       struct table_elt *p = 0;
 
+      /* Before starting the second iteration, set up the pointer_set
+         we use to avoid loops.  Most of the time (?) we do not iterate
+         at all, and we skip creating the set.  */
+      if (++i >= 2)
+        {
+          if (!visited)
+            visited = pointer_set_create ();
+          pointer_set_insert (visited, x);
+        }
+
       /* If arg1 is a COMPARE, extract the comparison arguments from it.
 	 On machines with CC0, this is the only case that can occur, since
 	 fold_rtx will return the COMPARE or item being compared with zero
 	 when given CC0.  */
 
+      x = NULL;
       if (GET_CODE (arg1) == COMPARE && arg2 == const0_rtx)
 	x = arg1;
 
@@ -2985,10 +2996,8 @@ find_comparison_args (enum rtx_code code
 	  if (! exp_equiv_p (p->exp, p->exp, 1, false))
 	    continue;
 
-	  /* If it's the same comparison we're already looking at, skip it.  */
-	  if (COMPARISON_P (p->exp)
-	      && XEXP (p->exp, 0) == arg1
-	      && XEXP (p->exp, 1) == arg2)
+	  /* If it's a comparison we've used before, skip it.  */
+	  if (visited && pointer_set_contains (visited, p->exp))
 	    continue;
 
 	  if (GET_CODE (p->exp) == COMPARE
@@ -3061,6 +3070,11 @@ find_comparison_args (enum rtx_code code
 	}
       else if (COMPARISON_P (x))
 	code = GET_CODE (x);
+
+      /* If it's the same comparison we're already looking at, stop.  */
+      if (XEXP (x, 0) == arg1 && XEXP (x, 1) == arg2)
+        break;
+
       arg1 = XEXP (x, 0), arg2 = XEXP (x, 1);
     }
 
@@ -3068,6 +3082,8 @@ find_comparison_args (enum rtx_code code
      because fold_rtx might produce const_int, and then it's too late.  */
   *pmode1 = GET_MODE (arg1), *pmode2 = GET_MODE (arg2);
   *parg1 = fold_rtx (arg1, 0), *parg2 = fold_rtx (arg2, 0);
+  if (visited)
+    pointer_set_destroy (visited);
 
   return code;
 }

It will be more expensive in the rare case of a cycle, but that's _really_
rare if it took 20-odd years to find it.

Paolo

> Paolo, will you reconsider this?  Anyone else care to join the fray?
> 
> -Sandra
> 
>