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

Subversion Repositories scarts

[/] [scarts/] [trunk/] [toolchain/] [scarts-gcc/] [gcc-4.1.1/] [gcc/] [ipa-reference.c] - Blame information for rev 12

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 12 jlechner
/* Callgraph based analysis of static variables.
2
   Copyright (C) 2004, 2005 Free Software Foundation, Inc.
3
   Contributed by Kenneth Zadeck <zadeck@naturalbridge.com>
4
 
5
This file is part of GCC.
6
 
7
GCC is free software; you can redistribute it and/or modify it under
8
the terms of the GNU General Public License as published by the Free
9
Software Foundation; either version 2, or (at your option) any later
10
version.
11
 
12
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13
WARRANTY; without even the implied warranty of MERCHANTABILITY or
14
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15
for more details.
16
 
17
You should have received a copy of the GNU General Public License
18
along with GCC; see the file COPYING.  If not, write to the Free
19
Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
20
02110-1301, USA.
21
*/
22
 
23
/* This file gathers information about how variables whose scope is
24
   confined to the compilation unit are used.
25
 
26
   There are two categories of information produced by this pass:
27
 
28
   1) The addressable (TREE_ADDRESSABLE) bit and readonly
29
   (TREE_READONLY) bit associated with these variables is properly set
30
   based on scanning all of the code withing the compilation unit.
31
 
32
   2) The transitive call site specific clobber effects are computed
33
   for the variables whose scope is contained within this compilation
34
   unit.
35
 
36
   First each function and static variable initialization is analyzed
37
   to determine which local static variables are either read, written,
38
   or have their address taken.  Any local static that has its address
39
   taken is removed from consideration.  Once the local read and
40
   writes are determined, a transitive closure of this information is
41
   performed over the call graph to determine the worst case set of
42
   side effects of each call.  In later parts of the compiler, these
43
   local and global sets are examined to make the call clobbering less
44
   traumatic, promote some statics to registers, and improve aliasing
45
   information.
46
 
47
   Currently must be run after inlining decisions have been made since
48
   otherwise, the local sets will not contain information that is
49
   consistent with post inlined state.  The global sets are not prone
50
   to this problem since they are by definition transitive.
51
*/
52
 
53
#include "config.h"
54
#include "system.h"
55
#include "coretypes.h"
56
#include "tm.h"
57
#include "tree.h"
58
#include "tree-flow.h"
59
#include "tree-inline.h"
60
#include "tree-pass.h"
61
#include "langhooks.h"
62
#include "pointer-set.h"
63
#include "ggc.h"
64
#include "ipa-utils.h"
65
#include "ipa-reference.h"
66
#include "c-common.h"
67
#include "tree-gimple.h"
68
#include "cgraph.h"
69
#include "output.h"
70
#include "flags.h"
71
#include "timevar.h"
72
#include "diagnostic.h"
73
#include "langhooks.h"
74
 
75
/* This splay tree contains all of the static variables that are
76
   being considered by the compilation level alias analysis.  For
77
   module_at_a_time compilation, this is the set of static but not
78
   public variables.  Any variables that either have their address
79
   taken or participate in otherwise unsavory operations are deleted
80
   from this list.  */
81
static GTY((param1_is(int), param2_is(tree)))
82
     splay_tree reference_vars_to_consider;
83
 
84
/* This bitmap is used to knock out the module static variables whose
85
   addresses have been taken and passed around.  */
86
static bitmap module_statics_escape;
87
 
88
/* This bitmap is used to knock out the module static variables that
89
   are not readonly.  */
90
static bitmap module_statics_written;
91
 
92
/* A bit is set for every module static we are considering.  This is
93
   ored into the local info when asm code is found that clobbers all
94
   memory. */
95
static bitmap all_module_statics;
96
 
97
static struct pointer_set_t *visited_nodes;
98
 
99
static bitmap_obstack ipa_obstack;
100
 
101
enum initialization_status_t
102
{
103
  UNINITIALIZED,
104
  RUNNING,
105
  FINISHED
106
};
107
 
108
tree memory_identifier_string;
109
 
110
/* Return the ipa_reference_vars structure starting from the cgraph NODE.  */
111
static inline ipa_reference_vars_info_t
112
get_reference_vars_info_from_cgraph (struct cgraph_node * node)
113
{
114
  return get_var_ann (node->decl)->reference_vars_info;
115
}
116
 
117
/* Get a bitmap that contains all of the locally referenced static
118
   variables for function FN.  */
119
static ipa_reference_local_vars_info_t
120
get_local_reference_vars_info (tree fn)
121
{
122
  ipa_reference_vars_info_t info = get_var_ann (fn)->reference_vars_info;
123
 
124
  if (info)
125
    return info->local;
126
  else
127
    /* This phase was not run.  */
128
    return NULL;
129
}
130
 
131
/* Get a bitmap that contains all of the globally referenced static
132
   variables for function FN.  */
133
 
134
static ipa_reference_global_vars_info_t
135
get_global_reference_vars_info (tree fn)
136
{
137
  ipa_reference_vars_info_t info = get_var_ann (fn)->reference_vars_info;
138
 
139
  if (info)
140
    return info->global;
141
  else
142
    /* This phase was not run.  */
143
    return NULL;
144
}
145
 
146
/* Return a bitmap indexed by VAR_DECL uid for the static variables
147
   that may be read locally by the execution of the function fn.
148
   Returns NULL if no data is available.  */
149
 
150
bitmap
151
ipa_reference_get_read_local (tree fn)
152
{
153
  ipa_reference_local_vars_info_t l = get_local_reference_vars_info (fn);
154
  if (l)
155
    return l->statics_read;
156
  else
157
    return NULL;
158
}
159
 
160
/* Return a bitmap indexed by VAR_DECL uid for the static variables
161
   that may be written locally by the execution of the function fn.
162
   Returns NULL if no data is available.  */
163
 
164
bitmap
165
ipa_reference_get_written_local (tree fn)
166
{
167
  ipa_reference_local_vars_info_t l = get_local_reference_vars_info (fn);
168
  if (l)
169
    return l->statics_written;
170
  else
171
    return NULL;
172
}
173
 
174
/* Return a bitmap indexed by VAR_DECL uid for the static variables
175
   that are read during the execution of the function FN.  Returns
176
   NULL if no data is available.  */
177
 
178
bitmap
179
ipa_reference_get_read_global (tree fn)
180
{
181
  ipa_reference_global_vars_info_t g = get_global_reference_vars_info (fn);
182
  if (g)
183
    return g->statics_read;
184
  else
185
    return NULL;
186
}
187
 
188
/* Return a bitmap indexed by VAR_DECL uid for the static variables
189
   that are written during the execution of the function FN.  Note
190
   that variables written may or may not be read during the function
191
   call.  Returns NULL if no data is available.  */
192
 
193
bitmap
194
ipa_reference_get_written_global (tree fn)
195
{
196
  ipa_reference_global_vars_info_t g = get_global_reference_vars_info (fn);
197
  if (g)
198
    return g->statics_written;
199
  else
200
    return NULL;
201
}
202
 
203
/* Return a bitmap indexed by_DECL_UID uid for the static variables
204
   that are not read during the execution of the function FN.  Returns
205
   NULL if no data is available.  */
206
 
207
bitmap
208
ipa_reference_get_not_read_global (tree fn)
209
{
210
  ipa_reference_global_vars_info_t g = get_global_reference_vars_info (fn);
211
  if (g)
212
    return g->statics_not_read;
213
  else
214
    return NULL;
215
}
216
 
217
/* Return a bitmap indexed by DECL_UID uid for the static variables
218
   that are not written during the execution of the function FN.  Note
219
   that variables written may or may not be read during the function
220
   call.  Returns NULL if no data is available.  */
221
 
222
bitmap
223
ipa_reference_get_not_written_global (tree fn)
224
{
225
  ipa_reference_global_vars_info_t g = get_global_reference_vars_info (fn);
226
  if (g)
227
    return g->statics_not_written;
228
  else
229
    return NULL;
230
}
231
 
232
 
233
 
234
/* Add VAR to all_module_statics and the two
235
   reference_vars_to_consider* sets.  */
236
 
237
static inline void
238
add_static_var (tree var)
239
{
240
  int uid = DECL_UID (var);
241
  if (!bitmap_bit_p (all_module_statics, uid))
242
    {
243
      splay_tree_insert (reference_vars_to_consider,
244
                         uid, (splay_tree_value)var);
245
      bitmap_set_bit (all_module_statics, uid);
246
    }
247
}
248
 
249
/* Return true if the variable T is the right kind of static variable to
250
   perform compilation unit scope escape analysis.  */
251
 
252
static inline bool
253
has_proper_scope_for_analysis (tree t)
254
{
255
  /* If the variable has the "used" attribute, treat it as if it had a
256
     been touched by the devil.  */
257
  if (lookup_attribute ("used", DECL_ATTRIBUTES (t)))
258
    return false;
259
 
260
  /* Do not want to do anything with volatile except mark any
261
     function that uses one to be not const or pure.  */
262
  if (TREE_THIS_VOLATILE (t))
263
    return false;
264
 
265
  /* Do not care about a local automatic that is not static.  */
266
  if (!TREE_STATIC (t) && !DECL_EXTERNAL (t))
267
    return false;
268
 
269
  if (DECL_EXTERNAL (t) || TREE_PUBLIC (t))
270
    return false;
271
 
272
  /* This is a variable we care about.  Check if we have seen it
273
     before, and if not add it the set of variables we care about.  */
274
  if (!bitmap_bit_p (all_module_statics, DECL_UID (t)))
275
    add_static_var (t);
276
 
277
  return true;
278
}
279
 
280
/* If T is a VAR_DECL for a static that we are interested in, add the
281
   uid to the bitmap.  */
282
 
283
static void
284
check_operand (ipa_reference_local_vars_info_t local,
285
               tree t, bool checking_write)
286
{
287
  if (!t) return;
288
 
289
  if ((TREE_CODE (t) == VAR_DECL)
290
      && (has_proper_scope_for_analysis (t)))
291
    {
292
      if (checking_write)
293
        {
294
          if (local)
295
            bitmap_set_bit (local->statics_written, DECL_UID (t));
296
          /* Mark the write so we can tell which statics are
297
             readonly.  */
298
          bitmap_set_bit (module_statics_written, DECL_UID (t));
299
        }
300
      else if (local)
301
        bitmap_set_bit (local->statics_read, DECL_UID (t));
302
    }
303
}
304
 
305
/* Examine tree T for references to static variables. All internal
306
   references like array references or indirect references are added
307
   to the READ_BM. Direct references are added to either READ_BM or
308
   WRITE_BM depending on the value of CHECKING_WRITE.   */
309
 
310
static void
311
check_tree (ipa_reference_local_vars_info_t local, tree t, bool checking_write)
312
{
313
  if ((TREE_CODE (t) == EXC_PTR_EXPR) || (TREE_CODE (t) == FILTER_EXPR))
314
    return;
315
 
316
  while (TREE_CODE (t) == REALPART_EXPR
317
         || TREE_CODE (t) == IMAGPART_EXPR
318
         || handled_component_p (t))
319
    {
320
      if (TREE_CODE (t) == ARRAY_REF)
321
        check_operand (local, TREE_OPERAND (t, 1), false);
322
      t = TREE_OPERAND (t, 0);
323
    }
324
 
325
  /* The bottom of an indirect reference can only be read, not
326
     written.  So just recurse and whatever we find, check it against
327
     the read bitmaps.  */
328
 
329
  /*  if (INDIRECT_REF_P (t) || TREE_CODE (t) == MEM_REF) */
330
  /* FIXME when we have array_ref's of pointers.  */
331
  if (INDIRECT_REF_P (t))
332
    check_tree (local, TREE_OPERAND (t, 0), false);
333
 
334
  if (SSA_VAR_P (t))
335
    check_operand (local, t, checking_write);
336
}
337
 
338
/* Scan tree T to see if there are any addresses taken in within T.  */
339
 
340
static void
341
look_for_address_of (tree t)
342
{
343
  if (TREE_CODE (t) == ADDR_EXPR)
344
    {
345
      tree x = get_base_var (t);
346
      if (TREE_CODE (x) == VAR_DECL)
347
        if (has_proper_scope_for_analysis (x))
348
          bitmap_set_bit (module_statics_escape, DECL_UID (x));
349
    }
350
}
351
 
352
/* Check to see if T is a read or address of operation on a static var
353
   we are interested in analyzing.  LOCAL is passed in to get access
354
   to its bit vectors.  Local is NULL if this is called from a static
355
   initializer.  */
356
 
357
static void
358
check_rhs_var (ipa_reference_local_vars_info_t local, tree t)
359
{
360
  look_for_address_of (t);
361
 
362
  if (local == NULL)
363
    return;
364
 
365
  check_tree(local, t, false);
366
}
367
 
368
/* Check to see if T is an assignment to a static var we are
369
   interested in analyzing.  LOCAL is passed in to get access to its bit
370
   vectors.  */
371
 
372
static void
373
check_lhs_var (ipa_reference_local_vars_info_t local, tree t)
374
{
375
  if (local == NULL)
376
    return;
377
 
378
  check_tree(local, t, true);
379
}
380
 
381
/* This is a scaled down version of get_asm_expr_operands from
382
   tree_ssa_operands.c.  The version there runs much later and assumes
383
   that aliasing information is already available. Here we are just
384
   trying to find if the set of inputs and outputs contain references
385
   or address of operations to local static variables.  FN is the
386
   function being analyzed and STMT is the actual asm statement.  */
387
 
388
static void
389
get_asm_expr_operands (ipa_reference_local_vars_info_t local, tree stmt)
390
{
391
  int noutputs = list_length (ASM_OUTPUTS (stmt));
392
  const char **oconstraints
393
    = (const char **) alloca ((noutputs) * sizeof (const char *));
394
  int i;
395
  tree link;
396
  const char *constraint;
397
  bool allows_mem, allows_reg, is_inout;
398
 
399
  for (i=0, link = ASM_OUTPUTS (stmt); link; ++i, link = TREE_CHAIN (link))
400
    {
401
      oconstraints[i] = constraint
402
        = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
403
      parse_output_constraint (&constraint, i, 0, 0,
404
                               &allows_mem, &allows_reg, &is_inout);
405
 
406
      check_lhs_var (local, TREE_VALUE (link));
407
    }
408
 
409
  for (link = ASM_INPUTS (stmt); link; link = TREE_CHAIN (link))
410
    {
411
      constraint
412
        = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
413
      parse_input_constraint (&constraint, 0, 0, noutputs, 0,
414
                              oconstraints, &allows_mem, &allows_reg);
415
 
416
      check_rhs_var (local, TREE_VALUE (link));
417
    }
418
 
419
  for (link = ASM_CLOBBERS (stmt); link; link = TREE_CHAIN (link))
420
    if (simple_cst_equal(TREE_VALUE (link), memory_identifier_string) == 1)
421
      {
422
        /* Abandon all hope, ye who enter here. */
423
        local->calls_read_all = true;
424
        local->calls_write_all = true;
425
      }
426
}
427
 
428
/* Check the parameters of a function call from CALLER to CALL_EXPR to
429
   see if any of them are static vars.  Also check to see if this is
430
   either an indirect call, a call outside the compilation unit, or
431
   has special attributes that effect the clobbers.  The caller
432
   parameter is the tree node for the caller and the second operand is
433
   the tree node for the entire call expression.  */
434
 
435
static void
436
check_call (ipa_reference_local_vars_info_t local, tree call_expr)
437
{
438
  int flags = call_expr_flags (call_expr);
439
  tree operand_list = TREE_OPERAND (call_expr, 1);
440
  tree operand;
441
  tree callee_t = get_callee_fndecl (call_expr);
442
  enum availability avail = AVAIL_NOT_AVAILABLE;
443
 
444
  for (operand = operand_list;
445
       operand != NULL_TREE;
446
       operand = TREE_CHAIN (operand))
447
    {
448
      tree argument = TREE_VALUE (operand);
449
      check_rhs_var (local, argument);
450
    }
451
 
452
  if (callee_t)
453
    {
454
      struct cgraph_node* callee = cgraph_node(callee_t);
455
      avail = cgraph_function_body_availability (callee);
456
    }
457
 
458
  if (avail == AVAIL_NOT_AVAILABLE || avail == AVAIL_OVERWRITABLE)
459
    if (local)
460
      {
461
        if (flags & ECF_PURE)
462
          local->calls_read_all = true;
463
        else
464
          {
465
            local->calls_read_all = true;
466
            local->calls_write_all = true;
467
          }
468
      }
469
}
470
 
471
/* TP is the part of the tree currently under the microscope.
472
   WALK_SUBTREES is part of the walk_tree api but is unused here.
473
   DATA is cgraph_node of the function being walked.  */
474
 
475
/* FIXME: When this is converted to run over SSA form, this code
476
   should be converted to use the operand scanner.  */
477
 
478
static tree
479
scan_for_static_refs (tree *tp,
480
                      int *walk_subtrees,
481
                      void *data)
482
{
483
  struct cgraph_node *fn = data;
484
  tree t = *tp;
485
  ipa_reference_local_vars_info_t local = NULL;
486
  if (fn)
487
    local = get_reference_vars_info_from_cgraph (fn)->local;
488
 
489
  switch (TREE_CODE (t))
490
    {
491
    case VAR_DECL:
492
      if (DECL_INITIAL (t))
493
        walk_tree (&DECL_INITIAL (t), scan_for_static_refs, fn, visited_nodes);
494
      *walk_subtrees = 0;
495
      break;
496
 
497
    case MODIFY_EXPR:
498
      {
499
        /* First look on the lhs and see what variable is stored to */
500
        tree lhs = TREE_OPERAND (t, 0);
501
        tree rhs = TREE_OPERAND (t, 1);
502
        check_lhs_var (local, lhs);
503
 
504
        /* For the purposes of figuring out what the cast affects */
505
 
506
        /* Next check the operands on the rhs to see if they are ok. */
507
        switch (TREE_CODE_CLASS (TREE_CODE (rhs)))
508
          {
509
          case tcc_binary:
510
            {
511
              tree op0 = TREE_OPERAND (rhs, 0);
512
              tree op1 = TREE_OPERAND (rhs, 1);
513
              check_rhs_var (local, op0);
514
              check_rhs_var (local, op1);
515
            }
516
            break;
517
          case tcc_unary:
518
            {
519
              tree op0 = TREE_OPERAND (rhs, 0);
520
              check_rhs_var (local, op0);
521
            }
522
 
523
            break;
524
          case tcc_reference:
525
            check_rhs_var (local, rhs);
526
            break;
527
          case tcc_declaration:
528
            check_rhs_var (local, rhs);
529
            break;
530
          case tcc_expression:
531
            switch (TREE_CODE (rhs))
532
              {
533
              case ADDR_EXPR:
534
                check_rhs_var (local, rhs);
535
                break;
536
              case CALL_EXPR:
537
                check_call (local, rhs);
538
                break;
539
              default:
540
                break;
541
              }
542
            break;
543
          default:
544
            break;
545
          }
546
        *walk_subtrees = 0;
547
      }
548
      break;
549
 
550
    case ADDR_EXPR:
551
      /* This case is here to find addresses on rhs of constructors in
552
         decl_initial of static variables. */
553
      check_rhs_var (local, t);
554
      *walk_subtrees = 0;
555
      break;
556
 
557
    case LABEL_EXPR:
558
      if (DECL_NONLOCAL (TREE_OPERAND (t, 0)))
559
        {
560
          /* Target of long jump. */
561
          local->calls_read_all = true;
562
          local->calls_write_all = true;
563
        }
564
      break;
565
 
566
    case CALL_EXPR:
567
      check_call (local, t);
568
      *walk_subtrees = 0;
569
      break;
570
 
571
    case ASM_EXPR:
572
      get_asm_expr_operands (local, t);
573
      *walk_subtrees = 0;
574
      break;
575
 
576
    default:
577
      break;
578
    }
579
  return NULL;
580
}
581
 
582
 
583
/* Lookup the tree node for the static variable that has UID.  */
584
static tree
585
get_static_decl (int index)
586
{
587
  splay_tree_node stn =
588
    splay_tree_lookup (reference_vars_to_consider, index);
589
  if (stn)
590
    return (tree)stn->value;
591
  return NULL;
592
}
593
 
594
/* Lookup the tree node for the static variable that has UID and
595
   convert the name to a string for debugging.  */
596
 
597
static const char *
598
get_static_name (int index)
599
{
600
  splay_tree_node stn =
601
    splay_tree_lookup (reference_vars_to_consider, index);
602
  if (stn)
603
    return lang_hooks.decl_printable_name ((tree)(stn->value), 2);
604
  return NULL;
605
}
606
 
607
/* Or in all of the bits from every callee into X, the caller's, bit
608
   vector.  There are several cases to check to avoid the sparse
609
   bitmap oring.  */
610
 
611
static void
612
propagate_bits (struct cgraph_node *x)
613
{
614
  ipa_reference_vars_info_t x_info = get_reference_vars_info_from_cgraph (x);
615
  ipa_reference_global_vars_info_t x_global = x_info->global;
616
 
617
  struct cgraph_edge *e;
618
  for (e = x->callees; e; e = e->next_callee)
619
    {
620
      struct cgraph_node *y = e->callee;
621
 
622
      /* Only look at the master nodes and skip external nodes.  */
623
      y = cgraph_master_clone (y);
624
      if (y)
625
        {
626
          if (get_reference_vars_info_from_cgraph (y))
627
            {
628
              ipa_reference_vars_info_t y_info = get_reference_vars_info_from_cgraph (y);
629
              ipa_reference_global_vars_info_t y_global = y_info->global;
630
 
631
              if (x_global->statics_read
632
                  != all_module_statics)
633
                {
634
                  if (y_global->statics_read
635
                      == all_module_statics)
636
                    {
637
                      BITMAP_FREE (x_global->statics_read);
638
                      x_global->statics_read
639
                        = all_module_statics;
640
                    }
641
                  /* Skip bitmaps that are pointer equal to node's bitmap
642
                     (no reason to spin within the cycle).  */
643
                  else if (x_global->statics_read
644
                           != y_global->statics_read)
645
                    bitmap_ior_into (x_global->statics_read,
646
                                     y_global->statics_read);
647
                }
648
 
649
              if (x_global->statics_written
650
                  != all_module_statics)
651
                {
652
                  if (y_global->statics_written
653
                      == all_module_statics)
654
                    {
655
                      BITMAP_FREE (x_global->statics_written);
656
                      x_global->statics_written
657
                        = all_module_statics;
658
                    }
659
                  /* Skip bitmaps that are pointer equal to node's bitmap
660
                     (no reason to spin within the cycle).  */
661
                  else if (x_global->statics_written
662
                           != y_global->statics_written)
663
                    bitmap_ior_into (x_global->statics_written,
664
                                     y_global->statics_written);
665
                }
666
            }
667
          else
668
            {
669
              gcc_unreachable ();
670
            }
671
        }
672
    }
673
}
674
 
675
/* Look at all of the callees of X to see which ones represent inlined
676
   calls.  For each of these callees, merge their local info into
677
   TARGET and check their children recursively.
678
 
679
   This function goes away when Jan changes the inliner and IPA
680
   analysis so that this is not run between the time when inlining
681
   decisions are made and when the inlining actually occurs.  */
682
 
683
static void
684
merge_callee_local_info (struct cgraph_node *target,
685
                         struct cgraph_node *x)
686
{
687
  struct cgraph_edge *e;
688
  ipa_reference_local_vars_info_t x_l =
689
    get_reference_vars_info_from_cgraph (target)->local;
690
 
691
  /* Make the world safe for tail recursion.  */
692
  struct ipa_dfs_info *node_info = x->aux;
693
 
694
  if (node_info->aux)
695
    return;
696
 
697
  node_info->aux = x;
698
 
699
  for (e = x->callees; e; e = e->next_callee)
700
    {
701
      struct cgraph_node *y = e->callee;
702
      if (y->global.inlined_to)
703
        {
704
          ipa_reference_vars_info_t y_info;
705
          ipa_reference_local_vars_info_t y_l;
706
          struct cgraph_node* orig_y = y;
707
 
708
          y = cgraph_master_clone (y);
709
          if (y)
710
            {
711
              y_info = get_reference_vars_info_from_cgraph (y);
712
              y_l = y_info->local;
713
              if (x_l != y_l)
714
                {
715
                  bitmap_ior_into (x_l->statics_read,
716
                                   y_l->statics_read);
717
                  bitmap_ior_into (x_l->statics_written,
718
                                   y_l->statics_written);
719
                }
720
              x_l->calls_read_all |= y_l->calls_read_all;
721
              x_l->calls_write_all |= y_l->calls_write_all;
722
              merge_callee_local_info (target, y);
723
            }
724
          else
725
            {
726
              fprintf(stderr, "suspect inlining of ");
727
              dump_cgraph_node (stderr, orig_y);
728
              fprintf(stderr, "\ninto ");
729
              dump_cgraph_node (stderr, target);
730
              dump_cgraph (stderr);
731
              gcc_assert(false);
732
            }
733
        }
734
    }
735
 
736
  node_info->aux = NULL;
737
}
738
 
739
/* The init routine for analyzing global static variable usage.  See
740
   comments at top for description.  */
741
static void
742
ipa_init (void)
743
{
744
  memory_identifier_string = build_string(7, "memory");
745
 
746
  reference_vars_to_consider =
747
    splay_tree_new_ggc (splay_tree_compare_ints);
748
 
749
  bitmap_obstack_initialize (&ipa_obstack);
750
  module_statics_escape = BITMAP_ALLOC (&ipa_obstack);
751
  module_statics_written = BITMAP_ALLOC (&ipa_obstack);
752
  all_module_statics = BITMAP_ALLOC (&ipa_obstack);
753
 
754
  /* There are some shared nodes, in particular the initializers on
755
     static declarations.  We do not need to scan them more than once
756
     since all we would be interested in are the addressof
757
     operations.  */
758
  visited_nodes = pointer_set_create ();
759
}
760
 
761
/* Check out the rhs of a static or global initialization VNODE to see
762
   if any of them contain addressof operations.  Note that some of
763
   these variables may  not even be referenced in the code in this
764
   compilation unit but their right hand sides may contain references
765
   to variables defined within this unit.  */
766
 
767
static void
768
analyze_variable (struct cgraph_varpool_node *vnode)
769
{
770
  tree global = vnode->decl;
771
  if (TREE_CODE (global) == VAR_DECL)
772
    {
773
      if (DECL_INITIAL (global))
774
        walk_tree (&DECL_INITIAL (global), scan_for_static_refs,
775
                   NULL, visited_nodes);
776
    }
777
  else gcc_unreachable ();
778
}
779
 
780
/* This is the main routine for finding the reference patterns for
781
   global variables within a function FN.  */
782
 
783
static void
784
analyze_function (struct cgraph_node *fn)
785
{
786
  ipa_reference_vars_info_t info
787
    = xcalloc (1, sizeof (struct ipa_reference_vars_info_d));
788
  ipa_reference_local_vars_info_t l
789
    = xcalloc (1, sizeof (struct ipa_reference_local_vars_info_d));
790
  tree decl = fn->decl;
791
 
792
  /* Add the info to the tree's annotation.  */
793
  get_var_ann (fn->decl)->reference_vars_info = info;
794
 
795
  info->local = l;
796
  l->statics_read = BITMAP_ALLOC (&ipa_obstack);
797
  l->statics_written = BITMAP_ALLOC (&ipa_obstack);
798
 
799
  if (dump_file)
800
    fprintf (dump_file, "\n local analysis of %s\n", cgraph_node_name (fn));
801
 
802
  {
803
    struct function *this_cfun = DECL_STRUCT_FUNCTION (decl);
804
    basic_block this_block;
805
 
806
    FOR_EACH_BB_FN (this_block, this_cfun)
807
      {
808
        block_stmt_iterator bsi;
809
        for (bsi = bsi_start (this_block); !bsi_end_p (bsi); bsi_next (&bsi))
810
          walk_tree (bsi_stmt_ptr (bsi), scan_for_static_refs,
811
                     fn, visited_nodes);
812
      }
813
  }
814
 
815
  /* There may be const decls with interesting right hand sides.  */
816
  if (DECL_STRUCT_FUNCTION (decl))
817
    {
818
      tree step;
819
      for (step = DECL_STRUCT_FUNCTION (decl)->unexpanded_var_list;
820
           step;
821
           step = TREE_CHAIN (step))
822
        {
823
          tree var = TREE_VALUE (step);
824
          if (TREE_CODE (var) == VAR_DECL
825
              && DECL_INITIAL (var)
826
              && !TREE_STATIC (var))
827
            walk_tree (&DECL_INITIAL (var), scan_for_static_refs,
828
                       fn, visited_nodes);
829
        }
830
    }
831
}
832
 
833
/* If FN is avail == AVAIL_OVERWRITABLE, replace the effects bit
834
   vectors with worst case bit vectors.  We had to analyze it above to
835
   find out if it took the address of any statics. However, now that
836
   we know that, we can get rid of all of the other side effects.  */
837
 
838
static void
839
clean_function (struct cgraph_node *fn)
840
{
841
  ipa_reference_vars_info_t info = get_reference_vars_info_from_cgraph (fn);
842
  ipa_reference_local_vars_info_t l = info->local;
843
  ipa_reference_global_vars_info_t g = info->global;
844
 
845
  if (l)
846
    {
847
      if (l->statics_read
848
          && l->statics_read != all_module_statics)
849
        BITMAP_FREE (l->statics_read);
850
      if (l->statics_written
851
          &&l->statics_written != all_module_statics)
852
        BITMAP_FREE (l->statics_written);
853
      free (l);
854
    }
855
 
856
  if (g)
857
    {
858
      if (g->statics_read
859
          && g->statics_read != all_module_statics)
860
        BITMAP_FREE (g->statics_read);
861
 
862
      if (g->statics_written
863
          && g->statics_written != all_module_statics)
864
        BITMAP_FREE (g->statics_written);
865
 
866
      if (g->statics_not_read
867
          && g->statics_not_read != all_module_statics)
868
        BITMAP_FREE (g->statics_not_read);
869
 
870
      if (g->statics_not_written
871
          && g->statics_not_written != all_module_statics)
872
        BITMAP_FREE (g->statics_not_written);
873
      free (g);
874
    }
875
 
876
 
877
  free (get_var_ann (fn->decl)->reference_vars_info);
878
  get_var_ann (fn->decl)->reference_vars_info = NULL;
879
}
880
 
881
 
882
/* Produce the global information by preforming a transitive closure
883
   on the local information that was produced by ipa_analyze_function
884
   and ipa_analyze_variable.  */
885
 
886
static void
887
static_execute (void)
888
{
889
  struct cgraph_node *node;
890
  struct cgraph_varpool_node *vnode;
891
  struct cgraph_node *w;
892
  struct cgraph_node **order =
893
    xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
894
  int order_pos = order_pos = ipa_utils_reduced_inorder (order, false, true);
895
  int i;
896
 
897
  ipa_init ();
898
 
899
  /* Process all of the variables first.  */
900
  for (vnode = cgraph_varpool_nodes_queue; vnode; vnode = vnode->next_needed)
901
    analyze_variable (vnode);
902
 
903
  /* Process all of the functions next.
904
 
905
     We do not want to process any of the clones so we check that this
906
     is a master clone.  However, we do need to process any
907
     AVAIL_OVERWRITABLE functions (these are never clones) because
908
     they may cause a static variable to escape.  The code that can
909
     overwrite such a function cannot access the statics because it
910
     would not be in the same compilation unit.  When the analysis is
911
     finished, the computed information of these AVAIL_OVERWRITABLE is
912
     replaced with worst case info.
913
  */
914
  for (node = cgraph_nodes; node; node = node->next)
915
    if (node->analyzed
916
        && (cgraph_is_master_clone (node)
917
            || (cgraph_function_body_availability (node)
918
                == AVAIL_OVERWRITABLE)))
919
      analyze_function (node);
920
 
921
  pointer_set_destroy (visited_nodes);
922
  visited_nodes = NULL;
923
  if (dump_file)
924
    dump_cgraph (dump_file);
925
 
926
  /* Prune out the variables that were found to behave badly
927
     (i.e. have their address taken).  */
928
  {
929
    unsigned int index;
930
    bitmap_iterator bi;
931
    bitmap module_statics_readonly = BITMAP_ALLOC (&ipa_obstack);
932
    bitmap module_statics_const = BITMAP_ALLOC (&ipa_obstack);
933
    bitmap bm_temp = BITMAP_ALLOC (&ipa_obstack);
934
 
935
    EXECUTE_IF_SET_IN_BITMAP (module_statics_escape, 0, index, bi)
936
      {
937
        splay_tree_remove (reference_vars_to_consider, index);
938
      }
939
 
940
    bitmap_and_compl_into (all_module_statics,
941
                           module_statics_escape);
942
 
943
    bitmap_and_compl (module_statics_readonly, all_module_statics,
944
                      module_statics_written);
945
 
946
    /* If the address is not taken, we can unset the addressable bit
947
       on this variable.  */
948
    EXECUTE_IF_SET_IN_BITMAP (all_module_statics, 0, index, bi)
949
      {
950
        tree var = get_static_decl (index);
951
        TREE_ADDRESSABLE (var) = 0;
952
        if (dump_file)
953
          fprintf (dump_file, "Not TREE_ADDRESSABLE var %s\n",
954
                   get_static_name (index));
955
      }
956
 
957
    /* If the variable is never written, we can set the TREE_READONLY
958
       flag.  Additionally if it has a DECL_INITIAL that is made up of
959
       constants we can treat the entire global as a constant.  */
960
 
961
    bitmap_and_compl (module_statics_readonly, all_module_statics,
962
                      module_statics_written);
963
    EXECUTE_IF_SET_IN_BITMAP (module_statics_readonly, 0, index, bi)
964
      {
965
        tree var = get_static_decl (index);
966
 
967
        /* Ignore variables in named sections - changing TREE_READONLY
968
           changes the section flags, potentially causing conflicts with
969
           other variables in the same named section.  */
970
        if (DECL_SECTION_NAME (var) == NULL_TREE)
971
          {
972
            TREE_READONLY (var) = 1;
973
            if (dump_file)
974
              fprintf (dump_file, "read-only var %s\n",
975
                       get_static_name (index));
976
          }
977
        if (DECL_INITIAL (var)
978
            && is_gimple_min_invariant (DECL_INITIAL (var)))
979
          {
980
            bitmap_set_bit (module_statics_const, index);
981
            if (dump_file)
982
              fprintf (dump_file, "read-only constant %s\n",
983
                       get_static_name (index));
984
          }
985
      }
986
 
987
    BITMAP_FREE(module_statics_escape);
988
    BITMAP_FREE(module_statics_written);
989
 
990
    if (dump_file)
991
      EXECUTE_IF_SET_IN_BITMAP (all_module_statics, 0, index, bi)
992
        {
993
          fprintf (dump_file, "\nPromotable global:%s",
994
                   get_static_name (index));
995
        }
996
 
997
    for (i = 0; i < order_pos; i++ )
998
      {
999
        ipa_reference_local_vars_info_t l;
1000
        node = order[i];
1001
        l = get_reference_vars_info_from_cgraph (node)->local;
1002
 
1003
        /* Any variables that are not in all_module_statics are
1004
           removed from the local maps.  This will include all of the
1005
           variables that were found to escape in the function
1006
           scanning.  */
1007
        bitmap_and_into (l->statics_read,
1008
                         all_module_statics);
1009
        bitmap_and_into (l->statics_written,
1010
                         all_module_statics);
1011
      }
1012
 
1013
    BITMAP_FREE(module_statics_readonly);
1014
    BITMAP_FREE(module_statics_const);
1015
    BITMAP_FREE(bm_temp);
1016
  }
1017
 
1018
  if (dump_file)
1019
    {
1020
      for (i = 0; i < order_pos; i++ )
1021
        {
1022
          unsigned int index;
1023
          ipa_reference_local_vars_info_t l;
1024
          bitmap_iterator bi;
1025
 
1026
          node = order[i];
1027
          l = get_reference_vars_info_from_cgraph (node)->local;
1028
          fprintf (dump_file,
1029
                   "\nFunction name:%s/%i:",
1030
                   cgraph_node_name (node), node->uid);
1031
          fprintf (dump_file, "\n  locals read: ");
1032
          EXECUTE_IF_SET_IN_BITMAP (l->statics_read,
1033
                                    0, index, bi)
1034
            {
1035
              fprintf (dump_file, "%s ",
1036
                       get_static_name (index));
1037
            }
1038
          fprintf (dump_file, "\n  locals written: ");
1039
          EXECUTE_IF_SET_IN_BITMAP (l->statics_written,
1040
                                    0, index, bi)
1041
            {
1042
              fprintf(dump_file, "%s ",
1043
                      get_static_name (index));
1044
            }
1045
        }
1046
    }
1047
 
1048
  /* Propagate the local information thru the call graph to produce
1049
     the global information.  All the nodes within a cycle will have
1050
     the same info so we collapse cycles first.  Then we can do the
1051
     propagation in one pass from the leaves to the roots.  */
1052
  order_pos = ipa_utils_reduced_inorder (order, true, true);
1053
  if (dump_file)
1054
    ipa_utils_print_order(dump_file, "reduced", order, order_pos);
1055
 
1056
  for (i = 0; i < order_pos; i++ )
1057
    {
1058
      ipa_reference_vars_info_t node_info;
1059
      ipa_reference_global_vars_info_t node_g =
1060
        xcalloc (1, sizeof (struct ipa_reference_global_vars_info_d));
1061
      ipa_reference_local_vars_info_t node_l;
1062
 
1063
      bool read_all;
1064
      bool write_all;
1065
      struct ipa_dfs_info * w_info;
1066
 
1067
      node = order[i];
1068
      node_info = get_reference_vars_info_from_cgraph (node);
1069
      if (!node_info)
1070
        {
1071
          dump_cgraph_node (stderr, node);
1072
          dump_cgraph (stderr);
1073
          gcc_unreachable ();
1074
        }
1075
 
1076
      node_info->global = node_g;
1077
      node_l = node_info->local;
1078
 
1079
      read_all = node_l->calls_read_all;
1080
      write_all = node_l->calls_write_all;
1081
 
1082
      /* If any node in a cycle is calls_read_all or calls_write_all
1083
         they all are. */
1084
      w_info = node->aux;
1085
      w = w_info->next_cycle;
1086
      while (w)
1087
        {
1088
          ipa_reference_local_vars_info_t w_l =
1089
            get_reference_vars_info_from_cgraph (w)->local;
1090
          read_all |= w_l->calls_read_all;
1091
          write_all |= w_l->calls_write_all;
1092
 
1093
          w_info = w->aux;
1094
          w = w_info->next_cycle;
1095
        }
1096
 
1097
      /* Initialized the bitmaps for the reduced nodes */
1098
      if (read_all)
1099
        node_g->statics_read = all_module_statics;
1100
      else
1101
        {
1102
          node_g->statics_read = BITMAP_ALLOC (&ipa_obstack);
1103
          bitmap_copy (node_g->statics_read,
1104
                       node_l->statics_read);
1105
        }
1106
 
1107
      if (write_all)
1108
        node_g->statics_written = all_module_statics;
1109
      else
1110
        {
1111
          node_g->statics_written = BITMAP_ALLOC (&ipa_obstack);
1112
          bitmap_copy (node_g->statics_written,
1113
                       node_l->statics_written);
1114
        }
1115
 
1116
      w_info = node->aux;
1117
      w = w_info->next_cycle;
1118
      while (w)
1119
        {
1120
          ipa_reference_vars_info_t w_ri =
1121
            get_reference_vars_info_from_cgraph (w);
1122
          ipa_reference_local_vars_info_t w_l = w_ri->local;
1123
 
1124
          /* All nodes within a cycle share the same global info bitmaps.  */
1125
          w_ri->global = node_g;
1126
 
1127
          /* These global bitmaps are initialized from the local info
1128
             of all of the nodes in the region.  However there is no
1129
             need to do any work if the bitmaps were set to
1130
             all_module_statics.  */
1131
          if (!read_all)
1132
            bitmap_ior_into (node_g->statics_read,
1133
                             w_l->statics_read);
1134
          if (!write_all)
1135
            bitmap_ior_into (node_g->statics_written,
1136
                             w_l->statics_written);
1137
          w_info = w->aux;
1138
          w = w_info->next_cycle;
1139
        }
1140
 
1141
      w = node;
1142
      while (w)
1143
        {
1144
          propagate_bits (w);
1145
          w_info = w->aux;
1146
          w = w_info->next_cycle;
1147
        }
1148
    }
1149
 
1150
  /* Need to fix up the local information sets.  The information that
1151
     has been gathered so far is preinlining.  However, the
1152
     compilation will progress post inlining so the local sets for the
1153
     inlined calls need to be merged into the callers.  Note that the
1154
     local sets are not shared between all of the nodes in a cycle so
1155
     those nodes in the cycle must be processed explicitly.  */
1156
  for (i = 0; i < order_pos; i++ )
1157
    {
1158
      struct ipa_dfs_info * w_info;
1159
      node = order[i];
1160
      merge_callee_local_info (node, node);
1161
 
1162
      w_info = node->aux;
1163
      w = w_info->next_cycle;
1164
      while (w)
1165
        {
1166
          merge_callee_local_info (w, w);
1167
          w_info = w->aux;
1168
          w = w_info->next_cycle;
1169
        }
1170
    }
1171
 
1172
  if (dump_file)
1173
    {
1174
      for (i = 0; i < order_pos; i++ )
1175
        {
1176
          ipa_reference_vars_info_t node_info;
1177
          ipa_reference_global_vars_info_t node_g;
1178
          ipa_reference_local_vars_info_t node_l;
1179
          unsigned int index;
1180
          bitmap_iterator bi;
1181
          struct ipa_dfs_info * w_info;
1182
 
1183
          node = order[i];
1184
          node_info = get_reference_vars_info_from_cgraph (node);
1185
          node_g = node_info->global;
1186
          node_l = node_info->local;
1187
          fprintf (dump_file,
1188
                   "\nFunction name:%s/%i:",
1189
                   cgraph_node_name (node), node->uid);
1190
          fprintf (dump_file, "\n  locals read: ");
1191
          EXECUTE_IF_SET_IN_BITMAP (node_l->statics_read,
1192
                                    0, index, bi)
1193
            {
1194
              fprintf (dump_file, "%s ",
1195
                       get_static_name (index));
1196
            }
1197
          fprintf (dump_file, "\n  locals written: ");
1198
          EXECUTE_IF_SET_IN_BITMAP (node_l->statics_written,
1199
                                    0, index, bi)
1200
            {
1201
              fprintf(dump_file, "%s ",
1202
                      get_static_name (index));
1203
            }
1204
 
1205
          w_info = node->aux;
1206
          w = w_info->next_cycle;
1207
          while (w)
1208
            {
1209
              ipa_reference_vars_info_t w_ri =
1210
                get_reference_vars_info_from_cgraph (w);
1211
              ipa_reference_local_vars_info_t w_l = w_ri->local;
1212
              fprintf (dump_file, "\n  next cycle: %s/%i ",
1213
                       cgraph_node_name (w), w->uid);
1214
              fprintf (dump_file, "\n    locals read: ");
1215
              EXECUTE_IF_SET_IN_BITMAP (w_l->statics_read,
1216
                                        0, index, bi)
1217
                {
1218
                  fprintf (dump_file, "%s ",
1219
                           get_static_name (index));
1220
                }
1221
 
1222
              fprintf (dump_file, "\n    locals written: ");
1223
              EXECUTE_IF_SET_IN_BITMAP (w_l->statics_written,
1224
                                        0, index, bi)
1225
                {
1226
                  fprintf(dump_file, "%s ",
1227
                          get_static_name (index));
1228
                }
1229
 
1230
 
1231
              w_info = w->aux;
1232
              w = w_info->next_cycle;
1233
            }
1234
          fprintf (dump_file, "\n  globals read: ");
1235
          EXECUTE_IF_SET_IN_BITMAP (node_g->statics_read,
1236
                                    0, index, bi)
1237
            {
1238
              fprintf (dump_file, "%s ",
1239
                       get_static_name (index));
1240
            }
1241
          fprintf (dump_file, "\n  globals written: ");
1242
          EXECUTE_IF_SET_IN_BITMAP (node_g->statics_written,
1243
                                    0, index, bi)
1244
            {
1245
              fprintf (dump_file, "%s ",
1246
                       get_static_name (index));
1247
            }
1248
        }
1249
    }
1250
 
1251
  /* Cleanup. */
1252
  for (i = 0; i < order_pos; i++ )
1253
    {
1254
      ipa_reference_vars_info_t node_info;
1255
      ipa_reference_global_vars_info_t node_g;
1256
      node = order[i];
1257
      node_info = get_reference_vars_info_from_cgraph (node);
1258
      node_g = node_info->global;
1259
 
1260
      /* Create the complimentary sets.  These are more useful for
1261
         certain apis.  */
1262
      node_g->statics_not_read = BITMAP_ALLOC (&ipa_obstack);
1263
      node_g->statics_not_written = BITMAP_ALLOC (&ipa_obstack);
1264
 
1265
      if (node_g->statics_read != all_module_statics)
1266
        {
1267
          bitmap_and_compl (node_g->statics_not_read,
1268
                            all_module_statics,
1269
                            node_g->statics_read);
1270
        }
1271
 
1272
      if (node_g->statics_written
1273
          != all_module_statics)
1274
        bitmap_and_compl (node_g->statics_not_written,
1275
                          all_module_statics,
1276
                          node_g->statics_written);
1277
   }
1278
 
1279
  free (order);
1280
 
1281
  for (node = cgraph_nodes; node; node = node->next)
1282
    {
1283
      /* Get rid of the aux information.  */
1284
 
1285
      if (node->aux)
1286
        {
1287
          free (node->aux);
1288
          node->aux = NULL;
1289
        }
1290
 
1291
      if (node->analyzed
1292
          && (cgraph_function_body_availability (node) == AVAIL_OVERWRITABLE))
1293
        clean_function (node);
1294
    }
1295
}
1296
 
1297
 
1298
static bool
1299
gate_reference (void)
1300
{
1301
  return (flag_unit_at_a_time != 0  && flag_ipa_reference
1302
          /* Don't bother doing anything if the program has errors.  */
1303
          && !(errorcount || sorrycount));
1304
}
1305
 
1306
struct tree_opt_pass pass_ipa_reference =
1307
{
1308
  "static-var",                         /* name */
1309
  gate_reference,                       /* gate */
1310
  static_execute,                       /* execute */
1311
  NULL,                                 /* sub */
1312
  NULL,                                 /* next */
1313
  0,                                     /* static_pass_number */
1314
  TV_IPA_REFERENCE,                     /* tv_id */
1315
  0,                                     /* properties_required */
1316
  0,                                     /* properties_provided */
1317
  0,                                     /* properties_destroyed */
1318
  0,                                     /* todo_flags_start */
1319
  0,                                    /* todo_flags_finish */
1320
 
1321
};
1322
 
1323
#include "gt-ipa-reference.h"
1324
 

powered by: WebSVN 2.1.0

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