Line data Source code
1 : /* Andersen-style solver for tree based points-to analysis
2 : Copyright (C) 2005-2026 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 3 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; see the file COPYING3. If not see
19 : <http://www.gnu.org/licenses/>. */
20 :
21 : #include "config.h"
22 : #include "system.h"
23 : #include "coretypes.h"
24 : #include "backend.h"
25 :
26 : #include "tree-ssa-structalias.h"
27 : #include "pta-andersen.h"
28 :
29 : /* During variable substitution and the offline version of indirect
30 : cycle finding, we create nodes to represent dereferences and
31 : address taken constraints. These represent where these start and
32 : end. */
33 : #define FIRST_REF_NODE (varmap).length ()
34 : #define LAST_REF_NODE (FIRST_REF_NODE + (FIRST_REF_NODE - 1))
35 :
36 : #define EXECUTE_IF_IN_NONNULL_BITMAP(a, b, c, d) \
37 : if (a) \
38 : EXECUTE_IF_SET_IN_BITMAP (a, b, c, d)
39 :
40 : using namespace pointer_analysis;
41 :
42 : /* Used for predecessor bitmaps. */
43 : static bitmap_obstack predbitmap_obstack;
44 :
45 : /* Used for per-solver-iteration bitmaps. */
46 : static bitmap_obstack iteration_obstack;
47 :
48 : typedef struct constraint_graph *constraint_graph_t;
49 :
50 : /* The constraint graph is represented as an array of bitmaps
51 : containing successor nodes. */
52 :
53 : struct constraint_graph
54 : {
55 : /* Size of this graph, which may be different than the number of
56 : nodes in the variable map. */
57 : unsigned int size;
58 :
59 : /* Explicit successors of each node. */
60 : bitmap *succs;
61 :
62 : /* Implicit predecessors of each node (Used for variable
63 : substitution). */
64 : bitmap *implicit_preds;
65 :
66 : /* Explicit predecessors of each node (Used for variable substitution). */
67 : bitmap *preds;
68 :
69 : /* Indirect cycle representatives, or -1 if the node has no indirect
70 : cycles. */
71 : int *indirect_cycles;
72 :
73 : /* Representative node for a node. rep[a] == a unless the node has
74 : been unified. */
75 : unsigned int *rep;
76 :
77 : /* Equivalence class representative for a label. This is used for
78 : variable substitution. */
79 : int *eq_rep;
80 :
81 : /* Pointer equivalence label for a node. All nodes with the same
82 : pointer equivalence label can be unified together at some point
83 : (either during constraint optimization or after the constraint
84 : graph is built). */
85 : unsigned int *pe;
86 :
87 : /* Pointer equivalence representative for a label. This is used to
88 : handle nodes that are pointer equivalent but not location
89 : equivalent. We can unite these once the addressof constraints
90 : are transformed into initial points-to sets. */
91 : int *pe_rep;
92 :
93 : /* Pointer equivalence label for each node, used during variable
94 : substitution. */
95 : unsigned int *pointer_label;
96 :
97 : /* Location equivalence label for each node, used during location
98 : equivalence finding. */
99 : unsigned int *loc_label;
100 :
101 : /* Pointed-by set for each node, used during location equivalence
102 : finding. This is pointed-by rather than pointed-to, because it
103 : is constructed using the predecessor graph. */
104 : bitmap *pointed_by;
105 :
106 : /* Points to sets for pointer equivalence. This is *not* the actual
107 : points-to sets for nodes. */
108 : bitmap *points_to;
109 :
110 : /* Bitmap of nodes where the bit is set if the node is a direct
111 : node. Used for variable substitution. */
112 : sbitmap direct_nodes;
113 :
114 : /* Bitmap of nodes where the bit is set if the node is address
115 : taken. Used for variable substitution. */
116 : bitmap address_taken;
117 :
118 : /* Vector of complex constraints for each graph node. Complex
119 : constraints are those involving dereferences or offsets that are
120 : not 0. */
121 : vec<constraint_t> *complex;
122 : };
123 :
124 : static constraint_graph_t graph;
125 :
126 : static void unify_nodes (constraint_graph_t, unsigned int, unsigned int, bool);
127 :
128 :
129 : /* Return the representative node for NODE, if NODE has been unioned
130 : with another NODE.
131 : This function performs path compression along the way to finding
132 : the representative. */
133 :
134 : static unsigned int
135 8723047174 : find (unsigned int node)
136 : {
137 8723047174 : gcc_checking_assert (node < graph->size);
138 8723047174 : if (graph->rep[node] != node)
139 428839463 : return graph->rep[node] = find (graph->rep[node]);
140 : return node;
141 : }
142 :
143 : /* Union the TO and FROM nodes to the TO nodes.
144 : Note that at some point in the future, we may want to do
145 : union-by-rank, in which case we are going to have to return the
146 : node we unified to. */
147 :
148 : static bool
149 616713206 : unite (unsigned int to, unsigned int from)
150 : {
151 616713206 : gcc_checking_assert (to < graph->size && from < graph->size);
152 616713206 : if (to != from
153 120740412 : && graph->rep[from] != to
154 : /* Do not merge an artificial variable into another, this will
155 : explode solution sets unnecessarily. */
156 858072887 : && (from >= FIRST_REF_NODE || !get_varinfo (from)->is_artificial_var))
157 : {
158 44010917 : graph->rep[from] = to;
159 44010917 : return true;
160 : }
161 : return false;
162 : }
163 :
164 : /* Perform path compression for all nodes in the node representatives
165 : union-find structure. */
166 :
167 : static void
168 4568954 : union_find_compress_all (void)
169 : {
170 4568954 : unsigned int i;
171 238452916 : for (i = 0; i < graph->size; i++)
172 233883962 : find (i);
173 4568954 : }
174 :
175 : /* Print the constraint graph in dot format. */
176 :
177 : static void
178 6 : dump_constraint_graph (FILE *file)
179 : {
180 6 : unsigned int i;
181 :
182 : /* Only print the graph if it has already been initialized: */
183 6 : if (!graph)
184 : return;
185 :
186 : /* Prints the header of the dot file: */
187 6 : fprintf (file, "strict digraph {\n");
188 6 : fprintf (file, " node [\n shape = box\n ]\n");
189 6 : fprintf (file, " edge [\n fontsize = \"12\"\n ]\n");
190 6 : fprintf (file, "\n // List of nodes and complex constraints in "
191 : "the constraint graph:\n");
192 :
193 : /* The next lines print the nodes in the graph together with the
194 : complex constraints attached to them. */
195 86 : for (i = 1; i < graph->size; i++)
196 : {
197 148 : if (i == FIRST_REF_NODE)
198 0 : continue;
199 74 : if (find (i) != i)
200 2 : continue;
201 72 : if (i < FIRST_REF_NODE)
202 72 : fprintf (file, "\"%s\"", get_varinfo (i)->name);
203 : else
204 0 : fprintf (file, "\"*%s\"", get_varinfo (i - FIRST_REF_NODE)->name);
205 72 : if (graph->complex[i].exists ())
206 : {
207 16 : unsigned j;
208 16 : constraint_t c;
209 16 : fprintf (file, " [label=\"\\N\\n");
210 70 : for (j = 0; graph->complex[i].iterate (j, &c); ++j)
211 : {
212 38 : dump_constraint (file, c);
213 38 : fprintf (file, "\\l");
214 : }
215 16 : fprintf (file, "\"]");
216 : }
217 72 : fprintf (file, ";\n");
218 : }
219 :
220 : /* Go over the edges. */
221 6 : fprintf (file, "\n // Edges in the constraint graph:\n");
222 86 : for (i = 1; i < graph->size; i++)
223 : {
224 74 : unsigned j;
225 74 : bitmap_iterator bi;
226 74 : if (find (i) != i)
227 2 : continue;
228 102 : EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i], 0, j, bi)
229 : {
230 30 : unsigned to = find (j);
231 30 : if (i == to)
232 0 : continue;
233 30 : if (i < FIRST_REF_NODE)
234 30 : fprintf (file, "\"%s\"", get_varinfo (i)->name);
235 : else
236 0 : fprintf (file, "\"*%s\"", get_varinfo (i - FIRST_REF_NODE)->name);
237 30 : fprintf (file, " -> ");
238 30 : if (to < FIRST_REF_NODE)
239 30 : fprintf (file, "\"%s\"", get_varinfo (to)->name);
240 : else
241 0 : fprintf (file, "\"*%s\"", get_varinfo (to - FIRST_REF_NODE)->name);
242 30 : fprintf (file, ";\n");
243 : }
244 : }
245 :
246 : /* Prints the tail of the dot file. */
247 6 : fprintf (file, "}\n");
248 : }
249 :
250 : /* Print out the constraint graph to stderr. */
251 :
252 : DEBUG_FUNCTION void
253 0 : debug_constraint_graph (void)
254 : {
255 0 : dump_constraint_graph (stderr);
256 0 : }
257 :
258 :
259 : /* SOLVER FUNCTIONS
260 :
261 : The solver is a simple worklist solver, that works on the following
262 : algorithm:
263 :
264 : sbitmap changed_nodes = all zeroes;
265 : changed_count = 0;
266 : For each node that is not already collapsed:
267 : changed_count++;
268 : set bit in changed nodes
269 :
270 : while (changed_count > 0)
271 : {
272 : compute topological ordering for constraint graph
273 :
274 : find and collapse cycles in the constraint graph (updating
275 : changed if necessary)
276 :
277 : for each node (n) in the graph in topological order:
278 : changed_count--;
279 :
280 : Process each complex constraint associated with the node,
281 : updating changed if necessary.
282 :
283 : For each outgoing edge from n, propagate the solution from n to
284 : the destination of the edge, updating changed as necessary.
285 :
286 : } */
287 :
288 : /* Return true if two constraint expressions A and B are equal. */
289 :
290 : static bool
291 18115123 : constraint_expr_equal (struct constraint_expr a, struct constraint_expr b)
292 : {
293 10930502 : return a.type == b.type && a.var == b.var && a.offset == b.offset;
294 : }
295 :
296 : /* Return true if constraint expression A is less than constraint expression
297 : B. This is just arbitrary, but consistent, in order to give them an
298 : ordering. */
299 :
300 : static bool
301 451882329 : constraint_expr_less (struct constraint_expr a, struct constraint_expr b)
302 : {
303 0 : if (a.type == b.type)
304 : {
305 268878823 : if (a.var == b.var)
306 202761601 : return a.offset < b.offset;
307 : else
308 66117222 : return a.var < b.var;
309 : }
310 : else
311 183003506 : return a.type < b.type;
312 : }
313 :
314 : /* Return true if constraint A is less than constraint B. This is just
315 : arbitrary, but consistent, in order to give them an ordering. */
316 :
317 : static bool
318 248946286 : constraint_less (const constraint_t &a, const constraint_t &b)
319 : {
320 497892572 : if (constraint_expr_less (a->lhs, b->lhs))
321 : return true;
322 214125360 : else if (constraint_expr_less (b->lhs, a->lhs))
323 : return false;
324 : else
325 95873363 : return constraint_expr_less (a->rhs, b->rhs);
326 : }
327 :
328 : /* Return true if two constraints A and B are equal. */
329 :
330 : static bool
331 11918293 : constraint_equal (const constraint &a, const constraint &b)
332 : {
333 18115123 : return constraint_expr_equal (a.lhs, b.lhs)
334 11918293 : && constraint_expr_equal (a.rhs, b.rhs);
335 : }
336 :
337 : /* Find a constraint LOOKFOR in the sorted constraint vector VEC. */
338 :
339 : static constraint_t
340 12109 : constraint_vec_find (vec<constraint_t> vec,
341 : constraint &lookfor)
342 : {
343 12109 : unsigned int place;
344 12109 : constraint_t found;
345 :
346 12109 : if (!vec.exists ())
347 : return NULL;
348 :
349 9929 : place = vec.lower_bound (&lookfor, constraint_less);
350 9929 : if (place >= vec.length ())
351 : return NULL;
352 4276 : found = vec[place];
353 4276 : if (!constraint_equal (*found, lookfor))
354 4189 : return NULL;
355 : return found;
356 : }
357 :
358 : /* Union two constraint vectors, TO and FROM. Put the result in TO.
359 : Returns true of TO set is changed. */
360 :
361 : static bool
362 43890174 : constraint_set_union (vec<constraint_t> *to,
363 : vec<constraint_t> *from)
364 : {
365 43890174 : int i;
366 43890174 : constraint_t c;
367 43890174 : bool any_change = false;
368 :
369 43902283 : FOR_EACH_VEC_ELT (*from, i, c)
370 : {
371 12109 : if (constraint_vec_find (*to, *c) == NULL)
372 : {
373 12022 : unsigned int place = to->lower_bound (c, constraint_less);
374 12022 : to->safe_insert (place, c);
375 12022 : any_change = true;
376 : }
377 : }
378 43890174 : return any_change;
379 : }
380 :
381 : /* Expands the solution in SET to all sub-fields of variables included. */
382 :
383 : static bitmap
384 136701474 : solution_set_expand (bitmap set, bitmap *expanded)
385 : {
386 136701474 : bitmap_iterator bi;
387 136701474 : unsigned j;
388 :
389 136701474 : if (*expanded)
390 : return *expanded;
391 :
392 76466681 : *expanded = BITMAP_ALLOC (&iteration_obstack);
393 :
394 : /* In a first pass expand variables, once for each head to avoid
395 : quadratic behavior, to include all sub-fields. */
396 76466681 : unsigned prev_head = 0;
397 261223517 : EXECUTE_IF_SET_IN_BITMAP (set, 0, j, bi)
398 : {
399 184756836 : varinfo_t v = get_varinfo (j);
400 184756836 : if (v->is_artificial_var
401 91301187 : || v->is_full_var)
402 110034770 : continue;
403 74722066 : if (v->head != prev_head)
404 : {
405 19066930 : varinfo_t head = get_varinfo (v->head);
406 19066930 : unsigned num = 1;
407 112440049 : for (varinfo_t n = vi_next (head); n != NULL; n = vi_next (n))
408 : {
409 93373119 : if (n->id != head->id + num)
410 : {
411 : /* Usually sub variables are adjacent but since we
412 : create pointed-to restrict representatives there
413 : can be gaps as well. */
414 15541 : bitmap_set_range (*expanded, head->id, num);
415 15541 : head = n;
416 15541 : num = 1;
417 : }
418 : else
419 93357578 : num++;
420 : }
421 :
422 19066930 : bitmap_set_range (*expanded, head->id, num);
423 19066930 : prev_head = v->head;
424 : }
425 : }
426 :
427 : /* And finally set the rest of the bits from SET in an efficient way. */
428 76466681 : bitmap_ior_into (*expanded, set);
429 :
430 76466681 : return *expanded;
431 : }
432 :
433 : /* Union solution sets TO and DELTA, and add INC to each member of DELTA in the
434 : process. */
435 :
436 : static bool
437 86063713 : set_union_with_increment (bitmap to, bitmap delta, HOST_WIDE_INT inc,
438 : bitmap *expanded_delta)
439 : {
440 86063713 : bool changed = false;
441 86063713 : bitmap_iterator bi;
442 86063713 : unsigned int i;
443 :
444 : /* If the solution of DELTA contains anything it is good enough to transfer
445 : this to TO. */
446 86063713 : if (bitmap_bit_p (delta, anything_id))
447 1193451 : return bitmap_set_bit (to, anything_id);
448 :
449 : /* If the offset is unknown we have to expand the solution to
450 : all subfields. */
451 84870262 : if (inc == UNKNOWN_OFFSET)
452 : {
453 83896770 : delta = solution_set_expand (delta, expanded_delta);
454 83896770 : changed |= bitmap_ior_into (to, delta);
455 83896770 : return changed;
456 : }
457 :
458 : /* For non-zero offset union the offsetted solution into the destination. */
459 3360001 : EXECUTE_IF_SET_IN_BITMAP (delta, 0, i, bi)
460 : {
461 2386509 : varinfo_t vi = get_varinfo (i);
462 :
463 : /* If this is a variable with just one field just set its bit
464 : in the result. */
465 2386509 : if (vi->is_artificial_var
466 1096771 : || vi->is_unknown_size_var
467 953579 : || vi->is_full_var)
468 1624730 : changed |= bitmap_set_bit (to, i);
469 : else
470 : {
471 761779 : HOST_WIDE_INT fieldoffset = vi->offset + inc;
472 761779 : unsigned HOST_WIDE_INT size = vi->size;
473 :
474 : /* If the offset makes the pointer point to before the
475 : variable use offset zero for the field lookup. */
476 761779 : if (fieldoffset < 0)
477 47442 : vi = get_varinfo (vi->head);
478 : else
479 714337 : vi = first_or_preceding_vi_for_offset (vi, fieldoffset);
480 :
481 1421952 : do
482 : {
483 1421952 : changed |= bitmap_set_bit (to, vi->id);
484 1421952 : if (vi->is_full_var
485 1421912 : || vi->next == 0)
486 : break;
487 :
488 : /* We have to include all fields that overlap the current field
489 : shifted by inc. */
490 950284 : vi = vi_next (vi);
491 : }
492 950284 : while (vi->offset < fieldoffset + size);
493 : }
494 : }
495 :
496 : return changed;
497 : }
498 :
499 : /* Insert constraint C into the list of complex constraints for graph
500 : node VAR. */
501 :
502 : static void
503 149605289 : insert_into_complex (constraint_graph_t graph,
504 : unsigned int var, constraint_t c)
505 : {
506 149605289 : vec<constraint_t> complex = graph->complex[var];
507 149605289 : unsigned int place = complex.lower_bound (c, constraint_less);
508 :
509 : /* Only insert constraints that do not already exist. */
510 149605289 : if (place >= complex.length ()
511 101844293 : || !constraint_equal (*c, *complex[place]))
512 148115616 : graph->complex[var].safe_insert (place, c);
513 149605289 : }
514 :
515 :
516 : /* Condense two variable nodes into a single variable node, by moving
517 : all associated info from FROM to TO. Returns true if TO node's
518 : constraint set changes after the merge. */
519 :
520 : static bool
521 43890174 : merge_node_constraints (constraint_graph_t graph, unsigned int to,
522 : unsigned int from)
523 : {
524 43890174 : unsigned int i;
525 43890174 : constraint_t c;
526 43890174 : bool any_change = false;
527 :
528 43890174 : gcc_checking_assert (find (from) == to);
529 :
530 : /* Move all complex constraints from src node into to node. */
531 43902283 : FOR_EACH_VEC_ELT (graph->complex[from], i, c)
532 : {
533 : /* In complex constraints for node FROM, we may have either
534 : a = *FROM, and *FROM = a, or an offsetted constraint which are
535 : always added to the rhs node's constraints. */
536 :
537 12109 : if (c->rhs.type == DEREF)
538 2919 : c->rhs.var = to;
539 9190 : else if (c->lhs.type == DEREF)
540 4560 : c->lhs.var = to;
541 : else
542 4630 : c->rhs.var = to;
543 :
544 : }
545 43890174 : any_change = constraint_set_union (&graph->complex[to],
546 : &graph->complex[from]);
547 43890174 : graph->complex[from].release ();
548 43890174 : return any_change;
549 : }
550 :
551 : /* Remove edges involving NODE from GRAPH. */
552 :
553 : static void
554 64191984 : clear_edges_for_node (constraint_graph_t graph, unsigned int node)
555 : {
556 64191984 : if (graph->succs[node])
557 799632 : BITMAP_FREE (graph->succs[node]);
558 64191984 : }
559 :
560 : /* Merge GRAPH nodes FROM and TO into node TO. Return whether TO
561 : received new successor edges. */
562 :
563 : static bool
564 43890174 : merge_graph_nodes (constraint_graph_t graph, unsigned int to,
565 : unsigned int from)
566 : {
567 43890174 : if (graph->indirect_cycles[from] != -1)
568 : {
569 : /* If we have indirect cycles with the from node, and we have
570 : none on the to node, the to node has indirect cycles from the
571 : from node now that they are unified.
572 : If indirect cycles exist on both, unify the nodes that they
573 : are in a cycle with, since we know they are in a cycle with
574 : each other. */
575 108 : if (graph->indirect_cycles[to] == -1)
576 83 : graph->indirect_cycles[to] = graph->indirect_cycles[from];
577 : }
578 :
579 : /* Merge all the successor edges. */
580 43890174 : bool new_succs = false;
581 43890174 : if (graph->succs[from])
582 : {
583 799632 : if (!graph->succs[to])
584 414329 : graph->succs[to] = BITMAP_ALLOC (&pta_obstack);
585 799632 : new_succs = bitmap_ior_into (graph->succs[to],
586 799632 : graph->succs[from]);
587 : }
588 :
589 43890174 : clear_edges_for_node (graph, from);
590 43890174 : return new_succs;
591 : }
592 :
593 :
594 : /* Add an indirect graph edge to GRAPH, going from TO to FROM if
595 : it doesn't exist in the graph already. */
596 :
597 : static void
598 302224916 : add_implicit_graph_edge (constraint_graph_t graph, unsigned int to,
599 : unsigned int from)
600 : {
601 302224916 : if (to == from)
602 : return;
603 :
604 302224916 : if (!graph->implicit_preds[to])
605 169232890 : graph->implicit_preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
606 :
607 302224916 : if (bitmap_set_bit (graph->implicit_preds[to], from))
608 283901628 : stats.num_implicit_edges++;
609 : }
610 :
611 : /* Add a predecessor graph edge to GRAPH, going from TO to FROM if
612 : it doesn't exist in the graph already.
613 : Return false if the edge already existed, true otherwise. */
614 :
615 : static void
616 255181244 : add_pred_graph_edge (constraint_graph_t graph, unsigned int to,
617 : unsigned int from)
618 : {
619 255181244 : if (!graph->preds[to])
620 150561964 : graph->preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
621 255181244 : bitmap_set_bit (graph->preds[to], from);
622 255181244 : }
623 :
624 : /* Add a graph edge to GRAPH, going from FROM to TO if
625 : it doesn't exist in the graph already.
626 : Return false if the edge already existed, true otherwise. */
627 :
628 : static bool
629 701720884 : add_graph_edge (constraint_graph_t graph, unsigned int to,
630 : unsigned int from)
631 : {
632 701720884 : if (to == from)
633 : {
634 : return false;
635 : }
636 : else
637 : {
638 701442983 : bool r = false;
639 :
640 701442983 : if (!graph->succs[from])
641 103613527 : graph->succs[from] = BITMAP_ALLOC (&pta_obstack);
642 :
643 : /* The graph solving process does not avoid "triangles", thus
644 : there can be multiple paths from a node to another involving
645 : intermediate other nodes. That causes extra copying which is
646 : most difficult to avoid when the intermediate node is ESCAPED
647 : because there are no edges added from ESCAPED. Avoid
648 : adding the direct edge FROM -> TO when we have FROM -> ESCAPED
649 : and TO contains ESCAPED.
650 : ??? Note this is only a heuristic, it does not prevent the
651 : situation from occurring. The heuristic helps PR38474 and
652 : PR99912 significantly. */
653 701442983 : if (to < FIRST_REF_NODE
654 668762750 : && bitmap_bit_p (graph->succs[from], find (escaped_id))
655 938628021 : && bitmap_bit_p (get_varinfo (find (to))->solution, escaped_id))
656 : {
657 204027214 : stats.num_avoided_edges++;
658 204027214 : return false;
659 : }
660 :
661 497415769 : if (bitmap_set_bit (graph->succs[from], to))
662 : {
663 415561818 : r = true;
664 415561818 : if (to < FIRST_REF_NODE && from < FIRST_REF_NODE)
665 370296188 : stats.num_edges++;
666 : }
667 : return r;
668 : }
669 : }
670 :
671 : /* Initialize the constraint graph structure to contain SIZE nodes. */
672 :
673 : static void
674 4568954 : init_graph (unsigned int size)
675 : {
676 4568954 : unsigned int j;
677 :
678 4568954 : bitmap_obstack_initialize (&predbitmap_obstack);
679 :
680 4568954 : graph = XCNEW (struct constraint_graph);
681 4568954 : graph->size = size;
682 4568954 : graph->succs = XCNEWVEC (bitmap, graph->size);
683 4568954 : graph->indirect_cycles = XNEWVEC (int, graph->size);
684 4568954 : graph->rep = XNEWVEC (unsigned int, graph->size);
685 : /* ??? Macros do not support template types with multiple arguments,
686 : so we use a typedef to work around it. */
687 4568954 : typedef vec<constraint_t> vec_constraint_t_heap;
688 4568954 : graph->complex = XCNEWVEC (vec_constraint_t_heap, size);
689 4568954 : graph->pe = XCNEWVEC (unsigned int, graph->size);
690 4568954 : graph->pe_rep = XNEWVEC (int, graph->size);
691 :
692 472336878 : for (j = 0; j < graph->size; j++)
693 : {
694 467767924 : graph->rep[j] = j;
695 467767924 : graph->pe_rep[j] = -1;
696 467767924 : graph->indirect_cycles[j] = -1;
697 : }
698 4568954 : }
699 :
700 : /* Build the constraint graph, adding only predecessor edges right now. */
701 :
702 : static void
703 4568954 : build_pred_graph (void)
704 : {
705 4568954 : int i;
706 4568954 : constraint_t c;
707 4568954 : unsigned int j;
708 :
709 4568954 : graph->implicit_preds = XCNEWVEC (bitmap, graph->size);
710 4568954 : graph->preds = XCNEWVEC (bitmap, graph->size);
711 4568954 : graph->pointer_label = XCNEWVEC (unsigned int, graph->size);
712 4568954 : graph->loc_label = XCNEWVEC (unsigned int, graph->size);
713 4568954 : graph->pointed_by = XCNEWVEC (bitmap, graph->size);
714 4568954 : graph->points_to = XCNEWVEC (bitmap, graph->size);
715 4568954 : graph->eq_rep = XNEWVEC (int, graph->size);
716 4568954 : graph->direct_nodes = sbitmap_alloc (graph->size);
717 4568954 : graph->address_taken = BITMAP_ALLOC (&predbitmap_obstack);
718 4568954 : bitmap_clear (graph->direct_nodes);
719 :
720 472336878 : for (j = 1; j < FIRST_REF_NODE; j++)
721 : {
722 229315008 : if (!get_varinfo (j)->is_special_var)
723 206470238 : bitmap_set_bit (graph->direct_nodes, j);
724 : }
725 :
726 472336878 : for (j = 0; j < graph->size; j++)
727 467767924 : graph->eq_rep[j] = -1;
728 :
729 476905832 : for (j = 0; j < varmap.length (); j++)
730 233883962 : graph->indirect_cycles[j] = -1;
731 :
732 457619970 : FOR_EACH_VEC_ELT (constraints, i, c)
733 : {
734 453051016 : struct constraint_expr lhs = c->lhs;
735 453051016 : struct constraint_expr rhs = c->rhs;
736 453051016 : unsigned int lhsvar = lhs.var;
737 453051016 : unsigned int rhsvar = rhs.var;
738 :
739 453051016 : if (lhs.type == DEREF)
740 : {
741 : /* *x = y. */
742 37208542 : if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
743 : {
744 32700282 : if (lhs.var == anything_id)
745 0 : add_pred_graph_edge (graph, storedanything_id, rhsvar);
746 : else
747 65400564 : add_pred_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
748 : }
749 : }
750 415842474 : else if (rhs.type == DEREF)
751 : {
752 : /* x = *y */
753 50172587 : if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
754 26945280 : add_pred_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
755 : else
756 36699947 : bitmap_clear_bit (graph->direct_nodes, lhsvar);
757 : }
758 365669887 : else if (rhs.type == ADDRESSOF)
759 : {
760 93216594 : varinfo_t v;
761 :
762 : /* x = &y */
763 93216594 : if (graph->points_to[lhsvar] == NULL)
764 68902047 : graph->points_to[lhsvar] = BITMAP_ALLOC (&predbitmap_obstack);
765 93216594 : bitmap_set_bit (graph->points_to[lhsvar], rhsvar);
766 :
767 93216594 : if (graph->pointed_by[rhsvar] == NULL)
768 22291507 : graph->pointed_by[rhsvar] = BITMAP_ALLOC (&predbitmap_obstack);
769 93216594 : bitmap_set_bit (graph->pointed_by[rhsvar], lhsvar);
770 :
771 : /* Implicitly, *x = y */
772 186433188 : add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
773 :
774 : /* All related variables are no longer direct nodes. */
775 93216594 : bitmap_clear_bit (graph->direct_nodes, rhsvar);
776 93216594 : v = get_varinfo (rhsvar);
777 93216594 : if (!v->is_full_var)
778 : {
779 7771879 : v = get_varinfo (v->head);
780 50504245 : do
781 : {
782 50504245 : bitmap_clear_bit (graph->direct_nodes, v->id);
783 50504245 : v = vi_next (v);
784 : }
785 50504245 : while (v != NULL);
786 : }
787 93216594 : bitmap_set_bit (graph->address_taken, rhsvar);
788 : }
789 272453293 : else if (lhsvar > anything_id
790 272453293 : && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
791 : {
792 : /* x = y */
793 209008322 : add_pred_graph_edge (graph, lhsvar, rhsvar);
794 : /* Implicitly, *x = *y */
795 209008322 : add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar,
796 209008322 : FIRST_REF_NODE + rhsvar);
797 : }
798 63444971 : else if (lhs.offset != 0 || rhs.offset != 0)
799 : {
800 63272644 : if (rhs.offset != 0)
801 63272644 : bitmap_clear_bit (graph->direct_nodes, lhs.var);
802 0 : else if (lhs.offset != 0)
803 0 : bitmap_clear_bit (graph->direct_nodes, rhs.var);
804 : }
805 : }
806 4568954 : }
807 :
808 : /* Build the constraint graph, adding successor edges. */
809 :
810 : static void
811 4568954 : build_succ_graph (void)
812 : {
813 4568954 : unsigned i, t;
814 4568954 : constraint_t c;
815 :
816 457619970 : FOR_EACH_VEC_ELT (constraints, i, c)
817 : {
818 453051016 : struct constraint_expr lhs;
819 453051016 : struct constraint_expr rhs;
820 453051016 : unsigned int lhsvar;
821 453051016 : unsigned int rhsvar;
822 :
823 453051016 : if (!c)
824 2516795 : continue;
825 :
826 450534221 : lhs = c->lhs;
827 450534221 : rhs = c->rhs;
828 450534221 : lhsvar = find (lhs.var);
829 450534221 : rhsvar = find (rhs.var);
830 :
831 450534221 : if (lhs.type == DEREF)
832 : {
833 37169019 : if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
834 : {
835 32680233 : if (lhs.var == anything_id)
836 0 : add_graph_edge (graph, storedanything_id, rhsvar);
837 : else
838 65360466 : add_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
839 : }
840 : }
841 413365202 : else if (rhs.type == DEREF)
842 : {
843 50171657 : if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
844 26943806 : add_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
845 : }
846 363193545 : else if (rhs.type == ADDRESSOF)
847 : {
848 : /* x = &y */
849 93216594 : gcc_checking_assert (find (rhs.var) == rhs.var);
850 93216594 : bitmap_set_bit (get_varinfo (lhsvar)->solution, rhsvar);
851 : }
852 269976951 : else if (lhsvar > anything_id
853 269976951 : && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
854 : {
855 179287531 : add_graph_edge (graph, lhsvar, rhsvar);
856 : }
857 : }
858 :
859 : /* Add edges from STOREDANYTHING to all nodes that can receive pointers. */
860 4568954 : t = find (storedanything_id);
861 201901284 : for (i = integer_id + 1; i < FIRST_REF_NODE; ++i)
862 : {
863 192763376 : if (get_varinfo (i)->may_have_pointers)
864 192739491 : add_graph_edge (graph, find (i), t);
865 : }
866 :
867 : /* Everything stored to ANYTHING also potentially escapes. */
868 4568954 : add_graph_edge (graph, find (escaped_id), t);
869 4568954 : }
870 :
871 :
872 : /* Changed variables on the last iteration. */
873 : static bitmap changed;
874 :
875 : /* Strongly Connected Component visitation info. */
876 :
877 : class scc_info
878 : {
879 : public:
880 : scc_info (size_t size);
881 : ~scc_info ();
882 :
883 : auto_sbitmap visited;
884 : auto_sbitmap deleted;
885 : unsigned int *dfs;
886 : unsigned int *node_mapping;
887 : int current_index;
888 : auto_vec<unsigned> scc_stack;
889 : };
890 :
891 :
892 : /* Recursive routine to find strongly connected components in GRAPH.
893 : SI is the SCC info to store the information in, and N is the id of current
894 : graph node we are processing.
895 :
896 : This is Tarjan's strongly connected component finding algorithm, as
897 : modified by Nuutila to keep only non-root nodes on the stack.
898 : The algorithm can be found in "On finding the strongly connected
899 : connected components in a directed graph" by Esko Nuutila and Eljas
900 : Soisalon-Soininen, in Information Processing Letters volume 49,
901 : number 1, pages 9-14. */
902 :
903 : static void
904 420343679 : scc_visit (constraint_graph_t graph, class scc_info *si, unsigned int n)
905 : {
906 420343679 : unsigned int i;
907 420343679 : bitmap_iterator bi;
908 420343679 : unsigned int my_dfs;
909 :
910 420343679 : bitmap_set_bit (si->visited, n);
911 420343679 : si->dfs[n] = si->current_index ++;
912 420343679 : my_dfs = si->dfs[n];
913 :
914 : /* Visit all the successors. */
915 776071727 : EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[n], 0, i, bi)
916 : {
917 355728048 : unsigned int w;
918 :
919 711456096 : if (i > LAST_REF_NODE)
920 : break;
921 :
922 355728048 : w = find (i);
923 355728048 : if (bitmap_bit_p (si->deleted, w))
924 172930573 : continue;
925 :
926 182797475 : if (!bitmap_bit_p (si->visited, w))
927 181856751 : scc_visit (graph, si, w);
928 :
929 182797475 : unsigned int t = find (w);
930 182797475 : gcc_checking_assert (find (n) == n);
931 182797475 : if (si->dfs[t] < si->dfs[n])
932 635776 : si->dfs[n] = si->dfs[t];
933 : }
934 :
935 : /* See if any components have been identified. */
936 420343679 : if (si->dfs[n] == my_dfs)
937 : {
938 419710097 : if (si->scc_stack.length () > 0
939 419710097 : && si->dfs[si->scc_stack.last ()] >= my_dfs)
940 : {
941 189537 : bitmap scc = BITMAP_ALLOC (NULL);
942 189537 : unsigned int lowest_node;
943 189537 : bitmap_iterator bi;
944 :
945 189537 : bitmap_set_bit (scc, n);
946 :
947 189537 : while (si->scc_stack.length () != 0
948 594982 : && si->dfs[si->scc_stack.last ()] >= my_dfs)
949 : {
950 405445 : unsigned int w = si->scc_stack.pop ();
951 :
952 405445 : bitmap_set_bit (scc, w);
953 : }
954 :
955 189537 : lowest_node = bitmap_first_set_bit (scc);
956 189537 : gcc_assert (lowest_node < FIRST_REF_NODE);
957 :
958 : /* Collapse the SCC nodes into a single node, and mark the
959 : indirect cycles. */
960 784519 : EXECUTE_IF_SET_IN_BITMAP (scc, 0, i, bi)
961 : {
962 594982 : if (i < FIRST_REF_NODE)
963 : {
964 474239 : if (unite (lowest_node, i))
965 14237 : unify_nodes (graph, lowest_node, i, false);
966 : }
967 : else
968 : {
969 120743 : if (unite (lowest_node, i))
970 241486 : graph->indirect_cycles[i - FIRST_REF_NODE] = lowest_node;
971 : }
972 : }
973 189537 : bitmap_set_bit (si->deleted, lowest_node);
974 : }
975 : else
976 419520560 : bitmap_set_bit (si->deleted, n);
977 : }
978 : else
979 633582 : si->scc_stack.safe_push (n);
980 420343679 : }
981 :
982 : /* Unify node FROM into node TO, updating the changed count if
983 : necessary when UPDATE_CHANGED is true. */
984 :
985 : static void
986 43890174 : unify_nodes (constraint_graph_t graph, unsigned int to, unsigned int from,
987 : bool update_changed)
988 : {
989 43890174 : gcc_checking_assert (to != from && find (to) == to);
990 :
991 43890174 : if (dump_file && (dump_flags & TDF_DETAILS))
992 573 : fprintf (dump_file, "Unifying %s to %s\n",
993 573 : get_varinfo (from)->name,
994 573 : get_varinfo (to)->name);
995 :
996 43890174 : if (update_changed)
997 60180 : stats.unified_vars_dynamic++;
998 : else
999 43829994 : stats.unified_vars_static++;
1000 :
1001 43890174 : varinfo_t tovi = get_varinfo (to);
1002 43890174 : if (merge_graph_nodes (graph, to, from))
1003 : {
1004 : /* If from brings new successors and the TO solution is not a
1005 : subset of FROM we have to forward the TO solution along these
1006 : edges. */
1007 757683 : if (update_changed)
1008 17270 : bitmap_set_bit (changed, to);
1009 : }
1010 43890174 : if (merge_node_constraints (graph, to, from))
1011 : {
1012 3815 : if (update_changed)
1013 1268 : bitmap_set_bit (changed, to);
1014 : }
1015 :
1016 : /* Mark TO as changed if FROM was changed. If TO was already marked
1017 : as changed, decrease the changed count. */
1018 :
1019 43887627 : if (update_changed
1020 43887627 : && bitmap_clear_bit (changed, from))
1021 22711 : bitmap_set_bit (changed, to);
1022 43890174 : varinfo_t fromvi = get_varinfo (from);
1023 43890174 : if (fromvi->solution)
1024 : {
1025 : /* If the solution changes because of the merging, we need to mark
1026 : the variable as changed. */
1027 43890174 : if (bitmap_ior_into (tovi->solution, fromvi->solution))
1028 : {
1029 377219 : if (update_changed)
1030 9338 : bitmap_set_bit (changed, to);
1031 : }
1032 :
1033 43890174 : BITMAP_FREE (fromvi->solution);
1034 43890174 : if (fromvi->oldsolution)
1035 40154 : BITMAP_FREE (fromvi->oldsolution);
1036 :
1037 43890174 : if (stats.iterations > 0
1038 60180 : && tovi->oldsolution)
1039 4938 : BITMAP_FREE (tovi->oldsolution);
1040 : }
1041 43890174 : if (graph->succs[to])
1042 865032 : bitmap_clear_bit (graph->succs[to], to);
1043 43890174 : }
1044 :
1045 : /* Add a copy edge FROM -> TO, optimizing special cases. Returns TRUE
1046 : if the solution of TO changed. */
1047 :
1048 : static bool
1049 328579558 : solve_add_graph_edge (constraint_graph_t graph, unsigned int to,
1050 : unsigned int from)
1051 : {
1052 : /* Adding edges from the special vars is pointless.
1053 : They don't have sets that can change. */
1054 328579558 : if (get_varinfo (from)->is_special_var)
1055 63164432 : return bitmap_ior_into (get_varinfo (to)->solution,
1056 126328864 : get_varinfo (from)->solution);
1057 : /* Merging the solution from ESCAPED needlessly increases
1058 : the set. Use ESCAPED as representative instead. */
1059 265415126 : else if (from == find (escaped_id))
1060 30632170 : return bitmap_set_bit (get_varinfo (to)->solution, escaped_id);
1061 234782956 : else if (get_varinfo (from)->may_have_pointers
1062 234782956 : && add_graph_edge (graph, to, from))
1063 85549342 : return bitmap_ior_into (get_varinfo (to)->solution,
1064 85549342 : get_varinfo (from)->solution);
1065 : return false;
1066 : }
1067 :
1068 : /* Process a constraint C that represents x = *(y + off), using DELTA as the
1069 : starting solution for y. */
1070 :
1071 : static void
1072 69950866 : do_sd_constraint (constraint_graph_t graph, constraint_t c,
1073 : bitmap delta, bitmap *expanded_delta)
1074 : {
1075 69950866 : unsigned int lhs = c->lhs.var;
1076 69950866 : bool flag = false;
1077 69950866 : bitmap sol = get_varinfo (lhs)->solution;
1078 69950866 : unsigned int j;
1079 69950866 : bitmap_iterator bi;
1080 69950866 : HOST_WIDE_INT roffset = c->rhs.offset;
1081 :
1082 : /* Our IL does not allow this. */
1083 69950866 : gcc_checking_assert (c->lhs.offset == 0);
1084 :
1085 : /* If the solution of Y contains anything it is good enough to transfer
1086 : this to the LHS. */
1087 69950866 : if (bitmap_bit_p (delta, anything_id))
1088 : {
1089 565963 : flag |= bitmap_set_bit (sol, anything_id);
1090 565963 : goto done;
1091 : }
1092 :
1093 : /* If we do not know at with offset the rhs is dereferenced compute
1094 : the reachability set of DELTA, conservatively assuming it is
1095 : dereferenced at all valid offsets. */
1096 69384903 : if (roffset == UNKNOWN_OFFSET)
1097 : {
1098 51104806 : delta = solution_set_expand (delta, expanded_delta);
1099 : /* No further offset processing is necessary. */
1100 51104806 : roffset = 0;
1101 : }
1102 :
1103 : /* For each variable j in delta (Sol(y)), add
1104 : an edge in the graph from j to x, and union Sol(j) into Sol(x). */
1105 275069798 : EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1106 : {
1107 205684895 : varinfo_t v = get_varinfo (j);
1108 205684895 : HOST_WIDE_INT fieldoffset = v->offset + roffset;
1109 205684895 : unsigned HOST_WIDE_INT size = v->size;
1110 205684895 : unsigned int t;
1111 :
1112 205684895 : if (v->is_full_var)
1113 : ;
1114 109704122 : else if (roffset != 0)
1115 : {
1116 3555196 : if (fieldoffset < 0)
1117 32255 : v = get_varinfo (v->head);
1118 : else
1119 3522941 : v = first_or_preceding_vi_for_offset (v, fieldoffset);
1120 : }
1121 :
1122 : /* We have to include all fields that overlap the current field
1123 : shifted by roffset. */
1124 206351199 : do
1125 : {
1126 206351199 : t = find (v->id);
1127 :
1128 206351199 : flag |= solve_add_graph_edge (graph, lhs, t);
1129 :
1130 206351199 : if (v->is_full_var
1131 110370231 : || v->next == 0)
1132 : break;
1133 :
1134 90250254 : v = vi_next (v);
1135 : }
1136 90250254 : while (v->offset < fieldoffset + size);
1137 : }
1138 :
1139 69384903 : done:
1140 : /* If the LHS solution changed, mark the var as changed. */
1141 69950866 : if (flag)
1142 29444159 : bitmap_set_bit (changed, lhs);
1143 69950866 : }
1144 :
1145 : /* Process a constraint C that represents *(x + off) = y using DELTA
1146 : as the starting solution for x. */
1147 :
1148 : static void
1149 55935449 : do_ds_constraint (constraint_t c, bitmap delta, bitmap *expanded_delta)
1150 : {
1151 55935449 : unsigned int rhs = c->rhs.var;
1152 55935449 : bitmap sol = get_varinfo (rhs)->solution;
1153 55935449 : unsigned int j;
1154 55935449 : bitmap_iterator bi;
1155 55935449 : HOST_WIDE_INT loff = c->lhs.offset;
1156 55935449 : bool escaped_p = false;
1157 :
1158 : /* Our IL does not allow this. */
1159 55935449 : gcc_checking_assert (c->rhs.offset == 0);
1160 :
1161 : /* If the solution of y contains ANYTHING simply use the ANYTHING
1162 : solution. This avoids needlessly increasing the points-to sets. */
1163 55935449 : if (bitmap_bit_p (sol, anything_id))
1164 397625 : sol = get_varinfo (find (anything_id))->solution;
1165 :
1166 : /* If the solution for x contains ANYTHING we have to merge the
1167 : solution of y into all pointer variables which we do via
1168 : STOREDANYTHING. */
1169 55935449 : if (bitmap_bit_p (delta, anything_id))
1170 : {
1171 447878 : unsigned t = find (storedanything_id);
1172 447878 : if (solve_add_graph_edge (graph, t, rhs))
1173 36033 : bitmap_set_bit (changed, t);
1174 447878 : return;
1175 : }
1176 :
1177 : /* If we do not know at with offset the rhs is dereferenced compute
1178 : the reachability set of DELTA, conservatively assuming it is
1179 : dereferenced at all valid offsets. */
1180 55487571 : if (loff == UNKNOWN_OFFSET)
1181 : {
1182 1699898 : delta = solution_set_expand (delta, expanded_delta);
1183 1699898 : loff = 0;
1184 : }
1185 :
1186 : /* For each member j of delta (Sol(x)), add an edge from y to j and
1187 : union Sol(y) into Sol(j) */
1188 214851088 : EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1189 : {
1190 159363517 : varinfo_t v = get_varinfo (j);
1191 159363517 : unsigned int t;
1192 159363517 : HOST_WIDE_INT fieldoffset = v->offset + loff;
1193 159363517 : unsigned HOST_WIDE_INT size = v->size;
1194 :
1195 159363517 : if (v->is_full_var)
1196 : ;
1197 80092570 : else if (loff != 0)
1198 : {
1199 5226741 : if (fieldoffset < 0)
1200 6308 : v = get_varinfo (v->head);
1201 : else
1202 5220433 : v = first_or_preceding_vi_for_offset (v, fieldoffset);
1203 : }
1204 :
1205 : /* We have to include all fields that overlap the current field
1206 : shifted by loff. */
1207 161258988 : do
1208 : {
1209 161258988 : if (v->may_have_pointers)
1210 : {
1211 : /* If v is a global variable then this is an escape point. */
1212 149820710 : if (v->is_global_var
1213 115318850 : && !escaped_p)
1214 : {
1215 44190217 : t = find (escaped_id);
1216 44190217 : if (add_graph_edge (graph, t, rhs)
1217 60504420 : && bitmap_ior_into (get_varinfo (t)->solution, sol))
1218 1310552 : bitmap_set_bit (changed, t);
1219 : /* Enough to let rhs escape once. */
1220 : escaped_p = true;
1221 : }
1222 :
1223 149820710 : if (v->is_special_var)
1224 : break;
1225 :
1226 121780481 : t = find (v->id);
1227 :
1228 121780481 : if (solve_add_graph_edge (graph, t, rhs))
1229 12629534 : bitmap_set_bit (changed, t);
1230 : }
1231 :
1232 133218759 : if (v->is_full_var
1233 81987896 : || v->next == 0)
1234 : break;
1235 :
1236 66655578 : v = vi_next (v);
1237 : }
1238 66655578 : while (v->offset < fieldoffset + size);
1239 : }
1240 : }
1241 :
1242 : /* Handle a non-simple (simple meaning requires no iteration),
1243 : constraint (IE *x = &y, x = *y, *x = y, and x = y with offsets involved). */
1244 :
1245 : static void
1246 211950083 : do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta,
1247 : bitmap *expanded_delta)
1248 : {
1249 211950083 : if (c->lhs.type == DEREF)
1250 : {
1251 55935449 : if (c->rhs.type == ADDRESSOF)
1252 : {
1253 0 : gcc_unreachable ();
1254 : }
1255 : else
1256 : {
1257 : /* *x = y */
1258 55935449 : do_ds_constraint (c, delta, expanded_delta);
1259 : }
1260 : }
1261 156014634 : else if (c->rhs.type == DEREF)
1262 : {
1263 : /* x = *y */
1264 69950921 : if (!(get_varinfo (c->lhs.var)->is_special_var))
1265 69950866 : do_sd_constraint (graph, c, delta, expanded_delta);
1266 : }
1267 : else
1268 : {
1269 86063713 : bitmap tmp;
1270 86063713 : bool flag = false;
1271 :
1272 86063713 : gcc_checking_assert (c->rhs.type == SCALAR && c->lhs.type == SCALAR
1273 : && c->rhs.offset != 0 && c->lhs.offset == 0);
1274 86063713 : tmp = get_varinfo (c->lhs.var)->solution;
1275 :
1276 86063713 : flag = set_union_with_increment (tmp, delta, c->rhs.offset,
1277 : expanded_delta);
1278 :
1279 86063713 : if (flag)
1280 21839470 : bitmap_set_bit (changed, c->lhs.var);
1281 : }
1282 211950083 : }
1283 :
1284 : /* Initialize and return a new SCC info structure. */
1285 :
1286 9137908 : scc_info::scc_info (size_t size) :
1287 9137908 : visited (size), deleted (size), current_index (0), scc_stack (1)
1288 : {
1289 9137908 : bitmap_clear (visited);
1290 9137908 : bitmap_clear (deleted);
1291 9137908 : node_mapping = XNEWVEC (unsigned int, size);
1292 9137908 : dfs = XCNEWVEC (unsigned int, size);
1293 :
1294 944673756 : for (size_t i = 0; i < size; i++)
1295 935535848 : node_mapping[i] = i;
1296 9137908 : }
1297 :
1298 : /* Free an SCC info structure pointed to by SI. */
1299 :
1300 9137908 : scc_info::~scc_info ()
1301 : {
1302 9137908 : free (node_mapping);
1303 9137908 : free (dfs);
1304 9137908 : }
1305 :
1306 :
1307 : /* Find indirect cycles in GRAPH that occur, using strongly connected
1308 : components, and note them in the indirect cycles map.
1309 :
1310 : This technique comes from Ben Hardekopf and Calvin Lin,
1311 : "It Pays to be Lazy: Fast and Accurate Pointer Analysis for Millions of
1312 : Lines of Code", submitted to PLDI 2007. */
1313 :
1314 : static void
1315 4568954 : find_indirect_cycles (constraint_graph_t graph)
1316 : {
1317 4568954 : unsigned int i;
1318 4568954 : unsigned int size = graph->size;
1319 4568954 : scc_info si (size);
1320 :
1321 940104802 : for (i = 0; i < MIN (LAST_REF_NODE, size); i++)
1322 463198970 : if (!bitmap_bit_p (si.visited, i) && find (i) == i)
1323 238486928 : scc_visit (graph, &si, i);
1324 4568954 : }
1325 :
1326 : /* Visit the graph in topological order starting at node N, and store the
1327 : order in TOPO_ORDER using VISITED to indicate visited nodes. */
1328 :
1329 : static void
1330 461996715 : topo_visit (constraint_graph_t graph, vec<unsigned> &topo_order,
1331 : sbitmap visited, unsigned int n)
1332 : {
1333 461996715 : bitmap_iterator bi;
1334 461996715 : unsigned int j;
1335 :
1336 461996715 : bitmap_set_bit (visited, n);
1337 :
1338 461996715 : if (graph->succs[n])
1339 1121648838 : EXECUTE_IF_SET_IN_BITMAP (graph->succs[n], 0, j, bi)
1340 : {
1341 905756506 : unsigned k = find (j);
1342 905756506 : if (!bitmap_bit_p (visited, k))
1343 351159542 : topo_visit (graph, topo_order, visited, k);
1344 : }
1345 :
1346 : /* Also consider copy with offset complex constraints as implicit edges. */
1347 908965432 : for (auto c : graph->complex[n])
1348 : {
1349 : /* Constraints are ordered so that SCALAR = SCALAR appear first. */
1350 258844161 : if (c->lhs.type != SCALAR || c->rhs.type != SCALAR)
1351 : break;
1352 145359399 : gcc_checking_assert (c->rhs.var == n);
1353 145359399 : unsigned k = find (c->lhs.var);
1354 145359399 : if (!bitmap_bit_p (visited, k))
1355 38876625 : topo_visit (graph, topo_order, visited, k);
1356 : }
1357 :
1358 461996715 : topo_order.quick_push (n);
1359 461996715 : }
1360 :
1361 : /* Compute a topological ordering for GRAPH, and return the result. */
1362 :
1363 : static auto_vec<unsigned>
1364 8129517 : compute_topo_order (constraint_graph_t graph)
1365 : {
1366 8129517 : unsigned int i;
1367 8129517 : unsigned int size = graph->size;
1368 :
1369 8129517 : auto_sbitmap visited (size);
1370 8129517 : bitmap_clear (visited);
1371 :
1372 : /* For the heuristic in add_graph_edge to work optimally make sure to
1373 : first visit the connected component of the graph containing
1374 : ESCAPED. Do this by extracting the connected component
1375 : with ESCAPED and append that to all other components as solve_graph
1376 : pops from the order. */
1377 8129517 : auto_vec<unsigned> tail (size);
1378 8129517 : topo_visit (graph, tail, visited, find (escaped_id));
1379 :
1380 8129517 : auto_vec<unsigned> topo_order (size);
1381 :
1382 589613880 : for (i = 0; i != size; ++i)
1383 573354846 : if (!bitmap_bit_p (visited, i) && find (i) == i)
1384 63831031 : topo_visit (graph, topo_order, visited, i);
1385 :
1386 8129517 : topo_order.splice (tail);
1387 8129517 : return topo_order;
1388 8129517 : }
1389 :
1390 : /* Structure used to for hash value numbering of pointer equivalence
1391 : classes. */
1392 :
1393 : typedef struct equiv_class_label
1394 : {
1395 : hashval_t hashcode;
1396 : unsigned int equivalence_class;
1397 : bitmap labels;
1398 : } *equiv_class_label_t;
1399 : typedef const struct equiv_class_label *const_equiv_class_label_t;
1400 :
1401 : /* Equiv_class_label hashtable helpers. */
1402 :
1403 : struct equiv_class_hasher : nofree_ptr_hash <equiv_class_label>
1404 : {
1405 : static inline hashval_t hash (const equiv_class_label *);
1406 : static inline bool equal (const equiv_class_label *,
1407 : const equiv_class_label *);
1408 : };
1409 :
1410 : /* A hashtable for mapping a bitmap of labels->pointer equivalence
1411 : classes. */
1412 : static hash_table<equiv_class_hasher> *pointer_equiv_class_table;
1413 :
1414 : /* A hashtable for mapping a bitmap of labels->location equivalence
1415 : classes. */
1416 : static hash_table<equiv_class_hasher> *location_equiv_class_table;
1417 :
1418 : /* Hash function for a equiv_class_label_t. */
1419 :
1420 : inline hashval_t
1421 194211308 : equiv_class_hasher::hash (const equiv_class_label *ecl)
1422 : {
1423 194211308 : return ecl->hashcode;
1424 : }
1425 :
1426 : /* Equality function for two equiv_class_label_t's. */
1427 :
1428 : inline bool
1429 251556898 : equiv_class_hasher::equal (const equiv_class_label *eql1,
1430 : const equiv_class_label *eql2)
1431 : {
1432 251556898 : return (eql1->hashcode == eql2->hashcode
1433 251556898 : && bitmap_equal_p (eql1->labels, eql2->labels));
1434 : }
1435 :
1436 : struct obstack equiv_class_obstack;
1437 :
1438 : /* Lookup a equivalence class in TABLE by the bitmap of LABELS with
1439 : hash HAS it contains. Sets *REF_LABELS to the bitmap LABELS
1440 : is equivalent to. */
1441 :
1442 : static equiv_class_label *
1443 199825081 : equiv_class_lookup_or_add (hash_table<equiv_class_hasher> *table,
1444 : bitmap labels)
1445 : {
1446 199825081 : equiv_class_label **slot;
1447 199825081 : equiv_class_label ecl;
1448 :
1449 199825081 : ecl.labels = labels;
1450 199825081 : ecl.hashcode = bitmap_hash (labels);
1451 199825081 : slot = table->find_slot (&ecl, INSERT);
1452 199825081 : if (!*slot)
1453 : {
1454 167249470 : *slot = XOBNEW (&equiv_class_obstack, struct equiv_class_label);
1455 167249470 : (*slot)->labels = labels;
1456 167249470 : (*slot)->hashcode = ecl.hashcode;
1457 167249470 : (*slot)->equivalence_class = 0;
1458 : }
1459 :
1460 199825081 : return *slot;
1461 : }
1462 :
1463 :
1464 : /* Perform offline variable substitution.
1465 :
1466 : This is a worst case quadratic time way of identifying variables
1467 : that must have equivalent points-to sets, including those caused by
1468 : static cycles, and single entry subgraphs, in the constraint graph.
1469 :
1470 : The technique is described in "Exploiting Pointer and Location
1471 : Equivalence to Optimize Pointer Analysis. In the 14th International
1472 : Static Analysis Symposium (SAS), August 2007." It is known as the
1473 : "HU" algorithm, and is equivalent to value numbering the collapsed
1474 : constraint graph including evaluating unions.
1475 :
1476 : The general method of finding equivalence classes is as follows:
1477 : Add fake nodes (REF nodes) and edges for *a = b and a = *b constraints.
1478 : Initialize all non-REF nodes to be direct nodes.
1479 : For each constraint a = a U {b}, we set pts(a) = pts(a) u {fresh
1480 : variable}
1481 : For each constraint containing the dereference, we also do the same
1482 : thing.
1483 :
1484 : We then compute SCC's in the graph and unify nodes in the same SCC,
1485 : including pts sets.
1486 :
1487 : For each non-collapsed node x:
1488 : Visit all unvisited explicit incoming edges.
1489 : Ignoring all non-pointers, set pts(x) = Union of pts(a) for y
1490 : where y->x.
1491 : Lookup the equivalence class for pts(x).
1492 : If we found one, equivalence_class(x) = found class.
1493 : Otherwise, equivalence_class(x) = new class, and new_class is
1494 : added to the lookup table.
1495 :
1496 : All direct nodes with the same equivalence class can be replaced
1497 : with a single representative node.
1498 : All unlabeled nodes (label == 0) are not pointers and all edges
1499 : involving them can be eliminated.
1500 : We perform these optimizations during rewrite_constraints
1501 :
1502 : In addition to pointer equivalence class finding, we also perform
1503 : location equivalence class finding. This is the set of variables
1504 : that always appear together in points-to sets. We use this to
1505 : compress the size of the points-to sets. */
1506 :
1507 : /* Current maximum pointer equivalence class id. */
1508 : static int pointer_equiv_class;
1509 :
1510 : /* Current maximum location equivalence class id. */
1511 : static int location_equiv_class;
1512 :
1513 : /* Recursive routine to find strongly connected components in GRAPH,
1514 : and label it's nodes with DFS numbers. */
1515 :
1516 : static void
1517 273363783 : condense_visit (constraint_graph_t graph, class scc_info *si, unsigned int n)
1518 : {
1519 273363783 : unsigned int i;
1520 273363783 : bitmap_iterator bi;
1521 273363783 : unsigned int my_dfs;
1522 :
1523 273363783 : gcc_checking_assert (si->node_mapping[n] == n);
1524 273363783 : bitmap_set_bit (si->visited, n);
1525 273363783 : si->dfs[n] = si->current_index ++;
1526 273363783 : my_dfs = si->dfs[n];
1527 :
1528 : /* Visit all the successors. */
1529 502567777 : EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
1530 : {
1531 229203994 : unsigned int w = si->node_mapping[i];
1532 :
1533 229203994 : if (bitmap_bit_p (si->deleted, w))
1534 145585148 : continue;
1535 :
1536 83618846 : if (!bitmap_bit_p (si->visited, w))
1537 82131745 : condense_visit (graph, si, w);
1538 :
1539 83618846 : unsigned int t = si->node_mapping[w];
1540 83618846 : gcc_checking_assert (si->node_mapping[n] == n);
1541 83618846 : if (si->dfs[t] < si->dfs[n])
1542 2640083 : si->dfs[n] = si->dfs[t];
1543 : }
1544 :
1545 : /* Visit all the implicit predecessors. */
1546 333092385 : EXECUTE_IF_IN_NONNULL_BITMAP (graph->implicit_preds[n], 0, i, bi)
1547 : {
1548 59728602 : unsigned int w = si->node_mapping[i];
1549 :
1550 59728602 : if (bitmap_bit_p (si->deleted, w))
1551 19733605 : continue;
1552 :
1553 39994997 : if (!bitmap_bit_p (si->visited, w))
1554 35035118 : condense_visit (graph, si, w);
1555 :
1556 39994997 : unsigned int t = si->node_mapping[w];
1557 39994997 : gcc_assert (si->node_mapping[n] == n);
1558 39994997 : if (si->dfs[t] < si->dfs[n])
1559 8445570 : si->dfs[n] = si->dfs[t];
1560 : }
1561 :
1562 : /* See if any components have been identified. */
1563 273363783 : if (si->dfs[n] == my_dfs)
1564 : {
1565 262445380 : if (si->scc_stack.length () != 0
1566 262445380 : && si->dfs[si->scc_stack.last ()] >= my_dfs)
1567 : {
1568 : /* Find the first node of the SCC and do non-bitmap work. */
1569 10918403 : bool direct_p = true;
1570 10918403 : unsigned first = si->scc_stack.length ();
1571 10918403 : do
1572 : {
1573 10918403 : --first;
1574 10918403 : unsigned int w = si->scc_stack[first];
1575 10918403 : si->node_mapping[w] = n;
1576 10918403 : if (!bitmap_bit_p (graph->direct_nodes, w))
1577 8802997 : direct_p = false;
1578 : }
1579 : while (first > 0
1580 12305755 : && si->dfs[si->scc_stack[first - 1]] >= my_dfs);
1581 1387352 : if (!direct_p)
1582 872996 : bitmap_clear_bit (graph->direct_nodes, n);
1583 :
1584 : /* Want to reduce to node n, push that first. */
1585 1387352 : si->scc_stack.reserve (1);
1586 1387352 : si->scc_stack.quick_push (si->scc_stack[first]);
1587 1387352 : si->scc_stack[first] = n;
1588 :
1589 1387352 : unsigned scc_size = si->scc_stack.length () - first;
1590 1387352 : unsigned split = scc_size / 2;
1591 1387352 : unsigned carry = scc_size - split * 2;
1592 4848672 : while (split > 0)
1593 : {
1594 14379723 : for (unsigned i = 0; i < split; ++i)
1595 : {
1596 10918403 : unsigned a = si->scc_stack[first + i];
1597 10918403 : unsigned b = si->scc_stack[first + split + carry + i];
1598 :
1599 : /* Unify our nodes. */
1600 10918403 : if (graph->preds[b])
1601 : {
1602 4786829 : if (!graph->preds[a])
1603 997232 : std::swap (graph->preds[a], graph->preds[b]);
1604 : else
1605 3789597 : bitmap_ior_into_and_free (graph->preds[a],
1606 : &graph->preds[b]);
1607 : }
1608 10918403 : if (graph->implicit_preds[b])
1609 : {
1610 8702346 : if (!graph->implicit_preds[a])
1611 877707 : std::swap (graph->implicit_preds[a],
1612 : graph->implicit_preds[b]);
1613 : else
1614 7824639 : bitmap_ior_into_and_free (graph->implicit_preds[a],
1615 : &graph->implicit_preds[b]);
1616 : }
1617 10918403 : if (graph->points_to[b])
1618 : {
1619 530316 : if (!graph->points_to[a])
1620 235518 : std::swap (graph->points_to[a], graph->points_to[b]);
1621 : else
1622 294798 : bitmap_ior_into_and_free (graph->points_to[a],
1623 : &graph->points_to[b]);
1624 : }
1625 : }
1626 3461320 : unsigned remain = split + carry;
1627 3461320 : split = remain / 2;
1628 3461320 : carry = remain - split * 2;
1629 : }
1630 : /* Actually pop the SCC. */
1631 1387352 : si->scc_stack.truncate (first);
1632 : }
1633 262445380 : bitmap_set_bit (si->deleted, n);
1634 : }
1635 : else
1636 10918403 : si->scc_stack.safe_push (n);
1637 273363783 : }
1638 :
1639 : /* Label pointer equivalences.
1640 :
1641 : This performs a value numbering of the constraint graph to
1642 : discover which variables will always have the same points-to sets
1643 : under the current set of constraints.
1644 :
1645 : The way it value numbers is to store the set of points-to bits
1646 : generated by the constraints and graph edges. This is just used as a
1647 : hash and equality comparison. The *actual set of points-to bits* is
1648 : completely irrelevant, in that we don't care about being able to
1649 : extract them later.
1650 :
1651 : The equality values (currently bitmaps) just have to satisfy a few
1652 : constraints, the main ones being:
1653 : 1. The combining operation must be order independent.
1654 : 2. The end result of a given set of operations must be unique iff the
1655 : combination of input values is unique
1656 : 3. Hashable. */
1657 :
1658 : static void
1659 238762835 : label_visit (constraint_graph_t graph, class scc_info *si, unsigned int n)
1660 : {
1661 238762835 : unsigned int i, first_pred;
1662 238762835 : bitmap_iterator bi;
1663 :
1664 238762835 : bitmap_set_bit (si->visited, n);
1665 :
1666 : /* Label and union our incoming edges's points to sets. */
1667 238762835 : first_pred = -1U;
1668 462635369 : EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
1669 : {
1670 223872534 : unsigned int w = si->node_mapping[i];
1671 223872534 : if (!bitmap_bit_p (si->visited, w))
1672 77401785 : label_visit (graph, si, w);
1673 :
1674 : /* Skip unused edges. */
1675 223872534 : if (w == n || graph->pointer_label[w] == 0)
1676 5244427 : continue;
1677 :
1678 218628107 : if (graph->points_to[w])
1679 : {
1680 218628107 : if (!graph->points_to[n])
1681 : {
1682 152483109 : if (first_pred == -1U)
1683 : first_pred = w;
1684 : else
1685 : {
1686 42282805 : graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
1687 42282805 : bitmap_ior (graph->points_to[n],
1688 42282805 : graph->points_to[first_pred],
1689 42282805 : graph->points_to[w]);
1690 : }
1691 : }
1692 : else
1693 66144998 : bitmap_ior_into (graph->points_to[n], graph->points_to[w]);
1694 : }
1695 : }
1696 :
1697 : /* Indirect nodes get fresh variables and a new pointer equiv class. */
1698 238762835 : if (!bitmap_bit_p (graph->direct_nodes, n))
1699 : {
1700 115636590 : if (!graph->points_to[n])
1701 : {
1702 66643520 : graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
1703 66643520 : if (first_pred != -1U)
1704 26988533 : bitmap_copy (graph->points_to[n], graph->points_to[first_pred]);
1705 : }
1706 231273180 : bitmap_set_bit (graph->points_to[n], FIRST_REF_NODE + n);
1707 115636590 : graph->pointer_label[n] = pointer_equiv_class++;
1708 115636590 : equiv_class_label_t ecl;
1709 231273180 : ecl = equiv_class_lookup_or_add (pointer_equiv_class_table,
1710 115636590 : graph->points_to[n]);
1711 115636590 : ecl->equivalence_class = graph->pointer_label[n];
1712 176865851 : return;
1713 : }
1714 :
1715 : /* If there was only a single non-empty predecessor the pointer equiv
1716 : class is the same. */
1717 123126245 : if (!graph->points_to[n])
1718 : {
1719 61229261 : if (first_pred != -1U)
1720 : {
1721 40928966 : graph->pointer_label[n] = graph->pointer_label[first_pred];
1722 40928966 : graph->points_to[n] = graph->points_to[first_pred];
1723 : }
1724 : return;
1725 : }
1726 :
1727 61896984 : if (!bitmap_empty_p (graph->points_to[n]))
1728 : {
1729 61896984 : equiv_class_label_t ecl;
1730 61896984 : ecl = equiv_class_lookup_or_add (pointer_equiv_class_table,
1731 : graph->points_to[n]);
1732 61896984 : if (ecl->equivalence_class == 0)
1733 29773633 : ecl->equivalence_class = pointer_equiv_class++;
1734 : else
1735 : {
1736 32123351 : BITMAP_FREE (graph->points_to[n]);
1737 32123351 : graph->points_to[n] = ecl->labels;
1738 : }
1739 61896984 : graph->pointer_label[n] = ecl->equivalence_class;
1740 : }
1741 : }
1742 :
1743 : /* Print the pred graph in dot format. */
1744 :
1745 : static void
1746 3 : dump_pred_graph (class scc_info *si, FILE *file)
1747 : {
1748 3 : unsigned int i;
1749 :
1750 : /* Only print the graph if it has already been initialized: */
1751 3 : if (!graph)
1752 : return;
1753 :
1754 : /* Prints the header of the dot file: */
1755 3 : fprintf (file, "strict digraph {\n");
1756 3 : fprintf (file, " node [\n shape = box\n ]\n");
1757 3 : fprintf (file, " edge [\n fontsize = \"12\"\n ]\n");
1758 3 : fprintf (file, "\n // List of nodes and complex constraints in "
1759 : "the constraint graph:\n");
1760 :
1761 : /* The next lines print the nodes in the graph together with the
1762 : complex constraints attached to them. */
1763 83 : for (i = 1; i < graph->size; i++)
1764 : {
1765 154 : if (i == FIRST_REF_NODE)
1766 3 : continue;
1767 74 : if (si->node_mapping[i] != i)
1768 0 : continue;
1769 74 : if (i < FIRST_REF_NODE)
1770 37 : fprintf (file, "\"%s\"", get_varinfo (i)->name);
1771 : else
1772 37 : fprintf (file, "\"*%s\"", get_varinfo (i - FIRST_REF_NODE)->name);
1773 74 : if (graph->points_to[i]
1774 74 : && !bitmap_empty_p (graph->points_to[i]))
1775 : {
1776 11 : if (i < FIRST_REF_NODE)
1777 11 : fprintf (file, "[label=\"%s = {", get_varinfo (i)->name);
1778 : else
1779 0 : fprintf (file, "[label=\"*%s = {",
1780 0 : get_varinfo (i - FIRST_REF_NODE)->name);
1781 11 : unsigned j;
1782 11 : bitmap_iterator bi;
1783 25 : EXECUTE_IF_SET_IN_BITMAP (graph->points_to[i], 0, j, bi)
1784 14 : fprintf (file, " %d", j);
1785 11 : fprintf (file, " }\"]");
1786 : }
1787 74 : fprintf (file, ";\n");
1788 : }
1789 :
1790 : /* Go over the edges. */
1791 3 : fprintf (file, "\n // Edges in the constraint graph:\n");
1792 83 : for (i = 1; i < graph->size; i++)
1793 : {
1794 77 : unsigned j;
1795 77 : bitmap_iterator bi;
1796 77 : if (si->node_mapping[i] != i)
1797 0 : continue;
1798 92 : EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[i], 0, j, bi)
1799 : {
1800 15 : unsigned from = si->node_mapping[j];
1801 15 : if (from < FIRST_REF_NODE)
1802 7 : fprintf (file, "\"%s\"", get_varinfo (from)->name);
1803 : else
1804 8 : fprintf (file, "\"*%s\"",
1805 8 : get_varinfo (from - FIRST_REF_NODE)->name);
1806 15 : fprintf (file, " -> ");
1807 15 : if (i < FIRST_REF_NODE)
1808 11 : fprintf (file, "\"%s\"", get_varinfo (i)->name);
1809 : else
1810 8 : fprintf (file, "\"*%s\"", get_varinfo (i - FIRST_REF_NODE)->name);
1811 15 : fprintf (file, ";\n");
1812 : }
1813 : }
1814 :
1815 : /* Prints the tail of the dot file. */
1816 3 : fprintf (file, "}\n");
1817 : }
1818 :
1819 : /* Perform offline variable substitution, discovering equivalence
1820 : classes, and eliminating non-pointer variables. */
1821 :
1822 : static class scc_info *
1823 4568954 : perform_var_substitution (constraint_graph_t graph)
1824 : {
1825 4568954 : unsigned int i;
1826 4568954 : unsigned int size = graph->size;
1827 4568954 : scc_info *si = new scc_info (size);
1828 :
1829 4568954 : bitmap_obstack_initialize (&iteration_obstack);
1830 4568954 : gcc_obstack_init (&equiv_class_obstack);
1831 4568954 : pointer_equiv_class_table = new hash_table<equiv_class_hasher> (511);
1832 4568954 : location_equiv_class_table
1833 4568954 : = new hash_table<equiv_class_hasher> (511);
1834 4568954 : pointer_equiv_class = 1;
1835 4568954 : location_equiv_class = 1;
1836 :
1837 : /* Condense the nodes, which means to find SCC's, count incoming
1838 : predecessors, and unite nodes in SCC's. */
1839 233883962 : for (i = 1; i < FIRST_REF_NODE; i++)
1840 229315008 : if (!bitmap_bit_p (si->visited, si->node_mapping[i]))
1841 156196920 : condense_visit (graph, si, si->node_mapping[i]);
1842 :
1843 4568954 : if (dump_file && (dump_flags & TDF_GRAPH))
1844 : {
1845 3 : fprintf (dump_file, "\n\n// The constraint graph before var-substitution "
1846 : "in dot format:\n");
1847 3 : dump_pred_graph (si, dump_file);
1848 3 : fprintf (dump_file, "\n\n");
1849 : }
1850 :
1851 4568954 : bitmap_clear (si->visited);
1852 : /* Actually the label the nodes for pointer equivalences. */
1853 472336878 : for (i = 1; i < FIRST_REF_NODE; i++)
1854 229315008 : if (!bitmap_bit_p (si->visited, si->node_mapping[i]))
1855 161361050 : label_visit (graph, si, si->node_mapping[i]);
1856 :
1857 : /* Calculate location equivalence labels. */
1858 233883962 : for (i = 1; i < FIRST_REF_NODE; i++)
1859 : {
1860 229315008 : bitmap pointed_by;
1861 229315008 : bitmap_iterator bi;
1862 229315008 : unsigned int j;
1863 :
1864 229315008 : if (!graph->pointed_by[i])
1865 207023501 : continue;
1866 22291507 : pointed_by = BITMAP_ALLOC (&iteration_obstack);
1867 :
1868 : /* Translate the pointed-by mapping for pointer equivalence
1869 : labels. */
1870 100380554 : EXECUTE_IF_SET_IN_BITMAP (graph->pointed_by[i], 0, j, bi)
1871 : {
1872 78089047 : bitmap_set_bit (pointed_by,
1873 78089047 : graph->pointer_label[si->node_mapping[j]]);
1874 : }
1875 : /* The original pointed_by is now dead. */
1876 22291507 : BITMAP_FREE (graph->pointed_by[i]);
1877 :
1878 : /* Look up the location equivalence label if one exists, or make
1879 : one otherwise. */
1880 22291507 : equiv_class_label_t ecl;
1881 22291507 : ecl = equiv_class_lookup_or_add (location_equiv_class_table, pointed_by);
1882 22291507 : if (ecl->equivalence_class == 0)
1883 21839247 : ecl->equivalence_class = location_equiv_class++;
1884 : else
1885 : {
1886 452260 : if (dump_file && (dump_flags & TDF_DETAILS))
1887 55 : fprintf (dump_file, "Found location equivalence for node %s\n",
1888 55 : get_varinfo (i)->name);
1889 452260 : BITMAP_FREE (pointed_by);
1890 : }
1891 22291507 : graph->loc_label[i] = ecl->equivalence_class;
1892 :
1893 : }
1894 :
1895 4568954 : if (dump_file && (dump_flags & TDF_DETAILS))
1896 6830 : for (i = 1; i < FIRST_REF_NODE; i++)
1897 : {
1898 6529 : unsigned j = si->node_mapping[i];
1899 6529 : if (j != i)
1900 : {
1901 21 : fprintf (dump_file, "%s node id %d ",
1902 21 : bitmap_bit_p (graph->direct_nodes, i)
1903 : ? "Direct" : "Indirect", i);
1904 21 : if (i < FIRST_REF_NODE)
1905 21 : fprintf (dump_file, "\"%s\"", get_varinfo (i)->name);
1906 : else
1907 0 : fprintf (dump_file, "\"*%s\"",
1908 0 : get_varinfo (i - FIRST_REF_NODE)->name);
1909 21 : fprintf (dump_file, " mapped to SCC leader node id %d ", j);
1910 21 : if (j < FIRST_REF_NODE)
1911 21 : fprintf (dump_file, "\"%s\"\n", get_varinfo (j)->name);
1912 : else
1913 0 : fprintf (dump_file, "\"*%s\"\n",
1914 0 : get_varinfo (j - FIRST_REF_NODE)->name);
1915 : }
1916 : else
1917 : {
1918 10023 : fprintf (dump_file,
1919 : "Equivalence classes for %s node id %d ",
1920 6508 : bitmap_bit_p (graph->direct_nodes, i)
1921 : ? "direct" : "indirect", i);
1922 6508 : if (i < FIRST_REF_NODE)
1923 6508 : fprintf (dump_file, "\"%s\"", get_varinfo (i)->name);
1924 : else
1925 0 : fprintf (dump_file, "\"*%s\"",
1926 0 : get_varinfo (i - FIRST_REF_NODE)->name);
1927 6508 : fprintf (dump_file,
1928 : ": pointer %d, location %d\n",
1929 6508 : graph->pointer_label[i], graph->loc_label[i]);
1930 : }
1931 : }
1932 :
1933 : /* Quickly eliminate our non-pointer variables. */
1934 :
1935 233883962 : for (i = 1; i < FIRST_REF_NODE; i++)
1936 : {
1937 229315008 : unsigned int node = si->node_mapping[i];
1938 :
1939 229315008 : if (graph->pointer_label[node] == 0)
1940 : {
1941 20301810 : if (dump_file && (dump_flags & TDF_DETAILS))
1942 926 : fprintf (dump_file,
1943 : "%s is a non-pointer variable, eliminating edges.\n",
1944 926 : get_varinfo (node)->name);
1945 20301810 : stats.nonpointer_vars++;
1946 20301810 : clear_edges_for_node (graph, node);
1947 : }
1948 : }
1949 :
1950 4568954 : return si;
1951 : }
1952 :
1953 : /* Free information that was only necessary for variable
1954 : substitution. */
1955 :
1956 : static void
1957 4568954 : free_var_substitution_info (class scc_info *si)
1958 : {
1959 4568954 : delete si;
1960 4568954 : free (graph->pointer_label);
1961 4568954 : free (graph->loc_label);
1962 4568954 : free (graph->pointed_by);
1963 4568954 : free (graph->points_to);
1964 4568954 : free (graph->eq_rep);
1965 4568954 : sbitmap_free (graph->direct_nodes);
1966 4568954 : delete pointer_equiv_class_table;
1967 4568954 : pointer_equiv_class_table = NULL;
1968 4568954 : delete location_equiv_class_table;
1969 4568954 : location_equiv_class_table = NULL;
1970 4568954 : obstack_free (&equiv_class_obstack, NULL);
1971 4568954 : bitmap_obstack_release (&iteration_obstack);
1972 4568954 : }
1973 :
1974 : /* Return an existing node that is equivalent to NODE, which has
1975 : equivalence class LABEL, if one exists. Return NODE otherwise. */
1976 :
1977 : static unsigned int
1978 901068442 : find_equivalent_node (constraint_graph_t graph,
1979 : unsigned int node, unsigned int label)
1980 : {
1981 : /* If the address version of this variable is unused, we can
1982 : substitute it for anything else with the same label.
1983 : Otherwise, we know the pointers are equivalent, but not the
1984 : locations, and we can unite them later. */
1985 :
1986 901068442 : if (!bitmap_bit_p (graph->address_taken, node))
1987 : {
1988 700842480 : gcc_checking_assert (label < graph->size);
1989 :
1990 700842480 : if (graph->eq_rep[label] != -1)
1991 : {
1992 : /* Unify the two variables since we know they are equivalent. */
1993 593311835 : if (unite (graph->eq_rep[label], node))
1994 : {
1995 43025134 : unify_nodes (graph, graph->eq_rep[label], node, false);
1996 43025134 : return graph->eq_rep[label];
1997 : }
1998 : }
1999 : else
2000 : {
2001 107530645 : graph->eq_rep[label] = node;
2002 107530645 : graph->pe_rep[label] = node;
2003 : }
2004 : }
2005 : else
2006 : {
2007 200225962 : gcc_checking_assert (label < graph->size);
2008 200225962 : graph->pe[node] = label;
2009 200225962 : if (graph->pe_rep[label] == -1)
2010 22201416 : graph->pe_rep[label] = node;
2011 : }
2012 :
2013 : return node;
2014 : }
2015 :
2016 : /* Unite pointer equivalent but not location equivalent nodes in
2017 : GRAPH. This may only be performed once variable substitution is
2018 : finished. */
2019 :
2020 : static void
2021 4568954 : unite_pointer_equivalences (constraint_graph_t graph)
2022 : {
2023 4568954 : unsigned int i;
2024 :
2025 : /* Go through the pointer equivalences and unite them to their
2026 : representative, if they aren't already. */
2027 233883962 : for (i = 1; i < FIRST_REF_NODE; i++)
2028 : {
2029 229315008 : unsigned int label = graph->pe[i];
2030 229315008 : if (label)
2031 : {
2032 22291507 : int label_rep = graph->pe_rep[label];
2033 :
2034 22291507 : if (label_rep == -1)
2035 0 : continue;
2036 :
2037 22291507 : label_rep = find (label_rep);
2038 22291507 : if (label_rep >= 0 && unite (label_rep, find (i)))
2039 790623 : unify_nodes (graph, label_rep, i, false);
2040 : }
2041 : }
2042 4568954 : }
2043 :
2044 : /* Move complex constraints to the GRAPH nodes they belong to. */
2045 :
2046 : static void
2047 4568954 : move_complex_constraints (constraint_graph_t graph)
2048 : {
2049 4568954 : int i;
2050 4568954 : constraint_t c;
2051 :
2052 457619970 : FOR_EACH_VEC_ELT (constraints, i, c)
2053 : {
2054 453051016 : if (c)
2055 : {
2056 450534221 : struct constraint_expr lhs = c->lhs;
2057 450534221 : struct constraint_expr rhs = c->rhs;
2058 :
2059 450534221 : if (lhs.type == DEREF)
2060 : {
2061 37169019 : insert_into_complex (graph, lhs.var, c);
2062 : }
2063 413365202 : else if (rhs.type == DEREF)
2064 : {
2065 50171657 : if (!(get_varinfo (lhs.var)->is_special_var))
2066 50171654 : insert_into_complex (graph, rhs.var, c);
2067 : }
2068 363193545 : else if (rhs.type != ADDRESSOF && lhs.var > anything_id
2069 269815918 : && (lhs.offset != 0 || rhs.offset != 0))
2070 : {
2071 62264616 : insert_into_complex (graph, rhs.var, c);
2072 : }
2073 : }
2074 : }
2075 4568954 : }
2076 :
2077 : /* Optimize and rewrite complex constraints while performing
2078 : collapsing of equivalent nodes. SI is the SCC_INFO that is the
2079 : result of perform_variable_substitution. */
2080 :
2081 : static void
2082 4568954 : rewrite_constraints (constraint_graph_t graph,
2083 : class scc_info *si)
2084 : {
2085 4568954 : int i;
2086 4568954 : constraint_t c;
2087 :
2088 4568954 : if (flag_checking)
2089 : {
2090 472333730 : for (unsigned int j = 0; j < graph->size; j++)
2091 467764836 : gcc_assert (find (j) == j);
2092 : }
2093 :
2094 457619970 : FOR_EACH_VEC_ELT (constraints, i, c)
2095 : {
2096 453051016 : struct constraint_expr lhs = c->lhs;
2097 453051016 : struct constraint_expr rhs = c->rhs;
2098 453051016 : unsigned int lhsvar = find (lhs.var);
2099 453051016 : unsigned int rhsvar = find (rhs.var);
2100 453051016 : unsigned int lhsnode, rhsnode;
2101 453051016 : unsigned int lhslabel, rhslabel;
2102 :
2103 453051016 : lhsnode = si->node_mapping[lhsvar];
2104 453051016 : rhsnode = si->node_mapping[rhsvar];
2105 453051016 : lhslabel = graph->pointer_label[lhsnode];
2106 453051016 : rhslabel = graph->pointer_label[rhsnode];
2107 :
2108 : /* See if it is really a non-pointer variable, and if so, ignore
2109 : the constraint. */
2110 453051016 : if (lhslabel == 0)
2111 : {
2112 791346 : if (dump_file && (dump_flags & TDF_DETAILS))
2113 : {
2114 :
2115 44 : fprintf (dump_file, "%s is a non-pointer variable, "
2116 : "ignoring constraint:",
2117 22 : get_varinfo (lhs.var)->name);
2118 22 : dump_constraint (dump_file, c);
2119 22 : fprintf (dump_file, "\n");
2120 : }
2121 791346 : constraints[i] = NULL;
2122 453051016 : continue;
2123 : }
2124 :
2125 452259670 : if (rhslabel == 0)
2126 : {
2127 1725449 : if (dump_file && (dump_flags & TDF_DETAILS))
2128 : {
2129 :
2130 90 : fprintf (dump_file, "%s is a non-pointer variable, "
2131 : "ignoring constraint:",
2132 45 : get_varinfo (rhs.var)->name);
2133 45 : dump_constraint (dump_file, c);
2134 45 : fprintf (dump_file, "\n");
2135 : }
2136 1725449 : constraints[i] = NULL;
2137 1725449 : continue;
2138 : }
2139 :
2140 450534221 : lhsvar = find_equivalent_node (graph, lhsvar, lhslabel);
2141 450534221 : rhsvar = find_equivalent_node (graph, rhsvar, rhslabel);
2142 450534221 : c->lhs.var = lhsvar;
2143 450534221 : c->rhs.var = rhsvar;
2144 : }
2145 4568954 : }
2146 :
2147 : /* Eliminate indirect cycles involving NODE. Return true if NODE was
2148 : part of an SCC, false otherwise. */
2149 :
2150 : static bool
2151 461976542 : eliminate_indirect_cycles (unsigned int node)
2152 : {
2153 461976542 : if (graph->indirect_cycles[node] != -1
2154 462308672 : && !bitmap_empty_p (get_varinfo (node)->solution))
2155 : {
2156 298290 : unsigned int i;
2157 298290 : auto_vec<unsigned> queue;
2158 298290 : int queuepos;
2159 298290 : unsigned int to = find (graph->indirect_cycles[node]);
2160 298290 : bitmap_iterator bi;
2161 :
2162 : /* We can't touch the solution set and call unify_nodes
2163 : at the same time, because unify_nodes is going to do
2164 : bitmap unions into it. */
2165 :
2166 1132859 : EXECUTE_IF_SET_IN_BITMAP (get_varinfo (node)->solution, 0, i, bi)
2167 : {
2168 834569 : if (find (i) == i && i != to)
2169 : {
2170 514882 : if (unite (to, i))
2171 60180 : queue.safe_push (i);
2172 : }
2173 : }
2174 :
2175 60180 : for (queuepos = 0;
2176 373201 : queue.iterate (queuepos, &i);
2177 : queuepos++)
2178 : {
2179 60180 : unify_nodes (graph, to, i, true);
2180 : }
2181 298290 : return true;
2182 298290 : }
2183 : return false;
2184 : }
2185 :
2186 : /* Solve the constraint graph GRAPH using our worklist solver.
2187 : This is based on the PW* family of solvers from the "Efficient Field
2188 : Sensitive Pointer Analysis for C" paper.
2189 : It works by iterating over all the graph nodes, processing the complex
2190 : constraints and propagating the copy constraints, until everything stops
2191 : changed. This corresponds to steps 6-8 in the solving list given above. */
2192 :
2193 : static void
2194 4568954 : solve_graph (constraint_graph_t graph)
2195 : {
2196 4568954 : unsigned int size = graph->size;
2197 4568954 : unsigned int i;
2198 4568954 : bitmap pts;
2199 :
2200 4568954 : changed = BITMAP_ALLOC (NULL);
2201 :
2202 : /* Mark all initial non-collapsed nodes as changed. */
2203 233883962 : for (i = 1; i < size; i++)
2204 : {
2205 229315008 : varinfo_t ivi = get_varinfo (i);
2206 414800022 : if (find (i) == i && !bitmap_empty_p (ivi->solution)
2207 287402305 : && ((graph->succs[i] && !bitmap_empty_p (graph->succs[i]))
2208 237232223 : || graph->complex[i].length () > 0))
2209 37134833 : bitmap_set_bit (changed, i);
2210 : }
2211 :
2212 : /* Allocate a bitmap to be used to store the changed bits. */
2213 4568954 : pts = BITMAP_ALLOC (&pta_obstack);
2214 :
2215 17267425 : while (!bitmap_empty_p (changed))
2216 : {
2217 8129517 : unsigned int i;
2218 8129517 : stats.iterations++;
2219 :
2220 8129517 : bitmap_obstack_initialize (&iteration_obstack);
2221 :
2222 8129517 : auto_vec<unsigned> topo_order = compute_topo_order (graph);
2223 478255749 : while (topo_order.length () != 0)
2224 : {
2225 461996715 : i = topo_order.pop ();
2226 :
2227 : /* If this variable is not a representative, skip it. */
2228 461996715 : if (find (i) != i)
2229 20173 : continue;
2230 :
2231 : /* In certain indirect cycle cases, we may merge this
2232 : variable to another. */
2233 461976542 : if (eliminate_indirect_cycles (i) && find (i) != i)
2234 93 : continue;
2235 :
2236 : /* If the node has changed, we need to process the
2237 : complex constraints and outgoing edges again. For complex
2238 : constraints that modify i itself, like the common group of
2239 : callarg = callarg + UNKNOWN;
2240 : callarg = *callarg + UNKNOWN;
2241 : *callarg = callescape;
2242 : make sure to iterate immediately because that maximizes
2243 : cache reuse and expands the graph quickest, leading to
2244 : better visitation order in the next iteration. */
2245 634875080 : while (bitmap_clear_bit (changed, i))
2246 : {
2247 173159219 : bitmap solution;
2248 173159219 : vec<constraint_t> &complex = graph->complex[i];
2249 173159219 : varinfo_t vi = get_varinfo (i);
2250 173159219 : bool solution_empty;
2251 :
2252 : /* Compute the changed set of solution bits. If anything
2253 : is in the solution just propagate that. */
2254 173159219 : if (bitmap_bit_p (vi->solution, anything_id))
2255 : {
2256 : /* If anything is also in the old solution there is
2257 : nothing to do.
2258 : ??? But we shouldn't ended up with "changed" set ... */
2259 2734285 : if (vi->oldsolution
2260 2734285 : && bitmap_bit_p (vi->oldsolution, anything_id))
2261 : break;
2262 2473697 : bitmap_copy (pts, get_varinfo (find (anything_id))->solution);
2263 : }
2264 170424934 : else if (vi->oldsolution)
2265 35999332 : bitmap_and_compl (pts, vi->solution, vi->oldsolution);
2266 : else
2267 134425602 : bitmap_copy (pts, vi->solution);
2268 :
2269 172898631 : if (bitmap_empty_p (pts))
2270 : break;
2271 :
2272 172898631 : if (vi->oldsolution)
2273 37225510 : bitmap_ior_into (vi->oldsolution, pts);
2274 : else
2275 : {
2276 135673121 : vi->oldsolution = BITMAP_ALLOC (&oldpta_obstack);
2277 135673121 : bitmap_copy (vi->oldsolution, pts);
2278 : }
2279 :
2280 172898631 : solution = vi->solution;
2281 172898631 : solution_empty = bitmap_empty_p (solution);
2282 :
2283 : /* Process the complex constraints. */
2284 172898631 : hash_set<constraint_t> *cvisited = nullptr;
2285 172898631 : if (flag_checking)
2286 172897782 : cvisited = new hash_set<constraint_t>;
2287 172898631 : bitmap expanded_pts = NULL;
2288 384889810 : for (unsigned j = 0; j < complex.length (); ++j)
2289 : {
2290 211991179 : constraint_t c = complex[j];
2291 : /* At unification time only the directly involved nodes
2292 : will get their complex constraints updated. Update
2293 : our complex constraints now but keep the constraint
2294 : vector sorted and clear of duplicates. Also make
2295 : sure to evaluate each prevailing constraint only once. */
2296 211991179 : unsigned int new_lhs = find (c->lhs.var);
2297 211991179 : unsigned int new_rhs = find (c->rhs.var);
2298 211991179 : if (c->lhs.var != new_lhs || c->rhs.var != new_rhs)
2299 : {
2300 94078 : constraint tem = *c;
2301 94078 : tem.lhs.var = new_lhs;
2302 94078 : tem.rhs.var = new_rhs;
2303 94078 : unsigned int place
2304 94078 : = complex.lower_bound (&tem, constraint_less);
2305 94078 : c->lhs.var = new_lhs;
2306 94078 : c->rhs.var = new_rhs;
2307 94078 : if (place != j)
2308 : {
2309 85263 : complex.ordered_remove (j);
2310 85263 : if (j < place)
2311 72681 : --place;
2312 85263 : if (place < complex.length ())
2313 : {
2314 30723 : if (constraint_equal (*complex[place], *c))
2315 : {
2316 12726 : j--;
2317 41096 : continue;
2318 : }
2319 : else
2320 17997 : complex.safe_insert (place, c);
2321 : }
2322 : else
2323 54540 : complex.quick_push (c);
2324 72537 : if (place > j)
2325 : {
2326 28370 : j--;
2327 28370 : continue;
2328 : }
2329 : }
2330 : }
2331 :
2332 : /* The only complex constraint that can change our
2333 : solution to non-empty, given an empty solution,
2334 : is a constraint where the lhs side is receiving
2335 : some set from elsewhere. */
2336 211950083 : if (cvisited && cvisited->add (c))
2337 0 : gcc_unreachable ();
2338 211950083 : if (!solution_empty || c->lhs.type != DEREF)
2339 211950083 : do_complex_constraint (graph, c, pts, &expanded_pts);
2340 : }
2341 172898631 : if (cvisited)
2342 : {
2343 : /* When checking, verify the order of constraints is
2344 : maintained and each constraint is evaluated exactly
2345 : once. */
2346 302521803 : for (unsigned j = 1; j < complex.length (); ++j)
2347 129624021 : gcc_assert (constraint_less (complex[j-1], complex[j]));
2348 255222784 : gcc_assert (cvisited->elements () == complex.length ());
2349 172897782 : delete cvisited;
2350 : }
2351 172898631 : BITMAP_FREE (expanded_pts);
2352 :
2353 172898631 : solution_empty = bitmap_empty_p (solution);
2354 :
2355 172898631 : if (!solution_empty)
2356 : {
2357 172898631 : bitmap_iterator bi;
2358 172898631 : unsigned eff_escaped_id = find (escaped_id);
2359 172898631 : unsigned j;
2360 :
2361 : /* Propagate solution to all successors. */
2362 172898631 : unsigned to_remove = ~0U;
2363 456141398 : EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i],
2364 : 0, j, bi)
2365 : {
2366 283242767 : if (to_remove != ~0U)
2367 : {
2368 775651 : bitmap_clear_bit (graph->succs[i], to_remove);
2369 775651 : to_remove = ~0U;
2370 : }
2371 283242767 : unsigned int to = find (j);
2372 283242767 : if (to != j)
2373 : {
2374 : /* Update the succ graph, avoiding duplicate
2375 : work. */
2376 837669 : to_remove = j;
2377 837669 : if (! bitmap_set_bit (graph->succs[i], to))
2378 128143 : continue;
2379 : /* We eventually end up processing 'to' twice
2380 : as it is undefined whether bitmap iteration
2381 : iterates over bits set during iteration.
2382 : Play safe instead of doing tricks. */
2383 : }
2384 : /* Don't try to propagate to ourselves. */
2385 283114624 : if (to == i)
2386 : {
2387 117469 : to_remove = j;
2388 117469 : continue;
2389 : }
2390 : /* Early node unification can lead to edges from
2391 : escaped - remove them. */
2392 282997155 : if (i == eff_escaped_id)
2393 : {
2394 20122 : to_remove = j;
2395 20122 : if (bitmap_set_bit (get_varinfo (to)->solution,
2396 : escaped_id))
2397 19340 : bitmap_set_bit (changed, to);
2398 20122 : continue;
2399 : }
2400 :
2401 282977033 : if (bitmap_ior_into (get_varinfo (to)->solution, pts))
2402 140879270 : bitmap_set_bit (changed, to);
2403 : }
2404 107306283 : if (to_remove != ~0U)
2405 133863 : bitmap_clear_bit (graph->succs[i], to_remove);
2406 : }
2407 : }
2408 : }
2409 8129517 : bitmap_obstack_release (&iteration_obstack);
2410 8129517 : }
2411 :
2412 4568954 : BITMAP_FREE (pts);
2413 4568954 : BITMAP_FREE (changed);
2414 4568954 : bitmap_obstack_release (&oldpta_obstack);
2415 4568954 : }
2416 :
2417 : void
2418 4568954 : delete_graph (void)
2419 : {
2420 4568954 : unsigned int i;
2421 238452916 : for (i = 0; i < graph->size; i++)
2422 233883962 : graph->complex[i].release ();
2423 4568954 : free (graph->complex);
2424 :
2425 4568954 : free (graph->succs);
2426 4568954 : free (graph->pe);
2427 4568954 : free (graph->pe_rep);
2428 4568954 : free (graph->indirect_cycles);
2429 : /* We are not doing free (graph->rep) since the representatives mapping is
2430 : needed outside of the solver too. */
2431 4568954 : free (graph);
2432 4568954 : }
2433 :
2434 : /* Remove the REF and ADDRESS edges from GRAPH, as well as all the
2435 : predecessor edges. */
2436 :
2437 : static void
2438 4568954 : remove_preds_and_fake_succs (constraint_graph_t graph)
2439 : {
2440 4568954 : unsigned int i;
2441 :
2442 : /* Clear the implicit ref and address nodes from the successor
2443 : lists. */
2444 233883962 : for (i = 1; i < FIRST_REF_NODE; i++)
2445 : {
2446 229315008 : if (graph->succs[i])
2447 74586847 : bitmap_clear_range (graph->succs[i], FIRST_REF_NODE,
2448 74586847 : FIRST_REF_NODE * 2);
2449 : }
2450 :
2451 : /* Free the successor list for the non-ref nodes. */
2452 238452916 : for (i = FIRST_REF_NODE + 1; i < graph->size; i++)
2453 : {
2454 229315008 : if (graph->succs[i])
2455 12162317 : BITMAP_FREE (graph->succs[i]);
2456 : }
2457 :
2458 : /* Now reallocate the size of the successor list as, and blow away
2459 : the predecessor bitmaps. */
2460 4568954 : graph->size = varmap.length ();
2461 4568954 : graph->succs = XRESIZEVEC (bitmap, graph->succs, graph->size);
2462 :
2463 4568954 : free (graph->implicit_preds);
2464 4568954 : graph->implicit_preds = NULL;
2465 4568954 : free (graph->preds);
2466 4568954 : graph->preds = NULL;
2467 4568954 : bitmap_obstack_release (&predbitmap_obstack);
2468 4568954 : }
2469 :
2470 : namespace pointer_analysis {
2471 :
2472 : /* Solve the constraint set. The entry function of the solver. */
2473 :
2474 : void
2475 4568954 : solve_constraints (void)
2476 : {
2477 4568954 : class scc_info *si;
2478 :
2479 : /* Sort varinfos so that ones that cannot be pointed to are last.
2480 : This makes bitmaps more efficient. */
2481 4568954 : unsigned int *map = XNEWVEC (unsigned int, varmap.length ());
2482 50258494 : for (unsigned i = 0; i < integer_id + 1; ++i)
2483 41120586 : map[i] = i;
2484 : /* Start with address-taken vars, followed by not address-taken vars
2485 : to move vars never appearing in the points-to solution bitmaps last. */
2486 : unsigned j = integer_id + 1;
2487 394664660 : for (unsigned i = integer_id + 1; i < varmap.length (); ++i)
2488 192763376 : if (varmap[varmap[i]->head]->address_taken)
2489 15827253 : map[i] = j++;
2490 197332330 : for (unsigned i = integer_id + 1; i < varmap.length (); ++i)
2491 192763376 : if (! varmap[varmap[i]->head]->address_taken)
2492 176936123 : map[i] = j++;
2493 : /* Shuffle varmap according to map. */
2494 197332330 : for (unsigned i = integer_id + 1; i < varmap.length (); ++i)
2495 : {
2496 287062261 : while (map[varmap[i]->id] != i)
2497 94298885 : std::swap (varmap[i], varmap[map[varmap[i]->id]]);
2498 192763376 : gcc_assert (bitmap_empty_p (varmap[i]->solution));
2499 192763376 : varmap[i]->id = i;
2500 192763376 : varmap[i]->next = map[varmap[i]->next];
2501 192763376 : varmap[i]->head = map[varmap[i]->head];
2502 : }
2503 : /* Finally rewrite constraints. */
2504 457619970 : for (unsigned i = 0; i < constraints.length (); ++i)
2505 : {
2506 453051016 : constraints[i]->lhs.var = map[constraints[i]->lhs.var];
2507 453051016 : constraints[i]->rhs.var = map[constraints[i]->rhs.var];
2508 : }
2509 4568954 : free (map);
2510 :
2511 4568954 : if (dump_file)
2512 489 : fprintf (dump_file,
2513 : "\nCollapsing static cycles and doing variable "
2514 : "substitution\n");
2515 :
2516 9137908 : init_graph (varmap.length () * 2);
2517 :
2518 4568954 : if (dump_file)
2519 489 : fprintf (dump_file, "Building predecessor graph\n");
2520 4568954 : build_pred_graph ();
2521 :
2522 4568954 : if (dump_file)
2523 489 : fprintf (dump_file, "Detecting pointer and location "
2524 : "equivalences\n");
2525 4568954 : si = perform_var_substitution (graph);
2526 :
2527 4568954 : if (dump_file)
2528 489 : fprintf (dump_file, "Rewriting constraints and unifying "
2529 : "variables\n");
2530 4568954 : rewrite_constraints (graph, si);
2531 :
2532 4568954 : build_succ_graph ();
2533 :
2534 4568954 : free_var_substitution_info (si);
2535 :
2536 : /* Attach complex constraints to graph nodes. */
2537 4568954 : move_complex_constraints (graph);
2538 :
2539 4568954 : if (dump_file)
2540 489 : fprintf (dump_file, "Uniting pointer but not location equivalent "
2541 : "variables\n");
2542 4568954 : unite_pointer_equivalences (graph);
2543 :
2544 4568954 : if (dump_file)
2545 489 : fprintf (dump_file, "Finding indirect cycles\n");
2546 4568954 : find_indirect_cycles (graph);
2547 :
2548 : /* Implicit nodes and predecessors are no longer necessary at this
2549 : point. */
2550 4568954 : remove_preds_and_fake_succs (graph);
2551 :
2552 4568954 : if (dump_file && (dump_flags & TDF_GRAPH))
2553 : {
2554 3 : fprintf (dump_file, "\n\n// The constraint graph before solve-graph "
2555 : "in dot format:\n");
2556 3 : dump_constraint_graph (dump_file);
2557 3 : fprintf (dump_file, "\n\n");
2558 : }
2559 :
2560 4568954 : if (dump_file)
2561 489 : fprintf (dump_file, "Solving graph\n");
2562 :
2563 4568954 : solve_graph (graph);
2564 :
2565 4568954 : if (dump_file && (dump_flags & TDF_GRAPH))
2566 : {
2567 3 : fprintf (dump_file, "\n\n// The constraint graph after solve-graph "
2568 : "in dot format:\n");
2569 3 : dump_constraint_graph (dump_file);
2570 3 : fprintf (dump_file, "\n\n");
2571 : }
2572 :
2573 : /* The mapping node -> representative is one of the outputs of the
2574 : solver. */
2575 4568954 : union_find_compress_all ();
2576 4568954 : var_rep = graph->rep;
2577 :
2578 4568954 : delete_graph ();
2579 4568954 : }
2580 :
2581 : } // namespace pointer_analysis
|