gcc/tree-if-conv.c

   1 /* If-conversion for vectorizer.
   2    Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010
   3    Free Software Foundation, Inc.
   4    Contributed by Devang Patel <dpatel@apple.com>
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 3, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22 /* This pass implements a tree level if-conversion of loops.  Its
  23    initial goal is to help the vectorizer to vectorize loops with
  24    conditions.
  25
  26    A short description of if-conversion:
  27
  28      o Decide if a loop is if-convertible or not.
  29      o Walk all loop basic blocks in breadth first order (BFS order).
  30        o Remove conditional statements (at the end of basic block)
  31          and propagate condition into destination basic blocks'
  32          predicate list.
  33        o Replace modify expression with conditional modify expression
  34          using current basic block's condition.
  35      o Merge all basic blocks
  36        o Replace phi nodes with conditional modify expr
  37        o Merge all basic blocks into header
  38
  39      Sample transformation:
  40
  41      INPUT
  42      -----
  43
  44      # i_23 = PHI <0(0), i_18(10)>;
  45      <L0>:;
  46      j_15 = A[i_23];
  47      if (j_15 > 41) goto <L1>; else goto <L17>;
  48
  49      <L17>:;
  50      goto <bb 3> (<L3>);
  51
  52      <L1>:;
  53
  54      # iftmp.2_4 = PHI <0(8), 42(2)>;
  55      <L3>:;
  56      A[i_23] = iftmp.2_4;
  57      i_18 = i_23 + 1;
  58      if (i_18 <= 15) goto <L19>; else goto <L18>;
  59
  60      <L19>:;
  61      goto <bb 1> (<L0>);
  62
  63      <L18>:;
  64
  65      OUTPUT
  66      ------
  67
  68      # i_23 = PHI <0(0), i_18(10)>;
  69      <L0>:;
  70      j_15 = A[i_23];
  71
  72      <L3>:;
  73      iftmp.2_4 = j_15 > 41 ? 42 : 0;
  74      A[i_23] = iftmp.2_4;
  75      i_18 = i_23 + 1;
  76      if (i_18 <= 15) goto <L19>; else goto <L18>;
  77
  78      <L19>:;
  79      goto <bb 1> (<L0>);
  80
  81      <L18>:;
  82 */
  83
  84 #include "config.h"
  85 #include "system.h"
  86 #include "coretypes.h"
  87 #include "tm.h"
  88 #include "tree.h"
  89 #include "flags.h"
  90 #include "timevar.h"
  91 #include "basic-block.h"
  92 #include "diagnostic.h"
  93 #include "tree-pretty-print.h"
  94 #include "gimple-pretty-print.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
 103 /* List of basic blocks in if-conversion-suitable order.  */
 104 static basic_block *ifc_bbs;
 105
 106 /* Create 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 to the 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 /* Add the 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 COND to the e->aux field.  In case the edge
 179          destination is a PHI node, this condition will be added to
 180          the block predicate to construct a 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 successor edges of BB exits 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
 202   FOR_EACH_EDGE (e, ei, bb->succs)
 203     if (loop_exit_edge_p (loop, e))
 204       return true;
 205
 206   return false;
 207 }
 208
 209 /* STMT is a GIMPLE_COND.  Update two destination's predicate list.
 210    Remove COND_EXPR, if it is not the exit condition of LOOP.
 211    Otherwise update the exit condition of LOOP appropriately.  GSI
 212    points to the statement STMT.  */
 213
 214 static void
 215 tree_if_convert_cond_stmt (struct loop *loop, gimple stmt, tree cond,
 216                            gimple_stmt_iterator *gsi)
 217 {
 218   tree c2;
 219   edge true_edge, false_edge;
 220   location_t loc = gimple_location (stmt);
 221   tree c = fold_build2_loc (loc, gimple_cond_code (stmt), boolean_type_node,
 222                             gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
 223
 224   extract_true_false_edges_from_block (gimple_bb (stmt),
 225                                        &true_edge, &false_edge);
 226
 227   /* Add new condition into destination's predicate list.  */
 228
 229   /* If C is true, then TRUE_EDGE is taken.  */
 230   add_to_dst_predicate_list (loop, true_edge, cond, c, gsi);
 231
 232   /* If C is false, then FALSE_EDGE is taken.  */
 233   c2 = invert_truthvalue_loc (loc, unshare_expr (c));
 234   add_to_dst_predicate_list (loop, false_edge, cond, c2, gsi);
 235
 236   /* Now this conditional statement is redundant.  Remove it.  But, do
 237      not remove the exit condition!  Update the exit condition using
 238      the new condition.  */
 239   if (!bb_with_exit_edge_p (loop, gimple_bb (stmt)))
 240     {
 241       gsi_remove (gsi, true);
 242       cond = NULL_TREE;
 243     }
 244 }
 245
 246 /* If-convert stmt T which is part of LOOP.
 247
 248    If T is a GIMPLE_ASSIGN then it is converted into a conditional
 249    modify expression using COND.  For conditional expressions, add
 250    a condition in the destination basic block's predicate list and
 251    remove the conditional expression itself.  GSI points to the
 252    statement T.  */
 253
 254 static tree
 255 tree_if_convert_stmt (struct loop *loop, gimple t, tree cond,
 256                       gimple_stmt_iterator *gsi)
 257 {
 258   if (dump_file && (dump_flags & TDF_DETAILS))
 259     {
 260       fprintf (dump_file, "------if-convert stmt\n");
 261       print_gimple_stmt (dump_file, t, 0, TDF_SLIM);
 262       print_generic_stmt (dump_file, cond, TDF_SLIM);
 263     }
 264
 265   switch (gimple_code (t))
 266     {
 267       /* Labels are harmless here.  */
 268     case GIMPLE_LABEL:
 269       break;
 270
 271     case GIMPLE_DEBUG:
 272       /* ??? Should there be conditional GIMPLE_DEBUG_BINDs?  */
 273       if (gimple_debug_bind_p (gsi_stmt (*gsi)))
 274         {
 275           gimple_debug_bind_reset_value (gsi_stmt (*gsi));
 276           update_stmt (gsi_stmt (*gsi));
 277         }
 278       break;
 279
 280     case GIMPLE_ASSIGN:
 281       /* This GIMPLE_ASSIGN is killing previous value of LHS.  Appropriate
 282          value will be selected by PHI node based on condition.  It is possible
 283          that before this transformation, PHI nodes was selecting default
 284          value and now it will use this new value.  This is OK because it does
 285          not change the validity of the program.  */
 286       break;
 287
 288     case GIMPLE_COND:
 289       /* Update destination blocks' predicate list and remove this
 290          condition expression.  */
 291       tree_if_convert_cond_stmt (loop, t, cond, gsi);
 292       cond = NULL_TREE;
 293       break;
 294
 295     default:
 296       gcc_unreachable ();
 297     }
 298
 299   return cond;
 300 }
 301
 302 /* Return true when PHI is if-convertible.  PHI is part of loop LOOP
 303    and it belongs to basic block BB.
 304
 305    PHI is not if-convertible if:
 306    - it has more than 2 arguments,
 307    - virtual PHI is immediately used in another PHI node,
 308    - virtual PHI on BB other than header.  */
 309
 310 static bool
 311 if_convertible_phi_p (struct loop *loop, basic_block bb, gimple phi)
 312 {
 313   if (dump_file && (dump_flags & TDF_DETAILS))
 314     {
 315       fprintf (dump_file, "-------------------------\n");
 316       print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
 317     }
 318
 319   if (bb != loop->header && gimple_phi_num_args (phi) != 2)
 320     {
 321       if (dump_file && (dump_flags & TDF_DETAILS))
 322         fprintf (dump_file, "More than two phi node args.\n");
 323       return false;
 324     }
 325
 326   if (!is_gimple_reg (SSA_NAME_VAR (gimple_phi_result (phi))))
 327     {
 328       imm_use_iterator imm_iter;
 329       use_operand_p use_p;
 330
 331       if (bb != loop->header)
 332         {
 333           if (dump_file && (dump_flags & TDF_DETAILS))
 334             fprintf (dump_file, "Virtual phi not on loop header.\n");
 335           return false;
 336         }
 337       FOR_EACH_IMM_USE_FAST (use_p, imm_iter, gimple_phi_result (phi))
 338         {
 339           if (gimple_code (USE_STMT (use_p)) == GIMPLE_PHI)
 340             {
 341               if (dump_file && (dump_flags & TDF_DETAILS))
 342                 fprintf (dump_file, "Difficult to handle this virtual phi.\n");
 343               return false;
 344             }
 345         }
 346     }
 347
 348   return true;
 349 }
 350
 351 /* Return true when STMT is if-convertible.
 352
 353    GIMPLE_ASSIGN statement is not if-convertible if,
 354    - it is not movable,
 355    - it could trap,
 356    - LHS is not var decl.
 357
 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 = gimple_assign_lhs (stmt);
 365
 366   if (dump_file && (dump_flags & TDF_DETAILS))
 367     {
 368       fprintf (dump_file, "-------------------------\n");
 369       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
 370     }
 371
 372   /* Some of these constrains might be too conservative.  */
 373   if (stmt_ends_bb_p (stmt)
 374       || gimple_has_volatile_ops (stmt)
 375       || (TREE_CODE (lhs) == SSA_NAME
 376           && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
 377       || gimple_has_side_effects (stmt))
 378     {
 379       if (dump_file && (dump_flags & TDF_DETAILS))
 380         fprintf (dump_file, "stmt not suitable for ifcvt\n");
 381       return false;
 382     }
 383
 384   /* See if it needs speculative loading or not.  */
 385   if (bb != loop->header
 386       && gimple_assign_rhs_could_trap_p (stmt))
 387     {
 388       if (dump_file && (dump_flags & TDF_DETAILS))
 389         fprintf (dump_file, "tree could trap...\n");
 390       return false;
 391     }
 392
 393   if (TREE_CODE (lhs) != SSA_NAME
 394       && bb != loop->header
 395       && !bb_with_exit_edge_p (loop, bb))
 396     {
 397       if (dump_file && (dump_flags & TDF_DETAILS))
 398         {
 399           fprintf (dump_file, "LHS is not var\n");
 400           print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
 401         }
 402       return false;
 403     }
 404
 405   return true;
 406 }
 407
 408 /* Return true when STMT is if-convertible.
 409
 410    A statement is if-convertible if:
 411    - it is an if-convertible GIMPLE_ASSGIN,
 412    - it is a GIMPLE_LABEL or a GIMPLE_COND.
 413
 414    STMT is inside BB, which is inside loop LOOP.  */
 415
 416 static bool
 417 if_convertible_stmt_p (struct loop *loop, basic_block bb, gimple stmt)
 418 {
 419   switch (gimple_code (stmt))
 420     {
 421     case GIMPLE_LABEL:
 422     case GIMPLE_DEBUG:
 423     case GIMPLE_COND:
 424       return true;
 425
 426     case GIMPLE_ASSIGN:
 427       return if_convertible_gimple_assign_stmt_p (loop, bb, stmt);
 428
 429     default:
 430       /* Don't know what to do with 'em so don't do anything.  */
 431       if (dump_file && (dump_flags & TDF_DETAILS))
 432         {
 433           fprintf (dump_file, "don't know what to do\n");
 434           print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
 435         }
 436       return false;
 437       break;
 438     }
 439
 440   return true;
 441 }
 442
 443 /* Return true when BB is if-convertible.  This routine does not check
 444    basic block's statements and phis.
 445
 446    A basic block is not if-convertible if:
 447    - it is non-empty and it is after the exit block (in BFS order),
 448    - it is after the exit block but before the latch,
 449    - its edges are not normal.
 450
 451    EXIT_BB is the basic block containing the exit of the LOOP.  BB is
 452    inside LOOP.  */
 453
 454 static bool
 455 if_convertible_bb_p (struct loop *loop, basic_block bb, basic_block exit_bb)
 456 {
 457   edge e;
 458   edge_iterator ei;
 459
 460   if (dump_file && (dump_flags & TDF_DETAILS))
 461     fprintf (dump_file, "----------[%d]-------------\n", bb->index);
 462
 463   if (exit_bb)
 464     {
 465       if (bb != loop->latch)
 466         {
 467           if (dump_file && (dump_flags & TDF_DETAILS))
 468             fprintf (dump_file, "basic block after exit bb but before latch\n");
 469           return false;
 470         }
 471       else if (!empty_block_p (bb))
 472         {
 473           if (dump_file && (dump_flags & TDF_DETAILS))
 474             fprintf (dump_file, "non empty basic block after exit bb\n");
 475           return false;
 476         }
 477       else if (bb == loop->latch
 478                && bb != exit_bb
 479                && !dominated_by_p (CDI_DOMINATORS, bb, exit_bb))
 480           {
 481             if (dump_file && (dump_flags & TDF_DETAILS))
 482               fprintf (dump_file, "latch is not dominated by exit_block\n");
 483             return false;
 484           }
 485     }
 486
 487   /* Be less adventurous and handle only normal edges.  */
 488   FOR_EACH_EDGE (e, ei, bb->succs)
 489     if (e->flags &
 490         (EDGE_ABNORMAL_CALL | EDGE_EH | EDGE_ABNORMAL | EDGE_IRREDUCIBLE_LOOP))
 491       {
 492         if (dump_file && (dump_flags & TDF_DETAILS))
 493           fprintf (dump_file, "Difficult to handle edges\n");
 494         return false;
 495       }
 496
 497   return true;
 498 }
 499
 500 /* Return true when all predecessor blocks of BB are visited.  The
 501    VISITED bitmap keeps track of the visited blocks.  */
 502
 503 static bool
 504 pred_blocks_visited_p (basic_block bb, bitmap *visited)
 505 {
 506   edge e;
 507   edge_iterator ei;
 508   FOR_EACH_EDGE (e, ei, bb->preds)
 509     if (!bitmap_bit_p (*visited, e->src->index))
 510       return false;
 511
 512   return true;
 513 }
 514
 515 /* Get body of a LOOP in suitable order for if-conversion.  It is
 516    caller's responsibility to deallocate basic block list.
 517    If-conversion suitable order is, breadth first sort (BFS) order
 518    with an additional constraint: select a block only if all its
 519    predecessors are already selected.  */
 520
 521 static basic_block *
 522 get_loop_body_in_if_conv_order (const struct loop *loop)
 523 {
 524   basic_block *blocks, *blocks_in_bfs_order;
 525   basic_block bb;
 526   bitmap visited;
 527   unsigned int index = 0;
 528   unsigned int visited_count = 0;
 529
 530   gcc_assert (loop->num_nodes);
 531   gcc_assert (loop->latch != EXIT_BLOCK_PTR);
 532
 533   blocks = XCNEWVEC (basic_block, loop->num_nodes);
 534   visited = BITMAP_ALLOC (NULL);
 535
 536   blocks_in_bfs_order = get_loop_body_in_bfs_order (loop);
 537
 538   index = 0;
 539   while (index < loop->num_nodes)
 540     {
 541       bb = blocks_in_bfs_order [index];
 542
 543       if (bb->flags & BB_IRREDUCIBLE_LOOP)
 544         {
 545           free (blocks_in_bfs_order);
 546           BITMAP_FREE (visited);
 547           free (blocks);
 548           return NULL;
 549         }
 550
 551       if (!bitmap_bit_p (visited, bb->index))
 552         {
 553           if (pred_blocks_visited_p (bb, &visited)
 554               || bb == loop->header)
 555             {
 556               /* This block is now visited.  */
 557               bitmap_set_bit (visited, bb->index);
 558               blocks[visited_count++] = bb;
 559             }
 560         }
 561
 562       index++;
 563
 564       if (index == loop->num_nodes
 565           && visited_count != loop->num_nodes)
 566         /* Not done yet.  */
 567         index = 0;
 568     }
 569   free (blocks_in_bfs_order);
 570   BITMAP_FREE (visited);
 571   return blocks;
 572 }
 573
 574 /* Return true when LOOP is if-convertible.
 575    LOOP is if-convertible if:
 576    - it is innermost,
 577    - it has two or more basic blocks,
 578    - it has only one exit,
 579    - loop header is not the exit edge,
 580    - if its basic blocks and phi nodes are if convertible.  */
 581
 582 static bool
 583 if_convertible_loop_p (struct loop *loop)
 584 {
 585   basic_block bb;
 586   gimple_stmt_iterator itr;
 587   unsigned int i;
 588   edge e;
 589   edge_iterator ei;
 590   basic_block exit_bb = NULL;
 591
 592   /* Handle only innermost loop.  */
 593   if (!loop || loop->inner)
 594     {
 595       if (dump_file && (dump_flags & TDF_DETAILS))
 596         fprintf (dump_file, "not innermost loop\n");
 597       return false;
 598     }
 599
 600   /* If only one block, no need for if-conversion.  */
 601   if (loop->num_nodes <= 2)
 602     {
 603       if (dump_file && (dump_flags & TDF_DETAILS))
 604         fprintf (dump_file, "less than 2 basic blocks\n");
 605       return false;
 606     }
 607
 608   /* More than one loop exit is too much to handle.  */
 609   if (!single_exit (loop))
 610     {
 611       if (dump_file && (dump_flags & TDF_DETAILS))
 612         fprintf (dump_file, "multiple exits\n");
 613       return false;
 614     }
 615
 616   /* ??? Check target's vector conditional operation support for vectorizer.  */
 617
 618   /* If one of the loop header's edge is exit edge then do not apply
 619      if-conversion.  */
 620   FOR_EACH_EDGE (e, ei, loop->header->succs)
 621     {
 622       if (loop_exit_edge_p (loop, e))
 623         return false;
 624     }
 625
 626   calculate_dominance_info (CDI_DOMINATORS);
 627
 628   /* Allow statements that can be handled during if-conversion.  */
 629   ifc_bbs = get_loop_body_in_if_conv_order (loop);
 630   if (!ifc_bbs)
 631     {
 632       if (dump_file && (dump_flags & TDF_DETAILS))
 633         fprintf (dump_file, "Irreducible loop\n");
 634       return false;
 635     }
 636
 637   for (i = 0; i < loop->num_nodes; i++)
 638     {
 639       bb = ifc_bbs[i];
 640
 641       if (!if_convertible_bb_p (loop, bb, exit_bb))
 642         return false;
 643
 644       for (itr = gsi_start_bb (bb); !gsi_end_p (itr); gsi_next (&itr))
 645         if (!if_convertible_stmt_p (loop, bb, gsi_stmt (itr)))
 646           return false;
 647
 648       itr = gsi_start_phis (bb);
 649
 650       if (!gsi_end_p (itr))
 651         FOR_EACH_EDGE (e, ei, bb->preds)
 652           e->aux = NULL;
 653
 654       for (; !gsi_end_p (itr); gsi_next (&itr))
 655         if (!if_convertible_phi_p (loop, bb, gsi_stmt (itr)))
 656           return false;
 657
 658       if (bb_with_exit_edge_p (loop, bb))
 659         exit_bb = bb;
 660     }
 661
 662   if (dump_file)
 663     fprintf (dump_file, "Applying if-conversion\n");
 664
 665   return true;
 666 }
 667
 668 /* During if-conversion, the bb->aux field is used to hold a predicate
 669    list.  This function cleans for all the basic blocks in the given
 670    LOOP their predicate list.  It also cleans up the e->aux field of
 671    all the successor edges: e->aux is used to hold the true and false
 672    conditions for conditional expressions.  */
 673
 674 static void
 675 clean_predicate_lists (struct loop *loop)
 676 {
 677   basic_block *bb;
 678   unsigned int i;
 679   edge e;
 680   edge_iterator ei;
 681
 682   bb = get_loop_body (loop);
 683   for (i = 0; i < loop->num_nodes; i++)
 684     {
 685       bb[i]->aux = NULL;
 686       FOR_EACH_EDGE (e, ei, bb[i]->succs)
 687         e->aux = NULL;
 688     }
 689   free (bb);
 690 }
 691
 692 /* Basic block BB has two predecessors.  Using predecessor's bb->aux
 693    field, set appropriate condition COND for the PHI node replacement.
 694    Return true block whose phi arguments are selected when cond is
 695    true.  LOOP is the loop containing the if-converted region, GSI is
 696    the place to insert the code for the if-conversion.  */
 697
 698 static basic_block
 699 find_phi_replacement_condition (struct loop *loop,
 700                                 basic_block bb, tree *cond,
 701                                 gimple_stmt_iterator *gsi)
 702 {
 703   edge first_edge, second_edge;
 704   tree tmp_cond;
 705
 706   gcc_assert (EDGE_COUNT (bb->preds) == 2);
 707   first_edge = EDGE_PRED (bb, 0);
 708   second_edge = EDGE_PRED (bb, 1);
 709
 710   /* Use condition based on following criteria:
 711      1)
 712        S1: x = !c ? a : b;
 713
 714        S2: x = c ? b : a;
 715
 716        S2 is preferred over S1. Make 'b' first_bb and use its condition.
 717
 718      2) Do not make loop header first_bb.
 719
 720      3)
 721        S1: x = !(c == d)? a : b;
 722
 723        S21: t1 = c == d;
 724        S22: x = t1 ? b : a;
 725
 726        S3: x = (c == d) ? b : a;
 727
 728        S3 is preferred over S1 and S2*, Make 'b' first_bb and use
 729        its condition.
 730
 731      4) If  pred B is dominated by pred A then use pred B's condition.
 732         See PR23115.  */
 733
 734   /* Select condition that is not TRUTH_NOT_EXPR.  */
 735   tmp_cond = (tree) (first_edge->src)->aux;
 736   gcc_assert (tmp_cond);
 737
 738   if (TREE_CODE (tmp_cond) == TRUTH_NOT_EXPR)
 739     {
 740       edge tmp_edge;
 741
 742       tmp_edge = first_edge;
 743       first_edge = second_edge;
 744       second_edge = tmp_edge;
 745     }
 746
 747   /* Check if FIRST_BB is loop header or not and make sure that
 748      FIRST_BB does not dominate SECOND_BB.  */
 749   if (first_edge->src == loop->header
 750       || dominated_by_p (CDI_DOMINATORS,
 751                          second_edge->src, first_edge->src))
 752     {
 753       *cond = (tree) (second_edge->src)->aux;
 754
 755       /* If there is a condition on an incoming edge, add it to the
 756          incoming bb predicate.  */
 757       if (second_edge->aux)
 758         *cond = build2 (TRUTH_AND_EXPR, boolean_type_node,
 759                         *cond, (tree) second_edge->aux);
 760
 761       if (TREE_CODE (*cond) == TRUTH_NOT_EXPR)
 762         *cond = invert_truthvalue (*cond);
 763       else
 764         /* Select non loop header bb.  */
 765         first_edge = second_edge;
 766     }
 767   else
 768     {
 769       *cond = (tree) (first_edge->src)->aux;
 770
 771       /* If there is a condition on an incoming edge, add it to the
 772          incoming bb predicate.  */
 773       if (first_edge->aux)
 774         *cond = build2 (TRUTH_AND_EXPR, boolean_type_node,
 775                         *cond, (tree) first_edge->aux);
 776     }
 777
 778   /* Gimplify the condition: the vectorizer prefers to have gimple
 779      values as conditions.  Various targets use different means to
 780      communicate conditions in vector compare operations.  Using a
 781      gimple value allows the compiler to emit vector compare and
 782      select RTL without exposing compare's result.  */
 783   *cond = force_gimple_operand_gsi (gsi, unshare_expr (*cond),
 784                                     false, NULL_TREE,
 785                                     true, GSI_SAME_STMT);
 786   if (!is_gimple_reg (*cond) && !is_gimple_condexpr (*cond))
 787     {
 788       gimple new_stmt;
 789
 790       new_stmt = ifc_temp_var (TREE_TYPE (*cond), unshare_expr (*cond));
 791       gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
 792       *cond = gimple_assign_lhs (new_stmt);
 793     }
 794
 795   gcc_assert (*cond);
 796
 797   return first_edge->src;
 798 }
 799
 800 /* Replace PHI node with conditional modify expr using COND.  This
 801    routine does not handle PHI nodes with more than two arguments.
 802
 803    For example,
 804      S1: A = PHI <x1(1), x2(5)
 805    is converted into,
 806      S2: A = cond ? x1 : x2;
 807
 808    The generated code is inserted at GSI that points to the top of
 809    basic block's statement list.  When COND is true, phi arg from
 810    TRUE_BB is selected.  */
 811
 812 static void
 813 replace_phi_with_cond_gimple_assign_stmt (gimple phi, tree cond,
 814                                           basic_block true_bb,
 815                                           gimple_stmt_iterator *gsi)
 816 {
 817   gimple new_stmt;
 818   basic_block bb;
 819   tree rhs;
 820   tree arg_0, arg_1;
 821
 822   gcc_assert (gimple_code (phi) == GIMPLE_PHI
 823               && gimple_phi_num_args (phi) == 2);
 824
 825   bb = gimple_bb (phi);
 826
 827   /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr.  */
 828   if (EDGE_PRED (bb, 1)->src == true_bb)
 829     {
 830       arg_0 = gimple_phi_arg_def (phi, 1);
 831       arg_1 = gimple_phi_arg_def (phi, 0);
 832     }
 833   else
 834     {
 835       arg_0 = gimple_phi_arg_def (phi, 0);
 836       arg_1 = gimple_phi_arg_def (phi, 1);
 837     }
 838
 839   /* Build new RHS using selected condition and arguments.  */
 840   rhs = build3 (COND_EXPR, TREE_TYPE (PHI_RESULT (phi)),
 841                 unshare_expr (cond), unshare_expr (arg_0),
 842                 unshare_expr (arg_1));
 843
 844   new_stmt = gimple_build_assign (unshare_expr (PHI_RESULT (phi)), rhs);
 845   SSA_NAME_DEF_STMT (gimple_phi_result (phi)) = new_stmt;
 846   gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
 847   update_stmt (new_stmt);
 848
 849   if (dump_file && (dump_flags & TDF_DETAILS))
 850     {
 851       fprintf (dump_file, "new phi replacement stmt\n");
 852       print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM);
 853     }
 854 }
 855
 856 /* Process phi nodes for the given LOOP.  Replace phi nodes with
 857    conditional modify expressions.  */
 858
 859 static void
 860 process_phi_nodes (struct loop *loop)
 861 {
 862   basic_block bb;
 863   unsigned int orig_loop_num_nodes = loop->num_nodes;
 864   unsigned int i;
 865
 866   for (i = 1; i < orig_loop_num_nodes; i++)
 867     {
 868       gimple phi;
 869       tree cond = NULL_TREE;
 870       gimple_stmt_iterator gsi, phi_gsi;
 871       basic_block true_bb = NULL;
 872       bb = ifc_bbs[i];
 873
 874       if (bb == loop->header)
 875         continue;
 876
 877       phi_gsi = gsi_start_phis (bb);
 878       gsi = gsi_after_labels (bb);
 879
 880       /* BB has two predecessors.  Using predecessor's aux field, set
 881          appropriate condition for the PHI node replacement.  */
 882       if (!gsi_end_p (phi_gsi))
 883         true_bb = find_phi_replacement_condition (loop, bb, &cond, &gsi);
 884
 885       while (!gsi_end_p (phi_gsi))
 886         {
 887           phi = gsi_stmt (phi_gsi);
 888           replace_phi_with_cond_gimple_assign_stmt (phi, cond, true_bb, &gsi);
 889           release_phi_node (phi);
 890           gsi_next (&phi_gsi);
 891         }
 892       set_phi_nodes (bb, NULL);
 893     }
 894 }
 895
 896 /* Combine all the basic blocks from LOOP into one or two super basic
 897    blocks.  Replace PHI nodes with conditional modify expressions.  */
 898
 899 static void
 900 combine_blocks (struct loop *loop)
 901 {
 902   basic_block bb, exit_bb, merge_target_bb;
 903   unsigned int orig_loop_num_nodes = loop->num_nodes;
 904   unsigned int i;
 905   edge e;
 906   edge_iterator ei;
 907
 908   /* Process phi nodes to prepare blocks for merge.  */
 909   process_phi_nodes (loop);
 910
 911   /* Merge basic blocks: first remove all the edges in the loop,
 912      except for those from the exit block.  */
 913   exit_bb = NULL;
 914   for (i = 0; i < orig_loop_num_nodes; i++)
 915     {
 916       bb = ifc_bbs[i];
 917       if (bb_with_exit_edge_p (loop, bb))
 918         {
 919           exit_bb = bb;
 920           break;
 921         }
 922     }
 923   gcc_assert (exit_bb != loop->latch);
 924
 925   for (i = 1; i < orig_loop_num_nodes; i++)
 926     {
 927       bb = ifc_bbs[i];
 928
 929       for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei));)
 930         {
 931           if (e->src == exit_bb)
 932             ei_next (&ei);
 933           else
 934             remove_edge (e);
 935         }
 936     }
 937
 938   if (exit_bb != NULL)
 939     {
 940       if (exit_bb != loop->header)
 941         {
 942           /* Connect this node to loop header.  */
 943           make_edge (loop->header, exit_bb, EDGE_FALLTHRU);
 944           set_immediate_dominator (CDI_DOMINATORS, exit_bb, loop->header);
 945         }
 946
 947       /* Redirect non-exit edges to loop->latch.  */
 948       FOR_EACH_EDGE (e, ei, exit_bb->succs)
 949         {
 950           if (!loop_exit_edge_p (loop, e))
 951             redirect_edge_and_branch (e, loop->latch);
 952         }
 953       set_immediate_dominator (CDI_DOMINATORS, loop->latch, exit_bb);
 954     }
 955   else
 956     {
 957       /* If the loop does not have an exit, reconnect header and latch.  */
 958       make_edge (loop->header, loop->latch, EDGE_FALLTHRU);
 959       set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header);
 960     }
 961
 962   merge_target_bb = loop->header;
 963   for (i = 1; i < orig_loop_num_nodes; i++)
 964     {
 965       gimple_stmt_iterator gsi;
 966       gimple_stmt_iterator last;
 967
 968       bb = ifc_bbs[i];
 969
 970       if (bb == exit_bb || bb == loop->latch)
 971         continue;
 972
 973       /* Remove labels and make stmts member of loop->header.  */
 974       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
 975         {
 976           if (gimple_code (gsi_stmt (gsi)) == GIMPLE_LABEL)
 977             gsi_remove (&gsi, true);
 978           else
 979             {
 980               gimple_set_bb (gsi_stmt (gsi), merge_target_bb);
 981               gsi_next (&gsi);
 982             }
 983         }
 984
 985       /* Update stmt list.  */
 986       last = gsi_last_bb (merge_target_bb);
 987       gsi_insert_seq_after (&last, bb_seq (bb), GSI_NEW_STMT);
 988       set_bb_seq (bb, NULL);
 989
 990       delete_basic_block (bb);
 991     }
 992
 993   /* If possible, merge loop header to the block with the exit edge.
 994      This reduces the number of basic blocks to two, to please the
 995      vectorizer that handles only loops with two nodes.
 996
 997      FIXME: Call cleanup_tree_cfg.  */
 998   if (exit_bb
 999       && exit_bb != loop->header
1000       && can_merge_blocks_p (loop->header, exit_bb))
1001     merge_blocks (loop->header, exit_bb);
1002 }
1003
1004 /* If-convert LOOP when it is legal.  For the moment this pass has no
1005    profitability analysis.  */
1006
1007 static void
1008 tree_if_conversion (struct loop *loop)
1009 {
1010   gimple_stmt_iterator itr;
1011   unsigned int i;
1012
1013   ifc_bbs = NULL;
1014
1015   /* If-conversion is not appropriate for all loops.  First, check if
1016      the loop is if-convertible.  */
1017   if (!if_convertible_loop_p (loop))
1018     {
1019       if (dump_file && (dump_flags & TDF_DETAILS))
1020         fprintf (dump_file, "-------------------------\n");
1021       if (ifc_bbs)
1022         {
1023           free (ifc_bbs);
1024           ifc_bbs = NULL;
1025         }
1026       return;
1027     }
1028
1029   for (i = 0; i < loop->num_nodes; i++)
1030     {
1031       basic_block bb = ifc_bbs [i];
1032       tree cond = (tree) bb->aux;
1033
1034       /* Process all the statements in this basic block.
1035          Remove conditional expression, if any, and annotate
1036          destination basic block(s) appropriately.  */
1037       for (itr = gsi_start_bb (bb); !gsi_end_p (itr); /* empty */)
1038         {
1039           gimple t = gsi_stmt (itr);
1040           cond = tree_if_convert_stmt (loop, t, cond, &itr);
1041           if (!gsi_end_p (itr))
1042             gsi_next (&itr);
1043         }
1044
1045       /* If current bb has only one successor, then consider it as an
1046          unconditional goto.  */
1047       if (single_succ_p (bb))
1048         {
1049           basic_block bb_n = single_succ (bb);
1050
1051           /* The successor bb inherits the predicate of its
1052              predecessor.  If there is no predicate in the predecessor
1053              bb, then consider the successor bb as always executed.  */
1054           if (cond == NULL_TREE)
1055             cond = boolean_true_node;
1056
1057           add_to_predicate_list (bb_n, cond);
1058         }
1059     }
1060
1061   /* Now, all statements are if-converted and basic blocks are
1062      annotated appropriately.  Combine all the basic blocks into one
1063      huge basic block.  */
1064   combine_blocks (loop);
1065
1066   /* clean up */
1067   clean_predicate_lists (loop);
1068   free (ifc_bbs);
1069   ifc_bbs = NULL;
1070 }
1071
1072 /* Tree if-conversion pass management.  */
1073
1074 static unsigned int
1075 main_tree_if_conversion (void)
1076 {
1077   loop_iterator li;
1078   struct loop *loop;
1079
1080   if (number_of_loops () <= 1)
1081     return 0;
1082
1083   FOR_EACH_LOOP (li, loop, 0)
1084     tree_if_conversion (loop);
1085
1086   return 0;
1087 }
1088
1089 static bool
1090 gate_tree_if_conversion (void)
1091 {
1092   return flag_tree_vectorize != 0;
1093 }
1094
1095 struct gimple_opt_pass pass_if_conversion =
1096 {
1097  {
1098   GIMPLE_PASS,
1099   "ifcvt",                              /* name */
1100   gate_tree_if_conversion,              /* gate */
1101   main_tree_if_conversion,              /* execute */
1102   NULL,                                 /* sub */
1103   NULL,                                 /* next */
1104   0,                                    /* static_pass_number */
1105   TV_NONE,                              /* tv_id */
1106   PROP_cfg | PROP_ssa,                  /* properties_required */
1107   0,                                    /* properties_provided */
1108   0,                                    /* properties_destroyed */
1109   0,                                    /* todo_flags_start */
1110   TODO_dump_func | TODO_verify_stmts | TODO_verify_flow
1111                                         /* todo_flags_finish */
1112  }
1113 };