tree-if-conv.c revision 171826
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 compiler 766 to emit vector compare and select RTL without exposing compare's result. */ 767 *cond = force_gimple_operand (*cond, &new_stmts, false, NULL_TREE); 768 if (new_stmts) 769 bsi_insert_before (bsi, new_stmts, BSI_SAME_STMT); 770 if (!is_gimple_reg (*cond) && !is_gimple_condexpr (*cond)) 771 { 772 tree new_stmt; 773 774 new_stmt = ifc_temp_var (TREE_TYPE (*cond), unshare_expr (*cond)); 775 bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT); 776 *cond = TREE_OPERAND (new_stmt, 0); 777 } 778 779 gcc_assert (*cond); 780 781 return first_edge->src; 782} 783 784 785/* Replace PHI node with conditional modify expr using COND. 786 This routine does not handle PHI nodes with more than two arguments. 787 For example, 788 S1: A = PHI <x1(1), x2(5) 789 is converted into, 790 S2: A = cond ? x1 : x2; 791 S2 is inserted at the top of basic block's statement list. 792 When COND is true, phi arg from TRUE_BB is selected. 793*/ 794 795static void 796replace_phi_with_cond_modify_expr (tree phi, tree cond, basic_block true_bb, 797 block_stmt_iterator *bsi) 798{ 799 tree new_stmt; 800 basic_block bb; 801 tree rhs; 802 tree arg_0, arg_1; 803 804 gcc_assert (TREE_CODE (phi) == PHI_NODE); 805 806 /* If this is not filtered earlier, then now it is too late. */ 807 gcc_assert (PHI_NUM_ARGS (phi) == 2); 808 809 /* Find basic block and initialize iterator. */ 810 bb = bb_for_stmt (phi); 811 812 /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr. */ 813 if (EDGE_PRED (bb, 1)->src == true_bb) 814 { 815 arg_0 = PHI_ARG_DEF (phi, 1); 816 arg_1 = PHI_ARG_DEF (phi, 0); 817 } 818 else 819 { 820 arg_0 = PHI_ARG_DEF (phi, 0); 821 arg_1 = PHI_ARG_DEF (phi, 1); 822 } 823 824 /* Build new RHS using selected condition and arguments. */ 825 rhs = build3 (COND_EXPR, TREE_TYPE (PHI_RESULT (phi)), 826 unshare_expr (cond), unshare_expr (arg_0), 827 unshare_expr (arg_1)); 828 829 /* Create new MODIFY expression using RHS. */ 830 new_stmt = build2 (MODIFY_EXPR, TREE_TYPE (PHI_RESULT (phi)), 831 unshare_expr (PHI_RESULT (phi)), rhs); 832 833 /* Make new statement definition of the original phi result. */ 834 SSA_NAME_DEF_STMT (PHI_RESULT (phi)) = new_stmt; 835 836 /* Insert using iterator. */ 837 bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT); 838 update_stmt (new_stmt); 839 840 if (dump_file && (dump_flags & TDF_DETAILS)) 841 { 842 fprintf (dump_file, "new phi replacement stmt\n"); 843 print_generic_stmt (dump_file, new_stmt, TDF_SLIM); 844 } 845} 846 847/* Process phi nodes for the given LOOP. Replace phi nodes with cond 848 modify expr. */ 849 850static void 851process_phi_nodes (struct loop *loop) 852{ 853 basic_block bb; 854 unsigned int orig_loop_num_nodes = loop->num_nodes; 855 unsigned int i; 856 857 /* Replace phi nodes with cond. modify expr. */ 858 for (i = 1; i < orig_loop_num_nodes; i++) 859 { 860 tree phi, cond; 861 block_stmt_iterator bsi; 862 basic_block true_bb = NULL; 863 bb = ifc_bbs[i]; 864 865 if (bb == loop->header) 866 continue; 867 868 phi = phi_nodes (bb); 869 bsi = bsi_after_labels (bb); 870 871 /* BB has two predecessors. Using predecessor's aux field, set 872 appropriate condition for the PHI node replacement. */ 873 if (phi) 874 true_bb = find_phi_replacement_condition (loop, bb, &cond, &bsi); 875 876 while (phi) 877 { 878 tree next = PHI_CHAIN (phi); 879 replace_phi_with_cond_modify_expr (phi, cond, true_bb, &bsi); 880 release_phi_node (phi); 881 phi = next; 882 } 883 bb->phi_nodes = NULL; 884 } 885 return; 886} 887 888/* Combine all basic block from the given LOOP into one or two super 889 basic block. Replace PHI nodes with conditional modify expression. */ 890 891static void 892combine_blocks (struct loop *loop) 893{ 894 basic_block bb, exit_bb, merge_target_bb; 895 unsigned int orig_loop_num_nodes = loop->num_nodes; 896 unsigned int i; 897 edge e; 898 edge_iterator ei; 899 900 /* Process phi nodes to prepare blocks for merge. */ 901 process_phi_nodes (loop); 902 903 /* Merge basic blocks. First remove all the edges in the loop, except 904 for those from the exit block. */ 905 exit_bb = NULL; 906 for (i = 0; i < orig_loop_num_nodes; i++) 907 { 908 bb = ifc_bbs[i]; 909 if (bb_with_exit_edge_p (loop, bb)) 910 { 911 exit_bb = bb; 912 break; 913 } 914 } 915 gcc_assert (exit_bb != loop->latch); 916 917 for (i = 1; i < orig_loop_num_nodes; i++) 918 { 919 bb = ifc_bbs[i]; 920 921 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei));) 922 { 923 if (e->src == exit_bb) 924 ei_next (&ei); 925 else 926 remove_edge (e); 927 } 928 } 929 930 if (exit_bb != NULL) 931 { 932 if (exit_bb != loop->header) 933 { 934 /* Connect this node with loop header. */ 935 make_edge (loop->header, exit_bb, EDGE_FALLTHRU); 936 set_immediate_dominator (CDI_DOMINATORS, exit_bb, loop->header); 937 } 938 939 /* Redirect non-exit edges to loop->latch. */ 940 FOR_EACH_EDGE (e, ei, exit_bb->succs) 941 { 942 if (!loop_exit_edge_p (loop, e)) 943 redirect_edge_and_branch (e, loop->latch); 944 } 945 set_immediate_dominator (CDI_DOMINATORS, loop->latch, exit_bb); 946 } 947 else 948 { 949 /* If the loop does not have exit then reconnect header and latch. */ 950 make_edge (loop->header, loop->latch, EDGE_FALLTHRU); 951 set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header); 952 } 953 954 merge_target_bb = loop->header; 955 for (i = 1; i < orig_loop_num_nodes; i++) 956 { 957 block_stmt_iterator bsi; 958 tree_stmt_iterator last; 959 960 bb = ifc_bbs[i]; 961 962 if (bb == exit_bb || bb == loop->latch) 963 continue; 964 965 /* Remove labels and make stmts member of loop->header. */ 966 for (bsi = bsi_start (bb); !bsi_end_p (bsi); ) 967 { 968 if (TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR) 969 bsi_remove (&bsi, true); 970 else 971 { 972 set_bb_for_stmt (bsi_stmt (bsi), merge_target_bb); 973 bsi_next (&bsi); 974 } 975 } 976 977 /* Update stmt list. */ 978 last = tsi_last (merge_target_bb->stmt_list); 979 tsi_link_after (&last, bb->stmt_list, TSI_NEW_STMT); 980 bb->stmt_list = NULL; 981 982 /* Update dominator info. */ 983 if (dom_computed[CDI_DOMINATORS]) 984 delete_from_dominance_info (CDI_DOMINATORS, bb); 985 if (dom_computed[CDI_POST_DOMINATORS]) 986 delete_from_dominance_info (CDI_POST_DOMINATORS, bb); 987 988 /* Remove basic block. */ 989 remove_bb_from_loops (bb); 990 expunge_block (bb); 991 } 992 993 /* Now if possible, merge loop header and block with exit edge. 994 This reduces number of basic blocks to 2. Auto vectorizer addresses 995 loops with two nodes only. FIXME: Use cleanup_tree_cfg(). */ 996 if (exit_bb 997 && exit_bb != loop->header 998 && can_merge_blocks_p (loop->header, exit_bb)) 999 { 1000 remove_bb_from_loops (exit_bb); 1001 merge_blocks (loop->header, exit_bb); 1002 } 1003} 1004 1005/* Make new temp variable of type TYPE. Add MODIFY_EXPR to assign EXP 1006 to the new variable. */ 1007 1008static tree 1009ifc_temp_var (tree type, tree exp) 1010{ 1011 const char *name = "_ifc_"; 1012 tree var, stmt, new_name; 1013 1014 if (is_gimple_reg (exp)) 1015 return exp; 1016 1017 /* Create new temporary variable. */ 1018 var = create_tmp_var (type, name); 1019 add_referenced_var (var); 1020 1021 /* Build new statement to assign EXP to new variable. */ 1022 stmt = build2 (MODIFY_EXPR, type, var, exp); 1023 1024 /* Get SSA name for the new variable and set make new statement 1025 its definition statement. */ 1026 new_name = make_ssa_name (var, stmt); 1027 TREE_OPERAND (stmt, 0) = new_name; 1028 SSA_NAME_DEF_STMT (new_name) = stmt; 1029 1030 return stmt; 1031} 1032 1033 1034/* Return TRUE iff, all pred blocks of BB are visited. 1035 Bitmap VISITED keeps history of visited blocks. */ 1036 1037static bool 1038pred_blocks_visited_p (basic_block bb, bitmap *visited) 1039{ 1040 edge e; 1041 edge_iterator ei; 1042 FOR_EACH_EDGE (e, ei, bb->preds) 1043 if (!bitmap_bit_p (*visited, e->src->index)) 1044 return false; 1045 1046 return true; 1047} 1048 1049/* Get body of a LOOP in suitable order for if-conversion. 1050 It is caller's responsibility to deallocate basic block 1051 list. If-conversion suitable order is, BFS order with one 1052 additional constraint. Select block in BFS block, if all 1053 pred are already selected. */ 1054 1055static basic_block * 1056get_loop_body_in_if_conv_order (const struct loop *loop) 1057{ 1058 basic_block *blocks, *blocks_in_bfs_order; 1059 basic_block bb; 1060 bitmap visited; 1061 unsigned int index = 0; 1062 unsigned int visited_count = 0; 1063 1064 gcc_assert (loop->num_nodes); 1065 gcc_assert (loop->latch != EXIT_BLOCK_PTR); 1066 1067 blocks = XCNEWVEC (basic_block, loop->num_nodes); 1068 visited = BITMAP_ALLOC (NULL); 1069 1070 blocks_in_bfs_order = get_loop_body_in_bfs_order (loop); 1071 1072 index = 0; 1073 while (index < loop->num_nodes) 1074 { 1075 bb = blocks_in_bfs_order [index]; 1076 1077 if (bb->flags & BB_IRREDUCIBLE_LOOP) 1078 { 1079 free (blocks_in_bfs_order); 1080 BITMAP_FREE (visited); 1081 free (blocks); 1082 return NULL; 1083 } 1084 if (!bitmap_bit_p (visited, bb->index)) 1085 { 1086 if (pred_blocks_visited_p (bb, &visited) 1087 || bb == loop->header) 1088 { 1089 /* This block is now visited. */ 1090 bitmap_set_bit (visited, bb->index); 1091 blocks[visited_count++] = bb; 1092 } 1093 } 1094 index++; 1095 if (index == loop->num_nodes 1096 && visited_count != loop->num_nodes) 1097 { 1098 /* Not done yet. */ 1099 index = 0; 1100 } 1101 } 1102 free (blocks_in_bfs_order); 1103 BITMAP_FREE (visited); 1104 return blocks; 1105} 1106 1107/* Return true if one of the basic block BB edge is exit of LOOP. */ 1108 1109static bool 1110bb_with_exit_edge_p (struct loop *loop, basic_block bb) 1111{ 1112 edge e; 1113 edge_iterator ei; 1114 bool exit_edge_found = false; 1115 1116 FOR_EACH_EDGE (e, ei, bb->succs) 1117 if (loop_exit_edge_p (loop, e)) 1118 { 1119 exit_edge_found = true; 1120 break; 1121 } 1122 1123 return exit_edge_found; 1124} 1125 1126/* Tree if-conversion pass management. */ 1127 1128static unsigned int 1129main_tree_if_conversion (void) 1130{ 1131 unsigned i, loop_num; 1132 struct loop *loop; 1133 1134 if (!current_loops) 1135 return 0; 1136 1137 loop_num = current_loops->num; 1138 for (i = 0; i < loop_num; i++) 1139 { 1140 loop = current_loops->parray[i]; 1141 if (!loop) 1142 continue; 1143 1144 tree_if_conversion (loop, true); 1145 } 1146 return 0; 1147} 1148 1149static bool 1150gate_tree_if_conversion (void) 1151{ 1152 return flag_tree_vectorize != 0; 1153} 1154 1155struct tree_opt_pass pass_if_conversion = 1156{ 1157 "ifcvt", /* name */ 1158 gate_tree_if_conversion, /* gate */ 1159 main_tree_if_conversion, /* execute */ 1160 NULL, /* sub */ 1161 NULL, /* next */ 1162 0, /* static_pass_number */ 1163 0, /* tv_id */ 1164 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */ 1165 0, /* properties_provided */ 1166 0, /* properties_destroyed */ 1167 0, /* todo_flags_start */ 1168 TODO_dump_func | TODO_verify_loops | TODO_verify_stmts | TODO_verify_flow, 1169 /* todo_flags_finish */ 1170 0 /* letter */ 1171}; 1172