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
 453   /* Assume all locals are unused.  */
 454   for (t = cfun->unexpanded_var_list; t; t = TREE_CHAIN (t))
 455     {
 456       tree var = TREE_VALUE (t);
 457       if (TREE_CODE (var) != FUNCTION_DECL
 458           && var_ann (var))
 459         var_ann (var)->used = false;
 460     }
 461
 462   /* Walk the CFG marking all referenced symbols.  */
 463   FOR_EACH_BB (bb)
 464     {
 465       block_stmt_iterator bsi;
 466       tree phi, def;
 467
 468       /* Walk the statements.  */
 469       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 470         mark_all_vars_used (bsi_stmt_ptr (bsi));
 471
 472       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 473         {
 474           use_operand_p arg_p;
 475           ssa_op_iter i;
 476
 477           /* No point processing globals.  */
 478           if (is_global_var (SSA_NAME_VAR (PHI_RESULT (phi))))
 479             continue;
 480
 481           def = PHI_RESULT (phi);
 482           mark_all_vars_used (&def);
 483
 484           FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_ALL_USES)
 485             {
 486               tree arg = USE_FROM_PTR (arg_p);
 487               mark_all_vars_used (&arg);
 488             }
 489         }
 490     }
 491
 492   /* Remove unmarked vars and clear used flag.  */
 493   for (cell = &cfun->unexpanded_var_list; *cell; )
 494     {
 495       tree var = TREE_VALUE (*cell);
 496       var_ann_t ann;
 497
 498       if (TREE_CODE (var) != FUNCTION_DECL
 499           && (!(ann = var_ann (var))
 500               || !ann->used))
 501         {
 502           *cell = TREE_CHAIN (*cell);
 503           continue;
 504         }
 505
 506       cell = &TREE_CHAIN (*cell);
 507     }
 508 }
 509
 510
 511 /* Allocate and return a new live range information object base on MAP.  */
 512
 513 static tree_live_info_p
 514 new_tree_live_info (var_map map)
 515 {
 516   tree_live_info_p live;
 517   unsigned x;
 518
 519   live = (tree_live_info_p) xmalloc (sizeof (struct tree_live_info_d));
 520   live->map = map;
 521   live->num_blocks = last_basic_block;
 522
 523   live->livein = (bitmap *)xmalloc (last_basic_block * sizeof (bitmap));
 524   for (x = 0; x < (unsigned)last_basic_block; x++)
 525     live->livein[x] = BITMAP_ALLOC (NULL);
 526
 527   live->liveout = (bitmap *)xmalloc (last_basic_block * sizeof (bitmap));
 528   for (x = 0; x < (unsigned)last_basic_block; x++)
 529     live->liveout[x] = BITMAP_ALLOC (NULL);
 530
 531   live->work_stack = XNEWVEC (int, last_basic_block);
 532   live->stack_top = live->work_stack;
 533
 534   live->global = BITMAP_ALLOC (NULL);
 535   return live;
 536 }
 537
 538
 539 /* Free storage for live range info object LIVE.  */
 540
 541 void
 542 delete_tree_live_info (tree_live_info_p live)
 543 {
 544   int x;
 545
 546   BITMAP_FREE (live->global);
 547   free (live->work_stack);
 548
 549   for (x = live->num_blocks - 1; x >= 0; x--)
 550     BITMAP_FREE (live->liveout[x]);
 551   free (live->liveout);
 552
 553   for (x = live->num_blocks - 1; x >= 0; x--)
 554     BITMAP_FREE (live->livein[x]);
 555   free (live->livein);
 556
 557   free (live);
 558 }
 559
 560
 561 /* Visit basic block BB and propogate any required live on entry bits from
 562    LIVE into the predecessors.  VISITED is the bitmap of visited blocks.
 563    TMP is a temporary work bitmap which is passed in to avoid reallocting
 564    it each time.  */
 565
 566 static void
 567 loe_visit_block (tree_live_info_p live, basic_block bb, sbitmap visited,
 568                  bitmap tmp)
 569 {
 570   edge e;
 571   bool change;
 572   edge_iterator ei;
 573   basic_block pred_bb;
 574   bitmap loe;
 575   gcc_assert (!TEST_BIT (visited, bb->index));
 576
 577   SET_BIT (visited, bb->index);
 578   loe = live_on_entry (live, bb);
 579
 580   FOR_EACH_EDGE (e, ei, bb->preds)
 581     {
 582       pred_bb = e->src;
 583       if (pred_bb == ENTRY_BLOCK_PTR)
 584         continue;
 585       /* TMP is variables live-on-entry from BB that aren't defined in the
 586          predecessor block.  This should be the live on entry vars to pred.
 587          Note that liveout is the DEFs in a block while live on entry is
 588          being calculated.  */
 589       bitmap_and_compl (tmp, loe, live->liveout[pred_bb->index]);
 590
 591       /* Add these bits to live-on-entry for the pred. if there are any
 592          changes, and pred_bb has been visited already, add it to the
 593          revisit stack.  */
 594       change = bitmap_ior_into (live_on_entry (live, pred_bb), tmp);
 595       if (TEST_BIT (visited, pred_bb->index) && change)
 596         {
 597           RESET_BIT (visited, pred_bb->index);
 598           *(live->stack_top)++ = pred_bb->index;
 599         }
 600     }
 601 }
 602
 603
 604 /* Using LIVE, fill in all the live-on-entry blocks between the defs and uses
 605    of all the vairables.  */
 606
 607 static void
 608 live_worklist (tree_live_info_p live)
 609 {
 610   unsigned b;
 611   basic_block bb;
 612   sbitmap visited = sbitmap_alloc (last_basic_block + 1);
 613   bitmap tmp = BITMAP_ALLOC (NULL);
 614
 615   sbitmap_zero (visited);
 616
 617   /* Visit all the blocks in reverse order and propogate live on entry values
 618      into the predecessors blocks.  */
 619   FOR_EACH_BB_REVERSE (bb)
 620     loe_visit_block (live, bb, visited, tmp);
 621
 622   /* Process any blocks which require further iteration.  */
 623   while (live->stack_top != live->work_stack)
 624     {
 625       b = *--(live->stack_top);
 626       loe_visit_block (live, BASIC_BLOCK (b), visited, tmp);
 627     }
 628
 629   BITMAP_FREE (tmp);
 630   sbitmap_free (visited);
 631 }
 632
 633
 634 /* Calulate the initial live on entry vector for SSA_NAME using immediate_use
 635    links.  Set the live on entry fields in LIVE.  Def's are marked temporarily
 636    in the liveout vector.  */
 637
 638 static void
 639 set_var_live_on_entry (tree ssa_name, tree_live_info_p live)
 640 {
 641   int p;
 642   tree stmt;
 643   use_operand_p use;
 644   basic_block def_bb = NULL;
 645   imm_use_iterator imm_iter;
 646   bool global = false;
 647
 648   p = var_to_partition (live->map, ssa_name);
 649   if (p == NO_PARTITION)
 650     return;
 651
 652   stmt = SSA_NAME_DEF_STMT (ssa_name);
 653   if (stmt)
 654     {
 655       def_bb = bb_for_stmt (stmt);
 656       /* Mark defs in liveout bitmap temporarily.  */
 657       if (def_bb)
 658         bitmap_set_bit (live->liveout[def_bb->index], p);
 659     }
 660   else
 661     def_bb = ENTRY_BLOCK_PTR;
 662
 663   /* Visit each use of SSA_NAME and if it isn't in the same block as the def,
 664      add it to the list of live on entry blocks.  */
 665   FOR_EACH_IMM_USE_FAST (use, imm_iter, ssa_name)
 666     {
 667       tree use_stmt = USE_STMT (use);
 668       basic_block add_block = NULL;
 669
 670       if (TREE_CODE (use_stmt) == PHI_NODE)
 671         {
 672           /* Uses in PHI's are considered to be live at exit of the SRC block
 673              as this is where a copy would be inserted.  Check to see if it is
 674              defined in that block, or whether its live on entry.  */
 675           int index = PHI_ARG_INDEX_FROM_USE (use);
 676           edge e = PHI_ARG_EDGE (use_stmt, index);
 677           if (e->src != ENTRY_BLOCK_PTR)
 678             {
 679               if (e->src != def_bb)
 680                 add_block = e->src;
 681             }
 682         }
 683       else
 684         {
 685           /* If its not defined in this block, its live on entry.  */
 686           basic_block use_bb = bb_for_stmt (use_stmt);
 687           if (use_bb != def_bb)
 688             add_block = use_bb;
 689         }
 690
 691       /* If there was a live on entry use, set the bit.  */
 692       if (add_block)
 693         {
 694           global = true;
 695           bitmap_set_bit (live->livein[add_block->index], p);
 696         }
 697     }
 698
 699   /* If SSA_NAME is live on entry to at least one block, fill in all the live
 700      on entry blocks between the def and all the uses.  */
 701   if (global)
 702     bitmap_set_bit (live->global, p);
 703 }
 704
 705
 706 /* Calculate the live on exit vectors based on the entry info in LIVEINFO.  */
 707
 708 void
 709 calculate_live_on_exit (tree_live_info_p liveinfo)
 710 {
 711   unsigned i;
 712   int p;
 713   tree t, phi;
 714   basic_block bb;
 715   edge e;
 716   edge_iterator ei;
 717
 718   /* live on entry calculations used liveout vectors for defs, clear them.  */
 719   FOR_EACH_BB (bb)
 720     bitmap_clear (liveinfo->liveout[bb->index]);
 721
 722   /* Set all the live-on-exit bits for uses in PHIs.  */
 723   FOR_EACH_BB (bb)
 724     {
 725       /* Mark the PHI arguments which are live on exit to the pred block.  */
 726       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 727         for (i = 0; i < (unsigned)PHI_NUM_ARGS (phi); i++)
 728           {
 729             t = PHI_ARG_DEF (phi, i);
 730             if (TREE_CODE (t) != SSA_NAME)
 731               continue;
 732             p = var_to_partition (liveinfo->map, t);
 733             if (p == NO_PARTITION)
 734               continue;
 735             e = PHI_ARG_EDGE (phi, i);
 736             if (e->src != ENTRY_BLOCK_PTR)
 737               bitmap_set_bit (liveinfo->liveout[e->src->index], p);
 738           }
 739
 740       /* Add each successors live on entry to this bock live on exit.  */
 741       FOR_EACH_EDGE (e, ei, bb->succs)
 742         if (e->dest != EXIT_BLOCK_PTR)
 743           bitmap_ior_into (liveinfo->liveout[bb->index],
 744                            live_on_entry (liveinfo, e->dest));
 745     }
 746 }
 747
 748
 749 /* Given partition map MAP, calculate all the live on entry bitmaps for
 750    each partition.  Return a new live info object.  */
 751
 752 tree_live_info_p
 753 calculate_live_ranges (var_map map)
 754 {
 755   tree var;
 756   unsigned i;
 757   tree_live_info_p live;
 758
 759   live = new_tree_live_info (map);
 760   for (i = 0; i < num_var_partitions (map); i++)
 761     {
 762       var = partition_to_var (map, i);
 763       if (var != NULL_TREE)
 764         set_var_live_on_entry (var, live);
 765     }
 766
 767   live_worklist (live);
 768
 769 #ifdef ENABLE_CHECKING
 770   verify_live_on_entry (live);
 771 #endif
 772
 773   calculate_live_on_exit (live);
 774   return live;
 775 }
 776
 777
 778 /* Output partition map MAP to file F.  */
 779
 780 void
 781 dump_var_map (FILE *f, var_map map)
 782 {
 783   int t;
 784   unsigned x, y;
 785   int p;
 786
 787   fprintf (f, "\nPartition map \n\n");
 788
 789   for (x = 0; x < map->num_partitions; x++)
 790     {
 791       if (map->view_to_partition != NULL)
 792         p = map->view_to_partition[x];
 793       else
 794         p = x;
 795
 796       if (map->partition_to_var[p] == NULL_TREE)
 797         continue;
 798
 799       t = 0;
 800       for (y = 1; y < num_ssa_names; y++)
 801         {
 802           p = partition_find (map->var_partition, y);
 803           if (map->partition_to_view)
 804             p = map->partition_to_view[p];
 805           if (p == (int)x)
 806             {
 807               if (t++ == 0)
 808                 {
 809                   fprintf(f, "Partition %d (", x);
 810                   print_generic_expr (f, partition_to_var (map, p), TDF_SLIM);
 811                   fprintf (f, " - ");
 812                 }
 813               fprintf (f, "%d ", y);
 814             }
 815         }
 816       if (t != 0)
 817         fprintf (f, ")\n");
 818     }
 819   fprintf (f, "\n");
 820 }
 821
 822
 823 /* Output live range info LIVE to file F, controlled by FLAG.  */
 824
 825 void
 826 dump_live_info (FILE *f, tree_live_info_p live, int flag)
 827 {
 828   basic_block bb;
 829   unsigned i;
 830   var_map map = live->map;
 831   bitmap_iterator bi;
 832
 833   if ((flag & LIVEDUMP_ENTRY) && live->livein)
 834     {
 835       FOR_EACH_BB (bb)
 836         {
 837           fprintf (f, "\nLive on entry to BB%d : ", bb->index);
 838           EXECUTE_IF_SET_IN_BITMAP (live->livein[bb->index], 0, i, bi)
 839             {
 840               print_generic_expr (f, partition_to_var (map, i), TDF_SLIM);
 841               fprintf (f, "  ");
 842             }
 843           fprintf (f, "\n");
 844         }
 845     }
 846
 847   if ((flag & LIVEDUMP_EXIT) && live->liveout)
 848     {
 849       FOR_EACH_BB (bb)
 850         {
 851           fprintf (f, "\nLive on exit from BB%d : ", bb->index);
 852           EXECUTE_IF_SET_IN_BITMAP (live->liveout[bb->index], 0, i, bi)
 853             {
 854               print_generic_expr (f, partition_to_var (map, i), TDF_SLIM);
 855               fprintf (f, "  ");
 856             }
 857           fprintf (f, "\n");
 858         }
 859     }
 860 }
 861
 862
 863 #ifdef ENABLE_CHECKING
 864 /* Verify that SSA_VAR is a non-virtual SSA_NAME.  */
 865
 866 void
 867 register_ssa_partition_check (tree ssa_var)
 868 {
 869   gcc_assert (TREE_CODE (ssa_var) == SSA_NAME);
 870   if (!is_gimple_reg (SSA_NAME_VAR (ssa_var)))
 871     {
 872       fprintf (stderr, "Illegally registering a virtual SSA name :");
 873       print_generic_expr (stderr, ssa_var, TDF_SLIM);
 874       fprintf (stderr, " in the SSA->Normal phase.\n");
 875       internal_error ("SSA corruption");
 876     }
 877 }
 878
 879
 880 /* Verify that the info in LIVE matches the current cfg.  */
 881
 882 static void
 883 verify_live_on_entry (tree_live_info_p live)
 884 {
 885   unsigned i;
 886   tree var;
 887   tree phi, stmt;
 888   basic_block bb;
 889   edge e;
 890   int num;
 891   edge_iterator ei;
 892   var_map map = live->map;
 893
 894    /* Check for live on entry partitions and report those with a DEF in
 895       the program. This will typically mean an optimization has done
 896       something wrong.  */
 897   bb = ENTRY_BLOCK_PTR;
 898   num = 0;
 899   FOR_EACH_EDGE (e, ei, bb->succs)
 900     {
 901       int entry_block = e->dest->index;
 902       if (e->dest == EXIT_BLOCK_PTR)
 903         continue;
 904       for (i = 0; i < (unsigned)num_var_partitions (map); i++)
 905         {
 906           basic_block tmp;
 907           tree d;
 908           bitmap loe;
 909           var = partition_to_var (map, i);
 910           stmt = SSA_NAME_DEF_STMT (var);
 911           tmp = bb_for_stmt (stmt);
 912           d = gimple_default_def (cfun, SSA_NAME_VAR (var));
 913
 914           loe = live_on_entry (live, e->dest);
 915           if (loe && bitmap_bit_p (loe, i))
 916             {
 917               if (!IS_EMPTY_STMT (stmt))
 918                 {
 919                   num++;
 920                   print_generic_expr (stderr, var, TDF_SLIM);
 921                   fprintf (stderr, " is defined ");
 922                   if (tmp)
 923                     fprintf (stderr, " in BB%d, ", tmp->index);
 924                   fprintf (stderr, "by:\n");
 925                   print_generic_expr (stderr, stmt, TDF_SLIM);
 926                   fprintf (stderr, "\nIt is also live-on-entry to entry BB %d",
 927                            entry_block);
 928                   fprintf (stderr, " So it appears to have multiple defs.\n");
 929                 }
 930               else
 931                 {
 932                   if (d != var)
 933                     {
 934                       num++;
 935                       print_generic_expr (stderr, var, TDF_SLIM);
 936                       fprintf (stderr, " is live-on-entry to BB%d ",entry_block);
 937                       if (d)
 938                         {
 939                           fprintf (stderr, " but is not the default def of ");
 940                           print_generic_expr (stderr, d, TDF_SLIM);
 941                           fprintf (stderr, "\n");
 942                         }
 943                       else
 944                         fprintf (stderr, " and there is no default def.\n");
 945                     }
 946                 }
 947             }
 948           else
 949             if (d == var)
 950               {
 951                 /* The only way this var shouldn't be marked live on entry is
 952                    if it occurs in a PHI argument of the block.  */
 953                 int z, ok = 0;
 954                 for (phi = phi_nodes (e->dest);
 955                      phi && !ok;
 956                      phi = PHI_CHAIN (phi))
 957                   {
 958                     for (z = 0; z < PHI_NUM_ARGS (phi); z++)
 959                       if (var == PHI_ARG_DEF (phi, z))
 960                         {
 961                           ok = 1;
 962                           break;
 963                         }
 964                   }
 965                 if (ok)
 966                   continue;
 967                 num++;
 968                 print_generic_expr (stderr, var, TDF_SLIM);
 969                 fprintf (stderr, " is not marked live-on-entry to entry BB%d ",
 970                          entry_block);
 971                 fprintf (stderr, "but it is a default def so it should be.\n");
 972               }
 973         }
 974     }
 975   gcc_assert (num <= 0);
 976 }
 977 #endif