]>
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 | } |
4ee00913 | 1431 | else if (0 && dump_file && !(get_varinfo (j)->is_special_var)) |
910fdc79 | 1432 | fprintf (dump_file, "Untypesafe usage in do_sd_constraint\n"); |
c58936b6 | 1433 | |
910fdc79 | 1434 | } |
4cf4d6a3 | 1435 | |
4ee00913 | 1436 | done: |
910fdc79 DB |
1437 | /* If the LHS solution changed, mark the var as changed. */ |
1438 | if (flag) | |
1439 | { | |
1440 | get_varinfo (lhs)->solution = sol; | |
1441 | if (!TEST_BIT (changed, lhs)) | |
1442 | { | |
1443 | SET_BIT (changed, lhs); | |
1444 | changed_count++; | |
1445 | } | |
c58936b6 | 1446 | } |
910fdc79 DB |
1447 | } |
1448 | ||
1449 | /* Process a constraint C that represents *x = y. */ | |
1450 | ||
1451 | static void | |
57250223 | 1452 | do_ds_constraint (constraint_t c, bitmap delta) |
910fdc79 | 1453 | { |
7b765bed | 1454 | unsigned int rhs = c->rhs.var; |
910fdc79 DB |
1455 | bitmap sol = get_varinfo (rhs)->solution; |
1456 | unsigned int j; | |
1457 | bitmap_iterator bi; | |
1458 | ||
4ee00913 DB |
1459 | if (bitmap_bit_p (sol, anything_id)) |
1460 | { | |
1461 | EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi) | |
1462 | { | |
1463 | varinfo_t jvi = get_varinfo (j); | |
1464 | unsigned int t; | |
1465 | unsigned int loff = c->lhs.offset; | |
1466 | unsigned HOST_WIDE_INT fieldoffset = jvi->offset + loff; | |
1467 | varinfo_t v; | |
1468 | ||
1469 | v = first_vi_for_offset (get_varinfo (j), fieldoffset); | |
1470 | if (!v) | |
1471 | continue; | |
3e5937d7 | 1472 | t = find (v->id); |
c58936b6 | 1473 | |
4ee00913 DB |
1474 | if (!bitmap_bit_p (get_varinfo (t)->solution, anything_id)) |
1475 | { | |
1476 | bitmap_set_bit (get_varinfo (t)->solution, anything_id); | |
1477 | if (!TEST_BIT (changed, t)) | |
1478 | { | |
1479 | SET_BIT (changed, t); | |
1480 | changed_count++; | |
1481 | } | |
1482 | } | |
1483 | } | |
1484 | return; | |
1485 | } | |
4ee00913 | 1486 | |
910fdc79 DB |
1487 | /* For each member j of delta (Sol(x)), add an edge from y to j and |
1488 | union Sol(y) into Sol(j) */ | |
1489 | EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi) | |
1490 | { | |
13c2c08b | 1491 | unsigned HOST_WIDE_INT loff = c->lhs.offset; |
62e5bf5d | 1492 | if (type_safe (j, &loff) && !(get_varinfo (j)->is_special_var)) |
910fdc79 DB |
1493 | { |
1494 | varinfo_t v; | |
1495 | unsigned int t; | |
1496 | unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + loff; | |
57250223 | 1497 | bitmap tmp; |
c58936b6 | 1498 | |
910fdc79 | 1499 | v = first_vi_for_offset (get_varinfo (j), fieldoffset); |
8971094d DB |
1500 | if (!v) |
1501 | continue; | |
3e5937d7 | 1502 | t = find (v->id); |
57250223 DB |
1503 | tmp = get_varinfo (t)->solution; |
1504 | ||
7b765bed | 1505 | if (set_union_with_increment (tmp, sol, 0)) |
910fdc79 | 1506 | { |
57250223 DB |
1507 | get_varinfo (t)->solution = tmp; |
1508 | if (t == rhs) | |
1509 | sol = get_varinfo (rhs)->solution; | |
1510 | if (!TEST_BIT (changed, t)) | |
910fdc79 | 1511 | { |
57250223 DB |
1512 | SET_BIT (changed, t); |
1513 | changed_count++; | |
910fdc79 DB |
1514 | } |
1515 | } | |
57250223 | 1516 | } |
4ee00913 | 1517 | else if (0 && dump_file && !(get_varinfo (j)->is_special_var)) |
910fdc79 DB |
1518 | fprintf (dump_file, "Untypesafe usage in do_ds_constraint\n"); |
1519 | } | |
1520 | } | |
1521 | ||
3e5937d7 DB |
1522 | /* Handle a non-simple (simple meaning requires no iteration), |
1523 | constraint (IE *x = &y, x = *y, *x = y, and x = y with offsets involved). */ | |
c58936b6 | 1524 | |
910fdc79 DB |
1525 | static void |
1526 | do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta) | |
1527 | { | |
1528 | if (c->lhs.type == DEREF) | |
1529 | { | |
1530 | if (c->rhs.type == ADDRESSOF) | |
1531 | { | |
7b765bed | 1532 | gcc_unreachable(); |
910fdc79 DB |
1533 | } |
1534 | else | |
1535 | { | |
1536 | /* *x = y */ | |
57250223 | 1537 | do_ds_constraint (c, delta); |
910fdc79 DB |
1538 | } |
1539 | } | |
57250223 | 1540 | else if (c->rhs.type == DEREF) |
910fdc79 DB |
1541 | { |
1542 | /* x = *y */ | |
13c2c08b DB |
1543 | if (!(get_varinfo (c->lhs.var)->is_special_var)) |
1544 | do_sd_constraint (graph, c, delta); | |
910fdc79 | 1545 | } |
c58936b6 | 1546 | else |
57250223 | 1547 | { |
c58936b6 | 1548 | bitmap tmp; |
57250223 DB |
1549 | bitmap solution; |
1550 | bool flag = false; | |
57250223 | 1551 | |
62e5bf5d | 1552 | gcc_assert (c->rhs.type == SCALAR && c->lhs.type == SCALAR); |
7b765bed DB |
1553 | solution = get_varinfo (c->rhs.var)->solution; |
1554 | tmp = get_varinfo (c->lhs.var)->solution; | |
57250223 DB |
1555 | |
1556 | flag = set_union_with_increment (tmp, solution, c->rhs.offset); | |
c58936b6 | 1557 | |
57250223 DB |
1558 | if (flag) |
1559 | { | |
7b765bed DB |
1560 | get_varinfo (c->lhs.var)->solution = tmp; |
1561 | if (!TEST_BIT (changed, c->lhs.var)) | |
57250223 | 1562 | { |
7b765bed | 1563 | SET_BIT (changed, c->lhs.var); |
57250223 DB |
1564 | changed_count++; |
1565 | } | |
1566 | } | |
1567 | } | |
910fdc79 DB |
1568 | } |
1569 | ||
1570 | /* Initialize and return a new SCC info structure. */ | |
1571 | ||
1572 | static struct scc_info * | |
3e5937d7 | 1573 | init_scc_info (size_t size) |
910fdc79 | 1574 | { |
5ed6ace5 | 1575 | struct scc_info *si = XNEW (struct scc_info); |
3e5937d7 | 1576 | size_t i; |
910fdc79 DB |
1577 | |
1578 | si->current_index = 0; | |
1579 | si->visited = sbitmap_alloc (size); | |
1580 | sbitmap_zero (si->visited); | |
7b765bed DB |
1581 | si->deleted = sbitmap_alloc (size); |
1582 | sbitmap_zero (si->deleted); | |
3e5937d7 DB |
1583 | si->node_mapping = XNEWVEC (unsigned int, size); |
1584 | si->dfs = XCNEWVEC (unsigned int, size); | |
1585 | ||
1586 | for (i = 0; i < size; i++) | |
1587 | si->node_mapping[i] = i; | |
1588 | ||
740e80e8 | 1589 | si->scc_stack = VEC_alloc (unsigned, heap, 1); |
910fdc79 DB |
1590 | return si; |
1591 | } | |
1592 | ||
1593 | /* Free an SCC info structure pointed to by SI */ | |
1594 | ||
1595 | static void | |
1596 | free_scc_info (struct scc_info *si) | |
c58936b6 | 1597 | { |
910fdc79 | 1598 | sbitmap_free (si->visited); |
7b765bed | 1599 | sbitmap_free (si->deleted); |
3e5937d7 DB |
1600 | free (si->node_mapping); |
1601 | free (si->dfs); | |
740e80e8 | 1602 | VEC_free (unsigned, heap, si->scc_stack); |
3e5937d7 | 1603 | free (si); |
910fdc79 DB |
1604 | } |
1605 | ||
1606 | ||
3e5937d7 DB |
1607 | /* Find indirect cycles in GRAPH that occur, using strongly connected |
1608 | components, and note them in the indirect cycles map. | |
1609 | ||
1610 | This technique comes from Ben Hardekopf and Calvin Lin, | |
1611 | "It Pays to be Lazy: Fast and Accurate Pointer Analysis for Millions of | |
1612 | Lines of Code", submitted to PLDI 2007. */ | |
910fdc79 DB |
1613 | |
1614 | static void | |
3e5937d7 | 1615 | find_indirect_cycles (constraint_graph_t graph) |
910fdc79 DB |
1616 | { |
1617 | unsigned int i; | |
3e5937d7 DB |
1618 | unsigned int size = graph->size; |
1619 | struct scc_info *si = init_scc_info (size); | |
910fdc79 | 1620 | |
3e5937d7 DB |
1621 | for (i = 0; i < MIN (LAST_REF_NODE, size); i ++ ) |
1622 | if (!TEST_BIT (si->visited, i) && find (i) == i) | |
910fdc79 | 1623 | scc_visit (graph, si, i); |
c58936b6 | 1624 | |
910fdc79 DB |
1625 | free_scc_info (si); |
1626 | } | |
1627 | ||
1628 | /* Compute a topological ordering for GRAPH, and store the result in the | |
1629 | topo_info structure TI. */ | |
1630 | ||
c58936b6 | 1631 | static void |
910fdc79 DB |
1632 | compute_topo_order (constraint_graph_t graph, |
1633 | struct topo_info *ti) | |
1634 | { | |
1635 | unsigned int i; | |
7b765bed | 1636 | unsigned int size = graph->size; |
c58936b6 | 1637 | |
910fdc79 | 1638 | for (i = 0; i != size; ++i) |
3e5937d7 | 1639 | if (!TEST_BIT (ti->visited, i) && find (i) == i) |
910fdc79 DB |
1640 | topo_visit (graph, ti, i); |
1641 | } | |
1642 | ||
7b765bed DB |
1643 | /* Structure used to for hash value numbering of pointer equivalence |
1644 | classes. */ | |
1645 | ||
1646 | typedef struct equiv_class_label | |
1647 | { | |
1648 | unsigned int equivalence_class; | |
1649 | bitmap labels; | |
1650 | hashval_t hashcode; | |
1651 | } *equiv_class_label_t; | |
586de218 | 1652 | typedef const struct equiv_class_label *const_equiv_class_label_t; |
7b765bed DB |
1653 | |
1654 | /* A hashtable for mapping a bitmap of labels->pointer equivalence | |
1655 | classes. */ | |
1656 | static htab_t pointer_equiv_class_table; | |
1657 | ||
1658 | /* A hashtable for mapping a bitmap of labels->location equivalence | |
1659 | classes. */ | |
1660 | static htab_t location_equiv_class_table; | |
1661 | ||
1662 | /* Hash function for a equiv_class_label_t */ | |
1663 | ||
1664 | static hashval_t | |
1665 | equiv_class_label_hash (const void *p) | |
1666 | { | |
586de218 | 1667 | const_equiv_class_label_t const ecl = (const_equiv_class_label_t) p; |
7b765bed DB |
1668 | return ecl->hashcode; |
1669 | } | |
1670 | ||
1671 | /* Equality function for two equiv_class_label_t's. */ | |
1672 | ||
1673 | static int | |
1674 | equiv_class_label_eq (const void *p1, const void *p2) | |
1675 | { | |
586de218 KG |
1676 | const_equiv_class_label_t const eql1 = (const_equiv_class_label_t) p1; |
1677 | const_equiv_class_label_t const eql2 = (const_equiv_class_label_t) p2; | |
7b765bed DB |
1678 | return bitmap_equal_p (eql1->labels, eql2->labels); |
1679 | } | |
1680 | ||
1681 | /* Lookup a equivalence class in TABLE by the bitmap of LABELS it | |
1682 | contains. */ | |
1683 | ||
1684 | static unsigned int | |
1685 | equiv_class_lookup (htab_t table, bitmap labels) | |
1686 | { | |
1687 | void **slot; | |
1688 | struct equiv_class_label ecl; | |
1689 | ||
1690 | ecl.labels = labels; | |
1691 | ecl.hashcode = bitmap_hash (labels); | |
c58936b6 | 1692 | |
7b765bed DB |
1693 | slot = htab_find_slot_with_hash (table, &ecl, |
1694 | ecl.hashcode, NO_INSERT); | |
1695 | if (!slot) | |
1696 | return 0; | |
1697 | else | |
1698 | return ((equiv_class_label_t) *slot)->equivalence_class; | |
1699 | } | |
1700 | ||
1701 | ||
1702 | /* Add an equivalence class named EQUIVALENCE_CLASS with labels LABELS | |
1703 | to TABLE. */ | |
1704 | ||
1705 | static void | |
1706 | equiv_class_add (htab_t table, unsigned int equivalence_class, | |
1707 | bitmap labels) | |
1708 | { | |
1709 | void **slot; | |
1710 | equiv_class_label_t ecl = XNEW (struct equiv_class_label); | |
1711 | ||
1712 | ecl->labels = labels; | |
1713 | ecl->equivalence_class = equivalence_class; | |
1714 | ecl->hashcode = bitmap_hash (labels); | |
1715 | ||
1716 | slot = htab_find_slot_with_hash (table, ecl, | |
1717 | ecl->hashcode, INSERT); | |
1718 | gcc_assert (!*slot); | |
1719 | *slot = (void *) ecl; | |
1720 | } | |
1721 | ||
1722 | /* Perform offline variable substitution. | |
910fdc79 | 1723 | |
7b765bed DB |
1724 | This is a worst case quadratic time way of identifying variables |
1725 | that must have equivalent points-to sets, including those caused by | |
1726 | static cycles, and single entry subgraphs, in the constraint graph. | |
3e5937d7 | 1727 | |
7b765bed DB |
1728 | The technique is described in "Exploiting Pointer and Location |
1729 | Equivalence to Optimize Pointer Analysis. In the 14th International | |
1730 | Static Analysis Symposium (SAS), August 2007." It is known as the | |
1731 | "HU" algorithm, and is equivalent to value numbering the collapsed | |
1732 | constraint graph including evaluating unions. | |
3e5937d7 DB |
1733 | |
1734 | The general method of finding equivalence classes is as follows: | |
1735 | Add fake nodes (REF nodes) and edges for *a = b and a = *b constraints. | |
7b765bed DB |
1736 | Initialize all non-REF nodes to be direct nodes. |
1737 | For each constraint a = a U {b}, we set pts(a) = pts(a) u {fresh | |
1738 | variable} | |
1739 | For each constraint containing the dereference, we also do the same | |
1740 | thing. | |
1741 | ||
1742 | We then compute SCC's in the graph and unify nodes in the same SCC, | |
1743 | including pts sets. | |
1744 | ||
1745 | For each non-collapsed node x: | |
1746 | Visit all unvisited explicit incoming edges. | |
1747 | Ignoring all non-pointers, set pts(x) = Union of pts(a) for y | |
1748 | where y->x. | |
1749 | Lookup the equivalence class for pts(x). | |
1750 | If we found one, equivalence_class(x) = found class. | |
1751 | Otherwise, equivalence_class(x) = new class, and new_class is | |
1752 | added to the lookup table. | |
3e5937d7 DB |
1753 | |
1754 | All direct nodes with the same equivalence class can be replaced | |
1755 | with a single representative node. | |
1756 | All unlabeled nodes (label == 0) are not pointers and all edges | |
1757 | involving them can be eliminated. | |
7b765bed DB |
1758 | We perform these optimizations during rewrite_constraints |
1759 | ||
1760 | In addition to pointer equivalence class finding, we also perform | |
1761 | location equivalence class finding. This is the set of variables | |
1762 | that always appear together in points-to sets. We use this to | |
1763 | compress the size of the points-to sets. */ | |
1764 | ||
1765 | /* Current maximum pointer equivalence class id. */ | |
1766 | static int pointer_equiv_class; | |
3e5937d7 | 1767 | |
7b765bed DB |
1768 | /* Current maximum location equivalence class id. */ |
1769 | static int location_equiv_class; | |
3e5937d7 DB |
1770 | |
1771 | /* Recursive routine to find strongly connected components in GRAPH, | |
7b765bed | 1772 | and label it's nodes with DFS numbers. */ |
910fdc79 DB |
1773 | |
1774 | static void | |
7b765bed | 1775 | condense_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n) |
910fdc79 | 1776 | { |
3e5937d7 DB |
1777 | unsigned int i; |
1778 | bitmap_iterator bi; | |
1779 | unsigned int my_dfs; | |
c58936b6 | 1780 | |
3e5937d7 DB |
1781 | gcc_assert (si->node_mapping[n] == n); |
1782 | SET_BIT (si->visited, n); | |
1783 | si->dfs[n] = si->current_index ++; | |
1784 | my_dfs = si->dfs[n]; | |
c58936b6 | 1785 | |
3e5937d7 DB |
1786 | /* Visit all the successors. */ |
1787 | EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi) | |
910fdc79 | 1788 | { |
3e5937d7 | 1789 | unsigned int w = si->node_mapping[i]; |
910fdc79 | 1790 | |
7b765bed | 1791 | if (TEST_BIT (si->deleted, w)) |
910fdc79 DB |
1792 | continue; |
1793 | ||
3e5937d7 | 1794 | if (!TEST_BIT (si->visited, w)) |
7b765bed | 1795 | condense_visit (graph, si, w); |
3e5937d7 DB |
1796 | { |
1797 | unsigned int t = si->node_mapping[w]; | |
1798 | unsigned int nnode = si->node_mapping[n]; | |
62e5bf5d | 1799 | gcc_assert (nnode == n); |
910fdc79 | 1800 | |
3e5937d7 DB |
1801 | if (si->dfs[t] < si->dfs[nnode]) |
1802 | si->dfs[n] = si->dfs[t]; | |
1803 | } | |
1804 | } | |
910fdc79 | 1805 | |
3e5937d7 DB |
1806 | /* Visit all the implicit predecessors. */ |
1807 | EXECUTE_IF_IN_NONNULL_BITMAP (graph->implicit_preds[n], 0, i, bi) | |
1808 | { | |
1809 | unsigned int w = si->node_mapping[i]; | |
1810 | ||
7b765bed | 1811 | if (TEST_BIT (si->deleted, w)) |
3e5937d7 DB |
1812 | continue; |
1813 | ||
1814 | if (!TEST_BIT (si->visited, w)) | |
7b765bed | 1815 | condense_visit (graph, si, w); |
3e5937d7 DB |
1816 | { |
1817 | unsigned int t = si->node_mapping[w]; | |
1818 | unsigned int nnode = si->node_mapping[n]; | |
1819 | gcc_assert (nnode == n); | |
1820 | ||
1821 | if (si->dfs[t] < si->dfs[nnode]) | |
1822 | si->dfs[n] = si->dfs[t]; | |
1823 | } | |
1824 | } | |
4ee00913 | 1825 | |
3e5937d7 DB |
1826 | /* See if any components have been identified. */ |
1827 | if (si->dfs[n] == my_dfs) | |
1828 | { | |
1829 | while (VEC_length (unsigned, si->scc_stack) != 0 | |
1830 | && si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs) | |
910fdc79 | 1831 | { |
3e5937d7 DB |
1832 | unsigned int w = VEC_pop (unsigned, si->scc_stack); |
1833 | si->node_mapping[w] = n; | |
1834 | ||
1835 | if (!TEST_BIT (graph->direct_nodes, w)) | |
1836 | RESET_BIT (graph->direct_nodes, n); | |
3e5937d7 | 1837 | |
7b765bed DB |
1838 | /* Unify our nodes. */ |
1839 | if (graph->preds[w]) | |
1840 | { | |
1841 | if (!graph->preds[n]) | |
1842 | graph->preds[n] = BITMAP_ALLOC (&predbitmap_obstack); | |
1843 | bitmap_ior_into (graph->preds[n], graph->preds[w]); | |
1844 | } | |
1845 | if (graph->implicit_preds[w]) | |
1846 | { | |
1847 | if (!graph->implicit_preds[n]) | |
1848 | graph->implicit_preds[n] = BITMAP_ALLOC (&predbitmap_obstack); | |
1849 | bitmap_ior_into (graph->implicit_preds[n], | |
1850 | graph->implicit_preds[w]); | |
1851 | } | |
1852 | if (graph->points_to[w]) | |
1853 | { | |
1854 | if (!graph->points_to[n]) | |
1855 | graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack); | |
1856 | bitmap_ior_into (graph->points_to[n], | |
1857 | graph->points_to[w]); | |
1858 | } | |
3e5937d7 DB |
1859 | EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi) |
1860 | { | |
7b765bed DB |
1861 | unsigned int rep = si->node_mapping[i]; |
1862 | graph->number_incoming[rep]++; | |
3e5937d7 | 1863 | } |
3e5937d7 | 1864 | } |
7b765bed | 1865 | SET_BIT (si->deleted, n); |
3e5937d7 DB |
1866 | } |
1867 | else | |
1868 | VEC_safe_push (unsigned, heap, si->scc_stack, n); | |
1869 | } | |
1870 | ||
7b765bed DB |
1871 | /* Label pointer equivalences. */ |
1872 | ||
1873 | static void | |
1874 | label_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n) | |
1875 | { | |
1876 | unsigned int i; | |
1877 | bitmap_iterator bi; | |
1878 | SET_BIT (si->visited, n); | |
1879 | ||
1880 | if (!graph->points_to[n]) | |
1881 | graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack); | |
1882 | ||
1883 | /* Label and union our incoming edges's points to sets. */ | |
1884 | EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi) | |
1885 | { | |
1886 | unsigned int w = si->node_mapping[i]; | |
1887 | if (!TEST_BIT (si->visited, w)) | |
1888 | label_visit (graph, si, w); | |
1889 | ||
1890 | /* Skip unused edges */ | |
1891 | if (w == n || graph->pointer_label[w] == 0) | |
1892 | { | |
1893 | graph->number_incoming[w]--; | |
1894 | continue; | |
1895 | } | |
1896 | if (graph->points_to[w]) | |
1897 | bitmap_ior_into(graph->points_to[n], graph->points_to[w]); | |
1898 | ||
1899 | /* If all incoming edges to w have been processed and | |
1900 | graph->points_to[w] was not stored in the hash table, we can | |
1901 | free it. */ | |
1902 | graph->number_incoming[w]--; | |
1903 | if (!graph->number_incoming[w] && !TEST_BIT (graph->pt_used, w)) | |
1904 | { | |
1905 | BITMAP_FREE (graph->points_to[w]); | |
1906 | } | |
1907 | } | |
1908 | /* Indirect nodes get fresh variables. */ | |
1909 | if (!TEST_BIT (graph->direct_nodes, n)) | |
1910 | bitmap_set_bit (graph->points_to[n], FIRST_REF_NODE + n); | |
1911 | ||
1912 | if (!bitmap_empty_p (graph->points_to[n])) | |
1913 | { | |
1914 | unsigned int label = equiv_class_lookup (pointer_equiv_class_table, | |
1915 | graph->points_to[n]); | |
1916 | if (!label) | |
1917 | { | |
1918 | SET_BIT (graph->pt_used, n); | |
1919 | label = pointer_equiv_class++; | |
1920 | equiv_class_add (pointer_equiv_class_table, | |
1921 | label, graph->points_to[n]); | |
1922 | } | |
1923 | graph->pointer_label[n] = label; | |
1924 | } | |
1925 | } | |
1926 | ||
3e5937d7 DB |
1927 | /* Perform offline variable substitution, discovering equivalence |
1928 | classes, and eliminating non-pointer variables. */ | |
1929 | ||
1930 | static struct scc_info * | |
1931 | perform_var_substitution (constraint_graph_t graph) | |
1932 | { | |
1933 | unsigned int i; | |
1934 | unsigned int size = graph->size; | |
1935 | struct scc_info *si = init_scc_info (size); | |
1936 | ||
1937 | bitmap_obstack_initialize (&iteration_obstack); | |
7b765bed DB |
1938 | pointer_equiv_class_table = htab_create (511, equiv_class_label_hash, |
1939 | equiv_class_label_eq, free); | |
1940 | location_equiv_class_table = htab_create (511, equiv_class_label_hash, | |
1941 | equiv_class_label_eq, free); | |
1942 | pointer_equiv_class = 1; | |
1943 | location_equiv_class = 1; | |
1944 | ||
1945 | /* Condense the nodes, which means to find SCC's, count incoming | |
1946 | predecessors, and unite nodes in SCC's. */ | |
aa46c8a3 | 1947 | for (i = 0; i < FIRST_REF_NODE; i++) |
7b765bed DB |
1948 | if (!TEST_BIT (si->visited, si->node_mapping[i])) |
1949 | condense_visit (graph, si, si->node_mapping[i]); | |
3e5937d7 | 1950 | |
7b765bed DB |
1951 | sbitmap_zero (si->visited); |
1952 | /* Actually the label the nodes for pointer equivalences */ | |
aa46c8a3 | 1953 | for (i = 0; i < FIRST_REF_NODE; i++) |
3e5937d7 DB |
1954 | if (!TEST_BIT (si->visited, si->node_mapping[i])) |
1955 | label_visit (graph, si, si->node_mapping[i]); | |
1956 | ||
7b765bed DB |
1957 | /* Calculate location equivalence labels. */ |
1958 | for (i = 0; i < FIRST_REF_NODE; i++) | |
1959 | { | |
1960 | bitmap pointed_by; | |
1961 | bitmap_iterator bi; | |
1962 | unsigned int j; | |
1963 | unsigned int label; | |
1964 | ||
1965 | if (!graph->pointed_by[i]) | |
1966 | continue; | |
1967 | pointed_by = BITMAP_ALLOC (&iteration_obstack); | |
1968 | ||
1969 | /* Translate the pointed-by mapping for pointer equivalence | |
1970 | labels. */ | |
1971 | EXECUTE_IF_SET_IN_BITMAP (graph->pointed_by[i], 0, j, bi) | |
1972 | { | |
1973 | bitmap_set_bit (pointed_by, | |
1974 | graph->pointer_label[si->node_mapping[j]]); | |
1975 | } | |
1976 | /* The original pointed_by is now dead. */ | |
1977 | BITMAP_FREE (graph->pointed_by[i]); | |
1978 | ||
1979 | /* Look up the location equivalence label if one exists, or make | |
1980 | one otherwise. */ | |
1981 | label = equiv_class_lookup (location_equiv_class_table, | |
1982 | pointed_by); | |
1983 | if (label == 0) | |
1984 | { | |
1985 | label = location_equiv_class++; | |
1986 | equiv_class_add (location_equiv_class_table, | |
1987 | label, pointed_by); | |
1988 | } | |
1989 | else | |
1990 | { | |
1991 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1992 | fprintf (dump_file, "Found location equivalence for node %s\n", | |
1993 | get_varinfo (i)->name); | |
1994 | BITMAP_FREE (pointed_by); | |
1995 | } | |
1996 | graph->loc_label[i] = label; | |
1997 | ||
1998 | } | |
1999 | ||
3e5937d7 DB |
2000 | if (dump_file && (dump_flags & TDF_DETAILS)) |
2001 | for (i = 0; i < FIRST_REF_NODE; i++) | |
2002 | { | |
2003 | bool direct_node = TEST_BIT (graph->direct_nodes, i); | |
2004 | fprintf (dump_file, | |
7b765bed DB |
2005 | "Equivalence classes for %s node id %d:%s are pointer: %d" |
2006 | ", location:%d\n", | |
3e5937d7 | 2007 | direct_node ? "Direct node" : "Indirect node", i, |
62e5bf5d | 2008 | get_varinfo (i)->name, |
7b765bed DB |
2009 | graph->pointer_label[si->node_mapping[i]], |
2010 | graph->loc_label[si->node_mapping[i]]); | |
3e5937d7 DB |
2011 | } |
2012 | ||
2013 | /* Quickly eliminate our non-pointer variables. */ | |
2014 | ||
2015 | for (i = 0; i < FIRST_REF_NODE; i++) | |
2016 | { | |
2017 | unsigned int node = si->node_mapping[i]; | |
2018 | ||
aa46c8a3 | 2019 | if (graph->pointer_label[node] == 0) |
3e5937d7 | 2020 | { |
23e73993 | 2021 | if (dump_file && (dump_flags & TDF_DETAILS)) |
3e5937d7 DB |
2022 | fprintf (dump_file, |
2023 | "%s is a non-pointer variable, eliminating edges.\n", | |
2024 | get_varinfo (node)->name); | |
2025 | stats.nonpointer_vars++; | |
2026 | clear_edges_for_node (graph, node); | |
910fdc79 DB |
2027 | } |
2028 | } | |
7b765bed | 2029 | |
3e5937d7 DB |
2030 | return si; |
2031 | } | |
2032 | ||
2033 | /* Free information that was only necessary for variable | |
2034 | substitution. */ | |
910fdc79 | 2035 | |
3e5937d7 DB |
2036 | static void |
2037 | free_var_substitution_info (struct scc_info *si) | |
2038 | { | |
2039 | free_scc_info (si); | |
7b765bed DB |
2040 | free (graph->pointer_label); |
2041 | free (graph->loc_label); | |
2042 | free (graph->pointed_by); | |
2043 | free (graph->points_to); | |
2044 | free (graph->number_incoming); | |
3e5937d7 DB |
2045 | free (graph->eq_rep); |
2046 | sbitmap_free (graph->direct_nodes); | |
7b765bed DB |
2047 | sbitmap_free (graph->pt_used); |
2048 | htab_delete (pointer_equiv_class_table); | |
2049 | htab_delete (location_equiv_class_table); | |
4ee00913 | 2050 | bitmap_obstack_release (&iteration_obstack); |
3e5937d7 DB |
2051 | } |
2052 | ||
2053 | /* Return an existing node that is equivalent to NODE, which has | |
2054 | equivalence class LABEL, if one exists. Return NODE otherwise. */ | |
2055 | ||
2056 | static unsigned int | |
2057 | find_equivalent_node (constraint_graph_t graph, | |
2058 | unsigned int node, unsigned int label) | |
2059 | { | |
2060 | /* If the address version of this variable is unused, we can | |
2061 | substitute it for anything else with the same label. | |
2062 | Otherwise, we know the pointers are equivalent, but not the | |
7b765bed | 2063 | locations, and we can unite them later. */ |
3e5937d7 | 2064 | |
7b765bed | 2065 | if (!bitmap_bit_p (graph->address_taken, node)) |
3e5937d7 DB |
2066 | { |
2067 | gcc_assert (label < graph->size); | |
2068 | ||
2069 | if (graph->eq_rep[label] != -1) | |
2070 | { | |
2071 | /* Unify the two variables since we know they are equivalent. */ | |
2072 | if (unite (graph->eq_rep[label], node)) | |
2073 | unify_nodes (graph, graph->eq_rep[label], node, false); | |
2074 | return graph->eq_rep[label]; | |
2075 | } | |
2076 | else | |
2077 | { | |
2078 | graph->eq_rep[label] = node; | |
7b765bed | 2079 | graph->pe_rep[label] = node; |
3e5937d7 DB |
2080 | } |
2081 | } | |
7b765bed DB |
2082 | else |
2083 | { | |
2084 | gcc_assert (label < graph->size); | |
2085 | graph->pe[node] = label; | |
2086 | if (graph->pe_rep[label] == -1) | |
2087 | graph->pe_rep[label] = node; | |
2088 | } | |
2089 | ||
3e5937d7 DB |
2090 | return node; |
2091 | } | |
2092 | ||
7b765bed DB |
2093 | /* Unite pointer equivalent but not location equivalent nodes in |
2094 | GRAPH. This may only be performed once variable substitution is | |
2095 | finished. */ | |
2096 | ||
2097 | static void | |
2098 | unite_pointer_equivalences (constraint_graph_t graph) | |
2099 | { | |
2100 | unsigned int i; | |
2101 | ||
2102 | /* Go through the pointer equivalences and unite them to their | |
2103 | representative, if they aren't already. */ | |
aa46c8a3 | 2104 | for (i = 0; i < FIRST_REF_NODE; i++) |
7b765bed DB |
2105 | { |
2106 | unsigned int label = graph->pe[i]; | |
aa46c8a3 DB |
2107 | if (label) |
2108 | { | |
2109 | int label_rep = graph->pe_rep[label]; | |
2110 | ||
2111 | if (label_rep == -1) | |
2112 | continue; | |
2113 | ||
2114 | label_rep = find (label_rep); | |
2115 | if (label_rep >= 0 && unite (label_rep, find (i))) | |
2116 | unify_nodes (graph, label_rep, i, false); | |
2117 | } | |
7b765bed DB |
2118 | } |
2119 | } | |
2120 | ||
2121 | /* Move complex constraints to the GRAPH nodes they belong to. */ | |
3e5937d7 DB |
2122 | |
2123 | static void | |
7b765bed DB |
2124 | move_complex_constraints (constraint_graph_t graph) |
2125 | { | |
2126 | int i; | |
2127 | constraint_t c; | |
2128 | ||
2129 | for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++) | |
2130 | { | |
2131 | if (c) | |
2132 | { | |
2133 | struct constraint_expr lhs = c->lhs; | |
2134 | struct constraint_expr rhs = c->rhs; | |
2135 | ||
2136 | if (lhs.type == DEREF) | |
2137 | { | |
2138 | insert_into_complex (graph, lhs.var, c); | |
2139 | } | |
2140 | else if (rhs.type == DEREF) | |
2141 | { | |
2142 | if (!(get_varinfo (lhs.var)->is_special_var)) | |
2143 | insert_into_complex (graph, rhs.var, c); | |
2144 | } | |
2145 | else if (rhs.type != ADDRESSOF && lhs.var > anything_id | |
2146 | && (lhs.offset != 0 || rhs.offset != 0)) | |
2147 | { | |
2148 | insert_into_complex (graph, rhs.var, c); | |
2149 | } | |
2150 | } | |
2151 | } | |
2152 | } | |
2153 | ||
2154 | ||
2155 | /* Optimize and rewrite complex constraints while performing | |
2156 | collapsing of equivalent nodes. SI is the SCC_INFO that is the | |
2157 | result of perform_variable_substitution. */ | |
2158 | ||
2159 | static void | |
2160 | rewrite_constraints (constraint_graph_t graph, | |
2161 | struct scc_info *si) | |
3e5937d7 DB |
2162 | { |
2163 | int i; | |
2164 | unsigned int j; | |
2165 | constraint_t c; | |
2166 | ||
2167 | for (j = 0; j < graph->size; j++) | |
2168 | gcc_assert (find (j) == j); | |
2169 | ||
2170 | for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++) | |
2171 | { | |
2172 | struct constraint_expr lhs = c->lhs; | |
2173 | struct constraint_expr rhs = c->rhs; | |
2174 | unsigned int lhsvar = find (get_varinfo_fc (lhs.var)->id); | |
2175 | unsigned int rhsvar = find (get_varinfo_fc (rhs.var)->id); | |
2176 | unsigned int lhsnode, rhsnode; | |
2177 | unsigned int lhslabel, rhslabel; | |
2178 | ||
2179 | lhsnode = si->node_mapping[lhsvar]; | |
2180 | rhsnode = si->node_mapping[rhsvar]; | |
7b765bed DB |
2181 | lhslabel = graph->pointer_label[lhsnode]; |
2182 | rhslabel = graph->pointer_label[rhsnode]; | |
3e5937d7 DB |
2183 | |
2184 | /* See if it is really a non-pointer variable, and if so, ignore | |
2185 | the constraint. */ | |
2186 | if (lhslabel == 0) | |
2187 | { | |
aa46c8a3 | 2188 | if (dump_file && (dump_flags & TDF_DETAILS)) |
3e5937d7 | 2189 | { |
aa46c8a3 DB |
2190 | |
2191 | fprintf (dump_file, "%s is a non-pointer variable," | |
2192 | "ignoring constraint:", | |
2193 | get_varinfo (lhs.var)->name); | |
2194 | dump_constraint (dump_file, c); | |
3e5937d7 | 2195 | } |
aa46c8a3 DB |
2196 | VEC_replace (constraint_t, constraints, i, NULL); |
2197 | continue; | |
3e5937d7 DB |
2198 | } |
2199 | ||
2200 | if (rhslabel == 0) | |
2201 | { | |
aa46c8a3 | 2202 | if (dump_file && (dump_flags & TDF_DETAILS)) |
3e5937d7 | 2203 | { |
aa46c8a3 DB |
2204 | |
2205 | fprintf (dump_file, "%s is a non-pointer variable," | |
2206 | "ignoring constraint:", | |
2207 | get_varinfo (rhs.var)->name); | |
2208 | dump_constraint (dump_file, c); | |
3e5937d7 | 2209 | } |
aa46c8a3 DB |
2210 | VEC_replace (constraint_t, constraints, i, NULL); |
2211 | continue; | |
3e5937d7 DB |
2212 | } |
2213 | ||
2214 | lhsvar = find_equivalent_node (graph, lhsvar, lhslabel); | |
2215 | rhsvar = find_equivalent_node (graph, rhsvar, rhslabel); | |
2216 | c->lhs.var = lhsvar; | |
2217 | c->rhs.var = rhsvar; | |
2218 | ||
3e5937d7 DB |
2219 | } |
2220 | } | |
2221 | ||
2222 | /* Eliminate indirect cycles involving NODE. Return true if NODE was | |
2223 | part of an SCC, false otherwise. */ | |
2224 | ||
2225 | static bool | |
2226 | eliminate_indirect_cycles (unsigned int node) | |
2227 | { | |
2228 | if (graph->indirect_cycles[node] != -1 | |
2229 | && !bitmap_empty_p (get_varinfo (node)->solution)) | |
2230 | { | |
2231 | unsigned int i; | |
2232 | VEC(unsigned,heap) *queue = NULL; | |
2233 | int queuepos; | |
2234 | unsigned int to = find (graph->indirect_cycles[node]); | |
2235 | bitmap_iterator bi; | |
2236 | ||
2237 | /* We can't touch the solution set and call unify_nodes | |
2238 | at the same time, because unify_nodes is going to do | |
2239 | bitmap unions into it. */ | |
2240 | ||
2241 | EXECUTE_IF_SET_IN_BITMAP (get_varinfo (node)->solution, 0, i, bi) | |
2242 | { | |
2243 | if (find (i) == i && i != to) | |
2244 | { | |
2245 | if (unite (to, i)) | |
2246 | VEC_safe_push (unsigned, heap, queue, i); | |
2247 | } | |
2248 | } | |
2249 | ||
2250 | for (queuepos = 0; | |
2251 | VEC_iterate (unsigned, queue, queuepos, i); | |
2252 | queuepos++) | |
2253 | { | |
2254 | unify_nodes (graph, to, i, true); | |
2255 | } | |
2256 | VEC_free (unsigned, heap, queue); | |
2257 | return true; | |
2258 | } | |
2259 | return false; | |
910fdc79 DB |
2260 | } |
2261 | ||
910fdc79 DB |
2262 | /* Solve the constraint graph GRAPH using our worklist solver. |
2263 | This is based on the PW* family of solvers from the "Efficient Field | |
2264 | Sensitive Pointer Analysis for C" paper. | |
2265 | It works by iterating over all the graph nodes, processing the complex | |
2266 | constraints and propagating the copy constraints, until everything stops | |
2267 | changed. This corresponds to steps 6-8 in the solving list given above. */ | |
2268 | ||
2269 | static void | |
2270 | solve_graph (constraint_graph_t graph) | |
2271 | { | |
7b765bed | 2272 | unsigned int size = graph->size; |
910fdc79 | 2273 | unsigned int i; |
3e5937d7 | 2274 | bitmap pts; |
910fdc79 | 2275 | |
3e5937d7 | 2276 | changed_count = 0; |
910fdc79 | 2277 | changed = sbitmap_alloc (size); |
3e5937d7 | 2278 | sbitmap_zero (changed); |
c58936b6 | 2279 | |
3e5937d7 | 2280 | /* Mark all initial non-collapsed nodes as changed. */ |
910fdc79 | 2281 | for (i = 0; i < size; i++) |
3e5937d7 DB |
2282 | { |
2283 | varinfo_t ivi = get_varinfo (i); | |
2284 | if (find (i) == i && !bitmap_empty_p (ivi->solution) | |
2285 | && ((graph->succs[i] && !bitmap_empty_p (graph->succs[i])) | |
2286 | || VEC_length (constraint_t, graph->complex[i]) > 0)) | |
2287 | { | |
2288 | SET_BIT (changed, i); | |
2289 | changed_count++; | |
2290 | } | |
2291 | } | |
2292 | ||
2293 | /* Allocate a bitmap to be used to store the changed bits. */ | |
2294 | pts = BITMAP_ALLOC (&pta_obstack); | |
c58936b6 | 2295 | |
910fdc79 DB |
2296 | while (changed_count > 0) |
2297 | { | |
2298 | unsigned int i; | |
2299 | struct topo_info *ti = init_topo_info (); | |
2300 | stats.iterations++; | |
4ee00913 | 2301 | |
910fdc79 | 2302 | bitmap_obstack_initialize (&iteration_obstack); |
c58936b6 | 2303 | |
910fdc79 DB |
2304 | compute_topo_order (graph, ti); |
2305 | ||
740e80e8 | 2306 | while (VEC_length (unsigned, ti->topo_order) != 0) |
910fdc79 | 2307 | { |
3e5937d7 | 2308 | |
740e80e8 | 2309 | i = VEC_pop (unsigned, ti->topo_order); |
3e5937d7 DB |
2310 | |
2311 | /* If this variable is not a representative, skip it. */ | |
2312 | if (find (i) != i) | |
2313 | continue; | |
2314 | ||
d3c36974 DB |
2315 | /* In certain indirect cycle cases, we may merge this |
2316 | variable to another. */ | |
62e5bf5d | 2317 | if (eliminate_indirect_cycles (i) && find (i) != i) |
d3c36974 | 2318 | continue; |
910fdc79 DB |
2319 | |
2320 | /* If the node has changed, we need to process the | |
2321 | complex constraints and outgoing edges again. */ | |
2322 | if (TEST_BIT (changed, i)) | |
2323 | { | |
2324 | unsigned int j; | |
2325 | constraint_t c; | |
910fdc79 | 2326 | bitmap solution; |
3e5937d7 | 2327 | VEC(constraint_t,heap) *complex = graph->complex[i]; |
21392f19 | 2328 | bool solution_empty; |
48e540b0 | 2329 | |
910fdc79 DB |
2330 | RESET_BIT (changed, i); |
2331 | changed_count--; | |
2332 | ||
3e5937d7 DB |
2333 | /* Compute the changed set of solution bits. */ |
2334 | bitmap_and_compl (pts, get_varinfo (i)->solution, | |
2335 | get_varinfo (i)->oldsolution); | |
2336 | ||
2337 | if (bitmap_empty_p (pts)) | |
2338 | continue; | |
2339 | ||
2340 | bitmap_ior_into (get_varinfo (i)->oldsolution, pts); | |
2341 | ||
910fdc79 | 2342 | solution = get_varinfo (i)->solution; |
21392f19 DB |
2343 | solution_empty = bitmap_empty_p (solution); |
2344 | ||
2345 | /* Process the complex constraints */ | |
910fdc79 | 2346 | for (j = 0; VEC_iterate (constraint_t, complex, j, c); j++) |
21392f19 | 2347 | { |
7b765bed DB |
2348 | /* XXX: This is going to unsort the constraints in |
2349 | some cases, which will occasionally add duplicate | |
2350 | constraints during unification. This does not | |
2351 | affect correctness. */ | |
2352 | c->lhs.var = find (c->lhs.var); | |
2353 | c->rhs.var = find (c->rhs.var); | |
2354 | ||
21392f19 DB |
2355 | /* The only complex constraint that can change our |
2356 | solution to non-empty, given an empty solution, | |
2357 | is a constraint where the lhs side is receiving | |
2358 | some set from elsewhere. */ | |
2359 | if (!solution_empty || c->lhs.type != DEREF) | |
3e5937d7 | 2360 | do_complex_constraint (graph, c, pts); |
21392f19 | 2361 | } |
910fdc79 | 2362 | |
21392f19 DB |
2363 | solution_empty = bitmap_empty_p (solution); |
2364 | ||
2365 | if (!solution_empty) | |
4ee00913 | 2366 | { |
3e5937d7 DB |
2367 | bitmap_iterator bi; |
2368 | ||
21392f19 | 2369 | /* Propagate solution to all successors. */ |
c58936b6 | 2370 | EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i], |
21392f19 | 2371 | 0, j, bi) |
4ee00913 | 2372 | { |
3e5937d7 DB |
2373 | bitmap tmp; |
2374 | bool flag; | |
2375 | ||
2376 | unsigned int to = find (j); | |
2377 | tmp = get_varinfo (to)->solution; | |
2378 | flag = false; | |
c58936b6 | 2379 | |
3e5937d7 DB |
2380 | /* Don't try to propagate to ourselves. */ |
2381 | if (to == i) | |
2382 | continue; | |
c58936b6 | 2383 | |
3e5937d7 | 2384 | flag = set_union_with_increment (tmp, pts, 0); |
c58936b6 | 2385 | |
21392f19 | 2386 | if (flag) |
4ee00913 | 2387 | { |
3e5937d7 DB |
2388 | get_varinfo (to)->solution = tmp; |
2389 | if (!TEST_BIT (changed, to)) | |
21392f19 | 2390 | { |
3e5937d7 | 2391 | SET_BIT (changed, to); |
21392f19 DB |
2392 | changed_count++; |
2393 | } | |
4ee00913 DB |
2394 | } |
2395 | } | |
910fdc79 DB |
2396 | } |
2397 | } | |
2398 | } | |
2399 | free_topo_info (ti); | |
2400 | bitmap_obstack_release (&iteration_obstack); | |
2401 | } | |
c58936b6 | 2402 | |
3e5937d7 | 2403 | BITMAP_FREE (pts); |
910fdc79 | 2404 | sbitmap_free (changed); |
3e5937d7 | 2405 | bitmap_obstack_release (&oldpta_obstack); |
910fdc79 DB |
2406 | } |
2407 | ||
3e5937d7 | 2408 | /* Map from trees to variable infos. */ |
15814ba0 | 2409 | static struct pointer_map_t *vi_for_tree; |
910fdc79 | 2410 | |
910fdc79 | 2411 | |
15814ba0 | 2412 | /* Insert ID as the variable id for tree T in the vi_for_tree map. */ |
910fdc79 | 2413 | |
c58936b6 | 2414 | static void |
3e5937d7 | 2415 | insert_vi_for_tree (tree t, varinfo_t vi) |
910fdc79 | 2416 | { |
15814ba0 PB |
2417 | void **slot = pointer_map_insert (vi_for_tree, t); |
2418 | gcc_assert (vi); | |
910fdc79 | 2419 | gcc_assert (*slot == NULL); |
15814ba0 | 2420 | *slot = vi; |
910fdc79 DB |
2421 | } |
2422 | ||
3e5937d7 | 2423 | /* Find the variable info for tree T in VI_FOR_TREE. If T does not |
15814ba0 | 2424 | exist in the map, return NULL, otherwise, return the varinfo we found. */ |
910fdc79 | 2425 | |
15814ba0 PB |
2426 | static varinfo_t |
2427 | lookup_vi_for_tree (tree t) | |
910fdc79 | 2428 | { |
15814ba0 PB |
2429 | void **slot = pointer_map_contains (vi_for_tree, t); |
2430 | if (slot == NULL) | |
2431 | return NULL; | |
910fdc79 | 2432 | |
15814ba0 | 2433 | return (varinfo_t) *slot; |
910fdc79 DB |
2434 | } |
2435 | ||
2436 | /* Return a printable name for DECL */ | |
2437 | ||
2438 | static const char * | |
2439 | alias_get_name (tree decl) | |
2440 | { | |
2441 | const char *res = get_name (decl); | |
2442 | char *temp; | |
2443 | int num_printed = 0; | |
2444 | ||
2445 | if (res != NULL) | |
2446 | return res; | |
2447 | ||
2448 | res = "NULL"; | |
4f6c9110 RG |
2449 | if (!dump_file) |
2450 | return res; | |
2451 | ||
910fdc79 DB |
2452 | if (TREE_CODE (decl) == SSA_NAME) |
2453 | { | |
c58936b6 | 2454 | num_printed = asprintf (&temp, "%s_%u", |
910fdc79 DB |
2455 | alias_get_name (SSA_NAME_VAR (decl)), |
2456 | SSA_NAME_VERSION (decl)); | |
2457 | } | |
2458 | else if (DECL_P (decl)) | |
2459 | { | |
2460 | num_printed = asprintf (&temp, "D.%u", DECL_UID (decl)); | |
2461 | } | |
2462 | if (num_printed > 0) | |
2463 | { | |
2464 | res = ggc_strdup (temp); | |
2465 | free (temp); | |
2466 | } | |
2467 | return res; | |
2468 | } | |
2469 | ||
15814ba0 PB |
2470 | /* Find the variable id for tree T in the map. |
2471 | If T doesn't exist in the map, create an entry for it and return it. */ | |
910fdc79 | 2472 | |
3e5937d7 DB |
2473 | static varinfo_t |
2474 | get_vi_for_tree (tree t) | |
910fdc79 | 2475 | { |
15814ba0 PB |
2476 | void **slot = pointer_map_contains (vi_for_tree, t); |
2477 | if (slot == NULL) | |
3e5937d7 | 2478 | return get_varinfo (create_variable_info_for (t, alias_get_name (t))); |
c58936b6 | 2479 | |
15814ba0 | 2480 | return (varinfo_t) *slot; |
910fdc79 DB |
2481 | } |
2482 | ||
2483 | /* Get a constraint expression from an SSA_VAR_P node. */ | |
2484 | ||
2485 | static struct constraint_expr | |
2486 | get_constraint_exp_from_ssa_var (tree t) | |
2487 | { | |
2488 | struct constraint_expr cexpr; | |
2489 | ||
2490 | gcc_assert (SSA_VAR_P (t) || DECL_P (t)); | |
2491 | ||
2492 | /* For parameters, get at the points-to set for the actual parm | |
2493 | decl. */ | |
c58936b6 DB |
2494 | if (TREE_CODE (t) == SSA_NAME |
2495 | && TREE_CODE (SSA_NAME_VAR (t)) == PARM_DECL | |
38635499 | 2496 | && SSA_NAME_IS_DEFAULT_DEF (t)) |
910fdc79 DB |
2497 | return get_constraint_exp_from_ssa_var (SSA_NAME_VAR (t)); |
2498 | ||
2499 | cexpr.type = SCALAR; | |
c58936b6 | 2500 | |
3e5937d7 | 2501 | cexpr.var = get_vi_for_tree (t)->id; |
47bcb538 DB |
2502 | /* If we determine the result is "anything", and we know this is readonly, |
2503 | say it points to readonly memory instead. */ | |
2504 | if (cexpr.var == anything_id && TREE_READONLY (t)) | |
910fdc79 | 2505 | { |
3e5937d7 | 2506 | cexpr.type = ADDRESSOF; |
910fdc79 DB |
2507 | cexpr.var = readonly_id; |
2508 | } | |
c58936b6 | 2509 | |
910fdc79 DB |
2510 | cexpr.offset = 0; |
2511 | return cexpr; | |
2512 | } | |
2513 | ||
2514 | /* Process a completed constraint T, and add it to the constraint | |
7b765bed DB |
2515 | list. FROM_CALL is true if this is a constraint coming from a |
2516 | call, which means any DEREFs we see are "may-deref's", not | |
2517 | "must-deref"'s. */ | |
910fdc79 DB |
2518 | |
2519 | static void | |
7b765bed | 2520 | process_constraint_1 (constraint_t t, bool from_call) |
910fdc79 DB |
2521 | { |
2522 | struct constraint_expr rhs = t->rhs; | |
2523 | struct constraint_expr lhs = t->lhs; | |
c58936b6 | 2524 | |
910fdc79 DB |
2525 | gcc_assert (rhs.var < VEC_length (varinfo_t, varmap)); |
2526 | gcc_assert (lhs.var < VEC_length (varinfo_t, varmap)); | |
2527 | ||
7b765bed DB |
2528 | if (!from_call) |
2529 | { | |
2530 | if (lhs.type == DEREF) | |
2531 | get_varinfo (lhs.var)->directly_dereferenced = true; | |
2532 | if (rhs.type == DEREF) | |
2533 | get_varinfo (rhs.var)->directly_dereferenced = true; | |
2534 | } | |
c58936b6 DB |
2535 | |
2536 | if (!use_field_sensitive) | |
2537 | { | |
2538 | t->rhs.offset = 0; | |
2539 | t->lhs.offset = 0; | |
2540 | } | |
2541 | ||
910fdc79 DB |
2542 | /* ANYTHING == ANYTHING is pointless. */ |
2543 | if (lhs.var == anything_id && rhs.var == anything_id) | |
2544 | return; | |
2545 | ||
2546 | /* If we have &ANYTHING = something, convert to SOMETHING = &ANYTHING) */ | |
3e5937d7 | 2547 | else if (lhs.var == anything_id && lhs.type == ADDRESSOF) |
910fdc79 DB |
2548 | { |
2549 | rhs = t->lhs; | |
2550 | t->lhs = t->rhs; | |
2551 | t->rhs = rhs; | |
7b765bed | 2552 | process_constraint_1 (t, from_call); |
c58936b6 | 2553 | } |
910fdc79 DB |
2554 | /* This can happen in our IR with things like n->a = *p */ |
2555 | else if (rhs.type == DEREF && lhs.type == DEREF && rhs.var != anything_id) | |
2556 | { | |
2557 | /* Split into tmp = *rhs, *lhs = tmp */ | |
2558 | tree rhsdecl = get_varinfo (rhs.var)->decl; | |
2559 | tree pointertype = TREE_TYPE (rhsdecl); | |
2560 | tree pointedtotype = TREE_TYPE (pointertype); | |
2561 | tree tmpvar = create_tmp_var_raw (pointedtotype, "doubledereftmp"); | |
2562 | struct constraint_expr tmplhs = get_constraint_exp_from_ssa_var (tmpvar); | |
c58936b6 | 2563 | |
910fdc79 DB |
2564 | /* If this is an aggregate of known size, we should have passed |
2565 | this off to do_structure_copy, and it should have broken it | |
2566 | up. */ | |
c58936b6 | 2567 | gcc_assert (!AGGREGATE_TYPE_P (pointedtotype) |
910fdc79 | 2568 | || get_varinfo (rhs.var)->is_unknown_size_var); |
c58936b6 | 2569 | |
7b765bed DB |
2570 | process_constraint_1 (new_constraint (tmplhs, rhs), from_call); |
2571 | process_constraint_1 (new_constraint (lhs, tmplhs), from_call); | |
2572 | } | |
2573 | else if (rhs.type == ADDRESSOF && lhs.type == DEREF) | |
2574 | { | |
2575 | /* Split into tmp = &rhs, *lhs = tmp */ | |
2576 | tree rhsdecl = get_varinfo (rhs.var)->decl; | |
2577 | tree pointertype = TREE_TYPE (rhsdecl); | |
2578 | tree tmpvar = create_tmp_var_raw (pointertype, "derefaddrtmp"); | |
2579 | struct constraint_expr tmplhs = get_constraint_exp_from_ssa_var (tmpvar); | |
2580 | ||
2581 | process_constraint_1 (new_constraint (tmplhs, rhs), from_call); | |
2582 | process_constraint_1 (new_constraint (lhs, tmplhs), from_call); | |
910fdc79 | 2583 | } |
910fdc79 DB |
2584 | else |
2585 | { | |
3e5937d7 | 2586 | gcc_assert (rhs.type != ADDRESSOF || rhs.offset == 0); |
b5efa470 | 2587 | VEC_safe_push (constraint_t, heap, constraints, t); |
910fdc79 DB |
2588 | } |
2589 | } | |
2590 | ||
7b765bed DB |
2591 | |
2592 | /* Process constraint T, performing various simplifications and then | |
2593 | adding it to our list of overall constraints. */ | |
2594 | ||
2595 | static void | |
2596 | process_constraint (constraint_t t) | |
2597 | { | |
2598 | process_constraint_1 (t, false); | |
2599 | } | |
2600 | ||
21392f19 DB |
2601 | /* Return true if T is a variable of a type that could contain |
2602 | pointers. */ | |
2603 | ||
2604 | static bool | |
2605 | could_have_pointers (tree t) | |
2606 | { | |
2607 | tree type = TREE_TYPE (t); | |
c58936b6 | 2608 | |
6e7e772d DN |
2609 | if (POINTER_TYPE_P (type) |
2610 | || AGGREGATE_TYPE_P (type) | |
21392f19 DB |
2611 | || TREE_CODE (type) == COMPLEX_TYPE) |
2612 | return true; | |
6e7e772d | 2613 | |
21392f19 DB |
2614 | return false; |
2615 | } | |
910fdc79 DB |
2616 | |
2617 | /* Return the position, in bits, of FIELD_DECL from the beginning of its | |
2618 | structure. */ | |
2619 | ||
2620 | static unsigned HOST_WIDE_INT | |
2621 | bitpos_of_field (const tree fdecl) | |
2622 | { | |
2623 | ||
2624 | if (TREE_CODE (DECL_FIELD_OFFSET (fdecl)) != INTEGER_CST | |
2625 | || TREE_CODE (DECL_FIELD_BIT_OFFSET (fdecl)) != INTEGER_CST) | |
2626 | return -1; | |
c58936b6 DB |
2627 | |
2628 | return (tree_low_cst (DECL_FIELD_OFFSET (fdecl), 1) * 8) | |
2629 | + tree_low_cst (DECL_FIELD_BIT_OFFSET (fdecl), 1); | |
910fdc79 DB |
2630 | } |
2631 | ||
2632 | ||
dd68d988 DB |
2633 | /* Return true if an access to [ACCESSPOS, ACCESSSIZE] |
2634 | overlaps with a field at [FIELDPOS, FIELDSIZE] */ | |
2635 | ||
2636 | static bool | |
2637 | offset_overlaps_with_access (const unsigned HOST_WIDE_INT fieldpos, | |
2638 | const unsigned HOST_WIDE_INT fieldsize, | |
2639 | const unsigned HOST_WIDE_INT accesspos, | |
2640 | const unsigned HOST_WIDE_INT accesssize) | |
2641 | { | |
2642 | if (fieldpos == accesspos && fieldsize == accesssize) | |
2643 | return true; | |
2238c11d | 2644 | if (accesspos >= fieldpos && accesspos < (fieldpos + fieldsize)) |
dd68d988 DB |
2645 | return true; |
2646 | if (accesspos < fieldpos && (accesspos + accesssize > fieldpos)) | |
2647 | return true; | |
c58936b6 | 2648 | |
dd68d988 DB |
2649 | return false; |
2650 | } | |
2651 | ||
910fdc79 DB |
2652 | /* Given a COMPONENT_REF T, return the constraint_expr for it. */ |
2653 | ||
4ee00913 | 2654 | static void |
1d85354c | 2655 | get_constraint_for_component_ref (tree t, VEC(ce_s, heap) **results) |
910fdc79 | 2656 | { |
4ee00913 | 2657 | tree orig_t = t; |
b1347638 | 2658 | HOST_WIDE_INT bitsize = -1; |
6bec9271 | 2659 | HOST_WIDE_INT bitmaxsize = -1; |
910fdc79 | 2660 | HOST_WIDE_INT bitpos; |
910fdc79 | 2661 | tree forzero; |
4ee00913 DB |
2662 | struct constraint_expr *result; |
2663 | unsigned int beforelength = VEC_length (ce_s, *results); | |
910fdc79 DB |
2664 | |
2665 | /* Some people like to do cute things like take the address of | |
2666 | &0->a.b */ | |
2667 | forzero = t; | |
2668 | while (!SSA_VAR_P (forzero) && !CONSTANT_CLASS_P (forzero)) | |
4ee00913 | 2669 | forzero = TREE_OPERAND (forzero, 0); |
910fdc79 | 2670 | |
c58936b6 | 2671 | if (CONSTANT_CLASS_P (forzero) && integer_zerop (forzero)) |
910fdc79 | 2672 | { |
4ee00913 | 2673 | struct constraint_expr temp; |
c58936b6 | 2674 | |
4ee00913 DB |
2675 | temp.offset = 0; |
2676 | temp.var = integer_id; | |
2677 | temp.type = SCALAR; | |
2678 | VEC_safe_push (ce_s, heap, *results, &temp); | |
2679 | return; | |
910fdc79 | 2680 | } |
c58936b6 | 2681 | |
6bec9271 | 2682 | t = get_ref_base_and_extent (t, &bitpos, &bitsize, &bitmaxsize); |
21392f19 | 2683 | |
3a057207 | 2684 | /* String constants are readonly, so there is nothing to really do |
21392f19 DB |
2685 | here. */ |
2686 | if (TREE_CODE (t) == STRING_CST) | |
2687 | return; | |
2688 | ||
1d85354c | 2689 | get_constraint_for (t, results); |
4ee00913 | 2690 | result = VEC_last (ce_s, *results); |
a555a02c | 2691 | result->offset = bitpos; |
4ee00913 DB |
2692 | |
2693 | gcc_assert (beforelength + 1 == VEC_length (ce_s, *results)); | |
910fdc79 DB |
2694 | |
2695 | /* This can also happen due to weird offsetof type macros. */ | |
4ee00913 DB |
2696 | if (TREE_CODE (t) != ADDR_EXPR && result->type == ADDRESSOF) |
2697 | result->type = SCALAR; | |
c58936b6 | 2698 | |
4ee00913 | 2699 | if (result->type == SCALAR) |
910fdc79 DB |
2700 | { |
2701 | /* In languages like C, you can access one past the end of an | |
2702 | array. You aren't allowed to dereference it, so we can | |
2703 | ignore this constraint. When we handle pointer subtraction, | |
2704 | we may have to do something cute here. */ | |
c58936b6 | 2705 | |
18455d17 RG |
2706 | if (result->offset < get_varinfo (result->var)->fullsize |
2707 | && bitmaxsize != 0) | |
dd68d988 DB |
2708 | { |
2709 | /* It's also not true that the constraint will actually start at the | |
2710 | right offset, it may start in some padding. We only care about | |
2711 | setting the constraint to the first actual field it touches, so | |
c58936b6 | 2712 | walk to find it. */ |
dd68d988 | 2713 | varinfo_t curr; |
4ee00913 | 2714 | for (curr = get_varinfo (result->var); curr; curr = curr->next) |
dd68d988 DB |
2715 | { |
2716 | if (offset_overlaps_with_access (curr->offset, curr->size, | |
a555a02c | 2717 | result->offset, bitmaxsize)) |
dd68d988 | 2718 | { |
4ee00913 | 2719 | result->var = curr->id; |
dd68d988 | 2720 | break; |
dd68d988 DB |
2721 | } |
2722 | } | |
2723 | /* assert that we found *some* field there. The user couldn't be | |
2724 | accessing *only* padding. */ | |
4ee00913 DB |
2725 | /* Still the user could access one past the end of an array |
2726 | embedded in a struct resulting in accessing *only* padding. */ | |
2727 | gcc_assert (curr || ref_contains_array_ref (orig_t)); | |
dd68d988 | 2728 | } |
18455d17 RG |
2729 | else if (bitmaxsize == 0) |
2730 | { | |
2731 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
2732 | fprintf (dump_file, "Access to zero-sized part of variable," | |
2733 | "ignoring\n"); | |
2734 | } | |
910fdc79 DB |
2735 | else |
2736 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
2737 | fprintf (dump_file, "Access to past the end of variable, ignoring\n"); | |
2738 | ||
4ee00913 | 2739 | result->offset = 0; |
910fdc79 | 2740 | } |
7b765bed DB |
2741 | else if (bitmaxsize == -1) |
2742 | { | |
2743 | /* We can't handle DEREF constraints with unknown size, we'll | |
2744 | get the wrong answer. Punt and return anything. */ | |
2745 | result->var = anything_id; | |
2746 | result->offset = 0; | |
2747 | } | |
910fdc79 DB |
2748 | } |
2749 | ||
2750 | ||
2751 | /* Dereference the constraint expression CONS, and return the result. | |
2752 | DEREF (ADDRESSOF) = SCALAR | |
2753 | DEREF (SCALAR) = DEREF | |
2754 | DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp)) | |
2755 | This is needed so that we can handle dereferencing DEREF constraints. */ | |
2756 | ||
4ee00913 DB |
2757 | static void |
2758 | do_deref (VEC (ce_s, heap) **constraints) | |
910fdc79 | 2759 | { |
4ee00913 DB |
2760 | struct constraint_expr *c; |
2761 | unsigned int i = 0; | |
c58936b6 | 2762 | |
4ee00913 | 2763 | for (i = 0; VEC_iterate (ce_s, *constraints, i, c); i++) |
910fdc79 | 2764 | { |
4ee00913 DB |
2765 | if (c->type == SCALAR) |
2766 | c->type = DEREF; | |
2767 | else if (c->type == ADDRESSOF) | |
2768 | c->type = SCALAR; | |
2769 | else if (c->type == DEREF) | |
2770 | { | |
2771 | tree tmpvar = create_tmp_var_raw (ptr_type_node, "dereftmp"); | |
2772 | struct constraint_expr tmplhs = get_constraint_exp_from_ssa_var (tmpvar); | |
2773 | process_constraint (new_constraint (tmplhs, *c)); | |
2774 | c->var = tmplhs.var; | |
2775 | } | |
2776 | else | |
2777 | gcc_unreachable (); | |
910fdc79 | 2778 | } |
910fdc79 DB |
2779 | } |
2780 | ||
910fdc79 DB |
2781 | /* Given a tree T, return the constraint expression for it. */ |
2782 | ||
4ee00913 | 2783 | static void |
1d85354c | 2784 | get_constraint_for (tree t, VEC (ce_s, heap) **results) |
910fdc79 DB |
2785 | { |
2786 | struct constraint_expr temp; | |
2787 | ||
2788 | /* x = integer is all glommed to a single variable, which doesn't | |
2789 | point to anything by itself. That is, of course, unless it is an | |
2790 | integer constant being treated as a pointer, in which case, we | |
2791 | will return that this is really the addressof anything. This | |
2792 | happens below, since it will fall into the default case. The only | |
2793 | case we know something about an integer treated like a pointer is | |
2794 | when it is the NULL pointer, and then we just say it points to | |
2795 | NULL. */ | |
2796 | if (TREE_CODE (t) == INTEGER_CST | |
7b765bed | 2797 | && integer_zerop (t)) |
910fdc79 DB |
2798 | { |
2799 | temp.var = nothing_id; | |
2800 | temp.type = ADDRESSOF; | |
2801 | temp.offset = 0; | |
4ee00913 DB |
2802 | VEC_safe_push (ce_s, heap, *results, &temp); |
2803 | return; | |
910fdc79 DB |
2804 | } |
2805 | ||
2806 | switch (TREE_CODE_CLASS (TREE_CODE (t))) | |
2807 | { | |
2808 | case tcc_expression: | |
5039610b | 2809 | case tcc_vl_exp: |
910fdc79 DB |
2810 | { |
2811 | switch (TREE_CODE (t)) | |
2812 | { | |
2813 | case ADDR_EXPR: | |
2814 | { | |
4ee00913 DB |
2815 | struct constraint_expr *c; |
2816 | unsigned int i; | |
a916f21d | 2817 | tree exp = TREE_OPERAND (t, 0); |
6df11ca1 | 2818 | tree pttype = TREE_TYPE (TREE_TYPE (t)); |
a916f21d RG |
2819 | |
2820 | get_constraint_for (exp, results); | |
6e7e772d | 2821 | |
c58936b6 | 2822 | |
7b765bed DB |
2823 | /* Complex types are special. Taking the address of one |
2824 | allows you to access either part of it through that | |
2825 | pointer. */ | |
2826 | if (VEC_length (ce_s, *results) == 1 && | |
2827 | TREE_CODE (pttype) == COMPLEX_TYPE) | |
6df11ca1 DB |
2828 | { |
2829 | struct constraint_expr *origrhs; | |
2830 | varinfo_t origvar; | |
2831 | struct constraint_expr tmp; | |
2832 | ||
2833 | gcc_assert (VEC_length (ce_s, *results) == 1); | |
2834 | origrhs = VEC_last (ce_s, *results); | |
2835 | tmp = *origrhs; | |
2836 | VEC_pop (ce_s, *results); | |
2837 | origvar = get_varinfo (origrhs->var); | |
2838 | for (; origvar; origvar = origvar->next) | |
2839 | { | |
2840 | tmp.var = origvar->id; | |
2841 | VEC_safe_push (ce_s, heap, *results, &tmp); | |
2842 | } | |
2843 | } | |
c58936b6 | 2844 | |
4ee00913 DB |
2845 | for (i = 0; VEC_iterate (ce_s, *results, i, c); i++) |
2846 | { | |
2847 | if (c->type == DEREF) | |
2848 | c->type = SCALAR; | |
c58936b6 | 2849 | else |
4ee00913 DB |
2850 | c->type = ADDRESSOF; |
2851 | } | |
2852 | return; | |
910fdc79 DB |
2853 | } |
2854 | break; | |
2855 | case CALL_EXPR: | |
910fdc79 DB |
2856 | /* XXX: In interprocedural mode, if we didn't have the |
2857 | body, we would need to do *each pointer argument = | |
2858 | &ANYTHING added. */ | |
2859 | if (call_expr_flags (t) & (ECF_MALLOC | ECF_MAY_BE_ALLOCA)) | |
2860 | { | |
e8ca4159 | 2861 | varinfo_t vi; |
c900f6aa | 2862 | tree heapvar = heapvar_lookup (t); |
c58936b6 | 2863 | |
c900f6aa | 2864 | if (heapvar == NULL) |
c58936b6 | 2865 | { |
c900f6aa DB |
2866 | heapvar = create_tmp_var_raw (ptr_type_node, "HEAP"); |
2867 | DECL_EXTERNAL (heapvar) = 1; | |
ae536040 | 2868 | get_var_ann (heapvar)->is_heapvar = 1; |
5cd4ec7f | 2869 | if (gimple_referenced_vars (cfun)) |
f004ab02 | 2870 | add_referenced_var (heapvar); |
c900f6aa DB |
2871 | heapvar_insert (t, heapvar); |
2872 | } | |
2873 | ||
910fdc79 DB |
2874 | temp.var = create_variable_info_for (heapvar, |
2875 | alias_get_name (heapvar)); | |
c58936b6 | 2876 | |
e8ca4159 DN |
2877 | vi = get_varinfo (temp.var); |
2878 | vi->is_artificial_var = 1; | |
2879 | vi->is_heap_var = 1; | |
3e5937d7 | 2880 | temp.type = ADDRESSOF; |
910fdc79 | 2881 | temp.offset = 0; |
4ee00913 DB |
2882 | VEC_safe_push (ce_s, heap, *results, &temp); |
2883 | return; | |
910fdc79 | 2884 | } |
21392f19 DB |
2885 | else |
2886 | { | |
c58936b6 | 2887 | temp.var = anything_id; |
21392f19 DB |
2888 | temp.type = SCALAR; |
2889 | temp.offset = 0; | |
2890 | VEC_safe_push (ce_s, heap, *results, &temp); | |
2891 | return; | |
2892 | } | |
2893 | break; | |
910fdc79 DB |
2894 | default: |
2895 | { | |
2896 | temp.type = ADDRESSOF; | |
2897 | temp.var = anything_id; | |
2898 | temp.offset = 0; | |
4ee00913 DB |
2899 | VEC_safe_push (ce_s, heap, *results, &temp); |
2900 | return; | |
910fdc79 DB |
2901 | } |
2902 | } | |
2903 | } | |
2904 | case tcc_reference: | |
2905 | { | |
2906 | switch (TREE_CODE (t)) | |
2907 | { | |
2908 | case INDIRECT_REF: | |
2909 | { | |
1d85354c | 2910 | get_constraint_for (TREE_OPERAND (t, 0), results); |
4ee00913 DB |
2911 | do_deref (results); |
2912 | return; | |
910fdc79 DB |
2913 | } |
2914 | case ARRAY_REF: | |
32961db5 | 2915 | case ARRAY_RANGE_REF: |
910fdc79 | 2916 | case COMPONENT_REF: |
1d85354c | 2917 | get_constraint_for_component_ref (t, results); |
4ee00913 | 2918 | return; |
910fdc79 DB |
2919 | default: |
2920 | { | |
2921 | temp.type = ADDRESSOF; | |
2922 | temp.var = anything_id; | |
2923 | temp.offset = 0; | |
4ee00913 DB |
2924 | VEC_safe_push (ce_s, heap, *results, &temp); |
2925 | return; | |
910fdc79 DB |
2926 | } |
2927 | } | |
2928 | } | |
2929 | case tcc_unary: | |
2930 | { | |
2931 | switch (TREE_CODE (t)) | |
2932 | { | |
2933 | case NOP_EXPR: | |
2934 | case CONVERT_EXPR: | |
2935 | case NON_LVALUE_EXPR: | |
2936 | { | |
2937 | tree op = TREE_OPERAND (t, 0); | |
c58936b6 | 2938 | |
910fdc79 DB |
2939 | /* Cast from non-pointer to pointers are bad news for us. |
2940 | Anything else, we see through */ | |
e8ca4159 DN |
2941 | if (!(POINTER_TYPE_P (TREE_TYPE (t)) |
2942 | && ! POINTER_TYPE_P (TREE_TYPE (op)))) | |
4ee00913 | 2943 | { |
1d85354c | 2944 | get_constraint_for (op, results); |
4ee00913 DB |
2945 | return; |
2946 | } | |
e8ca4159 DN |
2947 | |
2948 | /* FALLTHRU */ | |
910fdc79 DB |
2949 | } |
2950 | default: | |
2951 | { | |
2952 | temp.type = ADDRESSOF; | |
2953 | temp.var = anything_id; | |
2954 | temp.offset = 0; | |
4ee00913 DB |
2955 | VEC_safe_push (ce_s, heap, *results, &temp); |
2956 | return; | |
910fdc79 DB |
2957 | } |
2958 | } | |
2959 | } | |
2960 | case tcc_exceptional: | |
2961 | { | |
2962 | switch (TREE_CODE (t)) | |
2963 | { | |
c58936b6 | 2964 | case PHI_NODE: |
4ee00913 | 2965 | { |
1d85354c | 2966 | get_constraint_for (PHI_RESULT (t), results); |
4ee00913 DB |
2967 | return; |
2968 | } | |
2969 | break; | |
910fdc79 | 2970 | case SSA_NAME: |
4ee00913 DB |
2971 | { |
2972 | struct constraint_expr temp; | |
2973 | temp = get_constraint_exp_from_ssa_var (t); | |
2974 | VEC_safe_push (ce_s, heap, *results, &temp); | |
2975 | return; | |
2976 | } | |
2977 | break; | |
910fdc79 DB |
2978 | default: |
2979 | { | |
2980 | temp.type = ADDRESSOF; | |
2981 | temp.var = anything_id; | |
2982 | temp.offset = 0; | |
4ee00913 DB |
2983 | VEC_safe_push (ce_s, heap, *results, &temp); |
2984 | return; | |
910fdc79 DB |
2985 | } |
2986 | } | |
2987 | } | |
2988 | case tcc_declaration: | |
4ee00913 DB |
2989 | { |
2990 | struct constraint_expr temp; | |
2991 | temp = get_constraint_exp_from_ssa_var (t); | |
2992 | VEC_safe_push (ce_s, heap, *results, &temp); | |
2993 | return; | |
2994 | } | |
910fdc79 DB |
2995 | default: |
2996 | { | |
2997 | temp.type = ADDRESSOF; | |
2998 | temp.var = anything_id; | |
2999 | temp.offset = 0; | |
4ee00913 DB |
3000 | VEC_safe_push (ce_s, heap, *results, &temp); |
3001 | return; | |
910fdc79 DB |
3002 | } |
3003 | } | |
3004 | } | |
3005 | ||
3006 | ||
3007 | /* Handle the structure copy case where we have a simple structure copy | |
c58936b6 DB |
3008 | between LHS and RHS that is of SIZE (in bits) |
3009 | ||
910fdc79 DB |
3010 | For each field of the lhs variable (lhsfield) |
3011 | For each field of the rhs variable at lhsfield.offset (rhsfield) | |
3012 | add the constraint lhsfield = rhsfield | |
910fdc79 | 3013 | |
03190594 DB |
3014 | If we fail due to some kind of type unsafety or other thing we |
3015 | can't handle, return false. We expect the caller to collapse the | |
3016 | variable in that case. */ | |
3017 | ||
3018 | static bool | |
910fdc79 DB |
3019 | do_simple_structure_copy (const struct constraint_expr lhs, |
3020 | const struct constraint_expr rhs, | |
3021 | const unsigned HOST_WIDE_INT size) | |
3022 | { | |
3023 | varinfo_t p = get_varinfo (lhs.var); | |
a5eadacc | 3024 | unsigned HOST_WIDE_INT pstart, last; |
910fdc79 DB |
3025 | pstart = p->offset; |
3026 | last = p->offset + size; | |
3027 | for (; p && p->offset < last; p = p->next) | |
3028 | { | |
3029 | varinfo_t q; | |
3030 | struct constraint_expr templhs = lhs; | |
3031 | struct constraint_expr temprhs = rhs; | |
3032 | unsigned HOST_WIDE_INT fieldoffset; | |
3033 | ||
c58936b6 | 3034 | templhs.var = p->id; |
910fdc79 DB |
3035 | q = get_varinfo (temprhs.var); |
3036 | fieldoffset = p->offset - pstart; | |
3037 | q = first_vi_for_offset (q, q->offset + fieldoffset); | |
03190594 DB |
3038 | if (!q) |
3039 | return false; | |
910fdc79 DB |
3040 | temprhs.var = q->id; |
3041 | process_constraint (new_constraint (templhs, temprhs)); | |
3042 | } | |
03190594 | 3043 | return true; |
910fdc79 DB |
3044 | } |
3045 | ||
3046 | ||
3047 | /* Handle the structure copy case where we have a structure copy between a | |
3048 | aggregate on the LHS and a dereference of a pointer on the RHS | |
c58936b6 DB |
3049 | that is of SIZE (in bits) |
3050 | ||
910fdc79 DB |
3051 | For each field of the lhs variable (lhsfield) |
3052 | rhs.offset = lhsfield->offset | |
3053 | add the constraint lhsfield = rhs | |
3054 | */ | |
3055 | ||
3056 | static void | |
3057 | do_rhs_deref_structure_copy (const struct constraint_expr lhs, | |
3058 | const struct constraint_expr rhs, | |
3059 | const unsigned HOST_WIDE_INT size) | |
3060 | { | |
3061 | varinfo_t p = get_varinfo (lhs.var); | |
3062 | unsigned HOST_WIDE_INT pstart,last; | |
3063 | pstart = p->offset; | |
3064 | last = p->offset + size; | |
3065 | ||
3066 | for (; p && p->offset < last; p = p->next) | |
3067 | { | |
3068 | varinfo_t q; | |
3069 | struct constraint_expr templhs = lhs; | |
3070 | struct constraint_expr temprhs = rhs; | |
3071 | unsigned HOST_WIDE_INT fieldoffset; | |
3072 | ||
3073 | ||
3074 | if (templhs.type == SCALAR) | |
c58936b6 | 3075 | templhs.var = p->id; |
910fdc79 DB |
3076 | else |
3077 | templhs.offset = p->offset; | |
c58936b6 | 3078 | |
910fdc79 | 3079 | q = get_varinfo (temprhs.var); |
c58936b6 | 3080 | fieldoffset = p->offset - pstart; |
910fdc79 DB |
3081 | temprhs.offset += fieldoffset; |
3082 | process_constraint (new_constraint (templhs, temprhs)); | |
3083 | } | |
3084 | } | |
3085 | ||
3086 | /* Handle the structure copy case where we have a structure copy | |
110abdbc | 3087 | between an aggregate on the RHS and a dereference of a pointer on |
c58936b6 | 3088 | the LHS that is of SIZE (in bits) |
910fdc79 DB |
3089 | |
3090 | For each field of the rhs variable (rhsfield) | |
3091 | lhs.offset = rhsfield->offset | |
3092 | add the constraint lhs = rhsfield | |
3093 | */ | |
3094 | ||
3095 | static void | |
3096 | do_lhs_deref_structure_copy (const struct constraint_expr lhs, | |
3097 | const struct constraint_expr rhs, | |
3098 | const unsigned HOST_WIDE_INT size) | |
3099 | { | |
3100 | varinfo_t p = get_varinfo (rhs.var); | |
3101 | unsigned HOST_WIDE_INT pstart,last; | |
3102 | pstart = p->offset; | |
3103 | last = p->offset + size; | |
3104 | ||
3105 | for (; p && p->offset < last; p = p->next) | |
3106 | { | |
3107 | varinfo_t q; | |
3108 | struct constraint_expr templhs = lhs; | |
3109 | struct constraint_expr temprhs = rhs; | |
3110 | unsigned HOST_WIDE_INT fieldoffset; | |
3111 | ||
3112 | ||
3113 | if (temprhs.type == SCALAR) | |
c58936b6 | 3114 | temprhs.var = p->id; |
910fdc79 DB |
3115 | else |
3116 | temprhs.offset = p->offset; | |
c58936b6 | 3117 | |
910fdc79 | 3118 | q = get_varinfo (templhs.var); |
c58936b6 | 3119 | fieldoffset = p->offset - pstart; |
910fdc79 DB |
3120 | templhs.offset += fieldoffset; |
3121 | process_constraint (new_constraint (templhs, temprhs)); | |
3122 | } | |
3123 | } | |
3124 | ||
03190594 DB |
3125 | /* Sometimes, frontends like to give us bad type information. This |
3126 | function will collapse all the fields from VAR to the end of VAR, | |
c58936b6 | 3127 | into VAR, so that we treat those fields as a single variable. |
03190594 DB |
3128 | We return the variable they were collapsed into. */ |
3129 | ||
3130 | static unsigned int | |
3131 | collapse_rest_of_var (unsigned int var) | |
3132 | { | |
3133 | varinfo_t currvar = get_varinfo (var); | |
3134 | varinfo_t field; | |
3135 | ||
3136 | for (field = currvar->next; field; field = field->next) | |
3137 | { | |
3138 | if (dump_file) | |
c58936b6 | 3139 | fprintf (dump_file, "Type safety: Collapsing var %s into %s\n", |
03190594 | 3140 | field->name, currvar->name); |
c58936b6 | 3141 | |
03190594 DB |
3142 | gcc_assert (!field->collapsed_to); |
3143 | field->collapsed_to = currvar; | |
3144 | } | |
3145 | ||
3146 | currvar->next = NULL; | |
3147 | currvar->size = currvar->fullsize - currvar->offset; | |
c58936b6 | 3148 | |
03190594 DB |
3149 | return currvar->id; |
3150 | } | |
910fdc79 DB |
3151 | |
3152 | /* Handle aggregate copies by expanding into copies of the respective | |
3153 | fields of the structures. */ | |
3154 | ||
3155 | static void | |
3156 | do_structure_copy (tree lhsop, tree rhsop) | |
3157 | { | |
3158 | struct constraint_expr lhs, rhs, tmp; | |
4ee00913 | 3159 | VEC (ce_s, heap) *lhsc = NULL, *rhsc = NULL; |
910fdc79 DB |
3160 | varinfo_t p; |
3161 | unsigned HOST_WIDE_INT lhssize; | |
3162 | unsigned HOST_WIDE_INT rhssize; | |
3163 | ||
1d85354c RG |
3164 | get_constraint_for (lhsop, &lhsc); |
3165 | get_constraint_for (rhsop, &rhsc); | |
4ee00913 DB |
3166 | gcc_assert (VEC_length (ce_s, lhsc) == 1); |
3167 | gcc_assert (VEC_length (ce_s, rhsc) == 1); | |
3168 | lhs = *(VEC_last (ce_s, lhsc)); | |
3169 | rhs = *(VEC_last (ce_s, rhsc)); | |
c58936b6 | 3170 | |
4ee00913 DB |
3171 | VEC_free (ce_s, heap, lhsc); |
3172 | VEC_free (ce_s, heap, rhsc); | |
3173 | ||
910fdc79 | 3174 | /* If we have special var = x, swap it around. */ |
13c2c08b | 3175 | if (lhs.var <= integer_id && !(get_varinfo (rhs.var)->is_special_var)) |
910fdc79 DB |
3176 | { |
3177 | tmp = lhs; | |
3178 | lhs = rhs; | |
3179 | rhs = tmp; | |
3180 | } | |
c58936b6 | 3181 | |
a5eadacc DB |
3182 | /* This is fairly conservative for the RHS == ADDRESSOF case, in that it's |
3183 | possible it's something we could handle. However, most cases falling | |
3184 | into this are dealing with transparent unions, which are slightly | |
3185 | weird. */ | |
13c2c08b | 3186 | if (rhs.type == ADDRESSOF && !(get_varinfo (rhs.var)->is_special_var)) |
a5eadacc DB |
3187 | { |
3188 | rhs.type = ADDRESSOF; | |
3189 | rhs.var = anything_id; | |
3190 | } | |
3191 | ||
3192 | /* If the RHS is a special var, or an addressof, set all the LHS fields to | |
3193 | that special var. */ | |
910fdc79 DB |
3194 | if (rhs.var <= integer_id) |
3195 | { | |
3196 | for (p = get_varinfo (lhs.var); p; p = p->next) | |
3197 | { | |
3198 | struct constraint_expr templhs = lhs; | |
3199 | struct constraint_expr temprhs = rhs; | |
4ee00913 | 3200 | |
910fdc79 DB |
3201 | if (templhs.type == SCALAR ) |
3202 | templhs.var = p->id; | |
3203 | else | |
3204 | templhs.offset += p->offset; | |
3205 | process_constraint (new_constraint (templhs, temprhs)); | |
3206 | } | |
3207 | } | |
3208 | else | |
3209 | { | |
4e422b8b DB |
3210 | tree rhstype = TREE_TYPE (rhsop); |
3211 | tree lhstype = TREE_TYPE (lhsop); | |
4ee00913 DB |
3212 | tree rhstypesize; |
3213 | tree lhstypesize; | |
3214 | ||
3215 | lhstypesize = DECL_P (lhsop) ? DECL_SIZE (lhsop) : TYPE_SIZE (lhstype); | |
3216 | rhstypesize = DECL_P (rhsop) ? DECL_SIZE (rhsop) : TYPE_SIZE (rhstype); | |
4e422b8b DB |
3217 | |
3218 | /* If we have a variably sized types on the rhs or lhs, and a deref | |
3219 | constraint, add the constraint, lhsconstraint = &ANYTHING. | |
3220 | This is conservatively correct because either the lhs is an unknown | |
3221 | sized var (if the constraint is SCALAR), or the lhs is a DEREF | |
3222 | constraint, and every variable it can point to must be unknown sized | |
3223 | anyway, so we don't need to worry about fields at all. */ | |
3224 | if ((rhs.type == DEREF && TREE_CODE (rhstypesize) != INTEGER_CST) | |
3225 | || (lhs.type == DEREF && TREE_CODE (lhstypesize) != INTEGER_CST)) | |
3226 | { | |
3227 | rhs.var = anything_id; | |
3228 | rhs.type = ADDRESSOF; | |
3229 | rhs.offset = 0; | |
3230 | process_constraint (new_constraint (lhs, rhs)); | |
3231 | return; | |
3232 | } | |
3233 | ||
a5eadacc DB |
3234 | /* The size only really matters insofar as we don't set more or less of |
3235 | the variable. If we hit an unknown size var, the size should be the | |
3236 | whole darn thing. */ | |
3237 | if (get_varinfo (rhs.var)->is_unknown_size_var) | |
3238 | rhssize = ~0; | |
3239 | else | |
4e422b8b | 3240 | rhssize = TREE_INT_CST_LOW (rhstypesize); |
a5eadacc DB |
3241 | |
3242 | if (get_varinfo (lhs.var)->is_unknown_size_var) | |
3243 | lhssize = ~0; | |
3244 | else | |
4e422b8b | 3245 | lhssize = TREE_INT_CST_LOW (lhstypesize); |
a5eadacc | 3246 | |
c58936b6 DB |
3247 | |
3248 | if (rhs.type == SCALAR && lhs.type == SCALAR) | |
03190594 DB |
3249 | { |
3250 | if (!do_simple_structure_copy (lhs, rhs, MIN (lhssize, rhssize))) | |
c58936b6 | 3251 | { |
03190594 DB |
3252 | lhs.var = collapse_rest_of_var (lhs.var); |
3253 | rhs.var = collapse_rest_of_var (rhs.var); | |
3254 | lhs.offset = 0; | |
3255 | rhs.offset = 0; | |
3256 | lhs.type = SCALAR; | |
3257 | rhs.type = SCALAR; | |
3258 | process_constraint (new_constraint (lhs, rhs)); | |
3259 | } | |
3260 | } | |
910fdc79 DB |
3261 | else if (lhs.type != DEREF && rhs.type == DEREF) |
3262 | do_rhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize)); | |
3263 | else if (lhs.type == DEREF && rhs.type != DEREF) | |
3264 | do_lhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize)); | |
3265 | else | |
3266 | { | |
4e422b8b | 3267 | tree pointedtotype = lhstype; |
c58936b6 | 3268 | tree tmpvar; |
a5eadacc | 3269 | |
910fdc79 DB |
3270 | gcc_assert (rhs.type == DEREF && lhs.type == DEREF); |
3271 | tmpvar = create_tmp_var_raw (pointedtotype, "structcopydereftmp"); | |
a5eadacc DB |
3272 | do_structure_copy (tmpvar, rhsop); |
3273 | do_structure_copy (lhsop, tmpvar); | |
910fdc79 DB |
3274 | } |
3275 | } | |
3276 | } | |
3277 | ||
6e7e772d | 3278 | |
e8ca4159 DN |
3279 | /* Update related alias information kept in AI. This is used when |
3280 | building name tags, alias sets and deciding grouping heuristics. | |
3281 | STMT is the statement to process. This function also updates | |
3282 | ADDRESSABLE_VARS. */ | |
3283 | ||
3284 | static void | |
3285 | update_alias_info (tree stmt, struct alias_info *ai) | |
3286 | { | |
3287 | bitmap addr_taken; | |
3288 | use_operand_p use_p; | |
e8ca4159 | 3289 | ssa_op_iter iter; |
e9e0aa2c | 3290 | bool stmt_dereferences_ptr_p; |
21392f19 | 3291 | enum escape_type stmt_escape_type = is_escape_site (stmt); |
e9e0aa2c DN |
3292 | struct mem_ref_stats_d *mem_ref_stats = gimple_mem_ref_stats (cfun); |
3293 | ||
3294 | stmt_dereferences_ptr_p = false; | |
e8ca4159 | 3295 | |
21392f19 DB |
3296 | if (stmt_escape_type == ESCAPE_TO_CALL |
3297 | || stmt_escape_type == ESCAPE_TO_PURE_CONST) | |
3298 | { | |
e9e0aa2c | 3299 | mem_ref_stats->num_call_sites++; |
21392f19 | 3300 | if (stmt_escape_type == ESCAPE_TO_PURE_CONST) |
e9e0aa2c | 3301 | mem_ref_stats->num_pure_const_call_sites++; |
21392f19 | 3302 | } |
e9e0aa2c DN |
3303 | else if (stmt_escape_type == ESCAPE_TO_ASM) |
3304 | mem_ref_stats->num_asm_sites++; | |
21392f19 | 3305 | |
e8ca4159 DN |
3306 | /* Mark all the variables whose address are taken by the statement. */ |
3307 | addr_taken = addresses_taken (stmt); | |
3308 | if (addr_taken) | |
3309 | { | |
5cd4ec7f | 3310 | bitmap_ior_into (gimple_addressable_vars (cfun), addr_taken); |
e8ca4159 DN |
3311 | |
3312 | /* If STMT is an escape point, all the addresses taken by it are | |
3313 | call-clobbered. */ | |
d16a5e36 | 3314 | if (stmt_escape_type != NO_ESCAPE) |
e8ca4159 | 3315 | { |
3b302421 RG |
3316 | bitmap_iterator bi; |
3317 | unsigned i; | |
e8ca4159 | 3318 | |
3b302421 | 3319 | EXECUTE_IF_SET_IN_BITMAP (addr_taken, 0, i, bi) |
d16a5e36 | 3320 | { |
3b302421 | 3321 | tree rvar = referenced_var (i); |
d16a5e36 DB |
3322 | if (!unmodifiable_var_p (rvar)) |
3323 | mark_call_clobbered (rvar, stmt_escape_type); | |
3324 | } | |
e8ca4159 DN |
3325 | } |
3326 | } | |
3327 | ||
e9e0aa2c DN |
3328 | /* Process each operand use. For pointers, determine whether they |
3329 | are dereferenced by the statement, or whether their value | |
3330 | escapes, etc. */ | |
e8ca4159 DN |
3331 | FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE) |
3332 | { | |
3333 | tree op, var; | |
3334 | var_ann_t v_ann; | |
3335 | struct ptr_info_def *pi; | |
e9e0aa2c | 3336 | unsigned num_uses, num_loads, num_stores; |
e8ca4159 DN |
3337 | |
3338 | op = USE_FROM_PTR (use_p); | |
3339 | ||
3340 | /* If STMT is a PHI node, OP may be an ADDR_EXPR. If so, add it | |
3341 | to the set of addressable variables. */ | |
3342 | if (TREE_CODE (op) == ADDR_EXPR) | |
3343 | { | |
5cd4ec7f JH |
3344 | bitmap addressable_vars = gimple_addressable_vars (cfun); |
3345 | ||
e8ca4159 | 3346 | gcc_assert (TREE_CODE (stmt) == PHI_NODE); |
5cd4ec7f | 3347 | gcc_assert (addressable_vars); |
e8ca4159 DN |
3348 | |
3349 | /* PHI nodes don't have annotations for pinning the set | |
3350 | of addresses taken, so we collect them here. | |
3351 | ||
3352 | FIXME, should we allow PHI nodes to have annotations | |
3353 | so that they can be treated like regular statements? | |
3354 | Currently, they are treated as second-class | |
3355 | statements. */ | |
e9e0aa2c | 3356 | add_to_addressable_set (TREE_OPERAND (op, 0), &addressable_vars); |
e8ca4159 DN |
3357 | continue; |
3358 | } | |
3359 | ||
e9e0aa2c | 3360 | /* Ignore constants (they may occur in PHI node arguments). */ |
e8ca4159 DN |
3361 | if (TREE_CODE (op) != SSA_NAME) |
3362 | continue; | |
3363 | ||
3364 | var = SSA_NAME_VAR (op); | |
3365 | v_ann = var_ann (var); | |
3366 | ||
38635499 | 3367 | /* The base variable of an SSA name must be a GIMPLE register, and thus |
fd0bd278 ZD |
3368 | it cannot be aliased. */ |
3369 | gcc_assert (!may_be_aliased (var)); | |
e8ca4159 DN |
3370 | |
3371 | /* We are only interested in pointers. */ | |
3372 | if (!POINTER_TYPE_P (TREE_TYPE (op))) | |
3373 | continue; | |
3374 | ||
3375 | pi = get_ptr_info (op); | |
3376 | ||
3377 | /* Add OP to AI->PROCESSED_PTRS, if it's not there already. */ | |
3378 | if (!TEST_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (op))) | |
3379 | { | |
3380 | SET_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (op)); | |
d96f49bf | 3381 | VEC_safe_push (tree, heap, ai->processed_ptrs, op); |
e8ca4159 DN |
3382 | } |
3383 | ||
3384 | /* If STMT is a PHI node, then it will not have pointer | |
3385 | dereferences and it will not be an escape point. */ | |
3386 | if (TREE_CODE (stmt) == PHI_NODE) | |
3387 | continue; | |
3388 | ||
3389 | /* Determine whether OP is a dereferenced pointer, and if STMT | |
3390 | is an escape point, whether OP escapes. */ | |
e9e0aa2c | 3391 | count_uses_and_derefs (op, stmt, &num_uses, &num_loads, &num_stores); |
e8ca4159 | 3392 | |
17c7e33e DN |
3393 | /* Handle a corner case involving address expressions of the |
3394 | form '&PTR->FLD'. The problem with these expressions is that | |
3395 | they do not represent a dereference of PTR. However, if some | |
3396 | other transformation propagates them into an INDIRECT_REF | |
3397 | expression, we end up with '*(&PTR->FLD)' which is folded | |
3398 | into 'PTR->FLD'. | |
3399 | ||
3400 | So, if the original code had no other dereferences of PTR, | |
3401 | the aliaser will not create memory tags for it, and when | |
3402 | &PTR->FLD gets propagated to INDIRECT_REF expressions, the | |
38635499 | 3403 | memory operations will receive no VDEF/VUSE operands. |
17c7e33e DN |
3404 | |
3405 | One solution would be to have count_uses_and_derefs consider | |
3406 | &PTR->FLD a dereference of PTR. But that is wrong, since it | |
3407 | is not really a dereference but an offset calculation. | |
3408 | ||
3409 | What we do here is to recognize these special ADDR_EXPR | |
3410 | nodes. Since these expressions are never GIMPLE values (they | |
3411 | are not GIMPLE invariants), they can only appear on the RHS | |
3412 | of an assignment and their base address is always an | |
3413 | INDIRECT_REF expression. */ | |
07beea0d AH |
3414 | if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT |
3415 | && TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1)) == ADDR_EXPR | |
3416 | && !is_gimple_val (GIMPLE_STMT_OPERAND (stmt, 1))) | |
17c7e33e DN |
3417 | { |
3418 | /* If the RHS if of the form &PTR->FLD and PTR == OP, then | |
3419 | this represents a potential dereference of PTR. */ | |
07beea0d | 3420 | tree rhs = GIMPLE_STMT_OPERAND (stmt, 1); |
17c7e33e DN |
3421 | tree base = get_base_address (TREE_OPERAND (rhs, 0)); |
3422 | if (TREE_CODE (base) == INDIRECT_REF | |
3423 | && TREE_OPERAND (base, 0) == op) | |
e9e0aa2c | 3424 | num_loads++; |
17c7e33e DN |
3425 | } |
3426 | ||
e9e0aa2c | 3427 | if (num_loads + num_stores > 0) |
e8ca4159 DN |
3428 | { |
3429 | /* Mark OP as dereferenced. In a subsequent pass, | |
3430 | dereferenced pointers that point to a set of | |
3431 | variables will be assigned a name tag to alias | |
3432 | all the variables OP points to. */ | |
3433 | pi->is_dereferenced = 1; | |
3434 | ||
e8ca4159 DN |
3435 | /* If this is a store operation, mark OP as being |
3436 | dereferenced to store, otherwise mark it as being | |
3437 | dereferenced to load. */ | |
e9e0aa2c | 3438 | if (num_stores > 0) |
38635499 | 3439 | pointer_set_insert (ai->dereferenced_ptrs_store, var); |
e8ca4159 | 3440 | else |
38635499 | 3441 | pointer_set_insert (ai->dereferenced_ptrs_load, var); |
e9e0aa2c DN |
3442 | |
3443 | /* Update the frequency estimate for all the dereferences of | |
3444 | pointer OP. */ | |
3445 | update_mem_sym_stats_from_stmt (op, stmt, num_loads, num_stores); | |
7b765bed | 3446 | |
e9e0aa2c DN |
3447 | /* Indicate that STMT contains pointer dereferences. */ |
3448 | stmt_dereferences_ptr_p = true; | |
e8ca4159 DN |
3449 | } |
3450 | ||
e9e0aa2c | 3451 | if (stmt_escape_type != NO_ESCAPE && num_loads + num_stores < num_uses) |
e8ca4159 DN |
3452 | { |
3453 | /* If STMT is an escape point and STMT contains at | |
3454 | least one direct use of OP, then the value of OP | |
3455 | escapes and so the pointed-to variables need to | |
3456 | be marked call-clobbered. */ | |
3457 | pi->value_escapes_p = 1; | |
d16a5e36 | 3458 | pi->escape_mask |= stmt_escape_type; |
e8ca4159 DN |
3459 | |
3460 | /* If the statement makes a function call, assume | |
3461 | that pointer OP will be dereferenced in a store | |
3462 | operation inside the called function. */ | |
c58936b6 DB |
3463 | if (get_call_expr_in (stmt) |
3464 | || stmt_escape_type == ESCAPE_STORED_IN_GLOBAL) | |
e8ca4159 | 3465 | { |
38635499 | 3466 | pointer_set_insert (ai->dereferenced_ptrs_store, var); |
e8ca4159 DN |
3467 | pi->is_dereferenced = 1; |
3468 | } | |
3469 | } | |
3470 | } | |
3471 | ||
0bfac35f DB |
3472 | if (TREE_CODE (stmt) == PHI_NODE) |
3473 | return; | |
3474 | ||
38635499 | 3475 | /* Mark stored variables in STMT as being written to and update the |
e9e0aa2c DN |
3476 | memory reference stats for all memory symbols referenced by STMT. */ |
3477 | if (stmt_references_memory_p (stmt)) | |
e8ca4159 | 3478 | { |
3b302421 RG |
3479 | unsigned i; |
3480 | bitmap_iterator bi; | |
e9e0aa2c DN |
3481 | |
3482 | mem_ref_stats->num_mem_stmts++; | |
3483 | ||
3484 | /* Notice that we only update memory reference stats for symbols | |
3485 | loaded and stored by the statement if the statement does not | |
3486 | contain pointer dereferences and it is not a call/asm site. | |
3487 | This is to avoid double accounting problems when creating | |
3488 | memory partitions. After computing points-to information, | |
3489 | pointer dereference statistics are used to update the | |
3490 | reference stats of the pointed-to variables, so here we | |
3491 | should only update direct references to symbols. | |
3492 | ||
3493 | Indirect references are not updated here for two reasons: (1) | |
3494 | The first time we compute alias information, the sets | |
3495 | LOADED/STORED are empty for pointer dereferences, (2) After | |
3496 | partitioning, LOADED/STORED may have references to | |
3497 | partitions, not the original pointed-to variables. So, if we | |
3498 | always counted LOADED/STORED here and during partitioning, we | |
3499 | would count many symbols more than once. | |
3500 | ||
3501 | This does cause some imprecision when a statement has a | |
3502 | combination of direct symbol references and pointer | |
3503 | dereferences (e.g., MEMORY_VAR = *PTR) or if a call site has | |
3504 | memory symbols in its argument list, but these cases do not | |
7fa7289d | 3505 | occur so frequently as to constitute a serious problem. */ |
e9e0aa2c | 3506 | if (STORED_SYMS (stmt)) |
3b302421 | 3507 | EXECUTE_IF_SET_IN_BITMAP (STORED_SYMS (stmt), 0, i, bi) |
e9e0aa2c | 3508 | { |
3b302421 | 3509 | tree sym = referenced_var (i); |
e9e0aa2c DN |
3510 | pointer_set_insert (ai->written_vars, sym); |
3511 | if (!stmt_dereferences_ptr_p | |
3512 | && stmt_escape_type != ESCAPE_TO_CALL | |
3513 | && stmt_escape_type != ESCAPE_TO_PURE_CONST | |
3514 | && stmt_escape_type != ESCAPE_TO_ASM) | |
3515 | update_mem_sym_stats_from_stmt (sym, stmt, 0, 1); | |
3516 | } | |
3517 | ||
3518 | if (!stmt_dereferences_ptr_p | |
3519 | && LOADED_SYMS (stmt) | |
3520 | && stmt_escape_type != ESCAPE_TO_CALL | |
3521 | && stmt_escape_type != ESCAPE_TO_PURE_CONST | |
3522 | && stmt_escape_type != ESCAPE_TO_ASM) | |
3b302421 RG |
3523 | EXECUTE_IF_SET_IN_BITMAP (LOADED_SYMS (stmt), 0, i, bi) |
3524 | update_mem_sym_stats_from_stmt (referenced_var (i), stmt, 1, 0); | |
e8ca4159 DN |
3525 | } |
3526 | } | |
3527 | ||
3528 | ||
3529 | /* Handle pointer arithmetic EXPR when creating aliasing constraints. | |
3530 | Expressions of the type PTR + CST can be handled in two ways: | |
3531 | ||
3532 | 1- If the constraint for PTR is ADDRESSOF for a non-structure | |
3533 | variable, then we can use it directly because adding or | |
3534 | subtracting a constant may not alter the original ADDRESSOF | |
a4174ebf | 3535 | constraint (i.e., pointer arithmetic may not legally go outside |
e8ca4159 DN |
3536 | an object's boundaries). |
3537 | ||
3538 | 2- If the constraint for PTR is ADDRESSOF for a structure variable, | |
3539 | then if CST is a compile-time constant that can be used as an | |
3540 | offset, we can determine which sub-variable will be pointed-to | |
3541 | by the expression. | |
3542 | ||
3543 | Return true if the expression is handled. For any other kind of | |
3544 | expression, return false so that each operand can be added as a | |
3545 | separate constraint by the caller. */ | |
3546 | ||
3547 | static bool | |
4ee00913 | 3548 | handle_ptr_arith (VEC (ce_s, heap) *lhsc, tree expr) |
e8ca4159 DN |
3549 | { |
3550 | tree op0, op1; | |
4ee00913 DB |
3551 | struct constraint_expr *c, *c2; |
3552 | unsigned int i = 0; | |
3553 | unsigned int j = 0; | |
3554 | VEC (ce_s, heap) *temp = NULL; | |
7b765bed DB |
3555 | unsigned int rhsoffset = 0; |
3556 | bool unknown_addend = false; | |
e8ca4159 | 3557 | |
5be014d5 | 3558 | if (TREE_CODE (expr) != POINTER_PLUS_EXPR) |
e8ca4159 DN |
3559 | return false; |
3560 | ||
3561 | op0 = TREE_OPERAND (expr, 0); | |
3562 | op1 = TREE_OPERAND (expr, 1); | |
5be014d5 | 3563 | gcc_assert (POINTER_TYPE_P (TREE_TYPE (op0))); |
e8ca4159 | 3564 | |
1d85354c | 3565 | get_constraint_for (op0, &temp); |
c58936b6 | 3566 | |
7b765bed DB |
3567 | /* Handle non-constants by making constraints from integer. */ |
3568 | if (TREE_CODE (op1) == INTEGER_CST) | |
3569 | rhsoffset = TREE_INT_CST_LOW (op1) * BITS_PER_UNIT; | |
3570 | else | |
3571 | unknown_addend = true; | |
e8ca4159 | 3572 | |
4ee00913 DB |
3573 | for (i = 0; VEC_iterate (ce_s, lhsc, i, c); i++) |
3574 | for (j = 0; VEC_iterate (ce_s, temp, j, c2); j++) | |
3575 | { | |
3576 | if (c2->type == ADDRESSOF && rhsoffset != 0) | |
3577 | { | |
3578 | varinfo_t temp = get_varinfo (c2->var); | |
04743a37 RG |
3579 | |
3580 | /* An access one after the end of an array is valid, | |
3581 | so simply punt on accesses we cannot resolve. */ | |
3582 | temp = first_vi_for_offset (temp, rhsoffset); | |
3583 | if (temp == NULL) | |
3584 | continue; | |
3585 | c2->var = temp->id; | |
4ee00913 DB |
3586 | c2->offset = 0; |
3587 | } | |
7b765bed DB |
3588 | else if (unknown_addend) |
3589 | { | |
3590 | /* Can't handle *a + integer where integer is unknown. */ | |
3591 | if (c2->type != SCALAR) | |
3592 | { | |
3593 | struct constraint_expr intc; | |
3594 | intc.var = integer_id; | |
3595 | intc.offset = 0; | |
3596 | intc.type = SCALAR; | |
3597 | process_constraint (new_constraint (*c, intc)); | |
3598 | } | |
3599 | else | |
3600 | { | |
3601 | /* We known it lives somewhere within c2->var. */ | |
3602 | varinfo_t tmp = get_varinfo (c2->var); | |
3603 | for (; tmp; tmp = tmp->next) | |
3604 | { | |
3605 | struct constraint_expr tmpc = *c2; | |
3606 | c2->var = tmp->id; | |
3607 | c2->offset = 0; | |
3608 | process_constraint (new_constraint (*c, tmpc)); | |
3609 | } | |
3610 | } | |
3611 | } | |
4ee00913 DB |
3612 | else |
3613 | c2->offset = rhsoffset; | |
3614 | process_constraint (new_constraint (*c, *c2)); | |
3615 | } | |
e8ca4159 | 3616 | |
4ee00913 | 3617 | VEC_free (ce_s, heap, temp); |
e8ca4159 DN |
3618 | |
3619 | return true; | |
3620 | } | |
3621 | ||
7b765bed DB |
3622 | /* For non-IPA mode, generate constraints necessary for a call on the |
3623 | RHS. */ | |
3624 | ||
3625 | static void | |
3626 | handle_rhs_call (tree rhs) | |
3627 | { | |
3628 | tree arg; | |
3629 | call_expr_arg_iterator iter; | |
3630 | struct constraint_expr rhsc; | |
3631 | ||
3632 | rhsc.var = anything_id; | |
3633 | rhsc.offset = 0; | |
3634 | rhsc.type = ADDRESSOF; | |
3635 | ||
3636 | FOR_EACH_CALL_EXPR_ARG (arg, iter, rhs) | |
3637 | { | |
3638 | VEC(ce_s, heap) *lhsc = NULL; | |
3639 | ||
3640 | /* Find those pointers being passed, and make sure they end up | |
3641 | pointing to anything. */ | |
3642 | if (POINTER_TYPE_P (TREE_TYPE (arg))) | |
3643 | { | |
3644 | unsigned int j; | |
3645 | struct constraint_expr *lhsp; | |
3646 | ||
3647 | get_constraint_for (arg, &lhsc); | |
3648 | do_deref (&lhsc); | |
3649 | for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++) | |
3650 | process_constraint_1 (new_constraint (*lhsp, rhsc), true); | |
3651 | VEC_free (ce_s, heap, lhsc); | |
3652 | } | |
3653 | } | |
3654 | } | |
e8ca4159 | 3655 | |
af947da7 RG |
3656 | /* For non-IPA mode, generate constraints necessary for a call |
3657 | that returns a pointer and assigns it to LHS. This simply makes | |
3658 | the LHS point to anything. */ | |
3659 | ||
3660 | static void | |
3661 | handle_lhs_call (tree lhs) | |
3662 | { | |
3663 | VEC(ce_s, heap) *lhsc = NULL; | |
3664 | struct constraint_expr rhsc; | |
3665 | unsigned int j; | |
3666 | struct constraint_expr *lhsp; | |
3667 | ||
3668 | rhsc.var = anything_id; | |
3669 | rhsc.offset = 0; | |
3670 | rhsc.type = ADDRESSOF; | |
3671 | get_constraint_for (lhs, &lhsc); | |
3672 | for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++) | |
3673 | process_constraint_1 (new_constraint (*lhsp, rhsc), true); | |
3674 | VEC_free (ce_s, heap, lhsc); | |
3675 | } | |
3676 | ||
e8ca4159 DN |
3677 | /* Walk statement T setting up aliasing constraints according to the |
3678 | references found in T. This function is the main part of the | |
3679 | constraint builder. AI points to auxiliary alias information used | |
3680 | when building alias sets and computing alias grouping heuristics. */ | |
910fdc79 DB |
3681 | |
3682 | static void | |
4ee00913 | 3683 | find_func_aliases (tree origt) |
910fdc79 | 3684 | { |
4ee00913 DB |
3685 | tree t = origt; |
3686 | VEC(ce_s, heap) *lhsc = NULL; | |
3687 | VEC(ce_s, heap) *rhsc = NULL; | |
3688 | struct constraint_expr *c; | |
910fdc79 | 3689 | |
4ee00913 DB |
3690 | if (TREE_CODE (t) == RETURN_EXPR && TREE_OPERAND (t, 0)) |
3691 | t = TREE_OPERAND (t, 0); | |
910fdc79 | 3692 | |
e8ca4159 DN |
3693 | /* Now build constraints expressions. */ |
3694 | if (TREE_CODE (t) == PHI_NODE) | |
3695 | { | |
6df11ca1 DB |
3696 | gcc_assert (!AGGREGATE_TYPE_P (TREE_TYPE (PHI_RESULT (t)))); |
3697 | ||
e8ca4159 DN |
3698 | /* Only care about pointers and structures containing |
3699 | pointers. */ | |
21392f19 | 3700 | if (could_have_pointers (PHI_RESULT (t))) |
e8ca4159 DN |
3701 | { |
3702 | int i; | |
4ee00913 | 3703 | unsigned int j; |
c58936b6 | 3704 | |
4ee00913 DB |
3705 | /* For a phi node, assign all the arguments to |
3706 | the result. */ | |
1d85354c | 3707 | get_constraint_for (PHI_RESULT (t), &lhsc); |
e8ca4159 | 3708 | for (i = 0; i < PHI_NUM_ARGS (t); i++) |
c58936b6 | 3709 | { |
0a4288d9 RG |
3710 | tree rhstype; |
3711 | tree strippedrhs = PHI_ARG_DEF (t, i); | |
3712 | ||
3713 | STRIP_NOPS (strippedrhs); | |
3714 | rhstype = TREE_TYPE (strippedrhs); | |
1d85354c | 3715 | get_constraint_for (PHI_ARG_DEF (t, i), &rhsc); |
0a4288d9 | 3716 | |
4ee00913 DB |
3717 | for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++) |
3718 | { | |
3719 | struct constraint_expr *c2; | |
3720 | while (VEC_length (ce_s, rhsc) > 0) | |
3721 | { | |
3722 | c2 = VEC_last (ce_s, rhsc); | |
3723 | process_constraint (new_constraint (*c, *c2)); | |
3724 | VEC_pop (ce_s, rhsc); | |
3725 | } | |
3726 | } | |
c58936b6 | 3727 | } |
4ee00913 DB |
3728 | } |
3729 | } | |
3730 | /* In IPA mode, we need to generate constraints to pass call | |
6e7e772d DN |
3731 | arguments through their calls. There are two cases, either a |
3732 | GIMPLE_MODIFY_STMT when we are returning a value, or just a plain | |
7b765bed DB |
3733 | CALL_EXPR when we are not. |
3734 | ||
3735 | In non-ipa mode, we need to generate constraints for each | |
3736 | pointer passed by address. */ | |
3737 | else if (((TREE_CODE (t) == GIMPLE_MODIFY_STMT | |
3738 | && TREE_CODE (GIMPLE_STMT_OPERAND (t, 1)) == CALL_EXPR | |
3739 | && !(call_expr_flags (GIMPLE_STMT_OPERAND (t, 1)) | |
3740 | & (ECF_MALLOC | ECF_MAY_BE_ALLOCA))) | |
3741 | || (TREE_CODE (t) == CALL_EXPR | |
3742 | && !(call_expr_flags (t) | |
3743 | & (ECF_MALLOC | ECF_MAY_BE_ALLOCA))))) | |
4ee00913 | 3744 | { |
7b765bed | 3745 | if (!in_ipa_mode) |
4ee00913 | 3746 | { |
7b765bed | 3747 | if (TREE_CODE (t) == GIMPLE_MODIFY_STMT) |
af947da7 RG |
3748 | { |
3749 | handle_rhs_call (GIMPLE_STMT_OPERAND (t, 1)); | |
3750 | if (POINTER_TYPE_P (TREE_TYPE (GIMPLE_STMT_OPERAND (t, 1)))) | |
3751 | handle_lhs_call (GIMPLE_STMT_OPERAND (t, 0)); | |
3752 | } | |
7b765bed DB |
3753 | else |
3754 | handle_rhs_call (t); | |
4ee00913 DB |
3755 | } |
3756 | else | |
3757 | { | |
7b765bed DB |
3758 | tree lhsop; |
3759 | tree rhsop; | |
3760 | tree arg; | |
3761 | call_expr_arg_iterator iter; | |
3762 | varinfo_t fi; | |
3763 | int i = 1; | |
3764 | tree decl; | |
3765 | if (TREE_CODE (t) == GIMPLE_MODIFY_STMT) | |
e8ca4159 | 3766 | { |
7b765bed DB |
3767 | lhsop = GIMPLE_STMT_OPERAND (t, 0); |
3768 | rhsop = GIMPLE_STMT_OPERAND (t, 1); | |
4ee00913 DB |
3769 | } |
3770 | else | |
3771 | { | |
7b765bed DB |
3772 | lhsop = NULL; |
3773 | rhsop = t; | |
e8ca4159 | 3774 | } |
7b765bed DB |
3775 | decl = get_callee_fndecl (rhsop); |
3776 | ||
3777 | /* If we can directly resolve the function being called, do so. | |
3778 | Otherwise, it must be some sort of indirect expression that | |
3779 | we should still be able to handle. */ | |
3780 | if (decl) | |
4ee00913 | 3781 | { |
7b765bed DB |
3782 | fi = get_vi_for_tree (decl); |
3783 | } | |
3784 | else | |
3785 | { | |
3786 | decl = CALL_EXPR_FN (rhsop); | |
3787 | fi = get_vi_for_tree (decl); | |
4ee00913 | 3788 | } |
6e7e772d | 3789 | |
7b765bed DB |
3790 | /* Assign all the passed arguments to the appropriate incoming |
3791 | parameters of the function. */ | |
c58936b6 | 3792 | |
7b765bed | 3793 | FOR_EACH_CALL_EXPR_ARG (arg, iter, rhsop) |
4ee00913 | 3794 | { |
7b765bed DB |
3795 | struct constraint_expr lhs ; |
3796 | struct constraint_expr *rhsp; | |
3797 | ||
3798 | get_constraint_for (arg, &rhsc); | |
3799 | if (TREE_CODE (decl) != FUNCTION_DECL) | |
3800 | { | |
3801 | lhs.type = DEREF; | |
3802 | lhs.var = fi->id; | |
3803 | lhs.offset = i; | |
3804 | } | |
3805 | else | |
3806 | { | |
3807 | lhs.type = SCALAR; | |
3808 | lhs.var = first_vi_for_offset (fi, i)->id; | |
3809 | lhs.offset = 0; | |
3810 | } | |
3811 | while (VEC_length (ce_s, rhsc) != 0) | |
3812 | { | |
3813 | rhsp = VEC_last (ce_s, rhsc); | |
3814 | process_constraint (new_constraint (lhs, *rhsp)); | |
3815 | VEC_pop (ce_s, rhsc); | |
3816 | } | |
3817 | i++; | |
4ee00913 | 3818 | } |
7b765bed DB |
3819 | |
3820 | /* If we are returning a value, assign it to the result. */ | |
3821 | if (lhsop) | |
4ee00913 | 3822 | { |
7b765bed DB |
3823 | struct constraint_expr rhs; |
3824 | struct constraint_expr *lhsp; | |
3825 | unsigned int j = 0; | |
3826 | ||
3827 | get_constraint_for (lhsop, &lhsc); | |
3828 | if (TREE_CODE (decl) != FUNCTION_DECL) | |
3829 | { | |
3830 | rhs.type = DEREF; | |
3831 | rhs.var = fi->id; | |
3832 | rhs.offset = i; | |
3833 | } | |
3834 | else | |
3835 | { | |
3836 | rhs.type = SCALAR; | |
3837 | rhs.var = first_vi_for_offset (fi, i)->id; | |
3838 | rhs.offset = 0; | |
3839 | } | |
3840 | for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++) | |
3841 | process_constraint (new_constraint (*lhsp, rhs)); | |
4ee00913 | 3842 | } |
c58936b6 | 3843 | } |
e8ca4159 | 3844 | } |
4ee00913 | 3845 | /* Otherwise, just a regular assignment statement. */ |
07beea0d | 3846 | else if (TREE_CODE (t) == GIMPLE_MODIFY_STMT) |
e8ca4159 | 3847 | { |
07beea0d AH |
3848 | tree lhsop = GIMPLE_STMT_OPERAND (t, 0); |
3849 | tree rhsop = GIMPLE_STMT_OPERAND (t, 1); | |
4ee00913 | 3850 | int i; |
e8ca4159 | 3851 | |
c58936b6 | 3852 | if ((AGGREGATE_TYPE_P (TREE_TYPE (lhsop)) |
98b2060a RG |
3853 | || TREE_CODE (TREE_TYPE (lhsop)) == COMPLEX_TYPE) |
3854 | && (AGGREGATE_TYPE_P (TREE_TYPE (rhsop)) | |
3855 | || TREE_CODE (TREE_TYPE (lhsop)) == COMPLEX_TYPE)) | |
e8ca4159 DN |
3856 | { |
3857 | do_structure_copy (lhsop, rhsop); | |
3858 | } | |
3859 | else | |
3860 | { | |
3861 | /* Only care about operations with pointers, structures | |
3862 | containing pointers, dereferences, and call expressions. */ | |
21392f19 | 3863 | if (could_have_pointers (lhsop) |
e8ca4159 DN |
3864 | || TREE_CODE (rhsop) == CALL_EXPR) |
3865 | { | |
1d85354c | 3866 | get_constraint_for (lhsop, &lhsc); |
e8ca4159 DN |
3867 | switch (TREE_CODE_CLASS (TREE_CODE (rhsop))) |
3868 | { | |
3869 | /* RHS that consist of unary operations, | |
3870 | exceptional types, or bare decls/constants, get | |
c58936b6 | 3871 | handled directly by get_constraint_for. */ |
910fdc79 DB |
3872 | case tcc_reference: |
3873 | case tcc_declaration: | |
3874 | case tcc_constant: | |
3875 | case tcc_exceptional: | |
3876 | case tcc_expression: | |
5039610b | 3877 | case tcc_vl_exp: |
910fdc79 | 3878 | case tcc_unary: |
e8ca4159 | 3879 | { |
4ee00913 | 3880 | unsigned int j; |
4ee00913 | 3881 | |
6df11ca1 | 3882 | get_constraint_for (rhsop, &rhsc); |
4ee00913 DB |
3883 | for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++) |
3884 | { | |
3885 | struct constraint_expr *c2; | |
3886 | unsigned int k; | |
c58936b6 | 3887 | |
4ee00913 DB |
3888 | for (k = 0; VEC_iterate (ce_s, rhsc, k, c2); k++) |
3889 | process_constraint (new_constraint (*c, *c2)); | |
3890 | } | |
3891 | ||
e8ca4159 | 3892 | } |
910fdc79 DB |
3893 | break; |
3894 | ||
e8ca4159 DN |
3895 | case tcc_binary: |
3896 | { | |
3897 | /* For pointer arithmetic of the form | |
3898 | PTR + CST, we can simply use PTR's | |
3899 | constraint because pointer arithmetic is | |
3900 | not allowed to go out of bounds. */ | |
4ee00913 | 3901 | if (handle_ptr_arith (lhsc, rhsop)) |
e8ca4159 DN |
3902 | break; |
3903 | } | |
3904 | /* FALLTHRU */ | |
3905 | ||
3906 | /* Otherwise, walk each operand. Notice that we | |
3907 | can't use the operand interface because we need | |
3908 | to process expressions other than simple operands | |
3909 | (e.g. INDIRECT_REF, ADDR_EXPR, CALL_EXPR). */ | |
910fdc79 | 3910 | default: |
5039610b | 3911 | for (i = 0; i < TREE_OPERAND_LENGTH (rhsop); i++) |
910fdc79 DB |
3912 | { |
3913 | tree op = TREE_OPERAND (rhsop, i); | |
4ee00913 DB |
3914 | unsigned int j; |
3915 | ||
3916 | gcc_assert (VEC_length (ce_s, rhsc) == 0); | |
1d85354c | 3917 | get_constraint_for (op, &rhsc); |
4ee00913 DB |
3918 | for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++) |
3919 | { | |
3920 | struct constraint_expr *c2; | |
3921 | while (VEC_length (ce_s, rhsc) > 0) | |
3922 | { | |
3923 | c2 = VEC_last (ce_s, rhsc); | |
3924 | process_constraint (new_constraint (*c, *c2)); | |
3925 | VEC_pop (ce_s, rhsc); | |
3926 | } | |
3927 | } | |
910fdc79 | 3928 | } |
c58936b6 | 3929 | } |
e8ca4159 DN |
3930 | } |
3931 | } | |
910fdc79 | 3932 | } |
058dcc25 ILT |
3933 | else if (TREE_CODE (t) == CHANGE_DYNAMIC_TYPE_EXPR) |
3934 | { | |
3935 | unsigned int j; | |
3936 | ||
3937 | get_constraint_for (CHANGE_DYNAMIC_TYPE_LOCATION (t), &lhsc); | |
3938 | for (j = 0; VEC_iterate (ce_s, lhsc, j, c); ++j) | |
3939 | get_varinfo (c->var)->no_tbaa_pruning = true; | |
3940 | } | |
e8ca4159 DN |
3941 | |
3942 | /* After promoting variables and computing aliasing we will | |
3943 | need to re-scan most statements. FIXME: Try to minimize the | |
3944 | number of statements re-scanned. It's not really necessary to | |
c58936b6 | 3945 | re-scan *all* statements. */ |
4ee00913 DB |
3946 | mark_stmt_modified (origt); |
3947 | VEC_free (ce_s, heap, rhsc); | |
3948 | VEC_free (ce_s, heap, lhsc); | |
910fdc79 DB |
3949 | } |
3950 | ||
3951 | ||
3952 | /* Find the first varinfo in the same variable as START that overlaps with | |
3953 | OFFSET. | |
3954 | Effectively, walk the chain of fields for the variable START to find the | |
3955 | first field that overlaps with OFFSET. | |
8971094d | 3956 | Return NULL if we can't find one. */ |
910fdc79 | 3957 | |
c58936b6 | 3958 | static varinfo_t |
910fdc79 DB |
3959 | first_vi_for_offset (varinfo_t start, unsigned HOST_WIDE_INT offset) |
3960 | { | |
3961 | varinfo_t curr = start; | |
3962 | while (curr) | |
3963 | { | |
3964 | /* We may not find a variable in the field list with the actual | |
3965 | offset when when we have glommed a structure to a variable. | |
3966 | In that case, however, offset should still be within the size | |
3967 | of the variable. */ | |
3968 | if (offset >= curr->offset && offset < (curr->offset + curr->size)) | |
3969 | return curr; | |
3970 | curr = curr->next; | |
3971 | } | |
8971094d | 3972 | return NULL; |
910fdc79 DB |
3973 | } |
3974 | ||
3975 | ||
4cf4d6a3 DB |
3976 | /* Insert the varinfo FIELD into the field list for BASE, at the front |
3977 | of the list. */ | |
3978 | ||
3979 | static void | |
3980 | insert_into_field_list (varinfo_t base, varinfo_t field) | |
3981 | { | |
3982 | varinfo_t prev = base; | |
3983 | varinfo_t curr = base->next; | |
c58936b6 | 3984 | |
4cf4d6a3 DB |
3985 | field->next = curr; |
3986 | prev->next = field; | |
3987 | } | |
3988 | ||
910fdc79 DB |
3989 | /* Insert the varinfo FIELD into the field list for BASE, ordered by |
3990 | offset. */ | |
3991 | ||
3992 | static void | |
4cf4d6a3 | 3993 | insert_into_field_list_sorted (varinfo_t base, varinfo_t field) |
910fdc79 DB |
3994 | { |
3995 | varinfo_t prev = base; | |
3996 | varinfo_t curr = base->next; | |
c58936b6 | 3997 | |
910fdc79 DB |
3998 | if (curr == NULL) |
3999 | { | |
4000 | prev->next = field; | |
4001 | field->next = NULL; | |
4002 | } | |
4003 | else | |
4004 | { | |
4005 | while (curr) | |
4006 | { | |
4007 | if (field->offset <= curr->offset) | |
4008 | break; | |
4009 | prev = curr; | |
4010 | curr = curr->next; | |
4011 | } | |
4012 | field->next = prev->next; | |
4013 | prev->next = field; | |
4014 | } | |
4015 | } | |
4016 | ||
4017 | /* qsort comparison function for two fieldoff's PA and PB */ | |
4018 | ||
c58936b6 | 4019 | static int |
910fdc79 DB |
4020 | fieldoff_compare (const void *pa, const void *pb) |
4021 | { | |
4022 | const fieldoff_s *foa = (const fieldoff_s *)pa; | |
4023 | const fieldoff_s *fob = (const fieldoff_s *)pb; | |
4024 | HOST_WIDE_INT foasize, fobsize; | |
c58936b6 | 4025 | |
910fdc79 DB |
4026 | if (foa->offset != fob->offset) |
4027 | return foa->offset - fob->offset; | |
4028 | ||
35ed859b RG |
4029 | foasize = TREE_INT_CST_LOW (foa->size); |
4030 | fobsize = TREE_INT_CST_LOW (fob->size); | |
910fdc79 DB |
4031 | return foasize - fobsize; |
4032 | } | |
4033 | ||
4034 | /* Sort a fieldstack according to the field offset and sizes. */ | |
83f676b3 RS |
4035 | void |
4036 | sort_fieldstack (VEC(fieldoff_s,heap) *fieldstack) | |
910fdc79 | 4037 | { |
c58936b6 DB |
4038 | qsort (VEC_address (fieldoff_s, fieldstack), |
4039 | VEC_length (fieldoff_s, fieldstack), | |
910fdc79 DB |
4040 | sizeof (fieldoff_s), |
4041 | fieldoff_compare); | |
4042 | } | |
4043 | ||
d7705551 DN |
4044 | /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all |
4045 | the fields of TYPE onto fieldstack, recording their offsets along | |
4046 | the way. | |
4047 | ||
4048 | OFFSET is used to keep track of the offset in this entire | |
4049 | structure, rather than just the immediately containing structure. | |
4050 | Returns the number of fields pushed. | |
4051 | ||
910fdc79 | 4052 | HAS_UNION is set to true if we find a union type as a field of |
d7705551 DN |
4053 | TYPE. |
4054 | ||
4055 | ADDRESSABLE_TYPE is the type of the outermost object that could | |
99739a3e | 4056 | have its address taken. */ |
910fdc79 DB |
4057 | |
4058 | int | |
c58936b6 | 4059 | push_fields_onto_fieldstack (tree type, VEC(fieldoff_s,heap) **fieldstack, |
3d9b47dc | 4060 | HOST_WIDE_INT offset, bool *has_union, |
99739a3e | 4061 | tree addressable_type) |
910fdc79 DB |
4062 | { |
4063 | tree field; | |
4064 | int count = 0; | |
3fe2f42a RG |
4065 | unsigned int first_element = VEC_length (fieldoff_s, *fieldstack); |
4066 | ||
4067 | /* If the vector of fields is growing too big, bail out early. | |
4068 | Callers check for VEC_length <= MAX_FIELDS_FOR_FIELD_SENSITIVE, make | |
4069 | sure this fails. */ | |
4070 | if (first_element > MAX_FIELDS_FOR_FIELD_SENSITIVE) | |
4071 | return 0; | |
c58936b6 | 4072 | |
8ae5e6f2 AP |
4073 | if (TREE_CODE (type) == COMPLEX_TYPE) |
4074 | { | |
4075 | fieldoff_s *real_part, *img_part; | |
4076 | real_part = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL); | |
4077 | real_part->type = TREE_TYPE (type); | |
4078 | real_part->size = TYPE_SIZE (TREE_TYPE (type)); | |
4079 | real_part->offset = offset; | |
4080 | real_part->decl = NULL_TREE; | |
3d9b47dc | 4081 | real_part->alias_set = -1; |
99739a3e | 4082 | real_part->base_for_components = false; |
c58936b6 | 4083 | |
8ae5e6f2 AP |
4084 | img_part = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL); |
4085 | img_part->type = TREE_TYPE (type); | |
4086 | img_part->size = TYPE_SIZE (TREE_TYPE (type)); | |
4087 | img_part->offset = offset + TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (type))); | |
4088 | img_part->decl = NULL_TREE; | |
3d9b47dc | 4089 | img_part->alias_set = -1; |
99739a3e | 4090 | img_part->base_for_components = false; |
c58936b6 | 4091 | |
99739a3e | 4092 | count = 2; |
8ae5e6f2 | 4093 | } |
910fdc79 | 4094 | |
99739a3e | 4095 | else if (TREE_CODE (type) == ARRAY_TYPE) |
a916f21d RG |
4096 | { |
4097 | tree sz = TYPE_SIZE (type); | |
4098 | tree elsz = TYPE_SIZE (TREE_TYPE (type)); | |
4099 | HOST_WIDE_INT nr; | |
4100 | int i; | |
4101 | ||
4102 | if (! sz | |
4103 | || ! host_integerp (sz, 1) | |
4104 | || TREE_INT_CST_LOW (sz) == 0 | |
4105 | || ! elsz | |
4106 | || ! host_integerp (elsz, 1) | |
4107 | || TREE_INT_CST_LOW (elsz) == 0) | |
4108 | return 0; | |
4109 | ||
4110 | nr = TREE_INT_CST_LOW (sz) / TREE_INT_CST_LOW (elsz); | |
4111 | if (nr > SALIAS_MAX_ARRAY_ELEMENTS) | |
4112 | return 0; | |
4113 | ||
4114 | for (i = 0; i < nr; ++i) | |
4115 | { | |
4116 | bool push = false; | |
4117 | int pushed = 0; | |
c58936b6 DB |
4118 | |
4119 | if (has_union | |
a916f21d RG |
4120 | && (TREE_CODE (TREE_TYPE (type)) == QUAL_UNION_TYPE |
4121 | || TREE_CODE (TREE_TYPE (type)) == UNION_TYPE)) | |
4122 | *has_union = true; | |
c58936b6 | 4123 | |
a916f21d RG |
4124 | if (!AGGREGATE_TYPE_P (TREE_TYPE (type))) /* var_can_have_subvars */ |
4125 | push = true; | |
4126 | else if (!(pushed = push_fields_onto_fieldstack | |
d7705551 DN |
4127 | (TREE_TYPE (type), |
4128 | fieldstack, | |
4129 | offset + i * TREE_INT_CST_LOW (elsz), | |
4130 | has_union, | |
fa89b6ec EB |
4131 | (TYPE_NONALIASED_COMPONENT (type) |
4132 | ? addressable_type | |
99739a3e | 4133 | : TREE_TYPE (type))))) |
a916f21d RG |
4134 | /* Empty structures may have actual size, like in C++. So |
4135 | see if we didn't push any subfields and the size is | |
4136 | nonzero, push the field onto the stack */ | |
4137 | push = true; | |
4138 | ||
4139 | if (push) | |
4140 | { | |
4141 | fieldoff_s *pair; | |
4142 | ||
4143 | pair = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL); | |
4144 | pair->type = TREE_TYPE (type); | |
4145 | pair->size = elsz; | |
4146 | pair->decl = NULL_TREE; | |
4147 | pair->offset = offset + i * TREE_INT_CST_LOW (elsz); | |
fa89b6ec EB |
4148 | if (TYPE_NONALIASED_COMPONENT (type)) |
4149 | pair->alias_set = get_alias_set (addressable_type); | |
4150 | else | |
4151 | pair->alias_set = -1; | |
99739a3e | 4152 | pair->base_for_components = false; |
a916f21d RG |
4153 | count++; |
4154 | } | |
4155 | else | |
4156 | count += pushed; | |
4157 | } | |
a916f21d RG |
4158 | } |
4159 | ||
99739a3e RG |
4160 | else |
4161 | { | |
4162 | for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field)) | |
4163 | if (TREE_CODE (field) == FIELD_DECL) | |
910fdc79 | 4164 | { |
99739a3e RG |
4165 | bool push = false; |
4166 | int pushed = 0; | |
4167 | ||
4168 | if (has_union | |
4169 | && (TREE_CODE (TREE_TYPE (field)) == QUAL_UNION_TYPE | |
4170 | || TREE_CODE (TREE_TYPE (field)) == UNION_TYPE)) | |
4171 | *has_union = true; | |
4172 | ||
4173 | if (!var_can_have_subvars (field)) | |
4174 | push = true; | |
4175 | else if (!(pushed = push_fields_onto_fieldstack | |
4176 | (TREE_TYPE (field), | |
4177 | fieldstack, | |
4178 | offset + bitpos_of_field (field), | |
4179 | has_union, | |
4180 | (DECL_NONADDRESSABLE_P (field) | |
4181 | ? addressable_type | |
4182 | : TREE_TYPE (field)))) | |
4183 | && DECL_SIZE (field) | |
4184 | && !integer_zerop (DECL_SIZE (field))) | |
4185 | /* Empty structures may have actual size, like in C++. So | |
4186 | see if we didn't push any subfields and the size is | |
4187 | nonzero, push the field onto the stack */ | |
4188 | push = true; | |
4189 | ||
4190 | if (push) | |
4191 | { | |
4192 | fieldoff_s *pair; | |
4193 | ||
4194 | pair = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL); | |
4195 | pair->type = TREE_TYPE (field); | |
4196 | pair->size = DECL_SIZE (field); | |
4197 | pair->decl = field; | |
4198 | pair->offset = offset + bitpos_of_field (field); | |
4199 | if (DECL_NONADDRESSABLE_P (field)) | |
4200 | pair->alias_set = get_alias_set (addressable_type); | |
4201 | else | |
4202 | pair->alias_set = -1; | |
4203 | pair->base_for_components = false; | |
4204 | count++; | |
4205 | } | |
3d9b47dc | 4206 | else |
99739a3e RG |
4207 | count += pushed; |
4208 | } | |
4209 | } | |
4210 | ||
4211 | /* Make sure the first pushed field is marked as eligible for | |
4212 | being a base for component references. */ | |
4213 | if (count > 0) | |
4214 | VEC_index (fieldoff_s, *fieldstack, first_element)->base_for_components = true; | |
910fdc79 DB |
4215 | |
4216 | return count; | |
4217 | } | |
4218 | ||
c58936b6 | 4219 | /* Create a constraint from ANYTHING variable to VI. */ |
910fdc79 | 4220 | static void |
c58936b6 | 4221 | make_constraint_from_anything (varinfo_t vi) |
910fdc79 DB |
4222 | { |
4223 | struct constraint_expr lhs, rhs; | |
21392f19 | 4224 | |
c58936b6 | 4225 | lhs.var = vi->id; |
21392f19 DB |
4226 | lhs.offset = 0; |
4227 | lhs.type = SCALAR; | |
4228 | ||
c58936b6 DB |
4229 | rhs.var = anything_id; |
4230 | rhs.offset = 0; | |
3e5937d7 | 4231 | rhs.type = ADDRESSOF; |
910fdc79 DB |
4232 | process_constraint (new_constraint (lhs, rhs)); |
4233 | } | |
4234 | ||
4ee00913 DB |
4235 | /* Count the number of arguments DECL has, and set IS_VARARGS to true |
4236 | if it is a varargs function. */ | |
4237 | ||
4238 | static unsigned int | |
4239 | count_num_arguments (tree decl, bool *is_varargs) | |
4240 | { | |
4241 | unsigned int i = 0; | |
4242 | tree t; | |
4243 | ||
c58936b6 | 4244 | for (t = TYPE_ARG_TYPES (TREE_TYPE (decl)); |
4ee00913 DB |
4245 | t; |
4246 | t = TREE_CHAIN (t)) | |
c58936b6 | 4247 | { |
4ee00913 DB |
4248 | if (TREE_VALUE (t) == void_type_node) |
4249 | break; | |
4250 | i++; | |
4251 | } | |
c58936b6 | 4252 | |
4ee00913 DB |
4253 | if (!t) |
4254 | *is_varargs = true; | |
4255 | return i; | |
4256 | } | |
4257 | ||
4258 | /* Creation function node for DECL, using NAME, and return the index | |
4259 | of the variable we've created for the function. */ | |
4260 | ||
4261 | static unsigned int | |
4262 | create_function_info_for (tree decl, const char *name) | |
4263 | { | |
4264 | unsigned int index = VEC_length (varinfo_t, varmap); | |
4265 | varinfo_t vi; | |
c58936b6 | 4266 | tree arg; |
4ee00913 DB |
4267 | unsigned int i; |
4268 | bool is_varargs = false; | |
4269 | ||
4270 | /* Create the variable info. */ | |
4271 | ||
3e5937d7 | 4272 | vi = new_var_info (decl, index, name); |
4ee00913 DB |
4273 | vi->decl = decl; |
4274 | vi->offset = 0; | |
4275 | vi->has_union = 0; | |
4276 | vi->size = 1; | |
4277 | vi->fullsize = count_num_arguments (decl, &is_varargs) + 1; | |
3e5937d7 | 4278 | insert_vi_for_tree (vi->decl, vi); |
4ee00913 DB |
4279 | VEC_safe_push (varinfo_t, heap, varmap, vi); |
4280 | ||
4281 | stats.total_vars++; | |
4282 | ||
4283 | /* If it's varargs, we don't know how many arguments it has, so we | |
4284 | can't do much. | |
4285 | */ | |
4286 | if (is_varargs) | |
4287 | { | |
4288 | vi->fullsize = ~0; | |
4289 | vi->size = ~0; | |
4290 | vi->is_unknown_size_var = true; | |
4291 | return index; | |
4292 | } | |
4293 | ||
c58936b6 | 4294 | |
4ee00913 DB |
4295 | arg = DECL_ARGUMENTS (decl); |
4296 | ||
6416ae7f | 4297 | /* Set up variables for each argument. */ |
4ee00913 | 4298 | for (i = 1; i < vi->fullsize; i++) |
c58936b6 | 4299 | { |
4ee00913 DB |
4300 | varinfo_t argvi; |
4301 | const char *newname; | |
4302 | char *tempname; | |
4303 | unsigned int newindex; | |
4304 | tree argdecl = decl; | |
4305 | ||
4306 | if (arg) | |
4307 | argdecl = arg; | |
c58936b6 | 4308 | |
4ee00913 DB |
4309 | newindex = VEC_length (varinfo_t, varmap); |
4310 | asprintf (&tempname, "%s.arg%d", name, i-1); | |
4311 | newname = ggc_strdup (tempname); | |
4312 | free (tempname); | |
4313 | ||
3e5937d7 | 4314 | argvi = new_var_info (argdecl, newindex, newname); |
4ee00913 DB |
4315 | argvi->decl = argdecl; |
4316 | VEC_safe_push (varinfo_t, heap, varmap, argvi); | |
4317 | argvi->offset = i; | |
4318 | argvi->size = 1; | |
4319 | argvi->fullsize = vi->fullsize; | |
4320 | argvi->has_union = false; | |
4cf4d6a3 | 4321 | insert_into_field_list_sorted (vi, argvi); |
4ee00913 DB |
4322 | stats.total_vars ++; |
4323 | if (arg) | |
4324 | { | |
3e5937d7 | 4325 | insert_vi_for_tree (arg, argvi); |
4ee00913 DB |
4326 | arg = TREE_CHAIN (arg); |
4327 | } | |
4328 | } | |
4cf4d6a3 | 4329 | |
4ee00913 DB |
4330 | /* Create a variable for the return var. */ |
4331 | if (DECL_RESULT (decl) != NULL | |
4332 | || !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (decl)))) | |
4333 | { | |
4334 | varinfo_t resultvi; | |
4335 | const char *newname; | |
4336 | char *tempname; | |
4337 | unsigned int newindex; | |
4338 | tree resultdecl = decl; | |
4339 | ||
4340 | vi->fullsize ++; | |
4341 | ||
4ee00913 DB |
4342 | if (DECL_RESULT (decl)) |
4343 | resultdecl = DECL_RESULT (decl); | |
c58936b6 | 4344 | |
4ee00913 DB |
4345 | newindex = VEC_length (varinfo_t, varmap); |
4346 | asprintf (&tempname, "%s.result", name); | |
4347 | newname = ggc_strdup (tempname); | |
4348 | free (tempname); | |
4349 | ||
3e5937d7 | 4350 | resultvi = new_var_info (resultdecl, newindex, newname); |
4ee00913 DB |
4351 | resultvi->decl = resultdecl; |
4352 | VEC_safe_push (varinfo_t, heap, varmap, resultvi); | |
4353 | resultvi->offset = i; | |
4354 | resultvi->size = 1; | |
4355 | resultvi->fullsize = vi->fullsize; | |
4356 | resultvi->has_union = false; | |
4cf4d6a3 | 4357 | insert_into_field_list_sorted (vi, resultvi); |
4ee00913 DB |
4358 | stats.total_vars ++; |
4359 | if (DECL_RESULT (decl)) | |
3e5937d7 | 4360 | insert_vi_for_tree (DECL_RESULT (decl), resultvi); |
4ee00913 DB |
4361 | } |
4362 | return index; | |
c58936b6 | 4363 | } |
4ee00913 | 4364 | |
6c11790d | 4365 | |
c58936b6 | 4366 | /* Return true if FIELDSTACK contains fields that overlap. |
6c11790d DB |
4367 | FIELDSTACK is assumed to be sorted by offset. */ |
4368 | ||
4369 | static bool | |
4370 | check_for_overlaps (VEC (fieldoff_s,heap) *fieldstack) | |
4371 | { | |
4372 | fieldoff_s *fo = NULL; | |
4373 | unsigned int i; | |
30d2662c | 4374 | HOST_WIDE_INT lastoffset = -1; |
6c11790d DB |
4375 | |
4376 | for (i = 0; VEC_iterate (fieldoff_s, fieldstack, i, fo); i++) | |
4377 | { | |
4378 | if (fo->offset == lastoffset) | |
4379 | return true; | |
4380 | lastoffset = fo->offset; | |
4381 | } | |
4382 | return false; | |
4383 | } | |
21392f19 | 4384 | |
910fdc79 DB |
4385 | /* Create a varinfo structure for NAME and DECL, and add it to VARMAP. |
4386 | This will also create any varinfo structures necessary for fields | |
4387 | of DECL. */ | |
4388 | ||
4389 | static unsigned int | |
4390 | create_variable_info_for (tree decl, const char *name) | |
4391 | { | |
4392 | unsigned int index = VEC_length (varinfo_t, varmap); | |
4393 | varinfo_t vi; | |
4394 | tree decltype = TREE_TYPE (decl); | |
4ee00913 | 4395 | tree declsize = DECL_P (decl) ? DECL_SIZE (decl) : TYPE_SIZE (decltype); |
910fdc79 | 4396 | bool notokay = false; |
58b82d2b | 4397 | bool hasunion; |
910fdc79 | 4398 | bool is_global = DECL_P (decl) ? is_global_var (decl) : false; |
910fdc79 | 4399 | VEC (fieldoff_s,heap) *fieldstack = NULL; |
c58936b6 | 4400 | |
4ee00913 DB |
4401 | if (TREE_CODE (decl) == FUNCTION_DECL && in_ipa_mode) |
4402 | return create_function_info_for (decl, name); | |
58b82d2b | 4403 | |
e8ca4159 | 4404 | hasunion = TREE_CODE (decltype) == UNION_TYPE |
c58936b6 | 4405 | || TREE_CODE (decltype) == QUAL_UNION_TYPE; |
58b82d2b | 4406 | if (var_can_have_subvars (decl) && use_field_sensitive && !hasunion) |
910fdc79 | 4407 | { |
3d9b47dc | 4408 | push_fields_onto_fieldstack (decltype, &fieldstack, 0, &hasunion, |
99739a3e | 4409 | decltype); |
58b82d2b DB |
4410 | if (hasunion) |
4411 | { | |
4412 | VEC_free (fieldoff_s, heap, fieldstack); | |
4413 | notokay = true; | |
4ee00913 | 4414 | } |
910fdc79 | 4415 | } |
c58936b6 | 4416 | |
910fdc79 DB |
4417 | |
4418 | /* If the variable doesn't have subvars, we may end up needing to | |
4419 | sort the field list and create fake variables for all the | |
4420 | fields. */ | |
3e5937d7 | 4421 | vi = new_var_info (decl, index, name); |
910fdc79 DB |
4422 | vi->decl = decl; |
4423 | vi->offset = 0; | |
58b82d2b | 4424 | vi->has_union = hasunion; |
4ee00913 DB |
4425 | if (!declsize |
4426 | || TREE_CODE (declsize) != INTEGER_CST | |
910fdc79 DB |
4427 | || TREE_CODE (decltype) == UNION_TYPE |
4428 | || TREE_CODE (decltype) == QUAL_UNION_TYPE) | |
4429 | { | |
4430 | vi->is_unknown_size_var = true; | |
4431 | vi->fullsize = ~0; | |
4432 | vi->size = ~0; | |
4433 | } | |
4434 | else | |
4435 | { | |
4ee00913 | 4436 | vi->fullsize = TREE_INT_CST_LOW (declsize); |
910fdc79 DB |
4437 | vi->size = vi->fullsize; |
4438 | } | |
c58936b6 | 4439 | |
3e5937d7 | 4440 | insert_vi_for_tree (vi->decl, vi); |
b5efa470 | 4441 | VEC_safe_push (varinfo_t, heap, varmap, vi); |
4ee00913 | 4442 | if (is_global && (!flag_whole_program || !in_ipa_mode)) |
c58936b6 | 4443 | make_constraint_from_anything (vi); |
910fdc79 DB |
4444 | |
4445 | stats.total_vars++; | |
c58936b6 DB |
4446 | if (use_field_sensitive |
4447 | && !notokay | |
4448 | && !vi->is_unknown_size_var | |
98035a75 | 4449 | && var_can_have_subvars (decl) |
11948f6b | 4450 | && VEC_length (fieldoff_s, fieldstack) > 1 |
98035a75 | 4451 | && VEC_length (fieldoff_s, fieldstack) <= MAX_FIELDS_FOR_FIELD_SENSITIVE) |
910fdc79 DB |
4452 | { |
4453 | unsigned int newindex = VEC_length (varinfo_t, varmap); | |
4454 | fieldoff_s *fo = NULL; | |
4455 | unsigned int i; | |
910fdc79 DB |
4456 | |
4457 | for (i = 0; !notokay && VEC_iterate (fieldoff_s, fieldstack, i, fo); i++) | |
4458 | { | |
35ed859b RG |
4459 | if (! fo->size |
4460 | || TREE_CODE (fo->size) != INTEGER_CST | |
910fdc79 DB |
4461 | || fo->offset < 0) |
4462 | { | |
4463 | notokay = true; | |
4464 | break; | |
4465 | } | |
4466 | } | |
58b82d2b DB |
4467 | |
4468 | /* We can't sort them if we have a field with a variable sized type, | |
4469 | which will make notokay = true. In that case, we are going to return | |
4470 | without creating varinfos for the fields anyway, so sorting them is a | |
4471 | waste to boot. */ | |
6c11790d | 4472 | if (!notokay) |
c58936b6 | 4473 | { |
6c11790d DB |
4474 | sort_fieldstack (fieldstack); |
4475 | /* Due to some C++ FE issues, like PR 22488, we might end up | |
4476 | what appear to be overlapping fields even though they, | |
4477 | in reality, do not overlap. Until the C++ FE is fixed, | |
4478 | we will simply disable field-sensitivity for these cases. */ | |
4479 | notokay = check_for_overlaps (fieldstack); | |
4480 | } | |
c58936b6 DB |
4481 | |
4482 | ||
910fdc79 DB |
4483 | if (VEC_length (fieldoff_s, fieldstack) != 0) |
4484 | fo = VEC_index (fieldoff_s, fieldstack, 0); | |
4485 | ||
4486 | if (fo == NULL || notokay) | |
4487 | { | |
4488 | vi->is_unknown_size_var = 1; | |
4489 | vi->fullsize = ~0; | |
4490 | vi->size = ~0; | |
4491 | VEC_free (fieldoff_s, heap, fieldstack); | |
4492 | return index; | |
4493 | } | |
c58936b6 | 4494 | |
35ed859b | 4495 | vi->size = TREE_INT_CST_LOW (fo->size); |
046a69e0 | 4496 | vi->offset = fo->offset; |
c58936b6 DB |
4497 | for (i = VEC_length (fieldoff_s, fieldstack) - 1; |
4498 | i >= 1 && VEC_iterate (fieldoff_s, fieldstack, i, fo); | |
4cf4d6a3 | 4499 | i--) |
910fdc79 DB |
4500 | { |
4501 | varinfo_t newvi; | |
4f6c9110 | 4502 | const char *newname = "NULL"; |
910fdc79 DB |
4503 | char *tempname; |
4504 | ||
910fdc79 | 4505 | newindex = VEC_length (varinfo_t, varmap); |
4f6c9110 RG |
4506 | if (dump_file) |
4507 | { | |
4508 | if (fo->decl) | |
c58936b6 | 4509 | asprintf (&tempname, "%s.%s", |
4f6c9110 RG |
4510 | vi->name, alias_get_name (fo->decl)); |
4511 | else | |
c58936b6 | 4512 | asprintf (&tempname, "%s." HOST_WIDE_INT_PRINT_DEC, |
4f6c9110 RG |
4513 | vi->name, fo->offset); |
4514 | newname = ggc_strdup (tempname); | |
4515 | free (tempname); | |
4516 | } | |
3e5937d7 | 4517 | newvi = new_var_info (decl, newindex, newname); |
910fdc79 | 4518 | newvi->offset = fo->offset; |
35ed859b | 4519 | newvi->size = TREE_INT_CST_LOW (fo->size); |
910fdc79 DB |
4520 | newvi->fullsize = vi->fullsize; |
4521 | insert_into_field_list (vi, newvi); | |
b5efa470 | 4522 | VEC_safe_push (varinfo_t, heap, varmap, newvi); |
4ee00913 | 4523 | if (is_global && (!flag_whole_program || !in_ipa_mode)) |
c58936b6 DB |
4524 | make_constraint_from_anything (newvi); |
4525 | ||
4ee00913 | 4526 | stats.total_vars++; |
910fdc79 | 4527 | } |
910fdc79 | 4528 | } |
efe9e829 RG |
4529 | |
4530 | VEC_free (fieldoff_s, heap, fieldstack); | |
4531 | ||
910fdc79 DB |
4532 | return index; |
4533 | } | |
4534 | ||
4535 | /* Print out the points-to solution for VAR to FILE. */ | |
4536 | ||
4537 | void | |
4538 | dump_solution_for_var (FILE *file, unsigned int var) | |
4539 | { | |
4540 | varinfo_t vi = get_varinfo (var); | |
4541 | unsigned int i; | |
c58936b6 DB |
4542 | bitmap_iterator bi; |
4543 | ||
3e5937d7 | 4544 | if (find (var) != var) |
910fdc79 | 4545 | { |
3e5937d7 | 4546 | varinfo_t vipt = get_varinfo (find (var)); |
c58936b6 DB |
4547 | fprintf (file, "%s = same as %s\n", vi->name, vipt->name); |
4548 | } | |
4549 | else | |
4550 | { | |
4551 | fprintf (file, "%s = { ", vi->name); | |
3e5937d7 | 4552 | EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi) |
c58936b6 DB |
4553 | { |
4554 | fprintf (file, "%s ", get_varinfo (i)->name); | |
4555 | } | |
058dcc25 ILT |
4556 | fprintf (file, "}"); |
4557 | if (vi->no_tbaa_pruning) | |
4558 | fprintf (file, " no-tbaa-pruning"); | |
4559 | fprintf (file, "\n"); | |
910fdc79 | 4560 | } |
910fdc79 DB |
4561 | } |
4562 | ||
4563 | /* Print the points-to solution for VAR to stdout. */ | |
4564 | ||
4565 | void | |
4566 | debug_solution_for_var (unsigned int var) | |
4567 | { | |
4568 | dump_solution_for_var (stdout, var); | |
4569 | } | |
4570 | ||
910fdc79 DB |
4571 | /* Create varinfo structures for all of the variables in the |
4572 | function for intraprocedural mode. */ | |
4573 | ||
4574 | static void | |
4575 | intra_create_variable_infos (void) | |
4576 | { | |
4577 | tree t; | |
21392f19 | 4578 | struct constraint_expr lhs, rhs; |
b23987ec | 4579 | |
6e7e772d DN |
4580 | /* For each incoming pointer argument arg, create the constraint ARG |
4581 | = ANYTHING or a dummy variable if flag_argument_noalias is set. */ | |
910fdc79 DB |
4582 | for (t = DECL_ARGUMENTS (current_function_decl); t; t = TREE_CHAIN (t)) |
4583 | { | |
910fdc79 | 4584 | varinfo_t p; |
c58936b6 | 4585 | |
21392f19 DB |
4586 | if (!could_have_pointers (t)) |
4587 | continue; | |
c58936b6 | 4588 | |
e9e0aa2c DN |
4589 | /* If flag_argument_noalias is set, then function pointer |
4590 | arguments are guaranteed not to point to each other. In that | |
4591 | case, create an artificial variable PARM_NOALIAS and the | |
4592 | constraint ARG = &PARM_NOALIAS. */ | |
4593 | if (POINTER_TYPE_P (TREE_TYPE (t)) && flag_argument_noalias > 0) | |
7cc92f92 RG |
4594 | { |
4595 | varinfo_t vi; | |
7cc92f92 | 4596 | tree heapvar = heapvar_lookup (t); |
c58936b6 | 4597 | |
21392f19 DB |
4598 | lhs.offset = 0; |
4599 | lhs.type = SCALAR; | |
3e5937d7 | 4600 | lhs.var = get_vi_for_tree (t)->id; |
c58936b6 | 4601 | |
7cc92f92 RG |
4602 | if (heapvar == NULL_TREE) |
4603 | { | |
e9e0aa2c | 4604 | var_ann_t ann; |
c58936b6 | 4605 | heapvar = create_tmp_var_raw (TREE_TYPE (TREE_TYPE (t)), |
4cf4d6a3 | 4606 | "PARM_NOALIAS"); |
7cc92f92 | 4607 | DECL_EXTERNAL (heapvar) = 1; |
5cd4ec7f | 4608 | if (gimple_referenced_vars (cfun)) |
f004ab02 | 4609 | add_referenced_var (heapvar); |
e9e0aa2c | 4610 | |
7cc92f92 | 4611 | heapvar_insert (t, heapvar); |
e9e0aa2c DN |
4612 | |
4613 | ann = get_var_ann (heapvar); | |
4614 | if (flag_argument_noalias == 1) | |
4615 | ann->noalias_state = NO_ALIAS; | |
4616 | else if (flag_argument_noalias == 2) | |
4617 | ann->noalias_state = NO_ALIAS_GLOBAL; | |
4618 | else if (flag_argument_noalias == 3) | |
4619 | ann->noalias_state = NO_ALIAS_ANYTHING; | |
4620 | else | |
4621 | gcc_unreachable (); | |
7cc92f92 | 4622 | } |
e9e0aa2c | 4623 | |
3e5937d7 | 4624 | vi = get_vi_for_tree (heapvar); |
7cc92f92 RG |
4625 | vi->is_artificial_var = 1; |
4626 | vi->is_heap_var = 1; | |
3e5937d7 DB |
4627 | rhs.var = vi->id; |
4628 | rhs.type = ADDRESSOF; | |
7cc92f92 | 4629 | rhs.offset = 0; |
c58936b6 | 4630 | for (p = get_varinfo (lhs.var); p; p = p->next) |
7cc92f92 RG |
4631 | { |
4632 | struct constraint_expr temp = lhs; | |
4633 | temp.var = p->id; | |
4634 | process_constraint (new_constraint (temp, rhs)); | |
4635 | } | |
4636 | } | |
c58936b6 | 4637 | else |
21392f19 | 4638 | { |
3e5937d7 DB |
4639 | varinfo_t arg_vi = get_vi_for_tree (t); |
4640 | ||
4641 | for (p = arg_vi; p; p = p->next) | |
c58936b6 | 4642 | make_constraint_from_anything (p); |
21392f19 DB |
4643 | } |
4644 | } | |
910fdc79 DB |
4645 | } |
4646 | ||
1296c31f DB |
4647 | /* Structure used to put solution bitmaps in a hashtable so they can |
4648 | be shared among variables with the same points-to set. */ | |
4649 | ||
4650 | typedef struct shared_bitmap_info | |
4651 | { | |
4652 | bitmap pt_vars; | |
4653 | hashval_t hashcode; | |
4654 | } *shared_bitmap_info_t; | |
e5cfc29f | 4655 | typedef const struct shared_bitmap_info *const_shared_bitmap_info_t; |
1296c31f DB |
4656 | |
4657 | static htab_t shared_bitmap_table; | |
4658 | ||
4659 | /* Hash function for a shared_bitmap_info_t */ | |
4660 | ||
4661 | static hashval_t | |
4662 | shared_bitmap_hash (const void *p) | |
4663 | { | |
e5cfc29f | 4664 | const_shared_bitmap_info_t const bi = (const_shared_bitmap_info_t) p; |
1296c31f DB |
4665 | return bi->hashcode; |
4666 | } | |
4667 | ||
4668 | /* Equality function for two shared_bitmap_info_t's. */ | |
4669 | ||
4670 | static int | |
4671 | shared_bitmap_eq (const void *p1, const void *p2) | |
4672 | { | |
e5cfc29f KG |
4673 | const_shared_bitmap_info_t const sbi1 = (const_shared_bitmap_info_t) p1; |
4674 | const_shared_bitmap_info_t const sbi2 = (const_shared_bitmap_info_t) p2; | |
1296c31f DB |
4675 | return bitmap_equal_p (sbi1->pt_vars, sbi2->pt_vars); |
4676 | } | |
4677 | ||
4678 | /* Lookup a bitmap in the shared bitmap hashtable, and return an already | |
4679 | existing instance if there is one, NULL otherwise. */ | |
4680 | ||
4681 | static bitmap | |
4682 | shared_bitmap_lookup (bitmap pt_vars) | |
4683 | { | |
4684 | void **slot; | |
4685 | struct shared_bitmap_info sbi; | |
4686 | ||
4687 | sbi.pt_vars = pt_vars; | |
4688 | sbi.hashcode = bitmap_hash (pt_vars); | |
7b765bed | 4689 | |
1296c31f DB |
4690 | slot = htab_find_slot_with_hash (shared_bitmap_table, &sbi, |
4691 | sbi.hashcode, NO_INSERT); | |
4692 | if (!slot) | |
4693 | return NULL; | |
4694 | else | |
4695 | return ((shared_bitmap_info_t) *slot)->pt_vars; | |
4696 | } | |
4697 | ||
4698 | ||
4699 | /* Add a bitmap to the shared bitmap hashtable. */ | |
4700 | ||
4701 | static void | |
4702 | shared_bitmap_add (bitmap pt_vars) | |
4703 | { | |
4704 | void **slot; | |
4705 | shared_bitmap_info_t sbi = XNEW (struct shared_bitmap_info); | |
7b765bed | 4706 | |
1296c31f DB |
4707 | sbi->pt_vars = pt_vars; |
4708 | sbi->hashcode = bitmap_hash (pt_vars); | |
7b765bed | 4709 | |
1296c31f DB |
4710 | slot = htab_find_slot_with_hash (shared_bitmap_table, sbi, |
4711 | sbi->hashcode, INSERT); | |
4712 | gcc_assert (!*slot); | |
4713 | *slot = (void *) sbi; | |
4714 | } | |
4715 | ||
4716 | ||
910fdc79 | 4717 | /* Set bits in INTO corresponding to the variable uids in solution set |
21392f19 DB |
4718 | FROM, which came from variable PTR. |
4719 | For variables that are actually dereferenced, we also use type | |
6bdff197 DB |
4720 | based alias analysis to prune the points-to sets. |
4721 | IS_DEREFED is true if PTR was directly dereferenced, which we use to | |
058dcc25 ILT |
4722 | help determine whether we are we are allowed to prune using TBAA. |
4723 | If NO_TBAA_PRUNING is true, we do not perform any TBAA pruning of | |
4724 | the from set. */ | |
910fdc79 DB |
4725 | |
4726 | static void | |
058dcc25 ILT |
4727 | set_uids_in_ptset (tree ptr, bitmap into, bitmap from, bool is_derefed, |
4728 | bool no_tbaa_pruning) | |
910fdc79 DB |
4729 | { |
4730 | unsigned int i; | |
4731 | bitmap_iterator bi; | |
f83ca251 RG |
4732 | alias_set_type ptr_alias_set; |
4733 | ||
4734 | gcc_assert (POINTER_TYPE_P (TREE_TYPE (ptr))); | |
4735 | ptr_alias_set = get_alias_set (TREE_TYPE (TREE_TYPE (ptr))); | |
910fdc79 DB |
4736 | |
4737 | EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi) | |
4738 | { | |
4739 | varinfo_t vi = get_varinfo (i); | |
4862826d | 4740 | alias_set_type var_alias_set; |
c58936b6 | 4741 | |
e8ca4159 DN |
4742 | /* The only artificial variables that are allowed in a may-alias |
4743 | set are heap variables. */ | |
4744 | if (vi->is_artificial_var && !vi->is_heap_var) | |
4745 | continue; | |
c58936b6 | 4746 | |
58b82d2b DB |
4747 | if (vi->has_union && get_subvars_for_var (vi->decl) != NULL) |
4748 | { | |
eee717aa RG |
4749 | unsigned int i; |
4750 | tree subvar; | |
4751 | subvar_t sv = get_subvars_for_var (vi->decl); | |
4752 | ||
e8ca4159 DN |
4753 | /* Variables containing unions may need to be converted to |
4754 | their SFT's, because SFT's can have unions and we cannot. */ | |
eee717aa RG |
4755 | for (i = 0; VEC_iterate (tree, sv, i, subvar); ++i) |
4756 | bitmap_set_bit (into, DECL_UID (subvar)); | |
58b82d2b | 4757 | } |
c58936b6 | 4758 | else if (TREE_CODE (vi->decl) == VAR_DECL |
fda2b8e3 JJ |
4759 | || TREE_CODE (vi->decl) == PARM_DECL |
4760 | || TREE_CODE (vi->decl) == RESULT_DECL) | |
e8ca4159 | 4761 | { |
4a648c5d | 4762 | subvar_t sv; |
4ee00913 | 4763 | if (var_can_have_subvars (vi->decl) |
4a648c5d | 4764 | && (sv = get_subvars_for_var (vi->decl))) |
e8ca4159 DN |
4765 | { |
4766 | /* If VI->DECL is an aggregate for which we created | |
4a648c5d RG |
4767 | SFTs, add the SFT corresponding to VI->OFFSET. |
4768 | If we didn't do field-sensitive PTA we need to to | |
4769 | add all overlapping SFTs. */ | |
4770 | unsigned int j; | |
4771 | tree sft = get_first_overlapping_subvar (sv, vi->offset, | |
4772 | vi->size, &j); | |
7b765bed | 4773 | gcc_assert (sft); |
4a648c5d | 4774 | for (; VEC_iterate (tree, sv, j, sft); ++j) |
21392f19 | 4775 | { |
4a648c5d RG |
4776 | if (SFT_OFFSET (sft) > vi->offset |
4777 | && vi->size <= SFT_OFFSET (sft) - vi->offset) | |
4778 | break; | |
4779 | ||
21392f19 | 4780 | var_alias_set = get_alias_set (sft); |
058dcc25 ILT |
4781 | if (no_tbaa_pruning |
4782 | || (!is_derefed && !vi->directly_dereferenced) | |
21392f19 | 4783 | || alias_sets_conflict_p (ptr_alias_set, var_alias_set)) |
d7705551 DN |
4784 | { |
4785 | bitmap_set_bit (into, DECL_UID (sft)); | |
4786 | ||
99739a3e RG |
4787 | /* Pointed-to SFTs are needed by the operand scanner |
4788 | to adjust offsets when adding operands to memory | |
d7705551 DN |
4789 | expressions that dereference PTR. This means |
4790 | that memory partitioning may not partition | |
4791 | this SFT because the operand scanner will not | |
4792 | be able to find the other SFTs next to this | |
99739a3e RG |
4793 | one. But we only need to do this if the pointed |
4794 | to type is aggregate. */ | |
4795 | if (SFT_BASE_FOR_COMPONENTS_P (sft)) | |
d7705551 DN |
4796 | SFT_UNPARTITIONABLE_P (sft) = true; |
4797 | } | |
21392f19 | 4798 | } |
e8ca4159 DN |
4799 | } |
4800 | else | |
4801 | { | |
21392f19 DB |
4802 | /* Otherwise, just add VI->DECL to the alias set. |
4803 | Don't type prune artificial vars. */ | |
4804 | if (vi->is_artificial_var) | |
4805 | bitmap_set_bit (into, DECL_UID (vi->decl)); | |
4806 | else | |
4807 | { | |
4808 | var_alias_set = get_alias_set (vi->decl); | |
058dcc25 ILT |
4809 | if (no_tbaa_pruning |
4810 | || (!is_derefed && !vi->directly_dereferenced) | |
21392f19 DB |
4811 | || alias_sets_conflict_p (ptr_alias_set, var_alias_set)) |
4812 | bitmap_set_bit (into, DECL_UID (vi->decl)); | |
4813 | } | |
e8ca4159 DN |
4814 | } |
4815 | } | |
910fdc79 DB |
4816 | } |
4817 | } | |
e8ca4159 DN |
4818 | |
4819 | ||
4820 | static bool have_alias_info = false; | |
910fdc79 | 4821 | |
c58936b6 DB |
4822 | /* The list of SMT's that are in use by our pointer variables. This |
4823 | is the set of SMT's for all pointers that can point to anything. */ | |
4824 | static bitmap used_smts; | |
4825 | ||
4826 | /* Due to the ordering of points-to set calculation and SMT | |
4827 | calculation being a bit co-dependent, we can't just calculate SMT | |
4828 | used info whenever we want, we have to calculate it around the time | |
4829 | that find_what_p_points_to is called. */ | |
c58936b6 DB |
4830 | |
4831 | /* Mark which SMT's are in use by points-to anything variables. */ | |
4832 | ||
e5ebbea5 | 4833 | void |
c58936b6 DB |
4834 | set_used_smts (void) |
4835 | { | |
4836 | int i; | |
4837 | varinfo_t vi; | |
3e5937d7 | 4838 | used_smts = BITMAP_ALLOC (&pta_obstack); |
c58936b6 DB |
4839 | |
4840 | for (i = 0; VEC_iterate (varinfo_t, varmap, i, vi); i++) | |
4841 | { | |
4842 | tree var = vi->decl; | |
7b765bed | 4843 | varinfo_t withsolution = get_varinfo (find (i)); |
c58936b6 | 4844 | tree smt; |
c58936b6 DB |
4845 | var_ann_t va; |
4846 | struct ptr_info_def *pi = NULL; | |
3e5937d7 | 4847 | |
ff3add8d DB |
4848 | /* For parm decls, the pointer info may be under the default |
4849 | def. */ | |
4850 | if (TREE_CODE (vi->decl) == PARM_DECL | |
4851 | && gimple_default_def (cfun, var)) | |
4852 | pi = SSA_NAME_PTR_INFO (gimple_default_def (cfun, var)); | |
4853 | else if (TREE_CODE (var) == SSA_NAME) | |
c58936b6 DB |
4854 | pi = SSA_NAME_PTR_INFO (var); |
4855 | ||
7b765bed DB |
4856 | /* Skip the special variables and those that can't be aliased. */ |
4857 | if (vi->is_special_var | |
3e5937d7 DB |
4858 | || !SSA_VAR_P (var) |
4859 | || (pi && !pi->is_dereferenced) | |
ff3add8d DB |
4860 | || (TREE_CODE (var) == VAR_DECL && !may_be_aliased (var)) |
4861 | || !POINTER_TYPE_P (TREE_TYPE (var))) | |
c58936b6 DB |
4862 | continue; |
4863 | ||
4864 | if (TREE_CODE (var) == SSA_NAME) | |
4865 | var = SSA_NAME_VAR (var); | |
4866 | ||
4867 | va = var_ann (var); | |
4868 | if (!va) | |
4869 | continue; | |
4870 | ||
4871 | smt = va->symbol_mem_tag; | |
7b765bed | 4872 | if (smt && bitmap_bit_p (withsolution->solution, anything_id)) |
ff3add8d | 4873 | bitmap_set_bit (used_smts, DECL_UID (smt)); |
c58936b6 | 4874 | } |
c58936b6 DB |
4875 | } |
4876 | ||
1296c31f | 4877 | /* Merge the necessary SMT's into the bitmap INTO, which is |
c58936b6 DB |
4878 | P's varinfo. This involves merging all SMT's that are a subset of |
4879 | the SMT necessary for P. */ | |
4880 | ||
4881 | static void | |
1296c31f | 4882 | merge_smts_into (tree p, bitmap solution) |
c58936b6 | 4883 | { |
3b302421 RG |
4884 | unsigned int i; |
4885 | bitmap_iterator bi; | |
c58936b6 | 4886 | tree smt; |
306219a2 | 4887 | bitmap aliases; |
c58936b6 DB |
4888 | tree var = p; |
4889 | ||
4890 | if (TREE_CODE (p) == SSA_NAME) | |
4891 | var = SSA_NAME_VAR (p); | |
4892 | ||
4893 | smt = var_ann (var)->symbol_mem_tag; | |
4894 | if (smt) | |
4895 | { | |
4862826d | 4896 | alias_set_type smtset = get_alias_set (TREE_TYPE (smt)); |
c58936b6 DB |
4897 | |
4898 | /* Need to set the SMT subsets first before this | |
4899 | will work properly. */ | |
1296c31f | 4900 | bitmap_set_bit (solution, DECL_UID (smt)); |
3b302421 | 4901 | EXECUTE_IF_SET_IN_BITMAP (used_smts, 0, i, bi) |
c58936b6 | 4902 | { |
3b302421 | 4903 | tree newsmt = referenced_var (i); |
c58936b6 DB |
4904 | tree newsmttype = TREE_TYPE (newsmt); |
4905 | ||
4906 | if (alias_set_subset_of (get_alias_set (newsmttype), | |
4907 | smtset)) | |
3b302421 | 4908 | bitmap_set_bit (solution, i); |
c58936b6 DB |
4909 | } |
4910 | ||
306219a2 | 4911 | aliases = MTAG_ALIASES (smt); |
c58936b6 | 4912 | if (aliases) |
7b765bed | 4913 | bitmap_ior_into (solution, aliases); |
c58936b6 DB |
4914 | } |
4915 | } | |
4916 | ||
910fdc79 | 4917 | /* Given a pointer variable P, fill in its points-to set, or return |
3e5937d7 | 4918 | false if we can't. |
c58936b6 | 4919 | Rather than return false for variables that point-to anything, we |
7b765bed | 4920 | instead find the corresponding SMT, and merge in its aliases. In |
c58936b6 DB |
4921 | addition to these aliases, we also set the bits for the SMT's |
4922 | themselves and their subsets, as SMT's are still in use by | |
4923 | non-SSA_NAME's, and pruning may eliminate every one of their | |
4924 | aliases. In such a case, if we did not include the right set of | |
4925 | SMT's in the points-to set of the variable, we'd end up with | |
4926 | statements that do not conflict but should. */ | |
910fdc79 DB |
4927 | |
4928 | bool | |
4929 | find_what_p_points_to (tree p) | |
4930 | { | |
7cc92f92 | 4931 | tree lookup_p = p; |
3e5937d7 | 4932 | varinfo_t vi; |
e8ca4159 | 4933 | |
910fdc79 DB |
4934 | if (!have_alias_info) |
4935 | return false; | |
e8ca4159 | 4936 | |
7cc92f92 RG |
4937 | /* For parameters, get at the points-to set for the actual parm |
4938 | decl. */ | |
c58936b6 DB |
4939 | if (TREE_CODE (p) == SSA_NAME |
4940 | && TREE_CODE (SSA_NAME_VAR (p)) == PARM_DECL | |
38635499 | 4941 | && SSA_NAME_IS_DEFAULT_DEF (p)) |
7cc92f92 RG |
4942 | lookup_p = SSA_NAME_VAR (p); |
4943 | ||
15814ba0 PB |
4944 | vi = lookup_vi_for_tree (lookup_p); |
4945 | if (vi) | |
910fdc79 | 4946 | { |
910fdc79 DB |
4947 | if (vi->is_artificial_var) |
4948 | return false; | |
4949 | ||
e8ca4159 | 4950 | /* See if this is a field or a structure. */ |
910fdc79 DB |
4951 | if (vi->size != vi->fullsize) |
4952 | { | |
e8ca4159 DN |
4953 | /* Nothing currently asks about structure fields directly, |
4954 | but when they do, we need code here to hand back the | |
4955 | points-to set. */ | |
910fdc79 DB |
4956 | if (!var_can_have_subvars (vi->decl) |
4957 | || get_subvars_for_var (vi->decl) == NULL) | |
4958 | return false; | |
c58936b6 | 4959 | } |
910fdc79 DB |
4960 | else |
4961 | { | |
4962 | struct ptr_info_def *pi = get_ptr_info (p); | |
4963 | unsigned int i; | |
4964 | bitmap_iterator bi; | |
c58936b6 | 4965 | bool was_pt_anything = false; |
1296c31f DB |
4966 | bitmap finished_solution; |
4967 | bitmap result; | |
7b765bed | 4968 | |
c58936b6 DB |
4969 | if (!pi->is_dereferenced) |
4970 | return false; | |
910fdc79 DB |
4971 | |
4972 | /* This variable may have been collapsed, let's get the real | |
4973 | variable. */ | |
3e5937d7 | 4974 | vi = get_varinfo (find (vi->id)); |
c58936b6 | 4975 | |
e8ca4159 DN |
4976 | /* Translate artificial variables into SSA_NAME_PTR_INFO |
4977 | attributes. */ | |
910fdc79 DB |
4978 | EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi) |
4979 | { | |
e8ca4159 DN |
4980 | varinfo_t vi = get_varinfo (i); |
4981 | ||
4982 | if (vi->is_artificial_var) | |
4983 | { | |
4984 | /* FIXME. READONLY should be handled better so that | |
a4174ebf | 4985 | flow insensitive aliasing can disregard writable |
e8ca4159 DN |
4986 | aliases. */ |
4987 | if (vi->id == nothing_id) | |
4988 | pi->pt_null = 1; | |
4989 | else if (vi->id == anything_id) | |
c58936b6 | 4990 | was_pt_anything = 1; |
e8ca4159 | 4991 | else if (vi->id == readonly_id) |
c58936b6 | 4992 | was_pt_anything = 1; |
e8ca4159 | 4993 | else if (vi->id == integer_id) |
c58936b6 | 4994 | was_pt_anything = 1; |
e8ca4159 DN |
4995 | else if (vi->is_heap_var) |
4996 | pi->pt_global_mem = 1; | |
4997 | } | |
910fdc79 | 4998 | } |
e8ca4159 | 4999 | |
1296c31f | 5000 | /* Share the final set of variables when possible. */ |
1296c31f DB |
5001 | finished_solution = BITMAP_GGC_ALLOC (); |
5002 | stats.points_to_sets_created++; | |
7b765bed | 5003 | |
73fd4ad6 EB |
5004 | /* Instead of using pt_anything, we merge in the SMT aliases |
5005 | for the underlying SMT. In addition, if they could have | |
5006 | pointed to anything, they could point to global memory. | |
5007 | But we cannot do that for ref-all pointers because these | |
5008 | aliases have not been computed yet. */ | |
1296c31f | 5009 | if (was_pt_anything) |
c58936b6 | 5010 | { |
73fd4ad6 EB |
5011 | if (PTR_IS_REF_ALL (p)) |
5012 | { | |
5013 | pi->pt_anything = 1; | |
5014 | return false; | |
5015 | } | |
5016 | ||
1296c31f DB |
5017 | merge_smts_into (p, finished_solution); |
5018 | pi->pt_global_mem = 1; | |
5019 | } | |
7b765bed | 5020 | |
f83ca251 | 5021 | set_uids_in_ptset (p, finished_solution, vi->solution, |
058dcc25 ILT |
5022 | vi->directly_dereferenced, |
5023 | vi->no_tbaa_pruning); | |
1296c31f DB |
5024 | result = shared_bitmap_lookup (finished_solution); |
5025 | ||
5026 | if (!result) | |
5027 | { | |
5028 | shared_bitmap_add (finished_solution); | |
5029 | pi->pt_vars = finished_solution; | |
c58936b6 DB |
5030 | } |
5031 | else | |
5032 | { | |
1296c31f DB |
5033 | pi->pt_vars = result; |
5034 | bitmap_clear (finished_solution); | |
c58936b6 | 5035 | } |
e8ca4159 DN |
5036 | |
5037 | if (bitmap_empty_p (pi->pt_vars)) | |
5038 | pi->pt_vars = NULL; | |
5039 | ||
910fdc79 DB |
5040 | return true; |
5041 | } | |
5042 | } | |
e8ca4159 | 5043 | |
910fdc79 DB |
5044 | return false; |
5045 | } | |
5046 | ||
63a4ef6f | 5047 | |
910fdc79 | 5048 | |
63a4ef6f DN |
5049 | /* Dump points-to information to OUTFILE. */ |
5050 | ||
5051 | void | |
910fdc79 DB |
5052 | dump_sa_points_to_info (FILE *outfile) |
5053 | { | |
910fdc79 | 5054 | unsigned int i; |
63a4ef6f | 5055 | |
e8ca4159 | 5056 | fprintf (outfile, "\nPoints-to sets\n\n"); |
63a4ef6f | 5057 | |
910fdc79 DB |
5058 | if (dump_flags & TDF_STATS) |
5059 | { | |
5060 | fprintf (outfile, "Stats:\n"); | |
63a4ef6f | 5061 | fprintf (outfile, "Total vars: %d\n", stats.total_vars); |
3e5937d7 DB |
5062 | fprintf (outfile, "Non-pointer vars: %d\n", |
5063 | stats.nonpointer_vars); | |
63a4ef6f DN |
5064 | fprintf (outfile, "Statically unified vars: %d\n", |
5065 | stats.unified_vars_static); | |
63a4ef6f DN |
5066 | fprintf (outfile, "Dynamically unified vars: %d\n", |
5067 | stats.unified_vars_dynamic); | |
5068 | fprintf (outfile, "Iterations: %d\n", stats.iterations); | |
4ee00913 | 5069 | fprintf (outfile, "Number of edges: %d\n", stats.num_edges); |
3e5937d7 DB |
5070 | fprintf (outfile, "Number of implicit edges: %d\n", |
5071 | stats.num_implicit_edges); | |
910fdc79 | 5072 | } |
63a4ef6f | 5073 | |
910fdc79 DB |
5074 | for (i = 0; i < VEC_length (varinfo_t, varmap); i++) |
5075 | dump_solution_for_var (outfile, i); | |
5076 | } | |
5077 | ||
5078 | ||
63a4ef6f DN |
5079 | /* Debug points-to information to stderr. */ |
5080 | ||
5081 | void | |
5082 | debug_sa_points_to_info (void) | |
5083 | { | |
5084 | dump_sa_points_to_info (stderr); | |
5085 | } | |
5086 | ||
5087 | ||
910fdc79 DB |
5088 | /* Initialize the always-existing constraint variables for NULL |
5089 | ANYTHING, READONLY, and INTEGER */ | |
5090 | ||
5091 | static void | |
5092 | init_base_vars (void) | |
5093 | { | |
5094 | struct constraint_expr lhs, rhs; | |
5095 | ||
5096 | /* Create the NULL variable, used to represent that a variable points | |
5097 | to NULL. */ | |
5098 | nothing_tree = create_tmp_var_raw (void_type_node, "NULL"); | |
3e5937d7 DB |
5099 | var_nothing = new_var_info (nothing_tree, 0, "NULL"); |
5100 | insert_vi_for_tree (nothing_tree, var_nothing); | |
910fdc79 DB |
5101 | var_nothing->is_artificial_var = 1; |
5102 | var_nothing->offset = 0; | |
5103 | var_nothing->size = ~0; | |
5104 | var_nothing->fullsize = ~0; | |
13c2c08b | 5105 | var_nothing->is_special_var = 1; |
910fdc79 | 5106 | nothing_id = 0; |
b5efa470 | 5107 | VEC_safe_push (varinfo_t, heap, varmap, var_nothing); |
910fdc79 DB |
5108 | |
5109 | /* Create the ANYTHING variable, used to represent that a variable | |
5110 | points to some unknown piece of memory. */ | |
5111 | anything_tree = create_tmp_var_raw (void_type_node, "ANYTHING"); | |
3e5937d7 DB |
5112 | var_anything = new_var_info (anything_tree, 1, "ANYTHING"); |
5113 | insert_vi_for_tree (anything_tree, var_anything); | |
910fdc79 DB |
5114 | var_anything->is_artificial_var = 1; |
5115 | var_anything->size = ~0; | |
5116 | var_anything->offset = 0; | |
5117 | var_anything->next = NULL; | |
5118 | var_anything->fullsize = ~0; | |
13c2c08b | 5119 | var_anything->is_special_var = 1; |
910fdc79 DB |
5120 | anything_id = 1; |
5121 | ||
5122 | /* Anything points to anything. This makes deref constraints just | |
c58936b6 | 5123 | work in the presence of linked list and other p = *p type loops, |
910fdc79 | 5124 | by saying that *ANYTHING = ANYTHING. */ |
b5efa470 | 5125 | VEC_safe_push (varinfo_t, heap, varmap, var_anything); |
910fdc79 DB |
5126 | lhs.type = SCALAR; |
5127 | lhs.var = anything_id; | |
5128 | lhs.offset = 0; | |
3e5937d7 | 5129 | rhs.type = ADDRESSOF; |
910fdc79 DB |
5130 | rhs.var = anything_id; |
5131 | rhs.offset = 0; | |
e8ca4159 | 5132 | |
a5eadacc DB |
5133 | /* This specifically does not use process_constraint because |
5134 | process_constraint ignores all anything = anything constraints, since all | |
5135 | but this one are redundant. */ | |
b5efa470 | 5136 | VEC_safe_push (constraint_t, heap, constraints, new_constraint (lhs, rhs)); |
c58936b6 | 5137 | |
910fdc79 DB |
5138 | /* Create the READONLY variable, used to represent that a variable |
5139 | points to readonly memory. */ | |
5140 | readonly_tree = create_tmp_var_raw (void_type_node, "READONLY"); | |
3e5937d7 | 5141 | var_readonly = new_var_info (readonly_tree, 2, "READONLY"); |
910fdc79 DB |
5142 | var_readonly->is_artificial_var = 1; |
5143 | var_readonly->offset = 0; | |
5144 | var_readonly->size = ~0; | |
5145 | var_readonly->fullsize = ~0; | |
5146 | var_readonly->next = NULL; | |
13c2c08b | 5147 | var_readonly->is_special_var = 1; |
3e5937d7 | 5148 | insert_vi_for_tree (readonly_tree, var_readonly); |
910fdc79 | 5149 | readonly_id = 2; |
b5efa470 | 5150 | VEC_safe_push (varinfo_t, heap, varmap, var_readonly); |
910fdc79 DB |
5151 | |
5152 | /* readonly memory points to anything, in order to make deref | |
5153 | easier. In reality, it points to anything the particular | |
5154 | readonly variable can point to, but we don't track this | |
607fb860 | 5155 | separately. */ |
910fdc79 DB |
5156 | lhs.type = SCALAR; |
5157 | lhs.var = readonly_id; | |
5158 | lhs.offset = 0; | |
3e5937d7 | 5159 | rhs.type = ADDRESSOF; |
910fdc79 DB |
5160 | rhs.var = anything_id; |
5161 | rhs.offset = 0; | |
c58936b6 | 5162 | |
910fdc79 | 5163 | process_constraint (new_constraint (lhs, rhs)); |
c58936b6 | 5164 | |
910fdc79 DB |
5165 | /* Create the INTEGER variable, used to represent that a variable points |
5166 | to an INTEGER. */ | |
5167 | integer_tree = create_tmp_var_raw (void_type_node, "INTEGER"); | |
3e5937d7 DB |
5168 | var_integer = new_var_info (integer_tree, 3, "INTEGER"); |
5169 | insert_vi_for_tree (integer_tree, var_integer); | |
910fdc79 DB |
5170 | var_integer->is_artificial_var = 1; |
5171 | var_integer->size = ~0; | |
5172 | var_integer->fullsize = ~0; | |
5173 | var_integer->offset = 0; | |
5174 | var_integer->next = NULL; | |
13c2c08b | 5175 | var_integer->is_special_var = 1; |
910fdc79 | 5176 | integer_id = 3; |
b5efa470 | 5177 | VEC_safe_push (varinfo_t, heap, varmap, var_integer); |
a5eadacc | 5178 | |
21392f19 DB |
5179 | /* INTEGER = ANYTHING, because we don't know where a dereference of |
5180 | a random integer will point to. */ | |
a5eadacc DB |
5181 | lhs.type = SCALAR; |
5182 | lhs.var = integer_id; | |
5183 | lhs.offset = 0; | |
3e5937d7 | 5184 | rhs.type = ADDRESSOF; |
a5eadacc DB |
5185 | rhs.var = anything_id; |
5186 | rhs.offset = 0; | |
5187 | process_constraint (new_constraint (lhs, rhs)); | |
c58936b6 | 5188 | } |
910fdc79 | 5189 | |
4ee00913 | 5190 | /* Initialize things necessary to perform PTA */ |
910fdc79 | 5191 | |
4ee00913 DB |
5192 | static void |
5193 | init_alias_vars (void) | |
910fdc79 | 5194 | { |
3e5937d7 DB |
5195 | bitmap_obstack_initialize (&pta_obstack); |
5196 | bitmap_obstack_initialize (&oldpta_obstack); | |
4ee00913 | 5197 | bitmap_obstack_initialize (&predbitmap_obstack); |
910fdc79 | 5198 | |
c58936b6 | 5199 | constraint_pool = create_alloc_pool ("Constraint pool", |
910fdc79 DB |
5200 | sizeof (struct constraint), 30); |
5201 | variable_info_pool = create_alloc_pool ("Variable info pool", | |
5202 | sizeof (struct variable_info), 30); | |
b5efa470 DB |
5203 | constraints = VEC_alloc (constraint_t, heap, 8); |
5204 | varmap = VEC_alloc (varinfo_t, heap, 8); | |
15814ba0 | 5205 | vi_for_tree = pointer_map_create (); |
3e5937d7 | 5206 | |
910fdc79 | 5207 | memset (&stats, 0, sizeof (stats)); |
1296c31f DB |
5208 | shared_bitmap_table = htab_create (511, shared_bitmap_hash, |
5209 | shared_bitmap_eq, free); | |
910fdc79 | 5210 | init_base_vars (); |
4ee00913 DB |
5211 | } |
5212 | ||
3e5937d7 DB |
5213 | /* Remove the REF and ADDRESS edges from GRAPH, as well as all the |
5214 | predecessor edges. */ | |
5215 | ||
5216 | static void | |
5217 | remove_preds_and_fake_succs (constraint_graph_t graph) | |
5218 | { | |
5219 | unsigned int i; | |
5220 | ||
5221 | /* Clear the implicit ref and address nodes from the successor | |
5222 | lists. */ | |
5223 | for (i = 0; i < FIRST_REF_NODE; i++) | |
5224 | { | |
5225 | if (graph->succs[i]) | |
5226 | bitmap_clear_range (graph->succs[i], FIRST_REF_NODE, | |
5227 | FIRST_REF_NODE * 2); | |
5228 | } | |
5229 | ||
5230 | /* Free the successor list for the non-ref nodes. */ | |
5231 | for (i = FIRST_REF_NODE; i < graph->size; i++) | |
5232 | { | |
5233 | if (graph->succs[i]) | |
5234 | BITMAP_FREE (graph->succs[i]); | |
5235 | } | |
5236 | ||
5237 | /* Now reallocate the size of the successor list as, and blow away | |
5238 | the predecessor bitmaps. */ | |
5239 | graph->size = VEC_length (varinfo_t, varmap); | |
c22940cd | 5240 | graph->succs = XRESIZEVEC (bitmap, graph->succs, graph->size); |
3e5937d7 DB |
5241 | |
5242 | free (graph->implicit_preds); | |
5243 | graph->implicit_preds = NULL; | |
5244 | free (graph->preds); | |
5245 | graph->preds = NULL; | |
5246 | bitmap_obstack_release (&predbitmap_obstack); | |
5247 | } | |
5248 | ||
058dcc25 ILT |
5249 | /* Compute the set of variables we can't TBAA prune. */ |
5250 | ||
5251 | static void | |
5252 | compute_tbaa_pruning (void) | |
5253 | { | |
5254 | unsigned int size = VEC_length (varinfo_t, varmap); | |
5255 | unsigned int i; | |
5256 | bool any; | |
5257 | ||
5258 | changed_count = 0; | |
5259 | changed = sbitmap_alloc (size); | |
5260 | sbitmap_zero (changed); | |
5261 | ||
5262 | /* Mark all initial no_tbaa_pruning nodes as changed. */ | |
5263 | any = false; | |
5264 | for (i = 0; i < size; ++i) | |
5265 | { | |
5266 | varinfo_t ivi = get_varinfo (i); | |
5267 | ||
5268 | if (find (i) == i && ivi->no_tbaa_pruning) | |
5269 | { | |
5270 | any = true; | |
5271 | if ((graph->succs[i] && !bitmap_empty_p (graph->succs[i])) | |
5272 | || VEC_length (constraint_t, graph->complex[i]) > 0) | |
5273 | { | |
5274 | SET_BIT (changed, i); | |
5275 | ++changed_count; | |
5276 | } | |
5277 | } | |
5278 | } | |
5279 | ||
5280 | while (changed_count > 0) | |
5281 | { | |
5282 | struct topo_info *ti = init_topo_info (); | |
5283 | ++stats.iterations; | |
5284 | ||
058dcc25 ILT |
5285 | compute_topo_order (graph, ti); |
5286 | ||
5287 | while (VEC_length (unsigned, ti->topo_order) != 0) | |
5288 | { | |
5289 | bitmap_iterator bi; | |
5290 | ||
5291 | i = VEC_pop (unsigned, ti->topo_order); | |
5292 | ||
5293 | /* If this variable is not a representative, skip it. */ | |
5294 | if (find (i) != i) | |
5295 | continue; | |
5296 | ||
5297 | /* If the node has changed, we need to process the complex | |
5298 | constraints and outgoing edges again. */ | |
5299 | if (TEST_BIT (changed, i)) | |
5300 | { | |
5301 | unsigned int j; | |
5302 | constraint_t c; | |
5303 | VEC(constraint_t,heap) *complex = graph->complex[i]; | |
5304 | ||
5305 | RESET_BIT (changed, i); | |
5306 | --changed_count; | |
5307 | ||
5308 | /* Process the complex copy constraints. */ | |
5309 | for (j = 0; VEC_iterate (constraint_t, complex, j, c); ++j) | |
5310 | { | |
5311 | if (c->lhs.type == SCALAR && c->rhs.type == SCALAR) | |
5312 | { | |
5313 | varinfo_t lhsvi = get_varinfo (find (c->lhs.var)); | |
5314 | ||
5315 | if (!lhsvi->no_tbaa_pruning) | |
5316 | { | |
5317 | lhsvi->no_tbaa_pruning = true; | |
5318 | if (!TEST_BIT (changed, lhsvi->id)) | |
5319 | { | |
5320 | SET_BIT (changed, lhsvi->id); | |
5321 | ++changed_count; | |
5322 | } | |
5323 | } | |
5324 | } | |
5325 | } | |
5326 | ||
5327 | /* Propagate to all successors. */ | |
5328 | EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i], 0, j, bi) | |
5329 | { | |
5330 | unsigned int to = find (j); | |
5331 | varinfo_t tovi = get_varinfo (to); | |
5332 | ||
5333 | /* Don't propagate to ourselves. */ | |
5334 | if (to == i) | |
5335 | continue; | |
5336 | ||
5337 | if (!tovi->no_tbaa_pruning) | |
5338 | { | |
5339 | tovi->no_tbaa_pruning = true; | |
5340 | if (!TEST_BIT (changed, to)) | |
5341 | { | |
5342 | SET_BIT (changed, to); | |
5343 | ++changed_count; | |
5344 | } | |
5345 | } | |
5346 | } | |
5347 | } | |
5348 | } | |
5349 | ||
5350 | free_topo_info (ti); | |
058dcc25 ILT |
5351 | } |
5352 | ||
5353 | sbitmap_free (changed); | |
5354 | ||
5355 | if (any) | |
5356 | { | |
5357 | for (i = 0; i < size; ++i) | |
5358 | { | |
5359 | varinfo_t ivi = get_varinfo (i); | |
5360 | varinfo_t ivip = get_varinfo (find (i)); | |
5361 | ||
5362 | if (ivip->no_tbaa_pruning) | |
5363 | { | |
5364 | tree var = ivi->decl; | |
5365 | ||
5366 | if (TREE_CODE (var) == SSA_NAME) | |
5367 | var = SSA_NAME_VAR (var); | |
5368 | ||
5369 | if (POINTER_TYPE_P (TREE_TYPE (var))) | |
5370 | { | |
5371 | DECL_NO_TBAA_P (var) = 1; | |
5372 | ||
5373 | /* Tell the RTL layer that this pointer can alias | |
5374 | anything. */ | |
5375 | DECL_POINTER_ALIAS_SET (var) = 0; | |
5376 | } | |
5377 | } | |
5378 | } | |
5379 | } | |
5380 | } | |
5381 | ||
4ee00913 DB |
5382 | /* Create points-to sets for the current function. See the comments |
5383 | at the start of the file for an algorithmic overview. */ | |
5384 | ||
5385 | void | |
5386 | compute_points_to_sets (struct alias_info *ai) | |
5387 | { | |
3e5937d7 | 5388 | struct scc_info *si; |
4ee00913 DB |
5389 | basic_block bb; |
5390 | ||
5391 | timevar_push (TV_TREE_PTA); | |
5392 | ||
5393 | init_alias_vars (); | |
c9fa8bd4 | 5394 | init_alias_heapvars (); |
910fdc79 DB |
5395 | |
5396 | intra_create_variable_infos (); | |
5397 | ||
5398 | /* Now walk all statements and derive aliases. */ | |
5399 | FOR_EACH_BB (bb) | |
5400 | { | |
c58936b6 | 5401 | block_stmt_iterator bsi; |
910fdc79 DB |
5402 | tree phi; |
5403 | ||
3d95caa4 | 5404 | for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) |
4ee00913 DB |
5405 | { |
5406 | if (is_gimple_reg (PHI_RESULT (phi))) | |
5407 | { | |
5408 | find_func_aliases (phi); | |
d37d06fe | 5409 | |
4ee00913 DB |
5410 | /* Update various related attributes like escaped |
5411 | addresses, pointer dereferences for loads and stores. | |
5412 | This is used when creating name tags and alias | |
5413 | sets. */ | |
5414 | update_alias_info (phi, ai); | |
5415 | } | |
5416 | } | |
910fdc79 | 5417 | |
058dcc25 | 5418 | for (bsi = bsi_start (bb); !bsi_end_p (bsi); ) |
4ee00913 DB |
5419 | { |
5420 | tree stmt = bsi_stmt (bsi); | |
21392f19 | 5421 | |
4ee00913 | 5422 | find_func_aliases (stmt); |
38635499 | 5423 | |
21392f19 DB |
5424 | /* Update various related attributes like escaped |
5425 | addresses, pointer dereferences for loads and stores. | |
5426 | This is used when creating name tags and alias | |
5427 | sets. */ | |
4ee00913 | 5428 | update_alias_info (stmt, ai); |
058dcc25 ILT |
5429 | |
5430 | /* The information in CHANGE_DYNAMIC_TYPE_EXPR nodes has now | |
5431 | been captured, and we can remove them. */ | |
5432 | if (TREE_CODE (stmt) == CHANGE_DYNAMIC_TYPE_EXPR) | |
5433 | bsi_remove (&bsi, true); | |
5434 | else | |
5435 | bsi_next (&bsi); | |
4ee00913 | 5436 | } |
910fdc79 DB |
5437 | } |
5438 | ||
910fdc79 DB |
5439 | |
5440 | if (dump_file) | |
5441 | { | |
e8ca4159 | 5442 | fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n"); |
910fdc79 DB |
5443 | dump_constraints (dump_file); |
5444 | } | |
c58936b6 | 5445 | |
21392f19 DB |
5446 | if (dump_file) |
5447 | fprintf (dump_file, | |
5448 | "\nCollapsing static cycles and doing variable " | |
7b765bed DB |
5449 | "substitution\n"); |
5450 | ||
5451 | init_graph (VEC_length (varinfo_t, varmap) * 2); | |
5452 | ||
5453 | if (dump_file) | |
5454 | fprintf (dump_file, "Building predecessor graph\n"); | |
3e5937d7 | 5455 | build_pred_graph (); |
7b765bed DB |
5456 | |
5457 | if (dump_file) | |
5458 | fprintf (dump_file, "Detecting pointer and location " | |
5459 | "equivalences\n"); | |
3e5937d7 | 5460 | si = perform_var_substitution (graph); |
7b765bed DB |
5461 | |
5462 | if (dump_file) | |
5463 | fprintf (dump_file, "Rewriting constraints and unifying " | |
5464 | "variables\n"); | |
5465 | rewrite_constraints (graph, si); | |
3e5937d7 DB |
5466 | free_var_substitution_info (si); |
5467 | ||
5468 | build_succ_graph (); | |
7b765bed DB |
5469 | move_complex_constraints (graph); |
5470 | ||
5471 | if (dump_file) | |
5472 | fprintf (dump_file, "Uniting pointer but not location equivalent " | |
5473 | "variables\n"); | |
5474 | unite_pointer_equivalences (graph); | |
5475 | ||
5476 | if (dump_file) | |
5477 | fprintf (dump_file, "Finding indirect cycles\n"); | |
3e5937d7 | 5478 | find_indirect_cycles (graph); |
c58936b6 | 5479 | |
3e5937d7 DB |
5480 | /* Implicit nodes and predecessors are no longer necessary at this |
5481 | point. */ | |
5482 | remove_preds_and_fake_succs (graph); | |
c58936b6 | 5483 | |
21392f19 | 5484 | if (dump_file) |
7b765bed | 5485 | fprintf (dump_file, "Solving graph\n"); |
c58936b6 | 5486 | |
21392f19 | 5487 | solve_graph (graph); |
c58936b6 | 5488 | |
058dcc25 ILT |
5489 | compute_tbaa_pruning (); |
5490 | ||
910fdc79 DB |
5491 | if (dump_file) |
5492 | dump_sa_points_to_info (dump_file); | |
c58936b6 | 5493 | |
910fdc79 | 5494 | have_alias_info = true; |
e8ca4159 DN |
5495 | |
5496 | timevar_pop (TV_TREE_PTA); | |
910fdc79 DB |
5497 | } |
5498 | ||
910fdc79 DB |
5499 | |
5500 | /* Delete created points-to sets. */ | |
5501 | ||
e8ca4159 DN |
5502 | void |
5503 | delete_points_to_sets (void) | |
910fdc79 | 5504 | { |
7b765bed | 5505 | unsigned int i; |
c58936b6 | 5506 | |
1296c31f | 5507 | htab_delete (shared_bitmap_table); |
3e5937d7 DB |
5508 | if (dump_file && (dump_flags & TDF_STATS)) |
5509 | fprintf (dump_file, "Points to sets created:%d\n", | |
5510 | stats.points_to_sets_created); | |
5511 | ||
15814ba0 | 5512 | pointer_map_destroy (vi_for_tree); |
3e5937d7 | 5513 | bitmap_obstack_release (&pta_obstack); |
b5efa470 | 5514 | VEC_free (constraint_t, heap, constraints); |
c58936b6 | 5515 | |
7b765bed | 5516 | for (i = 0; i < graph->size; i++) |
3e5937d7 | 5517 | VEC_free (constraint_t, heap, graph->complex[i]); |
285463b5 | 5518 | free (graph->complex); |
21392f19 | 5519 | |
3e5937d7 | 5520 | free (graph->rep); |
57250223 | 5521 | free (graph->succs); |
7b765bed DB |
5522 | free (graph->pe); |
5523 | free (graph->pe_rep); | |
3e5937d7 | 5524 | free (graph->indirect_cycles); |
b5efa470 DB |
5525 | free (graph); |
5526 | ||
5527 | VEC_free (varinfo_t, heap, varmap); | |
910fdc79 | 5528 | free_alloc_pool (variable_info_pool); |
c58936b6 | 5529 | free_alloc_pool (constraint_pool); |
910fdc79 DB |
5530 | have_alias_info = false; |
5531 | } | |
973162ec | 5532 | |
4ee00913 DB |
5533 | /* Return true if we should execute IPA PTA. */ |
5534 | static bool | |
5535 | gate_ipa_pta (void) | |
5536 | { | |
5537 | return (flag_unit_at_a_time != 0 | |
c58936b6 | 5538 | && flag_ipa_pta |
4ee00913 DB |
5539 | /* Don't bother doing anything if the program has errors. */ |
5540 | && !(errorcount || sorrycount)); | |
5541 | } | |
5542 | ||
5543 | /* Execute the driver for IPA PTA. */ | |
c2924966 | 5544 | static unsigned int |
4ee00913 DB |
5545 | ipa_pta_execute (void) |
5546 | { | |
5547 | struct cgraph_node *node; | |
3e5937d7 DB |
5548 | struct scc_info *si; |
5549 | ||
4ee00913 | 5550 | in_ipa_mode = 1; |
4cf4d6a3 | 5551 | init_alias_heapvars (); |
4ee00913 | 5552 | init_alias_vars (); |
c58936b6 | 5553 | |
4ee00913 DB |
5554 | for (node = cgraph_nodes; node; node = node->next) |
5555 | { | |
5556 | if (!node->analyzed || cgraph_is_master_clone (node)) | |
5557 | { | |
5558 | unsigned int varid; | |
c58936b6 DB |
5559 | |
5560 | varid = create_function_info_for (node->decl, | |
4ee00913 DB |
5561 | cgraph_node_name (node)); |
5562 | if (node->local.externally_visible) | |
5563 | { | |
5564 | varinfo_t fi = get_varinfo (varid); | |
5565 | for (; fi; fi = fi->next) | |
c58936b6 | 5566 | make_constraint_from_anything (fi); |
4ee00913 DB |
5567 | } |
5568 | } | |
5569 | } | |
5570 | for (node = cgraph_nodes; node; node = node->next) | |
5571 | { | |
5572 | if (node->analyzed && cgraph_is_master_clone (node)) | |
5573 | { | |
5576d6f2 | 5574 | struct function *func = DECL_STRUCT_FUNCTION (node->decl); |
4ee00913 DB |
5575 | basic_block bb; |
5576 | tree old_func_decl = current_function_decl; | |
5577 | if (dump_file) | |
c58936b6 DB |
5578 | fprintf (dump_file, |
5579 | "Generating constraints for %s\n", | |
5580 | cgraph_node_name (node)); | |
5576d6f2 | 5581 | push_cfun (func); |
4ee00913 DB |
5582 | current_function_decl = node->decl; |
5583 | ||
5576d6f2 | 5584 | FOR_EACH_BB_FN (bb, func) |
4ee00913 | 5585 | { |
c58936b6 | 5586 | block_stmt_iterator bsi; |
4ee00913 | 5587 | tree phi; |
c58936b6 | 5588 | |
3d95caa4 | 5589 | for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) |
4ee00913 DB |
5590 | { |
5591 | if (is_gimple_reg (PHI_RESULT (phi))) | |
5592 | { | |
5593 | find_func_aliases (phi); | |
5594 | } | |
5595 | } | |
c58936b6 | 5596 | |
4ee00913 DB |
5597 | for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) |
5598 | { | |
5599 | tree stmt = bsi_stmt (bsi); | |
5600 | find_func_aliases (stmt); | |
5601 | } | |
c58936b6 | 5602 | } |
4ee00913 | 5603 | current_function_decl = old_func_decl; |
c58936b6 | 5604 | pop_cfun (); |
4ee00913 DB |
5605 | } |
5606 | else | |
5607 | { | |
5608 | /* Make point to anything. */ | |
5609 | } | |
5610 | } | |
5611 | ||
4ee00913 DB |
5612 | if (dump_file) |
5613 | { | |
5614 | fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n"); | |
5615 | dump_constraints (dump_file); | |
5616 | } | |
c58936b6 | 5617 | |
21392f19 | 5618 | if (dump_file) |
c58936b6 | 5619 | fprintf (dump_file, |
21392f19 DB |
5620 | "\nCollapsing static cycles and doing variable " |
5621 | "substitution:\n"); | |
c58936b6 | 5622 | |
7b765bed | 5623 | init_graph (VEC_length (varinfo_t, varmap) * 2); |
3e5937d7 DB |
5624 | build_pred_graph (); |
5625 | si = perform_var_substitution (graph); | |
7b765bed | 5626 | rewrite_constraints (graph, si); |
3e5937d7 DB |
5627 | free_var_substitution_info (si); |
5628 | ||
5629 | build_succ_graph (); | |
7b765bed DB |
5630 | move_complex_constraints (graph); |
5631 | unite_pointer_equivalences (graph); | |
3e5937d7 DB |
5632 | find_indirect_cycles (graph); |
5633 | ||
5634 | /* Implicit nodes and predecessors are no longer necessary at this | |
5635 | point. */ | |
5636 | remove_preds_and_fake_succs (graph); | |
c58936b6 | 5637 | |
21392f19 | 5638 | if (dump_file) |
7b765bed | 5639 | fprintf (dump_file, "\nSolving graph\n"); |
c58936b6 | 5640 | |
21392f19 | 5641 | solve_graph (graph); |
c58936b6 | 5642 | |
4ee00913 DB |
5643 | if (dump_file) |
5644 | dump_sa_points_to_info (dump_file); | |
c58936b6 | 5645 | |
4ee00913 | 5646 | in_ipa_mode = 0; |
4cf4d6a3 DB |
5647 | delete_alias_heapvars (); |
5648 | delete_points_to_sets (); | |
c2924966 | 5649 | return 0; |
4ee00913 | 5650 | } |
c58936b6 | 5651 | |
4ee00913 DB |
5652 | struct tree_opt_pass pass_ipa_pta = |
5653 | { | |
5654 | "pta", /* name */ | |
5655 | gate_ipa_pta, /* gate */ | |
5656 | ipa_pta_execute, /* execute */ | |
5657 | NULL, /* sub */ | |
5658 | NULL, /* next */ | |
5659 | 0, /* static_pass_number */ | |
5660 | TV_IPA_PTA, /* tv_id */ | |
5661 | 0, /* properties_required */ | |
5662 | 0, /* properties_provided */ | |
5663 | 0, /* properties_destroyed */ | |
5664 | 0, /* todo_flags_start */ | |
7b765bed | 5665 | TODO_update_ssa, /* todo_flags_finish */ |
4ee00913 DB |
5666 | 0 /* letter */ |
5667 | }; | |
5668 | ||
c900f6aa | 5669 | /* Initialize the heapvar for statement mapping. */ |
83f676b3 | 5670 | void |
c900f6aa | 5671 | init_alias_heapvars (void) |
973162ec | 5672 | { |
c9fa8bd4 JH |
5673 | if (!heapvar_for_stmt) |
5674 | heapvar_for_stmt = htab_create_ggc (11, tree_map_hash, tree_map_eq, | |
5675 | NULL); | |
c900f6aa | 5676 | } |
973162ec | 5677 | |
c900f6aa DB |
5678 | void |
5679 | delete_alias_heapvars (void) | |
5680 | { | |
21392f19 | 5681 | htab_delete (heapvar_for_stmt); |
c9fa8bd4 | 5682 | heapvar_for_stmt = NULL; |
973162ec | 5683 | } |
c900f6aa | 5684 | |
c58936b6 | 5685 | |
c900f6aa | 5686 | #include "gt-tree-ssa-structalias.h" |