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.
 138    Apply if-conversion to the LOOP. Return true if successful otherwise return
 139    false. If false is returned then loop remains unchanged.
 140    FOR_VECTORIZER is a boolean flag. It indicates whether if-conversion is used
 141    for vectorizer or not. If it is used for vectorizer, additional checks are
 142    used. (Vectorization checks 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 loop  is
 154      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 validity 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.. (Not implemented yet).  */
 525
 526 static bool
 527 if_convertible_loop_p (struct loop *loop, bool for_vectorizer ATTRIBUTE_UNUSED)
 528 {
 529   basic_block bb;
 530   gimple_stmt_iterator itr;
 531   unsigned int i;
 532   edge e;
 533   edge_iterator ei;
 534   basic_block exit_bb = NULL;
 535
 536   /* Handle only inner most loop.  */
 537   if (!loop || loop->inner)
 538     {
 539       if (dump_file && (dump_flags & TDF_DETAILS))
 540         fprintf (dump_file, "not inner most loop\n");
 541       return false;
 542     }
 543
 544   /* If only one block, no need for if-conversion.  */
 545   if (loop->num_nodes <= 2)
 546     {
 547       if (dump_file && (dump_flags & TDF_DETAILS))
 548         fprintf (dump_file, "less than 2 basic blocks\n");
 549       return false;
 550     }
 551
 552   /* More than one loop exit is too much to handle.  */
 553   if (!single_exit (loop))
 554     {
 555       if (dump_file && (dump_flags & TDF_DETAILS))
 556         fprintf (dump_file, "multiple exits\n");
 557       return false;
 558     }
 559
 560   /* ??? Check target's vector conditional operation support for vectorizer.  */
 561
 562   /* If one of the loop header's edge is exit edge then do not apply
 563      if-conversion.  */
 564   FOR_EACH_EDGE (e, ei, loop->header->succs)
 565     {
 566       if (loop_exit_edge_p (loop, e))
 567         return false;
 568     }
 569
 570   calculate_dominance_info (CDI_DOMINATORS);
 571   calculate_dominance_info (CDI_POST_DOMINATORS);
 572
 573   /* Allow statements that can be handled during if-conversion.  */
 574   ifc_bbs = get_loop_body_in_if_conv_order (loop);
 575   if (!ifc_bbs)
 576     {
 577       if (dump_file && (dump_flags & TDF_DETAILS))
 578         fprintf (dump_file,"Irreducible loop\n");
 579       free_dominance_info (CDI_POST_DOMINATORS);
 580       return false;
 581     }
 582
 583   for (i = 0; i < loop->num_nodes; i++)
 584     {
 585       bb = ifc_bbs[i];
 586
 587       if (!if_convertible_bb_p (loop, bb, exit_bb))
 588         return false;
 589
 590       /* Check statements.  */
 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       /* ??? Check data dependency for vectorizer.  */
 595
 596       /* What about phi nodes ? */
 597       itr = gsi_start_phis (bb);
 598
 599       /* Clear aux field of incoming edges to a bb with a phi node.  */
 600       if (!gsi_end_p (itr))
 601         FOR_EACH_EDGE (e, ei, bb->preds)
 602           e->aux = NULL;
 603
 604       /* Check statements.  */
 605       for (; !gsi_end_p (itr); gsi_next (&itr))
 606         if (!if_convertible_phi_p (loop, bb, gsi_stmt (itr)))
 607           return false;
 608
 609       if (bb_with_exit_edge_p (loop, bb))
 610         exit_bb = bb;
 611     }
 612
 613   /* OK. Did not find any potential issues so go ahead in if-convert
 614      this loop. Now there is no looking back.  */
 615   if (dump_file)
 616     fprintf (dump_file,"Applying if-conversion\n");
 617
 618   free_dominance_info (CDI_POST_DOMINATORS);
 619   return true;
 620 }
 621
 622 /* Add condition COND into predicate list of basic block BB.  */
 623
 624 static void
 625 add_to_predicate_list (basic_block bb, tree new_cond)
 626 {
 627   tree cond = (tree) bb->aux;
 628
 629   if (cond)
 630     cond = fold_build2_loc (EXPR_LOCATION (cond),
 631                         TRUTH_OR_EXPR, boolean_type_node,
 632                         unshare_expr (cond), new_cond);
 633   else
 634     cond = new_cond;
 635
 636   bb->aux = cond;
 637 }
 638
 639 /* Add condition COND into BB's predicate list.  PREV_COND is
 640    existing condition.  */
 641
 642 static tree
 643 add_to_dst_predicate_list (struct loop * loop, edge e,
 644                            tree prev_cond, tree cond,
 645                            gimple_stmt_iterator *gsi)
 646 {
 647   tree new_cond = NULL_TREE;
 648
 649   if (!flow_bb_inside_loop_p (loop, e->dest))
 650     return NULL_TREE;
 651
 652   if (prev_cond == boolean_true_node || !prev_cond)
 653     new_cond = unshare_expr (cond);
 654   else
 655     {
 656       tree tmp;
 657       gimple tmp_stmt = NULL;
 658
 659       prev_cond = force_gimple_operand_gsi (gsi, unshare_expr (prev_cond),
 660                                             true, NULL, true, GSI_SAME_STMT);
 661
 662       cond = force_gimple_operand_gsi (gsi, unshare_expr (cond),
 663                                        true, NULL, true, GSI_SAME_STMT);
 664
 665       /* Add the condition to aux field of the edge.  In case edge
 666          destination is a PHI node, this condition will be ANDed with
 667          block predicate to construct complete condition.  */
 668       e->aux = cond;
 669
 670       /* new_cond == prev_cond AND cond */
 671       tmp = build2 (TRUTH_AND_EXPR, boolean_type_node,
 672                     unshare_expr (prev_cond), cond);
 673       tmp_stmt = ifc_temp_var (boolean_type_node, tmp);
 674       gsi_insert_before (gsi, tmp_stmt, GSI_SAME_STMT);
 675       new_cond = gimple_assign_lhs (tmp_stmt);
 676     }
 677   add_to_predicate_list (e->dest, new_cond);
 678   return new_cond;
 679 }
 680
 681 /* During if-conversion aux field from basic block structure is used to hold
 682    predicate list. Clean each basic block's predicate list for the given LOOP.
 683    Also clean aux field of successor edges, used to hold true and false
 684    condition from conditional expression.  */
 685
 686 static void
 687 clean_predicate_lists (struct loop *loop)
 688 {
 689   basic_block *bb;
 690   unsigned int i;
 691   edge e;
 692   edge_iterator ei;
 693
 694   bb = get_loop_body (loop);
 695   for (i = 0; i < loop->num_nodes; i++)
 696     {
 697       bb[i]->aux = NULL;
 698       FOR_EACH_EDGE (e, ei, bb[i]->succs)
 699         e->aux = NULL;
 700     }
 701   free (bb);
 702 }
 703
 704 /* Basic block BB has two predecessors. Using predecessor's aux field, set
 705    appropriate condition COND for the PHI node replacement. Return true block
 706    whose phi arguments are selected when cond is true.  */
 707
 708 static basic_block
 709 find_phi_replacement_condition (struct loop *loop,
 710                                 basic_block bb, tree *cond,
 711                                 gimple_stmt_iterator *gsi)
 712 {
 713   edge first_edge, second_edge;
 714   tree tmp_cond;
 715
 716   gcc_assert (EDGE_COUNT (bb->preds) == 2);
 717   first_edge = EDGE_PRED (bb, 0);
 718   second_edge = EDGE_PRED (bb, 1);
 719
 720   /* Use condition based on following criteria:
 721      1)
 722        S1: x = !c ? a : b;
 723
 724        S2: x = c ? b : a;
 725
 726        S2 is preferred over S1. Make 'b' first_bb and use its condition.
 727
 728      2) Do not make loop header first_bb.
 729
 730      3)
 731        S1: x = !(c == d)? a : b;
 732
 733        S21: t1 = c == d;
 734        S22: x = t1 ? b : a;
 735
 736        S3: x = (c == d) ? b : a;
 737
 738        S3 is preferred over S1 and S2*, Make 'b' first_bb and use
 739        its condition.
 740
 741      4) If  pred B is dominated by pred A then use pred B's condition.
 742         See PR23115.  */
 743
 744   /* Select condition that is not TRUTH_NOT_EXPR.  */
 745   tmp_cond = (tree) (first_edge->src)->aux;
 746   gcc_assert (tmp_cond);
 747
 748   if (TREE_CODE (tmp_cond) == TRUTH_NOT_EXPR)
 749     {
 750       edge tmp_edge;
 751
 752       tmp_edge = first_edge;
 753       first_edge = second_edge;
 754       second_edge = tmp_edge;
 755     }
 756
 757   /* Check if FIRST_BB is loop header or not and make sure that
 758      FIRST_BB does not dominate SECOND_BB.  */
 759   if (first_edge->src == loop->header
 760       || dominated_by_p (CDI_DOMINATORS,
 761                          second_edge->src, first_edge->src))
 762     {
 763       *cond = (tree) (second_edge->src)->aux;
 764
 765       /* If there is a condition on an incoming edge,
 766          AND it with the incoming bb predicate.  */
 767       if (second_edge->aux)
 768         *cond = build2 (TRUTH_AND_EXPR, boolean_type_node,
 769                         *cond, (tree) second_edge->aux);
 770
 771       if (TREE_CODE (*cond) == TRUTH_NOT_EXPR)
 772         /* We can be smart here and choose inverted
 773            condition without switching bbs.  */
 774         *cond = invert_truthvalue (*cond);
 775       else
 776         /* Select non loop header bb.  */
 777         first_edge = second_edge;
 778     }
 779   else
 780     {
 781       /* FIRST_BB is not loop header */
 782       *cond = (tree) (first_edge->src)->aux;
 783
 784       /* If there is a condition on an incoming edge,
 785          AND it with the incoming bb predicate.  */
 786       if (first_edge->aux)
 787         *cond = build2 (TRUTH_AND_EXPR, boolean_type_node,
 788                         *cond, (tree) first_edge->aux);
 789     }
 790
 791   /* Create temp. for the condition. Vectorizer prefers to have gimple
 792      value as condition. Various targets use different means to communicate
 793      condition in vector compare operation. Using gimple value allows
 794      compiler to emit vector compare and select RTL without exposing
 795      compare's result.  */
 796   *cond = force_gimple_operand_gsi (gsi, unshare_expr (*cond),
 797                                     false, NULL_TREE,
 798                                     true, GSI_SAME_STMT);
 799   if (!is_gimple_reg (*cond) && !is_gimple_condexpr (*cond))
 800     {
 801       gimple new_stmt;
 802
 803       new_stmt = ifc_temp_var (TREE_TYPE (*cond), unshare_expr (*cond));
 804       gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
 805       *cond = gimple_assign_lhs (new_stmt);
 806     }
 807
 808   gcc_assert (*cond);
 809
 810   return first_edge->src;
 811 }
 812
 813
 814 /* Replace PHI node with conditional modify expr using COND.
 815    This routine does not handle PHI nodes with more than two arguments.
 816    For example,
 817      S1: A = PHI <x1(1), x2(5)
 818    is converted into,
 819      S2: A = cond ? x1 : x2;
 820    S2 is inserted at the top of basic block's statement list.
 821    When COND is true, phi arg from TRUE_BB is selected.
 822 */
 823
 824 static void
 825 replace_phi_with_cond_gimple_assign_stmt (gimple phi, tree cond,
 826                                           basic_block true_bb,
 827                                           gimple_stmt_iterator *gsi)
 828 {
 829   gimple new_stmt;
 830   basic_block bb;
 831   tree rhs;
 832   tree arg_0, arg_1;
 833
 834   gcc_assert (gimple_code (phi) == GIMPLE_PHI);
 835
 836   /* If this is not filtered earlier, then now it is too late.  */
 837   gcc_assert (gimple_phi_num_args (phi) == 2);
 838
 839   /* Find basic block and initialize iterator.  */
 840   bb = gimple_bb (phi);
 841
 842   /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr.  */
 843   if (EDGE_PRED (bb, 1)->src == true_bb)
 844     {
 845       arg_0 = gimple_phi_arg_def (phi, 1);
 846       arg_1 = gimple_phi_arg_def (phi, 0);
 847     }
 848   else
 849     {
 850       arg_0 = gimple_phi_arg_def (phi, 0);
 851       arg_1 = gimple_phi_arg_def (phi, 1);
 852     }
 853
 854   /* Build new RHS using selected condition and arguments.  */
 855   rhs = build3 (COND_EXPR, TREE_TYPE (PHI_RESULT (phi)),
 856                 unshare_expr (cond), unshare_expr (arg_0),
 857                 unshare_expr (arg_1));
 858
 859   /* Create new GIMPLE_ASSIGN statement using RHS.  */
 860   new_stmt = gimple_build_assign (unshare_expr (PHI_RESULT (phi)), rhs);
 861
 862   /* Make new statement definition of the original phi result.  */
 863   SSA_NAME_DEF_STMT (gimple_phi_result (phi)) = new_stmt;
 864
 865   /* Insert using iterator.  */
 866   gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
 867   update_stmt (new_stmt);
 868
 869   if (dump_file && (dump_flags & TDF_DETAILS))
 870     {
 871       fprintf (dump_file, "new phi replacement stmt\n");
 872       print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM);
 873     }
 874 }
 875
 876 /* Process phi nodes for the given  LOOP.  Replace phi nodes with cond
 877    modify expr.  */
 878
 879 static void
 880 process_phi_nodes (struct loop *loop)
 881 {
 882   basic_block bb;
 883   unsigned int orig_loop_num_nodes = loop->num_nodes;
 884   unsigned int i;
 885
 886   /* Replace phi nodes with cond. modify expr.  */
 887   for (i = 1; i < orig_loop_num_nodes; i++)
 888     {
 889       gimple phi;
 890       tree cond = NULL_TREE;
 891       gimple_stmt_iterator gsi, phi_gsi;
 892       basic_block true_bb = NULL;
 893       bb = ifc_bbs[i];
 894
 895       if (bb == loop->header)
 896         continue;
 897
 898       phi_gsi = gsi_start_phis (bb);
 899       gsi = gsi_after_labels (bb);
 900
 901       /* BB has two predecessors. Using predecessor's aux field, set
 902          appropriate condition for the PHI node replacement.  */
 903       if (!gsi_end_p (phi_gsi))
 904         true_bb = find_phi_replacement_condition (loop, bb, &cond, &gsi);
 905
 906       while (!gsi_end_p (phi_gsi))
 907         {
 908           phi = gsi_stmt (phi_gsi);
 909           replace_phi_with_cond_gimple_assign_stmt (phi, cond, true_bb, &gsi);
 910           release_phi_node (phi);
 911           gsi_next (&phi_gsi);
 912         }
 913       set_phi_nodes (bb, NULL);
 914     }
 915   return;
 916 }
 917
 918 /* Combine all basic block from the given LOOP into one or two super
 919    basic block.  Replace PHI nodes with conditional modify expression.  */
 920
 921 static void
 922 combine_blocks (struct loop *loop)
 923 {
 924   basic_block bb, exit_bb, merge_target_bb;
 925   unsigned int orig_loop_num_nodes = loop->num_nodes;
 926   unsigned int i;
 927   edge e;
 928   edge_iterator ei;
 929
 930   /* Process phi nodes to prepare blocks for merge.  */
 931   process_phi_nodes (loop);
 932
 933   /* Merge basic blocks.  First remove all the edges in the loop, except
 934      for those from the exit block.  */
 935   exit_bb = NULL;
 936   for (i = 0; i < orig_loop_num_nodes; i++)
 937     {
 938       bb = ifc_bbs[i];
 939       if (bb_with_exit_edge_p (loop, bb))
 940         {
 941           exit_bb = bb;
 942           break;
 943         }
 944     }
 945   gcc_assert (exit_bb != loop->latch);
 946
 947   for (i = 1; i < orig_loop_num_nodes; i++)
 948     {
 949       bb = ifc_bbs[i];
 950
 951       for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei));)
 952         {
 953           if (e->src == exit_bb)
 954             ei_next (&ei);
 955           else
 956             remove_edge (e);
 957         }
 958     }
 959
 960   if (exit_bb != NULL)
 961     {
 962       if (exit_bb != loop->header)
 963         {
 964           /* Connect this node with loop header.  */
 965           make_edge (loop->header, exit_bb, EDGE_FALLTHRU);
 966           set_immediate_dominator (CDI_DOMINATORS, exit_bb, loop->header);
 967         }
 968
 969       /* Redirect non-exit edges to loop->latch.  */
 970       FOR_EACH_EDGE (e, ei, exit_bb->succs)
 971         {
 972           if (!loop_exit_edge_p (loop, e))
 973             redirect_edge_and_branch (e, loop->latch);
 974         }
 975       set_immediate_dominator (CDI_DOMINATORS, loop->latch, exit_bb);
 976     }
 977   else
 978     {
 979       /* If the loop does not have exit then reconnect header and latch.  */
 980       make_edge (loop->header, loop->latch, EDGE_FALLTHRU);
 981       set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header);
 982     }
 983
 984   merge_target_bb = loop->header;
 985   for (i = 1; i < orig_loop_num_nodes; i++)
 986     {
 987       gimple_stmt_iterator gsi;
 988       gimple_stmt_iterator last;
 989
 990       bb = ifc_bbs[i];
 991
 992       if (bb == exit_bb || bb == loop->latch)
 993         continue;
 994
 995       /* Remove labels and make stmts member of loop->header.  */
 996       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
 997         {
 998           if (gimple_code (gsi_stmt (gsi)) == GIMPLE_LABEL)
 999             gsi_remove (&gsi, true);
1000           else
1001             {
1002               gimple_set_bb (gsi_stmt (gsi), merge_target_bb);
1003               gsi_next (&gsi);
1004             }
1005         }
1006
1007       /* Update stmt list.  */
1008       last = gsi_last_bb (merge_target_bb);
1009       gsi_insert_seq_after (&last, bb_seq (bb), GSI_NEW_STMT);
1010       set_bb_seq (bb, NULL);
1011
1012       delete_basic_block (bb);
1013     }
1014
1015   /* Now if possible, merge loop header and block with exit edge.
1016      This reduces number of basic blocks to 2. Auto vectorizer addresses
1017      loops with two nodes only.  FIXME: Use cleanup_tree_cfg().  */
1018   if (exit_bb
1019       && exit_bb != loop->header
1020       && can_merge_blocks_p (loop->header, exit_bb))
1021     merge_blocks (loop->header, exit_bb);
1022 }
1023
1024 /* Make a new temp variable of type TYPE. Add GIMPLE_ASSIGN to assign EXP
1025    to the new variable.  */
1026
1027 static gimple
1028 ifc_temp_var (tree type, tree exp)
1029 {
1030   const char *name = "_ifc_";
1031   tree var, new_name;
1032   gimple stmt;
1033
1034   /* Create new temporary variable.  */
1035   var = create_tmp_var (type, name);
1036   add_referenced_var (var);
1037
1038   /* Build new statement to assign EXP to new variable.  */
1039   stmt = gimple_build_assign (var, exp);
1040
1041   /* Get SSA name for the new variable and set make new statement
1042      its definition statement.  */
1043   new_name = make_ssa_name (var, stmt);
1044   gimple_assign_set_lhs (stmt, new_name);
1045   SSA_NAME_DEF_STMT (new_name) = stmt;
1046   update_stmt (stmt);
1047
1048   return stmt;
1049 }
1050
1051
1052 /* Return TRUE iff, all pred blocks of BB are visited.
1053    Bitmap VISITED keeps history of visited blocks.  */
1054
1055 static bool
1056 pred_blocks_visited_p (basic_block bb, bitmap *visited)
1057 {
1058   edge e;
1059   edge_iterator ei;
1060   FOR_EACH_EDGE (e, ei, bb->preds)
1061     if (!bitmap_bit_p (*visited, e->src->index))
1062       return false;
1063
1064   return true;
1065 }
1066
1067 /* Get body of a LOOP in suitable order for if-conversion.
1068    It is caller's responsibility to deallocate basic block
1069    list.  If-conversion suitable order is, BFS order with one
1070    additional constraint. Select block in BFS block, if all
1071    pred are already selected.  */
1072
1073 static basic_block *
1074 get_loop_body_in_if_conv_order (const struct loop *loop)
1075 {
1076   basic_block *blocks, *blocks_in_bfs_order;
1077   basic_block bb;
1078   bitmap visited;
1079   unsigned int index = 0;
1080   unsigned int visited_count = 0;
1081
1082   gcc_assert (loop->num_nodes);
1083   gcc_assert (loop->latch != EXIT_BLOCK_PTR);
1084
1085   blocks = XCNEWVEC (basic_block, loop->num_nodes);
1086   visited = BITMAP_ALLOC (NULL);
1087
1088   blocks_in_bfs_order = get_loop_body_in_bfs_order (loop);
1089
1090   index = 0;
1091   while (index < loop->num_nodes)
1092     {
1093       bb = blocks_in_bfs_order [index];
1094
1095       if (bb->flags & BB_IRREDUCIBLE_LOOP)
1096         {
1097           free (blocks_in_bfs_order);
1098           BITMAP_FREE (visited);
1099           free (blocks);
1100           return NULL;
1101         }
1102       if (!bitmap_bit_p (visited, bb->index))
1103         {
1104           if (pred_blocks_visited_p (bb, &visited)
1105               || bb == loop->header)
1106             {
1107               /* This block is now visited.  */
1108               bitmap_set_bit (visited, bb->index);
1109               blocks[visited_count++] = bb;
1110             }
1111         }
1112       index++;
1113       if (index == loop->num_nodes
1114           && visited_count != loop->num_nodes)
1115         {
1116           /* Not done yet.  */
1117           index = 0;
1118         }
1119     }
1120   free (blocks_in_bfs_order);
1121   BITMAP_FREE (visited);
1122   return blocks;
1123 }
1124
1125 /* Return true if one of the basic block BB edge is exit of LOOP.  */
1126
1127 static bool
1128 bb_with_exit_edge_p (struct loop *loop, basic_block bb)
1129 {
1130   edge e;
1131   edge_iterator ei;
1132   bool exit_edge_found = false;
1133
1134   FOR_EACH_EDGE (e, ei, bb->succs)
1135     if (loop_exit_edge_p (loop, e))
1136       {
1137         exit_edge_found = true;
1138         break;
1139       }
1140
1141   return exit_edge_found;
1142 }
1143
1144 /* Tree if-conversion pass management.  */
1145
1146 static unsigned int
1147 main_tree_if_conversion (void)
1148 {
1149   loop_iterator li;
1150   struct loop *loop;
1151
1152   if (number_of_loops () <= 1)
1153     return 0;
1154
1155   FOR_EACH_LOOP (li, loop, 0)
1156     {
1157       tree_if_conversion (loop, true);
1158     }
1159   return 0;
1160 }
1161
1162 static bool
1163 gate_tree_if_conversion (void)
1164 {
1165   return flag_tree_vectorize != 0;
1166 }
1167
1168 struct gimple_opt_pass pass_if_conversion =
1169 {
1170  {
1171   GIMPLE_PASS,
1172   "ifcvt",                              /* name */
1173   gate_tree_if_conversion,              /* gate */
1174   main_tree_if_conversion,              /* execute */
1175   NULL,                                 /* sub */
1176   NULL,                                 /* next */
1177   0,                                    /* static_pass_number */
1178   TV_NONE,                              /* tv_id */
1179   PROP_cfg | PROP_ssa,                  /* properties_required */
1180   0,                                    /* properties_provided */
1181   0,                                    /* properties_destroyed */
1182   0,                                    /* todo_flags_start */
1183   TODO_dump_func | TODO_verify_loops | TODO_verify_stmts | TODO_verify_flow
1184                                         /* todo_flags_finish */
1185  }
1186 };