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
  82             arg0 = PHI_ARG_DEF (phi, 0);
  83             arg1 = PHI_ARG_DEF (phi, 1);
  84
  85             /* Do the replacement of conditional if it can be done.  */
  86             if (conditional_replacement (bb, phi, arg0, arg1))
  87               {
  88                 /* We have done the replacement so we need to rebuild the cfg.   */
  89                 removed_phis = true;
  90                 continue;
  91               }
  92         }
  93     }
  94
  95   /* If we removed any PHIs, then we have unreachable blocks and blocks
  96      which need to be merged in the CFG.  */
  97   if (removed_phis)
  98     cleanup_tree_cfg ();
  99 }
 100
 101 /*  The function conditional_replacement does the main work of doing the conditional
 102     replacement.  Return true if the replacement is done.  Otherwise return false.
 103     bb is the basic block where the replacement is going to be done on.  arg0
 104     is argument 0 from the 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
 181   cond = COND_EXPR_COND (last_stmt (cond_block));
 182   result = PHI_RESULT (phi);
 183   if (TREE_CODE (cond) != SSA_NAME
 184       && !lang_hooks.types_compatible_p (TREE_TYPE (cond), TREE_TYPE (result)))
 185     {
 186       new_var = make_rename_temp (TREE_TYPE (cond), NULL);
 187       old_result = cond;
 188       cond = new_var;
 189     }
 190
 191   /* If the condition was a naked SSA_NAME and the type is not the
 192       same as the type of the result, then convert the type of the
 193       condition.  */
 194   if (!lang_hooks.types_compatible_p (TREE_TYPE (cond), TREE_TYPE (result)))
 195     cond = fold_convert (TREE_TYPE (result), cond);
 196
 197   /* We need to know which is the true edge and which is the false
 198       edge so that we know when to invert the condition below.  */
 199   extract_true_false_edges_from_block (cond_block, &true_edge, &false_edge);
 200
 201   /* Insert our new statement at the head of our block.  */
 202   bsi = bsi_start (bb);
 203
 204   if (old_result)
 205     {
 206       tree new1;
 207       if (TREE_CODE_CLASS (TREE_CODE (old_result)) != '<')
 208         return false;
 209
 210       new1 = build (TREE_CODE (old_result), TREE_TYPE (result),
 211                     TREE_OPERAND (old_result, 0),
 212                     TREE_OPERAND (old_result, 1));
 213
 214       new1 = build (MODIFY_EXPR, TREE_TYPE (result),
 215                     new_var, new1);
 216       bsi_insert_after (&bsi, new1, BSI_NEW_STMT);
 217     }
 218
 219
 220   /* At this point we know we have a COND_EXPR with two successors.
 221       One successor is BB, the other successor is an empty block which
 222       falls through into BB.
 223
 224       There is a single PHI node at the join point (BB) and its arguments
 225       are constants (0, 1).
 226
 227       So, given the condition COND, and the two PHI arguments, we can
 228       rewrite this PHI into non-branching code:
 229
 230         dest = (COND) or dest = COND'
 231
 232       We use the condition as-is if the argument associated with the
 233       true edge has the value one or the argument associated with the
 234       false edge as the value zero.  Note that those conditions are not
 235       the same since only one of the outgoing edges from the COND_EXPR
 236       will directly reach BB and thus be associated with an argument.  */
 237
 238   if ((PHI_ARG_EDGE (phi, 0) == true_edge && integer_onep (arg0))
 239       || (PHI_ARG_EDGE (phi, 0) == false_edge && integer_zerop (arg0))
 240       || (PHI_ARG_EDGE (phi, 1) == true_edge && integer_onep (arg1))
 241       || (PHI_ARG_EDGE (phi, 1) == false_edge && integer_zerop (arg1)))
 242     {
 243       new = build (MODIFY_EXPR, TREE_TYPE (PHI_RESULT (phi)),
 244                     PHI_RESULT (phi), cond);
 245     }
 246   else
 247     {
 248       tree cond1 = invert_truthvalue (cond);
 249
 250       cond = cond1;
 251       /* If what we get back is a conditional expression, there is no
 252          way that is can be gimple.   */
 253       if (TREE_CODE (cond) == COND_EXPR)
 254         return false;
 255
 256       /* If what we get back is not gimple try to create it as gimple by
 257          using a temporary variable.   */
 258       if (is_gimple_cast (cond)
 259           && !is_gimple_val (TREE_OPERAND (cond, 0)))
 260         {
 261           tree temp = TREE_OPERAND (cond, 0);
 262           tree new_var_1 = make_rename_temp (TREE_TYPE (temp), NULL);
 263           new = build (MODIFY_EXPR, TREE_TYPE (new_var_1), new_var_1, temp);
 264           bsi_insert_after (&bsi, new, BSI_NEW_STMT);
 265           cond = fold_convert (TREE_TYPE (result), new_var_1);
 266         }
 267
 268       if (TREE_CODE (cond) == TRUTH_NOT_EXPR
 269           &&  !is_gimple_val (TREE_OPERAND (cond, 0)))
 270         return false;
 271
 272       new = build (MODIFY_EXPR, TREE_TYPE (PHI_RESULT (phi)),
 273                     PHI_RESULT (phi), cond);
 274     }
 275
 276   bsi_insert_after (&bsi, new, BSI_NEW_STMT);
 277
 278   /* Register our new statement as the defining statement for
 279       the result.  */
 280   SSA_NAME_DEF_STMT (PHI_RESULT (phi)) = new;
 281
 282   /* Remove the now useless PHI node.
 283
 284       We do not want to use remove_phi_node since that releases the
 285       SSA_NAME as well and the SSA_NAME is still being used.  */
 286   release_phi_node (phi);
 287   bb_ann (bb)->phi_nodes = NULL;
 288
 289   /* Disconnect the edge leading into the empty block.  That will
 290      make the empty block unreachable and it will be removed later.  */
 291   if (cond_block->succ->dest == bb)
 292     {
 293       cond_block->succ->flags |= EDGE_FALLTHRU;
 294       cond_block->succ->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
 295       ssa_remove_edge (cond_block->succ->succ_next);
 296     }
 297   else
 298     {
 299       cond_block->succ->succ_next->flags |= EDGE_FALLTHRU;
 300       cond_block->succ->succ_next->flags
 301         &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
 302       ssa_remove_edge (cond_block->succ);
 303     }
 304
 305   /* Eliminate the COND_EXPR at the end of COND_BLOCK.  */
 306   bsi = bsi_last (cond_block);
 307   bsi_remove (&bsi);
 308
 309   if (dump_file && (dump_flags & TDF_DETAILS))
 310     fprintf (dump_file,
 311               "COND_EXPR in block %d and PHI in block %d converted to straightline code.\n",
 312               cond_block->index,
 313               bb->index);
 314
 315   /* Note that we optimized this PHI.  */
 316   return true;
 317 }
 318
 319
 320 /* Always do these optimizations if we have SSA
 321    trees to work on.  */
 322 static bool
 323 gate_phiopt (void)
 324 {
 325   return 1;
 326 }
 327
 328 struct tree_opt_pass pass_phiopt =
 329 {
 330   "phiopt",                             /* name */
 331   gate_phiopt,                          /* gate */
 332   tree_ssa_phiopt,                      /* execute */
 333   NULL,                                 /* sub */
 334   NULL,                                 /* next */
 335   0,                                    /* static_pass_number */
 336   TV_TREE_PHIOPT,                       /* tv_id */
 337   PROP_cfg | PROP_ssa,                  /* properties_required */
 338   0,                                    /* properties_provided */
 339   0,                                    /* properties_destroyed */
 340   0,                                    /* todo_flags_start */
 341   TODO_dump_func | TODO_ggc_collect     /* todo_flags_finish */
 342     | TODO_verify_ssa | TODO_rename_vars
 343     | TODO_verify_flow
 344 };
 345
 346