gcc/tree-ssa-live.c

   1 /* Liveness for SSA trees.
   2    Copyright (C) 2003, 2004, 2005, 2007, 2008, 2009 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       edge_iterator ei;
 604       edge e;
 605
 606       /* Walk the statements.  */
 607       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 608         {
 609           gimple stmt = gsi_stmt (gsi);
 610           tree b = gimple_block (stmt);
 611
 612           if (b)
 613             TREE_USED (b) = true;
 614
 615           for (i = 0; i < gimple_num_ops (stmt); i++)
 616             mark_all_vars_used (gimple_op_ptr (gsi_stmt (gsi), i), NULL);
 617         }
 618
 619       for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 620         {
 621           use_operand_p arg_p;
 622           ssa_op_iter i;
 623           tree def;
 624           gimple phi = gsi_stmt (gsi);
 625
 626           /* No point processing globals.  */
 627           if (is_global_var (SSA_NAME_VAR (gimple_phi_result (phi))))
 628             continue;
 629
 630           def = gimple_phi_result (phi);
 631           mark_all_vars_used (&def, NULL);
 632
 633           FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_ALL_USES)
 634             {
 635               tree arg = USE_FROM_PTR (arg_p);
 636               mark_all_vars_used (&arg, NULL);
 637             }
 638         }
 639
 640       FOR_EACH_EDGE (e, ei, bb->succs)
 641         if (e->goto_locus)
 642           TREE_USED (e->goto_block) = true;
 643     }
 644
 645   cfun->has_local_explicit_reg_vars = false;
 646
 647   /* Remove unmarked local vars from local_decls.  */
 648   for (cell = &cfun->local_decls; *cell; )
 649     {
 650       tree var = TREE_VALUE (*cell);
 651
 652       if (TREE_CODE (var) != FUNCTION_DECL
 653           && (!(ann = var_ann (var))
 654               || !ann->used))
 655         {
 656           if (is_global_var (var))
 657             {
 658               if (global_unused_vars == NULL)
 659                 global_unused_vars = BITMAP_ALLOC (NULL);
 660               bitmap_set_bit (global_unused_vars, DECL_UID (var));
 661             }
 662           else
 663             {
 664               *cell = TREE_CHAIN (*cell);
 665               continue;
 666             }
 667         }
 668       else if (TREE_CODE (var) == VAR_DECL
 669                && DECL_HARD_REGISTER (var)
 670                && !is_global_var (var))
 671         cfun->has_local_explicit_reg_vars = true;
 672       cell = &TREE_CHAIN (*cell);
 673     }
 674
 675   /* Remove unmarked global vars from local_decls.  */
 676   if (global_unused_vars != NULL)
 677     {
 678       for (t = cfun->local_decls; t; t = TREE_CHAIN (t))
 679         {
 680           tree var = TREE_VALUE (t);
 681
 682           if (TREE_CODE (var) == VAR_DECL
 683               && is_global_var (var)
 684               && (ann = var_ann (var)) != NULL
 685               && ann->used)
 686             mark_all_vars_used (&DECL_INITIAL (var), global_unused_vars);
 687         }
 688
 689       for (cell = &cfun->local_decls; *cell; )
 690         {
 691           tree var = TREE_VALUE (*cell);
 692
 693           if (TREE_CODE (var) == VAR_DECL
 694               && is_global_var (var)
 695               && bitmap_bit_p (global_unused_vars, DECL_UID (var))
 696               && (optimize || DECL_ARTIFICIAL (var)))
 697             *cell = TREE_CHAIN (*cell);
 698           else
 699             cell = &TREE_CHAIN (*cell);
 700         }
 701       BITMAP_FREE (global_unused_vars);
 702     }
 703
 704   /* Remove unused variables from REFERENCED_VARs.  As a special
 705      exception keep the variables that are believed to be aliased.
 706      Those can't be easily removed from the alias sets and operand
 707      caches.  They will be removed shortly after the next may_alias
 708      pass is performed.  */
 709   FOR_EACH_REFERENCED_VAR (t, rvi)
 710     if (!is_global_var (t)
 711         && !MTAG_P (t)
 712         && TREE_CODE (t) != PARM_DECL
 713         && TREE_CODE (t) != RESULT_DECL
 714         && !(ann = var_ann (t))->used
 715         && !ann->symbol_mem_tag
 716         && !TREE_ADDRESSABLE (t)
 717         && (optimize || DECL_ARTIFICIAL (t)))
 718       remove_referenced_var (t);
 719   if (optimize)
 720     remove_unused_scope_block_p (DECL_INITIAL (current_function_decl));
 721 }
 722
 723
 724 /* Allocate and return a new live range information object base on MAP.  */
 725
 726 static tree_live_info_p
 727 new_tree_live_info (var_map map)
 728 {
 729   tree_live_info_p live;
 730   unsigned x;
 731
 732   live = (tree_live_info_p) xmalloc (sizeof (struct tree_live_info_d));
 733   live->map = map;
 734   live->num_blocks = last_basic_block;
 735
 736   live->livein = (bitmap *)xmalloc (last_basic_block * sizeof (bitmap));
 737   for (x = 0; x < (unsigned)last_basic_block; x++)
 738     live->livein[x] = BITMAP_ALLOC (NULL);
 739
 740   live->liveout = (bitmap *)xmalloc (last_basic_block * sizeof (bitmap));
 741   for (x = 0; x < (unsigned)last_basic_block; x++)
 742     live->liveout[x] = BITMAP_ALLOC (NULL);
 743
 744   live->work_stack = XNEWVEC (int, last_basic_block);
 745   live->stack_top = live->work_stack;
 746
 747   live->global = BITMAP_ALLOC (NULL);
 748   return live;
 749 }
 750
 751
 752 /* Free storage for live range info object LIVE.  */
 753
 754 void
 755 delete_tree_live_info (tree_live_info_p live)
 756 {
 757   int x;
 758
 759   BITMAP_FREE (live->global);
 760   free (live->work_stack);
 761
 762   for (x = live->num_blocks - 1; x >= 0; x--)
 763     BITMAP_FREE (live->liveout[x]);
 764   free (live->liveout);
 765
 766   for (x = live->num_blocks - 1; x >= 0; x--)
 767     BITMAP_FREE (live->livein[x]);
 768   free (live->livein);
 769
 770   free (live);
 771 }
 772
 773
 774 /* Visit basic block BB and propagate any required live on entry bits from
 775    LIVE into the predecessors.  VISITED is the bitmap of visited blocks.
 776    TMP is a temporary work bitmap which is passed in to avoid reallocating
 777    it each time.  */
 778
 779 static void
 780 loe_visit_block (tree_live_info_p live, basic_block bb, sbitmap visited,
 781                  bitmap tmp)
 782 {
 783   edge e;
 784   bool change;
 785   edge_iterator ei;
 786   basic_block pred_bb;
 787   bitmap loe;
 788   gcc_assert (!TEST_BIT (visited, bb->index));
 789
 790   SET_BIT (visited, bb->index);
 791   loe = live_on_entry (live, bb);
 792
 793   FOR_EACH_EDGE (e, ei, bb->preds)
 794     {
 795       pred_bb = e->src;
 796       if (pred_bb == ENTRY_BLOCK_PTR)
 797         continue;
 798       /* TMP is variables live-on-entry from BB that aren't defined in the
 799          predecessor block.  This should be the live on entry vars to pred.
 800          Note that liveout is the DEFs in a block while live on entry is
 801          being calculated.  */
 802       bitmap_and_compl (tmp, loe, live->liveout[pred_bb->index]);
 803
 804       /* Add these bits to live-on-entry for the pred. if there are any
 805          changes, and pred_bb has been visited already, add it to the
 806          revisit stack.  */
 807       change = bitmap_ior_into (live_on_entry (live, pred_bb), tmp);
 808       if (TEST_BIT (visited, pred_bb->index) && change)
 809         {
 810           RESET_BIT (visited, pred_bb->index);
 811           *(live->stack_top)++ = pred_bb->index;
 812         }
 813     }
 814 }
 815
 816
 817 /* Using LIVE, fill in all the live-on-entry blocks between the defs and uses
 818    of all the variables.  */
 819
 820 static void
 821 live_worklist (tree_live_info_p live)
 822 {
 823   unsigned b;
 824   basic_block bb;
 825   sbitmap visited = sbitmap_alloc (last_basic_block + 1);
 826   bitmap tmp = BITMAP_ALLOC (NULL);
 827
 828   sbitmap_zero (visited);
 829
 830   /* Visit all the blocks in reverse order and propagate live on entry values
 831      into the predecessors blocks.  */
 832   FOR_EACH_BB_REVERSE (bb)
 833     loe_visit_block (live, bb, visited, tmp);
 834
 835   /* Process any blocks which require further iteration.  */
 836   while (live->stack_top != live->work_stack)
 837     {
 838       b = *--(live->stack_top);
 839       loe_visit_block (live, BASIC_BLOCK (b), visited, tmp);
 840     }
 841
 842   BITMAP_FREE (tmp);
 843   sbitmap_free (visited);
 844 }
 845
 846
 847 /* Calculate the initial live on entry vector for SSA_NAME using immediate_use
 848    links.  Set the live on entry fields in LIVE.  Def's are marked temporarily
 849    in the liveout vector.  */
 850
 851 static void
 852 set_var_live_on_entry (tree ssa_name, tree_live_info_p live)
 853 {
 854   int p;
 855   gimple stmt;
 856   use_operand_p use;
 857   basic_block def_bb = NULL;
 858   imm_use_iterator imm_iter;
 859   bool global = false;
 860
 861   p = var_to_partition (live->map, ssa_name);
 862   if (p == NO_PARTITION)
 863     return;
 864
 865   stmt = SSA_NAME_DEF_STMT (ssa_name);
 866   if (stmt)
 867     {
 868       def_bb = gimple_bb (stmt);
 869       /* Mark defs in liveout bitmap temporarily.  */
 870       if (def_bb)
 871         bitmap_set_bit (live->liveout[def_bb->index], p);
 872     }
 873   else
 874     def_bb = ENTRY_BLOCK_PTR;
 875
 876   /* Visit each use of SSA_NAME and if it isn't in the same block as the def,
 877      add it to the list of live on entry blocks.  */
 878   FOR_EACH_IMM_USE_FAST (use, imm_iter, ssa_name)
 879     {
 880       gimple use_stmt = USE_STMT (use);
 881       basic_block add_block = NULL;
 882
 883       if (gimple_code (use_stmt) == GIMPLE_PHI)
 884         {
 885           /* Uses in PHI's are considered to be live at exit of the SRC block
 886              as this is where a copy would be inserted.  Check to see if it is
 887              defined in that block, or whether its live on entry.  */
 888           int index = PHI_ARG_INDEX_FROM_USE (use);
 889           edge e = gimple_phi_arg_edge (use_stmt, index);
 890           if (e->src != ENTRY_BLOCK_PTR)
 891             {
 892               if (e->src != def_bb)
 893                 add_block = e->src;
 894             }
 895         }
 896       else
 897         {
 898           /* If its not defined in this block, its live on entry.  */
 899           basic_block use_bb = gimple_bb (use_stmt);
 900           if (use_bb != def_bb)
 901             add_block = use_bb;
 902         }
 903
 904       /* If there was a live on entry use, set the bit.  */
 905       if (add_block)
 906         {
 907           global = true;
 908           bitmap_set_bit (live->livein[add_block->index], p);
 909         }
 910     }
 911
 912   /* If SSA_NAME is live on entry to at least one block, fill in all the live
 913      on entry blocks between the def and all the uses.  */
 914   if (global)
 915     bitmap_set_bit (live->global, p);
 916 }
 917
 918
 919 /* Calculate the live on exit vectors based on the entry info in LIVEINFO.  */
 920
 921 void
 922 calculate_live_on_exit (tree_live_info_p liveinfo)
 923 {
 924   basic_block bb;
 925   edge e;
 926   edge_iterator ei;
 927
 928   /* live on entry calculations used liveout vectors for defs, clear them.  */
 929   FOR_EACH_BB (bb)
 930     bitmap_clear (liveinfo->liveout[bb->index]);
 931
 932   /* Set all the live-on-exit bits for uses in PHIs.  */
 933   FOR_EACH_BB (bb)
 934     {
 935       gimple_stmt_iterator gsi;
 936       size_t i;
 937
 938       /* Mark the PHI arguments which are live on exit to the pred block.  */
 939       for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 940         {
 941           gimple phi = gsi_stmt (gsi);
 942           for (i = 0; i < gimple_phi_num_args (phi); i++)
 943             {
 944               tree t = PHI_ARG_DEF (phi, i);
 945               int p;
 946
 947               if (TREE_CODE (t) != SSA_NAME)
 948                 continue;
 949
 950               p = var_to_partition (liveinfo->map, t);
 951               if (p == NO_PARTITION)
 952                 continue;
 953               e = gimple_phi_arg_edge (phi, i);
 954               if (e->src != ENTRY_BLOCK_PTR)
 955                 bitmap_set_bit (liveinfo->liveout[e->src->index], p);
 956             }
 957         }
 958
 959       /* Add each successors live on entry to this bock live on exit.  */
 960       FOR_EACH_EDGE (e, ei, bb->succs)
 961         if (e->dest != EXIT_BLOCK_PTR)
 962           bitmap_ior_into (liveinfo->liveout[bb->index],
 963                            live_on_entry (liveinfo, e->dest));
 964     }
 965 }
 966
 967
 968 /* Given partition map MAP, calculate all the live on entry bitmaps for
 969    each partition.  Return a new live info object.  */
 970
 971 tree_live_info_p
 972 calculate_live_ranges (var_map map)
 973 {
 974   tree var;
 975   unsigned i;
 976   tree_live_info_p live;
 977
 978   live = new_tree_live_info (map);
 979   for (i = 0; i < num_var_partitions (map); i++)
 980     {
 981       var = partition_to_var (map, i);
 982       if (var != NULL_TREE)
 983         set_var_live_on_entry (var, live);
 984     }
 985
 986   live_worklist (live);
 987
 988 #ifdef ENABLE_CHECKING
 989   verify_live_on_entry (live);
 990 #endif
 991
 992   calculate_live_on_exit (live);
 993   return live;
 994 }
 995
 996
 997 /* Output partition map MAP to file F.  */
 998
 999 void
1000 dump_var_map (FILE *f, var_map map)
1001 {
1002   int t;
1003   unsigned x, y;
1004   int p;
1005
1006   fprintf (f, "\nPartition map \n\n");
1007
1008   for (x = 0; x < map->num_partitions; x++)
1009     {
1010       if (map->view_to_partition != NULL)
1011         p = map->view_to_partition[x];
1012       else
1013         p = x;
1014
1015       if (map->partition_to_var[p] == NULL_TREE)
1016         continue;
1017
1018       t = 0;
1019       for (y = 1; y < num_ssa_names; y++)
1020         {
1021           p = partition_find (map->var_partition, y);
1022           if (map->partition_to_view)
1023             p = map->partition_to_view[p];
1024           if (p == (int)x)
1025             {
1026               if (t++ == 0)
1027                 {
1028                   fprintf(f, "Partition %d (", x);
1029                   print_generic_expr (f, partition_to_var (map, p), TDF_SLIM);
1030                   fprintf (f, " - ");
1031                 }
1032               fprintf (f, "%d ", y);
1033             }
1034         }
1035       if (t != 0)
1036         fprintf (f, ")\n");
1037     }
1038   fprintf (f, "\n");
1039 }
1040
1041
1042 /* Output live range info LIVE to file F, controlled by FLAG.  */
1043
1044 void
1045 dump_live_info (FILE *f, tree_live_info_p live, int flag)
1046 {
1047   basic_block bb;
1048   unsigned i;
1049   var_map map = live->map;
1050   bitmap_iterator bi;
1051
1052   if ((flag & LIVEDUMP_ENTRY) && live->livein)
1053     {
1054       FOR_EACH_BB (bb)
1055         {
1056           fprintf (f, "\nLive on entry to BB%d : ", bb->index);
1057           EXECUTE_IF_SET_IN_BITMAP (live->livein[bb->index], 0, i, bi)
1058             {
1059               print_generic_expr (f, partition_to_var (map, i), TDF_SLIM);
1060               fprintf (f, "  ");
1061             }
1062           fprintf (f, "\n");
1063         }
1064     }
1065
1066   if ((flag & LIVEDUMP_EXIT) && live->liveout)
1067     {
1068       FOR_EACH_BB (bb)
1069         {
1070           fprintf (f, "\nLive on exit from BB%d : ", bb->index);
1071           EXECUTE_IF_SET_IN_BITMAP (live->liveout[bb->index], 0, i, bi)
1072             {
1073               print_generic_expr (f, partition_to_var (map, i), TDF_SLIM);
1074               fprintf (f, "  ");
1075             }
1076           fprintf (f, "\n");
1077         }
1078     }
1079 }
1080
1081
1082 #ifdef ENABLE_CHECKING
1083 /* Verify that SSA_VAR is a non-virtual SSA_NAME.  */
1084
1085 void
1086 register_ssa_partition_check (tree ssa_var)
1087 {
1088   gcc_assert (TREE_CODE (ssa_var) == SSA_NAME);
1089   if (!is_gimple_reg (SSA_NAME_VAR (ssa_var)))
1090     {
1091       fprintf (stderr, "Illegally registering a virtual SSA name :");
1092       print_generic_expr (stderr, ssa_var, TDF_SLIM);
1093       fprintf (stderr, " in the SSA->Normal phase.\n");
1094       internal_error ("SSA corruption");
1095     }
1096 }
1097
1098
1099 /* Verify that the info in LIVE matches the current cfg.  */
1100
1101 static void
1102 verify_live_on_entry (tree_live_info_p live)
1103 {
1104   unsigned i;
1105   tree var;
1106   gimple stmt;
1107   basic_block bb;
1108   edge e;
1109   int num;
1110   edge_iterator ei;
1111   var_map map = live->map;
1112
1113    /* Check for live on entry partitions and report those with a DEF in
1114       the program. This will typically mean an optimization has done
1115       something wrong.  */
1116   bb = ENTRY_BLOCK_PTR;
1117   num = 0;
1118   FOR_EACH_EDGE (e, ei, bb->succs)
1119     {
1120       int entry_block = e->dest->index;
1121       if (e->dest == EXIT_BLOCK_PTR)
1122         continue;
1123       for (i = 0; i < (unsigned)num_var_partitions (map); i++)
1124         {
1125           basic_block tmp;
1126           tree d;
1127           bitmap loe;
1128           var = partition_to_var (map, i);
1129           stmt = SSA_NAME_DEF_STMT (var);
1130           tmp = gimple_bb (stmt);
1131           d = gimple_default_def (cfun, SSA_NAME_VAR (var));
1132
1133           loe = live_on_entry (live, e->dest);
1134           if (loe && bitmap_bit_p (loe, i))
1135             {
1136               if (!gimple_nop_p (stmt))
1137                 {
1138                   num++;
1139                   print_generic_expr (stderr, var, TDF_SLIM);
1140                   fprintf (stderr, " is defined ");
1141                   if (tmp)
1142                     fprintf (stderr, " in BB%d, ", tmp->index);
1143                   fprintf (stderr, "by:\n");
1144                   print_gimple_stmt (stderr, stmt, 0, TDF_SLIM);
1145                   fprintf (stderr, "\nIt is also live-on-entry to entry BB %d",
1146                            entry_block);
1147                   fprintf (stderr, " So it appears to have multiple defs.\n");
1148                 }
1149               else
1150                 {
1151                   if (d != var)
1152                     {
1153                       num++;
1154                       print_generic_expr (stderr, var, TDF_SLIM);
1155                       fprintf (stderr, " is live-on-entry to BB%d ",
1156                                entry_block);
1157                       if (d)
1158                         {
1159                           fprintf (stderr, " but is not the default def of ");
1160                           print_generic_expr (stderr, d, TDF_SLIM);
1161                           fprintf (stderr, "\n");
1162                         }
1163                       else
1164                         fprintf (stderr, " and there is no default def.\n");
1165                     }
1166                 }
1167             }
1168           else
1169             if (d == var)
1170               {
1171                 /* The only way this var shouldn't be marked live on entry is
1172                    if it occurs in a PHI argument of the block.  */
1173                 size_t z;
1174                 bool ok = false;
1175                 gimple_stmt_iterator gsi;
1176                 for (gsi = gsi_start_phis (e->dest);
1177                      !gsi_end_p (gsi) && !ok;
1178                      gsi_next (&gsi))
1179                   {
1180                     gimple phi = gsi_stmt (gsi);
1181                     for (z = 0; z < gimple_phi_num_args (phi); z++)
1182                       if (var == gimple_phi_arg_def (phi, z))
1183                         {
1184                           ok = true;
1185                           break;
1186                         }
1187                   }
1188                 if (ok)
1189                   continue;
1190                 num++;
1191                 print_generic_expr (stderr, var, TDF_SLIM);
1192                 fprintf (stderr, " is not marked live-on-entry to entry BB%d ",
1193                          entry_block);
1194                 fprintf (stderr, "but it is a default def so it should be.\n");
1195               }
1196         }
1197     }
1198   gcc_assert (num <= 0);
1199 }
1200 #endif