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 "tm_p.h"
  30 #include "basic-block.h"
  31 #include "timevar.h"
  32 #include "diagnostic.h"
  33 #include "tree-flow.h"
  34 #include "tree-pass.h"
  35 #include "tree-dump.h"
  36 #include "langhooks.h"
  37
  38 static void tree_ssa_phiopt (void);
  39 static bool conditional_replacement (basic_block bb, tree phi, tree arg0,
  40                                      tree arg1);
  41
  42 /* This pass eliminates PHI nodes which can be trivially implemented as
  43    an assignment from a conditional expression.  ie if we have something
  44    like:
  45
  46      bb0:
  47       if (cond) goto bb2; else goto bb1;
  48      bb1:
  49      bb2:
  50       x = PHI (0 (bb1), 1 (bb0)
  51
  52    We can rewrite that as:
  53
  54      bb0:
  55      bb1:
  56      bb2:
  57       x = cond;
  58
  59    bb1 will become unreachable and bb0 and bb2 will almost always
  60    be merged into a single block.  This occurs often due to gimplification
  61    of conditionals.  */
  62
  63 static void
  64 tree_ssa_phiopt (void)
  65 {
  66   basic_block bb;
  67   bool removed_phis = false;
  68
  69   /* Search every basic block for PHI nodes we may be able to optimize.  */
  70   FOR_EACH_BB (bb)
  71     {
  72       tree arg0, arg1, phi;
  73
  74
  75       /* We're searching for blocks with one PHI node which has two
  76          arguments.  */
  77       phi = phi_nodes (bb);
  78       if (phi && TREE_CHAIN (phi) == NULL
  79           && PHI_NUM_ARGS (phi) == 2)
  80         {
  81           arg0 = PHI_ARG_DEF (phi, 0);
  82           arg1 = PHI_ARG_DEF (phi, 1);
  83
  84           /* Do the replacement of conditional if it can be done.  */
  85           if (conditional_replacement (bb, phi, arg0, arg1))
  86             {
  87               /* We have done the replacement so we need to rebuild the cfg.  */
  88               removed_phis = true;
  89               continue;
  90             }
  91         }
  92     }
  93
  94   /* If we removed any PHIs, then we have unreachable blocks and blocks
  95      which need to be merged in the CFG.  */
  96   if (removed_phis)
  97     cleanup_tree_cfg ();
  98 }
  99
 100 /*  The function conditional_replacement does the main work of doing the
 101     conditional replacement.  Return true if the replacement is done.
 102     Otherwise return false.
 103     BB is the basic block where the replacement is going to be done on.  ARG0
 104     is argument 0 from PHI.  Likewise for ARG1.   */
 105
 106 static bool
 107 conditional_replacement (basic_block bb, tree phi, tree arg0, tree arg1)
 108 {
 109   tree result;
 110   tree old_result = NULL;
 111   basic_block other_block = NULL;
 112   basic_block cond_block = NULL;
 113   tree last0, last1, new, cond;
 114   block_stmt_iterator bsi;
 115   edge true_edge, false_edge;
 116   tree new_var = NULL;
 117
 118   /* The PHI arguments have the constants 0 and 1, then convert
 119      it to the conditional.  */
 120   if ((integer_zerop (arg0) && integer_onep (arg1))
 121       || (integer_zerop (arg1) && integer_onep (arg0)))
 122     ;
 123   else
 124     return false;
 125
 126   /* One of the alternatives must come from a block ending with
 127      a COND_EXPR.  The other block must be entirely empty, except
 128      for labels.  */
 129   last0 = last_stmt (bb->pred->src);
 130   last1 = last_stmt (bb->pred->pred_next->src);
 131   if (last0 && TREE_CODE (last0) == COND_EXPR)
 132     {
 133       cond_block = bb->pred->src;
 134       other_block = bb->pred->pred_next->src;
 135     }
 136   else if (last1 && TREE_CODE (last1) == COND_EXPR)
 137     {
 138       other_block = bb->pred->src;
 139       cond_block = bb->pred->pred_next->src;
 140     }
 141   else
 142     return false;
 143
 144   /* COND_BLOCK must have precisely two successors.  We indirectly
 145      verify that those successors are BB and OTHER_BLOCK.  */
 146   if (!cond_block->succ
 147       || !cond_block->succ->succ_next
 148       || cond_block->succ->succ_next->succ_next
 149       || (cond_block->succ->flags & EDGE_ABNORMAL) != 0
 150       || (cond_block->succ->succ_next->flags & EDGE_ABNORMAL) != 0)
 151     return false;
 152
 153   /* OTHER_BLOCK must have a single predecessor which is COND_BLOCK,
 154      OTHER_BLOCK must have a single successor which is BB and
 155      OTHER_BLOCK must have no PHI nodes.  */
 156   if (!other_block->pred
 157       || other_block->pred->src != cond_block
 158       || other_block->pred->pred_next
 159       || !other_block->succ
 160       || other_block->succ->dest != bb
 161       || other_block->succ->succ_next
 162       || phi_nodes (other_block))
 163     return false;
 164
 165   /* OTHER_BLOCK must have no executable statements.  */
 166   bsi = bsi_start (other_block);
 167   while (!bsi_end_p (bsi)
 168           && (TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR
 169               || IS_EMPTY_STMT (bsi_stmt (bsi))))
 170     bsi_next (&bsi);
 171
 172   if (!bsi_end_p (bsi))
 173     return false;
 174
 175   /* If the condition is not a naked SSA_NAME and its type does not
 176      match the type of the result, then we have to create a new
 177      variable to optimize this case as it would likely create
 178      non-gimple code when the condition was converted to the
 179      result's type.  */
 180   cond = COND_EXPR_COND (last_stmt (cond_block));
 181   result = PHI_RESULT (phi);
 182   if (TREE_CODE (cond) != SSA_NAME
 183       && !lang_hooks.types_compatible_p (TREE_TYPE (cond), TREE_TYPE (result)))
 184     {
 185       new_var = make_rename_temp (TREE_TYPE (cond), NULL);
 186       old_result = cond;
 187       cond = new_var;
 188     }
 189
 190   /* If the condition was a naked SSA_NAME and the type is not the
 191      same as the type of the result, then convert the type of the
 192      condition.  */
 193   if (!lang_hooks.types_compatible_p (TREE_TYPE (cond), TREE_TYPE (result)))
 194     cond = fold_convert (TREE_TYPE (result), cond);
 195
 196   /* We need to know which is the true edge and which is the false
 197      edge so that we know when to invert the condition below.  */
 198   extract_true_false_edges_from_block (cond_block, &true_edge, &false_edge);
 199
 200   /* Insert our new statement at the head of our block.  */
 201   bsi = bsi_start (bb);
 202
 203   if (old_result)
 204     {
 205       tree new1;
 206       if (TREE_CODE_CLASS (TREE_CODE (old_result)) != '<')
 207         return false;
 208
 209       new1 = build (TREE_CODE (old_result), TREE_TYPE (result),
 210                     TREE_OPERAND (old_result, 0),
 211                     TREE_OPERAND (old_result, 1));
 212
 213       new1 = build (MODIFY_EXPR, TREE_TYPE (result),
 214                     new_var, new1);
 215       bsi_insert_after (&bsi, new1, BSI_NEW_STMT);
 216     }
 217
 218   /* At this point we know we have a COND_EXPR with two successors.
 219      One successor is BB, the other successor is an empty block which
 220      falls through into BB.
 221
 222      There is a single PHI node at the join point (BB) and its arguments
 223      are constants (0, 1).
 224
 225      So, given the condition COND, and the two PHI arguments, we can
 226      rewrite this PHI into non-branching code:
 227
 228        dest = (COND) or dest = COND'
 229
 230      We use the condition as-is if the argument associated with the
 231      true edge has the value one or the argument associated with the
 232      false edge as the value zero.  Note that those conditions are not
 233      the same since only one of the outgoing edges from the COND_EXPR
 234      will directly reach BB and thus be associated with an argument.  */
 235   if ((PHI_ARG_EDGE (phi, 0) == true_edge && integer_onep (arg0))
 236       || (PHI_ARG_EDGE (phi, 0) == false_edge && integer_zerop (arg0))
 237       || (PHI_ARG_EDGE (phi, 1) == true_edge && integer_onep (arg1))
 238       || (PHI_ARG_EDGE (phi, 1) == false_edge && integer_zerop (arg1)))
 239     {
 240       new = build (MODIFY_EXPR, TREE_TYPE (PHI_RESULT (phi)),
 241                     PHI_RESULT (phi), cond);
 242     }
 243   else
 244     {
 245       tree cond1 = invert_truthvalue (cond);
 246
 247       cond = cond1;
 248       /* If what we get back is a conditional expression, there is no
 249          way that is can be gimple.   */
 250       if (TREE_CODE (cond) == COND_EXPR)
 251         return false;
 252
 253       /* If what we get back is not gimple try to create it as gimple by
 254          using a temporary variable.   */
 255       if (is_gimple_cast (cond)
 256           && !is_gimple_val (TREE_OPERAND (cond, 0)))
 257         {
 258           tree temp = TREE_OPERAND (cond, 0);
 259           tree new_var_1 = make_rename_temp (TREE_TYPE (temp), NULL);
 260           new = build (MODIFY_EXPR, TREE_TYPE (new_var_1), new_var_1, temp);
 261           bsi_insert_after (&bsi, new, BSI_NEW_STMT);
 262           cond = fold_convert (TREE_TYPE (result), new_var_1);
 263         }
 264
 265       if (TREE_CODE (cond) == TRUTH_NOT_EXPR
 266           &&  !is_gimple_val (TREE_OPERAND (cond, 0)))
 267         return false;
 268
 269       new = build (MODIFY_EXPR, TREE_TYPE (PHI_RESULT (phi)),
 270                     PHI_RESULT (phi), cond);
 271     }
 272
 273   bsi_insert_after (&bsi, new, BSI_NEW_STMT);
 274
 275   /* Register our new statement as the defining statement for
 276      the result.  */
 277   SSA_NAME_DEF_STMT (PHI_RESULT (phi)) = new;
 278
 279   /* Remove the now useless PHI node.
 280
 281      We do not want to use remove_phi_node since that releases the
 282      SSA_NAME as well and the SSA_NAME is still being used.  */
 283   release_phi_node (phi);
 284   bb_ann (bb)->phi_nodes = NULL;
 285
 286   /* Disconnect the edge leading into the empty block.  That will
 287      make the empty block unreachable and it will be removed later.  */
 288   if (cond_block->succ->dest == bb)
 289     {
 290       cond_block->succ->flags |= EDGE_FALLTHRU;
 291       cond_block->succ->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
 292       ssa_remove_edge (cond_block->succ->succ_next);
 293     }
 294   else
 295     {
 296       cond_block->succ->succ_next->flags |= EDGE_FALLTHRU;
 297       cond_block->succ->succ_next->flags
 298         &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
 299       ssa_remove_edge (cond_block->succ);
 300     }
 301
 302   /* Eliminate the COND_EXPR at the end of COND_BLOCK.  */
 303   bsi = bsi_last (cond_block);
 304   bsi_remove (&bsi);
 305
 306   if (dump_file && (dump_flags & TDF_DETAILS))
 307     fprintf (dump_file,
 308               "COND_EXPR in block %d and PHI in block %d converted to straightline code.\n",
 309               cond_block->index,
 310               bb->index);
 311
 312   /* Note that we optimized this PHI.  */
 313   return true;
 314 }
 315
 316
 317 /* Always do these optimizations if we have SSA
 318    trees to work on.  */
 319 static bool
 320 gate_phiopt (void)
 321 {
 322   return 1;
 323 }
 324
 325 struct tree_opt_pass pass_phiopt =
 326 {
 327   "phiopt",                             /* name */
 328   gate_phiopt,                          /* gate */
 329   tree_ssa_phiopt,                      /* execute */
 330   NULL,                                 /* sub */
 331   NULL,                                 /* next */
 332   0,                                    /* static_pass_number */
 333   TV_TREE_PHIOPT,                       /* tv_id */
 334   PROP_cfg | PROP_ssa,                  /* properties_required */
 335   0,                                    /* properties_provided */
 336   0,                                    /* properties_destroyed */
 337   0,                                    /* todo_flags_start */
 338   TODO_dump_func | TODO_ggc_collect     /* todo_flags_finish */
 339     | TODO_verify_ssa | TODO_rename_vars
 340     | TODO_verify_flow
 341 };
 342
 343