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   if (p1 == p2)
 147     {
 148       if (debug)
 149         fprintf (debug, " : Already coalesced.\n");
 150       return false;
 151     }
 152
 153   rep1 = partition_to_var (map, p1);
 154   rep2 = partition_to_var (map, p2);
 155   root1 = SSA_NAME_VAR (rep1);
 156   root2 = SSA_NAME_VAR (rep2);
 157   if (!root1 && !root2)
 158     return false;
 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 ((root1 && TREE_CODE (root1) == PARM_DECL)
 181       && (root2 && TREE_CODE (root2) == PARM_DECL))
 182     {
 183       if (debug)
 184         fprintf (debug, " : 2 different PARM_DECLS. No coalesce.\n");
 185       return false;
 186     }
 187
 188   if ((root1 && TREE_CODE (root1) == RESULT_DECL)
 189       != (root2 && TREE_CODE (root2) == RESULT_DECL))
 190     {
 191       if (debug)
 192         fprintf (debug, " : One root a RESULT_DECL. No coalesce.\n");
 193       return false;
 194     }
 195
 196   ign1 = !root1 || (TREE_CODE (root1) == VAR_DECL && DECL_IGNORED_P (root1));
 197   ign2 = !root2 || (TREE_CODE (root2) == VAR_DECL && DECL_IGNORED_P (root2));
 198
 199   /* Refrain from coalescing user variables, if requested.  */
 200   if (!ign1 && !ign2)
 201     {
 202       if (flag_ssa_coalesce_vars && DECL_FROM_INLINE (root2))
 203         ign2 = true;
 204       else if (flag_ssa_coalesce_vars && DECL_FROM_INLINE (root1))
 205         ign1 = true;
 206       else if (flag_ssa_coalesce_vars != 2)
 207         {
 208           if (debug)
 209             fprintf (debug, " : 2 different USER vars. No coalesce.\n");
 210           return false;
 211         }
 212       else
 213         ign2 = true;
 214     }
 215
 216   /* If both values have default defs, we can't coalesce.  If only one has a
 217      tag, make sure that variable is the new root partition.  */
 218   if (root1 && ssa_default_def (cfun, root1))
 219     {
 220       if (root2 && ssa_default_def (cfun, root2))
 221         {
 222           if (debug)
 223             fprintf (debug, " : 2 default defs. No coalesce.\n");
 224           return false;
 225         }
 226       else
 227         {
 228           ign2 = true;
 229           ign1 = false;
 230         }
 231     }
 232   else if (root2 && ssa_default_def (cfun, root2))
 233     {
 234       ign1 = true;
 235       ign2 = false;
 236     }
 237
 238   /* Do not coalesce if we cannot assign a symbol to the partition.  */
 239   if (!(!ign2 && root2)
 240       && !(!ign1 && root1))
 241     {
 242       if (debug)
 243         fprintf (debug, " : Choosen variable has no root.  No coalesce.\n");
 244       return false;
 245     }
 246
 247   /* Don't coalesce if the new chosen root variable would be read-only.
 248      If both ign1 && ign2, then the root var of the larger partition
 249      wins, so reject in that case if any of the root vars is TREE_READONLY.
 250      Otherwise reject only if the root var, on which replace_ssa_name_symbol
 251      will be called below, is readonly.  */
 252   if (((root1 && TREE_READONLY (root1)) && ign2)
 253       || ((root2 && TREE_READONLY (root2)) && ign1))
 254     {
 255       if (debug)
 256         fprintf (debug, " : Readonly variable.  No coalesce.\n");
 257       return false;
 258     }
 259
 260   /* Don't coalesce if the two variables aren't type compatible .  */
 261   if (!types_compatible_p (TREE_TYPE (var1), TREE_TYPE (var2))
 262       /* There is a disconnect between the middle-end type-system and
 263          VRP, avoid coalescing enum types with different bounds.  */
 264       || ((TREE_CODE (TREE_TYPE (var1)) == ENUMERAL_TYPE
 265            || TREE_CODE (TREE_TYPE (var2)) == ENUMERAL_TYPE)
 266           && TREE_TYPE (var1) != TREE_TYPE (var2)))
 267     {
 268       if (debug)
 269         fprintf (debug, " : Incompatible types.  No coalesce.\n");
 270       return false;
 271     }
 272
 273   /* Merge the two partitions.  */
 274   p3 = partition_union (map->var_partition, p1, p2);
 275
 276   /* Set the root variable of the partition to the better choice, if there is
 277      one.  */
 278   if (!ign2 && root2)
 279     replace_ssa_name_symbol (partition_to_var (map, p3), root2);
 280   else if (!ign1 && root1)
 281     replace_ssa_name_symbol (partition_to_var (map, p3), root1);
 282   else
 283     gcc_unreachable ();
 284
 285   if (debug)
 286     {
 287       fprintf (debug, " --> P%d ", p3);
 288       print_generic_expr (debug, SSA_NAME_VAR (partition_to_var (map, p3)),
 289                           TDF_SLIM);
 290       fprintf (debug, "\n");
 291     }
 292   return true;
 293 }
 294
 295
 296 /* This function will make a pass through the IL, and attempt to coalesce any
 297    SSA versions which occur in PHI's or copies.  Coalescing is accomplished by
 298    changing the underlying root variable of all coalesced version.  This will
 299    then cause the SSA->normal pass to attempt to coalesce them all to the same
 300    variable.  */
 301
 302 static unsigned int
 303 rename_ssa_copies (void)
 304 {
 305   var_map map;
 306   basic_block bb;
 307   gimple_stmt_iterator gsi;
 308   tree var, part_var;
 309   gimple stmt, phi;
 310   unsigned x;
 311   FILE *debug;
 312   bool updated = false;
 313
 314   memset (&stats, 0, sizeof (stats));
 315
 316   if (dump_file && (dump_flags & TDF_DETAILS))
 317     debug = dump_file;
 318   else
 319     debug = NULL;
 320
 321   map = init_var_map (num_ssa_names);
 322
 323   FOR_EACH_BB (bb)
 324     {
 325       /* Scan for real copies.  */
 326       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 327         {
 328           stmt = gsi_stmt (gsi);
 329           if (gimple_assign_ssa_name_copy_p (stmt))
 330             {
 331               tree lhs = gimple_assign_lhs (stmt);
 332               tree rhs = gimple_assign_rhs1 (stmt);
 333
 334               updated |= copy_rename_partition_coalesce (map, lhs, rhs, debug);
 335             }
 336         }
 337     }
 338
 339   FOR_EACH_BB (bb)
 340     {
 341       /* Treat PHI nodes as copies between the result and each argument.  */
 342       for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 343         {
 344           size_t i;
 345           tree res;
 346
 347           phi = gsi_stmt (gsi);
 348           res = gimple_phi_result (phi);
 349
 350           /* Do not process virtual SSA_NAMES.  */
 351           if (virtual_operand_p (res))
 352             continue;
 353
 354           /* Make sure to only use the same partition for an argument
 355              as the result but never the other way around.  */
 356           if (SSA_NAME_VAR (res)
 357               && !DECL_IGNORED_P (SSA_NAME_VAR (res)))
 358             for (i = 0; i < gimple_phi_num_args (phi); i++)
 359               {
 360                 tree arg = PHI_ARG_DEF (phi, i);
 361                 if (TREE_CODE (arg) == SSA_NAME)
 362                   updated |= copy_rename_partition_coalesce (map, res, arg,
 363                                                              debug);
 364               }
 365           /* Else if all arguments are in the same partition try to merge
 366              it with the result.  */
 367           else
 368             {
 369               int all_p_same = -1;
 370               int p = -1;
 371               for (i = 0; i < gimple_phi_num_args (phi); i++)
 372                 {
 373                   tree arg = PHI_ARG_DEF (phi, i);
 374                   if (TREE_CODE (arg) != SSA_NAME)
 375                     {
 376                       all_p_same = 0;
 377                       break;
 378                     }
 379                   else if (all_p_same == -1)
 380                     {
 381                       p = partition_find (map->var_partition,
 382                                           SSA_NAME_VERSION (arg));
 383                       all_p_same = 1;
 384                     }
 385                   else if (all_p_same == 1
 386                            && p != partition_find (map->var_partition,
 387                                                    SSA_NAME_VERSION (arg)))
 388                     {
 389                       all_p_same = 0;
 390                       break;
 391                     }
 392                 }
 393               if (all_p_same == 1)
 394                 updated |= copy_rename_partition_coalesce (map, res,
 395                                                            PHI_ARG_DEF (phi, 0),
 396                                                            debug);
 397             }
 398         }
 399     }
 400
 401   if (debug)
 402     dump_var_map (debug, map);
 403
 404   /* Now one more pass to make all elements of a partition share the same
 405      root variable.  */
 406
 407   for (x = 1; x < num_ssa_names; x++)
 408     {
 409       part_var = partition_to_var (map, x);
 410       if (!part_var)
 411         continue;
 412       var = ssa_name (x);
 413       if (SSA_NAME_VAR (var) == SSA_NAME_VAR (part_var))
 414         continue;
 415       if (debug)
 416         {
 417           fprintf (debug, "Coalesced ");
 418           print_generic_expr (debug, var, TDF_SLIM);
 419           fprintf (debug, " to ");
 420           print_generic_expr (debug, part_var, TDF_SLIM);
 421           fprintf (debug, "\n");
 422         }
 423       stats.coalesced++;
 424       replace_ssa_name_symbol (var, SSA_NAME_VAR (part_var));
 425     }
 426
 427   statistics_counter_event (cfun, "copies coalesced",
 428                             stats.coalesced);
 429   delete_var_map (map);
 430   return updated ? TODO_remove_unused_locals : 0;
 431 }
 432
 433 /* Return true if copy rename is to be performed.  */
 434
 435 static bool
 436 gate_copyrename (void)
 437 {
 438   return flag_tree_copyrename != 0;
 439 }
 440
 441 struct gimple_opt_pass pass_rename_ssa_copies =
 442 {
 443  {
 444   GIMPLE_PASS,
 445   "copyrename",                         /* name */
 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 };