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