gcc/tree-if-conv.c

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