1/* Induction variable canonicalization. 2 Copyright (C) 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 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/* This pass detects the loops that iterate a constant number of times, 22 adds a canonical induction variable (step -1, tested against 0) 23 and replaces the exit test. This enables the less powerful rtl 24 level analysis to use this information. 25 26 This might spoil the code in some cases (by increasing register pressure). 27 Note that in the case the new variable is not needed, ivopts will get rid 28 of it, so it might only be a problem when there are no other linear induction 29 variables. In that case the created optimization possibilities are likely 30 to pay up. 31 32 Additionally in case we detect that it is beneficial to unroll the 33 loop completely, we do it right here to expose the optimization 34 possibilities to the following passes. */ 35 36#include "config.h" 37#include "system.h" 38#include "coretypes.h" 39#include "tm.h" 40#include "tree.h" 41#include "rtl.h" 42#include "tm_p.h" 43#include "hard-reg-set.h" 44#include "basic-block.h" 45#include "output.h" 46#include "diagnostic.h" 47#include "tree-flow.h" 48#include "tree-dump.h" 49#include "cfgloop.h" 50#include "tree-pass.h" 51#include "ggc.h" 52#include "tree-chrec.h" 53#include "tree-scalar-evolution.h" 54#include "params.h" 55#include "flags.h" 56#include "tree-inline.h" 57 58/* Specifies types of loops that may be unrolled. */ 59 60enum unroll_level 61{ 62 UL_SINGLE_ITER, /* Only loops that exit immediately in the first 63 iteration. */ 64 UL_NO_GROWTH, /* Only loops whose unrolling will not cause increase 65 of code size. */ 66 UL_ALL /* All suitable loops. */ 67}; 68 69/* Adds a canonical induction variable to LOOP iterating NITER times. EXIT 70 is the exit edge whose condition is replaced. */ 71 72static void 73create_canonical_iv (struct loop *loop, edge exit, tree niter) 74{ 75 edge in; 76 tree cond, type, var; 77 block_stmt_iterator incr_at; 78 enum tree_code cmp; 79 80 if (dump_file && (dump_flags & TDF_DETAILS)) 81 { 82 fprintf (dump_file, "Added canonical iv to loop %d, ", loop->num); 83 print_generic_expr (dump_file, niter, TDF_SLIM); 84 fprintf (dump_file, " iterations.\n"); 85 } 86 87 cond = last_stmt (exit->src); 88 in = EDGE_SUCC (exit->src, 0); 89 if (in == exit) 90 in = EDGE_SUCC (exit->src, 1); 91 92 /* Note that we do not need to worry about overflows, since 93 type of niter is always unsigned and all comparisons are 94 just for equality/nonequality -- i.e. everything works 95 with a modulo arithmetics. */ 96 97 type = TREE_TYPE (niter); 98 niter = fold_build2 (PLUS_EXPR, type, 99 niter, 100 build_int_cst (type, 1)); 101 incr_at = bsi_last (in->src); 102 create_iv (niter, 103 fold_convert (type, integer_minus_one_node), 104 NULL_TREE, loop, 105 &incr_at, false, NULL, &var); 106 107 cmp = (exit->flags & EDGE_TRUE_VALUE) ? EQ_EXPR : NE_EXPR; 108 COND_EXPR_COND (cond) = build2 (cmp, boolean_type_node, 109 var, 110 build_int_cst (type, 0)); 111 update_stmt (cond); 112} 113 114/* Computes an estimated number of insns in LOOP. */ 115 116unsigned 117tree_num_loop_insns (struct loop *loop) 118{ 119 basic_block *body = get_loop_body (loop); 120 block_stmt_iterator bsi; 121 unsigned size = 1, i; 122 123 for (i = 0; i < loop->num_nodes; i++) 124 for (bsi = bsi_start (body[i]); !bsi_end_p (bsi); bsi_next (&bsi)) 125 size += estimate_num_insns (bsi_stmt (bsi)); 126 free (body); 127 128 return size; 129} 130 131/* Estimate number of insns of completely unrolled loop. We assume 132 that the size of the unrolled loop is decreased in the 133 following way (the numbers of insns are based on what 134 estimate_num_insns returns for appropriate statements): 135 136 1) exit condition gets removed (2 insns) 137 2) increment of the control variable gets removed (2 insns) 138 3) All remaining statements are likely to get simplified 139 due to constant propagation. Hard to estimate; just 140 as a heuristics we decrease the rest by 1/3. 141 142 NINSNS is the number of insns in the loop before unrolling. 143 NUNROLL is the number of times the loop is unrolled. */ 144 145static unsigned HOST_WIDE_INT 146estimated_unrolled_size (unsigned HOST_WIDE_INT ninsns, 147 unsigned HOST_WIDE_INT nunroll) 148{ 149 HOST_WIDE_INT unr_insns = 2 * ((HOST_WIDE_INT) ninsns - 4) / 3; 150 if (unr_insns <= 0) 151 unr_insns = 1; 152 unr_insns *= (nunroll + 1); 153 154 return unr_insns; 155} 156 157/* Tries to unroll LOOP completely, i.e. NITER times. LOOPS is the 158 loop tree. UL determines which loops we are allowed to unroll. 159 EXIT is the exit of the loop that should be eliminated. */ 160 161static bool 162try_unroll_loop_completely (struct loops *loops ATTRIBUTE_UNUSED, 163 struct loop *loop, 164 edge exit, tree niter, 165 enum unroll_level ul) 166{ 167 unsigned HOST_WIDE_INT n_unroll, ninsns, max_unroll, unr_insns; 168 tree old_cond, cond, dont_exit, do_exit; 169 170 if (loop->inner) 171 return false; 172 173 if (!host_integerp (niter, 1)) 174 return false; 175 n_unroll = tree_low_cst (niter, 1); 176 177 max_unroll = PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES); 178 if (n_unroll > max_unroll) 179 return false; 180 181 if (n_unroll) 182 { 183 if (ul == UL_SINGLE_ITER) 184 return false; 185 186 ninsns = tree_num_loop_insns (loop); 187 188 if (n_unroll * ninsns 189 > (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS)) 190 return false; 191 192 if (ul == UL_NO_GROWTH) 193 { 194 unr_insns = estimated_unrolled_size (ninsns, n_unroll); 195 196 if (dump_file && (dump_flags & TDF_DETAILS)) 197 { 198 fprintf (dump_file, " Loop size: %d\n", (int) ninsns); 199 fprintf (dump_file, " Estimated size after unrolling: %d\n", 200 (int) unr_insns); 201 } 202 203 if (unr_insns > ninsns) 204 { 205 if (dump_file && (dump_flags & TDF_DETAILS)) 206 fprintf (dump_file, "Not unrolling loop %d:\n", loop->num); 207 return false; 208 } 209 } 210 } 211 212 if (exit->flags & EDGE_TRUE_VALUE) 213 { 214 dont_exit = boolean_false_node; 215 do_exit = boolean_true_node; 216 } 217 else 218 { 219 dont_exit = boolean_true_node; 220 do_exit = boolean_false_node; 221 } 222 cond = last_stmt (exit->src); 223 224 if (n_unroll) 225 { 226 sbitmap wont_exit; 227 edge *edges_to_remove = xmalloc (sizeof (edge *) * n_unroll); 228 unsigned int n_to_remove = 0; 229 230 old_cond = COND_EXPR_COND (cond); 231 COND_EXPR_COND (cond) = dont_exit; 232 update_stmt (cond); 233 initialize_original_copy_tables (); 234 235 wont_exit = sbitmap_alloc (n_unroll + 1); 236 sbitmap_ones (wont_exit); 237 RESET_BIT (wont_exit, 0); 238 239 if (!tree_duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop), 240 loops, n_unroll, wont_exit, 241 exit, edges_to_remove, 242 &n_to_remove, 243 DLTHE_FLAG_UPDATE_FREQ 244 | DLTHE_FLAG_COMPLETTE_PEEL)) 245 { 246 COND_EXPR_COND (cond) = old_cond; 247 update_stmt (cond); 248 free_original_copy_tables (); 249 free (wont_exit); 250 free (edges_to_remove); 251 return false; 252 } 253 free (wont_exit); 254 free (edges_to_remove); 255 free_original_copy_tables (); 256 } 257 258 COND_EXPR_COND (cond) = do_exit; 259 update_stmt (cond); 260 261 update_ssa (TODO_update_ssa); 262 263 if (dump_file && (dump_flags & TDF_DETAILS)) 264 fprintf (dump_file, "Unrolled loop %d completely.\n", loop->num); 265 266 return true; 267} 268 269/* Adds a canonical induction variable to LOOP if suitable. LOOPS is the loops 270 tree. CREATE_IV is true if we may create a new iv. UL determines 271 which loops we are allowed to completely unroll. If TRY_EVAL is true, we try 272 to determine the number of iterations of a loop by direct evaluation. 273 Returns true if cfg is changed. */ 274 275static bool 276canonicalize_loop_induction_variables (struct loops *loops, struct loop *loop, 277 bool create_iv, enum unroll_level ul, 278 bool try_eval) 279{ 280 edge exit = NULL; 281 tree niter; 282 283 niter = number_of_iterations_in_loop (loop); 284 if (TREE_CODE (niter) == INTEGER_CST) 285 { 286 exit = loop->single_exit; 287 if (!just_once_each_iteration_p (loop, exit->src)) 288 return false; 289 290 /* The result of number_of_iterations_in_loop is by one higher than 291 we expect (i.e. it returns number of executions of the exit 292 condition, not of the loop latch edge). */ 293 niter = fold_build2 (MINUS_EXPR, TREE_TYPE (niter), niter, 294 build_int_cst (TREE_TYPE (niter), 1)); 295 } 296 else 297 { 298 /* If the loop has more than one exit, try checking all of them 299 for # of iterations determinable through scev. */ 300 if (!loop->single_exit) 301 niter = find_loop_niter (loop, &exit); 302 303 /* Finally if everything else fails, try brute force evaluation. */ 304 if (try_eval 305 && (chrec_contains_undetermined (niter) 306 || TREE_CODE (niter) != INTEGER_CST)) 307 niter = find_loop_niter_by_eval (loop, &exit); 308 309 if (chrec_contains_undetermined (niter) 310 || TREE_CODE (niter) != INTEGER_CST) 311 return false; 312 } 313 314 if (dump_file && (dump_flags & TDF_DETAILS)) 315 { 316 fprintf (dump_file, "Loop %d iterates ", loop->num); 317 print_generic_expr (dump_file, niter, TDF_SLIM); 318 fprintf (dump_file, " times.\n"); 319 } 320 321 if (try_unroll_loop_completely (loops, loop, exit, niter, ul)) 322 return true; 323 324 if (create_iv) 325 create_canonical_iv (loop, exit, niter); 326 327 return false; 328} 329 330/* The main entry point of the pass. Adds canonical induction variables 331 to the suitable LOOPS. */ 332 333void 334canonicalize_induction_variables (struct loops *loops) 335{ 336 unsigned i; 337 struct loop *loop; 338 bool changed = false; 339 340 for (i = 1; i < loops->num; i++) 341 { 342 loop = loops->parray[i]; 343 344 if (loop) 345 changed |= canonicalize_loop_induction_variables (loops, loop, 346 true, UL_SINGLE_ITER, 347 true); 348 } 349 350 /* Clean up the information about numbers of iterations, since brute force 351 evaluation could reveal new information. */ 352 scev_reset (); 353 354 if (changed) 355 cleanup_tree_cfg_loop (); 356} 357 358/* Unroll LOOPS completely if they iterate just few times. Unless 359 MAY_INCREASE_SIZE is true, perform the unrolling only if the 360 size of the code does not increase. */ 361 362void 363tree_unroll_loops_completely (struct loops *loops, bool may_increase_size) 364{ 365 unsigned i; 366 struct loop *loop; 367 bool changed = false; 368 enum unroll_level ul; 369 370 for (i = 1; i < loops->num; i++) 371 { 372 loop = loops->parray[i]; 373 374 if (!loop) 375 continue; 376 377 if (may_increase_size && maybe_hot_bb_p (loop->header)) 378 ul = UL_ALL; 379 else 380 ul = UL_NO_GROWTH; 381 changed |= canonicalize_loop_induction_variables (loops, loop, 382 false, ul, 383 !flag_tree_loop_ivcanon); 384 } 385 386 /* Clean up the information about numbers of iterations, since complete 387 unrolling might have invalidated it. */ 388 scev_reset (); 389 390 if (changed) 391 cleanup_tree_cfg_loop (); 392} 393 394/* Checks whether LOOP is empty. */ 395 396static bool 397empty_loop_p (struct loop *loop) 398{ 399 edge exit; 400 struct tree_niter_desc niter; 401 tree phi, def; 402 basic_block *body; 403 block_stmt_iterator bsi; 404 unsigned i; 405 tree stmt; 406 407 /* If the loop has multiple exits, it is too hard for us to handle. 408 Similarly, if the exit is not dominating, we cannot determine 409 whether the loop is not infinite. */ 410 exit = single_dom_exit (loop); 411 if (!exit) 412 return false; 413 414 /* The loop must be finite. */ 415 if (!number_of_iterations_exit (loop, exit, &niter, false)) 416 return false; 417 418 /* Values of all loop exit phi nodes must be invariants. */ 419 for (phi = phi_nodes (exit->dest); phi; phi = PHI_CHAIN (phi)) 420 { 421 if (!is_gimple_reg (PHI_RESULT (phi))) 422 continue; 423 424 def = PHI_ARG_DEF_FROM_EDGE (phi, exit); 425 426 if (!expr_invariant_in_loop_p (loop, def)) 427 return false; 428 } 429 430 /* And there should be no memory modifying or from other reasons 431 unremovable statements. */ 432 body = get_loop_body (loop); 433 for (i = 0; i < loop->num_nodes; i++) 434 { 435 /* Irreducible region might be infinite. */ 436 if (body[i]->flags & BB_IRREDUCIBLE_LOOP) 437 { 438 free (body); 439 return false; 440 } 441 442 for (bsi = bsi_start (body[i]); !bsi_end_p (bsi); bsi_next (&bsi)) 443 { 444 stmt = bsi_stmt (bsi); 445 if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS) 446 || stmt_ann (stmt)->has_volatile_ops) 447 { 448 free (body); 449 return false; 450 } 451 452 /* Also, asm statements and calls may have side effects and we 453 cannot change the number of times they are executed. */ 454 switch (TREE_CODE (stmt)) 455 { 456 case RETURN_EXPR: 457 case MODIFY_EXPR: 458 stmt = get_call_expr_in (stmt); 459 if (!stmt) 460 break; 461 462 case CALL_EXPR: 463 if (TREE_SIDE_EFFECTS (stmt)) 464 { 465 free (body); 466 return false; 467 } 468 break; 469 470 case ASM_EXPR: 471 /* We cannot remove volatile assembler. */ 472 if (ASM_VOLATILE_P (stmt)) 473 { 474 free (body); 475 return false; 476 } 477 break; 478 479 default: 480 break; 481 } 482 } 483 } 484 free (body); 485 486 return true; 487} 488 489/* Remove LOOP by making it exit in the first iteration. */ 490 491static void 492remove_empty_loop (struct loop *loop) 493{ 494 edge exit = single_dom_exit (loop), non_exit; 495 tree cond_stmt = last_stmt (exit->src); 496 tree do_exit; 497 basic_block *body; 498 unsigned n_before, freq_in, freq_h; 499 gcov_type exit_count = exit->count; 500 501 non_exit = EDGE_SUCC (exit->src, 0); 502 if (non_exit == exit) 503 non_exit = EDGE_SUCC (exit->src, 1); 504 505 if (exit->flags & EDGE_TRUE_VALUE) 506 do_exit = boolean_true_node; 507 else 508 do_exit = boolean_false_node; 509 510 COND_EXPR_COND (cond_stmt) = do_exit; 511 update_stmt (cond_stmt); 512 513 /* Let us set the probabilities of the edges coming from the exit block. */ 514 exit->probability = REG_BR_PROB_BASE; 515 non_exit->probability = 0; 516 non_exit->count = 0; 517 518 /* Update frequencies and counts. Everything before 519 the exit needs to be scaled FREQ_IN/FREQ_H times, 520 where FREQ_IN is the frequency of the entry edge 521 and FREQ_H is the frequency of the loop header. 522 Everything after the exit has zero frequency. */ 523 freq_h = loop->header->frequency; 524 freq_in = EDGE_FREQUENCY (loop_preheader_edge (loop)); 525 if (freq_h != 0) 526 { 527 body = get_loop_body_in_dom_order (loop); 528 for (n_before = 1; n_before <= loop->num_nodes; n_before++) 529 if (body[n_before - 1] == exit->src) 530 break; 531 scale_bbs_frequencies_int (body, n_before, freq_in, freq_h); 532 scale_bbs_frequencies_int (body + n_before, loop->num_nodes - n_before, 533 0, 1); 534 free (body); 535 } 536 537 /* Number of executions of exit is not changed, thus we need to restore 538 the original value. */ 539 exit->count = exit_count; 540} 541 542/* Removes LOOP if it is empty. Returns true if LOOP is removed. CHANGED 543 is set to true if LOOP or any of its subloops is removed. */ 544 545static bool 546try_remove_empty_loop (struct loop *loop, bool *changed) 547{ 548 bool nonempty_subloop = false; 549 struct loop *sub; 550 551 /* First, all subloops must be removed. */ 552 for (sub = loop->inner; sub; sub = sub->next) 553 nonempty_subloop |= !try_remove_empty_loop (sub, changed); 554 555 if (nonempty_subloop || !empty_loop_p (loop)) 556 return false; 557 558 remove_empty_loop (loop); 559 *changed = true; 560 return true; 561} 562 563/* Remove the empty LOOPS. */ 564 565void 566remove_empty_loops (struct loops *loops) 567{ 568 bool changed = false; 569 struct loop *loop; 570 571 for (loop = loops->tree_root->inner; loop; loop = loop->next) 572 try_remove_empty_loop (loop, &changed); 573 574 if (changed) 575 { 576 scev_reset (); 577 cleanup_tree_cfg_loop (); 578 } 579} 580