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. DUMP is the file to that the details 46 about the analysis should be dumped. */ 47 48static struct loops * 49tree_loop_optimizer_init (FILE *dump) 50{ 51 struct loops *loops = loop_optimizer_init (dump); 52 53 if (!loops) 54 return NULL; 55 56 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa); 57 58 return loops; 59} 60 61/* The loop superpass. */ 62 63static bool 64gate_tree_loop (void) 65{ 66 return flag_tree_loop_optimize != 0; 67} 68 69struct tree_opt_pass pass_tree_loop = 70{ 71 "loop", /* name */ 72 gate_tree_loop, /* gate */ 73 NULL, /* execute */ 74 NULL, /* sub */ 75 NULL, /* next */ 76 0, /* static_pass_number */ 77 TV_TREE_LOOP, /* tv_id */ 78 PROP_cfg, /* properties_required */ 79 0, /* properties_provided */ 80 0, /* properties_destroyed */ 81 TODO_ggc_collect, /* todo_flags_start */ 82 TODO_dump_func | TODO_verify_ssa | TODO_ggc_collect, /* todo_flags_finish */ 83 0 /* letter */ 84}; 85 86/* Loop optimizer initialization. */ 87 88static void 89tree_ssa_loop_init (void) 90{ 91 current_loops = tree_loop_optimizer_init (dump_file); 92 if (!current_loops) 93 return; 94 95 /* Find the loops that are exited just through a single edge. */ 96 mark_single_exit_loops (current_loops); 97 98 scev_initialize (current_loops); 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 void 121tree_ssa_loop_im (void) 122{ 123 if (!current_loops) 124 return; 125 126 tree_ssa_lim (current_loops); 127} 128 129static bool 130gate_tree_ssa_loop_im (void) 131{ 132 return flag_tree_loop_im != 0; 133} 134 135struct tree_opt_pass pass_lim = 136{ 137 "lim", /* name */ 138 gate_tree_ssa_loop_im, /* gate */ 139 tree_ssa_loop_im, /* execute */ 140 NULL, /* sub */ 141 NULL, /* next */ 142 0, /* static_pass_number */ 143 TV_LIM, /* tv_id */ 144 PROP_cfg, /* properties_required */ 145 0, /* properties_provided */ 146 0, /* properties_destroyed */ 147 0, /* todo_flags_start */ 148 TODO_dump_func | TODO_verify_loops, /* todo_flags_finish */ 149 0 /* letter */ 150}; 151 152/* Loop unswitching pass. */ 153 154static void 155tree_ssa_loop_unswitch (void) 156{ 157 if (!current_loops) 158 return; 159 160 tree_ssa_unswitch_loops (current_loops); 161} 162 163static bool 164gate_tree_ssa_loop_unswitch (void) 165{ 166 return flag_unswitch_loops != 0; 167} 168 169struct tree_opt_pass pass_tree_unswitch = 170{ 171 "unswitch", /* name */ 172 gate_tree_ssa_loop_unswitch, /* gate */ 173 tree_ssa_loop_unswitch, /* execute */ 174 NULL, /* sub */ 175 NULL, /* next */ 176 0, /* static_pass_number */ 177 TV_TREE_LOOP_UNSWITCH, /* tv_id */ 178 PROP_cfg, /* properties_required */ 179 0, /* properties_provided */ 180 0, /* properties_destroyed */ 181 0, /* todo_flags_start */ 182 TODO_dump_func | TODO_verify_loops, /* todo_flags_finish */ 183 0 /* letter */ 184}; 185 186/* Loop autovectorization. */ 187 188static void 189tree_vectorize (void) 190{ 191 vectorize_loops (current_loops); 192} 193 194static bool 195gate_tree_vectorize (void) 196{ 197 return flag_tree_vectorize && current_loops; 198} 199 200struct tree_opt_pass pass_vectorize = 201{ 202 "vect", /* name */ 203 gate_tree_vectorize, /* gate */ 204 tree_vectorize, /* execute */ 205 NULL, /* sub */ 206 NULL, /* next */ 207 0, /* static_pass_number */ 208 TV_TREE_VECTORIZATION, /* tv_id */ 209 PROP_cfg | PROP_ssa, /* properties_required */ 210 0, /* properties_provided */ 211 0, /* properties_destroyed */ 212 TODO_verify_loops, /* todo_flags_start */ 213 TODO_dump_func | TODO_update_ssa, /* todo_flags_finish */ 214 0 /* letter */ 215}; 216 217/* Loop nest optimizations. */ 218 219static void 220tree_linear_transform (void) 221{ 222 if (!current_loops) 223 return; 224 225 linear_transform_loops (current_loops); 226} 227 228static bool 229gate_tree_linear_transform (void) 230{ 231 return flag_tree_loop_linear != 0; 232} 233 234struct tree_opt_pass pass_linear_transform = 235{ 236 "ltrans", /* name */ 237 gate_tree_linear_transform, /* gate */ 238 tree_linear_transform, /* execute */ 239 NULL, /* sub */ 240 NULL, /* next */ 241 0, /* static_pass_number */ 242 TV_TREE_LINEAR_TRANSFORM, /* tv_id */ 243 PROP_cfg | PROP_ssa, /* properties_required */ 244 0, /* properties_provided */ 245 0, /* properties_destroyed */ 246 0, /* todo_flags_start */ 247 TODO_dump_func | TODO_verify_loops, /* todo_flags_finish */ 248 0 /* letter */ 249}; 250 251/* Canonical induction variable creation pass. */ 252 253static void 254tree_ssa_loop_ivcanon (void) 255{ 256 if (!current_loops) 257 return; 258 259 canonicalize_induction_variables (current_loops); 260} 261 262static bool 263gate_tree_ssa_loop_ivcanon (void) 264{ 265 return flag_tree_loop_ivcanon != 0; 266} 267 268struct tree_opt_pass pass_iv_canon = 269{ 270 "ivcanon", /* name */ 271 gate_tree_ssa_loop_ivcanon, /* gate */ 272 tree_ssa_loop_ivcanon, /* execute */ 273 NULL, /* sub */ 274 NULL, /* next */ 275 0, /* static_pass_number */ 276 TV_TREE_LOOP_IVCANON, /* tv_id */ 277 PROP_cfg | PROP_ssa, /* properties_required */ 278 0, /* properties_provided */ 279 0, /* properties_destroyed */ 280 0, /* todo_flags_start */ 281 TODO_dump_func | TODO_verify_loops, /* todo_flags_finish */ 282 0 /* letter */ 283}; 284 285/* Propagation of constants using scev. */ 286 287static bool 288gate_scev_const_prop (void) 289{ 290 return true; 291} 292 293struct tree_opt_pass pass_scev_cprop = 294{ 295 "sccp", /* name */ 296 gate_scev_const_prop, /* gate */ 297 scev_const_prop, /* execute */ 298 NULL, /* sub */ 299 NULL, /* next */ 300 0, /* static_pass_number */ 301 TV_SCEV_CONST, /* tv_id */ 302 PROP_cfg | PROP_ssa, /* properties_required */ 303 0, /* properties_provided */ 304 0, /* properties_destroyed */ 305 0, /* todo_flags_start */ 306 TODO_dump_func | TODO_cleanup_cfg 307 | TODO_update_ssa_only_virtuals, 308 /* todo_flags_finish */ 309 0 /* letter */ 310}; 311 312/* Remove empty loops. */ 313 314static void 315tree_ssa_empty_loop (void) 316{ 317 if (!current_loops) 318 return; 319 320 remove_empty_loops (current_loops); 321} 322 323struct tree_opt_pass pass_empty_loop = 324{ 325 "empty", /* name */ 326 NULL, /* gate */ 327 tree_ssa_empty_loop, /* execute */ 328 NULL, /* sub */ 329 NULL, /* next */ 330 0, /* static_pass_number */ 331 TV_COMPLETE_UNROLL, /* tv_id */ 332 PROP_cfg | PROP_ssa, /* properties_required */ 333 0, /* properties_provided */ 334 0, /* properties_destroyed */ 335 0, /* todo_flags_start */ 336 TODO_dump_func | TODO_verify_loops, /* todo_flags_finish */ 337 0 /* letter */ 338}; 339 340/* Record bounds on numbers of iterations of loops. */ 341 342static void 343tree_ssa_loop_bounds (void) 344{ 345 if (!current_loops) 346 return; 347 348 estimate_numbers_of_iterations (current_loops); 349 scev_reset (); 350} 351 352struct tree_opt_pass pass_record_bounds = 353{ 354 NULL, /* name */ 355 NULL, /* gate */ 356 tree_ssa_loop_bounds, /* execute */ 357 NULL, /* sub */ 358 NULL, /* next */ 359 0, /* static_pass_number */ 360 TV_TREE_LOOP_BOUNDS, /* tv_id */ 361 PROP_cfg | PROP_ssa, /* properties_required */ 362 0, /* properties_provided */ 363 0, /* properties_destroyed */ 364 0, /* todo_flags_start */ 365 0, /* todo_flags_finish */ 366 0 /* letter */ 367}; 368 369/* Complete unrolling of loops. */ 370 371static void 372tree_complete_unroll (void) 373{ 374 if (!current_loops) 375 return; 376 377 tree_unroll_loops_completely (current_loops, 378 flag_unroll_loops 379 || flag_peel_loops 380 || optimize >= 3); 381} 382 383static bool 384gate_tree_complete_unroll (void) 385{ 386 return true; 387} 388 389struct tree_opt_pass pass_complete_unroll = 390{ 391 "cunroll", /* name */ 392 gate_tree_complete_unroll, /* gate */ 393 tree_complete_unroll, /* execute */ 394 NULL, /* sub */ 395 NULL, /* next */ 396 0, /* static_pass_number */ 397 TV_COMPLETE_UNROLL, /* tv_id */ 398 PROP_cfg | PROP_ssa, /* properties_required */ 399 0, /* properties_provided */ 400 0, /* properties_destroyed */ 401 0, /* todo_flags_start */ 402 TODO_dump_func | TODO_verify_loops, /* todo_flags_finish */ 403 0 /* letter */ 404}; 405 406/* Induction variable optimizations. */ 407 408static void 409tree_ssa_loop_ivopts (void) 410{ 411 if (!current_loops) 412 return; 413 414 tree_ssa_iv_optimize (current_loops); 415} 416 417static bool 418gate_tree_ssa_loop_ivopts (void) 419{ 420 return flag_ivopts != 0; 421} 422 423struct tree_opt_pass pass_iv_optimize = 424{ 425 "ivopts", /* name */ 426 gate_tree_ssa_loop_ivopts, /* gate */ 427 tree_ssa_loop_ivopts, /* execute */ 428 NULL, /* sub */ 429 NULL, /* next */ 430 0, /* static_pass_number */ 431 TV_TREE_LOOP_IVOPTS, /* tv_id */ 432 PROP_cfg | PROP_ssa, /* properties_required */ 433 0, /* properties_provided */ 434 0, /* properties_destroyed */ 435 0, /* todo_flags_start */ 436 TODO_dump_func | TODO_verify_loops, /* todo_flags_finish */ 437 0 /* letter */ 438}; 439 440/* Loop optimizer finalization. */ 441 442static void 443tree_ssa_loop_done (void) 444{ 445 if (!current_loops) 446 return; 447 448 free_numbers_of_iterations_estimates (current_loops); 449 scev_finalize (); 450 loop_optimizer_finalize (current_loops, 451 (dump_flags & TDF_DETAILS ? dump_file : NULL)); 452 current_loops = NULL; 453} 454 455struct tree_opt_pass pass_tree_loop_done = 456{ 457 "loopdone", /* name */ 458 NULL, /* gate */ 459 tree_ssa_loop_done, /* execute */ 460 NULL, /* sub */ 461 NULL, /* next */ 462 0, /* static_pass_number */ 463 TV_TREE_LOOP_FINI, /* tv_id */ 464 PROP_cfg, /* properties_required */ 465 0, /* properties_provided */ 466 0, /* properties_destroyed */ 467 0, /* todo_flags_start */ 468 TODO_cleanup_cfg | TODO_dump_func, /* todo_flags_finish */ 469 0 /* letter */ 470}; 471