gcc/tree-ssa-copyrename.c

   1 /* Rename SSA copies.
   2    Copyright (C) 2004-2013 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 "gimple-iterator.h"
  28 #include "flags.h"
  29 #include "basic-block.h"
  30 #include "function.h"
  31 #include "tree-pretty-print.h"
  32 #include "bitmap.h"
  33 #include "gimple-ssa.h"
  34 #include "tree-ssanames.h"
  35 #include "tree-dfa.h"
  36 #include "tree-inline.h"
  37 #include "hashtab.h"
  38 #include "tree-ssa-live.h"
  39 #include "tree-pass.h"
  40 #include "langhooks.h"
  41
  42 static struct
  43 {
  44   /* Number of copies coalesced.  */
  45   int coalesced;
  46 } stats;
  47
  48 /* The following routines implement the SSA copy renaming phase.
  49
  50    This optimization looks for copies between 2 SSA_NAMES, either through a
  51    direct copy, or an implicit one via a PHI node result and its arguments.
  52
  53    Each copy is examined to determine if it is possible to rename the base
  54    variable of one of the operands to the same variable as the other operand.
  55    i.e.
  56    T.3_5 = <blah>
  57    a_1 = T.3_5
  58
  59    If this copy couldn't be copy propagated, it could possibly remain in the
  60    program throughout the optimization phases.   After SSA->normal, it would
  61    become:
  62
  63    T.3 = <blah>
  64    a = T.3
  65
  66    Since T.3_5 is distinct from all other SSA versions of T.3, there is no
  67    fundamental reason why the base variable needs to be T.3, subject to
  68    certain restrictions.  This optimization attempts to determine if we can
  69    change the base variable on copies like this, and result in code such as:
  70
  71    a_5 = <blah>
  72    a_1 = a_5
  73
  74    This gives the SSA->normal pass a shot at coalescing a_1 and a_5. If it is
  75    possible, the copy goes away completely. If it isn't possible, a new temp
  76    will be created for a_5, and you will end up with the exact same code:
  77
  78    a.8 = <blah>
  79    a = a.8
  80
  81    The other benefit of performing this optimization relates to what variables
  82    are chosen in copies.  Gimplification of the program uses temporaries for
  83    a lot of things. expressions like
  84
  85    a_1 = <blah>
  86    <blah2> = a_1
  87
  88    get turned into
  89
  90    T.3_5 = <blah>
  91    a_1 = T.3_5
  92    <blah2> = a_1
  93
  94    Copy propagation is done in a forward direction, and if we can propagate
  95    through the copy, we end up with:
  96
  97    T.3_5 = <blah>
  98    <blah2> = T.3_5
  99
 100    The copy is gone, but so is all reference to the user variable 'a'. By
 101    performing this optimization, we would see the sequence:
 102
 103    a_5 = <blah>
 104    a_1 = a_5
 105    <blah2> = a_1
 106
 107    which copy propagation would then turn into:
 108
 109    a_5 = <blah>
 110    <blah2> = a_5
 111
 112    and so we still retain the user variable whenever possible.  */
 113
 114
 115 /* Coalesce the partitions in MAP representing VAR1 and VAR2 if it is valid.
 116    Choose a representative for the partition, and send debug info to DEBUG.  */
 117
 118 static void
 119 copy_rename_partition_coalesce (var_map map, tree var1, tree var2, FILE *debug)
 120 {
 121   int p1, p2, p3;
 122   tree root1, root2;
 123   tree rep1, rep2;
 124   bool ign1, ign2, abnorm;
 125
 126   gcc_assert (TREE_CODE (var1) == SSA_NAME);
 127   gcc_assert (TREE_CODE (var2) == SSA_NAME);
 128
 129   register_ssa_partition (map, var1);
 130   register_ssa_partition (map, var2);
 131
 132   p1 = partition_find (map->var_partition, SSA_NAME_VERSION (var1));
 133   p2 = partition_find (map->var_partition, SSA_NAME_VERSION (var2));
 134
 135   if (debug)
 136     {
 137       fprintf (debug, "Try : ");
 138       print_generic_expr (debug, var1, TDF_SLIM);
 139       fprintf (debug, "(P%d) & ", p1);
 140       print_generic_expr (debug, var2, TDF_SLIM);
 141       fprintf (debug, "(P%d)", p2);
 142     }
 143
 144   gcc_assert (p1 != NO_PARTITION);
 145   gcc_assert (p2 != NO_PARTITION);
 146
 147   if (p1 == p2)
 148     {
 149       if (debug)
 150         fprintf (debug, " : Already coalesced.\n");
 151       return;
 152     }
 153
 154   rep1 = partition_to_var (map, p1);
 155   rep2 = partition_to_var (map, p2);
 156   root1 = SSA_NAME_VAR (rep1);
 157   root2 = SSA_NAME_VAR (rep2);
 158   if (!root1 && !root2)
 159     return;
 160
 161   /* Don't coalesce if one of the variables occurs in an abnormal PHI.  */
 162   abnorm = (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rep1)
 163             || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rep2));
 164   if (abnorm)
 165     {
 166       if (debug)
 167         fprintf (debug, " : Abnormal PHI barrier.  No coalesce.\n");
 168       return;
 169     }
 170
 171   /* Partitions already have the same root, simply merge them.  */
 172   if (root1 == root2)
 173     {
 174       p1 = partition_union (map->var_partition, p1, p2);
 175       if (debug)
 176         fprintf (debug, " : Same root, coalesced --> P%d.\n", p1);
 177       return;
 178     }
 179
 180   /* Never attempt to coalesce 2 different parameters.  */
 181   if ((root1 && TREE_CODE (root1) == PARM_DECL)
 182       && (root2 && TREE_CODE (root2) == PARM_DECL))
 183     {
 184       if (debug)
 185         fprintf (debug, " : 2 different PARM_DECLS. No coalesce.\n");
 186       return;
 187     }
 188
 189   if ((root1 && TREE_CODE (root1) == RESULT_DECL)
 190       != (root2 && TREE_CODE (root2) == RESULT_DECL))
 191     {
 192       if (debug)
 193         fprintf (debug, " : One root a RESULT_DECL. No coalesce.\n");
 194       return;
 195     }
 196
 197   ign1 = !root1 || (TREE_CODE (root1) == VAR_DECL && DECL_IGNORED_P (root1));
 198   ign2 = !root2 || (TREE_CODE (root2) == VAR_DECL && DECL_IGNORED_P (root2));
 199
 200   /* Refrain from coalescing user variables, if requested.  */
 201   if (!ign1 && !ign2)
 202     {
 203       if (flag_ssa_coalesce_vars && DECL_FROM_INLINE (root2))
 204         ign2 = true;
 205       else if (flag_ssa_coalesce_vars && DECL_FROM_INLINE (root1))
 206         ign1 = true;
 207       else if (flag_ssa_coalesce_vars != 2)
 208         {
 209           if (debug)
 210             fprintf (debug, " : 2 different USER vars. No coalesce.\n");
 211           return;
 212         }
 213       else
 214         ign2 = true;
 215     }
 216
 217   /* If both values have default defs, we can't coalesce.  If only one has a
 218      tag, make sure that variable is the new root partition.  */
 219   if (root1 && ssa_default_def (cfun, root1))
 220     {
 221       if (root2 && ssa_default_def (cfun, root2))
 222         {
 223           if (debug)
 224             fprintf (debug, " : 2 default defs. No coalesce.\n");
 225           return;
 226         }
 227       else
 228         {
 229           ign2 = true;
 230           ign1 = false;
 231         }
 232     }
 233   else if (root2 && ssa_default_def (cfun, root2))
 234     {
 235       ign1 = true;
 236       ign2 = false;
 237     }
 238
 239   /* Do not coalesce if we cannot assign a symbol to the partition.  */
 240   if (!(!ign2 && root2)
 241       && !(!ign1 && root1))
 242     {
 243       if (debug)
 244         fprintf (debug, " : Choosen variable has no root.  No coalesce.\n");
 245       return;
 246     }
 247
 248   /* Don't coalesce if the new chosen root variable would be read-only.
 249      If both ign1 && ign2, then the root var of the larger partition
 250      wins, so reject in that case if any of the root vars is TREE_READONLY.
 251      Otherwise reject only if the root var, on which replace_ssa_name_symbol
 252      will be called below, is readonly.  */
 253   if (((root1 && TREE_READONLY (root1)) && ign2)
 254       || ((root2 && TREE_READONLY (root2)) && ign1))
 255     {
 256       if (debug)
 257         fprintf (debug, " : Readonly variable.  No coalesce.\n");
 258       return;
 259     }
 260
 261   /* Don't coalesce if the two variables aren't type compatible .  */
 262   if (!types_compatible_p (TREE_TYPE (var1), TREE_TYPE (var2))
 263       /* There is a disconnect between the middle-end type-system and
 264          VRP, avoid coalescing enum types with different bounds.  */
 265       || ((TREE_CODE (TREE_TYPE (var1)) == ENUMERAL_TYPE
 266            || TREE_CODE (TREE_TYPE (var2)) == ENUMERAL_TYPE)
 267           && TREE_TYPE (var1) != TREE_TYPE (var2)))
 268     {
 269       if (debug)
 270         fprintf (debug, " : Incompatible types.  No coalesce.\n");
 271       return;
 272     }
 273
 274   /* Merge the two partitions.  */
 275   p3 = partition_union (map->var_partition, p1, p2);
 276
 277   /* Set the root variable of the partition to the better choice, if there is
 278      one.  */
 279   if (!ign2 && root2)
 280     replace_ssa_name_symbol (partition_to_var (map, p3), root2);
 281   else if (!ign1 && root1)
 282     replace_ssa_name_symbol (partition_to_var (map, p3), root1);
 283   else
 284     gcc_unreachable ();
 285
 286   if (debug)
 287     {
 288       fprintf (debug, " --> P%d ", p3);
 289       print_generic_expr (debug, SSA_NAME_VAR (partition_to_var (map, p3)),
 290                           TDF_SLIM);
 291       fprintf (debug, "\n");
 292     }
 293 }
 294
 295
 296 /* This function will make a pass through the IL, and attempt to coalesce any
 297    SSA versions which occur in PHI's or copies.  Coalescing is accomplished by
 298    changing the underlying root variable of all coalesced version.  This will
 299    then cause the SSA->normal pass to attempt to coalesce them all to the same
 300    variable.  */
 301
 302 static unsigned int
 303 rename_ssa_copies (void)
 304 {
 305   var_map map;
 306   basic_block bb;
 307   gimple_stmt_iterator gsi;
 308   tree var, part_var;
 309   gimple stmt, phi;
 310   unsigned x;
 311   FILE *debug;
 312
 313   memset (&stats, 0, sizeof (stats));
 314
 315   if (dump_file && (dump_flags & TDF_DETAILS))
 316     debug = dump_file;
 317   else
 318     debug = NULL;
 319
 320   map = init_var_map (num_ssa_names);
 321
 322   FOR_EACH_BB (bb)
 323     {
 324       /* Scan for real copies.  */
 325       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 326         {
 327           stmt = gsi_stmt (gsi);
 328           if (gimple_assign_ssa_name_copy_p (stmt))
 329             {
 330               tree lhs = gimple_assign_lhs (stmt);
 331               tree rhs = gimple_assign_rhs1 (stmt);
 332
 333               copy_rename_partition_coalesce (map, lhs, rhs, debug);
 334             }
 335         }
 336     }
 337
 338   FOR_EACH_BB (bb)
 339     {
 340       /* Treat PHI nodes as copies between the result and each argument.  */
 341       for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 342         {
 343           size_t i;
 344           tree res;
 345
 346           phi = gsi_stmt (gsi);
 347           res = gimple_phi_result (phi);
 348
 349           /* Do not process virtual SSA_NAMES.  */
 350           if (virtual_operand_p (res))
 351             continue;
 352
 353           /* Make sure to only use the same partition for an argument
 354              as the result but never the other way around.  */
 355           if (SSA_NAME_VAR (res)
 356               && !DECL_IGNORED_P (SSA_NAME_VAR (res)))
 357             for (i = 0; i < gimple_phi_num_args (phi); i++)
 358               {
 359                 tree arg = PHI_ARG_DEF (phi, i);
 360                 if (TREE_CODE (arg) == SSA_NAME)
 361                   copy_rename_partition_coalesce (map, res, arg,
 362                                                   debug);
 363               }
 364           /* Else if all arguments are in the same partition try to merge
 365              it with the result.  */
 366           else
 367             {
 368               int all_p_same = -1;
 369               int p = -1;
 370               for (i = 0; i < gimple_phi_num_args (phi); i++)
 371                 {
 372                   tree arg = PHI_ARG_DEF (phi, i);
 373                   if (TREE_CODE (arg) != SSA_NAME)
 374                     {
 375                       all_p_same = 0;
 376                       break;
 377                     }
 378                   else if (all_p_same == -1)
 379                     {
 380                       p = partition_find (map->var_partition,
 381                                           SSA_NAME_VERSION (arg));
 382                       all_p_same = 1;
 383                     }
 384                   else if (all_p_same == 1
 385                            && p != partition_find (map->var_partition,
 386                                                    SSA_NAME_VERSION (arg)))
 387                     {
 388                       all_p_same = 0;
 389                       break;
 390                     }
 391                 }
 392               if (all_p_same == 1)
 393                 copy_rename_partition_coalesce (map, res,
 394                                                 PHI_ARG_DEF (phi, 0),
 395                                                 debug);
 396             }
 397         }
 398     }
 399
 400   if (debug)
 401     dump_var_map (debug, map);
 402
 403   /* Now one more pass to make all elements of a partition share the same
 404      root variable.  */
 405
 406   for (x = 1; x < num_ssa_names; x++)
 407     {
 408       part_var = partition_to_var (map, x);
 409       if (!part_var)
 410         continue;
 411       var = ssa_name (x);
 412       if (SSA_NAME_VAR (var) == SSA_NAME_VAR (part_var))
 413         continue;
 414       if (debug)
 415         {
 416           fprintf (debug, "Coalesced ");
 417           print_generic_expr (debug, var, TDF_SLIM);
 418           fprintf (debug, " to ");
 419           print_generic_expr (debug, part_var, TDF_SLIM);
 420           fprintf (debug, "\n");
 421         }
 422       stats.coalesced++;
 423       replace_ssa_name_symbol (var, SSA_NAME_VAR (part_var));
 424     }
 425
 426   statistics_counter_event (cfun, "copies coalesced",
 427                             stats.coalesced);
 428   delete_var_map (map);
 429   return 0;
 430 }
 431
 432 /* Return true if copy rename is to be performed.  */
 433
 434 static bool
 435 gate_copyrename (void)
 436 {
 437   return flag_tree_copyrename != 0;
 438 }
 439
 440 namespace {
 441
 442 const pass_data pass_data_rename_ssa_copies =
 443 {
 444   GIMPLE_PASS, /* type */
 445   "copyrename", /* name */
 446   OPTGROUP_NONE, /* optinfo_flags */
 447   true, /* has_gate */
 448   true, /* has_execute */
 449   TV_TREE_COPY_RENAME, /* tv_id */
 450   ( PROP_cfg | PROP_ssa ), /* properties_required */
 451   0, /* properties_provided */
 452   0, /* properties_destroyed */
 453   0, /* todo_flags_start */
 454   TODO_verify_ssa, /* todo_flags_finish */
 455 };
 456
 457 class pass_rename_ssa_copies : public gimple_opt_pass
 458 {
 459 public:
 460   pass_rename_ssa_copies (gcc::context *ctxt)
 461     : gimple_opt_pass (pass_data_rename_ssa_copies, ctxt)
 462   {}
 463
 464   /* opt_pass methods: */
 465   opt_pass * clone () { return new pass_rename_ssa_copies (m_ctxt); }
 466   bool gate () { return gate_copyrename (); }
 467   unsigned int execute () { return rename_ssa_copies (); }
 468
 469 }; // class pass_rename_ssa_copies
 470
 471 } // anon namespace
 472
 473 gimple_opt_pass *
 474 make_pass_rename_ssa_copies (gcc::context *ctxt)
 475 {
 476   return new pass_rename_ssa_copies (ctxt);
 477 }