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