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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-old/] [gcc-4.2.2/] [gcc/] [tree-ssa-alias.c] - Blame information for rev 841

Go to most recent revision | Details | Compare with Previous | View Log

Line No. Rev Author Line
1 38 julius
/* Alias analysis for trees.
2
   Copyright (C) 2004, 2005, 2007 Free Software Foundation, Inc.
3
   Contributed by Diego Novillo <dnovillo@redhat.com>
4
 
5
This file is part of GCC.
6
 
7
GCC is free software; you can redistribute it and/or modify
8
it under the terms of the GNU General Public License as published by
9
the Free Software Foundation; either version 3, or (at your option)
10
any later version.
11
 
12
GCC is distributed in the hope that it will be useful,
13
but WITHOUT ANY WARRANTY; without even the implied warranty of
14
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15
GNU General Public License for more details.
16
 
17
You should have received a copy of the GNU General Public License
18
along with GCC; see the file COPYING3.  If not see
19
<http://www.gnu.org/licenses/>.  */
20
 
21
#include "config.h"
22
#include "system.h"
23
#include "coretypes.h"
24
#include "tm.h"
25
#include "tree.h"
26
#include "rtl.h"
27
#include "tm_p.h"
28
#include "hard-reg-set.h"
29
#include "basic-block.h"
30
#include "timevar.h"
31
#include "expr.h"
32
#include "ggc.h"
33
#include "langhooks.h"
34
#include "flags.h"
35
#include "function.h"
36
#include "diagnostic.h"
37
#include "tree-dump.h"
38
#include "tree-gimple.h"
39
#include "tree-flow.h"
40
#include "tree-inline.h"
41
#include "tree-pass.h"
42
#include "tree-ssa-structalias.h"
43
#include "convert.h"
44
#include "params.h"
45
#include "ipa-type-escape.h"
46
#include "vec.h"
47
#include "bitmap.h"
48
#include "vecprim.h"
49
#include "pointer-set.h"
50
 
51
/* Obstack used to hold grouping bitmaps and other temporary bitmaps used by
52
   aliasing  */
53
static bitmap_obstack alias_obstack;
54
 
55
/* 'true' after aliases have been computed (see compute_may_aliases).  */
56
bool aliases_computed_p;
57
 
58
/* Structure to map a variable to its alias set and keep track of the
59
   virtual operands that will be needed to represent it.  */
60
struct alias_map_d
61
{
62
  /* Variable and its alias set.  */
63
  tree var;
64
  HOST_WIDE_INT set;
65
 
66
  /* Total number of virtual operands that will be needed to represent
67
     all the aliases of VAR.  */
68
  long total_alias_vops;
69
 
70
  /* Nonzero if the aliases for this memory tag have been grouped
71
     already.  Used in group_aliases.  */
72
  unsigned int grouped_p : 1;
73
 
74
  /* Set of variables aliased with VAR.  This is the exact same
75
     information contained in VAR_ANN (VAR)->MAY_ALIASES, but in
76
     bitmap form to speed up alias grouping.  */
77
  bitmap may_aliases;
78
};
79
 
80
 
81
/* Counters used to display statistics on alias analysis.  */
82
struct alias_stats_d
83
{
84
  unsigned int alias_queries;
85
  unsigned int alias_mayalias;
86
  unsigned int alias_noalias;
87
  unsigned int simple_queries;
88
  unsigned int simple_resolved;
89
  unsigned int tbaa_queries;
90
  unsigned int tbaa_resolved;
91
  unsigned int structnoaddress_queries;
92
  unsigned int structnoaddress_resolved;
93
};
94
 
95
 
96
/* Local variables.  */
97
static struct alias_stats_d alias_stats;
98
 
99
/* Local functions.  */
100
static void compute_flow_insensitive_aliasing (struct alias_info *);
101
static void finalize_ref_all_pointers (struct alias_info *);
102
static void dump_alias_stats (FILE *);
103
static bool may_alias_p (tree, HOST_WIDE_INT, tree, HOST_WIDE_INT, bool);
104
static tree create_memory_tag (tree type, bool is_type_tag);
105
static tree get_tmt_for (tree, struct alias_info *);
106
static tree get_nmt_for (tree);
107
static void add_may_alias (tree, tree);
108
static void replace_may_alias (tree, size_t, tree);
109
static struct alias_info *init_alias_info (void);
110
static void delete_alias_info (struct alias_info *);
111
static void compute_flow_sensitive_aliasing (struct alias_info *);
112
static void setup_pointers_and_addressables (struct alias_info *);
113
static void create_global_var (void);
114
static void maybe_create_global_var (struct alias_info *ai);
115
static void group_aliases (struct alias_info *);
116
static void set_pt_anything (tree ptr);
117
 
118
/* Global declarations.  */
119
 
120
/* Call clobbered variables in the function.  If bit I is set, then
121
   REFERENCED_VARS (I) is call-clobbered.  */
122
bitmap call_clobbered_vars;
123
 
124
/* Addressable variables in the function.  If bit I is set, then
125
   REFERENCED_VARS (I) has had its address taken.  Note that
126
   CALL_CLOBBERED_VARS and ADDRESSABLE_VARS are not related.  An
127
   addressable variable is not necessarily call-clobbered (e.g., a
128
   local addressable whose address does not escape) and not all
129
   call-clobbered variables are addressable (e.g., a local static
130
   variable).  */
131
bitmap addressable_vars;
132
 
133
/* When the program has too many call-clobbered variables and call-sites,
134
   this variable is used to represent the clobbering effects of function
135
   calls.  In these cases, all the call clobbered variables in the program
136
   are forced to alias this variable.  This reduces compile times by not
137
   having to keep track of too many V_MAY_DEF expressions at call sites.  */
138
tree global_var;
139
 
140
/* qsort comparison function to sort type/name tags by DECL_UID.  */
141
 
142
static int
143
sort_tags_by_id (const void *pa, const void *pb)
144
{
145
  tree a = *(tree *)pa;
146
  tree b = *(tree *)pb;
147
 
148
  return DECL_UID (a) - DECL_UID (b);
149
}
150
 
151
/* Initialize WORKLIST to contain those memory tags that are marked call
152
   clobbered.  Initialized WORKLIST2 to contain the reasons these
153
   memory tags escaped.  */
154
 
155
static void
156
init_transitive_clobber_worklist (VEC (tree, heap) **worklist,
157
                                  VEC (int, heap) **worklist2)
158
{
159
  referenced_var_iterator rvi;
160
  tree curr;
161
 
162
  FOR_EACH_REFERENCED_VAR (curr, rvi)
163
    {
164
      if (MTAG_P (curr) && is_call_clobbered (curr))
165
        {
166
          VEC_safe_push (tree, heap, *worklist, curr);
167
          VEC_safe_push (int, heap, *worklist2, var_ann (curr)->escape_mask);
168
        }
169
    }
170
}
171
 
172
/* Add ALIAS to WORKLIST (and the reason for escaping REASON to WORKLIST2) if
173
   ALIAS is not already marked call clobbered, and is a memory
174
   tag.  */
175
 
176
static void
177
add_to_worklist (tree alias, VEC (tree, heap) **worklist,
178
                 VEC (int, heap) **worklist2,
179
                 int reason)
180
{
181
  if (MTAG_P (alias) && !is_call_clobbered (alias))
182
    {
183
      VEC_safe_push (tree, heap, *worklist, alias);
184
      VEC_safe_push (int, heap, *worklist2, reason);
185
    }
186
}
187
 
188
/* Mark aliases of TAG as call clobbered, and place any tags on the
189
   alias list that were not already call clobbered on WORKLIST.  */
190
 
191
static void
192
mark_aliases_call_clobbered (tree tag, VEC (tree, heap) **worklist,
193
                             VEC (int, heap) **worklist2)
194
{
195
  unsigned int i;
196
  VEC (tree, gc) *ma;
197
  tree entry;
198
  var_ann_t ta = var_ann (tag);
199
 
200
  if (!MTAG_P (tag))
201
    return;
202
  ma = may_aliases (tag);
203
  if (!ma)
204
    return;
205
 
206
  for (i = 0; VEC_iterate (tree, ma, i, entry); i++)
207
    {
208
      if (!unmodifiable_var_p (entry))
209
        {
210
          add_to_worklist (entry, worklist, worklist2, ta->escape_mask);
211
          mark_call_clobbered (entry, ta->escape_mask);
212
        }
213
    }
214
}
215
 
216
/* Tags containing global vars need to be marked as global.
217
   Tags containing call clobbered vars need to be marked as call
218
   clobbered. */
219
 
220
static void
221
compute_tag_properties (void)
222
{
223
  referenced_var_iterator rvi;
224
  tree tag;
225
  bool changed = true;
226
  VEC (tree, heap) *taglist = NULL;
227
 
228
  FOR_EACH_REFERENCED_VAR (tag, rvi)
229
    {
230
      if (!MTAG_P (tag) || TREE_CODE (tag) == STRUCT_FIELD_TAG)
231
        continue;
232
      VEC_safe_push (tree, heap, taglist, tag);
233
    }
234
 
235
  /* We sort the taglist by DECL_UID, for two reasons.
236
     1. To get a sequential ordering to make the bitmap accesses
237
     faster.
238
     2. Because of the way we compute aliases, it's more likely that
239
     an earlier tag is included in a later tag, and this will reduce
240
     the number of iterations.
241
 
242
     If we had a real tag graph, we would just topo-order it and be
243
     done with it.  */
244
  qsort (VEC_address (tree, taglist),
245
         VEC_length (tree, taglist),
246
         sizeof (tree),
247
         sort_tags_by_id);
248
 
249
  /* Go through each tag not marked as global, and if it aliases
250
     global vars, mark it global.
251
 
252
     If the tag contains call clobbered vars, mark it call
253
     clobbered.
254
 
255
     This loop iterates because tags may appear in the may-aliases
256
     list of other tags when we group.  */
257
 
258
  while (changed)
259
    {
260
      unsigned int k;
261
 
262
      changed = false;
263
      for (k = 0; VEC_iterate (tree, taglist, k, tag); k++)
264
        {
265
          VEC (tree, gc) *ma;
266
          unsigned int i;
267
          tree entry;
268
          bool tagcc = is_call_clobbered (tag);
269
          bool tagglobal = MTAG_GLOBAL (tag);
270
 
271
          if (tagcc && tagglobal)
272
            continue;
273
 
274
          ma = may_aliases (tag);
275
          if (!ma)
276
            continue;
277
 
278
          for (i = 0; VEC_iterate (tree, ma, i, entry); i++)
279
            {
280
              /* Call clobbered entries cause the tag to be marked
281
                 call clobbered.  */
282
              if (!tagcc && is_call_clobbered (entry))
283
                {
284
                  mark_call_clobbered (tag, var_ann (entry)->escape_mask);
285
                  tagcc = true;
286
                  changed = true;
287
                }
288
 
289
              /* Global vars cause the tag to be marked global.  */
290
              if (!tagglobal && is_global_var (entry))
291
                {
292
                  MTAG_GLOBAL (tag) = true;
293
                  changed = true;
294
                  tagglobal = true;
295
                }
296
 
297
              /* Early exit once both global and cc are set, since the
298
                 loop can't do any more than that.  */
299
              if (tagcc && tagglobal)
300
                break;
301
            }
302
        }
303
    }
304
  VEC_free (tree, heap, taglist);
305
}
306
 
307
/* Set up the initial variable clobbers and globalness.
308
   When this function completes, only tags whose aliases need to be
309
   clobbered will be set clobbered.  Tags clobbered because they
310
   contain call clobbered vars are handled in compute_tag_properties.  */
311
 
312
static void
313
set_initial_properties (struct alias_info *ai)
314
{
315
  unsigned int i;
316
  referenced_var_iterator rvi;
317
  tree var;
318
  tree ptr;
319
 
320
  FOR_EACH_REFERENCED_VAR (var, rvi)
321
    {
322
      if (is_global_var (var)
323
          && (!var_can_have_subvars (var)
324
              || get_subvars_for_var (var) == NULL))
325
        {
326
          if (!unmodifiable_var_p (var))
327
            mark_call_clobbered (var, ESCAPE_IS_GLOBAL);
328
        }
329
      else if (TREE_CODE (var) == PARM_DECL
330
               && default_def (var)
331
               && POINTER_TYPE_P (TREE_TYPE (var)))
332
        {
333
          tree def = default_def (var);
334
          get_ptr_info (def)->value_escapes_p = 1;
335
          get_ptr_info (def)->escape_mask |= ESCAPE_IS_PARM;
336
        }
337
    }
338
 
339
  for (i = 0; VEC_iterate (tree, ai->processed_ptrs, i, ptr); i++)
340
    {
341
      struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
342
      var_ann_t v_ann = var_ann (SSA_NAME_VAR (ptr));
343
 
344
      if (pi->value_escapes_p)
345
        {
346
          /* If PTR escapes then its associated memory tags and
347
             pointed-to variables are call-clobbered.  */
348
          if (pi->name_mem_tag)
349
            mark_call_clobbered (pi->name_mem_tag, pi->escape_mask);
350
 
351
          if (v_ann->symbol_mem_tag)
352
            mark_call_clobbered (v_ann->symbol_mem_tag, pi->escape_mask);
353
 
354
          if (pi->pt_vars)
355
            {
356
              bitmap_iterator bi;
357
              unsigned int j;
358
              EXECUTE_IF_SET_IN_BITMAP (pi->pt_vars, 0, j, bi)
359
                if (!unmodifiable_var_p (referenced_var (j)))
360
                  mark_call_clobbered (referenced_var (j), pi->escape_mask);
361
            }
362
        }
363
 
364
      /* If the name tag is call clobbered, so is the symbol tag
365
         associated with the base VAR_DECL.  */
366
      if (pi->name_mem_tag
367
          && v_ann->symbol_mem_tag
368
          && is_call_clobbered (pi->name_mem_tag))
369
        mark_call_clobbered (v_ann->symbol_mem_tag, pi->escape_mask);
370
 
371
      /* Name tags and symbol tags that we don't know where they point
372
         to, might point to global memory, and thus, are clobbered.
373
 
374
         FIXME:  This is not quite right.  They should only be
375
         clobbered if value_escapes_p is true, regardless of whether
376
         they point to global memory or not.
377
         So removing this code and fixing all the bugs would be nice.
378
         It is the cause of a bunch of clobbering.  */
379
      if ((pi->pt_global_mem || pi->pt_anything)
380
          && pi->is_dereferenced && pi->name_mem_tag)
381
        {
382
          mark_call_clobbered (pi->name_mem_tag, ESCAPE_IS_GLOBAL);
383
          MTAG_GLOBAL (pi->name_mem_tag) = true;
384
        }
385
 
386
      if ((pi->pt_global_mem || pi->pt_anything)
387
          && pi->is_dereferenced
388
          && v_ann->symbol_mem_tag)
389
        {
390
          mark_call_clobbered (v_ann->symbol_mem_tag, ESCAPE_IS_GLOBAL);
391
          MTAG_GLOBAL (v_ann->symbol_mem_tag) = true;
392
        }
393
    }
394
}
395
 
396
 
397
/* This variable is set to true if we are updating the used alone
398
   information for SMTs, or are in a pass that is going to break it
399
   temporarily.  */
400
bool updating_used_alone;
401
 
402
/* Compute which variables need to be marked call clobbered because
403
   their tag is call clobbered, and which tags need to be marked
404
   global because they contain global variables.  */
405
 
406
static void
407
compute_call_clobbered (struct alias_info *ai)
408
{
409
  VEC (tree, heap) *worklist = NULL;
410
  VEC(int,heap) *worklist2 = NULL;
411
 
412
  set_initial_properties (ai);
413
  init_transitive_clobber_worklist (&worklist, &worklist2);
414
  while (VEC_length (tree, worklist) != 0)
415
    {
416
      tree curr = VEC_pop (tree, worklist);
417
      int reason = VEC_pop (int, worklist2);
418
 
419
      mark_call_clobbered (curr, reason);
420
      mark_aliases_call_clobbered (curr, &worklist, &worklist2);
421
    }
422
  VEC_free (tree, heap, worklist);
423
  VEC_free (int, heap, worklist2);
424
  compute_tag_properties ();
425
}
426
 
427
 
428
/* Helper for recalculate_used_alone.  Return a conservatively correct
429
   answer as to whether STMT may make a store on the LHS to SYM.  */
430
 
431
static bool
432
lhs_may_store_to (tree stmt, tree sym ATTRIBUTE_UNUSED)
433
{
434
  tree lhs = TREE_OPERAND (stmt, 0);
435
 
436
  lhs = get_base_address (lhs);
437
 
438
  if (!lhs)
439
    return false;
440
 
441
  if (TREE_CODE (lhs) == SSA_NAME)
442
    return false;
443
  /* We could do better here by looking at the type tag of LHS, but it
444
     is unclear whether this is worth it. */
445
  return true;
446
}
447
 
448
/* Recalculate the used_alone information for SMTs . */
449
 
450
void
451
recalculate_used_alone (void)
452
{
453
  VEC (tree, heap) *calls = NULL;
454
  block_stmt_iterator bsi;
455
  basic_block bb;
456
  tree stmt;
457
  size_t i;
458
  referenced_var_iterator rvi;
459
  tree var;
460
 
461
  /* First, reset all the SMT used alone bits to zero.  */
462
  updating_used_alone = true;
463
  FOR_EACH_REFERENCED_VAR (var, rvi)
464
    if (TREE_CODE (var) == SYMBOL_MEMORY_TAG)
465
      {
466
        SMT_OLD_USED_ALONE (var) = SMT_USED_ALONE (var);
467
        SMT_USED_ALONE (var) = 0;
468
      }
469
 
470
  /* Walk all the statements.
471
     Calls get put into a list of statements to update, since we will
472
     need to update operands on them if we make any changes.
473
     If we see a bare use of a SMT anywhere in a real virtual use or virtual
474
     def, mark the SMT as used alone, and for renaming.  */
475
  FOR_EACH_BB (bb)
476
    {
477
      for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
478
        {
479
          bool iscall = false;
480
          ssa_op_iter iter;
481
 
482
          stmt = bsi_stmt (bsi);
483
 
484
          if (TREE_CODE (stmt) == CALL_EXPR
485
              || (TREE_CODE (stmt) == MODIFY_EXPR
486
                  && TREE_CODE (TREE_OPERAND (stmt, 1)) == CALL_EXPR))
487
            {
488
              iscall = true;
489
              VEC_safe_push (tree, heap, calls, stmt);
490
            }
491
 
492
          FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter,
493
                                     SSA_OP_VUSE | SSA_OP_VIRTUAL_DEFS)
494
            {
495
              tree svar = var;
496
 
497
              if (TREE_CODE (var) == SSA_NAME)
498
                svar = SSA_NAME_VAR (var);
499
 
500
              if (TREE_CODE (svar) == SYMBOL_MEMORY_TAG)
501
                {
502
                  /* We only care about the LHS on calls.  */
503
                  if (iscall && !lhs_may_store_to (stmt, svar))
504
                    continue;
505
 
506
                  if (!SMT_USED_ALONE (svar))
507
                    {
508
                      SMT_USED_ALONE (svar) = true;
509
 
510
                      /* Only need to mark for renaming if it wasn't
511
                         used alone before.  */
512
                      if (!SMT_OLD_USED_ALONE (svar))
513
                        mark_sym_for_renaming (svar);
514
                    }
515
                }
516
            }
517
        }
518
    }
519
 
520
  /* Update the operands on all the calls we saw.  */
521
  if (calls)
522
    {
523
      for (i = 0; VEC_iterate (tree, calls, i, stmt); i++)
524
        update_stmt (stmt);
525
    }
526
 
527
  /* We need to mark SMT's that are no longer used for renaming so the
528
     symbols go away, or else verification will be angry with us, even
529
     though they are dead.  */
530
  FOR_EACH_REFERENCED_VAR (var, rvi)
531
    if (TREE_CODE (var) == SYMBOL_MEMORY_TAG)
532
      {
533
        if (SMT_OLD_USED_ALONE (var) && !SMT_USED_ALONE (var))
534
          mark_sym_for_renaming (var);
535
      }
536
 
537
  VEC_free (tree, heap, calls);
538
  updating_used_alone = false;
539
}
540
 
541
/* Compute may-alias information for every variable referenced in function
542
   FNDECL.
543
 
544
   Alias analysis proceeds in 3 main phases:
545
 
546
   1- Points-to and escape analysis.
547
 
548
   This phase walks the use-def chains in the SSA web looking for three
549
   things:
550
 
551
        * Assignments of the form P_i = &VAR
552
        * Assignments of the form P_i = malloc()
553
        * Pointers and ADDR_EXPR that escape the current function.
554
 
555
   The concept of 'escaping' is the same one used in the Java world.  When
556
   a pointer or an ADDR_EXPR escapes, it means that it has been exposed
557
   outside of the current function.  So, assignment to global variables,
558
   function arguments and returning a pointer are all escape sites, as are
559
   conversions between pointers and integers.
560
 
561
   This is where we are currently limited.  Since not everything is renamed
562
   into SSA, we lose track of escape properties when a pointer is stashed
563
   inside a field in a structure, for instance.  In those cases, we are
564
   assuming that the pointer does escape.
565
 
566
   We use escape analysis to determine whether a variable is
567
   call-clobbered.  Simply put, if an ADDR_EXPR escapes, then the variable
568
   is call-clobbered.  If a pointer P_i escapes, then all the variables
569
   pointed-to by P_i (and its memory tag) also escape.
570
 
571
   2- Compute flow-sensitive aliases
572
 
573
   We have two classes of memory tags.  Memory tags associated with the
574
   pointed-to data type of the pointers in the program.  These tags are
575
   called "symbol memory tag" (SMT).  The other class are those associated
576
   with SSA_NAMEs, called "name memory tag" (NMT). The basic idea is that
577
   when adding operands for an INDIRECT_REF *P_i, we will first check
578
   whether P_i has a name tag, if it does we use it, because that will have
579
   more precise aliasing information.  Otherwise, we use the standard symbol
580
   tag.
581
 
582
   In this phase, we go through all the pointers we found in points-to
583
   analysis and create alias sets for the name memory tags associated with
584
   each pointer P_i.  If P_i escapes, we mark call-clobbered the variables
585
   it points to and its tag.
586
 
587
 
588
   3- Compute flow-insensitive aliases
589
 
590
   This pass will compare the alias set of every symbol memory tag and
591
   every addressable variable found in the program.  Given a symbol
592
   memory tag SMT and an addressable variable V.  If the alias sets of
593
   SMT and V conflict (as computed by may_alias_p), then V is marked
594
   as an alias tag and added to the alias set of SMT.
595
 
596
   For instance, consider the following function:
597
 
598
            foo (int i)
599
            {
600
              int *p, a, b;
601
 
602
              if (i > 10)
603
                p = &a;
604
              else
605
                p = &b;
606
 
607
              *p = 3;
608
              a = b + 2;
609
              return *p;
610
            }
611
 
612
   After aliasing analysis has finished, the symbol memory tag for pointer
613
   'p' will have two aliases, namely variables 'a' and 'b'.  Every time
614
   pointer 'p' is dereferenced, we want to mark the operation as a
615
   potential reference to 'a' and 'b'.
616
 
617
            foo (int i)
618
            {
619
              int *p, a, b;
620
 
621
              if (i_2 > 10)
622
                p_4 = &a;
623
              else
624
                p_6 = &b;
625
              # p_1 = PHI <p_4(1), p_6(2)>;
626
 
627
              # a_7 = V_MAY_DEF <a_3>;
628
              # b_8 = V_MAY_DEF <b_5>;
629
              *p_1 = 3;
630
 
631
              # a_9 = V_MAY_DEF <a_7>
632
              # VUSE <b_8>
633
              a_9 = b_8 + 2;
634
 
635
              # VUSE <a_9>;
636
              # VUSE <b_8>;
637
              return *p_1;
638
            }
639
 
640
   In certain cases, the list of may aliases for a pointer may grow too
641
   large.  This may cause an explosion in the number of virtual operands
642
   inserted in the code.  Resulting in increased memory consumption and
643
   compilation time.
644
 
645
   When the number of virtual operands needed to represent aliased
646
   loads and stores grows too large (configurable with @option{--param
647
   max-aliased-vops}), alias sets are grouped to avoid severe
648
   compile-time slow downs and memory consumption.  See group_aliases.  */
649
 
650
static unsigned int
651
compute_may_aliases (void)
652
{
653
  struct alias_info *ai;
654
 
655
  memset (&alias_stats, 0, sizeof (alias_stats));
656
 
657
  /* Initialize aliasing information.  */
658
  ai = init_alias_info ();
659
 
660
  /* For each pointer P_i, determine the sets of variables that P_i may
661
     point-to.  For every addressable variable V, determine whether the
662
     address of V escapes the current function, making V call-clobbered
663
     (i.e., whether &V is stored in a global variable or if its passed as a
664
     function call argument).  */
665
  compute_points_to_sets (ai);
666
 
667
  /* Collect all pointers and addressable variables, compute alias sets,
668
     create memory tags for pointers and promote variables whose address is
669
     not needed anymore.  */
670
  setup_pointers_and_addressables (ai);
671
 
672
  /* Compute flow-sensitive, points-to based aliasing for all the name
673
     memory tags.  Note that this pass needs to be done before flow
674
     insensitive analysis because it uses the points-to information
675
     gathered before to mark call-clobbered symbol tags.  */
676
  compute_flow_sensitive_aliasing (ai);
677
 
678
  /* Compute type-based flow-insensitive aliasing for all the type
679
     memory tags.  */
680
  compute_flow_insensitive_aliasing (ai);
681
 
682
  /* Compute call clobbering information.  */
683
  compute_call_clobbered (ai);
684
 
685
  /* Determine if we need to enable alias grouping.  */
686
  if (ai->total_alias_vops >= MAX_ALIASED_VOPS)
687
    group_aliases (ai);
688
 
689
  /* If the program has too many call-clobbered variables and/or function
690
     calls, create .GLOBAL_VAR and use it to model call-clobbering
691
     semantics at call sites.  This reduces the number of virtual operands
692
     considerably, improving compile times at the expense of lost
693
     aliasing precision.  */
694
  maybe_create_global_var (ai);
695
 
696
  /* If the program contains ref-all pointers, finalize may-alias information
697
     for them.  This pass needs to be run after call-clobbering information
698
     has been computed.  */
699
  if (ai->ref_all_symbol_mem_tag)
700
    finalize_ref_all_pointers (ai);
701
 
702
  /* Debugging dumps.  */
703
  if (dump_file)
704
    {
705
      dump_referenced_vars (dump_file);
706
      if (dump_flags & TDF_STATS)
707
        dump_alias_stats (dump_file);
708
      dump_points_to_info (dump_file);
709
      dump_alias_info (dump_file);
710
    }
711
 
712
  /* Deallocate memory used by aliasing data structures.  */
713
  delete_alias_info (ai);
714
 
715
  updating_used_alone = true;
716
  {
717
    block_stmt_iterator bsi;
718
    basic_block bb;
719
    FOR_EACH_BB (bb)
720
      {
721
        for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
722
          {
723
            update_stmt_if_modified (bsi_stmt (bsi));
724
          }
725
      }
726
  }
727
  recalculate_used_alone ();
728
  updating_used_alone = false;
729
  return 0;
730
}
731
 
732
 
733
struct tree_opt_pass pass_may_alias =
734
{
735
  "alias",                              /* name */
736
  NULL,                                 /* gate */
737
  compute_may_aliases,                  /* execute */
738
  NULL,                                 /* sub */
739
  NULL,                                 /* next */
740
  0,                                     /* static_pass_number */
741
  TV_TREE_MAY_ALIAS,                    /* tv_id */
742
  PROP_cfg | PROP_ssa,                  /* properties_required */
743
  PROP_alias,                           /* properties_provided */
744
  0,                                     /* properties_destroyed */
745
  0,                                     /* todo_flags_start */
746
  TODO_dump_func | TODO_update_ssa
747
    | TODO_ggc_collect | TODO_verify_ssa
748
    | TODO_verify_stmts,                /* todo_flags_finish */
749
 
750
};
751
 
752
 
753
/* Data structure used to count the number of dereferences to PTR
754
   inside an expression.  */
755
struct count_ptr_d
756
{
757
  tree ptr;
758
  unsigned count;
759
};
760
 
761
 
762
/* Helper for count_uses_and_derefs.  Called by walk_tree to look for
763
   (ALIGN/MISALIGNED_)INDIRECT_REF nodes for the pointer passed in DATA.  */
764
 
765
static tree
766
count_ptr_derefs (tree *tp, int *walk_subtrees, void *data)
767
{
768
  struct count_ptr_d *count_p = (struct count_ptr_d *) data;
769
 
770
  /* Do not walk inside ADDR_EXPR nodes.  In the expression &ptr->fld,
771
     pointer 'ptr' is *not* dereferenced, it is simply used to compute
772
     the address of 'fld' as 'ptr + offsetof(fld)'.  */
773
  if (TREE_CODE (*tp) == ADDR_EXPR)
774
    {
775
      *walk_subtrees = 0;
776
      return NULL_TREE;
777
    }
778
 
779
  if (INDIRECT_REF_P (*tp) && TREE_OPERAND (*tp, 0) == count_p->ptr)
780
    count_p->count++;
781
 
782
  return NULL_TREE;
783
}
784
 
785
 
786
/* Count the number of direct and indirect uses for pointer PTR in
787
   statement STMT.  The two counts are stored in *NUM_USES_P and
788
   *NUM_DEREFS_P respectively.  *IS_STORE_P is set to 'true' if at
789
   least one of those dereferences is a store operation.  */
790
 
791
void
792
count_uses_and_derefs (tree ptr, tree stmt, unsigned *num_uses_p,
793
                       unsigned *num_derefs_p, bool *is_store)
794
{
795
  ssa_op_iter i;
796
  tree use;
797
 
798
  *num_uses_p = 0;
799
  *num_derefs_p = 0;
800
  *is_store = false;
801
 
802
  /* Find out the total number of uses of PTR in STMT.  */
803
  FOR_EACH_SSA_TREE_OPERAND (use, stmt, i, SSA_OP_USE)
804
    if (use == ptr)
805
      (*num_uses_p)++;
806
 
807
  /* Now count the number of indirect references to PTR.  This is
808
     truly awful, but we don't have much choice.  There are no parent
809
     pointers inside INDIRECT_REFs, so an expression like
810
     '*x_1 = foo (x_1, *x_1)' needs to be traversed piece by piece to
811
     find all the indirect and direct uses of x_1 inside.  The only
812
     shortcut we can take is the fact that GIMPLE only allows
813
     INDIRECT_REFs inside the expressions below.  */
814
  if (TREE_CODE (stmt) == MODIFY_EXPR
815
      || (TREE_CODE (stmt) == RETURN_EXPR
816
          && TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR)
817
      || TREE_CODE (stmt) == ASM_EXPR
818
      || TREE_CODE (stmt) == CALL_EXPR)
819
    {
820
      tree lhs, rhs;
821
 
822
      if (TREE_CODE (stmt) == MODIFY_EXPR)
823
        {
824
          lhs = TREE_OPERAND (stmt, 0);
825
          rhs = TREE_OPERAND (stmt, 1);
826
        }
827
      else if (TREE_CODE (stmt) == RETURN_EXPR)
828
        {
829
          tree e = TREE_OPERAND (stmt, 0);
830
          lhs = TREE_OPERAND (e, 0);
831
          rhs = TREE_OPERAND (e, 1);
832
        }
833
      else if (TREE_CODE (stmt) == ASM_EXPR)
834
        {
835
          lhs = ASM_OUTPUTS (stmt);
836
          rhs = ASM_INPUTS (stmt);
837
        }
838
      else
839
        {
840
          lhs = NULL_TREE;
841
          rhs = stmt;
842
        }
843
 
844
      if (lhs && (TREE_CODE (lhs) == TREE_LIST || EXPR_P (lhs)))
845
        {
846
          struct count_ptr_d count;
847
          count.ptr = ptr;
848
          count.count = 0;
849
          walk_tree (&lhs, count_ptr_derefs, &count, NULL);
850
          *is_store = true;
851
          *num_derefs_p = count.count;
852
        }
853
 
854
      if (rhs && (TREE_CODE (rhs) == TREE_LIST || EXPR_P (rhs)))
855
        {
856
          struct count_ptr_d count;
857
          count.ptr = ptr;
858
          count.count = 0;
859
          walk_tree (&rhs, count_ptr_derefs, &count, NULL);
860
          *num_derefs_p += count.count;
861
        }
862
    }
863
 
864
  gcc_assert (*num_uses_p >= *num_derefs_p);
865
}
866
 
867
/* Initialize the data structures used for alias analysis.  */
868
 
869
static struct alias_info *
870
init_alias_info (void)
871
{
872
  struct alias_info *ai;
873
  referenced_var_iterator rvi;
874
  tree var;
875
 
876
  bitmap_obstack_initialize (&alias_obstack);
877
  ai = XCNEW (struct alias_info);
878
  ai->ssa_names_visited = sbitmap_alloc (num_ssa_names);
879
  sbitmap_zero (ai->ssa_names_visited);
880
  ai->processed_ptrs = VEC_alloc (tree, heap, 50);
881
  ai->written_vars = BITMAP_ALLOC (&alias_obstack);
882
  ai->dereferenced_ptrs_store = BITMAP_ALLOC (&alias_obstack);
883
  ai->dereferenced_ptrs_load = BITMAP_ALLOC (&alias_obstack);
884
 
885
  /* If aliases have been computed before, clear existing information.  */
886
  if (aliases_computed_p)
887
    {
888
      unsigned i;
889
 
890
      /* Similarly, clear the set of addressable variables.  In this
891
         case, we can just clear the set because addressability is
892
         only computed here.  */
893
      bitmap_clear (addressable_vars);
894
 
895
      /* Clear flow-insensitive alias information from each symbol.  */
896
      FOR_EACH_REFERENCED_VAR (var, rvi)
897
        {
898
          var_ann_t ann = var_ann (var);
899
 
900
          ann->is_aliased = 0;
901
          ann->may_aliases = NULL;
902
          NUM_REFERENCES_CLEAR (ann);
903
 
904
          /* Since we are about to re-discover call-clobbered
905
             variables, clear the call-clobbered flag.  Variables that
906
             are intrinsically call-clobbered (globals, local statics,
907
             etc) will not be marked by the aliasing code, so we can't
908
             remove them from CALL_CLOBBERED_VARS.
909
 
910
             NB: STRUCT_FIELDS are still call clobbered if they are for
911
             a global variable, so we *don't* clear their call clobberedness
912
             just because they are tags, though we will clear it if they
913
             aren't for global variables.  */
914
          if (TREE_CODE (var) == NAME_MEMORY_TAG
915
              || TREE_CODE (var) == SYMBOL_MEMORY_TAG
916
              || !is_global_var (var))
917
            clear_call_clobbered (var);
918
        }
919
 
920
      /* Clear flow-sensitive points-to information from each SSA name.  */
921
      for (i = 1; i < num_ssa_names; i++)
922
        {
923
          tree name = ssa_name (i);
924
 
925
          if (!name || !POINTER_TYPE_P (TREE_TYPE (name)))
926
            continue;
927
 
928
          if (SSA_NAME_PTR_INFO (name))
929
            {
930
              struct ptr_info_def *pi = SSA_NAME_PTR_INFO (name);
931
 
932
              /* Clear all the flags but keep the name tag to
933
                 avoid creating new temporaries unnecessarily.  If
934
                 this pointer is found to point to a subset or
935
                 superset of its former points-to set, then a new
936
                 tag will need to be created in create_name_tags.  */
937
              pi->pt_anything = 0;
938
              pi->pt_null = 0;
939
              pi->value_escapes_p = 0;
940
              pi->is_dereferenced = 0;
941
              if (pi->pt_vars)
942
                bitmap_clear (pi->pt_vars);
943
            }
944
        }
945
    }
946
 
947
  /* Next time, we will need to reset alias information.  */
948
  aliases_computed_p = true;
949
 
950
  return ai;
951
}
952
 
953
 
954
/* Deallocate memory used by alias analysis.  */
955
 
956
static void
957
delete_alias_info (struct alias_info *ai)
958
{
959
  size_t i;
960
  referenced_var_iterator rvi;
961
  tree var;
962
 
963
  sbitmap_free (ai->ssa_names_visited);
964
  VEC_free (tree, heap, ai->processed_ptrs);
965
 
966
  for (i = 0; i < ai->num_addressable_vars; i++)
967
    free (ai->addressable_vars[i]);
968
 
969
  FOR_EACH_REFERENCED_VAR(var, rvi)
970
    {
971
      var_ann_t ann = var_ann (var);
972
      NUM_REFERENCES_CLEAR (ann);
973
    }
974
 
975
  free (ai->addressable_vars);
976
 
977
  for (i = 0; i < ai->num_pointers; i++)
978
    free (ai->pointers[i]);
979
  free (ai->pointers);
980
 
981
  BITMAP_FREE (ai->written_vars);
982
  BITMAP_FREE (ai->dereferenced_ptrs_store);
983
  BITMAP_FREE (ai->dereferenced_ptrs_load);
984
  bitmap_obstack_release (&alias_obstack);
985
  free (ai);
986
 
987
  delete_points_to_sets ();
988
}
989
 
990
/* Used for hashing to identify pointer infos with identical
991
   pt_vars bitmaps.  */
992
static int
993
eq_ptr_info (const void *p1, const void *p2)
994
{
995
  const struct ptr_info_def *n1 = (const struct ptr_info_def *) p1;
996
  const struct ptr_info_def *n2 = (const struct ptr_info_def *) p2;
997
  return bitmap_equal_p (n1->pt_vars, n2->pt_vars);
998
}
999
 
1000
static hashval_t
1001
ptr_info_hash (const void *p)
1002
{
1003
  const struct ptr_info_def *n = (const struct ptr_info_def *) p;
1004
  return bitmap_hash (n->pt_vars);
1005
}
1006
 
1007
/* Create name tags for all the pointers that have been dereferenced.
1008
   We only create a name tag for a pointer P if P is found to point to
1009
   a set of variables (so that we can alias them to *P) or if it is
1010
   the result of a call to malloc (which means that P cannot point to
1011
   anything else nor alias any other variable).
1012
 
1013
   If two pointers P and Q point to the same set of variables, they
1014
   are assigned the same name tag.  */
1015
 
1016
static void
1017
create_name_tags (void)
1018
{
1019
  size_t i;
1020
  VEC (tree, heap) *with_ptvars = NULL;
1021
  tree ptr;
1022
  htab_t ptr_hash;
1023
 
1024
  /* Collect the list of pointers with a non-empty points to set.  */
1025
  for (i = 1; i < num_ssa_names; i++)
1026
    {
1027
      tree ptr = ssa_name (i);
1028
      struct ptr_info_def *pi;
1029
 
1030
      if (!ptr
1031
          || !POINTER_TYPE_P (TREE_TYPE (ptr))
1032
          || !SSA_NAME_PTR_INFO (ptr))
1033
        continue;
1034
 
1035
      pi = SSA_NAME_PTR_INFO (ptr);
1036
 
1037
      if (pi->pt_anything || !pi->is_dereferenced)
1038
        {
1039
          /* No name tags for pointers that have not been
1040
             dereferenced or point to an arbitrary location.  */
1041
          pi->name_mem_tag = NULL_TREE;
1042
          continue;
1043
        }
1044
 
1045
      /* Set pt_anything on the pointers without pt_vars filled in so
1046
         that they are assigned a symbol tag.  */
1047
      if (pi->pt_vars && !bitmap_empty_p (pi->pt_vars))
1048
        VEC_safe_push (tree, heap, with_ptvars, ptr);
1049
      else
1050
        set_pt_anything (ptr);
1051
    }
1052
 
1053
  /* If we didn't find any pointers with pt_vars set, we're done.  */
1054
  if (!with_ptvars)
1055
    return;
1056
 
1057
  ptr_hash = htab_create (10, ptr_info_hash, eq_ptr_info, NULL);
1058
  /* Now go through the pointers with pt_vars, and find a name tag
1059
     with the same pt_vars as this pointer, or create one if one
1060
     doesn't exist.  */
1061
  for (i = 0; VEC_iterate (tree, with_ptvars, i, ptr); i++)
1062
    {
1063
      struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
1064
      tree old_name_tag = pi->name_mem_tag;
1065
      struct ptr_info_def **slot;
1066
 
1067
      /* If PTR points to a set of variables, check if we don't
1068
         have another pointer Q with the same points-to set before
1069
         creating a tag.  If so, use Q's tag instead of creating a
1070
         new one.
1071
 
1072
         This is important for not creating unnecessary symbols
1073
         and also for copy propagation.  If we ever need to
1074
         propagate PTR into Q or vice-versa, we would run into
1075
         problems if they both had different name tags because
1076
         they would have different SSA version numbers (which
1077
         would force us to take the name tags in and out of SSA).  */
1078
 
1079
      slot = (struct ptr_info_def **) htab_find_slot (ptr_hash, pi, INSERT);
1080
      if (*slot)
1081
        pi->name_mem_tag = (*slot)->name_mem_tag;
1082
      else
1083
        {
1084
          *slot = pi;
1085
          /* If we didn't find a pointer with the same points-to set
1086
             as PTR, create a new name tag if needed.  */
1087
          if (pi->name_mem_tag == NULL_TREE)
1088
            pi->name_mem_tag = get_nmt_for (ptr);
1089
        }
1090
 
1091
      /* If the new name tag computed for PTR is different than
1092
         the old name tag that it used to have, then the old tag
1093
         needs to be removed from the IL, so we mark it for
1094
         renaming.  */
1095
      if (old_name_tag && old_name_tag != pi->name_mem_tag)
1096
        mark_sym_for_renaming (old_name_tag);
1097
 
1098
      TREE_THIS_VOLATILE (pi->name_mem_tag)
1099
        |= TREE_THIS_VOLATILE (TREE_TYPE (TREE_TYPE (ptr)));
1100
 
1101
      /* Mark the new name tag for renaming.  */
1102
      mark_sym_for_renaming (pi->name_mem_tag);
1103
    }
1104
  htab_delete (ptr_hash);
1105
 
1106
  VEC_free (tree, heap, with_ptvars);
1107
}
1108
 
1109
 
1110
/* For every pointer P_i in AI->PROCESSED_PTRS, create may-alias sets for
1111
   the name memory tag (NMT) associated with P_i.  If P_i escapes, then its
1112
   name tag and the variables it points-to are call-clobbered.  Finally, if
1113
   P_i escapes and we could not determine where it points to, then all the
1114
   variables in the same alias set as *P_i are marked call-clobbered.  This
1115
   is necessary because we must assume that P_i may take the address of any
1116
   variable in the same alias set.  */
1117
 
1118
static void
1119
compute_flow_sensitive_aliasing (struct alias_info *ai)
1120
{
1121
  size_t i;
1122
  tree ptr;
1123
 
1124
  for (i = 0; VEC_iterate (tree, ai->processed_ptrs, i, ptr); i++)
1125
    {
1126
      if (!find_what_p_points_to (ptr))
1127
        set_pt_anything (ptr);
1128
    }
1129
 
1130
  create_name_tags ();
1131
 
1132
  for (i = 0; VEC_iterate (tree, ai->processed_ptrs, i, ptr); i++)
1133
    {
1134
      unsigned j;
1135
      struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
1136
      var_ann_t v_ann = var_ann (SSA_NAME_VAR (ptr));
1137
      bitmap_iterator bi;
1138
 
1139
 
1140
      /* Set up aliasing information for PTR's name memory tag (if it has
1141
         one).  Note that only pointers that have been dereferenced will
1142
         have a name memory tag.  */
1143
      if (pi->name_mem_tag && pi->pt_vars)
1144
        EXECUTE_IF_SET_IN_BITMAP (pi->pt_vars, 0, j, bi)
1145
          {
1146
            add_may_alias (pi->name_mem_tag, referenced_var (j));
1147
            add_may_alias (v_ann->symbol_mem_tag, referenced_var (j));
1148
          }
1149
    }
1150
}
1151
 
1152
 
1153
/* Compute type-based alias sets.  Traverse all the pointers and
1154
   addressable variables found in setup_pointers_and_addressables.
1155
 
1156
   For every pointer P in AI->POINTERS and addressable variable V in
1157
   AI->ADDRESSABLE_VARS, add V to the may-alias sets of P's symbol
1158
   memory tag (SMT) if their alias sets conflict.  V is then marked as
1159
   an alias tag so that the operand scanner knows that statements
1160
   containing V have aliased operands.  */
1161
 
1162
static void
1163
compute_flow_insensitive_aliasing (struct alias_info *ai)
1164
{
1165
  size_t i;
1166
 
1167
  /* Initialize counter for the total number of virtual operands that
1168
     aliasing will introduce.  When AI->TOTAL_ALIAS_VOPS goes beyond the
1169
     threshold set by --params max-alias-vops, we enable alias
1170
     grouping.  */
1171
  ai->total_alias_vops = 0;
1172
 
1173
  /* For every pointer P, determine which addressable variables may alias
1174
     with P's symbol memory tag.  */
1175
  for (i = 0; i < ai->num_pointers; i++)
1176
    {
1177
      size_t j;
1178
      struct alias_map_d *p_map = ai->pointers[i];
1179
      tree tag = var_ann (p_map->var)->symbol_mem_tag;
1180
      var_ann_t tag_ann = var_ann (tag);
1181
      tree var;
1182
 
1183
      /* Call-clobbering information is not finalized yet at this point.  */
1184
      if (PTR_IS_REF_ALL (p_map->var))
1185
        continue;
1186
 
1187
      p_map->total_alias_vops = 0;
1188
      p_map->may_aliases = BITMAP_ALLOC (&alias_obstack);
1189
 
1190
      /* Add any pre-existing may_aliases to the bitmap used to represent
1191
         TAG's alias set in case we need to group aliases.  */
1192
      for (j = 0; VEC_iterate (tree, tag_ann->may_aliases, j, var); ++j)
1193
        bitmap_set_bit (p_map->may_aliases, DECL_UID (var));
1194
 
1195
      for (j = 0; j < ai->num_addressable_vars; j++)
1196
        {
1197
          struct alias_map_d *v_map;
1198
          var_ann_t v_ann;
1199
          bool tag_stored_p, var_stored_p;
1200
 
1201
          v_map = ai->addressable_vars[j];
1202
          var = v_map->var;
1203
          v_ann = var_ann (var);
1204
 
1205
          /* Skip memory tags and variables that have never been
1206
             written to.  We also need to check if the variables are
1207
             call-clobbered because they may be overwritten by
1208
             function calls.
1209
 
1210
             Note this is effectively random accessing elements in
1211
             the sparse bitset, which can be highly inefficient.
1212
             So we first check the call_clobbered status of the
1213
             tag and variable before querying the bitmap.  */
1214
          tag_stored_p = is_call_clobbered (tag)
1215
                         || bitmap_bit_p (ai->written_vars, DECL_UID (tag));
1216
          var_stored_p = is_call_clobbered (var)
1217
                         || bitmap_bit_p (ai->written_vars, DECL_UID (var));
1218
          if (!tag_stored_p && !var_stored_p)
1219
            continue;
1220
 
1221
          if (may_alias_p (p_map->var, p_map->set, var, v_map->set, false))
1222
            {
1223
              size_t num_tag_refs, num_var_refs;
1224
 
1225
              num_tag_refs = NUM_REFERENCES (tag_ann);
1226
              num_var_refs = NUM_REFERENCES (v_ann);
1227
 
1228
              /* Add VAR to TAG's may-aliases set.  */
1229
 
1230
              /* We should never have a var with subvars here, because
1231
                 they shouldn't get into the set of addressable vars */
1232
              gcc_assert (!var_can_have_subvars (var)
1233
                          || get_subvars_for_var (var) == NULL);
1234
 
1235
              add_may_alias (tag, var);
1236
              /* Update the bitmap used to represent TAG's alias set
1237
                 in case we need to group aliases.  */
1238
              bitmap_set_bit (p_map->may_aliases, DECL_UID (var));
1239
 
1240
              /* Update the total number of virtual operands due to
1241
                 aliasing.  Since we are adding one more alias to TAG's
1242
                 may-aliases set, the total number of virtual operands due
1243
                 to aliasing will be increased by the number of references
1244
                 made to VAR and TAG (every reference to TAG will also
1245
                 count as a reference to VAR).  */
1246
              ai->total_alias_vops += (num_var_refs + num_tag_refs);
1247
              p_map->total_alias_vops += (num_var_refs + num_tag_refs);
1248
 
1249
 
1250
            }
1251
        }
1252
    }
1253
 
1254
  /* Since this analysis is based exclusively on symbols, it fails to
1255
     handle cases where two pointers P and Q have different memory
1256
     tags with conflicting alias set numbers but no aliased symbols in
1257
     common.
1258
 
1259
     For example, suppose that we have two memory tags SMT.1 and SMT.2
1260
     such that
1261
 
1262
                may-aliases (SMT.1) = { a }
1263
                may-aliases (SMT.2) = { b }
1264
 
1265
     and the alias set number of SMT.1 conflicts with that of SMT.2.
1266
     Since they don't have symbols in common, loads and stores from
1267
     SMT.1 and SMT.2 will seem independent of each other, which will
1268
     lead to the optimizers making invalid transformations (see
1269
     testsuite/gcc.c-torture/execute/pr15262-[12].c).
1270
 
1271
     To avoid this problem, we do a final traversal of AI->POINTERS
1272
     looking for pairs of pointers that have no aliased symbols in
1273
     common and yet have conflicting alias set numbers.  */
1274
  for (i = 0; i < ai->num_pointers; i++)
1275
    {
1276
      size_t j;
1277
      struct alias_map_d *p_map1 = ai->pointers[i];
1278
      tree tag1 = var_ann (p_map1->var)->symbol_mem_tag;
1279
      bitmap may_aliases1 = p_map1->may_aliases;
1280
 
1281
      if (PTR_IS_REF_ALL (p_map1->var))
1282
        continue;
1283
 
1284
      for (j = i + 1; j < ai->num_pointers; j++)
1285
        {
1286
          struct alias_map_d *p_map2 = ai->pointers[j];
1287
          tree tag2 = var_ann (p_map2->var)->symbol_mem_tag;
1288
          bitmap may_aliases2 = p_map2->may_aliases;
1289
 
1290
          if (PTR_IS_REF_ALL (p_map2->var))
1291
            continue;
1292
 
1293
          /* If the pointers may not point to each other, do nothing.  */
1294
          if (!may_alias_p (p_map1->var, p_map1->set, tag2, p_map2->set, true))
1295
            continue;
1296
 
1297
          /* The two pointers may alias each other.  If they already have
1298
             symbols in common, do nothing.  */
1299
          if (bitmap_intersect_p (may_aliases1, may_aliases2))
1300
            continue;
1301
 
1302
          if (!bitmap_empty_p (may_aliases2))
1303
            {
1304
              unsigned int k;
1305
              bitmap_iterator bi;
1306
 
1307
              /* Add all the aliases for TAG2 into TAG1's alias set.
1308
                 FIXME, update grouping heuristic counters.  */
1309
              EXECUTE_IF_SET_IN_BITMAP (may_aliases2, 0, k, bi)
1310
                add_may_alias (tag1, referenced_var (k));
1311
              bitmap_ior_into (may_aliases1, may_aliases2);
1312
            }
1313
          else
1314
            {
1315
              /* Since TAG2 does not have any aliases of its own, add
1316
                 TAG2 itself to the alias set of TAG1.  */
1317
              add_may_alias (tag1, tag2);
1318
              bitmap_set_bit (may_aliases1, DECL_UID (tag2));
1319
            }
1320
        }
1321
    }
1322
 
1323
  if (dump_file)
1324
    fprintf (dump_file, "\n%s: Total number of aliased vops: %ld\n",
1325
             get_name (current_function_decl),
1326
             ai->total_alias_vops);
1327
}
1328
 
1329
 
1330
/* Finalize may-alias information for ref-all pointers.  Traverse all
1331
   the addressable variables found in setup_pointers_and_addressables.
1332
 
1333
   If flow-sensitive alias analysis has attached a name memory tag to
1334
   a ref-all pointer, we will use it for the dereferences because that
1335
   will have more precise aliasing information.  But if there is no
1336
   name tag, we will use a special symbol tag that aliases all the
1337
   call-clobbered addressable variables.  */
1338
 
1339
static void
1340
finalize_ref_all_pointers (struct alias_info *ai)
1341
{
1342
  size_t i;
1343
 
1344
  if (global_var)
1345
    add_may_alias (ai->ref_all_symbol_mem_tag, global_var);
1346
  else
1347
    {
1348
      /* First add the real call-clobbered variables.  */
1349
      for (i = 0; i < ai->num_addressable_vars; i++)
1350
        {
1351
          tree var = ai->addressable_vars[i]->var;
1352
          if (is_call_clobbered (var))
1353
            add_may_alias (ai->ref_all_symbol_mem_tag, var);
1354
        }
1355
 
1356
      /* Then add the call-clobbered pointer memory tags.  See
1357
         compute_flow_insensitive_aliasing for the rationale.  */
1358
      for (i = 0; i < ai->num_pointers; i++)
1359
        {
1360
          tree ptr = ai->pointers[i]->var, tag;
1361
          if (PTR_IS_REF_ALL (ptr))
1362
            continue;
1363
          tag = var_ann (ptr)->symbol_mem_tag;
1364
          if (is_call_clobbered (tag))
1365
            add_may_alias (ai->ref_all_symbol_mem_tag, tag);
1366
        }
1367
    }
1368
}
1369
 
1370
 
1371
/* Comparison function for qsort used in group_aliases.  */
1372
 
1373
static int
1374
total_alias_vops_cmp (const void *p, const void *q)
1375
{
1376
  const struct alias_map_d **p1 = (const struct alias_map_d **)p;
1377
  const struct alias_map_d **p2 = (const struct alias_map_d **)q;
1378
  long n1 = (*p1)->total_alias_vops;
1379
  long n2 = (*p2)->total_alias_vops;
1380
 
1381
  /* We want to sort in descending order.  */
1382
  return (n1 > n2 ? -1 : (n1 == n2) ? 0 : 1);
1383
}
1384
 
1385
/* Group all the aliases for TAG to make TAG represent all the
1386
   variables in its alias set.  Update the total number
1387
   of virtual operands due to aliasing (AI->TOTAL_ALIAS_VOPS).  This
1388
   function will make TAG be the unique alias tag for all the
1389
   variables in its may-aliases.  So, given:
1390
 
1391
        may-aliases(TAG) = { V1, V2, V3 }
1392
 
1393
   This function will group the variables into:
1394
 
1395
        may-aliases(V1) = { TAG }
1396
        may-aliases(V2) = { TAG }
1397
        may-aliases(V2) = { TAG }  */
1398
 
1399
static void
1400
group_aliases_into (tree tag, bitmap tag_aliases, struct alias_info *ai)
1401
{
1402
  unsigned int i;
1403
  var_ann_t tag_ann = var_ann (tag);
1404
  size_t num_tag_refs = NUM_REFERENCES (tag_ann);
1405
  bitmap_iterator bi;
1406
 
1407
  EXECUTE_IF_SET_IN_BITMAP (tag_aliases, 0, i, bi)
1408
    {
1409
      tree var = referenced_var (i);
1410
      var_ann_t ann = var_ann (var);
1411
 
1412
      /* Make TAG the unique alias of VAR.  */
1413
      ann->is_aliased = 0;
1414
      ann->may_aliases = NULL;
1415
 
1416
      /* Note that VAR and TAG may be the same if the function has no
1417
         addressable variables (see the discussion at the end of
1418
         setup_pointers_and_addressables).  */
1419
      if (var != tag)
1420
        add_may_alias (var, tag);
1421
 
1422
      /* Reduce total number of virtual operands contributed
1423
         by TAG on behalf of VAR.  Notice that the references to VAR
1424
         itself won't be removed.  We will merely replace them with
1425
         references to TAG.  */
1426
      ai->total_alias_vops -= num_tag_refs;
1427
    }
1428
 
1429
  /* We have reduced the number of virtual operands that TAG makes on
1430
     behalf of all the variables formerly aliased with it.  However,
1431
     we have also "removed" all the virtual operands for TAG itself,
1432
     so we add them back.  */
1433
  ai->total_alias_vops += num_tag_refs;
1434
 
1435
  /* TAG no longer has any aliases.  */
1436
  tag_ann->may_aliases = NULL;
1437
}
1438
 
1439
 
1440
/* Group may-aliases sets to reduce the number of virtual operands due
1441
   to aliasing.
1442
 
1443
     1- Sort the list of pointers in decreasing number of contributed
1444
        virtual operands.
1445
 
1446
     2- Take the first entry in AI->POINTERS and revert the role of
1447
        the memory tag and its aliases.  Usually, whenever an aliased
1448
        variable Vi is found to alias with a memory tag T, we add Vi
1449
        to the may-aliases set for T.  Meaning that after alias
1450
        analysis, we will have:
1451
 
1452
                may-aliases(T) = { V1, V2, V3, ..., Vn }
1453
 
1454
        This means that every statement that references T, will get 'n'
1455
        virtual operands for each of the Vi tags.  But, when alias
1456
        grouping is enabled, we make T an alias tag and add it to the
1457
        alias set of all the Vi variables:
1458
 
1459
                may-aliases(V1) = { T }
1460
                may-aliases(V2) = { T }
1461
                ...
1462
                may-aliases(Vn) = { T }
1463
 
1464
        This has two effects: (a) statements referencing T will only get
1465
        a single virtual operand, and, (b) all the variables Vi will now
1466
        appear to alias each other.  So, we lose alias precision to
1467
        improve compile time.  But, in theory, a program with such a high
1468
        level of aliasing should not be very optimizable in the first
1469
        place.
1470
 
1471
     3- Since variables may be in the alias set of more than one
1472
        memory tag, the grouping done in step (2) needs to be extended
1473
        to all the memory tags that have a non-empty intersection with
1474
        the may-aliases set of tag T.  For instance, if we originally
1475
        had these may-aliases sets:
1476
 
1477
                may-aliases(T) = { V1, V2, V3 }
1478
                may-aliases(R) = { V2, V4 }
1479
 
1480
        In step (2) we would have reverted the aliases for T as:
1481
 
1482
                may-aliases(V1) = { T }
1483
                may-aliases(V2) = { T }
1484
                may-aliases(V3) = { T }
1485
 
1486
        But note that now V2 is no longer aliased with R.  We could
1487
        add R to may-aliases(V2), but we are in the process of
1488
        grouping aliases to reduce virtual operands so what we do is
1489
        add V4 to the grouping to obtain:
1490
 
1491
                may-aliases(V1) = { T }
1492
                may-aliases(V2) = { T }
1493
                may-aliases(V3) = { T }
1494
                may-aliases(V4) = { T }
1495
 
1496
     4- If the total number of virtual operands due to aliasing is
1497
        still above the threshold set by max-alias-vops, go back to (2).  */
1498
 
1499
static void
1500
group_aliases (struct alias_info *ai)
1501
{
1502
  size_t i;
1503
  tree ptr;
1504
 
1505
  /* Sort the POINTERS array in descending order of contributed
1506
     virtual operands.  */
1507
  qsort (ai->pointers, ai->num_pointers, sizeof (struct alias_map_d *),
1508
         total_alias_vops_cmp);
1509
 
1510
  /* For every pointer in AI->POINTERS, reverse the roles of its tag
1511
     and the tag's may-aliases set.  */
1512
  for (i = 0; i < ai->num_pointers; i++)
1513
    {
1514
      size_t j;
1515
      tree tag1 = var_ann (ai->pointers[i]->var)->symbol_mem_tag;
1516
      bitmap tag1_aliases = ai->pointers[i]->may_aliases;
1517
 
1518
      /* Skip tags that have been grouped already.  */
1519
      if (ai->pointers[i]->grouped_p)
1520
        continue;
1521
 
1522
      /* See if TAG1 had any aliases in common with other symbol tags.
1523
         If we find a TAG2 with common aliases with TAG1, add TAG2's
1524
         aliases into TAG1.  */
1525
      for (j = i + 1; j < ai->num_pointers; j++)
1526
        {
1527
          bitmap tag2_aliases = ai->pointers[j]->may_aliases;
1528
 
1529
          if (bitmap_intersect_p (tag1_aliases, tag2_aliases))
1530
            {
1531
              tree tag2 = var_ann (ai->pointers[j]->var)->symbol_mem_tag;
1532
 
1533
              bitmap_ior_into (tag1_aliases, tag2_aliases);
1534
 
1535
              /* TAG2 does not need its aliases anymore.  */
1536
              bitmap_clear (tag2_aliases);
1537
              var_ann (tag2)->may_aliases = NULL;
1538
 
1539
              /* TAG1 is the unique alias of TAG2.  */
1540
              add_may_alias (tag2, tag1);
1541
 
1542
              ai->pointers[j]->grouped_p = true;
1543
            }
1544
        }
1545
 
1546
      /* Now group all the aliases we collected into TAG1.  */
1547
      group_aliases_into (tag1, tag1_aliases, ai);
1548
 
1549
      /* If we've reduced total number of virtual operands below the
1550
         threshold, stop.  */
1551
      if (ai->total_alias_vops < MAX_ALIASED_VOPS)
1552
        break;
1553
    }
1554
 
1555
  /* Finally, all the variables that have been grouped cannot be in
1556
     the may-alias set of name memory tags.  Suppose that we have
1557
     grouped the aliases in this code so that may-aliases(a) = SMT.20
1558
 
1559
        p_5 = &a;
1560
        ...
1561
        # a_9 = V_MAY_DEF <a_8>
1562
        p_5->field = 0
1563
        ... Several modifications to SMT.20 ...
1564
        # VUSE <a_9>
1565
        x_30 = p_5->field
1566
 
1567
     Since p_5 points to 'a', the optimizers will try to propagate 0
1568
     into p_5->field, but that is wrong because there have been
1569
     modifications to 'SMT.20' in between.  To prevent this we have to
1570
     replace 'a' with 'SMT.20' in the name tag of p_5.  */
1571
  for (i = 0; VEC_iterate (tree, ai->processed_ptrs, i, ptr); i++)
1572
    {
1573
      size_t j;
1574
      tree name_tag = SSA_NAME_PTR_INFO (ptr)->name_mem_tag;
1575
      VEC(tree,gc) *aliases;
1576
      tree alias;
1577
 
1578
      if (name_tag == NULL_TREE)
1579
        continue;
1580
 
1581
      aliases = var_ann (name_tag)->may_aliases;
1582
      for (j = 0; VEC_iterate (tree, aliases, j, alias); j++)
1583
        {
1584
          var_ann_t ann = var_ann (alias);
1585
 
1586
          if ((!MTAG_P (alias)
1587
               || TREE_CODE (alias) == STRUCT_FIELD_TAG)
1588
              && ann->may_aliases)
1589
            {
1590
              tree new_alias;
1591
 
1592
              gcc_assert (VEC_length (tree, ann->may_aliases) == 1);
1593
 
1594
              new_alias = VEC_index (tree, ann->may_aliases, 0);
1595
              replace_may_alias (name_tag, j, new_alias);
1596
            }
1597
        }
1598
    }
1599
 
1600
  if (dump_file)
1601
    fprintf (dump_file,
1602
             "%s: Total number of aliased vops after grouping: %ld%s\n",
1603
             get_name (current_function_decl),
1604
             ai->total_alias_vops,
1605
             (ai->total_alias_vops < 0) ? " (negative values are OK)" : "");
1606
}
1607
 
1608
 
1609
/* Create a new alias set entry for VAR in AI->ADDRESSABLE_VARS.  */
1610
 
1611
static void
1612
create_alias_map_for (tree var, struct alias_info *ai)
1613
{
1614
  struct alias_map_d *alias_map;
1615
  alias_map = XCNEW (struct alias_map_d);
1616
  alias_map->var = var;
1617
  alias_map->set = get_alias_set (var);
1618
  ai->addressable_vars[ai->num_addressable_vars++] = alias_map;
1619
}
1620
 
1621
 
1622
/* Create memory tags for all the dereferenced pointers and build the
1623
   ADDRESSABLE_VARS and POINTERS arrays used for building the may-alias
1624
   sets.  Based on the address escape and points-to information collected
1625
   earlier, this pass will also clear the TREE_ADDRESSABLE flag from those
1626
   variables whose address is not needed anymore.  */
1627
 
1628
static void
1629
setup_pointers_and_addressables (struct alias_info *ai)
1630
{
1631
  size_t n_vars, num_addressable_vars, num_pointers;
1632
  referenced_var_iterator rvi;
1633
  tree var;
1634
  VEC (tree, heap) *varvec = NULL;
1635
  safe_referenced_var_iterator srvi;
1636
 
1637
  /* Size up the arrays ADDRESSABLE_VARS and POINTERS.  */
1638
  num_addressable_vars = num_pointers = 0;
1639
 
1640
  FOR_EACH_REFERENCED_VAR (var, rvi)
1641
    {
1642
      if (may_be_aliased (var))
1643
        num_addressable_vars++;
1644
 
1645
      if (POINTER_TYPE_P (TREE_TYPE (var)))
1646
        {
1647
          /* Since we don't keep track of volatile variables, assume that
1648
             these pointers are used in indirect store operations.  */
1649
          if (TREE_THIS_VOLATILE (var))
1650
            bitmap_set_bit (ai->dereferenced_ptrs_store, DECL_UID (var));
1651
 
1652
          num_pointers++;
1653
        }
1654
    }
1655
 
1656
  /* Create ADDRESSABLE_VARS and POINTERS.  Note that these arrays are
1657
     always going to be slightly bigger than we actually need them
1658
     because some TREE_ADDRESSABLE variables will be marked
1659
     non-addressable below and only pointers with unique symbol tags are
1660
     going to be added to POINTERS.  */
1661
  ai->addressable_vars = XCNEWVEC (struct alias_map_d *, num_addressable_vars);
1662
  ai->pointers = XCNEWVEC (struct alias_map_d *, num_pointers);
1663
  ai->num_addressable_vars = 0;
1664
  ai->num_pointers = 0;
1665
 
1666
  /* Since we will be creating symbol memory tags within this loop,
1667
     cache the value of NUM_REFERENCED_VARS to avoid processing the
1668
     additional tags unnecessarily.  */
1669
  n_vars = num_referenced_vars;
1670
 
1671
  FOR_EACH_REFERENCED_VAR_SAFE (var, varvec, srvi)
1672
    {
1673
      var_ann_t v_ann = var_ann (var);
1674
      subvar_t svars;
1675
 
1676
      /* Name memory tags already have flow-sensitive aliasing
1677
         information, so they need not be processed by
1678
         compute_flow_insensitive_aliasing.  Similarly, symbol memory
1679
         tags are already accounted for when we process their
1680
         associated pointer.
1681
 
1682
         Structure fields, on the other hand, have to have some of this
1683
         information processed for them, but it's pointless to mark them
1684
         non-addressable (since they are fake variables anyway).  */
1685
      if (MTAG_P (var) && TREE_CODE (var) != STRUCT_FIELD_TAG)
1686
        continue;
1687
 
1688
      /* Remove the ADDRESSABLE flag from every addressable variable whose
1689
         address is not needed anymore.  This is caused by the propagation
1690
         of ADDR_EXPR constants into INDIRECT_REF expressions and the
1691
         removal of dead pointer assignments done by the early scalar
1692
         cleanup passes.  */
1693
      if (TREE_ADDRESSABLE (var))
1694
        {
1695
          if (!bitmap_bit_p (addressable_vars, DECL_UID (var))
1696
              && TREE_CODE (var) != RESULT_DECL
1697
              && !is_global_var (var))
1698
            {
1699
              bool okay_to_mark = true;
1700
 
1701
              /* Since VAR is now a regular GIMPLE register, we will need
1702
                 to rename VAR into SSA afterwards.  */
1703
              mark_sym_for_renaming (var);
1704
 
1705
              /* If VAR can have sub-variables, and any of its
1706
                 sub-variables has its address taken, then we cannot
1707
                 remove the addressable flag from VAR.  */
1708
              if (var_can_have_subvars (var)
1709
                  && (svars = get_subvars_for_var (var)))
1710
                {
1711
                  subvar_t sv;
1712
 
1713
                  for (sv = svars; sv; sv = sv->next)
1714
                    {
1715
                      if (bitmap_bit_p (addressable_vars, DECL_UID (sv->var)))
1716
                        okay_to_mark = false;
1717
                      mark_sym_for_renaming (sv->var);
1718
                    }
1719
                }
1720
 
1721
              /* The address of VAR is not needed, remove the
1722
                 addressable bit, so that it can be optimized as a
1723
                 regular variable.  */
1724
              if (okay_to_mark)
1725
                mark_non_addressable (var);
1726
            }
1727
        }
1728
 
1729
      /* Global variables and addressable locals may be aliased.  Create an
1730
         entry in ADDRESSABLE_VARS for VAR.  */
1731
      if (may_be_aliased (var)
1732
          && (!var_can_have_subvars (var)
1733
              || get_subvars_for_var (var) == NULL))
1734
        {
1735
          create_alias_map_for (var, ai);
1736
          mark_sym_for_renaming (var);
1737
        }
1738
 
1739
      /* Add pointer variables that have been dereferenced to the POINTERS
1740
         array and create a symbol memory tag for them.  */
1741
      if (POINTER_TYPE_P (TREE_TYPE (var)))
1742
        {
1743
          if ((bitmap_bit_p (ai->dereferenced_ptrs_store, DECL_UID (var))
1744
               || bitmap_bit_p (ai->dereferenced_ptrs_load, DECL_UID (var))))
1745
            {
1746
              tree tag;
1747
              var_ann_t t_ann;
1748
 
1749
              /* If pointer VAR still doesn't have a memory tag
1750
                 associated with it, create it now or re-use an
1751
                 existing one.  */
1752
              tag = get_tmt_for (var, ai);
1753
              t_ann = var_ann (tag);
1754
 
1755
              /* The symbol tag will need to be renamed into SSA
1756
                 afterwards. Note that we cannot do this inside
1757
                 get_tmt_for because aliasing may run multiple times
1758
                 and we only create symbol tags the first time.  */
1759
              mark_sym_for_renaming (tag);
1760
 
1761
              /* Similarly, if pointer VAR used to have another type
1762
                 tag, we will need to process it in the renamer to
1763
                 remove the stale virtual operands.  */
1764
              if (v_ann->symbol_mem_tag)
1765
                mark_sym_for_renaming (v_ann->symbol_mem_tag);
1766
 
1767
              /* Associate the tag with pointer VAR.  */
1768
              v_ann->symbol_mem_tag = tag;
1769
 
1770
              /* If pointer VAR has been used in a store operation,
1771
                 then its memory tag must be marked as written-to.  */
1772
              if (bitmap_bit_p (ai->dereferenced_ptrs_store, DECL_UID (var)))
1773
                bitmap_set_bit (ai->written_vars, DECL_UID (tag));
1774
 
1775
              /* All the dereferences of pointer VAR count as
1776
                 references of TAG.  Since TAG can be associated with
1777
                 several pointers, add the dereferences of VAR to the
1778
                 TAG.  */
1779
              NUM_REFERENCES_SET (t_ann,
1780
                                  NUM_REFERENCES (t_ann)
1781
                                  + NUM_REFERENCES (v_ann));
1782
            }
1783
          else
1784
            {
1785
              /* The pointer has not been dereferenced.  If it had a
1786
                 symbol memory tag, remove it and mark the old tag for
1787
                 renaming to remove it out of the IL.  */
1788
              var_ann_t ann = var_ann (var);
1789
              tree tag = ann->symbol_mem_tag;
1790
              if (tag)
1791
                {
1792
                  mark_sym_for_renaming (tag);
1793
                  ann->symbol_mem_tag = NULL_TREE;
1794
                }
1795
            }
1796
        }
1797
    }
1798
  VEC_free (tree, heap, varvec);
1799
}
1800
 
1801
 
1802
/* Determine whether to use .GLOBAL_VAR to model call clobbering semantics. At
1803
   every call site, we need to emit V_MAY_DEF expressions to represent the
1804
   clobbering effects of the call for variables whose address escapes the
1805
   current function.
1806
 
1807
   One approach is to group all call-clobbered variables into a single
1808
   representative that is used as an alias of every call-clobbered variable
1809
   (.GLOBAL_VAR).  This works well, but it ties the optimizer hands because
1810
   references to any call clobbered variable is a reference to .GLOBAL_VAR.
1811
 
1812
   The second approach is to emit a clobbering V_MAY_DEF for every
1813
   call-clobbered variable at call sites.  This is the preferred way in terms
1814
   of optimization opportunities but it may create too many V_MAY_DEF operands
1815
   if there are many call clobbered variables and function calls in the
1816
   function.
1817
 
1818
   To decide whether or not to use .GLOBAL_VAR we multiply the number of
1819
   function calls found by the number of call-clobbered variables.  If that
1820
   product is beyond a certain threshold, as determined by the parameterized
1821
   values shown below, we use .GLOBAL_VAR.
1822
 
1823
   FIXME.  This heuristic should be improved.  One idea is to use several
1824
   .GLOBAL_VARs of different types instead of a single one.  The thresholds
1825
   have been derived from a typical bootstrap cycle, including all target
1826
   libraries. Compile times were found increase by ~1% compared to using
1827
   .GLOBAL_VAR.  */
1828
 
1829
static void
1830
maybe_create_global_var (struct alias_info *ai)
1831
{
1832
  unsigned i, n_clobbered;
1833
  bitmap_iterator bi;
1834
 
1835
  /* No need to create it, if we have one already.  */
1836
  if (global_var == NULL_TREE)
1837
    {
1838
      /* Count all the call-clobbered variables.  */
1839
      n_clobbered = 0;
1840
      EXECUTE_IF_SET_IN_BITMAP (call_clobbered_vars, 0, i, bi)
1841
        {
1842
          n_clobbered++;
1843
        }
1844
 
1845
      /* If the number of virtual operands that would be needed to
1846
         model all the call-clobbered variables is larger than
1847
         GLOBAL_VAR_THRESHOLD, create .GLOBAL_VAR.
1848
 
1849
         Also create .GLOBAL_VAR if there are no call-clobbered
1850
         variables and the program contains a mixture of pure/const
1851
         and regular function calls.  This is to avoid the problem
1852
         described in PR 20115:
1853
 
1854
              int X;
1855
              int func_pure (void) { return X; }
1856
              int func_non_pure (int a) { X += a; }
1857
              int foo ()
1858
              {
1859
                int a = func_pure ();
1860
                func_non_pure (a);
1861
                a = func_pure ();
1862
                return a;
1863
              }
1864
 
1865
         Since foo() has no call-clobbered variables, there is
1866
         no relationship between the calls to func_pure and
1867
         func_non_pure.  Since func_pure has no side-effects, value
1868
         numbering optimizations elide the second call to func_pure.
1869
         So, if we have some pure/const and some regular calls in the
1870
         program we create .GLOBAL_VAR to avoid missing these
1871
         relations.  */
1872
      if (ai->num_calls_found * n_clobbered >= (size_t) GLOBAL_VAR_THRESHOLD
1873
          || (n_clobbered == 0
1874
              && ai->num_calls_found > 0
1875
              && ai->num_pure_const_calls_found > 0
1876
              && ai->num_calls_found > ai->num_pure_const_calls_found))
1877
        create_global_var ();
1878
    }
1879
 
1880
  /* Mark all call-clobbered symbols for renaming.  Since the initial
1881
     rewrite into SSA ignored all call sites, we may need to rename
1882
     .GLOBAL_VAR and the call-clobbered variables.   */
1883
  EXECUTE_IF_SET_IN_BITMAP (call_clobbered_vars, 0, i, bi)
1884
    {
1885
      tree var = referenced_var (i);
1886
 
1887
      /* If the function has calls to clobbering functions and
1888
         .GLOBAL_VAR has been created, make it an alias for all
1889
         call-clobbered variables.  */
1890
      if (global_var && var != global_var)
1891
        {
1892
          add_may_alias (var, global_var);
1893
          gcc_assert (!get_subvars_for_var (var));
1894
        }
1895
 
1896
      mark_sym_for_renaming (var);
1897
    }
1898
}
1899
 
1900
 
1901
/* Return TRUE if pointer PTR may point to variable VAR.
1902
 
1903
   MEM_ALIAS_SET is the alias set for the memory location pointed-to by PTR
1904
        This is needed because when checking for type conflicts we are
1905
        interested in the alias set of the memory location pointed-to by
1906
        PTR.  The alias set of PTR itself is irrelevant.
1907
 
1908
   VAR_ALIAS_SET is the alias set for VAR.  */
1909
 
1910
static bool
1911
may_alias_p (tree ptr, HOST_WIDE_INT mem_alias_set,
1912
             tree var, HOST_WIDE_INT var_alias_set,
1913
             bool alias_set_only)
1914
{
1915
  tree mem;
1916
 
1917
  alias_stats.alias_queries++;
1918
  alias_stats.simple_queries++;
1919
 
1920
  /* By convention, a variable cannot alias itself.  */
1921
  mem = var_ann (ptr)->symbol_mem_tag;
1922
  if (mem == var)
1923
    {
1924
      alias_stats.alias_noalias++;
1925
      alias_stats.simple_resolved++;
1926
      return false;
1927
    }
1928
 
1929
  /* If -fargument-noalias-global is > 2, pointer arguments may
1930
     not point to anything else.  */
1931
  if (flag_argument_noalias > 2 && TREE_CODE (ptr) == PARM_DECL)
1932
    {
1933
      alias_stats.alias_noalias++;
1934
      alias_stats.simple_resolved++;
1935
      return false;
1936
    }
1937
 
1938
  /* If -fargument-noalias-global is > 1, pointer arguments may
1939
     not point to global variables.  */
1940
  if (flag_argument_noalias > 1 && is_global_var (var)
1941
      && TREE_CODE (ptr) == PARM_DECL)
1942
    {
1943
      alias_stats.alias_noalias++;
1944
      alias_stats.simple_resolved++;
1945
      return false;
1946
    }
1947
 
1948
  /* If either MEM or VAR is a read-only global and the other one
1949
     isn't, then PTR cannot point to VAR.  */
1950
  if ((unmodifiable_var_p (mem) && !unmodifiable_var_p (var))
1951
      || (unmodifiable_var_p (var) && !unmodifiable_var_p (mem)))
1952
    {
1953
      alias_stats.alias_noalias++;
1954
      alias_stats.simple_resolved++;
1955
      return false;
1956
    }
1957
 
1958
  gcc_assert (TREE_CODE (mem) == SYMBOL_MEMORY_TAG);
1959
 
1960
  alias_stats.tbaa_queries++;
1961
 
1962
  /* If the alias sets don't conflict then MEM cannot alias VAR.  */
1963
  if (!alias_sets_conflict_p (mem_alias_set, var_alias_set))
1964
    {
1965
      alias_stats.alias_noalias++;
1966
      alias_stats.tbaa_resolved++;
1967
      return false;
1968
    }
1969
 
1970
  /* If var is a record or union type, ptr cannot point into var
1971
     unless there is some operation explicit address operation in the
1972
     program that can reference a field of the ptr's dereferenced
1973
     type.  This also assumes that the types of both var and ptr are
1974
     contained within the compilation unit, and that there is no fancy
1975
     addressing arithmetic associated with any of the types
1976
     involved.  */
1977
 
1978
  if ((mem_alias_set != 0) && (var_alias_set != 0))
1979
    {
1980
      tree ptr_type = TREE_TYPE (ptr);
1981
      tree var_type = TREE_TYPE (var);
1982
 
1983
      /* The star count is -1 if the type at the end of the pointer_to
1984
         chain is not a record or union type. */
1985
      if ((!alias_set_only) &&
1986
          ipa_type_escape_star_count_of_interesting_type (var_type) >= 0)
1987
        {
1988
          int ptr_star_count = 0;
1989
 
1990
          /* Ipa_type_escape_star_count_of_interesting_type is a little to
1991
             restrictive for the pointer type, need to allow pointers to
1992
             primitive types as long as those types cannot be pointers
1993
             to everything.  */
1994
          while (POINTER_TYPE_P (ptr_type))
1995
            /* Strip the *'s off.  */
1996
            {
1997
              ptr_type = TREE_TYPE (ptr_type);
1998
              ptr_star_count++;
1999
            }
2000
 
2001
          /* There does not appear to be a better test to see if the
2002
             pointer type was one of the pointer to everything
2003
             types.  */
2004
 
2005
          if (ptr_star_count > 0)
2006
            {
2007
              alias_stats.structnoaddress_queries++;
2008
              if (ipa_type_escape_field_does_not_clobber_p (var_type,
2009
                                                            TREE_TYPE (ptr)))
2010
                {
2011
                  alias_stats.structnoaddress_resolved++;
2012
                  alias_stats.alias_noalias++;
2013
                  return false;
2014
                }
2015
            }
2016
          else if (ptr_star_count == 0)
2017
            {
2018
              /* If ptr_type was not really a pointer to type, it cannot
2019
                 alias.  */
2020
              alias_stats.structnoaddress_queries++;
2021
              alias_stats.structnoaddress_resolved++;
2022
              alias_stats.alias_noalias++;
2023
              return false;
2024
            }
2025
        }
2026
    }
2027
 
2028
  alias_stats.alias_mayalias++;
2029
  return true;
2030
}
2031
 
2032
 
2033
/* Add ALIAS to the set of variables that may alias VAR.  */
2034
 
2035
static void
2036
add_may_alias (tree var, tree alias)
2037
{
2038
  size_t i;
2039
  var_ann_t v_ann = get_var_ann (var);
2040
  var_ann_t a_ann = get_var_ann (alias);
2041
  tree al;
2042
 
2043
  /* Don't allow self-referential aliases.  */
2044
  gcc_assert (var != alias);
2045
 
2046
  /* ALIAS must be addressable if it's being added to an alias set.  */
2047
#if 1
2048
  TREE_ADDRESSABLE (alias) = 1;
2049
#else
2050
  gcc_assert (may_be_aliased (alias));
2051
#endif
2052
 
2053
  if (v_ann->may_aliases == NULL)
2054
    v_ann->may_aliases = VEC_alloc (tree, gc, 2);
2055
 
2056
  /* Avoid adding duplicates.  */
2057
  for (i = 0; VEC_iterate (tree, v_ann->may_aliases, i, al); i++)
2058
    if (alias == al)
2059
      return;
2060
 
2061
  VEC_safe_push (tree, gc, v_ann->may_aliases, alias);
2062
  a_ann->is_aliased = 1;
2063
}
2064
 
2065
 
2066
/* Replace alias I in the alias sets of VAR with NEW_ALIAS.  */
2067
 
2068
static void
2069
replace_may_alias (tree var, size_t i, tree new_alias)
2070
{
2071
  var_ann_t v_ann = var_ann (var);
2072
  VEC_replace (tree, v_ann->may_aliases, i, new_alias);
2073
}
2074
 
2075
 
2076
/* Mark pointer PTR as pointing to an arbitrary memory location.  */
2077
 
2078
static void
2079
set_pt_anything (tree ptr)
2080
{
2081
  struct ptr_info_def *pi = get_ptr_info (ptr);
2082
 
2083
  pi->pt_anything = 1;
2084
  pi->pt_vars = NULL;
2085
 
2086
  /* The pointer used to have a name tag, but we now found it pointing
2087
     to an arbitrary location.  The name tag needs to be renamed and
2088
     disassociated from PTR.  */
2089
  if (pi->name_mem_tag)
2090
    {
2091
      mark_sym_for_renaming (pi->name_mem_tag);
2092
      pi->name_mem_tag = NULL_TREE;
2093
    }
2094
}
2095
 
2096
 
2097
/* Return true if STMT is an "escape" site from the current function.  Escape
2098
   sites those statements which might expose the address of a variable
2099
   outside the current function.  STMT is an escape site iff:
2100
 
2101
        1- STMT is a function call, or
2102
        2- STMT is an __asm__ expression, or
2103
        3- STMT is an assignment to a non-local variable, or
2104
        4- STMT is a return statement.
2105
 
2106
   Return the type of escape site found, if we found one, or NO_ESCAPE
2107
   if none.  */
2108
 
2109
enum escape_type
2110
is_escape_site (tree stmt)
2111
{
2112
  tree call = get_call_expr_in (stmt);
2113
  if (call != NULL_TREE)
2114
    {
2115
      if (!TREE_SIDE_EFFECTS (call))
2116
        return ESCAPE_TO_PURE_CONST;
2117
 
2118
      return ESCAPE_TO_CALL;
2119
    }
2120
  else if (TREE_CODE (stmt) == ASM_EXPR)
2121
    return ESCAPE_TO_ASM;
2122
  else if (TREE_CODE (stmt) == MODIFY_EXPR)
2123
    {
2124
      tree lhs = TREE_OPERAND (stmt, 0);
2125
 
2126
      /* Get to the base of _REF nodes.  */
2127
      if (TREE_CODE (lhs) != SSA_NAME)
2128
        lhs = get_base_address (lhs);
2129
 
2130
      /* If we couldn't recognize the LHS of the assignment, assume that it
2131
         is a non-local store.  */
2132
      if (lhs == NULL_TREE)
2133
        return ESCAPE_UNKNOWN;
2134
 
2135
      if (TREE_CODE (TREE_OPERAND (stmt, 1)) == NOP_EXPR
2136
          || TREE_CODE (TREE_OPERAND (stmt, 1)) == CONVERT_EXPR
2137
          || TREE_CODE (TREE_OPERAND (stmt, 1)) == VIEW_CONVERT_EXPR)
2138
        {
2139
          tree from = TREE_TYPE (TREE_OPERAND (TREE_OPERAND (stmt, 1), 0));
2140
          tree to = TREE_TYPE (TREE_OPERAND (stmt, 1));
2141
 
2142
          /* If the RHS is a conversion between a pointer and an integer, the
2143
             pointer escapes since we can't track the integer.  */
2144
          if (POINTER_TYPE_P (from) && !POINTER_TYPE_P (to))
2145
            return ESCAPE_BAD_CAST;
2146
 
2147
          /* Same if the RHS is a conversion between a regular pointer and a
2148
             ref-all pointer since we can't track the SMT of the former.  */
2149
          if (POINTER_TYPE_P (from) && !TYPE_REF_CAN_ALIAS_ALL (from)
2150
              && POINTER_TYPE_P (to) && TYPE_REF_CAN_ALIAS_ALL (to))
2151
            return ESCAPE_BAD_CAST;
2152
        }
2153
 
2154
      /* If the LHS is an SSA name, it can't possibly represent a non-local
2155
         memory store.  */
2156
      if (TREE_CODE (lhs) == SSA_NAME)
2157
        return NO_ESCAPE;
2158
 
2159
      /* FIXME: LHS is not an SSA_NAME.  Even if it's an assignment to a
2160
         local variables we cannot be sure if it will escape, because we
2161
         don't have information about objects not in SSA form.  Need to
2162
         implement something along the lines of
2163
 
2164
         J.-D. Choi, M. Gupta, M. J. Serrano, V. C. Sreedhar, and S. P.
2165
         Midkiff, ``Escape analysis for java,'' in Proceedings of the
2166
         Conference on Object-Oriented Programming Systems, Languages, and
2167
         Applications (OOPSLA), pp. 1-19, 1999.  */
2168
      return ESCAPE_STORED_IN_GLOBAL;
2169
    }
2170
  else if (TREE_CODE (stmt) == RETURN_EXPR)
2171
    return ESCAPE_TO_RETURN;
2172
 
2173
  return NO_ESCAPE;
2174
}
2175
 
2176
/* Create a new memory tag of type TYPE.
2177
   Does NOT push it into the current binding.  */
2178
 
2179
static tree
2180
create_tag_raw (enum tree_code code, tree type, const char *prefix)
2181
{
2182
  tree tmp_var;
2183
  tree new_type;
2184
 
2185
  /* Make the type of the variable writable.  */
2186
  new_type = build_type_variant (type, 0, 0);
2187
  TYPE_ATTRIBUTES (new_type) = TYPE_ATTRIBUTES (type);
2188
 
2189
  tmp_var = build_decl (code, create_tmp_var_name (prefix),
2190
                        type);
2191
  /* Make the variable writable.  */
2192
  TREE_READONLY (tmp_var) = 0;
2193
 
2194
  /* It doesn't start out global.  */
2195
  MTAG_GLOBAL (tmp_var) = 0;
2196
  TREE_STATIC (tmp_var) = 0;
2197
  TREE_USED (tmp_var) = 1;
2198
 
2199
  return tmp_var;
2200
}
2201
 
2202
/* Create a new memory tag of type TYPE.  If IS_TYPE_TAG is true, the tag
2203
   is considered to represent all the pointers whose pointed-to types are
2204
   in the same alias set class.  Otherwise, the tag represents a single
2205
   SSA_NAME pointer variable.  */
2206
 
2207
static tree
2208
create_memory_tag (tree type, bool is_type_tag)
2209
{
2210
  var_ann_t ann;
2211
  tree tag = create_tag_raw (is_type_tag ? SYMBOL_MEMORY_TAG : NAME_MEMORY_TAG,
2212
                             type, (is_type_tag) ? "SMT" : "NMT");
2213
 
2214
  /* By default, memory tags are local variables.  Alias analysis will
2215
     determine whether they should be considered globals.  */
2216
  DECL_CONTEXT (tag) = current_function_decl;
2217
 
2218
  /* Memory tags are by definition addressable.  */
2219
  TREE_ADDRESSABLE (tag) = 1;
2220
 
2221
  ann = get_var_ann (tag);
2222
  ann->symbol_mem_tag = NULL_TREE;
2223
 
2224
  /* Add the tag to the symbol table.  */
2225
  add_referenced_var (tag);
2226
 
2227
  return tag;
2228
}
2229
 
2230
 
2231
/* Create a name memory tag to represent a specific SSA_NAME pointer P_i.
2232
   This is used if P_i has been found to point to a specific set of
2233
   variables or to a non-aliased memory location like the address returned
2234
   by malloc functions.  */
2235
 
2236
static tree
2237
get_nmt_for (tree ptr)
2238
{
2239
  struct ptr_info_def *pi = get_ptr_info (ptr);
2240
  tree tag = pi->name_mem_tag;
2241
 
2242
  if (tag == NULL_TREE)
2243
    tag = create_memory_tag (TREE_TYPE (TREE_TYPE (ptr)), false);
2244
  return tag;
2245
}
2246
 
2247
 
2248
/* Return the symbol memory tag associated to pointer PTR.  A memory
2249
   tag is an artificial variable that represents the memory location
2250
   pointed-to by PTR.  It is used to model the effects of pointer
2251
   de-references on addressable variables.
2252
 
2253
   AI points to the data gathered during alias analysis.  This
2254
   function populates the array AI->POINTERS.  */
2255
 
2256
static tree
2257
get_tmt_for (tree ptr, struct alias_info *ai)
2258
{
2259
  size_t i;
2260
  tree tag;
2261
  tree tag_type = TREE_TYPE (TREE_TYPE (ptr));
2262
  HOST_WIDE_INT tag_set = get_alias_set (tag_type);
2263
 
2264
  /* We use a unique memory tag for all the ref-all pointers.  */
2265
  if (PTR_IS_REF_ALL (ptr))
2266
    {
2267
      if (!ai->ref_all_symbol_mem_tag)
2268
        ai->ref_all_symbol_mem_tag = create_memory_tag (void_type_node, true);
2269
      return ai->ref_all_symbol_mem_tag;
2270
    }
2271
 
2272
  /* To avoid creating unnecessary memory tags, only create one memory tag
2273
     per alias set class.  Note that it may be tempting to group
2274
     memory tags based on conflicting alias sets instead of
2275
     equivalence.  That would be wrong because alias sets are not
2276
     necessarily transitive (as demonstrated by the libstdc++ test
2277
     23_containers/vector/cons/4.cc).  Given three alias sets A, B, C
2278
     such that conflicts (A, B) == true and conflicts (A, C) == true,
2279
     it does not necessarily follow that conflicts (B, C) == true.  */
2280
  for (i = 0, tag = NULL_TREE; i < ai->num_pointers; i++)
2281
    {
2282
      struct alias_map_d *curr = ai->pointers[i];
2283
      tree curr_tag = var_ann (curr->var)->symbol_mem_tag;
2284
      if (tag_set == curr->set)
2285
        {
2286
          tag = curr_tag;
2287
          break;
2288
        }
2289
    }
2290
 
2291
  /* If VAR cannot alias with any of the existing memory tags, create a new
2292
     tag for PTR and add it to the POINTERS array.  */
2293
  if (tag == NULL_TREE)
2294
    {
2295
      struct alias_map_d *alias_map;
2296
 
2297
      /* If PTR did not have a symbol tag already, create a new SMT.*
2298
         artificial variable representing the memory location
2299
         pointed-to by PTR.  */
2300
      if (var_ann (ptr)->symbol_mem_tag == NULL_TREE)
2301
        tag = create_memory_tag (tag_type, true);
2302
      else
2303
        tag = var_ann (ptr)->symbol_mem_tag;
2304
 
2305
      /* Add PTR to the POINTERS array.  Note that we are not interested in
2306
         PTR's alias set.  Instead, we cache the alias set for the memory that
2307
         PTR points to.  */
2308
      alias_map = XCNEW (struct alias_map_d);
2309
      alias_map->var = ptr;
2310
      alias_map->set = tag_set;
2311
      ai->pointers[ai->num_pointers++] = alias_map;
2312
    }
2313
 
2314
  /* If the pointed-to type is volatile, so is the tag.  */
2315
  TREE_THIS_VOLATILE (tag) |= TREE_THIS_VOLATILE (tag_type);
2316
 
2317
  /* Make sure that the symbol tag has the same alias set as the
2318
     pointed-to type.  */
2319
  gcc_assert (tag_set == get_alias_set (tag));
2320
 
2321
  return tag;
2322
}
2323
 
2324
 
2325
/* Create GLOBAL_VAR, an artificial global variable to act as a
2326
   representative of all the variables that may be clobbered by function
2327
   calls.  */
2328
 
2329
static void
2330
create_global_var (void)
2331
{
2332
  global_var = build_decl (VAR_DECL, get_identifier (".GLOBAL_VAR"),
2333
                           void_type_node);
2334
  DECL_ARTIFICIAL (global_var) = 1;
2335
  TREE_READONLY (global_var) = 0;
2336
  DECL_EXTERNAL (global_var) = 1;
2337
  TREE_STATIC (global_var) = 1;
2338
  TREE_USED (global_var) = 1;
2339
  DECL_CONTEXT (global_var) = NULL_TREE;
2340
  TREE_THIS_VOLATILE (global_var) = 0;
2341
  TREE_ADDRESSABLE (global_var) = 0;
2342
 
2343
  create_var_ann (global_var);
2344
  mark_call_clobbered (global_var, ESCAPE_UNKNOWN);
2345
  add_referenced_var (global_var);
2346
  mark_sym_for_renaming (global_var);
2347
}
2348
 
2349
 
2350
/* Dump alias statistics on FILE.  */
2351
 
2352
static void
2353
dump_alias_stats (FILE *file)
2354
{
2355
  const char *funcname
2356
    = lang_hooks.decl_printable_name (current_function_decl, 2);
2357
  fprintf (file, "\nAlias statistics for %s\n\n", funcname);
2358
  fprintf (file, "Total alias queries:\t%u\n", alias_stats.alias_queries);
2359
  fprintf (file, "Total alias mayalias results:\t%u\n",
2360
           alias_stats.alias_mayalias);
2361
  fprintf (file, "Total alias noalias results:\t%u\n",
2362
           alias_stats.alias_noalias);
2363
  fprintf (file, "Total simple queries:\t%u\n",
2364
           alias_stats.simple_queries);
2365
  fprintf (file, "Total simple resolved:\t%u\n",
2366
           alias_stats.simple_resolved);
2367
  fprintf (file, "Total TBAA queries:\t%u\n",
2368
           alias_stats.tbaa_queries);
2369
  fprintf (file, "Total TBAA resolved:\t%u\n",
2370
           alias_stats.tbaa_resolved);
2371
  fprintf (file, "Total non-addressable structure type queries:\t%u\n",
2372
           alias_stats.structnoaddress_queries);
2373
  fprintf (file, "Total non-addressable structure type resolved:\t%u\n",
2374
           alias_stats.structnoaddress_resolved);
2375
}
2376
 
2377
 
2378
/* Dump alias information on FILE.  */
2379
 
2380
void
2381
dump_alias_info (FILE *file)
2382
{
2383
  size_t i;
2384
  const char *funcname
2385
    = lang_hooks.decl_printable_name (current_function_decl, 2);
2386
  referenced_var_iterator rvi;
2387
  tree var;
2388
 
2389
  fprintf (file, "\nFlow-insensitive alias information for %s\n\n", funcname);
2390
 
2391
  fprintf (file, "Aliased symbols\n\n");
2392
 
2393
  FOR_EACH_REFERENCED_VAR (var, rvi)
2394
    {
2395
      if (may_be_aliased (var))
2396
        dump_variable (file, var);
2397
    }
2398
 
2399
  fprintf (file, "\nDereferenced pointers\n\n");
2400
 
2401
  FOR_EACH_REFERENCED_VAR (var, rvi)
2402
    {
2403
      var_ann_t ann = var_ann (var);
2404
      if (ann->symbol_mem_tag)
2405
        dump_variable (file, var);
2406
    }
2407
 
2408
  fprintf (file, "\nSymbol memory tags\n\n");
2409
 
2410
  FOR_EACH_REFERENCED_VAR (var, rvi)
2411
    {
2412
      if (TREE_CODE (var) == SYMBOL_MEMORY_TAG)
2413
        dump_variable (file, var);
2414
    }
2415
 
2416
  fprintf (file, "\n\nFlow-sensitive alias information for %s\n\n", funcname);
2417
 
2418
  fprintf (file, "SSA_NAME pointers\n\n");
2419
  for (i = 1; i < num_ssa_names; i++)
2420
    {
2421
      tree ptr = ssa_name (i);
2422
      struct ptr_info_def *pi;
2423
 
2424
      if (ptr == NULL_TREE)
2425
        continue;
2426
 
2427
      pi = SSA_NAME_PTR_INFO (ptr);
2428
      if (!SSA_NAME_IN_FREE_LIST (ptr)
2429
          && pi
2430
          && pi->name_mem_tag)
2431
        dump_points_to_info_for (file, ptr);
2432
    }
2433
 
2434
  fprintf (file, "\nName memory tags\n\n");
2435
 
2436
  FOR_EACH_REFERENCED_VAR (var, rvi)
2437
    {
2438
      if (TREE_CODE (var) == NAME_MEMORY_TAG)
2439
        dump_variable (file, var);
2440
    }
2441
 
2442
  fprintf (file, "\n");
2443
}
2444
 
2445
 
2446
/* Dump alias information on stderr.  */
2447
 
2448
void
2449
debug_alias_info (void)
2450
{
2451
  dump_alias_info (stderr);
2452
}
2453
 
2454
 
2455
/* Return the alias information associated with pointer T.  It creates a
2456
   new instance if none existed.  */
2457
 
2458
struct ptr_info_def *
2459
get_ptr_info (tree t)
2460
{
2461
  struct ptr_info_def *pi;
2462
 
2463
  gcc_assert (POINTER_TYPE_P (TREE_TYPE (t)));
2464
 
2465
  pi = SSA_NAME_PTR_INFO (t);
2466
  if (pi == NULL)
2467
    {
2468
      pi = GGC_NEW (struct ptr_info_def);
2469
      memset ((void *)pi, 0, sizeof (*pi));
2470
      SSA_NAME_PTR_INFO (t) = pi;
2471
    }
2472
 
2473
  return pi;
2474
}
2475
 
2476
 
2477
/* Dump points-to information for SSA_NAME PTR into FILE.  */
2478
 
2479
void
2480
dump_points_to_info_for (FILE *file, tree ptr)
2481
{
2482
  struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
2483
 
2484
  print_generic_expr (file, ptr, dump_flags);
2485
 
2486
  if (pi)
2487
    {
2488
      if (pi->name_mem_tag)
2489
        {
2490
          fprintf (file, ", name memory tag: ");
2491
          print_generic_expr (file, pi->name_mem_tag, dump_flags);
2492
        }
2493
 
2494
      if (pi->is_dereferenced)
2495
        fprintf (file, ", is dereferenced");
2496
 
2497
      if (pi->value_escapes_p)
2498
        fprintf (file, ", its value escapes");
2499
 
2500
      if (pi->pt_anything)
2501
        fprintf (file, ", points-to anything");
2502
 
2503
      if (pi->pt_null)
2504
        fprintf (file, ", points-to NULL");
2505
 
2506
      if (pi->pt_vars)
2507
        {
2508
          unsigned ix;
2509
          bitmap_iterator bi;
2510
 
2511
          fprintf (file, ", points-to vars: { ");
2512
          EXECUTE_IF_SET_IN_BITMAP (pi->pt_vars, 0, ix, bi)
2513
            {
2514
              print_generic_expr (file, referenced_var (ix), dump_flags);
2515
              fprintf (file, " ");
2516
            }
2517
          fprintf (file, "}");
2518
        }
2519
    }
2520
 
2521
  fprintf (file, "\n");
2522
}
2523
 
2524
 
2525
/* Dump points-to information for VAR into stderr.  */
2526
 
2527
void
2528
debug_points_to_info_for (tree var)
2529
{
2530
  dump_points_to_info_for (stderr, var);
2531
}
2532
 
2533
 
2534
/* Dump points-to information into FILE.  NOTE: This function is slow, as
2535
   it needs to traverse the whole CFG looking for pointer SSA_NAMEs.  */
2536
 
2537
void
2538
dump_points_to_info (FILE *file)
2539
{
2540
  basic_block bb;
2541
  block_stmt_iterator si;
2542
  ssa_op_iter iter;
2543
  const char *fname =
2544
    lang_hooks.decl_printable_name (current_function_decl, 2);
2545
  referenced_var_iterator rvi;
2546
  tree var;
2547
 
2548
  fprintf (file, "\n\nPointed-to sets for pointers in %s\n\n", fname);
2549
 
2550
  /* First dump points-to information for the default definitions of
2551
     pointer variables.  This is necessary because default definitions are
2552
     not part of the code.  */
2553
  FOR_EACH_REFERENCED_VAR (var, rvi)
2554
    {
2555
      if (POINTER_TYPE_P (TREE_TYPE (var)))
2556
        {
2557
          tree def = default_def (var);
2558
          if (def)
2559
            dump_points_to_info_for (file, def);
2560
        }
2561
    }
2562
 
2563
  /* Dump points-to information for every pointer defined in the program.  */
2564
  FOR_EACH_BB (bb)
2565
    {
2566
      tree phi;
2567
 
2568
      for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2569
        {
2570
          tree ptr = PHI_RESULT (phi);
2571
          if (POINTER_TYPE_P (TREE_TYPE (ptr)))
2572
            dump_points_to_info_for (file, ptr);
2573
        }
2574
 
2575
        for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
2576
          {
2577
            tree stmt = bsi_stmt (si);
2578
            tree def;
2579
            FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
2580
              if (POINTER_TYPE_P (TREE_TYPE (def)))
2581
                dump_points_to_info_for (file, def);
2582
          }
2583
    }
2584
 
2585
  fprintf (file, "\n");
2586
}
2587
 
2588
 
2589
/* Dump points-to info pointed to by PTO into STDERR.  */
2590
 
2591
void
2592
debug_points_to_info (void)
2593
{
2594
  dump_points_to_info (stderr);
2595
}
2596
 
2597
/* Dump to FILE the list of variables that may be aliasing VAR.  */
2598
 
2599
void
2600
dump_may_aliases_for (FILE *file, tree var)
2601
{
2602
  VEC(tree, gc) *aliases;
2603
 
2604
  if (TREE_CODE (var) == SSA_NAME)
2605
    var = SSA_NAME_VAR (var);
2606
 
2607
  aliases = var_ann (var)->may_aliases;
2608
  if (aliases)
2609
    {
2610
      size_t i;
2611
      tree al;
2612
      fprintf (file, "{ ");
2613
      for (i = 0; VEC_iterate (tree, aliases, i, al); i++)
2614
        {
2615
          print_generic_expr (file, al, dump_flags);
2616
          fprintf (file, " ");
2617
        }
2618
      fprintf (file, "}");
2619
    }
2620
}
2621
 
2622
 
2623
/* Dump to stderr the list of variables that may be aliasing VAR.  */
2624
 
2625
void
2626
debug_may_aliases_for (tree var)
2627
{
2628
  dump_may_aliases_for (stderr, var);
2629
}
2630
 
2631
/* Return true if VAR may be aliased.  */
2632
 
2633
bool
2634
may_be_aliased (tree var)
2635
{
2636
  /* Obviously.  */
2637
  if (TREE_ADDRESSABLE (var))
2638
    return true;
2639
 
2640
  /* Globally visible variables can have their addresses taken by other
2641
     translation units.  */
2642
 
2643
  if (MTAG_P (var)
2644
      && (MTAG_GLOBAL (var) || TREE_PUBLIC (var)))
2645
    return true;
2646
  else if (!MTAG_P (var)
2647
      && (DECL_EXTERNAL (var) || TREE_PUBLIC (var)))
2648
    return true;
2649
 
2650
  /* Automatic variables can't have their addresses escape any other way.
2651
     This must be after the check for global variables, as extern declarations
2652
     do not have TREE_STATIC set.  */
2653
  if (!TREE_STATIC (var))
2654
    return false;
2655
 
2656
  /* If we're in unit-at-a-time mode, then we must have seen all occurrences
2657
     of address-of operators, and so we can trust TREE_ADDRESSABLE.  Otherwise
2658
     we can only be sure the variable isn't addressable if it's local to the
2659
     current function.  */
2660
  if (flag_unit_at_a_time)
2661
    return false;
2662
  if (decl_function_context (var) == current_function_decl)
2663
    return false;
2664
 
2665
  return true;
2666
}
2667
 
2668
 
2669
/* Given two symbols return TRUE if one is in the alias set of the other.  */
2670
bool
2671
is_aliased_with (tree tag, tree sym)
2672
{
2673
  size_t i;
2674
  VEC(tree,gc) *aliases;
2675
  tree al;
2676
 
2677
  if (var_ann (sym)->is_aliased)
2678
    {
2679
      aliases = var_ann (tag)->may_aliases;
2680
 
2681
      if (aliases == NULL)
2682
        return false;
2683
 
2684
      for (i = 0; VEC_iterate (tree, aliases, i, al); i++)
2685
        if (al == sym)
2686
          return true;
2687
    }
2688
  else
2689
    {
2690
      aliases = var_ann (sym)->may_aliases;
2691
 
2692
      if (aliases == NULL)
2693
        return false;
2694
 
2695
      for (i = 0; VEC_iterate (tree, aliases, i, al); i++)
2696
        if (al == tag)
2697
          return true;
2698
    }
2699
 
2700
  return false;
2701
}
2702
 
2703
 
2704
/* Given two tags return TRUE if their may-alias sets intersect.  */
2705
 
2706
bool
2707
may_aliases_intersect (tree tag1, tree tag2)
2708
{
2709
  struct pointer_set_t *set1 = pointer_set_create ();
2710
  unsigned i;
2711
  VEC(tree,gc) *may_aliases1 = may_aliases (tag1);
2712
  VEC(tree,gc) *may_aliases2 = may_aliases (tag2);
2713
  tree sym;
2714
 
2715
  /* Insert all the symbols from the first may-alias set into the
2716
     pointer-set.  */
2717
  for (i = 0; VEC_iterate (tree, may_aliases1, i, sym); i++)
2718
    pointer_set_insert (set1, sym);
2719
 
2720
  /* Go through the second may-alias set and check if it contains symbols that
2721
     are common with the first set.  */
2722
  for (i = 0; VEC_iterate (tree, may_aliases2, i, sym); i++)
2723
    if (pointer_set_contains (set1, sym))
2724
      {
2725
       pointer_set_destroy (set1);
2726
       return true;
2727
      }
2728
 
2729
  pointer_set_destroy (set1);
2730
  return false;
2731
}
2732
 
2733
 
2734
/* The following is based on code in add_stmt_operand to ensure that the
2735
   same defs/uses/vdefs/vuses will be found after replacing a reference
2736
   to var (or ARRAY_REF to var) with an INDIRECT_REF to ptr whose value
2737
   is the address of var.  Return a memtag for the ptr, after adding the
2738
   proper may_aliases to it (which are the aliases of var, if it has any,
2739
   or var itself).  */
2740
 
2741
static tree
2742
add_may_alias_for_new_tag (tree tag, tree var)
2743
{
2744
  var_ann_t v_ann = var_ann (var);
2745
  VEC(tree, gc) *aliases = v_ann->may_aliases;
2746
 
2747
  /* Case 1: |aliases| == 1  */
2748
  if ((aliases != NULL)
2749
      && (VEC_length (tree, aliases) == 1))
2750
    {
2751
      tree ali = VEC_index (tree, aliases, 0);
2752
 
2753
      if (TREE_CODE (ali) == SYMBOL_MEMORY_TAG)
2754
        return ali;
2755
    }
2756
 
2757
  /* Case 2: |aliases| == 0  */
2758
  if (aliases == NULL)
2759
    add_may_alias (tag, var);
2760
  else
2761
    {
2762
      /* Case 3: |aliases| > 1  */
2763
      unsigned i;
2764
      tree al;
2765
 
2766
      for (i = 0; VEC_iterate (tree, aliases, i, al); i++)
2767
        add_may_alias (tag, al);
2768
    }
2769
 
2770
  return tag;
2771
}
2772
 
2773
/* Create a new symbol tag for PTR.  Construct the may-alias list of this type
2774
   tag so that it has the aliasing of VAR, or of the relevant subvars of VAR
2775
   according to the location accessed by EXPR.
2776
 
2777
   Note, the set of aliases represented by the new symbol tag are not marked
2778
   for renaming.  */
2779
 
2780
void
2781
new_type_alias (tree ptr, tree var, tree expr)
2782
{
2783
  var_ann_t p_ann = var_ann (ptr);
2784
  tree tag_type = TREE_TYPE (TREE_TYPE (ptr));
2785
  tree tag;
2786
  subvar_t svars;
2787
  tree ali = NULL_TREE;
2788
  HOST_WIDE_INT offset, size, maxsize;
2789
  tree ref;
2790
 
2791
  gcc_assert (p_ann->symbol_mem_tag == NULL_TREE);
2792
  gcc_assert (!MTAG_P (var));
2793
 
2794
  ref = get_ref_base_and_extent (expr, &offset, &size, &maxsize);
2795
  gcc_assert (ref);
2796
 
2797
  tag = create_memory_tag (tag_type, true);
2798
  p_ann->symbol_mem_tag = tag;
2799
 
2800
  /* Add VAR to the may-alias set of PTR's new symbol tag.  If VAR has
2801
     subvars, add the subvars to the tag instead of the actual var.  */
2802
  if (var_can_have_subvars (var)
2803
      && (svars = get_subvars_for_var (var)))
2804
    {
2805
      subvar_t sv;
2806
      VEC (tree, heap) *overlaps = NULL;
2807
      unsigned int len;
2808
 
2809
      for (sv = svars; sv; sv = sv->next)
2810
        {
2811
          bool exact;
2812
 
2813
          if (overlap_subvar (offset, maxsize, sv->var, &exact))
2814
            VEC_safe_push (tree, heap, overlaps, sv->var);
2815
        }
2816
      len = VEC_length (tree, overlaps);
2817
      if (dump_file && (dump_flags & TDF_DETAILS))
2818
        fprintf (dump_file, "\nnumber of overlapping subvars = %u\n", len);
2819
      gcc_assert (len);
2820
 
2821
      if (len == 1)
2822
        ali = add_may_alias_for_new_tag (tag, VEC_index (tree, overlaps, 0));
2823
      else if (len > 1)
2824
        {
2825
          unsigned int k;
2826
          tree sv_var;
2827
 
2828
          for (k = 0; VEC_iterate (tree, overlaps, k, sv_var); k++)
2829
            {
2830
              ali = add_may_alias_for_new_tag (tag, sv_var);
2831
 
2832
              if (ali != tag)
2833
                {
2834
                  /* Can happen only if 'Case 1' of add_may_alias_for_new_tag
2835
                     took place.  Since more than one svar was found, we add
2836
                     'ali' as one of the may_aliases of the new tag.  */
2837
                  add_may_alias (tag, ali);
2838
                  ali = tag;
2839
                }
2840
            }
2841
        }
2842
    }
2843
  else
2844
    ali = add_may_alias_for_new_tag (tag, var);
2845
 
2846
  p_ann->symbol_mem_tag = ali;
2847
  TREE_READONLY (tag) = TREE_READONLY (var);
2848
  MTAG_GLOBAL (tag) = is_global_var (var);
2849
}
2850
 
2851
/* This represents the used range of a variable.  */
2852
 
2853
typedef struct used_part
2854
{
2855
  HOST_WIDE_INT minused;
2856
  HOST_WIDE_INT maxused;
2857
  /* True if we have an explicit use/def of some portion of this variable,
2858
     even if it is all of it. i.e. a.b = 5 or temp = a.b.  */
2859
  bool explicit_uses;
2860
  /* True if we have an implicit use/def of some portion of this
2861
     variable.  Implicit uses occur when we can't tell what part we
2862
     are referencing, and have to make conservative assumptions.  */
2863
  bool implicit_uses;
2864
  /* True if the structure is only written to or taken its address.  */
2865
  bool write_only;
2866
} *used_part_t;
2867
 
2868
/* An array of used_part structures, indexed by variable uid.  */
2869
 
2870
static htab_t used_portions;
2871
 
2872
struct used_part_map
2873
{
2874
  unsigned int uid;
2875
  used_part_t to;
2876
};
2877
 
2878
/* Return true if the uid in the two used part maps are equal.  */
2879
 
2880
static int
2881
used_part_map_eq (const void *va, const void *vb)
2882
{
2883
  const struct used_part_map *a = (const struct used_part_map *) va;
2884
  const struct used_part_map *b = (const struct used_part_map *) vb;
2885
  return (a->uid == b->uid);
2886
}
2887
 
2888
/* Hash a from uid in a used_part_map.  */
2889
 
2890
static unsigned int
2891
used_part_map_hash (const void *item)
2892
{
2893
  return ((const struct used_part_map *)item)->uid;
2894
}
2895
 
2896
/* Free a used part map element.  */
2897
 
2898
static void
2899
free_used_part_map (void *item)
2900
{
2901
  free (((struct used_part_map *)item)->to);
2902
  free (item);
2903
}
2904
 
2905
/* Lookup a used_part structure for a UID.  */
2906
 
2907
static used_part_t
2908
up_lookup (unsigned int uid)
2909
{
2910
  struct used_part_map *h, in;
2911
  in.uid = uid;
2912
  h = (struct used_part_map *) htab_find_with_hash (used_portions, &in, uid);
2913
  if (!h)
2914
    return NULL;
2915
  return h->to;
2916
}
2917
 
2918
/* Insert the pair UID, TO into the used part hashtable.  */
2919
 
2920
static void
2921
up_insert (unsigned int uid, used_part_t to)
2922
{
2923
  struct used_part_map *h;
2924
  void **loc;
2925
 
2926
  h = XNEW (struct used_part_map);
2927
  h->uid = uid;
2928
  h->to = to;
2929
  loc = htab_find_slot_with_hash (used_portions, h,
2930
                                  uid, INSERT);
2931
  if (*loc != NULL)
2932
    free (*loc);
2933
  *(struct used_part_map **)  loc = h;
2934
}
2935
 
2936
 
2937
/* Given a variable uid, UID, get or create the entry in the used portions
2938
   table for the variable.  */
2939
 
2940
static used_part_t
2941
get_or_create_used_part_for (size_t uid)
2942
{
2943
  used_part_t up;
2944
  if ((up = up_lookup (uid)) == NULL)
2945
    {
2946
      up = XCNEW (struct used_part);
2947
      up->minused = INT_MAX;
2948
      up->maxused = 0;
2949
      up->explicit_uses = false;
2950
      up->implicit_uses = false;
2951
      up->write_only = true;
2952
    }
2953
 
2954
  return up;
2955
}
2956
 
2957
 
2958
/* Create and return a structure sub-variable for field type FIELD at
2959
   offset OFFSET, with size SIZE, of variable VAR.  */
2960
 
2961
static tree
2962
create_sft (tree var, tree field, unsigned HOST_WIDE_INT offset,
2963
            unsigned HOST_WIDE_INT size)
2964
{
2965
  var_ann_t ann;
2966
  tree subvar = create_tag_raw (STRUCT_FIELD_TAG, field, "SFT");
2967
 
2968
  /* We need to copy the various flags from VAR to SUBVAR, so that
2969
     they are is_global_var iff the original variable was.  */
2970
  DECL_CONTEXT (subvar) = DECL_CONTEXT (var);
2971
  MTAG_GLOBAL (subvar) = DECL_EXTERNAL (var);
2972
  TREE_PUBLIC  (subvar) = TREE_PUBLIC (var);
2973
  TREE_STATIC (subvar) = TREE_STATIC (var);
2974
  TREE_READONLY (subvar) = TREE_READONLY (var);
2975
  TREE_ADDRESSABLE (subvar) = TREE_ADDRESSABLE (var);
2976
 
2977
  /* Add the new variable to REFERENCED_VARS.  */
2978
  ann = get_var_ann (subvar);
2979
  ann->symbol_mem_tag = NULL;
2980
  add_referenced_var (subvar);
2981
  SFT_PARENT_VAR (subvar) = var;
2982
  SFT_OFFSET (subvar) = offset;
2983
  SFT_SIZE (subvar) = size;
2984
  return subvar;
2985
}
2986
 
2987
 
2988
/* Given an aggregate VAR, create the subvariables that represent its
2989
   fields.  */
2990
 
2991
static void
2992
create_overlap_variables_for (tree var)
2993
{
2994
  VEC(fieldoff_s,heap) *fieldstack = NULL;
2995
  used_part_t up;
2996
  size_t uid = DECL_UID (var);
2997
 
2998
  up = up_lookup (uid);
2999
  if (!up
3000
      || up->write_only)
3001
    return;
3002
 
3003
  push_fields_onto_fieldstack (TREE_TYPE (var), &fieldstack, 0, NULL);
3004
  if (VEC_length (fieldoff_s, fieldstack) != 0)
3005
    {
3006
      subvar_t *subvars;
3007
      fieldoff_s *fo;
3008
      bool notokay = false;
3009
      int fieldcount = 0;
3010
      int i;
3011
      HOST_WIDE_INT lastfooffset = -1;
3012
      HOST_WIDE_INT lastfosize = -1;
3013
      tree lastfotype = NULL_TREE;
3014
 
3015
      /* Not all fields have DECL_SIZE set, and those that don't, we don't
3016
         know their size, and thus, can't handle.
3017
         The same is true of fields with DECL_SIZE that is not an integer
3018
         constant (such as variable sized fields).
3019
         Fields with offsets which are not constant will have an offset < 0
3020
         We *could* handle fields that are constant sized arrays, but
3021
         currently don't.  Doing so would require some extra changes to
3022
         tree-ssa-operands.c.  */
3023
 
3024
      for (i = 0; VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
3025
        {
3026
          if (!fo->size
3027
              || TREE_CODE (fo->size) != INTEGER_CST
3028
              || fo->offset < 0)
3029
            {
3030
              notokay = true;
3031
              break;
3032
            }
3033
          fieldcount++;
3034
        }
3035
 
3036
      /* The current heuristic we use is as follows:
3037
         If the variable has no used portions in this function, no
3038
         structure vars are created for it.
3039
         Otherwise,
3040
         If the variable has less than SALIAS_MAX_IMPLICIT_FIELDS,
3041
         we always create structure vars for them.
3042
         If the variable has more than SALIAS_MAX_IMPLICIT_FIELDS, and
3043
         some explicit uses, we create structure vars for them.
3044
         If the variable has more than SALIAS_MAX_IMPLICIT_FIELDS, and
3045
         no explicit uses, we do not create structure vars for them.
3046
      */
3047
 
3048
      if (fieldcount >= SALIAS_MAX_IMPLICIT_FIELDS
3049
          && !up->explicit_uses)
3050
        {
3051
          if (dump_file && (dump_flags & TDF_DETAILS))
3052
            {
3053
              fprintf (dump_file, "Variable ");
3054
              print_generic_expr (dump_file, var, 0);
3055
              fprintf (dump_file, " has no explicit uses in this function, and is > SALIAS_MAX_IMPLICIT_FIELDS, so skipping\n");
3056
            }
3057
          notokay = true;
3058
        }
3059
 
3060
      /* Bail out, if we can't create overlap variables.  */
3061
      if (notokay)
3062
        {
3063
          VEC_free (fieldoff_s, heap, fieldstack);
3064
          return;
3065
        }
3066
 
3067
      /* Otherwise, create the variables.  */
3068
      subvars = lookup_subvars_for_var (var);
3069
 
3070
      sort_fieldstack (fieldstack);
3071
 
3072
      for (i = VEC_length (fieldoff_s, fieldstack);
3073
           VEC_iterate (fieldoff_s, fieldstack, --i, fo);)
3074
        {
3075
          subvar_t sv;
3076
          HOST_WIDE_INT fosize;
3077
          tree currfotype;
3078
 
3079
          fosize = TREE_INT_CST_LOW (fo->size);
3080
          currfotype = fo->type;
3081
 
3082
          /* If this field isn't in the used portion,
3083
             or it has the exact same offset and size as the last
3084
             field, skip it.  */
3085
 
3086
          if (((fo->offset <= up->minused
3087
                && fo->offset + fosize <= up->minused)
3088
               || fo->offset >= up->maxused)
3089
              || (fo->offset == lastfooffset
3090
                  && fosize == lastfosize
3091
                  && currfotype == lastfotype))
3092
            continue;
3093
          sv = GGC_NEW (struct subvar);
3094
          sv->next = *subvars;
3095
          sv->var = create_sft (var, fo->type, fo->offset, fosize);
3096
 
3097
          if (dump_file)
3098
            {
3099
              fprintf (dump_file, "structure field tag %s created for var %s",
3100
                       get_name (sv->var), get_name (var));
3101
              fprintf (dump_file, " offset " HOST_WIDE_INT_PRINT_DEC,
3102
                       SFT_OFFSET (sv->var));
3103
              fprintf (dump_file, " size " HOST_WIDE_INT_PRINT_DEC,
3104
                       SFT_SIZE (sv->var));
3105
              fprintf (dump_file, "\n");
3106
            }
3107
 
3108
          lastfotype = currfotype;
3109
          lastfooffset = fo->offset;
3110
          lastfosize = fosize;
3111
          *subvars = sv;
3112
        }
3113
 
3114
      /* Once we have created subvars, the original is no longer call
3115
         clobbered on its own.  Its call clobbered status depends
3116
         completely on the call clobbered status of the subvars.
3117
 
3118
         add_referenced_var in the above loop will take care of
3119
         marking subvars of global variables as call clobbered for us
3120
         to start, since they are global as well.  */
3121
      clear_call_clobbered (var);
3122
    }
3123
 
3124
  VEC_free (fieldoff_s, heap, fieldstack);
3125
}
3126
 
3127
 
3128
/* Find the conservative answer to the question of what portions of what
3129
   structures are used by this statement.  We assume that if we have a
3130
   component ref with a known size + offset, that we only need that part
3131
   of the structure.  For unknown cases, or cases where we do something
3132
   to the whole structure, we assume we need to create fields for the
3133
   entire structure.  */
3134
 
3135
static tree
3136
find_used_portions (tree *tp, int *walk_subtrees, void *lhs_p)
3137
{
3138
  switch (TREE_CODE (*tp))
3139
    {
3140
    case MODIFY_EXPR:
3141
      /* Recurse manually here to track whether the use is in the
3142
         LHS of an assignment.  */
3143
      find_used_portions (&TREE_OPERAND (*tp, 0), walk_subtrees, tp);
3144
      return find_used_portions (&TREE_OPERAND (*tp, 1), walk_subtrees, NULL);
3145
    case REALPART_EXPR:
3146
    case IMAGPART_EXPR:
3147
    case COMPONENT_REF:
3148
    case ARRAY_REF:
3149
      {
3150
        HOST_WIDE_INT bitsize;
3151
        HOST_WIDE_INT bitmaxsize;
3152
        HOST_WIDE_INT bitpos;
3153
        tree ref;
3154
        ref = get_ref_base_and_extent (*tp, &bitpos, &bitsize, &bitmaxsize);
3155
        if (DECL_P (ref)
3156
            && var_can_have_subvars (ref)
3157
            && bitmaxsize != -1)
3158
          {
3159
            size_t uid = DECL_UID (ref);
3160
            used_part_t up;
3161
 
3162
            up = get_or_create_used_part_for (uid);
3163
 
3164
            if (bitpos <= up->minused)
3165
              up->minused = bitpos;
3166
            if ((bitpos + bitmaxsize >= up->maxused))
3167
              up->maxused = bitpos + bitmaxsize;
3168
 
3169
            if (bitsize == bitmaxsize)
3170
              up->explicit_uses = true;
3171
            else
3172
              up->implicit_uses = true;
3173
            if (!lhs_p)
3174
              up->write_only = false;
3175
            up_insert (uid, up);
3176
 
3177
            *walk_subtrees = 0;
3178
            return NULL_TREE;
3179
          }
3180
      }
3181
      break;
3182
      /* This is here to make sure we mark the entire base variable as used
3183
         when you take its address.  Because our used portion analysis is
3184
         simple, we aren't looking at casts or pointer arithmetic to see what
3185
         happens when you take the address.  */
3186
    case ADDR_EXPR:
3187
      {
3188
        tree var = get_base_address (TREE_OPERAND (*tp, 0));
3189
 
3190
        if (var
3191
            && DECL_P (var)
3192
            && DECL_SIZE (var)
3193
            && var_can_have_subvars (var)
3194
            && TREE_CODE (DECL_SIZE (var)) == INTEGER_CST)
3195
          {
3196
            used_part_t up;
3197
            size_t uid = DECL_UID (var);
3198
 
3199
            up = get_or_create_used_part_for (uid);
3200
 
3201
            up->minused = 0;
3202
            up->maxused = TREE_INT_CST_LOW (DECL_SIZE (var));
3203
            up->implicit_uses = true;
3204
            if (!lhs_p)
3205
              up->write_only = false;
3206
 
3207
            up_insert (uid, up);
3208
            *walk_subtrees = 0;
3209
            return NULL_TREE;
3210
          }
3211
      }
3212
      break;
3213
    case CALL_EXPR:
3214
      {
3215
        tree *arg;
3216
        for (arg = &TREE_OPERAND (*tp, 1); *arg; arg = &TREE_CHAIN (*arg))
3217
          {
3218
            if (TREE_CODE (TREE_VALUE (*arg)) != ADDR_EXPR)
3219
              find_used_portions (&TREE_VALUE (*arg), walk_subtrees, NULL);
3220
          }
3221
        *walk_subtrees = 0;
3222
        return NULL_TREE;
3223
      }
3224
    case VAR_DECL:
3225
    case PARM_DECL:
3226
    case RESULT_DECL:
3227
      {
3228
        tree var = *tp;
3229
        if (DECL_SIZE (var)
3230
            && var_can_have_subvars (var)
3231
            && TREE_CODE (DECL_SIZE (var)) == INTEGER_CST)
3232
          {
3233
            used_part_t up;
3234
            size_t uid = DECL_UID (var);
3235
 
3236
            up = get_or_create_used_part_for (uid);
3237
 
3238
            up->minused = 0;
3239
            up->maxused = TREE_INT_CST_LOW (DECL_SIZE (var));
3240
            up->implicit_uses = true;
3241
 
3242
            up_insert (uid, up);
3243
            *walk_subtrees = 0;
3244
            return NULL_TREE;
3245
          }
3246
      }
3247
      break;
3248
 
3249
    default:
3250
      break;
3251
 
3252
    }
3253
  return NULL_TREE;
3254
}
3255
 
3256
/* Create structure field variables for structures used in this function.  */
3257
 
3258
static unsigned int
3259
create_structure_vars (void)
3260
{
3261
  basic_block bb;
3262
  safe_referenced_var_iterator rvi;
3263
  VEC (tree, heap) *varvec = NULL;
3264
  tree var;
3265
 
3266
  used_portions = htab_create (10, used_part_map_hash, used_part_map_eq,
3267
                               free_used_part_map);
3268
 
3269
  FOR_EACH_BB (bb)
3270
    {
3271
      block_stmt_iterator bsi;
3272
      for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
3273
        {
3274
          walk_tree_without_duplicates (bsi_stmt_ptr (bsi),
3275
                                        find_used_portions,
3276
                                        NULL);
3277
        }
3278
    }
3279
  FOR_EACH_REFERENCED_VAR_SAFE (var, varvec, rvi)
3280
    {
3281
      /* The C++ FE creates vars without DECL_SIZE set, for some reason.  */
3282
      if (var
3283
          && DECL_SIZE (var)
3284
          && var_can_have_subvars (var)
3285
          && !MTAG_P (var)
3286
          && TREE_CODE (DECL_SIZE (var)) == INTEGER_CST)
3287
        create_overlap_variables_for (var);
3288
    }
3289
  htab_delete (used_portions);
3290
  VEC_free (tree, heap, varvec);
3291
  return 0;
3292
}
3293
 
3294
static bool
3295
gate_structure_vars (void)
3296
{
3297
  return flag_tree_salias != 0;
3298
}
3299
 
3300
struct tree_opt_pass pass_create_structure_vars =
3301
{
3302
  "salias",              /* name */
3303
  gate_structure_vars,   /* gate */
3304
  create_structure_vars, /* execute */
3305
  NULL,                  /* sub */
3306
  NULL,                  /* next */
3307
  0,                      /* static_pass_number */
3308
  0,                      /* tv_id */
3309
  PROP_cfg,              /* properties_required */
3310
  0,                      /* properties_provided */
3311
  0,                      /* properties_destroyed */
3312
  0,                      /* todo_flags_start */
3313
  TODO_dump_func,        /* todo_flags_finish */
3314
 
3315
};
3316
 
3317
/* Reset the DECL_CALL_CLOBBERED flags on our referenced vars.  In
3318
   theory, this only needs to be done for globals.  */
3319
 
3320
static unsigned int
3321
reset_cc_flags (void)
3322
{
3323
  tree var;
3324
  referenced_var_iterator rvi;
3325
 
3326
  FOR_EACH_REFERENCED_VAR (var, rvi)
3327
    DECL_CALL_CLOBBERED (var) = false;
3328
  return 0;
3329
}
3330
 
3331
struct tree_opt_pass pass_reset_cc_flags =
3332
{
3333
  NULL,          /* name */
3334
  NULL,          /* gate */
3335
  reset_cc_flags, /* execute */
3336
  NULL,                  /* sub */
3337
  NULL,                  /* next */
3338
  0,                      /* static_pass_number */
3339
  0,                      /* tv_id */
3340
  PROP_referenced_vars |PROP_cfg, /* properties_required */
3341
  0,                      /* properties_provided */
3342
  0,                      /* properties_destroyed */
3343
  0,                      /* todo_flags_start */
3344
  0,                      /* todo_flags_finish */
3345
 
3346
};

powered by: WebSVN 2.1.0

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