gcc/tree-ssa-copyrename.c

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