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