gcc/tree-ssa-copyrename.c

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