gcc/tree-ssa-copyrename.c

   1 /* Rename SSA copies.
   2    Copyright (C) 2004, 2006, 2007, 2008, 2009, 2010
   3    Free Software Foundation, Inc.
   4    Contributed by Andrew MacLeod <amacleod@redhat.com>
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify
   9 it under the terms of the GNU General Public License as published by
  10 the Free Software Foundation; either version 3, or (at your option)
  11 any later version.
  12
  13 GCC is distributed in the hope that it will be useful,
  14 but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 GNU General Public License for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tm.h"
  26 #include "tree.h"
  27 #include "gimple.h"
  28 #include "flags.h"
  29 #include "basic-block.h"
  30 #include "function.h"
  31 #include "diagnostic.h"
  32 #include "tree-pretty-print.h"
  33 #include "bitmap.h"
  34 #include "tree-flow.h"
  35 #include "gimple.h"
  36 #include "tree-inline.h"
  37 #include "timevar.h"
  38 #include "hashtab.h"
  39 #include "tree-dump.h"
  40 #include "tree-ssa-live.h"
  41 #include "tree-pass.h"
  42 #include "langhooks.h"
  43
  44 /* The following routines implement the SSA copy renaming phase.
  45
  46    This optimization looks for copies between 2 SSA_NAMES, either through a
  47    direct copy, or an implicit one via a PHI node result and its arguments.
  48
  49    Each copy is examined to determine if it is possible to rename the base
  50    variable of one of the operands to the same variable as the other operand.
  51    i.e.
  52    T.3_5 = <blah>
  53    a_1 = T.3_5
  54
  55    If this copy couldn't be copy propagated, it could possibly remain in the
  56    program throughout the optimization phases.   After SSA->normal, it would
  57    become:
  58
  59    T.3 = <blah>
  60    a = T.3
  61
  62    Since T.3_5 is distinct from all other SSA versions of T.3, there is no
  63    fundamental reason why the base variable needs to be T.3, subject to
  64    certain restrictions.  This optimization attempts to determine if we can
  65    change the base variable on copies like this, and result in code such as:
  66
  67    a_5 = <blah>
  68    a_1 = a_5
  69
  70    This gives the SSA->normal pass a shot at coalescing a_1 and a_5. If it is
  71    possible, the copy goes away completely. If it isn't possible, a new temp
  72    will be created for a_5, and you will end up with the exact same code:
  73
  74    a.8 = <blah>
  75    a = a.8
  76
  77    The other benefit of performing this optimization relates to what variables
  78    are chosen in copies.  Gimplification of the program uses temporaries for
  79    a lot of things. expressions like
  80
  81    a_1 = <blah>
  82    <blah2> = a_1
  83
  84    get turned into
  85
  86    T.3_5 = <blah>
  87    a_1 = T.3_5
  88    <blah2> = a_1
  89
  90    Copy propagation is done in a forward direction, and if we can propagate
  91    through the copy, we end up with:
  92
  93    T.3_5 = <blah>
  94    <blah2> = T.3_5
  95
  96    The copy is gone, but so is all reference to the user variable 'a'. By
  97    performing this optimization, we would see the sequence:
  98
  99    a_5 = <blah>
 100    a_1 = a_5
 101    <blah2> = a_1
 102
 103    which copy propagation would then turn into:
 104
 105    a_5 = <blah>
 106    <blah2> = a_5
 107
 108    and so we still retain the user variable whenever possible.  */
 109
 110
 111 /* Coalesce the partitions in MAP representing VAR1 and VAR2 if it is valid.
 112    Choose a representative for the partition, and send debug info to DEBUG.  */
 113
 114 static bool
 115 copy_rename_partition_coalesce (var_map map, tree var1, tree var2, FILE *debug)
 116 {
 117   int p1, p2, p3;
 118   tree root1, root2;
 119   tree rep1, rep2;
 120   bool ign1, ign2, abnorm;
 121
 122   gcc_assert (TREE_CODE (var1) == SSA_NAME);
 123   gcc_assert (TREE_CODE (var2) == SSA_NAME);
 124
 125   register_ssa_partition (map, var1);
 126   register_ssa_partition (map, var2);
 127
 128   p1 = partition_find (map->var_partition, SSA_NAME_VERSION (var1));
 129   p2 = partition_find (map->var_partition, SSA_NAME_VERSION (var2));
 130
 131   if (debug)
 132     {
 133       fprintf (debug, "Try : ");
 134       print_generic_expr (debug, var1, TDF_SLIM);
 135       fprintf (debug, "(P%d) & ", p1);
 136       print_generic_expr (debug, var2, TDF_SLIM);
 137       fprintf (debug, "(P%d)", p2);
 138     }
 139
 140   gcc_assert (p1 != NO_PARTITION);
 141   gcc_assert (p2 != NO_PARTITION);
 142
 143   rep1 = partition_to_var (map, p1);
 144   rep2 = partition_to_var (map, p2);
 145   root1 = SSA_NAME_VAR (rep1);
 146   root2 = SSA_NAME_VAR (rep2);
 147
 148   if (p1 == p2)
 149     {
 150       if (debug)
 151         fprintf (debug, " : Already coalesced.\n");
 152       return false;
 153     }
 154
 155   /* Don't coalesce if one of the variables occurs in an abnormal PHI.  */
 156   abnorm = (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rep1)
 157             || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rep2));
 158   if (abnorm)
 159     {
 160       if (debug)
 161         fprintf (debug, " : Abnormal PHI barrier.  No coalesce.\n");
 162       return false;
 163     }
 164
 165   /* Partitions already have the same root, simply merge them.  */
 166   if (root1 == root2)
 167     {
 168       p1 = partition_union (map->var_partition, p1, p2);
 169       if (debug)
 170         fprintf (debug, " : Same root, coalesced --> P%d.\n", p1);
 171       return false;
 172     }
 173
 174   /* Never attempt to coalesce 2 difference parameters.  */
 175   if (TREE_CODE (root1) == PARM_DECL && TREE_CODE (root2) == PARM_DECL)
 176     {
 177       if (debug)
 178         fprintf (debug, " : 2 different PARM_DECLS. No coalesce.\n");
 179       return false;
 180     }
 181
 182   if ((TREE_CODE (root1) == RESULT_DECL) != (TREE_CODE (root2) == RESULT_DECL))
 183     {
 184       if (debug)
 185         fprintf (debug, " : One root a RESULT_DECL. No coalesce.\n");
 186       return false;
 187     }
 188
 189   ign1 = TREE_CODE (root1) == VAR_DECL && DECL_IGNORED_P (root1);
 190   ign2 = TREE_CODE (root2) == VAR_DECL && DECL_IGNORED_P (root2);
 191
 192   /* Never attempt to coalesce 2 user variables unless one is an inline
 193      variable.  */
 194   if (!ign1 && !ign2)
 195     {
 196       if (DECL_FROM_INLINE (root2))
 197         ign2 = true;
 198       else if (DECL_FROM_INLINE (root1))
 199         ign1 = true;
 200       else
 201         {
 202           if (debug)
 203             fprintf (debug, " : 2 different USER vars. No coalesce.\n");
 204           return false;
 205         }
 206     }
 207
 208   /* If both values have default defs, we can't coalesce.  If only one has a
 209      tag, make sure that variable is the new root partition.  */
 210   if (gimple_default_def (cfun, root1))
 211     {
 212       if (gimple_default_def (cfun, root2))
 213         {
 214           if (debug)
 215             fprintf (debug, " : 2 default defs. No coalesce.\n");
 216           return false;
 217         }
 218       else
 219         {
 220           ign2 = true;
 221           ign1 = false;
 222         }
 223     }
 224   else if (gimple_default_def (cfun, root2))
 225     {
 226       ign1 = true;
 227       ign2 = false;
 228     }
 229
 230   /* Don't coalesce if the two variables aren't type compatible.  */
 231   if (!types_compatible_p (TREE_TYPE (root1), TREE_TYPE (root2)))
 232     {
 233       if (debug)
 234         fprintf (debug, " : Incompatible types.  No coalesce.\n");
 235       return false;
 236     }
 237
 238   /* Merge the two partitions.  */
 239   p3 = partition_union (map->var_partition, p1, p2);
 240
 241   /* Set the root variable of the partition to the better choice, if there is
 242      one.  */
 243   if (!ign2)
 244     replace_ssa_name_symbol (partition_to_var (map, p3), root2);
 245   else if (!ign1)
 246     replace_ssa_name_symbol (partition_to_var (map, p3), root1);
 247
 248   if (debug)
 249     {
 250       fprintf (debug, " --> P%d ", p3);
 251       print_generic_expr (debug, SSA_NAME_VAR (partition_to_var (map, p3)),
 252                           TDF_SLIM);
 253       fprintf (debug, "\n");
 254     }
 255   return true;
 256 }
 257
 258
 259 /* This function will make a pass through the IL, and attempt to coalesce any
 260    SSA versions which occur in PHI's or copies.  Coalescing is accomplished by
 261    changing the underlying root variable of all coalesced version.  This will
 262    then cause the SSA->normal pass to attempt to coalesce them all to the same
 263    variable.  */
 264
 265 static unsigned int
 266 rename_ssa_copies (void)
 267 {
 268   var_map map;
 269   basic_block bb;
 270   gimple_stmt_iterator gsi;
 271   tree var, part_var;
 272   gimple stmt, phi;
 273   unsigned x;
 274   FILE *debug;
 275   bool updated = false;
 276
 277   if (dump_file && (dump_flags & TDF_DETAILS))
 278     debug = dump_file;
 279   else
 280     debug = NULL;
 281
 282   map = init_var_map (num_ssa_names);
 283
 284   FOR_EACH_BB (bb)
 285     {
 286       /* Scan for real copies.  */
 287       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 288         {
 289           stmt = gsi_stmt (gsi);
 290           if (gimple_assign_ssa_name_copy_p (stmt))
 291             {
 292               tree lhs = gimple_assign_lhs (stmt);
 293               tree rhs = gimple_assign_rhs1 (stmt);
 294
 295               updated |= copy_rename_partition_coalesce (map, lhs, rhs, debug);
 296             }
 297         }
 298     }
 299
 300   FOR_EACH_BB (bb)
 301     {
 302       /* Treat PHI nodes as copies between the result and each argument.  */
 303       for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 304         {
 305           size_t i;
 306           tree res;
 307
 308           phi = gsi_stmt (gsi);
 309           res = gimple_phi_result (phi);
 310
 311           /* Do not process virtual SSA_NAMES.  */
 312           if (!is_gimple_reg (SSA_NAME_VAR (res)))
 313             continue;
 314
 315           for (i = 0; i < gimple_phi_num_args (phi); i++)
 316             {
 317               tree arg = gimple_phi_arg (phi, i)->def;
 318               if (TREE_CODE (arg) == SSA_NAME)
 319                 updated |= copy_rename_partition_coalesce (map, res, arg, debug);
 320             }
 321         }
 322     }
 323
 324   if (debug)
 325     dump_var_map (debug, map);
 326
 327   /* Now one more pass to make all elements of a partition share the same
 328      root variable.  */
 329
 330   for (x = 1; x < num_ssa_names; x++)
 331     {
 332       part_var = partition_to_var (map, x);
 333       if (!part_var)
 334         continue;
 335       var = ssa_name (x);
 336       if (debug)
 337         {
 338           if (SSA_NAME_VAR (var) != SSA_NAME_VAR (part_var))
 339             {
 340               fprintf (debug, "Coalesced ");
 341               print_generic_expr (debug, var, TDF_SLIM);
 342               fprintf (debug, " to ");
 343               print_generic_expr (debug, part_var, TDF_SLIM);
 344               fprintf (debug, "\n");
 345             }
 346         }
 347       replace_ssa_name_symbol (var, SSA_NAME_VAR (part_var));
 348     }
 349
 350   delete_var_map (map);
 351   return updated ? TODO_remove_unused_locals : 0;
 352 }
 353
 354 /* Return true if copy rename is to be performed.  */
 355
 356 static bool
 357 gate_copyrename (void)
 358 {
 359   return flag_tree_copyrename != 0;
 360 }
 361
 362 struct gimple_opt_pass pass_rename_ssa_copies =
 363 {
 364  {
 365   GIMPLE_PASS,
 366   "copyrename",                         /* name */
 367   gate_copyrename,                      /* gate */
 368   rename_ssa_copies,                    /* execute */
 369   NULL,                                 /* sub */
 370   NULL,                                 /* next */
 371   0,                                    /* static_pass_number */
 372   TV_TREE_COPY_RENAME,                  /* tv_id */
 373   PROP_cfg | PROP_ssa,                  /* properties_required */
 374   0,                                    /* properties_provided */
 375   0,                                    /* properties_destroyed */
 376   0,                                    /* todo_flags_start */
 377   TODO_dump_func | TODO_verify_ssa      /* todo_flags_finish */
 378  }
 379 };