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