]>
Commit | Line | Data |
---|---|---|
910fdc79 DB |
1 | /* Tree based points-to analysis |
2 | Copyright (C) 2005 Free Software Foundation, Inc. | |
3 | Contributed by Daniel Berlin <dberlin@dberlin.org> | |
4 | ||
5 | This file is part of GCC. | |
6 | ||
7 | GCC is free software; you can redistribute it and/or modify | |
8 | under the terms of the GNU General Public License as published by | |
9 | the Free Software Foundation; either version 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" | |
e8ca4159 | 51 | #include "tree-ssa-structalias.h" |
910fdc79 DB |
52 | |
53 | /* The idea behind this analyzer is to generate set constraints from the | |
54 | program, then solve the resulting constraints in order to generate the | |
55 | points-to sets. | |
56 | ||
57 | Set constraints are a way of modeling program analysis problems that | |
58 | involve sets. They consist of an inclusion constraint language, | |
59 | describing the variables (each variable is a set) and operations that | |
60 | are involved on the variables, and a set of rules that derive facts | |
61 | from these operations. To solve a system of set constraints, you derive | |
62 | all possible facts under the rules, which gives you the correct sets | |
63 | as a consequence. | |
64 | ||
65 | See "Efficient Field-sensitive pointer analysis for C" by "David | |
66 | J. Pearce and Paul H. J. Kelly and Chris Hankin, at | |
67 | http://citeseer.ist.psu.edu/pearce04efficient.html | |
68 | ||
69 | Also see "Ultra-fast Aliasing Analysis using CLA: A Million Lines | |
70 | of C Code in a Second" by ""Nevin Heintze and Olivier Tardieu" at | |
71 | http://citeseer.ist.psu.edu/heintze01ultrafast.html | |
72 | ||
73 | There are three types of constraint expressions, DEREF, ADDRESSOF, and | |
74 | SCALAR. Each constraint expression consists of a constraint type, | |
75 | a variable, and an offset. | |
76 | ||
77 | SCALAR is a constraint expression type used to represent x, whether | |
78 | it appears on the LHS or the RHS of a statement. | |
79 | DEREF is a constraint expression type used to represent *x, whether | |
80 | it appears on the LHS or the RHS of a statement. | |
81 | ADDRESSOF is a constraint expression used to represent &x, whether | |
607fb860 | 82 | it appears on the LHS or the RHS of a statement. |
910fdc79 DB |
83 | |
84 | Each pointer variable in the program is assigned an integer id, and | |
85 | each field of a structure variable is assigned an integer id as well. | |
86 | ||
87 | Structure variables are linked to their list of fields through a "next | |
88 | field" in each variable that points to the next field in offset | |
89 | order. | |
90 | Each variable for a structure field has | |
91 | ||
92 | 1. "size", that tells the size in bits of that field. | |
93 | 2. "fullsize, that tells the size in bits of the entire structure. | |
94 | 3. "offset", that tells the offset in bits from the beginning of the | |
95 | structure to this field. | |
96 | ||
97 | Thus, | |
98 | struct f | |
99 | { | |
100 | int a; | |
101 | int b; | |
102 | } foo; | |
103 | int *bar; | |
104 | ||
105 | looks like | |
106 | ||
107 | foo.a -> id 1, size 32, offset 0, fullsize 64, next foo.b | |
108 | foo.b -> id 2, size 32, offset 32, fullsize 64, next NULL | |
109 | bar -> id 3, size 32, offset 0, fullsize 32, next NULL | |
110 | ||
111 | ||
112 | In order to solve the system of set constraints, the following is | |
113 | done: | |
114 | ||
115 | 1. Each constraint variable x has a solution set associated with it, | |
116 | Sol(x). | |
117 | ||
118 | 2. Constraints are separated into direct, copy, and complex. | |
119 | Direct constraints are ADDRESSOF constraints that require no extra | |
120 | processing, such as P = &Q | |
121 | Copy constraints are those of the form P = Q. | |
122 | Complex constraints are all the constraints involving dereferences. | |
123 | ||
124 | 3. All direct constraints of the form P = &Q are processed, such | |
125 | that Q is added to Sol(P) | |
126 | ||
127 | 4. All complex constraints for a given constraint variable are stored in a | |
128 | linked list attached to that variable's node. | |
129 | ||
130 | 5. A directed graph is built out of the copy constraints. Each | |
131 | constraint variable is a node in the graph, and an edge from | |
132 | Q to P is added for each copy constraint of the form P = Q | |
133 | ||
134 | 6. The graph is then walked, and solution sets are | |
135 | propagated along the copy edges, such that an edge from Q to P | |
136 | causes Sol(P) <- Sol(P) union Sol(Q). | |
137 | ||
138 | 7. As we visit each node, all complex constraints associated with | |
607fb860 KH |
139 | that node are processed by adding appropriate copy edges to the graph, or the |
140 | appropriate variables to the solution set. | |
910fdc79 DB |
141 | |
142 | 8. The process of walking the graph is iterated until no solution | |
143 | sets change. | |
144 | ||
145 | Prior to walking the graph in steps 6 and 7, We perform static | |
146 | cycle elimination on the constraint graph, as well | |
147 | as off-line variable substitution. | |
148 | ||
149 | TODO: Adding offsets to pointer-to-structures can be handled (IE not punted | |
150 | on and turned into anything), but isn't. You can just see what offset | |
151 | inside the pointed-to struct it's going to access. | |
152 | ||
153 | TODO: Constant bounded arrays can be handled as if they were structs of the | |
154 | same number of elements. | |
155 | ||
156 | TODO: Modeling heap and incoming pointers becomes much better if we | |
157 | add fields to them as we discover them, which we could do. | |
158 | ||
159 | TODO: We could handle unions, but to be honest, it's probably not | |
160 | worth the pain or slowdown. */ | |
161 | ||
162 | static bool use_field_sensitive = true; | |
163 | static unsigned int create_variable_info_for (tree, const char *); | |
164 | static struct constraint_expr get_constraint_for (tree); | |
165 | static void build_constraint_graph (void); | |
166 | ||
167 | static bitmap_obstack ptabitmap_obstack; | |
168 | static bitmap_obstack iteration_obstack; | |
169 | DEF_VEC_P(constraint_t); | |
170 | DEF_VEC_ALLOC_P(constraint_t,gc); | |
171 | ||
172 | static struct constraint_stats | |
173 | { | |
174 | unsigned int total_vars; | |
175 | unsigned int collapsed_vars; | |
176 | unsigned int unified_vars_static; | |
177 | unsigned int unified_vars_dynamic; | |
178 | unsigned int iterations; | |
179 | } stats; | |
180 | ||
181 | struct variable_info | |
182 | { | |
183 | /* ID of this variable */ | |
184 | unsigned int id; | |
185 | ||
186 | /* Name of this variable */ | |
187 | const char *name; | |
188 | ||
189 | /* Tree that this variable is associated with. */ | |
190 | tree decl; | |
191 | ||
192 | /* Offset of this variable, in bits, from the base variable */ | |
193 | unsigned HOST_WIDE_INT offset; | |
194 | ||
195 | /* Size of the variable, in bits. */ | |
196 | unsigned HOST_WIDE_INT size; | |
197 | ||
198 | /* Full size of the base variable, in bits. */ | |
199 | unsigned HOST_WIDE_INT fullsize; | |
200 | ||
201 | /* A link to the variable for the next field in this structure. */ | |
202 | struct variable_info *next; | |
203 | ||
204 | /* Node in the graph that represents the constraints and points-to | |
205 | solution for the variable. */ | |
206 | unsigned int node; | |
207 | ||
208 | /* True if the address of this variable is taken. Needed for | |
209 | variable substitution. */ | |
210 | unsigned int address_taken:1; | |
211 | ||
212 | /* True if this variable is the target of a dereference. Needed for | |
213 | variable substitution. */ | |
214 | unsigned int indirect_target:1; | |
215 | ||
216 | /* True if this is a variable created by the constraint analysis, such as | |
217 | heap variables and constraints we had to break up. */ | |
218 | unsigned int is_artificial_var:1; | |
219 | ||
220 | /* True for variables whose size is not known or variable. */ | |
221 | unsigned int is_unknown_size_var:1; | |
222 | ||
58b82d2b DB |
223 | /* True for variables that have unions somewhere in them. */ |
224 | unsigned int has_union:1; | |
225 | ||
e8ca4159 DN |
226 | /* True if this is a heap variable. */ |
227 | unsigned int is_heap_var:1; | |
228 | ||
910fdc79 DB |
229 | /* Points-to set for this variable. */ |
230 | bitmap solution; | |
231 | ||
232 | /* Variable ids represented by this node. */ | |
233 | bitmap variables; | |
234 | ||
235 | /* Vector of complex constraints for this node. Complex | |
236 | constraints are those involving dereferences. */ | |
237 | VEC(constraint_t,gc) *complex; | |
238 | }; | |
239 | typedef struct variable_info *varinfo_t; | |
240 | ||
241 | static varinfo_t first_vi_for_offset (varinfo_t, unsigned HOST_WIDE_INT); | |
242 | ||
243 | /* Pool of variable info structures. */ | |
244 | static alloc_pool variable_info_pool; | |
245 | ||
246 | DEF_VEC_P(varinfo_t); | |
247 | ||
248 | DEF_VEC_ALLOC_P(varinfo_t, gc); | |
249 | ||
607fb860 | 250 | /* Table of variable info structures for constraint variables. Indexed directly |
910fdc79 DB |
251 | by variable info id. */ |
252 | static VEC(varinfo_t,gc) *varmap; | |
253 | #define get_varinfo(n) VEC_index(varinfo_t, varmap, n) | |
254 | ||
255 | /* Variable that represents the unknown pointer. */ | |
256 | static varinfo_t var_anything; | |
257 | static tree anything_tree; | |
258 | static unsigned int anything_id; | |
259 | ||
260 | /* Variable that represents the NULL pointer. */ | |
261 | static varinfo_t var_nothing; | |
262 | static tree nothing_tree; | |
263 | static unsigned int nothing_id; | |
264 | ||
265 | /* Variable that represents read only memory. */ | |
266 | static varinfo_t var_readonly; | |
267 | static tree readonly_tree; | |
268 | static unsigned int readonly_id; | |
269 | ||
270 | /* Variable that represents integers. This is used for when people do things | |
271 | like &0->a.b. */ | |
272 | static varinfo_t var_integer; | |
273 | static tree integer_tree; | |
274 | static unsigned int integer_id; | |
275 | ||
e8ca4159 DN |
276 | /* Variable that represents arbitrary offsets into an object. Used to |
277 | represent pointer arithmetic, which may not legally escape the | |
278 | bounds of an object. */ | |
279 | static varinfo_t var_anyoffset; | |
280 | static tree anyoffset_tree; | |
281 | static unsigned int anyoffset_id; | |
910fdc79 DB |
282 | |
283 | /* Return a new variable info structure consisting for a variable | |
284 | named NAME, and using constraint graph node NODE. */ | |
285 | ||
286 | static varinfo_t | |
287 | new_var_info (tree t, unsigned int id, const char *name, unsigned int node) | |
288 | { | |
289 | varinfo_t ret = pool_alloc (variable_info_pool); | |
290 | ||
291 | ret->id = id; | |
292 | ret->name = name; | |
293 | ret->decl = t; | |
294 | ret->node = node; | |
295 | ret->address_taken = false; | |
296 | ret->indirect_target = false; | |
297 | ret->is_artificial_var = false; | |
e8ca4159 | 298 | ret->is_heap_var = false; |
910fdc79 DB |
299 | ret->is_unknown_size_var = false; |
300 | ret->solution = BITMAP_ALLOC (&ptabitmap_obstack); | |
301 | bitmap_clear (ret->solution); | |
302 | ret->variables = BITMAP_ALLOC (&ptabitmap_obstack); | |
303 | bitmap_clear (ret->variables); | |
304 | ret->complex = NULL; | |
305 | ret->next = NULL; | |
306 | return ret; | |
307 | } | |
308 | ||
309 | typedef enum {SCALAR, DEREF, ADDRESSOF} constraint_expr_type; | |
310 | ||
311 | /* An expression that appears in a constraint. */ | |
312 | ||
313 | struct constraint_expr | |
314 | { | |
315 | /* Constraint type. */ | |
316 | constraint_expr_type type; | |
317 | ||
318 | /* Variable we are referring to in the constraint. */ | |
319 | unsigned int var; | |
320 | ||
321 | /* Offset, in bits, of this constraint from the beginning of | |
322 | variables it ends up referring to. | |
323 | ||
324 | IOW, in a deref constraint, we would deref, get the result set, | |
325 | then add OFFSET to each member. */ | |
326 | unsigned HOST_WIDE_INT offset; | |
327 | }; | |
328 | ||
329 | static struct constraint_expr do_deref (struct constraint_expr); | |
330 | ||
331 | /* Our set constraints are made up of two constraint expressions, one | |
332 | LHS, and one RHS. | |
333 | ||
334 | As described in the introduction, our set constraints each represent an | |
335 | operation between set valued variables. | |
336 | */ | |
337 | struct constraint | |
338 | { | |
339 | struct constraint_expr lhs; | |
340 | struct constraint_expr rhs; | |
341 | }; | |
342 | ||
343 | /* List of constraints that we use to build the constraint graph from. */ | |
344 | ||
345 | static VEC(constraint_t,gc) *constraints; | |
346 | static alloc_pool constraint_pool; | |
347 | ||
348 | /* An edge in the constraint graph. We technically have no use for | |
349 | the src, since it will always be the same node that we are indexing | |
350 | into the pred/succ arrays with, but it's nice for checking | |
351 | purposes. The edges are weighted, with a bit set in weights for | |
352 | each edge from src to dest with that weight. */ | |
353 | ||
354 | struct constraint_edge | |
355 | { | |
356 | unsigned int src; | |
357 | unsigned int dest; | |
358 | bitmap weights; | |
359 | }; | |
360 | ||
361 | typedef struct constraint_edge *constraint_edge_t; | |
362 | static alloc_pool constraint_edge_pool; | |
363 | ||
364 | /* Return a new constraint edge from SRC to DEST. */ | |
365 | ||
366 | static constraint_edge_t | |
367 | new_constraint_edge (unsigned int src, unsigned int dest) | |
368 | { | |
369 | constraint_edge_t ret = pool_alloc (constraint_edge_pool); | |
370 | ret->src = src; | |
371 | ret->dest = dest; | |
372 | ret->weights = NULL; | |
373 | return ret; | |
374 | } | |
375 | ||
376 | DEF_VEC_P(constraint_edge_t); | |
377 | DEF_VEC_ALLOC_P(constraint_edge_t,gc); | |
378 | ||
379 | ||
380 | /* The constraint graph is simply a set of adjacency vectors, one per | |
381 | variable. succs[x] is the vector of successors for variable x, and preds[x] | |
382 | is the vector of predecessors for variable x. | |
383 | IOW, all edges are "forward" edges, which is not like our CFG. | |
384 | So remember that | |
385 | preds[x]->src == x, and | |
386 | succs[x]->src == x*/ | |
387 | ||
388 | struct constraint_graph | |
389 | { | |
390 | VEC(constraint_edge_t,gc) **succs; | |
391 | VEC(constraint_edge_t,gc) **preds; | |
392 | }; | |
393 | ||
394 | typedef struct constraint_graph *constraint_graph_t; | |
395 | ||
396 | static constraint_graph_t graph; | |
397 | ||
398 | /* Create a new constraint consisting of LHS and RHS expressions. */ | |
399 | ||
400 | static constraint_t | |
401 | new_constraint (const struct constraint_expr lhs, | |
402 | const struct constraint_expr rhs) | |
403 | { | |
404 | constraint_t ret = pool_alloc (constraint_pool); | |
405 | ret->lhs = lhs; | |
406 | ret->rhs = rhs; | |
407 | return ret; | |
408 | } | |
409 | ||
410 | /* Print out constraint C to FILE. */ | |
411 | ||
412 | void | |
413 | dump_constraint (FILE *file, constraint_t c) | |
414 | { | |
415 | if (c->lhs.type == ADDRESSOF) | |
416 | fprintf (file, "&"); | |
417 | else if (c->lhs.type == DEREF) | |
418 | fprintf (file, "*"); | |
419 | fprintf (file, "%s", get_varinfo (c->lhs.var)->name); | |
420 | if (c->lhs.offset != 0) | |
421 | fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->lhs.offset); | |
422 | fprintf (file, " = "); | |
423 | if (c->rhs.type == ADDRESSOF) | |
424 | fprintf (file, "&"); | |
425 | else if (c->rhs.type == DEREF) | |
426 | fprintf (file, "*"); | |
427 | fprintf (file, "%s", get_varinfo (c->rhs.var)->name); | |
428 | if (c->rhs.offset != 0) | |
429 | fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->rhs.offset); | |
430 | fprintf (file, "\n"); | |
431 | } | |
432 | ||
433 | /* Print out constraint C to stderr. */ | |
434 | ||
435 | void | |
436 | debug_constraint (constraint_t c) | |
437 | { | |
438 | dump_constraint (stderr, c); | |
439 | } | |
440 | ||
441 | /* Print out all constraints to FILE */ | |
442 | ||
443 | void | |
444 | dump_constraints (FILE *file) | |
445 | { | |
446 | int i; | |
447 | constraint_t c; | |
448 | for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++) | |
449 | dump_constraint (file, c); | |
450 | } | |
451 | ||
452 | /* Print out all constraints to stderr. */ | |
453 | ||
454 | void | |
455 | debug_constraints (void) | |
456 | { | |
457 | dump_constraints (stderr); | |
458 | } | |
459 | ||
460 | /* SOLVER FUNCTIONS | |
461 | ||
462 | The solver is a simple worklist solver, that works on the following | |
463 | algorithm: | |
464 | ||
465 | sbitmap changed_nodes = all ones; | |
466 | changed_count = number of nodes; | |
467 | For each node that was already collapsed: | |
468 | changed_count--; | |
469 | ||
470 | ||
471 | while (changed_count > 0) | |
472 | { | |
473 | compute topological ordering for constraint graph | |
474 | ||
475 | find and collapse cycles in the constraint graph (updating | |
476 | changed if necessary) | |
477 | ||
478 | for each node (n) in the graph in topological order: | |
479 | changed_count--; | |
480 | ||
481 | Process each complex constraint associated with the node, | |
482 | updating changed if necessary. | |
483 | ||
484 | For each outgoing edge from n, propagate the solution from n to | |
485 | the destination of the edge, updating changed as necessary. | |
486 | ||
487 | } */ | |
488 | ||
489 | /* Return true if two constraint expressions A and B are equal. */ | |
490 | ||
491 | static bool | |
492 | constraint_expr_equal (struct constraint_expr a, struct constraint_expr b) | |
493 | { | |
494 | return a.type == b.type | |
495 | && a.var == b.var | |
496 | && a.offset == b.offset; | |
497 | } | |
498 | ||
499 | /* Return true if constraint expression A is less than constraint expression | |
500 | B. This is just arbitrary, but consistent, in order to give them an | |
501 | ordering. */ | |
502 | ||
503 | static bool | |
504 | constraint_expr_less (struct constraint_expr a, struct constraint_expr b) | |
505 | { | |
506 | if (a.type == b.type) | |
507 | { | |
508 | if (a.var == b.var) | |
509 | return a.offset < b.offset; | |
510 | else | |
511 | return a.var < b.var; | |
512 | } | |
513 | else | |
514 | return a.type < b.type; | |
515 | } | |
516 | ||
517 | /* Return true if constraint A is less than constraint B. This is just | |
518 | arbitrary, but consistent, in order to give them an ordering. */ | |
519 | ||
520 | static bool | |
521 | constraint_less (const constraint_t a, const constraint_t b) | |
522 | { | |
523 | if (constraint_expr_less (a->lhs, b->lhs)) | |
524 | return true; | |
525 | else if (constraint_expr_less (b->lhs, a->lhs)) | |
526 | return false; | |
527 | else | |
528 | return constraint_expr_less (a->rhs, b->rhs); | |
529 | } | |
530 | ||
531 | /* Return true if two constraints A and B are equal. */ | |
532 | ||
533 | static bool | |
534 | constraint_equal (struct constraint a, struct constraint b) | |
535 | { | |
536 | return constraint_expr_equal (a.lhs, b.lhs) | |
537 | && constraint_expr_equal (a.rhs, b.rhs); | |
538 | } | |
539 | ||
540 | ||
541 | /* Find a constraint LOOKFOR in the sorted constraint vector VEC */ | |
542 | ||
543 | static constraint_t | |
544 | constraint_vec_find (VEC(constraint_t,gc) *vec, | |
545 | struct constraint lookfor) | |
546 | { | |
547 | unsigned int place; | |
548 | constraint_t found; | |
549 | ||
550 | if (vec == NULL) | |
551 | return NULL; | |
552 | ||
553 | place = VEC_lower_bound (constraint_t, vec, &lookfor, constraint_less); | |
554 | if (place >= VEC_length (constraint_t, vec)) | |
555 | return NULL; | |
556 | found = VEC_index (constraint_t, vec, place); | |
557 | if (!constraint_equal (*found, lookfor)) | |
558 | return NULL; | |
559 | return found; | |
560 | } | |
561 | ||
562 | /* Union two constraint vectors, TO and FROM. Put the result in TO. */ | |
563 | ||
564 | static void | |
565 | constraint_set_union (VEC(constraint_t,gc) **to, | |
566 | VEC(constraint_t,gc) **from) | |
567 | { | |
568 | int i; | |
569 | constraint_t c; | |
570 | ||
571 | for (i = 0; VEC_iterate (constraint_t, *from, i, c); i++) | |
572 | { | |
573 | if (constraint_vec_find (*to, *c) == NULL) | |
574 | { | |
575 | unsigned int place = VEC_lower_bound (constraint_t, *to, c, | |
576 | constraint_less); | |
577 | VEC_safe_insert (constraint_t, gc, *to, place, c); | |
578 | } | |
579 | } | |
580 | } | |
581 | ||
582 | /* Take a solution set SET, add OFFSET to each member of the set, and | |
583 | overwrite SET with the result when done. */ | |
584 | ||
585 | static void | |
586 | solution_set_add (bitmap set, unsigned HOST_WIDE_INT offset) | |
587 | { | |
588 | bitmap result = BITMAP_ALLOC (&iteration_obstack); | |
589 | unsigned int i; | |
590 | bitmap_iterator bi; | |
591 | ||
592 | EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi) | |
593 | { | |
594 | /* If this is a properly sized variable, only add offset if it's | |
595 | less than end. Otherwise, it is globbed to a single | |
596 | variable. */ | |
597 | ||
598 | if ((get_varinfo (i)->offset + offset) < get_varinfo (i)->fullsize) | |
599 | { | |
600 | unsigned HOST_WIDE_INT fieldoffset = get_varinfo (i)->offset + offset; | |
601 | varinfo_t v = first_vi_for_offset (get_varinfo (i), fieldoffset); | |
602 | bitmap_set_bit (result, v->id); | |
603 | } | |
604 | else if (get_varinfo (i)->is_artificial_var | |
605 | || get_varinfo (i)->is_unknown_size_var) | |
606 | { | |
607 | bitmap_set_bit (result, i); | |
608 | } | |
609 | } | |
610 | ||
611 | bitmap_copy (set, result); | |
612 | BITMAP_FREE (result); | |
613 | } | |
614 | ||
615 | /* Union solution sets TO and FROM, and add INC to each member of FROM in the | |
616 | process. */ | |
617 | ||
618 | static bool | |
619 | set_union_with_increment (bitmap to, bitmap from, unsigned HOST_WIDE_INT inc) | |
620 | { | |
621 | if (inc == 0) | |
622 | return bitmap_ior_into (to, from); | |
623 | else | |
624 | { | |
625 | bitmap tmp; | |
626 | bool res; | |
627 | ||
628 | tmp = BITMAP_ALLOC (&iteration_obstack); | |
629 | bitmap_copy (tmp, from); | |
630 | solution_set_add (tmp, inc); | |
631 | res = bitmap_ior_into (to, tmp); | |
632 | BITMAP_FREE (tmp); | |
633 | return res; | |
634 | } | |
635 | } | |
636 | ||
637 | /* Insert constraint C into the list of complex constraints for VAR. */ | |
638 | ||
639 | static void | |
640 | insert_into_complex (unsigned int var, constraint_t c) | |
641 | { | |
642 | varinfo_t vi = get_varinfo (var); | |
643 | unsigned int place = VEC_lower_bound (constraint_t, vi->complex, c, | |
644 | constraint_less); | |
645 | VEC_safe_insert (constraint_t, gc, vi->complex, place, c); | |
646 | } | |
647 | ||
648 | ||
649 | /* Compare two constraint edges A and B, return true if they are equal. */ | |
650 | ||
651 | static bool | |
652 | constraint_edge_equal (struct constraint_edge a, struct constraint_edge b) | |
653 | { | |
654 | return a.src == b.src && a.dest == b.dest; | |
655 | } | |
656 | ||
657 | /* Compare two constraint edges, return true if A is less than B */ | |
658 | ||
659 | static bool | |
660 | constraint_edge_less (const constraint_edge_t a, const constraint_edge_t b) | |
661 | { | |
662 | if (a->dest < b->dest) | |
663 | return true; | |
664 | else if (a->dest == b->dest) | |
665 | return a->src < b->src; | |
666 | else | |
667 | return false; | |
668 | } | |
669 | ||
670 | /* Find the constraint edge that matches LOOKFOR, in VEC. | |
671 | Return the edge, if found, NULL otherwise. */ | |
672 | ||
673 | static constraint_edge_t | |
674 | constraint_edge_vec_find (VEC(constraint_edge_t,gc) *vec, | |
675 | struct constraint_edge lookfor) | |
676 | { | |
677 | unsigned int place; | |
678 | constraint_edge_t edge; | |
679 | ||
680 | place = VEC_lower_bound (constraint_edge_t, vec, &lookfor, | |
681 | constraint_edge_less); | |
682 | edge = VEC_index (constraint_edge_t, vec, place); | |
683 | if (!constraint_edge_equal (*edge, lookfor)) | |
684 | return NULL; | |
685 | return edge; | |
686 | } | |
687 | ||
688 | /* Condense two variable nodes into a single variable node, by moving | |
689 | all associated info from SRC to TO. */ | |
690 | ||
691 | static void | |
692 | condense_varmap_nodes (unsigned int to, unsigned int src) | |
693 | { | |
694 | varinfo_t tovi = get_varinfo (to); | |
695 | varinfo_t srcvi = get_varinfo (src); | |
696 | unsigned int i; | |
697 | constraint_t c; | |
698 | bitmap_iterator bi; | |
699 | ||
700 | /* the src node, and all its variables, are now the to node. */ | |
701 | srcvi->node = to; | |
702 | EXECUTE_IF_SET_IN_BITMAP (srcvi->variables, 0, i, bi) | |
703 | get_varinfo (i)->node = to; | |
704 | ||
705 | /* Merge the src node variables and the to node variables. */ | |
706 | bitmap_set_bit (tovi->variables, src); | |
707 | bitmap_ior_into (tovi->variables, srcvi->variables); | |
708 | bitmap_clear (srcvi->variables); | |
709 | ||
710 | /* Move all complex constraints from src node into to node */ | |
711 | for (i = 0; VEC_iterate (constraint_t, srcvi->complex, i, c); i++) | |
712 | { | |
713 | /* In complex constraints for node src, we may have either | |
714 | a = *src, and *src = a. */ | |
715 | ||
716 | if (c->rhs.type == DEREF) | |
717 | c->rhs.var = to; | |
718 | else | |
719 | c->lhs.var = to; | |
720 | } | |
721 | constraint_set_union (&tovi->complex, &srcvi->complex); | |
722 | srcvi->complex = NULL; | |
723 | } | |
724 | ||
725 | /* Erase EDGE from GRAPH. This routine only handles self-edges | |
726 | (e.g. an edge from a to a). */ | |
727 | ||
728 | static void | |
729 | erase_graph_self_edge (constraint_graph_t graph, struct constraint_edge edge) | |
730 | { | |
731 | VEC(constraint_edge_t,gc) *predvec = graph->preds[edge.src]; | |
732 | VEC(constraint_edge_t,gc) *succvec = graph->succs[edge.dest]; | |
733 | unsigned int place; | |
734 | gcc_assert (edge.src == edge.dest); | |
735 | ||
736 | /* Remove from the successors. */ | |
737 | place = VEC_lower_bound (constraint_edge_t, succvec, &edge, | |
738 | constraint_edge_less); | |
739 | ||
740 | /* Make sure we found the edge. */ | |
741 | #ifdef ENABLE_CHECKING | |
742 | { | |
743 | constraint_edge_t tmp = VEC_index (constraint_edge_t, succvec, place); | |
744 | gcc_assert (constraint_edge_equal (*tmp, edge)); | |
745 | } | |
746 | #endif | |
747 | VEC_ordered_remove (constraint_edge_t, succvec, place); | |
748 | ||
749 | /* Remove from the predecessors. */ | |
750 | place = VEC_lower_bound (constraint_edge_t, predvec, &edge, | |
751 | constraint_edge_less); | |
752 | ||
753 | /* Make sure we found the edge. */ | |
754 | #ifdef ENABLE_CHECKING | |
755 | { | |
756 | constraint_edge_t tmp = VEC_index (constraint_edge_t, predvec, place); | |
757 | gcc_assert (constraint_edge_equal (*tmp, edge)); | |
758 | } | |
759 | #endif | |
760 | VEC_ordered_remove (constraint_edge_t, predvec, place); | |
761 | } | |
762 | ||
763 | /* Remove edges involving NODE from GRAPH. */ | |
764 | ||
765 | static void | |
766 | clear_edges_for_node (constraint_graph_t graph, unsigned int node) | |
767 | { | |
768 | VEC(constraint_edge_t,gc) *succvec = graph->succs[node]; | |
769 | VEC(constraint_edge_t,gc) *predvec = graph->preds[node]; | |
770 | constraint_edge_t c; | |
771 | int i; | |
772 | ||
773 | /* Walk the successors, erase the associated preds. */ | |
774 | for (i = 0; VEC_iterate (constraint_edge_t, succvec, i, c); i++) | |
775 | if (c->dest != node) | |
776 | { | |
777 | unsigned int place; | |
778 | struct constraint_edge lookfor; | |
779 | lookfor.src = c->dest; | |
780 | lookfor.dest = node; | |
781 | place = VEC_lower_bound (constraint_edge_t, graph->preds[c->dest], | |
782 | &lookfor, constraint_edge_less); | |
783 | VEC_ordered_remove (constraint_edge_t, graph->preds[c->dest], place); | |
784 | } | |
785 | /* Walk the preds, erase the associated succs. */ | |
786 | for (i =0; VEC_iterate (constraint_edge_t, predvec, i, c); i++) | |
787 | if (c->dest != node) | |
788 | { | |
789 | unsigned int place; | |
790 | struct constraint_edge lookfor; | |
791 | lookfor.src = c->dest; | |
792 | lookfor.dest = node; | |
793 | place = VEC_lower_bound (constraint_edge_t, graph->succs[c->dest], | |
794 | &lookfor, constraint_edge_less); | |
795 | VEC_ordered_remove (constraint_edge_t, graph->succs[c->dest], place); | |
796 | } | |
797 | ||
798 | graph->preds[node] = NULL; | |
799 | graph->succs[node] = NULL; | |
800 | } | |
801 | ||
802 | static bool edge_added = false; | |
803 | ||
804 | /* Add edge NEWE to the graph. */ | |
805 | ||
806 | static bool | |
807 | add_graph_edge (constraint_graph_t graph, struct constraint_edge newe) | |
808 | { | |
809 | unsigned int place; | |
810 | unsigned int src = newe.src; | |
811 | unsigned int dest = newe.dest; | |
812 | VEC(constraint_edge_t,gc) *vec; | |
813 | ||
814 | vec = graph->preds[src]; | |
815 | place = VEC_lower_bound (constraint_edge_t, vec, &newe, | |
816 | constraint_edge_less); | |
817 | if (place == VEC_length (constraint_edge_t, vec) | |
818 | || VEC_index (constraint_edge_t, vec, place)->dest != dest) | |
819 | { | |
820 | constraint_edge_t edge = new_constraint_edge (src, dest); | |
821 | bitmap weightbitmap; | |
822 | ||
823 | weightbitmap = BITMAP_ALLOC (&ptabitmap_obstack); | |
824 | edge->weights = weightbitmap; | |
825 | VEC_safe_insert (constraint_edge_t, gc, graph->preds[edge->src], | |
826 | place, edge); | |
827 | edge = new_constraint_edge (dest, src); | |
828 | edge->weights = weightbitmap; | |
829 | place = VEC_lower_bound (constraint_edge_t, graph->succs[edge->src], | |
830 | edge, constraint_edge_less); | |
831 | VEC_safe_insert (constraint_edge_t, gc, graph->succs[edge->src], | |
832 | place, edge); | |
833 | edge_added = true; | |
834 | return true; | |
835 | } | |
836 | else | |
837 | return false; | |
838 | } | |
839 | ||
840 | ||
841 | /* Return the bitmap representing the weights of edge LOOKFOR */ | |
842 | ||
843 | static bitmap | |
844 | get_graph_weights (constraint_graph_t graph, struct constraint_edge lookfor) | |
845 | { | |
846 | constraint_edge_t edge; | |
847 | unsigned int src = lookfor.src; | |
848 | VEC(constraint_edge_t,gc) *vec; | |
849 | vec = graph->preds[src]; | |
850 | edge = constraint_edge_vec_find (vec, lookfor); | |
851 | gcc_assert (edge != NULL); | |
852 | return edge->weights; | |
853 | } | |
854 | ||
855 | ||
856 | /* Merge GRAPH nodes FROM and TO into node TO. */ | |
857 | ||
858 | static void | |
859 | merge_graph_nodes (constraint_graph_t graph, unsigned int to, | |
860 | unsigned int from) | |
861 | { | |
862 | VEC(constraint_edge_t,gc) *succvec = graph->succs[from]; | |
863 | VEC(constraint_edge_t,gc) *predvec = graph->preds[from]; | |
864 | int i; | |
865 | constraint_edge_t c; | |
866 | ||
867 | /* Merge all the predecessor edges. */ | |
868 | ||
869 | for (i = 0; VEC_iterate (constraint_edge_t, predvec, i, c); i++) | |
870 | { | |
871 | unsigned int d = c->dest; | |
872 | struct constraint_edge olde; | |
873 | struct constraint_edge newe; | |
874 | bitmap temp; | |
875 | bitmap weights; | |
876 | if (c->dest == from) | |
877 | d = to; | |
878 | newe.src = to; | |
879 | newe.dest = d; | |
880 | add_graph_edge (graph, newe); | |
881 | olde.src = from; | |
882 | olde.dest = c->dest; | |
883 | temp = get_graph_weights (graph, olde); | |
884 | weights = get_graph_weights (graph, newe); | |
885 | bitmap_ior_into (weights, temp); | |
886 | } | |
887 | ||
888 | /* Merge all the successor edges. */ | |
889 | for (i = 0; VEC_iterate (constraint_edge_t, succvec, i, c); i++) | |
890 | { | |
891 | unsigned int d = c->dest; | |
892 | struct constraint_edge olde; | |
893 | struct constraint_edge newe; | |
894 | bitmap temp; | |
895 | bitmap weights; | |
896 | if (c->dest == from) | |
897 | d = to; | |
898 | newe.src = d; | |
899 | newe.dest = to; | |
900 | add_graph_edge (graph, newe); | |
901 | olde.src = c->dest; | |
902 | olde.dest = from; | |
903 | temp = get_graph_weights (graph, olde); | |
904 | weights = get_graph_weights (graph, newe); | |
905 | bitmap_ior_into (weights, temp); | |
906 | } | |
907 | clear_edges_for_node (graph, from); | |
908 | } | |
909 | ||
910 | /* Add a graph edge to GRAPH, going from TO to FROM, with WEIGHT, if | |
911 | it doesn't exist in the graph already. | |
912 | Return false if the edge already existed, true otherwise. */ | |
913 | ||
914 | static bool | |
915 | int_add_graph_edge (constraint_graph_t graph, unsigned int to, | |
916 | unsigned int from, unsigned HOST_WIDE_INT weight) | |
917 | { | |
918 | if (to == from && weight == 0) | |
919 | { | |
920 | return false; | |
921 | } | |
922 | else | |
923 | { | |
924 | bool r; | |
925 | struct constraint_edge edge; | |
926 | edge.src = to; | |
927 | edge.dest = from; | |
928 | r = add_graph_edge (graph, edge); | |
929 | r |= !bitmap_bit_p (get_graph_weights (graph, edge), weight); | |
930 | bitmap_set_bit (get_graph_weights (graph, edge), weight); | |
931 | return r; | |
932 | } | |
933 | } | |
934 | ||
935 | ||
936 | /* Return true if LOOKFOR is an existing graph edge. */ | |
937 | ||
938 | static bool | |
939 | valid_graph_edge (constraint_graph_t graph, struct constraint_edge lookfor) | |
940 | { | |
941 | return constraint_edge_vec_find (graph->preds[lookfor.src], lookfor) != NULL; | |
942 | } | |
943 | ||
944 | ||
945 | /* Build the constraint graph. */ | |
946 | ||
947 | static void | |
948 | build_constraint_graph (void) | |
949 | { | |
950 | int i = 0; | |
951 | constraint_t c; | |
952 | ||
953 | graph = ggc_alloc (sizeof (struct constraint_graph)); | |
e8ca4159 DN |
954 | graph->succs = ggc_alloc_cleared (VEC_length (varinfo_t, varmap) |
955 | * sizeof (*graph->succs)); | |
956 | graph->preds = ggc_alloc_cleared (VEC_length (varinfo_t, varmap) | |
957 | * sizeof (*graph->preds)); | |
958 | ||
910fdc79 DB |
959 | for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++) |
960 | { | |
961 | struct constraint_expr lhs = c->lhs; | |
962 | struct constraint_expr rhs = c->rhs; | |
963 | if (lhs.type == DEREF) | |
964 | { | |
965 | /* *x = y or *x = &y (complex) */ | |
966 | if (rhs.type == ADDRESSOF || rhs.var > anything_id) | |
967 | insert_into_complex (lhs.var, c); | |
968 | } | |
969 | else if (rhs.type == DEREF) | |
970 | { | |
971 | /* !ANYTHING = *y */ | |
972 | if (lhs.var > anything_id) | |
973 | insert_into_complex (rhs.var, c); | |
974 | } | |
975 | else if (rhs.type == ADDRESSOF) | |
976 | { | |
977 | /* x = &y */ | |
978 | bitmap_set_bit (get_varinfo (lhs.var)->solution, rhs.var); | |
979 | } | |
980 | else if (rhs.var > anything_id && lhs.var > anything_id) | |
981 | { | |
982 | /* Ignore 0 weighted self edges, as they can't possibly contribute | |
983 | anything */ | |
984 | if (lhs.var != rhs.var || rhs.offset != 0 || lhs.offset != 0) | |
985 | { | |
986 | ||
987 | struct constraint_edge edge; | |
988 | edge.src = lhs.var; | |
989 | edge.dest = rhs.var; | |
990 | /* x = y (simple) */ | |
991 | add_graph_edge (graph, edge); | |
992 | bitmap_set_bit (get_graph_weights (graph, edge), | |
993 | rhs.offset); | |
994 | } | |
995 | ||
996 | } | |
997 | } | |
998 | } | |
e8ca4159 DN |
999 | |
1000 | ||
910fdc79 DB |
1001 | /* Changed variables on the last iteration. */ |
1002 | static unsigned int changed_count; | |
1003 | static sbitmap changed; | |
1004 | ||
740e80e8 FXC |
1005 | DEF_VEC_I(unsigned); |
1006 | DEF_VEC_ALLOC_I(unsigned,heap); | |
910fdc79 DB |
1007 | |
1008 | ||
1009 | /* Strongly Connected Component visitation info. */ | |
1010 | ||
1011 | struct scc_info | |
1012 | { | |
1013 | sbitmap visited; | |
1014 | sbitmap in_component; | |
1015 | int current_index; | |
1016 | unsigned int *visited_index; | |
740e80e8 FXC |
1017 | VEC(unsigned,heap) *scc_stack; |
1018 | VEC(unsigned,heap) *unification_queue; | |
910fdc79 DB |
1019 | }; |
1020 | ||
1021 | ||
1022 | /* Recursive routine to find strongly connected components in GRAPH. | |
1023 | SI is the SCC info to store the information in, and N is the id of current | |
1024 | graph node we are processing. | |
1025 | ||
1026 | This is Tarjan's strongly connected component finding algorithm, as | |
1027 | modified by Nuutila to keep only non-root nodes on the stack. | |
1028 | The algorithm can be found in "On finding the strongly connected | |
1029 | connected components in a directed graph" by Esko Nuutila and Eljas | |
1030 | Soisalon-Soininen, in Information Processing Letters volume 49, | |
1031 | number 1, pages 9-14. */ | |
1032 | ||
1033 | static void | |
1034 | scc_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n) | |
1035 | { | |
1036 | constraint_edge_t c; | |
1037 | int i; | |
1038 | ||
1039 | gcc_assert (get_varinfo (n)->node == n); | |
1040 | SET_BIT (si->visited, n); | |
1041 | RESET_BIT (si->in_component, n); | |
1042 | si->visited_index[n] = si->current_index ++; | |
1043 | ||
1044 | /* Visit all the successors. */ | |
1045 | for (i = 0; VEC_iterate (constraint_edge_t, graph->succs[n], i, c); i++) | |
1046 | { | |
1047 | /* We only want to find and collapse the zero weight edges. */ | |
1048 | if (bitmap_bit_p (c->weights, 0)) | |
1049 | { | |
1050 | unsigned int w = c->dest; | |
1051 | if (!TEST_BIT (si->visited, w)) | |
1052 | scc_visit (graph, si, w); | |
1053 | if (!TEST_BIT (si->in_component, w)) | |
1054 | { | |
1055 | unsigned int t = get_varinfo (w)->node; | |
1056 | unsigned int nnode = get_varinfo (n)->node; | |
1057 | if (si->visited_index[t] < si->visited_index[nnode]) | |
1058 | get_varinfo (n)->node = t; | |
1059 | } | |
1060 | } | |
1061 | } | |
1062 | ||
1063 | /* See if any components have been identified. */ | |
1064 | if (get_varinfo (n)->node == n) | |
1065 | { | |
1066 | unsigned int t = si->visited_index[n]; | |
1067 | SET_BIT (si->in_component, n); | |
740e80e8 FXC |
1068 | while (VEC_length (unsigned, si->scc_stack) != 0 |
1069 | && t < si->visited_index[VEC_last (unsigned, si->scc_stack)]) | |
910fdc79 | 1070 | { |
740e80e8 | 1071 | unsigned int w = VEC_pop (unsigned, si->scc_stack); |
910fdc79 DB |
1072 | get_varinfo (w)->node = n; |
1073 | SET_BIT (si->in_component, w); | |
1074 | /* Mark this node for collapsing. */ | |
740e80e8 | 1075 | VEC_safe_push (unsigned, heap, si->unification_queue, w); |
910fdc79 DB |
1076 | } |
1077 | } | |
1078 | else | |
740e80e8 | 1079 | VEC_safe_push (unsigned, heap, si->scc_stack, n); |
910fdc79 DB |
1080 | } |
1081 | ||
1082 | ||
1083 | /* Collapse two variables into one variable. */ | |
1084 | ||
1085 | static void | |
1086 | collapse_nodes (constraint_graph_t graph, unsigned int to, unsigned int from) | |
1087 | { | |
1088 | bitmap tosol, fromsol; | |
1089 | struct constraint_edge edge; | |
1090 | ||
1091 | ||
1092 | condense_varmap_nodes (to, from); | |
1093 | tosol = get_varinfo (to)->solution; | |
1094 | fromsol = get_varinfo (from)->solution; | |
1095 | bitmap_ior_into (tosol, fromsol); | |
1096 | merge_graph_nodes (graph, to, from); | |
1097 | edge.src = to; | |
1098 | edge.dest = to; | |
1099 | if (valid_graph_edge (graph, edge)) | |
1100 | { | |
1101 | bitmap weights = get_graph_weights (graph, edge); | |
1102 | bitmap_clear_bit (weights, 0); | |
1103 | if (bitmap_empty_p (weights)) | |
1104 | erase_graph_self_edge (graph, edge); | |
1105 | } | |
1106 | bitmap_clear (fromsol); | |
1107 | get_varinfo (to)->address_taken |= get_varinfo (from)->address_taken; | |
1108 | get_varinfo (to)->indirect_target |= get_varinfo (from)->indirect_target; | |
1109 | } | |
1110 | ||
1111 | ||
1112 | /* Unify nodes in GRAPH that we have found to be part of a cycle. | |
1113 | SI is the Strongly Connected Components information structure that tells us | |
1114 | what components to unify. | |
1115 | UPDATE_CHANGED should be set to true if the changed sbitmap and changed | |
1116 | count should be updated to reflect the unification. */ | |
1117 | ||
1118 | static void | |
1119 | process_unification_queue (constraint_graph_t graph, struct scc_info *si, | |
1120 | bool update_changed) | |
1121 | { | |
1122 | size_t i = 0; | |
1123 | bitmap tmp = BITMAP_ALLOC (update_changed ? &iteration_obstack : NULL); | |
1124 | bitmap_clear (tmp); | |
1125 | ||
1126 | /* We proceed as follows: | |
1127 | ||
1128 | For each component in the queue (components are delineated by | |
1129 | when current_queue_element->node != next_queue_element->node): | |
1130 | ||
1131 | rep = representative node for component | |
1132 | ||
1133 | For each node (tounify) to be unified in the component, | |
1134 | merge the solution for tounify into tmp bitmap | |
1135 | ||
1136 | clear solution for tounify | |
1137 | ||
1138 | merge edges from tounify into rep | |
1139 | ||
1140 | merge complex constraints from tounify into rep | |
1141 | ||
1142 | update changed count to note that tounify will never change | |
1143 | again | |
1144 | ||
1145 | Merge tmp into solution for rep, marking rep changed if this | |
1146 | changed rep's solution. | |
1147 | ||
1148 | Delete any 0 weighted self-edges we now have for rep. */ | |
740e80e8 | 1149 | while (i != VEC_length (unsigned, si->unification_queue)) |
910fdc79 | 1150 | { |
740e80e8 | 1151 | unsigned int tounify = VEC_index (unsigned, si->unification_queue, i); |
910fdc79 DB |
1152 | unsigned int n = get_varinfo (tounify)->node; |
1153 | ||
1154 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1155 | fprintf (dump_file, "Unifying %s to %s\n", | |
1156 | get_varinfo (tounify)->name, | |
1157 | get_varinfo (n)->name); | |
1158 | if (update_changed) | |
1159 | stats.unified_vars_dynamic++; | |
1160 | else | |
1161 | stats.unified_vars_static++; | |
1162 | bitmap_ior_into (tmp, get_varinfo (tounify)->solution); | |
1163 | merge_graph_nodes (graph, n, tounify); | |
1164 | condense_varmap_nodes (n, tounify); | |
1165 | ||
1166 | if (update_changed && TEST_BIT (changed, tounify)) | |
1167 | { | |
1168 | RESET_BIT (changed, tounify); | |
1169 | if (!TEST_BIT (changed, n)) | |
1170 | SET_BIT (changed, n); | |
1171 | else | |
1172 | { | |
1173 | gcc_assert (changed_count > 0); | |
1174 | changed_count--; | |
1175 | } | |
1176 | } | |
1177 | ||
1178 | bitmap_clear (get_varinfo (tounify)->solution); | |
1179 | ++i; | |
1180 | ||
1181 | /* If we've either finished processing the entire queue, or | |
1182 | finished processing all nodes for component n, update the solution for | |
1183 | n. */ | |
740e80e8 FXC |
1184 | if (i == VEC_length (unsigned, si->unification_queue) |
1185 | || get_varinfo (VEC_index (unsigned, si->unification_queue, i))->node != n) | |
910fdc79 DB |
1186 | { |
1187 | struct constraint_edge edge; | |
1188 | ||
1189 | /* If the solution changes because of the merging, we need to mark | |
1190 | the variable as changed. */ | |
1191 | if (bitmap_ior_into (get_varinfo (n)->solution, tmp)) | |
1192 | { | |
1193 | if (update_changed && !TEST_BIT (changed, n)) | |
1194 | { | |
1195 | SET_BIT (changed, n); | |
1196 | changed_count++; | |
1197 | } | |
1198 | } | |
1199 | bitmap_clear (tmp); | |
1200 | edge.src = n; | |
1201 | edge.dest = n; | |
1202 | if (valid_graph_edge (graph, edge)) | |
1203 | { | |
1204 | bitmap weights = get_graph_weights (graph, edge); | |
1205 | bitmap_clear_bit (weights, 0); | |
1206 | if (bitmap_empty_p (weights)) | |
1207 | erase_graph_self_edge (graph, edge); | |
1208 | } | |
1209 | } | |
1210 | } | |
1211 | BITMAP_FREE (tmp); | |
1212 | } | |
1213 | ||
1214 | ||
1215 | /* Information needed to compute the topological ordering of a graph. */ | |
1216 | ||
1217 | struct topo_info | |
1218 | { | |
1219 | /* sbitmap of visited nodes. */ | |
1220 | sbitmap visited; | |
1221 | /* Array that stores the topological order of the graph, *in | |
1222 | reverse*. */ | |
740e80e8 | 1223 | VEC(unsigned,heap) *topo_order; |
910fdc79 DB |
1224 | }; |
1225 | ||
1226 | ||
1227 | /* Initialize and return a topological info structure. */ | |
1228 | ||
1229 | static struct topo_info * | |
1230 | init_topo_info (void) | |
1231 | { | |
1232 | size_t size = VEC_length (varinfo_t, varmap); | |
1233 | struct topo_info *ti = xmalloc (sizeof (struct topo_info)); | |
1234 | ti->visited = sbitmap_alloc (size); | |
1235 | sbitmap_zero (ti->visited); | |
740e80e8 | 1236 | ti->topo_order = VEC_alloc (unsigned, heap, 1); |
910fdc79 DB |
1237 | return ti; |
1238 | } | |
1239 | ||
1240 | ||
1241 | /* Free the topological sort info pointed to by TI. */ | |
1242 | ||
1243 | static void | |
1244 | free_topo_info (struct topo_info *ti) | |
1245 | { | |
1246 | sbitmap_free (ti->visited); | |
740e80e8 | 1247 | VEC_free (unsigned, heap, ti->topo_order); |
910fdc79 DB |
1248 | free (ti); |
1249 | } | |
1250 | ||
1251 | /* Visit the graph in topological order, and store the order in the | |
1252 | topo_info structure. */ | |
1253 | ||
1254 | static void | |
1255 | topo_visit (constraint_graph_t graph, struct topo_info *ti, | |
1256 | unsigned int n) | |
1257 | { | |
1258 | VEC(constraint_edge_t,gc) *succs = graph->succs[n]; | |
1259 | constraint_edge_t c; | |
1260 | int i; | |
1261 | SET_BIT (ti->visited, n); | |
1262 | for (i = 0; VEC_iterate (constraint_edge_t, succs, i, c); i++) | |
1263 | { | |
1264 | if (!TEST_BIT (ti->visited, c->dest)) | |
1265 | topo_visit (graph, ti, c->dest); | |
1266 | } | |
740e80e8 | 1267 | VEC_safe_push (unsigned, heap, ti->topo_order, n); |
910fdc79 DB |
1268 | } |
1269 | ||
1270 | /* Return true if variable N + OFFSET is a legal field of N. */ | |
1271 | ||
1272 | static bool | |
1273 | type_safe (unsigned int n, unsigned HOST_WIDE_INT *offset) | |
1274 | { | |
1275 | varinfo_t ninfo = get_varinfo (n); | |
1276 | ||
1277 | /* For things we've globbed to single variables, any offset into the | |
1278 | variable acts like the entire variable, so that it becomes offset | |
1279 | 0. */ | |
1280 | if (n == anything_id | |
1281 | || ninfo->is_artificial_var | |
1282 | || ninfo->is_unknown_size_var) | |
1283 | { | |
1284 | *offset = 0; | |
1285 | return true; | |
1286 | } | |
1287 | return n > anything_id | |
1288 | && (get_varinfo (n)->offset + *offset) < get_varinfo (n)->fullsize; | |
1289 | } | |
1290 | ||
1291 | /* Process a constraint C that represents *x = &y. */ | |
1292 | ||
1293 | static void | |
1294 | do_da_constraint (constraint_graph_t graph ATTRIBUTE_UNUSED, | |
1295 | constraint_t c, bitmap delta) | |
1296 | { | |
1297 | unsigned int rhs = c->rhs.var; | |
1298 | unsigned HOST_WIDE_INT offset = c->lhs.offset; | |
1299 | unsigned int j; | |
1300 | bitmap_iterator bi; | |
1301 | ||
1302 | /* For each member j of Delta (Sol(x)), add x to Sol(j) */ | |
1303 | EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi) | |
1304 | { | |
1305 | if (type_safe (j, &offset)) | |
1306 | { | |
1307 | /* *x != NULL && *x != ANYTHING*/ | |
1308 | varinfo_t v; | |
1309 | unsigned int t; | |
1310 | bitmap sol; | |
1311 | unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + offset; | |
1312 | v = first_vi_for_offset (get_varinfo (j), fieldoffset); | |
1313 | t = v->node; | |
1314 | sol = get_varinfo (t)->solution; | |
1315 | if (!bitmap_bit_p (sol, rhs)) | |
1316 | { | |
1317 | bitmap_set_bit (sol, rhs); | |
1318 | if (!TEST_BIT (changed, t)) | |
1319 | { | |
1320 | SET_BIT (changed, t); | |
1321 | changed_count++; | |
1322 | } | |
1323 | } | |
1324 | } | |
1325 | else if (dump_file) | |
1326 | fprintf (dump_file, "Untypesafe usage in do_da_constraint.\n"); | |
1327 | ||
1328 | } | |
1329 | } | |
1330 | ||
1331 | /* Process a constraint C that represents x = *y, using DELTA as the | |
1332 | starting solution. */ | |
1333 | ||
1334 | static void | |
1335 | do_sd_constraint (constraint_graph_t graph, constraint_t c, | |
1336 | bitmap delta) | |
1337 | { | |
1338 | unsigned int lhs = get_varinfo (c->lhs.var)->node; | |
1339 | unsigned HOST_WIDE_INT roffset = c->rhs.offset; | |
1340 | bool flag = false; | |
1341 | bitmap sol = get_varinfo (lhs)->solution; | |
1342 | unsigned int j; | |
1343 | bitmap_iterator bi; | |
1344 | ||
1345 | /* For each variable j in delta (Sol(y)), add | |
1346 | an edge in the graph from j to x, and union Sol(j) into Sol(x). */ | |
1347 | EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi) | |
1348 | { | |
1349 | if (type_safe (j, &roffset)) | |
1350 | { | |
1351 | varinfo_t v; | |
1352 | unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + roffset; | |
1353 | unsigned int t; | |
1354 | ||
1355 | v = first_vi_for_offset (get_varinfo (j), fieldoffset); | |
1356 | t = v->node; | |
1357 | if (int_add_graph_edge (graph, lhs, t, 0)) | |
1358 | flag |= bitmap_ior_into (sol, get_varinfo (t)->solution); | |
1359 | } | |
1360 | else if (dump_file) | |
1361 | fprintf (dump_file, "Untypesafe usage in do_sd_constraint\n"); | |
1362 | ||
1363 | } | |
1364 | ||
1365 | /* If the LHS solution changed, mark the var as changed. */ | |
1366 | if (flag) | |
1367 | { | |
1368 | get_varinfo (lhs)->solution = sol; | |
1369 | if (!TEST_BIT (changed, lhs)) | |
1370 | { | |
1371 | SET_BIT (changed, lhs); | |
1372 | changed_count++; | |
1373 | } | |
1374 | } | |
1375 | } | |
1376 | ||
1377 | /* Process a constraint C that represents *x = y. */ | |
1378 | ||
1379 | static void | |
1380 | do_ds_constraint (constraint_graph_t graph, constraint_t c, bitmap delta) | |
1381 | { | |
1382 | unsigned int rhs = get_varinfo (c->rhs.var)->node; | |
1383 | unsigned HOST_WIDE_INT loff = c->lhs.offset; | |
1384 | unsigned HOST_WIDE_INT roff = c->rhs.offset; | |
1385 | bitmap sol = get_varinfo (rhs)->solution; | |
1386 | unsigned int j; | |
1387 | bitmap_iterator bi; | |
1388 | ||
1389 | /* For each member j of delta (Sol(x)), add an edge from y to j and | |
1390 | union Sol(y) into Sol(j) */ | |
1391 | EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi) | |
1392 | { | |
1393 | if (type_safe (j, &loff)) | |
1394 | { | |
1395 | varinfo_t v; | |
1396 | unsigned int t; | |
1397 | unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + loff; | |
1398 | ||
1399 | v = first_vi_for_offset (get_varinfo (j), fieldoffset); | |
1400 | t = v->node; | |
1401 | if (int_add_graph_edge (graph, t, rhs, roff)) | |
1402 | { | |
1403 | bitmap tmp = get_varinfo (t)->solution; | |
1404 | if (set_union_with_increment (tmp, sol, roff)) | |
1405 | { | |
1406 | get_varinfo (t)->solution = tmp; | |
1407 | if (t == rhs) | |
1408 | { | |
1409 | sol = get_varinfo (rhs)->solution; | |
1410 | } | |
1411 | if (!TEST_BIT (changed, t)) | |
1412 | { | |
1413 | SET_BIT (changed, t); | |
1414 | changed_count++; | |
1415 | } | |
1416 | } | |
1417 | } | |
1418 | } | |
1419 | else if (dump_file) | |
1420 | fprintf (dump_file, "Untypesafe usage in do_ds_constraint\n"); | |
1421 | } | |
1422 | } | |
1423 | ||
1424 | /* Handle a non-simple (simple meaning requires no iteration), non-copy | |
1425 | constraint (IE *x = &y, x = *y, and *x = y). */ | |
1426 | ||
1427 | static void | |
1428 | do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta) | |
1429 | { | |
1430 | if (c->lhs.type == DEREF) | |
1431 | { | |
1432 | if (c->rhs.type == ADDRESSOF) | |
1433 | { | |
1434 | /* *x = &y */ | |
1435 | do_da_constraint (graph, c, delta); | |
1436 | } | |
1437 | else | |
1438 | { | |
1439 | /* *x = y */ | |
1440 | do_ds_constraint (graph, c, delta); | |
1441 | } | |
1442 | } | |
1443 | else | |
1444 | { | |
1445 | /* x = *y */ | |
1446 | do_sd_constraint (graph, c, delta); | |
1447 | } | |
1448 | } | |
1449 | ||
1450 | /* Initialize and return a new SCC info structure. */ | |
1451 | ||
1452 | static struct scc_info * | |
1453 | init_scc_info (void) | |
1454 | { | |
1455 | struct scc_info *si = xmalloc (sizeof (struct scc_info)); | |
1456 | size_t size = VEC_length (varinfo_t, varmap); | |
1457 | ||
1458 | si->current_index = 0; | |
1459 | si->visited = sbitmap_alloc (size); | |
1460 | sbitmap_zero (si->visited); | |
1461 | si->in_component = sbitmap_alloc (size); | |
1462 | sbitmap_ones (si->in_component); | |
1463 | si->visited_index = xcalloc (sizeof (unsigned int), size + 1); | |
740e80e8 FXC |
1464 | si->scc_stack = VEC_alloc (unsigned, heap, 1); |
1465 | si->unification_queue = VEC_alloc (unsigned, heap, 1); | |
910fdc79 DB |
1466 | return si; |
1467 | } | |
1468 | ||
1469 | /* Free an SCC info structure pointed to by SI */ | |
1470 | ||
1471 | static void | |
1472 | free_scc_info (struct scc_info *si) | |
1473 | { | |
1474 | sbitmap_free (si->visited); | |
1475 | sbitmap_free (si->in_component); | |
1476 | free (si->visited_index); | |
740e80e8 FXC |
1477 | VEC_free (unsigned, heap, si->scc_stack); |
1478 | VEC_free (unsigned, heap, si->unification_queue); | |
910fdc79 DB |
1479 | free(si); |
1480 | } | |
1481 | ||
1482 | ||
1483 | /* Find cycles in GRAPH that occur, using strongly connected components, and | |
1484 | collapse the cycles into a single representative node. if UPDATE_CHANGED | |
1485 | is true, then update the changed sbitmap to note those nodes whose | |
1486 | solutions have changed as a result of collapsing. */ | |
1487 | ||
1488 | static void | |
1489 | find_and_collapse_graph_cycles (constraint_graph_t graph, bool update_changed) | |
1490 | { | |
1491 | unsigned int i; | |
1492 | unsigned int size = VEC_length (varinfo_t, varmap); | |
1493 | struct scc_info *si = init_scc_info (); | |
1494 | ||
1495 | for (i = 0; i != size; ++i) | |
1496 | if (!TEST_BIT (si->visited, i) && get_varinfo (i)->node == i) | |
1497 | scc_visit (graph, si, i); | |
1498 | process_unification_queue (graph, si, update_changed); | |
1499 | free_scc_info (si); | |
1500 | } | |
1501 | ||
1502 | /* Compute a topological ordering for GRAPH, and store the result in the | |
1503 | topo_info structure TI. */ | |
1504 | ||
1505 | static void | |
1506 | compute_topo_order (constraint_graph_t graph, | |
1507 | struct topo_info *ti) | |
1508 | { | |
1509 | unsigned int i; | |
1510 | unsigned int size = VEC_length (varinfo_t, varmap); | |
1511 | ||
1512 | for (i = 0; i != size; ++i) | |
1513 | if (!TEST_BIT (ti->visited, i) && get_varinfo (i)->node == i) | |
1514 | topo_visit (graph, ti, i); | |
1515 | } | |
1516 | ||
1517 | /* Return true if bitmap B is empty, or a bitmap other than bit 0 is set. */ | |
1518 | ||
1519 | static bool | |
1520 | bitmap_other_than_zero_bit_set (bitmap b) | |
1521 | { | |
1522 | unsigned int i; | |
1523 | bitmap_iterator bi; | |
1524 | ||
1525 | if (bitmap_empty_p (b)) | |
1526 | return false; | |
1527 | EXECUTE_IF_SET_IN_BITMAP (b, 1, i, bi) | |
1528 | return true; | |
1529 | return false; | |
1530 | } | |
1531 | ||
1532 | /* Perform offline variable substitution. | |
1533 | ||
1534 | This is a linear time way of identifying variables that must have | |
1535 | equivalent points-to sets, including those caused by static cycles, | |
1536 | and single entry subgraphs, in the constraint graph. | |
1537 | ||
1538 | The technique is described in "Off-line variable substitution for | |
1539 | scaling points-to analysis" by Atanas Rountev and Satish Chandra, | |
1540 | in "ACM SIGPLAN Notices" volume 35, number 5, pages 47-56. */ | |
1541 | ||
1542 | static void | |
1543 | perform_var_substitution (constraint_graph_t graph) | |
1544 | { | |
1545 | struct topo_info *ti = init_topo_info (); | |
1546 | ||
1547 | /* Compute the topological ordering of the graph, then visit each | |
1548 | node in topological order. */ | |
1549 | compute_topo_order (graph, ti); | |
1550 | ||
740e80e8 | 1551 | while (VEC_length (unsigned, ti->topo_order) != 0) |
910fdc79 | 1552 | { |
740e80e8 | 1553 | unsigned int i = VEC_pop (unsigned, ti->topo_order); |
910fdc79 DB |
1554 | unsigned int pred; |
1555 | varinfo_t vi = get_varinfo (i); | |
1556 | bool okay_to_elim = false; | |
1557 | unsigned int root = VEC_length (varinfo_t, varmap); | |
1558 | VEC(constraint_edge_t,gc) *predvec = graph->preds[i]; | |
1559 | constraint_edge_t ce; | |
1560 | bitmap tmp; | |
1561 | ||
1562 | /* We can't eliminate things whose address is taken, or which is | |
1563 | the target of a dereference. */ | |
1564 | if (vi->address_taken || vi->indirect_target) | |
1565 | continue; | |
1566 | ||
1567 | /* See if all predecessors of I are ripe for elimination */ | |
1568 | for (pred = 0; VEC_iterate (constraint_edge_t, predvec, pred, ce); pred++) | |
1569 | { | |
1570 | bitmap weight; | |
1571 | unsigned int w; | |
1572 | weight = get_graph_weights (graph, *ce); | |
1573 | ||
1574 | /* We can't eliminate variables that have non-zero weighted | |
1575 | edges between them. */ | |
1576 | if (bitmap_other_than_zero_bit_set (weight)) | |
1577 | { | |
1578 | okay_to_elim = false; | |
1579 | break; | |
1580 | } | |
1581 | w = get_varinfo (ce->dest)->node; | |
1582 | ||
1583 | /* We can't eliminate the node if one of the predecessors is | |
1584 | part of a different strongly connected component. */ | |
1585 | if (!okay_to_elim) | |
1586 | { | |
1587 | root = w; | |
1588 | okay_to_elim = true; | |
1589 | } | |
1590 | else if (w != root) | |
1591 | { | |
1592 | okay_to_elim = false; | |
1593 | break; | |
1594 | } | |
1595 | ||
1596 | /* Theorem 4 in Rountev and Chandra: If i is a direct node, | |
1597 | then Solution(i) is a subset of Solution (w), where w is a | |
1598 | predecessor in the graph. | |
607fb860 | 1599 | Corollary: If all predecessors of i have the same |
910fdc79 DB |
1600 | points-to set, then i has that same points-to set as |
1601 | those predecessors. */ | |
1602 | tmp = BITMAP_ALLOC (NULL); | |
1603 | bitmap_and_compl (tmp, get_varinfo (i)->solution, | |
1604 | get_varinfo (w)->solution); | |
1605 | if (!bitmap_empty_p (tmp)) | |
1606 | { | |
1607 | okay_to_elim = false; | |
1608 | BITMAP_FREE (tmp); | |
1609 | break; | |
1610 | } | |
1611 | BITMAP_FREE (tmp); | |
1612 | } | |
1613 | ||
1614 | /* See if the root is different than the original node. | |
1615 | If so, we've found an equivalence. */ | |
1616 | if (root != get_varinfo (i)->node && okay_to_elim) | |
1617 | { | |
1618 | /* Found an equivalence */ | |
1619 | get_varinfo (i)->node = root; | |
1620 | collapse_nodes (graph, root, i); | |
1621 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1622 | fprintf (dump_file, "Collapsing %s into %s\n", | |
1623 | get_varinfo (i)->name, | |
1624 | get_varinfo (root)->name); | |
1625 | stats.collapsed_vars++; | |
1626 | } | |
1627 | } | |
1628 | ||
1629 | free_topo_info (ti); | |
1630 | } | |
1631 | ||
1632 | ||
1633 | /* Solve the constraint graph GRAPH using our worklist solver. | |
1634 | This is based on the PW* family of solvers from the "Efficient Field | |
1635 | Sensitive Pointer Analysis for C" paper. | |
1636 | It works by iterating over all the graph nodes, processing the complex | |
1637 | constraints and propagating the copy constraints, until everything stops | |
1638 | changed. This corresponds to steps 6-8 in the solving list given above. */ | |
1639 | ||
1640 | static void | |
1641 | solve_graph (constraint_graph_t graph) | |
1642 | { | |
1643 | unsigned int size = VEC_length (varinfo_t, varmap); | |
1644 | unsigned int i; | |
1645 | ||
1646 | changed_count = size; | |
1647 | changed = sbitmap_alloc (size); | |
1648 | sbitmap_ones (changed); | |
1649 | ||
1650 | /* The already collapsed/unreachable nodes will never change, so we | |
1651 | need to account for them in changed_count. */ | |
1652 | for (i = 0; i < size; i++) | |
1653 | if (get_varinfo (i)->node != i) | |
1654 | changed_count--; | |
1655 | ||
1656 | while (changed_count > 0) | |
1657 | { | |
1658 | unsigned int i; | |
1659 | struct topo_info *ti = init_topo_info (); | |
1660 | stats.iterations++; | |
1661 | ||
1662 | bitmap_obstack_initialize (&iteration_obstack); | |
1663 | ||
1664 | if (edge_added) | |
1665 | { | |
1666 | /* We already did cycle elimination once, when we did | |
1667 | variable substitution, so we don't need it again for the | |
1668 | first iteration. */ | |
1669 | if (stats.iterations > 1) | |
1670 | find_and_collapse_graph_cycles (graph, true); | |
1671 | ||
1672 | edge_added = false; | |
1673 | } | |
1674 | ||
1675 | compute_topo_order (graph, ti); | |
1676 | ||
740e80e8 | 1677 | while (VEC_length (unsigned, ti->topo_order) != 0) |
910fdc79 | 1678 | { |
740e80e8 | 1679 | i = VEC_pop (unsigned, ti->topo_order); |
910fdc79 DB |
1680 | gcc_assert (get_varinfo (i)->node == i); |
1681 | ||
1682 | /* If the node has changed, we need to process the | |
1683 | complex constraints and outgoing edges again. */ | |
1684 | if (TEST_BIT (changed, i)) | |
1685 | { | |
1686 | unsigned int j; | |
1687 | constraint_t c; | |
1688 | constraint_edge_t e; | |
1689 | bitmap solution; | |
1690 | VEC(constraint_t,gc) *complex = get_varinfo (i)->complex; | |
1691 | VEC(constraint_edge_t,gc) *succs; | |
1692 | ||
1693 | RESET_BIT (changed, i); | |
1694 | changed_count--; | |
1695 | ||
1696 | /* Process the complex constraints */ | |
1697 | solution = get_varinfo (i)->solution; | |
1698 | for (j = 0; VEC_iterate (constraint_t, complex, j, c); j++) | |
1699 | do_complex_constraint (graph, c, solution); | |
1700 | ||
1701 | /* Propagate solution to all successors. */ | |
1702 | succs = graph->succs[i]; | |
1703 | for (j = 0; VEC_iterate (constraint_edge_t, succs, j, e); j++) | |
1704 | { | |
1705 | bitmap tmp = get_varinfo (e->dest)->solution; | |
1706 | bool flag = false; | |
1707 | unsigned int k; | |
1708 | bitmap weights = e->weights; | |
1709 | bitmap_iterator bi; | |
1710 | ||
1711 | gcc_assert (!bitmap_empty_p (weights)); | |
1712 | EXECUTE_IF_SET_IN_BITMAP (weights, 0, k, bi) | |
1713 | flag |= set_union_with_increment (tmp, solution, k); | |
1714 | ||
1715 | if (flag) | |
1716 | { | |
1717 | get_varinfo (e->dest)->solution = tmp; | |
1718 | if (!TEST_BIT (changed, e->dest)) | |
1719 | { | |
1720 | SET_BIT (changed, e->dest); | |
1721 | changed_count++; | |
1722 | } | |
1723 | } | |
1724 | } | |
1725 | } | |
1726 | } | |
1727 | free_topo_info (ti); | |
1728 | bitmap_obstack_release (&iteration_obstack); | |
1729 | } | |
1730 | ||
1731 | sbitmap_free (changed); | |
1732 | } | |
1733 | ||
1734 | ||
1735 | /* CONSTRAINT AND VARIABLE GENERATION FUNCTIONS */ | |
1736 | ||
1737 | /* Map from trees to variable ids. */ | |
1738 | static htab_t id_for_tree; | |
1739 | ||
1740 | typedef struct tree_id | |
1741 | { | |
1742 | tree t; | |
1743 | unsigned int id; | |
1744 | } *tree_id_t; | |
1745 | ||
1746 | /* Hash a tree id structure. */ | |
1747 | ||
1748 | static hashval_t | |
1749 | tree_id_hash (const void *p) | |
1750 | { | |
1751 | const tree_id_t ta = (tree_id_t) p; | |
1752 | return htab_hash_pointer (ta->t); | |
1753 | } | |
1754 | ||
1755 | /* Return true if the tree in P1 and the tree in P2 are the same. */ | |
1756 | ||
1757 | static int | |
1758 | tree_id_eq (const void *p1, const void *p2) | |
1759 | { | |
1760 | const tree_id_t ta1 = (tree_id_t) p1; | |
1761 | const tree_id_t ta2 = (tree_id_t) p2; | |
1762 | return ta1->t == ta2->t; | |
1763 | } | |
1764 | ||
1765 | /* Insert ID as the variable id for tree T in the hashtable. */ | |
1766 | ||
1767 | static void | |
1768 | insert_id_for_tree (tree t, int id) | |
1769 | { | |
1770 | void **slot; | |
1771 | struct tree_id finder; | |
1772 | tree_id_t new_pair; | |
1773 | ||
1774 | finder.t = t; | |
1775 | slot = htab_find_slot (id_for_tree, &finder, INSERT); | |
1776 | gcc_assert (*slot == NULL); | |
1777 | new_pair = xmalloc (sizeof (struct tree_id)); | |
1778 | new_pair->t = t; | |
1779 | new_pair->id = id; | |
1780 | *slot = (void *)new_pair; | |
1781 | } | |
1782 | ||
1783 | /* Find the variable id for tree T in ID_FOR_TREE. If T does not | |
1784 | exist in the hash table, return false, otherwise, return true and | |
1785 | set *ID to the id we found. */ | |
1786 | ||
1787 | static bool | |
1788 | lookup_id_for_tree (tree t, unsigned int *id) | |
1789 | { | |
1790 | tree_id_t pair; | |
1791 | struct tree_id finder; | |
1792 | ||
1793 | finder.t = t; | |
1794 | pair = htab_find (id_for_tree, &finder); | |
1795 | if (pair == NULL) | |
1796 | return false; | |
1797 | *id = pair->id; | |
1798 | return true; | |
1799 | } | |
1800 | ||
1801 | /* Return a printable name for DECL */ | |
1802 | ||
1803 | static const char * | |
1804 | alias_get_name (tree decl) | |
1805 | { | |
1806 | const char *res = get_name (decl); | |
1807 | char *temp; | |
1808 | int num_printed = 0; | |
1809 | ||
1810 | if (res != NULL) | |
1811 | return res; | |
1812 | ||
1813 | res = "NULL"; | |
1814 | if (TREE_CODE (decl) == SSA_NAME) | |
1815 | { | |
1816 | num_printed = asprintf (&temp, "%s_%u", | |
1817 | alias_get_name (SSA_NAME_VAR (decl)), | |
1818 | SSA_NAME_VERSION (decl)); | |
1819 | } | |
1820 | else if (DECL_P (decl)) | |
1821 | { | |
1822 | num_printed = asprintf (&temp, "D.%u", DECL_UID (decl)); | |
1823 | } | |
1824 | if (num_printed > 0) | |
1825 | { | |
1826 | res = ggc_strdup (temp); | |
1827 | free (temp); | |
1828 | } | |
1829 | return res; | |
1830 | } | |
1831 | ||
1832 | /* Find the variable id for tree T in the hashtable. | |
1833 | If T doesn't exist in the hash table, create an entry for it. */ | |
1834 | ||
1835 | static unsigned int | |
1836 | get_id_for_tree (tree t) | |
1837 | { | |
1838 | tree_id_t pair; | |
1839 | struct tree_id finder; | |
1840 | ||
1841 | finder.t = t; | |
1842 | pair = htab_find (id_for_tree, &finder); | |
1843 | if (pair == NULL) | |
1844 | return create_variable_info_for (t, alias_get_name (t)); | |
1845 | ||
1846 | return pair->id; | |
1847 | } | |
1848 | ||
1849 | /* Get a constraint expression from an SSA_VAR_P node. */ | |
1850 | ||
1851 | static struct constraint_expr | |
1852 | get_constraint_exp_from_ssa_var (tree t) | |
1853 | { | |
1854 | struct constraint_expr cexpr; | |
1855 | ||
1856 | gcc_assert (SSA_VAR_P (t) || DECL_P (t)); | |
1857 | ||
1858 | /* For parameters, get at the points-to set for the actual parm | |
1859 | decl. */ | |
1860 | if (TREE_CODE (t) == SSA_NAME | |
1861 | && TREE_CODE (SSA_NAME_VAR (t)) == PARM_DECL | |
1862 | && default_def (SSA_NAME_VAR (t)) == t) | |
1863 | return get_constraint_exp_from_ssa_var (SSA_NAME_VAR (t)); | |
1864 | ||
1865 | cexpr.type = SCALAR; | |
1866 | ||
47bcb538 DB |
1867 | cexpr.var = get_id_for_tree (t); |
1868 | /* If we determine the result is "anything", and we know this is readonly, | |
1869 | say it points to readonly memory instead. */ | |
1870 | if (cexpr.var == anything_id && TREE_READONLY (t)) | |
910fdc79 DB |
1871 | { |
1872 | cexpr.type = ADDRESSOF; | |
1873 | cexpr.var = readonly_id; | |
1874 | } | |
910fdc79 DB |
1875 | |
1876 | cexpr.offset = 0; | |
1877 | return cexpr; | |
1878 | } | |
1879 | ||
1880 | /* Process a completed constraint T, and add it to the constraint | |
1881 | list. */ | |
1882 | ||
1883 | static void | |
1884 | process_constraint (constraint_t t) | |
1885 | { | |
1886 | struct constraint_expr rhs = t->rhs; | |
1887 | struct constraint_expr lhs = t->lhs; | |
1888 | ||
1889 | gcc_assert (rhs.var < VEC_length (varinfo_t, varmap)); | |
1890 | gcc_assert (lhs.var < VEC_length (varinfo_t, varmap)); | |
1891 | ||
1892 | /* ANYTHING == ANYTHING is pointless. */ | |
1893 | if (lhs.var == anything_id && rhs.var == anything_id) | |
1894 | return; | |
1895 | ||
1896 | /* If we have &ANYTHING = something, convert to SOMETHING = &ANYTHING) */ | |
1897 | else if (lhs.var == anything_id && lhs.type == ADDRESSOF) | |
1898 | { | |
1899 | rhs = t->lhs; | |
1900 | t->lhs = t->rhs; | |
1901 | t->rhs = rhs; | |
1902 | process_constraint (t); | |
1903 | } | |
1904 | /* This can happen in our IR with things like n->a = *p */ | |
1905 | else if (rhs.type == DEREF && lhs.type == DEREF && rhs.var != anything_id) | |
1906 | { | |
1907 | /* Split into tmp = *rhs, *lhs = tmp */ | |
1908 | tree rhsdecl = get_varinfo (rhs.var)->decl; | |
1909 | tree pointertype = TREE_TYPE (rhsdecl); | |
1910 | tree pointedtotype = TREE_TYPE (pointertype); | |
1911 | tree tmpvar = create_tmp_var_raw (pointedtotype, "doubledereftmp"); | |
1912 | struct constraint_expr tmplhs = get_constraint_exp_from_ssa_var (tmpvar); | |
1913 | ||
1914 | /* If this is an aggregate of known size, we should have passed | |
1915 | this off to do_structure_copy, and it should have broken it | |
1916 | up. */ | |
1917 | gcc_assert (!AGGREGATE_TYPE_P (pointedtotype) | |
1918 | || get_varinfo (rhs.var)->is_unknown_size_var); | |
1919 | ||
1920 | process_constraint (new_constraint (tmplhs, rhs)); | |
1921 | process_constraint (new_constraint (lhs, tmplhs)); | |
1922 | } | |
1923 | else if (rhs.type == ADDRESSOF) | |
1924 | { | |
1925 | varinfo_t vi; | |
1926 | gcc_assert (rhs.offset == 0); | |
1927 | ||
1928 | for (vi = get_varinfo (rhs.var); vi != NULL; vi = vi->next) | |
1929 | vi->address_taken = true; | |
1930 | ||
1931 | VEC_safe_push (constraint_t, gc, constraints, t); | |
1932 | } | |
1933 | else | |
1934 | { | |
1935 | if (lhs.type != DEREF && rhs.type == DEREF) | |
1936 | get_varinfo (lhs.var)->indirect_target = true; | |
1937 | VEC_safe_push (constraint_t, gc, constraints, t); | |
1938 | } | |
1939 | } | |
1940 | ||
1941 | ||
1942 | /* Return the position, in bits, of FIELD_DECL from the beginning of its | |
1943 | structure. */ | |
1944 | ||
1945 | static unsigned HOST_WIDE_INT | |
1946 | bitpos_of_field (const tree fdecl) | |
1947 | { | |
1948 | ||
1949 | if (TREE_CODE (DECL_FIELD_OFFSET (fdecl)) != INTEGER_CST | |
1950 | || TREE_CODE (DECL_FIELD_BIT_OFFSET (fdecl)) != INTEGER_CST) | |
1951 | return -1; | |
1952 | ||
1953 | return (tree_low_cst (DECL_FIELD_OFFSET (fdecl), 1) * 8) | |
1954 | + tree_low_cst (DECL_FIELD_BIT_OFFSET (fdecl), 1); | |
1955 | } | |
1956 | ||
1957 | ||
dd68d988 DB |
1958 | /* Return true if an access to [ACCESSPOS, ACCESSSIZE] |
1959 | overlaps with a field at [FIELDPOS, FIELDSIZE] */ | |
1960 | ||
1961 | static bool | |
1962 | offset_overlaps_with_access (const unsigned HOST_WIDE_INT fieldpos, | |
1963 | const unsigned HOST_WIDE_INT fieldsize, | |
1964 | const unsigned HOST_WIDE_INT accesspos, | |
1965 | const unsigned HOST_WIDE_INT accesssize) | |
1966 | { | |
1967 | if (fieldpos == accesspos && fieldsize == accesssize) | |
1968 | return true; | |
2238c11d | 1969 | if (accesspos >= fieldpos && accesspos < (fieldpos + fieldsize)) |
dd68d988 DB |
1970 | return true; |
1971 | if (accesspos < fieldpos && (accesspos + accesssize > fieldpos)) | |
1972 | return true; | |
1973 | ||
1974 | return false; | |
1975 | } | |
1976 | ||
910fdc79 DB |
1977 | /* Given a COMPONENT_REF T, return the constraint_expr for it. */ |
1978 | ||
1979 | static struct constraint_expr | |
1980 | get_constraint_for_component_ref (tree t) | |
1981 | { | |
1982 | struct constraint_expr result; | |
1983 | HOST_WIDE_INT bitsize; | |
1984 | HOST_WIDE_INT bitpos; | |
1985 | tree offset; | |
1986 | enum machine_mode mode; | |
1987 | int unsignedp; | |
1988 | int volatilep; | |
1989 | tree forzero; | |
1990 | ||
1991 | result.offset = 0; | |
1992 | result.type = SCALAR; | |
1993 | result.var = 0; | |
1994 | ||
1995 | /* Some people like to do cute things like take the address of | |
1996 | &0->a.b */ | |
1997 | forzero = t; | |
1998 | while (!SSA_VAR_P (forzero) && !CONSTANT_CLASS_P (forzero)) | |
1999 | forzero = TREE_OPERAND (forzero, 0); | |
2000 | ||
2001 | if (CONSTANT_CLASS_P (forzero) && integer_zerop (forzero)) | |
2002 | { | |
2003 | result.offset = 0; | |
2004 | result.var = integer_id; | |
2005 | result.type = SCALAR; | |
2006 | return result; | |
2007 | } | |
2008 | ||
2009 | t = get_inner_reference (t, &bitsize, &bitpos, &offset, &mode, | |
2010 | &unsignedp, &volatilep, false); | |
2011 | result = get_constraint_for (t); | |
2012 | ||
2013 | /* This can also happen due to weird offsetof type macros. */ | |
2014 | if (TREE_CODE (t) != ADDR_EXPR && result.type == ADDRESSOF) | |
2015 | result.type = SCALAR; | |
2016 | ||
2017 | /* If we know where this goes, then yay. Otherwise, booo. */ | |
2018 | ||
2019 | if (offset == NULL && bitsize != -1) | |
2020 | { | |
2021 | result.offset = bitpos; | |
2022 | } | |
2023 | else | |
2024 | { | |
2025 | result.var = anything_id; | |
2026 | result.offset = 0; | |
2027 | } | |
2028 | ||
2029 | if (result.type == SCALAR) | |
2030 | { | |
2031 | /* In languages like C, you can access one past the end of an | |
2032 | array. You aren't allowed to dereference it, so we can | |
2033 | ignore this constraint. When we handle pointer subtraction, | |
2034 | we may have to do something cute here. */ | |
2035 | ||
2036 | if (result.offset < get_varinfo (result.var)->fullsize) | |
dd68d988 DB |
2037 | { |
2038 | /* It's also not true that the constraint will actually start at the | |
2039 | right offset, it may start in some padding. We only care about | |
2040 | setting the constraint to the first actual field it touches, so | |
2041 | walk to find it. */ | |
2042 | varinfo_t curr; | |
2043 | for (curr = get_varinfo (result.var); curr; curr = curr->next) | |
2044 | { | |
2045 | if (offset_overlaps_with_access (curr->offset, curr->size, | |
2046 | result.offset, bitsize)) | |
2047 | { | |
2048 | result.var = curr->id; | |
2049 | break; | |
2050 | ||
2051 | } | |
2052 | } | |
2053 | /* assert that we found *some* field there. The user couldn't be | |
2054 | accessing *only* padding. */ | |
2055 | ||
2056 | gcc_assert (curr); | |
2057 | } | |
910fdc79 DB |
2058 | else |
2059 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
2060 | fprintf (dump_file, "Access to past the end of variable, ignoring\n"); | |
2061 | ||
2062 | result.offset = 0; | |
2063 | } | |
2064 | ||
2065 | return result; | |
2066 | } | |
2067 | ||
2068 | ||
2069 | /* Dereference the constraint expression CONS, and return the result. | |
2070 | DEREF (ADDRESSOF) = SCALAR | |
2071 | DEREF (SCALAR) = DEREF | |
2072 | DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp)) | |
2073 | This is needed so that we can handle dereferencing DEREF constraints. */ | |
2074 | ||
2075 | static struct constraint_expr | |
2076 | do_deref (struct constraint_expr cons) | |
2077 | { | |
2078 | if (cons.type == SCALAR) | |
2079 | { | |
2080 | cons.type = DEREF; | |
2081 | return cons; | |
2082 | } | |
2083 | else if (cons.type == ADDRESSOF) | |
2084 | { | |
2085 | cons.type = SCALAR; | |
2086 | return cons; | |
2087 | } | |
2088 | else if (cons.type == DEREF) | |
2089 | { | |
2090 | tree tmpvar = create_tmp_var_raw (ptr_type_node, "derefmp"); | |
2091 | struct constraint_expr tmplhs = get_constraint_exp_from_ssa_var (tmpvar); | |
2092 | process_constraint (new_constraint (tmplhs, cons)); | |
2093 | cons.var = tmplhs.var; | |
2094 | return cons; | |
2095 | } | |
2096 | gcc_unreachable (); | |
2097 | } | |
2098 | ||
2099 | ||
2100 | /* Given a tree T, return the constraint expression for it. */ | |
2101 | ||
2102 | static struct constraint_expr | |
2103 | get_constraint_for (tree t) | |
2104 | { | |
2105 | struct constraint_expr temp; | |
2106 | ||
2107 | /* x = integer is all glommed to a single variable, which doesn't | |
2108 | point to anything by itself. That is, of course, unless it is an | |
2109 | integer constant being treated as a pointer, in which case, we | |
2110 | will return that this is really the addressof anything. This | |
2111 | happens below, since it will fall into the default case. The only | |
2112 | case we know something about an integer treated like a pointer is | |
2113 | when it is the NULL pointer, and then we just say it points to | |
2114 | NULL. */ | |
2115 | if (TREE_CODE (t) == INTEGER_CST | |
2116 | && !POINTER_TYPE_P (TREE_TYPE (t))) | |
2117 | { | |
2118 | temp.var = integer_id; | |
2119 | temp.type = SCALAR; | |
2120 | temp.offset = 0; | |
2121 | return temp; | |
2122 | } | |
2123 | else if (TREE_CODE (t) == INTEGER_CST | |
2124 | && integer_zerop (t)) | |
2125 | { | |
2126 | temp.var = nothing_id; | |
2127 | temp.type = ADDRESSOF; | |
2128 | temp.offset = 0; | |
2129 | return temp; | |
2130 | } | |
2131 | ||
2132 | switch (TREE_CODE_CLASS (TREE_CODE (t))) | |
2133 | { | |
2134 | case tcc_expression: | |
2135 | { | |
2136 | switch (TREE_CODE (t)) | |
2137 | { | |
2138 | case ADDR_EXPR: | |
2139 | { | |
2140 | temp = get_constraint_for (TREE_OPERAND (t, 0)); | |
2141 | if (temp.type == DEREF) | |
2142 | temp.type = SCALAR; | |
2143 | else | |
2144 | temp.type = ADDRESSOF; | |
2145 | return temp; | |
2146 | } | |
2147 | break; | |
2148 | case CALL_EXPR: | |
2149 | ||
2150 | /* XXX: In interprocedural mode, if we didn't have the | |
2151 | body, we would need to do *each pointer argument = | |
2152 | &ANYTHING added. */ | |
2153 | if (call_expr_flags (t) & (ECF_MALLOC | ECF_MAY_BE_ALLOCA)) | |
2154 | { | |
e8ca4159 DN |
2155 | varinfo_t vi; |
2156 | tree heapvar; | |
2157 | ||
2158 | heapvar = create_tmp_var_raw (ptr_type_node, "HEAP"); | |
2159 | DECL_EXTERNAL (heapvar) = 1; | |
2160 | add_referenced_tmp_var (heapvar); | |
910fdc79 DB |
2161 | temp.var = create_variable_info_for (heapvar, |
2162 | alias_get_name (heapvar)); | |
2163 | ||
e8ca4159 DN |
2164 | vi = get_varinfo (temp.var); |
2165 | vi->is_artificial_var = 1; | |
2166 | vi->is_heap_var = 1; | |
910fdc79 DB |
2167 | temp.type = ADDRESSOF; |
2168 | temp.offset = 0; | |
2169 | return temp; | |
2170 | } | |
2171 | /* FALLTHRU */ | |
2172 | default: | |
2173 | { | |
2174 | temp.type = ADDRESSOF; | |
2175 | temp.var = anything_id; | |
2176 | temp.offset = 0; | |
2177 | return temp; | |
2178 | } | |
2179 | } | |
2180 | } | |
2181 | case tcc_reference: | |
2182 | { | |
2183 | switch (TREE_CODE (t)) | |
2184 | { | |
2185 | case INDIRECT_REF: | |
2186 | { | |
2187 | temp = get_constraint_for (TREE_OPERAND (t, 0)); | |
2188 | temp = do_deref (temp); | |
2189 | return temp; | |
2190 | } | |
2191 | case ARRAY_REF: | |
2192 | case COMPONENT_REF: | |
2193 | temp = get_constraint_for_component_ref (t); | |
2194 | return temp; | |
2195 | default: | |
2196 | { | |
2197 | temp.type = ADDRESSOF; | |
2198 | temp.var = anything_id; | |
2199 | temp.offset = 0; | |
2200 | return temp; | |
2201 | } | |
2202 | } | |
2203 | } | |
2204 | case tcc_unary: | |
2205 | { | |
2206 | switch (TREE_CODE (t)) | |
2207 | { | |
2208 | case NOP_EXPR: | |
2209 | case CONVERT_EXPR: | |
2210 | case NON_LVALUE_EXPR: | |
2211 | { | |
2212 | tree op = TREE_OPERAND (t, 0); | |
2213 | ||
2214 | /* Cast from non-pointer to pointers are bad news for us. | |
2215 | Anything else, we see through */ | |
e8ca4159 DN |
2216 | if (!(POINTER_TYPE_P (TREE_TYPE (t)) |
2217 | && ! POINTER_TYPE_P (TREE_TYPE (op)))) | |
910fdc79 | 2218 | return get_constraint_for (op); |
e8ca4159 DN |
2219 | |
2220 | /* FALLTHRU */ | |
910fdc79 DB |
2221 | } |
2222 | default: | |
2223 | { | |
2224 | temp.type = ADDRESSOF; | |
2225 | temp.var = anything_id; | |
2226 | temp.offset = 0; | |
2227 | return temp; | |
2228 | } | |
2229 | } | |
2230 | } | |
2231 | case tcc_exceptional: | |
2232 | { | |
2233 | switch (TREE_CODE (t)) | |
2234 | { | |
2235 | case PHI_NODE: | |
2236 | return get_constraint_for (PHI_RESULT (t)); | |
2237 | case SSA_NAME: | |
2238 | return get_constraint_exp_from_ssa_var (t); | |
2239 | default: | |
2240 | { | |
2241 | temp.type = ADDRESSOF; | |
2242 | temp.var = anything_id; | |
2243 | temp.offset = 0; | |
2244 | return temp; | |
2245 | } | |
2246 | } | |
2247 | } | |
2248 | case tcc_declaration: | |
2249 | return get_constraint_exp_from_ssa_var (t); | |
2250 | default: | |
2251 | { | |
2252 | temp.type = ADDRESSOF; | |
2253 | temp.var = anything_id; | |
2254 | temp.offset = 0; | |
2255 | return temp; | |
2256 | } | |
2257 | } | |
2258 | } | |
2259 | ||
2260 | ||
2261 | /* Handle the structure copy case where we have a simple structure copy | |
2262 | between LHS and RHS that is of SIZE (in bits) | |
2263 | ||
2264 | For each field of the lhs variable (lhsfield) | |
2265 | For each field of the rhs variable at lhsfield.offset (rhsfield) | |
2266 | add the constraint lhsfield = rhsfield | |
2267 | */ | |
2268 | ||
2269 | static void | |
2270 | do_simple_structure_copy (const struct constraint_expr lhs, | |
2271 | const struct constraint_expr rhs, | |
2272 | const unsigned HOST_WIDE_INT size) | |
2273 | { | |
2274 | varinfo_t p = get_varinfo (lhs.var); | |
a5eadacc | 2275 | unsigned HOST_WIDE_INT pstart, last; |
910fdc79 DB |
2276 | pstart = p->offset; |
2277 | last = p->offset + size; | |
2278 | for (; p && p->offset < last; p = p->next) | |
2279 | { | |
2280 | varinfo_t q; | |
2281 | struct constraint_expr templhs = lhs; | |
2282 | struct constraint_expr temprhs = rhs; | |
2283 | unsigned HOST_WIDE_INT fieldoffset; | |
2284 | ||
2285 | templhs.var = p->id; | |
2286 | q = get_varinfo (temprhs.var); | |
2287 | fieldoffset = p->offset - pstart; | |
2288 | q = first_vi_for_offset (q, q->offset + fieldoffset); | |
2289 | temprhs.var = q->id; | |
2290 | process_constraint (new_constraint (templhs, temprhs)); | |
2291 | } | |
2292 | } | |
2293 | ||
2294 | ||
2295 | /* Handle the structure copy case where we have a structure copy between a | |
2296 | aggregate on the LHS and a dereference of a pointer on the RHS | |
2297 | that is of SIZE (in bits) | |
2298 | ||
2299 | For each field of the lhs variable (lhsfield) | |
2300 | rhs.offset = lhsfield->offset | |
2301 | add the constraint lhsfield = rhs | |
2302 | */ | |
2303 | ||
2304 | static void | |
2305 | do_rhs_deref_structure_copy (const struct constraint_expr lhs, | |
2306 | const struct constraint_expr rhs, | |
2307 | const unsigned HOST_WIDE_INT size) | |
2308 | { | |
2309 | varinfo_t p = get_varinfo (lhs.var); | |
2310 | unsigned HOST_WIDE_INT pstart,last; | |
2311 | pstart = p->offset; | |
2312 | last = p->offset + size; | |
2313 | ||
2314 | for (; p && p->offset < last; p = p->next) | |
2315 | { | |
2316 | varinfo_t q; | |
2317 | struct constraint_expr templhs = lhs; | |
2318 | struct constraint_expr temprhs = rhs; | |
2319 | unsigned HOST_WIDE_INT fieldoffset; | |
2320 | ||
2321 | ||
2322 | if (templhs.type == SCALAR) | |
2323 | templhs.var = p->id; | |
2324 | else | |
2325 | templhs.offset = p->offset; | |
2326 | ||
2327 | q = get_varinfo (temprhs.var); | |
2328 | fieldoffset = p->offset - pstart; | |
2329 | temprhs.offset += fieldoffset; | |
2330 | process_constraint (new_constraint (templhs, temprhs)); | |
2331 | } | |
2332 | } | |
2333 | ||
2334 | /* Handle the structure copy case where we have a structure copy | |
2335 | between a aggregate on the RHS and a dereference of a pointer on | |
2336 | the LHS that is of SIZE (in bits) | |
2337 | ||
2338 | For each field of the rhs variable (rhsfield) | |
2339 | lhs.offset = rhsfield->offset | |
2340 | add the constraint lhs = rhsfield | |
2341 | */ | |
2342 | ||
2343 | static void | |
2344 | do_lhs_deref_structure_copy (const struct constraint_expr lhs, | |
2345 | const struct constraint_expr rhs, | |
2346 | const unsigned HOST_WIDE_INT size) | |
2347 | { | |
2348 | varinfo_t p = get_varinfo (rhs.var); | |
2349 | unsigned HOST_WIDE_INT pstart,last; | |
2350 | pstart = p->offset; | |
2351 | last = p->offset + size; | |
2352 | ||
2353 | for (; p && p->offset < last; p = p->next) | |
2354 | { | |
2355 | varinfo_t q; | |
2356 | struct constraint_expr templhs = lhs; | |
2357 | struct constraint_expr temprhs = rhs; | |
2358 | unsigned HOST_WIDE_INT fieldoffset; | |
2359 | ||
2360 | ||
2361 | if (temprhs.type == SCALAR) | |
2362 | temprhs.var = p->id; | |
2363 | else | |
2364 | temprhs.offset = p->offset; | |
2365 | ||
2366 | q = get_varinfo (templhs.var); | |
2367 | fieldoffset = p->offset - pstart; | |
2368 | templhs.offset += fieldoffset; | |
2369 | process_constraint (new_constraint (templhs, temprhs)); | |
2370 | } | |
2371 | } | |
2372 | ||
2373 | ||
2374 | /* Handle aggregate copies by expanding into copies of the respective | |
2375 | fields of the structures. */ | |
2376 | ||
2377 | static void | |
2378 | do_structure_copy (tree lhsop, tree rhsop) | |
2379 | { | |
2380 | struct constraint_expr lhs, rhs, tmp; | |
2381 | varinfo_t p; | |
2382 | unsigned HOST_WIDE_INT lhssize; | |
2383 | unsigned HOST_WIDE_INT rhssize; | |
2384 | ||
910fdc79 DB |
2385 | lhs = get_constraint_for (lhsop); |
2386 | rhs = get_constraint_for (rhsop); | |
2387 | ||
2388 | /* If we have special var = x, swap it around. */ | |
2389 | if (lhs.var <= integer_id && rhs.var > integer_id) | |
2390 | { | |
2391 | tmp = lhs; | |
2392 | lhs = rhs; | |
2393 | rhs = tmp; | |
2394 | } | |
2395 | ||
a5eadacc DB |
2396 | /* This is fairly conservative for the RHS == ADDRESSOF case, in that it's |
2397 | possible it's something we could handle. However, most cases falling | |
2398 | into this are dealing with transparent unions, which are slightly | |
2399 | weird. */ | |
2400 | if (rhs.type == ADDRESSOF && rhs.var > integer_id) | |
2401 | { | |
2402 | rhs.type = ADDRESSOF; | |
2403 | rhs.var = anything_id; | |
2404 | } | |
2405 | ||
2406 | /* If the RHS is a special var, or an addressof, set all the LHS fields to | |
2407 | that special var. */ | |
910fdc79 DB |
2408 | if (rhs.var <= integer_id) |
2409 | { | |
2410 | for (p = get_varinfo (lhs.var); p; p = p->next) | |
2411 | { | |
2412 | struct constraint_expr templhs = lhs; | |
2413 | struct constraint_expr temprhs = rhs; | |
2414 | if (templhs.type == SCALAR ) | |
2415 | templhs.var = p->id; | |
2416 | else | |
2417 | templhs.offset += p->offset; | |
2418 | process_constraint (new_constraint (templhs, temprhs)); | |
2419 | } | |
2420 | } | |
2421 | else | |
2422 | { | |
4e422b8b DB |
2423 | tree rhstype = TREE_TYPE (rhsop); |
2424 | tree lhstype = TREE_TYPE (lhsop); | |
2425 | tree rhstypesize = TYPE_SIZE (rhstype); | |
2426 | tree lhstypesize = TYPE_SIZE (lhstype); | |
2427 | ||
2428 | /* If we have a variably sized types on the rhs or lhs, and a deref | |
2429 | constraint, add the constraint, lhsconstraint = &ANYTHING. | |
2430 | This is conservatively correct because either the lhs is an unknown | |
2431 | sized var (if the constraint is SCALAR), or the lhs is a DEREF | |
2432 | constraint, and every variable it can point to must be unknown sized | |
2433 | anyway, so we don't need to worry about fields at all. */ | |
2434 | if ((rhs.type == DEREF && TREE_CODE (rhstypesize) != INTEGER_CST) | |
2435 | || (lhs.type == DEREF && TREE_CODE (lhstypesize) != INTEGER_CST)) | |
2436 | { | |
2437 | rhs.var = anything_id; | |
2438 | rhs.type = ADDRESSOF; | |
2439 | rhs.offset = 0; | |
2440 | process_constraint (new_constraint (lhs, rhs)); | |
2441 | return; | |
2442 | } | |
2443 | ||
a5eadacc DB |
2444 | /* The size only really matters insofar as we don't set more or less of |
2445 | the variable. If we hit an unknown size var, the size should be the | |
2446 | whole darn thing. */ | |
2447 | if (get_varinfo (rhs.var)->is_unknown_size_var) | |
2448 | rhssize = ~0; | |
2449 | else | |
4e422b8b | 2450 | rhssize = TREE_INT_CST_LOW (rhstypesize); |
a5eadacc DB |
2451 | |
2452 | if (get_varinfo (lhs.var)->is_unknown_size_var) | |
2453 | lhssize = ~0; | |
2454 | else | |
4e422b8b | 2455 | lhssize = TREE_INT_CST_LOW (lhstypesize); |
a5eadacc DB |
2456 | |
2457 | ||
910fdc79 DB |
2458 | if (rhs.type == SCALAR && lhs.type == SCALAR) |
2459 | do_simple_structure_copy (lhs, rhs, MIN (lhssize, rhssize)); | |
2460 | else if (lhs.type != DEREF && rhs.type == DEREF) | |
2461 | do_rhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize)); | |
2462 | else if (lhs.type == DEREF && rhs.type != DEREF) | |
2463 | do_lhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize)); | |
2464 | else | |
2465 | { | |
4e422b8b | 2466 | tree pointedtotype = lhstype; |
a5eadacc DB |
2467 | tree tmpvar; |
2468 | ||
910fdc79 DB |
2469 | gcc_assert (rhs.type == DEREF && lhs.type == DEREF); |
2470 | tmpvar = create_tmp_var_raw (pointedtotype, "structcopydereftmp"); | |
a5eadacc DB |
2471 | do_structure_copy (tmpvar, rhsop); |
2472 | do_structure_copy (lhsop, tmpvar); | |
910fdc79 DB |
2473 | } |
2474 | } | |
2475 | } | |
2476 | ||
2477 | ||
2478 | /* Return true if REF, a COMPONENT_REF, has an INDIRECT_REF somewhere | |
2479 | in it. */ | |
2480 | ||
2481 | static inline bool | |
2482 | ref_contains_indirect_ref (tree ref) | |
2483 | { | |
2484 | while (handled_component_p (ref)) | |
2485 | { | |
2486 | if (TREE_CODE (ref) == INDIRECT_REF) | |
2487 | return true; | |
2488 | ref = TREE_OPERAND (ref, 0); | |
2489 | } | |
2490 | return false; | |
2491 | } | |
2492 | ||
2493 | ||
e8ca4159 DN |
2494 | /* Update related alias information kept in AI. This is used when |
2495 | building name tags, alias sets and deciding grouping heuristics. | |
2496 | STMT is the statement to process. This function also updates | |
2497 | ADDRESSABLE_VARS. */ | |
2498 | ||
2499 | static void | |
2500 | update_alias_info (tree stmt, struct alias_info *ai) | |
2501 | { | |
2502 | bitmap addr_taken; | |
2503 | use_operand_p use_p; | |
e8ca4159 DN |
2504 | ssa_op_iter iter; |
2505 | bool stmt_escapes_p = is_escape_site (stmt, ai); | |
0bfac35f | 2506 | tree op; |
e8ca4159 DN |
2507 | |
2508 | /* Mark all the variables whose address are taken by the statement. */ | |
2509 | addr_taken = addresses_taken (stmt); | |
2510 | if (addr_taken) | |
2511 | { | |
2512 | bitmap_ior_into (addressable_vars, addr_taken); | |
2513 | ||
2514 | /* If STMT is an escape point, all the addresses taken by it are | |
2515 | call-clobbered. */ | |
2516 | if (stmt_escapes_p) | |
2517 | { | |
2518 | bitmap_iterator bi; | |
2519 | unsigned i; | |
2520 | ||
2521 | EXECUTE_IF_SET_IN_BITMAP (addr_taken, 0, i, bi) | |
2522 | mark_call_clobbered (referenced_var (i)); | |
2523 | } | |
2524 | } | |
2525 | ||
2526 | /* Process each operand use. If an operand may be aliased, keep | |
2527 | track of how many times it's being used. For pointers, determine | |
2528 | whether they are dereferenced by the statement, or whether their | |
2529 | value escapes, etc. */ | |
2530 | FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE) | |
2531 | { | |
2532 | tree op, var; | |
2533 | var_ann_t v_ann; | |
2534 | struct ptr_info_def *pi; | |
2535 | bool is_store; | |
2536 | unsigned num_uses, num_derefs; | |
2537 | ||
2538 | op = USE_FROM_PTR (use_p); | |
2539 | ||
2540 | /* If STMT is a PHI node, OP may be an ADDR_EXPR. If so, add it | |
2541 | to the set of addressable variables. */ | |
2542 | if (TREE_CODE (op) == ADDR_EXPR) | |
2543 | { | |
2544 | gcc_assert (TREE_CODE (stmt) == PHI_NODE); | |
2545 | ||
2546 | /* PHI nodes don't have annotations for pinning the set | |
2547 | of addresses taken, so we collect them here. | |
2548 | ||
2549 | FIXME, should we allow PHI nodes to have annotations | |
2550 | so that they can be treated like regular statements? | |
2551 | Currently, they are treated as second-class | |
2552 | statements. */ | |
2553 | add_to_addressable_set (TREE_OPERAND (op, 0), &addressable_vars); | |
2554 | continue; | |
2555 | } | |
2556 | ||
2557 | /* Ignore constants. */ | |
2558 | if (TREE_CODE (op) != SSA_NAME) | |
2559 | continue; | |
2560 | ||
2561 | var = SSA_NAME_VAR (op); | |
2562 | v_ann = var_ann (var); | |
2563 | ||
2564 | /* If the operand's variable may be aliased, keep track of how | |
2565 | many times we've referenced it. This is used for alias | |
2566 | grouping in compute_flow_insensitive_aliasing. */ | |
2567 | if (may_be_aliased (var)) | |
2568 | NUM_REFERENCES_INC (v_ann); | |
2569 | ||
2570 | /* We are only interested in pointers. */ | |
2571 | if (!POINTER_TYPE_P (TREE_TYPE (op))) | |
2572 | continue; | |
2573 | ||
2574 | pi = get_ptr_info (op); | |
2575 | ||
2576 | /* Add OP to AI->PROCESSED_PTRS, if it's not there already. */ | |
2577 | if (!TEST_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (op))) | |
2578 | { | |
2579 | SET_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (op)); | |
2580 | VARRAY_PUSH_TREE (ai->processed_ptrs, op); | |
2581 | } | |
2582 | ||
2583 | /* If STMT is a PHI node, then it will not have pointer | |
2584 | dereferences and it will not be an escape point. */ | |
2585 | if (TREE_CODE (stmt) == PHI_NODE) | |
2586 | continue; | |
2587 | ||
2588 | /* Determine whether OP is a dereferenced pointer, and if STMT | |
2589 | is an escape point, whether OP escapes. */ | |
2590 | count_uses_and_derefs (op, stmt, &num_uses, &num_derefs, &is_store); | |
2591 | ||
2592 | if (num_derefs > 0) | |
2593 | { | |
2594 | /* Mark OP as dereferenced. In a subsequent pass, | |
2595 | dereferenced pointers that point to a set of | |
2596 | variables will be assigned a name tag to alias | |
2597 | all the variables OP points to. */ | |
2598 | pi->is_dereferenced = 1; | |
2599 | ||
2600 | /* Keep track of how many time we've dereferenced each | |
2601 | pointer. */ | |
2602 | NUM_REFERENCES_INC (v_ann); | |
2603 | ||
2604 | /* If this is a store operation, mark OP as being | |
2605 | dereferenced to store, otherwise mark it as being | |
2606 | dereferenced to load. */ | |
2607 | if (is_store) | |
2608 | bitmap_set_bit (ai->dereferenced_ptrs_store, DECL_UID (var)); | |
2609 | else | |
2610 | bitmap_set_bit (ai->dereferenced_ptrs_load, DECL_UID (var)); | |
2611 | } | |
2612 | ||
2613 | if (stmt_escapes_p && num_derefs < num_uses) | |
2614 | { | |
2615 | /* If STMT is an escape point and STMT contains at | |
2616 | least one direct use of OP, then the value of OP | |
2617 | escapes and so the pointed-to variables need to | |
2618 | be marked call-clobbered. */ | |
2619 | pi->value_escapes_p = 1; | |
2620 | ||
2621 | /* If the statement makes a function call, assume | |
2622 | that pointer OP will be dereferenced in a store | |
2623 | operation inside the called function. */ | |
2624 | if (get_call_expr_in (stmt)) | |
2625 | { | |
2626 | bitmap_set_bit (ai->dereferenced_ptrs_store, DECL_UID (var)); | |
2627 | pi->is_dereferenced = 1; | |
2628 | } | |
2629 | } | |
2630 | } | |
2631 | ||
0bfac35f DB |
2632 | if (TREE_CODE (stmt) == PHI_NODE) |
2633 | return; | |
2634 | ||
2635 | /* Update reference counter for definitions to any | |
2636 | potentially aliased variable. This is used in the alias | |
2637 | grouping heuristics. */ | |
2638 | FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF) | |
e8ca4159 | 2639 | { |
e8ca4159 DN |
2640 | tree var = SSA_NAME_VAR (op); |
2641 | var_ann_t ann = var_ann (var); | |
2642 | bitmap_set_bit (ai->written_vars, DECL_UID (var)); | |
2643 | if (may_be_aliased (var)) | |
2644 | NUM_REFERENCES_INC (ann); | |
0bfac35f DB |
2645 | |
2646 | } | |
2647 | ||
2648 | /* Mark variables in V_MAY_DEF operands as being written to. */ | |
2649 | FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_VIRTUAL_DEFS) | |
2650 | { | |
2651 | tree var = DECL_P (op) ? op : SSA_NAME_VAR (op); | |
2652 | bitmap_set_bit (ai->written_vars, DECL_UID (var)); | |
e8ca4159 DN |
2653 | } |
2654 | } | |
2655 | ||
2656 | ||
2657 | /* Handle pointer arithmetic EXPR when creating aliasing constraints. | |
2658 | Expressions of the type PTR + CST can be handled in two ways: | |
2659 | ||
2660 | 1- If the constraint for PTR is ADDRESSOF for a non-structure | |
2661 | variable, then we can use it directly because adding or | |
2662 | subtracting a constant may not alter the original ADDRESSOF | |
2663 | constraing (i.e., pointer arithmetic may not legally go outside | |
2664 | an object's boundaries). | |
2665 | ||
2666 | 2- If the constraint for PTR is ADDRESSOF for a structure variable, | |
2667 | then if CST is a compile-time constant that can be used as an | |
2668 | offset, we can determine which sub-variable will be pointed-to | |
2669 | by the expression. | |
2670 | ||
2671 | Return true if the expression is handled. For any other kind of | |
2672 | expression, return false so that each operand can be added as a | |
2673 | separate constraint by the caller. */ | |
2674 | ||
2675 | static bool | |
2676 | handle_ptr_arith (struct constraint_expr lhs, tree expr) | |
2677 | { | |
2678 | tree op0, op1; | |
2679 | struct constraint_expr base, offset; | |
2680 | ||
2681 | if (TREE_CODE (expr) != PLUS_EXPR) | |
2682 | return false; | |
2683 | ||
2684 | op0 = TREE_OPERAND (expr, 0); | |
2685 | op1 = TREE_OPERAND (expr, 1); | |
2686 | ||
2687 | base = get_constraint_for (op0); | |
2688 | ||
2689 | offset.var = anyoffset_id; | |
2690 | offset.type = ADDRESSOF; | |
2691 | offset.offset = 0; | |
2692 | ||
2693 | process_constraint (new_constraint (lhs, base)); | |
2694 | process_constraint (new_constraint (lhs, offset)); | |
2695 | ||
2696 | return true; | |
2697 | } | |
2698 | ||
2699 | ||
2700 | /* Walk statement T setting up aliasing constraints according to the | |
2701 | references found in T. This function is the main part of the | |
2702 | constraint builder. AI points to auxiliary alias information used | |
2703 | when building alias sets and computing alias grouping heuristics. */ | |
910fdc79 DB |
2704 | |
2705 | static void | |
e8ca4159 | 2706 | find_func_aliases (tree t, struct alias_info *ai) |
910fdc79 DB |
2707 | { |
2708 | struct constraint_expr lhs, rhs; | |
910fdc79 | 2709 | |
e8ca4159 DN |
2710 | /* Update various related attributes like escaped addresses, pointer |
2711 | dereferences for loads and stores. This is used when creating | |
2712 | name tags and alias sets. */ | |
2713 | update_alias_info (t, ai); | |
910fdc79 | 2714 | |
e8ca4159 DN |
2715 | /* Now build constraints expressions. */ |
2716 | if (TREE_CODE (t) == PHI_NODE) | |
2717 | { | |
2718 | /* Only care about pointers and structures containing | |
2719 | pointers. */ | |
2720 | if (POINTER_TYPE_P (TREE_TYPE (PHI_RESULT (t))) | |
2721 | || AGGREGATE_TYPE_P (TREE_TYPE (PHI_RESULT (t)))) | |
2722 | { | |
2723 | int i; | |
910fdc79 | 2724 | |
e8ca4159 DN |
2725 | lhs = get_constraint_for (PHI_RESULT (t)); |
2726 | for (i = 0; i < PHI_NUM_ARGS (t); i++) | |
2727 | { | |
2728 | rhs = get_constraint_for (PHI_ARG_DEF (t, i)); | |
2729 | process_constraint (new_constraint (lhs, rhs)); | |
2730 | } | |
2731 | } | |
2732 | } | |
2733 | else if (TREE_CODE (t) == MODIFY_EXPR) | |
2734 | { | |
2735 | tree lhsop = TREE_OPERAND (t, 0); | |
2736 | tree rhsop = TREE_OPERAND (t, 1); | |
2737 | int i; | |
2738 | ||
2739 | if (AGGREGATE_TYPE_P (TREE_TYPE (lhsop)) | |
2740 | && AGGREGATE_TYPE_P (TREE_TYPE (rhsop))) | |
2741 | { | |
2742 | do_structure_copy (lhsop, rhsop); | |
2743 | } | |
2744 | else | |
2745 | { | |
2746 | /* Only care about operations with pointers, structures | |
2747 | containing pointers, dereferences, and call expressions. */ | |
2748 | if (POINTER_TYPE_P (TREE_TYPE (lhsop)) | |
2749 | || AGGREGATE_TYPE_P (TREE_TYPE (lhsop)) | |
2750 | || ref_contains_indirect_ref (lhsop) | |
2751 | || TREE_CODE (rhsop) == CALL_EXPR) | |
2752 | { | |
2753 | lhs = get_constraint_for (lhsop); | |
2754 | switch (TREE_CODE_CLASS (TREE_CODE (rhsop))) | |
2755 | { | |
2756 | /* RHS that consist of unary operations, | |
2757 | exceptional types, or bare decls/constants, get | |
2758 | handled directly by get_constraint_for. */ | |
910fdc79 DB |
2759 | case tcc_reference: |
2760 | case tcc_declaration: | |
2761 | case tcc_constant: | |
2762 | case tcc_exceptional: | |
2763 | case tcc_expression: | |
2764 | case tcc_unary: | |
e8ca4159 DN |
2765 | { |
2766 | rhs = get_constraint_for (rhsop); | |
2767 | process_constraint (new_constraint (lhs, rhs)); | |
2768 | ||
2769 | /* When taking the address of an aggregate | |
2770 | type, from the LHS we can access any field | |
2771 | of the RHS. */ | |
2772 | if (rhs.type == ADDRESSOF | |
2773 | && rhs.var > anything_id | |
2774 | && AGGREGATE_TYPE_P (TREE_TYPE (TREE_TYPE (rhsop)))) | |
2775 | { | |
2776 | rhs.var = anyoffset_id; | |
2777 | rhs.type = ADDRESSOF; | |
2778 | rhs.offset = 0; | |
2779 | process_constraint (new_constraint (lhs, rhs)); | |
2780 | } | |
2781 | } | |
910fdc79 DB |
2782 | break; |
2783 | ||
e8ca4159 DN |
2784 | case tcc_binary: |
2785 | { | |
2786 | /* For pointer arithmetic of the form | |
2787 | PTR + CST, we can simply use PTR's | |
2788 | constraint because pointer arithmetic is | |
2789 | not allowed to go out of bounds. */ | |
2790 | if (handle_ptr_arith (lhs, rhsop)) | |
2791 | break; | |
2792 | } | |
2793 | /* FALLTHRU */ | |
2794 | ||
2795 | /* Otherwise, walk each operand. Notice that we | |
2796 | can't use the operand interface because we need | |
2797 | to process expressions other than simple operands | |
2798 | (e.g. INDIRECT_REF, ADDR_EXPR, CALL_EXPR). */ | |
910fdc79 DB |
2799 | default: |
2800 | for (i = 0; i < TREE_CODE_LENGTH (TREE_CODE (rhsop)); i++) | |
2801 | { | |
2802 | tree op = TREE_OPERAND (rhsop, i); | |
2803 | rhs = get_constraint_for (op); | |
2804 | process_constraint (new_constraint (lhs, rhs)); | |
2805 | } | |
e8ca4159 DN |
2806 | } |
2807 | } | |
2808 | } | |
910fdc79 | 2809 | } |
e8ca4159 DN |
2810 | |
2811 | /* After promoting variables and computing aliasing we will | |
2812 | need to re-scan most statements. FIXME: Try to minimize the | |
2813 | number of statements re-scanned. It's not really necessary to | |
2814 | re-scan *all* statements. */ | |
2815 | mark_stmt_modified (t); | |
910fdc79 DB |
2816 | } |
2817 | ||
2818 | ||
2819 | /* Find the first varinfo in the same variable as START that overlaps with | |
2820 | OFFSET. | |
2821 | Effectively, walk the chain of fields for the variable START to find the | |
2822 | first field that overlaps with OFFSET. | |
2823 | Abort if we can't find one. */ | |
2824 | ||
2825 | static varinfo_t | |
2826 | first_vi_for_offset (varinfo_t start, unsigned HOST_WIDE_INT offset) | |
2827 | { | |
2828 | varinfo_t curr = start; | |
2829 | while (curr) | |
2830 | { | |
2831 | /* We may not find a variable in the field list with the actual | |
2832 | offset when when we have glommed a structure to a variable. | |
2833 | In that case, however, offset should still be within the size | |
2834 | of the variable. */ | |
2835 | if (offset >= curr->offset && offset < (curr->offset + curr->size)) | |
2836 | return curr; | |
2837 | curr = curr->next; | |
2838 | } | |
2839 | ||
2840 | gcc_unreachable (); | |
2841 | } | |
2842 | ||
2843 | ||
2844 | /* Insert the varinfo FIELD into the field list for BASE, ordered by | |
2845 | offset. */ | |
2846 | ||
2847 | static void | |
2848 | insert_into_field_list (varinfo_t base, varinfo_t field) | |
2849 | { | |
2850 | varinfo_t prev = base; | |
2851 | varinfo_t curr = base->next; | |
2852 | ||
2853 | if (curr == NULL) | |
2854 | { | |
2855 | prev->next = field; | |
2856 | field->next = NULL; | |
2857 | } | |
2858 | else | |
2859 | { | |
2860 | while (curr) | |
2861 | { | |
2862 | if (field->offset <= curr->offset) | |
2863 | break; | |
2864 | prev = curr; | |
2865 | curr = curr->next; | |
2866 | } | |
2867 | field->next = prev->next; | |
2868 | prev->next = field; | |
2869 | } | |
2870 | } | |
2871 | ||
2872 | /* qsort comparison function for two fieldoff's PA and PB */ | |
2873 | ||
2874 | static int | |
2875 | fieldoff_compare (const void *pa, const void *pb) | |
2876 | { | |
2877 | const fieldoff_s *foa = (const fieldoff_s *)pa; | |
2878 | const fieldoff_s *fob = (const fieldoff_s *)pb; | |
2879 | HOST_WIDE_INT foasize, fobsize; | |
2880 | ||
2881 | if (foa->offset != fob->offset) | |
2882 | return foa->offset - fob->offset; | |
2883 | ||
2884 | foasize = TREE_INT_CST_LOW (DECL_SIZE (foa->field)); | |
2885 | fobsize = TREE_INT_CST_LOW (DECL_SIZE (fob->field)); | |
2886 | return foasize - fobsize; | |
2887 | } | |
2888 | ||
2889 | /* Sort a fieldstack according to the field offset and sizes. */ | |
2890 | void sort_fieldstack (VEC(fieldoff_s,heap) *fieldstack) | |
2891 | { | |
2892 | qsort (VEC_address (fieldoff_s, fieldstack), | |
2893 | VEC_length (fieldoff_s, fieldstack), | |
2894 | sizeof (fieldoff_s), | |
2895 | fieldoff_compare); | |
2896 | } | |
2897 | ||
2898 | /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all the fields | |
2899 | of TYPE onto fieldstack, recording their offsets along the way. | |
2900 | OFFSET is used to keep track of the offset in this entire structure, rather | |
2901 | than just the immediately containing structure. Returns the number | |
2902 | of fields pushed. | |
2903 | HAS_UNION is set to true if we find a union type as a field of | |
2904 | TYPE. */ | |
2905 | ||
2906 | int | |
2907 | push_fields_onto_fieldstack (tree type, VEC(fieldoff_s,heap) **fieldstack, | |
2908 | HOST_WIDE_INT offset, bool *has_union) | |
2909 | { | |
2910 | tree field; | |
2911 | int count = 0; | |
2912 | ||
2913 | for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field)) | |
2914 | if (TREE_CODE (field) == FIELD_DECL) | |
2915 | { | |
2916 | bool push = false; | |
2917 | ||
2918 | if (has_union | |
2919 | && (TREE_CODE (TREE_TYPE (field)) == QUAL_UNION_TYPE | |
2920 | || TREE_CODE (TREE_TYPE (field)) == UNION_TYPE)) | |
2921 | *has_union = true; | |
2922 | ||
2923 | if (!var_can_have_subvars (field)) | |
2924 | push = true; | |
2925 | else if (!(push_fields_onto_fieldstack | |
2926 | (TREE_TYPE (field), fieldstack, | |
2927 | offset + bitpos_of_field (field), has_union)) | |
2928 | && DECL_SIZE (field) | |
2929 | && !integer_zerop (DECL_SIZE (field))) | |
2930 | /* Empty structures may have actual size, like in C++. So | |
2931 | see if we didn't push any subfields and the size is | |
2932 | nonzero, push the field onto the stack */ | |
2933 | push = true; | |
2934 | ||
2935 | if (push) | |
2936 | { | |
2937 | fieldoff_s *pair; | |
2938 | ||
2939 | pair = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL); | |
2940 | pair->field = field; | |
2941 | pair->offset = offset + bitpos_of_field (field); | |
2942 | count++; | |
2943 | } | |
2944 | } | |
2945 | ||
2946 | return count; | |
2947 | } | |
2948 | ||
2949 | static void | |
2950 | make_constraint_to_anything (varinfo_t vi) | |
2951 | { | |
2952 | struct constraint_expr lhs, rhs; | |
2953 | ||
2954 | lhs.var = vi->id; | |
2955 | lhs.offset = 0; | |
2956 | lhs.type = SCALAR; | |
2957 | ||
2958 | rhs.var = anything_id; | |
2959 | rhs.offset =0 ; | |
2960 | rhs.type = ADDRESSOF; | |
2961 | process_constraint (new_constraint (lhs, rhs)); | |
2962 | } | |
2963 | ||
2964 | /* Create a varinfo structure for NAME and DECL, and add it to VARMAP. | |
2965 | This will also create any varinfo structures necessary for fields | |
2966 | of DECL. */ | |
2967 | ||
2968 | static unsigned int | |
2969 | create_variable_info_for (tree decl, const char *name) | |
2970 | { | |
2971 | unsigned int index = VEC_length (varinfo_t, varmap); | |
2972 | varinfo_t vi; | |
2973 | tree decltype = TREE_TYPE (decl); | |
2974 | bool notokay = false; | |
58b82d2b | 2975 | bool hasunion; |
910fdc79 | 2976 | bool is_global = DECL_P (decl) ? is_global_var (decl) : false; |
910fdc79 DB |
2977 | VEC (fieldoff_s,heap) *fieldstack = NULL; |
2978 | ||
58b82d2b | 2979 | |
e8ca4159 DN |
2980 | hasunion = TREE_CODE (decltype) == UNION_TYPE |
2981 | || TREE_CODE (decltype) == QUAL_UNION_TYPE; | |
58b82d2b | 2982 | if (var_can_have_subvars (decl) && use_field_sensitive && !hasunion) |
910fdc79 | 2983 | { |
58b82d2b DB |
2984 | push_fields_onto_fieldstack (decltype, &fieldstack, 0, &hasunion); |
2985 | if (hasunion) | |
2986 | { | |
2987 | VEC_free (fieldoff_s, heap, fieldstack); | |
2988 | notokay = true; | |
2989 | } | |
910fdc79 | 2990 | } |
910fdc79 DB |
2991 | |
2992 | ||
2993 | /* If the variable doesn't have subvars, we may end up needing to | |
2994 | sort the field list and create fake variables for all the | |
2995 | fields. */ | |
2996 | vi = new_var_info (decl, index, name, index); | |
2997 | vi->decl = decl; | |
2998 | vi->offset = 0; | |
58b82d2b | 2999 | vi->has_union = hasunion; |
910fdc79 | 3000 | if (!TYPE_SIZE (decltype) |
a5eadacc | 3001 | || TREE_CODE (TYPE_SIZE (decltype)) != INTEGER_CST |
910fdc79 DB |
3002 | || TREE_CODE (decltype) == ARRAY_TYPE |
3003 | || TREE_CODE (decltype) == UNION_TYPE | |
3004 | || TREE_CODE (decltype) == QUAL_UNION_TYPE) | |
3005 | { | |
3006 | vi->is_unknown_size_var = true; | |
3007 | vi->fullsize = ~0; | |
3008 | vi->size = ~0; | |
3009 | } | |
3010 | else | |
3011 | { | |
3012 | vi->fullsize = TREE_INT_CST_LOW (TYPE_SIZE (decltype)); | |
3013 | vi->size = vi->fullsize; | |
3014 | } | |
3015 | ||
3016 | insert_id_for_tree (vi->decl, index); | |
3017 | VEC_safe_push (varinfo_t, gc, varmap, vi); | |
3018 | if (is_global) | |
3019 | make_constraint_to_anything (vi); | |
3020 | ||
3021 | stats.total_vars++; | |
3022 | if (use_field_sensitive | |
3023 | && !notokay | |
3024 | && !vi->is_unknown_size_var | |
3025 | && var_can_have_subvars (decl)) | |
3026 | { | |
3027 | unsigned int newindex = VEC_length (varinfo_t, varmap); | |
3028 | fieldoff_s *fo = NULL; | |
3029 | unsigned int i; | |
3030 | tree field; | |
3031 | ||
3032 | for (i = 0; !notokay && VEC_iterate (fieldoff_s, fieldstack, i, fo); i++) | |
3033 | { | |
3034 | if (!DECL_SIZE (fo->field) | |
3035 | || TREE_CODE (DECL_SIZE (fo->field)) != INTEGER_CST | |
3036 | || TREE_CODE (TREE_TYPE (fo->field)) == ARRAY_TYPE | |
3037 | || fo->offset < 0) | |
3038 | { | |
3039 | notokay = true; | |
3040 | break; | |
3041 | } | |
3042 | } | |
58b82d2b DB |
3043 | |
3044 | /* We can't sort them if we have a field with a variable sized type, | |
3045 | which will make notokay = true. In that case, we are going to return | |
3046 | without creating varinfos for the fields anyway, so sorting them is a | |
3047 | waste to boot. */ | |
3048 | if (!notokay) | |
3049 | sort_fieldstack (fieldstack); | |
910fdc79 DB |
3050 | |
3051 | if (VEC_length (fieldoff_s, fieldstack) != 0) | |
3052 | fo = VEC_index (fieldoff_s, fieldstack, 0); | |
3053 | ||
3054 | if (fo == NULL || notokay) | |
3055 | { | |
3056 | vi->is_unknown_size_var = 1; | |
3057 | vi->fullsize = ~0; | |
3058 | vi->size = ~0; | |
3059 | VEC_free (fieldoff_s, heap, fieldstack); | |
3060 | return index; | |
3061 | } | |
3062 | ||
3063 | field = fo->field; | |
910fdc79 DB |
3064 | vi->size = TREE_INT_CST_LOW (DECL_SIZE (field)); |
3065 | for (i = 1; VEC_iterate (fieldoff_s, fieldstack, i, fo); i++) | |
3066 | { | |
3067 | varinfo_t newvi; | |
3068 | const char *newname; | |
3069 | char *tempname; | |
3070 | ||
3071 | field = fo->field; | |
3072 | newindex = VEC_length (varinfo_t, varmap); | |
3073 | asprintf (&tempname, "%s.%s", vi->name, alias_get_name (field)); | |
3074 | newname = ggc_strdup (tempname); | |
3075 | free (tempname); | |
3076 | newvi = new_var_info (decl, newindex, newname, newindex); | |
3077 | newvi->offset = fo->offset; | |
3078 | newvi->size = TREE_INT_CST_LOW (DECL_SIZE (field)); | |
3079 | newvi->fullsize = vi->fullsize; | |
3080 | insert_into_field_list (vi, newvi); | |
3081 | VEC_safe_push (varinfo_t, gc, varmap, newvi); | |
3082 | if (is_global) | |
3083 | make_constraint_to_anything (newvi); | |
3084 | ||
3085 | stats.total_vars++; | |
3086 | } | |
3087 | VEC_free (fieldoff_s, heap, fieldstack); | |
3088 | } | |
3089 | return index; | |
3090 | } | |
3091 | ||
3092 | /* Print out the points-to solution for VAR to FILE. */ | |
3093 | ||
3094 | void | |
3095 | dump_solution_for_var (FILE *file, unsigned int var) | |
3096 | { | |
3097 | varinfo_t vi = get_varinfo (var); | |
3098 | unsigned int i; | |
3099 | bitmap_iterator bi; | |
3100 | ||
63a4ef6f | 3101 | fprintf (file, "%s = { ", vi->name); |
910fdc79 DB |
3102 | EXECUTE_IF_SET_IN_BITMAP (get_varinfo (vi->node)->solution, 0, i, bi) |
3103 | { | |
63a4ef6f | 3104 | fprintf (file, "%s ", get_varinfo (i)->name); |
910fdc79 DB |
3105 | } |
3106 | fprintf (file, "}\n"); | |
3107 | } | |
3108 | ||
3109 | /* Print the points-to solution for VAR to stdout. */ | |
3110 | ||
3111 | void | |
3112 | debug_solution_for_var (unsigned int var) | |
3113 | { | |
3114 | dump_solution_for_var (stdout, var); | |
3115 | } | |
3116 | ||
3117 | ||
3118 | /* Create varinfo structures for all of the variables in the | |
3119 | function for intraprocedural mode. */ | |
3120 | ||
3121 | static void | |
3122 | intra_create_variable_infos (void) | |
3123 | { | |
3124 | tree t; | |
3125 | ||
3126 | /* For each incoming argument arg, ARG = &ANYTHING */ | |
3127 | for (t = DECL_ARGUMENTS (current_function_decl); t; t = TREE_CHAIN (t)) | |
3128 | { | |
3129 | struct constraint_expr lhs; | |
3130 | struct constraint_expr rhs; | |
3131 | varinfo_t p; | |
3132 | ||
3133 | lhs.offset = 0; | |
3134 | lhs.type = SCALAR; | |
3135 | lhs.var = create_variable_info_for (t, alias_get_name (t)); | |
3136 | ||
910fdc79 DB |
3137 | rhs.var = anything_id; |
3138 | rhs.type = ADDRESSOF; | |
3139 | rhs.offset = 0; | |
3140 | ||
3141 | for (p = get_varinfo (lhs.var); p; p = p->next) | |
3142 | { | |
3143 | struct constraint_expr temp = lhs; | |
3144 | temp.var = p->id; | |
3145 | process_constraint (new_constraint (temp, rhs)); | |
3146 | } | |
3147 | } | |
3148 | ||
3149 | } | |
3150 | ||
3151 | /* Set bits in INTO corresponding to the variable uids in solution set | |
3152 | FROM */ | |
3153 | ||
3154 | static void | |
3155 | set_uids_in_ptset (bitmap into, bitmap from) | |
3156 | { | |
3157 | unsigned int i; | |
3158 | bitmap_iterator bi; | |
e8ca4159 DN |
3159 | bool found_anyoffset = false; |
3160 | subvar_t sv; | |
910fdc79 DB |
3161 | |
3162 | EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi) | |
3163 | { | |
3164 | varinfo_t vi = get_varinfo (i); | |
e8ca4159 DN |
3165 | |
3166 | /* If we find ANYOFFSET in the solution and the solution | |
3167 | includes SFTs for some structure, then all the SFTs in that | |
3168 | structure will need to be added to the alias set. */ | |
3169 | if (vi->id == anyoffset_id) | |
3170 | { | |
3171 | found_anyoffset = true; | |
3172 | continue; | |
3173 | } | |
3174 | ||
3175 | /* The only artificial variables that are allowed in a may-alias | |
3176 | set are heap variables. */ | |
3177 | if (vi->is_artificial_var && !vi->is_heap_var) | |
3178 | continue; | |
58b82d2b | 3179 | |
58b82d2b DB |
3180 | if (vi->has_union && get_subvars_for_var (vi->decl) != NULL) |
3181 | { | |
e8ca4159 DN |
3182 | /* Variables containing unions may need to be converted to |
3183 | their SFT's, because SFT's can have unions and we cannot. */ | |
3184 | for (sv = get_subvars_for_var (vi->decl); sv; sv = sv->next) | |
a3648cfc | 3185 | bitmap_set_bit (into, DECL_UID (sv->var)); |
58b82d2b | 3186 | } |
58b82d2b | 3187 | else if (TREE_CODE (vi->decl) == VAR_DECL |
e8ca4159 DN |
3188 | || TREE_CODE (vi->decl) == PARM_DECL) |
3189 | { | |
3190 | if (found_anyoffset | |
3191 | && var_can_have_subvars (vi->decl) | |
3192 | && get_subvars_for_var (vi->decl)) | |
3193 | { | |
3194 | /* If ANYOFFSET is in the solution set and VI->DECL is | |
3195 | an aggregate variable with sub-variables, then any of | |
3196 | the SFTs inside VI->DECL may have been accessed. Add | |
3197 | all the sub-vars for VI->DECL. */ | |
3198 | for (sv = get_subvars_for_var (vi->decl); sv; sv = sv->next) | |
3199 | bitmap_set_bit (into, DECL_UID (sv->var)); | |
3200 | } | |
3201 | else if (var_can_have_subvars (vi->decl) | |
3202 | && get_subvars_for_var (vi->decl)) | |
3203 | { | |
3204 | /* If VI->DECL is an aggregate for which we created | |
3205 | SFTs, add the SFT corresponding to VI->OFFSET. */ | |
3206 | tree sft = get_subvar_at (vi->decl, vi->offset); | |
3207 | bitmap_set_bit (into, DECL_UID (sft)); | |
3208 | } | |
3209 | else | |
3210 | { | |
3211 | /* Otherwise, just add VI->DECL to the alias set. */ | |
3212 | bitmap_set_bit (into, DECL_UID (vi->decl)); | |
3213 | } | |
3214 | } | |
910fdc79 DB |
3215 | } |
3216 | } | |
e8ca4159 DN |
3217 | |
3218 | ||
3219 | static bool have_alias_info = false; | |
910fdc79 DB |
3220 | |
3221 | /* Given a pointer variable P, fill in its points-to set, or return | |
3222 | false if we can't. */ | |
3223 | ||
3224 | bool | |
3225 | find_what_p_points_to (tree p) | |
3226 | { | |
3227 | unsigned int id = 0; | |
e8ca4159 | 3228 | |
910fdc79 DB |
3229 | if (!have_alias_info) |
3230 | return false; | |
e8ca4159 | 3231 | |
910fdc79 DB |
3232 | if (lookup_id_for_tree (p, &id)) |
3233 | { | |
3234 | varinfo_t vi = get_varinfo (id); | |
3235 | ||
3236 | if (vi->is_artificial_var) | |
3237 | return false; | |
3238 | ||
e8ca4159 | 3239 | /* See if this is a field or a structure. */ |
910fdc79 DB |
3240 | if (vi->size != vi->fullsize) |
3241 | { | |
e8ca4159 DN |
3242 | /* Nothing currently asks about structure fields directly, |
3243 | but when they do, we need code here to hand back the | |
3244 | points-to set. */ | |
910fdc79 DB |
3245 | if (!var_can_have_subvars (vi->decl) |
3246 | || get_subvars_for_var (vi->decl) == NULL) | |
3247 | return false; | |
3248 | } | |
3249 | else | |
3250 | { | |
3251 | struct ptr_info_def *pi = get_ptr_info (p); | |
3252 | unsigned int i; | |
3253 | bitmap_iterator bi; | |
3254 | ||
3255 | /* This variable may have been collapsed, let's get the real | |
3256 | variable. */ | |
3257 | vi = get_varinfo (vi->node); | |
3258 | ||
e8ca4159 DN |
3259 | /* Translate artificial variables into SSA_NAME_PTR_INFO |
3260 | attributes. */ | |
910fdc79 DB |
3261 | EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi) |
3262 | { | |
e8ca4159 DN |
3263 | varinfo_t vi = get_varinfo (i); |
3264 | ||
3265 | if (vi->is_artificial_var) | |
3266 | { | |
3267 | /* FIXME. READONLY should be handled better so that | |
3268 | flow insensitive aliasing can disregard writeable | |
3269 | aliases. */ | |
3270 | if (vi->id == nothing_id) | |
3271 | pi->pt_null = 1; | |
3272 | else if (vi->id == anything_id) | |
3273 | pi->pt_anything = 1; | |
3274 | else if (vi->id == readonly_id) | |
3275 | pi->pt_anything = 1; | |
3276 | else if (vi->id == integer_id) | |
3277 | pi->pt_anything = 1; | |
3278 | else if (vi->is_heap_var) | |
3279 | pi->pt_global_mem = 1; | |
3280 | } | |
910fdc79 | 3281 | } |
e8ca4159 DN |
3282 | |
3283 | if (pi->pt_anything) | |
3284 | return false; | |
3285 | ||
910fdc79 DB |
3286 | if (!pi->pt_vars) |
3287 | pi->pt_vars = BITMAP_GGC_ALLOC (); | |
e8ca4159 | 3288 | |
910fdc79 | 3289 | set_uids_in_ptset (pi->pt_vars, vi->solution); |
e8ca4159 DN |
3290 | |
3291 | if (bitmap_empty_p (pi->pt_vars)) | |
3292 | pi->pt_vars = NULL; | |
3293 | ||
910fdc79 DB |
3294 | return true; |
3295 | } | |
3296 | } | |
e8ca4159 | 3297 | |
910fdc79 DB |
3298 | return false; |
3299 | } | |
3300 | ||
63a4ef6f | 3301 | |
910fdc79 DB |
3302 | /* Initialize things necessary to perform PTA */ |
3303 | ||
3304 | static void | |
3305 | init_alias_vars (void) | |
3306 | { | |
3307 | bitmap_obstack_initialize (&ptabitmap_obstack); | |
3308 | } | |
3309 | ||
910fdc79 | 3310 | |
63a4ef6f DN |
3311 | /* Dump points-to information to OUTFILE. */ |
3312 | ||
3313 | void | |
910fdc79 DB |
3314 | dump_sa_points_to_info (FILE *outfile) |
3315 | { | |
910fdc79 | 3316 | unsigned int i; |
63a4ef6f | 3317 | |
e8ca4159 | 3318 | fprintf (outfile, "\nPoints-to sets\n\n"); |
63a4ef6f | 3319 | |
910fdc79 DB |
3320 | if (dump_flags & TDF_STATS) |
3321 | { | |
3322 | fprintf (outfile, "Stats:\n"); | |
63a4ef6f DN |
3323 | fprintf (outfile, "Total vars: %d\n", stats.total_vars); |
3324 | fprintf (outfile, "Statically unified vars: %d\n", | |
3325 | stats.unified_vars_static); | |
3326 | fprintf (outfile, "Collapsed vars: %d\n", stats.collapsed_vars); | |
3327 | fprintf (outfile, "Dynamically unified vars: %d\n", | |
3328 | stats.unified_vars_dynamic); | |
3329 | fprintf (outfile, "Iterations: %d\n", stats.iterations); | |
910fdc79 | 3330 | } |
63a4ef6f | 3331 | |
910fdc79 DB |
3332 | for (i = 0; i < VEC_length (varinfo_t, varmap); i++) |
3333 | dump_solution_for_var (outfile, i); | |
3334 | } | |
3335 | ||
3336 | ||
63a4ef6f DN |
3337 | /* Debug points-to information to stderr. */ |
3338 | ||
3339 | void | |
3340 | debug_sa_points_to_info (void) | |
3341 | { | |
3342 | dump_sa_points_to_info (stderr); | |
3343 | } | |
3344 | ||
3345 | ||
910fdc79 DB |
3346 | /* Initialize the always-existing constraint variables for NULL |
3347 | ANYTHING, READONLY, and INTEGER */ | |
3348 | ||
3349 | static void | |
3350 | init_base_vars (void) | |
3351 | { | |
3352 | struct constraint_expr lhs, rhs; | |
3353 | ||
3354 | /* Create the NULL variable, used to represent that a variable points | |
3355 | to NULL. */ | |
3356 | nothing_tree = create_tmp_var_raw (void_type_node, "NULL"); | |
3357 | var_nothing = new_var_info (nothing_tree, 0, "NULL", 0); | |
3358 | insert_id_for_tree (nothing_tree, 0); | |
3359 | var_nothing->is_artificial_var = 1; | |
3360 | var_nothing->offset = 0; | |
3361 | var_nothing->size = ~0; | |
3362 | var_nothing->fullsize = ~0; | |
3363 | nothing_id = 0; | |
3364 | VEC_safe_push (varinfo_t, gc, varmap, var_nothing); | |
3365 | ||
3366 | /* Create the ANYTHING variable, used to represent that a variable | |
3367 | points to some unknown piece of memory. */ | |
3368 | anything_tree = create_tmp_var_raw (void_type_node, "ANYTHING"); | |
3369 | var_anything = new_var_info (anything_tree, 1, "ANYTHING", 1); | |
3370 | insert_id_for_tree (anything_tree, 1); | |
3371 | var_anything->is_artificial_var = 1; | |
3372 | var_anything->size = ~0; | |
3373 | var_anything->offset = 0; | |
3374 | var_anything->next = NULL; | |
3375 | var_anything->fullsize = ~0; | |
3376 | anything_id = 1; | |
3377 | ||
3378 | /* Anything points to anything. This makes deref constraints just | |
3379 | work in the presence of linked list and other p = *p type loops, | |
3380 | by saying that *ANYTHING = ANYTHING. */ | |
3381 | VEC_safe_push (varinfo_t, gc, varmap, var_anything); | |
3382 | lhs.type = SCALAR; | |
3383 | lhs.var = anything_id; | |
3384 | lhs.offset = 0; | |
3385 | rhs.type = ADDRESSOF; | |
3386 | rhs.var = anything_id; | |
3387 | rhs.offset = 0; | |
3388 | var_anything->address_taken = true; | |
e8ca4159 | 3389 | |
a5eadacc DB |
3390 | /* This specifically does not use process_constraint because |
3391 | process_constraint ignores all anything = anything constraints, since all | |
3392 | but this one are redundant. */ | |
3393 | VEC_safe_push (constraint_t, gc, constraints, new_constraint (lhs, rhs)); | |
910fdc79 DB |
3394 | |
3395 | /* Create the READONLY variable, used to represent that a variable | |
3396 | points to readonly memory. */ | |
3397 | readonly_tree = create_tmp_var_raw (void_type_node, "READONLY"); | |
3398 | var_readonly = new_var_info (readonly_tree, 2, "READONLY", 2); | |
3399 | var_readonly->is_artificial_var = 1; | |
3400 | var_readonly->offset = 0; | |
3401 | var_readonly->size = ~0; | |
3402 | var_readonly->fullsize = ~0; | |
3403 | var_readonly->next = NULL; | |
3404 | insert_id_for_tree (readonly_tree, 2); | |
3405 | readonly_id = 2; | |
3406 | VEC_safe_push (varinfo_t, gc, varmap, var_readonly); | |
3407 | ||
3408 | /* readonly memory points to anything, in order to make deref | |
3409 | easier. In reality, it points to anything the particular | |
3410 | readonly variable can point to, but we don't track this | |
607fb860 | 3411 | separately. */ |
910fdc79 DB |
3412 | lhs.type = SCALAR; |
3413 | lhs.var = readonly_id; | |
3414 | lhs.offset = 0; | |
3415 | rhs.type = ADDRESSOF; | |
3416 | rhs.var = anything_id; | |
3417 | rhs.offset = 0; | |
910fdc79 DB |
3418 | |
3419 | process_constraint (new_constraint (lhs, rhs)); | |
3420 | ||
3421 | /* Create the INTEGER variable, used to represent that a variable points | |
3422 | to an INTEGER. */ | |
3423 | integer_tree = create_tmp_var_raw (void_type_node, "INTEGER"); | |
3424 | var_integer = new_var_info (integer_tree, 3, "INTEGER", 3); | |
3425 | insert_id_for_tree (integer_tree, 3); | |
3426 | var_integer->is_artificial_var = 1; | |
3427 | var_integer->size = ~0; | |
3428 | var_integer->fullsize = ~0; | |
3429 | var_integer->offset = 0; | |
3430 | var_integer->next = NULL; | |
3431 | integer_id = 3; | |
3432 | VEC_safe_push (varinfo_t, gc, varmap, var_integer); | |
a5eadacc DB |
3433 | |
3434 | /* *INTEGER = ANYTHING, because we don't know where a dereference of a random | |
3435 | integer will point to. */ | |
3436 | lhs.type = SCALAR; | |
3437 | lhs.var = integer_id; | |
3438 | lhs.offset = 0; | |
3439 | rhs.type = ADDRESSOF; | |
3440 | rhs.var = anything_id; | |
3441 | rhs.offset = 0; | |
3442 | process_constraint (new_constraint (lhs, rhs)); | |
e8ca4159 DN |
3443 | |
3444 | /* Create the ANYOFFSET variable, used to represent an arbitrary offset | |
3445 | inside an object. This is similar to ANYTHING, but less drastic. | |
3446 | It means that the pointer can point anywhere inside an object, | |
3447 | but not outside of it. */ | |
3448 | anyoffset_tree = create_tmp_var_raw (void_type_node, "ANYOFFSET"); | |
3449 | anyoffset_id = 4; | |
3450 | var_anyoffset = new_var_info (anyoffset_tree, anyoffset_id, "ANYOFFSET", | |
3451 | anyoffset_id); | |
3452 | insert_id_for_tree (anyoffset_tree, anyoffset_id); | |
3453 | var_anyoffset->is_artificial_var = 1; | |
3454 | var_anyoffset->size = ~0; | |
3455 | var_anyoffset->offset = 0; | |
3456 | var_anyoffset->next = NULL; | |
3457 | var_anyoffset->fullsize = ~0; | |
3458 | VEC_safe_push (varinfo_t, gc, varmap, var_anyoffset); | |
3459 | ||
3460 | /* ANYOFFSET points to ANYOFFSET. */ | |
3461 | lhs.type = SCALAR; | |
3462 | lhs.var = anyoffset_id; | |
3463 | lhs.offset = 0; | |
3464 | rhs.type = ADDRESSOF; | |
3465 | rhs.var = anyoffset_id; | |
3466 | rhs.offset = 0; | |
3467 | process_constraint (new_constraint (lhs, rhs)); | |
910fdc79 DB |
3468 | } |
3469 | ||
3470 | ||
3471 | /* Create points-to sets for the current function. See the comments | |
3472 | at the start of the file for an algorithmic overview. */ | |
3473 | ||
e8ca4159 DN |
3474 | void |
3475 | compute_points_to_sets (struct alias_info *ai) | |
910fdc79 DB |
3476 | { |
3477 | basic_block bb; | |
e8ca4159 DN |
3478 | |
3479 | timevar_push (TV_TREE_PTA); | |
3480 | ||
910fdc79 DB |
3481 | init_alias_vars (); |
3482 | ||
3483 | constraint_pool = create_alloc_pool ("Constraint pool", | |
3484 | sizeof (struct constraint), 30); | |
3485 | variable_info_pool = create_alloc_pool ("Variable info pool", | |
3486 | sizeof (struct variable_info), 30); | |
3487 | constraint_edge_pool = create_alloc_pool ("Constraint edges", | |
3488 | sizeof (struct constraint_edge), 30); | |
3489 | ||
3490 | constraints = VEC_alloc (constraint_t, gc, 8); | |
3491 | varmap = VEC_alloc (varinfo_t, gc, 8); | |
3492 | id_for_tree = htab_create (10, tree_id_hash, tree_id_eq, free); | |
3493 | memset (&stats, 0, sizeof (stats)); | |
e8ca4159 | 3494 | |
910fdc79 DB |
3495 | init_base_vars (); |
3496 | ||
3497 | intra_create_variable_infos (); | |
3498 | ||
3499 | /* Now walk all statements and derive aliases. */ | |
3500 | FOR_EACH_BB (bb) | |
3501 | { | |
3502 | block_stmt_iterator bsi; | |
3503 | tree phi; | |
3504 | ||
3505 | for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi)) | |
3506 | if (is_gimple_reg (PHI_RESULT (phi))) | |
e8ca4159 | 3507 | find_func_aliases (phi, ai); |
910fdc79 DB |
3508 | |
3509 | for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) | |
e8ca4159 | 3510 | find_func_aliases (bsi_stmt (bsi), ai); |
910fdc79 DB |
3511 | } |
3512 | ||
3513 | build_constraint_graph (); | |
3514 | ||
3515 | if (dump_file) | |
3516 | { | |
e8ca4159 | 3517 | fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n"); |
910fdc79 DB |
3518 | dump_constraints (dump_file); |
3519 | } | |
3520 | ||
3521 | if (dump_file) | |
e8ca4159 DN |
3522 | fprintf (dump_file, "\nCollapsing static cycles and doing variable " |
3523 | "substitution:\n"); | |
910fdc79 DB |
3524 | |
3525 | find_and_collapse_graph_cycles (graph, false); | |
3526 | perform_var_substitution (graph); | |
3527 | ||
3528 | if (dump_file) | |
e8ca4159 | 3529 | fprintf (dump_file, "\nSolving graph:\n"); |
910fdc79 DB |
3530 | |
3531 | solve_graph (graph); | |
3532 | ||
3533 | if (dump_file) | |
3534 | dump_sa_points_to_info (dump_file); | |
3535 | ||
3536 | have_alias_info = true; | |
e8ca4159 DN |
3537 | |
3538 | timevar_pop (TV_TREE_PTA); | |
910fdc79 DB |
3539 | } |
3540 | ||
910fdc79 DB |
3541 | |
3542 | /* Delete created points-to sets. */ | |
3543 | ||
e8ca4159 DN |
3544 | void |
3545 | delete_points_to_sets (void) | |
910fdc79 DB |
3546 | { |
3547 | htab_delete (id_for_tree); | |
3548 | free_alloc_pool (variable_info_pool); | |
3549 | free_alloc_pool (constraint_pool); | |
3550 | free_alloc_pool (constraint_edge_pool); | |
3551 | bitmap_obstack_release (&ptabitmap_obstack); | |
3552 | have_alias_info = false; | |
3553 | } |