1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
|
/* Tree based points-to analysis
Copyright (C) 2005-2025 Free Software Foundation, Inc.
Contributed by Daniel Berlin <dberlin@dberlin.org>
This file is part of GCC.
GCC is free software; you can redistribute it and/or modify
under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 3 of the License, or
(at your option) any later version.
GCC is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3. If not see
<http://www.gnu.org/licenses/>. */
/* NOTE: This file declares the internal interface of the points-to analyzer.
Outward-facing function declarations can be found in tree-ssa-alias.h. */
#ifndef TREE_SSA_STRUCTALIAS_H
#define TREE_SSA_STRUCTALIAS_H
namespace pointer_analysis {
enum constraint_expr_type {SCALAR, DEREF, ADDRESSOF};
/* Static IDs for the special variables. Variable ID zero is unused
and used as terminator for the sub-variable chain. */
enum { nothing_id = 1, anything_id = 2, string_id = 3,
escaped_id = 4, nonlocal_id = 5, escaped_return_id = 6,
storedanything_id = 7, integer_id = 8 };
/* Use 0x8000... as special unknown offset. */
#define UNKNOWN_OFFSET HOST_WIDE_INT_MIN
/* An expression that appears in a constraint. */
struct constraint_expr
{
/* Constraint type. */
constraint_expr_type type;
/* Variable we are referring to in the constraint. */
unsigned int var;
/* Offset, in bits, of this constraint from the beginning of
variables it ends up referring to.
IOW, in a deref constraint, we would deref, get the result set,
then add OFFSET to each member. */
HOST_WIDE_INT offset;
};
typedef struct constraint_expr ce_s;
/* Our set constraints are made up of two constraint expressions, one
LHS, and one RHS.
As described in the introduction in tree-ssa-structalias.cc, our set
constraints each represent an operation between set valued variables.
*/
struct constraint
{
struct constraint_expr lhs;
struct constraint_expr rhs;
};
typedef struct constraint *constraint_t;
struct variable_info
{
/* ID of this variable. */
unsigned int id;
/* True if this is a variable created by the constraint analysis, such as
heap variables and constraints we had to break up. */
unsigned int is_artificial_var : 1;
/* True if this is a special variable whose solution set should not be
changed. */
unsigned int is_special_var : 1;
/* True for variables whose size is not known or variable. */
unsigned int is_unknown_size_var : 1;
/* True for (sub-)fields that represent a whole variable. */
unsigned int is_full_var : 1;
/* True if this is a heap variable. */
unsigned int is_heap_var : 1;
/* True if this is a register variable. */
unsigned int is_reg_var : 1;
/* True if this field may contain pointers. */
unsigned int may_have_pointers : 1;
/* True if this field has only restrict qualified pointers. */
unsigned int only_restrict_pointers : 1;
/* True if this represents a heap var created for a restrict qualified
pointer. */
unsigned int is_restrict_var : 1;
/* True if this represents a global variable. */
unsigned int is_global_var : 1;
/* True if this represents a module escape point for IPA analysis. */
unsigned int is_ipa_escape_point : 1;
/* True if this represents a IPA function info. */
unsigned int is_fn_info : 1;
/* True if this appears as RHS in a ADDRESSOF constraint. */
unsigned int address_taken : 1;
/* ??? Store somewhere better. */
unsigned short ruid;
/* The ID of the variable for the next field in this structure
or zero for the last field in this structure. */
unsigned next;
/* The ID of the variable for the first field in this structure. */
unsigned head;
/* Offset of this variable, in bits, from the base variable. */
unsigned HOST_WIDE_INT offset;
/* Size of the variable, in bits. */
unsigned HOST_WIDE_INT size;
/* Full size of the base variable, in bits. */
unsigned HOST_WIDE_INT fullsize;
/* In IPA mode the shadow UID in case the variable needs to be duplicated in
the final points-to solution because it reaches its containing
function recursively. Zero if none is needed. */
unsigned int shadow_var_uid;
/* Name of this variable. */
const char *name;
/* Tree that this variable is associated with. */
tree decl;
/* Points-to set for this variable. */
bitmap solution;
/* Old points-to set for this variable. */
bitmap oldsolution;
};
typedef struct variable_info *varinfo_t;
struct constraint_stats
{
unsigned int total_vars;
unsigned int nonpointer_vars;
unsigned int unified_vars_static;
unsigned int unified_vars_dynamic;
unsigned int iterations;
unsigned int num_edges;
unsigned int num_implicit_edges;
unsigned int num_avoided_edges;
unsigned int points_to_sets_created;
};
extern struct constraint_stats stats;
extern bitmap_obstack pta_obstack;
extern bitmap_obstack oldpta_obstack;
extern vec<varinfo_t> varmap;
extern vec<constraint_t> constraints;
extern unsigned int *var_rep;
/* Return the varmap element N. */
inline varinfo_t
get_varinfo (unsigned int n)
{
return varmap[n];
}
/* Return the next variable in the list of sub-variables of VI
or NULL if VI is the last sub-variable. */
inline varinfo_t
vi_next (varinfo_t vi)
{
return get_varinfo (vi->next);
}
varinfo_t first_vi_for_offset (varinfo_t start,
unsigned HOST_WIDE_INT offset);
varinfo_t first_or_preceding_vi_for_offset (varinfo_t start,
unsigned HOST_WIDE_INT offset);
void dump_constraint (FILE *file, constraint_t c);
void dump_constraints (FILE *file, int from);
void dump_solution_for_var (FILE *file, unsigned int var);
void dump_sa_stats (FILE *outfile);
void dump_sa_points_to_info (FILE *outfile);
void dump_varinfo (FILE *file, varinfo_t vi);
void dump_varmap (FILE *file);
void debug_constraint (constraint_t);
void debug_constraints (void);
void debug_solution_for_var (unsigned int);
void debug_sa_points_to_info (void);
void debug_varinfo (varinfo_t);
void debug_varmap (void);
} // namespace pointer_analysis
#endif /* TREE_SSA_STRUCTALIAS_H */
|
