gcc/tree-if-conv.c

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