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   if (DECL_HARD_REGISTER (root1) || DECL_HARD_REGISTER (root2))
 150     {
 151       if (debug)
 152         {
 153           if (DECL_HARD_REGISTER (root1))
 154             print_generic_expr (debug, var1, TDF_SLIM);
 155           else
 156             print_generic_expr (debug, var2, TDF_SLIM);
 157           fprintf (debug, " is a hardware register.  No Coalescing.\n");
 158         }
 159       return;
 160     }
 161
 162   ann1 = var_ann (root1);
 163   ann2 = var_ann (root2);
 164
 165   if (p1 == p2)
 166     {
 167       if (debug)
 168         fprintf (debug, " : Already coalesced.\n");
 169       return;
 170     }
 171
 172   /* Don't coalesce if one of the variables occurs in an abnormal PHI.  */
 173   abnorm = (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rep1)
 174             || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rep2));
 175   if (abnorm)
 176     {
 177       if (debug)
 178         fprintf (debug, " : Abnormal PHI barrier.  No coalesce.\n");
 179       return;
 180     }
 181
 182   /* Partitions already have the same root, simply merge them.  */
 183   if (root1 == root2)
 184     {
 185       p1 = partition_union (map->var_partition, p1, p2);
 186       if (debug)
 187         fprintf (debug, " : Same root, coalesced --> P%d.\n", p1);
 188       return;
 189     }
 190
 191   /* Never attempt to coalesce 2 difference parameters.  */
 192   if (TREE_CODE (root1) == PARM_DECL && TREE_CODE (root2) == PARM_DECL)
 193     {
 194       if (debug)
 195         fprintf (debug, " : 2 different PARM_DECLS. No coalesce.\n");
 196       return;
 197     }
 198
 199   if ((TREE_CODE (root1) == RESULT_DECL) != (TREE_CODE (root2) == RESULT_DECL))
 200     {
 201       if (debug)
 202         fprintf (debug, " : One root a RESULT_DECL. No coalesce.\n");
 203       return;
 204     }
 205
 206   ign1 = TREE_CODE (root1) == VAR_DECL && DECL_IGNORED_P (root1);
 207   ign2 = TREE_CODE (root2) == VAR_DECL && DECL_IGNORED_P (root2);
 208
 209   /* Never attempt to coalesce 2 user variables unless one is an inline
 210      variable.  */
 211   if (!ign1 && !ign2)
 212     {
 213       if (DECL_FROM_INLINE (root2))
 214         ign2 = true;
 215       else if (DECL_FROM_INLINE (root1))
 216         ign1 = true;
 217       else
 218         {
 219           if (debug)
 220             fprintf (debug, " : 2 different USER vars. No coalesce.\n");
 221           return;
 222         }
 223     }
 224
 225   /* Don't coalesce if there are two different memory tags.  */
 226   if (ann1->type_mem_tag && ann2->type_mem_tag
 227       && ann1->type_mem_tag != ann2->type_mem_tag)
 228     {
 229       if (debug)
 230         fprintf (debug, " : 2 memory tags. No coalesce.\n");
 231       return;
 232     }
 233
 234   /* If both values have default defs, we can't coalesce.  If only one has a
 235      tag, make sure that variable is the new root partition.  */
 236   if (default_def (root1))
 237     {
 238       if (default_def (root2))
 239         {
 240           if (debug)
 241             fprintf (debug, " : 2 default defs. No coalesce.\n");
 242           return;
 243         }
 244       else
 245         {
 246           ign2 = true;
 247           ign1 = false;
 248         }
 249     }
 250   else if (default_def (root2))
 251     {
 252       ign1 = true;
 253       ign2 = false;
 254     }
 255
 256   /* Don't coalesce if the two variables aren't type compatible.  */
 257   if (!lang_hooks.types_compatible_p (TREE_TYPE (root1), TREE_TYPE (root2)))
 258     {
 259       if (debug)
 260         fprintf (debug, " : Incompatible types.  No coalesce.\n");
 261       return;
 262     }
 263
 264   /* Don't coalesce if the aliasing sets of the types are different.  */
 265   if (POINTER_TYPE_P (TREE_TYPE (root1))
 266       && POINTER_TYPE_P (TREE_TYPE (root2))
 267       && get_alias_set (TREE_TYPE (TREE_TYPE (root1)))
 268           != get_alias_set (TREE_TYPE (TREE_TYPE (root2))))
 269     {
 270       if (debug)
 271         fprintf (debug, " : 2 different alasing sets. No coalesce.\n");
 272       return;
 273     }
 274
 275
 276   /* Merge the two partitions.  */
 277   p3 = partition_union (map->var_partition, p1, p2);
 278
 279   /* Set the root variable of the partition to the better choice, if there is
 280      one.  */
 281   if (!ign2)
 282     replace_ssa_name_symbol (partition_to_var (map, p3), root2);
 283   else if (!ign1)
 284     replace_ssa_name_symbol (partition_to_var (map, p3), root1);
 285
 286   /* Update the various flag widgitry of the current base representative.  */
 287   ann3 = var_ann (SSA_NAME_VAR (partition_to_var (map, p3)));
 288   if (ann1->type_mem_tag)
 289     ann3->type_mem_tag = ann1->type_mem_tag;
 290   else
 291     ann3->type_mem_tag = ann2->type_mem_tag;
 292
 293   if (debug)
 294     {
 295       fprintf (debug, " --> P%d ", p3);
 296       print_generic_expr (debug, SSA_NAME_VAR (partition_to_var (map, p3)),
 297                           TDF_SLIM);
 298       fprintf (debug, "\n");
 299     }
 300 }
 301
 302
 303 /* This function will make a pass through the IL, and attempt to coalesce any
 304    SSA versions which occur in PHI's or copies.  Coalescing is accomplished by
 305    changing the underlying root variable of all coalesced version.  This will
 306    then cause the SSA->normal pass to attempt to coalesce them all to the same
 307    variable.  */
 308
 309 void
 310 rename_ssa_copies (void)
 311 {
 312   var_map map;
 313   basic_block bb;
 314   block_stmt_iterator bsi;
 315   tree phi, stmt, var, part_var;
 316   unsigned x;
 317   FILE *debug;
 318
 319   if (dump_file && (dump_flags & TDF_DETAILS))
 320     debug = dump_file;
 321   else
 322     debug = NULL;
 323
 324   map = init_var_map (num_ssa_names + 1);
 325
 326   FOR_EACH_BB (bb)
 327     {
 328       /* Scan for real copies.  */
 329       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 330         {
 331           stmt = bsi_stmt (bsi);
 332           if (TREE_CODE (stmt) == MODIFY_EXPR)
 333             {
 334               tree lhs = TREE_OPERAND (stmt, 0);
 335               tree rhs = TREE_OPERAND (stmt, 1);
 336
 337               if (TREE_CODE (lhs) == SSA_NAME && TREE_CODE (rhs) == SSA_NAME)
 338                 copy_rename_partition_coalesce (map, lhs, rhs, debug);
 339             }
 340         }
 341     }
 342
 343   FOR_EACH_BB (bb)
 344     {
 345       /* Treat PHI nodes as copies between the result and each argument.  */
 346       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 347         {
 348           int i;
 349           tree res = PHI_RESULT (phi);
 350
 351           /* Do not process virtual SSA_NAMES.  */
 352           if (!is_gimple_reg (SSA_NAME_VAR (res)))
 353             continue;
 354
 355           for (i = 0; i < PHI_NUM_ARGS (phi); i++)
 356             {
 357               tree arg = PHI_ARG_DEF (phi, i);
 358               if (TREE_CODE (arg) == SSA_NAME)
 359                 copy_rename_partition_coalesce (map, res, arg, debug);
 360             }
 361         }
 362     }
 363
 364   if (debug)
 365     dump_var_map (debug, map);
 366
 367   /* Now one more pass to make all elements of a partition share the same
 368      root variable.  */
 369
 370   for (x = 1; x <= num_ssa_names; x++)
 371     {
 372       part_var = partition_to_var (map, x);
 373       if (!part_var)
 374         continue;
 375       var = map->partition_to_var[x];
 376       if (debug)
 377         {
 378           if (SSA_NAME_VAR (var) != SSA_NAME_VAR (part_var))
 379             {
 380               fprintf (debug, "Coalesced ");
 381               print_generic_expr (debug, var, TDF_SLIM);
 382               fprintf (debug, " to ");
 383               print_generic_expr (debug, part_var, TDF_SLIM);
 384               fprintf (debug, "\n");
 385             }
 386         }
 387       replace_ssa_name_symbol (var, SSA_NAME_VAR (part_var));
 388     }
 389
 390   delete_var_map (map);
 391 }
 392
 393 /* Return true if copy rename is to be performed.  */
 394
 395 static bool
 396 gate_copyrename (void)
 397 {
 398   return flag_tree_copyrename != 0;
 399 }
 400
 401 struct tree_opt_pass pass_rename_ssa_copies =
 402 {
 403   "copyrename",                         /* name */
 404   gate_copyrename,                      /* gate */
 405   rename_ssa_copies,                    /* execute */
 406   NULL,                                 /* sub */
 407   NULL,                                 /* next */
 408   0,                                    /* static_pass_number */
 409   TV_TREE_COPY_RENAME,                  /* tv_id */
 410   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
 411   0,                                    /* properties_provided */
 412   0,                                    /* properties_destroyed */
 413   0,                                    /* todo_flags_start */
 414   TODO_dump_func | TODO_verify_ssa,     /* todo_flags_finish */
 415   0                                     /* letter */
 416 };
 417