------- Additional Comments From rakdver at atrey dot karlin dot mff dot cuni
dot cz 2005-01-02 20:56 -------
Subject: Re: [4.0 regression] Endless loop compiling simple file: Bug in
tree-scalar-evolution.c (instantiate_parameters_1)?
> (In reply to comment #5)
> > Caused by an exponential time complexity of instantiate_parameters.
> > I am working on a patch.
>
> The following patch solves the exponential time complexity.
not really (well, maybe in this particular case, but not in general).
Your patch definitely helps (and you should submit it anyway), but
yhe problem is that even with your patch it may happen that
instantiate_parameters is called recursively several times for one
ssa name if the expression contains it several times, and if this
happens for several expressions in a row, you get the exponential
complexity. I am just testing the patch below that caches the results
to avoid this problem.
Index: tree-scalar-evolution.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-scalar-evolution.c,v
retrieving revision 2.14
diff -c -3 -p -r2.14 tree-scalar-evolution.c
*** tree-scalar-evolution.c 31 Dec 2004 18:03:28 -0000 2.14
--- tree-scalar-evolution.c 2 Jan 2005 20:31:01 -0000
*************** analyze_scalar_evolution_in_loop (struct
*** 1888,1906 ****
}
}
/* Analyze all the parameters of the chrec that were left under a symbolic
form,
with respect to LOOP. CHREC is the chrec to instantiate. If
ALLOW_SUPERLOOP_CHRECS is true, replacing loop invariants with
! outer loop chrecs is done. */
static tree
instantiate_parameters_1 (struct loop *loop, tree chrec,
! bool allow_superloop_chrecs)
{
tree res, op0, op1, op2;
basic_block def_bb;
struct loop *def_loop;
!
if (chrec == NULL_TREE
|| automatically_generated_chrec_p (chrec))
return chrec;
--- 1888,1942 ----
}
}
+ /* Returns instantiated value for VERSION in CACHE. */
+
+ static tree
+ get_instantiated_value (htab_t cache, tree version)
+ {
+ struct scev_info_str *info, pattern;
+
+ pattern.var = version;
+ info = htab_find (cache, &pattern);
+
+ if (info)
+ return info->chrec;
+ else
+ return NULL_TREE;
+ }
+
+ /* Sets instantiated value for VERSION to VAL in CACHE. */
+
+ static void
+ set_instantiated_value (htab_t cache, tree version, tree val)
+ {
+ struct scev_info_str *info, pattern;
+ PTR *slot;
+
+ pattern.var = version;
+ slot = htab_find_slot (cache, &pattern, INSERT);
+
+ if (*slot)
+ info = *slot;
+ else
+ info = *slot = new_scev_info_str (version);
+ info->chrec = val;
+ }
+
/* Analyze all the parameters of the chrec that were left under a symbolic
form,
with respect to LOOP. CHREC is the chrec to instantiate. If
ALLOW_SUPERLOOP_CHRECS is true, replacing loop invariants with
! outer loop chrecs is done. CACHE is the cache of already instantiated
! values. */
static tree
instantiate_parameters_1 (struct loop *loop, tree chrec,
! bool allow_superloop_chrecs,
! htab_t cache)
{
tree res, op0, op1, op2;
basic_block def_bb;
struct loop *def_loop;
!
if (chrec == NULL_TREE
|| automatically_generated_chrec_p (chrec))
return chrec;
*************** instantiate_parameters_1 (struct loop *l
*** 1920,1960 ****
&& !flow_bb_inside_loop_p (loop, def_bb)))
return chrec;
! /* Don't instantiate the SSA_NAME if it is in a mixer
structure. This is used for avoiding the instantiation of
recursively defined functions, such as:
| a_2 -> {0, +, 1, +, a_2}_1 */
!
if (bitmap_bit_p (already_instantiated, SSA_NAME_VERSION (chrec)))
! {
! if (!flow_bb_inside_loop_p (loop, def_bb))
! {
! /* We may keep the loop invariant in symbolic form. */
! return chrec;
! }
! else
! {
! /* Something with unknown behavior in LOOP. */
! return chrec_dont_know;
! }
! }
def_loop = find_common_loop (loop, def_bb->loop_father);
/* If the analysis yields a parametric chrec, instantiate the
! result again. Avoid the cyclic instantiation in mixers. */
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);
bitmap_clear_bit (already_instantiated, SSA_NAME_VERSION (chrec));
return res;
case POLYNOMIAL_CHREC:
op0 = instantiate_parameters_1 (loop, CHREC_LEFT (chrec),
! allow_superloop_chrecs);
op1 = instantiate_parameters_1 (loop, CHREC_RIGHT (chrec),
! allow_superloop_chrecs);
if (CHREC_LEFT (chrec) != op0
|| CHREC_RIGHT (chrec) != op1)
chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1);
--- 1956,2007 ----
&& !flow_bb_inside_loop_p (loop, def_bb)))
return chrec;
! /* We cache the value of instantiated variable to avoid exponential
! time complexity due to reevaluations. We also store the convenient
! value in the cache in order to prevent infinite recursion -- we do
! not want to instantiate the SSA_NAME if it is in a mixer
structure. This is used for avoiding the instantiation of
recursively defined functions, such as:
| a_2 -> {0, +, 1, +, a_2}_1 */
!
! res = get_instantiated_value (cache, chrec);
! if (res)
! return res;
!
! /* Store the convenient value for chrec in the structure. If it
! is defined outside of the loop, we may just leave it in symbolic
! form, otherwise we need to admit that we do not know its behavior
! inside the loop. */
! res = !flow_bb_inside_loop_p (loop, def_bb) ? chrec : chrec_dont_know;
! set_instantiated_value (cache, chrec, res);
!
! /* To make things even more complicated, instantiate_parameters_1
! calls analyze_scalar_evolution that may call # of iterations
! analysis that may in turn call instantiate_parameters_1 again.
! To prevent the infinite recursion, keep also the bitmap of
! ssa names that are being instantiated globally. */
if (bitmap_bit_p (already_instantiated, SSA_NAME_VERSION (chrec)))
! return res;
def_loop = find_common_loop (loop, def_bb->loop_father);
/* If the analysis yields a parametric chrec, instantiate the
! 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);
bitmap_clear_bit (already_instantiated, SSA_NAME_VERSION (chrec));
+
+ /* Store the correct value to the cache. */
+ set_instantiated_value (cache, chrec, res);
return res;
case POLYNOMIAL_CHREC:
op0 = instantiate_parameters_1 (loop, CHREC_LEFT (chrec),
! allow_superloop_chrecs, cache);
op1 = instantiate_parameters_1 (loop, CHREC_RIGHT (chrec),
! allow_superloop_chrecs, cache);
if (CHREC_LEFT (chrec) != op0
|| CHREC_RIGHT (chrec) != op1)
chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1);
*************** instantiate_parameters_1 (struct loop *l
*** 1962,1970 ****
case PLUS_EXPR:
op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
! allow_superloop_chrecs);
op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
! allow_superloop_chrecs);
if (TREE_OPERAND (chrec, 0) != op0
|| TREE_OPERAND (chrec, 1) != op1)
chrec = chrec_fold_plus (TREE_TYPE (chrec), op0, op1);
--- 2009,2017 ----
case PLUS_EXPR:
op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
! allow_superloop_chrecs, cache);
op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
! allow_superloop_chrecs, cache);
if (TREE_OPERAND (chrec, 0) != op0
|| TREE_OPERAND (chrec, 1) != op1)
chrec = chrec_fold_plus (TREE_TYPE (chrec), op0, op1);
*************** instantiate_parameters_1 (struct loop *l
*** 1972,1980 ****
case MINUS_EXPR:
op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
! allow_superloop_chrecs);
op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
! allow_superloop_chrecs);
if (TREE_OPERAND (chrec, 0) != op0
|| TREE_OPERAND (chrec, 1) != op1)
chrec = chrec_fold_minus (TREE_TYPE (chrec), op0, op1);
--- 2019,2027 ----
case MINUS_EXPR:
op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
! allow_superloop_chrecs, cache);
op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
! allow_superloop_chrecs, cache);
if (TREE_OPERAND (chrec, 0) != op0
|| TREE_OPERAND (chrec, 1) != op1)
chrec = chrec_fold_minus (TREE_TYPE (chrec), op0, op1);
*************** instantiate_parameters_1 (struct loop *l
*** 1982,1990 ****
case MULT_EXPR:
op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
! allow_superloop_chrecs);
op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
! allow_superloop_chrecs);
if (TREE_OPERAND (chrec, 0) != op0
|| TREE_OPERAND (chrec, 1) != op1)
chrec = chrec_fold_multiply (TREE_TYPE (chrec), op0, op1);
--- 2029,2037 ----
case MULT_EXPR:
op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
! allow_superloop_chrecs, cache);
op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
! allow_superloop_chrecs, cache);
if (TREE_OPERAND (chrec, 0) != op0
|| TREE_OPERAND (chrec, 1) != op1)
chrec = chrec_fold_multiply (TREE_TYPE (chrec), op0, op1);
*************** instantiate_parameters_1 (struct loop *l
*** 1994,2000 ****
case CONVERT_EXPR:
case NON_LVALUE_EXPR:
op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
! allow_superloop_chrecs);
if (op0 == chrec_dont_know)
return chrec_dont_know;
--- 2041,2047 ----
case CONVERT_EXPR:
case NON_LVALUE_EXPR:
op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
! allow_superloop_chrecs, cache);
if (op0 == chrec_dont_know)
return chrec_dont_know;
*************** instantiate_parameters_1 (struct loop *l
*** 2017,2027 ****
{
case 3:
op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
! allow_superloop_chrecs);
op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
! allow_superloop_chrecs);
op2 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 2),
! allow_superloop_chrecs);
if (op0 == chrec_dont_know
|| op1 == chrec_dont_know
|| op2 == chrec_dont_know)
--- 2064,2074 ----
{
case 3:
op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
! allow_superloop_chrecs, cache);
op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
! allow_superloop_chrecs, cache);
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)
*************** instantiate_parameters_1 (struct loop *l
*** 2037,2045 ****
case 2:
op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
! allow_superloop_chrecs);
op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
! allow_superloop_chrecs);
if (op0 == chrec_dont_know
|| op1 == chrec_dont_know)
return chrec_dont_know;
--- 2084,2092 ----
case 2:
op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
! allow_superloop_chrecs, cache);
op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
! allow_superloop_chrecs, cache);
if (op0 == chrec_dont_know
|| op1 == chrec_dont_know)
return chrec_dont_know;
*************** instantiate_parameters_1 (struct loop *l
*** 2051,2057 ****
case 1:
op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
! allow_superloop_chrecs);
if (op0 == chrec_dont_know)
return chrec_dont_know;
if (op0 == TREE_OPERAND (chrec, 0))
--- 2098,2104 ----
case 1:
op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
! allow_superloop_chrecs, cache);
if (op0 == chrec_dont_know)
return chrec_dont_know;
if (op0 == TREE_OPERAND (chrec, 0))
*************** instantiate_parameters (struct loop *loo
*** 2078,2083 ****
--- 2125,2131 ----
tree chrec)
{
tree res;
+ htab_t cache = htab_create (10, hash_scev_info, eq_scev_info,
del_scev_info);
if (dump_file && (dump_flags & TDF_DETAILS))
{
*************** instantiate_parameters (struct loop *loo
*** 2088,2094 ****
fprintf (dump_file, ")\n");
}
! res = instantiate_parameters_1 (loop, chrec, true);
if (dump_file && (dump_flags & TDF_DETAILS))
{
--- 2136,2142 ----
fprintf (dump_file, ")\n");
}
! res = instantiate_parameters_1 (loop, chrec, true, cache);
if (dump_file && (dump_flags & TDF_DETAILS))
{
*************** instantiate_parameters (struct loop *loo
*** 2096,2101 ****
--- 2144,2151 ----
print_generic_expr (dump_file, res, 0);
fprintf (dump_file, "))\n");
}
+
+ htab_delete (cache);
return res;
}
*************** instantiate_parameters (struct loop *loo
*** 2106,2112 ****
static tree
resolve_mixers (struct loop *loop, tree chrec)
{
! return instantiate_parameters_1 (loop, chrec, false);
}
/* Entry point for the analysis of the number of iterations pass.
--- 2156,2165 ----
static tree
resolve_mixers (struct loop *loop, tree chrec)
{
! htab_t cache = htab_create (10, hash_scev_info, eq_scev_info,
del_scev_info);
! tree ret = instantiate_parameters_1 (loop, chrec, false, cache);
! htab_delete (cache);
! return ret;
}
/* Entry point for the analysis of the number of iterations pass.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19224
