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