1 /* If-conversion for vectorizer. 2 Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011 3 Free Software Foundation, Inc. 4 Contributed by Devang Patel <dpatel@apple.com> 5 6 This file is part of GCC. 7 8 GCC is free software; you can redistribute it and/or modify it under 9 the terms of the GNU General Public License as published by the Free 10 Software Foundation; either version 3, or (at your option) any later 11 version. 12 13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY 14 WARRANTY; without even the implied warranty of MERCHANTABILITY or 15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 16 for more details. 17 18 You should have received a copy of the GNU General Public License 19 along with GCC; see the file COPYING3. If not see 20 <http://www.gnu.org/licenses/>. */ 21 22 /* This pass implements a tree level if-conversion of loops. Its 23 initial goal is to help the vectorizer to vectorize loops with 24 conditions. 25 26 A short description of if-conversion: 27 28 o Decide if a loop is if-convertible or not. 29 o Walk all loop basic blocks in breadth first order (BFS order). 30 o Remove conditional statements (at the end of basic block) 31 and propagate condition into destination basic blocks' 32 predicate list. 33 o Replace modify expression with conditional modify expression 34 using current basic block's condition. 35 o Merge all basic blocks 36 o Replace phi nodes with conditional modify expr 37 o Merge all basic blocks into header 38 39 Sample transformation: 40 41 INPUT 42 ----- 43 44 # i_23 = PHI <0(0), i_18(10)>; 45 <L0>:; 46 j_15 = A[i_23]; 47 if (j_15 > 41) goto <L1>; else goto <L17>; 48 49 <L17>:; 50 goto <bb 3> (<L3>); 51 52 <L1>:; 53 54 # iftmp.2_4 = PHI <0(8), 42(2)>; 55 <L3>:; 56 A[i_23] = iftmp.2_4; 57 i_18 = i_23 + 1; 58 if (i_18 <= 15) goto <L19>; else goto <L18>; 59 60 <L19>:; 61 goto <bb 1> (<L0>); 62 63 <L18>:; 64 65 OUTPUT 66 ------ 67 68 # i_23 = PHI <0(0), i_18(10)>; 69 <L0>:; 70 j_15 = A[i_23]; 71 72 <L3>:; 73 iftmp.2_4 = j_15 > 41 ? 42 : 0; 74 A[i_23] = iftmp.2_4; 75 i_18 = i_23 + 1; 76 if (i_18 <= 15) goto <L19>; else goto <L18>; 77 78 <L19>:; 79 goto <bb 1> (<L0>); 80 81 <L18>:; 82 */ 83 84 #include "config.h" 85 #include "system.h" 86 #include "coretypes.h" 87 #include "tm.h" 88 #include "tree.h" 89 #include "flags.h" 90 #include "timevar.h" 91 #include "basic-block.h" 92 #include "tree-pretty-print.h" 93 #include "gimple-pretty-print.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 "dbgcnt.h" 102 103 /* List of basic blocks in if-conversion-suitable order. */ 104 static basic_block *ifc_bbs; 105 106 /* Structure used to predicate basic blocks. This is attached to the 107 ->aux field of the BBs in the loop to be if-converted. */ 108 typedef struct bb_predicate_s { 109 110 /* The condition under which this basic block is executed. */ 111 tree predicate; 112 113 /* PREDICATE is gimplified, and the sequence of statements is 114 recorded here, in order to avoid the duplication of computations 115 that occur in previous conditions. See PR44483. */ 116 gimple_seq predicate_gimplified_stmts; 117 } *bb_predicate_p; 118 119 /* Returns true when the basic block BB has a predicate. */ 120 121 static inline bool 122 bb_has_predicate (basic_block bb) 123 { 124 return bb->aux != NULL; 125 } 126 127 /* Returns the gimplified predicate for basic block BB. */ 128 129 static inline tree 130 bb_predicate (basic_block bb) 131 { 132 return ((bb_predicate_p) bb->aux)->predicate; 133 } 134 135 /* Sets the gimplified predicate COND for basic block BB. */ 136 137 static inline void 138 set_bb_predicate (basic_block bb, tree cond) 139 { 140 gcc_assert ((TREE_CODE (cond) == TRUTH_NOT_EXPR 141 && is_gimple_condexpr (TREE_OPERAND (cond, 0))) 142 || is_gimple_condexpr (cond)); 143 ((bb_predicate_p) bb->aux)->predicate = cond; 144 } 145 146 /* Returns the sequence of statements of the gimplification of the 147 predicate for basic block BB. */ 148 149 static inline gimple_seq 150 bb_predicate_gimplified_stmts (basic_block bb) 151 { 152 return ((bb_predicate_p) bb->aux)->predicate_gimplified_stmts; 153 } 154 155 /* Sets the sequence of statements STMTS of the gimplification of the 156 predicate for basic block BB. */ 157 158 static inline void 159 set_bb_predicate_gimplified_stmts (basic_block bb, gimple_seq stmts) 160 { 161 ((bb_predicate_p) bb->aux)->predicate_gimplified_stmts = stmts; 162 } 163 164 /* Adds the sequence of statements STMTS to the sequence of statements 165 of the predicate for basic block BB. */ 166 167 static inline void 168 add_bb_predicate_gimplified_stmts (basic_block bb, gimple_seq stmts) 169 { 170 gimple_seq_add_seq 171 (&(((bb_predicate_p) bb->aux)->predicate_gimplified_stmts), stmts); 172 } 173 174 /* Initializes to TRUE the predicate of basic block BB. */ 175 176 static inline void 177 init_bb_predicate (basic_block bb) 178 { 179 bb->aux = XNEW (struct bb_predicate_s); 180 set_bb_predicate_gimplified_stmts (bb, NULL); 181 set_bb_predicate (bb, boolean_true_node); 182 } 183 184 /* Free the predicate of basic block BB. */ 185 186 static inline void 187 free_bb_predicate (basic_block bb) 188 { 189 gimple_seq stmts; 190 191 if (!bb_has_predicate (bb)) 192 return; 193 194 /* Release the SSA_NAMEs created for the gimplification of the 195 predicate. */ 196 stmts = bb_predicate_gimplified_stmts (bb); 197 if (stmts) 198 { 199 gimple_stmt_iterator i; 200 201 for (i = gsi_start (stmts); !gsi_end_p (i); gsi_next (&i)) 202 free_stmt_operands (gsi_stmt (i)); 203 } 204 205 free (bb->aux); 206 bb->aux = NULL; 207 } 208 209 /* Free the predicate of BB and reinitialize it with the true 210 predicate. */ 211 212 static inline void 213 reset_bb_predicate (basic_block bb) 214 { 215 free_bb_predicate (bb); 216 init_bb_predicate (bb); 217 } 218 219 /* Returns a new SSA_NAME of type TYPE that is assigned the value of 220 the expression EXPR. Inserts the statement created for this 221 computation before GSI and leaves the iterator GSI at the same 222 statement. */ 223 224 static tree 225 ifc_temp_var (tree type, tree expr, gimple_stmt_iterator *gsi) 226 { 227 const char *name = "_ifc_"; 228 tree var, new_name; 229 gimple stmt; 230 231 /* Create new temporary variable. */ 232 var = create_tmp_var (type, name); 233 add_referenced_var (var); 234 235 /* Build new statement to assign EXPR to new variable. */ 236 stmt = gimple_build_assign (var, expr); 237 238 /* Get SSA name for the new variable and set make new statement 239 its definition statement. */ 240 new_name = make_ssa_name (var, stmt); 241 gimple_assign_set_lhs (stmt, new_name); 242 SSA_NAME_DEF_STMT (new_name) = stmt; 243 update_stmt (stmt); 244 245 gsi_insert_before (gsi, stmt, GSI_SAME_STMT); 246 return gimple_assign_lhs (stmt); 247 } 248 249 /* Return true when COND is a true predicate. */ 250 251 static inline bool 252 is_true_predicate (tree cond) 253 { 254 return (cond == NULL_TREE 255 || cond == boolean_true_node 256 || integer_onep (cond)); 257 } 258 259 /* Returns true when BB has a predicate that is not trivial: true or 260 NULL_TREE. */ 261 262 static inline bool 263 is_predicated (basic_block bb) 264 { 265 return !is_true_predicate (bb_predicate (bb)); 266 } 267 268 /* Parses the predicate COND and returns its comparison code and 269 operands OP0 and OP1. */ 270 271 static enum tree_code 272 parse_predicate (tree cond, tree *op0, tree *op1) 273 { 274 gimple s; 275 276 if (TREE_CODE (cond) == SSA_NAME 277 && is_gimple_assign (s = SSA_NAME_DEF_STMT (cond))) 278 { 279 if (TREE_CODE_CLASS (gimple_assign_rhs_code (s)) == tcc_comparison) 280 { 281 *op0 = gimple_assign_rhs1 (s); 282 *op1 = gimple_assign_rhs2 (s); 283 return gimple_assign_rhs_code (s); 284 } 285 286 else if (gimple_assign_rhs_code (s) == TRUTH_NOT_EXPR) 287 { 288 tree op = gimple_assign_rhs1 (s); 289 tree type = TREE_TYPE (op); 290 enum tree_code code = parse_predicate (op, op0, op1); 291 292 return code == ERROR_MARK ? ERROR_MARK 293 : invert_tree_comparison (code, HONOR_NANS (TYPE_MODE (type))); 294 } 295 296 return ERROR_MARK; 297 } 298 299 if (TREE_CODE_CLASS (TREE_CODE (cond)) == tcc_comparison) 300 { 301 *op0 = TREE_OPERAND (cond, 0); 302 *op1 = TREE_OPERAND (cond, 1); 303 return TREE_CODE (cond); 304 } 305 306 return ERROR_MARK; 307 } 308 309 /* Returns the fold of predicate C1 OR C2 at location LOC. */ 310 311 static tree 312 fold_or_predicates (location_t loc, tree c1, tree c2) 313 { 314 tree op1a, op1b, op2a, op2b; 315 enum tree_code code1 = parse_predicate (c1, &op1a, &op1b); 316 enum tree_code code2 = parse_predicate (c2, &op2a, &op2b); 317 318 if (code1 != ERROR_MARK && code2 != ERROR_MARK) 319 { 320 tree t = maybe_fold_or_comparisons (code1, op1a, op1b, 321 code2, op2a, op2b); 322 if (t) 323 return t; 324 } 325 326 return fold_build2_loc (loc, TRUTH_OR_EXPR, boolean_type_node, c1, c2); 327 } 328 329 /* Add condition NC to the predicate list of basic block BB. */ 330 331 static inline void 332 add_to_predicate_list (basic_block bb, tree nc) 333 { 334 tree bc, *tp; 335 336 if (is_true_predicate (nc)) 337 return; 338 339 if (!is_predicated (bb)) 340 bc = nc; 341 else 342 { 343 bc = bb_predicate (bb); 344 bc = fold_or_predicates (EXPR_LOCATION (bc), nc, bc); 345 if (is_true_predicate (bc)) 346 { 347 reset_bb_predicate (bb); 348 return; 349 } 350 } 351 352 /* Allow a TRUTH_NOT_EXPR around the main predicate. */ 353 if (TREE_CODE (bc) == TRUTH_NOT_EXPR) 354 tp = &TREE_OPERAND (bc, 0); 355 else 356 tp = &bc; 357 if (!is_gimple_condexpr (*tp)) 358 { 359 gimple_seq stmts; 360 *tp = force_gimple_operand_1 (*tp, &stmts, is_gimple_condexpr, NULL_TREE); 361 add_bb_predicate_gimplified_stmts (bb, stmts); 362 } 363 set_bb_predicate (bb, bc); 364 } 365 366 /* Add the condition COND to the previous condition PREV_COND, and add 367 this to the predicate list of the destination of edge E. LOOP is 368 the loop to be if-converted. */ 369 370 static void 371 add_to_dst_predicate_list (struct loop *loop, edge e, 372 tree prev_cond, tree cond) 373 { 374 if (!flow_bb_inside_loop_p (loop, e->dest)) 375 return; 376 377 if (!is_true_predicate (prev_cond)) 378 cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, 379 prev_cond, cond); 380 381 add_to_predicate_list (e->dest, cond); 382 } 383 384 /* Return true if one of the successor edges of BB exits LOOP. */ 385 386 static bool 387 bb_with_exit_edge_p (struct loop *loop, basic_block bb) 388 { 389 edge e; 390 edge_iterator ei; 391 392 FOR_EACH_EDGE (e, ei, bb->succs) 393 if (loop_exit_edge_p (loop, e)) 394 return true; 395 396 return false; 397 } 398 399 /* Return true when PHI is if-convertible. PHI is part of loop LOOP 400 and it belongs to basic block BB. 401 402 PHI is not if-convertible if: 403 - it has more than 2 arguments. 404 405 When the flag_tree_loop_if_convert_stores is not set, PHI is not 406 if-convertible if: 407 - a virtual PHI is immediately used in another PHI node, 408 - there is a virtual PHI in a BB other than the loop->header. */ 409 410 static bool 411 if_convertible_phi_p (struct loop *loop, basic_block bb, gimple phi) 412 { 413 if (dump_file && (dump_flags & TDF_DETAILS)) 414 { 415 fprintf (dump_file, "-------------------------\n"); 416 print_gimple_stmt (dump_file, phi, 0, TDF_SLIM); 417 } 418 419 if (bb != loop->header && gimple_phi_num_args (phi) != 2) 420 { 421 if (dump_file && (dump_flags & TDF_DETAILS)) 422 fprintf (dump_file, "More than two phi node args.\n"); 423 return false; 424 } 425 426 if (flag_tree_loop_if_convert_stores) 427 return true; 428 429 /* When the flag_tree_loop_if_convert_stores is not set, check 430 that there are no memory writes in the branches of the loop to be 431 if-converted. */ 432 if (!is_gimple_reg (SSA_NAME_VAR (gimple_phi_result (phi)))) 433 { 434 imm_use_iterator imm_iter; 435 use_operand_p use_p; 436 437 if (bb != loop->header) 438 { 439 if (dump_file && (dump_flags & TDF_DETAILS)) 440 fprintf (dump_file, "Virtual phi not on loop->header.\n"); 441 return false; 442 } 443 444 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, gimple_phi_result (phi)) 445 { 446 if (gimple_code (USE_STMT (use_p)) == GIMPLE_PHI) 447 { 448 if (dump_file && (dump_flags & TDF_DETAILS)) 449 fprintf (dump_file, "Difficult to handle this virtual phi.\n"); 450 return false; 451 } 452 } 453 } 454 455 return true; 456 } 457 458 /* Records the status of a data reference. This struct is attached to 459 each DR->aux field. */ 460 461 struct ifc_dr { 462 /* -1 when not initialized, 0 when false, 1 when true. */ 463 int written_at_least_once; 464 465 /* -1 when not initialized, 0 when false, 1 when true. */ 466 int rw_unconditionally; 467 }; 468 469 #define IFC_DR(DR) ((struct ifc_dr *) (DR)->aux) 470 #define DR_WRITTEN_AT_LEAST_ONCE(DR) (IFC_DR (DR)->written_at_least_once) 471 #define DR_RW_UNCONDITIONALLY(DR) (IFC_DR (DR)->rw_unconditionally) 472 473 /* Returns true when the memory references of STMT are read or written 474 unconditionally. In other words, this function returns true when 475 for every data reference A in STMT there exist other accesses to 476 a data reference with the same base with predicates that add up (OR-up) to 477 the true predicate: this ensures that the data reference A is touched 478 (read or written) on every iteration of the if-converted loop. */ 479 480 static bool 481 memrefs_read_or_written_unconditionally (gimple stmt, 482 VEC (data_reference_p, heap) *drs) 483 { 484 int i, j; 485 data_reference_p a, b; 486 tree ca = bb_predicate (gimple_bb (stmt)); 487 488 for (i = 0; VEC_iterate (data_reference_p, drs, i, a); i++) 489 if (DR_STMT (a) == stmt) 490 { 491 bool found = false; 492 int x = DR_RW_UNCONDITIONALLY (a); 493 494 if (x == 0) 495 return false; 496 497 if (x == 1) 498 continue; 499 500 for (j = 0; VEC_iterate (data_reference_p, drs, j, b); j++) 501 { 502 tree ref_base_a = DR_REF (a); 503 tree ref_base_b = DR_REF (b); 504 505 if (DR_STMT (b) == stmt) 506 continue; 507 508 while (TREE_CODE (ref_base_a) == COMPONENT_REF 509 || TREE_CODE (ref_base_a) == IMAGPART_EXPR 510 || TREE_CODE (ref_base_a) == REALPART_EXPR) 511 ref_base_a = TREE_OPERAND (ref_base_a, 0); 512 513 while (TREE_CODE (ref_base_b) == COMPONENT_REF 514 || TREE_CODE (ref_base_b) == IMAGPART_EXPR 515 || TREE_CODE (ref_base_b) == REALPART_EXPR) 516 ref_base_b = TREE_OPERAND (ref_base_b, 0); 517 518 if (!operand_equal_p (ref_base_a, ref_base_b, 0)) 519 { 520 tree cb = bb_predicate (gimple_bb (DR_STMT (b))); 521 522 if (DR_RW_UNCONDITIONALLY (b) == 1 523 || is_true_predicate (cb) 524 || is_true_predicate (ca 525 = fold_or_predicates (EXPR_LOCATION (cb), ca, cb))) 526 { 527 DR_RW_UNCONDITIONALLY (a) = 1; 528 DR_RW_UNCONDITIONALLY (b) = 1; 529 found = true; 530 break; 531 } 532 } 533 } 534 535 if (!found) 536 { 537 DR_RW_UNCONDITIONALLY (a) = 0; 538 return false; 539 } 540 } 541 542 return true; 543 } 544 545 /* Returns true when the memory references of STMT are unconditionally 546 written. In other words, this function returns true when for every 547 data reference A written in STMT, there exist other writes to the 548 same data reference with predicates that add up (OR-up) to the true 549 predicate: this ensures that the data reference A is written on 550 every iteration of the if-converted loop. */ 551 552 static bool 553 write_memrefs_written_at_least_once (gimple stmt, 554 VEC (data_reference_p, heap) *drs) 555 { 556 int i, j; 557 data_reference_p a, b; 558 tree ca = bb_predicate (gimple_bb (stmt)); 559 560 for (i = 0; VEC_iterate (data_reference_p, drs, i, a); i++) 561 if (DR_STMT (a) == stmt 562 && DR_IS_WRITE (a)) 563 { 564 bool found = false; 565 int x = DR_WRITTEN_AT_LEAST_ONCE (a); 566 567 if (x == 0) 568 return false; 569 570 if (x == 1) 571 continue; 572 573 for (j = 0; VEC_iterate (data_reference_p, drs, j, b); j++) 574 if (DR_STMT (b) != stmt 575 && DR_IS_WRITE (b) 576 && same_data_refs_base_objects (a, b)) 577 { 578 tree cb = bb_predicate (gimple_bb (DR_STMT (b))); 579 580 if (DR_WRITTEN_AT_LEAST_ONCE (b) == 1 581 || is_true_predicate (cb) 582 || is_true_predicate (ca = fold_or_predicates (EXPR_LOCATION (cb), 583 ca, cb))) 584 { 585 DR_WRITTEN_AT_LEAST_ONCE (a) = 1; 586 DR_WRITTEN_AT_LEAST_ONCE (b) = 1; 587 found = true; 588 break; 589 } 590 } 591 592 if (!found) 593 { 594 DR_WRITTEN_AT_LEAST_ONCE (a) = 0; 595 return false; 596 } 597 } 598 599 return true; 600 } 601 602 /* Return true when the memory references of STMT won't trap in the 603 if-converted code. There are two things that we have to check for: 604 605 - writes to memory occur to writable memory: if-conversion of 606 memory writes transforms the conditional memory writes into 607 unconditional writes, i.e. "if (cond) A[i] = foo" is transformed 608 into "A[i] = cond ? foo : A[i]", and as the write to memory may not 609 be executed at all in the original code, it may be a readonly 610 memory. To check that A is not const-qualified, we check that 611 there exists at least an unconditional write to A in the current 612 function. 613 614 - reads or writes to memory are valid memory accesses for every 615 iteration. To check that the memory accesses are correctly formed 616 and that we are allowed to read and write in these locations, we 617 check that the memory accesses to be if-converted occur at every 618 iteration unconditionally. */ 619 620 static bool 621 ifcvt_memrefs_wont_trap (gimple stmt, VEC (data_reference_p, heap) *refs) 622 { 623 return write_memrefs_written_at_least_once (stmt, refs) 624 && memrefs_read_or_written_unconditionally (stmt, refs); 625 } 626 627 /* Wrapper around gimple_could_trap_p refined for the needs of the 628 if-conversion. Try to prove that the memory accesses of STMT could 629 not trap in the innermost loop containing STMT. */ 630 631 static bool 632 ifcvt_could_trap_p (gimple stmt, VEC (data_reference_p, heap) *refs) 633 { 634 if (gimple_vuse (stmt) 635 && !gimple_could_trap_p_1 (stmt, false, false) 636 && ifcvt_memrefs_wont_trap (stmt, refs)) 637 return false; 638 639 return gimple_could_trap_p (stmt); 640 } 641 642 /* Return true when STMT is if-convertible. 643 644 GIMPLE_ASSIGN statement is not if-convertible if, 645 - it is not movable, 646 - it could trap, 647 - LHS is not var decl. */ 648 649 static bool 650 if_convertible_gimple_assign_stmt_p (gimple stmt, 651 VEC (data_reference_p, heap) *refs) 652 { 653 tree lhs = gimple_assign_lhs (stmt); 654 basic_block bb; 655 656 if (dump_file && (dump_flags & TDF_DETAILS)) 657 { 658 fprintf (dump_file, "-------------------------\n"); 659 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 660 } 661 662 if (!is_gimple_reg_type (TREE_TYPE (lhs))) 663 return false; 664 665 /* Some of these constrains might be too conservative. */ 666 if (stmt_ends_bb_p (stmt) 667 || gimple_has_volatile_ops (stmt) 668 || (TREE_CODE (lhs) == SSA_NAME 669 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs)) 670 || gimple_has_side_effects (stmt)) 671 { 672 if (dump_file && (dump_flags & TDF_DETAILS)) 673 fprintf (dump_file, "stmt not suitable for ifcvt\n"); 674 return false; 675 } 676 677 if (flag_tree_loop_if_convert_stores) 678 { 679 if (ifcvt_could_trap_p (stmt, refs)) 680 { 681 if (dump_file && (dump_flags & TDF_DETAILS)) 682 fprintf (dump_file, "tree could trap...\n"); 683 return false; 684 } 685 return true; 686 } 687 688 if (gimple_assign_rhs_could_trap_p (stmt)) 689 { 690 if (dump_file && (dump_flags & TDF_DETAILS)) 691 fprintf (dump_file, "tree could trap...\n"); 692 return false; 693 } 694 695 bb = gimple_bb (stmt); 696 697 if (TREE_CODE (lhs) != SSA_NAME 698 && bb != bb->loop_father->header 699 && !bb_with_exit_edge_p (bb->loop_father, bb)) 700 { 701 if (dump_file && (dump_flags & TDF_DETAILS)) 702 { 703 fprintf (dump_file, "LHS is not var\n"); 704 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 705 } 706 return false; 707 } 708 709 return true; 710 } 711 712 /* Return true when STMT is if-convertible. 713 714 A statement is if-convertible if: 715 - it is an if-convertible GIMPLE_ASSGIN, 716 - it is a GIMPLE_LABEL or a GIMPLE_COND. */ 717 718 static bool 719 if_convertible_stmt_p (gimple stmt, VEC (data_reference_p, heap) *refs) 720 { 721 switch (gimple_code (stmt)) 722 { 723 case GIMPLE_LABEL: 724 case GIMPLE_DEBUG: 725 case GIMPLE_COND: 726 return true; 727 728 case GIMPLE_ASSIGN: 729 return if_convertible_gimple_assign_stmt_p (stmt, refs); 730 731 case GIMPLE_CALL: 732 { 733 tree fndecl = gimple_call_fndecl (stmt); 734 if (fndecl) 735 { 736 int flags = gimple_call_flags (stmt); 737 if ((flags & ECF_CONST) 738 && !(flags & ECF_LOOPING_CONST_OR_PURE) 739 /* We can only vectorize some builtins at the moment, 740 so restrict if-conversion to those. */ 741 && DECL_BUILT_IN (fndecl)) 742 return true; 743 } 744 return false; 745 } 746 747 default: 748 /* Don't know what to do with 'em so don't do anything. */ 749 if (dump_file && (dump_flags & TDF_DETAILS)) 750 { 751 fprintf (dump_file, "don't know what to do\n"); 752 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 753 } 754 return false; 755 break; 756 } 757 758 return true; 759 } 760 761 /* Return true when BB post-dominates all its predecessors. */ 762 763 static bool 764 bb_postdominates_preds (basic_block bb) 765 { 766 unsigned i; 767 768 for (i = 0; i < EDGE_COUNT (bb->preds); i++) 769 if (!dominated_by_p (CDI_POST_DOMINATORS, EDGE_PRED (bb, i)->src, bb)) 770 return false; 771 772 return true; 773 } 774 775 /* Return true when BB is if-convertible. This routine does not check 776 basic block's statements and phis. 777 778 A basic block is not if-convertible if: 779 - it is non-empty and it is after the exit block (in BFS order), 780 - it is after the exit block but before the latch, 781 - its edges are not normal. 782 783 EXIT_BB is the basic block containing the exit of the LOOP. BB is 784 inside LOOP. */ 785 786 static bool 787 if_convertible_bb_p (struct loop *loop, basic_block bb, basic_block exit_bb) 788 { 789 edge e; 790 edge_iterator ei; 791 792 if (dump_file && (dump_flags & TDF_DETAILS)) 793 fprintf (dump_file, "----------[%d]-------------\n", bb->index); 794 795 if (EDGE_COUNT (bb->preds) > 2 796 || EDGE_COUNT (bb->succs) > 2) 797 return false; 798 799 if (exit_bb) 800 { 801 if (bb != loop->latch) 802 { 803 if (dump_file && (dump_flags & TDF_DETAILS)) 804 fprintf (dump_file, "basic block after exit bb but before latch\n"); 805 return false; 806 } 807 else if (!empty_block_p (bb)) 808 { 809 if (dump_file && (dump_flags & TDF_DETAILS)) 810 fprintf (dump_file, "non empty basic block after exit bb\n"); 811 return false; 812 } 813 else if (bb == loop->latch 814 && bb != exit_bb 815 && !dominated_by_p (CDI_DOMINATORS, bb, exit_bb)) 816 { 817 if (dump_file && (dump_flags & TDF_DETAILS)) 818 fprintf (dump_file, "latch is not dominated by exit_block\n"); 819 return false; 820 } 821 } 822 823 /* Be less adventurous and handle only normal edges. */ 824 FOR_EACH_EDGE (e, ei, bb->succs) 825 if (e->flags & 826 (EDGE_ABNORMAL_CALL | EDGE_EH | EDGE_ABNORMAL | EDGE_IRREDUCIBLE_LOOP)) 827 { 828 if (dump_file && (dump_flags & TDF_DETAILS)) 829 fprintf (dump_file, "Difficult to handle edges\n"); 830 return false; 831 } 832 833 if (EDGE_COUNT (bb->preds) == 2 834 && bb != loop->header 835 && !bb_postdominates_preds (bb)) 836 return false; 837 838 return true; 839 } 840 841 /* Return true when all predecessor blocks of BB are visited. The 842 VISITED bitmap keeps track of the visited blocks. */ 843 844 static bool 845 pred_blocks_visited_p (basic_block bb, bitmap *visited) 846 { 847 edge e; 848 edge_iterator ei; 849 FOR_EACH_EDGE (e, ei, bb->preds) 850 if (!bitmap_bit_p (*visited, e->src->index)) 851 return false; 852 853 return true; 854 } 855 856 /* Get body of a LOOP in suitable order for if-conversion. It is 857 caller's responsibility to deallocate basic block list. 858 If-conversion suitable order is, breadth first sort (BFS) order 859 with an additional constraint: select a block only if all its 860 predecessors are already selected. */ 861 862 static basic_block * 863 get_loop_body_in_if_conv_order (const struct loop *loop) 864 { 865 basic_block *blocks, *blocks_in_bfs_order; 866 basic_block bb; 867 bitmap visited; 868 unsigned int index = 0; 869 unsigned int visited_count = 0; 870 871 gcc_assert (loop->num_nodes); 872 gcc_assert (loop->latch != EXIT_BLOCK_PTR); 873 874 blocks = XCNEWVEC (basic_block, loop->num_nodes); 875 visited = BITMAP_ALLOC (NULL); 876 877 blocks_in_bfs_order = get_loop_body_in_bfs_order (loop); 878 879 index = 0; 880 while (index < loop->num_nodes) 881 { 882 bb = blocks_in_bfs_order [index]; 883 884 if (bb->flags & BB_IRREDUCIBLE_LOOP) 885 { 886 free (blocks_in_bfs_order); 887 BITMAP_FREE (visited); 888 free (blocks); 889 return NULL; 890 } 891 892 if (!bitmap_bit_p (visited, bb->index)) 893 { 894 if (pred_blocks_visited_p (bb, &visited) 895 || bb == loop->header) 896 { 897 /* This block is now visited. */ 898 bitmap_set_bit (visited, bb->index); 899 blocks[visited_count++] = bb; 900 } 901 } 902 903 index++; 904 905 if (index == loop->num_nodes 906 && visited_count != loop->num_nodes) 907 /* Not done yet. */ 908 index = 0; 909 } 910 free (blocks_in_bfs_order); 911 BITMAP_FREE (visited); 912 return blocks; 913 } 914 915 /* Returns true when the analysis of the predicates for all the basic 916 blocks in LOOP succeeded. 917 918 predicate_bbs first allocates the predicates of the basic blocks. 919 These fields are then initialized with the tree expressions 920 representing the predicates under which a basic block is executed 921 in the LOOP. As the loop->header is executed at each iteration, it 922 has the "true" predicate. Other statements executed under a 923 condition are predicated with that condition, for example 924 925 | if (x) 926 | S1; 927 | else 928 | S2; 929 930 S1 will be predicated with "x", and 931 S2 will be predicated with "!x". */ 932 933 static bool 934 predicate_bbs (loop_p loop) 935 { 936 unsigned int i; 937 938 for (i = 0; i < loop->num_nodes; i++) 939 init_bb_predicate (ifc_bbs[i]); 940 941 for (i = 0; i < loop->num_nodes; i++) 942 { 943 basic_block bb = ifc_bbs[i]; 944 tree cond; 945 gimple_stmt_iterator itr; 946 947 /* The loop latch is always executed and has no extra conditions 948 to be processed: skip it. */ 949 if (bb == loop->latch) 950 { 951 reset_bb_predicate (loop->latch); 952 continue; 953 } 954 955 cond = bb_predicate (bb); 956 957 for (itr = gsi_start_bb (bb); !gsi_end_p (itr); gsi_next (&itr)) 958 { 959 gimple stmt = gsi_stmt (itr); 960 961 switch (gimple_code (stmt)) 962 { 963 case GIMPLE_LABEL: 964 case GIMPLE_ASSIGN: 965 case GIMPLE_CALL: 966 case GIMPLE_DEBUG: 967 break; 968 969 case GIMPLE_COND: 970 { 971 tree c2, tem; 972 edge true_edge, false_edge; 973 location_t loc = gimple_location (stmt); 974 tree c = fold_build2_loc (loc, gimple_cond_code (stmt), 975 boolean_type_node, 976 gimple_cond_lhs (stmt), 977 gimple_cond_rhs (stmt)); 978 979 /* Add new condition into destination's predicate list. */ 980 extract_true_false_edges_from_block (gimple_bb (stmt), 981 &true_edge, &false_edge); 982 983 /* If C is true, then TRUE_EDGE is taken. */ 984 add_to_dst_predicate_list (loop, true_edge, 985 unshare_expr (cond), 986 unshare_expr (c)); 987 988 /* If C is false, then FALSE_EDGE is taken. */ 989 c2 = invert_truthvalue_loc (loc, unshare_expr (c)); 990 tem = canonicalize_cond_expr_cond (c2); 991 if (tem) 992 c2 = tem; 993 add_to_dst_predicate_list (loop, false_edge, 994 unshare_expr (cond), c2); 995 996 cond = NULL_TREE; 997 break; 998 } 999 1000 default: 1001 /* Not handled yet in if-conversion. */ 1002 return false; 1003 } 1004 } 1005 1006 /* If current bb has only one successor, then consider it as an 1007 unconditional goto. */ 1008 if (single_succ_p (bb)) 1009 { 1010 basic_block bb_n = single_succ (bb); 1011 1012 /* The successor bb inherits the predicate of its 1013 predecessor. If there is no predicate in the predecessor 1014 bb, then consider the successor bb as always executed. */ 1015 if (cond == NULL_TREE) 1016 cond = boolean_true_node; 1017 1018 add_to_predicate_list (bb_n, cond); 1019 } 1020 } 1021 1022 /* The loop header is always executed. */ 1023 reset_bb_predicate (loop->header); 1024 gcc_assert (bb_predicate_gimplified_stmts (loop->header) == NULL 1025 && bb_predicate_gimplified_stmts (loop->latch) == NULL); 1026 1027 return true; 1028 } 1029 1030 /* Return true when LOOP is if-convertible. This is a helper function 1031 for if_convertible_loop_p. REFS and DDRS are initialized and freed 1032 in if_convertible_loop_p. */ 1033 1034 static bool 1035 if_convertible_loop_p_1 (struct loop *loop, 1036 VEC (loop_p, heap) **loop_nest, 1037 VEC (data_reference_p, heap) **refs, 1038 VEC (ddr_p, heap) **ddrs) 1039 { 1040 bool res; 1041 unsigned int i; 1042 basic_block exit_bb = NULL; 1043 1044 /* Don't if-convert the loop when the data dependences cannot be 1045 computed: the loop won't be vectorized in that case. */ 1046 res = compute_data_dependences_for_loop (loop, true, loop_nest, refs, ddrs); 1047 if (!res) 1048 return false; 1049 1050 calculate_dominance_info (CDI_DOMINATORS); 1051 calculate_dominance_info (CDI_POST_DOMINATORS); 1052 1053 /* Allow statements that can be handled during if-conversion. */ 1054 ifc_bbs = get_loop_body_in_if_conv_order (loop); 1055 if (!ifc_bbs) 1056 { 1057 if (dump_file && (dump_flags & TDF_DETAILS)) 1058 fprintf (dump_file, "Irreducible loop\n"); 1059 return false; 1060 } 1061 1062 for (i = 0; i < loop->num_nodes; i++) 1063 { 1064 basic_block bb = ifc_bbs[i]; 1065 1066 if (!if_convertible_bb_p (loop, bb, exit_bb)) 1067 return false; 1068 1069 if (bb_with_exit_edge_p (loop, bb)) 1070 exit_bb = bb; 1071 } 1072 1073 res = predicate_bbs (loop); 1074 if (!res) 1075 return false; 1076 1077 if (flag_tree_loop_if_convert_stores) 1078 { 1079 data_reference_p dr; 1080 1081 for (i = 0; VEC_iterate (data_reference_p, *refs, i, dr); i++) 1082 { 1083 dr->aux = XNEW (struct ifc_dr); 1084 DR_WRITTEN_AT_LEAST_ONCE (dr) = -1; 1085 DR_RW_UNCONDITIONALLY (dr) = -1; 1086 } 1087 } 1088 1089 for (i = 0; i < loop->num_nodes; i++) 1090 { 1091 basic_block bb = ifc_bbs[i]; 1092 gimple_stmt_iterator itr; 1093 1094 for (itr = gsi_start_phis (bb); !gsi_end_p (itr); gsi_next (&itr)) 1095 if (!if_convertible_phi_p (loop, bb, gsi_stmt (itr))) 1096 return false; 1097 1098 /* Check the if-convertibility of statements in predicated BBs. */ 1099 if (is_predicated (bb)) 1100 for (itr = gsi_start_bb (bb); !gsi_end_p (itr); gsi_next (&itr)) 1101 if (!if_convertible_stmt_p (gsi_stmt (itr), *refs)) 1102 return false; 1103 } 1104 1105 if (dump_file) 1106 fprintf (dump_file, "Applying if-conversion\n"); 1107 1108 return true; 1109 } 1110 1111 /* Return true when LOOP is if-convertible. 1112 LOOP is if-convertible if: 1113 - it is innermost, 1114 - it has two or more basic blocks, 1115 - it has only one exit, 1116 - loop header is not the exit edge, 1117 - if its basic blocks and phi nodes are if convertible. */ 1118 1119 static bool 1120 if_convertible_loop_p (struct loop *loop) 1121 { 1122 edge e; 1123 edge_iterator ei; 1124 bool res = false; 1125 VEC (data_reference_p, heap) *refs; 1126 VEC (ddr_p, heap) *ddrs; 1127 VEC (loop_p, heap) *loop_nest; 1128 1129 /* Handle only innermost loop. */ 1130 if (!loop || loop->inner) 1131 { 1132 if (dump_file && (dump_flags & TDF_DETAILS)) 1133 fprintf (dump_file, "not innermost loop\n"); 1134 return false; 1135 } 1136 1137 /* If only one block, no need for if-conversion. */ 1138 if (loop->num_nodes <= 2) 1139 { 1140 if (dump_file && (dump_flags & TDF_DETAILS)) 1141 fprintf (dump_file, "less than 2 basic blocks\n"); 1142 return false; 1143 } 1144 1145 /* More than one loop exit is too much to handle. */ 1146 if (!single_exit (loop)) 1147 { 1148 if (dump_file && (dump_flags & TDF_DETAILS)) 1149 fprintf (dump_file, "multiple exits\n"); 1150 return false; 1151 } 1152 1153 /* If one of the loop header's edge is an exit edge then do not 1154 apply if-conversion. */ 1155 FOR_EACH_EDGE (e, ei, loop->header->succs) 1156 if (loop_exit_edge_p (loop, e)) 1157 return false; 1158 1159 refs = VEC_alloc (data_reference_p, heap, 5); 1160 ddrs = VEC_alloc (ddr_p, heap, 25); 1161 loop_nest = VEC_alloc (loop_p, heap, 3); 1162 res = if_convertible_loop_p_1 (loop, &loop_nest, &refs, &ddrs); 1163 1164 if (flag_tree_loop_if_convert_stores) 1165 { 1166 data_reference_p dr; 1167 unsigned int i; 1168 1169 for (i = 0; VEC_iterate (data_reference_p, refs, i, dr); i++) 1170 free (dr->aux); 1171 } 1172 1173 VEC_free (loop_p, heap, loop_nest); 1174 free_data_refs (refs); 1175 free_dependence_relations (ddrs); 1176 return res; 1177 } 1178 1179 /* Basic block BB has two predecessors. Using predecessor's bb 1180 predicate, set an appropriate condition COND for the PHI node 1181 replacement. Return the true block whose phi arguments are 1182 selected when cond is true. LOOP is the loop containing the 1183 if-converted region, GSI is the place to insert the code for the 1184 if-conversion. */ 1185 1186 static basic_block 1187 find_phi_replacement_condition (struct loop *loop, 1188 basic_block bb, tree *cond, 1189 gimple_stmt_iterator *gsi) 1190 { 1191 edge first_edge, second_edge; 1192 tree tmp_cond; 1193 1194 gcc_assert (EDGE_COUNT (bb->preds) == 2); 1195 first_edge = EDGE_PRED (bb, 0); 1196 second_edge = EDGE_PRED (bb, 1); 1197 1198 /* Use condition based on following criteria: 1199 1) 1200 S1: x = !c ? a : b; 1201 1202 S2: x = c ? b : a; 1203 1204 S2 is preferred over S1. Make 'b' first_bb and use its condition. 1205 1206 2) Do not make loop header first_bb. 1207 1208 3) 1209 S1: x = !(c == d)? a : b; 1210 1211 S21: t1 = c == d; 1212 S22: x = t1 ? b : a; 1213 1214 S3: x = (c == d) ? b : a; 1215 1216 S3 is preferred over S1 and S2*, Make 'b' first_bb and use 1217 its condition. 1218 1219 4) If pred B is dominated by pred A then use pred B's condition. 1220 See PR23115. */ 1221 1222 /* Select condition that is not TRUTH_NOT_EXPR. */ 1223 tmp_cond = bb_predicate (first_edge->src); 1224 gcc_assert (tmp_cond); 1225 1226 if (TREE_CODE (tmp_cond) == TRUTH_NOT_EXPR) 1227 { 1228 edge tmp_edge; 1229 1230 tmp_edge = first_edge; 1231 first_edge = second_edge; 1232 second_edge = tmp_edge; 1233 } 1234 1235 /* Check if FIRST_BB is loop header or not and make sure that 1236 FIRST_BB does not dominate SECOND_BB. */ 1237 if (first_edge->src == loop->header 1238 || dominated_by_p (CDI_DOMINATORS, 1239 second_edge->src, first_edge->src)) 1240 { 1241 *cond = bb_predicate (second_edge->src); 1242 1243 if (TREE_CODE (*cond) == TRUTH_NOT_EXPR) 1244 *cond = TREE_OPERAND (*cond, 0); 1245 else 1246 /* Select non loop header bb. */ 1247 first_edge = second_edge; 1248 } 1249 else 1250 *cond = bb_predicate (first_edge->src); 1251 1252 /* Gimplify the condition to a valid cond-expr conditonal operand. */ 1253 *cond = force_gimple_operand_gsi_1 (gsi, unshare_expr (*cond), 1254 is_gimple_condexpr, NULL_TREE, 1255 true, GSI_SAME_STMT); 1256 1257 return first_edge->src; 1258 } 1259 1260 /* Replace a scalar PHI node with a COND_EXPR using COND as condition. 1261 This routine does not handle PHI nodes with more than two 1262 arguments. 1263 1264 For example, 1265 S1: A = PHI <x1(1), x2(5)> 1266 is converted into, 1267 S2: A = cond ? x1 : x2; 1268 1269 The generated code is inserted at GSI that points to the top of 1270 basic block's statement list. When COND is true, phi arg from 1271 TRUE_BB is selected. */ 1272 1273 static void 1274 predicate_scalar_phi (gimple phi, tree cond, 1275 basic_block true_bb, 1276 gimple_stmt_iterator *gsi) 1277 { 1278 gimple new_stmt; 1279 basic_block bb; 1280 tree rhs, res, arg, scev; 1281 1282 gcc_assert (gimple_code (phi) == GIMPLE_PHI 1283 && gimple_phi_num_args (phi) == 2); 1284 1285 res = gimple_phi_result (phi); 1286 /* Do not handle virtual phi nodes. */ 1287 if (!is_gimple_reg (SSA_NAME_VAR (res))) 1288 return; 1289 1290 bb = gimple_bb (phi); 1291 1292 if ((arg = degenerate_phi_result (phi)) 1293 || ((scev = analyze_scalar_evolution (gimple_bb (phi)->loop_father, 1294 res)) 1295 && !chrec_contains_undetermined (scev) 1296 && scev != res 1297 && (arg = gimple_phi_arg_def (phi, 0)))) 1298 rhs = arg; 1299 else 1300 { 1301 tree arg_0, arg_1; 1302 /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr. */ 1303 if (EDGE_PRED (bb, 1)->src == true_bb) 1304 { 1305 arg_0 = gimple_phi_arg_def (phi, 1); 1306 arg_1 = gimple_phi_arg_def (phi, 0); 1307 } 1308 else 1309 { 1310 arg_0 = gimple_phi_arg_def (phi, 0); 1311 arg_1 = gimple_phi_arg_def (phi, 1); 1312 } 1313 1314 gcc_checking_assert (bb == bb->loop_father->header 1315 || bb_postdominates_preds (bb)); 1316 1317 /* Build new RHS using selected condition and arguments. */ 1318 rhs = build3 (COND_EXPR, TREE_TYPE (res), 1319 unshare_expr (cond), arg_0, arg_1); 1320 } 1321 1322 new_stmt = gimple_build_assign (res, rhs); 1323 SSA_NAME_DEF_STMT (gimple_phi_result (phi)) = new_stmt; 1324 gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT); 1325 update_stmt (new_stmt); 1326 1327 if (dump_file && (dump_flags & TDF_DETAILS)) 1328 { 1329 fprintf (dump_file, "new phi replacement stmt\n"); 1330 print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM); 1331 } 1332 } 1333 1334 /* Replaces in LOOP all the scalar phi nodes other than those in the 1335 LOOP->header block with conditional modify expressions. */ 1336 1337 static void 1338 predicate_all_scalar_phis (struct loop *loop) 1339 { 1340 basic_block bb; 1341 unsigned int orig_loop_num_nodes = loop->num_nodes; 1342 unsigned int i; 1343 1344 for (i = 1; i < orig_loop_num_nodes; i++) 1345 { 1346 gimple phi; 1347 tree cond = NULL_TREE; 1348 gimple_stmt_iterator gsi, phi_gsi; 1349 basic_block true_bb = NULL; 1350 bb = ifc_bbs[i]; 1351 1352 if (bb == loop->header) 1353 continue; 1354 1355 phi_gsi = gsi_start_phis (bb); 1356 if (gsi_end_p (phi_gsi)) 1357 continue; 1358 1359 /* BB has two predecessors. Using predecessor's aux field, set 1360 appropriate condition for the PHI node replacement. */ 1361 gsi = gsi_after_labels (bb); 1362 true_bb = find_phi_replacement_condition (loop, bb, &cond, &gsi); 1363 1364 while (!gsi_end_p (phi_gsi)) 1365 { 1366 phi = gsi_stmt (phi_gsi); 1367 predicate_scalar_phi (phi, cond, true_bb, &gsi); 1368 release_phi_node (phi); 1369 gsi_next (&phi_gsi); 1370 } 1371 1372 set_phi_nodes (bb, NULL); 1373 } 1374 } 1375 1376 /* Insert in each basic block of LOOP the statements produced by the 1377 gimplification of the predicates. */ 1378 1379 static void 1380 insert_gimplified_predicates (loop_p loop) 1381 { 1382 unsigned int i; 1383 1384 for (i = 0; i < loop->num_nodes; i++) 1385 { 1386 basic_block bb = ifc_bbs[i]; 1387 gimple_seq stmts; 1388 1389 if (!is_predicated (bb)) 1390 { 1391 /* Do not insert statements for a basic block that is not 1392 predicated. Also make sure that the predicate of the 1393 basic block is set to true. */ 1394 reset_bb_predicate (bb); 1395 continue; 1396 } 1397 1398 stmts = bb_predicate_gimplified_stmts (bb); 1399 if (stmts) 1400 { 1401 if (flag_tree_loop_if_convert_stores) 1402 { 1403 /* Insert the predicate of the BB just after the label, 1404 as the if-conversion of memory writes will use this 1405 predicate. */ 1406 gimple_stmt_iterator gsi = gsi_after_labels (bb); 1407 gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT); 1408 } 1409 else 1410 { 1411 /* Insert the predicate of the BB at the end of the BB 1412 as this would reduce the register pressure: the only 1413 use of this predicate will be in successor BBs. */ 1414 gimple_stmt_iterator gsi = gsi_last_bb (bb); 1415 1416 if (gsi_end_p (gsi) 1417 || stmt_ends_bb_p (gsi_stmt (gsi))) 1418 gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT); 1419 else 1420 gsi_insert_seq_after (&gsi, stmts, GSI_SAME_STMT); 1421 } 1422 1423 /* Once the sequence is code generated, set it to NULL. */ 1424 set_bb_predicate_gimplified_stmts (bb, NULL); 1425 } 1426 } 1427 } 1428 1429 /* Predicate each write to memory in LOOP. 1430 1431 This function transforms control flow constructs containing memory 1432 writes of the form: 1433 1434 | for (i = 0; i < N; i++) 1435 | if (cond) 1436 | A[i] = expr; 1437 1438 into the following form that does not contain control flow: 1439 1440 | for (i = 0; i < N; i++) 1441 | A[i] = cond ? expr : A[i]; 1442 1443 The original CFG looks like this: 1444 1445 | bb_0 1446 | i = 0 1447 | end_bb_0 1448 | 1449 | bb_1 1450 | if (i < N) goto bb_5 else goto bb_2 1451 | end_bb_1 1452 | 1453 | bb_2 1454 | cond = some_computation; 1455 | if (cond) goto bb_3 else goto bb_4 1456 | end_bb_2 1457 | 1458 | bb_3 1459 | A[i] = expr; 1460 | goto bb_4 1461 | end_bb_3 1462 | 1463 | bb_4 1464 | goto bb_1 1465 | end_bb_4 1466 1467 insert_gimplified_predicates inserts the computation of the COND 1468 expression at the beginning of the destination basic block: 1469 1470 | bb_0 1471 | i = 0 1472 | end_bb_0 1473 | 1474 | bb_1 1475 | if (i < N) goto bb_5 else goto bb_2 1476 | end_bb_1 1477 | 1478 | bb_2 1479 | cond = some_computation; 1480 | if (cond) goto bb_3 else goto bb_4 1481 | end_bb_2 1482 | 1483 | bb_3 1484 | cond = some_computation; 1485 | A[i] = expr; 1486 | goto bb_4 1487 | end_bb_3 1488 | 1489 | bb_4 1490 | goto bb_1 1491 | end_bb_4 1492 1493 predicate_mem_writes is then predicating the memory write as follows: 1494 1495 | bb_0 1496 | i = 0 1497 | end_bb_0 1498 | 1499 | bb_1 1500 | if (i < N) goto bb_5 else goto bb_2 1501 | end_bb_1 1502 | 1503 | bb_2 1504 | if (cond) goto bb_3 else goto bb_4 1505 | end_bb_2 1506 | 1507 | bb_3 1508 | cond = some_computation; 1509 | A[i] = cond ? expr : A[i]; 1510 | goto bb_4 1511 | end_bb_3 1512 | 1513 | bb_4 1514 | goto bb_1 1515 | end_bb_4 1516 1517 and finally combine_blocks removes the basic block boundaries making 1518 the loop vectorizable: 1519 1520 | bb_0 1521 | i = 0 1522 | if (i < N) goto bb_5 else goto bb_1 1523 | end_bb_0 1524 | 1525 | bb_1 1526 | cond = some_computation; 1527 | A[i] = cond ? expr : A[i]; 1528 | if (i < N) goto bb_5 else goto bb_4 1529 | end_bb_1 1530 | 1531 | bb_4 1532 | goto bb_1 1533 | end_bb_4 1534 */ 1535 1536 static void 1537 predicate_mem_writes (loop_p loop) 1538 { 1539 unsigned int i, orig_loop_num_nodes = loop->num_nodes; 1540 1541 for (i = 1; i < orig_loop_num_nodes; i++) 1542 { 1543 gimple_stmt_iterator gsi; 1544 basic_block bb = ifc_bbs[i]; 1545 tree cond = bb_predicate (bb); 1546 bool swap; 1547 gimple stmt; 1548 1549 if (is_true_predicate (cond)) 1550 continue; 1551 1552 swap = false; 1553 if (TREE_CODE (cond) == TRUTH_NOT_EXPR) 1554 { 1555 swap = true; 1556 cond = TREE_OPERAND (cond, 0); 1557 } 1558 1559 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 1560 if ((stmt = gsi_stmt (gsi)) 1561 && gimple_assign_single_p (stmt) 1562 && gimple_vdef (stmt)) 1563 { 1564 tree lhs = gimple_assign_lhs (stmt); 1565 tree rhs = gimple_assign_rhs1 (stmt); 1566 tree type = TREE_TYPE (lhs); 1567 1568 lhs = ifc_temp_var (type, unshare_expr (lhs), &gsi); 1569 rhs = ifc_temp_var (type, unshare_expr (rhs), &gsi); 1570 if (swap) 1571 { 1572 tree tem = lhs; 1573 lhs = rhs; 1574 rhs = tem; 1575 } 1576 cond = force_gimple_operand_gsi_1 (&gsi, unshare_expr (cond), 1577 is_gimple_condexpr, NULL_TREE, 1578 true, GSI_SAME_STMT); 1579 rhs = build3 (COND_EXPR, type, unshare_expr (cond), rhs, lhs); 1580 gimple_assign_set_rhs1 (stmt, ifc_temp_var (type, rhs, &gsi)); 1581 update_stmt (stmt); 1582 } 1583 } 1584 } 1585 1586 /* Remove all GIMPLE_CONDs and GIMPLE_LABELs of all the basic blocks 1587 other than the exit and latch of the LOOP. Also resets the 1588 GIMPLE_DEBUG information. */ 1589 1590 static void 1591 remove_conditions_and_labels (loop_p loop) 1592 { 1593 gimple_stmt_iterator gsi; 1594 unsigned int i; 1595 1596 for (i = 0; i < loop->num_nodes; i++) 1597 { 1598 basic_block bb = ifc_bbs[i]; 1599 1600 if (bb_with_exit_edge_p (loop, bb) 1601 || bb == loop->latch) 1602 continue; 1603 1604 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); ) 1605 switch (gimple_code (gsi_stmt (gsi))) 1606 { 1607 case GIMPLE_COND: 1608 case GIMPLE_LABEL: 1609 gsi_remove (&gsi, true); 1610 break; 1611 1612 case GIMPLE_DEBUG: 1613 /* ??? Should there be conditional GIMPLE_DEBUG_BINDs? */ 1614 if (gimple_debug_bind_p (gsi_stmt (gsi))) 1615 { 1616 gimple_debug_bind_reset_value (gsi_stmt (gsi)); 1617 update_stmt (gsi_stmt (gsi)); 1618 } 1619 gsi_next (&gsi); 1620 break; 1621 1622 default: 1623 gsi_next (&gsi); 1624 } 1625 } 1626 } 1627 1628 /* Combine all the basic blocks from LOOP into one or two super basic 1629 blocks. Replace PHI nodes with conditional modify expressions. */ 1630 1631 static void 1632 combine_blocks (struct loop *loop) 1633 { 1634 basic_block bb, exit_bb, merge_target_bb; 1635 unsigned int orig_loop_num_nodes = loop->num_nodes; 1636 unsigned int i; 1637 edge e; 1638 edge_iterator ei; 1639 1640 remove_conditions_and_labels (loop); 1641 insert_gimplified_predicates (loop); 1642 predicate_all_scalar_phis (loop); 1643 1644 if (flag_tree_loop_if_convert_stores) 1645 predicate_mem_writes (loop); 1646 1647 /* Merge basic blocks: first remove all the edges in the loop, 1648 except for those from the exit block. */ 1649 exit_bb = NULL; 1650 for (i = 0; i < orig_loop_num_nodes; i++) 1651 { 1652 bb = ifc_bbs[i]; 1653 free_bb_predicate (bb); 1654 if (bb_with_exit_edge_p (loop, bb)) 1655 { 1656 exit_bb = bb; 1657 break; 1658 } 1659 } 1660 gcc_assert (exit_bb != loop->latch); 1661 1662 for (i = 1; i < orig_loop_num_nodes; i++) 1663 { 1664 bb = ifc_bbs[i]; 1665 1666 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei));) 1667 { 1668 if (e->src == exit_bb) 1669 ei_next (&ei); 1670 else 1671 remove_edge (e); 1672 } 1673 } 1674 1675 if (exit_bb != NULL) 1676 { 1677 if (exit_bb != loop->header) 1678 { 1679 /* Connect this node to loop header. */ 1680 make_edge (loop->header, exit_bb, EDGE_FALLTHRU); 1681 set_immediate_dominator (CDI_DOMINATORS, exit_bb, loop->header); 1682 } 1683 1684 /* Redirect non-exit edges to loop->latch. */ 1685 FOR_EACH_EDGE (e, ei, exit_bb->succs) 1686 { 1687 if (!loop_exit_edge_p (loop, e)) 1688 redirect_edge_and_branch (e, loop->latch); 1689 } 1690 set_immediate_dominator (CDI_DOMINATORS, loop->latch, exit_bb); 1691 } 1692 else 1693 { 1694 /* If the loop does not have an exit, reconnect header and latch. */ 1695 make_edge (loop->header, loop->latch, EDGE_FALLTHRU); 1696 set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header); 1697 } 1698 1699 merge_target_bb = loop->header; 1700 for (i = 1; i < orig_loop_num_nodes; i++) 1701 { 1702 gimple_stmt_iterator gsi; 1703 gimple_stmt_iterator last; 1704 1705 bb = ifc_bbs[i]; 1706 1707 if (bb == exit_bb || bb == loop->latch) 1708 continue; 1709 1710 /* Make stmts member of loop->header. */ 1711 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 1712 gimple_set_bb (gsi_stmt (gsi), merge_target_bb); 1713 1714 /* Update stmt list. */ 1715 last = gsi_last_bb (merge_target_bb); 1716 gsi_insert_seq_after (&last, bb_seq (bb), GSI_NEW_STMT); 1717 set_bb_seq (bb, NULL); 1718 1719 delete_basic_block (bb); 1720 } 1721 1722 /* If possible, merge loop header to the block with the exit edge. 1723 This reduces the number of basic blocks to two, to please the 1724 vectorizer that handles only loops with two nodes. */ 1725 if (exit_bb 1726 && exit_bb != loop->header 1727 && can_merge_blocks_p (loop->header, exit_bb)) 1728 merge_blocks (loop->header, exit_bb); 1729 1730 free (ifc_bbs); 1731 ifc_bbs = NULL; 1732 } 1733 1734 /* If-convert LOOP when it is legal. For the moment this pass has no 1735 profitability analysis. Returns true when something changed. */ 1736 1737 static bool 1738 tree_if_conversion (struct loop *loop) 1739 { 1740 bool changed = false; 1741 ifc_bbs = NULL; 1742 1743 if (!if_convertible_loop_p (loop) 1744 || !dbg_cnt (if_conversion_tree)) 1745 goto cleanup; 1746 1747 /* Now all statements are if-convertible. Combine all the basic 1748 blocks into one huge basic block doing the if-conversion 1749 on-the-fly. */ 1750 combine_blocks (loop); 1751 1752 if (flag_tree_loop_if_convert_stores) 1753 mark_sym_for_renaming (gimple_vop (cfun)); 1754 1755 changed = true; 1756 1757 cleanup: 1758 if (ifc_bbs) 1759 { 1760 unsigned int i; 1761 1762 for (i = 0; i < loop->num_nodes; i++) 1763 free_bb_predicate (ifc_bbs[i]); 1764 1765 free (ifc_bbs); 1766 ifc_bbs = NULL; 1767 } 1768 1769 return changed; 1770 } 1771 1772 /* Tree if-conversion pass management. */ 1773 1774 static unsigned int 1775 main_tree_if_conversion (void) 1776 { 1777 loop_iterator li; 1778 struct loop *loop; 1779 bool changed = false; 1780 unsigned todo = 0; 1781 1782 if (number_of_loops () <= 1) 1783 return 0; 1784 1785 FOR_EACH_LOOP (li, loop, 0) 1786 changed |= tree_if_conversion (loop); 1787 1788 if (changed) 1789 todo |= TODO_cleanup_cfg; 1790 1791 if (changed && flag_tree_loop_if_convert_stores) 1792 todo |= TODO_update_ssa_only_virtuals; 1793 1794 free_dominance_info (CDI_POST_DOMINATORS); 1795 1796 return todo; 1797 } 1798 1799 /* Returns true when the if-conversion pass is enabled. */ 1800 1801 static bool 1802 gate_tree_if_conversion (void) 1803 { 1804 return ((flag_tree_vectorize && flag_tree_loop_if_convert != 0) 1805 || flag_tree_loop_if_convert == 1 1806 || flag_tree_loop_if_convert_stores == 1); 1807 } 1808 1809 struct gimple_opt_pass pass_if_conversion = 1810 { 1811 { 1812 GIMPLE_PASS, 1813 "ifcvt", /* name */ 1814 gate_tree_if_conversion, /* gate */ 1815 main_tree_if_conversion, /* execute */ 1816 NULL, /* sub */ 1817 NULL, /* next */ 1818 0, /* static_pass_number */ 1819 TV_NONE, /* tv_id */ 1820 PROP_cfg | PROP_ssa, /* properties_required */ 1821 0, /* properties_provided */ 1822 0, /* properties_destroyed */ 1823 0, /* todo_flags_start */ 1824 TODO_verify_stmts | TODO_verify_flow 1825 /* todo_flags_finish */ 1826 } 1827 }; 1828