}
}
+/* 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. */
+ 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)
+ 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;
&& !flow_bb_inside_loop_p (loop, def_bb)))
return chrec;
- /* Don't instantiate the SSA_NAME if it is in a mixer
+ /* 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)))
- {
- 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;
- }
- }
+ return res;
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. */
+ 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);
+ 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);
+ allow_superloop_chrecs, cache);
op1 = instantiate_parameters_1 (loop, CHREC_RIGHT (chrec),
- allow_superloop_chrecs);
+ allow_superloop_chrecs, cache);
if (CHREC_LEFT (chrec) != op0
|| CHREC_RIGHT (chrec) != op1)
chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1);
case PLUS_EXPR:
op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
- allow_superloop_chrecs);
+ allow_superloop_chrecs, cache);
op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
- allow_superloop_chrecs);
+ allow_superloop_chrecs, cache);
if (TREE_OPERAND (chrec, 0) != op0
|| TREE_OPERAND (chrec, 1) != op1)
chrec = chrec_fold_plus (TREE_TYPE (chrec), op0, op1);
case MINUS_EXPR:
op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
- allow_superloop_chrecs);
+ allow_superloop_chrecs, cache);
op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
- allow_superloop_chrecs);
+ allow_superloop_chrecs, cache);
if (TREE_OPERAND (chrec, 0) != op0
|| TREE_OPERAND (chrec, 1) != op1)
chrec = chrec_fold_minus (TREE_TYPE (chrec), op0, op1);
case MULT_EXPR:
op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
- allow_superloop_chrecs);
+ allow_superloop_chrecs, cache);
op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
- allow_superloop_chrecs);
+ allow_superloop_chrecs, cache);
if (TREE_OPERAND (chrec, 0) != op0
|| TREE_OPERAND (chrec, 1) != op1)
chrec = chrec_fold_multiply (TREE_TYPE (chrec), op0, op1);
case CONVERT_EXPR:
case NON_LVALUE_EXPR:
op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
- allow_superloop_chrecs);
+ allow_superloop_chrecs, cache);
if (op0 == chrec_dont_know)
return chrec_dont_know;
{
case 3:
op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
- allow_superloop_chrecs);
+ allow_superloop_chrecs, cache);
op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
- allow_superloop_chrecs);
+ allow_superloop_chrecs, cache);
op2 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 2),
- allow_superloop_chrecs);
+ allow_superloop_chrecs, cache);
if (op0 == chrec_dont_know
|| op1 == chrec_dont_know
|| op2 == chrec_dont_know)
case 2:
op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
- allow_superloop_chrecs);
+ allow_superloop_chrecs, cache);
op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
- allow_superloop_chrecs);
+ allow_superloop_chrecs, cache);
if (op0 == chrec_dont_know
|| op1 == chrec_dont_know)
return chrec_dont_know;
case 1:
op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
- allow_superloop_chrecs);
+ allow_superloop_chrecs, cache);
if (op0 == chrec_dont_know)
return chrec_dont_know;
if (op0 == TREE_OPERAND (chrec, 0))
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))
{
fprintf (dump_file, ")\n");
}
- res = instantiate_parameters_1 (loop, chrec, true);
+ res = instantiate_parameters_1 (loop, chrec, true, cache);
if (dump_file && (dump_flags & TDF_DETAILS))
{
print_generic_expr (dump_file, res, 0);
fprintf (dump_file, "))\n");
}
+
+ htab_delete (cache);
return res;
}
static tree
resolve_mixers (struct loop *loop, tree chrec)
{
- return instantiate_parameters_1 (loop, chrec, false);
+ 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.
OSDN Git Service
