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