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