gcc/tree-if-conv.c

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