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