1/* If-conversion for vectorizer. 2 Copyright (C) 2004-2015 Free Software Foundation, Inc. 3 Contributed by Devang Patel <dpatel@apple.com> 4 5This file is part of GCC. 6 7GCC is free software; you can redistribute it and/or modify it under 8the terms of the GNU General Public License as published by the Free 9Software Foundation; either version 3, or (at your option) any later 10version. 11 12GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13WARRANTY; without even the implied warranty of MERCHANTABILITY or 14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15for more details. 16 17You should have received a copy of the GNU General Public License 18along with GCC; see the file 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 "tm.h" 87#include "hash-set.h" 88#include "machmode.h" 89#include "vec.h" 90#include "double-int.h" 91#include "input.h" 92#include "alias.h" 93#include "symtab.h" 94#include "wide-int.h" 95#include "inchash.h" 96#include "tree.h" 97#include "fold-const.h" 98#include "stor-layout.h" 99#include "flags.h" 100#include "predict.h" 101#include "hard-reg-set.h" 102#include "function.h" 103#include "dominance.h" 104#include "cfg.h" 105#include "basic-block.h" 106#include "gimple-pretty-print.h" 107#include "tree-ssa-alias.h" 108#include "internal-fn.h" 109#include "gimple-fold.h" 110#include "gimple-expr.h" 111#include "is-a.h" 112#include "gimple.h" 113#include "gimplify.h" 114#include "gimple-iterator.h" 115#include "gimplify-me.h" 116#include "gimple-ssa.h" 117#include "tree-cfg.h" 118#include "tree-phinodes.h" 119#include "ssa-iterators.h" 120#include "stringpool.h" 121#include "tree-ssanames.h" 122#include "tree-into-ssa.h" 123#include "tree-ssa.h" 124#include "cfgloop.h" 125#include "tree-chrec.h" 126#include "tree-data-ref.h" 127#include "tree-scalar-evolution.h" 128#include "tree-ssa-loop-ivopts.h" 129#include "tree-ssa-address.h" 130#include "tree-pass.h" 131#include "dbgcnt.h" 132#include "hashtab.h" 133#include "rtl.h" 134#include "statistics.h" 135#include "real.h" 136#include "fixed-value.h" 137#include "insn-config.h" 138#include "expmed.h" 139#include "dojump.h" 140#include "explow.h" 141#include "calls.h" 142#include "emit-rtl.h" 143#include "varasm.h" 144#include "stmt.h" 145#include "expr.h" 146#include "insn-codes.h" 147#include "optabs.h" 148#include "hash-map.h" 149 150/* List of basic blocks in if-conversion-suitable order. */ 151static basic_block *ifc_bbs; 152 153/* Apply more aggressive (extended) if-conversion if true. */ 154static bool aggressive_if_conv; 155 156/* Structure used to predicate basic blocks. This is attached to the 157 ->aux field of the BBs in the loop to be if-converted. */ 158typedef struct bb_predicate_s { 159 160 /* The condition under which this basic block is executed. */ 161 tree predicate; 162 163 /* PREDICATE is gimplified, and the sequence of statements is 164 recorded here, in order to avoid the duplication of computations 165 that occur in previous conditions. See PR44483. */ 166 gimple_seq predicate_gimplified_stmts; 167} *bb_predicate_p; 168 169/* Returns true when the basic block BB has a predicate. */ 170 171static inline bool 172bb_has_predicate (basic_block bb) 173{ 174 return bb->aux != NULL; 175} 176 177/* Returns the gimplified predicate for basic block BB. */ 178 179static inline tree 180bb_predicate (basic_block bb) 181{ 182 return ((bb_predicate_p) bb->aux)->predicate; 183} 184 185/* Sets the gimplified predicate COND for basic block BB. */ 186 187static inline void 188set_bb_predicate (basic_block bb, tree cond) 189{ 190 gcc_assert ((TREE_CODE (cond) == TRUTH_NOT_EXPR 191 && is_gimple_condexpr (TREE_OPERAND (cond, 0))) 192 || is_gimple_condexpr (cond)); 193 ((bb_predicate_p) bb->aux)->predicate = cond; 194} 195 196/* Returns the sequence of statements of the gimplification of the 197 predicate for basic block BB. */ 198 199static inline gimple_seq 200bb_predicate_gimplified_stmts (basic_block bb) 201{ 202 return ((bb_predicate_p) bb->aux)->predicate_gimplified_stmts; 203} 204 205/* Sets the sequence of statements STMTS of the gimplification of the 206 predicate for basic block BB. */ 207 208static inline void 209set_bb_predicate_gimplified_stmts (basic_block bb, gimple_seq stmts) 210{ 211 ((bb_predicate_p) bb->aux)->predicate_gimplified_stmts = stmts; 212} 213 214/* Adds the sequence of statements STMTS to the sequence of statements 215 of the predicate for basic block BB. */ 216 217static inline void 218add_bb_predicate_gimplified_stmts (basic_block bb, gimple_seq stmts) 219{ 220 gimple_seq_add_seq 221 (&(((bb_predicate_p) bb->aux)->predicate_gimplified_stmts), stmts); 222} 223 224/* Initializes to TRUE the predicate of basic block BB. */ 225 226static inline void 227init_bb_predicate (basic_block bb) 228{ 229 bb->aux = XNEW (struct bb_predicate_s); 230 set_bb_predicate_gimplified_stmts (bb, NULL); 231 set_bb_predicate (bb, boolean_true_node); 232} 233 234/* Release the SSA_NAMEs associated with the predicate of basic block BB, 235 but don't actually free it. */ 236 237static inline void 238release_bb_predicate (basic_block bb) 239{ 240 gimple_seq stmts = bb_predicate_gimplified_stmts (bb); 241 if (stmts) 242 { 243 gimple_stmt_iterator i; 244 245 for (i = gsi_start (stmts); !gsi_end_p (i); gsi_next (&i)) 246 free_stmt_operands (cfun, gsi_stmt (i)); 247 set_bb_predicate_gimplified_stmts (bb, NULL); 248 } 249} 250 251/* Free the predicate of basic block BB. */ 252 253static inline void 254free_bb_predicate (basic_block bb) 255{ 256 if (!bb_has_predicate (bb)) 257 return; 258 259 release_bb_predicate (bb); 260 free (bb->aux); 261 bb->aux = NULL; 262} 263 264/* Reinitialize predicate of BB with the true predicate. */ 265 266static inline void 267reset_bb_predicate (basic_block bb) 268{ 269 if (!bb_has_predicate (bb)) 270 init_bb_predicate (bb); 271 else 272 { 273 release_bb_predicate (bb); 274 set_bb_predicate (bb, boolean_true_node); 275 } 276} 277 278/* Returns a new SSA_NAME of type TYPE that is assigned the value of 279 the expression EXPR. Inserts the statement created for this 280 computation before GSI and leaves the iterator GSI at the same 281 statement. */ 282 283static tree 284ifc_temp_var (tree type, tree expr, gimple_stmt_iterator *gsi) 285{ 286 tree new_name = make_temp_ssa_name (type, NULL, "_ifc_"); 287 gimple stmt = gimple_build_assign (new_name, expr); 288 gsi_insert_before (gsi, stmt, GSI_SAME_STMT); 289 return new_name; 290} 291 292/* Return true when COND is a true predicate. */ 293 294static inline bool 295is_true_predicate (tree cond) 296{ 297 return (cond == NULL_TREE 298 || cond == boolean_true_node 299 || integer_onep (cond)); 300} 301 302/* Returns true when BB has a predicate that is not trivial: true or 303 NULL_TREE. */ 304 305static inline bool 306is_predicated (basic_block bb) 307{ 308 return !is_true_predicate (bb_predicate (bb)); 309} 310 311/* Parses the predicate COND and returns its comparison code and 312 operands OP0 and OP1. */ 313 314static enum tree_code 315parse_predicate (tree cond, tree *op0, tree *op1) 316{ 317 gimple s; 318 319 if (TREE_CODE (cond) == SSA_NAME 320 && is_gimple_assign (s = SSA_NAME_DEF_STMT (cond))) 321 { 322 if (TREE_CODE_CLASS (gimple_assign_rhs_code (s)) == tcc_comparison) 323 { 324 *op0 = gimple_assign_rhs1 (s); 325 *op1 = gimple_assign_rhs2 (s); 326 return gimple_assign_rhs_code (s); 327 } 328 329 else if (gimple_assign_rhs_code (s) == TRUTH_NOT_EXPR) 330 { 331 tree op = gimple_assign_rhs1 (s); 332 tree type = TREE_TYPE (op); 333 enum tree_code code = parse_predicate (op, op0, op1); 334 335 return code == ERROR_MARK ? ERROR_MARK 336 : invert_tree_comparison (code, HONOR_NANS (type)); 337 } 338 339 return ERROR_MARK; 340 } 341 342 if (TREE_CODE_CLASS (TREE_CODE (cond)) == tcc_comparison) 343 { 344 *op0 = TREE_OPERAND (cond, 0); 345 *op1 = TREE_OPERAND (cond, 1); 346 return TREE_CODE (cond); 347 } 348 349 return ERROR_MARK; 350} 351 352/* Returns the fold of predicate C1 OR C2 at location LOC. */ 353 354static tree 355fold_or_predicates (location_t loc, tree c1, tree c2) 356{ 357 tree op1a, op1b, op2a, op2b; 358 enum tree_code code1 = parse_predicate (c1, &op1a, &op1b); 359 enum tree_code code2 = parse_predicate (c2, &op2a, &op2b); 360 361 if (code1 != ERROR_MARK && code2 != ERROR_MARK) 362 { 363 tree t = maybe_fold_or_comparisons (code1, op1a, op1b, 364 code2, op2a, op2b); 365 if (t) 366 return t; 367 } 368 369 return fold_build2_loc (loc, TRUTH_OR_EXPR, boolean_type_node, c1, c2); 370} 371 372/* Returns true if N is either a constant or a SSA_NAME. */ 373 374static bool 375constant_or_ssa_name (tree n) 376{ 377 switch (TREE_CODE (n)) 378 { 379 case SSA_NAME: 380 case INTEGER_CST: 381 case REAL_CST: 382 case COMPLEX_CST: 383 case VECTOR_CST: 384 return true; 385 default: 386 return false; 387 } 388} 389 390/* Returns either a COND_EXPR or the folded expression if the folded 391 expression is a MIN_EXPR, a MAX_EXPR, an ABS_EXPR, 392 a constant or a SSA_NAME. */ 393 394static tree 395fold_build_cond_expr (tree type, tree cond, tree rhs, tree lhs) 396{ 397 tree rhs1, lhs1, cond_expr; 398 399 /* If COND is comparison r != 0 and r has boolean type, convert COND 400 to SSA_NAME to accept by vect bool pattern. */ 401 if (TREE_CODE (cond) == NE_EXPR) 402 { 403 tree op0 = TREE_OPERAND (cond, 0); 404 tree op1 = TREE_OPERAND (cond, 1); 405 if (TREE_CODE (op0) == SSA_NAME 406 && TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE 407 && (integer_zerop (op1))) 408 cond = op0; 409 } 410 cond_expr = fold_ternary (COND_EXPR, type, cond, 411 rhs, lhs); 412 413 if (cond_expr == NULL_TREE) 414 return build3 (COND_EXPR, type, cond, rhs, lhs); 415 416 STRIP_USELESS_TYPE_CONVERSION (cond_expr); 417 418 if (constant_or_ssa_name (cond_expr)) 419 return cond_expr; 420 421 if (TREE_CODE (cond_expr) == ABS_EXPR) 422 { 423 rhs1 = TREE_OPERAND (cond_expr, 1); 424 STRIP_USELESS_TYPE_CONVERSION (rhs1); 425 if (constant_or_ssa_name (rhs1)) 426 return build1 (ABS_EXPR, type, rhs1); 427 } 428 429 if (TREE_CODE (cond_expr) == MIN_EXPR 430 || TREE_CODE (cond_expr) == MAX_EXPR) 431 { 432 lhs1 = TREE_OPERAND (cond_expr, 0); 433 STRIP_USELESS_TYPE_CONVERSION (lhs1); 434 rhs1 = TREE_OPERAND (cond_expr, 1); 435 STRIP_USELESS_TYPE_CONVERSION (rhs1); 436 if (constant_or_ssa_name (rhs1) 437 && constant_or_ssa_name (lhs1)) 438 return build2 (TREE_CODE (cond_expr), type, lhs1, rhs1); 439 } 440 return build3 (COND_EXPR, type, cond, rhs, lhs); 441} 442 443/* Add condition NC to the predicate list of basic block BB. LOOP is 444 the loop to be if-converted. Use predicate of cd-equivalent block 445 for join bb if it exists: we call basic blocks bb1 and bb2 446 cd-equivalent if they are executed under the same condition. */ 447 448static inline void 449add_to_predicate_list (struct loop *loop, basic_block bb, tree nc) 450{ 451 tree bc, *tp; 452 basic_block dom_bb; 453 454 if (is_true_predicate (nc)) 455 return; 456 457 /* If dominance tells us this basic block is always executed, 458 don't record any predicates for it. */ 459 if (dominated_by_p (CDI_DOMINATORS, loop->latch, bb)) 460 return; 461 462 dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb); 463 /* We use notion of cd equivalence to get simpler predicate for 464 join block, e.g. if join block has 2 predecessors with predicates 465 p1 & p2 and p1 & !p2, we'd like to get p1 for it instead of 466 p1 & p2 | p1 & !p2. */ 467 if (dom_bb != loop->header 468 && get_immediate_dominator (CDI_POST_DOMINATORS, dom_bb) == bb) 469 { 470 gcc_assert (flow_bb_inside_loop_p (loop, dom_bb)); 471 bc = bb_predicate (dom_bb); 472 if (!is_true_predicate (bc)) 473 set_bb_predicate (bb, bc); 474 else 475 gcc_assert (is_true_predicate (bb_predicate (bb))); 476 if (dump_file && (dump_flags & TDF_DETAILS)) 477 fprintf (dump_file, "Use predicate of bb#%d for bb#%d\n", 478 dom_bb->index, bb->index); 479 return; 480 } 481 482 if (!is_predicated (bb)) 483 bc = nc; 484 else 485 { 486 bc = bb_predicate (bb); 487 bc = fold_or_predicates (EXPR_LOCATION (bc), nc, bc); 488 if (is_true_predicate (bc)) 489 { 490 reset_bb_predicate (bb); 491 return; 492 } 493 } 494 495 /* Allow a TRUTH_NOT_EXPR around the main predicate. */ 496 if (TREE_CODE (bc) == TRUTH_NOT_EXPR) 497 tp = &TREE_OPERAND (bc, 0); 498 else 499 tp = &bc; 500 if (!is_gimple_condexpr (*tp)) 501 { 502 gimple_seq stmts; 503 *tp = force_gimple_operand_1 (*tp, &stmts, is_gimple_condexpr, NULL_TREE); 504 add_bb_predicate_gimplified_stmts (bb, stmts); 505 } 506 set_bb_predicate (bb, bc); 507} 508 509/* Add the condition COND to the previous condition PREV_COND, and add 510 this to the predicate list of the destination of edge E. LOOP is 511 the loop to be if-converted. */ 512 513static void 514add_to_dst_predicate_list (struct loop *loop, edge e, 515 tree prev_cond, tree cond) 516{ 517 if (!flow_bb_inside_loop_p (loop, e->dest)) 518 return; 519 520 if (!is_true_predicate (prev_cond)) 521 cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, 522 prev_cond, cond); 523 524 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, e->dest)) 525 add_to_predicate_list (loop, e->dest, cond); 526} 527 528/* Return true if one of the successor edges of BB exits LOOP. */ 529 530static bool 531bb_with_exit_edge_p (struct loop *loop, basic_block bb) 532{ 533 edge e; 534 edge_iterator ei; 535 536 FOR_EACH_EDGE (e, ei, bb->succs) 537 if (loop_exit_edge_p (loop, e)) 538 return true; 539 540 return false; 541} 542 543/* Return true when PHI is if-convertible. PHI is part of loop LOOP 544 and it belongs to basic block BB. 545 546 PHI is not if-convertible if: 547 - it has more than 2 arguments. 548 549 When the flag_tree_loop_if_convert_stores is not set, PHI is not 550 if-convertible if: 551 - a virtual PHI is immediately used in another PHI node, 552 - there is a virtual PHI in a BB other than the loop->header. 553 When the aggressive_if_conv is set, PHI can have more than 554 two arguments. */ 555 556static bool 557if_convertible_phi_p (struct loop *loop, basic_block bb, gphi *phi, 558 bool any_mask_load_store) 559{ 560 if (dump_file && (dump_flags & TDF_DETAILS)) 561 { 562 fprintf (dump_file, "-------------------------\n"); 563 print_gimple_stmt (dump_file, phi, 0, TDF_SLIM); 564 } 565 566 if (bb != loop->header) 567 { 568 if (gimple_phi_num_args (phi) != 2 569 && !aggressive_if_conv) 570 { 571 if (dump_file && (dump_flags & TDF_DETAILS)) 572 fprintf (dump_file, "More than two phi node args.\n"); 573 return false; 574 } 575 } 576 577 if (flag_tree_loop_if_convert_stores || any_mask_load_store) 578 return true; 579 580 /* When the flag_tree_loop_if_convert_stores is not set, check 581 that there are no memory writes in the branches of the loop to be 582 if-converted. */ 583 if (virtual_operand_p (gimple_phi_result (phi))) 584 { 585 imm_use_iterator imm_iter; 586 use_operand_p use_p; 587 588 if (bb != loop->header) 589 { 590 if (dump_file && (dump_flags & TDF_DETAILS)) 591 fprintf (dump_file, "Virtual phi not on loop->header.\n"); 592 return false; 593 } 594 595 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, gimple_phi_result (phi)) 596 { 597 if (gimple_code (USE_STMT (use_p)) == GIMPLE_PHI) 598 { 599 if (dump_file && (dump_flags & TDF_DETAILS)) 600 fprintf (dump_file, "Difficult to handle this virtual phi.\n"); 601 return false; 602 } 603 } 604 } 605 606 return true; 607} 608 609/* Records the status of a data reference. This struct is attached to 610 each DR->aux field. */ 611 612struct ifc_dr { 613 /* -1 when not initialized, 0 when false, 1 when true. */ 614 int written_at_least_once; 615 616 /* -1 when not initialized, 0 when false, 1 when true. */ 617 int rw_unconditionally; 618}; 619 620#define IFC_DR(DR) ((struct ifc_dr *) (DR)->aux) 621#define DR_WRITTEN_AT_LEAST_ONCE(DR) (IFC_DR (DR)->written_at_least_once) 622#define DR_RW_UNCONDITIONALLY(DR) (IFC_DR (DR)->rw_unconditionally) 623 624/* Returns true when the memory references of STMT are read or written 625 unconditionally. In other words, this function returns true when 626 for every data reference A in STMT there exist other accesses to 627 a data reference with the same base with predicates that add up (OR-up) to 628 the true predicate: this ensures that the data reference A is touched 629 (read or written) on every iteration of the if-converted loop. */ 630 631static bool 632memrefs_read_or_written_unconditionally (gimple stmt, 633 vec<data_reference_p> drs) 634{ 635 int i, j; 636 data_reference_p a, b; 637 tree ca = bb_predicate (gimple_bb (stmt)); 638 639 for (i = 0; drs.iterate (i, &a); i++) 640 if (DR_STMT (a) == stmt) 641 { 642 bool found = false; 643 int x = DR_RW_UNCONDITIONALLY (a); 644 645 if (x == 0) 646 return false; 647 648 if (x == 1) 649 continue; 650 651 for (j = 0; drs.iterate (j, &b); j++) 652 { 653 tree ref_base_a = DR_REF (a); 654 tree ref_base_b = DR_REF (b); 655 656 if (DR_STMT (b) == stmt) 657 continue; 658 659 while (TREE_CODE (ref_base_a) == COMPONENT_REF 660 || TREE_CODE (ref_base_a) == IMAGPART_EXPR 661 || TREE_CODE (ref_base_a) == REALPART_EXPR) 662 ref_base_a = TREE_OPERAND (ref_base_a, 0); 663 664 while (TREE_CODE (ref_base_b) == COMPONENT_REF 665 || TREE_CODE (ref_base_b) == IMAGPART_EXPR 666 || TREE_CODE (ref_base_b) == REALPART_EXPR) 667 ref_base_b = TREE_OPERAND (ref_base_b, 0); 668 669 if (operand_equal_p (ref_base_a, ref_base_b, 0)) 670 { 671 tree cb = bb_predicate (gimple_bb (DR_STMT (b))); 672 673 if (DR_RW_UNCONDITIONALLY (b) == 1 674 || is_true_predicate (cb) 675 || is_true_predicate (ca 676 = fold_or_predicates (EXPR_LOCATION (cb), ca, cb))) 677 { 678 DR_RW_UNCONDITIONALLY (a) = 1; 679 DR_RW_UNCONDITIONALLY (b) = 1; 680 found = true; 681 break; 682 } 683 } 684 } 685 686 if (!found) 687 { 688 DR_RW_UNCONDITIONALLY (a) = 0; 689 return false; 690 } 691 } 692 693 return true; 694} 695 696/* Returns true when the memory references of STMT are unconditionally 697 written. In other words, this function returns true when for every 698 data reference A written in STMT, there exist other writes to the 699 same data reference with predicates that add up (OR-up) to the true 700 predicate: this ensures that the data reference A is written on 701 every iteration of the if-converted loop. */ 702 703static bool 704write_memrefs_written_at_least_once (gimple stmt, 705 vec<data_reference_p> drs) 706{ 707 int i, j; 708 data_reference_p a, b; 709 tree ca = bb_predicate (gimple_bb (stmt)); 710 711 for (i = 0; drs.iterate (i, &a); i++) 712 if (DR_STMT (a) == stmt 713 && DR_IS_WRITE (a)) 714 { 715 bool found = false; 716 int x = DR_WRITTEN_AT_LEAST_ONCE (a); 717 718 if (x == 0) 719 return false; 720 721 if (x == 1) 722 continue; 723 724 for (j = 0; drs.iterate (j, &b); j++) 725 if (DR_STMT (b) != stmt 726 && DR_IS_WRITE (b) 727 && same_data_refs_base_objects (a, b)) 728 { 729 tree cb = bb_predicate (gimple_bb (DR_STMT (b))); 730 731 if (DR_WRITTEN_AT_LEAST_ONCE (b) == 1 732 || is_true_predicate (cb) 733 || is_true_predicate (ca = fold_or_predicates (EXPR_LOCATION (cb), 734 ca, cb))) 735 { 736 DR_WRITTEN_AT_LEAST_ONCE (a) = 1; 737 DR_WRITTEN_AT_LEAST_ONCE (b) = 1; 738 found = true; 739 break; 740 } 741 } 742 743 if (!found) 744 { 745 DR_WRITTEN_AT_LEAST_ONCE (a) = 0; 746 return false; 747 } 748 } 749 750 return true; 751} 752 753/* Return true when the memory references of STMT won't trap in the 754 if-converted code. There are two things that we have to check for: 755 756 - writes to memory occur to writable memory: if-conversion of 757 memory writes transforms the conditional memory writes into 758 unconditional writes, i.e. "if (cond) A[i] = foo" is transformed 759 into "A[i] = cond ? foo : A[i]", and as the write to memory may not 760 be executed at all in the original code, it may be a readonly 761 memory. To check that A is not const-qualified, we check that 762 there exists at least an unconditional write to A in the current 763 function. 764 765 - reads or writes to memory are valid memory accesses for every 766 iteration. To check that the memory accesses are correctly formed 767 and that we are allowed to read and write in these locations, we 768 check that the memory accesses to be if-converted occur at every 769 iteration unconditionally. */ 770 771static bool 772ifcvt_memrefs_wont_trap (gimple stmt, vec<data_reference_p> refs) 773{ 774 return write_memrefs_written_at_least_once (stmt, refs) 775 && memrefs_read_or_written_unconditionally (stmt, refs); 776} 777 778/* Wrapper around gimple_could_trap_p refined for the needs of the 779 if-conversion. Try to prove that the memory accesses of STMT could 780 not trap in the innermost loop containing STMT. */ 781 782static bool 783ifcvt_could_trap_p (gimple stmt, vec<data_reference_p> refs) 784{ 785 if (gimple_vuse (stmt) 786 && !gimple_could_trap_p_1 (stmt, false, false) 787 && ifcvt_memrefs_wont_trap (stmt, refs)) 788 return false; 789 790 return gimple_could_trap_p (stmt); 791} 792 793/* Return true if STMT could be converted into a masked load or store 794 (conditional load or store based on a mask computed from bb predicate). */ 795 796static bool 797ifcvt_can_use_mask_load_store (gimple stmt) 798{ 799 tree lhs, ref; 800 machine_mode mode; 801 basic_block bb = gimple_bb (stmt); 802 bool is_load; 803 804 if (!(flag_tree_loop_vectorize || bb->loop_father->force_vectorize) 805 || bb->loop_father->dont_vectorize 806 || !gimple_assign_single_p (stmt) 807 || gimple_has_volatile_ops (stmt)) 808 return false; 809 810 /* Check whether this is a load or store. */ 811 lhs = gimple_assign_lhs (stmt); 812 if (gimple_store_p (stmt)) 813 { 814 if (!is_gimple_val (gimple_assign_rhs1 (stmt))) 815 return false; 816 is_load = false; 817 ref = lhs; 818 } 819 else if (gimple_assign_load_p (stmt)) 820 { 821 is_load = true; 822 ref = gimple_assign_rhs1 (stmt); 823 } 824 else 825 return false; 826 827 if (may_be_nonaddressable_p (ref)) 828 return false; 829 830 /* Mask should be integer mode of the same size as the load/store 831 mode. */ 832 mode = TYPE_MODE (TREE_TYPE (lhs)); 833 if (int_mode_for_mode (mode) == BLKmode 834 || VECTOR_MODE_P (mode)) 835 return false; 836 837 if (can_vec_mask_load_store_p (mode, is_load)) 838 return true; 839 840 return false; 841} 842 843/* Return true when STMT is if-convertible. 844 845 GIMPLE_ASSIGN statement is not if-convertible if, 846 - it is not movable, 847 - it could trap, 848 - LHS is not var decl. */ 849 850static bool 851if_convertible_gimple_assign_stmt_p (gimple stmt, 852 vec<data_reference_p> refs, 853 bool *any_mask_load_store) 854{ 855 tree lhs = gimple_assign_lhs (stmt); 856 basic_block bb; 857 858 if (dump_file && (dump_flags & TDF_DETAILS)) 859 { 860 fprintf (dump_file, "-------------------------\n"); 861 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 862 } 863 864 if (!is_gimple_reg_type (TREE_TYPE (lhs))) 865 return false; 866 867 /* Some of these constrains might be too conservative. */ 868 if (stmt_ends_bb_p (stmt) 869 || gimple_has_volatile_ops (stmt) 870 || (TREE_CODE (lhs) == SSA_NAME 871 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs)) 872 || gimple_has_side_effects (stmt)) 873 { 874 if (dump_file && (dump_flags & TDF_DETAILS)) 875 fprintf (dump_file, "stmt not suitable for ifcvt\n"); 876 return false; 877 } 878 879 /* tree-into-ssa.c uses GF_PLF_1, so avoid it, because 880 in between if_convertible_loop_p and combine_blocks 881 we can perform loop versioning. */ 882 gimple_set_plf (stmt, GF_PLF_2, false); 883 884 if (flag_tree_loop_if_convert_stores) 885 { 886 if (ifcvt_could_trap_p (stmt, refs)) 887 { 888 if (ifcvt_can_use_mask_load_store (stmt)) 889 { 890 gimple_set_plf (stmt, GF_PLF_2, true); 891 *any_mask_load_store = true; 892 return true; 893 } 894 if (dump_file && (dump_flags & TDF_DETAILS)) 895 fprintf (dump_file, "tree could trap...\n"); 896 return false; 897 } 898 return true; 899 } 900 901 if (gimple_assign_rhs_could_trap_p (stmt)) 902 { 903 if (ifcvt_can_use_mask_load_store (stmt)) 904 { 905 gimple_set_plf (stmt, GF_PLF_2, true); 906 *any_mask_load_store = true; 907 return true; 908 } 909 if (dump_file && (dump_flags & TDF_DETAILS)) 910 fprintf (dump_file, "tree could trap...\n"); 911 return false; 912 } 913 914 bb = gimple_bb (stmt); 915 916 if (TREE_CODE (lhs) != SSA_NAME 917 && bb != bb->loop_father->header 918 && !bb_with_exit_edge_p (bb->loop_father, bb)) 919 { 920 if (ifcvt_can_use_mask_load_store (stmt)) 921 { 922 gimple_set_plf (stmt, GF_PLF_2, true); 923 *any_mask_load_store = true; 924 return true; 925 } 926 if (dump_file && (dump_flags & TDF_DETAILS)) 927 { 928 fprintf (dump_file, "LHS is not var\n"); 929 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 930 } 931 return false; 932 } 933 934 return true; 935} 936 937/* Return true when STMT is if-convertible. 938 939 A statement is if-convertible if: 940 - it is an if-convertible GIMPLE_ASSIGN, 941 - it is a GIMPLE_LABEL or a GIMPLE_COND, 942 - it is builtins call. */ 943 944static bool 945if_convertible_stmt_p (gimple stmt, vec<data_reference_p> refs, 946 bool *any_mask_load_store) 947{ 948 switch (gimple_code (stmt)) 949 { 950 case GIMPLE_LABEL: 951 case GIMPLE_DEBUG: 952 case GIMPLE_COND: 953 return true; 954 955 case GIMPLE_ASSIGN: 956 return if_convertible_gimple_assign_stmt_p (stmt, refs, 957 any_mask_load_store); 958 959 case GIMPLE_CALL: 960 { 961 tree fndecl = gimple_call_fndecl (stmt); 962 if (fndecl) 963 { 964 int flags = gimple_call_flags (stmt); 965 if ((flags & ECF_CONST) 966 && !(flags & ECF_LOOPING_CONST_OR_PURE) 967 /* We can only vectorize some builtins at the moment, 968 so restrict if-conversion to those. */ 969 && DECL_BUILT_IN (fndecl)) 970 return true; 971 } 972 return false; 973 } 974 975 default: 976 /* Don't know what to do with 'em so don't do anything. */ 977 if (dump_file && (dump_flags & TDF_DETAILS)) 978 { 979 fprintf (dump_file, "don't know what to do\n"); 980 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 981 } 982 return false; 983 break; 984 } 985 986 return true; 987} 988 989/* Assumes that BB has more than 1 predecessors. 990 Returns false if at least one successor is not on critical edge 991 and true otherwise. */ 992 993static inline bool 994all_preds_critical_p (basic_block bb) 995{ 996 edge e; 997 edge_iterator ei; 998 999 FOR_EACH_EDGE (e, ei, bb->preds) 1000 if (EDGE_COUNT (e->src->succs) == 1) 1001 return false; 1002 return true; 1003} 1004 1005/* Returns true if at least one successor in on critical edge. */ 1006static inline bool 1007has_pred_critical_p (basic_block bb) 1008{ 1009 edge e; 1010 edge_iterator ei; 1011 1012 FOR_EACH_EDGE (e, ei, bb->preds) 1013 if (EDGE_COUNT (e->src->succs) > 1) 1014 return true; 1015 return false; 1016} 1017 1018/* Return true when BB is if-convertible. This routine does not check 1019 basic block's statements and phis. 1020 1021 A basic block is not if-convertible if: 1022 - it is non-empty and it is after the exit block (in BFS order), 1023 - it is after the exit block but before the latch, 1024 - its edges are not normal. 1025 1026 Last restriction is valid if aggressive_if_conv is false. 1027 1028 EXIT_BB is the basic block containing the exit of the LOOP. BB is 1029 inside LOOP. */ 1030 1031static bool 1032if_convertible_bb_p (struct loop *loop, basic_block bb, basic_block exit_bb) 1033{ 1034 edge e; 1035 edge_iterator ei; 1036 1037 if (dump_file && (dump_flags & TDF_DETAILS)) 1038 fprintf (dump_file, "----------[%d]-------------\n", bb->index); 1039 1040 if (EDGE_COUNT (bb->succs) > 2) 1041 return false; 1042 1043 if (EDGE_COUNT (bb->preds) > 2 1044 && !aggressive_if_conv) 1045 return false; 1046 1047 if (exit_bb) 1048 { 1049 if (bb != loop->latch) 1050 { 1051 if (dump_file && (dump_flags & TDF_DETAILS)) 1052 fprintf (dump_file, "basic block after exit bb but before latch\n"); 1053 return false; 1054 } 1055 else if (!empty_block_p (bb)) 1056 { 1057 if (dump_file && (dump_flags & TDF_DETAILS)) 1058 fprintf (dump_file, "non empty basic block after exit bb\n"); 1059 return false; 1060 } 1061 else if (bb == loop->latch 1062 && bb != exit_bb 1063 && !dominated_by_p (CDI_DOMINATORS, bb, exit_bb)) 1064 { 1065 if (dump_file && (dump_flags & TDF_DETAILS)) 1066 fprintf (dump_file, "latch is not dominated by exit_block\n"); 1067 return false; 1068 } 1069 } 1070 1071 /* Be less adventurous and handle only normal edges. */ 1072 FOR_EACH_EDGE (e, ei, bb->succs) 1073 if (e->flags & (EDGE_EH | EDGE_ABNORMAL | EDGE_IRREDUCIBLE_LOOP)) 1074 { 1075 if (dump_file && (dump_flags & TDF_DETAILS)) 1076 fprintf (dump_file, "Difficult to handle edges\n"); 1077 return false; 1078 } 1079 1080 /* At least one incoming edge has to be non-critical as otherwise edge 1081 predicates are not equal to basic-block predicates of the edge 1082 source. This check is skipped if aggressive_if_conv is true. */ 1083 if (!aggressive_if_conv 1084 && EDGE_COUNT (bb->preds) > 1 1085 && bb != loop->header 1086 && all_preds_critical_p (bb)) 1087 { 1088 if (dump_file && (dump_flags & TDF_DETAILS)) 1089 fprintf (dump_file, "only critical predecessors\n"); 1090 return false; 1091 } 1092 1093 return true; 1094} 1095 1096/* Return true when all predecessor blocks of BB are visited. The 1097 VISITED bitmap keeps track of the visited blocks. */ 1098 1099static bool 1100pred_blocks_visited_p (basic_block bb, bitmap *visited) 1101{ 1102 edge e; 1103 edge_iterator ei; 1104 FOR_EACH_EDGE (e, ei, bb->preds) 1105 if (!bitmap_bit_p (*visited, e->src->index)) 1106 return false; 1107 1108 return true; 1109} 1110 1111/* Get body of a LOOP in suitable order for if-conversion. It is 1112 caller's responsibility to deallocate basic block list. 1113 If-conversion suitable order is, breadth first sort (BFS) order 1114 with an additional constraint: select a block only if all its 1115 predecessors are already selected. */ 1116 1117static basic_block * 1118get_loop_body_in_if_conv_order (const struct loop *loop) 1119{ 1120 basic_block *blocks, *blocks_in_bfs_order; 1121 basic_block bb; 1122 bitmap visited; 1123 unsigned int index = 0; 1124 unsigned int visited_count = 0; 1125 1126 gcc_assert (loop->num_nodes); 1127 gcc_assert (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun)); 1128 1129 blocks = XCNEWVEC (basic_block, loop->num_nodes); 1130 visited = BITMAP_ALLOC (NULL); 1131 1132 blocks_in_bfs_order = get_loop_body_in_bfs_order (loop); 1133 1134 index = 0; 1135 while (index < loop->num_nodes) 1136 { 1137 bb = blocks_in_bfs_order [index]; 1138 1139 if (bb->flags & BB_IRREDUCIBLE_LOOP) 1140 { 1141 free (blocks_in_bfs_order); 1142 BITMAP_FREE (visited); 1143 free (blocks); 1144 return NULL; 1145 } 1146 1147 if (!bitmap_bit_p (visited, bb->index)) 1148 { 1149 if (pred_blocks_visited_p (bb, &visited) 1150 || bb == loop->header) 1151 { 1152 /* This block is now visited. */ 1153 bitmap_set_bit (visited, bb->index); 1154 blocks[visited_count++] = bb; 1155 } 1156 } 1157 1158 index++; 1159 1160 if (index == loop->num_nodes 1161 && visited_count != loop->num_nodes) 1162 /* Not done yet. */ 1163 index = 0; 1164 } 1165 free (blocks_in_bfs_order); 1166 BITMAP_FREE (visited); 1167 return blocks; 1168} 1169 1170/* Returns true when the analysis of the predicates for all the basic 1171 blocks in LOOP succeeded. 1172 1173 predicate_bbs first allocates the predicates of the basic blocks. 1174 These fields are then initialized with the tree expressions 1175 representing the predicates under which a basic block is executed 1176 in the LOOP. As the loop->header is executed at each iteration, it 1177 has the "true" predicate. Other statements executed under a 1178 condition are predicated with that condition, for example 1179 1180 | if (x) 1181 | S1; 1182 | else 1183 | S2; 1184 1185 S1 will be predicated with "x", and 1186 S2 will be predicated with "!x". */ 1187 1188static void 1189predicate_bbs (loop_p loop) 1190{ 1191 unsigned int i; 1192 1193 for (i = 0; i < loop->num_nodes; i++) 1194 init_bb_predicate (ifc_bbs[i]); 1195 1196 for (i = 0; i < loop->num_nodes; i++) 1197 { 1198 basic_block bb = ifc_bbs[i]; 1199 tree cond; 1200 gimple stmt; 1201 1202 /* The loop latch and loop exit block are always executed and 1203 have no extra conditions to be processed: skip them. */ 1204 if (bb == loop->latch 1205 || bb_with_exit_edge_p (loop, bb)) 1206 { 1207 reset_bb_predicate (bb); 1208 continue; 1209 } 1210 1211 cond = bb_predicate (bb); 1212 stmt = last_stmt (bb); 1213 if (stmt && gimple_code (stmt) == GIMPLE_COND) 1214 { 1215 tree c2; 1216 edge true_edge, false_edge; 1217 location_t loc = gimple_location (stmt); 1218 tree c = build2_loc (loc, gimple_cond_code (stmt), 1219 boolean_type_node, 1220 gimple_cond_lhs (stmt), 1221 gimple_cond_rhs (stmt)); 1222 1223 /* Add new condition into destination's predicate list. */ 1224 extract_true_false_edges_from_block (gimple_bb (stmt), 1225 &true_edge, &false_edge); 1226 1227 /* If C is true, then TRUE_EDGE is taken. */ 1228 add_to_dst_predicate_list (loop, true_edge, unshare_expr (cond), 1229 unshare_expr (c)); 1230 1231 /* If C is false, then FALSE_EDGE is taken. */ 1232 c2 = build1_loc (loc, TRUTH_NOT_EXPR, boolean_type_node, 1233 unshare_expr (c)); 1234 add_to_dst_predicate_list (loop, false_edge, 1235 unshare_expr (cond), c2); 1236 1237 cond = NULL_TREE; 1238 } 1239 1240 /* If current bb has only one successor, then consider it as an 1241 unconditional goto. */ 1242 if (single_succ_p (bb)) 1243 { 1244 basic_block bb_n = single_succ (bb); 1245 1246 /* The successor bb inherits the predicate of its 1247 predecessor. If there is no predicate in the predecessor 1248 bb, then consider the successor bb as always executed. */ 1249 if (cond == NULL_TREE) 1250 cond = boolean_true_node; 1251 1252 add_to_predicate_list (loop, bb_n, cond); 1253 } 1254 } 1255 1256 /* The loop header is always executed. */ 1257 reset_bb_predicate (loop->header); 1258 gcc_assert (bb_predicate_gimplified_stmts (loop->header) == NULL 1259 && bb_predicate_gimplified_stmts (loop->latch) == NULL); 1260} 1261 1262/* Return true when LOOP is if-convertible. This is a helper function 1263 for if_convertible_loop_p. REFS and DDRS are initialized and freed 1264 in if_convertible_loop_p. */ 1265 1266static bool 1267if_convertible_loop_p_1 (struct loop *loop, 1268 vec<loop_p> *loop_nest, 1269 vec<data_reference_p> *refs, 1270 vec<ddr_p> *ddrs, bool *any_mask_load_store) 1271{ 1272 bool res; 1273 unsigned int i; 1274 basic_block exit_bb = NULL; 1275 1276 /* Don't if-convert the loop when the data dependences cannot be 1277 computed: the loop won't be vectorized in that case. */ 1278 res = compute_data_dependences_for_loop (loop, true, loop_nest, refs, ddrs); 1279 if (!res) 1280 return false; 1281 1282 calculate_dominance_info (CDI_DOMINATORS); 1283 calculate_dominance_info (CDI_POST_DOMINATORS); 1284 1285 /* Allow statements that can be handled during if-conversion. */ 1286 ifc_bbs = get_loop_body_in_if_conv_order (loop); 1287 if (!ifc_bbs) 1288 { 1289 if (dump_file && (dump_flags & TDF_DETAILS)) 1290 fprintf (dump_file, "Irreducible loop\n"); 1291 return false; 1292 } 1293 1294 for (i = 0; i < loop->num_nodes; i++) 1295 { 1296 basic_block bb = ifc_bbs[i]; 1297 1298 if (!if_convertible_bb_p (loop, bb, exit_bb)) 1299 return false; 1300 1301 if (bb_with_exit_edge_p (loop, bb)) 1302 exit_bb = bb; 1303 } 1304 1305 for (i = 0; i < loop->num_nodes; i++) 1306 { 1307 basic_block bb = ifc_bbs[i]; 1308 gimple_stmt_iterator gsi; 1309 1310 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 1311 switch (gimple_code (gsi_stmt (gsi))) 1312 { 1313 case GIMPLE_LABEL: 1314 case GIMPLE_ASSIGN: 1315 case GIMPLE_CALL: 1316 case GIMPLE_DEBUG: 1317 case GIMPLE_COND: 1318 break; 1319 default: 1320 return false; 1321 } 1322 } 1323 1324 if (flag_tree_loop_if_convert_stores) 1325 { 1326 data_reference_p dr; 1327 1328 for (i = 0; refs->iterate (i, &dr); i++) 1329 { 1330 dr->aux = XNEW (struct ifc_dr); 1331 DR_WRITTEN_AT_LEAST_ONCE (dr) = -1; 1332 DR_RW_UNCONDITIONALLY (dr) = -1; 1333 } 1334 predicate_bbs (loop); 1335 } 1336 1337 for (i = 0; i < loop->num_nodes; i++) 1338 { 1339 basic_block bb = ifc_bbs[i]; 1340 gimple_stmt_iterator itr; 1341 1342 /* Check the if-convertibility of statements in predicated BBs. */ 1343 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb)) 1344 for (itr = gsi_start_bb (bb); !gsi_end_p (itr); gsi_next (&itr)) 1345 if (!if_convertible_stmt_p (gsi_stmt (itr), *refs, 1346 any_mask_load_store)) 1347 return false; 1348 } 1349 1350 if (flag_tree_loop_if_convert_stores) 1351 for (i = 0; i < loop->num_nodes; i++) 1352 free_bb_predicate (ifc_bbs[i]); 1353 1354 /* Checking PHIs needs to be done after stmts, as the fact whether there 1355 are any masked loads or stores affects the tests. */ 1356 for (i = 0; i < loop->num_nodes; i++) 1357 { 1358 basic_block bb = ifc_bbs[i]; 1359 gphi_iterator itr; 1360 1361 for (itr = gsi_start_phis (bb); !gsi_end_p (itr); gsi_next (&itr)) 1362 if (!if_convertible_phi_p (loop, bb, itr.phi (), 1363 *any_mask_load_store)) 1364 return false; 1365 } 1366 1367 if (dump_file) 1368 fprintf (dump_file, "Applying if-conversion\n"); 1369 1370 return true; 1371} 1372 1373/* Return true when LOOP is if-convertible. 1374 LOOP is if-convertible if: 1375 - it is innermost, 1376 - it has two or more basic blocks, 1377 - it has only one exit, 1378 - loop header is not the exit edge, 1379 - if its basic blocks and phi nodes are if convertible. */ 1380 1381static bool 1382if_convertible_loop_p (struct loop *loop, bool *any_mask_load_store) 1383{ 1384 edge e; 1385 edge_iterator ei; 1386 bool res = false; 1387 vec<data_reference_p> refs; 1388 vec<ddr_p> ddrs; 1389 1390 /* Handle only innermost loop. */ 1391 if (!loop || loop->inner) 1392 { 1393 if (dump_file && (dump_flags & TDF_DETAILS)) 1394 fprintf (dump_file, "not innermost loop\n"); 1395 return false; 1396 } 1397 1398 /* If only one block, no need for if-conversion. */ 1399 if (loop->num_nodes <= 2) 1400 { 1401 if (dump_file && (dump_flags & TDF_DETAILS)) 1402 fprintf (dump_file, "less than 2 basic blocks\n"); 1403 return false; 1404 } 1405 1406 /* More than one loop exit is too much to handle. */ 1407 if (!single_exit (loop)) 1408 { 1409 if (dump_file && (dump_flags & TDF_DETAILS)) 1410 fprintf (dump_file, "multiple exits\n"); 1411 return false; 1412 } 1413 1414 /* If one of the loop header's edge is an exit edge then do not 1415 apply if-conversion. */ 1416 FOR_EACH_EDGE (e, ei, loop->header->succs) 1417 if (loop_exit_edge_p (loop, e)) 1418 return false; 1419 1420 refs.create (5); 1421 ddrs.create (25); 1422 auto_vec<loop_p, 3> loop_nest; 1423 res = if_convertible_loop_p_1 (loop, &loop_nest, &refs, &ddrs, 1424 any_mask_load_store); 1425 1426 if (flag_tree_loop_if_convert_stores) 1427 { 1428 data_reference_p dr; 1429 unsigned int i; 1430 1431 for (i = 0; refs.iterate (i, &dr); i++) 1432 free (dr->aux); 1433 } 1434 1435 free_data_refs (refs); 1436 free_dependence_relations (ddrs); 1437 return res; 1438} 1439 1440/* Returns true if def-stmt for phi argument ARG is simple increment/decrement 1441 which is in predicated basic block. 1442 In fact, the following PHI pattern is searching: 1443 loop-header: 1444 reduc_1 = PHI <..., reduc_2> 1445 ... 1446 if (...) 1447 reduc_3 = ... 1448 reduc_2 = PHI <reduc_1, reduc_3> 1449 1450 ARG_0 and ARG_1 are correspondent PHI arguments. 1451 REDUC, OP0 and OP1 contain reduction stmt and its operands. 1452 EXTENDED is true if PHI has > 2 arguments. */ 1453 1454static bool 1455is_cond_scalar_reduction (gimple phi, gimple *reduc, tree arg_0, tree arg_1, 1456 tree *op0, tree *op1, bool extended) 1457{ 1458 tree lhs, r_op1, r_op2; 1459 gimple stmt; 1460 gimple header_phi = NULL; 1461 enum tree_code reduction_op; 1462 basic_block bb = gimple_bb (phi); 1463 struct loop *loop = bb->loop_father; 1464 edge latch_e = loop_latch_edge (loop); 1465 imm_use_iterator imm_iter; 1466 use_operand_p use_p; 1467 edge e; 1468 edge_iterator ei; 1469 bool result = false; 1470 if (TREE_CODE (arg_0) != SSA_NAME || TREE_CODE (arg_1) != SSA_NAME) 1471 return false; 1472 1473 if (!extended && gimple_code (SSA_NAME_DEF_STMT (arg_0)) == GIMPLE_PHI) 1474 { 1475 lhs = arg_1; 1476 header_phi = SSA_NAME_DEF_STMT (arg_0); 1477 stmt = SSA_NAME_DEF_STMT (arg_1); 1478 } 1479 else if (gimple_code (SSA_NAME_DEF_STMT (arg_1)) == GIMPLE_PHI) 1480 { 1481 lhs = arg_0; 1482 header_phi = SSA_NAME_DEF_STMT (arg_1); 1483 stmt = SSA_NAME_DEF_STMT (arg_0); 1484 } 1485 else 1486 return false; 1487 if (gimple_bb (header_phi) != loop->header) 1488 return false; 1489 1490 if (PHI_ARG_DEF_FROM_EDGE (header_phi, latch_e) != PHI_RESULT (phi)) 1491 return false; 1492 1493 if (gimple_code (stmt) != GIMPLE_ASSIGN 1494 || gimple_has_volatile_ops (stmt)) 1495 return false; 1496 1497 if (!flow_bb_inside_loop_p (loop, gimple_bb (stmt))) 1498 return false; 1499 1500 if (!is_predicated (gimple_bb (stmt))) 1501 return false; 1502 1503 /* Check that stmt-block is predecessor of phi-block. */ 1504 FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->succs) 1505 if (e->dest == bb) 1506 { 1507 result = true; 1508 break; 1509 } 1510 if (!result) 1511 return false; 1512 1513 if (!has_single_use (lhs)) 1514 return false; 1515 1516 reduction_op = gimple_assign_rhs_code (stmt); 1517 if (reduction_op != PLUS_EXPR && reduction_op != MINUS_EXPR) 1518 return false; 1519 r_op1 = gimple_assign_rhs1 (stmt); 1520 r_op2 = gimple_assign_rhs2 (stmt); 1521 1522 /* Make R_OP1 to hold reduction variable. */ 1523 if (r_op2 == PHI_RESULT (header_phi) 1524 && reduction_op == PLUS_EXPR) 1525 { 1526 tree tmp = r_op1; 1527 r_op1 = r_op2; 1528 r_op2 = tmp; 1529 } 1530 else if (r_op1 != PHI_RESULT (header_phi)) 1531 return false; 1532 1533 /* Check that R_OP1 is used in reduction stmt or in PHI only. */ 1534 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, r_op1) 1535 { 1536 gimple use_stmt = USE_STMT (use_p); 1537 if (is_gimple_debug (use_stmt)) 1538 continue; 1539 if (use_stmt == stmt) 1540 continue; 1541 if (gimple_code (use_stmt) != GIMPLE_PHI) 1542 return false; 1543 } 1544 1545 *op0 = r_op1; *op1 = r_op2; 1546 *reduc = stmt; 1547 return true; 1548} 1549 1550/* Converts conditional scalar reduction into unconditional form, e.g. 1551 bb_4 1552 if (_5 != 0) goto bb_5 else goto bb_6 1553 end_bb_4 1554 bb_5 1555 res_6 = res_13 + 1; 1556 end_bb_5 1557 bb_6 1558 # res_2 = PHI <res_13(4), res_6(5)> 1559 end_bb_6 1560 1561 will be converted into sequence 1562 _ifc__1 = _5 != 0 ? 1 : 0; 1563 res_2 = res_13 + _ifc__1; 1564 Argument SWAP tells that arguments of conditional expression should be 1565 swapped. 1566 Returns rhs of resulting PHI assignment. */ 1567 1568static tree 1569convert_scalar_cond_reduction (gimple reduc, gimple_stmt_iterator *gsi, 1570 tree cond, tree op0, tree op1, bool swap) 1571{ 1572 gimple_stmt_iterator stmt_it; 1573 gimple new_assign; 1574 tree rhs; 1575 tree rhs1 = gimple_assign_rhs1 (reduc); 1576 tree tmp = make_temp_ssa_name (TREE_TYPE (rhs1), NULL, "_ifc_"); 1577 tree c; 1578 tree zero = build_zero_cst (TREE_TYPE (rhs1)); 1579 1580 if (dump_file && (dump_flags & TDF_DETAILS)) 1581 { 1582 fprintf (dump_file, "Found cond scalar reduction.\n"); 1583 print_gimple_stmt (dump_file, reduc, 0, TDF_SLIM); 1584 } 1585 1586 /* Build cond expression using COND and constant operand 1587 of reduction rhs. */ 1588 c = fold_build_cond_expr (TREE_TYPE (rhs1), 1589 unshare_expr (cond), 1590 swap ? zero : op1, 1591 swap ? op1 : zero); 1592 1593 /* Create assignment stmt and insert it at GSI. */ 1594 new_assign = gimple_build_assign (tmp, c); 1595 gsi_insert_before (gsi, new_assign, GSI_SAME_STMT); 1596 /* Build rhs for unconditional increment/decrement. */ 1597 rhs = fold_build2 (gimple_assign_rhs_code (reduc), 1598 TREE_TYPE (rhs1), op0, tmp); 1599 1600 /* Delete original reduction stmt. */ 1601 stmt_it = gsi_for_stmt (reduc); 1602 gsi_remove (&stmt_it, true); 1603 release_defs (reduc); 1604 return rhs; 1605} 1606 1607/* Helpers for PHI arguments hashtable map. */ 1608 1609struct phi_args_hash_traits : default_hashmap_traits 1610{ 1611 static inline hashval_t hash (tree); 1612 static inline bool equal_keys (tree, tree); 1613}; 1614 1615inline hashval_t 1616phi_args_hash_traits::hash (tree value) 1617{ 1618 return iterative_hash_expr (value, 0); 1619} 1620 1621inline bool 1622phi_args_hash_traits::equal_keys (tree value1, tree value2) 1623{ 1624 return operand_equal_p (value1, value2, 0); 1625} 1626 1627 /* Produce condition for all occurrences of ARG in PHI node. */ 1628 1629static tree 1630gen_phi_arg_condition (gphi *phi, vec<int> *occur, 1631 gimple_stmt_iterator *gsi) 1632{ 1633 int len; 1634 int i; 1635 tree cond = NULL_TREE; 1636 tree c; 1637 edge e; 1638 1639 len = occur->length (); 1640 gcc_assert (len > 0); 1641 for (i = 0; i < len; i++) 1642 { 1643 e = gimple_phi_arg_edge (phi, (*occur)[i]); 1644 c = bb_predicate (e->src); 1645 if (is_true_predicate (c)) 1646 continue; 1647 c = force_gimple_operand_gsi_1 (gsi, unshare_expr (c), 1648 is_gimple_condexpr, NULL_TREE, 1649 true, GSI_SAME_STMT); 1650 if (cond != NULL_TREE) 1651 { 1652 /* Must build OR expression. */ 1653 cond = fold_or_predicates (EXPR_LOCATION (c), c, cond); 1654 cond = force_gimple_operand_gsi_1 (gsi, unshare_expr (cond), 1655 is_gimple_condexpr, NULL_TREE, 1656 true, GSI_SAME_STMT); 1657 } 1658 else 1659 cond = c; 1660 } 1661 gcc_assert (cond != NULL_TREE); 1662 return cond; 1663} 1664 1665/* Replace a scalar PHI node with a COND_EXPR using COND as condition. 1666 This routine can handle PHI nodes with more than two arguments. 1667 1668 For example, 1669 S1: A = PHI <x1(1), x2(5)> 1670 is converted into, 1671 S2: A = cond ? x1 : x2; 1672 1673 The generated code is inserted at GSI that points to the top of 1674 basic block's statement list. 1675 If PHI node has more than two arguments a chain of conditional 1676 expression is produced. */ 1677 1678 1679static void 1680predicate_scalar_phi (gphi *phi, gimple_stmt_iterator *gsi) 1681{ 1682 gimple new_stmt = NULL, reduc; 1683 tree rhs, res, arg0, arg1, op0, op1, scev; 1684 tree cond; 1685 unsigned int index0; 1686 unsigned int max, args_len; 1687 edge e; 1688 basic_block bb; 1689 unsigned int i; 1690 1691 res = gimple_phi_result (phi); 1692 if (virtual_operand_p (res)) 1693 return; 1694 1695 if ((rhs = degenerate_phi_result (phi)) 1696 || ((scev = analyze_scalar_evolution (gimple_bb (phi)->loop_father, 1697 res)) 1698 && !chrec_contains_undetermined (scev) 1699 && scev != res 1700 && (rhs = gimple_phi_arg_def (phi, 0)))) 1701 { 1702 if (dump_file && (dump_flags & TDF_DETAILS)) 1703 { 1704 fprintf (dump_file, "Degenerate phi!\n"); 1705 print_gimple_stmt (dump_file, phi, 0, TDF_SLIM); 1706 } 1707 new_stmt = gimple_build_assign (res, rhs); 1708 gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT); 1709 update_stmt (new_stmt); 1710 return; 1711 } 1712 1713 bb = gimple_bb (phi); 1714 if (EDGE_COUNT (bb->preds) == 2) 1715 { 1716 /* Predicate ordinary PHI node with 2 arguments. */ 1717 edge first_edge, second_edge; 1718 basic_block true_bb; 1719 first_edge = EDGE_PRED (bb, 0); 1720 second_edge = EDGE_PRED (bb, 1); 1721 cond = bb_predicate (first_edge->src); 1722 if (TREE_CODE (cond) == TRUTH_NOT_EXPR) 1723 { 1724 edge tmp_edge = first_edge; 1725 first_edge = second_edge; 1726 second_edge = tmp_edge; 1727 } 1728 if (EDGE_COUNT (first_edge->src->succs) > 1) 1729 { 1730 cond = bb_predicate (second_edge->src); 1731 if (TREE_CODE (cond) == TRUTH_NOT_EXPR) 1732 cond = TREE_OPERAND (cond, 0); 1733 else 1734 first_edge = second_edge; 1735 } 1736 else 1737 cond = bb_predicate (first_edge->src); 1738 /* Gimplify the condition to a valid cond-expr conditonal operand. */ 1739 cond = force_gimple_operand_gsi_1 (gsi, unshare_expr (cond), 1740 is_gimple_condexpr, NULL_TREE, 1741 true, GSI_SAME_STMT); 1742 true_bb = first_edge->src; 1743 if (EDGE_PRED (bb, 1)->src == true_bb) 1744 { 1745 arg0 = gimple_phi_arg_def (phi, 1); 1746 arg1 = gimple_phi_arg_def (phi, 0); 1747 } 1748 else 1749 { 1750 arg0 = gimple_phi_arg_def (phi, 0); 1751 arg1 = gimple_phi_arg_def (phi, 1); 1752 } 1753 if (is_cond_scalar_reduction (phi, &reduc, arg0, arg1, 1754 &op0, &op1, false)) 1755 /* Convert reduction stmt into vectorizable form. */ 1756 rhs = convert_scalar_cond_reduction (reduc, gsi, cond, op0, op1, 1757 true_bb != gimple_bb (reduc)); 1758 else 1759 /* Build new RHS using selected condition and arguments. */ 1760 rhs = fold_build_cond_expr (TREE_TYPE (res), unshare_expr (cond), 1761 arg0, arg1); 1762 new_stmt = gimple_build_assign (res, rhs); 1763 gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT); 1764 update_stmt (new_stmt); 1765 1766 if (dump_file && (dump_flags & TDF_DETAILS)) 1767 { 1768 fprintf (dump_file, "new phi replacement stmt\n"); 1769 print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM); 1770 } 1771 return; 1772 } 1773 1774 /* Create hashmap for PHI node which contain vector of argument indexes 1775 having the same value. */ 1776 bool swap = false; 1777 hash_map<tree, auto_vec<int>, phi_args_hash_traits> phi_arg_map; 1778 unsigned int num_args = gimple_phi_num_args (phi); 1779 int max_ind = -1; 1780 /* Vector of different PHI argument values. */ 1781 auto_vec<tree> args (num_args); 1782 1783 /* Compute phi_arg_map. */ 1784 for (i = 0; i < num_args; i++) 1785 { 1786 tree arg; 1787 1788 arg = gimple_phi_arg_def (phi, i); 1789 if (!phi_arg_map.get (arg)) 1790 args.quick_push (arg); 1791 phi_arg_map.get_or_insert (arg).safe_push (i); 1792 } 1793 1794 /* Determine element with max number of occurrences. */ 1795 max_ind = -1; 1796 max = 1; 1797 args_len = args.length (); 1798 for (i = 0; i < args_len; i++) 1799 { 1800 unsigned int len; 1801 if ((len = phi_arg_map.get (args[i])->length ()) > max) 1802 { 1803 max_ind = (int) i; 1804 max = len; 1805 } 1806 } 1807 1808 /* Put element with max number of occurences to the end of ARGS. */ 1809 if (max_ind != -1 && max_ind +1 != (int) args_len) 1810 { 1811 tree tmp = args[args_len - 1]; 1812 args[args_len - 1] = args[max_ind]; 1813 args[max_ind] = tmp; 1814 } 1815 1816 /* Handle one special case when number of arguments with different values 1817 is equal 2 and one argument has the only occurrence. Such PHI can be 1818 handled as if would have only 2 arguments. */ 1819 if (args_len == 2 && phi_arg_map.get (args[0])->length () == 1) 1820 { 1821 vec<int> *indexes; 1822 indexes = phi_arg_map.get (args[0]); 1823 index0 = (*indexes)[0]; 1824 arg0 = args[0]; 1825 arg1 = args[1]; 1826 e = gimple_phi_arg_edge (phi, index0); 1827 cond = bb_predicate (e->src); 1828 if (TREE_CODE (cond) == TRUTH_NOT_EXPR) 1829 { 1830 swap = true; 1831 cond = TREE_OPERAND (cond, 0); 1832 } 1833 /* Gimplify the condition to a valid cond-expr conditonal operand. */ 1834 cond = force_gimple_operand_gsi_1 (gsi, unshare_expr (cond), 1835 is_gimple_condexpr, NULL_TREE, 1836 true, GSI_SAME_STMT); 1837 if (!(is_cond_scalar_reduction (phi, &reduc, arg0 , arg1, 1838 &op0, &op1, true))) 1839 rhs = fold_build_cond_expr (TREE_TYPE (res), unshare_expr (cond), 1840 swap? arg1 : arg0, 1841 swap? arg0 : arg1); 1842 else 1843 /* Convert reduction stmt into vectorizable form. */ 1844 rhs = convert_scalar_cond_reduction (reduc, gsi, cond, op0, op1, 1845 swap); 1846 new_stmt = gimple_build_assign (res, rhs); 1847 gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT); 1848 update_stmt (new_stmt); 1849 } 1850 else 1851 { 1852 /* Common case. */ 1853 vec<int> *indexes; 1854 tree type = TREE_TYPE (gimple_phi_result (phi)); 1855 tree lhs; 1856 arg1 = args[1]; 1857 for (i = 0; i < args_len; i++) 1858 { 1859 arg0 = args[i]; 1860 indexes = phi_arg_map.get (args[i]); 1861 if (i != args_len - 1) 1862 lhs = make_temp_ssa_name (type, NULL, "_ifc_"); 1863 else 1864 lhs = res; 1865 cond = gen_phi_arg_condition (phi, indexes, gsi); 1866 rhs = fold_build_cond_expr (type, unshare_expr (cond), 1867 arg0, arg1); 1868 new_stmt = gimple_build_assign (lhs, rhs); 1869 gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT); 1870 update_stmt (new_stmt); 1871 arg1 = lhs; 1872 } 1873 } 1874 1875 if (dump_file && (dump_flags & TDF_DETAILS)) 1876 { 1877 fprintf (dump_file, "new extended phi replacement stmt\n"); 1878 print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM); 1879 } 1880} 1881 1882/* Replaces in LOOP all the scalar phi nodes other than those in the 1883 LOOP->header block with conditional modify expressions. */ 1884 1885static void 1886predicate_all_scalar_phis (struct loop *loop) 1887{ 1888 basic_block bb; 1889 unsigned int orig_loop_num_nodes = loop->num_nodes; 1890 unsigned int i; 1891 1892 for (i = 1; i < orig_loop_num_nodes; i++) 1893 { 1894 gphi *phi; 1895 gimple_stmt_iterator gsi; 1896 gphi_iterator phi_gsi; 1897 bb = ifc_bbs[i]; 1898 1899 if (bb == loop->header) 1900 continue; 1901 1902 if (EDGE_COUNT (bb->preds) == 1) 1903 continue; 1904 1905 phi_gsi = gsi_start_phis (bb); 1906 if (gsi_end_p (phi_gsi)) 1907 continue; 1908 1909 gsi = gsi_after_labels (bb); 1910 while (!gsi_end_p (phi_gsi)) 1911 { 1912 phi = phi_gsi.phi (); 1913 predicate_scalar_phi (phi, &gsi); 1914 release_phi_node (phi); 1915 gsi_next (&phi_gsi); 1916 } 1917 1918 set_phi_nodes (bb, NULL); 1919 } 1920} 1921 1922/* Insert in each basic block of LOOP the statements produced by the 1923 gimplification of the predicates. */ 1924 1925static void 1926insert_gimplified_predicates (loop_p loop, bool any_mask_load_store) 1927{ 1928 unsigned int i; 1929 1930 for (i = 0; i < loop->num_nodes; i++) 1931 { 1932 basic_block bb = ifc_bbs[i]; 1933 gimple_seq stmts; 1934 if (!is_predicated (bb)) 1935 gcc_assert (bb_predicate_gimplified_stmts (bb) == NULL); 1936 if (!is_predicated (bb)) 1937 { 1938 /* Do not insert statements for a basic block that is not 1939 predicated. Also make sure that the predicate of the 1940 basic block is set to true. */ 1941 reset_bb_predicate (bb); 1942 continue; 1943 } 1944 1945 stmts = bb_predicate_gimplified_stmts (bb); 1946 if (stmts) 1947 { 1948 if (flag_tree_loop_if_convert_stores 1949 || any_mask_load_store) 1950 { 1951 /* Insert the predicate of the BB just after the label, 1952 as the if-conversion of memory writes will use this 1953 predicate. */ 1954 gimple_stmt_iterator gsi = gsi_after_labels (bb); 1955 gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT); 1956 } 1957 else 1958 { 1959 /* Insert the predicate of the BB at the end of the BB 1960 as this would reduce the register pressure: the only 1961 use of this predicate will be in successor BBs. */ 1962 gimple_stmt_iterator gsi = gsi_last_bb (bb); 1963 1964 if (gsi_end_p (gsi) 1965 || stmt_ends_bb_p (gsi_stmt (gsi))) 1966 gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT); 1967 else 1968 gsi_insert_seq_after (&gsi, stmts, GSI_SAME_STMT); 1969 } 1970 1971 /* Once the sequence is code generated, set it to NULL. */ 1972 set_bb_predicate_gimplified_stmts (bb, NULL); 1973 } 1974 } 1975} 1976 1977/* Helper function for predicate_mem_writes. Returns index of existent 1978 mask if it was created for given SIZE and -1 otherwise. */ 1979 1980static int 1981mask_exists (int size, vec<int> vec) 1982{ 1983 unsigned int ix; 1984 int v; 1985 FOR_EACH_VEC_ELT (vec, ix, v) 1986 if (v == size) 1987 return (int) ix; 1988 return -1; 1989} 1990 1991/* Predicate each write to memory in LOOP. 1992 1993 This function transforms control flow constructs containing memory 1994 writes of the form: 1995 1996 | for (i = 0; i < N; i++) 1997 | if (cond) 1998 | A[i] = expr; 1999 2000 into the following form that does not contain control flow: 2001 2002 | for (i = 0; i < N; i++) 2003 | A[i] = cond ? expr : A[i]; 2004 2005 The original CFG looks like this: 2006 2007 | bb_0 2008 | i = 0 2009 | end_bb_0 2010 | 2011 | bb_1 2012 | if (i < N) goto bb_5 else goto bb_2 2013 | end_bb_1 2014 | 2015 | bb_2 2016 | cond = some_computation; 2017 | if (cond) goto bb_3 else goto bb_4 2018 | end_bb_2 2019 | 2020 | bb_3 2021 | A[i] = expr; 2022 | goto bb_4 2023 | end_bb_3 2024 | 2025 | bb_4 2026 | goto bb_1 2027 | end_bb_4 2028 2029 insert_gimplified_predicates inserts the computation of the COND 2030 expression at the beginning of the destination basic block: 2031 2032 | bb_0 2033 | i = 0 2034 | end_bb_0 2035 | 2036 | bb_1 2037 | if (i < N) goto bb_5 else goto bb_2 2038 | end_bb_1 2039 | 2040 | bb_2 2041 | cond = some_computation; 2042 | if (cond) goto bb_3 else goto bb_4 2043 | end_bb_2 2044 | 2045 | bb_3 2046 | cond = some_computation; 2047 | A[i] = expr; 2048 | goto bb_4 2049 | end_bb_3 2050 | 2051 | bb_4 2052 | goto bb_1 2053 | end_bb_4 2054 2055 predicate_mem_writes is then predicating the memory write as follows: 2056 2057 | bb_0 2058 | i = 0 2059 | end_bb_0 2060 | 2061 | bb_1 2062 | if (i < N) goto bb_5 else goto bb_2 2063 | end_bb_1 2064 | 2065 | bb_2 2066 | if (cond) goto bb_3 else goto bb_4 2067 | end_bb_2 2068 | 2069 | bb_3 2070 | cond = some_computation; 2071 | A[i] = cond ? expr : A[i]; 2072 | goto bb_4 2073 | end_bb_3 2074 | 2075 | bb_4 2076 | goto bb_1 2077 | end_bb_4 2078 2079 and finally combine_blocks removes the basic block boundaries making 2080 the loop vectorizable: 2081 2082 | bb_0 2083 | i = 0 2084 | if (i < N) goto bb_5 else goto bb_1 2085 | end_bb_0 2086 | 2087 | bb_1 2088 | cond = some_computation; 2089 | A[i] = cond ? expr : A[i]; 2090 | if (i < N) goto bb_5 else goto bb_4 2091 | end_bb_1 2092 | 2093 | bb_4 2094 | goto bb_1 2095 | end_bb_4 2096*/ 2097 2098static void 2099predicate_mem_writes (loop_p loop) 2100{ 2101 unsigned int i, orig_loop_num_nodes = loop->num_nodes; 2102 auto_vec<int, 1> vect_sizes; 2103 auto_vec<tree, 1> vect_masks; 2104 2105 for (i = 1; i < orig_loop_num_nodes; i++) 2106 { 2107 gimple_stmt_iterator gsi; 2108 basic_block bb = ifc_bbs[i]; 2109 tree cond = bb_predicate (bb); 2110 bool swap; 2111 gimple stmt; 2112 int index; 2113 2114 if (is_true_predicate (cond)) 2115 continue; 2116 2117 swap = false; 2118 if (TREE_CODE (cond) == TRUTH_NOT_EXPR) 2119 { 2120 swap = true; 2121 cond = TREE_OPERAND (cond, 0); 2122 } 2123 2124 vect_sizes.truncate (0); 2125 vect_masks.truncate (0); 2126 2127 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 2128 if (!gimple_assign_single_p (stmt = gsi_stmt (gsi))) 2129 continue; 2130 else if (gimple_plf (stmt, GF_PLF_2)) 2131 { 2132 tree lhs = gimple_assign_lhs (stmt); 2133 tree rhs = gimple_assign_rhs1 (stmt); 2134 tree ref, addr, ptr, masktype, mask_op0, mask_op1, mask; 2135 gimple new_stmt; 2136 int bitsize = GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (lhs))); 2137 ref = TREE_CODE (lhs) == SSA_NAME ? rhs : lhs; 2138 mark_addressable (ref); 2139 addr = force_gimple_operand_gsi (&gsi, build_fold_addr_expr (ref), 2140 true, NULL_TREE, true, 2141 GSI_SAME_STMT); 2142 if (!vect_sizes.is_empty () 2143 && (index = mask_exists (bitsize, vect_sizes)) != -1) 2144 /* Use created mask. */ 2145 mask = vect_masks[index]; 2146 else 2147 { 2148 masktype = build_nonstandard_integer_type (bitsize, 1); 2149 mask_op0 = build_int_cst (masktype, swap ? 0 : -1); 2150 mask_op1 = build_int_cst (masktype, swap ? -1 : 0); 2151 cond = force_gimple_operand_gsi_1 (&gsi, unshare_expr (cond), 2152 is_gimple_condexpr, 2153 NULL_TREE, 2154 true, GSI_SAME_STMT); 2155 mask = fold_build_cond_expr (masktype, unshare_expr (cond), 2156 mask_op0, mask_op1); 2157 mask = ifc_temp_var (masktype, mask, &gsi); 2158 /* Save mask and its size for further use. */ 2159 vect_sizes.safe_push (bitsize); 2160 vect_masks.safe_push (mask); 2161 } 2162 ptr = build_int_cst (reference_alias_ptr_type (ref), 0); 2163 /* Copy points-to info if possible. */ 2164 if (TREE_CODE (addr) == SSA_NAME && !SSA_NAME_PTR_INFO (addr)) 2165 copy_ref_info (build2 (MEM_REF, TREE_TYPE (ref), addr, ptr), 2166 ref); 2167 if (TREE_CODE (lhs) == SSA_NAME) 2168 { 2169 new_stmt 2170 = gimple_build_call_internal (IFN_MASK_LOAD, 3, addr, 2171 ptr, mask); 2172 gimple_call_set_lhs (new_stmt, lhs); 2173 } 2174 else 2175 new_stmt 2176 = gimple_build_call_internal (IFN_MASK_STORE, 4, addr, ptr, 2177 mask, rhs); 2178 gsi_replace (&gsi, new_stmt, true); 2179 } 2180 else if (gimple_vdef (stmt)) 2181 { 2182 tree lhs = gimple_assign_lhs (stmt); 2183 tree rhs = gimple_assign_rhs1 (stmt); 2184 tree type = TREE_TYPE (lhs); 2185 2186 lhs = ifc_temp_var (type, unshare_expr (lhs), &gsi); 2187 rhs = ifc_temp_var (type, unshare_expr (rhs), &gsi); 2188 if (swap) 2189 { 2190 tree tem = lhs; 2191 lhs = rhs; 2192 rhs = tem; 2193 } 2194 cond = force_gimple_operand_gsi_1 (&gsi, unshare_expr (cond), 2195 is_gimple_condexpr, NULL_TREE, 2196 true, GSI_SAME_STMT); 2197 rhs = fold_build_cond_expr (type, unshare_expr (cond), rhs, lhs); 2198 gimple_assign_set_rhs1 (stmt, ifc_temp_var (type, rhs, &gsi)); 2199 update_stmt (stmt); 2200 } 2201 } 2202} 2203 2204/* Remove all GIMPLE_CONDs and GIMPLE_LABELs of all the basic blocks 2205 other than the exit and latch of the LOOP. Also resets the 2206 GIMPLE_DEBUG information. */ 2207 2208static void 2209remove_conditions_and_labels (loop_p loop) 2210{ 2211 gimple_stmt_iterator gsi; 2212 unsigned int i; 2213 2214 for (i = 0; i < loop->num_nodes; i++) 2215 { 2216 basic_block bb = ifc_bbs[i]; 2217 2218 if (bb_with_exit_edge_p (loop, bb) 2219 || bb == loop->latch) 2220 continue; 2221 2222 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); ) 2223 switch (gimple_code (gsi_stmt (gsi))) 2224 { 2225 case GIMPLE_COND: 2226 case GIMPLE_LABEL: 2227 gsi_remove (&gsi, true); 2228 break; 2229 2230 case GIMPLE_DEBUG: 2231 /* ??? Should there be conditional GIMPLE_DEBUG_BINDs? */ 2232 if (gimple_debug_bind_p (gsi_stmt (gsi))) 2233 { 2234 gimple_debug_bind_reset_value (gsi_stmt (gsi)); 2235 update_stmt (gsi_stmt (gsi)); 2236 } 2237 gsi_next (&gsi); 2238 break; 2239 2240 default: 2241 gsi_next (&gsi); 2242 } 2243 } 2244} 2245 2246/* Combine all the basic blocks from LOOP into one or two super basic 2247 blocks. Replace PHI nodes with conditional modify expressions. */ 2248 2249static void 2250combine_blocks (struct loop *loop, bool any_mask_load_store) 2251{ 2252 basic_block bb, exit_bb, merge_target_bb; 2253 unsigned int orig_loop_num_nodes = loop->num_nodes; 2254 unsigned int i; 2255 edge e; 2256 edge_iterator ei; 2257 2258 predicate_bbs (loop); 2259 remove_conditions_and_labels (loop); 2260 insert_gimplified_predicates (loop, any_mask_load_store); 2261 predicate_all_scalar_phis (loop); 2262 2263 if (flag_tree_loop_if_convert_stores || any_mask_load_store) 2264 predicate_mem_writes (loop); 2265 2266 /* Merge basic blocks: first remove all the edges in the loop, 2267 except for those from the exit block. */ 2268 exit_bb = NULL; 2269 bool *predicated = XNEWVEC (bool, orig_loop_num_nodes); 2270 for (i = 0; i < orig_loop_num_nodes; i++) 2271 { 2272 bb = ifc_bbs[i]; 2273 predicated[i] = !is_true_predicate (bb_predicate (bb)); 2274 free_bb_predicate (bb); 2275 if (bb_with_exit_edge_p (loop, bb)) 2276 { 2277 gcc_assert (exit_bb == NULL); 2278 exit_bb = bb; 2279 } 2280 } 2281 gcc_assert (exit_bb != loop->latch); 2282 2283 for (i = 1; i < orig_loop_num_nodes; i++) 2284 { 2285 bb = ifc_bbs[i]; 2286 2287 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei));) 2288 { 2289 if (e->src == exit_bb) 2290 ei_next (&ei); 2291 else 2292 remove_edge (e); 2293 } 2294 } 2295 2296 if (exit_bb != NULL) 2297 { 2298 if (exit_bb != loop->header) 2299 { 2300 /* Connect this node to loop header. */ 2301 make_edge (loop->header, exit_bb, EDGE_FALLTHRU); 2302 set_immediate_dominator (CDI_DOMINATORS, exit_bb, loop->header); 2303 } 2304 2305 /* Redirect non-exit edges to loop->latch. */ 2306 FOR_EACH_EDGE (e, ei, exit_bb->succs) 2307 { 2308 if (!loop_exit_edge_p (loop, e)) 2309 redirect_edge_and_branch (e, loop->latch); 2310 } 2311 set_immediate_dominator (CDI_DOMINATORS, loop->latch, exit_bb); 2312 } 2313 else 2314 { 2315 /* If the loop does not have an exit, reconnect header and latch. */ 2316 make_edge (loop->header, loop->latch, EDGE_FALLTHRU); 2317 set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header); 2318 } 2319 2320 merge_target_bb = loop->header; 2321 for (i = 1; i < orig_loop_num_nodes; i++) 2322 { 2323 gimple_stmt_iterator gsi; 2324 gimple_stmt_iterator last; 2325 2326 bb = ifc_bbs[i]; 2327 2328 if (bb == exit_bb || bb == loop->latch) 2329 continue; 2330 2331 /* Make stmts member of loop->header and clear range info from all stmts 2332 in BB which is now no longer executed conditional on a predicate we 2333 could have derived it from. */ 2334 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 2335 { 2336 gimple stmt = gsi_stmt (gsi); 2337 gimple_set_bb (stmt, merge_target_bb); 2338 if (predicated[i]) 2339 { 2340 ssa_op_iter i; 2341 tree op; 2342 FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_DEF) 2343 reset_flow_sensitive_info (op); 2344 } 2345 } 2346 2347 /* Update stmt list. */ 2348 last = gsi_last_bb (merge_target_bb); 2349 gsi_insert_seq_after (&last, bb_seq (bb), GSI_NEW_STMT); 2350 set_bb_seq (bb, NULL); 2351 2352 delete_basic_block (bb); 2353 } 2354 2355 /* If possible, merge loop header to the block with the exit edge. 2356 This reduces the number of basic blocks to two, to please the 2357 vectorizer that handles only loops with two nodes. */ 2358 if (exit_bb 2359 && exit_bb != loop->header 2360 && can_merge_blocks_p (loop->header, exit_bb)) 2361 merge_blocks (loop->header, exit_bb); 2362 2363 free (ifc_bbs); 2364 ifc_bbs = NULL; 2365 free (predicated); 2366} 2367 2368/* Version LOOP before if-converting it, the original loop 2369 will be then if-converted, the new copy of the loop will not, 2370 and the LOOP_VECTORIZED internal call will be guarding which 2371 loop to execute. The vectorizer pass will fold this 2372 internal call into either true or false. */ 2373 2374static bool 2375version_loop_for_if_conversion (struct loop *loop) 2376{ 2377 basic_block cond_bb; 2378 tree cond = make_ssa_name (boolean_type_node); 2379 struct loop *new_loop; 2380 gimple g; 2381 gimple_stmt_iterator gsi; 2382 2383 g = gimple_build_call_internal (IFN_LOOP_VECTORIZED, 2, 2384 build_int_cst (integer_type_node, loop->num), 2385 integer_zero_node); 2386 gimple_call_set_lhs (g, cond); 2387 2388 initialize_original_copy_tables (); 2389 new_loop = loop_version (loop, cond, &cond_bb, 2390 REG_BR_PROB_BASE, REG_BR_PROB_BASE, 2391 REG_BR_PROB_BASE, true); 2392 free_original_copy_tables (); 2393 if (new_loop == NULL) 2394 return false; 2395 new_loop->dont_vectorize = true; 2396 new_loop->force_vectorize = false; 2397 gsi = gsi_last_bb (cond_bb); 2398 gimple_call_set_arg (g, 1, build_int_cst (integer_type_node, new_loop->num)); 2399 gsi_insert_before (&gsi, g, GSI_SAME_STMT); 2400 update_ssa (TODO_update_ssa); 2401 return true; 2402} 2403 2404/* Performs splitting of critical edges if aggressive_if_conv is true. 2405 Returns false if loop won't be if converted and true otherwise. */ 2406 2407static bool 2408ifcvt_split_critical_edges (struct loop *loop) 2409{ 2410 basic_block *body; 2411 basic_block bb; 2412 unsigned int num = loop->num_nodes; 2413 unsigned int i; 2414 gimple stmt; 2415 edge e; 2416 edge_iterator ei; 2417 2418 if (num <= 2) 2419 return false; 2420 if (loop->inner) 2421 return false; 2422 if (!single_exit (loop)) 2423 return false; 2424 2425 body = get_loop_body (loop); 2426 for (i = 0; i < num; i++) 2427 { 2428 bb = body[i]; 2429 if (bb == loop->latch 2430 || bb_with_exit_edge_p (loop, bb)) 2431 continue; 2432 stmt = last_stmt (bb); 2433 /* Skip basic blocks not ending with conditional branch. */ 2434 if (!(stmt && gimple_code (stmt) == GIMPLE_COND)) 2435 continue; 2436 FOR_EACH_EDGE (e, ei, bb->succs) 2437 if (EDGE_CRITICAL_P (e) && e->dest->loop_father == loop) 2438 split_edge (e); 2439 } 2440 free (body); 2441 return true; 2442} 2443 2444/* Assumes that lhs of DEF_STMT have multiple uses. 2445 Delete one use by (1) creation of copy DEF_STMT with 2446 unique lhs; (2) change original use of lhs in one 2447 use statement with newly created lhs. */ 2448 2449static void 2450ifcvt_split_def_stmt (gimple def_stmt, gimple use_stmt) 2451{ 2452 tree var; 2453 tree lhs; 2454 gimple copy_stmt; 2455 gimple_stmt_iterator gsi; 2456 use_operand_p use_p; 2457 imm_use_iterator imm_iter; 2458 2459 var = gimple_assign_lhs (def_stmt); 2460 copy_stmt = gimple_copy (def_stmt); 2461 lhs = make_temp_ssa_name (TREE_TYPE (var), NULL, "_ifc_"); 2462 gimple_assign_set_lhs (copy_stmt, lhs); 2463 SSA_NAME_DEF_STMT (lhs) = copy_stmt; 2464 /* Insert copy of DEF_STMT. */ 2465 gsi = gsi_for_stmt (def_stmt); 2466 gsi_insert_after (&gsi, copy_stmt, GSI_SAME_STMT); 2467 /* Change use of var to lhs in use_stmt. */ 2468 if (dump_file && (dump_flags & TDF_DETAILS)) 2469 { 2470 fprintf (dump_file, "Change use of var "); 2471 print_generic_expr (dump_file, var, TDF_SLIM); 2472 fprintf (dump_file, " to "); 2473 print_generic_expr (dump_file, lhs, TDF_SLIM); 2474 fprintf (dump_file, "\n"); 2475 } 2476 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var) 2477 { 2478 if (USE_STMT (use_p) != use_stmt) 2479 continue; 2480 SET_USE (use_p, lhs); 2481 break; 2482 } 2483} 2484 2485/* Traverse bool pattern recursively starting from VAR. 2486 Save its def and use statements to defuse_list if VAR does 2487 not have single use. */ 2488 2489static void 2490ifcvt_walk_pattern_tree (tree var, vec<gimple> *defuse_list, 2491 gimple use_stmt) 2492{ 2493 tree rhs1, rhs2; 2494 enum tree_code code; 2495 gimple def_stmt; 2496 2497 def_stmt = SSA_NAME_DEF_STMT (var); 2498 if (gimple_code (def_stmt) != GIMPLE_ASSIGN) 2499 return; 2500 if (!has_single_use (var)) 2501 { 2502 /* Put def and use stmts into defuse_list. */ 2503 defuse_list->safe_push (def_stmt); 2504 defuse_list->safe_push (use_stmt); 2505 if (dump_file && (dump_flags & TDF_DETAILS)) 2506 { 2507 fprintf (dump_file, "Multiple lhs uses in stmt\n"); 2508 print_gimple_stmt (dump_file, def_stmt, 0, TDF_SLIM); 2509 } 2510 } 2511 rhs1 = gimple_assign_rhs1 (def_stmt); 2512 code = gimple_assign_rhs_code (def_stmt); 2513 switch (code) 2514 { 2515 case SSA_NAME: 2516 ifcvt_walk_pattern_tree (rhs1, defuse_list, def_stmt); 2517 break; 2518 CASE_CONVERT: 2519 if ((TYPE_PRECISION (TREE_TYPE (rhs1)) != 1 2520 || !TYPE_UNSIGNED (TREE_TYPE (rhs1))) 2521 && TREE_CODE (TREE_TYPE (rhs1)) != BOOLEAN_TYPE) 2522 break; 2523 ifcvt_walk_pattern_tree (rhs1, defuse_list, def_stmt); 2524 break; 2525 case BIT_NOT_EXPR: 2526 ifcvt_walk_pattern_tree (rhs1, defuse_list, def_stmt); 2527 break; 2528 case BIT_AND_EXPR: 2529 case BIT_IOR_EXPR: 2530 case BIT_XOR_EXPR: 2531 ifcvt_walk_pattern_tree (rhs1, defuse_list, def_stmt); 2532 rhs2 = gimple_assign_rhs2 (def_stmt); 2533 ifcvt_walk_pattern_tree (rhs2, defuse_list, def_stmt); 2534 break; 2535 default: 2536 break; 2537 } 2538 return; 2539} 2540 2541/* Returns true if STMT can be a root of bool pattern apllied 2542 by vectorizer. */ 2543 2544static bool 2545stmt_is_root_of_bool_pattern (gimple stmt) 2546{ 2547 enum tree_code code; 2548 tree lhs, rhs; 2549 2550 code = gimple_assign_rhs_code (stmt); 2551 if (CONVERT_EXPR_CODE_P (code)) 2552 { 2553 lhs = gimple_assign_lhs (stmt); 2554 rhs = gimple_assign_rhs1 (stmt); 2555 if (TREE_CODE (TREE_TYPE (rhs)) != BOOLEAN_TYPE) 2556 return false; 2557 if (TREE_CODE (TREE_TYPE (lhs)) == BOOLEAN_TYPE) 2558 return false; 2559 return true; 2560 } 2561 else if (code == COND_EXPR) 2562 { 2563 rhs = gimple_assign_rhs1 (stmt); 2564 if (TREE_CODE (rhs) != SSA_NAME) 2565 return false; 2566 return true; 2567 } 2568 return false; 2569} 2570 2571/* Traverse all statements in BB which correspondent to loop header to 2572 find out all statements which can start bool pattern applied by 2573 vectorizer and convert multiple uses in it to conform pattern 2574 restrictions. Such case can occur if the same predicate is used both 2575 for phi node conversion and load/store mask. */ 2576 2577static void 2578ifcvt_repair_bool_pattern (basic_block bb) 2579{ 2580 tree rhs; 2581 gimple stmt; 2582 gimple_stmt_iterator gsi; 2583 vec<gimple> defuse_list = vNULL; 2584 vec<gimple> pattern_roots = vNULL; 2585 bool repeat = true; 2586 int niter = 0; 2587 unsigned int ix; 2588 2589 /* Collect all root pattern statements. */ 2590 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 2591 { 2592 stmt = gsi_stmt (gsi); 2593 if (gimple_code (stmt) != GIMPLE_ASSIGN) 2594 continue; 2595 if (!stmt_is_root_of_bool_pattern (stmt)) 2596 continue; 2597 pattern_roots.safe_push (stmt); 2598 } 2599 2600 if (pattern_roots.is_empty ()) 2601 return; 2602 2603 /* Split all statements with multiple uses iteratively since splitting 2604 may create new multiple uses. */ 2605 while (repeat) 2606 { 2607 repeat = false; 2608 niter++; 2609 FOR_EACH_VEC_ELT (pattern_roots, ix, stmt) 2610 { 2611 rhs = gimple_assign_rhs1 (stmt); 2612 ifcvt_walk_pattern_tree (rhs, &defuse_list, stmt); 2613 while (defuse_list.length () > 0) 2614 { 2615 repeat = true; 2616 gimple def_stmt, use_stmt; 2617 use_stmt = defuse_list.pop (); 2618 def_stmt = defuse_list.pop (); 2619 ifcvt_split_def_stmt (def_stmt, use_stmt); 2620 } 2621 2622 } 2623 } 2624 if (dump_file && (dump_flags & TDF_DETAILS)) 2625 fprintf (dump_file, "Repair bool pattern takes %d iterations. \n", 2626 niter); 2627} 2628 2629/* Delete redundant statements produced by predication which prevents 2630 loop vectorization. */ 2631 2632static void 2633ifcvt_local_dce (basic_block bb) 2634{ 2635 gimple stmt; 2636 gimple stmt1; 2637 gimple phi; 2638 gimple_stmt_iterator gsi; 2639 vec<gimple> worklist; 2640 enum gimple_code code; 2641 use_operand_p use_p; 2642 imm_use_iterator imm_iter; 2643 2644 worklist.create (64); 2645 /* Consider all phi as live statements. */ 2646 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 2647 { 2648 phi = gsi_stmt (gsi); 2649 gimple_set_plf (phi, GF_PLF_2, true); 2650 worklist.safe_push (phi); 2651 } 2652 /* Consider load/store statemnts, CALL and COND as live. */ 2653 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 2654 { 2655 stmt = gsi_stmt (gsi); 2656 if (gimple_store_p (stmt) 2657 || gimple_assign_load_p (stmt) 2658 || is_gimple_debug (stmt)) 2659 { 2660 gimple_set_plf (stmt, GF_PLF_2, true); 2661 worklist.safe_push (stmt); 2662 continue; 2663 } 2664 code = gimple_code (stmt); 2665 if (code == GIMPLE_COND || code == GIMPLE_CALL) 2666 { 2667 gimple_set_plf (stmt, GF_PLF_2, true); 2668 worklist.safe_push (stmt); 2669 continue; 2670 } 2671 gimple_set_plf (stmt, GF_PLF_2, false); 2672 2673 if (code == GIMPLE_ASSIGN) 2674 { 2675 tree lhs = gimple_assign_lhs (stmt); 2676 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, lhs) 2677 { 2678 stmt1 = USE_STMT (use_p); 2679 if (gimple_bb (stmt1) != bb) 2680 { 2681 gimple_set_plf (stmt, GF_PLF_2, true); 2682 worklist.safe_push (stmt); 2683 break; 2684 } 2685 } 2686 } 2687 } 2688 /* Propagate liveness through arguments of live stmt. */ 2689 while (worklist.length () > 0) 2690 { 2691 ssa_op_iter iter; 2692 use_operand_p use_p; 2693 tree use; 2694 2695 stmt = worklist.pop (); 2696 FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE) 2697 { 2698 use = USE_FROM_PTR (use_p); 2699 if (TREE_CODE (use) != SSA_NAME) 2700 continue; 2701 stmt1 = SSA_NAME_DEF_STMT (use); 2702 if (gimple_bb (stmt1) != bb 2703 || gimple_plf (stmt1, GF_PLF_2)) 2704 continue; 2705 gimple_set_plf (stmt1, GF_PLF_2, true); 2706 worklist.safe_push (stmt1); 2707 } 2708 } 2709 /* Delete dead statements. */ 2710 gsi = gsi_start_bb (bb); 2711 while (!gsi_end_p (gsi)) 2712 { 2713 stmt = gsi_stmt (gsi); 2714 if (gimple_plf (stmt, GF_PLF_2)) 2715 { 2716 gsi_next (&gsi); 2717 continue; 2718 } 2719 if (dump_file && (dump_flags & TDF_DETAILS)) 2720 { 2721 fprintf (dump_file, "Delete dead stmt in bb#%d\n", bb->index); 2722 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 2723 } 2724 gsi_remove (&gsi, true); 2725 release_defs (stmt); 2726 } 2727} 2728 2729/* If-convert LOOP when it is legal. For the moment this pass has no 2730 profitability analysis. Returns non-zero todo flags when something 2731 changed. */ 2732 2733static unsigned int 2734tree_if_conversion (struct loop *loop) 2735{ 2736 unsigned int todo = 0; 2737 ifc_bbs = NULL; 2738 bool any_mask_load_store = false; 2739 2740 /* Set-up aggressive if-conversion for loops marked with simd pragma. */ 2741 aggressive_if_conv = loop->force_vectorize; 2742 /* Check either outer loop was marked with simd pragma. */ 2743 if (!aggressive_if_conv) 2744 { 2745 struct loop *outer_loop = loop_outer (loop); 2746 if (outer_loop && outer_loop->force_vectorize) 2747 aggressive_if_conv = true; 2748 } 2749 2750 if (aggressive_if_conv) 2751 if (!ifcvt_split_critical_edges (loop)) 2752 goto cleanup; 2753 2754 if (!if_convertible_loop_p (loop, &any_mask_load_store) 2755 || !dbg_cnt (if_conversion_tree)) 2756 goto cleanup; 2757 2758 if (any_mask_load_store 2759 && ((!flag_tree_loop_vectorize && !loop->force_vectorize) 2760 || loop->dont_vectorize)) 2761 goto cleanup; 2762 2763 if (any_mask_load_store && !version_loop_for_if_conversion (loop)) 2764 goto cleanup; 2765 2766 /* Now all statements are if-convertible. Combine all the basic 2767 blocks into one huge basic block doing the if-conversion 2768 on-the-fly. */ 2769 combine_blocks (loop, any_mask_load_store); 2770 2771 /* Delete dead predicate computations and repair tree correspondent 2772 to bool pattern to delete multiple uses of preidcates. */ 2773 if (aggressive_if_conv) 2774 { 2775 ifcvt_local_dce (loop->header); 2776 ifcvt_repair_bool_pattern (loop->header); 2777 } 2778 2779 todo |= TODO_cleanup_cfg; 2780 if (flag_tree_loop_if_convert_stores || any_mask_load_store) 2781 { 2782 mark_virtual_operands_for_renaming (cfun); 2783 todo |= TODO_update_ssa_only_virtuals; 2784 } 2785 2786 cleanup: 2787 if (ifc_bbs) 2788 { 2789 unsigned int i; 2790 2791 for (i = 0; i < loop->num_nodes; i++) 2792 free_bb_predicate (ifc_bbs[i]); 2793 2794 free (ifc_bbs); 2795 ifc_bbs = NULL; 2796 } 2797 free_dominance_info (CDI_POST_DOMINATORS); 2798 2799 return todo; 2800} 2801 2802/* Tree if-conversion pass management. */ 2803 2804namespace { 2805 2806const pass_data pass_data_if_conversion = 2807{ 2808 GIMPLE_PASS, /* type */ 2809 "ifcvt", /* name */ 2810 OPTGROUP_NONE, /* optinfo_flags */ 2811 TV_NONE, /* tv_id */ 2812 ( PROP_cfg | PROP_ssa ), /* properties_required */ 2813 0, /* properties_provided */ 2814 0, /* properties_destroyed */ 2815 0, /* todo_flags_start */ 2816 0, /* todo_flags_finish */ 2817}; 2818 2819class pass_if_conversion : public gimple_opt_pass 2820{ 2821public: 2822 pass_if_conversion (gcc::context *ctxt) 2823 : gimple_opt_pass (pass_data_if_conversion, ctxt) 2824 {} 2825 2826 /* opt_pass methods: */ 2827 virtual bool gate (function *); 2828 virtual unsigned int execute (function *); 2829 2830}; // class pass_if_conversion 2831 2832bool 2833pass_if_conversion::gate (function *fun) 2834{ 2835 return (((flag_tree_loop_vectorize || fun->has_force_vectorize_loops) 2836 && flag_tree_loop_if_convert != 0) 2837 || flag_tree_loop_if_convert == 1 2838 || flag_tree_loop_if_convert_stores == 1); 2839} 2840 2841unsigned int 2842pass_if_conversion::execute (function *fun) 2843{ 2844 struct loop *loop; 2845 unsigned todo = 0; 2846 2847 if (number_of_loops (fun) <= 1) 2848 return 0; 2849 2850 FOR_EACH_LOOP (loop, 0) 2851 if (flag_tree_loop_if_convert == 1 2852 || flag_tree_loop_if_convert_stores == 1 2853 || ((flag_tree_loop_vectorize || loop->force_vectorize) 2854 && !loop->dont_vectorize)) 2855 todo |= tree_if_conversion (loop); 2856 2857#ifdef ENABLE_CHECKING 2858 { 2859 basic_block bb; 2860 FOR_EACH_BB_FN (bb, fun) 2861 gcc_assert (!bb->aux); 2862 } 2863#endif 2864 2865 return todo; 2866} 2867 2868} // anon namespace 2869 2870gimple_opt_pass * 2871make_pass_if_conversion (gcc::context *ctxt) 2872{ 2873 return new pass_if_conversion (ctxt); 2874} 2875