gcc/tree-ssa-copy.c

   1 /* Const/copy propagation and SSA_NAME replacement support routines.
   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
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 2, or (at your option)
   9 any later version.
  10
  11 GCC is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 GNU General Public License 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
  18 the Free Software Foundation, 59 Temple Place - Suite 330,
  19 Boston, MA 02111-1307, USA.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "tree.h"
  26 #include "flags.h"
  27 #include "rtl.h"
  28 #include "tm_p.h"
  29 #include "ggc.h"
  30 #include "basic-block.h"
  31 #include "output.h"
  32 #include "errors.h"
  33 #include "expr.h"
  34 #include "function.h"
  35 #include "diagnostic.h"
  36 #include "timevar.h"
  37 #include "tree-dump.h"
  38 #include "tree-flow.h"
  39 #include "tree-pass.h"
  40 #include "langhooks.h"
  41
  42 /* This file provides a handful of interfaces for performing const/copy
  43    propagation and simple expression replacement which keep variable
  44    annotations up-to-date.
  45
  46    We require that for any copy operation where the RHS and LHS have
  47    a non-null memory tag that the memory tag be the same.   It is OK
  48    for one or both of the memory tags to be NULL.
  49
  50    We also require tracking if a variable is dereferenced in a load or
  51    store operation.
  52
  53    We enforce these requirements by having all copy propagation and
  54    replacements of one SSA_NAME with a different SSA_NAME to use the
  55    APIs defined in this file.  */
  56
  57 /* Given two SSA_NAMEs, replace the one pointed to by OP_P with VAR.
  58
  59    If *OP_P is a pointer, copy the memory tag used originally by *OP_P into
  60    VAR.  This is needed in cases where VAR had never been dereferenced in the
  61    program.
  62
  63    If FOR_PROPAGATION is true, then perform additional checks to ensure
  64    that const/copy propagation of var for *OP_P is valid.  */
  65
  66 static void
  67 replace_ssa_names (tree *op_p,
  68                    tree var,
  69                    bool for_propagation ATTRIBUTE_UNUSED)
  70 {
  71 #if defined ENABLE_CHECKING
  72   if (for_propagation && !may_propagate_copy (*op_p, var))
  73     abort ();
  74 #endif
  75
  76   /* If VAR doesn't have a memory tag, copy the one from the original
  77      operand.  Also copy the dereferenced flags.  */
  78   if (POINTER_TYPE_P (TREE_TYPE (*op_p)))
  79     {
  80       var_ann_t new_ann = var_ann (SSA_NAME_VAR (var));
  81       var_ann_t orig_ann = var_ann (SSA_NAME_VAR (*op_p));
  82
  83       if (new_ann->type_mem_tag == NULL_TREE)
  84         new_ann->type_mem_tag = orig_ann->type_mem_tag;
  85       else if (orig_ann->type_mem_tag == NULL_TREE)
  86         orig_ann->type_mem_tag = new_ann->type_mem_tag;
  87       else if (new_ann->type_mem_tag != orig_ann->type_mem_tag)
  88         abort ();
  89     }
  90
  91   *op_p = var;
  92 }
  93
  94 /* Common code for propagate_value and replace_exp.
  95
  96    Replace *OP_P with VAL.  FOR_PROPAGATION indicates if the replacement
  97    is done to propagate a value or not.  */
  98
  99 static void
 100 replace_exp_1 (tree *op_p, tree val, bool for_propagation)
 101 {
 102   if (TREE_CODE (val) == SSA_NAME)
 103     {
 104       if (TREE_CODE (*op_p) == SSA_NAME)
 105         replace_ssa_names (op_p, val, for_propagation);
 106       else
 107         *op_p = val;
 108     }
 109   else
 110     *op_p = lhd_unsave_expr_now (val);
 111 }
 112
 113 /* Propagate the value VAL (assumed to be a constant or another SSA_NAME)
 114    into the operand pointed by OP_P.
 115
 116    Use this version for const/copy propagation as it will perform additional
 117    checks to ensure validity of the const/copy propagation.  */
 118
 119 void
 120 propagate_value (tree *op_p, tree val)
 121 {
 122   replace_exp_1 (op_p, val, true);
 123 }
 124
 125 /* Replace *OP_P with value VAL (assumed to be a constant or another SSA_NAME).
 126
 127    Use this version when not const/copy propagating values.  For example,
 128    PRE uses this version when building expressions as they would appear
 129    in specific blocks taking into account actions of PHI nodes.  */
 130
 131 void
 132 replace_exp (tree *op_p, tree val)
 133 {
 134   replace_exp_1 (op_p, val, false);
 135 }
 136
 137 /* Replace *OP_P in STMT with any known equivalent value for *OP_P from
 138    CONST_AND_COPIES.  */
 139
 140 static bool
 141 cprop_operand (stmt_ann_t ann, tree *op_p, varray_type const_and_copies)
 142 {
 143   bool may_have_exposed_new_symbols = false;
 144   tree val;
 145
 146   /* If the operand has a known constant value or it is known to be a
 147      copy of some other variable, use the value or copy stored in
 148      CONST_AND_COPIES.  */
 149   val = VARRAY_TREE (const_and_copies, SSA_NAME_VERSION (*op_p));
 150   if (val)
 151     {
 152       tree op_type, val_type;
 153
 154       /* Do not change the base variable in the virtual operand
 155          tables.  That would make it impossible to reconstruct
 156          the renamed virtual operand if we later modify this
 157          statement.  Also only allow the new value to be an SSA_NAME
 158          for propagation into virtual operands.  */
 159       if (!is_gimple_reg (*op_p)
 160           && (get_virtual_var (val) != get_virtual_var (*op_p)
 161               || TREE_CODE (val) != SSA_NAME))
 162         return false;
 163
 164       /* Get the toplevel type of each operand.  */
 165       op_type = TREE_TYPE (*op_p);
 166       val_type = TREE_TYPE (val);
 167
 168       /* While both types are pointers, get the type of the object
 169          pointed to.  */
 170       while (POINTER_TYPE_P (op_type) && POINTER_TYPE_P (val_type))
 171         {
 172           op_type = TREE_TYPE (op_type);
 173           val_type = TREE_TYPE (val_type);
 174         }
 175
 176       /* Make sure underlying types match before propagating a
 177          constant by converting the constant to the proper type.  Note
 178          that convert may return a non-gimple expression, in which case
 179          we ignore this propagation opportunity.  */
 180      if (!lang_hooks.types_compatible_p (op_type, val_type)
 181            && TREE_CODE (val) != SSA_NAME)
 182         {
 183           val = convert (TREE_TYPE (*op_p), val);
 184           if (!is_gimple_min_invariant (val)
 185               && TREE_CODE (val) != SSA_NAME)
 186             return false;
 187         }
 188
 189       /* Certain operands are not allowed to be copy propagated due
 190          to their interaction with exception handling and some GCC
 191          extensions.  */
 192       if (TREE_CODE (val) == SSA_NAME
 193           && !may_propagate_copy (*op_p, val))
 194         return false;
 195
 196       /* Dump details.  */
 197       if (dump_file && (dump_flags & TDF_DETAILS))
 198         {
 199           fprintf (dump_file, "  Replaced '");
 200           print_generic_expr (dump_file, *op_p, dump_flags);
 201           fprintf (dump_file, "' with %s '",
 202                    (TREE_CODE (val) != SSA_NAME ? "constant" : "variable"));
 203           print_generic_expr (dump_file, val, dump_flags);
 204           fprintf (dump_file, "'\n");
 205         }
 206
 207       /* If VAL is an ADDR_EXPR or a constant of pointer type, note
 208          that we may have exposed a new symbol for SSA renaming.  */
 209       if (TREE_CODE (val) == ADDR_EXPR
 210           || (POINTER_TYPE_P (TREE_TYPE (*op_p))
 211               && is_gimple_min_invariant (val)))
 212         may_have_exposed_new_symbols = true;
 213
 214       propagate_value (op_p, val);
 215
 216       /* And note that we modified this statement.  This is now
 217          safe, even if we changed virtual operands since we will
 218          rescan the statement and rewrite its operands again.  */
 219       ann->modified = 1;
 220     }
 221   return may_have_exposed_new_symbols;
 222 }
 223
 224 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
 225    known value for that SSA_NAME (or NULL if no value is known).
 226
 227    Propagate values from CONST_AND_COPIES into the uses, vuses and
 228    vdef_ops of STMT.  */
 229
 230 bool
 231 cprop_into_stmt (tree stmt, varray_type const_and_copies)
 232 {
 233   bool may_have_exposed_new_symbols = false;
 234   stmt_ann_t ann = stmt_ann (stmt);
 235   size_t i, num_uses, num_vuses, num_vdefs;
 236   vuse_optype vuses;
 237   vdef_optype vdefs;
 238   use_optype uses;
 239
 240   uses = USE_OPS (ann);
 241   num_uses = NUM_USES (uses);
 242   for (i = 0; i < num_uses; i++)
 243     {
 244       tree *op_p = USE_OP_PTR (uses, i);
 245       if (TREE_CODE (*op_p) == SSA_NAME)
 246         may_have_exposed_new_symbols
 247           |= cprop_operand (ann, op_p, const_and_copies);
 248     }
 249
 250   vuses = VUSE_OPS (ann);
 251   num_vuses = NUM_VUSES (vuses);
 252   for (i = 0; i < num_vuses; i++)
 253     {
 254       tree *op_p = VUSE_OP_PTR (vuses, i);
 255       if (TREE_CODE (*op_p) == SSA_NAME)
 256         may_have_exposed_new_symbols
 257           |= cprop_operand (ann, op_p, const_and_copies);
 258     }
 259
 260   vdefs = VDEF_OPS (ann);
 261   num_vdefs = NUM_VDEFS (vdefs);
 262   for (i = 0; i < num_vdefs; i++)
 263     {
 264       tree *op_p = VDEF_OP_PTR (vdefs, i);
 265       if (TREE_CODE (*op_p) == SSA_NAME)
 266         may_have_exposed_new_symbols
 267           |= cprop_operand (ann, op_p, const_and_copies);
 268     }
 269   return may_have_exposed_new_symbols;
 270 }
 271
 272 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
 273    known value for that SSA_NAME (or NULL if no value is known).
 274
 275    Propagate values from CONST_AND_COPIES into the PHI nodes of the
 276    successors of BB.  */
 277
 278 void
 279 cprop_into_successor_phis (basic_block bb, varray_type const_and_copies)
 280 {
 281   edge e;
 282
 283   /* This can get rather expensive if the implementation is naive in
 284      how it finds the phi alternative associated with a particular edge.  */
 285   for (e = bb->succ; e; e = e->succ_next)
 286     {
 287       tree phi;
 288       int phi_num_args;
 289       int hint;
 290
 291       /* If this is an abnormal edge, then we do not want to copy propagate
 292          into the PHI alternative associated with this edge.  */
 293       if (e->flags & EDGE_ABNORMAL)
 294         continue;
 295
 296       phi = phi_nodes (e->dest);
 297       if (! phi)
 298         continue;
 299
 300       /* There is no guarantee that for any two PHI nodes in a block that
 301          the phi alternative associated with a particular edge will be
 302          at the same index in the phi alternative array.
 303
 304          However, it is very likely they will be the same.  So we keep
 305          track of the index of the alternative where we found the edge in
 306          the previous phi node and check that index first in the next
 307          phi node.  If that hint fails, then we actually search all
 308          the entries.  */
 309       phi_num_args = PHI_NUM_ARGS (phi);
 310       hint = phi_num_args;
 311       for ( ; phi; phi = TREE_CHAIN (phi))
 312         {
 313           int i;
 314           tree new;
 315           tree *orig_p;
 316
 317           /* If the hint is valid (!= phi_num_args), see if it points
 318              us to the desired phi alternative.  */
 319           if (hint != phi_num_args && PHI_ARG_EDGE (phi, hint) == e)
 320             ;
 321           else
 322             {
 323               /* The hint was either invalid or did not point to the
 324                  correct phi alternative.  Search all the alternatives
 325                  for the correct one.  Update the hint.  */
 326               for (i = 0; i < phi_num_args; i++)
 327                 if (PHI_ARG_EDGE (phi, i) == e)
 328                   break;
 329               hint = i;
 330             }
 331
 332 #ifdef ENABLE_CHECKING
 333           /* If we did not find the proper alternative, then something is
 334              horribly wrong.  */
 335           if (hint == phi_num_args)
 336             abort ();
 337 #endif
 338
 339           /* The alternative may be associated with a constant, so verify
 340              it is an SSA_NAME before doing anything with it.  */
 341           orig_p = &PHI_ARG_DEF (phi, hint);
 342           if (TREE_CODE (*orig_p) != SSA_NAME)
 343             continue;
 344
 345           /* If we have *ORIG_P in our constant/copy table, then replace
 346              ORIG_P with its value in our constant/copy table.  */
 347           new = VARRAY_TREE (const_and_copies, SSA_NAME_VERSION (*orig_p));
 348           if (new
 349               && (TREE_CODE (new) == SSA_NAME
 350                   || is_gimple_min_invariant (new))
 351               && may_propagate_copy (*orig_p, new))
 352             propagate_value (orig_p, new);
 353         }
 354     }
 355 }