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