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