gcc/tree-if-conv.c

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