gcc/tree-ssa-live.c

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