tree-if-conv.c revision 171825
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. */ 746171825Skan *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 765169689Skan condition in vector compare operation. Using gimple value allows compiler 766169689Skan to emit vector compare and select RTL without exposing compare's result. */ 767169689Skan *cond = force_gimple_operand (*cond, &new_stmts, false, NULL_TREE); 768169689Skan if (new_stmts) 769169689Skan bsi_insert_before (bsi, new_stmts, BSI_SAME_STMT); 770169689Skan if (!is_gimple_reg (*cond) && !is_gimple_condexpr (*cond)) 771169689Skan { 772169689Skan tree new_stmt; 773169689Skan 774169689Skan new_stmt = ifc_temp_var (TREE_TYPE (*cond), unshare_expr (*cond)); 775169689Skan bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT); 776169689Skan *cond = TREE_OPERAND (new_stmt, 0); 777169689Skan } 778169689Skan 779169689Skan gcc_assert (*cond); 780169689Skan 781171825Skan return first_edge->src; 782169689Skan} 783169689Skan 784169689Skan 785169689Skan/* Replace PHI node with conditional modify expr using COND. 786169689Skan This routine does not handle PHI nodes with more than two arguments. 787169689Skan For example, 788169689Skan S1: A = PHI <x1(1), x2(5) 789169689Skan is converted into, 790169689Skan S2: A = cond ? x1 : x2; 791169689Skan S2 is inserted at the top of basic block's statement list. 792169689Skan When COND is true, phi arg from TRUE_BB is selected. 793169689Skan*/ 794169689Skan 795169689Skanstatic void 796169689Skanreplace_phi_with_cond_modify_expr (tree phi, tree cond, basic_block true_bb, 797169689Skan block_stmt_iterator *bsi) 798169689Skan{ 799169689Skan tree new_stmt; 800169689Skan basic_block bb; 801169689Skan tree rhs; 802169689Skan tree arg_0, arg_1; 803169689Skan 804169689Skan gcc_assert (TREE_CODE (phi) == PHI_NODE); 805169689Skan 806169689Skan /* If this is not filtered earlier, then now it is too late. */ 807169689Skan gcc_assert (PHI_NUM_ARGS (phi) == 2); 808169689Skan 809169689Skan /* Find basic block and initialize iterator. */ 810169689Skan bb = bb_for_stmt (phi); 811169689Skan 812169689Skan /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr. */ 813169689Skan if (EDGE_PRED (bb, 1)->src == true_bb) 814169689Skan { 815169689Skan arg_0 = PHI_ARG_DEF (phi, 1); 816169689Skan arg_1 = PHI_ARG_DEF (phi, 0); 817169689Skan } 818169689Skan else 819169689Skan { 820169689Skan arg_0 = PHI_ARG_DEF (phi, 0); 821169689Skan arg_1 = PHI_ARG_DEF (phi, 1); 822169689Skan } 823169689Skan 824169689Skan /* Build new RHS using selected condition and arguments. */ 825169689Skan rhs = build3 (COND_EXPR, TREE_TYPE (PHI_RESULT (phi)), 826169689Skan unshare_expr (cond), unshare_expr (arg_0), 827169689Skan unshare_expr (arg_1)); 828169689Skan 829169689Skan /* Create new MODIFY expression using RHS. */ 830169689Skan new_stmt = build2 (MODIFY_EXPR, TREE_TYPE (PHI_RESULT (phi)), 831169689Skan unshare_expr (PHI_RESULT (phi)), rhs); 832169689Skan 833169689Skan /* Make new statement definition of the original phi result. */ 834169689Skan SSA_NAME_DEF_STMT (PHI_RESULT (phi)) = new_stmt; 835169689Skan 836169689Skan /* Insert using iterator. */ 837169689Skan bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT); 838169689Skan update_stmt (new_stmt); 839169689Skan 840169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 841169689Skan { 842169689Skan fprintf (dump_file, "new phi replacement stmt\n"); 843169689Skan print_generic_stmt (dump_file, new_stmt, TDF_SLIM); 844169689Skan } 845169689Skan} 846169689Skan 847169689Skan/* Process phi nodes for the given LOOP. Replace phi nodes with cond 848169689Skan modify expr. */ 849169689Skan 850169689Skanstatic void 851169689Skanprocess_phi_nodes (struct loop *loop) 852169689Skan{ 853169689Skan basic_block bb; 854169689Skan unsigned int orig_loop_num_nodes = loop->num_nodes; 855169689Skan unsigned int i; 856169689Skan 857169689Skan /* Replace phi nodes with cond. modify expr. */ 858169689Skan for (i = 1; i < orig_loop_num_nodes; i++) 859169689Skan { 860169689Skan tree phi, cond; 861169689Skan block_stmt_iterator bsi; 862169689Skan basic_block true_bb = NULL; 863169689Skan bb = ifc_bbs[i]; 864169689Skan 865169689Skan if (bb == loop->header) 866169689Skan continue; 867169689Skan 868169689Skan phi = phi_nodes (bb); 869169689Skan bsi = bsi_after_labels (bb); 870169689Skan 871169689Skan /* BB has two predecessors. Using predecessor's aux field, set 872169689Skan appropriate condition for the PHI node replacement. */ 873169689Skan if (phi) 874169689Skan true_bb = find_phi_replacement_condition (loop, bb, &cond, &bsi); 875169689Skan 876169689Skan while (phi) 877169689Skan { 878169689Skan tree next = PHI_CHAIN (phi); 879169689Skan replace_phi_with_cond_modify_expr (phi, cond, true_bb, &bsi); 880169689Skan release_phi_node (phi); 881169689Skan phi = next; 882169689Skan } 883169689Skan bb->phi_nodes = NULL; 884169689Skan } 885169689Skan return; 886169689Skan} 887169689Skan 888169689Skan/* Combine all basic block from the given LOOP into one or two super 889169689Skan basic block. Replace PHI nodes with conditional modify expression. */ 890169689Skan 891169689Skanstatic void 892169689Skancombine_blocks (struct loop *loop) 893169689Skan{ 894169689Skan basic_block bb, exit_bb, merge_target_bb; 895169689Skan unsigned int orig_loop_num_nodes = loop->num_nodes; 896169689Skan unsigned int i; 897169689Skan edge e; 898169689Skan edge_iterator ei; 899169689Skan 900169689Skan /* Process phi nodes to prepare blocks for merge. */ 901169689Skan process_phi_nodes (loop); 902169689Skan 903169689Skan /* Merge basic blocks. First remove all the edges in the loop, except 904169689Skan for those from the exit block. */ 905169689Skan exit_bb = NULL; 906169689Skan for (i = 0; i < orig_loop_num_nodes; i++) 907169689Skan { 908169689Skan bb = ifc_bbs[i]; 909169689Skan if (bb_with_exit_edge_p (loop, bb)) 910169689Skan { 911169689Skan exit_bb = bb; 912169689Skan break; 913169689Skan } 914169689Skan } 915169689Skan gcc_assert (exit_bb != loop->latch); 916169689Skan 917169689Skan for (i = 1; i < orig_loop_num_nodes; i++) 918169689Skan { 919169689Skan bb = ifc_bbs[i]; 920169689Skan 921169689Skan for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei));) 922169689Skan { 923169689Skan if (e->src == exit_bb) 924169689Skan ei_next (&ei); 925169689Skan else 926169689Skan remove_edge (e); 927169689Skan } 928169689Skan } 929169689Skan 930169689Skan if (exit_bb != NULL) 931169689Skan { 932169689Skan if (exit_bb != loop->header) 933169689Skan { 934169689Skan /* Connect this node with loop header. */ 935169689Skan make_edge (loop->header, exit_bb, EDGE_FALLTHRU); 936169689Skan set_immediate_dominator (CDI_DOMINATORS, exit_bb, loop->header); 937169689Skan } 938169689Skan 939169689Skan /* Redirect non-exit edges to loop->latch. */ 940169689Skan FOR_EACH_EDGE (e, ei, exit_bb->succs) 941169689Skan { 942169689Skan if (!loop_exit_edge_p (loop, e)) 943169689Skan redirect_edge_and_branch (e, loop->latch); 944169689Skan } 945169689Skan set_immediate_dominator (CDI_DOMINATORS, loop->latch, exit_bb); 946169689Skan } 947169689Skan else 948169689Skan { 949169689Skan /* If the loop does not have exit then reconnect header and latch. */ 950169689Skan make_edge (loop->header, loop->latch, EDGE_FALLTHRU); 951169689Skan set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header); 952169689Skan } 953169689Skan 954169689Skan merge_target_bb = loop->header; 955169689Skan for (i = 1; i < orig_loop_num_nodes; i++) 956169689Skan { 957169689Skan block_stmt_iterator bsi; 958169689Skan tree_stmt_iterator last; 959169689Skan 960169689Skan bb = ifc_bbs[i]; 961169689Skan 962169689Skan if (bb == exit_bb || bb == loop->latch) 963169689Skan continue; 964169689Skan 965169689Skan /* Remove labels and make stmts member of loop->header. */ 966169689Skan for (bsi = bsi_start (bb); !bsi_end_p (bsi); ) 967169689Skan { 968169689Skan if (TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR) 969169689Skan bsi_remove (&bsi, true); 970169689Skan else 971169689Skan { 972169689Skan set_bb_for_stmt (bsi_stmt (bsi), merge_target_bb); 973169689Skan bsi_next (&bsi); 974169689Skan } 975169689Skan } 976169689Skan 977169689Skan /* Update stmt list. */ 978169689Skan last = tsi_last (merge_target_bb->stmt_list); 979169689Skan tsi_link_after (&last, bb->stmt_list, TSI_NEW_STMT); 980169689Skan bb->stmt_list = NULL; 981169689Skan 982169689Skan /* Update dominator info. */ 983169689Skan if (dom_computed[CDI_DOMINATORS]) 984169689Skan delete_from_dominance_info (CDI_DOMINATORS, bb); 985169689Skan if (dom_computed[CDI_POST_DOMINATORS]) 986169689Skan delete_from_dominance_info (CDI_POST_DOMINATORS, bb); 987169689Skan 988169689Skan /* Remove basic block. */ 989169689Skan remove_bb_from_loops (bb); 990169689Skan expunge_block (bb); 991169689Skan } 992169689Skan 993169689Skan /* Now if possible, merge loop header and block with exit edge. 994169689Skan This reduces number of basic blocks to 2. Auto vectorizer addresses 995169689Skan loops with two nodes only. FIXME: Use cleanup_tree_cfg(). */ 996169689Skan if (exit_bb 997169689Skan && exit_bb != loop->header 998169689Skan && can_merge_blocks_p (loop->header, exit_bb)) 999169689Skan { 1000169689Skan remove_bb_from_loops (exit_bb); 1001169689Skan merge_blocks (loop->header, exit_bb); 1002169689Skan } 1003169689Skan} 1004169689Skan 1005169689Skan/* Make new temp variable of type TYPE. Add MODIFY_EXPR to assign EXP 1006169689Skan to the new variable. */ 1007169689Skan 1008169689Skanstatic tree 1009169689Skanifc_temp_var (tree type, tree exp) 1010169689Skan{ 1011169689Skan const char *name = "_ifc_"; 1012169689Skan tree var, stmt, new_name; 1013169689Skan 1014169689Skan if (is_gimple_reg (exp)) 1015169689Skan return exp; 1016169689Skan 1017169689Skan /* Create new temporary variable. */ 1018169689Skan var = create_tmp_var (type, name); 1019169689Skan add_referenced_var (var); 1020169689Skan 1021169689Skan /* Build new statement to assign EXP to new variable. */ 1022169689Skan stmt = build2 (MODIFY_EXPR, type, var, exp); 1023169689Skan 1024169689Skan /* Get SSA name for the new variable and set make new statement 1025169689Skan its definition statement. */ 1026169689Skan new_name = make_ssa_name (var, stmt); 1027169689Skan TREE_OPERAND (stmt, 0) = new_name; 1028169689Skan SSA_NAME_DEF_STMT (new_name) = stmt; 1029169689Skan 1030169689Skan return stmt; 1031169689Skan} 1032169689Skan 1033169689Skan 1034169689Skan/* Return TRUE iff, all pred blocks of BB are visited. 1035169689Skan Bitmap VISITED keeps history of visited blocks. */ 1036169689Skan 1037169689Skanstatic bool 1038169689Skanpred_blocks_visited_p (basic_block bb, bitmap *visited) 1039169689Skan{ 1040169689Skan edge e; 1041169689Skan edge_iterator ei; 1042169689Skan FOR_EACH_EDGE (e, ei, bb->preds) 1043169689Skan if (!bitmap_bit_p (*visited, e->src->index)) 1044169689Skan return false; 1045169689Skan 1046169689Skan return true; 1047169689Skan} 1048169689Skan 1049169689Skan/* Get body of a LOOP in suitable order for if-conversion. 1050169689Skan It is caller's responsibility to deallocate basic block 1051169689Skan list. If-conversion suitable order is, BFS order with one 1052169689Skan additional constraint. Select block in BFS block, if all 1053169689Skan pred are already selected. */ 1054169689Skan 1055169689Skanstatic basic_block * 1056169689Skanget_loop_body_in_if_conv_order (const struct loop *loop) 1057169689Skan{ 1058169689Skan basic_block *blocks, *blocks_in_bfs_order; 1059169689Skan basic_block bb; 1060169689Skan bitmap visited; 1061169689Skan unsigned int index = 0; 1062169689Skan unsigned int visited_count = 0; 1063169689Skan 1064169689Skan gcc_assert (loop->num_nodes); 1065169689Skan gcc_assert (loop->latch != EXIT_BLOCK_PTR); 1066169689Skan 1067169689Skan blocks = XCNEWVEC (basic_block, loop->num_nodes); 1068169689Skan visited = BITMAP_ALLOC (NULL); 1069169689Skan 1070169689Skan blocks_in_bfs_order = get_loop_body_in_bfs_order (loop); 1071169689Skan 1072169689Skan index = 0; 1073169689Skan while (index < loop->num_nodes) 1074169689Skan { 1075169689Skan bb = blocks_in_bfs_order [index]; 1076169689Skan 1077169689Skan if (bb->flags & BB_IRREDUCIBLE_LOOP) 1078169689Skan { 1079169689Skan free (blocks_in_bfs_order); 1080169689Skan BITMAP_FREE (visited); 1081169689Skan free (blocks); 1082169689Skan return NULL; 1083169689Skan } 1084169689Skan if (!bitmap_bit_p (visited, bb->index)) 1085169689Skan { 1086169689Skan if (pred_blocks_visited_p (bb, &visited) 1087169689Skan || bb == loop->header) 1088169689Skan { 1089169689Skan /* This block is now visited. */ 1090169689Skan bitmap_set_bit (visited, bb->index); 1091169689Skan blocks[visited_count++] = bb; 1092169689Skan } 1093169689Skan } 1094169689Skan index++; 1095169689Skan if (index == loop->num_nodes 1096169689Skan && visited_count != loop->num_nodes) 1097169689Skan { 1098169689Skan /* Not done yet. */ 1099169689Skan index = 0; 1100169689Skan } 1101169689Skan } 1102169689Skan free (blocks_in_bfs_order); 1103169689Skan BITMAP_FREE (visited); 1104169689Skan return blocks; 1105169689Skan} 1106169689Skan 1107169689Skan/* Return true if one of the basic block BB edge is exit of LOOP. */ 1108169689Skan 1109169689Skanstatic bool 1110169689Skanbb_with_exit_edge_p (struct loop *loop, basic_block bb) 1111169689Skan{ 1112169689Skan edge e; 1113169689Skan edge_iterator ei; 1114169689Skan bool exit_edge_found = false; 1115169689Skan 1116169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 1117169689Skan if (loop_exit_edge_p (loop, e)) 1118169689Skan { 1119169689Skan exit_edge_found = true; 1120169689Skan break; 1121169689Skan } 1122169689Skan 1123169689Skan return exit_edge_found; 1124169689Skan} 1125169689Skan 1126169689Skan/* Tree if-conversion pass management. */ 1127169689Skan 1128169689Skanstatic unsigned int 1129169689Skanmain_tree_if_conversion (void) 1130169689Skan{ 1131169689Skan unsigned i, loop_num; 1132169689Skan struct loop *loop; 1133169689Skan 1134169689Skan if (!current_loops) 1135169689Skan return 0; 1136169689Skan 1137169689Skan loop_num = current_loops->num; 1138169689Skan for (i = 0; i < loop_num; i++) 1139169689Skan { 1140169689Skan loop = current_loops->parray[i]; 1141169689Skan if (!loop) 1142169689Skan continue; 1143169689Skan 1144169689Skan tree_if_conversion (loop, true); 1145169689Skan } 1146169689Skan return 0; 1147169689Skan} 1148169689Skan 1149169689Skanstatic bool 1150169689Skangate_tree_if_conversion (void) 1151169689Skan{ 1152169689Skan return flag_tree_vectorize != 0; 1153169689Skan} 1154169689Skan 1155169689Skanstruct tree_opt_pass pass_if_conversion = 1156169689Skan{ 1157169689Skan "ifcvt", /* name */ 1158169689Skan gate_tree_if_conversion, /* gate */ 1159169689Skan main_tree_if_conversion, /* execute */ 1160169689Skan NULL, /* sub */ 1161169689Skan NULL, /* next */ 1162169689Skan 0, /* static_pass_number */ 1163169689Skan 0, /* tv_id */ 1164169689Skan PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */ 1165169689Skan 0, /* properties_provided */ 1166169689Skan 0, /* properties_destroyed */ 1167169689Skan 0, /* todo_flags_start */ 1168169689Skan TODO_dump_func | TODO_verify_loops | TODO_verify_stmts | TODO_verify_flow, 1169169689Skan /* todo_flags_finish */ 1170169689Skan 0 /* letter */ 1171169689Skan}; 1172