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 : : /* Use 0x8000... as special unknown offset. */
38 : : #define UNKNOWN_OFFSET HOST_WIDE_INT_MIN
39 : :
40 : : /* An expression that appears in a constraint. */
41 : :
42 : : struct constraint_expr
43 : : {
44 : : /* Constraint type. */
45 : : constraint_expr_type type;
46 : :
47 : : /* Variable we are referring to in the constraint. */
48 : : unsigned int var;
49 : :
50 : : /* Offset, in bits, of this constraint from the beginning of
51 : : variables it ends up referring to.
52 : :
53 : : IOW, in a deref constraint, we would deref, get the result set,
54 : : then add OFFSET to each member. */
55 : : HOST_WIDE_INT offset;
56 : : };
57 : : typedef struct constraint_expr ce_s;
58 : :
59 : : /* Our set constraints are made up of two constraint expressions, one
60 : : LHS, and one RHS.
61 : :
62 : : As described in the introduction in tree-ssa-structalias.cc, our set
63 : : constraints each represent an operation between set valued variables.
64 : : */
65 : : struct constraint
66 : : {
67 : : struct constraint_expr lhs;
68 : : struct constraint_expr rhs;
69 : : };
70 : : typedef struct constraint *constraint_t;
71 : :
72 : : struct variable_info
73 : : {
74 : : /* ID of this variable. */
75 : : unsigned int id;
76 : :
77 : : /* True if this is a variable created by the constraint analysis, such as
78 : : heap variables and constraints we had to break up. */
79 : : unsigned int is_artificial_var : 1;
80 : :
81 : : /* True if this is a special variable whose solution set should not be
82 : : changed. */
83 : : unsigned int is_special_var : 1;
84 : :
85 : : /* True for variables whose size is not known or variable. */
86 : : unsigned int is_unknown_size_var : 1;
87 : :
88 : : /* True for (sub-)fields that represent a whole variable. */
89 : : unsigned int is_full_var : 1;
90 : :
91 : : /* True if this is a heap variable. */
92 : : unsigned int is_heap_var : 1;
93 : :
94 : : /* True if this is a register variable. */
95 : : unsigned int is_reg_var : 1;
96 : :
97 : : /* True if this field may contain pointers. */
98 : : unsigned int may_have_pointers : 1;
99 : :
100 : : /* True if this field has only restrict qualified pointers. */
101 : : unsigned int only_restrict_pointers : 1;
102 : :
103 : : /* True if this represents a heap var created for a restrict qualified
104 : : pointer. */
105 : : unsigned int is_restrict_var : 1;
106 : :
107 : : /* True if this represents a global variable. */
108 : : unsigned int is_global_var : 1;
109 : :
110 : : /* True if this represents a module escape point for IPA analysis. */
111 : : unsigned int is_ipa_escape_point : 1;
112 : :
113 : : /* True if this represents a IPA function info. */
114 : : unsigned int is_fn_info : 1;
115 : :
116 : : /* True if this appears as RHS in a ADDRESSOF constraint. */
117 : : unsigned int address_taken : 1;
118 : :
119 : : /* ??? Store somewhere better. */
120 : : unsigned short ruid;
121 : :
122 : : /* The ID of the variable for the next field in this structure
123 : : or zero for the last field in this structure. */
124 : : unsigned next;
125 : :
126 : : /* The ID of the variable for the first field in this structure. */
127 : : unsigned head;
128 : :
129 : : /* Offset of this variable, in bits, from the base variable. */
130 : : unsigned HOST_WIDE_INT offset;
131 : :
132 : : /* Size of the variable, in bits. */
133 : : unsigned HOST_WIDE_INT size;
134 : :
135 : : /* Full size of the base variable, in bits. */
136 : : unsigned HOST_WIDE_INT fullsize;
137 : :
138 : : /* In IPA mode the shadow UID in case the variable needs to be duplicated in
139 : : the final points-to solution because it reaches its containing
140 : : function recursively. Zero if none is needed. */
141 : : unsigned int shadow_var_uid;
142 : :
143 : : /* Name of this variable. */
144 : : const char *name;
145 : :
146 : : /* Tree that this variable is associated with. */
147 : : tree decl;
148 : :
149 : : /* Points-to set for this variable. */
150 : : bitmap solution;
151 : :
152 : : /* Old points-to set for this variable. */
153 : : bitmap oldsolution;
154 : : };
155 : : typedef struct variable_info *varinfo_t;
156 : :
157 : : struct constraint_stats
158 : : {
159 : : unsigned int total_vars;
160 : : unsigned int nonpointer_vars;
161 : : unsigned int unified_vars_static;
162 : : unsigned int unified_vars_dynamic;
163 : : unsigned int iterations;
164 : : unsigned int num_edges;
165 : : unsigned int num_implicit_edges;
166 : : unsigned int num_avoided_edges;
167 : : unsigned int points_to_sets_created;
168 : : };
169 : :
170 : : extern struct constraint_stats stats;
171 : :
172 : : extern bitmap_obstack pta_obstack;
173 : : extern bitmap_obstack oldpta_obstack;
174 : :
175 : : extern vec<varinfo_t> varmap;
176 : : extern vec<constraint_t> constraints;
177 : : extern unsigned int *var_rep;
178 : :
179 : :
180 : : /* Return the varmap element N. */
181 : :
182 : : inline varinfo_t
183 : 227592154 : get_varinfo (unsigned int n)
184 : : {
185 : 4928576806 : return varmap[n];
186 : : }
187 : :
188 : : /* Return the next variable in the list of sub-variables of VI
189 : : or NULL if VI is the last sub-variable. */
190 : :
191 : : inline varinfo_t
192 : 641703028 : vi_next (varinfo_t vi)
193 : : {
194 : 641703028 : return get_varinfo (vi->next);
195 : : }
196 : :
197 : : varinfo_t first_vi_for_offset (varinfo_t start,
198 : : unsigned HOST_WIDE_INT offset);
199 : : varinfo_t first_or_preceding_vi_for_offset (varinfo_t start,
200 : : unsigned HOST_WIDE_INT offset);
201 : : void dump_constraint (FILE *file, constraint_t c);
202 : : void dump_constraints (FILE *file, int from);
203 : : void dump_solution_for_var (FILE *file, unsigned int var);
204 : : void dump_sa_stats (FILE *outfile);
205 : : void dump_sa_points_to_info (FILE *outfile);
206 : : void dump_varinfo (FILE *file, varinfo_t vi);
207 : : void dump_varmap (FILE *file);
208 : : void debug_constraint (constraint_t);
209 : : void debug_constraints (void);
210 : : void debug_solution_for_var (unsigned int);
211 : : void debug_sa_points_to_info (void);
212 : : void debug_varinfo (varinfo_t);
213 : : void debug_varmap (void);
214 : :
215 : : } // namespace pointer_analysis
216 : :
217 : : #endif /* TREE_SSA_STRUCTALIAS_H */
|
