tree-if-conv.c revision 169689
1181111Sdes/* If-conversion for vectorizer. 2107553Sdes Copyright (C) 2004, 2005 Free Software Foundation, Inc. 399059Sdes Contributed by Devang Patel <dpatel@apple.com> 4157020Sdes 5157020SdesThis file is part of GCC. 6157020Sdes 7124244SdesGCC is free software; you can redistribute it and/or modify it under 8157020Sdesthe terms of the GNU General Public License as published by the Free 9157020SdesSoftware Foundation; either version 2, or (at your option) any later 1099059Sdesversion. 11181111Sdes 12181111SdesGCC is distributed in the hope that it will be useful, but WITHOUT ANY 13181111SdesWARRANTY; without even the implied warranty of MERCHANTABILITY or 14157020SdesFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15157020Sdesfor more details. 1699059Sdes 17157020SdesYou should have received a copy of the GNU General Public License 18157020Sdesalong with GCC; see the file COPYING. If not, write to the Free 1999059SdesSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 20157020Sdes02110-1301, USA. */ 21157020Sdes 22124244Sdes/* This pass implements tree level if-conversion transformation of loops. 23157020Sdes Initial goal is to help vectorizer vectorize loops with conditions. 24157020Sdes 25124244Sdes A short description of if-conversion: 26181111Sdes 27181111Sdes o Decide if a loop is if-convertible or not. 28181111Sdes o Walk all loop basic blocks in breadth first order (BFS order). 2999059Sdes o Remove conditional statements (at the end of basic block) 3099059Sdes and propagate condition into destination basic blocks' 3199059Sdes predicate list. 32157020Sdes o Replace modify expression with conditional modify expression 33157020Sdes using current basic block's condition. 3499059Sdes o Merge all basic blocks 35157020Sdes o Replace phi nodes with conditional modify expr 36157020Sdes o Merge all basic blocks into header 3799059Sdes 38157020Sdes Sample transformation: 39157020Sdes 40157020Sdes INPUT 4199059Sdes ----- 42181111Sdes 43181111Sdes # i_23 = PHI <0(0), i_18(10)>; 44181111Sdes <L0>:; 4599059Sdes j_15 = A[i_23]; 4699059Sdes if (j_15 > 41) goto <L1>; else goto <L17>; 4799059Sdes 48157020Sdes <L17>:; 49157020Sdes goto <bb 3> (<L3>); 5099059Sdes 51157020Sdes <L1>:; 52157020Sdes 5399059Sdes # iftmp.2_4 = PHI <0(8), 42(2)>; 54157020Sdes <L3>:; 55157020Sdes A[i_23] = iftmp.2_4; 5699059Sdes i_18 = i_23 + 1; 57157020Sdes if (i_18 <= 15) goto <L19>; else goto <L18>; 58157020Sdes 59124244Sdes <L19>:; 60157020Sdes goto <bb 1> (<L0>); 61157020Sdes 62128462Sdes <L18>:; 63157020Sdes 64157020Sdes OUTPUT 6599059Sdes ------ 66181111Sdes 67181111Sdes # i_23 = PHI <0(0), i_18(10)>; 68181111Sdes <L0>:; 69157020Sdes j_15 = A[i_23]; 70157020Sdes 7199059Sdes <L3>:; 72197679Sdes iftmp.2_4 = j_15 > 41 ? 42 : 0; 73197679Sdes A[i_23] = iftmp.2_4; 74197679Sdes i_18 = i_23 + 1; 75157020Sdes if (i_18 <= 15) goto <L19>; else goto <L18>; 76157020Sdes 7799059Sdes <L19>:; 78157020Sdes goto <bb 1> (<L0>); 79157020Sdes 8099059Sdes <L18>:; 81157020Sdes*/ 82157020Sdes 8399059Sdes#include "config.h" 84157020Sdes#include "system.h" 85157020Sdes#include "coretypes.h" 8699059Sdes#include "tm.h" 87157020Sdes#include "tree.h" 88202213Sed#include "c-common.h" 8999059Sdes#include "flags.h" 90157020Sdes#include "timevar.h" 91157020Sdes#include "varray.h" 9299059Sdes#include "rtl.h" 93157020Sdes#include "basic-block.h" 94202213Sed#include "diagnostic.h" 9599059Sdes#include "tree-flow.h" 96157020Sdes#include "tree-dump.h" 97157020Sdes#include "cfgloop.h" 9899059Sdes#include "tree-chrec.h" 99157020Sdes#include "tree-data-ref.h" 100157020Sdes#include "tree-scalar-evolution.h" 10199059Sdes#include "tree-pass.h" 10299059Sdes#include "target.h" 10399059Sdes 10499059Sdes/* local function prototypes */ 10599059Sdesstatic unsigned int main_tree_if_conversion (void); 10699059Sdesstatic tree tree_if_convert_stmt (struct loop *loop, tree, tree, 10799059Sdes block_stmt_iterator *); 10899059Sdesstatic void tree_if_convert_cond_expr (struct loop *, tree, tree, 10999059Sdes block_stmt_iterator *); 11099059Sdesstatic bool if_convertible_phi_p (struct loop *, basic_block, tree); 111157020Sdesstatic bool if_convertible_modify_expr_p (struct loop *, basic_block, tree); 112157020Sdesstatic bool if_convertible_stmt_p (struct loop *, basic_block, tree); 11399059Sdesstatic bool if_convertible_bb_p (struct loop *, basic_block, basic_block); 11499059Sdesstatic bool if_convertible_loop_p (struct loop *, bool); 115202213Sedstatic void add_to_predicate_list (basic_block, tree); 11699059Sdesstatic tree add_to_dst_predicate_list (struct loop * loop, basic_block, tree, tree, 11799059Sdes block_stmt_iterator *); 118202213Sedstatic void clean_predicate_lists (struct loop *loop); 11999059Sdesstatic basic_block find_phi_replacement_condition (struct loop *loop, 12099059Sdes basic_block, tree *, 121202213Sed block_stmt_iterator *); 12299059Sdesstatic void replace_phi_with_cond_modify_expr (tree, tree, basic_block, 12399059Sdes block_stmt_iterator *); 12499059Sdesstatic void process_phi_nodes (struct loop *); 12599059Sdesstatic void combine_blocks (struct loop *); 126204917Sdesstatic tree ifc_temp_var (tree, tree); 127207319Sdesstatic bool pred_blocks_visited_p (basic_block, bitmap *); 128204917Sdesstatic basic_block * get_loop_body_in_if_conv_order (const struct loop *loop); 129157020Sdesstatic bool bb_with_exit_edge_p (struct loop *, basic_block); 130157020Sdes 13199059Sdes/* List of basic blocks in if-conversion-suitable order. */ 132197679Sdesstatic basic_block *ifc_bbs; 133181111Sdes 134181111Sdes/* Main entry point. 135197679Sdes Apply if-conversion to the LOOP. Return true if successful otherwise return 136197679Sdes false. If false is returned then loop remains unchanged. 137197679Sdes FOR_VECTORIZER is a boolean flag. It indicates whether if-conversion is used 138157020Sdes for vectorizer or not. If it is used for vectorizer, additional checks are 139157020Sdes used. (Vectorization checks are not yet implemented). */ 14099059Sdes 141157020Sdesstatic bool 142157020Sdestree_if_conversion (struct loop *loop, bool for_vectorizer) 14399059Sdes{ 14499059Sdes basic_block bb; 145159458Sdes block_stmt_iterator itr; 14699059Sdes tree cond; 14799059Sdes unsigned int i; 148159458Sdes 14999059Sdes ifc_bbs = NULL; 150157020Sdes 151157020Sdes /* if-conversion is not appropriate for all loops. First, check if loop is 15299059Sdes if-convertible or not. */ 153157020Sdes if (!if_convertible_loop_p (loop, for_vectorizer)) 154157020Sdes { 155124244Sdes if (dump_file && (dump_flags & TDF_DETAILS)) 156157020Sdes fprintf (dump_file,"-------------------------\n"); 157157020Sdes if (ifc_bbs) 15899059Sdes { 159157020Sdes free (ifc_bbs); 160157020Sdes ifc_bbs = NULL; 16199059Sdes } 162157020Sdes free_dominance_info (CDI_POST_DOMINATORS); 163157020Sdes return false; 16499059Sdes } 165157020Sdes 166157020Sdes cond = NULL_TREE; 16799059Sdes 168157020Sdes /* Do actual work now. */ 169157020Sdes for (i = 0; i < loop->num_nodes; i++) 17099059Sdes { 171157020Sdes bb = ifc_bbs [i]; 172157020Sdes 17399059Sdes /* Update condition using predicate list. */ 174181111Sdes cond = bb->aux; 175181111Sdes 176181111Sdes /* Process all statements in this basic block. 177181111Sdes Remove conditional expression, if any, and annotate 178181111Sdes destination basic block(s) appropriately. */ 179181111Sdes for (itr = bsi_start (bb); !bsi_end_p (itr); /* empty */) 180157020Sdes { 181157020Sdes tree t = bsi_stmt (itr); 18299059Sdes cond = tree_if_convert_stmt (loop, t, cond, &itr); 183157020Sdes if (!bsi_end_p (itr)) 184157020Sdes bsi_next (&itr); 18599059Sdes } 186181111Sdes 187181111Sdes /* If current bb has only one successor, then consider it as an 188181111Sdes unconditional goto. */ 189149754Sdes if (single_succ_p (bb)) 190149754Sdes { 191149754Sdes basic_block bb_n = single_succ (bb); 192181111Sdes if (cond != NULL_TREE) 193181111Sdes add_to_predicate_list (bb_n, cond); 194181111Sdes cond = NULL_TREE; 195107553Sdes } 19699059Sdes } 19799059Sdes 198113912Sdes /* Now, all statements are if-converted and basic blocks are 199113912Sdes annotated appropriately. Combine all basic block into one huge 200113912Sdes basic block. */ 201157020Sdes combine_blocks (loop); 202157020Sdes 203157020Sdes /* clean up */ 204107553Sdes clean_predicate_lists (loop); 20599059Sdes free (ifc_bbs); 20699059Sdes ifc_bbs = NULL; 207107553Sdes 20899059Sdes return true; 20999059Sdes} 210147006Sdes 211147006Sdes/* if-convert stmt T which is part of LOOP. 212147006Sdes If T is a MODIFY_EXPR than it is converted into conditional modify 213107553Sdes expression using COND. For conditional expressions, add condition in the 21499059Sdes destination basic block's predicate list and remove conditional 21599059Sdes expression itself. BSI is the iterator used to traverse statements of 216107553Sdes loop. It is used here when it is required to delete current statement. */ 21799059Sdes 21899059Sdesstatic tree 219157020Sdestree_if_convert_stmt (struct loop * loop, tree t, tree cond, 220157020Sdes block_stmt_iterator *bsi) 221157020Sdes{ 222137019Sdes if (dump_file && (dump_flags & TDF_DETAILS)) 223194297Sjhb { 224137019Sdes fprintf (dump_file, "------if-convert stmt\n"); 225124244Sdes print_generic_stmt (dump_file, t, TDF_SLIM); 226147006Sdes print_generic_stmt (dump_file, cond, TDF_SLIM); 227124244Sdes } 228157020Sdes 229157020Sdes switch (TREE_CODE (t)) 230157020Sdes { 231162860Sdes /* Labels are harmless here. */ 232162860Sdes case LABEL_EXPR: 233162860Sdes break; 234107553Sdes 23599059Sdes case MODIFY_EXPR: 23699059Sdes /* This modify_expr is killing previous value of LHS. Appropriate value will 237157020Sdes be selected by PHI node based on condition. It is possible that before 238157020Sdes this transformation, PHI nodes was selecting default value and now it will 239157020Sdes use this new value. This is OK because it does not change validity the 240157020Sdes program. */ 241157020Sdes break; 242157020Sdes 243147006Sdes case COND_EXPR: 244147006Sdes /* Update destination blocks' predicate list and remove this 245147006Sdes condition expression. */ 246147006Sdes tree_if_convert_cond_expr (loop, t, cond, bsi); 247162860Sdes cond = NULL_TREE; 248162860Sdes break; 249162860Sdes 250162860Sdes default: 251137019Sdes gcc_unreachable (); 252137019Sdes } 253137019Sdes return cond; 254137019Sdes} 255147006Sdes 256147006Sdes/* STMT is COND_EXPR. Update two destination's predicate list. 257147006Sdes Remove COND_EXPR, if it is not the loop exit condition. Otherwise 258147006Sdes update loop exit condition appropriately. BSI is the iterator 259147006Sdes used to traverse statement list. STMT is part of loop LOOP. */ 260147006Sdes 261147006Sdesstatic void 262147006Sdestree_if_convert_cond_expr (struct loop *loop, tree stmt, tree cond, 263147006Sdes block_stmt_iterator *bsi) 264147006Sdes{ 265147006Sdes tree c, c2; 266147006Sdes edge true_edge, false_edge; 267181111Sdes 268181111Sdes gcc_assert (TREE_CODE (stmt) == COND_EXPR); 269181111Sdes 270181111Sdes c = COND_EXPR_COND (stmt); 271181111Sdes 272181111Sdes extract_true_false_edges_from_block (bb_for_stmt (stmt), 273181111Sdes &true_edge, &false_edge); 274181111Sdes 275162860Sdes /* Add new condition into destination's predicate list. */ 276162860Sdes 277162860Sdes /* If 'c' is true then TRUE_EDGE is taken. */ 278162860Sdes add_to_dst_predicate_list (loop, true_edge->dest, cond, 279147006Sdes unshare_expr (c), bsi); 280147006Sdes 281147006Sdes /* If 'c' is false then FALSE_EDGE is taken. */ 282147006Sdes c2 = invert_truthvalue (unshare_expr (c)); 283147006Sdes add_to_dst_predicate_list (loop, false_edge->dest, cond, c2, bsi); 284147006Sdes 285147006Sdes /* Now this conditional statement is redundant. Remove it. 286147006Sdes But, do not remove exit condition! Update exit condition 287162860Sdes using new condition. */ 288162860Sdes if (!bb_with_exit_edge_p (loop, bb_for_stmt (stmt))) 289162860Sdes { 290162860Sdes bsi_remove (bsi, true); 291162860Sdes cond = NULL_TREE; 292162860Sdes } 293162860Sdes return; 294162860Sdes} 295149754Sdes 296149754Sdes/* Return true, iff PHI is if-convertible. PHI is part of loop LOOP 297149754Sdes and it belongs to basic block BB. 298149754Sdes PHI is not if-convertible 299149754Sdes - if it has more than 2 arguments. 300149754Sdes - Virtual PHI is immediately used in another PHI node. */ 301149754Sdes 302149754Sdesstatic bool 303157020Sdesif_convertible_phi_p (struct loop *loop, basic_block bb, tree phi) 304192595Sdes{ 305157020Sdes if (dump_file && (dump_flags & TDF_DETAILS)) 306157020Sdes { 307157020Sdes fprintf (dump_file, "-------------------------\n"); 308157020Sdes print_generic_stmt (dump_file, phi, TDF_SLIM); 309137019Sdes } 310137019Sdes 311137019Sdes if (bb != loop->header && PHI_NUM_ARGS (phi) != 2) 312137019Sdes { 313137019Sdes if (dump_file && (dump_flags & TDF_DETAILS)) 314137019Sdes fprintf (dump_file, "More than two phi node args.\n"); 315107553Sdes return false; 31699059Sdes } 31799059Sdes 318107553Sdes if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi)))) 31999059Sdes { 32099059Sdes imm_use_iterator imm_iter; 321107553Sdes use_operand_p use_p; 32299319Sdes FOR_EACH_IMM_USE_FAST (use_p, imm_iter, PHI_RESULT (phi)) 32399059Sdes { 324107553Sdes if (TREE_CODE (USE_STMT (use_p)) == PHI_NODE) 325202213Sed { 32699059Sdes if (dump_file && (dump_flags & TDF_DETAILS)) 327157020Sdes fprintf (dump_file, "Difficult to handle this virtual phi.\n"); 328157020Sdes return false; 329157020Sdes } 330162860Sdes } 331162860Sdes } 332162860Sdes 333157020Sdes return true; 334157020Sdes} 335157020Sdes 336107553Sdes/* Return true, if M_EXPR is if-convertible. 33799059Sdes MODIFY_EXPR is not if-convertible if, 33899059Sdes - It is not movable. 339107553Sdes - It could trap. 34099059Sdes - LHS is not var decl. 34199059Sdes MODIFY_EXPR is part of block BB, which is inside loop LOOP. 342162860Sdes*/ 343162860Sdes 344162860Sdesstatic bool 345162860Sdesif_convertible_modify_expr_p (struct loop *loop, basic_block bb, tree m_expr) 346162860Sdes{ 347162860Sdes if (dump_file && (dump_flags & TDF_DETAILS)) 348124244Sdes { 349124244Sdes fprintf (dump_file, "-------------------------\n"); 350124244Sdes print_generic_stmt (dump_file, m_expr, TDF_SLIM); 351107553Sdes } 35299059Sdes 35399059Sdes /* Be conservative and do not handle immovable expressions. */ 354181111Sdes if (movement_possibility (m_expr) == MOVE_IMPOSSIBLE) 355181111Sdes { 356181111Sdes if (dump_file && (dump_flags & TDF_DETAILS)) 357107553Sdes fprintf (dump_file, "stmt is movable. Don't take risk\n"); 35899059Sdes return false; 35999059Sdes } 360181111Sdes 361181111Sdes /* See if it needs speculative loading or not. */ 362181111Sdes if (bb != loop->header 363181111Sdes && tree_could_trap_p (TREE_OPERAND (m_expr, 1))) 364181111Sdes { 365181111Sdes if (dump_file && (dump_flags & TDF_DETAILS)) 366181111Sdes fprintf (dump_file, "tree could trap...\n"); 367181111Sdes return false; 368181111Sdes } 369107553Sdes 37099059Sdes if (TREE_CODE (TREE_OPERAND (m_expr, 1)) == CALL_EXPR) 37199059Sdes { 372107553Sdes if (dump_file && (dump_flags & TDF_DETAILS)) 37399059Sdes fprintf (dump_file, "CALL_EXPR \n"); 37499059Sdes return false; 375107553Sdes } 37699059Sdes 37799059Sdes if (TREE_CODE (TREE_OPERAND (m_expr, 0)) != SSA_NAME 378147006Sdes && bb != loop->header 379147006Sdes && !bb_with_exit_edge_p (loop, bb)) 380147006Sdes { 381147006Sdes if (dump_file && (dump_flags & TDF_DETAILS)) 382147006Sdes { 383147006Sdes fprintf (dump_file, "LHS is not var\n"); 384107553Sdes print_generic_stmt (dump_file, m_expr, TDF_SLIM); 38599059Sdes } 38699059Sdes return false; 387107553Sdes } 38899059Sdes 38999059Sdes 390181111Sdes return true; 391181111Sdes} 392181111Sdes 393192595Sdes/* Return true, iff STMT is if-convertible. 394192595Sdes Statement is if-convertible if, 395192595Sdes - It is if-convertible MODIFY_EXPR 396107553Sdes - IT is LABEL_EXPR or COND_EXPR. 39799059Sdes STMT is inside block BB, which is inside loop LOOP. */ 39899059Sdes 399107553Sdesstatic bool 40099059Sdesif_convertible_stmt_p (struct loop *loop, basic_block bb, tree stmt) 40199059Sdes{ 402107553Sdes switch (TREE_CODE (stmt)) 40399059Sdes { 40499059Sdes case LABEL_EXPR: 405107553Sdes break; 406107553Sdes 40799059Sdes case MODIFY_EXPR: 408157020Sdes 409157020Sdes if (!if_convertible_modify_expr_p (loop, bb, stmt)) 410157020Sdes return false; 411157020Sdes break; 412157020Sdes 413157020Sdes case COND_EXPR: 414107553Sdes break; 415107553Sdes 416107553Sdes default: 417181111Sdes /* Don't know what to do with 'em so don't do anything. */ 418181111Sdes if (dump_file && (dump_flags & TDF_DETAILS)) 419181111Sdes { 420107553Sdes fprintf (dump_file, "don't know what to do\n"); 42199059Sdes print_generic_stmt (dump_file, stmt, TDF_SLIM); 42299059Sdes } 423107553Sdes return false; 42499059Sdes break; 42599059Sdes } 426157020Sdes 427157020Sdes return true; 428157020Sdes} 429107553Sdes 430124244Sdes/* Return true, iff BB is if-convertible. 43199059Sdes Note: This routine does _not_ check basic block statements and phis. 432162860Sdes Basic block is not if-convertible if, 433162860Sdes - Basic block is non-empty and it is after exit block (in BFS order). 434162860Sdes - Basic block is after exit block but before latch. 435107553Sdes - Basic block edge(s) is not normal. 43699059Sdes EXIT_BB_SEEN is true if basic block with exit edge is already seen. 43799059Sdes BB is inside loop LOOP. */ 438107553Sdes 43999059Sdesstatic bool 44099059Sdesif_convertible_bb_p (struct loop *loop, basic_block bb, basic_block exit_bb) 441107553Sdes{ 44299059Sdes edge e; 44399059Sdes edge_iterator ei; 444107553Sdes 44599059Sdes if (dump_file && (dump_flags & TDF_DETAILS)) 44699059Sdes fprintf (dump_file, "----------[%d]-------------\n", bb->index); 447107553Sdes 44899319Sdes if (exit_bb) 44999059Sdes { 450107553Sdes if (bb != loop->latch) 451202213Sed { 45299059Sdes if (dump_file && (dump_flags & TDF_DETAILS)) 453107553Sdes fprintf (dump_file, "basic block after exit bb but before latch\n"); 454202213Sed return false; 45599059Sdes } 456107553Sdes else if (!empty_block_p (bb)) 457202213Sed { 45899059Sdes if (dump_file && (dump_flags & TDF_DETAILS)) 459207319Sdes fprintf (dump_file, "non empty basic block after exit bb\n"); 460207319Sdes return false; 461207319Sdes } 462162860Sdes else if (bb == loop->latch 463162860Sdes && bb != exit_bb 464162860Sdes && !dominated_by_p (CDI_DOMINATORS, bb, exit_bb)) 465107553Sdes { 46699059Sdes if (dump_file && (dump_flags & TDF_DETAILS)) 46799059Sdes fprintf (dump_file, "latch is not dominated by exit_block\n"); 468107553Sdes return false; 46999059Sdes } 47099059Sdes } 471204917Sdes 472204917Sdes /* Be less adventurous and handle only normal edges. */ 473204917Sdes FOR_EACH_EDGE (e, ei, bb->succs) 474126279Sdes if (e->flags & 475126279Sdes (EDGE_ABNORMAL_CALL | EDGE_EH | EDGE_ABNORMAL | EDGE_IRREDUCIBLE_LOOP)) 476126279Sdes { 477126279Sdes if (dump_file && (dump_flags & TDF_DETAILS)) 478126279Sdes fprintf (dump_file,"Difficult to handle edges\n"); 479126279Sdes return false; 480126279Sdes } 481126279Sdes 482126279Sdes return true; 483126279Sdes} 484126279Sdes 485126279Sdes/* Return true, iff LOOP is if-convertible. 486124244Sdes LOOP is if-convertible if, 487147006Sdes - It is innermost. 488124244Sdes - It has two or more basic blocks. 489126279Sdes - It has only one exit. 490126279Sdes - Loop header is not the exit edge. 491126279Sdes - If its basic blocks and phi nodes are if convertible. See above for 492157020Sdes more info. 493157020Sdes FOR_VECTORIZER enables vectorizer specific checks. For example, support 494157020Sdes for vector conditions, data dependency checks etc.. (Not implemented yet). */ 495157020Sdes 496202213Sedstatic bool 497157020Sdesif_convertible_loop_p (struct loop *loop, bool for_vectorizer ATTRIBUTE_UNUSED) 498157020Sdes{ 499202213Sed tree phi; 500157020Sdes basic_block bb; 501149754Sdes block_stmt_iterator itr; 502149754Sdes unsigned int i; 503149754Sdes edge e; 504107553Sdes edge_iterator ei; 505107553Sdes basic_block exit_bb = NULL; 506107553Sdes 507157020Sdes /* Handle only inner most loop. */ 508157020Sdes if (!loop || loop->inner) 509157020Sdes { 510157020Sdes if (dump_file && (dump_flags & TDF_DETAILS)) 511202213Sed fprintf (dump_file, "not inner most loop\n"); 512157020Sdes return false; 513107553Sdes } 51499059Sdes 51599059Sdes /* If only one block, no need for if-conversion. */ 516107553Sdes if (loop->num_nodes <= 2) 51799059Sdes { 51899059Sdes if (dump_file && (dump_flags & TDF_DETAILS)) 519107553Sdes fprintf (dump_file, "less than 2 basic blocks\n"); 52099059Sdes return false; 52199059Sdes } 522107553Sdes 52399059Sdes /* More than one loop exit is too much to handle. */ 52499059Sdes if (!loop->single_exit) 525157020Sdes { 526157020Sdes if (dump_file && (dump_flags & TDF_DETAILS)) 527157020Sdes fprintf (dump_file, "multiple exits\n"); 528107553Sdes return false; 529162953Sdes } 53099059Sdes 531157020Sdes /* ??? Check target's vector conditional operation support for vectorizer. */ 532157020Sdes 533157020Sdes /* If one of the loop header's edge is exit edge then do not apply 534147006Sdes if-conversion. */ 535147006Sdes FOR_EACH_EDGE (e, ei, loop->header->succs) 536147006Sdes { 537197679Sdes if (loop_exit_edge_p (loop, e)) 538197679Sdes return false; 539197679Sdes } 540107553Sdes 54199059Sdes calculate_dominance_info (CDI_DOMINATORS); 54299059Sdes calculate_dominance_info (CDI_POST_DOMINATORS); 543147006Sdes 544147006Sdes /* Allow statements that can be handled during if-conversion. */ 545147006Sdes ifc_bbs = get_loop_body_in_if_conv_order (loop); 546107553Sdes if (!ifc_bbs) 547107553Sdes { 548107553Sdes if (dump_file && (dump_flags & TDF_DETAILS)) 549107553Sdes fprintf (dump_file,"Irreducible loop\n"); 55099059Sdes free_dominance_info (CDI_POST_DOMINATORS); 55199059Sdes return false; 552107553Sdes } 55399059Sdes 55499059Sdes for (i = 0; i < loop->num_nodes; i++) 555181111Sdes { 556149754Sdes bb = ifc_bbs[i]; 557149754Sdes 558207319Sdes if (!if_convertible_bb_p (loop, bb, exit_bb)) 559207319Sdes return false; 560207319Sdes 561107553Sdes /* Check statements. */ 56299059Sdes for (itr = bsi_start (bb); !bsi_end_p (itr); bsi_next (&itr)) 56399059Sdes if (!if_convertible_stmt_p (loop, bb, bsi_stmt (itr))) 564107553Sdes return false; 56599059Sdes /* ??? Check data dependency for vectorizer. */ 56699059Sdes 567107553Sdes /* What about phi nodes ? */ 56899059Sdes for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 56999059Sdes if (!if_convertible_phi_p (loop, bb, phi)) 570107553Sdes return false; 57199059Sdes 57299059Sdes if (bb_with_exit_edge_p (loop, bb)) 573107553Sdes exit_bb = bb; 574107553Sdes } 575107553Sdes 576107553Sdes /* OK. Did not find any potential issues so go ahead in if-convert 57799059Sdes this loop. Now there is no looking back. */ 57899059Sdes if (dump_file) 579107553Sdes fprintf (dump_file,"Applying if-conversion\n"); 58099059Sdes 58199059Sdes free_dominance_info (CDI_POST_DOMINATORS); 582157020Sdes return true; 583157020Sdes} 584157020Sdes 585157020Sdes/* Add condition COND into predicate list of basic block BB. */ 586202213Sed 587157020Sdesstatic void 588107553Sdesadd_to_predicate_list (basic_block bb, tree new_cond) 58999059Sdes{ 59099059Sdes tree cond = bb->aux; 591107553Sdes 59299059Sdes if (cond) 59399059Sdes cond = fold_build2 (TRUTH_OR_EXPR, boolean_type_node, 594107553Sdes unshare_expr (cond), new_cond); 59599059Sdes else 59699059Sdes cond = new_cond; 597107553Sdes 598202213Sed bb->aux = cond; 59999059Sdes} 600107553Sdes 601202213Sed/* Add condition COND into BB's predicate list. PREV_COND is 60299059Sdes existing condition. */ 603157020Sdes 604157020Sdesstatic tree 605157020Sdesadd_to_dst_predicate_list (struct loop * loop, basic_block bb, 606157020Sdes tree prev_cond, tree cond, 607157020Sdes block_stmt_iterator *bsi) 608157020Sdes{ 609107553Sdes tree new_cond = NULL_TREE; 61099059Sdes 61199059Sdes if (!flow_bb_inside_loop_p (loop, bb)) 612107553Sdes return NULL_TREE; 61399059Sdes 61499059Sdes if (prev_cond == boolean_true_node || !prev_cond) 615157020Sdes new_cond = unshare_expr (cond); 616157020Sdes else 617157020Sdes { 618107553Sdes tree tmp; 61999059Sdes tree tmp_stmt = NULL_TREE; 62099059Sdes tree tmp_stmts1 = NULL_TREE; 621107553Sdes tree tmp_stmts2 = NULL_TREE; 622162953Sdes prev_cond = force_gimple_operand (unshare_expr (prev_cond), 62399059Sdes &tmp_stmts1, true, NULL); 624107553Sdes if (tmp_stmts1) 62599059Sdes bsi_insert_before (bsi, tmp_stmts1, BSI_SAME_STMT); 62699059Sdes 627107553Sdes cond = force_gimple_operand (unshare_expr (cond), 62899059Sdes &tmp_stmts2, true, NULL); 62999059Sdes if (tmp_stmts2) 630157020Sdes bsi_insert_before (bsi, tmp_stmts2, BSI_SAME_STMT); 631157020Sdes 632157020Sdes /* new_cond == prev_cond AND cond */ 633157020Sdes tmp = build2 (TRUTH_AND_EXPR, boolean_type_node, 634157020Sdes unshare_expr (prev_cond), cond); 635157020Sdes tmp_stmt = ifc_temp_var (boolean_type_node, tmp); 636137019Sdes bsi_insert_before (bsi, tmp_stmt, BSI_SAME_STMT); 637137019Sdes new_cond = TREE_OPERAND (tmp_stmt, 0); 638137019Sdes } 639107553Sdes add_to_predicate_list (bb, new_cond); 64099059Sdes return new_cond; 64199059Sdes} 642107553Sdes 64399059Sdes/* During if-conversion aux field from basic block is used to hold predicate 64499059Sdes list. Clean each basic block's predicate list for the given LOOP. */ 645162860Sdes 646162860Sdesstatic void 64799059Sdesclean_predicate_lists (struct loop *loop) 648157020Sdes{ 649157020Sdes basic_block *bb; 650157020Sdes unsigned int i; 651107553Sdes bb = get_loop_body (loop); 65299059Sdes for (i = 0; i < loop->num_nodes; i++) 65399059Sdes bb[i]->aux = NULL; 654113912Sdes 655113912Sdes free (bb); 656113912Sdes} 657107553Sdes 65899059Sdes/* Basic block BB has two predecessors. Using predecessor's aux field, set 65999059Sdes appropriate condition COND for the PHI node replacement. Return true block 660157020Sdes whose phi arguments are selected when cond is true. */ 661157020Sdes 662157020Sdesstatic basic_block 663157020Sdesfind_phi_replacement_condition (struct loop *loop, 664124244Sdes basic_block bb, tree *cond, 665124244Sdes block_stmt_iterator *bsi) 666124244Sdes{ 667107553Sdes basic_block first_bb = NULL; 66899059Sdes basic_block second_bb = NULL; 66999059Sdes tree tmp_cond, new_stmts; 670157020Sdes 671157020Sdes gcc_assert (EDGE_COUNT (bb->preds) == 2); 672157020Sdes first_bb = (EDGE_PRED (bb, 0))->src; 673157020Sdes second_bb = (EDGE_PRED (bb, 1))->src; 674157020Sdes 675157020Sdes /* Use condition based on following criteria: 676107553Sdes 1) 67799059Sdes S1: x = !c ? a : b; 67899059Sdes 679126279Sdes S2: x = c ? b : a; 680126279Sdes 681126279Sdes S2 is preferred over S1. Make 'b' first_bb and use its condition. 682124244Sdes 683124244Sdes 2) Do not make loop header first_bb. 684124244Sdes 685107553Sdes 3) 68699059Sdes S1: x = !(c == d)? a : b; 68799059Sdes 688157020Sdes S21: t1 = c == d; 689157020Sdes S22: x = t1 ? b : a; 690157020Sdes 691157020Sdes S3: x = (c == d) ? b : a; 692157020Sdes 693157020Sdes S3 is preferred over S1 and S2*, Make 'b' first_bb and use 694181111Sdes its condition. 695181111Sdes 696181111Sdes 4) If pred B is dominated by pred A then use pred B's condition. 697181111Sdes See PR23115. */ 698181111Sdes 699181111Sdes /* Select condition that is not TRUTH_NOT_EXPR. */ 700128462Sdes tmp_cond = first_bb->aux; 701128462Sdes if (TREE_CODE (tmp_cond) == TRUTH_NOT_EXPR) 702128462Sdes { 703157020Sdes basic_block tmp_bb; 704157020Sdes tmp_bb = first_bb; 705157020Sdes first_bb = second_bb; 706113912Sdes second_bb = tmp_bb; 707113912Sdes } 708113912Sdes 709107553Sdes /* Check if FIRST_BB is loop header or not and make sure that 71099059Sdes FIRST_BB does not dominate SECOND_BB. */ 71199059Sdes if (first_bb == loop->header 712107553Sdes || dominated_by_p (CDI_DOMINATORS, second_bb, first_bb)) 71399319Sdes { 71499059Sdes tmp_cond = second_bb->aux; 715107553Sdes if (TREE_CODE (tmp_cond) == TRUTH_NOT_EXPR) 716202213Sed { 71799059Sdes /* Select non loop header condition but do not switch basic blocks. */ 718157020Sdes *cond = invert_truthvalue (unshare_expr (tmp_cond)); 719157020Sdes } 720157020Sdes else 721157020Sdes { 722157020Sdes /* Select non loop header condition. */ 723157020Sdes first_bb = second_bb; 724157020Sdes *cond = first_bb->aux; 725157020Sdes } 726157020Sdes } 727107553Sdes else 72899059Sdes /* FIRST_BB is not loop header */ 72999059Sdes *cond = first_bb->aux; 730107553Sdes 73199059Sdes /* Create temp. for the condition. Vectorizer prefers to have gimple 73299059Sdes value as condition. Various targets use different means to communicate 733107553Sdes condition in vector compare operation. Using gimple value allows compiler 73499059Sdes to emit vector compare and select RTL without exposing compare's result. */ 73599059Sdes *cond = force_gimple_operand (*cond, &new_stmts, false, NULL_TREE); 736107553Sdes if (new_stmts) 73799059Sdes bsi_insert_before (bsi, new_stmts, BSI_SAME_STMT); 73899059Sdes if (!is_gimple_reg (*cond) && !is_gimple_condexpr (*cond)) 739107553Sdes { 74099059Sdes tree new_stmt; 74199059Sdes 742107553Sdes new_stmt = ifc_temp_var (TREE_TYPE (*cond), unshare_expr (*cond)); 74399059Sdes bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT); 74499059Sdes *cond = TREE_OPERAND (new_stmt, 0); 745157020Sdes } 746157020Sdes 747157020Sdes gcc_assert (*cond); 748157020Sdes 749157020Sdes return first_bb; 750157020Sdes} 751107553Sdes 75299059Sdes 75399059Sdes/* Replace PHI node with conditional modify expr using COND. 754107553Sdes This routine does not handle PHI nodes with more than two arguments. 75599059Sdes For example, 75699059Sdes S1: A = PHI <x1(1), x2(5) 757124244Sdes is converted into, 758124244Sdes S2: A = cond ? x1 : x2; 759124244Sdes S2 is inserted at the top of basic block's statement list. 760107553Sdes When COND is true, phi arg from TRUE_BB is selected. 76199059Sdes*/ 76299059Sdes 763107553Sdesstatic void 76499059Sdesreplace_phi_with_cond_modify_expr (tree phi, tree cond, basic_block true_bb, 76599059Sdes block_stmt_iterator *bsi) 766107553Sdes{ 76799059Sdes tree new_stmt; 76899059Sdes basic_block bb; 769107553Sdes tree rhs; 77099059Sdes tree arg_0, arg_1; 77199059Sdes 772204917Sdes gcc_assert (TREE_CODE (phi) == PHI_NODE); 773204917Sdes 774204917Sdes /* If this is not filtered earlier, then now it is too late. */ 775107553Sdes gcc_assert (PHI_NUM_ARGS (phi) == 2); 77699059Sdes 77799059Sdes /* Find basic block and initialize iterator. */ 778107553Sdes bb = bb_for_stmt (phi); 77999059Sdes 78099059Sdes new_stmt = NULL_TREE; 781107553Sdes arg_0 = NULL_TREE; 78299059Sdes arg_1 = NULL_TREE; 78399059Sdes 784204917Sdes /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr. */ 785204917Sdes if (EDGE_PRED (bb, 1)->src == true_bb) 786204917Sdes { 787107553Sdes arg_0 = PHI_ARG_DEF (phi, 1); 78899059Sdes arg_1 = PHI_ARG_DEF (phi, 0); 78999059Sdes } 790107553Sdes else 79199059Sdes { 79299059Sdes arg_0 = PHI_ARG_DEF (phi, 0); 793124244Sdes arg_1 = PHI_ARG_DEF (phi, 1); 794124244Sdes } 795124244Sdes 796107553Sdes /* Build new RHS using selected condition and arguments. */ 79799059Sdes rhs = build3 (COND_EXPR, TREE_TYPE (PHI_RESULT (phi)), 79899059Sdes unshare_expr (cond), unshare_expr (arg_0), 799124244Sdes unshare_expr (arg_1)); 800124244Sdes 801124244Sdes /* Create new MODIFY expression using RHS. */ 802107553Sdes new_stmt = build2 (MODIFY_EXPR, TREE_TYPE (PHI_RESULT (phi)), 80399059Sdes unshare_expr (PHI_RESULT (phi)), rhs); 80499059Sdes 805107553Sdes /* Make new statement definition of the original phi result. */ 80699059Sdes SSA_NAME_DEF_STMT (PHI_RESULT (phi)) = new_stmt; 80799059Sdes 808107553Sdes /* Insert using iterator. */ 80999059Sdes bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT); 81099059Sdes update_stmt (new_stmt); 811107553Sdes 81299319Sdes if (dump_file && (dump_flags & TDF_DETAILS)) 81399059Sdes { 814207319Sdes fprintf (dump_file, "new phi replacement stmt\n"); 815207319Sdes print_generic_stmt (dump_file, new_stmt, TDF_SLIM); 816207319Sdes } 817107553Sdes} 818202213Sed 81999059Sdes/* Process phi nodes for the given LOOP. Replace phi nodes with cond 820107553Sdes modify expr. */ 82199059Sdes 82299059Sdesstatic void 823181111Sdesprocess_phi_nodes (struct loop *loop) 824181111Sdes{ 825181111Sdes basic_block bb; 826162860Sdes unsigned int orig_loop_num_nodes = loop->num_nodes; 827162860Sdes unsigned int i; 828162860Sdes 829162860Sdes /* Replace phi nodes with cond. modify expr. */ 830162860Sdes for (i = 1; i < orig_loop_num_nodes; i++) 831162860Sdes { 832107553Sdes tree phi, cond; 83399059Sdes block_stmt_iterator bsi; 83499059Sdes basic_block true_bb = NULL; 835107553Sdes bb = ifc_bbs[i]; 83699059Sdes 83799059Sdes if (bb == loop->header) 838107553Sdes continue; 83999059Sdes 84099059Sdes phi = phi_nodes (bb); 841107553Sdes bsi = bsi_after_labels (bb); 84299059Sdes 84399059Sdes /* BB has two predecessors. Using predecessor's aux field, set 844157020Sdes appropriate condition for the PHI node replacement. */ 845157020Sdes if (phi) 846157020Sdes true_bb = find_phi_replacement_condition (loop, bb, &cond, &bsi); 847107553Sdes 84899059Sdes while (phi) 84999059Sdes { 850107553Sdes tree next = PHI_CHAIN (phi); 85199059Sdes replace_phi_with_cond_modify_expr (phi, cond, true_bb, &bsi); 85299059Sdes release_phi_node (phi); 853147006Sdes phi = next; 854147006Sdes } 855147006Sdes bb->phi_nodes = NULL; 856157020Sdes } 857157020Sdes return; 858157020Sdes} 859157020Sdes 860157020Sdes/* Combine all basic block from the given LOOP into one or two super 861157020Sdes basic block. Replace PHI nodes with conditional modify expression. */ 862181111Sdes 863181111Sdesstatic void 864181111Sdescombine_blocks (struct loop *loop) 865181111Sdes{ 866181111Sdes basic_block bb, exit_bb, merge_target_bb; 867181111Sdes unsigned int orig_loop_num_nodes = loop->num_nodes; 868107553Sdes unsigned int i; 86999059Sdes edge e; 87099059Sdes edge_iterator ei; 871107553Sdes 87299059Sdes /* Process phi nodes to prepare blocks for merge. */ 87399059Sdes process_phi_nodes (loop); 874107553Sdes 875162953Sdes /* Merge basic blocks. First remove all the edges in the loop, except 87699059Sdes for those from the exit block. */ 877149754Sdes exit_bb = NULL; 878149754Sdes for (i = 0; i < orig_loop_num_nodes; i++) 879149754Sdes { 880107553Sdes bb = ifc_bbs[i]; 88199059Sdes if (bb_with_exit_edge_p (loop, bb)) 88299059Sdes { 883107553Sdes exit_bb = bb; 88499059Sdes break; 88599059Sdes } 886157020Sdes } 887157020Sdes gcc_assert (exit_bb != loop->latch); 888157020Sdes 889107553Sdes for (i = 1; i < orig_loop_num_nodes; i++) 89099059Sdes { 89199059Sdes bb = ifc_bbs[i]; 892107553Sdes 89399059Sdes for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei));) 89499059Sdes { 895107553Sdes if (e->src == exit_bb) 89699059Sdes ei_next (&ei); 89799059Sdes else 898107553Sdes remove_edge (e); 89999059Sdes } 90099059Sdes } 901107553Sdes 90299059Sdes if (exit_bb != NULL) 90399059Sdes { 904113912Sdes if (exit_bb != loop->header) 905113912Sdes { 906113912Sdes /* Connect this node with loop header. */ 907107553Sdes make_edge (loop->header, exit_bb, EDGE_FALLTHRU); 90899059Sdes set_immediate_dominator (CDI_DOMINATORS, exit_bb, loop->header); 90999059Sdes } 910149754Sdes 911149754Sdes /* Redirect non-exit edges to loop->latch. */ 912149754Sdes FOR_EACH_EDGE (e, ei, exit_bb->succs) 913149754Sdes { 914157020Sdes if (!loop_exit_edge_p (loop, e)) 915149754Sdes redirect_edge_and_branch (e, loop->latch); 916126279Sdes } 917126279Sdes set_immediate_dominator (CDI_DOMINATORS, loop->latch, exit_bb); 918126279Sdes } 919157020Sdes else 920157020Sdes { 921157020Sdes /* If the loop does not have exit then reconnect header and latch. */ 922157020Sdes make_edge (loop->header, loop->latch, EDGE_FALLTHRU); 923157020Sdes set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header); 924157020Sdes } 925157020Sdes 926157020Sdes merge_target_bb = loop->header; 927157020Sdes for (i = 1; i < orig_loop_num_nodes; i++) 928192595Sdes { 929192595Sdes block_stmt_iterator bsi; 930192595Sdes tree_stmt_iterator last; 931157020Sdes 932157020Sdes bb = ifc_bbs[i]; 933157020Sdes 934107553Sdes if (bb == exit_bb || bb == loop->latch) 93599059Sdes continue; 93699059Sdes 937113912Sdes /* Remove labels and make stmts member of loop->header. */ 938113912Sdes for (bsi = bsi_start (bb); !bsi_end_p (bsi); ) 939113912Sdes { 940157020Sdes if (TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR) 941157020Sdes bsi_remove (&bsi, true); 942157020Sdes else 943181111Sdes { 944181111Sdes set_bb_for_stmt (bsi_stmt (bsi), merge_target_bb); 945181111Sdes bsi_next (&bsi); 946107553Sdes } 94799059Sdes } 94899059Sdes 949157020Sdes /* Update stmt list. */ 950157020Sdes last = tsi_last (merge_target_bb->stmt_list); 951157020Sdes tsi_link_after (&last, bb->stmt_list, TSI_NEW_STMT); 952124244Sdes bb->stmt_list = NULL; 953124244Sdes 954124244Sdes /* Update dominator info. */ 955107553Sdes if (dom_computed[CDI_DOMINATORS]) 95699059Sdes delete_from_dominance_info (CDI_DOMINATORS, bb); 95799059Sdes if (dom_computed[CDI_POST_DOMINATORS]) 958107553Sdes delete_from_dominance_info (CDI_POST_DOMINATORS, bb); 95999059Sdes 96099059Sdes /* Remove basic block. */ 961107553Sdes remove_bb_from_loops (bb); 96299059Sdes expunge_block (bb); 96399059Sdes } 964137019Sdes 965137019Sdes /* Now if possible, merge loop header and block with exit edge. 966137019Sdes This reduces number of basic blocks to 2. Auto vectorizer addresses 967157020Sdes loops with two nodes only. FIXME: Use cleanup_tree_cfg(). */ 968157020Sdes if (exit_bb 969157020Sdes && exit_bb != loop->header 970107553Sdes && can_merge_blocks_p (loop->header, exit_bb)) 97199059Sdes { 97299059Sdes remove_bb_from_loops (exit_bb); 973181111Sdes merge_blocks (loop->header, exit_bb); 974181111Sdes } 975181111Sdes} 976137019Sdes 977137019Sdes/* Make new temp variable of type TYPE. Add MODIFY_EXPR to assign EXP 978137019Sdes to the new variable. */ 979157020Sdes 980157020Sdesstatic tree 981157020Sdesifc_temp_var (tree type, tree exp) 982181111Sdes{ 983181111Sdes const char *name = "_ifc_"; 984181111Sdes tree var, stmt, new_name; 985128462Sdes 986128462Sdes if (is_gimple_reg (exp)) 987128462Sdes return exp; 988113912Sdes 989113912Sdes /* Create new temporary variable. */ 990113912Sdes var = create_tmp_var (type, name); 991126279Sdes add_referenced_var (var); 992126279Sdes 993126279Sdes /* Build new statement to assign EXP to new variable. */ 994107553Sdes stmt = build2 (MODIFY_EXPR, type, var, exp); 99599059Sdes 99699059Sdes /* Get SSA name for the new variable and set make new statement 997181111Sdes its definition statement. */ 998181111Sdes new_name = make_ssa_name (var, stmt); 999181111Sdes TREE_OPERAND (stmt, 0) = new_name; 1000107553Sdes SSA_NAME_DEF_STMT (new_name) = stmt; 100199059Sdes 100299059Sdes return stmt; 1003126279Sdes} 1004126279Sdes 1005126279Sdes 1006107553Sdes/* Return TRUE iff, all pred blocks of BB are visited. 100799059Sdes Bitmap VISITED keeps history of visited blocks. */ 100899059Sdes 1009124244Sdesstatic bool 1010124244Sdespred_blocks_visited_p (basic_block bb, bitmap *visited) 1011124244Sdes{ 1012149754Sdes edge e; 1013149754Sdes edge_iterator ei; 1014149754Sdes FOR_EACH_EDGE (e, ei, bb->preds) 1015107553Sdes if (!bitmap_bit_p (*visited, e->src->index)) 101699059Sdes return false; 101799059Sdes 1018113912Sdes return true; 1019113912Sdes} 1020113912Sdes 1021107553Sdes/* Get body of a LOOP in suitable order for if-conversion. 102299059Sdes It is caller's responsibility to deallocate basic block 102399059Sdes list. If-conversion suitable order is, BFS order with one 1024107553Sdes additional constraint. Select block in BFS block, if all 1025162953Sdes pred are already selected. */ 102699059Sdes 1027107553Sdesstatic basic_block * 102899059Sdesget_loop_body_in_if_conv_order (const struct loop *loop) 102999059Sdes{ 1030107553Sdes basic_block *blocks, *blocks_in_bfs_order; 103199059Sdes basic_block bb; 103299059Sdes bitmap visited; 1033124244Sdes unsigned int index = 0; 1034124244Sdes unsigned int visited_count = 0; 1035124244Sdes 1036107553Sdes gcc_assert (loop->num_nodes); 103799059Sdes gcc_assert (loop->latch != EXIT_BLOCK_PTR); 103899059Sdes 1039107553Sdes blocks = XCNEWVEC (basic_block, loop->num_nodes); 104099059Sdes visited = BITMAP_ALLOC (NULL); 104199059Sdes 1042157020Sdes blocks_in_bfs_order = get_loop_body_in_bfs_order (loop); 1043202213Sed 1044157020Sdes index = 0; 1045157020Sdes while (index < loop->num_nodes) 1046157020Sdes { 1047157020Sdes bb = blocks_in_bfs_order [index]; 1048107553Sdes 1049107553Sdes if (bb->flags & BB_IRREDUCIBLE_LOOP) 1050107553Sdes { 1051107553Sdes free (blocks_in_bfs_order); 105299059Sdes BITMAP_FREE (visited); 105399059Sdes free (blocks); 1054107553Sdes return NULL; 105599059Sdes } 105699059Sdes if (!bitmap_bit_p (visited, bb->index)) 1057157020Sdes { 1058157020Sdes if (pred_blocks_visited_p (bb, &visited) 1059157020Sdes || bb == loop->header) 1060157020Sdes { 1061202213Sed /* This block is now visited. */ 1062157020Sdes bitmap_set_bit (visited, bb->index); 1063157020Sdes blocks[visited_count++] = bb; 1064157020Sdes } 1065157020Sdes } 1066157020Sdes index++; 1067202213Sed if (index == loop->num_nodes 1068157020Sdes && visited_count != loop->num_nodes) 1069181111Sdes { 1070181111Sdes /* Not done yet. */ 1071181111Sdes index = 0; 1072157020Sdes } 1073157020Sdes } 1074157020Sdes free (blocks_in_bfs_order); 1075107553Sdes BITMAP_FREE (visited); 107699059Sdes return blocks; 107799059Sdes} 1078128462Sdes 1079128462Sdes/* Return true if one of the basic block BB edge is exit of LOOP. */ 1080128462Sdes 1081157020Sdesstatic bool 1082157020Sdesbb_with_exit_edge_p (struct loop *loop, basic_block bb) 1083157020Sdes{ 1084107553Sdes edge e; 108599059Sdes edge_iterator ei; 108699059Sdes bool exit_edge_found = false; 1087126279Sdes 1088126279Sdes FOR_EACH_EDGE (e, ei, bb->succs) 1089126279Sdes if (loop_exit_edge_p (loop, e)) 1090107553Sdes { 109199059Sdes exit_edge_found = true; 109299059Sdes break; 1093204917Sdes } 1094204917Sdes 1095204917Sdes return exit_edge_found; 1096107553Sdes} 109799059Sdes 109899059Sdes/* Tree if-conversion pass management. */ 1099107553Sdes 110099059Sdesstatic unsigned int 110199059Sdesmain_tree_if_conversion (void) 1102107553Sdes{ 110399059Sdes unsigned i, loop_num; 110499059Sdes struct loop *loop; 1105107553Sdes 110699059Sdes if (!current_loops) 110799059Sdes return 0; 1108107553Sdes 110999059Sdes loop_num = current_loops->num; 111099059Sdes for (i = 0; i < loop_num; i++) 1111107553Sdes { 1112202213Sed loop = current_loops->parray[i]; 111399059Sdes if (!loop) 1114107553Sdes continue; 1115202213Sed 111699059Sdes tree_if_conversion (loop, true); 1117157020Sdes } 1118157020Sdes return 0; 1119157020Sdes} 1120157020Sdes 1121157020Sdesstatic bool 1122157020Sdesgate_tree_if_conversion (void) 1123157020Sdes{ 1124157020Sdes return flag_tree_vectorize != 0; 1125157020Sdes} 1126157020Sdes 1127157020Sdesstruct tree_opt_pass pass_if_conversion = 1128157020Sdes{ 1129157020Sdes "ifcvt", /* name */ 1130157020Sdes gate_tree_if_conversion, /* gate */ 1131157020Sdes main_tree_if_conversion, /* execute */ 1132157020Sdes NULL, /* sub */ 1133157020Sdes NULL, /* next */ 1134157020Sdes 0, /* static_pass_number */ 1135107553Sdes 0, /* tv_id */ 113699059Sdes PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */ 113799059Sdes 0, /* properties_provided */ 1138124244Sdes 0, /* properties_destroyed */ 1139124244Sdes 0, /* todo_flags_start */ 1140124244Sdes TODO_dump_func | TODO_verify_loops | TODO_verify_stmts | TODO_verify_flow, 1141107553Sdes /* todo_flags_finish */ 114299059Sdes 0 /* letter */ 114399059Sdes}; 1144107553Sdes