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