1254219Scy/* Loop optimizations over tree-ssa. 2254219Scy Copyright (C) 2003, 2005 Free Software Foundation, Inc. 3254219Scy 4254219ScyThis file is part of GCC. 5254219Scy 6254219ScyGCC is free software; you can redistribute it and/or modify it 7254219Scyunder the terms of the GNU General Public License as published by the 8254219ScyFree Software Foundation; either version 2, or (at your option) any 9254219Scylater version. 10254219Scy 11254219ScyGCC is distributed in the hope that it will be useful, but WITHOUT 12254219ScyANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13254219ScyFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14254219Scyfor more details. 15254219Scy 16254219ScyYou should have received a copy of the GNU General Public License 17254219Scyalong with GCC; see the file COPYING. If not, write to the Free 18254219ScySoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 19254219Scy02110-1301, USA. */ 20254219Scy 21254219Scy#include "config.h" 22254219Scy#include "system.h" 23254219Scy#include "coretypes.h" 24254219Scy#include "tm.h" 25254219Scy#include "tree.h" 26254219Scy#include "rtl.h" 27254219Scy#include "tm_p.h" 28254219Scy#include "hard-reg-set.h" 29254219Scy#include "basic-block.h" 30254219Scy#include "output.h" 31254219Scy#include "diagnostic.h" 32254219Scy#include "tree-flow.h" 33254219Scy#include "tree-dump.h" 34254219Scy#include "tree-pass.h" 35254219Scy#include "timevar.h" 36254219Scy#include "cfgloop.h" 37254219Scy#include "flags.h" 38254219Scy#include "tree-inline.h" 39254219Scy#include "tree-scalar-evolution.h" 40254219Scy 41254219Scy/* The loop tree currently optimized. */ 42254219Scy 43254219Scystruct loops *current_loops = NULL; 44254219Scy 45254219Scy/* Initializes the loop structures. */ 46254219Scy 47254219Scystatic struct loops * 48254219Scytree_loop_optimizer_init (void) 49254219Scy{ 50254219Scy struct loops *loops; 51254219Scy 52254219Scy loops = loop_optimizer_init (LOOPS_NORMAL 53254219Scy | LOOPS_HAVE_MARKED_SINGLE_EXITS); 54254219Scy 55254219Scy if (!loops) 56254219Scy return NULL; 57254219Scy 58254219Scy rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa); 59254219Scy 60254219Scy return loops; 61254219Scy} 62254219Scy 63254219Scy/* The loop superpass. */ 64254219Scy 65254219Scystatic bool 66254219Scygate_tree_loop (void) 67254219Scy{ 68254219Scy return flag_tree_loop_optimize != 0; 69254219Scy} 70254219Scy 71254219Scystruct tree_opt_pass pass_tree_loop = 72254219Scy{ 73254219Scy "loop", /* name */ 74254219Scy gate_tree_loop, /* gate */ 75254219Scy NULL, /* execute */ 76254219Scy NULL, /* sub */ 77254219Scy NULL, /* next */ 78254219Scy 0, /* static_pass_number */ 79254219Scy TV_TREE_LOOP, /* tv_id */ 80254219Scy PROP_cfg, /* properties_required */ 81254219Scy 0, /* properties_provided */ 82254219Scy 0, /* properties_destroyed */ 83254219Scy TODO_ggc_collect, /* todo_flags_start */ 84254219Scy TODO_dump_func | TODO_verify_ssa | TODO_ggc_collect, /* todo_flags_finish */ 85254219Scy 0 /* letter */ 86254219Scy}; 87254219Scy 88254219Scy/* Loop optimizer initialization. */ 89254219Scy 90254219Scystatic unsigned int 91254219Scytree_ssa_loop_init (void) 92254219Scy{ 93254219Scy current_loops = tree_loop_optimizer_init (); 94254219Scy if (!current_loops) 95254219Scy return 0; 96254219Scy 97254219Scy scev_initialize (current_loops); 98254219Scy return 0; 99254219Scy} 100254219Scy 101254219Scystruct tree_opt_pass pass_tree_loop_init = 102254219Scy{ 103254219Scy "loopinit", /* name */ 104254219Scy NULL, /* gate */ 105254219Scy tree_ssa_loop_init, /* execute */ 106254219Scy NULL, /* sub */ 107254219Scy NULL, /* next */ 108254219Scy 0, /* static_pass_number */ 109254219Scy TV_TREE_LOOP_INIT, /* tv_id */ 110254219Scy PROP_cfg, /* properties_required */ 111254219Scy 0, /* properties_provided */ 112254219Scy 0, /* properties_destroyed */ 113254219Scy 0, /* todo_flags_start */ 114254219Scy TODO_dump_func | TODO_verify_loops, /* todo_flags_finish */ 115254219Scy 0 /* letter */ 116254219Scy}; 117254219Scy 118254219Scy/* Loop invariant motion pass. */ 119254219Scy 120254219Scystatic unsigned int 121254219Scytree_ssa_loop_im (void) 122254219Scy{ 123254219Scy if (!current_loops) 124254219Scy return 0; 125254219Scy 126254219Scy tree_ssa_lim (current_loops); 127254219Scy return 0; 128254219Scy} 129254219Scy 130254219Scystatic bool 131254219Scygate_tree_ssa_loop_im (void) 132254219Scy{ 133254219Scy return flag_tree_loop_im != 0; 134254219Scy} 135254219Scy 136254219Scystruct tree_opt_pass pass_lim = 137254219Scy{ 138254219Scy "lim", /* name */ 139254219Scy gate_tree_ssa_loop_im, /* gate */ 140254219Scy tree_ssa_loop_im, /* execute */ 141254219Scy NULL, /* sub */ 142254219Scy NULL, /* next */ 143254219Scy 0, /* static_pass_number */ 144254219Scy TV_LIM, /* tv_id */ 145254219Scy PROP_cfg, /* properties_required */ 146254219Scy 0, /* properties_provided */ 147254219Scy 0, /* properties_destroyed */ 148254219Scy 0, /* todo_flags_start */ 149254219Scy TODO_dump_func | TODO_verify_loops, /* todo_flags_finish */ 150254219Scy 0 /* letter */ 151254219Scy}; 152254219Scy 153254219Scy/* Loop unswitching pass. */ 154254219Scy 155254219Scystatic unsigned int 156254219Scytree_ssa_loop_unswitch (void) 157254219Scy{ 158254219Scy if (!current_loops) 159254219Scy return 0; 160254219Scy 161254219Scy return tree_ssa_unswitch_loops (current_loops); 162254219Scy} 163254219Scy 164254219Scystatic bool 165254219Scygate_tree_ssa_loop_unswitch (void) 166254219Scy{ 167254219Scy return flag_unswitch_loops != 0; 168254219Scy} 169254219Scy 170254219Scystruct tree_opt_pass pass_tree_unswitch = 171254219Scy{ 172254219Scy "unswitch", /* name */ 173254219Scy gate_tree_ssa_loop_unswitch, /* gate */ 174254219Scy tree_ssa_loop_unswitch, /* execute */ 175254219Scy NULL, /* sub */ 176254219Scy NULL, /* next */ 177254219Scy 0, /* static_pass_number */ 178254219Scy TV_TREE_LOOP_UNSWITCH, /* tv_id */ 179254219Scy PROP_cfg, /* properties_required */ 180254219Scy 0, /* properties_provided */ 181254219Scy 0, /* properties_destroyed */ 182254219Scy 0, /* todo_flags_start */ 183254219Scy TODO_dump_func | TODO_verify_loops, /* todo_flags_finish */ 184254219Scy 0 /* letter */ 185254219Scy}; 186254219Scy 187254219Scy/* Loop autovectorization. */ 188254219Scy 189254219Scystatic unsigned int 190254219Scytree_vectorize (void) 191254219Scy{ 192254219Scy vectorize_loops (current_loops); 193254219Scy return 0; 194254219Scy} 195254219Scy 196254219Scystatic bool 197254219Scygate_tree_vectorize (void) 198254219Scy{ 199254219Scy return flag_tree_vectorize && current_loops; 200254219Scy} 201254219Scy 202254219Scystruct tree_opt_pass pass_vectorize = 203254219Scy{ 204254219Scy "vect", /* name */ 205254219Scy gate_tree_vectorize, /* gate */ 206254219Scy tree_vectorize, /* execute */ 207254219Scy NULL, /* sub */ 208254219Scy NULL, /* next */ 209254219Scy 0, /* static_pass_number */ 210254219Scy TV_TREE_VECTORIZATION, /* tv_id */ 211254219Scy PROP_cfg | PROP_ssa, /* properties_required */ 212254219Scy 0, /* properties_provided */ 213254219Scy 0, /* properties_destroyed */ 214254219Scy TODO_verify_loops, /* todo_flags_start */ 215254219Scy TODO_dump_func | TODO_update_ssa, /* todo_flags_finish */ 216254219Scy 0 /* letter */ 217254219Scy}; 218254219Scy 219254219Scy/* Loop nest optimizations. */ 220254219Scy 221254219Scystatic unsigned int 222254219Scytree_linear_transform (void) 223254219Scy{ 224254219Scy if (!current_loops) 225254219Scy return 0; 226254219Scy 227254219Scy linear_transform_loops (current_loops); 228254219Scy return 0; 229254219Scy} 230254219Scy 231254219Scystatic bool 232254219Scygate_tree_linear_transform (void) 233254219Scy{ 234254219Scy return flag_tree_loop_linear != 0; 235254219Scy} 236254219Scy 237254219Scystruct tree_opt_pass pass_linear_transform = 238254219Scy{ 239254219Scy "ltrans", /* name */ 240254219Scy gate_tree_linear_transform, /* gate */ 241254219Scy tree_linear_transform, /* execute */ 242254219Scy NULL, /* sub */ 243254219Scy NULL, /* next */ 244254219Scy 0, /* static_pass_number */ 245254219Scy TV_TREE_LINEAR_TRANSFORM, /* tv_id */ 246254219Scy PROP_cfg | PROP_ssa, /* properties_required */ 247254219Scy 0, /* properties_provided */ 248254219Scy 0, /* properties_destroyed */ 249254219Scy 0, /* todo_flags_start */ 250254219Scy TODO_dump_func | TODO_verify_loops, /* todo_flags_finish */ 251254219Scy 0 /* letter */ 252254219Scy}; 253254219Scy 254254219Scy/* Canonical induction variable creation pass. */ 255254219Scy 256254219Scystatic unsigned int 257254219Scytree_ssa_loop_ivcanon (void) 258254219Scy{ 259254219Scy if (!current_loops) 260254219Scy return 0; 261254219Scy 262254219Scy return canonicalize_induction_variables (current_loops); 263254219Scy} 264254219Scy 265254219Scystatic bool 266254219Scygate_tree_ssa_loop_ivcanon (void) 267254219Scy{ 268254219Scy return flag_tree_loop_ivcanon != 0; 269254219Scy} 270254219Scy 271254219Scystruct tree_opt_pass pass_iv_canon = 272254219Scy{ 273254219Scy "ivcanon", /* name */ 274254219Scy gate_tree_ssa_loop_ivcanon, /* gate */ 275254219Scy tree_ssa_loop_ivcanon, /* execute */ 276254219Scy NULL, /* sub */ 277254219Scy NULL, /* next */ 278254219Scy 0, /* static_pass_number */ 279254219Scy TV_TREE_LOOP_IVCANON, /* tv_id */ 280254219Scy PROP_cfg | PROP_ssa, /* properties_required */ 281254219Scy 0, /* properties_provided */ 282254219Scy 0, /* properties_destroyed */ 283254219Scy 0, /* todo_flags_start */ 284254219Scy TODO_dump_func | TODO_verify_loops, /* todo_flags_finish */ 285254219Scy 0 /* letter */ 286254219Scy}; 287254219Scy 288254219Scy/* Propagation of constants using scev. */ 289254219Scy 290254219Scystatic bool 291254219Scygate_scev_const_prop (void) 292254219Scy{ 293254219Scy return true; 294254219Scy} 295254219Scy 296254219Scystruct tree_opt_pass pass_scev_cprop = 297254219Scy{ 298254219Scy "sccp", /* name */ 299254219Scy gate_scev_const_prop, /* gate */ 300254219Scy scev_const_prop, /* execute */ 301254219Scy NULL, /* sub */ 302254219Scy NULL, /* next */ 303254219Scy 0, /* static_pass_number */ 304254219Scy TV_SCEV_CONST, /* tv_id */ 305254219Scy PROP_cfg | PROP_ssa, /* properties_required */ 306254219Scy 0, /* properties_provided */ 307254219Scy 0, /* properties_destroyed */ 308254219Scy 0, /* todo_flags_start */ 309254219Scy TODO_dump_func | TODO_cleanup_cfg 310254219Scy | TODO_update_ssa_only_virtuals, 311254219Scy /* todo_flags_finish */ 312254219Scy 0 /* letter */ 313254219Scy}; 314254219Scy 315254219Scy/* Remove empty loops. */ 316254219Scy 317254219Scystatic unsigned int 318254219Scytree_ssa_empty_loop (void) 319254219Scy{ 320254219Scy if (!current_loops) 321254219Scy return 0; 322254219Scy 323254219Scy return remove_empty_loops (current_loops); 324254219Scy} 325254219Scy 326254219Scystruct tree_opt_pass pass_empty_loop = 327254219Scy{ 328254219Scy "empty", /* name */ 329254219Scy NULL, /* gate */ 330254219Scy tree_ssa_empty_loop, /* execute */ 331254219Scy NULL, /* sub */ 332254219Scy NULL, /* next */ 333254219Scy 0, /* static_pass_number */ 334254219Scy TV_COMPLETE_UNROLL, /* tv_id */ 335254219Scy PROP_cfg | PROP_ssa, /* properties_required */ 336254219Scy 0, /* properties_provided */ 337254219Scy 0, /* properties_destroyed */ 338254219Scy 0, /* todo_flags_start */ 339254219Scy TODO_dump_func | TODO_verify_loops, /* todo_flags_finish */ 340254219Scy 0 /* letter */ 341254219Scy}; 342254219Scy 343254219Scy/* Record bounds on numbers of iterations of loops. */ 344254219Scy 345254219Scystatic unsigned int 346254219Scytree_ssa_loop_bounds (void) 347254219Scy{ 348254219Scy if (!current_loops) 349254219Scy return 0; 350254219Scy 351254219Scy estimate_numbers_of_iterations (current_loops); 352254219Scy scev_reset (); 353254219Scy return 0; 354254219Scy} 355254219Scy 356254219Scystruct tree_opt_pass pass_record_bounds = 357254219Scy{ 358254219Scy NULL, /* name */ 359254219Scy NULL, /* gate */ 360254219Scy tree_ssa_loop_bounds, /* execute */ 361254219Scy NULL, /* sub */ 362254219Scy NULL, /* next */ 363254219Scy 0, /* static_pass_number */ 364254219Scy TV_TREE_LOOP_BOUNDS, /* tv_id */ 365254219Scy PROP_cfg | PROP_ssa, /* properties_required */ 366254219Scy 0, /* properties_provided */ 367254219Scy 0, /* properties_destroyed */ 368254219Scy 0, /* todo_flags_start */ 369254219Scy 0, /* todo_flags_finish */ 370254219Scy 0 /* letter */ 371254219Scy}; 372254219Scy 373254219Scy/* Complete unrolling of loops. */ 374254219Scy 375254219Scystatic unsigned int 376254219Scytree_complete_unroll (void) 377254219Scy{ 378254219Scy if (!current_loops) 379254219Scy return 0; 380254219Scy 381254219Scy return tree_unroll_loops_completely (current_loops, 382254219Scy flag_unroll_loops 383254219Scy || flag_peel_loops 384254219Scy || optimize >= 3); 385254219Scy} 386254219Scy 387254219Scystatic bool 388254219Scygate_tree_complete_unroll (void) 389254219Scy{ 390254219Scy return true; 391254219Scy} 392254219Scy 393254219Scystruct tree_opt_pass pass_complete_unroll = 394254219Scy{ 395254219Scy "cunroll", /* name */ 396254219Scy gate_tree_complete_unroll, /* gate */ 397254219Scy tree_complete_unroll, /* execute */ 398254219Scy NULL, /* sub */ 399254219Scy NULL, /* next */ 400254219Scy 0, /* static_pass_number */ 401254219Scy TV_COMPLETE_UNROLL, /* tv_id */ 402254219Scy PROP_cfg | PROP_ssa, /* properties_required */ 403254219Scy 0, /* properties_provided */ 404254219Scy 0, /* properties_destroyed */ 405254219Scy 0, /* todo_flags_start */ 406254219Scy TODO_dump_func | TODO_verify_loops, /* todo_flags_finish */ 407254219Scy 0 /* letter */ 408254219Scy}; 409254219Scy 410254219Scy/* Prefetching. */ 411254219Scy 412254219Scystatic unsigned int 413254219Scytree_ssa_loop_prefetch (void) 414254219Scy{ 415254219Scy if (!current_loops) 416254219Scy return 0; 417254219Scy 418254219Scy return tree_ssa_prefetch_arrays (current_loops); 419254219Scy} 420254219Scy 421254219Scystatic bool 422254219Scygate_tree_ssa_loop_prefetch (void) 423254219Scy{ 424254219Scy return flag_prefetch_loop_arrays != 0; 425254219Scy} 426254219Scy 427254219Scystruct tree_opt_pass pass_loop_prefetch = 428254219Scy{ 429254219Scy "prefetch", /* name */ 430254219Scy gate_tree_ssa_loop_prefetch, /* gate */ 431254219Scy tree_ssa_loop_prefetch, /* execute */ 432254219Scy NULL, /* sub */ 433254219Scy NULL, /* next */ 434254219Scy 0, /* static_pass_number */ 435254219Scy TV_TREE_PREFETCH, /* tv_id */ 436254219Scy PROP_cfg | PROP_ssa, /* properties_required */ 437254219Scy 0, /* properties_provided */ 438254219Scy 0, /* properties_destroyed */ 439254219Scy 0, /* todo_flags_start */ 440254219Scy TODO_dump_func | TODO_verify_loops, /* todo_flags_finish */ 441254219Scy 0 /* letter */ 442254219Scy}; 443254219Scy 444254219Scy/* Induction variable optimizations. */ 445254219Scy 446254219Scystatic unsigned int 447254219Scytree_ssa_loop_ivopts (void) 448254219Scy{ 449254219Scy if (!current_loops) 450254219Scy return 0; 451254219Scy 452254219Scy tree_ssa_iv_optimize (current_loops); 453254219Scy return 0; 454254219Scy} 455254219Scy 456254219Scystatic bool 457254219Scygate_tree_ssa_loop_ivopts (void) 458254219Scy{ 459254219Scy return flag_ivopts != 0; 460254219Scy} 461254219Scy 462254219Scystruct tree_opt_pass pass_iv_optimize = 463254219Scy{ 464254219Scy "ivopts", /* name */ 465254219Scy gate_tree_ssa_loop_ivopts, /* gate */ 466254219Scy tree_ssa_loop_ivopts, /* execute */ 467254219Scy NULL, /* sub */ 468254219Scy NULL, /* next */ 469254219Scy 0, /* static_pass_number */ 470254219Scy TV_TREE_LOOP_IVOPTS, /* tv_id */ 471254219Scy PROP_cfg | PROP_ssa, /* properties_required */ 472254219Scy 0, /* properties_provided */ 473254219Scy 0, /* properties_destroyed */ 474254219Scy 0, /* todo_flags_start */ 475254219Scy TODO_dump_func 476254219Scy | TODO_verify_loops 477254219Scy | TODO_update_ssa, /* todo_flags_finish */ 478254219Scy 0 /* letter */ 479254219Scy}; 480254219Scy 481254219Scy/* Loop optimizer finalization. */ 482254219Scy 483254219Scystatic unsigned int 484254219Scytree_ssa_loop_done (void) 485254219Scy{ 486254219Scy if (!current_loops) 487254219Scy return 0; 488254219Scy 489254219Scy free_numbers_of_iterations_estimates (current_loops); 490254219Scy scev_finalize (); 491254219Scy loop_optimizer_finalize (current_loops); 492254219Scy current_loops = NULL; 493254219Scy return 0; 494254219Scy} 495254219Scy 496254219Scystruct tree_opt_pass pass_tree_loop_done = 497254219Scy{ 498254219Scy "loopdone", /* name */ 499254219Scy NULL, /* gate */ 500254219Scy tree_ssa_loop_done, /* execute */ 501254219Scy NULL, /* sub */ 502254219Scy NULL, /* next */ 503254219Scy 0, /* static_pass_number */ 504254219Scy TV_TREE_LOOP_FINI, /* tv_id */ 505254219Scy PROP_cfg, /* properties_required */ 506254219Scy 0, /* properties_provided */ 507254219Scy 0, /* properties_destroyed */ 508254219Scy 0, /* todo_flags_start */ 509254219Scy TODO_cleanup_cfg | TODO_dump_func, /* todo_flags_finish */ 510254219Scy 0 /* letter */ 511254219Scy}; 512254219Scy