From 15a951ca6939db302ac188180743cc64651c449d Mon Sep 17 00:00:00 2001 From: rakdver Date: Sun, 9 Jan 2005 08:22:10 +0000 Subject: [PATCH] PR tree-optimization/19224 * tree-scalar-evolution.c (get_instantiated_value, set_instantiated_value): New functions. (instantiate_parameters_1): Cache the results. (instantiate_parameters, resolve_mixers): Initialize and free the cache. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@93106 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/ChangeLog | 9 ++++ gcc/tree-scalar-evolution.c | 125 +++++++++++++++++++++++++++++++------------- 2 files changed, 98 insertions(+), 36 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index d4395a0..5f6b14b 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,12 @@ +2005-01-09 Zdenek Dvorak + + PR tree-optimization/19224 + * tree-scalar-evolution.c (get_instantiated_value, + set_instantiated_value): New functions. + (instantiate_parameters_1): Cache the results. + (instantiate_parameters, resolve_mixers): Initialize and free + the cache. + 2005-01-08 David Edelsohn * config/i386/i386.md (addhi_4): Correct reference in comment. diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c index dd4ea0b..1ffeb0b 100644 --- a/gcc/tree-scalar-evolution.c +++ b/gcc/tree-scalar-evolution.c @@ -1888,19 +1888,55 @@ analyze_scalar_evolution_in_loop (struct loop *wrto_loop, struct loop *use_loop, } } +/* 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; @@ -1920,41 +1956,52 @@ instantiate_parameters_1 (struct loop *loop, tree 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); @@ -1962,9 +2009,9 @@ instantiate_parameters_1 (struct loop *loop, tree chrec, 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); @@ -1972,9 +2019,9 @@ instantiate_parameters_1 (struct loop *loop, tree chrec, 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); @@ -1982,9 +2029,9 @@ instantiate_parameters_1 (struct loop *loop, tree chrec, 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); @@ -1994,7 +2041,7 @@ instantiate_parameters_1 (struct loop *loop, tree chrec, 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; @@ -2017,11 +2064,11 @@ instantiate_parameters_1 (struct loop *loop, tree chrec, { 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) @@ -2037,9 +2084,9 @@ instantiate_parameters_1 (struct loop *loop, tree chrec, 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; @@ -2051,7 +2098,7 @@ instantiate_parameters_1 (struct loop *loop, tree chrec, 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)) @@ -2078,6 +2125,7 @@ instantiate_parameters (struct loop *loop, 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)) { @@ -2088,7 +2136,7 @@ instantiate_parameters (struct loop *loop, 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)) { @@ -2096,6 +2144,8 @@ instantiate_parameters (struct loop *loop, print_generic_expr (dump_file, res, 0); fprintf (dump_file, "))\n"); } + + htab_delete (cache); return res; } @@ -2106,7 +2156,10 @@ instantiate_parameters (struct loop *loop, 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. -- 2.7.4