Branch data Line data Source code
1 : : /* Andersen-style solver for tree based points-to analysis
2 : : Copyright (C) 2005-2025 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 : 9348749181 : find (unsigned int node)
136 : : {
137 : 9348749181 : gcc_checking_assert (node < graph->size);
138 : 9348749181 : if (graph->rep[node] != node)
139 : 1057304637 : 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 : 598731079 : unite (unsigned int to, unsigned int from)
150 : : {
151 : 598731079 : gcc_checking_assert (to < graph->size && from < graph->size);
152 : 598731079 : if (to != from && graph->rep[from] != to)
153 : : {
154 : 70517930 : graph->rep[from] = to;
155 : 70517930 : 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 : 4459820 : union_find_compress_all (void)
165 : : {
166 : 4459820 : unsigned int i;
167 : 231318720 : for (i = 0; i < graph->size; i++)
168 : 226858900 : find (i);
169 : 4459820 : }
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 : 19243604 : constraint_expr_equal (struct constraint_expr a, struct constraint_expr b)
288 : : {
289 : 11941907 : 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 : 454251010 : constraint_expr_less (struct constraint_expr a, struct constraint_expr b)
298 : : {
299 : 0 : if (a.type == b.type)
300 : : {
301 : 270823443 : if (a.var == b.var)
302 : 204037280 : return a.offset < b.offset;
303 : : else
304 : 66786163 : return a.var < b.var;
305 : : }
306 : : else
307 : 183427567 : 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 : 249524773 : constraint_less (const constraint_t &a, const constraint_t &b)
315 : : {
316 : 499049546 : if (constraint_expr_less (a->lhs, b->lhs))
317 : : return true;
318 : 216362708 : else if (constraint_expr_less (b->lhs, a->lhs))
319 : : return false;
320 : : else
321 : 96544883 : 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 : 12632819 : constraint_equal (const constraint &a, const constraint &b)
328 : : {
329 : 19243604 : return constraint_expr_equal (a.lhs, b.lhs)
330 : 12632819 : && 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 : 277001 : constraint_vec_find (vec<constraint_t> vec,
337 : : constraint &lookfor)
338 : : {
339 : 277001 : unsigned int place;
340 : 277001 : constraint_t found;
341 : :
342 : 277001 : if (!vec.exists ())
343 : : return NULL;
344 : :
345 : 221747 : place = vec.lower_bound (&lookfor, constraint_less);
346 : 221747 : if (place >= vec.length ())
347 : : return NULL;
348 : 87223 : found = vec[place];
349 : 87223 : 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 : 70395261 : constraint_set_union (vec<constraint_t> *to,
359 : : vec<constraint_t> *from)
360 : : {
361 : 70395261 : int i;
362 : 70395261 : constraint_t c;
363 : 70395261 : bool any_change = false;
364 : :
365 : 70672262 : FOR_EACH_VEC_ELT (*from, i, c)
366 : : {
367 : 277001 : if (constraint_vec_find (*to, *c) == NULL)
368 : : {
369 : 276333 : unsigned int place = to->lower_bound (c, constraint_less);
370 : 276333 : to->safe_insert (place, c);
371 : 276333 : any_change = true;
372 : : }
373 : : }
374 : 70395261 : return any_change;
375 : : }
376 : :
377 : : /* Expands the solution in SET to all sub-fields of variables included. */
378 : :
379 : : static bitmap
380 : 135214369 : solution_set_expand (bitmap set, bitmap *expanded)
381 : : {
382 : 135214369 : bitmap_iterator bi;
383 : 135214369 : unsigned j;
384 : :
385 : 135214369 : if (*expanded)
386 : : return *expanded;
387 : :
388 : 75424477 : *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 : 75424477 : unsigned prev_head = 0;
393 : 295406182 : EXECUTE_IF_SET_IN_BITMAP (set, 0, j, bi)
394 : : {
395 : 219981705 : varinfo_t v = get_varinfo (j);
396 : 219981705 : if (v->is_artificial_var
397 : 130470019 : || v->is_full_var)
398 : 110404397 : continue;
399 : 109577308 : if (v->head != prev_head)
400 : : {
401 : 25005053 : varinfo_t head = get_varinfo (v->head);
402 : 25005053 : unsigned num = 1;
403 : 146175640 : for (varinfo_t n = vi_next (head); n != NULL; n = vi_next (n))
404 : : {
405 : 121170587 : 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 : 15366 : bitmap_set_range (*expanded, head->id, num);
411 : 15366 : head = n;
412 : 15366 : num = 1;
413 : : }
414 : : else
415 : 121155221 : num++;
416 : : }
417 : :
418 : 25005053 : bitmap_set_range (*expanded, head->id, num);
419 : 25005053 : prev_head = v->head;
420 : : }
421 : : }
422 : :
423 : : /* And finally set the rest of the bits from SET in an efficient way. */
424 : 75424477 : bitmap_ior_into (*expanded, set);
425 : :
426 : 75424477 : 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 : 84535597 : set_union_with_increment (bitmap to, bitmap delta, HOST_WIDE_INT inc,
434 : : bitmap *expanded_delta)
435 : : {
436 : 84535597 : bool changed = false;
437 : 84535597 : bitmap_iterator bi;
438 : 84535597 : unsigned int i;
439 : :
440 : : /* If the solution of DELTA contains anything it is good enough to transfer
441 : : this to TO. */
442 : 84535597 : if (bitmap_bit_p (delta, anything_id))
443 : 1320867 : 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 : 83214730 : if (inc == UNKNOWN_OFFSET)
448 : : {
449 : 82225526 : delta = solution_set_expand (delta, expanded_delta);
450 : 82225526 : changed |= bitmap_ior_into (to, delta);
451 : 82225526 : return changed;
452 : : }
453 : :
454 : : /* For non-zero offset union the offsetted solution into the destination. */
455 : 4276246 : EXECUTE_IF_SET_IN_BITMAP (delta, 0, i, bi)
456 : : {
457 : 3287042 : 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 : 3287042 : if (vi->is_artificial_var
462 : 1966539 : || vi->is_unknown_size_var
463 : 1827126 : || vi->is_full_var)
464 : 1709250 : changed |= bitmap_set_bit (to, i);
465 : : else
466 : : {
467 : 1577792 : HOST_WIDE_INT fieldoffset = vi->offset + inc;
468 : 1577792 : 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 : 1577792 : if (fieldoffset < 0)
473 : 33217 : vi = get_varinfo (vi->head);
474 : : else
475 : 1544575 : vi = first_or_preceding_vi_for_offset (vi, fieldoffset);
476 : :
477 : 1906045 : do
478 : : {
479 : 1906045 : changed |= bitmap_set_bit (to, vi->id);
480 : 1906045 : if (vi->is_full_var
481 : 1906005 : || vi->next == 0)
482 : : break;
483 : :
484 : : /* We have to include all fields that overlap the current field
485 : : shifted by inc. */
486 : 900921 : vi = vi_next (vi);
487 : : }
488 : 900921 : 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 : 145098288 : insert_into_complex (constraint_graph_t graph,
500 : : unsigned int var, constraint_t c)
501 : : {
502 : 145098288 : vec<constraint_t> complex = graph->complex[var];
503 : 145098288 : unsigned int place = complex.lower_bound (c, constraint_less);
504 : :
505 : : /* Only insert constraints that do not already exist. */
506 : 145098288 : if (place >= complex.length ()
507 : 99688054 : || !constraint_equal (*c, *complex[place]))
508 : 143161087 : graph->complex[var].safe_insert (place, c);
509 : 145098288 : }
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 : 70395261 : merge_node_constraints (constraint_graph_t graph, unsigned int to,
518 : : unsigned int from)
519 : : {
520 : 70395261 : unsigned int i;
521 : 70395261 : constraint_t c;
522 : 70395261 : bool any_change = false;
523 : :
524 : 70395261 : gcc_checking_assert (find (from) == to);
525 : :
526 : : /* Move all complex constraints from src node into to node. */
527 : 70672262 : 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 : 277001 : if (c->rhs.type == DEREF)
534 : 90414 : c->rhs.var = to;
535 : 186587 : else if (c->lhs.type == DEREF)
536 : 91406 : c->lhs.var = to;
537 : : else
538 : 95181 : c->rhs.var = to;
539 : :
540 : : }
541 : 70395261 : any_change = constraint_set_union (&graph->complex[to],
542 : : &graph->complex[from]);
543 : 70395261 : graph->complex[from].release ();
544 : 70395261 : return any_change;
545 : : }
546 : :
547 : : /* Remove edges involving NODE from GRAPH. */
548 : :
549 : : static void
550 : 90241359 : clear_edges_for_node (constraint_graph_t graph, unsigned int node)
551 : : {
552 : 90241359 : if (graph->succs[node])
553 : 2469396 : BITMAP_FREE (graph->succs[node]);
554 : 90241359 : }
555 : :
556 : : /* Merge GRAPH nodes FROM and TO into node TO. */
557 : :
558 : : static void
559 : 70395261 : merge_graph_nodes (constraint_graph_t graph, unsigned int to,
560 : : unsigned int from)
561 : : {
562 : 70395261 : 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 : 77 : if (graph->indirect_cycles[to] == -1)
571 : 56 : graph->indirect_cycles[to] = graph->indirect_cycles[from];
572 : : }
573 : :
574 : : /* Merge all the successor edges. */
575 : 70395261 : if (graph->succs[from])
576 : : {
577 : 2469396 : if (!graph->succs[to])
578 : 1240932 : graph->succs[to] = BITMAP_ALLOC (&pta_obstack);
579 : 2469396 : bitmap_ior_into (graph->succs[to],
580 : 2469396 : graph->succs[from]);
581 : : }
582 : :
583 : 70395261 : clear_edges_for_node (graph, from);
584 : 70395261 : }
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 : 293680504 : add_implicit_graph_edge (constraint_graph_t graph, unsigned int to,
592 : : unsigned int from)
593 : : {
594 : 293680504 : if (to == from)
595 : : return;
596 : :
597 : 293680504 : if (!graph->implicit_preds[to])
598 : 163956954 : graph->implicit_preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
599 : :
600 : 293680504 : if (bitmap_set_bit (graph->implicit_preds[to], from))
601 : 276320464 : 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 : 248737768 : add_pred_graph_edge (constraint_graph_t graph, unsigned int to,
610 : : unsigned int from)
611 : : {
612 : 248737768 : if (!graph->preds[to])
613 : 146125914 : graph->preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
614 : 248737768 : bitmap_set_bit (graph->preds[to], from);
615 : 248737768 : }
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 : 792958440 : add_graph_edge (constraint_graph_t graph, unsigned int to,
623 : : unsigned int from)
624 : : {
625 : 792958440 : if (to == from)
626 : : {
627 : : return false;
628 : : }
629 : : else
630 : : {
631 : 792215322 : bool r = false;
632 : :
633 : 792215322 : if (!graph->succs[from])
634 : 92497955 : 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 : 792215322 : if (to < FIRST_REF_NODE
647 : 760403559 : && bitmap_bit_p (graph->succs[from], find (escaped_id))
648 : 1155294667 : && bitmap_bit_p (get_varinfo (find (to))->solution, escaped_id))
649 : : {
650 : 305085957 : stats.num_avoided_edges++;
651 : 305085957 : return false;
652 : : }
653 : :
654 : 487129365 : if (bitmap_set_bit (graph->succs[from], to))
655 : : {
656 : 340406495 : r = true;
657 : 340406495 : if (to < FIRST_REF_NODE && from < FIRST_REF_NODE)
658 : 296464473 : stats.num_edges++;
659 : : }
660 : 487129365 : return r;
661 : : }
662 : : }
663 : :
664 : : /* Initialize the constraint graph structure to contain SIZE nodes. */
665 : :
666 : : static void
667 : 4459820 : init_graph (unsigned int size)
668 : : {
669 : 4459820 : unsigned int j;
670 : :
671 : 4459820 : bitmap_obstack_initialize (&predbitmap_obstack);
672 : :
673 : 4459820 : graph = XCNEW (struct constraint_graph);
674 : 4459820 : graph->size = size;
675 : 4459820 : graph->succs = XCNEWVEC (bitmap, graph->size);
676 : 4459820 : graph->indirect_cycles = XNEWVEC (int, graph->size);
677 : 4459820 : 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 : 4459820 : typedef vec<constraint_t> vec_constraint_t_heap;
681 : 4459820 : graph->complex = XCNEWVEC (vec_constraint_t_heap, size);
682 : 4459820 : graph->pe = XCNEWVEC (unsigned int, graph->size);
683 : 4459820 : graph->pe_rep = XNEWVEC (int, graph->size);
684 : :
685 : 458177620 : for (j = 0; j < graph->size; j++)
686 : : {
687 : 453717800 : graph->rep[j] = j;
688 : 453717800 : graph->pe_rep[j] = -1;
689 : 453717800 : graph->indirect_cycles[j] = -1;
690 : : }
691 : 4459820 : }
692 : :
693 : : /* Build the constraint graph, adding only predecessor edges right now. */
694 : :
695 : : static void
696 : 4459820 : build_pred_graph (void)
697 : : {
698 : 4459820 : int i;
699 : 4459820 : constraint_t c;
700 : 4459820 : unsigned int j;
701 : :
702 : 4459820 : graph->implicit_preds = XCNEWVEC (bitmap, graph->size);
703 : 4459820 : graph->preds = XCNEWVEC (bitmap, graph->size);
704 : 4459820 : graph->pointer_label = XCNEWVEC (unsigned int, graph->size);
705 : 4459820 : graph->loc_label = XCNEWVEC (unsigned int, graph->size);
706 : 4459820 : graph->pointed_by = XCNEWVEC (bitmap, graph->size);
707 : 4459820 : graph->points_to = XCNEWVEC (bitmap, graph->size);
708 : 4459820 : graph->eq_rep = XNEWVEC (int, graph->size);
709 : 4459820 : graph->direct_nodes = sbitmap_alloc (graph->size);
710 : 4459820 : graph->address_taken = BITMAP_ALLOC (&predbitmap_obstack);
711 : 4459820 : bitmap_clear (graph->direct_nodes);
712 : :
713 : 458177620 : for (j = 1; j < FIRST_REF_NODE; j++)
714 : : {
715 : 222399080 : if (!get_varinfo (j)->is_special_var)
716 : 200099980 : bitmap_set_bit (graph->direct_nodes, j);
717 : : }
718 : :
719 : 458177620 : for (j = 0; j < graph->size; j++)
720 : 453717800 : graph->eq_rep[j] = -1;
721 : :
722 : 462637440 : for (j = 0; j < varmap.length (); j++)
723 : 226858900 : graph->indirect_cycles[j] = -1;
724 : :
725 : 444467733 : FOR_EACH_VEC_ELT (constraints, i, c)
726 : : {
727 : 440007913 : struct constraint_expr lhs = c->lhs;
728 : 440007913 : struct constraint_expr rhs = c->rhs;
729 : 440007913 : unsigned int lhsvar = lhs.var;
730 : 440007913 : unsigned int rhsvar = rhs.var;
731 : :
732 : 440007913 : if (lhs.type == DEREF)
733 : : {
734 : : /* *x = y. */
735 : 36169829 : if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
736 : : {
737 : 31839123 : if (lhs.var == anything_id)
738 : 0 : add_pred_graph_edge (graph, storedanything_id, rhsvar);
739 : : else
740 : 63678246 : add_pred_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
741 : : }
742 : : }
743 : 403838084 : else if (rhs.type == DEREF)
744 : : {
745 : : /* x = *y */
746 : 48750209 : if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
747 : 26271310 : add_pred_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
748 : : else
749 : 35614554 : bitmap_clear_bit (graph->direct_nodes, lhsvar);
750 : : }
751 : 355087875 : else if (rhs.type == ADDRESSOF)
752 : : {
753 : 89917514 : varinfo_t v;
754 : :
755 : : /* x = &y */
756 : 89917514 : if (graph->points_to[lhsvar] == NULL)
757 : 66679621 : graph->points_to[lhsvar] = BITMAP_ALLOC (&predbitmap_obstack);
758 : 89917514 : bitmap_set_bit (graph->points_to[lhsvar], rhsvar);
759 : :
760 : 89917514 : if (graph->pointed_by[rhsvar] == NULL)
761 : 21573398 : graph->pointed_by[rhsvar] = BITMAP_ALLOC (&predbitmap_obstack);
762 : 89917514 : bitmap_set_bit (graph->pointed_by[rhsvar], lhsvar);
763 : :
764 : : /* Implicitly, *x = y */
765 : 179835028 : add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
766 : :
767 : : /* All related variables are no longer direct nodes. */
768 : 89917514 : bitmap_clear_bit (graph->direct_nodes, rhsvar);
769 : 89917514 : v = get_varinfo (rhsvar);
770 : 89917514 : if (!v->is_full_var)
771 : : {
772 : 7346953 : v = get_varinfo (v->head);
773 : 46558752 : do
774 : : {
775 : 46558752 : bitmap_clear_bit (graph->direct_nodes, v->id);
776 : 46558752 : v = vi_next (v);
777 : : }
778 : 46558752 : while (v != NULL);
779 : : }
780 : 89917514 : bitmap_set_bit (graph->address_taken, rhsvar);
781 : : }
782 : 265170361 : else if (lhsvar > anything_id
783 : 265170361 : && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
784 : : {
785 : : /* x = y */
786 : 203762990 : add_pred_graph_edge (graph, lhsvar, rhsvar);
787 : : /* Implicitly, *x = *y */
788 : 203762990 : add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar,
789 : 203762990 : FIRST_REF_NODE + rhsvar);
790 : : }
791 : 61407371 : else if (lhs.offset != 0 || rhs.offset != 0)
792 : : {
793 : 61216054 : if (rhs.offset != 0)
794 : 61216054 : 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 : 4459820 : }
800 : :
801 : : /* Build the constraint graph, adding successor edges. */
802 : :
803 : : static void
804 : 4459820 : build_succ_graph (void)
805 : : {
806 : 4459820 : unsigned i, t;
807 : 4459820 : constraint_t c;
808 : :
809 : 444467733 : FOR_EACH_VEC_ELT (constraints, i, c)
810 : : {
811 : 440007913 : struct constraint_expr lhs;
812 : 440007913 : struct constraint_expr rhs;
813 : 440007913 : unsigned int lhsvar;
814 : 440007913 : unsigned int rhsvar;
815 : :
816 : 440007913 : if (!c)
817 : 2541977 : continue;
818 : :
819 : 437465936 : lhs = c->lhs;
820 : 437465936 : rhs = c->rhs;
821 : 437465936 : lhsvar = find (lhs.var);
822 : 437465936 : rhsvar = find (rhs.var);
823 : :
824 : 437465936 : if (lhs.type == DEREF)
825 : : {
826 : 36123578 : if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
827 : : {
828 : 31811763 : if (lhs.var == anything_id)
829 : 0 : add_graph_edge (graph, storedanything_id, rhsvar);
830 : : else
831 : 63623526 : add_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
832 : : }
833 : : }
834 : 401342358 : else if (rhs.type == DEREF)
835 : : {
836 : 48749243 : if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
837 : 26269736 : add_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
838 : : }
839 : 352593115 : else if (rhs.type == ADDRESSOF)
840 : : {
841 : : /* x = &y */
842 : 89917514 : gcc_checking_assert (find (rhs.var) == rhs.var);
843 : 89917514 : bitmap_set_bit (get_varinfo (lhsvar)->solution, rhsvar);
844 : : }
845 : 262675601 : else if (lhsvar > anything_id
846 : 262675601 : && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
847 : : {
848 : 153463448 : add_graph_edge (graph, lhsvar, rhsvar);
849 : : }
850 : : }
851 : :
852 : : /* Add edges from STOREDANYTHING to all nodes that can receive pointers. */
853 : 4459820 : t = find (storedanything_id);
854 : 195640160 : for (i = integer_id + 1; i < FIRST_REF_NODE; ++i)
855 : : {
856 : 186720520 : if (get_varinfo (i)->may_have_pointers)
857 : 186697142 : add_graph_edge (graph, find (i), t);
858 : : }
859 : :
860 : : /* Everything stored to ANYTHING also potentially escapes. */
861 : 4459820 : add_graph_edge (graph, find (escaped_id), t);
862 : 4459820 : }
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 : 380050489 : scc_visit (constraint_graph_t graph, class scc_info *si, unsigned int n)
898 : : {
899 : 380050489 : unsigned int i;
900 : 380050489 : bitmap_iterator bi;
901 : 380050489 : unsigned int my_dfs;
902 : :
903 : 380050489 : bitmap_set_bit (si->visited, n);
904 : 380050489 : si->dfs[n] = si->current_index ++;
905 : 380050489 : my_dfs = si->dfs[n];
906 : :
907 : : /* Visit all the successors. */
908 : 645927640 : EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[n], 0, i, bi)
909 : : {
910 : 265877151 : unsigned int w;
911 : :
912 : 531754302 : if (i > LAST_REF_NODE)
913 : : break;
914 : :
915 : 265877151 : w = find (i);
916 : 265877151 : if (bitmap_bit_p (si->deleted, w))
917 : 115705990 : continue;
918 : :
919 : 150171161 : if (!bitmap_bit_p (si->visited, w))
920 : 149900660 : scc_visit (graph, si, w);
921 : :
922 : 150171161 : unsigned int t = find (w);
923 : 150171161 : gcc_checking_assert (find (n) == n);
924 : 150171161 : if (si->dfs[t] < si->dfs[n])
925 : 141473 : si->dfs[n] = si->dfs[t];
926 : : }
927 : :
928 : : /* See if any components have been identified. */
929 : 380050489 : if (si->dfs[n] == my_dfs)
930 : : {
931 : 379909082 : if (si->scc_stack.length () > 0
932 : 379909082 : && si->dfs[si->scc_stack.last ()] >= my_dfs)
933 : : {
934 : 108098 : bitmap scc = BITMAP_ALLOC (NULL);
935 : 108098 : unsigned int lowest_node;
936 : 108098 : bitmap_iterator bi;
937 : :
938 : 108098 : bitmap_set_bit (scc, n);
939 : :
940 : 108098 : while (si->scc_stack.length () != 0
941 : 249505 : && si->dfs[si->scc_stack.last ()] >= my_dfs)
942 : : {
943 : 141407 : unsigned int w = si->scc_stack.pop ();
944 : :
945 : 141407 : bitmap_set_bit (scc, w);
946 : : }
947 : :
948 : 108098 : lowest_node = bitmap_first_set_bit (scc);
949 : 108098 : gcc_assert (lowest_node < FIRST_REF_NODE);
950 : :
951 : : /* Collapse the SCC nodes into a single node, and mark the
952 : : indirect cycles. */
953 : 357603 : EXECUTE_IF_SET_IN_BITMAP (scc, 0, i, bi)
954 : : {
955 : 249505 : if (i < FIRST_REF_NODE)
956 : : {
957 : 126836 : if (unite (lowest_node, i))
958 : 18738 : unify_nodes (graph, lowest_node, i, false);
959 : : }
960 : : else
961 : : {
962 : 122669 : unite (lowest_node, i);
963 : 245338 : graph->indirect_cycles[i - FIRST_REF_NODE] = lowest_node;
964 : : }
965 : : }
966 : 108098 : bitmap_set_bit (si->deleted, lowest_node);
967 : : }
968 : : else
969 : 379800984 : bitmap_set_bit (si->deleted, n);
970 : : }
971 : : else
972 : 141407 : si->scc_stack.safe_push (n);
973 : 380050489 : }
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 : 70395261 : unify_nodes (constraint_graph_t graph, unsigned int to, unsigned int from,
980 : : bool update_changed)
981 : : {
982 : 70395261 : gcc_checking_assert (to != from && find (to) == to);
983 : :
984 : 70395261 : if (dump_file && (dump_flags & TDF_DETAILS))
985 : 1224 : fprintf (dump_file, "Unifying %s to %s\n",
986 : 1224 : get_varinfo (from)->name,
987 : 1224 : get_varinfo (to)->name);
988 : :
989 : 70395261 : if (update_changed)
990 : 346305 : stats.unified_vars_dynamic++;
991 : : else
992 : 70048956 : stats.unified_vars_static++;
993 : :
994 : 70395261 : merge_graph_nodes (graph, to, from);
995 : 70395261 : if (merge_node_constraints (graph, to, from))
996 : : {
997 : 94332 : if (update_changed)
998 : 12449 : 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 : 70313378 : if (update_changed
1005 : 70313378 : && bitmap_clear_bit (changed, from))
1006 : 37173 : bitmap_set_bit (changed, to);
1007 : 70395261 : varinfo_t fromvi = get_varinfo (from);
1008 : 70395261 : if (fromvi->solution)
1009 : : {
1010 : : /* If the solution changes because of the merging, we need to mark
1011 : : the variable as changed. */
1012 : 70395261 : varinfo_t tovi = get_varinfo (to);
1013 : 70395261 : if (bitmap_ior_into (tovi->solution, fromvi->solution))
1014 : : {
1015 : 1939283 : if (update_changed)
1016 : 68355 : bitmap_set_bit (changed, to);
1017 : : }
1018 : :
1019 : 70395261 : BITMAP_FREE (fromvi->solution);
1020 : 70395261 : if (fromvi->oldsolution)
1021 : 216620 : BITMAP_FREE (fromvi->oldsolution);
1022 : :
1023 : 70395261 : if (stats.iterations > 0
1024 : 346305 : && tovi->oldsolution)
1025 : 20035 : BITMAP_FREE (tovi->oldsolution);
1026 : : }
1027 : 70395261 : if (graph->succs[to])
1028 : 2657570 : bitmap_clear_bit (graph->succs[to], to);
1029 : 70395261 : }
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 : 424884468 : 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 : 424884468 : if (get_varinfo (from)->is_special_var)
1041 : 30691858 : return bitmap_ior_into (get_varinfo (to)->solution,
1042 : 61383716 : get_varinfo (from)->solution);
1043 : : /* Merging the solution from ESCAPED needlessly increases
1044 : : the set. Use ESCAPED as representative instead. */
1045 : 394192610 : else if (from == find (escaped_id))
1046 : 35308735 : return bitmap_set_bit (get_varinfo (to)->solution, escaped_id);
1047 : 358883875 : else if (get_varinfo (from)->may_have_pointers
1048 : 358883875 : && add_graph_edge (graph, to, from))
1049 : 116705812 : return bitmap_ior_into (get_varinfo (to)->solution,
1050 : 116705812 : 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 : 69500289 : do_sd_constraint (constraint_graph_t graph, constraint_t c,
1059 : : bitmap delta, bitmap *expanded_delta)
1060 : : {
1061 : 69500289 : unsigned int lhs = c->lhs.var;
1062 : 69500289 : bool flag = false;
1063 : 69500289 : bitmap sol = get_varinfo (lhs)->solution;
1064 : 69500289 : unsigned int j;
1065 : 69500289 : bitmap_iterator bi;
1066 : 69500289 : HOST_WIDE_INT roffset = c->rhs.offset;
1067 : :
1068 : : /* Our IL does not allow this. */
1069 : 69500289 : 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 : 69500289 : if (bitmap_bit_p (delta, anything_id))
1074 : : {
1075 : 690393 : flag |= bitmap_set_bit (sol, anything_id);
1076 : 690393 : 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 : 68809896 : if (roffset == UNKNOWN_OFFSET)
1083 : : {
1084 : 50931971 : delta = solution_set_expand (delta, expanded_delta);
1085 : : /* No further offset processing is necessary. */
1086 : 50931971 : 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 : 310853363 : EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1092 : : {
1093 : 242043467 : varinfo_t v = get_varinfo (j);
1094 : 242043467 : HOST_WIDE_INT fieldoffset = v->offset + roffset;
1095 : 242043467 : unsigned HOST_WIDE_INT size = v->size;
1096 : 242043467 : unsigned int t;
1097 : :
1098 : 242043467 : if (v->is_full_var)
1099 : : ;
1100 : 144146952 : else if (roffset != 0)
1101 : : {
1102 : 5244538 : if (fieldoffset < 0)
1103 : 133358 : v = get_varinfo (v->head);
1104 : : else
1105 : 5111180 : 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 : 243615518 : do
1111 : : {
1112 : 243615518 : t = find (v->id);
1113 : :
1114 : 243615518 : flag |= solve_add_graph_edge (graph, lhs, t);
1115 : :
1116 : 243615518 : if (v->is_full_var
1117 : 145718811 : || v->next == 0)
1118 : : break;
1119 : :
1120 : 118795035 : v = vi_next (v);
1121 : : }
1122 : 118795035 : while (v->offset < fieldoffset + size);
1123 : : }
1124 : :
1125 : 68809896 : done:
1126 : : /* If the LHS solution changed, mark the var as changed. */
1127 : 69500289 : if (flag)
1128 : 27890345 : bitmap_set_bit (changed, lhs);
1129 : 69500289 : }
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 : 56296124 : do_ds_constraint (constraint_t c, bitmap delta, bitmap *expanded_delta)
1136 : : {
1137 : 56296124 : unsigned int rhs = c->rhs.var;
1138 : 56296124 : bitmap sol = get_varinfo (rhs)->solution;
1139 : 56296124 : unsigned int j;
1140 : 56296124 : bitmap_iterator bi;
1141 : 56296124 : HOST_WIDE_INT loff = c->lhs.offset;
1142 : 56296124 : bool escaped_p = false;
1143 : :
1144 : : /* Our IL does not allow this. */
1145 : 56296124 : 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 : 56296124 : if (bitmap_bit_p (sol, anything_id))
1150 : 476495 : 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 : 56296124 : if (bitmap_bit_p (delta, anything_id))
1156 : : {
1157 : 521724 : unsigned t = find (storedanything_id);
1158 : 521724 : if (solve_add_graph_edge (graph, t, rhs))
1159 : 36504 : bitmap_set_bit (changed, t);
1160 : 521724 : 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 : 55774400 : if (loff == UNKNOWN_OFFSET)
1167 : : {
1168 : 2056872 : delta = solution_set_expand (delta, expanded_delta);
1169 : 2056872 : 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 : 272875175 : EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1175 : : {
1176 : 217100775 : varinfo_t v = get_varinfo (j);
1177 : 217100775 : unsigned int t;
1178 : 217100775 : HOST_WIDE_INT fieldoffset = v->offset + loff;
1179 : 217100775 : unsigned HOST_WIDE_INT size = v->size;
1180 : :
1181 : 217100775 : if (v->is_full_var)
1182 : : ;
1183 : 133031755 : else if (loff != 0)
1184 : : {
1185 : 8136514 : if (fieldoffset < 0)
1186 : 5052 : v = get_varinfo (v->head);
1187 : : else
1188 : 8131462 : 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 : 219533601 : do
1194 : : {
1195 : 219533601 : if (v->may_have_pointers)
1196 : : {
1197 : : /* If v is a global variable then this is an escape point. */
1198 : 206889844 : if (v->is_global_var
1199 : 154973888 : && !escaped_p)
1200 : : {
1201 : 44507929 : t = find (escaped_id);
1202 : 44507929 : if (add_graph_edge (graph, t, rhs)
1203 : 58098897 : && bitmap_ior_into (get_varinfo (t)->solution, sol))
1204 : 1329107 : bitmap_set_bit (changed, t);
1205 : : /* Enough to let rhs escape once. */
1206 : : escaped_p = true;
1207 : : }
1208 : :
1209 : 206889844 : if (v->is_special_var)
1210 : : break;
1211 : :
1212 : 180747226 : t = find (v->id);
1213 : :
1214 : 180747226 : if (solve_add_graph_edge (graph, t, rhs))
1215 : 12255141 : bitmap_set_bit (changed, t);
1216 : : }
1217 : :
1218 : 193390983 : if (v->is_full_var
1219 : 135464439 : || v->next == 0)
1220 : : break;
1221 : :
1222 : 110470496 : v = vi_next (v);
1223 : : }
1224 : 110470496 : 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 : 210332010 : do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta,
1233 : : bitmap *expanded_delta)
1234 : : {
1235 : 210332010 : if (c->lhs.type == DEREF)
1236 : : {
1237 : 56296124 : if (c->rhs.type == ADDRESSOF)
1238 : : {
1239 : 0 : gcc_unreachable ();
1240 : : }
1241 : : else
1242 : : {
1243 : : /* *x = y */
1244 : 56296124 : do_ds_constraint (c, delta, expanded_delta);
1245 : : }
1246 : : }
1247 : 154035886 : else if (c->rhs.type == DEREF)
1248 : : {
1249 : : /* x = *y */
1250 : 69500289 : if (!(get_varinfo (c->lhs.var)->is_special_var))
1251 : 69500289 : do_sd_constraint (graph, c, delta, expanded_delta);
1252 : : }
1253 : : else
1254 : : {
1255 : 84535597 : bitmap tmp;
1256 : 84535597 : bool flag = false;
1257 : :
1258 : 84535597 : gcc_checking_assert (c->rhs.type == SCALAR && c->lhs.type == SCALAR
1259 : : && c->rhs.offset != 0 && c->lhs.offset == 0);
1260 : 84535597 : tmp = get_varinfo (c->lhs.var)->solution;
1261 : :
1262 : 84535597 : flag = set_union_with_increment (tmp, delta, c->rhs.offset,
1263 : : expanded_delta);
1264 : :
1265 : 84535597 : if (flag)
1266 : 20754201 : bitmap_set_bit (changed, c->lhs.var);
1267 : : }
1268 : 210332010 : }
1269 : :
1270 : : /* Initialize and return a new SCC info structure. */
1271 : :
1272 : 8919640 : scc_info::scc_info (size_t size) :
1273 : 8919640 : visited (size), deleted (size), current_index (0), scc_stack (1)
1274 : : {
1275 : 8919640 : bitmap_clear (visited);
1276 : 8919640 : bitmap_clear (deleted);
1277 : 8919640 : node_mapping = XNEWVEC (unsigned int, size);
1278 : 8919640 : dfs = XCNEWVEC (unsigned int, size);
1279 : :
1280 : 916355240 : for (size_t i = 0; i < size; i++)
1281 : 907435600 : node_mapping[i] = i;
1282 : 8919640 : }
1283 : :
1284 : : /* Free an SCC info structure pointed to by SI. */
1285 : :
1286 : 8919640 : scc_info::~scc_info ()
1287 : : {
1288 : 8919640 : free (node_mapping);
1289 : 8919640 : free (dfs);
1290 : 8919640 : }
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 : 4459820 : find_indirect_cycles (constraint_graph_t graph)
1302 : : {
1303 : 4459820 : unsigned int i;
1304 : 4459820 : unsigned int size = graph->size;
1305 : 4459820 : scc_info si (size);
1306 : :
1307 : 911895420 : for (i = 0; i < MIN (LAST_REF_NODE, size); i++)
1308 : 449257980 : if (!bitmap_bit_p (si.visited, i) && find (i) == i)
1309 : 230149829 : scc_visit (graph, &si, i);
1310 : 4459820 : }
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 : 386251984 : topo_visit (constraint_graph_t graph, vec<unsigned> &topo_order,
1317 : : sbitmap visited, unsigned int n)
1318 : : {
1319 : 386251984 : bitmap_iterator bi;
1320 : 386251984 : unsigned int j;
1321 : :
1322 : 386251984 : bitmap_set_bit (visited, n);
1323 : :
1324 : 386251984 : if (graph->succs[n])
1325 : 940634456 : EXECUTE_IF_SET_IN_BITMAP (graph->succs[n], 0, j, bi)
1326 : : {
1327 : 742017357 : unsigned k = find (j);
1328 : 742017357 : if (!bitmap_bit_p (visited, k))
1329 : 282469540 : topo_visit (graph, topo_order, visited, k);
1330 : : }
1331 : :
1332 : : /* Also consider copy with offset complex constraints as implicit edges. */
1333 : 825977998 : for (auto c : graph->complex[n])
1334 : : {
1335 : : /* Constraints are ordered so that SCALAR = SCALAR appear first. */
1336 : 255847799 : if (c->lhs.type != SCALAR || c->rhs.type != SCALAR)
1337 : : break;
1338 : 142238976 : gcc_checking_assert (c->rhs.var == n);
1339 : 142238976 : unsigned k = find (c->lhs.var);
1340 : 142238976 : if (!bitmap_bit_p (visited, k))
1341 : 36333512 : topo_visit (graph, topo_order, visited, k);
1342 : : }
1343 : :
1344 : 386251984 : topo_order.quick_push (n);
1345 : 386251984 : }
1346 : :
1347 : : /* Compute a topological ordering for GRAPH, and return the result. */
1348 : :
1349 : : static auto_vec<unsigned>
1350 : 7889852 : compute_topo_order (constraint_graph_t graph)
1351 : : {
1352 : 7889852 : unsigned int i;
1353 : 7889852 : unsigned int size = graph->size;
1354 : :
1355 : 7889852 : auto_sbitmap visited (size);
1356 : 7889852 : 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 : 7889852 : auto_vec<unsigned> tail (size);
1364 : 7889852 : topo_visit (graph, tail, visited, find (escaped_id));
1365 : :
1366 : 7889852 : auto_vec<unsigned> topo_order (size);
1367 : :
1368 : 587670950 : for (i = 0; i != size; ++i)
1369 : 571891246 : if (!bitmap_bit_p (visited, i) && find (i) == i)
1370 : 59559080 : topo_visit (graph, topo_order, visited, i);
1371 : :
1372 : 7889852 : topo_order.splice (tail);
1373 : 7889852 : return topo_order;
1374 : 7889852 : }
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 : 185581101 : equiv_class_hasher::hash (const equiv_class_label *ecl)
1408 : : {
1409 : 185581101 : return ecl->hashcode;
1410 : : }
1411 : :
1412 : : /* Equality function for two equiv_class_label_t's. */
1413 : :
1414 : : inline bool
1415 : 241223479 : equiv_class_hasher::equal (const equiv_class_label *eql1,
1416 : : const equiv_class_label *eql2)
1417 : : {
1418 : 241223479 : return (eql1->hashcode == eql2->hashcode
1419 : 241223479 : && 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 : 193899694 : equiv_class_lookup_or_add (hash_table<equiv_class_hasher> *table,
1430 : : bitmap labels)
1431 : : {
1432 : 193899694 : equiv_class_label **slot;
1433 : 193899694 : equiv_class_label ecl;
1434 : :
1435 : 193899694 : ecl.labels = labels;
1436 : 193899694 : ecl.hashcode = bitmap_hash (labels);
1437 : 193899694 : slot = table->find_slot (&ecl, INSERT);
1438 : 193899694 : if (!*slot)
1439 : : {
1440 : 161987400 : *slot = XOBNEW (&equiv_class_obstack, struct equiv_class_label);
1441 : 161987400 : (*slot)->labels = labels;
1442 : 161987400 : (*slot)->hashcode = ecl.hashcode;
1443 : 161987400 : (*slot)->equivalence_class = 0;
1444 : : }
1445 : :
1446 : 193899694 : 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 : 265808429 : condense_visit (constraint_graph_t graph, class scc_info *si, unsigned int n)
1504 : : {
1505 : 265808429 : unsigned int i;
1506 : 265808429 : bitmap_iterator bi;
1507 : 265808429 : unsigned int my_dfs;
1508 : :
1509 : 265808429 : gcc_checking_assert (si->node_mapping[n] == n);
1510 : 265808429 : bitmap_set_bit (si->visited, n);
1511 : 265808429 : si->dfs[n] = si->current_index ++;
1512 : 265808429 : my_dfs = si->dfs[n];
1513 : :
1514 : : /* Visit all the successors. */
1515 : 489354776 : EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
1516 : : {
1517 : 223546347 : unsigned int w = si->node_mapping[i];
1518 : :
1519 : 223546347 : if (bitmap_bit_p (si->deleted, w))
1520 : 141924110 : continue;
1521 : :
1522 : 81622237 : if (!bitmap_bit_p (si->visited, w))
1523 : 80160270 : condense_visit (graph, si, w);
1524 : :
1525 : 81622237 : unsigned int t = si->node_mapping[w];
1526 : 81622237 : gcc_checking_assert (si->node_mapping[n] == n);
1527 : 81622237 : if (si->dfs[t] < si->dfs[n])
1528 : 2651416 : si->dfs[n] = si->dfs[t];
1529 : : }
1530 : :
1531 : : /* Visit all the implicit predecessors. */
1532 : 324758142 : EXECUTE_IF_IN_NONNULL_BITMAP (graph->implicit_preds[n], 0, i, bi)
1533 : : {
1534 : 58949713 : unsigned int w = si->node_mapping[i];
1535 : :
1536 : 58949713 : if (bitmap_bit_p (si->deleted, w))
1537 : 19533067 : continue;
1538 : :
1539 : 39416646 : if (!bitmap_bit_p (si->visited, w))
1540 : 34584686 : condense_visit (graph, si, w);
1541 : :
1542 : 39416646 : unsigned int t = si->node_mapping[w];
1543 : 39416646 : gcc_assert (si->node_mapping[n] == n);
1544 : 39416646 : if (si->dfs[t] < si->dfs[n])
1545 : 8297497 : si->dfs[n] = si->dfs[t];
1546 : : }
1547 : :
1548 : : /* See if any components have been identified. */
1549 : 265808429 : if (si->dfs[n] == my_dfs)
1550 : : {
1551 : 255019300 : if (si->scc_stack.length () != 0
1552 : 255019300 : && 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 : 10789129 : do
1558 : : {
1559 : 10789129 : --first;
1560 : 10789129 : unsigned int w = si->scc_stack[first];
1561 : 10789129 : si->node_mapping[w] = n;
1562 : 10789129 : if (!bitmap_bit_p (graph->direct_nodes, w))
1563 : 8671616 : direct_p = false;
1564 : : }
1565 : : while (first > 0
1566 : 12144160 : && si->dfs[si->scc_stack[first - 1]] >= my_dfs);
1567 : 1355031 : if (!direct_p)
1568 : 868593 : bitmap_clear_bit (graph->direct_nodes, n);
1569 : :
1570 : : /* Want to reduce to node n, push that first. */
1571 : 1355031 : si->scc_stack.reserve (1);
1572 : 1355031 : si->scc_stack.quick_push (si->scc_stack[first]);
1573 : 1355031 : si->scc_stack[first] = n;
1574 : :
1575 : 1355031 : unsigned scc_size = si->scc_stack.length () - first;
1576 : 1355031 : unsigned split = scc_size / 2;
1577 : 1355031 : unsigned carry = scc_size - split * 2;
1578 : 4778937 : while (split > 0)
1579 : : {
1580 : 14213035 : for (unsigned i = 0; i < split; ++i)
1581 : : {
1582 : 10789129 : unsigned a = si->scc_stack[first + i];
1583 : 10789129 : unsigned b = si->scc_stack[first + split + carry + i];
1584 : :
1585 : : /* Unify our nodes. */
1586 : 10789129 : if (graph->preds[b])
1587 : : {
1588 : 4730320 : if (!graph->preds[a])
1589 : 968795 : std::swap (graph->preds[a], graph->preds[b]);
1590 : : else
1591 : 3761525 : bitmap_ior_into_and_free (graph->preds[a],
1592 : : &graph->preds[b]);
1593 : : }
1594 : 10789129 : if (graph->implicit_preds[b])
1595 : : {
1596 : 8567150 : if (!graph->implicit_preds[a])
1597 : 884515 : std::swap (graph->implicit_preds[a],
1598 : : graph->implicit_preds[b]);
1599 : : else
1600 : 7682635 : bitmap_ior_into_and_free (graph->implicit_preds[a],
1601 : : &graph->implicit_preds[b]);
1602 : : }
1603 : 10789129 : if (graph->points_to[b])
1604 : : {
1605 : 520957 : if (!graph->points_to[a])
1606 : 229874 : std::swap (graph->points_to[a], graph->points_to[b]);
1607 : : else
1608 : 291083 : bitmap_ior_into_and_free (graph->points_to[a],
1609 : : &graph->points_to[b]);
1610 : : }
1611 : : }
1612 : 3423906 : unsigned remain = split + carry;
1613 : 3423906 : split = remain / 2;
1614 : 3423906 : carry = remain - split * 2;
1615 : : }
1616 : : /* Actually pop the SCC. */
1617 : 1355031 : si->scc_stack.truncate (first);
1618 : : }
1619 : 255019300 : bitmap_set_bit (si->deleted, n);
1620 : : }
1621 : : else
1622 : 10789129 : si->scc_stack.safe_push (n);
1623 : 265808429 : }
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 : 231544741 : label_visit (constraint_graph_t graph, class scc_info *si, unsigned int n)
1646 : : {
1647 : 231544741 : unsigned int i, first_pred;
1648 : 231544741 : bitmap_iterator bi;
1649 : :
1650 : 231544741 : bitmap_set_bit (si->visited, n);
1651 : :
1652 : : /* Label and union our incoming edges's points to sets. */
1653 : 231544741 : first_pred = -1U;
1654 : 449799053 : EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
1655 : : {
1656 : 218254312 : unsigned int w = si->node_mapping[i];
1657 : 218254312 : if (!bitmap_bit_p (si->visited, w))
1658 : 75475869 : label_visit (graph, si, w);
1659 : :
1660 : : /* Skip unused edges. */
1661 : 218254312 : if (w == n || graph->pointer_label[w] == 0)
1662 : 5270533 : continue;
1663 : :
1664 : 212983779 : if (graph->points_to[w])
1665 : : {
1666 : 212983779 : if (!graph->points_to[n])
1667 : : {
1668 : 148003185 : if (first_pred == -1U)
1669 : : first_pred = w;
1670 : : else
1671 : : {
1672 : 41208464 : graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
1673 : 41208464 : bitmap_ior (graph->points_to[n],
1674 : 41208464 : graph->points_to[first_pred],
1675 : 41208464 : graph->points_to[w]);
1676 : : }
1677 : : }
1678 : : else
1679 : 64980594 : 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 : 231544741 : if (!bitmap_bit_p (graph->direct_nodes, n))
1685 : : {
1686 : 112097386 : if (!graph->points_to[n])
1687 : : {
1688 : 64729294 : graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
1689 : 64729294 : if (first_pred != -1U)
1690 : 26212467 : bitmap_copy (graph->points_to[n], graph->points_to[first_pred]);
1691 : : }
1692 : 224194772 : bitmap_set_bit (graph->points_to[n], FIRST_REF_NODE + n);
1693 : 112097386 : graph->pointer_label[n] = pointer_equiv_class++;
1694 : 112097386 : equiv_class_label_t ecl;
1695 : 224194772 : ecl = equiv_class_lookup_or_add (pointer_equiv_class_table,
1696 : 112097386 : graph->points_to[n]);
1697 : 112097386 : ecl->equivalence_class = graph->pointer_label[n];
1698 : 171315831 : return;
1699 : : }
1700 : :
1701 : : /* If there was only a single non-empty predecessor the pointer equiv
1702 : : class is the same. */
1703 : 119447355 : if (!graph->points_to[n])
1704 : : {
1705 : 59218445 : if (first_pred != -1U)
1706 : : {
1707 : 39373790 : graph->pointer_label[n] = graph->pointer_label[first_pred];
1708 : 39373790 : graph->points_to[n] = graph->points_to[first_pred];
1709 : : }
1710 : 59218445 : return;
1711 : : }
1712 : :
1713 : 60228910 : if (!bitmap_empty_p (graph->points_to[n]))
1714 : : {
1715 : 60228910 : equiv_class_label_t ecl;
1716 : 60228910 : ecl = equiv_class_lookup_or_add (pointer_equiv_class_table,
1717 : : graph->points_to[n]);
1718 : 60228910 : if (ecl->equivalence_class == 0)
1719 : 28757489 : ecl->equivalence_class = pointer_equiv_class++;
1720 : : else
1721 : : {
1722 : 31471421 : BITMAP_FREE (graph->points_to[n]);
1723 : 31471421 : graph->points_to[n] = ecl->labels;
1724 : : }
1725 : 60228910 : 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 : 4459820 : perform_var_substitution (constraint_graph_t graph)
1810 : : {
1811 : 4459820 : unsigned int i;
1812 : 4459820 : unsigned int size = graph->size;
1813 : 4459820 : scc_info *si = new scc_info (size);
1814 : :
1815 : 4459820 : bitmap_obstack_initialize (&iteration_obstack);
1816 : 4459820 : gcc_obstack_init (&equiv_class_obstack);
1817 : 4459820 : pointer_equiv_class_table = new hash_table<equiv_class_hasher> (511);
1818 : 4459820 : location_equiv_class_table
1819 : 4459820 : = new hash_table<equiv_class_hasher> (511);
1820 : 4459820 : pointer_equiv_class = 1;
1821 : 4459820 : 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 : 226858900 : for (i = 1; i < FIRST_REF_NODE; i++)
1826 : 222399080 : if (!bitmap_bit_p (si->visited, si->node_mapping[i]))
1827 : 151063473 : condense_visit (graph, si, si->node_mapping[i]);
1828 : :
1829 : 4459820 : 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 : 4459820 : bitmap_clear (si->visited);
1838 : : /* Actually the label the nodes for pointer equivalences. */
1839 : 458177620 : for (i = 1; i < FIRST_REF_NODE; i++)
1840 : 222399080 : if (!bitmap_bit_p (si->visited, si->node_mapping[i]))
1841 : 156068872 : label_visit (graph, si, si->node_mapping[i]);
1842 : :
1843 : : /* Calculate location equivalence labels. */
1844 : 226858900 : for (i = 1; i < FIRST_REF_NODE; i++)
1845 : : {
1846 : 222399080 : bitmap pointed_by;
1847 : 222399080 : bitmap_iterator bi;
1848 : 222399080 : unsigned int j;
1849 : :
1850 : 222399080 : if (!graph->pointed_by[i])
1851 : 200825682 : continue;
1852 : 21573398 : pointed_by = BITMAP_ALLOC (&iteration_obstack);
1853 : :
1854 : : /* Translate the pointed-by mapping for pointer equivalence
1855 : : labels. */
1856 : 97196442 : EXECUTE_IF_SET_IN_BITMAP (graph->pointed_by[i], 0, j, bi)
1857 : : {
1858 : 75623044 : bitmap_set_bit (pointed_by,
1859 : 75623044 : graph->pointer_label[si->node_mapping[j]]);
1860 : : }
1861 : : /* The original pointed_by is now dead. */
1862 : 21573398 : BITMAP_FREE (graph->pointed_by[i]);
1863 : :
1864 : : /* Look up the location equivalence label if one exists, or make
1865 : : one otherwise. */
1866 : 21573398 : equiv_class_label_t ecl;
1867 : 21573398 : ecl = equiv_class_lookup_or_add (location_equiv_class_table, pointed_by);
1868 : 21573398 : if (ecl->equivalence_class == 0)
1869 : 21132525 : ecl->equivalence_class = location_equiv_class++;
1870 : : else
1871 : : {
1872 : 440873 : if (dump_file && (dump_flags & TDF_DETAILS))
1873 : 53 : fprintf (dump_file, "Found location equivalence for node %s\n",
1874 : 53 : get_varinfo (i)->name);
1875 : 440873 : BITMAP_FREE (pointed_by);
1876 : : }
1877 : 21573398 : graph->loc_label[i] = ecl->equivalence_class;
1878 : :
1879 : : }
1880 : :
1881 : 4459820 : if (dump_file && (dump_flags & TDF_DETAILS))
1882 : 6771 : for (i = 1; i < FIRST_REF_NODE; i++)
1883 : : {
1884 : 6472 : unsigned j = si->node_mapping[i];
1885 : 6472 : 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 : 9941 : fprintf (dump_file,
1905 : : "Equivalence classes for %s node id %d ",
1906 : 6451 : bitmap_bit_p (graph->direct_nodes, i)
1907 : : ? "direct" : "indirect", i);
1908 : 6451 : if (i < FIRST_REF_NODE)
1909 : 6451 : 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 : 6451 : fprintf (dump_file,
1914 : : ": pointer %d, location %d\n",
1915 : 6451 : graph->pointer_label[i], graph->loc_label[i]);
1916 : : }
1917 : : }
1918 : :
1919 : : /* Quickly eliminate our non-pointer variables. */
1920 : :
1921 : 226858900 : for (i = 1; i < FIRST_REF_NODE; i++)
1922 : : {
1923 : 222399080 : unsigned int node = si->node_mapping[i];
1924 : :
1925 : 222399080 : if (graph->pointer_label[node] == 0)
1926 : : {
1927 : 19846098 : if (dump_file && (dump_flags & TDF_DETAILS))
1928 : 921 : fprintf (dump_file,
1929 : : "%s is a non-pointer variable, eliminating edges.\n",
1930 : 921 : get_varinfo (node)->name);
1931 : 19846098 : stats.nonpointer_vars++;
1932 : 19846098 : clear_edges_for_node (graph, node);
1933 : : }
1934 : : }
1935 : :
1936 : 4459820 : return si;
1937 : : }
1938 : :
1939 : : /* Free information that was only necessary for variable
1940 : : substitution. */
1941 : :
1942 : : static void
1943 : 4459820 : free_var_substitution_info (class scc_info *si)
1944 : : {
1945 : 4459820 : delete si;
1946 : 4459820 : free (graph->pointer_label);
1947 : 4459820 : free (graph->loc_label);
1948 : 4459820 : free (graph->pointed_by);
1949 : 4459820 : free (graph->points_to);
1950 : 4459820 : free (graph->eq_rep);
1951 : 4459820 : sbitmap_free (graph->direct_nodes);
1952 : 4459820 : delete pointer_equiv_class_table;
1953 : 4459820 : pointer_equiv_class_table = NULL;
1954 : 4459820 : delete location_equiv_class_table;
1955 : 4459820 : location_equiv_class_table = NULL;
1956 : 4459820 : obstack_free (&equiv_class_obstack, NULL);
1957 : 4459820 : bitmap_obstack_release (&iteration_obstack);
1958 : 4459820 : }
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 : 874931872 : 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 : 874931872 : if (!bitmap_bit_p (graph->address_taken, node))
1973 : : {
1974 : 680718358 : gcc_checking_assert (label < graph->size);
1975 : :
1976 : 680718358 : if (graph->eq_rep[label] != -1)
1977 : : {
1978 : : /* Unify the two variables since we know they are equivalent. */
1979 : 576561871 : if (unite (graph->eq_rep[label], node))
1980 : 67715756 : unify_nodes (graph, graph->eq_rep[label], node, false);
1981 : 576561871 : return graph->eq_rep[label];
1982 : : }
1983 : : else
1984 : : {
1985 : 104156487 : graph->eq_rep[label] = node;
1986 : 104156487 : graph->pe_rep[label] = node;
1987 : : }
1988 : : }
1989 : : else
1990 : : {
1991 : 194213514 : gcc_checking_assert (label < graph->size);
1992 : 194213514 : graph->pe[node] = label;
1993 : 194213514 : if (graph->pe_rep[label] == -1)
1994 : 21478367 : 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 : 4459820 : unite_pointer_equivalences (constraint_graph_t graph)
2006 : : {
2007 : 4459820 : unsigned int i;
2008 : :
2009 : : /* Go through the pointer equivalences and unite them to their
2010 : : representative, if they aren't already. */
2011 : 226858900 : for (i = 1; i < FIRST_REF_NODE; i++)
2012 : : {
2013 : 222399080 : unsigned int label = graph->pe[i];
2014 : 222399080 : if (label)
2015 : : {
2016 : 21573398 : int label_rep = graph->pe_rep[label];
2017 : :
2018 : 21573398 : if (label_rep == -1)
2019 : 0 : continue;
2020 : :
2021 : 21573398 : label_rep = find (label_rep);
2022 : 21573398 : if (label_rep >= 0 && unite (label_rep, find (i)))
2023 : 2314462 : unify_nodes (graph, label_rep, i, false);
2024 : : }
2025 : : }
2026 : 4459820 : }
2027 : :
2028 : : /* Move complex constraints to the GRAPH nodes they belong to. */
2029 : :
2030 : : static void
2031 : 4459820 : move_complex_constraints (constraint_graph_t graph)
2032 : : {
2033 : 4459820 : int i;
2034 : 4459820 : constraint_t c;
2035 : :
2036 : 444467733 : FOR_EACH_VEC_ELT (constraints, i, c)
2037 : : {
2038 : 440007913 : if (c)
2039 : : {
2040 : 437465936 : struct constraint_expr lhs = c->lhs;
2041 : 437465936 : struct constraint_expr rhs = c->rhs;
2042 : :
2043 : 437465936 : if (lhs.type == DEREF)
2044 : : {
2045 : 36123578 : insert_into_complex (graph, lhs.var, c);
2046 : : }
2047 : 401342358 : else if (rhs.type == DEREF)
2048 : : {
2049 : 48749243 : if (!(get_varinfo (lhs.var)->is_special_var))
2050 : 48749237 : insert_into_complex (graph, rhs.var, c);
2051 : : }
2052 : 352593115 : else if (rhs.type != ADDRESSOF && lhs.var > anything_id
2053 : 262520282 : && (lhs.offset != 0 || rhs.offset != 0))
2054 : : {
2055 : 60225473 : insert_into_complex (graph, rhs.var, c);
2056 : : }
2057 : : }
2058 : : }
2059 : 4459820 : }
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 : 4459820 : rewrite_constraints (constraint_graph_t graph,
2067 : : class scc_info *si)
2068 : : {
2069 : 4459820 : int i;
2070 : 4459820 : constraint_t c;
2071 : :
2072 : 4459820 : if (flag_checking)
2073 : : {
2074 : 458174472 : for (unsigned int j = 0; j < graph->size; j++)
2075 : 453714712 : gcc_assert (find (j) == j);
2076 : : }
2077 : :
2078 : 444467733 : FOR_EACH_VEC_ELT (constraints, i, c)
2079 : : {
2080 : 440007913 : struct constraint_expr lhs = c->lhs;
2081 : 440007913 : struct constraint_expr rhs = c->rhs;
2082 : 440007913 : unsigned int lhsvar = find (lhs.var);
2083 : 440007913 : unsigned int rhsvar = find (rhs.var);
2084 : 440007913 : unsigned int lhsnode, rhsnode;
2085 : 440007913 : unsigned int lhslabel, rhslabel;
2086 : :
2087 : 440007913 : lhsnode = si->node_mapping[lhsvar];
2088 : 440007913 : rhsnode = si->node_mapping[rhsvar];
2089 : 440007913 : lhslabel = graph->pointer_label[lhsnode];
2090 : 440007913 : rhslabel = graph->pointer_label[rhsnode];
2091 : :
2092 : : /* See if it is really a non-pointer variable, and if so, ignore
2093 : : the constraint. */
2094 : 440007913 : if (lhslabel == 0)
2095 : : {
2096 : 784164 : 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 : 784164 : constraints[i] = NULL;
2106 : 2541977 : continue;
2107 : : }
2108 : :
2109 : 439223749 : if (rhslabel == 0)
2110 : : {
2111 : 1757813 : 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 : 1757813 : constraints[i] = NULL;
2121 : 1757813 : continue;
2122 : : }
2123 : :
2124 : 437465936 : lhsvar = find_equivalent_node (graph, lhsvar, lhslabel);
2125 : 437465936 : rhsvar = find_equivalent_node (graph, rhsvar, rhslabel);
2126 : 437465936 : c->lhs.var = lhsvar;
2127 : 437465936 : c->rhs.var = rhsvar;
2128 : : }
2129 : 4459820 : }
2130 : :
2131 : : /* Eliminate indirect cycles involving NODE. Return true if NODE was
2132 : : part of an SCC, false otherwise. */
2133 : :
2134 : : static bool
2135 : 385938212 : eliminate_indirect_cycles (unsigned int node)
2136 : : {
2137 : 385938212 : if (graph->indirect_cycles[node] != -1
2138 : 386268200 : && !bitmap_empty_p (get_varinfo (node)->solution))
2139 : : {
2140 : 297459 : unsigned int i;
2141 : 297459 : auto_vec<unsigned> queue;
2142 : 297459 : int queuepos;
2143 : 297459 : unsigned int to = find (graph->indirect_cycles[node]);
2144 : 297459 : 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 : 1614776 : EXECUTE_IF_SET_IN_BITMAP (get_varinfo (node)->solution, 0, i, bi)
2151 : : {
2152 : 1317317 : if (find (i) == i && i != to)
2153 : : {
2154 : 346305 : if (unite (to, i))
2155 : 346305 : queue.safe_push (i);
2156 : : }
2157 : : }
2158 : :
2159 : 346305 : for (queuepos = 0;
2160 : 643764 : queue.iterate (queuepos, &i);
2161 : : queuepos++)
2162 : : {
2163 : 346305 : unify_nodes (graph, to, i, true);
2164 : : }
2165 : 297459 : return true;
2166 : 297459 : }
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 : 4459820 : solve_graph (constraint_graph_t graph)
2179 : : {
2180 : 4459820 : unsigned int size = graph->size;
2181 : 4459820 : unsigned int i;
2182 : 4459820 : bitmap pts;
2183 : :
2184 : 4459820 : changed = BITMAP_ALLOC (NULL);
2185 : :
2186 : : /* Mark all initial non-collapsed nodes as changed. */
2187 : 226858900 : for (i = 1; i < size; i++)
2188 : : {
2189 : 222399080 : varinfo_t ivi = get_varinfo (i);
2190 : 374749204 : if (find (i) == i && !bitmap_empty_p (ivi->solution)
2191 : 275183026 : && ((graph->succs[i] && !bitmap_empty_p (graph->succs[i]))
2192 : 230185408 : || graph->complex[i].length () > 0))
2193 : 33601424 : bitmap_set_bit (changed, i);
2194 : : }
2195 : :
2196 : : /* Allocate a bitmap to be used to store the changed bits. */
2197 : 4459820 : pts = BITMAP_ALLOC (&pta_obstack);
2198 : :
2199 : 16809492 : while (!bitmap_empty_p (changed))
2200 : : {
2201 : 7889852 : unsigned int i;
2202 : 7889852 : stats.iterations++;
2203 : :
2204 : 7889852 : bitmap_obstack_initialize (&iteration_obstack);
2205 : :
2206 : 7889852 : auto_vec<unsigned> topo_order = compute_topo_order (graph);
2207 : 402031688 : while (topo_order.length () != 0)
2208 : : {
2209 : 386251984 : i = topo_order.pop ();
2210 : :
2211 : : /* If this variable is not a representative, skip it. */
2212 : 386251984 : if (find (i) != i)
2213 : 313772 : continue;
2214 : :
2215 : : /* In certain indirect cycle cases, we may merge this
2216 : : variable to another. */
2217 : 385938212 : if (eliminate_indirect_cycles (i) && find (i) != i)
2218 : 53 : 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 : 528500400 : while (bitmap_clear_bit (changed, i))
2230 : : {
2231 : 142868223 : bitmap solution;
2232 : 142868223 : vec<constraint_t> &complex = graph->complex[i];
2233 : 142868223 : varinfo_t vi = get_varinfo (i);
2234 : 142868223 : bool solution_empty;
2235 : :
2236 : : /* Compute the changed set of solution bits. If anything
2237 : : is in the solution just propagate that. */
2238 : 142868223 : 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 : 2785024 : if (vi->oldsolution
2244 : 2785024 : && bitmap_bit_p (vi->oldsolution, anything_id))
2245 : : break;
2246 : 2479042 : bitmap_copy (pts, get_varinfo (find (anything_id))->solution);
2247 : : }
2248 : 140083199 : else if (vi->oldsolution)
2249 : 36407101 : bitmap_and_compl (pts, vi->solution, vi->oldsolution);
2250 : : else
2251 : 103676098 : bitmap_copy (pts, vi->solution);
2252 : :
2253 : 142562241 : if (bitmap_empty_p (pts))
2254 : : break;
2255 : :
2256 : 142562241 : if (vi->oldsolution)
2257 : 37626502 : bitmap_ior_into (vi->oldsolution, pts);
2258 : : else
2259 : : {
2260 : 104935739 : vi->oldsolution = BITMAP_ALLOC (&oldpta_obstack);
2261 : 104935739 : bitmap_copy (vi->oldsolution, pts);
2262 : : }
2263 : :
2264 : 142562241 : solution = vi->solution;
2265 : 142562241 : solution_empty = bitmap_empty_p (solution);
2266 : :
2267 : : /* Process the complex constraints. */
2268 : 142562241 : hash_set<constraint_t> *cvisited = nullptr;
2269 : 142562241 : if (flag_checking)
2270 : 142561556 : cvisited = new hash_set<constraint_t>;
2271 : 142562241 : bitmap expanded_pts = NULL;
2272 : 353195363 : for (unsigned j = 0; j < complex.length (); ++j)
2273 : : {
2274 : 210633122 : 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 : 210633122 : unsigned int new_lhs = find (c->lhs.var);
2281 : 210633122 : unsigned int new_rhs = find (c->rhs.var);
2282 : 210633122 : if (c->lhs.var != new_lhs || c->rhs.var != new_rhs)
2283 : : {
2284 : 1609346 : constraint tem = *c;
2285 : 1609346 : tem.lhs.var = new_lhs;
2286 : 1609346 : tem.rhs.var = new_rhs;
2287 : 1609346 : unsigned int place
2288 : 1609346 : = complex.lower_bound (&tem, constraint_less);
2289 : 1609346 : c->lhs.var = new_lhs;
2290 : 1609346 : c->rhs.var = new_rhs;
2291 : 1609346 : if (place != j)
2292 : : {
2293 : 1597133 : complex.ordered_remove (j);
2294 : 1597133 : if (j < place)
2295 : 1579571 : --place;
2296 : 1597133 : if (place < complex.length ())
2297 : : {
2298 : 390109 : if (constraint_equal (*complex[place], *c))
2299 : : {
2300 : 36052 : j--;
2301 : 301112 : continue;
2302 : : }
2303 : : else
2304 : 354057 : complex.safe_insert (place, c);
2305 : : }
2306 : : else
2307 : 1207024 : complex.quick_push (c);
2308 : 1561081 : if (place > j)
2309 : : {
2310 : 265060 : j--;
2311 : 265060 : 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 : 210332010 : if (cvisited && cvisited->add (c))
2321 : 0 : gcc_unreachable ();
2322 : 210332010 : if (!solution_empty || c->lhs.type != DEREF)
2323 : 210332010 : do_complex_constraint (graph, c, pts, &expanded_pts);
2324 : : }
2325 : 142562241 : if (cvisited)
2326 : : {
2327 : : /* When checking, verify the order of constraints is
2328 : : maintained and each constraint is evaluated exactly
2329 : : once. */
2330 : 271624463 : for (unsigned j = 1; j < complex.length (); ++j)
2331 : 129062907 : gcc_assert (constraint_less (complex[j-1], complex[j]));
2332 : 223829599 : gcc_assert (cvisited->elements () == complex.length ());
2333 : 142561556 : delete cvisited;
2334 : : }
2335 : 142562241 : BITMAP_FREE (expanded_pts);
2336 : :
2337 : 142562241 : solution_empty = bitmap_empty_p (solution);
2338 : :
2339 : 142562241 : if (!solution_empty)
2340 : : {
2341 : 142562241 : bitmap_iterator bi;
2342 : 142562241 : unsigned eff_escaped_id = find (escaped_id);
2343 : 142562241 : unsigned j;
2344 : :
2345 : : /* Propagate solution to all successors. */
2346 : 142562241 : unsigned to_remove = ~0U;
2347 : 360854404 : EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i],
2348 : : 0, j, bi)
2349 : : {
2350 : 218292163 : if (to_remove != ~0U)
2351 : : {
2352 : 2268215 : bitmap_clear_bit (graph->succs[i], to_remove);
2353 : 2268215 : to_remove = ~0U;
2354 : : }
2355 : 218292163 : unsigned int to = find (j);
2356 : 218292163 : if (to != j)
2357 : : {
2358 : : /* Update the succ graph, avoiding duplicate
2359 : : work. */
2360 : 2235937 : to_remove = j;
2361 : 2235937 : if (! bitmap_set_bit (graph->succs[i], to))
2362 : 902474 : 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 : 217389689 : if (to == i)
2370 : : {
2371 : 175168 : to_remove = j;
2372 : 175168 : continue;
2373 : : }
2374 : : /* Early node unification can lead to edges from
2375 : : escaped - remove them. */
2376 : 217214521 : if (i == eff_escaped_id)
2377 : : {
2378 : 175277 : to_remove = j;
2379 : 175277 : if (bitmap_set_bit (get_varinfo (to)->solution,
2380 : : escaped_id))
2381 : 95785 : bitmap_set_bit (changed, to);
2382 : 175277 : continue;
2383 : : }
2384 : :
2385 : 217039244 : if (bitmap_ior_into (get_varinfo (to)->solution, pts))
2386 : 96454587 : bitmap_set_bit (changed, to);
2387 : : }
2388 : 100125230 : if (to_remove != ~0U)
2389 : 217527 : bitmap_clear_bit (graph->succs[i], to_remove);
2390 : : }
2391 : : }
2392 : : }
2393 : 7889852 : bitmap_obstack_release (&iteration_obstack);
2394 : 7889852 : }
2395 : :
2396 : 4459820 : BITMAP_FREE (pts);
2397 : 4459820 : BITMAP_FREE (changed);
2398 : 4459820 : bitmap_obstack_release (&oldpta_obstack);
2399 : 4459820 : }
2400 : :
2401 : : void
2402 : 4459820 : delete_graph (void)
2403 : : {
2404 : 4459820 : unsigned int i;
2405 : 231318720 : for (i = 0; i < graph->size; i++)
2406 : 226858900 : graph->complex[i].release ();
2407 : 4459820 : free (graph->complex);
2408 : :
2409 : 4459820 : free (graph->succs);
2410 : 4459820 : free (graph->pe);
2411 : 4459820 : free (graph->pe_rep);
2412 : 4459820 : 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 : 4459820 : free (graph);
2416 : 4459820 : }
2417 : :
2418 : : /* Remove the REF and ADDRESS edges from GRAPH, as well as all the
2419 : : predecessor edges. */
2420 : :
2421 : : static void
2422 : 4459820 : remove_preds_and_fake_succs (constraint_graph_t graph)
2423 : : {
2424 : 4459820 : unsigned int i;
2425 : :
2426 : : /* Clear the implicit ref and address nodes from the successor
2427 : : lists. */
2428 : 226858900 : for (i = 1; i < FIRST_REF_NODE; i++)
2429 : : {
2430 : 222399080 : if (graph->succs[i])
2431 : 65105180 : bitmap_clear_range (graph->succs[i], FIRST_REF_NODE,
2432 : 65105180 : FIRST_REF_NODE * 2);
2433 : : }
2434 : :
2435 : : /* Free the successor list for the non-ref nodes. */
2436 : 231318720 : for (i = FIRST_REF_NODE + 1; i < graph->size; i++)
2437 : : {
2438 : 222399080 : if (graph->succs[i])
2439 : 11884236 : 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 : 4459820 : graph->size = varmap.length ();
2445 : 4459820 : graph->succs = XRESIZEVEC (bitmap, graph->succs, graph->size);
2446 : :
2447 : 4459820 : free (graph->implicit_preds);
2448 : 4459820 : graph->implicit_preds = NULL;
2449 : 4459820 : free (graph->preds);
2450 : 4459820 : graph->preds = NULL;
2451 : 4459820 : bitmap_obstack_release (&predbitmap_obstack);
2452 : 4459820 : }
2453 : :
2454 : : namespace pointer_analysis {
2455 : :
2456 : : /* Solve the constraint set. The entry function of the solver. */
2457 : :
2458 : : void
2459 : 4459820 : solve_constraints (void)
2460 : : {
2461 : 4459820 : 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 : 4459820 : unsigned int *map = XNEWVEC (unsigned int, varmap.length ());
2466 : 44598200 : for (unsigned i = 0; i < integer_id + 1; ++i)
2467 : 40138380 : 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 : 382360680 : for (unsigned i = integer_id + 1; i < varmap.length (); ++i)
2472 : 186720520 : if (varmap[varmap[i]->head]->address_taken)
2473 : 15197074 : map[i] = j++;
2474 : 191180340 : for (unsigned i = integer_id + 1; i < varmap.length (); ++i)
2475 : 186720520 : if (! varmap[varmap[i]->head]->address_taken)
2476 : 171523446 : map[i] = j++;
2477 : : /* Shuffle varmap according to map. */
2478 : 191180340 : for (unsigned i = integer_id + 1; i < varmap.length (); ++i)
2479 : : {
2480 : 276189895 : while (map[varmap[i]->id] != i)
2481 : 89469375 : std::swap (varmap[i], varmap[map[varmap[i]->id]]);
2482 : 186720520 : gcc_assert (bitmap_empty_p (varmap[i]->solution));
2483 : 186720520 : varmap[i]->id = i;
2484 : 186720520 : varmap[i]->next = map[varmap[i]->next];
2485 : 186720520 : varmap[i]->head = map[varmap[i]->head];
2486 : : }
2487 : : /* Finally rewrite constraints. */
2488 : 444467733 : for (unsigned i = 0; i < constraints.length (); ++i)
2489 : : {
2490 : 440007913 : constraints[i]->lhs.var = map[constraints[i]->lhs.var];
2491 : 440007913 : constraints[i]->rhs.var = map[constraints[i]->rhs.var];
2492 : : }
2493 : 4459820 : free (map);
2494 : :
2495 : 4459820 : if (dump_file)
2496 : 480 : fprintf (dump_file,
2497 : : "\nCollapsing static cycles and doing variable "
2498 : : "substitution\n");
2499 : :
2500 : 8919640 : init_graph (varmap.length () * 2);
2501 : :
2502 : 4459820 : if (dump_file)
2503 : 480 : fprintf (dump_file, "Building predecessor graph\n");
2504 : 4459820 : build_pred_graph ();
2505 : :
2506 : 4459820 : if (dump_file)
2507 : 480 : fprintf (dump_file, "Detecting pointer and location "
2508 : : "equivalences\n");
2509 : 4459820 : si = perform_var_substitution (graph);
2510 : :
2511 : 4459820 : if (dump_file)
2512 : 480 : fprintf (dump_file, "Rewriting constraints and unifying "
2513 : : "variables\n");
2514 : 4459820 : rewrite_constraints (graph, si);
2515 : :
2516 : 4459820 : build_succ_graph ();
2517 : :
2518 : 4459820 : free_var_substitution_info (si);
2519 : :
2520 : : /* Attach complex constraints to graph nodes. */
2521 : 4459820 : move_complex_constraints (graph);
2522 : :
2523 : 4459820 : if (dump_file)
2524 : 480 : fprintf (dump_file, "Uniting pointer but not location equivalent "
2525 : : "variables\n");
2526 : 4459820 : unite_pointer_equivalences (graph);
2527 : :
2528 : 4459820 : if (dump_file)
2529 : 480 : fprintf (dump_file, "Finding indirect cycles\n");
2530 : 4459820 : find_indirect_cycles (graph);
2531 : :
2532 : : /* Implicit nodes and predecessors are no longer necessary at this
2533 : : point. */
2534 : 4459820 : remove_preds_and_fake_succs (graph);
2535 : :
2536 : 4459820 : 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 : 4459820 : if (dump_file)
2545 : 480 : fprintf (dump_file, "Solving graph\n");
2546 : :
2547 : 4459820 : solve_graph (graph);
2548 : :
2549 : 4459820 : 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 : 4459820 : union_find_compress_all ();
2560 : 4459820 : var_rep = graph->rep;
2561 : :
2562 : 4459820 : delete_graph ();
2563 : 4459820 : }
2564 : :
2565 : : } // namespace pointer_analysis
|
