1/* If-conversion for vectorizer. 2 Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009 3 Free Software Foundation, Inc. 4 Contributed by Devang Patel <dpatel@apple.com> 5 6This file is part of GCC. 7 8GCC is free software; you can redistribute it and/or modify it under 9the terms of the GNU General Public License as published by the Free 10Software Foundation; either version 3, or (at your option) any later 11version. 12 13GCC is distributed in the hope that it will be useful, but WITHOUT ANY 14WARRANTY; without even the implied warranty of MERCHANTABILITY or 15FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 16for more details. 17 18You should have received a copy of the GNU General Public License 19along with GCC; see the file COPYING3. If not see 20<http://www.gnu.org/licenses/>. */ 21 22/* This pass implements tree level if-conversion transformation of loops. 23 Initial goal is to help vectorizer vectorize loops with conditions. 24 25 A short description of if-conversion: 26 27 o Decide if a loop is if-convertible or not. 28 o Walk all loop basic blocks in breadth first order (BFS order). 29 o Remove conditional statements (at the end of basic block) 30 and propagate condition into destination basic blocks' 31 predicate list. 32 o Replace modify expression with conditional modify expression 33 using current basic block's condition. 34 o Merge all basic blocks 35 o Replace phi nodes with conditional modify expr 36 o Merge all basic blocks into header 37 38 Sample transformation: 39 40 INPUT 41 ----- 42 43 # i_23 = PHI <0(0), i_18(10)>; 44 <L0>:; 45 j_15 = A[i_23]; 46 if (j_15 > 41) goto <L1>; else goto <L17>; 47 48 <L17>:; 49 goto <bb 3> (<L3>); 50 51 <L1>:; 52 53 # iftmp.2_4 = PHI <0(8), 42(2)>; 54 <L3>:; 55 A[i_23] = iftmp.2_4; 56 i_18 = i_23 + 1; 57 if (i_18 <= 15) goto <L19>; else goto <L18>; 58 59 <L19>:; 60 goto <bb 1> (<L0>); 61 62 <L18>:; 63 64 OUTPUT 65 ------ 66 67 # i_23 = PHI <0(0), i_18(10)>; 68 <L0>:; 69 j_15 = A[i_23]; 70 71 <L3>:; 72 iftmp.2_4 = j_15 > 41 ? 42 : 0; 73 A[i_23] = iftmp.2_4; 74 i_18 = i_23 + 1; 75 if (i_18 <= 15) goto <L19>; else goto <L18>; 76 77 <L19>:; 78 goto <bb 1> (<L0>); 79 80 <L18>:; 81*/ 82 83#include "config.h" 84#include "system.h" 85#include "coretypes.h" 86#include "tm.h" 87#include "tree.h" 88#include "flags.h" 89#include "timevar.h" 90#include "varray.h" 91#include "rtl.h" 92#include "basic-block.h" 93#include "diagnostic.h" 94#include "tree-flow.h" 95#include "tree-dump.h" 96#include "cfgloop.h" 97#include "tree-chrec.h" 98#include "tree-data-ref.h" 99#include "tree-scalar-evolution.h" 100#include "tree-pass.h" 101#include "target.h" 102 103 104/* local function prototypes */ 105static unsigned int main_tree_if_conversion (void); 106static tree tree_if_convert_stmt (struct loop *loop, gimple, tree, 107 gimple_stmt_iterator *); 108static void tree_if_convert_cond_stmt (struct loop *, gimple, tree, 109 gimple_stmt_iterator *); 110static bool if_convertible_phi_p (struct loop *, basic_block, gimple); 111static bool if_convertible_gimple_assign_stmt_p (struct loop *, basic_block, 112 gimple); 113static bool if_convertible_stmt_p (struct loop *, basic_block, gimple); 114static bool if_convertible_bb_p (struct loop *, basic_block, basic_block); 115static bool if_convertible_loop_p (struct loop *, bool); 116static void add_to_predicate_list (basic_block, tree); 117static tree add_to_dst_predicate_list (struct loop * loop, edge, 118 tree, tree, 119 gimple_stmt_iterator *); 120static void clean_predicate_lists (struct loop *loop); 121static basic_block find_phi_replacement_condition (struct loop *loop, 122 basic_block, tree *, 123 gimple_stmt_iterator *); 124static void replace_phi_with_cond_gimple_assign_stmt (gimple, tree, 125 basic_block, 126 gimple_stmt_iterator *); 127static void process_phi_nodes (struct loop *); 128static void combine_blocks (struct loop *); 129static gimple ifc_temp_var (tree, tree); 130static bool pred_blocks_visited_p (basic_block, bitmap *); 131static basic_block * get_loop_body_in_if_conv_order (const struct loop *loop); 132static bool bb_with_exit_edge_p (struct loop *, basic_block); 133 134/* List of basic blocks in if-conversion-suitable order. */ 135static basic_block *ifc_bbs; 136 137/* Main entry point. 138 Apply if-conversion to the LOOP. Return true if successful otherwise return 139 false. If false is returned then loop remains unchanged. 140 FOR_VECTORIZER is a boolean flag. It indicates whether if-conversion is used 141 for vectorizer or not. If it is used for vectorizer, additional checks are 142 used. (Vectorization checks are not yet implemented). */ 143 144static bool 145tree_if_conversion (struct loop *loop, bool for_vectorizer) 146{ 147 basic_block bb; 148 gimple_stmt_iterator itr; 149 unsigned int i; 150 151 ifc_bbs = NULL; 152 153 /* if-conversion is not appropriate for all loops. First, check if loop is 154 if-convertible or not. */ 155 if (!if_convertible_loop_p (loop, for_vectorizer)) 156 { 157 if (dump_file && (dump_flags & TDF_DETAILS)) 158 fprintf (dump_file,"-------------------------\n"); 159 if (ifc_bbs) 160 { 161 free (ifc_bbs); 162 ifc_bbs = NULL; 163 } 164 free_dominance_info (CDI_POST_DOMINATORS); 165 return false; 166 } 167 168 /* Do actual work now. */ 169 for (i = 0; i < loop->num_nodes; i++) 170 { 171 tree cond; 172 173 bb = ifc_bbs [i]; 174 175 /* Update condition using predicate list. */ 176 cond = (tree) bb->aux; 177 178 /* Process all statements in this basic block. 179 Remove conditional expression, if any, and annotate 180 destination basic block(s) appropriately. */ 181 for (itr = gsi_start_bb (bb); !gsi_end_p (itr); /* empty */) 182 { 183 gimple t = gsi_stmt (itr); 184 cond = tree_if_convert_stmt (loop, t, cond, &itr); 185 if (!gsi_end_p (itr)) 186 gsi_next (&itr); 187 } 188 189 /* If current bb has only one successor, then consider it as an 190 unconditional goto. */ 191 if (single_succ_p (bb)) 192 { 193 basic_block bb_n = single_succ (bb); 194 195 /* Successor bb inherits predicate of its predecessor. If there 196 is no predicate in predecessor bb, then consider successor bb 197 as always executed. */ 198 if (cond == NULL_TREE) 199 cond = boolean_true_node; 200 201 add_to_predicate_list (bb_n, cond); 202 } 203 } 204 205 /* Now, all statements are if-converted and basic blocks are 206 annotated appropriately. Combine all basic block into one huge 207 basic block. */ 208 combine_blocks (loop); 209 210 /* clean up */ 211 clean_predicate_lists (loop); 212 free (ifc_bbs); 213 ifc_bbs = NULL; 214 215 return true; 216} 217 218/* if-convert stmt T which is part of LOOP. 219 If T is a GIMPLE_ASSIGN then it is converted into conditional modify 220 expression using COND. For conditional expressions, add condition in the 221 destination basic block's predicate list and remove conditional 222 expression itself. BSI is the iterator used to traverse statements of 223 loop. It is used here when it is required to delete current statement. */ 224 225static tree 226tree_if_convert_stmt (struct loop * loop, gimple t, tree cond, 227 gimple_stmt_iterator *gsi) 228{ 229 if (dump_file && (dump_flags & TDF_DETAILS)) 230 { 231 fprintf (dump_file, "------if-convert stmt\n"); 232 print_gimple_stmt (dump_file, t, 0, TDF_SLIM); 233 print_generic_stmt (dump_file, cond, TDF_SLIM); 234 } 235 236 switch (gimple_code (t)) 237 { 238 /* Labels are harmless here. */ 239 case GIMPLE_LABEL: 240 break; 241 242 case GIMPLE_DEBUG: 243 /* ??? Should there be conditional GIMPLE_DEBUG_BINDs? */ 244 if (gimple_debug_bind_p (gsi_stmt (*gsi))) 245 { 246 gimple_debug_bind_reset_value (gsi_stmt (*gsi)); 247 update_stmt (gsi_stmt (*gsi)); 248 } 249 break; 250 251 case GIMPLE_ASSIGN: 252 /* This GIMPLE_ASSIGN is killing previous value of LHS. Appropriate 253 value will be selected by PHI node based on condition. It is possible 254 that before this transformation, PHI nodes was selecting default 255 value and now it will use this new value. This is OK because it does 256 not change validity the program. */ 257 break; 258 259 case GIMPLE_COND: 260 /* Update destination blocks' predicate list and remove this 261 condition expression. */ 262 tree_if_convert_cond_stmt (loop, t, cond, gsi); 263 cond = NULL_TREE; 264 break; 265 266 default: 267 gcc_unreachable (); 268 } 269 return cond; 270} 271 272/* STMT is a GIMPLE_COND. Update two destination's predicate list. 273 Remove COND_EXPR, if it is not the loop exit condition. Otherwise 274 update loop exit condition appropriately. GSI is the iterator 275 used to traverse statement list. STMT is part of loop LOOP. */ 276 277static void 278tree_if_convert_cond_stmt (struct loop *loop, gimple stmt, tree cond, 279 gimple_stmt_iterator *gsi) 280{ 281 tree c, c2; 282 edge true_edge, false_edge; 283 location_t loc = gimple_location (stmt); 284 285 gcc_assert (gimple_code (stmt) == GIMPLE_COND); 286 287 c = fold_build2_loc (loc, gimple_cond_code (stmt), boolean_type_node, 288 gimple_cond_lhs (stmt), gimple_cond_rhs (stmt)); 289 290 extract_true_false_edges_from_block (gimple_bb (stmt), 291 &true_edge, &false_edge); 292 293 /* Add new condition into destination's predicate list. */ 294 295 /* If C is true then TRUE_EDGE is taken. */ 296 add_to_dst_predicate_list (loop, true_edge, cond, c, gsi); 297 298 /* If 'c' is false then FALSE_EDGE is taken. */ 299 c2 = invert_truthvalue_loc (loc, unshare_expr (c)); 300 add_to_dst_predicate_list (loop, false_edge, cond, c2, gsi); 301 302 /* Now this conditional statement is redundant. Remove it. 303 But, do not remove exit condition! Update exit condition 304 using new condition. */ 305 if (!bb_with_exit_edge_p (loop, gimple_bb (stmt))) 306 { 307 gsi_remove (gsi, true); 308 cond = NULL_TREE; 309 } 310 return; 311} 312 313/* Return true, iff PHI is if-convertible. PHI is part of loop LOOP 314 and it belongs to basic block BB. 315 PHI is not if-convertible 316 - if it has more than 2 arguments. 317 - Virtual PHI is immediately used in another PHI node. 318 - Virtual PHI on BB other than header. */ 319 320static bool 321if_convertible_phi_p (struct loop *loop, basic_block bb, gimple phi) 322{ 323 if (dump_file && (dump_flags & TDF_DETAILS)) 324 { 325 fprintf (dump_file, "-------------------------\n"); 326 print_gimple_stmt (dump_file, phi, 0, TDF_SLIM); 327 } 328 329 if (bb != loop->header && gimple_phi_num_args (phi) != 2) 330 { 331 if (dump_file && (dump_flags & TDF_DETAILS)) 332 fprintf (dump_file, "More than two phi node args.\n"); 333 return false; 334 } 335 336 if (!is_gimple_reg (SSA_NAME_VAR (gimple_phi_result (phi)))) 337 { 338 imm_use_iterator imm_iter; 339 use_operand_p use_p; 340 341 if (bb != loop->header) 342 { 343 if (dump_file && (dump_flags & TDF_DETAILS)) 344 fprintf (dump_file, "Virtual phi not on loop header.\n"); 345 return false; 346 } 347 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, gimple_phi_result (phi)) 348 { 349 if (gimple_code (USE_STMT (use_p)) == GIMPLE_PHI) 350 { 351 if (dump_file && (dump_flags & TDF_DETAILS)) 352 fprintf (dump_file, "Difficult to handle this virtual phi.\n"); 353 return false; 354 } 355 } 356 } 357 358 return true; 359} 360 361/* Return true, if STMT is if-convertible. 362 GIMPLE_ASSIGN statement is not if-convertible if, 363 - It is not movable. 364 - It could trap. 365 - LHS is not var decl. 366 GIMPLE_ASSIGN is part of block BB, which is inside loop LOOP. */ 367 368static bool 369if_convertible_gimple_assign_stmt_p (struct loop *loop, basic_block bb, 370 gimple stmt) 371{ 372 tree lhs; 373 374 if (!is_gimple_assign (stmt)) 375 return false; 376 377 if (dump_file && (dump_flags & TDF_DETAILS)) 378 { 379 fprintf (dump_file, "-------------------------\n"); 380 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 381 } 382 383 lhs = gimple_assign_lhs (stmt); 384 385 /* Some of these constrains might be too conservative. */ 386 if (stmt_ends_bb_p (stmt) 387 || gimple_has_volatile_ops (stmt) 388 || (TREE_CODE (lhs) == SSA_NAME 389 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs)) 390 || gimple_has_side_effects (stmt)) 391 { 392 if (dump_file && (dump_flags & TDF_DETAILS)) 393 fprintf (dump_file, "stmt not suitable for ifcvt\n"); 394 return false; 395 } 396 397 /* See if it needs speculative loading or not. */ 398 if (bb != loop->header 399 && gimple_assign_rhs_could_trap_p (stmt)) 400 { 401 if (dump_file && (dump_flags & TDF_DETAILS)) 402 fprintf (dump_file, "tree could trap...\n"); 403 return false; 404 } 405 406 if (TREE_CODE (lhs) != SSA_NAME 407 && bb != loop->header 408 && !bb_with_exit_edge_p (loop, bb)) 409 { 410 if (dump_file && (dump_flags & TDF_DETAILS)) 411 { 412 fprintf (dump_file, "LHS is not var\n"); 413 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 414 } 415 return false; 416 } 417 418 return true; 419} 420 421/* Return true, iff STMT is if-convertible. 422 Statement is if-convertible if, 423 - It is if-convertible GIMPLE_ASSGIN 424 - It is GIMPLE_LABEL or GIMPLE_COND. 425 STMT is inside block BB, which is inside loop LOOP. */ 426 427static bool 428if_convertible_stmt_p (struct loop *loop, basic_block bb, gimple stmt) 429{ 430 switch (gimple_code (stmt)) 431 { 432 case GIMPLE_LABEL: 433 break; 434 435 case GIMPLE_DEBUG: 436 break; 437 438 case GIMPLE_ASSIGN: 439 if (!if_convertible_gimple_assign_stmt_p (loop, bb, stmt)) 440 return false; 441 break; 442 443 case GIMPLE_COND: 444 break; 445 446 default: 447 /* Don't know what to do with 'em so don't do anything. */ 448 if (dump_file && (dump_flags & TDF_DETAILS)) 449 { 450 fprintf (dump_file, "don't know what to do\n"); 451 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 452 } 453 return false; 454 break; 455 } 456 457 return true; 458} 459 460/* Return true, iff BB is if-convertible. 461 Note: This routine does _not_ check basic block statements and phis. 462 Basic block is not if-convertible if, 463 - Basic block is non-empty and it is after exit block (in BFS order). 464 - Basic block is after exit block but before latch. 465 - Basic block edge(s) is not normal. 466 EXIT_BB_SEEN is true if basic block with exit edge is already seen. 467 BB is inside loop LOOP. */ 468 469static bool 470if_convertible_bb_p (struct loop *loop, basic_block bb, basic_block exit_bb) 471{ 472 edge e; 473 edge_iterator ei; 474 475 if (dump_file && (dump_flags & TDF_DETAILS)) 476 fprintf (dump_file, "----------[%d]-------------\n", bb->index); 477 478 if (exit_bb) 479 { 480 if (bb != loop->latch) 481 { 482 if (dump_file && (dump_flags & TDF_DETAILS)) 483 fprintf (dump_file, "basic block after exit bb but before latch\n"); 484 return false; 485 } 486 else if (!empty_block_p (bb)) 487 { 488 if (dump_file && (dump_flags & TDF_DETAILS)) 489 fprintf (dump_file, "non empty basic block after exit bb\n"); 490 return false; 491 } 492 else if (bb == loop->latch 493 && bb != exit_bb 494 && !dominated_by_p (CDI_DOMINATORS, bb, exit_bb)) 495 { 496 if (dump_file && (dump_flags & TDF_DETAILS)) 497 fprintf (dump_file, "latch is not dominated by exit_block\n"); 498 return false; 499 } 500 } 501 502 /* Be less adventurous and handle only normal edges. */ 503 FOR_EACH_EDGE (e, ei, bb->succs) 504 if (e->flags & 505 (EDGE_ABNORMAL_CALL | EDGE_EH | EDGE_ABNORMAL | EDGE_IRREDUCIBLE_LOOP)) 506 { 507 if (dump_file && (dump_flags & TDF_DETAILS)) 508 fprintf (dump_file,"Difficult to handle edges\n"); 509 return false; 510 } 511 512 return true; 513} 514 515/* Return true, iff LOOP is if-convertible. 516 LOOP is if-convertible if, 517 - It is innermost. 518 - It has two or more basic blocks. 519 - It has only one exit. 520 - Loop header is not the exit edge. 521 - If its basic blocks and phi nodes are if convertible. See above for 522 more info. 523 FOR_VECTORIZER enables vectorizer specific checks. For example, support 524 for vector conditions, data dependency checks etc.. (Not implemented yet). */ 525 526static bool 527if_convertible_loop_p (struct loop *loop, bool for_vectorizer ATTRIBUTE_UNUSED) 528{ 529 basic_block bb; 530 gimple_stmt_iterator itr; 531 unsigned int i; 532 edge e; 533 edge_iterator ei; 534 basic_block exit_bb = NULL; 535 536 /* Handle only inner most loop. */ 537 if (!loop || loop->inner) 538 { 539 if (dump_file && (dump_flags & TDF_DETAILS)) 540 fprintf (dump_file, "not inner most loop\n"); 541 return false; 542 } 543 544 /* If only one block, no need for if-conversion. */ 545 if (loop->num_nodes <= 2) 546 { 547 if (dump_file && (dump_flags & TDF_DETAILS)) 548 fprintf (dump_file, "less than 2 basic blocks\n"); 549 return false; 550 } 551 552 /* More than one loop exit is too much to handle. */ 553 if (!single_exit (loop)) 554 { 555 if (dump_file && (dump_flags & TDF_DETAILS)) 556 fprintf (dump_file, "multiple exits\n"); 557 return false; 558 } 559 560 /* ??? Check target's vector conditional operation support for vectorizer. */ 561 562 /* If one of the loop header's edge is exit edge then do not apply 563 if-conversion. */ 564 FOR_EACH_EDGE (e, ei, loop->header->succs) 565 { 566 if (loop_exit_edge_p (loop, e)) 567 return false; 568 } 569 570 calculate_dominance_info (CDI_DOMINATORS); 571 calculate_dominance_info (CDI_POST_DOMINATORS); 572 573 /* Allow statements that can be handled during if-conversion. */ 574 ifc_bbs = get_loop_body_in_if_conv_order (loop); 575 if (!ifc_bbs) 576 { 577 if (dump_file && (dump_flags & TDF_DETAILS)) 578 fprintf (dump_file,"Irreducible loop\n"); 579 free_dominance_info (CDI_POST_DOMINATORS); 580 return false; 581 } 582 583 for (i = 0; i < loop->num_nodes; i++) 584 { 585 bb = ifc_bbs[i]; 586 587 if (!if_convertible_bb_p (loop, bb, exit_bb)) 588 return false; 589 590 /* Check statements. */ 591 for (itr = gsi_start_bb (bb); !gsi_end_p (itr); gsi_next (&itr)) 592 if (!if_convertible_stmt_p (loop, bb, gsi_stmt (itr))) 593 return false; 594 /* ??? Check data dependency for vectorizer. */ 595 596 /* What about phi nodes ? */ 597 itr = gsi_start_phis (bb); 598 599 /* Clear aux field of incoming edges to a bb with a phi node. */ 600 if (!gsi_end_p (itr)) 601 FOR_EACH_EDGE (e, ei, bb->preds) 602 e->aux = NULL; 603 604 /* Check statements. */ 605 for (; !gsi_end_p (itr); gsi_next (&itr)) 606 if (!if_convertible_phi_p (loop, bb, gsi_stmt (itr))) 607 return false; 608 609 if (bb_with_exit_edge_p (loop, bb)) 610 exit_bb = bb; 611 } 612 613 /* OK. Did not find any potential issues so go ahead in if-convert 614 this loop. Now there is no looking back. */ 615 if (dump_file) 616 fprintf (dump_file,"Applying if-conversion\n"); 617 618 free_dominance_info (CDI_POST_DOMINATORS); 619 return true; 620} 621 622/* Add condition COND into predicate list of basic block BB. */ 623 624static void 625add_to_predicate_list (basic_block bb, tree new_cond) 626{ 627 tree cond = (tree) bb->aux; 628 629 if (cond) 630 cond = fold_build2_loc (EXPR_LOCATION (cond), 631 TRUTH_OR_EXPR, boolean_type_node, 632 unshare_expr (cond), new_cond); 633 else 634 cond = new_cond; 635 636 bb->aux = cond; 637} 638 639/* Add condition COND into BB's predicate list. PREV_COND is 640 existing condition. */ 641 642static tree 643add_to_dst_predicate_list (struct loop * loop, edge e, 644 tree prev_cond, tree cond, 645 gimple_stmt_iterator *gsi) 646{ 647 tree new_cond = NULL_TREE; 648 649 if (!flow_bb_inside_loop_p (loop, e->dest)) 650 return NULL_TREE; 651 652 if (prev_cond == boolean_true_node || !prev_cond) 653 new_cond = unshare_expr (cond); 654 else 655 { 656 tree tmp; 657 gimple tmp_stmt = NULL; 658 659 prev_cond = force_gimple_operand_gsi (gsi, unshare_expr (prev_cond), 660 true, NULL, true, GSI_SAME_STMT); 661 662 cond = force_gimple_operand_gsi (gsi, unshare_expr (cond), 663 true, NULL, true, GSI_SAME_STMT); 664 665 /* Add the condition to aux field of the edge. In case edge 666 destination is a PHI node, this condition will be ANDed with 667 block predicate to construct complete condition. */ 668 e->aux = cond; 669 670 /* new_cond == prev_cond AND cond */ 671 tmp = build2 (TRUTH_AND_EXPR, boolean_type_node, 672 unshare_expr (prev_cond), cond); 673 tmp_stmt = ifc_temp_var (boolean_type_node, tmp); 674 gsi_insert_before (gsi, tmp_stmt, GSI_SAME_STMT); 675 new_cond = gimple_assign_lhs (tmp_stmt); 676 } 677 add_to_predicate_list (e->dest, new_cond); 678 return new_cond; 679} 680 681/* During if-conversion aux field from basic block structure is used to hold 682 predicate list. Clean each basic block's predicate list for the given LOOP. 683 Also clean aux field of successor edges, used to hold true and false 684 condition from conditional expression. */ 685 686static void 687clean_predicate_lists (struct loop *loop) 688{ 689 basic_block *bb; 690 unsigned int i; 691 edge e; 692 edge_iterator ei; 693 694 bb = get_loop_body (loop); 695 for (i = 0; i < loop->num_nodes; i++) 696 { 697 bb[i]->aux = NULL; 698 FOR_EACH_EDGE (e, ei, bb[i]->succs) 699 e->aux = NULL; 700 } 701 free (bb); 702} 703 704/* Basic block BB has two predecessors. Using predecessor's aux field, set 705 appropriate condition COND for the PHI node replacement. Return true block 706 whose phi arguments are selected when cond is true. */ 707 708static basic_block 709find_phi_replacement_condition (struct loop *loop, 710 basic_block bb, tree *cond, 711 gimple_stmt_iterator *gsi) 712{ 713 edge first_edge, second_edge; 714 tree tmp_cond; 715 716 gcc_assert (EDGE_COUNT (bb->preds) == 2); 717 first_edge = EDGE_PRED (bb, 0); 718 second_edge = EDGE_PRED (bb, 1); 719 720 /* Use condition based on following criteria: 721 1) 722 S1: x = !c ? a : b; 723 724 S2: x = c ? b : a; 725 726 S2 is preferred over S1. Make 'b' first_bb and use its condition. 727 728 2) Do not make loop header first_bb. 729 730 3) 731 S1: x = !(c == d)? a : b; 732 733 S21: t1 = c == d; 734 S22: x = t1 ? b : a; 735 736 S3: x = (c == d) ? b : a; 737 738 S3 is preferred over S1 and S2*, Make 'b' first_bb and use 739 its condition. 740 741 4) If pred B is dominated by pred A then use pred B's condition. 742 See PR23115. */ 743 744 /* Select condition that is not TRUTH_NOT_EXPR. */ 745 tmp_cond = (tree) (first_edge->src)->aux; 746 gcc_assert (tmp_cond); 747 748 if (TREE_CODE (tmp_cond) == TRUTH_NOT_EXPR) 749 { 750 edge tmp_edge; 751 752 tmp_edge = first_edge; 753 first_edge = second_edge; 754 second_edge = tmp_edge; 755 } 756 757 /* Check if FIRST_BB is loop header or not and make sure that 758 FIRST_BB does not dominate SECOND_BB. */ 759 if (first_edge->src == loop->header 760 || dominated_by_p (CDI_DOMINATORS, 761 second_edge->src, first_edge->src)) 762 { 763 *cond = (tree) (second_edge->src)->aux; 764 765 /* If there is a condition on an incoming edge, 766 AND it with the incoming bb predicate. */ 767 if (second_edge->aux) 768 *cond = build2 (TRUTH_AND_EXPR, boolean_type_node, 769 *cond, (tree) second_edge->aux); 770 771 if (TREE_CODE (*cond) == TRUTH_NOT_EXPR) 772 /* We can be smart here and choose inverted 773 condition without switching bbs. */ 774 *cond = invert_truthvalue (*cond); 775 else 776 /* Select non loop header bb. */ 777 first_edge = second_edge; 778 } 779 else 780 { 781 /* FIRST_BB is not loop header */ 782 *cond = (tree) (first_edge->src)->aux; 783 784 /* If there is a condition on an incoming edge, 785 AND it with the incoming bb predicate. */ 786 if (first_edge->aux) 787 *cond = build2 (TRUTH_AND_EXPR, boolean_type_node, 788 *cond, (tree) first_edge->aux); 789 } 790 791 /* Create temp. for the condition. Vectorizer prefers to have gimple 792 value as condition. Various targets use different means to communicate 793 condition in vector compare operation. Using gimple value allows 794 compiler to emit vector compare and select RTL without exposing 795 compare's result. */ 796 *cond = force_gimple_operand_gsi (gsi, unshare_expr (*cond), 797 false, NULL_TREE, 798 true, GSI_SAME_STMT); 799 if (!is_gimple_reg (*cond) && !is_gimple_condexpr (*cond)) 800 { 801 gimple new_stmt; 802 803 new_stmt = ifc_temp_var (TREE_TYPE (*cond), unshare_expr (*cond)); 804 gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT); 805 *cond = gimple_assign_lhs (new_stmt); 806 } 807 808 gcc_assert (*cond); 809 810 return first_edge->src; 811} 812 813 814/* Replace PHI node with conditional modify expr using COND. 815 This routine does not handle PHI nodes with more than two arguments. 816 For example, 817 S1: A = PHI <x1(1), x2(5) 818 is converted into, 819 S2: A = cond ? x1 : x2; 820 S2 is inserted at the top of basic block's statement list. 821 When COND is true, phi arg from TRUE_BB is selected. 822*/ 823 824static void 825replace_phi_with_cond_gimple_assign_stmt (gimple phi, tree cond, 826 basic_block true_bb, 827 gimple_stmt_iterator *gsi) 828{ 829 gimple new_stmt; 830 basic_block bb; 831 tree rhs; 832 tree arg_0, arg_1; 833 834 gcc_assert (gimple_code (phi) == GIMPLE_PHI); 835 836 /* If this is not filtered earlier, then now it is too late. */ 837 gcc_assert (gimple_phi_num_args (phi) == 2); 838 839 /* Find basic block and initialize iterator. */ 840 bb = gimple_bb (phi); 841 842 /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr. */ 843 if (EDGE_PRED (bb, 1)->src == true_bb) 844 { 845 arg_0 = gimple_phi_arg_def (phi, 1); 846 arg_1 = gimple_phi_arg_def (phi, 0); 847 } 848 else 849 { 850 arg_0 = gimple_phi_arg_def (phi, 0); 851 arg_1 = gimple_phi_arg_def (phi, 1); 852 } 853 854 /* Build new RHS using selected condition and arguments. */ 855 rhs = build3 (COND_EXPR, TREE_TYPE (PHI_RESULT (phi)), 856 unshare_expr (cond), unshare_expr (arg_0), 857 unshare_expr (arg_1)); 858 859 /* Create new GIMPLE_ASSIGN statement using RHS. */ 860 new_stmt = gimple_build_assign (unshare_expr (PHI_RESULT (phi)), rhs); 861 862 /* Make new statement definition of the original phi result. */ 863 SSA_NAME_DEF_STMT (gimple_phi_result (phi)) = new_stmt; 864 865 /* Insert using iterator. */ 866 gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT); 867 update_stmt (new_stmt); 868 869 if (dump_file && (dump_flags & TDF_DETAILS)) 870 { 871 fprintf (dump_file, "new phi replacement stmt\n"); 872 print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM); 873 } 874} 875 876/* Process phi nodes for the given LOOP. Replace phi nodes with cond 877 modify expr. */ 878 879static void 880process_phi_nodes (struct loop *loop) 881{ 882 basic_block bb; 883 unsigned int orig_loop_num_nodes = loop->num_nodes; 884 unsigned int i; 885 886 /* Replace phi nodes with cond. modify expr. */ 887 for (i = 1; i < orig_loop_num_nodes; i++) 888 { 889 gimple phi; 890 tree cond = NULL_TREE; 891 gimple_stmt_iterator gsi, phi_gsi; 892 basic_block true_bb = NULL; 893 bb = ifc_bbs[i]; 894 895 if (bb == loop->header) 896 continue; 897 898 phi_gsi = gsi_start_phis (bb); 899 gsi = gsi_after_labels (bb); 900 901 /* BB has two predecessors. Using predecessor's aux field, set 902 appropriate condition for the PHI node replacement. */ 903 if (!gsi_end_p (phi_gsi)) 904 true_bb = find_phi_replacement_condition (loop, bb, &cond, &gsi); 905 906 while (!gsi_end_p (phi_gsi)) 907 { 908 phi = gsi_stmt (phi_gsi); 909 replace_phi_with_cond_gimple_assign_stmt (phi, cond, true_bb, &gsi); 910 release_phi_node (phi); 911 gsi_next (&phi_gsi); 912 } 913 set_phi_nodes (bb, NULL); 914 } 915 return; 916} 917 918/* Combine all basic block from the given LOOP into one or two super 919 basic block. Replace PHI nodes with conditional modify expression. */ 920 921static void 922combine_blocks (struct loop *loop) 923{ 924 basic_block bb, exit_bb, merge_target_bb; 925 unsigned int orig_loop_num_nodes = loop->num_nodes; 926 unsigned int i; 927 edge e; 928 edge_iterator ei; 929 930 /* Process phi nodes to prepare blocks for merge. */ 931 process_phi_nodes (loop); 932 933 /* Merge basic blocks. First remove all the edges in the loop, except 934 for those from the exit block. */ 935 exit_bb = NULL; 936 for (i = 0; i < orig_loop_num_nodes; i++) 937 { 938 bb = ifc_bbs[i]; 939 if (bb_with_exit_edge_p (loop, bb)) 940 { 941 exit_bb = bb; 942 break; 943 } 944 } 945 gcc_assert (exit_bb != loop->latch); 946 947 for (i = 1; i < orig_loop_num_nodes; i++) 948 { 949 bb = ifc_bbs[i]; 950 951 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei));) 952 { 953 if (e->src == exit_bb) 954 ei_next (&ei); 955 else 956 remove_edge (e); 957 } 958 } 959 960 if (exit_bb != NULL) 961 { 962 if (exit_bb != loop->header) 963 { 964 /* Connect this node with loop header. */ 965 make_edge (loop->header, exit_bb, EDGE_FALLTHRU); 966 set_immediate_dominator (CDI_DOMINATORS, exit_bb, loop->header); 967 } 968 969 /* Redirect non-exit edges to loop->latch. */ 970 FOR_EACH_EDGE (e, ei, exit_bb->succs) 971 { 972 if (!loop_exit_edge_p (loop, e)) 973 redirect_edge_and_branch (e, loop->latch); 974 } 975 set_immediate_dominator (CDI_DOMINATORS, loop->latch, exit_bb); 976 } 977 else 978 { 979 /* If the loop does not have exit then reconnect header and latch. */ 980 make_edge (loop->header, loop->latch, EDGE_FALLTHRU); 981 set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header); 982 } 983 984 merge_target_bb = loop->header; 985 for (i = 1; i < orig_loop_num_nodes; i++) 986 { 987 gimple_stmt_iterator gsi; 988 gimple_stmt_iterator last; 989 990 bb = ifc_bbs[i]; 991 992 if (bb == exit_bb || bb == loop->latch) 993 continue; 994 995 /* Remove labels and make stmts member of loop->header. */ 996 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); ) 997 { 998 if (gimple_code (gsi_stmt (gsi)) == GIMPLE_LABEL) 999 gsi_remove (&gsi, true); 1000 else 1001 { 1002 gimple_set_bb (gsi_stmt (gsi), merge_target_bb); 1003 gsi_next (&gsi); 1004 } 1005 } 1006 1007 /* Update stmt list. */ 1008 last = gsi_last_bb (merge_target_bb); 1009 gsi_insert_seq_after (&last, bb_seq (bb), GSI_NEW_STMT); 1010 set_bb_seq (bb, NULL); 1011 1012 delete_basic_block (bb); 1013 } 1014 1015 /* Now if possible, merge loop header and block with exit edge. 1016 This reduces number of basic blocks to 2. Auto vectorizer addresses 1017 loops with two nodes only. FIXME: Use cleanup_tree_cfg(). */ 1018 if (exit_bb 1019 && exit_bb != loop->header 1020 && can_merge_blocks_p (loop->header, exit_bb)) 1021 merge_blocks (loop->header, exit_bb); 1022} 1023 1024/* Make a new temp variable of type TYPE. Add GIMPLE_ASSIGN to assign EXP 1025 to the new variable. */ 1026 1027static gimple 1028ifc_temp_var (tree type, tree exp) 1029{ 1030 const char *name = "_ifc_"; 1031 tree var, new_name; 1032 gimple stmt; 1033 1034 /* Create new temporary variable. */ 1035 var = create_tmp_var (type, name); 1036 add_referenced_var (var); 1037 1038 /* Build new statement to assign EXP to new variable. */ 1039 stmt = gimple_build_assign (var, exp); 1040 1041 /* Get SSA name for the new variable and set make new statement 1042 its definition statement. */ 1043 new_name = make_ssa_name (var, stmt); 1044 gimple_assign_set_lhs (stmt, new_name); 1045 SSA_NAME_DEF_STMT (new_name) = stmt; 1046 update_stmt (stmt); 1047 1048 return stmt; 1049} 1050 1051 1052/* Return TRUE iff, all pred blocks of BB are visited. 1053 Bitmap VISITED keeps history of visited blocks. */ 1054 1055static bool 1056pred_blocks_visited_p (basic_block bb, bitmap *visited) 1057{ 1058 edge e; 1059 edge_iterator ei; 1060 FOR_EACH_EDGE (e, ei, bb->preds) 1061 if (!bitmap_bit_p (*visited, e->src->index)) 1062 return false; 1063 1064 return true; 1065} 1066 1067/* Get body of a LOOP in suitable order for if-conversion. 1068 It is caller's responsibility to deallocate basic block 1069 list. If-conversion suitable order is, BFS order with one 1070 additional constraint. Select block in BFS block, if all 1071 pred are already selected. */ 1072 1073static basic_block * 1074get_loop_body_in_if_conv_order (const struct loop *loop) 1075{ 1076 basic_block *blocks, *blocks_in_bfs_order; 1077 basic_block bb; 1078 bitmap visited; 1079 unsigned int index = 0; 1080 unsigned int visited_count = 0; 1081 1082 gcc_assert (loop->num_nodes); 1083 gcc_assert (loop->latch != EXIT_BLOCK_PTR); 1084 1085 blocks = XCNEWVEC (basic_block, loop->num_nodes); 1086 visited = BITMAP_ALLOC (NULL); 1087 1088 blocks_in_bfs_order = get_loop_body_in_bfs_order (loop); 1089 1090 index = 0; 1091 while (index < loop->num_nodes) 1092 { 1093 bb = blocks_in_bfs_order [index]; 1094 1095 if (bb->flags & BB_IRREDUCIBLE_LOOP) 1096 { 1097 free (blocks_in_bfs_order); 1098 BITMAP_FREE (visited); 1099 free (blocks); 1100 return NULL; 1101 } 1102 if (!bitmap_bit_p (visited, bb->index)) 1103 { 1104 if (pred_blocks_visited_p (bb, &visited) 1105 || bb == loop->header) 1106 { 1107 /* This block is now visited. */ 1108 bitmap_set_bit (visited, bb->index); 1109 blocks[visited_count++] = bb; 1110 } 1111 } 1112 index++; 1113 if (index == loop->num_nodes 1114 && visited_count != loop->num_nodes) 1115 { 1116 /* Not done yet. */ 1117 index = 0; 1118 } 1119 } 1120 free (blocks_in_bfs_order); 1121 BITMAP_FREE (visited); 1122 return blocks; 1123} 1124 1125/* Return true if one of the basic block BB edge is exit of LOOP. */ 1126 1127static bool 1128bb_with_exit_edge_p (struct loop *loop, basic_block bb) 1129{ 1130 edge e; 1131 edge_iterator ei; 1132 bool exit_edge_found = false; 1133 1134 FOR_EACH_EDGE (e, ei, bb->succs) 1135 if (loop_exit_edge_p (loop, e)) 1136 { 1137 exit_edge_found = true; 1138 break; 1139 } 1140 1141 return exit_edge_found; 1142} 1143 1144/* Tree if-conversion pass management. */ 1145 1146static unsigned int 1147main_tree_if_conversion (void) 1148{ 1149 loop_iterator li; 1150 struct loop *loop; 1151 1152 if (number_of_loops () <= 1) 1153 return 0; 1154 1155 FOR_EACH_LOOP (li, loop, 0) 1156 { 1157 tree_if_conversion (loop, true); 1158 } 1159 return 0; 1160} 1161 1162static bool 1163gate_tree_if_conversion (void) 1164{ 1165 return flag_tree_vectorize != 0; 1166} 1167 1168struct gimple_opt_pass pass_if_conversion = 1169{ 1170 { 1171 GIMPLE_PASS, 1172 "ifcvt", /* name */ 1173 gate_tree_if_conversion, /* gate */ 1174 main_tree_if_conversion, /* execute */ 1175 NULL, /* sub */ 1176 NULL, /* next */ 1177 0, /* static_pass_number */ 1178 TV_NONE, /* tv_id */ 1179 PROP_cfg | PROP_ssa, /* properties_required */ 1180 0, /* properties_provided */ 1181 0, /* properties_destroyed */ 1182 0, /* todo_flags_start */ 1183 TODO_dump_func | TODO_verify_loops | TODO_verify_stmts | TODO_verify_flow 1184 /* todo_flags_finish */ 1185 } 1186}; 1187