gcc/tree-ssanames.c

   1 /* Generic routines for manipulating SSA_NAME expressions
   2    Copyright (C) 2003-2013 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 3, or (at your option)
   9 any later version.
  10
  11 GCC is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 GNU General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING3.  If not see
  18 <http://www.gnu.org/licenses/>.  */
  19
  20 #include "config.h"
  21 #include "system.h"
  22 #include "coretypes.h"
  23 #include "tm.h"
  24 #include "tree.h"
  25 #include "gimple.h"
  26 #include "gimple-ssa.h"
  27 #include "tree-phinodes.h"
  28 #include "ssa-iterators.h"
  29 #include "tree-ssanames.h"
  30 #include "tree-into-ssa.h"
  31 #include "tree-ssa.h"
  32 #include "tree-pass.h"
  33
  34 /* Rewriting a function into SSA form can create a huge number of SSA_NAMEs,
  35    many of which may be thrown away shortly after their creation if jumps
  36    were threaded through PHI nodes.
  37
  38    While our garbage collection mechanisms will handle this situation, it
  39    is extremely wasteful to create nodes and throw them away, especially
  40    when the nodes can be reused.
  41
  42    For PR 8361, we can significantly reduce the number of nodes allocated
  43    and thus the total amount of memory allocated by managing SSA_NAMEs a
  44    little.  This additionally helps reduce the amount of work done by the
  45    garbage collector.  Similar results have been seen on a wider variety
  46    of tests (such as the compiler itself).
  47
  48    Right now we maintain our free list on a per-function basis.  It may
  49    or may not make sense to maintain the free list for the duration of
  50    a compilation unit.
  51
  52    External code should rely solely upon HIGHEST_SSA_VERSION and the
  53    externally defined functions.  External code should not know about
  54    the details of the free list management.
  55
  56    External code should also not assume the version number on nodes is
  57    monotonically increasing.  We reuse the version number when we
  58    reuse an SSA_NAME expression.  This helps keep arrays and bitmaps
  59    more compact.  */
  60
  61
  62 /* Version numbers with special meanings.  We start allocating new version
  63    numbers after the special ones.  */
  64 #define UNUSED_NAME_VERSION 0
  65
  66 unsigned int ssa_name_nodes_reused;
  67 unsigned int ssa_name_nodes_created;
  68
  69 #define FREE_SSANAMES(fun) (fun)->gimple_df->free_ssanames
  70
  71
  72 /* Initialize management of SSA_NAMEs to default SIZE.  If SIZE is
  73    zero use default.  */
  74
  75 void
  76 init_ssanames (struct function *fn, int size)
  77 {
  78   if (size < 50)
  79     size = 50;
  80
  81   vec_alloc (SSANAMES (fn), size);
  82
  83   /* Version 0 is special, so reserve the first slot in the table.  Though
  84      currently unused, we may use version 0 in alias analysis as part of
  85      the heuristics used to group aliases when the alias sets are too
  86      large.
  87
  88      We use vec::quick_push here because we know that SSA_NAMES has at
  89      least 50 elements reserved in it.  */
  90   SSANAMES (fn)->quick_push (NULL_TREE);
  91   FREE_SSANAMES (fn) = NULL;
  92
  93   fn->gimple_df->ssa_renaming_needed = 0;
  94   fn->gimple_df->rename_vops = 0;
  95 }
  96
  97 /* Finalize management of SSA_NAMEs.  */
  98
  99 void
 100 fini_ssanames (void)
 101 {
 102   vec_free (SSANAMES (cfun));
 103   vec_free (FREE_SSANAMES (cfun));
 104 }
 105
 106 /* Dump some simple statistics regarding the re-use of SSA_NAME nodes.  */
 107
 108 void
 109 ssanames_print_statistics (void)
 110 {
 111   fprintf (stderr, "SSA_NAME nodes allocated: %u\n", ssa_name_nodes_created);
 112   fprintf (stderr, "SSA_NAME nodes reused: %u\n", ssa_name_nodes_reused);
 113 }
 114
 115 /* Return an SSA_NAME node for variable VAR defined in statement STMT
 116    in function FN.  STMT may be an empty statement for artificial
 117    references (e.g., default definitions created when a variable is
 118    used without a preceding definition).  */
 119
 120 tree
 121 make_ssa_name_fn (struct function *fn, tree var, gimple stmt)
 122 {
 123   tree t;
 124   use_operand_p imm;
 125
 126   gcc_assert (TREE_CODE (var) == VAR_DECL
 127               || TREE_CODE (var) == PARM_DECL
 128               || TREE_CODE (var) == RESULT_DECL
 129               || (TYPE_P (var) && is_gimple_reg_type (var)));
 130
 131   /* If our free list has an element, then use it.  */
 132   if (!vec_safe_is_empty (FREE_SSANAMES (fn)))
 133     {
 134       t = FREE_SSANAMES (fn)->pop ();
 135       if (GATHER_STATISTICS)
 136         ssa_name_nodes_reused++;
 137
 138       /* The node was cleared out when we put it on the free list, so
 139          there is no need to do so again here.  */
 140       gcc_assert (ssa_name (SSA_NAME_VERSION (t)) == NULL);
 141       (*SSANAMES (fn))[SSA_NAME_VERSION (t)] = t;
 142     }
 143   else
 144     {
 145       t = make_node (SSA_NAME);
 146       SSA_NAME_VERSION (t) = SSANAMES (fn)->length ();
 147       vec_safe_push (SSANAMES (fn), t);
 148       if (GATHER_STATISTICS)
 149         ssa_name_nodes_created++;
 150     }
 151
 152   if (TYPE_P (var))
 153     {
 154       TREE_TYPE (t) = var;
 155       SET_SSA_NAME_VAR_OR_IDENTIFIER (t, NULL_TREE);
 156     }
 157   else
 158     {
 159       TREE_TYPE (t) = TREE_TYPE (var);
 160       SET_SSA_NAME_VAR_OR_IDENTIFIER (t, var);
 161     }
 162   SSA_NAME_DEF_STMT (t) = stmt;
 163   if (POINTER_TYPE_P (TREE_TYPE (t)))
 164     SSA_NAME_PTR_INFO (t) = NULL;
 165   else
 166     SSA_NAME_RANGE_INFO (t) = NULL;
 167
 168   SSA_NAME_IN_FREE_LIST (t) = 0;
 169   SSA_NAME_IS_DEFAULT_DEF (t) = 0;
 170   imm = &(SSA_NAME_IMM_USE_NODE (t));
 171   imm->use = NULL;
 172   imm->prev = imm;
 173   imm->next = imm;
 174   imm->loc.ssa_name = t;
 175
 176   return t;
 177 }
 178
 179 /* Store range information MIN, and MAX to tree ssa_name NAME.  */
 180
 181 void
 182 set_range_info (tree name, double_int min, double_int max)
 183 {
 184   gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
 185   range_info_def *ri = SSA_NAME_RANGE_INFO (name);
 186
 187   /* Allocate if not available.  */
 188   if (ri == NULL)
 189     {
 190       ri = ggc_alloc_cleared_range_info_def ();
 191       SSA_NAME_RANGE_INFO (name) = ri;
 192       ri->nonzero_bits = double_int::mask (TYPE_PRECISION (TREE_TYPE (name)));
 193     }
 194
 195   /* Set the values.  */
 196   ri->min = min;
 197   ri->max = max;
 198
 199   /* If it is a range, try to improve nonzero_bits from the min/max.  */
 200   if (min.cmp (max, TYPE_UNSIGNED (TREE_TYPE (name))) != 1)
 201     {
 202       int prec = TYPE_PRECISION (TREE_TYPE (name));
 203       double_int xorv;
 204
 205       min = min.zext (prec);
 206       max = max.zext (prec);
 207       xorv = min ^ max;
 208       if (xorv.high)
 209         xorv = double_int::mask (2 * HOST_BITS_PER_WIDE_INT
 210                                  - clz_hwi (xorv.high));
 211       else if (xorv.low)
 212         xorv = double_int::mask (HOST_BITS_PER_WIDE_INT
 213                                  - clz_hwi (xorv.low));
 214       ri->nonzero_bits = ri->nonzero_bits & (min | xorv);
 215     }
 216 }
 217
 218
 219 /* Gets range information MIN, MAX and returns enum value_range_type
 220    corresponding to tree ssa_name NAME.  enum value_range_type returned
 221    is used to determine if MIN and MAX are valid values.  */
 222
 223 enum value_range_type
 224 get_range_info (const_tree name, double_int *min, double_int *max)
 225 {
 226   enum value_range_type range_type;
 227   gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
 228   gcc_assert (min && max);
 229   range_info_def *ri = SSA_NAME_RANGE_INFO (name);
 230
 231   /* Return VR_VARYING for SSA_NAMEs with NULL RANGE_INFO or SSA_NAMEs
 232      with integral types width > 2 * HOST_BITS_PER_WIDE_INT precision.  */
 233   if (!ri || (GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (name)))
 234               > 2 * HOST_BITS_PER_WIDE_INT))
 235     return VR_VARYING;
 236
 237   /* If min > max, it is VR_ANTI_RANGE.  */
 238   if (ri->min.cmp (ri->max, TYPE_UNSIGNED (TREE_TYPE (name))) == 1)
 239     {
 240       /* VR_ANTI_RANGE ~[min, max] is encoded as [max + 1, min - 1].  */
 241       range_type = VR_ANTI_RANGE;
 242       *min = ri->max + double_int_one;
 243       *max = ri->min - double_int_one;
 244     }
 245   else
 246   {
 247     /* Otherwise (when min <= max), it is VR_RANGE.  */
 248     range_type = VR_RANGE;
 249     *min = ri->min;
 250     *max = ri->max;
 251   }
 252   return range_type;
 253 }
 254
 255 /* Change non-zero bits bitmask of NAME.  */
 256
 257 void
 258 set_nonzero_bits (tree name, double_int mask)
 259 {
 260   gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
 261   if (SSA_NAME_RANGE_INFO (name) == NULL)
 262     set_range_info (name,
 263                     tree_to_double_int (TYPE_MIN_VALUE (TREE_TYPE (name))),
 264                     tree_to_double_int (TYPE_MAX_VALUE (TREE_TYPE (name))));
 265   range_info_def *ri = SSA_NAME_RANGE_INFO (name);
 266   ri->nonzero_bits
 267     = mask & double_int::mask (TYPE_PRECISION (TREE_TYPE (name)));
 268 }
 269
 270 /* Return a double_int with potentially non-zero bits in SSA_NAME
 271    NAME, or double_int_minus_one if unknown.  */
 272
 273 double_int
 274 get_nonzero_bits (const_tree name)
 275 {
 276   if (POINTER_TYPE_P (TREE_TYPE (name)))
 277     {
 278       struct ptr_info_def *pi = SSA_NAME_PTR_INFO (name);
 279       if (pi && pi->align)
 280         {
 281           double_int al = double_int::from_uhwi (pi->align - 1);
 282           return ((double_int::mask (TYPE_PRECISION (TREE_TYPE (name))) & ~al)
 283                   | double_int::from_uhwi (pi->misalign));
 284         }
 285       return double_int_minus_one;
 286     }
 287
 288   range_info_def *ri = SSA_NAME_RANGE_INFO (name);
 289   if (!ri || (GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (name)))
 290               > 2 * HOST_BITS_PER_WIDE_INT))
 291     return double_int_minus_one;
 292
 293   return ri->nonzero_bits;
 294 }
 295
 296 /* We no longer need the SSA_NAME expression VAR, release it so that
 297    it may be reused.
 298
 299    Note it is assumed that no calls to make_ssa_name will be made
 300    until all uses of the ssa name are released and that the only
 301    use of the SSA_NAME expression is to check its SSA_NAME_VAR.  All
 302    other fields must be assumed clobbered.  */
 303
 304 void
 305 release_ssa_name (tree var)
 306 {
 307   if (!var)
 308     return;
 309
 310   /* Never release the default definition for a symbol.  It's a
 311      special SSA name that should always exist once it's created.  */
 312   if (SSA_NAME_IS_DEFAULT_DEF (var))
 313     return;
 314
 315   /* If VAR has been registered for SSA updating, don't remove it.
 316      After update_ssa has run, the name will be released.  */
 317   if (name_registered_for_update_p (var))
 318     {
 319       release_ssa_name_after_update_ssa (var);
 320       return;
 321     }
 322
 323   /* release_ssa_name can be called multiple times on a single SSA_NAME.
 324      However, it should only end up on our free list one time.   We
 325      keep a status bit in the SSA_NAME node itself to indicate it has
 326      been put on the free list.
 327
 328      Note that once on the freelist you can not reference the SSA_NAME's
 329      defining statement.  */
 330   if (! SSA_NAME_IN_FREE_LIST (var))
 331     {
 332       tree saved_ssa_name_var = SSA_NAME_VAR (var);
 333       int saved_ssa_name_version = SSA_NAME_VERSION (var);
 334       use_operand_p imm = &(SSA_NAME_IMM_USE_NODE (var));
 335
 336       if (MAY_HAVE_DEBUG_STMTS)
 337         insert_debug_temp_for_var_def (NULL, var);
 338
 339 #ifdef ENABLE_CHECKING
 340       verify_imm_links (stderr, var);
 341 #endif
 342       while (imm->next != imm)
 343         delink_imm_use (imm->next);
 344
 345       (*SSANAMES (cfun))[SSA_NAME_VERSION (var)] = NULL_TREE;
 346       memset (var, 0, tree_size (var));
 347
 348       imm->prev = imm;
 349       imm->next = imm;
 350       imm->loc.ssa_name = var;
 351
 352       /* First put back the right tree node so that the tree checking
 353          macros do not complain.  */
 354       TREE_SET_CODE (var, SSA_NAME);
 355
 356       /* Restore the version number.  */
 357       SSA_NAME_VERSION (var) = saved_ssa_name_version;
 358
 359       /* Hopefully this can go away once we have the new incremental
 360          SSA updating code installed.  */
 361       SET_SSA_NAME_VAR_OR_IDENTIFIER (var, saved_ssa_name_var);
 362
 363       /* Note this SSA_NAME is now in the first list.  */
 364       SSA_NAME_IN_FREE_LIST (var) = 1;
 365
 366       /* And finally put it on the free list.  */
 367       vec_safe_push (FREE_SSANAMES (cfun), var);
 368     }
 369 }
 370
 371 /* If the alignment of the pointer described by PI is known, return true and
 372    store the alignment and the deviation from it into *ALIGNP and *MISALIGNP
 373    respectively.  Otherwise return false.  */
 374
 375 bool
 376 get_ptr_info_alignment (struct ptr_info_def *pi, unsigned int *alignp,
 377                         unsigned int *misalignp)
 378 {
 379   if (pi->align)
 380     {
 381       *alignp = pi->align;
 382       *misalignp = pi->misalign;
 383       return true;
 384     }
 385   else
 386     return false;
 387 }
 388
 389 /* State that the pointer described by PI has unknown alignment.  */
 390
 391 void
 392 mark_ptr_info_alignment_unknown (struct ptr_info_def *pi)
 393 {
 394   pi->align = 0;
 395   pi->misalign = 0;
 396 }
 397
 398 /* Store the the power-of-two byte alignment and the deviation from that
 399    alignment of pointer described by PI to ALIOGN and MISALIGN
 400    respectively.  */
 401
 402 void
 403 set_ptr_info_alignment (struct ptr_info_def *pi, unsigned int align,
 404                             unsigned int misalign)
 405 {
 406   gcc_checking_assert (align != 0);
 407   gcc_assert ((align & (align - 1)) == 0);
 408   gcc_assert ((misalign & ~(align - 1)) == 0);
 409
 410   pi->align = align;
 411   pi->misalign = misalign;
 412 }
 413
 414 /* If pointer described by PI has known alignment, increase its known
 415    misalignment by INCREMENT modulo its current alignment.  */
 416
 417 void
 418 adjust_ptr_info_misalignment (struct ptr_info_def *pi,
 419                               unsigned int increment)
 420 {
 421   if (pi->align != 0)
 422     {
 423       pi->misalign += increment;
 424       pi->misalign &= (pi->align - 1);
 425     }
 426 }
 427
 428 /* Return the alias information associated with pointer T.  It creates a
 429    new instance if none existed.  */
 430
 431 struct ptr_info_def *
 432 get_ptr_info (tree t)
 433 {
 434   struct ptr_info_def *pi;
 435
 436   gcc_assert (POINTER_TYPE_P (TREE_TYPE (t)));
 437
 438   pi = SSA_NAME_PTR_INFO (t);
 439   if (pi == NULL)
 440     {
 441       pi = ggc_alloc_cleared_ptr_info_def ();
 442       pt_solution_reset (&pi->pt);
 443       mark_ptr_info_alignment_unknown (pi);
 444       SSA_NAME_PTR_INFO (t) = pi;
 445     }
 446
 447   return pi;
 448 }
 449
 450
 451 /* Creates a new SSA name using the template NAME tobe defined by
 452    statement STMT in function FN.  */
 453
 454 tree
 455 copy_ssa_name_fn (struct function *fn, tree name, gimple stmt)
 456 {
 457   tree new_name;
 458
 459   if (SSA_NAME_VAR (name))
 460     new_name = make_ssa_name_fn (fn, SSA_NAME_VAR (name), stmt);
 461   else
 462     {
 463       new_name = make_ssa_name_fn (fn, TREE_TYPE (name), stmt);
 464       SET_SSA_NAME_VAR_OR_IDENTIFIER (new_name, SSA_NAME_IDENTIFIER (name));
 465     }
 466
 467   return new_name;
 468 }
 469
 470
 471 /* Creates a duplicate of the ptr_info_def at PTR_INFO for use by
 472    the SSA name NAME.  */
 473
 474 void
 475 duplicate_ssa_name_ptr_info (tree name, struct ptr_info_def *ptr_info)
 476 {
 477   struct ptr_info_def *new_ptr_info;
 478
 479   gcc_assert (POINTER_TYPE_P (TREE_TYPE (name)));
 480   gcc_assert (!SSA_NAME_PTR_INFO (name));
 481
 482   if (!ptr_info)
 483     return;
 484
 485   new_ptr_info = ggc_alloc_ptr_info_def ();
 486   *new_ptr_info = *ptr_info;
 487
 488   SSA_NAME_PTR_INFO (name) = new_ptr_info;
 489 }
 490
 491 /* Creates a duplicate of the range_info_def at RANGE_INFO for use by
 492    the SSA name NAME.  */
 493 void
 494 duplicate_ssa_name_range_info (tree name, struct range_info_def *range_info)
 495 {
 496   struct range_info_def *new_range_info;
 497
 498   gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
 499   gcc_assert (!SSA_NAME_RANGE_INFO (name));
 500
 501   if (!range_info)
 502     return;
 503
 504   new_range_info = ggc_alloc_range_info_def ();
 505   *new_range_info = *range_info;
 506
 507   SSA_NAME_RANGE_INFO (name) = new_range_info;
 508 }
 509
 510
 511
 512 /* Creates a duplicate of a ssa name NAME tobe defined by statement STMT
 513    in function FN.  */
 514
 515 tree
 516 duplicate_ssa_name_fn (struct function *fn, tree name, gimple stmt)
 517 {
 518   tree new_name = copy_ssa_name_fn (fn, name, stmt);
 519   if (POINTER_TYPE_P (TREE_TYPE (name)))
 520     {
 521       struct ptr_info_def *old_ptr_info = SSA_NAME_PTR_INFO (name);
 522
 523       if (old_ptr_info)
 524         duplicate_ssa_name_ptr_info (new_name, old_ptr_info);
 525     }
 526   else
 527     {
 528       struct range_info_def *old_range_info = SSA_NAME_RANGE_INFO (name);
 529
 530       if (old_range_info)
 531         duplicate_ssa_name_range_info (new_name, old_range_info);
 532     }
 533
 534   return new_name;
 535 }
 536
 537
 538 /* Release all the SSA_NAMEs created by STMT.  */
 539
 540 void
 541 release_defs (gimple stmt)
 542 {
 543   tree def;
 544   ssa_op_iter iter;
 545
 546   /* Make sure that we are in SSA.  Otherwise, operand cache may point
 547      to garbage.  */
 548   gcc_assert (gimple_in_ssa_p (cfun));
 549
 550   FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
 551     if (TREE_CODE (def) == SSA_NAME)
 552       release_ssa_name (def);
 553 }
 554
 555
 556 /* Replace the symbol associated with SSA_NAME with SYM.  */
 557
 558 void
 559 replace_ssa_name_symbol (tree ssa_name, tree sym)
 560 {
 561   SET_SSA_NAME_VAR_OR_IDENTIFIER (ssa_name, sym);
 562   TREE_TYPE (ssa_name) = TREE_TYPE (sym);
 563 }
 564
 565 /* Return SSA names that are unused to GGC memory and compact the SSA
 566    version namespace.  This is used to keep footprint of compiler during
 567    interprocedural optimization.  */
 568 static unsigned int
 569 release_dead_ssa_names (void)
 570 {
 571   unsigned i, j;
 572   int n = vec_safe_length (FREE_SSANAMES (cfun));
 573
 574   /* Now release the freelist.  */
 575   vec_free (FREE_SSANAMES (cfun));
 576
 577   /* And compact the SSA number space.  We make sure to not change the
 578      relative order of SSA versions.  */
 579   for (i = 1, j = 1; i < cfun->gimple_df->ssa_names->length (); ++i)
 580     {
 581       tree name = ssa_name (i);
 582       if (name)
 583         {
 584           if (i != j)
 585             {
 586               SSA_NAME_VERSION (name) = j;
 587               (*cfun->gimple_df->ssa_names)[j] = name;
 588             }
 589           j++;
 590         }
 591     }
 592   cfun->gimple_df->ssa_names->truncate (j);
 593
 594   statistics_counter_event (cfun, "SSA names released", n);
 595   statistics_counter_event (cfun, "SSA name holes removed", i - j);
 596   if (dump_file)
 597     fprintf (dump_file, "Released %i names, %.2f%%, removed %i holes\n",
 598              n, n * 100.0 / num_ssa_names, i - j);
 599   return 0;
 600 }
 601
 602 namespace {
 603
 604 const pass_data pass_data_release_ssa_names =
 605 {
 606   GIMPLE_PASS, /* type */
 607   "release_ssa", /* name */
 608   OPTGROUP_NONE, /* optinfo_flags */
 609   false, /* has_gate */
 610   true, /* has_execute */
 611   TV_TREE_SSA_OTHER, /* tv_id */
 612   PROP_ssa, /* properties_required */
 613   0, /* properties_provided */
 614   0, /* properties_destroyed */
 615   TODO_remove_unused_locals, /* todo_flags_start */
 616   0, /* todo_flags_finish */
 617 };
 618
 619 class pass_release_ssa_names : public gimple_opt_pass
 620 {
 621 public:
 622   pass_release_ssa_names (gcc::context *ctxt)
 623     : gimple_opt_pass (pass_data_release_ssa_names, ctxt)
 624   {}
 625
 626   /* opt_pass methods: */
 627   unsigned int execute () { return release_dead_ssa_names (); }
 628
 629 }; // class pass_release_ssa_names
 630
 631 } // anon namespace
 632
 633 gimple_opt_pass *
 634 make_pass_release_ssa_names (gcc::context *ctxt)
 635 {
 636   return new pass_release_ssa_names (ctxt);
 637 }