1/* Loop optimizations over tree-ssa. 2 Copyright (C) 2003, 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 7under the terms of the GNU General Public License as published by the 8Free Software Foundation; either version 2, or (at your option) any 9later version. 10 11GCC is distributed in the hope that it will be useful, but WITHOUT 12ANY WARRANTY; 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 "tree.h" 26#include "rtl.h" 27#include "tm_p.h" 28#include "hard-reg-set.h" 29#include "basic-block.h" 30#include "output.h" 31#include "diagnostic.h" 32#include "tree-flow.h" 33#include "tree-dump.h" 34#include "tree-pass.h" 35#include "timevar.h" 36#include "cfgloop.h" 37#include "flags.h" 38#include "tree-inline.h" 39#include "tree-scalar-evolution.h" 40 41/* The loop tree currently optimized. */ 42 43struct loops *current_loops = NULL; 44 45/* Initializes the loop structures. */ 46 47static struct loops * 48tree_loop_optimizer_init (void) 49{ 50 struct loops *loops; 51 52 loops = loop_optimizer_init (LOOPS_NORMAL 53 | LOOPS_HAVE_MARKED_SINGLE_EXITS); 54 55 if (!loops) 56 return NULL; 57 58 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa); 59 60 return loops; 61} 62 63/* The loop superpass. */ 64 65static bool 66gate_tree_loop (void) 67{ 68 return flag_tree_loop_optimize != 0; 69} 70 71struct tree_opt_pass pass_tree_loop = 72{ 73 "loop", /* name */ 74 gate_tree_loop, /* gate */ 75 NULL, /* execute */ 76 NULL, /* sub */ 77 NULL, /* next */ 78 0, /* static_pass_number */ 79 TV_TREE_LOOP, /* tv_id */ 80 PROP_cfg, /* properties_required */ 81 0, /* properties_provided */ 82 0, /* properties_destroyed */ 83 TODO_ggc_collect, /* todo_flags_start */ 84 TODO_dump_func | TODO_verify_ssa | TODO_ggc_collect, /* todo_flags_finish */ 85 0 /* letter */ 86}; 87 88/* Loop optimizer initialization. */ 89 90static unsigned int 91tree_ssa_loop_init (void) 92{ 93 current_loops = tree_loop_optimizer_init (); 94 if (!current_loops) 95 return 0; 96 97 scev_initialize (current_loops); 98 return 0; 99} 100 101struct tree_opt_pass pass_tree_loop_init = 102{ 103 "loopinit", /* name */ 104 NULL, /* gate */ 105 tree_ssa_loop_init, /* execute */ 106 NULL, /* sub */ 107 NULL, /* next */ 108 0, /* static_pass_number */ 109 TV_TREE_LOOP_INIT, /* tv_id */ 110 PROP_cfg, /* properties_required */ 111 0, /* properties_provided */ 112 0, /* properties_destroyed */ 113 0, /* todo_flags_start */ 114 TODO_dump_func | TODO_verify_loops, /* todo_flags_finish */ 115 0 /* letter */ 116}; 117 118/* Loop invariant motion pass. */ 119 120static unsigned int 121tree_ssa_loop_im (void) 122{ 123 if (!current_loops) 124 return 0; 125 126 tree_ssa_lim (current_loops); 127 return 0; 128} 129 130static bool 131gate_tree_ssa_loop_im (void) 132{ 133 return flag_tree_loop_im != 0; 134} 135 136struct tree_opt_pass pass_lim = 137{ 138 "lim", /* name */ 139 gate_tree_ssa_loop_im, /* gate */ 140 tree_ssa_loop_im, /* execute */ 141 NULL, /* sub */ 142 NULL, /* next */ 143 0, /* static_pass_number */ 144 TV_LIM, /* tv_id */ 145 PROP_cfg, /* properties_required */ 146 0, /* properties_provided */ 147 0, /* properties_destroyed */ 148 0, /* todo_flags_start */ 149 TODO_dump_func | TODO_verify_loops, /* todo_flags_finish */ 150 0 /* letter */ 151}; 152 153/* Loop unswitching pass. */ 154 155static unsigned int 156tree_ssa_loop_unswitch (void) 157{ 158 if (!current_loops) 159 return 0; 160 161 return tree_ssa_unswitch_loops (current_loops); 162} 163 164static bool 165gate_tree_ssa_loop_unswitch (void) 166{ 167 return flag_unswitch_loops != 0; 168} 169 170struct tree_opt_pass pass_tree_unswitch = 171{ 172 "unswitch", /* name */ 173 gate_tree_ssa_loop_unswitch, /* gate */ 174 tree_ssa_loop_unswitch, /* execute */ 175 NULL, /* sub */ 176 NULL, /* next */ 177 0, /* static_pass_number */ 178 TV_TREE_LOOP_UNSWITCH, /* tv_id */ 179 PROP_cfg, /* properties_required */ 180 0, /* properties_provided */ 181 0, /* properties_destroyed */ 182 0, /* todo_flags_start */ 183 TODO_dump_func | TODO_verify_loops, /* todo_flags_finish */ 184 0 /* letter */ 185}; 186 187/* Loop autovectorization. */ 188 189static unsigned int 190tree_vectorize (void) 191{ 192 vectorize_loops (current_loops); 193 return 0; 194} 195 196static bool 197gate_tree_vectorize (void) 198{ 199 return flag_tree_vectorize && current_loops; 200} 201 202struct tree_opt_pass pass_vectorize = 203{ 204 "vect", /* name */ 205 gate_tree_vectorize, /* gate */ 206 tree_vectorize, /* execute */ 207 NULL, /* sub */ 208 NULL, /* next */ 209 0, /* static_pass_number */ 210 TV_TREE_VECTORIZATION, /* tv_id */ 211 PROP_cfg | PROP_ssa, /* properties_required */ 212 0, /* properties_provided */ 213 0, /* properties_destroyed */ 214 TODO_verify_loops, /* todo_flags_start */ 215 TODO_dump_func | TODO_update_ssa, /* todo_flags_finish */ 216 0 /* letter */ 217}; 218 219/* Loop nest optimizations. */ 220 221static unsigned int 222tree_linear_transform (void) 223{ 224 if (!current_loops) 225 return 0; 226 227 linear_transform_loops (current_loops); 228 return 0; 229} 230 231static bool 232gate_tree_linear_transform (void) 233{ 234 return flag_tree_loop_linear != 0; 235} 236 237struct tree_opt_pass pass_linear_transform = 238{ 239 "ltrans", /* name */ 240 gate_tree_linear_transform, /* gate */ 241 tree_linear_transform, /* execute */ 242 NULL, /* sub */ 243 NULL, /* next */ 244 0, /* static_pass_number */ 245 TV_TREE_LINEAR_TRANSFORM, /* tv_id */ 246 PROP_cfg | PROP_ssa, /* properties_required */ 247 0, /* properties_provided */ 248 0, /* properties_destroyed */ 249 0, /* todo_flags_start */ 250 TODO_dump_func | TODO_verify_loops, /* todo_flags_finish */ 251 0 /* letter */ 252}; 253 254/* Canonical induction variable creation pass. */ 255 256static unsigned int 257tree_ssa_loop_ivcanon (void) 258{ 259 if (!current_loops) 260 return 0; 261 262 return canonicalize_induction_variables (current_loops); 263} 264 265static bool 266gate_tree_ssa_loop_ivcanon (void) 267{ 268 return flag_tree_loop_ivcanon != 0; 269} 270 271struct tree_opt_pass pass_iv_canon = 272{ 273 "ivcanon", /* name */ 274 gate_tree_ssa_loop_ivcanon, /* gate */ 275 tree_ssa_loop_ivcanon, /* execute */ 276 NULL, /* sub */ 277 NULL, /* next */ 278 0, /* static_pass_number */ 279 TV_TREE_LOOP_IVCANON, /* tv_id */ 280 PROP_cfg | PROP_ssa, /* properties_required */ 281 0, /* properties_provided */ 282 0, /* properties_destroyed */ 283 0, /* todo_flags_start */ 284 TODO_dump_func | TODO_verify_loops, /* todo_flags_finish */ 285 0 /* letter */ 286}; 287 288/* Propagation of constants using scev. */ 289 290static bool 291gate_scev_const_prop (void) 292{ 293 return true; 294} 295 296struct tree_opt_pass pass_scev_cprop = 297{ 298 "sccp", /* name */ 299 gate_scev_const_prop, /* gate */ 300 scev_const_prop, /* execute */ 301 NULL, /* sub */ 302 NULL, /* next */ 303 0, /* static_pass_number */ 304 TV_SCEV_CONST, /* tv_id */ 305 PROP_cfg | PROP_ssa, /* properties_required */ 306 0, /* properties_provided */ 307 0, /* properties_destroyed */ 308 0, /* todo_flags_start */ 309 TODO_dump_func | TODO_cleanup_cfg 310 | TODO_update_ssa_only_virtuals, 311 /* todo_flags_finish */ 312 0 /* letter */ 313}; 314 315/* Remove empty loops. */ 316 317static unsigned int 318tree_ssa_empty_loop (void) 319{ 320 if (!current_loops) 321 return 0; 322 323 return remove_empty_loops (current_loops); 324} 325 326struct tree_opt_pass pass_empty_loop = 327{ 328 "empty", /* name */ 329 NULL, /* gate */ 330 tree_ssa_empty_loop, /* execute */ 331 NULL, /* sub */ 332 NULL, /* next */ 333 0, /* static_pass_number */ 334 TV_COMPLETE_UNROLL, /* tv_id */ 335 PROP_cfg | PROP_ssa, /* properties_required */ 336 0, /* properties_provided */ 337 0, /* properties_destroyed */ 338 0, /* todo_flags_start */ 339 TODO_dump_func | TODO_verify_loops, /* todo_flags_finish */ 340 0 /* letter */ 341}; 342 343/* Record bounds on numbers of iterations of loops. */ 344 345static unsigned int 346tree_ssa_loop_bounds (void) 347{ 348 if (!current_loops) 349 return 0; 350 351 estimate_numbers_of_iterations (current_loops); 352 scev_reset (); 353 return 0; 354} 355 356struct tree_opt_pass pass_record_bounds = 357{ 358 NULL, /* name */ 359 NULL, /* gate */ 360 tree_ssa_loop_bounds, /* execute */ 361 NULL, /* sub */ 362 NULL, /* next */ 363 0, /* static_pass_number */ 364 TV_TREE_LOOP_BOUNDS, /* tv_id */ 365 PROP_cfg | PROP_ssa, /* properties_required */ 366 0, /* properties_provided */ 367 0, /* properties_destroyed */ 368 0, /* todo_flags_start */ 369 0, /* todo_flags_finish */ 370 0 /* letter */ 371}; 372 373/* Complete unrolling of loops. */ 374 375static unsigned int 376tree_complete_unroll (void) 377{ 378 if (!current_loops) 379 return 0; 380 381 return tree_unroll_loops_completely (current_loops, 382 flag_unroll_loops 383 || flag_peel_loops 384 || optimize >= 3); 385} 386 387static bool 388gate_tree_complete_unroll (void) 389{ 390 return true; 391} 392 393struct tree_opt_pass pass_complete_unroll = 394{ 395 "cunroll", /* name */ 396 gate_tree_complete_unroll, /* gate */ 397 tree_complete_unroll, /* execute */ 398 NULL, /* sub */ 399 NULL, /* next */ 400 0, /* static_pass_number */ 401 TV_COMPLETE_UNROLL, /* tv_id */ 402 PROP_cfg | PROP_ssa, /* properties_required */ 403 0, /* properties_provided */ 404 0, /* properties_destroyed */ 405 0, /* todo_flags_start */ 406 TODO_dump_func | TODO_verify_loops, /* todo_flags_finish */ 407 0 /* letter */ 408}; 409 410/* Prefetching. */ 411 412static unsigned int 413tree_ssa_loop_prefetch (void) 414{ 415 if (!current_loops) 416 return 0; 417 418 return tree_ssa_prefetch_arrays (current_loops); 419} 420 421static bool 422gate_tree_ssa_loop_prefetch (void) 423{ 424 return flag_prefetch_loop_arrays != 0; 425} 426 427struct tree_opt_pass pass_loop_prefetch = 428{ 429 "prefetch", /* name */ 430 gate_tree_ssa_loop_prefetch, /* gate */ 431 tree_ssa_loop_prefetch, /* execute */ 432 NULL, /* sub */ 433 NULL, /* next */ 434 0, /* static_pass_number */ 435 TV_TREE_PREFETCH, /* tv_id */ 436 PROP_cfg | PROP_ssa, /* properties_required */ 437 0, /* properties_provided */ 438 0, /* properties_destroyed */ 439 0, /* todo_flags_start */ 440 TODO_dump_func | TODO_verify_loops, /* todo_flags_finish */ 441 0 /* letter */ 442}; 443 444/* Induction variable optimizations. */ 445 446static unsigned int 447tree_ssa_loop_ivopts (void) 448{ 449 if (!current_loops) 450 return 0; 451 452 tree_ssa_iv_optimize (current_loops); 453 return 0; 454} 455 456static bool 457gate_tree_ssa_loop_ivopts (void) 458{ 459 return flag_ivopts != 0; 460} 461 462struct tree_opt_pass pass_iv_optimize = 463{ 464 "ivopts", /* name */ 465 gate_tree_ssa_loop_ivopts, /* gate */ 466 tree_ssa_loop_ivopts, /* execute */ 467 NULL, /* sub */ 468 NULL, /* next */ 469 0, /* static_pass_number */ 470 TV_TREE_LOOP_IVOPTS, /* tv_id */ 471 PROP_cfg | PROP_ssa, /* properties_required */ 472 0, /* properties_provided */ 473 0, /* properties_destroyed */ 474 0, /* todo_flags_start */ 475 TODO_dump_func 476 | TODO_verify_loops 477 | TODO_update_ssa, /* todo_flags_finish */ 478 0 /* letter */ 479}; 480 481/* Loop optimizer finalization. */ 482 483static unsigned int 484tree_ssa_loop_done (void) 485{ 486 if (!current_loops) 487 return 0; 488 489 free_numbers_of_iterations_estimates (current_loops); 490 scev_finalize (); 491 loop_optimizer_finalize (current_loops); 492 current_loops = NULL; 493 return 0; 494} 495 496struct tree_opt_pass pass_tree_loop_done = 497{ 498 "loopdone", /* name */ 499 NULL, /* gate */ 500 tree_ssa_loop_done, /* execute */ 501 NULL, /* sub */ 502 NULL, /* next */ 503 0, /* static_pass_number */ 504 TV_TREE_LOOP_FINI, /* tv_id */ 505 PROP_cfg, /* properties_required */ 506 0, /* properties_provided */ 507 0, /* properties_destroyed */ 508 0, /* todo_flags_start */ 509 TODO_cleanup_cfg | TODO_dump_func, /* todo_flags_finish */ 510 0 /* letter */ 511}; 512