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 9277976108 : find (unsigned int node)
136 : {
137 9277976108 : gcc_checking_assert (node < graph->size);
138 9277976108 : if (graph->rep[node] != node)
139 1048078470 : 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 592764249 : unite (unsigned int to, unsigned int from)
150 : {
151 592764249 : gcc_checking_assert (to < graph->size && from < graph->size);
152 592764249 : if (to != from && graph->rep[from] != to)
153 : {
154 69845880 : graph->rep[from] = to;
155 69845880 : 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 4400386 : union_find_compress_all (void)
165 : {
166 4400386 : unsigned int i;
167 229490627 : for (i = 0; i < graph->size; i++)
168 225090241 : find (i);
169 4400386 : }
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 19180023 : constraint_expr_equal (struct constraint_expr a, struct constraint_expr b)
288 : {
289 12005857 : 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 450018602 : constraint_expr_less (struct constraint_expr a, struct constraint_expr b)
298 : {
299 0 : if (a.type == b.type)
300 : {
301 269068840 : if (a.var == b.var)
302 201783128 : return a.offset < b.offset;
303 : else
304 67285712 : return a.var < b.var;
305 : }
306 : else
307 180949762 : 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 247613949 : constraint_less (const constraint_t &a, const constraint_t &b)
315 : {
316 495227898 : if (constraint_expr_less (a->lhs, b->lhs))
317 : return true;
318 214082152 : else if (constraint_expr_less (b->lhs, a->lhs))
319 : return false;
320 : else
321 95363577 : 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 12588733 : constraint_equal (const constraint &a, const constraint &b)
328 : {
329 19180023 : return constraint_expr_equal (a.lhs, b.lhs)
330 12588733 : && 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 265309 : constraint_vec_find (vec<constraint_t> vec,
337 : constraint &lookfor)
338 : {
339 265309 : unsigned int place;
340 265309 : constraint_t found;
341 :
342 265309 : if (!vec.exists ())
343 : return NULL;
344 :
345 212017 : place = vec.lower_bound (&lookfor, constraint_less);
346 212017 : if (place >= vec.length ())
347 : return NULL;
348 82588 : found = vec[place];
349 82588 : 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 69726363 : constraint_set_union (vec<constraint_t> *to,
359 : vec<constraint_t> *from)
360 : {
361 69726363 : int i;
362 69726363 : constraint_t c;
363 69726363 : bool any_change = false;
364 :
365 69991672 : FOR_EACH_VEC_ELT (*from, i, c)
366 : {
367 265309 : if (constraint_vec_find (*to, *c) == NULL)
368 : {
369 264827 : unsigned int place = to->lower_bound (c, constraint_less);
370 264827 : to->safe_insert (place, c);
371 264827 : any_change = true;
372 : }
373 : }
374 69726363 : return any_change;
375 : }
376 :
377 : /* Expands the solution in SET to all sub-fields of variables included. */
378 :
379 : static bitmap
380 134643483 : solution_set_expand (bitmap set, bitmap *expanded)
381 : {
382 134643483 : bitmap_iterator bi;
383 134643483 : unsigned j;
384 :
385 134643483 : if (*expanded)
386 : return *expanded;
387 :
388 75044891 : *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 75044891 : unsigned prev_head = 0;
393 294570719 : EXECUTE_IF_SET_IN_BITMAP (set, 0, j, bi)
394 : {
395 219525828 : varinfo_t v = get_varinfo (j);
396 219525828 : if (v->is_artificial_var
397 130764375 : || v->is_full_var)
398 110072105 : continue;
399 109453723 : if (v->head != prev_head)
400 : {
401 24637151 : varinfo_t head = get_varinfo (v->head);
402 24637151 : unsigned num = 1;
403 146071485 : for (varinfo_t n = vi_next (head); n != NULL; n = vi_next (n))
404 : {
405 121434334 : 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 13942 : bitmap_set_range (*expanded, head->id, num);
411 13942 : head = n;
412 13942 : num = 1;
413 : }
414 : else
415 121420392 : num++;
416 : }
417 :
418 24637151 : bitmap_set_range (*expanded, head->id, num);
419 24637151 : prev_head = v->head;
420 : }
421 : }
422 :
423 : /* And finally set the rest of the bits from SET in an efficient way. */
424 75044891 : bitmap_ior_into (*expanded, set);
425 :
426 75044891 : 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 84150744 : set_union_with_increment (bitmap to, bitmap delta, HOST_WIDE_INT inc,
434 : bitmap *expanded_delta)
435 : {
436 84150744 : bool changed = false;
437 84150744 : bitmap_iterator bi;
438 84150744 : unsigned int i;
439 :
440 : /* If the solution of DELTA contains anything it is good enough to transfer
441 : this to TO. */
442 84150744 : if (bitmap_bit_p (delta, anything_id))
443 1200334 : 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 82950410 : if (inc == UNKNOWN_OFFSET)
448 : {
449 81998568 : delta = solution_set_expand (delta, expanded_delta);
450 81998568 : changed |= bitmap_ior_into (to, delta);
451 81998568 : return changed;
452 : }
453 :
454 : /* For non-zero offset union the offsetted solution into the destination. */
455 4298092 : EXECUTE_IF_SET_IN_BITMAP (delta, 0, i, bi)
456 : {
457 3346250 : 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 3346250 : if (vi->is_artificial_var
462 2102698 : || vi->is_unknown_size_var
463 1906281 : || vi->is_full_var)
464 1668794 : changed |= bitmap_set_bit (to, i);
465 : else
466 : {
467 1677456 : HOST_WIDE_INT fieldoffset = vi->offset + inc;
468 1677456 : 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 1677456 : if (fieldoffset < 0)
473 51258 : vi = get_varinfo (vi->head);
474 : else
475 1626198 : vi = first_or_preceding_vi_for_offset (vi, fieldoffset);
476 :
477 2551328 : do
478 : {
479 2551328 : changed |= bitmap_set_bit (to, vi->id);
480 2551328 : if (vi->is_full_var
481 2551288 : || vi->next == 0)
482 : break;
483 :
484 : /* We have to include all fields that overlap the current field
485 : shifted by inc. */
486 1502188 : vi = vi_next (vi);
487 : }
488 1502188 : 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 143996625 : insert_into_complex (constraint_graph_t graph,
500 : unsigned int var, constraint_t c)
501 : {
502 143996625 : vec<constraint_t> complex = graph->complex[var];
503 143996625 : unsigned int place = complex.lower_bound (c, constraint_less);
504 :
505 : /* Only insert constraints that do not already exist. */
506 143996625 : if (place >= complex.length ()
507 98957890 : || !constraint_equal (*c, *complex[place]))
508 142022218 : graph->complex[var].safe_insert (place, c);
509 143996625 : }
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 69726363 : merge_node_constraints (constraint_graph_t graph, unsigned int to,
518 : unsigned int from)
519 : {
520 69726363 : unsigned int i;
521 69726363 : constraint_t c;
522 69726363 : bool any_change = false;
523 :
524 69726363 : gcc_checking_assert (find (from) == to);
525 :
526 : /* Move all complex constraints from src node into to node. */
527 69991672 : 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 265309 : if (c->rhs.type == DEREF)
534 86625 : c->rhs.var = to;
535 178684 : else if (c->lhs.type == DEREF)
536 87638 : c->lhs.var = to;
537 : else
538 91046 : c->rhs.var = to;
539 :
540 : }
541 69726363 : any_change = constraint_set_union (&graph->complex[to],
542 : &graph->complex[from]);
543 69726363 : graph->complex[from].release ();
544 69726363 : return any_change;
545 : }
546 :
547 : /* Remove edges involving NODE from GRAPH. */
548 :
549 : static void
550 89435271 : clear_edges_for_node (constraint_graph_t graph, unsigned int node)
551 : {
552 89435271 : if (graph->succs[node])
553 2417144 : BITMAP_FREE (graph->succs[node]);
554 89435271 : }
555 :
556 : /* Merge GRAPH nodes FROM and TO into node TO. */
557 :
558 : static void
559 69726363 : merge_graph_nodes (constraint_graph_t graph, unsigned int to,
560 : unsigned int from)
561 : {
562 69726363 : 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 156 : if (graph->indirect_cycles[to] == -1)
571 113 : graph->indirect_cycles[to] = graph->indirect_cycles[from];
572 : }
573 :
574 : /* Merge all the successor edges. */
575 69726363 : if (graph->succs[from])
576 : {
577 2417144 : if (!graph->succs[to])
578 1229230 : graph->succs[to] = BITMAP_ALLOC (&pta_obstack);
579 2417144 : bitmap_ior_into (graph->succs[to],
580 2417144 : graph->succs[from]);
581 : }
582 :
583 69726363 : clear_edges_for_node (graph, from);
584 69726363 : }
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 290568481 : add_implicit_graph_edge (constraint_graph_t graph, unsigned int to,
592 : unsigned int from)
593 : {
594 290568481 : if (to == from)
595 : return;
596 :
597 290568481 : if (!graph->implicit_preds[to])
598 162643023 : graph->implicit_preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
599 :
600 290568481 : if (bitmap_set_bit (graph->implicit_preds[to], from))
601 273245454 : 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 245527672 : add_pred_graph_edge (constraint_graph_t graph, unsigned int to,
610 : unsigned int from)
611 : {
612 245527672 : if (!graph->preds[to])
613 144641575 : graph->preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
614 245527672 : bitmap_set_bit (graph->preds[to], from);
615 245527672 : }
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 788717528 : add_graph_edge (constraint_graph_t graph, unsigned int to,
623 : unsigned int from)
624 : {
625 788717528 : if (to == from)
626 : {
627 : return false;
628 : }
629 : else
630 : {
631 787987924 : bool r = false;
632 :
633 787987924 : if (!graph->succs[from])
634 91773383 : 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 787987924 : if (to < FIRST_REF_NODE
647 756556652 : && bitmap_bit_p (graph->succs[from], find (escaped_id))
648 1150654925 : && bitmap_bit_p (get_varinfo (find (to))->solution, escaped_id))
649 : {
650 304860447 : stats.num_avoided_edges++;
651 304860447 : return false;
652 : }
653 :
654 483127477 : if (bitmap_set_bit (graph->succs[from], to))
655 : {
656 338181392 : r = true;
657 338181392 : if (to < FIRST_REF_NODE && from < FIRST_REF_NODE)
658 294777588 : stats.num_edges++;
659 : }
660 483127477 : return r;
661 : }
662 : }
663 :
664 : /* Initialize the constraint graph structure to contain SIZE nodes. */
665 :
666 : static void
667 4400386 : init_graph (unsigned int size)
668 : {
669 4400386 : unsigned int j;
670 :
671 4400386 : bitmap_obstack_initialize (&predbitmap_obstack);
672 :
673 4400386 : graph = XCNEW (struct constraint_graph);
674 4400386 : graph->size = size;
675 4400386 : graph->succs = XCNEWVEC (bitmap, graph->size);
676 4400386 : graph->indirect_cycles = XNEWVEC (int, graph->size);
677 4400386 : 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 4400386 : typedef vec<constraint_t> vec_constraint_t_heap;
681 4400386 : graph->complex = XCNEWVEC (vec_constraint_t_heap, size);
682 4400386 : graph->pe = XCNEWVEC (unsigned int, graph->size);
683 4400386 : graph->pe_rep = XNEWVEC (int, graph->size);
684 :
685 454580868 : for (j = 0; j < graph->size; j++)
686 : {
687 450180482 : graph->rep[j] = j;
688 450180482 : graph->pe_rep[j] = -1;
689 450180482 : graph->indirect_cycles[j] = -1;
690 : }
691 4400386 : }
692 :
693 : /* Build the constraint graph, adding only predecessor edges right now. */
694 :
695 : static void
696 4400386 : build_pred_graph (void)
697 : {
698 4400386 : int i;
699 4400386 : constraint_t c;
700 4400386 : unsigned int j;
701 :
702 4400386 : graph->implicit_preds = XCNEWVEC (bitmap, graph->size);
703 4400386 : graph->preds = XCNEWVEC (bitmap, graph->size);
704 4400386 : graph->pointer_label = XCNEWVEC (unsigned int, graph->size);
705 4400386 : graph->loc_label = XCNEWVEC (unsigned int, graph->size);
706 4400386 : graph->pointed_by = XCNEWVEC (bitmap, graph->size);
707 4400386 : graph->points_to = XCNEWVEC (bitmap, graph->size);
708 4400386 : graph->eq_rep = XNEWVEC (int, graph->size);
709 4400386 : graph->direct_nodes = sbitmap_alloc (graph->size);
710 4400386 : graph->address_taken = BITMAP_ALLOC (&predbitmap_obstack);
711 4400386 : bitmap_clear (graph->direct_nodes);
712 :
713 454580868 : for (j = 1; j < FIRST_REF_NODE; j++)
714 : {
715 220689855 : if (!get_varinfo (j)->is_special_var)
716 198687925 : bitmap_set_bit (graph->direct_nodes, j);
717 : }
718 :
719 454580868 : for (j = 0; j < graph->size; j++)
720 450180482 : graph->eq_rep[j] = -1;
721 :
722 458981254 : for (j = 0; j < varmap.length (); j++)
723 225090241 : graph->indirect_cycles[j] = -1;
724 :
725 440180542 : FOR_EACH_VEC_ELT (constraints, i, c)
726 : {
727 435780156 : struct constraint_expr lhs = c->lhs;
728 435780156 : struct constraint_expr rhs = c->rhs;
729 435780156 : unsigned int lhsvar = lhs.var;
730 435780156 : unsigned int rhsvar = rhs.var;
731 :
732 435780156 : if (lhs.type == DEREF)
733 : {
734 : /* *x = y. */
735 35805380 : if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
736 : {
737 31454243 : if (lhs.var == anything_id)
738 0 : add_pred_graph_edge (graph, storedanything_id, rhsvar);
739 : else
740 62908486 : add_pred_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
741 : }
742 : }
743 399974776 : else if (rhs.type == DEREF)
744 : {
745 : /* x = *y */
746 48254067 : if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
747 26030336 : add_pred_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
748 : else
749 35238899 : bitmap_clear_bit (graph->direct_nodes, lhsvar);
750 : }
751 351720709 : else if (rhs.type == ADDRESSOF)
752 : {
753 89510220 : varinfo_t v;
754 :
755 : /* x = &y */
756 89510220 : if (graph->points_to[lhsvar] == NULL)
757 66504855 : graph->points_to[lhsvar] = BITMAP_ALLOC (&predbitmap_obstack);
758 89510220 : bitmap_set_bit (graph->points_to[lhsvar], rhsvar);
759 :
760 89510220 : if (graph->pointed_by[rhsvar] == NULL)
761 21413675 : graph->pointed_by[rhsvar] = BITMAP_ALLOC (&predbitmap_obstack);
762 89510220 : bitmap_set_bit (graph->pointed_by[rhsvar], lhsvar);
763 :
764 : /* Implicitly, *x = y */
765 179020440 : add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
766 :
767 : /* All related variables are no longer direct nodes. */
768 89510220 : bitmap_clear_bit (graph->direct_nodes, rhsvar);
769 89510220 : v = get_varinfo (rhsvar);
770 89510220 : if (!v->is_full_var)
771 : {
772 7222826 : v = get_varinfo (v->head);
773 46637702 : do
774 : {
775 46637702 : bitmap_clear_bit (graph->direct_nodes, v->id);
776 46637702 : v = vi_next (v);
777 : }
778 46637702 : while (v != NULL);
779 : }
780 89510220 : bitmap_set_bit (graph->address_taken, rhsvar);
781 : }
782 262210489 : else if (lhsvar > anything_id
783 262210489 : && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
784 : {
785 : /* x = y */
786 201058261 : add_pred_graph_edge (graph, lhsvar, rhsvar);
787 : /* Implicitly, *x = *y */
788 201058261 : add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar,
789 201058261 : FIRST_REF_NODE + rhsvar);
790 : }
791 61152228 : else if (lhs.offset != 0 || rhs.offset != 0)
792 : {
793 60956707 : if (rhs.offset != 0)
794 60956707 : 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 4400386 : }
800 :
801 : /* Build the constraint graph, adding successor edges. */
802 :
803 : static void
804 4400386 : build_succ_graph (void)
805 : {
806 4400386 : unsigned i, t;
807 4400386 : constraint_t c;
808 :
809 440180542 : FOR_EACH_VEC_ELT (constraints, i, c)
810 : {
811 435780156 : struct constraint_expr lhs;
812 435780156 : struct constraint_expr rhs;
813 435780156 : unsigned int lhsvar;
814 435780156 : unsigned int rhsvar;
815 :
816 435780156 : if (!c)
817 2461986 : continue;
818 :
819 433318170 : lhs = c->lhs;
820 433318170 : rhs = c->rhs;
821 433318170 : lhsvar = find (lhs.var);
822 433318170 : rhsvar = find (rhs.var);
823 :
824 433318170 : if (lhs.type == DEREF)
825 : {
826 35763394 : if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
827 : {
828 31431272 : if (lhs.var == anything_id)
829 0 : add_graph_edge (graph, storedanything_id, rhsvar);
830 : else
831 62862544 : add_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
832 : }
833 : }
834 397554776 : else if (rhs.type == DEREF)
835 : {
836 48253089 : if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
837 26028756 : add_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
838 : }
839 349301687 : else if (rhs.type == ADDRESSOF)
840 : {
841 : /* x = &y */
842 89510220 : gcc_checking_assert (find (rhs.var) == rhs.var);
843 89510220 : bitmap_set_bit (get_varinfo (lhsvar)->solution, rhsvar);
844 : }
845 259791467 : else if (lhsvar > anything_id
846 259791467 : && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
847 : {
848 151107512 : add_graph_edge (graph, lhsvar, rhsvar);
849 : }
850 : }
851 :
852 : /* Add edges from STOREDANYTHING to all nodes that can receive pointers. */
853 4400386 : t = find (storedanything_id);
854 194287539 : for (i = integer_id + 1; i < FIRST_REF_NODE; ++i)
855 : {
856 185486767 : if (get_varinfo (i)->may_have_pointers)
857 185463042 : add_graph_edge (graph, find (i), t);
858 : }
859 :
860 : /* Everything stored to ANYTHING also potentially escapes. */
861 4400386 : add_graph_edge (graph, find (escaped_id), t);
862 4400386 : }
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 377230144 : scc_visit (constraint_graph_t graph, class scc_info *si, unsigned int n)
898 : {
899 377230144 : unsigned int i;
900 377230144 : bitmap_iterator bi;
901 377230144 : unsigned int my_dfs;
902 :
903 377230144 : bitmap_set_bit (si->visited, n);
904 377230144 : si->dfs[n] = si->current_index ++;
905 377230144 : my_dfs = si->dfs[n];
906 :
907 : /* Visit all the successors. */
908 640809410 : EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[n], 0, i, bi)
909 : {
910 263579266 : unsigned int w;
911 :
912 527158532 : if (i > LAST_REF_NODE)
913 : break;
914 :
915 263579266 : w = find (i);
916 263579266 : if (bitmap_bit_p (si->deleted, w))
917 114375187 : continue;
918 :
919 149204079 : if (!bitmap_bit_p (si->visited, w))
920 148942281 : scc_visit (graph, si, w);
921 :
922 149204079 : unsigned int t = find (w);
923 149204079 : gcc_checking_assert (find (n) == n);
924 149204079 : if (si->dfs[t] < si->dfs[n])
925 138362 : si->dfs[n] = si->dfs[t];
926 : }
927 :
928 : /* See if any components have been identified. */
929 377230144 : if (si->dfs[n] == my_dfs)
930 : {
931 377091840 : if (si->scc_stack.length () > 0
932 377091840 : && si->dfs[si->scc_stack.last ()] >= my_dfs)
933 : {
934 104964 : bitmap scc = BITMAP_ALLOC (NULL);
935 104964 : unsigned int lowest_node;
936 104964 : bitmap_iterator bi;
937 :
938 104964 : bitmap_set_bit (scc, n);
939 :
940 104964 : while (si->scc_stack.length () != 0
941 243268 : && si->dfs[si->scc_stack.last ()] >= my_dfs)
942 : {
943 138304 : unsigned int w = si->scc_stack.pop ();
944 :
945 138304 : bitmap_set_bit (scc, w);
946 : }
947 :
948 104964 : lowest_node = bitmap_first_set_bit (scc);
949 104964 : gcc_assert (lowest_node < FIRST_REF_NODE);
950 :
951 : /* Collapse the SCC nodes into a single node, and mark the
952 : indirect cycles. */
953 348232 : EXECUTE_IF_SET_IN_BITMAP (scc, 0, i, bi)
954 : {
955 243268 : if (i < FIRST_REF_NODE)
956 : {
957 123751 : if (unite (lowest_node, i))
958 18787 : unify_nodes (graph, lowest_node, i, false);
959 : }
960 : else
961 : {
962 119517 : unite (lowest_node, i);
963 239034 : graph->indirect_cycles[i - FIRST_REF_NODE] = lowest_node;
964 : }
965 : }
966 104964 : bitmap_set_bit (si->deleted, lowest_node);
967 : }
968 : else
969 376986876 : bitmap_set_bit (si->deleted, n);
970 : }
971 : else
972 138304 : si->scc_stack.safe_push (n);
973 377230144 : }
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 69726363 : unify_nodes (constraint_graph_t graph, unsigned int to, unsigned int from,
980 : bool update_changed)
981 : {
982 69726363 : gcc_checking_assert (to != from && find (to) == to);
983 :
984 69726363 : 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 69726363 : if (update_changed)
990 344060 : stats.unified_vars_dynamic++;
991 : else
992 69382303 : stats.unified_vars_static++;
993 :
994 69726363 : merge_graph_nodes (graph, to, from);
995 69726363 : if (merge_node_constraints (graph, to, from))
996 : {
997 89834 : if (update_changed)
998 10949 : 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 69647478 : if (update_changed
1005 69647478 : && bitmap_clear_bit (changed, from))
1006 36732 : bitmap_set_bit (changed, to);
1007 69726363 : varinfo_t fromvi = get_varinfo (from);
1008 69726363 : if (fromvi->solution)
1009 : {
1010 : /* If the solution changes because of the merging, we need to mark
1011 : the variable as changed. */
1012 69726363 : varinfo_t tovi = get_varinfo (to);
1013 69726363 : if (bitmap_ior_into (tovi->solution, fromvi->solution))
1014 : {
1015 1906285 : if (update_changed)
1016 67851 : bitmap_set_bit (changed, to);
1017 : }
1018 :
1019 69726363 : BITMAP_FREE (fromvi->solution);
1020 69726363 : if (fromvi->oldsolution)
1021 218297 : BITMAP_FREE (fromvi->oldsolution);
1022 :
1023 69726363 : if (stats.iterations > 0
1024 344060 : && tovi->oldsolution)
1025 18346 : BITMAP_FREE (tovi->oldsolution);
1026 : }
1027 69726363 : if (graph->succs[to])
1028 2598783 : bitmap_clear_bit (graph->succs[to], to);
1029 69726363 : }
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 424205194 : 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 424205194 : if (get_varinfo (from)->is_special_var)
1041 30073596 : return bitmap_ior_into (get_varinfo (to)->solution,
1042 60147192 : get_varinfo (from)->solution);
1043 : /* Merging the solution from ESCAPED needlessly increases
1044 : the set. Use ESCAPED as representative instead. */
1045 394131598 : else if (from == find (escaped_id))
1046 34970642 : return bitmap_set_bit (get_varinfo (to)->solution, escaped_id);
1047 359160956 : else if (get_varinfo (from)->may_have_pointers
1048 359160956 : && add_graph_edge (graph, to, from))
1049 117194500 : return bitmap_ior_into (get_varinfo (to)->solution,
1050 117194500 : 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 68802859 : do_sd_constraint (constraint_graph_t graph, constraint_t c,
1059 : bitmap delta, bitmap *expanded_delta)
1060 : {
1061 68802859 : unsigned int lhs = c->lhs.var;
1062 68802859 : bool flag = false;
1063 68802859 : bitmap sol = get_varinfo (lhs)->solution;
1064 68802859 : unsigned int j;
1065 68802859 : bitmap_iterator bi;
1066 68802859 : HOST_WIDE_INT roffset = c->rhs.offset;
1067 :
1068 : /* Our IL does not allow this. */
1069 68802859 : 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 68802859 : if (bitmap_bit_p (delta, anything_id))
1074 : {
1075 590271 : flag |= bitmap_set_bit (sol, anything_id);
1076 590271 : 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 68212588 : if (roffset == UNKNOWN_OFFSET)
1083 : {
1084 50573814 : delta = solution_set_expand (delta, expanded_delta);
1085 : /* No further offset processing is necessary. */
1086 50573814 : 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 310007275 : EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1092 : {
1093 241794687 : varinfo_t v = get_varinfo (j);
1094 241794687 : HOST_WIDE_INT fieldoffset = v->offset + roffset;
1095 241794687 : unsigned HOST_WIDE_INT size = v->size;
1096 241794687 : unsigned int t;
1097 :
1098 241794687 : if (v->is_full_var)
1099 : ;
1100 144946289 : else if (roffset != 0)
1101 : {
1102 5587146 : if (fieldoffset < 0)
1103 115133 : v = get_varinfo (v->head);
1104 : else
1105 5472013 : 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 243521155 : do
1111 : {
1112 243521155 : t = find (v->id);
1113 :
1114 243521155 : flag |= solve_add_graph_edge (graph, lhs, t);
1115 :
1116 243521155 : if (v->is_full_var
1117 146672565 : || v->next == 0)
1118 : break;
1119 :
1120 119797382 : v = vi_next (v);
1121 : }
1122 119797382 : while (v->offset < fieldoffset + size);
1123 : }
1124 :
1125 68212588 : done:
1126 : /* If the LHS solution changed, mark the var as changed. */
1127 68802859 : if (flag)
1128 27595375 : bitmap_set_bit (changed, lhs);
1129 68802859 : }
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 55656011 : do_ds_constraint (constraint_t c, bitmap delta, bitmap *expanded_delta)
1136 : {
1137 55656011 : unsigned int rhs = c->rhs.var;
1138 55656011 : bitmap sol = get_varinfo (rhs)->solution;
1139 55656011 : unsigned int j;
1140 55656011 : bitmap_iterator bi;
1141 55656011 : HOST_WIDE_INT loff = c->lhs.offset;
1142 55656011 : bool escaped_p = false;
1143 :
1144 : /* Our IL does not allow this. */
1145 55656011 : 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 55656011 : if (bitmap_bit_p (sol, anything_id))
1150 423289 : 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 55656011 : if (bitmap_bit_p (delta, anything_id))
1156 : {
1157 461681 : unsigned t = find (storedanything_id);
1158 461681 : if (solve_add_graph_edge (graph, t, rhs))
1159 36244 : bitmap_set_bit (changed, t);
1160 461681 : 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 55194330 : if (loff == UNKNOWN_OFFSET)
1167 : {
1168 2071101 : delta = solution_set_expand (delta, expanded_delta);
1169 2071101 : 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 271205554 : EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1175 : {
1176 216011224 : varinfo_t v = get_varinfo (j);
1177 216011224 : unsigned int t;
1178 216011224 : HOST_WIDE_INT fieldoffset = v->offset + loff;
1179 216011224 : unsigned HOST_WIDE_INT size = v->size;
1180 :
1181 216011224 : if (v->is_full_var)
1182 : ;
1183 132532454 : else if (loff != 0)
1184 : {
1185 8162706 : if (fieldoffset < 0)
1186 4748 : v = get_varinfo (v->head);
1187 : else
1188 8157958 : 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 218461823 : do
1194 : {
1195 218461823 : if (v->may_have_pointers)
1196 : {
1197 : /* If v is a global variable then this is an escape point. */
1198 206095247 : if (v->is_global_var
1199 154860841 : && !escaped_p)
1200 : {
1201 44140387 : t = find (escaped_id);
1202 44140387 : if (add_graph_edge (graph, t, rhs)
1203 57616414 : && bitmap_ior_into (get_varinfo (t)->solution, sol))
1204 1338020 : bitmap_set_bit (changed, t);
1205 : /* Enough to let rhs escape once. */
1206 : escaped_p = true;
1207 : }
1208 :
1209 206095247 : if (v->is_special_var)
1210 : break;
1211 :
1212 180222358 : t = find (v->id);
1213 :
1214 180222358 : if (solve_add_graph_edge (graph, t, rhs))
1215 12299123 : bitmap_set_bit (changed, t);
1216 : }
1217 :
1218 192588934 : if (v->is_full_var
1219 134982911 : || v->next == 0)
1220 : break;
1221 :
1222 110407970 : v = vi_next (v);
1223 : }
1224 110407970 : 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 208609614 : do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta,
1233 : bitmap *expanded_delta)
1234 : {
1235 208609614 : if (c->lhs.type == DEREF)
1236 : {
1237 55656011 : if (c->rhs.type == ADDRESSOF)
1238 : {
1239 0 : gcc_unreachable ();
1240 : }
1241 : else
1242 : {
1243 : /* *x = y */
1244 55656011 : do_ds_constraint (c, delta, expanded_delta);
1245 : }
1246 : }
1247 152953603 : else if (c->rhs.type == DEREF)
1248 : {
1249 : /* x = *y */
1250 68802859 : if (!(get_varinfo (c->lhs.var)->is_special_var))
1251 68802859 : do_sd_constraint (graph, c, delta, expanded_delta);
1252 : }
1253 : else
1254 : {
1255 84150744 : bitmap tmp;
1256 84150744 : bool flag = false;
1257 :
1258 84150744 : gcc_checking_assert (c->rhs.type == SCALAR && c->lhs.type == SCALAR
1259 : && c->rhs.offset != 0 && c->lhs.offset == 0);
1260 84150744 : tmp = get_varinfo (c->lhs.var)->solution;
1261 :
1262 84150744 : flag = set_union_with_increment (tmp, delta, c->rhs.offset,
1263 : expanded_delta);
1264 :
1265 84150744 : if (flag)
1266 20853608 : bitmap_set_bit (changed, c->lhs.var);
1267 : }
1268 208609614 : }
1269 :
1270 : /* Initialize and return a new SCC info structure. */
1271 :
1272 8800772 : scc_info::scc_info (size_t size) :
1273 8800772 : visited (size), deleted (size), current_index (0), scc_stack (1)
1274 : {
1275 8800772 : bitmap_clear (visited);
1276 8800772 : bitmap_clear (deleted);
1277 8800772 : node_mapping = XNEWVEC (unsigned int, size);
1278 8800772 : dfs = XCNEWVEC (unsigned int, size);
1279 :
1280 909161736 : for (size_t i = 0; i < size; i++)
1281 900360964 : node_mapping[i] = i;
1282 8800772 : }
1283 :
1284 : /* Free an SCC info structure pointed to by SI. */
1285 :
1286 8800772 : scc_info::~scc_info ()
1287 : {
1288 8800772 : free (node_mapping);
1289 8800772 : free (dfs);
1290 8800772 : }
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 4400386 : find_indirect_cycles (constraint_graph_t graph)
1302 : {
1303 4400386 : unsigned int i;
1304 4400386 : unsigned int size = graph->size;
1305 4400386 : scc_info si (size);
1306 :
1307 904761350 : for (i = 0; i < MIN (LAST_REF_NODE, size); i++)
1308 445780096 : if (!bitmap_bit_p (si.visited, i) && find (i) == i)
1309 228287863 : scc_visit (graph, &si, i);
1310 4400386 : }
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 382972028 : topo_visit (constraint_graph_t graph, vec<unsigned> &topo_order,
1317 : sbitmap visited, unsigned int n)
1318 : {
1319 382972028 : bitmap_iterator bi;
1320 382972028 : unsigned int j;
1321 :
1322 382972028 : bitmap_set_bit (visited, n);
1323 :
1324 382972028 : if (graph->succs[n])
1325 930293772 : EXECUTE_IF_SET_IN_BITMAP (graph->succs[n], 0, j, bi)
1326 : {
1327 734049195 : unsigned k = find (j);
1328 734049195 : if (!bitmap_bit_p (visited, k))
1329 279666825 : topo_visit (graph, topo_order, visited, k);
1330 : }
1331 :
1332 : /* Also consider copy with offset complex constraints as implicit edges. */
1333 818906942 : for (auto c : graph->complex[n])
1334 : {
1335 : /* Constraints are ordered so that SCALAR = SCALAR appear first. */
1336 253150563 : if (c->lhs.type != SCALAR || c->rhs.type != SCALAR)
1337 : break;
1338 141060986 : gcc_checking_assert (c->rhs.var == n);
1339 141060986 : unsigned k = find (c->lhs.var);
1340 141060986 : if (!bitmap_bit_p (visited, k))
1341 36561221 : topo_visit (graph, topo_order, visited, k);
1342 : }
1343 :
1344 382972028 : topo_order.quick_push (n);
1345 382972028 : }
1346 :
1347 : /* Compute a topological ordering for GRAPH, and return the result. */
1348 :
1349 : static auto_vec<unsigned>
1350 7808936 : compute_topo_order (constraint_graph_t graph)
1351 : {
1352 7808936 : unsigned int i;
1353 7808936 : unsigned int size = graph->size;
1354 :
1355 7808936 : auto_sbitmap visited (size);
1356 7808936 : 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 7808936 : auto_vec<unsigned> tail (size);
1364 7808936 : topo_visit (graph, tail, visited, find (escaped_id));
1365 :
1366 7808936 : auto_vec<unsigned> topo_order (size);
1367 :
1368 581808526 : for (i = 0; i != size; ++i)
1369 566190654 : if (!bitmap_bit_p (visited, i) && find (i) == i)
1370 58935046 : topo_visit (graph, topo_order, visited, i);
1371 :
1372 7808936 : topo_order.splice (tail);
1373 7808936 : return topo_order;
1374 7808936 : }
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 186828011 : equiv_class_hasher::hash (const equiv_class_label *ecl)
1408 : {
1409 186828011 : return ecl->hashcode;
1410 : }
1411 :
1412 : /* Equality function for two equiv_class_label_t's. */
1413 :
1414 : inline bool
1415 242179938 : equiv_class_hasher::equal (const equiv_class_label *eql1,
1416 : const equiv_class_label *eql2)
1417 : {
1418 242179938 : return (eql1->hashcode == eql2->hashcode
1419 242179938 : && 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 192344293 : equiv_class_lookup_or_add (hash_table<equiv_class_hasher> *table,
1430 : bitmap labels)
1431 : {
1432 192344293 : equiv_class_label **slot;
1433 192344293 : equiv_class_label ecl;
1434 :
1435 192344293 : ecl.labels = labels;
1436 192344293 : ecl.hashcode = bitmap_hash (labels);
1437 192344293 : slot = table->find_slot (&ecl, INSERT);
1438 192344293 : if (!*slot)
1439 : {
1440 160813995 : *slot = XOBNEW (&equiv_class_obstack, struct equiv_class_label);
1441 160813995 : (*slot)->labels = labels;
1442 160813995 : (*slot)->hashcode = ecl.hashcode;
1443 160813995 : (*slot)->equivalence_class = 0;
1444 : }
1445 :
1446 192344293 : 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 263296943 : condense_visit (constraint_graph_t graph, class scc_info *si, unsigned int n)
1504 : {
1505 263296943 : unsigned int i;
1506 263296943 : bitmap_iterator bi;
1507 263296943 : unsigned int my_dfs;
1508 :
1509 263296943 : gcc_checking_assert (si->node_mapping[n] == n);
1510 263296943 : bitmap_set_bit (si->visited, n);
1511 263296943 : si->dfs[n] = si->current_index ++;
1512 263296943 : my_dfs = si->dfs[n];
1513 :
1514 : /* Visit all the successors. */
1515 483808355 : EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
1516 : {
1517 220511412 : unsigned int w = si->node_mapping[i];
1518 :
1519 220511412 : if (bitmap_bit_p (si->deleted, w))
1520 140013771 : continue;
1521 :
1522 80497641 : if (!bitmap_bit_p (si->visited, w))
1523 79036689 : condense_visit (graph, si, w);
1524 :
1525 80497641 : unsigned int t = si->node_mapping[w];
1526 80497641 : gcc_checking_assert (si->node_mapping[n] == n);
1527 80497641 : if (si->dfs[t] < si->dfs[n])
1528 2612420 : si->dfs[n] = si->dfs[t];
1529 : }
1530 :
1531 : /* Visit all the implicit predecessors. */
1532 321218955 : EXECUTE_IF_IN_NONNULL_BITMAP (graph->implicit_preds[n], 0, i, bi)
1533 : {
1534 57922012 : unsigned int w = si->node_mapping[i];
1535 :
1536 57922012 : if (bitmap_bit_p (si->deleted, w))
1537 19181765 : continue;
1538 :
1539 38740247 : if (!bitmap_bit_p (si->visited, w))
1540 33929915 : condense_visit (graph, si, w);
1541 :
1542 38740247 : unsigned int t = si->node_mapping[w];
1543 38740247 : gcc_assert (si->node_mapping[n] == n);
1544 38740247 : if (si->dfs[t] < si->dfs[n])
1545 8200295 : si->dfs[n] = si->dfs[t];
1546 : }
1547 :
1548 : /* See if any components have been identified. */
1549 263296943 : if (si->dfs[n] == my_dfs)
1550 : {
1551 252650257 : if (si->scc_stack.length () != 0
1552 252650257 : && 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 10646686 : do
1558 : {
1559 10646686 : --first;
1560 10646686 : unsigned int w = si->scc_stack[first];
1561 10646686 : si->node_mapping[w] = n;
1562 10646686 : if (!bitmap_bit_p (graph->direct_nodes, w))
1563 8557405 : direct_p = false;
1564 : }
1565 : while (first > 0
1566 11987766 : && si->dfs[si->scc_stack[first - 1]] >= my_dfs);
1567 1341080 : if (!direct_p)
1568 851903 : bitmap_clear_bit (graph->direct_nodes, n);
1569 :
1570 : /* Want to reduce to node n, push that first. */
1571 1341080 : si->scc_stack.reserve (1);
1572 1341080 : si->scc_stack.quick_push (si->scc_stack[first]);
1573 1341080 : si->scc_stack[first] = n;
1574 :
1575 1341080 : unsigned scc_size = si->scc_stack.length () - first;
1576 1341080 : unsigned split = scc_size / 2;
1577 1341080 : unsigned carry = scc_size - split * 2;
1578 4703418 : while (split > 0)
1579 : {
1580 14009024 : for (unsigned i = 0; i < split; ++i)
1581 : {
1582 10646686 : unsigned a = si->scc_stack[first + i];
1583 10646686 : unsigned b = si->scc_stack[first + split + carry + i];
1584 :
1585 : /* Unify our nodes. */
1586 10646686 : if (graph->preds[b])
1587 : {
1588 4669553 : if (!graph->preds[a])
1589 961030 : std::swap (graph->preds[a], graph->preds[b]);
1590 : else
1591 3708523 : bitmap_ior_into_and_free (graph->preds[a],
1592 : &graph->preds[b]);
1593 : }
1594 10646686 : if (graph->implicit_preds[b])
1595 : {
1596 8460022 : if (!graph->implicit_preds[a])
1597 865490 : std::swap (graph->implicit_preds[a],
1598 : graph->implicit_preds[b]);
1599 : else
1600 7594532 : bitmap_ior_into_and_free (graph->implicit_preds[a],
1601 : &graph->implicit_preds[b]);
1602 : }
1603 10646686 : if (graph->points_to[b])
1604 : {
1605 522691 : if (!graph->points_to[a])
1606 230406 : std::swap (graph->points_to[a], graph->points_to[b]);
1607 : else
1608 292285 : bitmap_ior_into_and_free (graph->points_to[a],
1609 : &graph->points_to[b]);
1610 : }
1611 : }
1612 3362338 : unsigned remain = split + carry;
1613 3362338 : split = remain / 2;
1614 3362338 : carry = remain - split * 2;
1615 : }
1616 : /* Actually pop the SCC. */
1617 1341080 : si->scc_stack.truncate (first);
1618 : }
1619 252650257 : bitmap_set_bit (si->deleted, n);
1620 : }
1621 : else
1622 10646686 : si->scc_stack.safe_push (n);
1623 263296943 : }
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 229739466 : label_visit (constraint_graph_t graph, class scc_info *si, unsigned int n)
1646 : {
1647 229739466 : unsigned int i, first_pred;
1648 229739466 : bitmap_iterator bi;
1649 :
1650 229739466 : bitmap_set_bit (si->visited, n);
1651 :
1652 : /* Label and union our incoming edges's points to sets. */
1653 229739466 : first_pred = -1U;
1654 445044359 : EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
1655 : {
1656 215304893 : unsigned int w = si->node_mapping[i];
1657 215304893 : if (!bitmap_bit_p (si->visited, w))
1658 74414248 : label_visit (graph, si, w);
1659 :
1660 : /* Skip unused edges. */
1661 215304893 : if (w == n || graph->pointer_label[w] == 0)
1662 5148728 : continue;
1663 :
1664 210156165 : if (graph->points_to[w])
1665 : {
1666 210156165 : if (!graph->points_to[n])
1667 : {
1668 146145205 : if (first_pred == -1U)
1669 : first_pred = w;
1670 : else
1671 : {
1672 40539146 : graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
1673 40539146 : bitmap_ior (graph->points_to[n],
1674 40539146 : graph->points_to[first_pred],
1675 40539146 : graph->points_to[w]);
1676 : }
1677 : }
1678 : else
1679 64010960 : 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 229739466 : if (!bitmap_bit_p (graph->direct_nodes, n))
1685 : {
1686 111264248 : if (!graph->points_to[n])
1687 : {
1688 64178902 : graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
1689 64178902 : if (first_pred != -1U)
1690 25965567 : bitmap_copy (graph->points_to[n], graph->points_to[first_pred]);
1691 : }
1692 222528496 : bitmap_set_bit (graph->points_to[n], FIRST_REF_NODE + n);
1693 111264248 : graph->pointer_label[n] = pointer_equiv_class++;
1694 111264248 : equiv_class_label_t ecl;
1695 222528496 : ecl = equiv_class_lookup_or_add (pointer_equiv_class_table,
1696 111264248 : graph->points_to[n]);
1697 111264248 : ecl->equivalence_class = graph->pointer_label[n];
1698 170073096 : return;
1699 : }
1700 :
1701 : /* If there was only a single non-empty predecessor the pointer equiv
1702 : class is the same. */
1703 118475218 : if (!graph->points_to[n])
1704 : {
1705 58808848 : if (first_pred != -1U)
1706 : {
1707 39101346 : graph->pointer_label[n] = graph->pointer_label[first_pred];
1708 39101346 : graph->points_to[n] = graph->points_to[first_pred];
1709 : }
1710 58808848 : return;
1711 : }
1712 :
1713 59666370 : if (!bitmap_empty_p (graph->points_to[n]))
1714 : {
1715 59666370 : equiv_class_label_t ecl;
1716 59666370 : ecl = equiv_class_lookup_or_add (pointer_equiv_class_table,
1717 : graph->points_to[n]);
1718 59666370 : if (ecl->equivalence_class == 0)
1719 28576867 : ecl->equivalence_class = pointer_equiv_class++;
1720 : else
1721 : {
1722 31089503 : BITMAP_FREE (graph->points_to[n]);
1723 31089503 : graph->points_to[n] = ecl->labels;
1724 : }
1725 59666370 : 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 4400386 : perform_var_substitution (constraint_graph_t graph)
1810 : {
1811 4400386 : unsigned int i;
1812 4400386 : unsigned int size = graph->size;
1813 4400386 : scc_info *si = new scc_info (size);
1814 :
1815 4400386 : bitmap_obstack_initialize (&iteration_obstack);
1816 4400386 : gcc_obstack_init (&equiv_class_obstack);
1817 4400386 : pointer_equiv_class_table = new hash_table<equiv_class_hasher> (511);
1818 4400386 : location_equiv_class_table
1819 4400386 : = new hash_table<equiv_class_hasher> (511);
1820 4400386 : pointer_equiv_class = 1;
1821 4400386 : 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 225090241 : for (i = 1; i < FIRST_REF_NODE; i++)
1826 220689855 : if (!bitmap_bit_p (si->visited, si->node_mapping[i]))
1827 150330339 : condense_visit (graph, si, si->node_mapping[i]);
1828 :
1829 4400386 : 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 4400386 : bitmap_clear (si->visited);
1838 : /* Actually the label the nodes for pointer equivalences. */
1839 454580868 : for (i = 1; i < FIRST_REF_NODE; i++)
1840 220689855 : if (!bitmap_bit_p (si->visited, si->node_mapping[i]))
1841 155325218 : label_visit (graph, si, si->node_mapping[i]);
1842 :
1843 : /* Calculate location equivalence labels. */
1844 225090241 : for (i = 1; i < FIRST_REF_NODE; i++)
1845 : {
1846 220689855 : bitmap pointed_by;
1847 220689855 : bitmap_iterator bi;
1848 220689855 : unsigned int j;
1849 :
1850 220689855 : if (!graph->pointed_by[i])
1851 199276180 : continue;
1852 21413675 : pointed_by = BITMAP_ALLOC (&iteration_obstack);
1853 :
1854 : /* Translate the pointed-by mapping for pointer equivalence
1855 : labels. */
1856 96740338 : EXECUTE_IF_SET_IN_BITMAP (graph->pointed_by[i], 0, j, bi)
1857 : {
1858 75326663 : bitmap_set_bit (pointed_by,
1859 75326663 : graph->pointer_label[si->node_mapping[j]]);
1860 : }
1861 : /* The original pointed_by is now dead. */
1862 21413675 : BITMAP_FREE (graph->pointed_by[i]);
1863 :
1864 : /* Look up the location equivalence label if one exists, or make
1865 : one otherwise. */
1866 21413675 : equiv_class_label_t ecl;
1867 21413675 : ecl = equiv_class_lookup_or_add (location_equiv_class_table, pointed_by);
1868 21413675 : if (ecl->equivalence_class == 0)
1869 20972880 : ecl->equivalence_class = location_equiv_class++;
1870 : else
1871 : {
1872 440795 : 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 440795 : BITMAP_FREE (pointed_by);
1876 : }
1877 21413675 : graph->loc_label[i] = ecl->equivalence_class;
1878 :
1879 : }
1880 :
1881 4400386 : 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 225090241 : for (i = 1; i < FIRST_REF_NODE; i++)
1922 : {
1923 220689855 : unsigned int node = si->node_mapping[i];
1924 :
1925 220689855 : if (graph->pointer_label[node] == 0)
1926 : {
1927 19708908 : 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 19708908 : stats.nonpointer_vars++;
1932 19708908 : clear_edges_for_node (graph, node);
1933 : }
1934 : }
1935 :
1936 4400386 : return si;
1937 : }
1938 :
1939 : /* Free information that was only necessary for variable
1940 : substitution. */
1941 :
1942 : static void
1943 4400386 : free_var_substitution_info (class scc_info *si)
1944 : {
1945 4400386 : delete si;
1946 4400386 : free (graph->pointer_label);
1947 4400386 : free (graph->loc_label);
1948 4400386 : free (graph->pointed_by);
1949 4400386 : free (graph->points_to);
1950 4400386 : free (graph->eq_rep);
1951 4400386 : sbitmap_free (graph->direct_nodes);
1952 4400386 : delete pointer_equiv_class_table;
1953 4400386 : pointer_equiv_class_table = NULL;
1954 4400386 : delete location_equiv_class_table;
1955 4400386 : location_equiv_class_table = NULL;
1956 4400386 : obstack_free (&equiv_class_obstack, NULL);
1957 4400386 : bitmap_obstack_release (&iteration_obstack);
1958 4400386 : }
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 866636340 : 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 866636340 : if (!bitmap_bit_p (graph->address_taken, node))
1973 : {
1974 674224642 : gcc_checking_assert (label < graph->size);
1975 :
1976 674224642 : if (graph->eq_rep[label] != -1)
1977 : {
1978 : /* Unify the two variables since we know they are equivalent. */
1979 570763246 : if (unite (graph->eq_rep[label], node))
1980 67107604 : unify_nodes (graph, graph->eq_rep[label], node, false);
1981 570763246 : return graph->eq_rep[label];
1982 : }
1983 : else
1984 : {
1985 103461396 : graph->eq_rep[label] = node;
1986 103461396 : graph->pe_rep[label] = node;
1987 : }
1988 : }
1989 : else
1990 : {
1991 192411698 : gcc_checking_assert (label < graph->size);
1992 192411698 : graph->pe[node] = label;
1993 192411698 : if (graph->pe_rep[label] == -1)
1994 21322034 : 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 4400386 : unite_pointer_equivalences (constraint_graph_t graph)
2006 : {
2007 4400386 : unsigned int i;
2008 :
2009 : /* Go through the pointer equivalences and unite them to their
2010 : representative, if they aren't already. */
2011 225090241 : for (i = 1; i < FIRST_REF_NODE; i++)
2012 : {
2013 220689855 : unsigned int label = graph->pe[i];
2014 220689855 : if (label)
2015 : {
2016 21413675 : int label_rep = graph->pe_rep[label];
2017 :
2018 21413675 : if (label_rep == -1)
2019 0 : continue;
2020 :
2021 21413675 : label_rep = find (label_rep);
2022 21413675 : if (label_rep >= 0 && unite (label_rep, find (i)))
2023 2255912 : unify_nodes (graph, label_rep, i, false);
2024 : }
2025 : }
2026 4400386 : }
2027 :
2028 : /* Move complex constraints to the GRAPH nodes they belong to. */
2029 :
2030 : static void
2031 4400386 : move_complex_constraints (constraint_graph_t graph)
2032 : {
2033 4400386 : int i;
2034 4400386 : constraint_t c;
2035 :
2036 440180542 : FOR_EACH_VEC_ELT (constraints, i, c)
2037 : {
2038 435780156 : if (c)
2039 : {
2040 433318170 : struct constraint_expr lhs = c->lhs;
2041 433318170 : struct constraint_expr rhs = c->rhs;
2042 :
2043 433318170 : if (lhs.type == DEREF)
2044 : {
2045 35763394 : insert_into_complex (graph, lhs.var, c);
2046 : }
2047 397554776 : else if (rhs.type == DEREF)
2048 : {
2049 48253089 : if (!(get_varinfo (lhs.var)->is_special_var))
2050 48253083 : insert_into_complex (graph, rhs.var, c);
2051 : }
2052 349301687 : else if (rhs.type != ADDRESSOF && lhs.var > anything_id
2053 259630468 : && (lhs.offset != 0 || rhs.offset != 0))
2054 : {
2055 59980148 : insert_into_complex (graph, rhs.var, c);
2056 : }
2057 : }
2058 : }
2059 4400386 : }
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 4400386 : rewrite_constraints (constraint_graph_t graph,
2067 : class scc_info *si)
2068 : {
2069 4400386 : int i;
2070 4400386 : constraint_t c;
2071 :
2072 4400386 : if (flag_checking)
2073 : {
2074 454577720 : for (unsigned int j = 0; j < graph->size; j++)
2075 450177394 : gcc_assert (find (j) == j);
2076 : }
2077 :
2078 440180542 : FOR_EACH_VEC_ELT (constraints, i, c)
2079 : {
2080 435780156 : struct constraint_expr lhs = c->lhs;
2081 435780156 : struct constraint_expr rhs = c->rhs;
2082 435780156 : unsigned int lhsvar = find (lhs.var);
2083 435780156 : unsigned int rhsvar = find (rhs.var);
2084 435780156 : unsigned int lhsnode, rhsnode;
2085 435780156 : unsigned int lhslabel, rhslabel;
2086 :
2087 435780156 : lhsnode = si->node_mapping[lhsvar];
2088 435780156 : rhsnode = si->node_mapping[rhsvar];
2089 435780156 : lhslabel = graph->pointer_label[lhsnode];
2090 435780156 : rhslabel = graph->pointer_label[rhsnode];
2091 :
2092 : /* See if it is really a non-pointer variable, and if so, ignore
2093 : the constraint. */
2094 435780156 : if (lhslabel == 0)
2095 : {
2096 764029 : 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 764029 : constraints[i] = NULL;
2106 2461986 : continue;
2107 : }
2108 :
2109 435016127 : if (rhslabel == 0)
2110 : {
2111 1697957 : 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 1697957 : constraints[i] = NULL;
2121 1697957 : continue;
2122 : }
2123 :
2124 433318170 : lhsvar = find_equivalent_node (graph, lhsvar, lhslabel);
2125 433318170 : rhsvar = find_equivalent_node (graph, rhsvar, rhslabel);
2126 433318170 : c->lhs.var = lhsvar;
2127 433318170 : c->rhs.var = rhsvar;
2128 : }
2129 4400386 : }
2130 :
2131 : /* Eliminate indirect cycles involving NODE. Return true if NODE was
2132 : part of an SCC, false otherwise. */
2133 :
2134 : static bool
2135 382660228 : eliminate_indirect_cycles (unsigned int node)
2136 : {
2137 382660228 : if (graph->indirect_cycles[node] != -1
2138 382978906 : && !bitmap_empty_p (get_varinfo (node)->solution))
2139 : {
2140 287268 : unsigned int i;
2141 287268 : auto_vec<unsigned> queue;
2142 287268 : int queuepos;
2143 287268 : unsigned int to = find (graph->indirect_cycles[node]);
2144 287268 : 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 1565828 : EXECUTE_IF_SET_IN_BITMAP (get_varinfo (node)->solution, 0, i, bi)
2151 : {
2152 1278560 : if (find (i) == i && i != to)
2153 : {
2154 344060 : if (unite (to, i))
2155 344060 : queue.safe_push (i);
2156 : }
2157 : }
2158 :
2159 344060 : for (queuepos = 0;
2160 631328 : queue.iterate (queuepos, &i);
2161 : queuepos++)
2162 : {
2163 344060 : unify_nodes (graph, to, i, true);
2164 : }
2165 287268 : return true;
2166 287268 : }
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 4400386 : solve_graph (constraint_graph_t graph)
2179 : {
2180 4400386 : unsigned int size = graph->size;
2181 4400386 : unsigned int i;
2182 4400386 : bitmap pts;
2183 :
2184 4400386 : changed = BITMAP_ALLOC (NULL);
2185 :
2186 : /* Mark all initial non-collapsed nodes as changed. */
2187 225090241 : for (i = 1; i < size; i++)
2188 : {
2189 220689855 : varinfo_t ivi = get_varinfo (i);
2190 371997407 : if (find (i) == i && !bitmap_empty_p (ivi->solution)
2191 273373685 : && ((graph->succs[i] && !bitmap_empty_p (graph->succs[i]))
2192 228556378 : || graph->complex[i].length () > 0))
2193 33653521 : bitmap_set_bit (changed, i);
2194 : }
2195 :
2196 : /* Allocate a bitmap to be used to store the changed bits. */
2197 4400386 : pts = BITMAP_ALLOC (&pta_obstack);
2198 :
2199 16609708 : while (!bitmap_empty_p (changed))
2200 : {
2201 7808936 : unsigned int i;
2202 7808936 : stats.iterations++;
2203 :
2204 7808936 : bitmap_obstack_initialize (&iteration_obstack);
2205 :
2206 7808936 : auto_vec<unsigned> topo_order = compute_topo_order (graph);
2207 398589900 : while (topo_order.length () != 0)
2208 : {
2209 382972028 : i = topo_order.pop ();
2210 :
2211 : /* If this variable is not a representative, skip it. */
2212 382972028 : if (find (i) != i)
2213 311800 : continue;
2214 :
2215 : /* In certain indirect cycle cases, we may merge this
2216 : variable to another. */
2217 382660228 : if (eliminate_indirect_cycles (i) && find (i) != i)
2218 88 : 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 524451166 : while (bitmap_clear_bit (changed, i))
2230 : {
2231 142081454 : bitmap solution;
2232 142081454 : vec<constraint_t> &complex = graph->complex[i];
2233 142081454 : varinfo_t vi = get_varinfo (i);
2234 142081454 : bool solution_empty;
2235 :
2236 : /* Compute the changed set of solution bits. If anything
2237 : is in the solution just propagate that. */
2238 142081454 : 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 2526155 : if (vi->oldsolution
2244 2526155 : && bitmap_bit_p (vi->oldsolution, anything_id))
2245 : break;
2246 2235727 : bitmap_copy (pts, get_varinfo (find (anything_id))->solution);
2247 : }
2248 139555299 : else if (vi->oldsolution)
2249 36351421 : bitmap_and_compl (pts, vi->solution, vi->oldsolution);
2250 : else
2251 103203878 : bitmap_copy (pts, vi->solution);
2252 :
2253 141791026 : if (bitmap_empty_p (pts))
2254 : break;
2255 :
2256 141791026 : if (vi->oldsolution)
2257 37414679 : bitmap_ior_into (vi->oldsolution, pts);
2258 : else
2259 : {
2260 104376347 : vi->oldsolution = BITMAP_ALLOC (&oldpta_obstack);
2261 104376347 : bitmap_copy (vi->oldsolution, pts);
2262 : }
2263 :
2264 141791026 : solution = vi->solution;
2265 141791026 : solution_empty = bitmap_empty_p (solution);
2266 :
2267 : /* Process the complex constraints. */
2268 141791026 : hash_set<constraint_t> *cvisited = nullptr;
2269 141791026 : if (flag_checking)
2270 141790341 : cvisited = new hash_set<constraint_t>;
2271 141791026 : bitmap expanded_pts = NULL;
2272 350681721 : for (unsigned j = 0; j < complex.length (); ++j)
2273 : {
2274 208890695 : 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 208890695 : unsigned int new_lhs = find (c->lhs.var);
2281 208890695 : unsigned int new_rhs = find (c->rhs.var);
2282 208890695 : if (c->lhs.var != new_lhs || c->rhs.var != new_rhs)
2283 : {
2284 1576150 : constraint tem = *c;
2285 1576150 : tem.lhs.var = new_lhs;
2286 1576150 : tem.rhs.var = new_rhs;
2287 1576150 : unsigned int place
2288 1576150 : = complex.lower_bound (&tem, constraint_less);
2289 1576150 : c->lhs.var = new_lhs;
2290 1576150 : c->rhs.var = new_rhs;
2291 1576150 : if (place != j)
2292 : {
2293 1563839 : complex.ordered_remove (j);
2294 1563839 : if (j < place)
2295 1546096 : --place;
2296 1563839 : if (place < complex.length ())
2297 : {
2298 349256 : if (constraint_equal (*complex[place], *c))
2299 : {
2300 35875 : j--;
2301 281081 : continue;
2302 : }
2303 : else
2304 313381 : complex.safe_insert (place, c);
2305 : }
2306 : else
2307 1214583 : complex.quick_push (c);
2308 1527964 : if (place > j)
2309 : {
2310 245206 : j--;
2311 245206 : 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 208609614 : if (cvisited && cvisited->add (c))
2321 0 : gcc_unreachable ();
2322 208609614 : if (!solution_empty || c->lhs.type != DEREF)
2323 208609614 : do_complex_constraint (graph, c, pts, &expanded_pts);
2324 : }
2325 141791026 : if (cvisited)
2326 : {
2327 : /* When checking, verify the order of constraints is
2328 : maintained and each constraint is evaluated exactly
2329 : once. */
2330 269660720 : for (unsigned j = 1; j < complex.length (); ++j)
2331 127870379 : gcc_assert (constraint_less (complex[j-1], complex[j]));
2332 222528516 : gcc_assert (cvisited->elements () == complex.length ());
2333 141790341 : delete cvisited;
2334 : }
2335 141791026 : BITMAP_FREE (expanded_pts);
2336 :
2337 141791026 : solution_empty = bitmap_empty_p (solution);
2338 :
2339 141791026 : if (!solution_empty)
2340 : {
2341 141791026 : bitmap_iterator bi;
2342 141791026 : unsigned eff_escaped_id = find (escaped_id);
2343 141791026 : unsigned j;
2344 :
2345 : /* Propagate solution to all successors. */
2346 141791026 : unsigned to_remove = ~0U;
2347 358011254 : EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i],
2348 : 0, j, bi)
2349 : {
2350 216220228 : if (to_remove != ~0U)
2351 : {
2352 2159249 : bitmap_clear_bit (graph->succs[i], to_remove);
2353 2159249 : to_remove = ~0U;
2354 : }
2355 216220228 : unsigned int to = find (j);
2356 216220228 : if (to != j)
2357 : {
2358 : /* Update the succ graph, avoiding duplicate
2359 : work. */
2360 2132909 : to_remove = j;
2361 2132909 : if (! bitmap_set_bit (graph->succs[i], to))
2362 881800 : 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 215338428 : if (to == i)
2370 : {
2371 166043 : to_remove = j;
2372 166043 : continue;
2373 : }
2374 : /* Early node unification can lead to edges from
2375 : escaped - remove them. */
2376 215172385 : if (i == eff_escaped_id)
2377 : {
2378 166907 : to_remove = j;
2379 166907 : if (bitmap_set_bit (get_varinfo (to)->solution,
2380 : escaped_id))
2381 92924 : bitmap_set_bit (changed, to);
2382 166907 : continue;
2383 : }
2384 :
2385 215005478 : if (bitmap_ior_into (get_varinfo (to)->solution, pts))
2386 95592831 : bitmap_set_bit (changed, to);
2387 : }
2388 99368602 : if (to_remove != ~0U)
2389 212011 : bitmap_clear_bit (graph->succs[i], to_remove);
2390 : }
2391 : }
2392 : }
2393 7808936 : bitmap_obstack_release (&iteration_obstack);
2394 7808936 : }
2395 :
2396 4400386 : BITMAP_FREE (pts);
2397 4400386 : BITMAP_FREE (changed);
2398 4400386 : bitmap_obstack_release (&oldpta_obstack);
2399 4400386 : }
2400 :
2401 : void
2402 4400386 : delete_graph (void)
2403 : {
2404 4400386 : unsigned int i;
2405 229490627 : for (i = 0; i < graph->size; i++)
2406 225090241 : graph->complex[i].release ();
2407 4400386 : free (graph->complex);
2408 :
2409 4400386 : free (graph->succs);
2410 4400386 : free (graph->pe);
2411 4400386 : free (graph->pe_rep);
2412 4400386 : 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 4400386 : free (graph);
2416 4400386 : }
2417 :
2418 : /* Remove the REF and ADDRESS edges from GRAPH, as well as all the
2419 : predecessor edges. */
2420 :
2421 : static void
2422 4400386 : remove_preds_and_fake_succs (constraint_graph_t graph)
2423 : {
2424 4400386 : unsigned int i;
2425 :
2426 : /* Clear the implicit ref and address nodes from the successor
2427 : lists. */
2428 225090241 : for (i = 1; i < FIRST_REF_NODE; i++)
2429 : {
2430 220689855 : if (graph->succs[i])
2431 64423442 : bitmap_clear_range (graph->succs[i], FIRST_REF_NODE,
2432 64423442 : FIRST_REF_NODE * 2);
2433 : }
2434 :
2435 : /* Free the successor list for the non-ref nodes. */
2436 229490627 : for (i = FIRST_REF_NODE + 1; i < graph->size; i++)
2437 : {
2438 220689855 : if (graph->succs[i])
2439 11741145 : 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 4400386 : graph->size = varmap.length ();
2445 4400386 : graph->succs = XRESIZEVEC (bitmap, graph->succs, graph->size);
2446 :
2447 4400386 : free (graph->implicit_preds);
2448 4400386 : graph->implicit_preds = NULL;
2449 4400386 : free (graph->preds);
2450 4400386 : graph->preds = NULL;
2451 4400386 : bitmap_obstack_release (&predbitmap_obstack);
2452 4400386 : }
2453 :
2454 : namespace pointer_analysis {
2455 :
2456 : /* Solve the constraint set. The entry function of the solver. */
2457 :
2458 : void
2459 4400386 : solve_constraints (void)
2460 : {
2461 4400386 : 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 4400386 : unsigned int *map = XNEWVEC (unsigned int, varmap.length ());
2466 44003860 : for (unsigned i = 0; i < integer_id + 1; ++i)
2467 39603474 : 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 379774306 : for (unsigned i = integer_id + 1; i < varmap.length (); ++i)
2472 185486767 : if (varmap[varmap[i]->head]->address_taken)
2473 15223311 : map[i] = j++;
2474 189887153 : for (unsigned i = integer_id + 1; i < varmap.length (); ++i)
2475 185486767 : if (! varmap[varmap[i]->head]->address_taken)
2476 170263456 : map[i] = j++;
2477 : /* Shuffle varmap according to map. */
2478 189887153 : for (unsigned i = integer_id + 1; i < varmap.length (); ++i)
2479 : {
2480 275628170 : while (map[varmap[i]->id] != i)
2481 90141403 : std::swap (varmap[i], varmap[map[varmap[i]->id]]);
2482 185486767 : gcc_assert (bitmap_empty_p (varmap[i]->solution));
2483 185486767 : varmap[i]->id = i;
2484 185486767 : varmap[i]->next = map[varmap[i]->next];
2485 185486767 : varmap[i]->head = map[varmap[i]->head];
2486 : }
2487 : /* Finally rewrite constraints. */
2488 440180542 : for (unsigned i = 0; i < constraints.length (); ++i)
2489 : {
2490 435780156 : constraints[i]->lhs.var = map[constraints[i]->lhs.var];
2491 435780156 : constraints[i]->rhs.var = map[constraints[i]->rhs.var];
2492 : }
2493 4400386 : free (map);
2494 :
2495 4400386 : if (dump_file)
2496 484 : fprintf (dump_file,
2497 : "\nCollapsing static cycles and doing variable "
2498 : "substitution\n");
2499 :
2500 8800772 : init_graph (varmap.length () * 2);
2501 :
2502 4400386 : if (dump_file)
2503 484 : fprintf (dump_file, "Building predecessor graph\n");
2504 4400386 : build_pred_graph ();
2505 :
2506 4400386 : if (dump_file)
2507 484 : fprintf (dump_file, "Detecting pointer and location "
2508 : "equivalences\n");
2509 4400386 : si = perform_var_substitution (graph);
2510 :
2511 4400386 : if (dump_file)
2512 484 : fprintf (dump_file, "Rewriting constraints and unifying "
2513 : "variables\n");
2514 4400386 : rewrite_constraints (graph, si);
2515 :
2516 4400386 : build_succ_graph ();
2517 :
2518 4400386 : free_var_substitution_info (si);
2519 :
2520 : /* Attach complex constraints to graph nodes. */
2521 4400386 : move_complex_constraints (graph);
2522 :
2523 4400386 : if (dump_file)
2524 484 : fprintf (dump_file, "Uniting pointer but not location equivalent "
2525 : "variables\n");
2526 4400386 : unite_pointer_equivalences (graph);
2527 :
2528 4400386 : if (dump_file)
2529 484 : fprintf (dump_file, "Finding indirect cycles\n");
2530 4400386 : find_indirect_cycles (graph);
2531 :
2532 : /* Implicit nodes and predecessors are no longer necessary at this
2533 : point. */
2534 4400386 : remove_preds_and_fake_succs (graph);
2535 :
2536 4400386 : 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 4400386 : if (dump_file)
2545 484 : fprintf (dump_file, "Solving graph\n");
2546 :
2547 4400386 : solve_graph (graph);
2548 :
2549 4400386 : 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 4400386 : union_find_compress_all ();
2560 4400386 : var_rep = graph->rep;
2561 :
2562 4400386 : delete_graph ();
2563 4400386 : }
2564 :
2565 : } // namespace pointer_analysis
|
