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 = fold_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    v_may_def_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_v_may_defs;
 236   vuse_optype vuses;
 237   v_may_def_optype v_may_defs;
 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   v_may_defs = V_MAY_DEF_OPS (ann);
 261   num_v_may_defs = NUM_V_MAY_DEFS (v_may_defs);
 262   for (i = 0; i < num_v_may_defs; i++)
 263     {
 264       tree *op_p = V_MAY_DEF_OP_PTR (v_may_defs, 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    NONZERO_VARS is the set SSA_NAMES known to have a nonzero value,
 276    even if we don't know their precise value.
 277
 278    Propagate values from CONST_AND_COPIES and NONZERO_VARS into the PHI
 279    nodes of the successors of BB.  */
 280
 281 void
 282 cprop_into_successor_phis (basic_block bb,
 283                            varray_type const_and_copies,
 284                            bitmap nonzero_vars)
 285 {
 286   edge e;
 287
 288   /* This can get rather expensive if the implementation is naive in
 289      how it finds the phi alternative associated with a particular edge.  */
 290   for (e = bb->succ; e; e = e->succ_next)
 291     {
 292       tree phi;
 293       int phi_num_args;
 294       int hint;
 295
 296       /* If this is an abnormal edge, then we do not want to copy propagate
 297          into the PHI alternative associated with this edge.  */
 298       if (e->flags & EDGE_ABNORMAL)
 299         continue;
 300
 301       phi = phi_nodes (e->dest);
 302       if (! phi)
 303         continue;
 304
 305       /* There is no guarantee that for any two PHI nodes in a block that
 306          the phi alternative associated with a particular edge will be
 307          at the same index in the phi alternative array.
 308
 309          However, it is very likely they will be the same.  So we keep
 310          track of the index of the alternative where we found the edge in
 311          the previous phi node and check that index first in the next
 312          phi node.  If that hint fails, then we actually search all
 313          the entries.  */
 314       phi_num_args = PHI_NUM_ARGS (phi);
 315       hint = phi_num_args;
 316       for ( ; phi; phi = PHI_CHAIN (phi))
 317         {
 318           int i;
 319           tree new;
 320           tree *orig_p;
 321
 322           /* If the hint is valid (!= phi_num_args), see if it points
 323              us to the desired phi alternative.  */
 324           if (hint != phi_num_args && PHI_ARG_EDGE (phi, hint) == e)
 325             ;
 326           else
 327             {
 328               /* The hint was either invalid or did not point to the
 329                  correct phi alternative.  Search all the alternatives
 330                  for the correct one.  Update the hint.  */
 331               for (i = 0; i < phi_num_args; i++)
 332                 if (PHI_ARG_EDGE (phi, i) == e)
 333                   break;
 334               hint = i;
 335             }
 336
 337 #ifdef ENABLE_CHECKING
 338           /* If we did not find the proper alternative, then something is
 339              horribly wrong.  */
 340           if (hint == phi_num_args)
 341             abort ();
 342 #endif
 343
 344           /* The alternative may be associated with a constant, so verify
 345              it is an SSA_NAME before doing anything with it.  */
 346           orig_p = &PHI_ARG_DEF (phi, hint);
 347           if (TREE_CODE (*orig_p) != SSA_NAME)
 348             continue;
 349
 350           /* If the alternative is known to have a nonzero value, record
 351              that fact in the PHI node itself for future use.  */
 352           if (bitmap_bit_p (nonzero_vars, SSA_NAME_VERSION (*orig_p)))
 353             PHI_ARG_NONZERO (phi, hint) = true;
 354
 355           /* If we have *ORIG_P in our constant/copy table, then replace
 356              ORIG_P with its value in our constant/copy table.  */
 357           new = VARRAY_TREE (const_and_copies, SSA_NAME_VERSION (*orig_p));
 358           if (new
 359               && (TREE_CODE (new) == SSA_NAME
 360                   || is_gimple_min_invariant (new))
 361               && may_propagate_copy (*orig_p, new))
 362             propagate_value (orig_p, new);
 363         }
 364     }
 365 }