contrib/gcc-4.0/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, 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;
 643       tree tmp_stmt = NULL_TREE;
 644       tree tmp_stmts1 = NULL_TREE;
 645       tree tmp_stmts2 = NULL_TREE;
 646       prev_cond = force_gimple_operand (unshare_expr (prev_cond),
 647                                         &tmp_stmts1, true, NULL);
 648       if (tmp_stmts1)
 649         bsi_insert_before (bsi, tmp_stmts1, BSI_SAME_STMT);
 650
 651       cond = force_gimple_operand (unshare_expr (cond),
 652                                    &tmp_stmts2, true, NULL);
 653       if (tmp_stmts2)
 654         bsi_insert_before (bsi, tmp_stmts2, BSI_SAME_STMT);
 655
 656       /* new_cond == prev_cond AND cond */
 657       tmp = build (TRUTH_AND_EXPR, boolean_type_node,
 658                    unshare_expr (prev_cond), cond);
 659       tmp_stmt = ifc_temp_var (boolean_type_node, tmp);
 660       bsi_insert_before (bsi, tmp_stmt, BSI_SAME_STMT);
 661       new_cond = TREE_OPERAND (tmp_stmt, 0);
 662     }
 663   add_to_predicate_list (bb, new_cond);
 664   return new_cond;
 665 }
 666
 667 /* During if-conversion aux field from basic block is used to hold predicate
 668    list. Clean each basic block's predicate list for the given LOOP.  */
 669
 670 static void
 671 clean_predicate_lists (struct loop *loop)
 672 {
 673   basic_block *bb;
 674   unsigned int i;
 675   bb = get_loop_body (loop);
 676   for (i = 0; i < loop->num_nodes; i++)
 677     bb[i]->aux = NULL;
 678
 679   free (bb);
 680 }
 681
 682 /* Basic block BB has two predecessors. Using predecessor's aux field, set
 683    appropriate condition COND for the PHI node replacement. Return true block
 684    whose phi arguments are selected when cond is true.  */
 685
 686 static basic_block
 687 find_phi_replacement_condition (basic_block bb, tree *cond,
 688                                 block_stmt_iterator *bsi)
 689 {
 690   edge e;
 691   basic_block p1 = NULL;
 692   basic_block p2 = NULL;
 693   basic_block true_bb = NULL;
 694   tree tmp_cond;
 695   edge_iterator ei;
 696
 697   FOR_EACH_EDGE (e, ei, bb->preds)
 698     {
 699       if (p1 == NULL)
 700         p1 = e->src;
 701       else
 702         {
 703           gcc_assert (!p2);
 704           p2 = e->src;
 705         }
 706     }
 707
 708   /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr.  */
 709   tmp_cond = p1->aux;
 710   if (TREE_CODE (tmp_cond) == TRUTH_NOT_EXPR)
 711     {
 712       *cond  = p2->aux;
 713       true_bb = p2;
 714     }
 715   else
 716     {
 717       *cond  = p1->aux;
 718       true_bb = p1;
 719     }
 720
 721   /* Create temp. for the condition. Vectorizer prefers to have gimple
 722      value as condition. Various targets use different means to communicate
 723      condition in vector compare operation. Using gimple value allows compiler
 724      to emit vector compare and select RTL without exposing compare's result.  */
 725   if (!is_gimple_reg (*cond) && !is_gimple_condexpr (*cond))
 726     {
 727       tree new_stmt;
 728
 729       new_stmt = ifc_temp_var (TREE_TYPE (*cond), unshare_expr (*cond));
 730       bsi_insert_after (bsi, new_stmt, BSI_SAME_STMT);
 731       bsi_next (bsi);
 732       *cond = TREE_OPERAND (new_stmt, 0);
 733     }
 734
 735   gcc_assert (*cond);
 736
 737   return true_bb;
 738 }
 739
 740
 741 /* Replace PHI node with conditional modify expr using COND.
 742    This routine does not handle PHI nodes with more than two arguments.
 743    For example,
 744      S1: A = PHI <x1(1), x2(5)
 745    is converted into,
 746      S2: A = cond ? x1 : x2;
 747    S2 is inserted at the top of basic block's statement list.
 748    When COND is true, phi arg from TRUE_BB is selected.
 749 */
 750
 751 static void
 752 replace_phi_with_cond_modify_expr (tree phi, tree cond, basic_block true_bb,
 753                                    block_stmt_iterator *bsi)
 754 {
 755   tree new_stmt;
 756   basic_block bb;
 757   tree rhs;
 758   tree arg_0, arg_1;
 759
 760   gcc_assert (TREE_CODE (phi) == PHI_NODE);
 761
 762   /* If this is not filtered earlier, then now it is too late.  */
 763   gcc_assert (PHI_NUM_ARGS (phi) == 2);
 764
 765   /* Find basic block and initialize iterator.  */
 766   bb = bb_for_stmt (phi);
 767
 768   new_stmt = NULL_TREE;
 769   arg_0 = NULL_TREE;
 770   arg_1 = NULL_TREE;
 771
 772   /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr.  */
 773   if (EDGE_PRED (bb, 1)->src == true_bb)
 774     {
 775       arg_0 = PHI_ARG_DEF (phi, 1);
 776       arg_1 = PHI_ARG_DEF (phi, 0);
 777     }
 778   else
 779     {
 780       arg_0 = PHI_ARG_DEF (phi, 0);
 781       arg_1 = PHI_ARG_DEF (phi, 1);
 782     }
 783
 784   /* Build new RHS using selected condition and arguments.  */
 785   rhs = build (COND_EXPR, TREE_TYPE (PHI_RESULT (phi)),
 786                unshare_expr (cond), unshare_expr (arg_0),
 787                unshare_expr (arg_1));
 788
 789   /* Create new MODIFY expression using RHS.  */
 790   new_stmt = build (MODIFY_EXPR, TREE_TYPE (PHI_RESULT (phi)),
 791                     unshare_expr (PHI_RESULT (phi)), rhs);
 792
 793   /* Make new statement definition of the original phi result.  */
 794   SSA_NAME_DEF_STMT (PHI_RESULT (phi)) = new_stmt;
 795
 796   /* Set basic block and insert using iterator.  */
 797   set_bb_for_stmt (new_stmt, bb);
 798
 799   bsi_insert_after (bsi, new_stmt, BSI_SAME_STMT);
 800   bsi_next (bsi);
 801
 802   modify_stmt (new_stmt);
 803
 804   if (dump_file && (dump_flags & TDF_DETAILS))
 805     {
 806       fprintf (dump_file, "new phi replacement stmt\n");
 807       print_generic_stmt (dump_file, new_stmt, TDF_SLIM);
 808     }
 809 }
 810
 811 /* Process phi nodes for the given  LOOP.  Replace phi nodes with cond
 812    modify expr.  */
 813
 814 static void
 815 process_phi_nodes (struct loop *loop)
 816 {
 817   basic_block bb;
 818   unsigned int orig_loop_num_nodes = loop->num_nodes;
 819   unsigned int i;
 820
 821   /* Replace phi nodes with cond. modify expr.  */
 822   for (i = 1; i < orig_loop_num_nodes; i++)
 823     {
 824       tree phi, cond;
 825       block_stmt_iterator bsi;
 826       basic_block true_bb = NULL;
 827       bb = ifc_bbs[i];
 828
 829       if (bb == loop->header)
 830         continue;
 831
 832       phi = phi_nodes (bb);
 833       bsi = bsi_after_labels (bb);
 834
 835       /* BB has two predecessors. Using predecessor's aux field, set
 836          appropriate condition for the PHI node replacement.  */
 837       if (phi)
 838         true_bb = find_phi_replacement_condition (bb, &cond, &bsi);
 839
 840       while (phi)
 841         {
 842           tree next = PHI_CHAIN (phi);
 843           replace_phi_with_cond_modify_expr (phi, cond, true_bb, &bsi);
 844           release_phi_node (phi);
 845           phi = next;
 846         }
 847       bb_ann (bb)->phi_nodes = NULL;
 848     }
 849   return;
 850 }
 851
 852 /* Combine all basic block from the given LOOP into one or two super
 853    basic block.  Replace PHI nodes with conditional modify expression.  */
 854
 855 static void
 856 combine_blocks (struct loop *loop)
 857 {
 858   basic_block bb, exit_bb, merge_target_bb;
 859   unsigned int orig_loop_num_nodes = loop->num_nodes;
 860   unsigned int i;
 861   unsigned int n_exits;
 862   edge *exits = get_loop_exit_edges (loop, &n_exits);
 863   /* Process phi nodes to prepare blocks for merge.  */
 864   process_phi_nodes (loop);
 865
 866   exit_bb = NULL;
 867
 868   /* Merge basic blocks */
 869   merge_target_bb = loop->header;
 870   for (i = 1; i < orig_loop_num_nodes; i++)
 871     {
 872       edge e;
 873       block_stmt_iterator bsi;
 874       tree_stmt_iterator last;
 875
 876       bb = ifc_bbs[i];
 877
 878       if (!exit_bb && bb_with_exit_edge_p (bb))
 879           exit_bb = bb;
 880
 881       if (bb == exit_bb)
 882         {
 883           edge new_e;
 884           edge_iterator ei;
 885
 886           /* Connect this node with loop header.  */
 887           new_e = make_edge (ifc_bbs[0], bb, EDGE_FALLTHRU);
 888           set_immediate_dominator (CDI_DOMINATORS, bb, ifc_bbs[0]);
 889
 890           if (exit_bb != loop->latch)
 891             {
 892               /* Redirect non-exit edge to loop->latch.  */
 893               FOR_EACH_EDGE (e, ei, bb->succs)
 894                 if (!(e->flags & EDGE_LOOP_EXIT))
 895                   {
 896                     redirect_edge_and_branch (e, loop->latch);
 897                     set_immediate_dominator (CDI_DOMINATORS, loop->latch, bb);
 898                   }
 899             }
 900           continue;
 901         }
 902
 903       if (bb == loop->latch && empty_block_p (bb))
 904         continue;
 905
 906       /* It is time to remove this basic block.  First remove edges.  */
 907       while (EDGE_COUNT (bb->preds) > 0)
 908         remove_edge (EDGE_PRED (bb, 0));
 909
 910       /* This is loop latch and loop does not have exit then do not
 911          delete this basic block. Just remove its PREDS and reconnect
 912          loop->header and loop->latch blocks.  */
 913       if (bb == loop->latch && n_exits == 0)
 914         {
 915           exits = NULL; /* To suppress unused warning.  */
 916           make_edge (loop->header, loop->latch, EDGE_FALLTHRU);
 917           set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header);
 918           continue;
 919         }
 920
 921       while (EDGE_COUNT (bb->succs) > 0)
 922         remove_edge (EDGE_SUCC (bb, 0));
 923
 924       /* Remove labels and make stmts member of loop->header.  */
 925       for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
 926         {
 927           if (TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR)
 928             bsi_remove (&bsi);
 929           else
 930             {
 931               set_bb_for_stmt (bsi_stmt (bsi), merge_target_bb);
 932               bsi_next (&bsi);
 933             }
 934         }
 935
 936       /* Update stmt list.  */
 937       last = tsi_last (merge_target_bb->stmt_list);
 938       tsi_link_after (&last, bb->stmt_list, TSI_NEW_STMT);
 939       bb->stmt_list = NULL;
 940
 941       /* Update dominator info.  */
 942       if (dom_computed[CDI_DOMINATORS])
 943         delete_from_dominance_info (CDI_DOMINATORS, bb);
 944       if (dom_computed[CDI_POST_DOMINATORS])
 945         delete_from_dominance_info (CDI_POST_DOMINATORS, bb);
 946
 947       /* Remove basic block.  */
 948       if (bb == loop->latch)
 949         loop->latch = merge_target_bb;
 950       remove_bb_from_loops (bb);
 951       expunge_block (bb);
 952     }
 953
 954   /* Now if possible, merge loop header and block with exit edge.
 955      This reduces number of basic blocks to 2. Auto vectorizer addresses
 956      loops with two nodes only.  FIXME: Use cleanup_tree_cfg().  */
 957   if (exit_bb
 958       && loop->header != loop->latch
 959       && exit_bb != loop->latch
 960       && empty_block_p (loop->latch))
 961     {
 962       if (can_merge_blocks_p (loop->header, exit_bb))
 963         {
 964           remove_bb_from_loops (exit_bb);
 965           merge_blocks (loop->header, exit_bb);
 966         }
 967     }
 968 }
 969
 970 /* Make new  temp variable of type TYPE. Add MODIFY_EXPR to assign EXP
 971    to the new variable.  */
 972
 973 static tree
 974 ifc_temp_var (tree type, tree exp)
 975 {
 976   const char *name = "_ifc_";
 977   tree var, stmt, new_name;
 978
 979   if (is_gimple_reg (exp))
 980     return exp;
 981
 982   /* Create new temporary variable.  */
 983   var = create_tmp_var (type, name);
 984   add_referenced_tmp_var (var);
 985
 986   /* Build new statement to assign EXP to new variable.  */
 987   stmt = build (MODIFY_EXPR, type, var, exp);
 988
 989   /* Get SSA name for the new variable and set make new statement
 990      its definition statement.  */
 991   new_name = make_ssa_name (var, stmt);
 992   TREE_OPERAND (stmt, 0) = new_name;
 993   SSA_NAME_DEF_STMT (new_name) = stmt;
 994
 995   return stmt;
 996 }
 997
 998
 999 /* Return TRUE iff, all pred blocks of BB are visited.
1000    Bitmap VISITED keeps history of visited blocks.  */
1001
1002 static bool
1003 pred_blocks_visited_p (basic_block bb, bitmap *visited)
1004 {
1005   edge e;
1006   edge_iterator ei;
1007   FOR_EACH_EDGE (e, ei, bb->preds)
1008     if (!bitmap_bit_p (*visited, e->src->index))
1009       return false;
1010
1011   return true;
1012 }
1013
1014 /* Get body of a LOOP in suitable order for if-conversion.
1015    It is caller's responsibility to deallocate basic block
1016    list.  If-conversion suitable order is, BFS order with one
1017    additional constraint. Select block in BFS block, if all
1018    pred are already selected.  */
1019
1020 static basic_block *
1021 get_loop_body_in_if_conv_order (const struct loop *loop)
1022 {
1023   basic_block *blocks, *blocks_in_bfs_order;
1024   basic_block bb;
1025   bitmap visited;
1026   unsigned int index = 0;
1027   unsigned int visited_count = 0;
1028
1029   gcc_assert (loop->num_nodes);
1030   gcc_assert (loop->latch != EXIT_BLOCK_PTR);
1031
1032   blocks = xcalloc (loop->num_nodes, sizeof (basic_block));
1033   visited = BITMAP_ALLOC (NULL);
1034
1035   blocks_in_bfs_order = get_loop_body_in_bfs_order (loop);
1036
1037   index = 0;
1038   while (index < loop->num_nodes)
1039     {
1040       bb = blocks_in_bfs_order [index];
1041
1042       if (bb->flags & BB_IRREDUCIBLE_LOOP)
1043         {
1044           free (blocks_in_bfs_order);
1045           BITMAP_FREE (visited);
1046           free (blocks);
1047           return NULL;
1048         }
1049       if (!bitmap_bit_p (visited, bb->index))
1050         {
1051           if (pred_blocks_visited_p (bb, &visited)
1052               || bb == loop->header)
1053             {
1054               /* This block is now visited.  */
1055               bitmap_set_bit (visited, bb->index);
1056               blocks[visited_count++] = bb;
1057             }
1058         }
1059       index++;
1060       if (index == loop->num_nodes
1061           && visited_count != loop->num_nodes)
1062         {
1063           /* Not done yet.  */
1064           index = 0;
1065         }
1066     }
1067   free (blocks_in_bfs_order);
1068   BITMAP_FREE (visited);
1069   return blocks;
1070 }
1071
1072 /* Return true if one of the basic block BB edge is loop exit.  */
1073
1074 static bool
1075 bb_with_exit_edge_p (basic_block bb)
1076 {
1077   edge e;
1078   edge_iterator ei;
1079   bool exit_edge_found = false;
1080
1081   FOR_EACH_EDGE (e, ei, bb->succs)
1082     if (e->flags & EDGE_LOOP_EXIT)
1083       {
1084         exit_edge_found = true;
1085         break;
1086       }
1087
1088   return exit_edge_found;
1089 }
1090
1091 /* Tree if-conversion pass management.  */
1092
1093 static void
1094 main_tree_if_conversion (void)
1095 {
1096   unsigned i, loop_num;
1097   struct loop *loop;
1098
1099   if (!current_loops)
1100     return;
1101
1102   loop_num = current_loops->num;
1103   for (i = 0; i < loop_num; i++)
1104     {
1105       loop =  current_loops->parray[i];
1106       if (!loop)
1107       continue;
1108
1109       tree_if_conversion (loop, true);
1110     }
1111
1112 }
1113
1114 static bool
1115 gate_tree_if_conversion (void)
1116 {
1117   return flag_tree_vectorize != 0;
1118 }
1119
1120 struct tree_opt_pass pass_if_conversion =
1121 {
1122   "ifcvt",                           /* name */
1123   gate_tree_if_conversion,           /* gate */
1124   main_tree_if_conversion,           /* execute */
1125   NULL,                              /* sub */
1126   NULL,                              /* next */
1127   0,                                 /* static_pass_number */
1128   0,                                 /* tv_id */
1129   PROP_cfg | PROP_ssa | PROP_alias,  /* properties_required */
1130   0,                                 /* properties_provided */
1131   0,                                 /* properties_destroyed */
1132   TODO_dump_func,                    /* todo_flags_start */
1133   TODO_dump_func
1134     | TODO_verify_ssa
1135     | TODO_verify_stmts
1136     | TODO_verify_flow,              /* todo_flags_finish */
1137   0                                  /* letter */
1138 };