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