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