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 8793153692 : find (unsigned int node)
136 : {
137 8793153692 : gcc_checking_assert (node < graph->size);
138 8793153692 : if (graph->rep[node] != node)
139 431051465 : 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 620562618 : unite (unsigned int to, unsigned int from)
150 : {
151 620562618 : gcc_checking_assert (to < graph->size && from < graph->size);
152 620562618 : if (to != from
153 121148910 : && graph->rep[from] != to
154 : /* Do not merge an artificial variable into another, this will
155 : explode solution sets unnecessarily. */
156 862736907 : && (from >= FIRST_REF_NODE || !get_varinfo (from)->is_artificial_var))
157 : {
158 44102250 : graph->rep[from] = to;
159 44102250 : 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 4624489 : union_find_compress_all (void)
169 : {
170 4624489 : unsigned int i;
171 240185108 : for (i = 0; i < graph->size; i++)
172 235560619 : find (i);
173 4624489 : }
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 18322641 : constraint_expr_equal (struct constraint_expr a, struct constraint_expr b)
292 : {
293 11050274 : 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 455523185 : constraint_expr_less (struct constraint_expr a, struct constraint_expr b)
302 : {
303 0 : if (a.type == b.type)
304 : {
305 271091158 : if (a.var == b.var)
306 204264662 : return a.offset < b.offset;
307 : else
308 66826496 : return a.var < b.var;
309 : }
310 : else
311 184432027 : 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 251021043 : constraint_less (const constraint_t &a, const constraint_t &b)
319 : {
320 502042086 : if (constraint_expr_less (a->lhs, b->lhs))
321 : return true;
322 215851684 : else if (constraint_expr_less (b->lhs, a->lhs))
323 : return false;
324 : else
325 96576300 : 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 12063652 : constraint_equal (const constraint &a, const constraint &b)
332 : {
333 18322641 : return constraint_expr_equal (a.lhs, b.lhs)
334 12063652 : && 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 12349 : constraint_vec_find (vec<constraint_t> vec,
341 : constraint &lookfor)
342 : {
343 12349 : unsigned int place;
344 12349 : constraint_t found;
345 :
346 12349 : if (!vec.exists ())
347 : return NULL;
348 :
349 10090 : place = vec.lower_bound (&lookfor, constraint_less);
350 10090 : if (place >= vec.length ())
351 : return NULL;
352 4331 : found = vec[place];
353 4331 : if (!constraint_equal (*found, lookfor))
354 4244 : 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 43979015 : constraint_set_union (vec<constraint_t> *to,
363 : vec<constraint_t> *from)
364 : {
365 43979015 : int i;
366 43979015 : constraint_t c;
367 43979015 : bool any_change = false;
368 :
369 43991364 : FOR_EACH_VEC_ELT (*from, i, c)
370 : {
371 12349 : if (constraint_vec_find (*to, *c) == NULL)
372 : {
373 12262 : unsigned int place = to->lower_bound (c, constraint_less);
374 12262 : to->safe_insert (place, c);
375 12262 : any_change = true;
376 : }
377 : }
378 43979015 : return any_change;
379 : }
380 :
381 : /* Expands the solution in SET to all sub-fields of variables included. */
382 :
383 : static bitmap
384 137686097 : solution_set_expand (bitmap set, bitmap *expanded)
385 : {
386 137686097 : bitmap_iterator bi;
387 137686097 : unsigned j;
388 :
389 137686097 : if (*expanded)
390 : return *expanded;
391 :
392 76966660 : *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 76966660 : unsigned prev_head = 0;
397 263512993 : EXECUTE_IF_SET_IN_BITMAP (set, 0, j, bi)
398 : {
399 186546333 : varinfo_t v = get_varinfo (j);
400 186546333 : if (v->is_artificial_var
401 92474151 : || v->is_full_var)
402 110686772 : continue;
403 75859561 : if (v->head != prev_head)
404 : {
405 19346431 : varinfo_t head = get_varinfo (v->head);
406 19346431 : unsigned num = 1;
407 114016460 : for (varinfo_t n = vi_next (head); n != NULL; n = vi_next (n))
408 : {
409 94670029 : 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 15061 : bitmap_set_range (*expanded, head->id, num);
415 15061 : head = n;
416 15061 : num = 1;
417 : }
418 : else
419 94654968 : num++;
420 : }
421 :
422 19346431 : bitmap_set_range (*expanded, head->id, num);
423 19346431 : prev_head = v->head;
424 : }
425 : }
426 :
427 : /* And finally set the rest of the bits from SET in an efficient way. */
428 76966660 : bitmap_ior_into (*expanded, set);
429 :
430 76966660 : 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 86561521 : set_union_with_increment (bitmap to, bitmap delta, HOST_WIDE_INT inc,
438 : bitmap *expanded_delta)
439 : {
440 86561521 : bool changed = false;
441 86561521 : bitmap_iterator bi;
442 86561521 : unsigned int i;
443 :
444 : /* If the solution of DELTA contains anything it is good enough to transfer
445 : this to TO. */
446 86561521 : if (bitmap_bit_p (delta, anything_id))
447 1186052 : 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 85375469 : if (inc == UNKNOWN_OFFSET)
452 : {
453 84388893 : delta = solution_set_expand (delta, expanded_delta);
454 84388893 : changed |= bitmap_ior_into (to, delta);
455 84388893 : return changed;
456 : }
457 :
458 : /* For non-zero offset union the offsetted solution into the destination. */
459 3469544 : EXECUTE_IF_SET_IN_BITMAP (delta, 0, i, bi)
460 : {
461 2482968 : 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 2482968 : if (vi->is_artificial_var
466 1175234 : || vi->is_unknown_size_var
467 1029742 : || vi->is_full_var)
468 1644825 : changed |= bitmap_set_bit (to, i);
469 : else
470 : {
471 838143 : HOST_WIDE_INT fieldoffset = vi->offset + inc;
472 838143 : 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 838143 : if (fieldoffset < 0)
477 71220 : vi = get_varinfo (vi->head);
478 : else
479 766923 : vi = first_or_preceding_vi_for_offset (vi, fieldoffset);
480 :
481 1855121 : do
482 : {
483 1855121 : changed |= bitmap_set_bit (to, vi->id);
484 1855121 : if (vi->is_full_var
485 1855081 : || vi->next == 0)
486 : break;
487 :
488 : /* We have to include all fields that overlap the current field
489 : shifted by inc. */
490 1306652 : vi = vi_next (vi);
491 : }
492 1306652 : 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 150825843 : insert_into_complex (constraint_graph_t graph,
504 : unsigned int var, constraint_t c)
505 : {
506 150825843 : vec<constraint_t> complex = graph->complex[var];
507 150825843 : unsigned int place = complex.lower_bound (c, constraint_less);
508 :
509 : /* Only insert constraints that do not already exist. */
510 150825843 : if (place >= complex.length ()
511 102777106 : || !constraint_equal (*c, *complex[place]))
512 149330546 : graph->complex[var].safe_insert (place, c);
513 150825843 : }
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 43979015 : merge_node_constraints (constraint_graph_t graph, unsigned int to,
522 : unsigned int from)
523 : {
524 43979015 : unsigned int i;
525 43979015 : constraint_t c;
526 43979015 : bool any_change = false;
527 :
528 43979015 : gcc_checking_assert (find (from) == to);
529 :
530 : /* Move all complex constraints from src node into to node. */
531 43991364 : 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 12349 : if (c->rhs.type == DEREF)
538 2989 : c->rhs.var = to;
539 9360 : else if (c->lhs.type == DEREF)
540 4630 : c->lhs.var = to;
541 : else
542 4730 : c->rhs.var = to;
543 :
544 : }
545 43979015 : any_change = constraint_set_union (&graph->complex[to],
546 : &graph->complex[from]);
547 43979015 : graph->complex[from].release ();
548 43979015 : return any_change;
549 : }
550 :
551 : /* Remove edges involving NODE from GRAPH. */
552 :
553 : static void
554 64468718 : clear_edges_for_node (constraint_graph_t graph, unsigned int node)
555 : {
556 64468718 : if (graph->succs[node])
557 818547 : BITMAP_FREE (graph->succs[node]);
558 64468718 : }
559 :
560 : /* Merge GRAPH nodes FROM and TO into node TO. */
561 :
562 : static void
563 43979015 : merge_graph_nodes (constraint_graph_t graph, unsigned int to,
564 : unsigned int from)
565 : {
566 43979015 : if (graph->indirect_cycles[from] != -1)
567 : {
568 : /* If we have indirect cycles with the from node, and we have
569 : none on the to node, the to node has indirect cycles from the
570 : from node now that they are unified.
571 : If indirect cycles exist on both, unify the nodes that they
572 : are in a cycle with, since we know they are in a cycle with
573 : each other. */
574 108 : if (graph->indirect_cycles[to] == -1)
575 83 : graph->indirect_cycles[to] = graph->indirect_cycles[from];
576 : }
577 :
578 : /* Merge all the successor edges. */
579 43979015 : if (graph->succs[from])
580 : {
581 818547 : if (!graph->succs[to])
582 427279 : graph->succs[to] = BITMAP_ALLOC (&pta_obstack);
583 818547 : bitmap_ior_into (graph->succs[to],
584 818547 : graph->succs[from]);
585 : }
586 :
587 43979015 : clear_edges_for_node (graph, from);
588 43979015 : }
589 :
590 :
591 : /* Add an indirect graph edge to GRAPH, going from TO to FROM if
592 : it doesn't exist in the graph already. */
593 :
594 : static void
595 303703445 : add_implicit_graph_edge (constraint_graph_t graph, unsigned int to,
596 : unsigned int from)
597 : {
598 303703445 : if (to == from)
599 : return;
600 :
601 303703445 : if (!graph->implicit_preds[to])
602 170235003 : graph->implicit_preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
603 :
604 303703445 : if (bitmap_set_bit (graph->implicit_preds[to], from))
605 285547571 : stats.num_implicit_edges++;
606 : }
607 :
608 : /* Add a predecessor graph edge to GRAPH, going from TO to FROM if
609 : it doesn't exist in the graph already.
610 : Return false if the edge already existed, true otherwise. */
611 :
612 : static void
613 256849911 : add_pred_graph_edge (constraint_graph_t graph, unsigned int to,
614 : unsigned int from)
615 : {
616 256849911 : if (!graph->preds[to])
617 151533543 : graph->preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
618 256849911 : bitmap_set_bit (graph->preds[to], from);
619 256849911 : }
620 :
621 : /* Add a graph edge to GRAPH, going from FROM to TO if
622 : it doesn't exist in the graph already.
623 : Return false if the edge already existed, true otherwise. */
624 :
625 : static bool
626 708138766 : add_graph_edge (constraint_graph_t graph, unsigned int to,
627 : unsigned int from)
628 : {
629 708138766 : if (to == from)
630 : {
631 : return false;
632 : }
633 : else
634 : {
635 707878587 : bool r = false;
636 :
637 707878587 : if (!graph->succs[from])
638 104445035 : graph->succs[from] = BITMAP_ALLOC (&pta_obstack);
639 :
640 : /* The graph solving process does not avoid "triangles", thus
641 : there can be multiple paths from a node to another involving
642 : intermediate other nodes. That causes extra copying which is
643 : most difficult to avoid when the intermediate node is ESCAPED
644 : because there are no edges added from ESCAPED. Avoid
645 : adding the direct edge FROM -> TO when we have FROM -> ESCAPED
646 : and TO contains ESCAPED.
647 : ??? Note this is only a heuristic, it does not prevent the
648 : situation from occurring. The heuristic helps PR38474 and
649 : PR99912 significantly. */
650 707878587 : if (to < FIRST_REF_NODE
651 674941026 : && bitmap_bit_p (graph->succs[from], find (escaped_id))
652 948416992 : && bitmap_bit_p (get_varinfo (find (to))->solution, escaped_id))
653 : {
654 207138396 : stats.num_avoided_edges++;
655 207138396 : return false;
656 : }
657 :
658 500740191 : if (bitmap_set_bit (graph->succs[from], to))
659 : {
660 418647947 : r = true;
661 418647947 : if (to < FIRST_REF_NODE && from < FIRST_REF_NODE)
662 372977802 : stats.num_edges++;
663 : }
664 : return r;
665 : }
666 : }
667 :
668 : /* Initialize the constraint graph structure to contain SIZE nodes. */
669 :
670 : static void
671 4624489 : init_graph (unsigned int size)
672 : {
673 4624489 : unsigned int j;
674 :
675 4624489 : bitmap_obstack_initialize (&predbitmap_obstack);
676 :
677 4624489 : graph = XCNEW (struct constraint_graph);
678 4624489 : graph->size = size;
679 4624489 : graph->succs = XCNEWVEC (bitmap, graph->size);
680 4624489 : graph->indirect_cycles = XNEWVEC (int, graph->size);
681 4624489 : graph->rep = XNEWVEC (unsigned int, graph->size);
682 : /* ??? Macros do not support template types with multiple arguments,
683 : so we use a typedef to work around it. */
684 4624489 : typedef vec<constraint_t> vec_constraint_t_heap;
685 4624489 : graph->complex = XCNEWVEC (vec_constraint_t_heap, size);
686 4624489 : graph->pe = XCNEWVEC (unsigned int, graph->size);
687 4624489 : graph->pe_rep = XNEWVEC (int, graph->size);
688 :
689 475745727 : for (j = 0; j < graph->size; j++)
690 : {
691 471121238 : graph->rep[j] = j;
692 471121238 : graph->pe_rep[j] = -1;
693 471121238 : graph->indirect_cycles[j] = -1;
694 : }
695 4624489 : }
696 :
697 : /* Build the constraint graph, adding only predecessor edges right now. */
698 :
699 : static void
700 4624489 : build_pred_graph (void)
701 : {
702 4624489 : int i;
703 4624489 : constraint_t c;
704 4624489 : unsigned int j;
705 :
706 4624489 : graph->implicit_preds = XCNEWVEC (bitmap, graph->size);
707 4624489 : graph->preds = XCNEWVEC (bitmap, graph->size);
708 4624489 : graph->pointer_label = XCNEWVEC (unsigned int, graph->size);
709 4624489 : graph->loc_label = XCNEWVEC (unsigned int, graph->size);
710 4624489 : graph->pointed_by = XCNEWVEC (bitmap, graph->size);
711 4624489 : graph->points_to = XCNEWVEC (bitmap, graph->size);
712 4624489 : graph->eq_rep = XNEWVEC (int, graph->size);
713 4624489 : graph->direct_nodes = sbitmap_alloc (graph->size);
714 4624489 : graph->address_taken = BITMAP_ALLOC (&predbitmap_obstack);
715 4624489 : bitmap_clear (graph->direct_nodes);
716 :
717 475745727 : for (j = 1; j < FIRST_REF_NODE; j++)
718 : {
719 230936130 : if (!get_varinfo (j)->is_special_var)
720 207813685 : bitmap_set_bit (graph->direct_nodes, j);
721 : }
722 :
723 475745727 : for (j = 0; j < graph->size; j++)
724 471121238 : graph->eq_rep[j] = -1;
725 :
726 480370216 : for (j = 0; j < varmap.length (); j++)
727 235560619 : graph->indirect_cycles[j] = -1;
728 :
729 460410906 : FOR_EACH_VEC_ELT (constraints, i, c)
730 : {
731 455786417 : struct constraint_expr lhs = c->lhs;
732 455786417 : struct constraint_expr rhs = c->rhs;
733 455786417 : unsigned int lhsvar = lhs.var;
734 455786417 : unsigned int rhsvar = rhs.var;
735 :
736 455786417 : if (lhs.type == DEREF)
737 : {
738 : /* *x = y. */
739 37503374 : if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
740 : {
741 32957595 : if (lhs.var == anything_id)
742 0 : add_pred_graph_edge (graph, storedanything_id, rhsvar);
743 : else
744 65915190 : add_pred_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
745 : }
746 : }
747 418283043 : else if (rhs.type == DEREF)
748 : {
749 : /* x = *y */
750 50710733 : if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
751 27255084 : add_pred_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
752 : else
753 37083191 : bitmap_clear_bit (graph->direct_nodes, lhsvar);
754 : }
755 367572310 : else if (rhs.type == ADDRESSOF)
756 : {
757 93438671 : varinfo_t v;
758 :
759 : /* x = &y */
760 93438671 : if (graph->points_to[lhsvar] == NULL)
761 69330283 : graph->points_to[lhsvar] = BITMAP_ALLOC (&predbitmap_obstack);
762 93438671 : bitmap_set_bit (graph->points_to[lhsvar], rhsvar);
763 :
764 93438671 : if (graph->pointed_by[rhsvar] == NULL)
765 22525138 : graph->pointed_by[rhsvar] = BITMAP_ALLOC (&predbitmap_obstack);
766 93438671 : bitmap_set_bit (graph->pointed_by[rhsvar], lhsvar);
767 :
768 : /* Implicitly, *x = y */
769 186877342 : add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
770 :
771 : /* All related variables are no longer direct nodes. */
772 93438671 : bitmap_clear_bit (graph->direct_nodes, rhsvar);
773 93438671 : v = get_varinfo (rhsvar);
774 93438671 : if (!v->is_full_var)
775 : {
776 7943117 : v = get_varinfo (v->head);
777 51589748 : do
778 : {
779 51589748 : bitmap_clear_bit (graph->direct_nodes, v->id);
780 51589748 : v = vi_next (v);
781 : }
782 51589748 : while (v != NULL);
783 : }
784 93438671 : bitmap_set_bit (graph->address_taken, rhsvar);
785 : }
786 274133639 : else if (lhsvar > anything_id
787 274133639 : && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
788 : {
789 : /* x = y */
790 210264774 : add_pred_graph_edge (graph, lhsvar, rhsvar);
791 : /* Implicitly, *x = *y */
792 210264774 : add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar,
793 210264774 : FIRST_REF_NODE + rhsvar);
794 : }
795 63868865 : else if (lhs.offset != 0 || rhs.offset != 0)
796 : {
797 63672506 : if (rhs.offset != 0)
798 63672506 : bitmap_clear_bit (graph->direct_nodes, lhs.var);
799 0 : else if (lhs.offset != 0)
800 0 : bitmap_clear_bit (graph->direct_nodes, rhs.var);
801 : }
802 : }
803 4624489 : }
804 :
805 : /* Build the constraint graph, adding successor edges. */
806 :
807 : static void
808 4624489 : build_succ_graph (void)
809 : {
810 4624489 : unsigned i, t;
811 4624489 : constraint_t c;
812 :
813 460410906 : FOR_EACH_VEC_ELT (constraints, i, c)
814 : {
815 455786417 : struct constraint_expr lhs;
816 455786417 : struct constraint_expr rhs;
817 455786417 : unsigned int lhsvar;
818 455786417 : unsigned int rhsvar;
819 :
820 455786417 : if (!c)
821 2554388 : continue;
822 :
823 453232029 : lhs = c->lhs;
824 453232029 : rhs = c->rhs;
825 453232029 : lhsvar = find (lhs.var);
826 453232029 : rhsvar = find (rhs.var);
827 :
828 453232029 : if (lhs.type == DEREF)
829 : {
830 37462554 : if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
831 : {
832 32937561 : if (lhs.var == anything_id)
833 0 : add_graph_edge (graph, storedanything_id, rhsvar);
834 : else
835 65875122 : add_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
836 : }
837 : }
838 415769475 : else if (rhs.type == DEREF)
839 : {
840 50709803 : if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
841 27253610 : add_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
842 : }
843 365059672 : else if (rhs.type == ADDRESSOF)
844 : {
845 : /* x = &y */
846 93438671 : gcc_checking_assert (find (rhs.var) == rhs.var);
847 93438671 : bitmap_set_bit (get_varinfo (lhsvar)->solution, rhsvar);
848 : }
849 271621001 : else if (lhsvar > anything_id
850 271621001 : && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
851 : {
852 180420000 : add_graph_edge (graph, lhsvar, rhsvar);
853 : }
854 : }
855 :
856 : /* Add edges from STOREDANYTHING to all nodes that can receive pointers. */
857 4624489 : t = find (storedanything_id);
858 203189196 : for (i = integer_id + 1; i < FIRST_REF_NODE; ++i)
859 : {
860 193940218 : if (get_varinfo (i)->may_have_pointers)
861 193916333 : add_graph_edge (graph, find (i), t);
862 : }
863 :
864 : /* Everything stored to ANYTHING also potentially escapes. */
865 4624489 : add_graph_edge (graph, find (escaped_id), t);
866 4624489 : }
867 :
868 :
869 : /* Changed variables on the last iteration. */
870 : static bitmap changed;
871 :
872 : /* Strongly Connected Component visitation info. */
873 :
874 : class scc_info
875 : {
876 : public:
877 : scc_info (size_t size);
878 : ~scc_info ();
879 :
880 : auto_sbitmap visited;
881 : auto_sbitmap deleted;
882 : unsigned int *dfs;
883 : unsigned int *node_mapping;
884 : int current_index;
885 : auto_vec<unsigned> scc_stack;
886 : };
887 :
888 :
889 : /* Recursive routine to find strongly connected components in GRAPH.
890 : SI is the SCC info to store the information in, and N is the id of current
891 : graph node we are processing.
892 :
893 : This is Tarjan's strongly connected component finding algorithm, as
894 : modified by Nuutila to keep only non-root nodes on the stack.
895 : The algorithm can be found in "On finding the strongly connected
896 : connected components in a directed graph" by Esko Nuutila and Eljas
897 : Soisalon-Soininen, in Information Processing Letters volume 49,
898 : number 1, pages 9-14. */
899 :
900 : static void
901 423569458 : scc_visit (constraint_graph_t graph, class scc_info *si, unsigned int n)
902 : {
903 423569458 : unsigned int i;
904 423569458 : bitmap_iterator bi;
905 423569458 : unsigned int my_dfs;
906 :
907 423569458 : bitmap_set_bit (si->visited, n);
908 423569458 : si->dfs[n] = si->current_index ++;
909 423569458 : my_dfs = si->dfs[n];
910 :
911 : /* Visit all the successors. */
912 781884509 : EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[n], 0, i, bi)
913 : {
914 358315051 : unsigned int w;
915 :
916 716630102 : if (i > LAST_REF_NODE)
917 : break;
918 :
919 358315051 : w = find (i);
920 358315051 : if (bitmap_bit_p (si->deleted, w))
921 174164986 : continue;
922 :
923 184150065 : if (!bitmap_bit_p (si->visited, w))
924 183206675 : scc_visit (graph, si, w);
925 :
926 184150065 : unsigned int t = find (w);
927 184150065 : gcc_checking_assert (find (n) == n);
928 184150065 : if (si->dfs[t] < si->dfs[n])
929 638696 : si->dfs[n] = si->dfs[t];
930 : }
931 :
932 : /* See if any components have been identified. */
933 423569458 : if (si->dfs[n] == my_dfs)
934 : {
935 422932952 : if (si->scc_stack.length () > 0
936 422932952 : && si->dfs[si->scc_stack.last ()] >= my_dfs)
937 : {
938 191071 : bitmap scc = BITMAP_ALLOC (NULL);
939 191071 : unsigned int lowest_node;
940 191071 : bitmap_iterator bi;
941 :
942 191071 : bitmap_set_bit (scc, n);
943 :
944 191071 : while (si->scc_stack.length () != 0
945 599023 : && si->dfs[si->scc_stack.last ()] >= my_dfs)
946 : {
947 407952 : unsigned int w = si->scc_stack.pop ();
948 :
949 407952 : bitmap_set_bit (scc, w);
950 : }
951 :
952 191071 : lowest_node = bitmap_first_set_bit (scc);
953 191071 : gcc_assert (lowest_node < FIRST_REF_NODE);
954 :
955 : /* Collapse the SCC nodes into a single node, and mark the
956 : indirect cycles. */
957 790094 : EXECUTE_IF_SET_IN_BITMAP (scc, 0, i, bi)
958 : {
959 599023 : if (i < FIRST_REF_NODE)
960 : {
961 475788 : if (unite (lowest_node, i))
962 14387 : unify_nodes (graph, lowest_node, i, false);
963 : }
964 : else
965 : {
966 123235 : if (unite (lowest_node, i))
967 246470 : graph->indirect_cycles[i - FIRST_REF_NODE] = lowest_node;
968 : }
969 : }
970 191071 : bitmap_set_bit (si->deleted, lowest_node);
971 : }
972 : else
973 422741881 : bitmap_set_bit (si->deleted, n);
974 : }
975 : else
976 636506 : si->scc_stack.safe_push (n);
977 423569458 : }
978 :
979 : /* Unify node FROM into node TO, updating the changed count if
980 : necessary when UPDATE_CHANGED is true. */
981 :
982 : static void
983 43979015 : unify_nodes (constraint_graph_t graph, unsigned int to, unsigned int from,
984 : bool update_changed)
985 : {
986 43979015 : gcc_checking_assert (to != from && find (to) == to);
987 :
988 43979015 : if (dump_file && (dump_flags & TDF_DETAILS))
989 573 : fprintf (dump_file, "Unifying %s to %s\n",
990 573 : get_varinfo (from)->name,
991 573 : get_varinfo (to)->name);
992 :
993 43979015 : if (update_changed)
994 60324 : stats.unified_vars_dynamic++;
995 : else
996 43918691 : stats.unified_vars_static++;
997 :
998 43979015 : merge_graph_nodes (graph, to, from);
999 43979015 : if (merge_node_constraints (graph, to, from))
1000 : {
1001 3914 : if (update_changed)
1002 1288 : bitmap_set_bit (changed, to);
1003 : }
1004 :
1005 : /* Mark TO as changed if FROM was changed. If TO was already marked
1006 : as changed, decrease the changed count. */
1007 :
1008 43976389 : if (update_changed
1009 43976389 : && bitmap_clear_bit (changed, from))
1010 22782 : bitmap_set_bit (changed, to);
1011 43979015 : varinfo_t fromvi = get_varinfo (from);
1012 43979015 : if (fromvi->solution)
1013 : {
1014 : /* If the solution changes because of the merging, we need to mark
1015 : the variable as changed. */
1016 43979015 : varinfo_t tovi = get_varinfo (to);
1017 43979015 : if (bitmap_ior_into (tovi->solution, fromvi->solution))
1018 : {
1019 388824 : if (update_changed)
1020 9378 : bitmap_set_bit (changed, to);
1021 : }
1022 :
1023 43979015 : BITMAP_FREE (fromvi->solution);
1024 43979015 : if (fromvi->oldsolution)
1025 40236 : BITMAP_FREE (fromvi->oldsolution);
1026 :
1027 43979015 : if (stats.iterations > 0
1028 60324 : && tovi->oldsolution)
1029 4988 : BITMAP_FREE (tovi->oldsolution);
1030 : }
1031 43979015 : if (graph->succs[to])
1032 884106 : bitmap_clear_bit (graph->succs[to], to);
1033 43979015 : }
1034 :
1035 : /* Add a copy edge FROM -> TO, optimizing special cases. Returns TRUE
1036 : if the solution of TO changed. */
1037 :
1038 : static bool
1039 332839853 : solve_add_graph_edge (constraint_graph_t graph, unsigned int to,
1040 : unsigned int from)
1041 : {
1042 : /* Adding edges from the special vars is pointless.
1043 : They don't have sets that can change. */
1044 332839853 : if (get_varinfo (from)->is_special_var)
1045 63766327 : return bitmap_ior_into (get_varinfo (to)->solution,
1046 127532654 : get_varinfo (from)->solution);
1047 : /* Merging the solution from ESCAPED needlessly increases
1048 : the set. Use ESCAPED as representative instead. */
1049 269073526 : else if (from == find (escaped_id))
1050 30965548 : return bitmap_set_bit (get_varinfo (to)->solution, escaped_id);
1051 238107978 : else if (get_varinfo (from)->may_have_pointers
1052 238107978 : && add_graph_edge (graph, to, from))
1053 86148886 : return bitmap_ior_into (get_varinfo (to)->solution,
1054 86148886 : get_varinfo (from)->solution);
1055 : return false;
1056 : }
1057 :
1058 : /* Process a constraint C that represents x = *(y + off), using DELTA as the
1059 : starting solution for y. */
1060 :
1061 : static void
1062 70652694 : do_sd_constraint (constraint_graph_t graph, constraint_t c,
1063 : bitmap delta, bitmap *expanded_delta)
1064 : {
1065 70652694 : unsigned int lhs = c->lhs.var;
1066 70652694 : bool flag = false;
1067 70652694 : bitmap sol = get_varinfo (lhs)->solution;
1068 70652694 : unsigned int j;
1069 70652694 : bitmap_iterator bi;
1070 70652694 : HOST_WIDE_INT roffset = c->rhs.offset;
1071 :
1072 : /* Our IL does not allow this. */
1073 70652694 : gcc_checking_assert (c->lhs.offset == 0);
1074 :
1075 : /* If the solution of Y contains anything it is good enough to transfer
1076 : this to the LHS. */
1077 70652694 : if (bitmap_bit_p (delta, anything_id))
1078 : {
1079 562970 : flag |= bitmap_set_bit (sol, anything_id);
1080 562970 : goto done;
1081 : }
1082 :
1083 : /* If we do not know at with offset the rhs is dereferenced compute
1084 : the reachability set of DELTA, conservatively assuming it is
1085 : dereferenced at all valid offsets. */
1086 70089724 : if (roffset == UNKNOWN_OFFSET)
1087 : {
1088 51592767 : delta = solution_set_expand (delta, expanded_delta);
1089 : /* No further offset processing is necessary. */
1090 51592767 : roffset = 0;
1091 : }
1092 :
1093 : /* For each variable j in delta (Sol(y)), add
1094 : an edge in the graph from j to x, and union Sol(j) into Sol(x). */
1095 278817602 : EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1096 : {
1097 208727878 : varinfo_t v = get_varinfo (j);
1098 208727878 : HOST_WIDE_INT fieldoffset = v->offset + roffset;
1099 208727878 : unsigned HOST_WIDE_INT size = v->size;
1100 208727878 : unsigned int t;
1101 :
1102 208727878 : if (v->is_full_var)
1103 : ;
1104 111856823 : else if (roffset != 0)
1105 : {
1106 3873863 : if (fieldoffset < 0)
1107 32069 : v = get_varinfo (v->head);
1108 : else
1109 3841794 : v = first_or_preceding_vi_for_offset (v, fieldoffset);
1110 : }
1111 :
1112 : /* We have to include all fields that overlap the current field
1113 : shifted by roffset. */
1114 209464557 : do
1115 : {
1116 209464557 : t = find (v->id);
1117 :
1118 209464557 : flag |= solve_add_graph_edge (graph, lhs, t);
1119 :
1120 209464557 : if (v->is_full_var
1121 112593307 : || v->next == 0)
1122 : break;
1123 :
1124 91957988 : v = vi_next (v);
1125 : }
1126 91957988 : while (v->offset < fieldoffset + size);
1127 : }
1128 :
1129 70089724 : done:
1130 : /* If the LHS solution changed, mark the var as changed. */
1131 70652694 : if (flag)
1132 29748972 : bitmap_set_bit (changed, lhs);
1133 70652694 : }
1134 :
1135 : /* Process a constraint C that represents *(x + off) = y using DELTA
1136 : as the starting solution for x. */
1137 :
1138 : static void
1139 56340183 : do_ds_constraint (constraint_t c, bitmap delta, bitmap *expanded_delta)
1140 : {
1141 56340183 : unsigned int rhs = c->rhs.var;
1142 56340183 : bitmap sol = get_varinfo (rhs)->solution;
1143 56340183 : unsigned int j;
1144 56340183 : bitmap_iterator bi;
1145 56340183 : HOST_WIDE_INT loff = c->lhs.offset;
1146 56340183 : bool escaped_p = false;
1147 :
1148 : /* Our IL does not allow this. */
1149 56340183 : gcc_checking_assert (c->rhs.offset == 0);
1150 :
1151 : /* If the solution of y contains ANYTHING simply use the ANYTHING
1152 : solution. This avoids needlessly increasing the points-to sets. */
1153 56340183 : if (bitmap_bit_p (sol, anything_id))
1154 394748 : sol = get_varinfo (find (anything_id))->solution;
1155 :
1156 : /* If the solution for x contains ANYTHING we have to merge the
1157 : solution of y into all pointer variables which we do via
1158 : STOREDANYTHING. */
1159 56340183 : if (bitmap_bit_p (delta, anything_id))
1160 : {
1161 444922 : unsigned t = find (storedanything_id);
1162 444922 : if (solve_add_graph_edge (graph, t, rhs))
1163 35677 : bitmap_set_bit (changed, t);
1164 444922 : return;
1165 : }
1166 :
1167 : /* If we do not know at with offset the rhs is dereferenced compute
1168 : the reachability set of DELTA, conservatively assuming it is
1169 : dereferenced at all valid offsets. */
1170 55895261 : if (loff == UNKNOWN_OFFSET)
1171 : {
1172 1704437 : delta = solution_set_expand (delta, expanded_delta);
1173 1704437 : loff = 0;
1174 : }
1175 :
1176 : /* For each member j of delta (Sol(x)), add an edge from y to j and
1177 : union Sol(y) into Sol(j) */
1178 216688222 : EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1179 : {
1180 160792961 : varinfo_t v = get_varinfo (j);
1181 160792961 : unsigned int t;
1182 160792961 : HOST_WIDE_INT fieldoffset = v->offset + loff;
1183 160792961 : unsigned HOST_WIDE_INT size = v->size;
1184 :
1185 160792961 : if (v->is_full_var)
1186 : ;
1187 80951356 : else if (loff != 0)
1188 : {
1189 5256127 : if (fieldoffset < 0)
1190 6308 : v = get_varinfo (v->head);
1191 : else
1192 5249819 : v = first_or_preceding_vi_for_offset (v, fieldoffset);
1193 : }
1194 :
1195 : /* We have to include all fields that overlap the current field
1196 : shifted by loff. */
1197 162696790 : do
1198 : {
1199 162696790 : if (v->may_have_pointers)
1200 : {
1201 : /* If v is a global variable then this is an escape point. */
1202 151210250 : if (v->is_global_var
1203 116140997 : && !escaped_p)
1204 : {
1205 44506001 : t = find (escaped_id);
1206 44506001 : if (add_graph_edge (graph, t, rhs)
1207 61000886 : && bitmap_ior_into (get_varinfo (t)->solution, sol))
1208 1334575 : bitmap_set_bit (changed, t);
1209 : /* Enough to let rhs escape once. */
1210 : escaped_p = true;
1211 : }
1212 :
1213 151210250 : if (v->is_special_var)
1214 : break;
1215 :
1216 122930374 : t = find (v->id);
1217 :
1218 122930374 : if (solve_add_graph_edge (graph, t, rhs))
1219 12720194 : bitmap_set_bit (changed, t);
1220 : }
1221 :
1222 134416914 : if (v->is_full_var
1223 82855040 : || v->next == 0)
1224 : break;
1225 :
1226 67364681 : v = vi_next (v);
1227 : }
1228 67364681 : while (v->offset < fieldoffset + size);
1229 : }
1230 : }
1231 :
1232 : /* Handle a non-simple (simple meaning requires no iteration),
1233 : constraint (IE *x = &y, x = *y, *x = y, and x = y with offsets involved). */
1234 :
1235 : static void
1236 213554453 : do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta,
1237 : bitmap *expanded_delta)
1238 : {
1239 213554453 : if (c->lhs.type == DEREF)
1240 : {
1241 56340183 : if (c->rhs.type == ADDRESSOF)
1242 : {
1243 0 : gcc_unreachable ();
1244 : }
1245 : else
1246 : {
1247 : /* *x = y */
1248 56340183 : do_ds_constraint (c, delta, expanded_delta);
1249 : }
1250 : }
1251 157214270 : else if (c->rhs.type == DEREF)
1252 : {
1253 : /* x = *y */
1254 70652749 : if (!(get_varinfo (c->lhs.var)->is_special_var))
1255 70652694 : do_sd_constraint (graph, c, delta, expanded_delta);
1256 : }
1257 : else
1258 : {
1259 86561521 : bitmap tmp;
1260 86561521 : bool flag = false;
1261 :
1262 86561521 : gcc_checking_assert (c->rhs.type == SCALAR && c->lhs.type == SCALAR
1263 : && c->rhs.offset != 0 && c->lhs.offset == 0);
1264 86561521 : tmp = get_varinfo (c->lhs.var)->solution;
1265 :
1266 86561521 : flag = set_union_with_increment (tmp, delta, c->rhs.offset,
1267 : expanded_delta);
1268 :
1269 86561521 : if (flag)
1270 21962127 : bitmap_set_bit (changed, c->lhs.var);
1271 : }
1272 213554453 : }
1273 :
1274 : /* Initialize and return a new SCC info structure. */
1275 :
1276 9248978 : scc_info::scc_info (size_t size) :
1277 9248978 : visited (size), deleted (size), current_index (0), scc_stack (1)
1278 : {
1279 9248978 : bitmap_clear (visited);
1280 9248978 : bitmap_clear (deleted);
1281 9248978 : node_mapping = XNEWVEC (unsigned int, size);
1282 9248978 : dfs = XCNEWVEC (unsigned int, size);
1283 :
1284 951491454 : for (size_t i = 0; i < size; i++)
1285 942242476 : node_mapping[i] = i;
1286 9248978 : }
1287 :
1288 : /* Free an SCC info structure pointed to by SI. */
1289 :
1290 9248978 : scc_info::~scc_info ()
1291 : {
1292 9248978 : free (node_mapping);
1293 9248978 : free (dfs);
1294 9248978 : }
1295 :
1296 :
1297 : /* Find indirect cycles in GRAPH that occur, using strongly connected
1298 : components, and note them in the indirect cycles map.
1299 :
1300 : This technique comes from Ben Hardekopf and Calvin Lin,
1301 : "It Pays to be Lazy: Fast and Accurate Pointer Analysis for Millions of
1302 : Lines of Code", submitted to PLDI 2007. */
1303 :
1304 : static void
1305 4624489 : find_indirect_cycles (constraint_graph_t graph)
1306 : {
1307 4624489 : unsigned int i;
1308 4624489 : unsigned int size = graph->size;
1309 4624489 : scc_info si (size);
1310 :
1311 946866965 : for (i = 0; i < MIN (LAST_REF_NODE, size); i++)
1312 466496749 : if (!bitmap_bit_p (si.visited, i) && find (i) == i)
1313 240362783 : scc_visit (graph, &si, i);
1314 4624489 : }
1315 :
1316 : /* Visit the graph in topological order starting at node N, and store the
1317 : order in TOPO_ORDER using VISITED to indicate visited nodes. */
1318 :
1319 : static void
1320 466914259 : topo_visit (constraint_graph_t graph, vec<unsigned> &topo_order,
1321 : sbitmap visited, unsigned int n)
1322 : {
1323 466914259 : bitmap_iterator bi;
1324 466914259 : unsigned int j;
1325 :
1326 466914259 : bitmap_set_bit (visited, n);
1327 :
1328 466914259 : if (graph->succs[n])
1329 1133108648 : EXECUTE_IF_SET_IN_BITMAP (graph->succs[n], 0, j, bi)
1330 : {
1331 915000045 : unsigned k = find (j);
1332 915000045 : if (!bitmap_bit_p (visited, k))
1333 355045990 : topo_visit (graph, topo_order, visited, k);
1334 : }
1335 :
1336 : /* Also consider copy with offset complex constraints as implicit edges. */
1337 917792843 : for (auto c : graph->complex[n])
1338 : {
1339 : /* Constraints are ordered so that SCALAR = SCALAR appear first. */
1340 261292008 : if (c->lhs.type != SCALAR || c->rhs.type != SCALAR)
1341 : break;
1342 146403506 : gcc_checking_assert (c->rhs.var == n);
1343 146403506 : unsigned k = find (c->lhs.var);
1344 146403506 : if (!bitmap_bit_p (visited, k))
1345 38971118 : topo_visit (graph, topo_order, visited, k);
1346 : }
1347 :
1348 466914259 : topo_order.quick_push (n);
1349 466914259 : }
1350 :
1351 : /* Compute a topological ordering for GRAPH, and return the result. */
1352 :
1353 : static auto_vec<unsigned>
1354 8234835 : compute_topo_order (constraint_graph_t graph)
1355 : {
1356 8234835 : unsigned int i;
1357 8234835 : unsigned int size = graph->size;
1358 :
1359 8234835 : auto_sbitmap visited (size);
1360 8234835 : bitmap_clear (visited);
1361 :
1362 : /* For the heuristic in add_graph_edge to work optimally make sure to
1363 : first visit the connected component of the graph containing
1364 : ESCAPED. Do this by extracting the connected component
1365 : with ESCAPED and append that to all other components as solve_graph
1366 : pops from the order. */
1367 8234835 : auto_vec<unsigned> tail (size);
1368 8234835 : topo_visit (graph, tail, visited, find (escaped_id));
1369 :
1370 8234835 : auto_vec<unsigned> topo_order (size);
1371 :
1372 595260422 : for (i = 0; i != size; ++i)
1373 578790752 : if (!bitmap_bit_p (visited, i) && find (i) == i)
1374 64662316 : topo_visit (graph, topo_order, visited, i);
1375 :
1376 8234835 : topo_order.splice (tail);
1377 8234835 : return topo_order;
1378 8234835 : }
1379 :
1380 : /* Structure used to for hash value numbering of pointer equivalence
1381 : classes. */
1382 :
1383 : typedef struct equiv_class_label
1384 : {
1385 : hashval_t hashcode;
1386 : unsigned int equivalence_class;
1387 : bitmap labels;
1388 : } *equiv_class_label_t;
1389 : typedef const struct equiv_class_label *const_equiv_class_label_t;
1390 :
1391 : /* Equiv_class_label hashtable helpers. */
1392 :
1393 : struct equiv_class_hasher : nofree_ptr_hash <equiv_class_label>
1394 : {
1395 : static inline hashval_t hash (const equiv_class_label *);
1396 : static inline bool equal (const equiv_class_label *,
1397 : const equiv_class_label *);
1398 : };
1399 :
1400 : /* A hashtable for mapping a bitmap of labels->pointer equivalence
1401 : classes. */
1402 : static hash_table<equiv_class_hasher> *pointer_equiv_class_table;
1403 :
1404 : /* A hashtable for mapping a bitmap of labels->location equivalence
1405 : classes. */
1406 : static hash_table<equiv_class_hasher> *location_equiv_class_table;
1407 :
1408 : /* Hash function for a equiv_class_label_t. */
1409 :
1410 : inline hashval_t
1411 196851321 : equiv_class_hasher::hash (const equiv_class_label *ecl)
1412 : {
1413 196851321 : return ecl->hashcode;
1414 : }
1415 :
1416 : /* Equality function for two equiv_class_label_t's. */
1417 :
1418 : inline bool
1419 254548341 : equiv_class_hasher::equal (const equiv_class_label *eql1,
1420 : const equiv_class_label *eql2)
1421 : {
1422 254548341 : return (eql1->hashcode == eql2->hashcode
1423 254548341 : && bitmap_equal_p (eql1->labels, eql2->labels));
1424 : }
1425 :
1426 : struct obstack equiv_class_obstack;
1427 :
1428 : /* Lookup a equivalence class in TABLE by the bitmap of LABELS with
1429 : hash HAS it contains. Sets *REF_LABELS to the bitmap LABELS
1430 : is equivalent to. */
1431 :
1432 : static equiv_class_label *
1433 201514761 : equiv_class_lookup_or_add (hash_table<equiv_class_hasher> *table,
1434 : bitmap labels)
1435 : {
1436 201514761 : equiv_class_label **slot;
1437 201514761 : equiv_class_label ecl;
1438 :
1439 201514761 : ecl.labels = labels;
1440 201514761 : ecl.hashcode = bitmap_hash (labels);
1441 201514761 : slot = table->find_slot (&ecl, INSERT);
1442 201514761 : if (!*slot)
1443 : {
1444 168779941 : *slot = XOBNEW (&equiv_class_obstack, struct equiv_class_label);
1445 168779941 : (*slot)->labels = labels;
1446 168779941 : (*slot)->hashcode = ecl.hashcode;
1447 168779941 : (*slot)->equivalence_class = 0;
1448 : }
1449 :
1450 201514761 : return *slot;
1451 : }
1452 :
1453 :
1454 : /* Perform offline variable substitution.
1455 :
1456 : This is a worst case quadratic time way of identifying variables
1457 : that must have equivalent points-to sets, including those caused by
1458 : static cycles, and single entry subgraphs, in the constraint graph.
1459 :
1460 : The technique is described in "Exploiting Pointer and Location
1461 : Equivalence to Optimize Pointer Analysis. In the 14th International
1462 : Static Analysis Symposium (SAS), August 2007." It is known as the
1463 : "HU" algorithm, and is equivalent to value numbering the collapsed
1464 : constraint graph including evaluating unions.
1465 :
1466 : The general method of finding equivalence classes is as follows:
1467 : Add fake nodes (REF nodes) and edges for *a = b and a = *b constraints.
1468 : Initialize all non-REF nodes to be direct nodes.
1469 : For each constraint a = a U {b}, we set pts(a) = pts(a) u {fresh
1470 : variable}
1471 : For each constraint containing the dereference, we also do the same
1472 : thing.
1473 :
1474 : We then compute SCC's in the graph and unify nodes in the same SCC,
1475 : including pts sets.
1476 :
1477 : For each non-collapsed node x:
1478 : Visit all unvisited explicit incoming edges.
1479 : Ignoring all non-pointers, set pts(x) = Union of pts(a) for y
1480 : where y->x.
1481 : Lookup the equivalence class for pts(x).
1482 : If we found one, equivalence_class(x) = found class.
1483 : Otherwise, equivalence_class(x) = new class, and new_class is
1484 : added to the lookup table.
1485 :
1486 : All direct nodes with the same equivalence class can be replaced
1487 : with a single representative node.
1488 : All unlabeled nodes (label == 0) are not pointers and all edges
1489 : involving them can be eliminated.
1490 : We perform these optimizations during rewrite_constraints
1491 :
1492 : In addition to pointer equivalence class finding, we also perform
1493 : location equivalence class finding. This is the set of variables
1494 : that always appear together in points-to sets. We use this to
1495 : compress the size of the points-to sets. */
1496 :
1497 : /* Current maximum pointer equivalence class id. */
1498 : static int pointer_equiv_class;
1499 :
1500 : /* Current maximum location equivalence class id. */
1501 : static int location_equiv_class;
1502 :
1503 : /* Recursive routine to find strongly connected components in GRAPH,
1504 : and label it's nodes with DFS numbers. */
1505 :
1506 : static void
1507 275260860 : condense_visit (constraint_graph_t graph, class scc_info *si, unsigned int n)
1508 : {
1509 275260860 : unsigned int i;
1510 275260860 : bitmap_iterator bi;
1511 275260860 : unsigned int my_dfs;
1512 :
1513 275260860 : gcc_checking_assert (si->node_mapping[n] == n);
1514 275260860 : bitmap_set_bit (si->visited, n);
1515 275260860 : si->dfs[n] = si->current_index ++;
1516 275260860 : my_dfs = si->dfs[n];
1517 :
1518 : /* Visit all the successors. */
1519 505843631 : EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
1520 : {
1521 230582771 : unsigned int w = si->node_mapping[i];
1522 :
1523 230582771 : if (bitmap_bit_p (si->deleted, w))
1524 146448565 : continue;
1525 :
1526 84134206 : if (!bitmap_bit_p (si->visited, w))
1527 82649972 : condense_visit (graph, si, w);
1528 :
1529 84134206 : unsigned int t = si->node_mapping[w];
1530 84134206 : gcc_checking_assert (si->node_mapping[n] == n);
1531 84134206 : if (si->dfs[t] < si->dfs[n])
1532 2636235 : si->dfs[n] = si->dfs[t];
1533 : }
1534 :
1535 : /* Visit all the implicit predecessors. */
1536 335271396 : EXECUTE_IF_IN_NONNULL_BITMAP (graph->implicit_preds[n], 0, i, bi)
1537 : {
1538 60010536 : unsigned int w = si->node_mapping[i];
1539 :
1540 60010536 : if (bitmap_bit_p (si->deleted, w))
1541 19826667 : continue;
1542 :
1543 40183869 : if (!bitmap_bit_p (si->visited, w))
1544 35200617 : condense_visit (graph, si, w);
1545 :
1546 40183869 : unsigned int t = si->node_mapping[w];
1547 40183869 : gcc_assert (si->node_mapping[n] == n);
1548 40183869 : if (si->dfs[t] < si->dfs[n])
1549 8473355 : si->dfs[n] = si->dfs[t];
1550 : }
1551 :
1552 : /* See if any components have been identified. */
1553 275260860 : if (si->dfs[n] == my_dfs)
1554 : {
1555 264322719 : if (si->scc_stack.length () != 0
1556 264322719 : && si->dfs[si->scc_stack.last ()] >= my_dfs)
1557 : {
1558 : /* Find the first node of the SCC and do non-bitmap work. */
1559 10938141 : bool direct_p = true;
1560 10938141 : unsigned first = si->scc_stack.length ();
1561 10938141 : do
1562 : {
1563 10938141 : --first;
1564 10938141 : unsigned int w = si->scc_stack[first];
1565 10938141 : si->node_mapping[w] = n;
1566 10938141 : if (!bitmap_bit_p (graph->direct_nodes, w))
1567 8831080 : direct_p = false;
1568 : }
1569 : while (first > 0
1570 12314835 : && si->dfs[si->scc_stack[first - 1]] >= my_dfs);
1571 1376694 : if (!direct_p)
1572 874398 : bitmap_clear_bit (graph->direct_nodes, n);
1573 :
1574 : /* Want to reduce to node n, push that first. */
1575 1376694 : si->scc_stack.reserve (1);
1576 1376694 : si->scc_stack.quick_push (si->scc_stack[first]);
1577 1376694 : si->scc_stack[first] = n;
1578 :
1579 1376694 : unsigned scc_size = si->scc_stack.length () - first;
1580 1376694 : unsigned split = scc_size / 2;
1581 1376694 : unsigned carry = scc_size - split * 2;
1582 4829191 : while (split > 0)
1583 : {
1584 14390638 : for (unsigned i = 0; i < split; ++i)
1585 : {
1586 10938141 : unsigned a = si->scc_stack[first + i];
1587 10938141 : unsigned b = si->scc_stack[first + split + carry + i];
1588 :
1589 : /* Unify our nodes. */
1590 10938141 : if (graph->preds[b])
1591 : {
1592 4799466 : if (!graph->preds[a])
1593 1003602 : std::swap (graph->preds[a], graph->preds[b]);
1594 : else
1595 3795864 : bitmap_ior_into_and_free (graph->preds[a],
1596 : &graph->preds[b]);
1597 : }
1598 10938141 : if (graph->implicit_preds[b])
1599 : {
1600 8729968 : if (!graph->implicit_preds[a])
1601 880040 : std::swap (graph->implicit_preds[a],
1602 : graph->implicit_preds[b]);
1603 : else
1604 7849928 : bitmap_ior_into_and_free (graph->implicit_preds[a],
1605 : &graph->implicit_preds[b]);
1606 : }
1607 10938141 : if (graph->points_to[b])
1608 : {
1609 530329 : if (!graph->points_to[a])
1610 234929 : std::swap (graph->points_to[a], graph->points_to[b]);
1611 : else
1612 295400 : bitmap_ior_into_and_free (graph->points_to[a],
1613 : &graph->points_to[b]);
1614 : }
1615 : }
1616 3452497 : unsigned remain = split + carry;
1617 3452497 : split = remain / 2;
1618 3452497 : carry = remain - split * 2;
1619 : }
1620 : /* Actually pop the SCC. */
1621 1376694 : si->scc_stack.truncate (first);
1622 : }
1623 264322719 : bitmap_set_bit (si->deleted, n);
1624 : }
1625 : else
1626 10938141 : si->scc_stack.safe_push (n);
1627 275260860 : }
1628 :
1629 : /* Label pointer equivalences.
1630 :
1631 : This performs a value numbering of the constraint graph to
1632 : discover which variables will always have the same points-to sets
1633 : under the current set of constraints.
1634 :
1635 : The way it value numbers is to store the set of points-to bits
1636 : generated by the constraints and graph edges. This is just used as a
1637 : hash and equality comparison. The *actual set of points-to bits* is
1638 : completely irrelevant, in that we don't care about being able to
1639 : extract them later.
1640 :
1641 : The equality values (currently bitmaps) just have to satisfy a few
1642 : constraints, the main ones being:
1643 : 1. The combining operation must be order independent.
1644 : 2. The end result of a given set of operations must be unique iff the
1645 : combination of input values is unique
1646 : 3. Hashable. */
1647 :
1648 : static void
1649 240533084 : label_visit (constraint_graph_t graph, class scc_info *si, unsigned int n)
1650 : {
1651 240533084 : unsigned int i, first_pred;
1652 240533084 : bitmap_iterator bi;
1653 :
1654 240533084 : bitmap_set_bit (si->visited, n);
1655 :
1656 : /* Label and union our incoming edges's points to sets. */
1657 240533084 : first_pred = -1U;
1658 465735680 : EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
1659 : {
1660 225202596 : unsigned int w = si->node_mapping[i];
1661 225202596 : if (!bitmap_bit_p (si->visited, w))
1662 77920509 : label_visit (graph, si, w);
1663 :
1664 : /* Skip unused edges. */
1665 225202596 : if (w == n || graph->pointer_label[w] == 0)
1666 5252642 : continue;
1667 :
1668 219949954 : if (graph->points_to[w])
1669 : {
1670 219949954 : if (!graph->points_to[n])
1671 : {
1672 153564800 : if (first_pred == -1U)
1673 : first_pred = w;
1674 : else
1675 : {
1676 42628179 : graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
1677 42628179 : bitmap_ior (graph->points_to[n],
1678 42628179 : graph->points_to[first_pred],
1679 42628179 : graph->points_to[w]);
1680 : }
1681 : }
1682 : else
1683 66385154 : bitmap_ior_into (graph->points_to[n], graph->points_to[w]);
1684 : }
1685 : }
1686 :
1687 : /* Indirect nodes get fresh variables and a new pointer equiv class. */
1688 240533084 : if (!bitmap_bit_p (graph->direct_nodes, n))
1689 : {
1690 116632725 : if (!graph->points_to[n])
1691 : {
1692 67326561 : graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
1693 67326561 : if (first_pred != -1U)
1694 27253200 : bitmap_copy (graph->points_to[n], graph->points_to[first_pred]);
1695 : }
1696 233265450 : bitmap_set_bit (graph->points_to[n], FIRST_REF_NODE + n);
1697 116632725 : graph->pointer_label[n] = pointer_equiv_class++;
1698 116632725 : equiv_class_label_t ecl;
1699 233265450 : ecl = equiv_class_lookup_or_add (pointer_equiv_class_table,
1700 116632725 : graph->points_to[n]);
1701 116632725 : ecl->equivalence_class = graph->pointer_label[n];
1702 178176186 : return;
1703 : }
1704 :
1705 : /* If there was only a single non-empty predecessor the pointer equiv
1706 : class is the same. */
1707 123900359 : if (!graph->points_to[n])
1708 : {
1709 61543461 : if (first_pred != -1U)
1710 : {
1711 41055242 : graph->pointer_label[n] = graph->pointer_label[first_pred];
1712 41055242 : graph->points_to[n] = graph->points_to[first_pred];
1713 : }
1714 : return;
1715 : }
1716 :
1717 62356898 : if (!bitmap_empty_p (graph->points_to[n]))
1718 : {
1719 62356898 : equiv_class_label_t ecl;
1720 62356898 : ecl = equiv_class_lookup_or_add (pointer_equiv_class_table,
1721 : graph->points_to[n]);
1722 62356898 : if (ecl->equivalence_class == 0)
1723 30081572 : ecl->equivalence_class = pointer_equiv_class++;
1724 : else
1725 : {
1726 32275326 : BITMAP_FREE (graph->points_to[n]);
1727 32275326 : graph->points_to[n] = ecl->labels;
1728 : }
1729 62356898 : graph->pointer_label[n] = ecl->equivalence_class;
1730 : }
1731 : }
1732 :
1733 : /* Print the pred graph in dot format. */
1734 :
1735 : static void
1736 3 : dump_pred_graph (class scc_info *si, FILE *file)
1737 : {
1738 3 : unsigned int i;
1739 :
1740 : /* Only print the graph if it has already been initialized: */
1741 3 : if (!graph)
1742 : return;
1743 :
1744 : /* Prints the header of the dot file: */
1745 3 : fprintf (file, "strict digraph {\n");
1746 3 : fprintf (file, " node [\n shape = box\n ]\n");
1747 3 : fprintf (file, " edge [\n fontsize = \"12\"\n ]\n");
1748 3 : fprintf (file, "\n // List of nodes and complex constraints in "
1749 : "the constraint graph:\n");
1750 :
1751 : /* The next lines print the nodes in the graph together with the
1752 : complex constraints attached to them. */
1753 83 : for (i = 1; i < graph->size; i++)
1754 : {
1755 154 : if (i == FIRST_REF_NODE)
1756 3 : continue;
1757 74 : if (si->node_mapping[i] != i)
1758 0 : continue;
1759 74 : if (i < FIRST_REF_NODE)
1760 37 : fprintf (file, "\"%s\"", get_varinfo (i)->name);
1761 : else
1762 37 : fprintf (file, "\"*%s\"", get_varinfo (i - FIRST_REF_NODE)->name);
1763 74 : if (graph->points_to[i]
1764 74 : && !bitmap_empty_p (graph->points_to[i]))
1765 : {
1766 11 : if (i < FIRST_REF_NODE)
1767 11 : fprintf (file, "[label=\"%s = {", get_varinfo (i)->name);
1768 : else
1769 0 : fprintf (file, "[label=\"*%s = {",
1770 0 : get_varinfo (i - FIRST_REF_NODE)->name);
1771 11 : unsigned j;
1772 11 : bitmap_iterator bi;
1773 25 : EXECUTE_IF_SET_IN_BITMAP (graph->points_to[i], 0, j, bi)
1774 14 : fprintf (file, " %d", j);
1775 11 : fprintf (file, " }\"]");
1776 : }
1777 74 : fprintf (file, ";\n");
1778 : }
1779 :
1780 : /* Go over the edges. */
1781 3 : fprintf (file, "\n // Edges in the constraint graph:\n");
1782 83 : for (i = 1; i < graph->size; i++)
1783 : {
1784 77 : unsigned j;
1785 77 : bitmap_iterator bi;
1786 77 : if (si->node_mapping[i] != i)
1787 0 : continue;
1788 92 : EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[i], 0, j, bi)
1789 : {
1790 15 : unsigned from = si->node_mapping[j];
1791 15 : if (from < FIRST_REF_NODE)
1792 7 : fprintf (file, "\"%s\"", get_varinfo (from)->name);
1793 : else
1794 8 : fprintf (file, "\"*%s\"",
1795 8 : get_varinfo (from - FIRST_REF_NODE)->name);
1796 15 : fprintf (file, " -> ");
1797 15 : if (i < FIRST_REF_NODE)
1798 11 : fprintf (file, "\"%s\"", get_varinfo (i)->name);
1799 : else
1800 8 : fprintf (file, "\"*%s\"", get_varinfo (i - FIRST_REF_NODE)->name);
1801 15 : fprintf (file, ";\n");
1802 : }
1803 : }
1804 :
1805 : /* Prints the tail of the dot file. */
1806 3 : fprintf (file, "}\n");
1807 : }
1808 :
1809 : /* Perform offline variable substitution, discovering equivalence
1810 : classes, and eliminating non-pointer variables. */
1811 :
1812 : static class scc_info *
1813 4624489 : perform_var_substitution (constraint_graph_t graph)
1814 : {
1815 4624489 : unsigned int i;
1816 4624489 : unsigned int size = graph->size;
1817 4624489 : scc_info *si = new scc_info (size);
1818 :
1819 4624489 : bitmap_obstack_initialize (&iteration_obstack);
1820 4624489 : gcc_obstack_init (&equiv_class_obstack);
1821 4624489 : pointer_equiv_class_table = new hash_table<equiv_class_hasher> (511);
1822 4624489 : location_equiv_class_table
1823 4624489 : = new hash_table<equiv_class_hasher> (511);
1824 4624489 : pointer_equiv_class = 1;
1825 4624489 : location_equiv_class = 1;
1826 :
1827 : /* Condense the nodes, which means to find SCC's, count incoming
1828 : predecessors, and unite nodes in SCC's. */
1829 235560619 : for (i = 1; i < FIRST_REF_NODE; i++)
1830 230936130 : if (!bitmap_bit_p (si->visited, si->node_mapping[i]))
1831 157410271 : condense_visit (graph, si, si->node_mapping[i]);
1832 :
1833 4624489 : if (dump_file && (dump_flags & TDF_GRAPH))
1834 : {
1835 3 : fprintf (dump_file, "\n\n// The constraint graph before var-substitution "
1836 : "in dot format:\n");
1837 3 : dump_pred_graph (si, dump_file);
1838 3 : fprintf (dump_file, "\n\n");
1839 : }
1840 :
1841 4624489 : bitmap_clear (si->visited);
1842 : /* Actually the label the nodes for pointer equivalences. */
1843 475745727 : for (i = 1; i < FIRST_REF_NODE; i++)
1844 230936130 : if (!bitmap_bit_p (si->visited, si->node_mapping[i]))
1845 162612575 : label_visit (graph, si, si->node_mapping[i]);
1846 :
1847 : /* Calculate location equivalence labels. */
1848 235560619 : for (i = 1; i < FIRST_REF_NODE; i++)
1849 : {
1850 230936130 : bitmap pointed_by;
1851 230936130 : bitmap_iterator bi;
1852 230936130 : unsigned int j;
1853 :
1854 230936130 : if (!graph->pointed_by[i])
1855 208410992 : continue;
1856 22525138 : pointed_by = BITMAP_ALLOC (&iteration_obstack);
1857 :
1858 : /* Translate the pointed-by mapping for pointer equivalence
1859 : labels. */
1860 101146300 : EXECUTE_IF_SET_IN_BITMAP (graph->pointed_by[i], 0, j, bi)
1861 : {
1862 78621162 : bitmap_set_bit (pointed_by,
1863 78621162 : graph->pointer_label[si->node_mapping[j]]);
1864 : }
1865 : /* The original pointed_by is now dead. */
1866 22525138 : BITMAP_FREE (graph->pointed_by[i]);
1867 :
1868 : /* Look up the location equivalence label if one exists, or make
1869 : one otherwise. */
1870 22525138 : equiv_class_label_t ecl;
1871 22525138 : ecl = equiv_class_lookup_or_add (location_equiv_class_table, pointed_by);
1872 22525138 : if (ecl->equivalence_class == 0)
1873 22065644 : ecl->equivalence_class = location_equiv_class++;
1874 : else
1875 : {
1876 459494 : if (dump_file && (dump_flags & TDF_DETAILS))
1877 55 : fprintf (dump_file, "Found location equivalence for node %s\n",
1878 55 : get_varinfo (i)->name);
1879 459494 : BITMAP_FREE (pointed_by);
1880 : }
1881 22525138 : graph->loc_label[i] = ecl->equivalence_class;
1882 :
1883 : }
1884 :
1885 4624489 : if (dump_file && (dump_flags & TDF_DETAILS))
1886 6830 : for (i = 1; i < FIRST_REF_NODE; i++)
1887 : {
1888 6529 : unsigned j = si->node_mapping[i];
1889 6529 : if (j != i)
1890 : {
1891 21 : fprintf (dump_file, "%s node id %d ",
1892 21 : bitmap_bit_p (graph->direct_nodes, i)
1893 : ? "Direct" : "Indirect", i);
1894 21 : if (i < FIRST_REF_NODE)
1895 21 : fprintf (dump_file, "\"%s\"", get_varinfo (i)->name);
1896 : else
1897 0 : fprintf (dump_file, "\"*%s\"",
1898 0 : get_varinfo (i - FIRST_REF_NODE)->name);
1899 21 : fprintf (dump_file, " mapped to SCC leader node id %d ", j);
1900 21 : if (j < FIRST_REF_NODE)
1901 21 : fprintf (dump_file, "\"%s\"\n", get_varinfo (j)->name);
1902 : else
1903 0 : fprintf (dump_file, "\"*%s\"\n",
1904 0 : get_varinfo (j - FIRST_REF_NODE)->name);
1905 : }
1906 : else
1907 : {
1908 10023 : fprintf (dump_file,
1909 : "Equivalence classes for %s node id %d ",
1910 6508 : bitmap_bit_p (graph->direct_nodes, i)
1911 : ? "direct" : "indirect", i);
1912 6508 : if (i < FIRST_REF_NODE)
1913 6508 : fprintf (dump_file, "\"%s\"", get_varinfo (i)->name);
1914 : else
1915 0 : fprintf (dump_file, "\"*%s\"",
1916 0 : get_varinfo (i - FIRST_REF_NODE)->name);
1917 6508 : fprintf (dump_file,
1918 : ": pointer %d, location %d\n",
1919 6508 : graph->pointer_label[i], graph->loc_label[i]);
1920 : }
1921 : }
1922 :
1923 : /* Quickly eliminate our non-pointer variables. */
1924 :
1925 235560619 : for (i = 1; i < FIRST_REF_NODE; i++)
1926 : {
1927 230936130 : unsigned int node = si->node_mapping[i];
1928 :
1929 230936130 : if (graph->pointer_label[node] == 0)
1930 : {
1931 20489703 : if (dump_file && (dump_flags & TDF_DETAILS))
1932 926 : fprintf (dump_file,
1933 : "%s is a non-pointer variable, eliminating edges.\n",
1934 926 : get_varinfo (node)->name);
1935 20489703 : stats.nonpointer_vars++;
1936 20489703 : clear_edges_for_node (graph, node);
1937 : }
1938 : }
1939 :
1940 4624489 : return si;
1941 : }
1942 :
1943 : /* Free information that was only necessary for variable
1944 : substitution. */
1945 :
1946 : static void
1947 4624489 : free_var_substitution_info (class scc_info *si)
1948 : {
1949 4624489 : delete si;
1950 4624489 : free (graph->pointer_label);
1951 4624489 : free (graph->loc_label);
1952 4624489 : free (graph->pointed_by);
1953 4624489 : free (graph->points_to);
1954 4624489 : free (graph->eq_rep);
1955 4624489 : sbitmap_free (graph->direct_nodes);
1956 4624489 : delete pointer_equiv_class_table;
1957 4624489 : pointer_equiv_class_table = NULL;
1958 4624489 : delete location_equiv_class_table;
1959 4624489 : location_equiv_class_table = NULL;
1960 4624489 : obstack_free (&equiv_class_obstack, NULL);
1961 4624489 : bitmap_obstack_release (&iteration_obstack);
1962 4624489 : }
1963 :
1964 : /* Return an existing node that is equivalent to NODE, which has
1965 : equivalence class LABEL, if one exists. Return NODE otherwise. */
1966 :
1967 : static unsigned int
1968 906464058 : find_equivalent_node (constraint_graph_t graph,
1969 : unsigned int node, unsigned int label)
1970 : {
1971 : /* If the address version of this variable is unused, we can
1972 : substitute it for anything else with the same label.
1973 : Otherwise, we know the pointers are equivalent, but not the
1974 : locations, and we can unite them later. */
1975 :
1976 906464058 : if (!bitmap_bit_p (graph->address_taken, node))
1977 : {
1978 705325014 : gcc_checking_assert (label < graph->size);
1979 :
1980 705325014 : if (graph->eq_rep[label] != -1)
1981 : {
1982 : /* Unify the two variables since we know they are equivalent. */
1983 596911156 : if (unite (graph->eq_rep[label], node))
1984 : {
1985 43094901 : unify_nodes (graph, graph->eq_rep[label], node, false);
1986 43094901 : return graph->eq_rep[label];
1987 : }
1988 : }
1989 : else
1990 : {
1991 108413858 : graph->eq_rep[label] = node;
1992 108413858 : graph->pe_rep[label] = node;
1993 : }
1994 : }
1995 : else
1996 : {
1997 201139044 : gcc_checking_assert (label < graph->size);
1998 201139044 : graph->pe[node] = label;
1999 201139044 : if (graph->pe_rep[label] == -1)
2000 22434718 : graph->pe_rep[label] = node;
2001 : }
2002 :
2003 : return node;
2004 : }
2005 :
2006 : /* Unite pointer equivalent but not location equivalent nodes in
2007 : GRAPH. This may only be performed once variable substitution is
2008 : finished. */
2009 :
2010 : static void
2011 4624489 : unite_pointer_equivalences (constraint_graph_t graph)
2012 : {
2013 4624489 : unsigned int i;
2014 :
2015 : /* Go through the pointer equivalences and unite them to their
2016 : representative, if they aren't already. */
2017 235560619 : for (i = 1; i < FIRST_REF_NODE; i++)
2018 : {
2019 230936130 : unsigned int label = graph->pe[i];
2020 230936130 : if (label)
2021 : {
2022 22525138 : int label_rep = graph->pe_rep[label];
2023 :
2024 22525138 : if (label_rep == -1)
2025 0 : continue;
2026 :
2027 22525138 : label_rep = find (label_rep);
2028 22525138 : if (label_rep >= 0 && unite (label_rep, find (i)))
2029 809403 : unify_nodes (graph, label_rep, i, false);
2030 : }
2031 : }
2032 4624489 : }
2033 :
2034 : /* Move complex constraints to the GRAPH nodes they belong to. */
2035 :
2036 : static void
2037 4624489 : move_complex_constraints (constraint_graph_t graph)
2038 : {
2039 4624489 : int i;
2040 4624489 : constraint_t c;
2041 :
2042 460410906 : FOR_EACH_VEC_ELT (constraints, i, c)
2043 : {
2044 455786417 : if (c)
2045 : {
2046 453232029 : struct constraint_expr lhs = c->lhs;
2047 453232029 : struct constraint_expr rhs = c->rhs;
2048 :
2049 453232029 : if (lhs.type == DEREF)
2050 : {
2051 37462554 : insert_into_complex (graph, lhs.var, c);
2052 : }
2053 415769475 : else if (rhs.type == DEREF)
2054 : {
2055 50709803 : if (!(get_varinfo (lhs.var)->is_special_var))
2056 50709800 : insert_into_complex (graph, rhs.var, c);
2057 : }
2058 365059672 : else if (rhs.type != ADDRESSOF && lhs.var > anything_id
2059 271459978 : && (lhs.offset != 0 || rhs.offset != 0))
2060 : {
2061 62653489 : insert_into_complex (graph, rhs.var, c);
2062 : }
2063 : }
2064 : }
2065 4624489 : }
2066 :
2067 : /* Optimize and rewrite complex constraints while performing
2068 : collapsing of equivalent nodes. SI is the SCC_INFO that is the
2069 : result of perform_variable_substitution. */
2070 :
2071 : static void
2072 4624489 : rewrite_constraints (constraint_graph_t graph,
2073 : class scc_info *si)
2074 : {
2075 4624489 : int i;
2076 4624489 : constraint_t c;
2077 :
2078 4624489 : if (flag_checking)
2079 : {
2080 475742579 : for (unsigned int j = 0; j < graph->size; j++)
2081 471118150 : gcc_assert (find (j) == j);
2082 : }
2083 :
2084 460410906 : FOR_EACH_VEC_ELT (constraints, i, c)
2085 : {
2086 455786417 : struct constraint_expr lhs = c->lhs;
2087 455786417 : struct constraint_expr rhs = c->rhs;
2088 455786417 : unsigned int lhsvar = find (lhs.var);
2089 455786417 : unsigned int rhsvar = find (rhs.var);
2090 455786417 : unsigned int lhsnode, rhsnode;
2091 455786417 : unsigned int lhslabel, rhslabel;
2092 :
2093 455786417 : lhsnode = si->node_mapping[lhsvar];
2094 455786417 : rhsnode = si->node_mapping[rhsvar];
2095 455786417 : lhslabel = graph->pointer_label[lhsnode];
2096 455786417 : rhslabel = graph->pointer_label[rhsnode];
2097 :
2098 : /* See if it is really a non-pointer variable, and if so, ignore
2099 : the constraint. */
2100 455786417 : if (lhslabel == 0)
2101 : {
2102 804511 : if (dump_file && (dump_flags & TDF_DETAILS))
2103 : {
2104 :
2105 44 : fprintf (dump_file, "%s is a non-pointer variable, "
2106 : "ignoring constraint:",
2107 22 : get_varinfo (lhs.var)->name);
2108 22 : dump_constraint (dump_file, c);
2109 22 : fprintf (dump_file, "\n");
2110 : }
2111 804511 : constraints[i] = NULL;
2112 455786417 : continue;
2113 : }
2114 :
2115 454981906 : if (rhslabel == 0)
2116 : {
2117 1749877 : if (dump_file && (dump_flags & TDF_DETAILS))
2118 : {
2119 :
2120 90 : fprintf (dump_file, "%s is a non-pointer variable, "
2121 : "ignoring constraint:",
2122 45 : get_varinfo (rhs.var)->name);
2123 45 : dump_constraint (dump_file, c);
2124 45 : fprintf (dump_file, "\n");
2125 : }
2126 1749877 : constraints[i] = NULL;
2127 1749877 : continue;
2128 : }
2129 :
2130 453232029 : lhsvar = find_equivalent_node (graph, lhsvar, lhslabel);
2131 453232029 : rhsvar = find_equivalent_node (graph, rhsvar, rhslabel);
2132 453232029 : c->lhs.var = lhsvar;
2133 453232029 : c->rhs.var = rhsvar;
2134 : }
2135 4624489 : }
2136 :
2137 : /* Eliminate indirect cycles involving NODE. Return true if NODE was
2138 : part of an SCC, false otherwise. */
2139 :
2140 : static bool
2141 466894007 : eliminate_indirect_cycles (unsigned int node)
2142 : {
2143 466894007 : if (graph->indirect_cycles[node] != -1
2144 467233478 : && !bitmap_empty_p (get_varinfo (node)->solution))
2145 : {
2146 305302 : unsigned int i;
2147 305302 : auto_vec<unsigned> queue;
2148 305302 : int queuepos;
2149 305302 : unsigned int to = find (graph->indirect_cycles[node]);
2150 305302 : bitmap_iterator bi;
2151 :
2152 : /* We can't touch the solution set and call unify_nodes
2153 : at the same time, because unify_nodes is going to do
2154 : bitmap unions into it. */
2155 :
2156 1151327 : EXECUTE_IF_SET_IN_BITMAP (get_varinfo (node)->solution, 0, i, bi)
2157 : {
2158 846025 : if (find (i) == i && i != to)
2159 : {
2160 527301 : if (unite (to, i))
2161 60324 : queue.safe_push (i);
2162 : }
2163 : }
2164 :
2165 60324 : for (queuepos = 0;
2166 380473 : queue.iterate (queuepos, &i);
2167 : queuepos++)
2168 : {
2169 60324 : unify_nodes (graph, to, i, true);
2170 : }
2171 305302 : return true;
2172 305302 : }
2173 : return false;
2174 : }
2175 :
2176 : /* Solve the constraint graph GRAPH using our worklist solver.
2177 : This is based on the PW* family of solvers from the "Efficient Field
2178 : Sensitive Pointer Analysis for C" paper.
2179 : It works by iterating over all the graph nodes, processing the complex
2180 : constraints and propagating the copy constraints, until everything stops
2181 : changed. This corresponds to steps 6-8 in the solving list given above. */
2182 :
2183 : static void
2184 4624489 : solve_graph (constraint_graph_t graph)
2185 : {
2186 4624489 : unsigned int size = graph->size;
2187 4624489 : unsigned int i;
2188 4624489 : bitmap pts;
2189 :
2190 4624489 : changed = BITMAP_ALLOC (NULL);
2191 :
2192 : /* Mark all initial non-collapsed nodes as changed. */
2193 235560619 : for (i = 1; i < size; i++)
2194 : {
2195 230936130 : varinfo_t ivi = get_varinfo (i);
2196 417953569 : if (find (i) == i && !bitmap_empty_p (ivi->solution)
2197 289420856 : && ((graph->succs[i] && !bitmap_empty_p (graph->succs[i]))
2198 238871414 : || graph->complex[i].length () > 0))
2199 37310156 : bitmap_set_bit (changed, i);
2200 : }
2201 :
2202 : /* Allocate a bitmap to be used to store the changed bits. */
2203 4624489 : pts = BITMAP_ALLOC (&pta_obstack);
2204 :
2205 17483813 : while (!bitmap_empty_p (changed))
2206 : {
2207 8234835 : unsigned int i;
2208 8234835 : stats.iterations++;
2209 :
2210 8234835 : bitmap_obstack_initialize (&iteration_obstack);
2211 :
2212 8234835 : auto_vec<unsigned> topo_order = compute_topo_order (graph);
2213 483383929 : while (topo_order.length () != 0)
2214 : {
2215 466914259 : i = topo_order.pop ();
2216 :
2217 : /* If this variable is not a representative, skip it. */
2218 466914259 : if (find (i) != i)
2219 20252 : continue;
2220 :
2221 : /* In certain indirect cycle cases, we may merge this
2222 : variable to another. */
2223 466894007 : if (eliminate_indirect_cycles (i) && find (i) != i)
2224 93 : continue;
2225 :
2226 : /* If the node has changed, we need to process the
2227 : complex constraints and outgoing edges again. For complex
2228 : constraints that modify i itself, like the common group of
2229 : callarg = callarg + UNKNOWN;
2230 : callarg = *callarg + UNKNOWN;
2231 : *callarg = callescape;
2232 : make sure to iterate immediately because that maximizes
2233 : cache reuse and expands the graph quickest, leading to
2234 : better visitation order in the next iteration. */
2235 641117864 : while (bitmap_clear_bit (changed, i))
2236 : {
2237 174480287 : bitmap solution;
2238 174480287 : vec<constraint_t> &complex = graph->complex[i];
2239 174480287 : varinfo_t vi = get_varinfo (i);
2240 174480287 : bool solution_empty;
2241 :
2242 : /* Compute the changed set of solution bits. If anything
2243 : is in the solution just propagate that. */
2244 174480287 : if (bitmap_bit_p (vi->solution, anything_id))
2245 : {
2246 : /* If anything is also in the old solution there is
2247 : nothing to do.
2248 : ??? But we shouldn't ended up with "changed" set ... */
2249 2712618 : if (vi->oldsolution
2250 2712618 : && bitmap_bit_p (vi->oldsolution, anything_id))
2251 : break;
2252 2456281 : bitmap_copy (pts, get_varinfo (find (anything_id))->solution);
2253 : }
2254 171767669 : else if (vi->oldsolution)
2255 36354925 : bitmap_and_compl (pts, vi->solution, vi->oldsolution);
2256 : else
2257 135412744 : bitmap_copy (pts, vi->solution);
2258 :
2259 174223950 : if (bitmap_empty_p (pts))
2260 : break;
2261 :
2262 174223950 : if (vi->oldsolution)
2263 37573596 : bitmap_ior_into (vi->oldsolution, pts);
2264 : else
2265 : {
2266 136650354 : vi->oldsolution = BITMAP_ALLOC (&oldpta_obstack);
2267 136650354 : bitmap_copy (vi->oldsolution, pts);
2268 : }
2269 :
2270 174223950 : solution = vi->solution;
2271 174223950 : solution_empty = bitmap_empty_p (solution);
2272 :
2273 : /* Process the complex constraints. */
2274 174223950 : hash_set<constraint_t> *cvisited = nullptr;
2275 174223950 : if (flag_checking)
2276 174223101 : cvisited = new hash_set<constraint_t>;
2277 174223950 : bitmap expanded_pts = NULL;
2278 387819642 : for (unsigned j = 0; j < complex.length (); ++j)
2279 : {
2280 213595692 : constraint_t c = complex[j];
2281 : /* At unification time only the directly involved nodes
2282 : will get their complex constraints updated. Update
2283 : our complex constraints now but keep the constraint
2284 : vector sorted and clear of duplicates. Also make
2285 : sure to evaluate each prevailing constraint only once. */
2286 213595692 : unsigned int new_lhs = find (c->lhs.var);
2287 213595692 : unsigned int new_rhs = find (c->rhs.var);
2288 213595692 : if (c->lhs.var != new_lhs || c->rhs.var != new_rhs)
2289 : {
2290 94701 : constraint tem = *c;
2291 94701 : tem.lhs.var = new_lhs;
2292 94701 : tem.rhs.var = new_rhs;
2293 94701 : unsigned int place
2294 94701 : = complex.lower_bound (&tem, constraint_less);
2295 94701 : c->lhs.var = new_lhs;
2296 94701 : c->rhs.var = new_rhs;
2297 94701 : if (place != j)
2298 : {
2299 85659 : complex.ordered_remove (j);
2300 85659 : if (j < place)
2301 72989 : --place;
2302 85659 : if (place < complex.length ())
2303 : {
2304 31039 : if (constraint_equal (*complex[place], *c))
2305 : {
2306 12489 : j--;
2307 41239 : continue;
2308 : }
2309 : else
2310 18550 : complex.safe_insert (place, c);
2311 : }
2312 : else
2313 54620 : complex.quick_push (c);
2314 73170 : if (place > j)
2315 : {
2316 28750 : j--;
2317 28750 : continue;
2318 : }
2319 : }
2320 : }
2321 :
2322 : /* The only complex constraint that can change our
2323 : solution to non-empty, given an empty solution,
2324 : is a constraint where the lhs side is receiving
2325 : some set from elsewhere. */
2326 213554453 : if (cvisited && cvisited->add (c))
2327 0 : gcc_unreachable ();
2328 213554453 : if (!solution_empty || c->lhs.type != DEREF)
2329 213554453 : do_complex_constraint (graph, c, pts, &expanded_pts);
2330 : }
2331 174223950 : if (cvisited)
2332 : {
2333 : /* When checking, verify the order of constraints is
2334 : maintained and each constraint is evaluated exactly
2335 : once. */
2336 304907923 : for (unsigned j = 1; j < complex.length (); ++j)
2337 130684822 : gcc_assert (constraint_less (complex[j-1], complex[j]));
2338 257091672 : gcc_assert (cvisited->elements () == complex.length ());
2339 174223101 : delete cvisited;
2340 : }
2341 174223950 : BITMAP_FREE (expanded_pts);
2342 :
2343 174223950 : solution_empty = bitmap_empty_p (solution);
2344 :
2345 174223950 : if (!solution_empty)
2346 : {
2347 174223950 : bitmap_iterator bi;
2348 174223950 : unsigned eff_escaped_id = find (escaped_id);
2349 174223950 : unsigned j;
2350 :
2351 : /* Propagate solution to all successors. */
2352 174223950 : unsigned to_remove = ~0U;
2353 459466395 : EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i],
2354 : 0, j, bi)
2355 : {
2356 285242445 : if (to_remove != ~0U)
2357 : {
2358 780776 : bitmap_clear_bit (graph->succs[i], to_remove);
2359 780776 : to_remove = ~0U;
2360 : }
2361 285242445 : unsigned int to = find (j);
2362 285242445 : if (to != j)
2363 : {
2364 : /* Update the succ graph, avoiding duplicate
2365 : work. */
2366 842384 : to_remove = j;
2367 842384 : if (! bitmap_set_bit (graph->succs[i], to))
2368 126999 : continue;
2369 : /* We eventually end up processing 'to' twice
2370 : as it is undefined whether bitmap iteration
2371 : iterates over bits set during iteration.
2372 : Play safe instead of doing tricks. */
2373 : }
2374 : /* Don't try to propagate to ourselves. */
2375 285115446 : if (to == i)
2376 : {
2377 118347 : to_remove = j;
2378 118347 : continue;
2379 : }
2380 : /* Early node unification can lead to edges from
2381 : escaped - remove them. */
2382 284997099 : if (i == eff_escaped_id)
2383 : {
2384 20122 : to_remove = j;
2385 20122 : if (bitmap_set_bit (get_varinfo (to)->solution,
2386 : escaped_id))
2387 19340 : bitmap_set_bit (changed, to);
2388 20122 : continue;
2389 : }
2390 :
2391 284976977 : if (bitmap_ior_into (get_varinfo (to)->solution, pts))
2392 142065947 : bitmap_set_bit (changed, to);
2393 : }
2394 108086037 : if (to_remove != ~0U)
2395 133861 : bitmap_clear_bit (graph->succs[i], to_remove);
2396 : }
2397 : }
2398 : }
2399 8234835 : bitmap_obstack_release (&iteration_obstack);
2400 8234835 : }
2401 :
2402 4624489 : BITMAP_FREE (pts);
2403 4624489 : BITMAP_FREE (changed);
2404 4624489 : bitmap_obstack_release (&oldpta_obstack);
2405 4624489 : }
2406 :
2407 : void
2408 4624489 : delete_graph (void)
2409 : {
2410 4624489 : unsigned int i;
2411 240185108 : for (i = 0; i < graph->size; i++)
2412 235560619 : graph->complex[i].release ();
2413 4624489 : free (graph->complex);
2414 :
2415 4624489 : free (graph->succs);
2416 4624489 : free (graph->pe);
2417 4624489 : free (graph->pe_rep);
2418 4624489 : free (graph->indirect_cycles);
2419 : /* We are not doing free (graph->rep) since the representatives mapping is
2420 : needed outside of the solver too. */
2421 4624489 : free (graph);
2422 4624489 : }
2423 :
2424 : /* Remove the REF and ADDRESS edges from GRAPH, as well as all the
2425 : predecessor edges. */
2426 :
2427 : static void
2428 4624489 : remove_preds_and_fake_succs (constraint_graph_t graph)
2429 : {
2430 4624489 : unsigned int i;
2431 :
2432 : /* Clear the implicit ref and address nodes from the successor
2433 : lists. */
2434 235560619 : for (i = 1; i < FIRST_REF_NODE; i++)
2435 : {
2436 230936130 : if (graph->succs[i])
2437 75183016 : bitmap_clear_range (graph->succs[i], FIRST_REF_NODE,
2438 75183016 : FIRST_REF_NODE * 2);
2439 : }
2440 :
2441 : /* Free the successor list for the non-ref nodes. */
2442 240185108 : for (i = FIRST_REF_NODE + 1; i < graph->size; i++)
2443 : {
2444 230936130 : if (graph->succs[i])
2445 12307552 : BITMAP_FREE (graph->succs[i]);
2446 : }
2447 :
2448 : /* Now reallocate the size of the successor list as, and blow away
2449 : the predecessor bitmaps. */
2450 4624489 : graph->size = varmap.length ();
2451 4624489 : graph->succs = XRESIZEVEC (bitmap, graph->succs, graph->size);
2452 :
2453 4624489 : free (graph->implicit_preds);
2454 4624489 : graph->implicit_preds = NULL;
2455 4624489 : free (graph->preds);
2456 4624489 : graph->preds = NULL;
2457 4624489 : bitmap_obstack_release (&predbitmap_obstack);
2458 4624489 : }
2459 :
2460 : namespace pointer_analysis {
2461 :
2462 : /* Solve the constraint set. The entry function of the solver. */
2463 :
2464 : void
2465 4624489 : solve_constraints (void)
2466 : {
2467 4624489 : class scc_info *si;
2468 :
2469 : /* Sort varinfos so that ones that cannot be pointed to are last.
2470 : This makes bitmaps more efficient. */
2471 4624489 : unsigned int *map = XNEWVEC (unsigned int, varmap.length ());
2472 50869379 : for (unsigned i = 0; i < integer_id + 1; ++i)
2473 41620401 : map[i] = i;
2474 : /* Start with address-taken vars, followed by not address-taken vars
2475 : to move vars never appearing in the points-to solution bitmaps last. */
2476 : unsigned j = integer_id + 1;
2477 397129414 : for (unsigned i = integer_id + 1; i < varmap.length (); ++i)
2478 193940218 : if (varmap[varmap[i]->head]->address_taken)
2479 15915438 : map[i] = j++;
2480 198564707 : for (unsigned i = integer_id + 1; i < varmap.length (); ++i)
2481 193940218 : if (! varmap[varmap[i]->head]->address_taken)
2482 178024780 : map[i] = j++;
2483 : /* Shuffle varmap according to map. */
2484 198564707 : for (unsigned i = integer_id + 1; i < varmap.length (); ++i)
2485 : {
2486 288883118 : while (map[varmap[i]->id] != i)
2487 94942900 : std::swap (varmap[i], varmap[map[varmap[i]->id]]);
2488 193940218 : gcc_assert (bitmap_empty_p (varmap[i]->solution));
2489 193940218 : varmap[i]->id = i;
2490 193940218 : varmap[i]->next = map[varmap[i]->next];
2491 193940218 : varmap[i]->head = map[varmap[i]->head];
2492 : }
2493 : /* Finally rewrite constraints. */
2494 460410906 : for (unsigned i = 0; i < constraints.length (); ++i)
2495 : {
2496 455786417 : constraints[i]->lhs.var = map[constraints[i]->lhs.var];
2497 455786417 : constraints[i]->rhs.var = map[constraints[i]->rhs.var];
2498 : }
2499 4624489 : free (map);
2500 :
2501 4624489 : if (dump_file)
2502 489 : fprintf (dump_file,
2503 : "\nCollapsing static cycles and doing variable "
2504 : "substitution\n");
2505 :
2506 9248978 : init_graph (varmap.length () * 2);
2507 :
2508 4624489 : if (dump_file)
2509 489 : fprintf (dump_file, "Building predecessor graph\n");
2510 4624489 : build_pred_graph ();
2511 :
2512 4624489 : if (dump_file)
2513 489 : fprintf (dump_file, "Detecting pointer and location "
2514 : "equivalences\n");
2515 4624489 : si = perform_var_substitution (graph);
2516 :
2517 4624489 : if (dump_file)
2518 489 : fprintf (dump_file, "Rewriting constraints and unifying "
2519 : "variables\n");
2520 4624489 : rewrite_constraints (graph, si);
2521 :
2522 4624489 : build_succ_graph ();
2523 :
2524 4624489 : free_var_substitution_info (si);
2525 :
2526 : /* Attach complex constraints to graph nodes. */
2527 4624489 : move_complex_constraints (graph);
2528 :
2529 4624489 : if (dump_file)
2530 489 : fprintf (dump_file, "Uniting pointer but not location equivalent "
2531 : "variables\n");
2532 4624489 : unite_pointer_equivalences (graph);
2533 :
2534 4624489 : if (dump_file)
2535 489 : fprintf (dump_file, "Finding indirect cycles\n");
2536 4624489 : find_indirect_cycles (graph);
2537 :
2538 : /* Implicit nodes and predecessors are no longer necessary at this
2539 : point. */
2540 4624489 : remove_preds_and_fake_succs (graph);
2541 :
2542 4624489 : if (dump_file && (dump_flags & TDF_GRAPH))
2543 : {
2544 3 : fprintf (dump_file, "\n\n// The constraint graph before solve-graph "
2545 : "in dot format:\n");
2546 3 : dump_constraint_graph (dump_file);
2547 3 : fprintf (dump_file, "\n\n");
2548 : }
2549 :
2550 4624489 : if (dump_file)
2551 489 : fprintf (dump_file, "Solving graph\n");
2552 :
2553 4624489 : solve_graph (graph);
2554 :
2555 4624489 : if (dump_file && (dump_flags & TDF_GRAPH))
2556 : {
2557 3 : fprintf (dump_file, "\n\n// The constraint graph after solve-graph "
2558 : "in dot format:\n");
2559 3 : dump_constraint_graph (dump_file);
2560 3 : fprintf (dump_file, "\n\n");
2561 : }
2562 :
2563 : /* The mapping node -> representative is one of the outputs of the
2564 : solver. */
2565 4624489 : union_find_compress_all ();
2566 4624489 : var_rep = graph->rep;
2567 :
2568 4624489 : delete_graph ();
2569 4624489 : }
2570 :
2571 : } // namespace pointer_analysis
|
