gcc/tree-ssa-copyrename.c

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