1 /* If-conversion for vectorizer. 2 Copyright (C) 2004-2019 Free Software Foundation, Inc. 3 Contributed by Devang Patel <dpatel@apple.com> 4 5 This file is part of GCC. 6 7 GCC is free software; you can redistribute it and/or modify it under 8 the terms of the GNU General Public License as published by the Free 9 Software Foundation; either version 3, or (at your option) any later 10 version. 11 12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13 WARRANTY; without even the implied warranty of MERCHANTABILITY or 14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15 for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with GCC; see the file COPYING3. If not see 19 <http://www.gnu.org/licenses/>. */ 20 21 /* This pass implements a tree level if-conversion of loops. Its 22 initial goal is to help the vectorizer to vectorize loops with 23 conditions. 24 25 A short description of if-conversion: 26 27 o Decide if a loop is if-convertible or not. 28 o Walk all loop basic blocks in breadth first order (BFS order). 29 o Remove conditional statements (at the end of basic block) 30 and propagate condition into destination basic blocks' 31 predicate list. 32 o Replace modify expression with conditional modify expression 33 using current basic block's condition. 34 o Merge all basic blocks 35 o Replace phi nodes with conditional modify expr 36 o Merge all basic blocks into header 37 38 Sample transformation: 39 40 INPUT 41 ----- 42 43 # i_23 = PHI <0(0), i_18(10)>; 44 <L0>:; 45 j_15 = A[i_23]; 46 if (j_15 > 41) goto <L1>; else goto <L17>; 47 48 <L17>:; 49 goto <bb 3> (<L3>); 50 51 <L1>:; 52 53 # iftmp.2_4 = PHI <0(8), 42(2)>; 54 <L3>:; 55 A[i_23] = iftmp.2_4; 56 i_18 = i_23 + 1; 57 if (i_18 <= 15) goto <L19>; else goto <L18>; 58 59 <L19>:; 60 goto <bb 1> (<L0>); 61 62 <L18>:; 63 64 OUTPUT 65 ------ 66 67 # i_23 = PHI <0(0), i_18(10)>; 68 <L0>:; 69 j_15 = A[i_23]; 70 71 <L3>:; 72 iftmp.2_4 = j_15 > 41 ? 42 : 0; 73 A[i_23] = iftmp.2_4; 74 i_18 = i_23 + 1; 75 if (i_18 <= 15) goto <L19>; else goto <L18>; 76 77 <L19>:; 78 goto <bb 1> (<L0>); 79 80 <L18>:; 81 */ 82 83 #include "config.h" 84 #include "system.h" 85 #include "coretypes.h" 86 #include "backend.h" 87 #include "rtl.h" 88 #include "tree.h" 89 #include "gimple.h" 90 #include "cfghooks.h" 91 #include "tree-pass.h" 92 #include "ssa.h" 93 #include "expmed.h" 94 #include "optabs-query.h" 95 #include "gimple-pretty-print.h" 96 #include "alias.h" 97 #include "fold-const.h" 98 #include "stor-layout.h" 99 #include "gimple-fold.h" 100 #include "gimplify.h" 101 #include "gimple-iterator.h" 102 #include "gimplify-me.h" 103 #include "tree-cfg.h" 104 #include "tree-into-ssa.h" 105 #include "tree-ssa.h" 106 #include "cfgloop.h" 107 #include "tree-data-ref.h" 108 #include "tree-scalar-evolution.h" 109 #include "tree-ssa-loop.h" 110 #include "tree-ssa-loop-niter.h" 111 #include "tree-ssa-loop-ivopts.h" 112 #include "tree-ssa-address.h" 113 #include "dbgcnt.h" 114 #include "tree-hash-traits.h" 115 #include "varasm.h" 116 #include "builtins.h" 117 #include "params.h" 118 #include "cfganal.h" 119 #include "internal-fn.h" 120 #include "fold-const.h" 121 #include "tree-ssa-sccvn.h" 122 #include "tree-cfgcleanup.h" 123 124 /* Only handle PHIs with no more arguments unless we are asked to by 125 simd pragma. */ 126 #define MAX_PHI_ARG_NUM \ 127 ((unsigned) PARAM_VALUE (PARAM_MAX_TREE_IF_CONVERSION_PHI_ARGS)) 128 129 /* True if we've converted a statement that was only executed when some 130 condition C was true, and if for correctness we need to predicate the 131 statement to ensure that it is a no-op when C is false. See 132 predicate_statements for the kinds of predication we support. */ 133 static bool need_to_predicate; 134 135 /* Indicate if there are any complicated PHIs that need to be handled in 136 if-conversion. Complicated PHI has more than two arguments and can't 137 be degenerated to two arguments PHI. See more information in comment 138 before phi_convertible_by_degenerating_args. */ 139 static bool any_complicated_phi; 140 141 /* Hash for struct innermost_loop_behavior. It depends on the user to 142 free the memory. */ 143 144 struct innermost_loop_behavior_hash : nofree_ptr_hash <innermost_loop_behavior> 145 { 146 static inline hashval_t hash (const value_type &); 147 static inline bool equal (const value_type &, 148 const compare_type &); 149 }; 150 151 inline hashval_t 152 innermost_loop_behavior_hash::hash (const value_type &e) 153 { 154 hashval_t hash; 155 156 hash = iterative_hash_expr (e->base_address, 0); 157 hash = iterative_hash_expr (e->offset, hash); 158 hash = iterative_hash_expr (e->init, hash); 159 return iterative_hash_expr (e->step, hash); 160 } 161 162 inline bool 163 innermost_loop_behavior_hash::equal (const value_type &e1, 164 const compare_type &e2) 165 { 166 if ((e1->base_address && !e2->base_address) 167 || (!e1->base_address && e2->base_address) 168 || (!e1->offset && e2->offset) 169 || (e1->offset && !e2->offset) 170 || (!e1->init && e2->init) 171 || (e1->init && !e2->init) 172 || (!e1->step && e2->step) 173 || (e1->step && !e2->step)) 174 return false; 175 176 if (e1->base_address && e2->base_address 177 && !operand_equal_p (e1->base_address, e2->base_address, 0)) 178 return false; 179 if (e1->offset && e2->offset 180 && !operand_equal_p (e1->offset, e2->offset, 0)) 181 return false; 182 if (e1->init && e2->init 183 && !operand_equal_p (e1->init, e2->init, 0)) 184 return false; 185 if (e1->step && e2->step 186 && !operand_equal_p (e1->step, e2->step, 0)) 187 return false; 188 189 return true; 190 } 191 192 /* List of basic blocks in if-conversion-suitable order. */ 193 static basic_block *ifc_bbs; 194 195 /* Hash table to store <DR's innermost loop behavior, DR> pairs. */ 196 static hash_map<innermost_loop_behavior_hash, 197 data_reference_p> *innermost_DR_map; 198 199 /* Hash table to store <base reference, DR> pairs. */ 200 static hash_map<tree_operand_hash, data_reference_p> *baseref_DR_map; 201 202 /* List of redundant SSA names: the first should be replaced by the second. */ 203 static vec< std::pair<tree, tree> > redundant_ssa_names; 204 205 /* Structure used to predicate basic blocks. This is attached to the 206 ->aux field of the BBs in the loop to be if-converted. */ 207 struct bb_predicate { 208 209 /* The condition under which this basic block is executed. */ 210 tree predicate; 211 212 /* PREDICATE is gimplified, and the sequence of statements is 213 recorded here, in order to avoid the duplication of computations 214 that occur in previous conditions. See PR44483. */ 215 gimple_seq predicate_gimplified_stmts; 216 }; 217 218 /* Returns true when the basic block BB has a predicate. */ 219 220 static inline bool 221 bb_has_predicate (basic_block bb) 222 { 223 return bb->aux != NULL; 224 } 225 226 /* Returns the gimplified predicate for basic block BB. */ 227 228 static inline tree 229 bb_predicate (basic_block bb) 230 { 231 return ((struct bb_predicate *) bb->aux)->predicate; 232 } 233 234 /* Sets the gimplified predicate COND for basic block BB. */ 235 236 static inline void 237 set_bb_predicate (basic_block bb, tree cond) 238 { 239 gcc_assert ((TREE_CODE (cond) == TRUTH_NOT_EXPR 240 && is_gimple_condexpr (TREE_OPERAND (cond, 0))) 241 || is_gimple_condexpr (cond)); 242 ((struct bb_predicate *) bb->aux)->predicate = cond; 243 } 244 245 /* Returns the sequence of statements of the gimplification of the 246 predicate for basic block BB. */ 247 248 static inline gimple_seq 249 bb_predicate_gimplified_stmts (basic_block bb) 250 { 251 return ((struct bb_predicate *) bb->aux)->predicate_gimplified_stmts; 252 } 253 254 /* Sets the sequence of statements STMTS of the gimplification of the 255 predicate for basic block BB. */ 256 257 static inline void 258 set_bb_predicate_gimplified_stmts (basic_block bb, gimple_seq stmts) 259 { 260 ((struct bb_predicate *) bb->aux)->predicate_gimplified_stmts = stmts; 261 } 262 263 /* Adds the sequence of statements STMTS to the sequence of statements 264 of the predicate for basic block BB. */ 265 266 static inline void 267 add_bb_predicate_gimplified_stmts (basic_block bb, gimple_seq stmts) 268 { 269 /* We might have updated some stmts in STMTS via force_gimple_operand 270 calling fold_stmt and that producing multiple stmts. Delink immediate 271 uses so update_ssa after loop versioning doesn't get confused for 272 the not yet inserted predicates. 273 ??? This should go away once we reliably avoid updating stmts 274 not in any BB. */ 275 for (gimple_stmt_iterator gsi = gsi_start (stmts); 276 !gsi_end_p (gsi); gsi_next (&gsi)) 277 { 278 gimple *stmt = gsi_stmt (gsi); 279 delink_stmt_imm_use (stmt); 280 gimple_set_modified (stmt, true); 281 } 282 gimple_seq_add_seq_without_update 283 (&(((struct bb_predicate *) bb->aux)->predicate_gimplified_stmts), stmts); 284 } 285 286 /* Initializes to TRUE the predicate of basic block BB. */ 287 288 static inline void 289 init_bb_predicate (basic_block bb) 290 { 291 bb->aux = XNEW (struct bb_predicate); 292 set_bb_predicate_gimplified_stmts (bb, NULL); 293 set_bb_predicate (bb, boolean_true_node); 294 } 295 296 /* Release the SSA_NAMEs associated with the predicate of basic block BB. */ 297 298 static inline void 299 release_bb_predicate (basic_block bb) 300 { 301 gimple_seq stmts = bb_predicate_gimplified_stmts (bb); 302 if (stmts) 303 { 304 /* Ensure that these stmts haven't yet been added to a bb. */ 305 if (flag_checking) 306 for (gimple_stmt_iterator i = gsi_start (stmts); 307 !gsi_end_p (i); gsi_next (&i)) 308 gcc_assert (! gimple_bb (gsi_stmt (i))); 309 310 /* Discard them. */ 311 gimple_seq_discard (stmts); 312 set_bb_predicate_gimplified_stmts (bb, NULL); 313 } 314 } 315 316 /* Free the predicate of basic block BB. */ 317 318 static inline void 319 free_bb_predicate (basic_block bb) 320 { 321 if (!bb_has_predicate (bb)) 322 return; 323 324 release_bb_predicate (bb); 325 free (bb->aux); 326 bb->aux = NULL; 327 } 328 329 /* Reinitialize predicate of BB with the true predicate. */ 330 331 static inline void 332 reset_bb_predicate (basic_block bb) 333 { 334 if (!bb_has_predicate (bb)) 335 init_bb_predicate (bb); 336 else 337 { 338 release_bb_predicate (bb); 339 set_bb_predicate (bb, boolean_true_node); 340 } 341 } 342 343 /* Returns a new SSA_NAME of type TYPE that is assigned the value of 344 the expression EXPR. Inserts the statement created for this 345 computation before GSI and leaves the iterator GSI at the same 346 statement. */ 347 348 static tree 349 ifc_temp_var (tree type, tree expr, gimple_stmt_iterator *gsi) 350 { 351 tree new_name = make_temp_ssa_name (type, NULL, "_ifc_"); 352 gimple *stmt = gimple_build_assign (new_name, expr); 353 gimple_set_vuse (stmt, gimple_vuse (gsi_stmt (*gsi))); 354 gsi_insert_before (gsi, stmt, GSI_SAME_STMT); 355 return new_name; 356 } 357 358 /* Return true when COND is a false predicate. */ 359 360 static inline bool 361 is_false_predicate (tree cond) 362 { 363 return (cond != NULL_TREE 364 && (cond == boolean_false_node 365 || integer_zerop (cond))); 366 } 367 368 /* Return true when COND is a true predicate. */ 369 370 static inline bool 371 is_true_predicate (tree cond) 372 { 373 return (cond == NULL_TREE 374 || cond == boolean_true_node 375 || integer_onep (cond)); 376 } 377 378 /* Returns true when BB has a predicate that is not trivial: true or 379 NULL_TREE. */ 380 381 static inline bool 382 is_predicated (basic_block bb) 383 { 384 return !is_true_predicate (bb_predicate (bb)); 385 } 386 387 /* Parses the predicate COND and returns its comparison code and 388 operands OP0 and OP1. */ 389 390 static enum tree_code 391 parse_predicate (tree cond, tree *op0, tree *op1) 392 { 393 gimple *s; 394 395 if (TREE_CODE (cond) == SSA_NAME 396 && is_gimple_assign (s = SSA_NAME_DEF_STMT (cond))) 397 { 398 if (TREE_CODE_CLASS (gimple_assign_rhs_code (s)) == tcc_comparison) 399 { 400 *op0 = gimple_assign_rhs1 (s); 401 *op1 = gimple_assign_rhs2 (s); 402 return gimple_assign_rhs_code (s); 403 } 404 405 else if (gimple_assign_rhs_code (s) == TRUTH_NOT_EXPR) 406 { 407 tree op = gimple_assign_rhs1 (s); 408 tree type = TREE_TYPE (op); 409 enum tree_code code = parse_predicate (op, op0, op1); 410 411 return code == ERROR_MARK ? ERROR_MARK 412 : invert_tree_comparison (code, HONOR_NANS (type)); 413 } 414 415 return ERROR_MARK; 416 } 417 418 if (COMPARISON_CLASS_P (cond)) 419 { 420 *op0 = TREE_OPERAND (cond, 0); 421 *op1 = TREE_OPERAND (cond, 1); 422 return TREE_CODE (cond); 423 } 424 425 return ERROR_MARK; 426 } 427 428 /* Returns the fold of predicate C1 OR C2 at location LOC. */ 429 430 static tree 431 fold_or_predicates (location_t loc, tree c1, tree c2) 432 { 433 tree op1a, op1b, op2a, op2b; 434 enum tree_code code1 = parse_predicate (c1, &op1a, &op1b); 435 enum tree_code code2 = parse_predicate (c2, &op2a, &op2b); 436 437 if (code1 != ERROR_MARK && code2 != ERROR_MARK) 438 { 439 tree t = maybe_fold_or_comparisons (code1, op1a, op1b, 440 code2, op2a, op2b); 441 if (t) 442 return t; 443 } 444 445 return fold_build2_loc (loc, TRUTH_OR_EXPR, boolean_type_node, c1, c2); 446 } 447 448 /* Returns either a COND_EXPR or the folded expression if the folded 449 expression is a MIN_EXPR, a MAX_EXPR, an ABS_EXPR, 450 a constant or a SSA_NAME. */ 451 452 static tree 453 fold_build_cond_expr (tree type, tree cond, tree rhs, tree lhs) 454 { 455 tree rhs1, lhs1, cond_expr; 456 457 /* If COND is comparison r != 0 and r has boolean type, convert COND 458 to SSA_NAME to accept by vect bool pattern. */ 459 if (TREE_CODE (cond) == NE_EXPR) 460 { 461 tree op0 = TREE_OPERAND (cond, 0); 462 tree op1 = TREE_OPERAND (cond, 1); 463 if (TREE_CODE (op0) == SSA_NAME 464 && TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE 465 && (integer_zerop (op1))) 466 cond = op0; 467 } 468 cond_expr = fold_ternary (COND_EXPR, type, cond, rhs, lhs); 469 470 if (cond_expr == NULL_TREE) 471 return build3 (COND_EXPR, type, cond, rhs, lhs); 472 473 STRIP_USELESS_TYPE_CONVERSION (cond_expr); 474 475 if (is_gimple_val (cond_expr)) 476 return cond_expr; 477 478 if (TREE_CODE (cond_expr) == ABS_EXPR) 479 { 480 rhs1 = TREE_OPERAND (cond_expr, 1); 481 STRIP_USELESS_TYPE_CONVERSION (rhs1); 482 if (is_gimple_val (rhs1)) 483 return build1 (ABS_EXPR, type, rhs1); 484 } 485 486 if (TREE_CODE (cond_expr) == MIN_EXPR 487 || TREE_CODE (cond_expr) == MAX_EXPR) 488 { 489 lhs1 = TREE_OPERAND (cond_expr, 0); 490 STRIP_USELESS_TYPE_CONVERSION (lhs1); 491 rhs1 = TREE_OPERAND (cond_expr, 1); 492 STRIP_USELESS_TYPE_CONVERSION (rhs1); 493 if (is_gimple_val (rhs1) && is_gimple_val (lhs1)) 494 return build2 (TREE_CODE (cond_expr), type, lhs1, rhs1); 495 } 496 return build3 (COND_EXPR, type, cond, rhs, lhs); 497 } 498 499 /* Add condition NC to the predicate list of basic block BB. LOOP is 500 the loop to be if-converted. Use predicate of cd-equivalent block 501 for join bb if it exists: we call basic blocks bb1 and bb2 502 cd-equivalent if they are executed under the same condition. */ 503 504 static inline void 505 add_to_predicate_list (struct loop *loop, basic_block bb, tree nc) 506 { 507 tree bc, *tp; 508 basic_block dom_bb; 509 510 if (is_true_predicate (nc)) 511 return; 512 513 /* If dominance tells us this basic block is always executed, 514 don't record any predicates for it. */ 515 if (dominated_by_p (CDI_DOMINATORS, loop->latch, bb)) 516 return; 517 518 dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb); 519 /* We use notion of cd equivalence to get simpler predicate for 520 join block, e.g. if join block has 2 predecessors with predicates 521 p1 & p2 and p1 & !p2, we'd like to get p1 for it instead of 522 p1 & p2 | p1 & !p2. */ 523 if (dom_bb != loop->header 524 && get_immediate_dominator (CDI_POST_DOMINATORS, dom_bb) == bb) 525 { 526 gcc_assert (flow_bb_inside_loop_p (loop, dom_bb)); 527 bc = bb_predicate (dom_bb); 528 if (!is_true_predicate (bc)) 529 set_bb_predicate (bb, bc); 530 else 531 gcc_assert (is_true_predicate (bb_predicate (bb))); 532 if (dump_file && (dump_flags & TDF_DETAILS)) 533 fprintf (dump_file, "Use predicate of bb#%d for bb#%d\n", 534 dom_bb->index, bb->index); 535 return; 536 } 537 538 if (!is_predicated (bb)) 539 bc = nc; 540 else 541 { 542 bc = bb_predicate (bb); 543 bc = fold_or_predicates (EXPR_LOCATION (bc), nc, bc); 544 if (is_true_predicate (bc)) 545 { 546 reset_bb_predicate (bb); 547 return; 548 } 549 } 550 551 /* Allow a TRUTH_NOT_EXPR around the main predicate. */ 552 if (TREE_CODE (bc) == TRUTH_NOT_EXPR) 553 tp = &TREE_OPERAND (bc, 0); 554 else 555 tp = &bc; 556 if (!is_gimple_condexpr (*tp)) 557 { 558 gimple_seq stmts; 559 *tp = force_gimple_operand_1 (*tp, &stmts, is_gimple_condexpr, NULL_TREE); 560 add_bb_predicate_gimplified_stmts (bb, stmts); 561 } 562 set_bb_predicate (bb, bc); 563 } 564 565 /* Add the condition COND to the previous condition PREV_COND, and add 566 this to the predicate list of the destination of edge E. LOOP is 567 the loop to be if-converted. */ 568 569 static void 570 add_to_dst_predicate_list (struct loop *loop, edge e, 571 tree prev_cond, tree cond) 572 { 573 if (!flow_bb_inside_loop_p (loop, e->dest)) 574 return; 575 576 if (!is_true_predicate (prev_cond)) 577 cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, 578 prev_cond, cond); 579 580 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, e->dest)) 581 add_to_predicate_list (loop, e->dest, cond); 582 } 583 584 /* Return true if one of the successor edges of BB exits LOOP. */ 585 586 static bool 587 bb_with_exit_edge_p (struct loop *loop, basic_block bb) 588 { 589 edge e; 590 edge_iterator ei; 591 592 FOR_EACH_EDGE (e, ei, bb->succs) 593 if (loop_exit_edge_p (loop, e)) 594 return true; 595 596 return false; 597 } 598 599 /* Given PHI which has more than two arguments, this function checks if 600 it's if-convertible by degenerating its arguments. Specifically, if 601 below two conditions are satisfied: 602 603 1) Number of PHI arguments with different values equals to 2 and one 604 argument has the only occurrence. 605 2) The edge corresponding to the unique argument isn't critical edge. 606 607 Such PHI can be handled as PHIs have only two arguments. For example, 608 below PHI: 609 610 res = PHI <A_1(e1), A_1(e2), A_2(e3)>; 611 612 can be transformed into: 613 614 res = (predicate of e3) ? A_2 : A_1; 615 616 Return TRUE if it is the case, FALSE otherwise. */ 617 618 static bool 619 phi_convertible_by_degenerating_args (gphi *phi) 620 { 621 edge e; 622 tree arg, t1 = NULL, t2 = NULL; 623 unsigned int i, i1 = 0, i2 = 0, n1 = 0, n2 = 0; 624 unsigned int num_args = gimple_phi_num_args (phi); 625 626 gcc_assert (num_args > 2); 627 628 for (i = 0; i < num_args; i++) 629 { 630 arg = gimple_phi_arg_def (phi, i); 631 if (t1 == NULL || operand_equal_p (t1, arg, 0)) 632 { 633 n1++; 634 i1 = i; 635 t1 = arg; 636 } 637 else if (t2 == NULL || operand_equal_p (t2, arg, 0)) 638 { 639 n2++; 640 i2 = i; 641 t2 = arg; 642 } 643 else 644 return false; 645 } 646 647 if (n1 != 1 && n2 != 1) 648 return false; 649 650 /* Check if the edge corresponding to the unique arg is critical. */ 651 e = gimple_phi_arg_edge (phi, (n1 == 1) ? i1 : i2); 652 if (EDGE_COUNT (e->src->succs) > 1) 653 return false; 654 655 return true; 656 } 657 658 /* Return true when PHI is if-convertible. PHI is part of loop LOOP 659 and it belongs to basic block BB. Note at this point, it is sure 660 that PHI is if-convertible. This function updates global variable 661 ANY_COMPLICATED_PHI if PHI is complicated. */ 662 663 static bool 664 if_convertible_phi_p (struct loop *loop, basic_block bb, gphi *phi) 665 { 666 if (dump_file && (dump_flags & TDF_DETAILS)) 667 { 668 fprintf (dump_file, "-------------------------\n"); 669 print_gimple_stmt (dump_file, phi, 0, TDF_SLIM); 670 } 671 672 if (bb != loop->header 673 && gimple_phi_num_args (phi) > 2 674 && !phi_convertible_by_degenerating_args (phi)) 675 any_complicated_phi = true; 676 677 return true; 678 } 679 680 /* Records the status of a data reference. This struct is attached to 681 each DR->aux field. */ 682 683 struct ifc_dr { 684 bool rw_unconditionally; 685 bool w_unconditionally; 686 bool written_at_least_once; 687 688 tree rw_predicate; 689 tree w_predicate; 690 tree base_w_predicate; 691 }; 692 693 #define IFC_DR(DR) ((struct ifc_dr *) (DR)->aux) 694 #define DR_BASE_W_UNCONDITIONALLY(DR) (IFC_DR (DR)->written_at_least_once) 695 #define DR_RW_UNCONDITIONALLY(DR) (IFC_DR (DR)->rw_unconditionally) 696 #define DR_W_UNCONDITIONALLY(DR) (IFC_DR (DR)->w_unconditionally) 697 698 /* Iterates over DR's and stores refs, DR and base refs, DR pairs in 699 HASH tables. While storing them in HASH table, it checks if the 700 reference is unconditionally read or written and stores that as a flag 701 information. For base reference it checks if it is written atlest once 702 unconditionally and stores it as flag information along with DR. 703 In other words for every data reference A in STMT there exist other 704 accesses to a data reference with the same base with predicates that 705 add up (OR-up) to the true predicate: this ensures that the data 706 reference A is touched (read or written) on every iteration of the 707 if-converted loop. */ 708 static void 709 hash_memrefs_baserefs_and_store_DRs_read_written_info (data_reference_p a) 710 { 711 712 data_reference_p *master_dr, *base_master_dr; 713 tree base_ref = DR_BASE_OBJECT (a); 714 innermost_loop_behavior *innermost = &DR_INNERMOST (a); 715 tree ca = bb_predicate (gimple_bb (DR_STMT (a))); 716 bool exist1, exist2; 717 718 master_dr = &innermost_DR_map->get_or_insert (innermost, &exist1); 719 if (!exist1) 720 *master_dr = a; 721 722 if (DR_IS_WRITE (a)) 723 { 724 IFC_DR (*master_dr)->w_predicate 725 = fold_or_predicates (UNKNOWN_LOCATION, ca, 726 IFC_DR (*master_dr)->w_predicate); 727 if (is_true_predicate (IFC_DR (*master_dr)->w_predicate)) 728 DR_W_UNCONDITIONALLY (*master_dr) = true; 729 } 730 IFC_DR (*master_dr)->rw_predicate 731 = fold_or_predicates (UNKNOWN_LOCATION, ca, 732 IFC_DR (*master_dr)->rw_predicate); 733 if (is_true_predicate (IFC_DR (*master_dr)->rw_predicate)) 734 DR_RW_UNCONDITIONALLY (*master_dr) = true; 735 736 if (DR_IS_WRITE (a)) 737 { 738 base_master_dr = &baseref_DR_map->get_or_insert (base_ref, &exist2); 739 if (!exist2) 740 *base_master_dr = a; 741 IFC_DR (*base_master_dr)->base_w_predicate 742 = fold_or_predicates (UNKNOWN_LOCATION, ca, 743 IFC_DR (*base_master_dr)->base_w_predicate); 744 if (is_true_predicate (IFC_DR (*base_master_dr)->base_w_predicate)) 745 DR_BASE_W_UNCONDITIONALLY (*base_master_dr) = true; 746 } 747 } 748 749 /* Return TRUE if can prove the index IDX of an array reference REF is 750 within array bound. Return false otherwise. */ 751 752 static bool 753 idx_within_array_bound (tree ref, tree *idx, void *dta) 754 { 755 wi::overflow_type overflow; 756 widest_int niter, valid_niter, delta, wi_step; 757 tree ev, init, step; 758 tree low, high; 759 struct loop *loop = (struct loop*) dta; 760 761 /* Only support within-bound access for array references. */ 762 if (TREE_CODE (ref) != ARRAY_REF) 763 return false; 764 765 /* For arrays at the end of the structure, we are not guaranteed that they 766 do not really extend over their declared size. However, for arrays of 767 size greater than one, this is unlikely to be intended. */ 768 if (array_at_struct_end_p (ref)) 769 return false; 770 771 ev = analyze_scalar_evolution (loop, *idx); 772 ev = instantiate_parameters (loop, ev); 773 init = initial_condition (ev); 774 step = evolution_part_in_loop_num (ev, loop->num); 775 776 if (!init || TREE_CODE (init) != INTEGER_CST 777 || (step && TREE_CODE (step) != INTEGER_CST)) 778 return false; 779 780 low = array_ref_low_bound (ref); 781 high = array_ref_up_bound (ref); 782 783 /* The case of nonconstant bounds could be handled, but it would be 784 complicated. */ 785 if (TREE_CODE (low) != INTEGER_CST 786 || !high || TREE_CODE (high) != INTEGER_CST) 787 return false; 788 789 /* Check if the intial idx is within bound. */ 790 if (wi::to_widest (init) < wi::to_widest (low) 791 || wi::to_widest (init) > wi::to_widest (high)) 792 return false; 793 794 /* The idx is always within bound. */ 795 if (!step || integer_zerop (step)) 796 return true; 797 798 if (!max_loop_iterations (loop, &niter)) 799 return false; 800 801 if (wi::to_widest (step) < 0) 802 { 803 delta = wi::to_widest (init) - wi::to_widest (low); 804 wi_step = -wi::to_widest (step); 805 } 806 else 807 { 808 delta = wi::to_widest (high) - wi::to_widest (init); 809 wi_step = wi::to_widest (step); 810 } 811 812 valid_niter = wi::div_floor (delta, wi_step, SIGNED, &overflow); 813 /* The iteration space of idx is within array bound. */ 814 if (!overflow && niter <= valid_niter) 815 return true; 816 817 return false; 818 } 819 820 /* Return TRUE if ref is a within bound array reference. */ 821 822 static bool 823 ref_within_array_bound (gimple *stmt, tree ref) 824 { 825 struct loop *loop = loop_containing_stmt (stmt); 826 827 gcc_assert (loop != NULL); 828 return for_each_index (&ref, idx_within_array_bound, loop); 829 } 830 831 832 /* Given a memory reference expression T, return TRUE if base object 833 it refers to is writable. The base object of a memory reference 834 is the main object being referenced, which is returned by function 835 get_base_address. */ 836 837 static bool 838 base_object_writable (tree ref) 839 { 840 tree base_tree = get_base_address (ref); 841 842 return (base_tree 843 && DECL_P (base_tree) 844 && decl_binds_to_current_def_p (base_tree) 845 && !TREE_READONLY (base_tree)); 846 } 847 848 /* Return true when the memory references of STMT won't trap in the 849 if-converted code. There are two things that we have to check for: 850 851 - writes to memory occur to writable memory: if-conversion of 852 memory writes transforms the conditional memory writes into 853 unconditional writes, i.e. "if (cond) A[i] = foo" is transformed 854 into "A[i] = cond ? foo : A[i]", and as the write to memory may not 855 be executed at all in the original code, it may be a readonly 856 memory. To check that A is not const-qualified, we check that 857 there exists at least an unconditional write to A in the current 858 function. 859 860 - reads or writes to memory are valid memory accesses for every 861 iteration. To check that the memory accesses are correctly formed 862 and that we are allowed to read and write in these locations, we 863 check that the memory accesses to be if-converted occur at every 864 iteration unconditionally. 865 866 Returns true for the memory reference in STMT, same memory reference 867 is read or written unconditionally atleast once and the base memory 868 reference is written unconditionally once. This is to check reference 869 will not write fault. Also retuns true if the memory reference is 870 unconditionally read once then we are conditionally writing to memory 871 which is defined as read and write and is bound to the definition 872 we are seeing. */ 873 static bool 874 ifcvt_memrefs_wont_trap (gimple *stmt, vec<data_reference_p> drs) 875 { 876 /* If DR didn't see a reference here we can't use it to tell 877 whether the ref traps or not. */ 878 if (gimple_uid (stmt) == 0) 879 return false; 880 881 data_reference_p *master_dr, *base_master_dr; 882 data_reference_p a = drs[gimple_uid (stmt) - 1]; 883 884 tree base = DR_BASE_OBJECT (a); 885 innermost_loop_behavior *innermost = &DR_INNERMOST (a); 886 887 gcc_assert (DR_STMT (a) == stmt); 888 gcc_assert (DR_BASE_ADDRESS (a) || DR_OFFSET (a) 889 || DR_INIT (a) || DR_STEP (a)); 890 891 master_dr = innermost_DR_map->get (innermost); 892 gcc_assert (master_dr != NULL); 893 894 base_master_dr = baseref_DR_map->get (base); 895 896 /* If a is unconditionally written to it doesn't trap. */ 897 if (DR_W_UNCONDITIONALLY (*master_dr)) 898 return true; 899 900 /* If a is unconditionally accessed then ... 901 902 Even a is conditional access, we can treat it as an unconditional 903 one if it's an array reference and all its index are within array 904 bound. */ 905 if (DR_RW_UNCONDITIONALLY (*master_dr) 906 || ref_within_array_bound (stmt, DR_REF (a))) 907 { 908 /* an unconditional read won't trap. */ 909 if (DR_IS_READ (a)) 910 return true; 911 912 /* an unconditionaly write won't trap if the base is written 913 to unconditionally. */ 914 if (base_master_dr 915 && DR_BASE_W_UNCONDITIONALLY (*base_master_dr)) 916 return PARAM_VALUE (PARAM_ALLOW_STORE_DATA_RACES); 917 /* or the base is known to be not readonly. */ 918 else if (base_object_writable (DR_REF (a))) 919 return PARAM_VALUE (PARAM_ALLOW_STORE_DATA_RACES); 920 } 921 922 return false; 923 } 924 925 /* Return true if STMT could be converted into a masked load or store 926 (conditional load or store based on a mask computed from bb predicate). */ 927 928 static bool 929 ifcvt_can_use_mask_load_store (gimple *stmt) 930 { 931 /* Check whether this is a load or store. */ 932 tree lhs = gimple_assign_lhs (stmt); 933 bool is_load; 934 tree ref; 935 if (gimple_store_p (stmt)) 936 { 937 if (!is_gimple_val (gimple_assign_rhs1 (stmt))) 938 return false; 939 is_load = false; 940 ref = lhs; 941 } 942 else if (gimple_assign_load_p (stmt)) 943 { 944 is_load = true; 945 ref = gimple_assign_rhs1 (stmt); 946 } 947 else 948 return false; 949 950 if (may_be_nonaddressable_p (ref)) 951 return false; 952 953 /* Mask should be integer mode of the same size as the load/store 954 mode. */ 955 machine_mode mode = TYPE_MODE (TREE_TYPE (lhs)); 956 if (!int_mode_for_mode (mode).exists () || VECTOR_MODE_P (mode)) 957 return false; 958 959 if (can_vec_mask_load_store_p (mode, VOIDmode, is_load)) 960 return true; 961 962 return false; 963 } 964 965 /* Return true if STMT could be converted from an operation that is 966 unconditional to one that is conditional on a bb predicate mask. */ 967 968 static bool 969 ifcvt_can_predicate (gimple *stmt) 970 { 971 basic_block bb = gimple_bb (stmt); 972 973 if (!(flag_tree_loop_vectorize || bb->loop_father->force_vectorize) 974 || bb->loop_father->dont_vectorize 975 || gimple_has_volatile_ops (stmt)) 976 return false; 977 978 if (gimple_assign_single_p (stmt)) 979 return ifcvt_can_use_mask_load_store (stmt); 980 981 tree_code code = gimple_assign_rhs_code (stmt); 982 tree lhs_type = TREE_TYPE (gimple_assign_lhs (stmt)); 983 tree rhs_type = TREE_TYPE (gimple_assign_rhs1 (stmt)); 984 if (!types_compatible_p (lhs_type, rhs_type)) 985 return false; 986 internal_fn cond_fn = get_conditional_internal_fn (code); 987 return (cond_fn != IFN_LAST 988 && vectorized_internal_fn_supported_p (cond_fn, lhs_type)); 989 } 990 991 /* Return true when STMT is if-convertible. 992 993 GIMPLE_ASSIGN statement is not if-convertible if, 994 - it is not movable, 995 - it could trap, 996 - LHS is not var decl. */ 997 998 static bool 999 if_convertible_gimple_assign_stmt_p (gimple *stmt, 1000 vec<data_reference_p> refs) 1001 { 1002 tree lhs = gimple_assign_lhs (stmt); 1003 1004 if (dump_file && (dump_flags & TDF_DETAILS)) 1005 { 1006 fprintf (dump_file, "-------------------------\n"); 1007 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 1008 } 1009 1010 if (!is_gimple_reg_type (TREE_TYPE (lhs))) 1011 return false; 1012 1013 /* Some of these constrains might be too conservative. */ 1014 if (stmt_ends_bb_p (stmt) 1015 || gimple_has_volatile_ops (stmt) 1016 || (TREE_CODE (lhs) == SSA_NAME 1017 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs)) 1018 || gimple_has_side_effects (stmt)) 1019 { 1020 if (dump_file && (dump_flags & TDF_DETAILS)) 1021 fprintf (dump_file, "stmt not suitable for ifcvt\n"); 1022 return false; 1023 } 1024 1025 /* tree-into-ssa.c uses GF_PLF_1, so avoid it, because 1026 in between if_convertible_loop_p and combine_blocks 1027 we can perform loop versioning. */ 1028 gimple_set_plf (stmt, GF_PLF_2, false); 1029 1030 if ((! gimple_vuse (stmt) 1031 || gimple_could_trap_p_1 (stmt, false, false) 1032 || ! ifcvt_memrefs_wont_trap (stmt, refs)) 1033 && gimple_could_trap_p (stmt)) 1034 { 1035 if (ifcvt_can_predicate (stmt)) 1036 { 1037 gimple_set_plf (stmt, GF_PLF_2, true); 1038 need_to_predicate = true; 1039 return true; 1040 } 1041 if (dump_file && (dump_flags & TDF_DETAILS)) 1042 fprintf (dump_file, "tree could trap...\n"); 1043 return false; 1044 } 1045 1046 /* When if-converting stores force versioning, likewise if we 1047 ended up generating store data races. */ 1048 if (gimple_vdef (stmt)) 1049 need_to_predicate = true; 1050 1051 return true; 1052 } 1053 1054 /* Return true when STMT is if-convertible. 1055 1056 A statement is if-convertible if: 1057 - it is an if-convertible GIMPLE_ASSIGN, 1058 - it is a GIMPLE_LABEL or a GIMPLE_COND, 1059 - it is builtins call. */ 1060 1061 static bool 1062 if_convertible_stmt_p (gimple *stmt, vec<data_reference_p> refs) 1063 { 1064 switch (gimple_code (stmt)) 1065 { 1066 case GIMPLE_LABEL: 1067 case GIMPLE_DEBUG: 1068 case GIMPLE_COND: 1069 return true; 1070 1071 case GIMPLE_ASSIGN: 1072 return if_convertible_gimple_assign_stmt_p (stmt, refs); 1073 1074 case GIMPLE_CALL: 1075 { 1076 tree fndecl = gimple_call_fndecl (stmt); 1077 if (fndecl) 1078 { 1079 int flags = gimple_call_flags (stmt); 1080 if ((flags & ECF_CONST) 1081 && !(flags & ECF_LOOPING_CONST_OR_PURE) 1082 /* We can only vectorize some builtins at the moment, 1083 so restrict if-conversion to those. */ 1084 && fndecl_built_in_p (fndecl)) 1085 return true; 1086 } 1087 return false; 1088 } 1089 1090 default: 1091 /* Don't know what to do with 'em so don't do anything. */ 1092 if (dump_file && (dump_flags & TDF_DETAILS)) 1093 { 1094 fprintf (dump_file, "don't know what to do\n"); 1095 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 1096 } 1097 return false; 1098 } 1099 1100 return true; 1101 } 1102 1103 /* Assumes that BB has more than 1 predecessors. 1104 Returns false if at least one successor is not on critical edge 1105 and true otherwise. */ 1106 1107 static inline bool 1108 all_preds_critical_p (basic_block bb) 1109 { 1110 edge e; 1111 edge_iterator ei; 1112 1113 FOR_EACH_EDGE (e, ei, bb->preds) 1114 if (EDGE_COUNT (e->src->succs) == 1) 1115 return false; 1116 return true; 1117 } 1118 1119 /* Return true when BB is if-convertible. This routine does not check 1120 basic block's statements and phis. 1121 1122 A basic block is not if-convertible if: 1123 - it is non-empty and it is after the exit block (in BFS order), 1124 - it is after the exit block but before the latch, 1125 - its edges are not normal. 1126 1127 EXIT_BB is the basic block containing the exit of the LOOP. BB is 1128 inside LOOP. */ 1129 1130 static bool 1131 if_convertible_bb_p (struct loop *loop, basic_block bb, basic_block exit_bb) 1132 { 1133 edge e; 1134 edge_iterator ei; 1135 1136 if (dump_file && (dump_flags & TDF_DETAILS)) 1137 fprintf (dump_file, "----------[%d]-------------\n", bb->index); 1138 1139 if (EDGE_COUNT (bb->succs) > 2) 1140 return false; 1141 1142 if (exit_bb) 1143 { 1144 if (bb != loop->latch) 1145 { 1146 if (dump_file && (dump_flags & TDF_DETAILS)) 1147 fprintf (dump_file, "basic block after exit bb but before latch\n"); 1148 return false; 1149 } 1150 else if (!empty_block_p (bb)) 1151 { 1152 if (dump_file && (dump_flags & TDF_DETAILS)) 1153 fprintf (dump_file, "non empty basic block after exit bb\n"); 1154 return false; 1155 } 1156 else if (bb == loop->latch 1157 && bb != exit_bb 1158 && !dominated_by_p (CDI_DOMINATORS, bb, exit_bb)) 1159 { 1160 if (dump_file && (dump_flags & TDF_DETAILS)) 1161 fprintf (dump_file, "latch is not dominated by exit_block\n"); 1162 return false; 1163 } 1164 } 1165 1166 /* Be less adventurous and handle only normal edges. */ 1167 FOR_EACH_EDGE (e, ei, bb->succs) 1168 if (e->flags & (EDGE_EH | EDGE_ABNORMAL | EDGE_IRREDUCIBLE_LOOP)) 1169 { 1170 if (dump_file && (dump_flags & TDF_DETAILS)) 1171 fprintf (dump_file, "Difficult to handle edges\n"); 1172 return false; 1173 } 1174 1175 return true; 1176 } 1177 1178 /* Return true when all predecessor blocks of BB are visited. The 1179 VISITED bitmap keeps track of the visited blocks. */ 1180 1181 static bool 1182 pred_blocks_visited_p (basic_block bb, bitmap *visited) 1183 { 1184 edge e; 1185 edge_iterator ei; 1186 FOR_EACH_EDGE (e, ei, bb->preds) 1187 if (!bitmap_bit_p (*visited, e->src->index)) 1188 return false; 1189 1190 return true; 1191 } 1192 1193 /* Get body of a LOOP in suitable order for if-conversion. It is 1194 caller's responsibility to deallocate basic block list. 1195 If-conversion suitable order is, breadth first sort (BFS) order 1196 with an additional constraint: select a block only if all its 1197 predecessors are already selected. */ 1198 1199 static basic_block * 1200 get_loop_body_in_if_conv_order (const struct loop *loop) 1201 { 1202 basic_block *blocks, *blocks_in_bfs_order; 1203 basic_block bb; 1204 bitmap visited; 1205 unsigned int index = 0; 1206 unsigned int visited_count = 0; 1207 1208 gcc_assert (loop->num_nodes); 1209 gcc_assert (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun)); 1210 1211 blocks = XCNEWVEC (basic_block, loop->num_nodes); 1212 visited = BITMAP_ALLOC (NULL); 1213 1214 blocks_in_bfs_order = get_loop_body_in_bfs_order (loop); 1215 1216 index = 0; 1217 while (index < loop->num_nodes) 1218 { 1219 bb = blocks_in_bfs_order [index]; 1220 1221 if (bb->flags & BB_IRREDUCIBLE_LOOP) 1222 { 1223 free (blocks_in_bfs_order); 1224 BITMAP_FREE (visited); 1225 free (blocks); 1226 return NULL; 1227 } 1228 1229 if (!bitmap_bit_p (visited, bb->index)) 1230 { 1231 if (pred_blocks_visited_p (bb, &visited) 1232 || bb == loop->header) 1233 { 1234 /* This block is now visited. */ 1235 bitmap_set_bit (visited, bb->index); 1236 blocks[visited_count++] = bb; 1237 } 1238 } 1239 1240 index++; 1241 1242 if (index == loop->num_nodes 1243 && visited_count != loop->num_nodes) 1244 /* Not done yet. */ 1245 index = 0; 1246 } 1247 free (blocks_in_bfs_order); 1248 BITMAP_FREE (visited); 1249 return blocks; 1250 } 1251 1252 /* Returns true when the analysis of the predicates for all the basic 1253 blocks in LOOP succeeded. 1254 1255 predicate_bbs first allocates the predicates of the basic blocks. 1256 These fields are then initialized with the tree expressions 1257 representing the predicates under which a basic block is executed 1258 in the LOOP. As the loop->header is executed at each iteration, it 1259 has the "true" predicate. Other statements executed under a 1260 condition are predicated with that condition, for example 1261 1262 | if (x) 1263 | S1; 1264 | else 1265 | S2; 1266 1267 S1 will be predicated with "x", and 1268 S2 will be predicated with "!x". */ 1269 1270 static void 1271 predicate_bbs (loop_p loop) 1272 { 1273 unsigned int i; 1274 1275 for (i = 0; i < loop->num_nodes; i++) 1276 init_bb_predicate (ifc_bbs[i]); 1277 1278 for (i = 0; i < loop->num_nodes; i++) 1279 { 1280 basic_block bb = ifc_bbs[i]; 1281 tree cond; 1282 gimple *stmt; 1283 1284 /* The loop latch and loop exit block are always executed and 1285 have no extra conditions to be processed: skip them. */ 1286 if (bb == loop->latch 1287 || bb_with_exit_edge_p (loop, bb)) 1288 { 1289 reset_bb_predicate (bb); 1290 continue; 1291 } 1292 1293 cond = bb_predicate (bb); 1294 stmt = last_stmt (bb); 1295 if (stmt && gimple_code (stmt) == GIMPLE_COND) 1296 { 1297 tree c2; 1298 edge true_edge, false_edge; 1299 location_t loc = gimple_location (stmt); 1300 tree c = build2_loc (loc, gimple_cond_code (stmt), 1301 boolean_type_node, 1302 gimple_cond_lhs (stmt), 1303 gimple_cond_rhs (stmt)); 1304 1305 /* Add new condition into destination's predicate list. */ 1306 extract_true_false_edges_from_block (gimple_bb (stmt), 1307 &true_edge, &false_edge); 1308 1309 /* If C is true, then TRUE_EDGE is taken. */ 1310 add_to_dst_predicate_list (loop, true_edge, unshare_expr (cond), 1311 unshare_expr (c)); 1312 1313 /* If C is false, then FALSE_EDGE is taken. */ 1314 c2 = build1_loc (loc, TRUTH_NOT_EXPR, boolean_type_node, 1315 unshare_expr (c)); 1316 add_to_dst_predicate_list (loop, false_edge, 1317 unshare_expr (cond), c2); 1318 1319 cond = NULL_TREE; 1320 } 1321 1322 /* If current bb has only one successor, then consider it as an 1323 unconditional goto. */ 1324 if (single_succ_p (bb)) 1325 { 1326 basic_block bb_n = single_succ (bb); 1327 1328 /* The successor bb inherits the predicate of its 1329 predecessor. If there is no predicate in the predecessor 1330 bb, then consider the successor bb as always executed. */ 1331 if (cond == NULL_TREE) 1332 cond = boolean_true_node; 1333 1334 add_to_predicate_list (loop, bb_n, cond); 1335 } 1336 } 1337 1338 /* The loop header is always executed. */ 1339 reset_bb_predicate (loop->header); 1340 gcc_assert (bb_predicate_gimplified_stmts (loop->header) == NULL 1341 && bb_predicate_gimplified_stmts (loop->latch) == NULL); 1342 } 1343 1344 /* Build region by adding loop pre-header and post-header blocks. */ 1345 1346 static vec<basic_block> 1347 build_region (struct loop *loop) 1348 { 1349 vec<basic_block> region = vNULL; 1350 basic_block exit_bb = NULL; 1351 1352 gcc_assert (ifc_bbs); 1353 /* The first element is loop pre-header. */ 1354 region.safe_push (loop_preheader_edge (loop)->src); 1355 1356 for (unsigned int i = 0; i < loop->num_nodes; i++) 1357 { 1358 basic_block bb = ifc_bbs[i]; 1359 region.safe_push (bb); 1360 /* Find loop postheader. */ 1361 edge e; 1362 edge_iterator ei; 1363 FOR_EACH_EDGE (e, ei, bb->succs) 1364 if (loop_exit_edge_p (loop, e)) 1365 { 1366 exit_bb = e->dest; 1367 break; 1368 } 1369 } 1370 /* The last element is loop post-header. */ 1371 gcc_assert (exit_bb); 1372 region.safe_push (exit_bb); 1373 return region; 1374 } 1375 1376 /* Return true when LOOP is if-convertible. This is a helper function 1377 for if_convertible_loop_p. REFS and DDRS are initialized and freed 1378 in if_convertible_loop_p. */ 1379 1380 static bool 1381 if_convertible_loop_p_1 (struct loop *loop, vec<data_reference_p> *refs) 1382 { 1383 unsigned int i; 1384 basic_block exit_bb = NULL; 1385 vec<basic_block> region; 1386 1387 if (find_data_references_in_loop (loop, refs) == chrec_dont_know) 1388 return false; 1389 1390 calculate_dominance_info (CDI_DOMINATORS); 1391 1392 /* Allow statements that can be handled during if-conversion. */ 1393 ifc_bbs = get_loop_body_in_if_conv_order (loop); 1394 if (!ifc_bbs) 1395 { 1396 if (dump_file && (dump_flags & TDF_DETAILS)) 1397 fprintf (dump_file, "Irreducible loop\n"); 1398 return false; 1399 } 1400 1401 for (i = 0; i < loop->num_nodes; i++) 1402 { 1403 basic_block bb = ifc_bbs[i]; 1404 1405 if (!if_convertible_bb_p (loop, bb, exit_bb)) 1406 return false; 1407 1408 if (bb_with_exit_edge_p (loop, bb)) 1409 exit_bb = bb; 1410 } 1411 1412 for (i = 0; i < loop->num_nodes; i++) 1413 { 1414 basic_block bb = ifc_bbs[i]; 1415 gimple_stmt_iterator gsi; 1416 1417 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 1418 switch (gimple_code (gsi_stmt (gsi))) 1419 { 1420 case GIMPLE_LABEL: 1421 case GIMPLE_ASSIGN: 1422 case GIMPLE_CALL: 1423 case GIMPLE_DEBUG: 1424 case GIMPLE_COND: 1425 gimple_set_uid (gsi_stmt (gsi), 0); 1426 break; 1427 default: 1428 return false; 1429 } 1430 } 1431 1432 data_reference_p dr; 1433 1434 innermost_DR_map 1435 = new hash_map<innermost_loop_behavior_hash, data_reference_p>; 1436 baseref_DR_map = new hash_map<tree_operand_hash, data_reference_p>; 1437 1438 /* Compute post-dominator tree locally. */ 1439 region = build_region (loop); 1440 calculate_dominance_info_for_region (CDI_POST_DOMINATORS, region); 1441 1442 predicate_bbs (loop); 1443 1444 /* Free post-dominator tree since it is not used after predication. */ 1445 free_dominance_info_for_region (cfun, CDI_POST_DOMINATORS, region); 1446 region.release (); 1447 1448 for (i = 0; refs->iterate (i, &dr); i++) 1449 { 1450 tree ref = DR_REF (dr); 1451 1452 dr->aux = XNEW (struct ifc_dr); 1453 DR_BASE_W_UNCONDITIONALLY (dr) = false; 1454 DR_RW_UNCONDITIONALLY (dr) = false; 1455 DR_W_UNCONDITIONALLY (dr) = false; 1456 IFC_DR (dr)->rw_predicate = boolean_false_node; 1457 IFC_DR (dr)->w_predicate = boolean_false_node; 1458 IFC_DR (dr)->base_w_predicate = boolean_false_node; 1459 if (gimple_uid (DR_STMT (dr)) == 0) 1460 gimple_set_uid (DR_STMT (dr), i + 1); 1461 1462 /* If DR doesn't have innermost loop behavior or it's a compound 1463 memory reference, we synthesize its innermost loop behavior 1464 for hashing. */ 1465 if (TREE_CODE (ref) == COMPONENT_REF 1466 || TREE_CODE (ref) == IMAGPART_EXPR 1467 || TREE_CODE (ref) == REALPART_EXPR 1468 || !(DR_BASE_ADDRESS (dr) || DR_OFFSET (dr) 1469 || DR_INIT (dr) || DR_STEP (dr))) 1470 { 1471 while (TREE_CODE (ref) == COMPONENT_REF 1472 || TREE_CODE (ref) == IMAGPART_EXPR 1473 || TREE_CODE (ref) == REALPART_EXPR) 1474 ref = TREE_OPERAND (ref, 0); 1475 1476 memset (&DR_INNERMOST (dr), 0, sizeof (DR_INNERMOST (dr))); 1477 DR_BASE_ADDRESS (dr) = ref; 1478 } 1479 hash_memrefs_baserefs_and_store_DRs_read_written_info (dr); 1480 } 1481 1482 for (i = 0; i < loop->num_nodes; i++) 1483 { 1484 basic_block bb = ifc_bbs[i]; 1485 gimple_stmt_iterator itr; 1486 1487 /* Check the if-convertibility of statements in predicated BBs. */ 1488 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb)) 1489 for (itr = gsi_start_bb (bb); !gsi_end_p (itr); gsi_next (&itr)) 1490 if (!if_convertible_stmt_p (gsi_stmt (itr), *refs)) 1491 return false; 1492 } 1493 1494 /* Checking PHIs needs to be done after stmts, as the fact whether there 1495 are any masked loads or stores affects the tests. */ 1496 for (i = 0; i < loop->num_nodes; i++) 1497 { 1498 basic_block bb = ifc_bbs[i]; 1499 gphi_iterator itr; 1500 1501 for (itr = gsi_start_phis (bb); !gsi_end_p (itr); gsi_next (&itr)) 1502 if (!if_convertible_phi_p (loop, bb, itr.phi ())) 1503 return false; 1504 } 1505 1506 if (dump_file) 1507 fprintf (dump_file, "Applying if-conversion\n"); 1508 1509 return true; 1510 } 1511 1512 /* Return true when LOOP is if-convertible. 1513 LOOP is if-convertible if: 1514 - it is innermost, 1515 - it has two or more basic blocks, 1516 - it has only one exit, 1517 - loop header is not the exit edge, 1518 - if its basic blocks and phi nodes are if convertible. */ 1519 1520 static bool 1521 if_convertible_loop_p (struct loop *loop) 1522 { 1523 edge e; 1524 edge_iterator ei; 1525 bool res = false; 1526 vec<data_reference_p> refs; 1527 1528 /* Handle only innermost loop. */ 1529 if (!loop || loop->inner) 1530 { 1531 if (dump_file && (dump_flags & TDF_DETAILS)) 1532 fprintf (dump_file, "not innermost loop\n"); 1533 return false; 1534 } 1535 1536 /* If only one block, no need for if-conversion. */ 1537 if (loop->num_nodes <= 2) 1538 { 1539 if (dump_file && (dump_flags & TDF_DETAILS)) 1540 fprintf (dump_file, "less than 2 basic blocks\n"); 1541 return false; 1542 } 1543 1544 /* More than one loop exit is too much to handle. */ 1545 if (!single_exit (loop)) 1546 { 1547 if (dump_file && (dump_flags & TDF_DETAILS)) 1548 fprintf (dump_file, "multiple exits\n"); 1549 return false; 1550 } 1551 1552 /* If one of the loop header's edge is an exit edge then do not 1553 apply if-conversion. */ 1554 FOR_EACH_EDGE (e, ei, loop->header->succs) 1555 if (loop_exit_edge_p (loop, e)) 1556 return false; 1557 1558 refs.create (5); 1559 res = if_convertible_loop_p_1 (loop, &refs); 1560 1561 data_reference_p dr; 1562 unsigned int i; 1563 for (i = 0; refs.iterate (i, &dr); i++) 1564 free (dr->aux); 1565 1566 free_data_refs (refs); 1567 1568 delete innermost_DR_map; 1569 innermost_DR_map = NULL; 1570 1571 delete baseref_DR_map; 1572 baseref_DR_map = NULL; 1573 1574 return res; 1575 } 1576 1577 /* Returns true if def-stmt for phi argument ARG is simple increment/decrement 1578 which is in predicated basic block. 1579 In fact, the following PHI pattern is searching: 1580 loop-header: 1581 reduc_1 = PHI <..., reduc_2> 1582 ... 1583 if (...) 1584 reduc_3 = ... 1585 reduc_2 = PHI <reduc_1, reduc_3> 1586 1587 ARG_0 and ARG_1 are correspondent PHI arguments. 1588 REDUC, OP0 and OP1 contain reduction stmt and its operands. 1589 EXTENDED is true if PHI has > 2 arguments. */ 1590 1591 static bool 1592 is_cond_scalar_reduction (gimple *phi, gimple **reduc, tree arg_0, tree arg_1, 1593 tree *op0, tree *op1, bool extended) 1594 { 1595 tree lhs, r_op1, r_op2; 1596 gimple *stmt; 1597 gimple *header_phi = NULL; 1598 enum tree_code reduction_op; 1599 basic_block bb = gimple_bb (phi); 1600 struct loop *loop = bb->loop_father; 1601 edge latch_e = loop_latch_edge (loop); 1602 imm_use_iterator imm_iter; 1603 use_operand_p use_p; 1604 edge e; 1605 edge_iterator ei; 1606 bool result = false; 1607 if (TREE_CODE (arg_0) != SSA_NAME || TREE_CODE (arg_1) != SSA_NAME) 1608 return false; 1609 1610 if (!extended && gimple_code (SSA_NAME_DEF_STMT (arg_0)) == GIMPLE_PHI) 1611 { 1612 lhs = arg_1; 1613 header_phi = SSA_NAME_DEF_STMT (arg_0); 1614 stmt = SSA_NAME_DEF_STMT (arg_1); 1615 } 1616 else if (gimple_code (SSA_NAME_DEF_STMT (arg_1)) == GIMPLE_PHI) 1617 { 1618 lhs = arg_0; 1619 header_phi = SSA_NAME_DEF_STMT (arg_1); 1620 stmt = SSA_NAME_DEF_STMT (arg_0); 1621 } 1622 else 1623 return false; 1624 if (gimple_bb (header_phi) != loop->header) 1625 return false; 1626 1627 if (PHI_ARG_DEF_FROM_EDGE (header_phi, latch_e) != PHI_RESULT (phi)) 1628 return false; 1629 1630 if (gimple_code (stmt) != GIMPLE_ASSIGN 1631 || gimple_has_volatile_ops (stmt)) 1632 return false; 1633 1634 if (!flow_bb_inside_loop_p (loop, gimple_bb (stmt))) 1635 return false; 1636 1637 if (!is_predicated (gimple_bb (stmt))) 1638 return false; 1639 1640 /* Check that stmt-block is predecessor of phi-block. */ 1641 FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->succs) 1642 if (e->dest == bb) 1643 { 1644 result = true; 1645 break; 1646 } 1647 if (!result) 1648 return false; 1649 1650 if (!has_single_use (lhs)) 1651 return false; 1652 1653 reduction_op = gimple_assign_rhs_code (stmt); 1654 if (reduction_op != PLUS_EXPR && reduction_op != MINUS_EXPR) 1655 return false; 1656 r_op1 = gimple_assign_rhs1 (stmt); 1657 r_op2 = gimple_assign_rhs2 (stmt); 1658 1659 /* Make R_OP1 to hold reduction variable. */ 1660 if (r_op2 == PHI_RESULT (header_phi) 1661 && reduction_op == PLUS_EXPR) 1662 std::swap (r_op1, r_op2); 1663 else if (r_op1 != PHI_RESULT (header_phi)) 1664 return false; 1665 1666 /* Check that R_OP1 is used in reduction stmt or in PHI only. */ 1667 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, r_op1) 1668 { 1669 gimple *use_stmt = USE_STMT (use_p); 1670 if (is_gimple_debug (use_stmt)) 1671 continue; 1672 if (use_stmt == stmt) 1673 continue; 1674 if (gimple_code (use_stmt) != GIMPLE_PHI) 1675 return false; 1676 } 1677 1678 *op0 = r_op1; *op1 = r_op2; 1679 *reduc = stmt; 1680 return true; 1681 } 1682 1683 /* Converts conditional scalar reduction into unconditional form, e.g. 1684 bb_4 1685 if (_5 != 0) goto bb_5 else goto bb_6 1686 end_bb_4 1687 bb_5 1688 res_6 = res_13 + 1; 1689 end_bb_5 1690 bb_6 1691 # res_2 = PHI <res_13(4), res_6(5)> 1692 end_bb_6 1693 1694 will be converted into sequence 1695 _ifc__1 = _5 != 0 ? 1 : 0; 1696 res_2 = res_13 + _ifc__1; 1697 Argument SWAP tells that arguments of conditional expression should be 1698 swapped. 1699 Returns rhs of resulting PHI assignment. */ 1700 1701 static tree 1702 convert_scalar_cond_reduction (gimple *reduc, gimple_stmt_iterator *gsi, 1703 tree cond, tree op0, tree op1, bool swap) 1704 { 1705 gimple_stmt_iterator stmt_it; 1706 gimple *new_assign; 1707 tree rhs; 1708 tree rhs1 = gimple_assign_rhs1 (reduc); 1709 tree tmp = make_temp_ssa_name (TREE_TYPE (rhs1), NULL, "_ifc_"); 1710 tree c; 1711 tree zero = build_zero_cst (TREE_TYPE (rhs1)); 1712 1713 if (dump_file && (dump_flags & TDF_DETAILS)) 1714 { 1715 fprintf (dump_file, "Found cond scalar reduction.\n"); 1716 print_gimple_stmt (dump_file, reduc, 0, TDF_SLIM); 1717 } 1718 1719 /* Build cond expression using COND and constant operand 1720 of reduction rhs. */ 1721 c = fold_build_cond_expr (TREE_TYPE (rhs1), 1722 unshare_expr (cond), 1723 swap ? zero : op1, 1724 swap ? op1 : zero); 1725 1726 /* Create assignment stmt and insert it at GSI. */ 1727 new_assign = gimple_build_assign (tmp, c); 1728 gsi_insert_before (gsi, new_assign, GSI_SAME_STMT); 1729 /* Build rhs for unconditional increment/decrement. */ 1730 rhs = fold_build2 (gimple_assign_rhs_code (reduc), 1731 TREE_TYPE (rhs1), op0, tmp); 1732 1733 /* Delete original reduction stmt. */ 1734 stmt_it = gsi_for_stmt (reduc); 1735 gsi_remove (&stmt_it, true); 1736 release_defs (reduc); 1737 return rhs; 1738 } 1739 1740 /* Produce condition for all occurrences of ARG in PHI node. */ 1741 1742 static tree 1743 gen_phi_arg_condition (gphi *phi, vec<int> *occur, 1744 gimple_stmt_iterator *gsi) 1745 { 1746 int len; 1747 int i; 1748 tree cond = NULL_TREE; 1749 tree c; 1750 edge e; 1751 1752 len = occur->length (); 1753 gcc_assert (len > 0); 1754 for (i = 0; i < len; i++) 1755 { 1756 e = gimple_phi_arg_edge (phi, (*occur)[i]); 1757 c = bb_predicate (e->src); 1758 if (is_true_predicate (c)) 1759 { 1760 cond = c; 1761 break; 1762 } 1763 c = force_gimple_operand_gsi_1 (gsi, unshare_expr (c), 1764 is_gimple_condexpr, NULL_TREE, 1765 true, GSI_SAME_STMT); 1766 if (cond != NULL_TREE) 1767 { 1768 /* Must build OR expression. */ 1769 cond = fold_or_predicates (EXPR_LOCATION (c), c, cond); 1770 cond = force_gimple_operand_gsi_1 (gsi, unshare_expr (cond), 1771 is_gimple_condexpr, NULL_TREE, 1772 true, GSI_SAME_STMT); 1773 } 1774 else 1775 cond = c; 1776 } 1777 gcc_assert (cond != NULL_TREE); 1778 return cond; 1779 } 1780 1781 /* Local valueization callback that follows all-use SSA edges. */ 1782 1783 static tree 1784 ifcvt_follow_ssa_use_edges (tree val) 1785 { 1786 return val; 1787 } 1788 1789 /* Replace a scalar PHI node with a COND_EXPR using COND as condition. 1790 This routine can handle PHI nodes with more than two arguments. 1791 1792 For example, 1793 S1: A = PHI <x1(1), x2(5)> 1794 is converted into, 1795 S2: A = cond ? x1 : x2; 1796 1797 The generated code is inserted at GSI that points to the top of 1798 basic block's statement list. 1799 If PHI node has more than two arguments a chain of conditional 1800 expression is produced. */ 1801 1802 1803 static void 1804 predicate_scalar_phi (gphi *phi, gimple_stmt_iterator *gsi) 1805 { 1806 gimple *new_stmt = NULL, *reduc; 1807 tree rhs, res, arg0, arg1, op0, op1, scev; 1808 tree cond; 1809 unsigned int index0; 1810 unsigned int max, args_len; 1811 edge e; 1812 basic_block bb; 1813 unsigned int i; 1814 1815 res = gimple_phi_result (phi); 1816 if (virtual_operand_p (res)) 1817 return; 1818 1819 if ((rhs = degenerate_phi_result (phi)) 1820 || ((scev = analyze_scalar_evolution (gimple_bb (phi)->loop_father, 1821 res)) 1822 && !chrec_contains_undetermined (scev) 1823 && scev != res 1824 && (rhs = gimple_phi_arg_def (phi, 0)))) 1825 { 1826 if (dump_file && (dump_flags & TDF_DETAILS)) 1827 { 1828 fprintf (dump_file, "Degenerate phi!\n"); 1829 print_gimple_stmt (dump_file, phi, 0, TDF_SLIM); 1830 } 1831 new_stmt = gimple_build_assign (res, rhs); 1832 gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT); 1833 update_stmt (new_stmt); 1834 return; 1835 } 1836 1837 bb = gimple_bb (phi); 1838 if (EDGE_COUNT (bb->preds) == 2) 1839 { 1840 /* Predicate ordinary PHI node with 2 arguments. */ 1841 edge first_edge, second_edge; 1842 basic_block true_bb; 1843 first_edge = EDGE_PRED (bb, 0); 1844 second_edge = EDGE_PRED (bb, 1); 1845 cond = bb_predicate (first_edge->src); 1846 if (TREE_CODE (cond) == TRUTH_NOT_EXPR) 1847 std::swap (first_edge, second_edge); 1848 if (EDGE_COUNT (first_edge->src->succs) > 1) 1849 { 1850 cond = bb_predicate (second_edge->src); 1851 if (TREE_CODE (cond) == TRUTH_NOT_EXPR) 1852 cond = TREE_OPERAND (cond, 0); 1853 else 1854 first_edge = second_edge; 1855 } 1856 else 1857 cond = bb_predicate (first_edge->src); 1858 /* Gimplify the condition to a valid cond-expr conditonal operand. */ 1859 cond = force_gimple_operand_gsi_1 (gsi, unshare_expr (cond), 1860 is_gimple_condexpr, NULL_TREE, 1861 true, GSI_SAME_STMT); 1862 true_bb = first_edge->src; 1863 if (EDGE_PRED (bb, 1)->src == true_bb) 1864 { 1865 arg0 = gimple_phi_arg_def (phi, 1); 1866 arg1 = gimple_phi_arg_def (phi, 0); 1867 } 1868 else 1869 { 1870 arg0 = gimple_phi_arg_def (phi, 0); 1871 arg1 = gimple_phi_arg_def (phi, 1); 1872 } 1873 if (is_cond_scalar_reduction (phi, &reduc, arg0, arg1, 1874 &op0, &op1, false)) 1875 /* Convert reduction stmt into vectorizable form. */ 1876 rhs = convert_scalar_cond_reduction (reduc, gsi, cond, op0, op1, 1877 true_bb != gimple_bb (reduc)); 1878 else 1879 /* Build new RHS using selected condition and arguments. */ 1880 rhs = fold_build_cond_expr (TREE_TYPE (res), unshare_expr (cond), 1881 arg0, arg1); 1882 new_stmt = gimple_build_assign (res, rhs); 1883 gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT); 1884 gimple_stmt_iterator new_gsi = gsi_for_stmt (new_stmt); 1885 if (fold_stmt (&new_gsi, ifcvt_follow_ssa_use_edges)) 1886 { 1887 new_stmt = gsi_stmt (new_gsi); 1888 update_stmt (new_stmt); 1889 } 1890 1891 if (dump_file && (dump_flags & TDF_DETAILS)) 1892 { 1893 fprintf (dump_file, "new phi replacement stmt\n"); 1894 print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM); 1895 } 1896 return; 1897 } 1898 1899 /* Create hashmap for PHI node which contain vector of argument indexes 1900 having the same value. */ 1901 bool swap = false; 1902 hash_map<tree_operand_hash, auto_vec<int> > phi_arg_map; 1903 unsigned int num_args = gimple_phi_num_args (phi); 1904 int max_ind = -1; 1905 /* Vector of different PHI argument values. */ 1906 auto_vec<tree> args (num_args); 1907 1908 /* Compute phi_arg_map. */ 1909 for (i = 0; i < num_args; i++) 1910 { 1911 tree arg; 1912 1913 arg = gimple_phi_arg_def (phi, i); 1914 if (!phi_arg_map.get (arg)) 1915 args.quick_push (arg); 1916 phi_arg_map.get_or_insert (arg).safe_push (i); 1917 } 1918 1919 /* Determine element with max number of occurrences. */ 1920 max_ind = -1; 1921 max = 1; 1922 args_len = args.length (); 1923 for (i = 0; i < args_len; i++) 1924 { 1925 unsigned int len; 1926 if ((len = phi_arg_map.get (args[i])->length ()) > max) 1927 { 1928 max_ind = (int) i; 1929 max = len; 1930 } 1931 } 1932 1933 /* Put element with max number of occurences to the end of ARGS. */ 1934 if (max_ind != -1 && max_ind +1 != (int) args_len) 1935 std::swap (args[args_len - 1], args[max_ind]); 1936 1937 /* Handle one special case when number of arguments with different values 1938 is equal 2 and one argument has the only occurrence. Such PHI can be 1939 handled as if would have only 2 arguments. */ 1940 if (args_len == 2 && phi_arg_map.get (args[0])->length () == 1) 1941 { 1942 vec<int> *indexes; 1943 indexes = phi_arg_map.get (args[0]); 1944 index0 = (*indexes)[0]; 1945 arg0 = args[0]; 1946 arg1 = args[1]; 1947 e = gimple_phi_arg_edge (phi, index0); 1948 cond = bb_predicate (e->src); 1949 if (TREE_CODE (cond) == TRUTH_NOT_EXPR) 1950 { 1951 swap = true; 1952 cond = TREE_OPERAND (cond, 0); 1953 } 1954 /* Gimplify the condition to a valid cond-expr conditonal operand. */ 1955 cond = force_gimple_operand_gsi_1 (gsi, unshare_expr (cond), 1956 is_gimple_condexpr, NULL_TREE, 1957 true, GSI_SAME_STMT); 1958 if (!(is_cond_scalar_reduction (phi, &reduc, arg0 , arg1, 1959 &op0, &op1, true))) 1960 rhs = fold_build_cond_expr (TREE_TYPE (res), unshare_expr (cond), 1961 swap? arg1 : arg0, 1962 swap? arg0 : arg1); 1963 else 1964 /* Convert reduction stmt into vectorizable form. */ 1965 rhs = convert_scalar_cond_reduction (reduc, gsi, cond, op0, op1, 1966 swap); 1967 new_stmt = gimple_build_assign (res, rhs); 1968 gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT); 1969 update_stmt (new_stmt); 1970 } 1971 else 1972 { 1973 /* Common case. */ 1974 vec<int> *indexes; 1975 tree type = TREE_TYPE (gimple_phi_result (phi)); 1976 tree lhs; 1977 arg1 = args[1]; 1978 for (i = 0; i < args_len; i++) 1979 { 1980 arg0 = args[i]; 1981 indexes = phi_arg_map.get (args[i]); 1982 if (i != args_len - 1) 1983 lhs = make_temp_ssa_name (type, NULL, "_ifc_"); 1984 else 1985 lhs = res; 1986 cond = gen_phi_arg_condition (phi, indexes, gsi); 1987 rhs = fold_build_cond_expr (type, unshare_expr (cond), 1988 arg0, arg1); 1989 new_stmt = gimple_build_assign (lhs, rhs); 1990 gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT); 1991 update_stmt (new_stmt); 1992 arg1 = lhs; 1993 } 1994 } 1995 1996 if (dump_file && (dump_flags & TDF_DETAILS)) 1997 { 1998 fprintf (dump_file, "new extended phi replacement stmt\n"); 1999 print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM); 2000 } 2001 } 2002 2003 /* Replaces in LOOP all the scalar phi nodes other than those in the 2004 LOOP->header block with conditional modify expressions. */ 2005 2006 static void 2007 predicate_all_scalar_phis (struct loop *loop) 2008 { 2009 basic_block bb; 2010 unsigned int orig_loop_num_nodes = loop->num_nodes; 2011 unsigned int i; 2012 2013 for (i = 1; i < orig_loop_num_nodes; i++) 2014 { 2015 gphi *phi; 2016 gimple_stmt_iterator gsi; 2017 gphi_iterator phi_gsi; 2018 bb = ifc_bbs[i]; 2019 2020 if (bb == loop->header) 2021 continue; 2022 2023 phi_gsi = gsi_start_phis (bb); 2024 if (gsi_end_p (phi_gsi)) 2025 continue; 2026 2027 gsi = gsi_after_labels (bb); 2028 while (!gsi_end_p (phi_gsi)) 2029 { 2030 phi = phi_gsi.phi (); 2031 if (virtual_operand_p (gimple_phi_result (phi))) 2032 gsi_next (&phi_gsi); 2033 else 2034 { 2035 predicate_scalar_phi (phi, &gsi); 2036 remove_phi_node (&phi_gsi, false); 2037 } 2038 } 2039 } 2040 } 2041 2042 /* Insert in each basic block of LOOP the statements produced by the 2043 gimplification of the predicates. */ 2044 2045 static void 2046 insert_gimplified_predicates (loop_p loop) 2047 { 2048 unsigned int i; 2049 2050 for (i = 0; i < loop->num_nodes; i++) 2051 { 2052 basic_block bb = ifc_bbs[i]; 2053 gimple_seq stmts; 2054 if (!is_predicated (bb)) 2055 gcc_assert (bb_predicate_gimplified_stmts (bb) == NULL); 2056 if (!is_predicated (bb)) 2057 { 2058 /* Do not insert statements for a basic block that is not 2059 predicated. Also make sure that the predicate of the 2060 basic block is set to true. */ 2061 reset_bb_predicate (bb); 2062 continue; 2063 } 2064 2065 stmts = bb_predicate_gimplified_stmts (bb); 2066 if (stmts) 2067 { 2068 if (need_to_predicate) 2069 { 2070 /* Insert the predicate of the BB just after the label, 2071 as the if-conversion of memory writes will use this 2072 predicate. */ 2073 gimple_stmt_iterator gsi = gsi_after_labels (bb); 2074 gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT); 2075 } 2076 else 2077 { 2078 /* Insert the predicate of the BB at the end of the BB 2079 as this would reduce the register pressure: the only 2080 use of this predicate will be in successor BBs. */ 2081 gimple_stmt_iterator gsi = gsi_last_bb (bb); 2082 2083 if (gsi_end_p (gsi) 2084 || stmt_ends_bb_p (gsi_stmt (gsi))) 2085 gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT); 2086 else 2087 gsi_insert_seq_after (&gsi, stmts, GSI_SAME_STMT); 2088 } 2089 2090 /* Once the sequence is code generated, set it to NULL. */ 2091 set_bb_predicate_gimplified_stmts (bb, NULL); 2092 } 2093 } 2094 } 2095 2096 /* Helper function for predicate_statements. Returns index of existent 2097 mask if it was created for given SIZE and -1 otherwise. */ 2098 2099 static int 2100 mask_exists (int size, vec<int> vec) 2101 { 2102 unsigned int ix; 2103 int v; 2104 FOR_EACH_VEC_ELT (vec, ix, v) 2105 if (v == size) 2106 return (int) ix; 2107 return -1; 2108 } 2109 2110 /* Helper function for predicate_statements. STMT is a memory read or 2111 write and it needs to be predicated by MASK. Return a statement 2112 that does so. */ 2113 2114 static gimple * 2115 predicate_load_or_store (gimple_stmt_iterator *gsi, gassign *stmt, tree mask) 2116 { 2117 gcall *new_stmt; 2118 2119 tree lhs = gimple_assign_lhs (stmt); 2120 tree rhs = gimple_assign_rhs1 (stmt); 2121 tree ref = TREE_CODE (lhs) == SSA_NAME ? rhs : lhs; 2122 mark_addressable (ref); 2123 tree addr = force_gimple_operand_gsi (gsi, build_fold_addr_expr (ref), 2124 true, NULL_TREE, true, GSI_SAME_STMT); 2125 tree ptr = build_int_cst (reference_alias_ptr_type (ref), 2126 get_object_alignment (ref)); 2127 /* Copy points-to info if possible. */ 2128 if (TREE_CODE (addr) == SSA_NAME && !SSA_NAME_PTR_INFO (addr)) 2129 copy_ref_info (build2 (MEM_REF, TREE_TYPE (ref), addr, ptr), 2130 ref); 2131 if (TREE_CODE (lhs) == SSA_NAME) 2132 { 2133 new_stmt 2134 = gimple_build_call_internal (IFN_MASK_LOAD, 3, addr, 2135 ptr, mask); 2136 gimple_call_set_lhs (new_stmt, lhs); 2137 gimple_set_vuse (new_stmt, gimple_vuse (stmt)); 2138 } 2139 else 2140 { 2141 new_stmt 2142 = gimple_build_call_internal (IFN_MASK_STORE, 4, addr, ptr, 2143 mask, rhs); 2144 gimple_set_vuse (new_stmt, gimple_vuse (stmt)); 2145 gimple_set_vdef (new_stmt, gimple_vdef (stmt)); 2146 SSA_NAME_DEF_STMT (gimple_vdef (new_stmt)) = new_stmt; 2147 } 2148 gimple_call_set_nothrow (new_stmt, true); 2149 return new_stmt; 2150 } 2151 2152 /* STMT uses OP_LHS. Check whether it is equivalent to: 2153 2154 ... = OP_MASK ? OP_LHS : X; 2155 2156 Return X if so, otherwise return null. OP_MASK is an SSA_NAME that is 2157 known to have value OP_COND. */ 2158 2159 static tree 2160 check_redundant_cond_expr (gimple *stmt, tree op_mask, tree op_cond, 2161 tree op_lhs) 2162 { 2163 gassign *assign = dyn_cast <gassign *> (stmt); 2164 if (!assign || gimple_assign_rhs_code (assign) != COND_EXPR) 2165 return NULL_TREE; 2166 2167 tree use_cond = gimple_assign_rhs1 (assign); 2168 tree if_true = gimple_assign_rhs2 (assign); 2169 tree if_false = gimple_assign_rhs3 (assign); 2170 2171 if ((use_cond == op_mask || operand_equal_p (use_cond, op_cond, 0)) 2172 && if_true == op_lhs) 2173 return if_false; 2174 2175 if (inverse_conditions_p (use_cond, op_cond) && if_false == op_lhs) 2176 return if_true; 2177 2178 return NULL_TREE; 2179 } 2180 2181 /* Return true if VALUE is available for use at STMT. SSA_NAMES is 2182 the set of SSA names defined earlier in STMT's block. */ 2183 2184 static bool 2185 value_available_p (gimple *stmt, hash_set<tree_ssa_name_hash> *ssa_names, 2186 tree value) 2187 { 2188 if (is_gimple_min_invariant (value)) 2189 return true; 2190 2191 if (TREE_CODE (value) == SSA_NAME) 2192 { 2193 if (SSA_NAME_IS_DEFAULT_DEF (value)) 2194 return true; 2195 2196 basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (value)); 2197 basic_block use_bb = gimple_bb (stmt); 2198 return (def_bb == use_bb 2199 ? ssa_names->contains (value) 2200 : dominated_by_p (CDI_DOMINATORS, use_bb, def_bb)); 2201 } 2202 2203 return false; 2204 } 2205 2206 /* Helper function for predicate_statements. STMT is a potentially-trapping 2207 arithmetic operation that needs to be predicated by MASK, an SSA_NAME that 2208 has value COND. Return a statement that does so. SSA_NAMES is the set of 2209 SSA names defined earlier in STMT's block. */ 2210 2211 static gimple * 2212 predicate_rhs_code (gassign *stmt, tree mask, tree cond, 2213 hash_set<tree_ssa_name_hash> *ssa_names) 2214 { 2215 tree lhs = gimple_assign_lhs (stmt); 2216 tree_code code = gimple_assign_rhs_code (stmt); 2217 unsigned int nops = gimple_num_ops (stmt); 2218 internal_fn cond_fn = get_conditional_internal_fn (code); 2219 2220 /* Construct the arguments to the conditional internal function. */ 2221 auto_vec<tree, 8> args; 2222 args.safe_grow (nops + 1); 2223 args[0] = mask; 2224 for (unsigned int i = 1; i < nops; ++i) 2225 args[i] = gimple_op (stmt, i); 2226 args[nops] = NULL_TREE; 2227 2228 /* Look for uses of the result to see whether they are COND_EXPRs that can 2229 be folded into the conditional call. */ 2230 imm_use_iterator imm_iter; 2231 gimple *use_stmt; 2232 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, lhs) 2233 { 2234 tree new_else = check_redundant_cond_expr (use_stmt, mask, cond, lhs); 2235 if (new_else && value_available_p (stmt, ssa_names, new_else)) 2236 { 2237 if (!args[nops]) 2238 args[nops] = new_else; 2239 if (operand_equal_p (new_else, args[nops], 0)) 2240 { 2241 /* We have: 2242 2243 LHS = IFN_COND (MASK, ..., ELSE); 2244 X = MASK ? LHS : ELSE; 2245 2246 which makes X equivalent to LHS. */ 2247 tree use_lhs = gimple_assign_lhs (use_stmt); 2248 redundant_ssa_names.safe_push (std::make_pair (use_lhs, lhs)); 2249 } 2250 } 2251 } 2252 if (!args[nops]) 2253 args[nops] = targetm.preferred_else_value (cond_fn, TREE_TYPE (lhs), 2254 nops - 1, &args[1]); 2255 2256 /* Create and insert the call. */ 2257 gcall *new_stmt = gimple_build_call_internal_vec (cond_fn, args); 2258 gimple_call_set_lhs (new_stmt, lhs); 2259 gimple_call_set_nothrow (new_stmt, true); 2260 2261 return new_stmt; 2262 } 2263 2264 /* Predicate each write to memory in LOOP. 2265 2266 This function transforms control flow constructs containing memory 2267 writes of the form: 2268 2269 | for (i = 0; i < N; i++) 2270 | if (cond) 2271 | A[i] = expr; 2272 2273 into the following form that does not contain control flow: 2274 2275 | for (i = 0; i < N; i++) 2276 | A[i] = cond ? expr : A[i]; 2277 2278 The original CFG looks like this: 2279 2280 | bb_0 2281 | i = 0 2282 | end_bb_0 2283 | 2284 | bb_1 2285 | if (i < N) goto bb_5 else goto bb_2 2286 | end_bb_1 2287 | 2288 | bb_2 2289 | cond = some_computation; 2290 | if (cond) goto bb_3 else goto bb_4 2291 | end_bb_2 2292 | 2293 | bb_3 2294 | A[i] = expr; 2295 | goto bb_4 2296 | end_bb_3 2297 | 2298 | bb_4 2299 | goto bb_1 2300 | end_bb_4 2301 2302 insert_gimplified_predicates inserts the computation of the COND 2303 expression at the beginning of the destination basic block: 2304 2305 | bb_0 2306 | i = 0 2307 | end_bb_0 2308 | 2309 | bb_1 2310 | if (i < N) goto bb_5 else goto bb_2 2311 | end_bb_1 2312 | 2313 | bb_2 2314 | cond = some_computation; 2315 | if (cond) goto bb_3 else goto bb_4 2316 | end_bb_2 2317 | 2318 | bb_3 2319 | cond = some_computation; 2320 | A[i] = expr; 2321 | goto bb_4 2322 | end_bb_3 2323 | 2324 | bb_4 2325 | goto bb_1 2326 | end_bb_4 2327 2328 predicate_statements is then predicating the memory write as follows: 2329 2330 | bb_0 2331 | i = 0 2332 | end_bb_0 2333 | 2334 | bb_1 2335 | if (i < N) goto bb_5 else goto bb_2 2336 | end_bb_1 2337 | 2338 | bb_2 2339 | if (cond) goto bb_3 else goto bb_4 2340 | end_bb_2 2341 | 2342 | bb_3 2343 | cond = some_computation; 2344 | A[i] = cond ? expr : A[i]; 2345 | goto bb_4 2346 | end_bb_3 2347 | 2348 | bb_4 2349 | goto bb_1 2350 | end_bb_4 2351 2352 and finally combine_blocks removes the basic block boundaries making 2353 the loop vectorizable: 2354 2355 | bb_0 2356 | i = 0 2357 | if (i < N) goto bb_5 else goto bb_1 2358 | end_bb_0 2359 | 2360 | bb_1 2361 | cond = some_computation; 2362 | A[i] = cond ? expr : A[i]; 2363 | if (i < N) goto bb_5 else goto bb_4 2364 | end_bb_1 2365 | 2366 | bb_4 2367 | goto bb_1 2368 | end_bb_4 2369 */ 2370 2371 static void 2372 predicate_statements (loop_p loop) 2373 { 2374 unsigned int i, orig_loop_num_nodes = loop->num_nodes; 2375 auto_vec<int, 1> vect_sizes; 2376 auto_vec<tree, 1> vect_masks; 2377 hash_set<tree_ssa_name_hash> ssa_names; 2378 2379 for (i = 1; i < orig_loop_num_nodes; i++) 2380 { 2381 gimple_stmt_iterator gsi; 2382 basic_block bb = ifc_bbs[i]; 2383 tree cond = bb_predicate (bb); 2384 bool swap; 2385 int index; 2386 2387 if (is_true_predicate (cond)) 2388 continue; 2389 2390 swap = false; 2391 if (TREE_CODE (cond) == TRUTH_NOT_EXPR) 2392 { 2393 swap = true; 2394 cond = TREE_OPERAND (cond, 0); 2395 } 2396 2397 vect_sizes.truncate (0); 2398 vect_masks.truncate (0); 2399 2400 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);) 2401 { 2402 gassign *stmt = dyn_cast <gassign *> (gsi_stmt (gsi)); 2403 if (!stmt) 2404 ; 2405 else if (is_false_predicate (cond) 2406 && gimple_vdef (stmt)) 2407 { 2408 unlink_stmt_vdef (stmt); 2409 gsi_remove (&gsi, true); 2410 release_defs (stmt); 2411 continue; 2412 } 2413 else if (gimple_plf (stmt, GF_PLF_2)) 2414 { 2415 tree lhs = gimple_assign_lhs (stmt); 2416 tree mask; 2417 gimple *new_stmt; 2418 gimple_seq stmts = NULL; 2419 machine_mode mode = TYPE_MODE (TREE_TYPE (lhs)); 2420 /* We checked before setting GF_PLF_2 that an equivalent 2421 integer mode exists. */ 2422 int bitsize = GET_MODE_BITSIZE (mode).to_constant (); 2423 if (!vect_sizes.is_empty () 2424 && (index = mask_exists (bitsize, vect_sizes)) != -1) 2425 /* Use created mask. */ 2426 mask = vect_masks[index]; 2427 else 2428 { 2429 if (COMPARISON_CLASS_P (cond)) 2430 mask = gimple_build (&stmts, TREE_CODE (cond), 2431 boolean_type_node, 2432 TREE_OPERAND (cond, 0), 2433 TREE_OPERAND (cond, 1)); 2434 else 2435 mask = cond; 2436 2437 if (swap) 2438 { 2439 tree true_val 2440 = constant_boolean_node (true, TREE_TYPE (mask)); 2441 mask = gimple_build (&stmts, BIT_XOR_EXPR, 2442 TREE_TYPE (mask), mask, true_val); 2443 } 2444 gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT); 2445 2446 /* Save mask and its size for further use. */ 2447 vect_sizes.safe_push (bitsize); 2448 vect_masks.safe_push (mask); 2449 } 2450 if (gimple_assign_single_p (stmt)) 2451 new_stmt = predicate_load_or_store (&gsi, stmt, mask); 2452 else 2453 new_stmt = predicate_rhs_code (stmt, mask, cond, &ssa_names); 2454 2455 gsi_replace (&gsi, new_stmt, true); 2456 } 2457 else if (gimple_vdef (stmt)) 2458 { 2459 tree lhs = gimple_assign_lhs (stmt); 2460 tree rhs = gimple_assign_rhs1 (stmt); 2461 tree type = TREE_TYPE (lhs); 2462 2463 lhs = ifc_temp_var (type, unshare_expr (lhs), &gsi); 2464 rhs = ifc_temp_var (type, unshare_expr (rhs), &gsi); 2465 if (swap) 2466 std::swap (lhs, rhs); 2467 cond = force_gimple_operand_gsi_1 (&gsi, unshare_expr (cond), 2468 is_gimple_condexpr, NULL_TREE, 2469 true, GSI_SAME_STMT); 2470 rhs = fold_build_cond_expr (type, unshare_expr (cond), rhs, lhs); 2471 gimple_assign_set_rhs1 (stmt, ifc_temp_var (type, rhs, &gsi)); 2472 update_stmt (stmt); 2473 } 2474 tree lhs = gimple_get_lhs (gsi_stmt (gsi)); 2475 if (lhs && TREE_CODE (lhs) == SSA_NAME) 2476 ssa_names.add (lhs); 2477 gsi_next (&gsi); 2478 } 2479 ssa_names.empty (); 2480 } 2481 } 2482 2483 /* Remove all GIMPLE_CONDs and GIMPLE_LABELs of all the basic blocks 2484 other than the exit and latch of the LOOP. Also resets the 2485 GIMPLE_DEBUG information. */ 2486 2487 static void 2488 remove_conditions_and_labels (loop_p loop) 2489 { 2490 gimple_stmt_iterator gsi; 2491 unsigned int i; 2492 2493 for (i = 0; i < loop->num_nodes; i++) 2494 { 2495 basic_block bb = ifc_bbs[i]; 2496 2497 if (bb_with_exit_edge_p (loop, bb) 2498 || bb == loop->latch) 2499 continue; 2500 2501 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); ) 2502 switch (gimple_code (gsi_stmt (gsi))) 2503 { 2504 case GIMPLE_COND: 2505 case GIMPLE_LABEL: 2506 gsi_remove (&gsi, true); 2507 break; 2508 2509 case GIMPLE_DEBUG: 2510 /* ??? Should there be conditional GIMPLE_DEBUG_BINDs? */ 2511 if (gimple_debug_bind_p (gsi_stmt (gsi))) 2512 { 2513 gimple_debug_bind_reset_value (gsi_stmt (gsi)); 2514 update_stmt (gsi_stmt (gsi)); 2515 } 2516 gsi_next (&gsi); 2517 break; 2518 2519 default: 2520 gsi_next (&gsi); 2521 } 2522 } 2523 } 2524 2525 /* Combine all the basic blocks from LOOP into one or two super basic 2526 blocks. Replace PHI nodes with conditional modify expressions. */ 2527 2528 static void 2529 combine_blocks (struct loop *loop) 2530 { 2531 basic_block bb, exit_bb, merge_target_bb; 2532 unsigned int orig_loop_num_nodes = loop->num_nodes; 2533 unsigned int i; 2534 edge e; 2535 edge_iterator ei; 2536 2537 remove_conditions_and_labels (loop); 2538 insert_gimplified_predicates (loop); 2539 predicate_all_scalar_phis (loop); 2540 2541 if (need_to_predicate) 2542 predicate_statements (loop); 2543 2544 /* Merge basic blocks: first remove all the edges in the loop, 2545 except for those from the exit block. */ 2546 exit_bb = NULL; 2547 bool *predicated = XNEWVEC (bool, orig_loop_num_nodes); 2548 for (i = 0; i < orig_loop_num_nodes; i++) 2549 { 2550 bb = ifc_bbs[i]; 2551 predicated[i] = !is_true_predicate (bb_predicate (bb)); 2552 free_bb_predicate (bb); 2553 if (bb_with_exit_edge_p (loop, bb)) 2554 { 2555 gcc_assert (exit_bb == NULL); 2556 exit_bb = bb; 2557 } 2558 } 2559 gcc_assert (exit_bb != loop->latch); 2560 2561 for (i = 1; i < orig_loop_num_nodes; i++) 2562 { 2563 bb = ifc_bbs[i]; 2564 2565 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei));) 2566 { 2567 if (e->src == exit_bb) 2568 ei_next (&ei); 2569 else 2570 remove_edge (e); 2571 } 2572 } 2573 2574 if (exit_bb != NULL) 2575 { 2576 if (exit_bb != loop->header) 2577 { 2578 /* Connect this node to loop header. */ 2579 make_single_succ_edge (loop->header, exit_bb, EDGE_FALLTHRU); 2580 set_immediate_dominator (CDI_DOMINATORS, exit_bb, loop->header); 2581 } 2582 2583 /* Redirect non-exit edges to loop->latch. */ 2584 FOR_EACH_EDGE (e, ei, exit_bb->succs) 2585 { 2586 if (!loop_exit_edge_p (loop, e)) 2587 redirect_edge_and_branch (e, loop->latch); 2588 } 2589 set_immediate_dominator (CDI_DOMINATORS, loop->latch, exit_bb); 2590 } 2591 else 2592 { 2593 /* If the loop does not have an exit, reconnect header and latch. */ 2594 make_edge (loop->header, loop->latch, EDGE_FALLTHRU); 2595 set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header); 2596 } 2597 2598 merge_target_bb = loop->header; 2599 2600 /* Get at the virtual def valid for uses starting at the first block 2601 we merge into the header. Without a virtual PHI the loop has the 2602 same virtual use on all stmts. */ 2603 gphi *vphi = get_virtual_phi (loop->header); 2604 tree last_vdef = NULL_TREE; 2605 if (vphi) 2606 { 2607 last_vdef = gimple_phi_result (vphi); 2608 for (gimple_stmt_iterator gsi = gsi_start_bb (loop->header); 2609 ! gsi_end_p (gsi); gsi_next (&gsi)) 2610 if (gimple_vdef (gsi_stmt (gsi))) 2611 last_vdef = gimple_vdef (gsi_stmt (gsi)); 2612 } 2613 for (i = 1; i < orig_loop_num_nodes; i++) 2614 { 2615 gimple_stmt_iterator gsi; 2616 gimple_stmt_iterator last; 2617 2618 bb = ifc_bbs[i]; 2619 2620 if (bb == exit_bb || bb == loop->latch) 2621 continue; 2622 2623 /* We release virtual PHIs late because we have to propagate them 2624 out using the current VUSE. The def might be the one used 2625 after the loop. */ 2626 vphi = get_virtual_phi (bb); 2627 if (vphi) 2628 { 2629 /* When there's just loads inside the loop a stray virtual 2630 PHI merging the uses can appear, update last_vdef from 2631 it. */ 2632 if (!last_vdef) 2633 last_vdef = gimple_phi_arg_def (vphi, 0); 2634 imm_use_iterator iter; 2635 use_operand_p use_p; 2636 gimple *use_stmt; 2637 FOR_EACH_IMM_USE_STMT (use_stmt, iter, gimple_phi_result (vphi)) 2638 { 2639 FOR_EACH_IMM_USE_ON_STMT (use_p, iter) 2640 SET_USE (use_p, last_vdef); 2641 } 2642 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (vphi))) 2643 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (last_vdef) = 1; 2644 gsi = gsi_for_stmt (vphi); 2645 remove_phi_node (&gsi, true); 2646 } 2647 2648 /* Make stmts member of loop->header and clear range info from all stmts 2649 in BB which is now no longer executed conditional on a predicate we 2650 could have derived it from. */ 2651 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 2652 { 2653 gimple *stmt = gsi_stmt (gsi); 2654 gimple_set_bb (stmt, merge_target_bb); 2655 /* Update virtual operands. */ 2656 if (last_vdef) 2657 { 2658 use_operand_p use_p = ssa_vuse_operand (stmt); 2659 if (use_p 2660 && USE_FROM_PTR (use_p) != last_vdef) 2661 SET_USE (use_p, last_vdef); 2662 if (gimple_vdef (stmt)) 2663 last_vdef = gimple_vdef (stmt); 2664 } 2665 else 2666 /* If this is the first load we arrive at update last_vdef 2667 so we handle stray PHIs correctly. */ 2668 last_vdef = gimple_vuse (stmt); 2669 if (predicated[i]) 2670 { 2671 ssa_op_iter i; 2672 tree op; 2673 FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_DEF) 2674 reset_flow_sensitive_info (op); 2675 } 2676 } 2677 2678 /* Update stmt list. */ 2679 last = gsi_last_bb (merge_target_bb); 2680 gsi_insert_seq_after_without_update (&last, bb_seq (bb), GSI_NEW_STMT); 2681 set_bb_seq (bb, NULL); 2682 2683 delete_basic_block (bb); 2684 } 2685 2686 /* If possible, merge loop header to the block with the exit edge. 2687 This reduces the number of basic blocks to two, to please the 2688 vectorizer that handles only loops with two nodes. */ 2689 if (exit_bb 2690 && exit_bb != loop->header) 2691 { 2692 /* We release virtual PHIs late because we have to propagate them 2693 out using the current VUSE. The def might be the one used 2694 after the loop. */ 2695 vphi = get_virtual_phi (exit_bb); 2696 if (vphi) 2697 { 2698 imm_use_iterator iter; 2699 use_operand_p use_p; 2700 gimple *use_stmt; 2701 FOR_EACH_IMM_USE_STMT (use_stmt, iter, gimple_phi_result (vphi)) 2702 { 2703 FOR_EACH_IMM_USE_ON_STMT (use_p, iter) 2704 SET_USE (use_p, last_vdef); 2705 } 2706 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (vphi))) 2707 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (last_vdef) = 1; 2708 gimple_stmt_iterator gsi = gsi_for_stmt (vphi); 2709 remove_phi_node (&gsi, true); 2710 } 2711 2712 if (can_merge_blocks_p (loop->header, exit_bb)) 2713 merge_blocks (loop->header, exit_bb); 2714 } 2715 2716 free (ifc_bbs); 2717 ifc_bbs = NULL; 2718 free (predicated); 2719 } 2720 2721 /* Version LOOP before if-converting it; the original loop 2722 will be if-converted, the new copy of the loop will not, 2723 and the LOOP_VECTORIZED internal call will be guarding which 2724 loop to execute. The vectorizer pass will fold this 2725 internal call into either true or false. 2726 2727 Note that this function intentionally invalidates profile. Both edges 2728 out of LOOP_VECTORIZED must have 100% probability so the profile remains 2729 consistent after the condition is folded in the vectorizer. */ 2730 2731 static struct loop * 2732 version_loop_for_if_conversion (struct loop *loop, vec<gimple *> *preds) 2733 { 2734 basic_block cond_bb; 2735 tree cond = make_ssa_name (boolean_type_node); 2736 struct loop *new_loop; 2737 gimple *g; 2738 gimple_stmt_iterator gsi; 2739 unsigned int save_length; 2740 2741 g = gimple_build_call_internal (IFN_LOOP_VECTORIZED, 2, 2742 build_int_cst (integer_type_node, loop->num), 2743 integer_zero_node); 2744 gimple_call_set_lhs (g, cond); 2745 2746 /* Save BB->aux around loop_version as that uses the same field. */ 2747 save_length = loop->inner ? loop->inner->num_nodes : loop->num_nodes; 2748 void **saved_preds = XALLOCAVEC (void *, save_length); 2749 for (unsigned i = 0; i < save_length; i++) 2750 saved_preds[i] = ifc_bbs[i]->aux; 2751 2752 initialize_original_copy_tables (); 2753 /* At this point we invalidate porfile confistency until IFN_LOOP_VECTORIZED 2754 is re-merged in the vectorizer. */ 2755 new_loop = loop_version (loop, cond, &cond_bb, 2756 profile_probability::always (), 2757 profile_probability::always (), 2758 profile_probability::always (), 2759 profile_probability::always (), true); 2760 free_original_copy_tables (); 2761 2762 for (unsigned i = 0; i < save_length; i++) 2763 ifc_bbs[i]->aux = saved_preds[i]; 2764 2765 if (new_loop == NULL) 2766 return NULL; 2767 2768 new_loop->dont_vectorize = true; 2769 new_loop->force_vectorize = false; 2770 gsi = gsi_last_bb (cond_bb); 2771 gimple_call_set_arg (g, 1, build_int_cst (integer_type_node, new_loop->num)); 2772 if (preds) 2773 preds->safe_push (g); 2774 gsi_insert_before (&gsi, g, GSI_SAME_STMT); 2775 update_ssa (TODO_update_ssa); 2776 return new_loop; 2777 } 2778 2779 /* Return true when LOOP satisfies the follow conditions that will 2780 allow it to be recognized by the vectorizer for outer-loop 2781 vectorization: 2782 - The loop is not the root node of the loop tree. 2783 - The loop has exactly one inner loop. 2784 - The loop has a single exit. 2785 - The loop header has a single successor, which is the inner 2786 loop header. 2787 - Each of the inner and outer loop latches have a single 2788 predecessor. 2789 - The loop exit block has a single predecessor, which is the 2790 inner loop's exit block. */ 2791 2792 static bool 2793 versionable_outer_loop_p (struct loop *loop) 2794 { 2795 if (!loop_outer (loop) 2796 || loop->dont_vectorize 2797 || !loop->inner 2798 || loop->inner->next 2799 || !single_exit (loop) 2800 || !single_succ_p (loop->header) 2801 || single_succ (loop->header) != loop->inner->header 2802 || !single_pred_p (loop->latch) 2803 || !single_pred_p (loop->inner->latch)) 2804 return false; 2805 2806 basic_block outer_exit = single_pred (loop->latch); 2807 basic_block inner_exit = single_pred (loop->inner->latch); 2808 2809 if (!single_pred_p (outer_exit) || single_pred (outer_exit) != inner_exit) 2810 return false; 2811 2812 if (dump_file) 2813 fprintf (dump_file, "Found vectorizable outer loop for versioning\n"); 2814 2815 return true; 2816 } 2817 2818 /* Performs splitting of critical edges. Skip splitting and return false 2819 if LOOP will not be converted because: 2820 2821 - LOOP is not well formed. 2822 - LOOP has PHI with more than MAX_PHI_ARG_NUM arguments. 2823 2824 Last restriction is valid only if AGGRESSIVE_IF_CONV is false. */ 2825 2826 static bool 2827 ifcvt_split_critical_edges (struct loop *loop, bool aggressive_if_conv) 2828 { 2829 basic_block *body; 2830 basic_block bb; 2831 unsigned int num = loop->num_nodes; 2832 unsigned int i; 2833 gimple *stmt; 2834 edge e; 2835 edge_iterator ei; 2836 auto_vec<edge> critical_edges; 2837 2838 /* Loop is not well formed. */ 2839 if (num <= 2 || loop->inner || !single_exit (loop)) 2840 return false; 2841 2842 body = get_loop_body (loop); 2843 for (i = 0; i < num; i++) 2844 { 2845 bb = body[i]; 2846 if (!aggressive_if_conv 2847 && phi_nodes (bb) 2848 && EDGE_COUNT (bb->preds) > MAX_PHI_ARG_NUM) 2849 { 2850 if (dump_file && (dump_flags & TDF_DETAILS)) 2851 fprintf (dump_file, 2852 "BB %d has complicated PHI with more than %u args.\n", 2853 bb->index, MAX_PHI_ARG_NUM); 2854 2855 free (body); 2856 return false; 2857 } 2858 if (bb == loop->latch || bb_with_exit_edge_p (loop, bb)) 2859 continue; 2860 2861 stmt = last_stmt (bb); 2862 /* Skip basic blocks not ending with conditional branch. */ 2863 if (!stmt || gimple_code (stmt) != GIMPLE_COND) 2864 continue; 2865 2866 FOR_EACH_EDGE (e, ei, bb->succs) 2867 if (EDGE_CRITICAL_P (e) && e->dest->loop_father == loop) 2868 critical_edges.safe_push (e); 2869 } 2870 free (body); 2871 2872 while (critical_edges.length () > 0) 2873 { 2874 e = critical_edges.pop (); 2875 /* Don't split if bb can be predicated along non-critical edge. */ 2876 if (EDGE_COUNT (e->dest->preds) > 2 || all_preds_critical_p (e->dest)) 2877 split_edge (e); 2878 } 2879 2880 return true; 2881 } 2882 2883 /* Delete redundant statements produced by predication which prevents 2884 loop vectorization. */ 2885 2886 static void 2887 ifcvt_local_dce (basic_block bb) 2888 { 2889 gimple *stmt; 2890 gimple *stmt1; 2891 gimple *phi; 2892 gimple_stmt_iterator gsi; 2893 auto_vec<gimple *> worklist; 2894 enum gimple_code code; 2895 use_operand_p use_p; 2896 imm_use_iterator imm_iter; 2897 std::pair <tree, tree> *name_pair; 2898 unsigned int i; 2899 2900 FOR_EACH_VEC_ELT (redundant_ssa_names, i, name_pair) 2901 replace_uses_by (name_pair->first, name_pair->second); 2902 redundant_ssa_names.release (); 2903 2904 worklist.create (64); 2905 /* Consider all phi as live statements. */ 2906 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 2907 { 2908 phi = gsi_stmt (gsi); 2909 gimple_set_plf (phi, GF_PLF_2, true); 2910 worklist.safe_push (phi); 2911 } 2912 /* Consider load/store statements, CALL and COND as live. */ 2913 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 2914 { 2915 stmt = gsi_stmt (gsi); 2916 if (gimple_store_p (stmt) 2917 || gimple_assign_load_p (stmt) 2918 || is_gimple_debug (stmt)) 2919 { 2920 gimple_set_plf (stmt, GF_PLF_2, true); 2921 worklist.safe_push (stmt); 2922 continue; 2923 } 2924 code = gimple_code (stmt); 2925 if (code == GIMPLE_COND || code == GIMPLE_CALL) 2926 { 2927 gimple_set_plf (stmt, GF_PLF_2, true); 2928 worklist.safe_push (stmt); 2929 continue; 2930 } 2931 gimple_set_plf (stmt, GF_PLF_2, false); 2932 2933 if (code == GIMPLE_ASSIGN) 2934 { 2935 tree lhs = gimple_assign_lhs (stmt); 2936 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, lhs) 2937 { 2938 stmt1 = USE_STMT (use_p); 2939 if (gimple_bb (stmt1) != bb) 2940 { 2941 gimple_set_plf (stmt, GF_PLF_2, true); 2942 worklist.safe_push (stmt); 2943 break; 2944 } 2945 } 2946 } 2947 } 2948 /* Propagate liveness through arguments of live stmt. */ 2949 while (worklist.length () > 0) 2950 { 2951 ssa_op_iter iter; 2952 use_operand_p use_p; 2953 tree use; 2954 2955 stmt = worklist.pop (); 2956 FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE) 2957 { 2958 use = USE_FROM_PTR (use_p); 2959 if (TREE_CODE (use) != SSA_NAME) 2960 continue; 2961 stmt1 = SSA_NAME_DEF_STMT (use); 2962 if (gimple_bb (stmt1) != bb 2963 || gimple_plf (stmt1, GF_PLF_2)) 2964 continue; 2965 gimple_set_plf (stmt1, GF_PLF_2, true); 2966 worklist.safe_push (stmt1); 2967 } 2968 } 2969 /* Delete dead statements. */ 2970 gsi = gsi_start_bb (bb); 2971 while (!gsi_end_p (gsi)) 2972 { 2973 stmt = gsi_stmt (gsi); 2974 if (gimple_plf (stmt, GF_PLF_2)) 2975 { 2976 gsi_next (&gsi); 2977 continue; 2978 } 2979 if (dump_file && (dump_flags & TDF_DETAILS)) 2980 { 2981 fprintf (dump_file, "Delete dead stmt in bb#%d\n", bb->index); 2982 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 2983 } 2984 gsi_remove (&gsi, true); 2985 release_defs (stmt); 2986 } 2987 } 2988 2989 /* If-convert LOOP when it is legal. For the moment this pass has no 2990 profitability analysis. Returns non-zero todo flags when something 2991 changed. */ 2992 2993 unsigned int 2994 tree_if_conversion (struct loop *loop, vec<gimple *> *preds) 2995 { 2996 unsigned int todo = 0; 2997 bool aggressive_if_conv; 2998 struct loop *rloop; 2999 bitmap exit_bbs; 3000 3001 again: 3002 rloop = NULL; 3003 ifc_bbs = NULL; 3004 need_to_predicate = false; 3005 any_complicated_phi = false; 3006 3007 /* Apply more aggressive if-conversion when loop or its outer loop were 3008 marked with simd pragma. When that's the case, we try to if-convert 3009 loop containing PHIs with more than MAX_PHI_ARG_NUM arguments. */ 3010 aggressive_if_conv = loop->force_vectorize; 3011 if (!aggressive_if_conv) 3012 { 3013 struct loop *outer_loop = loop_outer (loop); 3014 if (outer_loop && outer_loop->force_vectorize) 3015 aggressive_if_conv = true; 3016 } 3017 3018 if (!ifcvt_split_critical_edges (loop, aggressive_if_conv)) 3019 goto cleanup; 3020 3021 if (!if_convertible_loop_p (loop) 3022 || !dbg_cnt (if_conversion_tree)) 3023 goto cleanup; 3024 3025 if ((need_to_predicate || any_complicated_phi) 3026 && ((!flag_tree_loop_vectorize && !loop->force_vectorize) 3027 || loop->dont_vectorize)) 3028 goto cleanup; 3029 3030 /* Since we have no cost model, always version loops unless the user 3031 specified -ftree-loop-if-convert or unless versioning is required. 3032 Either version this loop, or if the pattern is right for outer-loop 3033 vectorization, version the outer loop. In the latter case we will 3034 still if-convert the original inner loop. */ 3035 if (need_to_predicate 3036 || any_complicated_phi 3037 || flag_tree_loop_if_convert != 1) 3038 { 3039 struct loop *vloop 3040 = (versionable_outer_loop_p (loop_outer (loop)) 3041 ? loop_outer (loop) : loop); 3042 struct loop *nloop = version_loop_for_if_conversion (vloop, preds); 3043 if (nloop == NULL) 3044 goto cleanup; 3045 if (vloop != loop) 3046 { 3047 /* If versionable_outer_loop_p decided to version the 3048 outer loop, version also the inner loop of the non-vectorized 3049 loop copy. So we transform: 3050 loop1 3051 loop2 3052 into: 3053 if (LOOP_VECTORIZED (1, 3)) 3054 { 3055 loop1 3056 loop2 3057 } 3058 else 3059 loop3 (copy of loop1) 3060 if (LOOP_VECTORIZED (4, 5)) 3061 loop4 (copy of loop2) 3062 else 3063 loop5 (copy of loop4) */ 3064 gcc_assert (nloop->inner && nloop->inner->next == NULL); 3065 rloop = nloop->inner; 3066 } 3067 } 3068 3069 /* Now all statements are if-convertible. Combine all the basic 3070 blocks into one huge basic block doing the if-conversion 3071 on-the-fly. */ 3072 combine_blocks (loop); 3073 3074 /* Delete dead predicate computations. */ 3075 ifcvt_local_dce (loop->header); 3076 3077 /* Perform local CSE, this esp. helps the vectorizer analysis if loads 3078 and stores are involved. CSE only the loop body, not the entry 3079 PHIs, those are to be kept in sync with the non-if-converted copy. 3080 ??? We'll still keep dead stores though. */ 3081 exit_bbs = BITMAP_ALLOC (NULL); 3082 bitmap_set_bit (exit_bbs, single_exit (loop)->dest->index); 3083 bitmap_set_bit (exit_bbs, loop->latch->index); 3084 todo |= do_rpo_vn (cfun, loop_preheader_edge (loop), exit_bbs); 3085 BITMAP_FREE (exit_bbs); 3086 3087 todo |= TODO_cleanup_cfg; 3088 3089 cleanup: 3090 if (ifc_bbs) 3091 { 3092 unsigned int i; 3093 3094 for (i = 0; i < loop->num_nodes; i++) 3095 free_bb_predicate (ifc_bbs[i]); 3096 3097 free (ifc_bbs); 3098 ifc_bbs = NULL; 3099 } 3100 if (rloop != NULL) 3101 { 3102 loop = rloop; 3103 goto again; 3104 } 3105 3106 return todo; 3107 } 3108 3109 /* Tree if-conversion pass management. */ 3110 3111 namespace { 3112 3113 const pass_data pass_data_if_conversion = 3114 { 3115 GIMPLE_PASS, /* type */ 3116 "ifcvt", /* name */ 3117 OPTGROUP_NONE, /* optinfo_flags */ 3118 TV_TREE_LOOP_IFCVT, /* tv_id */ 3119 ( PROP_cfg | PROP_ssa ), /* properties_required */ 3120 0, /* properties_provided */ 3121 0, /* properties_destroyed */ 3122 0, /* todo_flags_start */ 3123 0, /* todo_flags_finish */ 3124 }; 3125 3126 class pass_if_conversion : public gimple_opt_pass 3127 { 3128 public: 3129 pass_if_conversion (gcc::context *ctxt) 3130 : gimple_opt_pass (pass_data_if_conversion, ctxt) 3131 {} 3132 3133 /* opt_pass methods: */ 3134 virtual bool gate (function *); 3135 virtual unsigned int execute (function *); 3136 3137 }; // class pass_if_conversion 3138 3139 bool 3140 pass_if_conversion::gate (function *fun) 3141 { 3142 return (((flag_tree_loop_vectorize || fun->has_force_vectorize_loops) 3143 && flag_tree_loop_if_convert != 0) 3144 || flag_tree_loop_if_convert == 1); 3145 } 3146 3147 unsigned int 3148 pass_if_conversion::execute (function *fun) 3149 { 3150 struct loop *loop; 3151 unsigned todo = 0; 3152 3153 if (number_of_loops (fun) <= 1) 3154 return 0; 3155 3156 auto_vec<gimple *> preds; 3157 FOR_EACH_LOOP (loop, 0) 3158 if (flag_tree_loop_if_convert == 1 3159 || ((flag_tree_loop_vectorize || loop->force_vectorize) 3160 && !loop->dont_vectorize)) 3161 todo |= tree_if_conversion (loop, &preds); 3162 3163 if (todo) 3164 { 3165 free_numbers_of_iterations_estimates (fun); 3166 scev_reset (); 3167 } 3168 3169 if (flag_checking) 3170 { 3171 basic_block bb; 3172 FOR_EACH_BB_FN (bb, fun) 3173 gcc_assert (!bb->aux); 3174 } 3175 3176 /* Perform IL update now, it might elide some loops. */ 3177 if (todo & TODO_cleanup_cfg) 3178 { 3179 cleanup_tree_cfg (); 3180 if (need_ssa_update_p (fun)) 3181 todo |= TODO_update_ssa; 3182 } 3183 if (todo & TODO_update_ssa_any) 3184 update_ssa (todo & TODO_update_ssa_any); 3185 3186 /* If if-conversion elided the loop fall back to the original one. */ 3187 for (unsigned i = 0; i < preds.length (); ++i) 3188 { 3189 gimple *g = preds[i]; 3190 if (!gimple_bb (g)) 3191 continue; 3192 unsigned ifcvt_loop = tree_to_uhwi (gimple_call_arg (g, 0)); 3193 if (!get_loop (fun, ifcvt_loop)) 3194 { 3195 if (dump_file) 3196 fprintf (dump_file, "If-converted loop vanished\n"); 3197 fold_loop_internal_call (g, boolean_false_node); 3198 } 3199 } 3200 3201 return 0; 3202 } 3203 3204 } // anon namespace 3205 3206 gimple_opt_pass * 3207 make_pass_if_conversion (gcc::context *ctxt) 3208 { 3209 return new pass_if_conversion (ctxt); 3210 } 3211