gcc/tree-ssa-live.c

   1 /* Liveness for SSA trees.
   2    Copyright (C) 2003, 2004, 2005, 2007, 2008 Free Software Foundation,
   3    Inc.
   4    Contributed by Andrew MacLeod <amacleod@redhat.com>
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify
   9 it under the terms of the GNU General Public License as published by
  10 the Free Software Foundation; either version 3, or (at your option)
  11 any later version.
  12
  13 GCC is distributed in the hope that it will be useful,
  14 but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 GNU General Public License for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tm.h"
  26 #include "tree.h"
  27 #include "diagnostic.h"
  28 #include "bitmap.h"
  29 #include "tree-flow.h"
  30 #include "tree-dump.h"
  31 #include "tree-ssa-live.h"
  32 #include "toplev.h"
  33 #include "debug.h"
  34 #include "flags.h"
  35
  36 #ifdef ENABLE_CHECKING
  37 static void  verify_live_on_entry (tree_live_info_p);
  38 #endif
  39
  40
  41 /* VARMAP maintains a mapping from SSA version number to real variables.
  42
  43    All SSA_NAMES are divided into partitions.  Initially each ssa_name is the
  44    only member of it's own partition.  Coalescing will attempt to group any
  45    ssa_names which occur in a copy or in a PHI node into the same partition.
  46
  47    At the end of out-of-ssa, each partition becomes a "real" variable and is
  48    rewritten as a compiler variable.
  49
  50    The var_map data structure is used to manage these partitions.  It allows
  51    partitions to be combined, and determines which partition belongs to what
  52    ssa_name or variable, and vice versa.  */
  53
  54
  55 /* This routine will initialize the basevar fields of MAP.  */
  56
  57 static void
  58 var_map_base_init (var_map map)
  59 {
  60   int x, num_part, num;
  61   tree var;
  62   var_ann_t ann;
  63
  64   num = 0;
  65   num_part = num_var_partitions (map);
  66
  67   /* If a base table already exists, clear it, otherwise create it.  */
  68   if (map->partition_to_base_index != NULL)
  69     {
  70       free (map->partition_to_base_index);
  71       VEC_truncate (tree, map->basevars, 0);
  72     }
  73   else
  74     map->basevars = VEC_alloc (tree, heap, MAX (40, (num_part / 10)));
  75
  76   map->partition_to_base_index = (int *) xmalloc (sizeof (int) * num_part);
  77
  78   /* Build the base variable list, and point partitions at their bases.  */
  79   for (x = 0; x < num_part; x++)
  80     {
  81       var = partition_to_var (map, x);
  82       if (TREE_CODE (var) == SSA_NAME)
  83          var = SSA_NAME_VAR (var);
  84       ann = var_ann (var);
  85       /* If base variable hasn't been seen, set it up.  */
  86       if (!ann->base_var_processed)
  87         {
  88           ann->base_var_processed = 1;
  89           VAR_ANN_BASE_INDEX (ann) = num++;
  90           VEC_safe_push (tree, heap, map->basevars, var);
  91         }
  92       map->partition_to_base_index[x] = VAR_ANN_BASE_INDEX (ann);
  93     }
  94
  95   map->num_basevars = num;
  96
  97   /* Now clear the processed bit.  */
  98   for (x = 0; x < num; x++)
  99     {
 100        var = VEC_index (tree, map->basevars, x);
 101        var_ann (var)->base_var_processed = 0;
 102     }
 103
 104 #ifdef ENABLE_CHECKING
 105   for (x = 0; x < num_part; x++)
 106     {
 107       tree var2;
 108       var = SSA_NAME_VAR (partition_to_var (map, x));
 109       var2 = VEC_index (tree, map->basevars, basevar_index (map, x));
 110       gcc_assert (var == var2);
 111     }
 112 #endif
 113 }
 114
 115
 116 /* Remove the base table in MAP.  */
 117
 118 static void
 119 var_map_base_fini (var_map map)
 120 {
 121   /* Free the basevar info if it is present.  */
 122   if (map->partition_to_base_index != NULL)
 123     {
 124       VEC_free (tree, heap, map->basevars);
 125       free (map->partition_to_base_index);
 126       map->partition_to_base_index = NULL;
 127       map->num_basevars = 0;
 128     }
 129 }
 130 /* Create a variable partition map of SIZE, initialize and return it.  */
 131
 132 var_map
 133 init_var_map (int size)
 134 {
 135   var_map map;
 136
 137   map = (var_map) xmalloc (sizeof (struct _var_map));
 138   map->var_partition = partition_new (size);
 139   map->partition_to_var
 140               = (tree *)xmalloc (size * sizeof (tree));
 141   memset (map->partition_to_var, 0, size * sizeof (tree));
 142
 143   map->partition_to_view = NULL;
 144   map->view_to_partition = NULL;
 145   map->num_partitions = size;
 146   map->partition_size = size;
 147   map->num_basevars = 0;
 148   map->partition_to_base_index = NULL;
 149   map->basevars = NULL;
 150   return map;
 151 }
 152
 153
 154 /* Free memory associated with MAP.  */
 155
 156 void
 157 delete_var_map (var_map map)
 158 {
 159   var_map_base_fini (map);
 160   free (map->partition_to_var);
 161   partition_delete (map->var_partition);
 162   if (map->partition_to_view)
 163     free (map->partition_to_view);
 164   if (map->view_to_partition)
 165     free (map->view_to_partition);
 166   free (map);
 167 }
 168
 169
 170 /* This function will combine the partitions in MAP for VAR1 and VAR2.  It
 171    Returns the partition which represents the new partition.  If the two
 172    partitions cannot be combined, NO_PARTITION is returned.  */
 173
 174 int
 175 var_union (var_map map, tree var1, tree var2)
 176 {
 177   int p1, p2, p3;
 178   tree root_var = NULL_TREE;
 179   tree other_var = NULL_TREE;
 180
 181   /* This is independent of partition_to_view. If partition_to_view is
 182      on, then whichever one of these partitions is absorbed will never have a
 183      dereference into the partition_to_view array any more.  */
 184
 185   if (TREE_CODE (var1) == SSA_NAME)
 186     p1 = partition_find (map->var_partition, SSA_NAME_VERSION (var1));
 187   else
 188     {
 189       p1 = var_to_partition (map, var1);
 190       if (map->view_to_partition)
 191         p1 = map->view_to_partition[p1];
 192       root_var = var1;
 193     }
 194
 195   if (TREE_CODE (var2) == SSA_NAME)
 196     p2 = partition_find (map->var_partition, SSA_NAME_VERSION (var2));
 197   else
 198     {
 199       p2 = var_to_partition (map, var2);
 200       if (map->view_to_partition)
 201         p2 = map->view_to_partition[p2];
 202
 203       /* If there is no root_var set, or it's not a user variable, set the
 204          root_var to this one.  */
 205       if (!root_var || (DECL_P (root_var) && DECL_IGNORED_P (root_var)))
 206         {
 207           other_var = root_var;
 208           root_var = var2;
 209         }
 210       else
 211         other_var = var2;
 212     }
 213
 214   gcc_assert (p1 != NO_PARTITION);
 215   gcc_assert (p2 != NO_PARTITION);
 216
 217   if (p1 == p2)
 218     p3 = p1;
 219   else
 220     p3 = partition_union (map->var_partition, p1, p2);
 221
 222   if (map->partition_to_view)
 223     p3 = map->partition_to_view[p3];
 224
 225   if (root_var)
 226     change_partition_var (map, root_var, p3);
 227   if (other_var)
 228     change_partition_var (map, other_var, p3);
 229
 230   return p3;
 231 }
 232
 233
 234 /* Compress the partition numbers in MAP such that they fall in the range
 235    0..(num_partitions-1) instead of wherever they turned out during
 236    the partitioning exercise.  This removes any references to unused
 237    partitions, thereby allowing bitmaps and other vectors to be much
 238    denser.
 239
 240    This is implemented such that compaction doesn't affect partitioning.
 241    Ie., once partitions are created and possibly merged, running one
 242    or more different kind of compaction will not affect the partitions
 243    themselves.  Their index might change, but all the same variables will
 244    still be members of the same partition group.  This allows work on reduced
 245    sets, and no loss of information when a larger set is later desired.
 246
 247    In particular, coalescing can work on partitions which have 2 or more
 248    definitions, and then 'recompact' later to include all the single
 249    definitions for assignment to program variables.  */
 250
 251
 252 /* Set MAP back to the initial state of having no partition view.  Return a
 253    bitmap which has a bit set for each partition number which is in use in the
 254    varmap.  */
 255
 256 static bitmap
 257 partition_view_init (var_map map)
 258 {
 259   bitmap used;
 260   int tmp;
 261   unsigned int x;
 262
 263   used = BITMAP_ALLOC (NULL);
 264
 265   /* Already in a view? Abandon the old one.  */
 266   if (map->partition_to_view)
 267     {
 268       free (map->partition_to_view);
 269       map->partition_to_view = NULL;
 270     }
 271   if (map->view_to_partition)
 272     {
 273       free (map->view_to_partition);
 274       map->view_to_partition = NULL;
 275     }
 276
 277   /* Find out which partitions are actually referenced.  */
 278   for (x = 0; x < map->partition_size; x++)
 279     {
 280       tmp = partition_find (map->var_partition, x);
 281       if (map->partition_to_var[tmp] != NULL_TREE && !bitmap_bit_p (used, tmp))
 282         bitmap_set_bit (used, tmp);
 283     }
 284
 285   map->num_partitions = map->partition_size;
 286   return used;
 287 }
 288
 289
 290 /* This routine will finalize the view data for MAP based on the partitions
 291    set in SELECTED.  This is either the same bitmap returned from
 292    partition_view_init, or a trimmed down version if some of those partitions
 293    were not desired in this view.  SELECTED is freed before returning.  */
 294
 295 static void
 296 partition_view_fini (var_map map, bitmap selected)
 297 {
 298   bitmap_iterator bi;
 299   unsigned count, i, x, limit;
 300   tree var;
 301
 302   gcc_assert (selected);
 303
 304   count = bitmap_count_bits (selected);
 305   limit = map->partition_size;
 306
 307   /* If its a one-to-one ratio, we don't need any view compaction.  */
 308   if (count < limit)
 309     {
 310       map->partition_to_view = (int *)xmalloc (limit * sizeof (int));
 311       memset (map->partition_to_view, 0xff, (limit * sizeof (int)));
 312       map->view_to_partition = (int *)xmalloc (count * sizeof (int));
 313
 314       i = 0;
 315       /* Give each selected partition an index.  */
 316       EXECUTE_IF_SET_IN_BITMAP (selected, 0, x, bi)
 317         {
 318           map->partition_to_view[x] = i;
 319           map->view_to_partition[i] = x;
 320           var = map->partition_to_var[x];
 321           /* If any one of the members of a partition is not an SSA_NAME, make
 322              sure it is the representative.  */
 323           if (TREE_CODE (var) != SSA_NAME)
 324             change_partition_var (map, var, i);
 325           i++;
 326         }
 327       gcc_assert (i == count);
 328       map->num_partitions = i;
 329     }
 330
 331   BITMAP_FREE (selected);
 332 }
 333
 334
 335 /* Create a partition view which includes all the used partitions in MAP.  If
 336    WANT_BASES is true, create the base variable map as well.  */
 337
 338 extern void
 339 partition_view_normal (var_map map, bool want_bases)
 340 {
 341   bitmap used;
 342
 343   used = partition_view_init (map);
 344   partition_view_fini (map, used);
 345
 346   if (want_bases)
 347     var_map_base_init (map);
 348   else
 349     var_map_base_fini (map);
 350 }
 351
 352
 353 /* Create a partition view in MAP which includes just partitions which occur in
 354    the bitmap ONLY. If WANT_BASES is true, create the base variable map
 355    as well.  */
 356
 357 extern void
 358 partition_view_bitmap (var_map map, bitmap only, bool want_bases)
 359 {
 360   bitmap used;
 361   bitmap new_partitions = BITMAP_ALLOC (NULL);
 362   unsigned x, p;
 363   bitmap_iterator bi;
 364
 365   used = partition_view_init (map);
 366   EXECUTE_IF_SET_IN_BITMAP (only, 0, x, bi)
 367     {
 368       p = partition_find (map->var_partition, x);
 369       gcc_assert (bitmap_bit_p (used, p));
 370       bitmap_set_bit (new_partitions, p);
 371     }
 372   partition_view_fini (map, new_partitions);
 373
 374   BITMAP_FREE (used);
 375   if (want_bases)
 376     var_map_base_init (map);
 377   else
 378     var_map_base_fini (map);
 379 }
 380
 381
 382 /* This function is used to change the representative variable in MAP for VAR's
 383    partition to a regular non-ssa variable.  This allows partitions to be
 384    mapped back to real variables.  */
 385
 386 void
 387 change_partition_var (var_map map, tree var, int part)
 388 {
 389   var_ann_t ann;
 390
 391   gcc_assert (TREE_CODE (var) != SSA_NAME);
 392
 393   ann = var_ann (var);
 394   ann->out_of_ssa_tag = 1;
 395   VAR_ANN_PARTITION (ann) = part;
 396   if (map->view_to_partition)
 397     map->partition_to_var[map->view_to_partition[part]] = var;
 398 }
 399
 400
 401 static inline void mark_all_vars_used (tree *, void *data);
 402
 403 /* Helper function for mark_all_vars_used, called via walk_tree.  */
 404
 405 static tree
 406 mark_all_vars_used_1 (tree *tp, int *walk_subtrees, void *data)
 407 {
 408   tree t = *tp;
 409   enum tree_code_class c = TREE_CODE_CLASS (TREE_CODE (t));
 410   tree b;
 411
 412   if (TREE_CODE (t) == SSA_NAME)
 413     t = SSA_NAME_VAR (t);
 414
 415   if (IS_EXPR_CODE_CLASS (c)
 416       && (b = TREE_BLOCK (t)) != NULL)
 417     TREE_USED (b) = true;
 418
 419   /* Ignore TREE_ORIGINAL for TARGET_MEM_REFS, as well as other
 420      fields that do not contain vars.  */
 421   if (TREE_CODE (t) == TARGET_MEM_REF)
 422     {
 423       mark_all_vars_used (&TMR_SYMBOL (t), data);
 424       mark_all_vars_used (&TMR_BASE (t), data);
 425       mark_all_vars_used (&TMR_INDEX (t), data);
 426       *walk_subtrees = 0;
 427       return NULL;
 428     }
 429
 430   /* Only need to mark VAR_DECLS; parameters and return results are not
 431      eliminated as unused.  */
 432   if (TREE_CODE (t) == VAR_DECL)
 433     {
 434       if (data != NULL && bitmap_bit_p ((bitmap) data, DECL_UID (t)))
 435         {
 436           bitmap_clear_bit ((bitmap) data, DECL_UID (t));
 437           mark_all_vars_used (&DECL_INITIAL (t), data);
 438         }
 439       set_is_used (t);
 440     }
 441
 442   if (IS_TYPE_OR_DECL_P (t))
 443     *walk_subtrees = 0;
 444
 445   return NULL;
 446 }
 447
 448 /* Mark the scope block SCOPE and its subblocks unused when they can be
 449    possibly eliminated if dead.  */
 450
 451 static void
 452 mark_scope_block_unused (tree scope)
 453 {
 454   tree t;
 455   TREE_USED (scope) = false;
 456   if (!(*debug_hooks->ignore_block) (scope))
 457     TREE_USED (scope) = true;
 458   for (t = BLOCK_SUBBLOCKS (scope); t ; t = BLOCK_CHAIN (t))
 459     mark_scope_block_unused (t);
 460 }
 461
 462 /* Look if the block is dead (by possibly eliminating its dead subblocks)
 463    and return true if so.
 464    Block is declared dead if:
 465      1) No statements are associated with it.
 466      2) Declares no live variables
 467      3) All subblocks are dead
 468         or there is precisely one subblocks and the block
 469         has same abstract origin as outer block and declares
 470         no variables, so it is pure wrapper.
 471    When we are not outputting full debug info, we also eliminate dead variables
 472    out of scope blocks to let them to be recycled by GGC and to save copying work
 473    done by the inliner.  */
 474
 475 static bool
 476 remove_unused_scope_block_p (tree scope)
 477 {
 478   tree *t, *next;
 479   bool unused = !TREE_USED (scope);
 480   var_ann_t ann;
 481   int nsubblocks = 0;
 482
 483   for (t = &BLOCK_VARS (scope); *t; t = next)
 484     {
 485       next = &TREE_CHAIN (*t);
 486
 487       /* Debug info of nested function refers to the block of the
 488          function.  */
 489       if (TREE_CODE (*t) == FUNCTION_DECL)
 490         unused = false;
 491
 492       /* Remove everything we don't generate debug info for.  */
 493       else if (DECL_IGNORED_P (*t))
 494         {
 495           *t = TREE_CHAIN (*t);
 496           next = t;
 497         }
 498
 499       /* When we are outputting debug info, we usually want to output
 500          info about optimized-out variables in the scope blocks.
 501          Exception are the scope blocks not containing any instructions
 502          at all so user can't get into the scopes at first place.  */
 503       else if ((ann = var_ann (*t)) != NULL
 504                 && ann->used)
 505         unused = false;
 506
 507       /* When we are not doing full debug info, we however can keep around
 508          only the used variables for cfgexpand's memory packing saving quite
 509          a lot of memory.  */
 510       else if (debug_info_level == DINFO_LEVEL_NORMAL
 511                || debug_info_level == DINFO_LEVEL_VERBOSE
 512                /* Removing declarations before inlining is going to affect
 513                   DECL_UID that in turn is going to affect hashtables and
 514                   code generation.  */
 515                || !cfun->after_inlining)
 516         unused = false;
 517
 518       else
 519         {
 520           *t = TREE_CHAIN (*t);
 521           next = t;
 522         }
 523     }
 524
 525   for (t = &BLOCK_SUBBLOCKS (scope); *t ;)
 526     if (remove_unused_scope_block_p (*t))
 527       {
 528         if (BLOCK_SUBBLOCKS (*t))
 529           {
 530             tree next = BLOCK_CHAIN (*t);
 531             tree supercontext = BLOCK_SUPERCONTEXT (*t);
 532             *t = BLOCK_SUBBLOCKS (*t);
 533             gcc_assert (!BLOCK_CHAIN (*t));
 534             BLOCK_CHAIN (*t) = next;
 535             BLOCK_SUPERCONTEXT (*t) = supercontext;
 536             t = &BLOCK_CHAIN (*t);
 537             nsubblocks ++;
 538           }
 539         else
 540           {
 541             gcc_assert (!BLOCK_VARS (*t));
 542             *t = BLOCK_CHAIN (*t);
 543           }
 544       }
 545     else
 546       {
 547         t = &BLOCK_CHAIN (*t);
 548         nsubblocks ++;
 549       }
 550    /* Outer scope is always used.  */
 551    if (!BLOCK_SUPERCONTEXT (scope)
 552        || TREE_CODE (BLOCK_SUPERCONTEXT (scope)) == FUNCTION_DECL)
 553      unused = false;
 554    /* If there are more than one live subblocks, it is used.  */
 555    else if (nsubblocks > 1)
 556      unused = false;
 557    /* When there is only one subblock, see if it is just wrapper we can
 558       ignore.  Wrappers are not declaring any variables and not changing
 559       abstract origin.  */
 560    else if (nsubblocks == 1
 561             && (BLOCK_VARS (scope)
 562                 || ((debug_info_level == DINFO_LEVEL_NORMAL
 563                      || debug_info_level == DINFO_LEVEL_VERBOSE)
 564                     && ((BLOCK_ABSTRACT_ORIGIN (scope)
 565                         != BLOCK_ABSTRACT_ORIGIN (BLOCK_SUPERCONTEXT (scope)))))))
 566      unused = false;
 567    return unused;
 568 }
 569
 570 /* Mark all VAR_DECLS under *EXPR_P as used, so that they won't be
 571    eliminated during the tree->rtl conversion process.  */
 572
 573 static inline void
 574 mark_all_vars_used (tree *expr_p, void *data)
 575 {
 576   walk_tree (expr_p, mark_all_vars_used_1, data, NULL);
 577 }
 578
 579
 580 /* Remove local variables that are not referenced in the IL.  */
 581
 582 void
 583 remove_unused_locals (void)
 584 {
 585   basic_block bb;
 586   tree t, *cell;
 587   referenced_var_iterator rvi;
 588   var_ann_t ann;
 589   bitmap global_unused_vars = NULL;
 590
 591   if (optimize)
 592     mark_scope_block_unused (DECL_INITIAL (current_function_decl));
 593
 594   /* Assume all locals are unused.  */
 595   FOR_EACH_REFERENCED_VAR (t, rvi)
 596     var_ann (t)->used = false;
 597
 598   /* Walk the CFG marking all referenced symbols.  */
 599   FOR_EACH_BB (bb)
 600     {
 601       gimple_stmt_iterator gsi;
 602       size_t i;
 603
 604       /* Walk the statements.  */
 605       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 606         {
 607           gimple stmt = gsi_stmt (gsi);
 608           tree b = gimple_block (stmt);
 609
 610           if (b)
 611             TREE_USED (b) = true;
 612
 613           for (i = 0; i < gimple_num_ops (stmt); i++)
 614             mark_all_vars_used (gimple_op_ptr (gsi_stmt (gsi), i), NULL);
 615         }
 616
 617       for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 618         {
 619           use_operand_p arg_p;
 620           ssa_op_iter i;
 621           tree def;
 622           gimple phi = gsi_stmt (gsi);
 623
 624           /* No point processing globals.  */
 625           if (is_global_var (SSA_NAME_VAR (gimple_phi_result (phi))))
 626             continue;
 627
 628           def = gimple_phi_result (phi);
 629           mark_all_vars_used (&def, NULL);
 630
 631           FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_ALL_USES)
 632             {
 633               tree arg = USE_FROM_PTR (arg_p);
 634               mark_all_vars_used (&arg, NULL);
 635             }
 636         }
 637     }
 638
 639   /* Remove unmarked local vars from local_decls.  */
 640   for (cell = &cfun->local_decls; *cell; )
 641     {
 642       tree var = TREE_VALUE (*cell);
 643
 644       if (TREE_CODE (var) != FUNCTION_DECL
 645           && (!(ann = var_ann (var))
 646               || !ann->used))
 647         {
 648           if (is_global_var (var))
 649             {
 650               if (global_unused_vars == NULL)
 651                 global_unused_vars = BITMAP_ALLOC (NULL);
 652               bitmap_set_bit (global_unused_vars, DECL_UID (var));
 653             }
 654           else
 655             {
 656               *cell = TREE_CHAIN (*cell);
 657               continue;
 658             }
 659         }
 660       cell = &TREE_CHAIN (*cell);
 661     }
 662
 663   /* Remove unmarked global vars from local_decls.  */
 664   if (global_unused_vars != NULL)
 665     {
 666       for (t = cfun->local_decls; t; t = TREE_CHAIN (t))
 667         {
 668           tree var = TREE_VALUE (t);
 669
 670           if (TREE_CODE (var) == VAR_DECL
 671               && is_global_var (var)
 672               && (ann = var_ann (var)) != NULL
 673               && ann->used)
 674             mark_all_vars_used (&DECL_INITIAL (var), global_unused_vars);
 675         }
 676
 677       for (cell = &cfun->local_decls; *cell; )
 678         {
 679           tree var = TREE_VALUE (*cell);
 680
 681           if (TREE_CODE (var) == VAR_DECL
 682               && is_global_var (var)
 683               && bitmap_bit_p (global_unused_vars, DECL_UID (var))
 684               && (optimize || DECL_ARTIFICIAL (var)))
 685             *cell = TREE_CHAIN (*cell);
 686           else
 687             cell = &TREE_CHAIN (*cell);
 688         }
 689       BITMAP_FREE (global_unused_vars);
 690     }
 691
 692   /* Remove unused variables from REFERENCED_VARs.  As a special
 693      exception keep the variables that are believed to be aliased.
 694      Those can't be easily removed from the alias sets and operand
 695      caches.  They will be removed shortly after the next may_alias
 696      pass is performed.  */
 697   FOR_EACH_REFERENCED_VAR (t, rvi)
 698     if (!is_global_var (t)
 699         && !MTAG_P (t)
 700         && TREE_CODE (t) != PARM_DECL
 701         && TREE_CODE (t) != RESULT_DECL
 702         && !(ann = var_ann (t))->used
 703         && !ann->symbol_mem_tag
 704         && !TREE_ADDRESSABLE (t)
 705         && (optimize || DECL_ARTIFICIAL (t)))
 706       remove_referenced_var (t);
 707   if (optimize)
 708     remove_unused_scope_block_p (DECL_INITIAL (current_function_decl));
 709 }
 710
 711
 712 /* Allocate and return a new live range information object base on MAP.  */
 713
 714 static tree_live_info_p
 715 new_tree_live_info (var_map map)
 716 {
 717   tree_live_info_p live;
 718   unsigned x;
 719
 720   live = (tree_live_info_p) xmalloc (sizeof (struct tree_live_info_d));
 721   live->map = map;
 722   live->num_blocks = last_basic_block;
 723
 724   live->livein = (bitmap *)xmalloc (last_basic_block * sizeof (bitmap));
 725   for (x = 0; x < (unsigned)last_basic_block; x++)
 726     live->livein[x] = BITMAP_ALLOC (NULL);
 727
 728   live->liveout = (bitmap *)xmalloc (last_basic_block * sizeof (bitmap));
 729   for (x = 0; x < (unsigned)last_basic_block; x++)
 730     live->liveout[x] = BITMAP_ALLOC (NULL);
 731
 732   live->work_stack = XNEWVEC (int, last_basic_block);
 733   live->stack_top = live->work_stack;
 734
 735   live->global = BITMAP_ALLOC (NULL);
 736   return live;
 737 }
 738
 739
 740 /* Free storage for live range info object LIVE.  */
 741
 742 void
 743 delete_tree_live_info (tree_live_info_p live)
 744 {
 745   int x;
 746
 747   BITMAP_FREE (live->global);
 748   free (live->work_stack);
 749
 750   for (x = live->num_blocks - 1; x >= 0; x--)
 751     BITMAP_FREE (live->liveout[x]);
 752   free (live->liveout);
 753
 754   for (x = live->num_blocks - 1; x >= 0; x--)
 755     BITMAP_FREE (live->livein[x]);
 756   free (live->livein);
 757
 758   free (live);
 759 }
 760
 761
 762 /* Visit basic block BB and propagate any required live on entry bits from
 763    LIVE into the predecessors.  VISITED is the bitmap of visited blocks.
 764    TMP is a temporary work bitmap which is passed in to avoid reallocating
 765    it each time.  */
 766
 767 static void
 768 loe_visit_block (tree_live_info_p live, basic_block bb, sbitmap visited,
 769                  bitmap tmp)
 770 {
 771   edge e;
 772   bool change;
 773   edge_iterator ei;
 774   basic_block pred_bb;
 775   bitmap loe;
 776   gcc_assert (!TEST_BIT (visited, bb->index));
 777
 778   SET_BIT (visited, bb->index);
 779   loe = live_on_entry (live, bb);
 780
 781   FOR_EACH_EDGE (e, ei, bb->preds)
 782     {
 783       pred_bb = e->src;
 784       if (pred_bb == ENTRY_BLOCK_PTR)
 785         continue;
 786       /* TMP is variables live-on-entry from BB that aren't defined in the
 787          predecessor block.  This should be the live on entry vars to pred.
 788          Note that liveout is the DEFs in a block while live on entry is
 789          being calculated.  */
 790       bitmap_and_compl (tmp, loe, live->liveout[pred_bb->index]);
 791
 792       /* Add these bits to live-on-entry for the pred. if there are any
 793          changes, and pred_bb has been visited already, add it to the
 794          revisit stack.  */
 795       change = bitmap_ior_into (live_on_entry (live, pred_bb), tmp);
 796       if (TEST_BIT (visited, pred_bb->index) && change)
 797         {
 798           RESET_BIT (visited, pred_bb->index);
 799           *(live->stack_top)++ = pred_bb->index;
 800         }
 801     }
 802 }
 803
 804
 805 /* Using LIVE, fill in all the live-on-entry blocks between the defs and uses
 806    of all the variables.  */
 807
 808 static void
 809 live_worklist (tree_live_info_p live)
 810 {
 811   unsigned b;
 812   basic_block bb;
 813   sbitmap visited = sbitmap_alloc (last_basic_block + 1);
 814   bitmap tmp = BITMAP_ALLOC (NULL);
 815
 816   sbitmap_zero (visited);
 817
 818   /* Visit all the blocks in reverse order and propagate live on entry values
 819      into the predecessors blocks.  */
 820   FOR_EACH_BB_REVERSE (bb)
 821     loe_visit_block (live, bb, visited, tmp);
 822
 823   /* Process any blocks which require further iteration.  */
 824   while (live->stack_top != live->work_stack)
 825     {
 826       b = *--(live->stack_top);
 827       loe_visit_block (live, BASIC_BLOCK (b), visited, tmp);
 828     }
 829
 830   BITMAP_FREE (tmp);
 831   sbitmap_free (visited);
 832 }
 833
 834
 835 /* Calculate the initial live on entry vector for SSA_NAME using immediate_use
 836    links.  Set the live on entry fields in LIVE.  Def's are marked temporarily
 837    in the liveout vector.  */
 838
 839 static void
 840 set_var_live_on_entry (tree ssa_name, tree_live_info_p live)
 841 {
 842   int p;
 843   gimple stmt;
 844   use_operand_p use;
 845   basic_block def_bb = NULL;
 846   imm_use_iterator imm_iter;
 847   bool global = false;
 848
 849   p = var_to_partition (live->map, ssa_name);
 850   if (p == NO_PARTITION)
 851     return;
 852
 853   stmt = SSA_NAME_DEF_STMT (ssa_name);
 854   if (stmt)
 855     {
 856       def_bb = gimple_bb (stmt);
 857       /* Mark defs in liveout bitmap temporarily.  */
 858       if (def_bb)
 859         bitmap_set_bit (live->liveout[def_bb->index], p);
 860     }
 861   else
 862     def_bb = ENTRY_BLOCK_PTR;
 863
 864   /* Visit each use of SSA_NAME and if it isn't in the same block as the def,
 865      add it to the list of live on entry blocks.  */
 866   FOR_EACH_IMM_USE_FAST (use, imm_iter, ssa_name)
 867     {
 868       gimple use_stmt = USE_STMT (use);
 869       basic_block add_block = NULL;
 870
 871       if (gimple_code (use_stmt) == GIMPLE_PHI)
 872         {
 873           /* Uses in PHI's are considered to be live at exit of the SRC block
 874              as this is where a copy would be inserted.  Check to see if it is
 875              defined in that block, or whether its live on entry.  */
 876           int index = PHI_ARG_INDEX_FROM_USE (use);
 877           edge e = gimple_phi_arg_edge (use_stmt, index);
 878           if (e->src != ENTRY_BLOCK_PTR)
 879             {
 880               if (e->src != def_bb)
 881                 add_block = e->src;
 882             }
 883         }
 884       else
 885         {
 886           /* If its not defined in this block, its live on entry.  */
 887           basic_block use_bb = gimple_bb (use_stmt);
 888           if (use_bb != def_bb)
 889             add_block = use_bb;
 890         }
 891
 892       /* If there was a live on entry use, set the bit.  */
 893       if (add_block)
 894         {
 895           global = true;
 896           bitmap_set_bit (live->livein[add_block->index], p);
 897         }
 898     }
 899
 900   /* If SSA_NAME is live on entry to at least one block, fill in all the live
 901      on entry blocks between the def and all the uses.  */
 902   if (global)
 903     bitmap_set_bit (live->global, p);
 904 }
 905
 906
 907 /* Calculate the live on exit vectors based on the entry info in LIVEINFO.  */
 908
 909 void
 910 calculate_live_on_exit (tree_live_info_p liveinfo)
 911 {
 912   basic_block bb;
 913   edge e;
 914   edge_iterator ei;
 915
 916   /* live on entry calculations used liveout vectors for defs, clear them.  */
 917   FOR_EACH_BB (bb)
 918     bitmap_clear (liveinfo->liveout[bb->index]);
 919
 920   /* Set all the live-on-exit bits for uses in PHIs.  */
 921   FOR_EACH_BB (bb)
 922     {
 923       gimple_stmt_iterator gsi;
 924       size_t i;
 925
 926       /* Mark the PHI arguments which are live on exit to the pred block.  */
 927       for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 928         {
 929           gimple phi = gsi_stmt (gsi);
 930           for (i = 0; i < gimple_phi_num_args (phi); i++)
 931             {
 932               tree t = PHI_ARG_DEF (phi, i);
 933               int p;
 934
 935               if (TREE_CODE (t) != SSA_NAME)
 936                 continue;
 937
 938               p = var_to_partition (liveinfo->map, t);
 939               if (p == NO_PARTITION)
 940                 continue;
 941               e = gimple_phi_arg_edge (phi, i);
 942               if (e->src != ENTRY_BLOCK_PTR)
 943                 bitmap_set_bit (liveinfo->liveout[e->src->index], p);
 944             }
 945         }
 946
 947       /* Add each successors live on entry to this bock live on exit.  */
 948       FOR_EACH_EDGE (e, ei, bb->succs)
 949         if (e->dest != EXIT_BLOCK_PTR)
 950           bitmap_ior_into (liveinfo->liveout[bb->index],
 951                            live_on_entry (liveinfo, e->dest));
 952     }
 953 }
 954
 955
 956 /* Given partition map MAP, calculate all the live on entry bitmaps for
 957    each partition.  Return a new live info object.  */
 958
 959 tree_live_info_p
 960 calculate_live_ranges (var_map map)
 961 {
 962   tree var;
 963   unsigned i;
 964   tree_live_info_p live;
 965
 966   live = new_tree_live_info (map);
 967   for (i = 0; i < num_var_partitions (map); i++)
 968     {
 969       var = partition_to_var (map, i);
 970       if (var != NULL_TREE)
 971         set_var_live_on_entry (var, live);
 972     }
 973
 974   live_worklist (live);
 975
 976 #ifdef ENABLE_CHECKING
 977   verify_live_on_entry (live);
 978 #endif
 979
 980   calculate_live_on_exit (live);
 981   return live;
 982 }
 983
 984
 985 /* Output partition map MAP to file F.  */
 986
 987 void
 988 dump_var_map (FILE *f, var_map map)
 989 {
 990   int t;
 991   unsigned x, y;
 992   int p;
 993
 994   fprintf (f, "\nPartition map \n\n");
 995
 996   for (x = 0; x < map->num_partitions; x++)
 997     {
 998       if (map->view_to_partition != NULL)
 999         p = map->view_to_partition[x];
1000       else
1001         p = x;
1002
1003       if (map->partition_to_var[p] == NULL_TREE)
1004         continue;
1005
1006       t = 0;
1007       for (y = 1; y < num_ssa_names; y++)
1008         {
1009           p = partition_find (map->var_partition, y);
1010           if (map->partition_to_view)
1011             p = map->partition_to_view[p];
1012           if (p == (int)x)
1013             {
1014               if (t++ == 0)
1015                 {
1016                   fprintf(f, "Partition %d (", x);
1017                   print_generic_expr (f, partition_to_var (map, p), TDF_SLIM);
1018                   fprintf (f, " - ");
1019                 }
1020               fprintf (f, "%d ", y);
1021             }
1022         }
1023       if (t != 0)
1024         fprintf (f, ")\n");
1025     }
1026   fprintf (f, "\n");
1027 }
1028
1029
1030 /* Output live range info LIVE to file F, controlled by FLAG.  */
1031
1032 void
1033 dump_live_info (FILE *f, tree_live_info_p live, int flag)
1034 {
1035   basic_block bb;
1036   unsigned i;
1037   var_map map = live->map;
1038   bitmap_iterator bi;
1039
1040   if ((flag & LIVEDUMP_ENTRY) && live->livein)
1041     {
1042       FOR_EACH_BB (bb)
1043         {
1044           fprintf (f, "\nLive on entry to BB%d : ", bb->index);
1045           EXECUTE_IF_SET_IN_BITMAP (live->livein[bb->index], 0, i, bi)
1046             {
1047               print_generic_expr (f, partition_to_var (map, i), TDF_SLIM);
1048               fprintf (f, "  ");
1049             }
1050           fprintf (f, "\n");
1051         }
1052     }
1053
1054   if ((flag & LIVEDUMP_EXIT) && live->liveout)
1055     {
1056       FOR_EACH_BB (bb)
1057         {
1058           fprintf (f, "\nLive on exit from BB%d : ", bb->index);
1059           EXECUTE_IF_SET_IN_BITMAP (live->liveout[bb->index], 0, i, bi)
1060             {
1061               print_generic_expr (f, partition_to_var (map, i), TDF_SLIM);
1062               fprintf (f, "  ");
1063             }
1064           fprintf (f, "\n");
1065         }
1066     }
1067 }
1068
1069
1070 #ifdef ENABLE_CHECKING
1071 /* Verify that SSA_VAR is a non-virtual SSA_NAME.  */
1072
1073 void
1074 register_ssa_partition_check (tree ssa_var)
1075 {
1076   gcc_assert (TREE_CODE (ssa_var) == SSA_NAME);
1077   if (!is_gimple_reg (SSA_NAME_VAR (ssa_var)))
1078     {
1079       fprintf (stderr, "Illegally registering a virtual SSA name :");
1080       print_generic_expr (stderr, ssa_var, TDF_SLIM);
1081       fprintf (stderr, " in the SSA->Normal phase.\n");
1082       internal_error ("SSA corruption");
1083     }
1084 }
1085
1086
1087 /* Verify that the info in LIVE matches the current cfg.  */
1088
1089 static void
1090 verify_live_on_entry (tree_live_info_p live)
1091 {
1092   unsigned i;
1093   tree var;
1094   gimple stmt;
1095   basic_block bb;
1096   edge e;
1097   int num;
1098   edge_iterator ei;
1099   var_map map = live->map;
1100
1101    /* Check for live on entry partitions and report those with a DEF in
1102       the program. This will typically mean an optimization has done
1103       something wrong.  */
1104   bb = ENTRY_BLOCK_PTR;
1105   num = 0;
1106   FOR_EACH_EDGE (e, ei, bb->succs)
1107     {
1108       int entry_block = e->dest->index;
1109       if (e->dest == EXIT_BLOCK_PTR)
1110         continue;
1111       for (i = 0; i < (unsigned)num_var_partitions (map); i++)
1112         {
1113           basic_block tmp;
1114           tree d;
1115           bitmap loe;
1116           var = partition_to_var (map, i);
1117           stmt = SSA_NAME_DEF_STMT (var);
1118           tmp = gimple_bb (stmt);
1119           d = gimple_default_def (cfun, SSA_NAME_VAR (var));
1120
1121           loe = live_on_entry (live, e->dest);
1122           if (loe && bitmap_bit_p (loe, i))
1123             {
1124               if (!gimple_nop_p (stmt))
1125                 {
1126                   num++;
1127                   print_generic_expr (stderr, var, TDF_SLIM);
1128                   fprintf (stderr, " is defined ");
1129                   if (tmp)
1130                     fprintf (stderr, " in BB%d, ", tmp->index);
1131                   fprintf (stderr, "by:\n");
1132                   print_gimple_stmt (stderr, stmt, 0, TDF_SLIM);
1133                   fprintf (stderr, "\nIt is also live-on-entry to entry BB %d",
1134                            entry_block);
1135                   fprintf (stderr, " So it appears to have multiple defs.\n");
1136                 }
1137               else
1138                 {
1139                   if (d != var)
1140                     {
1141                       num++;
1142                       print_generic_expr (stderr, var, TDF_SLIM);
1143                       fprintf (stderr, " is live-on-entry to BB%d ",
1144                                entry_block);
1145                       if (d)
1146                         {
1147                           fprintf (stderr, " but is not the default def of ");
1148                           print_generic_expr (stderr, d, TDF_SLIM);
1149                           fprintf (stderr, "\n");
1150                         }
1151                       else
1152                         fprintf (stderr, " and there is no default def.\n");
1153                     }
1154                 }
1155             }
1156           else
1157             if (d == var)
1158               {
1159                 /* The only way this var shouldn't be marked live on entry is
1160                    if it occurs in a PHI argument of the block.  */
1161                 size_t z;
1162                 bool ok = false;
1163                 gimple_stmt_iterator gsi;
1164                 for (gsi = gsi_start_phis (e->dest);
1165                      !gsi_end_p (gsi) && !ok;
1166                      gsi_next (&gsi))
1167                   {
1168                     gimple phi = gsi_stmt (gsi);
1169                     for (z = 0; z < gimple_phi_num_args (phi); z++)
1170                       if (var == gimple_phi_arg_def (phi, z))
1171                         {
1172                           ok = true;
1173                           break;
1174                         }
1175                   }
1176                 if (ok)
1177                   continue;
1178                 num++;
1179                 print_generic_expr (stderr, var, TDF_SLIM);
1180                 fprintf (stderr, " is not marked live-on-entry to entry BB%d ",
1181                          entry_block);
1182                 fprintf (stderr, "but it is a default def so it should be.\n");
1183               }
1184         }
1185     }
1186   gcc_assert (num <= 0);
1187 }
1188 #endif