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