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 9251962860 : find (unsigned int node)
136 : {
137 9251962860 : gcc_checking_assert (node < graph->size);
138 9251962860 : if (graph->rep[node] != node)
139 1048071784 : 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 589790081 : unite (unsigned int to, unsigned int from)
150 : {
151 589790081 : gcc_checking_assert (to < graph->size && from < graph->size);
152 589790081 : if (to != from && graph->rep[from] != to)
153 : {
154 69671705 : graph->rep[from] = to;
155 69671705 : return true;
156 : }
157 : return false;
158 : }
159 :
160 : /* Perform path compression for all nodes in the node representatives
161 : union-find structure. */
162 :
163 : static void
164 4411094 : union_find_compress_all (void)
165 : {
166 4411094 : unsigned int i;
167 228864962 : for (i = 0; i < graph->size; i++)
168 224453868 : find (i);
169 4411094 : }
170 :
171 : /* Print the constraint graph in dot format. */
172 :
173 : static void
174 6 : dump_constraint_graph (FILE *file)
175 : {
176 6 : unsigned int i;
177 :
178 : /* Only print the graph if it has already been initialized: */
179 6 : if (!graph)
180 : return;
181 :
182 : /* Prints the header of the dot file: */
183 6 : fprintf (file, "strict digraph {\n");
184 6 : fprintf (file, " node [\n shape = box\n ]\n");
185 6 : fprintf (file, " edge [\n fontsize = \"12\"\n ]\n");
186 6 : fprintf (file, "\n // List of nodes and complex constraints in "
187 : "the constraint graph:\n");
188 :
189 : /* The next lines print the nodes in the graph together with the
190 : complex constraints attached to them. */
191 80 : for (i = 1; i < graph->size; i++)
192 : {
193 148 : if (i == FIRST_REF_NODE)
194 0 : continue;
195 74 : if (find (i) != i)
196 2 : continue;
197 72 : if (i < FIRST_REF_NODE)
198 72 : fprintf (file, "\"%s\"", get_varinfo (i)->name);
199 : else
200 0 : fprintf (file, "\"*%s\"", get_varinfo (i - FIRST_REF_NODE)->name);
201 72 : if (graph->complex[i].exists ())
202 : {
203 16 : unsigned j;
204 16 : constraint_t c;
205 16 : fprintf (file, " [label=\"\\N\\n");
206 70 : for (j = 0; graph->complex[i].iterate (j, &c); ++j)
207 : {
208 38 : dump_constraint (file, c);
209 38 : fprintf (file, "\\l");
210 : }
211 16 : fprintf (file, "\"]");
212 : }
213 72 : fprintf (file, ";\n");
214 : }
215 :
216 : /* Go over the edges. */
217 6 : fprintf (file, "\n // Edges in the constraint graph:\n");
218 80 : for (i = 1; i < graph->size; i++)
219 : {
220 74 : unsigned j;
221 74 : bitmap_iterator bi;
222 74 : if (find (i) != i)
223 2 : continue;
224 102 : EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i], 0, j, bi)
225 : {
226 30 : unsigned to = find (j);
227 30 : if (i == to)
228 0 : continue;
229 30 : if (i < FIRST_REF_NODE)
230 30 : fprintf (file, "\"%s\"", get_varinfo (i)->name);
231 : else
232 0 : fprintf (file, "\"*%s\"", get_varinfo (i - FIRST_REF_NODE)->name);
233 30 : fprintf (file, " -> ");
234 30 : if (to < FIRST_REF_NODE)
235 30 : fprintf (file, "\"%s\"", get_varinfo (to)->name);
236 : else
237 0 : fprintf (file, "\"*%s\"", get_varinfo (to - FIRST_REF_NODE)->name);
238 30 : fprintf (file, ";\n");
239 : }
240 : }
241 :
242 : /* Prints the tail of the dot file. */
243 6 : fprintf (file, "}\n");
244 : }
245 :
246 : /* Print out the constraint graph to stderr. */
247 :
248 : DEBUG_FUNCTION void
249 0 : debug_constraint_graph (void)
250 : {
251 0 : dump_constraint_graph (stderr);
252 0 : }
253 :
254 :
255 : /* SOLVER FUNCTIONS
256 :
257 : The solver is a simple worklist solver, that works on the following
258 : algorithm:
259 :
260 : sbitmap changed_nodes = all zeroes;
261 : changed_count = 0;
262 : For each node that is not already collapsed:
263 : changed_count++;
264 : set bit in changed nodes
265 :
266 : while (changed_count > 0)
267 : {
268 : compute topological ordering for constraint graph
269 :
270 : find and collapse cycles in the constraint graph (updating
271 : changed if necessary)
272 :
273 : for each node (n) in the graph in topological order:
274 : changed_count--;
275 :
276 : Process each complex constraint associated with the node,
277 : updating changed if necessary.
278 :
279 : For each outgoing edge from n, propagate the solution from n to
280 : the destination of the edge, updating changed as necessary.
281 :
282 : } */
283 :
284 : /* Return true if two constraint expressions A and B are equal. */
285 :
286 : static bool
287 19014190 : constraint_expr_equal (struct constraint_expr a, struct constraint_expr b)
288 : {
289 11842372 : return a.type == b.type && a.var == b.var && a.offset == b.offset;
290 : }
291 :
292 : /* Return true if constraint expression A is less than constraint expression
293 : B. This is just arbitrary, but consistent, in order to give them an
294 : ordering. */
295 :
296 : static bool
297 447972669 : constraint_expr_less (struct constraint_expr a, struct constraint_expr b)
298 : {
299 0 : if (a.type == b.type)
300 : {
301 267319970 : if (a.var == b.var)
302 201472181 : return a.offset < b.offset;
303 : else
304 65847789 : return a.var < b.var;
305 : }
306 : else
307 180652699 : return a.type < b.type;
308 : }
309 :
310 : /* Return true if constraint A is less than constraint B. This is just
311 : arbitrary, but consistent, in order to give them an ordering. */
312 :
313 : static bool
314 246123016 : constraint_less (const constraint_t &a, const constraint_t &b)
315 : {
316 492246032 : if (constraint_expr_less (a->lhs, b->lhs))
317 : return true;
318 213285786 : else if (constraint_expr_less (b->lhs, a->lhs))
319 : return false;
320 : else
321 95206760 : return constraint_expr_less (a->rhs, b->rhs);
322 : }
323 :
324 : /* Return true if two constraints A and B are equal. */
325 :
326 : static bool
327 12430138 : constraint_equal (const constraint &a, const constraint &b)
328 : {
329 19014190 : return constraint_expr_equal (a.lhs, b.lhs)
330 12430138 : && constraint_expr_equal (a.rhs, b.rhs);
331 : }
332 :
333 : /* Find a constraint LOOKFOR in the sorted constraint vector VEC. */
334 :
335 : static constraint_t
336 261390 : constraint_vec_find (vec<constraint_t> vec,
337 : constraint &lookfor)
338 : {
339 261390 : unsigned int place;
340 261390 : constraint_t found;
341 :
342 261390 : if (!vec.exists ())
343 : return NULL;
344 :
345 208055 : place = vec.lower_bound (&lookfor, constraint_less);
346 208055 : if (place >= vec.length ())
347 : return NULL;
348 79758 : found = vec[place];
349 79758 : if (!constraint_equal (*found, lookfor))
350 : return NULL;
351 : return found;
352 : }
353 :
354 : /* Union two constraint vectors, TO and FROM. Put the result in TO.
355 : Returns true of TO set is changed. */
356 :
357 : static bool
358 69553926 : constraint_set_union (vec<constraint_t> *to,
359 : vec<constraint_t> *from)
360 : {
361 69553926 : int i;
362 69553926 : constraint_t c;
363 69553926 : bool any_change = false;
364 :
365 69815316 : FOR_EACH_VEC_ELT (*from, i, c)
366 : {
367 261390 : if (constraint_vec_find (*to, *c) == NULL)
368 : {
369 260932 : unsigned int place = to->lower_bound (c, constraint_less);
370 260932 : to->safe_insert (place, c);
371 260932 : any_change = true;
372 : }
373 : }
374 69553926 : return any_change;
375 : }
376 :
377 : /* Expands the solution in SET to all sub-fields of variables included. */
378 :
379 : static bitmap
380 133927727 : solution_set_expand (bitmap set, bitmap *expanded)
381 : {
382 133927727 : bitmap_iterator bi;
383 133927727 : unsigned j;
384 :
385 133927727 : if (*expanded)
386 : return *expanded;
387 :
388 74787803 : *expanded = BITMAP_ALLOC (&iteration_obstack);
389 :
390 : /* In a first pass expand variables, once for each head to avoid
391 : quadratic behavior, to include all sub-fields. */
392 74787803 : unsigned prev_head = 0;
393 294175426 : EXECUTE_IF_SET_IN_BITMAP (set, 0, j, bi)
394 : {
395 219387623 : varinfo_t v = get_varinfo (j);
396 219387623 : if (v->is_artificial_var
397 130957256 : || v->is_full_var)
398 109700627 : continue;
399 109686996 : if (v->head != prev_head)
400 : {
401 24545668 : varinfo_t head = get_varinfo (v->head);
402 24545668 : unsigned num = 1;
403 146341584 : for (varinfo_t n = vi_next (head); n != NULL; n = vi_next (n))
404 : {
405 121795916 : if (n->id != head->id + num)
406 : {
407 : /* Usually sub variables are adjacent but since we
408 : create pointed-to restrict representatives there
409 : can be gaps as well. */
410 14218 : bitmap_set_range (*expanded, head->id, num);
411 14218 : head = n;
412 14218 : num = 1;
413 : }
414 : else
415 121781698 : num++;
416 : }
417 :
418 24545668 : bitmap_set_range (*expanded, head->id, num);
419 24545668 : prev_head = v->head;
420 : }
421 : }
422 :
423 : /* And finally set the rest of the bits from SET in an efficient way. */
424 74787803 : bitmap_ior_into (*expanded, set);
425 :
426 74787803 : return *expanded;
427 : }
428 :
429 : /* Union solution sets TO and DELTA, and add INC to each member of DELTA in the
430 : process. */
431 :
432 : static bool
433 83667175 : set_union_with_increment (bitmap to, bitmap delta, HOST_WIDE_INT inc,
434 : bitmap *expanded_delta)
435 : {
436 83667175 : bool changed = false;
437 83667175 : bitmap_iterator bi;
438 83667175 : unsigned int i;
439 :
440 : /* If the solution of DELTA contains anything it is good enough to transfer
441 : this to TO. */
442 83667175 : if (bitmap_bit_p (delta, anything_id))
443 1053816 : return bitmap_set_bit (to, anything_id);
444 :
445 : /* If the offset is unknown we have to expand the solution to
446 : all subfields. */
447 82613359 : if (inc == UNKNOWN_OFFSET)
448 : {
449 81686082 : delta = solution_set_expand (delta, expanded_delta);
450 81686082 : changed |= bitmap_ior_into (to, delta);
451 81686082 : return changed;
452 : }
453 :
454 : /* For non-zero offset union the offsetted solution into the destination. */
455 4206999 : EXECUTE_IF_SET_IN_BITMAP (delta, 0, i, bi)
456 : {
457 3279722 : varinfo_t vi = get_varinfo (i);
458 :
459 : /* If this is a variable with just one field just set its bit
460 : in the result. */
461 3279722 : if (vi->is_artificial_var
462 2077304 : || vi->is_unknown_size_var
463 1885436 : || vi->is_full_var)
464 1604143 : changed |= bitmap_set_bit (to, i);
465 : else
466 : {
467 1675579 : HOST_WIDE_INT fieldoffset = vi->offset + inc;
468 1675579 : unsigned HOST_WIDE_INT size = vi->size;
469 :
470 : /* If the offset makes the pointer point to before the
471 : variable use offset zero for the field lookup. */
472 1675579 : if (fieldoffset < 0)
473 57906 : vi = get_varinfo (vi->head);
474 : else
475 1617673 : vi = first_or_preceding_vi_for_offset (vi, fieldoffset);
476 :
477 2657492 : do
478 : {
479 2657492 : changed |= bitmap_set_bit (to, vi->id);
480 2657492 : if (vi->is_full_var
481 2657452 : || vi->next == 0)
482 : break;
483 :
484 : /* We have to include all fields that overlap the current field
485 : shifted by inc. */
486 1592755 : vi = vi_next (vi);
487 : }
488 1592755 : while (vi->offset < fieldoffset + size);
489 : }
490 : }
491 :
492 : return changed;
493 : }
494 :
495 : /* Insert constraint C into the list of complex constraints for graph
496 : node VAR. */
497 :
498 : static void
499 143204808 : insert_into_complex (constraint_graph_t graph,
500 : unsigned int var, constraint_t c)
501 : {
502 143204808 : vec<constraint_t> complex = graph->complex[var];
503 143204808 : unsigned int place = complex.lower_bound (c, constraint_less);
504 :
505 : /* Only insert constraints that do not already exist. */
506 143204808 : if (place >= complex.length ()
507 98303248 : || !constraint_equal (*c, *complex[place]))
508 141247472 : graph->complex[var].safe_insert (place, c);
509 143204808 : }
510 :
511 :
512 : /* Condense two variable nodes into a single variable node, by moving
513 : all associated info from FROM to TO. Returns true if TO node's
514 : constraint set changes after the merge. */
515 :
516 : static bool
517 69553926 : merge_node_constraints (constraint_graph_t graph, unsigned int to,
518 : unsigned int from)
519 : {
520 69553926 : unsigned int i;
521 69553926 : constraint_t c;
522 69553926 : bool any_change = false;
523 :
524 69553926 : gcc_checking_assert (find (from) == to);
525 :
526 : /* Move all complex constraints from src node into to node. */
527 69815316 : FOR_EACH_VEC_ELT (graph->complex[from], i, c)
528 : {
529 : /* In complex constraints for node FROM, we may have either
530 : a = *FROM, and *FROM = a, or an offseted constraint which are
531 : always added to the rhs node's constraints. */
532 :
533 261390 : if (c->rhs.type == DEREF)
534 85465 : c->rhs.var = to;
535 175925 : else if (c->lhs.type == DEREF)
536 86446 : c->lhs.var = to;
537 : else
538 89479 : c->rhs.var = to;
539 :
540 : }
541 69553926 : any_change = constraint_set_union (&graph->complex[to],
542 : &graph->complex[from]);
543 69553926 : graph->complex[from].release ();
544 69553926 : return any_change;
545 : }
546 :
547 : /* Remove edges involving NODE from GRAPH. */
548 :
549 : static void
550 89204175 : clear_edges_for_node (constraint_graph_t graph, unsigned int node)
551 : {
552 89204175 : if (graph->succs[node])
553 2414039 : BITMAP_FREE (graph->succs[node]);
554 89204175 : }
555 :
556 : /* Merge GRAPH nodes FROM and TO into node TO. */
557 :
558 : static void
559 69553926 : merge_graph_nodes (constraint_graph_t graph, unsigned int to,
560 : unsigned int from)
561 : {
562 69553926 : if (graph->indirect_cycles[from] != -1)
563 : {
564 : /* If we have indirect cycles with the from node, and we have
565 : none on the to node, the to node has indirect cycles from the
566 : from node now that they are unified.
567 : If indirect cycles exist on both, unify the nodes that they
568 : are in a cycle with, since we know they are in a cycle with
569 : each other. */
570 119 : if (graph->indirect_cycles[to] == -1)
571 80 : graph->indirect_cycles[to] = graph->indirect_cycles[from];
572 : }
573 :
574 : /* Merge all the successor edges. */
575 69553926 : if (graph->succs[from])
576 : {
577 2414039 : if (!graph->succs[to])
578 1232963 : graph->succs[to] = BITMAP_ALLOC (&pta_obstack);
579 2414039 : bitmap_ior_into (graph->succs[to],
580 2414039 : graph->succs[from]);
581 : }
582 :
583 69553926 : clear_edges_for_node (graph, from);
584 69553926 : }
585 :
586 :
587 : /* Add an indirect graph edge to GRAPH, going from TO to FROM if
588 : it doesn't exist in the graph already. */
589 :
590 : static void
591 289510438 : add_implicit_graph_edge (constraint_graph_t graph, unsigned int to,
592 : unsigned int from)
593 : {
594 289510438 : if (to == from)
595 : return;
596 :
597 289510438 : if (!graph->implicit_preds[to])
598 162221257 : graph->implicit_preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
599 :
600 289510438 : if (bitmap_set_bit (graph->implicit_preds[to], from))
601 272181555 : stats.num_implicit_edges++;
602 : }
603 :
604 : /* Add a predecessor graph edge to GRAPH, going from TO to FROM if
605 : it doesn't exist in the graph already.
606 : Return false if the edge already existed, true otherwise. */
607 :
608 : static void
609 244477615 : add_pred_graph_edge (constraint_graph_t graph, unsigned int to,
610 : unsigned int from)
611 : {
612 244477615 : if (!graph->preds[to])
613 144141854 : graph->preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
614 244477615 : bitmap_set_bit (graph->preds[to], from);
615 244477615 : }
616 :
617 : /* Add a graph edge to GRAPH, going from FROM to TO if
618 : it doesn't exist in the graph already.
619 : Return false if the edge already existed, true otherwise. */
620 :
621 : static bool
622 787776889 : add_graph_edge (constraint_graph_t graph, unsigned int to,
623 : unsigned int from)
624 : {
625 787776889 : if (to == from)
626 : {
627 : return false;
628 : }
629 : else
630 : {
631 787061813 : bool r = false;
632 :
633 787061813 : if (!graph->succs[from])
634 91519855 : graph->succs[from] = BITMAP_ALLOC (&pta_obstack);
635 :
636 : /* The graph solving process does not avoid "triangles", thus
637 : there can be multiple paths from a node to another involving
638 : intermediate other nodes. That causes extra copying which is
639 : most difficult to avoid when the intermediate node is ESCAPED
640 : because there are no edges added from ESCAPED. Avoid
641 : adding the direct edge FROM -> TO when we have FROM -> ESCAPED
642 : and TO contains ESCAPED.
643 : ??? Note this is only a heuristic, it does not prevent the
644 : situation from occuring. The heuristic helps PR38474 and
645 : PR99912 significantly. */
646 787061813 : if (to < FIRST_REF_NODE
647 755724670 : && bitmap_bit_p (graph->succs[from], find (escaped_id))
648 1150267489 : && bitmap_bit_p (get_varinfo (find (to))->solution, escaped_id))
649 : {
650 305635202 : stats.num_avoided_edges++;
651 305635202 : return false;
652 : }
653 :
654 481426611 : if (bitmap_set_bit (graph->succs[from], to))
655 : {
656 336941415 : r = true;
657 336941415 : if (to < FIRST_REF_NODE && from < FIRST_REF_NODE)
658 293641663 : stats.num_edges++;
659 : }
660 481426611 : return r;
661 : }
662 : }
663 :
664 : /* Initialize the constraint graph structure to contain SIZE nodes. */
665 :
666 : static void
667 4411094 : init_graph (unsigned int size)
668 : {
669 4411094 : unsigned int j;
670 :
671 4411094 : bitmap_obstack_initialize (&predbitmap_obstack);
672 :
673 4411094 : graph = XCNEW (struct constraint_graph);
674 4411094 : graph->size = size;
675 4411094 : graph->succs = XCNEWVEC (bitmap, graph->size);
676 4411094 : graph->indirect_cycles = XNEWVEC (int, graph->size);
677 4411094 : graph->rep = XNEWVEC (unsigned int, graph->size);
678 : /* ??? Macros do not support template types with multiple arguments,
679 : so we use a typedef to work around it. */
680 4411094 : typedef vec<constraint_t> vec_constraint_t_heap;
681 4411094 : graph->complex = XCNEWVEC (vec_constraint_t_heap, size);
682 4411094 : graph->pe = XCNEWVEC (unsigned int, graph->size);
683 4411094 : graph->pe_rep = XNEWVEC (int, graph->size);
684 :
685 453318830 : for (j = 0; j < graph->size; j++)
686 : {
687 448907736 : graph->rep[j] = j;
688 448907736 : graph->pe_rep[j] = -1;
689 448907736 : graph->indirect_cycles[j] = -1;
690 : }
691 4411094 : }
692 :
693 : /* Build the constraint graph, adding only predecessor edges right now. */
694 :
695 : static void
696 4411094 : build_pred_graph (void)
697 : {
698 4411094 : int i;
699 4411094 : constraint_t c;
700 4411094 : unsigned int j;
701 :
702 4411094 : graph->implicit_preds = XCNEWVEC (bitmap, graph->size);
703 4411094 : graph->preds = XCNEWVEC (bitmap, graph->size);
704 4411094 : graph->pointer_label = XCNEWVEC (unsigned int, graph->size);
705 4411094 : graph->loc_label = XCNEWVEC (unsigned int, graph->size);
706 4411094 : graph->pointed_by = XCNEWVEC (bitmap, graph->size);
707 4411094 : graph->points_to = XCNEWVEC (bitmap, graph->size);
708 4411094 : graph->eq_rep = XNEWVEC (int, graph->size);
709 4411094 : graph->direct_nodes = sbitmap_alloc (graph->size);
710 4411094 : graph->address_taken = BITMAP_ALLOC (&predbitmap_obstack);
711 4411094 : bitmap_clear (graph->direct_nodes);
712 :
713 453318830 : for (j = 1; j < FIRST_REF_NODE; j++)
714 : {
715 220042774 : if (!get_varinfo (j)->is_special_var)
716 197987304 : bitmap_set_bit (graph->direct_nodes, j);
717 : }
718 :
719 453318830 : for (j = 0; j < graph->size; j++)
720 448907736 : graph->eq_rep[j] = -1;
721 :
722 457729924 : for (j = 0; j < varmap.length (); j++)
723 224453868 : graph->indirect_cycles[j] = -1;
724 :
725 438334715 : FOR_EACH_VEC_ELT (constraints, i, c)
726 : {
727 433923621 : struct constraint_expr lhs = c->lhs;
728 433923621 : struct constraint_expr rhs = c->rhs;
729 433923621 : unsigned int lhsvar = lhs.var;
730 433923621 : unsigned int rhsvar = rhs.var;
731 :
732 433923621 : if (lhs.type == DEREF)
733 : {
734 : /* *x = y. */
735 35689707 : if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
736 : {
737 31355729 : if (lhs.var == anything_id)
738 0 : add_pred_graph_edge (graph, storedanything_id, rhsvar);
739 : else
740 62711458 : add_pred_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
741 : }
742 : }
743 398233914 : else if (rhs.type == DEREF)
744 : {
745 : /* x = *y */
746 47875408 : if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
747 25998148 : add_pred_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
748 : else
749 34876334 : bitmap_clear_bit (graph->direct_nodes, lhsvar);
750 : }
751 350358506 : else if (rhs.type == ADDRESSOF)
752 : {
753 89387626 : varinfo_t v;
754 :
755 : /* x = &y */
756 89387626 : if (graph->points_to[lhsvar] == NULL)
757 66350937 : graph->points_to[lhsvar] = BITMAP_ALLOC (&predbitmap_obstack);
758 89387626 : bitmap_set_bit (graph->points_to[lhsvar], rhsvar);
759 :
760 89387626 : if (graph->pointed_by[rhsvar] == NULL)
761 21454192 : graph->pointed_by[rhsvar] = BITMAP_ALLOC (&predbitmap_obstack);
762 89387626 : bitmap_set_bit (graph->pointed_by[rhsvar], lhsvar);
763 :
764 : /* Implicitly, *x = y */
765 178775252 : add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
766 :
767 : /* All related variables are no longer direct nodes. */
768 89387626 : bitmap_clear_bit (graph->direct_nodes, rhsvar);
769 89387626 : v = get_varinfo (rhsvar);
770 89387626 : if (!v->is_full_var)
771 : {
772 7338739 : v = get_varinfo (v->head);
773 47255236 : do
774 : {
775 47255236 : bitmap_clear_bit (graph->direct_nodes, v->id);
776 47255236 : v = vi_next (v);
777 : }
778 47255236 : while (v != NULL);
779 : }
780 89387626 : bitmap_set_bit (graph->address_taken, rhsvar);
781 : }
782 260970880 : else if (lhsvar > anything_id
783 260970880 : && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
784 : {
785 : /* x = y */
786 200122812 : add_pred_graph_edge (graph, lhsvar, rhsvar);
787 : /* Implicitly, *x = *y */
788 200122812 : add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar,
789 200122812 : FIRST_REF_NODE + rhsvar);
790 : }
791 60848068 : else if (lhs.offset != 0 || rhs.offset != 0)
792 : {
793 60652648 : if (rhs.offset != 0)
794 60652648 : bitmap_clear_bit (graph->direct_nodes, lhs.var);
795 0 : else if (lhs.offset != 0)
796 0 : bitmap_clear_bit (graph->direct_nodes, rhs.var);
797 : }
798 : }
799 4411094 : }
800 :
801 : /* Build the constraint graph, adding successor edges. */
802 :
803 : static void
804 4411094 : build_succ_graph (void)
805 : {
806 4411094 : unsigned i, t;
807 4411094 : constraint_t c;
808 :
809 438334715 : FOR_EACH_VEC_ELT (constraints, i, c)
810 : {
811 433923621 : struct constraint_expr lhs;
812 433923621 : struct constraint_expr rhs;
813 433923621 : unsigned int lhsvar;
814 433923621 : unsigned int rhsvar;
815 :
816 433923621 : if (!c)
817 2403354 : continue;
818 :
819 431520267 : lhs = c->lhs;
820 431520267 : rhs = c->rhs;
821 431520267 : lhsvar = find (lhs.var);
822 431520267 : rhsvar = find (rhs.var);
823 :
824 431520267 : if (lhs.type == DEREF)
825 : {
826 35652946 : if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
827 : {
828 31337143 : if (lhs.var == anything_id)
829 0 : add_graph_edge (graph, storedanything_id, rhsvar);
830 : else
831 62674286 : add_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
832 : }
833 : }
834 395867321 : else if (rhs.type == DEREF)
835 : {
836 47874430 : if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
837 25996568 : add_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
838 : }
839 347992891 : else if (rhs.type == ADDRESSOF)
840 : {
841 : /* x = &y */
842 89387626 : gcc_checking_assert (find (rhs.var) == rhs.var);
843 89387626 : bitmap_set_bit (get_varinfo (lhsvar)->solution, rhsvar);
844 : }
845 258605265 : else if (lhsvar > anything_id
846 258605265 : && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
847 : {
848 150275475 : add_graph_edge (graph, lhsvar, rhsvar);
849 : }
850 : }
851 :
852 : /* Add edges from STOREDANYTHING to all nodes that can receive pointers. */
853 4411094 : t = find (storedanything_id);
854 193576210 : for (i = integer_id + 1; i < FIRST_REF_NODE; ++i)
855 : {
856 184754022 : if (get_varinfo (i)->may_have_pointers)
857 184730282 : add_graph_edge (graph, find (i), t);
858 : }
859 :
860 : /* Everything stored to ANYTHING also potentially escapes. */
861 4411094 : add_graph_edge (graph, find (escaped_id), t);
862 4411094 : }
863 :
864 :
865 : /* Changed variables on the last iteration. */
866 : static bitmap changed;
867 :
868 : /* Strongly Connected Component visitation info. */
869 :
870 : class scc_info
871 : {
872 : public:
873 : scc_info (size_t size);
874 : ~scc_info ();
875 :
876 : auto_sbitmap visited;
877 : auto_sbitmap deleted;
878 : unsigned int *dfs;
879 : unsigned int *node_mapping;
880 : int current_index;
881 : auto_vec<unsigned> scc_stack;
882 : };
883 :
884 :
885 : /* Recursive routine to find strongly connected components in GRAPH.
886 : SI is the SCC info to store the information in, and N is the id of current
887 : graph node we are processing.
888 :
889 : This is Tarjan's strongly connected component finding algorithm, as
890 : modified by Nuutila to keep only non-root nodes on the stack.
891 : The algorithm can be found in "On finding the strongly connected
892 : connected components in a directed graph" by Esko Nuutila and Eljas
893 : Soisalon-Soininen, in Information Processing Letters volume 49,
894 : number 1, pages 9-14. */
895 :
896 : static void
897 376116332 : scc_visit (constraint_graph_t graph, class scc_info *si, unsigned int n)
898 : {
899 376116332 : unsigned int i;
900 376116332 : bitmap_iterator bi;
901 376116332 : unsigned int my_dfs;
902 :
903 376116332 : bitmap_set_bit (si->visited, n);
904 376116332 : si->dfs[n] = si->current_index ++;
905 376116332 : my_dfs = si->dfs[n];
906 :
907 : /* Visit all the successors. */
908 638303460 : EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[n], 0, i, bi)
909 : {
910 262187128 : unsigned int w;
911 :
912 524374256 : if (i > LAST_REF_NODE)
913 : break;
914 :
915 262187128 : w = find (i);
916 262187128 : if (bitmap_bit_p (si->deleted, w))
917 113651428 : continue;
918 :
919 148535700 : if (!bitmap_bit_p (si->visited, w))
920 148278640 : scc_visit (graph, si, w);
921 :
922 148535700 : unsigned int t = find (w);
923 148535700 : gcc_checking_assert (find (n) == n);
924 148535700 : if (si->dfs[t] < si->dfs[n])
925 136446 : si->dfs[n] = si->dfs[t];
926 : }
927 :
928 : /* See if any components have been identified. */
929 376116332 : if (si->dfs[n] == my_dfs)
930 : {
931 375979944 : if (si->scc_stack.length () > 0
932 375979944 : && si->dfs[si->scc_stack.last ()] >= my_dfs)
933 : {
934 103038 : bitmap scc = BITMAP_ALLOC (NULL);
935 103038 : unsigned int lowest_node;
936 103038 : bitmap_iterator bi;
937 :
938 103038 : bitmap_set_bit (scc, n);
939 :
940 103038 : while (si->scc_stack.length () != 0
941 239426 : && si->dfs[si->scc_stack.last ()] >= my_dfs)
942 : {
943 136388 : unsigned int w = si->scc_stack.pop ();
944 :
945 136388 : bitmap_set_bit (scc, w);
946 : }
947 :
948 103038 : lowest_node = bitmap_first_set_bit (scc);
949 103038 : gcc_assert (lowest_node < FIRST_REF_NODE);
950 :
951 : /* Collapse the SCC nodes into a single node, and mark the
952 : indirect cycles. */
953 342464 : EXECUTE_IF_SET_IN_BITMAP (scc, 0, i, bi)
954 : {
955 239426 : if (i < FIRST_REF_NODE)
956 : {
957 121647 : if (unite (lowest_node, i))
958 18609 : unify_nodes (graph, lowest_node, i, false);
959 : }
960 : else
961 : {
962 117779 : unite (lowest_node, i);
963 235558 : graph->indirect_cycles[i - FIRST_REF_NODE] = lowest_node;
964 : }
965 : }
966 103038 : bitmap_set_bit (si->deleted, lowest_node);
967 : }
968 : else
969 375876906 : bitmap_set_bit (si->deleted, n);
970 : }
971 : else
972 136388 : si->scc_stack.safe_push (n);
973 376116332 : }
974 :
975 : /* Unify node FROM into node TO, updating the changed count if
976 : necessary when UPDATE_CHANGED is true. */
977 :
978 : static void
979 69553926 : unify_nodes (constraint_graph_t graph, unsigned int to, unsigned int from,
980 : bool update_changed)
981 : {
982 69553926 : gcc_checking_assert (to != from && find (to) == to);
983 :
984 69553926 : if (dump_file && (dump_flags & TDF_DETAILS))
985 1228 : fprintf (dump_file, "Unifying %s to %s\n",
986 1228 : get_varinfo (from)->name,
987 1228 : get_varinfo (to)->name);
988 :
989 69553926 : if (update_changed)
990 337293 : stats.unified_vars_dynamic++;
991 : else
992 69216633 : stats.unified_vars_static++;
993 :
994 69553926 : merge_graph_nodes (graph, to, from);
995 69553926 : if (merge_node_constraints (graph, to, from))
996 : {
997 88621 : if (update_changed)
998 10779 : bitmap_set_bit (changed, to);
999 : }
1000 :
1001 : /* Mark TO as changed if FROM was changed. If TO was already marked
1002 : as changed, decrease the changed count. */
1003 :
1004 69476084 : if (update_changed
1005 69476084 : && bitmap_clear_bit (changed, from))
1006 33607 : bitmap_set_bit (changed, to);
1007 69553926 : varinfo_t fromvi = get_varinfo (from);
1008 69553926 : if (fromvi->solution)
1009 : {
1010 : /* If the solution changes because of the merging, we need to mark
1011 : the variable as changed. */
1012 69553926 : varinfo_t tovi = get_varinfo (to);
1013 69553926 : if (bitmap_ior_into (tovi->solution, fromvi->solution))
1014 : {
1015 1905501 : if (update_changed)
1016 67144 : bitmap_set_bit (changed, to);
1017 : }
1018 :
1019 69553926 : BITMAP_FREE (fromvi->solution);
1020 69553926 : if (fromvi->oldsolution)
1021 215548 : BITMAP_FREE (fromvi->oldsolution);
1022 :
1023 69553926 : if (stats.iterations > 0
1024 337293 : && tovi->oldsolution)
1025 16197 : BITMAP_FREE (tovi->oldsolution);
1026 : }
1027 69553926 : if (graph->succs[to])
1028 2591808 : bitmap_clear_bit (graph->succs[to], to);
1029 69553926 : }
1030 :
1031 : /* Add a copy edge FROM -> TO, optimizing special cases. Returns TRUE
1032 : if the solution of TO changed. */
1033 :
1034 : static bool
1035 424593359 : solve_add_graph_edge (constraint_graph_t graph, unsigned int to,
1036 : unsigned int from)
1037 : {
1038 : /* Adding edges from the special vars is pointless.
1039 : They don't have sets that can change. */
1040 424593359 : if (get_varinfo (from)->is_special_var)
1041 29822361 : return bitmap_ior_into (get_varinfo (to)->solution,
1042 59644722 : get_varinfo (from)->solution);
1043 : /* Merging the solution from ESCAPED needlessly increases
1044 : the set. Use ESCAPED as representative instead. */
1045 394770998 : else if (from == find (escaped_id))
1046 34827057 : return bitmap_set_bit (get_varinfo (to)->solution, escaped_id);
1047 359943941 : else if (get_varinfo (from)->may_have_pointers
1048 359943941 : && add_graph_edge (graph, to, from))
1049 117487872 : return bitmap_ior_into (get_varinfo (to)->solution,
1050 117487872 : get_varinfo (from)->solution);
1051 : return false;
1052 : }
1053 :
1054 : /* Process a constraint C that represents x = *(y + off), using DELTA as the
1055 : starting solution for y. */
1056 :
1057 : static void
1058 68221234 : do_sd_constraint (constraint_graph_t graph, constraint_t c,
1059 : bitmap delta, bitmap *expanded_delta)
1060 : {
1061 68221234 : unsigned int lhs = c->lhs.var;
1062 68221234 : bool flag = false;
1063 68221234 : bitmap sol = get_varinfo (lhs)->solution;
1064 68221234 : unsigned int j;
1065 68221234 : bitmap_iterator bi;
1066 68221234 : HOST_WIDE_INT roffset = c->rhs.offset;
1067 :
1068 : /* Our IL does not allow this. */
1069 68221234 : gcc_checking_assert (c->lhs.offset == 0);
1070 :
1071 : /* If the solution of Y contains anything it is good enough to transfer
1072 : this to the LHS. */
1073 68221234 : if (bitmap_bit_p (delta, anything_id))
1074 : {
1075 464566 : flag |= bitmap_set_bit (sol, anything_id);
1076 464566 : goto done;
1077 : }
1078 :
1079 : /* If we do not know at with offset the rhs is dereferenced compute
1080 : the reachability set of DELTA, conservatively assuming it is
1081 : dereferenced at all valid offsets. */
1082 67756668 : if (roffset == UNKNOWN_OFFSET)
1083 : {
1084 50176730 : delta = solution_set_expand (delta, expanded_delta);
1085 : /* No further offset processing is necessary. */
1086 50176730 : roffset = 0;
1087 : }
1088 :
1089 : /* For each variable j in delta (Sol(y)), add
1090 : an edge in the graph from j to x, and union Sol(j) into Sol(x). */
1091 309489944 : EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1092 : {
1093 241733276 : varinfo_t v = get_varinfo (j);
1094 241733276 : HOST_WIDE_INT fieldoffset = v->offset + roffset;
1095 241733276 : unsigned HOST_WIDE_INT size = v->size;
1096 241733276 : unsigned int t;
1097 :
1098 241733276 : if (v->is_full_var)
1099 : ;
1100 145254205 : else if (roffset != 0)
1101 : {
1102 5923600 : if (fieldoffset < 0)
1103 133878 : v = get_varinfo (v->head);
1104 : else
1105 5789722 : v = first_or_preceding_vi_for_offset (v, fieldoffset);
1106 : }
1107 :
1108 : /* We have to include all fields that overlap the current field
1109 : shifted by roffset. */
1110 243666306 : do
1111 : {
1112 243666306 : t = find (v->id);
1113 :
1114 243666306 : flag |= solve_add_graph_edge (graph, lhs, t);
1115 :
1116 243666306 : if (v->is_full_var
1117 147187043 : || v->next == 0)
1118 : break;
1119 :
1120 120303418 : v = vi_next (v);
1121 : }
1122 120303418 : while (v->offset < fieldoffset + size);
1123 : }
1124 :
1125 67756668 : done:
1126 : /* If the LHS solution changed, mark the var as changed. */
1127 68221234 : if (flag)
1128 27489657 : bitmap_set_bit (changed, lhs);
1129 68221234 : }
1130 :
1131 : /* Process a constraint C that represents *(x + off) = y using DELTA
1132 : as the starting solution for x. */
1133 :
1134 : static void
1135 55564369 : do_ds_constraint (constraint_t c, bitmap delta, bitmap *expanded_delta)
1136 : {
1137 55564369 : unsigned int rhs = c->rhs.var;
1138 55564369 : bitmap sol = get_varinfo (rhs)->solution;
1139 55564369 : unsigned int j;
1140 55564369 : bitmap_iterator bi;
1141 55564369 : HOST_WIDE_INT loff = c->lhs.offset;
1142 55564369 : bool escaped_p = false;
1143 :
1144 : /* Our IL does not allow this. */
1145 55564369 : gcc_checking_assert (c->rhs.offset == 0);
1146 :
1147 : /* If the solution of y contains ANYTHING simply use the ANYTHING
1148 : solution. This avoids needlessly increasing the points-to sets. */
1149 55564369 : if (bitmap_bit_p (sol, anything_id))
1150 346355 : sol = get_varinfo (find (anything_id))->solution;
1151 :
1152 : /* If the solution for x contains ANYTHING we have to merge the
1153 : solution of y into all pointer variables which we do via
1154 : STOREDANYTHING. */
1155 55564369 : if (bitmap_bit_p (delta, anything_id))
1156 : {
1157 376714 : unsigned t = find (storedanything_id);
1158 376714 : if (solve_add_graph_edge (graph, t, rhs))
1159 34418 : bitmap_set_bit (changed, t);
1160 376714 : return;
1161 : }
1162 :
1163 : /* If we do not know at with offset the rhs is dereferenced compute
1164 : the reachability set of DELTA, conservatively assuming it is
1165 : dereferenced at all valid offsets. */
1166 55187655 : if (loff == UNKNOWN_OFFSET)
1167 : {
1168 2064915 : delta = solution_set_expand (delta, expanded_delta);
1169 2064915 : loff = 0;
1170 : }
1171 :
1172 : /* For each member j of delta (Sol(x)), add an edge from y to j and
1173 : union Sol(y) into Sol(j) */
1174 271379912 : EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1175 : {
1176 216192257 : varinfo_t v = get_varinfo (j);
1177 216192257 : unsigned int t;
1178 216192257 : HOST_WIDE_INT fieldoffset = v->offset + loff;
1179 216192257 : unsigned HOST_WIDE_INT size = v->size;
1180 :
1181 216192257 : if (v->is_full_var)
1182 : ;
1183 132971731 : else if (loff != 0)
1184 : {
1185 8195170 : if (fieldoffset < 0)
1186 3884 : v = get_varinfo (v->head);
1187 : else
1188 8191286 : v = first_or_preceding_vi_for_offset (v, fieldoffset);
1189 : }
1190 :
1191 : /* We have to include all fields that overlap the current field
1192 : shifted by loff. */
1193 218621033 : do
1194 : {
1195 218621033 : if (v->may_have_pointers)
1196 : {
1197 : /* If v is a global variable then this is an escape point. */
1198 206343757 : if (v->is_global_var
1199 154880753 : && !escaped_p)
1200 : {
1201 44081075 : t = find (escaped_id);
1202 44081075 : if (add_graph_edge (graph, t, rhs)
1203 57564582 : && bitmap_ior_into (get_varinfo (t)->solution, sol))
1204 1341362 : bitmap_set_bit (changed, t);
1205 : /* Enough to let rhs escape once. */
1206 : escaped_p = true;
1207 : }
1208 :
1209 206343757 : if (v->is_special_var)
1210 : break;
1211 :
1212 180550339 : t = find (v->id);
1213 :
1214 180550339 : if (solve_add_graph_edge (graph, t, rhs))
1215 12340909 : bitmap_set_bit (changed, t);
1216 : }
1217 :
1218 192827615 : if (v->is_full_var
1219 135400365 : || v->next == 0)
1220 : break;
1221 :
1222 110754626 : v = vi_next (v);
1223 : }
1224 110754626 : while (v->offset < fieldoffset + size);
1225 : }
1226 : }
1227 :
1228 : /* Handle a non-simple (simple meaning requires no iteration),
1229 : constraint (IE *x = &y, x = *y, *x = y, and x = y with offsets involved). */
1230 :
1231 : static void
1232 207452778 : do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta,
1233 : bitmap *expanded_delta)
1234 : {
1235 207452778 : if (c->lhs.type == DEREF)
1236 : {
1237 55564369 : if (c->rhs.type == ADDRESSOF)
1238 : {
1239 0 : gcc_unreachable ();
1240 : }
1241 : else
1242 : {
1243 : /* *x = y */
1244 55564369 : do_ds_constraint (c, delta, expanded_delta);
1245 : }
1246 : }
1247 151888409 : else if (c->rhs.type == DEREF)
1248 : {
1249 : /* x = *y */
1250 68221234 : if (!(get_varinfo (c->lhs.var)->is_special_var))
1251 68221234 : do_sd_constraint (graph, c, delta, expanded_delta);
1252 : }
1253 : else
1254 : {
1255 83667175 : bitmap tmp;
1256 83667175 : bool flag = false;
1257 :
1258 83667175 : gcc_checking_assert (c->rhs.type == SCALAR && c->lhs.type == SCALAR
1259 : && c->rhs.offset != 0 && c->lhs.offset == 0);
1260 83667175 : tmp = get_varinfo (c->lhs.var)->solution;
1261 :
1262 83667175 : flag = set_union_with_increment (tmp, delta, c->rhs.offset,
1263 : expanded_delta);
1264 :
1265 83667175 : if (flag)
1266 20685605 : bitmap_set_bit (changed, c->lhs.var);
1267 : }
1268 207452778 : }
1269 :
1270 : /* Initialize and return a new SCC info structure. */
1271 :
1272 8822188 : scc_info::scc_info (size_t size) :
1273 8822188 : visited (size), deleted (size), current_index (0), scc_stack (1)
1274 : {
1275 8822188 : bitmap_clear (visited);
1276 8822188 : bitmap_clear (deleted);
1277 8822188 : node_mapping = XNEWVEC (unsigned int, size);
1278 8822188 : dfs = XCNEWVEC (unsigned int, size);
1279 :
1280 906637660 : for (size_t i = 0; i < size; i++)
1281 897815472 : node_mapping[i] = i;
1282 8822188 : }
1283 :
1284 : /* Free an SCC info structure pointed to by SI. */
1285 :
1286 8822188 : scc_info::~scc_info ()
1287 : {
1288 8822188 : free (node_mapping);
1289 8822188 : free (dfs);
1290 8822188 : }
1291 :
1292 :
1293 : /* Find indirect cycles in GRAPH that occur, using strongly connected
1294 : components, and note them in the indirect cycles map.
1295 :
1296 : This technique comes from Ben Hardekopf and Calvin Lin,
1297 : "It Pays to be Lazy: Fast and Accurate Pointer Analysis for Millions of
1298 : Lines of Code", submitted to PLDI 2007. */
1299 :
1300 : static void
1301 4411094 : find_indirect_cycles (constraint_graph_t graph)
1302 : {
1303 4411094 : unsigned int i;
1304 4411094 : unsigned int size = graph->size;
1305 4411094 : scc_info si (size);
1306 :
1307 902226566 : for (i = 0; i < MIN (LAST_REF_NODE, size); i++)
1308 444496642 : if (!bitmap_bit_p (si.visited, i) && find (i) == i)
1309 227837692 : scc_visit (graph, &si, i);
1310 4411094 : }
1311 :
1312 : /* Visit the graph in topological order starting at node N, and store the
1313 : order in TOPO_ORDER using VISITED to indicate visited nodes. */
1314 :
1315 : static void
1316 380960349 : topo_visit (constraint_graph_t graph, vec<unsigned> &topo_order,
1317 : sbitmap visited, unsigned int n)
1318 : {
1319 380960349 : bitmap_iterator bi;
1320 380960349 : unsigned int j;
1321 :
1322 380960349 : bitmap_set_bit (visited, n);
1323 :
1324 380960349 : if (graph->succs[n])
1325 925157307 : EXECUTE_IF_SET_IN_BITMAP (graph->succs[n], 0, j, bi)
1326 : {
1327 729951172 : unsigned k = find (j);
1328 729951172 : if (!bitmap_bit_p (visited, k))
1329 277853538 : topo_visit (graph, topo_order, visited, k);
1330 : }
1331 :
1332 : /* Also consider copy with offset complex constraints as implicit edges. */
1333 814222251 : for (auto c : graph->complex[n])
1334 : {
1335 : /* Constraints are ordered so that SCALAR = SCALAR appear first. */
1336 251643113 : if (c->lhs.type != SCALAR || c->rhs.type != SCALAR)
1337 : break;
1338 140461502 : gcc_checking_assert (c->rhs.var == n);
1339 140461502 : unsigned k = find (c->lhs.var);
1340 140461502 : if (!bitmap_bit_p (visited, k))
1341 36318409 : topo_visit (graph, topo_order, visited, k);
1342 : }
1343 :
1344 380960349 : topo_order.quick_push (n);
1345 380960349 : }
1346 :
1347 : /* Compute a topological ordering for GRAPH, and return the result. */
1348 :
1349 : static auto_vec<unsigned>
1350 7812564 : compute_topo_order (constraint_graph_t graph)
1351 : {
1352 7812564 : unsigned int i;
1353 7812564 : unsigned int size = graph->size;
1354 :
1355 7812564 : auto_sbitmap visited (size);
1356 7812564 : bitmap_clear (visited);
1357 :
1358 : /* For the heuristic in add_graph_edge to work optimally make sure to
1359 : first visit the connected component of the graph containing
1360 : ESCAPED. Do this by extracting the connected component
1361 : with ESCAPED and append that to all other components as solve_graph
1362 : pops from the order. */
1363 7812564 : auto_vec<unsigned> tail (size);
1364 7812564 : topo_visit (graph, tail, visited, find (escaped_id));
1365 :
1366 7812564 : auto_vec<unsigned> topo_order (size);
1367 :
1368 579290648 : for (i = 0; i != size; ++i)
1369 563665520 : if (!bitmap_bit_p (visited, i) && find (i) == i)
1370 58975838 : topo_visit (graph, topo_order, visited, i);
1371 :
1372 7812564 : topo_order.splice (tail);
1373 7812564 : return topo_order;
1374 7812564 : }
1375 :
1376 : /* Structure used to for hash value numbering of pointer equivalence
1377 : classes. */
1378 :
1379 : typedef struct equiv_class_label
1380 : {
1381 : hashval_t hashcode;
1382 : unsigned int equivalence_class;
1383 : bitmap labels;
1384 : } *equiv_class_label_t;
1385 : typedef const struct equiv_class_label *const_equiv_class_label_t;
1386 :
1387 : /* Equiv_class_label hashtable helpers. */
1388 :
1389 : struct equiv_class_hasher : nofree_ptr_hash <equiv_class_label>
1390 : {
1391 : static inline hashval_t hash (const equiv_class_label *);
1392 : static inline bool equal (const equiv_class_label *,
1393 : const equiv_class_label *);
1394 : };
1395 :
1396 : /* A hashtable for mapping a bitmap of labels->pointer equivalence
1397 : classes. */
1398 : static hash_table<equiv_class_hasher> *pointer_equiv_class_table;
1399 :
1400 : /* A hashtable for mapping a bitmap of labels->location equivalence
1401 : classes. */
1402 : static hash_table<equiv_class_hasher> *location_equiv_class_table;
1403 :
1404 : /* Hash function for a equiv_class_label_t. */
1405 :
1406 : inline hashval_t
1407 186127238 : equiv_class_hasher::hash (const equiv_class_label *ecl)
1408 : {
1409 186127238 : return ecl->hashcode;
1410 : }
1411 :
1412 : /* Equality function for two equiv_class_label_t's. */
1413 :
1414 : inline bool
1415 241412314 : equiv_class_hasher::equal (const equiv_class_label *eql1,
1416 : const equiv_class_label *eql2)
1417 : {
1418 241412314 : return (eql1->hashcode == eql2->hashcode
1419 241412314 : && bitmap_equal_p (eql1->labels, eql2->labels));
1420 : }
1421 :
1422 : struct obstack equiv_class_obstack;
1423 :
1424 : /* Lookup a equivalence class in TABLE by the bitmap of LABELS with
1425 : hash HAS it contains. Sets *REF_LABELS to the bitmap LABELS
1426 : is equivalent to. */
1427 :
1428 : static equiv_class_label *
1429 191987794 : equiv_class_lookup_or_add (hash_table<equiv_class_hasher> *table,
1430 : bitmap labels)
1431 : {
1432 191987794 : equiv_class_label **slot;
1433 191987794 : equiv_class_label ecl;
1434 :
1435 191987794 : ecl.labels = labels;
1436 191987794 : ecl.hashcode = bitmap_hash (labels);
1437 191987794 : slot = table->find_slot (&ecl, INSERT);
1438 191987794 : if (!*slot)
1439 : {
1440 160450305 : *slot = XOBNEW (&equiv_class_obstack, struct equiv_class_label);
1441 160450305 : (*slot)->labels = labels;
1442 160450305 : (*slot)->hashcode = ecl.hashcode;
1443 160450305 : (*slot)->equivalence_class = 0;
1444 : }
1445 :
1446 191987794 : return *slot;
1447 : }
1448 :
1449 :
1450 : /* Perform offline variable substitution.
1451 :
1452 : This is a worst case quadratic time way of identifying variables
1453 : that must have equivalent points-to sets, including those caused by
1454 : static cycles, and single entry subgraphs, in the constraint graph.
1455 :
1456 : The technique is described in "Exploiting Pointer and Location
1457 : Equivalence to Optimize Pointer Analysis. In the 14th International
1458 : Static Analysis Symposium (SAS), August 2007." It is known as the
1459 : "HU" algorithm, and is equivalent to value numbering the collapsed
1460 : constraint graph including evaluating unions.
1461 :
1462 : The general method of finding equivalence classes is as follows:
1463 : Add fake nodes (REF nodes) and edges for *a = b and a = *b constraints.
1464 : Initialize all non-REF nodes to be direct nodes.
1465 : For each constraint a = a U {b}, we set pts(a) = pts(a) u {fresh
1466 : variable}
1467 : For each constraint containing the dereference, we also do the same
1468 : thing.
1469 :
1470 : We then compute SCC's in the graph and unify nodes in the same SCC,
1471 : including pts sets.
1472 :
1473 : For each non-collapsed node x:
1474 : Visit all unvisited explicit incoming edges.
1475 : Ignoring all non-pointers, set pts(x) = Union of pts(a) for y
1476 : where y->x.
1477 : Lookup the equivalence class for pts(x).
1478 : If we found one, equivalence_class(x) = found class.
1479 : Otherwise, equivalence_class(x) = new class, and new_class is
1480 : added to the lookup table.
1481 :
1482 : All direct nodes with the same equivalence class can be replaced
1483 : with a single representative node.
1484 : All unlabeled nodes (label == 0) are not pointers and all edges
1485 : involving them can be eliminated.
1486 : We perform these optimizations during rewrite_constraints
1487 :
1488 : In addition to pointer equivalence class finding, we also perform
1489 : location equivalence class finding. This is the set of variables
1490 : that always appear together in points-to sets. We use this to
1491 : compress the size of the points-to sets. */
1492 :
1493 : /* Current maximum pointer equivalence class id. */
1494 : static int pointer_equiv_class;
1495 :
1496 : /* Current maximum location equivalence class id. */
1497 : static int location_equiv_class;
1498 :
1499 : /* Recursive routine to find strongly connected components in GRAPH,
1500 : and label it's nodes with DFS numbers. */
1501 :
1502 : static void
1503 262448663 : condense_visit (constraint_graph_t graph, class scc_info *si, unsigned int n)
1504 : {
1505 262448663 : unsigned int i;
1506 262448663 : bitmap_iterator bi;
1507 262448663 : unsigned int my_dfs;
1508 :
1509 262448663 : gcc_checking_assert (si->node_mapping[n] == n);
1510 262448663 : bitmap_set_bit (si->visited, n);
1511 262448663 : si->dfs[n] = si->current_index ++;
1512 262448663 : my_dfs = si->dfs[n];
1513 :
1514 : /* Visit all the successors. */
1515 481977685 : EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
1516 : {
1517 219529022 : unsigned int w = si->node_mapping[i];
1518 :
1519 219529022 : if (bitmap_bit_p (si->deleted, w))
1520 139457495 : continue;
1521 :
1522 80071527 : if (!bitmap_bit_p (si->visited, w))
1523 78625600 : condense_visit (graph, si, w);
1524 :
1525 80071527 : unsigned int t = si->node_mapping[w];
1526 80071527 : gcc_checking_assert (si->node_mapping[n] == n);
1527 80071527 : if (si->dfs[t] < si->dfs[n])
1528 2581018 : si->dfs[n] = si->dfs[t];
1529 : }
1530 :
1531 : /* Visit all the implicit predecessors. */
1532 320083220 : EXECUTE_IF_IN_NONNULL_BITMAP (graph->implicit_preds[n], 0, i, bi)
1533 : {
1534 57634557 : unsigned int w = si->node_mapping[i];
1535 :
1536 57634557 : if (bitmap_bit_p (si->deleted, w))
1537 19091006 : continue;
1538 :
1539 38543551 : if (!bitmap_bit_p (si->visited, w))
1540 33746166 : condense_visit (graph, si, w);
1541 :
1542 38543551 : unsigned int t = si->node_mapping[w];
1543 38543551 : gcc_assert (si->node_mapping[n] == n);
1544 38543551 : if (si->dfs[t] < si->dfs[n])
1545 8175006 : si->dfs[n] = si->dfs[t];
1546 : }
1547 :
1548 : /* See if any components have been identified. */
1549 262448663 : if (si->dfs[n] == my_dfs)
1550 : {
1551 251859046 : if (si->scc_stack.length () != 0
1552 251859046 : && si->dfs[si->scc_stack.last ()] >= my_dfs)
1553 : {
1554 : /* Find the first node of the SCC and do non-bitmap work. */
1555 : bool direct_p = true;
1556 : unsigned first = si->scc_stack.length ();
1557 10589617 : do
1558 : {
1559 10589617 : --first;
1560 10589617 : unsigned int w = si->scc_stack[first];
1561 10589617 : si->node_mapping[w] = n;
1562 10589617 : if (!bitmap_bit_p (graph->direct_nodes, w))
1563 8523702 : direct_p = false;
1564 : }
1565 : while (first > 0
1566 11923139 : && si->dfs[si->scc_stack[first - 1]] >= my_dfs);
1567 1333522 : if (!direct_p)
1568 845427 : bitmap_clear_bit (graph->direct_nodes, n);
1569 :
1570 : /* Want to reduce to node n, push that first. */
1571 1333522 : si->scc_stack.reserve (1);
1572 1333522 : si->scc_stack.quick_push (si->scc_stack[first]);
1573 1333522 : si->scc_stack[first] = n;
1574 :
1575 1333522 : unsigned scc_size = si->scc_stack.length () - first;
1576 1333522 : unsigned split = scc_size / 2;
1577 1333522 : unsigned carry = scc_size - split * 2;
1578 4673045 : while (split > 0)
1579 : {
1580 13929140 : for (unsigned i = 0; i < split; ++i)
1581 : {
1582 10589617 : unsigned a = si->scc_stack[first + i];
1583 10589617 : unsigned b = si->scc_stack[first + split + carry + i];
1584 :
1585 : /* Unify our nodes. */
1586 10589617 : if (graph->preds[b])
1587 : {
1588 4637234 : if (!graph->preds[a])
1589 960894 : std::swap (graph->preds[a], graph->preds[b]);
1590 : else
1591 3676340 : bitmap_ior_into_and_free (graph->preds[a],
1592 : &graph->preds[b]);
1593 : }
1594 10589617 : if (graph->implicit_preds[b])
1595 : {
1596 8428551 : if (!graph->implicit_preds[a])
1597 856976 : std::swap (graph->implicit_preds[a],
1598 : graph->implicit_preds[b]);
1599 : else
1600 7571575 : bitmap_ior_into_and_free (graph->implicit_preds[a],
1601 : &graph->implicit_preds[b]);
1602 : }
1603 10589617 : if (graph->points_to[b])
1604 : {
1605 517302 : if (!graph->points_to[a])
1606 228624 : std::swap (graph->points_to[a], graph->points_to[b]);
1607 : else
1608 288678 : bitmap_ior_into_and_free (graph->points_to[a],
1609 : &graph->points_to[b]);
1610 : }
1611 : }
1612 3339523 : unsigned remain = split + carry;
1613 3339523 : split = remain / 2;
1614 3339523 : carry = remain - split * 2;
1615 : }
1616 : /* Actually pop the SCC. */
1617 1333522 : si->scc_stack.truncate (first);
1618 : }
1619 251859046 : bitmap_set_bit (si->deleted, n);
1620 : }
1621 : else
1622 10589617 : si->scc_stack.safe_push (n);
1623 262448663 : }
1624 :
1625 : /* Label pointer equivalences.
1626 :
1627 : This performs a value numbering of the constraint graph to
1628 : discover which variables will always have the same points-to sets
1629 : under the current set of constraints.
1630 :
1631 : The way it value numbers is to store the set of points-to bits
1632 : generated by the constraints and graph edges. This is just used as a
1633 : hash and equality comparison. The *actual set of points-to bits* is
1634 : completely irrelevant, in that we don't care about being able to
1635 : extract them later.
1636 :
1637 : The equality values (currently bitmaps) just have to satisfy a few
1638 : constraints, the main ones being:
1639 : 1. The combining operation must be order independent.
1640 : 2. The end result of a given set of operations must be unique iff the
1641 : combination of input values is unique
1642 : 3. Hashable. */
1643 :
1644 : static void
1645 229117209 : label_visit (constraint_graph_t graph, class scc_info *si, unsigned int n)
1646 : {
1647 229117209 : unsigned int i, first_pred;
1648 229117209 : bitmap_iterator bi;
1649 :
1650 229117209 : bitmap_set_bit (si->visited, n);
1651 :
1652 : /* Label and union our incoming edges's points to sets. */
1653 229117209 : first_pred = -1U;
1654 443491158 : EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
1655 : {
1656 214373949 : unsigned int w = si->node_mapping[i];
1657 214373949 : if (!bitmap_bit_p (si->visited, w))
1658 74038867 : label_visit (graph, si, w);
1659 :
1660 : /* Skip unused edges. */
1661 214373949 : if (w == n || graph->pointer_label[w] == 0)
1662 5059951 : continue;
1663 :
1664 209313998 : if (graph->points_to[w])
1665 : {
1666 209313998 : if (!graph->points_to[n])
1667 : {
1668 145917452 : if (first_pred == -1U)
1669 : first_pred = w;
1670 : else
1671 : {
1672 40526981 : graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
1673 40526981 : bitmap_ior (graph->points_to[n],
1674 40526981 : graph->points_to[first_pred],
1675 40526981 : graph->points_to[w]);
1676 : }
1677 : }
1678 : else
1679 63396546 : bitmap_ior_into (graph->points_to[n], graph->points_to[w]);
1680 : }
1681 : }
1682 :
1683 : /* Indirect nodes get fresh variables and a new pointer equiv class. */
1684 229117209 : if (!bitmap_bit_p (graph->direct_nodes, n))
1685 : {
1686 111004659 : if (!graph->points_to[n])
1687 : {
1688 63944362 : graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
1689 63944362 : if (first_pred != -1U)
1690 25928695 : bitmap_copy (graph->points_to[n], graph->points_to[first_pred]);
1691 : }
1692 222009318 : bitmap_set_bit (graph->points_to[n], FIRST_REF_NODE + n);
1693 111004659 : graph->pointer_label[n] = pointer_equiv_class++;
1694 111004659 : equiv_class_label_t ecl;
1695 222009318 : ecl = equiv_class_lookup_or_add (pointer_equiv_class_table,
1696 111004659 : graph->points_to[n]);
1697 111004659 : ecl->equivalence_class = graph->pointer_label[n];
1698 169588266 : return;
1699 : }
1700 :
1701 : /* If there was only a single non-empty predecessor the pointer equiv
1702 : class is the same. */
1703 118112550 : if (!graph->points_to[n])
1704 : {
1705 58583607 : if (first_pred != -1U)
1706 : {
1707 38934795 : graph->pointer_label[n] = graph->pointer_label[first_pred];
1708 38934795 : graph->points_to[n] = graph->points_to[first_pred];
1709 : }
1710 58583607 : return;
1711 : }
1712 :
1713 59528943 : if (!bitmap_empty_p (graph->points_to[n]))
1714 : {
1715 59528943 : equiv_class_label_t ecl;
1716 59528943 : ecl = equiv_class_lookup_or_add (pointer_equiv_class_table,
1717 : graph->points_to[n]);
1718 59528943 : if (ecl->equivalence_class == 0)
1719 28436349 : ecl->equivalence_class = pointer_equiv_class++;
1720 : else
1721 : {
1722 31092594 : BITMAP_FREE (graph->points_to[n]);
1723 31092594 : graph->points_to[n] = ecl->labels;
1724 : }
1725 59528943 : graph->pointer_label[n] = ecl->equivalence_class;
1726 : }
1727 : }
1728 :
1729 : /* Print the pred graph in dot format. */
1730 :
1731 : static void
1732 3 : dump_pred_graph (class scc_info *si, FILE *file)
1733 : {
1734 3 : unsigned int i;
1735 :
1736 : /* Only print the graph if it has already been initialized: */
1737 3 : if (!graph)
1738 : return;
1739 :
1740 : /* Prints the header of the dot file: */
1741 3 : fprintf (file, "strict digraph {\n");
1742 3 : fprintf (file, " node [\n shape = box\n ]\n");
1743 3 : fprintf (file, " edge [\n fontsize = \"12\"\n ]\n");
1744 3 : fprintf (file, "\n // List of nodes and complex constraints in "
1745 : "the constraint graph:\n");
1746 :
1747 : /* The next lines print the nodes in the graph together with the
1748 : complex constraints attached to them. */
1749 80 : for (i = 1; i < graph->size; i++)
1750 : {
1751 154 : if (i == FIRST_REF_NODE)
1752 3 : continue;
1753 74 : if (si->node_mapping[i] != i)
1754 0 : continue;
1755 74 : if (i < FIRST_REF_NODE)
1756 37 : fprintf (file, "\"%s\"", get_varinfo (i)->name);
1757 : else
1758 37 : fprintf (file, "\"*%s\"", get_varinfo (i - FIRST_REF_NODE)->name);
1759 74 : if (graph->points_to[i]
1760 74 : && !bitmap_empty_p (graph->points_to[i]))
1761 : {
1762 11 : if (i < FIRST_REF_NODE)
1763 11 : fprintf (file, "[label=\"%s = {", get_varinfo (i)->name);
1764 : else
1765 0 : fprintf (file, "[label=\"*%s = {",
1766 0 : get_varinfo (i - FIRST_REF_NODE)->name);
1767 11 : unsigned j;
1768 11 : bitmap_iterator bi;
1769 25 : EXECUTE_IF_SET_IN_BITMAP (graph->points_to[i], 0, j, bi)
1770 14 : fprintf (file, " %d", j);
1771 11 : fprintf (file, " }\"]");
1772 : }
1773 74 : fprintf (file, ";\n");
1774 : }
1775 :
1776 : /* Go over the edges. */
1777 3 : fprintf (file, "\n // Edges in the constraint graph:\n");
1778 80 : for (i = 1; i < graph->size; i++)
1779 : {
1780 77 : unsigned j;
1781 77 : bitmap_iterator bi;
1782 77 : if (si->node_mapping[i] != i)
1783 0 : continue;
1784 92 : EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[i], 0, j, bi)
1785 : {
1786 15 : unsigned from = si->node_mapping[j];
1787 15 : if (from < FIRST_REF_NODE)
1788 7 : fprintf (file, "\"%s\"", get_varinfo (from)->name);
1789 : else
1790 8 : fprintf (file, "\"*%s\"",
1791 8 : get_varinfo (from - FIRST_REF_NODE)->name);
1792 15 : fprintf (file, " -> ");
1793 15 : if (i < FIRST_REF_NODE)
1794 11 : fprintf (file, "\"%s\"", get_varinfo (i)->name);
1795 : else
1796 8 : fprintf (file, "\"*%s\"", get_varinfo (i - FIRST_REF_NODE)->name);
1797 15 : fprintf (file, ";\n");
1798 : }
1799 : }
1800 :
1801 : /* Prints the tail of the dot file. */
1802 3 : fprintf (file, "}\n");
1803 : }
1804 :
1805 : /* Perform offline variable substitution, discovering equivalence
1806 : classes, and eliminating non-pointer variables. */
1807 :
1808 : static class scc_info *
1809 4411094 : perform_var_substitution (constraint_graph_t graph)
1810 : {
1811 4411094 : unsigned int i;
1812 4411094 : unsigned int size = graph->size;
1813 4411094 : scc_info *si = new scc_info (size);
1814 :
1815 4411094 : bitmap_obstack_initialize (&iteration_obstack);
1816 4411094 : gcc_obstack_init (&equiv_class_obstack);
1817 4411094 : pointer_equiv_class_table = new hash_table<equiv_class_hasher> (511);
1818 4411094 : location_equiv_class_table
1819 4411094 : = new hash_table<equiv_class_hasher> (511);
1820 4411094 : pointer_equiv_class = 1;
1821 4411094 : location_equiv_class = 1;
1822 :
1823 : /* Condense the nodes, which means to find SCC's, count incoming
1824 : predecessors, and unite nodes in SCC's. */
1825 224453868 : for (i = 1; i < FIRST_REF_NODE; i++)
1826 220042774 : if (!bitmap_bit_p (si->visited, si->node_mapping[i]))
1827 150076897 : condense_visit (graph, si, si->node_mapping[i]);
1828 :
1829 4411094 : if (dump_file && (dump_flags & TDF_GRAPH))
1830 : {
1831 3 : fprintf (dump_file, "\n\n// The constraint graph before var-substitution "
1832 : "in dot format:\n");
1833 3 : dump_pred_graph (si, dump_file);
1834 3 : fprintf (dump_file, "\n\n");
1835 : }
1836 :
1837 4411094 : bitmap_clear (si->visited);
1838 : /* Actually the label the nodes for pointer equivalences. */
1839 453318830 : for (i = 1; i < FIRST_REF_NODE; i++)
1840 220042774 : if (!bitmap_bit_p (si->visited, si->node_mapping[i]))
1841 155078342 : label_visit (graph, si, si->node_mapping[i]);
1842 :
1843 : /* Calculate location equivalence labels. */
1844 224453868 : for (i = 1; i < FIRST_REF_NODE; i++)
1845 : {
1846 220042774 : bitmap pointed_by;
1847 220042774 : bitmap_iterator bi;
1848 220042774 : unsigned int j;
1849 :
1850 220042774 : if (!graph->pointed_by[i])
1851 198588582 : continue;
1852 21454192 : pointed_by = BITMAP_ALLOC (&iteration_obstack);
1853 :
1854 : /* Translate the pointed-by mapping for pointer equivalence
1855 : labels. */
1856 96658856 : EXECUTE_IF_SET_IN_BITMAP (graph->pointed_by[i], 0, j, bi)
1857 : {
1858 75204664 : bitmap_set_bit (pointed_by,
1859 75204664 : graph->pointer_label[si->node_mapping[j]]);
1860 : }
1861 : /* The original pointed_by is now dead. */
1862 21454192 : BITMAP_FREE (graph->pointed_by[i]);
1863 :
1864 : /* Look up the location equivalence label if one exists, or make
1865 : one otherwise. */
1866 21454192 : equiv_class_label_t ecl;
1867 21454192 : ecl = equiv_class_lookup_or_add (location_equiv_class_table, pointed_by);
1868 21454192 : if (ecl->equivalence_class == 0)
1869 21009297 : ecl->equivalence_class = location_equiv_class++;
1870 : else
1871 : {
1872 444895 : if (dump_file && (dump_flags & TDF_DETAILS))
1873 54 : fprintf (dump_file, "Found location equivalence for node %s\n",
1874 54 : get_varinfo (i)->name);
1875 444895 : BITMAP_FREE (pointed_by);
1876 : }
1877 21454192 : graph->loc_label[i] = ecl->equivalence_class;
1878 :
1879 : }
1880 :
1881 4411094 : if (dump_file && (dump_flags & TDF_DETAILS))
1882 6826 : for (i = 1; i < FIRST_REF_NODE; i++)
1883 : {
1884 6523 : unsigned j = si->node_mapping[i];
1885 6523 : if (j != i)
1886 : {
1887 21 : fprintf (dump_file, "%s node id %d ",
1888 21 : bitmap_bit_p (graph->direct_nodes, i)
1889 : ? "Direct" : "Indirect", i);
1890 21 : if (i < FIRST_REF_NODE)
1891 21 : fprintf (dump_file, "\"%s\"", get_varinfo (i)->name);
1892 : else
1893 0 : fprintf (dump_file, "\"*%s\"",
1894 0 : get_varinfo (i - FIRST_REF_NODE)->name);
1895 21 : fprintf (dump_file, " mapped to SCC leader node id %d ", j);
1896 21 : if (j < FIRST_REF_NODE)
1897 21 : fprintf (dump_file, "\"%s\"\n", get_varinfo (j)->name);
1898 : else
1899 0 : fprintf (dump_file, "\"*%s\"\n",
1900 0 : get_varinfo (j - FIRST_REF_NODE)->name);
1901 : }
1902 : else
1903 : {
1904 10019 : fprintf (dump_file,
1905 : "Equivalence classes for %s node id %d ",
1906 6502 : bitmap_bit_p (graph->direct_nodes, i)
1907 : ? "direct" : "indirect", i);
1908 6502 : if (i < FIRST_REF_NODE)
1909 6502 : fprintf (dump_file, "\"%s\"", get_varinfo (i)->name);
1910 : else
1911 0 : fprintf (dump_file, "\"*%s\"",
1912 0 : get_varinfo (i - FIRST_REF_NODE)->name);
1913 6502 : fprintf (dump_file,
1914 : ": pointer %d, location %d\n",
1915 6502 : graph->pointer_label[i], graph->loc_label[i]);
1916 : }
1917 : }
1918 :
1919 : /* Quickly eliminate our non-pointer variables. */
1920 :
1921 224453868 : for (i = 1; i < FIRST_REF_NODE; i++)
1922 : {
1923 220042774 : unsigned int node = si->node_mapping[i];
1924 :
1925 220042774 : if (graph->pointer_label[node] == 0)
1926 : {
1927 19650249 : if (dump_file && (dump_flags & TDF_DETAILS))
1928 928 : fprintf (dump_file,
1929 : "%s is a non-pointer variable, eliminating edges.\n",
1930 928 : get_varinfo (node)->name);
1931 19650249 : stats.nonpointer_vars++;
1932 19650249 : clear_edges_for_node (graph, node);
1933 : }
1934 : }
1935 :
1936 4411094 : return si;
1937 : }
1938 :
1939 : /* Free information that was only necessary for variable
1940 : substitution. */
1941 :
1942 : static void
1943 4411094 : free_var_substitution_info (class scc_info *si)
1944 : {
1945 4411094 : delete si;
1946 4411094 : free (graph->pointer_label);
1947 4411094 : free (graph->loc_label);
1948 4411094 : free (graph->pointed_by);
1949 4411094 : free (graph->points_to);
1950 4411094 : free (graph->eq_rep);
1951 4411094 : sbitmap_free (graph->direct_nodes);
1952 4411094 : delete pointer_equiv_class_table;
1953 4411094 : pointer_equiv_class_table = NULL;
1954 4411094 : delete location_equiv_class_table;
1955 4411094 : location_equiv_class_table = NULL;
1956 4411094 : obstack_free (&equiv_class_obstack, NULL);
1957 4411094 : bitmap_obstack_release (&iteration_obstack);
1958 4411094 : }
1959 :
1960 : /* Return an existing node that is equivalent to NODE, which has
1961 : equivalence class LABEL, if one exists. Return NODE otherwise. */
1962 :
1963 : static unsigned int
1964 863040534 : find_equivalent_node (constraint_graph_t graph,
1965 : unsigned int node, unsigned int label)
1966 : {
1967 : /* If the address version of this variable is unused, we can
1968 : substitute it for anything else with the same label.
1969 : Otherwise, we know the pointers are equivalent, but not the
1970 : locations, and we can unite them later. */
1971 :
1972 863040534 : if (!bitmap_bit_p (graph->address_taken, node))
1973 : {
1974 670713333 : gcc_checking_assert (label < graph->size);
1975 :
1976 670713333 : if (graph->eq_rep[label] != -1)
1977 : {
1978 : /* Unify the two variables since we know they are equivalent. */
1979 567759170 : if (unite (graph->eq_rep[label], node))
1980 66943039 : unify_nodes (graph, graph->eq_rep[label], node, false);
1981 567759170 : return graph->eq_rep[label];
1982 : }
1983 : else
1984 : {
1985 102954163 : graph->eq_rep[label] = node;
1986 102954163 : graph->pe_rep[label] = node;
1987 : }
1988 : }
1989 : else
1990 : {
1991 192327201 : gcc_checking_assert (label < graph->size);
1992 192327201 : graph->pe[node] = label;
1993 192327201 : if (graph->pe_rep[label] == -1)
1994 21364245 : graph->pe_rep[label] = node;
1995 : }
1996 :
1997 : return node;
1998 : }
1999 :
2000 : /* Unite pointer equivalent but not location equivalent nodes in
2001 : GRAPH. This may only be performed once variable substitution is
2002 : finished. */
2003 :
2004 : static void
2005 4411094 : unite_pointer_equivalences (constraint_graph_t graph)
2006 : {
2007 4411094 : unsigned int i;
2008 :
2009 : /* Go through the pointer equivalences and unite them to their
2010 : representative, if they aren't already. */
2011 224453868 : for (i = 1; i < FIRST_REF_NODE; i++)
2012 : {
2013 220042774 : unsigned int label = graph->pe[i];
2014 220042774 : if (label)
2015 : {
2016 21454192 : int label_rep = graph->pe_rep[label];
2017 :
2018 21454192 : if (label_rep == -1)
2019 0 : continue;
2020 :
2021 21454192 : label_rep = find (label_rep);
2022 21454192 : if (label_rep >= 0 && unite (label_rep, find (i)))
2023 2254985 : unify_nodes (graph, label_rep, i, false);
2024 : }
2025 : }
2026 4411094 : }
2027 :
2028 : /* Move complex constraints to the GRAPH nodes they belong to. */
2029 :
2030 : static void
2031 4411094 : move_complex_constraints (constraint_graph_t graph)
2032 : {
2033 4411094 : int i;
2034 4411094 : constraint_t c;
2035 :
2036 438334715 : FOR_EACH_VEC_ELT (constraints, i, c)
2037 : {
2038 433923621 : if (c)
2039 : {
2040 431520267 : struct constraint_expr lhs = c->lhs;
2041 431520267 : struct constraint_expr rhs = c->rhs;
2042 :
2043 431520267 : if (lhs.type == DEREF)
2044 : {
2045 35652946 : insert_into_complex (graph, lhs.var, c);
2046 : }
2047 395867321 : else if (rhs.type == DEREF)
2048 : {
2049 47874430 : if (!(get_varinfo (lhs.var)->is_special_var))
2050 47874424 : insert_into_complex (graph, rhs.var, c);
2051 : }
2052 347992891 : else if (rhs.type != ADDRESSOF && lhs.var > anything_id
2053 258444250 : && (lhs.offset != 0 || rhs.offset != 0))
2054 : {
2055 59677438 : insert_into_complex (graph, rhs.var, c);
2056 : }
2057 : }
2058 : }
2059 4411094 : }
2060 :
2061 : /* Optimize and rewrite complex constraints while performing
2062 : collapsing of equivalent nodes. SI is the SCC_INFO that is the
2063 : result of perform_variable_substitution. */
2064 :
2065 : static void
2066 4411094 : rewrite_constraints (constraint_graph_t graph,
2067 : class scc_info *si)
2068 : {
2069 4411094 : int i;
2070 4411094 : constraint_t c;
2071 :
2072 4411094 : if (flag_checking)
2073 : {
2074 453315682 : for (unsigned int j = 0; j < graph->size; j++)
2075 448904648 : gcc_assert (find (j) == j);
2076 : }
2077 :
2078 438334715 : FOR_EACH_VEC_ELT (constraints, i, c)
2079 : {
2080 433923621 : struct constraint_expr lhs = c->lhs;
2081 433923621 : struct constraint_expr rhs = c->rhs;
2082 433923621 : unsigned int lhsvar = find (lhs.var);
2083 433923621 : unsigned int rhsvar = find (rhs.var);
2084 433923621 : unsigned int lhsnode, rhsnode;
2085 433923621 : unsigned int lhslabel, rhslabel;
2086 :
2087 433923621 : lhsnode = si->node_mapping[lhsvar];
2088 433923621 : rhsnode = si->node_mapping[rhsvar];
2089 433923621 : lhslabel = graph->pointer_label[lhsnode];
2090 433923621 : rhslabel = graph->pointer_label[rhsnode];
2091 :
2092 : /* See if it is really a non-pointer variable, and if so, ignore
2093 : the constraint. */
2094 433923621 : if (lhslabel == 0)
2095 : {
2096 733813 : if (dump_file && (dump_flags & TDF_DETAILS))
2097 : {
2098 :
2099 44 : fprintf (dump_file, "%s is a non-pointer variable, "
2100 : "ignoring constraint:",
2101 22 : get_varinfo (lhs.var)->name);
2102 22 : dump_constraint (dump_file, c);
2103 22 : fprintf (dump_file, "\n");
2104 : }
2105 733813 : constraints[i] = NULL;
2106 2403354 : continue;
2107 : }
2108 :
2109 433189808 : if (rhslabel == 0)
2110 : {
2111 1669541 : if (dump_file && (dump_flags & TDF_DETAILS))
2112 : {
2113 :
2114 88 : fprintf (dump_file, "%s is a non-pointer variable, "
2115 : "ignoring constraint:",
2116 44 : get_varinfo (rhs.var)->name);
2117 44 : dump_constraint (dump_file, c);
2118 44 : fprintf (dump_file, "\n");
2119 : }
2120 1669541 : constraints[i] = NULL;
2121 1669541 : continue;
2122 : }
2123 :
2124 431520267 : lhsvar = find_equivalent_node (graph, lhsvar, lhslabel);
2125 431520267 : rhsvar = find_equivalent_node (graph, rhsvar, rhslabel);
2126 431520267 : c->lhs.var = lhsvar;
2127 431520267 : c->rhs.var = rhsvar;
2128 : }
2129 4411094 : }
2130 :
2131 : /* Eliminate indirect cycles involving NODE. Return true if NODE was
2132 : part of an SCC, false otherwise. */
2133 :
2134 : static bool
2135 380652897 : eliminate_indirect_cycles (unsigned int node)
2136 : {
2137 380652897 : if (graph->indirect_cycles[node] != -1
2138 380967402 : && !bitmap_empty_p (get_varinfo (node)->solution))
2139 : {
2140 282893 : unsigned int i;
2141 282893 : auto_vec<unsigned> queue;
2142 282893 : int queuepos;
2143 282893 : unsigned int to = find (graph->indirect_cycles[node]);
2144 282893 : bitmap_iterator bi;
2145 :
2146 : /* We can't touch the solution set and call unify_nodes
2147 : at the same time, because unify_nodes is going to do
2148 : bitmap unions into it. */
2149 :
2150 1509499 : EXECUTE_IF_SET_IN_BITMAP (get_varinfo (node)->solution, 0, i, bi)
2151 : {
2152 1226606 : if (find (i) == i && i != to)
2153 : {
2154 337293 : if (unite (to, i))
2155 337293 : queue.safe_push (i);
2156 : }
2157 : }
2158 :
2159 337293 : for (queuepos = 0;
2160 620186 : queue.iterate (queuepos, &i);
2161 : queuepos++)
2162 : {
2163 337293 : unify_nodes (graph, to, i, true);
2164 : }
2165 282893 : return true;
2166 282893 : }
2167 : return false;
2168 : }
2169 :
2170 : /* Solve the constraint graph GRAPH using our worklist solver.
2171 : This is based on the PW* family of solvers from the "Efficient Field
2172 : Sensitive Pointer Analysis for C" paper.
2173 : It works by iterating over all the graph nodes, processing the complex
2174 : constraints and propagating the copy constraints, until everything stops
2175 : changed. This corresponds to steps 6-8 in the solving list given above. */
2176 :
2177 : static void
2178 4411094 : solve_graph (constraint_graph_t graph)
2179 : {
2180 4411094 : unsigned int size = graph->size;
2181 4411094 : unsigned int i;
2182 4411094 : bitmap pts;
2183 :
2184 4411094 : changed = BITMAP_ALLOC (NULL);
2185 :
2186 : /* Mark all initial non-collapsed nodes as changed. */
2187 224453868 : for (i = 1; i < size; i++)
2188 : {
2189 220042774 : varinfo_t ivi = get_varinfo (i);
2190 370868915 : if (find (i) == i && !bitmap_empty_p (ivi->solution)
2191 272629677 : && ((graph->succs[i] && !bitmap_empty_p (graph->succs[i]))
2192 227902378 : || graph->complex[i].length () > 0))
2193 33539128 : bitmap_set_bit (changed, i);
2194 : }
2195 :
2196 : /* Allocate a bitmap to be used to store the changed bits. */
2197 4411094 : pts = BITMAP_ALLOC (&pta_obstack);
2198 :
2199 16634752 : while (!bitmap_empty_p (changed))
2200 : {
2201 7812564 : unsigned int i;
2202 7812564 : stats.iterations++;
2203 :
2204 7812564 : bitmap_obstack_initialize (&iteration_obstack);
2205 :
2206 7812564 : auto_vec<unsigned> topo_order = compute_topo_order (graph);
2207 396585477 : while (topo_order.length () != 0)
2208 : {
2209 380960349 : i = topo_order.pop ();
2210 :
2211 : /* If this variable is not a representative, skip it. */
2212 380960349 : if (find (i) != i)
2213 307452 : continue;
2214 :
2215 : /* In certain indirect cycle cases, we may merge this
2216 : variable to another. */
2217 380652897 : if (eliminate_indirect_cycles (i) && find (i) != i)
2218 90 : continue;
2219 :
2220 : /* If the node has changed, we need to process the
2221 : complex constraints and outgoing edges again. For complex
2222 : constraints that modify i itself, like the common group of
2223 : callarg = callarg + UNKNOWN;
2224 : callarg = *callarg + UNKNOWN;
2225 : *callarg = callescape;
2226 : make sure to iterate immediately because that maximizes
2227 : cache reuse and expands the graph quickest, leading to
2228 : better visitation order in the next iteration. */
2229 521534273 : while (bitmap_clear_bit (changed, i))
2230 : {
2231 141150374 : bitmap solution;
2232 141150374 : vec<constraint_t> &complex = graph->complex[i];
2233 141150374 : varinfo_t vi = get_varinfo (i);
2234 141150374 : bool solution_empty;
2235 :
2236 : /* Compute the changed set of solution bits. If anything
2237 : is in the solution just propagate that. */
2238 141150374 : if (bitmap_bit_p (vi->solution, anything_id))
2239 : {
2240 : /* If anything is also in the old solution there is
2241 : nothing to do.
2242 : ??? But we shouldn't ended up with "changed" set ... */
2243 2216489 : if (vi->oldsolution
2244 2216489 : && bitmap_bit_p (vi->oldsolution, anything_id))
2245 : break;
2246 1947581 : bitmap_copy (pts, get_varinfo (find (anything_id))->solution);
2247 : }
2248 138933885 : else if (vi->oldsolution)
2249 36170098 : bitmap_and_compl (pts, vi->solution, vi->oldsolution);
2250 : else
2251 102763787 : bitmap_copy (pts, vi->solution);
2252 :
2253 140881466 : if (bitmap_empty_p (pts))
2254 : break;
2255 :
2256 140881466 : if (vi->oldsolution)
2257 37033420 : bitmap_ior_into (vi->oldsolution, pts);
2258 : else
2259 : {
2260 103848046 : vi->oldsolution = BITMAP_ALLOC (&oldpta_obstack);
2261 103848046 : bitmap_copy (vi->oldsolution, pts);
2262 : }
2263 :
2264 140881466 : solution = vi->solution;
2265 140881466 : solution_empty = bitmap_empty_p (solution);
2266 :
2267 : /* Process the complex constraints. */
2268 140881466 : hash_set<constraint_t> *cvisited = nullptr;
2269 140881466 : if (flag_checking)
2270 140880781 : cvisited = new hash_set<constraint_t>;
2271 140881466 : bitmap expanded_pts = NULL;
2272 348607177 : for (unsigned j = 0; j < complex.length (); ++j)
2273 : {
2274 207725711 : constraint_t c = complex[j];
2275 : /* At unification time only the directly involved nodes
2276 : will get their complex constraints updated. Update
2277 : our complex constraints now but keep the constraint
2278 : vector sorted and clear of duplicates. Also make
2279 : sure to evaluate each prevailing constraint only once. */
2280 207725711 : unsigned int new_lhs = find (c->lhs.var);
2281 207725711 : unsigned int new_rhs = find (c->rhs.var);
2282 207725711 : if (c->lhs.var != new_lhs || c->rhs.var != new_rhs)
2283 : {
2284 1551375 : constraint tem = *c;
2285 1551375 : tem.lhs.var = new_lhs;
2286 1551375 : tem.rhs.var = new_rhs;
2287 1551375 : unsigned int place
2288 1551375 : = complex.lower_bound (&tem, constraint_less);
2289 1551375 : c->lhs.var = new_lhs;
2290 1551375 : c->rhs.var = new_rhs;
2291 1551375 : if (place != j)
2292 : {
2293 1538957 : complex.ordered_remove (j);
2294 1538957 : if (j < place)
2295 1521403 : --place;
2296 1538957 : if (place < complex.length ())
2297 : {
2298 324098 : if (constraint_equal (*complex[place], *c))
2299 : {
2300 35031 : j--;
2301 272933 : continue;
2302 : }
2303 : else
2304 289067 : complex.safe_insert (place, c);
2305 : }
2306 : else
2307 1214859 : complex.quick_push (c);
2308 1503926 : if (place > j)
2309 : {
2310 237902 : j--;
2311 237902 : continue;
2312 : }
2313 : }
2314 : }
2315 :
2316 : /* The only complex constraint that can change our
2317 : solution to non-empty, given an empty solution,
2318 : is a constraint where the lhs side is receiving
2319 : some set from elsewhere. */
2320 207452778 : if (cvisited && cvisited->add (c))
2321 0 : gcc_unreachable ();
2322 207452778 : if (!solution_empty || c->lhs.type != DEREF)
2323 207452778 : do_complex_constraint (graph, c, pts, &expanded_pts);
2324 : }
2325 140881466 : if (cvisited)
2326 : {
2327 : /* When checking, verify the order of constraints is
2328 : maintained and each constraint is evaluated exactly
2329 : once. */
2330 268007625 : for (unsigned j = 1; j < complex.length (); ++j)
2331 127126844 : gcc_assert (constraint_less (complex[j-1], complex[j]));
2332 221205655 : gcc_assert (cvisited->elements () == complex.length ());
2333 140880781 : delete cvisited;
2334 : }
2335 140881466 : BITMAP_FREE (expanded_pts);
2336 :
2337 140881466 : solution_empty = bitmap_empty_p (solution);
2338 :
2339 140881466 : if (!solution_empty)
2340 : {
2341 140881466 : bitmap_iterator bi;
2342 140881466 : unsigned eff_escaped_id = find (escaped_id);
2343 140881466 : unsigned j;
2344 :
2345 : /* Propagate solution to all successors. */
2346 140881466 : unsigned to_remove = ~0U;
2347 355571132 : EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i],
2348 : 0, j, bi)
2349 : {
2350 214689666 : if (to_remove != ~0U)
2351 : {
2352 2117213 : bitmap_clear_bit (graph->succs[i], to_remove);
2353 2117213 : to_remove = ~0U;
2354 : }
2355 214689666 : unsigned int to = find (j);
2356 214689666 : if (to != j)
2357 : {
2358 : /* Update the succ graph, avoiding duplicate
2359 : work. */
2360 2097929 : to_remove = j;
2361 2097929 : if (! bitmap_set_bit (graph->succs[i], to))
2362 869583 : continue;
2363 : /* We eventually end up processing 'to' twice
2364 : as it is undefined whether bitmap iteration
2365 : iterates over bits set during iteration.
2366 : Play safe instead of doing tricks. */
2367 : }
2368 : /* Don't try to propagate to ourselves. */
2369 213820083 : if (to == i)
2370 : {
2371 162896 : to_remove = j;
2372 162896 : continue;
2373 : }
2374 : /* Early node unification can lead to edges from
2375 : escaped - remove them. */
2376 213657187 : if (i == eff_escaped_id)
2377 : {
2378 159962 : to_remove = j;
2379 159962 : if (bitmap_set_bit (get_varinfo (to)->solution,
2380 : escaped_id))
2381 91161 : bitmap_set_bit (changed, to);
2382 159962 : continue;
2383 : }
2384 :
2385 213497225 : if (bitmap_ior_into (get_varinfo (to)->solution, pts))
2386 94697201 : bitmap_set_bit (changed, to);
2387 : }
2388 98913044 : if (to_remove != ~0U)
2389 210759 : bitmap_clear_bit (graph->succs[i], to_remove);
2390 : }
2391 : }
2392 : }
2393 7812564 : bitmap_obstack_release (&iteration_obstack);
2394 7812564 : }
2395 :
2396 4411094 : BITMAP_FREE (pts);
2397 4411094 : BITMAP_FREE (changed);
2398 4411094 : bitmap_obstack_release (&oldpta_obstack);
2399 4411094 : }
2400 :
2401 : void
2402 4411094 : delete_graph (void)
2403 : {
2404 4411094 : unsigned int i;
2405 228864962 : for (i = 0; i < graph->size; i++)
2406 224453868 : graph->complex[i].release ();
2407 4411094 : free (graph->complex);
2408 :
2409 4411094 : free (graph->succs);
2410 4411094 : free (graph->pe);
2411 4411094 : free (graph->pe_rep);
2412 4411094 : free (graph->indirect_cycles);
2413 : /* We are not doing free (graph->rep) since the representatives mapping is
2414 : needed outside of the solver too. */
2415 4411094 : free (graph);
2416 4411094 : }
2417 :
2418 : /* Remove the REF and ADDRESS edges from GRAPH, as well as all the
2419 : predecessor edges. */
2420 :
2421 : static void
2422 4411094 : remove_preds_and_fake_succs (constraint_graph_t graph)
2423 : {
2424 4411094 : unsigned int i;
2425 :
2426 : /* Clear the implicit ref and address nodes from the successor
2427 : lists. */
2428 224453868 : for (i = 1; i < FIRST_REF_NODE; i++)
2429 : {
2430 220042774 : if (graph->succs[i])
2431 64160887 : bitmap_clear_range (graph->succs[i], FIRST_REF_NODE,
2432 64160887 : FIRST_REF_NODE * 2);
2433 : }
2434 :
2435 : /* Free the successor list for the non-ref nodes. */
2436 228864962 : for (i = FIRST_REF_NODE + 1; i < graph->size; i++)
2437 : {
2438 220042774 : if (graph->succs[i])
2439 11739330 : BITMAP_FREE (graph->succs[i]);
2440 : }
2441 :
2442 : /* Now reallocate the size of the successor list as, and blow away
2443 : the predecessor bitmaps. */
2444 4411094 : graph->size = varmap.length ();
2445 4411094 : graph->succs = XRESIZEVEC (bitmap, graph->succs, graph->size);
2446 :
2447 4411094 : free (graph->implicit_preds);
2448 4411094 : graph->implicit_preds = NULL;
2449 4411094 : free (graph->preds);
2450 4411094 : graph->preds = NULL;
2451 4411094 : bitmap_obstack_release (&predbitmap_obstack);
2452 4411094 : }
2453 :
2454 : namespace pointer_analysis {
2455 :
2456 : /* Solve the constraint set. The entry function of the solver. */
2457 :
2458 : void
2459 4411094 : solve_constraints (void)
2460 : {
2461 4411094 : class scc_info *si;
2462 :
2463 : /* Sort varinfos so that ones that cannot be pointed to are last.
2464 : This makes bitmaps more efficient. */
2465 4411094 : unsigned int *map = XNEWVEC (unsigned int, varmap.length ());
2466 44110940 : for (unsigned i = 0; i < integer_id + 1; ++i)
2467 39699846 : map[i] = i;
2468 : /* Start with address-taken vars, followed by not address-taken vars
2469 : to move vars never appearing in the points-to solution bitmaps last. */
2470 : unsigned j = integer_id + 1;
2471 378330232 : for (unsigned i = integer_id + 1; i < varmap.length (); ++i)
2472 184754022 : if (varmap[varmap[i]->head]->address_taken)
2473 15246041 : map[i] = j++;
2474 189165116 : for (unsigned i = integer_id + 1; i < varmap.length (); ++i)
2475 184754022 : if (! varmap[varmap[i]->head]->address_taken)
2476 169507981 : map[i] = j++;
2477 : /* Shuffle varmap according to map. */
2478 189165116 : for (unsigned i = integer_id + 1; i < varmap.length (); ++i)
2479 : {
2480 274694220 : while (map[varmap[i]->id] != i)
2481 89940198 : std::swap (varmap[i], varmap[map[varmap[i]->id]]);
2482 184754022 : gcc_assert (bitmap_empty_p (varmap[i]->solution));
2483 184754022 : varmap[i]->id = i;
2484 184754022 : varmap[i]->next = map[varmap[i]->next];
2485 184754022 : varmap[i]->head = map[varmap[i]->head];
2486 : }
2487 : /* Finally rewrite constraints. */
2488 438334715 : for (unsigned i = 0; i < constraints.length (); ++i)
2489 : {
2490 433923621 : constraints[i]->lhs.var = map[constraints[i]->lhs.var];
2491 433923621 : constraints[i]->rhs.var = map[constraints[i]->rhs.var];
2492 : }
2493 4411094 : free (map);
2494 :
2495 4411094 : if (dump_file)
2496 484 : fprintf (dump_file,
2497 : "\nCollapsing static cycles and doing variable "
2498 : "substitution\n");
2499 :
2500 8822188 : init_graph (varmap.length () * 2);
2501 :
2502 4411094 : if (dump_file)
2503 484 : fprintf (dump_file, "Building predecessor graph\n");
2504 4411094 : build_pred_graph ();
2505 :
2506 4411094 : if (dump_file)
2507 484 : fprintf (dump_file, "Detecting pointer and location "
2508 : "equivalences\n");
2509 4411094 : si = perform_var_substitution (graph);
2510 :
2511 4411094 : if (dump_file)
2512 484 : fprintf (dump_file, "Rewriting constraints and unifying "
2513 : "variables\n");
2514 4411094 : rewrite_constraints (graph, si);
2515 :
2516 4411094 : build_succ_graph ();
2517 :
2518 4411094 : free_var_substitution_info (si);
2519 :
2520 : /* Attach complex constraints to graph nodes. */
2521 4411094 : move_complex_constraints (graph);
2522 :
2523 4411094 : if (dump_file)
2524 484 : fprintf (dump_file, "Uniting pointer but not location equivalent "
2525 : "variables\n");
2526 4411094 : unite_pointer_equivalences (graph);
2527 :
2528 4411094 : if (dump_file)
2529 484 : fprintf (dump_file, "Finding indirect cycles\n");
2530 4411094 : find_indirect_cycles (graph);
2531 :
2532 : /* Implicit nodes and predecessors are no longer necessary at this
2533 : point. */
2534 4411094 : remove_preds_and_fake_succs (graph);
2535 :
2536 4411094 : if (dump_file && (dump_flags & TDF_GRAPH))
2537 : {
2538 3 : fprintf (dump_file, "\n\n// The constraint graph before solve-graph "
2539 : "in dot format:\n");
2540 3 : dump_constraint_graph (dump_file);
2541 3 : fprintf (dump_file, "\n\n");
2542 : }
2543 :
2544 4411094 : if (dump_file)
2545 484 : fprintf (dump_file, "Solving graph\n");
2546 :
2547 4411094 : solve_graph (graph);
2548 :
2549 4411094 : if (dump_file && (dump_flags & TDF_GRAPH))
2550 : {
2551 3 : fprintf (dump_file, "\n\n// The constraint graph after solve-graph "
2552 : "in dot format:\n");
2553 3 : dump_constraint_graph (dump_file);
2554 3 : fprintf (dump_file, "\n\n");
2555 : }
2556 :
2557 : /* The mapping node -> representative is one of the outputs of the
2558 : solver. */
2559 4411094 : union_find_compress_all ();
2560 4411094 : var_rep = graph->rep;
2561 :
2562 4411094 : delete_graph ();
2563 4411094 : }
2564 :
2565 : } // namespace pointer_analysis
|
