1 /* High-level loop manipulation functions. 2 Copyright (C) 2004, 2005, 2006, 2007, 2008, 2010 3 Free Software Foundation, Inc. 4 5 This file is part of GCC. 6 7 GCC is free software; you can redistribute it and/or modify it 8 under the terms of the GNU General Public License as published by the 9 Free Software Foundation; either version 3, or (at your option) any 10 later version. 11 12 GCC is distributed in the hope that it will be useful, but WITHOUT 13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15 for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with GCC; see the file COPYING3. If not see 19 <http://www.gnu.org/licenses/>. */ 20 21 #include "config.h" 22 #include "system.h" 23 #include "coretypes.h" 24 #include "tm.h" 25 #include "tree.h" 26 #include "tm_p.h" 27 #include "basic-block.h" 28 #include "output.h" 29 #include "tree-flow.h" 30 #include "tree-dump.h" 31 #include "timevar.h" 32 #include "cfgloop.h" 33 #include "tree-pass.h" 34 #include "cfglayout.h" 35 #include "tree-scalar-evolution.h" 36 #include "params.h" 37 #include "tree-inline.h" 38 #include "langhooks.h" 39 40 /* Creates an induction variable with value BASE + STEP * iteration in LOOP. 41 It is expected that neither BASE nor STEP are shared with other expressions 42 (unless the sharing rules allow this). Use VAR as a base var_decl for it 43 (if NULL, a new temporary will be created). The increment will occur at 44 INCR_POS (after it if AFTER is true, before it otherwise). INCR_POS and 45 AFTER can be computed using standard_iv_increment_position. The ssa versions 46 of the variable before and after increment will be stored in VAR_BEFORE and 47 VAR_AFTER (unless they are NULL). */ 48 49 void 50 create_iv (tree base, tree step, tree var, struct loop *loop, 51 gimple_stmt_iterator *incr_pos, bool after, 52 tree *var_before, tree *var_after) 53 { 54 gimple stmt; 55 tree initial, step1; 56 gimple_seq stmts; 57 tree vb, va; 58 enum tree_code incr_op = PLUS_EXPR; 59 edge pe = loop_preheader_edge (loop); 60 61 if (!var) 62 { 63 var = create_tmp_var (TREE_TYPE (base), "ivtmp"); 64 add_referenced_var (var); 65 } 66 67 vb = make_ssa_name (var, NULL); 68 if (var_before) 69 *var_before = vb; 70 va = make_ssa_name (var, NULL); 71 if (var_after) 72 *var_after = va; 73 74 /* For easier readability of the created code, produce MINUS_EXPRs 75 when suitable. */ 76 if (TREE_CODE (step) == INTEGER_CST) 77 { 78 if (TYPE_UNSIGNED (TREE_TYPE (step))) 79 { 80 step1 = fold_build1 (NEGATE_EXPR, TREE_TYPE (step), step); 81 if (tree_int_cst_lt (step1, step)) 82 { 83 incr_op = MINUS_EXPR; 84 step = step1; 85 } 86 } 87 else 88 { 89 bool ovf; 90 91 if (!tree_expr_nonnegative_warnv_p (step, &ovf) 92 && may_negate_without_overflow_p (step)) 93 { 94 incr_op = MINUS_EXPR; 95 step = fold_build1 (NEGATE_EXPR, TREE_TYPE (step), step); 96 } 97 } 98 } 99 if (POINTER_TYPE_P (TREE_TYPE (base))) 100 { 101 if (TREE_CODE (base) == ADDR_EXPR) 102 mark_addressable (TREE_OPERAND (base, 0)); 103 step = convert_to_ptrofftype (step); 104 if (incr_op == MINUS_EXPR) 105 step = fold_build1 (NEGATE_EXPR, TREE_TYPE (step), step); 106 incr_op = POINTER_PLUS_EXPR; 107 } 108 /* Gimplify the step if necessary. We put the computations in front of the 109 loop (i.e. the step should be loop invariant). */ 110 step = force_gimple_operand (step, &stmts, true, NULL_TREE); 111 if (stmts) 112 gsi_insert_seq_on_edge_immediate (pe, stmts); 113 114 stmt = gimple_build_assign_with_ops (incr_op, va, vb, step); 115 if (after) 116 gsi_insert_after (incr_pos, stmt, GSI_NEW_STMT); 117 else 118 gsi_insert_before (incr_pos, stmt, GSI_NEW_STMT); 119 120 initial = force_gimple_operand (base, &stmts, true, var); 121 if (stmts) 122 gsi_insert_seq_on_edge_immediate (pe, stmts); 123 124 stmt = create_phi_node (vb, loop->header); 125 SSA_NAME_DEF_STMT (vb) = stmt; 126 add_phi_arg (stmt, initial, loop_preheader_edge (loop), UNKNOWN_LOCATION); 127 add_phi_arg (stmt, va, loop_latch_edge (loop), UNKNOWN_LOCATION); 128 } 129 130 /* Add exit phis for the USE on EXIT. */ 131 132 static void 133 add_exit_phis_edge (basic_block exit, tree use) 134 { 135 gimple phi, def_stmt = SSA_NAME_DEF_STMT (use); 136 basic_block def_bb = gimple_bb (def_stmt); 137 struct loop *def_loop; 138 edge e; 139 edge_iterator ei; 140 141 /* Check that some of the edges entering the EXIT block exits a loop in 142 that USE is defined. */ 143 FOR_EACH_EDGE (e, ei, exit->preds) 144 { 145 def_loop = find_common_loop (def_bb->loop_father, e->src->loop_father); 146 if (!flow_bb_inside_loop_p (def_loop, e->dest)) 147 break; 148 } 149 150 if (!e) 151 return; 152 153 phi = create_phi_node (use, exit); 154 create_new_def_for (gimple_phi_result (phi), phi, 155 gimple_phi_result_ptr (phi)); 156 FOR_EACH_EDGE (e, ei, exit->preds) 157 add_phi_arg (phi, use, e, UNKNOWN_LOCATION); 158 } 159 160 /* Add exit phis for VAR that is used in LIVEIN. 161 Exits of the loops are stored in EXITS. */ 162 163 static void 164 add_exit_phis_var (tree var, bitmap livein, bitmap exits) 165 { 166 bitmap def; 167 unsigned index; 168 basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (var)); 169 bitmap_iterator bi; 170 171 if (is_gimple_reg (var)) 172 bitmap_clear_bit (livein, def_bb->index); 173 else 174 bitmap_set_bit (livein, def_bb->index); 175 176 def = BITMAP_ALLOC (NULL); 177 bitmap_set_bit (def, def_bb->index); 178 compute_global_livein (livein, def); 179 BITMAP_FREE (def); 180 181 EXECUTE_IF_AND_IN_BITMAP (exits, livein, 0, index, bi) 182 { 183 add_exit_phis_edge (BASIC_BLOCK (index), var); 184 } 185 } 186 187 /* Add exit phis for the names marked in NAMES_TO_RENAME. 188 Exits of the loops are stored in EXITS. Sets of blocks where the ssa 189 names are used are stored in USE_BLOCKS. */ 190 191 static void 192 add_exit_phis (bitmap names_to_rename, bitmap *use_blocks, bitmap loop_exits) 193 { 194 unsigned i; 195 bitmap_iterator bi; 196 197 EXECUTE_IF_SET_IN_BITMAP (names_to_rename, 0, i, bi) 198 { 199 add_exit_phis_var (ssa_name (i), use_blocks[i], loop_exits); 200 } 201 } 202 203 /* Returns a bitmap of all loop exit edge targets. */ 204 205 static bitmap 206 get_loops_exits (void) 207 { 208 bitmap exits = BITMAP_ALLOC (NULL); 209 basic_block bb; 210 edge e; 211 edge_iterator ei; 212 213 FOR_EACH_BB (bb) 214 { 215 FOR_EACH_EDGE (e, ei, bb->preds) 216 if (e->src != ENTRY_BLOCK_PTR 217 && !flow_bb_inside_loop_p (e->src->loop_father, bb)) 218 { 219 bitmap_set_bit (exits, bb->index); 220 break; 221 } 222 } 223 224 return exits; 225 } 226 227 /* For USE in BB, if it is used outside of the loop it is defined in, 228 mark it for rewrite. Record basic block BB where it is used 229 to USE_BLOCKS. Record the ssa name index to NEED_PHIS bitmap. */ 230 231 static void 232 find_uses_to_rename_use (basic_block bb, tree use, bitmap *use_blocks, 233 bitmap need_phis) 234 { 235 unsigned ver; 236 basic_block def_bb; 237 struct loop *def_loop; 238 239 if (TREE_CODE (use) != SSA_NAME) 240 return; 241 242 /* We don't need to keep virtual operands in loop-closed form. */ 243 if (!is_gimple_reg (use)) 244 return; 245 246 ver = SSA_NAME_VERSION (use); 247 def_bb = gimple_bb (SSA_NAME_DEF_STMT (use)); 248 if (!def_bb) 249 return; 250 def_loop = def_bb->loop_father; 251 252 /* If the definition is not inside a loop, it is not interesting. */ 253 if (!loop_outer (def_loop)) 254 return; 255 256 /* If the use is not outside of the loop it is defined in, it is not 257 interesting. */ 258 if (flow_bb_inside_loop_p (def_loop, bb)) 259 return; 260 261 if (!use_blocks[ver]) 262 use_blocks[ver] = BITMAP_ALLOC (NULL); 263 bitmap_set_bit (use_blocks[ver], bb->index); 264 265 bitmap_set_bit (need_phis, ver); 266 } 267 268 /* For uses in STMT, mark names that are used outside of the loop they are 269 defined to rewrite. Record the set of blocks in that the ssa 270 names are defined to USE_BLOCKS and the ssa names themselves to 271 NEED_PHIS. */ 272 273 static void 274 find_uses_to_rename_stmt (gimple stmt, bitmap *use_blocks, bitmap need_phis) 275 { 276 ssa_op_iter iter; 277 tree var; 278 basic_block bb = gimple_bb (stmt); 279 280 if (is_gimple_debug (stmt)) 281 return; 282 283 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES) 284 find_uses_to_rename_use (bb, var, use_blocks, need_phis); 285 } 286 287 /* Marks names that are used in BB and outside of the loop they are 288 defined in for rewrite. Records the set of blocks in that the ssa 289 names are defined to USE_BLOCKS. Record the SSA names that will 290 need exit PHIs in NEED_PHIS. */ 291 292 static void 293 find_uses_to_rename_bb (basic_block bb, bitmap *use_blocks, bitmap need_phis) 294 { 295 gimple_stmt_iterator bsi; 296 edge e; 297 edge_iterator ei; 298 299 FOR_EACH_EDGE (e, ei, bb->succs) 300 for (bsi = gsi_start_phis (e->dest); !gsi_end_p (bsi); gsi_next (&bsi)) 301 find_uses_to_rename_use (bb, PHI_ARG_DEF_FROM_EDGE (gsi_stmt (bsi), e), 302 use_blocks, need_phis); 303 304 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi)) 305 find_uses_to_rename_stmt (gsi_stmt (bsi), use_blocks, need_phis); 306 } 307 308 /* Marks names that are used outside of the loop they are defined in 309 for rewrite. Records the set of blocks in that the ssa 310 names are defined to USE_BLOCKS. If CHANGED_BBS is not NULL, 311 scan only blocks in this set. */ 312 313 static void 314 find_uses_to_rename (bitmap changed_bbs, bitmap *use_blocks, bitmap need_phis) 315 { 316 basic_block bb; 317 unsigned index; 318 bitmap_iterator bi; 319 320 if (changed_bbs && !bitmap_empty_p (changed_bbs)) 321 { 322 EXECUTE_IF_SET_IN_BITMAP (changed_bbs, 0, index, bi) 323 { 324 find_uses_to_rename_bb (BASIC_BLOCK (index), use_blocks, need_phis); 325 } 326 } 327 else 328 { 329 FOR_EACH_BB (bb) 330 { 331 find_uses_to_rename_bb (bb, use_blocks, need_phis); 332 } 333 } 334 } 335 336 /* Rewrites the program into a loop closed ssa form -- i.e. inserts extra 337 phi nodes to ensure that no variable is used outside the loop it is 338 defined in. 339 340 This strengthening of the basic ssa form has several advantages: 341 342 1) Updating it during unrolling/peeling/versioning is trivial, since 343 we do not need to care about the uses outside of the loop. 344 2) The behavior of all uses of an induction variable is the same. 345 Without this, you need to distinguish the case when the variable 346 is used outside of the loop it is defined in, for example 347 348 for (i = 0; i < 100; i++) 349 { 350 for (j = 0; j < 100; j++) 351 { 352 k = i + j; 353 use1 (k); 354 } 355 use2 (k); 356 } 357 358 Looking from the outer loop with the normal SSA form, the first use of k 359 is not well-behaved, while the second one is an induction variable with 360 base 99 and step 1. 361 362 If CHANGED_BBS is not NULL, we look for uses outside loops only in 363 the basic blocks in this set. 364 365 UPDATE_FLAG is used in the call to update_ssa. See 366 TODO_update_ssa* for documentation. */ 367 368 void 369 rewrite_into_loop_closed_ssa (bitmap changed_bbs, unsigned update_flag) 370 { 371 bitmap loop_exits; 372 bitmap *use_blocks; 373 unsigned i, old_num_ssa_names; 374 bitmap names_to_rename; 375 376 loops_state_set (LOOP_CLOSED_SSA); 377 if (number_of_loops () <= 1) 378 return; 379 380 loop_exits = get_loops_exits (); 381 names_to_rename = BITMAP_ALLOC (NULL); 382 383 /* If the pass has caused the SSA form to be out-of-date, update it 384 now. */ 385 update_ssa (update_flag); 386 387 old_num_ssa_names = num_ssa_names; 388 use_blocks = XCNEWVEC (bitmap, old_num_ssa_names); 389 390 /* Find the uses outside loops. */ 391 find_uses_to_rename (changed_bbs, use_blocks, names_to_rename); 392 393 /* Add the PHI nodes on exits of the loops for the names we need to 394 rewrite. */ 395 add_exit_phis (names_to_rename, use_blocks, loop_exits); 396 397 for (i = 0; i < old_num_ssa_names; i++) 398 BITMAP_FREE (use_blocks[i]); 399 free (use_blocks); 400 BITMAP_FREE (loop_exits); 401 BITMAP_FREE (names_to_rename); 402 403 /* Fix up all the names found to be used outside their original 404 loops. */ 405 update_ssa (TODO_update_ssa); 406 } 407 408 /* Check invariants of the loop closed ssa form for the USE in BB. */ 409 410 static void 411 check_loop_closed_ssa_use (basic_block bb, tree use) 412 { 413 gimple def; 414 basic_block def_bb; 415 416 if (TREE_CODE (use) != SSA_NAME || !is_gimple_reg (use)) 417 return; 418 419 def = SSA_NAME_DEF_STMT (use); 420 def_bb = gimple_bb (def); 421 gcc_assert (!def_bb 422 || flow_bb_inside_loop_p (def_bb->loop_father, bb)); 423 } 424 425 /* Checks invariants of loop closed ssa form in statement STMT in BB. */ 426 427 static void 428 check_loop_closed_ssa_stmt (basic_block bb, gimple stmt) 429 { 430 ssa_op_iter iter; 431 tree var; 432 433 if (is_gimple_debug (stmt)) 434 return; 435 436 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES) 437 check_loop_closed_ssa_use (bb, var); 438 } 439 440 /* Checks that invariants of the loop closed ssa form are preserved. 441 Call verify_ssa when VERIFY_SSA_P is true. */ 442 443 DEBUG_FUNCTION void 444 verify_loop_closed_ssa (bool verify_ssa_p) 445 { 446 basic_block bb; 447 gimple_stmt_iterator bsi; 448 gimple phi; 449 edge e; 450 edge_iterator ei; 451 452 if (number_of_loops () <= 1) 453 return; 454 455 if (verify_ssa_p) 456 verify_ssa (false); 457 458 timevar_push (TV_VERIFY_LOOP_CLOSED); 459 460 FOR_EACH_BB (bb) 461 { 462 for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi)) 463 { 464 phi = gsi_stmt (bsi); 465 FOR_EACH_EDGE (e, ei, bb->preds) 466 check_loop_closed_ssa_use (e->src, 467 PHI_ARG_DEF_FROM_EDGE (phi, e)); 468 } 469 470 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi)) 471 check_loop_closed_ssa_stmt (bb, gsi_stmt (bsi)); 472 } 473 474 timevar_pop (TV_VERIFY_LOOP_CLOSED); 475 } 476 477 /* Split loop exit edge EXIT. The things are a bit complicated by a need to 478 preserve the loop closed ssa form. The newly created block is returned. */ 479 480 basic_block 481 split_loop_exit_edge (edge exit) 482 { 483 basic_block dest = exit->dest; 484 basic_block bb = split_edge (exit); 485 gimple phi, new_phi; 486 tree new_name, name; 487 use_operand_p op_p; 488 gimple_stmt_iterator psi; 489 source_location locus; 490 491 for (psi = gsi_start_phis (dest); !gsi_end_p (psi); gsi_next (&psi)) 492 { 493 phi = gsi_stmt (psi); 494 op_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, single_succ_edge (bb)); 495 locus = gimple_phi_arg_location_from_edge (phi, single_succ_edge (bb)); 496 497 name = USE_FROM_PTR (op_p); 498 499 /* If the argument of the PHI node is a constant, we do not need 500 to keep it inside loop. */ 501 if (TREE_CODE (name) != SSA_NAME) 502 continue; 503 504 /* Otherwise create an auxiliary phi node that will copy the value 505 of the SSA name out of the loop. */ 506 new_name = duplicate_ssa_name (name, NULL); 507 new_phi = create_phi_node (new_name, bb); 508 SSA_NAME_DEF_STMT (new_name) = new_phi; 509 add_phi_arg (new_phi, name, exit, locus); 510 SET_USE (op_p, new_name); 511 } 512 513 return bb; 514 } 515 516 /* Returns the basic block in that statements should be emitted for induction 517 variables incremented at the end of the LOOP. */ 518 519 basic_block 520 ip_end_pos (struct loop *loop) 521 { 522 return loop->latch; 523 } 524 525 /* Returns the basic block in that statements should be emitted for induction 526 variables incremented just before exit condition of a LOOP. */ 527 528 basic_block 529 ip_normal_pos (struct loop *loop) 530 { 531 gimple last; 532 basic_block bb; 533 edge exit; 534 535 if (!single_pred_p (loop->latch)) 536 return NULL; 537 538 bb = single_pred (loop->latch); 539 last = last_stmt (bb); 540 if (!last 541 || gimple_code (last) != GIMPLE_COND) 542 return NULL; 543 544 exit = EDGE_SUCC (bb, 0); 545 if (exit->dest == loop->latch) 546 exit = EDGE_SUCC (bb, 1); 547 548 if (flow_bb_inside_loop_p (loop, exit->dest)) 549 return NULL; 550 551 return bb; 552 } 553 554 /* Stores the standard position for induction variable increment in LOOP 555 (just before the exit condition if it is available and latch block is empty, 556 end of the latch block otherwise) to BSI. INSERT_AFTER is set to true if 557 the increment should be inserted after *BSI. */ 558 559 void 560 standard_iv_increment_position (struct loop *loop, gimple_stmt_iterator *bsi, 561 bool *insert_after) 562 { 563 basic_block bb = ip_normal_pos (loop), latch = ip_end_pos (loop); 564 gimple last = last_stmt (latch); 565 566 if (!bb 567 || (last && gimple_code (last) != GIMPLE_LABEL)) 568 { 569 *bsi = gsi_last_bb (latch); 570 *insert_after = true; 571 } 572 else 573 { 574 *bsi = gsi_last_bb (bb); 575 *insert_after = false; 576 } 577 } 578 579 /* Copies phi node arguments for duplicated blocks. The index of the first 580 duplicated block is FIRST_NEW_BLOCK. */ 581 582 static void 583 copy_phi_node_args (unsigned first_new_block) 584 { 585 unsigned i; 586 587 for (i = first_new_block; i < (unsigned) last_basic_block; i++) 588 BASIC_BLOCK (i)->flags |= BB_DUPLICATED; 589 590 for (i = first_new_block; i < (unsigned) last_basic_block; i++) 591 add_phi_args_after_copy_bb (BASIC_BLOCK (i)); 592 593 for (i = first_new_block; i < (unsigned) last_basic_block; i++) 594 BASIC_BLOCK (i)->flags &= ~BB_DUPLICATED; 595 } 596 597 598 /* The same as cfgloopmanip.c:duplicate_loop_to_header_edge, but also 599 updates the PHI nodes at start of the copied region. In order to 600 achieve this, only loops whose exits all lead to the same location 601 are handled. 602 603 Notice that we do not completely update the SSA web after 604 duplication. The caller is responsible for calling update_ssa 605 after the loop has been duplicated. */ 606 607 bool 608 gimple_duplicate_loop_to_header_edge (struct loop *loop, edge e, 609 unsigned int ndupl, sbitmap wont_exit, 610 edge orig, VEC (edge, heap) **to_remove, 611 int flags) 612 { 613 unsigned first_new_block; 614 615 if (!loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES)) 616 return false; 617 if (!loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS)) 618 return false; 619 620 #ifdef ENABLE_CHECKING 621 if (loops_state_satisfies_p (LOOP_CLOSED_SSA)) 622 verify_loop_closed_ssa (true); 623 #endif 624 625 first_new_block = last_basic_block; 626 if (!duplicate_loop_to_header_edge (loop, e, ndupl, wont_exit, 627 orig, to_remove, flags)) 628 return false; 629 630 /* Readd the removed phi args for e. */ 631 flush_pending_stmts (e); 632 633 /* Copy the phi node arguments. */ 634 copy_phi_node_args (first_new_block); 635 636 scev_reset (); 637 638 return true; 639 } 640 641 /* Returns true if we can unroll LOOP FACTOR times. Number 642 of iterations of the loop is returned in NITER. */ 643 644 bool 645 can_unroll_loop_p (struct loop *loop, unsigned factor, 646 struct tree_niter_desc *niter) 647 { 648 edge exit; 649 650 /* Check whether unrolling is possible. We only want to unroll loops 651 for that we are able to determine number of iterations. We also 652 want to split the extra iterations of the loop from its end, 653 therefore we require that the loop has precisely one 654 exit. */ 655 656 exit = single_dom_exit (loop); 657 if (!exit) 658 return false; 659 660 if (!number_of_iterations_exit (loop, exit, niter, false) 661 || niter->cmp == ERROR_MARK 662 /* Scalar evolutions analysis might have copy propagated 663 the abnormal ssa names into these expressions, hence 664 emitting the computations based on them during loop 665 unrolling might create overlapping life ranges for 666 them, and failures in out-of-ssa. */ 667 || contains_abnormal_ssa_name_p (niter->may_be_zero) 668 || contains_abnormal_ssa_name_p (niter->control.base) 669 || contains_abnormal_ssa_name_p (niter->control.step) 670 || contains_abnormal_ssa_name_p (niter->bound)) 671 return false; 672 673 /* And of course, we must be able to duplicate the loop. */ 674 if (!can_duplicate_loop_p (loop)) 675 return false; 676 677 /* The final loop should be small enough. */ 678 if (tree_num_loop_insns (loop, &eni_size_weights) * factor 679 > (unsigned) PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS)) 680 return false; 681 682 return true; 683 } 684 685 /* Determines the conditions that control execution of LOOP unrolled FACTOR 686 times. DESC is number of iterations of LOOP. ENTER_COND is set to 687 condition that must be true if the main loop can be entered. 688 EXIT_BASE, EXIT_STEP, EXIT_CMP and EXIT_BOUND are set to values describing 689 how the exit from the unrolled loop should be controlled. */ 690 691 static void 692 determine_exit_conditions (struct loop *loop, struct tree_niter_desc *desc, 693 unsigned factor, tree *enter_cond, 694 tree *exit_base, tree *exit_step, 695 enum tree_code *exit_cmp, tree *exit_bound) 696 { 697 gimple_seq stmts; 698 tree base = desc->control.base; 699 tree step = desc->control.step; 700 tree bound = desc->bound; 701 tree type = TREE_TYPE (step); 702 tree bigstep, delta; 703 tree min = lower_bound_in_type (type, type); 704 tree max = upper_bound_in_type (type, type); 705 enum tree_code cmp = desc->cmp; 706 tree cond = boolean_true_node, assum; 707 708 /* For pointers, do the arithmetics in the type of step. */ 709 base = fold_convert (type, base); 710 bound = fold_convert (type, bound); 711 712 *enter_cond = boolean_false_node; 713 *exit_base = NULL_TREE; 714 *exit_step = NULL_TREE; 715 *exit_cmp = ERROR_MARK; 716 *exit_bound = NULL_TREE; 717 gcc_assert (cmp != ERROR_MARK); 718 719 /* We only need to be correct when we answer question 720 "Do at least FACTOR more iterations remain?" in the unrolled loop. 721 Thus, transforming BASE + STEP * i <> BOUND to 722 BASE + STEP * i < BOUND is ok. */ 723 if (cmp == NE_EXPR) 724 { 725 if (tree_int_cst_sign_bit (step)) 726 cmp = GT_EXPR; 727 else 728 cmp = LT_EXPR; 729 } 730 else if (cmp == LT_EXPR) 731 { 732 gcc_assert (!tree_int_cst_sign_bit (step)); 733 } 734 else if (cmp == GT_EXPR) 735 { 736 gcc_assert (tree_int_cst_sign_bit (step)); 737 } 738 else 739 gcc_unreachable (); 740 741 /* The main body of the loop may be entered iff: 742 743 1) desc->may_be_zero is false. 744 2) it is possible to check that there are at least FACTOR iterations 745 of the loop, i.e., BOUND - step * FACTOR does not overflow. 746 3) # of iterations is at least FACTOR */ 747 748 if (!integer_zerop (desc->may_be_zero)) 749 cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, 750 invert_truthvalue (desc->may_be_zero), 751 cond); 752 753 bigstep = fold_build2 (MULT_EXPR, type, step, 754 build_int_cst_type (type, factor)); 755 delta = fold_build2 (MINUS_EXPR, type, bigstep, step); 756 if (cmp == LT_EXPR) 757 assum = fold_build2 (GE_EXPR, boolean_type_node, 758 bound, 759 fold_build2 (PLUS_EXPR, type, min, delta)); 760 else 761 assum = fold_build2 (LE_EXPR, boolean_type_node, 762 bound, 763 fold_build2 (PLUS_EXPR, type, max, delta)); 764 cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, assum, cond); 765 766 bound = fold_build2 (MINUS_EXPR, type, bound, delta); 767 assum = fold_build2 (cmp, boolean_type_node, base, bound); 768 cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, assum, cond); 769 770 cond = force_gimple_operand (unshare_expr (cond), &stmts, false, NULL_TREE); 771 if (stmts) 772 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts); 773 /* cond now may be a gimple comparison, which would be OK, but also any 774 other gimple rhs (say a && b). In this case we need to force it to 775 operand. */ 776 if (!is_gimple_condexpr (cond)) 777 { 778 cond = force_gimple_operand (cond, &stmts, true, NULL_TREE); 779 if (stmts) 780 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts); 781 } 782 *enter_cond = cond; 783 784 base = force_gimple_operand (unshare_expr (base), &stmts, true, NULL_TREE); 785 if (stmts) 786 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts); 787 bound = force_gimple_operand (unshare_expr (bound), &stmts, true, NULL_TREE); 788 if (stmts) 789 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts); 790 791 *exit_base = base; 792 *exit_step = bigstep; 793 *exit_cmp = cmp; 794 *exit_bound = bound; 795 } 796 797 /* Scales the frequencies of all basic blocks in LOOP that are strictly 798 dominated by BB by NUM/DEN. */ 799 800 static void 801 scale_dominated_blocks_in_loop (struct loop *loop, basic_block bb, 802 int num, int den) 803 { 804 basic_block son; 805 806 if (den == 0) 807 return; 808 809 for (son = first_dom_son (CDI_DOMINATORS, bb); 810 son; 811 son = next_dom_son (CDI_DOMINATORS, son)) 812 { 813 if (!flow_bb_inside_loop_p (loop, son)) 814 continue; 815 scale_bbs_frequencies_int (&son, 1, num, den); 816 scale_dominated_blocks_in_loop (loop, son, num, den); 817 } 818 } 819 820 /* Unroll LOOP FACTOR times. DESC describes number of iterations of LOOP. 821 EXIT is the exit of the loop to that DESC corresponds. 822 823 If N is number of iterations of the loop and MAY_BE_ZERO is the condition 824 under that loop exits in the first iteration even if N != 0, 825 826 while (1) 827 { 828 x = phi (init, next); 829 830 pre; 831 if (st) 832 break; 833 post; 834 } 835 836 becomes (with possibly the exit conditions formulated a bit differently, 837 avoiding the need to create a new iv): 838 839 if (MAY_BE_ZERO || N < FACTOR) 840 goto rest; 841 842 do 843 { 844 x = phi (init, next); 845 846 pre; 847 post; 848 pre; 849 post; 850 ... 851 pre; 852 post; 853 N -= FACTOR; 854 855 } while (N >= FACTOR); 856 857 rest: 858 init' = phi (init, x); 859 860 while (1) 861 { 862 x = phi (init', next); 863 864 pre; 865 if (st) 866 break; 867 post; 868 } 869 870 Before the loop is unrolled, TRANSFORM is called for it (only for the 871 unrolled loop, but not for its versioned copy). DATA is passed to 872 TRANSFORM. */ 873 874 /* Probability in % that the unrolled loop is entered. Just a guess. */ 875 #define PROB_UNROLLED_LOOP_ENTERED 90 876 877 void 878 tree_transform_and_unroll_loop (struct loop *loop, unsigned factor, 879 edge exit, struct tree_niter_desc *desc, 880 transform_callback transform, 881 void *data) 882 { 883 gimple exit_if; 884 tree ctr_before, ctr_after; 885 tree enter_main_cond, exit_base, exit_step, exit_bound; 886 enum tree_code exit_cmp; 887 gimple phi_old_loop, phi_new_loop, phi_rest; 888 gimple_stmt_iterator psi_old_loop, psi_new_loop; 889 tree init, next, new_init, var; 890 struct loop *new_loop; 891 basic_block rest, exit_bb; 892 edge old_entry, new_entry, old_latch, precond_edge, new_exit; 893 edge new_nonexit, e; 894 gimple_stmt_iterator bsi; 895 use_operand_p op; 896 bool ok; 897 unsigned est_niter, prob_entry, scale_unrolled, scale_rest, freq_e, freq_h; 898 unsigned new_est_niter, i, prob; 899 unsigned irr = loop_preheader_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP; 900 sbitmap wont_exit; 901 VEC (edge, heap) *to_remove = NULL; 902 903 est_niter = expected_loop_iterations (loop); 904 determine_exit_conditions (loop, desc, factor, 905 &enter_main_cond, &exit_base, &exit_step, 906 &exit_cmp, &exit_bound); 907 908 /* Let us assume that the unrolled loop is quite likely to be entered. */ 909 if (integer_nonzerop (enter_main_cond)) 910 prob_entry = REG_BR_PROB_BASE; 911 else 912 prob_entry = PROB_UNROLLED_LOOP_ENTERED * REG_BR_PROB_BASE / 100; 913 914 /* The values for scales should keep profile consistent, and somewhat close 915 to correct. 916 917 TODO: The current value of SCALE_REST makes it appear that the loop that 918 is created by splitting the remaining iterations of the unrolled loop is 919 executed the same number of times as the original loop, and with the same 920 frequencies, which is obviously wrong. This does not appear to cause 921 problems, so we do not bother with fixing it for now. To make the profile 922 correct, we would need to change the probability of the exit edge of the 923 loop, and recompute the distribution of frequencies in its body because 924 of this change (scale the frequencies of blocks before and after the exit 925 by appropriate factors). */ 926 scale_unrolled = prob_entry; 927 scale_rest = REG_BR_PROB_BASE; 928 929 new_loop = loop_version (loop, enter_main_cond, NULL, 930 prob_entry, scale_unrolled, scale_rest, true); 931 gcc_assert (new_loop != NULL); 932 update_ssa (TODO_update_ssa); 933 934 /* Determine the probability of the exit edge of the unrolled loop. */ 935 new_est_niter = est_niter / factor; 936 937 /* Without profile feedback, loops for that we do not know a better estimate 938 are assumed to roll 10 times. When we unroll such loop, it appears to 939 roll too little, and it may even seem to be cold. To avoid this, we 940 ensure that the created loop appears to roll at least 5 times (but at 941 most as many times as before unrolling). */ 942 if (new_est_niter < 5) 943 { 944 if (est_niter < 5) 945 new_est_niter = est_niter; 946 else 947 new_est_niter = 5; 948 } 949 950 /* Prepare the cfg and update the phi nodes. Move the loop exit to the 951 loop latch (and make its condition dummy, for the moment). */ 952 rest = loop_preheader_edge (new_loop)->src; 953 precond_edge = single_pred_edge (rest); 954 split_edge (loop_latch_edge (loop)); 955 exit_bb = single_pred (loop->latch); 956 957 /* Since the exit edge will be removed, the frequency of all the blocks 958 in the loop that are dominated by it must be scaled by 959 1 / (1 - exit->probability). */ 960 scale_dominated_blocks_in_loop (loop, exit->src, 961 REG_BR_PROB_BASE, 962 REG_BR_PROB_BASE - exit->probability); 963 964 bsi = gsi_last_bb (exit_bb); 965 exit_if = gimple_build_cond (EQ_EXPR, integer_zero_node, 966 integer_zero_node, 967 NULL_TREE, NULL_TREE); 968 969 gsi_insert_after (&bsi, exit_if, GSI_NEW_STMT); 970 new_exit = make_edge (exit_bb, rest, EDGE_FALSE_VALUE | irr); 971 rescan_loop_exit (new_exit, true, false); 972 973 /* Set the probability of new exit to the same of the old one. Fix 974 the frequency of the latch block, by scaling it back by 975 1 - exit->probability. */ 976 new_exit->count = exit->count; 977 new_exit->probability = exit->probability; 978 new_nonexit = single_pred_edge (loop->latch); 979 new_nonexit->probability = REG_BR_PROB_BASE - exit->probability; 980 new_nonexit->flags = EDGE_TRUE_VALUE; 981 new_nonexit->count -= exit->count; 982 if (new_nonexit->count < 0) 983 new_nonexit->count = 0; 984 scale_bbs_frequencies_int (&loop->latch, 1, new_nonexit->probability, 985 REG_BR_PROB_BASE); 986 987 old_entry = loop_preheader_edge (loop); 988 new_entry = loop_preheader_edge (new_loop); 989 old_latch = loop_latch_edge (loop); 990 for (psi_old_loop = gsi_start_phis (loop->header), 991 psi_new_loop = gsi_start_phis (new_loop->header); 992 !gsi_end_p (psi_old_loop); 993 gsi_next (&psi_old_loop), gsi_next (&psi_new_loop)) 994 { 995 phi_old_loop = gsi_stmt (psi_old_loop); 996 phi_new_loop = gsi_stmt (psi_new_loop); 997 998 init = PHI_ARG_DEF_FROM_EDGE (phi_old_loop, old_entry); 999 op = PHI_ARG_DEF_PTR_FROM_EDGE (phi_new_loop, new_entry); 1000 gcc_assert (operand_equal_for_phi_arg_p (init, USE_FROM_PTR (op))); 1001 next = PHI_ARG_DEF_FROM_EDGE (phi_old_loop, old_latch); 1002 1003 /* Prefer using original variable as a base for the new ssa name. 1004 This is necessary for virtual ops, and useful in order to avoid 1005 losing debug info for real ops. */ 1006 if (TREE_CODE (next) == SSA_NAME 1007 && useless_type_conversion_p (TREE_TYPE (next), 1008 TREE_TYPE (init))) 1009 var = SSA_NAME_VAR (next); 1010 else if (TREE_CODE (init) == SSA_NAME 1011 && useless_type_conversion_p (TREE_TYPE (init), 1012 TREE_TYPE (next))) 1013 var = SSA_NAME_VAR (init); 1014 else if (useless_type_conversion_p (TREE_TYPE (next), TREE_TYPE (init))) 1015 { 1016 var = create_tmp_var (TREE_TYPE (next), "unrinittmp"); 1017 add_referenced_var (var); 1018 } 1019 else 1020 { 1021 var = create_tmp_var (TREE_TYPE (init), "unrinittmp"); 1022 add_referenced_var (var); 1023 } 1024 1025 new_init = make_ssa_name (var, NULL); 1026 phi_rest = create_phi_node (new_init, rest); 1027 SSA_NAME_DEF_STMT (new_init) = phi_rest; 1028 1029 add_phi_arg (phi_rest, init, precond_edge, UNKNOWN_LOCATION); 1030 add_phi_arg (phi_rest, next, new_exit, UNKNOWN_LOCATION); 1031 SET_USE (op, new_init); 1032 } 1033 1034 remove_path (exit); 1035 1036 /* Transform the loop. */ 1037 if (transform) 1038 (*transform) (loop, data); 1039 1040 /* Unroll the loop and remove the exits in all iterations except for the 1041 last one. */ 1042 wont_exit = sbitmap_alloc (factor); 1043 sbitmap_ones (wont_exit); 1044 RESET_BIT (wont_exit, factor - 1); 1045 1046 ok = gimple_duplicate_loop_to_header_edge 1047 (loop, loop_latch_edge (loop), factor - 1, 1048 wont_exit, new_exit, &to_remove, DLTHE_FLAG_UPDATE_FREQ); 1049 free (wont_exit); 1050 gcc_assert (ok); 1051 1052 FOR_EACH_VEC_ELT (edge, to_remove, i, e) 1053 { 1054 ok = remove_path (e); 1055 gcc_assert (ok); 1056 } 1057 VEC_free (edge, heap, to_remove); 1058 update_ssa (TODO_update_ssa); 1059 1060 /* Ensure that the frequencies in the loop match the new estimated 1061 number of iterations, and change the probability of the new 1062 exit edge. */ 1063 freq_h = loop->header->frequency; 1064 freq_e = EDGE_FREQUENCY (loop_preheader_edge (loop)); 1065 if (freq_h != 0) 1066 scale_loop_frequencies (loop, freq_e * (new_est_niter + 1), freq_h); 1067 1068 exit_bb = single_pred (loop->latch); 1069 new_exit = find_edge (exit_bb, rest); 1070 new_exit->count = loop_preheader_edge (loop)->count; 1071 new_exit->probability = REG_BR_PROB_BASE / (new_est_niter + 1); 1072 1073 rest->count += new_exit->count; 1074 rest->frequency += EDGE_FREQUENCY (new_exit); 1075 1076 new_nonexit = single_pred_edge (loop->latch); 1077 prob = new_nonexit->probability; 1078 new_nonexit->probability = REG_BR_PROB_BASE - new_exit->probability; 1079 new_nonexit->count = exit_bb->count - new_exit->count; 1080 if (new_nonexit->count < 0) 1081 new_nonexit->count = 0; 1082 if (prob > 0) 1083 scale_bbs_frequencies_int (&loop->latch, 1, new_nonexit->probability, 1084 prob); 1085 1086 /* Finally create the new counter for number of iterations and add the new 1087 exit instruction. */ 1088 bsi = gsi_last_nondebug_bb (exit_bb); 1089 exit_if = gsi_stmt (bsi); 1090 create_iv (exit_base, exit_step, NULL_TREE, loop, 1091 &bsi, false, &ctr_before, &ctr_after); 1092 gimple_cond_set_code (exit_if, exit_cmp); 1093 gimple_cond_set_lhs (exit_if, ctr_after); 1094 gimple_cond_set_rhs (exit_if, exit_bound); 1095 update_stmt (exit_if); 1096 1097 #ifdef ENABLE_CHECKING 1098 verify_flow_info (); 1099 verify_dominators (CDI_DOMINATORS); 1100 verify_loop_structure (); 1101 verify_loop_closed_ssa (true); 1102 #endif 1103 } 1104 1105 /* Wrapper over tree_transform_and_unroll_loop for case we do not 1106 want to transform the loop before unrolling. The meaning 1107 of the arguments is the same as for tree_transform_and_unroll_loop. */ 1108 1109 void 1110 tree_unroll_loop (struct loop *loop, unsigned factor, 1111 edge exit, struct tree_niter_desc *desc) 1112 { 1113 tree_transform_and_unroll_loop (loop, factor, exit, desc, 1114 NULL, NULL); 1115 } 1116 1117 /* Rewrite the phi node at position PSI in function of the main 1118 induction variable MAIN_IV and insert the generated code at GSI. */ 1119 1120 static void 1121 rewrite_phi_with_iv (loop_p loop, 1122 gimple_stmt_iterator *psi, 1123 gimple_stmt_iterator *gsi, 1124 tree main_iv) 1125 { 1126 affine_iv iv; 1127 gimple stmt, phi = gsi_stmt (*psi); 1128 tree atype, mtype, val, res = PHI_RESULT (phi); 1129 1130 if (!is_gimple_reg (res) || res == main_iv) 1131 { 1132 gsi_next (psi); 1133 return; 1134 } 1135 1136 if (!simple_iv (loop, loop, res, &iv, true)) 1137 { 1138 gsi_next (psi); 1139 return; 1140 } 1141 1142 remove_phi_node (psi, false); 1143 1144 atype = TREE_TYPE (res); 1145 mtype = POINTER_TYPE_P (atype) ? sizetype : atype; 1146 val = fold_build2 (MULT_EXPR, mtype, unshare_expr (iv.step), 1147 fold_convert (mtype, main_iv)); 1148 val = fold_build2 (POINTER_TYPE_P (atype) 1149 ? POINTER_PLUS_EXPR : PLUS_EXPR, 1150 atype, unshare_expr (iv.base), val); 1151 val = force_gimple_operand_gsi (gsi, val, false, NULL_TREE, true, 1152 GSI_SAME_STMT); 1153 stmt = gimple_build_assign (res, val); 1154 gsi_insert_before (gsi, stmt, GSI_SAME_STMT); 1155 SSA_NAME_DEF_STMT (res) = stmt; 1156 } 1157 1158 /* Rewrite all the phi nodes of LOOP in function of the main induction 1159 variable MAIN_IV. */ 1160 1161 static void 1162 rewrite_all_phi_nodes_with_iv (loop_p loop, tree main_iv) 1163 { 1164 unsigned i; 1165 basic_block *bbs = get_loop_body_in_dom_order (loop); 1166 gimple_stmt_iterator psi; 1167 1168 for (i = 0; i < loop->num_nodes; i++) 1169 { 1170 basic_block bb = bbs[i]; 1171 gimple_stmt_iterator gsi = gsi_after_labels (bb); 1172 1173 if (bb->loop_father != loop) 1174 continue; 1175 1176 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); ) 1177 rewrite_phi_with_iv (loop, &psi, &gsi, main_iv); 1178 } 1179 1180 free (bbs); 1181 } 1182 1183 /* Bases all the induction variables in LOOP on a single induction 1184 variable (unsigned with base 0 and step 1), whose final value is 1185 compared with *NIT. When the IV type precision has to be larger 1186 than *NIT type precision, *NIT is converted to the larger type, the 1187 conversion code is inserted before the loop, and *NIT is updated to 1188 the new definition. When BUMP_IN_LATCH is true, the induction 1189 variable is incremented in the loop latch, otherwise it is 1190 incremented in the loop header. Return the induction variable that 1191 was created. */ 1192 1193 tree 1194 canonicalize_loop_ivs (struct loop *loop, tree *nit, bool bump_in_latch) 1195 { 1196 unsigned precision = TYPE_PRECISION (TREE_TYPE (*nit)); 1197 unsigned original_precision = precision; 1198 tree type, var_before; 1199 gimple_stmt_iterator gsi, psi; 1200 gimple stmt; 1201 edge exit = single_dom_exit (loop); 1202 gimple_seq stmts; 1203 enum machine_mode mode; 1204 bool unsigned_p = false; 1205 1206 for (psi = gsi_start_phis (loop->header); 1207 !gsi_end_p (psi); gsi_next (&psi)) 1208 { 1209 gimple phi = gsi_stmt (psi); 1210 tree res = PHI_RESULT (phi); 1211 bool uns; 1212 1213 type = TREE_TYPE (res); 1214 if (!is_gimple_reg (res) 1215 || (!INTEGRAL_TYPE_P (type) 1216 && !POINTER_TYPE_P (type)) 1217 || TYPE_PRECISION (type) < precision) 1218 continue; 1219 1220 uns = POINTER_TYPE_P (type) | TYPE_UNSIGNED (type); 1221 1222 if (TYPE_PRECISION (type) > precision) 1223 unsigned_p = uns; 1224 else 1225 unsigned_p |= uns; 1226 1227 precision = TYPE_PRECISION (type); 1228 } 1229 1230 mode = smallest_mode_for_size (precision, MODE_INT); 1231 precision = GET_MODE_PRECISION (mode); 1232 type = build_nonstandard_integer_type (precision, unsigned_p); 1233 1234 if (original_precision != precision) 1235 { 1236 *nit = fold_convert (type, *nit); 1237 *nit = force_gimple_operand (*nit, &stmts, true, NULL_TREE); 1238 if (stmts) 1239 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts); 1240 } 1241 1242 if (bump_in_latch) 1243 gsi = gsi_last_bb (loop->latch); 1244 else 1245 gsi = gsi_last_nondebug_bb (loop->header); 1246 create_iv (build_int_cst_type (type, 0), build_int_cst (type, 1), NULL_TREE, 1247 loop, &gsi, bump_in_latch, &var_before, NULL); 1248 1249 rewrite_all_phi_nodes_with_iv (loop, var_before); 1250 1251 stmt = last_stmt (exit->src); 1252 /* Make the loop exit if the control condition is not satisfied. */ 1253 if (exit->flags & EDGE_TRUE_VALUE) 1254 { 1255 edge te, fe; 1256 1257 extract_true_false_edges_from_block (exit->src, &te, &fe); 1258 te->flags = EDGE_FALSE_VALUE; 1259 fe->flags = EDGE_TRUE_VALUE; 1260 } 1261 gimple_cond_set_code (stmt, LT_EXPR); 1262 gimple_cond_set_lhs (stmt, var_before); 1263 gimple_cond_set_rhs (stmt, *nit); 1264 update_stmt (stmt); 1265 1266 return var_before; 1267 } 1268