]>
Commit | Line | Data |
---|---|---|
910fdc79 | 1 | /* Tree based points-to analysis |
62e5bf5d | 2 | Copyright (C) 2005, 2006, 2007 Free Software Foundation, Inc. |
910fdc79 DB |
3 | Contributed by Daniel Berlin <dberlin@dberlin.org> |
4 | ||
9dcd6f09 | 5 | This file is part of GCC. |
910fdc79 | 6 | |
9dcd6f09 NC |
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. | |
910fdc79 | 11 | |
9dcd6f09 NC |
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. | |
910fdc79 | 16 | |
9dcd6f09 NC |
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/>. */ | |
910fdc79 DB |
20 | |
21 | #include "config.h" | |
22 | #include "system.h" | |
23 | #include "coretypes.h" | |
24 | #include "tm.h" | |
25 | #include "ggc.h" | |
26 | #include "obstack.h" | |
27 | #include "bitmap.h" | |
910fdc79 DB |
28 | #include "flags.h" |
29 | #include "rtl.h" | |
30 | #include "tm_p.h" | |
31 | #include "hard-reg-set.h" | |
32 | #include "basic-block.h" | |
33 | #include "output.h" | |
34 | #include "errors.h" | |
910fdc79 DB |
35 | #include "diagnostic.h" |
36 | #include "tree.h" | |
37 | #include "c-common.h" | |
38 | #include "tree-flow.h" | |
39 | #include "tree-inline.h" | |
40 | #include "varray.h" | |
41 | #include "c-tree.h" | |
42 | #include "tree-gimple.h" | |
43 | #include "hashtab.h" | |
44 | #include "function.h" | |
45 | #include "cgraph.h" | |
46 | #include "tree-pass.h" | |
47 | #include "timevar.h" | |
48 | #include "alloc-pool.h" | |
49 | #include "splay-tree.h" | |
a916f21d | 50 | #include "params.h" |
e8ca4159 | 51 | #include "tree-ssa-structalias.h" |
4ee00913 | 52 | #include "cgraph.h" |
c58936b6 | 53 | #include "alias.h" |
38635499 | 54 | #include "pointer-set.h" |
910fdc79 DB |
55 | |
56 | /* The idea behind this analyzer is to generate set constraints from the | |
57 | program, then solve the resulting constraints in order to generate the | |
c58936b6 | 58 | points-to sets. |
910fdc79 DB |
59 | |
60 | Set constraints are a way of modeling program analysis problems that | |
61 | involve sets. They consist of an inclusion constraint language, | |
62 | describing the variables (each variable is a set) and operations that | |
63 | are involved on the variables, and a set of rules that derive facts | |
64 | from these operations. To solve a system of set constraints, you derive | |
65 | all possible facts under the rules, which gives you the correct sets | |
66 | as a consequence. | |
67 | ||
68 | See "Efficient Field-sensitive pointer analysis for C" by "David | |
69 | J. Pearce and Paul H. J. Kelly and Chris Hankin, at | |
70 | http://citeseer.ist.psu.edu/pearce04efficient.html | |
71 | ||
72 | Also see "Ultra-fast Aliasing Analysis using CLA: A Million Lines | |
73 | of C Code in a Second" by ""Nevin Heintze and Olivier Tardieu" at | |
c58936b6 DB |
74 | http://citeseer.ist.psu.edu/heintze01ultrafast.html |
75 | ||
76 | There are three types of real constraint expressions, DEREF, | |
3e5937d7 | 77 | ADDRESSOF, and SCALAR. Each constraint expression consists |
c58936b6 | 78 | of a constraint type, a variable, and an offset. |
910fdc79 | 79 | |
910fdc79 DB |
80 | SCALAR is a constraint expression type used to represent x, whether |
81 | it appears on the LHS or the RHS of a statement. | |
82 | DEREF is a constraint expression type used to represent *x, whether | |
c58936b6 | 83 | it appears on the LHS or the RHS of a statement. |
910fdc79 | 84 | ADDRESSOF is a constraint expression used to represent &x, whether |
607fb860 | 85 | it appears on the LHS or the RHS of a statement. |
c58936b6 | 86 | |
910fdc79 DB |
87 | Each pointer variable in the program is assigned an integer id, and |
88 | each field of a structure variable is assigned an integer id as well. | |
c58936b6 | 89 | |
910fdc79 DB |
90 | Structure variables are linked to their list of fields through a "next |
91 | field" in each variable that points to the next field in offset | |
c58936b6 DB |
92 | order. |
93 | Each variable for a structure field has | |
910fdc79 DB |
94 | |
95 | 1. "size", that tells the size in bits of that field. | |
96 | 2. "fullsize, that tells the size in bits of the entire structure. | |
97 | 3. "offset", that tells the offset in bits from the beginning of the | |
98 | structure to this field. | |
99 | ||
c58936b6 | 100 | Thus, |
910fdc79 DB |
101 | struct f |
102 | { | |
103 | int a; | |
104 | int b; | |
105 | } foo; | |
106 | int *bar; | |
107 | ||
108 | looks like | |
109 | ||
110 | foo.a -> id 1, size 32, offset 0, fullsize 64, next foo.b | |
111 | foo.b -> id 2, size 32, offset 32, fullsize 64, next NULL | |
112 | bar -> id 3, size 32, offset 0, fullsize 32, next NULL | |
113 | ||
c58936b6 | 114 | |
910fdc79 DB |
115 | In order to solve the system of set constraints, the following is |
116 | done: | |
117 | ||
118 | 1. Each constraint variable x has a solution set associated with it, | |
119 | Sol(x). | |
c58936b6 | 120 | |
910fdc79 DB |
121 | 2. Constraints are separated into direct, copy, and complex. |
122 | Direct constraints are ADDRESSOF constraints that require no extra | |
123 | processing, such as P = &Q | |
124 | Copy constraints are those of the form P = Q. | |
2941f691 DB |
125 | Complex constraints are all the constraints involving dereferences |
126 | and offsets (including offsetted copies). | |
c58936b6 | 127 | |
910fdc79 | 128 | 3. All direct constraints of the form P = &Q are processed, such |
c58936b6 | 129 | that Q is added to Sol(P) |
910fdc79 DB |
130 | |
131 | 4. All complex constraints for a given constraint variable are stored in a | |
c58936b6 | 132 | linked list attached to that variable's node. |
910fdc79 DB |
133 | |
134 | 5. A directed graph is built out of the copy constraints. Each | |
c58936b6 | 135 | constraint variable is a node in the graph, and an edge from |
910fdc79 | 136 | Q to P is added for each copy constraint of the form P = Q |
c58936b6 | 137 | |
910fdc79 DB |
138 | 6. The graph is then walked, and solution sets are |
139 | propagated along the copy edges, such that an edge from Q to P | |
140 | causes Sol(P) <- Sol(P) union Sol(Q). | |
c58936b6 | 141 | |
910fdc79 | 142 | 7. As we visit each node, all complex constraints associated with |
607fb860 | 143 | that node are processed by adding appropriate copy edges to the graph, or the |
c58936b6 | 144 | appropriate variables to the solution set. |
910fdc79 DB |
145 | |
146 | 8. The process of walking the graph is iterated until no solution | |
147 | sets change. | |
148 | ||
149 | Prior to walking the graph in steps 6 and 7, We perform static | |
c58936b6 | 150 | cycle elimination on the constraint graph, as well |
910fdc79 | 151 | as off-line variable substitution. |
c58936b6 | 152 | |
910fdc79 DB |
153 | TODO: Adding offsets to pointer-to-structures can be handled (IE not punted |
154 | on and turned into anything), but isn't. You can just see what offset | |
155 | inside the pointed-to struct it's going to access. | |
c58936b6 | 156 | |
910fdc79 | 157 | TODO: Constant bounded arrays can be handled as if they were structs of the |
c58936b6 | 158 | same number of elements. |
910fdc79 DB |
159 | |
160 | TODO: Modeling heap and incoming pointers becomes much better if we | |
161 | add fields to them as we discover them, which we could do. | |
162 | ||
163 | TODO: We could handle unions, but to be honest, it's probably not | |
164 | worth the pain or slowdown. */ | |
165 | ||
c58936b6 | 166 | static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map))) |
21392f19 DB |
167 | htab_t heapvar_for_stmt; |
168 | ||
910fdc79 | 169 | static bool use_field_sensitive = true; |
4ee00913 | 170 | static int in_ipa_mode = 0; |
3e5937d7 DB |
171 | |
172 | /* Used for predecessor bitmaps. */ | |
4ee00913 | 173 | static bitmap_obstack predbitmap_obstack; |
3e5937d7 DB |
174 | |
175 | /* Used for points-to sets. */ | |
176 | static bitmap_obstack pta_obstack; | |
177 | ||
178 | /* Used for oldsolution members of variables. */ | |
179 | static bitmap_obstack oldpta_obstack; | |
180 | ||
181 | /* Used for per-solver-iteration bitmaps. */ | |
4ee00913 DB |
182 | static bitmap_obstack iteration_obstack; |
183 | ||
910fdc79 | 184 | static unsigned int create_variable_info_for (tree, const char *); |
3e5937d7 DB |
185 | typedef struct constraint_graph *constraint_graph_t; |
186 | static void unify_nodes (constraint_graph_t, unsigned int, unsigned int, bool); | |
910fdc79 | 187 | |
910fdc79 | 188 | DEF_VEC_P(constraint_t); |
b5efa470 | 189 | DEF_VEC_ALLOC_P(constraint_t,heap); |
910fdc79 | 190 | |
4ee00913 DB |
191 | #define EXECUTE_IF_IN_NONNULL_BITMAP(a, b, c, d) \ |
192 | if (a) \ | |
193 | EXECUTE_IF_SET_IN_BITMAP (a, b, c, d) | |
194 | ||
910fdc79 DB |
195 | static struct constraint_stats |
196 | { | |
197 | unsigned int total_vars; | |
3e5937d7 | 198 | unsigned int nonpointer_vars; |
910fdc79 DB |
199 | unsigned int unified_vars_static; |
200 | unsigned int unified_vars_dynamic; | |
201 | unsigned int iterations; | |
4ee00913 | 202 | unsigned int num_edges; |
3e5937d7 DB |
203 | unsigned int num_implicit_edges; |
204 | unsigned int points_to_sets_created; | |
910fdc79 DB |
205 | } stats; |
206 | ||
207 | struct variable_info | |
208 | { | |
209 | /* ID of this variable */ | |
210 | unsigned int id; | |
211 | ||
212 | /* Name of this variable */ | |
213 | const char *name; | |
214 | ||
215 | /* Tree that this variable is associated with. */ | |
216 | tree decl; | |
217 | ||
218 | /* Offset of this variable, in bits, from the base variable */ | |
c58936b6 | 219 | unsigned HOST_WIDE_INT offset; |
910fdc79 DB |
220 | |
221 | /* Size of the variable, in bits. */ | |
222 | unsigned HOST_WIDE_INT size; | |
223 | ||
224 | /* Full size of the base variable, in bits. */ | |
225 | unsigned HOST_WIDE_INT fullsize; | |
226 | ||
227 | /* A link to the variable for the next field in this structure. */ | |
228 | struct variable_info *next; | |
229 | ||
21392f19 DB |
230 | /* True if the variable is directly the target of a dereference. |
231 | This is used to track which variables are *actually* dereferenced | |
3e5937d7 | 232 | so we can prune their points to listed. */ |
21392f19 | 233 | unsigned int directly_dereferenced:1; |
910fdc79 DB |
234 | |
235 | /* True if this is a variable created by the constraint analysis, such as | |
236 | heap variables and constraints we had to break up. */ | |
237 | unsigned int is_artificial_var:1; | |
c58936b6 | 238 | |
13c2c08b DB |
239 | /* True if this is a special variable whose solution set should not be |
240 | changed. */ | |
241 | unsigned int is_special_var:1; | |
910fdc79 DB |
242 | |
243 | /* True for variables whose size is not known or variable. */ | |
c58936b6 | 244 | unsigned int is_unknown_size_var:1; |
910fdc79 | 245 | |
58b82d2b DB |
246 | /* True for variables that have unions somewhere in them. */ |
247 | unsigned int has_union:1; | |
248 | ||
e8ca4159 DN |
249 | /* True if this is a heap variable. */ |
250 | unsigned int is_heap_var:1; | |
251 | ||
058dcc25 ILT |
252 | /* True if we may not use TBAA to prune references to this |
253 | variable. This is used for C++ placement new. */ | |
254 | unsigned int no_tbaa_pruning : 1; | |
255 | ||
910fdc79 DB |
256 | /* Points-to set for this variable. */ |
257 | bitmap solution; | |
258 | ||
3e5937d7 DB |
259 | /* Old points-to set for this variable. */ |
260 | bitmap oldsolution; | |
261 | ||
3e5937d7 DB |
262 | /* Variable id this was collapsed to due to type unsafety. This |
263 | should be unused completely after build_succ_graph, or something | |
264 | is broken. */ | |
03190594 | 265 | struct variable_info *collapsed_to; |
910fdc79 DB |
266 | }; |
267 | typedef struct variable_info *varinfo_t; | |
268 | ||
269 | static varinfo_t first_vi_for_offset (varinfo_t, unsigned HOST_WIDE_INT); | |
270 | ||
271 | /* Pool of variable info structures. */ | |
272 | static alloc_pool variable_info_pool; | |
273 | ||
274 | DEF_VEC_P(varinfo_t); | |
275 | ||
b5efa470 | 276 | DEF_VEC_ALLOC_P(varinfo_t, heap); |
910fdc79 | 277 | |
38635499 DN |
278 | /* Table of variable info structures for constraint variables. |
279 | Indexed directly by variable info id. */ | |
b5efa470 | 280 | static VEC(varinfo_t,heap) *varmap; |
13c2c08b DB |
281 | |
282 | /* Return the varmap element N */ | |
283 | ||
284 | static inline varinfo_t | |
03190594 | 285 | get_varinfo (unsigned int n) |
13c2c08b | 286 | { |
62e5bf5d | 287 | return VEC_index (varinfo_t, varmap, n); |
13c2c08b | 288 | } |
910fdc79 | 289 | |
03190594 DB |
290 | /* Return the varmap element N, following the collapsed_to link. */ |
291 | ||
292 | static inline varinfo_t | |
293 | get_varinfo_fc (unsigned int n) | |
294 | { | |
62e5bf5d | 295 | varinfo_t v = VEC_index (varinfo_t, varmap, n); |
03190594 DB |
296 | |
297 | if (v->collapsed_to) | |
298 | return v->collapsed_to; | |
299 | return v; | |
300 | } | |
301 | ||
910fdc79 DB |
302 | /* Variable that represents the unknown pointer. */ |
303 | static varinfo_t var_anything; | |
304 | static tree anything_tree; | |
305 | static unsigned int anything_id; | |
306 | ||
307 | /* Variable that represents the NULL pointer. */ | |
308 | static varinfo_t var_nothing; | |
309 | static tree nothing_tree; | |
310 | static unsigned int nothing_id; | |
311 | ||
312 | /* Variable that represents read only memory. */ | |
313 | static varinfo_t var_readonly; | |
314 | static tree readonly_tree; | |
315 | static unsigned int readonly_id; | |
316 | ||
317 | /* Variable that represents integers. This is used for when people do things | |
318 | like &0->a.b. */ | |
319 | static varinfo_t var_integer; | |
320 | static tree integer_tree; | |
321 | static unsigned int integer_id; | |
322 | ||
f5d7990b | 323 | /* Lookup a heap var for FROM, and return it if we find one. */ |
c900f6aa | 324 | |
c58936b6 | 325 | static tree |
f5d7990b | 326 | heapvar_lookup (tree from) |
c900f6aa DB |
327 | { |
328 | struct tree_map *h, in; | |
fc8600f9 | 329 | in.base.from = from; |
c900f6aa | 330 | |
c22940cd TN |
331 | h = (struct tree_map *) htab_find_with_hash (heapvar_for_stmt, &in, |
332 | htab_hash_pointer (from)); | |
c900f6aa DB |
333 | if (h) |
334 | return h->to; | |
335 | return NULL_TREE; | |
336 | } | |
337 | ||
338 | /* Insert a mapping FROM->TO in the heap var for statement | |
339 | hashtable. */ | |
340 | ||
341 | static void | |
342 | heapvar_insert (tree from, tree to) | |
343 | { | |
344 | struct tree_map *h; | |
345 | void **loc; | |
346 | ||
c22940cd | 347 | h = GGC_NEW (struct tree_map); |
c900f6aa | 348 | h->hash = htab_hash_pointer (from); |
fc8600f9 | 349 | h->base.from = from; |
c900f6aa DB |
350 | h->to = to; |
351 | loc = htab_find_slot_with_hash (heapvar_for_stmt, h, h->hash, INSERT); | |
352 | *(struct tree_map **) loc = h; | |
21392f19 | 353 | } |
c900f6aa | 354 | |
910fdc79 DB |
355 | /* Return a new variable info structure consisting for a variable |
356 | named NAME, and using constraint graph node NODE. */ | |
357 | ||
358 | static varinfo_t | |
3e5937d7 | 359 | new_var_info (tree t, unsigned int id, const char *name) |
910fdc79 | 360 | { |
c22940cd | 361 | varinfo_t ret = (varinfo_t) pool_alloc (variable_info_pool); |
058dcc25 | 362 | tree var; |
910fdc79 DB |
363 | |
364 | ret->id = id; | |
365 | ret->name = name; | |
366 | ret->decl = t; | |
21392f19 | 367 | ret->directly_dereferenced = false; |
910fdc79 | 368 | ret->is_artificial_var = false; |
e8ca4159 | 369 | ret->is_heap_var = false; |
13c2c08b | 370 | ret->is_special_var = false; |
910fdc79 | 371 | ret->is_unknown_size_var = false; |
13c2c08b | 372 | ret->has_union = false; |
058dcc25 ILT |
373 | var = t; |
374 | if (TREE_CODE (var) == SSA_NAME) | |
375 | var = SSA_NAME_VAR (var); | |
376 | ret->no_tbaa_pruning = (DECL_P (var) | |
377 | && POINTER_TYPE_P (TREE_TYPE (var)) | |
378 | && DECL_NO_TBAA_P (var)); | |
3e5937d7 DB |
379 | ret->solution = BITMAP_ALLOC (&pta_obstack); |
380 | ret->oldsolution = BITMAP_ALLOC (&oldpta_obstack); | |
910fdc79 | 381 | ret->next = NULL; |
03190594 | 382 | ret->collapsed_to = NULL; |
910fdc79 DB |
383 | return ret; |
384 | } | |
385 | ||
3e5937d7 | 386 | typedef enum {SCALAR, DEREF, ADDRESSOF} constraint_expr_type; |
910fdc79 DB |
387 | |
388 | /* An expression that appears in a constraint. */ | |
389 | ||
c58936b6 | 390 | struct constraint_expr |
910fdc79 DB |
391 | { |
392 | /* Constraint type. */ | |
393 | constraint_expr_type type; | |
394 | ||
395 | /* Variable we are referring to in the constraint. */ | |
396 | unsigned int var; | |
397 | ||
398 | /* Offset, in bits, of this constraint from the beginning of | |
399 | variables it ends up referring to. | |
400 | ||
401 | IOW, in a deref constraint, we would deref, get the result set, | |
402 | then add OFFSET to each member. */ | |
403 | unsigned HOST_WIDE_INT offset; | |
404 | }; | |
405 | ||
4ee00913 DB |
406 | typedef struct constraint_expr ce_s; |
407 | DEF_VEC_O(ce_s); | |
408 | DEF_VEC_ALLOC_O(ce_s, heap); | |
1d85354c | 409 | static void get_constraint_for (tree, VEC(ce_s, heap) **); |
4ee00913 | 410 | static void do_deref (VEC (ce_s, heap) **); |
910fdc79 DB |
411 | |
412 | /* Our set constraints are made up of two constraint expressions, one | |
c58936b6 | 413 | LHS, and one RHS. |
910fdc79 DB |
414 | |
415 | As described in the introduction, our set constraints each represent an | |
416 | operation between set valued variables. | |
417 | */ | |
418 | struct constraint | |
419 | { | |
420 | struct constraint_expr lhs; | |
421 | struct constraint_expr rhs; | |
422 | }; | |
423 | ||
424 | /* List of constraints that we use to build the constraint graph from. */ | |
425 | ||
b5efa470 | 426 | static VEC(constraint_t,heap) *constraints; |
910fdc79 DB |
427 | static alloc_pool constraint_pool; |
428 | ||
910fdc79 | 429 | |
3e5937d7 DB |
430 | DEF_VEC_I(int); |
431 | DEF_VEC_ALLOC_I(int, heap); | |
432 | ||
57250223 DB |
433 | /* The constraint graph is represented as an array of bitmaps |
434 | containing successor nodes. */ | |
910fdc79 DB |
435 | |
436 | struct constraint_graph | |
437 | { | |
3e5937d7 DB |
438 | /* Size of this graph, which may be different than the number of |
439 | nodes in the variable map. */ | |
440 | unsigned int size; | |
441 | ||
442 | /* Explicit successors of each node. */ | |
57250223 | 443 | bitmap *succs; |
3e5937d7 DB |
444 | |
445 | /* Implicit predecessors of each node (Used for variable | |
446 | substitution). */ | |
447 | bitmap *implicit_preds; | |
448 | ||
449 | /* Explicit predecessors of each node (Used for variable substitution). */ | |
57250223 | 450 | bitmap *preds; |
910fdc79 | 451 | |
3e5937d7 DB |
452 | /* Indirect cycle representatives, or -1 if the node has no indirect |
453 | cycles. */ | |
454 | int *indirect_cycles; | |
455 | ||
456 | /* Representative node for a node. rep[a] == a unless the node has | |
457 | been unified. */ | |
458 | unsigned int *rep; | |
459 | ||
7b765bed | 460 | /* Equivalence class representative for a label. This is used for |
3e5937d7 DB |
461 | variable substitution. */ |
462 | int *eq_rep; | |
463 | ||
aa46c8a3 DB |
464 | /* Pointer equivalence label for a node. All nodes with the same |
465 | pointer equivalence label can be unified together at some point | |
466 | (either during constraint optimization or after the constraint | |
467 | graph is built). */ | |
7b765bed DB |
468 | unsigned int *pe; |
469 | ||
470 | /* Pointer equivalence representative for a label. This is used to | |
471 | handle nodes that are pointer equivalent but not location | |
472 | equivalent. We can unite these once the addressof constraints | |
473 | are transformed into initial points-to sets. */ | |
474 | int *pe_rep; | |
475 | ||
476 | /* Pointer equivalence label for each node, used during variable | |
477 | substitution. */ | |
478 | unsigned int *pointer_label; | |
479 | ||
480 | /* Location equivalence label for each node, used during location | |
481 | equivalence finding. */ | |
482 | unsigned int *loc_label; | |
483 | ||
484 | /* Pointed-by set for each node, used during location equivalence | |
485 | finding. This is pointed-by rather than pointed-to, because it | |
486 | is constructed using the predecessor graph. */ | |
487 | bitmap *pointed_by; | |
488 | ||
489 | /* Points to sets for pointer equivalence. This is *not* the actual | |
490 | points-to sets for nodes. */ | |
491 | bitmap *points_to; | |
3e5937d7 DB |
492 | |
493 | /* Bitmap of nodes where the bit is set if the node is a direct | |
494 | node. Used for variable substitution. */ | |
495 | sbitmap direct_nodes; | |
496 | ||
7b765bed DB |
497 | /* Bitmap of nodes where the bit is set if the node is address |
498 | taken. Used for variable substitution. */ | |
499 | bitmap address_taken; | |
500 | ||
501 | /* True if points_to bitmap for this node is stored in the hash | |
502 | table. */ | |
503 | sbitmap pt_used; | |
504 | ||
505 | /* Number of incoming edges remaining to be processed by pointer | |
506 | equivalence. | |
507 | Used for variable substitution. */ | |
508 | unsigned int *number_incoming; | |
509 | ||
510 | ||
3e5937d7 DB |
511 | /* Vector of complex constraints for each graph node. Complex |
512 | constraints are those involving dereferences or offsets that are | |
513 | not 0. */ | |
514 | VEC(constraint_t,heap) **complex; | |
515 | }; | |
910fdc79 DB |
516 | |
517 | static constraint_graph_t graph; | |
518 | ||
3e5937d7 DB |
519 | /* During variable substitution and the offline version of indirect |
520 | cycle finding, we create nodes to represent dereferences and | |
521 | address taken constraints. These represent where these start and | |
522 | end. */ | |
523 | #define FIRST_REF_NODE (VEC_length (varinfo_t, varmap)) | |
524 | #define LAST_REF_NODE (FIRST_REF_NODE + (FIRST_REF_NODE - 1)) | |
3e5937d7 DB |
525 | |
526 | /* Return the representative node for NODE, if NODE has been unioned | |
527 | with another NODE. | |
528 | This function performs path compression along the way to finding | |
529 | the representative. */ | |
530 | ||
531 | static unsigned int | |
532 | find (unsigned int node) | |
533 | { | |
534 | gcc_assert (node < graph->size); | |
535 | if (graph->rep[node] != node) | |
536 | return graph->rep[node] = find (graph->rep[node]); | |
537 | return node; | |
538 | } | |
539 | ||
540 | /* Union the TO and FROM nodes to the TO nodes. | |
541 | Note that at some point in the future, we may want to do | |
542 | union-by-rank, in which case we are going to have to return the | |
543 | node we unified to. */ | |
544 | ||
545 | static bool | |
546 | unite (unsigned int to, unsigned int from) | |
547 | { | |
548 | gcc_assert (to < graph->size && from < graph->size); | |
549 | if (to != from && graph->rep[from] != to) | |
550 | { | |
551 | graph->rep[from] = to; | |
552 | return true; | |
553 | } | |
554 | return false; | |
555 | } | |
556 | ||
910fdc79 DB |
557 | /* Create a new constraint consisting of LHS and RHS expressions. */ |
558 | ||
c58936b6 | 559 | static constraint_t |
910fdc79 DB |
560 | new_constraint (const struct constraint_expr lhs, |
561 | const struct constraint_expr rhs) | |
562 | { | |
c22940cd | 563 | constraint_t ret = (constraint_t) pool_alloc (constraint_pool); |
910fdc79 DB |
564 | ret->lhs = lhs; |
565 | ret->rhs = rhs; | |
566 | return ret; | |
567 | } | |
568 | ||
569 | /* Print out constraint C to FILE. */ | |
570 | ||
571 | void | |
572 | dump_constraint (FILE *file, constraint_t c) | |
573 | { | |
574 | if (c->lhs.type == ADDRESSOF) | |
575 | fprintf (file, "&"); | |
576 | else if (c->lhs.type == DEREF) | |
c58936b6 | 577 | fprintf (file, "*"); |
03190594 | 578 | fprintf (file, "%s", get_varinfo_fc (c->lhs.var)->name); |
910fdc79 DB |
579 | if (c->lhs.offset != 0) |
580 | fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->lhs.offset); | |
581 | fprintf (file, " = "); | |
582 | if (c->rhs.type == ADDRESSOF) | |
583 | fprintf (file, "&"); | |
584 | else if (c->rhs.type == DEREF) | |
585 | fprintf (file, "*"); | |
03190594 | 586 | fprintf (file, "%s", get_varinfo_fc (c->rhs.var)->name); |
910fdc79 DB |
587 | if (c->rhs.offset != 0) |
588 | fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->rhs.offset); | |
589 | fprintf (file, "\n"); | |
590 | } | |
591 | ||
592 | /* Print out constraint C to stderr. */ | |
593 | ||
594 | void | |
595 | debug_constraint (constraint_t c) | |
596 | { | |
597 | dump_constraint (stderr, c); | |
598 | } | |
599 | ||
600 | /* Print out all constraints to FILE */ | |
601 | ||
602 | void | |
603 | dump_constraints (FILE *file) | |
604 | { | |
605 | int i; | |
606 | constraint_t c; | |
607 | for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++) | |
608 | dump_constraint (file, c); | |
609 | } | |
610 | ||
611 | /* Print out all constraints to stderr. */ | |
612 | ||
613 | void | |
614 | debug_constraints (void) | |
615 | { | |
616 | dump_constraints (stderr); | |
617 | } | |
618 | ||
c58936b6 | 619 | /* SOLVER FUNCTIONS |
910fdc79 DB |
620 | |
621 | The solver is a simple worklist solver, that works on the following | |
622 | algorithm: | |
c58936b6 | 623 | |
3e5937d7 DB |
624 | sbitmap changed_nodes = all zeroes; |
625 | changed_count = 0; | |
626 | For each node that is not already collapsed: | |
627 | changed_count++; | |
628 | set bit in changed nodes | |
910fdc79 | 629 | |
910fdc79 DB |
630 | while (changed_count > 0) |
631 | { | |
632 | compute topological ordering for constraint graph | |
c58936b6 | 633 | |
910fdc79 DB |
634 | find and collapse cycles in the constraint graph (updating |
635 | changed if necessary) | |
c58936b6 | 636 | |
910fdc79 DB |
637 | for each node (n) in the graph in topological order: |
638 | changed_count--; | |
639 | ||
640 | Process each complex constraint associated with the node, | |
641 | updating changed if necessary. | |
642 | ||
643 | For each outgoing edge from n, propagate the solution from n to | |
644 | the destination of the edge, updating changed as necessary. | |
645 | ||
646 | } */ | |
647 | ||
648 | /* Return true if two constraint expressions A and B are equal. */ | |
649 | ||
650 | static bool | |
651 | constraint_expr_equal (struct constraint_expr a, struct constraint_expr b) | |
652 | { | |
4ee00913 | 653 | return a.type == b.type && a.var == b.var && a.offset == b.offset; |
910fdc79 DB |
654 | } |
655 | ||
656 | /* Return true if constraint expression A is less than constraint expression | |
657 | B. This is just arbitrary, but consistent, in order to give them an | |
658 | ordering. */ | |
659 | ||
660 | static bool | |
661 | constraint_expr_less (struct constraint_expr a, struct constraint_expr b) | |
662 | { | |
663 | if (a.type == b.type) | |
664 | { | |
665 | if (a.var == b.var) | |
666 | return a.offset < b.offset; | |
667 | else | |
668 | return a.var < b.var; | |
669 | } | |
670 | else | |
671 | return a.type < b.type; | |
672 | } | |
673 | ||
674 | /* Return true if constraint A is less than constraint B. This is just | |
675 | arbitrary, but consistent, in order to give them an ordering. */ | |
676 | ||
677 | static bool | |
678 | constraint_less (const constraint_t a, const constraint_t b) | |
679 | { | |
680 | if (constraint_expr_less (a->lhs, b->lhs)) | |
681 | return true; | |
682 | else if (constraint_expr_less (b->lhs, a->lhs)) | |
683 | return false; | |
684 | else | |
685 | return constraint_expr_less (a->rhs, b->rhs); | |
686 | } | |
687 | ||
688 | /* Return true if two constraints A and B are equal. */ | |
c58936b6 | 689 | |
910fdc79 DB |
690 | static bool |
691 | constraint_equal (struct constraint a, struct constraint b) | |
692 | { | |
c58936b6 | 693 | return constraint_expr_equal (a.lhs, b.lhs) |
910fdc79 DB |
694 | && constraint_expr_equal (a.rhs, b.rhs); |
695 | } | |
696 | ||
697 | ||
698 | /* Find a constraint LOOKFOR in the sorted constraint vector VEC */ | |
699 | ||
700 | static constraint_t | |
b5efa470 | 701 | constraint_vec_find (VEC(constraint_t,heap) *vec, |
910fdc79 DB |
702 | struct constraint lookfor) |
703 | { | |
c58936b6 | 704 | unsigned int place; |
910fdc79 DB |
705 | constraint_t found; |
706 | ||
707 | if (vec == NULL) | |
708 | return NULL; | |
709 | ||
710 | place = VEC_lower_bound (constraint_t, vec, &lookfor, constraint_less); | |
711 | if (place >= VEC_length (constraint_t, vec)) | |
712 | return NULL; | |
713 | found = VEC_index (constraint_t, vec, place); | |
714 | if (!constraint_equal (*found, lookfor)) | |
715 | return NULL; | |
716 | return found; | |
717 | } | |
718 | ||
719 | /* Union two constraint vectors, TO and FROM. Put the result in TO. */ | |
720 | ||
721 | static void | |
b5efa470 DB |
722 | constraint_set_union (VEC(constraint_t,heap) **to, |
723 | VEC(constraint_t,heap) **from) | |
910fdc79 DB |
724 | { |
725 | int i; | |
726 | constraint_t c; | |
727 | ||
728 | for (i = 0; VEC_iterate (constraint_t, *from, i, c); i++) | |
729 | { | |
730 | if (constraint_vec_find (*to, *c) == NULL) | |
731 | { | |
732 | unsigned int place = VEC_lower_bound (constraint_t, *to, c, | |
733 | constraint_less); | |
b5efa470 | 734 | VEC_safe_insert (constraint_t, heap, *to, place, c); |
910fdc79 DB |
735 | } |
736 | } | |
737 | } | |
738 | ||
739 | /* Take a solution set SET, add OFFSET to each member of the set, and | |
740 | overwrite SET with the result when done. */ | |
741 | ||
742 | static void | |
743 | solution_set_add (bitmap set, unsigned HOST_WIDE_INT offset) | |
744 | { | |
745 | bitmap result = BITMAP_ALLOC (&iteration_obstack); | |
746 | unsigned int i; | |
747 | bitmap_iterator bi; | |
748 | ||
749 | EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi) | |
750 | { | |
751 | /* If this is a properly sized variable, only add offset if it's | |
752 | less than end. Otherwise, it is globbed to a single | |
753 | variable. */ | |
c58936b6 | 754 | |
910fdc79 DB |
755 | if ((get_varinfo (i)->offset + offset) < get_varinfo (i)->fullsize) |
756 | { | |
757 | unsigned HOST_WIDE_INT fieldoffset = get_varinfo (i)->offset + offset; | |
758 | varinfo_t v = first_vi_for_offset (get_varinfo (i), fieldoffset); | |
8971094d DB |
759 | if (!v) |
760 | continue; | |
910fdc79 DB |
761 | bitmap_set_bit (result, v->id); |
762 | } | |
c58936b6 | 763 | else if (get_varinfo (i)->is_artificial_var |
13c2c08b | 764 | || get_varinfo (i)->has_union |
910fdc79 DB |
765 | || get_varinfo (i)->is_unknown_size_var) |
766 | { | |
767 | bitmap_set_bit (result, i); | |
768 | } | |
769 | } | |
c58936b6 DB |
770 | |
771 | bitmap_copy (set, result); | |
910fdc79 DB |
772 | BITMAP_FREE (result); |
773 | } | |
774 | ||
775 | /* Union solution sets TO and FROM, and add INC to each member of FROM in the | |
776 | process. */ | |
777 | ||
778 | static bool | |
779 | set_union_with_increment (bitmap to, bitmap from, unsigned HOST_WIDE_INT inc) | |
780 | { | |
781 | if (inc == 0) | |
782 | return bitmap_ior_into (to, from); | |
783 | else | |
784 | { | |
785 | bitmap tmp; | |
786 | bool res; | |
787 | ||
788 | tmp = BITMAP_ALLOC (&iteration_obstack); | |
789 | bitmap_copy (tmp, from); | |
790 | solution_set_add (tmp, inc); | |
791 | res = bitmap_ior_into (to, tmp); | |
792 | BITMAP_FREE (tmp); | |
793 | return res; | |
794 | } | |
795 | } | |
796 | ||
3e5937d7 DB |
797 | /* Insert constraint C into the list of complex constraints for graph |
798 | node VAR. */ | |
910fdc79 DB |
799 | |
800 | static void | |
3e5937d7 DB |
801 | insert_into_complex (constraint_graph_t graph, |
802 | unsigned int var, constraint_t c) | |
910fdc79 | 803 | { |
3e5937d7 DB |
804 | VEC (constraint_t, heap) *complex = graph->complex[var]; |
805 | unsigned int place = VEC_lower_bound (constraint_t, complex, c, | |
910fdc79 | 806 | constraint_less); |
3e5937d7 DB |
807 | |
808 | /* Only insert constraints that do not already exist. */ | |
809 | if (place >= VEC_length (constraint_t, complex) | |
810 | || !constraint_equal (*c, *VEC_index (constraint_t, complex, place))) | |
811 | VEC_safe_insert (constraint_t, heap, graph->complex[var], place, c); | |
910fdc79 DB |
812 | } |
813 | ||
814 | ||
910fdc79 DB |
815 | /* Condense two variable nodes into a single variable node, by moving |
816 | all associated info from SRC to TO. */ | |
817 | ||
c58936b6 | 818 | static void |
3e5937d7 DB |
819 | merge_node_constraints (constraint_graph_t graph, unsigned int to, |
820 | unsigned int from) | |
910fdc79 | 821 | { |
910fdc79 DB |
822 | unsigned int i; |
823 | constraint_t c; | |
c58936b6 | 824 | |
3e5937d7 | 825 | gcc_assert (find (from) == to); |
c58936b6 | 826 | |
910fdc79 | 827 | /* Move all complex constraints from src node into to node */ |
3e5937d7 | 828 | for (i = 0; VEC_iterate (constraint_t, graph->complex[from], i, c); i++) |
910fdc79 DB |
829 | { |
830 | /* In complex constraints for node src, we may have either | |
3e5937d7 DB |
831 | a = *src, and *src = a, or an offseted constraint which are |
832 | always added to the rhs node's constraints. */ | |
c58936b6 | 833 | |
910fdc79 DB |
834 | if (c->rhs.type == DEREF) |
835 | c->rhs.var = to; | |
3e5937d7 | 836 | else if (c->lhs.type == DEREF) |
910fdc79 | 837 | c->lhs.var = to; |
3e5937d7 DB |
838 | else |
839 | c->rhs.var = to; | |
910fdc79 | 840 | } |
3e5937d7 DB |
841 | constraint_set_union (&graph->complex[to], &graph->complex[from]); |
842 | VEC_free (constraint_t, heap, graph->complex[from]); | |
843 | graph->complex[from] = NULL; | |
910fdc79 DB |
844 | } |
845 | ||
910fdc79 DB |
846 | |
847 | /* Remove edges involving NODE from GRAPH. */ | |
848 | ||
849 | static void | |
850 | clear_edges_for_node (constraint_graph_t graph, unsigned int node) | |
851 | { | |
57250223 | 852 | if (graph->succs[node]) |
3e5937d7 | 853 | BITMAP_FREE (graph->succs[node]); |
f71ef09d DB |
854 | } |
855 | ||
910fdc79 DB |
856 | /* Merge GRAPH nodes FROM and TO into node TO. */ |
857 | ||
858 | static void | |
c58936b6 | 859 | merge_graph_nodes (constraint_graph_t graph, unsigned int to, |
910fdc79 DB |
860 | unsigned int from) |
861 | { | |
3e5937d7 | 862 | if (graph->indirect_cycles[from] != -1) |
4ee00913 | 863 | { |
3e5937d7 DB |
864 | /* If we have indirect cycles with the from node, and we have |
865 | none on the to node, the to node has indirect cycles from the | |
866 | from node now that they are unified. | |
867 | If indirect cycles exist on both, unify the nodes that they | |
868 | are in a cycle with, since we know they are in a cycle with | |
869 | each other. */ | |
870 | if (graph->indirect_cycles[to] == -1) | |
7b765bed | 871 | graph->indirect_cycles[to] = graph->indirect_cycles[from]; |
4ee00913 | 872 | } |
910fdc79 | 873 | |
57250223 DB |
874 | /* Merge all the successor edges. */ |
875 | if (graph->succs[from]) | |
4ee00913 | 876 | { |
57250223 | 877 | if (!graph->succs[to]) |
3e5937d7 | 878 | graph->succs[to] = BITMAP_ALLOC (&pta_obstack); |
c58936b6 | 879 | bitmap_ior_into (graph->succs[to], |
57250223 | 880 | graph->succs[from]); |
4ee00913 | 881 | } |
4ee00913 | 882 | |
910fdc79 DB |
883 | clear_edges_for_node (graph, from); |
884 | } | |
885 | ||
3e5937d7 DB |
886 | |
887 | /* Add an indirect graph edge to GRAPH, going from TO to FROM if | |
888 | it doesn't exist in the graph already. */ | |
889 | ||
890 | static void | |
891 | add_implicit_graph_edge (constraint_graph_t graph, unsigned int to, | |
892 | unsigned int from) | |
893 | { | |
894 | if (to == from) | |
895 | return; | |
896 | ||
897 | if (!graph->implicit_preds[to]) | |
898 | graph->implicit_preds[to] = BITMAP_ALLOC (&predbitmap_obstack); | |
899 | ||
900 | if (!bitmap_bit_p (graph->implicit_preds[to], from)) | |
901 | { | |
902 | stats.num_implicit_edges++; | |
903 | bitmap_set_bit (graph->implicit_preds[to], from); | |
904 | } | |
905 | } | |
906 | ||
907 | /* Add a predecessor graph edge to GRAPH, going from TO to FROM if | |
908 | it doesn't exist in the graph already. | |
909 | Return false if the edge already existed, true otherwise. */ | |
910 | ||
911 | static void | |
912 | add_pred_graph_edge (constraint_graph_t graph, unsigned int to, | |
913 | unsigned int from) | |
914 | { | |
915 | if (!graph->preds[to]) | |
916 | graph->preds[to] = BITMAP_ALLOC (&predbitmap_obstack); | |
917 | if (!bitmap_bit_p (graph->preds[to], from)) | |
918 | bitmap_set_bit (graph->preds[to], from); | |
919 | } | |
920 | ||
921 | /* Add a graph edge to GRAPH, going from FROM to TO if | |
910fdc79 DB |
922 | it doesn't exist in the graph already. |
923 | Return false if the edge already existed, true otherwise. */ | |
924 | ||
925 | static bool | |
57250223 DB |
926 | add_graph_edge (constraint_graph_t graph, unsigned int to, |
927 | unsigned int from) | |
910fdc79 | 928 | { |
57250223 | 929 | if (to == from) |
910fdc79 DB |
930 | { |
931 | return false; | |
932 | } | |
933 | else | |
934 | { | |
4ee00913 | 935 | bool r = false; |
c58936b6 | 936 | |
57250223 | 937 | if (!graph->succs[from]) |
3e5937d7 | 938 | graph->succs[from] = BITMAP_ALLOC (&pta_obstack); |
57250223 | 939 | if (!bitmap_bit_p (graph->succs[from], to)) |
f71ef09d | 940 | { |
57250223 | 941 | r = true; |
3e5937d7 DB |
942 | if (to < FIRST_REF_NODE && from < FIRST_REF_NODE) |
943 | stats.num_edges++; | |
57250223 | 944 | bitmap_set_bit (graph->succs[from], to); |
f71ef09d | 945 | } |
910fdc79 DB |
946 | return r; |
947 | } | |
948 | } | |
949 | ||
950 | ||
4ee00913 | 951 | /* Return true if {DEST.SRC} is an existing graph edge in GRAPH. */ |
910fdc79 DB |
952 | |
953 | static bool | |
c58936b6 | 954 | valid_graph_edge (constraint_graph_t graph, unsigned int src, |
4ee00913 | 955 | unsigned int dest) |
910fdc79 | 956 | { |
c58936b6 | 957 | return (graph->succs[dest] |
57250223 | 958 | && bitmap_bit_p (graph->succs[dest], src)); |
4ee00913 DB |
959 | } |
960 | ||
7b765bed DB |
961 | /* Initialize the constraint graph structure to contain SIZE nodes. */ |
962 | ||
963 | static void | |
964 | init_graph (unsigned int size) | |
965 | { | |
966 | unsigned int j; | |
967 | ||
968 | graph = XCNEW (struct constraint_graph); | |
969 | graph->size = size; | |
970 | graph->succs = XCNEWVEC (bitmap, graph->size); | |
971 | graph->indirect_cycles = XNEWVEC (int, graph->size); | |
972 | graph->rep = XNEWVEC (unsigned int, graph->size); | |
973 | graph->complex = XCNEWVEC (VEC(constraint_t, heap) *, size); | |
aa46c8a3 | 974 | graph->pe = XCNEWVEC (unsigned int, graph->size); |
7b765bed DB |
975 | graph->pe_rep = XNEWVEC (int, graph->size); |
976 | ||
977 | for (j = 0; j < graph->size; j++) | |
978 | { | |
979 | graph->rep[j] = j; | |
7b765bed DB |
980 | graph->pe_rep[j] = -1; |
981 | graph->indirect_cycles[j] = -1; | |
982 | } | |
983 | } | |
984 | ||
3e5937d7 | 985 | /* Build the constraint graph, adding only predecessor edges right now. */ |
910fdc79 DB |
986 | |
987 | static void | |
3e5937d7 | 988 | build_pred_graph (void) |
910fdc79 | 989 | { |
3e5937d7 | 990 | int i; |
910fdc79 | 991 | constraint_t c; |
3e5937d7 | 992 | unsigned int j; |
910fdc79 | 993 | |
3e5937d7 DB |
994 | graph->implicit_preds = XCNEWVEC (bitmap, graph->size); |
995 | graph->preds = XCNEWVEC (bitmap, graph->size); | |
7b765bed DB |
996 | graph->pointer_label = XCNEWVEC (unsigned int, graph->size); |
997 | graph->loc_label = XCNEWVEC (unsigned int, graph->size); | |
998 | graph->pointed_by = XCNEWVEC (bitmap, graph->size); | |
999 | graph->points_to = XCNEWVEC (bitmap, graph->size); | |
3e5937d7 | 1000 | graph->eq_rep = XNEWVEC (int, graph->size); |
3e5937d7 | 1001 | graph->direct_nodes = sbitmap_alloc (graph->size); |
7b765bed DB |
1002 | graph->pt_used = sbitmap_alloc (graph->size); |
1003 | graph->address_taken = BITMAP_ALLOC (&predbitmap_obstack); | |
1004 | graph->number_incoming = XCNEWVEC (unsigned int, graph->size); | |
3e5937d7 | 1005 | sbitmap_zero (graph->direct_nodes); |
7b765bed | 1006 | sbitmap_zero (graph->pt_used); |
3e5937d7 DB |
1007 | |
1008 | for (j = 0; j < FIRST_REF_NODE; j++) | |
1009 | { | |
1010 | if (!get_varinfo (j)->is_special_var) | |
1011 | SET_BIT (graph->direct_nodes, j); | |
1012 | } | |
1013 | ||
1014 | for (j = 0; j < graph->size; j++) | |
7b765bed | 1015 | graph->eq_rep[j] = -1; |
3e5937d7 DB |
1016 | |
1017 | for (j = 0; j < VEC_length (varinfo_t, varmap); j++) | |
1018 | graph->indirect_cycles[j] = -1; | |
e8ca4159 | 1019 | |
910fdc79 DB |
1020 | for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++) |
1021 | { | |
1022 | struct constraint_expr lhs = c->lhs; | |
1023 | struct constraint_expr rhs = c->rhs; | |
03190594 DB |
1024 | unsigned int lhsvar = get_varinfo_fc (lhs.var)->id; |
1025 | unsigned int rhsvar = get_varinfo_fc (rhs.var)->id; | |
1026 | ||
910fdc79 DB |
1027 | if (lhs.type == DEREF) |
1028 | { | |
3e5937d7 DB |
1029 | /* *x = y. */ |
1030 | if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR) | |
1031 | add_pred_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar); | |
910fdc79 DB |
1032 | } |
1033 | else if (rhs.type == DEREF) | |
1034 | { | |
3e5937d7 DB |
1035 | /* x = *y */ |
1036 | if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR) | |
1037 | add_pred_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar); | |
1038 | else | |
1039 | RESET_BIT (graph->direct_nodes, lhsvar); | |
910fdc79 | 1040 | } |
3e5937d7 | 1041 | else if (rhs.type == ADDRESSOF) |
910fdc79 DB |
1042 | { |
1043 | /* x = &y */ | |
7b765bed DB |
1044 | if (graph->points_to[lhsvar] == NULL) |
1045 | graph->points_to[lhsvar] = BITMAP_ALLOC (&predbitmap_obstack); | |
1046 | bitmap_set_bit (graph->points_to[lhsvar], rhsvar); | |
1047 | ||
1048 | if (graph->pointed_by[rhsvar] == NULL) | |
1049 | graph->pointed_by[rhsvar] = BITMAP_ALLOC (&predbitmap_obstack); | |
1050 | bitmap_set_bit (graph->pointed_by[rhsvar], lhsvar); | |
1051 | ||
3e5937d7 DB |
1052 | /* Implicitly, *x = y */ |
1053 | add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar); | |
1054 | ||
1055 | RESET_BIT (graph->direct_nodes, rhsvar); | |
7b765bed | 1056 | bitmap_set_bit (graph->address_taken, rhsvar); |
910fdc79 | 1057 | } |
3e5937d7 DB |
1058 | else if (lhsvar > anything_id |
1059 | && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0) | |
910fdc79 | 1060 | { |
3e5937d7 DB |
1061 | /* x = y */ |
1062 | add_pred_graph_edge (graph, lhsvar, rhsvar); | |
1063 | /* Implicitly, *x = *y */ | |
1064 | add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar, | |
1065 | FIRST_REF_NODE + rhsvar); | |
1066 | } | |
1067 | else if (lhs.offset != 0 || rhs.offset != 0) | |
1068 | { | |
1069 | if (rhs.offset != 0) | |
1070 | RESET_BIT (graph->direct_nodes, lhs.var); | |
7b765bed | 1071 | else if (lhs.offset != 0) |
3e5937d7 DB |
1072 | RESET_BIT (graph->direct_nodes, rhs.var); |
1073 | } | |
1074 | } | |
1075 | } | |
1076 | ||
1077 | /* Build the constraint graph, adding successor edges. */ | |
1078 | ||
1079 | static void | |
1080 | build_succ_graph (void) | |
1081 | { | |
1082 | int i; | |
1083 | constraint_t c; | |
1084 | ||
1085 | for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++) | |
1086 | { | |
1087 | struct constraint_expr lhs; | |
1088 | struct constraint_expr rhs; | |
1089 | unsigned int lhsvar; | |
1090 | unsigned int rhsvar; | |
1091 | ||
1092 | if (!c) | |
1093 | continue; | |
c58936b6 | 1094 | |
3e5937d7 DB |
1095 | lhs = c->lhs; |
1096 | rhs = c->rhs; | |
1097 | lhsvar = find (get_varinfo_fc (lhs.var)->id); | |
1098 | rhsvar = find (get_varinfo_fc (rhs.var)->id); | |
1099 | ||
1100 | if (lhs.type == DEREF) | |
1101 | { | |
1102 | if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR) | |
1103 | add_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar); | |
1104 | } | |
1105 | else if (rhs.type == DEREF) | |
1106 | { | |
1107 | if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR) | |
1108 | add_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar); | |
1109 | } | |
1110 | else if (rhs.type == ADDRESSOF) | |
1111 | { | |
1112 | /* x = &y */ | |
1113 | gcc_assert (find (get_varinfo_fc (rhs.var)->id) | |
1114 | == get_varinfo_fc (rhs.var)->id); | |
1115 | bitmap_set_bit (get_varinfo (lhsvar)->solution, rhsvar); | |
1116 | } | |
1117 | else if (lhsvar > anything_id | |
1118 | && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0) | |
1119 | { | |
1120 | add_graph_edge (graph, lhsvar, rhsvar); | |
910fdc79 DB |
1121 | } |
1122 | } | |
1123 | } | |
e8ca4159 DN |
1124 | |
1125 | ||
910fdc79 DB |
1126 | /* Changed variables on the last iteration. */ |
1127 | static unsigned int changed_count; | |
1128 | static sbitmap changed; | |
1129 | ||
740e80e8 FXC |
1130 | DEF_VEC_I(unsigned); |
1131 | DEF_VEC_ALLOC_I(unsigned,heap); | |
910fdc79 DB |
1132 | |
1133 | ||
1134 | /* Strongly Connected Component visitation info. */ | |
1135 | ||
1136 | struct scc_info | |
1137 | { | |
1138 | sbitmap visited; | |
7b765bed | 1139 | sbitmap deleted; |
3e5937d7 DB |
1140 | unsigned int *dfs; |
1141 | unsigned int *node_mapping; | |
910fdc79 | 1142 | int current_index; |
740e80e8 | 1143 | VEC(unsigned,heap) *scc_stack; |
910fdc79 DB |
1144 | }; |
1145 | ||
1146 | ||
1147 | /* Recursive routine to find strongly connected components in GRAPH. | |
1148 | SI is the SCC info to store the information in, and N is the id of current | |
1149 | graph node we are processing. | |
c58936b6 | 1150 | |
910fdc79 | 1151 | This is Tarjan's strongly connected component finding algorithm, as |
c58936b6 | 1152 | modified by Nuutila to keep only non-root nodes on the stack. |
910fdc79 DB |
1153 | The algorithm can be found in "On finding the strongly connected |
1154 | connected components in a directed graph" by Esko Nuutila and Eljas | |
1155 | Soisalon-Soininen, in Information Processing Letters volume 49, | |
1156 | number 1, pages 9-14. */ | |
1157 | ||
1158 | static void | |
1159 | scc_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n) | |
1160 | { | |
4ee00913 DB |
1161 | unsigned int i; |
1162 | bitmap_iterator bi; | |
3e5937d7 | 1163 | unsigned int my_dfs; |
910fdc79 | 1164 | |
910fdc79 | 1165 | SET_BIT (si->visited, n); |
3e5937d7 DB |
1166 | si->dfs[n] = si->current_index ++; |
1167 | my_dfs = si->dfs[n]; | |
c58936b6 | 1168 | |
910fdc79 | 1169 | /* Visit all the successors. */ |
57250223 | 1170 | EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[n], 0, i, bi) |
910fdc79 | 1171 | { |
3e5937d7 DB |
1172 | unsigned int w; |
1173 | ||
1174 | if (i > LAST_REF_NODE) | |
1175 | break; | |
1176 | ||
1177 | w = find (i); | |
7b765bed | 1178 | if (TEST_BIT (si->deleted, w)) |
3e5937d7 DB |
1179 | continue; |
1180 | ||
4ee00913 DB |
1181 | if (!TEST_BIT (si->visited, w)) |
1182 | scc_visit (graph, si, w); | |
3e5937d7 DB |
1183 | { |
1184 | unsigned int t = find (w); | |
1185 | unsigned int nnode = find (n); | |
62e5bf5d | 1186 | gcc_assert (nnode == n); |
3e5937d7 DB |
1187 | |
1188 | if (si->dfs[t] < si->dfs[nnode]) | |
1189 | si->dfs[n] = si->dfs[t]; | |
1190 | } | |
910fdc79 | 1191 | } |
c58936b6 | 1192 | |
910fdc79 | 1193 | /* See if any components have been identified. */ |
3e5937d7 | 1194 | if (si->dfs[n] == my_dfs) |
910fdc79 | 1195 | { |
3e5937d7 DB |
1196 | if (VEC_length (unsigned, si->scc_stack) > 0 |
1197 | && si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs) | |
910fdc79 | 1198 | { |
3e5937d7 DB |
1199 | bitmap scc = BITMAP_ALLOC (NULL); |
1200 | bool have_ref_node = n >= FIRST_REF_NODE; | |
1201 | unsigned int lowest_node; | |
1202 | bitmap_iterator bi; | |
910fdc79 | 1203 | |
3e5937d7 | 1204 | bitmap_set_bit (scc, n); |
910fdc79 | 1205 | |
3e5937d7 DB |
1206 | while (VEC_length (unsigned, si->scc_stack) != 0 |
1207 | && si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs) | |
1208 | { | |
1209 | unsigned int w = VEC_pop (unsigned, si->scc_stack); | |
910fdc79 | 1210 | |
3e5937d7 DB |
1211 | bitmap_set_bit (scc, w); |
1212 | if (w >= FIRST_REF_NODE) | |
1213 | have_ref_node = true; | |
1214 | } | |
4ee00913 | 1215 | |
3e5937d7 DB |
1216 | lowest_node = bitmap_first_set_bit (scc); |
1217 | gcc_assert (lowest_node < FIRST_REF_NODE); | |
7b765bed DB |
1218 | |
1219 | /* Collapse the SCC nodes into a single node, and mark the | |
1220 | indirect cycles. */ | |
3e5937d7 DB |
1221 | EXECUTE_IF_SET_IN_BITMAP (scc, 0, i, bi) |
1222 | { | |
1223 | if (i < FIRST_REF_NODE) | |
1224 | { | |
3e5937d7 DB |
1225 | if (unite (lowest_node, i)) |
1226 | unify_nodes (graph, lowest_node, i, false); | |
1227 | } | |
1228 | else | |
1229 | { | |
1230 | unite (lowest_node, i); | |
1231 | graph->indirect_cycles[i - FIRST_REF_NODE] = lowest_node; | |
1232 | } | |
1233 | } | |
4ee00913 | 1234 | } |
7b765bed | 1235 | SET_BIT (si->deleted, n); |
910fdc79 | 1236 | } |
3e5937d7 DB |
1237 | else |
1238 | VEC_safe_push (unsigned, heap, si->scc_stack, n); | |
910fdc79 DB |
1239 | } |
1240 | ||
3e5937d7 DB |
1241 | /* Unify node FROM into node TO, updating the changed count if |
1242 | necessary when UPDATE_CHANGED is true. */ | |
910fdc79 DB |
1243 | |
1244 | static void | |
3e5937d7 DB |
1245 | unify_nodes (constraint_graph_t graph, unsigned int to, unsigned int from, |
1246 | bool update_changed) | |
910fdc79 | 1247 | { |
910fdc79 | 1248 | |
3e5937d7 DB |
1249 | gcc_assert (to != from && find (to) == to); |
1250 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1251 | fprintf (dump_file, "Unifying %s to %s\n", | |
1252 | get_varinfo (from)->name, | |
1253 | get_varinfo (to)->name); | |
910fdc79 | 1254 | |
3e5937d7 DB |
1255 | if (update_changed) |
1256 | stats.unified_vars_dynamic++; | |
1257 | else | |
1258 | stats.unified_vars_static++; | |
910fdc79 | 1259 | |
3e5937d7 DB |
1260 | merge_graph_nodes (graph, to, from); |
1261 | merge_node_constraints (graph, to, from); | |
c58936b6 | 1262 | |
058dcc25 ILT |
1263 | if (get_varinfo (from)->no_tbaa_pruning) |
1264 | get_varinfo (to)->no_tbaa_pruning = true; | |
1265 | ||
7b765bed DB |
1266 | /* Mark TO as changed if FROM was changed. If TO was already marked |
1267 | as changed, decrease the changed count. */ | |
1268 | ||
3e5937d7 | 1269 | if (update_changed && TEST_BIT (changed, from)) |
910fdc79 | 1270 | { |
3e5937d7 DB |
1271 | RESET_BIT (changed, from); |
1272 | if (!TEST_BIT (changed, to)) | |
1273 | SET_BIT (changed, to); | |
910fdc79 | 1274 | else |
3e5937d7 DB |
1275 | { |
1276 | gcc_assert (changed_count > 0); | |
1277 | changed_count--; | |
1278 | } | |
1279 | } | |
aa46c8a3 | 1280 | if (get_varinfo (from)->solution) |
3e5937d7 | 1281 | { |
aa46c8a3 DB |
1282 | /* If the solution changes because of the merging, we need to mark |
1283 | the variable as changed. */ | |
1284 | if (bitmap_ior_into (get_varinfo (to)->solution, | |
1285 | get_varinfo (from)->solution)) | |
910fdc79 | 1286 | { |
aa46c8a3 DB |
1287 | if (update_changed && !TEST_BIT (changed, to)) |
1288 | { | |
1289 | SET_BIT (changed, to); | |
1290 | changed_count++; | |
1291 | } | |
1292 | } | |
1293 | ||
1294 | BITMAP_FREE (get_varinfo (from)->solution); | |
1295 | BITMAP_FREE (get_varinfo (from)->oldsolution); | |
1296 | ||
1297 | if (stats.iterations > 0) | |
1298 | { | |
1299 | BITMAP_FREE (get_varinfo (to)->oldsolution); | |
1300 | get_varinfo (to)->oldsolution = BITMAP_ALLOC (&oldpta_obstack); | |
910fdc79 | 1301 | } |
3e5937d7 | 1302 | } |
3e5937d7 DB |
1303 | if (valid_graph_edge (graph, to, to)) |
1304 | { | |
1305 | if (graph->succs[to]) | |
1306 | bitmap_clear_bit (graph->succs[to], to); | |
910fdc79 | 1307 | } |
910fdc79 DB |
1308 | } |
1309 | ||
910fdc79 DB |
1310 | /* Information needed to compute the topological ordering of a graph. */ |
1311 | ||
1312 | struct topo_info | |
1313 | { | |
1314 | /* sbitmap of visited nodes. */ | |
1315 | sbitmap visited; | |
1316 | /* Array that stores the topological order of the graph, *in | |
1317 | reverse*. */ | |
740e80e8 | 1318 | VEC(unsigned,heap) *topo_order; |
910fdc79 DB |
1319 | }; |
1320 | ||
1321 | ||
1322 | /* Initialize and return a topological info structure. */ | |
1323 | ||
1324 | static struct topo_info * | |
1325 | init_topo_info (void) | |
1326 | { | |
7b765bed | 1327 | size_t size = graph->size; |
5ed6ace5 | 1328 | struct topo_info *ti = XNEW (struct topo_info); |
910fdc79 DB |
1329 | ti->visited = sbitmap_alloc (size); |
1330 | sbitmap_zero (ti->visited); | |
740e80e8 | 1331 | ti->topo_order = VEC_alloc (unsigned, heap, 1); |
910fdc79 DB |
1332 | return ti; |
1333 | } | |
1334 | ||
1335 | ||
1336 | /* Free the topological sort info pointed to by TI. */ | |
1337 | ||
1338 | static void | |
1339 | free_topo_info (struct topo_info *ti) | |
1340 | { | |
1341 | sbitmap_free (ti->visited); | |
740e80e8 | 1342 | VEC_free (unsigned, heap, ti->topo_order); |
910fdc79 DB |
1343 | free (ti); |
1344 | } | |
1345 | ||
1346 | /* Visit the graph in topological order, and store the order in the | |
1347 | topo_info structure. */ | |
1348 | ||
1349 | static void | |
1350 | topo_visit (constraint_graph_t graph, struct topo_info *ti, | |
1351 | unsigned int n) | |
1352 | { | |
4ee00913 | 1353 | bitmap_iterator bi; |
4ee00913 DB |
1354 | unsigned int j; |
1355 | ||
910fdc79 | 1356 | SET_BIT (ti->visited, n); |
4ee00913 | 1357 | |
3e5937d7 DB |
1358 | if (graph->succs[n]) |
1359 | EXECUTE_IF_SET_IN_BITMAP (graph->succs[n], 0, j, bi) | |
4ee00913 DB |
1360 | { |
1361 | if (!TEST_BIT (ti->visited, j)) | |
1362 | topo_visit (graph, ti, j); | |
1363 | } | |
3e5937d7 | 1364 | |
740e80e8 | 1365 | VEC_safe_push (unsigned, heap, ti->topo_order, n); |
910fdc79 DB |
1366 | } |
1367 | ||
1368 | /* Return true if variable N + OFFSET is a legal field of N. */ | |
1369 | ||
c58936b6 | 1370 | static bool |
910fdc79 DB |
1371 | type_safe (unsigned int n, unsigned HOST_WIDE_INT *offset) |
1372 | { | |
1373 | varinfo_t ninfo = get_varinfo (n); | |
1374 | ||
1375 | /* For things we've globbed to single variables, any offset into the | |
1376 | variable acts like the entire variable, so that it becomes offset | |
1377 | 0. */ | |
5c3b86af | 1378 | if (ninfo->is_special_var |
910fdc79 DB |
1379 | || ninfo->is_artificial_var |
1380 | || ninfo->is_unknown_size_var) | |
1381 | { | |
1382 | *offset = 0; | |
1383 | return true; | |
1384 | } | |
5c3b86af | 1385 | return (get_varinfo (n)->offset + *offset) < get_varinfo (n)->fullsize; |
910fdc79 DB |
1386 | } |
1387 | ||
910fdc79 DB |
1388 | /* Process a constraint C that represents x = *y, using DELTA as the |
1389 | starting solution. */ | |
1390 | ||
1391 | static void | |
1392 | do_sd_constraint (constraint_graph_t graph, constraint_t c, | |
1393 | bitmap delta) | |
1394 | { | |
7b765bed | 1395 | unsigned int lhs = c->lhs.var; |
910fdc79 DB |
1396 | bool flag = false; |
1397 | bitmap sol = get_varinfo (lhs)->solution; | |
1398 | unsigned int j; | |
1399 | bitmap_iterator bi; | |
4ee00913 | 1400 | |
4ee00913 DB |
1401 | if (bitmap_bit_p (delta, anything_id)) |
1402 | { | |
1403 | flag = !bitmap_bit_p (sol, anything_id); | |
1404 | if (flag) | |
1405 | bitmap_set_bit (sol, anything_id); | |
1406 | goto done; | |
1407 | } | |
c58936b6 | 1408 | /* For each variable j in delta (Sol(y)), add |
910fdc79 DB |
1409 | an edge in the graph from j to x, and union Sol(j) into Sol(x). */ |
1410 | EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi) | |
1411 | { | |
13c2c08b | 1412 | unsigned HOST_WIDE_INT roffset = c->rhs.offset; |
910fdc79 DB |
1413 | if (type_safe (j, &roffset)) |
1414 | { | |
1415 | varinfo_t v; | |
1416 | unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + roffset; | |
1417 | unsigned int t; | |
1418 | ||
4ee00913 | 1419 | v = first_vi_for_offset (get_varinfo (j), fieldoffset); |
8971094d DB |
1420 | if (!v) |
1421 | continue; | |
3e5937d7 | 1422 | t = find (v->id); |
4ee00913 DB |
1423 | |
1424 | /* Adding edges from the special vars is pointless. | |
1425 | They don't have sets that can change. */ | |
1426 | if (get_varinfo (t) ->is_special_var) | |
1427 | flag |= bitmap_ior_into (sol, get_varinfo (t)->solution); | |
57250223 | 1428 | else if (add_graph_edge (graph, lhs, t)) |
4ee00913 | 1429 | flag |= bitmap_ior_into (sol, get_varinfo (t)->solution); |
910fdc79 | 1430 | } |
910fdc79 | 1431 | } |
4cf4d6a3 | 1432 | |
4ee00913 | 1433 | done: |
910fdc79 DB |
1434 | /* If the LHS solution changed, mark the var as changed. */ |
1435 | if (flag) | |
1436 | { | |
1437 | get_varinfo (lhs)->solution = sol; | |
1438 | if (!TEST_BIT (changed, lhs)) | |
1439 | { | |
1440 | SET_BIT (changed, lhs); | |
1441 | changed_count++; | |
1442 | } | |
c58936b6 | 1443 | } |
910fdc79 DB |
1444 | } |
1445 | ||
1446 | /* Process a constraint C that represents *x = y. */ | |
1447 | ||
1448 | static void | |
57250223 | 1449 | do_ds_constraint (constraint_t c, bitmap delta) |
910fdc79 | 1450 | { |
7b765bed | 1451 | unsigned int rhs = c->rhs.var; |
910fdc79 DB |
1452 | bitmap sol = get_varinfo (rhs)->solution; |
1453 | unsigned int j; | |
1454 | bitmap_iterator bi; | |
1455 | ||
4ee00913 DB |
1456 | if (bitmap_bit_p (sol, anything_id)) |
1457 | { | |
1458 | EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi) | |
1459 | { | |
1460 | varinfo_t jvi = get_varinfo (j); | |
1461 | unsigned int t; | |
1462 | unsigned int loff = c->lhs.offset; | |
1463 | unsigned HOST_WIDE_INT fieldoffset = jvi->offset + loff; | |
1464 | varinfo_t v; | |
1465 | ||
1466 | v = first_vi_for_offset (get_varinfo (j), fieldoffset); | |
1467 | if (!v) | |
1468 | continue; | |
3e5937d7 | 1469 | t = find (v->id); |
c58936b6 | 1470 | |
4ee00913 DB |
1471 | if (!bitmap_bit_p (get_varinfo (t)->solution, anything_id)) |
1472 | { | |
1473 | bitmap_set_bit (get_varinfo (t)->solution, anything_id); | |
1474 | if (!TEST_BIT (changed, t)) | |
1475 | { | |
1476 | SET_BIT (changed, t); | |
1477 | changed_count++; | |
1478 | } | |
1479 | } | |
1480 | } | |
1481 | return; | |
1482 | } | |
4ee00913 | 1483 | |
910fdc79 DB |
1484 | /* For each member j of delta (Sol(x)), add an edge from y to j and |
1485 | union Sol(y) into Sol(j) */ | |
1486 | EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi) | |
1487 | { | |
13c2c08b | 1488 | unsigned HOST_WIDE_INT loff = c->lhs.offset; |
62e5bf5d | 1489 | if (type_safe (j, &loff) && !(get_varinfo (j)->is_special_var)) |
910fdc79 DB |
1490 | { |
1491 | varinfo_t v; | |
1492 | unsigned int t; | |
1493 | unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + loff; | |
57250223 | 1494 | bitmap tmp; |
c58936b6 | 1495 | |
910fdc79 | 1496 | v = first_vi_for_offset (get_varinfo (j), fieldoffset); |
8971094d DB |
1497 | if (!v) |
1498 | continue; | |
3e5937d7 | 1499 | t = find (v->id); |
57250223 DB |
1500 | tmp = get_varinfo (t)->solution; |
1501 | ||
7b765bed | 1502 | if (set_union_with_increment (tmp, sol, 0)) |
910fdc79 | 1503 | { |
57250223 DB |
1504 | get_varinfo (t)->solution = tmp; |
1505 | if (t == rhs) | |
1506 | sol = get_varinfo (rhs)->solution; | |
1507 | if (!TEST_BIT (changed, t)) | |
910fdc79 | 1508 | { |
57250223 DB |
1509 | SET_BIT (changed, t); |
1510 | changed_count++; | |
910fdc79 DB |
1511 | } |
1512 | } | |
57250223 | 1513 | } |
910fdc79 DB |
1514 | } |
1515 | } | |
1516 | ||
3e5937d7 DB |
1517 | /* Handle a non-simple (simple meaning requires no iteration), |
1518 | constraint (IE *x = &y, x = *y, *x = y, and x = y with offsets involved). */ | |
c58936b6 | 1519 | |
910fdc79 DB |
1520 | static void |
1521 | do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta) | |
1522 | { | |
1523 | if (c->lhs.type == DEREF) | |
1524 | { | |
1525 | if (c->rhs.type == ADDRESSOF) | |
1526 | { | |
7b765bed | 1527 | gcc_unreachable(); |
910fdc79 DB |
1528 | } |
1529 | else | |
1530 | { | |
1531 | /* *x = y */ | |
57250223 | 1532 | do_ds_constraint (c, delta); |
910fdc79 DB |
1533 | } |
1534 | } | |
57250223 | 1535 | else if (c->rhs.type == DEREF) |
910fdc79 DB |
1536 | { |
1537 | /* x = *y */ | |
13c2c08b DB |
1538 | if (!(get_varinfo (c->lhs.var)->is_special_var)) |
1539 | do_sd_constraint (graph, c, delta); | |
910fdc79 | 1540 | } |
c58936b6 | 1541 | else |
57250223 | 1542 | { |
c58936b6 | 1543 | bitmap tmp; |
57250223 DB |
1544 | bitmap solution; |
1545 | bool flag = false; | |
57250223 | 1546 | |
62e5bf5d | 1547 | gcc_assert (c->rhs.type == SCALAR && c->lhs.type == SCALAR); |
7b765bed DB |
1548 | solution = get_varinfo (c->rhs.var)->solution; |
1549 | tmp = get_varinfo (c->lhs.var)->solution; | |
57250223 DB |
1550 | |
1551 | flag = set_union_with_increment (tmp, solution, c->rhs.offset); | |
c58936b6 | 1552 | |
57250223 DB |
1553 | if (flag) |
1554 | { | |
7b765bed DB |
1555 | get_varinfo (c->lhs.var)->solution = tmp; |
1556 | if (!TEST_BIT (changed, c->lhs.var)) | |
57250223 | 1557 | { |
7b765bed | 1558 | SET_BIT (changed, c->lhs.var); |
57250223 DB |
1559 | changed_count++; |
1560 | } | |
1561 | } | |
1562 | } | |
910fdc79 DB |
1563 | } |
1564 | ||
1565 | /* Initialize and return a new SCC info structure. */ | |
1566 | ||
1567 | static struct scc_info * | |
3e5937d7 | 1568 | init_scc_info (size_t size) |
910fdc79 | 1569 | { |
5ed6ace5 | 1570 | struct scc_info *si = XNEW (struct scc_info); |
3e5937d7 | 1571 | size_t i; |
910fdc79 DB |
1572 | |
1573 | si->current_index = 0; | |
1574 | si->visited = sbitmap_alloc (size); | |
1575 | sbitmap_zero (si->visited); | |
7b765bed DB |
1576 | si->deleted = sbitmap_alloc (size); |
1577 | sbitmap_zero (si->deleted); | |
3e5937d7 DB |
1578 | si->node_mapping = XNEWVEC (unsigned int, size); |
1579 | si->dfs = XCNEWVEC (unsigned int, size); | |
1580 | ||
1581 | for (i = 0; i < size; i++) | |
1582 | si->node_mapping[i] = i; | |
1583 | ||
740e80e8 | 1584 | si->scc_stack = VEC_alloc (unsigned, heap, 1); |
910fdc79 DB |
1585 | return si; |
1586 | } | |
1587 | ||
1588 | /* Free an SCC info structure pointed to by SI */ | |
1589 | ||
1590 | static void | |
1591 | free_scc_info (struct scc_info *si) | |
c58936b6 | 1592 | { |
910fdc79 | 1593 | sbitmap_free (si->visited); |
7b765bed | 1594 | sbitmap_free (si->deleted); |
3e5937d7 DB |
1595 | free (si->node_mapping); |
1596 | free (si->dfs); | |
740e80e8 | 1597 | VEC_free (unsigned, heap, si->scc_stack); |
3e5937d7 | 1598 | free (si); |
910fdc79 DB |
1599 | } |
1600 | ||
1601 | ||
3e5937d7 DB |
1602 | /* Find indirect cycles in GRAPH that occur, using strongly connected |
1603 | components, and note them in the indirect cycles map. | |
1604 | ||
1605 | This technique comes from Ben Hardekopf and Calvin Lin, | |
1606 | "It Pays to be Lazy: Fast and Accurate Pointer Analysis for Millions of | |
1607 | Lines of Code", submitted to PLDI 2007. */ | |
910fdc79 DB |
1608 | |
1609 | static void | |
3e5937d7 | 1610 | find_indirect_cycles (constraint_graph_t graph) |
910fdc79 DB |
1611 | { |
1612 | unsigned int i; | |
3e5937d7 DB |
1613 | unsigned int size = graph->size; |
1614 | struct scc_info *si = init_scc_info (size); | |
910fdc79 | 1615 | |
3e5937d7 DB |
1616 | for (i = 0; i < MIN (LAST_REF_NODE, size); i ++ ) |
1617 | if (!TEST_BIT (si->visited, i) && find (i) == i) | |
910fdc79 | 1618 | scc_visit (graph, si, i); |
c58936b6 | 1619 | |
910fdc79 DB |
1620 | free_scc_info (si); |
1621 | } | |
1622 | ||
1623 | /* Compute a topological ordering for GRAPH, and store the result in the | |
1624 | topo_info structure TI. */ | |
1625 | ||
c58936b6 | 1626 | static void |
910fdc79 DB |
1627 | compute_topo_order (constraint_graph_t graph, |
1628 | struct topo_info *ti) | |
1629 | { | |
1630 | unsigned int i; | |
7b765bed | 1631 | unsigned int size = graph->size; |
c58936b6 | 1632 | |
910fdc79 | 1633 | for (i = 0; i != size; ++i) |
3e5937d7 | 1634 | if (!TEST_BIT (ti->visited, i) && find (i) == i) |
910fdc79 DB |
1635 | topo_visit (graph, ti, i); |
1636 | } | |
1637 | ||
7b765bed DB |
1638 | /* Structure used to for hash value numbering of pointer equivalence |
1639 | classes. */ | |
1640 | ||
1641 | typedef struct equiv_class_label | |
1642 | { | |
1643 | unsigned int equivalence_class; | |
1644 | bitmap labels; | |
1645 | hashval_t hashcode; | |
1646 | } *equiv_class_label_t; | |
586de218 | 1647 | typedef const struct equiv_class_label *const_equiv_class_label_t; |
7b765bed DB |
1648 | |
1649 | /* A hashtable for mapping a bitmap of labels->pointer equivalence | |
1650 | classes. */ | |
1651 | static htab_t pointer_equiv_class_table; | |
1652 | ||
1653 | /* A hashtable for mapping a bitmap of labels->location equivalence | |
1654 | classes. */ | |
1655 | static htab_t location_equiv_class_table; | |
1656 | ||
1657 | /* Hash function for a equiv_class_label_t */ | |
1658 | ||
1659 | static hashval_t | |
1660 | equiv_class_label_hash (const void *p) | |
1661 | { | |
586de218 | 1662 | const_equiv_class_label_t const ecl = (const_equiv_class_label_t) p; |
7b765bed DB |
1663 | return ecl->hashcode; |
1664 | } | |
1665 | ||
1666 | /* Equality function for two equiv_class_label_t's. */ | |
1667 | ||
1668 | static int | |
1669 | equiv_class_label_eq (const void *p1, const void *p2) | |
1670 | { | |
586de218 KG |
1671 | const_equiv_class_label_t const eql1 = (const_equiv_class_label_t) p1; |
1672 | const_equiv_class_label_t const eql2 = (const_equiv_class_label_t) p2; | |
7b765bed DB |
1673 | return bitmap_equal_p (eql1->labels, eql2->labels); |
1674 | } | |
1675 | ||
1676 | /* Lookup a equivalence class in TABLE by the bitmap of LABELS it | |
1677 | contains. */ | |
1678 | ||
1679 | static unsigned int | |
1680 | equiv_class_lookup (htab_t table, bitmap labels) | |
1681 | { | |
1682 | void **slot; | |
1683 | struct equiv_class_label ecl; | |
1684 | ||
1685 | ecl.labels = labels; | |
1686 | ecl.hashcode = bitmap_hash (labels); | |
c58936b6 | 1687 | |
7b765bed DB |
1688 | slot = htab_find_slot_with_hash (table, &ecl, |
1689 | ecl.hashcode, NO_INSERT); | |
1690 | if (!slot) | |
1691 | return 0; | |
1692 | else | |
1693 | return ((equiv_class_label_t) *slot)->equivalence_class; | |
1694 | } | |
1695 | ||
1696 | ||
1697 | /* Add an equivalence class named EQUIVALENCE_CLASS with labels LABELS | |
1698 | to TABLE. */ | |
1699 | ||
1700 | static void | |
1701 | equiv_class_add (htab_t table, unsigned int equivalence_class, | |
1702 | bitmap labels) | |
1703 | { | |
1704 | void **slot; | |
1705 | equiv_class_label_t ecl = XNEW (struct equiv_class_label); | |
1706 | ||
1707 | ecl->labels = labels; | |
1708 | ecl->equivalence_class = equivalence_class; | |
1709 | ecl->hashcode = bitmap_hash (labels); | |
1710 | ||
1711 | slot = htab_find_slot_with_hash (table, ecl, | |
1712 | ecl->hashcode, INSERT); | |
1713 | gcc_assert (!*slot); | |
1714 | *slot = (void *) ecl; | |
1715 | } | |
1716 | ||
1717 | /* Perform offline variable substitution. | |
910fdc79 | 1718 | |
7b765bed DB |
1719 | This is a worst case quadratic time way of identifying variables |
1720 | that must have equivalent points-to sets, including those caused by | |
1721 | static cycles, and single entry subgraphs, in the constraint graph. | |
3e5937d7 | 1722 | |
7b765bed DB |
1723 | The technique is described in "Exploiting Pointer and Location |
1724 | Equivalence to Optimize Pointer Analysis. In the 14th International | |
1725 | Static Analysis Symposium (SAS), August 2007." It is known as the | |
1726 | "HU" algorithm, and is equivalent to value numbering the collapsed | |
1727 | constraint graph including evaluating unions. | |
3e5937d7 DB |
1728 | |
1729 | The general method of finding equivalence classes is as follows: | |
1730 | Add fake nodes (REF nodes) and edges for *a = b and a = *b constraints. | |
7b765bed DB |
1731 | Initialize all non-REF nodes to be direct nodes. |
1732 | For each constraint a = a U {b}, we set pts(a) = pts(a) u {fresh | |
1733 | variable} | |
1734 | For each constraint containing the dereference, we also do the same | |
1735 | thing. | |
1736 | ||
1737 | We then compute SCC's in the graph and unify nodes in the same SCC, | |
1738 | including pts sets. | |
1739 | ||
1740 | For each non-collapsed node x: | |
1741 | Visit all unvisited explicit incoming edges. | |
1742 | Ignoring all non-pointers, set pts(x) = Union of pts(a) for y | |
1743 | where y->x. | |
1744 | Lookup the equivalence class for pts(x). | |
1745 | If we found one, equivalence_class(x) = found class. | |
1746 | Otherwise, equivalence_class(x) = new class, and new_class is | |
1747 | added to the lookup table. | |
3e5937d7 DB |
1748 | |
1749 | All direct nodes with the same equivalence class can be replaced | |
1750 | with a single representative node. | |
1751 | All unlabeled nodes (label == 0) are not pointers and all edges | |
1752 | involving them can be eliminated. | |
7b765bed DB |
1753 | We perform these optimizations during rewrite_constraints |
1754 | ||
1755 | In addition to pointer equivalence class finding, we also perform | |
1756 | location equivalence class finding. This is the set of variables | |
1757 | that always appear together in points-to sets. We use this to | |
1758 | compress the size of the points-to sets. */ | |
1759 | ||
1760 | /* Current maximum pointer equivalence class id. */ | |
1761 | static int pointer_equiv_class; | |
3e5937d7 | 1762 | |
7b765bed DB |
1763 | /* Current maximum location equivalence class id. */ |
1764 | static int location_equiv_class; | |
3e5937d7 DB |
1765 | |
1766 | /* Recursive routine to find strongly connected components in GRAPH, | |
7b765bed | 1767 | and label it's nodes with DFS numbers. */ |
910fdc79 DB |
1768 | |
1769 | static void | |
7b765bed | 1770 | condense_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n) |
910fdc79 | 1771 | { |
3e5937d7 DB |
1772 | unsigned int i; |
1773 | bitmap_iterator bi; | |
1774 | unsigned int my_dfs; | |
c58936b6 | 1775 | |
3e5937d7 DB |
1776 | gcc_assert (si->node_mapping[n] == n); |
1777 | SET_BIT (si->visited, n); | |
1778 | si->dfs[n] = si->current_index ++; | |
1779 | my_dfs = si->dfs[n]; | |
c58936b6 | 1780 | |
3e5937d7 DB |
1781 | /* Visit all the successors. */ |
1782 | EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi) | |
910fdc79 | 1783 | { |
3e5937d7 | 1784 | unsigned int w = si->node_mapping[i]; |
910fdc79 | 1785 | |
7b765bed | 1786 | if (TEST_BIT (si->deleted, w)) |
910fdc79 DB |
1787 | continue; |
1788 | ||
3e5937d7 | 1789 | if (!TEST_BIT (si->visited, w)) |
7b765bed | 1790 | condense_visit (graph, si, w); |
3e5937d7 DB |
1791 | { |
1792 | unsigned int t = si->node_mapping[w]; | |
1793 | unsigned int nnode = si->node_mapping[n]; | |
62e5bf5d | 1794 | gcc_assert (nnode == n); |
910fdc79 | 1795 | |
3e5937d7 DB |
1796 | if (si->dfs[t] < si->dfs[nnode]) |
1797 | si->dfs[n] = si->dfs[t]; | |
1798 | } | |
1799 | } | |
910fdc79 | 1800 | |
3e5937d7 DB |
1801 | /* Visit all the implicit predecessors. */ |
1802 | EXECUTE_IF_IN_NONNULL_BITMAP (graph->implicit_preds[n], 0, i, bi) | |
1803 | { | |
1804 | unsigned int w = si->node_mapping[i]; | |
1805 | ||
7b765bed | 1806 | if (TEST_BIT (si->deleted, w)) |
3e5937d7 DB |
1807 | continue; |
1808 | ||
1809 | if (!TEST_BIT (si->visited, w)) | |
7b765bed | 1810 | condense_visit (graph, si, w); |
3e5937d7 DB |
1811 | { |
1812 | unsigned int t = si->node_mapping[w]; | |
1813 | unsigned int nnode = si->node_mapping[n]; | |
1814 | gcc_assert (nnode == n); | |
1815 | ||
1816 | if (si->dfs[t] < si->dfs[nnode]) | |
1817 | si->dfs[n] = si->dfs[t]; | |
1818 | } | |
1819 | } | |
4ee00913 | 1820 | |
3e5937d7 DB |
1821 | /* See if any components have been identified. */ |
1822 | if (si->dfs[n] == my_dfs) | |
1823 | { | |
1824 | while (VEC_length (unsigned, si->scc_stack) != 0 | |
1825 | && si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs) | |
910fdc79 | 1826 | { |
3e5937d7 DB |
1827 | unsigned int w = VEC_pop (unsigned, si->scc_stack); |
1828 | si->node_mapping[w] = n; | |
1829 | ||
1830 | if (!TEST_BIT (graph->direct_nodes, w)) | |
1831 | RESET_BIT (graph->direct_nodes, n); | |
3e5937d7 | 1832 | |
7b765bed DB |
1833 | /* Unify our nodes. */ |
1834 | if (graph->preds[w]) | |
1835 | { | |
1836 | if (!graph->preds[n]) | |
1837 | graph->preds[n] = BITMAP_ALLOC (&predbitmap_obstack); | |
1838 | bitmap_ior_into (graph->preds[n], graph->preds[w]); | |
1839 | } | |
1840 | if (graph->implicit_preds[w]) | |
1841 | { | |
1842 | if (!graph->implicit_preds[n]) | |
1843 | graph->implicit_preds[n] = BITMAP_ALLOC (&predbitmap_obstack); | |
1844 | bitmap_ior_into (graph->implicit_preds[n], | |
1845 | graph->implicit_preds[w]); | |
1846 | } | |
1847 | if (graph->points_to[w]) | |
1848 | { | |
1849 | if (!graph->points_to[n]) | |
1850 | graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack); | |
1851 | bitmap_ior_into (graph->points_to[n], | |
1852 | graph->points_to[w]); | |
1853 | } | |
3e5937d7 DB |
1854 | EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi) |
1855 | { | |
7b765bed DB |
1856 | unsigned int rep = si->node_mapping[i]; |
1857 | graph->number_incoming[rep]++; | |
3e5937d7 | 1858 | } |
3e5937d7 | 1859 | } |
7b765bed | 1860 | SET_BIT (si->deleted, n); |
3e5937d7 DB |
1861 | } |
1862 | else | |
1863 | VEC_safe_push (unsigned, heap, si->scc_stack, n); | |
1864 | } | |
1865 | ||
7b765bed DB |
1866 | /* Label pointer equivalences. */ |
1867 | ||
1868 | static void | |
1869 | label_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n) | |
1870 | { | |
1871 | unsigned int i; | |
1872 | bitmap_iterator bi; | |
1873 | SET_BIT (si->visited, n); | |
1874 | ||
1875 | if (!graph->points_to[n]) | |
1876 | graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack); | |
1877 | ||
1878 | /* Label and union our incoming edges's points to sets. */ | |
1879 | EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi) | |
1880 | { | |
1881 | unsigned int w = si->node_mapping[i]; | |
1882 | if (!TEST_BIT (si->visited, w)) | |
1883 | label_visit (graph, si, w); | |
1884 | ||
1885 | /* Skip unused edges */ | |
1886 | if (w == n || graph->pointer_label[w] == 0) | |
1887 | { | |
1888 | graph->number_incoming[w]--; | |
1889 | continue; | |
1890 | } | |
1891 | if (graph->points_to[w]) | |
1892 | bitmap_ior_into(graph->points_to[n], graph->points_to[w]); | |
1893 | ||
1894 | /* If all incoming edges to w have been processed and | |
1895 | graph->points_to[w] was not stored in the hash table, we can | |
1896 | free it. */ | |
1897 | graph->number_incoming[w]--; | |
1898 | if (!graph->number_incoming[w] && !TEST_BIT (graph->pt_used, w)) | |
1899 | { | |
1900 | BITMAP_FREE (graph->points_to[w]); | |
1901 | } | |
1902 | } | |
1903 | /* Indirect nodes get fresh variables. */ | |
1904 | if (!TEST_BIT (graph->direct_nodes, n)) | |
1905 | bitmap_set_bit (graph->points_to[n], FIRST_REF_NODE + n); | |
1906 | ||
1907 | if (!bitmap_empty_p (graph->points_to[n])) | |
1908 | { | |
1909 | unsigned int label = equiv_class_lookup (pointer_equiv_class_table, | |
1910 | graph->points_to[n]); | |
1911 | if (!label) | |
1912 | { | |
1913 | SET_BIT (graph->pt_used, n); | |
1914 | label = pointer_equiv_class++; | |
1915 | equiv_class_add (pointer_equiv_class_table, | |
1916 | label, graph->points_to[n]); | |
1917 | } | |
1918 | graph->pointer_label[n] = label; | |
1919 | } | |
1920 | } | |
1921 | ||
3e5937d7 DB |
1922 | /* Perform offline variable substitution, discovering equivalence |
1923 | classes, and eliminating non-pointer variables. */ | |
1924 | ||
1925 | static struct scc_info * | |
1926 | perform_var_substitution (constraint_graph_t graph) | |
1927 | { | |
1928 | unsigned int i; | |
1929 | unsigned int size = graph->size; | |
1930 | struct scc_info *si = init_scc_info (size); | |
1931 | ||
1932 | bitmap_obstack_initialize (&iteration_obstack); | |
7b765bed DB |
1933 | pointer_equiv_class_table = htab_create (511, equiv_class_label_hash, |
1934 | equiv_class_label_eq, free); | |
1935 | location_equiv_class_table = htab_create (511, equiv_class_label_hash, | |
1936 | equiv_class_label_eq, free); | |
1937 | pointer_equiv_class = 1; | |
1938 | location_equiv_class = 1; | |
1939 | ||
1940 | /* Condense the nodes, which means to find SCC's, count incoming | |
1941 | predecessors, and unite nodes in SCC's. */ | |
aa46c8a3 | 1942 | for (i = 0; i < FIRST_REF_NODE; i++) |
7b765bed DB |
1943 | if (!TEST_BIT (si->visited, si->node_mapping[i])) |
1944 | condense_visit (graph, si, si->node_mapping[i]); | |
3e5937d7 | 1945 | |
7b765bed DB |
1946 | sbitmap_zero (si->visited); |
1947 | /* Actually the label the nodes for pointer equivalences */ | |
aa46c8a3 | 1948 | for (i = 0; i < FIRST_REF_NODE; i++) |
3e5937d7 DB |
1949 | if (!TEST_BIT (si->visited, si->node_mapping[i])) |
1950 | label_visit (graph, si, si->node_mapping[i]); | |
1951 | ||
7b765bed DB |
1952 | /* Calculate location equivalence labels. */ |
1953 | for (i = 0; i < FIRST_REF_NODE; i++) | |
1954 | { | |
1955 | bitmap pointed_by; | |
1956 | bitmap_iterator bi; | |
1957 | unsigned int j; | |
1958 | unsigned int label; | |
1959 | ||
1960 | if (!graph->pointed_by[i]) | |
1961 | continue; | |
1962 | pointed_by = BITMAP_ALLOC (&iteration_obstack); | |
1963 | ||
1964 | /* Translate the pointed-by mapping for pointer equivalence | |
1965 | labels. */ | |
1966 | EXECUTE_IF_SET_IN_BITMAP (graph->pointed_by[i], 0, j, bi) | |
1967 | { | |
1968 | bitmap_set_bit (pointed_by, | |
1969 | graph->pointer_label[si->node_mapping[j]]); | |
1970 | } | |
1971 | /* The original pointed_by is now dead. */ | |
1972 | BITMAP_FREE (graph->pointed_by[i]); | |
1973 | ||
1974 | /* Look up the location equivalence label if one exists, or make | |
1975 | one otherwise. */ | |
1976 | label = equiv_class_lookup (location_equiv_class_table, | |
1977 | pointed_by); | |
1978 | if (label == 0) | |
1979 | { | |
1980 | label = location_equiv_class++; | |
1981 | equiv_class_add (location_equiv_class_table, | |
1982 | label, pointed_by); | |
1983 | } | |
1984 | else | |
1985 | { | |
1986 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1987 | fprintf (dump_file, "Found location equivalence for node %s\n", | |
1988 | get_varinfo (i)->name); | |
1989 | BITMAP_FREE (pointed_by); | |
1990 | } | |
1991 | graph->loc_label[i] = label; | |
1992 | ||
1993 | } | |
1994 | ||
3e5937d7 DB |
1995 | if (dump_file && (dump_flags & TDF_DETAILS)) |
1996 | for (i = 0; i < FIRST_REF_NODE; i++) | |
1997 | { | |
1998 | bool direct_node = TEST_BIT (graph->direct_nodes, i); | |
1999 | fprintf (dump_file, | |
7b765bed DB |
2000 | "Equivalence classes for %s node id %d:%s are pointer: %d" |
2001 | ", location:%d\n", | |
3e5937d7 | 2002 | direct_node ? "Direct node" : "Indirect node", i, |
62e5bf5d | 2003 | get_varinfo (i)->name, |
7b765bed DB |
2004 | graph->pointer_label[si->node_mapping[i]], |
2005 | graph->loc_label[si->node_mapping[i]]); | |
3e5937d7 DB |
2006 | } |
2007 | ||
2008 | /* Quickly eliminate our non-pointer variables. */ | |
2009 | ||
2010 | for (i = 0; i < FIRST_REF_NODE; i++) | |
2011 | { | |
2012 | unsigned int node = si->node_mapping[i]; | |
2013 | ||
aa46c8a3 | 2014 | if (graph->pointer_label[node] == 0) |
3e5937d7 | 2015 | { |
23e73993 | 2016 | if (dump_file && (dump_flags & TDF_DETAILS)) |
3e5937d7 DB |
2017 | fprintf (dump_file, |
2018 | "%s is a non-pointer variable, eliminating edges.\n", | |
2019 | get_varinfo (node)->name); | |
2020 | stats.nonpointer_vars++; | |
2021 | clear_edges_for_node (graph, node); | |
910fdc79 DB |
2022 | } |
2023 | } | |
7b765bed | 2024 | |
3e5937d7 DB |
2025 | return si; |
2026 | } | |
2027 | ||
2028 | /* Free information that was only necessary for variable | |
2029 | substitution. */ | |
910fdc79 | 2030 | |
3e5937d7 DB |
2031 | static void |
2032 | free_var_substitution_info (struct scc_info *si) | |
2033 | { | |
2034 | free_scc_info (si); | |
7b765bed DB |
2035 | free (graph->pointer_label); |
2036 | free (graph->loc_label); | |
2037 | free (graph->pointed_by); | |
2038 | free (graph->points_to); | |
2039 | free (graph->number_incoming); | |
3e5937d7 DB |
2040 | free (graph->eq_rep); |
2041 | sbitmap_free (graph->direct_nodes); | |
7b765bed DB |
2042 | sbitmap_free (graph->pt_used); |
2043 | htab_delete (pointer_equiv_class_table); | |
2044 | htab_delete (location_equiv_class_table); | |
4ee00913 | 2045 | bitmap_obstack_release (&iteration_obstack); |
3e5937d7 DB |
2046 | } |
2047 | ||
2048 | /* Return an existing node that is equivalent to NODE, which has | |
2049 | equivalence class LABEL, if one exists. Return NODE otherwise. */ | |
2050 | ||
2051 | static unsigned int | |
2052 | find_equivalent_node (constraint_graph_t graph, | |
2053 | unsigned int node, unsigned int label) | |
2054 | { | |
2055 | /* If the address version of this variable is unused, we can | |
2056 | substitute it for anything else with the same label. | |
2057 | Otherwise, we know the pointers are equivalent, but not the | |
7b765bed | 2058 | locations, and we can unite them later. */ |
3e5937d7 | 2059 | |
7b765bed | 2060 | if (!bitmap_bit_p (graph->address_taken, node)) |
3e5937d7 DB |
2061 | { |
2062 | gcc_assert (label < graph->size); | |
2063 | ||
2064 | if (graph->eq_rep[label] != -1) | |
2065 | { | |
2066 | /* Unify the two variables since we know they are equivalent. */ | |
2067 | if (unite (graph->eq_rep[label], node)) | |
2068 | unify_nodes (graph, graph->eq_rep[label], node, false); | |
2069 | return graph->eq_rep[label]; | |
2070 | } | |
2071 | else | |
2072 | { | |
2073 | graph->eq_rep[label] = node; | |
7b765bed | 2074 | graph->pe_rep[label] = node; |
3e5937d7 DB |
2075 | } |
2076 | } | |
7b765bed DB |
2077 | else |
2078 | { | |
2079 | gcc_assert (label < graph->size); | |
2080 | graph->pe[node] = label; | |
2081 | if (graph->pe_rep[label] == -1) | |
2082 | graph->pe_rep[label] = node; | |
2083 | } | |
2084 | ||
3e5937d7 DB |
2085 | return node; |
2086 | } | |
2087 | ||
7b765bed DB |
2088 | /* Unite pointer equivalent but not location equivalent nodes in |
2089 | GRAPH. This may only be performed once variable substitution is | |
2090 | finished. */ | |
2091 | ||
2092 | static void | |
2093 | unite_pointer_equivalences (constraint_graph_t graph) | |
2094 | { | |
2095 | unsigned int i; | |
2096 | ||
2097 | /* Go through the pointer equivalences and unite them to their | |
2098 | representative, if they aren't already. */ | |
aa46c8a3 | 2099 | for (i = 0; i < FIRST_REF_NODE; i++) |
7b765bed DB |
2100 | { |
2101 | unsigned int label = graph->pe[i]; | |
aa46c8a3 DB |
2102 | if (label) |
2103 | { | |
2104 | int label_rep = graph->pe_rep[label]; | |
2105 | ||
2106 | if (label_rep == -1) | |
2107 | continue; | |
2108 | ||
2109 | label_rep = find (label_rep); | |
2110 | if (label_rep >= 0 && unite (label_rep, find (i))) | |
2111 | unify_nodes (graph, label_rep, i, false); | |
2112 | } | |
7b765bed DB |
2113 | } |
2114 | } | |
2115 | ||
2116 | /* Move complex constraints to the GRAPH nodes they belong to. */ | |
3e5937d7 DB |
2117 | |
2118 | static void | |
7b765bed DB |
2119 | move_complex_constraints (constraint_graph_t graph) |
2120 | { | |
2121 | int i; | |
2122 | constraint_t c; | |
2123 | ||
2124 | for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++) | |
2125 | { | |
2126 | if (c) | |
2127 | { | |
2128 | struct constraint_expr lhs = c->lhs; | |
2129 | struct constraint_expr rhs = c->rhs; | |
2130 | ||
2131 | if (lhs.type == DEREF) | |
2132 | { | |
2133 | insert_into_complex (graph, lhs.var, c); | |
2134 | } | |
2135 | else if (rhs.type == DEREF) | |
2136 | { | |
2137 | if (!(get_varinfo (lhs.var)->is_special_var)) | |
2138 | insert_into_complex (graph, rhs.var, c); | |
2139 | } | |
2140 | else if (rhs.type != ADDRESSOF && lhs.var > anything_id | |
2141 | && (lhs.offset != 0 || rhs.offset != 0)) | |
2142 | { | |
2143 | insert_into_complex (graph, rhs.var, c); | |
2144 | } | |
2145 | } | |
2146 | } | |
2147 | } | |
2148 | ||
2149 | ||
2150 | /* Optimize and rewrite complex constraints while performing | |
2151 | collapsing of equivalent nodes. SI is the SCC_INFO that is the | |
2152 | result of perform_variable_substitution. */ | |
2153 | ||
2154 | static void | |
2155 | rewrite_constraints (constraint_graph_t graph, | |
2156 | struct scc_info *si) | |
3e5937d7 DB |
2157 | { |
2158 | int i; | |
2159 | unsigned int j; | |
2160 | constraint_t c; | |
2161 | ||
2162 | for (j = 0; j < graph->size; j++) | |
2163 | gcc_assert (find (j) == j); | |
2164 | ||
2165 | for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++) | |
2166 | { | |
2167 | struct constraint_expr lhs = c->lhs; | |
2168 | struct constraint_expr rhs = c->rhs; | |
2169 | unsigned int lhsvar = find (get_varinfo_fc (lhs.var)->id); | |
2170 | unsigned int rhsvar = find (get_varinfo_fc (rhs.var)->id); | |
2171 | unsigned int lhsnode, rhsnode; | |
2172 | unsigned int lhslabel, rhslabel; | |
2173 | ||
2174 | lhsnode = si->node_mapping[lhsvar]; | |
2175 | rhsnode = si->node_mapping[rhsvar]; | |
7b765bed DB |
2176 | lhslabel = graph->pointer_label[lhsnode]; |
2177 | rhslabel = graph->pointer_label[rhsnode]; | |
3e5937d7 DB |
2178 | |
2179 | /* See if it is really a non-pointer variable, and if so, ignore | |
2180 | the constraint. */ | |
2181 | if (lhslabel == 0) | |
2182 | { | |
aa46c8a3 | 2183 | if (dump_file && (dump_flags & TDF_DETAILS)) |
3e5937d7 | 2184 | { |
aa46c8a3 DB |
2185 | |
2186 | fprintf (dump_file, "%s is a non-pointer variable," | |
2187 | "ignoring constraint:", | |
2188 | get_varinfo (lhs.var)->name); | |
2189 | dump_constraint (dump_file, c); | |
3e5937d7 | 2190 | } |
aa46c8a3 DB |
2191 | VEC_replace (constraint_t, constraints, i, NULL); |
2192 | continue; | |
3e5937d7 DB |
2193 | } |
2194 | ||
2195 | if (rhslabel == 0) | |
2196 | { | |
aa46c8a3 | 2197 | if (dump_file && (dump_flags & TDF_DETAILS)) |
3e5937d7 | 2198 | { |
aa46c8a3 DB |
2199 | |
2200 | fprintf (dump_file, "%s is a non-pointer variable," | |
2201 | "ignoring constraint:", | |
2202 | get_varinfo (rhs.var)->name); | |
2203 | dump_constraint (dump_file, c); | |
3e5937d7 | 2204 | } |
aa46c8a3 DB |
2205 | VEC_replace (constraint_t, constraints, i, NULL); |
2206 | continue; | |
3e5937d7 DB |
2207 | } |
2208 | ||
2209 | lhsvar = find_equivalent_node (graph, lhsvar, lhslabel); | |
2210 | rhsvar = find_equivalent_node (graph, rhsvar, rhslabel); | |
2211 | c->lhs.var = lhsvar; | |
2212 | c->rhs.var = rhsvar; | |
2213 | ||
3e5937d7 DB |
2214 | } |
2215 | } | |
2216 | ||
2217 | /* Eliminate indirect cycles involving NODE. Return true if NODE was | |
2218 | part of an SCC, false otherwise. */ | |
2219 | ||
2220 | static bool | |
2221 | eliminate_indirect_cycles (unsigned int node) | |
2222 | { | |
2223 | if (graph->indirect_cycles[node] != -1 | |
2224 | && !bitmap_empty_p (get_varinfo (node)->solution)) | |
2225 | { | |
2226 | unsigned int i; | |
2227 | VEC(unsigned,heap) *queue = NULL; | |
2228 | int queuepos; | |
2229 | unsigned int to = find (graph->indirect_cycles[node]); | |
2230 | bitmap_iterator bi; | |
2231 | ||
2232 | /* We can't touch the solution set and call unify_nodes | |
2233 | at the same time, because unify_nodes is going to do | |
2234 | bitmap unions into it. */ | |
2235 | ||
2236 | EXECUTE_IF_SET_IN_BITMAP (get_varinfo (node)->solution, 0, i, bi) | |
2237 | { | |
2238 | if (find (i) == i && i != to) | |
2239 | { | |
2240 | if (unite (to, i)) | |
2241 | VEC_safe_push (unsigned, heap, queue, i); | |
2242 | } | |
2243 | } | |
2244 | ||
2245 | for (queuepos = 0; | |
2246 | VEC_iterate (unsigned, queue, queuepos, i); | |
2247 | queuepos++) | |
2248 | { | |
2249 | unify_nodes (graph, to, i, true); | |
2250 | } | |
2251 | VEC_free (unsigned, heap, queue); | |
2252 | return true; | |
2253 | } | |
2254 | return false; | |
910fdc79 DB |
2255 | } |
2256 | ||
910fdc79 DB |
2257 | /* Solve the constraint graph GRAPH using our worklist solver. |
2258 | This is based on the PW* family of solvers from the "Efficient Field | |
2259 | Sensitive Pointer Analysis for C" paper. | |
2260 | It works by iterating over all the graph nodes, processing the complex | |
2261 | constraints and propagating the copy constraints, until everything stops | |
2262 | changed. This corresponds to steps 6-8 in the solving list given above. */ | |
2263 | ||
2264 | static void | |
2265 | solve_graph (constraint_graph_t graph) | |
2266 | { | |
7b765bed | 2267 | unsigned int size = graph->size; |
910fdc79 | 2268 | unsigned int i; |
3e5937d7 | 2269 | bitmap pts; |
910fdc79 | 2270 | |
3e5937d7 | 2271 | changed_count = 0; |
910fdc79 | 2272 | changed = sbitmap_alloc (size); |
3e5937d7 | 2273 | sbitmap_zero (changed); |
c58936b6 | 2274 | |
3e5937d7 | 2275 | /* Mark all initial non-collapsed nodes as changed. */ |
910fdc79 | 2276 | for (i = 0; i < size; i++) |
3e5937d7 DB |
2277 | { |
2278 | varinfo_t ivi = get_varinfo (i); | |
2279 | if (find (i) == i && !bitmap_empty_p (ivi->solution) | |
2280 | && ((graph->succs[i] && !bitmap_empty_p (graph->succs[i])) | |
2281 | || VEC_length (constraint_t, graph->complex[i]) > 0)) | |
2282 | { | |
2283 | SET_BIT (changed, i); | |
2284 | changed_count++; | |
2285 | } | |
2286 | } | |
2287 | ||
2288 | /* Allocate a bitmap to be used to store the changed bits. */ | |
2289 | pts = BITMAP_ALLOC (&pta_obstack); | |
c58936b6 | 2290 | |
910fdc79 DB |
2291 | while (changed_count > 0) |
2292 | { | |
2293 | unsigned int i; | |
2294 | struct topo_info *ti = init_topo_info (); | |
2295 | stats.iterations++; | |
4ee00913 | 2296 | |
910fdc79 | 2297 | bitmap_obstack_initialize (&iteration_obstack); |
c58936b6 | 2298 | |
910fdc79 DB |
2299 | compute_topo_order (graph, ti); |
2300 | ||
740e80e8 | 2301 | while (VEC_length (unsigned, ti->topo_order) != 0) |
910fdc79 | 2302 | { |
3e5937d7 | 2303 | |
740e80e8 | 2304 | i = VEC_pop (unsigned, ti->topo_order); |
3e5937d7 DB |
2305 | |
2306 | /* If this variable is not a representative, skip it. */ | |
2307 | if (find (i) != i) | |
2308 | continue; | |
2309 | ||
d3c36974 DB |
2310 | /* In certain indirect cycle cases, we may merge this |
2311 | variable to another. */ | |
62e5bf5d | 2312 | if (eliminate_indirect_cycles (i) && find (i) != i) |
d3c36974 | 2313 | continue; |
910fdc79 DB |
2314 | |
2315 | /* If the node has changed, we need to process the | |
2316 | complex constraints and outgoing edges again. */ | |
2317 | if (TEST_BIT (changed, i)) | |
2318 | { | |
2319 | unsigned int j; | |
2320 | constraint_t c; | |
910fdc79 | 2321 | bitmap solution; |
3e5937d7 | 2322 | VEC(constraint_t,heap) *complex = graph->complex[i]; |
21392f19 | 2323 | bool solution_empty; |
48e540b0 | 2324 | |
910fdc79 DB |
2325 | RESET_BIT (changed, i); |
2326 | changed_count--; | |
2327 | ||
3e5937d7 DB |
2328 | /* Compute the changed set of solution bits. */ |
2329 | bitmap_and_compl (pts, get_varinfo (i)->solution, | |
2330 | get_varinfo (i)->oldsolution); | |
2331 | ||
2332 | if (bitmap_empty_p (pts)) | |
2333 | continue; | |
2334 | ||
2335 | bitmap_ior_into (get_varinfo (i)->oldsolution, pts); | |
2336 | ||
910fdc79 | 2337 | solution = get_varinfo (i)->solution; |
21392f19 DB |
2338 | solution_empty = bitmap_empty_p (solution); |
2339 | ||
2340 | /* Process the complex constraints */ | |
910fdc79 | 2341 | for (j = 0; VEC_iterate (constraint_t, complex, j, c); j++) |
21392f19 | 2342 | { |
7b765bed DB |
2343 | /* XXX: This is going to unsort the constraints in |
2344 | some cases, which will occasionally add duplicate | |
2345 | constraints during unification. This does not | |
2346 | affect correctness. */ | |
2347 | c->lhs.var = find (c->lhs.var); | |
2348 | c->rhs.var = find (c->rhs.var); | |
2349 | ||
21392f19 DB |
2350 | /* The only complex constraint that can change our |
2351 | solution to non-empty, given an empty solution, | |
2352 | is a constraint where the lhs side is receiving | |
2353 | some set from elsewhere. */ | |
2354 | if (!solution_empty || c->lhs.type != DEREF) | |
3e5937d7 | 2355 | do_complex_constraint (graph, c, pts); |
21392f19 | 2356 | } |
910fdc79 | 2357 | |
21392f19 DB |
2358 | solution_empty = bitmap_empty_p (solution); |
2359 | ||
2360 | if (!solution_empty) | |
4ee00913 | 2361 | { |
3e5937d7 DB |
2362 | bitmap_iterator bi; |
2363 | ||
21392f19 | 2364 | /* Propagate solution to all successors. */ |
c58936b6 | 2365 | EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i], |
21392f19 | 2366 | 0, j, bi) |
4ee00913 | 2367 | { |
3e5937d7 DB |
2368 | bitmap tmp; |
2369 | bool flag; | |
2370 | ||
2371 | unsigned int to = find (j); | |
2372 | tmp = get_varinfo (to)->solution; | |
2373 | flag = false; | |
c58936b6 | 2374 | |
3e5937d7 DB |
2375 | /* Don't try to propagate to ourselves. */ |
2376 | if (to == i) | |
2377 | continue; | |
c58936b6 | 2378 | |
3e5937d7 | 2379 | flag = set_union_with_increment (tmp, pts, 0); |
c58936b6 | 2380 | |
21392f19 | 2381 | if (flag) |
4ee00913 | 2382 | { |
3e5937d7 DB |
2383 | get_varinfo (to)->solution = tmp; |
2384 | if (!TEST_BIT (changed, to)) | |
21392f19 | 2385 | { |
3e5937d7 | 2386 | SET_BIT (changed, to); |
21392f19 DB |
2387 | changed_count++; |
2388 | } | |
4ee00913 DB |
2389 | } |
2390 | } | |
910fdc79 DB |
2391 | } |
2392 | } | |
2393 | } | |
2394 | free_topo_info (ti); | |
2395 | bitmap_obstack_release (&iteration_obstack); | |
2396 | } | |
c58936b6 | 2397 | |
3e5937d7 | 2398 | BITMAP_FREE (pts); |
910fdc79 | 2399 | sbitmap_free (changed); |
3e5937d7 | 2400 | bitmap_obstack_release (&oldpta_obstack); |
910fdc79 DB |
2401 | } |
2402 | ||
3e5937d7 | 2403 | /* Map from trees to variable infos. */ |
15814ba0 | 2404 | static struct pointer_map_t *vi_for_tree; |
910fdc79 | 2405 | |
910fdc79 | 2406 | |
15814ba0 | 2407 | /* Insert ID as the variable id for tree T in the vi_for_tree map. */ |
910fdc79 | 2408 | |
c58936b6 | 2409 | static void |
3e5937d7 | 2410 | insert_vi_for_tree (tree t, varinfo_t vi) |
910fdc79 | 2411 | { |
15814ba0 PB |
2412 | void **slot = pointer_map_insert (vi_for_tree, t); |
2413 | gcc_assert (vi); | |
910fdc79 | 2414 | gcc_assert (*slot == NULL); |
15814ba0 | 2415 | *slot = vi; |
910fdc79 DB |
2416 | } |
2417 | ||
3e5937d7 | 2418 | /* Find the variable info for tree T in VI_FOR_TREE. If T does not |
15814ba0 | 2419 | exist in the map, return NULL, otherwise, return the varinfo we found. */ |
910fdc79 | 2420 | |
15814ba0 PB |
2421 | static varinfo_t |
2422 | lookup_vi_for_tree (tree t) | |
910fdc79 | 2423 | { |
15814ba0 PB |
2424 | void **slot = pointer_map_contains (vi_for_tree, t); |
2425 | if (slot == NULL) | |
2426 | return NULL; | |
910fdc79 | 2427 | |
15814ba0 | 2428 | return (varinfo_t) *slot; |
910fdc79 DB |
2429 | } |
2430 | ||
2431 | /* Return a printable name for DECL */ | |
2432 | ||
2433 | static const char * | |
2434 | alias_get_name (tree decl) | |
2435 | { | |
2436 | const char *res = get_name (decl); | |
2437 | char *temp; | |
2438 | int num_printed = 0; | |
2439 | ||
2440 | if (res != NULL) | |
2441 | return res; | |
2442 | ||
2443 | res = "NULL"; | |
4f6c9110 RG |
2444 | if (!dump_file) |
2445 | return res; | |
2446 | ||
910fdc79 DB |
2447 | if (TREE_CODE (decl) == SSA_NAME) |
2448 | { | |
c58936b6 | 2449 | num_printed = asprintf (&temp, "%s_%u", |
910fdc79 DB |
2450 | alias_get_name (SSA_NAME_VAR (decl)), |
2451 | SSA_NAME_VERSION (decl)); | |
2452 | } | |
2453 | else if (DECL_P (decl)) | |
2454 | { | |
2455 | num_printed = asprintf (&temp, "D.%u", DECL_UID (decl)); | |
2456 | } | |
2457 | if (num_printed > 0) | |
2458 | { | |
2459 | res = ggc_strdup (temp); | |
2460 | free (temp); | |
2461 | } | |
2462 | return res; | |
2463 | } | |
2464 | ||
15814ba0 PB |
2465 | /* Find the variable id for tree T in the map. |
2466 | If T doesn't exist in the map, create an entry for it and return it. */ | |
910fdc79 | 2467 | |
3e5937d7 DB |
2468 | static varinfo_t |
2469 | get_vi_for_tree (tree t) | |
910fdc79 | 2470 | { |
15814ba0 PB |
2471 | void **slot = pointer_map_contains (vi_for_tree, t); |
2472 | if (slot == NULL) | |
3e5937d7 | 2473 | return get_varinfo (create_variable_info_for (t, alias_get_name (t))); |
c58936b6 | 2474 | |
15814ba0 | 2475 | return (varinfo_t) *slot; |
910fdc79 DB |
2476 | } |
2477 | ||
2478 | /* Get a constraint expression from an SSA_VAR_P node. */ | |
2479 | ||
2480 | static struct constraint_expr | |
2481 | get_constraint_exp_from_ssa_var (tree t) | |
2482 | { | |
2483 | struct constraint_expr cexpr; | |
2484 | ||
2485 | gcc_assert (SSA_VAR_P (t) || DECL_P (t)); | |
2486 | ||
2487 | /* For parameters, get at the points-to set for the actual parm | |
2488 | decl. */ | |
c58936b6 DB |
2489 | if (TREE_CODE (t) == SSA_NAME |
2490 | && TREE_CODE (SSA_NAME_VAR (t)) == PARM_DECL | |
38635499 | 2491 | && SSA_NAME_IS_DEFAULT_DEF (t)) |
910fdc79 DB |
2492 | return get_constraint_exp_from_ssa_var (SSA_NAME_VAR (t)); |
2493 | ||
2494 | cexpr.type = SCALAR; | |
c58936b6 | 2495 | |
3e5937d7 | 2496 | cexpr.var = get_vi_for_tree (t)->id; |
47bcb538 DB |
2497 | /* If we determine the result is "anything", and we know this is readonly, |
2498 | say it points to readonly memory instead. */ | |
2499 | if (cexpr.var == anything_id && TREE_READONLY (t)) | |
910fdc79 | 2500 | { |
3e5937d7 | 2501 | cexpr.type = ADDRESSOF; |
910fdc79 DB |
2502 | cexpr.var = readonly_id; |
2503 | } | |
c58936b6 | 2504 | |
910fdc79 DB |
2505 | cexpr.offset = 0; |
2506 | return cexpr; | |
2507 | } | |
2508 | ||
2509 | /* Process a completed constraint T, and add it to the constraint | |
7b765bed DB |
2510 | list. FROM_CALL is true if this is a constraint coming from a |
2511 | call, which means any DEREFs we see are "may-deref's", not | |
2512 | "must-deref"'s. */ | |
910fdc79 DB |
2513 | |
2514 | static void | |
7b765bed | 2515 | process_constraint_1 (constraint_t t, bool from_call) |
910fdc79 DB |
2516 | { |
2517 | struct constraint_expr rhs = t->rhs; | |
2518 | struct constraint_expr lhs = t->lhs; | |
c58936b6 | 2519 | |
910fdc79 DB |
2520 | gcc_assert (rhs.var < VEC_length (varinfo_t, varmap)); |
2521 | gcc_assert (lhs.var < VEC_length (varinfo_t, varmap)); | |
2522 | ||
7b765bed DB |
2523 | if (!from_call) |
2524 | { | |
2525 | if (lhs.type == DEREF) | |
2526 | get_varinfo (lhs.var)->directly_dereferenced = true; | |
2527 | if (rhs.type == DEREF) | |
2528 | get_varinfo (rhs.var)->directly_dereferenced = true; | |
2529 | } | |
c58936b6 DB |
2530 | |
2531 | if (!use_field_sensitive) | |
2532 | { | |
2533 | t->rhs.offset = 0; | |
2534 | t->lhs.offset = 0; | |
2535 | } | |
2536 | ||
910fdc79 DB |
2537 | /* ANYTHING == ANYTHING is pointless. */ |
2538 | if (lhs.var == anything_id && rhs.var == anything_id) | |
2539 | return; | |
2540 | ||
2541 | /* If we have &ANYTHING = something, convert to SOMETHING = &ANYTHING) */ | |
3e5937d7 | 2542 | else if (lhs.var == anything_id && lhs.type == ADDRESSOF) |
910fdc79 DB |
2543 | { |
2544 | rhs = t->lhs; | |
2545 | t->lhs = t->rhs; | |
2546 | t->rhs = rhs; | |
7b765bed | 2547 | process_constraint_1 (t, from_call); |
c58936b6 | 2548 | } |
910fdc79 DB |
2549 | /* This can happen in our IR with things like n->a = *p */ |
2550 | else if (rhs.type == DEREF && lhs.type == DEREF && rhs.var != anything_id) | |
2551 | { | |
2552 | /* Split into tmp = *rhs, *lhs = tmp */ | |
2553 | tree rhsdecl = get_varinfo (rhs.var)->decl; | |
2554 | tree pointertype = TREE_TYPE (rhsdecl); | |
2555 | tree pointedtotype = TREE_TYPE (pointertype); | |
2556 | tree tmpvar = create_tmp_var_raw (pointedtotype, "doubledereftmp"); | |
2557 | struct constraint_expr tmplhs = get_constraint_exp_from_ssa_var (tmpvar); | |
c58936b6 | 2558 | |
910fdc79 DB |
2559 | /* If this is an aggregate of known size, we should have passed |
2560 | this off to do_structure_copy, and it should have broken it | |
2561 | up. */ | |
c58936b6 | 2562 | gcc_assert (!AGGREGATE_TYPE_P (pointedtotype) |
910fdc79 | 2563 | || get_varinfo (rhs.var)->is_unknown_size_var); |
c58936b6 | 2564 | |
7b765bed DB |
2565 | process_constraint_1 (new_constraint (tmplhs, rhs), from_call); |
2566 | process_constraint_1 (new_constraint (lhs, tmplhs), from_call); | |
2567 | } | |
2568 | else if (rhs.type == ADDRESSOF && lhs.type == DEREF) | |
2569 | { | |
2570 | /* Split into tmp = &rhs, *lhs = tmp */ | |
2571 | tree rhsdecl = get_varinfo (rhs.var)->decl; | |
2572 | tree pointertype = TREE_TYPE (rhsdecl); | |
2573 | tree tmpvar = create_tmp_var_raw (pointertype, "derefaddrtmp"); | |
2574 | struct constraint_expr tmplhs = get_constraint_exp_from_ssa_var (tmpvar); | |
2575 | ||
2576 | process_constraint_1 (new_constraint (tmplhs, rhs), from_call); | |
2577 | process_constraint_1 (new_constraint (lhs, tmplhs), from_call); | |
910fdc79 | 2578 | } |
910fdc79 DB |
2579 | else |
2580 | { | |
3e5937d7 | 2581 | gcc_assert (rhs.type != ADDRESSOF || rhs.offset == 0); |
b5efa470 | 2582 | VEC_safe_push (constraint_t, heap, constraints, t); |
910fdc79 DB |
2583 | } |
2584 | } | |
2585 | ||
7b765bed DB |
2586 | |
2587 | /* Process constraint T, performing various simplifications and then | |
2588 | adding it to our list of overall constraints. */ | |
2589 | ||
2590 | static void | |
2591 | process_constraint (constraint_t t) | |
2592 | { | |
2593 | process_constraint_1 (t, false); | |
2594 | } | |
2595 | ||
21392f19 DB |
2596 | /* Return true if T is a variable of a type that could contain |
2597 | pointers. */ | |
2598 | ||
2599 | static bool | |
2600 | could_have_pointers (tree t) | |
2601 | { | |
2602 | tree type = TREE_TYPE (t); | |
c58936b6 | 2603 | |
6e7e772d DN |
2604 | if (POINTER_TYPE_P (type) |
2605 | || AGGREGATE_TYPE_P (type) | |
21392f19 DB |
2606 | || TREE_CODE (type) == COMPLEX_TYPE) |
2607 | return true; | |
6e7e772d | 2608 | |
21392f19 DB |
2609 | return false; |
2610 | } | |
910fdc79 DB |
2611 | |
2612 | /* Return the position, in bits, of FIELD_DECL from the beginning of its | |
2613 | structure. */ | |
2614 | ||
2615 | static unsigned HOST_WIDE_INT | |
2616 | bitpos_of_field (const tree fdecl) | |
2617 | { | |
2618 | ||
2619 | if (TREE_CODE (DECL_FIELD_OFFSET (fdecl)) != INTEGER_CST | |
2620 | || TREE_CODE (DECL_FIELD_BIT_OFFSET (fdecl)) != INTEGER_CST) | |
2621 | return -1; | |
c58936b6 DB |
2622 | |
2623 | return (tree_low_cst (DECL_FIELD_OFFSET (fdecl), 1) * 8) | |
2624 | + tree_low_cst (DECL_FIELD_BIT_OFFSET (fdecl), 1); | |
910fdc79 DB |
2625 | } |
2626 | ||
2627 | ||
2628 | /* Given a COMPONENT_REF T, return the constraint_expr for it. */ | |
2629 | ||
4ee00913 | 2630 | static void |
1d85354c | 2631 | get_constraint_for_component_ref (tree t, VEC(ce_s, heap) **results) |
910fdc79 | 2632 | { |
4ee00913 | 2633 | tree orig_t = t; |
b1347638 | 2634 | HOST_WIDE_INT bitsize = -1; |
6bec9271 | 2635 | HOST_WIDE_INT bitmaxsize = -1; |
910fdc79 | 2636 | HOST_WIDE_INT bitpos; |
910fdc79 | 2637 | tree forzero; |
4ee00913 DB |
2638 | struct constraint_expr *result; |
2639 | unsigned int beforelength = VEC_length (ce_s, *results); | |
910fdc79 DB |
2640 | |
2641 | /* Some people like to do cute things like take the address of | |
2642 | &0->a.b */ | |
2643 | forzero = t; | |
2644 | while (!SSA_VAR_P (forzero) && !CONSTANT_CLASS_P (forzero)) | |
4ee00913 | 2645 | forzero = TREE_OPERAND (forzero, 0); |
910fdc79 | 2646 | |
c58936b6 | 2647 | if (CONSTANT_CLASS_P (forzero) && integer_zerop (forzero)) |
910fdc79 | 2648 | { |
4ee00913 | 2649 | struct constraint_expr temp; |
c58936b6 | 2650 | |
4ee00913 DB |
2651 | temp.offset = 0; |
2652 | temp.var = integer_id; | |
2653 | temp.type = SCALAR; | |
2654 | VEC_safe_push (ce_s, heap, *results, &temp); | |
2655 | return; | |
910fdc79 | 2656 | } |
c58936b6 | 2657 | |
6bec9271 | 2658 | t = get_ref_base_and_extent (t, &bitpos, &bitsize, &bitmaxsize); |
21392f19 | 2659 | |
1d85354c | 2660 | get_constraint_for (t, results); |
4ee00913 | 2661 | result = VEC_last (ce_s, *results); |
a555a02c | 2662 | result->offset = bitpos; |
4ee00913 DB |
2663 | |
2664 | gcc_assert (beforelength + 1 == VEC_length (ce_s, *results)); | |
910fdc79 DB |
2665 | |
2666 | /* This can also happen due to weird offsetof type macros. */ | |
4ee00913 DB |
2667 | if (TREE_CODE (t) != ADDR_EXPR && result->type == ADDRESSOF) |
2668 | result->type = SCALAR; | |
c58936b6 | 2669 | |
4ee00913 | 2670 | if (result->type == SCALAR) |
910fdc79 DB |
2671 | { |
2672 | /* In languages like C, you can access one past the end of an | |
2673 | array. You aren't allowed to dereference it, so we can | |
2674 | ignore this constraint. When we handle pointer subtraction, | |
2675 | we may have to do something cute here. */ | |
c58936b6 | 2676 | |
18455d17 RG |
2677 | if (result->offset < get_varinfo (result->var)->fullsize |
2678 | && bitmaxsize != 0) | |
dd68d988 DB |
2679 | { |
2680 | /* It's also not true that the constraint will actually start at the | |
2681 | right offset, it may start in some padding. We only care about | |
2682 | setting the constraint to the first actual field it touches, so | |
c58936b6 | 2683 | walk to find it. */ |
dd68d988 | 2684 | varinfo_t curr; |
4ee00913 | 2685 | for (curr = get_varinfo (result->var); curr; curr = curr->next) |
dd68d988 | 2686 | { |
63d195d5 RG |
2687 | if (ranges_overlap_p (curr->offset, curr->size, |
2688 | result->offset, bitmaxsize)) | |
dd68d988 | 2689 | { |
4ee00913 | 2690 | result->var = curr->id; |
dd68d988 | 2691 | break; |
dd68d988 DB |
2692 | } |
2693 | } | |
2694 | /* assert that we found *some* field there. The user couldn't be | |
2695 | accessing *only* padding. */ | |
4ee00913 DB |
2696 | /* Still the user could access one past the end of an array |
2697 | embedded in a struct resulting in accessing *only* padding. */ | |
2698 | gcc_assert (curr || ref_contains_array_ref (orig_t)); | |
dd68d988 | 2699 | } |
18455d17 RG |
2700 | else if (bitmaxsize == 0) |
2701 | { | |
2702 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
2703 | fprintf (dump_file, "Access to zero-sized part of variable," | |
2704 | "ignoring\n"); | |
2705 | } | |
910fdc79 DB |
2706 | else |
2707 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
2708 | fprintf (dump_file, "Access to past the end of variable, ignoring\n"); | |
2709 | ||
4ee00913 | 2710 | result->offset = 0; |
910fdc79 | 2711 | } |
7b765bed DB |
2712 | else if (bitmaxsize == -1) |
2713 | { | |
2714 | /* We can't handle DEREF constraints with unknown size, we'll | |
2715 | get the wrong answer. Punt and return anything. */ | |
2716 | result->var = anything_id; | |
2717 | result->offset = 0; | |
2718 | } | |
910fdc79 DB |
2719 | } |
2720 | ||
2721 | ||
2722 | /* Dereference the constraint expression CONS, and return the result. | |
2723 | DEREF (ADDRESSOF) = SCALAR | |
2724 | DEREF (SCALAR) = DEREF | |
2725 | DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp)) | |
2726 | This is needed so that we can handle dereferencing DEREF constraints. */ | |
2727 | ||
4ee00913 DB |
2728 | static void |
2729 | do_deref (VEC (ce_s, heap) **constraints) | |
910fdc79 | 2730 | { |
4ee00913 DB |
2731 | struct constraint_expr *c; |
2732 | unsigned int i = 0; | |
c58936b6 | 2733 | |
4ee00913 | 2734 | for (i = 0; VEC_iterate (ce_s, *constraints, i, c); i++) |
910fdc79 | 2735 | { |
4ee00913 DB |
2736 | if (c->type == SCALAR) |
2737 | c->type = DEREF; | |
2738 | else if (c->type == ADDRESSOF) | |
2739 | c->type = SCALAR; | |
2740 | else if (c->type == DEREF) | |
2741 | { | |
2742 | tree tmpvar = create_tmp_var_raw (ptr_type_node, "dereftmp"); | |
2743 | struct constraint_expr tmplhs = get_constraint_exp_from_ssa_var (tmpvar); | |
2744 | process_constraint (new_constraint (tmplhs, *c)); | |
2745 | c->var = tmplhs.var; | |
2746 | } | |
2747 | else | |
2748 | gcc_unreachable (); | |
910fdc79 | 2749 | } |
910fdc79 DB |
2750 | } |
2751 | ||
910fdc79 DB |
2752 | /* Given a tree T, return the constraint expression for it. */ |
2753 | ||
4ee00913 | 2754 | static void |
1d85354c | 2755 | get_constraint_for (tree t, VEC (ce_s, heap) **results) |
910fdc79 DB |
2756 | { |
2757 | struct constraint_expr temp; | |
2758 | ||
2759 | /* x = integer is all glommed to a single variable, which doesn't | |
2760 | point to anything by itself. That is, of course, unless it is an | |
2761 | integer constant being treated as a pointer, in which case, we | |
2762 | will return that this is really the addressof anything. This | |
2763 | happens below, since it will fall into the default case. The only | |
2764 | case we know something about an integer treated like a pointer is | |
2765 | when it is the NULL pointer, and then we just say it points to | |
2766 | NULL. */ | |
2767 | if (TREE_CODE (t) == INTEGER_CST | |
7b765bed | 2768 | && integer_zerop (t)) |
910fdc79 DB |
2769 | { |
2770 | temp.var = nothing_id; | |
2771 | temp.type = ADDRESSOF; | |
2772 | temp.offset = 0; | |
4ee00913 DB |
2773 | VEC_safe_push (ce_s, heap, *results, &temp); |
2774 | return; | |
910fdc79 DB |
2775 | } |
2776 | ||
bd1f29d9 EB |
2777 | /* String constants are read-only. */ |
2778 | if (TREE_CODE (t) == STRING_CST) | |
2779 | { | |
2780 | temp.var = readonly_id; | |
2781 | temp.type = SCALAR; | |
2782 | temp.offset = 0; | |
2783 | VEC_safe_push (ce_s, heap, *results, &temp); | |
2784 | return; | |
2785 | } | |
2786 | ||
910fdc79 DB |
2787 | switch (TREE_CODE_CLASS (TREE_CODE (t))) |
2788 | { | |
2789 | case tcc_expression: | |
5039610b | 2790 | case tcc_vl_exp: |
910fdc79 DB |
2791 | { |
2792 | switch (TREE_CODE (t)) | |
2793 | { | |
2794 | case ADDR_EXPR: | |
2795 | { | |
4ee00913 DB |
2796 | struct constraint_expr *c; |
2797 | unsigned int i; | |
a916f21d | 2798 | tree exp = TREE_OPERAND (t, 0); |
6df11ca1 | 2799 | tree pttype = TREE_TYPE (TREE_TYPE (t)); |
a916f21d RG |
2800 | |
2801 | get_constraint_for (exp, results); | |
6e7e772d | 2802 | |
c58936b6 | 2803 | |
7b765bed DB |
2804 | /* Complex types are special. Taking the address of one |
2805 | allows you to access either part of it through that | |
2806 | pointer. */ | |
2807 | if (VEC_length (ce_s, *results) == 1 && | |
2808 | TREE_CODE (pttype) == COMPLEX_TYPE) | |
6df11ca1 DB |
2809 | { |
2810 | struct constraint_expr *origrhs; | |
2811 | varinfo_t origvar; | |
2812 | struct constraint_expr tmp; | |
2813 | ||
2814 | gcc_assert (VEC_length (ce_s, *results) == 1); | |
2815 | origrhs = VEC_last (ce_s, *results); | |
2816 | tmp = *origrhs; | |
2817 | VEC_pop (ce_s, *results); | |
2818 | origvar = get_varinfo (origrhs->var); | |
2819 | for (; origvar; origvar = origvar->next) | |
2820 | { | |
2821 | tmp.var = origvar->id; | |
2822 | VEC_safe_push (ce_s, heap, *results, &tmp); | |
2823 | } | |
2824 | } | |
c58936b6 | 2825 | |
4ee00913 DB |
2826 | for (i = 0; VEC_iterate (ce_s, *results, i, c); i++) |
2827 | { | |
2828 | if (c->type == DEREF) | |
2829 | c->type = SCALAR; | |
c58936b6 | 2830 | else |
4ee00913 DB |
2831 | c->type = ADDRESSOF; |
2832 | } | |
2833 | return; | |
910fdc79 DB |
2834 | } |
2835 | break; | |
2836 | case CALL_EXPR: | |
910fdc79 DB |
2837 | /* XXX: In interprocedural mode, if we didn't have the |
2838 | body, we would need to do *each pointer argument = | |
2839 | &ANYTHING added. */ | |
2840 | if (call_expr_flags (t) & (ECF_MALLOC | ECF_MAY_BE_ALLOCA)) | |
2841 | { | |
e8ca4159 | 2842 | varinfo_t vi; |
c900f6aa | 2843 | tree heapvar = heapvar_lookup (t); |
c58936b6 | 2844 | |
c900f6aa | 2845 | if (heapvar == NULL) |
c58936b6 | 2846 | { |
c900f6aa DB |
2847 | heapvar = create_tmp_var_raw (ptr_type_node, "HEAP"); |
2848 | DECL_EXTERNAL (heapvar) = 1; | |
ae536040 | 2849 | get_var_ann (heapvar)->is_heapvar = 1; |
5cd4ec7f | 2850 | if (gimple_referenced_vars (cfun)) |
f004ab02 | 2851 | add_referenced_var (heapvar); |
c900f6aa DB |
2852 | heapvar_insert (t, heapvar); |
2853 | } | |
2854 | ||
910fdc79 DB |
2855 | temp.var = create_variable_info_for (heapvar, |
2856 | alias_get_name (heapvar)); | |
c58936b6 | 2857 | |
e8ca4159 DN |
2858 | vi = get_varinfo (temp.var); |
2859 | vi->is_artificial_var = 1; | |
2860 | vi->is_heap_var = 1; | |
3e5937d7 | 2861 | temp.type = ADDRESSOF; |
910fdc79 | 2862 | temp.offset = 0; |
4ee00913 DB |
2863 | VEC_safe_push (ce_s, heap, *results, &temp); |
2864 | return; | |
910fdc79 | 2865 | } |
21392f19 DB |
2866 | else |
2867 | { | |
c58936b6 | 2868 | temp.var = anything_id; |
21392f19 DB |
2869 | temp.type = SCALAR; |
2870 | temp.offset = 0; | |
2871 | VEC_safe_push (ce_s, heap, *results, &temp); | |
2872 | return; | |
2873 | } | |
2874 | break; | |
910fdc79 DB |
2875 | default: |
2876 | { | |
2877 | temp.type = ADDRESSOF; | |
2878 | temp.var = anything_id; | |
2879 | temp.offset = 0; | |
4ee00913 DB |
2880 | VEC_safe_push (ce_s, heap, *results, &temp); |
2881 | return; | |
910fdc79 DB |
2882 | } |
2883 | } | |
2884 | } | |
2885 | case tcc_reference: | |
2886 | { | |
2887 | switch (TREE_CODE (t)) | |
2888 | { | |
2889 | case INDIRECT_REF: | |
2890 | { | |
1d85354c | 2891 | get_constraint_for (TREE_OPERAND (t, 0), results); |
4ee00913 DB |
2892 | do_deref (results); |
2893 | return; | |
910fdc79 DB |
2894 | } |
2895 | case ARRAY_REF: | |
32961db5 | 2896 | case ARRAY_RANGE_REF: |
910fdc79 | 2897 | case COMPONENT_REF: |
1d85354c | 2898 | get_constraint_for_component_ref (t, results); |
4ee00913 | 2899 | return; |
910fdc79 DB |
2900 | default: |
2901 | { | |
2902 | temp.type = ADDRESSOF; | |
2903 | temp.var = anything_id; | |
2904 | temp.offset = 0; | |
4ee00913 DB |
2905 | VEC_safe_push (ce_s, heap, *results, &temp); |
2906 | return; | |
910fdc79 DB |
2907 | } |
2908 | } | |
2909 | } | |
2910 | case tcc_unary: | |
2911 | { | |
2912 | switch (TREE_CODE (t)) | |
2913 | { | |
1043771b | 2914 | CASE_CONVERT: |
910fdc79 DB |
2915 | { |
2916 | tree op = TREE_OPERAND (t, 0); | |
c58936b6 | 2917 | |
910fdc79 DB |
2918 | /* Cast from non-pointer to pointers are bad news for us. |
2919 | Anything else, we see through */ | |
e8ca4159 DN |
2920 | if (!(POINTER_TYPE_P (TREE_TYPE (t)) |
2921 | && ! POINTER_TYPE_P (TREE_TYPE (op)))) | |
4ee00913 | 2922 | { |
1d85354c | 2923 | get_constraint_for (op, results); |
4ee00913 DB |
2924 | return; |
2925 | } | |
e8ca4159 DN |
2926 | |
2927 | /* FALLTHRU */ | |
910fdc79 DB |
2928 | } |
2929 | default: | |
2930 | { | |
2931 | temp.type = ADDRESSOF; | |
2932 | temp.var = anything_id; | |
2933 | temp.offset = 0; | |
4ee00913 DB |
2934 | VEC_safe_push (ce_s, heap, *results, &temp); |
2935 | return; | |
910fdc79 DB |
2936 | } |
2937 | } | |
2938 | } | |
2939 | case tcc_exceptional: | |
2940 | { | |
2941 | switch (TREE_CODE (t)) | |
2942 | { | |
c58936b6 | 2943 | case PHI_NODE: |
4ee00913 | 2944 | { |
1d85354c | 2945 | get_constraint_for (PHI_RESULT (t), results); |
4ee00913 DB |
2946 | return; |
2947 | } | |
2948 | break; | |
910fdc79 | 2949 | case SSA_NAME: |
4ee00913 DB |
2950 | { |
2951 | struct constraint_expr temp; | |
2952 | temp = get_constraint_exp_from_ssa_var (t); | |
2953 | VEC_safe_push (ce_s, heap, *results, &temp); | |
2954 | return; | |
2955 | } | |
2956 | break; | |
910fdc79 DB |
2957 | default: |
2958 | { | |
2959 | temp.type = ADDRESSOF; | |
2960 | temp.var = anything_id; | |
2961 | temp.offset = 0; | |
4ee00913 DB |
2962 | VEC_safe_push (ce_s, heap, *results, &temp); |
2963 | return; | |
910fdc79 DB |
2964 | } |
2965 | } | |
2966 | } | |
2967 | case tcc_declaration: | |
4ee00913 DB |
2968 | { |
2969 | struct constraint_expr temp; | |
2970 | temp = get_constraint_exp_from_ssa_var (t); | |
2971 | VEC_safe_push (ce_s, heap, *results, &temp); | |
2972 | return; | |
2973 | } | |
910fdc79 DB |
2974 | default: |
2975 | { | |
2976 | temp.type = ADDRESSOF; | |
2977 | temp.var = anything_id; | |
2978 | temp.offset = 0; | |
4ee00913 DB |
2979 | VEC_safe_push (ce_s, heap, *results, &temp); |
2980 | return; | |
910fdc79 DB |
2981 | } |
2982 | } | |
2983 | } | |
2984 | ||
2985 | ||
2986 | /* Handle the structure copy case where we have a simple structure copy | |
c58936b6 DB |
2987 | between LHS and RHS that is of SIZE (in bits) |
2988 | ||
910fdc79 DB |
2989 | For each field of the lhs variable (lhsfield) |
2990 | For each field of the rhs variable at lhsfield.offset (rhsfield) | |
2991 | add the constraint lhsfield = rhsfield | |
910fdc79 | 2992 | |
03190594 DB |
2993 | If we fail due to some kind of type unsafety or other thing we |
2994 | can't handle, return false. We expect the caller to collapse the | |
2995 | variable in that case. */ | |
2996 | ||
2997 | static bool | |
910fdc79 DB |
2998 | do_simple_structure_copy (const struct constraint_expr lhs, |
2999 | const struct constraint_expr rhs, | |
3000 | const unsigned HOST_WIDE_INT size) | |
3001 | { | |
3002 | varinfo_t p = get_varinfo (lhs.var); | |
a5eadacc | 3003 | unsigned HOST_WIDE_INT pstart, last; |
910fdc79 DB |
3004 | pstart = p->offset; |
3005 | last = p->offset + size; | |
3006 | for (; p && p->offset < last; p = p->next) | |
3007 | { | |
3008 | varinfo_t q; | |
3009 | struct constraint_expr templhs = lhs; | |
3010 | struct constraint_expr temprhs = rhs; | |
3011 | unsigned HOST_WIDE_INT fieldoffset; | |
3012 | ||
c58936b6 | 3013 | templhs.var = p->id; |
910fdc79 DB |
3014 | q = get_varinfo (temprhs.var); |
3015 | fieldoffset = p->offset - pstart; | |
3016 | q = first_vi_for_offset (q, q->offset + fieldoffset); | |
03190594 DB |
3017 | if (!q) |
3018 | return false; | |
910fdc79 DB |
3019 | temprhs.var = q->id; |
3020 | process_constraint (new_constraint (templhs, temprhs)); | |
3021 | } | |
03190594 | 3022 | return true; |
910fdc79 DB |
3023 | } |
3024 | ||
3025 | ||
3026 | /* Handle the structure copy case where we have a structure copy between a | |
3027 | aggregate on the LHS and a dereference of a pointer on the RHS | |
c58936b6 DB |
3028 | that is of SIZE (in bits) |
3029 | ||
910fdc79 DB |
3030 | For each field of the lhs variable (lhsfield) |
3031 | rhs.offset = lhsfield->offset | |
3032 | add the constraint lhsfield = rhs | |
3033 | */ | |
3034 | ||
3035 | static void | |
3036 | do_rhs_deref_structure_copy (const struct constraint_expr lhs, | |
3037 | const struct constraint_expr rhs, | |
3038 | const unsigned HOST_WIDE_INT size) | |
3039 | { | |
3040 | varinfo_t p = get_varinfo (lhs.var); | |
3041 | unsigned HOST_WIDE_INT pstart,last; | |
3042 | pstart = p->offset; | |
3043 | last = p->offset + size; | |
3044 | ||
3045 | for (; p && p->offset < last; p = p->next) | |
3046 | { | |
3047 | varinfo_t q; | |
3048 | struct constraint_expr templhs = lhs; | |
3049 | struct constraint_expr temprhs = rhs; | |
3050 | unsigned HOST_WIDE_INT fieldoffset; | |
3051 | ||
3052 | ||
3053 | if (templhs.type == SCALAR) | |
c58936b6 | 3054 | templhs.var = p->id; |
910fdc79 DB |
3055 | else |
3056 | templhs.offset = p->offset; | |
c58936b6 | 3057 | |
910fdc79 | 3058 | q = get_varinfo (temprhs.var); |
c58936b6 | 3059 | fieldoffset = p->offset - pstart; |
910fdc79 DB |
3060 | temprhs.offset += fieldoffset; |
3061 | process_constraint (new_constraint (templhs, temprhs)); | |
3062 | } | |
3063 | } | |
3064 | ||
3065 | /* Handle the structure copy case where we have a structure copy | |
110abdbc | 3066 | between an aggregate on the RHS and a dereference of a pointer on |
c58936b6 | 3067 | the LHS that is of SIZE (in bits) |
910fdc79 DB |
3068 | |
3069 | For each field of the rhs variable (rhsfield) | |
3070 | lhs.offset = rhsfield->offset | |
3071 | add the constraint lhs = rhsfield | |
3072 | */ | |
3073 | ||
3074 | static void | |
3075 | do_lhs_deref_structure_copy (const struct constraint_expr lhs, | |
3076 | const struct constraint_expr rhs, | |
3077 | const unsigned HOST_WIDE_INT size) | |
3078 | { | |
3079 | varinfo_t p = get_varinfo (rhs.var); | |
3080 | unsigned HOST_WIDE_INT pstart,last; | |
3081 | pstart = p->offset; | |
3082 | last = p->offset + size; | |
3083 | ||
3084 | for (; p && p->offset < last; p = p->next) | |
3085 | { | |
3086 | varinfo_t q; | |
3087 | struct constraint_expr templhs = lhs; | |
3088 | struct constraint_expr temprhs = rhs; | |
3089 | unsigned HOST_WIDE_INT fieldoffset; | |
3090 | ||
3091 | ||
3092 | if (temprhs.type == SCALAR) | |
c58936b6 | 3093 | temprhs.var = p->id; |
910fdc79 DB |
3094 | else |
3095 | temprhs.offset = p->offset; | |
c58936b6 | 3096 | |
910fdc79 | 3097 | q = get_varinfo (templhs.var); |
c58936b6 | 3098 | fieldoffset = p->offset - pstart; |
910fdc79 DB |
3099 | templhs.offset += fieldoffset; |
3100 | process_constraint (new_constraint (templhs, temprhs)); | |
3101 | } | |
3102 | } | |
3103 | ||
03190594 DB |
3104 | /* Sometimes, frontends like to give us bad type information. This |
3105 | function will collapse all the fields from VAR to the end of VAR, | |
c58936b6 | 3106 | into VAR, so that we treat those fields as a single variable. |
03190594 DB |
3107 | We return the variable they were collapsed into. */ |
3108 | ||
3109 | static unsigned int | |
3110 | collapse_rest_of_var (unsigned int var) | |
3111 | { | |
3112 | varinfo_t currvar = get_varinfo (var); | |
3113 | varinfo_t field; | |
3114 | ||
3115 | for (field = currvar->next; field; field = field->next) | |
3116 | { | |
3117 | if (dump_file) | |
c58936b6 | 3118 | fprintf (dump_file, "Type safety: Collapsing var %s into %s\n", |
03190594 | 3119 | field->name, currvar->name); |
c58936b6 | 3120 | |
03190594 DB |
3121 | gcc_assert (!field->collapsed_to); |
3122 | field->collapsed_to = currvar; | |
3123 | } | |
3124 | ||
3125 | currvar->next = NULL; | |
3126 | currvar->size = currvar->fullsize - currvar->offset; | |
c58936b6 | 3127 | |
03190594 DB |
3128 | return currvar->id; |
3129 | } | |
910fdc79 DB |
3130 | |
3131 | /* Handle aggregate copies by expanding into copies of the respective | |
3132 | fields of the structures. */ | |
3133 | ||
3134 | static void | |
3135 | do_structure_copy (tree lhsop, tree rhsop) | |
3136 | { | |
3137 | struct constraint_expr lhs, rhs, tmp; | |
4ee00913 | 3138 | VEC (ce_s, heap) *lhsc = NULL, *rhsc = NULL; |
910fdc79 DB |
3139 | varinfo_t p; |
3140 | unsigned HOST_WIDE_INT lhssize; | |
3141 | unsigned HOST_WIDE_INT rhssize; | |
3142 | ||
1d85354c RG |
3143 | get_constraint_for (lhsop, &lhsc); |
3144 | get_constraint_for (rhsop, &rhsc); | |
4ee00913 DB |
3145 | gcc_assert (VEC_length (ce_s, lhsc) == 1); |
3146 | gcc_assert (VEC_length (ce_s, rhsc) == 1); | |
3147 | lhs = *(VEC_last (ce_s, lhsc)); | |
3148 | rhs = *(VEC_last (ce_s, rhsc)); | |
c58936b6 | 3149 | |
4ee00913 DB |
3150 | VEC_free (ce_s, heap, lhsc); |
3151 | VEC_free (ce_s, heap, rhsc); | |
3152 | ||
910fdc79 | 3153 | /* If we have special var = x, swap it around. */ |
13c2c08b | 3154 | if (lhs.var <= integer_id && !(get_varinfo (rhs.var)->is_special_var)) |
910fdc79 DB |
3155 | { |
3156 | tmp = lhs; | |
3157 | lhs = rhs; | |
3158 | rhs = tmp; | |
3159 | } | |
c58936b6 | 3160 | |
a5eadacc DB |
3161 | /* This is fairly conservative for the RHS == ADDRESSOF case, in that it's |
3162 | possible it's something we could handle. However, most cases falling | |
3163 | into this are dealing with transparent unions, which are slightly | |
3164 | weird. */ | |
13c2c08b | 3165 | if (rhs.type == ADDRESSOF && !(get_varinfo (rhs.var)->is_special_var)) |
a5eadacc DB |
3166 | { |
3167 | rhs.type = ADDRESSOF; | |
3168 | rhs.var = anything_id; | |
3169 | } | |
3170 | ||
3171 | /* If the RHS is a special var, or an addressof, set all the LHS fields to | |
3172 | that special var. */ | |
910fdc79 DB |
3173 | if (rhs.var <= integer_id) |
3174 | { | |
3175 | for (p = get_varinfo (lhs.var); p; p = p->next) | |
3176 | { | |
3177 | struct constraint_expr templhs = lhs; | |
3178 | struct constraint_expr temprhs = rhs; | |
4ee00913 | 3179 | |
910fdc79 DB |
3180 | if (templhs.type == SCALAR ) |
3181 | templhs.var = p->id; | |
3182 | else | |
3183 | templhs.offset += p->offset; | |
3184 | process_constraint (new_constraint (templhs, temprhs)); | |
3185 | } | |
3186 | } | |
3187 | else | |
3188 | { | |
4e422b8b DB |
3189 | tree rhstype = TREE_TYPE (rhsop); |
3190 | tree lhstype = TREE_TYPE (lhsop); | |
4ee00913 DB |
3191 | tree rhstypesize; |
3192 | tree lhstypesize; | |
3193 | ||
3194 | lhstypesize = DECL_P (lhsop) ? DECL_SIZE (lhsop) : TYPE_SIZE (lhstype); | |
3195 | rhstypesize = DECL_P (rhsop) ? DECL_SIZE (rhsop) : TYPE_SIZE (rhstype); | |
4e422b8b DB |
3196 | |
3197 | /* If we have a variably sized types on the rhs or lhs, and a deref | |
3198 | constraint, add the constraint, lhsconstraint = &ANYTHING. | |
3199 | This is conservatively correct because either the lhs is an unknown | |
3200 | sized var (if the constraint is SCALAR), or the lhs is a DEREF | |
3201 | constraint, and every variable it can point to must be unknown sized | |
3202 | anyway, so we don't need to worry about fields at all. */ | |
3203 | if ((rhs.type == DEREF && TREE_CODE (rhstypesize) != INTEGER_CST) | |
3204 | || (lhs.type == DEREF && TREE_CODE (lhstypesize) != INTEGER_CST)) | |
3205 | { | |
3206 | rhs.var = anything_id; | |
3207 | rhs.type = ADDRESSOF; | |
3208 | rhs.offset = 0; | |
3209 | process_constraint (new_constraint (lhs, rhs)); | |
3210 | return; | |
3211 | } | |
3212 | ||
a5eadacc DB |
3213 | /* The size only really matters insofar as we don't set more or less of |
3214 | the variable. If we hit an unknown size var, the size should be the | |
3215 | whole darn thing. */ | |
3216 | if (get_varinfo (rhs.var)->is_unknown_size_var) | |
3217 | rhssize = ~0; | |
3218 | else | |
4e422b8b | 3219 | rhssize = TREE_INT_CST_LOW (rhstypesize); |
a5eadacc DB |
3220 | |
3221 | if (get_varinfo (lhs.var)->is_unknown_size_var) | |
3222 | lhssize = ~0; | |
3223 | else | |
4e422b8b | 3224 | lhssize = TREE_INT_CST_LOW (lhstypesize); |
a5eadacc | 3225 | |
c58936b6 DB |
3226 | |
3227 | if (rhs.type == SCALAR && lhs.type == SCALAR) | |
03190594 DB |
3228 | { |
3229 | if (!do_simple_structure_copy (lhs, rhs, MIN (lhssize, rhssize))) | |
c58936b6 | 3230 | { |
03190594 DB |
3231 | lhs.var = collapse_rest_of_var (lhs.var); |
3232 | rhs.var = collapse_rest_of_var (rhs.var); | |
3233 | lhs.offset = 0; | |
3234 | rhs.offset = 0; | |
3235 | lhs.type = SCALAR; | |
3236 | rhs.type = SCALAR; | |
3237 | process_constraint (new_constraint (lhs, rhs)); | |
3238 | } | |
3239 | } | |
910fdc79 DB |
3240 | else if (lhs.type != DEREF && rhs.type == DEREF) |
3241 | do_rhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize)); | |
3242 | else if (lhs.type == DEREF && rhs.type != DEREF) | |
3243 | do_lhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize)); | |
3244 | else | |
3245 | { | |
4e422b8b | 3246 | tree pointedtotype = lhstype; |
c58936b6 | 3247 | tree tmpvar; |
a5eadacc | 3248 | |
910fdc79 DB |
3249 | gcc_assert (rhs.type == DEREF && lhs.type == DEREF); |
3250 | tmpvar = create_tmp_var_raw (pointedtotype, "structcopydereftmp"); | |
a5eadacc DB |
3251 | do_structure_copy (tmpvar, rhsop); |
3252 | do_structure_copy (lhsop, tmpvar); | |
910fdc79 DB |
3253 | } |
3254 | } | |
3255 | } | |
3256 | ||
6e7e772d | 3257 | |
e8ca4159 DN |
3258 | /* Update related alias information kept in AI. This is used when |
3259 | building name tags, alias sets and deciding grouping heuristics. | |
3260 | STMT is the statement to process. This function also updates | |
3261 | ADDRESSABLE_VARS. */ | |
3262 | ||
3263 | static void | |
3264 | update_alias_info (tree stmt, struct alias_info *ai) | |
3265 | { | |
3266 | bitmap addr_taken; | |
3267 | use_operand_p use_p; | |
e8ca4159 | 3268 | ssa_op_iter iter; |
e9e0aa2c | 3269 | bool stmt_dereferences_ptr_p; |
21392f19 | 3270 | enum escape_type stmt_escape_type = is_escape_site (stmt); |
e9e0aa2c DN |
3271 | struct mem_ref_stats_d *mem_ref_stats = gimple_mem_ref_stats (cfun); |
3272 | ||
3273 | stmt_dereferences_ptr_p = false; | |
e8ca4159 | 3274 | |
21392f19 DB |
3275 | if (stmt_escape_type == ESCAPE_TO_CALL |
3276 | || stmt_escape_type == ESCAPE_TO_PURE_CONST) | |
3277 | { | |
e9e0aa2c | 3278 | mem_ref_stats->num_call_sites++; |
21392f19 | 3279 | if (stmt_escape_type == ESCAPE_TO_PURE_CONST) |
e9e0aa2c | 3280 | mem_ref_stats->num_pure_const_call_sites++; |
21392f19 | 3281 | } |
e9e0aa2c DN |
3282 | else if (stmt_escape_type == ESCAPE_TO_ASM) |
3283 | mem_ref_stats->num_asm_sites++; | |
21392f19 | 3284 | |
e8ca4159 DN |
3285 | /* Mark all the variables whose address are taken by the statement. */ |
3286 | addr_taken = addresses_taken (stmt); | |
3287 | if (addr_taken) | |
3288 | { | |
5cd4ec7f | 3289 | bitmap_ior_into (gimple_addressable_vars (cfun), addr_taken); |
e8ca4159 DN |
3290 | |
3291 | /* If STMT is an escape point, all the addresses taken by it are | |
3292 | call-clobbered. */ | |
d16a5e36 | 3293 | if (stmt_escape_type != NO_ESCAPE) |
e8ca4159 | 3294 | { |
3b302421 RG |
3295 | bitmap_iterator bi; |
3296 | unsigned i; | |
e8ca4159 | 3297 | |
3b302421 | 3298 | EXECUTE_IF_SET_IN_BITMAP (addr_taken, 0, i, bi) |
d16a5e36 | 3299 | { |
3b302421 | 3300 | tree rvar = referenced_var (i); |
d16a5e36 DB |
3301 | if (!unmodifiable_var_p (rvar)) |
3302 | mark_call_clobbered (rvar, stmt_escape_type); | |
3303 | } | |
e8ca4159 DN |
3304 | } |
3305 | } | |
3306 | ||
e9e0aa2c DN |
3307 | /* Process each operand use. For pointers, determine whether they |
3308 | are dereferenced by the statement, or whether their value | |
3309 | escapes, etc. */ | |
e8ca4159 DN |
3310 | FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE) |
3311 | { | |
3312 | tree op, var; | |
3313 | var_ann_t v_ann; | |
3314 | struct ptr_info_def *pi; | |
e9e0aa2c | 3315 | unsigned num_uses, num_loads, num_stores; |
e8ca4159 DN |
3316 | |
3317 | op = USE_FROM_PTR (use_p); | |
3318 | ||
3319 | /* If STMT is a PHI node, OP may be an ADDR_EXPR. If so, add it | |
3320 | to the set of addressable variables. */ | |
3321 | if (TREE_CODE (op) == ADDR_EXPR) | |
3322 | { | |
5cd4ec7f JH |
3323 | bitmap addressable_vars = gimple_addressable_vars (cfun); |
3324 | ||
e8ca4159 | 3325 | gcc_assert (TREE_CODE (stmt) == PHI_NODE); |
5cd4ec7f | 3326 | gcc_assert (addressable_vars); |
e8ca4159 DN |
3327 | |
3328 | /* PHI nodes don't have annotations for pinning the set | |
3329 | of addresses taken, so we collect them here. | |
3330 | ||
3331 | FIXME, should we allow PHI nodes to have annotations | |
3332 | so that they can be treated like regular statements? | |
3333 | Currently, they are treated as second-class | |
3334 | statements. */ | |
e9e0aa2c | 3335 | add_to_addressable_set (TREE_OPERAND (op, 0), &addressable_vars); |
e8ca4159 DN |
3336 | continue; |
3337 | } | |
3338 | ||
e9e0aa2c | 3339 | /* Ignore constants (they may occur in PHI node arguments). */ |
e8ca4159 DN |
3340 | if (TREE_CODE (op) != SSA_NAME) |
3341 | continue; | |
3342 | ||
3343 | var = SSA_NAME_VAR (op); | |
3344 | v_ann = var_ann (var); | |
3345 | ||
38635499 | 3346 | /* The base variable of an SSA name must be a GIMPLE register, and thus |
fd0bd278 ZD |
3347 | it cannot be aliased. */ |
3348 | gcc_assert (!may_be_aliased (var)); | |
e8ca4159 DN |
3349 | |
3350 | /* We are only interested in pointers. */ | |
3351 | if (!POINTER_TYPE_P (TREE_TYPE (op))) | |
3352 | continue; | |
3353 | ||
3354 | pi = get_ptr_info (op); | |
3355 | ||
3356 | /* Add OP to AI->PROCESSED_PTRS, if it's not there already. */ | |
3357 | if (!TEST_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (op))) | |
3358 | { | |
3359 | SET_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (op)); | |
d96f49bf | 3360 | VEC_safe_push (tree, heap, ai->processed_ptrs, op); |
e8ca4159 DN |
3361 | } |
3362 | ||
3363 | /* If STMT is a PHI node, then it will not have pointer | |
3364 | dereferences and it will not be an escape point. */ | |
3365 | if (TREE_CODE (stmt) == PHI_NODE) | |
3366 | continue; | |
3367 | ||
3368 | /* Determine whether OP is a dereferenced pointer, and if STMT | |
3369 | is an escape point, whether OP escapes. */ | |
e9e0aa2c | 3370 | count_uses_and_derefs (op, stmt, &num_uses, &num_loads, &num_stores); |
e8ca4159 | 3371 | |
17c7e33e DN |
3372 | /* Handle a corner case involving address expressions of the |
3373 | form '&PTR->FLD'. The problem with these expressions is that | |
3374 | they do not represent a dereference of PTR. However, if some | |
3375 | other transformation propagates them into an INDIRECT_REF | |
3376 | expression, we end up with '*(&PTR->FLD)' which is folded | |
3377 | into 'PTR->FLD'. | |
3378 | ||
3379 | So, if the original code had no other dereferences of PTR, | |
3380 | the aliaser will not create memory tags for it, and when | |
3381 | &PTR->FLD gets propagated to INDIRECT_REF expressions, the | |
38635499 | 3382 | memory operations will receive no VDEF/VUSE operands. |
17c7e33e DN |
3383 | |
3384 | One solution would be to have count_uses_and_derefs consider | |
3385 | &PTR->FLD a dereference of PTR. But that is wrong, since it | |
3386 | is not really a dereference but an offset calculation. | |
3387 | ||
3388 | What we do here is to recognize these special ADDR_EXPR | |
3389 | nodes. Since these expressions are never GIMPLE values (they | |
3390 | are not GIMPLE invariants), they can only appear on the RHS | |
3391 | of an assignment and their base address is always an | |
3392 | INDIRECT_REF expression. */ | |
07beea0d AH |
3393 | if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT |
3394 | && TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1)) == ADDR_EXPR | |
3395 | && !is_gimple_val (GIMPLE_STMT_OPERAND (stmt, 1))) | |
17c7e33e DN |
3396 | { |
3397 | /* If the RHS if of the form &PTR->FLD and PTR == OP, then | |
3398 | this represents a potential dereference of PTR. */ | |
07beea0d | 3399 | tree rhs = GIMPLE_STMT_OPERAND (stmt, 1); |
17c7e33e DN |
3400 | tree base = get_base_address (TREE_OPERAND (rhs, 0)); |
3401 | if (TREE_CODE (base) == INDIRECT_REF | |
3402 | && TREE_OPERAND (base, 0) == op) | |
e9e0aa2c | 3403 | num_loads++; |
17c7e33e DN |
3404 | } |
3405 | ||
e9e0aa2c | 3406 | if (num_loads + num_stores > 0) |
e8ca4159 DN |
3407 | { |
3408 | /* Mark OP as dereferenced. In a subsequent pass, | |
3409 | dereferenced pointers that point to a set of | |
3410 | variables will be assigned a name tag to alias | |
3411 | all the variables OP points to. */ | |
3412 | pi->is_dereferenced = 1; | |
3413 | ||
e8ca4159 DN |
3414 | /* If this is a store operation, mark OP as being |
3415 | dereferenced to store, otherwise mark it as being | |
3416 | dereferenced to load. */ | |
e9e0aa2c | 3417 | if (num_stores > 0) |
38635499 | 3418 | pointer_set_insert (ai->dereferenced_ptrs_store, var); |
e8ca4159 | 3419 | else |
38635499 | 3420 | pointer_set_insert (ai->dereferenced_ptrs_load, var); |
e9e0aa2c DN |
3421 | |
3422 | /* Update the frequency estimate for all the dereferences of | |
3423 | pointer OP. */ | |
3424 | update_mem_sym_stats_from_stmt (op, stmt, num_loads, num_stores); | |
7b765bed | 3425 | |
e9e0aa2c DN |
3426 | /* Indicate that STMT contains pointer dereferences. */ |
3427 | stmt_dereferences_ptr_p = true; | |
e8ca4159 DN |
3428 | } |
3429 | ||
e9e0aa2c | 3430 | if (stmt_escape_type != NO_ESCAPE && num_loads + num_stores < num_uses) |
e8ca4159 DN |
3431 | { |
3432 | /* If STMT is an escape point and STMT contains at | |
3433 | least one direct use of OP, then the value of OP | |
3434 | escapes and so the pointed-to variables need to | |
3435 | be marked call-clobbered. */ | |
3436 | pi->value_escapes_p = 1; | |
d16a5e36 | 3437 | pi->escape_mask |= stmt_escape_type; |
e8ca4159 DN |
3438 | |
3439 | /* If the statement makes a function call, assume | |
3440 | that pointer OP will be dereferenced in a store | |
3441 | operation inside the called function. */ | |
c58936b6 DB |
3442 | if (get_call_expr_in (stmt) |
3443 | || stmt_escape_type == ESCAPE_STORED_IN_GLOBAL) | |
e8ca4159 | 3444 | { |
38635499 | 3445 | pointer_set_insert (ai->dereferenced_ptrs_store, var); |
e8ca4159 DN |
3446 | pi->is_dereferenced = 1; |
3447 | } | |
3448 | } | |
3449 | } | |
3450 | ||
0bfac35f DB |
3451 | if (TREE_CODE (stmt) == PHI_NODE) |
3452 | return; | |
3453 | ||
38635499 | 3454 | /* Mark stored variables in STMT as being written to and update the |
e9e0aa2c DN |
3455 | memory reference stats for all memory symbols referenced by STMT. */ |
3456 | if (stmt_references_memory_p (stmt)) | |
e8ca4159 | 3457 | { |
3b302421 RG |
3458 | unsigned i; |
3459 | bitmap_iterator bi; | |
e9e0aa2c DN |
3460 | |
3461 | mem_ref_stats->num_mem_stmts++; | |
3462 | ||
3463 | /* Notice that we only update memory reference stats for symbols | |
3464 | loaded and stored by the statement if the statement does not | |
3465 | contain pointer dereferences and it is not a call/asm site. | |
3466 | This is to avoid double accounting problems when creating | |
3467 | memory partitions. After computing points-to information, | |
3468 | pointer dereference statistics are used to update the | |
3469 | reference stats of the pointed-to variables, so here we | |
3470 | should only update direct references to symbols. | |
3471 | ||
3472 | Indirect references are not updated here for two reasons: (1) | |
3473 | The first time we compute alias information, the sets | |
3474 | LOADED/STORED are empty for pointer dereferences, (2) After | |
3475 | partitioning, LOADED/STORED may have references to | |
3476 | partitions, not the original pointed-to variables. So, if we | |
3477 | always counted LOADED/STORED here and during partitioning, we | |
3478 | would count many symbols more than once. | |
3479 | ||
3480 | This does cause some imprecision when a statement has a | |
3481 | combination of direct symbol references and pointer | |
3482 | dereferences (e.g., MEMORY_VAR = *PTR) or if a call site has | |
3483 | memory symbols in its argument list, but these cases do not | |
7fa7289d | 3484 | occur so frequently as to constitute a serious problem. */ |
e9e0aa2c | 3485 | if (STORED_SYMS (stmt)) |
3b302421 | 3486 | EXECUTE_IF_SET_IN_BITMAP (STORED_SYMS (stmt), 0, i, bi) |
e9e0aa2c | 3487 | { |
3b302421 | 3488 | tree sym = referenced_var (i); |
e9e0aa2c DN |
3489 | pointer_set_insert (ai->written_vars, sym); |
3490 | if (!stmt_dereferences_ptr_p | |
3491 | && stmt_escape_type != ESCAPE_TO_CALL | |
3492 | && stmt_escape_type != ESCAPE_TO_PURE_CONST | |
3493 | && stmt_escape_type != ESCAPE_TO_ASM) | |
3494 | update_mem_sym_stats_from_stmt (sym, stmt, 0, 1); | |
3495 | } | |
3496 | ||
3497 | if (!stmt_dereferences_ptr_p | |
3498 | && LOADED_SYMS (stmt) | |
3499 | && stmt_escape_type != ESCAPE_TO_CALL | |
3500 | && stmt_escape_type != ESCAPE_TO_PURE_CONST | |
3501 | && stmt_escape_type != ESCAPE_TO_ASM) | |
3b302421 RG |
3502 | EXECUTE_IF_SET_IN_BITMAP (LOADED_SYMS (stmt), 0, i, bi) |
3503 | update_mem_sym_stats_from_stmt (referenced_var (i), stmt, 1, 0); | |
e8ca4159 DN |
3504 | } |
3505 | } | |
3506 | ||
3507 | ||
3508 | /* Handle pointer arithmetic EXPR when creating aliasing constraints. | |
3509 | Expressions of the type PTR + CST can be handled in two ways: | |
3510 | ||
3511 | 1- If the constraint for PTR is ADDRESSOF for a non-structure | |
3512 | variable, then we can use it directly because adding or | |
3513 | subtracting a constant may not alter the original ADDRESSOF | |
a4174ebf | 3514 | constraint (i.e., pointer arithmetic may not legally go outside |
e8ca4159 DN |
3515 | an object's boundaries). |
3516 | ||
3517 | 2- If the constraint for PTR is ADDRESSOF for a structure variable, | |
3518 | then if CST is a compile-time constant that can be used as an | |
3519 | offset, we can determine which sub-variable will be pointed-to | |
3520 | by the expression. | |
3521 | ||
3522 | Return true if the expression is handled. For any other kind of | |
3523 | expression, return false so that each operand can be added as a | |
3524 | separate constraint by the caller. */ | |
3525 | ||
3526 | static bool | |
4ee00913 | 3527 | handle_ptr_arith (VEC (ce_s, heap) *lhsc, tree expr) |
e8ca4159 DN |
3528 | { |
3529 | tree op0, op1; | |
4ee00913 DB |
3530 | struct constraint_expr *c, *c2; |
3531 | unsigned int i = 0; | |
3532 | unsigned int j = 0; | |
3533 | VEC (ce_s, heap) *temp = NULL; | |
7b765bed DB |
3534 | unsigned int rhsoffset = 0; |
3535 | bool unknown_addend = false; | |
e8ca4159 | 3536 | |
5be014d5 | 3537 | if (TREE_CODE (expr) != POINTER_PLUS_EXPR) |
e8ca4159 DN |
3538 | return false; |
3539 | ||
3540 | op0 = TREE_OPERAND (expr, 0); | |
3541 | op1 = TREE_OPERAND (expr, 1); | |
5be014d5 | 3542 | gcc_assert (POINTER_TYPE_P (TREE_TYPE (op0))); |
e8ca4159 | 3543 | |
1d85354c | 3544 | get_constraint_for (op0, &temp); |
c58936b6 | 3545 | |
7b765bed DB |
3546 | /* Handle non-constants by making constraints from integer. */ |
3547 | if (TREE_CODE (op1) == INTEGER_CST) | |
3548 | rhsoffset = TREE_INT_CST_LOW (op1) * BITS_PER_UNIT; | |
3549 | else | |
3550 | unknown_addend = true; | |
e8ca4159 | 3551 | |
4ee00913 DB |
3552 | for (i = 0; VEC_iterate (ce_s, lhsc, i, c); i++) |
3553 | for (j = 0; VEC_iterate (ce_s, temp, j, c2); j++) | |
3554 | { | |
3555 | if (c2->type == ADDRESSOF && rhsoffset != 0) | |
3556 | { | |
3557 | varinfo_t temp = get_varinfo (c2->var); | |
04743a37 RG |
3558 | |
3559 | /* An access one after the end of an array is valid, | |
3560 | so simply punt on accesses we cannot resolve. */ | |
3561 | temp = first_vi_for_offset (temp, rhsoffset); | |
3562 | if (temp == NULL) | |
3563 | continue; | |
3564 | c2->var = temp->id; | |
4ee00913 DB |
3565 | c2->offset = 0; |
3566 | } | |
7b765bed DB |
3567 | else if (unknown_addend) |
3568 | { | |
3569 | /* Can't handle *a + integer where integer is unknown. */ | |
3570 | if (c2->type != SCALAR) | |
3571 | { | |
3572 | struct constraint_expr intc; | |
3573 | intc.var = integer_id; | |
3574 | intc.offset = 0; | |
3575 | intc.type = SCALAR; | |
3576 | process_constraint (new_constraint (*c, intc)); | |
3577 | } | |
3578 | else | |
3579 | { | |
3580 | /* We known it lives somewhere within c2->var. */ | |
3581 | varinfo_t tmp = get_varinfo (c2->var); | |
3582 | for (; tmp; tmp = tmp->next) | |
3583 | { | |
3584 | struct constraint_expr tmpc = *c2; | |
3585 | c2->var = tmp->id; | |
3586 | c2->offset = 0; | |
3587 | process_constraint (new_constraint (*c, tmpc)); | |
3588 | } | |
3589 | } | |
3590 | } | |
4ee00913 DB |
3591 | else |
3592 | c2->offset = rhsoffset; | |
3593 | process_constraint (new_constraint (*c, *c2)); | |
3594 | } | |
e8ca4159 | 3595 | |
4ee00913 | 3596 | VEC_free (ce_s, heap, temp); |
e8ca4159 DN |
3597 | |
3598 | return true; | |
3599 | } | |
3600 | ||
7b765bed DB |
3601 | /* For non-IPA mode, generate constraints necessary for a call on the |
3602 | RHS. */ | |
3603 | ||
3604 | static void | |
3605 | handle_rhs_call (tree rhs) | |
3606 | { | |
3607 | tree arg; | |
3608 | call_expr_arg_iterator iter; | |
3609 | struct constraint_expr rhsc; | |
3610 | ||
3611 | rhsc.var = anything_id; | |
3612 | rhsc.offset = 0; | |
3613 | rhsc.type = ADDRESSOF; | |
3614 | ||
3615 | FOR_EACH_CALL_EXPR_ARG (arg, iter, rhs) | |
3616 | { | |
3617 | VEC(ce_s, heap) *lhsc = NULL; | |
3618 | ||
3619 | /* Find those pointers being passed, and make sure they end up | |
3620 | pointing to anything. */ | |
3621 | if (POINTER_TYPE_P (TREE_TYPE (arg))) | |
3622 | { | |
3623 | unsigned int j; | |
3624 | struct constraint_expr *lhsp; | |
3625 | ||
3626 | get_constraint_for (arg, &lhsc); | |
3627 | do_deref (&lhsc); | |
3628 | for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++) | |
3629 | process_constraint_1 (new_constraint (*lhsp, rhsc), true); | |
3630 | VEC_free (ce_s, heap, lhsc); | |
3631 | } | |
3632 | } | |
3633 | } | |
e8ca4159 | 3634 | |
af947da7 RG |
3635 | /* For non-IPA mode, generate constraints necessary for a call |
3636 | that returns a pointer and assigns it to LHS. This simply makes | |
3637 | the LHS point to anything. */ | |
3638 | ||
3639 | static void | |
3640 | handle_lhs_call (tree lhs) | |
3641 | { | |
3642 | VEC(ce_s, heap) *lhsc = NULL; | |
3643 | struct constraint_expr rhsc; | |
3644 | unsigned int j; | |
3645 | struct constraint_expr *lhsp; | |
3646 | ||
3647 | rhsc.var = anything_id; | |
3648 | rhsc.offset = 0; | |
3649 | rhsc.type = ADDRESSOF; | |
3650 | get_constraint_for (lhs, &lhsc); | |
3651 | for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++) | |
3652 | process_constraint_1 (new_constraint (*lhsp, rhsc), true); | |
3653 | VEC_free (ce_s, heap, lhsc); | |
3654 | } | |
3655 | ||
e8ca4159 DN |
3656 | /* Walk statement T setting up aliasing constraints according to the |
3657 | references found in T. This function is the main part of the | |
3658 | constraint builder. AI points to auxiliary alias information used | |
3659 | when building alias sets and computing alias grouping heuristics. */ | |
910fdc79 DB |
3660 | |
3661 | static void | |
4ee00913 | 3662 | find_func_aliases (tree origt) |
910fdc79 | 3663 | { |
4ee00913 DB |
3664 | tree t = origt; |
3665 | VEC(ce_s, heap) *lhsc = NULL; | |
3666 | VEC(ce_s, heap) *rhsc = NULL; | |
3667 | struct constraint_expr *c; | |
910fdc79 | 3668 | |
4ee00913 DB |
3669 | if (TREE_CODE (t) == RETURN_EXPR && TREE_OPERAND (t, 0)) |
3670 | t = TREE_OPERAND (t, 0); | |
910fdc79 | 3671 | |
e8ca4159 DN |
3672 | /* Now build constraints expressions. */ |
3673 | if (TREE_CODE (t) == PHI_NODE) | |
3674 | { | |
6df11ca1 DB |
3675 | gcc_assert (!AGGREGATE_TYPE_P (TREE_TYPE (PHI_RESULT (t)))); |
3676 | ||
e8ca4159 DN |
3677 | /* Only care about pointers and structures containing |
3678 | pointers. */ | |
21392f19 | 3679 | if (could_have_pointers (PHI_RESULT (t))) |
e8ca4159 DN |
3680 | { |
3681 | int i; | |
4ee00913 | 3682 | unsigned int j; |
c58936b6 | 3683 | |
4ee00913 DB |
3684 | /* For a phi node, assign all the arguments to |
3685 | the result. */ | |
1d85354c | 3686 | get_constraint_for (PHI_RESULT (t), &lhsc); |
e8ca4159 | 3687 | for (i = 0; i < PHI_NUM_ARGS (t); i++) |
c58936b6 | 3688 | { |
0a4288d9 RG |
3689 | tree rhstype; |
3690 | tree strippedrhs = PHI_ARG_DEF (t, i); | |
3691 | ||
3692 | STRIP_NOPS (strippedrhs); | |
3693 | rhstype = TREE_TYPE (strippedrhs); | |
1d85354c | 3694 | get_constraint_for (PHI_ARG_DEF (t, i), &rhsc); |
0a4288d9 | 3695 | |
4ee00913 DB |
3696 | for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++) |
3697 | { | |
3698 | struct constraint_expr *c2; | |
3699 | while (VEC_length (ce_s, rhsc) > 0) | |
3700 | { | |
3701 | c2 = VEC_last (ce_s, rhsc); | |
3702 | process_constraint (new_constraint (*c, *c2)); | |
3703 | VEC_pop (ce_s, rhsc); | |
3704 | } | |
3705 | } | |
c58936b6 | 3706 | } |
4ee00913 DB |
3707 | } |
3708 | } | |
3709 | /* In IPA mode, we need to generate constraints to pass call | |
6e7e772d DN |
3710 | arguments through their calls. There are two cases, either a |
3711 | GIMPLE_MODIFY_STMT when we are returning a value, or just a plain | |
7b765bed DB |
3712 | CALL_EXPR when we are not. |
3713 | ||
3714 | In non-ipa mode, we need to generate constraints for each | |
3715 | pointer passed by address. */ | |
3716 | else if (((TREE_CODE (t) == GIMPLE_MODIFY_STMT | |
3717 | && TREE_CODE (GIMPLE_STMT_OPERAND (t, 1)) == CALL_EXPR | |
3718 | && !(call_expr_flags (GIMPLE_STMT_OPERAND (t, 1)) | |
3719 | & (ECF_MALLOC | ECF_MAY_BE_ALLOCA))) | |
3720 | || (TREE_CODE (t) == CALL_EXPR | |
3721 | && !(call_expr_flags (t) | |
3722 | & (ECF_MALLOC | ECF_MAY_BE_ALLOCA))))) | |
4ee00913 | 3723 | { |
7b765bed | 3724 | if (!in_ipa_mode) |
4ee00913 | 3725 | { |
7b765bed | 3726 | if (TREE_CODE (t) == GIMPLE_MODIFY_STMT) |
af947da7 RG |
3727 | { |
3728 | handle_rhs_call (GIMPLE_STMT_OPERAND (t, 1)); | |
3729 | if (POINTER_TYPE_P (TREE_TYPE (GIMPLE_STMT_OPERAND (t, 1)))) | |
3730 | handle_lhs_call (GIMPLE_STMT_OPERAND (t, 0)); | |
3731 | } | |
7b765bed DB |
3732 | else |
3733 | handle_rhs_call (t); | |
4ee00913 DB |
3734 | } |
3735 | else | |
3736 | { | |
7b765bed DB |
3737 | tree lhsop; |
3738 | tree rhsop; | |
3739 | tree arg; | |
3740 | call_expr_arg_iterator iter; | |
3741 | varinfo_t fi; | |
3742 | int i = 1; | |
3743 | tree decl; | |
3744 | if (TREE_CODE (t) == GIMPLE_MODIFY_STMT) | |
e8ca4159 | 3745 | { |
7b765bed DB |
3746 | lhsop = GIMPLE_STMT_OPERAND (t, 0); |
3747 | rhsop = GIMPLE_STMT_OPERAND (t, 1); | |
4ee00913 DB |
3748 | } |
3749 | else | |
3750 | { | |
7b765bed DB |
3751 | lhsop = NULL; |
3752 | rhsop = t; | |
e8ca4159 | 3753 | } |
7b765bed DB |
3754 | decl = get_callee_fndecl (rhsop); |
3755 | ||
3756 | /* If we can directly resolve the function being called, do so. | |
3757 | Otherwise, it must be some sort of indirect expression that | |
3758 | we should still be able to handle. */ | |
3759 | if (decl) | |
4ee00913 | 3760 | { |
7b765bed DB |
3761 | fi = get_vi_for_tree (decl); |
3762 | } | |
3763 | else | |
3764 | { | |
3765 | decl = CALL_EXPR_FN (rhsop); | |
3766 | fi = get_vi_for_tree (decl); | |
4ee00913 | 3767 | } |
6e7e772d | 3768 | |
7b765bed DB |
3769 | /* Assign all the passed arguments to the appropriate incoming |
3770 | parameters of the function. */ | |
c58936b6 | 3771 | |
7b765bed | 3772 | FOR_EACH_CALL_EXPR_ARG (arg, iter, rhsop) |
4ee00913 | 3773 | { |
7b765bed DB |
3774 | struct constraint_expr lhs ; |
3775 | struct constraint_expr *rhsp; | |
3776 | ||
3777 | get_constraint_for (arg, &rhsc); | |
3778 | if (TREE_CODE (decl) != FUNCTION_DECL) | |
3779 | { | |
3780 | lhs.type = DEREF; | |
3781 | lhs.var = fi->id; | |
3782 | lhs.offset = i; | |
3783 | } | |
3784 | else | |
3785 | { | |
3786 | lhs.type = SCALAR; | |
3787 | lhs.var = first_vi_for_offset (fi, i)->id; | |
3788 | lhs.offset = 0; | |
3789 | } | |
3790 | while (VEC_length (ce_s, rhsc) != 0) | |
3791 | { | |
3792 | rhsp = VEC_last (ce_s, rhsc); | |
3793 | process_constraint (new_constraint (lhs, *rhsp)); | |
3794 | VEC_pop (ce_s, rhsc); | |
3795 | } | |
3796 | i++; | |
4ee00913 | 3797 | } |
7b765bed DB |
3798 | |
3799 | /* If we are returning a value, assign it to the result. */ | |
3800 | if (lhsop) | |
4ee00913 | 3801 | { |
7b765bed DB |
3802 | struct constraint_expr rhs; |
3803 | struct constraint_expr *lhsp; | |
3804 | unsigned int j = 0; | |
3805 | ||
3806 | get_constraint_for (lhsop, &lhsc); | |
3807 | if (TREE_CODE (decl) != FUNCTION_DECL) | |
3808 | { | |
3809 | rhs.type = DEREF; | |
3810 | rhs.var = fi->id; | |
3811 | rhs.offset = i; | |
3812 | } | |
3813 | else | |
3814 | { | |
3815 | rhs.type = SCALAR; | |
3816 | rhs.var = first_vi_for_offset (fi, i)->id; | |
3817 | rhs.offset = 0; | |
3818 | } | |
3819 | for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++) | |
3820 | process_constraint (new_constraint (*lhsp, rhs)); | |
4ee00913 | 3821 | } |
c58936b6 | 3822 | } |
e8ca4159 | 3823 | } |
4ee00913 | 3824 | /* Otherwise, just a regular assignment statement. */ |
07beea0d | 3825 | else if (TREE_CODE (t) == GIMPLE_MODIFY_STMT) |
e8ca4159 | 3826 | { |
07beea0d AH |
3827 | tree lhsop = GIMPLE_STMT_OPERAND (t, 0); |
3828 | tree rhsop = GIMPLE_STMT_OPERAND (t, 1); | |
4ee00913 | 3829 | int i; |
e8ca4159 | 3830 | |
c58936b6 | 3831 | if ((AGGREGATE_TYPE_P (TREE_TYPE (lhsop)) |
98b2060a RG |
3832 | || TREE_CODE (TREE_TYPE (lhsop)) == COMPLEX_TYPE) |
3833 | && (AGGREGATE_TYPE_P (TREE_TYPE (rhsop)) | |
3834 | || TREE_CODE (TREE_TYPE (lhsop)) == COMPLEX_TYPE)) | |
e8ca4159 DN |
3835 | { |
3836 | do_structure_copy (lhsop, rhsop); | |
3837 | } | |
3838 | else | |
3839 | { | |
3840 | /* Only care about operations with pointers, structures | |
3841 | containing pointers, dereferences, and call expressions. */ | |
21392f19 | 3842 | if (could_have_pointers (lhsop) |
e8ca4159 DN |
3843 | || TREE_CODE (rhsop) == CALL_EXPR) |
3844 | { | |
1d85354c | 3845 | get_constraint_for (lhsop, &lhsc); |
e8ca4159 DN |
3846 | switch (TREE_CODE_CLASS (TREE_CODE (rhsop))) |
3847 | { | |
3848 | /* RHS that consist of unary operations, | |
3849 | exceptional types, or bare decls/constants, get | |
c58936b6 | 3850 | handled directly by get_constraint_for. */ |
910fdc79 DB |
3851 | case tcc_reference: |
3852 | case tcc_declaration: | |
3853 | case tcc_constant: | |
3854 | case tcc_exceptional: | |
3855 | case tcc_expression: | |
5039610b | 3856 | case tcc_vl_exp: |
910fdc79 | 3857 | case tcc_unary: |
e8ca4159 | 3858 | { |
4ee00913 | 3859 | unsigned int j; |
4ee00913 | 3860 | |
6df11ca1 | 3861 | get_constraint_for (rhsop, &rhsc); |
4ee00913 DB |
3862 | for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++) |
3863 | { | |
3864 | struct constraint_expr *c2; | |
3865 | unsigned int k; | |
c58936b6 | 3866 | |
4ee00913 DB |
3867 | for (k = 0; VEC_iterate (ce_s, rhsc, k, c2); k++) |
3868 | process_constraint (new_constraint (*c, *c2)); | |
3869 | } | |
3870 | ||
e8ca4159 | 3871 | } |
910fdc79 DB |
3872 | break; |
3873 | ||
e8ca4159 DN |
3874 | case tcc_binary: |
3875 | { | |
3876 | /* For pointer arithmetic of the form | |
3877 | PTR + CST, we can simply use PTR's | |
3878 | constraint because pointer arithmetic is | |
3879 | not allowed to go out of bounds. */ | |
4ee00913 | 3880 | if (handle_ptr_arith (lhsc, rhsop)) |
e8ca4159 DN |
3881 | break; |
3882 | } | |
3883 | /* FALLTHRU */ | |
3884 | ||
3885 | /* Otherwise, walk each operand. Notice that we | |
3886 | can't use the operand interface because we need | |
3887 | to process expressions other than simple operands | |
3888 | (e.g. INDIRECT_REF, ADDR_EXPR, CALL_EXPR). */ | |
910fdc79 | 3889 | default: |
5039610b | 3890 | for (i = 0; i < TREE_OPERAND_LENGTH (rhsop); i++) |
910fdc79 DB |
3891 | { |
3892 | tree op = TREE_OPERAND (rhsop, i); | |
4ee00913 DB |
3893 | unsigned int j; |
3894 | ||
3895 | gcc_assert (VEC_length (ce_s, rhsc) == 0); | |
1d85354c | 3896 | get_constraint_for (op, &rhsc); |
4ee00913 DB |
3897 | for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++) |
3898 | { | |
3899 | struct constraint_expr *c2; | |
3900 | while (VEC_length (ce_s, rhsc) > 0) | |
3901 | { | |
3902 | c2 = VEC_last (ce_s, rhsc); | |
3903 | process_constraint (new_constraint (*c, *c2)); | |
3904 | VEC_pop (ce_s, rhsc); | |
3905 | } | |
3906 | } | |
910fdc79 | 3907 | } |
c58936b6 | 3908 | } |
e8ca4159 DN |
3909 | } |
3910 | } | |
910fdc79 | 3911 | } |
058dcc25 ILT |
3912 | else if (TREE_CODE (t) == CHANGE_DYNAMIC_TYPE_EXPR) |
3913 | { | |
3914 | unsigned int j; | |
3915 | ||
3916 | get_constraint_for (CHANGE_DYNAMIC_TYPE_LOCATION (t), &lhsc); | |
3917 | for (j = 0; VEC_iterate (ce_s, lhsc, j, c); ++j) | |
3918 | get_varinfo (c->var)->no_tbaa_pruning = true; | |
3919 | } | |
e8ca4159 DN |
3920 | |
3921 | /* After promoting variables and computing aliasing we will | |
3922 | need to re-scan most statements. FIXME: Try to minimize the | |
3923 | number of statements re-scanned. It's not really necessary to | |
c58936b6 | 3924 | re-scan *all* statements. */ |
4ee00913 DB |
3925 | mark_stmt_modified (origt); |
3926 | VEC_free (ce_s, heap, rhsc); | |
3927 | VEC_free (ce_s, heap, lhsc); | |
910fdc79 DB |
3928 | } |
3929 | ||
3930 | ||
3931 | /* Find the first varinfo in the same variable as START that overlaps with | |
3932 | OFFSET. | |
3933 | Effectively, walk the chain of fields for the variable START to find the | |
3934 | first field that overlaps with OFFSET. | |
8971094d | 3935 | Return NULL if we can't find one. */ |
910fdc79 | 3936 | |
c58936b6 | 3937 | static varinfo_t |
910fdc79 DB |
3938 | first_vi_for_offset (varinfo_t start, unsigned HOST_WIDE_INT offset) |
3939 | { | |
3940 | varinfo_t curr = start; | |
3941 | while (curr) | |
3942 | { | |
3943 | /* We may not find a variable in the field list with the actual | |
3944 | offset when when we have glommed a structure to a variable. | |
3945 | In that case, however, offset should still be within the size | |
3946 | of the variable. */ | |
3947 | if (offset >= curr->offset && offset < (curr->offset + curr->size)) | |
3948 | return curr; | |
3949 | curr = curr->next; | |
3950 | } | |
8971094d | 3951 | return NULL; |
910fdc79 DB |
3952 | } |
3953 | ||
3954 | ||
4cf4d6a3 DB |
3955 | /* Insert the varinfo FIELD into the field list for BASE, at the front |
3956 | of the list. */ | |
3957 | ||
3958 | static void | |
3959 | insert_into_field_list (varinfo_t base, varinfo_t field) | |
3960 | { | |
3961 | varinfo_t prev = base; | |
3962 | varinfo_t curr = base->next; | |
c58936b6 | 3963 | |
4cf4d6a3 DB |
3964 | field->next = curr; |
3965 | prev->next = field; | |
3966 | } | |
3967 | ||
910fdc79 DB |
3968 | /* Insert the varinfo FIELD into the field list for BASE, ordered by |
3969 | offset. */ | |
3970 | ||
3971 | static void | |
4cf4d6a3 | 3972 | insert_into_field_list_sorted (varinfo_t base, varinfo_t field) |
910fdc79 DB |
3973 | { |
3974 | varinfo_t prev = base; | |
3975 | varinfo_t curr = base->next; | |
c58936b6 | 3976 | |
910fdc79 DB |
3977 | if (curr == NULL) |
3978 | { | |
3979 | prev->next = field; | |
3980 | field->next = NULL; | |
3981 | } | |
3982 | else | |
3983 | { | |
3984 | while (curr) | |
3985 | { | |
3986 | if (field->offset <= curr->offset) | |
3987 | break; | |
3988 | prev = curr; | |
3989 | curr = curr->next; | |
3990 | } | |
3991 | field->next = prev->next; | |
3992 | prev->next = field; | |
3993 | } | |
3994 | } | |
3995 | ||
31de5b77 RG |
3996 | /* This structure is used during pushing fields onto the fieldstack |
3997 | to track the offset of the field, since bitpos_of_field gives it | |
3998 | relative to its immediate containing type, and we want it relative | |
3999 | to the ultimate containing object. */ | |
4000 | ||
4001 | struct fieldoff | |
4002 | { | |
4003 | /* Type of the field. */ | |
4004 | tree type; | |
4005 | ||
4006 | /* Size, in bits, of the field. */ | |
4007 | tree size; | |
4008 | ||
4009 | /* Field. */ | |
4010 | tree decl; | |
4011 | ||
4012 | /* Offset from the base of the base containing object to this field. */ | |
4013 | HOST_WIDE_INT offset; | |
4014 | }; | |
4015 | typedef struct fieldoff fieldoff_s; | |
4016 | ||
4017 | DEF_VEC_O(fieldoff_s); | |
4018 | DEF_VEC_ALLOC_O(fieldoff_s,heap); | |
4019 | ||
910fdc79 DB |
4020 | /* qsort comparison function for two fieldoff's PA and PB */ |
4021 | ||
c58936b6 | 4022 | static int |
910fdc79 DB |
4023 | fieldoff_compare (const void *pa, const void *pb) |
4024 | { | |
4025 | const fieldoff_s *foa = (const fieldoff_s *)pa; | |
4026 | const fieldoff_s *fob = (const fieldoff_s *)pb; | |
4027 | HOST_WIDE_INT foasize, fobsize; | |
c58936b6 | 4028 | |
910fdc79 DB |
4029 | if (foa->offset != fob->offset) |
4030 | return foa->offset - fob->offset; | |
4031 | ||
35ed859b RG |
4032 | foasize = TREE_INT_CST_LOW (foa->size); |
4033 | fobsize = TREE_INT_CST_LOW (fob->size); | |
910fdc79 DB |
4034 | return foasize - fobsize; |
4035 | } | |
4036 | ||
4037 | /* Sort a fieldstack according to the field offset and sizes. */ | |
31de5b77 | 4038 | static void |
83f676b3 | 4039 | sort_fieldstack (VEC(fieldoff_s,heap) *fieldstack) |
910fdc79 | 4040 | { |
c58936b6 DB |
4041 | qsort (VEC_address (fieldoff_s, fieldstack), |
4042 | VEC_length (fieldoff_s, fieldstack), | |
910fdc79 DB |
4043 | sizeof (fieldoff_s), |
4044 | fieldoff_compare); | |
4045 | } | |
4046 | ||
31de5b77 RG |
4047 | /* Return true if V is a tree that we can have subvars for. |
4048 | Normally, this is any aggregate type. Also complex | |
4049 | types which are not gimple registers can have subvars. */ | |
4050 | ||
4051 | static inline bool | |
4052 | var_can_have_subvars (const_tree v) | |
4053 | { | |
4054 | /* Volatile variables should never have subvars. */ | |
4055 | if (TREE_THIS_VOLATILE (v)) | |
4056 | return false; | |
4057 | ||
4058 | /* Non decls or memory tags can never have subvars. */ | |
4059 | if (!DECL_P (v) || MTAG_P (v)) | |
4060 | return false; | |
4061 | ||
4062 | /* Aggregates without overlapping fields can have subvars. */ | |
4063 | if (TREE_CODE (TREE_TYPE (v)) == RECORD_TYPE) | |
4064 | return true; | |
4065 | ||
4066 | return false; | |
4067 | } | |
4068 | ||
d7705551 DN |
4069 | /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all |
4070 | the fields of TYPE onto fieldstack, recording their offsets along | |
4071 | the way. | |
4072 | ||
4073 | OFFSET is used to keep track of the offset in this entire | |
4074 | structure, rather than just the immediately containing structure. | |
4075 | Returns the number of fields pushed. | |
4076 | ||
910fdc79 | 4077 | HAS_UNION is set to true if we find a union type as a field of |
31de5b77 | 4078 | TYPE. */ |
910fdc79 | 4079 | |
31de5b77 | 4080 | static int |
c58936b6 | 4081 | push_fields_onto_fieldstack (tree type, VEC(fieldoff_s,heap) **fieldstack, |
31de5b77 | 4082 | HOST_WIDE_INT offset, bool *has_union) |
910fdc79 DB |
4083 | { |
4084 | tree field; | |
4085 | int count = 0; | |
31de5b77 RG |
4086 | |
4087 | if (TREE_CODE (type) != RECORD_TYPE) | |
4088 | return 0; | |
3fe2f42a RG |
4089 | |
4090 | /* If the vector of fields is growing too big, bail out early. | |
4091 | Callers check for VEC_length <= MAX_FIELDS_FOR_FIELD_SENSITIVE, make | |
4092 | sure this fails. */ | |
31de5b77 | 4093 | if (VEC_length (fieldoff_s, *fieldstack) > MAX_FIELDS_FOR_FIELD_SENSITIVE) |
3fe2f42a | 4094 | return 0; |
c58936b6 | 4095 | |
31de5b77 RG |
4096 | for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field)) |
4097 | if (TREE_CODE (field) == FIELD_DECL) | |
4098 | { | |
4099 | bool push = false; | |
4100 | int pushed = 0; | |
4101 | ||
4102 | if (has_union | |
4103 | && (TREE_CODE (TREE_TYPE (field)) == QUAL_UNION_TYPE | |
4104 | || TREE_CODE (TREE_TYPE (field)) == UNION_TYPE)) | |
4105 | *has_union = true; | |
4106 | ||
4107 | if (!var_can_have_subvars (field)) | |
4108 | push = true; | |
4109 | else if (!(pushed = push_fields_onto_fieldstack | |
4110 | (TREE_TYPE (field), | |
4111 | fieldstack, | |
4112 | offset + bitpos_of_field (field), | |
4113 | has_union)) | |
4114 | && (DECL_SIZE (field) | |
4115 | && !integer_zerop (DECL_SIZE (field)))) | |
4116 | /* Empty structures may have actual size, like in C++. So | |
4117 | see if we didn't push any subfields and the size is | |
4118 | nonzero, push the field onto the stack. */ | |
4119 | push = true; | |
4120 | ||
4121 | if (push) | |
910fdc79 | 4122 | { |
31de5b77 RG |
4123 | fieldoff_s *pair; |
4124 | ||
4125 | pair = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL); | |
4126 | pair->type = TREE_TYPE (field); | |
4127 | pair->size = DECL_SIZE (field); | |
4128 | pair->decl = field; | |
4129 | pair->offset = offset + bitpos_of_field (field); | |
4130 | count++; | |
4131 | } | |
4132 | else | |
4133 | count += pushed; | |
4134 | } | |
910fdc79 DB |
4135 | |
4136 | return count; | |
4137 | } | |
4138 | ||
c58936b6 | 4139 | /* Create a constraint from ANYTHING variable to VI. */ |
910fdc79 | 4140 | static void |
c58936b6 | 4141 | make_constraint_from_anything (varinfo_t vi) |
910fdc79 DB |
4142 | { |
4143 | struct constraint_expr lhs, rhs; | |
21392f19 | 4144 | |
c58936b6 | 4145 | lhs.var = vi->id; |
21392f19 DB |
4146 | lhs.offset = 0; |
4147 | lhs.type = SCALAR; | |
4148 | ||
c58936b6 DB |
4149 | rhs.var = anything_id; |
4150 | rhs.offset = 0; | |
3e5937d7 | 4151 | rhs.type = ADDRESSOF; |
910fdc79 DB |
4152 | process_constraint (new_constraint (lhs, rhs)); |
4153 | } | |
4154 | ||
4ee00913 DB |
4155 | /* Count the number of arguments DECL has, and set IS_VARARGS to true |
4156 | if it is a varargs function. */ | |
4157 | ||
4158 | static unsigned int | |
4159 | count_num_arguments (tree decl, bool *is_varargs) | |
4160 | { | |
4161 | unsigned int i = 0; | |
4162 | tree t; | |
4163 | ||
c58936b6 | 4164 | for (t = TYPE_ARG_TYPES (TREE_TYPE (decl)); |
4ee00913 DB |
4165 | t; |
4166 | t = TREE_CHAIN (t)) | |
c58936b6 | 4167 | { |
4ee00913 DB |
4168 | if (TREE_VALUE (t) == void_type_node) |
4169 | break; | |
4170 | i++; | |
4171 | } | |
c58936b6 | 4172 | |
4ee00913 DB |
4173 | if (!t) |
4174 | *is_varargs = true; | |
4175 | return i; | |
4176 | } | |
4177 | ||
4178 | /* Creation function node for DECL, using NAME, and return the index | |
4179 | of the variable we've created for the function. */ | |
4180 | ||
4181 | static unsigned int | |
4182 | create_function_info_for (tree decl, const char *name) | |
4183 | { | |
4184 | unsigned int index = VEC_length (varinfo_t, varmap); | |
4185 | varinfo_t vi; | |
c58936b6 | 4186 | tree arg; |
4ee00913 DB |
4187 | unsigned int i; |
4188 | bool is_varargs = false; | |
4189 | ||
4190 | /* Create the variable info. */ | |
4191 | ||
3e5937d7 | 4192 | vi = new_var_info (decl, index, name); |
4ee00913 DB |
4193 | vi->decl = decl; |
4194 | vi->offset = 0; | |
4195 | vi->has_union = 0; | |
4196 | vi->size = 1; | |
4197 | vi->fullsize = count_num_arguments (decl, &is_varargs) + 1; | |
3e5937d7 | 4198 | insert_vi_for_tree (vi->decl, vi); |
4ee00913 DB |
4199 | VEC_safe_push (varinfo_t, heap, varmap, vi); |
4200 | ||
4201 | stats.total_vars++; | |
4202 | ||
4203 | /* If it's varargs, we don't know how many arguments it has, so we | |
4204 | can't do much. | |
4205 | */ | |
4206 | if (is_varargs) | |
4207 | { | |
4208 | vi->fullsize = ~0; | |
4209 | vi->size = ~0; | |
4210 | vi->is_unknown_size_var = true; | |
4211 | return index; | |
4212 | } | |
4213 | ||
c58936b6 | 4214 | |
4ee00913 DB |
4215 | arg = DECL_ARGUMENTS (decl); |
4216 | ||
6416ae7f | 4217 | /* Set up variables for each argument. */ |
4ee00913 | 4218 | for (i = 1; i < vi->fullsize; i++) |
c58936b6 | 4219 | { |
4ee00913 DB |
4220 | varinfo_t argvi; |
4221 | const char *newname; | |
4222 | char *tempname; | |
4223 | unsigned int newindex; | |
4224 | tree argdecl = decl; | |
4225 | ||
4226 | if (arg) | |
4227 | argdecl = arg; | |
c58936b6 | 4228 | |
4ee00913 DB |
4229 | newindex = VEC_length (varinfo_t, varmap); |
4230 | asprintf (&tempname, "%s.arg%d", name, i-1); | |
4231 | newname = ggc_strdup (tempname); | |
4232 | free (tempname); | |
4233 | ||
3e5937d7 | 4234 | argvi = new_var_info (argdecl, newindex, newname); |
4ee00913 DB |
4235 | argvi->decl = argdecl; |
4236 | VEC_safe_push (varinfo_t, heap, varmap, argvi); | |
4237 | argvi->offset = i; | |
4238 | argvi->size = 1; | |
4239 | argvi->fullsize = vi->fullsize; | |
4240 | argvi->has_union = false; | |
4cf4d6a3 | 4241 | insert_into_field_list_sorted (vi, argvi); |
4ee00913 DB |
4242 | stats.total_vars ++; |
4243 | if (arg) | |
4244 | { | |
3e5937d7 | 4245 | insert_vi_for_tree (arg, argvi); |
4ee00913 DB |
4246 | arg = TREE_CHAIN (arg); |
4247 | } | |
4248 | } | |
4cf4d6a3 | 4249 | |
4ee00913 DB |
4250 | /* Create a variable for the return var. */ |
4251 | if (DECL_RESULT (decl) != NULL | |
4252 | || !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (decl)))) | |
4253 | { | |
4254 | varinfo_t resultvi; | |
4255 | const char *newname; | |
4256 | char *tempname; | |
4257 | unsigned int newindex; | |
4258 | tree resultdecl = decl; | |
4259 | ||
4260 | vi->fullsize ++; | |
4261 | ||
4ee00913 DB |
4262 | if (DECL_RESULT (decl)) |
4263 | resultdecl = DECL_RESULT (decl); | |
c58936b6 | 4264 | |
4ee00913 DB |
4265 | newindex = VEC_length (varinfo_t, varmap); |
4266 | asprintf (&tempname, "%s.result", name); | |
4267 | newname = ggc_strdup (tempname); | |
4268 | free (tempname); | |
4269 | ||
3e5937d7 | 4270 | resultvi = new_var_info (resultdecl, newindex, newname); |
4ee00913 DB |
4271 | resultvi->decl = resultdecl; |
4272 | VEC_safe_push (varinfo_t, heap, varmap, resultvi); | |
4273 | resultvi->offset = i; | |
4274 | resultvi->size = 1; | |
4275 | resultvi->fullsize = vi->fullsize; | |
4276 | resultvi->has_union = false; | |
4cf4d6a3 | 4277 | insert_into_field_list_sorted (vi, resultvi); |
4ee00913 DB |
4278 | stats.total_vars ++; |
4279 | if (DECL_RESULT (decl)) | |
3e5937d7 | 4280 | insert_vi_for_tree (DECL_RESULT (decl), resultvi); |
4ee00913 DB |
4281 | } |
4282 | return index; | |
c58936b6 | 4283 | } |
4ee00913 | 4284 | |
6c11790d | 4285 | |
c58936b6 | 4286 | /* Return true if FIELDSTACK contains fields that overlap. |
6c11790d DB |
4287 | FIELDSTACK is assumed to be sorted by offset. */ |
4288 | ||
4289 | static bool | |
4290 | check_for_overlaps (VEC (fieldoff_s,heap) *fieldstack) | |
4291 | { | |
4292 | fieldoff_s *fo = NULL; | |
4293 | unsigned int i; | |
30d2662c | 4294 | HOST_WIDE_INT lastoffset = -1; |
6c11790d DB |
4295 | |
4296 | for (i = 0; VEC_iterate (fieldoff_s, fieldstack, i, fo); i++) | |
4297 | { | |
4298 | if (fo->offset == lastoffset) | |
4299 | return true; | |
4300 | lastoffset = fo->offset; | |
4301 | } | |
4302 | return false; | |
4303 | } | |
21392f19 | 4304 | |
910fdc79 DB |
4305 | /* Create a varinfo structure for NAME and DECL, and add it to VARMAP. |
4306 | This will also create any varinfo structures necessary for fields | |
4307 | of DECL. */ | |
4308 | ||
4309 | static unsigned int | |
4310 | create_variable_info_for (tree decl, const char *name) | |
4311 | { | |
4312 | unsigned int index = VEC_length (varinfo_t, varmap); | |
4313 | varinfo_t vi; | |
4314 | tree decltype = TREE_TYPE (decl); | |
4ee00913 | 4315 | tree declsize = DECL_P (decl) ? DECL_SIZE (decl) : TYPE_SIZE (decltype); |
910fdc79 | 4316 | bool notokay = false; |
58b82d2b | 4317 | bool hasunion; |
910fdc79 | 4318 | bool is_global = DECL_P (decl) ? is_global_var (decl) : false; |
910fdc79 | 4319 | VEC (fieldoff_s,heap) *fieldstack = NULL; |
c58936b6 | 4320 | |
4ee00913 DB |
4321 | if (TREE_CODE (decl) == FUNCTION_DECL && in_ipa_mode) |
4322 | return create_function_info_for (decl, name); | |
58b82d2b | 4323 | |
e8ca4159 | 4324 | hasunion = TREE_CODE (decltype) == UNION_TYPE |
c58936b6 | 4325 | || TREE_CODE (decltype) == QUAL_UNION_TYPE; |
58b82d2b | 4326 | if (var_can_have_subvars (decl) && use_field_sensitive && !hasunion) |
910fdc79 | 4327 | { |
31de5b77 | 4328 | push_fields_onto_fieldstack (decltype, &fieldstack, 0, &hasunion); |
58b82d2b DB |
4329 | if (hasunion) |
4330 | { | |
4331 | VEC_free (fieldoff_s, heap, fieldstack); | |
4332 | notokay = true; | |
4ee00913 | 4333 | } |
910fdc79 | 4334 | } |
c58936b6 | 4335 | |
910fdc79 DB |
4336 | /* If the variable doesn't have subvars, we may end up needing to |
4337 | sort the field list and create fake variables for all the | |
4338 | fields. */ | |
3e5937d7 | 4339 | vi = new_var_info (decl, index, name); |
910fdc79 DB |
4340 | vi->decl = decl; |
4341 | vi->offset = 0; | |
58b82d2b | 4342 | vi->has_union = hasunion; |
4ee00913 DB |
4343 | if (!declsize |
4344 | || TREE_CODE (declsize) != INTEGER_CST | |
910fdc79 DB |
4345 | || TREE_CODE (decltype) == UNION_TYPE |
4346 | || TREE_CODE (decltype) == QUAL_UNION_TYPE) | |
4347 | { | |
4348 | vi->is_unknown_size_var = true; | |
4349 | vi->fullsize = ~0; | |
4350 | vi->size = ~0; | |
4351 | } | |
4352 | else | |
4353 | { | |
4ee00913 | 4354 | vi->fullsize = TREE_INT_CST_LOW (declsize); |
910fdc79 DB |
4355 | vi->size = vi->fullsize; |
4356 | } | |
c58936b6 | 4357 | |
3e5937d7 | 4358 | insert_vi_for_tree (vi->decl, vi); |
b5efa470 | 4359 | VEC_safe_push (varinfo_t, heap, varmap, vi); |
4ee00913 | 4360 | if (is_global && (!flag_whole_program || !in_ipa_mode)) |
c58936b6 | 4361 | make_constraint_from_anything (vi); |
910fdc79 DB |
4362 | |
4363 | stats.total_vars++; | |
c58936b6 DB |
4364 | if (use_field_sensitive |
4365 | && !notokay | |
4366 | && !vi->is_unknown_size_var | |
98035a75 | 4367 | && var_can_have_subvars (decl) |
11948f6b | 4368 | && VEC_length (fieldoff_s, fieldstack) > 1 |
98035a75 | 4369 | && VEC_length (fieldoff_s, fieldstack) <= MAX_FIELDS_FOR_FIELD_SENSITIVE) |
910fdc79 DB |
4370 | { |
4371 | unsigned int newindex = VEC_length (varinfo_t, varmap); | |
4372 | fieldoff_s *fo = NULL; | |
4373 | unsigned int i; | |
910fdc79 DB |
4374 | |
4375 | for (i = 0; !notokay && VEC_iterate (fieldoff_s, fieldstack, i, fo); i++) | |
4376 | { | |
35ed859b RG |
4377 | if (! fo->size |
4378 | || TREE_CODE (fo->size) != INTEGER_CST | |
910fdc79 DB |
4379 | || fo->offset < 0) |
4380 | { | |
4381 | notokay = true; | |
4382 | break; | |
4383 | } | |
4384 | } | |
58b82d2b DB |
4385 | |
4386 | /* We can't sort them if we have a field with a variable sized type, | |
4387 | which will make notokay = true. In that case, we are going to return | |
4388 | without creating varinfos for the fields anyway, so sorting them is a | |
4389 | waste to boot. */ | |
6c11790d | 4390 | if (!notokay) |
c58936b6 | 4391 | { |
6c11790d DB |
4392 | sort_fieldstack (fieldstack); |
4393 | /* Due to some C++ FE issues, like PR 22488, we might end up | |
4394 | what appear to be overlapping fields even though they, | |
4395 | in reality, do not overlap. Until the C++ FE is fixed, | |
4396 | we will simply disable field-sensitivity for these cases. */ | |
4397 | notokay = check_for_overlaps (fieldstack); | |
4398 | } | |
c58936b6 DB |
4399 | |
4400 | ||
910fdc79 DB |
4401 | if (VEC_length (fieldoff_s, fieldstack) != 0) |
4402 | fo = VEC_index (fieldoff_s, fieldstack, 0); | |
4403 | ||
4404 | if (fo == NULL || notokay) | |
4405 | { | |
4406 | vi->is_unknown_size_var = 1; | |
4407 | vi->fullsize = ~0; | |
4408 | vi->size = ~0; | |
4409 | VEC_free (fieldoff_s, heap, fieldstack); | |
4410 | return index; | |
4411 | } | |
c58936b6 | 4412 | |
35ed859b | 4413 | vi->size = TREE_INT_CST_LOW (fo->size); |
046a69e0 | 4414 | vi->offset = fo->offset; |
c58936b6 DB |
4415 | for (i = VEC_length (fieldoff_s, fieldstack) - 1; |
4416 | i >= 1 && VEC_iterate (fieldoff_s, fieldstack, i, fo); | |
4cf4d6a3 | 4417 | i--) |
910fdc79 DB |
4418 | { |
4419 | varinfo_t newvi; | |
4f6c9110 | 4420 | const char *newname = "NULL"; |
910fdc79 DB |
4421 | char *tempname; |
4422 | ||
910fdc79 | 4423 | newindex = VEC_length (varinfo_t, varmap); |
4f6c9110 RG |
4424 | if (dump_file) |
4425 | { | |
4426 | if (fo->decl) | |
c58936b6 | 4427 | asprintf (&tempname, "%s.%s", |
4f6c9110 RG |
4428 | vi->name, alias_get_name (fo->decl)); |
4429 | else | |
c58936b6 | 4430 | asprintf (&tempname, "%s." HOST_WIDE_INT_PRINT_DEC, |
4f6c9110 RG |
4431 | vi->name, fo->offset); |
4432 | newname = ggc_strdup (tempname); | |
4433 | free (tempname); | |
4434 | } | |
3e5937d7 | 4435 | newvi = new_var_info (decl, newindex, newname); |
910fdc79 | 4436 | newvi->offset = fo->offset; |
35ed859b | 4437 | newvi->size = TREE_INT_CST_LOW (fo->size); |
910fdc79 DB |
4438 | newvi->fullsize = vi->fullsize; |
4439 | insert_into_field_list (vi, newvi); | |
b5efa470 | 4440 | VEC_safe_push (varinfo_t, heap, varmap, newvi); |
4ee00913 | 4441 | if (is_global && (!flag_whole_program || !in_ipa_mode)) |
c58936b6 DB |
4442 | make_constraint_from_anything (newvi); |
4443 | ||
4ee00913 | 4444 | stats.total_vars++; |
910fdc79 | 4445 | } |
910fdc79 | 4446 | } |
efe9e829 RG |
4447 | |
4448 | VEC_free (fieldoff_s, heap, fieldstack); | |
4449 | ||
910fdc79 DB |
4450 | return index; |
4451 | } | |
4452 | ||
4453 | /* Print out the points-to solution for VAR to FILE. */ | |
4454 | ||
4455 | void | |
4456 | dump_solution_for_var (FILE *file, unsigned int var) | |
4457 | { | |
4458 | varinfo_t vi = get_varinfo (var); | |
4459 | unsigned int i; | |
c58936b6 DB |
4460 | bitmap_iterator bi; |
4461 | ||
3e5937d7 | 4462 | if (find (var) != var) |
910fdc79 | 4463 | { |
3e5937d7 | 4464 | varinfo_t vipt = get_varinfo (find (var)); |
c58936b6 DB |
4465 | fprintf (file, "%s = same as %s\n", vi->name, vipt->name); |
4466 | } | |
4467 | else | |
4468 | { | |
4469 | fprintf (file, "%s = { ", vi->name); | |
3e5937d7 | 4470 | EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi) |
c58936b6 DB |
4471 | { |
4472 | fprintf (file, "%s ", get_varinfo (i)->name); | |
4473 | } | |
058dcc25 ILT |
4474 | fprintf (file, "}"); |
4475 | if (vi->no_tbaa_pruning) | |
4476 | fprintf (file, " no-tbaa-pruning"); | |
4477 | fprintf (file, "\n"); | |
910fdc79 | 4478 | } |
910fdc79 DB |
4479 | } |
4480 | ||
4481 | /* Print the points-to solution for VAR to stdout. */ | |
4482 | ||
4483 | void | |
4484 | debug_solution_for_var (unsigned int var) | |
4485 | { | |
4486 | dump_solution_for_var (stdout, var); | |
4487 | } | |
4488 | ||
910fdc79 DB |
4489 | /* Create varinfo structures for all of the variables in the |
4490 | function for intraprocedural mode. */ | |
4491 | ||
4492 | static void | |
4493 | intra_create_variable_infos (void) | |
4494 | { | |
4495 | tree t; | |
21392f19 | 4496 | struct constraint_expr lhs, rhs; |
b23987ec | 4497 | |
6e7e772d DN |
4498 | /* For each incoming pointer argument arg, create the constraint ARG |
4499 | = ANYTHING or a dummy variable if flag_argument_noalias is set. */ | |
910fdc79 DB |
4500 | for (t = DECL_ARGUMENTS (current_function_decl); t; t = TREE_CHAIN (t)) |
4501 | { | |
910fdc79 | 4502 | varinfo_t p; |
c58936b6 | 4503 | |
21392f19 DB |
4504 | if (!could_have_pointers (t)) |
4505 | continue; | |
c58936b6 | 4506 | |
e9e0aa2c DN |
4507 | /* If flag_argument_noalias is set, then function pointer |
4508 | arguments are guaranteed not to point to each other. In that | |
4509 | case, create an artificial variable PARM_NOALIAS and the | |
4510 | constraint ARG = &PARM_NOALIAS. */ | |
4511 | if (POINTER_TYPE_P (TREE_TYPE (t)) && flag_argument_noalias > 0) | |
7cc92f92 RG |
4512 | { |
4513 | varinfo_t vi; | |
7cc92f92 | 4514 | tree heapvar = heapvar_lookup (t); |
c58936b6 | 4515 | |
21392f19 DB |
4516 | lhs.offset = 0; |
4517 | lhs.type = SCALAR; | |
3e5937d7 | 4518 | lhs.var = get_vi_for_tree (t)->id; |
c58936b6 | 4519 | |
7cc92f92 RG |
4520 | if (heapvar == NULL_TREE) |
4521 | { | |
e9e0aa2c | 4522 | var_ann_t ann; |
c58936b6 | 4523 | heapvar = create_tmp_var_raw (TREE_TYPE (TREE_TYPE (t)), |
4cf4d6a3 | 4524 | "PARM_NOALIAS"); |
7cc92f92 | 4525 | DECL_EXTERNAL (heapvar) = 1; |
5cd4ec7f | 4526 | if (gimple_referenced_vars (cfun)) |
f004ab02 | 4527 | add_referenced_var (heapvar); |
e9e0aa2c | 4528 | |
7cc92f92 | 4529 | heapvar_insert (t, heapvar); |
e9e0aa2c DN |
4530 | |
4531 | ann = get_var_ann (heapvar); | |
4532 | if (flag_argument_noalias == 1) | |
4533 | ann->noalias_state = NO_ALIAS; | |
4534 | else if (flag_argument_noalias == 2) | |
4535 | ann->noalias_state = NO_ALIAS_GLOBAL; | |
4536 | else if (flag_argument_noalias == 3) | |
4537 | ann->noalias_state = NO_ALIAS_ANYTHING; | |
4538 | else | |
4539 | gcc_unreachable (); | |
7cc92f92 | 4540 | } |
e9e0aa2c | 4541 | |
3e5937d7 | 4542 | vi = get_vi_for_tree (heapvar); |
7cc92f92 RG |
4543 | vi->is_artificial_var = 1; |
4544 | vi->is_heap_var = 1; | |
3e5937d7 DB |
4545 | rhs.var = vi->id; |
4546 | rhs.type = ADDRESSOF; | |
7cc92f92 | 4547 | rhs.offset = 0; |
c58936b6 | 4548 | for (p = get_varinfo (lhs.var); p; p = p->next) |
7cc92f92 RG |
4549 | { |
4550 | struct constraint_expr temp = lhs; | |
4551 | temp.var = p->id; | |
4552 | process_constraint (new_constraint (temp, rhs)); | |
4553 | } | |
4554 | } | |
c58936b6 | 4555 | else |
21392f19 | 4556 | { |
3e5937d7 DB |
4557 | varinfo_t arg_vi = get_vi_for_tree (t); |
4558 | ||
4559 | for (p = arg_vi; p; p = p->next) | |
c58936b6 | 4560 | make_constraint_from_anything (p); |
21392f19 DB |
4561 | } |
4562 | } | |
910fdc79 DB |
4563 | } |
4564 | ||
1296c31f DB |
4565 | /* Structure used to put solution bitmaps in a hashtable so they can |
4566 | be shared among variables with the same points-to set. */ | |
4567 | ||
4568 | typedef struct shared_bitmap_info | |
4569 | { | |
4570 | bitmap pt_vars; | |
4571 | hashval_t hashcode; | |
4572 | } *shared_bitmap_info_t; | |
e5cfc29f | 4573 | typedef const struct shared_bitmap_info *const_shared_bitmap_info_t; |
1296c31f DB |
4574 | |
4575 | static htab_t shared_bitmap_table; | |
4576 | ||
4577 | /* Hash function for a shared_bitmap_info_t */ | |
4578 | ||
4579 | static hashval_t | |
4580 | shared_bitmap_hash (const void *p) | |
4581 | { | |
e5cfc29f | 4582 | const_shared_bitmap_info_t const bi = (const_shared_bitmap_info_t) p; |
1296c31f DB |
4583 | return bi->hashcode; |
4584 | } | |
4585 | ||
4586 | /* Equality function for two shared_bitmap_info_t's. */ | |
4587 | ||
4588 | static int | |
4589 | shared_bitmap_eq (const void *p1, const void *p2) | |
4590 | { | |
e5cfc29f KG |
4591 | const_shared_bitmap_info_t const sbi1 = (const_shared_bitmap_info_t) p1; |
4592 | const_shared_bitmap_info_t const sbi2 = (const_shared_bitmap_info_t) p2; | |
1296c31f DB |
4593 | return bitmap_equal_p (sbi1->pt_vars, sbi2->pt_vars); |
4594 | } | |
4595 | ||
4596 | /* Lookup a bitmap in the shared bitmap hashtable, and return an already | |
4597 | existing instance if there is one, NULL otherwise. */ | |
4598 | ||
4599 | static bitmap | |
4600 | shared_bitmap_lookup (bitmap pt_vars) | |
4601 | { | |
4602 | void **slot; | |
4603 | struct shared_bitmap_info sbi; | |
4604 | ||
4605 | sbi.pt_vars = pt_vars; | |
4606 | sbi.hashcode = bitmap_hash (pt_vars); | |
7b765bed | 4607 | |
1296c31f DB |
4608 | slot = htab_find_slot_with_hash (shared_bitmap_table, &sbi, |
4609 | sbi.hashcode, NO_INSERT); | |
4610 | if (!slot) | |
4611 | return NULL; | |
4612 | else | |
4613 | return ((shared_bitmap_info_t) *slot)->pt_vars; | |
4614 | } | |
4615 | ||
4616 | ||
4617 | /* Add a bitmap to the shared bitmap hashtable. */ | |
4618 | ||
4619 | static void | |
4620 | shared_bitmap_add (bitmap pt_vars) | |
4621 | { | |
4622 | void **slot; | |
4623 | shared_bitmap_info_t sbi = XNEW (struct shared_bitmap_info); | |
7b765bed | 4624 | |
1296c31f DB |
4625 | sbi->pt_vars = pt_vars; |
4626 | sbi->hashcode = bitmap_hash (pt_vars); | |
7b765bed | 4627 | |
1296c31f DB |
4628 | slot = htab_find_slot_with_hash (shared_bitmap_table, sbi, |
4629 | sbi->hashcode, INSERT); | |
4630 | gcc_assert (!*slot); | |
4631 | *slot = (void *) sbi; | |
4632 | } | |
4633 | ||
4634 | ||
910fdc79 | 4635 | /* Set bits in INTO corresponding to the variable uids in solution set |
21392f19 DB |
4636 | FROM, which came from variable PTR. |
4637 | For variables that are actually dereferenced, we also use type | |
6bdff197 DB |
4638 | based alias analysis to prune the points-to sets. |
4639 | IS_DEREFED is true if PTR was directly dereferenced, which we use to | |
058dcc25 ILT |
4640 | help determine whether we are we are allowed to prune using TBAA. |
4641 | If NO_TBAA_PRUNING is true, we do not perform any TBAA pruning of | |
4642 | the from set. */ | |
910fdc79 DB |
4643 | |
4644 | static void | |
058dcc25 ILT |
4645 | set_uids_in_ptset (tree ptr, bitmap into, bitmap from, bool is_derefed, |
4646 | bool no_tbaa_pruning) | |
910fdc79 DB |
4647 | { |
4648 | unsigned int i; | |
4649 | bitmap_iterator bi; | |
f83ca251 RG |
4650 | |
4651 | gcc_assert (POINTER_TYPE_P (TREE_TYPE (ptr))); | |
910fdc79 DB |
4652 | |
4653 | EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi) | |
4654 | { | |
4655 | varinfo_t vi = get_varinfo (i); | |
c58936b6 | 4656 | |
e8ca4159 DN |
4657 | /* The only artificial variables that are allowed in a may-alias |
4658 | set are heap variables. */ | |
4659 | if (vi->is_artificial_var && !vi->is_heap_var) | |
4660 | continue; | |
c58936b6 | 4661 | |
5611cf0b RG |
4662 | if (TREE_CODE (vi->decl) == VAR_DECL |
4663 | || TREE_CODE (vi->decl) == PARM_DECL | |
4664 | || TREE_CODE (vi->decl) == RESULT_DECL) | |
58b82d2b | 4665 | { |
5611cf0b RG |
4666 | /* Just add VI->DECL to the alias set. |
4667 | Don't type prune artificial vars. */ | |
4668 | if (vi->is_artificial_var) | |
4669 | bitmap_set_bit (into, DECL_UID (vi->decl)); | |
e8ca4159 DN |
4670 | else |
4671 | { | |
5611cf0b RG |
4672 | alias_set_type var_alias_set, ptr_alias_set; |
4673 | var_alias_set = get_alias_set (vi->decl); | |
4674 | ptr_alias_set = get_alias_set (TREE_TYPE (TREE_TYPE (ptr))); | |
4675 | if (no_tbaa_pruning | |
4676 | || (!is_derefed && !vi->directly_dereferenced) | |
4677 | || alias_sets_conflict_p (ptr_alias_set, var_alias_set)) | |
4678 | bitmap_set_bit (into, DECL_UID (vi->decl)); | |
e8ca4159 DN |
4679 | } |
4680 | } | |
910fdc79 DB |
4681 | } |
4682 | } | |
e8ca4159 DN |
4683 | |
4684 | ||
4685 | static bool have_alias_info = false; | |
910fdc79 | 4686 | |
c58936b6 DB |
4687 | /* The list of SMT's that are in use by our pointer variables. This |
4688 | is the set of SMT's for all pointers that can point to anything. */ | |
4689 | static bitmap used_smts; | |
4690 | ||
4691 | /* Due to the ordering of points-to set calculation and SMT | |
4692 | calculation being a bit co-dependent, we can't just calculate SMT | |
4693 | used info whenever we want, we have to calculate it around the time | |
4694 | that find_what_p_points_to is called. */ | |
c58936b6 DB |
4695 | |
4696 | /* Mark which SMT's are in use by points-to anything variables. */ | |
4697 | ||
e5ebbea5 | 4698 | void |
c58936b6 DB |
4699 | set_used_smts (void) |
4700 | { | |
4701 | int i; | |
4702 | varinfo_t vi; | |
3e5937d7 | 4703 | used_smts = BITMAP_ALLOC (&pta_obstack); |
c58936b6 DB |
4704 | |
4705 | for (i = 0; VEC_iterate (varinfo_t, varmap, i, vi); i++) | |
4706 | { | |
4707 | tree var = vi->decl; | |
7b765bed | 4708 | varinfo_t withsolution = get_varinfo (find (i)); |
c58936b6 | 4709 | tree smt; |
c58936b6 DB |
4710 | var_ann_t va; |
4711 | struct ptr_info_def *pi = NULL; | |
3e5937d7 | 4712 | |
ff3add8d DB |
4713 | /* For parm decls, the pointer info may be under the default |
4714 | def. */ | |
4715 | if (TREE_CODE (vi->decl) == PARM_DECL | |
4716 | && gimple_default_def (cfun, var)) | |
4717 | pi = SSA_NAME_PTR_INFO (gimple_default_def (cfun, var)); | |
4718 | else if (TREE_CODE (var) == SSA_NAME) | |
c58936b6 DB |
4719 | pi = SSA_NAME_PTR_INFO (var); |
4720 | ||
7b765bed DB |
4721 | /* Skip the special variables and those that can't be aliased. */ |
4722 | if (vi->is_special_var | |
3e5937d7 DB |
4723 | || !SSA_VAR_P (var) |
4724 | || (pi && !pi->is_dereferenced) | |
ff3add8d DB |
4725 | || (TREE_CODE (var) == VAR_DECL && !may_be_aliased (var)) |
4726 | || !POINTER_TYPE_P (TREE_TYPE (var))) | |
c58936b6 DB |
4727 | continue; |
4728 | ||
4729 | if (TREE_CODE (var) == SSA_NAME) | |
4730 | var = SSA_NAME_VAR (var); | |
4731 | ||
4732 | va = var_ann (var); | |
4733 | if (!va) | |
4734 | continue; | |
4735 | ||
4736 | smt = va->symbol_mem_tag; | |
7b765bed | 4737 | if (smt && bitmap_bit_p (withsolution->solution, anything_id)) |
ff3add8d | 4738 | bitmap_set_bit (used_smts, DECL_UID (smt)); |
c58936b6 | 4739 | } |
c58936b6 DB |
4740 | } |
4741 | ||
1296c31f | 4742 | /* Merge the necessary SMT's into the bitmap INTO, which is |
c58936b6 DB |
4743 | P's varinfo. This involves merging all SMT's that are a subset of |
4744 | the SMT necessary for P. */ | |
4745 | ||
4746 | static void | |
1296c31f | 4747 | merge_smts_into (tree p, bitmap solution) |
c58936b6 | 4748 | { |
c58936b6 | 4749 | tree smt; |
306219a2 | 4750 | bitmap aliases; |
c58936b6 DB |
4751 | tree var = p; |
4752 | ||
4753 | if (TREE_CODE (p) == SSA_NAME) | |
4754 | var = SSA_NAME_VAR (p); | |
4755 | ||
4756 | smt = var_ann (var)->symbol_mem_tag; | |
4757 | if (smt) | |
4758 | { | |
17d2c090 | 4759 | /* The smt itself isn't included in its aliases. */ |
1296c31f | 4760 | bitmap_set_bit (solution, DECL_UID (smt)); |
c58936b6 | 4761 | |
306219a2 | 4762 | aliases = MTAG_ALIASES (smt); |
c58936b6 | 4763 | if (aliases) |
7b765bed | 4764 | bitmap_ior_into (solution, aliases); |
c58936b6 DB |
4765 | } |
4766 | } | |
4767 | ||
910fdc79 | 4768 | /* Given a pointer variable P, fill in its points-to set, or return |
3e5937d7 | 4769 | false if we can't. |
c58936b6 | 4770 | Rather than return false for variables that point-to anything, we |
7b765bed | 4771 | instead find the corresponding SMT, and merge in its aliases. In |
c58936b6 DB |
4772 | addition to these aliases, we also set the bits for the SMT's |
4773 | themselves and their subsets, as SMT's are still in use by | |
4774 | non-SSA_NAME's, and pruning may eliminate every one of their | |
4775 | aliases. In such a case, if we did not include the right set of | |
4776 | SMT's in the points-to set of the variable, we'd end up with | |
4777 | statements that do not conflict but should. */ | |
910fdc79 DB |
4778 | |
4779 | bool | |
4780 | find_what_p_points_to (tree p) | |
4781 | { | |
7cc92f92 | 4782 | tree lookup_p = p; |
3e5937d7 | 4783 | varinfo_t vi; |
e8ca4159 | 4784 | |
910fdc79 DB |
4785 | if (!have_alias_info) |
4786 | return false; | |
e8ca4159 | 4787 | |
7cc92f92 RG |
4788 | /* For parameters, get at the points-to set for the actual parm |
4789 | decl. */ | |
c58936b6 DB |
4790 | if (TREE_CODE (p) == SSA_NAME |
4791 | && TREE_CODE (SSA_NAME_VAR (p)) == PARM_DECL | |
38635499 | 4792 | && SSA_NAME_IS_DEFAULT_DEF (p)) |
7cc92f92 RG |
4793 | lookup_p = SSA_NAME_VAR (p); |
4794 | ||
15814ba0 PB |
4795 | vi = lookup_vi_for_tree (lookup_p); |
4796 | if (vi) | |
910fdc79 | 4797 | { |
910fdc79 DB |
4798 | if (vi->is_artificial_var) |
4799 | return false; | |
4800 | ||
e8ca4159 | 4801 | /* See if this is a field or a structure. */ |
910fdc79 DB |
4802 | if (vi->size != vi->fullsize) |
4803 | { | |
e8ca4159 DN |
4804 | /* Nothing currently asks about structure fields directly, |
4805 | but when they do, we need code here to hand back the | |
4806 | points-to set. */ | |
5611cf0b | 4807 | return false; |
c58936b6 | 4808 | } |
910fdc79 DB |
4809 | else |
4810 | { | |
4811 | struct ptr_info_def *pi = get_ptr_info (p); | |
4812 | unsigned int i; | |
4813 | bitmap_iterator bi; | |
c58936b6 | 4814 | bool was_pt_anything = false; |
1296c31f DB |
4815 | bitmap finished_solution; |
4816 | bitmap result; | |
7b765bed | 4817 | |
c58936b6 DB |
4818 | if (!pi->is_dereferenced) |
4819 | return false; | |
910fdc79 DB |
4820 | |
4821 | /* This variable may have been collapsed, let's get the real | |
4822 | variable. */ | |
3e5937d7 | 4823 | vi = get_varinfo (find (vi->id)); |
c58936b6 | 4824 | |
e8ca4159 DN |
4825 | /* Translate artificial variables into SSA_NAME_PTR_INFO |
4826 | attributes. */ | |
910fdc79 DB |
4827 | EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi) |
4828 | { | |
e8ca4159 DN |
4829 | varinfo_t vi = get_varinfo (i); |
4830 | ||
4831 | if (vi->is_artificial_var) | |
4832 | { | |
4833 | /* FIXME. READONLY should be handled better so that | |
a4174ebf | 4834 | flow insensitive aliasing can disregard writable |
e8ca4159 DN |
4835 | aliases. */ |
4836 | if (vi->id == nothing_id) | |
4837 | pi->pt_null = 1; | |
4838 | else if (vi->id == anything_id) | |
c58936b6 | 4839 | was_pt_anything = 1; |
e8ca4159 | 4840 | else if (vi->id == readonly_id) |
c58936b6 | 4841 | was_pt_anything = 1; |
e8ca4159 | 4842 | else if (vi->id == integer_id) |
c58936b6 | 4843 | was_pt_anything = 1; |
e8ca4159 DN |
4844 | else if (vi->is_heap_var) |
4845 | pi->pt_global_mem = 1; | |
4846 | } | |
910fdc79 | 4847 | } |
e8ca4159 | 4848 | |
1296c31f | 4849 | /* Share the final set of variables when possible. */ |
1296c31f DB |
4850 | finished_solution = BITMAP_GGC_ALLOC (); |
4851 | stats.points_to_sets_created++; | |
7b765bed | 4852 | |
73fd4ad6 EB |
4853 | /* Instead of using pt_anything, we merge in the SMT aliases |
4854 | for the underlying SMT. In addition, if they could have | |
59e6913a | 4855 | pointed to anything, they could point to global memory. */ |
1296c31f | 4856 | if (was_pt_anything) |
c58936b6 | 4857 | { |
1296c31f DB |
4858 | merge_smts_into (p, finished_solution); |
4859 | pi->pt_global_mem = 1; | |
4860 | } | |
7b765bed | 4861 | |
f83ca251 | 4862 | set_uids_in_ptset (p, finished_solution, vi->solution, |
058dcc25 ILT |
4863 | vi->directly_dereferenced, |
4864 | vi->no_tbaa_pruning); | |
1296c31f DB |
4865 | result = shared_bitmap_lookup (finished_solution); |
4866 | ||
4867 | if (!result) | |
4868 | { | |
4869 | shared_bitmap_add (finished_solution); | |
4870 | pi->pt_vars = finished_solution; | |
c58936b6 DB |
4871 | } |
4872 | else | |
4873 | { | |
1296c31f DB |
4874 | pi->pt_vars = result; |
4875 | bitmap_clear (finished_solution); | |
c58936b6 | 4876 | } |
e8ca4159 DN |
4877 | |
4878 | if (bitmap_empty_p (pi->pt_vars)) | |
4879 | pi->pt_vars = NULL; | |
4880 | ||
910fdc79 DB |
4881 | return true; |
4882 | } | |
4883 | } | |
e8ca4159 | 4884 | |
910fdc79 DB |
4885 | return false; |
4886 | } | |
4887 | ||
63a4ef6f | 4888 | |
910fdc79 | 4889 | |
63a4ef6f DN |
4890 | /* Dump points-to information to OUTFILE. */ |
4891 | ||
4892 | void | |
910fdc79 DB |
4893 | dump_sa_points_to_info (FILE *outfile) |
4894 | { | |
910fdc79 | 4895 | unsigned int i; |
63a4ef6f | 4896 | |
e8ca4159 | 4897 | fprintf (outfile, "\nPoints-to sets\n\n"); |
63a4ef6f | 4898 | |
910fdc79 DB |
4899 | if (dump_flags & TDF_STATS) |
4900 | { | |
4901 | fprintf (outfile, "Stats:\n"); | |
63a4ef6f | 4902 | fprintf (outfile, "Total vars: %d\n", stats.total_vars); |
3e5937d7 DB |
4903 | fprintf (outfile, "Non-pointer vars: %d\n", |
4904 | stats.nonpointer_vars); | |
63a4ef6f DN |
4905 | fprintf (outfile, "Statically unified vars: %d\n", |
4906 | stats.unified_vars_static); | |
63a4ef6f DN |
4907 | fprintf (outfile, "Dynamically unified vars: %d\n", |
4908 | stats.unified_vars_dynamic); | |
4909 | fprintf (outfile, "Iterations: %d\n", stats.iterations); | |
4ee00913 | 4910 | fprintf (outfile, "Number of edges: %d\n", stats.num_edges); |
3e5937d7 DB |
4911 | fprintf (outfile, "Number of implicit edges: %d\n", |
4912 | stats.num_implicit_edges); | |
910fdc79 | 4913 | } |
63a4ef6f | 4914 | |
910fdc79 DB |
4915 | for (i = 0; i < VEC_length (varinfo_t, varmap); i++) |
4916 | dump_solution_for_var (outfile, i); | |
4917 | } | |
4918 | ||
4919 | ||
63a4ef6f DN |
4920 | /* Debug points-to information to stderr. */ |
4921 | ||
4922 | void | |
4923 | debug_sa_points_to_info (void) | |
4924 | { | |
4925 | dump_sa_points_to_info (stderr); | |
4926 | } | |
4927 | ||
4928 | ||
910fdc79 DB |
4929 | /* Initialize the always-existing constraint variables for NULL |
4930 | ANYTHING, READONLY, and INTEGER */ | |
4931 | ||
4932 | static void | |
4933 | init_base_vars (void) | |
4934 | { | |
4935 | struct constraint_expr lhs, rhs; | |
4936 | ||
4937 | /* Create the NULL variable, used to represent that a variable points | |
4938 | to NULL. */ | |
4939 | nothing_tree = create_tmp_var_raw (void_type_node, "NULL"); | |
3e5937d7 DB |
4940 | var_nothing = new_var_info (nothing_tree, 0, "NULL"); |
4941 | insert_vi_for_tree (nothing_tree, var_nothing); | |
910fdc79 DB |
4942 | var_nothing->is_artificial_var = 1; |
4943 | var_nothing->offset = 0; | |
4944 | var_nothing->size = ~0; | |
4945 | var_nothing->fullsize = ~0; | |
13c2c08b | 4946 | var_nothing->is_special_var = 1; |
910fdc79 | 4947 | nothing_id = 0; |
b5efa470 | 4948 | VEC_safe_push (varinfo_t, heap, varmap, var_nothing); |
910fdc79 DB |
4949 | |
4950 | /* Create the ANYTHING variable, used to represent that a variable | |
4951 | points to some unknown piece of memory. */ | |
4952 | anything_tree = create_tmp_var_raw (void_type_node, "ANYTHING"); | |
3e5937d7 DB |
4953 | var_anything = new_var_info (anything_tree, 1, "ANYTHING"); |
4954 | insert_vi_for_tree (anything_tree, var_anything); | |
910fdc79 DB |
4955 | var_anything->is_artificial_var = 1; |
4956 | var_anything->size = ~0; | |
4957 | var_anything->offset = 0; | |
4958 | var_anything->next = NULL; | |
4959 | var_anything->fullsize = ~0; | |
13c2c08b | 4960 | var_anything->is_special_var = 1; |
910fdc79 DB |
4961 | anything_id = 1; |
4962 | ||
4963 | /* Anything points to anything. This makes deref constraints just | |
c58936b6 | 4964 | work in the presence of linked list and other p = *p type loops, |
910fdc79 | 4965 | by saying that *ANYTHING = ANYTHING. */ |
b5efa470 | 4966 | VEC_safe_push (varinfo_t, heap, varmap, var_anything); |
910fdc79 DB |
4967 | lhs.type = SCALAR; |
4968 | lhs.var = anything_id; | |
4969 | lhs.offset = 0; | |
3e5937d7 | 4970 | rhs.type = ADDRESSOF; |
910fdc79 DB |
4971 | rhs.var = anything_id; |
4972 | rhs.offset = 0; | |
e8ca4159 | 4973 | |
a5eadacc DB |
4974 | /* This specifically does not use process_constraint because |
4975 | process_constraint ignores all anything = anything constraints, since all | |
4976 | but this one are redundant. */ | |
b5efa470 | 4977 | VEC_safe_push (constraint_t, heap, constraints, new_constraint (lhs, rhs)); |
c58936b6 | 4978 | |
910fdc79 DB |
4979 | /* Create the READONLY variable, used to represent that a variable |
4980 | points to readonly memory. */ | |
4981 | readonly_tree = create_tmp_var_raw (void_type_node, "READONLY"); | |
3e5937d7 | 4982 | var_readonly = new_var_info (readonly_tree, 2, "READONLY"); |
910fdc79 DB |
4983 | var_readonly->is_artificial_var = 1; |
4984 | var_readonly->offset = 0; | |
4985 | var_readonly->size = ~0; | |
4986 | var_readonly->fullsize = ~0; | |
4987 | var_readonly->next = NULL; | |
13c2c08b | 4988 | var_readonly->is_special_var = 1; |
3e5937d7 | 4989 | insert_vi_for_tree (readonly_tree, var_readonly); |
910fdc79 | 4990 | readonly_id = 2; |
b5efa470 | 4991 | VEC_safe_push (varinfo_t, heap, varmap, var_readonly); |
910fdc79 DB |
4992 | |
4993 | /* readonly memory points to anything, in order to make deref | |
4994 | easier. In reality, it points to anything the particular | |
4995 | readonly variable can point to, but we don't track this | |
607fb860 | 4996 | separately. */ |
910fdc79 DB |
4997 | lhs.type = SCALAR; |
4998 | lhs.var = readonly_id; | |
4999 | lhs.offset = 0; | |
3e5937d7 | 5000 | rhs.type = ADDRESSOF; |
910fdc79 DB |
5001 | rhs.var = anything_id; |
5002 | rhs.offset = 0; | |
c58936b6 | 5003 | |
910fdc79 | 5004 | process_constraint (new_constraint (lhs, rhs)); |
c58936b6 | 5005 | |
910fdc79 DB |
5006 | /* Create the INTEGER variable, used to represent that a variable points |
5007 | to an INTEGER. */ | |
5008 | integer_tree = create_tmp_var_raw (void_type_node, "INTEGER"); | |
3e5937d7 DB |
5009 | var_integer = new_var_info (integer_tree, 3, "INTEGER"); |
5010 | insert_vi_for_tree (integer_tree, var_integer); | |
910fdc79 DB |
5011 | var_integer->is_artificial_var = 1; |
5012 | var_integer->size = ~0; | |
5013 | var_integer->fullsize = ~0; | |
5014 | var_integer->offset = 0; | |
5015 | var_integer->next = NULL; | |
13c2c08b | 5016 | var_integer->is_special_var = 1; |
910fdc79 | 5017 | integer_id = 3; |
b5efa470 | 5018 | VEC_safe_push (varinfo_t, heap, varmap, var_integer); |
a5eadacc | 5019 | |
21392f19 DB |
5020 | /* INTEGER = ANYTHING, because we don't know where a dereference of |
5021 | a random integer will point to. */ | |
a5eadacc DB |
5022 | lhs.type = SCALAR; |
5023 | lhs.var = integer_id; | |
5024 | lhs.offset = 0; | |
3e5937d7 | 5025 | rhs.type = ADDRESSOF; |
a5eadacc DB |
5026 | rhs.var = anything_id; |
5027 | rhs.offset = 0; | |
5028 | process_constraint (new_constraint (lhs, rhs)); | |
c58936b6 | 5029 | } |
910fdc79 | 5030 | |
4ee00913 | 5031 | /* Initialize things necessary to perform PTA */ |
910fdc79 | 5032 | |
4ee00913 DB |
5033 | static void |
5034 | init_alias_vars (void) | |
910fdc79 | 5035 | { |
3e5937d7 DB |
5036 | bitmap_obstack_initialize (&pta_obstack); |
5037 | bitmap_obstack_initialize (&oldpta_obstack); | |
4ee00913 | 5038 | bitmap_obstack_initialize (&predbitmap_obstack); |
910fdc79 | 5039 | |
c58936b6 | 5040 | constraint_pool = create_alloc_pool ("Constraint pool", |
910fdc79 DB |
5041 | sizeof (struct constraint), 30); |
5042 | variable_info_pool = create_alloc_pool ("Variable info pool", | |
5043 | sizeof (struct variable_info), 30); | |
b5efa470 DB |
5044 | constraints = VEC_alloc (constraint_t, heap, 8); |
5045 | varmap = VEC_alloc (varinfo_t, heap, 8); | |
15814ba0 | 5046 | vi_for_tree = pointer_map_create (); |
3e5937d7 | 5047 | |
910fdc79 | 5048 | memset (&stats, 0, sizeof (stats)); |
1296c31f DB |
5049 | shared_bitmap_table = htab_create (511, shared_bitmap_hash, |
5050 | shared_bitmap_eq, free); | |
910fdc79 | 5051 | init_base_vars (); |
4ee00913 DB |
5052 | } |
5053 | ||
3e5937d7 DB |
5054 | /* Remove the REF and ADDRESS edges from GRAPH, as well as all the |
5055 | predecessor edges. */ | |
5056 | ||
5057 | static void | |
5058 | remove_preds_and_fake_succs (constraint_graph_t graph) | |
5059 | { | |
5060 | unsigned int i; | |
5061 | ||
5062 | /* Clear the implicit ref and address nodes from the successor | |
5063 | lists. */ | |
5064 | for (i = 0; i < FIRST_REF_NODE; i++) | |
5065 | { | |
5066 | if (graph->succs[i]) | |
5067 | bitmap_clear_range (graph->succs[i], FIRST_REF_NODE, | |
5068 | FIRST_REF_NODE * 2); | |
5069 | } | |
5070 | ||
5071 | /* Free the successor list for the non-ref nodes. */ | |
5072 | for (i = FIRST_REF_NODE; i < graph->size; i++) | |
5073 | { | |
5074 | if (graph->succs[i]) | |
5075 | BITMAP_FREE (graph->succs[i]); | |
5076 | } | |
5077 | ||
5078 | /* Now reallocate the size of the successor list as, and blow away | |
5079 | the predecessor bitmaps. */ | |
5080 | graph->size = VEC_length (varinfo_t, varmap); | |
c22940cd | 5081 | graph->succs = XRESIZEVEC (bitmap, graph->succs, graph->size); |
3e5937d7 DB |
5082 | |
5083 | free (graph->implicit_preds); | |
5084 | graph->implicit_preds = NULL; | |
5085 | free (graph->preds); | |
5086 | graph->preds = NULL; | |
5087 | bitmap_obstack_release (&predbitmap_obstack); | |
5088 | } | |
5089 | ||
058dcc25 ILT |
5090 | /* Compute the set of variables we can't TBAA prune. */ |
5091 | ||
5092 | static void | |
5093 | compute_tbaa_pruning (void) | |
5094 | { | |
5095 | unsigned int size = VEC_length (varinfo_t, varmap); | |
5096 | unsigned int i; | |
5097 | bool any; | |
5098 | ||
5099 | changed_count = 0; | |
5100 | changed = sbitmap_alloc (size); | |
5101 | sbitmap_zero (changed); | |
5102 | ||
5103 | /* Mark all initial no_tbaa_pruning nodes as changed. */ | |
5104 | any = false; | |
5105 | for (i = 0; i < size; ++i) | |
5106 | { | |
5107 | varinfo_t ivi = get_varinfo (i); | |
5108 | ||
5109 | if (find (i) == i && ivi->no_tbaa_pruning) | |
5110 | { | |
5111 | any = true; | |
5112 | if ((graph->succs[i] && !bitmap_empty_p (graph->succs[i])) | |
5113 | || VEC_length (constraint_t, graph->complex[i]) > 0) | |
5114 | { | |
5115 | SET_BIT (changed, i); | |
5116 | ++changed_count; | |
5117 | } | |
5118 | } | |
5119 | } | |
5120 | ||
5121 | while (changed_count > 0) | |
5122 | { | |
5123 | struct topo_info *ti = init_topo_info (); | |
5124 | ++stats.iterations; | |
5125 | ||
058dcc25 ILT |
5126 | compute_topo_order (graph, ti); |
5127 | ||
5128 | while (VEC_length (unsigned, ti->topo_order) != 0) | |
5129 | { | |
5130 | bitmap_iterator bi; | |
5131 | ||
5132 | i = VEC_pop (unsigned, ti->topo_order); | |
5133 | ||
5134 | /* If this variable is not a representative, skip it. */ | |
5135 | if (find (i) != i) | |
5136 | continue; | |
5137 | ||
5138 | /* If the node has changed, we need to process the complex | |
5139 | constraints and outgoing edges again. */ | |
5140 | if (TEST_BIT (changed, i)) | |
5141 | { | |
5142 | unsigned int j; | |
5143 | constraint_t c; | |
5144 | VEC(constraint_t,heap) *complex = graph->complex[i]; | |
5145 | ||
5146 | RESET_BIT (changed, i); | |
5147 | --changed_count; | |
5148 | ||
5149 | /* Process the complex copy constraints. */ | |
5150 | for (j = 0; VEC_iterate (constraint_t, complex, j, c); ++j) | |
5151 | { | |
5152 | if (c->lhs.type == SCALAR && c->rhs.type == SCALAR) | |
5153 | { | |
5154 | varinfo_t lhsvi = get_varinfo (find (c->lhs.var)); | |
5155 | ||
5156 | if (!lhsvi->no_tbaa_pruning) | |
5157 | { | |
5158 | lhsvi->no_tbaa_pruning = true; | |
5159 | if (!TEST_BIT (changed, lhsvi->id)) | |
5160 | { | |
5161 | SET_BIT (changed, lhsvi->id); | |
5162 | ++changed_count; | |
5163 | } | |
5164 | } | |
5165 | } | |
5166 | } | |
5167 | ||
5168 | /* Propagate to all successors. */ | |
5169 | EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i], 0, j, bi) | |
5170 | { | |
5171 | unsigned int to = find (j); | |
5172 | varinfo_t tovi = get_varinfo (to); | |
5173 | ||
5174 | /* Don't propagate to ourselves. */ | |
5175 | if (to == i) | |
5176 | continue; | |
5177 | ||
5178 | if (!tovi->no_tbaa_pruning) | |
5179 | { | |
5180 | tovi->no_tbaa_pruning = true; | |
5181 | if (!TEST_BIT (changed, to)) | |
5182 | { | |
5183 | SET_BIT (changed, to); | |
5184 | ++changed_count; | |
5185 | } | |
5186 | } | |
5187 | } | |
5188 | } | |
5189 | } | |
5190 | ||
5191 | free_topo_info (ti); | |
058dcc25 ILT |
5192 | } |
5193 | ||
5194 | sbitmap_free (changed); | |
5195 | ||
5196 | if (any) | |
5197 | { | |
5198 | for (i = 0; i < size; ++i) | |
5199 | { | |
5200 | varinfo_t ivi = get_varinfo (i); | |
5201 | varinfo_t ivip = get_varinfo (find (i)); | |
5202 | ||
5203 | if (ivip->no_tbaa_pruning) | |
5204 | { | |
5205 | tree var = ivi->decl; | |
5206 | ||
5207 | if (TREE_CODE (var) == SSA_NAME) | |
5208 | var = SSA_NAME_VAR (var); | |
5209 | ||
5210 | if (POINTER_TYPE_P (TREE_TYPE (var))) | |
5211 | { | |
5212 | DECL_NO_TBAA_P (var) = 1; | |
5213 | ||
5214 | /* Tell the RTL layer that this pointer can alias | |
5215 | anything. */ | |
5216 | DECL_POINTER_ALIAS_SET (var) = 0; | |
5217 | } | |
5218 | } | |
5219 | } | |
5220 | } | |
5221 | } | |
5222 | ||
4ee00913 DB |
5223 | /* Create points-to sets for the current function. See the comments |
5224 | at the start of the file for an algorithmic overview. */ | |
5225 | ||
5226 | void | |
5227 | compute_points_to_sets (struct alias_info *ai) | |
5228 | { | |
3e5937d7 | 5229 | struct scc_info *si; |
4ee00913 DB |
5230 | basic_block bb; |
5231 | ||
5232 | timevar_push (TV_TREE_PTA); | |
5233 | ||
5234 | init_alias_vars (); | |
c9fa8bd4 | 5235 | init_alias_heapvars (); |
910fdc79 DB |
5236 | |
5237 | intra_create_variable_infos (); | |
5238 | ||
5239 | /* Now walk all statements and derive aliases. */ | |
5240 | FOR_EACH_BB (bb) | |
5241 | { | |
c58936b6 | 5242 | block_stmt_iterator bsi; |
910fdc79 DB |
5243 | tree phi; |
5244 | ||
3d95caa4 | 5245 | for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) |
4ee00913 DB |
5246 | { |
5247 | if (is_gimple_reg (PHI_RESULT (phi))) | |
5248 | { | |
5249 | find_func_aliases (phi); | |
d37d06fe | 5250 | |
4ee00913 DB |
5251 | /* Update various related attributes like escaped |
5252 | addresses, pointer dereferences for loads and stores. | |
5253 | This is used when creating name tags and alias | |
5254 | sets. */ | |
5255 | update_alias_info (phi, ai); | |
5256 | } | |
5257 | } | |
910fdc79 | 5258 | |
058dcc25 | 5259 | for (bsi = bsi_start (bb); !bsi_end_p (bsi); ) |
4ee00913 DB |
5260 | { |
5261 | tree stmt = bsi_stmt (bsi); | |
21392f19 | 5262 | |
4ee00913 | 5263 | find_func_aliases (stmt); |
38635499 | 5264 | |
21392f19 DB |
5265 | /* Update various related attributes like escaped |
5266 | addresses, pointer dereferences for loads and stores. | |
5267 | This is used when creating name tags and alias | |
5268 | sets. */ | |
4ee00913 | 5269 | update_alias_info (stmt, ai); |
058dcc25 ILT |
5270 | |
5271 | /* The information in CHANGE_DYNAMIC_TYPE_EXPR nodes has now | |
5272 | been captured, and we can remove them. */ | |
5273 | if (TREE_CODE (stmt) == CHANGE_DYNAMIC_TYPE_EXPR) | |
5274 | bsi_remove (&bsi, true); | |
5275 | else | |
5276 | bsi_next (&bsi); | |
4ee00913 | 5277 | } |
910fdc79 DB |
5278 | } |
5279 | ||
910fdc79 DB |
5280 | |
5281 | if (dump_file) | |
5282 | { | |
e8ca4159 | 5283 | fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n"); |
910fdc79 DB |
5284 | dump_constraints (dump_file); |
5285 | } | |
c58936b6 | 5286 | |
21392f19 DB |
5287 | if (dump_file) |
5288 | fprintf (dump_file, | |
5289 | "\nCollapsing static cycles and doing variable " | |
7b765bed DB |
5290 | "substitution\n"); |
5291 | ||
5292 | init_graph (VEC_length (varinfo_t, varmap) * 2); | |
5293 | ||
5294 | if (dump_file) | |
5295 | fprintf (dump_file, "Building predecessor graph\n"); | |
3e5937d7 | 5296 | build_pred_graph (); |
7b765bed DB |
5297 | |
5298 | if (dump_file) | |
5299 | fprintf (dump_file, "Detecting pointer and location " | |
5300 | "equivalences\n"); | |
3e5937d7 | 5301 | si = perform_var_substitution (graph); |
7b765bed DB |
5302 | |
5303 | if (dump_file) | |
5304 | fprintf (dump_file, "Rewriting constraints and unifying " | |
5305 | "variables\n"); | |
5306 | rewrite_constraints (graph, si); | |
3e5937d7 DB |
5307 | free_var_substitution_info (si); |
5308 | ||
5309 | build_succ_graph (); | |
7b765bed DB |
5310 | move_complex_constraints (graph); |
5311 | ||
5312 | if (dump_file) | |
5313 | fprintf (dump_file, "Uniting pointer but not location equivalent " | |
5314 | "variables\n"); | |
5315 | unite_pointer_equivalences (graph); | |
5316 | ||
5317 | if (dump_file) | |
5318 | fprintf (dump_file, "Finding indirect cycles\n"); | |
3e5937d7 | 5319 | find_indirect_cycles (graph); |
c58936b6 | 5320 | |
3e5937d7 DB |
5321 | /* Implicit nodes and predecessors are no longer necessary at this |
5322 | point. */ | |
5323 | remove_preds_and_fake_succs (graph); | |
c58936b6 | 5324 | |
21392f19 | 5325 | if (dump_file) |
7b765bed | 5326 | fprintf (dump_file, "Solving graph\n"); |
c58936b6 | 5327 | |
21392f19 | 5328 | solve_graph (graph); |
c58936b6 | 5329 | |
058dcc25 ILT |
5330 | compute_tbaa_pruning (); |
5331 | ||
910fdc79 DB |
5332 | if (dump_file) |
5333 | dump_sa_points_to_info (dump_file); | |
c58936b6 | 5334 | |
910fdc79 | 5335 | have_alias_info = true; |
e8ca4159 DN |
5336 | |
5337 | timevar_pop (TV_TREE_PTA); | |
910fdc79 DB |
5338 | } |
5339 | ||
910fdc79 DB |
5340 | |
5341 | /* Delete created points-to sets. */ | |
5342 | ||
e8ca4159 DN |
5343 | void |
5344 | delete_points_to_sets (void) | |
910fdc79 | 5345 | { |
7b765bed | 5346 | unsigned int i; |
c58936b6 | 5347 | |
1296c31f | 5348 | htab_delete (shared_bitmap_table); |
3e5937d7 DB |
5349 | if (dump_file && (dump_flags & TDF_STATS)) |
5350 | fprintf (dump_file, "Points to sets created:%d\n", | |
5351 | stats.points_to_sets_created); | |
5352 | ||
15814ba0 | 5353 | pointer_map_destroy (vi_for_tree); |
3e5937d7 | 5354 | bitmap_obstack_release (&pta_obstack); |
b5efa470 | 5355 | VEC_free (constraint_t, heap, constraints); |
c58936b6 | 5356 | |
7b765bed | 5357 | for (i = 0; i < graph->size; i++) |
3e5937d7 | 5358 | VEC_free (constraint_t, heap, graph->complex[i]); |
285463b5 | 5359 | free (graph->complex); |
21392f19 | 5360 | |
3e5937d7 | 5361 | free (graph->rep); |
57250223 | 5362 | free (graph->succs); |
7b765bed DB |
5363 | free (graph->pe); |
5364 | free (graph->pe_rep); | |
3e5937d7 | 5365 | free (graph->indirect_cycles); |
b5efa470 DB |
5366 | free (graph); |
5367 | ||
5368 | VEC_free (varinfo_t, heap, varmap); | |
910fdc79 | 5369 | free_alloc_pool (variable_info_pool); |
c58936b6 | 5370 | free_alloc_pool (constraint_pool); |
910fdc79 DB |
5371 | have_alias_info = false; |
5372 | } | |
973162ec | 5373 | |
4ee00913 DB |
5374 | /* Return true if we should execute IPA PTA. */ |
5375 | static bool | |
5376 | gate_ipa_pta (void) | |
5377 | { | |
5378 | return (flag_unit_at_a_time != 0 | |
c58936b6 | 5379 | && flag_ipa_pta |
4ee00913 DB |
5380 | /* Don't bother doing anything if the program has errors. */ |
5381 | && !(errorcount || sorrycount)); | |
5382 | } | |
5383 | ||
5384 | /* Execute the driver for IPA PTA. */ | |
c2924966 | 5385 | static unsigned int |
4ee00913 DB |
5386 | ipa_pta_execute (void) |
5387 | { | |
5388 | struct cgraph_node *node; | |
3e5937d7 DB |
5389 | struct scc_info *si; |
5390 | ||
4ee00913 | 5391 | in_ipa_mode = 1; |
4cf4d6a3 | 5392 | init_alias_heapvars (); |
4ee00913 | 5393 | init_alias_vars (); |
c58936b6 | 5394 | |
4ee00913 DB |
5395 | for (node = cgraph_nodes; node; node = node->next) |
5396 | { | |
5397 | if (!node->analyzed || cgraph_is_master_clone (node)) | |
5398 | { | |
5399 | unsigned int varid; | |
c58936b6 DB |
5400 | |
5401 | varid = create_function_info_for (node->decl, | |
4ee00913 DB |
5402 | cgraph_node_name (node)); |
5403 | if (node->local.externally_visible) | |
5404 | { | |
5405 | varinfo_t fi = get_varinfo (varid); | |
5406 | for (; fi; fi = fi->next) | |
c58936b6 | 5407 | make_constraint_from_anything (fi); |
4ee00913 DB |
5408 | } |
5409 | } | |
5410 | } | |
5411 | for (node = cgraph_nodes; node; node = node->next) | |
5412 | { | |
5413 | if (node->analyzed && cgraph_is_master_clone (node)) | |
5414 | { | |
5576d6f2 | 5415 | struct function *func = DECL_STRUCT_FUNCTION (node->decl); |
4ee00913 DB |
5416 | basic_block bb; |
5417 | tree old_func_decl = current_function_decl; | |
5418 | if (dump_file) | |
c58936b6 DB |
5419 | fprintf (dump_file, |
5420 | "Generating constraints for %s\n", | |
5421 | cgraph_node_name (node)); | |
5576d6f2 | 5422 | push_cfun (func); |
4ee00913 DB |
5423 | current_function_decl = node->decl; |
5424 | ||
5576d6f2 | 5425 | FOR_EACH_BB_FN (bb, func) |
4ee00913 | 5426 | { |
c58936b6 | 5427 | block_stmt_iterator bsi; |
4ee00913 | 5428 | tree phi; |
c58936b6 | 5429 | |
3d95caa4 | 5430 | for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) |
4ee00913 DB |
5431 | { |
5432 | if (is_gimple_reg (PHI_RESULT (phi))) | |
5433 | { | |
5434 | find_func_aliases (phi); | |
5435 | } | |
5436 | } | |
c58936b6 | 5437 | |
4ee00913 DB |
5438 | for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) |
5439 | { | |
5440 | tree stmt = bsi_stmt (bsi); | |
5441 | find_func_aliases (stmt); | |
5442 | } | |
c58936b6 | 5443 | } |
4ee00913 | 5444 | current_function_decl = old_func_decl; |
c58936b6 | 5445 | pop_cfun (); |
4ee00913 DB |
5446 | } |
5447 | else | |
5448 | { | |
5449 | /* Make point to anything. */ | |
5450 | } | |
5451 | } | |
5452 | ||
4ee00913 DB |
5453 | if (dump_file) |
5454 | { | |
5455 | fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n"); | |
5456 | dump_constraints (dump_file); | |
5457 | } | |
c58936b6 | 5458 | |
21392f19 | 5459 | if (dump_file) |
c58936b6 | 5460 | fprintf (dump_file, |
21392f19 DB |
5461 | "\nCollapsing static cycles and doing variable " |
5462 | "substitution:\n"); | |
c58936b6 | 5463 | |
7b765bed | 5464 | init_graph (VEC_length (varinfo_t, varmap) * 2); |
3e5937d7 DB |
5465 | build_pred_graph (); |
5466 | si = perform_var_substitution (graph); | |
7b765bed | 5467 | rewrite_constraints (graph, si); |
3e5937d7 DB |
5468 | free_var_substitution_info (si); |
5469 | ||
5470 | build_succ_graph (); | |
7b765bed DB |
5471 | move_complex_constraints (graph); |
5472 | unite_pointer_equivalences (graph); | |
3e5937d7 DB |
5473 | find_indirect_cycles (graph); |
5474 | ||
5475 | /* Implicit nodes and predecessors are no longer necessary at this | |
5476 | point. */ | |
5477 | remove_preds_and_fake_succs (graph); | |
c58936b6 | 5478 | |
21392f19 | 5479 | if (dump_file) |
7b765bed | 5480 | fprintf (dump_file, "\nSolving graph\n"); |
c58936b6 | 5481 | |
21392f19 | 5482 | solve_graph (graph); |
c58936b6 | 5483 | |
4ee00913 DB |
5484 | if (dump_file) |
5485 | dump_sa_points_to_info (dump_file); | |
c58936b6 | 5486 | |
4ee00913 | 5487 | in_ipa_mode = 0; |
4cf4d6a3 DB |
5488 | delete_alias_heapvars (); |
5489 | delete_points_to_sets (); | |
c2924966 | 5490 | return 0; |
4ee00913 | 5491 | } |
c58936b6 | 5492 | |
8ddbbcae | 5493 | struct simple_ipa_opt_pass pass_ipa_pta = |
4ee00913 | 5494 | { |
8ddbbcae JH |
5495 | { |
5496 | SIMPLE_IPA_PASS, | |
4ee00913 DB |
5497 | "pta", /* name */ |
5498 | gate_ipa_pta, /* gate */ | |
5499 | ipa_pta_execute, /* execute */ | |
5500 | NULL, /* sub */ | |
5501 | NULL, /* next */ | |
5502 | 0, /* static_pass_number */ | |
5503 | TV_IPA_PTA, /* tv_id */ | |
5504 | 0, /* properties_required */ | |
5505 | 0, /* properties_provided */ | |
5506 | 0, /* properties_destroyed */ | |
5507 | 0, /* todo_flags_start */ | |
8ddbbcae JH |
5508 | TODO_update_ssa /* todo_flags_finish */ |
5509 | } | |
4ee00913 DB |
5510 | }; |
5511 | ||
c900f6aa | 5512 | /* Initialize the heapvar for statement mapping. */ |
83f676b3 | 5513 | void |
c900f6aa | 5514 | init_alias_heapvars (void) |
973162ec | 5515 | { |
c9fa8bd4 JH |
5516 | if (!heapvar_for_stmt) |
5517 | heapvar_for_stmt = htab_create_ggc (11, tree_map_hash, tree_map_eq, | |
5518 | NULL); | |
c900f6aa | 5519 | } |
973162ec | 5520 | |
c900f6aa DB |
5521 | void |
5522 | delete_alias_heapvars (void) | |
5523 | { | |
21392f19 | 5524 | htab_delete (heapvar_for_stmt); |
c9fa8bd4 | 5525 | heapvar_for_stmt = NULL; |
973162ec | 5526 | } |
c900f6aa | 5527 | |
c58936b6 | 5528 | |
c900f6aa | 5529 | #include "gt-tree-ssa-structalias.h" |