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