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 tree level if-conversion transformation of loops.
  23    Initial goal is to help vectorizer vectorize loops with conditions.
  24
  25    A short description of if-conversion:
  26
  27      o Decide if a loop is if-convertible or not.
  28      o Walk all loop basic blocks in breadth first order (BFS order).
  29        o Remove conditional statements (at the end of basic block)
  30          and propagate condition into destination basic blocks'
  31          predicate list.
  32        o Replace modify expression with conditional modify expression
  33          using current basic block's condition.
  34      o Merge all basic blocks
  35        o Replace phi nodes with conditional modify expr
  36        o Merge all basic blocks into header
  37
  38      Sample transformation:
  39
  40      INPUT
  41      -----
  42
  43      # i_23 = PHI <0(0), i_18(10)>;
  44      <L0>:;
  45      j_15 = A[i_23];
  46      if (j_15 > 41) goto <L1>; else goto <L17>;
  47
  48      <L17>:;
  49      goto <bb 3> (<L3>);
  50
  51      <L1>:;
  52
  53      # iftmp.2_4 = PHI <0(8), 42(2)>;
  54      <L3>:;
  55      A[i_23] = iftmp.2_4;
  56      i_18 = i_23 + 1;
  57      if (i_18 <= 15) goto <L19>; else goto <L18>;
  58
  59      <L19>:;
  60      goto <bb 1> (<L0>);
  61
  62      <L18>:;
  63
  64      OUTPUT
  65      ------
  66
  67      # i_23 = PHI <0(0), i_18(10)>;
  68      <L0>:;
  69      j_15 = A[i_23];
  70
  71      <L3>:;
  72      iftmp.2_4 = j_15 > 41 ? 42 : 0;
  73      A[i_23] = iftmp.2_4;
  74      i_18 = i_23 + 1;
  75      if (i_18 <= 15) goto <L19>; else goto <L18>;
  76
  77      <L19>:;
  78      goto <bb 1> (<L0>);
  79
  80      <L18>:;
  81 */
  82
  83 #include "config.h"
  84 #include "system.h"
  85 #include "coretypes.h"
  86 #include "tm.h"
  87 #include "tree.h"
  88 #include "flags.h"
  89 #include "timevar.h"
  90 #include "varray.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, if STMT is if-convertible.
 354    GIMPLE_ASSIGN statement is not if-convertible if,
 355    - it is not movable,
 356    - it could trap,
 357    - LHS is not var decl.
 358    GIMPLE_ASSIGN is part of block BB, which is inside loop LOOP.  */
 359
 360 static bool
 361 if_convertible_gimple_assign_stmt_p (struct loop *loop, basic_block bb,
 362                                      gimple stmt)
 363 {
 364   tree lhs;
 365
 366   if (!is_gimple_assign (stmt))
 367     return false;
 368
 369   if (dump_file && (dump_flags & TDF_DETAILS))
 370     {
 371       fprintf (dump_file, "-------------------------\n");
 372       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
 373     }
 374
 375   lhs = gimple_assign_lhs (stmt);
 376
 377   /* Some of these constrains might be too conservative.  */
 378   if (stmt_ends_bb_p (stmt)
 379       || gimple_has_volatile_ops (stmt)
 380       || (TREE_CODE (lhs) == SSA_NAME
 381           && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
 382       || gimple_has_side_effects (stmt))
 383     {
 384       if (dump_file && (dump_flags & TDF_DETAILS))
 385         fprintf (dump_file, "stmt not suitable for ifcvt\n");
 386       return false;
 387     }
 388
 389   /* See if it needs speculative loading or not.  */
 390   if (bb != loop->header
 391       && gimple_assign_rhs_could_trap_p (stmt))
 392     {
 393       if (dump_file && (dump_flags & TDF_DETAILS))
 394         fprintf (dump_file, "tree could trap...\n");
 395       return false;
 396     }
 397
 398   if (TREE_CODE (lhs) != SSA_NAME
 399       && bb != loop->header
 400       && !bb_with_exit_edge_p (loop, bb))
 401     {
 402       if (dump_file && (dump_flags & TDF_DETAILS))
 403         {
 404           fprintf (dump_file, "LHS is not var\n");
 405           print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
 406         }
 407       return false;
 408     }
 409
 410   return true;
 411 }
 412
 413 /* Return true, iff STMT is if-convertible.
 414    Statement is if-convertible if,
 415    - it is if-convertible GIMPLE_ASSGIN,
 416    - it is GIMPLE_LABEL or GIMPLE_COND.
 417    STMT is inside block BB, which is inside loop LOOP.  */
 418
 419 static bool
 420 if_convertible_stmt_p (struct loop *loop, basic_block bb, gimple stmt)
 421 {
 422   switch (gimple_code (stmt))
 423     {
 424     case GIMPLE_LABEL:
 425       break;
 426
 427     case GIMPLE_DEBUG:
 428       break;
 429
 430     case GIMPLE_ASSIGN:
 431       if (!if_convertible_gimple_assign_stmt_p (loop, bb, stmt))
 432         return false;
 433       break;
 434
 435     case GIMPLE_COND:
 436       break;
 437
 438     default:
 439       /* Don't know what to do with 'em so don't do anything.  */
 440       if (dump_file && (dump_flags & TDF_DETAILS))
 441         {
 442           fprintf (dump_file, "don't know what to do\n");
 443           print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
 444         }
 445       return false;
 446       break;
 447     }
 448
 449   return true;
 450 }
 451
 452 /* Return true, iff BB is if-convertible.
 453    Note: This routine does _not_ check basic block statements and phis.
 454    Basic block is not if-convertible if:
 455    - basic block is non-empty and it is after exit block (in BFS order),
 456    - basic block is after exit block but before latch,
 457    - basic block edge(s) is not normal.
 458    EXIT_BB_SEEN is true if basic block with exit edge is already seen.
 459    BB is inside loop LOOP.  */
 460
 461 static bool
 462 if_convertible_bb_p (struct loop *loop, basic_block bb, basic_block exit_bb)
 463 {
 464   edge e;
 465   edge_iterator ei;
 466
 467   if (dump_file && (dump_flags & TDF_DETAILS))
 468     fprintf (dump_file, "----------[%d]-------------\n", bb->index);
 469
 470   if (exit_bb)
 471     {
 472       if (bb != loop->latch)
 473         {
 474           if (dump_file && (dump_flags & TDF_DETAILS))
 475             fprintf (dump_file, "basic block after exit bb but before latch\n");
 476           return false;
 477         }
 478       else if (!empty_block_p (bb))
 479         {
 480           if (dump_file && (dump_flags & TDF_DETAILS))
 481             fprintf (dump_file, "non empty basic block after exit bb\n");
 482           return false;
 483         }
 484       else if (bb == loop->latch
 485                && bb != exit_bb
 486                && !dominated_by_p (CDI_DOMINATORS, bb, exit_bb))
 487           {
 488             if (dump_file && (dump_flags & TDF_DETAILS))
 489               fprintf (dump_file, "latch is not dominated by exit_block\n");
 490             return false;
 491           }
 492     }
 493
 494   /* Be less adventurous and handle only normal edges.  */
 495   FOR_EACH_EDGE (e, ei, bb->succs)
 496     if (e->flags &
 497         (EDGE_ABNORMAL_CALL | EDGE_EH | EDGE_ABNORMAL | EDGE_IRREDUCIBLE_LOOP))
 498       {
 499         if (dump_file && (dump_flags & TDF_DETAILS))
 500           fprintf (dump_file,"Difficult to handle edges\n");
 501         return false;
 502       }
 503
 504   return true;
 505 }
 506
 507 /* Return TRUE iff, all pred blocks of BB are visited.
 508    Bitmap VISITED keeps history of visited blocks.  */
 509
 510 static bool
 511 pred_blocks_visited_p (basic_block bb, bitmap *visited)
 512 {
 513   edge e;
 514   edge_iterator ei;
 515   FOR_EACH_EDGE (e, ei, bb->preds)
 516     if (!bitmap_bit_p (*visited, e->src->index))
 517       return false;
 518
 519   return true;
 520 }
 521
 522 /* Get body of a LOOP in suitable order for if-conversion.  It is
 523    caller's responsibility to deallocate basic block list.
 524    If-conversion suitable order is, breadth first sort (BFS) order
 525    with an additional constraint: select a block only if all its
 526    predecessors are already selected.  */
 527
 528 static basic_block *
 529 get_loop_body_in_if_conv_order (const struct loop *loop)
 530 {
 531   basic_block *blocks, *blocks_in_bfs_order;
 532   basic_block bb;
 533   bitmap visited;
 534   unsigned int index = 0;
 535   unsigned int visited_count = 0;
 536
 537   gcc_assert (loop->num_nodes);
 538   gcc_assert (loop->latch != EXIT_BLOCK_PTR);
 539
 540   blocks = XCNEWVEC (basic_block, loop->num_nodes);
 541   visited = BITMAP_ALLOC (NULL);
 542
 543   blocks_in_bfs_order = get_loop_body_in_bfs_order (loop);
 544
 545   index = 0;
 546   while (index < loop->num_nodes)
 547     {
 548       bb = blocks_in_bfs_order [index];
 549
 550       if (bb->flags & BB_IRREDUCIBLE_LOOP)
 551         {
 552           free (blocks_in_bfs_order);
 553           BITMAP_FREE (visited);
 554           free (blocks);
 555           return NULL;
 556         }
 557
 558       if (!bitmap_bit_p (visited, bb->index))
 559         {
 560           if (pred_blocks_visited_p (bb, &visited)
 561               || bb == loop->header)
 562             {
 563               /* This block is now visited.  */
 564               bitmap_set_bit (visited, bb->index);
 565               blocks[visited_count++] = bb;
 566             }
 567         }
 568
 569       index++;
 570
 571       if (index == loop->num_nodes
 572           && visited_count != loop->num_nodes)
 573         /* Not done yet.  */
 574         index = 0;
 575     }
 576   free (blocks_in_bfs_order);
 577   BITMAP_FREE (visited);
 578   return blocks;
 579 }
 580
 581 /* Return true, iff LOOP is if-convertible.
 582    LOOP is if-convertible if:
 583    - it is innermost,
 584    - it has two or more basic blocks,
 585    - it has only one exit,
 586    - loop header is not the exit edge,
 587    - if its basic blocks and phi nodes are if convertible.  */
 588
 589 static bool
 590 if_convertible_loop_p (struct loop *loop)
 591 {
 592   basic_block bb;
 593   gimple_stmt_iterator itr;
 594   unsigned int i;
 595   edge e;
 596   edge_iterator ei;
 597   basic_block exit_bb = NULL;
 598
 599   /* Handle only inner most loop.  */
 600   if (!loop || loop->inner)
 601     {
 602       if (dump_file && (dump_flags & TDF_DETAILS))
 603         fprintf (dump_file, "not inner most loop\n");
 604       return false;
 605     }
 606
 607   /* If only one block, no need for if-conversion.  */
 608   if (loop->num_nodes <= 2)
 609     {
 610       if (dump_file && (dump_flags & TDF_DETAILS))
 611         fprintf (dump_file, "less than 2 basic blocks\n");
 612       return false;
 613     }
 614
 615   /* More than one loop exit is too much to handle.  */
 616   if (!single_exit (loop))
 617     {
 618       if (dump_file && (dump_flags & TDF_DETAILS))
 619         fprintf (dump_file, "multiple exits\n");
 620       return false;
 621     }
 622
 623   /* ??? Check target's vector conditional operation support for vectorizer.  */
 624
 625   /* If one of the loop header's edge is exit edge then do not apply
 626      if-conversion.  */
 627   FOR_EACH_EDGE (e, ei, loop->header->succs)
 628     {
 629       if (loop_exit_edge_p (loop, e))
 630         return false;
 631     }
 632
 633   calculate_dominance_info (CDI_DOMINATORS);
 634   calculate_dominance_info (CDI_POST_DOMINATORS);
 635
 636   /* Allow statements that can be handled during if-conversion.  */
 637   ifc_bbs = get_loop_body_in_if_conv_order (loop);
 638   if (!ifc_bbs)
 639     {
 640       if (dump_file && (dump_flags & TDF_DETAILS))
 641         fprintf (dump_file,"Irreducible loop\n");
 642       free_dominance_info (CDI_POST_DOMINATORS);
 643       return false;
 644     }
 645
 646   for (i = 0; i < loop->num_nodes; i++)
 647     {
 648       bb = ifc_bbs[i];
 649
 650       if (!if_convertible_bb_p (loop, bb, exit_bb))
 651         return false;
 652
 653       for (itr = gsi_start_bb (bb); !gsi_end_p (itr); gsi_next (&itr))
 654         if (!if_convertible_stmt_p (loop, bb, gsi_stmt (itr)))
 655           return false;
 656
 657       itr = gsi_start_phis (bb);
 658
 659       if (!gsi_end_p (itr))
 660         FOR_EACH_EDGE (e, ei, bb->preds)
 661           e->aux = NULL;
 662
 663       for (; !gsi_end_p (itr); gsi_next (&itr))
 664         if (!if_convertible_phi_p (loop, bb, gsi_stmt (itr)))
 665           return false;
 666
 667       if (bb_with_exit_edge_p (loop, bb))
 668         exit_bb = bb;
 669     }
 670
 671   if (dump_file)
 672     fprintf (dump_file,"Applying if-conversion\n");
 673
 674   free_dominance_info (CDI_POST_DOMINATORS);
 675   return true;
 676 }
 677
 678 /* During if-conversion aux field from basic block structure is used to hold
 679    predicate list.  Clean each basic block's predicate list for the given LOOP.
 680    Also clean aux field of successor edges, used to hold true and false
 681    condition from conditional expression.  */
 682
 683 static void
 684 clean_predicate_lists (struct loop *loop)
 685 {
 686   basic_block *bb;
 687   unsigned int i;
 688   edge e;
 689   edge_iterator ei;
 690
 691   bb = get_loop_body (loop);
 692   for (i = 0; i < loop->num_nodes; i++)
 693     {
 694       bb[i]->aux = NULL;
 695       FOR_EACH_EDGE (e, ei, bb[i]->succs)
 696         e->aux = NULL;
 697     }
 698   free (bb);
 699 }
 700
 701 /* Basic block BB has two predecessors. Using predecessor's aux field, set
 702    appropriate condition COND for the PHI node replacement.  Return true block
 703    whose phi arguments are selected when cond is true.  */
 704
 705 static basic_block
 706 find_phi_replacement_condition (struct loop *loop,
 707                                 basic_block bb, tree *cond,
 708                                 gimple_stmt_iterator *gsi)
 709 {
 710   edge first_edge, second_edge;
 711   tree tmp_cond;
 712
 713   gcc_assert (EDGE_COUNT (bb->preds) == 2);
 714   first_edge = EDGE_PRED (bb, 0);
 715   second_edge = EDGE_PRED (bb, 1);
 716
 717   /* Use condition based on following criteria:
 718      1)
 719        S1: x = !c ? a : b;
 720
 721        S2: x = c ? b : a;
 722
 723        S2 is preferred over S1. Make 'b' first_bb and use its condition.
 724
 725      2) Do not make loop header first_bb.
 726
 727      3)
 728        S1: x = !(c == d)? a : b;
 729
 730        S21: t1 = c == d;
 731        S22: x = t1 ? b : a;
 732
 733        S3: x = (c == d) ? b : a;
 734
 735        S3 is preferred over S1 and S2*, Make 'b' first_bb and use
 736        its condition.
 737
 738      4) If  pred B is dominated by pred A then use pred B's condition.
 739         See PR23115.  */
 740
 741   /* Select condition that is not TRUTH_NOT_EXPR.  */
 742   tmp_cond = (tree) (first_edge->src)->aux;
 743   gcc_assert (tmp_cond);
 744
 745   if (TREE_CODE (tmp_cond) == TRUTH_NOT_EXPR)
 746     {
 747       edge tmp_edge;
 748
 749       tmp_edge = first_edge;
 750       first_edge = second_edge;
 751       second_edge = tmp_edge;
 752     }
 753
 754   /* Check if FIRST_BB is loop header or not and make sure that
 755      FIRST_BB does not dominate SECOND_BB.  */
 756   if (first_edge->src == loop->header
 757       || dominated_by_p (CDI_DOMINATORS,
 758                          second_edge->src, first_edge->src))
 759     {
 760       *cond = (tree) (second_edge->src)->aux;
 761
 762       /* If there is a condition on an incoming edge,
 763          AND it with the incoming bb predicate.  */
 764       if (second_edge->aux)
 765         *cond = build2 (TRUTH_AND_EXPR, boolean_type_node,
 766                         *cond, (tree) second_edge->aux);
 767
 768       if (TREE_CODE (*cond) == TRUTH_NOT_EXPR)
 769         /* We can be smart here and choose inverted
 770            condition without switching bbs.  */
 771         *cond = invert_truthvalue (*cond);
 772       else
 773         /* Select non loop header bb.  */
 774         first_edge = second_edge;
 775     }
 776   else
 777     {
 778       /* FIRST_BB is not loop header */
 779       *cond = (tree) (first_edge->src)->aux;
 780
 781       /* If there is a condition on an incoming edge,
 782          AND it with the incoming bb predicate.  */
 783       if (first_edge->aux)
 784         *cond = build2 (TRUTH_AND_EXPR, boolean_type_node,
 785                         *cond, (tree) first_edge->aux);
 786     }
 787
 788   /* Create temp. for the condition. Vectorizer prefers to have gimple
 789      value as condition. Various targets use different means to communicate
 790      condition in vector compare operation. Using gimple value allows
 791      compiler to emit vector compare and select RTL without exposing
 792      compare's result.  */
 793   *cond = force_gimple_operand_gsi (gsi, unshare_expr (*cond),
 794                                     false, NULL_TREE,
 795                                     true, GSI_SAME_STMT);
 796   if (!is_gimple_reg (*cond) && !is_gimple_condexpr (*cond))
 797     {
 798       gimple new_stmt;
 799
 800       new_stmt = ifc_temp_var (TREE_TYPE (*cond), unshare_expr (*cond));
 801       gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
 802       *cond = gimple_assign_lhs (new_stmt);
 803     }
 804
 805   gcc_assert (*cond);
 806
 807   return first_edge->src;
 808 }
 809
 810
 811 /* Replace PHI node with conditional modify expr using COND.
 812    This routine does not handle PHI nodes with more than two arguments.
 813    For example,
 814      S1: A = PHI <x1(1), x2(5)
 815    is converted into,
 816      S2: A = cond ? x1 : x2;
 817    S2 is inserted at the top of basic block's statement list.
 818    When COND is true, phi arg from TRUE_BB is selected.
 819 */
 820
 821 static void
 822 replace_phi_with_cond_gimple_assign_stmt (gimple phi, tree cond,
 823                                           basic_block true_bb,
 824                                           gimple_stmt_iterator *gsi)
 825 {
 826   gimple new_stmt;
 827   basic_block bb;
 828   tree rhs;
 829   tree arg_0, arg_1;
 830
 831   gcc_assert (gimple_code (phi) == GIMPLE_PHI);
 832
 833   /* If this is not filtered earlier, then now it is too late.  */
 834   gcc_assert (gimple_phi_num_args (phi) == 2);
 835
 836   /* Find basic block and initialize iterator.  */
 837   bb = gimple_bb (phi);
 838
 839   /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr.  */
 840   if (EDGE_PRED (bb, 1)->src == true_bb)
 841     {
 842       arg_0 = gimple_phi_arg_def (phi, 1);
 843       arg_1 = gimple_phi_arg_def (phi, 0);
 844     }
 845   else
 846     {
 847       arg_0 = gimple_phi_arg_def (phi, 0);
 848       arg_1 = gimple_phi_arg_def (phi, 1);
 849     }
 850
 851   /* Build new RHS using selected condition and arguments.  */
 852   rhs = build3 (COND_EXPR, TREE_TYPE (PHI_RESULT (phi)),
 853                 unshare_expr (cond), unshare_expr (arg_0),
 854                 unshare_expr (arg_1));
 855
 856   /* Create new GIMPLE_ASSIGN statement using RHS.  */
 857   new_stmt = gimple_build_assign (unshare_expr (PHI_RESULT (phi)), rhs);
 858
 859   /* Make new statement definition of the original phi result.  */
 860   SSA_NAME_DEF_STMT (gimple_phi_result (phi)) = new_stmt;
 861
 862   /* Insert using iterator.  */
 863   gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
 864   update_stmt (new_stmt);
 865
 866   if (dump_file && (dump_flags & TDF_DETAILS))
 867     {
 868       fprintf (dump_file, "new phi replacement stmt\n");
 869       print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM);
 870     }
 871 }
 872
 873 /* Process phi nodes for the given LOOP.  Replace phi nodes with
 874    conditional modify expressions.  */
 875
 876 static void
 877 process_phi_nodes (struct loop *loop)
 878 {
 879   basic_block bb;
 880   unsigned int orig_loop_num_nodes = loop->num_nodes;
 881   unsigned int i;
 882
 883   for (i = 1; i < orig_loop_num_nodes; i++)
 884     {
 885       gimple phi;
 886       tree cond = NULL_TREE;
 887       gimple_stmt_iterator gsi, phi_gsi;
 888       basic_block true_bb = NULL;
 889       bb = ifc_bbs[i];
 890
 891       if (bb == loop->header)
 892         continue;
 893
 894       phi_gsi = gsi_start_phis (bb);
 895       gsi = gsi_after_labels (bb);
 896
 897       /* BB has two predecessors.  Using predecessor's aux field, set
 898          appropriate condition for the PHI node replacement.  */
 899       if (!gsi_end_p (phi_gsi))
 900         true_bb = find_phi_replacement_condition (loop, bb, &cond, &gsi);
 901
 902       while (!gsi_end_p (phi_gsi))
 903         {
 904           phi = gsi_stmt (phi_gsi);
 905           replace_phi_with_cond_gimple_assign_stmt (phi, cond, true_bb, &gsi);
 906           release_phi_node (phi);
 907           gsi_next (&phi_gsi);
 908         }
 909       set_phi_nodes (bb, NULL);
 910     }
 911   return;
 912 }
 913
 914 /* Combine all the basic blocks from LOOP into one or two super basic
 915    blocks.  Replace PHI nodes with conditional modify expressions.  */
 916
 917 static void
 918 combine_blocks (struct loop *loop)
 919 {
 920   basic_block bb, exit_bb, merge_target_bb;
 921   unsigned int orig_loop_num_nodes = loop->num_nodes;
 922   unsigned int i;
 923   edge e;
 924   edge_iterator ei;
 925
 926   /* Process phi nodes to prepare blocks for merge.  */
 927   process_phi_nodes (loop);
 928
 929   /* Merge basic blocks.  First remove all the edges in the loop, except
 930      for those from the exit block.  */
 931   exit_bb = NULL;
 932   for (i = 0; i < orig_loop_num_nodes; i++)
 933     {
 934       bb = ifc_bbs[i];
 935       if (bb_with_exit_edge_p (loop, bb))
 936         {
 937           exit_bb = bb;
 938           break;
 939         }
 940     }
 941   gcc_assert (exit_bb != loop->latch);
 942
 943   for (i = 1; i < orig_loop_num_nodes; i++)
 944     {
 945       bb = ifc_bbs[i];
 946
 947       for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei));)
 948         {
 949           if (e->src == exit_bb)
 950             ei_next (&ei);
 951           else
 952             remove_edge (e);
 953         }
 954     }
 955
 956   if (exit_bb != NULL)
 957     {
 958       if (exit_bb != loop->header)
 959         {
 960           /* Connect this node with loop header.  */
 961           make_edge (loop->header, exit_bb, EDGE_FALLTHRU);
 962           set_immediate_dominator (CDI_DOMINATORS, exit_bb, loop->header);
 963         }
 964
 965       /* Redirect non-exit edges to loop->latch.  */
 966       FOR_EACH_EDGE (e, ei, exit_bb->succs)
 967         {
 968           if (!loop_exit_edge_p (loop, e))
 969             redirect_edge_and_branch (e, loop->latch);
 970         }
 971       set_immediate_dominator (CDI_DOMINATORS, loop->latch, exit_bb);
 972     }
 973   else
 974     {
 975       /* If the loop does not have exit then reconnect header and latch.  */
 976       make_edge (loop->header, loop->latch, EDGE_FALLTHRU);
 977       set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header);
 978     }
 979
 980   merge_target_bb = loop->header;
 981   for (i = 1; i < orig_loop_num_nodes; i++)
 982     {
 983       gimple_stmt_iterator gsi;
 984       gimple_stmt_iterator last;
 985
 986       bb = ifc_bbs[i];
 987
 988       if (bb == exit_bb || bb == loop->latch)
 989         continue;
 990
 991       /* Remove labels and make stmts member of loop->header.  */
 992       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
 993         {
 994           if (gimple_code (gsi_stmt (gsi)) == GIMPLE_LABEL)
 995             gsi_remove (&gsi, true);
 996           else
 997             {
 998               gimple_set_bb (gsi_stmt (gsi), merge_target_bb);
 999               gsi_next (&gsi);
1000             }
1001         }
1002
1003       /* Update stmt list.  */
1004       last = gsi_last_bb (merge_target_bb);
1005       gsi_insert_seq_after (&last, bb_seq (bb), GSI_NEW_STMT);
1006       set_bb_seq (bb, NULL);
1007
1008       delete_basic_block (bb);
1009     }
1010
1011   /* Now if possible, merge loop header and block with exit edge.
1012      This reduces number of basic blocks to 2.  Auto vectorizer addresses
1013      loops with two nodes only.  FIXME: Use cleanup_tree_cfg().  */
1014   if (exit_bb
1015       && exit_bb != loop->header
1016       && can_merge_blocks_p (loop->header, exit_bb))
1017     merge_blocks (loop->header, exit_bb);
1018 }
1019
1020 /* Main entry point.  Apply if-conversion to the LOOP.  Return true if
1021    successful otherwise return false.  If false is returned then loop
1022    remains unchanged.  */
1023
1024 static bool
1025 tree_if_conversion (struct loop *loop)
1026 {
1027   basic_block bb;
1028   gimple_stmt_iterator itr;
1029   unsigned int i;
1030
1031   ifc_bbs = NULL;
1032
1033   /* If-conversion is not appropriate for all loops.  First, check if
1034      loop is if-convertible or not.  */
1035   if (!if_convertible_loop_p (loop))
1036     {
1037       if (dump_file && (dump_flags & TDF_DETAILS))
1038         fprintf (dump_file,"-------------------------\n");
1039       if (ifc_bbs)
1040         {
1041           free (ifc_bbs);
1042           ifc_bbs = NULL;
1043         }
1044       free_dominance_info (CDI_POST_DOMINATORS);
1045       return false;
1046     }
1047
1048   /* Do actual work now.  */
1049   for (i = 0; i < loop->num_nodes; i++)
1050     {
1051       tree cond;
1052
1053       bb = ifc_bbs [i];
1054
1055       /* Update condition using predicate list.  */
1056       cond = (tree) bb->aux;
1057
1058       /* Process all statements in this basic block.
1059          Remove conditional expression, if any, and annotate
1060          destination basic block(s) appropriately.  */
1061       for (itr = gsi_start_bb (bb); !gsi_end_p (itr); /* empty */)
1062         {
1063           gimple t = gsi_stmt (itr);
1064           cond = tree_if_convert_stmt (loop, t, cond, &itr);
1065           if (!gsi_end_p (itr))
1066             gsi_next (&itr);
1067         }
1068
1069       /* If current bb has only one successor, then consider it as an
1070          unconditional goto.  */
1071       if (single_succ_p (bb))
1072         {
1073           basic_block bb_n = single_succ (bb);
1074
1075           /* Successor bb inherits predicate of its predecessor.  If there
1076              is no predicate in predecessor bb, then consider successor bb
1077              as always executed.  */
1078           if (cond == NULL_TREE)
1079             cond = boolean_true_node;
1080
1081           add_to_predicate_list (bb_n, cond);
1082         }
1083     }
1084
1085   /* Now, all statements are if-converted and basic blocks are
1086      annotated appropriately.  Combine all basic block into one huge
1087      basic block.  */
1088   combine_blocks (loop);
1089
1090   /* clean up */
1091   clean_predicate_lists (loop);
1092   free (ifc_bbs);
1093   ifc_bbs = NULL;
1094
1095   return true;
1096 }
1097
1098 /* Tree if-conversion pass management.  */
1099
1100 static unsigned int
1101 main_tree_if_conversion (void)
1102 {
1103   loop_iterator li;
1104   struct loop *loop;
1105
1106   if (number_of_loops () <= 1)
1107     return 0;
1108
1109   FOR_EACH_LOOP (li, loop, 0)
1110     tree_if_conversion (loop);
1111
1112   return 0;
1113 }
1114
1115 static bool
1116 gate_tree_if_conversion (void)
1117 {
1118   return flag_tree_vectorize != 0;
1119 }
1120
1121 struct gimple_opt_pass pass_if_conversion =
1122 {
1123  {
1124   GIMPLE_PASS,
1125   "ifcvt",                              /* name */
1126   gate_tree_if_conversion,              /* gate */
1127   main_tree_if_conversion,              /* execute */
1128   NULL,                                 /* sub */
1129   NULL,                                 /* next */
1130   0,                                    /* static_pass_number */
1131   TV_NONE,                              /* tv_id */
1132   PROP_cfg | PROP_ssa,                  /* properties_required */
1133   0,                                    /* properties_provided */
1134   0,                                    /* properties_destroyed */
1135   0,                                    /* todo_flags_start */
1136   TODO_dump_func | TODO_verify_stmts | TODO_verify_flow
1137                                         /* todo_flags_finish */
1138  }
1139 };