gcc/tree-if-conv.c

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