gcc/tree-ssa-copyrename.c

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