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