This is the mail archive of the
gcc-bugs@gcc.gnu.org
mailing list for the GCC project.
[Bug tree-optimization/18595] [4.0 Regression] IV-OPTS is O(N^3)
- From: "steven at gcc dot gnu dot org" <gcc-bugzilla at gcc dot gnu dot org>
- To: gcc-bugs at gcc dot gnu dot org
- Date: 23 Jan 2005 14:22:19 -0000
- Subject: [Bug tree-optimization/18595] [4.0 Regression] IV-OPTS is O(N^3)
- References: <20041121145949.18595.pinskia@gcc.gnu.org>
- Reply-to: gcc-bugzilla at gcc dot gnu dot org
------- Additional Comments From steven at gcc dot gnu dot org 2005-01-23 14:22 -------
More profile data:
-----------------------------------------------
0.00 187.04 1/1 execute_pass_list [6]
[7] 76.5 0.00 187.04 1 tree_ssa_iv_optimize [7]
2.48 184.56 200/200 tree_ssa_iv_optimize_loop [8]
0.00 0.00 1/201 free_loop_data [349]
0.00 0.00 2/30137 bitmap_obstack_free [178]
0.00 0.00 201/7042572 xcalloc [127]
0.00 0.00 3/2369 varray_init [1063]
0.00 0.00 2/36950 bitmap_obstack_alloc [794]
-----------------------------------------------
2.48 184.56 200/200 tree_ssa_iv_optimize [7]
[8] 76.5 2.48 184.56 200 tree_ssa_iv_optimize_loop [8]
30.61 134.21 309011/311017 simple_iv <cycle 2> [35]
6.45 9.73 3085512/3085512 find_interesting_uses_stmt
[25]
0.04 1.03 200/202 scev_reset [93]
0.00 0.76 200/200 determine_use_iv_costs [107]
0.00 0.50 200/200 rewrite_uses [142]
0.00 0.35 200/202 loop_commit_inserts [181]
0.11 0.11 20100/20100 find_interesting_uses_cond
[241]
0.02 0.09 200/311017 number_of_iterations_exit
<cycle 2> [41]
0.06 0.04 200/201 free_loop_data [349]
0.00 0.09 200/200 create_new_ivs [360]
0.00 0.08 200/401 get_loop_body_in_dom_order
[274]
0.00 0.06 200/2601 get_loop_body [111]
0.05 0.00 200/200 remove_unused_ivs [440]
0.02 0.03 19703/99904
find_interesting_uses_outer_or_nonlin [223]
0.00 0.04 2004/2804 add_candidate [413]
0.00 0.02 200/200 find_optimal_iv_set [609]
0.00 0.02 20507/40407 set_iv [503]
0.00 0.02 800/800 add_iv_value_candidates [689]
0.01 0.01 80200/26291603 flow_bb_inside_loop_p [44]
0.01 0.00 800/30137 bitmap_obstack_free [178]
0.00 0.00 1006/5012 force_var_cost [590]
0.00 0.00 200/200 iv_ca_free [1067]
0.00 0.00 201/3005 add_candidate_1 [530]
0.00 0.00 20708/370258 zero_p [517]
0.00 0.00 1399/3525413 get_iv [69]
0.00 0.00 402/12009984 fold_convert [17]
0.00 0.00 1198/3329551 is_gimple_reg [71]
0.00 0.00 1202/40175413 build_int_cst_wide [26]
0.00 0.00 200/200 single_dom_exit [1344]
0.00 0.00 402/132285 find_edge [436]
0.00 0.00 1003/8376514 bitmap_set_bit [92]
0.00 0.00 20507/20507 contains_abnormal_ssa_name_p
[1427]
0.00 0.00 201/57945 int_cst_value [804]
0.00 0.00 1202/22889750 build_int_cst [141]
0.00 0.00 1006/5034 add_cost [1463]
0.00 0.00 1007/22165 cst_and_fits_in_hwi [1748]
0.00 0.00 402/1401 loop_latch_edge [2001]
0.00 0.00 201/1597 loop_preheader_edge [1984]
-----------------------------------------------
[9] 67.8 30.81 135.08 311017+24191806 <cycle 2 as a whole> [9]
13.18 43.06 3133403+18788021 instantiate_parameters_1
<cycle 2> [11]
5.21 44.15 9695984 analyze_scalar_evolution_1
<cycle 2> [12]
0.22 20.27 703698 interpret_rhs_modify_expr
<cycle 2> [22]
2.89 7.22 9695984 analyze_scalar_evolution
<cycle 2> [32]
0.57 6.74 313469+81390 follow_ssa_edge_in_rhs <cycle
2> [38]
6.69 0.56 415264+1352605 follow_ssa_edge <cycle 2>
[39]
0.22 4.74 21906 number_of_iterations_exit
<cycle 2> [41]
0.05 1.16 30495 number_of_iterations_in_loop
<cycle 2> [86]
0.04 0.07 43784 instantiate_parameters <cycle
2> [347]
0.05 0.01 65718
simplify_using_outer_evolutions <cycle 2> [441]
0.05 0.00 30295
compute_overall_effect_of_inner_loop <cycle 2> [459]
-----------------------------------------------
22088230 chrec_convert [10]
0.95 4.12 101392/1139473 instantiate_parameters_1
<cycle 2> [11]
1.23 5.36 131992/1139473 follow_ssa_edge_in_rhs <cycle
2> [38]
3.78 16.43 404782/1139473 interpret_rhs_modify_expr
<cycle 2> [22]
4.68 20.35 501307/1139473 analyze_scalar_evolution_1
<cycle 2> [12]
[10] 23.3 10.64 46.26 1139473+22088230 chrec_convert [10]
3.01 17.81 11575896/12009984 fold_convert [17]
4.15 13.69 10684608/22863854 build3_stat [13]
2.97 1.31 11044115/40175413 build_int_cst_wide [26]
0.76 0.94 340478/806987 fold <cycle 7> [47]
1.37 0.00 23227703/23318505 chrec_type [77]
0.25 0.00 11044115/22889750 build_int_cst [141]
22088230 chrec_convert [10]
-----------------------------------------------
18788021 instantiate_parameters_1
<cycle 2> [11]
43784 instantiate_parameters <cycle
2> [347]
3089619 simple_iv <cycle 2> [35]
[11] 23.0 13.18 43.06 3133403+18788021 instantiate_parameters_1 <cycle
2> [11]
1.28 8.71 11465180/11465180 set_instantiated_value [33]
2.25 7.43 5793593/22863854 build3_stat [13]
0.85 5.09 104374/326865 chrec_fold_plus_1 [24]
0.95 4.12 101392/1139473 chrec_convert [10]
1.51 0.67 5628417/40175413 build_int_cst_wide [26]
1.92 0.03 5773179/5820723 htab_find_with_hash [67]
1.84 0.00 21921424/29473273 is_gimple_min_invariant
[56]
0.82 0.70 8874753/26291603 flow_bb_inside_loop_p [44]
0.90 0.28 5773179/5784085 htab_find [88]
1.14 0.00 5732590/6202135 bitmap_clear_bit [85]
0.85 0.00 5732590/5756097 find_common_loop [104]
0.78 0.00 5732590/8376514 bitmap_set_bit [92]
0.67 0.00 5732590/10054625 bitmap_bit_p [89]
0.13 0.00 5628417/22889750 build_int_cst [141]
0.05 0.06 21892/806987 fold <cycle 7> [47]
0.01 0.03 21892/609615 build2_stat [98]
0.01 0.01 82482/3352077 chrec_fold_plus [122]
0.00 0.00 21892/2867796 chrec_fold_minus [154]
5732590 analyze_scalar_evolution
<cycle 2> [32]
18788021 instantiate_parameters_1
<cycle 2> [11]
-----------------------------------------------
9695984 analyze_scalar_evolution
<cycle 2> [32]
[12] 20.2 5.21 44.15 9695984 analyze_scalar_evolution_1 <cycle
2> [12]
4.68 20.35 501307/1139473 chrec_convert [10]
1.65 9.88 202391/326865 chrec_fold_plus_1 [24]
0.45 4.61 6482915/15734611 find_var_scev_info [29]
0.88 0.75 9534492/26291603 flow_bb_inside_loop_p [44]
0.17 0.55 428920/22863854 build3_stat [13]
0.05 0.06 21785/806987 fold <cycle 7> [47]
0.01 0.03 202389/3352077 chrec_fold_plus [122]
0.02 0.00 70699/70699 chrec_merge [642]
0.01 0.00 70699/1575094 loop_phi_node_p [202]
0.00 0.00 2/2867796 chrec_fold_minus [154]
703698 interpret_rhs_modify_expr
<cycle 2> [22]
70699 follow_ssa_edge <cycle 2>
[39]
-----------------------------------------------
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18595