--- /dev/null
+/* Tree based points-to analysis
+ Copyright (C) 2005, 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
+ Contributed by Daniel Berlin <dberlin@dberlin.org>
+
+ This file is part of GCC.
+
+ GCC is free software; you can redistribute it and/or modify
+ under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 3 of the License, or
+ (at your option) any later version.
+
+ GCC is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with GCC; see the file COPYING3. If not see
+ <http://www.gnu.org/licenses/>. */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include "ggc.h"
+#include "obstack.h"
+#include "bitmap.h"
+#include "flags.h"
+#include "rtl.h"
+#include "tm_p.h"
+#include "hard-reg-set.h"
+#include "basic-block.h"
+#include "output.h"
+#include "tree.h"
+#include "c-common.h"
+#include "tree-flow.h"
+#include "tree-inline.h"
+#include "varray.h"
+#include "c-tree.h"
+#include "diagnostic.h"
+#include "toplev.h"
+#include "gimple.h"
+#include "hashtab.h"
+#include "function.h"
+#include "cgraph.h"
+#include "tree-pass.h"
+#include "timevar.h"
+#include "alloc-pool.h"
+#include "splay-tree.h"
+#include "params.h"
+#include "tree-ssa-structalias.h"
+#include "cgraph.h"
+#include "alias.h"
+#include "pointer-set.h"
+
+/* The idea behind this analyzer is to generate set constraints from the
+ program, then solve the resulting constraints in order to generate the
+ points-to sets.
+
+ Set constraints are a way of modeling program analysis problems that
+ involve sets. They consist of an inclusion constraint language,
+ describing the variables (each variable is a set) and operations that
+ are involved on the variables, and a set of rules that derive facts
+ from these operations. To solve a system of set constraints, you derive
+ all possible facts under the rules, which gives you the correct sets
+ as a consequence.
+
+ See "Efficient Field-sensitive pointer analysis for C" by "David
+ J. Pearce and Paul H. J. Kelly and Chris Hankin, at
+ http://citeseer.ist.psu.edu/pearce04efficient.html
+
+ Also see "Ultra-fast Aliasing Analysis using CLA: A Million Lines
+ of C Code in a Second" by ""Nevin Heintze and Olivier Tardieu" at
+ http://citeseer.ist.psu.edu/heintze01ultrafast.html
+
+ There are three types of real constraint expressions, DEREF,
+ ADDRESSOF, and SCALAR. Each constraint expression consists
+ of a constraint type, a variable, and an offset.
+
+ SCALAR is a constraint expression type used to represent x, whether
+ it appears on the LHS or the RHS of a statement.
+ DEREF is a constraint expression type used to represent *x, whether
+ it appears on the LHS or the RHS of a statement.
+ ADDRESSOF is a constraint expression used to represent &x, whether
+ it appears on the LHS or the RHS of a statement.
+
+ Each pointer variable in the program is assigned an integer id, and
+ each field of a structure variable is assigned an integer id as well.
+
+ Structure variables are linked to their list of fields through a "next
+ field" in each variable that points to the next field in offset
+ order.
+ Each variable for a structure field has
+
+ 1. "size", that tells the size in bits of that field.
+ 2. "fullsize, that tells the size in bits of the entire structure.
+ 3. "offset", that tells the offset in bits from the beginning of the
+ structure to this field.
+
+ Thus,
+ struct f
+ {
+ int a;
+ int b;
+ } foo;
+ int *bar;
+
+ looks like
+
+ foo.a -> id 1, size 32, offset 0, fullsize 64, next foo.b
+ foo.b -> id 2, size 32, offset 32, fullsize 64, next NULL
+ bar -> id 3, size 32, offset 0, fullsize 32, next NULL
+
+
+ In order to solve the system of set constraints, the following is
+ done:
+
+ 1. Each constraint variable x has a solution set associated with it,
+ Sol(x).
+
+ 2. Constraints are separated into direct, copy, and complex.
+ Direct constraints are ADDRESSOF constraints that require no extra
+ processing, such as P = &Q
+ Copy constraints are those of the form P = Q.
+ Complex constraints are all the constraints involving dereferences
+ and offsets (including offsetted copies).
+
+ 3. All direct constraints of the form P = &Q are processed, such
+ that Q is added to Sol(P)
+
+ 4. All complex constraints for a given constraint variable are stored in a
+ linked list attached to that variable's node.
+
+ 5. A directed graph is built out of the copy constraints. Each
+ constraint variable is a node in the graph, and an edge from
+ Q to P is added for each copy constraint of the form P = Q
+
+ 6. The graph is then walked, and solution sets are
+ propagated along the copy edges, such that an edge from Q to P
+ causes Sol(P) <- Sol(P) union Sol(Q).
+
+ 7. As we visit each node, all complex constraints associated with
+ that node are processed by adding appropriate copy edges to the graph, or the
+ appropriate variables to the solution set.
+
+ 8. The process of walking the graph is iterated until no solution
+ sets change.
+
+ Prior to walking the graph in steps 6 and 7, We perform static
+ cycle elimination on the constraint graph, as well
+ as off-line variable substitution.
+
+ TODO: Adding offsets to pointer-to-structures can be handled (IE not punted
+ on and turned into anything), but isn't. You can just see what offset
+ inside the pointed-to struct it's going to access.
+
+ TODO: Constant bounded arrays can be handled as if they were structs of the
+ same number of elements.
+
+ TODO: Modeling heap and incoming pointers becomes much better if we
+ add fields to them as we discover them, which we could do.
+
+ TODO: We could handle unions, but to be honest, it's probably not
+ worth the pain or slowdown. */
+
+static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map)))
+htab_t heapvar_for_stmt;
+
+static bool use_field_sensitive = true;
+static int in_ipa_mode = 0;
+
+/* Used for predecessor bitmaps. */
+static bitmap_obstack predbitmap_obstack;
+
+/* Used for points-to sets. */
+static bitmap_obstack pta_obstack;
+
+/* Used for oldsolution members of variables. */
+static bitmap_obstack oldpta_obstack;
+
+/* Used for per-solver-iteration bitmaps. */
+static bitmap_obstack iteration_obstack;
+
+static unsigned int create_variable_info_for (tree, const char *);
+typedef struct constraint_graph *constraint_graph_t;
+static void unify_nodes (constraint_graph_t, unsigned int, unsigned int, bool);
+
+DEF_VEC_P(constraint_t);
+DEF_VEC_ALLOC_P(constraint_t,heap);
+
+#define EXECUTE_IF_IN_NONNULL_BITMAP(a, b, c, d) \
+ if (a) \
+ EXECUTE_IF_SET_IN_BITMAP (a, b, c, d)
+
+static struct constraint_stats
+{
+ unsigned int total_vars;
+ unsigned int nonpointer_vars;
+ unsigned int unified_vars_static;
+ unsigned int unified_vars_dynamic;
+ unsigned int iterations;
+ unsigned int num_edges;
+ unsigned int num_implicit_edges;
+ unsigned int points_to_sets_created;
+} stats;
+
+struct variable_info
+{
+ /* ID of this variable */
+ unsigned int id;
+
+ /* True if this is a variable created by the constraint analysis, such as
+ heap variables and constraints we had to break up. */
+ unsigned int is_artificial_var:1;
+
+ /* True if this is a special variable whose solution set should not be
+ changed. */
+ unsigned int is_special_var:1;
+
+ /* True for variables whose size is not known or variable. */
+ unsigned int is_unknown_size_var:1;
+
+ /* True for (sub-)fields that represent a whole variable. */
+ unsigned int is_full_var : 1;
+
+ /* True if this is a heap variable. */
+ unsigned int is_heap_var:1;
+
+ /* True if we may not use TBAA to prune references to this
+ variable. This is used for C++ placement new. */
+ unsigned int no_tbaa_pruning : 1;
+
+ /* True if this field may contain pointers. */
+ unsigned int may_have_pointers : 1;
+
+ /* Variable id this was collapsed to due to type unsafety. Zero if
+ this variable was not collapsed. This should be unused completely
+ after build_succ_graph, or something is broken. */
+ unsigned int collapsed_to;
+
+ /* A link to the variable for the next field in this structure. */
+ struct variable_info *next;
+
+ /* Offset of this variable, in bits, from the base variable */
+ unsigned HOST_WIDE_INT offset;
+
+ /* Size of the variable, in bits. */
+ unsigned HOST_WIDE_INT size;
+
+ /* Full size of the base variable, in bits. */
+ unsigned HOST_WIDE_INT fullsize;
+
+ /* Name of this variable */
+ const char *name;
+
+ /* Tree that this variable is associated with. */
+ tree decl;
+
+ /* Points-to set for this variable. */
+ bitmap solution;
+
+ /* Old points-to set for this variable. */
+ bitmap oldsolution;
+};
+typedef struct variable_info *varinfo_t;
+
+static varinfo_t first_vi_for_offset (varinfo_t, unsigned HOST_WIDE_INT);
+static varinfo_t lookup_vi_for_tree (tree);
+
+/* Pool of variable info structures. */
+static alloc_pool variable_info_pool;
+
+DEF_VEC_P(varinfo_t);
+
+DEF_VEC_ALLOC_P(varinfo_t, heap);
+
+/* Table of variable info structures for constraint variables.
+ Indexed directly by variable info id. */
+static VEC(varinfo_t,heap) *varmap;
+
+/* Return the varmap element N */
+
+static inline varinfo_t
+get_varinfo (unsigned int n)
+{
+ return VEC_index (varinfo_t, varmap, n);
+}
+
+/* Return the varmap element N, following the collapsed_to link. */
+
+static inline varinfo_t
+get_varinfo_fc (unsigned int n)
+{
+ varinfo_t v = VEC_index (varinfo_t, varmap, n);
+
+ if (v->collapsed_to != 0)
+ return get_varinfo (v->collapsed_to);
+ return v;
+}
+
+/* Static IDs for the special variables. */
+enum { nothing_id = 0, anything_id = 1, readonly_id = 2,
+ escaped_id = 3, nonlocal_id = 4, callused_id = 5,
+ storedanything_id = 6, integer_id = 7 };
+
+/* Variable that represents the unknown pointer. */
+static varinfo_t var_anything;
+static tree anything_tree;
+
+/* Variable that represents the NULL pointer. */
+static varinfo_t var_nothing;
+static tree nothing_tree;
+
+/* Variable that represents read only memory. */
+static varinfo_t var_readonly;
+static tree readonly_tree;
+
+/* Variable that represents escaped memory. */
+static varinfo_t var_escaped;
+static tree escaped_tree;
+
+/* Variable that represents nonlocal memory. */
+static varinfo_t var_nonlocal;
+static tree nonlocal_tree;
+
+/* Variable that represents call-used memory. */
+static varinfo_t var_callused;
+static tree callused_tree;
+
+/* Variable that represents variables that are stored to anything. */
+static varinfo_t var_storedanything;
+static tree storedanything_tree;
+
+/* Variable that represents integers. This is used for when people do things
+ like &0->a.b. */
+static varinfo_t var_integer;
+static tree integer_tree;
+
+/* Lookup a heap var for FROM, and return it if we find one. */
+
+static tree
+heapvar_lookup (tree from)
+{
+ struct tree_map *h, in;
+ in.base.from = from;
+
+ h = (struct tree_map *) htab_find_with_hash (heapvar_for_stmt, &in,
+ htab_hash_pointer (from));
+ if (h)
+ return h->to;
+ return NULL_TREE;
+}
+
+/* Insert a mapping FROM->TO in the heap var for statement
+ hashtable. */
+
+static void
+heapvar_insert (tree from, tree to)
+{
+ struct tree_map *h;
+ void **loc;
+
+ h = GGC_NEW (struct tree_map);
+ h->hash = htab_hash_pointer (from);
+ h->base.from = from;
+ h->to = to;
+ loc = htab_find_slot_with_hash (heapvar_for_stmt, h, h->hash, INSERT);
+ *(struct tree_map **) loc = h;
+}
+
+/* Return a new variable info structure consisting for a variable
+ named NAME, and using constraint graph node NODE. */
+
+static varinfo_t
+new_var_info (tree t, unsigned int id, const char *name)
+{
+ varinfo_t ret = (varinfo_t) pool_alloc (variable_info_pool);
+ tree var;
+
+ ret->id = id;
+ ret->name = name;
+ ret->decl = t;
+ ret->is_artificial_var = false;
+ ret->is_heap_var = false;
+ ret->is_special_var = false;
+ ret->is_unknown_size_var = false;
+ ret->is_full_var = false;
+ ret->may_have_pointers = true;
+ var = t;
+ if (TREE_CODE (var) == SSA_NAME)
+ var = SSA_NAME_VAR (var);
+ ret->no_tbaa_pruning = (DECL_P (var)
+ && POINTER_TYPE_P (TREE_TYPE (var))
+ && DECL_NO_TBAA_P (var));
+ ret->solution = BITMAP_ALLOC (&pta_obstack);
+ ret->oldsolution = BITMAP_ALLOC (&oldpta_obstack);
+ ret->next = NULL;
+ ret->collapsed_to = 0;
+ return ret;
+}
+
+typedef enum {SCALAR, DEREF, ADDRESSOF} constraint_expr_type;
+
+/* An expression that appears in a constraint. */
+
+struct constraint_expr
+{
+ /* Constraint type. */
+ constraint_expr_type type;
+
+ /* Variable we are referring to in the constraint. */
+ unsigned int var;
+
+ /* Offset, in bits, of this constraint from the beginning of
+ variables it ends up referring to.
+
+ IOW, in a deref constraint, we would deref, get the result set,
+ then add OFFSET to each member. */
+ unsigned HOST_WIDE_INT offset;
+};
+
+typedef struct constraint_expr ce_s;
+DEF_VEC_O(ce_s);
+DEF_VEC_ALLOC_O(ce_s, heap);
+static void get_constraint_for_1 (tree, VEC(ce_s, heap) **, bool);
+static void get_constraint_for (tree, VEC(ce_s, heap) **);
+static void do_deref (VEC (ce_s, heap) **);
+
+/* Our set constraints are made up of two constraint expressions, one
+ LHS, and one RHS.
+
+ As described in the introduction, our set constraints each represent an
+ operation between set valued variables.
+*/
+struct constraint
+{
+ struct constraint_expr lhs;
+ struct constraint_expr rhs;
+};
+
+/* List of constraints that we use to build the constraint graph from. */
+
+static VEC(constraint_t,heap) *constraints;
+static alloc_pool constraint_pool;
+
+
+DEF_VEC_I(int);
+DEF_VEC_ALLOC_I(int, heap);
+
+/* The constraint graph is represented as an array of bitmaps
+ containing successor nodes. */
+
+struct constraint_graph
+{
+ /* Size of this graph, which may be different than the number of
+ nodes in the variable map. */
+ unsigned int size;
+
+ /* Explicit successors of each node. */
+ bitmap *succs;
+
+ /* Implicit predecessors of each node (Used for variable
+ substitution). */
+ bitmap *implicit_preds;
+
+ /* Explicit predecessors of each node (Used for variable substitution). */
+ bitmap *preds;
+
+ /* Indirect cycle representatives, or -1 if the node has no indirect
+ cycles. */
+ int *indirect_cycles;
+
+ /* Representative node for a node. rep[a] == a unless the node has
+ been unified. */
+ unsigned int *rep;
+
+ /* Equivalence class representative for a label. This is used for
+ variable substitution. */
+ int *eq_rep;
+
+ /* Pointer equivalence label for a node. All nodes with the same
+ pointer equivalence label can be unified together at some point
+ (either during constraint optimization or after the constraint
+ graph is built). */
+ unsigned int *pe;
+
+ /* Pointer equivalence representative for a label. This is used to
+ handle nodes that are pointer equivalent but not location
+ equivalent. We can unite these once the addressof constraints
+ are transformed into initial points-to sets. */
+ int *pe_rep;
+
+ /* Pointer equivalence label for each node, used during variable
+ substitution. */
+ unsigned int *pointer_label;
+
+ /* Location equivalence label for each node, used during location
+ equivalence finding. */
+ unsigned int *loc_label;
+
+ /* Pointed-by set for each node, used during location equivalence
+ finding. This is pointed-by rather than pointed-to, because it
+ is constructed using the predecessor graph. */
+ bitmap *pointed_by;
+
+ /* Points to sets for pointer equivalence. This is *not* the actual
+ points-to sets for nodes. */
+ bitmap *points_to;
+
+ /* Bitmap of nodes where the bit is set if the node is a direct
+ node. Used for variable substitution. */
+ sbitmap direct_nodes;
+
+ /* Bitmap of nodes where the bit is set if the node is address
+ taken. Used for variable substitution. */
+ bitmap address_taken;
+
+ /* Vector of complex constraints for each graph node. Complex
+ constraints are those involving dereferences or offsets that are
+ not 0. */
+ VEC(constraint_t,heap) **complex;
+};
+
+static constraint_graph_t graph;
+
+/* During variable substitution and the offline version of indirect
+ cycle finding, we create nodes to represent dereferences and
+ address taken constraints. These represent where these start and
+ end. */
+#define FIRST_REF_NODE (VEC_length (varinfo_t, varmap))
+#define LAST_REF_NODE (FIRST_REF_NODE + (FIRST_REF_NODE - 1))
+
+/* Return the representative node for NODE, if NODE has been unioned
+ with another NODE.
+ This function performs path compression along the way to finding
+ the representative. */
+
+static unsigned int
+find (unsigned int node)
+{
+ gcc_assert (node < graph->size);
+ if (graph->rep[node] != node)
+ return graph->rep[node] = find (graph->rep[node]);
+ return node;
+}
+
+/* Union the TO and FROM nodes to the TO nodes.
+ Note that at some point in the future, we may want to do
+ union-by-rank, in which case we are going to have to return the
+ node we unified to. */
+
+static bool
+unite (unsigned int to, unsigned int from)
+{
+ gcc_assert (to < graph->size && from < graph->size);
+ if (to != from && graph->rep[from] != to)
+ {
+ graph->rep[from] = to;
+ return true;
+ }
+ return false;
+}
+
+/* Create a new constraint consisting of LHS and RHS expressions. */
+
+static constraint_t
+new_constraint (const struct constraint_expr lhs,
+ const struct constraint_expr rhs)
+{
+ constraint_t ret = (constraint_t) pool_alloc (constraint_pool);
+ ret->lhs = lhs;
+ ret->rhs = rhs;
+ return ret;
+}
+
+/* Print out constraint C to FILE. */
+
+void
+dump_constraint (FILE *file, constraint_t c)
+{
+ if (c->lhs.type == ADDRESSOF)
+ fprintf (file, "&");
+ else if (c->lhs.type == DEREF)
+ fprintf (file, "*");
+ fprintf (file, "%s", get_varinfo_fc (c->lhs.var)->name);
+ if (c->lhs.offset != 0)
+ fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->lhs.offset);
+ fprintf (file, " = ");
+ if (c->rhs.type == ADDRESSOF)
+ fprintf (file, "&");
+ else if (c->rhs.type == DEREF)
+ fprintf (file, "*");
+ fprintf (file, "%s", get_varinfo_fc (c->rhs.var)->name);
+ if (c->rhs.offset != 0)
+ fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->rhs.offset);
+ fprintf (file, "\n");
+}
+
+/* Print out constraint C to stderr. */
+
+void
+debug_constraint (constraint_t c)
+{
+ dump_constraint (stderr, c);
+}
+
+/* Print out all constraints to FILE */
+
+void
+dump_constraints (FILE *file)
+{
+ int i;
+ constraint_t c;
+ for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
+ dump_constraint (file, c);
+}
+
+/* Print out all constraints to stderr. */
+
+void
+debug_constraints (void)
+{
+ dump_constraints (stderr);
+}
+
+/* Print out to FILE the edge in the constraint graph that is created by
+ constraint c. The edge may have a label, depending on the type of
+ constraint that it represents. If complex1, e.g: a = *b, then the label
+ is "=*", if complex2, e.g: *a = b, then the label is "*=", if
+ complex with an offset, e.g: a = b + 8, then the label is "+".
+ Otherwise the edge has no label. */
+
+void
+dump_constraint_edge (FILE *file, constraint_t c)
+{
+ if (c->rhs.type != ADDRESSOF)
+ {
+ const char *src = get_varinfo_fc (c->rhs.var)->name;
+ const char *dst = get_varinfo_fc (c->lhs.var)->name;
+ fprintf (file, " \"%s\" -> \"%s\" ", src, dst);
+ /* Due to preprocessing of constraints, instructions like *a = *b are
+ illegal; thus, we do not have to handle such cases. */
+ if (c->lhs.type == DEREF)
+ fprintf (file, " [ label=\"*=\" ] ;\n");
+ else if (c->rhs.type == DEREF)
+ fprintf (file, " [ label=\"=*\" ] ;\n");
+ else
+ {
+ /* We must check the case where the constraint is an offset.
+ In this case, it is treated as a complex constraint. */
+ if (c->rhs.offset != c->lhs.offset)
+ fprintf (file, " [ label=\"+\" ] ;\n");
+ else
+ fprintf (file, " ;\n");
+ }
+ }
+}
+
+/* Print the constraint graph in dot format. */
+
+void
+dump_constraint_graph (FILE *file)
+{
+ unsigned int i=0, size;
+ constraint_t c;
+
+ /* Only print the graph if it has already been initialized: */
+ if (!graph)
+ return;
+
+ /* Print the constraints used to produce the constraint graph. The
+ constraints will be printed as comments in the dot file: */
+ fprintf (file, "\n\n/* Constraints used in the constraint graph:\n");
+ dump_constraints (file);
+ fprintf (file, "*/\n");
+
+ /* Prints the header of the dot file: */
+ fprintf (file, "\n\n// The constraint graph in dot format:\n");
+ fprintf (file, "strict digraph {\n");
+ fprintf (file, " node [\n shape = box\n ]\n");
+ fprintf (file, " edge [\n fontsize = \"12\"\n ]\n");
+ fprintf (file, "\n // List of nodes in the constraint graph:\n");
+
+ /* The next lines print the nodes in the graph. In order to get the
+ number of nodes in the graph, we must choose the minimum between the
+ vector VEC (varinfo_t, varmap) and graph->size. If the graph has not
+ yet been initialized, then graph->size == 0, otherwise we must only
+ read nodes that have an entry in VEC (varinfo_t, varmap). */
+ size = VEC_length (varinfo_t, varmap);
+ size = size < graph->size ? size : graph->size;
+ for (i = 0; i < size; i++)
+ {
+ const char *name = get_varinfo_fc (graph->rep[i])->name;
+ fprintf (file, " \"%s\" ;\n", name);
+ }
+
+ /* Go over the list of constraints printing the edges in the constraint
+ graph. */
+ fprintf (file, "\n // The constraint edges:\n");
+ for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
+ if (c)
+ dump_constraint_edge (file, c);
+
+ /* Prints the tail of the dot file. By now, only the closing bracket. */
+ fprintf (file, "}\n\n\n");
+}
+
+/* Print out the constraint graph to stderr. */
+
+void
+debug_constraint_graph (void)
+{
+ dump_constraint_graph (stderr);
+}
+
+/* SOLVER FUNCTIONS
+
+ The solver is a simple worklist solver, that works on the following
+ algorithm:
+
+ sbitmap changed_nodes = all zeroes;
+ changed_count = 0;
+ For each node that is not already collapsed:
+ changed_count++;
+ set bit in changed nodes
+
+ while (changed_count > 0)
+ {
+ compute topological ordering for constraint graph
+
+ find and collapse cycles in the constraint graph (updating
+ changed if necessary)
+
+ for each node (n) in the graph in topological order:
+ changed_count--;
+
+ Process each complex constraint associated with the node,
+ updating changed if necessary.
+
+ For each outgoing edge from n, propagate the solution from n to
+ the destination of the edge, updating changed as necessary.
+
+ } */
+
+/* Return true if two constraint expressions A and B are equal. */
+
+static bool
+constraint_expr_equal (struct constraint_expr a, struct constraint_expr b)
+{
+ return a.type == b.type && a.var == b.var && a.offset == b.offset;
+}
+
+/* Return true if constraint expression A is less than constraint expression
+ B. This is just arbitrary, but consistent, in order to give them an
+ ordering. */
+
+static bool
+constraint_expr_less (struct constraint_expr a, struct constraint_expr b)
+{
+ if (a.type == b.type)
+ {
+ if (a.var == b.var)
+ return a.offset < b.offset;
+ else
+ return a.var < b.var;
+ }
+ else
+ return a.type < b.type;
+}
+
+/* Return true if constraint A is less than constraint B. This is just
+ arbitrary, but consistent, in order to give them an ordering. */
+
+static bool
+constraint_less (const constraint_t a, const constraint_t b)
+{
+ if (constraint_expr_less (a->lhs, b->lhs))
+ return true;
+ else if (constraint_expr_less (b->lhs, a->lhs))
+ return false;
+ else
+ return constraint_expr_less (a->rhs, b->rhs);
+}
+
+/* Return true if two constraints A and B are equal. */
+
+static bool
+constraint_equal (struct constraint a, struct constraint b)
+{
+ return constraint_expr_equal (a.lhs, b.lhs)
+ && constraint_expr_equal (a.rhs, b.rhs);
+}
+
+
+/* Find a constraint LOOKFOR in the sorted constraint vector VEC */
+
+static constraint_t
+constraint_vec_find (VEC(constraint_t,heap) *vec,
+ struct constraint lookfor)
+{
+ unsigned int place;
+ constraint_t found;
+
+ if (vec == NULL)
+ return NULL;
+
+ place = VEC_lower_bound (constraint_t, vec, &lookfor, constraint_less);
+ if (place >= VEC_length (constraint_t, vec))
+ return NULL;
+ found = VEC_index (constraint_t, vec, place);
+ if (!constraint_equal (*found, lookfor))
+ return NULL;
+ return found;
+}
+
+/* Union two constraint vectors, TO and FROM. Put the result in TO. */
+
+static void
+constraint_set_union (VEC(constraint_t,heap) **to,
+ VEC(constraint_t,heap) **from)
+{
+ int i;
+ constraint_t c;
+
+ for (i = 0; VEC_iterate (constraint_t, *from, i, c); i++)
+ {
+ if (constraint_vec_find (*to, *c) == NULL)
+ {
+ unsigned int place = VEC_lower_bound (constraint_t, *to, c,
+ constraint_less);
+ VEC_safe_insert (constraint_t, heap, *to, place, c);
+ }
+ }
+}
+
+/* Take a solution set SET, add OFFSET to each member of the set, and
+ overwrite SET with the result when done. */
+
+static void
+solution_set_add (bitmap set, unsigned HOST_WIDE_INT offset)
+{
+ bitmap result = BITMAP_ALLOC (&iteration_obstack);
+ unsigned int i;
+ bitmap_iterator bi;
+
+ EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
+ {
+ varinfo_t vi = get_varinfo (i);
+
+ /* If this is a variable with just one field just set its bit
+ in the result. */
+ if (vi->is_artificial_var
+ || vi->is_unknown_size_var
+ || vi->is_full_var)
+ bitmap_set_bit (result, i);
+ else
+ {
+ unsigned HOST_WIDE_INT fieldoffset = vi->offset + offset;
+ varinfo_t v = first_vi_for_offset (vi, fieldoffset);
+ /* If the result is outside of the variable use the last field. */
+ if (!v)
+ {
+ v = vi;
+ while (v->next != NULL)
+ v = v->next;
+ }
+ bitmap_set_bit (result, v->id);
+ /* If the result is not exactly at fieldoffset include the next
+ field as well. See get_constraint_for_ptr_offset for more
+ rationale. */
+ if (v->offset != fieldoffset
+ && v->next != NULL)
+ bitmap_set_bit (result, v->next->id);
+ }
+ }
+
+ bitmap_copy (set, result);
+ BITMAP_FREE (result);
+}
+
+/* Union solution sets TO and FROM, and add INC to each member of FROM in the
+ process. */
+
+static bool
+set_union_with_increment (bitmap to, bitmap from, unsigned HOST_WIDE_INT inc)
+{
+ if (inc == 0)
+ return bitmap_ior_into (to, from);
+ else
+ {
+ bitmap tmp;
+ bool res;
+
+ tmp = BITMAP_ALLOC (&iteration_obstack);
+ bitmap_copy (tmp, from);
+ solution_set_add (tmp, inc);
+ res = bitmap_ior_into (to, tmp);
+ BITMAP_FREE (tmp);
+ return res;
+ }
+}
+
+/* Insert constraint C into the list of complex constraints for graph
+ node VAR. */
+
+static void
+insert_into_complex (constraint_graph_t graph,
+ unsigned int var, constraint_t c)
+{
+ VEC (constraint_t, heap) *complex = graph->complex[var];
+ unsigned int place = VEC_lower_bound (constraint_t, complex, c,
+ constraint_less);
+
+ /* Only insert constraints that do not already exist. */
+ if (place >= VEC_length (constraint_t, complex)
+ || !constraint_equal (*c, *VEC_index (constraint_t, complex, place)))
+ VEC_safe_insert (constraint_t, heap, graph->complex[var], place, c);
+}
+
+
+/* Condense two variable nodes into a single variable node, by moving
+ all associated info from SRC to TO. */
+
+static void
+merge_node_constraints (constraint_graph_t graph, unsigned int to,
+ unsigned int from)
+{
+ unsigned int i;
+ constraint_t c;
+
+ gcc_assert (find (from) == to);
+
+ /* Move all complex constraints from src node into to node */
+ for (i = 0; VEC_iterate (constraint_t, graph->complex[from], i, c); i++)
+ {
+ /* In complex constraints for node src, we may have either
+ a = *src, and *src = a, or an offseted constraint which are
+ always added to the rhs node's constraints. */
+
+ if (c->rhs.type == DEREF)
+ c->rhs.var = to;
+ else if (c->lhs.type == DEREF)
+ c->lhs.var = to;
+ else
+ c->rhs.var = to;
+ }
+ constraint_set_union (&graph->complex[to], &graph->complex[from]);
+ VEC_free (constraint_t, heap, graph->complex[from]);
+ graph->complex[from] = NULL;
+}
+
+
+/* Remove edges involving NODE from GRAPH. */
+
+static void
+clear_edges_for_node (constraint_graph_t graph, unsigned int node)
+{
+ if (graph->succs[node])
+ BITMAP_FREE (graph->succs[node]);
+}
+
+/* Merge GRAPH nodes FROM and TO into node TO. */
+
+static void
+merge_graph_nodes (constraint_graph_t graph, unsigned int to,
+ unsigned int from)
+{
+ if (graph->indirect_cycles[from] != -1)
+ {
+ /* If we have indirect cycles with the from node, and we have
+ none on the to node, the to node has indirect cycles from the
+ from node now that they are unified.
+ If indirect cycles exist on both, unify the nodes that they
+ are in a cycle with, since we know they are in a cycle with
+ each other. */
+ if (graph->indirect_cycles[to] == -1)
+ graph->indirect_cycles[to] = graph->indirect_cycles[from];
+ }
+
+ /* Merge all the successor edges. */
+ if (graph->succs[from])
+ {
+ if (!graph->succs[to])
+ graph->succs[to] = BITMAP_ALLOC (&pta_obstack);
+ bitmap_ior_into (graph->succs[to],
+ graph->succs[from]);
+ }
+
+ clear_edges_for_node (graph, from);
+}
+
+
+/* Add an indirect graph edge to GRAPH, going from TO to FROM if
+ it doesn't exist in the graph already. */
+
+static void
+add_implicit_graph_edge (constraint_graph_t graph, unsigned int to,
+ unsigned int from)
+{
+ if (to == from)
+ return;
+
+ if (!graph->implicit_preds[to])
+ graph->implicit_preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
+
+ if (bitmap_set_bit (graph->implicit_preds[to], from))
+ stats.num_implicit_edges++;
+}
+
+/* Add a predecessor graph edge to GRAPH, going from TO to FROM if
+ it doesn't exist in the graph already.
+ Return false if the edge already existed, true otherwise. */
+
+static void
+add_pred_graph_edge (constraint_graph_t graph, unsigned int to,
+ unsigned int from)
+{
+ if (!graph->preds[to])
+ graph->preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
+ bitmap_set_bit (graph->preds[to], from);
+}
+
+/* Add a graph edge to GRAPH, going from FROM to TO if
+ it doesn't exist in the graph already.
+ Return false if the edge already existed, true otherwise. */
+
+static bool
+add_graph_edge (constraint_graph_t graph, unsigned int to,
+ unsigned int from)
+{
+ if (to == from)
+ {
+ return false;
+ }
+ else
+ {
+ bool r = false;
+
+ if (!graph->succs[from])
+ graph->succs[from] = BITMAP_ALLOC (&pta_obstack);
+ if (bitmap_set_bit (graph->succs[from], to))
+ {
+ r = true;
+ if (to < FIRST_REF_NODE && from < FIRST_REF_NODE)
+ stats.num_edges++;
+ }
+ return r;
+ }
+}
+
+
+/* Return true if {DEST.SRC} is an existing graph edge in GRAPH. */
+
+static bool
+valid_graph_edge (constraint_graph_t graph, unsigned int src,
+ unsigned int dest)
+{
+ return (graph->succs[dest]
+ && bitmap_bit_p (graph->succs[dest], src));
+}
+
+/* Initialize the constraint graph structure to contain SIZE nodes. */
+
+static void
+init_graph (unsigned int size)
+{
+ unsigned int j;
+
+ graph = XCNEW (struct constraint_graph);
+ graph->size = size;
+ graph->succs = XCNEWVEC (bitmap, graph->size);
+ graph->indirect_cycles = XNEWVEC (int, graph->size);
+ graph->rep = XNEWVEC (unsigned int, graph->size);
+ graph->complex = XCNEWVEC (VEC(constraint_t, heap) *, size);
+ graph->pe = XCNEWVEC (unsigned int, graph->size);
+ graph->pe_rep = XNEWVEC (int, graph->size);
+
+ for (j = 0; j < graph->size; j++)
+ {
+ graph->rep[j] = j;
+ graph->pe_rep[j] = -1;
+ graph->indirect_cycles[j] = -1;
+ }
+}
+
+/* Build the constraint graph, adding only predecessor edges right now. */
+
+static void
+build_pred_graph (void)
+{
+ int i;
+ constraint_t c;
+ unsigned int j;
+
+ graph->implicit_preds = XCNEWVEC (bitmap, graph->size);
+ graph->preds = XCNEWVEC (bitmap, graph->size);
+ graph->pointer_label = XCNEWVEC (unsigned int, graph->size);
+ graph->loc_label = XCNEWVEC (unsigned int, graph->size);
+ graph->pointed_by = XCNEWVEC (bitmap, graph->size);
+ graph->points_to = XCNEWVEC (bitmap, graph->size);
+ graph->eq_rep = XNEWVEC (int, graph->size);
+ graph->direct_nodes = sbitmap_alloc (graph->size);
+ graph->address_taken = BITMAP_ALLOC (&predbitmap_obstack);
+ sbitmap_zero (graph->direct_nodes);
+
+ for (j = 0; j < FIRST_REF_NODE; j++)
+ {
+ if (!get_varinfo (j)->is_special_var)
+ SET_BIT (graph->direct_nodes, j);
+ }
+
+ for (j = 0; j < graph->size; j++)
+ graph->eq_rep[j] = -1;
+
+ for (j = 0; j < VEC_length (varinfo_t, varmap); j++)
+ graph->indirect_cycles[j] = -1;
+
+ for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
+ {
+ struct constraint_expr lhs = c->lhs;
+ struct constraint_expr rhs = c->rhs;
+ unsigned int lhsvar = get_varinfo_fc (lhs.var)->id;
+ unsigned int rhsvar = get_varinfo_fc (rhs.var)->id;
+
+ if (lhs.type == DEREF)
+ {
+ /* *x = y. */
+ if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
+ add_pred_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
+ }
+ else if (rhs.type == DEREF)
+ {
+ /* x = *y */
+ if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
+ add_pred_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
+ else
+ RESET_BIT (graph->direct_nodes, lhsvar);
+ }
+ else if (rhs.type == ADDRESSOF)
+ {
+ varinfo_t v;
+
+ /* x = &y */
+ if (graph->points_to[lhsvar] == NULL)
+ graph->points_to[lhsvar] = BITMAP_ALLOC (&predbitmap_obstack);
+ bitmap_set_bit (graph->points_to[lhsvar], rhsvar);
+
+ if (graph->pointed_by[rhsvar] == NULL)
+ graph->pointed_by[rhsvar] = BITMAP_ALLOC (&predbitmap_obstack);
+ bitmap_set_bit (graph->pointed_by[rhsvar], lhsvar);
+
+ /* Implicitly, *x = y */
+ add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
+
+ /* All related variables are no longer direct nodes. */
+ RESET_BIT (graph->direct_nodes, rhsvar);
+ v = get_varinfo (rhsvar);
+ if (!v->is_full_var)
+ {
+ v = lookup_vi_for_tree (v->decl);
+ do
+ {
+ RESET_BIT (graph->direct_nodes, v->id);
+ v = v->next;
+ }
+ while (v != NULL);
+ }
+ bitmap_set_bit (graph->address_taken, rhsvar);
+ }
+ else if (lhsvar > anything_id
+ && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
+ {
+ /* x = y */
+ add_pred_graph_edge (graph, lhsvar, rhsvar);
+ /* Implicitly, *x = *y */
+ add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar,
+ FIRST_REF_NODE + rhsvar);
+ }
+ else if (lhs.offset != 0 || rhs.offset != 0)
+ {
+ if (rhs.offset != 0)
+ RESET_BIT (graph->direct_nodes, lhs.var);
+ else if (lhs.offset != 0)
+ RESET_BIT (graph->direct_nodes, rhs.var);
+ }
+ }
+}
+
+/* Build the constraint graph, adding successor edges. */
+
+static void
+build_succ_graph (void)
+{
+ unsigned i, t;
+ constraint_t c;
+
+ for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
+ {
+ struct constraint_expr lhs;
+ struct constraint_expr rhs;
+ unsigned int lhsvar;
+ unsigned int rhsvar;
+
+ if (!c)
+ continue;
+
+ lhs = c->lhs;
+ rhs = c->rhs;
+ lhsvar = find (get_varinfo_fc (lhs.var)->id);
+ rhsvar = find (get_varinfo_fc (rhs.var)->id);
+
+ if (lhs.type == DEREF)
+ {
+ if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR)
+ add_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar);
+ }
+ else if (rhs.type == DEREF)
+ {
+ if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR)
+ add_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar);
+ }
+ else if (rhs.type == ADDRESSOF)
+ {
+ /* x = &y */
+ gcc_assert (find (get_varinfo_fc (rhs.var)->id)
+ == get_varinfo_fc (rhs.var)->id);
+ bitmap_set_bit (get_varinfo (lhsvar)->solution, rhsvar);
+ }
+ else if (lhsvar > anything_id
+ && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0)
+ {
+ add_graph_edge (graph, lhsvar, rhsvar);
+ }
+ }
+
+ /* Add edges from STOREDANYTHING to all non-direct nodes. */
+ t = find (storedanything_id);
+ for (i = integer_id + 1; i < FIRST_REF_NODE; ++i)
+ {
+ if (!TEST_BIT (graph->direct_nodes, i))
+ add_graph_edge (graph, find (i), t);
+ }
+}
+
+
+/* Changed variables on the last iteration. */
+static unsigned int changed_count;
+static sbitmap changed;
+
+DEF_VEC_I(unsigned);
+DEF_VEC_ALLOC_I(unsigned,heap);
+
+
+/* Strongly Connected Component visitation info. */
+
+struct scc_info
+{
+ sbitmap visited;
+ sbitmap deleted;
+ unsigned int *dfs;
+ unsigned int *node_mapping;
+ int current_index;
+ VEC(unsigned,heap) *scc_stack;
+};
+
+
+/* Recursive routine to find strongly connected components in GRAPH.
+ SI is the SCC info to store the information in, and N is the id of current
+ graph node we are processing.
+
+ This is Tarjan's strongly connected component finding algorithm, as
+ modified by Nuutila to keep only non-root nodes on the stack.
+ The algorithm can be found in "On finding the strongly connected
+ connected components in a directed graph" by Esko Nuutila and Eljas
+ Soisalon-Soininen, in Information Processing Letters volume 49,
+ number 1, pages 9-14. */
+
+static void
+scc_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
+{
+ unsigned int i;
+ bitmap_iterator bi;
+ unsigned int my_dfs;
+
+ SET_BIT (si->visited, n);
+ si->dfs[n] = si->current_index ++;
+ my_dfs = si->dfs[n];
+
+ /* Visit all the successors. */
+ EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[n], 0, i, bi)
+ {
+ unsigned int w;
+
+ if (i > LAST_REF_NODE)
+ break;
+
+ w = find (i);
+ if (TEST_BIT (si->deleted, w))
+ continue;
+
+ if (!TEST_BIT (si->visited, w))
+ scc_visit (graph, si, w);
+ {
+ unsigned int t = find (w);
+ unsigned int nnode = find (n);
+ gcc_assert (nnode == n);
+
+ if (si->dfs[t] < si->dfs[nnode])
+ si->dfs[n] = si->dfs[t];
+ }
+ }
+
+ /* See if any components have been identified. */
+ if (si->dfs[n] == my_dfs)
+ {
+ if (VEC_length (unsigned, si->scc_stack) > 0
+ && si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs)
+ {
+ bitmap scc = BITMAP_ALLOC (NULL);
+ bool have_ref_node = n >= FIRST_REF_NODE;
+ unsigned int lowest_node;
+ bitmap_iterator bi;
+
+ bitmap_set_bit (scc, n);
+
+ while (VEC_length (unsigned, si->scc_stack) != 0
+ && si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs)
+ {
+ unsigned int w = VEC_pop (unsigned, si->scc_stack);
+
+ bitmap_set_bit (scc, w);
+ if (w >= FIRST_REF_NODE)
+ have_ref_node = true;
+ }
+
+ lowest_node = bitmap_first_set_bit (scc);
+ gcc_assert (lowest_node < FIRST_REF_NODE);
+
+ /* Collapse the SCC nodes into a single node, and mark the
+ indirect cycles. */
+ EXECUTE_IF_SET_IN_BITMAP (scc, 0, i, bi)
+ {
+ if (i < FIRST_REF_NODE)
+ {
+ if (unite (lowest_node, i))
+ unify_nodes (graph, lowest_node, i, false);
+ }
+ else
+ {
+ unite (lowest_node, i);
+ graph->indirect_cycles[i - FIRST_REF_NODE] = lowest_node;
+ }
+ }
+ }
+ SET_BIT (si->deleted, n);
+ }
+ else
+ VEC_safe_push (unsigned, heap, si->scc_stack, n);
+}
+
+/* Unify node FROM into node TO, updating the changed count if
+ necessary when UPDATE_CHANGED is true. */
+
+static void
+unify_nodes (constraint_graph_t graph, unsigned int to, unsigned int from,
+ bool update_changed)
+{
+
+ gcc_assert (to != from && find (to) == to);
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Unifying %s to %s\n",
+ get_varinfo (from)->name,
+ get_varinfo (to)->name);
+
+ if (update_changed)
+ stats.unified_vars_dynamic++;
+ else
+ stats.unified_vars_static++;
+
+ merge_graph_nodes (graph, to, from);
+ merge_node_constraints (graph, to, from);
+
+ if (get_varinfo (from)->no_tbaa_pruning)
+ get_varinfo (to)->no_tbaa_pruning = true;
+
+ /* Mark TO as changed if FROM was changed. If TO was already marked
+ as changed, decrease the changed count. */
+
+ if (update_changed && TEST_BIT (changed, from))
+ {
+ RESET_BIT (changed, from);
+ if (!TEST_BIT (changed, to))
+ SET_BIT (changed, to);
+ else
+ {
+ gcc_assert (changed_count > 0);
+ changed_count--;
+ }
+ }
+ if (get_varinfo (from)->solution)
+ {
+ /* If the solution changes because of the merging, we need to mark
+ the variable as changed. */
+ if (bitmap_ior_into (get_varinfo (to)->solution,
+ get_varinfo (from)->solution))
+ {
+ if (update_changed && !TEST_BIT (changed, to))
+ {
+ SET_BIT (changed, to);
+ changed_count++;
+ }
+ }
+
+ BITMAP_FREE (get_varinfo (from)->solution);
+ BITMAP_FREE (get_varinfo (from)->oldsolution);
+
+ if (stats.iterations > 0)
+ {
+ BITMAP_FREE (get_varinfo (to)->oldsolution);
+ get_varinfo (to)->oldsolution = BITMAP_ALLOC (&oldpta_obstack);
+ }
+ }
+ if (valid_graph_edge (graph, to, to))
+ {
+ if (graph->succs[to])
+ bitmap_clear_bit (graph->succs[to], to);
+ }
+}
+
+/* Information needed to compute the topological ordering of a graph. */
+
+struct topo_info
+{
+ /* sbitmap of visited nodes. */
+ sbitmap visited;
+ /* Array that stores the topological order of the graph, *in
+ reverse*. */
+ VEC(unsigned,heap) *topo_order;
+};
+
+
+/* Initialize and return a topological info structure. */
+
+static struct topo_info *
+init_topo_info (void)
+{
+ size_t size = graph->size;
+ struct topo_info *ti = XNEW (struct topo_info);
+ ti->visited = sbitmap_alloc (size);
+ sbitmap_zero (ti->visited);
+ ti->topo_order = VEC_alloc (unsigned, heap, 1);
+ return ti;
+}
+
+
+/* Free the topological sort info pointed to by TI. */
+
+static void
+free_topo_info (struct topo_info *ti)
+{
+ sbitmap_free (ti->visited);
+ VEC_free (unsigned, heap, ti->topo_order);
+ free (ti);
+}
+
+/* Visit the graph in topological order, and store the order in the
+ topo_info structure. */
+
+static void
+topo_visit (constraint_graph_t graph, struct topo_info *ti,
+ unsigned int n)
+{
+ bitmap_iterator bi;
+ unsigned int j;
+
+ SET_BIT (ti->visited, n);
+
+ if (graph->succs[n])
+ EXECUTE_IF_SET_IN_BITMAP (graph->succs[n], 0, j, bi)
+ {
+ if (!TEST_BIT (ti->visited, j))
+ topo_visit (graph, ti, j);
+ }
+
+ VEC_safe_push (unsigned, heap, ti->topo_order, n);
+}
+
+/* Return true if variable N + OFFSET is a legal field of N. */
+
+static bool
+type_safe (unsigned int n, unsigned HOST_WIDE_INT *offset)
+{
+ varinfo_t ninfo = get_varinfo (n);
+
+ /* For things we've globbed to single variables, any offset into the
+ variable acts like the entire variable, so that it becomes offset
+ 0. */
+ if (ninfo->is_special_var
+ || ninfo->is_artificial_var
+ || ninfo->is_unknown_size_var
+ || ninfo->is_full_var)
+ {
+ *offset = 0;
+ return true;
+ }
+ return (get_varinfo (n)->offset + *offset) < get_varinfo (n)->fullsize;
+}
+
+/* Process a constraint C that represents x = *y, using DELTA as the
+ starting solution. */
+
+static void
+do_sd_constraint (constraint_graph_t graph, constraint_t c,
+ bitmap delta)
+{
+ unsigned int lhs = c->lhs.var;
+ bool flag = false;
+ bitmap sol = get_varinfo (lhs)->solution;
+ unsigned int j;
+ bitmap_iterator bi;
+
+ /* For x = *ESCAPED and x = *CALLUSED we want to compute the
+ reachability set of the rhs var. As a pointer to a sub-field
+ of a variable can also reach all other fields of the variable
+ we simply have to expand the solution to contain all sub-fields
+ if one sub-field is contained. */
+ if (c->rhs.var == find (escaped_id)
+ || c->rhs.var == find (callused_id))
+ {
+ bitmap vars = NULL;
+ /* In a first pass record all variables we need to add all
+ sub-fields off. This avoids quadratic behavior. */
+ EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
+ {
+ varinfo_t v = get_varinfo (j);
+ if (v->is_full_var)
+ continue;
+
+ v = lookup_vi_for_tree (v->decl);
+ if (v->next != NULL)
+ {
+ if (vars == NULL)
+ vars = BITMAP_ALLOC (NULL);
+ bitmap_set_bit (vars, v->id);
+ }
+ }
+ /* In the second pass now do the addition to the solution and
+ to speed up solving add it to the delta as well. */
+ if (vars != NULL)
+ {
+ EXECUTE_IF_SET_IN_BITMAP (vars, 0, j, bi)
+ {
+ varinfo_t v = get_varinfo (j);
+ for (; v != NULL; v = v->next)
+ {
+ if (bitmap_set_bit (sol, v->id))
+ {
+ flag = true;
+ bitmap_set_bit (delta, v->id);
+ }
+ }
+ }
+ BITMAP_FREE (vars);
+ }
+ }
+
+ if (bitmap_bit_p (delta, anything_id))
+ {
+ flag |= bitmap_set_bit (sol, anything_id);
+ goto done;
+ }
+
+ /* For each variable j in delta (Sol(y)), add
+ an edge in the graph from j to x, and union Sol(j) into Sol(x). */
+ EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
+ {
+ unsigned HOST_WIDE_INT roffset = c->rhs.offset;
+ if (type_safe (j, &roffset))
+ {
+ varinfo_t v;
+ unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + roffset;
+ unsigned int t;
+
+ v = first_vi_for_offset (get_varinfo (j), fieldoffset);
+ /* If the access is outside of the variable we can ignore it. */
+ if (!v)
+ continue;
+ t = find (v->id);
+
+ /* Adding edges from the special vars is pointless.
+ They don't have sets that can change. */
+ if (get_varinfo (t)->is_special_var)
+ flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
+ /* Merging the solution from ESCAPED needlessly increases
+ the set. Use ESCAPED as representative instead.
+ Same for CALLUSED. */
+ else if (get_varinfo (t)->id == find (escaped_id))
+ flag |= bitmap_set_bit (sol, escaped_id);
+ else if (get_varinfo (t)->id == find (callused_id))
+ flag |= bitmap_set_bit (sol, callused_id);
+ else if (add_graph_edge (graph, lhs, t))
+ flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
+ }
+ }
+
+done:
+ /* If the LHS solution changed, mark the var as changed. */
+ if (flag)
+ {
+ get_varinfo (lhs)->solution = sol;
+ if (!TEST_BIT (changed, lhs))
+ {
+ SET_BIT (changed, lhs);
+ changed_count++;
+ }
+ }
+}
+
+/* Process a constraint C that represents *x = y. */
+
+static void
+do_ds_constraint (constraint_t c, bitmap delta)
+{
+ unsigned int rhs = c->rhs.var;
+ bitmap sol = get_varinfo (rhs)->solution;
+ unsigned int j;
+ bitmap_iterator bi;
+
+ /* Our IL does not allow this. */
+ gcc_assert (c->rhs.offset == 0);
+
+ /* If the solution of y contains ANYTHING simply use the ANYTHING
+ solution. This avoids needlessly increasing the points-to sets. */
+ if (bitmap_bit_p (sol, anything_id))
+ sol = get_varinfo (find (anything_id))->solution;
+
+ /* If the solution for x contains ANYTHING we have to merge the
+ solution of y into all pointer variables which we do via
+ STOREDANYTHING. */
+ if (bitmap_bit_p (delta, anything_id))
+ {
+ unsigned t = find (storedanything_id);
+ if (add_graph_edge (graph, t, rhs))
+ {
+ if (bitmap_ior_into (get_varinfo (t)->solution, sol))
+ {
+ if (!TEST_BIT (changed, t))
+ {
+ SET_BIT (changed, t);
+ changed_count++;
+ }
+ }
+ }
+ return;
+ }
+
+ /* For each member j of delta (Sol(x)), add an edge from y to j and
+ union Sol(y) into Sol(j) */
+ EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
+ {
+ unsigned HOST_WIDE_INT loff = c->lhs.offset;
+ if (type_safe (j, &loff) && !(get_varinfo (j)->is_special_var))
+ {
+ varinfo_t v;
+ unsigned int t;
+ unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + loff;
+
+ v = first_vi_for_offset (get_varinfo (j), fieldoffset);
+ /* If the access is outside of the variable we can ignore it. */
+ if (!v)
+ continue;
+
+ if (v->may_have_pointers)
+ {
+ t = find (v->id);
+ if (add_graph_edge (graph, t, rhs))
+ {
+ if (bitmap_ior_into (get_varinfo (t)->solution, sol))
+ {
+ if (t == rhs)
+ sol = get_varinfo (rhs)->solution;
+ if (!TEST_BIT (changed, t))
+ {
+ SET_BIT (changed, t);
+ changed_count++;
+ }
+ }
+ }
+ }
+ }
+ }
+}
+
+/* Handle a non-simple (simple meaning requires no iteration),
+ constraint (IE *x = &y, x = *y, *x = y, and x = y with offsets involved). */
+
+static void
+do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta)
+{
+ if (c->lhs.type == DEREF)
+ {
+ if (c->rhs.type == ADDRESSOF)
+ {
+ gcc_unreachable();
+ }
+ else
+ {
+ /* *x = y */
+ do_ds_constraint (c, delta);
+ }
+ }
+ else if (c->rhs.type == DEREF)
+ {
+ /* x = *y */
+ if (!(get_varinfo (c->lhs.var)->is_special_var))
+ do_sd_constraint (graph, c, delta);
+ }
+ else
+ {
+ bitmap tmp;
+ bitmap solution;
+ bool flag = false;
+
+ gcc_assert (c->rhs.type == SCALAR && c->lhs.type == SCALAR);
+ solution = get_varinfo (c->rhs.var)->solution;
+ tmp = get_varinfo (c->lhs.var)->solution;
+
+ flag = set_union_with_increment (tmp, solution, c->rhs.offset);
+
+ if (flag)
+ {
+ get_varinfo (c->lhs.var)->solution = tmp;
+ if (!TEST_BIT (changed, c->lhs.var))
+ {
+ SET_BIT (changed, c->lhs.var);
+ changed_count++;
+ }
+ }
+ }
+}
+
+/* Initialize and return a new SCC info structure. */
+
+static struct scc_info *
+init_scc_info (size_t size)
+{
+ struct scc_info *si = XNEW (struct scc_info);
+ size_t i;
+
+ si->current_index = 0;
+ si->visited = sbitmap_alloc (size);
+ sbitmap_zero (si->visited);
+ si->deleted = sbitmap_alloc (size);
+ sbitmap_zero (si->deleted);
+ si->node_mapping = XNEWVEC (unsigned int, size);
+ si->dfs = XCNEWVEC (unsigned int, size);
+
+ for (i = 0; i < size; i++)
+ si->node_mapping[i] = i;
+
+ si->scc_stack = VEC_alloc (unsigned, heap, 1);
+ return si;
+}
+
+/* Free an SCC info structure pointed to by SI */
+
+static void
+free_scc_info (struct scc_info *si)
+{
+ sbitmap_free (si->visited);
+ sbitmap_free (si->deleted);
+ free (si->node_mapping);
+ free (si->dfs);
+ VEC_free (unsigned, heap, si->scc_stack);
+ free (si);
+}
+
+
+/* Find indirect cycles in GRAPH that occur, using strongly connected
+ components, and note them in the indirect cycles map.
+
+ This technique comes from Ben Hardekopf and Calvin Lin,
+ "It Pays to be Lazy: Fast and Accurate Pointer Analysis for Millions of
+ Lines of Code", submitted to PLDI 2007. */
+
+static void
+find_indirect_cycles (constraint_graph_t graph)
+{
+ unsigned int i;
+ unsigned int size = graph->size;
+ struct scc_info *si = init_scc_info (size);
+
+ for (i = 0; i < MIN (LAST_REF_NODE, size); i ++ )
+ if (!TEST_BIT (si->visited, i) && find (i) == i)
+ scc_visit (graph, si, i);
+
+ free_scc_info (si);
+}
+
+/* Compute a topological ordering for GRAPH, and store the result in the
+ topo_info structure TI. */
+
+static void
+compute_topo_order (constraint_graph_t graph,
+ struct topo_info *ti)
+{
+ unsigned int i;
+ unsigned int size = graph->size;
+
+ for (i = 0; i != size; ++i)
+ if (!TEST_BIT (ti->visited, i) && find (i) == i)
+ topo_visit (graph, ti, i);
+}
+
+/* Structure used to for hash value numbering of pointer equivalence
+ classes. */
+
+typedef struct equiv_class_label
+{
+ hashval_t hashcode;
+ unsigned int equivalence_class;
+ bitmap labels;
+} *equiv_class_label_t;
+typedef const struct equiv_class_label *const_equiv_class_label_t;
+
+/* A hashtable for mapping a bitmap of labels->pointer equivalence
+ classes. */
+static htab_t pointer_equiv_class_table;
+
+/* A hashtable for mapping a bitmap of labels->location equivalence
+ classes. */
+static htab_t location_equiv_class_table;
+
+/* Hash function for a equiv_class_label_t */
+
+static hashval_t
+equiv_class_label_hash (const void *p)
+{
+ const_equiv_class_label_t const ecl = (const_equiv_class_label_t) p;
+ return ecl->hashcode;
+}
+
+/* Equality function for two equiv_class_label_t's. */
+
+static int
+equiv_class_label_eq (const void *p1, const void *p2)
+{
+ const_equiv_class_label_t const eql1 = (const_equiv_class_label_t) p1;
+ const_equiv_class_label_t const eql2 = (const_equiv_class_label_t) p2;
+ return bitmap_equal_p (eql1->labels, eql2->labels);
+}
+
+/* Lookup a equivalence class in TABLE by the bitmap of LABELS it
+ contains. */
+
+static unsigned int
+equiv_class_lookup (htab_t table, bitmap labels)
+{
+ void **slot;
+ struct equiv_class_label ecl;
+
+ ecl.labels = labels;
+ ecl.hashcode = bitmap_hash (labels);
+
+ slot = htab_find_slot_with_hash (table, &ecl,
+ ecl.hashcode, NO_INSERT);
+ if (!slot)
+ return 0;
+ else
+ return ((equiv_class_label_t) *slot)->equivalence_class;
+}
+
+
+/* Add an equivalence class named EQUIVALENCE_CLASS with labels LABELS
+ to TABLE. */
+
+static void
+equiv_class_add (htab_t table, unsigned int equivalence_class,
+ bitmap labels)
+{
+ void **slot;
+ equiv_class_label_t ecl = XNEW (struct equiv_class_label);
+
+ ecl->labels = labels;
+ ecl->equivalence_class = equivalence_class;
+ ecl->hashcode = bitmap_hash (labels);
+
+ slot = htab_find_slot_with_hash (table, ecl,
+ ecl->hashcode, INSERT);
+ gcc_assert (!*slot);
+ *slot = (void *) ecl;
+}
+
+/* Perform offline variable substitution.
+
+ This is a worst case quadratic time way of identifying variables
+ that must have equivalent points-to sets, including those caused by
+ static cycles, and single entry subgraphs, in the constraint graph.
+
+ The technique is described in "Exploiting Pointer and Location
+ Equivalence to Optimize Pointer Analysis. In the 14th International
+ Static Analysis Symposium (SAS), August 2007." It is known as the
+ "HU" algorithm, and is equivalent to value numbering the collapsed
+ constraint graph including evaluating unions.
+
+ The general method of finding equivalence classes is as follows:
+ Add fake nodes (REF nodes) and edges for *a = b and a = *b constraints.
+ Initialize all non-REF nodes to be direct nodes.
+ For each constraint a = a U {b}, we set pts(a) = pts(a) u {fresh
+ variable}
+ For each constraint containing the dereference, we also do the same
+ thing.
+
+ We then compute SCC's in the graph and unify nodes in the same SCC,
+ including pts sets.
+
+ For each non-collapsed node x:
+ Visit all unvisited explicit incoming edges.
+ Ignoring all non-pointers, set pts(x) = Union of pts(a) for y
+ where y->x.
+ Lookup the equivalence class for pts(x).
+ If we found one, equivalence_class(x) = found class.
+ Otherwise, equivalence_class(x) = new class, and new_class is
+ added to the lookup table.
+
+ All direct nodes with the same equivalence class can be replaced
+ with a single representative node.
+ All unlabeled nodes (label == 0) are not pointers and all edges
+ involving them can be eliminated.
+ We perform these optimizations during rewrite_constraints
+
+ In addition to pointer equivalence class finding, we also perform
+ location equivalence class finding. This is the set of variables
+ that always appear together in points-to sets. We use this to
+ compress the size of the points-to sets. */
+
+/* Current maximum pointer equivalence class id. */
+static int pointer_equiv_class;
+
+/* Current maximum location equivalence class id. */
+static int location_equiv_class;
+
+/* Recursive routine to find strongly connected components in GRAPH,
+ and label it's nodes with DFS numbers. */
+
+static void
+condense_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
+{
+ unsigned int i;
+ bitmap_iterator bi;
+ unsigned int my_dfs;
+
+ gcc_assert (si->node_mapping[n] == n);
+ SET_BIT (si->visited, n);
+ si->dfs[n] = si->current_index ++;
+ my_dfs = si->dfs[n];
+
+ /* Visit all the successors. */
+ EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
+ {
+ unsigned int w = si->node_mapping[i];
+
+ if (TEST_BIT (si->deleted, w))
+ continue;
+
+ if (!TEST_BIT (si->visited, w))
+ condense_visit (graph, si, w);
+ {
+ unsigned int t = si->node_mapping[w];
+ unsigned int nnode = si->node_mapping[n];
+ gcc_assert (nnode == n);
+
+ if (si->dfs[t] < si->dfs[nnode])
+ si->dfs[n] = si->dfs[t];
+ }
+ }
+
+ /* Visit all the implicit predecessors. */
+ EXECUTE_IF_IN_NONNULL_BITMAP (graph->implicit_preds[n], 0, i, bi)
+ {
+ unsigned int w = si->node_mapping[i];
+
+ if (TEST_BIT (si->deleted, w))
+ continue;
+
+ if (!TEST_BIT (si->visited, w))
+ condense_visit (graph, si, w);
+ {
+ unsigned int t = si->node_mapping[w];
+ unsigned int nnode = si->node_mapping[n];
+ gcc_assert (nnode == n);
+
+ if (si->dfs[t] < si->dfs[nnode])
+ si->dfs[n] = si->dfs[t];
+ }
+ }
+
+ /* See if any components have been identified. */
+ if (si->dfs[n] == my_dfs)
+ {
+ while (VEC_length (unsigned, si->scc_stack) != 0
+ && si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs)
+ {
+ unsigned int w = VEC_pop (unsigned, si->scc_stack);
+ si->node_mapping[w] = n;
+
+ if (!TEST_BIT (graph->direct_nodes, w))
+ RESET_BIT (graph->direct_nodes, n);
+
+ /* Unify our nodes. */
+ if (graph->preds[w])
+ {
+ if (!graph->preds[n])
+ graph->preds[n] = BITMAP_ALLOC (&predbitmap_obstack);
+ bitmap_ior_into (graph->preds[n], graph->preds[w]);
+ }
+ if (graph->implicit_preds[w])
+ {
+ if (!graph->implicit_preds[n])
+ graph->implicit_preds[n] = BITMAP_ALLOC (&predbitmap_obstack);
+ bitmap_ior_into (graph->implicit_preds[n],
+ graph->implicit_preds[w]);
+ }
+ if (graph->points_to[w])
+ {
+ if (!graph->points_to[n])
+ graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
+ bitmap_ior_into (graph->points_to[n],
+ graph->points_to[w]);
+ }
+ }
+ SET_BIT (si->deleted, n);
+ }
+ else
+ VEC_safe_push (unsigned, heap, si->scc_stack, n);
+}
+
+/* Label pointer equivalences. */
+
+static void
+label_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
+{
+ unsigned int i;
+ bitmap_iterator bi;
+ SET_BIT (si->visited, n);
+
+ if (!graph->points_to[n])
+ graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
+
+ /* Label and union our incoming edges's points to sets. */
+ EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
+ {
+ unsigned int w = si->node_mapping[i];
+ if (!TEST_BIT (si->visited, w))
+ label_visit (graph, si, w);
+
+ /* Skip unused edges */
+ if (w == n || graph->pointer_label[w] == 0)
+ continue;
+
+ if (graph->points_to[w])
+ bitmap_ior_into(graph->points_to[n], graph->points_to[w]);
+ }
+ /* Indirect nodes get fresh variables. */
+ if (!TEST_BIT (graph->direct_nodes, n))
+ bitmap_set_bit (graph->points_to[n], FIRST_REF_NODE + n);
+
+ if (!bitmap_empty_p (graph->points_to[n]))
+ {
+ unsigned int label = equiv_class_lookup (pointer_equiv_class_table,
+ graph->points_to[n]);
+ if (!label)
+ {
+ label = pointer_equiv_class++;
+ equiv_class_add (pointer_equiv_class_table,
+ label, graph->points_to[n]);
+ }
+ graph->pointer_label[n] = label;
+ }
+}
+
+/* Perform offline variable substitution, discovering equivalence
+ classes, and eliminating non-pointer variables. */
+
+static struct scc_info *
+perform_var_substitution (constraint_graph_t graph)
+{
+ unsigned int i;
+ unsigned int size = graph->size;
+ struct scc_info *si = init_scc_info (size);
+
+ bitmap_obstack_initialize (&iteration_obstack);
+ pointer_equiv_class_table = htab_create (511, equiv_class_label_hash,
+ equiv_class_label_eq, free);
+ location_equiv_class_table = htab_create (511, equiv_class_label_hash,
+ equiv_class_label_eq, free);
+ pointer_equiv_class = 1;
+ location_equiv_class = 1;
+
+ /* Condense the nodes, which means to find SCC's, count incoming
+ predecessors, and unite nodes in SCC's. */
+ for (i = 0; i < FIRST_REF_NODE; i++)
+ if (!TEST_BIT (si->visited, si->node_mapping[i]))
+ condense_visit (graph, si, si->node_mapping[i]);
+
+ sbitmap_zero (si->visited);
+ /* Actually the label the nodes for pointer equivalences */
+ for (i = 0; i < FIRST_REF_NODE; i++)
+ if (!TEST_BIT (si->visited, si->node_mapping[i]))
+ label_visit (graph, si, si->node_mapping[i]);
+
+ /* Calculate location equivalence labels. */
+ for (i = 0; i < FIRST_REF_NODE; i++)
+ {
+ bitmap pointed_by;
+ bitmap_iterator bi;
+ unsigned int j;
+ unsigned int label;
+
+ if (!graph->pointed_by[i])
+ continue;
+ pointed_by = BITMAP_ALLOC (&iteration_obstack);
+
+ /* Translate the pointed-by mapping for pointer equivalence
+ labels. */
+ EXECUTE_IF_SET_IN_BITMAP (graph->pointed_by[i], 0, j, bi)
+ {
+ bitmap_set_bit (pointed_by,
+ graph->pointer_label[si->node_mapping[j]]);
+ }
+ /* The original pointed_by is now dead. */
+ BITMAP_FREE (graph->pointed_by[i]);
+
+ /* Look up the location equivalence label if one exists, or make
+ one otherwise. */
+ label = equiv_class_lookup (location_equiv_class_table,
+ pointed_by);
+ if (label == 0)
+ {
+ label = location_equiv_class++;
+ equiv_class_add (location_equiv_class_table,
+ label, pointed_by);
+ }
+ else
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Found location equivalence for node %s\n",
+ get_varinfo (i)->name);
+ BITMAP_FREE (pointed_by);
+ }
+ graph->loc_label[i] = label;
+
+ }
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ for (i = 0; i < FIRST_REF_NODE; i++)
+ {
+ bool direct_node = TEST_BIT (graph->direct_nodes, i);
+ fprintf (dump_file,
+ "Equivalence classes for %s node id %d:%s are pointer: %d"
+ ", location:%d\n",
+ direct_node ? "Direct node" : "Indirect node", i,
+ get_varinfo (i)->name,
+ graph->pointer_label[si->node_mapping[i]],
+ graph->loc_label[si->node_mapping[i]]);
+ }
+
+ /* Quickly eliminate our non-pointer variables. */
+
+ for (i = 0; i < FIRST_REF_NODE; i++)
+ {
+ unsigned int node = si->node_mapping[i];
+
+ if (graph->pointer_label[node] == 0)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file,
+ "%s is a non-pointer variable, eliminating edges.\n",
+ get_varinfo (node)->name);
+ stats.nonpointer_vars++;
+ clear_edges_for_node (graph, node);
+ }
+ }
+
+ return si;
+}
+
+/* Free information that was only necessary for variable
+ substitution. */
+
+static void
+free_var_substitution_info (struct scc_info *si)
+{
+ free_scc_info (si);
+ free (graph->pointer_label);
+ free (graph->loc_label);
+ free (graph->pointed_by);
+ free (graph->points_to);
+ free (graph->eq_rep);
+ sbitmap_free (graph->direct_nodes);
+ htab_delete (pointer_equiv_class_table);
+ htab_delete (location_equiv_class_table);
+ bitmap_obstack_release (&iteration_obstack);
+}
+
+/* Return an existing node that is equivalent to NODE, which has
+ equivalence class LABEL, if one exists. Return NODE otherwise. */
+
+static unsigned int
+find_equivalent_node (constraint_graph_t graph,
+ unsigned int node, unsigned int label)
+{
+ /* If the address version of this variable is unused, we can
+ substitute it for anything else with the same label.
+ Otherwise, we know the pointers are equivalent, but not the
+ locations, and we can unite them later. */
+
+ if (!bitmap_bit_p (graph->address_taken, node))
+ {
+ gcc_assert (label < graph->size);
+
+ if (graph->eq_rep[label] != -1)
+ {
+ /* Unify the two variables since we know they are equivalent. */
+ if (unite (graph->eq_rep[label], node))
+ unify_nodes (graph, graph->eq_rep[label], node, false);
+ return graph->eq_rep[label];
+ }
+ else
+ {
+ graph->eq_rep[label] = node;
+ graph->pe_rep[label] = node;
+ }
+ }
+ else
+ {
+ gcc_assert (label < graph->size);
+ graph->pe[node] = label;
+ if (graph->pe_rep[label] == -1)
+ graph->pe_rep[label] = node;
+ }
+
+ return node;
+}
+
+/* Unite pointer equivalent but not location equivalent nodes in
+ GRAPH. This may only be performed once variable substitution is
+ finished. */
+
+static void
+unite_pointer_equivalences (constraint_graph_t graph)
+{
+ unsigned int i;
+
+ /* Go through the pointer equivalences and unite them to their
+ representative, if they aren't already. */
+ for (i = 0; i < FIRST_REF_NODE; i++)
+ {
+ unsigned int label = graph->pe[i];
+ if (label)
+ {
+ int label_rep = graph->pe_rep[label];
+
+ if (label_rep == -1)
+ continue;
+
+ label_rep = find (label_rep);
+ if (label_rep >= 0 && unite (label_rep, find (i)))
+ unify_nodes (graph, label_rep, i, false);
+ }
+ }
+}
+
+/* Move complex constraints to the GRAPH nodes they belong to. */
+
+static void
+move_complex_constraints (constraint_graph_t graph)
+{
+ int i;
+ constraint_t c;
+
+ for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
+ {
+ if (c)
+ {
+ struct constraint_expr lhs = c->lhs;
+ struct constraint_expr rhs = c->rhs;
+
+ if (lhs.type == DEREF)
+ {
+ insert_into_complex (graph, lhs.var, c);
+ }
+ else if (rhs.type == DEREF)
+ {
+ if (!(get_varinfo (lhs.var)->is_special_var))
+ insert_into_complex (graph, rhs.var, c);
+ }
+ else if (rhs.type != ADDRESSOF && lhs.var > anything_id
+ && (lhs.offset != 0 || rhs.offset != 0))
+ {
+ insert_into_complex (graph, rhs.var, c);
+ }
+ }
+ }
+}
+
+
+/* Optimize and rewrite complex constraints while performing
+ collapsing of equivalent nodes. SI is the SCC_INFO that is the
+ result of perform_variable_substitution. */
+
+static void
+rewrite_constraints (constraint_graph_t graph,
+ struct scc_info *si)
+{
+ int i;
+ unsigned int j;
+ constraint_t c;
+
+ for (j = 0; j < graph->size; j++)
+ gcc_assert (find (j) == j);
+
+ for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
+ {
+ struct constraint_expr lhs = c->lhs;
+ struct constraint_expr rhs = c->rhs;
+ unsigned int lhsvar = find (get_varinfo_fc (lhs.var)->id);
+ unsigned int rhsvar = find (get_varinfo_fc (rhs.var)->id);
+ unsigned int lhsnode, rhsnode;
+ unsigned int lhslabel, rhslabel;
+
+ lhsnode = si->node_mapping[lhsvar];
+ rhsnode = si->node_mapping[rhsvar];
+ lhslabel = graph->pointer_label[lhsnode];
+ rhslabel = graph->pointer_label[rhsnode];
+
+ /* See if it is really a non-pointer variable, and if so, ignore
+ the constraint. */
+ if (lhslabel == 0)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+
+ fprintf (dump_file, "%s is a non-pointer variable,"
+ "ignoring constraint:",
+ get_varinfo (lhs.var)->name);
+ dump_constraint (dump_file, c);
+ }
+ VEC_replace (constraint_t, constraints, i, NULL);
+ continue;
+ }
+
+ if (rhslabel == 0)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+
+ fprintf (dump_file, "%s is a non-pointer variable,"
+ "ignoring constraint:",
+ get_varinfo (rhs.var)->name);
+ dump_constraint (dump_file, c);
+ }
+ VEC_replace (constraint_t, constraints, i, NULL);
+ continue;
+ }
+
+ lhsvar = find_equivalent_node (graph, lhsvar, lhslabel);
+ rhsvar = find_equivalent_node (graph, rhsvar, rhslabel);
+ c->lhs.var = lhsvar;
+ c->rhs.var = rhsvar;
+
+ }
+}
+
+/* Eliminate indirect cycles involving NODE. Return true if NODE was
+ part of an SCC, false otherwise. */
+
+static bool
+eliminate_indirect_cycles (unsigned int node)
+{
+ if (graph->indirect_cycles[node] != -1
+ && !bitmap_empty_p (get_varinfo (node)->solution))
+ {
+ unsigned int i;
+ VEC(unsigned,heap) *queue = NULL;
+ int queuepos;
+ unsigned int to = find (graph->indirect_cycles[node]);
+ bitmap_iterator bi;
+
+ /* We can't touch the solution set and call unify_nodes
+ at the same time, because unify_nodes is going to do
+ bitmap unions into it. */
+
+ EXECUTE_IF_SET_IN_BITMAP (get_varinfo (node)->solution, 0, i, bi)
+ {
+ if (find (i) == i && i != to)
+ {
+ if (unite (to, i))
+ VEC_safe_push (unsigned, heap, queue, i);
+ }
+ }
+
+ for (queuepos = 0;
+ VEC_iterate (unsigned, queue, queuepos, i);
+ queuepos++)
+ {
+ unify_nodes (graph, to, i, true);
+ }
+ VEC_free (unsigned, heap, queue);
+ return true;
+ }
+ return false;
+}
+
+/* Solve the constraint graph GRAPH using our worklist solver.
+ This is based on the PW* family of solvers from the "Efficient Field
+ Sensitive Pointer Analysis for C" paper.
+ It works by iterating over all the graph nodes, processing the complex
+ constraints and propagating the copy constraints, until everything stops
+ changed. This corresponds to steps 6-8 in the solving list given above. */
+
+static void
+solve_graph (constraint_graph_t graph)
+{
+ unsigned int size = graph->size;
+ unsigned int i;
+ bitmap pts;
+
+ changed_count = 0;
+ changed = sbitmap_alloc (size);
+ sbitmap_zero (changed);
+
+ /* Mark all initial non-collapsed nodes as changed. */
+ for (i = 0; i < size; i++)
+ {
+ varinfo_t ivi = get_varinfo (i);
+ if (find (i) == i && !bitmap_empty_p (ivi->solution)
+ && ((graph->succs[i] && !bitmap_empty_p (graph->succs[i]))
+ || VEC_length (constraint_t, graph->complex[i]) > 0))
+ {
+ SET_BIT (changed, i);
+ changed_count++;
+ }
+ }
+
+ /* Allocate a bitmap to be used to store the changed bits. */
+ pts = BITMAP_ALLOC (&pta_obstack);
+
+ while (changed_count > 0)
+ {
+ unsigned int i;
+ struct topo_info *ti = init_topo_info ();
+ stats.iterations++;
+
+ bitmap_obstack_initialize (&iteration_obstack);
+
+ compute_topo_order (graph, ti);
+
+ while (VEC_length (unsigned, ti->topo_order) != 0)
+ {
+
+ i = VEC_pop (unsigned, ti->topo_order);
+
+ /* If this variable is not a representative, skip it. */
+ if (find (i) != i)
+ continue;
+
+ /* In certain indirect cycle cases, we may merge this
+ variable to another. */
+ if (eliminate_indirect_cycles (i) && find (i) != i)
+ continue;
+
+ /* If the node has changed, we need to process the
+ complex constraints and outgoing edges again. */
+ if (TEST_BIT (changed, i))
+ {
+ unsigned int j;
+ constraint_t c;
+ bitmap solution;
+ VEC(constraint_t,heap) *complex = graph->complex[i];
+ bool solution_empty;
+
+ RESET_BIT (changed, i);
+ changed_count--;
+
+ /* Compute the changed set of solution bits. */
+ bitmap_and_compl (pts, get_varinfo (i)->solution,
+ get_varinfo (i)->oldsolution);
+
+ if (bitmap_empty_p (pts))
+ continue;
+
+ bitmap_ior_into (get_varinfo (i)->oldsolution, pts);
+
+ solution = get_varinfo (i)->solution;
+ solution_empty = bitmap_empty_p (solution);
+
+ /* Process the complex constraints */
+ for (j = 0; VEC_iterate (constraint_t, complex, j, c); j++)
+ {
+ /* XXX: This is going to unsort the constraints in
+ some cases, which will occasionally add duplicate
+ constraints during unification. This does not
+ affect correctness. */
+ c->lhs.var = find (c->lhs.var);
+ c->rhs.var = find (c->rhs.var);
+
+ /* The only complex constraint that can change our
+ solution to non-empty, given an empty solution,
+ is a constraint where the lhs side is receiving
+ some set from elsewhere. */
+ if (!solution_empty || c->lhs.type != DEREF)
+ do_complex_constraint (graph, c, pts);
+ }
+
+ solution_empty = bitmap_empty_p (solution);
+
+ if (!solution_empty
+ /* Do not propagate the ESCAPED/CALLUSED solutions. */
+ && i != find (escaped_id)
+ && i != find (callused_id))
+ {
+ bitmap_iterator bi;
+
+ /* Propagate solution to all successors. */
+ EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i],
+ 0, j, bi)
+ {
+ bitmap tmp;
+ bool flag;
+
+ unsigned int to = find (j);
+ tmp = get_varinfo (to)->solution;
+ flag = false;
+
+ /* Don't try to propagate to ourselves. */
+ if (to == i)
+ continue;
+
+ flag = set_union_with_increment (tmp, pts, 0);
+
+ if (flag)
+ {
+ get_varinfo (to)->solution = tmp;
+ if (!TEST_BIT (changed, to))
+ {
+ SET_BIT (changed, to);
+ changed_count++;
+ }
+ }
+ }
+ }
+ }
+ }
+ free_topo_info (ti);
+ bitmap_obstack_release (&iteration_obstack);
+ }
+
+ BITMAP_FREE (pts);
+ sbitmap_free (changed);
+ bitmap_obstack_release (&oldpta_obstack);
+}
+
+/* Map from trees to variable infos. */
+static struct pointer_map_t *vi_for_tree;
+
+
+/* Insert ID as the variable id for tree T in the vi_for_tree map. */
+
+static void
+insert_vi_for_tree (tree t, varinfo_t vi)
+{
+ void **slot = pointer_map_insert (vi_for_tree, t);
+ gcc_assert (vi);
+ gcc_assert (*slot == NULL);
+ *slot = vi;
+}
+
+/* Find the variable info for tree T in VI_FOR_TREE. If T does not
+ exist in the map, return NULL, otherwise, return the varinfo we found. */
+
+static varinfo_t
+lookup_vi_for_tree (tree t)
+{
+ void **slot = pointer_map_contains (vi_for_tree, t);
+ if (slot == NULL)
+ return NULL;
+
+ return (varinfo_t) *slot;
+}
+
+/* Return a printable name for DECL */
+
+static const char *
+alias_get_name (tree decl)
+{
+ const char *res = get_name (decl);
+ char *temp;
+ int num_printed = 0;
+
+ if (res != NULL)
+ return res;
+
+ res = "NULL";
+ if (!dump_file)
+ return res;
+
+ if (TREE_CODE (decl) == SSA_NAME)
+ {
+ num_printed = asprintf (&temp, "%s_%u",
+ alias_get_name (SSA_NAME_VAR (decl)),
+ SSA_NAME_VERSION (decl));
+ }
+ else if (DECL_P (decl))
+ {
+ num_printed = asprintf (&temp, "D.%u", DECL_UID (decl));
+ }
+ if (num_printed > 0)
+ {
+ res = ggc_strdup (temp);
+ free (temp);
+ }
+ return res;
+}
+
+/* Find the variable id for tree T in the map.
+ If T doesn't exist in the map, create an entry for it and return it. */
+
+static varinfo_t
+get_vi_for_tree (tree t)
+{
+ void **slot = pointer_map_contains (vi_for_tree, t);
+ if (slot == NULL)
+ return get_varinfo (create_variable_info_for (t, alias_get_name (t)));
+
+ return (varinfo_t) *slot;
+}
+
+/* Get a constraint expression for a new temporary variable. */
+
+static struct constraint_expr
+get_constraint_exp_for_temp (tree t)
+{
+ struct constraint_expr cexpr;
+
+ gcc_assert (SSA_VAR_P (t));
+
+ cexpr.type = SCALAR;
+ cexpr.var = get_vi_for_tree (t)->id;
+ cexpr.offset = 0;
+
+ return cexpr;
+}
+
+/* Get a constraint expression vector from an SSA_VAR_P node.
+ If address_p is true, the result will be taken its address of. */
+
+static void
+get_constraint_for_ssa_var (tree t, VEC(ce_s, heap) **results, bool address_p)
+{
+ struct constraint_expr cexpr;
+ varinfo_t vi;
+
+ /* We allow FUNCTION_DECLs here even though it doesn't make much sense. */
+ gcc_assert (SSA_VAR_P (t) || DECL_P (t));
+
+ /* For parameters, get at the points-to set for the actual parm
+ decl. */
+ if (TREE_CODE (t) == SSA_NAME
+ && TREE_CODE (SSA_NAME_VAR (t)) == PARM_DECL
+ && SSA_NAME_IS_DEFAULT_DEF (t))
+ {
+ get_constraint_for_ssa_var (SSA_NAME_VAR (t), results, address_p);
+ return;
+ }
+
+ vi = get_vi_for_tree (t);
+ cexpr.var = vi->id;
+ cexpr.type = SCALAR;
+ cexpr.offset = 0;
+ /* If we determine the result is "anything", and we know this is readonly,
+ say it points to readonly memory instead. */
+ if (cexpr.var == anything_id && TREE_READONLY (t))
+ {
+ gcc_unreachable ();
+ cexpr.type = ADDRESSOF;
+ cexpr.var = readonly_id;
+ }
+
+ /* If we are not taking the address of the constraint expr, add all
+ sub-fiels of the variable as well. */
+ if (!address_p)
+ {
+ for (; vi; vi = vi->next)
+ {
+ cexpr.var = vi->id;
+ VEC_safe_push (ce_s, heap, *results, &cexpr);
+ }
+ return;
+ }
+
+ VEC_safe_push (ce_s, heap, *results, &cexpr);
+}
+
+/* Process constraint T, performing various simplifications and then
+ adding it to our list of overall constraints. */
+
+static void
+process_constraint (constraint_t t)
+{
+ struct constraint_expr rhs = t->rhs;
+ struct constraint_expr lhs = t->lhs;
+
+ gcc_assert (rhs.var < VEC_length (varinfo_t, varmap));
+ gcc_assert (lhs.var < VEC_length (varinfo_t, varmap));
+
+ /* ANYTHING == ANYTHING is pointless. */
+ if (lhs.var == anything_id && rhs.var == anything_id)
+ return;
+
+ /* If we have &ANYTHING = something, convert to SOMETHING = &ANYTHING) */
+ else if (lhs.var == anything_id && lhs.type == ADDRESSOF)
+ {
+ rhs = t->lhs;
+ t->lhs = t->rhs;
+ t->rhs = rhs;
+ process_constraint (t);
+ }
+ /* This can happen in our IR with things like n->a = *p */
+ else if (rhs.type == DEREF && lhs.type == DEREF && rhs.var != anything_id)
+ {
+ /* Split into tmp = *rhs, *lhs = tmp */
+ tree rhsdecl = get_varinfo (rhs.var)->decl;
+ tree pointertype = TREE_TYPE (rhsdecl);
+ tree pointedtotype = TREE_TYPE (pointertype);
+ tree tmpvar = create_tmp_var_raw (pointedtotype, "doubledereftmp");
+ struct constraint_expr tmplhs = get_constraint_exp_for_temp (tmpvar);
+
+ process_constraint (new_constraint (tmplhs, rhs));
+ process_constraint (new_constraint (lhs, tmplhs));
+ }
+ else if (rhs.type == ADDRESSOF && lhs.type == DEREF)
+ {
+ /* Split into tmp = &rhs, *lhs = tmp */
+ tree rhsdecl = get_varinfo (rhs.var)->decl;
+ tree pointertype = TREE_TYPE (rhsdecl);
+ tree tmpvar = create_tmp_var_raw (pointertype, "derefaddrtmp");
+ struct constraint_expr tmplhs = get_constraint_exp_for_temp (tmpvar);
+
+ process_constraint (new_constraint (tmplhs, rhs));
+ process_constraint (new_constraint (lhs, tmplhs));
+ }
+ else
+ {
+ gcc_assert (rhs.type != ADDRESSOF || rhs.offset == 0);
+ VEC_safe_push (constraint_t, heap, constraints, t);
+ }
+}
+
+/* Return true if T is a type that could contain pointers. */
+
+static bool
+type_could_have_pointers (tree type)
+{
+ if (POINTER_TYPE_P (type))
+ return true;
+
+ if (TREE_CODE (type) == ARRAY_TYPE)
+ return type_could_have_pointers (TREE_TYPE (type));
+
+ return AGGREGATE_TYPE_P (type);
+}
+
+/* Return true if T is a variable of a type that could contain
+ pointers. */
+
+static bool
+could_have_pointers (tree t)
+{
+ return type_could_have_pointers (TREE_TYPE (t));
+}
+
+/* Return the position, in bits, of FIELD_DECL from the beginning of its
+ structure. */
+
+static HOST_WIDE_INT
+bitpos_of_field (const tree fdecl)
+{
+
+ if (!host_integerp (DECL_FIELD_OFFSET (fdecl), 0)
+ || !host_integerp (DECL_FIELD_BIT_OFFSET (fdecl), 0))
+ return -1;
+
+ return (TREE_INT_CST_LOW (DECL_FIELD_OFFSET (fdecl)) * 8
+ + TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (fdecl)));
+}
+
+
+/* Get constraint expressions for offsetting PTR by OFFSET. Stores the
+ resulting constraint expressions in *RESULTS. */
+
+static void
+get_constraint_for_ptr_offset (tree ptr, tree offset,
+ VEC (ce_s, heap) **results)
+{
+ struct constraint_expr c;
+ unsigned int j, n;
+ unsigned HOST_WIDE_INT rhsunitoffset, rhsoffset;
+
+ /* If we do not do field-sensitive PTA adding offsets to pointers
+ does not change the points-to solution. */
+ if (!use_field_sensitive)
+ {
+ get_constraint_for (ptr, results);
+ return;
+ }
+
+ /* If the offset is not a non-negative integer constant that fits
+ in a HOST_WIDE_INT, we have to fall back to a conservative
+ solution which includes all sub-fields of all pointed-to
+ variables of ptr.
+ ??? As we do not have the ability to express this, fall back
+ to anything. */
+ if (!host_integerp (offset, 1))
+ {
+ struct constraint_expr temp;
+ temp.var = anything_id;
+ temp.type = SCALAR;
+ temp.offset = 0;
+ VEC_safe_push (ce_s, heap, *results, &temp);
+ return;
+ }
+
+ /* Make sure the bit-offset also fits. */
+ rhsunitoffset = TREE_INT_CST_LOW (offset);
+ rhsoffset = rhsunitoffset * BITS_PER_UNIT;
+ if (rhsunitoffset != rhsoffset / BITS_PER_UNIT)
+ {
+ struct constraint_expr temp;
+ temp.var = anything_id;
+ temp.type = SCALAR;
+ temp.offset = 0;
+ VEC_safe_push (ce_s, heap, *results, &temp);
+ return;
+ }
+
+ get_constraint_for (ptr, results);
+ if (rhsoffset == 0)
+ return;
+
+ /* As we are eventually appending to the solution do not use
+ VEC_iterate here. */
+ n = VEC_length (ce_s, *results);
+ for (j = 0; j < n; j++)
+ {
+ varinfo_t curr;
+ c = *VEC_index (ce_s, *results, j);
+ curr = get_varinfo (c.var);
+
+ if (c.type == ADDRESSOF
+ && !curr->is_full_var)
+ {
+ varinfo_t temp, curr = get_varinfo (c.var);
+
+ /* Search the sub-field which overlaps with the
+ pointed-to offset. As we deal with positive offsets
+ only, we can start the search from the current variable. */
+ temp = first_vi_for_offset (curr, curr->offset + rhsoffset);
+
+ /* If the result is outside of the variable we have to provide
+ a conservative result, as the variable is still reachable
+ from the resulting pointer (even though it technically
+ cannot point to anything). The last sub-field is such
+ a conservative result.
+ ??? If we always had a sub-field for &object + 1 then
+ we could represent this in a more precise way. */
+ if (temp == NULL)
+ {
+ temp = curr;
+ while (temp->next != NULL)
+ temp = temp->next;
+ continue;
+ }
+
+ /* If the found variable is not exactly at the pointed to
+ result, we have to include the next variable in the
+ solution as well. Otherwise two increments by offset / 2
+ do not result in the same or a conservative superset
+ solution. */
+ if (temp->offset != curr->offset + rhsoffset
+ && temp->next != NULL)
+ {
+ struct constraint_expr c2;
+ c2.var = temp->next->id;
+ c2.type = ADDRESSOF;
+ c2.offset = 0;
+ VEC_safe_push (ce_s, heap, *results, &c2);
+ }
+ c.var = temp->id;
+ c.offset = 0;
+ }
+ else if (c.type == ADDRESSOF
+ /* If this varinfo represents a full variable just use it. */
+ && curr->is_full_var)
+ c.offset = 0;
+ else
+ c.offset = rhsoffset;
+
+ VEC_replace (ce_s, *results, j, &c);
+ }
+}
+
+
+/* Given a COMPONENT_REF T, return the constraint_expr vector for it.
+ If address_p is true the result will be taken its address of. */
+
+static void
+get_constraint_for_component_ref (tree t, VEC(ce_s, heap) **results,
+ bool address_p)
+{
+ tree orig_t = t;
+ HOST_WIDE_INT bitsize = -1;
+ HOST_WIDE_INT bitmaxsize = -1;
+ HOST_WIDE_INT bitpos;
+ tree forzero;
+ struct constraint_expr *result;
+
+ /* Some people like to do cute things like take the address of
+ &0->a.b */
+ forzero = t;
+ while (!SSA_VAR_P (forzero) && !CONSTANT_CLASS_P (forzero))
+ forzero = TREE_OPERAND (forzero, 0);
+
+ if (CONSTANT_CLASS_P (forzero) && integer_zerop (forzero))
+ {
+ struct constraint_expr temp;
+
+ temp.offset = 0;
+ temp.var = integer_id;
+ temp.type = SCALAR;
+ VEC_safe_push (ce_s, heap, *results, &temp);
+ return;
+ }
+
+ t = get_ref_base_and_extent (t, &bitpos, &bitsize, &bitmaxsize);
+
+ /* Pretend to take the address of the base, we'll take care of
+ adding the required subset of sub-fields below. */
+ get_constraint_for_1 (t, results, true);
+ gcc_assert (VEC_length (ce_s, *results) == 1);
+ result = VEC_last (ce_s, *results);
+
+ /* This can also happen due to weird offsetof type macros. */
+ if (TREE_CODE (t) != ADDR_EXPR && result->type == ADDRESSOF)
+ result->type = SCALAR;
+
+ if (result->type == SCALAR
+ && get_varinfo (result->var)->is_full_var)
+ /* For single-field vars do not bother about the offset. */
+ result->offset = 0;
+ else if (result->type == SCALAR)
+ {
+ /* In languages like C, you can access one past the end of an
+ array. You aren't allowed to dereference it, so we can
+ ignore this constraint. When we handle pointer subtraction,
+ we may have to do something cute here. */
+
+ if ((unsigned HOST_WIDE_INT)bitpos < get_varinfo (result->var)->fullsize
+ && bitmaxsize != 0)
+ {
+ /* It's also not true that the constraint will actually start at the
+ right offset, it may start in some padding. We only care about
+ setting the constraint to the first actual field it touches, so
+ walk to find it. */
+ struct constraint_expr cexpr = *result;
+ varinfo_t curr;
+ VEC_pop (ce_s, *results);
+ cexpr.offset = 0;
+ for (curr = get_varinfo (cexpr.var); curr; curr = curr->next)
+ {
+ if (ranges_overlap_p (curr->offset, curr->size,
+ bitpos, bitmaxsize))
+ {
+ cexpr.var = curr->id;
+ VEC_safe_push (ce_s, heap, *results, &cexpr);
+ if (address_p)
+ break;
+ }
+ }
+ /* If we are going to take the address of this field then
+ to be able to compute reachability correctly add at least
+ the last field of the variable. */
+ if (address_p
+ && VEC_length (ce_s, *results) == 0)
+ {
+ curr = get_varinfo (cexpr.var);
+ while (curr->next != NULL)
+ curr = curr->next;
+ cexpr.var = curr->id;
+ VEC_safe_push (ce_s, heap, *results, &cexpr);
+ }
+ else
+ /* Assert that we found *some* field there. The user couldn't be
+ accessing *only* padding. */
+ /* Still the user could access one past the end of an array
+ embedded in a struct resulting in accessing *only* padding. */
+ gcc_assert (VEC_length (ce_s, *results) >= 1
+ || ref_contains_array_ref (orig_t));
+ }
+ else if (bitmaxsize == 0)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Access to zero-sized part of variable,"
+ "ignoring\n");
+ }
+ else
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Access to past the end of variable, ignoring\n");
+ }
+ else if (bitmaxsize == -1)
+ {
+ /* We can't handle DEREF constraints with unknown size, we'll
+ get the wrong answer. Punt and return anything. */
+ result->var = anything_id;
+ result->offset = 0;
+ }
+ else
+ result->offset = bitpos;
+}
+
+
+/* Dereference the constraint expression CONS, and return the result.
+ DEREF (ADDRESSOF) = SCALAR
+ DEREF (SCALAR) = DEREF
+ DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp))
+ This is needed so that we can handle dereferencing DEREF constraints. */
+
+static void
+do_deref (VEC (ce_s, heap) **constraints)
+{
+ struct constraint_expr *c;
+ unsigned int i = 0;
+
+ for (i = 0; VEC_iterate (ce_s, *constraints, i, c); i++)
+ {
+ if (c->type == SCALAR)
+ c->type = DEREF;
+ else if (c->type == ADDRESSOF)
+ c->type = SCALAR;
+ else if (c->type == DEREF)
+ {
+ tree tmpvar = create_tmp_var_raw (ptr_type_node, "dereftmp");
+ struct constraint_expr tmplhs = get_constraint_exp_for_temp (tmpvar);
+ process_constraint (new_constraint (tmplhs, *c));
+ c->var = tmplhs.var;
+ }
+ else
+ gcc_unreachable ();
+ }
+}
+
+/* Given a tree T, return the constraint expression for it. */
+
+static void
+get_constraint_for_1 (tree t, VEC (ce_s, heap) **results, bool address_p)
+{
+ struct constraint_expr temp;
+
+ /* x = integer is all glommed to a single variable, which doesn't
+ point to anything by itself. That is, of course, unless it is an
+ integer constant being treated as a pointer, in which case, we
+ will return that this is really the addressof anything. This
+ happens below, since it will fall into the default case. The only
+ case we know something about an integer treated like a pointer is
+ when it is the NULL pointer, and then we just say it points to
+ NULL.
+
+ Do not do that if -fno-delete-null-pointer-checks though, because
+ in that case *NULL does not fail, so it _should_ alias *anything.
+ It is not worth adding a new option or renaming the existing one,
+ since this case is relatively obscure. */
+ if (flag_delete_null_pointer_checks
+ && TREE_CODE (t) == INTEGER_CST
+ && integer_zerop (t))
+ {
+ temp.var = nothing_id;
+ temp.type = ADDRESSOF;
+ temp.offset = 0;
+ VEC_safe_push (ce_s, heap, *results, &temp);
+ return;
+ }
+
+ /* String constants are read-only. */
+ if (TREE_CODE (t) == STRING_CST)
+ {
+ temp.var = readonly_id;
+ temp.type = SCALAR;
+ temp.offset = 0;
+ VEC_safe_push (ce_s, heap, *results, &temp);
+ return;
+ }
+
+ switch (TREE_CODE_CLASS (TREE_CODE (t)))
+ {
+ case tcc_expression:
+ {
+ switch (TREE_CODE (t))
+ {
+ case ADDR_EXPR:
+ {
+ struct constraint_expr *c;
+ unsigned int i;
+ tree exp = TREE_OPERAND (t, 0);
+
+ get_constraint_for_1 (exp, results, true);
+
+ for (i = 0; VEC_iterate (ce_s, *results, i, c); i++)
+ {
+ if (c->type == DEREF)
+ c->type = SCALAR;
+ else
+ c->type = ADDRESSOF;
+ }
+ return;
+ }
+ break;
+ default:;
+ }
+ break;
+ }
+ case tcc_reference:
+ {
+ switch (TREE_CODE (t))
+ {
+ case INDIRECT_REF:
+ {
+ get_constraint_for_1 (TREE_OPERAND (t, 0), results, address_p);
+ do_deref (results);
+ return;
+ }
+ case ARRAY_REF:
+ case ARRAY_RANGE_REF:
+ case COMPONENT_REF:
+ get_constraint_for_component_ref (t, results, address_p);
+ return;
+ default:;
+ }
+ break;
+ }
+ case tcc_exceptional:
+ {
+ switch (TREE_CODE (t))
+ {
+ case SSA_NAME:
+ {
+ get_constraint_for_ssa_var (t, results, address_p);
+ return;
+ }
+ default:;
+ }
+ break;
+ }
+ case tcc_declaration:
+ {
+ get_constraint_for_ssa_var (t, results, address_p);
+ return;
+ }
+ default:;
+ }
+
+ /* The default fallback is a constraint from anything. */
+ temp.type = ADDRESSOF;
+ temp.var = anything_id;
+ temp.offset = 0;
+ VEC_safe_push (ce_s, heap, *results, &temp);
+}
+
+/* Given a gimple tree T, return the constraint expression vector for it. */
+
+static void
+get_constraint_for (tree t, VEC (ce_s, heap) **results)
+{
+ gcc_assert (VEC_length (ce_s, *results) == 0);
+
+ get_constraint_for_1 (t, results, false);
+}
+
+/* Handle the structure copy case where we have a simple structure copy
+ between LHS and RHS that is of SIZE (in bits)
+
+ For each field of the lhs variable (lhsfield)
+ For each field of the rhs variable at lhsfield.offset (rhsfield)
+ add the constraint lhsfield = rhsfield
+
+ If we fail due to some kind of type unsafety or other thing we
+ can't handle, return false. We expect the caller to collapse the
+ variable in that case. */
+
+static bool
+do_simple_structure_copy (const struct constraint_expr lhs,
+ const struct constraint_expr rhs,
+ const unsigned HOST_WIDE_INT size)
+{
+ varinfo_t p = get_varinfo (lhs.var);
+ unsigned HOST_WIDE_INT pstart, last;
+ pstart = p->offset;
+ last = p->offset + size;
+ for (; p && p->offset < last; p = p->next)
+ {
+ varinfo_t q;
+ struct constraint_expr templhs = lhs;
+ struct constraint_expr temprhs = rhs;
+ unsigned HOST_WIDE_INT fieldoffset;
+
+ templhs.var = p->id;
+ q = get_varinfo (temprhs.var);
+ fieldoffset = p->offset - pstart;
+ q = first_vi_for_offset (q, q->offset + fieldoffset);
+ if (!q)
+ return false;
+ temprhs.var = q->id;
+ process_constraint (new_constraint (templhs, temprhs));
+ }
+ return true;
+}
+
+
+/* Handle the structure copy case where we have a structure copy between a
+ aggregate on the LHS and a dereference of a pointer on the RHS
+ that is of SIZE (in bits)
+
+ For each field of the lhs variable (lhsfield)
+ rhs.offset = lhsfield->offset
+ add the constraint lhsfield = rhs
+*/
+
+static void
+do_rhs_deref_structure_copy (const struct constraint_expr lhs,
+ const struct constraint_expr rhs,
+ const unsigned HOST_WIDE_INT size)
+{
+ varinfo_t p = get_varinfo (lhs.var);
+ unsigned HOST_WIDE_INT pstart,last;
+ pstart = p->offset;
+ last = p->offset + size;
+
+ for (; p && p->offset < last; p = p->next)
+ {
+ varinfo_t q;
+ struct constraint_expr templhs = lhs;
+ struct constraint_expr temprhs = rhs;
+ unsigned HOST_WIDE_INT fieldoffset;
+
+
+ if (templhs.type == SCALAR)
+ templhs.var = p->id;
+ else
+ templhs.offset = p->offset;
+
+ q = get_varinfo (temprhs.var);
+ fieldoffset = p->offset - pstart;
+ temprhs.offset += fieldoffset;
+ process_constraint (new_constraint (templhs, temprhs));
+ }
+}
+
+/* Handle the structure copy case where we have a structure copy
+ between an aggregate on the RHS and a dereference of a pointer on
+ the LHS that is of SIZE (in bits)
+
+ For each field of the rhs variable (rhsfield)
+ lhs.offset = rhsfield->offset
+ add the constraint lhs = rhsfield
+*/
+
+static void
+do_lhs_deref_structure_copy (const struct constraint_expr lhs,
+ const struct constraint_expr rhs,
+ const unsigned HOST_WIDE_INT size)
+{
+ varinfo_t p = get_varinfo (rhs.var);
+ unsigned HOST_WIDE_INT pstart,last;
+ pstart = p->offset;
+ last = p->offset + size;
+
+ for (; p && p->offset < last; p = p->next)
+ {
+ varinfo_t q;
+ struct constraint_expr templhs = lhs;
+ struct constraint_expr temprhs = rhs;
+ unsigned HOST_WIDE_INT fieldoffset;
+
+
+ if (temprhs.type == SCALAR)
+ temprhs.var = p->id;
+ else
+ temprhs.offset = p->offset;
+
+ q = get_varinfo (templhs.var);
+ fieldoffset = p->offset - pstart;
+ templhs.offset += fieldoffset;
+ process_constraint (new_constraint (templhs, temprhs));
+ }
+}
+
+/* Sometimes, frontends like to give us bad type information. This
+ function will collapse all the fields from VAR to the end of VAR,
+ into VAR, so that we treat those fields as a single variable.
+ We return the variable they were collapsed into. */
+
+static unsigned int
+collapse_rest_of_var (unsigned int var)
+{
+ varinfo_t currvar = get_varinfo (var);
+ varinfo_t field;
+
+ for (field = currvar->next; field; field = field->next)
+ {
+ if (dump_file)
+ fprintf (dump_file, "Type safety: Collapsing var %s into %s\n",
+ field->name, currvar->name);
+
+ gcc_assert (field->collapsed_to == 0);
+ field->collapsed_to = currvar->id;
+ }
+
+ currvar->next = NULL;
+ currvar->size = currvar->fullsize - currvar->offset;
+
+ return currvar->id;
+}
+
+/* Handle aggregate copies by expanding into copies of the respective
+ fields of the structures. */
+
+static void
+do_structure_copy (tree lhsop, tree rhsop)
+{
+ struct constraint_expr lhs, rhs, tmp;
+ VEC (ce_s, heap) *lhsc = NULL, *rhsc = NULL;
+ varinfo_t p;
+ unsigned HOST_WIDE_INT lhssize;
+ unsigned HOST_WIDE_INT rhssize;
+
+ /* Pretend we are taking the address of the constraint exprs.
+ We deal with walking the sub-fields ourselves. */
+ get_constraint_for_1 (lhsop, &lhsc, true);
+ get_constraint_for_1 (rhsop, &rhsc, true);
+ gcc_assert (VEC_length (ce_s, lhsc) == 1);
+ gcc_assert (VEC_length (ce_s, rhsc) == 1);
+ lhs = *(VEC_last (ce_s, lhsc));
+ rhs = *(VEC_last (ce_s, rhsc));
+
+ VEC_free (ce_s, heap, lhsc);
+ VEC_free (ce_s, heap, rhsc);
+
+ /* If we have special var = x, swap it around. */
+ if (lhs.var <= integer_id && !(get_varinfo (rhs.var)->is_special_var))
+ {
+ tmp = lhs;
+ lhs = rhs;
+ rhs = tmp;
+ }
+
+ /* This is fairly conservative for the RHS == ADDRESSOF case, in that it's
+ possible it's something we could handle. However, most cases falling
+ into this are dealing with transparent unions, which are slightly
+ weird. */
+ if (rhs.type == ADDRESSOF && !(get_varinfo (rhs.var)->is_special_var))
+ {
+ rhs.type = ADDRESSOF;
+ rhs.var = anything_id;
+ }
+
+ /* If the RHS is a special var, or an addressof, set all the LHS fields to
+ that special var. */
+ if (rhs.var <= integer_id)
+ {
+ for (p = get_varinfo (lhs.var); p; p = p->next)
+ {
+ struct constraint_expr templhs = lhs;
+ struct constraint_expr temprhs = rhs;
+
+ if (templhs.type == SCALAR )
+ templhs.var = p->id;
+ else
+ templhs.offset += p->offset;
+ process_constraint (new_constraint (templhs, temprhs));
+ }
+ }
+ else
+ {
+ tree rhstype = TREE_TYPE (rhsop);
+ tree lhstype = TREE_TYPE (lhsop);
+ tree rhstypesize;
+ tree lhstypesize;
+
+ lhstypesize = DECL_P (lhsop) ? DECL_SIZE (lhsop) : TYPE_SIZE (lhstype);
+ rhstypesize = DECL_P (rhsop) ? DECL_SIZE (rhsop) : TYPE_SIZE (rhstype);
+
+ /* If we have a variably sized types on the rhs or lhs, and a deref
+ constraint, add the constraint, lhsconstraint = &ANYTHING.
+ This is conservatively correct because either the lhs is an unknown
+ sized var (if the constraint is SCALAR), or the lhs is a DEREF
+ constraint, and every variable it can point to must be unknown sized
+ anyway, so we don't need to worry about fields at all. */
+ if ((rhs.type == DEREF && TREE_CODE (rhstypesize) != INTEGER_CST)
+ || (lhs.type == DEREF && TREE_CODE (lhstypesize) != INTEGER_CST))
+ {
+ rhs.var = anything_id;
+ rhs.type = ADDRESSOF;
+ rhs.offset = 0;
+ process_constraint (new_constraint (lhs, rhs));
+ return;
+ }
+
+ /* The size only really matters insofar as we don't set more or less of
+ the variable. If we hit an unknown size var, the size should be the
+ whole darn thing. */
+ if (get_varinfo (rhs.var)->is_unknown_size_var)
+ rhssize = ~0;
+ else
+ rhssize = TREE_INT_CST_LOW (rhstypesize);
+
+ if (get_varinfo (lhs.var)->is_unknown_size_var)
+ lhssize = ~0;
+ else
+ lhssize = TREE_INT_CST_LOW (lhstypesize);
+
+
+ if (rhs.type == SCALAR && lhs.type == SCALAR)
+ {
+ if (!do_simple_structure_copy (lhs, rhs, MIN (lhssize, rhssize)))
+ {
+ lhs.var = collapse_rest_of_var (get_varinfo_fc (lhs.var)->id);
+ rhs.var = collapse_rest_of_var (get_varinfo_fc (rhs.var)->id);
+ lhs.offset = 0;
+ rhs.offset = 0;
+ lhs.type = SCALAR;
+ rhs.type = SCALAR;
+ process_constraint (new_constraint (lhs, rhs));
+ }
+ }
+ else if (lhs.type != DEREF && rhs.type == DEREF)
+ do_rhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
+ else if (lhs.type == DEREF && rhs.type != DEREF)
+ do_lhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
+ else
+ {
+ tree pointedtotype = lhstype;
+ tree tmpvar;
+
+ gcc_assert (rhs.type == DEREF && lhs.type == DEREF);
+ tmpvar = create_tmp_var_raw (pointedtotype, "structcopydereftmp");
+ do_structure_copy (tmpvar, rhsop);
+ do_structure_copy (lhsop, tmpvar);
+ }
+ }
+}
+
+/* Create a constraint ID = OP. */
+
+static void
+make_constraint_to (unsigned id, tree op)
+{
+ VEC(ce_s, heap) *rhsc = NULL;
+ struct constraint_expr *c;
+ struct constraint_expr includes;
+ unsigned int j;
+
+ includes.var = id;
+ includes.offset = 0;
+ includes.type = SCALAR;
+
+ get_constraint_for (op, &rhsc);
+ for (j = 0; VEC_iterate (ce_s, rhsc, j, c); j++)
+ process_constraint (new_constraint (includes, *c));
+ VEC_free (ce_s, heap, rhsc);
+}
+
+/* Make constraints necessary to make OP escape. */
+
+static void
+make_escape_constraint (tree op)
+{
+ make_constraint_to (escaped_id, op);
+}
+
+/* For non-IPA mode, generate constraints necessary for a call on the
+ RHS. */
+
+static void
+handle_rhs_call (gimple stmt)
+{
+ unsigned i;
+
+ for (i = 0; i < gimple_call_num_args (stmt); ++i)
+ {
+ tree arg = gimple_call_arg (stmt, i);
+
+ /* Find those pointers being passed, and make sure they end up
+ pointing to anything. */
+ if (could_have_pointers (arg))
+ make_escape_constraint (arg);
+ }
+
+ /* The static chain escapes as well. */
+ if (gimple_call_chain (stmt))
+ make_escape_constraint (gimple_call_chain (stmt));
+}
+
+/* For non-IPA mode, generate constraints necessary for a call
+ that returns a pointer and assigns it to LHS. This simply makes
+ the LHS point to global and escaped variables. */
+
+static void
+handle_lhs_call (tree lhs, int flags)
+{
+ VEC(ce_s, heap) *lhsc = NULL;
+ struct constraint_expr rhsc;
+ unsigned int j;
+ struct constraint_expr *lhsp;
+
+ get_constraint_for (lhs, &lhsc);
+
+ if (flags & ECF_MALLOC)
+ {
+ tree heapvar = heapvar_lookup (lhs);
+ varinfo_t vi;
+
+ if (heapvar == NULL)
+ {
+ heapvar = create_tmp_var_raw (ptr_type_node, "HEAP");
+ DECL_EXTERNAL (heapvar) = 1;
+ get_var_ann (heapvar)->is_heapvar = 1;
+ if (gimple_referenced_vars (cfun))
+ add_referenced_var (heapvar);
+ heapvar_insert (lhs, heapvar);
+ }
+
+ rhsc.var = create_variable_info_for (heapvar,
+ alias_get_name (heapvar));
+ vi = get_varinfo (rhsc.var);
+ vi->is_artificial_var = 1;
+ vi->is_heap_var = 1;
+ vi->is_unknown_size_var = true;
+ vi->fullsize = ~0;
+ vi->size = ~0;
+ rhsc.type = ADDRESSOF;
+ rhsc.offset = 0;
+ }
+ else
+ {
+ rhsc.var = escaped_id;
+ rhsc.offset = 0;
+ rhsc.type = ADDRESSOF;
+ }
+ for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
+ process_constraint (new_constraint (*lhsp, rhsc));
+ VEC_free (ce_s, heap, lhsc);
+}
+
+/* For non-IPA mode, generate constraints necessary for a call of a
+ const function that returns a pointer in the statement STMT. */
+
+static void
+handle_const_call (gimple stmt)
+{
+ tree lhs = gimple_call_lhs (stmt);
+ VEC(ce_s, heap) *lhsc = NULL;
+ struct constraint_expr rhsc;
+ unsigned int j, k;
+ struct constraint_expr *lhsp;
+ tree tmpvar;
+ struct constraint_expr tmpc;
+
+ get_constraint_for (lhs, &lhsc);
+
+ /* If this is a nested function then it can return anything. */
+ if (gimple_call_chain (stmt))
+ {
+ rhsc.var = anything_id;
+ rhsc.offset = 0;
+ rhsc.type = ADDRESSOF;
+ for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
+ process_constraint (new_constraint (*lhsp, rhsc));
+ VEC_free (ce_s, heap, lhsc);
+ return;
+ }
+
+ /* We always use a temporary here, otherwise we end up with a quadratic
+ amount of constraints for
+ large_struct = const_call (large_struct);
+ in field-sensitive PTA. */
+ tmpvar = create_tmp_var_raw (ptr_type_node, "consttmp");
+ tmpc = get_constraint_exp_for_temp (tmpvar);
+
+ /* May return addresses of globals. */
+ rhsc.var = nonlocal_id;
+ rhsc.offset = 0;
+ rhsc.type = ADDRESSOF;
+ process_constraint (new_constraint (tmpc, rhsc));
+
+ /* May return arguments. */
+ for (k = 0; k < gimple_call_num_args (stmt); ++k)
+ {
+ tree arg = gimple_call_arg (stmt, k);
+
+ if (could_have_pointers (arg))
+ {
+ VEC(ce_s, heap) *argc = NULL;
+ struct constraint_expr *argp;
+ int i;
+
+ get_constraint_for (arg, &argc);
+ for (i = 0; VEC_iterate (ce_s, argc, i, argp); i++)
+ process_constraint (new_constraint (tmpc, *argp));
+ VEC_free (ce_s, heap, argc);
+ }
+ }
+
+ for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
+ process_constraint (new_constraint (*lhsp, tmpc));
+
+ VEC_free (ce_s, heap, lhsc);
+}
+
+/* For non-IPA mode, generate constraints necessary for a call to a
+ pure function in statement STMT. */
+
+static void
+handle_pure_call (gimple stmt)
+{
+ unsigned i;
+
+ /* Memory reached from pointer arguments is call-used. */
+ for (i = 0; i < gimple_call_num_args (stmt); ++i)
+ {
+ tree arg = gimple_call_arg (stmt, i);
+
+ if (could_have_pointers (arg))
+ make_constraint_to (callused_id, arg);
+ }
+
+ /* The static chain is used as well. */
+ if (gimple_call_chain (stmt))
+ make_constraint_to (callused_id, gimple_call_chain (stmt));
+
+ /* If the call returns a pointer it may point to reachable memory
+ from the arguments. Not so for malloc functions though. */
+ if (gimple_call_lhs (stmt)
+ && could_have_pointers (gimple_call_lhs (stmt))
+ && !(gimple_call_flags (stmt) & ECF_MALLOC))
+ {
+ tree lhs = gimple_call_lhs (stmt);
+ VEC(ce_s, heap) *lhsc = NULL;
+ struct constraint_expr rhsc;
+ struct constraint_expr *lhsp;
+ unsigned j;
+
+ get_constraint_for (lhs, &lhsc);
+
+ /* If this is a nested function then it can return anything. */
+ if (gimple_call_chain (stmt))
+ {
+ rhsc.var = anything_id;
+ rhsc.offset = 0;
+ rhsc.type = ADDRESSOF;
+ for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
+ process_constraint (new_constraint (*lhsp, rhsc));
+ VEC_free (ce_s, heap, lhsc);
+ return;
+ }
+
+ /* Else just add the call-used memory here. Escaped variables
+ and globals will be dealt with in handle_lhs_call. */
+ rhsc.var = callused_id;
+ rhsc.offset = 0;
+ rhsc.type = ADDRESSOF;
+ for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
+ process_constraint (new_constraint (*lhsp, rhsc));
+ VEC_free (ce_s, heap, lhsc);
+ }
+}
+
+/* Walk statement T setting up aliasing constraints according to the
+ references found in T. This function is the main part of the
+ constraint builder. AI points to auxiliary alias information used
+ when building alias sets and computing alias grouping heuristics. */
+
+static void
+find_func_aliases (gimple origt)
+{
+ gimple t = origt;
+ VEC(ce_s, heap) *lhsc = NULL;
+ VEC(ce_s, heap) *rhsc = NULL;
+ struct constraint_expr *c;
+ enum escape_type stmt_escape_type;
+
+ /* Now build constraints expressions. */
+ if (gimple_code (t) == GIMPLE_PHI)
+ {
+ gcc_assert (!AGGREGATE_TYPE_P (TREE_TYPE (gimple_phi_result (t))));
+
+ /* Only care about pointers and structures containing
+ pointers. */
+ if (could_have_pointers (gimple_phi_result (t)))
+ {
+ size_t i;
+ unsigned int j;
+
+ /* For a phi node, assign all the arguments to
+ the result. */
+ get_constraint_for (gimple_phi_result (t), &lhsc);
+ for (i = 0; i < gimple_phi_num_args (t); i++)
+ {
+ tree rhstype;
+ tree strippedrhs = PHI_ARG_DEF (t, i);
+
+ STRIP_NOPS (strippedrhs);
+ rhstype = TREE_TYPE (strippedrhs);
+ get_constraint_for (gimple_phi_arg_def (t, i), &rhsc);
+
+ for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++)
+ {
+ struct constraint_expr *c2;
+ while (VEC_length (ce_s, rhsc) > 0)
+ {
+ c2 = VEC_last (ce_s, rhsc);
+ process_constraint (new_constraint (*c, *c2));
+ VEC_pop (ce_s, rhsc);
+ }
+ }
+ }
+ }
+ }
+ /* In IPA mode, we need to generate constraints to pass call
+ arguments through their calls. There are two cases,
+ either a GIMPLE_CALL returning a value, or just a plain
+ GIMPLE_CALL when we are not.
+
+ In non-ipa mode, we need to generate constraints for each
+ pointer passed by address. */
+ else if (is_gimple_call (t))
+ {
+ if (!in_ipa_mode)
+ {
+ int flags = gimple_call_flags (t);
+
+ /* Const functions can return their arguments and addresses
+ of global memory but not of escaped memory. */
+ if (flags & ECF_CONST)
+ {
+ if (gimple_call_lhs (t)
+ && could_have_pointers (gimple_call_lhs (t)))
+ handle_const_call (t);
+ }
+ /* Pure functions can return addresses in and of memory
+ reachable from their arguments, but they are not an escape
+ point for reachable memory of their arguments. */
+ else if (flags & ECF_PURE)
+ {
+ handle_pure_call (t);
+ if (gimple_call_lhs (t)
+ && could_have_pointers (gimple_call_lhs (t)))
+ handle_lhs_call (gimple_call_lhs (t), flags);
+ }
+ else
+ {
+ handle_rhs_call (t);
+ if (gimple_call_lhs (t)
+ && could_have_pointers (gimple_call_lhs (t)))
+ handle_lhs_call (gimple_call_lhs (t), flags);
+ }
+ }
+ else
+ {
+ tree lhsop;
+ varinfo_t fi;
+ int i = 1;
+ size_t j;
+ tree decl;
+
+ lhsop = gimple_call_lhs (t);
+ decl = gimple_call_fndecl (t);
+
+ /* If we can directly resolve the function being called, do so.
+ Otherwise, it must be some sort of indirect expression that
+ we should still be able to handle. */
+ if (decl)
+ fi = get_vi_for_tree (decl);
+ else
+ {
+ decl = gimple_call_fn (t);
+ fi = get_vi_for_tree (decl);
+ }
+
+ /* Assign all the passed arguments to the appropriate incoming
+ parameters of the function. */
+ for (j = 0; j < gimple_call_num_args (t); j++)
+ {
+ struct constraint_expr lhs ;
+ struct constraint_expr *rhsp;
+ tree arg = gimple_call_arg (t, j);
+
+ get_constraint_for (arg, &rhsc);
+ if (TREE_CODE (decl) != FUNCTION_DECL)
+ {
+ lhs.type = DEREF;
+ lhs.var = fi->id;
+ lhs.offset = i;
+ }
+ else
+ {
+ lhs.type = SCALAR;
+ lhs.var = first_vi_for_offset (fi, i)->id;
+ lhs.offset = 0;
+ }
+ while (VEC_length (ce_s, rhsc) != 0)
+ {
+ rhsp = VEC_last (ce_s, rhsc);
+ process_constraint (new_constraint (lhs, *rhsp));
+ VEC_pop (ce_s, rhsc);
+ }
+ i++;
+ }
+
+ /* If we are returning a value, assign it to the result. */
+ if (lhsop)
+ {
+ struct constraint_expr rhs;
+ struct constraint_expr *lhsp;
+ unsigned int j = 0;
+
+ get_constraint_for (lhsop, &lhsc);
+ if (TREE_CODE (decl) != FUNCTION_DECL)
+ {
+ rhs.type = DEREF;
+ rhs.var = fi->id;
+ rhs.offset = i;
+ }
+ else
+ {
+ rhs.type = SCALAR;
+ rhs.var = first_vi_for_offset (fi, i)->id;
+ rhs.offset = 0;
+ }
+ for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
+ process_constraint (new_constraint (*lhsp, rhs));
+ }
+ }
+ }
+ /* Otherwise, just a regular assignment statement. Only care about
+ operations with pointer result, others are dealt with as escape
+ points if they have pointer operands. */
+ else if (is_gimple_assign (t)
+ && could_have_pointers (gimple_assign_lhs (t)))
+ {
+ /* Otherwise, just a regular assignment statement. */
+ tree lhsop = gimple_assign_lhs (t);
+ tree rhsop = (gimple_num_ops (t) == 2) ? gimple_assign_rhs1 (t) : NULL;
+
+ if (rhsop && AGGREGATE_TYPE_P (TREE_TYPE (lhsop)))
+ do_structure_copy (lhsop, rhsop);
+ else
+ {
+ unsigned int j;
+ struct constraint_expr temp;
+ get_constraint_for (lhsop, &lhsc);
+
+ if (gimple_assign_rhs_code (t) == POINTER_PLUS_EXPR)
+ get_constraint_for_ptr_offset (gimple_assign_rhs1 (t),
+ gimple_assign_rhs2 (t), &rhsc);
+ else if ((CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (t))
+ && !(POINTER_TYPE_P (gimple_expr_type (t))
+ && !POINTER_TYPE_P (TREE_TYPE (rhsop))))
+ || gimple_assign_single_p (t))
+ get_constraint_for (rhsop, &rhsc);
+ else
+ {
+ temp.type = ADDRESSOF;
+ temp.var = anything_id;
+ temp.offset = 0;
+ VEC_safe_push (ce_s, heap, rhsc, &temp);
+ }
+ for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++)
+ {
+ struct constraint_expr *c2;
+ unsigned int k;
+
+ for (k = 0; VEC_iterate (ce_s, rhsc, k, c2); k++)
+ process_constraint (new_constraint (*c, *c2));
+ }
+ }
+ }
+ else if (gimple_code (t) == GIMPLE_CHANGE_DYNAMIC_TYPE)
+ {
+ unsigned int j;
+
+ get_constraint_for (gimple_cdt_location (t), &lhsc);
+ for (j = 0; VEC_iterate (ce_s, lhsc, j, c); ++j)
+ get_varinfo (c->var)->no_tbaa_pruning = true;
+ }
+
+ stmt_escape_type = is_escape_site (t);
+ if (stmt_escape_type == ESCAPE_STORED_IN_GLOBAL)
+ {
+ gcc_assert (is_gimple_assign (t));
+ if (gimple_assign_rhs_code (t) == ADDR_EXPR)
+ {
+ tree rhs = gimple_assign_rhs1 (t);
+ tree base = get_base_address (TREE_OPERAND (rhs, 0));
+ if (base
+ && (!DECL_P (base)
+ || !is_global_var (base)))
+ make_escape_constraint (rhs);
+ }
+ else if (get_gimple_rhs_class (gimple_assign_rhs_code (t))
+ == GIMPLE_SINGLE_RHS)
+ {
+ if (could_have_pointers (gimple_assign_rhs1 (t)))
+ make_escape_constraint (gimple_assign_rhs1 (t));
+ }
+ else
+ gcc_unreachable ();
+ }
+ else if (stmt_escape_type == ESCAPE_BAD_CAST)
+ {
+ gcc_assert (is_gimple_assign (t));
+ gcc_assert (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (t))
+ || gimple_assign_rhs_code (t) == VIEW_CONVERT_EXPR);
+ make_escape_constraint (gimple_assign_rhs1 (t));
+ }
+ else if (stmt_escape_type == ESCAPE_TO_ASM)
+ {
+ unsigned i;
+ for (i = 0; i < gimple_asm_noutputs (t); ++i)
+ {
+ tree op = TREE_VALUE (gimple_asm_output_op (t, i));
+ if (op && could_have_pointers (op))
+ /* Strictly we'd only need the constraints from ESCAPED and
+ NONLOCAL. */
+ make_escape_constraint (op);
+ }
+ for (i = 0; i < gimple_asm_ninputs (t); ++i)
+ {
+ tree op = TREE_VALUE (gimple_asm_input_op (t, i));
+ if (op && could_have_pointers (op))
+ /* Strictly we'd only need the constraint to ESCAPED. */
+ make_escape_constraint (op);
+ }
+ }
+
+ /* After promoting variables and computing aliasing we will
+ need to re-scan most statements. FIXME: Try to minimize the
+ number of statements re-scanned. It's not really necessary to
+ re-scan *all* statements. */
+ if (!in_ipa_mode)
+ gimple_set_modified (origt, true);
+ VEC_free (ce_s, heap, rhsc);
+ VEC_free (ce_s, heap, lhsc);
+}
+
+
+/* Find the first varinfo in the same variable as START that overlaps with
+ OFFSET.
+ Effectively, walk the chain of fields for the variable START to find the
+ first field that overlaps with OFFSET.
+ Return NULL if we can't find one. */
+
+static varinfo_t
+first_vi_for_offset (varinfo_t start, unsigned HOST_WIDE_INT offset)
+{
+ varinfo_t curr = start;
+ while (curr)
+ {
+ /* We may not find a variable in the field list with the actual
+ offset when when we have glommed a structure to a variable.
+ In that case, however, offset should still be within the size
+ of the variable. */
+ if (offset >= curr->offset && offset < (curr->offset + curr->size))
+ return curr;
+ curr = curr->next;
+ }
+ return NULL;
+}
+
+
+/* Insert the varinfo FIELD into the field list for BASE, at the front
+ of the list. */
+
+static void
+insert_into_field_list (varinfo_t base, varinfo_t field)
+{
+ varinfo_t prev = base;
+ varinfo_t curr = base->next;
+
+ field->next = curr;
+ prev->next = field;
+}
+
+/* Insert the varinfo FIELD into the field list for BASE, ordered by
+ offset. */
+
+static void
+insert_into_field_list_sorted (varinfo_t base, varinfo_t field)
+{
+ varinfo_t prev = base;
+ varinfo_t curr = base->next;
+
+ if (curr == NULL)
+ {
+ prev->next = field;
+ field->next = NULL;
+ }
+ else
+ {
+ while (curr)
+ {
+ if (field->offset <= curr->offset)
+ break;
+ prev = curr;
+ curr = curr->next;
+ }
+ field->next = prev->next;
+ prev->next = field;
+ }
+}
+
+/* This structure is used during pushing fields onto the fieldstack
+ to track the offset of the field, since bitpos_of_field gives it
+ relative to its immediate containing type, and we want it relative
+ to the ultimate containing object. */
+
+struct fieldoff
+{
+ /* Offset from the base of the base containing object to this field. */
+ HOST_WIDE_INT offset;
+
+ /* Size, in bits, of the field. */
+ unsigned HOST_WIDE_INT size;
+
+ unsigned has_unknown_size : 1;
+
+ unsigned may_have_pointers : 1;
+};
+typedef struct fieldoff fieldoff_s;
+
+DEF_VEC_O(fieldoff_s);
+DEF_VEC_ALLOC_O(fieldoff_s,heap);
+
+/* qsort comparison function for two fieldoff's PA and PB */
+
+static int
+fieldoff_compare (const void *pa, const void *pb)
+{
+ const fieldoff_s *foa = (const fieldoff_s *)pa;
+ const fieldoff_s *fob = (const fieldoff_s *)pb;
+ unsigned HOST_WIDE_INT foasize, fobsize;
+
+ if (foa->offset < fob->offset)
+ return -1;
+ else if (foa->offset > fob->offset)
+ return 1;
+
+ foasize = foa->size;
+ fobsize = fob->size;
+ if (foasize < fobsize)
+ return -1;
+ else if (foasize > fobsize)
+ return 1;
+ return 0;
+}
+
+/* Sort a fieldstack according to the field offset and sizes. */
+static void
+sort_fieldstack (VEC(fieldoff_s,heap) *fieldstack)
+{
+ qsort (VEC_address (fieldoff_s, fieldstack),
+ VEC_length (fieldoff_s, fieldstack),
+ sizeof (fieldoff_s),
+ fieldoff_compare);
+}
+
+/* Return true if V is a tree that we can have subvars for.
+ Normally, this is any aggregate type. Also complex
+ types which are not gimple registers can have subvars. */
+
+static inline bool
+var_can_have_subvars (const_tree v)
+{
+ /* Volatile variables should never have subvars. */
+ if (TREE_THIS_VOLATILE (v))
+ return false;
+
+ /* Non decls or memory tags can never have subvars. */
+ if (!DECL_P (v) || MTAG_P (v))
+ return false;
+
+ /* Aggregates without overlapping fields can have subvars. */
+ if (TREE_CODE (TREE_TYPE (v)) == RECORD_TYPE)
+ return true;
+
+ return false;
+}
+
+/* Given a TYPE, and a vector of field offsets FIELDSTACK, push all
+ the fields of TYPE onto fieldstack, recording their offsets along
+ the way.
+
+ OFFSET is used to keep track of the offset in this entire
+ structure, rather than just the immediately containing structure.
+ Returns the number of fields pushed. */
+
+static int
+push_fields_onto_fieldstack (tree type, VEC(fieldoff_s,heap) **fieldstack,
+ HOST_WIDE_INT offset)
+{
+ tree field;
+ int count = 0;
+
+ if (TREE_CODE (type) != RECORD_TYPE)
+ return 0;
+
+ /* If the vector of fields is growing too big, bail out early.
+ Callers check for VEC_length <= MAX_FIELDS_FOR_FIELD_SENSITIVE, make
+ sure this fails. */
+ if (VEC_length (fieldoff_s, *fieldstack) > MAX_FIELDS_FOR_FIELD_SENSITIVE)
+ return 0;
+
+ for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
+ if (TREE_CODE (field) == FIELD_DECL)
+ {
+ bool push = false;
+ int pushed = 0;
+ HOST_WIDE_INT foff = bitpos_of_field (field);
+
+ if (!var_can_have_subvars (field)
+ || TREE_CODE (TREE_TYPE (field)) == QUAL_UNION_TYPE
+ || TREE_CODE (TREE_TYPE (field)) == UNION_TYPE)
+ push = true;
+ else if (!(pushed = push_fields_onto_fieldstack
+ (TREE_TYPE (field), fieldstack, offset + foff))
+ && (DECL_SIZE (field)
+ && !integer_zerop (DECL_SIZE (field))))
+ /* Empty structures may have actual size, like in C++. So
+ see if we didn't push any subfields and the size is
+ nonzero, push the field onto the stack. */
+ push = true;
+
+ if (push)
+ {
+ fieldoff_s *pair = NULL;
+ bool has_unknown_size = false;
+
+ if (!VEC_empty (fieldoff_s, *fieldstack))
+ pair = VEC_last (fieldoff_s, *fieldstack);
+
+ if (!DECL_SIZE (field)
+ || !host_integerp (DECL_SIZE (field), 1))
+ has_unknown_size = true;
+
+ /* If adjacent fields do not contain pointers merge them. */
+ if (pair
+ && !pair->may_have_pointers
+ && !could_have_pointers (field)
+ && !pair->has_unknown_size
+ && !has_unknown_size
+ && pair->offset + (HOST_WIDE_INT)pair->size == offset + foff)
+ {
+ pair = VEC_last (fieldoff_s, *fieldstack);
+ pair->size += TREE_INT_CST_LOW (DECL_SIZE (field));
+ }
+ else
+ {
+ pair = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
+ pair->offset = offset + foff;
+ pair->has_unknown_size = has_unknown_size;
+ if (!has_unknown_size)
+ pair->size = TREE_INT_CST_LOW (DECL_SIZE (field));
+ else
+ pair->size = -1;
+ pair->may_have_pointers = could_have_pointers (field);
+ count++;
+ }
+ }
+ else
+ count += pushed;
+ }
+
+ return count;
+}
+
+/* Create a constraint ID = &FROM. */
+
+static void
+make_constraint_from (varinfo_t vi, int from)
+{
+ struct constraint_expr lhs, rhs;
+
+ lhs.var = vi->id;
+ lhs.offset = 0;
+ lhs.type = SCALAR;
+
+ rhs.var = from;
+ rhs.offset = 0;
+ rhs.type = ADDRESSOF;
+ process_constraint (new_constraint (lhs, rhs));
+}
+
+/* Count the number of arguments DECL has, and set IS_VARARGS to true
+ if it is a varargs function. */
+
+static unsigned int
+count_num_arguments (tree decl, bool *is_varargs)
+{
+ unsigned int i = 0;
+ tree t;
+
+ for (t = TYPE_ARG_TYPES (TREE_TYPE (decl));
+ t;
+ t = TREE_CHAIN (t))
+ {
+ if (TREE_VALUE (t) == void_type_node)
+ break;
+ i++;
+ }
+
+ if (!t)
+ *is_varargs = true;
+ return i;
+}
+
+/* Creation function node for DECL, using NAME, and return the index
+ of the variable we've created for the function. */
+
+static unsigned int
+create_function_info_for (tree decl, const char *name)
+{
+ unsigned int index = VEC_length (varinfo_t, varmap);
+ varinfo_t vi;
+ tree arg;
+ unsigned int i;
+ bool is_varargs = false;
+
+ /* Create the variable info. */
+
+ vi = new_var_info (decl, index, name);
+ vi->decl = decl;
+ vi->offset = 0;
+ vi->size = 1;
+ vi->fullsize = count_num_arguments (decl, &is_varargs) + 1;
+ insert_vi_for_tree (vi->decl, vi);
+ VEC_safe_push (varinfo_t, heap, varmap, vi);
+
+ stats.total_vars++;
+
+ /* If it's varargs, we don't know how many arguments it has, so we
+ can't do much. */
+ if (is_varargs)
+ {
+ vi->fullsize = ~0;
+ vi->size = ~0;
+ vi->is_unknown_size_var = true;
+ return index;
+ }
+
+
+ arg = DECL_ARGUMENTS (decl);
+
+ /* Set up variables for each argument. */
+ for (i = 1; i < vi->fullsize; i++)
+ {
+ varinfo_t argvi;
+ const char *newname;
+ char *tempname;
+ unsigned int newindex;
+ tree argdecl = decl;
+
+ if (arg)
+ argdecl = arg;
+
+ newindex = VEC_length (varinfo_t, varmap);
+ asprintf (&tempname, "%s.arg%d", name, i-1);
+ newname = ggc_strdup (tempname);
+ free (tempname);
+
+ argvi = new_var_info (argdecl, newindex, newname);
+ argvi->decl = argdecl;
+ VEC_safe_push (varinfo_t, heap, varmap, argvi);
+ argvi->offset = i;
+ argvi->size = 1;
+ argvi->is_full_var = true;
+ argvi->fullsize = vi->fullsize;
+ insert_into_field_list_sorted (vi, argvi);
+ stats.total_vars ++;
+ if (arg)
+ {
+ insert_vi_for_tree (arg, argvi);
+ arg = TREE_CHAIN (arg);
+ }
+ }
+
+ /* Create a variable for the return var. */
+ if (DECL_RESULT (decl) != NULL
+ || !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (decl))))
+ {
+ varinfo_t resultvi;
+ const char *newname;
+ char *tempname;
+ unsigned int newindex;
+ tree resultdecl = decl;
+
+ vi->fullsize ++;
+
+ if (DECL_RESULT (decl))
+ resultdecl = DECL_RESULT (decl);
+
+ newindex = VEC_length (varinfo_t, varmap);
+ asprintf (&tempname, "%s.result", name);
+ newname = ggc_strdup (tempname);
+ free (tempname);
+
+ resultvi = new_var_info (resultdecl, newindex, newname);
+ resultvi->decl = resultdecl;
+ VEC_safe_push (varinfo_t, heap, varmap, resultvi);
+ resultvi->offset = i;
+ resultvi->size = 1;
+ resultvi->fullsize = vi->fullsize;
+ resultvi->is_full_var = true;
+ insert_into_field_list_sorted (vi, resultvi);
+ stats.total_vars ++;
+ if (DECL_RESULT (decl))
+ insert_vi_for_tree (DECL_RESULT (decl), resultvi);
+ }
+ return index;
+}
+
+
+/* Return true if FIELDSTACK contains fields that overlap.
+ FIELDSTACK is assumed to be sorted by offset. */
+
+static bool
+check_for_overlaps (VEC (fieldoff_s,heap) *fieldstack)
+{
+ fieldoff_s *fo = NULL;
+ unsigned int i;
+ HOST_WIDE_INT lastoffset = -1;
+
+ for (i = 0; VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
+ {
+ if (fo->offset == lastoffset)
+ return true;
+ lastoffset = fo->offset;
+ }
+ return false;
+}
+
+/* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
+ This will also create any varinfo structures necessary for fields
+ of DECL. */
+
+static unsigned int
+create_variable_info_for (tree decl, const char *name)
+{
+ unsigned int index = VEC_length (varinfo_t, varmap);
+ varinfo_t vi;
+ tree decl_type = TREE_TYPE (decl);
+ tree declsize = DECL_P (decl) ? DECL_SIZE (decl) : TYPE_SIZE (decl_type);
+ bool is_global = DECL_P (decl) ? is_global_var (decl) : false;
+ VEC (fieldoff_s,heap) *fieldstack = NULL;
+
+ if (TREE_CODE (decl) == FUNCTION_DECL && in_ipa_mode)
+ return create_function_info_for (decl, name);
+
+ if (var_can_have_subvars (decl) && use_field_sensitive
+ && (!var_ann (decl)
+ || var_ann (decl)->noalias_state == 0)
+ && (!var_ann (decl)
+ || !var_ann (decl)->is_heapvar))
+ push_fields_onto_fieldstack (decl_type, &fieldstack, 0);
+
+ /* If the variable doesn't have subvars, we may end up needing to
+ sort the field list and create fake variables for all the
+ fields. */
+ vi = new_var_info (decl, index, name);
+ vi->decl = decl;
+ vi->offset = 0;
+ vi->may_have_pointers = could_have_pointers (decl);
+ if (!declsize
+ || !host_integerp (declsize, 1))
+ {
+ vi->is_unknown_size_var = true;
+ vi->fullsize = ~0;
+ vi->size = ~0;
+ }
+ else
+ {
+ vi->fullsize = TREE_INT_CST_LOW (declsize);
+ vi->size = vi->fullsize;
+ }
+
+ insert_vi_for_tree (vi->decl, vi);
+ VEC_safe_push (varinfo_t, heap, varmap, vi);
+ if (is_global && (!flag_whole_program || !in_ipa_mode)
+ && vi->may_have_pointers)
+ {
+ if (var_ann (decl)
+ && var_ann (decl)->noalias_state == NO_ALIAS_ANYTHING)
+ make_constraint_from (vi, vi->id);
+ else
+ make_constraint_from (vi, escaped_id);
+ }
+
+ stats.total_vars++;
+ if (use_field_sensitive
+ && !vi->is_unknown_size_var
+ && var_can_have_subvars (decl)
+ && VEC_length (fieldoff_s, fieldstack) > 1
+ && VEC_length (fieldoff_s, fieldstack) <= MAX_FIELDS_FOR_FIELD_SENSITIVE)
+ {
+ unsigned int newindex = VEC_length (varinfo_t, varmap);
+ fieldoff_s *fo = NULL;
+ bool notokay = false;
+ unsigned int i;
+
+ for (i = 0; !notokay && VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
+ {
+ if (fo->has_unknown_size
+ || fo->offset < 0)
+ {
+ notokay = true;
+ break;
+ }
+ }
+
+ /* We can't sort them if we have a field with a variable sized type,
+ which will make notokay = true. In that case, we are going to return
+ without creating varinfos for the fields anyway, so sorting them is a
+ waste to boot. */
+ if (!notokay)
+ {
+ sort_fieldstack (fieldstack);
+ /* Due to some C++ FE issues, like PR 22488, we might end up
+ what appear to be overlapping fields even though they,
+ in reality, do not overlap. Until the C++ FE is fixed,
+ we will simply disable field-sensitivity for these cases. */
+ notokay = check_for_overlaps (fieldstack);
+ }
+
+
+ if (VEC_length (fieldoff_s, fieldstack) != 0)
+ fo = VEC_index (fieldoff_s, fieldstack, 0);
+
+ if (fo == NULL || notokay)
+ {
+ vi->is_unknown_size_var = 1;
+ vi->fullsize = ~0;
+ vi->size = ~0;
+ vi->is_full_var = true;
+ VEC_free (fieldoff_s, heap, fieldstack);
+ return index;
+ }
+
+ vi->size = fo->size;
+ vi->offset = fo->offset;
+ vi->may_have_pointers = fo->may_have_pointers;
+ for (i = VEC_length (fieldoff_s, fieldstack) - 1;
+ i >= 1 && VEC_iterate (fieldoff_s, fieldstack, i, fo);
+ i--)
+ {
+ varinfo_t newvi;
+ const char *newname = "NULL";
+ char *tempname;
+
+ newindex = VEC_length (varinfo_t, varmap);
+ if (dump_file)
+ {
+ asprintf (&tempname, "%s." HOST_WIDE_INT_PRINT_DEC
+ "+" HOST_WIDE_INT_PRINT_DEC,
+ vi->name, fo->offset, fo->size);
+ newname = ggc_strdup (tempname);
+ free (tempname);
+ }
+ newvi = new_var_info (decl, newindex, newname);
+ newvi->offset = fo->offset;
+ newvi->size = fo->size;
+ newvi->fullsize = vi->fullsize;
+ newvi->may_have_pointers = fo->may_have_pointers;
+ insert_into_field_list (vi, newvi);
+ VEC_safe_push (varinfo_t, heap, varmap, newvi);
+ if (is_global && (!flag_whole_program || !in_ipa_mode)
+ && newvi->may_have_pointers)
+ make_constraint_from (newvi, escaped_id);
+
+ stats.total_vars++;
+ }
+ }
+ else
+ vi->is_full_var = true;
+
+ VEC_free (fieldoff_s, heap, fieldstack);
+
+ return index;
+}
+
+/* Print out the points-to solution for VAR to FILE. */
+
+void
+dump_solution_for_var (FILE *file, unsigned int var)
+{
+ varinfo_t vi = get_varinfo (var);
+ unsigned int i;
+ bitmap_iterator bi;
+
+ if (find (var) != var)
+ {
+ varinfo_t vipt = get_varinfo (find (var));
+ fprintf (file, "%s = same as %s\n", vi->name, vipt->name);
+ }
+ else
+ {
+ fprintf (file, "%s = { ", vi->name);
+ EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
+ {
+ fprintf (file, "%s ", get_varinfo (i)->name);
+ }
+ fprintf (file, "}");
+ if (vi->no_tbaa_pruning)
+ fprintf (file, " no-tbaa-pruning");
+ fprintf (file, "\n");
+ }
+}
+
+/* Print the points-to solution for VAR to stdout. */
+
+void
+debug_solution_for_var (unsigned int var)
+{
+ dump_solution_for_var (stdout, var);
+}
+
+/* Create varinfo structures for all of the variables in the
+ function for intraprocedural mode. */
+
+static void
+intra_create_variable_infos (void)
+{
+ tree t;
+ struct constraint_expr lhs, rhs;
+
+ /* For each incoming pointer argument arg, create the constraint ARG
+ = NONLOCAL or a dummy variable if flag_argument_noalias is set. */
+ for (t = DECL_ARGUMENTS (current_function_decl); t; t = TREE_CHAIN (t))
+ {
+ varinfo_t p;
+
+ if (!could_have_pointers (t))
+ continue;
+
+ /* If flag_argument_noalias is set, then function pointer
+ arguments are guaranteed not to point to each other. In that
+ case, create an artificial variable PARM_NOALIAS and the
+ constraint ARG = &PARM_NOALIAS. */
+ if (POINTER_TYPE_P (TREE_TYPE (t)) && flag_argument_noalias > 0)
+ {
+ varinfo_t vi;
+ tree heapvar = heapvar_lookup (t);
+
+ lhs.offset = 0;
+ lhs.type = SCALAR;
+ lhs.var = get_vi_for_tree (t)->id;
+
+ if (heapvar == NULL_TREE)
+ {
+ var_ann_t ann;
+ heapvar = create_tmp_var_raw (ptr_type_node,
+ "PARM_NOALIAS");
+ DECL_EXTERNAL (heapvar) = 1;
+ if (gimple_referenced_vars (cfun))
+ add_referenced_var (heapvar);
+
+ heapvar_insert (t, heapvar);
+
+ ann = get_var_ann (heapvar);
+ ann->is_heapvar = 1;
+ if (flag_argument_noalias == 1)
+ ann->noalias_state = NO_ALIAS;
+ else if (flag_argument_noalias == 2)
+ ann->noalias_state = NO_ALIAS_GLOBAL;
+ else if (flag_argument_noalias == 3)
+ ann->noalias_state = NO_ALIAS_ANYTHING;
+ else
+ gcc_unreachable ();
+ }
+
+ vi = get_vi_for_tree (heapvar);
+ vi->is_artificial_var = 1;
+ vi->is_heap_var = 1;
+ vi->is_unknown_size_var = true;
+ vi->fullsize = ~0;
+ vi->size = ~0;
+ rhs.var = vi->id;
+ rhs.type = ADDRESSOF;
+ rhs.offset = 0;
+ for (p = get_varinfo (lhs.var); p; p = p->next)
+ {
+ struct constraint_expr temp = lhs;
+ temp.var = p->id;
+ process_constraint (new_constraint (temp, rhs));
+ }
+ }
+ else
+ {
+ varinfo_t arg_vi = get_vi_for_tree (t);
+
+ for (p = arg_vi; p; p = p->next)
+ make_constraint_from (p, nonlocal_id);
+ }
+ }
+
+ /* Add a constraint for a result decl that is passed by reference. */
+ if (DECL_RESULT (cfun->decl)
+ && DECL_BY_REFERENCE (DECL_RESULT (cfun->decl)))
+ {
+ varinfo_t p, result_vi = get_vi_for_tree (DECL_RESULT (cfun->decl));
+
+ for (p = result_vi; p; p = p->next)
+ make_constraint_from (p, nonlocal_id);
+ }
+
+ /* Add a constraint for the incoming static chain parameter. */
+ if (cfun->static_chain_decl != NULL_TREE)
+ {
+ varinfo_t p, chain_vi = get_vi_for_tree (cfun->static_chain_decl);
+
+ for (p = chain_vi; p; p = p->next)
+ make_constraint_from (p, nonlocal_id);
+ }
+}
+
+/* Structure used to put solution bitmaps in a hashtable so they can
+ be shared among variables with the same points-to set. */
+
+typedef struct shared_bitmap_info
+{
+ bitmap pt_vars;
+ hashval_t hashcode;
+} *shared_bitmap_info_t;
+typedef const struct shared_bitmap_info *const_shared_bitmap_info_t;
+
+static htab_t shared_bitmap_table;
+
+/* Hash function for a shared_bitmap_info_t */
+
+static hashval_t
+shared_bitmap_hash (const void *p)
+{
+ const_shared_bitmap_info_t const bi = (const_shared_bitmap_info_t) p;
+ return bi->hashcode;
+}
+
+/* Equality function for two shared_bitmap_info_t's. */
+
+static int
+shared_bitmap_eq (const void *p1, const void *p2)
+{
+ const_shared_bitmap_info_t const sbi1 = (const_shared_bitmap_info_t) p1;
+ const_shared_bitmap_info_t const sbi2 = (const_shared_bitmap_info_t) p2;
+ return bitmap_equal_p (sbi1->pt_vars, sbi2->pt_vars);
+}
+
+/* Lookup a bitmap in the shared bitmap hashtable, and return an already
+ existing instance if there is one, NULL otherwise. */
+
+static bitmap
+shared_bitmap_lookup (bitmap pt_vars)
+{
+ void **slot;
+ struct shared_bitmap_info sbi;
+
+ sbi.pt_vars = pt_vars;
+ sbi.hashcode = bitmap_hash (pt_vars);
+
+ slot = htab_find_slot_with_hash (shared_bitmap_table, &sbi,
+ sbi.hashcode, NO_INSERT);
+ if (!slot)
+ return NULL;
+ else
+ return ((shared_bitmap_info_t) *slot)->pt_vars;
+}
+
+
+/* Add a bitmap to the shared bitmap hashtable. */
+
+static void
+shared_bitmap_add (bitmap pt_vars)
+{
+ void **slot;
+ shared_bitmap_info_t sbi = XNEW (struct shared_bitmap_info);
+
+ sbi->pt_vars = pt_vars;
+ sbi->hashcode = bitmap_hash (pt_vars);
+
+ slot = htab_find_slot_with_hash (shared_bitmap_table, sbi,
+ sbi->hashcode, INSERT);
+ gcc_assert (!*slot);
+ *slot = (void *) sbi;
+}
+
+
+/* Set bits in INTO corresponding to the variable uids in solution set
+ FROM, which came from variable PTR.
+ For variables that are actually dereferenced, we also use type
+ based alias analysis to prune the points-to sets.
+ IS_DEREFED is true if PTR was directly dereferenced, which we use to
+ help determine whether we are we are allowed to prune using TBAA.
+ If NO_TBAA_PRUNING is true, we do not perform any TBAA pruning of
+ the from set. Returns the number of pruned variables. */
+
+static unsigned
+set_uids_in_ptset (tree ptr, bitmap into, bitmap from, bool is_derefed,
+ bool no_tbaa_pruning)
+{
+ unsigned int i;
+ bitmap_iterator bi;
+ unsigned pruned = 0;
+
+ gcc_assert (POINTER_TYPE_P (TREE_TYPE (ptr)));
+
+ EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
+ {
+ varinfo_t vi = get_varinfo (i);
+
+ /* The only artificial variables that are allowed in a may-alias
+ set are heap variables. */
+ if (vi->is_artificial_var && !vi->is_heap_var)
+ continue;
+
+ if (TREE_CODE (vi->decl) == VAR_DECL
+ || TREE_CODE (vi->decl) == PARM_DECL
+ || TREE_CODE (vi->decl) == RESULT_DECL)
+ {
+ /* Just add VI->DECL to the alias set.
+ Don't type prune artificial vars or points-to sets
+ for pointers that have not been dereferenced or with
+ type-based pruning disabled. */
+ if (vi->is_artificial_var
+ || !is_derefed
+ || no_tbaa_pruning
+ || vi->no_tbaa_pruning)
+ bitmap_set_bit (into, DECL_UID (vi->decl));
+ else
+ {
+ alias_set_type var_alias_set, mem_alias_set;
+ var_alias_set = get_alias_set (vi->decl);
+ mem_alias_set = get_alias_set (TREE_TYPE (TREE_TYPE (ptr)));
+ if (may_alias_p (SSA_NAME_VAR (ptr), mem_alias_set,
+ vi->decl, var_alias_set, true))
+ bitmap_set_bit (into, DECL_UID (vi->decl));
+ else
+ ++pruned;
+ }
+ }
+ }
+
+ return pruned;
+}
+
+
+static bool have_alias_info = false;
+
+/* Emit a note for the pointer initialization point DEF. */
+
+static void
+emit_pointer_definition (tree ptr, bitmap visited)
+{
+ gimple def = SSA_NAME_DEF_STMT (ptr);
+ if (gimple_code (def) == GIMPLE_PHI)
+ {
+ use_operand_p argp;
+ ssa_op_iter oi;
+
+ FOR_EACH_PHI_ARG (argp, def, oi, SSA_OP_USE)
+ {
+ tree arg = USE_FROM_PTR (argp);
+ if (TREE_CODE (arg) == SSA_NAME)
+ {
+ if (bitmap_set_bit (visited, SSA_NAME_VERSION (arg)))
+ emit_pointer_definition (arg, visited);
+ }
+ else
+ inform (0, "initialized from %qE", arg);
+ }
+ }
+ else if (!gimple_nop_p (def))
+ inform (gimple_location (def), "initialized from here");
+}
+
+/* Emit a strict aliasing warning for dereferencing the pointer PTR. */
+
+static void
+emit_alias_warning (tree ptr)
+{
+ gimple use;
+ imm_use_iterator ui;
+ bool warned = false;
+
+ FOR_EACH_IMM_USE_STMT (use, ui, ptr)
+ {
+ tree deref = NULL_TREE;
+
+ if (gimple_has_lhs (use))
+ {
+ tree lhs = get_base_address (gimple_get_lhs (use));
+ if (lhs
+ && INDIRECT_REF_P (lhs)
+ && TREE_OPERAND (lhs, 0) == ptr)
+ deref = lhs;
+ }
+ if (gimple_assign_single_p (use))
+ {
+ tree rhs = get_base_address (gimple_assign_rhs1 (use));
+ if (rhs
+ && INDIRECT_REF_P (rhs)
+ && TREE_OPERAND (rhs, 0) == ptr)
+ deref = rhs;
+ }
+ else if (is_gimple_call (use))
+ {
+ unsigned i;
+ for (i = 0; i < gimple_call_num_args (use); ++i)
+ {
+ tree op = get_base_address (gimple_call_arg (use, i));
+ if (op
+ && INDIRECT_REF_P (op)
+ && TREE_OPERAND (op, 0) == ptr)
+ deref = op;
+ }
+ }
+ if (deref
+ && !TREE_NO_WARNING (deref))
+ {
+ TREE_NO_WARNING (deref) = 1;
+ warned |= warning_at (gimple_location (use), OPT_Wstrict_aliasing,
+ "dereferencing pointer %qD does break "
+ "strict-aliasing rules", SSA_NAME_VAR (ptr));
+ }
+ }
+ if (warned)
+ {
+ bitmap visited = BITMAP_ALLOC (NULL);
+ emit_pointer_definition (ptr, visited);
+ BITMAP_FREE (visited);
+ }
+}
+
+/* Given a pointer variable P, fill in its points-to set, or return
+ false if we can't.
+ Rather than return false for variables that point-to anything, we
+ instead find the corresponding SMT, and merge in its aliases. In
+ addition to these aliases, we also set the bits for the SMT's
+ themselves and their subsets, as SMT's are still in use by
+ non-SSA_NAME's, and pruning may eliminate every one of their
+ aliases. In such a case, if we did not include the right set of
+ SMT's in the points-to set of the variable, we'd end up with
+ statements that do not conflict but should. */
+
+bool
+find_what_p_points_to (tree p)
+{
+ tree lookup_p = p;
+ varinfo_t vi;
+
+ if (!have_alias_info)
+ return false;
+
+ /* For parameters, get at the points-to set for the actual parm
+ decl. */
+ if (TREE_CODE (p) == SSA_NAME
+ && TREE_CODE (SSA_NAME_VAR (p)) == PARM_DECL
+ && SSA_NAME_IS_DEFAULT_DEF (p))
+ lookup_p = SSA_NAME_VAR (p);
+
+ vi = lookup_vi_for_tree (lookup_p);
+ if (vi)
+ {
+ if (vi->is_artificial_var)
+ return false;
+
+ /* See if this is a field or a structure. */
+ if (vi->size != vi->fullsize)
+ {
+ /* Nothing currently asks about structure fields directly,
+ but when they do, we need code here to hand back the
+ points-to set. */
+ return false;
+ }
+ else
+ {
+ struct ptr_info_def *pi = get_ptr_info (p);
+ unsigned int i, pruned;
+ bitmap_iterator bi;
+ bool was_pt_anything = false;
+ bitmap finished_solution;
+ bitmap result;
+
+ if (!pi->memory_tag_needed)
+ return false;
+
+ /* This variable may have been collapsed, let's get the real
+ variable. */
+ vi = get_varinfo (find (vi->id));
+
+ /* Translate artificial variables into SSA_NAME_PTR_INFO
+ attributes. */
+ EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
+ {
+ varinfo_t vi = get_varinfo (i);
+
+ if (vi->is_artificial_var)
+ {
+ /* FIXME. READONLY should be handled better so that
+ flow insensitive aliasing can disregard writable
+ aliases. */
+ if (vi->id == nothing_id)
+ pi->pt_null = 1;
+ else if (vi->id == anything_id
+ || vi->id == nonlocal_id
+ || vi->id == escaped_id
+ || vi->id == callused_id)
+ was_pt_anything = 1;
+ else if (vi->id == readonly_id)
+ was_pt_anything = 1;
+ else if (vi->id == integer_id)
+ was_pt_anything = 1;
+ else if (vi->is_heap_var)
+ pi->pt_global_mem = 1;
+ }
+ }
+
+ /* Instead of doing extra work, simply do not create
+ points-to information for pt_anything pointers. This
+ will cause the operand scanner to fall back to the
+ type-based SMT and its aliases. Which is the best
+ we could do here for the points-to set as well. */
+ if (was_pt_anything)
+ return false;
+
+ /* Share the final set of variables when possible. */
+ finished_solution = BITMAP_GGC_ALLOC ();
+ stats.points_to_sets_created++;
+
+ pruned = set_uids_in_ptset (p, finished_solution, vi->solution,
+ pi->is_dereferenced,
+ vi->no_tbaa_pruning);
+ result = shared_bitmap_lookup (finished_solution);
+
+ if (!result)
+ {
+ shared_bitmap_add (finished_solution);
+ pi->pt_vars = finished_solution;
+ }
+ else
+ {
+ pi->pt_vars = result;
+ bitmap_clear (finished_solution);
+ }
+
+ if (bitmap_empty_p (pi->pt_vars))
+ {
+ pi->pt_vars = NULL;
+ if (pruned > 0
+ && !pi->pt_null
+ && pi->is_dereferenced
+ && warn_strict_aliasing > 0
+ && !SSA_NAME_IS_DEFAULT_DEF (p))
+ {
+ if (dump_file && dump_flags & TDF_DETAILS)
+ {
+ fprintf (dump_file, "alias warning for ");
+ print_generic_expr (dump_file, p, 0);
+ fprintf (dump_file, "\n");
+ }
+ emit_alias_warning (p);
+ }
+ }
+
+ return true;
+ }
+ }
+
+ return false;
+}
+
+/* Mark the ESCAPED solution as call clobbered. Returns false if
+ pt_anything escaped which needs all locals that have their address
+ taken marked call clobbered as well. */
+
+bool
+clobber_what_escaped (void)
+{
+ varinfo_t vi;
+ unsigned int i;
+ bitmap_iterator bi;
+
+ if (!have_alias_info)
+ return false;
+
+ /* This variable may have been collapsed, let's get the real
+ variable for escaped_id. */
+ vi = get_varinfo (find (escaped_id));
+
+ /* If call-used memory escapes we need to include it in the
+ set of escaped variables. This can happen if a pure
+ function returns a pointer and this pointer escapes. */
+ if (bitmap_bit_p (vi->solution, callused_id))
+ {
+ varinfo_t cu_vi = get_varinfo (find (callused_id));
+ bitmap_ior_into (vi->solution, cu_vi->solution);
+ }
+
+ /* Mark variables in the solution call-clobbered. */
+ EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
+ {
+ varinfo_t vi = get_varinfo (i);
+
+ if (vi->is_artificial_var)
+ {
+ /* nothing_id and readonly_id do not cause any
+ call clobber ops. For anything_id and integer_id
+ we need to clobber all addressable vars. */
+ if (vi->id == anything_id
+ || vi->id == integer_id)
+ return false;
+ }
+
+ /* Only artificial heap-vars are further interesting. */
+ if (vi->is_artificial_var && !vi->is_heap_var)
+ continue;
+
+ if ((TREE_CODE (vi->decl) == VAR_DECL
+ || TREE_CODE (vi->decl) == PARM_DECL
+ || TREE_CODE (vi->decl) == RESULT_DECL)
+ && !unmodifiable_var_p (vi->decl))
+ mark_call_clobbered (vi->decl, ESCAPE_TO_CALL);
+ }
+
+ return true;
+}
+
+/* Compute the call-used variables. */
+
+void
+compute_call_used_vars (void)
+{
+ varinfo_t vi;
+ unsigned int i;
+ bitmap_iterator bi;
+ bool has_anything_id = false;
+
+ if (!have_alias_info)
+ return;
+
+ /* This variable may have been collapsed, let's get the real
+ variable for escaped_id. */
+ vi = get_varinfo (find (callused_id));
+
+ /* Mark variables in the solution call-clobbered. */
+ EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
+ {
+ varinfo_t vi = get_varinfo (i);
+
+ if (vi->is_artificial_var)
+ {
+ /* For anything_id and integer_id we need to make
+ all local addressable vars call-used. */
+ if (vi->id == anything_id
+ || vi->id == integer_id)
+ has_anything_id = true;
+ }
+
+ /* Only artificial heap-vars are further interesting. */
+ if (vi->is_artificial_var && !vi->is_heap_var)
+ continue;
+
+ if ((TREE_CODE (vi->decl) == VAR_DECL
+ || TREE_CODE (vi->decl) == PARM_DECL
+ || TREE_CODE (vi->decl) == RESULT_DECL)
+ && !unmodifiable_var_p (vi->decl))
+ bitmap_set_bit (gimple_call_used_vars (cfun), DECL_UID (vi->decl));
+ }
+
+ /* If anything is call-used, add all addressable locals to the set. */
+ if (has_anything_id)
+ bitmap_ior_into (gimple_call_used_vars (cfun),
+ gimple_addressable_vars (cfun));
+}
+
+
+/* Dump points-to information to OUTFILE. */
+
+void
+dump_sa_points_to_info (FILE *outfile)
+{
+ unsigned int i;
+
+ fprintf (outfile, "\nPoints-to sets\n\n");
+
+ if (dump_flags & TDF_STATS)
+ {
+ fprintf (outfile, "Stats:\n");
+ fprintf (outfile, "Total vars: %d\n", stats.total_vars);
+ fprintf (outfile, "Non-pointer vars: %d\n",
+ stats.nonpointer_vars);
+ fprintf (outfile, "Statically unified vars: %d\n",
+ stats.unified_vars_static);
+ fprintf (outfile, "Dynamically unified vars: %d\n",
+ stats.unified_vars_dynamic);
+ fprintf (outfile, "Iterations: %d\n", stats.iterations);
+ fprintf (outfile, "Number of edges: %d\n", stats.num_edges);
+ fprintf (outfile, "Number of implicit edges: %d\n",
+ stats.num_implicit_edges);
+ }
+
+ for (i = 0; i < VEC_length (varinfo_t, varmap); i++)
+ dump_solution_for_var (outfile, i);
+}
+
+
+/* Debug points-to information to stderr. */
+
+void
+debug_sa_points_to_info (void)
+{
+ dump_sa_points_to_info (stderr);
+}
+
+
+/* Initialize the always-existing constraint variables for NULL
+ ANYTHING, READONLY, and INTEGER */
+
+static void
+init_base_vars (void)
+{
+ struct constraint_expr lhs, rhs;
+
+ /* Create the NULL variable, used to represent that a variable points
+ to NULL. */
+ nothing_tree = create_tmp_var_raw (void_type_node, "NULL");
+ var_nothing = new_var_info (nothing_tree, nothing_id, "NULL");
+ insert_vi_for_tree (nothing_tree, var_nothing);
+ var_nothing->is_artificial_var = 1;
+ var_nothing->offset = 0;
+ var_nothing->size = ~0;
+ var_nothing->fullsize = ~0;
+ var_nothing->is_special_var = 1;
+ VEC_safe_push (varinfo_t, heap, varmap, var_nothing);
+
+ /* Create the ANYTHING variable, used to represent that a variable
+ points to some unknown piece of memory. */
+ anything_tree = create_tmp_var_raw (void_type_node, "ANYTHING");
+ var_anything = new_var_info (anything_tree, anything_id, "ANYTHING");
+ insert_vi_for_tree (anything_tree, var_anything);
+ var_anything->is_artificial_var = 1;
+ var_anything->size = ~0;
+ var_anything->offset = 0;
+ var_anything->next = NULL;
+ var_anything->fullsize = ~0;
+ var_anything->is_special_var = 1;
+
+ /* Anything points to anything. This makes deref constraints just
+ work in the presence of linked list and other p = *p type loops,
+ by saying that *ANYTHING = ANYTHING. */
+ VEC_safe_push (varinfo_t, heap, varmap, var_anything);
+ lhs.type = SCALAR;
+ lhs.var = anything_id;
+ lhs.offset = 0;
+ rhs.type = ADDRESSOF;
+ rhs.var = anything_id;
+ rhs.offset = 0;
+
+ /* This specifically does not use process_constraint because
+ process_constraint ignores all anything = anything constraints, since all
+ but this one are redundant. */
+ VEC_safe_push (constraint_t, heap, constraints, new_constraint (lhs, rhs));
+
+ /* Create the READONLY variable, used to represent that a variable
+ points to readonly memory. */
+ readonly_tree = create_tmp_var_raw (void_type_node, "READONLY");
+ var_readonly = new_var_info (readonly_tree, readonly_id, "READONLY");
+ var_readonly->is_artificial_var = 1;
+ var_readonly->offset = 0;
+ var_readonly->size = ~0;
+ var_readonly->fullsize = ~0;
+ var_readonly->next = NULL;
+ var_readonly->is_special_var = 1;
+ insert_vi_for_tree (readonly_tree, var_readonly);
+ VEC_safe_push (varinfo_t, heap, varmap, var_readonly);
+
+ /* readonly memory points to anything, in order to make deref
+ easier. In reality, it points to anything the particular
+ readonly variable can point to, but we don't track this
+ separately. */
+ lhs.type = SCALAR;
+ lhs.var = readonly_id;
+ lhs.offset = 0;
+ rhs.type = ADDRESSOF;
+ rhs.var = readonly_id; /* FIXME */
+ rhs.offset = 0;
+ process_constraint (new_constraint (lhs, rhs));
+
+ /* Create the ESCAPED variable, used to represent the set of escaped
+ memory. */
+ escaped_tree = create_tmp_var_raw (void_type_node, "ESCAPED");
+ var_escaped = new_var_info (escaped_tree, escaped_id, "ESCAPED");
+ insert_vi_for_tree (escaped_tree, var_escaped);
+ var_escaped->is_artificial_var = 1;
+ var_escaped->offset = 0;
+ var_escaped->size = ~0;
+ var_escaped->fullsize = ~0;
+ var_escaped->is_special_var = 0;
+ VEC_safe_push (varinfo_t, heap, varmap, var_escaped);
+ gcc_assert (VEC_index (varinfo_t, varmap, 3) == var_escaped);
+
+ /* ESCAPED = *ESCAPED, because escaped is may-deref'd at calls, etc. */
+ lhs.type = SCALAR;
+ lhs.var = escaped_id;
+ lhs.offset = 0;
+ rhs.type = DEREF;
+ rhs.var = escaped_id;
+ rhs.offset = 0;
+ process_constraint (new_constraint (lhs, rhs));
+
+ /* Create the NONLOCAL variable, used to represent the set of nonlocal
+ memory. */
+ nonlocal_tree = create_tmp_var_raw (void_type_node, "NONLOCAL");
+ var_nonlocal = new_var_info (nonlocal_tree, nonlocal_id, "NONLOCAL");
+ insert_vi_for_tree (nonlocal_tree, var_nonlocal);
+ var_nonlocal->is_artificial_var = 1;
+ var_nonlocal->offset = 0;
+ var_nonlocal->size = ~0;
+ var_nonlocal->fullsize = ~0;
+ var_nonlocal->is_special_var = 1;
+ VEC_safe_push (varinfo_t, heap, varmap, var_nonlocal);
+
+ /* Nonlocal memory points to escaped (which includes nonlocal),
+ in order to make deref easier. */
+ lhs.type = SCALAR;
+ lhs.var = nonlocal_id;
+ lhs.offset = 0;
+ rhs.type = ADDRESSOF;
+ rhs.var = escaped_id;
+ rhs.offset = 0;
+ process_constraint (new_constraint (lhs, rhs));
+
+ /* Create the CALLUSED variable, used to represent the set of call-used
+ memory. */
+ callused_tree = create_tmp_var_raw (void_type_node, "CALLUSED");
+ var_callused = new_var_info (callused_tree, callused_id, "CALLUSED");
+ insert_vi_for_tree (callused_tree, var_callused);
+ var_callused->is_artificial_var = 1;
+ var_callused->offset = 0;
+ var_callused->size = ~0;
+ var_callused->fullsize = ~0;
+ var_callused->is_special_var = 0;
+ VEC_safe_push (varinfo_t, heap, varmap, var_callused);
+
+ /* CALLUSED = *CALLUSED, because call-used is may-deref'd at calls, etc. */
+ lhs.type = SCALAR;
+ lhs.var = callused_id;
+ lhs.offset = 0;
+ rhs.type = DEREF;
+ rhs.var = callused_id;
+ rhs.offset = 0;
+ process_constraint (new_constraint (lhs, rhs));
+
+ /* Create the STOREDANYTHING variable, used to represent the set of
+ variables stored to *ANYTHING. */
+ storedanything_tree = create_tmp_var_raw (ptr_type_node, "STOREDANYTHING");
+ var_storedanything = new_var_info (storedanything_tree, storedanything_id,
+ "STOREDANYTHING");
+ insert_vi_for_tree (storedanything_tree, var_storedanything);
+ var_storedanything->is_artificial_var = 1;
+ var_storedanything->offset = 0;
+ var_storedanything->size = ~0;
+ var_storedanything->fullsize = ~0;
+ var_storedanything->is_special_var = 0;
+ VEC_safe_push (varinfo_t, heap, varmap, var_storedanything);
+
+ /* Create the INTEGER variable, used to represent that a variable points
+ to an INTEGER. */
+ integer_tree = create_tmp_var_raw (void_type_node, "INTEGER");
+ var_integer = new_var_info (integer_tree, integer_id, "INTEGER");
+ insert_vi_for_tree (integer_tree, var_integer);
+ var_integer->is_artificial_var = 1;
+ var_integer->size = ~0;
+ var_integer->fullsize = ~0;
+ var_integer->offset = 0;
+ var_integer->next = NULL;
+ var_integer->is_special_var = 1;
+ VEC_safe_push (varinfo_t, heap, varmap, var_integer);
+
+ /* INTEGER = ANYTHING, because we don't know where a dereference of
+ a random integer will point to. */
+ lhs.type = SCALAR;
+ lhs.var = integer_id;
+ lhs.offset = 0;
+ rhs.type = ADDRESSOF;
+ rhs.var = anything_id;
+ rhs.offset = 0;
+ process_constraint (new_constraint (lhs, rhs));
+
+ /* *ESCAPED = &ESCAPED. This is true because we have to assume
+ everything pointed to by escaped can also point to escaped. */
+ lhs.type = DEREF;
+ lhs.var = escaped_id;
+ lhs.offset = 0;
+ rhs.type = ADDRESSOF;
+ rhs.var = escaped_id;
+ rhs.offset = 0;
+ process_constraint (new_constraint (lhs, rhs));
+
+ /* *ESCAPED = &NONLOCAL. This is true because we have to assume
+ everything pointed to by escaped can also point to nonlocal. */
+ lhs.type = DEREF;
+ lhs.var = escaped_id;
+ lhs.offset = 0;
+ rhs.type = ADDRESSOF;
+ rhs.var = nonlocal_id;
+ rhs.offset = 0;
+ process_constraint (new_constraint (lhs, rhs));
+}
+
+/* Initialize things necessary to perform PTA */
+
+static void
+init_alias_vars (void)
+{
+ use_field_sensitive = (MAX_FIELDS_FOR_FIELD_SENSITIVE > 1);
+
+ bitmap_obstack_initialize (&pta_obstack);
+ bitmap_obstack_initialize (&oldpta_obstack);
+ bitmap_obstack_initialize (&predbitmap_obstack);
+
+ constraint_pool = create_alloc_pool ("Constraint pool",
+ sizeof (struct constraint), 30);
+ variable_info_pool = create_alloc_pool ("Variable info pool",
+ sizeof (struct variable_info), 30);
+ constraints = VEC_alloc (constraint_t, heap, 8);
+ varmap = VEC_alloc (varinfo_t, heap, 8);
+ vi_for_tree = pointer_map_create ();
+
+ memset (&stats, 0, sizeof (stats));
+ shared_bitmap_table = htab_create (511, shared_bitmap_hash,
+ shared_bitmap_eq, free);
+ init_base_vars ();
+}
+
+/* Remove the REF and ADDRESS edges from GRAPH, as well as all the
+ predecessor edges. */
+
+static void
+remove_preds_and_fake_succs (constraint_graph_t graph)
+{
+ unsigned int i;
+
+ /* Clear the implicit ref and address nodes from the successor
+ lists. */
+ for (i = 0; i < FIRST_REF_NODE; i++)
+ {
+ if (graph->succs[i])
+ bitmap_clear_range (graph->succs[i], FIRST_REF_NODE,
+ FIRST_REF_NODE * 2);
+ }
+
+ /* Free the successor list for the non-ref nodes. */
+ for (i = FIRST_REF_NODE; i < graph->size; i++)
+ {
+ if (graph->succs[i])
+ BITMAP_FREE (graph->succs[i]);
+ }
+
+ /* Now reallocate the size of the successor list as, and blow away
+ the predecessor bitmaps. */
+ graph->size = VEC_length (varinfo_t, varmap);
+ graph->succs = XRESIZEVEC (bitmap, graph->succs, graph->size);
+
+ free (graph->implicit_preds);
+ graph->implicit_preds = NULL;
+ free (graph->preds);
+ graph->preds = NULL;
+ bitmap_obstack_release (&predbitmap_obstack);
+}
+
+/* Compute the set of variables we can't TBAA prune. */
+
+static void
+compute_tbaa_pruning (void)
+{
+ unsigned int size = VEC_length (varinfo_t, varmap);
+ unsigned int i;
+ bool any;
+
+ changed_count = 0;
+ changed = sbitmap_alloc (size);
+ sbitmap_zero (changed);
+
+ /* Mark all initial no_tbaa_pruning nodes as changed. */
+ any = false;
+ for (i = 0; i < size; ++i)
+ {
+ varinfo_t ivi = get_varinfo (i);
+
+ if (find (i) == i && ivi->no_tbaa_pruning)
+ {
+ any = true;
+ if ((graph->succs[i] && !bitmap_empty_p (graph->succs[i]))
+ || VEC_length (constraint_t, graph->complex[i]) > 0)
+ {
+ SET_BIT (changed, i);
+ ++changed_count;
+ }
+ }
+ }
+
+ while (changed_count > 0)
+ {
+ struct topo_info *ti = init_topo_info ();
+ ++stats.iterations;
+
+ compute_topo_order (graph, ti);
+
+ while (VEC_length (unsigned, ti->topo_order) != 0)
+ {
+ bitmap_iterator bi;
+
+ i = VEC_pop (unsigned, ti->topo_order);
+
+ /* If this variable is not a representative, skip it. */
+ if (find (i) != i)
+ continue;
+
+ /* If the node has changed, we need to process the complex
+ constraints and outgoing edges again. */
+ if (TEST_BIT (changed, i))
+ {
+ unsigned int j;
+ constraint_t c;
+ VEC(constraint_t,heap) *complex = graph->complex[i];
+
+ RESET_BIT (changed, i);
+ --changed_count;
+
+ /* Process the complex copy constraints. */
+ for (j = 0; VEC_iterate (constraint_t, complex, j, c); ++j)
+ {
+ if (c->lhs.type == SCALAR && c->rhs.type == SCALAR)
+ {
+ varinfo_t lhsvi = get_varinfo (find (c->lhs.var));
+
+ if (!lhsvi->no_tbaa_pruning)
+ {
+ lhsvi->no_tbaa_pruning = true;
+ if (!TEST_BIT (changed, lhsvi->id))
+ {
+ SET_BIT (changed, lhsvi->id);
+ ++changed_count;
+ }
+ }
+ }
+ }
+
+ /* Propagate to all successors. */
+ EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i], 0, j, bi)
+ {
+ unsigned int to = find (j);
+ varinfo_t tovi = get_varinfo (to);
+
+ /* Don't propagate to ourselves. */
+ if (to == i)
+ continue;
+
+ if (!tovi->no_tbaa_pruning)
+ {
+ tovi->no_tbaa_pruning = true;
+ if (!TEST_BIT (changed, to))
+ {
+ SET_BIT (changed, to);
+ ++changed_count;
+ }
+ }
+ }
+ }
+ }
+
+ free_topo_info (ti);
+ }
+
+ sbitmap_free (changed);
+
+ if (any)
+ {
+ for (i = 0; i < size; ++i)
+ {
+ varinfo_t ivi = get_varinfo (i);
+ varinfo_t ivip = get_varinfo (find (i));
+
+ if (ivip->no_tbaa_pruning)
+ {
+ tree var = ivi->decl;
+
+ if (TREE_CODE (var) == SSA_NAME)
+ var = SSA_NAME_VAR (var);
+
+ if (POINTER_TYPE_P (TREE_TYPE (var)))
+ {
+ DECL_NO_TBAA_P (var) = 1;
+
+ /* Tell the RTL layer that this pointer can alias
+ anything. */
+ DECL_POINTER_ALIAS_SET (var) = 0;
+ }
+ }
+ }
+ }
+}
+
+/* Create points-to sets for the current function. See the comments
+ at the start of the file for an algorithmic overview. */
+
+void
+compute_points_to_sets (void)
+{
+ struct scc_info *si;
+ basic_block bb;
+
+ timevar_push (TV_TREE_PTA);
+
+ init_alias_vars ();
+ init_alias_heapvars ();
+
+ intra_create_variable_infos ();
+
+ /* Now walk all statements and derive aliases. */
+ FOR_EACH_BB (bb)
+ {
+ gimple_stmt_iterator gsi;
+
+ for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ {
+ gimple phi = gsi_stmt (gsi);
+
+ if (is_gimple_reg (gimple_phi_result (phi)))
+ find_func_aliases (phi);
+ }
+
+ for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ find_func_aliases (gsi_stmt (gsi));
+ }
+
+
+ if (dump_file)
+ {
+ fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
+ dump_constraints (dump_file);
+ }
+
+ if (dump_file)
+ fprintf (dump_file,
+ "\nCollapsing static cycles and doing variable "
+ "substitution\n");
+
+ init_graph (VEC_length (varinfo_t, varmap) * 2);
+
+ if (dump_file)
+ fprintf (dump_file, "Building predecessor graph\n");
+ build_pred_graph ();
+
+ if (dump_file)
+ fprintf (dump_file, "Detecting pointer and location "
+ "equivalences\n");
+ si = perform_var_substitution (graph);
+
+ if (dump_file)
+ fprintf (dump_file, "Rewriting constraints and unifying "
+ "variables\n");
+ rewrite_constraints (graph, si);
+
+ build_succ_graph ();
+ free_var_substitution_info (si);
+
+ if (dump_file && (dump_flags & TDF_GRAPH))
+ dump_constraint_graph (dump_file);
+
+ move_complex_constraints (graph);
+
+ if (dump_file)
+ fprintf (dump_file, "Uniting pointer but not location equivalent "
+ "variables\n");
+ unite_pointer_equivalences (graph);
+
+ if (dump_file)
+ fprintf (dump_file, "Finding indirect cycles\n");
+ find_indirect_cycles (graph);
+
+ /* Implicit nodes and predecessors are no longer necessary at this
+ point. */
+ remove_preds_and_fake_succs (graph);
+
+ if (dump_file)
+ fprintf (dump_file, "Solving graph\n");
+
+ solve_graph (graph);
+
+ compute_tbaa_pruning ();
+
+ if (dump_file)
+ dump_sa_points_to_info (dump_file);
+
+ have_alias_info = true;
+
+ timevar_pop (TV_TREE_PTA);
+}
+
+
+/* Delete created points-to sets. */
+
+void
+delete_points_to_sets (void)
+{
+ unsigned int i;
+
+ htab_delete (shared_bitmap_table);
+ if (dump_file && (dump_flags & TDF_STATS))
+ fprintf (dump_file, "Points to sets created:%d\n",
+ stats.points_to_sets_created);
+
+ pointer_map_destroy (vi_for_tree);
+ bitmap_obstack_release (&pta_obstack);
+ VEC_free (constraint_t, heap, constraints);
+
+ for (i = 0; i < graph->size; i++)
+ VEC_free (constraint_t, heap, graph->complex[i]);
+ free (graph->complex);
+
+ free (graph->rep);
+ free (graph->succs);
+ free (graph->pe);
+ free (graph->pe_rep);
+ free (graph->indirect_cycles);
+ free (graph);
+
+ VEC_free (varinfo_t, heap, varmap);
+ free_alloc_pool (variable_info_pool);
+ free_alloc_pool (constraint_pool);
+ have_alias_info = false;
+}
+
+/* Return true if we should execute IPA PTA. */
+static bool
+gate_ipa_pta (void)
+{
+ return (flag_ipa_pta
+ /* Don't bother doing anything if the program has errors. */
+ && !(errorcount || sorrycount));
+}
+
+/* Execute the driver for IPA PTA. */
+static unsigned int
+ipa_pta_execute (void)
+{
+ struct cgraph_node *node;
+ struct scc_info *si;
+
+ in_ipa_mode = 1;
+ init_alias_heapvars ();
+ init_alias_vars ();
+
+ for (node = cgraph_nodes; node; node = node->next)
+ {
+ if (!node->analyzed || cgraph_is_master_clone (node))
+ {
+ unsigned int varid;
+
+ varid = create_function_info_for (node->decl,
+ cgraph_node_name (node));
+ if (node->local.externally_visible)
+ {
+ varinfo_t fi = get_varinfo (varid);
+ for (; fi; fi = fi->next)
+ make_constraint_from (fi, anything_id);
+ }
+ }
+ }
+ for (node = cgraph_nodes; node; node = node->next)
+ {
+ if (node->analyzed && cgraph_is_master_clone (node))
+ {
+ struct function *func = DECL_STRUCT_FUNCTION (node->decl);
+ basic_block bb;
+ tree old_func_decl = current_function_decl;
+ if (dump_file)
+ fprintf (dump_file,
+ "Generating constraints for %s\n",
+ cgraph_node_name (node));
+ push_cfun (func);
+ current_function_decl = node->decl;
+
+ FOR_EACH_BB_FN (bb, func)
+ {
+ gimple_stmt_iterator gsi;
+
+ for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
+ gsi_next (&gsi))
+ {
+ gimple phi = gsi_stmt (gsi);
+
+ if (is_gimple_reg (gimple_phi_result (phi)))
+ find_func_aliases (phi);
+ }
+
+ for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ find_func_aliases (gsi_stmt (gsi));
+ }
+ current_function_decl = old_func_decl;
+ pop_cfun ();
+ }
+ else
+ {
+ /* Make point to anything. */
+ }
+ }
+
+ if (dump_file)
+ {
+ fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
+ dump_constraints (dump_file);
+ }
+
+ if (dump_file)
+ fprintf (dump_file,
+ "\nCollapsing static cycles and doing variable "
+ "substitution:\n");
+
+ init_graph (VEC_length (varinfo_t, varmap) * 2);
+ build_pred_graph ();
+ si = perform_var_substitution (graph);
+ rewrite_constraints (graph, si);
+
+ build_succ_graph ();
+ free_var_substitution_info (si);
+ move_complex_constraints (graph);
+ unite_pointer_equivalences (graph);
+ find_indirect_cycles (graph);
+
+ /* Implicit nodes and predecessors are no longer necessary at this
+ point. */
+ remove_preds_and_fake_succs (graph);
+
+ if (dump_file)
+ fprintf (dump_file, "\nSolving graph\n");
+
+ solve_graph (graph);
+
+ if (dump_file)
+ dump_sa_points_to_info (dump_file);
+
+ in_ipa_mode = 0;
+ delete_alias_heapvars ();
+ delete_points_to_sets ();
+ return 0;
+}
+
+struct simple_ipa_opt_pass pass_ipa_pta =
+{
+ {
+ SIMPLE_IPA_PASS,
+ "pta", /* name */
+ gate_ipa_pta, /* gate */
+ ipa_pta_execute, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ TV_IPA_PTA, /* tv_id */
+ 0, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_update_ssa /* todo_flags_finish */
+ }
+};
+
+/* Initialize the heapvar for statement mapping. */
+void
+init_alias_heapvars (void)
+{
+ if (!heapvar_for_stmt)
+ heapvar_for_stmt = htab_create_ggc (11, tree_map_hash, tree_map_eq,
+ NULL);
+}
+
+void
+delete_alias_heapvars (void)
+{
+ htab_delete (heapvar_for_stmt);
+ heapvar_for_stmt = NULL;
+}
+
+#include "gt-tree-ssa-structalias.h"
projects / msp430-gcc.git / blobdiff