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