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 compiler
 766      to emit vector compare and select RTL without exposing compare's result.  */
 767   *cond = force_gimple_operand (*cond, &new_stmts, false, NULL_TREE);
 768   if (new_stmts)
 769     bsi_insert_before (bsi, new_stmts, BSI_SAME_STMT);
 770   if (!is_gimple_reg (*cond) && !is_gimple_condexpr (*cond))
 771     {
 772       tree new_stmt;
 773
 774       new_stmt = ifc_temp_var (TREE_TYPE (*cond), unshare_expr (*cond));
 775       bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT);
 776       *cond = TREE_OPERAND (new_stmt, 0);
 777     }
 778
 779   gcc_assert (*cond);
 780
 781   return first_edge->src;
 782 }
 783
 784
 785 /* Replace PHI node with conditional modify expr using COND.
 786    This routine does not handle PHI nodes with more than two arguments.
 787    For example,
 788      S1: A = PHI <x1(1), x2(5)
 789    is converted into,
 790      S2: A = cond ? x1 : x2;
 791    S2 is inserted at the top of basic block's statement list.
 792    When COND is true, phi arg from TRUE_BB is selected.
 793 */
 794
 795 static void
 796 replace_phi_with_cond_modify_expr (tree phi, tree cond, basic_block true_bb,
 797                                    block_stmt_iterator *bsi)
 798 {
 799   tree new_stmt;
 800   basic_block bb;
 801   tree rhs;
 802   tree arg_0, arg_1;
 803
 804   gcc_assert (TREE_CODE (phi) == PHI_NODE);
 805
 806   /* If this is not filtered earlier, then now it is too late.  */
 807   gcc_assert (PHI_NUM_ARGS (phi) == 2);
 808
 809   /* Find basic block and initialize iterator.  */
 810   bb = bb_for_stmt (phi);
 811
 812   /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr.  */
 813   if (EDGE_PRED (bb, 1)->src == true_bb)
 814     {
 815       arg_0 = PHI_ARG_DEF (phi, 1);
 816       arg_1 = PHI_ARG_DEF (phi, 0);
 817     }
 818   else
 819     {
 820       arg_0 = PHI_ARG_DEF (phi, 0);
 821       arg_1 = PHI_ARG_DEF (phi, 1);
 822     }
 823
 824   /* Build new RHS using selected condition and arguments.  */
 825   rhs = build3 (COND_EXPR, TREE_TYPE (PHI_RESULT (phi)),
 826                 unshare_expr (cond), unshare_expr (arg_0),
 827                 unshare_expr (arg_1));
 828
 829   /* Create new MODIFY expression using RHS.  */
 830   new_stmt = build2 (MODIFY_EXPR, TREE_TYPE (PHI_RESULT (phi)),
 831                      unshare_expr (PHI_RESULT (phi)), rhs);
 832
 833   /* Make new statement definition of the original phi result.  */
 834   SSA_NAME_DEF_STMT (PHI_RESULT (phi)) = new_stmt;
 835
 836   /* Insert using iterator.  */
 837   bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT);
 838   update_stmt (new_stmt);
 839
 840   if (dump_file && (dump_flags & TDF_DETAILS))
 841     {
 842       fprintf (dump_file, "new phi replacement stmt\n");
 843       print_generic_stmt (dump_file, new_stmt, TDF_SLIM);
 844     }
 845 }
 846
 847 /* Process phi nodes for the given  LOOP.  Replace phi nodes with cond
 848    modify expr.  */
 849
 850 static void
 851 process_phi_nodes (struct loop *loop)
 852 {
 853   basic_block bb;
 854   unsigned int orig_loop_num_nodes = loop->num_nodes;
 855   unsigned int i;
 856
 857   /* Replace phi nodes with cond. modify expr.  */
 858   for (i = 1; i < orig_loop_num_nodes; i++)
 859     {
 860       tree phi, cond;
 861       block_stmt_iterator bsi;
 862       basic_block true_bb = NULL;
 863       bb = ifc_bbs[i];
 864
 865       if (bb == loop->header)
 866         continue;
 867
 868       phi = phi_nodes (bb);
 869       bsi = bsi_after_labels (bb);
 870
 871       /* BB has two predecessors. Using predecessor's aux field, set
 872          appropriate condition for the PHI node replacement.  */
 873       if (phi)
 874         true_bb = find_phi_replacement_condition (loop, bb, &cond, &bsi);
 875
 876       while (phi)
 877         {
 878           tree next = PHI_CHAIN (phi);
 879           replace_phi_with_cond_modify_expr (phi, cond, true_bb, &bsi);
 880           release_phi_node (phi);
 881           phi = next;
 882         }
 883       bb->phi_nodes = NULL;
 884     }
 885   return;
 886 }
 887
 888 /* Combine all basic block from the given LOOP into one or two super
 889    basic block.  Replace PHI nodes with conditional modify expression.  */
 890
 891 static void
 892 combine_blocks (struct loop *loop)
 893 {
 894   basic_block bb, exit_bb, merge_target_bb;
 895   unsigned int orig_loop_num_nodes = loop->num_nodes;
 896   unsigned int i;
 897   edge e;
 898   edge_iterator ei;
 899
 900   /* Process phi nodes to prepare blocks for merge.  */
 901   process_phi_nodes (loop);
 902
 903   /* Merge basic blocks.  First remove all the edges in the loop, except
 904      for those from the exit block.  */
 905   exit_bb = NULL;
 906   for (i = 0; i < orig_loop_num_nodes; i++)
 907     {
 908       bb = ifc_bbs[i];
 909       if (bb_with_exit_edge_p (loop, bb))
 910         {
 911           exit_bb = bb;
 912           break;
 913         }
 914     }
 915   gcc_assert (exit_bb != loop->latch);
 916
 917   for (i = 1; i < orig_loop_num_nodes; i++)
 918     {
 919       bb = ifc_bbs[i];
 920
 921       for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei));)
 922         {
 923           if (e->src == exit_bb)
 924             ei_next (&ei);
 925           else
 926             remove_edge (e);
 927         }
 928     }
 929
 930   if (exit_bb != NULL)
 931     {
 932       if (exit_bb != loop->header)
 933         {
 934           /* Connect this node with loop header.  */
 935           make_edge (loop->header, exit_bb, EDGE_FALLTHRU);
 936           set_immediate_dominator (CDI_DOMINATORS, exit_bb, loop->header);
 937         }
 938
 939       /* Redirect non-exit edges to loop->latch.  */
 940       FOR_EACH_EDGE (e, ei, exit_bb->succs)
 941         {
 942           if (!loop_exit_edge_p (loop, e))
 943             redirect_edge_and_branch (e, loop->latch);
 944         }
 945       set_immediate_dominator (CDI_DOMINATORS, loop->latch, exit_bb);
 946     }
 947   else
 948     {
 949       /* If the loop does not have exit then reconnect header and latch.  */
 950       make_edge (loop->header, loop->latch, EDGE_FALLTHRU);
 951       set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header);
 952     }
 953
 954   merge_target_bb = loop->header;
 955   for (i = 1; i < orig_loop_num_nodes; i++)
 956     {
 957       block_stmt_iterator bsi;
 958       tree_stmt_iterator last;
 959
 960       bb = ifc_bbs[i];
 961
 962       if (bb == exit_bb || bb == loop->latch)
 963         continue;
 964
 965       /* Remove labels and make stmts member of loop->header.  */
 966       for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
 967         {
 968           if (TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR)
 969             bsi_remove (&bsi, true);
 970           else
 971             {
 972               set_bb_for_stmt (bsi_stmt (bsi), merge_target_bb);
 973               bsi_next (&bsi);
 974             }
 975         }
 976
 977       /* Update stmt list.  */
 978       last = tsi_last (merge_target_bb->stmt_list);
 979       tsi_link_after (&last, bb->stmt_list, TSI_NEW_STMT);
 980       bb->stmt_list = NULL;
 981
 982       /* Update dominator info.  */
 983       if (dom_computed[CDI_DOMINATORS])
 984         delete_from_dominance_info (CDI_DOMINATORS, bb);
 985       if (dom_computed[CDI_POST_DOMINATORS])
 986         delete_from_dominance_info (CDI_POST_DOMINATORS, bb);
 987
 988       /* Remove basic block.  */
 989       remove_bb_from_loops (bb);
 990       expunge_block (bb);
 991     }
 992
 993   /* Now if possible, merge loop header and block with exit edge.
 994      This reduces number of basic blocks to 2. Auto vectorizer addresses
 995      loops with two nodes only.  FIXME: Use cleanup_tree_cfg().  */
 996   if (exit_bb
 997       && exit_bb != loop->header
 998       && can_merge_blocks_p (loop->header, exit_bb))
 999     {
1000       remove_bb_from_loops (exit_bb);
1001       merge_blocks (loop->header, exit_bb);
1002     }
1003 }
1004
1005 /* Make new  temp variable of type TYPE. Add MODIFY_EXPR to assign EXP
1006    to the new variable.  */
1007
1008 static tree
1009 ifc_temp_var (tree type, tree exp)
1010 {
1011   const char *name = "_ifc_";
1012   tree var, stmt, new_name;
1013
1014   if (is_gimple_reg (exp))
1015     return exp;
1016
1017   /* Create new temporary variable.  */
1018   var = create_tmp_var (type, name);
1019   add_referenced_var (var);
1020
1021   /* Build new statement to assign EXP to new variable.  */
1022   stmt = build2 (MODIFY_EXPR, type, var, exp);
1023
1024   /* Get SSA name for the new variable and set make new statement
1025      its definition statement.  */
1026   new_name = make_ssa_name (var, stmt);
1027   TREE_OPERAND (stmt, 0) = new_name;
1028   SSA_NAME_DEF_STMT (new_name) = stmt;
1029
1030   return stmt;
1031 }
1032
1033
1034 /* Return TRUE iff, all pred blocks of BB are visited.
1035    Bitmap VISITED keeps history of visited blocks.  */
1036
1037 static bool
1038 pred_blocks_visited_p (basic_block bb, bitmap *visited)
1039 {
1040   edge e;
1041   edge_iterator ei;
1042   FOR_EACH_EDGE (e, ei, bb->preds)
1043     if (!bitmap_bit_p (*visited, e->src->index))
1044       return false;
1045
1046   return true;
1047 }
1048
1049 /* Get body of a LOOP in suitable order for if-conversion.
1050    It is caller's responsibility to deallocate basic block
1051    list.  If-conversion suitable order is, BFS order with one
1052    additional constraint. Select block in BFS block, if all
1053    pred are already selected.  */
1054
1055 static basic_block *
1056 get_loop_body_in_if_conv_order (const struct loop *loop)
1057 {
1058   basic_block *blocks, *blocks_in_bfs_order;
1059   basic_block bb;
1060   bitmap visited;
1061   unsigned int index = 0;
1062   unsigned int visited_count = 0;
1063
1064   gcc_assert (loop->num_nodes);
1065   gcc_assert (loop->latch != EXIT_BLOCK_PTR);
1066
1067   blocks = XCNEWVEC (basic_block, loop->num_nodes);
1068   visited = BITMAP_ALLOC (NULL);
1069
1070   blocks_in_bfs_order = get_loop_body_in_bfs_order (loop);
1071
1072   index = 0;
1073   while (index < loop->num_nodes)
1074     {
1075       bb = blocks_in_bfs_order [index];
1076
1077       if (bb->flags & BB_IRREDUCIBLE_LOOP)
1078         {
1079           free (blocks_in_bfs_order);
1080           BITMAP_FREE (visited);
1081           free (blocks);
1082           return NULL;
1083         }
1084       if (!bitmap_bit_p (visited, bb->index))
1085         {
1086           if (pred_blocks_visited_p (bb, &visited)
1087               || bb == loop->header)
1088             {
1089               /* This block is now visited.  */
1090               bitmap_set_bit (visited, bb->index);
1091               blocks[visited_count++] = bb;
1092             }
1093         }
1094       index++;
1095       if (index == loop->num_nodes
1096           && visited_count != loop->num_nodes)
1097         {
1098           /* Not done yet.  */
1099           index = 0;
1100         }
1101     }
1102   free (blocks_in_bfs_order);
1103   BITMAP_FREE (visited);
1104   return blocks;
1105 }
1106
1107 /* Return true if one of the basic block BB edge is exit of LOOP.  */
1108
1109 static bool
1110 bb_with_exit_edge_p (struct loop *loop, basic_block bb)
1111 {
1112   edge e;
1113   edge_iterator ei;
1114   bool exit_edge_found = false;
1115
1116   FOR_EACH_EDGE (e, ei, bb->succs)
1117     if (loop_exit_edge_p (loop, e))
1118       {
1119         exit_edge_found = true;
1120         break;
1121       }
1122
1123   return exit_edge_found;
1124 }
1125
1126 /* Tree if-conversion pass management.  */
1127
1128 static unsigned int
1129 main_tree_if_conversion (void)
1130 {
1131   unsigned i, loop_num;
1132   struct loop *loop;
1133
1134   if (!current_loops)
1135     return 0;
1136
1137   loop_num = current_loops->num;
1138   for (i = 0; i < loop_num; i++)
1139     {
1140       loop =  current_loops->parray[i];
1141       if (!loop)
1142       continue;
1143
1144       tree_if_conversion (loop, true);
1145     }
1146   return 0;
1147 }
1148
1149 static bool
1150 gate_tree_if_conversion (void)
1151 {
1152   return flag_tree_vectorize != 0;
1153 }
1154
1155 struct tree_opt_pass pass_if_conversion =
1156 {
1157   "ifcvt",                              /* name */
1158   gate_tree_if_conversion,              /* gate */
1159   main_tree_if_conversion,              /* execute */
1160   NULL,                                 /* sub */
1161   NULL,                                 /* next */
1162   0,                                    /* static_pass_number */
1163   0,                                    /* tv_id */
1164   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
1165   0,                                    /* properties_provided */
1166   0,                                    /* properties_destroyed */
1167   0,                                    /* todo_flags_start */
1168   TODO_dump_func | TODO_verify_loops | TODO_verify_stmts | TODO_verify_flow,
1169                                         /* todo_flags_finish */
1170   0                                     /* letter */
1171 };