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 is if-convertible. This routine does not check 762 basic block's statements and phis. 763 764 A basic block is not if-convertible if: 765 - it is non-empty and it is after the exit block (in BFS order), 766 - it is after the exit block but before the latch, 767 - its edges are not normal. 768 769 EXIT_BB is the basic block containing the exit of the LOOP. BB is 770 inside LOOP. */ 771 772 static bool 773 if_convertible_bb_p (struct loop *loop, basic_block bb, basic_block exit_bb) 774 { 775 edge e; 776 edge_iterator ei; 777 778 if (dump_file && (dump_flags & TDF_DETAILS)) 779 fprintf (dump_file, "----------[%d]-------------\n", bb->index); 780 781 if (EDGE_COUNT (bb->preds) > 2 782 || EDGE_COUNT (bb->succs) > 2) 783 return false; 784 785 if (exit_bb) 786 { 787 if (bb != loop->latch) 788 { 789 if (dump_file && (dump_flags & TDF_DETAILS)) 790 fprintf (dump_file, "basic block after exit bb but before latch\n"); 791 return false; 792 } 793 else if (!empty_block_p (bb)) 794 { 795 if (dump_file && (dump_flags & TDF_DETAILS)) 796 fprintf (dump_file, "non empty basic block after exit bb\n"); 797 return false; 798 } 799 else if (bb == loop->latch 800 && bb != exit_bb 801 && !dominated_by_p (CDI_DOMINATORS, bb, exit_bb)) 802 { 803 if (dump_file && (dump_flags & TDF_DETAILS)) 804 fprintf (dump_file, "latch is not dominated by exit_block\n"); 805 return false; 806 } 807 } 808 809 /* Be less adventurous and handle only normal edges. */ 810 FOR_EACH_EDGE (e, ei, bb->succs) 811 if (e->flags & 812 (EDGE_ABNORMAL_CALL | EDGE_EH | EDGE_ABNORMAL | EDGE_IRREDUCIBLE_LOOP)) 813 { 814 if (dump_file && (dump_flags & TDF_DETAILS)) 815 fprintf (dump_file, "Difficult to handle edges\n"); 816 return false; 817 } 818 819 /* At least one incoming edge has to be non-critical as otherwise edge 820 predicates are not equal to basic-block predicates of the edge 821 source. */ 822 if (EDGE_COUNT (bb->preds) > 1 823 && bb != loop->header) 824 { 825 bool found = false; 826 FOR_EACH_EDGE (e, ei, bb->preds) 827 if (EDGE_COUNT (e->src->succs) == 1) 828 found = true; 829 if (!found) 830 { 831 if (dump_file && (dump_flags & TDF_DETAILS)) 832 fprintf (dump_file, "only critical predecessors\n"); 833 return false; 834 } 835 } 836 837 return true; 838 } 839 840 /* Return true when all predecessor blocks of BB are visited. The 841 VISITED bitmap keeps track of the visited blocks. */ 842 843 static bool 844 pred_blocks_visited_p (basic_block bb, bitmap *visited) 845 { 846 edge e; 847 edge_iterator ei; 848 FOR_EACH_EDGE (e, ei, bb->preds) 849 if (!bitmap_bit_p (*visited, e->src->index)) 850 return false; 851 852 return true; 853 } 854 855 /* Get body of a LOOP in suitable order for if-conversion. It is 856 caller's responsibility to deallocate basic block list. 857 If-conversion suitable order is, breadth first sort (BFS) order 858 with an additional constraint: select a block only if all its 859 predecessors are already selected. */ 860 861 static basic_block * 862 get_loop_body_in_if_conv_order (const struct loop *loop) 863 { 864 basic_block *blocks, *blocks_in_bfs_order; 865 basic_block bb; 866 bitmap visited; 867 unsigned int index = 0; 868 unsigned int visited_count = 0; 869 870 gcc_assert (loop->num_nodes); 871 gcc_assert (loop->latch != EXIT_BLOCK_PTR); 872 873 blocks = XCNEWVEC (basic_block, loop->num_nodes); 874 visited = BITMAP_ALLOC (NULL); 875 876 blocks_in_bfs_order = get_loop_body_in_bfs_order (loop); 877 878 index = 0; 879 while (index < loop->num_nodes) 880 { 881 bb = blocks_in_bfs_order [index]; 882 883 if (bb->flags & BB_IRREDUCIBLE_LOOP) 884 { 885 free (blocks_in_bfs_order); 886 BITMAP_FREE (visited); 887 free (blocks); 888 return NULL; 889 } 890 891 if (!bitmap_bit_p (visited, bb->index)) 892 { 893 if (pred_blocks_visited_p (bb, &visited) 894 || bb == loop->header) 895 { 896 /* This block is now visited. */ 897 bitmap_set_bit (visited, bb->index); 898 blocks[visited_count++] = bb; 899 } 900 } 901 902 index++; 903 904 if (index == loop->num_nodes 905 && visited_count != loop->num_nodes) 906 /* Not done yet. */ 907 index = 0; 908 } 909 free (blocks_in_bfs_order); 910 BITMAP_FREE (visited); 911 return blocks; 912 } 913 914 /* Returns true when the analysis of the predicates for all the basic 915 blocks in LOOP succeeded. 916 917 predicate_bbs first allocates the predicates of the basic blocks. 918 These fields are then initialized with the tree expressions 919 representing the predicates under which a basic block is executed 920 in the LOOP. As the loop->header is executed at each iteration, it 921 has the "true" predicate. Other statements executed under a 922 condition are predicated with that condition, for example 923 924 | if (x) 925 | S1; 926 | else 927 | S2; 928 929 S1 will be predicated with "x", and 930 S2 will be predicated with "!x". */ 931 932 static bool 933 predicate_bbs (loop_p loop) 934 { 935 unsigned int i; 936 937 for (i = 0; i < loop->num_nodes; i++) 938 init_bb_predicate (ifc_bbs[i]); 939 940 for (i = 0; i < loop->num_nodes; i++) 941 { 942 basic_block bb = ifc_bbs[i]; 943 tree cond; 944 gimple_stmt_iterator itr; 945 946 /* The loop latch is always executed and has no extra conditions 947 to be processed: skip it. */ 948 if (bb == loop->latch) 949 { 950 reset_bb_predicate (loop->latch); 951 continue; 952 } 953 954 cond = bb_predicate (bb); 955 956 for (itr = gsi_start_bb (bb); !gsi_end_p (itr); gsi_next (&itr)) 957 { 958 gimple stmt = gsi_stmt (itr); 959 960 switch (gimple_code (stmt)) 961 { 962 case GIMPLE_LABEL: 963 case GIMPLE_ASSIGN: 964 case GIMPLE_CALL: 965 case GIMPLE_DEBUG: 966 break; 967 968 case GIMPLE_COND: 969 { 970 tree c2, tem; 971 edge true_edge, false_edge; 972 location_t loc = gimple_location (stmt); 973 tree c = fold_build2_loc (loc, gimple_cond_code (stmt), 974 boolean_type_node, 975 gimple_cond_lhs (stmt), 976 gimple_cond_rhs (stmt)); 977 978 /* Add new condition into destination's predicate list. */ 979 extract_true_false_edges_from_block (gimple_bb (stmt), 980 &true_edge, &false_edge); 981 982 /* If C is true, then TRUE_EDGE is taken. */ 983 add_to_dst_predicate_list (loop, true_edge, 984 unshare_expr (cond), 985 unshare_expr (c)); 986 987 /* If C is false, then FALSE_EDGE is taken. */ 988 c2 = invert_truthvalue_loc (loc, unshare_expr (c)); 989 tem = canonicalize_cond_expr_cond (c2); 990 if (tem) 991 c2 = tem; 992 add_to_dst_predicate_list (loop, false_edge, 993 unshare_expr (cond), c2); 994 995 cond = NULL_TREE; 996 break; 997 } 998 999 default: 1000 /* Not handled yet in if-conversion. */ 1001 return false; 1002 } 1003 } 1004 1005 /* If current bb has only one successor, then consider it as an 1006 unconditional goto. */ 1007 if (single_succ_p (bb)) 1008 { 1009 basic_block bb_n = single_succ (bb); 1010 1011 /* The successor bb inherits the predicate of its 1012 predecessor. If there is no predicate in the predecessor 1013 bb, then consider the successor bb as always executed. */ 1014 if (cond == NULL_TREE) 1015 cond = boolean_true_node; 1016 1017 add_to_predicate_list (bb_n, cond); 1018 } 1019 } 1020 1021 /* The loop header is always executed. */ 1022 reset_bb_predicate (loop->header); 1023 gcc_assert (bb_predicate_gimplified_stmts (loop->header) == NULL 1024 && bb_predicate_gimplified_stmts (loop->latch) == NULL); 1025 1026 return true; 1027 } 1028 1029 /* Return true when LOOP is if-convertible. This is a helper function 1030 for if_convertible_loop_p. REFS and DDRS are initialized and freed 1031 in if_convertible_loop_p. */ 1032 1033 static bool 1034 if_convertible_loop_p_1 (struct loop *loop, 1035 VEC (loop_p, heap) **loop_nest, 1036 VEC (data_reference_p, heap) **refs, 1037 VEC (ddr_p, heap) **ddrs) 1038 { 1039 bool res; 1040 unsigned int i; 1041 basic_block exit_bb = NULL; 1042 1043 /* Don't if-convert the loop when the data dependences cannot be 1044 computed: the loop won't be vectorized in that case. */ 1045 res = compute_data_dependences_for_loop (loop, true, loop_nest, refs, ddrs); 1046 if (!res) 1047 return false; 1048 1049 calculate_dominance_info (CDI_DOMINATORS); 1050 1051 /* Allow statements that can be handled during if-conversion. */ 1052 ifc_bbs = get_loop_body_in_if_conv_order (loop); 1053 if (!ifc_bbs) 1054 { 1055 if (dump_file && (dump_flags & TDF_DETAILS)) 1056 fprintf (dump_file, "Irreducible loop\n"); 1057 return false; 1058 } 1059 1060 for (i = 0; i < loop->num_nodes; i++) 1061 { 1062 basic_block bb = ifc_bbs[i]; 1063 1064 if (!if_convertible_bb_p (loop, bb, exit_bb)) 1065 return false; 1066 1067 if (bb_with_exit_edge_p (loop, bb)) 1068 exit_bb = bb; 1069 } 1070 1071 res = predicate_bbs (loop); 1072 if (!res) 1073 return false; 1074 1075 if (flag_tree_loop_if_convert_stores) 1076 { 1077 data_reference_p dr; 1078 1079 for (i = 0; VEC_iterate (data_reference_p, *refs, i, dr); i++) 1080 { 1081 dr->aux = XNEW (struct ifc_dr); 1082 DR_WRITTEN_AT_LEAST_ONCE (dr) = -1; 1083 DR_RW_UNCONDITIONALLY (dr) = -1; 1084 } 1085 } 1086 1087 for (i = 0; i < loop->num_nodes; i++) 1088 { 1089 basic_block bb = ifc_bbs[i]; 1090 gimple_stmt_iterator itr; 1091 1092 for (itr = gsi_start_phis (bb); !gsi_end_p (itr); gsi_next (&itr)) 1093 if (!if_convertible_phi_p (loop, bb, gsi_stmt (itr))) 1094 return false; 1095 1096 /* Check the if-convertibility of statements in predicated BBs. */ 1097 if (is_predicated (bb)) 1098 for (itr = gsi_start_bb (bb); !gsi_end_p (itr); gsi_next (&itr)) 1099 if (!if_convertible_stmt_p (gsi_stmt (itr), *refs)) 1100 return false; 1101 } 1102 1103 if (dump_file) 1104 fprintf (dump_file, "Applying if-conversion\n"); 1105 1106 return true; 1107 } 1108 1109 /* Return true when LOOP is if-convertible. 1110 LOOP is if-convertible if: 1111 - it is innermost, 1112 - it has two or more basic blocks, 1113 - it has only one exit, 1114 - loop header is not the exit edge, 1115 - if its basic blocks and phi nodes are if convertible. */ 1116 1117 static bool 1118 if_convertible_loop_p (struct loop *loop) 1119 { 1120 edge e; 1121 edge_iterator ei; 1122 bool res = false; 1123 VEC (data_reference_p, heap) *refs; 1124 VEC (ddr_p, heap) *ddrs; 1125 VEC (loop_p, heap) *loop_nest; 1126 1127 /* Handle only innermost loop. */ 1128 if (!loop || loop->inner) 1129 { 1130 if (dump_file && (dump_flags & TDF_DETAILS)) 1131 fprintf (dump_file, "not innermost loop\n"); 1132 return false; 1133 } 1134 1135 /* If only one block, no need for if-conversion. */ 1136 if (loop->num_nodes <= 2) 1137 { 1138 if (dump_file && (dump_flags & TDF_DETAILS)) 1139 fprintf (dump_file, "less than 2 basic blocks\n"); 1140 return false; 1141 } 1142 1143 /* More than one loop exit is too much to handle. */ 1144 if (!single_exit (loop)) 1145 { 1146 if (dump_file && (dump_flags & TDF_DETAILS)) 1147 fprintf (dump_file, "multiple exits\n"); 1148 return false; 1149 } 1150 1151 /* If one of the loop header's edge is an exit edge then do not 1152 apply if-conversion. */ 1153 FOR_EACH_EDGE (e, ei, loop->header->succs) 1154 if (loop_exit_edge_p (loop, e)) 1155 return false; 1156 1157 refs = VEC_alloc (data_reference_p, heap, 5); 1158 ddrs = VEC_alloc (ddr_p, heap, 25); 1159 loop_nest = VEC_alloc (loop_p, heap, 3); 1160 res = if_convertible_loop_p_1 (loop, &loop_nest, &refs, &ddrs); 1161 1162 if (flag_tree_loop_if_convert_stores) 1163 { 1164 data_reference_p dr; 1165 unsigned int i; 1166 1167 for (i = 0; VEC_iterate (data_reference_p, refs, i, dr); i++) 1168 free (dr->aux); 1169 } 1170 1171 VEC_free (loop_p, heap, loop_nest); 1172 free_data_refs (refs); 1173 free_dependence_relations (ddrs); 1174 return res; 1175 } 1176 1177 /* Basic block BB has two predecessors. Using predecessor's bb 1178 predicate, set an appropriate condition COND for the PHI node 1179 replacement. Return the true block whose phi arguments are 1180 selected when cond is true. LOOP is the loop containing the 1181 if-converted region, GSI is the place to insert the code for the 1182 if-conversion. */ 1183 1184 static basic_block 1185 find_phi_replacement_condition (basic_block bb, tree *cond, 1186 gimple_stmt_iterator *gsi) 1187 { 1188 edge first_edge, second_edge; 1189 tree tmp_cond; 1190 1191 gcc_assert (EDGE_COUNT (bb->preds) == 2); 1192 first_edge = EDGE_PRED (bb, 0); 1193 second_edge = EDGE_PRED (bb, 1); 1194 1195 /* Prefer an edge with a not negated predicate. 1196 ??? That's a very weak cost model. */ 1197 tmp_cond = bb_predicate (first_edge->src); 1198 gcc_assert (tmp_cond); 1199 if (TREE_CODE (tmp_cond) == TRUTH_NOT_EXPR) 1200 { 1201 edge tmp_edge; 1202 1203 tmp_edge = first_edge; 1204 first_edge = second_edge; 1205 second_edge = tmp_edge; 1206 } 1207 1208 /* Check if the edge we take the condition from is not critical. 1209 We know that at least one non-critical edge exists. */ 1210 if (EDGE_COUNT (first_edge->src->succs) > 1) 1211 { 1212 *cond = bb_predicate (second_edge->src); 1213 1214 if (TREE_CODE (*cond) == TRUTH_NOT_EXPR) 1215 *cond = TREE_OPERAND (*cond, 0); 1216 else 1217 /* Select non loop header bb. */ 1218 first_edge = second_edge; 1219 } 1220 else 1221 *cond = bb_predicate (first_edge->src); 1222 1223 /* Gimplify the condition to a valid cond-expr conditonal operand. */ 1224 *cond = force_gimple_operand_gsi_1 (gsi, unshare_expr (*cond), 1225 is_gimple_condexpr, NULL_TREE, 1226 true, GSI_SAME_STMT); 1227 1228 return first_edge->src; 1229 } 1230 1231 /* Replace a scalar PHI node with a COND_EXPR using COND as condition. 1232 This routine does not handle PHI nodes with more than two 1233 arguments. 1234 1235 For example, 1236 S1: A = PHI <x1(1), x2(5)> 1237 is converted into, 1238 S2: A = cond ? x1 : x2; 1239 1240 The generated code is inserted at GSI that points to the top of 1241 basic block's statement list. When COND is true, phi arg from 1242 TRUE_BB is selected. */ 1243 1244 static void 1245 predicate_scalar_phi (gimple phi, tree cond, 1246 basic_block true_bb, 1247 gimple_stmt_iterator *gsi) 1248 { 1249 gimple new_stmt; 1250 basic_block bb; 1251 tree rhs, res, arg, scev; 1252 1253 gcc_assert (gimple_code (phi) == GIMPLE_PHI 1254 && gimple_phi_num_args (phi) == 2); 1255 1256 res = gimple_phi_result (phi); 1257 /* Do not handle virtual phi nodes. */ 1258 if (!is_gimple_reg (SSA_NAME_VAR (res))) 1259 return; 1260 1261 bb = gimple_bb (phi); 1262 1263 if ((arg = degenerate_phi_result (phi)) 1264 || ((scev = analyze_scalar_evolution (gimple_bb (phi)->loop_father, 1265 res)) 1266 && !chrec_contains_undetermined (scev) 1267 && scev != res 1268 && (arg = gimple_phi_arg_def (phi, 0)))) 1269 rhs = arg; 1270 else 1271 { 1272 tree arg_0, arg_1; 1273 /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr. */ 1274 if (EDGE_PRED (bb, 1)->src == true_bb) 1275 { 1276 arg_0 = gimple_phi_arg_def (phi, 1); 1277 arg_1 = gimple_phi_arg_def (phi, 0); 1278 } 1279 else 1280 { 1281 arg_0 = gimple_phi_arg_def (phi, 0); 1282 arg_1 = gimple_phi_arg_def (phi, 1); 1283 } 1284 1285 /* Build new RHS using selected condition and arguments. */ 1286 rhs = build3 (COND_EXPR, TREE_TYPE (res), 1287 unshare_expr (cond), arg_0, arg_1); 1288 } 1289 1290 new_stmt = gimple_build_assign (res, rhs); 1291 SSA_NAME_DEF_STMT (gimple_phi_result (phi)) = new_stmt; 1292 gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT); 1293 update_stmt (new_stmt); 1294 1295 if (dump_file && (dump_flags & TDF_DETAILS)) 1296 { 1297 fprintf (dump_file, "new phi replacement stmt\n"); 1298 print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM); 1299 } 1300 } 1301 1302 /* Replaces in LOOP all the scalar phi nodes other than those in the 1303 LOOP->header block with conditional modify expressions. */ 1304 1305 static void 1306 predicate_all_scalar_phis (struct loop *loop) 1307 { 1308 basic_block bb; 1309 unsigned int orig_loop_num_nodes = loop->num_nodes; 1310 unsigned int i; 1311 1312 for (i = 1; i < orig_loop_num_nodes; i++) 1313 { 1314 gimple phi; 1315 tree cond = NULL_TREE; 1316 gimple_stmt_iterator gsi, phi_gsi; 1317 basic_block true_bb = NULL; 1318 bb = ifc_bbs[i]; 1319 1320 if (bb == loop->header) 1321 continue; 1322 1323 phi_gsi = gsi_start_phis (bb); 1324 if (gsi_end_p (phi_gsi)) 1325 continue; 1326 1327 /* BB has two predecessors. Using predecessor's aux field, set 1328 appropriate condition for the PHI node replacement. */ 1329 gsi = gsi_after_labels (bb); 1330 true_bb = find_phi_replacement_condition (bb, &cond, &gsi); 1331 1332 while (!gsi_end_p (phi_gsi)) 1333 { 1334 phi = gsi_stmt (phi_gsi); 1335 predicate_scalar_phi (phi, cond, true_bb, &gsi); 1336 release_phi_node (phi); 1337 gsi_next (&phi_gsi); 1338 } 1339 1340 set_phi_nodes (bb, NULL); 1341 } 1342 } 1343 1344 /* Insert in each basic block of LOOP the statements produced by the 1345 gimplification of the predicates. */ 1346 1347 static void 1348 insert_gimplified_predicates (loop_p loop) 1349 { 1350 unsigned int i; 1351 1352 for (i = 0; i < loop->num_nodes; i++) 1353 { 1354 basic_block bb = ifc_bbs[i]; 1355 gimple_seq stmts; 1356 1357 if (!is_predicated (bb)) 1358 { 1359 /* Do not insert statements for a basic block that is not 1360 predicated. Also make sure that the predicate of the 1361 basic block is set to true. */ 1362 reset_bb_predicate (bb); 1363 continue; 1364 } 1365 1366 stmts = bb_predicate_gimplified_stmts (bb); 1367 if (stmts) 1368 { 1369 if (flag_tree_loop_if_convert_stores) 1370 { 1371 /* Insert the predicate of the BB just after the label, 1372 as the if-conversion of memory writes will use this 1373 predicate. */ 1374 gimple_stmt_iterator gsi = gsi_after_labels (bb); 1375 gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT); 1376 } 1377 else 1378 { 1379 /* Insert the predicate of the BB at the end of the BB 1380 as this would reduce the register pressure: the only 1381 use of this predicate will be in successor BBs. */ 1382 gimple_stmt_iterator gsi = gsi_last_bb (bb); 1383 1384 if (gsi_end_p (gsi) 1385 || stmt_ends_bb_p (gsi_stmt (gsi))) 1386 gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT); 1387 else 1388 gsi_insert_seq_after (&gsi, stmts, GSI_SAME_STMT); 1389 } 1390 1391 /* Once the sequence is code generated, set it to NULL. */ 1392 set_bb_predicate_gimplified_stmts (bb, NULL); 1393 } 1394 } 1395 } 1396 1397 /* Predicate each write to memory in LOOP. 1398 1399 This function transforms control flow constructs containing memory 1400 writes of the form: 1401 1402 | for (i = 0; i < N; i++) 1403 | if (cond) 1404 | A[i] = expr; 1405 1406 into the following form that does not contain control flow: 1407 1408 | for (i = 0; i < N; i++) 1409 | A[i] = cond ? expr : A[i]; 1410 1411 The original CFG looks like this: 1412 1413 | bb_0 1414 | i = 0 1415 | end_bb_0 1416 | 1417 | bb_1 1418 | if (i < N) goto bb_5 else goto bb_2 1419 | end_bb_1 1420 | 1421 | bb_2 1422 | cond = some_computation; 1423 | if (cond) goto bb_3 else goto bb_4 1424 | end_bb_2 1425 | 1426 | bb_3 1427 | A[i] = expr; 1428 | goto bb_4 1429 | end_bb_3 1430 | 1431 | bb_4 1432 | goto bb_1 1433 | end_bb_4 1434 1435 insert_gimplified_predicates inserts the computation of the COND 1436 expression at the beginning of the destination basic block: 1437 1438 | bb_0 1439 | i = 0 1440 | end_bb_0 1441 | 1442 | bb_1 1443 | if (i < N) goto bb_5 else goto bb_2 1444 | end_bb_1 1445 | 1446 | bb_2 1447 | cond = some_computation; 1448 | if (cond) goto bb_3 else goto bb_4 1449 | end_bb_2 1450 | 1451 | bb_3 1452 | cond = some_computation; 1453 | A[i] = expr; 1454 | goto bb_4 1455 | end_bb_3 1456 | 1457 | bb_4 1458 | goto bb_1 1459 | end_bb_4 1460 1461 predicate_mem_writes is then predicating the memory write as follows: 1462 1463 | bb_0 1464 | i = 0 1465 | end_bb_0 1466 | 1467 | bb_1 1468 | if (i < N) goto bb_5 else goto bb_2 1469 | end_bb_1 1470 | 1471 | bb_2 1472 | if (cond) goto bb_3 else goto bb_4 1473 | end_bb_2 1474 | 1475 | bb_3 1476 | cond = some_computation; 1477 | A[i] = cond ? expr : A[i]; 1478 | goto bb_4 1479 | end_bb_3 1480 | 1481 | bb_4 1482 | goto bb_1 1483 | end_bb_4 1484 1485 and finally combine_blocks removes the basic block boundaries making 1486 the loop vectorizable: 1487 1488 | bb_0 1489 | i = 0 1490 | if (i < N) goto bb_5 else goto bb_1 1491 | end_bb_0 1492 | 1493 | bb_1 1494 | cond = some_computation; 1495 | A[i] = cond ? expr : A[i]; 1496 | if (i < N) goto bb_5 else goto bb_4 1497 | end_bb_1 1498 | 1499 | bb_4 1500 | goto bb_1 1501 | end_bb_4 1502 */ 1503 1504 static void 1505 predicate_mem_writes (loop_p loop) 1506 { 1507 unsigned int i, orig_loop_num_nodes = loop->num_nodes; 1508 1509 for (i = 1; i < orig_loop_num_nodes; i++) 1510 { 1511 gimple_stmt_iterator gsi; 1512 basic_block bb = ifc_bbs[i]; 1513 tree cond = bb_predicate (bb); 1514 bool swap; 1515 gimple stmt; 1516 1517 if (is_true_predicate (cond)) 1518 continue; 1519 1520 swap = false; 1521 if (TREE_CODE (cond) == TRUTH_NOT_EXPR) 1522 { 1523 swap = true; 1524 cond = TREE_OPERAND (cond, 0); 1525 } 1526 1527 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 1528 if ((stmt = gsi_stmt (gsi)) 1529 && gimple_assign_single_p (stmt) 1530 && gimple_vdef (stmt)) 1531 { 1532 tree lhs = gimple_assign_lhs (stmt); 1533 tree rhs = gimple_assign_rhs1 (stmt); 1534 tree type = TREE_TYPE (lhs); 1535 1536 lhs = ifc_temp_var (type, unshare_expr (lhs), &gsi); 1537 rhs = ifc_temp_var (type, unshare_expr (rhs), &gsi); 1538 if (swap) 1539 { 1540 tree tem = lhs; 1541 lhs = rhs; 1542 rhs = tem; 1543 } 1544 cond = force_gimple_operand_gsi_1 (&gsi, unshare_expr (cond), 1545 is_gimple_condexpr, NULL_TREE, 1546 true, GSI_SAME_STMT); 1547 rhs = build3 (COND_EXPR, type, unshare_expr (cond), rhs, lhs); 1548 gimple_assign_set_rhs1 (stmt, ifc_temp_var (type, rhs, &gsi)); 1549 update_stmt (stmt); 1550 } 1551 } 1552 } 1553 1554 /* Remove all GIMPLE_CONDs and GIMPLE_LABELs of all the basic blocks 1555 other than the exit and latch of the LOOP. Also resets the 1556 GIMPLE_DEBUG information. */ 1557 1558 static void 1559 remove_conditions_and_labels (loop_p loop) 1560 { 1561 gimple_stmt_iterator gsi; 1562 unsigned int i; 1563 1564 for (i = 0; i < loop->num_nodes; i++) 1565 { 1566 basic_block bb = ifc_bbs[i]; 1567 1568 if (bb_with_exit_edge_p (loop, bb) 1569 || bb == loop->latch) 1570 continue; 1571 1572 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); ) 1573 switch (gimple_code (gsi_stmt (gsi))) 1574 { 1575 case GIMPLE_COND: 1576 case GIMPLE_LABEL: 1577 gsi_remove (&gsi, true); 1578 break; 1579 1580 case GIMPLE_DEBUG: 1581 /* ??? Should there be conditional GIMPLE_DEBUG_BINDs? */ 1582 if (gimple_debug_bind_p (gsi_stmt (gsi))) 1583 { 1584 gimple_debug_bind_reset_value (gsi_stmt (gsi)); 1585 update_stmt (gsi_stmt (gsi)); 1586 } 1587 gsi_next (&gsi); 1588 break; 1589 1590 default: 1591 gsi_next (&gsi); 1592 } 1593 } 1594 } 1595 1596 /* Combine all the basic blocks from LOOP into one or two super basic 1597 blocks. Replace PHI nodes with conditional modify expressions. */ 1598 1599 static void 1600 combine_blocks (struct loop *loop) 1601 { 1602 basic_block bb, exit_bb, merge_target_bb; 1603 unsigned int orig_loop_num_nodes = loop->num_nodes; 1604 unsigned int i; 1605 edge e; 1606 edge_iterator ei; 1607 1608 remove_conditions_and_labels (loop); 1609 insert_gimplified_predicates (loop); 1610 predicate_all_scalar_phis (loop); 1611 1612 if (flag_tree_loop_if_convert_stores) 1613 predicate_mem_writes (loop); 1614 1615 /* Merge basic blocks: first remove all the edges in the loop, 1616 except for those from the exit block. */ 1617 exit_bb = NULL; 1618 for (i = 0; i < orig_loop_num_nodes; i++) 1619 { 1620 bb = ifc_bbs[i]; 1621 free_bb_predicate (bb); 1622 if (bb_with_exit_edge_p (loop, bb)) 1623 { 1624 exit_bb = bb; 1625 break; 1626 } 1627 } 1628 gcc_assert (exit_bb != loop->latch); 1629 1630 for (i = 1; i < orig_loop_num_nodes; i++) 1631 { 1632 bb = ifc_bbs[i]; 1633 1634 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei));) 1635 { 1636 if (e->src == exit_bb) 1637 ei_next (&ei); 1638 else 1639 remove_edge (e); 1640 } 1641 } 1642 1643 if (exit_bb != NULL) 1644 { 1645 if (exit_bb != loop->header) 1646 { 1647 /* Connect this node to loop header. */ 1648 make_edge (loop->header, exit_bb, EDGE_FALLTHRU); 1649 set_immediate_dominator (CDI_DOMINATORS, exit_bb, loop->header); 1650 } 1651 1652 /* Redirect non-exit edges to loop->latch. */ 1653 FOR_EACH_EDGE (e, ei, exit_bb->succs) 1654 { 1655 if (!loop_exit_edge_p (loop, e)) 1656 redirect_edge_and_branch (e, loop->latch); 1657 } 1658 set_immediate_dominator (CDI_DOMINATORS, loop->latch, exit_bb); 1659 } 1660 else 1661 { 1662 /* If the loop does not have an exit, reconnect header and latch. */ 1663 make_edge (loop->header, loop->latch, EDGE_FALLTHRU); 1664 set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header); 1665 } 1666 1667 merge_target_bb = loop->header; 1668 for (i = 1; i < orig_loop_num_nodes; i++) 1669 { 1670 gimple_stmt_iterator gsi; 1671 gimple_stmt_iterator last; 1672 1673 bb = ifc_bbs[i]; 1674 1675 if (bb == exit_bb || bb == loop->latch) 1676 continue; 1677 1678 /* Make stmts member of loop->header. */ 1679 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 1680 gimple_set_bb (gsi_stmt (gsi), merge_target_bb); 1681 1682 /* Update stmt list. */ 1683 last = gsi_last_bb (merge_target_bb); 1684 gsi_insert_seq_after (&last, bb_seq (bb), GSI_NEW_STMT); 1685 set_bb_seq (bb, NULL); 1686 1687 delete_basic_block (bb); 1688 } 1689 1690 /* If possible, merge loop header to the block with the exit edge. 1691 This reduces the number of basic blocks to two, to please the 1692 vectorizer that handles only loops with two nodes. */ 1693 if (exit_bb 1694 && exit_bb != loop->header 1695 && can_merge_blocks_p (loop->header, exit_bb)) 1696 merge_blocks (loop->header, exit_bb); 1697 1698 free (ifc_bbs); 1699 ifc_bbs = NULL; 1700 } 1701 1702 /* If-convert LOOP when it is legal. For the moment this pass has no 1703 profitability analysis. Returns true when something changed. */ 1704 1705 static bool 1706 tree_if_conversion (struct loop *loop) 1707 { 1708 bool changed = false; 1709 ifc_bbs = NULL; 1710 1711 if (!if_convertible_loop_p (loop) 1712 || !dbg_cnt (if_conversion_tree)) 1713 goto cleanup; 1714 1715 /* Now all statements are if-convertible. Combine all the basic 1716 blocks into one huge basic block doing the if-conversion 1717 on-the-fly. */ 1718 combine_blocks (loop); 1719 1720 if (flag_tree_loop_if_convert_stores) 1721 mark_sym_for_renaming (gimple_vop (cfun)); 1722 1723 changed = true; 1724 1725 cleanup: 1726 if (ifc_bbs) 1727 { 1728 unsigned int i; 1729 1730 for (i = 0; i < loop->num_nodes; i++) 1731 free_bb_predicate (ifc_bbs[i]); 1732 1733 free (ifc_bbs); 1734 ifc_bbs = NULL; 1735 } 1736 1737 return changed; 1738 } 1739 1740 /* Tree if-conversion pass management. */ 1741 1742 static unsigned int 1743 main_tree_if_conversion (void) 1744 { 1745 loop_iterator li; 1746 struct loop *loop; 1747 bool changed = false; 1748 unsigned todo = 0; 1749 1750 if (number_of_loops () <= 1) 1751 return 0; 1752 1753 FOR_EACH_LOOP (li, loop, 0) 1754 changed |= tree_if_conversion (loop); 1755 1756 if (changed) 1757 todo |= TODO_cleanup_cfg; 1758 1759 if (changed && flag_tree_loop_if_convert_stores) 1760 todo |= TODO_update_ssa_only_virtuals; 1761 1762 return todo; 1763 } 1764 1765 /* Returns true when the if-conversion pass is enabled. */ 1766 1767 static bool 1768 gate_tree_if_conversion (void) 1769 { 1770 return ((flag_tree_vectorize && flag_tree_loop_if_convert != 0) 1771 || flag_tree_loop_if_convert == 1 1772 || flag_tree_loop_if_convert_stores == 1); 1773 } 1774 1775 struct gimple_opt_pass pass_if_conversion = 1776 { 1777 { 1778 GIMPLE_PASS, 1779 "ifcvt", /* name */ 1780 gate_tree_if_conversion, /* gate */ 1781 main_tree_if_conversion, /* execute */ 1782 NULL, /* sub */ 1783 NULL, /* next */ 1784 0, /* static_pass_number */ 1785 TV_NONE, /* tv_id */ 1786 PROP_cfg | PROP_ssa, /* properties_required */ 1787 0, /* properties_provided */ 1788 0, /* properties_destroyed */ 1789 0, /* todo_flags_start */ 1790 TODO_verify_stmts | TODO_verify_flow 1791 /* todo_flags_finish */ 1792 } 1793 }; 1794