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