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