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