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