OSDN Git Service

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