contrib/gcc/tree-if-conv.c

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