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).
