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