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