gcc/tree-if-conv.c

   1 /* If-conversion for vectorizer.
   2    Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010
   3    Free Software Foundation, Inc.
   4    Contributed by Devang Patel <dpatel@apple.com>
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 3, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22 /* This pass implements a tree level if-conversion of loops.  Its
  23    initial goal is to help the vectorizer to vectorize loops with
  24    conditions.
  25
  26    A short description of if-conversion:
  27
  28      o Decide if a loop is if-convertible or not.
  29      o Walk all loop basic blocks in breadth first order (BFS order).
  30        o Remove conditional statements (at the end of basic block)
  31          and propagate condition into destination basic blocks'
  32          predicate list.
  33        o Replace modify expression with conditional modify expression
  34          using current basic block's condition.
  35      o Merge all basic blocks
  36        o Replace phi nodes with conditional modify expr
  37        o Merge all basic blocks into header
  38
  39      Sample transformation:
  40
  41      INPUT
  42      -----
  43
  44      # i_23 = PHI <0(0), i_18(10)>;
  45      <L0>:;
  46      j_15 = A[i_23];
  47      if (j_15 > 41) goto <L1>; else goto <L17>;
  48
  49      <L17>:;
  50      goto <bb 3> (<L3>);
  51
  52      <L1>:;
  53
  54      # iftmp.2_4 = PHI <0(8), 42(2)>;
  55      <L3>:;
  56      A[i_23] = iftmp.2_4;
  57      i_18 = i_23 + 1;
  58      if (i_18 <= 15) goto <L19>; else goto <L18>;
  59
  60      <L19>:;
  61      goto <bb 1> (<L0>);
  62
  63      <L18>:;
  64
  65      OUTPUT
  66      ------
  67
  68      # i_23 = PHI <0(0), i_18(10)>;
  69      <L0>:;
  70      j_15 = A[i_23];
  71
  72      <L3>:;
  73      iftmp.2_4 = j_15 > 41 ? 42 : 0;
  74      A[i_23] = iftmp.2_4;
  75      i_18 = i_23 + 1;
  76      if (i_18 <= 15) goto <L19>; else goto <L18>;
  77
  78      <L19>:;
  79      goto <bb 1> (<L0>);
  80
  81      <L18>:;
  82 */
  83
  84 #include "config.h"
  85 #include "system.h"
  86 #include "coretypes.h"
  87 #include "tm.h"
  88 #include "tree.h"
  89 #include "flags.h"
  90 #include "timevar.h"
  91 #include "basic-block.h"
  92 #include "diagnostic.h"
  93 #include "tree-pretty-print.h"
  94 #include "gimple-pretty-print.h"
  95 #include "tree-flow.h"
  96 #include "tree-dump.h"
  97 #include "cfgloop.h"
  98 #include "tree-chrec.h"
  99 #include "tree-data-ref.h"
 100 #include "tree-scalar-evolution.h"
 101 #include "tree-pass.h"
 102
 103 /* List of basic blocks in if-conversion-suitable order.  */
 104 static basic_block *ifc_bbs;
 105
 106 /* Create a new temp variable of type TYPE.  Add GIMPLE_ASSIGN to assign EXP
 107    to the new variable.  */
 108
 109 static gimple
 110 ifc_temp_var (tree type, tree exp)
 111 {
 112   const char *name = "_ifc_";
 113   tree var, new_name;
 114   gimple stmt;
 115
 116   /* Create new temporary variable.  */
 117   var = create_tmp_var (type, name);
 118   add_referenced_var (var);
 119
 120   /* Build new statement to assign EXP to new variable.  */
 121   stmt = gimple_build_assign (var, exp);
 122
 123   /* Get SSA name for the new variable and set make new statement
 124      its definition statement.  */
 125   new_name = make_ssa_name (var, stmt);
 126   gimple_assign_set_lhs (stmt, new_name);
 127   SSA_NAME_DEF_STMT (new_name) = stmt;
 128   update_stmt (stmt);
 129
 130   return stmt;
 131 }
 132
 133 /* Add condition NEW_COND to the predicate list of basic block BB.  */
 134
 135 static void
 136 add_to_predicate_list (basic_block bb, tree new_cond)
 137 {
 138   tree cond = (tree) bb->aux;
 139
 140   if (cond)
 141     cond = fold_build2_loc (EXPR_LOCATION (cond),
 142                             TRUTH_OR_EXPR, boolean_type_node,
 143                             unshare_expr (cond), new_cond);
 144   else
 145     cond = new_cond;
 146
 147   bb->aux = cond;
 148 }
 149
 150 /* Add the condition COND to the previous condition PREV_COND, and add
 151    this to the predicate list of the destination of edge E.  LOOP is
 152    the loop to be if-converted.  */
 153
 154 static tree
 155 add_to_dst_predicate_list (struct loop *loop, edge e,
 156                            tree prev_cond, tree cond)
 157 {
 158   tree new_cond = NULL_TREE;
 159
 160   if (!flow_bb_inside_loop_p (loop, e->dest))
 161     return NULL_TREE;
 162
 163   if (prev_cond == boolean_true_node || !prev_cond)
 164     new_cond = unshare_expr (cond);
 165   else
 166     new_cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
 167                             unshare_expr (prev_cond), cond);
 168
 169   add_to_predicate_list (e->dest, new_cond);
 170   return new_cond;
 171 }
 172
 173 /* Return true if one of the successor edges of BB exits LOOP.  */
 174
 175 static bool
 176 bb_with_exit_edge_p (struct loop *loop, basic_block bb)
 177 {
 178   edge e;
 179   edge_iterator ei;
 180
 181   FOR_EACH_EDGE (e, ei, bb->succs)
 182     if (loop_exit_edge_p (loop, e))
 183       return true;
 184
 185   return false;
 186 }
 187
 188 /* Return true when PHI is if-convertible.  PHI is part of loop LOOP
 189    and it belongs to basic block BB.
 190
 191    PHI is not if-convertible if:
 192    - it has more than 2 arguments,
 193    - virtual PHI is immediately used in another PHI node,
 194    - virtual PHI on BB other than header.  */
 195
 196 static bool
 197 if_convertible_phi_p (struct loop *loop, basic_block bb, gimple phi)
 198 {
 199   if (dump_file && (dump_flags & TDF_DETAILS))
 200     {
 201       fprintf (dump_file, "-------------------------\n");
 202       print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
 203     }
 204
 205   if (bb != loop->header && gimple_phi_num_args (phi) != 2)
 206     {
 207       if (dump_file && (dump_flags & TDF_DETAILS))
 208         fprintf (dump_file, "More than two phi node args.\n");
 209       return false;
 210     }
 211
 212   if (!is_gimple_reg (SSA_NAME_VAR (gimple_phi_result (phi))))
 213     {
 214       imm_use_iterator imm_iter;
 215       use_operand_p use_p;
 216
 217       if (bb != loop->header)
 218         {
 219           if (dump_file && (dump_flags & TDF_DETAILS))
 220             fprintf (dump_file, "Virtual phi not on loop header.\n");
 221           return false;
 222         }
 223       FOR_EACH_IMM_USE_FAST (use_p, imm_iter, gimple_phi_result (phi))
 224         {
 225           if (gimple_code (USE_STMT (use_p)) == GIMPLE_PHI)
 226             {
 227               if (dump_file && (dump_flags & TDF_DETAILS))
 228                 fprintf (dump_file, "Difficult to handle this virtual phi.\n");
 229               return false;
 230             }
 231         }
 232     }
 233
 234   return true;
 235 }
 236
 237 /* Return true when STMT is if-convertible.
 238
 239    GIMPLE_ASSIGN statement is not if-convertible if,
 240    - it is not movable,
 241    - it could trap,
 242    - LHS is not var decl.
 243
 244    GIMPLE_ASSIGN is part of block BB, which is inside loop LOOP.  */
 245
 246 static bool
 247 if_convertible_gimple_assign_stmt_p (struct loop *loop, basic_block bb,
 248                                      gimple stmt)
 249 {
 250   tree lhs = gimple_assign_lhs (stmt);
 251
 252   if (dump_file && (dump_flags & TDF_DETAILS))
 253     {
 254       fprintf (dump_file, "-------------------------\n");
 255       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
 256     }
 257
 258   /* Some of these constrains might be too conservative.  */
 259   if (stmt_ends_bb_p (stmt)
 260       || gimple_has_volatile_ops (stmt)
 261       || (TREE_CODE (lhs) == SSA_NAME
 262           && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
 263       || gimple_has_side_effects (stmt))
 264     {
 265       if (dump_file && (dump_flags & TDF_DETAILS))
 266         fprintf (dump_file, "stmt not suitable for ifcvt\n");
 267       return false;
 268     }
 269
 270   if (gimple_assign_rhs_could_trap_p (stmt))
 271     {
 272       if (dump_file && (dump_flags & TDF_DETAILS))
 273         fprintf (dump_file, "tree could trap...\n");
 274       return false;
 275     }
 276
 277   if (TREE_CODE (lhs) != SSA_NAME
 278       && bb != loop->header
 279       && !bb_with_exit_edge_p (loop, bb))
 280     {
 281       if (dump_file && (dump_flags & TDF_DETAILS))
 282         {
 283           fprintf (dump_file, "LHS is not var\n");
 284           print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
 285         }
 286       return false;
 287     }
 288
 289   return true;
 290 }
 291
 292 /* Return true when STMT is if-convertible.
 293
 294    A statement is if-convertible if:
 295    - it is an if-convertible GIMPLE_ASSGIN,
 296    - it is a GIMPLE_LABEL or a GIMPLE_COND.
 297
 298    STMT is inside BB, which is inside loop LOOP.  */
 299
 300 static bool
 301 if_convertible_stmt_p (struct loop *loop, basic_block bb, gimple stmt)
 302 {
 303   switch (gimple_code (stmt))
 304     {
 305     case GIMPLE_LABEL:
 306     case GIMPLE_DEBUG:
 307     case GIMPLE_COND:
 308       return true;
 309
 310     case GIMPLE_ASSIGN:
 311       return if_convertible_gimple_assign_stmt_p (loop, bb, stmt);
 312
 313     default:
 314       /* Don't know what to do with 'em so don't do anything.  */
 315       if (dump_file && (dump_flags & TDF_DETAILS))
 316         {
 317           fprintf (dump_file, "don't know what to do\n");
 318           print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
 319         }
 320       return false;
 321       break;
 322     }
 323
 324   return true;
 325 }
 326
 327 /* Return true when BB is if-convertible.  This routine does not check
 328    basic block's statements and phis.
 329
 330    A basic block is not if-convertible if:
 331    - it is non-empty and it is after the exit block (in BFS order),
 332    - it is after the exit block but before the latch,
 333    - its edges are not normal.
 334
 335    EXIT_BB is the basic block containing the exit of the LOOP.  BB is
 336    inside LOOP.  */
 337
 338 static bool
 339 if_convertible_bb_p (struct loop *loop, basic_block bb, basic_block exit_bb)
 340 {
 341   edge e;
 342   edge_iterator ei;
 343
 344   if (dump_file && (dump_flags & TDF_DETAILS))
 345     fprintf (dump_file, "----------[%d]-------------\n", bb->index);
 346
 347   if (EDGE_COUNT (bb->preds) > 2
 348       || EDGE_COUNT (bb->succs) > 2)
 349     return false;
 350
 351   if (exit_bb)
 352     {
 353       if (bb != loop->latch)
 354         {
 355           if (dump_file && (dump_flags & TDF_DETAILS))
 356             fprintf (dump_file, "basic block after exit bb but before latch\n");
 357           return false;
 358         }
 359       else if (!empty_block_p (bb))
 360         {
 361           if (dump_file && (dump_flags & TDF_DETAILS))
 362             fprintf (dump_file, "non empty basic block after exit bb\n");
 363           return false;
 364         }
 365       else if (bb == loop->latch
 366                && bb != exit_bb
 367                && !dominated_by_p (CDI_DOMINATORS, bb, exit_bb))
 368           {
 369             if (dump_file && (dump_flags & TDF_DETAILS))
 370               fprintf (dump_file, "latch is not dominated by exit_block\n");
 371             return false;
 372           }
 373     }
 374
 375   /* Be less adventurous and handle only normal edges.  */
 376   FOR_EACH_EDGE (e, ei, bb->succs)
 377     if (e->flags &
 378         (EDGE_ABNORMAL_CALL | EDGE_EH | EDGE_ABNORMAL | EDGE_IRREDUCIBLE_LOOP))
 379       {
 380         if (dump_file && (dump_flags & TDF_DETAILS))
 381           fprintf (dump_file, "Difficult to handle edges\n");
 382         return false;
 383       }
 384
 385   return true;
 386 }
 387
 388 /* Return true when all predecessor blocks of BB are visited.  The
 389    VISITED bitmap keeps track of the visited blocks.  */
 390
 391 static bool
 392 pred_blocks_visited_p (basic_block bb, bitmap *visited)
 393 {
 394   edge e;
 395   edge_iterator ei;
 396   FOR_EACH_EDGE (e, ei, bb->preds)
 397     if (!bitmap_bit_p (*visited, e->src->index))
 398       return false;
 399
 400   return true;
 401 }
 402
 403 /* Get body of a LOOP in suitable order for if-conversion.  It is
 404    caller's responsibility to deallocate basic block list.
 405    If-conversion suitable order is, breadth first sort (BFS) order
 406    with an additional constraint: select a block only if all its
 407    predecessors are already selected.  */
 408
 409 static basic_block *
 410 get_loop_body_in_if_conv_order (const struct loop *loop)
 411 {
 412   basic_block *blocks, *blocks_in_bfs_order;
 413   basic_block bb;
 414   bitmap visited;
 415   unsigned int index = 0;
 416   unsigned int visited_count = 0;
 417
 418   gcc_assert (loop->num_nodes);
 419   gcc_assert (loop->latch != EXIT_BLOCK_PTR);
 420
 421   blocks = XCNEWVEC (basic_block, loop->num_nodes);
 422   visited = BITMAP_ALLOC (NULL);
 423
 424   blocks_in_bfs_order = get_loop_body_in_bfs_order (loop);
 425
 426   index = 0;
 427   while (index < loop->num_nodes)
 428     {
 429       bb = blocks_in_bfs_order [index];
 430
 431       if (bb->flags & BB_IRREDUCIBLE_LOOP)
 432         {
 433           free (blocks_in_bfs_order);
 434           BITMAP_FREE (visited);
 435           free (blocks);
 436           return NULL;
 437         }
 438
 439       if (!bitmap_bit_p (visited, bb->index))
 440         {
 441           if (pred_blocks_visited_p (bb, &visited)
 442               || bb == loop->header)
 443             {
 444               /* This block is now visited.  */
 445               bitmap_set_bit (visited, bb->index);
 446               blocks[visited_count++] = bb;
 447             }
 448         }
 449
 450       index++;
 451
 452       if (index == loop->num_nodes
 453           && visited_count != loop->num_nodes)
 454         /* Not done yet.  */
 455         index = 0;
 456     }
 457   free (blocks_in_bfs_order);
 458   BITMAP_FREE (visited);
 459   return blocks;
 460 }
 461
 462 /* Returns true when the analysis of the predicates for all the basic
 463    blocks in LOOP succeeded.
 464
 465    predicate_bbs first clears the ->aux fields of the basic blocks.
 466    These fields are then initialized with the tree expressions
 467    representing the predicates under which a basic block is executed
 468    in the LOOP.  As the loop->header is executed at each iteration, it
 469    has the "true" predicate.  Other statements executed under a
 470    condition are predicated with that condition, for example
 471
 472    | if (x)
 473    |   S1;
 474    | else
 475    |   S2;
 476
 477    S1 will be predicated with "x", and S2 will be predicated with
 478    "!x".  */
 479
 480 static bool
 481 predicate_bbs (loop_p loop)
 482 {
 483   unsigned int i;
 484
 485   for (i = 0; i < loop->num_nodes; i++)
 486     ifc_bbs[i]->aux = NULL;
 487
 488   for (i = 0; i < loop->num_nodes; i++)
 489     {
 490       basic_block bb = ifc_bbs [i];
 491       tree cond = (tree) bb->aux;
 492       gimple_stmt_iterator itr;
 493
 494       for (itr = gsi_start_bb (bb); !gsi_end_p (itr); gsi_next (&itr))
 495         {
 496           gimple stmt = gsi_stmt (itr);
 497
 498           switch (gimple_code (stmt))
 499             {
 500             case GIMPLE_LABEL:
 501             case GIMPLE_ASSIGN:
 502             case GIMPLE_CALL:
 503               break;
 504
 505             case GIMPLE_DEBUG:
 506               /* ??? Should there be conditional GIMPLE_DEBUG_BINDs?  */
 507               if (gimple_debug_bind_p (gsi_stmt (itr)))
 508                 {
 509                   gimple_debug_bind_reset_value (gsi_stmt (itr));
 510                   update_stmt (gsi_stmt (itr));
 511                 }
 512               break;
 513
 514             case GIMPLE_COND:
 515               {
 516                 tree c2;
 517                 edge true_edge, false_edge;
 518                 location_t loc = gimple_location (stmt);
 519                 tree c = fold_build2_loc (loc, gimple_cond_code (stmt),
 520                                           boolean_type_node,
 521                                           gimple_cond_lhs (stmt),
 522                                           gimple_cond_rhs (stmt));
 523
 524                 extract_true_false_edges_from_block (gimple_bb (stmt),
 525                                                      &true_edge, &false_edge);
 526
 527                 /* Add new condition into destination's predicate list.  */
 528
 529                 /* If C is true, then TRUE_EDGE is taken.  */
 530                 add_to_dst_predicate_list (loop, true_edge, cond, c);
 531
 532                 /* If C is false, then FALSE_EDGE is taken.  */
 533                 c2 = invert_truthvalue_loc (loc, unshare_expr (c));
 534                 add_to_dst_predicate_list (loop, false_edge, cond, c2);
 535
 536                 cond = NULL_TREE;
 537                 break;
 538               }
 539
 540             case GIMPLE_SWITCH:
 541               /* Not handled yet in if-conversion.  */
 542               return false;
 543
 544             default:
 545               gcc_unreachable ();
 546             }
 547         }
 548
 549       /* If current bb has only one successor, then consider it as an
 550          unconditional goto.  */
 551       if (single_succ_p (bb))
 552         {
 553           basic_block bb_n = single_succ (bb);
 554
 555           /* The successor bb inherits the predicate of its
 556              predecessor.  If there is no predicate in the predecessor
 557              bb, then consider the successor bb as always executed.  */
 558           if (cond == NULL_TREE)
 559             cond = boolean_true_node;
 560
 561           add_to_predicate_list (bb_n, cond);
 562         }
 563     }
 564
 565   /* The loop header is always executed.  */
 566   loop->header->aux = boolean_true_node;
 567
 568   return true;
 569 }
 570
 571 /* Returns true when BB has a predicate that is not trivial: true or
 572    NULL_TREE.  */
 573
 574 static bool
 575 is_predicated (basic_block bb)
 576 {
 577   tree cond = (tree) bb->aux;
 578
 579   return (cond != NULL_TREE
 580           && cond != boolean_true_node
 581           && !integer_onep (cond));
 582 }
 583
 584 /* Return true when LOOP is if-convertible.
 585    LOOP is if-convertible if:
 586    - it is innermost,
 587    - it has two or more basic blocks,
 588    - it has only one exit,
 589    - loop header is not the exit edge,
 590    - if its basic blocks and phi nodes are if convertible.  */
 591
 592 static bool
 593 if_convertible_loop_p (struct loop *loop)
 594 {
 595   unsigned int i;
 596   edge e;
 597   edge_iterator ei;
 598   basic_block exit_bb = NULL;
 599
 600   /* Handle only innermost loop.  */
 601   if (!loop || loop->inner)
 602     {
 603       if (dump_file && (dump_flags & TDF_DETAILS))
 604         fprintf (dump_file, "not innermost loop\n");
 605       return false;
 606     }
 607
 608   /* If only one block, no need for if-conversion.  */
 609   if (loop->num_nodes <= 2)
 610     {
 611       if (dump_file && (dump_flags & TDF_DETAILS))
 612         fprintf (dump_file, "less than 2 basic blocks\n");
 613       return false;
 614     }
 615
 616   /* More than one loop exit is too much to handle.  */
 617   if (!single_exit (loop))
 618     {
 619       if (dump_file && (dump_flags & TDF_DETAILS))
 620         fprintf (dump_file, "multiple exits\n");
 621       return false;
 622     }
 623
 624   /* ??? Check target's vector conditional operation support for vectorizer.  */
 625
 626   /* If one of the loop header's edge is exit edge then do not apply
 627      if-conversion.  */
 628   FOR_EACH_EDGE (e, ei, loop->header->succs)
 629     {
 630       if (loop_exit_edge_p (loop, e))
 631         return false;
 632     }
 633
 634   /* Don't if-convert the loop when the data dependences cannot be
 635      computed: the loop won't be vectorized in that case.  */
 636   {
 637     VEC (data_reference_p, heap) *refs = VEC_alloc (data_reference_p, heap, 5);
 638     VEC (ddr_p, heap) *ddrs = VEC_alloc (ddr_p, heap, 25);
 639     bool res = compute_data_dependences_for_loop (loop, true, &refs, &ddrs);
 640
 641     free_data_refs (refs);
 642     free_dependence_relations (ddrs);
 643
 644     if (!res)
 645       return false;
 646   }
 647
 648   calculate_dominance_info (CDI_DOMINATORS);
 649
 650   /* Allow statements that can be handled during if-conversion.  */
 651   ifc_bbs = get_loop_body_in_if_conv_order (loop);
 652   if (!ifc_bbs)
 653     {
 654       if (dump_file && (dump_flags & TDF_DETAILS))
 655         fprintf (dump_file, "Irreducible loop\n");
 656       return false;
 657     }
 658
 659   for (i = 0; i < loop->num_nodes; i++)
 660     {
 661       basic_block bb = ifc_bbs[i];
 662
 663       if (!if_convertible_bb_p (loop, bb, exit_bb))
 664         return false;
 665
 666       if (bb_with_exit_edge_p (loop, bb))
 667         exit_bb = bb;
 668     }
 669
 670   if (!predicate_bbs (loop))
 671     return false;
 672
 673   for (i = 0; i < loop->num_nodes; i++)
 674     {
 675       basic_block bb = ifc_bbs[i];
 676       gimple_stmt_iterator itr;
 677
 678       for (itr = gsi_start_phis (bb); !gsi_end_p (itr); gsi_next (&itr))
 679         if (!if_convertible_phi_p (loop, bb, gsi_stmt (itr)))
 680           return false;
 681
 682       /* For non predicated BBs, don't check their statements.  */
 683       if (!is_predicated (bb))
 684         continue;
 685
 686       for (itr = gsi_start_bb (bb); !gsi_end_p (itr); gsi_next (&itr))
 687         if (!if_convertible_stmt_p (loop, bb, gsi_stmt (itr)))
 688           return false;
 689     }
 690
 691   if (dump_file)
 692     fprintf (dump_file, "Applying if-conversion\n");
 693
 694   return true;
 695 }
 696
 697 /* During if-conversion, the bb->aux field is used to hold a predicate
 698    list.  This function cleans for all the basic blocks in the given
 699    LOOP their predicate list.  */
 700
 701 static void
 702 clean_predicate_lists (struct loop *loop)
 703 {
 704   unsigned int i;
 705   basic_block *bbs = get_loop_body (loop);
 706
 707   for (i = 0; i < loop->num_nodes; i++)
 708     bbs[i]->aux = NULL;
 709
 710   free (bbs);
 711 }
 712
 713 /* Basic block BB has two predecessors.  Using predecessor's bb->aux
 714    field, set appropriate condition COND for the PHI node replacement.
 715    Return true block whose phi arguments are selected when cond is
 716    true.  LOOP is the loop containing the if-converted region, GSI is
 717    the place to insert the code for the if-conversion.  */
 718
 719 static basic_block
 720 find_phi_replacement_condition (struct loop *loop,
 721                                 basic_block bb, tree *cond,
 722                                 gimple_stmt_iterator *gsi)
 723 {
 724   edge first_edge, second_edge;
 725   tree tmp_cond;
 726
 727   gcc_assert (EDGE_COUNT (bb->preds) == 2);
 728   first_edge = EDGE_PRED (bb, 0);
 729   second_edge = EDGE_PRED (bb, 1);
 730
 731   /* Use condition based on following criteria:
 732      1)
 733        S1: x = !c ? a : b;
 734
 735        S2: x = c ? b : a;
 736
 737        S2 is preferred over S1. Make 'b' first_bb and use its condition.
 738
 739      2) Do not make loop header first_bb.
 740
 741      3)
 742        S1: x = !(c == d)? a : b;
 743
 744        S21: t1 = c == d;
 745        S22: x = t1 ? b : a;
 746
 747        S3: x = (c == d) ? b : a;
 748
 749        S3 is preferred over S1 and S2*, Make 'b' first_bb and use
 750        its condition.
 751
 752      4) If  pred B is dominated by pred A then use pred B's condition.
 753         See PR23115.  */
 754
 755   /* Select condition that is not TRUTH_NOT_EXPR.  */
 756   tmp_cond = (tree) (first_edge->src)->aux;
 757   gcc_assert (tmp_cond);
 758
 759   if (TREE_CODE (tmp_cond) == TRUTH_NOT_EXPR)
 760     {
 761       edge tmp_edge;
 762
 763       tmp_edge = first_edge;
 764       first_edge = second_edge;
 765       second_edge = tmp_edge;
 766     }
 767
 768   /* Check if FIRST_BB is loop header or not and make sure that
 769      FIRST_BB does not dominate SECOND_BB.  */
 770   if (first_edge->src == loop->header
 771       || dominated_by_p (CDI_DOMINATORS,
 772                          second_edge->src, first_edge->src))
 773     {
 774       *cond = (tree) (second_edge->src)->aux;
 775
 776       if (TREE_CODE (*cond) == TRUTH_NOT_EXPR)
 777         *cond = invert_truthvalue (*cond);
 778       else
 779         /* Select non loop header bb.  */
 780         first_edge = second_edge;
 781     }
 782   else
 783     *cond = (tree) (first_edge->src)->aux;
 784
 785   /* Gimplify the condition: the vectorizer prefers to have gimple
 786      values as conditions.  Various targets use different means to
 787      communicate conditions in vector compare operations.  Using a
 788      gimple value allows the compiler to emit vector compare and
 789      select RTL without exposing compare's result.  */
 790   *cond = force_gimple_operand_gsi (gsi, unshare_expr (*cond),
 791                                     false, NULL_TREE,
 792                                     true, GSI_SAME_STMT);
 793   if (!is_gimple_reg (*cond) && !is_gimple_condexpr (*cond))
 794     {
 795       gimple new_stmt;
 796
 797       new_stmt = ifc_temp_var (TREE_TYPE (*cond), unshare_expr (*cond));
 798       gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
 799       *cond = gimple_assign_lhs (new_stmt);
 800     }
 801
 802   gcc_assert (*cond);
 803
 804   return first_edge->src;
 805 }
 806
 807 /* Replace PHI node with conditional modify expr using COND.  This
 808    routine does not handle PHI nodes with more than two arguments.
 809
 810    For example,
 811      S1: A = PHI <x1(1), x2(5)
 812    is converted into,
 813      S2: A = cond ? x1 : x2;
 814
 815    The generated code is inserted at GSI that points to the top of
 816    basic block's statement list.  When COND is true, phi arg from
 817    TRUE_BB is selected.  */
 818
 819 static void
 820 replace_phi_with_cond_gimple_assign_stmt (gimple phi, tree cond,
 821                                           basic_block true_bb,
 822                                           gimple_stmt_iterator *gsi)
 823 {
 824   gimple new_stmt;
 825   basic_block bb;
 826   tree rhs;
 827   tree arg;
 828
 829   gcc_assert (gimple_code (phi) == GIMPLE_PHI
 830               && gimple_phi_num_args (phi) == 2);
 831
 832   bb = gimple_bb (phi);
 833
 834   arg = degenerate_phi_result (phi);
 835   if (arg)
 836     rhs = arg;
 837   else
 838     {
 839       tree arg_0, arg_1;
 840       /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr.  */
 841       if (EDGE_PRED (bb, 1)->src == true_bb)
 842         {
 843           arg_0 = gimple_phi_arg_def (phi, 1);
 844           arg_1 = gimple_phi_arg_def (phi, 0);
 845         }
 846       else
 847         {
 848           arg_0 = gimple_phi_arg_def (phi, 0);
 849           arg_1 = gimple_phi_arg_def (phi, 1);
 850         }
 851
 852       /* Build new RHS using selected condition and arguments.  */
 853       rhs = build3 (COND_EXPR, TREE_TYPE (PHI_RESULT (phi)),
 854                     unshare_expr (cond), arg_0, arg_1);
 855     }
 856
 857   new_stmt = gimple_build_assign (PHI_RESULT (phi), rhs);
 858   SSA_NAME_DEF_STMT (gimple_phi_result (phi)) = new_stmt;
 859   gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
 860   update_stmt (new_stmt);
 861
 862   if (dump_file && (dump_flags & TDF_DETAILS))
 863     {
 864       fprintf (dump_file, "new phi replacement stmt\n");
 865       print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM);
 866     }
 867 }
 868
 869 /* Process phi nodes for the given LOOP.  Replace phi nodes with
 870    conditional modify expressions.  */
 871
 872 static void
 873 process_phi_nodes (struct loop *loop)
 874 {
 875   basic_block bb;
 876   unsigned int orig_loop_num_nodes = loop->num_nodes;
 877   unsigned int i;
 878
 879   for (i = 1; i < orig_loop_num_nodes; i++)
 880     {
 881       gimple phi;
 882       tree cond = NULL_TREE;
 883       gimple_stmt_iterator gsi, phi_gsi;
 884       basic_block true_bb = NULL;
 885       bb = ifc_bbs[i];
 886
 887       if (bb == loop->header)
 888         continue;
 889
 890       phi_gsi = gsi_start_phis (bb);
 891       gsi = gsi_after_labels (bb);
 892
 893       /* BB has two predecessors.  Using predecessor's aux field, set
 894          appropriate condition for the PHI node replacement.  */
 895       if (!gsi_end_p (phi_gsi))
 896         true_bb = find_phi_replacement_condition (loop, bb, &cond, &gsi);
 897
 898       while (!gsi_end_p (phi_gsi))
 899         {
 900           phi = gsi_stmt (phi_gsi);
 901           replace_phi_with_cond_gimple_assign_stmt (phi, cond, true_bb, &gsi);
 902           release_phi_node (phi);
 903           gsi_next (&phi_gsi);
 904         }
 905       set_phi_nodes (bb, NULL);
 906     }
 907 }
 908
 909 /* Remove all GIMPLE_CONDs and GIMPLE_LABELs of all the basic blocks
 910    other than the exit and latch of the LOOP.  */
 911
 912 static void
 913 remove_conditions_and_labels (loop_p loop)
 914 {
 915   gimple_stmt_iterator gsi;
 916   unsigned int i;
 917
 918   for (i = 0; i < loop->num_nodes; i++)
 919     {
 920       basic_block bb = ifc_bbs [i];
 921
 922       if (bb_with_exit_edge_p (loop, bb)
 923         || bb == loop->latch)
 924       continue;
 925
 926       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
 927       if (gimple_code (gsi_stmt (gsi)) == GIMPLE_COND
 928           || gimple_code (gsi_stmt (gsi)) == GIMPLE_LABEL)
 929         gsi_remove (&gsi, true);
 930       else
 931         gsi_next (&gsi);
 932     }
 933 }
 934
 935 /* Combine all the basic blocks from LOOP into one or two super basic
 936    blocks.  Replace PHI nodes with conditional modify expressions.  */
 937
 938 static void
 939 combine_blocks (struct loop *loop)
 940 {
 941   basic_block bb, exit_bb, merge_target_bb;
 942   unsigned int orig_loop_num_nodes = loop->num_nodes;
 943   unsigned int i;
 944   edge e;
 945   edge_iterator ei;
 946
 947   remove_conditions_and_labels (loop);
 948
 949   /* Process phi nodes to prepare blocks for merge.  */
 950   process_phi_nodes (loop);
 951
 952   /* Merge basic blocks: first remove all the edges in the loop,
 953      except for those from the exit block.  */
 954   exit_bb = NULL;
 955   for (i = 0; i < orig_loop_num_nodes; i++)
 956     {
 957       bb = ifc_bbs[i];
 958       if (bb_with_exit_edge_p (loop, bb))
 959         {
 960           exit_bb = bb;
 961           break;
 962         }
 963     }
 964   gcc_assert (exit_bb != loop->latch);
 965
 966   for (i = 1; i < orig_loop_num_nodes; i++)
 967     {
 968       bb = ifc_bbs[i];
 969
 970       for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei));)
 971         {
 972           if (e->src == exit_bb)
 973             ei_next (&ei);
 974           else
 975             remove_edge (e);
 976         }
 977     }
 978
 979   if (exit_bb != NULL)
 980     {
 981       if (exit_bb != loop->header)
 982         {
 983           /* Connect this node to loop header.  */
 984           make_edge (loop->header, exit_bb, EDGE_FALLTHRU);
 985           set_immediate_dominator (CDI_DOMINATORS, exit_bb, loop->header);
 986         }
 987
 988       /* Redirect non-exit edges to loop->latch.  */
 989       FOR_EACH_EDGE (e, ei, exit_bb->succs)
 990         {
 991           if (!loop_exit_edge_p (loop, e))
 992             redirect_edge_and_branch (e, loop->latch);
 993         }
 994       set_immediate_dominator (CDI_DOMINATORS, loop->latch, exit_bb);
 995     }
 996   else
 997     {
 998       /* If the loop does not have an exit, reconnect header and latch.  */
 999       make_edge (loop->header, loop->latch, EDGE_FALLTHRU);
1000       set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header);
1001     }
1002
1003   merge_target_bb = loop->header;
1004   for (i = 1; i < orig_loop_num_nodes; i++)
1005     {
1006       gimple_stmt_iterator gsi;
1007       gimple_stmt_iterator last;
1008
1009       bb = ifc_bbs[i];
1010
1011       if (bb == exit_bb || bb == loop->latch)
1012         continue;
1013
1014       /* Make stmts member of loop->header.  */
1015       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1016         gimple_set_bb (gsi_stmt (gsi), merge_target_bb);
1017
1018       /* Update stmt list.  */
1019       last = gsi_last_bb (merge_target_bb);
1020       gsi_insert_seq_after (&last, bb_seq (bb), GSI_NEW_STMT);
1021       set_bb_seq (bb, NULL);
1022
1023       delete_basic_block (bb);
1024     }
1025
1026   /* If possible, merge loop header to the block with the exit edge.
1027      This reduces the number of basic blocks to two, to please the
1028      vectorizer that handles only loops with two nodes.
1029
1030      FIXME: Call cleanup_tree_cfg.  */
1031   if (exit_bb
1032       && exit_bb != loop->header
1033       && can_merge_blocks_p (loop->header, exit_bb))
1034     merge_blocks (loop->header, exit_bb);
1035 }
1036
1037 /* If-convert LOOP when it is legal.  For the moment this pass has no
1038    profitability analysis.  */
1039
1040 static void
1041 tree_if_conversion (struct loop *loop)
1042 {
1043   ifc_bbs = NULL;
1044
1045   if (!if_convertible_loop_p (loop))
1046     goto cleanup;
1047
1048   /* Now all statements are if-convertible.  Combine all the basic
1049      blocks into one huge basic block doing the if-conversion
1050      on-the-fly.  */
1051   combine_blocks (loop);
1052
1053  cleanup:
1054   clean_predicate_lists (loop);
1055   if (ifc_bbs)
1056     {
1057       free (ifc_bbs);
1058       ifc_bbs = NULL;
1059     }
1060 }
1061
1062 /* Tree if-conversion pass management.  */
1063
1064 static unsigned int
1065 main_tree_if_conversion (void)
1066 {
1067   loop_iterator li;
1068   struct loop *loop;
1069
1070   if (number_of_loops () <= 1)
1071     return 0;
1072
1073   FOR_EACH_LOOP (li, loop, 0)
1074     tree_if_conversion (loop);
1075
1076   return 0;
1077 }
1078
1079 static bool
1080 gate_tree_if_conversion (void)
1081 {
1082   return flag_tree_vectorize != 0;
1083 }
1084
1085 struct gimple_opt_pass pass_if_conversion =
1086 {
1087  {
1088   GIMPLE_PASS,
1089   "ifcvt",                              /* name */
1090   gate_tree_if_conversion,              /* gate */
1091   main_tree_if_conversion,              /* execute */
1092   NULL,                                 /* sub */
1093   NULL,                                 /* next */
1094   0,                                    /* static_pass_number */
1095   TV_NONE,                              /* tv_id */
1096   PROP_cfg | PROP_ssa,                  /* properties_required */
1097   0,                                    /* properties_provided */
1098   0,                                    /* properties_destroyed */
1099   0,                                    /* todo_flags_start */
1100   TODO_dump_func | TODO_verify_stmts | TODO_verify_flow
1101                                         /* todo_flags_finish */
1102  }
1103 };