gcc/tree-ssa-phiopt.c

   1 /* Optimization of PHI nodes by converting them into straightline code.
   2    Copyright (C) 2004 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it
   7 under the terms of the GNU General Public License as published by the
   8 Free Software Foundation; either version 2, or (at your option) any
   9 later version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT
  12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING.  If not, write to the Free
  18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  19 02111-1307, USA.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "errors.h"
  26 #include "ggc.h"
  27 #include "tree.h"
  28 #include "rtl.h"
  29 #include "flags.h"
  30 #include "tm_p.h"
  31 #include "basic-block.h"
  32 #include "timevar.h"
  33 #include "diagnostic.h"
  34 #include "tree-flow.h"
  35 #include "tree-pass.h"
  36 #include "tree-dump.h"
  37 #include "langhooks.h"
  38
  39 static void tree_ssa_phiopt (void);
  40 static bool conditional_replacement (basic_block, tree, tree, tree);
  41 static bool value_replacement (basic_block, tree, tree, tree);
  42 static void replace_phi_with_stmt (block_stmt_iterator, basic_block,
  43                                    basic_block, tree, tree);
  44 static bool candidate_bb_for_phi_optimization (basic_block,
  45                                                basic_block *,
  46                                                basic_block *);
  47
  48 /* This pass eliminates PHI nodes which can be trivially implemented as
  49    an assignment from a conditional expression.  ie if we have something
  50    like:
  51
  52      bb0:
  53       if (cond) goto bb2; else goto bb1;
  54      bb1:
  55      bb2:
  56       x = PHI (0 (bb1), 1 (bb0)
  57
  58    We can rewrite that as:
  59
  60      bb0:
  61      bb1:
  62      bb2:
  63       x = cond;
  64
  65    bb1 will become unreachable and bb0 and bb2 will almost always
  66    be merged into a single block.  This occurs often due to gimplification
  67     of conditionals.
  68
  69    Also done is the following optimization:
  70
  71      bb0:
  72       if (a != b) goto bb2; else goto bb1;
  73      bb1:
  74      bb2:
  75       x = PHI (a (bb1), b (bb0))
  76
  77    We can rewrite that as:
  78
  79      bb0:
  80      bb1:
  81      bb2:
  82       x = b;
  83
  84    This can sometimes occur as a result of other optimizations.  A
  85    similar transformation is done by the ifcvt RTL optimizer.  */
  86
  87 static void
  88 tree_ssa_phiopt (void)
  89 {
  90   basic_block bb;
  91   bool removed_phis = false;
  92
  93   /* Search every basic block for PHI nodes we may be able to optimize.  */
  94   FOR_EACH_BB (bb)
  95     {
  96       tree arg0, arg1, phi;
  97
  98       /* We're searching for blocks with one PHI node which has two
  99          arguments.  */
 100       phi = phi_nodes (bb);
 101       if (phi && TREE_CHAIN (phi) == NULL
 102           && PHI_NUM_ARGS (phi) == 2)
 103         {
 104           arg0 = PHI_ARG_DEF (phi, 0);
 105           arg1 = PHI_ARG_DEF (phi, 1);
 106
 107           /* Do the replacement of conditional if it can be done.  */
 108             if (conditional_replacement (bb, phi, arg0, arg1)
 109                 || value_replacement (bb, phi, arg0, arg1))
 110               {
 111                 /* We have done the replacement so we need to rebuild the
 112                    cfg when this pass is complete.  */
 113                 removed_phis = true;
 114               }
 115         }
 116     }
 117
 118   /* If we removed any PHIs, then we have unreachable blocks and blocks
 119      which need to be merged in the CFG.  */
 120   if (removed_phis)
 121     cleanup_tree_cfg ();
 122 }
 123
 124 /* BB is a basic block which has only one PHI node with precisely two
 125    arguments.
 126
 127    Examine both of BB's predecessors to see if one ends with a
 128    COND_EXPR and the other is an empty block.  If so, then we may
 129    be able to optimize PHI nodes at the start of BB.
 130
 131    If so, mark store the block with the COND_EXPR into COND_BLOCK_P
 132    and the other block into OTHER_BLOCK_P and return true, otherwise
 133    return false.  */
 134
 135 static bool
 136 candidate_bb_for_phi_optimization (basic_block bb,
 137                                    basic_block *cond_block_p,
 138                                    basic_block *other_block_p)
 139 {
 140   tree last0, last1;
 141   block_stmt_iterator bsi;
 142   basic_block cond_block, other_block;
 143
 144   /* One of the alternatives must come from a block ending with
 145      a COND_EXPR.  The other block must be entirely empty, except
 146      for labels.  */
 147   last0 = last_stmt (bb->pred->src);
 148   last1 = last_stmt (bb->pred->pred_next->src);
 149   if (last0 && TREE_CODE (last0) == COND_EXPR)
 150     {
 151       cond_block = bb->pred->src;
 152       other_block = bb->pred->pred_next->src;
 153     }
 154   else if (last1 && TREE_CODE (last1) == COND_EXPR)
 155     {
 156       other_block = bb->pred->src;
 157       cond_block = bb->pred->pred_next->src;
 158     }
 159   else
 160     return false;
 161
 162   /* COND_BLOCK must have precisely two successors.  We indirectly
 163      verify that those successors are BB and OTHER_BLOCK.  */
 164   if (!cond_block->succ
 165       || !cond_block->succ->succ_next
 166       || cond_block->succ->succ_next->succ_next
 167       || (cond_block->succ->flags & EDGE_ABNORMAL) != 0
 168       || (cond_block->succ->succ_next->flags & EDGE_ABNORMAL) != 0)
 169     return false;
 170
 171   /* OTHER_BLOCK must have a single predecessor which is COND_BLOCK,
 172      OTHER_BLOCK must have a single successor which is BB and
 173      OTHER_BLOCK must have no PHI nodes.  */
 174   if (!other_block->pred
 175       || other_block->pred->src != cond_block
 176       || other_block->pred->pred_next
 177       || !other_block->succ
 178       || other_block->succ->dest != bb
 179       || other_block->succ->succ_next
 180       || phi_nodes (other_block))
 181     return false;
 182
 183   /* OTHER_BLOCK must have no executable statements.  */
 184   bsi = bsi_start (other_block);
 185   while (!bsi_end_p (bsi)
 186           && (TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR
 187               || IS_EMPTY_STMT (bsi_stmt (bsi))))
 188     bsi_next (&bsi);
 189
 190   if (!bsi_end_p (bsi))
 191     return false;
 192
 193   *cond_block_p = cond_block;
 194   *other_block_p = other_block;
 195   /* Everything looks OK.  */
 196   return true;
 197 }
 198
 199 /* Replace PHI in block BB with statement NEW.  NEW is inserted after
 200    BSI.  Remove the edge from COND_BLOCK which does not lead to BB (COND_BLOCK
 201    is known to have two edges, one of which must reach BB).  */
 202
 203 static void
 204 replace_phi_with_stmt (block_stmt_iterator bsi, basic_block bb,
 205                        basic_block cond_block, tree phi, tree new)
 206 {
 207   /* Insert our new statement at the head of our block.  */
 208   bsi_insert_after (&bsi, new, BSI_NEW_STMT);
 209
 210   /* Register our new statement as the defining statement for
 211      the result.  */
 212   SSA_NAME_DEF_STMT (PHI_RESULT (phi)) = new;
 213
 214   /* Remove the now useless PHI node.
 215
 216      We do not want to use remove_phi_node since that releases the
 217      SSA_NAME as well and the SSA_NAME is still being used.  */
 218   release_phi_node (phi);
 219   bb_ann (bb)->phi_nodes = NULL;
 220
 221   /* Disconnect the edge leading into the empty block.  That will
 222      make the empty block unreachable and it will be removed later.  */
 223   if (cond_block->succ->dest == bb)
 224     {
 225       cond_block->succ->flags |= EDGE_FALLTHRU;
 226       cond_block->succ->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
 227       ssa_remove_edge (cond_block->succ->succ_next);
 228     }
 229   else
 230     {
 231       cond_block->succ->succ_next->flags |= EDGE_FALLTHRU;
 232       cond_block->succ->succ_next->flags
 233         &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
 234       ssa_remove_edge (cond_block->succ);
 235     }
 236
 237   /* Eliminate the COND_EXPR at the end of COND_BLOCK.  */
 238   bsi = bsi_last (cond_block);
 239   bsi_remove (&bsi);
 240
 241   if (dump_file && (dump_flags & TDF_DETAILS))
 242     fprintf (dump_file,
 243               "COND_EXPR in block %d and PHI in block %d converted to straightline code.\n",
 244               cond_block->index,
 245               bb->index);
 246 }
 247
 248 /*  The function conditional_replacement does the main work of doing the
 249     conditional replacement.  Return true if the replacement is done.
 250     Otherwise return false.
 251     BB is the basic block where the replacement is going to be done on.  ARG0
 252     is argument 0 from PHI.  Likewise for ARG1.   */
 253
 254 static bool
 255 conditional_replacement (basic_block bb, tree phi, tree arg0, tree arg1)
 256 {
 257   tree result;
 258   tree old_result = NULL;
 259   basic_block other_block = NULL;
 260   basic_block cond_block = NULL;
 261   tree new, cond;
 262   block_stmt_iterator bsi;
 263   edge true_edge, false_edge;
 264   tree new_var = NULL;
 265
 266   /* The PHI arguments have the constants 0 and 1, then convert
 267      it to the conditional.  */
 268   if ((integer_zerop (arg0) && integer_onep (arg1))
 269       || (integer_zerop (arg1) && integer_onep (arg0)))
 270     ;
 271   else
 272     return false;
 273
 274   if (!candidate_bb_for_phi_optimization (bb, &cond_block, &other_block))
 275     return false;
 276
 277   /* If the condition is not a naked SSA_NAME and its type does not
 278      match the type of the result, then we have to create a new
 279      variable to optimize this case as it would likely create
 280      non-gimple code when the condition was converted to the
 281      result's type.  */
 282   cond = COND_EXPR_COND (last_stmt (cond_block));
 283   result = PHI_RESULT (phi);
 284   if (TREE_CODE (cond) != SSA_NAME
 285       && !lang_hooks.types_compatible_p (TREE_TYPE (cond), TREE_TYPE (result)))
 286     {
 287       new_var = make_rename_temp (TREE_TYPE (cond), NULL);
 288       old_result = cond;
 289       cond = new_var;
 290     }
 291
 292   /* If the condition was a naked SSA_NAME and the type is not the
 293      same as the type of the result, then convert the type of the
 294      condition.  */
 295   if (!lang_hooks.types_compatible_p (TREE_TYPE (cond), TREE_TYPE (result)))
 296     cond = fold_convert (TREE_TYPE (result), cond);
 297
 298   /* We need to know which is the true edge and which is the false
 299      edge so that we know when to invert the condition below.  */
 300   extract_true_false_edges_from_block (cond_block, &true_edge, &false_edge);
 301
 302   /* Insert our new statement at the head of our block.  */
 303   bsi = bsi_start (bb);
 304
 305   if (old_result)
 306     {
 307       tree new1;
 308       if (TREE_CODE_CLASS (TREE_CODE (old_result)) != '<')
 309         return false;
 310
 311       new1 = build (TREE_CODE (old_result), TREE_TYPE (result),
 312                     TREE_OPERAND (old_result, 0),
 313                     TREE_OPERAND (old_result, 1));
 314
 315       new1 = build (MODIFY_EXPR, TREE_TYPE (result), new_var, new1);
 316       bsi_insert_after (&bsi, new1, BSI_NEW_STMT);
 317     }
 318
 319   /* At this point we know we have a COND_EXPR with two successors.
 320      One successor is BB, the other successor is an empty block which
 321      falls through into BB.
 322
 323      There is a single PHI node at the join point (BB) and its arguments
 324      are constants (0, 1).
 325
 326      So, given the condition COND, and the two PHI arguments, we can
 327      rewrite this PHI into non-branching code:
 328
 329        dest = (COND) or dest = COND'
 330
 331      We use the condition as-is if the argument associated with the
 332      true edge has the value one or the argument associated with the
 333      false edge as the value zero.  Note that those conditions are not
 334      the same since only one of the outgoing edges from the COND_EXPR
 335      will directly reach BB and thus be associated with an argument.  */
 336   if ((PHI_ARG_EDGE (phi, 0) == true_edge && integer_onep (arg0))
 337       || (PHI_ARG_EDGE (phi, 0) == false_edge && integer_zerop (arg0))
 338       || (PHI_ARG_EDGE (phi, 1) == true_edge && integer_onep (arg1))
 339       || (PHI_ARG_EDGE (phi, 1) == false_edge && integer_zerop (arg1)))
 340     {
 341       new = build (MODIFY_EXPR, TREE_TYPE (PHI_RESULT (phi)),
 342                     PHI_RESULT (phi), cond);
 343     }
 344   else
 345     {
 346       tree cond1 = invert_truthvalue (cond);
 347
 348       cond = cond1;
 349       /* If what we get back is a conditional expression, there is no
 350           way that it can be gimple.  */
 351       if (TREE_CODE (cond) == COND_EXPR)
 352         return false;
 353
 354       /* If what we get back is not gimple try to create it as gimple by
 355          using a temporary variable.   */
 356       if (is_gimple_cast (cond)
 357           && !is_gimple_val (TREE_OPERAND (cond, 0)))
 358         {
 359           tree temp = TREE_OPERAND (cond, 0);
 360           tree new_var_1 = make_rename_temp (TREE_TYPE (temp), NULL);
 361           new = build (MODIFY_EXPR, TREE_TYPE (new_var_1), new_var_1, temp);
 362           bsi_insert_after (&bsi, new, BSI_NEW_STMT);
 363           cond = fold_convert (TREE_TYPE (result), new_var_1);
 364         }
 365
 366       if (TREE_CODE (cond) == TRUTH_NOT_EXPR
 367           &&  !is_gimple_val (TREE_OPERAND (cond, 0)))
 368         return false;
 369
 370       new = build (MODIFY_EXPR, TREE_TYPE (PHI_RESULT (phi)),
 371                     PHI_RESULT (phi), cond);
 372     }
 373
 374   replace_phi_with_stmt (bsi, bb, cond_block, phi, new);
 375
 376   /* Note that we optimized this PHI.  */
 377   return true;
 378 }
 379
 380 /*  The function value_replacement does the main work of doing the value
 381     replacement.  Return true if the replacement is done.  Otherwise return
 382     false.
 383     BB is the basic block where the replacement is going to be done on.  ARG0
 384     is argument 0 from the PHI.  Likewise for ARG1.   */
 385
 386 static bool
 387 value_replacement (basic_block bb, tree phi, tree arg0, tree arg1)
 388 {
 389   tree result;
 390   basic_block other_block = NULL;
 391   basic_block cond_block = NULL;
 392   tree new, cond;
 393   edge true_edge, false_edge;
 394
 395   /* If the type says honor signed zeros we cannot do this
 396      optimization.   */
 397   if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg1))))
 398     return false;
 399
 400   if (!candidate_bb_for_phi_optimization (bb, &cond_block, &other_block))
 401     return false;
 402
 403   cond = COND_EXPR_COND (last_stmt (cond_block));
 404   result = PHI_RESULT (phi);
 405
 406   /* This transformation is only valid for equality comparisons.  */
 407   if (TREE_CODE (cond) != NE_EXPR && TREE_CODE (cond) != EQ_EXPR)
 408     return false;
 409
 410   /* We need to know which is the true edge and which is the false
 411       edge so that we know if have abs or negative abs.  */
 412   extract_true_false_edges_from_block (cond_block, &true_edge, &false_edge);
 413
 414   /* At this point we know we have a COND_EXPR with two successors.
 415      One successor is BB, the other successor is an empty block which
 416      falls through into BB.
 417
 418      The condition for the COND_EXPR is known to be NE_EXPR or EQ_EXPR.
 419
 420      There is a single PHI node at the join point (BB) with two arguments.
 421
 422      We now need to verify that the two arguments in the PHI node match
 423      the two arguments to the equality comparison.  */
 424
 425   if ((operand_equal_p (arg0, TREE_OPERAND (cond, 0), 0)
 426        && operand_equal_p (arg1, TREE_OPERAND (cond, 1), 0))
 427       || (operand_equal_p (arg1, TREE_OPERAND (cond, 0), 0)
 428           && operand_equal_p (arg0, TREE_OPERAND (cond, 1), 0)))
 429     {
 430       edge e;
 431       tree arg;
 432
 433       e = (TREE_CODE (cond) == NE_EXPR ? true_edge : false_edge);
 434       if (PHI_ARG_EDGE (phi, 0) == e)
 435         arg = arg0;
 436       else
 437         arg = arg1;
 438
 439       /* Build the new assignment.  */
 440       new = build (MODIFY_EXPR, TREE_TYPE (result), result, arg);
 441
 442       replace_phi_with_stmt (bsi_start (bb), bb, cond_block, phi, new);
 443
 444       /* Note that we optimized this PHI.  */
 445       return true;
 446     }
 447   return false;
 448 }
 449
 450
 451 /* Always do these optimizations if we have SSA
 452    trees to work on.  */
 453 static bool
 454 gate_phiopt (void)
 455 {
 456   return 1;
 457 }
 458
 459 struct tree_opt_pass pass_phiopt =
 460 {
 461   "phiopt",                             /* name */
 462   gate_phiopt,                          /* gate */
 463   tree_ssa_phiopt,                      /* execute */
 464   NULL,                                 /* sub */
 465   NULL,                                 /* next */
 466   0,                                    /* static_pass_number */
 467   TV_TREE_PHIOPT,                       /* tv_id */
 468   PROP_cfg | PROP_ssa,                  /* properties_required */
 469   0,                                    /* properties_provided */
 470   0,                                    /* properties_destroyed */
 471   0,                                    /* todo_flags_start */
 472   TODO_dump_func | TODO_ggc_collect     /* todo_flags_finish */
 473     | TODO_verify_ssa | TODO_rename_vars
 474     | TODO_verify_flow
 475 };
 476
 477