This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH] Fix quadraticness in simplify_using_initial_condition
- From: Richard Guenther <rguenther at suse dot de>
- To: gcc-patches at gcc dot gnu dot org
- Cc: Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>
- Date: Thu, 15 Jun 2006 17:24:14 +0200 (CEST)
- Subject: [PATCH] Fix quadraticness in simplify_using_initial_condition
This fixes quadratic behavior in compile-time and memory usage in
the number of BBs and loops for an artificial testcase like
#define ONE_LOOP \
{ int i, j; \
for (i = 0; i < i_last; i++) \
for (j = 0; j < j_last; j++) { \
array[i][j] = barray[i][j] * barray[j][i]; \
sum += array[j][i]; \
} \
i_last = function(sum, array, &j_last); \
}
#define L2 \
ONE_LOOP \
ONE_LOOP
#define L16 L2 L2 L2 L2 L2 L2 L2 L2
#define L128 L16 L16 L16 L16 L16 L16 L16 L16
#define L1024 L128 L128 L128 L128 L128 L128 L128 L128
extern int function (int, int **, int *);
int f(int i_last, int j_last, int **array, int **barray)
{
int sum = 0;
L1024
return sum + i_last + j_last;
}
Bootstrapped and tested on x86_64-unknown-linux-gnu.
Ok for mainline?
Thanks,
Richard.
:ADDPATCH loop:
2006-06-15 Richrad Guenther <rguenther@suse.de>
* tree-ssa-loop-niter.c (simplify_using_initial_conditions):
Limit iteration over the dominators.
Index: tree-ssa-loop-niter.c
===================================================================
*** tree-ssa-loop-niter.c (revision 114674)
--- tree-ssa-loop-niter.c (working copy)
*************** simplify_using_initial_conditions (struc
*** 899,910 ****
edge e;
basic_block bb;
tree exp, cond;
if (TREE_CODE (expr) == INTEGER_CST)
return expr;
for (bb = loop->header;
! bb != ENTRY_BLOCK_PTR;
bb = get_immediate_dominator (CDI_DOMINATORS, bb))
{
if (!single_pred_p (bb))
--- 899,914 ----
edge e;
basic_block bb;
tree exp, cond;
+ int cnt = 0;
if (TREE_CODE (expr) == INTEGER_CST)
return expr;
+ /* Limit walking the dominators to avoid quadraticness in
+ the number of BBs times the number of loops in degenerate
+ cases. */
for (bb = loop->header;
! bb != ENTRY_BLOCK_PTR && cnt < 8;
bb = get_immediate_dominator (CDI_DOMINATORS, bb))
{
if (!single_pred_p (bb))
*************** simplify_using_initial_conditions (struc
*** 926,931 ****
--- 930,936 ----
cond);
expr = exp;
+ ++cnt;
}
return expr;