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