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