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