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