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