1169689Skan/* If-conversion for vectorizer. 2169689Skan Copyright (C) 2004, 2005 Free Software Foundation, Inc. 3169689Skan Contributed by Devang Patel <dpatel@apple.com> 4169689Skan 5169689SkanThis file is part of GCC. 6169689Skan 7169689SkanGCC is free software; you can redistribute it and/or modify it under 8169689Skanthe terms of the GNU General Public License as published by the Free 9169689SkanSoftware Foundation; either version 2, or (at your option) any later 10169689Skanversion. 11169689Skan 12169689SkanGCC is distributed in the hope that it will be useful, but WITHOUT ANY 13169689SkanWARRANTY; without even the implied warranty of MERCHANTABILITY or 14169689SkanFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15169689Skanfor more details. 16169689Skan 17169689SkanYou should have received a copy of the GNU General Public License 18169689Skanalong with GCC; see the file COPYING. If not, write to the Free 19169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 20169689Skan02110-1301, USA. */ 21169689Skan 22169689Skan/* This pass implements tree level if-conversion transformation of loops. 23169689Skan Initial goal is to help vectorizer vectorize loops with conditions. 24169689Skan 25169689Skan A short description of if-conversion: 26169689Skan 27169689Skan o Decide if a loop is if-convertible or not. 28169689Skan o Walk all loop basic blocks in breadth first order (BFS order). 29169689Skan o Remove conditional statements (at the end of basic block) 30169689Skan and propagate condition into destination basic blocks' 31169689Skan predicate list. 32169689Skan o Replace modify expression with conditional modify expression 33169689Skan using current basic block's condition. 34169689Skan o Merge all basic blocks 35169689Skan o Replace phi nodes with conditional modify expr 36169689Skan o Merge all basic blocks into header 37169689Skan 38169689Skan Sample transformation: 39169689Skan 40169689Skan INPUT 41169689Skan ----- 42169689Skan 43169689Skan # i_23 = PHI <0(0), i_18(10)>; 44169689Skan <L0>:; 45169689Skan j_15 = A[i_23]; 46169689Skan if (j_15 > 41) goto <L1>; else goto <L17>; 47169689Skan 48169689Skan <L17>:; 49169689Skan goto <bb 3> (<L3>); 50169689Skan 51169689Skan <L1>:; 52169689Skan 53169689Skan # iftmp.2_4 = PHI <0(8), 42(2)>; 54169689Skan <L3>:; 55169689Skan A[i_23] = iftmp.2_4; 56169689Skan i_18 = i_23 + 1; 57169689Skan if (i_18 <= 15) goto <L19>; else goto <L18>; 58169689Skan 59169689Skan <L19>:; 60169689Skan goto <bb 1> (<L0>); 61169689Skan 62169689Skan <L18>:; 63169689Skan 64169689Skan OUTPUT 65169689Skan ------ 66169689Skan 67169689Skan # i_23 = PHI <0(0), i_18(10)>; 68169689Skan <L0>:; 69169689Skan j_15 = A[i_23]; 70169689Skan 71169689Skan <L3>:; 72169689Skan iftmp.2_4 = j_15 > 41 ? 42 : 0; 73169689Skan A[i_23] = iftmp.2_4; 74169689Skan i_18 = i_23 + 1; 75169689Skan if (i_18 <= 15) goto <L19>; else goto <L18>; 76169689Skan 77169689Skan <L19>:; 78169689Skan goto <bb 1> (<L0>); 79169689Skan 80169689Skan <L18>:; 81169689Skan*/ 82169689Skan 83169689Skan#include "config.h" 84169689Skan#include "system.h" 85169689Skan#include "coretypes.h" 86169689Skan#include "tm.h" 87169689Skan#include "tree.h" 88169689Skan#include "c-common.h" 89169689Skan#include "flags.h" 90169689Skan#include "timevar.h" 91169689Skan#include "varray.h" 92169689Skan#include "rtl.h" 93169689Skan#include "basic-block.h" 94169689Skan#include "diagnostic.h" 95169689Skan#include "tree-flow.h" 96169689Skan#include "tree-dump.h" 97169689Skan#include "cfgloop.h" 98169689Skan#include "tree-chrec.h" 99169689Skan#include "tree-data-ref.h" 100169689Skan#include "tree-scalar-evolution.h" 101169689Skan#include "tree-pass.h" 102169689Skan#include "target.h" 103169689Skan 104169689Skan/* local function prototypes */ 105169689Skanstatic unsigned int main_tree_if_conversion (void); 106169689Skanstatic tree tree_if_convert_stmt (struct loop *loop, tree, tree, 107169689Skan block_stmt_iterator *); 108169689Skanstatic void tree_if_convert_cond_expr (struct loop *, tree, tree, 109169689Skan block_stmt_iterator *); 110169689Skanstatic bool if_convertible_phi_p (struct loop *, basic_block, tree); 111169689Skanstatic bool if_convertible_modify_expr_p (struct loop *, basic_block, tree); 112169689Skanstatic bool if_convertible_stmt_p (struct loop *, basic_block, tree); 113169689Skanstatic bool if_convertible_bb_p (struct loop *, basic_block, basic_block); 114169689Skanstatic bool if_convertible_loop_p (struct loop *, bool); 115169689Skanstatic void add_to_predicate_list (basic_block, tree); 116171825Skanstatic tree add_to_dst_predicate_list (struct loop * loop, edge, 117171825Skan tree, tree, 118169689Skan block_stmt_iterator *); 119169689Skanstatic void clean_predicate_lists (struct loop *loop); 120169689Skanstatic basic_block find_phi_replacement_condition (struct loop *loop, 121169689Skan basic_block, tree *, 122169689Skan block_stmt_iterator *); 123169689Skanstatic void replace_phi_with_cond_modify_expr (tree, tree, basic_block, 124169689Skan block_stmt_iterator *); 125169689Skanstatic void process_phi_nodes (struct loop *); 126169689Skanstatic void combine_blocks (struct loop *); 127169689Skanstatic tree ifc_temp_var (tree, tree); 128169689Skanstatic bool pred_blocks_visited_p (basic_block, bitmap *); 129169689Skanstatic basic_block * get_loop_body_in_if_conv_order (const struct loop *loop); 130169689Skanstatic bool bb_with_exit_edge_p (struct loop *, basic_block); 131169689Skan 132169689Skan/* List of basic blocks in if-conversion-suitable order. */ 133169689Skanstatic basic_block *ifc_bbs; 134169689Skan 135169689Skan/* Main entry point. 136169689Skan Apply if-conversion to the LOOP. Return true if successful otherwise return 137169689Skan false. If false is returned then loop remains unchanged. 138169689Skan FOR_VECTORIZER is a boolean flag. It indicates whether if-conversion is used 139169689Skan for vectorizer or not. If it is used for vectorizer, additional checks are 140169689Skan used. (Vectorization checks are not yet implemented). */ 141169689Skan 142169689Skanstatic bool 143169689Skantree_if_conversion (struct loop *loop, bool for_vectorizer) 144169689Skan{ 145169689Skan basic_block bb; 146169689Skan block_stmt_iterator itr; 147169689Skan unsigned int i; 148169689Skan 149169689Skan ifc_bbs = NULL; 150169689Skan 151169689Skan /* if-conversion is not appropriate for all loops. First, check if loop is 152169689Skan if-convertible or not. */ 153169689Skan if (!if_convertible_loop_p (loop, for_vectorizer)) 154169689Skan { 155169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 156169689Skan fprintf (dump_file,"-------------------------\n"); 157169689Skan if (ifc_bbs) 158169689Skan { 159169689Skan free (ifc_bbs); 160169689Skan ifc_bbs = NULL; 161169689Skan } 162169689Skan free_dominance_info (CDI_POST_DOMINATORS); 163169689Skan return false; 164169689Skan } 165169689Skan 166169689Skan /* Do actual work now. */ 167169689Skan for (i = 0; i < loop->num_nodes; i++) 168169689Skan { 169171825Skan tree cond; 170171825Skan 171169689Skan bb = ifc_bbs [i]; 172169689Skan 173169689Skan /* Update condition using predicate list. */ 174169689Skan cond = bb->aux; 175169689Skan 176169689Skan /* Process all statements in this basic block. 177169689Skan Remove conditional expression, if any, and annotate 178169689Skan destination basic block(s) appropriately. */ 179169689Skan for (itr = bsi_start (bb); !bsi_end_p (itr); /* empty */) 180169689Skan { 181169689Skan tree t = bsi_stmt (itr); 182169689Skan cond = tree_if_convert_stmt (loop, t, cond, &itr); 183169689Skan if (!bsi_end_p (itr)) 184169689Skan bsi_next (&itr); 185169689Skan } 186169689Skan 187169689Skan /* If current bb has only one successor, then consider it as an 188169689Skan unconditional goto. */ 189169689Skan if (single_succ_p (bb)) 190169689Skan { 191169689Skan basic_block bb_n = single_succ (bb); 192169689Skan if (cond != NULL_TREE) 193169689Skan add_to_predicate_list (bb_n, cond); 194169689Skan } 195169689Skan } 196169689Skan 197169689Skan /* Now, all statements are if-converted and basic blocks are 198169689Skan annotated appropriately. Combine all basic block into one huge 199169689Skan basic block. */ 200169689Skan combine_blocks (loop); 201169689Skan 202169689Skan /* clean up */ 203169689Skan clean_predicate_lists (loop); 204169689Skan free (ifc_bbs); 205169689Skan ifc_bbs = NULL; 206169689Skan 207169689Skan return true; 208169689Skan} 209169689Skan 210169689Skan/* if-convert stmt T which is part of LOOP. 211169689Skan If T is a MODIFY_EXPR than it is converted into conditional modify 212169689Skan expression using COND. For conditional expressions, add condition in the 213169689Skan destination basic block's predicate list and remove conditional 214169689Skan expression itself. BSI is the iterator used to traverse statements of 215169689Skan loop. It is used here when it is required to delete current statement. */ 216169689Skan 217169689Skanstatic tree 218169689Skantree_if_convert_stmt (struct loop * loop, tree t, tree cond, 219169689Skan block_stmt_iterator *bsi) 220169689Skan{ 221169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 222169689Skan { 223169689Skan fprintf (dump_file, "------if-convert stmt\n"); 224169689Skan print_generic_stmt (dump_file, t, TDF_SLIM); 225169689Skan print_generic_stmt (dump_file, cond, TDF_SLIM); 226169689Skan } 227169689Skan 228169689Skan switch (TREE_CODE (t)) 229169689Skan { 230169689Skan /* Labels are harmless here. */ 231169689Skan case LABEL_EXPR: 232169689Skan break; 233169689Skan 234169689Skan case MODIFY_EXPR: 235169689Skan /* This modify_expr is killing previous value of LHS. Appropriate value will 236169689Skan be selected by PHI node based on condition. It is possible that before 237169689Skan this transformation, PHI nodes was selecting default value and now it will 238169689Skan use this new value. This is OK because it does not change validity the 239169689Skan program. */ 240169689Skan break; 241169689Skan 242169689Skan case COND_EXPR: 243169689Skan /* Update destination blocks' predicate list and remove this 244169689Skan condition expression. */ 245169689Skan tree_if_convert_cond_expr (loop, t, cond, bsi); 246169689Skan cond = NULL_TREE; 247169689Skan break; 248169689Skan 249169689Skan default: 250169689Skan gcc_unreachable (); 251169689Skan } 252169689Skan return cond; 253169689Skan} 254169689Skan 255169689Skan/* STMT is COND_EXPR. Update two destination's predicate list. 256169689Skan Remove COND_EXPR, if it is not the loop exit condition. Otherwise 257169689Skan update loop exit condition appropriately. BSI is the iterator 258169689Skan used to traverse statement list. STMT is part of loop LOOP. */ 259169689Skan 260169689Skanstatic void 261169689Skantree_if_convert_cond_expr (struct loop *loop, tree stmt, tree cond, 262169689Skan block_stmt_iterator *bsi) 263169689Skan{ 264169689Skan tree c, c2; 265169689Skan edge true_edge, false_edge; 266169689Skan 267169689Skan gcc_assert (TREE_CODE (stmt) == COND_EXPR); 268169689Skan 269169689Skan c = COND_EXPR_COND (stmt); 270169689Skan 271169689Skan extract_true_false_edges_from_block (bb_for_stmt (stmt), 272169689Skan &true_edge, &false_edge); 273169689Skan 274169689Skan /* Add new condition into destination's predicate list. */ 275169689Skan 276169689Skan /* If 'c' is true then TRUE_EDGE is taken. */ 277171825Skan add_to_dst_predicate_list (loop, true_edge, cond, 278169689Skan unshare_expr (c), bsi); 279169689Skan 280169689Skan /* If 'c' is false then FALSE_EDGE is taken. */ 281169689Skan c2 = invert_truthvalue (unshare_expr (c)); 282171825Skan add_to_dst_predicate_list (loop, false_edge, cond, c2, bsi); 283169689Skan 284169689Skan /* Now this conditional statement is redundant. Remove it. 285169689Skan But, do not remove exit condition! Update exit condition 286169689Skan using new condition. */ 287169689Skan if (!bb_with_exit_edge_p (loop, bb_for_stmt (stmt))) 288169689Skan { 289169689Skan bsi_remove (bsi, true); 290169689Skan cond = NULL_TREE; 291169689Skan } 292169689Skan return; 293169689Skan} 294169689Skan 295169689Skan/* Return true, iff PHI is if-convertible. PHI is part of loop LOOP 296169689Skan and it belongs to basic block BB. 297169689Skan PHI is not if-convertible 298169689Skan - if it has more than 2 arguments. 299169689Skan - Virtual PHI is immediately used in another PHI node. */ 300169689Skan 301169689Skanstatic bool 302169689Skanif_convertible_phi_p (struct loop *loop, basic_block bb, tree phi) 303169689Skan{ 304169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 305169689Skan { 306169689Skan fprintf (dump_file, "-------------------------\n"); 307169689Skan print_generic_stmt (dump_file, phi, TDF_SLIM); 308169689Skan } 309169689Skan 310169689Skan if (bb != loop->header && PHI_NUM_ARGS (phi) != 2) 311169689Skan { 312169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 313169689Skan fprintf (dump_file, "More than two phi node args.\n"); 314169689Skan return false; 315169689Skan } 316169689Skan 317169689Skan if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi)))) 318169689Skan { 319169689Skan imm_use_iterator imm_iter; 320169689Skan use_operand_p use_p; 321169689Skan FOR_EACH_IMM_USE_FAST (use_p, imm_iter, PHI_RESULT (phi)) 322169689Skan { 323169689Skan if (TREE_CODE (USE_STMT (use_p)) == PHI_NODE) 324169689Skan { 325169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 326169689Skan fprintf (dump_file, "Difficult to handle this virtual phi.\n"); 327169689Skan return false; 328169689Skan } 329169689Skan } 330169689Skan } 331169689Skan 332169689Skan return true; 333169689Skan} 334169689Skan 335169689Skan/* Return true, if M_EXPR is if-convertible. 336169689Skan MODIFY_EXPR is not if-convertible if, 337169689Skan - It is not movable. 338169689Skan - It could trap. 339169689Skan - LHS is not var decl. 340169689Skan MODIFY_EXPR is part of block BB, which is inside loop LOOP. 341169689Skan*/ 342169689Skan 343169689Skanstatic bool 344169689Skanif_convertible_modify_expr_p (struct loop *loop, basic_block bb, tree m_expr) 345169689Skan{ 346169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 347169689Skan { 348169689Skan fprintf (dump_file, "-------------------------\n"); 349169689Skan print_generic_stmt (dump_file, m_expr, TDF_SLIM); 350169689Skan } 351169689Skan 352169689Skan /* Be conservative and do not handle immovable expressions. */ 353169689Skan if (movement_possibility (m_expr) == MOVE_IMPOSSIBLE) 354169689Skan { 355169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 356169689Skan fprintf (dump_file, "stmt is movable. Don't take risk\n"); 357169689Skan return false; 358169689Skan } 359169689Skan 360169689Skan /* See if it needs speculative loading or not. */ 361169689Skan if (bb != loop->header 362169689Skan && tree_could_trap_p (TREE_OPERAND (m_expr, 1))) 363169689Skan { 364169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 365169689Skan fprintf (dump_file, "tree could trap...\n"); 366169689Skan return false; 367169689Skan } 368169689Skan 369169689Skan if (TREE_CODE (TREE_OPERAND (m_expr, 1)) == CALL_EXPR) 370169689Skan { 371169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 372169689Skan fprintf (dump_file, "CALL_EXPR \n"); 373169689Skan return false; 374169689Skan } 375169689Skan 376169689Skan if (TREE_CODE (TREE_OPERAND (m_expr, 0)) != SSA_NAME 377169689Skan && bb != loop->header 378169689Skan && !bb_with_exit_edge_p (loop, bb)) 379169689Skan { 380169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 381169689Skan { 382169689Skan fprintf (dump_file, "LHS is not var\n"); 383169689Skan print_generic_stmt (dump_file, m_expr, TDF_SLIM); 384169689Skan } 385169689Skan return false; 386169689Skan } 387169689Skan 388169689Skan 389169689Skan return true; 390169689Skan} 391169689Skan 392169689Skan/* Return true, iff STMT is if-convertible. 393169689Skan Statement is if-convertible if, 394169689Skan - It is if-convertible MODIFY_EXPR 395169689Skan - IT is LABEL_EXPR or COND_EXPR. 396169689Skan STMT is inside block BB, which is inside loop LOOP. */ 397169689Skan 398169689Skanstatic bool 399169689Skanif_convertible_stmt_p (struct loop *loop, basic_block bb, tree stmt) 400169689Skan{ 401169689Skan switch (TREE_CODE (stmt)) 402169689Skan { 403169689Skan case LABEL_EXPR: 404169689Skan break; 405169689Skan 406169689Skan case MODIFY_EXPR: 407169689Skan 408169689Skan if (!if_convertible_modify_expr_p (loop, bb, stmt)) 409169689Skan return false; 410169689Skan break; 411169689Skan 412169689Skan case COND_EXPR: 413169689Skan break; 414169689Skan 415169689Skan default: 416169689Skan /* Don't know what to do with 'em so don't do anything. */ 417169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 418169689Skan { 419169689Skan fprintf (dump_file, "don't know what to do\n"); 420169689Skan print_generic_stmt (dump_file, stmt, TDF_SLIM); 421169689Skan } 422169689Skan return false; 423169689Skan break; 424169689Skan } 425169689Skan 426169689Skan return true; 427169689Skan} 428169689Skan 429169689Skan/* Return true, iff BB is if-convertible. 430169689Skan Note: This routine does _not_ check basic block statements and phis. 431169689Skan Basic block is not if-convertible if, 432169689Skan - Basic block is non-empty and it is after exit block (in BFS order). 433169689Skan - Basic block is after exit block but before latch. 434169689Skan - Basic block edge(s) is not normal. 435169689Skan EXIT_BB_SEEN is true if basic block with exit edge is already seen. 436169689Skan BB is inside loop LOOP. */ 437169689Skan 438169689Skanstatic bool 439169689Skanif_convertible_bb_p (struct loop *loop, basic_block bb, basic_block exit_bb) 440169689Skan{ 441169689Skan edge e; 442169689Skan edge_iterator ei; 443169689Skan 444169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 445169689Skan fprintf (dump_file, "----------[%d]-------------\n", bb->index); 446169689Skan 447169689Skan if (exit_bb) 448169689Skan { 449169689Skan if (bb != loop->latch) 450169689Skan { 451169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 452169689Skan fprintf (dump_file, "basic block after exit bb but before latch\n"); 453169689Skan return false; 454169689Skan } 455169689Skan else if (!empty_block_p (bb)) 456169689Skan { 457169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 458169689Skan fprintf (dump_file, "non empty basic block after exit bb\n"); 459169689Skan return false; 460169689Skan } 461169689Skan else if (bb == loop->latch 462169689Skan && bb != exit_bb 463169689Skan && !dominated_by_p (CDI_DOMINATORS, bb, exit_bb)) 464169689Skan { 465169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 466169689Skan fprintf (dump_file, "latch is not dominated by exit_block\n"); 467169689Skan return false; 468169689Skan } 469169689Skan } 470169689Skan 471169689Skan /* Be less adventurous and handle only normal edges. */ 472169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 473169689Skan if (e->flags & 474169689Skan (EDGE_ABNORMAL_CALL | EDGE_EH | EDGE_ABNORMAL | EDGE_IRREDUCIBLE_LOOP)) 475169689Skan { 476169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 477169689Skan fprintf (dump_file,"Difficult to handle edges\n"); 478169689Skan return false; 479169689Skan } 480169689Skan 481169689Skan return true; 482169689Skan} 483169689Skan 484169689Skan/* Return true, iff LOOP is if-convertible. 485169689Skan LOOP is if-convertible if, 486169689Skan - It is innermost. 487169689Skan - It has two or more basic blocks. 488169689Skan - It has only one exit. 489169689Skan - Loop header is not the exit edge. 490169689Skan - If its basic blocks and phi nodes are if convertible. See above for 491169689Skan more info. 492169689Skan FOR_VECTORIZER enables vectorizer specific checks. For example, support 493169689Skan for vector conditions, data dependency checks etc.. (Not implemented yet). */ 494169689Skan 495169689Skanstatic bool 496169689Skanif_convertible_loop_p (struct loop *loop, bool for_vectorizer ATTRIBUTE_UNUSED) 497169689Skan{ 498169689Skan tree phi; 499169689Skan basic_block bb; 500169689Skan block_stmt_iterator itr; 501169689Skan unsigned int i; 502169689Skan edge e; 503169689Skan edge_iterator ei; 504169689Skan basic_block exit_bb = NULL; 505169689Skan 506169689Skan /* Handle only inner most loop. */ 507169689Skan if (!loop || loop->inner) 508169689Skan { 509169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 510169689Skan fprintf (dump_file, "not inner most loop\n"); 511169689Skan return false; 512169689Skan } 513169689Skan 514169689Skan /* If only one block, no need for if-conversion. */ 515169689Skan if (loop->num_nodes <= 2) 516169689Skan { 517169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 518169689Skan fprintf (dump_file, "less than 2 basic blocks\n"); 519169689Skan return false; 520169689Skan } 521169689Skan 522169689Skan /* More than one loop exit is too much to handle. */ 523169689Skan if (!loop->single_exit) 524169689Skan { 525169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 526169689Skan fprintf (dump_file, "multiple exits\n"); 527169689Skan return false; 528169689Skan } 529169689Skan 530169689Skan /* ??? Check target's vector conditional operation support for vectorizer. */ 531169689Skan 532169689Skan /* If one of the loop header's edge is exit edge then do not apply 533169689Skan if-conversion. */ 534169689Skan FOR_EACH_EDGE (e, ei, loop->header->succs) 535169689Skan { 536169689Skan if (loop_exit_edge_p (loop, e)) 537169689Skan return false; 538169689Skan } 539169689Skan 540169689Skan calculate_dominance_info (CDI_DOMINATORS); 541169689Skan calculate_dominance_info (CDI_POST_DOMINATORS); 542169689Skan 543169689Skan /* Allow statements that can be handled during if-conversion. */ 544169689Skan ifc_bbs = get_loop_body_in_if_conv_order (loop); 545169689Skan if (!ifc_bbs) 546169689Skan { 547169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 548169689Skan fprintf (dump_file,"Irreducible loop\n"); 549169689Skan free_dominance_info (CDI_POST_DOMINATORS); 550169689Skan return false; 551169689Skan } 552169689Skan 553169689Skan for (i = 0; i < loop->num_nodes; i++) 554169689Skan { 555169689Skan bb = ifc_bbs[i]; 556169689Skan 557169689Skan if (!if_convertible_bb_p (loop, bb, exit_bb)) 558169689Skan return false; 559169689Skan 560169689Skan /* Check statements. */ 561169689Skan for (itr = bsi_start (bb); !bsi_end_p (itr); bsi_next (&itr)) 562169689Skan if (!if_convertible_stmt_p (loop, bb, bsi_stmt (itr))) 563169689Skan return false; 564169689Skan /* ??? Check data dependency for vectorizer. */ 565169689Skan 566169689Skan /* What about phi nodes ? */ 567171825Skan phi = phi_nodes (bb); 568171825Skan 569171825Skan /* Clear aux field of incoming edges to a bb with a phi node. */ 570171825Skan if (phi) 571171825Skan FOR_EACH_EDGE (e, ei, bb->preds) 572171825Skan e->aux = NULL; 573171825Skan 574171825Skan /* Check statements. */ 575171825Skan for (; phi; phi = PHI_CHAIN (phi)) 576169689Skan if (!if_convertible_phi_p (loop, bb, phi)) 577169689Skan return false; 578169689Skan 579169689Skan if (bb_with_exit_edge_p (loop, bb)) 580169689Skan exit_bb = bb; 581169689Skan } 582169689Skan 583169689Skan /* OK. Did not find any potential issues so go ahead in if-convert 584169689Skan this loop. Now there is no looking back. */ 585169689Skan if (dump_file) 586169689Skan fprintf (dump_file,"Applying if-conversion\n"); 587169689Skan 588169689Skan free_dominance_info (CDI_POST_DOMINATORS); 589169689Skan return true; 590169689Skan} 591169689Skan 592169689Skan/* Add condition COND into predicate list of basic block BB. */ 593169689Skan 594169689Skanstatic void 595169689Skanadd_to_predicate_list (basic_block bb, tree new_cond) 596169689Skan{ 597169689Skan tree cond = bb->aux; 598169689Skan 599169689Skan if (cond) 600169689Skan cond = fold_build2 (TRUTH_OR_EXPR, boolean_type_node, 601169689Skan unshare_expr (cond), new_cond); 602169689Skan else 603169689Skan cond = new_cond; 604169689Skan 605169689Skan bb->aux = cond; 606169689Skan} 607169689Skan 608169689Skan/* Add condition COND into BB's predicate list. PREV_COND is 609169689Skan existing condition. */ 610169689Skan 611169689Skanstatic tree 612171825Skanadd_to_dst_predicate_list (struct loop * loop, edge e, 613169689Skan tree prev_cond, tree cond, 614169689Skan block_stmt_iterator *bsi) 615169689Skan{ 616169689Skan tree new_cond = NULL_TREE; 617169689Skan 618171825Skan if (!flow_bb_inside_loop_p (loop, e->dest)) 619169689Skan return NULL_TREE; 620169689Skan 621169689Skan if (prev_cond == boolean_true_node || !prev_cond) 622169689Skan new_cond = unshare_expr (cond); 623169689Skan else 624169689Skan { 625169689Skan tree tmp; 626169689Skan tree tmp_stmt = NULL_TREE; 627169689Skan tree tmp_stmts1 = NULL_TREE; 628169689Skan tree tmp_stmts2 = NULL_TREE; 629169689Skan prev_cond = force_gimple_operand (unshare_expr (prev_cond), 630169689Skan &tmp_stmts1, true, NULL); 631169689Skan if (tmp_stmts1) 632169689Skan bsi_insert_before (bsi, tmp_stmts1, BSI_SAME_STMT); 633169689Skan 634169689Skan cond = force_gimple_operand (unshare_expr (cond), 635169689Skan &tmp_stmts2, true, NULL); 636169689Skan if (tmp_stmts2) 637169689Skan bsi_insert_before (bsi, tmp_stmts2, BSI_SAME_STMT); 638169689Skan 639171825Skan /* Add the condition to aux field of the edge. In case edge 640171825Skan destination is a PHI node, this condition will be ANDed with 641171825Skan block predicate to construct complete condition. */ 642171825Skan e->aux = cond; 643171825Skan 644169689Skan /* new_cond == prev_cond AND cond */ 645169689Skan tmp = build2 (TRUTH_AND_EXPR, boolean_type_node, 646169689Skan unshare_expr (prev_cond), cond); 647169689Skan tmp_stmt = ifc_temp_var (boolean_type_node, tmp); 648169689Skan bsi_insert_before (bsi, tmp_stmt, BSI_SAME_STMT); 649169689Skan new_cond = TREE_OPERAND (tmp_stmt, 0); 650169689Skan } 651171825Skan add_to_predicate_list (e->dest, new_cond); 652169689Skan return new_cond; 653169689Skan} 654169689Skan 655171825Skan/* During if-conversion aux field from basic block structure is used to hold 656171825Skan predicate list. Clean each basic block's predicate list for the given LOOP. 657171825Skan Also clean aux field of succesor edges, used to hold true and false 658171825Skan condition from conditional expression. */ 659169689Skan 660169689Skanstatic void 661169689Skanclean_predicate_lists (struct loop *loop) 662169689Skan{ 663169689Skan basic_block *bb; 664169689Skan unsigned int i; 665171825Skan edge e; 666171825Skan edge_iterator ei; 667171825Skan 668169689Skan bb = get_loop_body (loop); 669169689Skan for (i = 0; i < loop->num_nodes; i++) 670171825Skan { 671171825Skan bb[i]->aux = NULL; 672171825Skan FOR_EACH_EDGE (e, ei, bb[i]->succs) 673171825Skan e->aux = NULL; 674171825Skan } 675169689Skan free (bb); 676169689Skan} 677169689Skan 678169689Skan/* Basic block BB has two predecessors. Using predecessor's aux field, set 679169689Skan appropriate condition COND for the PHI node replacement. Return true block 680169689Skan whose phi arguments are selected when cond is true. */ 681169689Skan 682169689Skanstatic basic_block 683169689Skanfind_phi_replacement_condition (struct loop *loop, 684169689Skan basic_block bb, tree *cond, 685169689Skan block_stmt_iterator *bsi) 686169689Skan{ 687171825Skan edge first_edge, second_edge; 688169689Skan tree tmp_cond, new_stmts; 689169689Skan 690169689Skan gcc_assert (EDGE_COUNT (bb->preds) == 2); 691171825Skan first_edge = EDGE_PRED (bb, 0); 692171825Skan second_edge = EDGE_PRED (bb, 1); 693169689Skan 694169689Skan /* Use condition based on following criteria: 695169689Skan 1) 696169689Skan S1: x = !c ? a : b; 697169689Skan 698169689Skan S2: x = c ? b : a; 699169689Skan 700169689Skan S2 is preferred over S1. Make 'b' first_bb and use its condition. 701169689Skan 702169689Skan 2) Do not make loop header first_bb. 703169689Skan 704169689Skan 3) 705169689Skan S1: x = !(c == d)? a : b; 706169689Skan 707169689Skan S21: t1 = c == d; 708169689Skan S22: x = t1 ? b : a; 709169689Skan 710169689Skan S3: x = (c == d) ? b : a; 711169689Skan 712169689Skan S3 is preferred over S1 and S2*, Make 'b' first_bb and use 713171825Skan its condition. 714169689Skan 715169689Skan 4) If pred B is dominated by pred A then use pred B's condition. 716169689Skan See PR23115. */ 717169689Skan 718169689Skan /* Select condition that is not TRUTH_NOT_EXPR. */ 719171825Skan tmp_cond = (first_edge->src)->aux; 720169689Skan if (TREE_CODE (tmp_cond) == TRUTH_NOT_EXPR) 721169689Skan { 722171825Skan edge tmp_edge; 723171825Skan 724171825Skan tmp_edge = first_edge; 725171825Skan first_edge = second_edge; 726171825Skan second_edge = tmp_edge; 727169689Skan } 728169689Skan 729169689Skan /* Check if FIRST_BB is loop header or not and make sure that 730169689Skan FIRST_BB does not dominate SECOND_BB. */ 731171825Skan if (first_edge->src == loop->header 732171825Skan || dominated_by_p (CDI_DOMINATORS, 733171825Skan second_edge->src, first_edge->src)) 734169689Skan { 735171825Skan *cond = (second_edge->src)->aux; 736171825Skan 737171825Skan /* If there is a condition on an incoming edge, 738171825Skan AND it with the incoming bb predicate. */ 739171825Skan if (second_edge->aux) 740171825Skan *cond = build2 (TRUTH_AND_EXPR, boolean_type_node, 741171825Skan *cond, second_edge->aux); 742171825Skan 743171825Skan if (TREE_CODE (*cond) == TRUTH_NOT_EXPR) 744171825Skan /* We can be smart here and choose inverted 745171825Skan condition without switching bbs. */ 746220150Smm *cond = invert_truthvalue (*cond); 747169689Skan else 748171825Skan /* Select non loop header bb. */ 749171825Skan first_edge = second_edge; 750169689Skan } 751169689Skan else 752171825Skan { 753171825Skan /* FIRST_BB is not loop header */ 754171825Skan *cond = (first_edge->src)->aux; 755169689Skan 756171825Skan /* If there is a condition on an incoming edge, 757171825Skan AND it with the incoming bb predicate. */ 758171825Skan if (first_edge->aux) 759171825Skan *cond = build2 (TRUTH_AND_EXPR, boolean_type_node, 760171825Skan *cond, first_edge->aux); 761171825Skan } 762171825Skan 763169689Skan /* Create temp. for the condition. Vectorizer prefers to have gimple 764169689Skan value as condition. Various targets use different means to communicate 765220150Smm condition in vector compare operation. Using gimple value allows 766220150Smm compiler to emit vector compare and select RTL without exposing 767220150Smm compare's result. */ 768220150Smm *cond = force_gimple_operand (unshare_expr (*cond), &new_stmts, 769220150Smm false, NULL_TREE); 770169689Skan if (new_stmts) 771169689Skan bsi_insert_before (bsi, new_stmts, BSI_SAME_STMT); 772169689Skan if (!is_gimple_reg (*cond) && !is_gimple_condexpr (*cond)) 773169689Skan { 774169689Skan tree new_stmt; 775169689Skan 776169689Skan new_stmt = ifc_temp_var (TREE_TYPE (*cond), unshare_expr (*cond)); 777169689Skan bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT); 778169689Skan *cond = TREE_OPERAND (new_stmt, 0); 779169689Skan } 780169689Skan 781169689Skan gcc_assert (*cond); 782169689Skan 783171825Skan return first_edge->src; 784169689Skan} 785169689Skan 786169689Skan 787169689Skan/* Replace PHI node with conditional modify expr using COND. 788169689Skan This routine does not handle PHI nodes with more than two arguments. 789169689Skan For example, 790169689Skan S1: A = PHI <x1(1), x2(5) 791169689Skan is converted into, 792169689Skan S2: A = cond ? x1 : x2; 793169689Skan S2 is inserted at the top of basic block's statement list. 794169689Skan When COND is true, phi arg from TRUE_BB is selected. 795169689Skan*/ 796169689Skan 797169689Skanstatic void 798169689Skanreplace_phi_with_cond_modify_expr (tree phi, tree cond, basic_block true_bb, 799169689Skan block_stmt_iterator *bsi) 800169689Skan{ 801169689Skan tree new_stmt; 802169689Skan basic_block bb; 803169689Skan tree rhs; 804169689Skan tree arg_0, arg_1; 805169689Skan 806169689Skan gcc_assert (TREE_CODE (phi) == PHI_NODE); 807169689Skan 808169689Skan /* If this is not filtered earlier, then now it is too late. */ 809169689Skan gcc_assert (PHI_NUM_ARGS (phi) == 2); 810169689Skan 811169689Skan /* Find basic block and initialize iterator. */ 812169689Skan bb = bb_for_stmt (phi); 813169689Skan 814169689Skan /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr. */ 815169689Skan if (EDGE_PRED (bb, 1)->src == true_bb) 816169689Skan { 817169689Skan arg_0 = PHI_ARG_DEF (phi, 1); 818169689Skan arg_1 = PHI_ARG_DEF (phi, 0); 819169689Skan } 820169689Skan else 821169689Skan { 822169689Skan arg_0 = PHI_ARG_DEF (phi, 0); 823169689Skan arg_1 = PHI_ARG_DEF (phi, 1); 824169689Skan } 825169689Skan 826169689Skan /* Build new RHS using selected condition and arguments. */ 827169689Skan rhs = build3 (COND_EXPR, TREE_TYPE (PHI_RESULT (phi)), 828169689Skan unshare_expr (cond), unshare_expr (arg_0), 829169689Skan unshare_expr (arg_1)); 830169689Skan 831169689Skan /* Create new MODIFY expression using RHS. */ 832169689Skan new_stmt = build2 (MODIFY_EXPR, TREE_TYPE (PHI_RESULT (phi)), 833169689Skan unshare_expr (PHI_RESULT (phi)), rhs); 834169689Skan 835169689Skan /* Make new statement definition of the original phi result. */ 836169689Skan SSA_NAME_DEF_STMT (PHI_RESULT (phi)) = new_stmt; 837169689Skan 838169689Skan /* Insert using iterator. */ 839169689Skan bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT); 840169689Skan update_stmt (new_stmt); 841169689Skan 842169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 843169689Skan { 844169689Skan fprintf (dump_file, "new phi replacement stmt\n"); 845169689Skan print_generic_stmt (dump_file, new_stmt, TDF_SLIM); 846169689Skan } 847169689Skan} 848169689Skan 849169689Skan/* Process phi nodes for the given LOOP. Replace phi nodes with cond 850169689Skan modify expr. */ 851169689Skan 852169689Skanstatic void 853169689Skanprocess_phi_nodes (struct loop *loop) 854169689Skan{ 855169689Skan basic_block bb; 856169689Skan unsigned int orig_loop_num_nodes = loop->num_nodes; 857169689Skan unsigned int i; 858169689Skan 859169689Skan /* Replace phi nodes with cond. modify expr. */ 860169689Skan for (i = 1; i < orig_loop_num_nodes; i++) 861169689Skan { 862169689Skan tree phi, cond; 863169689Skan block_stmt_iterator bsi; 864169689Skan basic_block true_bb = NULL; 865169689Skan bb = ifc_bbs[i]; 866169689Skan 867169689Skan if (bb == loop->header) 868169689Skan continue; 869169689Skan 870169689Skan phi = phi_nodes (bb); 871169689Skan bsi = bsi_after_labels (bb); 872169689Skan 873169689Skan /* BB has two predecessors. Using predecessor's aux field, set 874169689Skan appropriate condition for the PHI node replacement. */ 875169689Skan if (phi) 876169689Skan true_bb = find_phi_replacement_condition (loop, bb, &cond, &bsi); 877169689Skan 878169689Skan while (phi) 879169689Skan { 880169689Skan tree next = PHI_CHAIN (phi); 881169689Skan replace_phi_with_cond_modify_expr (phi, cond, true_bb, &bsi); 882169689Skan release_phi_node (phi); 883169689Skan phi = next; 884169689Skan } 885169689Skan bb->phi_nodes = NULL; 886169689Skan } 887169689Skan return; 888169689Skan} 889169689Skan 890169689Skan/* Combine all basic block from the given LOOP into one or two super 891169689Skan basic block. Replace PHI nodes with conditional modify expression. */ 892169689Skan 893169689Skanstatic void 894169689Skancombine_blocks (struct loop *loop) 895169689Skan{ 896169689Skan basic_block bb, exit_bb, merge_target_bb; 897169689Skan unsigned int orig_loop_num_nodes = loop->num_nodes; 898169689Skan unsigned int i; 899169689Skan edge e; 900169689Skan edge_iterator ei; 901169689Skan 902169689Skan /* Process phi nodes to prepare blocks for merge. */ 903169689Skan process_phi_nodes (loop); 904169689Skan 905169689Skan /* Merge basic blocks. First remove all the edges in the loop, except 906169689Skan for those from the exit block. */ 907169689Skan exit_bb = NULL; 908169689Skan for (i = 0; i < orig_loop_num_nodes; i++) 909169689Skan { 910169689Skan bb = ifc_bbs[i]; 911169689Skan if (bb_with_exit_edge_p (loop, bb)) 912169689Skan { 913169689Skan exit_bb = bb; 914169689Skan break; 915169689Skan } 916169689Skan } 917169689Skan gcc_assert (exit_bb != loop->latch); 918169689Skan 919169689Skan for (i = 1; i < orig_loop_num_nodes; i++) 920169689Skan { 921169689Skan bb = ifc_bbs[i]; 922169689Skan 923169689Skan for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei));) 924169689Skan { 925169689Skan if (e->src == exit_bb) 926169689Skan ei_next (&ei); 927169689Skan else 928169689Skan remove_edge (e); 929169689Skan } 930169689Skan } 931169689Skan 932169689Skan if (exit_bb != NULL) 933169689Skan { 934169689Skan if (exit_bb != loop->header) 935169689Skan { 936169689Skan /* Connect this node with loop header. */ 937169689Skan make_edge (loop->header, exit_bb, EDGE_FALLTHRU); 938169689Skan set_immediate_dominator (CDI_DOMINATORS, exit_bb, loop->header); 939169689Skan } 940169689Skan 941169689Skan /* Redirect non-exit edges to loop->latch. */ 942169689Skan FOR_EACH_EDGE (e, ei, exit_bb->succs) 943169689Skan { 944169689Skan if (!loop_exit_edge_p (loop, e)) 945169689Skan redirect_edge_and_branch (e, loop->latch); 946169689Skan } 947169689Skan set_immediate_dominator (CDI_DOMINATORS, loop->latch, exit_bb); 948169689Skan } 949169689Skan else 950169689Skan { 951169689Skan /* If the loop does not have exit then reconnect header and latch. */ 952169689Skan make_edge (loop->header, loop->latch, EDGE_FALLTHRU); 953169689Skan set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header); 954169689Skan } 955169689Skan 956169689Skan merge_target_bb = loop->header; 957169689Skan for (i = 1; i < orig_loop_num_nodes; i++) 958169689Skan { 959169689Skan block_stmt_iterator bsi; 960169689Skan tree_stmt_iterator last; 961169689Skan 962169689Skan bb = ifc_bbs[i]; 963169689Skan 964169689Skan if (bb == exit_bb || bb == loop->latch) 965169689Skan continue; 966169689Skan 967169689Skan /* Remove labels and make stmts member of loop->header. */ 968169689Skan for (bsi = bsi_start (bb); !bsi_end_p (bsi); ) 969169689Skan { 970169689Skan if (TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR) 971169689Skan bsi_remove (&bsi, true); 972169689Skan else 973169689Skan { 974169689Skan set_bb_for_stmt (bsi_stmt (bsi), merge_target_bb); 975169689Skan bsi_next (&bsi); 976169689Skan } 977169689Skan } 978169689Skan 979169689Skan /* Update stmt list. */ 980169689Skan last = tsi_last (merge_target_bb->stmt_list); 981169689Skan tsi_link_after (&last, bb->stmt_list, TSI_NEW_STMT); 982169689Skan bb->stmt_list = NULL; 983169689Skan 984169689Skan /* Update dominator info. */ 985169689Skan if (dom_computed[CDI_DOMINATORS]) 986169689Skan delete_from_dominance_info (CDI_DOMINATORS, bb); 987169689Skan if (dom_computed[CDI_POST_DOMINATORS]) 988169689Skan delete_from_dominance_info (CDI_POST_DOMINATORS, bb); 989169689Skan 990169689Skan /* Remove basic block. */ 991169689Skan remove_bb_from_loops (bb); 992169689Skan expunge_block (bb); 993169689Skan } 994169689Skan 995169689Skan /* Now if possible, merge loop header and block with exit edge. 996169689Skan This reduces number of basic blocks to 2. Auto vectorizer addresses 997169689Skan loops with two nodes only. FIXME: Use cleanup_tree_cfg(). */ 998169689Skan if (exit_bb 999169689Skan && exit_bb != loop->header 1000169689Skan && can_merge_blocks_p (loop->header, exit_bb)) 1001169689Skan { 1002169689Skan remove_bb_from_loops (exit_bb); 1003169689Skan merge_blocks (loop->header, exit_bb); 1004169689Skan } 1005169689Skan} 1006169689Skan 1007169689Skan/* Make new temp variable of type TYPE. Add MODIFY_EXPR to assign EXP 1008169689Skan to the new variable. */ 1009169689Skan 1010169689Skanstatic tree 1011169689Skanifc_temp_var (tree type, tree exp) 1012169689Skan{ 1013169689Skan const char *name = "_ifc_"; 1014169689Skan tree var, stmt, new_name; 1015169689Skan 1016169689Skan if (is_gimple_reg (exp)) 1017169689Skan return exp; 1018169689Skan 1019169689Skan /* Create new temporary variable. */ 1020169689Skan var = create_tmp_var (type, name); 1021169689Skan add_referenced_var (var); 1022169689Skan 1023169689Skan /* Build new statement to assign EXP to new variable. */ 1024169689Skan stmt = build2 (MODIFY_EXPR, type, var, exp); 1025169689Skan 1026169689Skan /* Get SSA name for the new variable and set make new statement 1027169689Skan its definition statement. */ 1028169689Skan new_name = make_ssa_name (var, stmt); 1029169689Skan TREE_OPERAND (stmt, 0) = new_name; 1030169689Skan SSA_NAME_DEF_STMT (new_name) = stmt; 1031169689Skan 1032169689Skan return stmt; 1033169689Skan} 1034169689Skan 1035169689Skan 1036169689Skan/* Return TRUE iff, all pred blocks of BB are visited. 1037169689Skan Bitmap VISITED keeps history of visited blocks. */ 1038169689Skan 1039169689Skanstatic bool 1040169689Skanpred_blocks_visited_p (basic_block bb, bitmap *visited) 1041169689Skan{ 1042169689Skan edge e; 1043169689Skan edge_iterator ei; 1044169689Skan FOR_EACH_EDGE (e, ei, bb->preds) 1045169689Skan if (!bitmap_bit_p (*visited, e->src->index)) 1046169689Skan return false; 1047169689Skan 1048169689Skan return true; 1049169689Skan} 1050169689Skan 1051169689Skan/* Get body of a LOOP in suitable order for if-conversion. 1052169689Skan It is caller's responsibility to deallocate basic block 1053169689Skan list. If-conversion suitable order is, BFS order with one 1054169689Skan additional constraint. Select block in BFS block, if all 1055169689Skan pred are already selected. */ 1056169689Skan 1057169689Skanstatic basic_block * 1058169689Skanget_loop_body_in_if_conv_order (const struct loop *loop) 1059169689Skan{ 1060169689Skan basic_block *blocks, *blocks_in_bfs_order; 1061169689Skan basic_block bb; 1062169689Skan bitmap visited; 1063169689Skan unsigned int index = 0; 1064169689Skan unsigned int visited_count = 0; 1065169689Skan 1066169689Skan gcc_assert (loop->num_nodes); 1067169689Skan gcc_assert (loop->latch != EXIT_BLOCK_PTR); 1068169689Skan 1069169689Skan blocks = XCNEWVEC (basic_block, loop->num_nodes); 1070169689Skan visited = BITMAP_ALLOC (NULL); 1071169689Skan 1072169689Skan blocks_in_bfs_order = get_loop_body_in_bfs_order (loop); 1073169689Skan 1074169689Skan index = 0; 1075169689Skan while (index < loop->num_nodes) 1076169689Skan { 1077169689Skan bb = blocks_in_bfs_order [index]; 1078169689Skan 1079169689Skan if (bb->flags & BB_IRREDUCIBLE_LOOP) 1080169689Skan { 1081169689Skan free (blocks_in_bfs_order); 1082169689Skan BITMAP_FREE (visited); 1083169689Skan free (blocks); 1084169689Skan return NULL; 1085169689Skan } 1086169689Skan if (!bitmap_bit_p (visited, bb->index)) 1087169689Skan { 1088169689Skan if (pred_blocks_visited_p (bb, &visited) 1089169689Skan || bb == loop->header) 1090169689Skan { 1091169689Skan /* This block is now visited. */ 1092169689Skan bitmap_set_bit (visited, bb->index); 1093169689Skan blocks[visited_count++] = bb; 1094169689Skan } 1095169689Skan } 1096169689Skan index++; 1097169689Skan if (index == loop->num_nodes 1098169689Skan && visited_count != loop->num_nodes) 1099169689Skan { 1100169689Skan /* Not done yet. */ 1101169689Skan index = 0; 1102169689Skan } 1103169689Skan } 1104169689Skan free (blocks_in_bfs_order); 1105169689Skan BITMAP_FREE (visited); 1106169689Skan return blocks; 1107169689Skan} 1108169689Skan 1109169689Skan/* Return true if one of the basic block BB edge is exit of LOOP. */ 1110169689Skan 1111169689Skanstatic bool 1112169689Skanbb_with_exit_edge_p (struct loop *loop, basic_block bb) 1113169689Skan{ 1114169689Skan edge e; 1115169689Skan edge_iterator ei; 1116169689Skan bool exit_edge_found = false; 1117169689Skan 1118169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 1119169689Skan if (loop_exit_edge_p (loop, e)) 1120169689Skan { 1121169689Skan exit_edge_found = true; 1122169689Skan break; 1123169689Skan } 1124169689Skan 1125169689Skan return exit_edge_found; 1126169689Skan} 1127169689Skan 1128169689Skan/* Tree if-conversion pass management. */ 1129169689Skan 1130169689Skanstatic unsigned int 1131169689Skanmain_tree_if_conversion (void) 1132169689Skan{ 1133169689Skan unsigned i, loop_num; 1134169689Skan struct loop *loop; 1135169689Skan 1136169689Skan if (!current_loops) 1137169689Skan return 0; 1138169689Skan 1139169689Skan loop_num = current_loops->num; 1140169689Skan for (i = 0; i < loop_num; i++) 1141169689Skan { 1142169689Skan loop = current_loops->parray[i]; 1143169689Skan if (!loop) 1144169689Skan continue; 1145169689Skan 1146169689Skan tree_if_conversion (loop, true); 1147169689Skan } 1148169689Skan return 0; 1149169689Skan} 1150169689Skan 1151169689Skanstatic bool 1152169689Skangate_tree_if_conversion (void) 1153169689Skan{ 1154169689Skan return flag_tree_vectorize != 0; 1155169689Skan} 1156169689Skan 1157169689Skanstruct tree_opt_pass pass_if_conversion = 1158169689Skan{ 1159169689Skan "ifcvt", /* name */ 1160169689Skan gate_tree_if_conversion, /* gate */ 1161169689Skan main_tree_if_conversion, /* execute */ 1162169689Skan NULL, /* sub */ 1163169689Skan NULL, /* next */ 1164169689Skan 0, /* static_pass_number */ 1165169689Skan 0, /* tv_id */ 1166169689Skan PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */ 1167169689Skan 0, /* properties_provided */ 1168169689Skan 0, /* properties_destroyed */ 1169169689Skan 0, /* todo_flags_start */ 1170169689Skan TODO_dump_func | TODO_verify_loops | TODO_verify_stmts | TODO_verify_flow, 1171169689Skan /* todo_flags_finish */ 1172169689Skan 0 /* letter */ 1173169689Skan}; 1174