gcc/tree-if-conv.c

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