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