gcc/tree-ssa-live.c

   1 /* Liveness for SSA trees.
   2    Copyright (C) 2003, 2004, 2005 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 2, 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 COPYING.  If not, write to
  19 the Free Software Foundation, 51 Franklin Street, Fifth Floor,
  20 Boston, MA 02110-1301, USA.  */
  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
  34 #ifdef ENABLE_CHECKING
  35 static void  verify_live_on_entry (tree_live_info_p);
  36 #endif
  37
  38
  39 /* VARMAP maintains a mapping from SSA version number to real variables.
  40
  41    All SSA_NAMES are divided into partitions.  Initially each ssa_name is the
  42    only member of it's own partition.  Coalescing will attempt to group any
  43    ssa_names which occur in a copy or in a PHI node into the same partition.
  44
  45    At the end of out-of-ssa, each partition becomes a "real" variable and is
  46    rewritten as a compiler variable.
  47
  48    The var_map datat structure is used to manage these partitions.  It allows
  49    partitions to be combined, and determines which partition belongs to what
  50    ssa_name or variable, and vice versa.  */
  51
  52
  53 /* This routine will initialize the basevar fields of MAP.  */
  54
  55 static void
  56 var_map_base_init (var_map map)
  57 {
  58   int x, num_part, num;
  59   tree var;
  60   var_ann_t ann;
  61
  62   num = 0;
  63   num_part = num_var_partitions (map);
  64
  65   /* If a base table already exists, clear it, otherwise create it.  */
  66   if (map->partition_to_base_index != NULL)
  67     {
  68       free (map->partition_to_base_index);
  69       VEC_truncate (tree, map->basevars, 0);
  70     }
  71   else
  72     map->basevars = VEC_alloc (tree, heap, MAX (40, (num_part / 10)));
  73
  74   map->partition_to_base_index = (int *) xmalloc (sizeof (int) * num_part);
  75
  76   /* Build the base variable list, and point partitions at their bases.  */
  77   for (x = 0; x < num_part; x++)
  78     {
  79       var = partition_to_var (map, x);
  80       if (TREE_CODE (var) == SSA_NAME)
  81          var = SSA_NAME_VAR (var);
  82       ann = var_ann (var);
  83       /* If base variable hasn't been seen, set it up.  */
  84       if (!ann->base_var_processed)
  85         {
  86           ann->base_var_processed = 1;
  87           VAR_ANN_BASE_INDEX (ann) = num++;
  88           VEC_safe_push (tree, heap, map->basevars, var);
  89         }
  90       map->partition_to_base_index[x] = VAR_ANN_BASE_INDEX (ann);
  91     }
  92
  93   map->num_basevars = num;
  94
  95   /* Now clear the processed bit.  */
  96   for (x = 0; x < num; x++)
  97     {
  98        var = VEC_index (tree, map->basevars, x);
  99        var_ann (var)->base_var_processed = 0;
 100     }
 101
 102 #ifdef ENABLE_CHECKING
 103   for (x = 0; x < num_part; x++)
 104     {
 105       tree var2;
 106       var = SSA_NAME_VAR (partition_to_var (map, x));
 107       var2 = VEC_index (tree, map->basevars, basevar_index (map, x));
 108       gcc_assert (var == var2);
 109     }
 110 #endif
 111 }
 112
 113
 114 /* Remove the base table in MAP.  */
 115
 116 static void
 117 var_map_base_fini (var_map map)
 118 {
 119   /* Free the basevar info if it is present.  */
 120   if (map->partition_to_base_index != NULL)
 121     {
 122       VEC_free (tree, heap, map->basevars);
 123       free (map->partition_to_base_index);
 124       map->partition_to_base_index = NULL;
 125       map->num_basevars = 0;
 126     }
 127 }
 128 /* Create a variable partition map of SIZE, initialize and return it.  */
 129
 130 var_map
 131 init_var_map (int size)
 132 {
 133   var_map map;
 134
 135   map = (var_map) xmalloc (sizeof (struct _var_map));
 136   map->var_partition = partition_new (size);
 137   map->partition_to_var
 138               = (tree *)xmalloc (size * sizeof (tree));
 139   memset (map->partition_to_var, 0, size * sizeof (tree));
 140
 141   map->partition_to_view = NULL;
 142   map->view_to_partition = NULL;
 143   map->num_partitions = size;
 144   map->partition_size = size;
 145   map->num_basevars = 0;
 146   map->partition_to_base_index = NULL;
 147   map->basevars = NULL;
 148   return map;
 149 }
 150
 151
 152 /* Free memory associated with MAP.  */
 153
 154 void
 155 delete_var_map (var_map map)
 156 {
 157   var_map_base_fini (map);
 158   free (map->partition_to_var);
 159   partition_delete (map->var_partition);
 160   if (map->partition_to_view)
 161     free (map->partition_to_view);
 162   if (map->view_to_partition)
 163     free (map->view_to_partition);
 164   free (map);
 165 }
 166
 167
 168 /* This function will combine the partitions in MAP for VAR1 and VAR2.  It
 169    Returns the partition which represents the new partition.  If the two
 170    partitions cannot be combined, NO_PARTITION is returned.  */
 171
 172 int
 173 var_union (var_map map, tree var1, tree var2)
 174 {
 175   int p1, p2, p3;
 176   tree root_var = NULL_TREE;
 177   tree other_var = NULL_TREE;
 178
 179   /* This is independent of partition_to_view. If partition_to_view is
 180      on, then whichever one of these partitions is absorbed will never have a
 181      dereference into the partition_to_view array any more.  */
 182
 183   if (TREE_CODE (var1) == SSA_NAME)
 184     p1 = partition_find (map->var_partition, SSA_NAME_VERSION (var1));
 185   else
 186     {
 187       p1 = var_to_partition (map, var1);
 188       if (map->view_to_partition)
 189         p1 = map->view_to_partition[p1];
 190       root_var = var1;
 191     }
 192
 193   if (TREE_CODE (var2) == SSA_NAME)
 194     p2 = partition_find (map->var_partition, SSA_NAME_VERSION (var2));
 195   else
 196     {
 197       p2 = var_to_partition (map, var2);
 198       if (map->view_to_partition)
 199         p2 = map->view_to_partition[p2];
 200
 201       /* If there is no root_var set, or it's not a user variable, set the
 202          root_var to this one.  */
 203       if (!root_var || (DECL_P (root_var) && DECL_IGNORED_P (root_var)))
 204         {
 205           other_var = root_var;
 206           root_var = var2;
 207         }
 208       else
 209         other_var = var2;
 210     }
 211
 212   gcc_assert (p1 != NO_PARTITION);
 213   gcc_assert (p2 != NO_PARTITION);
 214
 215   if (p1 == p2)
 216     p3 = p1;
 217   else
 218     p3 = partition_union (map->var_partition, p1, p2);
 219
 220   if (map->partition_to_view)
 221     p3 = map->partition_to_view[p3];
 222
 223   if (root_var)
 224     change_partition_var (map, root_var, p3);
 225   if (other_var)
 226     change_partition_var (map, other_var, p3);
 227
 228   return p3;
 229 }
 230
 231
 232 /* Compress the partition numbers in MAP such that they fall in the range
 233    0..(num_partitions-1) instead of wherever they turned out during
 234    the partitioning exercise.  This removes any references to unused
 235    partitions, thereby allowing bitmaps and other vectors to be much
 236    denser.
 237
 238    This is implemented such that compaction doesn't affect partitioning.
 239    Ie., once partitions are created and possibly merged, running one
 240    or more different kind of compaction will not affect the partitions
 241    themselves.  Their index might change, but all the same variables will
 242    still be members of the same partition group.  This allows work on reduced
 243    sets, and no loss of information when a larger set is later desired.
 244
 245    In particular, coalescing can work on partitions which have 2 or more
 246    definitions, and then 'recompact' later to include all the single
 247    definitions for assignment to program variables.  */
 248
 249
 250 /* Set MAP back to the initial state of having no partition view.  Return a
 251    bitmap which has a bit set for each partition number which is in use in the
 252    varmap.  */
 253
 254 static bitmap
 255 partition_view_init (var_map map)
 256 {
 257   bitmap used;
 258   int tmp;
 259   unsigned int x;
 260
 261   used = BITMAP_ALLOC (NULL);
 262
 263   /* Already in a view? Abandon the old one.  */
 264   if (map->partition_to_view)
 265     {
 266       free (map->partition_to_view);
 267       map->partition_to_view = NULL;
 268     }
 269   if (map->view_to_partition)
 270     {
 271       free (map->view_to_partition);
 272       map->view_to_partition = NULL;
 273     }
 274
 275   /* Find out which partitions are actually referenced.  */
 276   for (x = 0; x < map->partition_size; x++)
 277     {
 278       tmp = partition_find (map->var_partition, x);
 279       if (map->partition_to_var[tmp] != NULL_TREE && !bitmap_bit_p (used, tmp))
 280         bitmap_set_bit (used, tmp);
 281     }
 282
 283   map->num_partitions = map->partition_size;
 284   return used;
 285 }
 286
 287
 288 /* This routine will finalize the view data for MAP based on the partitions
 289    set in SELECTED.  This is either the same bitmap returned from
 290    partition_view_init, or a trimmed down version if some of those partitions
 291    were not desired in this view.  SELECTED is freed before returning.  */
 292
 293 static void
 294 partition_view_fini (var_map map, bitmap selected)
 295 {
 296   bitmap_iterator bi;
 297   unsigned count, i, x, limit;
 298   tree var;
 299
 300   gcc_assert (selected);
 301
 302   count = bitmap_count_bits (selected);
 303   limit = map->partition_size;
 304
 305   /* If its a one-to-one ratio, we don't need any view compaction.  */
 306   if (count < limit)
 307     {
 308       map->partition_to_view = (int *)xmalloc (limit * sizeof (int));
 309       memset (map->partition_to_view, 0xff, (limit * sizeof (int)));
 310       map->view_to_partition = (int *)xmalloc (count * sizeof (int));
 311
 312       i = 0;
 313       /* Give each selected partition an index.  */
 314       EXECUTE_IF_SET_IN_BITMAP (selected, 0, x, bi)
 315         {
 316           map->partition_to_view[x] = i;
 317           map->view_to_partition[i] = x;
 318           var = map->partition_to_var[x];
 319           /* If any one of the members of a partition is not an SSA_NAME, make
 320              sure it is the representative.  */
 321           if (TREE_CODE (var) != SSA_NAME)
 322             change_partition_var (map, var, i);
 323           i++;
 324         }
 325       gcc_assert (i == count);
 326       map->num_partitions = i;
 327     }
 328
 329   BITMAP_FREE (selected);
 330 }
 331
 332
 333 /* Create a partition view which includes all the used partitions in MAP.  If
 334    WANT_BASES is true, create the base variable map as well.  */
 335
 336 extern void
 337 partition_view_normal (var_map map, bool want_bases)
 338 {
 339   bitmap used;
 340
 341   used = partition_view_init (map);
 342   partition_view_fini (map, used);
 343
 344   if (want_bases)
 345     var_map_base_init (map);
 346   else
 347     var_map_base_fini (map);
 348 }
 349
 350
 351 /* Create a partition view in MAP which includes just partitions which occur in
 352    the bitmap ONLY. If WANT_BASES is true, create the base variable map
 353    as well.  */
 354
 355 extern void
 356 partition_view_bitmap (var_map map, bitmap only, bool want_bases)
 357 {
 358   bitmap used;
 359   bitmap new_partitions = BITMAP_ALLOC (NULL);
 360   unsigned x, p;
 361   bitmap_iterator bi;
 362
 363   used = partition_view_init (map);
 364   EXECUTE_IF_SET_IN_BITMAP (only, 0, x, bi)
 365     {
 366       p = partition_find (map->var_partition, x);
 367       gcc_assert (bitmap_bit_p (used, p));
 368       bitmap_set_bit (new_partitions, p);
 369     }
 370   partition_view_fini (map, new_partitions);
 371
 372   BITMAP_FREE (used);
 373   if (want_bases)
 374     var_map_base_init (map);
 375   else
 376     var_map_base_fini (map);
 377 }
 378
 379
 380 /* This function is used to change the representative variable in MAP for VAR's
 381    partition to a regular non-ssa variable.  This allows partitions to be
 382    mapped back to real variables.  */
 383
 384 void
 385 change_partition_var (var_map map, tree var, int part)
 386 {
 387   var_ann_t ann;
 388
 389   gcc_assert (TREE_CODE (var) != SSA_NAME);
 390
 391   ann = var_ann (var);
 392   ann->out_of_ssa_tag = 1;
 393   VAR_ANN_PARTITION (ann) = part;
 394   if (map->view_to_partition)
 395     map->partition_to_var[map->view_to_partition[part]] = var;
 396 }
 397
 398
 399 static inline void mark_all_vars_used (tree *);
 400
 401 /* Helper function for mark_all_vars_used, called via walk_tree.  */
 402
 403 static tree
 404 mark_all_vars_used_1 (tree *tp, int *walk_subtrees,
 405                       void *data ATTRIBUTE_UNUSED)
 406 {
 407   tree t = *tp;
 408
 409   if (TREE_CODE (t) == SSA_NAME)
 410     t = SSA_NAME_VAR (t);
 411
 412   /* Ignore TREE_ORIGINAL for TARGET_MEM_REFS, as well as other
 413      fields that do not contain vars.  */
 414   if (TREE_CODE (t) == TARGET_MEM_REF)
 415     {
 416       mark_all_vars_used (&TMR_SYMBOL (t));
 417       mark_all_vars_used (&TMR_BASE (t));
 418       mark_all_vars_used (&TMR_INDEX (t));
 419       *walk_subtrees = 0;
 420       return NULL;
 421     }
 422
 423   /* Only need to mark VAR_DECLS; parameters and return results are not
 424      eliminated as unused.  */
 425   if (TREE_CODE (t) == VAR_DECL)
 426     set_is_used (t);
 427
 428   if (IS_TYPE_OR_DECL_P (t))
 429     *walk_subtrees = 0;
 430
 431   return NULL;
 432 }
 433
 434
 435 /* Mark all VAR_DECLS under *EXPR_P as used, so that they won't be
 436    eliminated during the tree->rtl conversion process.  */
 437
 438 static inline void
 439 mark_all_vars_used (tree *expr_p)
 440 {
 441   walk_tree (expr_p, mark_all_vars_used_1, NULL, NULL);
 442 }
 443
 444
 445 /* Remove local variables that are not referenced in the IL.  */
 446
 447 void
 448 remove_unused_locals (void)
 449 {
 450   basic_block bb;
 451   tree t, *cell;
 452   referenced_var_iterator rvi;
 453   var_ann_t ann;
 454
 455   /* Assume all locals are unused.  */
 456   FOR_EACH_REFERENCED_VAR (t, rvi)
 457     var_ann (t)->used = false;
 458
 459   /* Walk the CFG marking all referenced symbols.  */
 460   FOR_EACH_BB (bb)
 461     {
 462       block_stmt_iterator bsi;
 463       tree phi, def;
 464
 465       /* Walk the statements.  */
 466       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 467         mark_all_vars_used (bsi_stmt_ptr (bsi));
 468
 469       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 470         {
 471           use_operand_p arg_p;
 472           ssa_op_iter i;
 473
 474           /* No point processing globals.  */
 475           if (is_global_var (SSA_NAME_VAR (PHI_RESULT (phi))))
 476             continue;
 477
 478           def = PHI_RESULT (phi);
 479           mark_all_vars_used (&def);
 480
 481           FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_ALL_USES)
 482             {
 483               tree arg = USE_FROM_PTR (arg_p);
 484               mark_all_vars_used (&arg);
 485             }
 486         }
 487     }
 488
 489   /* Remove unmarked vars and clear used flag.  */
 490   for (cell = &cfun->unexpanded_var_list; *cell; )
 491     {
 492       tree var = TREE_VALUE (*cell);
 493
 494       if (TREE_CODE (var) != FUNCTION_DECL
 495           && (!(ann = var_ann (var))
 496               || !ann->used))
 497         {
 498           *cell = TREE_CHAIN (*cell);
 499           continue;
 500         }
 501
 502       cell = &TREE_CHAIN (*cell);
 503     }
 504
 505   /* Remove unused variables from REFERENCED_VARs.  As a special
 506      exception keep the variables that are believed to be aliased.
 507      Those can't be easily removed from the alias sets and operand
 508      caches.  They will be removed shortly after the next may_alias
 509      pass is performed.  */
 510   FOR_EACH_REFERENCED_VAR (t, rvi)
 511     if (!is_global_var (t)
 512         && !MTAG_P (t)
 513         && TREE_CODE (t) != PARM_DECL
 514         && TREE_CODE (t) != RESULT_DECL
 515         && !(ann = var_ann (t))->used
 516         && !ann->symbol_mem_tag
 517         && !TREE_ADDRESSABLE (t))
 518       remove_referenced_var (t);
 519 }
 520
 521
 522 /* Allocate and return a new live range information object base on MAP.  */
 523
 524 static tree_live_info_p
 525 new_tree_live_info (var_map map)
 526 {
 527   tree_live_info_p live;
 528   unsigned x;
 529
 530   live = (tree_live_info_p) xmalloc (sizeof (struct tree_live_info_d));
 531   live->map = map;
 532   live->num_blocks = last_basic_block;
 533
 534   live->livein = (bitmap *)xmalloc (last_basic_block * sizeof (bitmap));
 535   for (x = 0; x < (unsigned)last_basic_block; x++)
 536     live->livein[x] = BITMAP_ALLOC (NULL);
 537
 538   live->liveout = (bitmap *)xmalloc (last_basic_block * sizeof (bitmap));
 539   for (x = 0; x < (unsigned)last_basic_block; x++)
 540     live->liveout[x] = BITMAP_ALLOC (NULL);
 541
 542   live->work_stack = XNEWVEC (int, last_basic_block);
 543   live->stack_top = live->work_stack;
 544
 545   live->global = BITMAP_ALLOC (NULL);
 546   return live;
 547 }
 548
 549
 550 /* Free storage for live range info object LIVE.  */
 551
 552 void
 553 delete_tree_live_info (tree_live_info_p live)
 554 {
 555   int x;
 556
 557   BITMAP_FREE (live->global);
 558   free (live->work_stack);
 559
 560   for (x = live->num_blocks - 1; x >= 0; x--)
 561     BITMAP_FREE (live->liveout[x]);
 562   free (live->liveout);
 563
 564   for (x = live->num_blocks - 1; x >= 0; x--)
 565     BITMAP_FREE (live->livein[x]);
 566   free (live->livein);
 567
 568   free (live);
 569 }
 570
 571
 572 /* Visit basic block BB and propogate any required live on entry bits from
 573    LIVE into the predecessors.  VISITED is the bitmap of visited blocks.
 574    TMP is a temporary work bitmap which is passed in to avoid reallocating
 575    it each time.  */
 576
 577 static void
 578 loe_visit_block (tree_live_info_p live, basic_block bb, sbitmap visited,
 579                  bitmap tmp)
 580 {
 581   edge e;
 582   bool change;
 583   edge_iterator ei;
 584   basic_block pred_bb;
 585   bitmap loe;
 586   gcc_assert (!TEST_BIT (visited, bb->index));
 587
 588   SET_BIT (visited, bb->index);
 589   loe = live_on_entry (live, bb);
 590
 591   FOR_EACH_EDGE (e, ei, bb->preds)
 592     {
 593       pred_bb = e->src;
 594       if (pred_bb == ENTRY_BLOCK_PTR)
 595         continue;
 596       /* TMP is variables live-on-entry from BB that aren't defined in the
 597          predecessor block.  This should be the live on entry vars to pred.
 598          Note that liveout is the DEFs in a block while live on entry is
 599          being calculated.  */
 600       bitmap_and_compl (tmp, loe, live->liveout[pred_bb->index]);
 601
 602       /* Add these bits to live-on-entry for the pred. if there are any
 603          changes, and pred_bb has been visited already, add it to the
 604          revisit stack.  */
 605       change = bitmap_ior_into (live_on_entry (live, pred_bb), tmp);
 606       if (TEST_BIT (visited, pred_bb->index) && change)
 607         {
 608           RESET_BIT (visited, pred_bb->index);
 609           *(live->stack_top)++ = pred_bb->index;
 610         }
 611     }
 612 }
 613
 614
 615 /* Using LIVE, fill in all the live-on-entry blocks between the defs and uses
 616    of all the variables.  */
 617
 618 static void
 619 live_worklist (tree_live_info_p live)
 620 {
 621   unsigned b;
 622   basic_block bb;
 623   sbitmap visited = sbitmap_alloc (last_basic_block + 1);
 624   bitmap tmp = BITMAP_ALLOC (NULL);
 625
 626   sbitmap_zero (visited);
 627
 628   /* Visit all the blocks in reverse order and propogate live on entry values
 629      into the predecessors blocks.  */
 630   FOR_EACH_BB_REVERSE (bb)
 631     loe_visit_block (live, bb, visited, tmp);
 632
 633   /* Process any blocks which require further iteration.  */
 634   while (live->stack_top != live->work_stack)
 635     {
 636       b = *--(live->stack_top);
 637       loe_visit_block (live, BASIC_BLOCK (b), visited, tmp);
 638     }
 639
 640   BITMAP_FREE (tmp);
 641   sbitmap_free (visited);
 642 }
 643
 644
 645 /* Calculate the initial live on entry vector for SSA_NAME using immediate_use
 646    links.  Set the live on entry fields in LIVE.  Def's are marked temporarily
 647    in the liveout vector.  */
 648
 649 static void
 650 set_var_live_on_entry (tree ssa_name, tree_live_info_p live)
 651 {
 652   int p;
 653   tree stmt;
 654   use_operand_p use;
 655   basic_block def_bb = NULL;
 656   imm_use_iterator imm_iter;
 657   bool global = false;
 658
 659   p = var_to_partition (live->map, ssa_name);
 660   if (p == NO_PARTITION)
 661     return;
 662
 663   stmt = SSA_NAME_DEF_STMT (ssa_name);
 664   if (stmt)
 665     {
 666       def_bb = bb_for_stmt (stmt);
 667       /* Mark defs in liveout bitmap temporarily.  */
 668       if (def_bb)
 669         bitmap_set_bit (live->liveout[def_bb->index], p);
 670     }
 671   else
 672     def_bb = ENTRY_BLOCK_PTR;
 673
 674   /* Visit each use of SSA_NAME and if it isn't in the same block as the def,
 675      add it to the list of live on entry blocks.  */
 676   FOR_EACH_IMM_USE_FAST (use, imm_iter, ssa_name)
 677     {
 678       tree use_stmt = USE_STMT (use);
 679       basic_block add_block = NULL;
 680
 681       if (TREE_CODE (use_stmt) == PHI_NODE)
 682         {
 683           /* Uses in PHI's are considered to be live at exit of the SRC block
 684              as this is where a copy would be inserted.  Check to see if it is
 685              defined in that block, or whether its live on entry.  */
 686           int index = PHI_ARG_INDEX_FROM_USE (use);
 687           edge e = PHI_ARG_EDGE (use_stmt, index);
 688           if (e->src != ENTRY_BLOCK_PTR)
 689             {
 690               if (e->src != def_bb)
 691                 add_block = e->src;
 692             }
 693         }
 694       else
 695         {
 696           /* If its not defined in this block, its live on entry.  */
 697           basic_block use_bb = bb_for_stmt (use_stmt);
 698           if (use_bb != def_bb)
 699             add_block = use_bb;
 700         }
 701
 702       /* If there was a live on entry use, set the bit.  */
 703       if (add_block)
 704         {
 705           global = true;
 706           bitmap_set_bit (live->livein[add_block->index], p);
 707         }
 708     }
 709
 710   /* If SSA_NAME is live on entry to at least one block, fill in all the live
 711      on entry blocks between the def and all the uses.  */
 712   if (global)
 713     bitmap_set_bit (live->global, p);
 714 }
 715
 716
 717 /* Calculate the live on exit vectors based on the entry info in LIVEINFO.  */
 718
 719 void
 720 calculate_live_on_exit (tree_live_info_p liveinfo)
 721 {
 722   unsigned i;
 723   int p;
 724   tree t, phi;
 725   basic_block bb;
 726   edge e;
 727   edge_iterator ei;
 728
 729   /* live on entry calculations used liveout vectors for defs, clear them.  */
 730   FOR_EACH_BB (bb)
 731     bitmap_clear (liveinfo->liveout[bb->index]);
 732
 733   /* Set all the live-on-exit bits for uses in PHIs.  */
 734   FOR_EACH_BB (bb)
 735     {
 736       /* Mark the PHI arguments which are live on exit to the pred block.  */
 737       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 738         for (i = 0; i < (unsigned)PHI_NUM_ARGS (phi); i++)
 739           {
 740             t = PHI_ARG_DEF (phi, i);
 741             if (TREE_CODE (t) != SSA_NAME)
 742               continue;
 743             p = var_to_partition (liveinfo->map, t);
 744             if (p == NO_PARTITION)
 745               continue;
 746             e = PHI_ARG_EDGE (phi, i);
 747             if (e->src != ENTRY_BLOCK_PTR)
 748               bitmap_set_bit (liveinfo->liveout[e->src->index], p);
 749           }
 750
 751       /* Add each successors live on entry to this bock live on exit.  */
 752       FOR_EACH_EDGE (e, ei, bb->succs)
 753         if (e->dest != EXIT_BLOCK_PTR)
 754           bitmap_ior_into (liveinfo->liveout[bb->index],
 755                            live_on_entry (liveinfo, e->dest));
 756     }
 757 }
 758
 759
 760 /* Given partition map MAP, calculate all the live on entry bitmaps for
 761    each partition.  Return a new live info object.  */
 762
 763 tree_live_info_p
 764 calculate_live_ranges (var_map map)
 765 {
 766   tree var;
 767   unsigned i;
 768   tree_live_info_p live;
 769
 770   live = new_tree_live_info (map);
 771   for (i = 0; i < num_var_partitions (map); i++)
 772     {
 773       var = partition_to_var (map, i);
 774       if (var != NULL_TREE)
 775         set_var_live_on_entry (var, live);
 776     }
 777
 778   live_worklist (live);
 779
 780 #ifdef ENABLE_CHECKING
 781   verify_live_on_entry (live);
 782 #endif
 783
 784   calculate_live_on_exit (live);
 785   return live;
 786 }
 787
 788
 789 /* Output partition map MAP to file F.  */
 790
 791 void
 792 dump_var_map (FILE *f, var_map map)
 793 {
 794   int t;
 795   unsigned x, y;
 796   int p;
 797
 798   fprintf (f, "\nPartition map \n\n");
 799
 800   for (x = 0; x < map->num_partitions; x++)
 801     {
 802       if (map->view_to_partition != NULL)
 803         p = map->view_to_partition[x];
 804       else
 805         p = x;
 806
 807       if (map->partition_to_var[p] == NULL_TREE)
 808         continue;
 809
 810       t = 0;
 811       for (y = 1; y < num_ssa_names; y++)
 812         {
 813           p = partition_find (map->var_partition, y);
 814           if (map->partition_to_view)
 815             p = map->partition_to_view[p];
 816           if (p == (int)x)
 817             {
 818               if (t++ == 0)
 819                 {
 820                   fprintf(f, "Partition %d (", x);
 821                   print_generic_expr (f, partition_to_var (map, p), TDF_SLIM);
 822                   fprintf (f, " - ");
 823                 }
 824               fprintf (f, "%d ", y);
 825             }
 826         }
 827       if (t != 0)
 828         fprintf (f, ")\n");
 829     }
 830   fprintf (f, "\n");
 831 }
 832
 833
 834 /* Output live range info LIVE to file F, controlled by FLAG.  */
 835
 836 void
 837 dump_live_info (FILE *f, tree_live_info_p live, int flag)
 838 {
 839   basic_block bb;
 840   unsigned i;
 841   var_map map = live->map;
 842   bitmap_iterator bi;
 843
 844   if ((flag & LIVEDUMP_ENTRY) && live->livein)
 845     {
 846       FOR_EACH_BB (bb)
 847         {
 848           fprintf (f, "\nLive on entry to BB%d : ", bb->index);
 849           EXECUTE_IF_SET_IN_BITMAP (live->livein[bb->index], 0, i, bi)
 850             {
 851               print_generic_expr (f, partition_to_var (map, i), TDF_SLIM);
 852               fprintf (f, "  ");
 853             }
 854           fprintf (f, "\n");
 855         }
 856     }
 857
 858   if ((flag & LIVEDUMP_EXIT) && live->liveout)
 859     {
 860       FOR_EACH_BB (bb)
 861         {
 862           fprintf (f, "\nLive on exit from BB%d : ", bb->index);
 863           EXECUTE_IF_SET_IN_BITMAP (live->liveout[bb->index], 0, i, bi)
 864             {
 865               print_generic_expr (f, partition_to_var (map, i), TDF_SLIM);
 866               fprintf (f, "  ");
 867             }
 868           fprintf (f, "\n");
 869         }
 870     }
 871 }
 872
 873
 874 #ifdef ENABLE_CHECKING
 875 /* Verify that SSA_VAR is a non-virtual SSA_NAME.  */
 876
 877 void
 878 register_ssa_partition_check (tree ssa_var)
 879 {
 880   gcc_assert (TREE_CODE (ssa_var) == SSA_NAME);
 881   if (!is_gimple_reg (SSA_NAME_VAR (ssa_var)))
 882     {
 883       fprintf (stderr, "Illegally registering a virtual SSA name :");
 884       print_generic_expr (stderr, ssa_var, TDF_SLIM);
 885       fprintf (stderr, " in the SSA->Normal phase.\n");
 886       internal_error ("SSA corruption");
 887     }
 888 }
 889
 890
 891 /* Verify that the info in LIVE matches the current cfg.  */
 892
 893 static void
 894 verify_live_on_entry (tree_live_info_p live)
 895 {
 896   unsigned i;
 897   tree var;
 898   tree phi, stmt;
 899   basic_block bb;
 900   edge e;
 901   int num;
 902   edge_iterator ei;
 903   var_map map = live->map;
 904
 905    /* Check for live on entry partitions and report those with a DEF in
 906       the program. This will typically mean an optimization has done
 907       something wrong.  */
 908   bb = ENTRY_BLOCK_PTR;
 909   num = 0;
 910   FOR_EACH_EDGE (e, ei, bb->succs)
 911     {
 912       int entry_block = e->dest->index;
 913       if (e->dest == EXIT_BLOCK_PTR)
 914         continue;
 915       for (i = 0; i < (unsigned)num_var_partitions (map); i++)
 916         {
 917           basic_block tmp;
 918           tree d;
 919           bitmap loe;
 920           var = partition_to_var (map, i);
 921           stmt = SSA_NAME_DEF_STMT (var);
 922           tmp = bb_for_stmt (stmt);
 923           d = gimple_default_def (cfun, SSA_NAME_VAR (var));
 924
 925           loe = live_on_entry (live, e->dest);
 926           if (loe && bitmap_bit_p (loe, i))
 927             {
 928               if (!IS_EMPTY_STMT (stmt))
 929                 {
 930                   num++;
 931                   print_generic_expr (stderr, var, TDF_SLIM);
 932                   fprintf (stderr, " is defined ");
 933                   if (tmp)
 934                     fprintf (stderr, " in BB%d, ", tmp->index);
 935                   fprintf (stderr, "by:\n");
 936                   print_generic_expr (stderr, stmt, TDF_SLIM);
 937                   fprintf (stderr, "\nIt is also live-on-entry to entry BB %d",
 938                            entry_block);
 939                   fprintf (stderr, " So it appears to have multiple defs.\n");
 940                 }
 941               else
 942                 {
 943                   if (d != var)
 944                     {
 945                       num++;
 946                       print_generic_expr (stderr, var, TDF_SLIM);
 947                       fprintf (stderr, " is live-on-entry to BB%d ",entry_block);
 948                       if (d)
 949                         {
 950                           fprintf (stderr, " but is not the default def of ");
 951                           print_generic_expr (stderr, d, TDF_SLIM);
 952                           fprintf (stderr, "\n");
 953                         }
 954                       else
 955                         fprintf (stderr, " and there is no default def.\n");
 956                     }
 957                 }
 958             }
 959           else
 960             if (d == var)
 961               {
 962                 /* The only way this var shouldn't be marked live on entry is
 963                    if it occurs in a PHI argument of the block.  */
 964                 int z, ok = 0;
 965                 for (phi = phi_nodes (e->dest);
 966                      phi && !ok;
 967                      phi = PHI_CHAIN (phi))
 968                   {
 969                     for (z = 0; z < PHI_NUM_ARGS (phi); z++)
 970                       if (var == PHI_ARG_DEF (phi, z))
 971                         {
 972                           ok = 1;
 973                           break;
 974                         }
 975                   }
 976                 if (ok)
 977                   continue;
 978                 num++;
 979                 print_generic_expr (stderr, var, TDF_SLIM);
 980                 fprintf (stderr, " is not marked live-on-entry to entry BB%d ",
 981                          entry_block);
 982                 fprintf (stderr, "but it is a default def so it should be.\n");
 983               }
 984         }
 985     }
 986   gcc_assert (num <= 0);
 987 }
 988 #endif