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