[Bug middle-end/53852] -ftree-loop-linear: large compile time / memory usage

["matz at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53852

--- Comment #2 from Michael Matz <matz at gcc dot gnu.org> 2012-07-04 12:11:10 UTC ---
ISL generally has speed problems.  For instance graphite/interchange-8.c
needs quite long to compile (well, several seconds), and _all_ of the runtime
is basically in malloc/free/copy activity of isl_int's.  It does 10 million
calls to malloc/free, 51 million to gmpz_set, 15 million to gmpz_addmul,
9 million to gmpz_mul, 51 million gmpn_copi, and so on.

Huge causes for this excessive gmp activity is compute_deps ->
isl_union_map_compute_flow.  Three calls of the latter are responsible
for 76% compile time, and it's all in gmp activity.  It's then
doing 16x isl_access_info_compute_flow, 210x isl_map_partial_lexmax,
307x isl_map_apply_range and isl_map_intersect, which do 10000x 
isl_basic_map_intersect and 7400x isl_basic_map_apply_range.  That causes
25000x isl_basic_map_simplify and 61000x isl_basic_map_alloc_space.
That results in 82000x isl_blk_alloc, which ultimately does the excessive
number of malloc and gmp_init calls.  And it results in several million
calls to the simplify primitives
(isl_seq_elim->isl_seq_combine->gmp_addmul/mul/set, isl_seq_copy, and
isl_seq_abs_min_non_zero).