gcc/tree-if-conv.c

   1 /* If-conversion for vectorizer.
   2    Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009
   3    Free Software Foundation, Inc.
   4    Contributed by Devang Patel <dpatel@apple.com>
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 3, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22 /* This pass implements a tree level if-conversion of loops.  Its
  23    initial goal is to help the vectorizer to vectorize loops with
  24    conditions.
  25
  26    A short description of if-conversion:
  27
  28      o Decide if a loop is if-convertible or not.
  29      o Walk all loop basic blocks in breadth first order (BFS order).
  30        o Remove conditional statements (at the end of basic block)
  31          and propagate condition into destination basic blocks'
  32          predicate list.
  33        o Replace modify expression with conditional modify expression
  34          using current basic block's condition.
  35      o Merge all basic blocks
  36        o Replace phi nodes with conditional modify expr
  37        o Merge all basic blocks into header
  38
  39      Sample transformation:
  40
  41      INPUT
  42      -----
  43
  44      # i_23 = PHI <0(0), i_18(10)>;
  45      <L0>:;
  46      j_15 = A[i_23];
  47      if (j_15 > 41) goto <L1>; else goto <L17>;
  48
  49      <L17>:;
  50      goto <bb 3> (<L3>);
  51
  52      <L1>:;
  53
  54      # iftmp.2_4 = PHI <0(8), 42(2)>;
  55      <L3>:;
  56      A[i_23] = iftmp.2_4;
  57      i_18 = i_23 + 1;
  58      if (i_18 <= 15) goto <L19>; else goto <L18>;
  59
  60      <L19>:;
  61      goto <bb 1> (<L0>);
  62
  63      <L18>:;
  64
  65      OUTPUT
  66      ------
  67
  68      # i_23 = PHI <0(0), i_18(10)>;
  69      <L0>:;
  70      j_15 = A[i_23];
  71
  72      <L3>:;
  73      iftmp.2_4 = j_15 > 41 ? 42 : 0;
  74      A[i_23] = iftmp.2_4;
  75      i_18 = i_23 + 1;
  76      if (i_18 <= 15) goto <L19>; else goto <L18>;
  77
  78      <L19>:;
  79      goto <bb 1> (<L0>);
  80
  81      <L18>:;
  82 */
  83
  84 #include "config.h"
  85 #include "system.h"
  86 #include "coretypes.h"
  87 #include "tm.h"
  88 #include "tree.h"
  89 #include "flags.h"
  90 #include "timevar.h"
  91 #include "rtl.h"
  92 #include "basic-block.h"
  93 #include "diagnostic.h"
  94 #include "tree-flow.h"
  95 #include "tree-dump.h"
  96 #include "cfgloop.h"
  97 #include "tree-chrec.h"
  98 #include "tree-data-ref.h"
  99 #include "tree-scalar-evolution.h"
 100 #include "tree-pass.h"
 101 #include "target.h"
 102
 103 /* List of basic blocks in if-conversion-suitable order.  */
 104 static basic_block *ifc_bbs;
 105
 106 /* 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 inner most loop.  */
 593   if (!loop || loop->inner)
 594     {
 595       if (dump_file && (dump_flags & TDF_DETAILS))
 596         fprintf (dump_file, "not inner most 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   calculate_dominance_info (CDI_POST_DOMINATORS);
 628
 629   /* Allow statements that can be handled during if-conversion.  */
 630   ifc_bbs = get_loop_body_in_if_conv_order (loop);
 631   if (!ifc_bbs)
 632     {
 633       if (dump_file && (dump_flags & TDF_DETAILS))
 634         fprintf (dump_file,"Irreducible loop\n");
 635       free_dominance_info (CDI_POST_DOMINATORS);
 636       return false;
 637     }
 638
 639   for (i = 0; i < loop->num_nodes; i++)
 640     {
 641       bb = ifc_bbs[i];
 642
 643       if (!if_convertible_bb_p (loop, bb, exit_bb))
 644         return false;
 645
 646       for (itr = gsi_start_bb (bb); !gsi_end_p (itr); gsi_next (&itr))
 647         if (!if_convertible_stmt_p (loop, bb, gsi_stmt (itr)))
 648           return false;
 649
 650       itr = gsi_start_phis (bb);
 651
 652       if (!gsi_end_p (itr))
 653         FOR_EACH_EDGE (e, ei, bb->preds)
 654           e->aux = NULL;
 655
 656       for (; !gsi_end_p (itr); gsi_next (&itr))
 657         if (!if_convertible_phi_p (loop, bb, gsi_stmt (itr)))
 658           return false;
 659
 660       if (bb_with_exit_edge_p (loop, bb))
 661         exit_bb = bb;
 662     }
 663
 664   if (dump_file)
 665     fprintf (dump_file,"Applying if-conversion\n");
 666
 667   free_dominance_info (CDI_POST_DOMINATORS);
 668   return true;
 669 }
 670
 671 /* During if-conversion, the bb->aux field is used to hold a predicate
 672    list.  This function cleans for all the basic blocks in the given
 673    LOOP their predicate list.  It also cleans up the e->aux field of
 674    all the successor edges: e->aux is used to hold the true and false
 675    conditions for conditional expressions.  */
 676
 677 static void
 678 clean_predicate_lists (struct loop *loop)
 679 {
 680   basic_block *bb;
 681   unsigned int i;
 682   edge e;
 683   edge_iterator ei;
 684
 685   bb = get_loop_body (loop);
 686   for (i = 0; i < loop->num_nodes; i++)
 687     {
 688       bb[i]->aux = NULL;
 689       FOR_EACH_EDGE (e, ei, bb[i]->succs)
 690         e->aux = NULL;
 691     }
 692   free (bb);
 693 }
 694
 695 /* Basic block BB has two predecessors.  Using predecessor's bb->aux
 696    field, set appropriate condition COND for the PHI node replacement.
 697    Return true block whose phi arguments are selected when cond is
 698    true.  LOOP is the loop containing the if-converted region, GSI is
 699    the place to insert the code for the if-conversion.  */
 700
 701 static basic_block
 702 find_phi_replacement_condition (struct loop *loop,
 703                                 basic_block bb, tree *cond,
 704                                 gimple_stmt_iterator *gsi)
 705 {
 706   edge first_edge, second_edge;
 707   tree tmp_cond;
 708
 709   gcc_assert (EDGE_COUNT (bb->preds) == 2);
 710   first_edge = EDGE_PRED (bb, 0);
 711   second_edge = EDGE_PRED (bb, 1);
 712
 713   /* Use condition based on following criteria:
 714      1)
 715        S1: x = !c ? a : b;
 716
 717        S2: x = c ? b : a;
 718
 719        S2 is preferred over S1. Make 'b' first_bb and use its condition.
 720
 721      2) Do not make loop header first_bb.
 722
 723      3)
 724        S1: x = !(c == d)? a : b;
 725
 726        S21: t1 = c == d;
 727        S22: x = t1 ? b : a;
 728
 729        S3: x = (c == d) ? b : a;
 730
 731        S3 is preferred over S1 and S2*, Make 'b' first_bb and use
 732        its condition.
 733
 734      4) If  pred B is dominated by pred A then use pred B's condition.
 735         See PR23115.  */
 736
 737   /* Select condition that is not TRUTH_NOT_EXPR.  */
 738   tmp_cond = (tree) (first_edge->src)->aux;
 739   gcc_assert (tmp_cond);
 740
 741   if (TREE_CODE (tmp_cond) == TRUTH_NOT_EXPR)
 742     {
 743       edge tmp_edge;
 744
 745       tmp_edge = first_edge;
 746       first_edge = second_edge;
 747       second_edge = tmp_edge;
 748     }
 749
 750   /* Check if FIRST_BB is loop header or not and make sure that
 751      FIRST_BB does not dominate SECOND_BB.  */
 752   if (first_edge->src == loop->header
 753       || dominated_by_p (CDI_DOMINATORS,
 754                          second_edge->src, first_edge->src))
 755     {
 756       *cond = (tree) (second_edge->src)->aux;
 757
 758       /* If there is a condition on an incoming edge, add it to the
 759          incoming bb predicate.  */
 760       if (second_edge->aux)
 761         *cond = build2 (TRUTH_AND_EXPR, boolean_type_node,
 762                         *cond, (tree) second_edge->aux);
 763
 764       if (TREE_CODE (*cond) == TRUTH_NOT_EXPR)
 765         *cond = invert_truthvalue (*cond);
 766       else
 767         /* Select non loop header bb.  */
 768         first_edge = second_edge;
 769     }
 770   else
 771     {
 772       *cond = (tree) (first_edge->src)->aux;
 773
 774       /* If there is a condition on an incoming edge, add it to the
 775          incoming bb predicate.  */
 776       if (first_edge->aux)
 777         *cond = build2 (TRUTH_AND_EXPR, boolean_type_node,
 778                         *cond, (tree) first_edge->aux);
 779     }
 780
 781   /* Gimplify the condition: the vectorizer prefers to have gimple
 782      values as conditions.  Various targets use different means to
 783      communicate conditions in vector compare operations.  Using a
 784      gimple value allows the compiler to emit vector compare and
 785      select RTL without exposing compare's result.  */
 786   *cond = force_gimple_operand_gsi (gsi, unshare_expr (*cond),
 787                                     false, NULL_TREE,
 788                                     true, GSI_SAME_STMT);
 789   if (!is_gimple_reg (*cond) && !is_gimple_condexpr (*cond))
 790     {
 791       gimple new_stmt;
 792
 793       new_stmt = ifc_temp_var (TREE_TYPE (*cond), unshare_expr (*cond));
 794       gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
 795       *cond = gimple_assign_lhs (new_stmt);
 796     }
 797
 798   gcc_assert (*cond);
 799
 800   return first_edge->src;
 801 }
 802
 803 /* Replace PHI node with conditional modify expr using COND.  This
 804    routine does not handle PHI nodes with more than two arguments.
 805
 806    For example,
 807      S1: A = PHI <x1(1), x2(5)
 808    is converted into,
 809      S2: A = cond ? x1 : x2;
 810
 811    The generated code is inserted at GSI that points to the top of
 812    basic block's statement list.  When COND is true, phi arg from
 813    TRUE_BB is selected.  */
 814
 815 static void
 816 replace_phi_with_cond_gimple_assign_stmt (gimple phi, tree cond,
 817                                           basic_block true_bb,
 818                                           gimple_stmt_iterator *gsi)
 819 {
 820   gimple new_stmt;
 821   basic_block bb;
 822   tree rhs;
 823   tree arg_0, arg_1;
 824
 825   gcc_assert (gimple_code (phi) == GIMPLE_PHI
 826               && gimple_phi_num_args (phi) == 2);
 827
 828   bb = gimple_bb (phi);
 829
 830   /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr.  */
 831   if (EDGE_PRED (bb, 1)->src == true_bb)
 832     {
 833       arg_0 = gimple_phi_arg_def (phi, 1);
 834       arg_1 = gimple_phi_arg_def (phi, 0);
 835     }
 836   else
 837     {
 838       arg_0 = gimple_phi_arg_def (phi, 0);
 839       arg_1 = gimple_phi_arg_def (phi, 1);
 840     }
 841
 842   /* Build new RHS using selected condition and arguments.  */
 843   rhs = build3 (COND_EXPR, TREE_TYPE (PHI_RESULT (phi)),
 844                 unshare_expr (cond), unshare_expr (arg_0),
 845                 unshare_expr (arg_1));
 846
 847   new_stmt = gimple_build_assign (unshare_expr (PHI_RESULT (phi)), rhs);
 848   SSA_NAME_DEF_STMT (gimple_phi_result (phi)) = new_stmt;
 849   gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
 850   update_stmt (new_stmt);
 851
 852   if (dump_file && (dump_flags & TDF_DETAILS))
 853     {
 854       fprintf (dump_file, "new phi replacement stmt\n");
 855       print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM);
 856     }
 857 }
 858
 859 /* Process phi nodes for the given LOOP.  Replace phi nodes with
 860    conditional modify expressions.  */
 861
 862 static void
 863 process_phi_nodes (struct loop *loop)
 864 {
 865   basic_block bb;
 866   unsigned int orig_loop_num_nodes = loop->num_nodes;
 867   unsigned int i;
 868
 869   for (i = 1; i < orig_loop_num_nodes; i++)
 870     {
 871       gimple phi;
 872       tree cond = NULL_TREE;
 873       gimple_stmt_iterator gsi, phi_gsi;
 874       basic_block true_bb = NULL;
 875       bb = ifc_bbs[i];
 876
 877       if (bb == loop->header)
 878         continue;
 879
 880       phi_gsi = gsi_start_phis (bb);
 881       gsi = gsi_after_labels (bb);
 882
 883       /* BB has two predecessors.  Using predecessor's aux field, set
 884          appropriate condition for the PHI node replacement.  */
 885       if (!gsi_end_p (phi_gsi))
 886         true_bb = find_phi_replacement_condition (loop, bb, &cond, &gsi);
 887
 888       while (!gsi_end_p (phi_gsi))
 889         {
 890           phi = gsi_stmt (phi_gsi);
 891           replace_phi_with_cond_gimple_assign_stmt (phi, cond, true_bb, &gsi);
 892           release_phi_node (phi);
 893           gsi_next (&phi_gsi);
 894         }
 895       set_phi_nodes (bb, NULL);
 896     }
 897 }
 898
 899 /* Combine all the basic blocks from LOOP into one or two super basic
 900    blocks.  Replace PHI nodes with conditional modify expressions.  */
 901
 902 static void
 903 combine_blocks (struct loop *loop)
 904 {
 905   basic_block bb, exit_bb, merge_target_bb;
 906   unsigned int orig_loop_num_nodes = loop->num_nodes;
 907   unsigned int i;
 908   edge e;
 909   edge_iterator ei;
 910
 911   /* Process phi nodes to prepare blocks for merge.  */
 912   process_phi_nodes (loop);
 913
 914   /* Merge basic blocks: first remove all the edges in the loop,
 915      except for those from the exit block.  */
 916   exit_bb = NULL;
 917   for (i = 0; i < orig_loop_num_nodes; i++)
 918     {
 919       bb = ifc_bbs[i];
 920       if (bb_with_exit_edge_p (loop, bb))
 921         {
 922           exit_bb = bb;
 923           break;
 924         }
 925     }
 926   gcc_assert (exit_bb != loop->latch);
 927
 928   for (i = 1; i < orig_loop_num_nodes; i++)
 929     {
 930       bb = ifc_bbs[i];
 931
 932       for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei));)
 933         {
 934           if (e->src == exit_bb)
 935             ei_next (&ei);
 936           else
 937             remove_edge (e);
 938         }
 939     }
 940
 941   if (exit_bb != NULL)
 942     {
 943       if (exit_bb != loop->header)
 944         {
 945           /* Connect this node to loop header.  */
 946           make_edge (loop->header, exit_bb, EDGE_FALLTHRU);
 947           set_immediate_dominator (CDI_DOMINATORS, exit_bb, loop->header);
 948         }
 949
 950       /* Redirect non-exit edges to loop->latch.  */
 951       FOR_EACH_EDGE (e, ei, exit_bb->succs)
 952         {
 953           if (!loop_exit_edge_p (loop, e))
 954             redirect_edge_and_branch (e, loop->latch);
 955         }
 956       set_immediate_dominator (CDI_DOMINATORS, loop->latch, exit_bb);
 957     }
 958   else
 959     {
 960       /* If the loop does not have an exit, reconnect header and latch.  */
 961       make_edge (loop->header, loop->latch, EDGE_FALLTHRU);
 962       set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header);
 963     }
 964
 965   merge_target_bb = loop->header;
 966   for (i = 1; i < orig_loop_num_nodes; i++)
 967     {
 968       gimple_stmt_iterator gsi;
 969       gimple_stmt_iterator last;
 970
 971       bb = ifc_bbs[i];
 972
 973       if (bb == exit_bb || bb == loop->latch)
 974         continue;
 975
 976       /* Remove labels and make stmts member of loop->header.  */
 977       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
 978         {
 979           if (gimple_code (gsi_stmt (gsi)) == GIMPLE_LABEL)
 980             gsi_remove (&gsi, true);
 981           else
 982             {
 983               gimple_set_bb (gsi_stmt (gsi), merge_target_bb);
 984               gsi_next (&gsi);
 985             }
 986         }
 987
 988       /* Update stmt list.  */
 989       last = gsi_last_bb (merge_target_bb);
 990       gsi_insert_seq_after (&last, bb_seq (bb), GSI_NEW_STMT);
 991       set_bb_seq (bb, NULL);
 992
 993       delete_basic_block (bb);
 994     }
 995
 996   /* If possible, merge loop header to the block with the exit edge.
 997      This reduces the number of basic blocks to two, to please the
 998      vectorizer that handles only loops with two nodes.
 999
1000      FIXME: Call cleanup_tree_cfg.  */
1001   if (exit_bb
1002       && exit_bb != loop->header
1003       && can_merge_blocks_p (loop->header, exit_bb))
1004     merge_blocks (loop->header, exit_bb);
1005 }
1006
1007 /* Main entry point: return true when LOOP is if-converted, otherwise
1008    the loop remains unchanged.  */
1009
1010 static bool
1011 tree_if_conversion (struct loop *loop)
1012 {
1013   gimple_stmt_iterator itr;
1014   unsigned int i;
1015
1016   ifc_bbs = NULL;
1017
1018   /* If-conversion is not appropriate for all loops.  First, check if
1019      the loop is if-convertible.  */
1020   if (!if_convertible_loop_p (loop))
1021     {
1022       if (dump_file && (dump_flags & TDF_DETAILS))
1023         fprintf (dump_file,"-------------------------\n");
1024       if (ifc_bbs)
1025         {
1026           free (ifc_bbs);
1027           ifc_bbs = NULL;
1028         }
1029       free_dominance_info (CDI_POST_DOMINATORS);
1030       return false;
1031     }
1032
1033   for (i = 0; i < loop->num_nodes; i++)
1034     {
1035       basic_block bb = ifc_bbs [i];
1036       tree cond = (tree) bb->aux;
1037
1038       /* Process all the statements in this basic block.
1039          Remove conditional expression, if any, and annotate
1040          destination basic block(s) appropriately.  */
1041       for (itr = gsi_start_bb (bb); !gsi_end_p (itr); /* empty */)
1042         {
1043           gimple t = gsi_stmt (itr);
1044           cond = tree_if_convert_stmt (loop, t, cond, &itr);
1045           if (!gsi_end_p (itr))
1046             gsi_next (&itr);
1047         }
1048
1049       /* If current bb has only one successor, then consider it as an
1050          unconditional goto.  */
1051       if (single_succ_p (bb))
1052         {
1053           basic_block bb_n = single_succ (bb);
1054
1055           /* The successor bb inherits the predicate of its
1056              predecessor.  If there is no predicate in the predecessor
1057              bb, then consider the successor bb as always executed.  */
1058           if (cond == NULL_TREE)
1059             cond = boolean_true_node;
1060
1061           add_to_predicate_list (bb_n, cond);
1062         }
1063     }
1064
1065   /* Now, all statements are if-converted and basic blocks are
1066      annotated appropriately.  Combine all the basic blocks into one
1067      huge basic block.  */
1068   combine_blocks (loop);
1069
1070   /* clean up */
1071   clean_predicate_lists (loop);
1072   free (ifc_bbs);
1073   ifc_bbs = NULL;
1074
1075   return true;
1076 }
1077
1078 /* Tree if-conversion pass management.  */
1079
1080 static unsigned int
1081 main_tree_if_conversion (void)
1082 {
1083   loop_iterator li;
1084   struct loop *loop;
1085
1086   if (number_of_loops () <= 1)
1087     return 0;
1088
1089   FOR_EACH_LOOP (li, loop, 0)
1090     tree_if_conversion (loop);
1091
1092   return 0;
1093 }
1094
1095 static bool
1096 gate_tree_if_conversion (void)
1097 {
1098   return flag_tree_vectorize != 0;
1099 }
1100
1101 struct gimple_opt_pass pass_if_conversion =
1102 {
1103  {
1104   GIMPLE_PASS,
1105   "ifcvt",                              /* name */
1106   gate_tree_if_conversion,              /* gate */
1107   main_tree_if_conversion,              /* execute */
1108   NULL,                                 /* sub */
1109   NULL,                                 /* next */
1110   0,                                    /* static_pass_number */
1111   TV_NONE,                              /* tv_id */
1112   PROP_cfg | PROP_ssa,                  /* properties_required */
1113   0,                                    /* properties_provided */
1114   0,                                    /* properties_destroyed */
1115   0,                                    /* todo_flags_start */
1116   TODO_dump_func | TODO_verify_stmts | TODO_verify_flow
1117                                         /* todo_flags_finish */
1118  }
1119 };