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