1/* Tree based points-to analysis
2 Copyright (C) 2005-2017 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#include "rtl.h"
26#include "tree.h"
27#include "gimple.h"
28#include "alloc-pool.h"
29#include "tree-pass.h"
30#include "ssa.h"
31#include "cgraph.h"
32#include "tree-pretty-print.h"
33#include "diagnostic-core.h"
34#include "fold-const.h"
35#include "stor-layout.h"
36#include "stmt.h"
37#include "gimple-iterator.h"
38#include "tree-into-ssa.h"
39#include "tree-dfa.h"
40#include "params.h"
41#include "gimple-walk.h"
42#include "varasm.h"
43#include "stringpool.h"
44#include "attribs.h"
45
46/* The idea behind this analyzer is to generate set constraints from the
47 program, then solve the resulting constraints in order to generate the
48 points-to sets.
49
50 Set constraints are a way of modeling program analysis problems that
51 involve sets. They consist of an inclusion constraint language,
52 describing the variables (each variable is a set) and operations that
53 are involved on the variables, and a set of rules that derive facts
54 from these operations. To solve a system of set constraints, you derive
55 all possible facts under the rules, which gives you the correct sets
56 as a consequence.
57
58 See "Efficient Field-sensitive pointer analysis for C" by "David
59 J. Pearce and Paul H. J. Kelly and Chris Hankin, at
60 http://citeseer.ist.psu.edu/pearce04efficient.html
61
62 Also see "Ultra-fast Aliasing Analysis using CLA: A Million Lines
63 of C Code in a Second" by ""Nevin Heintze and Olivier Tardieu" at
64 http://citeseer.ist.psu.edu/heintze01ultrafast.html
65
66 There are three types of real constraint expressions, DEREF,
67 ADDRESSOF, and SCALAR. Each constraint expression consists
68 of a constraint type, a variable, and an offset.
69
70 SCALAR is a constraint expression type used to represent x, whether
71 it appears on the LHS or the RHS of a statement.
72 DEREF is a constraint expression type used to represent *x, whether
73 it appears on the LHS or the RHS of a statement.
74 ADDRESSOF is a constraint expression used to represent &x, whether
75 it appears on the LHS or the RHS of a statement.
76
77 Each pointer variable in the program is assigned an integer id, and
78 each field of a structure variable is assigned an integer id as well.
79
80 Structure variables are linked to their list of fields through a "next
81 field" in each variable that points to the next field in offset
82 order.
83 Each variable for a structure field has
84
85 1. "size", that tells the size in bits of that field.
86 2. "fullsize, that tells the size in bits of the entire structure.
87 3. "offset", that tells the offset in bits from the beginning of the
88 structure to this field.
89
90 Thus,
91 struct f
92 {
93 int a;
94 int b;
95 } foo;
96 int *bar;
97
98 looks like
99
100 foo.a -> id 1, size 32, offset 0, fullsize 64, next foo.b
101 foo.b -> id 2, size 32, offset 32, fullsize 64, next NULL
102 bar -> id 3, size 32, offset 0, fullsize 32, next NULL
103
104
105 In order to solve the system of set constraints, the following is
106 done:
107
108 1. Each constraint variable x has a solution set associated with it,
109 Sol(x).
110
111 2. Constraints are separated into direct, copy, and complex.
112 Direct constraints are ADDRESSOF constraints that require no extra
113 processing, such as P = &Q
114 Copy constraints are those of the form P = Q.
115 Complex constraints are all the constraints involving dereferences
116 and offsets (including offsetted copies).
117
118 3. All direct constraints of the form P = &Q are processed, such
119 that Q is added to Sol(P)
120
121 4. All complex constraints for a given constraint variable are stored in a
122 linked list attached to that variable's node.
123
124 5. A directed graph is built out of the copy constraints. Each
125 constraint variable is a node in the graph, and an edge from
126 Q to P is added for each copy constraint of the form P = Q
127
128 6. The graph is then walked, and solution sets are
129 propagated along the copy edges, such that an edge from Q to P
130 causes Sol(P) <- Sol(P) union Sol(Q).
131
132 7. As we visit each node, all complex constraints associated with
133 that node are processed by adding appropriate copy edges to the graph, or the
134 appropriate variables to the solution set.
135
136 8. The process of walking the graph is iterated until no solution
137 sets change.
138
139 Prior to walking the graph in steps 6 and 7, We perform static
140 cycle elimination on the constraint graph, as well
141 as off-line variable substitution.
142
143 TODO: Adding offsets to pointer-to-structures can be handled (IE not punted
144 on and turned into anything), but isn't. You can just see what offset
145 inside the pointed-to struct it's going to access.
146
147 TODO: Constant bounded arrays can be handled as if they were structs of the
148 same number of elements.
149
150 TODO: Modeling heap and incoming pointers becomes much better if we
151 add fields to them as we discover them, which we could do.
152
153 TODO: We could handle unions, but to be honest, it's probably not
154 worth the pain or slowdown. */
155
156/* IPA-PTA optimizations possible.
157
158 When the indirect function called is ANYTHING we can add disambiguation
159 based on the function signatures (or simply the parameter count which
160 is the varinfo size). We also do not need to consider functions that
161 do not have their address taken.
162
163 The is_global_var bit which marks escape points is overly conservative
164 in IPA mode. Split it to is_escape_point and is_global_var - only
165 externally visible globals are escape points in IPA mode.
166 There is now is_ipa_escape_point but this is only used in a few
167 selected places.
168
169 The way we introduce DECL_PT_UID to avoid fixing up all points-to
170 sets in the translation unit when we copy a DECL during inlining
171 pessimizes precision. The advantage is that the DECL_PT_UID keeps
172 compile-time and memory usage overhead low - the points-to sets
173 do not grow or get unshared as they would during a fixup phase.
174 An alternative solution is to delay IPA PTA until after all
175 inlining transformations have been applied.
176
177 The way we propagate clobber/use information isn't optimized.
178 It should use a new complex constraint that properly filters
179 out local variables of the callee (though that would make
180 the sets invalid after inlining). OTOH we might as well
181 admit defeat to WHOPR and simply do all the clobber/use analysis
182 and propagation after PTA finished but before we threw away
183 points-to information for memory variables. WHOPR and PTA
184 do not play along well anyway - the whole constraint solving
185 would need to be done in WPA phase and it will be very interesting
186 to apply the results to local SSA names during LTRANS phase.
187
188 We probably should compute a per-function unit-ESCAPE solution
189 propagating it simply like the clobber / uses solutions. The
190 solution can go alongside the non-IPA espaced solution and be
191 used to query which vars escape the unit through a function.
192 This is also required to make the escaped-HEAP trick work in IPA mode.
193
194 We never put function decls in points-to sets so we do not
195 keep the set of called functions for indirect calls.
196
197 And probably more. */
198
199static bool use_field_sensitive = true;
200static int in_ipa_mode = 0;
201
202/* Used for predecessor bitmaps. */
203static bitmap_obstack predbitmap_obstack;
204
205/* Used for points-to sets. */
206static bitmap_obstack pta_obstack;
207
208/* Used for oldsolution members of variables. */
209static bitmap_obstack oldpta_obstack;
210
211/* Used for per-solver-iteration bitmaps. */
212static bitmap_obstack iteration_obstack;
213
214static unsigned int create_variable_info_for (tree, const char *, bool);
215typedef struct constraint_graph *constraint_graph_t;
216static void unify_nodes (constraint_graph_t, unsigned int, unsigned int, bool);
217
218struct constraint;
219typedef struct constraint *constraint_t;
220
221
222#define EXECUTE_IF_IN_NONNULL_BITMAP(a, b, c, d) \
223 if (a) \
224 EXECUTE_IF_SET_IN_BITMAP (a, b, c, d)
225
226static struct constraint_stats
227{
228 unsigned int total_vars;
229 unsigned int nonpointer_vars;
230 unsigned int unified_vars_static;
231 unsigned int unified_vars_dynamic;
232 unsigned int iterations;
233 unsigned int num_edges;
234 unsigned int num_implicit_edges;
235 unsigned int points_to_sets_created;
236} stats;
237
238struct variable_info
239{
240 /* ID of this variable */
241 unsigned int id;
242
243 /* True if this is a variable created by the constraint analysis, such as
244 heap variables and constraints we had to break up. */
245 unsigned int is_artificial_var : 1;
246
247 /* True if this is a special variable whose solution set should not be
248 changed. */
249 unsigned int is_special_var : 1;
250
251 /* True for variables whose size is not known or variable. */
252 unsigned int is_unknown_size_var : 1;
253
254 /* True for (sub-)fields that represent a whole variable. */
255 unsigned int is_full_var : 1;
256
257 /* True if this is a heap variable. */
258 unsigned int is_heap_var : 1;
259
260 /* True if this is a register variable. */
261 unsigned int is_reg_var : 1;
262
263 /* True if this field may contain pointers. */
264 unsigned int may_have_pointers : 1;
265
266 /* True if this field has only restrict qualified pointers. */
267 unsigned int only_restrict_pointers : 1;
268
269 /* True if this represents a heap var created for a restrict qualified
270 pointer. */
271 unsigned int is_restrict_var : 1;
272
273 /* True if this represents a global variable. */
274 unsigned int is_global_var : 1;
275
276 /* True if this represents a module escape point for IPA analysis. */
277 unsigned int is_ipa_escape_point : 1;
278
279 /* True if this represents a IPA function info. */
280 unsigned int is_fn_info : 1;
281
282 /* ??? Store somewhere better. */
283 unsigned short ruid;
284
285 /* The ID of the variable for the next field in this structure
286 or zero for the last field in this structure. */
287 unsigned next;
288
289 /* The ID of the variable for the first field in this structure. */
290 unsigned head;
291
292 /* Offset of this variable, in bits, from the base variable */
293 unsigned HOST_WIDE_INT offset;
294
295 /* Size of the variable, in bits. */
296 unsigned HOST_WIDE_INT size;
297
298 /* Full size of the base variable, in bits. */
299 unsigned HOST_WIDE_INT fullsize;
300
301 /* Name of this variable */
302 const char *name;
303
304 /* Tree that this variable is associated with. */
305 tree decl;
306
307 /* Points-to set for this variable. */
308 bitmap solution;
309
310 /* Old points-to set for this variable. */
311 bitmap oldsolution;
312};
313typedef struct variable_info *varinfo_t;
314
315static varinfo_t first_vi_for_offset (varinfo_t, unsigned HOST_WIDE_INT);
316static varinfo_t first_or_preceding_vi_for_offset (varinfo_t,
317 unsigned HOST_WIDE_INT);
318static varinfo_t lookup_vi_for_tree (tree);
319static inline bool type_can_have_subvars (const_tree);
320static void make_param_constraints (varinfo_t);
321
322/* Pool of variable info structures. */
323static object_allocator<variable_info> variable_info_pool
324 ("Variable info pool");
325
326/* Map varinfo to final pt_solution. */
327static hash_map<varinfo_t, pt_solution *> *final_solutions;
328struct obstack final_solutions_obstack;
329
330/* Table of variable info structures for constraint variables.
331 Indexed directly by variable info id. */
332static vec<varinfo_t> varmap;
333
334/* Return the varmap element N */
335
336static inline varinfo_t
337get_varinfo (unsigned int n)
338{
339 return varmap[n];
340}
341
342/* Return the next variable in the list of sub-variables of VI
343 or NULL if VI is the last sub-variable. */
344
345static inline varinfo_t
346vi_next (varinfo_t vi)
347{
348 return get_varinfo (vi->next);
349}
350
351/* Static IDs for the special variables. Variable ID zero is unused
352 and used as terminator for the sub-variable chain. */
353enum { nothing_id = 1, anything_id = 2, string_id = 3,
354 escaped_id = 4, nonlocal_id = 5,
355 storedanything_id = 6, integer_id = 7 };
356
357/* Return a new variable info structure consisting for a variable
358 named NAME, and using constraint graph node NODE. Append it
359 to the vector of variable info structures. */
360
361static varinfo_t
362new_var_info (tree t, const char *name, bool add_id)
363{
364 unsigned index = varmap.length ();
365 varinfo_t ret = variable_info_pool.allocate ();
366
367 if (dump_file && add_id)
368 {
369 char *tempname = xasprintf ("%s(%d)", name, index);
370 name = ggc_strdup (tempname);
371 free (tempname);
372 }
373
374 ret->id = index;
375 ret->name = name;
376 ret->decl = t;
377 /* Vars without decl are artificial and do not have sub-variables. */
378 ret->is_artificial_var = (t == NULL_TREE);
379 ret->is_special_var = false;
380 ret->is_unknown_size_var = false;
381 ret->is_full_var = (t == NULL_TREE);
382 ret->is_heap_var = false;
383 ret->may_have_pointers = true;
384 ret->only_restrict_pointers = false;
385 ret->is_restrict_var = false;
386 ret->ruid = 0;
387 ret->is_global_var = (t == NULL_TREE);
388 ret->is_ipa_escape_point = false;
389 ret->is_fn_info = false;
390 if (t && DECL_P (t))
391 ret->is_global_var = (is_global_var (t)
392 /* We have to treat even local register variables
393 as escape points. */
394 || (VAR_P (t) && DECL_HARD_REGISTER (t)));
395 ret->is_reg_var = (t && TREE_CODE (t) == SSA_NAME);
396 ret->solution = BITMAP_ALLOC (&pta_obstack);
397 ret->oldsolution = NULL;
398 ret->next = 0;
399 ret->head = ret->id;
400
401 stats.total_vars++;
402
403 varmap.safe_push (ret);
404
405 return ret;
406}
407
408/* A map mapping call statements to per-stmt variables for uses
409 and clobbers specific to the call. */
410static hash_map<gimple *, varinfo_t> *call_stmt_vars;
411
412/* Lookup or create the variable for the call statement CALL. */
413
414static varinfo_t
415get_call_vi (gcall *call)
416{
417 varinfo_t vi, vi2;
418
419 bool existed;
420 varinfo_t *slot_p = &call_stmt_vars->get_or_insert (call, &existed);
421 if (existed)
422 return *slot_p;
423
424 vi = new_var_info (NULL_TREE, "CALLUSED", true);
425 vi->offset = 0;
426 vi->size = 1;
427 vi->fullsize = 2;
428 vi->is_full_var = true;
429 vi->is_reg_var = true;
430
431 vi2 = new_var_info (NULL_TREE, "CALLCLOBBERED", true);
432 vi2->offset = 1;
433 vi2->size = 1;
434 vi2->fullsize = 2;
435 vi2->is_full_var = true;
436 vi2->is_reg_var = true;
437
438 vi->next = vi2->id;
439
440 *slot_p = vi;
441 return vi;
442}
443
444/* Lookup the variable for the call statement CALL representing
445 the uses. Returns NULL if there is nothing special about this call. */
446
447static varinfo_t
448lookup_call_use_vi (gcall *call)
449{
450 varinfo_t *slot_p = call_stmt_vars->get (call);
451 if (slot_p)
452 return *slot_p;
453
454 return NULL;
455}
456
457/* Lookup the variable for the call statement CALL representing
458 the clobbers. Returns NULL if there is nothing special about this call. */
459
460static varinfo_t
461lookup_call_clobber_vi (gcall *call)
462{
463 varinfo_t uses = lookup_call_use_vi (call);
464 if (!uses)
465 return NULL;
466
467 return vi_next (uses);
468}
469
470/* Lookup or create the variable for the call statement CALL representing
471 the uses. */
472
473static varinfo_t
474get_call_use_vi (gcall *call)
475{
476 return get_call_vi (call);
477}
478
479/* Lookup or create the variable for the call statement CALL representing
480 the clobbers. */
481
482static varinfo_t ATTRIBUTE_UNUSED
483get_call_clobber_vi (gcall *call)
484{
485 return vi_next (get_call_vi (call));
486}
487
488
489enum constraint_expr_type {SCALAR, DEREF, ADDRESSOF};
490
491/* An expression that appears in a constraint. */
492
493struct constraint_expr
494{
495 /* Constraint type. */
496 constraint_expr_type type;
497
498 /* Variable we are referring to in the constraint. */
499 unsigned int var;
500
501 /* Offset, in bits, of this constraint from the beginning of
502 variables it ends up referring to.
503
504 IOW, in a deref constraint, we would deref, get the result set,
505 then add OFFSET to each member. */
506 HOST_WIDE_INT offset;
507};
508
509/* Use 0x8000... as special unknown offset. */
510#define UNKNOWN_OFFSET HOST_WIDE_INT_MIN
511
512typedef struct constraint_expr ce_s;
513static void get_constraint_for_1 (tree, vec<ce_s> *, bool, bool);
514static void get_constraint_for (tree, vec<ce_s> *);
515static void get_constraint_for_rhs (tree, vec<ce_s> *);
516static void do_deref (vec<ce_s> *);
517
518/* Our set constraints are made up of two constraint expressions, one
519 LHS, and one RHS.
520
521 As described in the introduction, our set constraints each represent an
522 operation between set valued variables.
523*/
524struct constraint
525{
526 struct constraint_expr lhs;
527 struct constraint_expr rhs;
528};
529
530/* List of constraints that we use to build the constraint graph from. */
531
532static vec<constraint_t> constraints;
533static object_allocator<constraint> constraint_pool ("Constraint pool");
534
535/* The constraint graph is represented as an array of bitmaps
536 containing successor nodes. */
537
538struct constraint_graph
539{
540 /* Size of this graph, which may be different than the number of
541 nodes in the variable map. */
542 unsigned int size;
543
544 /* Explicit successors of each node. */
545 bitmap *succs;
546
547 /* Implicit predecessors of each node (Used for variable
548 substitution). */
549 bitmap *implicit_preds;
550
551 /* Explicit predecessors of each node (Used for variable substitution). */
552 bitmap *preds;
553
554 /* Indirect cycle representatives, or -1 if the node has no indirect
555 cycles. */
556 int *indirect_cycles;
557
558 /* Representative node for a node. rep[a] == a unless the node has
559 been unified. */
560 unsigned int *rep;
561
562 /* Equivalence class representative for a label. This is used for
563 variable substitution. */
564 int *eq_rep;
565
566 /* Pointer equivalence label for a node. All nodes with the same
567 pointer equivalence label can be unified together at some point
568 (either during constraint optimization or after the constraint
569 graph is built). */
570 unsigned int *pe;
571
572 /* Pointer equivalence representative for a label. This is used to
573 handle nodes that are pointer equivalent but not location
574 equivalent. We can unite these once the addressof constraints
575 are transformed into initial points-to sets. */
576 int *pe_rep;
577
578 /* Pointer equivalence label for each node, used during variable
579 substitution. */
580 unsigned int *pointer_label;
581
582 /* Location equivalence label for each node, used during location
583 equivalence finding. */
584 unsigned int *loc_label;
585
586 /* Pointed-by set for each node, used during location equivalence
587 finding. This is pointed-by rather than pointed-to, because it
588 is constructed using the predecessor graph. */
589 bitmap *pointed_by;
590
591 /* Points to sets for pointer equivalence. This is *not* the actual
592 points-to sets for nodes. */
593 bitmap *points_to;
594
595 /* Bitmap of nodes where the bit is set if the node is a direct
596 node. Used for variable substitution. */
597 sbitmap direct_nodes;
598
599 /* Bitmap of nodes where the bit is set if the node is address
600 taken. Used for variable substitution. */
601 bitmap address_taken;
602
603 /* Vector of complex constraints for each graph node. Complex
604 constraints are those involving dereferences or offsets that are
605 not 0. */
606 vec<constraint_t> *complex;
607};
608
609static constraint_graph_t graph;
610
611/* During variable substitution and the offline version of indirect
612 cycle finding, we create nodes to represent dereferences and
613 address taken constraints. These represent where these start and
614 end. */
615#define FIRST_REF_NODE (varmap).length ()
616#define LAST_REF_NODE (FIRST_REF_NODE + (FIRST_REF_NODE - 1))
617
618/* Return the representative node for NODE, if NODE has been unioned
619 with another NODE.
620 This function performs path compression along the way to finding
621 the representative. */
622
623static unsigned int
624find (unsigned int node)
625{
626 gcc_checking_assert (node < graph->size);
627 if (graph->rep[node] != node)
628 return graph->rep[node] = find (graph->rep[node]);
629 return node;
630}
631
632/* Union the TO and FROM nodes to the TO nodes.
633 Note that at some point in the future, we may want to do
634 union-by-rank, in which case we are going to have to return the
635 node we unified to. */
636
637static bool
638unite (unsigned int to, unsigned int from)
639{
640 gcc_checking_assert (to < graph->size && from < graph->size);
641 if (to != from && graph->rep[from] != to)
642 {
643 graph->rep[from] = to;
644 return true;
645 }
646 return false;
647}
648
649/* Create a new constraint consisting of LHS and RHS expressions. */
650
651static constraint_t
652new_constraint (const struct constraint_expr lhs,
653 const struct constraint_expr rhs)
654{
655 constraint_t ret = constraint_pool.allocate ();
656 ret->lhs = lhs;
657 ret->rhs = rhs;
658 return ret;
659}
660
661/* Print out constraint C to FILE. */
662
663static void
664dump_constraint (FILE *file, constraint_t c)
665{
666 if (c->lhs.type == ADDRESSOF)
667 fprintf (file, "&");
668 else if (c->lhs.type == DEREF)
669 fprintf (file, "*");
670 fprintf (file, "%s", get_varinfo (c->lhs.var)->name);
671 if (c->lhs.offset == UNKNOWN_OFFSET)
672 fprintf (file, " + UNKNOWN");
673 else if (c->lhs.offset != 0)
674 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->lhs.offset);
675 fprintf (file, " = ");
676 if (c->rhs.type == ADDRESSOF)
677 fprintf (file, "&");
678 else if (c->rhs.type == DEREF)
679 fprintf (file, "*");
680 fprintf (file, "%s", get_varinfo (c->rhs.var)->name);
681 if (c->rhs.offset == UNKNOWN_OFFSET)
682 fprintf (file, " + UNKNOWN");
683 else if (c->rhs.offset != 0)
684 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->rhs.offset);
685}
686
687
688void debug_constraint (constraint_t);
689void debug_constraints (void);
690void debug_constraint_graph (void);
691void debug_solution_for_var (unsigned int);
692void debug_sa_points_to_info (void);
693void debug_varinfo (varinfo_t);
694void debug_varmap (void);
695
696/* Print out constraint C to stderr. */
697
698DEBUG_FUNCTION void
699debug_constraint (constraint_t c)
700{
701 dump_constraint (stderr, c);
702 fprintf (stderr, "\n");
703}
704
705/* Print out all constraints to FILE */
706
707static void
708dump_constraints (FILE *file, int from)
709{
710 int i;
711 constraint_t c;
712 for (i = from; constraints.iterate (i, &c); i++)
713 if (c)
714 {
715 dump_constraint (file, c);
716 fprintf (file, "\n");
717 }
718}
719
720/* Print out all constraints to stderr. */
721
722DEBUG_FUNCTION void
723debug_constraints (void)
724{
725 dump_constraints (stderr, 0);
726}
727
728/* Print the constraint graph in dot format. */
729
730static void
731dump_constraint_graph (FILE *file)
732{
733 unsigned int i;
734
735 /* Only print the graph if it has already been initialized: */
736 if (!graph)
737 return;
738
739 /* Prints the header of the dot file: */
740 fprintf (file, "strict digraph {\n");
741 fprintf (file, " node [\n shape = box\n ]\n");
742 fprintf (file, " edge [\n fontsize = \"12\"\n ]\n");
743 fprintf (file, "\n // List of nodes and complex constraints in "
744 "the constraint graph:\n");
745
746 /* The next lines print the nodes in the graph together with the
747 complex constraints attached to them. */
748 for (i = 1; i < graph->size; i++)
749 {
750 if (i == FIRST_REF_NODE)
751 continue;
752 if (find (i) != i)
753 continue;
754 if (i < FIRST_REF_NODE)
755 fprintf (file, "\"%s\"", get_varinfo (i)->name);
756 else
757 fprintf (file, "\"*%s\"", get_varinfo (i - FIRST_REF_NODE)->name);
758 if (graph->complex[i].exists ())
759 {
760 unsigned j;
761 constraint_t c;
762 fprintf (file, " [label=\"\\N\\n");
763 for (j = 0; graph->complex[i].iterate (j, &c); ++j)
764 {
765 dump_constraint (file, c);
766 fprintf (file, "\\l");
767 }
768 fprintf (file, "\"]");
769 }
770 fprintf (file, ";\n");
771 }
772
773 /* Go over the edges. */
774 fprintf (file, "\n // Edges in the constraint graph:\n");
775 for (i = 1; i < graph->size; i++)
776 {
777 unsigned j;
778 bitmap_iterator bi;
779 if (find (i) != i)
780 continue;
781 EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i], 0, j, bi)
782 {
783 unsigned to = find (j);
784 if (i == to)
785 continue;
786 if (i < FIRST_REF_NODE)
787 fprintf (file, "\"%s\"", get_varinfo (i)->name);
788 else
789 fprintf (file, "\"*%s\"", get_varinfo (i - FIRST_REF_NODE)->name);
790 fprintf (file, " -> ");
791 if (to < FIRST_REF_NODE)
792 fprintf (file, "\"%s\"", get_varinfo (to)->name);
793 else
794 fprintf (file, "\"*%s\"", get_varinfo (to - FIRST_REF_NODE)->name);
795 fprintf (file, ";\n");
796 }
797 }
798
799 /* Prints the tail of the dot file. */
800 fprintf (file, "}\n");
801}
802
803/* Print out the constraint graph to stderr. */
804
805DEBUG_FUNCTION void
806debug_constraint_graph (void)
807{
808 dump_constraint_graph (stderr);
809}
810
811/* SOLVER FUNCTIONS
812
813 The solver is a simple worklist solver, that works on the following
814 algorithm:
815
816 sbitmap changed_nodes = all zeroes;
817 changed_count = 0;
818 For each node that is not already collapsed:
819 changed_count++;
820 set bit in changed nodes
821
822 while (changed_count > 0)
823 {
824 compute topological ordering for constraint graph
825
826 find and collapse cycles in the constraint graph (updating
827 changed if necessary)
828
829 for each node (n) in the graph in topological order:
830 changed_count--;
831
832 Process each complex constraint associated with the node,
833 updating changed if necessary.
834
835 For each outgoing edge from n, propagate the solution from n to
836 the destination of the edge, updating changed as necessary.
837
838 } */
839
840/* Return true if two constraint expressions A and B are equal. */
841
842static bool
843constraint_expr_equal (struct constraint_expr a, struct constraint_expr b)
844{
845 return a.type == b.type && a.var == b.var && a.offset == b.offset;
846}
847
848/* Return true if constraint expression A is less than constraint expression
849 B. This is just arbitrary, but consistent, in order to give them an
850 ordering. */
851
852static bool
853constraint_expr_less (struct constraint_expr a, struct constraint_expr b)
854{
855 if (a.type == b.type)
856 {
857 if (a.var == b.var)
858 return a.offset < b.offset;
859 else
860 return a.var < b.var;
861 }
862 else
863 return a.type < b.type;
864}
865
866/* Return true if constraint A is less than constraint B. This is just
867 arbitrary, but consistent, in order to give them an ordering. */
868
869static bool
870constraint_less (const constraint_t &a, const constraint_t &b)
871{
872 if (constraint_expr_less (a->lhs, b->lhs))
873 return true;
874 else if (constraint_expr_less (b->lhs, a->lhs))
875 return false;
876 else
877 return constraint_expr_less (a->rhs, b->rhs);
878}
879
880/* Return true if two constraints A and B are equal. */
881
882static bool
883constraint_equal (struct constraint a, struct constraint b)
884{
885 return constraint_expr_equal (a.lhs, b.lhs)
886 && constraint_expr_equal (a.rhs, b.rhs);
887}
888
889
890/* Find a constraint LOOKFOR in the sorted constraint vector VEC */
891
892static constraint_t
893constraint_vec_find (vec<constraint_t> vec,
894 struct constraint lookfor)
895{
896 unsigned int place;
897 constraint_t found;
898
899 if (!vec.exists ())
900 return NULL;
901
902 place = vec.lower_bound (&lookfor, constraint_less);
903 if (place >= vec.length ())
904 return NULL;
905 found = vec[place];
906 if (!constraint_equal (*found, lookfor))
907 return NULL;
908 return found;
909}
910
911/* Union two constraint vectors, TO and FROM. Put the result in TO.
912 Returns true of TO set is changed. */
913
914static bool
915constraint_set_union (vec<constraint_t> *to,
916 vec<constraint_t> *from)
917{
918 int i;
919 constraint_t c;
920 bool any_change = false;
921
922 FOR_EACH_VEC_ELT (*from, i, c)
923 {
924 if (constraint_vec_find (*to, *c) == NULL)
925 {
926 unsigned int place = to->lower_bound (c, constraint_less);
927 to->safe_insert (place, c);
928 any_change = true;
929 }
930 }
931 return any_change;
932}
933
934/* Expands the solution in SET to all sub-fields of variables included. */
935
936static bitmap
937solution_set_expand (bitmap set, bitmap *expanded)
938{
939 bitmap_iterator bi;
940 unsigned j;
941
942 if (*expanded)
943 return *expanded;
944
945 *expanded = BITMAP_ALLOC (&iteration_obstack);
946
947 /* In a first pass expand to the head of the variables we need to
948 add all sub-fields off. This avoids quadratic behavior. */
949 EXECUTE_IF_SET_IN_BITMAP (set, 0, j, bi)
950 {
951 varinfo_t v = get_varinfo (j);
952 if (v->is_artificial_var
953 || v->is_full_var)
954 continue;
955 bitmap_set_bit (*expanded, v->head);
956 }
957
958 /* In the second pass now expand all head variables with subfields. */
959 EXECUTE_IF_SET_IN_BITMAP (*expanded, 0, j, bi)
960 {
961 varinfo_t v = get_varinfo (j);
962 if (v->head != j)
963 continue;
964 for (v = vi_next (v); v != NULL; v = vi_next (v))
965 bitmap_set_bit (*expanded, v->id);
966 }
967
968 /* And finally set the rest of the bits from SET. */
969 bitmap_ior_into (*expanded, set);
970
971 return *expanded;
972}
973
974/* Union solution sets TO and DELTA, and add INC to each member of DELTA in the
975 process. */
976
977static bool
978set_union_with_increment (bitmap to, bitmap delta, HOST_WIDE_INT inc,
979 bitmap *expanded_delta)
980{
981 bool changed = false;
982 bitmap_iterator bi;
983 unsigned int i;
984
985 /* If the solution of DELTA contains anything it is good enough to transfer
986 this to TO. */
987 if (bitmap_bit_p (delta, anything_id))
988 return bitmap_set_bit (to, anything_id);
989
990 /* If the offset is unknown we have to expand the solution to
991 all subfields. */
992 if (inc == UNKNOWN_OFFSET)
993 {
994 delta = solution_set_expand (delta, expanded_delta);
995 changed |= bitmap_ior_into (to, delta);
996 return changed;
997 }
998
999 /* For non-zero offset union the offsetted solution into the destination. */
1000 EXECUTE_IF_SET_IN_BITMAP (delta, 0, i, bi)
1001 {
1002 varinfo_t vi = get_varinfo (i);
1003
1004 /* If this is a variable with just one field just set its bit
1005 in the result. */
1006 if (vi->is_artificial_var
1007 || vi->is_unknown_size_var
1008 || vi->is_full_var)
1009 changed |= bitmap_set_bit (to, i);
1010 else
1011 {
1012 HOST_WIDE_INT fieldoffset = vi->offset + inc;
1013 unsigned HOST_WIDE_INT size = vi->size;
1014
1015 /* If the offset makes the pointer point to before the
1016 variable use offset zero for the field lookup. */
1017 if (fieldoffset < 0)
1018 vi = get_varinfo (vi->head);
1019 else
1020 vi = first_or_preceding_vi_for_offset (vi, fieldoffset);
1021
1022 do
1023 {
1024 changed |= bitmap_set_bit (to, vi->id);
1025 if (vi->is_full_var
1026 || vi->next == 0)
1027 break;
1028
1029 /* We have to include all fields that overlap the current field
1030 shifted by inc. */
1031 vi = vi_next (vi);
1032 }
1033 while (vi->offset < fieldoffset + size);
1034 }
1035 }
1036
1037 return changed;
1038}
1039
1040/* Insert constraint C into the list of complex constraints for graph
1041 node VAR. */
1042
1043static void
1044insert_into_complex (constraint_graph_t graph,
1045 unsigned int var, constraint_t c)
1046{
1047 vec<constraint_t> complex = graph->complex[var];
1048 unsigned int place = complex.lower_bound (c, constraint_less);
1049
1050 /* Only insert constraints that do not already exist. */
1051 if (place >= complex.length ()
1052 || !constraint_equal (*c, *complex[place]))
1053 graph->complex[var].safe_insert (place, c);
1054}
1055
1056
1057/* Condense two variable nodes into a single variable node, by moving
1058 all associated info from FROM to TO. Returns true if TO node's
1059 constraint set changes after the merge. */
1060
1061static bool
1062merge_node_constraints (constraint_graph_t graph, unsigned int to,
1063 unsigned int from)
1064{
1065 unsigned int i;
1066 constraint_t c;
1067 bool any_change = false;
1068
1069 gcc_checking_assert (find (from) == to);
1070
1071 /* Move all complex constraints from src node into to node */
1072 FOR_EACH_VEC_ELT (graph->complex[from], i, c)
1073 {
1074 /* In complex constraints for node FROM, we may have either
1075 a = *FROM, and *FROM = a, or an offseted constraint which are
1076 always added to the rhs node's constraints. */
1077
1078 if (c->rhs.type == DEREF)
1079 c->rhs.var = to;
1080 else if (c->lhs.type == DEREF)
1081 c->lhs.var = to;
1082 else
1083 c->rhs.var = to;
1084
1085 }
1086 any_change = constraint_set_union (&graph->complex[to],
1087 &graph->complex[from]);
1088 graph->complex[from].release ();
1089 return any_change;
1090}
1091
1092
1093/* Remove edges involving NODE from GRAPH. */
1094
1095static void
1096clear_edges_for_node (constraint_graph_t graph, unsigned int node)
1097{
1098 if (graph->succs[node])
1099 BITMAP_FREE (graph->succs[node]);
1100}
1101
1102/* Merge GRAPH nodes FROM and TO into node TO. */
1103
1104static void
1105merge_graph_nodes (constraint_graph_t graph, unsigned int to,
1106 unsigned int from)
1107{
1108 if (graph->indirect_cycles[from] != -1)
1109 {
1110 /* If we have indirect cycles with the from node, and we have
1111 none on the to node, the to node has indirect cycles from the
1112 from node now that they are unified.
1113 If indirect cycles exist on both, unify the nodes that they
1114 are in a cycle with, since we know they are in a cycle with
1115 each other. */
1116 if (graph->indirect_cycles[to] == -1)
1117 graph->indirect_cycles[to] = graph->indirect_cycles[from];
1118 }
1119
1120 /* Merge all the successor edges. */
1121 if (graph->succs[from])
1122 {
1123 if (!graph->succs[to])
1124 graph->succs[to] = BITMAP_ALLOC (&pta_obstack);
1125 bitmap_ior_into (graph->succs[to],
1126 graph->succs[from]);
1127 }
1128
1129 clear_edges_for_node (graph, from);
1130}
1131
1132
1133/* Add an indirect graph edge to GRAPH, going from TO to FROM if
1134 it doesn't exist in the graph already. */
1135
1136static void
1137add_implicit_graph_edge (constraint_graph_t graph, unsigned int to,
1138 unsigned int from)
1139{
1140 if (to == from)
1141 return;
1142
1143 if (!graph->implicit_preds[to])
1144 graph->implicit_preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
1145
1146 if (bitmap_set_bit (graph->implicit_preds[to], from))
1147 stats.num_implicit_edges++;
1148}
1149
1150/* Add a predecessor graph edge to GRAPH, going from TO to FROM if
1151 it doesn't exist in the graph already.
1152 Return false if the edge already existed, true otherwise. */
1153
1154static void
1155add_pred_graph_edge (constraint_graph_t graph, unsigned int to,
1156 unsigned int from)
1157{
1158 if (!graph->preds[to])
1159 graph->preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
1160 bitmap_set_bit (graph->preds[to], from);
1161}
1162
1163/* Add a graph edge to GRAPH, going from FROM to TO if
1164 it doesn't exist in the graph already.
1165 Return false if the edge already existed, true otherwise. */
1166
1167static bool
1168add_graph_edge (constraint_graph_t graph, unsigned int to,
1169 unsigned int from)
1170{
1171 if (to == from)
1172 {
1173 return false;
1174 }
1175 else
1176 {
1177 bool r = false;
1178
1179 if (!graph->succs[from])
1180 graph->succs[from] = BITMAP_ALLOC (&pta_obstack);
1181 if (bitmap_set_bit (graph->succs[from], to))
1182 {
1183 r = true;
1184 if (to < FIRST_REF_NODE && from < FIRST_REF_NODE)
1185 stats.num_edges++;
1186 }
1187 return r;
1188 }
1189}
1190
1191
1192/* Initialize the constraint graph structure to contain SIZE nodes. */
1193
1194static void
1195init_graph (unsigned int size)
1196{
1197 unsigned int j;
1198
1199 graph = XCNEW (struct constraint_graph);
1200 graph->size = size;
1201 graph->succs = XCNEWVEC (bitmap, graph->size);
1202 graph->indirect_cycles = XNEWVEC (int, graph->size);
1203 graph->rep = XNEWVEC (unsigned int, graph->size);
1204 /* ??? Macros do not support template types with multiple arguments,
1205 so we use a typedef to work around it. */
1206 typedef vec<constraint_t> vec_constraint_t_heap;
1207 graph->complex = XCNEWVEC (vec_constraint_t_heap, size);
1208 graph->pe = XCNEWVEC (unsigned int, graph->size);
1209 graph->pe_rep = XNEWVEC (int, graph->size);
1210
1211 for (j = 0; j < graph->size; j++)
1212 {
1213 graph->rep[j] = j;
1214 graph->pe_rep[j] = -1;
1215 graph->indirect_cycles[j] = -1;
1216 }
1217}
1218
1219/* Build the constraint graph, adding only predecessor edges right now. */
1220
1221static void
1222build_pred_graph (void)
1223{
1224 int i;
1225 constraint_t c;
1226 unsigned int j;
1227
1228 graph->implicit_preds = XCNEWVEC (bitmap, graph->size);
1229 graph->preds = XCNEWVEC (bitmap, graph->size);
1230 graph->pointer_label = XCNEWVEC (unsigned int, graph->size);
1231 graph->loc_label = XCNEWVEC (unsigned int, graph->size);
1232 graph->pointed_by = XCNEWVEC (bitmap, graph->size);
1233 graph->points_to = XCNEWVEC (bitmap, graph->size);
1234 graph->eq_rep = XNEWVEC (int, graph->size);
1235 graph->direct_nodes = sbitmap_alloc (graph->size);
1236 graph->address_taken = BITMAP_ALLOC (&predbitmap_obstack);
1237 bitmap_clear (graph->direct_nodes);
1238
1239 for (j = 1; j < FIRST_REF_NODE; j++)
1240 {
1241 if (!get_varinfo (j)->is_special_var)
1242 bitmap_set_bit (graph->direct_nodes, j);
1243 }
1244
1245 for (j = 0; j < graph->size; j++)
1246 graph->eq_rep[j] = -1;
1247
1248 for (j = 0; j < varmap.length (); j++)
1249 graph->indirect_cycles[j] = -1;
1250
1251 FOR_EACH_VEC_ELT (constraints, i, c)
1252 {
1253 struct constraint_expr lhs = c->lhs;
1254 struct constraint_expr rhs = c->rhs;
1255 unsigned int lhsvar = lhs.var;
1256 unsigned int rhsvar = rhs.var;
1257
1258 if (lhs.type == DEREF)
1259 {
1260 /* *x = y. */
1261 if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
1262 add_pred_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
1263 }
1264 else if (rhs.type == DEREF)
1265 {
1266 /* x = *y */
1267 if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
1268 add_pred_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
1269 else
1270 bitmap_clear_bit (graph->direct_nodes, lhsvar);
1271 }
1272 else if (rhs.type == ADDRESSOF)
1273 {
1274 varinfo_t v;
1275
1276 /* x = &y */
1277 if (graph->points_to[lhsvar] == NULL)
1278 graph->points_to[lhsvar] = BITMAP_ALLOC (&predbitmap_obstack);
1279 bitmap_set_bit (graph->points_to[lhsvar], rhsvar);
1280
1281 if (graph->pointed_by[rhsvar] == NULL)
1282 graph->pointed_by[rhsvar] = BITMAP_ALLOC (&predbitmap_obstack);
1283 bitmap_set_bit (graph->pointed_by[rhsvar], lhsvar);
1284
1285 /* Implicitly, *x = y */
1286 add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
1287
1288 /* All related variables are no longer direct nodes. */
1289 bitmap_clear_bit (graph->direct_nodes, rhsvar);
1290 v = get_varinfo (rhsvar);
1291 if (!v->is_full_var)
1292 {
1293 v = get_varinfo (v->head);
1294 do
1295 {
1296 bitmap_clear_bit (graph->direct_nodes, v->id);
1297 v = vi_next (v);
1298 }
1299 while (v != NULL);
1300 }
1301 bitmap_set_bit (graph->address_taken, rhsvar);
1302 }
1303 else if (lhsvar > anything_id
1304 && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
1305 {
1306 /* x = y */
1307 add_pred_graph_edge (graph, lhsvar, rhsvar);
1308 /* Implicitly, *x = *y */
1309 add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar,
1310 FIRST_REF_NODE + rhsvar);
1311 }
1312 else if (lhs.offset != 0 || rhs.offset != 0)
1313 {
1314 if (rhs.offset != 0)
1315 bitmap_clear_bit (graph->direct_nodes, lhs.var);
1316 else if (lhs.offset != 0)
1317 bitmap_clear_bit (graph->direct_nodes, rhs.var);
1318 }
1319 }
1320}
1321
1322/* Build the constraint graph, adding successor edges. */
1323
1324static void
1325build_succ_graph (void)
1326{
1327 unsigned i, t;
1328 constraint_t c;
1329
1330 FOR_EACH_VEC_ELT (constraints, i, c)
1331 {
1332 struct constraint_expr lhs;
1333 struct constraint_expr rhs;
1334 unsigned int lhsvar;
1335 unsigned int rhsvar;
1336
1337 if (!c)
1338 continue;
1339
1340 lhs = c->lhs;
1341 rhs = c->rhs;
1342 lhsvar = find (lhs.var);
1343 rhsvar = find (rhs.var);
1344
1345 if (lhs.type == DEREF)
1346 {
1347 if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
1348 add_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
1349 }
1350 else if (rhs.type == DEREF)
1351 {
1352 if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
1353 add_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
1354 }
1355 else if (rhs.type == ADDRESSOF)
1356 {
1357 /* x = &y */
1358 gcc_checking_assert (find (rhs.var) == rhs.var);
1359 bitmap_set_bit (get_varinfo (lhsvar)->solution, rhsvar);
1360 }
1361 else if (lhsvar > anything_id
1362 && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
1363 {
1364 add_graph_edge (graph, lhsvar, rhsvar);
1365 }
1366 }
1367
1368 /* Add edges from STOREDANYTHING to all non-direct nodes that can
1369 receive pointers. */
1370 t = find (storedanything_id);
1371 for (i = integer_id + 1; i < FIRST_REF_NODE; ++i)
1372 {
1373 if (!bitmap_bit_p (graph->direct_nodes, i)
1374 && get_varinfo (i)->may_have_pointers)
1375 add_graph_edge (graph, find (i), t);
1376 }
1377
1378 /* Everything stored to ANYTHING also potentially escapes. */
1379 add_graph_edge (graph, find (escaped_id), t);
1380}
1381
1382
1383/* Changed variables on the last iteration. */
1384static bitmap changed;
1385
1386/* Strongly Connected Component visitation info. */
1387
1388struct scc_info
1389{
1390 scc_info (size_t size);
1391 ~scc_info ();
1392
1393 auto_sbitmap visited;
1394 auto_sbitmap deleted;
1395 unsigned int *dfs;
1396 unsigned int *node_mapping;
1397 int current_index;
1398 auto_vec<unsigned> scc_stack;
1399};
1400
1401
1402/* Recursive routine to find strongly connected components in GRAPH.
1403 SI is the SCC info to store the information in, and N is the id of current
1404 graph node we are processing.
1405
1406 This is Tarjan's strongly connected component finding algorithm, as
1407 modified by Nuutila to keep only non-root nodes on the stack.
1408 The algorithm can be found in "On finding the strongly connected
1409 connected components in a directed graph" by Esko Nuutila and Eljas
1410 Soisalon-Soininen, in Information Processing Letters volume 49,
1411 number 1, pages 9-14. */
1412
1413static void
1414scc_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
1415{
1416 unsigned int i;
1417 bitmap_iterator bi;
1418 unsigned int my_dfs;
1419
1420 bitmap_set_bit (si->visited, n);
1421 si->dfs[n] = si->current_index ++;
1422 my_dfs = si->dfs[n];
1423
1424 /* Visit all the successors. */
1425 EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[n], 0, i, bi)
1426 {
1427 unsigned int w;
1428
1429 if (i > LAST_REF_NODE)
1430 break;
1431
1432 w = find (i);
1433 if (bitmap_bit_p (si->deleted, w))
1434 continue;
1435
1436 if (!bitmap_bit_p (si->visited, w))
1437 scc_visit (graph, si, w);
1438
1439 unsigned int t = find (w);
1440 gcc_checking_assert (find (n) == n);
1441 if (si->dfs[t] < si->dfs[n])
1442 si->dfs[n] = si->dfs[t];
1443 }
1444
1445 /* See if any components have been identified. */
1446 if (si->dfs[n] == my_dfs)
1447 {
1448 if (si->scc_stack.length () > 0
1449 && si->dfs[si->scc_stack.last ()] >= my_dfs)
1450 {
1451 bitmap scc = BITMAP_ALLOC (NULL);
1452 unsigned int lowest_node;
1453 bitmap_iterator bi;
1454
1455 bitmap_set_bit (scc, n);
1456
1457 while (si->scc_stack.length () != 0
1458 && si->dfs[si->scc_stack.last ()] >= my_dfs)
1459 {
1460 unsigned int w = si->scc_stack.pop ();
1461
1462 bitmap_set_bit (scc, w);
1463 }
1464
1465 lowest_node = bitmap_first_set_bit (scc);
1466 gcc_assert (lowest_node < FIRST_REF_NODE);
1467
1468 /* Collapse the SCC nodes into a single node, and mark the
1469 indirect cycles. */
1470 EXECUTE_IF_SET_IN_BITMAP (scc, 0, i, bi)
1471 {
1472 if (i < FIRST_REF_NODE)
1473 {
1474 if (unite (lowest_node, i))
1475 unify_nodes (graph, lowest_node, i, false);
1476 }
1477 else
1478 {
1479 unite (lowest_node, i);
1480 graph->indirect_cycles[i - FIRST_REF_NODE] = lowest_node;
1481 }
1482 }
1483 }
1484 bitmap_set_bit (si->deleted, n);
1485 }
1486 else
1487 si->scc_stack.safe_push (n);
1488}
1489
1490/* Unify node FROM into node TO, updating the changed count if
1491 necessary when UPDATE_CHANGED is true. */
1492
1493static void
1494unify_nodes (constraint_graph_t graph, unsigned int to, unsigned int from,
1495 bool update_changed)
1496{
1497 gcc_checking_assert (to != from && find (to) == to);
1498
1499 if (dump_file && (dump_flags & TDF_DETAILS))
1500 fprintf (dump_file, "Unifying %s to %s\n",
1501 get_varinfo (from)->name,
1502 get_varinfo (to)->name);
1503
1504 if (update_changed)
1505 stats.unified_vars_dynamic++;
1506 else
1507 stats.unified_vars_static++;
1508
1509 merge_graph_nodes (graph, to, from);
1510 if (merge_node_constraints (graph, to, from))
1511 {
1512 if (update_changed)
1513 bitmap_set_bit (changed, to);
1514 }
1515
1516 /* Mark TO as changed if FROM was changed. If TO was already marked
1517 as changed, decrease the changed count. */
1518
1519 if (update_changed
1520 && bitmap_clear_bit (changed, from))
1521 bitmap_set_bit (changed, to);
1522 varinfo_t fromvi = get_varinfo (from);
1523 if (fromvi->solution)
1524 {
1525 /* If the solution changes because of the merging, we need to mark
1526 the variable as changed. */
1527 varinfo_t tovi = get_varinfo (to);
1528 if (bitmap_ior_into (tovi->solution, fromvi->solution))
1529 {
1530 if (update_changed)
1531 bitmap_set_bit (changed, to);
1532 }
1533
1534 BITMAP_FREE (fromvi->solution);
1535 if (fromvi->oldsolution)
1536 BITMAP_FREE (fromvi->oldsolution);
1537
1538 if (stats.iterations > 0
1539 && tovi->oldsolution)
1540 BITMAP_FREE (tovi->oldsolution);
1541 }
1542 if (graph->succs[to])
1543 bitmap_clear_bit (graph->succs[to], to);
1544}
1545
1546/* Information needed to compute the topological ordering of a graph. */
1547
1548struct topo_info
1549{
1550 /* sbitmap of visited nodes. */
1551 sbitmap visited;
1552 /* Array that stores the topological order of the graph, *in
1553 reverse*. */
1554 vec<unsigned> topo_order;
1555};
1556
1557
1558/* Initialize and return a topological info structure. */
1559
1560static struct topo_info *
1561init_topo_info (void)
1562{
1563 size_t size = graph->size;
1564 struct topo_info *ti = XNEW (struct topo_info);
1565 ti->visited = sbitmap_alloc (size);
1566 bitmap_clear (ti->visited);
1567 ti->topo_order.create (1);
1568 return ti;
1569}
1570
1571
1572/* Free the topological sort info pointed to by TI. */
1573
1574static void
1575free_topo_info (struct topo_info *ti)
1576{
1577 sbitmap_free (ti->visited);
1578 ti->topo_order.release ();
1579 free (ti);
1580}
1581
1582/* Visit the graph in topological order, and store the order in the
1583 topo_info structure. */
1584
1585static void
1586topo_visit (constraint_graph_t graph, struct topo_info *ti,
1587 unsigned int n)
1588{
1589 bitmap_iterator bi;
1590 unsigned int j;
1591
1592 bitmap_set_bit (ti->visited, n);
1593
1594 if (graph->succs[n])
1595 EXECUTE_IF_SET_IN_BITMAP (graph->succs[n], 0, j, bi)
1596 {
1597 if (!bitmap_bit_p (ti->visited, j))
1598 topo_visit (graph, ti, j);
1599 }
1600
1601 ti->topo_order.safe_push (n);
1602}
1603
1604/* Process a constraint C that represents x = *(y + off), using DELTA as the
1605 starting solution for y. */
1606
1607static void
1608do_sd_constraint (constraint_graph_t graph, constraint_t c,
1609 bitmap delta, bitmap *expanded_delta)
1610{
1611 unsigned int lhs = c->lhs.var;
1612 bool flag = false;
1613 bitmap sol = get_varinfo (lhs)->solution;
1614 unsigned int j;
1615 bitmap_iterator bi;
1616 HOST_WIDE_INT roffset = c->rhs.offset;
1617
1618 /* Our IL does not allow this. */
1619 gcc_checking_assert (c->lhs.offset == 0);
1620
1621 /* If the solution of Y contains anything it is good enough to transfer
1622 this to the LHS. */
1623 if (bitmap_bit_p (delta, anything_id))
1624 {
1625 flag |= bitmap_set_bit (sol, anything_id);
1626 goto done;
1627 }
1628
1629 /* If we do not know at with offset the rhs is dereferenced compute
1630 the reachability set of DELTA, conservatively assuming it is
1631 dereferenced at all valid offsets. */
1632 if (roffset == UNKNOWN_OFFSET)
1633 {
1634 delta = solution_set_expand (delta, expanded_delta);
1635 /* No further offset processing is necessary. */
1636 roffset = 0;
1637 }
1638
1639 /* For each variable j in delta (Sol(y)), add
1640 an edge in the graph from j to x, and union Sol(j) into Sol(x). */
1641 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1642 {
1643 varinfo_t v = get_varinfo (j);
1644 HOST_WIDE_INT fieldoffset = v->offset + roffset;
1645 unsigned HOST_WIDE_INT size = v->size;
1646 unsigned int t;
1647
1648 if (v->is_full_var)
1649 ;
1650 else if (roffset != 0)
1651 {
1652 if (fieldoffset < 0)
1653 v = get_varinfo (v->head);
1654 else
1655 v = first_or_preceding_vi_for_offset (v, fieldoffset);
1656 }
1657
1658 /* We have to include all fields that overlap the current field
1659 shifted by roffset. */
1660 do
1661 {
1662 t = find (v->id);
1663
1664 /* Adding edges from the special vars is pointless.
1665 They don't have sets that can change. */
1666 if (get_varinfo (t)->is_special_var)
1667 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1668 /* Merging the solution from ESCAPED needlessly increases
1669 the set. Use ESCAPED as representative instead. */
1670 else if (v->id == escaped_id)
1671 flag |= bitmap_set_bit (sol, escaped_id);
1672 else if (v->may_have_pointers
1673 && add_graph_edge (graph, lhs, t))
1674 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
1675
1676 if (v->is_full_var
1677 || v->next == 0)
1678 break;
1679
1680 v = vi_next (v);
1681 }
1682 while (v->offset < fieldoffset + size);
1683 }
1684
1685done:
1686 /* If the LHS solution changed, mark the var as changed. */
1687 if (flag)
1688 {
1689 get_varinfo (lhs)->solution = sol;
1690 bitmap_set_bit (changed, lhs);
1691 }
1692}
1693
1694/* Process a constraint C that represents *(x + off) = y using DELTA
1695 as the starting solution for x. */
1696
1697static void
1698do_ds_constraint (constraint_t c, bitmap delta, bitmap *expanded_delta)
1699{
1700 unsigned int rhs = c->rhs.var;
1701 bitmap sol = get_varinfo (rhs)->solution;
1702 unsigned int j;
1703 bitmap_iterator bi;
1704 HOST_WIDE_INT loff = c->lhs.offset;
1705 bool escaped_p = false;
1706
1707 /* Our IL does not allow this. */
1708 gcc_checking_assert (c->rhs.offset == 0);
1709
1710 /* If the solution of y contains ANYTHING simply use the ANYTHING
1711 solution. This avoids needlessly increasing the points-to sets. */
1712 if (bitmap_bit_p (sol, anything_id))
1713 sol = get_varinfo (find (anything_id))->solution;
1714
1715 /* If the solution for x contains ANYTHING we have to merge the
1716 solution of y into all pointer variables which we do via
1717 STOREDANYTHING. */
1718 if (bitmap_bit_p (delta, anything_id))
1719 {
1720 unsigned t = find (storedanything_id);
1721 if (add_graph_edge (graph, t, rhs))
1722 {
1723 if (bitmap_ior_into (get_varinfo (t)->solution, sol))
1724 bitmap_set_bit (changed, t);
1725 }
1726 return;
1727 }
1728
1729 /* If we do not know at with offset the rhs is dereferenced compute
1730 the reachability set of DELTA, conservatively assuming it is
1731 dereferenced at all valid offsets. */
1732 if (loff == UNKNOWN_OFFSET)
1733 {
1734 delta = solution_set_expand (delta, expanded_delta);
1735 loff = 0;
1736 }
1737
1738 /* For each member j of delta (Sol(x)), add an edge from y to j and
1739 union Sol(y) into Sol(j) */
1740 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
1741 {
1742 varinfo_t v = get_varinfo (j);
1743 unsigned int t;
1744 HOST_WIDE_INT fieldoffset = v->offset + loff;
1745 unsigned HOST_WIDE_INT size = v->size;
1746
1747 if (v->is_full_var)
1748 ;
1749 else if (loff != 0)
1750 {
1751 if (fieldoffset < 0)
1752 v = get_varinfo (v->head);
1753 else
1754 v = first_or_preceding_vi_for_offset (v, fieldoffset);
1755 }
1756
1757 /* We have to include all fields that overlap the current field
1758 shifted by loff. */
1759 do
1760 {
1761 if (v->may_have_pointers)
1762 {
1763 /* If v is a global variable then this is an escape point. */
1764 if (v->is_global_var
1765 && !escaped_p)
1766 {
1767 t = find (escaped_id);
1768 if (add_graph_edge (graph, t, rhs)
1769 && bitmap_ior_into (get_varinfo (t)->solution, sol))
1770 bitmap_set_bit (changed, t);
1771 /* Enough to let rhs escape once. */
1772 escaped_p = true;
1773 }
1774
1775 if (v->is_special_var)
1776 break;
1777
1778 t = find (v->id);
1779 if (add_graph_edge (graph, t, rhs)
1780 && bitmap_ior_into (get_varinfo (t)->solution, sol))
1781 bitmap_set_bit (changed, t);
1782 }
1783
1784 if (v->is_full_var
1785 || v->next == 0)
1786 break;
1787
1788 v = vi_next (v);
1789 }
1790 while (v->offset < fieldoffset + size);
1791 }
1792}
1793
1794/* Handle a non-simple (simple meaning requires no iteration),
1795 constraint (IE *x = &y, x = *y, *x = y, and x = y with offsets involved). */
1796
1797static void
1798do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta,
1799 bitmap *expanded_delta)
1800{
1801 if (c->lhs.type == DEREF)
1802 {
1803 if (c->rhs.type == ADDRESSOF)
1804 {
1805 gcc_unreachable ();
1806 }
1807 else
1808 {
1809 /* *x = y */
1810 do_ds_constraint (c, delta, expanded_delta);
1811 }
1812 }
1813 else if (c->rhs.type == DEREF)
1814 {
1815 /* x = *y */
1816 if (!(get_varinfo (c->lhs.var)->is_special_var))
1817 do_sd_constraint (graph, c, delta, expanded_delta);
1818 }
1819 else
1820 {
1821 bitmap tmp;
1822 bool flag = false;
1823
1824 gcc_checking_assert (c->rhs.type == SCALAR && c->lhs.type == SCALAR
1825 && c->rhs.offset != 0 && c->lhs.offset == 0);
1826 tmp = get_varinfo (c->lhs.var)->solution;
1827
1828 flag = set_union_with_increment (tmp, delta, c->rhs.offset,
1829 expanded_delta);
1830
1831 if (flag)
1832 bitmap_set_bit (changed, c->lhs.var);
1833 }
1834}
1835
1836/* Initialize and return a new SCC info structure. */
1837
1838scc_info::scc_info (size_t size) :
1839 visited (size), deleted (size), current_index (0), scc_stack (1)
1840{
1841 bitmap_clear (visited);
1842 bitmap_clear (deleted);
1843 node_mapping = XNEWVEC (unsigned int, size);
1844 dfs = XCNEWVEC (unsigned int, size);
1845
1846 for (size_t i = 0; i < size; i++)
1847 node_mapping[i] = i;
1848}
1849
1850/* Free an SCC info structure pointed to by SI */
1851
1852scc_info::~scc_info ()
1853{
1854 free (node_mapping);
1855 free (dfs);
1856}
1857
1858
1859/* Find indirect cycles in GRAPH that occur, using strongly connected
1860 components, and note them in the indirect cycles map.
1861
1862 This technique comes from Ben Hardekopf and Calvin Lin,
1863 "It Pays to be Lazy: Fast and Accurate Pointer Analysis for Millions of
1864 Lines of Code", submitted to PLDI 2007. */
1865
1866static void
1867find_indirect_cycles (constraint_graph_t graph)
1868{
1869 unsigned int i;
1870 unsigned int size = graph->size;
1871 scc_info si (size);
1872
1873 for (i = 0; i < MIN (LAST_REF_NODE, size); i ++ )
1874 if (!bitmap_bit_p (si.visited, i) && find (i) == i)
1875 scc_visit (graph, &si, i);
1876}
1877
1878/* Compute a topological ordering for GRAPH, and store the result in the
1879 topo_info structure TI. */
1880
1881static void
1882compute_topo_order (constraint_graph_t graph,
1883 struct topo_info *ti)
1884{
1885 unsigned int i;
1886 unsigned int size = graph->size;
1887
1888 for (i = 0; i != size; ++i)
1889 if (!bitmap_bit_p (ti->visited, i) && find (i) == i)
1890 topo_visit (graph, ti, i);
1891}
1892
1893/* Structure used to for hash value numbering of pointer equivalence
1894 classes. */
1895
1896typedef struct equiv_class_label
1897{
1898 hashval_t hashcode;
1899 unsigned int equivalence_class;
1900 bitmap labels;
1901} *equiv_class_label_t;
1902typedef const struct equiv_class_label *const_equiv_class_label_t;
1903
1904/* Equiv_class_label hashtable helpers. */
1905
1906struct equiv_class_hasher : free_ptr_hash <equiv_class_label>
1907{
1908 static inline hashval_t hash (const equiv_class_label *);
1909 static inline bool equal (const equiv_class_label *,
1910 const equiv_class_label *);
1911};
1912
1913/* Hash function for a equiv_class_label_t */
1914
1915inline hashval_t
1916equiv_class_hasher::hash (const equiv_class_label *ecl)
1917{
1918 return ecl->hashcode;
1919}
1920
1921/* Equality function for two equiv_class_label_t's. */
1922
1923inline bool
1924equiv_class_hasher::equal (const equiv_class_label *eql1,
1925 const equiv_class_label *eql2)
1926{
1927 return (eql1->hashcode == eql2->hashcode
1928 && bitmap_equal_p (eql1->labels, eql2->labels));
1929}
1930
1931/* A hashtable for mapping a bitmap of labels->pointer equivalence
1932 classes. */
1933static hash_table<equiv_class_hasher> *pointer_equiv_class_table;
1934
1935/* A hashtable for mapping a bitmap of labels->location equivalence
1936 classes. */
1937static hash_table<equiv_class_hasher> *location_equiv_class_table;
1938
1939/* Lookup a equivalence class in TABLE by the bitmap of LABELS with
1940 hash HAS it contains. Sets *REF_LABELS to the bitmap LABELS
1941 is equivalent to. */
1942
1943static equiv_class_label *
1944equiv_class_lookup_or_add (hash_table<equiv_class_hasher> *table,
1945 bitmap labels)
1946{
1947 equiv_class_label **slot;
1948 equiv_class_label ecl;
1949
1950 ecl.labels = labels;
1951 ecl.hashcode = bitmap_hash (labels);
1952 slot = table->find_slot (&ecl, INSERT);
1953 if (!*slot)
1954 {
1955 *slot = XNEW (struct equiv_class_label);
1956 (*slot)->labels = labels;
1957 (*slot)->hashcode = ecl.hashcode;
1958 (*slot)->equivalence_class = 0;
1959 }
1960
1961 return *slot;
1962}
1963
1964/* Perform offline variable substitution.
1965
1966 This is a worst case quadratic time way of identifying variables
1967 that must have equivalent points-to sets, including those caused by
1968 static cycles, and single entry subgraphs, in the constraint graph.
1969
1970 The technique is described in "Exploiting Pointer and Location
1971 Equivalence to Optimize Pointer Analysis. In the 14th International
1972 Static Analysis Symposium (SAS), August 2007." It is known as the
1973 "HU" algorithm, and is equivalent to value numbering the collapsed
1974 constraint graph including evaluating unions.
1975
1976 The general method of finding equivalence classes is as follows:
1977 Add fake nodes (REF nodes) and edges for *a = b and a = *b constraints.
1978 Initialize all non-REF nodes to be direct nodes.
1979 For each constraint a = a U {b}, we set pts(a) = pts(a) u {fresh
1980 variable}
1981 For each constraint containing the dereference, we also do the same
1982 thing.
1983
1984 We then compute SCC's in the graph and unify nodes in the same SCC,
1985 including pts sets.
1986
1987 For each non-collapsed node x:
1988 Visit all unvisited explicit incoming edges.
1989 Ignoring all non-pointers, set pts(x) = Union of pts(a) for y
1990 where y->x.
1991 Lookup the equivalence class for pts(x).
1992 If we found one, equivalence_class(x) = found class.
1993 Otherwise, equivalence_class(x) = new class, and new_class is
1994 added to the lookup table.
1995
1996 All direct nodes with the same equivalence class can be replaced
1997 with a single representative node.
1998 All unlabeled nodes (label == 0) are not pointers and all edges
1999 involving them can be eliminated.
2000 We perform these optimizations during rewrite_constraints
2001
2002 In addition to pointer equivalence class finding, we also perform
2003 location equivalence class finding. This is the set of variables
2004 that always appear together in points-to sets. We use this to
2005 compress the size of the points-to sets. */
2006
2007/* Current maximum pointer equivalence class id. */
2008static int pointer_equiv_class;
2009
2010/* Current maximum location equivalence class id. */
2011static int location_equiv_class;
2012
2013/* Recursive routine to find strongly connected components in GRAPH,
2014 and label it's nodes with DFS numbers. */
2015
2016static void
2017condense_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
2018{
2019 unsigned int i;
2020 bitmap_iterator bi;
2021 unsigned int my_dfs;
2022
2023 gcc_checking_assert (si->node_mapping[n] == n);
2024 bitmap_set_bit (si->visited, n);
2025 si->dfs[n] = si->current_index ++;
2026 my_dfs = si->dfs[n];
2027
2028 /* Visit all the successors. */
2029 EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
2030 {
2031 unsigned int w = si->node_mapping[i];
2032
2033 if (bitmap_bit_p (si->deleted, w))
2034 continue;
2035
2036 if (!bitmap_bit_p (si->visited, w))
2037 condense_visit (graph, si, w);
2038
2039 unsigned int t = si->node_mapping[w];
2040 gcc_checking_assert (si->node_mapping[n] == n);
2041 if (si->dfs[t] < si->dfs[n])
2042 si->dfs[n] = si->dfs[t];
2043 }
2044
2045 /* Visit all the implicit predecessors. */
2046 EXECUTE_IF_IN_NONNULL_BITMAP (graph->implicit_preds[n], 0, i, bi)
2047 {
2048 unsigned int w = si->node_mapping[i];
2049
2050 if (bitmap_bit_p (si->deleted, w))
2051 continue;
2052
2053 if (!bitmap_bit_p (si->visited, w))
2054 condense_visit (graph, si, w);
2055
2056 unsigned int t = si->node_mapping[w];
2057 gcc_assert (si->node_mapping[n] == n);
2058 if (si->dfs[t] < si->dfs[n])
2059 si->dfs[n] = si->dfs[t];
2060 }
2061
2062 /* See if any components have been identified. */
2063 if (si->dfs[n] == my_dfs)
2064 {
2065 while (si->scc_stack.length () != 0
2066 && si->dfs[si->scc_stack.last ()] >= my_dfs)
2067 {
2068 unsigned int w = si->scc_stack.pop ();
2069 si->node_mapping[w] = n;
2070
2071 if (!bitmap_bit_p (graph->direct_nodes, w))
2072 bitmap_clear_bit (graph->direct_nodes, n);
2073
2074 /* Unify our nodes. */
2075 if (graph->preds[w])
2076 {
2077 if (!graph->preds[n])
2078 graph->preds[n] = BITMAP_ALLOC (&predbitmap_obstack);
2079 bitmap_ior_into (graph->preds[n], graph->preds[w]);
2080 }
2081 if (graph->implicit_preds[w])
2082 {
2083 if (!graph->implicit_preds[n])
2084 graph->implicit_preds[n] = BITMAP_ALLOC (&predbitmap_obstack);
2085 bitmap_ior_into (graph->implicit_preds[n],
2086 graph->implicit_preds[w]);
2087 }
2088 if (graph->points_to[w])
2089 {
2090 if (!graph->points_to[n])
2091 graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
2092 bitmap_ior_into (graph->points_to[n],
2093 graph->points_to[w]);
2094 }
2095 }
2096 bitmap_set_bit (si->deleted, n);
2097 }
2098 else
2099 si->scc_stack.safe_push (n);
2100}
2101
2102/* Label pointer equivalences.
2103
2104 This performs a value numbering of the constraint graph to
2105 discover which variables will always have the same points-to sets
2106 under the current set of constraints.
2107
2108 The way it value numbers is to store the set of points-to bits
2109 generated by the constraints and graph edges. This is just used as a
2110 hash and equality comparison. The *actual set of points-to bits* is
2111 completely irrelevant, in that we don't care about being able to
2112 extract them later.
2113
2114 The equality values (currently bitmaps) just have to satisfy a few
2115 constraints, the main ones being:
2116 1. The combining operation must be order independent.
2117 2. The end result of a given set of operations must be unique iff the
2118 combination of input values is unique
2119 3. Hashable. */
2120
2121static void
2122label_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
2123{
2124 unsigned int i, first_pred;
2125 bitmap_iterator bi;
2126
2127 bitmap_set_bit (si->visited, n);
2128
2129 /* Label and union our incoming edges's points to sets. */
2130 first_pred = -1U;
2131 EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
2132 {
2133 unsigned int w = si->node_mapping[i];
2134 if (!bitmap_bit_p (si->visited, w))
2135 label_visit (graph, si, w);
2136
2137 /* Skip unused edges */
2138 if (w == n || graph->pointer_label[w] == 0)
2139 continue;
2140
2141 if (graph->points_to[w])
2142 {
2143 if (!graph->points_to[n])
2144 {
2145 if (first_pred == -1U)
2146 first_pred = w;
2147 else
2148 {
2149 graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
2150 bitmap_ior (graph->points_to[n],
2151 graph->points_to[first_pred],
2152 graph->points_to[w]);
2153 }
2154 }
2155 else
2156 bitmap_ior_into (graph->points_to[n], graph->points_to[w]);
2157 }
2158 }
2159
2160 /* Indirect nodes get fresh variables and a new pointer equiv class. */
2161 if (!bitmap_bit_p (graph->direct_nodes, n))
2162 {
2163 if (!graph->points_to[n])
2164 {
2165 graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
2166 if (first_pred != -1U)
2167 bitmap_copy (graph->points_to[n], graph->points_to[first_pred]);
2168 }
2169 bitmap_set_bit (graph->points_to[n], FIRST_REF_NODE + n);
2170 graph->pointer_label[n] = pointer_equiv_class++;
2171 equiv_class_label_t ecl;
2172 ecl = equiv_class_lookup_or_add (pointer_equiv_class_table,
2173 graph->points_to[n]);
2174 ecl->equivalence_class = graph->pointer_label[n];
2175 return;
2176 }
2177
2178 /* If there was only a single non-empty predecessor the pointer equiv
2179 class is the same. */
2180 if (!graph->points_to[n])
2181 {
2182 if (first_pred != -1U)
2183 {
2184 graph->pointer_label[n] = graph->pointer_label[first_pred];
2185 graph->points_to[n] = graph->points_to[first_pred];
2186 }
2187 return;
2188 }
2189
2190 if (!bitmap_empty_p (graph->points_to[n]))
2191 {
2192 equiv_class_label_t ecl;
2193 ecl = equiv_class_lookup_or_add (pointer_equiv_class_table,
2194 graph->points_to[n]);
2195 if (ecl->equivalence_class == 0)
2196 ecl->equivalence_class = pointer_equiv_class++;
2197 else
2198 {
2199 BITMAP_FREE (graph->points_to[n]);
2200 graph->points_to[n] = ecl->labels;
2201 }
2202 graph->pointer_label[n] = ecl->equivalence_class;
2203 }
2204}
2205
2206/* Print the pred graph in dot format. */
2207
2208static void
2209dump_pred_graph (struct scc_info *si, FILE *file)
2210{
2211 unsigned int i;
2212
2213 /* Only print the graph if it has already been initialized: */
2214 if (!graph)
2215 return;
2216
2217 /* Prints the header of the dot file: */
2218 fprintf (file, "strict digraph {\n");
2219 fprintf (file, " node [\n shape = box\n ]\n");
2220 fprintf (file, " edge [\n fontsize = \"12\"\n ]\n");
2221 fprintf (file, "\n // List of nodes and complex constraints in "
2222 "the constraint graph:\n");
2223
2224 /* The next lines print the nodes in the graph together with the
2225 complex constraints attached to them. */
2226 for (i = 1; i < graph->size; i++)
2227 {
2228 if (i == FIRST_REF_NODE)
2229 continue;
2230 if (si->node_mapping[i] != i)
2231 continue;
2232 if (i < FIRST_REF_NODE)
2233 fprintf (file, "\"%s\"", get_varinfo (i)->name);
2234 else
2235 fprintf (file, "\"*%s\"", get_varinfo (i - FIRST_REF_NODE)->name);
2236 if (graph->points_to[i]
2237 && !bitmap_empty_p (graph->points_to[i]))
2238 {
2239 if (i < FIRST_REF_NODE)
2240 fprintf (file, "[label=\"%s = {", get_varinfo (i)->name);
2241 else
2242 fprintf (file, "[label=\"*%s = {",
2243 get_varinfo (i - FIRST_REF_NODE)->name);
2244 unsigned j;
2245 bitmap_iterator bi;
2246 EXECUTE_IF_SET_IN_BITMAP (graph->points_to[i], 0, j, bi)
2247 fprintf (file, " %d", j);
2248 fprintf (file, " }\"]");
2249 }
2250 fprintf (file, ";\n");
2251 }
2252
2253 /* Go over the edges. */
2254 fprintf (file, "\n // Edges in the constraint graph:\n");
2255 for (i = 1; i < graph->size; i++)
2256 {
2257 unsigned j;
2258 bitmap_iterator bi;
2259 if (si->node_mapping[i] != i)
2260 continue;
2261 EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[i], 0, j, bi)
2262 {
2263 unsigned from = si->node_mapping[j];
2264 if (from < FIRST_REF_NODE)
2265 fprintf (file, "\"%s\"", get_varinfo (from)->name);
2266 else
2267 fprintf (file, "\"*%s\"", get_varinfo (from - FIRST_REF_NODE)->name);
2268 fprintf (file, " -> ");
2269 if (i < FIRST_REF_NODE)
2270 fprintf (file, "\"%s\"", get_varinfo (i)->name);
2271 else
2272 fprintf (file, "\"*%s\"", get_varinfo (i - FIRST_REF_NODE)->name);
2273 fprintf (file, ";\n");
2274 }
2275 }
2276
2277 /* Prints the tail of the dot file. */
2278 fprintf (file, "}\n");
2279}
2280
2281/* Perform offline variable substitution, discovering equivalence
2282 classes, and eliminating non-pointer variables. */
2283
2284static struct scc_info *
2285perform_var_substitution (constraint_graph_t graph)
2286{
2287 unsigned int i;
2288 unsigned int size = graph->size;
2289 scc_info *si = new scc_info (size);
2290
2291 bitmap_obstack_initialize (&iteration_obstack);
2292 pointer_equiv_class_table = new hash_table<equiv_class_hasher> (511);
2293 location_equiv_class_table
2294 = new hash_table<equiv_class_hasher> (511);
2295 pointer_equiv_class = 1;
2296 location_equiv_class = 1;
2297
2298 /* Condense the nodes, which means to find SCC's, count incoming
2299 predecessors, and unite nodes in SCC's. */
2300 for (i = 1; i < FIRST_REF_NODE; i++)
2301 if (!bitmap_bit_p (si->visited, si->node_mapping[i]))
2302 condense_visit (graph, si, si->node_mapping[i]);
2303
2304 if (dump_file && (dump_flags & TDF_GRAPH))
2305 {
2306 fprintf (dump_file, "\n\n// The constraint graph before var-substitution "
2307 "in dot format:\n");
2308 dump_pred_graph (si, dump_file);
2309 fprintf (dump_file, "\n\n");
2310 }
2311
2312 bitmap_clear (si->visited);
2313 /* Actually the label the nodes for pointer equivalences */
2314 for (i = 1; i < FIRST_REF_NODE; i++)
2315 if (!bitmap_bit_p (si->visited, si->node_mapping[i]))
2316 label_visit (graph, si, si->node_mapping[i]);
2317
2318 /* Calculate location equivalence labels. */
2319 for (i = 1; i < FIRST_REF_NODE; i++)
2320 {
2321 bitmap pointed_by;
2322 bitmap_iterator bi;
2323 unsigned int j;
2324
2325 if (!graph->pointed_by[i])
2326 continue;
2327 pointed_by = BITMAP_ALLOC (&iteration_obstack);
2328
2329 /* Translate the pointed-by mapping for pointer equivalence
2330 labels. */
2331 EXECUTE_IF_SET_IN_BITMAP (graph->pointed_by[i], 0, j, bi)
2332 {
2333 bitmap_set_bit (pointed_by,
2334 graph->pointer_label[si->node_mapping[j]]);
2335 }
2336 /* The original pointed_by is now dead. */
2337 BITMAP_FREE (graph->pointed_by[i]);
2338
2339 /* Look up the location equivalence label if one exists, or make
2340 one otherwise. */
2341 equiv_class_label_t ecl;
2342 ecl = equiv_class_lookup_or_add (location_equiv_class_table, pointed_by);
2343 if (ecl->equivalence_class == 0)
2344 ecl->equivalence_class = location_equiv_class++;
2345 else
2346 {
2347 if (dump_file && (dump_flags & TDF_DETAILS))
2348 fprintf (dump_file, "Found location equivalence for node %s\n",
2349 get_varinfo (i)->name);
2350 BITMAP_FREE (pointed_by);
2351 }
2352 graph->loc_label[i] = ecl->equivalence_class;
2353
2354 }
2355
2356 if (dump_file && (dump_flags & TDF_DETAILS))
2357 for (i = 1; i < FIRST_REF_NODE; i++)
2358 {
2359 unsigned j = si->node_mapping[i];
2360 if (j != i)
2361 {
2362 fprintf (dump_file, "%s node id %d ",
2363 bitmap_bit_p (graph->direct_nodes, i)
2364 ? "Direct" : "Indirect", i);
2365 if (i < FIRST_REF_NODE)
2366 fprintf (dump_file, "\"%s\"", get_varinfo (i)->name);
2367 else
2368 fprintf (dump_file, "\"*%s\"",
2369 get_varinfo (i - FIRST_REF_NODE)->name);
2370 fprintf (dump_file, " mapped to SCC leader node id %d ", j);
2371 if (j < FIRST_REF_NODE)
2372 fprintf (dump_file, "\"%s\"\n", get_varinfo (j)->name);
2373 else
2374 fprintf (dump_file, "\"*%s\"\n",
2375 get_varinfo (j - FIRST_REF_NODE)->name);
2376 }
2377 else
2378 {
2379 fprintf (dump_file,
2380 "Equivalence classes for %s node id %d ",
2381 bitmap_bit_p (graph->direct_nodes, i)
2382 ? "direct" : "indirect", i);
2383 if (i < FIRST_REF_NODE)
2384 fprintf (dump_file, "\"%s\"", get_varinfo (i)->name);
2385 else
2386 fprintf (dump_file, "\"*%s\"",
2387 get_varinfo (i - FIRST_REF_NODE)->name);
2388 fprintf (dump_file,
2389 ": pointer %d, location %d\n",
2390 graph->pointer_label[i], graph->loc_label[i]);
2391 }
2392 }
2393
2394 /* Quickly eliminate our non-pointer variables. */
2395
2396 for (i = 1; i < FIRST_REF_NODE; i++)
2397 {
2398 unsigned int node = si->node_mapping[i];
2399
2400 if (graph->pointer_label[node] == 0)
2401 {
2402 if (dump_file && (dump_flags & TDF_DETAILS))
2403 fprintf (dump_file,
2404 "%s is a non-pointer variable, eliminating edges.\n",
2405 get_varinfo (node)->name);
2406 stats.nonpointer_vars++;
2407 clear_edges_for_node (graph, node);
2408 }
2409 }
2410
2411 return si;
2412}
2413
2414/* Free information that was only necessary for variable
2415 substitution. */
2416
2417static void
2418free_var_substitution_info (struct scc_info *si)
2419{
2420 delete si;
2421 free (graph->pointer_label);
2422 free (graph->loc_label);
2423 free (graph->pointed_by);
2424 free (graph->points_to);
2425 free (graph->eq_rep);
2426 sbitmap_free (graph->direct_nodes);
2427 delete pointer_equiv_class_table;
2428 pointer_equiv_class_table = NULL;
2429 delete location_equiv_class_table;
2430 location_equiv_class_table = NULL;
2431 bitmap_obstack_release (&iteration_obstack);
2432}
2433
2434/* Return an existing node that is equivalent to NODE, which has
2435 equivalence class LABEL, if one exists. Return NODE otherwise. */
2436
2437static unsigned int
2438find_equivalent_node (constraint_graph_t graph,
2439 unsigned int node, unsigned int label)
2440{
2441 /* If the address version of this variable is unused, we can
2442 substitute it for anything else with the same label.
2443 Otherwise, we know the pointers are equivalent, but not the
2444 locations, and we can unite them later. */
2445
2446 if (!bitmap_bit_p (graph->address_taken, node))
2447 {
2448 gcc_checking_assert (label < graph->size);
2449
2450 if (graph->eq_rep[label] != -1)
2451 {
2452 /* Unify the two variables since we know they are equivalent. */
2453 if (unite (graph->eq_rep[label], node))
2454 unify_nodes (graph, graph->eq_rep[label], node, false);
2455 return graph->eq_rep[label];
2456 }
2457 else
2458 {
2459 graph->eq_rep[label] = node;
2460 graph->pe_rep[label] = node;
2461 }
2462 }
2463 else
2464 {
2465 gcc_checking_assert (label < graph->size);
2466 graph->pe[node] = label;
2467 if (graph->pe_rep[label] == -1)
2468 graph->pe_rep[label] = node;
2469 }
2470
2471 return node;
2472}
2473
2474/* Unite pointer equivalent but not location equivalent nodes in
2475 GRAPH. This may only be performed once variable substitution is
2476 finished. */
2477
2478static void
2479unite_pointer_equivalences (constraint_graph_t graph)
2480{
2481 unsigned int i;
2482
2483 /* Go through the pointer equivalences and unite them to their
2484 representative, if they aren't already. */
2485 for (i = 1; i < FIRST_REF_NODE; i++)
2486 {
2487 unsigned int label = graph->pe[i];
2488 if (label)
2489 {
2490 int label_rep = graph->pe_rep[label];
2491
2492 if (label_rep == -1)
2493 continue;
2494
2495 label_rep = find (label_rep);
2496 if (label_rep >= 0 && unite (label_rep, find (i)))
2497 unify_nodes (graph, label_rep, i, false);
2498 }
2499 }
2500}
2501
2502/* Move complex constraints to the GRAPH nodes they belong to. */
2503
2504static void
2505move_complex_constraints (constraint_graph_t graph)
2506{
2507 int i;
2508 constraint_t c;
2509
2510 FOR_EACH_VEC_ELT (constraints, i, c)
2511 {
2512 if (c)
2513 {
2514 struct constraint_expr lhs = c->lhs;
2515 struct constraint_expr rhs = c->rhs;
2516
2517 if (lhs.type == DEREF)
2518 {
2519 insert_into_complex (graph, lhs.var, c);
2520 }
2521 else if (rhs.type == DEREF)
2522 {
2523 if (!(get_varinfo (lhs.var)->is_special_var))
2524 insert_into_complex (graph, rhs.var, c);
2525 }
2526 else if (rhs.type != ADDRESSOF && lhs.var > anything_id
2527 && (lhs.offset != 0 || rhs.offset != 0))
2528 {
2529 insert_into_complex (graph, rhs.var, c);
2530 }
2531 }
2532 }
2533}
2534
2535
2536/* Optimize and rewrite complex constraints while performing
2537 collapsing of equivalent nodes. SI is the SCC_INFO that is the
2538 result of perform_variable_substitution. */
2539
2540static void
2541rewrite_constraints (constraint_graph_t graph,
2542 struct scc_info *si)
2543{
2544 int i;
2545 constraint_t c;
2546
2547 if (flag_checking)
2548 {
2549 for (unsigned int j = 0; j < graph->size; j++)
2550 gcc_assert (find (j) == j);
2551 }
2552
2553 FOR_EACH_VEC_ELT (constraints, i, c)
2554 {
2555 struct constraint_expr lhs = c->lhs;
2556 struct constraint_expr rhs = c->rhs;
2557 unsigned int lhsvar = find (lhs.var);
2558 unsigned int rhsvar = find (rhs.var);
2559 unsigned int lhsnode, rhsnode;
2560 unsigned int lhslabel, rhslabel;
2561
2562 lhsnode = si->node_mapping[lhsvar];
2563 rhsnode = si->node_mapping[rhsvar];
2564 lhslabel = graph->pointer_label[lhsnode];
2565 rhslabel = graph->pointer_label[rhsnode];
2566
2567 /* See if it is really a non-pointer variable, and if so, ignore
2568 the constraint. */
2569 if (lhslabel == 0)
2570 {
2571 if (dump_file && (dump_flags & TDF_DETAILS))
2572 {
2573
2574 fprintf (dump_file, "%s is a non-pointer variable, "
2575 "ignoring constraint:",
2576 get_varinfo (lhs.var)->name);
2577 dump_constraint (dump_file, c);
2578 fprintf (dump_file, "\n");
2579 }
2580 constraints[i] = NULL;
2581 continue;
2582 }
2583
2584 if (rhslabel == 0)
2585 {
2586 if (dump_file && (dump_flags & TDF_DETAILS))
2587 {
2588
2589 fprintf (dump_file, "%s is a non-pointer variable, "
2590 "ignoring constraint:",
2591 get_varinfo (rhs.var)->name);
2592 dump_constraint (dump_file, c);
2593 fprintf (dump_file, "\n");
2594 }
2595 constraints[i] = NULL;
2596 continue;
2597 }
2598
2599 lhsvar = find_equivalent_node (graph, lhsvar, lhslabel);
2600 rhsvar = find_equivalent_node (graph, rhsvar, rhslabel);
2601 c->lhs.var = lhsvar;
2602 c->rhs.var = rhsvar;
2603 }
2604}
2605
2606/* Eliminate indirect cycles involving NODE. Return true if NODE was
2607 part of an SCC, false otherwise. */
2608
2609static bool
2610eliminate_indirect_cycles (unsigned int node)
2611{
2612 if (graph->indirect_cycles[node] != -1
2613 && !bitmap_empty_p (get_varinfo (node)->solution))
2614 {
2615 unsigned int i;
2616 auto_vec<unsigned> queue;
2617 int queuepos;
2618 unsigned int to = find (graph->indirect_cycles[node]);
2619 bitmap_iterator bi;
2620
2621 /* We can't touch the solution set and call unify_nodes
2622 at the same time, because unify_nodes is going to do
2623 bitmap unions into it. */
2624
2625 EXECUTE_IF_SET_IN_BITMAP (get_varinfo (node)->solution, 0, i, bi)
2626 {
2627 if (find (i) == i && i != to)
2628 {
2629 if (unite (to, i))
2630 queue.safe_push (i);
2631 }
2632 }
2633
2634 for (queuepos = 0;
2635 queue.iterate (queuepos, &i);
2636 queuepos++)
2637 {
2638 unify_nodes (graph, to, i, true);
2639 }
2640 return true;
2641 }
2642 return false;
2643}
2644
2645/* Solve the constraint graph GRAPH using our worklist solver.
2646 This is based on the PW* family of solvers from the "Efficient Field
2647 Sensitive Pointer Analysis for C" paper.
2648 It works by iterating over all the graph nodes, processing the complex
2649 constraints and propagating the copy constraints, until everything stops
2650 changed. This corresponds to steps 6-8 in the solving list given above. */
2651
2652static void
2653solve_graph (constraint_graph_t graph)
2654{
2655 unsigned int size = graph->size;
2656 unsigned int i;
2657 bitmap pts;
2658
2659 changed = BITMAP_ALLOC (NULL);
2660
2661 /* Mark all initial non-collapsed nodes as changed. */
2662 for (i = 1; i < size; i++)
2663 {
2664 varinfo_t ivi = get_varinfo (i);
2665 if (find (i) == i && !bitmap_empty_p (ivi->solution)
2666 && ((graph->succs[i] && !bitmap_empty_p (graph->succs[i]))
2667 || graph->complex[i].length () > 0))
2668 bitmap_set_bit (changed, i);
2669 }
2670
2671 /* Allocate a bitmap to be used to store the changed bits. */
2672 pts = BITMAP_ALLOC (&pta_obstack);
2673
2674 while (!bitmap_empty_p (changed))
2675 {
2676 unsigned int i;
2677 struct topo_info *ti = init_topo_info ();
2678 stats.iterations++;
2679
2680 bitmap_obstack_initialize (&iteration_obstack);
2681
2682 compute_topo_order (graph, ti);
2683
2684 while (ti->topo_order.length () != 0)
2685 {
2686
2687 i = ti->topo_order.pop ();
2688
2689 /* If this variable is not a representative, skip it. */
2690 if (find (i) != i)
2691 continue;
2692
2693 /* In certain indirect cycle cases, we may merge this
2694 variable to another. */
2695 if (eliminate_indirect_cycles (i) && find (i) != i)
2696 continue;
2697
2698 /* If the node has changed, we need to process the
2699 complex constraints and outgoing edges again. */
2700 if (bitmap_clear_bit (changed, i))
2701 {
2702 unsigned int j;
2703 constraint_t c;
2704 bitmap solution;
2705 vec<constraint_t> complex = graph->complex[i];
2706 varinfo_t vi = get_varinfo (i);
2707 bool solution_empty;
2708
2709 /* Compute the changed set of solution bits. If anything
2710 is in the solution just propagate that. */
2711 if (bitmap_bit_p (vi->solution, anything_id))
2712 {
2713 /* If anything is also in the old solution there is
2714 nothing to do.
2715 ??? But we shouldn't ended up with "changed" set ... */
2716 if (vi->oldsolution
2717 && bitmap_bit_p (vi->oldsolution, anything_id))
2718 continue;
2719 bitmap_copy (pts, get_varinfo (find (anything_id))->solution);
2720 }
2721 else if (vi->oldsolution)
2722 bitmap_and_compl (pts, vi->solution, vi->oldsolution);
2723 else
2724 bitmap_copy (pts, vi->solution);
2725
2726 if (bitmap_empty_p (pts))
2727 continue;
2728
2729 if (vi->oldsolution)
2730 bitmap_ior_into (vi->oldsolution, pts);
2731 else
2732 {
2733 vi->oldsolution = BITMAP_ALLOC (&oldpta_obstack);
2734 bitmap_copy (vi->oldsolution, pts);
2735 }
2736
2737 solution = vi->solution;
2738 solution_empty = bitmap_empty_p (solution);
2739
2740 /* Process the complex constraints */
2741 bitmap expanded_pts = NULL;
2742 FOR_EACH_VEC_ELT (complex, j, c)
2743 {
2744 /* XXX: This is going to unsort the constraints in
2745 some cases, which will occasionally add duplicate
2746 constraints during unification. This does not
2747 affect correctness. */
2748 c->lhs.var = find (c->lhs.var);
2749 c->rhs.var = find (c->rhs.var);
2750
2751 /* The only complex constraint that can change our
2752 solution to non-empty, given an empty solution,
2753 is a constraint where the lhs side is receiving
2754 some set from elsewhere. */
2755 if (!solution_empty || c->lhs.type != DEREF)
2756 do_complex_constraint (graph, c, pts, &expanded_pts);
2757 }
2758 BITMAP_FREE (expanded_pts);
2759
2760 solution_empty = bitmap_empty_p (solution);
2761
2762 if (!solution_empty)
2763 {
2764 bitmap_iterator bi;
2765 unsigned eff_escaped_id = find (escaped_id);
2766
2767 /* Propagate solution to all successors. */
2768 unsigned to_remove = ~0U;
2769 EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i],
2770 0, j, bi)
2771 {
2772 if (to_remove != ~0U)
2773 {
2774 bitmap_clear_bit (graph->succs[i], to_remove);
2775 to_remove = ~0U;
2776 }
2777 unsigned int to = find (j);
2778 if (to != j)
2779 {
2780 /* Update the succ graph, avoiding duplicate
2781 work. */
2782 to_remove = j;
2783 if (! bitmap_set_bit (graph->succs[i], to))
2784 continue;
2785 /* We eventually end up processing 'to' twice
2786 as it is undefined whether bitmap iteration
2787 iterates over bits set during iteration.
2788 Play safe instead of doing tricks. */
2789 }
2790 /* Don't try to propagate to ourselves. */
2791 if (to == i)
2792 continue;
2793
2794 bitmap tmp = get_varinfo (to)->solution;
2795 bool flag = false;
2796
2797 /* If we propagate from ESCAPED use ESCAPED as
2798 placeholder. */
2799 if (i == eff_escaped_id)
2800 flag = bitmap_set_bit (tmp, escaped_id);
2801 else
2802 flag = bitmap_ior_into (tmp, pts);
2803
2804 if (flag)
2805 bitmap_set_bit (changed, to);
2806 }
2807 if (to_remove != ~0U)
2808 bitmap_clear_bit (graph->succs[i], to_remove);
2809 }
2810 }
2811 }
2812 free_topo_info (ti);
2813 bitmap_obstack_release (&iteration_obstack);
2814 }
2815
2816 BITMAP_FREE (pts);
2817 BITMAP_FREE (changed);
2818 bitmap_obstack_release (&oldpta_obstack);
2819}
2820
2821/* Map from trees to variable infos. */
2822static hash_map<tree, varinfo_t> *vi_for_tree;
2823
2824
2825/* Insert ID as the variable id for tree T in the vi_for_tree map. */
2826
2827static void
2828insert_vi_for_tree (tree t, varinfo_t vi)
2829{
2830 gcc_assert (vi);
2831 gcc_assert (!vi_for_tree->put (t, vi));
2832}
2833
2834/* Find the variable info for tree T in VI_FOR_TREE. If T does not
2835 exist in the map, return NULL, otherwise, return the varinfo we found. */
2836
2837static varinfo_t
2838lookup_vi_for_tree (tree t)
2839{
2840 varinfo_t *slot = vi_for_tree->get (t);
2841 if (slot == NULL)
2842 return NULL;
2843
2844 return *slot;
2845}
2846
2847/* Return a printable name for DECL */
2848
2849static const char *
2850alias_get_name (tree decl)
2851{
2852 const char *res = "NULL";
2853 if (dump_file)
2854 {
2855 char *temp = NULL;
2856 if (TREE_CODE (decl) == SSA_NAME)
2857 {
2858 res = get_name (decl);
2859 temp = xasprintf ("%s_%u", res ? res : "", SSA_NAME_VERSION (decl));
2860 }
2861 else if (HAS_DECL_ASSEMBLER_NAME_P (decl)
2862 && DECL_ASSEMBLER_NAME_SET_P (decl))
2863 res = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME_RAW (decl));
2864 else if (DECL_P (decl))
2865 {
2866 res = get_name (decl);
2867 if (!res)
2868 temp = xasprintf ("D.%u", DECL_UID (decl));
2869 }
2870
2871 if (temp)
2872 {
2873 res = ggc_strdup (temp);
2874 free (temp);
2875 }
2876 }
2877
2878 return res;
2879}
2880
2881/* Find the variable id for tree T in the map.
2882 If T doesn't exist in the map, create an entry for it and return it. */
2883
2884static varinfo_t
2885get_vi_for_tree (tree t)
2886{
2887 varinfo_t *slot = vi_for_tree->get (t);
2888 if (slot == NULL)
2889 {
2890 unsigned int id = create_variable_info_for (t, alias_get_name (t), false);
2891 return get_varinfo (id);
2892 }
2893
2894 return *slot;
2895}
2896
2897/* Get a scalar constraint expression for a new temporary variable. */
2898
2899static struct constraint_expr
2900new_scalar_tmp_constraint_exp (const char *name, bool add_id)
2901{
2902 struct constraint_expr tmp;
2903 varinfo_t vi;
2904
2905 vi = new_var_info (NULL_TREE, name, add_id);
2906 vi->offset = 0;
2907 vi->size = -1;
2908 vi->fullsize = -1;
2909 vi->is_full_var = 1;
2910 vi->is_reg_var = 1;
2911
2912 tmp.var = vi->id;
2913 tmp.type = SCALAR;
2914 tmp.offset = 0;
2915
2916 return tmp;
2917}
2918
2919/* Get a constraint expression vector from an SSA_VAR_P node.
2920 If address_p is true, the result will be taken its address of. */
2921
2922static void
2923get_constraint_for_ssa_var (tree t, vec<ce_s> *results, bool address_p)
2924{
2925 struct constraint_expr cexpr;
2926 varinfo_t vi;
2927
2928 /* We allow FUNCTION_DECLs here even though it doesn't make much sense. */
2929 gcc_assert (TREE_CODE (t) == SSA_NAME || DECL_P (t));
2930
2931 /* For parameters, get at the points-to set for the actual parm
2932 decl. */
2933 if (TREE_CODE (t) == SSA_NAME
2934 && SSA_NAME_IS_DEFAULT_DEF (t)
2935 && (TREE_CODE (SSA_NAME_VAR (t)) == PARM_DECL
2936 || TREE_CODE (SSA_NAME_VAR (t)) == RESULT_DECL))
2937 {
2938 get_constraint_for_ssa_var (SSA_NAME_VAR (t), results, address_p);
2939 return;
2940 }
2941
2942 /* For global variables resort to the alias target. */
2943 if (VAR_P (t) && (TREE_STATIC (t) || DECL_EXTERNAL (t)))
2944 {
2945 varpool_node *node = varpool_node::get (t);
2946 if (node && node->alias && node->analyzed)
2947 {
2948 node = node->ultimate_alias_target ();
2949 /* Canonicalize the PT uid of all aliases to the ultimate target.
2950 ??? Hopefully the set of aliases can't change in a way that
2951 changes the ultimate alias target. */
2952 gcc_assert ((! DECL_PT_UID_SET_P (node->decl)
2953 || DECL_PT_UID (node->decl) == DECL_UID (node->decl))
2954 && (! DECL_PT_UID_SET_P (t)
2955 || DECL_PT_UID (t) == DECL_UID (node->decl)));
2956 DECL_PT_UID (t) = DECL_UID (node->decl);
2957 t = node->decl;
2958 }
2959
2960 /* If this is decl may bind to NULL note that. */
2961 if (address_p
2962 && (! node || ! node->nonzero_address ()))
2963 {
2964 cexpr.var = nothing_id;
2965 cexpr.type = SCALAR;
2966 cexpr.offset = 0;
2967 results->safe_push (cexpr);
2968 }
2969 }
2970
2971 vi = get_vi_for_tree (t);
2972 cexpr.var = vi->id;
2973 cexpr.type = SCALAR;
2974 cexpr.offset = 0;
2975
2976 /* If we are not taking the address of the constraint expr, add all
2977 sub-fiels of the variable as well. */
2978 if (!address_p
2979 && !vi->is_full_var)
2980 {
2981 for (; vi; vi = vi_next (vi))
2982 {
2983 cexpr.var = vi->id;
2984 results->safe_push (cexpr);
2985 }
2986 return;
2987 }
2988
2989 results->safe_push (cexpr);
2990}
2991
2992/* Process constraint T, performing various simplifications and then
2993 adding it to our list of overall constraints. */
2994
2995static void
2996process_constraint (constraint_t t)
2997{
2998 struct constraint_expr rhs = t->rhs;
2999 struct constraint_expr lhs = t->lhs;
3000
3001 gcc_assert (rhs.var < varmap.length ());
3002 gcc_assert (lhs.var < varmap.length ());
3003
3004 /* If we didn't get any useful constraint from the lhs we get
3005 &ANYTHING as fallback from get_constraint_for. Deal with
3006 it here by turning it into *ANYTHING. */
3007 if (lhs.type == ADDRESSOF
3008 && lhs.var == anything_id)
3009 lhs.type = DEREF;
3010
3011 /* ADDRESSOF on the lhs is invalid. */
3012 gcc_assert (lhs.type != ADDRESSOF);
3013
3014 /* We shouldn't add constraints from things that cannot have pointers.
3015 It's not completely trivial to avoid in the callers, so do it here. */
3016 if (rhs.type != ADDRESSOF
3017 && !get_varinfo (rhs.var)->may_have_pointers)
3018 return;
3019
3020 /* Likewise adding to the solution of a non-pointer var isn't useful. */
3021 if (!get_varinfo (lhs.var)->may_have_pointers)
3022 return;
3023
3024 /* This can happen in our IR with things like n->a = *p */
3025 if (rhs.type == DEREF && lhs.type == DEREF && rhs.var != anything_id)
3026 {
3027 /* Split into tmp = *rhs, *lhs = tmp */
3028 struct constraint_expr tmplhs;
3029 tmplhs = new_scalar_tmp_constraint_exp ("doubledereftmp", true);
3030 process_constraint (new_constraint (tmplhs, rhs));
3031 process_constraint (new_constraint (lhs, tmplhs));
3032 }
3033 else if ((rhs.type != SCALAR || rhs.offset != 0) && lhs.type == DEREF)
3034 {
3035 /* Split into tmp = &rhs, *lhs = tmp */
3036 struct constraint_expr tmplhs;
3037 tmplhs = new_scalar_tmp_constraint_exp ("derefaddrtmp", true);
3038 process_constraint (new_constraint (tmplhs, rhs));
3039 process_constraint (new_constraint (lhs, tmplhs));
3040 }
3041 else
3042 {
3043 gcc_assert (rhs.type != ADDRESSOF || rhs.offset == 0);
3044 constraints.safe_push (t);
3045 }
3046}
3047
3048
3049/* Return the position, in bits, of FIELD_DECL from the beginning of its
3050 structure. */
3051
3052static HOST_WIDE_INT
3053bitpos_of_field (const tree fdecl)
3054{
3055 if (!tree_fits_shwi_p (DECL_FIELD_OFFSET (fdecl))
3056 || !tree_fits_shwi_p (DECL_FIELD_BIT_OFFSET (fdecl)))
3057 return -1;
3058
3059 return (tree_to_shwi (DECL_FIELD_OFFSET (fdecl)) * BITS_PER_UNIT
3060 + tree_to_shwi (DECL_FIELD_BIT_OFFSET (fdecl)));
3061}
3062
3063
3064/* Get constraint expressions for offsetting PTR by OFFSET. Stores the
3065 resulting constraint expressions in *RESULTS. */
3066
3067static void
3068get_constraint_for_ptr_offset (tree ptr, tree offset,
3069 vec<ce_s> *results)
3070{
3071 struct constraint_expr c;
3072 unsigned int j, n;
3073 HOST_WIDE_INT rhsoffset;
3074
3075 /* If we do not do field-sensitive PTA adding offsets to pointers
3076 does not change the points-to solution. */
3077 if (!use_field_sensitive)
3078 {
3079 get_constraint_for_rhs (ptr, results);
3080 return;
3081 }
3082
3083 /* If the offset is not a non-negative integer constant that fits
3084 in a HOST_WIDE_INT, we have to fall back to a conservative
3085 solution which includes all sub-fields of all pointed-to
3086 variables of ptr. */
3087 if (offset == NULL_TREE
3088 || TREE_CODE (offset) != INTEGER_CST)
3089 rhsoffset = UNKNOWN_OFFSET;
3090 else
3091 {
3092 /* Sign-extend the offset. */
3093 offset_int soffset = offset_int::from (wi::to_wide (offset), SIGNED);
3094 if (!wi::fits_shwi_p (soffset))
3095 rhsoffset = UNKNOWN_OFFSET;
3096 else
3097 {
3098 /* Make sure the bit-offset also fits. */
3099 HOST_WIDE_INT rhsunitoffset = soffset.to_shwi ();
3100 rhsoffset = rhsunitoffset * (unsigned HOST_WIDE_INT) BITS_PER_UNIT;
3101 if (rhsunitoffset != rhsoffset / BITS_PER_UNIT)
3102 rhsoffset = UNKNOWN_OFFSET;
3103 }
3104 }
3105
3106 get_constraint_for_rhs (ptr, results);
3107 if (rhsoffset == 0)
3108 return;
3109
3110 /* As we are eventually appending to the solution do not use
3111 vec::iterate here. */
3112 n = results->length ();
3113 for (j = 0; j < n; j++)
3114 {
3115 varinfo_t curr;
3116 c = (*results)[j];
3117 curr = get_varinfo (c.var);
3118
3119 if (c.type == ADDRESSOF
3120 /* If this varinfo represents a full variable just use it. */
3121 && curr->is_full_var)
3122 ;
3123 else if (c.type == ADDRESSOF
3124 /* If we do not know the offset add all subfields. */
3125 && rhsoffset == UNKNOWN_OFFSET)
3126 {
3127 varinfo_t temp = get_varinfo (curr->head);
3128 do
3129 {
3130 struct constraint_expr c2;
3131 c2.var = temp->id;
3132 c2.type = ADDRESSOF;
3133 c2.offset = 0;
3134 if (c2.var != c.var)
3135 results->safe_push (c2);
3136 temp = vi_next (temp);
3137 }
3138 while (temp);
3139 }
3140 else if (c.type == ADDRESSOF)
3141 {
3142 varinfo_t temp;
3143 unsigned HOST_WIDE_INT offset = curr->offset + rhsoffset;
3144
3145 /* If curr->offset + rhsoffset is less than zero adjust it. */
3146 if (rhsoffset < 0
3147 && curr->offset < offset)
3148 offset = 0;
3149
3150 /* We have to include all fields that overlap the current
3151 field shifted by rhsoffset. And we include at least
3152 the last or the first field of the variable to represent
3153 reachability of off-bound addresses, in particular &object + 1,
3154 conservatively correct. */
3155 temp = first_or_preceding_vi_for_offset (curr, offset);
3156 c.var = temp->id;
3157 c.offset = 0;
3158 temp = vi_next (temp);
3159 while (temp
3160 && temp->offset < offset + curr->size)
3161 {
3162 struct constraint_expr c2;
3163 c2.var = temp->id;
3164 c2.type = ADDRESSOF;
3165 c2.offset = 0;
3166 results->safe_push (c2);
3167 temp = vi_next (temp);
3168 }
3169 }
3170 else if (c.type == SCALAR)
3171 {
3172 gcc_assert (c.offset == 0);
3173 c.offset = rhsoffset;
3174 }
3175 else
3176 /* We shouldn't get any DEREFs here. */
3177 gcc_unreachable ();
3178
3179 (*results)[j] = c;
3180 }
3181}
3182
3183
3184/* Given a COMPONENT_REF T, return the constraint_expr vector for it.
3185 If address_p is true the result will be taken its address of.
3186 If lhs_p is true then the constraint expression is assumed to be used
3187 as the lhs. */
3188
3189static void
3190get_constraint_for_component_ref (tree t, vec<ce_s> *results,
3191 bool address_p, bool lhs_p)
3192{
3193 tree orig_t = t;
3194 HOST_WIDE_INT bitsize = -1;
3195 HOST_WIDE_INT bitmaxsize = -1;
3196 HOST_WIDE_INT bitpos;
3197 bool reverse;
3198 tree forzero;
3199
3200 /* Some people like to do cute things like take the address of
3201 &0->a.b */
3202 forzero = t;
3203 while (handled_component_p (forzero)
3204 || INDIRECT_REF_P (forzero)
3205 || TREE_CODE (forzero) == MEM_REF)
3206 forzero = TREE_OPERAND (forzero, 0);
3207
3208 if (CONSTANT_CLASS_P (forzero) && integer_zerop (forzero))
3209 {
3210 struct constraint_expr temp;
3211
3212 temp.offset = 0;
3213 temp.var = integer_id;
3214 temp.type = SCALAR;
3215 results->safe_push (temp);
3216 return;
3217 }
3218
3219 t = get_ref_base_and_extent (t, &bitpos, &bitsize, &bitmaxsize, &reverse);
3220
3221 /* We can end up here for component references on a
3222 VIEW_CONVERT_EXPR <>(&foobar) or things like a
3223 BIT_FIELD_REF <&MEM[(void *)&b + 4B], ...>. So for
3224 symbolic constants simply give up. */
3225 if (TREE_CODE (t) == ADDR_EXPR)
3226 {
3227 constraint_expr result;
3228 result.type = SCALAR;
3229 result.var = anything_id;
3230 result.offset = 0;
3231 results->safe_push (result);
3232 return;
3233 }
3234
3235 /* Pretend to take the address of the base, we'll take care of
3236 adding the required subset of sub-fields below. */
3237 get_constraint_for_1 (t, results, true, lhs_p);
3238 /* Strip off nothing_id. */
3239 if (results->length () == 2)
3240 {
3241 gcc_assert ((*results)[0].var == nothing_id);
3242 results->unordered_remove (0);
3243 }
3244 gcc_assert (results->length () == 1);
3245 struct constraint_expr &result = results->last ();
3246
3247 if (result.type == SCALAR
3248 && get_varinfo (result.var)->is_full_var)
3249 /* For single-field vars do not bother about the offset. */
3250 result.offset = 0;
3251 else if (result.type == SCALAR)
3252 {
3253 /* In languages like C, you can access one past the end of an
3254 array. You aren't allowed to dereference it, so we can
3255 ignore this constraint. When we handle pointer subtraction,
3256 we may have to do something cute here. */
3257
3258 if ((unsigned HOST_WIDE_INT)bitpos < get_varinfo (result.var)->fullsize
3259 && bitmaxsize != 0)
3260 {
3261 /* It's also not true that the constraint will actually start at the
3262 right offset, it may start in some padding. We only care about
3263 setting the constraint to the first actual field it touches, so
3264 walk to find it. */
3265 struct constraint_expr cexpr = result;
3266 varinfo_t curr;
3267 results->pop ();
3268 cexpr.offset = 0;
3269 for (curr = get_varinfo (cexpr.var); curr; curr = vi_next (curr))
3270 {
3271 if (ranges_overlap_p (curr->offset, curr->size,
3272 bitpos, bitmaxsize))
3273 {
3274 cexpr.var = curr->id;
3275 results->safe_push (cexpr);
3276 if (address_p)
3277 break;
3278 }
3279 }
3280 /* If we are going to take the address of this field then
3281 to be able to compute reachability correctly add at least
3282 the last field of the variable. */
3283 if (address_p && results->length () == 0)
3284 {
3285 curr = get_varinfo (cexpr.var);
3286 while (curr->next != 0)
3287 curr = vi_next (curr);
3288 cexpr.var = curr->id;
3289 results->safe_push (cexpr);
3290 }
3291 else if (results->length () == 0)
3292 /* Assert that we found *some* field there. The user couldn't be
3293 accessing *only* padding. */
3294 /* Still the user could access one past the end of an array
3295 embedded in a struct resulting in accessing *only* padding. */
3296 /* Or accessing only padding via type-punning to a type
3297 that has a filed just in padding space. */
3298 {
3299 cexpr.type = SCALAR;
3300 cexpr.var = anything_id;
3301 cexpr.offset = 0;
3302 results->safe_push (cexpr);
3303 }
3304 }
3305 else if (bitmaxsize == 0)
3306 {
3307 if (dump_file && (dump_flags & TDF_DETAILS))
3308 fprintf (dump_file, "Access to zero-sized part of variable, "
3309 "ignoring\n");
3310 }
3311 else
3312 if (dump_file && (dump_flags & TDF_DETAILS))
3313 fprintf (dump_file, "Access to past the end of variable, ignoring\n");
3314 }
3315 else if (result.type == DEREF)
3316 {
3317 /* If we do not know exactly where the access goes say so. Note
3318 that only for non-structure accesses we know that we access
3319 at most one subfiled of any variable. */
3320 if (bitpos == -1
3321 || bitsize != bitmaxsize
3322 || AGGREGATE_TYPE_P (TREE_TYPE (orig_t))
3323 || result.offset == UNKNOWN_OFFSET)
3324 result.offset = UNKNOWN_OFFSET;
3325 else
3326 result.offset += bitpos;
3327 }
3328 else if (result.type == ADDRESSOF)
3329 {
3330 /* We can end up here for component references on constants like
3331 VIEW_CONVERT_EXPR <>({ 0, 1, 2, 3 })[i]. */
3332 result.type = SCALAR;
3333 result.var = anything_id;
3334 result.offset = 0;
3335 }
3336 else
3337 gcc_unreachable ();
3338}
3339
3340
3341/* Dereference the constraint expression CONS, and return the result.
3342 DEREF (ADDRESSOF) = SCALAR
3343 DEREF (SCALAR) = DEREF
3344 DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
3345 This is needed so that we can handle dereferencing DEREF constraints. */
3346
3347static void
3348do_deref (vec<ce_s> *constraints)
3349{
3350 struct constraint_expr *c;
3351 unsigned int i = 0;
3352
3353 FOR_EACH_VEC_ELT (*constraints, i, c)
3354 {
3355 if (c->type == SCALAR)
3356 c->type = DEREF;
3357 else if (c->type == ADDRESSOF)
3358 c->type = SCALAR;
3359 else if (c->type == DEREF)
3360 {
3361 struct constraint_expr tmplhs;
3362 tmplhs = new_scalar_tmp_constraint_exp ("dereftmp", true);
3363 process_constraint (new_constraint (tmplhs, *c));
3364 c->var = tmplhs.var;
3365 }
3366 else
3367 gcc_unreachable ();
3368 }
3369}
3370
3371/* Given a tree T, return the constraint expression for taking the
3372 address of it. */
3373
3374static void
3375get_constraint_for_address_of (tree t, vec<ce_s> *results)
3376{
3377 struct constraint_expr *c;
3378 unsigned int i;
3379
3380 get_constraint_for_1 (t, results, true, true);
3381
3382 FOR_EACH_VEC_ELT (*results, i, c)
3383 {
3384 if (c->type == DEREF)
3385 c->type = SCALAR;
3386 else
3387 c->type = ADDRESSOF;
3388 }
3389}
3390
3391/* Given a tree T, return the constraint expression for it. */
3392
3393static void
3394get_constraint_for_1 (tree t, vec<ce_s> *results, bool address_p,
3395 bool lhs_p)
3396{
3397 struct constraint_expr temp;
3398
3399 /* x = integer is all glommed to a single variable, which doesn't
3400 point to anything by itself. That is, of course, unless it is an
3401 integer constant being treated as a pointer, in which case, we
3402 will return that this is really the addressof anything. This
3403 happens below, since it will fall into the default case. The only
3404 case we know something about an integer treated like a pointer is
3405 when it is the NULL pointer, and then we just say it points to
3406 NULL.
3407
3408 Do not do that if -fno-delete-null-pointer-checks though, because
3409 in that case *NULL does not fail, so it _should_ alias *anything.
3410 It is not worth adding a new option or renaming the existing one,
3411 since this case is relatively obscure. */
3412 if ((TREE_CODE (t) == INTEGER_CST
3413 && integer_zerop (t))
3414 /* The only valid CONSTRUCTORs in gimple with pointer typed
3415 elements are zero-initializer. But in IPA mode we also
3416 process global initializers, so verify at least. */
3417 || (TREE_CODE (t) == CONSTRUCTOR
3418 && CONSTRUCTOR_NELTS (t) == 0))
3419 {
3420 if (flag_delete_null_pointer_checks)
3421 temp.var = nothing_id;
3422 else
3423 temp.var = nonlocal_id;
3424 temp.type = ADDRESSOF;
3425 temp.offset = 0;
3426 results->safe_push (temp);
3427 return;
3428 }
3429
3430 /* String constants are read-only, ideally we'd have a CONST_DECL
3431 for those. */
3432 if (TREE_CODE (t) == STRING_CST)
3433 {
3434 temp.var = string_id;
3435 temp.type = SCALAR;
3436 temp.offset = 0;
3437 results->safe_push (temp);
3438 return;
3439 }
3440
3441 switch (TREE_CODE_CLASS (TREE_CODE (t)))
3442 {
3443 case tcc_expression:
3444 {
3445 switch (TREE_CODE (t))
3446 {
3447 case ADDR_EXPR:
3448 get_constraint_for_address_of (TREE_OPERAND (t, 0), results);
3449 return;
3450 default:;
3451 }
3452 break;
3453 }
3454 case tcc_reference:
3455 {
3456 switch (TREE_CODE (t))
3457 {
3458 case MEM_REF:
3459 {
3460 struct constraint_expr cs;
3461 varinfo_t vi, curr;
3462 get_constraint_for_ptr_offset (TREE_OPERAND (t, 0),
3463 TREE_OPERAND (t, 1), results);
3464 do_deref (results);
3465
3466 /* If we are not taking the address then make sure to process
3467 all subvariables we might access. */
3468 if (address_p)
3469 return;
3470
3471 cs = results->last ();
3472 if (cs.type == DEREF
3473 && type_can_have_subvars (TREE_TYPE (t)))
3474 {
3475 /* For dereferences this means we have to defer it
3476 to solving time. */
3477 results->last ().offset = UNKNOWN_OFFSET;
3478 return;
3479 }
3480 if (cs.type != SCALAR)
3481 return;
3482
3483 vi = get_varinfo (cs.var);
3484 curr = vi_next (vi);
3485 if (!vi->is_full_var
3486 && curr)
3487 {
3488 unsigned HOST_WIDE_INT size;
3489 if (tree_fits_uhwi_p (TYPE_SIZE (TREE_TYPE (t))))
3490 size = tree_to_uhwi (TYPE_SIZE (TREE_TYPE (t)));
3491 else
3492 size = -1;
3493 for (; curr; curr = vi_next (curr))
3494 {
3495 if (curr->offset - vi->offset < size)
3496 {
3497 cs.var = curr->id;
3498 results->safe_push (cs);
3499 }
3500 else
3501 break;
3502 }
3503 }
3504 return;
3505 }
3506 case ARRAY_REF:
3507 case ARRAY_RANGE_REF:
3508 case COMPONENT_REF:
3509 case IMAGPART_EXPR:
3510 case REALPART_EXPR:
3511 case BIT_FIELD_REF:
3512 get_constraint_for_component_ref (t, results, address_p, lhs_p);
3513 return;
3514 case VIEW_CONVERT_EXPR:
3515 get_constraint_for_1 (TREE_OPERAND (t, 0), results, address_p,
3516 lhs_p);
3517 return;
3518 /* We are missing handling for TARGET_MEM_REF here. */
3519 default:;
3520 }
3521 break;
3522 }
3523 case tcc_exceptional:
3524 {
3525 switch (TREE_CODE (t))
3526 {
3527 case SSA_NAME:
3528 {
3529 get_constraint_for_ssa_var (t, results, address_p);
3530 return;
3531 }
3532 case CONSTRUCTOR:
3533 {
3534 unsigned int i;
3535 tree val;
3536 auto_vec<ce_s> tmp;
3537 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (t), i, val)
3538 {
3539 struct constraint_expr *rhsp;
3540 unsigned j;
3541 get_constraint_for_1 (val, &tmp, address_p, lhs_p);
3542 FOR_EACH_VEC_ELT (tmp, j, rhsp)
3543 results->safe_push (*rhsp);
3544 tmp.truncate (0);
3545 }
3546 /* We do not know whether the constructor was complete,
3547 so technically we have to add &NOTHING or &ANYTHING
3548 like we do for an empty constructor as well. */
3549 return;
3550 }
3551 default:;
3552 }
3553 break;
3554 }
3555 case tcc_declaration:
3556 {
3557 get_constraint_for_ssa_var (t, results, address_p);
3558 return;
3559 }
3560 case tcc_constant:
3561 {
3562 /* We cannot refer to automatic variables through constants. */
3563 temp.type = ADDRESSOF;
3564 temp.var = nonlocal_id;
3565 temp.offset = 0;
3566 results->safe_push (temp);
3567 return;
3568 }
3569 default:;
3570 }
3571
3572 /* The default fallback is a constraint from anything. */
3573 temp.type = ADDRESSOF;
3574 temp.var = anything_id;
3575 temp.offset = 0;
3576 results->safe_push (temp);
3577}
3578
3579/* Given a gimple tree T, return the constraint expression vector for it. */
3580
3581static void
3582get_constraint_for (tree t, vec<ce_s> *results)
3583{
3584 gcc_assert (results->length () == 0);
3585
3586 get_constraint_for_1 (t, results, false, true);
3587}
3588
3589/* Given a gimple tree T, return the constraint expression vector for it
3590 to be used as the rhs of a constraint. */
3591
3592static void
3593get_constraint_for_rhs (tree t, vec<ce_s> *results)
3594{
3595 gcc_assert (results->length () == 0);
3596
3597 get_constraint_for_1 (t, results, false, false);
3598}
3599
3600
3601/* Efficiently generates constraints from all entries in *RHSC to all
3602 entries in *LHSC. */
3603
3604static void
3605process_all_all_constraints (vec<ce_s> lhsc,
3606 vec<ce_s> rhsc)
3607{
3608 struct constraint_expr *lhsp, *rhsp;
3609 unsigned i, j;
3610
3611 if (lhsc.length () <= 1 || rhsc.length () <= 1)
3612 {
3613 FOR_EACH_VEC_ELT (lhsc, i, lhsp)
3614 FOR_EACH_VEC_ELT (rhsc, j, rhsp)
3615 process_constraint (new_constraint (*lhsp, *rhsp));
3616 }
3617 else
3618 {
3619 struct constraint_expr tmp;
3620 tmp = new_scalar_tmp_constraint_exp ("allalltmp", true);
3621 FOR_EACH_VEC_ELT (rhsc, i, rhsp)
3622 process_constraint (new_constraint (tmp, *rhsp));
3623 FOR_EACH_VEC_ELT (lhsc, i, lhsp)
3624 process_constraint (new_constraint (*lhsp, tmp));
3625 }
3626}
3627
3628/* Handle aggregate copies by expanding into copies of the respective
3629 fields of the structures. */
3630
3631static void
3632do_structure_copy (tree lhsop, tree rhsop)
3633{
3634 struct constraint_expr *lhsp, *rhsp;
3635 auto_vec<ce_s> lhsc;
3636 auto_vec<ce_s> rhsc;
3637 unsigned j;
3638
3639 get_constraint_for (lhsop, &lhsc);
3640 get_constraint_for_rhs (rhsop, &rhsc);
3641 lhsp = &lhsc[0];
3642 rhsp = &rhsc[0];
3643 if (lhsp->type == DEREF
3644 || (lhsp->type == ADDRESSOF && lhsp->var == anything_id)
3645 || rhsp->type == DEREF)
3646 {
3647 if (lhsp->type == DEREF)
3648 {
3649 gcc_assert (lhsc.length () == 1);
3650 lhsp->offset = UNKNOWN_OFFSET;
3651 }
3652 if (rhsp->type == DEREF)
3653 {
3654 gcc_assert (rhsc.length () == 1);
3655 rhsp->offset = UNKNOWN_OFFSET;
3656 }
3657 process_all_all_constraints (lhsc, rhsc);
3658 }
3659 else if (lhsp->type == SCALAR
3660 && (rhsp->type == SCALAR
3661 || rhsp->type == ADDRESSOF))
3662 {
3663 HOST_WIDE_INT lhssize, lhsmaxsize, lhsoffset;
3664 HOST_WIDE_INT rhssize, rhsmaxsize, rhsoffset;
3665 bool reverse;
3666 unsigned k = 0;
3667 get_ref_base_and_extent (lhsop, &lhsoffset, &lhssize, &lhsmaxsize,
3668 &reverse);
3669 get_ref_base_and_extent (rhsop, &rhsoffset, &rhssize, &rhsmaxsize,
3670 &reverse);
3671 for (j = 0; lhsc.iterate (j, &lhsp);)
3672 {
3673 varinfo_t lhsv, rhsv;
3674 rhsp = &rhsc[k];
3675 lhsv = get_varinfo (lhsp->var);
3676 rhsv = get_varinfo (rhsp->var);
3677 if (lhsv->may_have_pointers
3678 && (lhsv->is_full_var
3679 || rhsv->is_full_var
3680 || ranges_overlap_p (lhsv->offset + rhsoffset, lhsv->size,
3681 rhsv->offset + lhsoffset, rhsv->size)))
3682 process_constraint (new_constraint (*lhsp, *rhsp));
3683 if (!rhsv->is_full_var
3684 && (lhsv->is_full_var
3685 || (lhsv->offset + rhsoffset + lhsv->size
3686 > rhsv->offset + lhsoffset + rhsv->size)))
3687 {
3688 ++k;
3689 if (k >= rhsc.length ())
3690 break;
3691 }
3692 else
3693 ++j;
3694 }
3695 }
3696 else
3697 gcc_unreachable ();
3698}
3699
3700/* Create constraints ID = { rhsc }. */
3701
3702static void
3703make_constraints_to (unsigned id, vec<ce_s> rhsc)
3704{
3705 struct constraint_expr *c;
3706 struct constraint_expr includes;
3707 unsigned int j;
3708
3709 includes.var = id;
3710 includes.offset = 0;
3711 includes.type = SCALAR;
3712
3713 FOR_EACH_VEC_ELT (rhsc, j, c)
3714 process_constraint (new_constraint (includes, *c));
3715}
3716
3717/* Create a constraint ID = OP. */
3718
3719static void
3720make_constraint_to (unsigned id, tree op)
3721{
3722 auto_vec<ce_s> rhsc;
3723 get_constraint_for_rhs (op, &rhsc);
3724 make_constraints_to (id, rhsc);
3725}
3726
3727/* Create a constraint ID = &FROM. */
3728
3729static void
3730make_constraint_from (varinfo_t vi, int from)
3731{
3732 struct constraint_expr lhs, rhs;
3733
3734 lhs.var = vi->id;
3735 lhs.offset = 0;
3736 lhs.type = SCALAR;
3737
3738 rhs.var = from;
3739 rhs.offset = 0;
3740 rhs.type = ADDRESSOF;
3741 process_constraint (new_constraint (lhs, rhs));
3742}
3743
3744/* Create a constraint ID = FROM. */
3745
3746static void
3747make_copy_constraint (varinfo_t vi, int from)
3748{
3749 struct constraint_expr lhs, rhs;
3750
3751 lhs.var = vi->id;
3752 lhs.offset = 0;
3753 lhs.type = SCALAR;
3754
3755 rhs.var = from;
3756 rhs.offset = 0;
3757 rhs.type = SCALAR;
3758 process_constraint (new_constraint (lhs, rhs));
3759}
3760
3761/* Make constraints necessary to make OP escape. */
3762
3763static void
3764make_escape_constraint (tree op)
3765{
3766 make_constraint_to (escaped_id, op);
3767}
3768
3769/* Add constraints to that the solution of VI is transitively closed. */
3770
3771static void
3772make_transitive_closure_constraints (varinfo_t vi)
3773{
3774 struct constraint_expr lhs, rhs;
3775
3776 /* VAR = *(VAR + UNKNOWN); */
3777 lhs.type = SCALAR;
3778 lhs.var = vi->id;
3779 lhs.offset = 0;
3780 rhs.type = DEREF;
3781 rhs.var = vi->id;
3782 rhs.offset = UNKNOWN_OFFSET;
3783 process_constraint (new_constraint (lhs, rhs));
3784}
3785
3786/* Add constraints to that the solution of VI has all subvariables added. */
3787
3788static void
3789make_any_offset_constraints (varinfo_t vi)
3790{
3791 struct constraint_expr lhs, rhs;
3792
3793 /* VAR = VAR + UNKNOWN; */
3794 lhs.type = SCALAR;
3795 lhs.var = vi->id;
3796 lhs.offset = 0;
3797 rhs.type = SCALAR;
3798 rhs.var = vi->id;
3799 rhs.offset = UNKNOWN_OFFSET;
3800 process_constraint (new_constraint (lhs, rhs));
3801}
3802
3803/* Temporary storage for fake var decls. */
3804struct obstack fake_var_decl_obstack;
3805
3806/* Build a fake VAR_DECL acting as referrer to a DECL_UID. */
3807
3808static tree
3809build_fake_var_decl (tree type)
3810{
3811 tree decl = (tree) XOBNEW (&fake_var_decl_obstack, struct tree_var_decl);
3812 memset (decl, 0, sizeof (struct tree_var_decl));
3813 TREE_SET_CODE (decl, VAR_DECL);
3814 TREE_TYPE (decl) = type;
3815 DECL_UID (decl) = allocate_decl_uid ();
3816 SET_DECL_PT_UID (decl, -1);
3817 layout_decl (decl, 0);
3818 return decl;
3819}
3820
3821/* Create a new artificial heap variable with NAME.
3822 Return the created variable. */
3823
3824static varinfo_t
3825make_heapvar (const char *name, bool add_id)
3826{
3827 varinfo_t vi;
3828 tree heapvar;
3829
3830 heapvar = build_fake_var_decl (ptr_type_node);
3831 DECL_EXTERNAL (heapvar) = 1;
3832
3833 vi = new_var_info (heapvar, name, add_id);
3834 vi->is_artificial_var = true;
3835 vi->is_heap_var = true;
3836 vi->is_unknown_size_var = true;
3837 vi->offset = 0;
3838 vi->fullsize = ~0;
3839 vi->size = ~0;
3840 vi->is_full_var = true;
3841 insert_vi_for_tree (heapvar, vi);
3842
3843 return vi;
3844}
3845
3846/* Create a new artificial heap variable with NAME and make a
3847 constraint from it to LHS. Set flags according to a tag used
3848 for tracking restrict pointers. */
3849
3850static varinfo_t
3851make_constraint_from_restrict (varinfo_t lhs, const char *name, bool add_id)
3852{
3853 varinfo_t vi = make_heapvar (name, add_id);
3854 vi->is_restrict_var = 1;
3855 vi->is_global_var = 1;
3856 vi->may_have_pointers = 1;
3857 make_constraint_from (lhs, vi->id);
3858 return vi;
3859}
3860
3861/* Create a new artificial heap variable with NAME and make a
3862 constraint from it to LHS. Set flags according to a tag used
3863 for tracking restrict pointers and make the artificial heap
3864 point to global memory. */
3865
3866static varinfo_t
3867make_constraint_from_global_restrict (varinfo_t lhs, const char *name,
3868 bool add_id)
3869{
3870 varinfo_t vi = make_constraint_from_restrict (lhs, name, add_id);
3871 make_copy_constraint (vi, nonlocal_id);
3872 return vi;
3873}
3874
3875/* In IPA mode there are varinfos for different aspects of reach
3876 function designator. One for the points-to set of the return
3877 value, one for the variables that are clobbered by the function,
3878 one for its uses and one for each parameter (including a single
3879 glob for remaining variadic arguments). */
3880
3881enum { fi_clobbers = 1, fi_uses = 2,
3882 fi_static_chain = 3, fi_result = 4, fi_parm_base = 5 };
3883
3884/* Get a constraint for the requested part of a function designator FI
3885 when operating in IPA mode. */
3886
3887static struct constraint_expr
3888get_function_part_constraint (varinfo_t fi, unsigned part)
3889{
3890 struct constraint_expr c;
3891
3892 gcc_assert (in_ipa_mode);
3893
3894 if (fi->id == anything_id)
3895 {
3896 /* ??? We probably should have a ANYFN special variable. */
3897 c.var = anything_id;
3898 c.offset = 0;
3899 c.type = SCALAR;
3900 }
3901 else if (TREE_CODE (fi->decl) == FUNCTION_DECL)
3902 {
3903 varinfo_t ai = first_vi_for_offset (fi, part);
3904 if (ai)
3905 c.var = ai->id;
3906 else
3907 c.var = anything_id;
3908 c.offset = 0;
3909 c.type = SCALAR;
3910 }
3911 else
3912 {
3913 c.var = fi->id;
3914 c.offset = part;
3915 c.type = DEREF;
3916 }
3917
3918 return c;
3919}
3920
3921/* For non-IPA mode, generate constraints necessary for a call on the
3922 RHS. */
3923
3924static void
3925handle_rhs_call (gcall *stmt, vec<ce_s> *results)
3926{
3927 struct constraint_expr rhsc;
3928 unsigned i;
3929 bool returns_uses = false;
3930
3931 for (i = 0; i < gimple_call_num_args (stmt); ++i)
3932 {
3933 tree arg = gimple_call_arg (stmt, i);
3934 int flags = gimple_call_arg_flags (stmt, i);
3935
3936 /* If the argument is not used we can ignore it. */
3937 if (flags & EAF_UNUSED)
3938 continue;
3939
3940 /* As we compute ESCAPED context-insensitive we do not gain
3941 any precision with just EAF_NOCLOBBER but not EAF_NOESCAPE
3942 set. The argument would still get clobbered through the
3943 escape solution. */
3944 if ((flags & EAF_NOCLOBBER)
3945 && (flags & EAF_NOESCAPE))
3946 {
3947 varinfo_t uses = get_call_use_vi (stmt);
3948 varinfo_t tem = new_var_info (NULL_TREE, "callarg", true);
3949 tem->is_reg_var = true;
3950 make_constraint_to (tem->id, arg);
3951 make_any_offset_constraints (tem);
3952 if (!(flags & EAF_DIRECT))
3953 make_transitive_closure_constraints (tem);
3954 make_copy_constraint (uses, tem->id);
3955 returns_uses = true;
3956 }
3957 else if (flags & EAF_NOESCAPE)
3958 {
3959 struct constraint_expr lhs, rhs;
3960 varinfo_t uses = get_call_use_vi (stmt);
3961 varinfo_t clobbers = get_call_clobber_vi (stmt);
3962 varinfo_t tem = new_var_info (NULL_TREE, "callarg", true);
3963 tem->is_reg_var = true;
3964 make_constraint_to (tem->id, arg);
3965 make_any_offset_constraints (tem);
3966 if (!(flags & EAF_DIRECT))
3967 make_transitive_closure_constraints (tem);
3968 make_copy_constraint (uses, tem->id);
3969 make_copy_constraint (clobbers, tem->id);
3970 /* Add *tem = nonlocal, do not add *tem = callused as
3971 EAF_NOESCAPE parameters do not escape to other parameters
3972 and all other uses appear in NONLOCAL as well. */
3973 lhs.type = DEREF;
3974 lhs.var = tem->id;
3975 lhs.offset = 0;
3976 rhs.type = SCALAR;
3977 rhs.var = nonlocal_id;
3978 rhs.offset = 0;
3979 process_constraint (new_constraint (lhs, rhs));
3980 returns_uses = true;
3981 }
3982 else
3983 make_escape_constraint (arg);
3984 }
3985
3986 /* If we added to the calls uses solution make sure we account for
3987 pointers to it to be returned. */
3988 if (returns_uses)
3989 {
3990 rhsc.var = get_call_use_vi (stmt)->id;
3991 rhsc.offset = UNKNOWN_OFFSET;
3992 rhsc.type = SCALAR;
3993 results->safe_push (rhsc);
3994 }
3995
3996 /* The static chain escapes as well. */
3997 if (gimple_call_chain (stmt))
3998 make_escape_constraint (gimple_call_chain (stmt));
3999
4000 /* And if we applied NRV the address of the return slot escapes as well. */
4001 if (gimple_call_return_slot_opt_p (stmt)
4002 && gimple_call_lhs (stmt) != NULL_TREE
4003 && TREE_ADDRESSABLE (TREE_TYPE (gimple_call_lhs (stmt))))
4004 {
4005 auto_vec<ce_s> tmpc;
4006 struct constraint_expr lhsc, *c;
4007 get_constraint_for_address_of (gimple_call_lhs (stmt), &tmpc);
4008 lhsc.var = escaped_id;
4009 lhsc.offset = 0;
4010 lhsc.type = SCALAR;
4011 FOR_EACH_VEC_ELT (tmpc, i, c)
4012 process_constraint (new_constraint (lhsc, *c));
4013 }
4014
4015 /* Regular functions return nonlocal memory. */
4016 rhsc.var = nonlocal_id;
4017 rhsc.offset = 0;
4018 rhsc.type = SCALAR;
4019 results->safe_push (rhsc);
4020}
4021
4022/* For non-IPA mode, generate constraints necessary for a call
4023 that returns a pointer and assigns it to LHS. This simply makes
4024 the LHS point to global and escaped variables. */
4025
4026static void
4027handle_lhs_call (gcall *stmt, tree lhs, int flags, vec<ce_s> rhsc,
4028 tree fndecl)
4029{
4030 auto_vec<ce_s> lhsc;
4031
4032 get_constraint_for (lhs, &lhsc);
4033 /* If the store is to a global decl make sure to
4034 add proper escape constraints. */
4035 lhs = get_base_address (lhs);
4036 if (lhs
4037 && DECL_P (lhs)
4038 && is_global_var (lhs))
4039 {
4040 struct constraint_expr tmpc;
4041 tmpc.var = escaped_id;
4042 tmpc.offset = 0;
4043 tmpc.type = SCALAR;
4044 lhsc.safe_push (tmpc);
4045 }
4046
4047 /* If the call returns an argument unmodified override the rhs
4048 constraints. */
4049 if (flags & ERF_RETURNS_ARG
4050 && (flags & ERF_RETURN_ARG_MASK) < gimple_call_num_args (stmt))
4051 {
4052 tree arg;
4053 rhsc.create (0);
4054 arg = gimple_call_arg (stmt, flags & ERF_RETURN_ARG_MASK);
4055 get_constraint_for (arg, &rhsc);
4056 process_all_all_constraints (lhsc, rhsc);
4057 rhsc.release ();
4058 }
4059 else if (flags & ERF_NOALIAS)
4060 {
4061 varinfo_t vi;
4062 struct constraint_expr tmpc;
4063 rhsc.create (0);
4064 vi = make_heapvar ("HEAP", true);
4065 /* We are marking allocated storage local, we deal with it becoming
4066 global by escaping and setting of vars_contains_escaped_heap. */
4067 DECL_EXTERNAL (vi->decl) = 0;
4068 vi->is_global_var = 0;
4069 /* If this is not a real malloc call assume the memory was
4070 initialized and thus may point to global memory. All
4071 builtin functions with the malloc attribute behave in a sane way. */
4072 if (!fndecl
4073 || DECL_BUILT_IN_CLASS (fndecl) != BUILT_IN_NORMAL)
4074 make_constraint_from (vi, nonlocal_id);
4075 tmpc.var = vi->id;
4076 tmpc.offset = 0;
4077 tmpc.type = ADDRESSOF;
4078 rhsc.safe_push (tmpc);
4079 process_all_all_constraints (lhsc, rhsc);
4080 rhsc.release ();
4081 }
4082 else
4083 process_all_all_constraints (lhsc, rhsc);
4084}
4085
4086/* For non-IPA mode, generate constraints necessary for a call of a
4087 const function that returns a pointer in the statement STMT. */
4088
4089static void
4090handle_const_call (gcall *stmt, vec<ce_s> *results)
4091{
4092 struct constraint_expr rhsc;
4093 unsigned int k;
4094 bool need_uses = false;
4095
4096 /* Treat nested const functions the same as pure functions as far
4097 as the static chain is concerned. */
4098 if (gimple_call_chain (stmt))
4099 {
4100 varinfo_t uses = get_call_use_vi (stmt);
4101 make_constraint_to (uses->id, gimple_call_chain (stmt));
4102 need_uses = true;
4103 }
4104
4105 /* And if we applied NRV the address of the return slot escapes as well. */
4106 if (gimple_call_return_slot_opt_p (stmt)
4107 && gimple_call_lhs (stmt) != NULL_TREE
4108 && TREE_ADDRESSABLE (TREE_TYPE (gimple_call_lhs (stmt))))
4109 {
4110 varinfo_t uses = get_call_use_vi (stmt);
4111 auto_vec<ce_s> tmpc;
4112 get_constraint_for_address_of (gimple_call_lhs (stmt), &tmpc);
4113 make_constraints_to (uses->id, tmpc);
4114 need_uses = true;
4115 }
4116
4117 if (need_uses)
4118 {
4119 varinfo_t uses = get_call_use_vi (stmt);
4120 make_any_offset_constraints (uses);
4121 make_transitive_closure_constraints (uses);
4122 rhsc.var = uses->id;
4123 rhsc.offset = 0;
4124 rhsc.type = SCALAR;
4125 results->safe_push (rhsc);
4126 }
4127
4128 /* May return offsetted arguments. */
4129 varinfo_t tem = NULL;
4130 if (gimple_call_num_args (stmt) != 0)
4131 {
4132 tem = new_var_info (NULL_TREE, "callarg", true);
4133 tem->is_reg_var = true;
4134 }
4135 for (k = 0; k < gimple_call_num_args (stmt); ++k)
4136 {
4137 tree arg = gimple_call_arg (stmt, k);
4138 auto_vec<ce_s> argc;
4139 get_constraint_for_rhs (arg, &argc);
4140 make_constraints_to (tem->id, argc);
4141 }
4142 if (tem)
4143 {
4144 ce_s ce;
4145 ce.type = SCALAR;
4146 ce.var = tem->id;
4147 ce.offset = UNKNOWN_OFFSET;
4148 results->safe_push (ce);
4149 }
4150
4151 /* May return addresses of globals. */
4152 rhsc.var = nonlocal_id;
4153 rhsc.offset = 0;
4154 rhsc.type = ADDRESSOF;
4155 results->safe_push (rhsc);
4156}
4157
4158/* For non-IPA mode, generate constraints necessary for a call to a
4159 pure function in statement STMT. */
4160
4161static void
4162handle_pure_call (gcall *stmt, vec<ce_s> *results)
4163{
4164 struct constraint_expr rhsc;
4165 unsigned i;
4166 varinfo_t uses = NULL;
4167
4168 /* Memory reached from pointer arguments is call-used. */
4169 for (i = 0; i < gimple_call_num_args (stmt); ++i)
4170 {
4171 tree arg = gimple_call_arg (stmt, i);
4172 if (!uses)
4173 {
4174 uses = get_call_use_vi (stmt);
4175 make_any_offset_constraints (uses);
4176 make_transitive_closure_constraints (uses);
4177 }
4178 make_constraint_to (uses->id, arg);
4179 }
4180
4181 /* The static chain is used as well. */
4182 if (gimple_call_chain (stmt))
4183 {
4184 if (!uses)
4185 {
4186 uses = get_call_use_vi (stmt);
4187 make_any_offset_constraints (uses);
4188 make_transitive_closure_constraints (uses);
4189 }
4190 make_constraint_to (uses->id, gimple_call_chain (stmt));
4191 }
4192
4193 /* And if we applied NRV the address of the return slot. */
4194 if (gimple_call_return_slot_opt_p (stmt)
4195 && gimple_call_lhs (stmt) != NULL_TREE
4196 && TREE_ADDRESSABLE (TREE_TYPE (gimple_call_lhs (stmt))))
4197 {
4198 if (!uses)
4199 {
4200 uses = get_call_use_vi (stmt);
4201 make_any_offset_constraints (uses);
4202 make_transitive_closure_constraints (uses);
4203 }
4204 auto_vec<ce_s> tmpc;
4205 get_constraint_for_address_of (gimple_call_lhs (stmt), &tmpc);
4206 make_constraints_to (uses->id, tmpc);
4207 }
4208
4209 /* Pure functions may return call-used and nonlocal memory. */
4210 if (uses)
4211 {
4212 rhsc.var = uses->id;
4213 rhsc.offset = 0;
4214 rhsc.type = SCALAR;
4215 results->safe_push (rhsc);
4216 }
4217 rhsc.var = nonlocal_id;
4218 rhsc.offset = 0;
4219 rhsc.type = SCALAR;
4220 results->safe_push (rhsc);
4221}
4222
4223
4224/* Return the varinfo for the callee of CALL. */
4225
4226static varinfo_t
4227get_fi_for_callee (gcall *call)
4228{
4229 tree decl, fn = gimple_call_fn (call);
4230
4231 if (fn && TREE_CODE (fn) == OBJ_TYPE_REF)
4232 fn = OBJ_TYPE_REF_EXPR (fn);
4233
4234 /* If we can directly resolve the function being called, do so.
4235 Otherwise, it must be some sort of indirect expression that
4236 we should still be able to handle. */
4237 decl = gimple_call_addr_fndecl (fn);
4238 if (decl)
4239 return get_vi_for_tree (decl);
4240
4241 /* If the function is anything other than a SSA name pointer we have no
4242 clue and should be getting ANYFN (well, ANYTHING for now). */
4243 if (!fn || TREE_CODE (fn) != SSA_NAME)
4244 return get_varinfo (anything_id);
4245
4246 if (SSA_NAME_IS_DEFAULT_DEF (fn)
4247 && (TREE_CODE (SSA_NAME_VAR (fn)) == PARM_DECL
4248 || TREE_CODE (SSA_NAME_VAR (fn)) == RESULT_DECL))
4249 fn = SSA_NAME_VAR (fn);
4250
4251 return get_vi_for_tree (fn);
4252}
4253
4254/* Create constraints for assigning call argument ARG to the incoming parameter
4255 INDEX of function FI. */
4256
4257static void
4258find_func_aliases_for_call_arg (varinfo_t fi, unsigned index, tree arg)
4259{
4260 struct constraint_expr lhs;
4261 lhs = get_function_part_constraint (fi, fi_parm_base + index);
4262
4263 auto_vec<ce_s, 2> rhsc;
4264 get_constraint_for_rhs (arg, &rhsc);
4265
4266 unsigned j;
4267 struct constraint_expr *rhsp;
4268 FOR_EACH_VEC_ELT (rhsc, j, rhsp)
4269 process_constraint (new_constraint (lhs, *rhsp));
4270}
4271
4272/* Return true if FNDECL may be part of another lto partition. */
4273
4274static bool
4275fndecl_maybe_in_other_partition (tree fndecl)
4276{
4277 cgraph_node *fn_node = cgraph_node::get (fndecl);
4278 if (fn_node == NULL)
4279 return true;
4280
4281 return fn_node->in_other_partition;
4282}
4283
4284/* Create constraints for the builtin call T. Return true if the call
4285 was handled, otherwise false. */
4286
4287static bool
4288find_func_aliases_for_builtin_call (struct function *fn, gcall *t)
4289{
4290 tree fndecl = gimple_call_fndecl (t);
4291 auto_vec<ce_s, 2> lhsc;
4292 auto_vec<ce_s, 4> rhsc;
4293 varinfo_t fi;
4294
4295 if (gimple_call_builtin_p (t, BUILT_IN_NORMAL))
4296 /* ??? All builtins that are handled here need to be handled
4297 in the alias-oracle query functions explicitly! */
4298 switch (DECL_FUNCTION_CODE (fndecl))
4299 {
4300 /* All the following functions return a pointer to the same object
4301 as their first argument points to. The functions do not add
4302 to the ESCAPED solution. The functions make the first argument
4303 pointed to memory point to what the second argument pointed to
4304 memory points to. */
4305 case BUILT_IN_STRCPY:
4306 case BUILT_IN_STRNCPY:
4307 case BUILT_IN_BCOPY:
4308 case BUILT_IN_MEMCPY:
4309 case BUILT_IN_MEMMOVE:
4310 case BUILT_IN_MEMPCPY:
4311 case BUILT_IN_STPCPY:
4312 case BUILT_IN_STPNCPY:
4313 case BUILT_IN_STRCAT:
4314 case BUILT_IN_STRNCAT:
4315 case BUILT_IN_STRCPY_CHK:
4316 case BUILT_IN_STRNCPY_CHK:
4317 case BUILT_IN_MEMCPY_CHK:
4318 case BUILT_IN_MEMMOVE_CHK:
4319 case BUILT_IN_MEMPCPY_CHK:
4320 case BUILT_IN_STPCPY_CHK:
4321 case BUILT_IN_STPNCPY_CHK:
4322 case BUILT_IN_STRCAT_CHK:
4323 case BUILT_IN_STRNCAT_CHK:
4324 case BUILT_IN_TM_MEMCPY:
4325 case BUILT_IN_TM_MEMMOVE:
4326 {
4327 tree res = gimple_call_lhs (t);
4328 tree dest = gimple_call_arg (t, (DECL_FUNCTION_CODE (fndecl)
4329 == BUILT_IN_BCOPY ? 1 : 0));
4330 tree src = gimple_call_arg (t, (DECL_FUNCTION_CODE (fndecl)
4331 == BUILT_IN_BCOPY ? 0 : 1));
4332 if (res != NULL_TREE)
4333 {
4334 get_constraint_for (res, &lhsc);
4335 if (DECL_FUNCTION_CODE (fndecl) == BUILT_IN_MEMPCPY
4336 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_STPCPY
4337 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_STPNCPY
4338 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_MEMPCPY_CHK
4339 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_STPCPY_CHK
4340 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_STPNCPY_CHK)
4341 get_constraint_for_ptr_offset (dest, NULL_TREE, &rhsc);
4342 else
4343 get_constraint_for (dest, &rhsc);
4344 process_all_all_constraints (lhsc, rhsc);
4345 lhsc.truncate (0);
4346 rhsc.truncate (0);
4347 }
4348 get_constraint_for_ptr_offset (dest, NULL_TREE, &lhsc);
4349 get_constraint_for_ptr_offset (src, NULL_TREE, &rhsc);
4350 do_deref (&lhsc);
4351 do_deref (&rhsc);
4352 process_all_all_constraints (lhsc, rhsc);
4353 return true;
4354 }
4355 case BUILT_IN_MEMSET:
4356 case BUILT_IN_MEMSET_CHK:
4357 case BUILT_IN_TM_MEMSET:
4358 {
4359 tree res = gimple_call_lhs (t);
4360 tree dest = gimple_call_arg (t, 0);
4361 unsigned i;
4362 ce_s *lhsp;
4363 struct constraint_expr ac;
4364 if (res != NULL_TREE)
4365 {
4366 get_constraint_for (res, &lhsc);
4367 get_constraint_for (dest, &rhsc);
4368 process_all_all_constraints (lhsc, rhsc);
4369 lhsc.truncate (0);
4370 }
4371 get_constraint_for_ptr_offset (dest, NULL_TREE, &lhsc);
4372 do_deref (&lhsc);
4373 if (flag_delete_null_pointer_checks
4374 && integer_zerop (gimple_call_arg (t, 1)))
4375 {
4376 ac.type = ADDRESSOF;
4377 ac.var = nothing_id;
4378 }
4379 else
4380 {
4381 ac.type =