Branch data Line data Source code
1 : : /* Tree based points-to analysis
2 : : Copyright (C) 2005-2025 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 : 225286526 : get_varinfo (unsigned int n)
196 : : {
197 : 4879297593 : 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 : 632421874 : vi_next (varinfo_t vi)
205 : : {
206 : 632421874 : 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 */
|
