1169689Skan/* Loop optimizer initialization routines and RTL loop optimization passes. 2169689Skan Copyright (C) 2002, 2003, 2004, 2005 Free Software Foundation, Inc. 3132718Skan 4132718SkanThis file is part of GCC. 5132718Skan 6132718SkanGCC is free software; you can redistribute it and/or modify it under 7132718Skanthe terms of the GNU General Public License as published by the Free 8132718SkanSoftware Foundation; either version 2, or (at your option) any later 9132718Skanversion. 10132718Skan 11132718SkanGCC is distributed in the hope that it will be useful, but WITHOUT ANY 12132718SkanWARRANTY; without even the implied warranty of MERCHANTABILITY or 13132718SkanFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14132718Skanfor more details. 15132718Skan 16132718SkanYou should have received a copy of the GNU General Public License 17132718Skanalong with GCC; see the file COPYING. If not, write to the Free 18169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 19169689Skan02110-1301, USA. */ 20132718Skan 21132718Skan#include "config.h" 22132718Skan#include "system.h" 23132718Skan#include "coretypes.h" 24132718Skan#include "tm.h" 25132718Skan#include "rtl.h" 26132718Skan#include "hard-reg-set.h" 27169689Skan#include "obstack.h" 28132718Skan#include "basic-block.h" 29132718Skan#include "cfgloop.h" 30132718Skan#include "cfglayout.h" 31169689Skan#include "tree-pass.h" 32169689Skan#include "timevar.h" 33169689Skan#include "flags.h" 34132718Skan 35169689Skan 36169689Skan/* Initialize loop optimizer. This is used by the tree and RTL loop 37169689Skan optimizers. FLAGS specify what properties to compute and/or ensure for 38169689Skan loops. */ 39132718Skan 40132718Skanstruct loops * 41169689Skanloop_optimizer_init (unsigned flags) 42132718Skan{ 43169689Skan struct loops *loops = XCNEW (struct loops); 44132718Skan edge e; 45169689Skan edge_iterator ei; 46169689Skan static bool first_time = true; 47132718Skan 48169689Skan if (first_time) 49169689Skan { 50169689Skan first_time = false; 51169689Skan init_set_costs (); 52169689Skan } 53132718Skan 54132718Skan /* Avoid annoying special cases of edges going to exit 55132718Skan block. */ 56169689Skan 57169689Skan for (ei = ei_start (EXIT_BLOCK_PTR->preds); (e = ei_safe_edge (ei)); ) 58169689Skan if ((e->flags & EDGE_FALLTHRU) && !single_succ_p (e->src)) 59132718Skan split_edge (e); 60169689Skan else 61169689Skan ei_next (&ei); 62132718Skan 63132718Skan /* Find the loops. */ 64132718Skan 65169689Skan if (flow_loops_find (loops) <= 1) 66132718Skan { 67132718Skan /* No loops. */ 68132718Skan flow_loops_free (loops); 69132718Skan free (loops); 70132718Skan 71132718Skan return NULL; 72132718Skan } 73132718Skan 74132718Skan /* Not going to update these. */ 75132718Skan free (loops->cfg.rc_order); 76132718Skan loops->cfg.rc_order = NULL; 77132718Skan free (loops->cfg.dfs_order); 78132718Skan loops->cfg.dfs_order = NULL; 79132718Skan 80132718Skan /* Create pre-headers. */ 81169689Skan if (flags & LOOPS_HAVE_PREHEADERS) 82169689Skan create_preheaders (loops, CP_SIMPLE_PREHEADERS); 83132718Skan 84132718Skan /* Force all latches to have only single successor. */ 85169689Skan if (flags & LOOPS_HAVE_SIMPLE_LATCHES) 86169689Skan force_single_succ_latches (loops); 87132718Skan 88132718Skan /* Mark irreducible loops. */ 89169689Skan if (flags & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS) 90169689Skan mark_irreducible_loops (loops); 91132718Skan 92169689Skan if (flags & LOOPS_HAVE_MARKED_SINGLE_EXITS) 93169689Skan mark_single_exit_loops (loops); 94169689Skan 95132718Skan /* Dump loops. */ 96169689Skan flow_loops_dump (loops, dump_file, NULL, 1); 97132718Skan 98132718Skan#ifdef ENABLE_CHECKING 99132718Skan verify_dominators (CDI_DOMINATORS); 100132718Skan verify_loop_structure (loops); 101132718Skan#endif 102132718Skan 103132718Skan return loops; 104132718Skan} 105132718Skan 106169689Skan/* Finalize loop optimizer. */ 107169689Skanvoid 108169689Skanloop_optimizer_finalize (struct loops *loops) 109132718Skan{ 110169689Skan unsigned i; 111132718Skan 112169689Skan if (!loops) 113132718Skan return; 114132718Skan 115169689Skan for (i = 1; i < loops->num; i++) 116169689Skan if (loops->parray[i]) 117169689Skan free_simple_loop_desc (loops->parray[i]); 118132718Skan 119169689Skan /* Clean up. */ 120169689Skan flow_loops_free (loops); 121169689Skan free (loops); 122132718Skan 123169689Skan /* Checking. */ 124169689Skan#ifdef ENABLE_CHECKING 125169689Skan verify_flow_info (); 126169689Skan#endif 127169689Skan} 128132718Skan 129169689Skan 130169689Skan/* Gate for the RTL loop superpass. The actual passes are subpasses. 131169689Skan See passes.c for more on that. */ 132132718Skan 133169689Skanstatic bool 134169689Skangate_handle_loop2 (void) 135169689Skan{ 136169689Skan return (optimize > 0 137169689Skan && (flag_move_loop_invariants 138169689Skan || flag_unswitch_loops 139169689Skan || flag_peel_loops 140169689Skan || flag_unroll_loops 141169689Skan#ifdef HAVE_doloop_end 142169689Skan || (flag_branch_on_count_reg && HAVE_doloop_end) 143169689Skan#endif 144169689Skan )); 145169689Skan} 146132718Skan 147169689Skanstruct tree_opt_pass pass_loop2 = 148169689Skan{ 149169689Skan "loop2", /* name */ 150169689Skan gate_handle_loop2, /* gate */ 151169689Skan NULL, /* execute */ 152169689Skan NULL, /* sub */ 153169689Skan NULL, /* next */ 154169689Skan 0, /* static_pass_number */ 155169689Skan TV_LOOP, /* tv_id */ 156169689Skan 0, /* properties_required */ 157169689Skan 0, /* properties_provided */ 158169689Skan 0, /* properties_destroyed */ 159169689Skan 0, /* todo_flags_start */ 160169689Skan TODO_dump_func | 161169689Skan TODO_ggc_collect, /* todo_flags_finish */ 162169689Skan 'L' /* letter */ 163169689Skan}; 164169689Skan 165169689Skan 166169689Skan/* Initialization of the RTL loop passes. */ 167169689Skanstatic unsigned int 168169689Skanrtl_loop_init (void) 169169689Skan{ 170169689Skan if (dump_file) 171169689Skan dump_flow_info (dump_file, dump_flags); 172169689Skan 173169689Skan /* Initialize structures for layout changes. */ 174169689Skan cfg_layout_initialize (0); 175169689Skan 176169689Skan current_loops = loop_optimizer_init (LOOPS_NORMAL); 177169689Skan return 0; 178132718Skan} 179132718Skan 180169689Skanstruct tree_opt_pass pass_rtl_loop_init = 181132718Skan{ 182169689Skan "loop2_init", /* name */ 183169689Skan NULL, /* gate */ 184169689Skan rtl_loop_init, /* execute */ 185169689Skan NULL, /* sub */ 186169689Skan NULL, /* next */ 187169689Skan 0, /* static_pass_number */ 188169689Skan TV_LOOP, /* tv_id */ 189169689Skan 0, /* properties_required */ 190169689Skan 0, /* properties_provided */ 191169689Skan 0, /* properties_destroyed */ 192169689Skan 0, /* todo_flags_start */ 193169689Skan TODO_dump_func, /* todo_flags_finish */ 194169689Skan 'L' /* letter */ 195169689Skan}; 196169689Skan 197169689Skan 198169689Skan/* Finalization of the RTL loop passes. */ 199169689Skanstatic unsigned int 200169689Skanrtl_loop_done (void) 201169689Skan{ 202132718Skan basic_block bb; 203132718Skan 204169689Skan if (current_loops) 205169689Skan loop_optimizer_finalize (current_loops); 206169689Skan 207169689Skan free_dominance_info (CDI_DOMINATORS); 208169689Skan 209132718Skan /* Finalize layout changes. */ 210132718Skan FOR_EACH_BB (bb) 211132718Skan if (bb->next_bb != EXIT_BLOCK_PTR) 212169689Skan bb->aux = bb->next_bb; 213169689Skan cfg_layout_finalize (); 214132718Skan 215169689Skan cleanup_cfg (CLEANUP_EXPENSIVE); 216169689Skan delete_trivially_dead_insns (get_insns (), max_reg_num ()); 217169689Skan reg_scan (get_insns (), max_reg_num ()); 218169689Skan if (dump_file) 219169689Skan dump_flow_info (dump_file, dump_flags); 220132718Skan 221169689Skan current_loops = NULL; 222169689Skan return 0; 223169689Skan} 224132718Skan 225169689Skanstruct tree_opt_pass pass_rtl_loop_done = 226169689Skan{ 227169689Skan "loop2_done", /* name */ 228169689Skan NULL, /* gate */ 229169689Skan rtl_loop_done, /* execute */ 230169689Skan NULL, /* sub */ 231169689Skan NULL, /* next */ 232169689Skan 0, /* static_pass_number */ 233169689Skan TV_LOOP, /* tv_id */ 234169689Skan 0, /* properties_required */ 235169689Skan 0, /* properties_provided */ 236169689Skan 0, /* properties_destroyed */ 237169689Skan 0, /* todo_flags_start */ 238169689Skan TODO_dump_func, /* todo_flags_finish */ 239169689Skan 'L' /* letter */ 240169689Skan}; 241132718Skan 242169689Skan 243169689Skan/* Loop invariant code motion. */ 244169689Skanstatic bool 245169689Skangate_rtl_move_loop_invariants (void) 246169689Skan{ 247169689Skan return flag_move_loop_invariants; 248169689Skan} 249132718Skan 250169689Skanstatic unsigned int 251169689Skanrtl_move_loop_invariants (void) 252169689Skan{ 253169689Skan if (current_loops) 254169689Skan move_loop_invariants (current_loops); 255169689Skan return 0; 256169689Skan} 257132718Skan 258169689Skanstruct tree_opt_pass pass_rtl_move_loop_invariants = 259169689Skan{ 260169689Skan "loop2_invariant", /* name */ 261169689Skan gate_rtl_move_loop_invariants, /* gate */ 262169689Skan rtl_move_loop_invariants, /* execute */ 263169689Skan NULL, /* sub */ 264169689Skan NULL, /* next */ 265169689Skan 0, /* static_pass_number */ 266169689Skan TV_LOOP, /* tv_id */ 267169689Skan 0, /* properties_required */ 268169689Skan 0, /* properties_provided */ 269169689Skan 0, /* properties_destroyed */ 270169689Skan 0, /* todo_flags_start */ 271169689Skan TODO_dump_func, /* todo_flags_finish */ 272169689Skan 'L' /* letter */ 273169689Skan}; 274132718Skan 275169689Skan 276169689Skan/* Loop unswitching for RTL. */ 277169689Skanstatic bool 278169689Skangate_rtl_unswitch (void) 279169689Skan{ 280169689Skan return flag_unswitch_loops; 281169689Skan} 282132718Skan 283169689Skanstatic unsigned int 284169689Skanrtl_unswitch (void) 285169689Skan{ 286169689Skan if (current_loops) 287169689Skan unswitch_loops (current_loops); 288169689Skan return 0; 289169689Skan} 290132718Skan 291169689Skanstruct tree_opt_pass pass_rtl_unswitch = 292169689Skan{ 293169689Skan "loop2_unswitch", /* name */ 294169689Skan gate_rtl_unswitch, /* gate */ 295169689Skan rtl_unswitch, /* execute */ 296169689Skan NULL, /* sub */ 297169689Skan NULL, /* next */ 298169689Skan 0, /* static_pass_number */ 299169689Skan TV_LOOP, /* tv_id */ 300169689Skan 0, /* properties_required */ 301169689Skan 0, /* properties_provided */ 302169689Skan 0, /* properties_destroyed */ 303169689Skan 0, /* todo_flags_start */ 304169689Skan TODO_dump_func, /* todo_flags_finish */ 305169689Skan 'L' /* letter */ 306169689Skan}; 307132718Skan 308169689Skan 309169689Skan/* Loop unswitching for RTL. */ 310169689Skanstatic bool 311169689Skangate_rtl_unroll_and_peel_loops (void) 312169689Skan{ 313169689Skan return (flag_peel_loops || flag_unroll_loops || flag_unroll_all_loops); 314169689Skan} 315132718Skan 316169689Skanstatic unsigned int 317169689Skanrtl_unroll_and_peel_loops (void) 318169689Skan{ 319169689Skan if (current_loops) 320169689Skan { 321169689Skan int flags = 0; 322169689Skan 323169689Skan if (flag_peel_loops) 324169689Skan flags |= UAP_PEEL; 325169689Skan if (flag_unroll_loops) 326169689Skan flags |= UAP_UNROLL; 327169689Skan if (flag_unroll_all_loops) 328169689Skan flags |= UAP_UNROLL_ALL; 329169689Skan 330169689Skan unroll_and_peel_loops (current_loops, flags); 331132718Skan } 332169689Skan return 0; 333169689Skan} 334132718Skan 335169689Skanstruct tree_opt_pass pass_rtl_unroll_and_peel_loops = 336169689Skan{ 337169689Skan "loop2_unroll", /* name */ 338169689Skan gate_rtl_unroll_and_peel_loops, /* gate */ 339169689Skan rtl_unroll_and_peel_loops, /* execute */ 340169689Skan NULL, /* sub */ 341169689Skan NULL, /* next */ 342169689Skan 0, /* static_pass_number */ 343169689Skan TV_LOOP, /* tv_id */ 344169689Skan 0, /* properties_required */ 345169689Skan 0, /* properties_provided */ 346169689Skan 0, /* properties_destroyed */ 347169689Skan 0, /* todo_flags_start */ 348169689Skan TODO_dump_func, /* todo_flags_finish */ 349169689Skan 'L' /* letter */ 350169689Skan}; 351132718Skan 352169689Skan 353169689Skan/* The doloop optimization. */ 354169689Skanstatic bool 355169689Skangate_rtl_doloop (void) 356169689Skan{ 357169689Skan#ifdef HAVE_doloop_end 358169689Skan return (flag_branch_on_count_reg && HAVE_doloop_end); 359169689Skan#else 360169689Skan return 0; 361169689Skan#endif 362169689Skan} 363132718Skan 364169689Skanstatic unsigned int 365169689Skanrtl_doloop (void) 366169689Skan{ 367169689Skan#ifdef HAVE_doloop_end 368169689Skan if (current_loops) 369169689Skan doloop_optimize_loops (current_loops); 370132718Skan#endif 371169689Skan return 0; 372132718Skan} 373169689Skan 374169689Skanstruct tree_opt_pass pass_rtl_doloop = 375169689Skan{ 376169689Skan "loop2_doloop", /* name */ 377169689Skan gate_rtl_doloop, /* gate */ 378169689Skan rtl_doloop, /* execute */ 379169689Skan NULL, /* sub */ 380169689Skan NULL, /* next */ 381169689Skan 0, /* static_pass_number */ 382169689Skan TV_LOOP, /* tv_id */ 383169689Skan 0, /* properties_required */ 384169689Skan 0, /* properties_provided */ 385169689Skan 0, /* properties_destroyed */ 386169689Skan 0, /* todo_flags_start */ 387169689Skan TODO_dump_func, /* todo_flags_finish */ 388169689Skan 'L' /* letter */ 389169689Skan}; 390169689Skan 391