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