1169689Skan/* High-level loop manipulation functions. 2169689Skan Copyright (C) 2004, 2005, 2006, 2007 Free Software Foundation, Inc. 3169689Skan 4169689SkanThis file is part of GCC. 5169689Skan 6169689SkanGCC is free software; you can redistribute it and/or modify it 7169689Skanunder the terms of the GNU General Public License as published by the 8169689SkanFree Software Foundation; either version 2, or (at your option) any 9169689Skanlater version. 10169689Skan 11169689SkanGCC is distributed in the hope that it will be useful, but WITHOUT 12169689SkanANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13169689SkanFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14169689Skanfor more details. 15169689Skan 16169689SkanYou should have received a copy of the GNU General Public License 17169689Skanalong with GCC; see the file COPYING. If not, write to the Free 18169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 19169689Skan02110-1301, USA. */ 20169689Skan 21169689Skan#include "config.h" 22169689Skan#include "system.h" 23169689Skan#include "coretypes.h" 24169689Skan#include "tm.h" 25169689Skan#include "tree.h" 26169689Skan#include "rtl.h" 27169689Skan#include "tm_p.h" 28169689Skan#include "hard-reg-set.h" 29169689Skan#include "basic-block.h" 30169689Skan#include "output.h" 31169689Skan#include "diagnostic.h" 32169689Skan#include "tree-flow.h" 33169689Skan#include "tree-dump.h" 34169689Skan#include "timevar.h" 35169689Skan#include "cfgloop.h" 36169689Skan#include "tree-pass.h" 37169689Skan#include "cfglayout.h" 38169689Skan#include "tree-scalar-evolution.h" 39169689Skan#include "params.h" 40169689Skan 41169689Skan/* Creates an induction variable with value BASE + STEP * iteration in LOOP. 42169689Skan It is expected that neither BASE nor STEP are shared with other expressions 43169689Skan (unless the sharing rules allow this). Use VAR as a base var_decl for it 44169689Skan (if NULL, a new temporary will be created). The increment will occur at 45169689Skan INCR_POS (after it if AFTER is true, before it otherwise). INCR_POS and 46169689Skan AFTER can be computed using standard_iv_increment_position. The ssa versions 47169689Skan of the variable before and after increment will be stored in VAR_BEFORE and 48169689Skan VAR_AFTER (unless they are NULL). */ 49169689Skan 50169689Skanvoid 51169689Skancreate_iv (tree base, tree step, tree var, struct loop *loop, 52169689Skan block_stmt_iterator *incr_pos, bool after, 53169689Skan tree *var_before, tree *var_after) 54169689Skan{ 55169689Skan tree stmt, initial, step1, stmts; 56169689Skan tree vb, va; 57169689Skan enum tree_code incr_op = PLUS_EXPR; 58169689Skan edge pe = loop_preheader_edge (loop); 59169689Skan 60169689Skan if (!var) 61169689Skan { 62169689Skan var = create_tmp_var (TREE_TYPE (base), "ivtmp"); 63169689Skan add_referenced_var (var); 64169689Skan } 65169689Skan 66169689Skan vb = make_ssa_name (var, NULL_TREE); 67169689Skan if (var_before) 68169689Skan *var_before = vb; 69169689Skan va = make_ssa_name (var, NULL_TREE); 70169689Skan if (var_after) 71169689Skan *var_after = va; 72169689Skan 73169689Skan /* For easier readability of the created code, produce MINUS_EXPRs 74169689Skan when suitable. */ 75169689Skan if (TREE_CODE (step) == INTEGER_CST) 76169689Skan { 77169689Skan if (TYPE_UNSIGNED (TREE_TYPE (step))) 78169689Skan { 79169689Skan step1 = fold_build1 (NEGATE_EXPR, TREE_TYPE (step), step); 80169689Skan if (tree_int_cst_lt (step1, step)) 81169689Skan { 82169689Skan incr_op = MINUS_EXPR; 83169689Skan step = step1; 84169689Skan } 85169689Skan } 86169689Skan else 87169689Skan { 88169689Skan bool ovf; 89169689Skan 90169689Skan if (!tree_expr_nonnegative_warnv_p (step, &ovf) 91169689Skan && may_negate_without_overflow_p (step)) 92169689Skan { 93169689Skan incr_op = MINUS_EXPR; 94169689Skan step = fold_build1 (NEGATE_EXPR, TREE_TYPE (step), step); 95169689Skan } 96169689Skan } 97169689Skan } 98169689Skan 99169689Skan /* Gimplify the step if necessary. We put the computations in front of the 100169689Skan loop (i.e. the step should be loop invariant). */ 101169689Skan step = force_gimple_operand (step, &stmts, true, var); 102169689Skan if (stmts) 103169689Skan bsi_insert_on_edge_immediate_loop (pe, stmts); 104169689Skan 105169689Skan stmt = build2 (MODIFY_EXPR, void_type_node, va, 106169689Skan build2 (incr_op, TREE_TYPE (base), 107169689Skan vb, step)); 108169689Skan SSA_NAME_DEF_STMT (va) = stmt; 109169689Skan if (after) 110169689Skan bsi_insert_after (incr_pos, stmt, BSI_NEW_STMT); 111169689Skan else 112169689Skan bsi_insert_before (incr_pos, stmt, BSI_NEW_STMT); 113169689Skan 114169689Skan initial = force_gimple_operand (base, &stmts, true, var); 115169689Skan if (stmts) 116169689Skan bsi_insert_on_edge_immediate_loop (pe, stmts); 117169689Skan 118169689Skan stmt = create_phi_node (vb, loop->header); 119169689Skan SSA_NAME_DEF_STMT (vb) = stmt; 120169689Skan add_phi_arg (stmt, initial, loop_preheader_edge (loop)); 121169689Skan add_phi_arg (stmt, va, loop_latch_edge (loop)); 122169689Skan} 123169689Skan 124169689Skan/* Add exit phis for the USE on EXIT. */ 125169689Skan 126169689Skanstatic void 127169689Skanadd_exit_phis_edge (basic_block exit, tree use) 128169689Skan{ 129169689Skan tree phi, def_stmt = SSA_NAME_DEF_STMT (use); 130169689Skan basic_block def_bb = bb_for_stmt (def_stmt); 131169689Skan struct loop *def_loop; 132169689Skan edge e; 133169689Skan edge_iterator ei; 134169689Skan 135169689Skan /* Check that some of the edges entering the EXIT block exits a loop in 136169689Skan that USE is defined. */ 137169689Skan FOR_EACH_EDGE (e, ei, exit->preds) 138169689Skan { 139169689Skan def_loop = find_common_loop (def_bb->loop_father, e->src->loop_father); 140169689Skan if (!flow_bb_inside_loop_p (def_loop, e->dest)) 141169689Skan break; 142169689Skan } 143169689Skan 144169689Skan if (!e) 145169689Skan return; 146169689Skan 147169689Skan phi = create_phi_node (use, exit); 148169689Skan create_new_def_for (PHI_RESULT (phi), phi, PHI_RESULT_PTR (phi)); 149169689Skan FOR_EACH_EDGE (e, ei, exit->preds) 150169689Skan add_phi_arg (phi, use, e); 151169689Skan} 152169689Skan 153169689Skan/* Add exit phis for VAR that is used in LIVEIN. 154169689Skan Exits of the loops are stored in EXITS. */ 155169689Skan 156169689Skanstatic void 157169689Skanadd_exit_phis_var (tree var, bitmap livein, bitmap exits) 158169689Skan{ 159169689Skan bitmap def; 160169689Skan unsigned index; 161169689Skan basic_block def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (var)); 162169689Skan bitmap_iterator bi; 163169689Skan 164169689Skan if (is_gimple_reg (var)) 165169689Skan bitmap_clear_bit (livein, def_bb->index); 166169689Skan else 167169689Skan bitmap_set_bit (livein, def_bb->index); 168169689Skan 169169689Skan def = BITMAP_ALLOC (NULL); 170169689Skan bitmap_set_bit (def, def_bb->index); 171169689Skan compute_global_livein (livein, def); 172169689Skan BITMAP_FREE (def); 173169689Skan 174169689Skan EXECUTE_IF_AND_IN_BITMAP (exits, livein, 0, index, bi) 175169689Skan { 176169689Skan add_exit_phis_edge (BASIC_BLOCK (index), var); 177169689Skan } 178169689Skan} 179169689Skan 180169689Skan/* Add exit phis for the names marked in NAMES_TO_RENAME. 181169689Skan Exits of the loops are stored in EXITS. Sets of blocks where the ssa 182169689Skan names are used are stored in USE_BLOCKS. */ 183169689Skan 184169689Skanstatic void 185169689Skanadd_exit_phis (bitmap names_to_rename, bitmap *use_blocks, bitmap loop_exits) 186169689Skan{ 187169689Skan unsigned i; 188169689Skan bitmap_iterator bi; 189169689Skan 190169689Skan EXECUTE_IF_SET_IN_BITMAP (names_to_rename, 0, i, bi) 191169689Skan { 192169689Skan add_exit_phis_var (ssa_name (i), use_blocks[i], loop_exits); 193169689Skan } 194169689Skan} 195169689Skan 196169689Skan/* Returns a bitmap of all loop exit edge targets. */ 197169689Skan 198169689Skanstatic bitmap 199169689Skanget_loops_exits (void) 200169689Skan{ 201169689Skan bitmap exits = BITMAP_ALLOC (NULL); 202169689Skan basic_block bb; 203169689Skan edge e; 204169689Skan edge_iterator ei; 205169689Skan 206169689Skan FOR_EACH_BB (bb) 207169689Skan { 208169689Skan FOR_EACH_EDGE (e, ei, bb->preds) 209169689Skan if (e->src != ENTRY_BLOCK_PTR 210169689Skan && !flow_bb_inside_loop_p (e->src->loop_father, bb)) 211169689Skan { 212169689Skan bitmap_set_bit (exits, bb->index); 213169689Skan break; 214169689Skan } 215169689Skan } 216169689Skan 217169689Skan return exits; 218169689Skan} 219169689Skan 220169689Skan/* For USE in BB, if it is used outside of the loop it is defined in, 221169689Skan mark it for rewrite. Record basic block BB where it is used 222169689Skan to USE_BLOCKS. Record the ssa name index to NEED_PHIS bitmap. */ 223169689Skan 224169689Skanstatic void 225169689Skanfind_uses_to_rename_use (basic_block bb, tree use, bitmap *use_blocks, 226169689Skan bitmap need_phis) 227169689Skan{ 228169689Skan unsigned ver; 229169689Skan basic_block def_bb; 230169689Skan struct loop *def_loop; 231169689Skan 232169689Skan if (TREE_CODE (use) != SSA_NAME) 233169689Skan return; 234169689Skan 235169689Skan /* We don't need to keep virtual operands in loop-closed form. */ 236169689Skan if (!is_gimple_reg (use)) 237169689Skan return; 238169689Skan 239169689Skan ver = SSA_NAME_VERSION (use); 240169689Skan def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (use)); 241169689Skan if (!def_bb) 242169689Skan return; 243169689Skan def_loop = def_bb->loop_father; 244169689Skan 245169689Skan /* If the definition is not inside loop, it is not interesting. */ 246169689Skan if (!def_loop->outer) 247169689Skan return; 248169689Skan 249169689Skan if (!use_blocks[ver]) 250169689Skan use_blocks[ver] = BITMAP_ALLOC (NULL); 251169689Skan bitmap_set_bit (use_blocks[ver], bb->index); 252169689Skan 253169689Skan bitmap_set_bit (need_phis, ver); 254169689Skan} 255169689Skan 256169689Skan/* For uses in STMT, mark names that are used outside of the loop they are 257169689Skan defined to rewrite. Record the set of blocks in that the ssa 258169689Skan names are defined to USE_BLOCKS and the ssa names themselves to 259169689Skan NEED_PHIS. */ 260169689Skan 261169689Skanstatic void 262169689Skanfind_uses_to_rename_stmt (tree stmt, bitmap *use_blocks, bitmap need_phis) 263169689Skan{ 264169689Skan ssa_op_iter iter; 265169689Skan tree var; 266169689Skan basic_block bb = bb_for_stmt (stmt); 267169689Skan 268169689Skan FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS) 269169689Skan find_uses_to_rename_use (bb, var, use_blocks, need_phis); 270169689Skan} 271169689Skan 272169689Skan/* Marks names that are used in BB and outside of the loop they are 273169689Skan defined in for rewrite. Records the set of blocks in that the ssa 274169689Skan names are defined to USE_BLOCKS. Record the SSA names that will 275169689Skan need exit PHIs in NEED_PHIS. */ 276169689Skan 277169689Skanstatic void 278169689Skanfind_uses_to_rename_bb (basic_block bb, bitmap *use_blocks, bitmap need_phis) 279169689Skan{ 280169689Skan block_stmt_iterator bsi; 281169689Skan edge e; 282169689Skan edge_iterator ei; 283169689Skan tree phi; 284169689Skan 285169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 286169689Skan for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi)) 287169689Skan find_uses_to_rename_use (bb, PHI_ARG_DEF_FROM_EDGE (phi, e), 288169689Skan use_blocks, need_phis); 289169689Skan 290169689Skan for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 291169689Skan find_uses_to_rename_stmt (bsi_stmt (bsi), use_blocks, need_phis); 292169689Skan} 293169689Skan 294169689Skan/* Marks names that are used outside of the loop they are defined in 295169689Skan for rewrite. Records the set of blocks in that the ssa 296169689Skan names are defined to USE_BLOCKS. If CHANGED_BBS is not NULL, 297169689Skan scan only blocks in this set. */ 298169689Skan 299169689Skanstatic void 300169689Skanfind_uses_to_rename (bitmap changed_bbs, bitmap *use_blocks, bitmap need_phis) 301169689Skan{ 302169689Skan basic_block bb; 303169689Skan unsigned index; 304169689Skan bitmap_iterator bi; 305169689Skan 306169689Skan if (changed_bbs && !bitmap_empty_p (changed_bbs)) 307169689Skan { 308169689Skan EXECUTE_IF_SET_IN_BITMAP (changed_bbs, 0, index, bi) 309169689Skan { 310169689Skan find_uses_to_rename_bb (BASIC_BLOCK (index), use_blocks, need_phis); 311169689Skan } 312169689Skan } 313169689Skan else 314169689Skan { 315169689Skan FOR_EACH_BB (bb) 316169689Skan { 317169689Skan find_uses_to_rename_bb (bb, use_blocks, need_phis); 318169689Skan } 319169689Skan } 320169689Skan} 321169689Skan 322169689Skan/* Rewrites the program into a loop closed ssa form -- i.e. inserts extra 323169689Skan phi nodes to ensure that no variable is used outside the loop it is 324169689Skan defined in. 325169689Skan 326169689Skan This strengthening of the basic ssa form has several advantages: 327169689Skan 328169689Skan 1) Updating it during unrolling/peeling/versioning is trivial, since 329169689Skan we do not need to care about the uses outside of the loop. 330169689Skan 2) The behavior of all uses of an induction variable is the same. 331169689Skan Without this, you need to distinguish the case when the variable 332169689Skan is used outside of the loop it is defined in, for example 333169689Skan 334169689Skan for (i = 0; i < 100; i++) 335169689Skan { 336169689Skan for (j = 0; j < 100; j++) 337169689Skan { 338169689Skan k = i + j; 339169689Skan use1 (k); 340169689Skan } 341169689Skan use2 (k); 342169689Skan } 343169689Skan 344169689Skan Looking from the outer loop with the normal SSA form, the first use of k 345169689Skan is not well-behaved, while the second one is an induction variable with 346169689Skan base 99 and step 1. 347169689Skan 348169689Skan If CHANGED_BBS is not NULL, we look for uses outside loops only in 349169689Skan the basic blocks in this set. 350169689Skan 351169689Skan UPDATE_FLAG is used in the call to update_ssa. See 352169689Skan TODO_update_ssa* for documentation. */ 353169689Skan 354169689Skanvoid 355169689Skanrewrite_into_loop_closed_ssa (bitmap changed_bbs, unsigned update_flag) 356169689Skan{ 357169689Skan bitmap loop_exits = get_loops_exits (); 358169689Skan bitmap *use_blocks; 359169689Skan unsigned i, old_num_ssa_names; 360169689Skan bitmap names_to_rename = BITMAP_ALLOC (NULL); 361169689Skan 362169689Skan /* If the pass has caused the SSA form to be out-of-date, update it 363169689Skan now. */ 364169689Skan update_ssa (update_flag); 365169689Skan 366169689Skan old_num_ssa_names = num_ssa_names; 367169689Skan use_blocks = XCNEWVEC (bitmap, old_num_ssa_names); 368169689Skan 369169689Skan /* Find the uses outside loops. */ 370169689Skan find_uses_to_rename (changed_bbs, use_blocks, names_to_rename); 371169689Skan 372169689Skan /* Add the PHI nodes on exits of the loops for the names we need to 373169689Skan rewrite. */ 374169689Skan add_exit_phis (names_to_rename, use_blocks, loop_exits); 375169689Skan 376169689Skan for (i = 0; i < old_num_ssa_names; i++) 377169689Skan BITMAP_FREE (use_blocks[i]); 378169689Skan free (use_blocks); 379169689Skan BITMAP_FREE (loop_exits); 380169689Skan BITMAP_FREE (names_to_rename); 381169689Skan 382169689Skan /* Fix up all the names found to be used outside their original 383169689Skan loops. */ 384169689Skan update_ssa (TODO_update_ssa); 385169689Skan} 386169689Skan 387169689Skan/* Check invariants of the loop closed ssa form for the USE in BB. */ 388169689Skan 389169689Skanstatic void 390169689Skancheck_loop_closed_ssa_use (basic_block bb, tree use) 391169689Skan{ 392169689Skan tree def; 393169689Skan basic_block def_bb; 394169689Skan 395169689Skan if (TREE_CODE (use) != SSA_NAME || !is_gimple_reg (use)) 396169689Skan return; 397169689Skan 398169689Skan def = SSA_NAME_DEF_STMT (use); 399169689Skan def_bb = bb_for_stmt (def); 400169689Skan gcc_assert (!def_bb 401169689Skan || flow_bb_inside_loop_p (def_bb->loop_father, bb)); 402169689Skan} 403169689Skan 404169689Skan/* Checks invariants of loop closed ssa form in statement STMT in BB. */ 405169689Skan 406169689Skanstatic void 407169689Skancheck_loop_closed_ssa_stmt (basic_block bb, tree stmt) 408169689Skan{ 409169689Skan ssa_op_iter iter; 410169689Skan tree var; 411169689Skan 412169689Skan FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS) 413169689Skan check_loop_closed_ssa_use (bb, var); 414169689Skan} 415169689Skan 416169689Skan/* Checks that invariants of the loop closed ssa form are preserved. */ 417169689Skan 418169689Skanvoid 419169689Skanverify_loop_closed_ssa (void) 420169689Skan{ 421169689Skan basic_block bb; 422169689Skan block_stmt_iterator bsi; 423169689Skan tree phi; 424169689Skan unsigned i; 425169689Skan 426169689Skan if (current_loops == NULL) 427169689Skan return; 428169689Skan 429169689Skan verify_ssa (false); 430169689Skan 431169689Skan FOR_EACH_BB (bb) 432169689Skan { 433169689Skan for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 434169689Skan for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++) 435169689Skan check_loop_closed_ssa_use (PHI_ARG_EDGE (phi, i)->src, 436169689Skan PHI_ARG_DEF (phi, i)); 437169689Skan 438169689Skan for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 439169689Skan check_loop_closed_ssa_stmt (bb, bsi_stmt (bsi)); 440169689Skan } 441169689Skan} 442169689Skan 443169689Skan/* Split loop exit edge EXIT. The things are a bit complicated by a need to 444169689Skan preserve the loop closed ssa form. */ 445169689Skan 446169689Skanvoid 447169689Skansplit_loop_exit_edge (edge exit) 448169689Skan{ 449169689Skan basic_block dest = exit->dest; 450169689Skan basic_block bb = loop_split_edge_with (exit, NULL); 451169689Skan tree phi, new_phi, new_name, name; 452169689Skan use_operand_p op_p; 453169689Skan 454169689Skan for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi)) 455169689Skan { 456169689Skan op_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, single_succ_edge (bb)); 457169689Skan 458169689Skan name = USE_FROM_PTR (op_p); 459169689Skan 460169689Skan /* If the argument of the phi node is a constant, we do not need 461169689Skan to keep it inside loop. */ 462169689Skan if (TREE_CODE (name) != SSA_NAME) 463169689Skan continue; 464169689Skan 465169689Skan /* Otherwise create an auxiliary phi node that will copy the value 466169689Skan of the ssa name out of the loop. */ 467169689Skan new_name = duplicate_ssa_name (name, NULL); 468169689Skan new_phi = create_phi_node (new_name, bb); 469169689Skan SSA_NAME_DEF_STMT (new_name) = new_phi; 470169689Skan add_phi_arg (new_phi, name, exit); 471169689Skan SET_USE (op_p, new_name); 472169689Skan } 473169689Skan} 474169689Skan 475169689Skan/* Insert statement STMT to the edge E and update the loop structures. 476169689Skan Returns the newly created block (if any). */ 477169689Skan 478169689Skanbasic_block 479169689Skanbsi_insert_on_edge_immediate_loop (edge e, tree stmt) 480169689Skan{ 481169689Skan basic_block src, dest, new_bb; 482169689Skan struct loop *loop_c; 483169689Skan 484169689Skan src = e->src; 485169689Skan dest = e->dest; 486169689Skan 487169689Skan loop_c = find_common_loop (src->loop_father, dest->loop_father); 488169689Skan 489169689Skan new_bb = bsi_insert_on_edge_immediate (e, stmt); 490169689Skan 491169689Skan if (!new_bb) 492169689Skan return NULL; 493169689Skan 494169689Skan add_bb_to_loop (new_bb, loop_c); 495169689Skan if (dest->loop_father->latch == src) 496169689Skan dest->loop_father->latch = new_bb; 497169689Skan 498169689Skan return new_bb; 499169689Skan} 500169689Skan 501169689Skan/* Returns the basic block in that statements should be emitted for induction 502169689Skan variables incremented at the end of the LOOP. */ 503169689Skan 504169689Skanbasic_block 505169689Skanip_end_pos (struct loop *loop) 506169689Skan{ 507169689Skan return loop->latch; 508169689Skan} 509169689Skan 510169689Skan/* Returns the basic block in that statements should be emitted for induction 511169689Skan variables incremented just before exit condition of a LOOP. */ 512169689Skan 513169689Skanbasic_block 514169689Skanip_normal_pos (struct loop *loop) 515169689Skan{ 516169689Skan tree last; 517169689Skan basic_block bb; 518169689Skan edge exit; 519169689Skan 520169689Skan if (!single_pred_p (loop->latch)) 521169689Skan return NULL; 522169689Skan 523169689Skan bb = single_pred (loop->latch); 524169689Skan last = last_stmt (bb); 525169689Skan if (TREE_CODE (last) != COND_EXPR) 526169689Skan return NULL; 527169689Skan 528169689Skan exit = EDGE_SUCC (bb, 0); 529169689Skan if (exit->dest == loop->latch) 530169689Skan exit = EDGE_SUCC (bb, 1); 531169689Skan 532169689Skan if (flow_bb_inside_loop_p (loop, exit->dest)) 533169689Skan return NULL; 534169689Skan 535169689Skan return bb; 536169689Skan} 537169689Skan 538169689Skan/* Stores the standard position for induction variable increment in LOOP 539169689Skan (just before the exit condition if it is available and latch block is empty, 540169689Skan end of the latch block otherwise) to BSI. INSERT_AFTER is set to true if 541169689Skan the increment should be inserted after *BSI. */ 542169689Skan 543169689Skanvoid 544169689Skanstandard_iv_increment_position (struct loop *loop, block_stmt_iterator *bsi, 545169689Skan bool *insert_after) 546169689Skan{ 547169689Skan basic_block bb = ip_normal_pos (loop), latch = ip_end_pos (loop); 548169689Skan tree last = last_stmt (latch); 549169689Skan 550169689Skan if (!bb 551169689Skan || (last && TREE_CODE (last) != LABEL_EXPR)) 552169689Skan { 553169689Skan *bsi = bsi_last (latch); 554169689Skan *insert_after = true; 555169689Skan } 556169689Skan else 557169689Skan { 558169689Skan *bsi = bsi_last (bb); 559169689Skan *insert_after = false; 560169689Skan } 561169689Skan} 562169689Skan 563169689Skan/* Copies phi node arguments for duplicated blocks. The index of the first 564169689Skan duplicated block is FIRST_NEW_BLOCK. */ 565169689Skan 566169689Skanstatic void 567169689Skancopy_phi_node_args (unsigned first_new_block) 568169689Skan{ 569169689Skan unsigned i; 570169689Skan 571169689Skan for (i = first_new_block; i < (unsigned) last_basic_block; i++) 572169689Skan BASIC_BLOCK (i)->flags |= BB_DUPLICATED; 573169689Skan 574169689Skan for (i = first_new_block; i < (unsigned) last_basic_block; i++) 575169689Skan add_phi_args_after_copy_bb (BASIC_BLOCK (i)); 576169689Skan 577169689Skan for (i = first_new_block; i < (unsigned) last_basic_block; i++) 578169689Skan BASIC_BLOCK (i)->flags &= ~BB_DUPLICATED; 579169689Skan} 580169689Skan 581169689Skan 582169689Skan/* The same as cfgloopmanip.c:duplicate_loop_to_header_edge, but also 583169689Skan updates the PHI nodes at start of the copied region. In order to 584169689Skan achieve this, only loops whose exits all lead to the same location 585169689Skan are handled. 586169689Skan 587169689Skan Notice that we do not completely update the SSA web after 588169689Skan duplication. The caller is responsible for calling update_ssa 589169689Skan after the loop has been duplicated. */ 590169689Skan 591169689Skanbool 592169689Skantree_duplicate_loop_to_header_edge (struct loop *loop, edge e, 593169689Skan struct loops *loops, 594169689Skan unsigned int ndupl, sbitmap wont_exit, 595169689Skan edge orig, edge *to_remove, 596169689Skan unsigned int *n_to_remove, int flags) 597169689Skan{ 598169689Skan unsigned first_new_block; 599169689Skan 600169689Skan if (!(loops->state & LOOPS_HAVE_SIMPLE_LATCHES)) 601169689Skan return false; 602169689Skan if (!(loops->state & LOOPS_HAVE_PREHEADERS)) 603169689Skan return false; 604169689Skan 605169689Skan#ifdef ENABLE_CHECKING 606169689Skan verify_loop_closed_ssa (); 607169689Skan#endif 608169689Skan 609169689Skan first_new_block = last_basic_block; 610169689Skan if (!duplicate_loop_to_header_edge (loop, e, loops, ndupl, wont_exit, 611169689Skan orig, to_remove, n_to_remove, flags)) 612169689Skan return false; 613169689Skan 614169689Skan /* Readd the removed phi args for e. */ 615169689Skan flush_pending_stmts (e); 616169689Skan 617169689Skan /* Copy the phi node arguments. */ 618169689Skan copy_phi_node_args (first_new_block); 619169689Skan 620169689Skan scev_reset (); 621169689Skan 622169689Skan return true; 623169689Skan} 624169689Skan 625169689Skan/* Build if (COND) goto THEN_LABEL; else goto ELSE_LABEL; */ 626169689Skan 627169689Skanstatic tree 628169689Skanbuild_if_stmt (tree cond, tree then_label, tree else_label) 629169689Skan{ 630169689Skan return build3 (COND_EXPR, void_type_node, 631169689Skan cond, 632169689Skan build1 (GOTO_EXPR, void_type_node, then_label), 633169689Skan build1 (GOTO_EXPR, void_type_node, else_label)); 634169689Skan} 635169689Skan 636169689Skan/* Returns true if we can unroll LOOP FACTOR times. Number 637169689Skan of iterations of the loop is returned in NITER. */ 638169689Skan 639169689Skanbool 640169689Skancan_unroll_loop_p (struct loop *loop, unsigned factor, 641169689Skan struct tree_niter_desc *niter) 642169689Skan{ 643169689Skan edge exit; 644169689Skan 645169689Skan /* Check whether unrolling is possible. We only want to unroll loops 646169689Skan for that we are able to determine number of iterations. We also 647169689Skan want to split the extra iterations of the loop from its end, 648169689Skan therefore we require that the loop has precisely one 649169689Skan exit. */ 650169689Skan 651169689Skan exit = single_dom_exit (loop); 652169689Skan if (!exit) 653169689Skan return false; 654169689Skan 655169689Skan if (!number_of_iterations_exit (loop, exit, niter, false) 656169689Skan || niter->cmp == ERROR_MARK 657169689Skan /* Scalar evolutions analysis might have copy propagated 658169689Skan the abnormal ssa names into these expressions, hence 659169689Skan emiting the computations based on them during loop 660169689Skan unrolling might create overlapping life ranges for 661169689Skan them, and failures in out-of-ssa. */ 662169689Skan || contains_abnormal_ssa_name_p (niter->may_be_zero) 663169689Skan || contains_abnormal_ssa_name_p (niter->control.base) 664169689Skan || contains_abnormal_ssa_name_p (niter->control.step) 665169689Skan || contains_abnormal_ssa_name_p (niter->bound)) 666169689Skan return false; 667169689Skan 668169689Skan /* And of course, we must be able to duplicate the loop. */ 669169689Skan if (!can_duplicate_loop_p (loop)) 670169689Skan return false; 671169689Skan 672169689Skan /* The final loop should be small enough. */ 673169689Skan if (tree_num_loop_insns (loop) * factor 674169689Skan > (unsigned) PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS)) 675169689Skan return false; 676169689Skan 677169689Skan return true; 678169689Skan} 679169689Skan 680169689Skan/* Determines the conditions that control execution of LOOP unrolled FACTOR 681169689Skan times. DESC is number of iterations of LOOP. ENTER_COND is set to 682169689Skan condition that must be true if the main loop can be entered. 683169689Skan EXIT_BASE, EXIT_STEP, EXIT_CMP and EXIT_BOUND are set to values describing 684169689Skan how the exit from the unrolled loop should be controlled. */ 685169689Skan 686169689Skanstatic void 687169689Skandetermine_exit_conditions (struct loop *loop, struct tree_niter_desc *desc, 688169689Skan unsigned factor, tree *enter_cond, 689169689Skan tree *exit_base, tree *exit_step, 690169689Skan enum tree_code *exit_cmp, tree *exit_bound) 691169689Skan{ 692169689Skan tree stmts; 693169689Skan tree base = desc->control.base; 694169689Skan tree step = desc->control.step; 695169689Skan tree bound = desc->bound; 696169689Skan tree type = TREE_TYPE (base); 697169689Skan tree bigstep, delta; 698169689Skan tree min = lower_bound_in_type (type, type); 699169689Skan tree max = upper_bound_in_type (type, type); 700169689Skan enum tree_code cmp = desc->cmp; 701169689Skan tree cond = boolean_true_node, assum; 702169689Skan 703169689Skan *enter_cond = boolean_false_node; 704169689Skan *exit_base = NULL_TREE; 705169689Skan *exit_step = NULL_TREE; 706169689Skan *exit_cmp = ERROR_MARK; 707169689Skan *exit_bound = NULL_TREE; 708169689Skan gcc_assert (cmp != ERROR_MARK); 709169689Skan 710169689Skan /* We only need to be correct when we answer question 711169689Skan "Do at least FACTOR more iterations remain?" in the unrolled loop. 712169689Skan Thus, transforming BASE + STEP * i <> BOUND to 713169689Skan BASE + STEP * i < BOUND is ok. */ 714169689Skan if (cmp == NE_EXPR) 715169689Skan { 716169689Skan if (tree_int_cst_sign_bit (step)) 717169689Skan cmp = GT_EXPR; 718169689Skan else 719169689Skan cmp = LT_EXPR; 720169689Skan } 721169689Skan else if (cmp == LT_EXPR) 722169689Skan { 723169689Skan gcc_assert (!tree_int_cst_sign_bit (step)); 724169689Skan } 725169689Skan else if (cmp == GT_EXPR) 726169689Skan { 727169689Skan gcc_assert (tree_int_cst_sign_bit (step)); 728169689Skan } 729169689Skan else 730169689Skan gcc_unreachable (); 731169689Skan 732169689Skan /* The main body of the loop may be entered iff: 733169689Skan 734169689Skan 1) desc->may_be_zero is false. 735169689Skan 2) it is possible to check that there are at least FACTOR iterations 736169689Skan of the loop, i.e., BOUND - step * FACTOR does not overflow. 737169689Skan 3) # of iterations is at least FACTOR */ 738169689Skan 739169689Skan if (!zero_p (desc->may_be_zero)) 740169689Skan cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, 741169689Skan invert_truthvalue (desc->may_be_zero), 742169689Skan cond); 743169689Skan 744169689Skan bigstep = fold_build2 (MULT_EXPR, type, step, 745169689Skan build_int_cst_type (type, factor)); 746169689Skan delta = fold_build2 (MINUS_EXPR, type, bigstep, step); 747169689Skan if (cmp == LT_EXPR) 748169689Skan assum = fold_build2 (GE_EXPR, boolean_type_node, 749169689Skan bound, 750169689Skan fold_build2 (PLUS_EXPR, type, min, delta)); 751169689Skan else 752169689Skan assum = fold_build2 (LE_EXPR, boolean_type_node, 753169689Skan bound, 754169689Skan fold_build2 (PLUS_EXPR, type, max, delta)); 755169689Skan cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, assum, cond); 756169689Skan 757169689Skan bound = fold_build2 (MINUS_EXPR, type, bound, delta); 758169689Skan assum = fold_build2 (cmp, boolean_type_node, base, bound); 759169689Skan cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, assum, cond); 760169689Skan 761169689Skan cond = force_gimple_operand (unshare_expr (cond), &stmts, false, NULL_TREE); 762169689Skan if (stmts) 763169689Skan bsi_insert_on_edge_immediate_loop (loop_preheader_edge (loop), stmts); 764169689Skan /* cond now may be a gimple comparison, which would be OK, but also any 765169689Skan other gimple rhs (say a && b). In this case we need to force it to 766169689Skan operand. */ 767169689Skan if (!is_gimple_condexpr (cond)) 768169689Skan { 769169689Skan cond = force_gimple_operand (cond, &stmts, true, NULL_TREE); 770169689Skan if (stmts) 771169689Skan bsi_insert_on_edge_immediate_loop (loop_preheader_edge (loop), stmts); 772169689Skan } 773169689Skan *enter_cond = cond; 774169689Skan 775169689Skan base = force_gimple_operand (unshare_expr (base), &stmts, true, NULL_TREE); 776169689Skan if (stmts) 777169689Skan bsi_insert_on_edge_immediate_loop (loop_preheader_edge (loop), stmts); 778169689Skan bound = force_gimple_operand (unshare_expr (bound), &stmts, true, NULL_TREE); 779169689Skan if (stmts) 780169689Skan bsi_insert_on_edge_immediate_loop (loop_preheader_edge (loop), stmts); 781169689Skan 782169689Skan *exit_base = base; 783169689Skan *exit_step = bigstep; 784169689Skan *exit_cmp = cmp; 785169689Skan *exit_bound = bound; 786169689Skan} 787169689Skan 788169689Skan/* Unroll LOOP FACTOR times. LOOPS is the loops tree. DESC describes 789169689Skan number of iterations of LOOP. EXIT is the exit of the loop to that 790169689Skan DESC corresponds. 791169689Skan 792169689Skan If N is number of iterations of the loop and MAY_BE_ZERO is the condition 793169689Skan under that loop exits in the first iteration even if N != 0, 794169689Skan 795169689Skan while (1) 796169689Skan { 797169689Skan x = phi (init, next); 798169689Skan 799169689Skan pre; 800169689Skan if (st) 801169689Skan break; 802169689Skan post; 803169689Skan } 804169689Skan 805169689Skan becomes (with possibly the exit conditions formulated a bit differently, 806169689Skan avoiding the need to create a new iv): 807169689Skan 808169689Skan if (MAY_BE_ZERO || N < FACTOR) 809169689Skan goto rest; 810169689Skan 811169689Skan do 812169689Skan { 813169689Skan x = phi (init, next); 814169689Skan 815169689Skan pre; 816169689Skan post; 817169689Skan pre; 818169689Skan post; 819169689Skan ... 820169689Skan pre; 821169689Skan post; 822169689Skan N -= FACTOR; 823169689Skan 824169689Skan } while (N >= FACTOR); 825169689Skan 826169689Skan rest: 827169689Skan init' = phi (init, x); 828169689Skan 829169689Skan while (1) 830169689Skan { 831169689Skan x = phi (init', next); 832169689Skan 833169689Skan pre; 834169689Skan if (st) 835169689Skan break; 836169689Skan post; 837169689Skan } */ 838169689Skan 839169689Skanvoid 840169689Skantree_unroll_loop (struct loops *loops, struct loop *loop, unsigned factor, 841169689Skan edge exit, struct tree_niter_desc *desc) 842169689Skan{ 843169689Skan tree dont_exit, exit_if, ctr_before, ctr_after; 844169689Skan tree enter_main_cond, exit_base, exit_step, exit_bound; 845169689Skan enum tree_code exit_cmp; 846169689Skan tree phi_old_loop, phi_new_loop, phi_rest, init, next, new_init, var; 847169689Skan struct loop *new_loop; 848169689Skan basic_block rest, exit_bb; 849169689Skan edge old_entry, new_entry, old_latch, precond_edge, new_exit; 850169689Skan edge nonexit, new_nonexit; 851169689Skan block_stmt_iterator bsi; 852169689Skan use_operand_p op; 853169689Skan bool ok; 854169689Skan unsigned est_niter; 855169689Skan unsigned irr = loop_preheader_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP; 856169689Skan sbitmap wont_exit; 857169689Skan 858169689Skan est_niter = expected_loop_iterations (loop); 859169689Skan determine_exit_conditions (loop, desc, factor, 860169689Skan &enter_main_cond, &exit_base, &exit_step, 861169689Skan &exit_cmp, &exit_bound); 862169689Skan 863169689Skan new_loop = loop_version (loops, loop, enter_main_cond, NULL, true); 864169689Skan gcc_assert (new_loop != NULL); 865169689Skan update_ssa (TODO_update_ssa); 866169689Skan 867169689Skan /* Unroll the loop and remove the old exits. */ 868169689Skan dont_exit = ((exit->flags & EDGE_TRUE_VALUE) 869169689Skan ? boolean_false_node 870169689Skan : boolean_true_node); 871169689Skan if (exit == EDGE_SUCC (exit->src, 0)) 872169689Skan nonexit = EDGE_SUCC (exit->src, 1); 873169689Skan else 874169689Skan nonexit = EDGE_SUCC (exit->src, 0); 875169689Skan nonexit->probability = REG_BR_PROB_BASE; 876169689Skan exit->probability = 0; 877169689Skan nonexit->count += exit->count; 878169689Skan exit->count = 0; 879169689Skan exit_if = last_stmt (exit->src); 880169689Skan COND_EXPR_COND (exit_if) = dont_exit; 881169689Skan update_stmt (exit_if); 882169689Skan 883169689Skan wont_exit = sbitmap_alloc (factor); 884169689Skan sbitmap_ones (wont_exit); 885169689Skan ok = tree_duplicate_loop_to_header_edge 886169689Skan (loop, loop_latch_edge (loop), loops, factor - 1, 887169689Skan wont_exit, NULL, NULL, NULL, DLTHE_FLAG_UPDATE_FREQ); 888169689Skan free (wont_exit); 889169689Skan gcc_assert (ok); 890169689Skan update_ssa (TODO_update_ssa); 891169689Skan 892169689Skan /* Prepare the cfg and update the phi nodes. */ 893169689Skan rest = loop_preheader_edge (new_loop)->src; 894169689Skan precond_edge = single_pred_edge (rest); 895169689Skan loop_split_edge_with (loop_latch_edge (loop), NULL); 896169689Skan exit_bb = single_pred (loop->latch); 897169689Skan 898169689Skan new_exit = make_edge (exit_bb, rest, EDGE_FALSE_VALUE | irr); 899169689Skan new_exit->count = loop_preheader_edge (loop)->count; 900169689Skan est_niter = est_niter / factor + 1; 901169689Skan new_exit->probability = REG_BR_PROB_BASE / est_niter; 902169689Skan 903169689Skan new_nonexit = single_pred_edge (loop->latch); 904169689Skan new_nonexit->flags = EDGE_TRUE_VALUE; 905169689Skan new_nonexit->probability = REG_BR_PROB_BASE - new_exit->probability; 906169689Skan 907169689Skan old_entry = loop_preheader_edge (loop); 908169689Skan new_entry = loop_preheader_edge (new_loop); 909169689Skan old_latch = loop_latch_edge (loop); 910169689Skan for (phi_old_loop = phi_nodes (loop->header), 911169689Skan phi_new_loop = phi_nodes (new_loop->header); 912169689Skan phi_old_loop; 913169689Skan phi_old_loop = PHI_CHAIN (phi_old_loop), 914169689Skan phi_new_loop = PHI_CHAIN (phi_new_loop)) 915169689Skan { 916169689Skan init = PHI_ARG_DEF_FROM_EDGE (phi_old_loop, old_entry); 917169689Skan op = PHI_ARG_DEF_PTR_FROM_EDGE (phi_new_loop, new_entry); 918169689Skan gcc_assert (operand_equal_for_phi_arg_p (init, USE_FROM_PTR (op))); 919169689Skan next = PHI_ARG_DEF_FROM_EDGE (phi_old_loop, old_latch); 920169689Skan 921169689Skan /* Prefer using original variable as a base for the new ssa name. 922169689Skan This is necessary for virtual ops, and useful in order to avoid 923169689Skan losing debug info for real ops. */ 924169689Skan if (TREE_CODE (next) == SSA_NAME) 925169689Skan var = SSA_NAME_VAR (next); 926169689Skan else if (TREE_CODE (init) == SSA_NAME) 927169689Skan var = SSA_NAME_VAR (init); 928169689Skan else 929169689Skan { 930169689Skan var = create_tmp_var (TREE_TYPE (init), "unrinittmp"); 931169689Skan add_referenced_var (var); 932169689Skan } 933169689Skan 934169689Skan new_init = make_ssa_name (var, NULL_TREE); 935169689Skan phi_rest = create_phi_node (new_init, rest); 936169689Skan SSA_NAME_DEF_STMT (new_init) = phi_rest; 937169689Skan 938169689Skan add_phi_arg (phi_rest, init, precond_edge); 939169689Skan add_phi_arg (phi_rest, next, new_exit); 940169689Skan SET_USE (op, new_init); 941169689Skan } 942169689Skan 943169689Skan /* Finally create the new counter for number of iterations and add the new 944169689Skan exit instruction. */ 945169689Skan bsi = bsi_last (exit_bb); 946169689Skan create_iv (exit_base, exit_step, NULL_TREE, loop, 947169689Skan &bsi, true, &ctr_before, &ctr_after); 948169689Skan exit_if = build_if_stmt (build2 (exit_cmp, boolean_type_node, ctr_after, 949169689Skan exit_bound), 950169689Skan tree_block_label (loop->latch), 951169689Skan tree_block_label (rest)); 952169689Skan bsi_insert_after (&bsi, exit_if, BSI_NEW_STMT); 953169689Skan 954169689Skan verify_flow_info (); 955169689Skan verify_dominators (CDI_DOMINATORS); 956169689Skan verify_loop_structure (loops); 957169689Skan verify_loop_closed_ssa (); 958169689Skan} 959