1 /* Loop optimizer initialization routines and RTL loop optimization passes. 2 Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2010 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_alloc_cleared_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 128 129 /* Gate for the RTL loop superpass. The actual passes are subpasses. 130 See passes.c for more on that. */ 131 132 static bool 133 gate_handle_loop2 (void) 134 { 135 return (optimize > 0 136 && (flag_move_loop_invariants 137 || flag_unswitch_loops 138 || flag_peel_loops 139 || flag_unroll_loops 140 #ifdef HAVE_doloop_end 141 || (flag_branch_on_count_reg && HAVE_doloop_end) 142 #endif 143 )); 144 } 145 146 struct rtl_opt_pass pass_loop2 = 147 { 148 { 149 RTL_PASS, 150 "loop2", /* name */ 151 gate_handle_loop2, /* gate */ 152 NULL, /* execute */ 153 NULL, /* sub */ 154 NULL, /* next */ 155 0, /* static_pass_number */ 156 TV_LOOP, /* tv_id */ 157 0, /* properties_required */ 158 0, /* properties_provided */ 159 0, /* properties_destroyed */ 160 0, /* todo_flags_start */ 161 TODO_ggc_collect /* todo_flags_finish */ 162 } 163 }; 164 165 166 /* Initialization of the RTL loop passes. */ 167 static unsigned int 168 rtl_loop_init (void) 169 { 170 gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT); 171 172 if (dump_file) 173 dump_flow_info (dump_file, dump_flags); 174 175 loop_optimizer_init (LOOPS_NORMAL); 176 return 0; 177 } 178 179 struct rtl_opt_pass pass_rtl_loop_init = 180 { 181 { 182 RTL_PASS, 183 "loop2_init", /* name */ 184 NULL, /* gate */ 185 rtl_loop_init, /* execute */ 186 NULL, /* sub */ 187 NULL, /* next */ 188 0, /* static_pass_number */ 189 TV_LOOP, /* tv_id */ 190 0, /* properties_required */ 191 0, /* properties_provided */ 192 0, /* properties_destroyed */ 193 0, /* todo_flags_start */ 194 TODO_verify_rtl_sharing /* todo_flags_finish */ 195 } 196 }; 197 198 199 /* Finalization of the RTL loop passes. */ 200 201 static unsigned int 202 rtl_loop_done (void) 203 { 204 loop_optimizer_finalize (); 205 free_dominance_info (CDI_DOMINATORS); 206 207 cleanup_cfg (0); 208 if (dump_file) 209 dump_flow_info (dump_file, dump_flags); 210 211 return 0; 212 } 213 214 struct rtl_opt_pass pass_rtl_loop_done = 215 { 216 { 217 RTL_PASS, 218 "loop2_done", /* name */ 219 NULL, /* gate */ 220 rtl_loop_done, /* execute */ 221 NULL, /* sub */ 222 NULL, /* next */ 223 0, /* static_pass_number */ 224 TV_LOOP, /* tv_id */ 225 0, /* properties_required */ 226 0, /* properties_provided */ 227 0, /* properties_destroyed */ 228 0, /* todo_flags_start */ 229 TODO_verify_flow 230 | TODO_verify_rtl_sharing /* todo_flags_finish */ 231 } 232 }; 233 234 235 /* Loop invariant code motion. */ 236 static bool 237 gate_rtl_move_loop_invariants (void) 238 { 239 return flag_move_loop_invariants; 240 } 241 242 static unsigned int 243 rtl_move_loop_invariants (void) 244 { 245 if (number_of_loops () > 1) 246 move_loop_invariants (); 247 return 0; 248 } 249 250 struct rtl_opt_pass pass_rtl_move_loop_invariants = 251 { 252 { 253 RTL_PASS, 254 "loop2_invariant", /* name */ 255 gate_rtl_move_loop_invariants, /* gate */ 256 rtl_move_loop_invariants, /* execute */ 257 NULL, /* sub */ 258 NULL, /* next */ 259 0, /* static_pass_number */ 260 TV_LOOP_MOVE_INVARIANTS, /* tv_id */ 261 0, /* properties_required */ 262 0, /* properties_provided */ 263 0, /* properties_destroyed */ 264 0, /* todo_flags_start */ 265 TODO_df_verify | 266 TODO_df_finish | TODO_verify_rtl_sharing /* todo_flags_finish */ 267 } 268 }; 269 270 271 /* Loop unswitching for RTL. */ 272 static bool 273 gate_rtl_unswitch (void) 274 { 275 return flag_unswitch_loops; 276 } 277 278 static unsigned int 279 rtl_unswitch (void) 280 { 281 if (number_of_loops () > 1) 282 unswitch_loops (); 283 return 0; 284 } 285 286 struct rtl_opt_pass pass_rtl_unswitch = 287 { 288 { 289 RTL_PASS, 290 "loop2_unswitch", /* name */ 291 gate_rtl_unswitch, /* gate */ 292 rtl_unswitch, /* execute */ 293 NULL, /* sub */ 294 NULL, /* next */ 295 0, /* static_pass_number */ 296 TV_LOOP_UNSWITCH, /* tv_id */ 297 0, /* properties_required */ 298 0, /* properties_provided */ 299 0, /* properties_destroyed */ 300 0, /* todo_flags_start */ 301 TODO_verify_rtl_sharing, /* todo_flags_finish */ 302 } 303 }; 304 305 306 /* Loop unswitching for RTL. */ 307 static bool 308 gate_rtl_unroll_and_peel_loops (void) 309 { 310 return (flag_peel_loops || flag_unroll_loops || flag_unroll_all_loops); 311 } 312 313 static unsigned int 314 rtl_unroll_and_peel_loops (void) 315 { 316 if (number_of_loops () > 1) 317 { 318 int flags = 0; 319 if (dump_file) 320 df_dump (dump_file); 321 322 if (flag_peel_loops) 323 flags |= UAP_PEEL; 324 if (flag_unroll_loops) 325 flags |= UAP_UNROLL; 326 if (flag_unroll_all_loops) 327 flags |= UAP_UNROLL_ALL; 328 329 unroll_and_peel_loops (flags); 330 } 331 return 0; 332 } 333 334 struct rtl_opt_pass pass_rtl_unroll_and_peel_loops = 335 { 336 { 337 RTL_PASS, 338 "loop2_unroll", /* name */ 339 gate_rtl_unroll_and_peel_loops, /* gate */ 340 rtl_unroll_and_peel_loops, /* execute */ 341 NULL, /* sub */ 342 NULL, /* next */ 343 0, /* static_pass_number */ 344 TV_LOOP_UNROLL, /* tv_id */ 345 0, /* properties_required */ 346 0, /* properties_provided */ 347 0, /* properties_destroyed */ 348 0, /* todo_flags_start */ 349 TODO_verify_rtl_sharing, /* todo_flags_finish */ 350 } 351 }; 352 353 354 /* The doloop optimization. */ 355 static bool 356 gate_rtl_doloop (void) 357 { 358 #ifdef HAVE_doloop_end 359 return (flag_branch_on_count_reg && HAVE_doloop_end); 360 #else 361 return 0; 362 #endif 363 } 364 365 static unsigned int 366 rtl_doloop (void) 367 { 368 #ifdef HAVE_doloop_end 369 if (number_of_loops () > 1) 370 doloop_optimize_loops (); 371 #endif 372 return 0; 373 } 374 375 struct rtl_opt_pass pass_rtl_doloop = 376 { 377 { 378 RTL_PASS, 379 "loop2_doloop", /* name */ 380 gate_rtl_doloop, /* gate */ 381 rtl_doloop, /* execute */ 382 NULL, /* sub */ 383 NULL, /* next */ 384 0, /* static_pass_number */ 385 TV_LOOP_DOLOOP, /* tv_id */ 386 0, /* properties_required */ 387 0, /* properties_provided */ 388 0, /* properties_destroyed */ 389 0, /* todo_flags_start */ 390 TODO_verify_rtl_sharing /* todo_flags_finish */ 391 } 392 }; 393