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