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