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