OpenCores
URL https://opencores.org/ocsvn/openrisc_me/openrisc_me/trunk

Subversion Repositories openrisc_me

[/] [openrisc/] [trunk/] [gnu-src/] [gcc-4.5.1/] [gcc/] [tree-ssa-live.c] - Blame information for rev 280

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 280 jeremybenn
/* 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
 
140
  map->partition_to_view = NULL;
141
  map->view_to_partition = NULL;
142
  map->num_partitions = size;
143
  map->partition_size = size;
144
  map->num_basevars = 0;
145
  map->partition_to_base_index = NULL;
146
  map->basevars = NULL;
147
  return map;
148
}
149
 
150
 
151
/* Free memory associated with MAP.  */
152
 
153
void
154
delete_var_map (var_map map)
155
{
156
  var_map_base_fini (map);
157
  partition_delete (map->var_partition);
158
  if (map->partition_to_view)
159
    free (map->partition_to_view);
160
  if (map->view_to_partition)
161
    free (map->view_to_partition);
162
  free (map);
163
}
164
 
165
 
166
/* This function will combine the partitions in MAP for VAR1 and VAR2.  It
167
   Returns the partition which represents the new partition.  If the two
168
   partitions cannot be combined, NO_PARTITION is returned.  */
169
 
170
int
171
var_union (var_map map, tree var1, tree var2)
172
{
173
  int p1, p2, p3;
174
 
175
  gcc_assert (TREE_CODE (var1) == SSA_NAME);
176
  gcc_assert (TREE_CODE (var2) == SSA_NAME);
177
 
178
  /* This is independent of partition_to_view. If partition_to_view is
179
     on, then whichever one of these partitions is absorbed will never have a
180
     dereference into the partition_to_view array any more.  */
181
 
182
  p1 = partition_find (map->var_partition, SSA_NAME_VERSION (var1));
183
  p2 = partition_find (map->var_partition, SSA_NAME_VERSION (var2));
184
 
185
  gcc_assert (p1 != NO_PARTITION);
186
  gcc_assert (p2 != NO_PARTITION);
187
 
188
  if (p1 == p2)
189
    p3 = p1;
190
  else
191
    p3 = partition_union (map->var_partition, p1, p2);
192
 
193
  if (map->partition_to_view)
194
    p3 = map->partition_to_view[p3];
195
 
196
  return p3;
197
}
198
 
199
 
200
/* Compress the partition numbers in MAP such that they fall in the range
201
   0..(num_partitions-1) instead of wherever they turned out during
202
   the partitioning exercise.  This removes any references to unused
203
   partitions, thereby allowing bitmaps and other vectors to be much
204
   denser.
205
 
206
   This is implemented such that compaction doesn't affect partitioning.
207
   Ie., once partitions are created and possibly merged, running one
208
   or more different kind of compaction will not affect the partitions
209
   themselves.  Their index might change, but all the same variables will
210
   still be members of the same partition group.  This allows work on reduced
211
   sets, and no loss of information when a larger set is later desired.
212
 
213
   In particular, coalescing can work on partitions which have 2 or more
214
   definitions, and then 'recompact' later to include all the single
215
   definitions for assignment to program variables.  */
216
 
217
 
218
/* Set MAP back to the initial state of having no partition view.  Return a
219
   bitmap which has a bit set for each partition number which is in use in the
220
   varmap.  */
221
 
222
static bitmap
223
partition_view_init (var_map map)
224
{
225
  bitmap used;
226
  int tmp;
227
  unsigned int x;
228
 
229
  used = BITMAP_ALLOC (NULL);
230
 
231
  /* Already in a view? Abandon the old one.  */
232
  if (map->partition_to_view)
233
    {
234
      free (map->partition_to_view);
235
      map->partition_to_view = NULL;
236
    }
237
  if (map->view_to_partition)
238
    {
239
      free (map->view_to_partition);
240
      map->view_to_partition = NULL;
241
    }
242
 
243
  /* Find out which partitions are actually referenced.  */
244
  for (x = 0; x < map->partition_size; x++)
245
    {
246
      tmp = partition_find (map->var_partition, x);
247
      if (ssa_name (tmp) != NULL_TREE && is_gimple_reg (ssa_name (tmp))
248
          && (!has_zero_uses (ssa_name (tmp))
249
              || !SSA_NAME_IS_DEFAULT_DEF (ssa_name (tmp))))
250
        bitmap_set_bit (used, tmp);
251
    }
252
 
253
  map->num_partitions = map->partition_size;
254
  return used;
255
}
256
 
257
 
258
/* This routine will finalize the view data for MAP based on the partitions
259
   set in SELECTED.  This is either the same bitmap returned from
260
   partition_view_init, or a trimmed down version if some of those partitions
261
   were not desired in this view.  SELECTED is freed before returning.  */
262
 
263
static void
264
partition_view_fini (var_map map, bitmap selected)
265
{
266
  bitmap_iterator bi;
267
  unsigned count, i, x, limit;
268
 
269
  gcc_assert (selected);
270
 
271
  count = bitmap_count_bits (selected);
272
  limit = map->partition_size;
273
 
274
  /* If its a one-to-one ratio, we don't need any view compaction.  */
275
  if (count < limit)
276
    {
277
      map->partition_to_view = (int *)xmalloc (limit * sizeof (int));
278
      memset (map->partition_to_view, 0xff, (limit * sizeof (int)));
279
      map->view_to_partition = (int *)xmalloc (count * sizeof (int));
280
 
281
      i = 0;
282
      /* Give each selected partition an index.  */
283
      EXECUTE_IF_SET_IN_BITMAP (selected, 0, x, bi)
284
        {
285
          map->partition_to_view[x] = i;
286
          map->view_to_partition[i] = x;
287
          i++;
288
        }
289
      gcc_assert (i == count);
290
      map->num_partitions = i;
291
    }
292
 
293
  BITMAP_FREE (selected);
294
}
295
 
296
 
297
/* Create a partition view which includes all the used partitions in MAP.  If
298
   WANT_BASES is true, create the base variable map as well.  */
299
 
300
extern void
301
partition_view_normal (var_map map, bool want_bases)
302
{
303
  bitmap used;
304
 
305
  used = partition_view_init (map);
306
  partition_view_fini (map, used);
307
 
308
  if (want_bases)
309
    var_map_base_init (map);
310
  else
311
    var_map_base_fini (map);
312
}
313
 
314
 
315
/* Create a partition view in MAP which includes just partitions which occur in
316
   the bitmap ONLY. If WANT_BASES is true, create the base variable map
317
   as well.  */
318
 
319
extern void
320
partition_view_bitmap (var_map map, bitmap only, bool want_bases)
321
{
322
  bitmap used;
323
  bitmap new_partitions = BITMAP_ALLOC (NULL);
324
  unsigned x, p;
325
  bitmap_iterator bi;
326
 
327
  used = partition_view_init (map);
328
  EXECUTE_IF_SET_IN_BITMAP (only, 0, x, bi)
329
    {
330
      p = partition_find (map->var_partition, x);
331
      gcc_assert (bitmap_bit_p (used, p));
332
      bitmap_set_bit (new_partitions, p);
333
    }
334
  partition_view_fini (map, new_partitions);
335
 
336
  BITMAP_FREE (used);
337
  if (want_bases)
338
    var_map_base_init (map);
339
  else
340
    var_map_base_fini (map);
341
}
342
 
343
 
344
static inline void mark_all_vars_used (tree *, void *data);
345
 
346
/* Helper function for mark_all_vars_used, called via walk_tree.  */
347
 
348
static tree
349
mark_all_vars_used_1 (tree *tp, int *walk_subtrees, void *data)
350
{
351
  tree t = *tp;
352
  enum tree_code_class c = TREE_CODE_CLASS (TREE_CODE (t));
353
  tree b;
354
 
355
  if (TREE_CODE (t) == SSA_NAME)
356
    t = SSA_NAME_VAR (t);
357
 
358
  if (IS_EXPR_CODE_CLASS (c)
359
      && (b = TREE_BLOCK (t)) != NULL)
360
    TREE_USED (b) = true;
361
 
362
  /* Ignore TREE_ORIGINAL for TARGET_MEM_REFS, as well as other
363
     fields that do not contain vars.  */
364
  if (TREE_CODE (t) == TARGET_MEM_REF)
365
    {
366
      mark_all_vars_used (&TMR_SYMBOL (t), data);
367
      mark_all_vars_used (&TMR_BASE (t), data);
368
      mark_all_vars_used (&TMR_INDEX (t), data);
369
      *walk_subtrees = 0;
370
      return NULL;
371
    }
372
 
373
  /* Only need to mark VAR_DECLS; parameters and return results are not
374
     eliminated as unused.  */
375
  if (TREE_CODE (t) == VAR_DECL)
376
    {
377
      if (data != NULL && bitmap_bit_p ((bitmap) data, DECL_UID (t)))
378
        {
379
          bitmap_clear_bit ((bitmap) data, DECL_UID (t));
380
          mark_all_vars_used (&DECL_INITIAL (t), data);
381
        }
382
      set_is_used (t);
383
    }
384
 
385
  if (IS_TYPE_OR_DECL_P (t))
386
    *walk_subtrees = 0;
387
 
388
  return NULL;
389
}
390
 
391
/* Mark the scope block SCOPE and its subblocks unused when they can be
392
   possibly eliminated if dead.  */
393
 
394
static void
395
mark_scope_block_unused (tree scope)
396
{
397
  tree t;
398
  TREE_USED (scope) = false;
399
  if (!(*debug_hooks->ignore_block) (scope))
400
    TREE_USED (scope) = true;
401
  for (t = BLOCK_SUBBLOCKS (scope); t ; t = BLOCK_CHAIN (t))
402
    mark_scope_block_unused (t);
403
}
404
 
405
/* Look if the block is dead (by possibly eliminating its dead subblocks)
406
   and return true if so.
407
   Block is declared dead if:
408
     1) No statements are associated with it.
409
     2) Declares no live variables
410
     3) All subblocks are dead
411
        or there is precisely one subblocks and the block
412
        has same abstract origin as outer block and declares
413
        no variables, so it is pure wrapper.
414
   When we are not outputting full debug info, we also eliminate dead variables
415
   out of scope blocks to let them to be recycled by GGC and to save copying work
416
   done by the inliner.  */
417
 
418
static bool
419
remove_unused_scope_block_p (tree scope)
420
{
421
  tree *t, *next;
422
  bool unused = !TREE_USED (scope);
423
  var_ann_t ann;
424
  int nsubblocks = 0;
425
 
426
  for (t = &BLOCK_VARS (scope); *t; t = next)
427
    {
428
      next = &TREE_CHAIN (*t);
429
 
430
      /* Debug info of nested function refers to the block of the
431
         function.  We might stil call it even if all statements
432
         of function it was nested into was elliminated.
433
 
434
         TODO: We can actually look into cgraph to see if function
435
         will be output to file.  */
436
      if (TREE_CODE (*t) == FUNCTION_DECL)
437
        unused = false;
438
 
439
      /* If a decl has a value expr, we need to instantiate it
440
         regardless of debug info generation, to avoid codegen
441
         differences in memory overlap tests.  update_equiv_regs() may
442
         indirectly call validate_equiv_mem() to test whether a
443
         SET_DEST overlaps with others, and if the value expr changes
444
         by virtual register instantiation, we may get end up with
445
         different results.  */
446
      else if (TREE_CODE (*t) == VAR_DECL && DECL_HAS_VALUE_EXPR_P (*t))
447
        unused = false;
448
 
449
      /* Remove everything we don't generate debug info for.  */
450
      else if (DECL_IGNORED_P (*t))
451
        {
452
          *t = TREE_CHAIN (*t);
453
          next = t;
454
        }
455
 
456
      /* When we are outputting debug info, we usually want to output
457
         info about optimized-out variables in the scope blocks.
458
         Exception are the scope blocks not containing any instructions
459
         at all so user can't get into the scopes at first place.  */
460
      else if ((ann = var_ann (*t)) != NULL
461
                && ann->used)
462
        unused = false;
463
 
464
      /* When we are not doing full debug info, we however can keep around
465
         only the used variables for cfgexpand's memory packing saving quite
466
         a lot of memory.
467
 
468
         For sake of -g3, we keep around those vars but we don't count this as
469
         use of block, so innermost block with no used vars and no instructions
470
         can be considered dead.  We only want to keep around blocks user can
471
         breakpoint into and ask about value of optimized out variables.
472
 
473
         Similarly we need to keep around types at least until all variables of
474
         all nested blocks are gone.  We track no information on whether given
475
         type is used or not.  */
476
 
477
      else if (debug_info_level == DINFO_LEVEL_NORMAL
478
               || debug_info_level == DINFO_LEVEL_VERBOSE)
479
        ;
480
      else
481
        {
482
          *t = TREE_CHAIN (*t);
483
          next = t;
484
        }
485
    }
486
 
487
  for (t = &BLOCK_SUBBLOCKS (scope); *t ;)
488
    if (remove_unused_scope_block_p (*t))
489
      {
490
        if (BLOCK_SUBBLOCKS (*t))
491
          {
492
            tree next = BLOCK_CHAIN (*t);
493
            tree supercontext = BLOCK_SUPERCONTEXT (*t);
494
 
495
            *t = BLOCK_SUBBLOCKS (*t);
496
            while (BLOCK_CHAIN (*t))
497
              {
498
                BLOCK_SUPERCONTEXT (*t) = supercontext;
499
                t = &BLOCK_CHAIN (*t);
500
              }
501
            BLOCK_CHAIN (*t) = next;
502
            BLOCK_SUPERCONTEXT (*t) = supercontext;
503
            t = &BLOCK_CHAIN (*t);
504
            nsubblocks ++;
505
          }
506
        else
507
          *t = BLOCK_CHAIN (*t);
508
      }
509
    else
510
      {
511
        t = &BLOCK_CHAIN (*t);
512
        nsubblocks ++;
513
      }
514
 
515
 
516
   if (!unused)
517
     ;
518
   /* Outer scope is always used.  */
519
   else if (!BLOCK_SUPERCONTEXT (scope)
520
            || TREE_CODE (BLOCK_SUPERCONTEXT (scope)) == FUNCTION_DECL)
521
     unused = false;
522
   /* Innermost blocks with no live variables nor statements can be always
523
      eliminated.  */
524
   else if (!nsubblocks)
525
     ;
526
   /* For terse debug info we can eliminate info on unused variables.  */
527
   else if (debug_info_level == DINFO_LEVEL_NONE
528
            || debug_info_level == DINFO_LEVEL_TERSE)
529
     {
530
       /* Even for -g0/-g1 don't prune outer scopes from artificial
531
          functions, otherwise diagnostics using tree_nonartificial_location
532
          will not be emitted properly.  */
533
       if (inlined_function_outer_scope_p (scope))
534
         {
535
           tree ao = scope;
536
 
537
           while (ao
538
                  && TREE_CODE (ao) == BLOCK
539
                  && BLOCK_ABSTRACT_ORIGIN (ao) != ao)
540
             ao = BLOCK_ABSTRACT_ORIGIN (ao);
541
           if (ao
542
               && TREE_CODE (ao) == FUNCTION_DECL
543
               && DECL_DECLARED_INLINE_P (ao)
544
               && lookup_attribute ("artificial", DECL_ATTRIBUTES (ao)))
545
             unused = false;
546
         }
547
     }
548
   else if (BLOCK_VARS (scope) || BLOCK_NUM_NONLOCALIZED_VARS (scope))
549
     unused = false;
550
   /* See if this block is important for representation of inlined function.
551
      Inlined functions are always represented by block with
552
      block_ultimate_origin being set to FUNCTION_DECL and DECL_SOURCE_LOCATION
553
      set...  */
554
   else if (inlined_function_outer_scope_p (scope))
555
     unused = false;
556
   else
557
   /* Verfify that only blocks with source location set
558
      are entry points to the inlined functions.  */
559
     gcc_assert (BLOCK_SOURCE_LOCATION (scope) == UNKNOWN_LOCATION);
560
 
561
   TREE_USED (scope) = !unused;
562
   return unused;
563
}
564
 
565
/* Mark all VAR_DECLS under *EXPR_P as used, so that they won't be
566
   eliminated during the tree->rtl conversion process.  */
567
 
568
static inline void
569
mark_all_vars_used (tree *expr_p, void *data)
570
{
571
  walk_tree (expr_p, mark_all_vars_used_1, data, NULL);
572
}
573
 
574
 
575
/* Dump scope blocks starting at SCOPE to FILE.  INDENT is the
576
   indentation level and FLAGS is as in print_generic_expr.  */
577
 
578
static void
579
dump_scope_block (FILE *file, int indent, tree scope, int flags)
580
{
581
  tree var, t;
582
  unsigned int i;
583
 
584
  fprintf (file, "\n%*s{ Scope block #%i%s%s",indent, "" , BLOCK_NUMBER (scope),
585
           TREE_USED (scope) ? "" : " (unused)",
586
           BLOCK_ABSTRACT (scope) ? " (abstract)": "");
587
  if (BLOCK_SOURCE_LOCATION (scope) != UNKNOWN_LOCATION)
588
    {
589
      expanded_location s = expand_location (BLOCK_SOURCE_LOCATION (scope));
590
      fprintf (file, " %s:%i", s.file, s.line);
591
    }
592
  if (BLOCK_ABSTRACT_ORIGIN (scope))
593
    {
594
      tree origin = block_ultimate_origin (scope);
595
      if (origin)
596
        {
597
          fprintf (file, " Originating from :");
598
          if (DECL_P (origin))
599
            print_generic_decl (file, origin, flags);
600
          else
601
            fprintf (file, "#%i", BLOCK_NUMBER (origin));
602
        }
603
    }
604
  fprintf (file, " \n");
605
  for (var = BLOCK_VARS (scope); var; var = TREE_CHAIN (var))
606
    {
607
      bool used = false;
608
      var_ann_t ann;
609
 
610
      if ((ann = var_ann (var))
611
          && ann->used)
612
        used = true;
613
 
614
      fprintf (file, "%*s",indent, "");
615
      print_generic_decl (file, var, flags);
616
      fprintf (file, "%s\n", used ? "" : " (unused)");
617
    }
618
  for (i = 0; i < BLOCK_NUM_NONLOCALIZED_VARS (scope); i++)
619
    {
620
      fprintf (file, "%*s",indent, "");
621
      print_generic_decl (file, BLOCK_NONLOCALIZED_VAR (scope, i),
622
                          flags);
623
      fprintf (file, " (nonlocalized)\n");
624
    }
625
  for (t = BLOCK_SUBBLOCKS (scope); t ; t = BLOCK_CHAIN (t))
626
    dump_scope_block (file, indent + 2, t, flags);
627
  fprintf (file, "\n%*s}\n",indent, "");
628
}
629
 
630
/* Dump the tree of lexical scopes starting at SCOPE to stderr.  FLAGS
631
   is as in print_generic_expr.  */
632
 
633
void
634
debug_scope_block (tree scope, int flags)
635
{
636
  dump_scope_block (stderr, 0, scope, flags);
637
}
638
 
639
 
640
/* Dump the tree of lexical scopes of current_function_decl to FILE.
641
   FLAGS is as in print_generic_expr.  */
642
 
643
void
644
dump_scope_blocks (FILE *file, int flags)
645
{
646
  dump_scope_block (file, 0, DECL_INITIAL (current_function_decl), flags);
647
}
648
 
649
 
650
/* Dump the tree of lexical scopes of current_function_decl to stderr.
651
   FLAGS is as in print_generic_expr.  */
652
 
653
void
654
debug_scope_blocks (int flags)
655
{
656
  dump_scope_blocks (stderr, flags);
657
}
658
 
659
/* Remove local variables that are not referenced in the IL.  */
660
 
661
void
662
remove_unused_locals (void)
663
{
664
  basic_block bb;
665
  tree t, *cell;
666
  referenced_var_iterator rvi;
667
  var_ann_t ann;
668
  bitmap global_unused_vars = NULL;
669
 
670
  /* Removing declarations from lexical blocks when not optimizing is
671
     not only a waste of time, it actually causes differences in stack
672
     layout.  */
673
  if (!optimize)
674
    return;
675
 
676
  mark_scope_block_unused (DECL_INITIAL (current_function_decl));
677
 
678
  /* Assume all locals are unused.  */
679
  FOR_EACH_REFERENCED_VAR (t, rvi)
680
    var_ann (t)->used = false;
681
 
682
  /* Walk the CFG marking all referenced symbols.  */
683
  FOR_EACH_BB (bb)
684
    {
685
      gimple_stmt_iterator gsi;
686
      size_t i;
687
      edge_iterator ei;
688
      edge e;
689
 
690
      /* Walk the statements.  */
691
      for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
692
        {
693
          gimple stmt = gsi_stmt (gsi);
694
          tree b = gimple_block (stmt);
695
 
696
          if (is_gimple_debug (stmt))
697
            continue;
698
 
699
          if (b)
700
            TREE_USED (b) = true;
701
 
702
          for (i = 0; i < gimple_num_ops (stmt); i++)
703
            mark_all_vars_used (gimple_op_ptr (gsi_stmt (gsi), i), NULL);
704
        }
705
 
706
      for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
707
        {
708
          use_operand_p arg_p;
709
          ssa_op_iter i;
710
          tree def;
711
          gimple phi = gsi_stmt (gsi);
712
 
713
          /* No point processing globals.  */
714
          if (is_global_var (SSA_NAME_VAR (gimple_phi_result (phi))))
715
            continue;
716
 
717
          def = gimple_phi_result (phi);
718
          mark_all_vars_used (&def, NULL);
719
 
720
          FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_ALL_USES)
721
            {
722
              tree arg = USE_FROM_PTR (arg_p);
723
              mark_all_vars_used (&arg, NULL);
724
            }
725
        }
726
 
727
      FOR_EACH_EDGE (e, ei, bb->succs)
728
        if (e->goto_locus)
729
          TREE_USED (e->goto_block) = true;
730
    }
731
 
732
  cfun->has_local_explicit_reg_vars = false;
733
 
734
  /* Remove unmarked local vars from local_decls.  */
735
  for (cell = &cfun->local_decls; *cell; )
736
    {
737
      tree var = TREE_VALUE (*cell);
738
 
739
      if (TREE_CODE (var) != FUNCTION_DECL
740
          && (!(ann = var_ann (var))
741
              || !ann->used))
742
        {
743
          if (is_global_var (var))
744
            {
745
              if (global_unused_vars == NULL)
746
                global_unused_vars = BITMAP_ALLOC (NULL);
747
              bitmap_set_bit (global_unused_vars, DECL_UID (var));
748
            }
749
          else
750
            {
751
              *cell = TREE_CHAIN (*cell);
752
              continue;
753
            }
754
        }
755
      else if (TREE_CODE (var) == VAR_DECL
756
               && DECL_HARD_REGISTER (var)
757
               && !is_global_var (var))
758
        cfun->has_local_explicit_reg_vars = true;
759
      cell = &TREE_CHAIN (*cell);
760
    }
761
 
762
  /* Remove unmarked global vars from local_decls.  */
763
  if (global_unused_vars != NULL)
764
    {
765
      for (t = cfun->local_decls; t; t = TREE_CHAIN (t))
766
        {
767
          tree var = TREE_VALUE (t);
768
 
769
          if (TREE_CODE (var) == VAR_DECL
770
              && is_global_var (var)
771
              && (ann = var_ann (var)) != NULL
772
              && ann->used)
773
            mark_all_vars_used (&DECL_INITIAL (var), global_unused_vars);
774
        }
775
 
776
      for (cell = &cfun->local_decls; *cell; )
777
        {
778
          tree var = TREE_VALUE (*cell);
779
 
780
          if (TREE_CODE (var) == VAR_DECL
781
              && is_global_var (var)
782
              && bitmap_bit_p (global_unused_vars, DECL_UID (var)))
783
            *cell = TREE_CHAIN (*cell);
784
          else
785
            cell = &TREE_CHAIN (*cell);
786
        }
787
      BITMAP_FREE (global_unused_vars);
788
    }
789
 
790
  /* Remove unused variables from REFERENCED_VARs.  As a special
791
     exception keep the variables that are believed to be aliased.
792
     Those can't be easily removed from the alias sets and operand
793
     caches.  They will be removed shortly after the next may_alias
794
     pass is performed.  */
795
  FOR_EACH_REFERENCED_VAR (t, rvi)
796
    if (!is_global_var (t)
797
        && TREE_CODE (t) != PARM_DECL
798
        && TREE_CODE (t) != RESULT_DECL
799
        && !(ann = var_ann (t))->used
800
        && !ann->is_heapvar
801
        && !TREE_ADDRESSABLE (t))
802
      remove_referenced_var (t);
803
  remove_unused_scope_block_p (DECL_INITIAL (current_function_decl));
804
  if (dump_file && (dump_flags & TDF_DETAILS))
805
    {
806
      fprintf (dump_file, "Scope blocks after cleanups:\n");
807
      dump_scope_blocks (dump_file, dump_flags);
808
    }
809
}
810
 
811
 
812
/* Allocate and return a new live range information object base on MAP.  */
813
 
814
static tree_live_info_p
815
new_tree_live_info (var_map map)
816
{
817
  tree_live_info_p live;
818
  unsigned x;
819
 
820
  live = (tree_live_info_p) xmalloc (sizeof (struct tree_live_info_d));
821
  live->map = map;
822
  live->num_blocks = last_basic_block;
823
 
824
  live->livein = (bitmap *)xmalloc (last_basic_block * sizeof (bitmap));
825
  for (x = 0; x < (unsigned)last_basic_block; x++)
826
    live->livein[x] = BITMAP_ALLOC (NULL);
827
 
828
  live->liveout = (bitmap *)xmalloc (last_basic_block * sizeof (bitmap));
829
  for (x = 0; x < (unsigned)last_basic_block; x++)
830
    live->liveout[x] = BITMAP_ALLOC (NULL);
831
 
832
  live->work_stack = XNEWVEC (int, last_basic_block);
833
  live->stack_top = live->work_stack;
834
 
835
  live->global = BITMAP_ALLOC (NULL);
836
  return live;
837
}
838
 
839
 
840
/* Free storage for live range info object LIVE.  */
841
 
842
void
843
delete_tree_live_info (tree_live_info_p live)
844
{
845
  int x;
846
 
847
  BITMAP_FREE (live->global);
848
  free (live->work_stack);
849
 
850
  for (x = live->num_blocks - 1; x >= 0; x--)
851
    BITMAP_FREE (live->liveout[x]);
852
  free (live->liveout);
853
 
854
  for (x = live->num_blocks - 1; x >= 0; x--)
855
    BITMAP_FREE (live->livein[x]);
856
  free (live->livein);
857
 
858
  free (live);
859
}
860
 
861
 
862
/* Visit basic block BB and propagate any required live on entry bits from
863
   LIVE into the predecessors.  VISITED is the bitmap of visited blocks.
864
   TMP is a temporary work bitmap which is passed in to avoid reallocating
865
   it each time.  */
866
 
867
static void
868
loe_visit_block (tree_live_info_p live, basic_block bb, sbitmap visited,
869
                 bitmap tmp)
870
{
871
  edge e;
872
  bool change;
873
  edge_iterator ei;
874
  basic_block pred_bb;
875
  bitmap loe;
876
  gcc_assert (!TEST_BIT (visited, bb->index));
877
 
878
  SET_BIT (visited, bb->index);
879
  loe = live_on_entry (live, bb);
880
 
881
  FOR_EACH_EDGE (e, ei, bb->preds)
882
    {
883
      pred_bb = e->src;
884
      if (pred_bb == ENTRY_BLOCK_PTR)
885
        continue;
886
      /* TMP is variables live-on-entry from BB that aren't defined in the
887
         predecessor block.  This should be the live on entry vars to pred.
888
         Note that liveout is the DEFs in a block while live on entry is
889
         being calculated.  */
890
      bitmap_and_compl (tmp, loe, live->liveout[pred_bb->index]);
891
 
892
      /* Add these bits to live-on-entry for the pred. if there are any
893
         changes, and pred_bb has been visited already, add it to the
894
         revisit stack.  */
895
      change = bitmap_ior_into (live_on_entry (live, pred_bb), tmp);
896
      if (TEST_BIT (visited, pred_bb->index) && change)
897
        {
898
          RESET_BIT (visited, pred_bb->index);
899
          *(live->stack_top)++ = pred_bb->index;
900
        }
901
    }
902
}
903
 
904
 
905
/* Using LIVE, fill in all the live-on-entry blocks between the defs and uses
906
   of all the variables.  */
907
 
908
static void
909
live_worklist (tree_live_info_p live)
910
{
911
  unsigned b;
912
  basic_block bb;
913
  sbitmap visited = sbitmap_alloc (last_basic_block + 1);
914
  bitmap tmp = BITMAP_ALLOC (NULL);
915
 
916
  sbitmap_zero (visited);
917
 
918
  /* Visit all the blocks in reverse order and propagate live on entry values
919
     into the predecessors blocks.  */
920
  FOR_EACH_BB_REVERSE (bb)
921
    loe_visit_block (live, bb, visited, tmp);
922
 
923
  /* Process any blocks which require further iteration.  */
924
  while (live->stack_top != live->work_stack)
925
    {
926
      b = *--(live->stack_top);
927
      loe_visit_block (live, BASIC_BLOCK (b), visited, tmp);
928
    }
929
 
930
  BITMAP_FREE (tmp);
931
  sbitmap_free (visited);
932
}
933
 
934
 
935
/* Calculate the initial live on entry vector for SSA_NAME using immediate_use
936
   links.  Set the live on entry fields in LIVE.  Def's are marked temporarily
937
   in the liveout vector.  */
938
 
939
static void
940
set_var_live_on_entry (tree ssa_name, tree_live_info_p live)
941
{
942
  int p;
943
  gimple stmt;
944
  use_operand_p use;
945
  basic_block def_bb = NULL;
946
  imm_use_iterator imm_iter;
947
  bool global = false;
948
 
949
  p = var_to_partition (live->map, ssa_name);
950
  if (p == NO_PARTITION)
951
    return;
952
 
953
  stmt = SSA_NAME_DEF_STMT (ssa_name);
954
  if (stmt)
955
    {
956
      def_bb = gimple_bb (stmt);
957
      /* Mark defs in liveout bitmap temporarily.  */
958
      if (def_bb)
959
        bitmap_set_bit (live->liveout[def_bb->index], p);
960
    }
961
  else
962
    def_bb = ENTRY_BLOCK_PTR;
963
 
964
  /* Visit each use of SSA_NAME and if it isn't in the same block as the def,
965
     add it to the list of live on entry blocks.  */
966
  FOR_EACH_IMM_USE_FAST (use, imm_iter, ssa_name)
967
    {
968
      gimple use_stmt = USE_STMT (use);
969
      basic_block add_block = NULL;
970
 
971
      if (gimple_code (use_stmt) == GIMPLE_PHI)
972
        {
973
          /* Uses in PHI's are considered to be live at exit of the SRC block
974
             as this is where a copy would be inserted.  Check to see if it is
975
             defined in that block, or whether its live on entry.  */
976
          int index = PHI_ARG_INDEX_FROM_USE (use);
977
          edge e = gimple_phi_arg_edge (use_stmt, index);
978
          if (e->src != ENTRY_BLOCK_PTR)
979
            {
980
              if (e->src != def_bb)
981
                add_block = e->src;
982
            }
983
        }
984
      else if (is_gimple_debug (use_stmt))
985
        continue;
986
      else
987
        {
988
          /* If its not defined in this block, its live on entry.  */
989
          basic_block use_bb = gimple_bb (use_stmt);
990
          if (use_bb != def_bb)
991
            add_block = use_bb;
992
        }
993
 
994
      /* If there was a live on entry use, set the bit.  */
995
      if (add_block)
996
        {
997
          global = true;
998
          bitmap_set_bit (live->livein[add_block->index], p);
999
        }
1000
    }
1001
 
1002
  /* If SSA_NAME is live on entry to at least one block, fill in all the live
1003
     on entry blocks between the def and all the uses.  */
1004
  if (global)
1005
    bitmap_set_bit (live->global, p);
1006
}
1007
 
1008
 
1009
/* Calculate the live on exit vectors based on the entry info in LIVEINFO.  */
1010
 
1011
void
1012
calculate_live_on_exit (tree_live_info_p liveinfo)
1013
{
1014
  basic_block bb;
1015
  edge e;
1016
  edge_iterator ei;
1017
 
1018
  /* live on entry calculations used liveout vectors for defs, clear them.  */
1019
  FOR_EACH_BB (bb)
1020
    bitmap_clear (liveinfo->liveout[bb->index]);
1021
 
1022
  /* Set all the live-on-exit bits for uses in PHIs.  */
1023
  FOR_EACH_BB (bb)
1024
    {
1025
      gimple_stmt_iterator gsi;
1026
      size_t i;
1027
 
1028
      /* Mark the PHI arguments which are live on exit to the pred block.  */
1029
      for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1030
        {
1031
          gimple phi = gsi_stmt (gsi);
1032
          for (i = 0; i < gimple_phi_num_args (phi); i++)
1033
            {
1034
              tree t = PHI_ARG_DEF (phi, i);
1035
              int p;
1036
 
1037
              if (TREE_CODE (t) != SSA_NAME)
1038
                continue;
1039
 
1040
              p = var_to_partition (liveinfo->map, t);
1041
              if (p == NO_PARTITION)
1042
                continue;
1043
              e = gimple_phi_arg_edge (phi, i);
1044
              if (e->src != ENTRY_BLOCK_PTR)
1045
                bitmap_set_bit (liveinfo->liveout[e->src->index], p);
1046
            }
1047
        }
1048
 
1049
      /* Add each successors live on entry to this bock live on exit.  */
1050
      FOR_EACH_EDGE (e, ei, bb->succs)
1051
        if (e->dest != EXIT_BLOCK_PTR)
1052
          bitmap_ior_into (liveinfo->liveout[bb->index],
1053
                           live_on_entry (liveinfo, e->dest));
1054
    }
1055
}
1056
 
1057
 
1058
/* Given partition map MAP, calculate all the live on entry bitmaps for
1059
   each partition.  Return a new live info object.  */
1060
 
1061
tree_live_info_p
1062
calculate_live_ranges (var_map map)
1063
{
1064
  tree var;
1065
  unsigned i;
1066
  tree_live_info_p live;
1067
 
1068
  live = new_tree_live_info (map);
1069
  for (i = 0; i < num_var_partitions (map); i++)
1070
    {
1071
      var = partition_to_var (map, i);
1072
      if (var != NULL_TREE)
1073
        set_var_live_on_entry (var, live);
1074
    }
1075
 
1076
  live_worklist (live);
1077
 
1078
#ifdef ENABLE_CHECKING
1079
  verify_live_on_entry (live);
1080
#endif
1081
 
1082
  calculate_live_on_exit (live);
1083
  return live;
1084
}
1085
 
1086
 
1087
/* Output partition map MAP to file F.  */
1088
 
1089
void
1090
dump_var_map (FILE *f, var_map map)
1091
{
1092
  int t;
1093
  unsigned x, y;
1094
  int p;
1095
 
1096
  fprintf (f, "\nPartition map \n\n");
1097
 
1098
  for (x = 0; x < map->num_partitions; x++)
1099
    {
1100
      if (map->view_to_partition != NULL)
1101
        p = map->view_to_partition[x];
1102
      else
1103
        p = x;
1104
 
1105
      if (ssa_name (p) == NULL_TREE)
1106
        continue;
1107
 
1108
      t = 0;
1109
      for (y = 1; y < num_ssa_names; y++)
1110
        {
1111
          p = partition_find (map->var_partition, y);
1112
          if (map->partition_to_view)
1113
            p = map->partition_to_view[p];
1114
          if (p == (int)x)
1115
            {
1116
              if (t++ == 0)
1117
                {
1118
                  fprintf(f, "Partition %d (", x);
1119
                  print_generic_expr (f, partition_to_var (map, p), TDF_SLIM);
1120
                  fprintf (f, " - ");
1121
                }
1122
              fprintf (f, "%d ", y);
1123
            }
1124
        }
1125
      if (t != 0)
1126
        fprintf (f, ")\n");
1127
    }
1128
  fprintf (f, "\n");
1129
}
1130
 
1131
 
1132
/* Output live range info LIVE to file F, controlled by FLAG.  */
1133
 
1134
void
1135
dump_live_info (FILE *f, tree_live_info_p live, int flag)
1136
{
1137
  basic_block bb;
1138
  unsigned i;
1139
  var_map map = live->map;
1140
  bitmap_iterator bi;
1141
 
1142
  if ((flag & LIVEDUMP_ENTRY) && live->livein)
1143
    {
1144
      FOR_EACH_BB (bb)
1145
        {
1146
          fprintf (f, "\nLive on entry to BB%d : ", bb->index);
1147
          EXECUTE_IF_SET_IN_BITMAP (live->livein[bb->index], 0, i, bi)
1148
            {
1149
              print_generic_expr (f, partition_to_var (map, i), TDF_SLIM);
1150
              fprintf (f, "  ");
1151
            }
1152
          fprintf (f, "\n");
1153
        }
1154
    }
1155
 
1156
  if ((flag & LIVEDUMP_EXIT) && live->liveout)
1157
    {
1158
      FOR_EACH_BB (bb)
1159
        {
1160
          fprintf (f, "\nLive on exit from BB%d : ", bb->index);
1161
          EXECUTE_IF_SET_IN_BITMAP (live->liveout[bb->index], 0, i, bi)
1162
            {
1163
              print_generic_expr (f, partition_to_var (map, i), TDF_SLIM);
1164
              fprintf (f, "  ");
1165
            }
1166
          fprintf (f, "\n");
1167
        }
1168
    }
1169
}
1170
 
1171
 
1172
#ifdef ENABLE_CHECKING
1173
/* Verify that SSA_VAR is a non-virtual SSA_NAME.  */
1174
 
1175
void
1176
register_ssa_partition_check (tree ssa_var)
1177
{
1178
  gcc_assert (TREE_CODE (ssa_var) == SSA_NAME);
1179
  if (!is_gimple_reg (SSA_NAME_VAR (ssa_var)))
1180
    {
1181
      fprintf (stderr, "Illegally registering a virtual SSA name :");
1182
      print_generic_expr (stderr, ssa_var, TDF_SLIM);
1183
      fprintf (stderr, " in the SSA->Normal phase.\n");
1184
      internal_error ("SSA corruption");
1185
    }
1186
}
1187
 
1188
 
1189
/* Verify that the info in LIVE matches the current cfg.  */
1190
 
1191
static void
1192
verify_live_on_entry (tree_live_info_p live)
1193
{
1194
  unsigned i;
1195
  tree var;
1196
  gimple stmt;
1197
  basic_block bb;
1198
  edge e;
1199
  int num;
1200
  edge_iterator ei;
1201
  var_map map = live->map;
1202
 
1203
   /* Check for live on entry partitions and report those with a DEF in
1204
      the program. This will typically mean an optimization has done
1205
      something wrong.  */
1206
  bb = ENTRY_BLOCK_PTR;
1207
  num = 0;
1208
  FOR_EACH_EDGE (e, ei, bb->succs)
1209
    {
1210
      int entry_block = e->dest->index;
1211
      if (e->dest == EXIT_BLOCK_PTR)
1212
        continue;
1213
      for (i = 0; i < (unsigned)num_var_partitions (map); i++)
1214
        {
1215
          basic_block tmp;
1216
          tree d;
1217
          bitmap loe;
1218
          var = partition_to_var (map, i);
1219
          stmt = SSA_NAME_DEF_STMT (var);
1220
          tmp = gimple_bb (stmt);
1221
          d = gimple_default_def (cfun, SSA_NAME_VAR (var));
1222
 
1223
          loe = live_on_entry (live, e->dest);
1224
          if (loe && bitmap_bit_p (loe, i))
1225
            {
1226
              if (!gimple_nop_p (stmt))
1227
                {
1228
                  num++;
1229
                  print_generic_expr (stderr, var, TDF_SLIM);
1230
                  fprintf (stderr, " is defined ");
1231
                  if (tmp)
1232
                    fprintf (stderr, " in BB%d, ", tmp->index);
1233
                  fprintf (stderr, "by:\n");
1234
                  print_gimple_stmt (stderr, stmt, 0, TDF_SLIM);
1235
                  fprintf (stderr, "\nIt is also live-on-entry to entry BB %d",
1236
                           entry_block);
1237
                  fprintf (stderr, " So it appears to have multiple defs.\n");
1238
                }
1239
              else
1240
                {
1241
                  if (d != var)
1242
                    {
1243
                      num++;
1244
                      print_generic_expr (stderr, var, TDF_SLIM);
1245
                      fprintf (stderr, " is live-on-entry to BB%d ",
1246
                               entry_block);
1247
                      if (d)
1248
                        {
1249
                          fprintf (stderr, " but is not the default def of ");
1250
                          print_generic_expr (stderr, d, TDF_SLIM);
1251
                          fprintf (stderr, "\n");
1252
                        }
1253
                      else
1254
                        fprintf (stderr, " and there is no default def.\n");
1255
                    }
1256
                }
1257
            }
1258
          else
1259
            if (d == var)
1260
              {
1261
                /* The only way this var shouldn't be marked live on entry is
1262
                   if it occurs in a PHI argument of the block.  */
1263
                size_t z;
1264
                bool ok = false;
1265
                gimple_stmt_iterator gsi;
1266
                for (gsi = gsi_start_phis (e->dest);
1267
                     !gsi_end_p (gsi) && !ok;
1268
                     gsi_next (&gsi))
1269
                  {
1270
                    gimple phi = gsi_stmt (gsi);
1271
                    for (z = 0; z < gimple_phi_num_args (phi); z++)
1272
                      if (var == gimple_phi_arg_def (phi, z))
1273
                        {
1274
                          ok = true;
1275
                          break;
1276
                        }
1277
                  }
1278
                if (ok)
1279
                  continue;
1280
                num++;
1281
                print_generic_expr (stderr, var, TDF_SLIM);
1282
                fprintf (stderr, " is not marked live-on-entry to entry BB%d ",
1283
                         entry_block);
1284
                fprintf (stderr, "but it is a default def so it should be.\n");
1285
              }
1286
        }
1287
    }
1288
  gcc_assert (num <= 0);
1289
}
1290
#endif

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.