This is the mail archive of the
gcc-bugs@gcc.gnu.org
mailing list for the GCC project.
[Bug tree-optimization/18595] [4.0/4.1 Regression] IV-OPTS is O(N^3)
- From: "sebastian dot pop at cri dot ensmp dot fr" <gcc-bugzilla at gcc dot gnu dot org>
- To: gcc-bugs at gcc dot gnu dot org
- Date: 3 Nov 2005 20:10:55 -0000
- Subject: [Bug tree-optimization/18595] [4.0/4.1 Regression] IV-OPTS is O(N^3)
- References: <bug-18595-6528@http.gcc.gnu.org/bugzilla/>
- Reply-to: gcc-bugzilla at gcc dot gnu dot org
------- Comment #59 from sebastian dot pop at cri dot ensmp dot fr 2005-11-03 20:10 -------
Subject: Re: [4.0/4.1 Regression] IV-OPTS is O(N^3)
Here is a first patch that uses PARAM_SCEV_MAX_EXPR_SIZE for limiting
the size of expressions that we want to handle. I will send it to
gcc-patches once it bootstraps, etc.
time ./gcc/cc1 -O2 ~/ex/pr18595_100.c
tree loop bounds : 0.51 (17%) usr 0.03 (23%) sys 0.53 (17%) wall
32717 kB (29%) ggc
tree iv optimization : 1.23 (41%) usr 0.06 (46%) sys 1.29 (40%) wall
64971 kB (58%) ggc
real 0m3.995s
user 0m3.015s
sys 0m0.147s
time ./gcc/cc1 -O2 ~/ex/pr18595_200.c
tree loop bounds : 2.75 (23%) usr 0.05 (13%) sys 2.80 (22%) wall
72775 kB (22%) ggc
tree iv optimization : 3.74 (31%) usr 0.20 (51%) sys 4.30 (33%) wall
210289 kB (64%) ggc
real 0m13.316s
user 0m12.163s
sys 0m0.423s
time ./gcc/cc1 -fno-tree-pre -O2 ~/ex/pr18595_300.c
tree loop bounds : 0.16 ( 3%) usr 0.00 ( 0%) sys 0.15 ( 3%) wall
508 kB ( 1%) ggc
tree iv optimization : 2.26 (47%) usr 0.08 (62%) sys 2.33 (46%) wall
74743 kB (84%) ggc
real 0m6.287s
user 0m4.849s
sys 0m0.142s
time ./gcc/cc1 -fno-tree-pre -O2 ~/ex/pr18595_1000.c
tree loop bounds : 2.92 ( 4%) usr 0.00 ( 0%) sys 2.92 ( 4%) wall
913 kB ( 0%) ggc
tree iv optimization : 37.78 (54%) usr 0.91 (65%) sys 41.15 (52%) wall
786700 kB (93%) ggc
real 1m19.611s
user 1m10.288s
sys 0m1.403s
Index: tree-scalar-evolution.c
===================================================================
--- tree-scalar-evolution.c (revision 106440)
+++ tree-scalar-evolution.c (working copy)
@@ -1982,7 +1982,8 @@ loop_closed_phi_def (tree var)
/* Analyze all the parameters of the chrec that were left under a symbolic
form,
with respect to LOOP. CHREC is the chrec to instantiate. CACHE is the
cache
of already instantiated values. FLAGS modify the way chrecs are
- instantiated. */
+ instantiated. SIZE_EXPR is used for computing the size of the expression
to
+ be instantiated, and to stop if it exceeds some limit. */
/* Values for FLAGS. */
enum
@@ -1995,12 +1996,17 @@ enum
};
static tree
-instantiate_parameters_1 (struct loop *loop, tree chrec, int flags, htab_t
cache)
+instantiate_parameters_1 (struct loop *loop, tree chrec, int flags, htab_t
cache,
+ int size_expr)
{
tree res, op0, op1, op2;
basic_block def_bb;
struct loop *def_loop;
+ /* Give up if the path is longer than the MAX that we allow. */
+ if (size_expr++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
+ return chrec_dont_know;
+
if (automatically_generated_chrec_p (chrec)
|| is_gimple_min_invariant (chrec))
return chrec;
@@ -2068,7 +2074,7 @@ instantiate_parameters_1 (struct loop *l
}
else if (res != chrec_dont_know)
- res = instantiate_parameters_1 (loop, res, flags, cache);
+ res = instantiate_parameters_1 (loop, res, flags, cache, size_expr);
bitmap_clear_bit (already_instantiated, SSA_NAME_VERSION (chrec));
@@ -2078,12 +2084,12 @@ instantiate_parameters_1 (struct loop *l
case POLYNOMIAL_CHREC:
op0 = instantiate_parameters_1 (loop, CHREC_LEFT (chrec),
- flags, cache);
+ flags, cache, size_expr);
if (op0 == chrec_dont_know)
return chrec_dont_know;
op1 = instantiate_parameters_1 (loop, CHREC_RIGHT (chrec),
- flags, cache);
+ flags, cache, size_expr);
if (op1 == chrec_dont_know)
return chrec_dont_know;
@@ -2094,12 +2100,12 @@ instantiate_parameters_1 (struct loop *l
case PLUS_EXPR:
op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
- flags, cache);
+ flags, cache, size_expr);
if (op0 == chrec_dont_know)
return chrec_dont_know;
op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
- flags, cache);
+ flags, cache, size_expr);
if (op1 == chrec_dont_know)
return chrec_dont_know;
@@ -2110,12 +2116,12 @@ instantiate_parameters_1 (struct loop *l
case MINUS_EXPR:
op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
- flags, cache);
+ flags, cache, size_expr);
if (op0 == chrec_dont_know)
return chrec_dont_know;
op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
- flags, cache);
+ flags, cache, size_expr);
if (op1 == chrec_dont_know)
return chrec_dont_know;
@@ -2126,12 +2132,12 @@ instantiate_parameters_1 (struct loop *l
case MULT_EXPR:
op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
- flags, cache);
+ flags, cache, size_expr);
if (op0 == chrec_dont_know)
return chrec_dont_know;
op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
- flags, cache);
+ flags, cache, size_expr);
if (op1 == chrec_dont_know)
return chrec_dont_know;
@@ -2144,7 +2150,7 @@ instantiate_parameters_1 (struct loop *l
case CONVERT_EXPR:
case NON_LVALUE_EXPR:
op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
- flags, cache);
+ flags, cache, size_expr);
if (op0 == chrec_dont_know)
return chrec_dont_know;
@@ -2174,17 +2180,17 @@ instantiate_parameters_1 (struct loop *l
{
case 3:
op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
- flags, cache);
+ flags, cache, size_expr);
if (op0 == chrec_dont_know)
return chrec_dont_know;
op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
- flags, cache);
+ flags, cache, size_expr);
if (op1 == chrec_dont_know)
return chrec_dont_know;
op2 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 2),
- flags, cache);
+ flags, cache, size_expr);
if (op2 == chrec_dont_know)
return chrec_dont_know;
@@ -2198,12 +2204,12 @@ instantiate_parameters_1 (struct loop *l
case 2:
op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
- flags, cache);
+ flags, cache, size_expr);
if (op0 == chrec_dont_know)
return chrec_dont_know;
op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
- flags, cache);
+ flags, cache, size_expr);
if (op1 == chrec_dont_know)
return chrec_dont_know;
@@ -2214,7 +2220,7 @@ instantiate_parameters_1 (struct loop *l
case 1:
op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
- flags, cache);
+ flags, cache, size_expr);
if (op0 == chrec_dont_know)
return chrec_dont_know;
if (op0 == TREE_OPERAND (chrec, 0))
@@ -2252,7 +2258,8 @@ instantiate_parameters (struct loop *loo
fprintf (dump_file, ")\n");
}
- res = instantiate_parameters_1 (loop, chrec, INSERT_SUPERLOOP_CHRECS,
cache);
+ res = instantiate_parameters_1 (loop, chrec, INSERT_SUPERLOOP_CHRECS, cache,
+ 0);
if (dump_file && (dump_flags & TDF_DETAILS))
{
@@ -2275,7 +2282,7 @@ 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, FOLD_CONVERSIONS, cache);
+ tree ret = instantiate_parameters_1 (loop, chrec, FOLD_CONVERSIONS, cache,
0);
htab_delete (cache);
return ret;
}
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18595