1/* Loop optimizer initialization routines and RTL loop optimization passes. 2 Copyright (C) 2002, 2003, 2004, 2005 Free Software Foundation, Inc. 3 4This file is part of GCC. 5 6GCC is free software; you can redistribute it and/or modify it under 7the terms of the GNU General Public License as published by the Free 8Software Foundation; either version 2, or (at your option) any later 9version. 10 11GCC is distributed in the hope that it will be useful, but WITHOUT ANY 12WARRANTY; without even the implied warranty of MERCHANTABILITY or 13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14for more details. 15 16You should have received a copy of the GNU General Public License 17along with GCC; see the file COPYING. If not, write to the Free 18Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 1902110-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 40struct loops * 41loop_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. */ 107void 108loop_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 133static bool 134gate_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 147struct 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. */ 167static unsigned int 168rtl_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 180struct 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. */ 199static unsigned int 200rtl_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 225struct 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. */ 244static bool 245gate_rtl_move_loop_invariants (void) 246{ 247 return flag_move_loop_invariants; 248} 249 250static unsigned int 251rtl_move_loop_invariants (void) 252{ 253 if (current_loops) 254 move_loop_invariants (current_loops); 255 return 0; 256} 257 258struct 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. */ 277static bool 278gate_rtl_unswitch (void) 279{ 280 return flag_unswitch_loops; 281} 282 283static unsigned int 284rtl_unswitch (void) 285{ 286 if (current_loops) 287 unswitch_loops (current_loops); 288 return 0; 289} 290 291struct 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. */ 310static bool 311gate_rtl_unroll_and_peel_loops (void) 312{ 313 return (flag_peel_loops || flag_unroll_loops || flag_unroll_all_loops); 314} 315 316static unsigned int 317rtl_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 335struct 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. */ 354static bool 355gate_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 364static unsigned int 365rtl_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 374struct 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