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 : 9439653215 : find (unsigned int node)
136 : : {
137 : 9439653215 : gcc_checking_assert (node < graph->size);
138 : 9439653215 : if (graph->rep[node] != node)
139 : 1071167786 : 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 : 603935130 : unite (unsigned int to, unsigned int from)
150 : : {
151 : 603935130 : gcc_checking_assert (to < graph->size && from < graph->size);
152 : 603935130 : if (to != from && graph->rep[from] != to)
153 : : {
154 : 71031078 : graph->rep[from] = to;
155 : 71031078 : 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 : 4518845 : union_find_compress_all (void)
165 : : {
166 : 4518845 : unsigned int i;
167 : 233241293 : for (i = 0; i < graph->size; i++)
168 : 228722448 : find (i);
169 : 4518845 : }
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 : 19480273 : constraint_expr_equal (struct constraint_expr a, struct constraint_expr b)
288 : : {
289 : 12068018 : 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 : 458856466 : constraint_expr_less (struct constraint_expr a, struct constraint_expr b)
298 : : {
299 : 0 : if (a.type == b.type)
300 : : {
301 : 273556140 : if (a.var == b.var)
302 : 206048129 : return a.offset < b.offset;
303 : : else
304 : 67508011 : return a.var < b.var;
305 : : }
306 : : else
307 : 185300326 : 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 : 252127564 : constraint_less (const constraint_t &a, const constraint_t &b)
315 : : {
316 : 504255128 : if (constraint_expr_less (a->lhs, b->lhs))
317 : : return true;
318 : 218587354 : else if (constraint_expr_less (b->lhs, a->lhs))
319 : : return false;
320 : : else
321 : 97435225 : 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 : 12802442 : constraint_equal (const constraint &a, const constraint &b)
328 : : {
329 : 19480273 : return constraint_expr_equal (a.lhs, b.lhs)
330 : 12802442 : && 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 : 278787 : constraint_vec_find (vec<constraint_t> vec,
337 : : constraint &lookfor)
338 : : {
339 : 278787 : unsigned int place;
340 : 278787 : constraint_t found;
341 : :
342 : 278787 : if (!vec.exists ())
343 : : return NULL;
344 : :
345 : 223349 : place = vec.lower_bound (&lookfor, constraint_less);
346 : 223349 : if (place >= vec.length ())
347 : : return NULL;
348 : 87911 : found = vec[place];
349 : 87911 : 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 : 70906212 : constraint_set_union (vec<constraint_t> *to,
359 : : vec<constraint_t> *from)
360 : : {
361 : 70906212 : int i;
362 : 70906212 : constraint_t c;
363 : 70906212 : bool any_change = false;
364 : :
365 : 71184999 : FOR_EACH_VEC_ELT (*from, i, c)
366 : : {
367 : 278787 : if (constraint_vec_find (*to, *c) == NULL)
368 : : {
369 : 278120 : unsigned int place = to->lower_bound (c, constraint_less);
370 : 278120 : to->safe_insert (place, c);
371 : 278120 : any_change = true;
372 : : }
373 : : }
374 : 70906212 : return any_change;
375 : : }
376 : :
377 : : /* Expands the solution in SET to all sub-fields of variables included. */
378 : :
379 : : static bitmap
380 : 136395678 : solution_set_expand (bitmap set, bitmap *expanded)
381 : : {
382 : 136395678 : bitmap_iterator bi;
383 : 136395678 : unsigned j;
384 : :
385 : 136395678 : if (*expanded)
386 : : return *expanded;
387 : :
388 : 76033384 : *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 : 76033384 : unsigned prev_head = 0;
393 : 297906749 : EXECUTE_IF_SET_IN_BITMAP (set, 0, j, bi)
394 : : {
395 : 221873365 : varinfo_t v = get_varinfo (j);
396 : 221873365 : if (v->is_artificial_var
397 : 131623494 : || v->is_full_var)
398 : 111205404 : continue;
399 : 110667961 : if (v->head != prev_head)
400 : : {
401 : 25264367 : varinfo_t head = get_varinfo (v->head);
402 : 25264367 : unsigned num = 1;
403 : 147719836 : for (varinfo_t n = vi_next (head); n != NULL; n = vi_next (n))
404 : : {
405 : 122455469 : 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 : 15086 : bitmap_set_range (*expanded, head->id, num);
411 : 15086 : head = n;
412 : 15086 : num = 1;
413 : : }
414 : : else
415 : 122440383 : num++;
416 : : }
417 : :
418 : 25264367 : bitmap_set_range (*expanded, head->id, num);
419 : 25264367 : prev_head = v->head;
420 : : }
421 : : }
422 : :
423 : : /* And finally set the rest of the bits from SET in an efficient way. */
424 : 76033384 : bitmap_ior_into (*expanded, set);
425 : :
426 : 76033384 : 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 : 85173922 : set_union_with_increment (bitmap to, bitmap delta, HOST_WIDE_INT inc,
434 : : bitmap *expanded_delta)
435 : : {
436 : 85173922 : bool changed = false;
437 : 85173922 : bitmap_iterator bi;
438 : 85173922 : unsigned int i;
439 : :
440 : : /* If the solution of DELTA contains anything it is good enough to transfer
441 : : this to TO. */
442 : 85173922 : if (bitmap_bit_p (delta, anything_id))
443 : 1306330 : 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 : 83867592 : if (inc == UNKNOWN_OFFSET)
448 : : {
449 : 82866885 : delta = solution_set_expand (delta, expanded_delta);
450 : 82866885 : changed |= bitmap_ior_into (to, delta);
451 : 82866885 : return changed;
452 : : }
453 : :
454 : : /* For non-zero offset union the offsetted solution into the destination. */
455 : 4310036 : EXECUTE_IF_SET_IN_BITMAP (delta, 0, i, bi)
456 : : {
457 : 3309329 : 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 : 3309329 : if (vi->is_artificial_var
462 : 1970066 : || vi->is_unknown_size_var
463 : 1828806 : || vi->is_full_var)
464 : 1728000 : changed |= bitmap_set_bit (to, i);
465 : : else
466 : : {
467 : 1581329 : HOST_WIDE_INT fieldoffset = vi->offset + inc;
468 : 1581329 : 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 : 1581329 : if (fieldoffset < 0)
473 : 33072 : vi = get_varinfo (vi->head);
474 : : else
475 : 1548257 : vi = first_or_preceding_vi_for_offset (vi, fieldoffset);
476 : :
477 : 1908422 : do
478 : : {
479 : 1908422 : changed |= bitmap_set_bit (to, vi->id);
480 : 1908422 : if (vi->is_full_var
481 : 1908382 : || vi->next == 0)
482 : : break;
483 : :
484 : : /* We have to include all fields that overlap the current field
485 : : shifted by inc. */
486 : 899149 : vi = vi_next (vi);
487 : : }
488 : 899149 : 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 : 146491302 : insert_into_complex (constraint_graph_t graph,
500 : : unsigned int var, constraint_t c)
501 : : {
502 : 146491302 : vec<constraint_t> complex = graph->complex[var];
503 : 146491302 : unsigned int place = complex.lower_bound (c, constraint_less);
504 : :
505 : : /* Only insert constraints that do not already exist. */
506 : 146491302 : if (place >= complex.length ()
507 : 100766600 : || !constraint_equal (*c, *complex[place]))
508 : 144545682 : graph->complex[var].safe_insert (place, c);
509 : 146491302 : }
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 : 70906212 : merge_node_constraints (constraint_graph_t graph, unsigned int to,
518 : : unsigned int from)
519 : : {
520 : 70906212 : unsigned int i;
521 : 70906212 : constraint_t c;
522 : 70906212 : bool any_change = false;
523 : :
524 : 70906212 : gcc_checking_assert (find (from) == to);
525 : :
526 : : /* Move all complex constraints from src node into to node. */
527 : 71184999 : 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 : 278787 : if (c->rhs.type == DEREF)
534 : 91140 : c->rhs.var = to;
535 : 187647 : else if (c->lhs.type == DEREF)
536 : 92065 : c->lhs.var = to;
537 : : else
538 : 95582 : c->rhs.var = to;
539 : :
540 : : }
541 : 70906212 : any_change = constraint_set_union (&graph->complex[to],
542 : : &graph->complex[from]);
543 : 70906212 : graph->complex[from].release ();
544 : 70906212 : return any_change;
545 : : }
546 : :
547 : : /* Remove edges involving NODE from GRAPH. */
548 : :
549 : : static void
550 : 90761464 : clear_edges_for_node (constraint_graph_t graph, unsigned int node)
551 : : {
552 : 90761464 : if (graph->succs[node])
553 : 2511668 : BITMAP_FREE (graph->succs[node]);
554 : 90761464 : }
555 : :
556 : : /* Merge GRAPH nodes FROM and TO into node TO. */
557 : :
558 : : static void
559 : 70906212 : merge_graph_nodes (constraint_graph_t graph, unsigned int to,
560 : : unsigned int from)
561 : : {
562 : 70906212 : 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 : 73 : if (graph->indirect_cycles[to] == -1)
571 : 53 : graph->indirect_cycles[to] = graph->indirect_cycles[from];
572 : : }
573 : :
574 : : /* Merge all the successor edges. */
575 : 70906212 : if (graph->succs[from])
576 : : {
577 : 2511668 : if (!graph->succs[to])
578 : 1264946 : graph->succs[to] = BITMAP_ALLOC (&pta_obstack);
579 : 2511668 : bitmap_ior_into (graph->succs[to],
580 : 2511668 : graph->succs[from]);
581 : : }
582 : :
583 : 70906212 : clear_edges_for_node (graph, from);
584 : 70906212 : }
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 : 296156673 : add_implicit_graph_edge (constraint_graph_t graph, unsigned int to,
592 : : unsigned int from)
593 : : {
594 : 296156673 : if (to == from)
595 : : return;
596 : :
597 : 296156673 : if (!graph->implicit_preds[to])
598 : 165315784 : graph->implicit_preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
599 : :
600 : 296156673 : if (bitmap_set_bit (graph->implicit_preds[to], from))
601 : 278622627 : 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 : 250950538 : add_pred_graph_edge (constraint_graph_t graph, unsigned int to,
610 : : unsigned int from)
611 : : {
612 : 250950538 : if (!graph->preds[to])
613 : 147472064 : graph->preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
614 : 250950538 : bitmap_set_bit (graph->preds[to], from);
615 : 250950538 : }
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 : 800587152 : add_graph_edge (constraint_graph_t graph, unsigned int to,
623 : : unsigned int from)
624 : : {
625 : 800587152 : if (to == from)
626 : : {
627 : : return false;
628 : : }
629 : : else
630 : : {
631 : 799844154 : bool r = false;
632 : :
633 : 799844154 : if (!graph->succs[from])
634 : 93369012 : 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 : 799844154 : if (to < FIRST_REF_NODE
647 : 767716373 : && bitmap_bit_p (graph->succs[from], find (escaped_id))
648 : 1166946648 : && bitmap_bit_p (get_varinfo (find (to))->solution, escaped_id))
649 : : {
650 : 308740894 : stats.num_avoided_edges++;
651 : 308740894 : return false;
652 : : }
653 : :
654 : 491103260 : if (bitmap_set_bit (graph->succs[from], to))
655 : : {
656 : 343451218 : r = true;
657 : 343451218 : if (to < FIRST_REF_NODE && from < FIRST_REF_NODE)
658 : 299053344 : stats.num_edges++;
659 : : }
660 : 491103260 : return r;
661 : : }
662 : : }
663 : :
664 : : /* Initialize the constraint graph structure to contain SIZE nodes. */
665 : :
666 : : static void
667 : 4518845 : init_graph (unsigned int size)
668 : : {
669 : 4518845 : unsigned int j;
670 : :
671 : 4518845 : bitmap_obstack_initialize (&predbitmap_obstack);
672 : :
673 : 4518845 : graph = XCNEW (struct constraint_graph);
674 : 4518845 : graph->size = size;
675 : 4518845 : graph->succs = XCNEWVEC (bitmap, graph->size);
676 : 4518845 : graph->indirect_cycles = XNEWVEC (int, graph->size);
677 : 4518845 : 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 : 4518845 : typedef vec<constraint_t> vec_constraint_t_heap;
681 : 4518845 : graph->complex = XCNEWVEC (vec_constraint_t_heap, size);
682 : 4518845 : graph->pe = XCNEWVEC (unsigned int, graph->size);
683 : 4518845 : graph->pe_rep = XNEWVEC (int, graph->size);
684 : :
685 : 461963741 : for (j = 0; j < graph->size; j++)
686 : : {
687 : 457444896 : graph->rep[j] = j;
688 : 457444896 : graph->pe_rep[j] = -1;
689 : 457444896 : graph->indirect_cycles[j] = -1;
690 : : }
691 : 4518845 : }
692 : :
693 : : /* Build the constraint graph, adding only predecessor edges right now. */
694 : :
695 : : static void
696 : 4518845 : build_pred_graph (void)
697 : : {
698 : 4518845 : int i;
699 : 4518845 : constraint_t c;
700 : 4518845 : unsigned int j;
701 : :
702 : 4518845 : graph->implicit_preds = XCNEWVEC (bitmap, graph->size);
703 : 4518845 : graph->preds = XCNEWVEC (bitmap, graph->size);
704 : 4518845 : graph->pointer_label = XCNEWVEC (unsigned int, graph->size);
705 : 4518845 : graph->loc_label = XCNEWVEC (unsigned int, graph->size);
706 : 4518845 : graph->pointed_by = XCNEWVEC (bitmap, graph->size);
707 : 4518845 : graph->points_to = XCNEWVEC (bitmap, graph->size);
708 : 4518845 : graph->eq_rep = XNEWVEC (int, graph->size);
709 : 4518845 : graph->direct_nodes = sbitmap_alloc (graph->size);
710 : 4518845 : graph->address_taken = BITMAP_ALLOC (&predbitmap_obstack);
711 : 4518845 : bitmap_clear (graph->direct_nodes);
712 : :
713 : 461963741 : for (j = 1; j < FIRST_REF_NODE; j++)
714 : : {
715 : 224203603 : if (!get_varinfo (j)->is_special_var)
716 : 201609378 : bitmap_set_bit (graph->direct_nodes, j);
717 : : }
718 : :
719 : 461963741 : for (j = 0; j < graph->size; j++)
720 : 457444896 : graph->eq_rep[j] = -1;
721 : :
722 : 466482586 : for (j = 0; j < varmap.length (); j++)
723 : 228722448 : graph->indirect_cycles[j] = -1;
724 : :
725 : 448403212 : FOR_EACH_VEC_ELT (constraints, i, c)
726 : : {
727 : 443884367 : struct constraint_expr lhs = c->lhs;
728 : 443884367 : struct constraint_expr rhs = c->rhs;
729 : 443884367 : unsigned int lhsvar = lhs.var;
730 : 443884367 : unsigned int rhsvar = rhs.var;
731 : :
732 : 443884367 : if (lhs.type == DEREF)
733 : : {
734 : : /* *x = y. */
735 : 36536270 : if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
736 : : {
737 : 32155842 : if (lhs.var == anything_id)
738 : 0 : add_pred_graph_edge (graph, storedanything_id, rhsvar);
739 : : else
740 : 64311684 : add_pred_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
741 : : }
742 : : }
743 : 407348097 : else if (rhs.type == DEREF)
744 : : {
745 : : /* x = *y */
746 : 49292052 : if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
747 : 26560142 : add_pred_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
748 : : else
749 : 36011981 : bitmap_clear_bit (graph->direct_nodes, lhsvar);
750 : : }
751 : 358056045 : else if (rhs.type == ADDRESSOF)
752 : : {
753 : 90642048 : varinfo_t v;
754 : :
755 : : /* x = &y */
756 : 90642048 : if (graph->points_to[lhsvar] == NULL)
757 : 67179880 : graph->points_to[lhsvar] = BITMAP_ALLOC (&predbitmap_obstack);
758 : 90642048 : bitmap_set_bit (graph->points_to[lhsvar], rhsvar);
759 : :
760 : 90642048 : if (graph->pointed_by[rhsvar] == NULL)
761 : 21826662 : graph->pointed_by[rhsvar] = BITMAP_ALLOC (&predbitmap_obstack);
762 : 90642048 : bitmap_set_bit (graph->pointed_by[rhsvar], lhsvar);
763 : :
764 : : /* Implicitly, *x = y */
765 : 181284096 : add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
766 : :
767 : : /* All related variables are no longer direct nodes. */
768 : 90642048 : bitmap_clear_bit (graph->direct_nodes, rhsvar);
769 : 90642048 : v = get_varinfo (rhsvar);
770 : 90642048 : if (!v->is_full_var)
771 : : {
772 : 7523404 : v = get_varinfo (v->head);
773 : 47885818 : do
774 : : {
775 : 47885818 : bitmap_clear_bit (graph->direct_nodes, v->id);
776 : 47885818 : v = vi_next (v);
777 : : }
778 : 47885818 : while (v != NULL);
779 : : }
780 : 90642048 : bitmap_set_bit (graph->address_taken, rhsvar);
781 : : }
782 : 267413997 : else if (lhsvar > anything_id
783 : 267413997 : && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
784 : : {
785 : : /* x = y */
786 : 205514625 : add_pred_graph_edge (graph, lhsvar, rhsvar);
787 : : /* Implicitly, *x = *y */
788 : 205514625 : add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar,
789 : 205514625 : FIRST_REF_NODE + rhsvar);
790 : : }
791 : 61899372 : else if (lhs.offset != 0 || rhs.offset != 0)
792 : : {
793 : 61707897 : if (rhs.offset != 0)
794 : 61707897 : 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 : 4518845 : }
800 : :
801 : : /* Build the constraint graph, adding successor edges. */
802 : :
803 : : static void
804 : 4518845 : build_succ_graph (void)
805 : : {
806 : 4518845 : unsigned i, t;
807 : 4518845 : constraint_t c;
808 : :
809 : 448403212 : FOR_EACH_VEC_ELT (constraints, i, c)
810 : : {
811 : 443884367 : struct constraint_expr lhs;
812 : 443884367 : struct constraint_expr rhs;
813 : 443884367 : unsigned int lhsvar;
814 : 443884367 : unsigned int rhsvar;
815 : :
816 : 443884367 : if (!c)
817 : 2546102 : continue;
818 : :
819 : 441338265 : lhs = c->lhs;
820 : 441338265 : rhs = c->rhs;
821 : 441338265 : lhsvar = find (lhs.var);
822 : 441338265 : rhsvar = find (rhs.var);
823 : :
824 : 441338265 : if (lhs.type == DEREF)
825 : : {
826 : 36489050 : if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
827 : : {
828 : 32127781 : if (lhs.var == anything_id)
829 : 0 : add_graph_edge (graph, storedanything_id, rhsvar);
830 : : else
831 : 64255562 : add_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
832 : : }
833 : : }
834 : 404849215 : else if (rhs.type == DEREF)
835 : : {
836 : 49291085 : if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
837 : 26558572 : add_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
838 : : }
839 : 355558130 : else if (rhs.type == ADDRESSOF)
840 : : {
841 : : /* x = &y */
842 : 90642048 : gcc_checking_assert (find (rhs.var) == rhs.var);
843 : 90642048 : bitmap_set_bit (get_varinfo (lhsvar)->solution, rhsvar);
844 : : }
845 : 264916082 : else if (lhsvar > anything_id
846 : 264916082 : && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
847 : : {
848 : 154795737 : add_graph_edge (graph, lhsvar, rhsvar);
849 : : }
850 : : }
851 : :
852 : : /* Add edges from STOREDANYTHING to all nodes that can receive pointers. */
853 : 4518845 : t = find (storedanything_id);
854 : 197090533 : for (i = integer_id + 1; i < FIRST_REF_NODE; ++i)
855 : : {
856 : 188052843 : if (get_varinfo (i)->may_have_pointers)
857 : 188029391 : add_graph_edge (graph, find (i), t);
858 : : }
859 : :
860 : : /* Everything stored to ANYTHING also potentially escapes. */
861 : 4518845 : add_graph_edge (graph, find (escaped_id), t);
862 : 4518845 : }
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 : 383222692 : scc_visit (constraint_graph_t graph, class scc_info *si, unsigned int n)
898 : : {
899 : 383222692 : unsigned int i;
900 : 383222692 : bitmap_iterator bi;
901 : 383222692 : unsigned int my_dfs;
902 : :
903 : 383222692 : bitmap_set_bit (si->visited, n);
904 : 383222692 : si->dfs[n] = si->current_index ++;
905 : 383222692 : my_dfs = si->dfs[n];
906 : :
907 : : /* Visit all the successors. */
908 : 651405159 : EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[n], 0, i, bi)
909 : : {
910 : 268182467 : unsigned int w;
911 : :
912 : 536364934 : if (i > LAST_REF_NODE)
913 : : break;
914 : :
915 : 268182467 : w = find (i);
916 : 268182467 : if (bitmap_bit_p (si->deleted, w))
917 : 116863801 : continue;
918 : :
919 : 151318666 : if (!bitmap_bit_p (si->visited, w))
920 : 151045221 : scc_visit (graph, si, w);
921 : :
922 : 151318666 : unsigned int t = find (w);
923 : 151318666 : gcc_checking_assert (find (n) == n);
924 : 151318666 : if (si->dfs[t] < si->dfs[n])
925 : 143948 : si->dfs[n] = si->dfs[t];
926 : : }
927 : :
928 : : /* See if any components have been identified. */
929 : 383222692 : if (si->dfs[n] == my_dfs)
930 : : {
931 : 383078810 : if (si->scc_stack.length () > 0
932 : 383078810 : && si->dfs[si->scc_stack.last ()] >= my_dfs)
933 : : {
934 : 110030 : bitmap scc = BITMAP_ALLOC (NULL);
935 : 110030 : unsigned int lowest_node;
936 : 110030 : bitmap_iterator bi;
937 : :
938 : 110030 : bitmap_set_bit (scc, n);
939 : :
940 : 110030 : while (si->scc_stack.length () != 0
941 : 253912 : && si->dfs[si->scc_stack.last ()] >= my_dfs)
942 : : {
943 : 143882 : unsigned int w = si->scc_stack.pop ();
944 : :
945 : 143882 : bitmap_set_bit (scc, w);
946 : : }
947 : :
948 : 110030 : lowest_node = bitmap_first_set_bit (scc);
949 : 110030 : gcc_assert (lowest_node < FIRST_REF_NODE);
950 : :
951 : : /* Collapse the SCC nodes into a single node, and mark the
952 : : indirect cycles. */
953 : 363942 : EXECUTE_IF_SET_IN_BITMAP (scc, 0, i, bi)
954 : : {
955 : 253912 : if (i < FIRST_REF_NODE)
956 : : {
957 : 129046 : if (unite (lowest_node, i))
958 : 19016 : unify_nodes (graph, lowest_node, i, false);
959 : : }
960 : : else
961 : : {
962 : 124866 : unite (lowest_node, i);
963 : 249732 : graph->indirect_cycles[i - FIRST_REF_NODE] = lowest_node;
964 : : }
965 : : }
966 : 110030 : bitmap_set_bit (si->deleted, lowest_node);
967 : : }
968 : : else
969 : 382968780 : bitmap_set_bit (si->deleted, n);
970 : : }
971 : : else
972 : 143882 : si->scc_stack.safe_push (n);
973 : 383222692 : }
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 : 70906212 : unify_nodes (constraint_graph_t graph, unsigned int to, unsigned int from,
980 : : bool update_changed)
981 : : {
982 : 70906212 : gcc_checking_assert (to != from && find (to) == to);
983 : :
984 : 70906212 : 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 : 70906212 : if (update_changed)
990 : 345470 : stats.unified_vars_dynamic++;
991 : : else
992 : 70560742 : stats.unified_vars_static++;
993 : :
994 : 70906212 : merge_graph_nodes (graph, to, from);
995 : 70906212 : if (merge_node_constraints (graph, to, from))
996 : : {
997 : 94802 : if (update_changed)
998 : 12362 : 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 : 70823772 : if (update_changed
1005 : 70823772 : && bitmap_clear_bit (changed, from))
1006 : 37238 : bitmap_set_bit (changed, to);
1007 : 70906212 : varinfo_t fromvi = get_varinfo (from);
1008 : 70906212 : if (fromvi->solution)
1009 : : {
1010 : : /* If the solution changes because of the merging, we need to mark
1011 : : the variable as changed. */
1012 : 70906212 : varinfo_t tovi = get_varinfo (to);
1013 : 70906212 : if (bitmap_ior_into (tovi->solution, fromvi->solution))
1014 : : {
1015 : 1973126 : if (update_changed)
1016 : 69248 : bitmap_set_bit (changed, to);
1017 : : }
1018 : :
1019 : 70906212 : BITMAP_FREE (fromvi->solution);
1020 : 70906212 : if (fromvi->oldsolution)
1021 : 215108 : BITMAP_FREE (fromvi->oldsolution);
1022 : :
1023 : 70906212 : if (stats.iterations > 0
1024 : 345470 : && tovi->oldsolution)
1025 : 19965 : BITMAP_FREE (tovi->oldsolution);
1026 : : }
1027 : 70906212 : if (graph->succs[to])
1028 : 2699824 : bitmap_clear_bit (graph->succs[to], to);
1029 : 70906212 : }
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 : 429674935 : 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 : 429674935 : if (get_varinfo (from)->is_special_var)
1041 : 31090740 : return bitmap_ior_into (get_varinfo (to)->solution,
1042 : 62181480 : get_varinfo (from)->solution);
1043 : : /* Merging the solution from ESCAPED needlessly increases
1044 : : the set. Use ESCAPED as representative instead. */
1045 : 398584195 : else if (from == find (escaped_id))
1046 : 35650592 : return bitmap_set_bit (get_varinfo (to)->solution, escaped_id);
1047 : 362933603 : else if (get_varinfo (from)->may_have_pointers
1048 : 362933603 : && add_graph_edge (graph, to, from))
1049 : 117735516 : return bitmap_ior_into (get_varinfo (to)->solution,
1050 : 117735516 : 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 : 70216060 : do_sd_constraint (constraint_graph_t graph, constraint_t c,
1059 : : bitmap delta, bitmap *expanded_delta)
1060 : : {
1061 : 70216060 : unsigned int lhs = c->lhs.var;
1062 : 70216060 : bool flag = false;
1063 : 70216060 : bitmap sol = get_varinfo (lhs)->solution;
1064 : 70216060 : unsigned int j;
1065 : 70216060 : bitmap_iterator bi;
1066 : 70216060 : HOST_WIDE_INT roffset = c->rhs.offset;
1067 : :
1068 : : /* Our IL does not allow this. */
1069 : 70216060 : 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 : 70216060 : if (bitmap_bit_p (delta, anything_id))
1074 : : {
1075 : 679086 : flag |= bitmap_set_bit (sol, anything_id);
1076 : 679086 : 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 : 69536974 : if (roffset == UNKNOWN_OFFSET)
1083 : : {
1084 : 51472637 : delta = solution_set_expand (delta, expanded_delta);
1085 : : /* No further offset processing is necessary. */
1086 : 51472637 : 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 : 314599276 : EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1092 : : {
1093 : 245062302 : varinfo_t v = get_varinfo (j);
1094 : 245062302 : HOST_WIDE_INT fieldoffset = v->offset + roffset;
1095 : 245062302 : unsigned HOST_WIDE_INT size = v->size;
1096 : 245062302 : unsigned int t;
1097 : :
1098 : 245062302 : if (v->is_full_var)
1099 : : ;
1100 : 146257362 : else if (roffset != 0)
1101 : : {
1102 : 5643690 : if (fieldoffset < 0)
1103 : 186863 : v = get_varinfo (v->head);
1104 : : else
1105 : 5456827 : 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 : 247152192 : do
1111 : : {
1112 : 247152192 : t = find (v->id);
1113 : :
1114 : 247152192 : flag |= solve_add_graph_edge (graph, lhs, t);
1115 : :
1116 : 247152192 : if (v->is_full_var
1117 : 148347060 : || v->next == 0)
1118 : : break;
1119 : :
1120 : 120956314 : v = vi_next (v);
1121 : : }
1122 : 120956314 : while (v->offset < fieldoffset + size);
1123 : : }
1124 : :
1125 : 69536974 : done:
1126 : : /* If the LHS solution changed, mark the var as changed. */
1127 : 70216060 : if (flag)
1128 : 28196250 : bitmap_set_bit (changed, lhs);
1129 : 70216060 : }
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 : 56811491 : do_ds_constraint (constraint_t c, bitmap delta, bitmap *expanded_delta)
1136 : : {
1137 : 56811491 : unsigned int rhs = c->rhs.var;
1138 : 56811491 : bitmap sol = get_varinfo (rhs)->solution;
1139 : 56811491 : unsigned int j;
1140 : 56811491 : bitmap_iterator bi;
1141 : 56811491 : HOST_WIDE_INT loff = c->lhs.offset;
1142 : 56811491 : bool escaped_p = false;
1143 : :
1144 : : /* Our IL does not allow this. */
1145 : 56811491 : 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 : 56811491 : if (bitmap_bit_p (sol, anything_id))
1150 : 468089 : 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 : 56811491 : if (bitmap_bit_p (delta, anything_id))
1156 : : {
1157 : 513824 : unsigned t = find (storedanything_id);
1158 : 513824 : if (solve_add_graph_edge (graph, t, rhs))
1159 : 36155 : bitmap_set_bit (changed, t);
1160 : 513824 : 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 : 56297667 : if (loff == UNKNOWN_OFFSET)
1167 : : {
1168 : 2056156 : delta = solution_set_expand (delta, expanded_delta);
1169 : 2056156 : 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 : 275047637 : EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1175 : : {
1176 : 218749970 : varinfo_t v = get_varinfo (j);
1177 : 218749970 : unsigned int t;
1178 : 218749970 : HOST_WIDE_INT fieldoffset = v->offset + loff;
1179 : 218749970 : unsigned HOST_WIDE_INT size = v->size;
1180 : :
1181 : 218749970 : if (v->is_full_var)
1182 : : ;
1183 : 133968998 : else if (loff != 0)
1184 : : {
1185 : 8152201 : if (fieldoffset < 0)
1186 : 4971 : v = get_varinfo (v->head);
1187 : : else
1188 : 8147230 : 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 : 221185511 : do
1194 : : {
1195 : 221185511 : if (v->may_have_pointers)
1196 : : {
1197 : : /* If v is a global variable then this is an escape point. */
1198 : 208399949 : if (v->is_global_var
1199 : 156066572 : && !escaped_p)
1200 : : {
1201 : 44902914 : t = find (escaped_id);
1202 : 44902914 : if (add_graph_edge (graph, t, rhs)
1203 : 58675795 : && bitmap_ior_into (get_varinfo (t)->solution, sol))
1204 : 1348628 : bitmap_set_bit (changed, t);
1205 : : /* Enough to let rhs escape once. */
1206 : : escaped_p = true;
1207 : : }
1208 : :
1209 : 208399949 : if (v->is_special_var)
1210 : : break;
1211 : :
1212 : 182008919 : t = find (v->id);
1213 : :
1214 : 182008919 : if (solve_add_graph_edge (graph, t, rhs))
1215 : 12329266 : bitmap_set_bit (changed, t);
1216 : : }
1217 : :
1218 : 194794481 : if (v->is_full_var
1219 : 136404397 : || v->next == 0)
1220 : : break;
1221 : :
1222 : 111256874 : v = vi_next (v);
1223 : : }
1224 : 111256874 : 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 : 212201473 : do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta,
1233 : : bitmap *expanded_delta)
1234 : : {
1235 : 212201473 : if (c->lhs.type == DEREF)
1236 : : {
1237 : 56811491 : if (c->rhs.type == ADDRESSOF)
1238 : : {
1239 : 0 : gcc_unreachable ();
1240 : : }
1241 : : else
1242 : : {
1243 : : /* *x = y */
1244 : 56811491 : do_ds_constraint (c, delta, expanded_delta);
1245 : : }
1246 : : }
1247 : 155389982 : else if (c->rhs.type == DEREF)
1248 : : {
1249 : : /* x = *y */
1250 : 70216060 : if (!(get_varinfo (c->lhs.var)->is_special_var))
1251 : 70216060 : do_sd_constraint (graph, c, delta, expanded_delta);
1252 : : }
1253 : : else
1254 : : {
1255 : 85173922 : bitmap tmp;
1256 : 85173922 : bool flag = false;
1257 : :
1258 : 85173922 : gcc_checking_assert (c->rhs.type == SCALAR && c->lhs.type == SCALAR
1259 : : && c->rhs.offset != 0 && c->lhs.offset == 0);
1260 : 85173922 : tmp = get_varinfo (c->lhs.var)->solution;
1261 : :
1262 : 85173922 : flag = set_union_with_increment (tmp, delta, c->rhs.offset,
1263 : : expanded_delta);
1264 : :
1265 : 85173922 : if (flag)
1266 : 20926780 : bitmap_set_bit (changed, c->lhs.var);
1267 : : }
1268 : 212201473 : }
1269 : :
1270 : : /* Initialize and return a new SCC info structure. */
1271 : :
1272 : 9037690 : scc_info::scc_info (size_t size) :
1273 : 9037690 : visited (size), deleted (size), current_index (0), scc_stack (1)
1274 : : {
1275 : 9037690 : bitmap_clear (visited);
1276 : 9037690 : bitmap_clear (deleted);
1277 : 9037690 : node_mapping = XNEWVEC (unsigned int, size);
1278 : 9037690 : dfs = XCNEWVEC (unsigned int, size);
1279 : :
1280 : 923927482 : for (size_t i = 0; i < size; i++)
1281 : 914889792 : node_mapping[i] = i;
1282 : 9037690 : }
1283 : :
1284 : : /* Free an SCC info structure pointed to by SI. */
1285 : :
1286 : 9037690 : scc_info::~scc_info ()
1287 : : {
1288 : 9037690 : free (node_mapping);
1289 : 9037690 : free (dfs);
1290 : 9037690 : }
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 : 4518845 : find_indirect_cycles (constraint_graph_t graph)
1302 : : {
1303 : 4518845 : unsigned int i;
1304 : 4518845 : unsigned int size = graph->size;
1305 : 4518845 : scc_info si (size);
1306 : :
1307 : 919408637 : for (i = 0; i < MIN (LAST_REF_NODE, size); i++)
1308 : 452926051 : if (!bitmap_bit_p (si.visited, i) && find (i) == i)
1309 : 232177471 : scc_visit (graph, &si, i);
1310 : 4518845 : }
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 : 389817226 : topo_visit (constraint_graph_t graph, vec<unsigned> &topo_order,
1317 : : sbitmap visited, unsigned int n)
1318 : : {
1319 : 389817226 : bitmap_iterator bi;
1320 : 389817226 : unsigned int j;
1321 : :
1322 : 389817226 : bitmap_set_bit (visited, n);
1323 : :
1324 : 389817226 : if (graph->succs[n])
1325 : 950702159 : EXECUTE_IF_SET_IN_BITMAP (graph->succs[n], 0, j, bi)
1326 : : {
1327 : 749917971 : unsigned k = find (j);
1328 : 749917971 : if (!bitmap_bit_p (visited, k))
1329 : 284874530 : topo_visit (graph, topo_order, visited, k);
1330 : : }
1331 : :
1332 : : /* Also consider copy with offset complex constraints as implicit edges. */
1333 : 833609460 : for (auto c : graph->complex[n])
1334 : : {
1335 : : /* Constraints are ordered so that SCALAR = SCALAR appear first. */
1336 : 258494248 : if (c->lhs.type != SCALAR || c->rhs.type != SCALAR)
1337 : : break;
1338 : 143553348 : gcc_checking_assert (c->rhs.var == n);
1339 : 143553348 : unsigned k = find (c->lhs.var);
1340 : 143553348 : if (!bitmap_bit_p (visited, k))
1341 : 36570117 : topo_visit (graph, topo_order, visited, k);
1342 : : }
1343 : :
1344 : 389817226 : topo_order.quick_push (n);
1345 : 389817226 : }
1346 : :
1347 : : /* Compute a topological ordering for GRAPH, and return the result. */
1348 : :
1349 : : static auto_vec<unsigned>
1350 : 7994696 : compute_topo_order (constraint_graph_t graph)
1351 : : {
1352 : 7994696 : unsigned int i;
1353 : 7994696 : unsigned int size = graph->size;
1354 : :
1355 : 7994696 : auto_sbitmap visited (size);
1356 : 7994696 : 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 : 7994696 : auto_vec<unsigned> tail (size);
1364 : 7994696 : topo_visit (graph, tail, visited, find (escaped_id));
1365 : :
1366 : 7994696 : auto_vec<unsigned> topo_order (size);
1367 : :
1368 : 593097156 : for (i = 0; i != size; ++i)
1369 : 577107764 : if (!bitmap_bit_p (visited, i) && find (i) == i)
1370 : 60377883 : topo_visit (graph, topo_order, visited, i);
1371 : :
1372 : 7994696 : topo_order.splice (tail);
1373 : 7994696 : return topo_order;
1374 : 7994696 : }
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 : 187713683 : equiv_class_hasher::hash (const equiv_class_label *ecl)
1408 : : {
1409 : 187713683 : return ecl->hashcode;
1410 : : }
1411 : :
1412 : : /* Equality function for two equiv_class_label_t's. */
1413 : :
1414 : : inline bool
1415 : 243732888 : equiv_class_hasher::equal (const equiv_class_label *eql1,
1416 : : const equiv_class_label *eql2)
1417 : : {
1418 : 243732888 : return (eql1->hashcode == eql2->hashcode
1419 : 243732888 : && 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 : 195767941 : equiv_class_lookup_or_add (hash_table<equiv_class_hasher> *table,
1430 : : bitmap labels)
1431 : : {
1432 : 195767941 : equiv_class_label **slot;
1433 : 195767941 : equiv_class_label ecl;
1434 : :
1435 : 195767941 : ecl.labels = labels;
1436 : 195767941 : ecl.hashcode = bitmap_hash (labels);
1437 : 195767941 : slot = table->find_slot (&ecl, INSERT);
1438 : 195767941 : if (!*slot)
1439 : : {
1440 : 163632231 : *slot = XOBNEW (&equiv_class_obstack, struct equiv_class_label);
1441 : 163632231 : (*slot)->labels = labels;
1442 : 163632231 : (*slot)->hashcode = ecl.hashcode;
1443 : 163632231 : (*slot)->equivalence_class = 0;
1444 : : }
1445 : :
1446 : 195767941 : 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 : 267952786 : condense_visit (constraint_graph_t graph, class scc_info *si, unsigned int n)
1504 : : {
1505 : 267952786 : unsigned int i;
1506 : 267952786 : bitmap_iterator bi;
1507 : 267952786 : unsigned int my_dfs;
1508 : :
1509 : 267952786 : gcc_checking_assert (si->node_mapping[n] == n);
1510 : 267952786 : bitmap_set_bit (si->visited, n);
1511 : 267952786 : si->dfs[n] = si->current_index ++;
1512 : 267952786 : my_dfs = si->dfs[n];
1513 : :
1514 : : /* Visit all the successors. */
1515 : 493424575 : EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
1516 : : {
1517 : 225471789 : unsigned int w = si->node_mapping[i];
1518 : :
1519 : 225471789 : if (bitmap_bit_p (si->deleted, w))
1520 : 143259861 : continue;
1521 : :
1522 : 82211928 : if (!bitmap_bit_p (si->visited, w))
1523 : 80739010 : condense_visit (graph, si, w);
1524 : :
1525 : 82211928 : unsigned int t = si->node_mapping[w];
1526 : 82211928 : gcc_checking_assert (si->node_mapping[n] == n);
1527 : 82211928 : if (si->dfs[t] < si->dfs[n])
1528 : 2661778 : si->dfs[n] = si->dfs[t];
1529 : : }
1530 : :
1531 : : /* Visit all the implicit predecessors. */
1532 : 327293036 : EXECUTE_IF_IN_NONNULL_BITMAP (graph->implicit_preds[n], 0, i, bi)
1533 : : {
1534 : 59340250 : unsigned int w = si->node_mapping[i];
1535 : :
1536 : 59340250 : if (bitmap_bit_p (si->deleted, w))
1537 : 19650822 : continue;
1538 : :
1539 : 39689428 : if (!bitmap_bit_p (si->visited, w))
1540 : 34818845 : condense_visit (graph, si, w);
1541 : :
1542 : 39689428 : unsigned int t = si->node_mapping[w];
1543 : 39689428 : gcc_assert (si->node_mapping[n] == n);
1544 : 39689428 : if (si->dfs[t] < si->dfs[n])
1545 : 8352133 : si->dfs[n] = si->dfs[t];
1546 : : }
1547 : :
1548 : : /* See if any components have been identified. */
1549 : 267952786 : if (si->dfs[n] == my_dfs)
1550 : : {
1551 : 257106001 : if (si->scc_stack.length () != 0
1552 : 257106001 : && 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 : 10846785 : do
1558 : : {
1559 : 10846785 : --first;
1560 : 10846785 : unsigned int w = si->scc_stack[first];
1561 : 10846785 : si->node_mapping[w] = n;
1562 : 10846785 : if (!bitmap_bit_p (graph->direct_nodes, w))
1563 : 8722558 : direct_p = false;
1564 : : }
1565 : : while (first > 0
1566 : 12205199 : && si->dfs[si->scc_stack[first - 1]] >= my_dfs);
1567 : 1358414 : if (!direct_p)
1568 : 871838 : bitmap_clear_bit (graph->direct_nodes, n);
1569 : :
1570 : : /* Want to reduce to node n, push that first. */
1571 : 1358414 : si->scc_stack.reserve (1);
1572 : 1358414 : si->scc_stack.quick_push (si->scc_stack[first]);
1573 : 1358414 : si->scc_stack[first] = n;
1574 : :
1575 : 1358414 : unsigned scc_size = si->scc_stack.length () - first;
1576 : 1358414 : unsigned split = scc_size / 2;
1577 : 1358414 : unsigned carry = scc_size - split * 2;
1578 : 4792071 : while (split > 0)
1579 : : {
1580 : 14280442 : for (unsigned i = 0; i < split; ++i)
1581 : : {
1582 : 10846785 : unsigned a = si->scc_stack[first + i];
1583 : 10846785 : unsigned b = si->scc_stack[first + split + carry + i];
1584 : :
1585 : : /* Unify our nodes. */
1586 : 10846785 : if (graph->preds[b])
1587 : : {
1588 : 4759546 : if (!graph->preds[a])
1589 : 976852 : std::swap (graph->preds[a], graph->preds[b]);
1590 : : else
1591 : 3782694 : bitmap_ior_into_and_free (graph->preds[a],
1592 : : &graph->preds[b]);
1593 : : }
1594 : 10846785 : if (graph->implicit_preds[b])
1595 : : {
1596 : 8619409 : if (!graph->implicit_preds[a])
1597 : 888996 : std::swap (graph->implicit_preds[a],
1598 : : graph->implicit_preds[b]);
1599 : : else
1600 : 7730413 : bitmap_ior_into_and_free (graph->implicit_preds[a],
1601 : : &graph->implicit_preds[b]);
1602 : : }
1603 : 10846785 : if (graph->points_to[b])
1604 : : {
1605 : 523841 : if (!graph->points_to[a])
1606 : 231352 : std::swap (graph->points_to[a], graph->points_to[b]);
1607 : : else
1608 : 292489 : bitmap_ior_into_and_free (graph->points_to[a],
1609 : : &graph->points_to[b]);
1610 : : }
1611 : : }
1612 : 3433657 : unsigned remain = split + carry;
1613 : 3433657 : split = remain / 2;
1614 : 3433657 : carry = remain - split * 2;
1615 : : }
1616 : : /* Actually pop the SCC. */
1617 : 1358414 : si->scc_stack.truncate (first);
1618 : : }
1619 : 257106001 : bitmap_set_bit (si->deleted, n);
1620 : : }
1621 : : else
1622 : 10846785 : si->scc_stack.safe_push (n);
1623 : 267952786 : }
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 : 233474385 : label_visit (constraint_graph_t graph, class scc_info *si, unsigned int n)
1646 : : {
1647 : 233474385 : unsigned int i, first_pred;
1648 : 233474385 : bitmap_iterator bi;
1649 : :
1650 : 233474385 : bitmap_set_bit (si->visited, n);
1651 : :
1652 : : /* Label and union our incoming edges's points to sets. */
1653 : 233474385 : first_pred = -1U;
1654 : 453609889 : EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
1655 : : {
1656 : 220135504 : unsigned int w = si->node_mapping[i];
1657 : 220135504 : if (!bitmap_bit_p (si->visited, w))
1658 : 76035904 : label_visit (graph, si, w);
1659 : :
1660 : : /* Skip unused edges. */
1661 : 220135504 : if (w == n || graph->pointer_label[w] == 0)
1662 : 5279705 : continue;
1663 : :
1664 : 214855799 : if (graph->points_to[w])
1665 : : {
1666 : 214855799 : if (!graph->points_to[n])
1667 : : {
1668 : 149425235 : if (first_pred == -1U)
1669 : : first_pred = w;
1670 : : else
1671 : : {
1672 : 41627619 : graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
1673 : 41627619 : bitmap_ior (graph->points_to[n],
1674 : 41627619 : graph->points_to[first_pred],
1675 : 41627619 : graph->points_to[w]);
1676 : : }
1677 : : }
1678 : : else
1679 : 65430564 : 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 : 233474385 : if (!bitmap_bit_p (graph->direct_nodes, n))
1685 : : {
1686 : 113183451 : if (!graph->points_to[n])
1687 : : {
1688 : 65426269 : graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
1689 : 65426269 : if (first_pred != -1U)
1690 : 26490698 : bitmap_copy (graph->points_to[n], graph->points_to[first_pred]);
1691 : : }
1692 : 226366902 : bitmap_set_bit (graph->points_to[n], FIRST_REF_NODE + n);
1693 : 113183451 : graph->pointer_label[n] = pointer_equiv_class++;
1694 : 113183451 : equiv_class_label_t ecl;
1695 : 226366902 : ecl = equiv_class_lookup_or_add (pointer_equiv_class_table,
1696 : 113183451 : graph->points_to[n]);
1697 : 113183451 : ecl->equivalence_class = graph->pointer_label[n];
1698 : 172716557 : return;
1699 : : }
1700 : :
1701 : : /* If there was only a single non-empty predecessor the pointer equiv
1702 : : class is the same. */
1703 : 120290934 : if (!graph->points_to[n])
1704 : : {
1705 : 59533106 : if (first_pred != -1U)
1706 : : {
1707 : 39679299 : graph->pointer_label[n] = graph->pointer_label[first_pred];
1708 : 39679299 : graph->points_to[n] = graph->points_to[first_pred];
1709 : : }
1710 : 59533106 : return;
1711 : : }
1712 : :
1713 : 60757828 : if (!bitmap_empty_p (graph->points_to[n]))
1714 : : {
1715 : 60757828 : equiv_class_label_t ecl;
1716 : 60757828 : ecl = equiv_class_lookup_or_add (pointer_equiv_class_table,
1717 : : graph->points_to[n]);
1718 : 60757828 : if (ecl->equivalence_class == 0)
1719 : 29070689 : ecl->equivalence_class = pointer_equiv_class++;
1720 : : else
1721 : : {
1722 : 31687139 : BITMAP_FREE (graph->points_to[n]);
1723 : 31687139 : graph->points_to[n] = ecl->labels;
1724 : : }
1725 : 60757828 : 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 : 4518845 : perform_var_substitution (constraint_graph_t graph)
1810 : : {
1811 : 4518845 : unsigned int i;
1812 : 4518845 : unsigned int size = graph->size;
1813 : 4518845 : scc_info *si = new scc_info (size);
1814 : :
1815 : 4518845 : bitmap_obstack_initialize (&iteration_obstack);
1816 : 4518845 : gcc_obstack_init (&equiv_class_obstack);
1817 : 4518845 : pointer_equiv_class_table = new hash_table<equiv_class_hasher> (511);
1818 : 4518845 : location_equiv_class_table
1819 : 4518845 : = new hash_table<equiv_class_hasher> (511);
1820 : 4518845 : pointer_equiv_class = 1;
1821 : 4518845 : 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 : 228722448 : for (i = 1; i < FIRST_REF_NODE; i++)
1826 : 224203603 : if (!bitmap_bit_p (si->visited, si->node_mapping[i]))
1827 : 152394931 : condense_visit (graph, si, si->node_mapping[i]);
1828 : :
1829 : 4518845 : 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 : 4518845 : bitmap_clear (si->visited);
1838 : : /* Actually the label the nodes for pointer equivalences. */
1839 : 461963741 : for (i = 1; i < FIRST_REF_NODE; i++)
1840 : 224203603 : if (!bitmap_bit_p (si->visited, si->node_mapping[i]))
1841 : 157438481 : label_visit (graph, si, si->node_mapping[i]);
1842 : :
1843 : : /* Calculate location equivalence labels. */
1844 : 228722448 : for (i = 1; i < FIRST_REF_NODE; i++)
1845 : : {
1846 : 224203603 : bitmap pointed_by;
1847 : 224203603 : bitmap_iterator bi;
1848 : 224203603 : unsigned int j;
1849 : :
1850 : 224203603 : if (!graph->pointed_by[i])
1851 : 202376941 : continue;
1852 : 21826662 : pointed_by = BITMAP_ALLOC (&iteration_obstack);
1853 : :
1854 : : /* Translate the pointed-by mapping for pointer equivalence
1855 : : labels. */
1856 : 98073487 : EXECUTE_IF_SET_IN_BITMAP (graph->pointed_by[i], 0, j, bi)
1857 : : {
1858 : 76246825 : bitmap_set_bit (pointed_by,
1859 : 76246825 : graph->pointer_label[si->node_mapping[j]]);
1860 : : }
1861 : : /* The original pointed_by is now dead. */
1862 : 21826662 : BITMAP_FREE (graph->pointed_by[i]);
1863 : :
1864 : : /* Look up the location equivalence label if one exists, or make
1865 : : one otherwise. */
1866 : 21826662 : equiv_class_label_t ecl;
1867 : 21826662 : ecl = equiv_class_lookup_or_add (location_equiv_class_table, pointed_by);
1868 : 21826662 : if (ecl->equivalence_class == 0)
1869 : 21378091 : ecl->equivalence_class = location_equiv_class++;
1870 : : else
1871 : : {
1872 : 448571 : 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 : 448571 : BITMAP_FREE (pointed_by);
1876 : : }
1877 : 21826662 : graph->loc_label[i] = ecl->equivalence_class;
1878 : :
1879 : : }
1880 : :
1881 : 4518845 : if (dump_file && (dump_flags & TDF_DETAILS))
1882 : 6763 : for (i = 1; i < FIRST_REF_NODE; i++)
1883 : : {
1884 : 6464 : unsigned j = si->node_mapping[i];
1885 : 6464 : 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 : 9933 : fprintf (dump_file,
1905 : : "Equivalence classes for %s node id %d ",
1906 : 6443 : bitmap_bit_p (graph->direct_nodes, i)
1907 : : ? "direct" : "indirect", i);
1908 : 6443 : if (i < FIRST_REF_NODE)
1909 : 6443 : 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 : 6443 : fprintf (dump_file,
1914 : : ": pointer %d, location %d\n",
1915 : 6443 : graph->pointer_label[i], graph->loc_label[i]);
1916 : : }
1917 : : }
1918 : :
1919 : : /* Quickly eliminate our non-pointer variables. */
1920 : :
1921 : 228722448 : for (i = 1; i < FIRST_REF_NODE; i++)
1922 : : {
1923 : 224203603 : unsigned int node = si->node_mapping[i];
1924 : :
1925 : 224203603 : if (graph->pointer_label[node] == 0)
1926 : : {
1927 : 19855252 : if (dump_file && (dump_flags & TDF_DETAILS))
1928 : 913 : fprintf (dump_file,
1929 : : "%s is a non-pointer variable, eliminating edges.\n",
1930 : 913 : get_varinfo (node)->name);
1931 : 19855252 : stats.nonpointer_vars++;
1932 : 19855252 : clear_edges_for_node (graph, node);
1933 : : }
1934 : : }
1935 : :
1936 : 4518845 : return si;
1937 : : }
1938 : :
1939 : : /* Free information that was only necessary for variable
1940 : : substitution. */
1941 : :
1942 : : static void
1943 : 4518845 : free_var_substitution_info (class scc_info *si)
1944 : : {
1945 : 4518845 : delete si;
1946 : 4518845 : free (graph->pointer_label);
1947 : 4518845 : free (graph->loc_label);
1948 : 4518845 : free (graph->pointed_by);
1949 : 4518845 : free (graph->points_to);
1950 : 4518845 : free (graph->eq_rep);
1951 : 4518845 : sbitmap_free (graph->direct_nodes);
1952 : 4518845 : delete pointer_equiv_class_table;
1953 : 4518845 : pointer_equiv_class_table = NULL;
1954 : 4518845 : delete location_equiv_class_table;
1955 : 4518845 : location_equiv_class_table = NULL;
1956 : 4518845 : obstack_free (&equiv_class_obstack, NULL);
1957 : 4518845 : bitmap_obstack_release (&iteration_obstack);
1958 : 4518845 : }
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 : 882676530 : 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 : 882676530 : if (!bitmap_bit_p (graph->address_taken, node))
1973 : : {
1974 : 686637727 : gcc_checking_assert (label < graph->size);
1975 : :
1976 : 686637727 : if (graph->eq_rep[label] != -1)
1977 : : {
1978 : : /* Unify the two variables since we know they are equivalent. */
1979 : 581509086 : if (unite (graph->eq_rep[label], node))
1980 : 68184091 : unify_nodes (graph, graph->eq_rep[label], node, false);
1981 : 581509086 : return graph->eq_rep[label];
1982 : : }
1983 : : else
1984 : : {
1985 : 105128641 : graph->eq_rep[label] = node;
1986 : 105128641 : graph->pe_rep[label] = node;
1987 : : }
1988 : : }
1989 : : else
1990 : : {
1991 : 196038803 : gcc_checking_assert (label < graph->size);
1992 : 196038803 : graph->pe[node] = label;
1993 : 196038803 : if (graph->pe_rep[label] == -1)
1994 : 21730347 : 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 : 4518845 : unite_pointer_equivalences (constraint_graph_t graph)
2006 : : {
2007 : 4518845 : unsigned int i;
2008 : :
2009 : : /* Go through the pointer equivalences and unite them to their
2010 : : representative, if they aren't already. */
2011 : 228722448 : for (i = 1; i < FIRST_REF_NODE; i++)
2012 : : {
2013 : 224203603 : unsigned int label = graph->pe[i];
2014 : 224203603 : if (label)
2015 : : {
2016 : 21826662 : int label_rep = graph->pe_rep[label];
2017 : :
2018 : 21826662 : if (label_rep == -1)
2019 : 0 : continue;
2020 : :
2021 : 21826662 : label_rep = find (label_rep);
2022 : 21826662 : if (label_rep >= 0 && unite (label_rep, find (i)))
2023 : 2357635 : unify_nodes (graph, label_rep, i, false);
2024 : : }
2025 : : }
2026 : 4518845 : }
2027 : :
2028 : : /* Move complex constraints to the GRAPH nodes they belong to. */
2029 : :
2030 : : static void
2031 : 4518845 : move_complex_constraints (constraint_graph_t graph)
2032 : : {
2033 : 4518845 : int i;
2034 : 4518845 : constraint_t c;
2035 : :
2036 : 448403212 : FOR_EACH_VEC_ELT (constraints, i, c)
2037 : : {
2038 : 443884367 : if (c)
2039 : : {
2040 : 441338265 : struct constraint_expr lhs = c->lhs;
2041 : 441338265 : struct constraint_expr rhs = c->rhs;
2042 : :
2043 : 441338265 : if (lhs.type == DEREF)
2044 : : {
2045 : 36489050 : insert_into_complex (graph, lhs.var, c);
2046 : : }
2047 : 404849215 : else if (rhs.type == DEREF)
2048 : : {
2049 : 49291085 : if (!(get_varinfo (lhs.var)->is_special_var))
2050 : 49291079 : insert_into_complex (graph, rhs.var, c);
2051 : : }
2052 : 355558130 : else if (rhs.type != ADDRESSOF && lhs.var > anything_id
2053 : 264760549 : && (lhs.offset != 0 || rhs.offset != 0))
2054 : : {
2055 : 60711173 : insert_into_complex (graph, rhs.var, c);
2056 : : }
2057 : : }
2058 : : }
2059 : 4518845 : }
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 : 4518845 : rewrite_constraints (constraint_graph_t graph,
2067 : : class scc_info *si)
2068 : : {
2069 : 4518845 : int i;
2070 : 4518845 : constraint_t c;
2071 : :
2072 : 4518845 : if (flag_checking)
2073 : : {
2074 : 461960599 : for (unsigned int j = 0; j < graph->size; j++)
2075 : 457441814 : gcc_assert (find (j) == j);
2076 : : }
2077 : :
2078 : 448403212 : FOR_EACH_VEC_ELT (constraints, i, c)
2079 : : {
2080 : 443884367 : struct constraint_expr lhs = c->lhs;
2081 : 443884367 : struct constraint_expr rhs = c->rhs;
2082 : 443884367 : unsigned int lhsvar = find (lhs.var);
2083 : 443884367 : unsigned int rhsvar = find (rhs.var);
2084 : 443884367 : unsigned int lhsnode, rhsnode;
2085 : 443884367 : unsigned int lhslabel, rhslabel;
2086 : :
2087 : 443884367 : lhsnode = si->node_mapping[lhsvar];
2088 : 443884367 : rhsnode = si->node_mapping[rhsvar];
2089 : 443884367 : lhslabel = graph->pointer_label[lhsnode];
2090 : 443884367 : rhslabel = graph->pointer_label[rhsnode];
2091 : :
2092 : : /* See if it is really a non-pointer variable, and if so, ignore
2093 : : the constraint. */
2094 : 443884367 : if (lhslabel == 0)
2095 : : {
2096 : 783903 : 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 : 783903 : constraints[i] = NULL;
2106 : 2546102 : continue;
2107 : : }
2108 : :
2109 : 443100464 : if (rhslabel == 0)
2110 : : {
2111 : 1762199 : if (dump_file && (dump_flags & TDF_DETAILS))
2112 : : {
2113 : :
2114 : 72 : fprintf (dump_file, "%s is a non-pointer variable, "
2115 : : "ignoring constraint:",
2116 : 36 : get_varinfo (rhs.var)->name);
2117 : 36 : dump_constraint (dump_file, c);
2118 : 36 : fprintf (dump_file, "\n");
2119 : : }
2120 : 1762199 : constraints[i] = NULL;
2121 : 1762199 : continue;
2122 : : }
2123 : :
2124 : 441338265 : lhsvar = find_equivalent_node (graph, lhsvar, lhslabel);
2125 : 441338265 : rhsvar = find_equivalent_node (graph, rhsvar, rhslabel);
2126 : 441338265 : c->lhs.var = lhsvar;
2127 : 441338265 : c->rhs.var = rhsvar;
2128 : : }
2129 : 4518845 : }
2130 : :
2131 : : /* Eliminate indirect cycles involving NODE. Return true if NODE was
2132 : : part of an SCC, false otherwise. */
2133 : :
2134 : : static bool
2135 : 389502469 : eliminate_indirect_cycles (unsigned int node)
2136 : : {
2137 : 389502469 : if (graph->indirect_cycles[node] != -1
2138 : 389839030 : && !bitmap_empty_p (get_varinfo (node)->solution))
2139 : : {
2140 : 303547 : unsigned int i;
2141 : 303547 : auto_vec<unsigned> queue;
2142 : 303547 : int queuepos;
2143 : 303547 : unsigned int to = find (graph->indirect_cycles[node]);
2144 : 303547 : 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 : 1620090 : EXECUTE_IF_SET_IN_BITMAP (get_varinfo (node)->solution, 0, i, bi)
2151 : : {
2152 : 1316543 : if (find (i) == i && i != to)
2153 : : {
2154 : 345470 : if (unite (to, i))
2155 : 345470 : queue.safe_push (i);
2156 : : }
2157 : : }
2158 : :
2159 : 345470 : for (queuepos = 0;
2160 : 649017 : queue.iterate (queuepos, &i);
2161 : : queuepos++)
2162 : : {
2163 : 345470 : unify_nodes (graph, to, i, true);
2164 : : }
2165 : 303547 : return true;
2166 : 303547 : }
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 : 4518845 : solve_graph (constraint_graph_t graph)
2179 : : {
2180 : 4518845 : unsigned int size = graph->size;
2181 : 4518845 : unsigned int i;
2182 : 4518845 : bitmap pts;
2183 : :
2184 : 4518845 : changed = BITMAP_ALLOC (NULL);
2185 : :
2186 : : /* Mark all initial non-collapsed nodes as changed. */
2187 : 228722448 : for (i = 1; i < size; i++)
2188 : : {
2189 : 224203603 : varinfo_t ivi = get_varinfo (i);
2190 : 377846464 : if (find (i) == i && !bitmap_empty_p (ivi->solution)
2191 : 277441519 : && ((graph->succs[i] && !bitmap_empty_p (graph->succs[i]))
2192 : 232026913 : || graph->complex[i].length () > 0))
2193 : 33841647 : bitmap_set_bit (changed, i);
2194 : : }
2195 : :
2196 : : /* Allocate a bitmap to be used to store the changed bits. */
2197 : 4518845 : pts = BITMAP_ALLOC (&pta_obstack);
2198 : :
2199 : 17032386 : while (!bitmap_empty_p (changed))
2200 : : {
2201 : 7994696 : unsigned int i;
2202 : 7994696 : stats.iterations++;
2203 : :
2204 : 7994696 : bitmap_obstack_initialize (&iteration_obstack);
2205 : :
2206 : 7994696 : auto_vec<unsigned> topo_order = compute_topo_order (graph);
2207 : 405806618 : while (topo_order.length () != 0)
2208 : : {
2209 : 389817226 : i = topo_order.pop ();
2210 : :
2211 : : /* If this variable is not a representative, skip it. */
2212 : 389817226 : if (find (i) != i)
2213 : 314757 : continue;
2214 : :
2215 : : /* In certain indirect cycle cases, we may merge this
2216 : : variable to another. */
2217 : 389502469 : if (eliminate_indirect_cycles (i) && find (i) != i)
2218 : 50 : 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 : 533340099 : while (bitmap_clear_bit (changed, i))
2230 : : {
2231 : 144142494 : bitmap solution;
2232 : 144142494 : vec<constraint_t> &complex = graph->complex[i];
2233 : 144142494 : varinfo_t vi = get_varinfo (i);
2234 : 144142494 : bool solution_empty;
2235 : :
2236 : : /* Compute the changed set of solution bits. If anything
2237 : : is in the solution just propagate that. */
2238 : 144142494 : 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 : 2746856 : if (vi->oldsolution
2244 : 2746856 : && bitmap_bit_p (vi->oldsolution, anything_id))
2245 : : break;
2246 : 2442042 : bitmap_copy (pts, get_varinfo (find (anything_id))->solution);
2247 : : }
2248 : 141395638 : else if (vi->oldsolution)
2249 : 36786143 : bitmap_and_compl (pts, vi->solution, vi->oldsolution);
2250 : : else
2251 : 104609495 : bitmap_copy (pts, vi->solution);
2252 : :
2253 : 143837680 : if (bitmap_empty_p (pts))
2254 : : break;
2255 : :
2256 : 143837680 : if (vi->oldsolution)
2257 : 37985489 : bitmap_ior_into (vi->oldsolution, pts);
2258 : : else
2259 : : {
2260 : 105852191 : vi->oldsolution = BITMAP_ALLOC (&oldpta_obstack);
2261 : 105852191 : bitmap_copy (vi->oldsolution, pts);
2262 : : }
2263 : :
2264 : 143837680 : solution = vi->solution;
2265 : 143837680 : solution_empty = bitmap_empty_p (solution);
2266 : :
2267 : : /* Process the complex constraints. */
2268 : 143837680 : hash_set<constraint_t> *cvisited = nullptr;
2269 : 143837680 : if (flag_checking)
2270 : 143836995 : cvisited = new hash_set<constraint_t>;
2271 : 143837680 : bitmap expanded_pts = NULL;
2272 : 356343239 : for (unsigned j = 0; j < complex.length (); ++j)
2273 : : {
2274 : 212505559 : 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 : 212505559 : unsigned int new_lhs = find (c->lhs.var);
2281 : 212505559 : unsigned int new_rhs = find (c->rhs.var);
2282 : 212505559 : if (c->lhs.var != new_lhs || c->rhs.var != new_rhs)
2283 : : {
2284 : 1626005 : constraint tem = *c;
2285 : 1626005 : tem.lhs.var = new_lhs;
2286 : 1626005 : tem.rhs.var = new_rhs;
2287 : 1626005 : unsigned int place
2288 : 1626005 : = complex.lower_bound (&tem, constraint_less);
2289 : 1626005 : c->lhs.var = new_lhs;
2290 : 1626005 : c->rhs.var = new_rhs;
2291 : 1626005 : if (place != j)
2292 : : {
2293 : 1613585 : complex.ordered_remove (j);
2294 : 1613585 : if (j < place)
2295 : 1595399 : --place;
2296 : 1613585 : if (place < complex.length ())
2297 : : {
2298 : 399625 : if (constraint_equal (*complex[place], *c))
2299 : : {
2300 : 36560 : j--;
2301 : 304086 : continue;
2302 : : }
2303 : : else
2304 : 363065 : complex.safe_insert (place, c);
2305 : : }
2306 : : else
2307 : 1213960 : complex.quick_push (c);
2308 : 1577025 : if (place > j)
2309 : : {
2310 : 267526 : j--;
2311 : 267526 : 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 : 212201473 : if (cvisited && cvisited->add (c))
2321 : 0 : gcc_unreachable ();
2322 : 212201473 : if (!solution_empty || c->lhs.type != DEREF)
2323 : 212201473 : do_complex_constraint (graph, c, pts, &expanded_pts);
2324 : : }
2325 : 143837680 : if (cvisited)
2326 : : {
2327 : : /* When checking, verify the order of constraints is
2328 : : maintained and each constraint is evaluated exactly
2329 : : once. */
2330 : 274139900 : for (unsigned j = 1; j < complex.length (); ++j)
2331 : 130302905 : gcc_assert (constraint_less (complex[j-1], complex[j]));
2332 : 225734503 : gcc_assert (cvisited->elements () == complex.length ());
2333 : 143836995 : delete cvisited;
2334 : : }
2335 : 143837680 : BITMAP_FREE (expanded_pts);
2336 : :
2337 : 143837680 : solution_empty = bitmap_empty_p (solution);
2338 : :
2339 : 143837680 : if (!solution_empty)
2340 : : {
2341 : 143837680 : bitmap_iterator bi;
2342 : 143837680 : unsigned eff_escaped_id = find (escaped_id);
2343 : 143837680 : unsigned j;
2344 : :
2345 : : /* Propagate solution to all successors. */
2346 : 143837680 : unsigned to_remove = ~0U;
2347 : 364180790 : EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i],
2348 : : 0, j, bi)
2349 : : {
2350 : 220343110 : if (to_remove != ~0U)
2351 : : {
2352 : 2314805 : bitmap_clear_bit (graph->succs[i], to_remove);
2353 : 2314805 : to_remove = ~0U;
2354 : : }
2355 : 220343110 : unsigned int to = find (j);
2356 : 220343110 : if (to != j)
2357 : : {
2358 : : /* Update the succ graph, avoiding duplicate
2359 : : work. */
2360 : 2282393 : to_remove = j;
2361 : 2282393 : if (! bitmap_set_bit (graph->succs[i], to))
2362 : 917927 : 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 : 219425183 : if (to == i)
2370 : : {
2371 : 175475 : to_remove = j;
2372 : 175475 : continue;
2373 : : }
2374 : : /* Early node unification can lead to edges from
2375 : : escaped - remove them. */
2376 : 219249708 : if (i == eff_escaped_id)
2377 : : {
2378 : 175575 : to_remove = j;
2379 : 175575 : if (bitmap_set_bit (get_varinfo (to)->solution,
2380 : : escaped_id))
2381 : 96741 : bitmap_set_bit (changed, to);
2382 : 175575 : continue;
2383 : : }
2384 : :
2385 : 219074133 : if (bitmap_ior_into (get_varinfo (to)->solution, pts))
2386 : 97476369 : bitmap_set_bit (changed, to);
2387 : : }
2388 : 100987698 : if (to_remove != ~0U)
2389 : 217302 : bitmap_clear_bit (graph->succs[i], to_remove);
2390 : : }
2391 : : }
2392 : : }
2393 : 7994696 : bitmap_obstack_release (&iteration_obstack);
2394 : 7994696 : }
2395 : :
2396 : 4518845 : BITMAP_FREE (pts);
2397 : 4518845 : BITMAP_FREE (changed);
2398 : 4518845 : bitmap_obstack_release (&oldpta_obstack);
2399 : 4518845 : }
2400 : :
2401 : : void
2402 : 4518845 : delete_graph (void)
2403 : : {
2404 : 4518845 : unsigned int i;
2405 : 233241293 : for (i = 0; i < graph->size; i++)
2406 : 228722448 : graph->complex[i].release ();
2407 : 4518845 : free (graph->complex);
2408 : :
2409 : 4518845 : free (graph->succs);
2410 : 4518845 : free (graph->pe);
2411 : 4518845 : free (graph->pe_rep);
2412 : 4518845 : 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 : 4518845 : free (graph);
2416 : 4518845 : }
2417 : :
2418 : : /* Remove the REF and ADDRESS edges from GRAPH, as well as all the
2419 : : predecessor edges. */
2420 : :
2421 : : static void
2422 : 4518845 : remove_preds_and_fake_succs (constraint_graph_t graph)
2423 : : {
2424 : 4518845 : unsigned int i;
2425 : :
2426 : : /* Clear the implicit ref and address nodes from the successor
2427 : : lists. */
2428 : 228722448 : for (i = 1; i < FIRST_REF_NODE; i++)
2429 : : {
2430 : 224203603 : if (graph->succs[i])
2431 : 65771113 : bitmap_clear_range (graph->succs[i], FIRST_REF_NODE,
2432 : 65771113 : FIRST_REF_NODE * 2);
2433 : : }
2434 : :
2435 : : /* Free the successor list for the non-ref nodes. */
2436 : 233241293 : for (i = FIRST_REF_NODE + 1; i < graph->size; i++)
2437 : : {
2438 : 224203603 : if (graph->succs[i])
2439 : 12022098 : 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 : 4518845 : graph->size = varmap.length ();
2445 : 4518845 : graph->succs = XRESIZEVEC (bitmap, graph->succs, graph->size);
2446 : :
2447 : 4518845 : free (graph->implicit_preds);
2448 : 4518845 : graph->implicit_preds = NULL;
2449 : 4518845 : free (graph->preds);
2450 : 4518845 : graph->preds = NULL;
2451 : 4518845 : bitmap_obstack_release (&predbitmap_obstack);
2452 : 4518845 : }
2453 : :
2454 : : namespace pointer_analysis {
2455 : :
2456 : : /* Solve the constraint set. The entry function of the solver. */
2457 : :
2458 : : void
2459 : 4518845 : solve_constraints (void)
2460 : : {
2461 : 4518845 : 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 : 4518845 : unsigned int *map = XNEWVEC (unsigned int, varmap.length ());
2466 : 45188450 : for (unsigned i = 0; i < integer_id + 1; ++i)
2467 : 40669605 : 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 : 385143376 : for (unsigned i = integer_id + 1; i < varmap.length (); ++i)
2472 : 188052843 : if (varmap[varmap[i]->head]->address_taken)
2473 : 15269660 : map[i] = j++;
2474 : 192571688 : for (unsigned i = integer_id + 1; i < varmap.length (); ++i)
2475 : 188052843 : if (! varmap[varmap[i]->head]->address_taken)
2476 : 172783183 : map[i] = j++;
2477 : : /* Shuffle varmap according to map. */
2478 : 192571688 : for (unsigned i = integer_id + 1; i < varmap.length (); ++i)
2479 : : {
2480 : 278189822 : while (map[varmap[i]->id] != i)
2481 : 90136979 : std::swap (varmap[i], varmap[map[varmap[i]->id]]);
2482 : 188052843 : gcc_assert (bitmap_empty_p (varmap[i]->solution));
2483 : 188052843 : varmap[i]->id = i;
2484 : 188052843 : varmap[i]->next = map[varmap[i]->next];
2485 : 188052843 : varmap[i]->head = map[varmap[i]->head];
2486 : : }
2487 : : /* Finally rewrite constraints. */
2488 : 448403212 : for (unsigned i = 0; i < constraints.length (); ++i)
2489 : : {
2490 : 443884367 : constraints[i]->lhs.var = map[constraints[i]->lhs.var];
2491 : 443884367 : constraints[i]->rhs.var = map[constraints[i]->rhs.var];
2492 : : }
2493 : 4518845 : free (map);
2494 : :
2495 : 4518845 : if (dump_file)
2496 : 480 : fprintf (dump_file,
2497 : : "\nCollapsing static cycles and doing variable "
2498 : : "substitution\n");
2499 : :
2500 : 9037690 : init_graph (varmap.length () * 2);
2501 : :
2502 : 4518845 : if (dump_file)
2503 : 480 : fprintf (dump_file, "Building predecessor graph\n");
2504 : 4518845 : build_pred_graph ();
2505 : :
2506 : 4518845 : if (dump_file)
2507 : 480 : fprintf (dump_file, "Detecting pointer and location "
2508 : : "equivalences\n");
2509 : 4518845 : si = perform_var_substitution (graph);
2510 : :
2511 : 4518845 : if (dump_file)
2512 : 480 : fprintf (dump_file, "Rewriting constraints and unifying "
2513 : : "variables\n");
2514 : 4518845 : rewrite_constraints (graph, si);
2515 : :
2516 : 4518845 : build_succ_graph ();
2517 : :
2518 : 4518845 : free_var_substitution_info (si);
2519 : :
2520 : : /* Attach complex constraints to graph nodes. */
2521 : 4518845 : move_complex_constraints (graph);
2522 : :
2523 : 4518845 : if (dump_file)
2524 : 480 : fprintf (dump_file, "Uniting pointer but not location equivalent "
2525 : : "variables\n");
2526 : 4518845 : unite_pointer_equivalences (graph);
2527 : :
2528 : 4518845 : if (dump_file)
2529 : 480 : fprintf (dump_file, "Finding indirect cycles\n");
2530 : 4518845 : find_indirect_cycles (graph);
2531 : :
2532 : : /* Implicit nodes and predecessors are no longer necessary at this
2533 : : point. */
2534 : 4518845 : remove_preds_and_fake_succs (graph);
2535 : :
2536 : 4518845 : 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 : 4518845 : if (dump_file)
2545 : 480 : fprintf (dump_file, "Solving graph\n");
2546 : :
2547 : 4518845 : solve_graph (graph);
2548 : :
2549 : 4518845 : 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 : 4518845 : union_find_compress_all ();
2560 : 4518845 : var_rep = graph->rep;
2561 : :
2562 : 4518845 : delete_graph ();
2563 : 4518845 : }
2564 : :
2565 : : } // namespace pointer_analysis
|
