1/* High-level loop manipulation functions. 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#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 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 49void 50create_iv (tree base, tree step, tree var, struct loop *loop, 51 block_stmt_iterator *incr_pos, bool after, 52 tree *var_before, tree *var_after) 53{ 54 tree stmt, initial, step1, stmts; 55 tree vb, va; 56 enum tree_code incr_op = PLUS_EXPR; 57 edge pe = loop_preheader_edge (loop); 58 59 if (!var) 60 { 61 var = create_tmp_var (TREE_TYPE (base), "ivtmp"); 62 add_referenced_tmp_var (var); 63 } 64 65 vb = make_ssa_name (var, NULL_TREE); 66 if (var_before) 67 *var_before = vb; 68 va = make_ssa_name (var, NULL_TREE); 69 if (var_after) 70 *var_after = va; 71 72 /* For easier readability of the created code, produce MINUS_EXPRs 73 when suitable. */ 74 if (TREE_CODE (step) == INTEGER_CST) 75 { 76 if (TYPE_UNSIGNED (TREE_TYPE (step))) 77 { 78 step1 = fold_build1 (NEGATE_EXPR, TREE_TYPE (step), step); 79 if (tree_int_cst_lt (step1, step)) 80 { 81 incr_op = MINUS_EXPR; 82 step = step1; 83 } 84 } 85 else 86 { 87 if (!tree_expr_nonnegative_p (step) 88 && may_negate_without_overflow_p (step)) 89 { 90 incr_op = MINUS_EXPR; 91 step = fold_build1 (NEGATE_EXPR, TREE_TYPE (step), step); 92 } 93 } 94 } 95 96 /* Gimplify the step if necessary. We put the computations in front of the 97 loop (i.e. the step should be loop invariant). */ 98 step = force_gimple_operand (step, &stmts, true, var); 99 if (stmts) 100 bsi_insert_on_edge_immediate_loop (pe, stmts); 101 102 stmt = build2 (MODIFY_EXPR, void_type_node, va, 103 build2 (incr_op, TREE_TYPE (base), 104 vb, step)); 105 SSA_NAME_DEF_STMT (va) = stmt; 106 if (after) 107 bsi_insert_after (incr_pos, stmt, BSI_NEW_STMT); 108 else 109 bsi_insert_before (incr_pos, stmt, BSI_NEW_STMT); 110 111 initial = force_gimple_operand (base, &stmts, true, var); 112 if (stmts) 113 bsi_insert_on_edge_immediate_loop (pe, stmts); 114 115 stmt = create_phi_node (vb, loop->header); 116 SSA_NAME_DEF_STMT (vb) = stmt; 117 add_phi_arg (stmt, initial, loop_preheader_edge (loop)); 118 add_phi_arg (stmt, va, loop_latch_edge (loop)); 119} 120 121/* Add exit phis for the USE on EXIT. */ 122 123static void 124add_exit_phis_edge (basic_block exit, tree use) 125{ 126 tree phi, def_stmt = SSA_NAME_DEF_STMT (use); 127 basic_block def_bb = bb_for_stmt (def_stmt); 128 struct loop *def_loop; 129 edge e; 130 edge_iterator ei; 131 132 /* Check that some of the edges entering the EXIT block exits a loop in 133 that USE is defined. */ 134 FOR_EACH_EDGE (e, ei, exit->preds) 135 { 136 def_loop = find_common_loop (def_bb->loop_father, e->src->loop_father); 137 if (!flow_bb_inside_loop_p (def_loop, e->dest)) 138 break; 139 } 140 141 if (!e) 142 return; 143 144 phi = create_phi_node (use, exit); 145 create_new_def_for (PHI_RESULT (phi), phi, PHI_RESULT_PTR (phi)); 146 FOR_EACH_EDGE (e, ei, exit->preds) 147 add_phi_arg (phi, use, e); 148} 149 150/* Add exit phis for VAR that is used in LIVEIN. 151 Exits of the loops are stored in EXITS. */ 152 153static void 154add_exit_phis_var (tree var, bitmap livein, bitmap exits) 155{ 156 bitmap def; 157 unsigned index; 158 basic_block def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (var)); 159 bitmap_iterator bi; 160 161 if (is_gimple_reg (var)) 162 bitmap_clear_bit (livein, def_bb->index); 163 else 164 bitmap_set_bit (livein, def_bb->index); 165 166 def = BITMAP_ALLOC (NULL); 167 bitmap_set_bit (def, def_bb->index); 168 compute_global_livein (livein, def); 169 BITMAP_FREE (def); 170 171 EXECUTE_IF_AND_IN_BITMAP (exits, livein, 0, index, bi) 172 { 173 add_exit_phis_edge (BASIC_BLOCK (index), var); 174 } 175} 176 177/* Add exit phis for the names marked in NAMES_TO_RENAME. 178 Exits of the loops are stored in EXITS. Sets of blocks where the ssa 179 names are used are stored in USE_BLOCKS. */ 180 181static void 182add_exit_phis (bitmap names_to_rename, bitmap *use_blocks, bitmap loop_exits) 183{ 184 unsigned i; 185 bitmap_iterator bi; 186 187 EXECUTE_IF_SET_IN_BITMAP (names_to_rename, 0, i, bi) 188 { 189 add_exit_phis_var (ssa_name (i), use_blocks[i], loop_exits); 190 } 191} 192 193/* Returns a bitmap of all loop exit edge targets. */ 194 195static bitmap 196get_loops_exits (void) 197{ 198 bitmap exits = BITMAP_ALLOC (NULL); 199 basic_block bb; 200 edge e; 201 edge_iterator ei; 202 203 FOR_EACH_BB (bb) 204 { 205 FOR_EACH_EDGE (e, ei, bb->preds) 206 if (e->src != ENTRY_BLOCK_PTR 207 && !flow_bb_inside_loop_p (e->src->loop_father, bb)) 208 { 209 bitmap_set_bit (exits, bb->index); 210 break; 211 } 212 } 213 214 return exits; 215} 216 217/* For USE in BB, if it is used outside of the loop it is defined in, 218 mark it for rewrite. Record basic block BB where it is used 219 to USE_BLOCKS. Record the ssa name index to NEED_PHIS bitmap. */ 220 221static void 222find_uses_to_rename_use (basic_block bb, tree use, bitmap *use_blocks, 223 bitmap need_phis) 224{ 225 unsigned ver; 226 basic_block def_bb; 227 struct loop *def_loop; 228 229 if (TREE_CODE (use) != SSA_NAME) 230 return; 231 232 /* We don't need to keep virtual operands in loop-closed form. */ 233 if (!is_gimple_reg (use)) 234 return; 235 236 ver = SSA_NAME_VERSION (use); 237 def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (use)); 238 if (!def_bb) 239 return; 240 def_loop = def_bb->loop_father; 241 242 /* If the definition is not inside loop, it is not interesting. */ 243 if (!def_loop->outer) 244 return; 245 246 if (!use_blocks[ver]) 247 use_blocks[ver] = BITMAP_ALLOC (NULL); 248 bitmap_set_bit (use_blocks[ver], bb->index); 249 250 bitmap_set_bit (need_phis, ver); 251} 252 253/* For uses in STMT, mark names that are used outside of the loop they are 254 defined to rewrite. Record the set of blocks in that the ssa 255 names are defined to USE_BLOCKS and the ssa names themselves to 256 NEED_PHIS. */ 257 258static void 259find_uses_to_rename_stmt (tree stmt, bitmap *use_blocks, bitmap need_phis) 260{ 261 ssa_op_iter iter; 262 tree var; 263 basic_block bb = bb_for_stmt (stmt); 264 265 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS) 266 find_uses_to_rename_use (bb, var, use_blocks, need_phis); 267} 268 269/* Marks names that are used in BB and outside of the loop they are 270 defined in for rewrite. Records the set of blocks in that the ssa 271 names are defined to USE_BLOCKS. Record the SSA names that will 272 need exit PHIs in NEED_PHIS. */ 273 274static void 275find_uses_to_rename_bb (basic_block bb, bitmap *use_blocks, bitmap need_phis) 276{ 277 block_stmt_iterator bsi; 278 edge e; 279 edge_iterator ei; 280 tree phi; 281 282 FOR_EACH_EDGE (e, ei, bb->succs) 283 for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi)) 284 find_uses_to_rename_use (bb, PHI_ARG_DEF_FROM_EDGE (phi, e), 285 use_blocks, need_phis); 286 287 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 288 find_uses_to_rename_stmt (bsi_stmt (bsi), use_blocks, need_phis); 289} 290 291/* Marks names that are used outside of the loop they are defined in 292 for rewrite. Records the set of blocks in that the ssa 293 names are defined to USE_BLOCKS. If CHANGED_BBS is not NULL, 294 scan only blocks in this set. */ 295 296static void 297find_uses_to_rename (bitmap changed_bbs, bitmap *use_blocks, bitmap need_phis) 298{ 299 basic_block bb; 300 unsigned index; 301 bitmap_iterator bi; 302 303 if (changed_bbs && !bitmap_empty_p (changed_bbs)) 304 { 305 EXECUTE_IF_SET_IN_BITMAP (changed_bbs, 0, index, bi) 306 { 307 find_uses_to_rename_bb (BASIC_BLOCK (index), use_blocks, need_phis); 308 } 309 } 310 else 311 { 312 FOR_EACH_BB (bb) 313 { 314 find_uses_to_rename_bb (bb, use_blocks, need_phis); 315 } 316 } 317} 318 319/* Rewrites the program into a loop closed ssa form -- i.e. inserts extra 320 phi nodes to ensure that no variable is used outside the loop it is 321 defined in. 322 323 This strengthening of the basic ssa form has several advantages: 324 325 1) Updating it during unrolling/peeling/versioning is trivial, since 326 we do not need to care about the uses outside of the loop. 327 2) The behavior of all uses of an induction variable is the same. 328 Without this, you need to distinguish the case when the variable 329 is used outside of the loop it is defined in, for example 330 331 for (i = 0; i < 100; i++) 332 { 333 for (j = 0; j < 100; j++) 334 { 335 k = i + j; 336 use1 (k); 337 } 338 use2 (k); 339 } 340 341 Looking from the outer loop with the normal SSA form, the first use of k 342 is not well-behaved, while the second one is an induction variable with 343 base 99 and step 1. 344 345 If CHANGED_BBS is not NULL, we look for uses outside loops only in 346 the basic blocks in this set. 347 348 UPDATE_FLAG is used in the call to update_ssa. See 349 TODO_update_ssa* for documentation. */ 350 351void 352rewrite_into_loop_closed_ssa (bitmap changed_bbs, unsigned update_flag) 353{ 354 bitmap loop_exits = get_loops_exits (); 355 bitmap *use_blocks; 356 unsigned i, old_num_ssa_names; 357 bitmap names_to_rename = BITMAP_ALLOC (NULL); 358 359 /* If the pass has caused the SSA form to be out-of-date, update it 360 now. */ 361 update_ssa (update_flag); 362 363 old_num_ssa_names = num_ssa_names; 364 use_blocks = xcalloc (old_num_ssa_names, sizeof (bitmap)); 365 366 /* Find the uses outside loops. */ 367 find_uses_to_rename (changed_bbs, use_blocks, names_to_rename); 368 369 /* Add the PHI nodes on exits of the loops for the names we need to 370 rewrite. */ 371 add_exit_phis (names_to_rename, use_blocks, loop_exits); 372 373 for (i = 0; i < old_num_ssa_names; i++) 374 BITMAP_FREE (use_blocks[i]); 375 free (use_blocks); 376 BITMAP_FREE (loop_exits); 377 BITMAP_FREE (names_to_rename); 378 379 /* Fix up all the names found to be used outside their original 380 loops. */ 381 update_ssa (TODO_update_ssa); 382} 383 384/* Check invariants of the loop closed ssa form for the USE in BB. */ 385 386static void 387check_loop_closed_ssa_use (basic_block bb, tree use) 388{ 389 tree def; 390 basic_block def_bb; 391 392 if (TREE_CODE (use) != SSA_NAME || !is_gimple_reg (use)) 393 return; 394 395 def = SSA_NAME_DEF_STMT (use); 396 def_bb = bb_for_stmt (def); 397 gcc_assert (!def_bb 398 || flow_bb_inside_loop_p (def_bb->loop_father, bb)); 399} 400 401/* Checks invariants of loop closed ssa form in statement STMT in BB. */ 402 403static void 404check_loop_closed_ssa_stmt (basic_block bb, tree stmt) 405{ 406 ssa_op_iter iter; 407 tree var; 408 409 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS) 410 check_loop_closed_ssa_use (bb, var); 411} 412 413/* Checks that invariants of the loop closed ssa form are preserved. */ 414 415void 416verify_loop_closed_ssa (void) 417{ 418 basic_block bb; 419 block_stmt_iterator bsi; 420 tree phi; 421 unsigned i; 422 423 if (current_loops == NULL) 424 return; 425 426 verify_ssa (false); 427 428 FOR_EACH_BB (bb) 429 { 430 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 431 for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++) 432 check_loop_closed_ssa_use (PHI_ARG_EDGE (phi, i)->src, 433 PHI_ARG_DEF (phi, i)); 434 435 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 436 check_loop_closed_ssa_stmt (bb, bsi_stmt (bsi)); 437 } 438} 439 440/* Split loop exit edge EXIT. The things are a bit complicated by a need to 441 preserve the loop closed ssa form. */ 442 443void 444split_loop_exit_edge (edge exit) 445{ 446 basic_block dest = exit->dest; 447 basic_block bb = loop_split_edge_with (exit, NULL); 448 tree phi, new_phi, new_name, name; 449 use_operand_p op_p; 450 451 for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi)) 452 { 453 op_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, single_succ_edge (bb)); 454 455 name = USE_FROM_PTR (op_p); 456 457 /* If the argument of the phi node is a constant, we do not need 458 to keep it inside loop. */ 459 if (TREE_CODE (name) != SSA_NAME) 460 continue; 461 462 /* Otherwise create an auxiliary phi node that will copy the value 463 of the ssa name out of the loop. */ 464 new_name = duplicate_ssa_name (name, NULL); 465 new_phi = create_phi_node (new_name, bb); 466 SSA_NAME_DEF_STMT (new_name) = new_phi; 467 add_phi_arg (new_phi, name, exit); 468 SET_USE (op_p, new_name); 469 } 470} 471 472/* Insert statement STMT to the edge E and update the loop structures. 473 Returns the newly created block (if any). */ 474 475basic_block 476bsi_insert_on_edge_immediate_loop (edge e, tree stmt) 477{ 478 basic_block src, dest, new_bb; 479 struct loop *loop_c; 480 481 src = e->src; 482 dest = e->dest; 483 484 loop_c = find_common_loop (src->loop_father, dest->loop_father); 485 486 new_bb = bsi_insert_on_edge_immediate (e, stmt); 487 488 if (!new_bb) 489 return NULL; 490 491 add_bb_to_loop (new_bb, loop_c); 492 if (dest->loop_father->latch == src) 493 dest->loop_father->latch = new_bb; 494 495 return new_bb; 496} 497 498/* Returns the basic block in that statements should be emitted for induction 499 variables incremented at the end of the LOOP. */ 500 501basic_block 502ip_end_pos (struct loop *loop) 503{ 504 return loop->latch; 505} 506 507/* Returns the basic block in that statements should be emitted for induction 508 variables incremented just before exit condition of a LOOP. */ 509 510basic_block 511ip_normal_pos (struct loop *loop) 512{ 513 tree last; 514 basic_block bb; 515 edge exit; 516 517 if (!single_pred_p (loop->latch)) 518 return NULL; 519 520 bb = single_pred (loop->latch); 521 last = last_stmt (bb); 522 if (TREE_CODE (last) != COND_EXPR) 523 return NULL; 524 525 exit = EDGE_SUCC (bb, 0); 526 if (exit->dest == loop->latch) 527 exit = EDGE_SUCC (bb, 1); 528 529 if (flow_bb_inside_loop_p (loop, exit->dest)) 530 return NULL; 531 532 return bb; 533} 534 535/* Stores the standard position for induction variable increment in LOOP 536 (just before the exit condition if it is available and latch block is empty, 537 end of the latch block otherwise) to BSI. INSERT_AFTER is set to true if 538 the increment should be inserted after *BSI. */ 539 540void 541standard_iv_increment_position (struct loop *loop, block_stmt_iterator *bsi, 542 bool *insert_after) 543{ 544 basic_block bb = ip_normal_pos (loop), latch = ip_end_pos (loop); 545 tree last = last_stmt (latch); 546 547 if (!bb 548 || (last && TREE_CODE (last) != LABEL_EXPR)) 549 { 550 *bsi = bsi_last (latch); 551 *insert_after = true; 552 } 553 else 554 { 555 *bsi = bsi_last (bb); 556 *insert_after = false; 557 } 558} 559 560/* Copies phi node arguments for duplicated blocks. The index of the first 561 duplicated block is FIRST_NEW_BLOCK. */ 562 563static void 564copy_phi_node_args (unsigned first_new_block) 565{ 566 unsigned i; 567 568 for (i = first_new_block; i < (unsigned) last_basic_block; i++) 569 BASIC_BLOCK (i)->flags |= BB_DUPLICATED; 570 571 for (i = first_new_block; i < (unsigned) last_basic_block; i++) 572 add_phi_args_after_copy_bb (BASIC_BLOCK (i)); 573 574 for (i = first_new_block; i < (unsigned) last_basic_block; i++) 575 BASIC_BLOCK (i)->flags &= ~BB_DUPLICATED; 576} 577 578 579/* The same as cfgloopmanip.c:duplicate_loop_to_header_edge, but also 580 updates the PHI nodes at start of the copied region. In order to 581 achieve this, only loops whose exits all lead to the same location 582 are handled. 583 584 Notice that we do not completely update the SSA web after 585 duplication. The caller is responsible for calling update_ssa 586 after the loop has been duplicated. */ 587 588bool 589tree_duplicate_loop_to_header_edge (struct loop *loop, edge e, 590 struct loops *loops, 591 unsigned int ndupl, sbitmap wont_exit, 592 edge orig, edge *to_remove, 593 unsigned int *n_to_remove, int flags) 594{ 595 unsigned first_new_block; 596 597 if (!(loops->state & LOOPS_HAVE_SIMPLE_LATCHES)) 598 return false; 599 if (!(loops->state & LOOPS_HAVE_PREHEADERS)) 600 return false; 601 602#ifdef ENABLE_CHECKING 603 verify_loop_closed_ssa (); 604#endif 605 606 first_new_block = last_basic_block; 607 if (!duplicate_loop_to_header_edge (loop, e, loops, ndupl, wont_exit, 608 orig, to_remove, n_to_remove, flags)) 609 return false; 610 611 /* Readd the removed phi args for e. */ 612 flush_pending_stmts (e); 613 614 /* Copy the phi node arguments. */ 615 copy_phi_node_args (first_new_block); 616 617 scev_reset (); 618 619 return true; 620} 621