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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [gcc/] [tree-ssa-alias.c] - Blame information for rev 693

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

Line No. Rev Author Line
1 684 jeremybenn
/* Alias analysis for trees.
2
   Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011
3
   Free Software Foundation, Inc.
4
   Contributed by Diego Novillo <dnovillo@redhat.com>
5
 
6
This file is part of GCC.
7
 
8
GCC is free software; you can redistribute it and/or modify
9
it under the terms of the GNU General Public License as published by
10
the Free Software Foundation; either version 3, or (at your option)
11
any later version.
12
 
13
GCC is distributed in the hope that it will be useful,
14
but WITHOUT ANY WARRANTY; without even the implied warranty of
15
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16
GNU General Public License for more details.
17
 
18
You should have received a copy of the GNU General Public License
19
along with GCC; see the file COPYING3.  If not see
20
<http://www.gnu.org/licenses/>.  */
21
 
22
#include "config.h"
23
#include "system.h"
24
#include "coretypes.h"
25
#include "tm.h"
26
#include "tree.h"
27
#include "tm_p.h"
28
#include "target.h"
29
#include "basic-block.h"
30
#include "timevar.h"
31
#include "ggc.h"
32
#include "langhooks.h"
33
#include "flags.h"
34
#include "function.h"
35
#include "tree-pretty-print.h"
36
#include "tree-dump.h"
37
#include "gimple.h"
38
#include "tree-flow.h"
39
#include "tree-inline.h"
40
#include "tree-pass.h"
41
#include "convert.h"
42
#include "params.h"
43
#include "vec.h"
44
#include "bitmap.h"
45
#include "vecprim.h"
46
#include "pointer-set.h"
47
#include "alloc-pool.h"
48
#include "tree-ssa-alias.h"
49
 
50
/* Broad overview of how alias analysis on gimple works:
51
 
52
   Statements clobbering or using memory are linked through the
53
   virtual operand factored use-def chain.  The virtual operand
54
   is unique per function, its symbol is accessible via gimple_vop (cfun).
55
   Virtual operands are used for efficiently walking memory statements
56
   in the gimple IL and are useful for things like value-numbering as
57
   a generation count for memory references.
58
 
59
   SSA_NAME pointers may have associated points-to information
60
   accessible via the SSA_NAME_PTR_INFO macro.  Flow-insensitive
61
   points-to information is (re-)computed by the TODO_rebuild_alias
62
   pass manager todo.  Points-to information is also used for more
63
   precise tracking of call-clobbered and call-used variables and
64
   related disambiguations.
65
 
66
   This file contains functions for disambiguating memory references,
67
   the so called alias-oracle and tools for walking of the gimple IL.
68
 
69
   The main alias-oracle entry-points are
70
 
71
   bool stmt_may_clobber_ref_p (gimple, tree)
72
 
73
     This function queries if a statement may invalidate (parts of)
74
     the memory designated by the reference tree argument.
75
 
76
   bool ref_maybe_used_by_stmt_p (gimple, tree)
77
 
78
     This function queries if a statement may need (parts of) the
79
     memory designated by the reference tree argument.
80
 
81
   There are variants of these functions that only handle the call
82
   part of a statement, call_may_clobber_ref_p and ref_maybe_used_by_call_p.
83
   Note that these do not disambiguate against a possible call lhs.
84
 
85
   bool refs_may_alias_p (tree, tree)
86
 
87
     This function tries to disambiguate two reference trees.
88
 
89
   bool ptr_deref_may_alias_global_p (tree)
90
 
91
     This function queries if dereferencing a pointer variable may
92
     alias global memory.
93
 
94
   More low-level disambiguators are available and documented in
95
   this file.  Low-level disambiguators dealing with points-to
96
   information are in tree-ssa-structalias.c.  */
97
 
98
 
99
/* Query statistics for the different low-level disambiguators.
100
   A high-level query may trigger multiple of them.  */
101
 
102
static struct {
103
  unsigned HOST_WIDE_INT refs_may_alias_p_may_alias;
104
  unsigned HOST_WIDE_INT refs_may_alias_p_no_alias;
105
  unsigned HOST_WIDE_INT ref_maybe_used_by_call_p_may_alias;
106
  unsigned HOST_WIDE_INT ref_maybe_used_by_call_p_no_alias;
107
  unsigned HOST_WIDE_INT call_may_clobber_ref_p_may_alias;
108
  unsigned HOST_WIDE_INT call_may_clobber_ref_p_no_alias;
109
} alias_stats;
110
 
111
void
112
dump_alias_stats (FILE *s)
113
{
114
  fprintf (s, "\nAlias oracle query stats:\n");
115
  fprintf (s, "  refs_may_alias_p: "
116
           HOST_WIDE_INT_PRINT_DEC" disambiguations, "
117
           HOST_WIDE_INT_PRINT_DEC" queries\n",
118
           alias_stats.refs_may_alias_p_no_alias,
119
           alias_stats.refs_may_alias_p_no_alias
120
           + alias_stats.refs_may_alias_p_may_alias);
121
  fprintf (s, "  ref_maybe_used_by_call_p: "
122
           HOST_WIDE_INT_PRINT_DEC" disambiguations, "
123
           HOST_WIDE_INT_PRINT_DEC" queries\n",
124
           alias_stats.ref_maybe_used_by_call_p_no_alias,
125
           alias_stats.refs_may_alias_p_no_alias
126
           + alias_stats.ref_maybe_used_by_call_p_may_alias);
127
  fprintf (s, "  call_may_clobber_ref_p: "
128
           HOST_WIDE_INT_PRINT_DEC" disambiguations, "
129
           HOST_WIDE_INT_PRINT_DEC" queries\n",
130
           alias_stats.call_may_clobber_ref_p_no_alias,
131
           alias_stats.call_may_clobber_ref_p_no_alias
132
           + alias_stats.call_may_clobber_ref_p_may_alias);
133
}
134
 
135
 
136
/* Return true, if dereferencing PTR may alias with a global variable.  */
137
 
138
bool
139
ptr_deref_may_alias_global_p (tree ptr)
140
{
141
  struct ptr_info_def *pi;
142
 
143
  /* If we end up with a pointer constant here that may point
144
     to global memory.  */
145
  if (TREE_CODE (ptr) != SSA_NAME)
146
    return true;
147
 
148
  pi = SSA_NAME_PTR_INFO (ptr);
149
 
150
  /* If we do not have points-to information for this variable,
151
     we have to punt.  */
152
  if (!pi)
153
    return true;
154
 
155
  /* ???  This does not use TBAA to prune globals ptr may not access.  */
156
  return pt_solution_includes_global (&pi->pt);
157
}
158
 
159
/* Return true if dereferencing PTR may alias DECL.
160
   The caller is responsible for applying TBAA to see if PTR
161
   may access DECL at all.  */
162
 
163
static bool
164
ptr_deref_may_alias_decl_p (tree ptr, tree decl)
165
{
166
  struct ptr_info_def *pi;
167
 
168
  /* Conversions are irrelevant for points-to information and
169
     data-dependence analysis can feed us those.  */
170
  STRIP_NOPS (ptr);
171
 
172
  /* Anything we do not explicilty handle aliases.  */
173
  if ((TREE_CODE (ptr) != SSA_NAME
174
       && TREE_CODE (ptr) != ADDR_EXPR
175
       && TREE_CODE (ptr) != POINTER_PLUS_EXPR)
176
      || !POINTER_TYPE_P (TREE_TYPE (ptr))
177
      || (TREE_CODE (decl) != VAR_DECL
178
          && TREE_CODE (decl) != PARM_DECL
179
          && TREE_CODE (decl) != RESULT_DECL))
180
    return true;
181
 
182
  /* Disregard pointer offsetting.  */
183
  if (TREE_CODE (ptr) == POINTER_PLUS_EXPR)
184
    {
185
      do
186
        {
187
          ptr = TREE_OPERAND (ptr, 0);
188
        }
189
      while (TREE_CODE (ptr) == POINTER_PLUS_EXPR);
190
      return ptr_deref_may_alias_decl_p (ptr, decl);
191
    }
192
 
193
  /* ADDR_EXPR pointers either just offset another pointer or directly
194
     specify the pointed-to set.  */
195
  if (TREE_CODE (ptr) == ADDR_EXPR)
196
    {
197
      tree base = get_base_address (TREE_OPERAND (ptr, 0));
198
      if (base
199
          && (TREE_CODE (base) == MEM_REF
200
              || TREE_CODE (base) == TARGET_MEM_REF))
201
        ptr = TREE_OPERAND (base, 0);
202
      else if (base
203
               && DECL_P (base))
204
        return base == decl;
205
      else if (base
206
               && CONSTANT_CLASS_P (base))
207
        return false;
208
      else
209
        return true;
210
    }
211
 
212
  /* Non-aliased variables can not be pointed to.  */
213
  if (!may_be_aliased (decl))
214
    return false;
215
 
216
  /* If we do not have useful points-to information for this pointer
217
     we cannot disambiguate anything else.  */
218
  pi = SSA_NAME_PTR_INFO (ptr);
219
  if (!pi)
220
    return true;
221
 
222
  return pt_solution_includes (&pi->pt, decl);
223
}
224
 
225
/* Return true if dereferenced PTR1 and PTR2 may alias.
226
   The caller is responsible for applying TBAA to see if accesses
227
   through PTR1 and PTR2 may conflict at all.  */
228
 
229
bool
230
ptr_derefs_may_alias_p (tree ptr1, tree ptr2)
231
{
232
  struct ptr_info_def *pi1, *pi2;
233
 
234
  /* Conversions are irrelevant for points-to information and
235
     data-dependence analysis can feed us those.  */
236
  STRIP_NOPS (ptr1);
237
  STRIP_NOPS (ptr2);
238
 
239
  /* Anything we do not explicilty handle aliases.  */
240
  if ((TREE_CODE (ptr1) != SSA_NAME
241
       && TREE_CODE (ptr1) != ADDR_EXPR
242
       && TREE_CODE (ptr1) != POINTER_PLUS_EXPR)
243
      || (TREE_CODE (ptr2) != SSA_NAME
244
          && TREE_CODE (ptr2) != ADDR_EXPR
245
          && TREE_CODE (ptr2) != POINTER_PLUS_EXPR)
246
      || !POINTER_TYPE_P (TREE_TYPE (ptr1))
247
      || !POINTER_TYPE_P (TREE_TYPE (ptr2)))
248
    return true;
249
 
250
  /* Disregard pointer offsetting.  */
251
  if (TREE_CODE (ptr1) == POINTER_PLUS_EXPR)
252
    {
253
      do
254
        {
255
          ptr1 = TREE_OPERAND (ptr1, 0);
256
        }
257
      while (TREE_CODE (ptr1) == POINTER_PLUS_EXPR);
258
      return ptr_derefs_may_alias_p (ptr1, ptr2);
259
    }
260
  if (TREE_CODE (ptr2) == POINTER_PLUS_EXPR)
261
    {
262
      do
263
        {
264
          ptr2 = TREE_OPERAND (ptr2, 0);
265
        }
266
      while (TREE_CODE (ptr2) == POINTER_PLUS_EXPR);
267
      return ptr_derefs_may_alias_p (ptr1, ptr2);
268
    }
269
 
270
  /* ADDR_EXPR pointers either just offset another pointer or directly
271
     specify the pointed-to set.  */
272
  if (TREE_CODE (ptr1) == ADDR_EXPR)
273
    {
274
      tree base = get_base_address (TREE_OPERAND (ptr1, 0));
275
      if (base
276
          && (TREE_CODE (base) == MEM_REF
277
              || TREE_CODE (base) == TARGET_MEM_REF))
278
        ptr1 = TREE_OPERAND (base, 0);
279
      else if (base
280
               && DECL_P (base))
281
        return ptr_deref_may_alias_decl_p (ptr2, base);
282
      else
283
        return true;
284
    }
285
  if (TREE_CODE (ptr2) == ADDR_EXPR)
286
    {
287
      tree base = get_base_address (TREE_OPERAND (ptr2, 0));
288
      if (base
289
          && (TREE_CODE (base) == MEM_REF
290
              || TREE_CODE (base) == TARGET_MEM_REF))
291
        ptr2 = TREE_OPERAND (base, 0);
292
      else if (base
293
               && DECL_P (base))
294
        return ptr_deref_may_alias_decl_p (ptr1, base);
295
      else
296
        return true;
297
    }
298
 
299
  /* We may end up with two empty points-to solutions for two same pointers.
300
     In this case we still want to say both pointers alias, so shortcut
301
     that here.  */
302
  if (ptr1 == ptr2)
303
    return true;
304
 
305
  /* If we do not have useful points-to information for either pointer
306
     we cannot disambiguate anything else.  */
307
  pi1 = SSA_NAME_PTR_INFO (ptr1);
308
  pi2 = SSA_NAME_PTR_INFO (ptr2);
309
  if (!pi1 || !pi2)
310
    return true;
311
 
312
  /* ???  This does not use TBAA to prune decls from the intersection
313
     that not both pointers may access.  */
314
  return pt_solutions_intersect (&pi1->pt, &pi2->pt);
315
}
316
 
317
/* Return true if dereferencing PTR may alias *REF.
318
   The caller is responsible for applying TBAA to see if PTR
319
   may access *REF at all.  */
320
 
321
static bool
322
ptr_deref_may_alias_ref_p_1 (tree ptr, ao_ref *ref)
323
{
324
  tree base = ao_ref_base (ref);
325
 
326
  if (TREE_CODE (base) == MEM_REF
327
      || TREE_CODE (base) == TARGET_MEM_REF)
328
    return ptr_derefs_may_alias_p (ptr, TREE_OPERAND (base, 0));
329
  else if (DECL_P (base))
330
    return ptr_deref_may_alias_decl_p (ptr, base);
331
 
332
  return true;
333
}
334
 
335
 
336
/* Dump alias information on FILE.  */
337
 
338
void
339
dump_alias_info (FILE *file)
340
{
341
  size_t i;
342
  const char *funcname
343
    = lang_hooks.decl_printable_name (current_function_decl, 2);
344
  referenced_var_iterator rvi;
345
  tree var;
346
 
347
  fprintf (file, "\n\nAlias information for %s\n\n", funcname);
348
 
349
  fprintf (file, "Aliased symbols\n\n");
350
 
351
  FOR_EACH_REFERENCED_VAR (cfun, var, rvi)
352
    {
353
      if (may_be_aliased (var))
354
        dump_variable (file, var);
355
    }
356
 
357
  fprintf (file, "\nCall clobber information\n");
358
 
359
  fprintf (file, "\nESCAPED");
360
  dump_points_to_solution (file, &cfun->gimple_df->escaped);
361
 
362
  fprintf (file, "\n\nFlow-insensitive points-to information\n\n");
363
 
364
  for (i = 1; i < num_ssa_names; i++)
365
    {
366
      tree ptr = ssa_name (i);
367
      struct ptr_info_def *pi;
368
 
369
      if (ptr == NULL_TREE
370
          || SSA_NAME_IN_FREE_LIST (ptr))
371
        continue;
372
 
373
      pi = SSA_NAME_PTR_INFO (ptr);
374
      if (pi)
375
        dump_points_to_info_for (file, ptr);
376
    }
377
 
378
  fprintf (file, "\n");
379
}
380
 
381
 
382
/* Dump alias information on stderr.  */
383
 
384
DEBUG_FUNCTION void
385
debug_alias_info (void)
386
{
387
  dump_alias_info (stderr);
388
}
389
 
390
 
391
/* Dump the points-to set *PT into FILE.  */
392
 
393
void
394
dump_points_to_solution (FILE *file, struct pt_solution *pt)
395
{
396
  if (pt->anything)
397
    fprintf (file, ", points-to anything");
398
 
399
  if (pt->nonlocal)
400
    fprintf (file, ", points-to non-local");
401
 
402
  if (pt->escaped)
403
    fprintf (file, ", points-to escaped");
404
 
405
  if (pt->ipa_escaped)
406
    fprintf (file, ", points-to unit escaped");
407
 
408
  if (pt->null)
409
    fprintf (file, ", points-to NULL");
410
 
411
  if (pt->vars)
412
    {
413
      fprintf (file, ", points-to vars: ");
414
      dump_decl_set (file, pt->vars);
415
      if (pt->vars_contains_global)
416
        fprintf (file, " (includes global vars)");
417
    }
418
}
419
 
420
/* Dump points-to information for SSA_NAME PTR into FILE.  */
421
 
422
void
423
dump_points_to_info_for (FILE *file, tree ptr)
424
{
425
  struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
426
 
427
  print_generic_expr (file, ptr, dump_flags);
428
 
429
  if (pi)
430
    dump_points_to_solution (file, &pi->pt);
431
  else
432
    fprintf (file, ", points-to anything");
433
 
434
  fprintf (file, "\n");
435
}
436
 
437
 
438
/* Dump points-to information for VAR into stderr.  */
439
 
440
DEBUG_FUNCTION void
441
debug_points_to_info_for (tree var)
442
{
443
  dump_points_to_info_for (stderr, var);
444
}
445
 
446
 
447
/* Initializes the alias-oracle reference representation *R from REF.  */
448
 
449
void
450
ao_ref_init (ao_ref *r, tree ref)
451
{
452
  r->ref = ref;
453
  r->base = NULL_TREE;
454
  r->offset = 0;
455
  r->size = -1;
456
  r->max_size = -1;
457
  r->ref_alias_set = -1;
458
  r->base_alias_set = -1;
459
  r->volatile_p = ref ? TREE_THIS_VOLATILE (ref) : false;
460
}
461
 
462
/* Returns the base object of the memory reference *REF.  */
463
 
464
tree
465
ao_ref_base (ao_ref *ref)
466
{
467
  if (ref->base)
468
    return ref->base;
469
  ref->base = get_ref_base_and_extent (ref->ref, &ref->offset, &ref->size,
470
                                       &ref->max_size);
471
  return ref->base;
472
}
473
 
474
/* Returns the base object alias set of the memory reference *REF.  */
475
 
476
static alias_set_type
477
ao_ref_base_alias_set (ao_ref *ref)
478
{
479
  tree base_ref;
480
  if (ref->base_alias_set != -1)
481
    return ref->base_alias_set;
482
  if (!ref->ref)
483
    return 0;
484
  base_ref = ref->ref;
485
  while (handled_component_p (base_ref))
486
    base_ref = TREE_OPERAND (base_ref, 0);
487
  ref->base_alias_set = get_alias_set (base_ref);
488
  return ref->base_alias_set;
489
}
490
 
491
/* Returns the reference alias set of the memory reference *REF.  */
492
 
493
alias_set_type
494
ao_ref_alias_set (ao_ref *ref)
495
{
496
  if (ref->ref_alias_set != -1)
497
    return ref->ref_alias_set;
498
  ref->ref_alias_set = get_alias_set (ref->ref);
499
  return ref->ref_alias_set;
500
}
501
 
502
/* Init an alias-oracle reference representation from a gimple pointer
503
   PTR and a gimple size SIZE in bytes.  If SIZE is NULL_TREE the the
504
   size is assumed to be unknown.  The access is assumed to be only
505
   to or after of the pointer target, not before it.  */
506
 
507
void
508
ao_ref_init_from_ptr_and_size (ao_ref *ref, tree ptr, tree size)
509
{
510
  HOST_WIDE_INT t1, t2;
511
  ref->ref = NULL_TREE;
512
  if (TREE_CODE (ptr) == ADDR_EXPR)
513
    ref->base = get_ref_base_and_extent (TREE_OPERAND (ptr, 0),
514
                                         &ref->offset, &t1, &t2);
515
  else
516
    {
517
      ref->base = build2 (MEM_REF, char_type_node,
518
                          ptr, null_pointer_node);
519
      ref->offset = 0;
520
    }
521
  if (size
522
      && host_integerp (size, 0)
523
      && TREE_INT_CST_LOW (size) * 8 / 8 == TREE_INT_CST_LOW (size))
524
    ref->max_size = ref->size = TREE_INT_CST_LOW (size) * 8;
525
  else
526
    ref->max_size = ref->size = -1;
527
  ref->ref_alias_set = 0;
528
  ref->base_alias_set = 0;
529
  ref->volatile_p = false;
530
}
531
 
532
/* Return 1 if TYPE1 and TYPE2 are to be considered equivalent for the
533
   purpose of TBAA.  Return 0 if they are distinct and -1 if we cannot
534
   decide.  */
535
 
536
static inline int
537
same_type_for_tbaa (tree type1, tree type2)
538
{
539
  type1 = TYPE_MAIN_VARIANT (type1);
540
  type2 = TYPE_MAIN_VARIANT (type2);
541
 
542
  /* If we would have to do structural comparison bail out.  */
543
  if (TYPE_STRUCTURAL_EQUALITY_P (type1)
544
      || TYPE_STRUCTURAL_EQUALITY_P (type2))
545
    return -1;
546
 
547
  /* Compare the canonical types.  */
548
  if (TYPE_CANONICAL (type1) == TYPE_CANONICAL (type2))
549
    return 1;
550
 
551
  /* ??? Array types are not properly unified in all cases as we have
552
     spurious changes in the index types for example.  Removing this
553
     causes all sorts of problems with the Fortran frontend.  */
554
  if (TREE_CODE (type1) == ARRAY_TYPE
555
      && TREE_CODE (type2) == ARRAY_TYPE)
556
    return -1;
557
 
558
  /* ??? In Ada, an lvalue of an unconstrained type can be used to access an
559
     object of one of its constrained subtypes, e.g. when a function with an
560
     unconstrained parameter passed by reference is called on an object and
561
     inlined.  But, even in the case of a fixed size, type and subtypes are
562
     not equivalent enough as to share the same TYPE_CANONICAL, since this
563
     would mean that conversions between them are useless, whereas they are
564
     not (e.g. type and subtypes can have different modes).  So, in the end,
565
     they are only guaranteed to have the same alias set.  */
566
  if (get_alias_set (type1) == get_alias_set (type2))
567
    return -1;
568
 
569
  /* The types are known to be not equal.  */
570
  return 0;
571
}
572
 
573
/* Determine if the two component references REF1 and REF2 which are
574
   based on access types TYPE1 and TYPE2 and of which at least one is based
575
   on an indirect reference may alias.  REF2 is the only one that can
576
   be a decl in which case REF2_IS_DECL is true.
577
   REF1_ALIAS_SET, BASE1_ALIAS_SET, REF2_ALIAS_SET and BASE2_ALIAS_SET
578
   are the respective alias sets.  */
579
 
580
static bool
581
aliasing_component_refs_p (tree ref1,
582
                           alias_set_type ref1_alias_set,
583
                           alias_set_type base1_alias_set,
584
                           HOST_WIDE_INT offset1, HOST_WIDE_INT max_size1,
585
                           tree ref2,
586
                           alias_set_type ref2_alias_set,
587
                           alias_set_type base2_alias_set,
588
                           HOST_WIDE_INT offset2, HOST_WIDE_INT max_size2,
589
                           bool ref2_is_decl)
590
{
591
  /* If one reference is a component references through pointers try to find a
592
     common base and apply offset based disambiguation.  This handles
593
     for example
594
       struct A { int i; int j; } *q;
595
       struct B { struct A a; int k; } *p;
596
     disambiguating q->i and p->a.j.  */
597
  tree base1, base2;
598
  tree type1, type2;
599
  tree *refp;
600
  int same_p;
601
 
602
  /* Choose bases and base types to search for.  */
603
  base1 = ref1;
604
  while (handled_component_p (base1))
605
    base1 = TREE_OPERAND (base1, 0);
606
  type1 = TREE_TYPE (base1);
607
  base2 = ref2;
608
  while (handled_component_p (base2))
609
    base2 = TREE_OPERAND (base2, 0);
610
  type2 = TREE_TYPE (base2);
611
 
612
  /* Now search for the type1 in the access path of ref2.  This
613
     would be a common base for doing offset based disambiguation on.  */
614
  refp = &ref2;
615
  while (handled_component_p (*refp)
616
         && same_type_for_tbaa (TREE_TYPE (*refp), type1) == 0)
617
    refp = &TREE_OPERAND (*refp, 0);
618
  same_p = same_type_for_tbaa (TREE_TYPE (*refp), type1);
619
  /* If we couldn't compare types we have to bail out.  */
620
  if (same_p == -1)
621
    return true;
622
  else if (same_p == 1)
623
    {
624
      HOST_WIDE_INT offadj, sztmp, msztmp;
625
      get_ref_base_and_extent (*refp, &offadj, &sztmp, &msztmp);
626
      offset2 -= offadj;
627
      get_ref_base_and_extent (base1, &offadj, &sztmp, &msztmp);
628
      offset1 -= offadj;
629
      return ranges_overlap_p (offset1, max_size1, offset2, max_size2);
630
    }
631
  /* If we didn't find a common base, try the other way around.  */
632
  refp = &ref1;
633
  while (handled_component_p (*refp)
634
         && same_type_for_tbaa (TREE_TYPE (*refp), type2) == 0)
635
    refp = &TREE_OPERAND (*refp, 0);
636
  same_p = same_type_for_tbaa (TREE_TYPE (*refp), type2);
637
  /* If we couldn't compare types we have to bail out.  */
638
  if (same_p == -1)
639
    return true;
640
  else if (same_p == 1)
641
    {
642
      HOST_WIDE_INT offadj, sztmp, msztmp;
643
      get_ref_base_and_extent (*refp, &offadj, &sztmp, &msztmp);
644
      offset1 -= offadj;
645
      get_ref_base_and_extent (base2, &offadj, &sztmp, &msztmp);
646
      offset2 -= offadj;
647
      return ranges_overlap_p (offset1, max_size1, offset2, max_size2);
648
    }
649
 
650
  /* If we have two type access paths B1.path1 and B2.path2 they may
651
     only alias if either B1 is in B2.path2 or B2 is in B1.path1.
652
     But we can still have a path that goes B1.path1...B2.path2 with
653
     a part that we do not see.  So we can only disambiguate now
654
     if there is no B2 in the tail of path1 and no B1 on the
655
     tail of path2.  */
656
  if (base1_alias_set == ref2_alias_set
657
      || alias_set_subset_of (base1_alias_set, ref2_alias_set))
658
    return true;
659
  /* If this is ptr vs. decl then we know there is no ptr ... decl path.  */
660
  if (!ref2_is_decl)
661
    return (base2_alias_set == ref1_alias_set
662
            || alias_set_subset_of (base2_alias_set, ref1_alias_set));
663
  return false;
664
}
665
 
666
/* Return true if two memory references based on the variables BASE1
667
   and BASE2 constrained to [OFFSET1, OFFSET1 + MAX_SIZE1) and
668
   [OFFSET2, OFFSET2 + MAX_SIZE2) may alias.  */
669
 
670
static bool
671
decl_refs_may_alias_p (tree base1,
672
                       HOST_WIDE_INT offset1, HOST_WIDE_INT max_size1,
673
                       tree base2,
674
                       HOST_WIDE_INT offset2, HOST_WIDE_INT max_size2)
675
{
676
  gcc_checking_assert (DECL_P (base1) && DECL_P (base2));
677
 
678
  /* If both references are based on different variables, they cannot alias.  */
679
  if (base1 != base2)
680
    return false;
681
 
682
  /* If both references are based on the same variable, they cannot alias if
683
     the accesses do not overlap.  */
684
  return ranges_overlap_p (offset1, max_size1, offset2, max_size2);
685
}
686
 
687
/* Return true if an indirect reference based on *PTR1 constrained
688
   to [OFFSET1, OFFSET1 + MAX_SIZE1) may alias a variable based on BASE2
689
   constrained to [OFFSET2, OFFSET2 + MAX_SIZE2).  *PTR1 and BASE2 have
690
   the alias sets BASE1_ALIAS_SET and BASE2_ALIAS_SET which can be -1
691
   in which case they are computed on-demand.  REF1 and REF2
692
   if non-NULL are the complete memory reference trees.  */
693
 
694
static bool
695
indirect_ref_may_alias_decl_p (tree ref1 ATTRIBUTE_UNUSED, tree base1,
696
                               HOST_WIDE_INT offset1,
697
                               HOST_WIDE_INT max_size1 ATTRIBUTE_UNUSED,
698
                               alias_set_type ref1_alias_set,
699
                               alias_set_type base1_alias_set,
700
                               tree ref2 ATTRIBUTE_UNUSED, tree base2,
701
                               HOST_WIDE_INT offset2, HOST_WIDE_INT max_size2,
702
                               alias_set_type ref2_alias_set,
703
                               alias_set_type base2_alias_set, bool tbaa_p)
704
{
705
  tree ptr1;
706
  tree ptrtype1, dbase2;
707
  HOST_WIDE_INT offset1p = offset1, offset2p = offset2;
708
  HOST_WIDE_INT doffset1, doffset2;
709
  double_int moff;
710
 
711
  gcc_checking_assert ((TREE_CODE (base1) == MEM_REF
712
                        || TREE_CODE (base1) == TARGET_MEM_REF)
713
                       && DECL_P (base2));
714
 
715
  ptr1 = TREE_OPERAND (base1, 0);
716
 
717
  /* The offset embedded in MEM_REFs can be negative.  Bias them
718
     so that the resulting offset adjustment is positive.  */
719
  moff = mem_ref_offset (base1);
720
  moff = double_int_lshift (moff,
721
                            BITS_PER_UNIT == 8
722
                            ? 3 : exact_log2 (BITS_PER_UNIT),
723
                            HOST_BITS_PER_DOUBLE_INT, true);
724
  if (double_int_negative_p (moff))
725
    offset2p += double_int_neg (moff).low;
726
  else
727
    offset1p += moff.low;
728
 
729
  /* If only one reference is based on a variable, they cannot alias if
730
     the pointer access is beyond the extent of the variable access.
731
     (the pointer base cannot validly point to an offset less than zero
732
     of the variable).
733
     ???  IVOPTs creates bases that do not honor this restriction,
734
     so do not apply this optimization for TARGET_MEM_REFs.  */
735
  if (TREE_CODE (base1) != TARGET_MEM_REF
736
      && !ranges_overlap_p (MAX (0, offset1p), -1, offset2p, max_size2))
737
    return false;
738
  /* They also cannot alias if the pointer may not point to the decl.  */
739
  if (!ptr_deref_may_alias_decl_p (ptr1, base2))
740
    return false;
741
 
742
  /* Disambiguations that rely on strict aliasing rules follow.  */
743
  if (!flag_strict_aliasing || !tbaa_p)
744
    return true;
745
 
746
  ptrtype1 = TREE_TYPE (TREE_OPERAND (base1, 1));
747
 
748
  /* If the alias set for a pointer access is zero all bets are off.  */
749
  if (base1_alias_set == -1)
750
    base1_alias_set = get_deref_alias_set (ptrtype1);
751
  if (base1_alias_set == 0)
752
    return true;
753
  if (base2_alias_set == -1)
754
    base2_alias_set = get_alias_set (base2);
755
 
756
  /* When we are trying to disambiguate an access with a pointer dereference
757
     as base versus one with a decl as base we can use both the size
758
     of the decl and its dynamic type for extra disambiguation.
759
     ???  We do not know anything about the dynamic type of the decl
760
     other than that its alias-set contains base2_alias_set as a subset
761
     which does not help us here.  */
762
  /* As we know nothing useful about the dynamic type of the decl just
763
     use the usual conflict check rather than a subset test.
764
     ???  We could introduce -fvery-strict-aliasing when the language
765
     does not allow decls to have a dynamic type that differs from their
766
     static type.  Then we can check
767
     !alias_set_subset_of (base1_alias_set, base2_alias_set) instead.  */
768
  if (base1_alias_set != base2_alias_set
769
      && !alias_sets_conflict_p (base1_alias_set, base2_alias_set))
770
    return false;
771
  /* If the size of the access relevant for TBAA through the pointer
772
     is bigger than the size of the decl we can't possibly access the
773
     decl via that pointer.  */
774
  if (DECL_SIZE (base2) && COMPLETE_TYPE_P (TREE_TYPE (ptrtype1))
775
      && TREE_CODE (DECL_SIZE (base2)) == INTEGER_CST
776
      && TREE_CODE (TYPE_SIZE (TREE_TYPE (ptrtype1))) == INTEGER_CST
777
      /* ???  This in turn may run afoul when a decl of type T which is
778
         a member of union type U is accessed through a pointer to
779
         type U and sizeof T is smaller than sizeof U.  */
780
      && TREE_CODE (TREE_TYPE (ptrtype1)) != UNION_TYPE
781
      && TREE_CODE (TREE_TYPE (ptrtype1)) != QUAL_UNION_TYPE
782
      && tree_int_cst_lt (DECL_SIZE (base2), TYPE_SIZE (TREE_TYPE (ptrtype1))))
783
    return false;
784
 
785
  if (!ref2)
786
    return true;
787
 
788
  /* If the decl is accessed via a MEM_REF, reconstruct the base
789
     we can use for TBAA and an appropriately adjusted offset.  */
790
  dbase2 = ref2;
791
  while (handled_component_p (dbase2))
792
    dbase2 = TREE_OPERAND (dbase2, 0);
793
  doffset1 = offset1;
794
  doffset2 = offset2;
795
  if (TREE_CODE (dbase2) == MEM_REF
796
      || TREE_CODE (dbase2) == TARGET_MEM_REF)
797
    {
798
      double_int moff = mem_ref_offset (dbase2);
799
      moff = double_int_lshift (moff,
800
                                BITS_PER_UNIT == 8
801
                                ? 3 : exact_log2 (BITS_PER_UNIT),
802
                                HOST_BITS_PER_DOUBLE_INT, true);
803
      if (double_int_negative_p (moff))
804
        doffset1 -= double_int_neg (moff).low;
805
      else
806
        doffset2 -= moff.low;
807
    }
808
 
809
  /* If either reference is view-converted, give up now.  */
810
  if (same_type_for_tbaa (TREE_TYPE (base1), TREE_TYPE (ptrtype1)) != 1
811
      || same_type_for_tbaa (TREE_TYPE (dbase2),
812
                             TREE_TYPE (reference_alias_ptr_type (dbase2))) != 1)
813
    return true;
814
 
815
  /* If both references are through the same type, they do not alias
816
     if the accesses do not overlap.  This does extra disambiguation
817
     for mixed/pointer accesses but requires strict aliasing.
818
     For MEM_REFs we require that the component-ref offset we computed
819
     is relative to the start of the type which we ensure by
820
     comparing rvalue and access type and disregarding the constant
821
     pointer offset.  */
822
  if ((TREE_CODE (base1) != TARGET_MEM_REF
823
       || (!TMR_INDEX (base1) && !TMR_INDEX2 (base1)))
824
      && same_type_for_tbaa (TREE_TYPE (base1), TREE_TYPE (dbase2)) == 1)
825
    return ranges_overlap_p (doffset1, max_size1, doffset2, max_size2);
826
 
827
  /* Do access-path based disambiguation.  */
828
  if (ref1 && ref2
829
      && (handled_component_p (ref1) || handled_component_p (ref2)))
830
    return aliasing_component_refs_p (ref1,
831
                                      ref1_alias_set, base1_alias_set,
832
                                      offset1, max_size1,
833
                                      ref2,
834
                                      ref2_alias_set, base2_alias_set,
835
                                      offset2, max_size2, true);
836
 
837
  return true;
838
}
839
 
840
/* Return true if two indirect references based on *PTR1
841
   and *PTR2 constrained to [OFFSET1, OFFSET1 + MAX_SIZE1) and
842
   [OFFSET2, OFFSET2 + MAX_SIZE2) may alias.  *PTR1 and *PTR2 have
843
   the alias sets BASE1_ALIAS_SET and BASE2_ALIAS_SET which can be -1
844
   in which case they are computed on-demand.  REF1 and REF2
845
   if non-NULL are the complete memory reference trees. */
846
 
847
static bool
848
indirect_refs_may_alias_p (tree ref1 ATTRIBUTE_UNUSED, tree base1,
849
                           HOST_WIDE_INT offset1, HOST_WIDE_INT max_size1,
850
                           alias_set_type ref1_alias_set,
851
                           alias_set_type base1_alias_set,
852
                           tree ref2 ATTRIBUTE_UNUSED, tree base2,
853
                           HOST_WIDE_INT offset2, HOST_WIDE_INT max_size2,
854
                           alias_set_type ref2_alias_set,
855
                           alias_set_type base2_alias_set, bool tbaa_p)
856
{
857
  tree ptr1;
858
  tree ptr2;
859
  tree ptrtype1, ptrtype2;
860
 
861
  gcc_checking_assert ((TREE_CODE (base1) == MEM_REF
862
                        || TREE_CODE (base1) == TARGET_MEM_REF)
863
                       && (TREE_CODE (base2) == MEM_REF
864
                           || TREE_CODE (base2) == TARGET_MEM_REF));
865
 
866
  ptr1 = TREE_OPERAND (base1, 0);
867
  ptr2 = TREE_OPERAND (base2, 0);
868
 
869
  /* If both bases are based on pointers they cannot alias if they may not
870
     point to the same memory object or if they point to the same object
871
     and the accesses do not overlap.  */
872
  if ((!cfun || gimple_in_ssa_p (cfun))
873
      && operand_equal_p (ptr1, ptr2, 0)
874
      && (((TREE_CODE (base1) != TARGET_MEM_REF
875
            || (!TMR_INDEX (base1) && !TMR_INDEX2 (base1)))
876
           && (TREE_CODE (base2) != TARGET_MEM_REF
877
               || (!TMR_INDEX (base2) && !TMR_INDEX2 (base2))))
878
          || (TREE_CODE (base1) == TARGET_MEM_REF
879
              && TREE_CODE (base2) == TARGET_MEM_REF
880
              && (TMR_STEP (base1) == TMR_STEP (base2)
881
                  || (TMR_STEP (base1) && TMR_STEP (base2)
882
                      && operand_equal_p (TMR_STEP (base1),
883
                                          TMR_STEP (base2), 0)))
884
              && (TMR_INDEX (base1) == TMR_INDEX (base2)
885
                  || (TMR_INDEX (base1) && TMR_INDEX (base2)
886
                      && operand_equal_p (TMR_INDEX (base1),
887
                                          TMR_INDEX (base2), 0)))
888
              && (TMR_INDEX2 (base1) == TMR_INDEX2 (base2)
889
                  || (TMR_INDEX2 (base1) && TMR_INDEX2 (base2)
890
                      && operand_equal_p (TMR_INDEX2 (base1),
891
                                          TMR_INDEX2 (base2), 0))))))
892
    {
893
      double_int moff;
894
      /* The offset embedded in MEM_REFs can be negative.  Bias them
895
         so that the resulting offset adjustment is positive.  */
896
      moff = mem_ref_offset (base1);
897
      moff = double_int_lshift (moff,
898
                                BITS_PER_UNIT == 8
899
                                ? 3 : exact_log2 (BITS_PER_UNIT),
900
                                HOST_BITS_PER_DOUBLE_INT, true);
901
      if (double_int_negative_p (moff))
902
        offset2 += double_int_neg (moff).low;
903
      else
904
        offset1 += moff.low;
905
      moff = mem_ref_offset (base2);
906
      moff = double_int_lshift (moff,
907
                                BITS_PER_UNIT == 8
908
                                ? 3 : exact_log2 (BITS_PER_UNIT),
909
                                HOST_BITS_PER_DOUBLE_INT, true);
910
      if (double_int_negative_p (moff))
911
        offset1 += double_int_neg (moff).low;
912
      else
913
        offset2 += moff.low;
914
      return ranges_overlap_p (offset1, max_size1, offset2, max_size2);
915
    }
916
  if (!ptr_derefs_may_alias_p (ptr1, ptr2))
917
    return false;
918
 
919
  /* Disambiguations that rely on strict aliasing rules follow.  */
920
  if (!flag_strict_aliasing || !tbaa_p)
921
    return true;
922
 
923
  ptrtype1 = TREE_TYPE (TREE_OPERAND (base1, 1));
924
  ptrtype2 = TREE_TYPE (TREE_OPERAND (base2, 1));
925
 
926
  /* If the alias set for a pointer access is zero all bets are off.  */
927
  if (base1_alias_set == -1)
928
    base1_alias_set = get_deref_alias_set (ptrtype1);
929
  if (base1_alias_set == 0)
930
    return true;
931
  if (base2_alias_set == -1)
932
    base2_alias_set = get_deref_alias_set (ptrtype2);
933
  if (base2_alias_set == 0)
934
    return true;
935
 
936
  /* If both references are through the same type, they do not alias
937
     if the accesses do not overlap.  This does extra disambiguation
938
     for mixed/pointer accesses but requires strict aliasing.  */
939
  if ((TREE_CODE (base1) != TARGET_MEM_REF
940
       || (!TMR_INDEX (base1) && !TMR_INDEX2 (base1)))
941
      && (TREE_CODE (base2) != TARGET_MEM_REF
942
          || (!TMR_INDEX (base2) && !TMR_INDEX2 (base2)))
943
      && same_type_for_tbaa (TREE_TYPE (base1), TREE_TYPE (ptrtype1)) == 1
944
      && same_type_for_tbaa (TREE_TYPE (base2), TREE_TYPE (ptrtype2)) == 1
945
      && same_type_for_tbaa (TREE_TYPE (ptrtype1),
946
                             TREE_TYPE (ptrtype2)) == 1)
947
    return ranges_overlap_p (offset1, max_size1, offset2, max_size2);
948
 
949
  /* Do type-based disambiguation.  */
950
  if (base1_alias_set != base2_alias_set
951
      && !alias_sets_conflict_p (base1_alias_set, base2_alias_set))
952
    return false;
953
 
954
  /* Do access-path based disambiguation.  */
955
  if (ref1 && ref2
956
      && (handled_component_p (ref1) || handled_component_p (ref2))
957
      && same_type_for_tbaa (TREE_TYPE (base1), TREE_TYPE (ptrtype1)) == 1
958
      && same_type_for_tbaa (TREE_TYPE (base2), TREE_TYPE (ptrtype2)) == 1)
959
    return aliasing_component_refs_p (ref1,
960
                                      ref1_alias_set, base1_alias_set,
961
                                      offset1, max_size1,
962
                                      ref2,
963
                                      ref2_alias_set, base2_alias_set,
964
                                      offset2, max_size2, false);
965
 
966
  return true;
967
}
968
 
969
/* Return true, if the two memory references REF1 and REF2 may alias.  */
970
 
971
bool
972
refs_may_alias_p_1 (ao_ref *ref1, ao_ref *ref2, bool tbaa_p)
973
{
974
  tree base1, base2;
975
  HOST_WIDE_INT offset1 = 0, offset2 = 0;
976
  HOST_WIDE_INT max_size1 = -1, max_size2 = -1;
977
  bool var1_p, var2_p, ind1_p, ind2_p;
978
 
979
  gcc_checking_assert ((!ref1->ref
980
                        || TREE_CODE (ref1->ref) == SSA_NAME
981
                        || DECL_P (ref1->ref)
982
                        || TREE_CODE (ref1->ref) == STRING_CST
983
                        || handled_component_p (ref1->ref)
984
                        || TREE_CODE (ref1->ref) == MEM_REF
985
                        || TREE_CODE (ref1->ref) == TARGET_MEM_REF)
986
                       && (!ref2->ref
987
                           || TREE_CODE (ref2->ref) == SSA_NAME
988
                           || DECL_P (ref2->ref)
989
                           || TREE_CODE (ref2->ref) == STRING_CST
990
                           || handled_component_p (ref2->ref)
991
                           || TREE_CODE (ref2->ref) == MEM_REF
992
                           || TREE_CODE (ref2->ref) == TARGET_MEM_REF));
993
 
994
  /* Decompose the references into their base objects and the access.  */
995
  base1 = ao_ref_base (ref1);
996
  offset1 = ref1->offset;
997
  max_size1 = ref1->max_size;
998
  base2 = ao_ref_base (ref2);
999
  offset2 = ref2->offset;
1000
  max_size2 = ref2->max_size;
1001
 
1002
  /* We can end up with registers or constants as bases for example from
1003
     *D.1663_44 = VIEW_CONVERT_EXPR<struct DB_LSN>(__tmp$B0F64_59);
1004
     which is seen as a struct copy.  */
1005
  if (TREE_CODE (base1) == SSA_NAME
1006
      || TREE_CODE (base1) == CONST_DECL
1007
      || TREE_CODE (base1) == CONSTRUCTOR
1008
      || TREE_CODE (base1) == ADDR_EXPR
1009
      || CONSTANT_CLASS_P (base1)
1010
      || TREE_CODE (base2) == SSA_NAME
1011
      || TREE_CODE (base2) == CONST_DECL
1012
      || TREE_CODE (base2) == CONSTRUCTOR
1013
      || TREE_CODE (base2) == ADDR_EXPR
1014
      || CONSTANT_CLASS_P (base2))
1015
    return false;
1016
 
1017
  /* We can end up refering to code via function and label decls.
1018
     As we likely do not properly track code aliases conservatively
1019
     bail out.  */
1020
  if (TREE_CODE (base1) == FUNCTION_DECL
1021
      || TREE_CODE (base1) == LABEL_DECL
1022
      || TREE_CODE (base2) == FUNCTION_DECL
1023
      || TREE_CODE (base2) == LABEL_DECL)
1024
    return true;
1025
 
1026
  /* Two volatile accesses always conflict.  */
1027
  if (ref1->volatile_p
1028
      && ref2->volatile_p)
1029
    return true;
1030
 
1031
  /* Defer to simple offset based disambiguation if we have
1032
     references based on two decls.  Do this before defering to
1033
     TBAA to handle must-alias cases in conformance with the
1034
     GCC extension of allowing type-punning through unions.  */
1035
  var1_p = DECL_P (base1);
1036
  var2_p = DECL_P (base2);
1037
  if (var1_p && var2_p)
1038
    return decl_refs_may_alias_p (base1, offset1, max_size1,
1039
                                  base2, offset2, max_size2);
1040
 
1041
  ind1_p = (TREE_CODE (base1) == MEM_REF
1042
            || TREE_CODE (base1) == TARGET_MEM_REF);
1043
  ind2_p = (TREE_CODE (base2) == MEM_REF
1044
            || TREE_CODE (base2) == TARGET_MEM_REF);
1045
 
1046
  /* Canonicalize the pointer-vs-decl case.  */
1047
  if (ind1_p && var2_p)
1048
    {
1049
      HOST_WIDE_INT tmp1;
1050
      tree tmp2;
1051
      ao_ref *tmp3;
1052
      tmp1 = offset1; offset1 = offset2; offset2 = tmp1;
1053
      tmp1 = max_size1; max_size1 = max_size2; max_size2 = tmp1;
1054
      tmp2 = base1; base1 = base2; base2 = tmp2;
1055
      tmp3 = ref1; ref1 = ref2; ref2 = tmp3;
1056
      var1_p = true;
1057
      ind1_p = false;
1058
      var2_p = false;
1059
      ind2_p = true;
1060
    }
1061
 
1062
  /* First defer to TBAA if possible.  */
1063
  if (tbaa_p
1064
      && flag_strict_aliasing
1065
      && !alias_sets_conflict_p (ao_ref_alias_set (ref1),
1066
                                 ao_ref_alias_set (ref2)))
1067
    return false;
1068
 
1069
  /* Dispatch to the pointer-vs-decl or pointer-vs-pointer disambiguators.  */
1070
  if (var1_p && ind2_p)
1071
    return indirect_ref_may_alias_decl_p (ref2->ref, base2,
1072
                                          offset2, max_size2,
1073
                                          ao_ref_alias_set (ref2), -1,
1074
                                          ref1->ref, base1,
1075
                                          offset1, max_size1,
1076
                                          ao_ref_alias_set (ref1),
1077
                                          ao_ref_base_alias_set (ref1),
1078
                                          tbaa_p);
1079
  else if (ind1_p && ind2_p)
1080
    return indirect_refs_may_alias_p (ref1->ref, base1,
1081
                                      offset1, max_size1,
1082
                                      ao_ref_alias_set (ref1), -1,
1083
                                      ref2->ref, base2,
1084
                                      offset2, max_size2,
1085
                                      ao_ref_alias_set (ref2), -1,
1086
                                      tbaa_p);
1087
 
1088
  /* We really do not want to end up here, but returning true is safe.  */
1089
#ifdef ENABLE_CHECKING
1090
  gcc_unreachable ();
1091
#else
1092
  return true;
1093
#endif
1094
}
1095
 
1096
bool
1097
refs_may_alias_p (tree ref1, tree ref2)
1098
{
1099
  ao_ref r1, r2;
1100
  bool res;
1101
  ao_ref_init (&r1, ref1);
1102
  ao_ref_init (&r2, ref2);
1103
  res = refs_may_alias_p_1 (&r1, &r2, true);
1104
  if (res)
1105
    ++alias_stats.refs_may_alias_p_may_alias;
1106
  else
1107
    ++alias_stats.refs_may_alias_p_no_alias;
1108
  return res;
1109
}
1110
 
1111
/* Returns true if there is a anti-dependence for the STORE that
1112
   executes after the LOAD.  */
1113
 
1114
bool
1115
refs_anti_dependent_p (tree load, tree store)
1116
{
1117
  ao_ref r1, r2;
1118
  ao_ref_init (&r1, load);
1119
  ao_ref_init (&r2, store);
1120
  return refs_may_alias_p_1 (&r1, &r2, false);
1121
}
1122
 
1123
/* Returns true if there is a output dependence for the stores
1124
   STORE1 and STORE2.  */
1125
 
1126
bool
1127
refs_output_dependent_p (tree store1, tree store2)
1128
{
1129
  ao_ref r1, r2;
1130
  ao_ref_init (&r1, store1);
1131
  ao_ref_init (&r2, store2);
1132
  return refs_may_alias_p_1 (&r1, &r2, false);
1133
}
1134
 
1135
/* If the call CALL may use the memory reference REF return true,
1136
   otherwise return false.  */
1137
 
1138
static bool
1139
ref_maybe_used_by_call_p_1 (gimple call, ao_ref *ref)
1140
{
1141
  tree base, callee;
1142
  unsigned i;
1143
  int flags = gimple_call_flags (call);
1144
 
1145
  /* Const functions without a static chain do not implicitly use memory.  */
1146
  if (!gimple_call_chain (call)
1147
      && (flags & (ECF_CONST|ECF_NOVOPS)))
1148
    goto process_args;
1149
 
1150
  base = ao_ref_base (ref);
1151
  if (!base)
1152
    return true;
1153
 
1154
  /* A call that is not without side-effects might involve volatile
1155
     accesses and thus conflicts with all other volatile accesses.  */
1156
  if (ref->volatile_p)
1157
    return true;
1158
 
1159
  /* If the reference is based on a decl that is not aliased the call
1160
     cannot possibly use it.  */
1161
  if (DECL_P (base)
1162
      && !may_be_aliased (base)
1163
      /* But local statics can be used through recursion.  */
1164
      && !is_global_var (base))
1165
    goto process_args;
1166
 
1167
  callee = gimple_call_fndecl (call);
1168
 
1169
  /* Handle those builtin functions explicitly that do not act as
1170
     escape points.  See tree-ssa-structalias.c:find_func_aliases
1171
     for the list of builtins we might need to handle here.  */
1172
  if (callee != NULL_TREE
1173
      && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL)
1174
    switch (DECL_FUNCTION_CODE (callee))
1175
      {
1176
        /* All the following functions read memory pointed to by
1177
           their second argument.  strcat/strncat additionally
1178
           reads memory pointed to by the first argument.  */
1179
        case BUILT_IN_STRCAT:
1180
        case BUILT_IN_STRNCAT:
1181
          {
1182
            ao_ref dref;
1183
            ao_ref_init_from_ptr_and_size (&dref,
1184
                                           gimple_call_arg (call, 0),
1185
                                           NULL_TREE);
1186
            if (refs_may_alias_p_1 (&dref, ref, false))
1187
              return true;
1188
          }
1189
          /* FALLTHRU */
1190
        case BUILT_IN_STRCPY:
1191
        case BUILT_IN_STRNCPY:
1192
        case BUILT_IN_MEMCPY:
1193
        case BUILT_IN_MEMMOVE:
1194
        case BUILT_IN_MEMPCPY:
1195
        case BUILT_IN_STPCPY:
1196
        case BUILT_IN_STPNCPY:
1197
        case BUILT_IN_TM_MEMCPY:
1198
        case BUILT_IN_TM_MEMMOVE:
1199
          {
1200
            ao_ref dref;
1201
            tree size = NULL_TREE;
1202
            if (gimple_call_num_args (call) == 3)
1203
              size = gimple_call_arg (call, 2);
1204
            ao_ref_init_from_ptr_and_size (&dref,
1205
                                           gimple_call_arg (call, 1),
1206
                                           size);
1207
            return refs_may_alias_p_1 (&dref, ref, false);
1208
          }
1209
        case BUILT_IN_STRCAT_CHK:
1210
        case BUILT_IN_STRNCAT_CHK:
1211
          {
1212
            ao_ref dref;
1213
            ao_ref_init_from_ptr_and_size (&dref,
1214
                                           gimple_call_arg (call, 0),
1215
                                           NULL_TREE);
1216
            if (refs_may_alias_p_1 (&dref, ref, false))
1217
              return true;
1218
          }
1219
          /* FALLTHRU */
1220
        case BUILT_IN_STRCPY_CHK:
1221
        case BUILT_IN_STRNCPY_CHK:
1222
        case BUILT_IN_MEMCPY_CHK:
1223
        case BUILT_IN_MEMMOVE_CHK:
1224
        case BUILT_IN_MEMPCPY_CHK:
1225
        case BUILT_IN_STPCPY_CHK:
1226
        case BUILT_IN_STPNCPY_CHK:
1227
          {
1228
            ao_ref dref;
1229
            tree size = NULL_TREE;
1230
            if (gimple_call_num_args (call) == 4)
1231
              size = gimple_call_arg (call, 2);
1232
            ao_ref_init_from_ptr_and_size (&dref,
1233
                                           gimple_call_arg (call, 1),
1234
                                           size);
1235
            return refs_may_alias_p_1 (&dref, ref, false);
1236
          }
1237
        case BUILT_IN_BCOPY:
1238
          {
1239
            ao_ref dref;
1240
            tree size = gimple_call_arg (call, 2);
1241
            ao_ref_init_from_ptr_and_size (&dref,
1242
                                           gimple_call_arg (call, 0),
1243
                                           size);
1244
            return refs_may_alias_p_1 (&dref, ref, false);
1245
          }
1246
 
1247
        /* The following functions read memory pointed to by their
1248
           first argument.  */
1249
        CASE_BUILT_IN_TM_LOAD (1):
1250
        CASE_BUILT_IN_TM_LOAD (2):
1251
        CASE_BUILT_IN_TM_LOAD (4):
1252
        CASE_BUILT_IN_TM_LOAD (8):
1253
        CASE_BUILT_IN_TM_LOAD (FLOAT):
1254
        CASE_BUILT_IN_TM_LOAD (DOUBLE):
1255
        CASE_BUILT_IN_TM_LOAD (LDOUBLE):
1256
        CASE_BUILT_IN_TM_LOAD (M64):
1257
        CASE_BUILT_IN_TM_LOAD (M128):
1258
        CASE_BUILT_IN_TM_LOAD (M256):
1259
        case BUILT_IN_TM_LOG:
1260
        case BUILT_IN_TM_LOG_1:
1261
        case BUILT_IN_TM_LOG_2:
1262
        case BUILT_IN_TM_LOG_4:
1263
        case BUILT_IN_TM_LOG_8:
1264
        case BUILT_IN_TM_LOG_FLOAT:
1265
        case BUILT_IN_TM_LOG_DOUBLE:
1266
        case BUILT_IN_TM_LOG_LDOUBLE:
1267
        case BUILT_IN_TM_LOG_M64:
1268
        case BUILT_IN_TM_LOG_M128:
1269
        case BUILT_IN_TM_LOG_M256:
1270
          return ptr_deref_may_alias_ref_p_1 (gimple_call_arg (call, 0), ref);
1271
 
1272
        /* These read memory pointed to by the first argument.  */
1273
        case BUILT_IN_STRDUP:
1274
        case BUILT_IN_STRNDUP:
1275
          {
1276
            ao_ref dref;
1277
            tree size = NULL_TREE;
1278
            if (gimple_call_num_args (call) == 2)
1279
              size = gimple_call_arg (call, 1);
1280
            ao_ref_init_from_ptr_and_size (&dref,
1281
                                           gimple_call_arg (call, 0),
1282
                                           size);
1283
            return refs_may_alias_p_1 (&dref, ref, false);
1284
          }
1285
        /* The following builtins do not read from memory.  */
1286
        case BUILT_IN_FREE:
1287
        case BUILT_IN_MALLOC:
1288
        case BUILT_IN_CALLOC:
1289
        case BUILT_IN_ALLOCA:
1290
        case BUILT_IN_ALLOCA_WITH_ALIGN:
1291
        case BUILT_IN_STACK_SAVE:
1292
        case BUILT_IN_STACK_RESTORE:
1293
        case BUILT_IN_MEMSET:
1294
        case BUILT_IN_TM_MEMSET:
1295
        case BUILT_IN_MEMSET_CHK:
1296
        case BUILT_IN_FREXP:
1297
        case BUILT_IN_FREXPF:
1298
        case BUILT_IN_FREXPL:
1299
        case BUILT_IN_GAMMA_R:
1300
        case BUILT_IN_GAMMAF_R:
1301
        case BUILT_IN_GAMMAL_R:
1302
        case BUILT_IN_LGAMMA_R:
1303
        case BUILT_IN_LGAMMAF_R:
1304
        case BUILT_IN_LGAMMAL_R:
1305
        case BUILT_IN_MODF:
1306
        case BUILT_IN_MODFF:
1307
        case BUILT_IN_MODFL:
1308
        case BUILT_IN_REMQUO:
1309
        case BUILT_IN_REMQUOF:
1310
        case BUILT_IN_REMQUOL:
1311
        case BUILT_IN_SINCOS:
1312
        case BUILT_IN_SINCOSF:
1313
        case BUILT_IN_SINCOSL:
1314
        case BUILT_IN_ASSUME_ALIGNED:
1315
        case BUILT_IN_VA_END:
1316
          return false;
1317
        /* __sync_* builtins and some OpenMP builtins act as threading
1318
           barriers.  */
1319
#undef DEF_SYNC_BUILTIN
1320
#define DEF_SYNC_BUILTIN(ENUM, NAME, TYPE, ATTRS) case ENUM:
1321
#include "sync-builtins.def"
1322
#undef DEF_SYNC_BUILTIN
1323
        case BUILT_IN_GOMP_ATOMIC_START:
1324
        case BUILT_IN_GOMP_ATOMIC_END:
1325
        case BUILT_IN_GOMP_BARRIER:
1326
        case BUILT_IN_GOMP_TASKWAIT:
1327
        case BUILT_IN_GOMP_CRITICAL_START:
1328
        case BUILT_IN_GOMP_CRITICAL_END:
1329
        case BUILT_IN_GOMP_CRITICAL_NAME_START:
1330
        case BUILT_IN_GOMP_CRITICAL_NAME_END:
1331
        case BUILT_IN_GOMP_LOOP_END:
1332
        case BUILT_IN_GOMP_ORDERED_START:
1333
        case BUILT_IN_GOMP_ORDERED_END:
1334
        case BUILT_IN_GOMP_PARALLEL_END:
1335
        case BUILT_IN_GOMP_SECTIONS_END:
1336
        case BUILT_IN_GOMP_SINGLE_COPY_START:
1337
        case BUILT_IN_GOMP_SINGLE_COPY_END:
1338
          return true;
1339
 
1340
        default:
1341
          /* Fallthru to general call handling.  */;
1342
      }
1343
 
1344
  /* Check if base is a global static variable that is not read
1345
     by the function.  */
1346
  if (callee != NULL_TREE
1347
      && TREE_CODE (base) == VAR_DECL
1348
      && TREE_STATIC (base))
1349
    {
1350
      struct cgraph_node *node = cgraph_get_node (callee);
1351
      bitmap not_read;
1352
 
1353
      /* FIXME: Callee can be an OMP builtin that does not have a call graph
1354
         node yet.  We should enforce that there are nodes for all decls in the
1355
         IL and remove this check instead.  */
1356
      if (node
1357
          && (not_read = ipa_reference_get_not_read_global (node))
1358
          && bitmap_bit_p (not_read, DECL_UID (base)))
1359
        goto process_args;
1360
    }
1361
 
1362
  /* Check if the base variable is call-used.  */
1363
  if (DECL_P (base))
1364
    {
1365
      if (pt_solution_includes (gimple_call_use_set (call), base))
1366
        return true;
1367
    }
1368
  else if ((TREE_CODE (base) == MEM_REF
1369
            || TREE_CODE (base) == TARGET_MEM_REF)
1370
           && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME)
1371
    {
1372
      struct ptr_info_def *pi = SSA_NAME_PTR_INFO (TREE_OPERAND (base, 0));
1373
      if (!pi)
1374
        return true;
1375
 
1376
      if (pt_solutions_intersect (gimple_call_use_set (call), &pi->pt))
1377
        return true;
1378
    }
1379
  else
1380
    return true;
1381
 
1382
  /* Inspect call arguments for passed-by-value aliases.  */
1383
process_args:
1384
  for (i = 0; i < gimple_call_num_args (call); ++i)
1385
    {
1386
      tree op = gimple_call_arg (call, i);
1387
      int flags = gimple_call_arg_flags (call, i);
1388
 
1389
      if (flags & EAF_UNUSED)
1390
        continue;
1391
 
1392
      if (TREE_CODE (op) == WITH_SIZE_EXPR)
1393
        op = TREE_OPERAND (op, 0);
1394
 
1395
      if (TREE_CODE (op) != SSA_NAME
1396
          && !is_gimple_min_invariant (op))
1397
        {
1398
          ao_ref r;
1399
          ao_ref_init (&r, op);
1400
          if (refs_may_alias_p_1 (&r, ref, true))
1401
            return true;
1402
        }
1403
    }
1404
 
1405
  return false;
1406
}
1407
 
1408
static bool
1409
ref_maybe_used_by_call_p (gimple call, tree ref)
1410
{
1411
  ao_ref r;
1412
  bool res;
1413
  ao_ref_init (&r, ref);
1414
  res = ref_maybe_used_by_call_p_1 (call, &r);
1415
  if (res)
1416
    ++alias_stats.ref_maybe_used_by_call_p_may_alias;
1417
  else
1418
    ++alias_stats.ref_maybe_used_by_call_p_no_alias;
1419
  return res;
1420
}
1421
 
1422
 
1423
/* If the statement STMT may use the memory reference REF return
1424
   true, otherwise return false.  */
1425
 
1426
bool
1427
ref_maybe_used_by_stmt_p (gimple stmt, tree ref)
1428
{
1429
  if (is_gimple_assign (stmt))
1430
    {
1431
      tree rhs;
1432
 
1433
      /* All memory assign statements are single.  */
1434
      if (!gimple_assign_single_p (stmt))
1435
        return false;
1436
 
1437
      rhs = gimple_assign_rhs1 (stmt);
1438
      if (is_gimple_reg (rhs)
1439
          || is_gimple_min_invariant (rhs)
1440
          || gimple_assign_rhs_code (stmt) == CONSTRUCTOR)
1441
        return false;
1442
 
1443
      return refs_may_alias_p (rhs, ref);
1444
    }
1445
  else if (is_gimple_call (stmt))
1446
    return ref_maybe_used_by_call_p (stmt, ref);
1447
  else if (gimple_code (stmt) == GIMPLE_RETURN)
1448
    {
1449
      tree retval = gimple_return_retval (stmt);
1450
      tree base;
1451
      if (retval
1452
          && TREE_CODE (retval) != SSA_NAME
1453
          && !is_gimple_min_invariant (retval)
1454
          && refs_may_alias_p (retval, ref))
1455
        return true;
1456
      /* If ref escapes the function then the return acts as a use.  */
1457
      base = get_base_address (ref);
1458
      if (!base)
1459
        ;
1460
      else if (DECL_P (base))
1461
        return is_global_var (base);
1462
      else if (TREE_CODE (base) == MEM_REF
1463
               || TREE_CODE (base) == TARGET_MEM_REF)
1464
        return ptr_deref_may_alias_global_p (TREE_OPERAND (base, 0));
1465
      return false;
1466
    }
1467
 
1468
  return true;
1469
}
1470
 
1471
/* If the call in statement CALL may clobber the memory reference REF
1472
   return true, otherwise return false.  */
1473
 
1474
static bool
1475
call_may_clobber_ref_p_1 (gimple call, ao_ref *ref)
1476
{
1477
  tree base;
1478
  tree callee;
1479
 
1480
  /* If the call is pure or const it cannot clobber anything.  */
1481
  if (gimple_call_flags (call)
1482
      & (ECF_PURE|ECF_CONST|ECF_LOOPING_CONST_OR_PURE|ECF_NOVOPS))
1483
    return false;
1484
 
1485
  base = ao_ref_base (ref);
1486
  if (!base)
1487
    return true;
1488
 
1489
  if (TREE_CODE (base) == SSA_NAME
1490
      || CONSTANT_CLASS_P (base))
1491
    return false;
1492
 
1493
  /* A call that is not without side-effects might involve volatile
1494
     accesses and thus conflicts with all other volatile accesses.  */
1495
  if (ref->volatile_p)
1496
    return true;
1497
 
1498
  /* If the reference is based on a decl that is not aliased the call
1499
     cannot possibly clobber it.  */
1500
  if (DECL_P (base)
1501
      && !may_be_aliased (base)
1502
      /* But local non-readonly statics can be modified through recursion
1503
         or the call may implement a threading barrier which we must
1504
         treat as may-def.  */
1505
      && (TREE_READONLY (base)
1506
          || !is_global_var (base)))
1507
    return false;
1508
 
1509
  callee = gimple_call_fndecl (call);
1510
 
1511
  /* Handle those builtin functions explicitly that do not act as
1512
     escape points.  See tree-ssa-structalias.c:find_func_aliases
1513
     for the list of builtins we might need to handle here.  */
1514
  if (callee != NULL_TREE
1515
      && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL)
1516
    switch (DECL_FUNCTION_CODE (callee))
1517
      {
1518
        /* All the following functions clobber memory pointed to by
1519
           their first argument.  */
1520
        case BUILT_IN_STRCPY:
1521
        case BUILT_IN_STRNCPY:
1522
        case BUILT_IN_MEMCPY:
1523
        case BUILT_IN_MEMMOVE:
1524
        case BUILT_IN_MEMPCPY:
1525
        case BUILT_IN_STPCPY:
1526
        case BUILT_IN_STPNCPY:
1527
        case BUILT_IN_STRCAT:
1528
        case BUILT_IN_STRNCAT:
1529
        case BUILT_IN_MEMSET:
1530
        case BUILT_IN_TM_MEMSET:
1531
        CASE_BUILT_IN_TM_STORE (1):
1532
        CASE_BUILT_IN_TM_STORE (2):
1533
        CASE_BUILT_IN_TM_STORE (4):
1534
        CASE_BUILT_IN_TM_STORE (8):
1535
        CASE_BUILT_IN_TM_STORE (FLOAT):
1536
        CASE_BUILT_IN_TM_STORE (DOUBLE):
1537
        CASE_BUILT_IN_TM_STORE (LDOUBLE):
1538
        CASE_BUILT_IN_TM_STORE (M64):
1539
        CASE_BUILT_IN_TM_STORE (M128):
1540
        CASE_BUILT_IN_TM_STORE (M256):
1541
        case BUILT_IN_TM_MEMCPY:
1542
        case BUILT_IN_TM_MEMMOVE:
1543
          {
1544
            ao_ref dref;
1545
            tree size = NULL_TREE;
1546
            /* Don't pass in size for strncat, as the maximum size
1547
               is strlen (dest) + n + 1 instead of n, resp.
1548
               n + 1 at dest + strlen (dest), but strlen (dest) isn't
1549
               known.  */
1550
            if (gimple_call_num_args (call) == 3
1551
                && DECL_FUNCTION_CODE (callee) != BUILT_IN_STRNCAT)
1552
              size = gimple_call_arg (call, 2);
1553
            ao_ref_init_from_ptr_and_size (&dref,
1554
                                           gimple_call_arg (call, 0),
1555
                                           size);
1556
            return refs_may_alias_p_1 (&dref, ref, false);
1557
          }
1558
        case BUILT_IN_STRCPY_CHK:
1559
        case BUILT_IN_STRNCPY_CHK:
1560
        case BUILT_IN_MEMCPY_CHK:
1561
        case BUILT_IN_MEMMOVE_CHK:
1562
        case BUILT_IN_MEMPCPY_CHK:
1563
        case BUILT_IN_STPCPY_CHK:
1564
        case BUILT_IN_STPNCPY_CHK:
1565
        case BUILT_IN_STRCAT_CHK:
1566
        case BUILT_IN_STRNCAT_CHK:
1567
        case BUILT_IN_MEMSET_CHK:
1568
          {
1569
            ao_ref dref;
1570
            tree size = NULL_TREE;
1571
            /* Don't pass in size for __strncat_chk, as the maximum size
1572
               is strlen (dest) + n + 1 instead of n, resp.
1573
               n + 1 at dest + strlen (dest), but strlen (dest) isn't
1574
               known.  */
1575
            if (gimple_call_num_args (call) == 4
1576
                && DECL_FUNCTION_CODE (callee) != BUILT_IN_STRNCAT_CHK)
1577
              size = gimple_call_arg (call, 2);
1578
            ao_ref_init_from_ptr_and_size (&dref,
1579
                                           gimple_call_arg (call, 0),
1580
                                           size);
1581
            return refs_may_alias_p_1 (&dref, ref, false);
1582
          }
1583
        case BUILT_IN_BCOPY:
1584
          {
1585
            ao_ref dref;
1586
            tree size = gimple_call_arg (call, 2);
1587
            ao_ref_init_from_ptr_and_size (&dref,
1588
                                           gimple_call_arg (call, 1),
1589
                                           size);
1590
            return refs_may_alias_p_1 (&dref, ref, false);
1591
          }
1592
        /* Allocating memory does not have any side-effects apart from
1593
           being the definition point for the pointer.  */
1594
        case BUILT_IN_MALLOC:
1595
        case BUILT_IN_CALLOC:
1596
        case BUILT_IN_STRDUP:
1597
        case BUILT_IN_STRNDUP:
1598
          /* Unix98 specifies that errno is set on allocation failure.  */
1599
          if (flag_errno_math
1600
              && targetm.ref_may_alias_errno (ref))
1601
            return true;
1602
          return false;
1603
        case BUILT_IN_STACK_SAVE:
1604
        case BUILT_IN_ALLOCA:
1605
        case BUILT_IN_ALLOCA_WITH_ALIGN:
1606
        case BUILT_IN_ASSUME_ALIGNED:
1607
          return false;
1608
        /* Freeing memory kills the pointed-to memory.  More importantly
1609
           the call has to serve as a barrier for moving loads and stores
1610
           across it.  */
1611
        case BUILT_IN_FREE:
1612
        case BUILT_IN_VA_END:
1613
          {
1614
            tree ptr = gimple_call_arg (call, 0);
1615
            return ptr_deref_may_alias_ref_p_1 (ptr, ref);
1616
          }
1617
        case BUILT_IN_GAMMA_R:
1618
        case BUILT_IN_GAMMAF_R:
1619
        case BUILT_IN_GAMMAL_R:
1620
        case BUILT_IN_LGAMMA_R:
1621
        case BUILT_IN_LGAMMAF_R:
1622
        case BUILT_IN_LGAMMAL_R:
1623
          {
1624
            tree out = gimple_call_arg (call, 1);
1625
            if (ptr_deref_may_alias_ref_p_1 (out, ref))
1626
              return true;
1627
            if (flag_errno_math)
1628
              break;
1629
            return false;
1630
          }
1631
        case BUILT_IN_FREXP:
1632
        case BUILT_IN_FREXPF:
1633
        case BUILT_IN_FREXPL:
1634
        case BUILT_IN_MODF:
1635
        case BUILT_IN_MODFF:
1636
        case BUILT_IN_MODFL:
1637
          {
1638
            tree out = gimple_call_arg (call, 1);
1639
            return ptr_deref_may_alias_ref_p_1 (out, ref);
1640
          }
1641
        case BUILT_IN_REMQUO:
1642
        case BUILT_IN_REMQUOF:
1643
        case BUILT_IN_REMQUOL:
1644
          {
1645
            tree out = gimple_call_arg (call, 2);
1646
            if (ptr_deref_may_alias_ref_p_1 (out, ref))
1647
              return true;
1648
            if (flag_errno_math)
1649
              break;
1650
            return false;
1651
          }
1652
        case BUILT_IN_SINCOS:
1653
        case BUILT_IN_SINCOSF:
1654
        case BUILT_IN_SINCOSL:
1655
          {
1656
            tree sin = gimple_call_arg (call, 1);
1657
            tree cos = gimple_call_arg (call, 2);
1658
            return (ptr_deref_may_alias_ref_p_1 (sin, ref)
1659
                    || ptr_deref_may_alias_ref_p_1 (cos, ref));
1660
          }
1661
        /* __sync_* builtins and some OpenMP builtins act as threading
1662
           barriers.  */
1663
#undef DEF_SYNC_BUILTIN
1664
#define DEF_SYNC_BUILTIN(ENUM, NAME, TYPE, ATTRS) case ENUM:
1665
#include "sync-builtins.def"
1666
#undef DEF_SYNC_BUILTIN
1667
        case BUILT_IN_GOMP_ATOMIC_START:
1668
        case BUILT_IN_GOMP_ATOMIC_END:
1669
        case BUILT_IN_GOMP_BARRIER:
1670
        case BUILT_IN_GOMP_TASKWAIT:
1671
        case BUILT_IN_GOMP_CRITICAL_START:
1672
        case BUILT_IN_GOMP_CRITICAL_END:
1673
        case BUILT_IN_GOMP_CRITICAL_NAME_START:
1674
        case BUILT_IN_GOMP_CRITICAL_NAME_END:
1675
        case BUILT_IN_GOMP_LOOP_END:
1676
        case BUILT_IN_GOMP_ORDERED_START:
1677
        case BUILT_IN_GOMP_ORDERED_END:
1678
        case BUILT_IN_GOMP_PARALLEL_END:
1679
        case BUILT_IN_GOMP_SECTIONS_END:
1680
        case BUILT_IN_GOMP_SINGLE_COPY_START:
1681
        case BUILT_IN_GOMP_SINGLE_COPY_END:
1682
          return true;
1683
        default:
1684
          /* Fallthru to general call handling.  */;
1685
      }
1686
 
1687
  /* Check if base is a global static variable that is not written
1688
     by the function.  */
1689
  if (callee != NULL_TREE
1690
      && TREE_CODE (base) == VAR_DECL
1691
      && TREE_STATIC (base))
1692
    {
1693
      struct cgraph_node *node = cgraph_get_node (callee);
1694
      bitmap not_written;
1695
 
1696
      if (node
1697
          && (not_written = ipa_reference_get_not_written_global (node))
1698
          && bitmap_bit_p (not_written, DECL_UID (base)))
1699
        return false;
1700
    }
1701
 
1702
  /* Check if the base variable is call-clobbered.  */
1703
  if (DECL_P (base))
1704
    return pt_solution_includes (gimple_call_clobber_set (call), base);
1705
  else if ((TREE_CODE (base) == MEM_REF
1706
            || TREE_CODE (base) == TARGET_MEM_REF)
1707
           && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME)
1708
    {
1709
      struct ptr_info_def *pi = SSA_NAME_PTR_INFO (TREE_OPERAND (base, 0));
1710
      if (!pi)
1711
        return true;
1712
 
1713
      return pt_solutions_intersect (gimple_call_clobber_set (call), &pi->pt);
1714
    }
1715
 
1716
  return true;
1717
}
1718
 
1719
/* If the call in statement CALL may clobber the memory reference REF
1720
   return true, otherwise return false.  */
1721
 
1722
bool
1723
call_may_clobber_ref_p (gimple call, tree ref)
1724
{
1725
  bool res;
1726
  ao_ref r;
1727
  ao_ref_init (&r, ref);
1728
  res = call_may_clobber_ref_p_1 (call, &r);
1729
  if (res)
1730
    ++alias_stats.call_may_clobber_ref_p_may_alias;
1731
  else
1732
    ++alias_stats.call_may_clobber_ref_p_no_alias;
1733
  return res;
1734
}
1735
 
1736
 
1737
/* If the statement STMT may clobber the memory reference REF return true,
1738
   otherwise return false.  */
1739
 
1740
bool
1741
stmt_may_clobber_ref_p_1 (gimple stmt, ao_ref *ref)
1742
{
1743
  if (is_gimple_call (stmt))
1744
    {
1745
      tree lhs = gimple_call_lhs (stmt);
1746
      if (lhs
1747
          && TREE_CODE (lhs) != SSA_NAME)
1748
        {
1749
          ao_ref r;
1750
          ao_ref_init (&r, lhs);
1751
          if (refs_may_alias_p_1 (ref, &r, true))
1752
            return true;
1753
        }
1754
 
1755
      return call_may_clobber_ref_p_1 (stmt, ref);
1756
    }
1757
  else if (gimple_assign_single_p (stmt))
1758
    {
1759
      tree lhs = gimple_assign_lhs (stmt);
1760
      if (TREE_CODE (lhs) != SSA_NAME)
1761
        {
1762
          ao_ref r;
1763
          ao_ref_init (&r, lhs);
1764
          return refs_may_alias_p_1 (ref, &r, true);
1765
        }
1766
    }
1767
  else if (gimple_code (stmt) == GIMPLE_ASM)
1768
    return true;
1769
 
1770
  return false;
1771
}
1772
 
1773
bool
1774
stmt_may_clobber_ref_p (gimple stmt, tree ref)
1775
{
1776
  ao_ref r;
1777
  ao_ref_init (&r, ref);
1778
  return stmt_may_clobber_ref_p_1 (stmt, &r);
1779
}
1780
 
1781
/* If STMT kills the memory reference REF return true, otherwise
1782
   return false.  */
1783
 
1784
static bool
1785
stmt_kills_ref_p_1 (gimple stmt, ao_ref *ref)
1786
{
1787
  /* For a must-alias check we need to be able to constrain
1788
     the access properly.  */
1789
  ao_ref_base (ref);
1790
  if (ref->max_size == -1)
1791
    return false;
1792
 
1793
  if (gimple_has_lhs (stmt)
1794
      && TREE_CODE (gimple_get_lhs (stmt)) != SSA_NAME
1795
      /* The assignment is not necessarily carried out if it can throw
1796
         and we can catch it in the current function where we could inspect
1797
         the previous value.
1798
         ???  We only need to care about the RHS throwing.  For aggregate
1799
         assignments or similar calls and non-call exceptions the LHS
1800
         might throw as well.  */
1801
      && !stmt_can_throw_internal (stmt))
1802
    {
1803
      tree base, lhs = gimple_get_lhs (stmt);
1804
      HOST_WIDE_INT size, offset, max_size;
1805
      base = get_ref_base_and_extent (lhs, &offset, &size, &max_size);
1806
      /* We can get MEM[symbol: sZ, index: D.8862_1] here,
1807
         so base == ref->base does not always hold.  */
1808
      if (base == ref->base)
1809
        {
1810
          /* For a must-alias check we need to be able to constrain
1811
             the access properly.  */
1812
          if (size != -1 && size == max_size)
1813
            {
1814
              if (offset <= ref->offset
1815
                  && offset + size >= ref->offset + ref->max_size)
1816
                return true;
1817
            }
1818
        }
1819
    }
1820
 
1821
  if (is_gimple_call (stmt))
1822
    {
1823
      tree callee = gimple_call_fndecl (stmt);
1824
      if (callee != NULL_TREE
1825
          && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL)
1826
        switch (DECL_FUNCTION_CODE (callee))
1827
          {
1828
          case BUILT_IN_MEMCPY:
1829
          case BUILT_IN_MEMPCPY:
1830
          case BUILT_IN_MEMMOVE:
1831
          case BUILT_IN_MEMSET:
1832
          case BUILT_IN_MEMCPY_CHK:
1833
          case BUILT_IN_MEMPCPY_CHK:
1834
          case BUILT_IN_MEMMOVE_CHK:
1835
          case BUILT_IN_MEMSET_CHK:
1836
            {
1837
              tree dest = gimple_call_arg (stmt, 0);
1838
              tree len = gimple_call_arg (stmt, 2);
1839
              tree base = NULL_TREE;
1840
              HOST_WIDE_INT offset = 0;
1841
              if (!host_integerp (len, 0))
1842
                return false;
1843
              if (TREE_CODE (dest) == ADDR_EXPR)
1844
                base = get_addr_base_and_unit_offset (TREE_OPERAND (dest, 0),
1845
                                                      &offset);
1846
              else if (TREE_CODE (dest) == SSA_NAME)
1847
                base = dest;
1848
              if (base
1849
                  && base == ao_ref_base (ref))
1850
                {
1851
                  HOST_WIDE_INT size = TREE_INT_CST_LOW (len);
1852
                  if (offset <= ref->offset / BITS_PER_UNIT
1853
                      && (offset + size
1854
                          >= ((ref->offset + ref->max_size + BITS_PER_UNIT - 1)
1855
                              / BITS_PER_UNIT)))
1856
                    return true;
1857
                }
1858
              break;
1859
            }
1860
 
1861
          case BUILT_IN_VA_END:
1862
            {
1863
              tree ptr = gimple_call_arg (stmt, 0);
1864
              if (TREE_CODE (ptr) == ADDR_EXPR)
1865
                {
1866
                  tree base = ao_ref_base (ref);
1867
                  if (TREE_OPERAND (ptr, 0) == base)
1868
                    return true;
1869
                }
1870
              break;
1871
            }
1872
 
1873
          default:;
1874
          }
1875
    }
1876
  return false;
1877
}
1878
 
1879
bool
1880
stmt_kills_ref_p (gimple stmt, tree ref)
1881
{
1882
  ao_ref r;
1883
  ao_ref_init (&r, ref);
1884
  return stmt_kills_ref_p_1 (stmt, &r);
1885
}
1886
 
1887
 
1888
/* Walk the virtual use-def chain of VUSE until hitting the virtual operand
1889
   TARGET or a statement clobbering the memory reference REF in which
1890
   case false is returned.  The walk starts with VUSE, one argument of PHI.  */
1891
 
1892
static bool
1893
maybe_skip_until (gimple phi, tree target, ao_ref *ref,
1894
                  tree vuse, bitmap *visited)
1895
{
1896
  basic_block bb = gimple_bb (phi);
1897
 
1898
  if (!*visited)
1899
    *visited = BITMAP_ALLOC (NULL);
1900
 
1901
  bitmap_set_bit (*visited, SSA_NAME_VERSION (PHI_RESULT (phi)));
1902
 
1903
  /* Walk until we hit the target.  */
1904
  while (vuse != target)
1905
    {
1906
      gimple def_stmt = SSA_NAME_DEF_STMT (vuse);
1907
      /* Recurse for PHI nodes.  */
1908
      if (gimple_code (def_stmt) == GIMPLE_PHI)
1909
        {
1910
          /* An already visited PHI node ends the walk successfully.  */
1911
          if (bitmap_bit_p (*visited, SSA_NAME_VERSION (PHI_RESULT (def_stmt))))
1912
            return true;
1913
          vuse = get_continuation_for_phi (def_stmt, ref, visited);
1914
          if (!vuse)
1915
            return false;
1916
          continue;
1917
        }
1918
      /* A clobbering statement or the end of the IL ends it failing.  */
1919
      else if (gimple_nop_p (def_stmt)
1920
               || stmt_may_clobber_ref_p_1 (def_stmt, ref))
1921
        return false;
1922
      /* If we reach a new basic-block see if we already skipped it
1923
         in a previous walk that ended successfully.  */
1924
      if (gimple_bb (def_stmt) != bb)
1925
        {
1926
          if (!bitmap_set_bit (*visited, SSA_NAME_VERSION (vuse)))
1927
            return true;
1928
          bb = gimple_bb (def_stmt);
1929
        }
1930
      vuse = gimple_vuse (def_stmt);
1931
    }
1932
  return true;
1933
}
1934
 
1935
/* For two PHI arguments ARG0 and ARG1 try to skip non-aliasing code
1936
   until we hit the phi argument definition that dominates the other one.
1937
   Return that, or NULL_TREE if there is no such definition.  */
1938
 
1939
static tree
1940
get_continuation_for_phi_1 (gimple phi, tree arg0, tree arg1,
1941
                            ao_ref *ref, bitmap *visited)
1942
{
1943
  gimple def0 = SSA_NAME_DEF_STMT (arg0);
1944
  gimple def1 = SSA_NAME_DEF_STMT (arg1);
1945
  tree common_vuse;
1946
 
1947
  if (arg0 == arg1)
1948
    return arg0;
1949
  else if (gimple_nop_p (def0)
1950
           || (!gimple_nop_p (def1)
1951
               && dominated_by_p (CDI_DOMINATORS,
1952
                                  gimple_bb (def1), gimple_bb (def0))))
1953
    {
1954
      if (maybe_skip_until (phi, arg0, ref, arg1, visited))
1955
        return arg0;
1956
    }
1957
  else if (gimple_nop_p (def1)
1958
           || dominated_by_p (CDI_DOMINATORS,
1959
                              gimple_bb (def0), gimple_bb (def1)))
1960
    {
1961
      if (maybe_skip_until (phi, arg1, ref, arg0, visited))
1962
        return arg1;
1963
    }
1964
  /* Special case of a diamond:
1965
       MEM_1 = ...
1966
       goto (cond) ? L1 : L2
1967
       L1: store1 = ...    #MEM_2 = vuse(MEM_1)
1968
           goto L3
1969
       L2: store2 = ...    #MEM_3 = vuse(MEM_1)
1970
       L3: MEM_4 = PHI<MEM_2, MEM_3>
1971
     We were called with the PHI at L3, MEM_2 and MEM_3 don't
1972
     dominate each other, but still we can easily skip this PHI node
1973
     if we recognize that the vuse MEM operand is the same for both,
1974
     and that we can skip both statements (they don't clobber us).
1975
     This is still linear.  Don't use maybe_skip_until, that might
1976
     potentially be slow.  */
1977
  else if ((common_vuse = gimple_vuse (def0))
1978
           && common_vuse == gimple_vuse (def1))
1979
    {
1980
      if (!stmt_may_clobber_ref_p_1 (def0, ref)
1981
          && !stmt_may_clobber_ref_p_1 (def1, ref))
1982
        return common_vuse;
1983
    }
1984
 
1985
  return NULL_TREE;
1986
}
1987
 
1988
 
1989
/* Starting from a PHI node for the virtual operand of the memory reference
1990
   REF find a continuation virtual operand that allows to continue walking
1991
   statements dominating PHI skipping only statements that cannot possibly
1992
   clobber REF.  Returns NULL_TREE if no suitable virtual operand can
1993
   be found.  */
1994
 
1995
tree
1996
get_continuation_for_phi (gimple phi, ao_ref *ref, bitmap *visited)
1997
{
1998
  unsigned nargs = gimple_phi_num_args (phi);
1999
 
2000
  /* Through a single-argument PHI we can simply look through.  */
2001
  if (nargs == 1)
2002
    return PHI_ARG_DEF (phi, 0);
2003
 
2004
  /* For two or more arguments try to pairwise skip non-aliasing code
2005
     until we hit the phi argument definition that dominates the other one.  */
2006
  else if (nargs >= 2)
2007
    {
2008
      tree arg0, arg1;
2009
      unsigned i;
2010
 
2011
      /* Find a candidate for the virtual operand which definition
2012
         dominates those of all others.  */
2013
      arg0 = PHI_ARG_DEF (phi, 0);
2014
      if (!SSA_NAME_IS_DEFAULT_DEF (arg0))
2015
        for (i = 1; i < nargs; ++i)
2016
          {
2017
            arg1 = PHI_ARG_DEF (phi, i);
2018
            if (SSA_NAME_IS_DEFAULT_DEF (arg1))
2019
              {
2020
                arg0 = arg1;
2021
                break;
2022
              }
2023
            if (dominated_by_p (CDI_DOMINATORS,
2024
                                gimple_bb (SSA_NAME_DEF_STMT (arg0)),
2025
                                gimple_bb (SSA_NAME_DEF_STMT (arg1))))
2026
              arg0 = arg1;
2027
          }
2028
 
2029
      /* Then pairwise reduce against the found candidate.  */
2030
      for (i = 0; i < nargs; ++i)
2031
        {
2032
          arg1 = PHI_ARG_DEF (phi, i);
2033
          arg0 = get_continuation_for_phi_1 (phi, arg0, arg1, ref, visited);
2034
          if (!arg0)
2035
            return NULL_TREE;
2036
        }
2037
 
2038
      return arg0;
2039
    }
2040
 
2041
  return NULL_TREE;
2042
}
2043
 
2044
/* Based on the memory reference REF and its virtual use VUSE call
2045
   WALKER for each virtual use that is equivalent to VUSE, including VUSE
2046
   itself.  That is, for each virtual use for which its defining statement
2047
   does not clobber REF.
2048
 
2049
   WALKER is called with REF, the current virtual use and DATA.  If
2050
   WALKER returns non-NULL the walk stops and its result is returned.
2051
   At the end of a non-successful walk NULL is returned.
2052
 
2053
   TRANSLATE if non-NULL is called with a pointer to REF, the virtual
2054
   use which definition is a statement that may clobber REF and DATA.
2055
   If TRANSLATE returns (void *)-1 the walk stops and NULL is returned.
2056
   If TRANSLATE returns non-NULL the walk stops and its result is returned.
2057
   If TRANSLATE returns NULL the walk continues and TRANSLATE is supposed
2058
   to adjust REF and *DATA to make that valid.
2059
 
2060
   TODO: Cache the vector of equivalent vuses per ref, vuse pair.  */
2061
 
2062
void *
2063
walk_non_aliased_vuses (ao_ref *ref, tree vuse,
2064
                        void *(*walker)(ao_ref *, tree, void *),
2065
                        void *(*translate)(ao_ref *, tree, void *), void *data)
2066
{
2067
  bitmap visited = NULL;
2068
  void *res;
2069
 
2070
  timevar_push (TV_ALIAS_STMT_WALK);
2071
 
2072
  do
2073
    {
2074
      gimple def_stmt;
2075
 
2076
      /* ???  Do we want to account this to TV_ALIAS_STMT_WALK?  */
2077
      res = (*walker) (ref, vuse, data);
2078
      if (res)
2079
        break;
2080
 
2081
      def_stmt = SSA_NAME_DEF_STMT (vuse);
2082
      if (gimple_nop_p (def_stmt))
2083
        break;
2084
      else if (gimple_code (def_stmt) == GIMPLE_PHI)
2085
        vuse = get_continuation_for_phi (def_stmt, ref, &visited);
2086
      else
2087
        {
2088
          if (stmt_may_clobber_ref_p_1 (def_stmt, ref))
2089
            {
2090
              if (!translate)
2091
                break;
2092
              res = (*translate) (ref, vuse, data);
2093
              /* Failed lookup and translation.  */
2094
              if (res == (void *)-1)
2095
                {
2096
                  res = NULL;
2097
                  break;
2098
                }
2099
              /* Lookup succeeded.  */
2100
              else if (res != NULL)
2101
                break;
2102
              /* Translation succeeded, continue walking.  */
2103
            }
2104
          vuse = gimple_vuse (def_stmt);
2105
        }
2106
    }
2107
  while (vuse);
2108
 
2109
  if (visited)
2110
    BITMAP_FREE (visited);
2111
 
2112
  timevar_pop (TV_ALIAS_STMT_WALK);
2113
 
2114
  return res;
2115
}
2116
 
2117
 
2118
/* Based on the memory reference REF call WALKER for each vdef which
2119
   defining statement may clobber REF, starting with VDEF.  If REF
2120
   is NULL_TREE, each defining statement is visited.
2121
 
2122
   WALKER is called with REF, the current vdef and DATA.  If WALKER
2123
   returns true the walk is stopped, otherwise it continues.
2124
 
2125
   At PHI nodes walk_aliased_vdefs forks into one walk for reach
2126
   PHI argument (but only one walk continues on merge points), the
2127
   return value is true if any of the walks was successful.
2128
 
2129
   The function returns the number of statements walked.  */
2130
 
2131
static unsigned int
2132
walk_aliased_vdefs_1 (ao_ref *ref, tree vdef,
2133
                      bool (*walker)(ao_ref *, tree, void *), void *data,
2134
                      bitmap *visited, unsigned int cnt)
2135
{
2136
  do
2137
    {
2138
      gimple def_stmt = SSA_NAME_DEF_STMT (vdef);
2139
 
2140
      if (*visited
2141
          && !bitmap_set_bit (*visited, SSA_NAME_VERSION (vdef)))
2142
        return cnt;
2143
 
2144
      if (gimple_nop_p (def_stmt))
2145
        return cnt;
2146
      else if (gimple_code (def_stmt) == GIMPLE_PHI)
2147
        {
2148
          unsigned i;
2149
          if (!*visited)
2150
            *visited = BITMAP_ALLOC (NULL);
2151
          for (i = 0; i < gimple_phi_num_args (def_stmt); ++i)
2152
            cnt += walk_aliased_vdefs_1 (ref, gimple_phi_arg_def (def_stmt, i),
2153
                                         walker, data, visited, 0);
2154
          return cnt;
2155
        }
2156
 
2157
      /* ???  Do we want to account this to TV_ALIAS_STMT_WALK?  */
2158
      cnt++;
2159
      if ((!ref
2160
           || stmt_may_clobber_ref_p_1 (def_stmt, ref))
2161
          && (*walker) (ref, vdef, data))
2162
        return cnt;
2163
 
2164
      vdef = gimple_vuse (def_stmt);
2165
    }
2166
  while (1);
2167
}
2168
 
2169
unsigned int
2170
walk_aliased_vdefs (ao_ref *ref, tree vdef,
2171
                    bool (*walker)(ao_ref *, tree, void *), void *data,
2172
                    bitmap *visited)
2173
{
2174
  bitmap local_visited = NULL;
2175
  unsigned int ret;
2176
 
2177
  timevar_push (TV_ALIAS_STMT_WALK);
2178
 
2179
  ret = walk_aliased_vdefs_1 (ref, vdef, walker, data,
2180
                              visited ? visited : &local_visited, 0);
2181
  if (local_visited)
2182
    BITMAP_FREE (local_visited);
2183
 
2184
  timevar_pop (TV_ALIAS_STMT_WALK);
2185
 
2186
  return ret;
2187
}
2188
 

powered by: WebSVN 2.1.0

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