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