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