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