gcc/tree-ssa-copyrename.c

   1 /* Rename SSA copies.
   2    Copyright (C) 2004-2014 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 namespace {
 303
 304 const pass_data pass_data_rename_ssa_copies =
 305 {
 306   GIMPLE_PASS, /* type */
 307   "copyrename", /* name */
 308   OPTGROUP_NONE, /* optinfo_flags */
 309   TV_TREE_COPY_RENAME, /* tv_id */
 310   ( PROP_cfg | PROP_ssa ), /* properties_required */
 311   0, /* properties_provided */
 312   0, /* properties_destroyed */
 313   0, /* todo_flags_start */
 314   0, /* todo_flags_finish */
 315 };
 316
 317 class pass_rename_ssa_copies : public gimple_opt_pass
 318 {
 319 public:
 320   pass_rename_ssa_copies (gcc::context *ctxt)
 321     : gimple_opt_pass (pass_data_rename_ssa_copies, ctxt)
 322   {}
 323
 324   /* opt_pass methods: */
 325   opt_pass * clone () { return new pass_rename_ssa_copies (m_ctxt); }
 326   virtual bool gate (function *) { return flag_tree_copyrename != 0; }
 327   virtual unsigned int execute (function *);
 328
 329 }; // class pass_rename_ssa_copies
 330
 331 /* This function will make a pass through the IL, and attempt to coalesce any
 332    SSA versions which occur in PHI's or copies.  Coalescing is accomplished by
 333    changing the underlying root variable of all coalesced version.  This will
 334    then cause the SSA->normal pass to attempt to coalesce them all to the same
 335    variable.  */
 336
 337 unsigned int
 338 pass_rename_ssa_copies::execute (function *fun)
 339 {
 340   var_map map;
 341   basic_block bb;
 342   gimple_stmt_iterator gsi;
 343   tree var, part_var;
 344   gimple stmt, phi;
 345   unsigned x;
 346   FILE *debug;
 347
 348   memset (&stats, 0, sizeof (stats));
 349
 350   if (dump_file && (dump_flags & TDF_DETAILS))
 351     debug = dump_file;
 352   else
 353     debug = NULL;
 354
 355   map = init_var_map (num_ssa_names);
 356
 357   FOR_EACH_BB_FN (bb, fun)
 358     {
 359       /* Scan for real copies.  */
 360       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 361         {
 362           stmt = gsi_stmt (gsi);
 363           if (gimple_assign_ssa_name_copy_p (stmt))
 364             {
 365               tree lhs = gimple_assign_lhs (stmt);
 366               tree rhs = gimple_assign_rhs1 (stmt);
 367
 368               copy_rename_partition_coalesce (map, lhs, rhs, debug);
 369             }
 370         }
 371     }
 372
 373   FOR_EACH_BB_FN (bb, fun)
 374     {
 375       /* Treat PHI nodes as copies between the result and each argument.  */
 376       for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 377         {
 378           size_t i;
 379           tree res;
 380
 381           phi = gsi_stmt (gsi);
 382           res = gimple_phi_result (phi);
 383
 384           /* Do not process virtual SSA_NAMES.  */
 385           if (virtual_operand_p (res))
 386             continue;
 387
 388           /* Make sure to only use the same partition for an argument
 389              as the result but never the other way around.  */
 390           if (SSA_NAME_VAR (res)
 391               && !DECL_IGNORED_P (SSA_NAME_VAR (res)))
 392             for (i = 0; i < gimple_phi_num_args (phi); i++)
 393               {
 394                 tree arg = PHI_ARG_DEF (phi, i);
 395                 if (TREE_CODE (arg) == SSA_NAME)
 396                   copy_rename_partition_coalesce (map, res, arg,
 397                                                   debug);
 398               }
 399           /* Else if all arguments are in the same partition try to merge
 400              it with the result.  */
 401           else
 402             {
 403               int all_p_same = -1;
 404               int p = -1;
 405               for (i = 0; i < gimple_phi_num_args (phi); i++)
 406                 {
 407                   tree arg = PHI_ARG_DEF (phi, i);
 408                   if (TREE_CODE (arg) != SSA_NAME)
 409                     {
 410                       all_p_same = 0;
 411                       break;
 412                     }
 413                   else if (all_p_same == -1)
 414                     {
 415                       p = partition_find (map->var_partition,
 416                                           SSA_NAME_VERSION (arg));
 417                       all_p_same = 1;
 418                     }
 419                   else if (all_p_same == 1
 420                            && p != partition_find (map->var_partition,
 421                                                    SSA_NAME_VERSION (arg)))
 422                     {
 423                       all_p_same = 0;
 424                       break;
 425                     }
 426                 }
 427               if (all_p_same == 1)
 428                 copy_rename_partition_coalesce (map, res,
 429                                                 PHI_ARG_DEF (phi, 0),
 430                                                 debug);
 431             }
 432         }
 433     }
 434
 435   if (debug)
 436     dump_var_map (debug, map);
 437
 438   /* Now one more pass to make all elements of a partition share the same
 439      root variable.  */
 440
 441   for (x = 1; x < num_ssa_names; x++)
 442     {
 443       part_var = partition_to_var (map, x);
 444       if (!part_var)
 445         continue;
 446       var = ssa_name (x);
 447       if (SSA_NAME_VAR (var) == SSA_NAME_VAR (part_var))
 448         continue;
 449       if (debug)
 450         {
 451           fprintf (debug, "Coalesced ");
 452           print_generic_expr (debug, var, TDF_SLIM);
 453           fprintf (debug, " to ");
 454           print_generic_expr (debug, part_var, TDF_SLIM);
 455           fprintf (debug, "\n");
 456         }
 457       stats.coalesced++;
 458       replace_ssa_name_symbol (var, SSA_NAME_VAR (part_var));
 459     }
 460
 461   statistics_counter_event (fun, "copies coalesced",
 462                             stats.coalesced);
 463   delete_var_map (map);
 464   return 0;
 465 }
 466
 467 } // anon namespace
 468
 469 gimple_opt_pass *
 470 make_pass_rename_ssa_copies (gcc::context *ctxt)
 471 {
 472   return new pass_rename_ssa_copies (ctxt);
 473 }