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 9273931844 : find (unsigned int node)
136 : {
137 9273931844 : gcc_checking_assert (node < graph->size);
138 9273931844 : if (graph->rep[node] != node)
139 1049986764 : 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 591747803 : unite (unsigned int to, unsigned int from)
150 : {
151 591747803 : gcc_checking_assert (to < graph->size && from < graph->size);
152 591747803 : if (to != from && graph->rep[from] != to)
153 : {
154 69667372 : graph->rep[from] = to;
155 69667372 : 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 4415916 : union_find_compress_all (void)
165 : {
166 4415916 : unsigned int i;
167 229396132 : for (i = 0; i < graph->size; i++)
168 224980216 : find (i);
169 4415916 : }
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 19188668 : constraint_expr_equal (struct constraint_expr a, struct constraint_expr b)
288 : {
289 11981889 : 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 449382623 : constraint_expr_less (struct constraint_expr a, struct constraint_expr b)
298 : {
299 0 : if (a.type == b.type)
300 : {
301 268610025 : if (a.var == b.var)
302 201326930 : return a.offset < b.offset;
303 : else
304 67283095 : return a.var < b.var;
305 : }
306 : else
307 180772598 : 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 247255416 : constraint_less (const constraint_t &a, const constraint_t &b)
315 : {
316 494510832 : if (constraint_expr_less (a->lhs, b->lhs))
317 : return true;
318 213821300 : else if (constraint_expr_less (b->lhs, a->lhs))
319 : return false;
320 : else
321 95216557 : 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 12597130 : constraint_equal (const constraint &a, const constraint &b)
328 : {
329 19188668 : return constraint_expr_equal (a.lhs, b.lhs)
330 12597130 : && 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 265964 : constraint_vec_find (vec<constraint_t> vec,
337 : constraint &lookfor)
338 : {
339 265964 : unsigned int place;
340 265964 : constraint_t found;
341 :
342 265964 : if (!vec.exists ())
343 : return NULL;
344 :
345 212678 : place = vec.lower_bound (&lookfor, constraint_less);
346 212678 : if (place >= vec.length ())
347 : return NULL;
348 83446 : found = vec[place];
349 83446 : 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 69547016 : constraint_set_union (vec<constraint_t> *to,
359 : vec<constraint_t> *from)
360 : {
361 69547016 : int i;
362 69547016 : constraint_t c;
363 69547016 : bool any_change = false;
364 :
365 69812980 : FOR_EACH_VEC_ELT (*from, i, c)
366 : {
367 265964 : if (constraint_vec_find (*to, *c) == NULL)
368 : {
369 265481 : unsigned int place = to->lower_bound (c, constraint_less);
370 265481 : to->safe_insert (place, c);
371 265481 : any_change = true;
372 : }
373 : }
374 69547016 : return any_change;
375 : }
376 :
377 : /* Expands the solution in SET to all sub-fields of variables included. */
378 :
379 : static bitmap
380 134397636 : solution_set_expand (bitmap set, bitmap *expanded)
381 : {
382 134397636 : bitmap_iterator bi;
383 134397636 : unsigned j;
384 :
385 134397636 : if (*expanded)
386 : return *expanded;
387 :
388 74938141 : *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 74938141 : unsigned prev_head = 0;
393 294254207 : EXECUTE_IF_SET_IN_BITMAP (set, 0, j, bi)
394 : {
395 219316066 : varinfo_t v = get_varinfo (j);
396 219316066 : if (v->is_artificial_var
397 130662080 : || v->is_full_var)
398 109870160 : continue;
399 109445906 : if (v->head != prev_head)
400 : {
401 24609609 : varinfo_t head = get_varinfo (v->head);
402 24609609 : unsigned num = 1;
403 145992285 : for (varinfo_t n = vi_next (head); n != NULL; n = vi_next (n))
404 : {
405 121382676 : 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 17194 : bitmap_set_range (*expanded, head->id, num);
411 17194 : head = n;
412 17194 : num = 1;
413 : }
414 : else
415 121365482 : num++;
416 : }
417 :
418 24609609 : bitmap_set_range (*expanded, head->id, num);
419 24609609 : prev_head = v->head;
420 : }
421 : }
422 :
423 : /* And finally set the rest of the bits from SET in an efficient way. */
424 74938141 : bitmap_ior_into (*expanded, set);
425 :
426 74938141 : 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 83996388 : set_union_with_increment (bitmap to, bitmap delta, HOST_WIDE_INT inc,
434 : bitmap *expanded_delta)
435 : {
436 83996388 : bool changed = false;
437 83996388 : bitmap_iterator bi;
438 83996388 : unsigned int i;
439 :
440 : /* If the solution of DELTA contains anything it is good enough to transfer
441 : this to TO. */
442 83996388 : if (bitmap_bit_p (delta, anything_id))
443 1181147 : 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 82815241 : if (inc == UNKNOWN_OFFSET)
448 : {
449 81855057 : delta = solution_set_expand (delta, expanded_delta);
450 81855057 : changed |= bitmap_ior_into (to, delta);
451 81855057 : return changed;
452 : }
453 :
454 : /* For non-zero offset union the offsetted solution into the destination. */
455 4345780 : EXECUTE_IF_SET_IN_BITMAP (delta, 0, i, bi)
456 : {
457 3385596 : 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 3385596 : if (vi->is_artificial_var
462 2127492 : || vi->is_unknown_size_var
463 1943961 : || vi->is_full_var)
464 1669605 : changed |= bitmap_set_bit (to, i);
465 : else
466 : {
467 1715991 : HOST_WIDE_INT fieldoffset = vi->offset + inc;
468 1715991 : 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 1715991 : if (fieldoffset < 0)
473 62386 : vi = get_varinfo (vi->head);
474 : else
475 1653605 : vi = first_or_preceding_vi_for_offset (vi, fieldoffset);
476 :
477 2756651 : do
478 : {
479 2756651 : changed |= bitmap_set_bit (to, vi->id);
480 2756651 : if (vi->is_full_var
481 2756611 : || vi->next == 0)
482 : break;
483 :
484 : /* We have to include all fields that overlap the current field
485 : shifted by inc. */
486 1670188 : vi = vi_next (vi);
487 : }
488 1670188 : 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 143871550 : insert_into_complex (constraint_graph_t graph,
500 : unsigned int var, constraint_t c)
501 : {
502 143871550 : vec<constraint_t> complex = graph->complex[var];
503 143871550 : unsigned int place = complex.lower_bound (c, constraint_less);
504 :
505 : /* Only insert constraints that do not already exist. */
506 143871550 : if (place >= complex.length ()
507 98862729 : || !constraint_equal (*c, *complex[place]))
508 141912654 : graph->complex[var].safe_insert (place, c);
509 143871550 : }
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 69547016 : merge_node_constraints (constraint_graph_t graph, unsigned int to,
518 : unsigned int from)
519 : {
520 69547016 : unsigned int i;
521 69547016 : constraint_t c;
522 69547016 : bool any_change = false;
523 :
524 69547016 : gcc_checking_assert (find (from) == to);
525 :
526 : /* Move all complex constraints from src node into to node. */
527 69812980 : 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 265964 : if (c->rhs.type == DEREF)
534 87014 : c->rhs.var = to;
535 178950 : else if (c->lhs.type == DEREF)
536 87970 : c->lhs.var = to;
537 : else
538 90980 : c->rhs.var = to;
539 :
540 : }
541 69547016 : any_change = constraint_set_union (&graph->complex[to],
542 : &graph->complex[from]);
543 69547016 : graph->complex[from].release ();
544 69547016 : return any_change;
545 : }
546 :
547 : /* Remove edges involving NODE from GRAPH. */
548 :
549 : static void
550 89270388 : clear_edges_for_node (constraint_graph_t graph, unsigned int node)
551 : {
552 89270388 : if (graph->succs[node])
553 2420744 : BITMAP_FREE (graph->succs[node]);
554 89270388 : }
555 :
556 : /* Merge GRAPH nodes FROM and TO into node TO. */
557 :
558 : static void
559 69547016 : merge_graph_nodes (constraint_graph_t graph, unsigned int to,
560 : unsigned int from)
561 : {
562 69547016 : 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 117 : if (graph->indirect_cycles[to] == -1)
571 73 : graph->indirect_cycles[to] = graph->indirect_cycles[from];
572 : }
573 :
574 : /* Merge all the successor edges. */
575 69547016 : if (graph->succs[from])
576 : {
577 2420744 : if (!graph->succs[to])
578 1232286 : graph->succs[to] = BITMAP_ALLOC (&pta_obstack);
579 2420744 : bitmap_ior_into (graph->succs[to],
580 2420744 : graph->succs[from]);
581 : }
582 :
583 69547016 : clear_edges_for_node (graph, from);
584 69547016 : }
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 290074372 : add_implicit_graph_edge (constraint_graph_t graph, unsigned int to,
592 : unsigned int from)
593 : {
594 290074372 : if (to == from)
595 : return;
596 :
597 290074372 : if (!graph->implicit_preds[to])
598 162403278 : graph->implicit_preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
599 :
600 290074372 : if (bitmap_set_bit (graph->implicit_preds[to], from))
601 272749759 : 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 245171208 : add_pred_graph_edge (constraint_graph_t graph, unsigned int to,
610 : unsigned int from)
611 : {
612 245171208 : if (!graph->preds[to])
613 144481620 : graph->preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
614 245171208 : bitmap_set_bit (graph->preds[to], from);
615 245171208 : }
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 788308239 : add_graph_edge (constraint_graph_t graph, unsigned int to,
623 : unsigned int from)
624 : {
625 788308239 : if (to == from)
626 : {
627 : return false;
628 : }
629 : else
630 : {
631 787577261 : bool r = false;
632 :
633 787577261 : if (!graph->succs[from])
634 91734105 : 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 787577261 : if (to < FIRST_REF_NODE
647 756183991 : && bitmap_bit_p (graph->succs[from], find (escaped_id))
648 1150304682 : && bitmap_bit_p (get_varinfo (find (to))->solution, escaped_id))
649 : {
650 305170427 : stats.num_avoided_edges++;
651 305170427 : return false;
652 : }
653 :
654 482406834 : if (bitmap_set_bit (graph->succs[from], to))
655 : {
656 337868317 : r = true;
657 337868317 : if (to < FIRST_REF_NODE && from < FIRST_REF_NODE)
658 294459667 : stats.num_edges++;
659 : }
660 482406834 : return r;
661 : }
662 : }
663 :
664 : /* Initialize the constraint graph structure to contain SIZE nodes. */
665 :
666 : static void
667 4415916 : init_graph (unsigned int size)
668 : {
669 4415916 : unsigned int j;
670 :
671 4415916 : bitmap_obstack_initialize (&predbitmap_obstack);
672 :
673 4415916 : graph = XCNEW (struct constraint_graph);
674 4415916 : graph->size = size;
675 4415916 : graph->succs = XCNEWVEC (bitmap, graph->size);
676 4415916 : graph->indirect_cycles = XNEWVEC (int, graph->size);
677 4415916 : 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 4415916 : typedef vec<constraint_t> vec_constraint_t_heap;
681 4415916 : graph->complex = XCNEWVEC (vec_constraint_t_heap, size);
682 4415916 : graph->pe = XCNEWVEC (unsigned int, graph->size);
683 4415916 : graph->pe_rep = XNEWVEC (int, graph->size);
684 :
685 454376348 : for (j = 0; j < graph->size; j++)
686 : {
687 449960432 : graph->rep[j] = j;
688 449960432 : graph->pe_rep[j] = -1;
689 449960432 : graph->indirect_cycles[j] = -1;
690 : }
691 4415916 : }
692 :
693 : /* Build the constraint graph, adding only predecessor edges right now. */
694 :
695 : static void
696 4415916 : build_pred_graph (void)
697 : {
698 4415916 : int i;
699 4415916 : constraint_t c;
700 4415916 : unsigned int j;
701 :
702 4415916 : graph->implicit_preds = XCNEWVEC (bitmap, graph->size);
703 4415916 : graph->preds = XCNEWVEC (bitmap, graph->size);
704 4415916 : graph->pointer_label = XCNEWVEC (unsigned int, graph->size);
705 4415916 : graph->loc_label = XCNEWVEC (unsigned int, graph->size);
706 4415916 : graph->pointed_by = XCNEWVEC (bitmap, graph->size);
707 4415916 : graph->points_to = XCNEWVEC (bitmap, graph->size);
708 4415916 : graph->eq_rep = XNEWVEC (int, graph->size);
709 4415916 : graph->direct_nodes = sbitmap_alloc (graph->size);
710 4415916 : graph->address_taken = BITMAP_ALLOC (&predbitmap_obstack);
711 4415916 : bitmap_clear (graph->direct_nodes);
712 :
713 454376348 : for (j = 1; j < FIRST_REF_NODE; j++)
714 : {
715 220564300 : if (!get_varinfo (j)->is_special_var)
716 198484720 : bitmap_set_bit (graph->direct_nodes, j);
717 : }
718 :
719 454376348 : for (j = 0; j < graph->size; j++)
720 449960432 : graph->eq_rep[j] = -1;
721 :
722 458792264 : for (j = 0; j < varmap.length (); j++)
723 224980216 : graph->indirect_cycles[j] = -1;
724 :
725 439574561 : FOR_EACH_VEC_ELT (constraints, i, c)
726 : {
727 435158645 : struct constraint_expr lhs = c->lhs;
728 435158645 : struct constraint_expr rhs = c->rhs;
729 435158645 : unsigned int lhsvar = lhs.var;
730 435158645 : unsigned int rhsvar = rhs.var;
731 :
732 435158645 : if (lhs.type == DEREF)
733 : {
734 : /* *x = y. */
735 35732151 : if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
736 : {
737 31415715 : if (lhs.var == anything_id)
738 0 : add_pred_graph_edge (graph, storedanything_id, rhsvar);
739 : else
740 62831430 : add_pred_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
741 : }
742 : }
743 399426494 : else if (rhs.type == DEREF)
744 : {
745 : /* x = *y */
746 48255330 : if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
747 26094418 : add_pred_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
748 : else
749 35208121 : bitmap_clear_bit (graph->direct_nodes, lhsvar);
750 : }
751 351171164 : else if (rhs.type == ADDRESSOF)
752 : {
753 89366088 : varinfo_t v;
754 :
755 : /* x = &y */
756 89366088 : if (graph->points_to[lhsvar] == NULL)
757 66412194 : graph->points_to[lhsvar] = BITMAP_ALLOC (&predbitmap_obstack);
758 89366088 : bitmap_set_bit (graph->points_to[lhsvar], rhsvar);
759 :
760 89366088 : if (graph->pointed_by[rhsvar] == NULL)
761 21439098 : graph->pointed_by[rhsvar] = BITMAP_ALLOC (&predbitmap_obstack);
762 89366088 : bitmap_set_bit (graph->pointed_by[rhsvar], lhsvar);
763 :
764 : /* Implicitly, *x = y */
765 178732176 : add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
766 :
767 : /* All related variables are no longer direct nodes. */
768 89366088 : bitmap_clear_bit (graph->direct_nodes, rhsvar);
769 89366088 : v = get_varinfo (rhsvar);
770 89366088 : if (!v->is_full_var)
771 : {
772 7203851 : v = get_varinfo (v->head);
773 46311264 : do
774 : {
775 46311264 : bitmap_clear_bit (graph->direct_nodes, v->id);
776 46311264 : v = vi_next (v);
777 : }
778 46311264 : while (v != NULL);
779 : }
780 89366088 : bitmap_set_bit (graph->address_taken, rhsvar);
781 : }
782 261805076 : else if (lhsvar > anything_id
783 261805076 : && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
784 : {
785 : /* x = y */
786 200708284 : add_pred_graph_edge (graph, lhsvar, rhsvar);
787 : /* Implicitly, *x = *y */
788 200708284 : add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar,
789 200708284 : FIRST_REF_NODE + rhsvar);
790 : }
791 61096792 : else if (lhs.offset != 0 || rhs.offset != 0)
792 : {
793 60901245 : if (rhs.offset != 0)
794 60901245 : 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 4415916 : }
800 :
801 : /* Build the constraint graph, adding successor edges. */
802 :
803 : static void
804 4415916 : build_succ_graph (void)
805 : {
806 4415916 : unsigned i, t;
807 4415916 : constraint_t c;
808 :
809 439574561 : FOR_EACH_VEC_ELT (constraints, i, c)
810 : {
811 435158645 : struct constraint_expr lhs;
812 435158645 : struct constraint_expr rhs;
813 435158645 : unsigned int lhsvar;
814 435158645 : unsigned int rhsvar;
815 :
816 435158645 : if (!c)
817 2455141 : continue;
818 :
819 432703504 : lhs = c->lhs;
820 432703504 : rhs = c->rhs;
821 432703504 : lhsvar = find (lhs.var);
822 432703504 : rhsvar = find (rhs.var);
823 :
824 432703504 : if (lhs.type == DEREF)
825 : {
826 35689454 : if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
827 : {
828 31393270 : if (lhs.var == anything_id)
829 0 : add_graph_edge (graph, storedanything_id, rhsvar);
830 : else
831 62786540 : add_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
832 : }
833 : }
834 397014050 : else if (rhs.type == DEREF)
835 : {
836 48254352 : if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
837 26092838 : add_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
838 : }
839 348759698 : else if (rhs.type == ADDRESSOF)
840 : {
841 : /* x = &y */
842 89366088 : gcc_checking_assert (find (rhs.var) == rhs.var);
843 89366088 : bitmap_set_bit (get_varinfo (lhsvar)->solution, rhsvar);
844 : }
845 259393610 : else if (lhsvar > anything_id
846 259393610 : && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
847 : {
848 150805404 : add_graph_edge (graph, lhsvar, rhsvar);
849 : }
850 : }
851 :
852 : /* Add edges from STOREDANYTHING to all nodes that can receive pointers. */
853 4415916 : t = find (storedanything_id);
854 194068804 : for (i = integer_id + 1; i < FIRST_REF_NODE; ++i)
855 : {
856 185236972 : if (get_varinfo (i)->may_have_pointers)
857 185213250 : add_graph_edge (graph, find (i), t);
858 : }
859 :
860 : /* Everything stored to ANYTHING also potentially escapes. */
861 4415916 : add_graph_edge (graph, find (escaped_id), t);
862 4415916 : }
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 377177230 : scc_visit (constraint_graph_t graph, class scc_info *si, unsigned int n)
898 : {
899 377177230 : unsigned int i;
900 377177230 : bitmap_iterator bi;
901 377177230 : unsigned int my_dfs;
902 :
903 377177230 : bitmap_set_bit (si->visited, n);
904 377177230 : si->dfs[n] = si->current_index ++;
905 377177230 : my_dfs = si->dfs[n];
906 :
907 : /* Visit all the successors. */
908 640523914 : EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[n], 0, i, bi)
909 : {
910 263346684 : unsigned int w;
911 :
912 526693368 : if (i > LAST_REF_NODE)
913 : break;
914 :
915 263346684 : w = find (i);
916 263346684 : if (bitmap_bit_p (si->deleted, w))
917 114239840 : continue;
918 :
919 149106844 : if (!bitmap_bit_p (si->visited, w))
920 148845100 : scc_visit (graph, si, w);
921 :
922 149106844 : unsigned int t = find (w);
923 149106844 : gcc_checking_assert (find (n) == n);
924 149106844 : if (si->dfs[t] < si->dfs[n])
925 139269 : si->dfs[n] = si->dfs[t];
926 : }
927 :
928 : /* See if any components have been identified. */
929 377177230 : if (si->dfs[n] == my_dfs)
930 : {
931 377038019 : if (si->scc_stack.length () > 0
932 377038019 : && si->dfs[si->scc_stack.last ()] >= my_dfs)
933 : {
934 105670 : bitmap scc = BITMAP_ALLOC (NULL);
935 105670 : unsigned int lowest_node;
936 105670 : bitmap_iterator bi;
937 :
938 105670 : bitmap_set_bit (scc, n);
939 :
940 105670 : while (si->scc_stack.length () != 0
941 244881 : && si->dfs[si->scc_stack.last ()] >= my_dfs)
942 : {
943 139211 : unsigned int w = si->scc_stack.pop ();
944 :
945 139211 : bitmap_set_bit (scc, w);
946 : }
947 :
948 105670 : lowest_node = bitmap_first_set_bit (scc);
949 105670 : gcc_assert (lowest_node < FIRST_REF_NODE);
950 :
951 : /* Collapse the SCC nodes into a single node, and mark the
952 : indirect cycles. */
953 350551 : EXECUTE_IF_SET_IN_BITMAP (scc, 0, i, bi)
954 : {
955 244881 : if (i < FIRST_REF_NODE)
956 : {
957 124525 : if (unite (lowest_node, i))
958 18855 : unify_nodes (graph, lowest_node, i, false);
959 : }
960 : else
961 : {
962 120356 : unite (lowest_node, i);
963 240712 : graph->indirect_cycles[i - FIRST_REF_NODE] = lowest_node;
964 : }
965 : }
966 105670 : bitmap_set_bit (si->deleted, lowest_node);
967 : }
968 : else
969 376932349 : bitmap_set_bit (si->deleted, n);
970 : }
971 : else
972 139211 : si->scc_stack.safe_push (n);
973 377177230 : }
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 69547016 : unify_nodes (constraint_graph_t graph, unsigned int to, unsigned int from,
980 : bool update_changed)
981 : {
982 69547016 : gcc_checking_assert (to != from && find (to) == to);
983 :
984 69547016 : 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 69547016 : if (update_changed)
990 343630 : stats.unified_vars_dynamic++;
991 : else
992 69203386 : stats.unified_vars_static++;
993 :
994 69547016 : merge_graph_nodes (graph, to, from);
995 69547016 : if (merge_node_constraints (graph, to, from))
996 : {
997 90229 : if (update_changed)
998 10955 : 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 69467742 : if (update_changed
1005 69467742 : && bitmap_clear_bit (changed, from))
1006 36522 : bitmap_set_bit (changed, to);
1007 69547016 : varinfo_t fromvi = get_varinfo (from);
1008 69547016 : if (fromvi->solution)
1009 : {
1010 : /* If the solution changes because of the merging, we need to mark
1011 : the variable as changed. */
1012 69547016 : varinfo_t tovi = get_varinfo (to);
1013 69547016 : if (bitmap_ior_into (tovi->solution, fromvi->solution))
1014 : {
1015 1911016 : if (update_changed)
1016 68195 : bitmap_set_bit (changed, to);
1017 : }
1018 :
1019 69547016 : BITMAP_FREE (fromvi->solution);
1020 69547016 : if (fromvi->oldsolution)
1021 217721 : BITMAP_FREE (fromvi->oldsolution);
1022 :
1023 69547016 : if (stats.iterations > 0
1024 343630 : && tovi->oldsolution)
1025 18259 : BITMAP_FREE (tovi->oldsolution);
1026 : }
1027 69547016 : if (graph->succs[to])
1028 2602438 : bitmap_clear_bit (graph->succs[to], to);
1029 69547016 : }
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 424386731 : 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 424386731 : if (get_varinfo (from)->is_special_var)
1041 30062143 : return bitmap_ior_into (get_varinfo (to)->solution,
1042 60124286 : get_varinfo (from)->solution);
1043 : /* Merging the solution from ESCAPED needlessly increases
1044 : the set. Use ESCAPED as representative instead. */
1045 394324588 : else if (from == find (escaped_id))
1046 34953743 : return bitmap_set_bit (get_varinfo (to)->solution, escaped_id);
1047 359370845 : else if (get_varinfo (from)->may_have_pointers
1048 359370845 : && add_graph_edge (graph, to, from))
1049 116997558 : return bitmap_ior_into (get_varinfo (to)->solution,
1050 116997558 : 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 68735019 : do_sd_constraint (constraint_graph_t graph, constraint_t c,
1059 : bitmap delta, bitmap *expanded_delta)
1060 : {
1061 68735019 : unsigned int lhs = c->lhs.var;
1062 68735019 : bool flag = false;
1063 68735019 : bitmap sol = get_varinfo (lhs)->solution;
1064 68735019 : unsigned int j;
1065 68735019 : bitmap_iterator bi;
1066 68735019 : HOST_WIDE_INT roffset = c->rhs.offset;
1067 :
1068 : /* Our IL does not allow this. */
1069 68735019 : 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 68735019 : if (bitmap_bit_p (delta, anything_id))
1074 : {
1075 573642 : flag |= bitmap_set_bit (sol, anything_id);
1076 573642 : 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 68161377 : if (roffset == UNKNOWN_OFFSET)
1083 : {
1084 50466408 : delta = solution_set_expand (delta, expanded_delta);
1085 : /* No further offset processing is necessary. */
1086 50466408 : 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 310121455 : EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1092 : {
1093 241960078 : varinfo_t v = get_varinfo (j);
1094 241960078 : HOST_WIDE_INT fieldoffset = v->offset + roffset;
1095 241960078 : unsigned HOST_WIDE_INT size = v->size;
1096 241960078 : unsigned int t;
1097 :
1098 241960078 : if (v->is_full_var)
1099 : ;
1100 145225065 : else if (roffset != 0)
1101 : {
1102 5791932 : if (fieldoffset < 0)
1103 136104 : v = get_varinfo (v->head);
1104 : else
1105 5655828 : 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 243918853 : do
1111 : {
1112 243918853 : t = find (v->id);
1113 :
1114 243918853 : flag |= solve_add_graph_edge (graph, lhs, t);
1115 :
1116 243918853 : if (v->is_full_var
1117 147183648 : || v->next == 0)
1118 : break;
1119 :
1120 120214920 : v = vi_next (v);
1121 : }
1122 120214920 : while (v->offset < fieldoffset + size);
1123 : }
1124 :
1125 68161377 : done:
1126 : /* If the LHS solution changed, mark the var as changed. */
1127 68735019 : if (flag)
1128 27603431 : bitmap_set_bit (changed, lhs);
1129 68735019 : }
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 55523753 : do_ds_constraint (constraint_t c, bitmap delta, bitmap *expanded_delta)
1136 : {
1137 55523753 : unsigned int rhs = c->rhs.var;
1138 55523753 : bitmap sol = get_varinfo (rhs)->solution;
1139 55523753 : unsigned int j;
1140 55523753 : bitmap_iterator bi;
1141 55523753 : HOST_WIDE_INT loff = c->lhs.offset;
1142 55523753 : bool escaped_p = false;
1143 :
1144 : /* Our IL does not allow this. */
1145 55523753 : 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 55523753 : if (bitmap_bit_p (sol, anything_id))
1150 412012 : 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 55523753 : if (bitmap_bit_p (delta, anything_id))
1156 : {
1157 448545 : unsigned t = find (storedanything_id);
1158 448545 : if (solve_add_graph_edge (graph, t, rhs))
1159 36255 : bitmap_set_bit (changed, t);
1160 448545 : 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 55075208 : if (loff == UNKNOWN_OFFSET)
1167 : {
1168 2076171 : delta = solution_set_expand (delta, expanded_delta);
1169 2076171 : 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 270821342 : EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1175 : {
1176 215746134 : varinfo_t v = get_varinfo (j);
1177 215746134 : unsigned int t;
1178 215746134 : HOST_WIDE_INT fieldoffset = v->offset + loff;
1179 215746134 : unsigned HOST_WIDE_INT size = v->size;
1180 :
1181 215746134 : if (v->is_full_var)
1182 : ;
1183 132457581 : else if (loff != 0)
1184 : {
1185 8153148 : if (fieldoffset < 0)
1186 4748 : v = get_varinfo (v->head);
1187 : else
1188 8148400 : 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 218193284 : do
1194 : {
1195 218193284 : if (v->may_have_pointers)
1196 : {
1197 : /* If v is a global variable then this is an escape point. */
1198 205879561 : if (v->is_global_var
1199 154585437 : && !escaped_p)
1200 : {
1201 44063540 : t = find (escaped_id);
1202 44063540 : if (add_graph_edge (graph, t, rhs)
1203 57553205 : && bitmap_ior_into (get_varinfo (t)->solution, sol))
1204 1346766 : bitmap_set_bit (changed, t);
1205 : /* Enough to let rhs escape once. */
1206 : escaped_p = true;
1207 : }
1208 :
1209 205879561 : if (v->is_special_var)
1210 : break;
1211 :
1212 180019333 : t = find (v->id);
1213 :
1214 180019333 : if (solve_add_graph_edge (graph, t, rhs))
1215 12263819 : bitmap_set_bit (changed, t);
1216 : }
1217 :
1218 192333056 : if (v->is_full_var
1219 134904589 : || v->next == 0)
1220 : break;
1221 :
1222 110354728 : v = vi_next (v);
1223 : }
1224 110354728 : 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 208255160 : do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta,
1233 : bitmap *expanded_delta)
1234 : {
1235 208255160 : if (c->lhs.type == DEREF)
1236 : {
1237 55523753 : if (c->rhs.type == ADDRESSOF)
1238 : {
1239 0 : gcc_unreachable ();
1240 : }
1241 : else
1242 : {
1243 : /* *x = y */
1244 55523753 : do_ds_constraint (c, delta, expanded_delta);
1245 : }
1246 : }
1247 152731407 : else if (c->rhs.type == DEREF)
1248 : {
1249 : /* x = *y */
1250 68735019 : if (!(get_varinfo (c->lhs.var)->is_special_var))
1251 68735019 : do_sd_constraint (graph, c, delta, expanded_delta);
1252 : }
1253 : else
1254 : {
1255 83996388 : bitmap tmp;
1256 83996388 : bool flag = false;
1257 :
1258 83996388 : gcc_checking_assert (c->rhs.type == SCALAR && c->lhs.type == SCALAR
1259 : && c->rhs.offset != 0 && c->lhs.offset == 0);
1260 83996388 : tmp = get_varinfo (c->lhs.var)->solution;
1261 :
1262 83996388 : flag = set_union_with_increment (tmp, delta, c->rhs.offset,
1263 : expanded_delta);
1264 :
1265 83996388 : if (flag)
1266 20839300 : bitmap_set_bit (changed, c->lhs.var);
1267 : }
1268 208255160 : }
1269 :
1270 : /* Initialize and return a new SCC info structure. */
1271 :
1272 8831832 : scc_info::scc_info (size_t size) :
1273 8831832 : visited (size), deleted (size), current_index (0), scc_stack (1)
1274 : {
1275 8831832 : bitmap_clear (visited);
1276 8831832 : bitmap_clear (deleted);
1277 8831832 : node_mapping = XNEWVEC (unsigned int, size);
1278 8831832 : dfs = XCNEWVEC (unsigned int, size);
1279 :
1280 908752696 : for (size_t i = 0; i < size; i++)
1281 899920864 : node_mapping[i] = i;
1282 8831832 : }
1283 :
1284 : /* Free an SCC info structure pointed to by SI. */
1285 :
1286 8831832 : scc_info::~scc_info ()
1287 : {
1288 8831832 : free (node_mapping);
1289 8831832 : free (dfs);
1290 8831832 : }
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 4415916 : find_indirect_cycles (constraint_graph_t graph)
1302 : {
1303 4415916 : unsigned int i;
1304 4415916 : unsigned int size = graph->size;
1305 4415916 : scc_info si (size);
1306 :
1307 904336780 : for (i = 0; i < MIN (LAST_REF_NODE, size); i++)
1308 445544516 : if (!bitmap_bit_p (si.visited, i) && find (i) == i)
1309 228332130 : scc_visit (graph, &si, i);
1310 4415916 : }
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 383169402 : topo_visit (constraint_graph_t graph, vec<unsigned> &topo_order,
1317 : sbitmap visited, unsigned int n)
1318 : {
1319 383169402 : bitmap_iterator bi;
1320 383169402 : unsigned int j;
1321 :
1322 383169402 : bitmap_set_bit (visited, n);
1323 :
1324 383169402 : if (graph->succs[n])
1325 929950707 : EXECUTE_IF_SET_IN_BITMAP (graph->succs[n], 0, j, bi)
1326 : {
1327 733824270 : unsigned k = find (j);
1328 733824270 : if (!bitmap_bit_p (visited, k))
1329 279701074 : topo_visit (graph, topo_order, visited, k);
1330 : }
1331 :
1332 : /* Also consider copy with offset complex constraints as implicit edges. */
1333 818912775 : for (auto c : graph->complex[n])
1334 : {
1335 : /* Constraints are ordered so that SCALAR = SCALAR appear first. */
1336 253047831 : if (c->lhs.type != SCALAR || c->rhs.type != SCALAR)
1337 : break;
1338 140942567 : gcc_checking_assert (c->rhs.var == n);
1339 140942567 : unsigned k = find (c->lhs.var);
1340 140942567 : if (!bitmap_bit_p (visited, k))
1341 36509726 : topo_visit (graph, topo_order, visited, k);
1342 : }
1343 :
1344 383169402 : topo_order.quick_push (n);
1345 383169402 : }
1346 :
1347 : /* Compute a topological ordering for GRAPH, and return the result. */
1348 :
1349 : static auto_vec<unsigned>
1350 7833434 : compute_topo_order (constraint_graph_t graph)
1351 : {
1352 7833434 : unsigned int i;
1353 7833434 : unsigned int size = graph->size;
1354 :
1355 7833434 : auto_sbitmap visited (size);
1356 7833434 : 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 7833434 : auto_vec<unsigned> tail (size);
1364 7833434 : topo_visit (graph, tail, visited, find (escaped_id));
1365 :
1366 7833434 : auto_vec<unsigned> topo_order (size);
1367 :
1368 581636155 : for (i = 0; i != size; ++i)
1369 565969287 : if (!bitmap_bit_p (visited, i) && find (i) == i)
1370 59125168 : topo_visit (graph, topo_order, visited, i);
1371 :
1372 7833434 : topo_order.splice (tail);
1373 7833434 : return topo_order;
1374 7833434 : }
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 186271176 : equiv_class_hasher::hash (const equiv_class_label *ecl)
1408 : {
1409 186271176 : return ecl->hashcode;
1410 : }
1411 :
1412 : /* Equality function for two equiv_class_label_t's. */
1413 :
1414 : inline bool
1415 241531248 : equiv_class_hasher::equal (const equiv_class_label *eql1,
1416 : const equiv_class_label *eql2)
1417 : {
1418 241531248 : return (eql1->hashcode == eql2->hashcode
1419 241531248 : && 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 192366361 : equiv_class_lookup_or_add (hash_table<equiv_class_hasher> *table,
1430 : bitmap labels)
1431 : {
1432 192366361 : equiv_class_label **slot;
1433 192366361 : equiv_class_label ecl;
1434 :
1435 192366361 : ecl.labels = labels;
1436 192366361 : ecl.hashcode = bitmap_hash (labels);
1437 192366361 : slot = table->find_slot (&ecl, INSERT);
1438 192366361 : if (!*slot)
1439 : {
1440 160909877 : *slot = XOBNEW (&equiv_class_obstack, struct equiv_class_label);
1441 160909877 : (*slot)->labels = labels;
1442 160909877 : (*slot)->hashcode = ecl.hashcode;
1443 160909877 : (*slot)->equivalence_class = 0;
1444 : }
1445 :
1446 192366361 : 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 263168521 : condense_visit (constraint_graph_t graph, class scc_info *si, unsigned int n)
1504 : {
1505 263168521 : unsigned int i;
1506 263168521 : bitmap_iterator bi;
1507 263168521 : unsigned int my_dfs;
1508 :
1509 263168521 : gcc_checking_assert (si->node_mapping[n] == n);
1510 263168521 : bitmap_set_bit (si->visited, n);
1511 263168521 : si->dfs[n] = si->current_index ++;
1512 263168521 : my_dfs = si->dfs[n];
1513 :
1514 : /* Visit all the successors. */
1515 483320093 : EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
1516 : {
1517 220151572 : unsigned int w = si->node_mapping[i];
1518 :
1519 220151572 : if (bitmap_bit_p (si->deleted, w))
1520 139727579 : continue;
1521 :
1522 80423993 : if (!bitmap_bit_p (si->visited, w))
1523 78963144 : condense_visit (graph, si, w);
1524 :
1525 80423993 : unsigned int t = si->node_mapping[w];
1526 80423993 : gcc_checking_assert (si->node_mapping[n] == n);
1527 80423993 : if (si->dfs[t] < si->dfs[n])
1528 2613679 : si->dfs[n] = si->dfs[t];
1529 : }
1530 :
1531 : /* Visit all the implicit predecessors. */
1532 321016656 : EXECUTE_IF_IN_NONNULL_BITMAP (graph->implicit_preds[n], 0, i, bi)
1533 : {
1534 57848135 : unsigned int w = si->node_mapping[i];
1535 :
1536 57848135 : if (bitmap_bit_p (si->deleted, w))
1537 19166626 : continue;
1538 :
1539 38681509 : if (!bitmap_bit_p (si->visited, w))
1540 33883281 : condense_visit (graph, si, w);
1541 :
1542 38681509 : unsigned int t = si->node_mapping[w];
1543 38681509 : gcc_assert (si->node_mapping[n] == n);
1544 38681509 : if (si->dfs[t] < si->dfs[n])
1545 8185787 : si->dfs[n] = si->dfs[t];
1546 : }
1547 :
1548 : /* See if any components have been identified. */
1549 263168521 : if (si->dfs[n] == my_dfs)
1550 : {
1551 252538004 : if (si->scc_stack.length () != 0
1552 252538004 : && 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 10630517 : do
1558 : {
1559 10630517 : --first;
1560 10630517 : unsigned int w = si->scc_stack[first];
1561 10630517 : si->node_mapping[w] = n;
1562 10630517 : if (!bitmap_bit_p (graph->direct_nodes, w))
1563 8540948 : direct_p = false;
1564 : }
1565 : while (first > 0
1566 11972208 : && si->dfs[si->scc_stack[first - 1]] >= my_dfs);
1567 1341691 : if (!direct_p)
1568 852181 : bitmap_clear_bit (graph->direct_nodes, n);
1569 :
1570 : /* Want to reduce to node n, push that first. */
1571 1341691 : si->scc_stack.reserve (1);
1572 1341691 : si->scc_stack.quick_push (si->scc_stack[first]);
1573 1341691 : si->scc_stack[first] = n;
1574 :
1575 1341691 : unsigned scc_size = si->scc_stack.length () - first;
1576 1341691 : unsigned split = scc_size / 2;
1577 1341691 : unsigned carry = scc_size - split * 2;
1578 4702195 : while (split > 0)
1579 : {
1580 13991021 : for (unsigned i = 0; i < split; ++i)
1581 : {
1582 10630517 : unsigned a = si->scc_stack[first + i];
1583 10630517 : unsigned b = si->scc_stack[first + split + carry + i];
1584 :
1585 : /* Unify our nodes. */
1586 10630517 : if (graph->preds[b])
1587 : {
1588 4663679 : if (!graph->preds[a])
1589 957743 : std::swap (graph->preds[a], graph->preds[b]);
1590 : else
1591 3705936 : bitmap_ior_into_and_free (graph->preds[a],
1592 : &graph->preds[b]);
1593 : }
1594 10630517 : if (graph->implicit_preds[b])
1595 : {
1596 8443698 : if (!graph->implicit_preds[a])
1597 865735 : std::swap (graph->implicit_preds[a],
1598 : graph->implicit_preds[b]);
1599 : else
1600 7577963 : bitmap_ior_into_and_free (graph->implicit_preds[a],
1601 : &graph->implicit_preds[b]);
1602 : }
1603 10630517 : if (graph->points_to[b])
1604 : {
1605 522389 : if (!graph->points_to[a])
1606 230416 : std::swap (graph->points_to[a], graph->points_to[b]);
1607 : else
1608 291973 : bitmap_ior_into_and_free (graph->points_to[a],
1609 : &graph->points_to[b]);
1610 : }
1611 : }
1612 3360504 : unsigned remain = split + carry;
1613 3360504 : split = remain / 2;
1614 3360504 : carry = remain - split * 2;
1615 : }
1616 : /* Actually pop the SCC. */
1617 1341691 : si->scc_stack.truncate (first);
1618 : }
1619 252538004 : bitmap_set_bit (si->deleted, n);
1620 : }
1621 : else
1622 10630517 : si->scc_stack.safe_push (n);
1623 263168521 : }
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 229646256 : label_visit (constraint_graph_t graph, class scc_info *si, unsigned int n)
1646 : {
1647 229646256 : unsigned int i, first_pred;
1648 229646256 : bitmap_iterator bi;
1649 :
1650 229646256 : bitmap_set_bit (si->visited, n);
1651 :
1652 : /* Label and union our incoming edges's points to sets. */
1653 229646256 : first_pred = -1U;
1654 444595695 : EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
1655 : {
1656 214949439 : unsigned int w = si->node_mapping[i];
1657 214949439 : if (!bitmap_bit_p (si->visited, w))
1658 74345358 : label_visit (graph, si, w);
1659 :
1660 : /* Skip unused edges. */
1661 214949439 : if (w == n || graph->pointer_label[w] == 0)
1662 5144884 : continue;
1663 :
1664 209804555 : if (graph->points_to[w])
1665 : {
1666 209804555 : if (!graph->points_to[n])
1667 : {
1668 146043211 : if (first_pred == -1U)
1669 : first_pred = w;
1670 : else
1671 : {
1672 40545411 : graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
1673 40545411 : bitmap_ior (graph->points_to[n],
1674 40545411 : graph->points_to[first_pred],
1675 40545411 : graph->points_to[w]);
1676 : }
1677 : }
1678 : else
1679 63761344 : 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 229646256 : if (!bitmap_bit_p (graph->direct_nodes, n))
1685 : {
1686 111318330 : if (!graph->points_to[n])
1687 : {
1688 64261631 : graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
1689 64261631 : if (first_pred != -1U)
1690 25955362 : bitmap_copy (graph->points_to[n], graph->points_to[first_pred]);
1691 : }
1692 222636660 : bitmap_set_bit (graph->points_to[n], FIRST_REF_NODE + n);
1693 111318330 : graph->pointer_label[n] = pointer_equiv_class++;
1694 111318330 : equiv_class_label_t ecl;
1695 222636660 : ecl = equiv_class_lookup_or_add (pointer_equiv_class_table,
1696 111318330 : graph->points_to[n]);
1697 111318330 : ecl->equivalence_class = graph->pointer_label[n];
1698 170037323 : return;
1699 : }
1700 :
1701 : /* If there was only a single non-empty predecessor the pointer equiv
1702 : class is the same. */
1703 118327926 : if (!graph->points_to[n])
1704 : {
1705 58718993 : if (first_pred != -1U)
1706 : {
1707 38997027 : graph->pointer_label[n] = graph->pointer_label[first_pred];
1708 38997027 : graph->points_to[n] = graph->points_to[first_pred];
1709 : }
1710 58718993 : return;
1711 : }
1712 :
1713 59608933 : if (!bitmap_empty_p (graph->points_to[n]))
1714 : {
1715 59608933 : equiv_class_label_t ecl;
1716 59608933 : ecl = equiv_class_lookup_or_add (pointer_equiv_class_table,
1717 : graph->points_to[n]);
1718 59608933 : if (ecl->equivalence_class == 0)
1719 28592696 : ecl->equivalence_class = pointer_equiv_class++;
1720 : else
1721 : {
1722 31016237 : BITMAP_FREE (graph->points_to[n]);
1723 31016237 : graph->points_to[n] = ecl->labels;
1724 : }
1725 59608933 : 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 4415916 : perform_var_substitution (constraint_graph_t graph)
1810 : {
1811 4415916 : unsigned int i;
1812 4415916 : unsigned int size = graph->size;
1813 4415916 : scc_info *si = new scc_info (size);
1814 :
1815 4415916 : bitmap_obstack_initialize (&iteration_obstack);
1816 4415916 : gcc_obstack_init (&equiv_class_obstack);
1817 4415916 : pointer_equiv_class_table = new hash_table<equiv_class_hasher> (511);
1818 4415916 : location_equiv_class_table
1819 4415916 : = new hash_table<equiv_class_hasher> (511);
1820 4415916 : pointer_equiv_class = 1;
1821 4415916 : 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 224980216 : for (i = 1; i < FIRST_REF_NODE; i++)
1826 220564300 : if (!bitmap_bit_p (si->visited, si->node_mapping[i]))
1827 150322096 : condense_visit (graph, si, si->node_mapping[i]);
1828 :
1829 4415916 : 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 4415916 : bitmap_clear (si->visited);
1838 : /* Actually the label the nodes for pointer equivalences. */
1839 454376348 : for (i = 1; i < FIRST_REF_NODE; i++)
1840 220564300 : if (!bitmap_bit_p (si->visited, si->node_mapping[i]))
1841 155300898 : label_visit (graph, si, si->node_mapping[i]);
1842 :
1843 : /* Calculate location equivalence labels. */
1844 224980216 : for (i = 1; i < FIRST_REF_NODE; i++)
1845 : {
1846 220564300 : bitmap pointed_by;
1847 220564300 : bitmap_iterator bi;
1848 220564300 : unsigned int j;
1849 :
1850 220564300 : if (!graph->pointed_by[i])
1851 199125202 : continue;
1852 21439098 : pointed_by = BITMAP_ALLOC (&iteration_obstack);
1853 :
1854 : /* Translate the pointed-by mapping for pointer equivalence
1855 : labels. */
1856 96671772 : EXECUTE_IF_SET_IN_BITMAP (graph->pointed_by[i], 0, j, bi)
1857 : {
1858 75232674 : bitmap_set_bit (pointed_by,
1859 75232674 : graph->pointer_label[si->node_mapping[j]]);
1860 : }
1861 : /* The original pointed_by is now dead. */
1862 21439098 : BITMAP_FREE (graph->pointed_by[i]);
1863 :
1864 : /* Look up the location equivalence label if one exists, or make
1865 : one otherwise. */
1866 21439098 : equiv_class_label_t ecl;
1867 21439098 : ecl = equiv_class_lookup_or_add (location_equiv_class_table, pointed_by);
1868 21439098 : if (ecl->equivalence_class == 0)
1869 20998851 : ecl->equivalence_class = location_equiv_class++;
1870 : else
1871 : {
1872 440247 : 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 440247 : BITMAP_FREE (pointed_by);
1876 : }
1877 21439098 : graph->loc_label[i] = ecl->equivalence_class;
1878 :
1879 : }
1880 :
1881 4415916 : 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 224980216 : for (i = 1; i < FIRST_REF_NODE; i++)
1922 : {
1923 220564300 : unsigned int node = si->node_mapping[i];
1924 :
1925 220564300 : if (graph->pointer_label[node] == 0)
1926 : {
1927 19723372 : 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 19723372 : stats.nonpointer_vars++;
1932 19723372 : clear_edges_for_node (graph, node);
1933 : }
1934 : }
1935 :
1936 4415916 : return si;
1937 : }
1938 :
1939 : /* Free information that was only necessary for variable
1940 : substitution. */
1941 :
1942 : static void
1943 4415916 : free_var_substitution_info (class scc_info *si)
1944 : {
1945 4415916 : delete si;
1946 4415916 : free (graph->pointer_label);
1947 4415916 : free (graph->loc_label);
1948 4415916 : free (graph->pointed_by);
1949 4415916 : free (graph->points_to);
1950 4415916 : free (graph->eq_rep);
1951 4415916 : sbitmap_free (graph->direct_nodes);
1952 4415916 : delete pointer_equiv_class_table;
1953 4415916 : pointer_equiv_class_table = NULL;
1954 4415916 : delete location_equiv_class_table;
1955 4415916 : location_equiv_class_table = NULL;
1956 4415916 : obstack_free (&equiv_class_obstack, NULL);
1957 4415916 : bitmap_obstack_release (&iteration_obstack);
1958 4415916 : }
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 865407008 : 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 865407008 : if (!bitmap_bit_p (graph->address_taken, node))
1973 : {
1974 673164580 : gcc_checking_assert (label < graph->size);
1975 :
1976 673164580 : if (graph->eq_rep[label] != -1)
1977 : {
1978 : /* Unify the two variables since we know they are equivalent. */
1979 569720194 : if (unite (graph->eq_rep[label], node))
1980 66924145 : unify_nodes (graph, graph->eq_rep[label], node, false);
1981 569720194 : return graph->eq_rep[label];
1982 : }
1983 : else
1984 : {
1985 103444386 : graph->eq_rep[label] = node;
1986 103444386 : graph->pe_rep[label] = node;
1987 : }
1988 : }
1989 : else
1990 : {
1991 192242428 : gcc_checking_assert (label < graph->size);
1992 192242428 : graph->pe[node] = label;
1993 192242428 : if (graph->pe_rep[label] == -1)
1994 21347807 : 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 4415916 : unite_pointer_equivalences (constraint_graph_t graph)
2006 : {
2007 4415916 : unsigned int i;
2008 :
2009 : /* Go through the pointer equivalences and unite them to their
2010 : representative, if they aren't already. */
2011 224980216 : for (i = 1; i < FIRST_REF_NODE; i++)
2012 : {
2013 220564300 : unsigned int label = graph->pe[i];
2014 220564300 : if (label)
2015 : {
2016 21439098 : int label_rep = graph->pe_rep[label];
2017 :
2018 21439098 : if (label_rep == -1)
2019 0 : continue;
2020 :
2021 21439098 : label_rep = find (label_rep);
2022 21439098 : if (label_rep >= 0 && unite (label_rep, find (i)))
2023 2260386 : unify_nodes (graph, label_rep, i, false);
2024 : }
2025 : }
2026 4415916 : }
2027 :
2028 : /* Move complex constraints to the GRAPH nodes they belong to. */
2029 :
2030 : static void
2031 4415916 : move_complex_constraints (constraint_graph_t graph)
2032 : {
2033 4415916 : int i;
2034 4415916 : constraint_t c;
2035 :
2036 439574561 : FOR_EACH_VEC_ELT (constraints, i, c)
2037 : {
2038 435158645 : if (c)
2039 : {
2040 432703504 : struct constraint_expr lhs = c->lhs;
2041 432703504 : struct constraint_expr rhs = c->rhs;
2042 :
2043 432703504 : if (lhs.type == DEREF)
2044 : {
2045 35689454 : insert_into_complex (graph, lhs.var, c);
2046 : }
2047 397014050 : else if (rhs.type == DEREF)
2048 : {
2049 48254352 : if (!(get_varinfo (lhs.var)->is_special_var))
2050 48254346 : insert_into_complex (graph, rhs.var, c);
2051 : }
2052 348759698 : else if (rhs.type != ADDRESSOF && lhs.var > anything_id
2053 259232611 : && (lhs.offset != 0 || rhs.offset != 0))
2054 : {
2055 59927750 : insert_into_complex (graph, rhs.var, c);
2056 : }
2057 : }
2058 : }
2059 4415916 : }
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 4415916 : rewrite_constraints (constraint_graph_t graph,
2067 : class scc_info *si)
2068 : {
2069 4415916 : int i;
2070 4415916 : constraint_t c;
2071 :
2072 4415916 : if (flag_checking)
2073 : {
2074 454373200 : for (unsigned int j = 0; j < graph->size; j++)
2075 449957344 : gcc_assert (find (j) == j);
2076 : }
2077 :
2078 439574561 : FOR_EACH_VEC_ELT (constraints, i, c)
2079 : {
2080 435158645 : struct constraint_expr lhs = c->lhs;
2081 435158645 : struct constraint_expr rhs = c->rhs;
2082 435158645 : unsigned int lhsvar = find (lhs.var);
2083 435158645 : unsigned int rhsvar = find (rhs.var);
2084 435158645 : unsigned int lhsnode, rhsnode;
2085 435158645 : unsigned int lhslabel, rhslabel;
2086 :
2087 435158645 : lhsnode = si->node_mapping[lhsvar];
2088 435158645 : rhsnode = si->node_mapping[rhsvar];
2089 435158645 : lhslabel = graph->pointer_label[lhsnode];
2090 435158645 : rhslabel = graph->pointer_label[rhsnode];
2091 :
2092 : /* See if it is really a non-pointer variable, and if so, ignore
2093 : the constraint. */
2094 435158645 : if (lhslabel == 0)
2095 : {
2096 761545 : 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 761545 : constraints[i] = NULL;
2106 2455141 : continue;
2107 : }
2108 :
2109 434397100 : if (rhslabel == 0)
2110 : {
2111 1693596 : 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 1693596 : constraints[i] = NULL;
2121 1693596 : continue;
2122 : }
2123 :
2124 432703504 : lhsvar = find_equivalent_node (graph, lhsvar, lhslabel);
2125 432703504 : rhsvar = find_equivalent_node (graph, rhsvar, rhslabel);
2126 432703504 : c->lhs.var = lhsvar;
2127 432703504 : c->rhs.var = rhsvar;
2128 : }
2129 4415916 : }
2130 :
2131 : /* Eliminate indirect cycles involving NODE. Return true if NODE was
2132 : part of an SCC, false otherwise. */
2133 :
2134 : static bool
2135 382857558 : eliminate_indirect_cycles (unsigned int node)
2136 : {
2137 382857558 : if (graph->indirect_cycles[node] != -1
2138 383178977 : && !bitmap_empty_p (get_varinfo (node)->solution))
2139 : {
2140 289900 : unsigned int i;
2141 289900 : auto_vec<unsigned> queue;
2142 289900 : int queuepos;
2143 289900 : unsigned int to = find (graph->indirect_cycles[node]);
2144 289900 : 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 1567555 : EXECUTE_IF_SET_IN_BITMAP (get_varinfo (node)->solution, 0, i, bi)
2151 : {
2152 1277655 : if (find (i) == i && i != to)
2153 : {
2154 343630 : if (unite (to, i))
2155 343630 : queue.safe_push (i);
2156 : }
2157 : }
2158 :
2159 343630 : for (queuepos = 0;
2160 633530 : queue.iterate (queuepos, &i);
2161 : queuepos++)
2162 : {
2163 343630 : unify_nodes (graph, to, i, true);
2164 : }
2165 289900 : return true;
2166 289900 : }
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 4415916 : solve_graph (constraint_graph_t graph)
2179 : {
2180 4415916 : unsigned int size = graph->size;
2181 4415916 : unsigned int i;
2182 4415916 : bitmap pts;
2183 :
2184 4415916 : changed = BITMAP_ALLOC (NULL);
2185 :
2186 : /* Mark all initial non-collapsed nodes as changed. */
2187 224980216 : for (i = 1; i < size; i++)
2188 : {
2189 220564300 : varinfo_t ivi = get_varinfo (i);
2190 371925214 : if (find (i) == i && !bitmap_empty_p (ivi->solution)
2191 273219751 : && ((graph->succs[i] && !bitmap_empty_p (graph->succs[i]))
2192 228418646 : || graph->complex[i].length () > 0))
2193 33574632 : bitmap_set_bit (changed, i);
2194 : }
2195 :
2196 : /* Allocate a bitmap to be used to store the changed bits. */
2197 4415916 : pts = BITMAP_ALLOC (&pta_obstack);
2198 :
2199 16665266 : while (!bitmap_empty_p (changed))
2200 : {
2201 7833434 : unsigned int i;
2202 7833434 : stats.iterations++;
2203 :
2204 7833434 : bitmap_obstack_initialize (&iteration_obstack);
2205 :
2206 7833434 : auto_vec<unsigned> topo_order = compute_topo_order (graph);
2207 398836270 : while (topo_order.length () != 0)
2208 : {
2209 383169402 : i = topo_order.pop ();
2210 :
2211 : /* If this variable is not a representative, skip it. */
2212 383169402 : if (find (i) != i)
2213 311844 : continue;
2214 :
2215 : /* In certain indirect cycle cases, we may merge this
2216 : variable to another. */
2217 382857558 : if (eliminate_indirect_cycles (i) && find (i) != i)
2218 86 : 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 524496423 : while (bitmap_clear_bit (changed, i))
2230 : {
2231 141927200 : bitmap solution;
2232 141927200 : vec<constraint_t> &complex = graph->complex[i];
2233 141927200 : varinfo_t vi = get_varinfo (i);
2234 141927200 : bool solution_empty;
2235 :
2236 : /* Compute the changed set of solution bits. If anything
2237 : is in the solution just propagate that. */
2238 141927200 : 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 2490704 : if (vi->oldsolution
2244 2490704 : && bitmap_bit_p (vi->oldsolution, anything_id))
2245 : break;
2246 2202455 : bitmap_copy (pts, get_varinfo (find (anything_id))->solution);
2247 : }
2248 139436496 : else if (vi->oldsolution)
2249 36288003 : bitmap_and_compl (pts, vi->solution, vi->oldsolution);
2250 : else
2251 103148493 : bitmap_copy (pts, vi->solution);
2252 :
2253 141638951 : if (bitmap_empty_p (pts))
2254 : break;
2255 :
2256 141638951 : if (vi->oldsolution)
2257 37309530 : bitmap_ior_into (vi->oldsolution, pts);
2258 : else
2259 : {
2260 104329421 : vi->oldsolution = BITMAP_ALLOC (&oldpta_obstack);
2261 104329421 : bitmap_copy (vi->oldsolution, pts);
2262 : }
2263 :
2264 141638951 : solution = vi->solution;
2265 141638951 : solution_empty = bitmap_empty_p (solution);
2266 :
2267 : /* Process the complex constraints. */
2268 141638951 : hash_set<constraint_t> *cvisited = nullptr;
2269 141638951 : if (flag_checking)
2270 141638266 : cvisited = new hash_set<constraint_t>;
2271 141638951 : bitmap expanded_pts = NULL;
2272 350178778 : for (unsigned j = 0; j < complex.length (); ++j)
2273 : {
2274 208539827 : 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 208539827 : unsigned int new_lhs = find (c->lhs.var);
2281 208539827 : unsigned int new_rhs = find (c->rhs.var);
2282 208539827 : if (c->lhs.var != new_lhs || c->rhs.var != new_rhs)
2283 : {
2284 1581271 : constraint tem = *c;
2285 1581271 : tem.lhs.var = new_lhs;
2286 1581271 : tem.rhs.var = new_rhs;
2287 1581271 : unsigned int place
2288 1581271 : = complex.lower_bound (&tem, constraint_less);
2289 1581271 : c->lhs.var = new_lhs;
2290 1581271 : c->rhs.var = new_rhs;
2291 1581271 : if (place != j)
2292 : {
2293 1568864 : complex.ordered_remove (j);
2294 1568864 : if (j < place)
2295 1551065 : --place;
2296 1568864 : if (place < complex.length ())
2297 : {
2298 352469 : if (constraint_equal (*complex[place], *c))
2299 : {
2300 35777 : j--;
2301 284667 : continue;
2302 : }
2303 : else
2304 316692 : complex.safe_insert (place, c);
2305 : }
2306 : else
2307 1216395 : complex.quick_push (c);
2308 1533087 : if (place > j)
2309 : {
2310 248890 : j--;
2311 248890 : 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 208255160 : if (cvisited && cvisited->add (c))
2321 0 : gcc_unreachable ();
2322 208255160 : if (!solution_empty || c->lhs.type != DEREF)
2323 208255160 : do_complex_constraint (graph, c, pts, &expanded_pts);
2324 : }
2325 141638951 : if (cvisited)
2326 : {
2327 : /* When checking, verify the order of constraints is
2328 : maintained and each constraint is evaluated exactly
2329 : once. */
2330 269272760 : for (unsigned j = 1; j < complex.length (); ++j)
2331 127634494 : gcc_assert (constraint_less (complex[j-1], complex[j]));
2332 222257872 : gcc_assert (cvisited->elements () == complex.length ());
2333 141638266 : delete cvisited;
2334 : }
2335 141638951 : BITMAP_FREE (expanded_pts);
2336 :
2337 141638951 : solution_empty = bitmap_empty_p (solution);
2338 :
2339 141638951 : if (!solution_empty)
2340 : {
2341 141638951 : bitmap_iterator bi;
2342 141638951 : unsigned eff_escaped_id = find (escaped_id);
2343 141638951 : unsigned j;
2344 :
2345 : /* Propagate solution to all successors. */
2346 141638951 : unsigned to_remove = ~0U;
2347 357325740 : EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i],
2348 : 0, j, bi)
2349 : {
2350 215686789 : if (to_remove != ~0U)
2351 : {
2352 2156444 : bitmap_clear_bit (graph->succs[i], to_remove);
2353 2156444 : to_remove = ~0U;
2354 : }
2355 215686789 : unsigned int to = find (j);
2356 215686789 : if (to != j)
2357 : {
2358 : /* Update the succ graph, avoiding duplicate
2359 : work. */
2360 2130890 : to_remove = j;
2361 2130890 : if (! bitmap_set_bit (graph->succs[i], to))
2362 882107 : 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 214804682 : if (to == i)
2370 : {
2371 165721 : to_remove = j;
2372 165721 : continue;
2373 : }
2374 : /* Early node unification can lead to edges from
2375 : escaped - remove them. */
2376 214638961 : if (i == eff_escaped_id)
2377 : {
2378 166104 : to_remove = j;
2379 166104 : if (bitmap_set_bit (get_varinfo (to)->solution,
2380 : escaped_id))
2381 92876 : bitmap_set_bit (changed, to);
2382 166104 : continue;
2383 : }
2384 :
2385 214472857 : if (bitmap_ior_into (get_varinfo (to)->solution, pts))
2386 95344744 : bitmap_set_bit (changed, to);
2387 : }
2388 99167843 : if (to_remove != ~0U)
2389 211852 : bitmap_clear_bit (graph->succs[i], to_remove);
2390 : }
2391 : }
2392 : }
2393 7833434 : bitmap_obstack_release (&iteration_obstack);
2394 7833434 : }
2395 :
2396 4415916 : BITMAP_FREE (pts);
2397 4415916 : BITMAP_FREE (changed);
2398 4415916 : bitmap_obstack_release (&oldpta_obstack);
2399 4415916 : }
2400 :
2401 : void
2402 4415916 : delete_graph (void)
2403 : {
2404 4415916 : unsigned int i;
2405 229396132 : for (i = 0; i < graph->size; i++)
2406 224980216 : graph->complex[i].release ();
2407 4415916 : free (graph->complex);
2408 :
2409 4415916 : free (graph->succs);
2410 4415916 : free (graph->pe);
2411 4415916 : free (graph->pe_rep);
2412 4415916 : 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 4415916 : free (graph);
2416 4415916 : }
2417 :
2418 : /* Remove the REF and ADDRESS edges from GRAPH, as well as all the
2419 : predecessor edges. */
2420 :
2421 : static void
2422 4415916 : remove_preds_and_fake_succs (constraint_graph_t graph)
2423 : {
2424 4415916 : unsigned int i;
2425 :
2426 : /* Clear the implicit ref and address nodes from the successor
2427 : lists. */
2428 224980216 : for (i = 1; i < FIRST_REF_NODE; i++)
2429 : {
2430 220564300 : if (graph->succs[i])
2431 64396932 : bitmap_clear_range (graph->succs[i], FIRST_REF_NODE,
2432 64396932 : FIRST_REF_NODE * 2);
2433 : }
2434 :
2435 : /* Free the successor list for the non-ref nodes. */
2436 229396132 : for (i = FIRST_REF_NODE + 1; i < graph->size; i++)
2437 : {
2438 220564300 : if (graph->succs[i])
2439 11778409 : 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 4415916 : graph->size = varmap.length ();
2445 4415916 : graph->succs = XRESIZEVEC (bitmap, graph->succs, graph->size);
2446 :
2447 4415916 : free (graph->implicit_preds);
2448 4415916 : graph->implicit_preds = NULL;
2449 4415916 : free (graph->preds);
2450 4415916 : graph->preds = NULL;
2451 4415916 : bitmap_obstack_release (&predbitmap_obstack);
2452 4415916 : }
2453 :
2454 : namespace pointer_analysis {
2455 :
2456 : /* Solve the constraint set. The entry function of the solver. */
2457 :
2458 : void
2459 4415916 : solve_constraints (void)
2460 : {
2461 4415916 : 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 4415916 : unsigned int *map = XNEWVEC (unsigned int, varmap.length ());
2466 44159160 : for (unsigned i = 0; i < integer_id + 1; ++i)
2467 39743244 : 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 379305776 : for (unsigned i = integer_id + 1; i < varmap.length (); ++i)
2472 185236972 : if (varmap[varmap[i]->head]->address_taken)
2473 15187907 : map[i] = j++;
2474 189652888 : for (unsigned i = integer_id + 1; i < varmap.length (); ++i)
2475 185236972 : if (! varmap[varmap[i]->head]->address_taken)
2476 170049065 : map[i] = j++;
2477 : /* Shuffle varmap according to map. */
2478 189652888 : for (unsigned i = integer_id + 1; i < varmap.length (); ++i)
2479 : {
2480 274741298 : while (map[varmap[i]->id] != i)
2481 89504326 : std::swap (varmap[i], varmap[map[varmap[i]->id]]);
2482 185236972 : gcc_assert (bitmap_empty_p (varmap[i]->solution));
2483 185236972 : varmap[i]->id = i;
2484 185236972 : varmap[i]->next = map[varmap[i]->next];
2485 185236972 : varmap[i]->head = map[varmap[i]->head];
2486 : }
2487 : /* Finally rewrite constraints. */
2488 439574561 : for (unsigned i = 0; i < constraints.length (); ++i)
2489 : {
2490 435158645 : constraints[i]->lhs.var = map[constraints[i]->lhs.var];
2491 435158645 : constraints[i]->rhs.var = map[constraints[i]->rhs.var];
2492 : }
2493 4415916 : free (map);
2494 :
2495 4415916 : if (dump_file)
2496 484 : fprintf (dump_file,
2497 : "\nCollapsing static cycles and doing variable "
2498 : "substitution\n");
2499 :
2500 8831832 : init_graph (varmap.length () * 2);
2501 :
2502 4415916 : if (dump_file)
2503 484 : fprintf (dump_file, "Building predecessor graph\n");
2504 4415916 : build_pred_graph ();
2505 :
2506 4415916 : if (dump_file)
2507 484 : fprintf (dump_file, "Detecting pointer and location "
2508 : "equivalences\n");
2509 4415916 : si = perform_var_substitution (graph);
2510 :
2511 4415916 : if (dump_file)
2512 484 : fprintf (dump_file, "Rewriting constraints and unifying "
2513 : "variables\n");
2514 4415916 : rewrite_constraints (graph, si);
2515 :
2516 4415916 : build_succ_graph ();
2517 :
2518 4415916 : free_var_substitution_info (si);
2519 :
2520 : /* Attach complex constraints to graph nodes. */
2521 4415916 : move_complex_constraints (graph);
2522 :
2523 4415916 : if (dump_file)
2524 484 : fprintf (dump_file, "Uniting pointer but not location equivalent "
2525 : "variables\n");
2526 4415916 : unite_pointer_equivalences (graph);
2527 :
2528 4415916 : if (dump_file)
2529 484 : fprintf (dump_file, "Finding indirect cycles\n");
2530 4415916 : find_indirect_cycles (graph);
2531 :
2532 : /* Implicit nodes and predecessors are no longer necessary at this
2533 : point. */
2534 4415916 : remove_preds_and_fake_succs (graph);
2535 :
2536 4415916 : 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 4415916 : if (dump_file)
2545 484 : fprintf (dump_file, "Solving graph\n");
2546 :
2547 4415916 : solve_graph (graph);
2548 :
2549 4415916 : 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 4415916 : union_find_compress_all ();
2560 4415916 : var_rep = graph->rep;
2561 :
2562 4415916 : delete_graph ();
2563 4415916 : }
2564 :
2565 : } // namespace pointer_analysis
|
