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