gcc/tree-if-conv.c

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