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