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