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