gcc/tree-if-conv.c

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