gcc/tree-ssa-copyrename.c

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