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