1 /* Loop optimizer initialization routines and RTL loop optimization passes. 2 Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007, 2008 3 Free Software Foundation, Inc. 4 5 This file is part of GCC. 6 7 GCC is free software; you can redistribute it and/or modify it under 8 the terms of the GNU General Public License as published by the Free 9 Software Foundation; either version 3, or (at your option) any later 10 version. 11 12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13 WARRANTY; without even the implied warranty of MERCHANTABILITY or 14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15 for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with GCC; see the file COPYING3. If not see 19 <http://www.gnu.org/licenses/>. */ 20 21 #include "config.h" 22 #include "system.h" 23 #include "coretypes.h" 24 #include "tm.h" 25 #include "rtl.h" 26 #include "hard-reg-set.h" 27 #include "obstack.h" 28 #include "basic-block.h" 29 #include "cfgloop.h" 30 #include "cfglayout.h" 31 #include "tree-pass.h" 32 #include "timevar.h" 33 #include "flags.h" 34 #include "df.h" 35 #include "ggc.h" 36 37 38 /* Initialize loop structures. This is used by the tree and RTL loop 39 optimizers. FLAGS specify what properties to compute and/or ensure for 40 loops. */ 41 42 void 43 loop_optimizer_init (unsigned flags) 44 { 45 struct loops *loops; 46 47 gcc_assert (!current_loops); 48 loops = GGC_CNEW (struct loops); 49 50 /* Find the loops. */ 51 52 flow_loops_find (loops); 53 current_loops = loops; 54 55 if (flags & LOOPS_MAY_HAVE_MULTIPLE_LATCHES) 56 { 57 /* If the loops may have multiple latches, we cannot canonicalize 58 them further (and most of the loop manipulation functions will 59 not work). However, we avoid modifying cfg, which some 60 passes may want. */ 61 gcc_assert ((flags & ~(LOOPS_MAY_HAVE_MULTIPLE_LATCHES 62 | LOOPS_HAVE_RECORDED_EXITS)) == 0); 63 loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES); 64 } 65 else 66 disambiguate_loops_with_multiple_latches (); 67 68 /* Create pre-headers. */ 69 if (flags & LOOPS_HAVE_PREHEADERS) 70 { 71 int cp_flags = CP_SIMPLE_PREHEADERS; 72 73 if (flags & LOOPS_HAVE_FALLTHRU_PREHEADERS) 74 cp_flags |= CP_FALLTHRU_PREHEADERS; 75 76 create_preheaders (cp_flags); 77 } 78 79 /* Force all latches to have only single successor. */ 80 if (flags & LOOPS_HAVE_SIMPLE_LATCHES) 81 force_single_succ_latches (); 82 83 /* Mark irreducible loops. */ 84 if (flags & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS) 85 mark_irreducible_loops (); 86 87 if (flags & LOOPS_HAVE_RECORDED_EXITS) 88 record_loop_exits (); 89 90 /* Dump loops. */ 91 flow_loops_dump (dump_file, NULL, 1); 92 93 #ifdef ENABLE_CHECKING 94 verify_dominators (CDI_DOMINATORS); 95 verify_loop_structure (); 96 #endif 97 } 98 99 /* Finalize loop structures. */ 100 101 void 102 loop_optimizer_finalize (void) 103 { 104 loop_iterator li; 105 struct loop *loop; 106 basic_block bb; 107 108 gcc_assert (current_loops != NULL); 109 110 FOR_EACH_LOOP (li, loop, 0) 111 { 112 free_simple_loop_desc (loop); 113 } 114 115 /* Clean up. */ 116 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS)) 117 release_recorded_exits (); 118 flow_loops_free (current_loops); 119 ggc_free (current_loops); 120 current_loops = NULL; 121 122 FOR_ALL_BB (bb) 123 { 124 bb->loop_father = NULL; 125 } 126 127 /* Checking. */ 128 #ifdef ENABLE_CHECKING 129 /* FIXME: no point to verify flow info after bundling on ia64. Use this 130 hack for achieving this. */ 131 if (!reload_completed) 132 verify_flow_info (); 133 #endif 134 } 135 136 137 /* Gate for the RTL loop superpass. The actual passes are subpasses. 138 See passes.c for more on that. */ 139 140 static bool 141 gate_handle_loop2 (void) 142 { 143 return (optimize > 0 144 && (flag_move_loop_invariants 145 || flag_unswitch_loops 146 || flag_peel_loops 147 || flag_unroll_loops 148 #ifdef HAVE_doloop_end 149 || (flag_branch_on_count_reg && HAVE_doloop_end) 150 #endif 151 )); 152 } 153 154 struct rtl_opt_pass pass_loop2 = 155 { 156 { 157 RTL_PASS, 158 "loop2", /* name */ 159 gate_handle_loop2, /* gate */ 160 NULL, /* execute */ 161 NULL, /* sub */ 162 NULL, /* next */ 163 0, /* static_pass_number */ 164 TV_LOOP, /* tv_id */ 165 0, /* properties_required */ 166 0, /* properties_provided */ 167 0, /* properties_destroyed */ 168 0, /* todo_flags_start */ 169 TODO_dump_func | 170 TODO_ggc_collect /* todo_flags_finish */ 171 } 172 }; 173 174 175 /* Initialization of the RTL loop passes. */ 176 static unsigned int 177 rtl_loop_init (void) 178 { 179 gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT); 180 181 if (dump_file) 182 dump_flow_info (dump_file, dump_flags); 183 184 loop_optimizer_init (LOOPS_NORMAL); 185 return 0; 186 } 187 188 struct rtl_opt_pass pass_rtl_loop_init = 189 { 190 { 191 RTL_PASS, 192 "loop2_init", /* name */ 193 NULL, /* gate */ 194 rtl_loop_init, /* execute */ 195 NULL, /* sub */ 196 NULL, /* next */ 197 0, /* static_pass_number */ 198 TV_LOOP, /* tv_id */ 199 0, /* properties_required */ 200 0, /* properties_provided */ 201 0, /* properties_destroyed */ 202 0, /* todo_flags_start */ 203 TODO_dump_func | TODO_verify_rtl_sharing /* todo_flags_finish */ 204 } 205 }; 206 207 208 /* Finalization of the RTL loop passes. */ 209 210 static unsigned int 211 rtl_loop_done (void) 212 { 213 loop_optimizer_finalize (); 214 free_dominance_info (CDI_DOMINATORS); 215 216 cleanup_cfg (0); 217 if (dump_file) 218 dump_flow_info (dump_file, dump_flags); 219 220 return 0; 221 } 222 223 struct rtl_opt_pass pass_rtl_loop_done = 224 { 225 { 226 RTL_PASS, 227 "loop2_done", /* name */ 228 NULL, /* gate */ 229 rtl_loop_done, /* execute */ 230 NULL, /* sub */ 231 NULL, /* next */ 232 0, /* static_pass_number */ 233 TV_LOOP, /* tv_id */ 234 0, /* properties_required */ 235 0, /* properties_provided */ 236 0, /* properties_destroyed */ 237 0, /* todo_flags_start */ 238 TODO_dump_func | TODO_verify_rtl_sharing /* todo_flags_finish */ 239 } 240 }; 241 242 243 /* Loop invariant code motion. */ 244 static bool 245 gate_rtl_move_loop_invariants (void) 246 { 247 return flag_move_loop_invariants; 248 } 249 250 static unsigned int 251 rtl_move_loop_invariants (void) 252 { 253 if (number_of_loops () > 1) 254 move_loop_invariants (); 255 return 0; 256 } 257 258 struct rtl_opt_pass pass_rtl_move_loop_invariants = 259 { 260 { 261 RTL_PASS, 262 "loop2_invariant", /* name */ 263 gate_rtl_move_loop_invariants, /* gate */ 264 rtl_move_loop_invariants, /* execute */ 265 NULL, /* sub */ 266 NULL, /* next */ 267 0, /* static_pass_number */ 268 TV_LOOP_MOVE_INVARIANTS, /* tv_id */ 269 0, /* properties_required */ 270 0, /* properties_provided */ 271 0, /* properties_destroyed */ 272 0, /* todo_flags_start */ 273 TODO_df_verify | 274 TODO_df_finish | TODO_verify_rtl_sharing | 275 TODO_dump_func /* todo_flags_finish */ 276 } 277 }; 278 279 280 /* Loop unswitching for RTL. */ 281 static bool 282 gate_rtl_unswitch (void) 283 { 284 return flag_unswitch_loops; 285 } 286 287 static unsigned int 288 rtl_unswitch (void) 289 { 290 if (number_of_loops () > 1) 291 unswitch_loops (); 292 return 0; 293 } 294 295 struct rtl_opt_pass pass_rtl_unswitch = 296 { 297 { 298 RTL_PASS, 299 "loop2_unswitch", /* name */ 300 gate_rtl_unswitch, /* gate */ 301 rtl_unswitch, /* execute */ 302 NULL, /* sub */ 303 NULL, /* next */ 304 0, /* static_pass_number */ 305 TV_LOOP_UNSWITCH, /* tv_id */ 306 0, /* properties_required */ 307 0, /* properties_provided */ 308 0, /* properties_destroyed */ 309 0, /* todo_flags_start */ 310 TODO_dump_func | TODO_verify_rtl_sharing, /* todo_flags_finish */ 311 } 312 }; 313 314 315 /* Loop unswitching for RTL. */ 316 static bool 317 gate_rtl_unroll_and_peel_loops (void) 318 { 319 return (flag_peel_loops || flag_unroll_loops || flag_unroll_all_loops); 320 } 321 322 static unsigned int 323 rtl_unroll_and_peel_loops (void) 324 { 325 if (number_of_loops () > 1) 326 { 327 int flags = 0; 328 if (dump_file) 329 df_dump (dump_file); 330 331 if (flag_peel_loops) 332 flags |= UAP_PEEL; 333 if (flag_unroll_loops) 334 flags |= UAP_UNROLL; 335 if (flag_unroll_all_loops) 336 flags |= UAP_UNROLL_ALL; 337 338 unroll_and_peel_loops (flags); 339 } 340 return 0; 341 } 342 343 struct rtl_opt_pass pass_rtl_unroll_and_peel_loops = 344 { 345 { 346 RTL_PASS, 347 "loop2_unroll", /* name */ 348 gate_rtl_unroll_and_peel_loops, /* gate */ 349 rtl_unroll_and_peel_loops, /* execute */ 350 NULL, /* sub */ 351 NULL, /* next */ 352 0, /* static_pass_number */ 353 TV_LOOP_UNROLL, /* tv_id */ 354 0, /* properties_required */ 355 0, /* properties_provided */ 356 0, /* properties_destroyed */ 357 0, /* todo_flags_start */ 358 TODO_dump_func | TODO_verify_rtl_sharing, /* todo_flags_finish */ 359 } 360 }; 361 362 363 /* The doloop optimization. */ 364 static bool 365 gate_rtl_doloop (void) 366 { 367 #ifdef HAVE_doloop_end 368 return (flag_branch_on_count_reg && HAVE_doloop_end); 369 #else 370 return 0; 371 #endif 372 } 373 374 static unsigned int 375 rtl_doloop (void) 376 { 377 #ifdef HAVE_doloop_end 378 if (number_of_loops () > 1) 379 doloop_optimize_loops (); 380 #endif 381 return 0; 382 } 383 384 struct rtl_opt_pass pass_rtl_doloop = 385 { 386 { 387 RTL_PASS, 388 "loop2_doloop", /* name */ 389 gate_rtl_doloop, /* gate */ 390 rtl_doloop, /* execute */ 391 NULL, /* sub */ 392 NULL, /* next */ 393 0, /* static_pass_number */ 394 TV_LOOP_DOLOOP, /* tv_id */ 395 0, /* properties_required */ 396 0, /* properties_provided */ 397 0, /* properties_destroyed */ 398 0, /* todo_flags_start */ 399 TODO_dump_func | TODO_verify_rtl_sharing /* todo_flags_finish */ 400 } 401 }; 402 403