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
  58 /* Given two SSA_NAMEs, replace the annotations for the one referred to by OP
  59    with VAR's annmoptations.
  60
  61    If OP is a pointer, copy the memory tag used originally by OP into
  62    VAR.  This is needed in cases where VAR had never been dereferenced in the
  63    program.
  64
  65    If FOR_PROPAGATION is true, then perform additional checks to ensure
  66    that const/copy propagation of var for OP is valid.  */
  67
  68 static void
  69 replace_ssa_names_ann (tree op,
  70                    tree var,
  71                    bool for_propagation ATTRIBUTE_UNUSED)
  72 {
  73 #if defined ENABLE_CHECKING
  74   if (for_propagation && !may_propagate_copy (op, var))
  75     abort ();
  76 #endif
  77
  78   /* If VAR doesn't have a memory tag, copy the one from the original
  79      operand.  Also copy the dereferenced flags.  */
  80   if (POINTER_TYPE_P (TREE_TYPE (op)))
  81     {
  82       var_ann_t new_ann = var_ann (SSA_NAME_VAR (var));
  83       var_ann_t orig_ann = var_ann (SSA_NAME_VAR (op));
  84
  85       if (new_ann->type_mem_tag == NULL_TREE)
  86         new_ann->type_mem_tag = orig_ann->type_mem_tag;
  87       else if (orig_ann->type_mem_tag == NULL_TREE)
  88         orig_ann->type_mem_tag = new_ann->type_mem_tag;
  89       else if (new_ann->type_mem_tag != orig_ann->type_mem_tag)
  90         abort ();
  91     }
  92
  93 }
  94
  95
  96 /* Common code for propagate_value and replace_exp.
  97
  98    Replace use operand OP_P with VAL.  FOR_PROPAGATION indicates if the
  99    replacement is done to propagate a value or not.  */
 100
 101 static void
 102 replace_exp_1 (use_operand_p op_p, tree val, bool for_propagation)
 103 {
 104   if (TREE_CODE (val) == SSA_NAME)
 105     {
 106       if (TREE_CODE (USE_FROM_PTR (op_p)) == SSA_NAME)
 107         replace_ssa_names_ann (USE_FROM_PTR (op_p), val, for_propagation);
 108       SET_USE (op_p, val);
 109     }
 110   else
 111     SET_USE (op_p, lhd_unsave_expr_now (val));
 112 }
 113
 114 /* Propagate the value VAL (assumed to be a constant or another SSA_NAME)
 115    into the operand pointed by OP_P.
 116
 117    Use this version for const/copy propagation as it will perform additional
 118    checks to ensure validity of the const/copy propagation.  */
 119
 120 void
 121 propagate_value (use_operand_p op_p, tree val)
 122 {
 123   replace_exp_1 (op_p, val, true);
 124 }
 125
 126 /* Propagate the value VAL (assumed to be a constant or another SSA_NAME)
 127    into the tree pointed by OP_P.
 128
 129    Use this version for const/copy propagation when SSA operands are not
 130    available.  It will perform the additional checks to ensure validity of
 131    the const/copy propagation, but will not update any operand information.
 132    Be sure to mark the stmt as modified.  */
 133
 134 void
 135 propagate_tree_value (tree *op_p, tree val)
 136 {
 137   if (TREE_CODE (val) == SSA_NAME)
 138     {
 139       if (TREE_CODE (*op_p) == SSA_NAME)
 140         replace_ssa_names_ann (*op_p, val, true);
 141       *op_p = val;
 142     }
 143   else
 144     *op_p = lhd_unsave_expr_now (val);
 145 }
 146
 147 /* Replace *OP_P with value VAL (assumed to be a constant or another SSA_NAME).
 148
 149    Use this version when not const/copy propagating values.  For example,
 150    PRE uses this version when building expressions as they would appear
 151    in specific blocks taking into account actions of PHI nodes.  */
 152
 153 void
 154 replace_exp (use_operand_p op_p, tree val)
 155 {
 156   replace_exp_1 (op_p, val, false);
 157 }
 158
 159 /* Replace *OP_P in STMT with any known equivalent value for *OP_P from
 160    CONST_AND_COPIES.  */
 161
 162 static bool
 163 cprop_operand (stmt_ann_t ann, use_operand_p op_p, varray_type const_and_copies)
 164 {
 165   bool may_have_exposed_new_symbols = false;
 166   tree val;
 167   tree op = USE_FROM_PTR (op_p);
 168
 169   /* If the operand has a known constant value or it is known to be a
 170      copy of some other variable, use the value or copy stored in
 171      CONST_AND_COPIES.  */
 172   val = VARRAY_TREE (const_and_copies, SSA_NAME_VERSION (op));
 173   if (val)
 174     {
 175       tree op_type, val_type;
 176
 177       /* Do not change the base variable in the virtual operand
 178          tables.  That would make it impossible to reconstruct
 179          the renamed virtual operand if we later modify this
 180          statement.  Also only allow the new value to be an SSA_NAME
 181          for propagation into virtual operands.  */
 182       if (!is_gimple_reg (op)
 183           && (get_virtual_var (val) != get_virtual_var (op)
 184               || TREE_CODE (val) != SSA_NAME))
 185         return false;
 186
 187       /* Get the toplevel type of each operand.  */
 188       op_type = TREE_TYPE (op);
 189       val_type = TREE_TYPE (val);
 190
 191       /* While both types are pointers, get the type of the object
 192          pointed to.  */
 193       while (POINTER_TYPE_P (op_type) && POINTER_TYPE_P (val_type))
 194         {
 195           op_type = TREE_TYPE (op_type);
 196           val_type = TREE_TYPE (val_type);
 197         }
 198
 199       /* Make sure underlying types match before propagating a
 200          constant by converting the constant to the proper type.  Note
 201          that convert may return a non-gimple expression, in which case
 202          we ignore this propagation opportunity.  */
 203      if (!lang_hooks.types_compatible_p (op_type, val_type)
 204            && TREE_CODE (val) != SSA_NAME)
 205         {
 206           val = fold_convert (TREE_TYPE (op), val);
 207           if (!is_gimple_min_invariant (val)
 208               && TREE_CODE (val) != SSA_NAME)
 209             return false;
 210         }
 211
 212       /* Certain operands are not allowed to be copy propagated due
 213          to their interaction with exception handling and some GCC
 214          extensions.  */
 215       if (TREE_CODE (val) == SSA_NAME
 216           && !may_propagate_copy (op, val))
 217         return false;
 218
 219       /* Dump details.  */
 220       if (dump_file && (dump_flags & TDF_DETAILS))
 221         {
 222           fprintf (dump_file, "  Replaced '");
 223           print_generic_expr (dump_file, op, dump_flags);
 224           fprintf (dump_file, "' with %s '",
 225                    (TREE_CODE (val) != SSA_NAME ? "constant" : "variable"));
 226           print_generic_expr (dump_file, val, dump_flags);
 227           fprintf (dump_file, "'\n");
 228         }
 229
 230       /* If VAL is an ADDR_EXPR or a constant of pointer type, note
 231          that we may have exposed a new symbol for SSA renaming.  */
 232       if (TREE_CODE (val) == ADDR_EXPR
 233           || (POINTER_TYPE_P (TREE_TYPE (op))
 234               && is_gimple_min_invariant (val)))
 235         may_have_exposed_new_symbols = true;
 236
 237       propagate_value (op_p, val);
 238
 239       /* And note that we modified this statement.  This is now
 240          safe, even if we changed virtual operands since we will
 241          rescan the statement and rewrite its operands again.  */
 242       ann->modified = 1;
 243     }
 244   return may_have_exposed_new_symbols;
 245 }
 246
 247 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
 248    known value for that SSA_NAME (or NULL if no value is known).
 249
 250    Propagate values from CONST_AND_COPIES into the uses, vuses and
 251    v_may_def_ops of STMT.  */
 252
 253 bool
 254 cprop_into_stmt (tree stmt, varray_type const_and_copies)
 255 {
 256   bool may_have_exposed_new_symbols = false;
 257   stmt_ann_t ann = stmt_ann (stmt);
 258   size_t i, num_uses, num_vuses, num_v_may_defs;
 259   vuse_optype vuses;
 260   v_may_def_optype v_may_defs;
 261   use_optype uses;
 262
 263   uses = USE_OPS (ann);
 264   num_uses = NUM_USES (uses);
 265   for (i = 0; i < num_uses; i++)
 266     {
 267       use_operand_p op_p = USE_OP_PTR (uses, i);
 268       if (TREE_CODE (USE_FROM_PTR (op_p)) == SSA_NAME)
 269         may_have_exposed_new_symbols
 270           |= cprop_operand (ann, op_p, const_and_copies);
 271     }
 272
 273   vuses = VUSE_OPS (ann);
 274   num_vuses = NUM_VUSES (vuses);
 275   for (i = 0; i < num_vuses; i++)
 276     {
 277       use_operand_p op_p = VUSE_OP_PTR (vuses, i);
 278       if (TREE_CODE (USE_FROM_PTR (op_p)) == SSA_NAME)
 279         may_have_exposed_new_symbols
 280           |= cprop_operand (ann, op_p, const_and_copies);
 281     }
 282
 283   v_may_defs = V_MAY_DEF_OPS (ann);
 284   num_v_may_defs = NUM_V_MAY_DEFS (v_may_defs);
 285   for (i = 0; i < num_v_may_defs; i++)
 286     {
 287       use_operand_p op_p = V_MAY_DEF_OP_PTR (v_may_defs, i);
 288       if (TREE_CODE (USE_FROM_PTR (op_p)) == SSA_NAME)
 289         may_have_exposed_new_symbols
 290           |= cprop_operand (ann, op_p, const_and_copies);
 291     }
 292   return may_have_exposed_new_symbols;
 293 }
 294
 295 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
 296    known value for that SSA_NAME (or NULL if no value is known).
 297
 298    NONZERO_VARS is the set SSA_NAMES known to have a nonzero value,
 299    even if we don't know their precise value.
 300
 301    Propagate values from CONST_AND_COPIES and NONZERO_VARS into the PHI
 302    nodes of the successors of BB.  */
 303
 304 void
 305 cprop_into_successor_phis (basic_block bb,
 306                            varray_type const_and_copies,
 307                            bitmap nonzero_vars)
 308 {
 309   edge e;
 310
 311   /* This can get rather expensive if the implementation is naive in
 312      how it finds the phi alternative associated with a particular edge.  */
 313   for (e = bb->succ; e; e = e->succ_next)
 314     {
 315       tree phi;
 316       int phi_num_args;
 317       int hint;
 318
 319       /* If this is an abnormal edge, then we do not want to copy propagate
 320          into the PHI alternative associated with this edge.  */
 321       if (e->flags & EDGE_ABNORMAL)
 322         continue;
 323
 324       phi = phi_nodes (e->dest);
 325       if (! phi)
 326         continue;
 327
 328       /* There is no guarantee that for any two PHI nodes in a block that
 329          the phi alternative associated with a particular edge will be
 330          at the same index in the phi alternative array.
 331
 332          However, it is very likely they will be the same.  So we keep
 333          track of the index of the alternative where we found the edge in
 334          the previous phi node and check that index first in the next
 335          phi node.  If that hint fails, then we actually search all
 336          the entries.  */
 337       phi_num_args = PHI_NUM_ARGS (phi);
 338       hint = phi_num_args;
 339       for ( ; phi; phi = PHI_CHAIN (phi))
 340         {
 341           int i;
 342           tree new;
 343           use_operand_p orig_p;
 344           tree orig;
 345
 346           /* If the hint is valid (!= phi_num_args), see if it points
 347              us to the desired phi alternative.  */
 348           if (hint != phi_num_args && PHI_ARG_EDGE (phi, hint) == e)
 349             ;
 350           else
 351             {
 352               /* The hint was either invalid or did not point to the
 353                  correct phi alternative.  Search all the alternatives
 354                  for the correct one.  Update the hint.  */
 355               for (i = 0; i < phi_num_args; i++)
 356                 if (PHI_ARG_EDGE (phi, i) == e)
 357                   break;
 358               hint = i;
 359             }
 360
 361 #ifdef ENABLE_CHECKING
 362           /* If we did not find the proper alternative, then something is
 363              horribly wrong.  */
 364           if (hint == phi_num_args)
 365             abort ();
 366 #endif
 367
 368           /* The alternative may be associated with a constant, so verify
 369              it is an SSA_NAME before doing anything with it.  */
 370           orig_p = PHI_ARG_DEF_PTR (phi, hint);
 371           orig = USE_FROM_PTR (orig_p);
 372           if (TREE_CODE (orig) != SSA_NAME)
 373             continue;
 374
 375           /* If the alternative is known to have a nonzero value, record
 376              that fact in the PHI node itself for future use.  */
 377           if (bitmap_bit_p (nonzero_vars, SSA_NAME_VERSION (orig)))
 378             PHI_ARG_NONZERO (phi, hint) = true;
 379
 380           /* If we have *ORIG_P in our constant/copy table, then replace
 381              ORIG_P with its value in our constant/copy table.  */
 382           new = VARRAY_TREE (const_and_copies, SSA_NAME_VERSION (orig));
 383           if (new
 384               && (TREE_CODE (new) == SSA_NAME
 385                   || is_gimple_min_invariant (new))
 386               && may_propagate_copy (orig, new))
 387             propagate_value (orig_p, new);
 388         }
 389     }
 390 }