1 /* Loop optimizer initialization routines and RTL loop optimization passes. 2 Copyright (C) 2002, 2003, 2004, 2005 Free Software Foundation, Inc. 3 4 This file is part of GCC. 5 6 GCC is free software; you can redistribute it and/or modify it under 7 the terms of the GNU General Public License as published by the Free 8 Software Foundation; either version 2, or (at your option) any later 9 version. 10 11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY 12 WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 for more details. 15 16 You should have received a copy of the GNU General Public License 17 along with GCC; see the file COPYING. If not, write to the Free 18 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 19 02110-1301, USA. */ 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 35 36 /* Initialize loop optimizer. This is used by the tree and RTL loop 37 optimizers. FLAGS specify what properties to compute and/or ensure for 38 loops. */ 39 40 struct loops * 41 loop_optimizer_init (unsigned flags) 42 { 43 struct loops *loops = XCNEW (struct loops); 44 edge e; 45 edge_iterator ei; 46 static bool first_time = true; 47 48 if (first_time) 49 { 50 first_time = false; 51 init_set_costs (); 52 } 53 54 /* Avoid annoying special cases of edges going to exit 55 block. */ 56 57 for (ei = ei_start (EXIT_BLOCK_PTR->preds); (e = ei_safe_edge (ei)); ) 58 if ((e->flags & EDGE_FALLTHRU) && !single_succ_p (e->src)) 59 split_edge (e); 60 else 61 ei_next (&ei); 62 63 /* Find the loops. */ 64 65 if (flow_loops_find (loops) <= 1) 66 { 67 /* No loops. */ 68 flow_loops_free (loops); 69 free (loops); 70 71 return NULL; 72 } 73 74 /* Not going to update these. */ 75 free (loops->cfg.rc_order); 76 loops->cfg.rc_order = NULL; 77 free (loops->cfg.dfs_order); 78 loops->cfg.dfs_order = NULL; 79 80 /* Create pre-headers. */ 81 if (flags & LOOPS_HAVE_PREHEADERS) 82 create_preheaders (loops, CP_SIMPLE_PREHEADERS); 83 84 /* Force all latches to have only single successor. */ 85 if (flags & LOOPS_HAVE_SIMPLE_LATCHES) 86 force_single_succ_latches (loops); 87 88 /* Mark irreducible loops. */ 89 if (flags & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS) 90 mark_irreducible_loops (loops); 91 92 if (flags & LOOPS_HAVE_MARKED_SINGLE_EXITS) 93 mark_single_exit_loops (loops); 94 95 /* Dump loops. */ 96 flow_loops_dump (loops, dump_file, NULL, 1); 97 98 #ifdef ENABLE_CHECKING 99 verify_dominators (CDI_DOMINATORS); 100 verify_loop_structure (loops); 101 #endif 102 103 return loops; 104 } 105 106 /* Finalize loop optimizer. */ 107 void 108 loop_optimizer_finalize (struct loops *loops) 109 { 110 unsigned i; 111 112 if (!loops) 113 return; 114 115 for (i = 1; i < loops->num; i++) 116 if (loops->parray[i]) 117 free_simple_loop_desc (loops->parray[i]); 118 119 /* Clean up. */ 120 flow_loops_free (loops); 121 free (loops); 122 123 /* Checking. */ 124 #ifdef ENABLE_CHECKING 125 verify_flow_info (); 126 #endif 127 } 128 129 130 /* Gate for the RTL loop superpass. The actual passes are subpasses. 131 See passes.c for more on that. */ 132 133 static bool 134 gate_handle_loop2 (void) 135 { 136 return (optimize > 0 137 && (flag_move_loop_invariants 138 || flag_unswitch_loops 139 || flag_peel_loops 140 || flag_unroll_loops 141 #ifdef HAVE_doloop_end 142 || (flag_branch_on_count_reg && HAVE_doloop_end) 143 #endif 144 )); 145 } 146 147 struct tree_opt_pass pass_loop2 = 148 { 149 "loop2", /* name */ 150 gate_handle_loop2, /* gate */ 151 NULL, /* execute */ 152 NULL, /* sub */ 153 NULL, /* next */ 154 0, /* static_pass_number */ 155 TV_LOOP, /* tv_id */ 156 0, /* properties_required */ 157 0, /* properties_provided */ 158 0, /* properties_destroyed */ 159 0, /* todo_flags_start */ 160 TODO_dump_func | 161 TODO_ggc_collect, /* todo_flags_finish */ 162 'L' /* letter */ 163 }; 164 165 166 /* Initialization of the RTL loop passes. */ 167 static unsigned int 168 rtl_loop_init (void) 169 { 170 if (dump_file) 171 dump_flow_info (dump_file, dump_flags); 172 173 /* Initialize structures for layout changes. */ 174 cfg_layout_initialize (0); 175 176 current_loops = loop_optimizer_init (LOOPS_NORMAL); 177 return 0; 178 } 179 180 struct tree_opt_pass pass_rtl_loop_init = 181 { 182 "loop2_init", /* name */ 183 NULL, /* gate */ 184 rtl_loop_init, /* execute */ 185 NULL, /* sub */ 186 NULL, /* next */ 187 0, /* static_pass_number */ 188 TV_LOOP, /* tv_id */ 189 0, /* properties_required */ 190 0, /* properties_provided */ 191 0, /* properties_destroyed */ 192 0, /* todo_flags_start */ 193 TODO_dump_func, /* todo_flags_finish */ 194 'L' /* letter */ 195 }; 196 197 198 /* Finalization of the RTL loop passes. */ 199 static unsigned int 200 rtl_loop_done (void) 201 { 202 basic_block bb; 203 204 if (current_loops) 205 loop_optimizer_finalize (current_loops); 206 207 free_dominance_info (CDI_DOMINATORS); 208 209 /* Finalize layout changes. */ 210 FOR_EACH_BB (bb) 211 if (bb->next_bb != EXIT_BLOCK_PTR) 212 bb->aux = bb->next_bb; 213 cfg_layout_finalize (); 214 215 cleanup_cfg (CLEANUP_EXPENSIVE); 216 delete_trivially_dead_insns (get_insns (), max_reg_num ()); 217 reg_scan (get_insns (), max_reg_num ()); 218 if (dump_file) 219 dump_flow_info (dump_file, dump_flags); 220 221 current_loops = NULL; 222 return 0; 223 } 224 225 struct tree_opt_pass pass_rtl_loop_done = 226 { 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_flags_finish */ 239 'L' /* letter */ 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 (current_loops) 254 move_loop_invariants (current_loops); 255 return 0; 256 } 257 258 struct tree_opt_pass pass_rtl_move_loop_invariants = 259 { 260 "loop2_invariant", /* name */ 261 gate_rtl_move_loop_invariants, /* gate */ 262 rtl_move_loop_invariants, /* execute */ 263 NULL, /* sub */ 264 NULL, /* next */ 265 0, /* static_pass_number */ 266 TV_LOOP, /* tv_id */ 267 0, /* properties_required */ 268 0, /* properties_provided */ 269 0, /* properties_destroyed */ 270 0, /* todo_flags_start */ 271 TODO_dump_func, /* todo_flags_finish */ 272 'L' /* letter */ 273 }; 274 275 276 /* Loop unswitching for RTL. */ 277 static bool 278 gate_rtl_unswitch (void) 279 { 280 return flag_unswitch_loops; 281 } 282 283 static unsigned int 284 rtl_unswitch (void) 285 { 286 if (current_loops) 287 unswitch_loops (current_loops); 288 return 0; 289 } 290 291 struct tree_opt_pass pass_rtl_unswitch = 292 { 293 "loop2_unswitch", /* name */ 294 gate_rtl_unswitch, /* gate */ 295 rtl_unswitch, /* execute */ 296 NULL, /* sub */ 297 NULL, /* next */ 298 0, /* static_pass_number */ 299 TV_LOOP, /* tv_id */ 300 0, /* properties_required */ 301 0, /* properties_provided */ 302 0, /* properties_destroyed */ 303 0, /* todo_flags_start */ 304 TODO_dump_func, /* todo_flags_finish */ 305 'L' /* letter */ 306 }; 307 308 309 /* Loop unswitching for RTL. */ 310 static bool 311 gate_rtl_unroll_and_peel_loops (void) 312 { 313 return (flag_peel_loops || flag_unroll_loops || flag_unroll_all_loops); 314 } 315 316 static unsigned int 317 rtl_unroll_and_peel_loops (void) 318 { 319 if (current_loops) 320 { 321 int flags = 0; 322 323 if (flag_peel_loops) 324 flags |= UAP_PEEL; 325 if (flag_unroll_loops) 326 flags |= UAP_UNROLL; 327 if (flag_unroll_all_loops) 328 flags |= UAP_UNROLL_ALL; 329 330 unroll_and_peel_loops (current_loops, flags); 331 } 332 return 0; 333 } 334 335 struct tree_opt_pass pass_rtl_unroll_and_peel_loops = 336 { 337 "loop2_unroll", /* name */ 338 gate_rtl_unroll_and_peel_loops, /* gate */ 339 rtl_unroll_and_peel_loops, /* execute */ 340 NULL, /* sub */ 341 NULL, /* next */ 342 0, /* static_pass_number */ 343 TV_LOOP, /* tv_id */ 344 0, /* properties_required */ 345 0, /* properties_provided */ 346 0, /* properties_destroyed */ 347 0, /* todo_flags_start */ 348 TODO_dump_func, /* todo_flags_finish */ 349 'L' /* letter */ 350 }; 351 352 353 /* The doloop optimization. */ 354 static bool 355 gate_rtl_doloop (void) 356 { 357 #ifdef HAVE_doloop_end 358 return (flag_branch_on_count_reg && HAVE_doloop_end); 359 #else 360 return 0; 361 #endif 362 } 363 364 static unsigned int 365 rtl_doloop (void) 366 { 367 #ifdef HAVE_doloop_end 368 if (current_loops) 369 doloop_optimize_loops (current_loops); 370 #endif 371 return 0; 372 } 373 374 struct tree_opt_pass pass_rtl_doloop = 375 { 376 "loop2_doloop", /* name */ 377 gate_rtl_doloop, /* gate */ 378 rtl_doloop, /* execute */ 379 NULL, /* sub */ 380 NULL, /* next */ 381 0, /* static_pass_number */ 382 TV_LOOP, /* tv_id */ 383 0, /* properties_required */ 384 0, /* properties_provided */ 385 0, /* properties_destroyed */ 386 0, /* todo_flags_start */ 387 TODO_dump_func, /* todo_flags_finish */ 388 'L' /* letter */ 389 }; 390 391