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 (struct loop *, basic_block);
 130
 131 /* List of basic blocks in if-conversion-suitable order.  */
 132 static basic_block *ifc_bbs;
 133
 134 /* Main entry point.
 135    Apply if-conversion to the LOOP. Return true if successful otherwise return
 136    false. If false is returned then loop remains unchanged.
 137    FOR_VECTORIZER is a boolean flag. It indicates whether if-conversion is used
 138    for vectorizer or not. If it is used for vectorizer, additional checks are
 139    used. (Vectorization checks are not yet implemented).  */
 140
 141 static bool
 142 tree_if_conversion (struct loop *loop, bool for_vectorizer)
 143 {
 144   basic_block bb;
 145   block_stmt_iterator itr;
 146   tree cond;
 147   unsigned int i;
 148
 149   ifc_bbs = NULL;
 150
 151   /* if-conversion is not appropriate for all loops. First, check if loop  is
 152      if-convertible or not.  */
 153   if (!if_convertible_loop_p (loop, for_vectorizer))
 154     {
 155       if (dump_file && (dump_flags & TDF_DETAILS))
 156         fprintf (dump_file,"-------------------------\n");
 157       if (ifc_bbs)
 158         {
 159           free (ifc_bbs);
 160           ifc_bbs = NULL;
 161         }
 162       free_dominance_info (CDI_POST_DOMINATORS);
 163       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 (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   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;
 275   edge true_edge, false_edge;
 276
 277   gcc_assert (TREE_CODE (stmt) == COND_EXPR);
 278
 279   c = COND_EXPR_COND (stmt);
 280
 281   /* Create temp. for condition.  */
 282   if (!is_gimple_condexpr (c))
 283     {
 284       tree new_stmt;
 285       new_stmt = ifc_temp_var (TREE_TYPE (c), unshare_expr (c));
 286       bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT);
 287       c = TREE_OPERAND (new_stmt, 0);
 288     }
 289
 290   extract_true_false_edges_from_block (bb_for_stmt (stmt),
 291                                        &true_edge, &false_edge);
 292
 293   /* Add new condition into destination's predicate list.  */
 294
 295   /* If 'c' is true then TRUE_EDGE is taken.  */
 296   add_to_dst_predicate_list (loop, true_edge->dest, cond,
 297                              unshare_expr (c), bsi);
 298
 299   if (!is_gimple_reg(c) && is_gimple_condexpr (c))
 300     {
 301       tree new_stmt;
 302       new_stmt = ifc_temp_var (TREE_TYPE (c), unshare_expr (c));
 303       bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT);
 304       c = TREE_OPERAND (new_stmt, 0);
 305     }
 306
 307   /* If 'c' is false then FALSE_EDGE is taken.  */
 308   c2 = invert_truthvalue (unshare_expr (c));
 309   add_to_dst_predicate_list (loop, false_edge->dest, cond, c2, bsi);
 310
 311   /* Now this conditional statement is redundant. Remove it.
 312      But, do not remove exit condition! Update exit condition
 313      using new condition.  */
 314   if (!bb_with_exit_edge_p (loop, bb_for_stmt (stmt)))
 315     {
 316       bsi_remove (bsi);
 317       cond = NULL_TREE;
 318     }
 319   return;
 320 }
 321
 322 /* Return true, iff PHI is if-convertible. PHI is part of loop LOOP
 323    and it belongs to basic block BB.
 324    PHI is not if-convertible
 325    - if it has more than 2 arguments.
 326    - Virtual PHI is immediately used in another PHI node.  */
 327
 328 static bool
 329 if_convertible_phi_p (struct loop *loop, basic_block bb, tree phi)
 330 {
 331   if (dump_file && (dump_flags & TDF_DETAILS))
 332     {
 333       fprintf (dump_file, "-------------------------\n");
 334       print_generic_stmt (dump_file, phi, TDF_SLIM);
 335     }
 336
 337   if (bb != loop->header && PHI_NUM_ARGS (phi) != 2)
 338     {
 339       if (dump_file && (dump_flags & TDF_DETAILS))
 340         fprintf (dump_file, "More than two phi node args.\n");
 341       return false;
 342     }
 343
 344   if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
 345     {
 346       int j;
 347       dataflow_t df = get_immediate_uses (phi);
 348       int num_uses = num_immediate_uses (df);
 349       for (j = 0; j < num_uses; j++)
 350         {
 351           tree use = immediate_use (df, j);
 352           if (TREE_CODE (use) == PHI_NODE)
 353             {
 354               if (dump_file && (dump_flags & TDF_DETAILS))
 355                 fprintf (dump_file, "Difficult to handle this virtual phi.\n");
 356               return false;
 357             }
 358         }
 359     }
 360
 361   return true;
 362 }
 363
 364 /* Return true, if M_EXPR is if-convertible.
 365    MODIFY_EXPR is not if-convertible if,
 366    - It is not movable.
 367    - It could trap.
 368    - LHS is not var decl.
 369   MODIFY_EXPR is part of block BB, which is inside loop LOOP.
 370 */
 371
 372 static bool
 373 if_convertible_modify_expr_p (struct loop *loop, basic_block bb, tree m_expr)
 374 {
 375   if (dump_file && (dump_flags & TDF_DETAILS))
 376     {
 377       fprintf (dump_file, "-------------------------\n");
 378       print_generic_stmt (dump_file, m_expr, TDF_SLIM);
 379     }
 380
 381   /* Be conservative and do not handle immovable expressions.  */
 382   if (movement_possibility (m_expr) == MOVE_IMPOSSIBLE)
 383     {
 384       if (dump_file && (dump_flags & TDF_DETAILS))
 385         fprintf (dump_file, "stmt is movable. Don't take risk\n");
 386       return false;
 387     }
 388
 389   /* See if it needs speculative loading or not.  */
 390   if (bb != loop->header
 391       && tree_could_trap_p (TREE_OPERAND (m_expr, 1)))
 392     {
 393       if (dump_file && (dump_flags & TDF_DETAILS))
 394         fprintf (dump_file, "tree could trap...\n");
 395       return false;
 396     }
 397
 398   if (TREE_CODE (TREE_OPERAND (m_expr, 1)) == CALL_EXPR)
 399     {
 400       if (dump_file && (dump_flags & TDF_DETAILS))
 401         fprintf (dump_file, "CALL_EXPR \n");
 402       return false;
 403     }
 404
 405   if (TREE_CODE (TREE_OPERAND (m_expr, 0)) != SSA_NAME
 406       && bb != loop->header
 407       && !bb_with_exit_edge_p (loop, bb))
 408     {
 409       if (dump_file && (dump_flags & TDF_DETAILS))
 410         {
 411           fprintf (dump_file, "LHS is not var\n");
 412           print_generic_stmt (dump_file, m_expr, TDF_SLIM);
 413         }
 414       return false;
 415     }
 416
 417
 418   return true;
 419 }
 420
 421 /* Return true, iff STMT is if-convertible.
 422    Statement is if-convertible if,
 423    - It is if-convertible MODIFY_EXPR
 424    - IT is LABEL_EXPR, GOTO_EXPR or COND_EXPR.
 425    STMT is inside block BB, which is inside loop LOOP.  */
 426
 427 static bool
 428 if_convertible_stmt_p (struct loop *loop, basic_block bb, tree stmt)
 429 {
 430   switch (TREE_CODE (stmt))
 431     {
 432     case LABEL_EXPR:
 433       break;
 434
 435     case MODIFY_EXPR:
 436
 437       if (!if_convertible_modify_expr_p (loop, bb, stmt))
 438         return false;
 439       break;
 440
 441     case GOTO_EXPR:
 442     case COND_EXPR:
 443       break;
 444
 445     default:
 446       /* Don't know what to do with 'em so don't do anything.  */
 447       if (dump_file && (dump_flags & TDF_DETAILS))
 448         {
 449           fprintf (dump_file, "don't know what to do\n");
 450           print_generic_stmt (dump_file, stmt, TDF_SLIM);
 451         }
 452       return false;
 453       break;
 454     }
 455
 456   return true;
 457 }
 458
 459 /* Return true, iff BB is if-convertible.
 460    Note: This routine does _not_ check basic block statements and phis.
 461    Basic block is not if-convertible if,
 462    - Basic block is non-empty and it is after exit block (in BFS order).
 463    - Basic block is after exit block but before latch.
 464    - Basic block edge(s) is not normal.
 465    EXIT_BB_SEEN is true if basic block with exit edge is already seen.
 466    BB is inside loop LOOP.  */
 467
 468 static bool
 469 if_convertible_bb_p (struct loop *loop, basic_block bb, bool exit_bb_seen)
 470 {
 471   edge e;
 472   edge_iterator ei;
 473
 474   if (dump_file && (dump_flags & TDF_DETAILS))
 475     fprintf (dump_file, "----------[%d]-------------\n", bb->index);
 476
 477   if (exit_bb_seen)
 478     {
 479       if (bb != loop->latch)
 480         {
 481           if (dump_file && (dump_flags & TDF_DETAILS))
 482             fprintf (dump_file, "basic block after exit bb but before latch\n");
 483           return false;
 484         }
 485       else if (!empty_block_p (bb))
 486         {
 487           if (dump_file && (dump_flags & TDF_DETAILS))
 488             fprintf (dump_file, "non empty basic block after exit bb\n");
 489           return false;
 490         }
 491     }
 492
 493   /* Be less adventurous and handle only normal edges.  */
 494   FOR_EACH_EDGE (e, ei, bb->succs)
 495     if (e->flags &
 496         (EDGE_ABNORMAL_CALL | EDGE_EH | EDGE_ABNORMAL | EDGE_IRREDUCIBLE_LOOP))
 497       {
 498         if (dump_file && (dump_flags & TDF_DETAILS))
 499           fprintf (dump_file,"Difficult to handle edges\n");
 500         return false;
 501       }
 502
 503   return true;
 504 }
 505
 506 /* Return true, iff LOOP is if-convertible.
 507    LOOP is if-convertible if,
 508    - It is innermost.
 509    - It has two or more basic blocks.
 510    - It has only one exit.
 511    - Loop header is not the exit edge.
 512    - If its basic blocks and phi nodes are if convertible. See above for
 513      more info.
 514    FOR_VECTORIZER enables vectorizer specific checks. For example, support
 515    for vector conditions, data dependency checks etc.. (Not implemented yet).  */
 516
 517 static bool
 518 if_convertible_loop_p (struct loop *loop, bool for_vectorizer ATTRIBUTE_UNUSED)
 519 {
 520   tree phi;
 521   basic_block bb;
 522   block_stmt_iterator itr;
 523   unsigned int i;
 524   edge e;
 525   edge_iterator ei;
 526   bool exit_bb_seen = false;
 527
 528   /* Handle only inner most loop.  */
 529   if (!loop || loop->inner)
 530     {
 531       if (dump_file && (dump_flags & TDF_DETAILS))
 532         fprintf (dump_file, "not inner most loop\n");
 533       return false;
 534     }
 535
 536   /* If only one block, no need for if-conversion.  */
 537   if (loop->num_nodes <= 2)
 538     {
 539       if (dump_file && (dump_flags & TDF_DETAILS))
 540         fprintf (dump_file, "less than 2 basic blocks\n");
 541       return false;
 542     }
 543
 544   /* More than one loop exit is too much to handle.  */
 545   if (!loop->single_exit)
 546     {
 547       if (dump_file && (dump_flags & TDF_DETAILS))
 548         fprintf (dump_file, "multiple exits\n");
 549       return false;
 550     }
 551
 552   /* ??? Check target's vector conditional operation support for vectorizer.  */
 553
 554   /* If one of the loop header's edge is exit edge then do not apply
 555      if-conversion.  */
 556   FOR_EACH_EDGE (e, ei, loop->header->succs)
 557     {
 558       if (loop_exit_edge_p (loop, e))
 559         return false;
 560     }
 561
 562   compute_immediate_uses (TDFA_USE_OPS|TDFA_USE_VOPS, NULL);
 563
 564   calculate_dominance_info (CDI_DOMINATORS);
 565   calculate_dominance_info (CDI_POST_DOMINATORS);
 566
 567   /* Allow statements that can be handled during if-conversion.  */
 568   ifc_bbs = get_loop_body_in_if_conv_order (loop);
 569   if (!ifc_bbs)
 570     {
 571       if (dump_file && (dump_flags & TDF_DETAILS))
 572         fprintf (dump_file,"Irreducible loop\n");
 573       free_dominance_info (CDI_POST_DOMINATORS);
 574       return false;
 575     }
 576
 577   for (i = 0; i < loop->num_nodes; i++)
 578     {
 579       bb = ifc_bbs[i];
 580
 581       if (!if_convertible_bb_p (loop, bb, exit_bb_seen))
 582         return false;
 583
 584       /* Check statements.  */
 585       for (itr = bsi_start (bb); !bsi_end_p (itr); bsi_next (&itr))
 586         if (!if_convertible_stmt_p (loop, bb, bsi_stmt (itr)))
 587           return false;
 588       /* ??? Check data dependency for vectorizer.  */
 589
 590       /* What about phi nodes ? */
 591       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 592         if (!if_convertible_phi_p (loop, bb, phi))
 593           return false;
 594
 595       if (bb_with_exit_edge_p (loop, bb))
 596         exit_bb_seen = true;
 597     }
 598
 599   /* OK. Did not find any potential issues so go ahead in if-convert
 600      this loop. Now there is no looking back.  */
 601   if (dump_file)
 602     fprintf (dump_file,"Applying if-conversion\n");
 603
 604   free_dominance_info (CDI_POST_DOMINATORS);
 605   return true;
 606 }
 607
 608 /* Add condition COND into predicate list of basic block BB.  */
 609
 610 static void
 611 add_to_predicate_list (basic_block bb, tree new_cond)
 612 {
 613   tree cond = bb->aux;
 614
 615   if (cond)
 616     cond = fold (build (TRUTH_OR_EXPR, boolean_type_node,
 617                         unshare_expr (cond), new_cond));
 618   else
 619     cond = new_cond;
 620
 621   bb->aux = cond;
 622 }
 623
 624 /* Add condition COND into BB's predicate list.  PREV_COND is
 625    existing condition.  */
 626
 627 static tree
 628 add_to_dst_predicate_list (struct loop * loop, basic_block bb,
 629                            tree prev_cond, tree cond,
 630                            block_stmt_iterator *bsi)
 631 {
 632   tree new_cond = NULL_TREE;
 633
 634   if (!flow_bb_inside_loop_p (loop, bb))
 635     return NULL_TREE;
 636
 637   if (prev_cond == boolean_true_node || !prev_cond)
 638     new_cond = unshare_expr (cond);
 639   else
 640     {
 641       tree tmp;
 642       tree tmp_stmt = NULL_TREE;
 643       tree tmp_stmts1 = NULL_TREE;
 644       tree tmp_stmts2 = NULL_TREE;
 645       prev_cond = force_gimple_operand (unshare_expr (prev_cond),
 646                                         &tmp_stmts1, true, NULL);
 647       if (tmp_stmts1)
 648         bsi_insert_before (bsi, tmp_stmts1, BSI_SAME_STMT);
 649
 650       cond = force_gimple_operand (unshare_expr (cond),
 651                                    &tmp_stmts2, true, NULL);
 652       if (tmp_stmts2)
 653         bsi_insert_before (bsi, tmp_stmts2, BSI_SAME_STMT);
 654
 655       /* new_cond == prev_cond AND cond */
 656       tmp = build (TRUTH_AND_EXPR, boolean_type_node,
 657                    unshare_expr (prev_cond), cond);
 658       tmp_stmt = ifc_temp_var (boolean_type_node, tmp);
 659       bsi_insert_before (bsi, tmp_stmt, BSI_SAME_STMT);
 660       new_cond = TREE_OPERAND (tmp_stmt, 0);
 661     }
 662   add_to_predicate_list (bb, new_cond);
 663   return new_cond;
 664 }
 665
 666 /* During if-conversion aux field from basic block is used to hold predicate
 667    list. Clean each basic block's predicate list for the given LOOP.  */
 668
 669 static void
 670 clean_predicate_lists (struct loop *loop)
 671 {
 672   basic_block *bb;
 673   unsigned int i;
 674   bb = get_loop_body (loop);
 675   for (i = 0; i < loop->num_nodes; i++)
 676     bb[i]->aux = NULL;
 677
 678   free (bb);
 679 }
 680
 681 /* Basic block BB has two predecessors. Using predecessor's aux field, set
 682    appropriate condition COND for the PHI node replacement. Return true block
 683    whose phi arguments are selected when cond is true.  */
 684
 685 static basic_block
 686 find_phi_replacement_condition (basic_block bb, tree *cond,
 687                                 block_stmt_iterator *bsi)
 688 {
 689   edge e;
 690   basic_block p1 = NULL;
 691   basic_block p2 = NULL;
 692   basic_block true_bb = NULL;
 693   tree tmp_cond;
 694   edge_iterator ei;
 695
 696   FOR_EACH_EDGE (e, ei, bb->preds)
 697     {
 698       if (p1 == NULL)
 699         p1 = e->src;
 700       else
 701         {
 702           gcc_assert (!p2);
 703           p2 = e->src;
 704         }
 705     }
 706
 707   /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr.  */
 708   tmp_cond = p1->aux;
 709   if (TREE_CODE (tmp_cond) == TRUTH_NOT_EXPR)
 710     {
 711       *cond  = p2->aux;
 712       true_bb = p2;
 713     }
 714   else
 715     {
 716       *cond  = p1->aux;
 717       true_bb = p1;
 718     }
 719
 720   /* Create temp. for the condition. Vectorizer prefers to have gimple
 721      value as condition. Various targets use different means to communicate
 722      condition in vector compare operation. Using gimple value allows compiler
 723      to emit vector compare and select RTL without exposing compare's result.  */
 724   if (!is_gimple_reg (*cond) && !is_gimple_condexpr (*cond))
 725     {
 726       tree new_stmt;
 727
 728       new_stmt = ifc_temp_var (TREE_TYPE (*cond), unshare_expr (*cond));
 729       bsi_insert_after (bsi, new_stmt, BSI_SAME_STMT);
 730       bsi_next (bsi);
 731       *cond = TREE_OPERAND (new_stmt, 0);
 732     }
 733
 734   gcc_assert (*cond);
 735
 736   return true_bb;
 737 }
 738
 739
 740 /* Replace PHI node with conditional modify expr using COND.
 741    This routine does not handle PHI nodes with more than two arguments.
 742    For example,
 743      S1: A = PHI <x1(1), x2(5)
 744    is converted into,
 745      S2: A = cond ? x1 : x2;
 746    S2 is inserted at the top of basic block's statement list.
 747    When COND is true, phi arg from TRUE_BB is selected.
 748 */
 749
 750 static void
 751 replace_phi_with_cond_modify_expr (tree phi, tree cond, basic_block true_bb,
 752                                    block_stmt_iterator *bsi)
 753 {
 754   tree new_stmt;
 755   basic_block bb;
 756   tree rhs;
 757   tree arg_0, arg_1;
 758
 759   gcc_assert (TREE_CODE (phi) == PHI_NODE);
 760
 761   /* If this is not filtered earlier, then now it is too late.  */
 762   gcc_assert (PHI_NUM_ARGS (phi) == 2);
 763
 764   /* Find basic block and initialize iterator.  */
 765   bb = bb_for_stmt (phi);
 766
 767   new_stmt = NULL_TREE;
 768   arg_0 = NULL_TREE;
 769   arg_1 = NULL_TREE;
 770
 771   /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr.  */
 772   if (EDGE_PRED (bb, 1)->src == true_bb)
 773     {
 774       arg_0 = PHI_ARG_DEF (phi, 1);
 775       arg_1 = PHI_ARG_DEF (phi, 0);
 776     }
 777   else
 778     {
 779       arg_0 = PHI_ARG_DEF (phi, 0);
 780       arg_1 = PHI_ARG_DEF (phi, 1);
 781     }
 782
 783   /* Build new RHS using selected condition and arguments.  */
 784   rhs = build (COND_EXPR, TREE_TYPE (PHI_RESULT (phi)),
 785                unshare_expr (cond), unshare_expr (arg_0),
 786                unshare_expr (arg_1));
 787
 788   /* Create new MODIFY expression using RHS.  */
 789   new_stmt = build (MODIFY_EXPR, TREE_TYPE (PHI_RESULT (phi)),
 790                     unshare_expr (PHI_RESULT (phi)), rhs);
 791
 792   /* Make new statement definition of the original phi result.  */
 793   SSA_NAME_DEF_STMT (PHI_RESULT (phi)) = new_stmt;
 794
 795   /* Set basic block and insert using iterator.  */
 796   set_bb_for_stmt (new_stmt, bb);
 797
 798   bsi_insert_after (bsi, new_stmt, BSI_SAME_STMT);
 799   bsi_next (bsi);
 800
 801   modify_stmt (new_stmt);
 802
 803   if (dump_file && (dump_flags & TDF_DETAILS))
 804     {
 805       fprintf (dump_file, "new phi replacement stmt\n");
 806       print_generic_stmt (dump_file, new_stmt, TDF_SLIM);
 807     }
 808 }
 809
 810 /* Process phi nodes for the given  LOOP.  Replace phi nodes with cond
 811    modify expr.  */
 812
 813 static void
 814 process_phi_nodes (struct loop *loop)
 815 {
 816   basic_block bb;
 817   unsigned int orig_loop_num_nodes = loop->num_nodes;
 818   unsigned int i;
 819
 820   /* Replace phi nodes with cond. modify expr.  */
 821   for (i = 1; i < orig_loop_num_nodes; i++)
 822     {
 823       tree phi, cond;
 824       block_stmt_iterator bsi;
 825       basic_block true_bb = NULL;
 826       bb = ifc_bbs[i];
 827
 828       if (bb == loop->header)
 829         continue;
 830
 831       phi = phi_nodes (bb);
 832       bsi = bsi_after_labels (bb);
 833
 834       /* BB has two predecessors. Using predecessor's aux field, set
 835          appropriate condition for the PHI node replacement.  */
 836       if (phi)
 837         true_bb = find_phi_replacement_condition (bb, &cond, &bsi);
 838
 839       while (phi)
 840         {
 841           tree next = PHI_CHAIN (phi);
 842           replace_phi_with_cond_modify_expr (phi, cond, true_bb, &bsi);
 843           release_phi_node (phi);
 844           phi = next;
 845         }
 846       bb_ann (bb)->phi_nodes = NULL;
 847     }
 848   return;
 849 }
 850
 851 /* Combine all basic block from the given LOOP into one or two super
 852    basic block.  Replace PHI nodes with conditional modify expression.  */
 853
 854 static void
 855 combine_blocks (struct loop *loop)
 856 {
 857   basic_block bb, exit_bb, merge_target_bb;
 858   unsigned int orig_loop_num_nodes = loop->num_nodes;
 859   unsigned int i;
 860   unsigned int n_exits;
 861
 862   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 (loop, bb))
 879           exit_bb = bb;
 880
 881       if (bb == exit_bb)
 882         {
 883           edge_iterator ei;
 884
 885           /* Connect this node with loop header.  */
 886           make_edge (ifc_bbs[0], bb, EDGE_FALLTHRU);
 887           set_immediate_dominator (CDI_DOMINATORS, bb, ifc_bbs[0]);
 888
 889           if (exit_bb != loop->latch)
 890             {
 891               /* Redirect non-exit edge to loop->latch.  */
 892               FOR_EACH_EDGE (e, ei, bb->succs)
 893                 {
 894                   if (!loop_exit_edge_p (loop, e))
 895                     {
 896                       redirect_edge_and_branch (e, loop->latch);
 897                       set_immediate_dominator (CDI_DOMINATORS, loop->latch, bb);
 898                     }
 899                 }
 900             }
 901           continue;
 902         }
 903
 904       if (bb == loop->latch && empty_block_p (bb))
 905         continue;
 906
 907       /* It is time to remove this basic block.  First remove edges.  */
 908       while (EDGE_COUNT (bb->preds) > 0)
 909         remove_edge (EDGE_PRED (bb, 0));
 910
 911       /* This is loop latch and loop does not have exit then do not
 912          delete this basic block. Just remove its PREDS and reconnect
 913          loop->header and loop->latch blocks.  */
 914       if (bb == loop->latch && n_exits == 0)
 915         {
 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 exit of LOOP.  */
1073
1074 static bool
1075 bb_with_exit_edge_p (struct loop *loop, 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 (loop_exit_edge_p (loop, e))
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 };