[Bug tree-optimization/18595] [4.0 Regression] IV-OPTS is O(N^3)
sebastian dot pop at cri dot ensmp dot fr
gcc-bugzilla@gcc.gnu.org
Tue Jan 25 12:03:00 GMT 2005
------- Additional Comments From sebastian dot pop at cri dot ensmp dot fr 2005-01-25 12:03 -------
Subject: Re: [4.0 Regression] IV-OPTS is O(N^3)
rakdver at atrey dot karlin dot mff dot cuni dot cz wrote:
>
> ------- Additional Comments From rakdver at atrey dot karlin dot mff dot cuni dot cz 2005-01-25 11:14 -------
> Subject: Re: [4.0 Regression] IV-OPTS is O(N^3)
>
> > rakdver at atrey dot karlin dot mff dot cuni dot cz wrote:
> > > Adding the instantiation cache was compile time neutral on normal code,
> > > so I don't think the effect on scev cost is significant.
> > >
> >
> > How that? You end up querying and caching an evolution for every
> > instantiation of an SSA_NAME!
>
> which is pretty cheap (constant time operation); note that we do an
> equivalent lookup in the analyze_scalar_evolution call in any case, also
> without causing any compile time problems. I haven't measured any slowdown on
> normal testcases.
>
> > I will quantify the number of queries wrt the number of times this
> > information is useful. I think that with my patch, the instantiation
> > cache information is used zero times on a bootstrap.
>
> I don't think so. Please come up with some numbers, otherwise this
> discussion is pointless.
>
during a bootstrap:
instantiation cache queries: 1146452
instantiation cache uses: 247452 of which 143977 were scev_not_known,
the other were SSA_NAMEs.
this was counted with a grep|wc with the following patch:
Index: tree-scalar-evolution.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-scalar-evolution.c,v
retrieving revision 2.16
diff -d -u -p -r2.16 tree-scalar-evolution.c
--- tree-scalar-evolution.c 18 Jan 2005 11:36:26 -0000 2.16
+++ tree-scalar-evolution.c 25 Jan 2005 12:00:57 -0000
@@ -1898,8 +1898,15 @@ get_instantiated_value (htab_t cache, tr
pattern.var = version;
info = htab_find (cache, &pattern);
+ fprintf (stdout, "IC_query \n");
+
if (info)
- return info->chrec;
+ {
+ fprintf (stdout, "IC_used_once \n");
+ print_generic_expr (stdout, info->chrec, 0);
+ fprintf (stdout, "\n");
+ return info->chrec;
+ }
else
return NULL_TREE;
}
@@ -1915,6 +1922,8 @@ set_instantiated_value (htab_t cache, tr
pattern.var = version;
slot = htab_find_slot (cache, &pattern, INSERT);
+ fprintf (stdout, "IC_query \n");
+
if (*slot)
info = *slot;
else
@@ -1990,7 +1999,8 @@ instantiate_parameters_1 (struct loop *l
result again. */
bitmap_set_bit (already_instantiated, SSA_NAME_VERSION (chrec));
res = analyze_scalar_evolution (def_loop, chrec);
- res = instantiate_parameters_1 (loop, res, allow_superloop_chrecs, cache);
+ if (res != chrec_dont_know)
+ res = instantiate_parameters_1 (loop, res, allow_superloop_chrecs, cache);
bitmap_clear_bit (already_instantiated, SSA_NAME_VERSION (chrec));
/* Store the correct value to the cache. */
@@ -2000,8 +2010,14 @@ instantiate_parameters_1 (struct loop *l
case POLYNOMIAL_CHREC:
op0 = instantiate_parameters_1 (loop, CHREC_LEFT (chrec),
allow_superloop_chrecs, cache);
+ if (op0 == chrec_dont_know)
+ return chrec_dont_know;
+
op1 = instantiate_parameters_1 (loop, CHREC_RIGHT (chrec),
allow_superloop_chrecs, cache);
+ if (op1 == chrec_dont_know)
+ return chrec_dont_know;
+
if (CHREC_LEFT (chrec) != op0
|| CHREC_RIGHT (chrec) != op1)
chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1);
@@ -2010,8 +2026,14 @@ instantiate_parameters_1 (struct loop *l
case PLUS_EXPR:
op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
allow_superloop_chrecs, cache);
+ if (op0 == chrec_dont_know)
+ return chrec_dont_know;
+
op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
allow_superloop_chrecs, cache);
+ if (op1 == chrec_dont_know)
+ return chrec_dont_know;
+
if (TREE_OPERAND (chrec, 0) != op0
|| TREE_OPERAND (chrec, 1) != op1)
chrec = chrec_fold_plus (TREE_TYPE (chrec), op0, op1);
@@ -2020,8 +2042,14 @@ instantiate_parameters_1 (struct loop *l
case MINUS_EXPR:
op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
allow_superloop_chrecs, cache);
+ if (op0 == chrec_dont_know)
+ return chrec_dont_know;
+
op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
allow_superloop_chrecs, cache);
+ if (op1 == chrec_dont_know)
+ return chrec_dont_know;
+
if (TREE_OPERAND (chrec, 0) != op0
|| TREE_OPERAND (chrec, 1) != op1)
chrec = chrec_fold_minus (TREE_TYPE (chrec), op0, op1);
@@ -2030,8 +2058,14 @@ instantiate_parameters_1 (struct loop *l
case MULT_EXPR:
op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
allow_superloop_chrecs, cache);
+ if (op0 == chrec_dont_know)
+ return chrec_dont_know;
+
op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
allow_superloop_chrecs, cache);
+ if (op1 == chrec_dont_know)
+ return chrec_dont_know;
+
if (TREE_OPERAND (chrec, 0) != op0
|| TREE_OPERAND (chrec, 1) != op1)
chrec = chrec_fold_multiply (TREE_TYPE (chrec), op0, op1);
@@ -2065,13 +2099,17 @@ instantiate_parameters_1 (struct loop *l
case 3:
op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
allow_superloop_chrecs, cache);
+ if (op0 == chrec_dont_know)
+ return chrec_dont_know;
+
op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
allow_superloop_chrecs, cache);
+ if (op1 == chrec_dont_know)
+ return chrec_dont_know;
+
op2 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 2),
allow_superloop_chrecs, cache);
- if (op0 == chrec_dont_know
- || op1 == chrec_dont_know
- || op2 == chrec_dont_know)
+ if (op2 == chrec_dont_know)
return chrec_dont_know;
if (op0 == TREE_OPERAND (chrec, 0)
@@ -2085,10 +2123,12 @@ instantiate_parameters_1 (struct loop *l
case 2:
op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
allow_superloop_chrecs, cache);
+ if (op0 == chrec_dont_know)
+ return chrec_dont_know;
+
op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
allow_superloop_chrecs, cache);
- if (op0 == chrec_dont_know
- || op1 == chrec_dont_know)
+ if (op1 == chrec_dont_know)
return chrec_dont_know;
if (op0 == TREE_OPERAND (chrec, 0)
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18595
More information about the Gcc-bugs
mailing list