gcc/tree-if-conv.c

   1 /* If-conversion for vectorizer.
   2    Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009
   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 "rtl.h"
  92 #include "basic-block.h"
  93 #include "diagnostic.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 "target.h"
 102
 103 /* List of basic blocks in if-conversion-suitable order.  */
 104 static basic_block *ifc_bbs;
 105
 106 /* Make 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 into 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 /* And condition COND to the previous condition PREV_COND and add this
 151    to the predicate list of the destination of edge E.  GSI is the
 152    place where the gimplification of the resulting condition should
 153    output code.  LOOP is the loop to be if-converted.  */
 154
 155 static tree
 156 add_to_dst_predicate_list (struct loop *loop, edge e,
 157                            tree prev_cond, tree cond,
 158                            gimple_stmt_iterator *gsi)
 159 {
 160   tree new_cond = NULL_TREE;
 161
 162   if (!flow_bb_inside_loop_p (loop, e->dest))
 163     return NULL_TREE;
 164
 165   if (prev_cond == boolean_true_node || !prev_cond)
 166     new_cond = unshare_expr (cond);
 167   else
 168     {
 169       tree tmp;
 170       gimple tmp_stmt = NULL;
 171
 172       prev_cond = force_gimple_operand_gsi (gsi, unshare_expr (prev_cond),
 173                                             true, NULL, true, GSI_SAME_STMT);
 174
 175       cond = force_gimple_operand_gsi (gsi, unshare_expr (cond),
 176                                        true, NULL, true, GSI_SAME_STMT);
 177
 178       /* Add the condition to aux field of the edge.  In case edge
 179          destination is a PHI node, this condition will be ANDed with
 180          block predicate to construct complete condition.  */
 181       e->aux = cond;
 182
 183       tmp = build2 (TRUTH_AND_EXPR, boolean_type_node,
 184                     unshare_expr (prev_cond), cond);
 185       tmp_stmt = ifc_temp_var (boolean_type_node, tmp);
 186       gsi_insert_before (gsi, tmp_stmt, GSI_SAME_STMT);
 187       new_cond = gimple_assign_lhs (tmp_stmt);
 188     }
 189
 190   add_to_predicate_list (e->dest, new_cond);
 191   return new_cond;
 192 }
 193
 194 /* Return true if one of the basic block BB edge is exit of LOOP.  */
 195
 196 static bool
 197 bb_with_exit_edge_p (struct loop *loop, basic_block bb)
 198 {
 199   edge e;
 200   edge_iterator ei;
 201   bool exit_edge_found = false;
 202
 203   FOR_EACH_EDGE (e, ei, bb->succs)
 204     if (loop_exit_edge_p (loop, e))
 205       {
 206         exit_edge_found = true;
 207         break;
 208       }
 209
 210   return exit_edge_found;
 211 }
 212
 213 /* STMT is a GIMPLE_COND.  Update two destination's predicate list.
 214    Remove COND_EXPR, if it is not the loop exit condition.  Otherwise
 215    update loop exit condition appropriately.  GSI is the iterator
 216    used to traverse statement list.  STMT is part of loop LOOP.  */
 217
 218 static void
 219 tree_if_convert_cond_stmt (struct loop *loop, gimple stmt, tree cond,
 220                            gimple_stmt_iterator *gsi)
 221 {
 222   tree c2;
 223   edge true_edge, false_edge;
 224   location_t loc = gimple_location (stmt);
 225   tree c = fold_build2_loc (loc, gimple_cond_code (stmt), boolean_type_node,
 226                             gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
 227
 228   extract_true_false_edges_from_block (gimple_bb (stmt),
 229                                        &true_edge, &false_edge);
 230
 231   /* Add new condition into destination's predicate list.  */
 232
 233   /* If C is true, then TRUE_EDGE is taken.  */
 234   add_to_dst_predicate_list (loop, true_edge, cond, c, gsi);
 235
 236   /* If C is false, then FALSE_EDGE is taken.  */
 237   c2 = invert_truthvalue_loc (loc, unshare_expr (c));
 238   add_to_dst_predicate_list (loop, false_edge, cond, c2, gsi);
 239
 240   /* Now this conditional statement is redundant.  Remove it.
 241      But, do not remove exit condition!  Update exit condition
 242      using new condition.  */
 243   if (!bb_with_exit_edge_p (loop, gimple_bb (stmt)))
 244     {
 245       gsi_remove (gsi, true);
 246       cond = NULL_TREE;
 247     }
 248   return;
 249 }
 250
 251 /* If-convert stmt T which is part of LOOP.
 252    If T is a GIMPLE_ASSIGN then it is converted into conditional modify
 253    expression using COND.  For conditional expressions, add condition in the
 254    destination basic block's predicate list and remove conditional
 255    expression itself.  BSI is the iterator used to traverse statements of
 256    loop.  It is used here when it is required to delete current statement.  */
 257
 258 static tree
 259 tree_if_convert_stmt (struct loop *loop, gimple t, tree cond,
 260                       gimple_stmt_iterator *gsi)
 261 {
 262   if (dump_file && (dump_flags & TDF_DETAILS))
 263     {
 264       fprintf (dump_file, "------if-convert stmt\n");
 265       print_gimple_stmt (dump_file, t, 0, TDF_SLIM);
 266       print_generic_stmt (dump_file, cond, TDF_SLIM);
 267     }
 268
 269   switch (gimple_code (t))
 270     {
 271       /* Labels are harmless here.  */
 272     case GIMPLE_LABEL:
 273       break;
 274
 275     case GIMPLE_DEBUG:
 276       /* ??? Should there be conditional GIMPLE_DEBUG_BINDs?  */
 277       if (gimple_debug_bind_p (gsi_stmt (*gsi)))
 278         {
 279           gimple_debug_bind_reset_value (gsi_stmt (*gsi));
 280           update_stmt (gsi_stmt (*gsi));
 281         }
 282       break;
 283
 284     case GIMPLE_ASSIGN:
 285       /* This GIMPLE_ASSIGN is killing previous value of LHS.  Appropriate
 286          value will be selected by PHI node based on condition.  It is possible
 287          that before this transformation, PHI nodes was selecting default
 288          value and now it will use this new value.  This is OK because it does
 289          not change the validity of the program.  */
 290       break;
 291
 292     case GIMPLE_COND:
 293       /* Update destination blocks' predicate list and remove this
 294          condition expression.  */
 295       tree_if_convert_cond_stmt (loop, t, cond, gsi);
 296       cond = NULL_TREE;
 297       break;
 298
 299     default:
 300       gcc_unreachable ();
 301     }
 302   return cond;
 303 }
 304
 305 /* Return true, iff PHI is if-convertible.  PHI is part of loop LOOP
 306    and it belongs to basic block BB.
 307    PHI is not if-convertible
 308    - if it has more than 2 arguments,
 309    - virtual PHI is immediately used in another PHI node,
 310    - virtual PHI on BB other than header.  */
 311
 312 static bool
 313 if_convertible_phi_p (struct loop *loop, basic_block bb, gimple phi)
 314 {
 315   if (dump_file && (dump_flags & TDF_DETAILS))
 316     {
 317       fprintf (dump_file, "-------------------------\n");
 318       print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
 319     }
 320
 321   if (bb != loop->header && gimple_phi_num_args (phi) != 2)
 322     {
 323       if (dump_file && (dump_flags & TDF_DETAILS))
 324         fprintf (dump_file, "More than two phi node args.\n");
 325       return false;
 326     }
 327
 328   if (!is_gimple_reg (SSA_NAME_VAR (gimple_phi_result (phi))))
 329     {
 330       imm_use_iterator imm_iter;
 331       use_operand_p use_p;
 332
 333       if (bb != loop->header)
 334         {
 335           if (dump_file && (dump_flags & TDF_DETAILS))
 336             fprintf (dump_file, "Virtual phi not on loop header.\n");
 337           return false;
 338         }
 339       FOR_EACH_IMM_USE_FAST (use_p, imm_iter, gimple_phi_result (phi))
 340         {
 341           if (gimple_code (USE_STMT (use_p)) == GIMPLE_PHI)
 342             {
 343               if (dump_file && (dump_flags & TDF_DETAILS))
 344                 fprintf (dump_file, "Difficult to handle this virtual phi.\n");
 345               return false;
 346             }
 347         }
 348     }
 349
 350   return true;
 351 }
 352
 353 /* Return true when STMT is if-convertible.
 354
 355    GIMPLE_ASSIGN statement is not if-convertible if,
 356    - it is not movable,
 357    - it could trap,
 358    - LHS is not var decl.
 359    GIMPLE_ASSIGN is part of block BB, which is inside loop LOOP.  */
 360
 361 static bool
 362 if_convertible_gimple_assign_stmt_p (struct loop *loop, basic_block bb,
 363                                      gimple stmt)
 364 {
 365   tree lhs = gimple_assign_lhs (stmt);
 366
 367   if (dump_file && (dump_flags & TDF_DETAILS))
 368     {
 369       fprintf (dump_file, "-------------------------\n");
 370       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
 371     }
 372
 373   /* Some of these constrains might be too conservative.  */
 374   if (stmt_ends_bb_p (stmt)
 375       || gimple_has_volatile_ops (stmt)
 376       || (TREE_CODE (lhs) == SSA_NAME
 377           && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
 378       || gimple_has_side_effects (stmt))
 379     {
 380       if (dump_file && (dump_flags & TDF_DETAILS))
 381         fprintf (dump_file, "stmt not suitable for ifcvt\n");
 382       return false;
 383     }
 384
 385   /* See if it needs speculative loading or not.  */
 386   if (bb != loop->header
 387       && gimple_assign_rhs_could_trap_p (stmt))
 388     {
 389       if (dump_file && (dump_flags & TDF_DETAILS))
 390         fprintf (dump_file, "tree could trap...\n");
 391       return false;
 392     }
 393
 394   if (TREE_CODE (lhs) != SSA_NAME
 395       && bb != loop->header
 396       && !bb_with_exit_edge_p (loop, bb))
 397     {
 398       if (dump_file && (dump_flags & TDF_DETAILS))
 399         {
 400           fprintf (dump_file, "LHS is not var\n");
 401           print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
 402         }
 403       return false;
 404     }
 405
 406   return true;
 407 }
 408
 409 /* Return true, iff STMT is if-convertible.
 410    Statement is if-convertible if,
 411    - it is if-convertible GIMPLE_ASSGIN,
 412    - it is GIMPLE_LABEL or GIMPLE_COND.
 413    STMT is inside block BB, which is inside loop LOOP.  */
 414
 415 static bool
 416 if_convertible_stmt_p (struct loop *loop, basic_block bb, gimple stmt)
 417 {
 418   switch (gimple_code (stmt))
 419     {
 420     case GIMPLE_LABEL:
 421     case GIMPLE_DEBUG:
 422     case GIMPLE_COND:
 423       return true;
 424
 425     case GIMPLE_ASSIGN:
 426       return if_convertible_gimple_assign_stmt_p (loop, bb, stmt);
 427
 428     default:
 429       /* Don't know what to do with 'em so don't do anything.  */
 430       if (dump_file && (dump_flags & TDF_DETAILS))
 431         {
 432           fprintf (dump_file, "don't know what to do\n");
 433           print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
 434         }
 435       return false;
 436       break;
 437     }
 438
 439   return true;
 440 }
 441
 442 /* Return true, iff BB is if-convertible.
 443    Note: This routine does _not_ check basic block statements and phis.
 444    Basic block is not if-convertible if:
 445    - basic block is non-empty and it is after exit block (in BFS order),
 446    - basic block is after exit block but before latch,
 447    - basic block edge(s) is not normal.
 448    EXIT_BB_SEEN is true if basic block with exit edge is already seen.
 449    BB is inside loop LOOP.  */
 450
 451 static bool
 452 if_convertible_bb_p (struct loop *loop, basic_block bb, basic_block exit_bb)
 453 {
 454   edge e;
 455   edge_iterator ei;
 456
 457   if (dump_file && (dump_flags & TDF_DETAILS))
 458     fprintf (dump_file, "----------[%d]-------------\n", bb->index);
 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 iff, all pred blocks of BB are visited.
 498    Bitmap VISITED keeps history of 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 /* Return true, iff LOOP is if-convertible.
 572    LOOP is if-convertible if:
 573    - it is innermost,
 574    - it has two or more basic blocks,
 575    - it has only one exit,
 576    - loop header is not the exit edge,
 577    - if its basic blocks and phi nodes are if convertible.  See above for
 578      more info.
 579    FOR_VECTORIZER enables vectorizer specific checks, for example, support
 580    for vector conditions, data dependency checks, etc.
 581    (Not implemented yet).  */
 582
 583 static bool
 584 pred_blocks_visited_p (basic_block bb, bitmap *visited)
 585 {
 586   edge e;
 587   edge_iterator ei;
 588   FOR_EACH_EDGE (e, ei, bb->preds)
 589     if (!bitmap_bit_p (*visited, e->src->index))
 590       return false;
 591
 592   return true;
 593 }
 594
 595 /* Get body of a LOOP in suitable order for if-conversion.  It is
 596    caller's responsibility to deallocate basic block list.
 597    If-conversion suitable order is, breadth first sort (BFS) order
 598    with an additional constraint: select a block only if all its
 599    predecessors are already selected.  */
 600
 601 static basic_block *
 602 get_loop_body_in_if_conv_order (const struct loop *loop)
 603 {
 604   basic_block *blocks, *blocks_in_bfs_order;
 605   basic_block bb;
 606   bitmap visited;
 607   unsigned int index = 0;
 608   unsigned int visited_count = 0;
 609
 610   gcc_assert (loop->num_nodes);
 611   gcc_assert (loop->latch != EXIT_BLOCK_PTR);
 612
 613   blocks = XCNEWVEC (basic_block, loop->num_nodes);
 614   visited = BITMAP_ALLOC (NULL);
 615
 616   blocks_in_bfs_order = get_loop_body_in_bfs_order (loop);
 617
 618   index = 0;
 619   while (index < loop->num_nodes)
 620     {
 621       bb = blocks_in_bfs_order [index];
 622
 623       if (bb->flags & BB_IRREDUCIBLE_LOOP)
 624         {
 625           free (blocks_in_bfs_order);
 626           BITMAP_FREE (visited);
 627           free (blocks);
 628           return NULL;
 629         }
 630
 631       if (!bitmap_bit_p (visited, bb->index))
 632         {
 633           if (pred_blocks_visited_p (bb, &visited)
 634               || bb == loop->header)
 635             {
 636               /* This block is now visited.  */
 637               bitmap_set_bit (visited, bb->index);
 638               blocks[visited_count++] = bb;
 639             }
 640         }
 641
 642       index++;
 643
 644       if (index == loop->num_nodes
 645           && visited_count != loop->num_nodes)
 646         /* Not done yet.  */
 647         index = 0;
 648     }
 649   free (blocks_in_bfs_order);
 650   BITMAP_FREE (visited);
 651   return blocks;
 652 }
 653
 654 /* Return true when LOOP is if-convertible.
 655    LOOP is if-convertible if:
 656    - it is innermost,
 657    - it has two or more basic blocks,
 658    - it has only one exit,
 659    - loop header is not the exit edge,
 660    - if its basic blocks and phi nodes are if convertible.  */
 661
 662 static bool
 663 if_convertible_loop_p (struct loop *loop)
 664 {
 665   basic_block bb;
 666   gimple_stmt_iterator itr;
 667   unsigned int i;
 668   edge e;
 669   edge_iterator ei;
 670   basic_block exit_bb = NULL;
 671
 672   /* Handle only inner most loop.  */
 673   if (!loop || loop->inner)
 674     {
 675       if (dump_file && (dump_flags & TDF_DETAILS))
 676         fprintf (dump_file, "not inner most loop\n");
 677       return false;
 678     }
 679
 680   /* If only one block, no need for if-conversion.  */
 681   if (loop->num_nodes <= 2)
 682     {
 683       if (dump_file && (dump_flags & TDF_DETAILS))
 684         fprintf (dump_file, "less than 2 basic blocks\n");
 685       return false;
 686     }
 687
 688   /* More than one loop exit is too much to handle.  */
 689   if (!single_exit (loop))
 690     {
 691       if (dump_file && (dump_flags & TDF_DETAILS))
 692         fprintf (dump_file, "multiple exits\n");
 693       return false;
 694     }
 695
 696   /* ??? Check target's vector conditional operation support for vectorizer.  */
 697
 698   /* If one of the loop header's edge is exit edge then do not apply
 699      if-conversion.  */
 700   FOR_EACH_EDGE (e, ei, loop->header->succs)
 701     {
 702       if (loop_exit_edge_p (loop, e))
 703         return false;
 704     }
 705
 706   calculate_dominance_info (CDI_DOMINATORS);
 707   calculate_dominance_info (CDI_POST_DOMINATORS);
 708
 709   /* Allow statements that can be handled during if-conversion.  */
 710   ifc_bbs = get_loop_body_in_if_conv_order (loop);
 711   if (!ifc_bbs)
 712     {
 713       if (dump_file && (dump_flags & TDF_DETAILS))
 714         fprintf (dump_file,"Irreducible loop\n");
 715       free_dominance_info (CDI_POST_DOMINATORS);
 716       return false;
 717     }
 718
 719   for (i = 0; i < loop->num_nodes; i++)
 720     {
 721       bb = ifc_bbs[i];
 722
 723       if (!if_convertible_bb_p (loop, bb, exit_bb))
 724         return false;
 725
 726       for (itr = gsi_start_bb (bb); !gsi_end_p (itr); gsi_next (&itr))
 727         if (!if_convertible_stmt_p (loop, bb, gsi_stmt (itr)))
 728           return false;
 729
 730       itr = gsi_start_phis (bb);
 731
 732       if (!gsi_end_p (itr))
 733         FOR_EACH_EDGE (e, ei, bb->preds)
 734           e->aux = NULL;
 735
 736       for (; !gsi_end_p (itr); gsi_next (&itr))
 737         if (!if_convertible_phi_p (loop, bb, gsi_stmt (itr)))
 738           return false;
 739
 740       if (bb_with_exit_edge_p (loop, bb))
 741         exit_bb = bb;
 742     }
 743
 744   if (dump_file)
 745     fprintf (dump_file,"Applying if-conversion\n");
 746
 747   free_dominance_info (CDI_POST_DOMINATORS);
 748   return true;
 749 }
 750
 751 /* During if-conversion aux field from basic block structure is used to hold
 752    predicate list.  Clean each basic block's predicate list for the given LOOP.
 753    Also clean aux field of successor edges, used to hold true and false
 754    condition from conditional expression.  */
 755
 756 static void
 757 clean_predicate_lists (struct loop *loop)
 758 {
 759   basic_block *bb;
 760   unsigned int i;
 761   edge e;
 762   edge_iterator ei;
 763
 764   bb = get_loop_body (loop);
 765   for (i = 0; i < loop->num_nodes; i++)
 766     {
 767       bb[i]->aux = NULL;
 768       FOR_EACH_EDGE (e, ei, bb[i]->succs)
 769         e->aux = NULL;
 770     }
 771   free (bb);
 772 }
 773
 774 /* Basic block BB has two predecessors. Using predecessor's aux field, set
 775    appropriate condition COND for the PHI node replacement.  Return true block
 776    whose phi arguments are selected when cond is true.  */
 777
 778 static basic_block
 779 find_phi_replacement_condition (struct loop *loop,
 780                                 basic_block bb, tree *cond,
 781                                 gimple_stmt_iterator *gsi)
 782 {
 783   edge first_edge, second_edge;
 784   tree tmp_cond;
 785
 786   gcc_assert (EDGE_COUNT (bb->preds) == 2);
 787   first_edge = EDGE_PRED (bb, 0);
 788   second_edge = EDGE_PRED (bb, 1);
 789
 790   /* Use condition based on following criteria:
 791      1)
 792        S1: x = !c ? a : b;
 793
 794        S2: x = c ? b : a;
 795
 796        S2 is preferred over S1. Make 'b' first_bb and use its condition.
 797
 798      2) Do not make loop header first_bb.
 799
 800      3)
 801        S1: x = !(c == d)? a : b;
 802
 803        S21: t1 = c == d;
 804        S22: x = t1 ? b : a;
 805
 806        S3: x = (c == d) ? b : a;
 807
 808        S3 is preferred over S1 and S2*, Make 'b' first_bb and use
 809        its condition.
 810
 811      4) If  pred B is dominated by pred A then use pred B's condition.
 812         See PR23115.  */
 813
 814   /* Select condition that is not TRUTH_NOT_EXPR.  */
 815   tmp_cond = (tree) (first_edge->src)->aux;
 816   gcc_assert (tmp_cond);
 817
 818   if (TREE_CODE (tmp_cond) == TRUTH_NOT_EXPR)
 819     {
 820       edge tmp_edge;
 821
 822       tmp_edge = first_edge;
 823       first_edge = second_edge;
 824       second_edge = tmp_edge;
 825     }
 826
 827   /* Check if FIRST_BB is loop header or not and make sure that
 828      FIRST_BB does not dominate SECOND_BB.  */
 829   if (first_edge->src == loop->header
 830       || dominated_by_p (CDI_DOMINATORS,
 831                          second_edge->src, first_edge->src))
 832     {
 833       *cond = (tree) (second_edge->src)->aux;
 834
 835       /* If there is a condition on an incoming edge, add it to the
 836          incoming bb predicate.  */
 837       if (second_edge->aux)
 838         *cond = build2 (TRUTH_AND_EXPR, boolean_type_node,
 839                         *cond, (tree) second_edge->aux);
 840
 841       if (TREE_CODE (*cond) == TRUTH_NOT_EXPR)
 842         *cond = invert_truthvalue (*cond);
 843       else
 844         /* Select non loop header bb.  */
 845         first_edge = second_edge;
 846     }
 847   else
 848     {
 849       *cond = (tree) (first_edge->src)->aux;
 850
 851       /* If there is a condition on an incoming edge, add it to the
 852          incoming bb predicate.  */
 853       if (first_edge->aux)
 854         *cond = build2 (TRUTH_AND_EXPR, boolean_type_node,
 855                         *cond, (tree) first_edge->aux);
 856     }
 857
 858   /* Gimplify the condition: the vectorizer prefers to have gimple
 859      values as conditions.  Various targets use different means to
 860      communicate conditions in vector compare operations.  Using a
 861      gimple value allows the compiler to emit vector compare and
 862      select RTL without exposing compare's result.  */
 863   *cond = force_gimple_operand_gsi (gsi, unshare_expr (*cond),
 864                                     false, NULL_TREE,
 865                                     true, GSI_SAME_STMT);
 866   if (!is_gimple_reg (*cond) && !is_gimple_condexpr (*cond))
 867     {
 868       gimple new_stmt;
 869
 870       new_stmt = ifc_temp_var (TREE_TYPE (*cond), unshare_expr (*cond));
 871       gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
 872       *cond = gimple_assign_lhs (new_stmt);
 873     }
 874
 875   gcc_assert (*cond);
 876
 877   return first_edge->src;
 878 }
 879
 880 /* Replace PHI node with conditional modify expr using COND.  This
 881    routine does not handle PHI nodes with more than two arguments.
 882
 883    For example,
 884      S1: A = PHI <x1(1), x2(5)
 885    is converted into,
 886      S2: A = cond ? x1 : x2;
 887
 888    The generated code is inserted at GSI that points to the top of
 889    basic block's statement list.  When COND is true, phi arg from
 890    TRUE_BB is selected.  */
 891
 892 static void
 893 replace_phi_with_cond_gimple_assign_stmt (gimple phi, tree cond,
 894                                           basic_block true_bb,
 895                                           gimple_stmt_iterator *gsi)
 896 {
 897   gimple new_stmt;
 898   basic_block bb;
 899   tree rhs;
 900   tree arg_0, arg_1;
 901
 902   gcc_assert (gimple_code (phi) == GIMPLE_PHI
 903               && gimple_phi_num_args (phi) == 2);
 904
 905   bb = gimple_bb (phi);
 906
 907   /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr.  */
 908   if (EDGE_PRED (bb, 1)->src == true_bb)
 909     {
 910       arg_0 = gimple_phi_arg_def (phi, 1);
 911       arg_1 = gimple_phi_arg_def (phi, 0);
 912     }
 913   else
 914     {
 915       arg_0 = gimple_phi_arg_def (phi, 0);
 916       arg_1 = gimple_phi_arg_def (phi, 1);
 917     }
 918
 919   /* Build new RHS using selected condition and arguments.  */
 920   rhs = build3 (COND_EXPR, TREE_TYPE (PHI_RESULT (phi)),
 921                 unshare_expr (cond), unshare_expr (arg_0),
 922                 unshare_expr (arg_1));
 923
 924   new_stmt = gimple_build_assign (unshare_expr (PHI_RESULT (phi)), rhs);
 925   SSA_NAME_DEF_STMT (gimple_phi_result (phi)) = new_stmt;
 926   gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
 927   update_stmt (new_stmt);
 928
 929   if (dump_file && (dump_flags & TDF_DETAILS))
 930     {
 931       fprintf (dump_file, "new phi replacement stmt\n");
 932       print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM);
 933     }
 934 }
 935
 936 /* Process phi nodes for the given LOOP.  Replace phi nodes with
 937    conditional modify expressions.  */
 938
 939 static void
 940 process_phi_nodes (struct loop *loop)
 941 {
 942   basic_block bb;
 943   unsigned int orig_loop_num_nodes = loop->num_nodes;
 944   unsigned int i;
 945
 946   for (i = 1; i < orig_loop_num_nodes; i++)
 947     {
 948       gimple phi;
 949       tree cond = NULL_TREE;
 950       gimple_stmt_iterator gsi, phi_gsi;
 951       basic_block true_bb = NULL;
 952       bb = ifc_bbs[i];
 953
 954       if (bb == loop->header)
 955         continue;
 956
 957       phi_gsi = gsi_start_phis (bb);
 958       gsi = gsi_after_labels (bb);
 959
 960       /* BB has two predecessors.  Using predecessor's aux field, set
 961          appropriate condition for the PHI node replacement.  */
 962       if (!gsi_end_p (phi_gsi))
 963         true_bb = find_phi_replacement_condition (loop, bb, &cond, &gsi);
 964
 965       while (!gsi_end_p (phi_gsi))
 966         {
 967           phi = gsi_stmt (phi_gsi);
 968           replace_phi_with_cond_gimple_assign_stmt (phi, cond, true_bb, &gsi);
 969           release_phi_node (phi);
 970           gsi_next (&phi_gsi);
 971         }
 972       set_phi_nodes (bb, NULL);
 973     }
 974 }
 975
 976 /* Combine all the basic blocks from LOOP into one or two super basic
 977    blocks.  Replace PHI nodes with conditional modify expressions.  */
 978
 979 static void
 980 combine_blocks (struct loop *loop)
 981 {
 982   basic_block bb, exit_bb, merge_target_bb;
 983   unsigned int orig_loop_num_nodes = loop->num_nodes;
 984   unsigned int i;
 985   edge e;
 986   edge_iterator ei;
 987
 988   /* Process phi nodes to prepare blocks for merge.  */
 989   process_phi_nodes (loop);
 990
 991   /* Merge basic blocks: first remove all the edges in the loop,
 992      except for those from the exit block.  */
 993   exit_bb = NULL;
 994   for (i = 0; i < orig_loop_num_nodes; i++)
 995     {
 996       bb = ifc_bbs[i];
 997       if (bb_with_exit_edge_p (loop, bb))
 998         {
 999           exit_bb = bb;
1000           break;
1001         }
1002     }
1003   gcc_assert (exit_bb != loop->latch);
1004
1005   for (i = 1; i < orig_loop_num_nodes; i++)
1006     {
1007       bb = ifc_bbs[i];
1008
1009       for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei));)
1010         {
1011           if (e->src == exit_bb)
1012             ei_next (&ei);
1013           else
1014             remove_edge (e);
1015         }
1016     }
1017
1018   if (exit_bb != NULL)
1019     {
1020       if (exit_bb != loop->header)
1021         {
1022           /* Connect this node to loop header.  */
1023           make_edge (loop->header, exit_bb, EDGE_FALLTHRU);
1024           set_immediate_dominator (CDI_DOMINATORS, exit_bb, loop->header);
1025         }
1026
1027       /* Redirect non-exit edges to loop->latch.  */
1028       FOR_EACH_EDGE (e, ei, exit_bb->succs)
1029         {
1030           if (!loop_exit_edge_p (loop, e))
1031             redirect_edge_and_branch (e, loop->latch);
1032         }
1033       set_immediate_dominator (CDI_DOMINATORS, loop->latch, exit_bb);
1034     }
1035   else
1036     {
1037       /* If the loop does not have an exit, reconnect header and latch.  */
1038       make_edge (loop->header, loop->latch, EDGE_FALLTHRU);
1039       set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header);
1040     }
1041
1042   merge_target_bb = loop->header;
1043   for (i = 1; i < orig_loop_num_nodes; i++)
1044     {
1045       gimple_stmt_iterator gsi;
1046       gimple_stmt_iterator last;
1047
1048       bb = ifc_bbs[i];
1049
1050       if (bb == exit_bb || bb == loop->latch)
1051         continue;
1052
1053       /* Remove labels and make stmts member of loop->header.  */
1054       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
1055         {
1056           if (gimple_code (gsi_stmt (gsi)) == GIMPLE_LABEL)
1057             gsi_remove (&gsi, true);
1058           else
1059             {
1060               gimple_set_bb (gsi_stmt (gsi), merge_target_bb);
1061               gsi_next (&gsi);
1062             }
1063         }
1064
1065       /* Update stmt list.  */
1066       last = gsi_last_bb (merge_target_bb);
1067       gsi_insert_seq_after (&last, bb_seq (bb), GSI_NEW_STMT);
1068       set_bb_seq (bb, NULL);
1069
1070       delete_basic_block (bb);
1071     }
1072
1073   /* Now if possible, merge loop header and block with exit edge.
1074      This reduces number of basic blocks to 2.  Auto vectorizer addresses
1075      loops with two nodes only.  FIXME: Use cleanup_tree_cfg().  */
1076   if (exit_bb
1077       && exit_bb != loop->header
1078       && can_merge_blocks_p (loop->header, exit_bb))
1079     merge_blocks (loop->header, exit_bb);
1080 }
1081
1082 /* Main entry point.  Apply if-conversion to the LOOP.  Return true if
1083    successful otherwise return false.  If false is returned then loop
1084    remains unchanged.  FOR_VECTORIZER is a boolean flag.  It indicates
1085    whether if-conversion is used for vectorizer or not.  If it is used
1086    for vectorizer, additional checks are used. (Vectorization checks
1087    are not yet implemented).  */
1088
1089 static bool
1090 tree_if_conversion (struct loop *loop, bool for_vectorizer)
1091 {
1092   basic_block bb;
1093   gimple_stmt_iterator itr;
1094   unsigned int i;
1095
1096   ifc_bbs = NULL;
1097
1098   /* If-conversion is not appropriate for all loops.  First, check if
1099      loop is if-convertible or not.  */
1100   if (!if_convertible_loop_p (loop, for_vectorizer))
1101     {
1102       if (dump_file && (dump_flags & TDF_DETAILS))
1103         fprintf (dump_file,"-------------------------\n");
1104       if (ifc_bbs)
1105         {
1106           free (ifc_bbs);
1107           ifc_bbs = NULL;
1108         }
1109       free_dominance_info (CDI_POST_DOMINATORS);
1110       return false;
1111     }
1112
1113   /* Do actual work now.  */
1114   for (i = 0; i < loop->num_nodes; i++)
1115     {
1116       tree cond;
1117
1118       bb = ifc_bbs [i];
1119
1120       /* Update condition using predicate list.  */
1121       cond = (tree) bb->aux;
1122
1123       /* Process all statements in this basic block.
1124          Remove conditional expression, if any, and annotate
1125          destination basic block(s) appropriately.  */
1126       for (itr = gsi_start_bb (bb); !gsi_end_p (itr); /* empty */)
1127         {
1128           gimple t = gsi_stmt (itr);
1129           cond = tree_if_convert_stmt (loop, t, cond, &itr);
1130           if (!gsi_end_p (itr))
1131             gsi_next (&itr);
1132         }
1133
1134       /* If current bb has only one successor, then consider it as an
1135          unconditional goto.  */
1136       if (single_succ_p (bb))
1137         {
1138           basic_block bb_n = single_succ (bb);
1139
1140           /* Successor bb inherits predicate of its predecessor.  If there
1141              is no predicate in predecessor bb, then consider successor bb
1142              as always executed.  */
1143           if (cond == NULL_TREE)
1144             cond = boolean_true_node;
1145
1146           add_to_predicate_list (bb_n, cond);
1147         }
1148     }
1149
1150   /* Now, all statements are if-converted and basic blocks are
1151      annotated appropriately.  Combine all basic block into one huge
1152      basic block.  */
1153   combine_blocks (loop);
1154
1155   /* clean up */
1156   clean_predicate_lists (loop);
1157   free (ifc_bbs);
1158   ifc_bbs = NULL;
1159
1160   return true;
1161 }
1162
1163 /* Tree if-conversion pass management.  */
1164
1165 static unsigned int
1166 main_tree_if_conversion (void)
1167 {
1168   loop_iterator li;
1169   struct loop *loop;
1170
1171   if (number_of_loops () <= 1)
1172     return 0;
1173
1174   FOR_EACH_LOOP (li, loop, 0)
1175     tree_if_conversion (loop);
1176
1177   return 0;
1178 }
1179
1180 static bool
1181 gate_tree_if_conversion (void)
1182 {
1183   return flag_tree_vectorize != 0;
1184 }
1185
1186 struct gimple_opt_pass pass_if_conversion =
1187 {
1188  {
1189   GIMPLE_PASS,
1190   "ifcvt",                              /* name */
1191   gate_tree_if_conversion,              /* gate */
1192   main_tree_if_conversion,              /* execute */
1193   NULL,                                 /* sub */
1194   NULL,                                 /* next */
1195   0,                                    /* static_pass_number */
1196   TV_NONE,                              /* tv_id */
1197   PROP_cfg | PROP_ssa,                  /* properties_required */
1198   0,                                    /* properties_provided */
1199   0,                                    /* properties_destroyed */
1200   0,                                    /* todo_flags_start */
1201   TODO_dump_func | TODO_verify_stmts | TODO_verify_flow
1202                                         /* todo_flags_finish */
1203  }
1204 };