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