OSDN Git Service

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