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
 487    S2 will be predicated with "!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             case GIMPLE_DEBUG:
 513               break;
 514
 515             case GIMPLE_COND:
 516               {
 517                 tree c2;
 518                 edge true_edge, false_edge;
 519                 location_t loc = gimple_location (stmt);
 520                 tree c = fold_build2_loc (loc, gimple_cond_code (stmt),
 521                                           boolean_type_node,
 522                                           gimple_cond_lhs (stmt),
 523                                           gimple_cond_rhs (stmt));
 524
 525                 extract_true_false_edges_from_block (gimple_bb (stmt),
 526                                                      &true_edge, &false_edge);
 527
 528                 /* Add new condition into destination's predicate list.  */
 529
 530                 /* If C is true, then TRUE_EDGE is taken.  */
 531                 add_to_dst_predicate_list (loop, true_edge, cond, c);
 532
 533                 /* If C is false, then FALSE_EDGE is taken.  */
 534                 c2 = invert_truthvalue_loc (loc, unshare_expr (c));
 535                 add_to_dst_predicate_list (loop, false_edge, cond, c2);
 536
 537                 cond = NULL_TREE;
 538                 break;
 539               }
 540
 541             default:
 542               /* Not handled yet in if-conversion.  */
 543               return false;
 544             }
 545         }
 546
 547       /* If current bb has only one successor, then consider it as an
 548          unconditional goto.  */
 549       if (single_succ_p (bb))
 550         {
 551           basic_block bb_n = single_succ (bb);
 552
 553           /* The successor bb inherits the predicate of its
 554              predecessor.  If there is no predicate in the predecessor
 555              bb, then consider the successor bb as always executed.  */
 556           if (cond == NULL_TREE)
 557             cond = boolean_true_node;
 558
 559           add_to_predicate_list (bb_n, cond);
 560         }
 561     }
 562
 563   /* The loop header is always executed.  */
 564   loop->header->aux = boolean_true_node;
 565
 566   return true;
 567 }
 568
 569 /* Return true when LOOP is if-convertible.
 570    LOOP is if-convertible if:
 571    - it is innermost,
 572    - it has two or more basic blocks,
 573    - it has only one exit,
 574    - loop header is not the exit edge,
 575    - if its basic blocks and phi nodes are if convertible.  */
 576
 577 static bool
 578 if_convertible_loop_p (struct loop *loop)
 579 {
 580   unsigned int i;
 581   edge e;
 582   edge_iterator ei;
 583   basic_block exit_bb = NULL;
 584
 585   /* Handle only innermost loop.  */
 586   if (!loop || loop->inner)
 587     {
 588       if (dump_file && (dump_flags & TDF_DETAILS))
 589         fprintf (dump_file, "not innermost loop\n");
 590       return false;
 591     }
 592
 593   /* If only one block, no need for if-conversion.  */
 594   if (loop->num_nodes <= 2)
 595     {
 596       if (dump_file && (dump_flags & TDF_DETAILS))
 597         fprintf (dump_file, "less than 2 basic blocks\n");
 598       return false;
 599     }
 600
 601   /* More than one loop exit is too much to handle.  */
 602   if (!single_exit (loop))
 603     {
 604       if (dump_file && (dump_flags & TDF_DETAILS))
 605         fprintf (dump_file, "multiple exits\n");
 606       return false;
 607     }
 608
 609   /* ??? Check target's vector conditional operation support for vectorizer.  */
 610
 611   /* If one of the loop header's edge is exit edge then do not apply
 612      if-conversion.  */
 613   FOR_EACH_EDGE (e, ei, loop->header->succs)
 614     {
 615       if (loop_exit_edge_p (loop, e))
 616         return false;
 617     }
 618
 619   /* Don't if-convert the loop when the data dependences cannot be
 620      computed: the loop won't be vectorized in that case.  */
 621   {
 622     VEC (data_reference_p, heap) *refs = VEC_alloc (data_reference_p, heap, 5);
 623     VEC (ddr_p, heap) *ddrs = VEC_alloc (ddr_p, heap, 25);
 624     bool res = compute_data_dependences_for_loop (loop, true, &refs, &ddrs);
 625
 626     free_data_refs (refs);
 627     free_dependence_relations (ddrs);
 628
 629     if (!res)
 630       return false;
 631   }
 632
 633   calculate_dominance_info (CDI_DOMINATORS);
 634
 635   /* Allow statements that can be handled during if-conversion.  */
 636   ifc_bbs = get_loop_body_in_if_conv_order (loop);
 637   if (!ifc_bbs)
 638     {
 639       if (dump_file && (dump_flags & TDF_DETAILS))
 640         fprintf (dump_file, "Irreducible loop\n");
 641       return false;
 642     }
 643
 644   for (i = 0; i < loop->num_nodes; i++)
 645     {
 646       basic_block bb = ifc_bbs[i];
 647
 648       if (!if_convertible_bb_p (loop, bb, exit_bb))
 649         return false;
 650
 651       if (bb_with_exit_edge_p (loop, bb))
 652         exit_bb = bb;
 653     }
 654
 655   if (!predicate_bbs (loop))
 656     return false;
 657
 658   for (i = 0; i < loop->num_nodes; i++)
 659     {
 660       basic_block bb = ifc_bbs[i];
 661       gimple_stmt_iterator itr;
 662
 663       for (itr = gsi_start_phis (bb); !gsi_end_p (itr); gsi_next (&itr))
 664         if (!if_convertible_phi_p (loop, bb, gsi_stmt (itr)))
 665           return false;
 666
 667       /* For non predicated BBs, don't check their statements.  */
 668       if (!is_predicated (bb))
 669         continue;
 670
 671       for (itr = gsi_start_bb (bb); !gsi_end_p (itr); gsi_next (&itr))
 672         if (!if_convertible_stmt_p (loop, bb, gsi_stmt (itr)))
 673           return false;
 674     }
 675
 676   if (dump_file)
 677     fprintf (dump_file, "Applying if-conversion\n");
 678
 679   return true;
 680 }
 681
 682 /* During if-conversion, the bb->aux field is used to hold a predicate
 683    list.  This function cleans for all the basic blocks in the given
 684    LOOP their predicate list.  */
 685
 686 static void
 687 clean_predicate_lists (struct loop *loop)
 688 {
 689   unsigned int i;
 690   basic_block *bbs = get_loop_body (loop);
 691
 692   for (i = 0; i < loop->num_nodes; i++)
 693     bbs[i]->aux = NULL;
 694
 695   free (bbs);
 696 }
 697
 698 /* Basic block BB has two predecessors.  Using predecessor's bb->aux
 699    field, set appropriate condition COND for the PHI node replacement.
 700    Return true block whose phi arguments are selected when cond is
 701    true.  LOOP is the loop containing the if-converted region, GSI is
 702    the place to insert the code for the if-conversion.  */
 703
 704 static basic_block
 705 find_phi_replacement_condition (struct loop *loop,
 706                                 basic_block bb, tree *cond,
 707                                 gimple_stmt_iterator *gsi)
 708 {
 709   edge first_edge, second_edge;
 710   tree tmp_cond;
 711
 712   gcc_assert (EDGE_COUNT (bb->preds) == 2);
 713   first_edge = EDGE_PRED (bb, 0);
 714   second_edge = EDGE_PRED (bb, 1);
 715
 716   /* Use condition based on following criteria:
 717      1)
 718        S1: x = !c ? a : b;
 719
 720        S2: x = c ? b : a;
 721
 722        S2 is preferred over S1. Make 'b' first_bb and use its condition.
 723
 724      2) Do not make loop header first_bb.
 725
 726      3)
 727        S1: x = !(c == d)? a : b;
 728
 729        S21: t1 = c == d;
 730        S22: x = t1 ? b : a;
 731
 732        S3: x = (c == d) ? b : a;
 733
 734        S3 is preferred over S1 and S2*, Make 'b' first_bb and use
 735        its condition.
 736
 737      4) If  pred B is dominated by pred A then use pred B's condition.
 738         See PR23115.  */
 739
 740   /* Select condition that is not TRUTH_NOT_EXPR.  */
 741   tmp_cond = (tree) (first_edge->src)->aux;
 742   gcc_assert (tmp_cond);
 743
 744   if (TREE_CODE (tmp_cond) == TRUTH_NOT_EXPR)
 745     {
 746       edge tmp_edge;
 747
 748       tmp_edge = first_edge;
 749       first_edge = second_edge;
 750       second_edge = tmp_edge;
 751     }
 752
 753   /* Check if FIRST_BB is loop header or not and make sure that
 754      FIRST_BB does not dominate SECOND_BB.  */
 755   if (first_edge->src == loop->header
 756       || dominated_by_p (CDI_DOMINATORS,
 757                          second_edge->src, first_edge->src))
 758     {
 759       *cond = (tree) (second_edge->src)->aux;
 760
 761       if (TREE_CODE (*cond) == TRUTH_NOT_EXPR)
 762         *cond = invert_truthvalue (*cond);
 763       else
 764         /* Select non loop header bb.  */
 765         first_edge = second_edge;
 766     }
 767   else
 768     *cond = (tree) (first_edge->src)->aux;
 769
 770   /* Gimplify the condition: the vectorizer prefers to have gimple
 771      values as conditions.  Various targets use different means to
 772      communicate conditions in vector compare operations.  Using a
 773      gimple value allows the compiler to emit vector compare and
 774      select RTL without exposing compare's result.  */
 775   *cond = force_gimple_operand_gsi (gsi, unshare_expr (*cond),
 776                                     false, NULL_TREE,
 777                                     true, GSI_SAME_STMT);
 778   if (!is_gimple_reg (*cond) && !is_gimple_condexpr (*cond))
 779     {
 780       gimple new_stmt;
 781
 782       new_stmt = ifc_temp_var (TREE_TYPE (*cond), unshare_expr (*cond));
 783       gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
 784       *cond = gimple_assign_lhs (new_stmt);
 785     }
 786
 787   gcc_assert (*cond);
 788
 789   return first_edge->src;
 790 }
 791
 792 /* Replace PHI node with conditional modify expr using COND.  This
 793    routine does not handle PHI nodes with more than two arguments.
 794
 795    For example,
 796      S1: A = PHI <x1(1), x2(5)
 797    is converted into,
 798      S2: A = cond ? x1 : x2;
 799
 800    The generated code is inserted at GSI that points to the top of
 801    basic block's statement list.  When COND is true, phi arg from
 802    TRUE_BB is selected.  */
 803
 804 static void
 805 replace_phi_with_cond_gimple_assign_stmt (gimple phi, tree cond,
 806                                           basic_block true_bb,
 807                                           gimple_stmt_iterator *gsi)
 808 {
 809   gimple new_stmt;
 810   basic_block bb;
 811   tree rhs;
 812   tree arg;
 813
 814   gcc_assert (gimple_code (phi) == GIMPLE_PHI
 815               && gimple_phi_num_args (phi) == 2);
 816
 817   bb = gimple_bb (phi);
 818
 819   arg = degenerate_phi_result (phi);
 820   if (arg)
 821     rhs = arg;
 822   else
 823     {
 824       tree arg_0, arg_1;
 825       /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr.  */
 826       if (EDGE_PRED (bb, 1)->src == true_bb)
 827         {
 828           arg_0 = gimple_phi_arg_def (phi, 1);
 829           arg_1 = gimple_phi_arg_def (phi, 0);
 830         }
 831       else
 832         {
 833           arg_0 = gimple_phi_arg_def (phi, 0);
 834           arg_1 = gimple_phi_arg_def (phi, 1);
 835         }
 836
 837       /* Build new RHS using selected condition and arguments.  */
 838       rhs = build3 (COND_EXPR, TREE_TYPE (PHI_RESULT (phi)),
 839                     unshare_expr (cond), arg_0, arg_1);
 840     }
 841
 842   new_stmt = gimple_build_assign (PHI_RESULT (phi), rhs);
 843   SSA_NAME_DEF_STMT (gimple_phi_result (phi)) = new_stmt;
 844   gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
 845   update_stmt (new_stmt);
 846
 847   if (dump_file && (dump_flags & TDF_DETAILS))
 848     {
 849       fprintf (dump_file, "new phi replacement stmt\n");
 850       print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM);
 851     }
 852 }
 853
 854 /* Process phi nodes for the given LOOP.  Replace phi nodes with
 855    conditional modify expressions.  */
 856
 857 static void
 858 process_phi_nodes (struct loop *loop)
 859 {
 860   basic_block bb;
 861   unsigned int orig_loop_num_nodes = loop->num_nodes;
 862   unsigned int i;
 863
 864   for (i = 1; i < orig_loop_num_nodes; i++)
 865     {
 866       gimple phi;
 867       tree cond = NULL_TREE;
 868       gimple_stmt_iterator gsi, phi_gsi;
 869       basic_block true_bb = NULL;
 870       bb = ifc_bbs[i];
 871
 872       if (bb == loop->header)
 873         continue;
 874
 875       phi_gsi = gsi_start_phis (bb);
 876       gsi = gsi_after_labels (bb);
 877
 878       /* BB has two predecessors.  Using predecessor's aux field, set
 879          appropriate condition for the PHI node replacement.  */
 880       if (!gsi_end_p (phi_gsi))
 881         true_bb = find_phi_replacement_condition (loop, bb, &cond, &gsi);
 882
 883       while (!gsi_end_p (phi_gsi))
 884         {
 885           phi = gsi_stmt (phi_gsi);
 886           replace_phi_with_cond_gimple_assign_stmt (phi, cond, true_bb, &gsi);
 887           release_phi_node (phi);
 888           gsi_next (&phi_gsi);
 889         }
 890       set_phi_nodes (bb, NULL);
 891     }
 892 }
 893
 894 /* Remove all GIMPLE_CONDs and GIMPLE_LABELs of all the basic blocks
 895    other than the exit and latch of the LOOP.  Also resets the
 896    GIMPLE_DEBUG information.  */
 897
 898 static void
 899 remove_conditions_and_labels (loop_p loop)
 900 {
 901   gimple_stmt_iterator gsi;
 902   unsigned int i;
 903
 904   for (i = 0; i < loop->num_nodes; i++)
 905     {
 906       basic_block bb = ifc_bbs [i];
 907
 908       if (bb_with_exit_edge_p (loop, bb)
 909         || bb == loop->latch)
 910       continue;
 911
 912       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
 913         switch (gimple_code (gsi_stmt (gsi)))
 914           {
 915           case GIMPLE_COND:
 916           case GIMPLE_LABEL:
 917             gsi_remove (&gsi, true);
 918             break;
 919
 920           case GIMPLE_DEBUG:
 921             /* ??? Should there be conditional GIMPLE_DEBUG_BINDs?  */
 922             if (gimple_debug_bind_p (gsi_stmt (gsi)))
 923               {
 924                 gimple_debug_bind_reset_value (gsi_stmt (gsi));
 925                 update_stmt (gsi_stmt (gsi));
 926               }
 927             gsi_next (&gsi);
 928             break;
 929
 930           default:
 931             gsi_next (&gsi);
 932           }
 933     }
 934 }
 935
 936 /* Combine all the basic blocks from LOOP into one or two super basic
 937    blocks.  Replace PHI nodes with conditional modify expressions.  */
 938
 939 static void
 940 combine_blocks (struct loop *loop)
 941 {
 942   basic_block bb, exit_bb, merge_target_bb;
 943   unsigned int orig_loop_num_nodes = loop->num_nodes;
 944   unsigned int i;
 945   edge e;
 946   edge_iterator ei;
 947
 948   remove_conditions_and_labels (loop);
 949
 950   /* Process phi nodes to prepare blocks for merge.  */
 951   process_phi_nodes (loop);
 952
 953   /* Merge basic blocks: first remove all the edges in the loop,
 954      except for those from the exit block.  */
 955   exit_bb = NULL;
 956   for (i = 0; i < orig_loop_num_nodes; i++)
 957     {
 958       bb = ifc_bbs[i];
 959       if (bb_with_exit_edge_p (loop, bb))
 960         {
 961           exit_bb = bb;
 962           break;
 963         }
 964     }
 965   gcc_assert (exit_bb != loop->latch);
 966
 967   for (i = 1; i < orig_loop_num_nodes; i++)
 968     {
 969       bb = ifc_bbs[i];
 970
 971       for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei));)
 972         {
 973           if (e->src == exit_bb)
 974             ei_next (&ei);
 975           else
 976             remove_edge (e);
 977         }
 978     }
 979
 980   if (exit_bb != NULL)
 981     {
 982       if (exit_bb != loop->header)
 983         {
 984           /* Connect this node to loop header.  */
 985           make_edge (loop->header, exit_bb, EDGE_FALLTHRU);
 986           set_immediate_dominator (CDI_DOMINATORS, exit_bb, loop->header);
 987         }
 988
 989       /* Redirect non-exit edges to loop->latch.  */
 990       FOR_EACH_EDGE (e, ei, exit_bb->succs)
 991         {
 992           if (!loop_exit_edge_p (loop, e))
 993             redirect_edge_and_branch (e, loop->latch);
 994         }
 995       set_immediate_dominator (CDI_DOMINATORS, loop->latch, exit_bb);
 996     }
 997   else
 998     {
 999       /* If the loop does not have an exit, reconnect header and latch.  */
1000       make_edge (loop->header, loop->latch, EDGE_FALLTHRU);
1001       set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header);
1002     }
1003
1004   merge_target_bb = loop->header;
1005   for (i = 1; i < orig_loop_num_nodes; i++)
1006     {
1007       gimple_stmt_iterator gsi;
1008       gimple_stmt_iterator last;
1009
1010       bb = ifc_bbs[i];
1011
1012       if (bb == exit_bb || bb == loop->latch)
1013         continue;
1014
1015       /* Make stmts member of loop->header.  */
1016       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1017         gimple_set_bb (gsi_stmt (gsi), merge_target_bb);
1018
1019       /* Update stmt list.  */
1020       last = gsi_last_bb (merge_target_bb);
1021       gsi_insert_seq_after (&last, bb_seq (bb), GSI_NEW_STMT);
1022       set_bb_seq (bb, NULL);
1023
1024       delete_basic_block (bb);
1025     }
1026
1027   /* If possible, merge loop header to the block with the exit edge.
1028      This reduces the number of basic blocks to two, to please the
1029      vectorizer that handles only loops with two nodes.
1030
1031      FIXME: Call cleanup_tree_cfg.  */
1032   if (exit_bb
1033       && exit_bb != loop->header
1034       && can_merge_blocks_p (loop->header, exit_bb))
1035     merge_blocks (loop->header, exit_bb);
1036 }
1037
1038 /* If-convert LOOP when it is legal.  For the moment this pass has no
1039    profitability analysis.  */
1040
1041 static void
1042 tree_if_conversion (struct loop *loop)
1043 {
1044   ifc_bbs = NULL;
1045
1046   if (!if_convertible_loop_p (loop))
1047     goto cleanup;
1048
1049   /* Now all statements are if-convertible.  Combine all the basic
1050      blocks into one huge basic block doing the if-conversion
1051      on-the-fly.  */
1052   combine_blocks (loop);
1053
1054  cleanup:
1055   clean_predicate_lists (loop);
1056   if (ifc_bbs)
1057     {
1058       free (ifc_bbs);
1059       ifc_bbs = NULL;
1060     }
1061 }
1062
1063 /* Tree if-conversion pass management.  */
1064
1065 static unsigned int
1066 main_tree_if_conversion (void)
1067 {
1068   loop_iterator li;
1069   struct loop *loop;
1070
1071   if (number_of_loops () <= 1)
1072     return 0;
1073
1074   FOR_EACH_LOOP (li, loop, 0)
1075     tree_if_conversion (loop);
1076
1077   return 0;
1078 }
1079
1080 static bool
1081 gate_tree_if_conversion (void)
1082 {
1083   return flag_tree_vectorize != 0;
1084 }
1085
1086 struct gimple_opt_pass pass_if_conversion =
1087 {
1088  {
1089   GIMPLE_PASS,
1090   "ifcvt",                              /* name */
1091   gate_tree_if_conversion,              /* gate */
1092   main_tree_if_conversion,              /* execute */
1093   NULL,                                 /* sub */
1094   NULL,                                 /* next */
1095   0,                                    /* static_pass_number */
1096   TV_NONE,                              /* tv_id */
1097   PROP_cfg | PROP_ssa,                  /* properties_required */
1098   0,                                    /* properties_provided */
1099   0,                                    /* properties_destroyed */
1100   0,                                    /* todo_flags_start */
1101   TODO_dump_func | TODO_verify_stmts | TODO_verify_flow
1102                                         /* todo_flags_finish */
1103  }
1104 };