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.  See above for
 588      more info.
 589    FOR_VECTORIZER enables vectorizer specific checks, for example, support
 590    for vector conditions, data dependency checks, etc.
 591    (Not implemented yet).  */
 592
 593 static bool
 594 if_convertible_loop_p (struct loop *loop, bool for_vectorizer ATTRIBUTE_UNUSED)
 595 {
 596   basic_block bb;
 597   gimple_stmt_iterator itr;
 598   unsigned int i;
 599   edge e;
 600   edge_iterator ei;
 601   basic_block exit_bb = NULL;
 602
 603   /* Handle only inner most loop.  */
 604   if (!loop || loop->inner)
 605     {
 606       if (dump_file && (dump_flags & TDF_DETAILS))
 607         fprintf (dump_file, "not inner most loop\n");
 608       return false;
 609     }
 610
 611   /* If only one block, no need for if-conversion.  */
 612   if (loop->num_nodes <= 2)
 613     {
 614       if (dump_file && (dump_flags & TDF_DETAILS))
 615         fprintf (dump_file, "less than 2 basic blocks\n");
 616       return false;
 617     }
 618
 619   /* More than one loop exit is too much to handle.  */
 620   if (!single_exit (loop))
 621     {
 622       if (dump_file && (dump_flags & TDF_DETAILS))
 623         fprintf (dump_file, "multiple exits\n");
 624       return false;
 625     }
 626
 627   /* ??? Check target's vector conditional operation support for vectorizer.  */
 628
 629   /* If one of the loop header's edge is exit edge then do not apply
 630      if-conversion.  */
 631   FOR_EACH_EDGE (e, ei, loop->header->succs)
 632     {
 633       if (loop_exit_edge_p (loop, e))
 634         return false;
 635     }
 636
 637   calculate_dominance_info (CDI_DOMINATORS);
 638   calculate_dominance_info (CDI_POST_DOMINATORS);
 639
 640   /* Allow statements that can be handled during if-conversion.  */
 641   ifc_bbs = get_loop_body_in_if_conv_order (loop);
 642   if (!ifc_bbs)
 643     {
 644       if (dump_file && (dump_flags & TDF_DETAILS))
 645         fprintf (dump_file,"Irreducible loop\n");
 646       free_dominance_info (CDI_POST_DOMINATORS);
 647       return false;
 648     }
 649
 650   for (i = 0; i < loop->num_nodes; i++)
 651     {
 652       bb = ifc_bbs[i];
 653
 654       if (!if_convertible_bb_p (loop, bb, exit_bb))
 655         return false;
 656
 657       for (itr = gsi_start_bb (bb); !gsi_end_p (itr); gsi_next (&itr))
 658         if (!if_convertible_stmt_p (loop, bb, gsi_stmt (itr)))
 659           return false;
 660
 661       itr = gsi_start_phis (bb);
 662
 663       if (!gsi_end_p (itr))
 664         FOR_EACH_EDGE (e, ei, bb->preds)
 665           e->aux = NULL;
 666
 667       for (; !gsi_end_p (itr); gsi_next (&itr))
 668         if (!if_convertible_phi_p (loop, bb, gsi_stmt (itr)))
 669           return false;
 670
 671       if (bb_with_exit_edge_p (loop, bb))
 672         exit_bb = bb;
 673     }
 674
 675   if (dump_file)
 676     fprintf (dump_file,"Applying if-conversion\n");
 677
 678   free_dominance_info (CDI_POST_DOMINATORS);
 679   return true;
 680 }
 681
 682 /* During if-conversion aux field from basic block structure is used to hold
 683    predicate list.  Clean each basic block's predicate list for the given LOOP.
 684    Also clean aux field of successor edges, used to hold true and false
 685    condition from conditional expression.  */
 686
 687 static void
 688 clean_predicate_lists (struct loop *loop)
 689 {
 690   basic_block *bb;
 691   unsigned int i;
 692   edge e;
 693   edge_iterator ei;
 694
 695   bb = get_loop_body (loop);
 696   for (i = 0; i < loop->num_nodes; i++)
 697     {
 698       bb[i]->aux = NULL;
 699       FOR_EACH_EDGE (e, ei, bb[i]->succs)
 700         e->aux = NULL;
 701     }
 702   free (bb);
 703 }
 704
 705 /* Basic block BB has two predecessors. Using predecessor's aux field, set
 706    appropriate condition COND for the PHI node replacement.  Return true block
 707    whose phi arguments are selected when cond is true.  */
 708
 709 static basic_block
 710 find_phi_replacement_condition (struct loop *loop,
 711                                 basic_block bb, tree *cond,
 712                                 gimple_stmt_iterator *gsi)
 713 {
 714   edge first_edge, second_edge;
 715   tree tmp_cond;
 716
 717   gcc_assert (EDGE_COUNT (bb->preds) == 2);
 718   first_edge = EDGE_PRED (bb, 0);
 719   second_edge = EDGE_PRED (bb, 1);
 720
 721   /* Use condition based on following criteria:
 722      1)
 723        S1: x = !c ? a : b;
 724
 725        S2: x = c ? b : a;
 726
 727        S2 is preferred over S1. Make 'b' first_bb and use its condition.
 728
 729      2) Do not make loop header first_bb.
 730
 731      3)
 732        S1: x = !(c == d)? a : b;
 733
 734        S21: t1 = c == d;
 735        S22: x = t1 ? b : a;
 736
 737        S3: x = (c == d) ? b : a;
 738
 739        S3 is preferred over S1 and S2*, Make 'b' first_bb and use
 740        its condition.
 741
 742      4) If  pred B is dominated by pred A then use pred B's condition.
 743         See PR23115.  */
 744
 745   /* Select condition that is not TRUTH_NOT_EXPR.  */
 746   tmp_cond = (tree) (first_edge->src)->aux;
 747   gcc_assert (tmp_cond);
 748
 749   if (TREE_CODE (tmp_cond) == TRUTH_NOT_EXPR)
 750     {
 751       edge tmp_edge;
 752
 753       tmp_edge = first_edge;
 754       first_edge = second_edge;
 755       second_edge = tmp_edge;
 756     }
 757
 758   /* Check if FIRST_BB is loop header or not and make sure that
 759      FIRST_BB does not dominate SECOND_BB.  */
 760   if (first_edge->src == loop->header
 761       || dominated_by_p (CDI_DOMINATORS,
 762                          second_edge->src, first_edge->src))
 763     {
 764       *cond = (tree) (second_edge->src)->aux;
 765
 766       /* If there is a condition on an incoming edge,
 767          AND it with the incoming bb predicate.  */
 768       if (second_edge->aux)
 769         *cond = build2 (TRUTH_AND_EXPR, boolean_type_node,
 770                         *cond, (tree) second_edge->aux);
 771
 772       if (TREE_CODE (*cond) == TRUTH_NOT_EXPR)
 773         /* We can be smart here and choose inverted
 774            condition without switching bbs.  */
 775         *cond = invert_truthvalue (*cond);
 776       else
 777         /* Select non loop header bb.  */
 778         first_edge = second_edge;
 779     }
 780   else
 781     {
 782       /* FIRST_BB is not loop header */
 783       *cond = (tree) (first_edge->src)->aux;
 784
 785       /* If there is a condition on an incoming edge,
 786          AND it with the incoming bb predicate.  */
 787       if (first_edge->aux)
 788         *cond = build2 (TRUTH_AND_EXPR, boolean_type_node,
 789                         *cond, (tree) first_edge->aux);
 790     }
 791
 792   /* Create temp. for the condition. Vectorizer prefers to have gimple
 793      value as condition. Various targets use different means to communicate
 794      condition in vector compare operation. Using gimple value allows
 795      compiler to emit vector compare and select RTL without exposing
 796      compare's result.  */
 797   *cond = force_gimple_operand_gsi (gsi, unshare_expr (*cond),
 798                                     false, NULL_TREE,
 799                                     true, GSI_SAME_STMT);
 800   if (!is_gimple_reg (*cond) && !is_gimple_condexpr (*cond))
 801     {
 802       gimple new_stmt;
 803
 804       new_stmt = ifc_temp_var (TREE_TYPE (*cond), unshare_expr (*cond));
 805       gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
 806       *cond = gimple_assign_lhs (new_stmt);
 807     }
 808
 809   gcc_assert (*cond);
 810
 811   return first_edge->src;
 812 }
 813
 814
 815 /* Replace PHI node with conditional modify expr using COND.
 816    This routine does not handle PHI nodes with more than two arguments.
 817    For example,
 818      S1: A = PHI <x1(1), x2(5)
 819    is converted into,
 820      S2: A = cond ? x1 : x2;
 821    S2 is inserted at the top of basic block's statement list.
 822    When COND is true, phi arg from TRUE_BB is selected.
 823 */
 824
 825 static void
 826 replace_phi_with_cond_gimple_assign_stmt (gimple phi, tree cond,
 827                                           basic_block true_bb,
 828                                           gimple_stmt_iterator *gsi)
 829 {
 830   gimple new_stmt;
 831   basic_block bb;
 832   tree rhs;
 833   tree arg_0, arg_1;
 834
 835   gcc_assert (gimple_code (phi) == GIMPLE_PHI);
 836
 837   /* If this is not filtered earlier, then now it is too late.  */
 838   gcc_assert (gimple_phi_num_args (phi) == 2);
 839
 840   /* Find basic block and initialize iterator.  */
 841   bb = gimple_bb (phi);
 842
 843   /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr.  */
 844   if (EDGE_PRED (bb, 1)->src == true_bb)
 845     {
 846       arg_0 = gimple_phi_arg_def (phi, 1);
 847       arg_1 = gimple_phi_arg_def (phi, 0);
 848     }
 849   else
 850     {
 851       arg_0 = gimple_phi_arg_def (phi, 0);
 852       arg_1 = gimple_phi_arg_def (phi, 1);
 853     }
 854
 855   /* Build new RHS using selected condition and arguments.  */
 856   rhs = build3 (COND_EXPR, TREE_TYPE (PHI_RESULT (phi)),
 857                 unshare_expr (cond), unshare_expr (arg_0),
 858                 unshare_expr (arg_1));
 859
 860   /* Create new GIMPLE_ASSIGN statement using RHS.  */
 861   new_stmt = gimple_build_assign (unshare_expr (PHI_RESULT (phi)), rhs);
 862
 863   /* Make new statement definition of the original phi result.  */
 864   SSA_NAME_DEF_STMT (gimple_phi_result (phi)) = new_stmt;
 865
 866   /* Insert using iterator.  */
 867   gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
 868   update_stmt (new_stmt);
 869
 870   if (dump_file && (dump_flags & TDF_DETAILS))
 871     {
 872       fprintf (dump_file, "new phi replacement stmt\n");
 873       print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM);
 874     }
 875 }
 876
 877 /* Process phi nodes for the given LOOP.  Replace phi nodes with
 878    conditional modify expressions.  */
 879
 880 static void
 881 process_phi_nodes (struct loop *loop)
 882 {
 883   basic_block bb;
 884   unsigned int orig_loop_num_nodes = loop->num_nodes;
 885   unsigned int i;
 886
 887   for (i = 1; i < orig_loop_num_nodes; i++)
 888     {
 889       gimple phi;
 890       tree cond = NULL_TREE;
 891       gimple_stmt_iterator gsi, phi_gsi;
 892       basic_block true_bb = NULL;
 893       bb = ifc_bbs[i];
 894
 895       if (bb == loop->header)
 896         continue;
 897
 898       phi_gsi = gsi_start_phis (bb);
 899       gsi = gsi_after_labels (bb);
 900
 901       /* BB has two predecessors.  Using predecessor's aux field, set
 902          appropriate condition for the PHI node replacement.  */
 903       if (!gsi_end_p (phi_gsi))
 904         true_bb = find_phi_replacement_condition (loop, bb, &cond, &gsi);
 905
 906       while (!gsi_end_p (phi_gsi))
 907         {
 908           phi = gsi_stmt (phi_gsi);
 909           replace_phi_with_cond_gimple_assign_stmt (phi, cond, true_bb, &gsi);
 910           release_phi_node (phi);
 911           gsi_next (&phi_gsi);
 912         }
 913       set_phi_nodes (bb, NULL);
 914     }
 915   return;
 916 }
 917
 918 /* Combine all the basic blocks from LOOP into one or two super basic
 919    blocks.  Replace PHI nodes with conditional modify expressions.  */
 920
 921 static void
 922 combine_blocks (struct loop *loop)
 923 {
 924   basic_block bb, exit_bb, merge_target_bb;
 925   unsigned int orig_loop_num_nodes = loop->num_nodes;
 926   unsigned int i;
 927   edge e;
 928   edge_iterator ei;
 929
 930   /* Process phi nodes to prepare blocks for merge.  */
 931   process_phi_nodes (loop);
 932
 933   /* Merge basic blocks.  First remove all the edges in the loop, except
 934      for those from the exit block.  */
 935   exit_bb = NULL;
 936   for (i = 0; i < orig_loop_num_nodes; i++)
 937     {
 938       bb = ifc_bbs[i];
 939       if (bb_with_exit_edge_p (loop, bb))
 940         {
 941           exit_bb = bb;
 942           break;
 943         }
 944     }
 945   gcc_assert (exit_bb != loop->latch);
 946
 947   for (i = 1; i < orig_loop_num_nodes; i++)
 948     {
 949       bb = ifc_bbs[i];
 950
 951       for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei));)
 952         {
 953           if (e->src == exit_bb)
 954             ei_next (&ei);
 955           else
 956             remove_edge (e);
 957         }
 958     }
 959
 960   if (exit_bb != NULL)
 961     {
 962       if (exit_bb != loop->header)
 963         {
 964           /* Connect this node with loop header.  */
 965           make_edge (loop->header, exit_bb, EDGE_FALLTHRU);
 966           set_immediate_dominator (CDI_DOMINATORS, exit_bb, loop->header);
 967         }
 968
 969       /* Redirect non-exit edges to loop->latch.  */
 970       FOR_EACH_EDGE (e, ei, exit_bb->succs)
 971         {
 972           if (!loop_exit_edge_p (loop, e))
 973             redirect_edge_and_branch (e, loop->latch);
 974         }
 975       set_immediate_dominator (CDI_DOMINATORS, loop->latch, exit_bb);
 976     }
 977   else
 978     {
 979       /* If the loop does not have exit then reconnect header and latch.  */
 980       make_edge (loop->header, loop->latch, EDGE_FALLTHRU);
 981       set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header);
 982     }
 983
 984   merge_target_bb = loop->header;
 985   for (i = 1; i < orig_loop_num_nodes; i++)
 986     {
 987       gimple_stmt_iterator gsi;
 988       gimple_stmt_iterator last;
 989
 990       bb = ifc_bbs[i];
 991
 992       if (bb == exit_bb || bb == loop->latch)
 993         continue;
 994
 995       /* Remove labels and make stmts member of loop->header.  */
 996       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
 997         {
 998           if (gimple_code (gsi_stmt (gsi)) == GIMPLE_LABEL)
 999             gsi_remove (&gsi, true);
1000           else
1001             {
1002               gimple_set_bb (gsi_stmt (gsi), merge_target_bb);
1003               gsi_next (&gsi);
1004             }
1005         }
1006
1007       /* Update stmt list.  */
1008       last = gsi_last_bb (merge_target_bb);
1009       gsi_insert_seq_after (&last, bb_seq (bb), GSI_NEW_STMT);
1010       set_bb_seq (bb, NULL);
1011
1012       delete_basic_block (bb);
1013     }
1014
1015   /* Now if possible, merge loop header and block with exit edge.
1016      This reduces number of basic blocks to 2.  Auto vectorizer addresses
1017      loops with two nodes only.  FIXME: Use cleanup_tree_cfg().  */
1018   if (exit_bb
1019       && exit_bb != loop->header
1020       && can_merge_blocks_p (loop->header, exit_bb))
1021     merge_blocks (loop->header, exit_bb);
1022 }
1023
1024 /* Main entry point.  Apply if-conversion to the LOOP.  Return true if
1025    successful otherwise return false.  If false is returned then loop
1026    remains unchanged.  FOR_VECTORIZER is a boolean flag.  It indicates
1027    whether if-conversion is used for vectorizer or not.  If it is used
1028    for vectorizer, additional checks are used. (Vectorization checks
1029    are not yet implemented).  */
1030
1031 static bool
1032 tree_if_conversion (struct loop *loop, bool for_vectorizer)
1033 {
1034   basic_block bb;
1035   gimple_stmt_iterator itr;
1036   unsigned int i;
1037
1038   ifc_bbs = NULL;
1039
1040   /* If-conversion is not appropriate for all loops.  First, check if
1041      loop is if-convertible or not.  */
1042   if (!if_convertible_loop_p (loop, for_vectorizer))
1043     {
1044       if (dump_file && (dump_flags & TDF_DETAILS))
1045         fprintf (dump_file,"-------------------------\n");
1046       if (ifc_bbs)
1047         {
1048           free (ifc_bbs);
1049           ifc_bbs = NULL;
1050         }
1051       free_dominance_info (CDI_POST_DOMINATORS);
1052       return false;
1053     }
1054
1055   /* Do actual work now.  */
1056   for (i = 0; i < loop->num_nodes; i++)
1057     {
1058       tree cond;
1059
1060       bb = ifc_bbs [i];
1061
1062       /* Update condition using predicate list.  */
1063       cond = (tree) bb->aux;
1064
1065       /* Process all statements in this basic block.
1066          Remove conditional expression, if any, and annotate
1067          destination basic block(s) appropriately.  */
1068       for (itr = gsi_start_bb (bb); !gsi_end_p (itr); /* empty */)
1069         {
1070           gimple t = gsi_stmt (itr);
1071           cond = tree_if_convert_stmt (loop, t, cond, &itr);
1072           if (!gsi_end_p (itr))
1073             gsi_next (&itr);
1074         }
1075
1076       /* If current bb has only one successor, then consider it as an
1077          unconditional goto.  */
1078       if (single_succ_p (bb))
1079         {
1080           basic_block bb_n = single_succ (bb);
1081
1082           /* Successor bb inherits predicate of its predecessor.  If there
1083              is no predicate in predecessor bb, then consider successor bb
1084              as always executed.  */
1085           if (cond == NULL_TREE)
1086             cond = boolean_true_node;
1087
1088           add_to_predicate_list (bb_n, cond);
1089         }
1090     }
1091
1092   /* Now, all statements are if-converted and basic blocks are
1093      annotated appropriately.  Combine all basic block into one huge
1094      basic block.  */
1095   combine_blocks (loop);
1096
1097   /* clean up */
1098   clean_predicate_lists (loop);
1099   free (ifc_bbs);
1100   ifc_bbs = NULL;
1101
1102   return true;
1103 }
1104
1105 /* Tree if-conversion pass management.  */
1106
1107 static unsigned int
1108 main_tree_if_conversion (void)
1109 {
1110   loop_iterator li;
1111   struct loop *loop;
1112
1113   if (number_of_loops () <= 1)
1114     return 0;
1115
1116   FOR_EACH_LOOP (li, loop, 0)
1117     {
1118       tree_if_conversion (loop, true);
1119     }
1120   return 0;
1121 }
1122
1123 static bool
1124 gate_tree_if_conversion (void)
1125 {
1126   return flag_tree_vectorize != 0;
1127 }
1128
1129 struct gimple_opt_pass pass_if_conversion =
1130 {
1131  {
1132   GIMPLE_PASS,
1133   "ifcvt",                              /* name */
1134   gate_tree_if_conversion,              /* gate */
1135   main_tree_if_conversion,              /* execute */
1136   NULL,                                 /* sub */
1137   NULL,                                 /* next */
1138   0,                                    /* static_pass_number */
1139   TV_NONE,                              /* tv_id */
1140   PROP_cfg | PROP_ssa,                  /* properties_required */
1141   0,                                    /* properties_provided */
1142   0,                                    /* properties_destroyed */
1143   0,                                    /* todo_flags_start */
1144   TODO_dump_func | TODO_verify_stmts | TODO_verify_flow
1145                                         /* todo_flags_finish */
1146  }
1147 };