1/* High-level loop manipulation functions. 2 Copyright (C) 2004, 2005, 2006, 2007 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 "timevar.h" 35#include "cfgloop.h" 36#include "tree-pass.h" 37#include "cfglayout.h" 38#include "tree-scalar-evolution.h" 39#include "params.h" 40 41/* Creates an induction variable with value BASE + STEP * iteration in LOOP. 42 It is expected that neither BASE nor STEP are shared with other expressions 43 (unless the sharing rules allow this). Use VAR as a base var_decl for it 44 (if NULL, a new temporary will be created). The increment will occur at 45 INCR_POS (after it if AFTER is true, before it otherwise). INCR_POS and 46 AFTER can be computed using standard_iv_increment_position. The ssa versions 47 of the variable before and after increment will be stored in VAR_BEFORE and 48 VAR_AFTER (unless they are NULL). */ 49 50void 51create_iv (tree base, tree step, tree var, struct loop *loop, 52 block_stmt_iterator *incr_pos, bool after, 53 tree *var_before, tree *var_after) 54{ 55 tree stmt, initial, step1, stmts; 56 tree vb, va; 57 enum tree_code incr_op = PLUS_EXPR; 58 edge pe = loop_preheader_edge (loop); 59 60 if (!var) 61 { 62 var = create_tmp_var (TREE_TYPE (base), "ivtmp"); 63 add_referenced_var (var); 64 } 65 66 vb = make_ssa_name (var, NULL_TREE); 67 if (var_before) 68 *var_before = vb; 69 va = make_ssa_name (var, NULL_TREE); 70 if (var_after) 71 *var_after = va; 72 73 /* For easier readability of the created code, produce MINUS_EXPRs 74 when suitable. */ 75 if (TREE_CODE (step) == INTEGER_CST) 76 { 77 if (TYPE_UNSIGNED (TREE_TYPE (step))) 78 { 79 step1 = fold_build1 (NEGATE_EXPR, TREE_TYPE (step), step); 80 if (tree_int_cst_lt (step1, step)) 81 { 82 incr_op = MINUS_EXPR; 83 step = step1; 84 } 85 } 86 else 87 { 88 bool ovf; 89 90 if (!tree_expr_nonnegative_warnv_p (step, &ovf) 91 && may_negate_without_overflow_p (step)) 92 { 93 incr_op = MINUS_EXPR; 94 step = fold_build1 (NEGATE_EXPR, TREE_TYPE (step), step); 95 } 96 } 97 } 98 99 /* Gimplify the step if necessary. We put the computations in front of the 100 loop (i.e. the step should be loop invariant). */ 101 step = force_gimple_operand (step, &stmts, true, var); 102 if (stmts) 103 bsi_insert_on_edge_immediate_loop (pe, stmts); 104 105 stmt = build2 (MODIFY_EXPR, void_type_node, va, 106 build2 (incr_op, TREE_TYPE (base), 107 vb, step)); 108 SSA_NAME_DEF_STMT (va) = stmt; 109 if (after) 110 bsi_insert_after (incr_pos, stmt, BSI_NEW_STMT); 111 else 112 bsi_insert_before (incr_pos, stmt, BSI_NEW_STMT); 113 114 initial = force_gimple_operand (base, &stmts, true, var); 115 if (stmts) 116 bsi_insert_on_edge_immediate_loop (pe, stmts); 117 118 stmt = create_phi_node (vb, loop->header); 119 SSA_NAME_DEF_STMT (vb) = stmt; 120 add_phi_arg (stmt, initial, loop_preheader_edge (loop)); 121 add_phi_arg (stmt, va, loop_latch_edge (loop)); 122} 123 124/* Add exit phis for the USE on EXIT. */ 125 126static void 127add_exit_phis_edge (basic_block exit, tree use) 128{ 129 tree phi, def_stmt = SSA_NAME_DEF_STMT (use); 130 basic_block def_bb = bb_for_stmt (def_stmt); 131 struct loop *def_loop; 132 edge e; 133 edge_iterator ei; 134 135 /* Check that some of the edges entering the EXIT block exits a loop in 136 that USE is defined. */ 137 FOR_EACH_EDGE (e, ei, exit->preds) 138 { 139 def_loop = find_common_loop (def_bb->loop_father, e->src->loop_father); 140 if (!flow_bb_inside_loop_p (def_loop, e->dest)) 141 break; 142 } 143 144 if (!e) 145 return; 146 147 phi = create_phi_node (use, exit); 148 create_new_def_for (PHI_RESULT (phi), phi, PHI_RESULT_PTR (phi)); 149 FOR_EACH_EDGE (e, ei, exit->preds) 150 add_phi_arg (phi, use, e); 151} 152 153/* Add exit phis for VAR that is used in LIVEIN. 154 Exits of the loops are stored in EXITS. */ 155 156static void 157add_exit_phis_var (tree var, bitmap livein, bitmap exits) 158{ 159 bitmap def; 160 unsigned index; 161 basic_block def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (var)); 162 bitmap_iterator bi; 163 164 if (is_gimple_reg (var)) 165 bitmap_clear_bit (livein, def_bb->index); 166 else 167 bitmap_set_bit (livein, def_bb->index); 168 169 def = BITMAP_ALLOC (NULL); 170 bitmap_set_bit (def, def_bb->index); 171 compute_global_livein (livein, def); 172 BITMAP_FREE (def); 173 174 EXECUTE_IF_AND_IN_BITMAP (exits, livein, 0, index, bi) 175 { 176 add_exit_phis_edge (BASIC_BLOCK (index), var); 177 } 178} 179 180/* Add exit phis for the names marked in NAMES_TO_RENAME. 181 Exits of the loops are stored in EXITS. Sets of blocks where the ssa 182 names are used are stored in USE_BLOCKS. */ 183 184static void 185add_exit_phis (bitmap names_to_rename, bitmap *use_blocks, bitmap loop_exits) 186{ 187 unsigned i; 188 bitmap_iterator bi; 189 190 EXECUTE_IF_SET_IN_BITMAP (names_to_rename, 0, i, bi) 191 { 192 add_exit_phis_var (ssa_name (i), use_blocks[i], loop_exits); 193 } 194} 195 196/* Returns a bitmap of all loop exit edge targets. */ 197 198static bitmap 199get_loops_exits (void) 200{ 201 bitmap exits = BITMAP_ALLOC (NULL); 202 basic_block bb; 203 edge e; 204 edge_iterator ei; 205 206 FOR_EACH_BB (bb) 207 { 208 FOR_EACH_EDGE (e, ei, bb->preds) 209 if (e->src != ENTRY_BLOCK_PTR 210 && !flow_bb_inside_loop_p (e->src->loop_father, bb)) 211 { 212 bitmap_set_bit (exits, bb->index); 213 break; 214 } 215 } 216 217 return exits; 218} 219 220/* For USE in BB, if it is used outside of the loop it is defined in, 221 mark it for rewrite. Record basic block BB where it is used 222 to USE_BLOCKS. Record the ssa name index to NEED_PHIS bitmap. */ 223 224static void 225find_uses_to_rename_use (basic_block bb, tree use, bitmap *use_blocks, 226 bitmap need_phis) 227{ 228 unsigned ver; 229 basic_block def_bb; 230 struct loop *def_loop; 231 232 if (TREE_CODE (use) != SSA_NAME) 233 return; 234 235 /* We don't need to keep virtual operands in loop-closed form. */ 236 if (!is_gimple_reg (use)) 237 return; 238 239 ver = SSA_NAME_VERSION (use); 240 def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (use)); 241 if (!def_bb) 242 return; 243 def_loop = def_bb->loop_father; 244 245 /* If the definition is not inside loop, it is not interesting. */ 246 if (!def_loop->outer) 247 return; 248 249 if (!use_blocks[ver]) 250 use_blocks[ver] = BITMAP_ALLOC (NULL); 251 bitmap_set_bit (use_blocks[ver], bb->index); 252 253 bitmap_set_bit (need_phis, ver); 254} 255 256/* For uses in STMT, mark names that are used outside of the loop they are 257 defined to rewrite. Record the set of blocks in that the ssa 258 names are defined to USE_BLOCKS and the ssa names themselves to 259 NEED_PHIS. */ 260 261static void 262find_uses_to_rename_stmt (tree stmt, bitmap *use_blocks, bitmap need_phis) 263{ 264 ssa_op_iter iter; 265 tree var; 266 basic_block bb = bb_for_stmt (stmt); 267 268 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS) 269 find_uses_to_rename_use (bb, var, use_blocks, need_phis); 270} 271 272/* Marks names that are used in BB and outside of the loop they are 273 defined in for rewrite. Records the set of blocks in that the ssa 274 names are defined to USE_BLOCKS. Record the SSA names that will 275 need exit PHIs in NEED_PHIS. */ 276 277static void 278find_uses_to_rename_bb (basic_block bb, bitmap *use_blocks, bitmap need_phis) 279{ 280 block_stmt_iterator bsi; 281 edge e; 282 edge_iterator ei; 283 tree phi; 284 285 FOR_EACH_EDGE (e, ei, bb->succs) 286 for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi)) 287 find_uses_to_rename_use (bb, PHI_ARG_DEF_FROM_EDGE (phi, e), 288 use_blocks, need_phis); 289 290 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 291 find_uses_to_rename_stmt (bsi_stmt (bsi), use_blocks, need_phis); 292} 293 294/* Marks names that are used outside of the loop they are defined in 295 for rewrite. Records the set of blocks in that the ssa 296 names are defined to USE_BLOCKS. If CHANGED_BBS is not NULL, 297 scan only blocks in this set. */ 298 299static void 300find_uses_to_rename (bitmap changed_bbs, bitmap *use_blocks, bitmap need_phis) 301{ 302 basic_block bb; 303 unsigned index; 304 bitmap_iterator bi; 305 306 if (changed_bbs && !bitmap_empty_p (changed_bbs)) 307 { 308 EXECUTE_IF_SET_IN_BITMAP (changed_bbs, 0, index, bi) 309 { 310 find_uses_to_rename_bb (BASIC_BLOCK (index), use_blocks, need_phis); 311 } 312 } 313 else 314 { 315 FOR_EACH_BB (bb) 316 { 317 find_uses_to_rename_bb (bb, use_blocks, need_phis); 318 } 319 } 320} 321 322/* Rewrites the program into a loop closed ssa form -- i.e. inserts extra 323 phi nodes to ensure that no variable is used outside the loop it is 324 defined in. 325 326 This strengthening of the basic ssa form has several advantages: 327 328 1) Updating it during unrolling/peeling/versioning is trivial, since 329 we do not need to care about the uses outside of the loop. 330 2) The behavior of all uses of an induction variable is the same. 331 Without this, you need to distinguish the case when the variable 332 is used outside of the loop it is defined in, for example 333 334 for (i = 0; i < 100; i++) 335 { 336 for (j = 0; j < 100; j++) 337 { 338 k = i + j; 339 use1 (k); 340 } 341 use2 (k); 342 } 343 344 Looking from the outer loop with the normal SSA form, the first use of k 345 is not well-behaved, while the second one is an induction variable with 346 base 99 and step 1. 347 348 If CHANGED_BBS is not NULL, we look for uses outside loops only in 349 the basic blocks in this set. 350 351 UPDATE_FLAG is used in the call to update_ssa. See 352 TODO_update_ssa* for documentation. */ 353 354void 355rewrite_into_loop_closed_ssa (bitmap changed_bbs, unsigned update_flag) 356{ 357 bitmap loop_exits = get_loops_exits (); 358 bitmap *use_blocks; 359 unsigned i, old_num_ssa_names; 360 bitmap names_to_rename = BITMAP_ALLOC (NULL); 361 362 /* If the pass has caused the SSA form to be out-of-date, update it 363 now. */ 364 update_ssa (update_flag); 365 366 old_num_ssa_names = num_ssa_names; 367 use_blocks = XCNEWVEC (bitmap, old_num_ssa_names); 368 369 /* Find the uses outside loops. */ 370 find_uses_to_rename (changed_bbs, use_blocks, names_to_rename); 371 372 /* Add the PHI nodes on exits of the loops for the names we need to 373 rewrite. */ 374 add_exit_phis (names_to_rename, use_blocks, loop_exits); 375 376 for (i = 0; i < old_num_ssa_names; i++) 377 BITMAP_FREE (use_blocks[i]); 378 free (use_blocks); 379 BITMAP_FREE (loop_exits); 380 BITMAP_FREE (names_to_rename); 381 382 /* Fix up all the names found to be used outside their original 383 loops. */ 384 update_ssa (TODO_update_ssa); 385} 386 387/* Check invariants of the loop closed ssa form for the USE in BB. */ 388 389static void 390check_loop_closed_ssa_use (basic_block bb, tree use) 391{ 392 tree def; 393 basic_block def_bb; 394 395 if (TREE_CODE (use) != SSA_NAME || !is_gimple_reg (use)) 396 return; 397 398 def = SSA_NAME_DEF_STMT (use); 399 def_bb = bb_for_stmt (def); 400 gcc_assert (!def_bb 401 || flow_bb_inside_loop_p (def_bb->loop_father, bb)); 402} 403 404/* Checks invariants of loop closed ssa form in statement STMT in BB. */ 405 406static void 407check_loop_closed_ssa_stmt (basic_block bb, tree stmt) 408{ 409 ssa_op_iter iter; 410 tree var; 411 412 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS) 413 check_loop_closed_ssa_use (bb, var); 414} 415 416/* Checks that invariants of the loop closed ssa form are preserved. */ 417 418void 419verify_loop_closed_ssa (void) 420{ 421 basic_block bb; 422 block_stmt_iterator bsi; 423 tree phi; 424 unsigned i; 425 426 if (current_loops == NULL) 427 return; 428 429 verify_ssa (false); 430 431 FOR_EACH_BB (bb) 432 { 433 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 434 for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++) 435 check_loop_closed_ssa_use (PHI_ARG_EDGE (phi, i)->src, 436 PHI_ARG_DEF (phi, i)); 437 438 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 439 check_loop_closed_ssa_stmt (bb, bsi_stmt (bsi)); 440 } 441} 442 443/* Split loop exit edge EXIT. The things are a bit complicated by a need to 444 preserve the loop closed ssa form. */ 445 446void 447split_loop_exit_edge (edge exit) 448{ 449 basic_block dest = exit->dest; 450 basic_block bb = loop_split_edge_with (exit, NULL); 451 tree phi, new_phi, new_name, name; 452 use_operand_p op_p; 453 454 for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi)) 455 { 456 op_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, single_succ_edge (bb)); 457 458 name = USE_FROM_PTR (op_p); 459 460 /* If the argument of the phi node is a constant, we do not need 461 to keep it inside loop. */ 462 if (TREE_CODE (name) != SSA_NAME) 463 continue; 464 465 /* Otherwise create an auxiliary phi node that will copy the value 466 of the ssa name out of the loop. */ 467 new_name = duplicate_ssa_name (name, NULL); 468 new_phi = create_phi_node (new_name, bb); 469 SSA_NAME_DEF_STMT (new_name) = new_phi; 470 add_phi_arg (new_phi, name, exit); 471 SET_USE (op_p, new_name); 472 } 473} 474 475/* Insert statement STMT to the edge E and update the loop structures. 476 Returns the newly created block (if any). */ 477 478basic_block 479bsi_insert_on_edge_immediate_loop (edge e, tree stmt) 480{ 481 basic_block src, dest, new_bb; 482 struct loop *loop_c; 483 484 src = e->src; 485 dest = e->dest; 486 487 loop_c = find_common_loop (src->loop_father, dest->loop_father); 488 489 new_bb = bsi_insert_on_edge_immediate (e, stmt); 490 491 if (!new_bb) 492 return NULL; 493 494 add_bb_to_loop (new_bb, loop_c); 495 if (dest->loop_father->latch == src) 496 dest->loop_father->latch = new_bb; 497 498 return new_bb; 499} 500 501/* Returns the basic block in that statements should be emitted for induction 502 variables incremented at the end of the LOOP. */ 503 504basic_block 505ip_end_pos (struct loop *loop) 506{ 507 return loop->latch; 508} 509 510/* Returns the basic block in that statements should be emitted for induction 511 variables incremented just before exit condition of a LOOP. */ 512 513basic_block 514ip_normal_pos (struct loop *loop) 515{ 516 tree last; 517 basic_block bb; 518 edge exit; 519 520 if (!single_pred_p (loop->latch)) 521 return NULL; 522 523 bb = single_pred (loop->latch); 524 last = last_stmt (bb); 525 if (TREE_CODE (last) != COND_EXPR) 526 return NULL; 527 528 exit = EDGE_SUCC (bb, 0); 529 if (exit->dest == loop->latch) 530 exit = EDGE_SUCC (bb, 1); 531 532 if (flow_bb_inside_loop_p (loop, exit->dest)) 533 return NULL; 534 535 return bb; 536} 537 538/* Stores the standard position for induction variable increment in LOOP 539 (just before the exit condition if it is available and latch block is empty, 540 end of the latch block otherwise) to BSI. INSERT_AFTER is set to true if 541 the increment should be inserted after *BSI. */ 542 543void 544standard_iv_increment_position (struct loop *loop, block_stmt_iterator *bsi, 545 bool *insert_after) 546{ 547 basic_block bb = ip_normal_pos (loop), latch = ip_end_pos (loop); 548 tree last = last_stmt (latch); 549 550 if (!bb 551 || (last && TREE_CODE (last) != LABEL_EXPR)) 552 { 553 *bsi = bsi_last (latch); 554 *insert_after = true; 555 } 556 else 557 { 558 *bsi = bsi_last (bb); 559 *insert_after = false; 560 } 561} 562 563/* Copies phi node arguments for duplicated blocks. The index of the first 564 duplicated block is FIRST_NEW_BLOCK. */ 565 566static void 567copy_phi_node_args (unsigned first_new_block) 568{ 569 unsigned i; 570 571 for (i = first_new_block; i < (unsigned) last_basic_block; i++) 572 BASIC_BLOCK (i)->flags |= BB_DUPLICATED; 573 574 for (i = first_new_block; i < (unsigned) last_basic_block; i++) 575 add_phi_args_after_copy_bb (BASIC_BLOCK (i)); 576 577 for (i = first_new_block; i < (unsigned) last_basic_block; i++) 578 BASIC_BLOCK (i)->flags &= ~BB_DUPLICATED; 579} 580 581 582/* The same as cfgloopmanip.c:duplicate_loop_to_header_edge, but also 583 updates the PHI nodes at start of the copied region. In order to 584 achieve this, only loops whose exits all lead to the same location 585 are handled. 586 587 Notice that we do not completely update the SSA web after 588 duplication. The caller is responsible for calling update_ssa 589 after the loop has been duplicated. */ 590 591bool 592tree_duplicate_loop_to_header_edge (struct loop *loop, edge e, 593 struct loops *loops, 594 unsigned int ndupl, sbitmap wont_exit, 595 edge orig, edge *to_remove, 596 unsigned int *n_to_remove, int flags) 597{ 598 unsigned first_new_block; 599 600 if (!(loops->state & LOOPS_HAVE_SIMPLE_LATCHES)) 601 return false; 602 if (!(loops->state & LOOPS_HAVE_PREHEADERS)) 603 return false; 604 605#ifdef ENABLE_CHECKING 606 verify_loop_closed_ssa (); 607#endif 608 609 first_new_block = last_basic_block; 610 if (!duplicate_loop_to_header_edge (loop, e, loops, ndupl, wont_exit, 611 orig, to_remove, n_to_remove, flags)) 612 return false; 613 614 /* Readd the removed phi args for e. */ 615 flush_pending_stmts (e); 616 617 /* Copy the phi node arguments. */ 618 copy_phi_node_args (first_new_block); 619 620 scev_reset (); 621 622 return true; 623} 624 625/* Build if (COND) goto THEN_LABEL; else goto ELSE_LABEL; */ 626 627static tree 628build_if_stmt (tree cond, tree then_label, tree else_label) 629{ 630 return build3 (COND_EXPR, void_type_node, 631 cond, 632 build1 (GOTO_EXPR, void_type_node, then_label), 633 build1 (GOTO_EXPR, void_type_node, else_label)); 634} 635 636/* Returns true if we can unroll LOOP FACTOR times. Number 637 of iterations of the loop is returned in NITER. */ 638 639bool 640can_unroll_loop_p (struct loop *loop, unsigned factor, 641 struct tree_niter_desc *niter) 642{ 643 edge exit; 644 645 /* Check whether unrolling is possible. We only want to unroll loops 646 for that we are able to determine number of iterations. We also 647 want to split the extra iterations of the loop from its end, 648 therefore we require that the loop has precisely one 649 exit. */ 650 651 exit = single_dom_exit (loop); 652 if (!exit) 653 return false; 654 655 if (!number_of_iterations_exit (loop, exit, niter, false) 656 || niter->cmp == ERROR_MARK 657 /* Scalar evolutions analysis might have copy propagated 658 the abnormal ssa names into these expressions, hence 659 emiting the computations based on them during loop 660 unrolling might create overlapping life ranges for 661 them, and failures in out-of-ssa. */ 662 || contains_abnormal_ssa_name_p (niter->may_be_zero) 663 || contains_abnormal_ssa_name_p (niter->control.base) 664 || contains_abnormal_ssa_name_p (niter->control.step) 665 || contains_abnormal_ssa_name_p (niter->bound)) 666 return false; 667 668 /* And of course, we must be able to duplicate the loop. */ 669 if (!can_duplicate_loop_p (loop)) 670 return false; 671 672 /* The final loop should be small enough. */ 673 if (tree_num_loop_insns (loop) * factor 674 > (unsigned) PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS)) 675 return false; 676 677 return true; 678} 679 680/* Determines the conditions that control execution of LOOP unrolled FACTOR 681 times. DESC is number of iterations of LOOP. ENTER_COND is set to 682 condition that must be true if the main loop can be entered. 683 EXIT_BASE, EXIT_STEP, EXIT_CMP and EXIT_BOUND are set to values describing 684 how the exit from the unrolled loop should be controlled. */ 685 686static void 687determine_exit_conditions (struct loop *loop, struct tree_niter_desc *desc, 688 unsigned factor, tree *enter_cond, 689 tree *exit_base, tree *exit_step, 690 enum tree_code *exit_cmp, tree *exit_bound) 691{ 692 tree stmts; 693 tree base = desc->control.base; 694 tree step = desc->control.step; 695 tree bound = desc->bound; 696 tree type = TREE_TYPE (base); 697 tree bigstep, delta; 698 tree min = lower_bound_in_type (type, type); 699 tree max = upper_bound_in_type (type, type); 700 enum tree_code cmp = desc->cmp; 701 tree cond = boolean_true_node, assum; 702 703 *enter_cond = boolean_false_node; 704 *exit_base = NULL_TREE; 705 *exit_step = NULL_TREE; 706 *exit_cmp = ERROR_MARK; 707 *exit_bound = NULL_TREE; 708 gcc_assert (cmp != ERROR_MARK); 709 710 /* We only need to be correct when we answer question 711 "Do at least FACTOR more iterations remain?" in the unrolled loop. 712 Thus, transforming BASE + STEP * i <> BOUND to 713 BASE + STEP * i < BOUND is ok. */ 714 if (cmp == NE_EXPR) 715 { 716 if (tree_int_cst_sign_bit (step)) 717 cmp = GT_EXPR; 718 else 719 cmp = LT_EXPR; 720 } 721 else if (cmp == LT_EXPR) 722 { 723 gcc_assert (!tree_int_cst_sign_bit (step)); 724 } 725 else if (cmp == GT_EXPR) 726 { 727 gcc_assert (tree_int_cst_sign_bit (step)); 728 } 729 else 730 gcc_unreachable (); 731 732 /* The main body of the loop may be entered iff: 733 734 1) desc->may_be_zero is false. 735 2) it is possible to check that there are at least FACTOR iterations 736 of the loop, i.e., BOUND - step * FACTOR does not overflow. 737 3) # of iterations is at least FACTOR */ 738 739 if (!zero_p (desc->may_be_zero)) 740 cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, 741 invert_truthvalue (desc->may_be_zero), 742 cond); 743 744 bigstep = fold_build2 (MULT_EXPR, type, step, 745 build_int_cst_type (type, factor)); 746 delta = fold_build2 (MINUS_EXPR, type, bigstep, step); 747 if (cmp == LT_EXPR) 748 assum = fold_build2 (GE_EXPR, boolean_type_node, 749 bound, 750 fold_build2 (PLUS_EXPR, type, min, delta)); 751 else 752 assum = fold_build2 (LE_EXPR, boolean_type_node, 753 bound, 754 fold_build2 (PLUS_EXPR, type, max, delta)); 755 cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, assum, cond); 756 757 bound = fold_build2 (MINUS_EXPR, type, bound, delta); 758 assum = fold_build2 (cmp, boolean_type_node, base, bound); 759 cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, assum, cond); 760 761 cond = force_gimple_operand (unshare_expr (cond), &stmts, false, NULL_TREE); 762 if (stmts) 763 bsi_insert_on_edge_immediate_loop (loop_preheader_edge (loop), stmts); 764 /* cond now may be a gimple comparison, which would be OK, but also any 765 other gimple rhs (say a && b). In this case we need to force it to 766 operand. */ 767 if (!is_gimple_condexpr (cond)) 768 { 769 cond = force_gimple_operand (cond, &stmts, true, NULL_TREE); 770 if (stmts) 771 bsi_insert_on_edge_immediate_loop (loop_preheader_edge (loop), stmts); 772 } 773 *enter_cond = cond; 774 775 base = force_gimple_operand (unshare_expr (base), &stmts, true, NULL_TREE); 776 if (stmts) 777 bsi_insert_on_edge_immediate_loop (loop_preheader_edge (loop), stmts); 778 bound = force_gimple_operand (unshare_expr (bound), &stmts, true, NULL_TREE); 779 if (stmts) 780 bsi_insert_on_edge_immediate_loop (loop_preheader_edge (loop), stmts); 781 782 *exit_base = base; 783 *exit_step = bigstep; 784 *exit_cmp = cmp; 785 *exit_bound = bound; 786} 787 788/* Unroll LOOP FACTOR times. LOOPS is the loops tree. DESC describes 789 number of iterations of LOOP. EXIT is the exit of the loop to that 790 DESC corresponds. 791 792 If N is number of iterations of the loop and MAY_BE_ZERO is the condition 793 under that loop exits in the first iteration even if N != 0, 794 795 while (1) 796 { 797 x = phi (init, next); 798 799 pre; 800 if (st) 801 break; 802 post; 803 } 804 805 becomes (with possibly the exit conditions formulated a bit differently, 806 avoiding the need to create a new iv): 807 808 if (MAY_BE_ZERO || N < FACTOR) 809 goto rest; 810 811 do 812 { 813 x = phi (init, next); 814 815 pre; 816 post; 817 pre; 818 post; 819 ... 820 pre; 821 post; 822 N -= FACTOR; 823 824 } while (N >= FACTOR); 825 826 rest: 827 init' = phi (init, x); 828 829 while (1) 830 { 831 x = phi (init', next); 832 833 pre; 834 if (st) 835 break; 836 post; 837 } */ 838 839void 840tree_unroll_loop (struct loops *loops, struct loop *loop, unsigned factor, 841 edge exit, struct tree_niter_desc *desc) 842{ 843 tree dont_exit, exit_if, ctr_before, ctr_after; 844 tree enter_main_cond, exit_base, exit_step, exit_bound; 845 enum tree_code exit_cmp; 846 tree phi_old_loop, phi_new_loop, phi_rest, init, next, new_init, var; 847 struct loop *new_loop; 848 basic_block rest, exit_bb; 849 edge old_entry, new_entry, old_latch, precond_edge, new_exit; 850 edge nonexit, new_nonexit; 851 block_stmt_iterator bsi; 852 use_operand_p op; 853 bool ok; 854 unsigned est_niter; 855 unsigned irr = loop_preheader_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP; 856 sbitmap wont_exit; 857 858 est_niter = expected_loop_iterations (loop); 859 determine_exit_conditions (loop, desc, factor, 860 &enter_main_cond, &exit_base, &exit_step, 861 &exit_cmp, &exit_bound); 862 863 new_loop = loop_version (loops, loop, enter_main_cond, NULL, true); 864 gcc_assert (new_loop != NULL); 865 update_ssa (TODO_update_ssa); 866 867 /* Unroll the loop and remove the old exits. */ 868 dont_exit = ((exit->flags & EDGE_TRUE_VALUE) 869 ? boolean_false_node 870 : boolean_true_node); 871 if (exit == EDGE_SUCC (exit->src, 0)) 872 nonexit = EDGE_SUCC (exit->src, 1); 873 else 874 nonexit = EDGE_SUCC (exit->src, 0); 875 nonexit->probability = REG_BR_PROB_BASE; 876 exit->probability = 0; 877 nonexit->count += exit->count; 878 exit->count = 0; 879 exit_if = last_stmt (exit->src); 880 COND_EXPR_COND (exit_if) = dont_exit; 881 update_stmt (exit_if); 882 883 wont_exit = sbitmap_alloc (factor); 884 sbitmap_ones (wont_exit); 885 ok = tree_duplicate_loop_to_header_edge 886 (loop, loop_latch_edge (loop), loops, factor - 1, 887 wont_exit, NULL, NULL, NULL, DLTHE_FLAG_UPDATE_FREQ); 888 free (wont_exit); 889 gcc_assert (ok); 890 update_ssa (TODO_update_ssa); 891 892 /* Prepare the cfg and update the phi nodes. */ 893 rest = loop_preheader_edge (new_loop)->src; 894 precond_edge = single_pred_edge (rest); 895 loop_split_edge_with (loop_latch_edge (loop), NULL); 896 exit_bb = single_pred (loop->latch); 897 898 new_exit = make_edge (exit_bb, rest, EDGE_FALSE_VALUE | irr); 899 new_exit->count = loop_preheader_edge (loop)->count; 900 est_niter = est_niter / factor + 1; 901 new_exit->probability = REG_BR_PROB_BASE / est_niter; 902 903 new_nonexit = single_pred_edge (loop->latch); 904 new_nonexit->flags = EDGE_TRUE_VALUE; 905 new_nonexit->probability = REG_BR_PROB_BASE - new_exit->probability; 906 907 old_entry = loop_preheader_edge (loop); 908 new_entry = loop_preheader_edge (new_loop); 909 old_latch = loop_latch_edge (loop); 910 for (phi_old_loop = phi_nodes (loop->header), 911 phi_new_loop = phi_nodes (new_loop->header); 912 phi_old_loop; 913 phi_old_loop = PHI_CHAIN (phi_old_loop), 914 phi_new_loop = PHI_CHAIN (phi_new_loop)) 915 { 916 init = PHI_ARG_DEF_FROM_EDGE (phi_old_loop, old_entry); 917 op = PHI_ARG_DEF_PTR_FROM_EDGE (phi_new_loop, new_entry); 918 gcc_assert (operand_equal_for_phi_arg_p (init, USE_FROM_PTR (op))); 919 next = PHI_ARG_DEF_FROM_EDGE (phi_old_loop, old_latch); 920 921 /* Prefer using original variable as a base for the new ssa name. 922 This is necessary for virtual ops, and useful in order to avoid 923 losing debug info for real ops. */ 924 if (TREE_CODE (next) == SSA_NAME) 925 var = SSA_NAME_VAR (next); 926 else if (TREE_CODE (init) == SSA_NAME) 927 var = SSA_NAME_VAR (init); 928 else 929 { 930 var = create_tmp_var (TREE_TYPE (init), "unrinittmp"); 931 add_referenced_var (var); 932 } 933 934 new_init = make_ssa_name (var, NULL_TREE); 935 phi_rest = create_phi_node (new_init, rest); 936 SSA_NAME_DEF_STMT (new_init) = phi_rest; 937 938 add_phi_arg (phi_rest, init, precond_edge); 939 add_phi_arg (phi_rest, next, new_exit); 940 SET_USE (op, new_init); 941 } 942 943 /* Finally create the new counter for number of iterations and add the new 944 exit instruction. */ 945 bsi = bsi_last (exit_bb); 946 create_iv (exit_base, exit_step, NULL_TREE, loop, 947 &bsi, true, &ctr_before, &ctr_after); 948 exit_if = build_if_stmt (build2 (exit_cmp, boolean_type_node, ctr_after, 949 exit_bound), 950 tree_block_label (loop->latch), 951 tree_block_label (rest)); 952 bsi_insert_after (&bsi, exit_if, BSI_NEW_STMT); 953 954 verify_flow_info (); 955 verify_dominators (CDI_DOMINATORS); 956 verify_loop_structure (loops); 957 verify_loop_closed_ssa (); 958} 959