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. */ 38 39struct loops * 40loop_optimizer_init (FILE *dumpfile) 41{ 42 struct loops *loops = xcalloc (1, sizeof (struct loops)); 43 edge e; 44 edge_iterator ei; 45 static bool first_time = true; 46 47 if (first_time) 48 { 49 first_time = false; 50 init_set_costs (); 51 } 52 53 /* Avoid annoying special cases of edges going to exit 54 block. */ 55 56 for (ei = ei_start (EXIT_BLOCK_PTR->preds); (e = ei_safe_edge (ei)); ) 57 if ((e->flags & EDGE_FALLTHRU) && !single_succ_p (e->src)) 58 split_edge (e); 59 else 60 ei_next (&ei); 61 62 /* Find the loops. */ 63 64 if (flow_loops_find (loops) <= 1) 65 { 66 /* No loops. */ 67 flow_loops_free (loops); 68 free (loops); 69 70 return NULL; 71 } 72 73 /* Not going to update these. */ 74 free (loops->cfg.rc_order); 75 loops->cfg.rc_order = NULL; 76 free (loops->cfg.dfs_order); 77 loops->cfg.dfs_order = NULL; 78 79 /* Create pre-headers. */ 80 create_preheaders (loops, CP_SIMPLE_PREHEADERS); 81 82 /* Force all latches to have only single successor. */ 83 force_single_succ_latches (loops); 84 85 /* Mark irreducible loops. */ 86 mark_irreducible_loops (loops); 87 88 /* Dump loops. */ 89 flow_loops_dump (loops, dumpfile, NULL, 1); 90 91#ifdef ENABLE_CHECKING 92 verify_dominators (CDI_DOMINATORS); 93 verify_loop_structure (loops); 94#endif 95 96 return loops; 97} 98 99/* Finalize loop optimizer. */ 100void 101loop_optimizer_finalize (struct loops *loops, FILE *dumpfile) 102{ 103 unsigned i; 104 105 if (!loops) 106 return; 107 108 for (i = 1; i < loops->num; i++) 109 if (loops->parray[i]) 110 free_simple_loop_desc (loops->parray[i]); 111 112 /* Another dump. */ 113 flow_loops_dump (loops, dumpfile, NULL, 1); 114 115 /* Clean up. */ 116 flow_loops_free (loops); 117 free (loops); 118 119 /* Checking. */ 120#ifdef ENABLE_CHECKING 121 verify_flow_info (); 122#endif 123} 124 125 126/* Gate for the RTL loop superpass. The actual passes are subpasses. 127 See passes.c for more on that. */ 128 129static bool 130gate_handle_loop2 (void) 131{ 132 return (optimize > 0 && flag_loop_optimize2 133 && (flag_move_loop_invariants 134 || flag_unswitch_loops 135 || flag_peel_loops 136 || flag_unroll_loops 137 || flag_branch_on_count_reg)); 138} 139 140struct tree_opt_pass pass_loop2 = 141{ 142 "loop2", /* name */ 143 gate_handle_loop2, /* gate */ 144 NULL, /* execute */ 145 NULL, /* sub */ 146 NULL, /* next */ 147 0, /* static_pass_number */ 148 TV_LOOP, /* tv_id */ 149 0, /* properties_required */ 150 0, /* properties_provided */ 151 0, /* properties_destroyed */ 152 0, /* todo_flags_start */ 153 TODO_dump_func | 154 TODO_ggc_collect, /* todo_flags_finish */ 155 'L' /* letter */ 156}; 157 158 159/* Initialization of the RTL loop passes. */ 160static void 161rtl_loop_init (void) 162{ 163 if (dump_file) 164 dump_flow_info (dump_file); 165 166 /* Initialize structures for layout changes. */ 167 cfg_layout_initialize (0); 168 169 current_loops = loop_optimizer_init (dump_file); 170} 171 172struct tree_opt_pass pass_rtl_loop_init = 173{ 174 "loop2_init", /* name */ 175 NULL, /* gate */ 176 rtl_loop_init, /* execute */ 177 NULL, /* sub */ 178 NULL, /* next */ 179 0, /* static_pass_number */ 180 TV_LOOP, /* tv_id */ 181 0, /* properties_required */ 182 0, /* properties_provided */ 183 0, /* properties_destroyed */ 184 0, /* todo_flags_start */ 185 TODO_dump_func, /* todo_flags_finish */ 186 'L' /* letter */ 187}; 188 189 190/* Finalization of the RTL loop passes. */ 191static void 192rtl_loop_done (void) 193{ 194 basic_block bb; 195 196 if (current_loops) 197 loop_optimizer_finalize (current_loops, dump_file); 198 199 free_dominance_info (CDI_DOMINATORS); 200 201 /* Finalize layout changes. */ 202 FOR_EACH_BB (bb) 203 if (bb->next_bb != EXIT_BLOCK_PTR) 204 bb->aux = bb->next_bb; 205 cfg_layout_finalize (); 206 207 cleanup_cfg (CLEANUP_EXPENSIVE); 208 delete_trivially_dead_insns (get_insns (), max_reg_num ()); 209 reg_scan (get_insns (), max_reg_num ()); 210 if (dump_file) 211 dump_flow_info (dump_file); 212 213 current_loops = NULL; 214} 215 216struct tree_opt_pass pass_rtl_loop_done = 217{ 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_dump_func, /* todo_flags_finish */ 230 'L' /* letter */ 231}; 232 233 234/* Loop invariant code motion. */ 235static bool 236gate_rtl_move_loop_invariants (void) 237{ 238 return flag_move_loop_invariants; 239} 240 241static void 242rtl_move_loop_invariants (void) 243{ 244 if (current_loops) 245 move_loop_invariants (current_loops); 246} 247 248struct tree_opt_pass pass_rtl_move_loop_invariants = 249{ 250 "loop2_invariant", /* name */ 251 gate_rtl_move_loop_invariants, /* gate */ 252 rtl_move_loop_invariants, /* execute */ 253 NULL, /* sub */ 254 NULL, /* next */ 255 0, /* static_pass_number */ 256 TV_LOOP, /* tv_id */ 257 0, /* properties_required */ 258 0, /* properties_provided */ 259 0, /* properties_destroyed */ 260 0, /* todo_flags_start */ 261 TODO_dump_func, /* todo_flags_finish */ 262 'L' /* letter */ 263}; 264 265 266/* Loop unswitching for RTL. */ 267static bool 268gate_rtl_unswitch (void) 269{ 270 return flag_unswitch_loops; 271} 272 273static void 274rtl_unswitch (void) 275{ 276 if (current_loops) 277 unswitch_loops (current_loops); 278} 279 280struct tree_opt_pass pass_rtl_unswitch = 281{ 282 "loop2_unswitch", /* name */ 283 gate_rtl_unswitch, /* gate */ 284 rtl_unswitch, /* execute */ 285 NULL, /* sub */ 286 NULL, /* next */ 287 0, /* static_pass_number */ 288 TV_LOOP, /* tv_id */ 289 0, /* properties_required */ 290 0, /* properties_provided */ 291 0, /* properties_destroyed */ 292 0, /* todo_flags_start */ 293 TODO_dump_func, /* todo_flags_finish */ 294 'L' /* letter */ 295}; 296 297 298/* Loop unswitching for RTL. */ 299static bool 300gate_rtl_unroll_and_peel_loops (void) 301{ 302 return (flag_peel_loops || flag_unroll_loops || flag_unroll_all_loops); 303} 304 305static void 306rtl_unroll_and_peel_loops (void) 307{ 308 if (current_loops) 309 { 310 int flags = 0; 311 312 if (flag_peel_loops) 313 flags |= UAP_PEEL; 314 if (flag_unroll_loops) 315 flags |= UAP_UNROLL; 316 if (flag_unroll_all_loops) 317 flags |= UAP_UNROLL_ALL; 318 319 unroll_and_peel_loops (current_loops, flags); 320 } 321} 322 323struct tree_opt_pass pass_rtl_unroll_and_peel_loops = 324{ 325 "loop2_unroll", /* name */ 326 gate_rtl_unroll_and_peel_loops, /* gate */ 327 rtl_unroll_and_peel_loops, /* execute */ 328 NULL, /* sub */ 329 NULL, /* next */ 330 0, /* static_pass_number */ 331 TV_LOOP, /* tv_id */ 332 0, /* properties_required */ 333 0, /* properties_provided */ 334 0, /* properties_destroyed */ 335 0, /* todo_flags_start */ 336 TODO_dump_func, /* todo_flags_finish */ 337 'L' /* letter */ 338}; 339 340 341/* The doloop optimization. */ 342static bool 343gate_rtl_doloop (void) 344{ 345#ifdef HAVE_doloop_end 346 return (flag_branch_on_count_reg && HAVE_doloop_end); 347#else 348 return 0; 349#endif 350} 351 352static void 353rtl_doloop (void) 354{ 355#ifdef HAVE_doloop_end 356 if (current_loops) 357 doloop_optimize_loops (current_loops); 358#endif 359} 360 361struct tree_opt_pass pass_rtl_doloop = 362{ 363 "loop2_doloop", /* name */ 364 gate_rtl_doloop, /* gate */ 365 rtl_doloop, /* execute */ 366 NULL, /* sub */ 367 NULL, /* next */ 368 0, /* static_pass_number */ 369 TV_LOOP, /* tv_id */ 370 0, /* properties_required */ 371 0, /* properties_provided */ 372 0, /* properties_destroyed */ 373 0, /* todo_flags_start */ 374 TODO_dump_func, /* todo_flags_finish */ 375 'L' /* letter */ 376}; 377 378