aboutsummaryrefslogtreecommitdiffstats
path: root/gcc-4.8.1/gcc/tree-ssa-structalias.c
diff options
context:
space:
mode:
Diffstat (limited to 'gcc-4.8.1/gcc/tree-ssa-structalias.c')
-rw-r--r--gcc-4.8.1/gcc/tree-ssa-structalias.c7254
1 files changed, 0 insertions, 7254 deletions
diff --git a/gcc-4.8.1/gcc/tree-ssa-structalias.c b/gcc-4.8.1/gcc/tree-ssa-structalias.c
deleted file mode 100644
index 31a4c49c6..000000000
--- a/gcc-4.8.1/gcc/tree-ssa-structalias.c
+++ /dev/null
@@ -1,7254 +0,0 @@
-/* Tree based points-to analysis
- Copyright (C) 2005-2013 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 "basic-block.h"
-#include "tree.h"
-#include "tree-flow.h"
-#include "tree-inline.h"
-#include "diagnostic-core.h"
-#include "gimple.h"
-#include "hashtab.h"
-#include "function.h"
-#include "cgraph.h"
-#include "tree-pass.h"
-#include "alloc-pool.h"
-#include "splay-tree.h"
-#include "params.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. */
-
-/* IPA-PTA optimizations possible.
-
- When the indirect function called is ANYTHING we can add disambiguation
- based on the function signatures (or simply the parameter count which
- is the varinfo size). We also do not need to consider functions that
- do not have their address taken.
-
- The is_global_var bit which marks escape points is overly conservative
- in IPA mode. Split it to is_escape_point and is_global_var - only
- externally visible globals are escape points in IPA mode. This is
- also needed to fix the pt_solution_includes_global predicate
- (and thus ptr_deref_may_alias_global_p).
-
- The way we introduce DECL_PT_UID to avoid fixing up all points-to
- sets in the translation unit when we copy a DECL during inlining
- pessimizes precision. The advantage is that the DECL_PT_UID keeps
- compile-time and memory usage overhead low - the points-to sets
- do not grow or get unshared as they would during a fixup phase.
- An alternative solution is to delay IPA PTA until after all
- inlining transformations have been applied.
-
- The way we propagate clobber/use information isn't optimized.
- It should use a new complex constraint that properly filters
- out local variables of the callee (though that would make
- the sets invalid after inlining). OTOH we might as well
- admit defeat to WHOPR and simply do all the clobber/use analysis
- and propagation after PTA finished but before we threw away
- points-to information for memory variables. WHOPR and PTA
- do not play along well anyway - the whole constraint solving
- would need to be done in WPA phase and it will be very interesting
- to apply the results to local SSA names during LTRANS phase.
-
- We probably should compute a per-function unit-ESCAPE solution
- propagating it simply like the clobber / uses solutions. The
- solution can go alongside the non-IPA espaced solution and be
- used to query which vars escape the unit through a function.
-
- We never put function decls in points-to sets so we do not
- keep the set of called functions for indirect calls.
-
- And probably more. */
-
-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);
-
-struct constraint;
-typedef struct constraint *constraint_t;
-
-
-#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 this field may contain pointers. */
- unsigned int may_have_pointers : 1;
-
- /* True if this field has only restrict qualified pointers. */
- unsigned int only_restrict_pointers : 1;
-
- /* True if this represents a global variable. */
- unsigned int is_global_var : 1;
-
- /* True if this represents a IPA function info. */
- unsigned int is_fn_info : 1;
-
- /* 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 first_or_preceding_vi_for_offset (varinfo_t,
- unsigned HOST_WIDE_INT);
-static varinfo_t lookup_vi_for_tree (tree);
-static inline bool type_can_have_subvars (const_tree);
-
-/* Pool of variable info structures. */
-static alloc_pool variable_info_pool;
-
-/* Map varinfo to final pt_solution. */
-static pointer_map_t *final_solutions;
-struct obstack final_solutions_obstack;
-
-/* Table of variable info structures for constraint variables.
- Indexed directly by variable info id. */
-static vec<varinfo_t> varmap;
-
-/* Return the varmap element N */
-
-static inline varinfo_t
-get_varinfo (unsigned int n)
-{
- return varmap[n];
-}
-
-/* Static IDs for the special variables. */
-enum { nothing_id = 0, anything_id = 1, readonly_id = 2,
- escaped_id = 3, nonlocal_id = 4,
- storedanything_id = 5, integer_id = 6 };
-
-/* Return a new variable info structure consisting for a variable
- named NAME, and using constraint graph node NODE. Append it
- to the vector of variable info structures. */
-
-static varinfo_t
-new_var_info (tree t, const char *name)
-{
- unsigned index = varmap.length ();
- varinfo_t ret = (varinfo_t) pool_alloc (variable_info_pool);
-
- ret->id = index;
- ret->name = name;
- ret->decl = t;
- /* Vars without decl are artificial and do not have sub-variables. */
- ret->is_artificial_var = (t == NULL_TREE);
- ret->is_special_var = false;
- ret->is_unknown_size_var = false;
- ret->is_full_var = (t == NULL_TREE);
- ret->is_heap_var = false;
- ret->may_have_pointers = true;
- ret->only_restrict_pointers = false;
- ret->is_global_var = (t == NULL_TREE);
- ret->is_fn_info = false;
- if (t && DECL_P (t))
- ret->is_global_var = (is_global_var (t)
- /* We have to treat even local register variables
- as escape points. */
- || (TREE_CODE (t) == VAR_DECL
- && DECL_HARD_REGISTER (t)));
- ret->solution = BITMAP_ALLOC (&pta_obstack);
- ret->oldsolution = NULL;
- ret->next = NULL;
-
- stats.total_vars++;
-
- varmap.safe_push (ret);
-
- return ret;
-}
-
-
-/* A map mapping call statements to per-stmt variables for uses
- and clobbers specific to the call. */
-struct pointer_map_t *call_stmt_vars;
-
-/* Lookup or create the variable for the call statement CALL. */
-
-static varinfo_t
-get_call_vi (gimple call)
-{
- void **slot_p;
- varinfo_t vi, vi2;
-
- slot_p = pointer_map_insert (call_stmt_vars, call);
- if (*slot_p)
- return (varinfo_t) *slot_p;
-
- vi = new_var_info (NULL_TREE, "CALLUSED");
- vi->offset = 0;
- vi->size = 1;
- vi->fullsize = 2;
- vi->is_full_var = true;
-
- vi->next = vi2 = new_var_info (NULL_TREE, "CALLCLOBBERED");
- vi2->offset = 1;
- vi2->size = 1;
- vi2->fullsize = 2;
- vi2->is_full_var = true;
-
- *slot_p = (void *) vi;
- return vi;
-}
-
-/* Lookup the variable for the call statement CALL representing
- the uses. Returns NULL if there is nothing special about this call. */
-
-static varinfo_t
-lookup_call_use_vi (gimple call)
-{
- void **slot_p;
-
- slot_p = pointer_map_contains (call_stmt_vars, call);
- if (slot_p)
- return (varinfo_t) *slot_p;
-
- return NULL;
-}
-
-/* Lookup the variable for the call statement CALL representing
- the clobbers. Returns NULL if there is nothing special about this call. */
-
-static varinfo_t
-lookup_call_clobber_vi (gimple call)
-{
- varinfo_t uses = lookup_call_use_vi (call);
- if (!uses)
- return NULL;
-
- return uses->next;
-}
-
-/* Lookup or create the variable for the call statement CALL representing
- the uses. */
-
-static varinfo_t
-get_call_use_vi (gimple call)
-{
- return get_call_vi (call);
-}
-
-/* Lookup or create the variable for the call statement CALL representing
- the clobbers. */
-
-static varinfo_t ATTRIBUTE_UNUSED
-get_call_clobber_vi (gimple call)
-{
- return get_call_vi (call)->next;
-}
-
-
-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. */
- HOST_WIDE_INT offset;
-};
-
-/* Use 0x8000... as special unknown offset. */
-#define UNKNOWN_OFFSET ((HOST_WIDE_INT)-1 << (HOST_BITS_PER_WIDE_INT-1))
-
-typedef struct constraint_expr ce_s;
-static void get_constraint_for_1 (tree, vec<ce_s> *, bool, bool);
-static void get_constraint_for (tree, vec<ce_s> *);
-static void get_constraint_for_rhs (tree, vec<ce_s> *);
-static void do_deref (vec<ce_s> *);
-
-/* 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> constraints;
-static alloc_pool constraint_pool;
-
-/* 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> *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 (varmap).length ()
-#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. */
-
-static 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 (c->lhs.var)->name);
- if (c->lhs.offset == UNKNOWN_OFFSET)
- fprintf (file, " + UNKNOWN");
- else 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 (c->rhs.var)->name);
- if (c->rhs.offset == UNKNOWN_OFFSET)
- fprintf (file, " + UNKNOWN");
- else if (c->rhs.offset != 0)
- fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->rhs.offset);
-}
-
-
-void debug_constraint (constraint_t);
-void debug_constraints (void);
-void debug_constraint_graph (void);
-void debug_solution_for_var (unsigned int);
-void debug_sa_points_to_info (void);
-
-/* Print out constraint C to stderr. */
-
-DEBUG_FUNCTION void
-debug_constraint (constraint_t c)
-{
- dump_constraint (stderr, c);
- fprintf (stderr, "\n");
-}
-
-/* Print out all constraints to FILE */
-
-static void
-dump_constraints (FILE *file, int from)
-{
- int i;
- constraint_t c;
- for (i = from; constraints.iterate (i, &c); i++)
- if (c)
- {
- dump_constraint (file, c);
- fprintf (file, "\n");
- }
-}
-
-/* Print out all constraints to stderr. */
-
-DEBUG_FUNCTION void
-debug_constraints (void)
-{
- dump_constraints (stderr, 0);
-}
-
-/* Print the constraint graph in dot format. */
-
-static void
-dump_constraint_graph (FILE *file)
-{
- unsigned int i;
-
- /* Only print the graph if it has already been initialized: */
- if (!graph)
- return;
-
- /* Prints the header of the dot file: */
- 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 and complex constraints in "
- "the constraint graph:\n");
-
- /* The next lines print the nodes in the graph together with the
- complex constraints attached to them. */
- for (i = 0; i < graph->size; i++)
- {
- if (find (i) != i)
- continue;
- if (i < FIRST_REF_NODE)
- fprintf (file, "\"%s\"", get_varinfo (i)->name);
- else
- fprintf (file, "\"*%s\"", get_varinfo (i - FIRST_REF_NODE)->name);
- if (graph->complex[i].exists ())
- {
- unsigned j;
- constraint_t c;
- fprintf (file, " [label=\"\\N\\n");
- for (j = 0; graph->complex[i].iterate (j, &c); ++j)
- {
- dump_constraint (file, c);
- fprintf (file, "\\l");
- }
- fprintf (file, "\"]");
- }
- fprintf (file, ";\n");
- }
-
- /* Go over the edges. */
- fprintf (file, "\n // Edges in the constraint graph:\n");
- for (i = 0; i < graph->size; i++)
- {
- unsigned j;
- bitmap_iterator bi;
- if (find (i) != i)
- continue;
- EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i], 0, j, bi)
- {
- unsigned to = find (j);
- if (i == to)
- continue;
- if (i < FIRST_REF_NODE)
- fprintf (file, "\"%s\"", get_varinfo (i)->name);
- else
- fprintf (file, "\"*%s\"", get_varinfo (i - FIRST_REF_NODE)->name);
- fprintf (file, " -> ");
- if (to < FIRST_REF_NODE)
- fprintf (file, "\"%s\"", get_varinfo (to)->name);
- else
- fprintf (file, "\"*%s\"", get_varinfo (to - FIRST_REF_NODE)->name);
- fprintf (file, ";\n");
- }
- }
-
- /* Prints the tail of the dot file. */
- fprintf (file, "}\n");
-}
-
-/* Print out the constraint graph to stderr. */
-
-DEBUG_FUNCTION 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> vec,
- struct constraint lookfor)
-{
- unsigned int place;
- constraint_t found;
-
- if (!vec.exists ())
- return NULL;
-
- place = vec.lower_bound (&lookfor, constraint_less);
- if (place >= vec.length ())
- return NULL;
- found = 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> *to,
- vec<constraint_t> *from)
-{
- int i;
- constraint_t c;
-
- FOR_EACH_VEC_ELT (*from, i, c)
- {
- if (constraint_vec_find (*to, *c) == NULL)
- {
- unsigned int place = to->lower_bound (c, constraint_less);
- to->safe_insert (place, c);
- }
- }
-}
-
-/* Expands the solution in SET to all sub-fields of variables included.
- Union the expanded result into RESULT. */
-
-static void
-solution_set_expand (bitmap result, bitmap set)
-{
- bitmap_iterator bi;
- bitmap vars = NULL;
- unsigned j;
-
- /* In a first pass record all variables we need to add all
- sub-fields off. This avoids quadratic behavior. */
- EXECUTE_IF_SET_IN_BITMAP (set, 0, j, bi)
- {
- varinfo_t v = get_varinfo (j);
- if (v->is_artificial_var
- || v->is_full_var)
- continue;
- v = lookup_vi_for_tree (v->decl);
- 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)
- bitmap_set_bit (result, v->id);
- }
- BITMAP_FREE (vars);
- }
-}
-
-/* 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, HOST_WIDE_INT offset)
-{
- bitmap result = BITMAP_ALLOC (&iteration_obstack);
- unsigned int i;
- bitmap_iterator bi;
-
- /* If the offset is unknown we have to expand the solution to
- all subfields. */
- if (offset == UNKNOWN_OFFSET)
- {
- solution_set_expand (set, set);
- return;
- }
-
- 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;
-
- /* If the offset makes the pointer point to before the
- variable use offset zero for the field lookup. */
- if (offset < 0
- && fieldoffset > vi->offset)
- fieldoffset = 0;
-
- if (offset != 0)
- vi = first_or_preceding_vi_for_offset (vi, fieldoffset);
-
- bitmap_set_bit (result, vi->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 (vi->offset != fieldoffset
- && vi->next != NULL)
- bitmap_set_bit (result, vi->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, 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> complex = graph->complex[var];
- unsigned int place = complex.lower_bound (c, constraint_less);
-
- /* Only insert constraints that do not already exist. */
- if (place >= complex.length ()
- || !constraint_equal (*c, *complex[place]))
- graph->complex[var].safe_insert (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_EACH_VEC_ELT (graph->complex[from], i, c)
- {
- /* 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]);
- graph->complex[from].release ();
-}
-
-
-/* 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);
- /* ??? Macros do not support template types with multiple arguments,
- so we use a typedef to work around it. */
- typedef vec<constraint_t> vec_constraint_t_heap;
- 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);
- bitmap_clear (graph->direct_nodes);
-
- for (j = 0; j < FIRST_REF_NODE; j++)
- {
- if (!get_varinfo (j)->is_special_var)
- bitmap_set_bit (graph->direct_nodes, j);
- }
-
- for (j = 0; j < graph->size; j++)
- graph->eq_rep[j] = -1;
-
- for (j = 0; j < varmap.length (); j++)
- graph->indirect_cycles[j] = -1;
-
- FOR_EACH_VEC_ELT (constraints, i, c)
- {
- struct constraint_expr lhs = c->lhs;
- struct constraint_expr rhs = c->rhs;
- unsigned int lhsvar = lhs.var;
- unsigned int rhsvar = rhs.var;
-
- 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
- bitmap_clear_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. */
- bitmap_clear_bit (graph->direct_nodes, rhsvar);
- v = get_varinfo (rhsvar);
- if (!v->is_full_var)
- {
- v = lookup_vi_for_tree (v->decl);
- do
- {
- bitmap_clear_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)
- bitmap_clear_bit (graph->direct_nodes, lhs.var);
- else if (lhs.offset != 0)
- bitmap_clear_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_EACH_VEC_ELT (constraints, i, c)
- {
- 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 (lhs.var);
- rhsvar = find (rhs.var);
-
- 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 (rhs.var) == rhs.var);
- 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 that can
- receive pointers. */
- t = find (storedanything_id);
- for (i = integer_id + 1; i < FIRST_REF_NODE; ++i)
- {
- if (!bitmap_bit_p (graph->direct_nodes, i)
- && get_varinfo (i)->may_have_pointers)
- add_graph_edge (graph, find (i), t);
- }
-
- /* Everything stored to ANYTHING also potentially escapes. */
- add_graph_edge (graph, find (escaped_id), t);
-}
-
-
-/* Changed variables on the last iteration. */
-static bitmap changed;
-
-/* Strongly Connected Component visitation info. */
-
-struct scc_info
-{
- sbitmap visited;
- sbitmap deleted;
- unsigned int *dfs;
- unsigned int *node_mapping;
- int current_index;
- vec<unsigned> 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;
-
- bitmap_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 (bitmap_bit_p (si->deleted, w))
- continue;
-
- if (!bitmap_bit_p (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 (si->scc_stack.length () > 0
- && si->dfs[si->scc_stack.last ()] >= my_dfs)
- {
- bitmap scc = BITMAP_ALLOC (NULL);
- unsigned int lowest_node;
- bitmap_iterator bi;
-
- bitmap_set_bit (scc, n);
-
- while (si->scc_stack.length () != 0
- && si->dfs[si->scc_stack.last ()] >= my_dfs)
- {
- unsigned int w = si->scc_stack.pop ();
-
- bitmap_set_bit (scc, w);
- }
-
- 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;
- }
- }
- }
- bitmap_set_bit (si->deleted, n);
- }
- else
- si->scc_stack.safe_push (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);
-
- /* Mark TO as changed if FROM was changed. If TO was already marked
- as changed, decrease the changed count. */
-
- if (update_changed
- && bitmap_bit_p (changed, from))
- {
- bitmap_clear_bit (changed, from);
- bitmap_set_bit (changed, to);
- }
- 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)
- bitmap_set_bit (changed, to);
- }
-
- BITMAP_FREE (get_varinfo (from)->solution);
- if (get_varinfo (from)->oldsolution)
- BITMAP_FREE (get_varinfo (from)->oldsolution);
-
- if (stats.iterations > 0
- && get_varinfo (to)->oldsolution)
- BITMAP_FREE (get_varinfo (to)->oldsolution);
- }
- 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> 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);
- bitmap_clear (ti->visited);
- ti->topo_order.create (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);
- ti->topo_order.release ();
- 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;
-
- bitmap_set_bit (ti->visited, n);
-
- if (graph->succs[n])
- EXECUTE_IF_SET_IN_BITMAP (graph->succs[n], 0, j, bi)
- {
- if (!bitmap_bit_p (ti->visited, j))
- topo_visit (graph, ti, j);
- }
-
- ti->topo_order.safe_push (n);
-}
-
-/* Process a constraint C that represents x = *(y + off), using DELTA as the
- starting solution for y. */
-
-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;
- HOST_WIDE_INT roffset = c->rhs.offset;
-
- /* Our IL does not allow this. */
- gcc_assert (c->lhs.offset == 0);
-
- /* If the solution of Y contains anything it is good enough to transfer
- this to the LHS. */
- if (bitmap_bit_p (delta, anything_id))
- {
- flag |= bitmap_set_bit (sol, anything_id);
- goto done;
- }
-
- /* If we do not know at with offset the rhs is dereferenced compute
- the reachability set of DELTA, conservatively assuming it is
- dereferenced at all valid offsets. */
- if (roffset == UNKNOWN_OFFSET)
- {
- solution_set_expand (delta, delta);
- /* No further offset processing is necessary. */
- roffset = 0;
- }
-
- /* 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)
- {
- varinfo_t v = get_varinfo (j);
- HOST_WIDE_INT fieldoffset = v->offset + roffset;
- unsigned int t;
-
- if (v->is_full_var)
- fieldoffset = v->offset;
- else if (roffset != 0)
- v = first_vi_for_offset (v, fieldoffset);
- /* If the access is outside of the variable we can ignore it. */
- if (!v)
- continue;
-
- do
- {
- 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. */
- else if (v->id == escaped_id)
- flag |= bitmap_set_bit (sol, escaped_id);
- else if (v->may_have_pointers
- && add_graph_edge (graph, lhs, t))
- flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
-
- /* If the variable is not exactly at the requested offset
- we have to include the next one. */
- if (v->offset == (unsigned HOST_WIDE_INT)fieldoffset
- || v->next == NULL)
- break;
-
- v = v->next;
- fieldoffset = v->offset;
- }
- while (1);
- }
-
-done:
- /* If the LHS solution changed, mark the var as changed. */
- if (flag)
- {
- get_varinfo (lhs)->solution = sol;
- bitmap_set_bit (changed, lhs);
- }
-}
-
-/* Process a constraint C that represents *(x + off) = y using DELTA
- as the starting solution for x. */
-
-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;
- HOST_WIDE_INT loff = c->lhs.offset;
- bool escaped_p = false;
-
- /* 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))
- bitmap_set_bit (changed, t);
- }
- return;
- }
-
- /* If we do not know at with offset the rhs is dereferenced compute
- the reachability set of DELTA, conservatively assuming it is
- dereferenced at all valid offsets. */
- if (loff == UNKNOWN_OFFSET)
- {
- solution_set_expand (delta, delta);
- loff = 0;
- }
-
- /* 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)
- {
- varinfo_t v = get_varinfo (j);
- unsigned int t;
- HOST_WIDE_INT fieldoffset = v->offset + loff;
-
- if (v->is_full_var)
- fieldoffset = v->offset;
- else if (loff != 0)
- v = first_vi_for_offset (v, fieldoffset);
- /* If the access is outside of the variable we can ignore it. */
- if (!v)
- continue;
-
- do
- {
- if (v->may_have_pointers)
- {
- /* If v is a global variable then this is an escape point. */
- if (v->is_global_var
- && !escaped_p)
- {
- t = find (escaped_id);
- if (add_graph_edge (graph, t, rhs)
- && bitmap_ior_into (get_varinfo (t)->solution, sol))
- bitmap_set_bit (changed, t);
- /* Enough to let rhs escape once. */
- escaped_p = true;
- }
-
- if (v->is_special_var)
- break;
-
- t = find (v->id);
- if (add_graph_edge (graph, t, rhs)
- && bitmap_ior_into (get_varinfo (t)->solution, sol))
- bitmap_set_bit (changed, t);
- }
-
- /* If the variable is not exactly at the requested offset
- we have to include the next one. */
- if (v->offset == (unsigned HOST_WIDE_INT)fieldoffset
- || v->next == NULL)
- break;
-
- v = v->next;
- fieldoffset = v->offset;
- }
- while (1);
- }
-}
-
-/* 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;
- bitmap_set_bit (changed, c->lhs.var);
- }
- }
-}
-
-/* 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);
- bitmap_clear (si->visited);
- si->deleted = sbitmap_alloc (size);
- bitmap_clear (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.create (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);
- si->scc_stack.release ();
- 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 (!bitmap_bit_p (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 (!bitmap_bit_p (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 (eql1->hashcode == eql2->hashcode
- && bitmap_equal_p (eql1->labels, eql2->labels));
-}
-
-/* Lookup a equivalence class in TABLE by the bitmap of LABELS with
- hash HAS it contains. Sets *REF_LABELS to the bitmap LABELS
- is equivalent to. */
-
-static equiv_class_label *
-equiv_class_lookup_or_add (htab_t table, bitmap labels)
-{
- equiv_class_label **slot;
- equiv_class_label ecl;
-
- ecl.labels = labels;
- ecl.hashcode = bitmap_hash (labels);
- slot = (equiv_class_label **) htab_find_slot_with_hash (table, &ecl,
- ecl.hashcode, INSERT);
- if (!*slot)
- {
- *slot = XNEW (struct equiv_class_label);
- (*slot)->labels = labels;
- (*slot)->hashcode = ecl.hashcode;
- (*slot)->equivalence_class = 0;
- }
-
- return *slot;
-}
-
-/* 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);
- bitmap_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 (bitmap_bit_p (si->deleted, w))
- continue;
-
- if (!bitmap_bit_p (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 (bitmap_bit_p (si->deleted, w))
- continue;
-
- if (!bitmap_bit_p (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 (si->scc_stack.length () != 0
- && si->dfs[si->scc_stack.last ()] >= my_dfs)
- {
- unsigned int w = si->scc_stack.pop ();
- si->node_mapping[w] = n;
-
- if (!bitmap_bit_p (graph->direct_nodes, w))
- bitmap_clear_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]);
- }
- }
- bitmap_set_bit (si->deleted, n);
- }
- else
- si->scc_stack.safe_push (n);
-}
-
-/* Label pointer equivalences. */
-
-static void
-label_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
-{
- unsigned int i, first_pred;
- bitmap_iterator bi;
-
- bitmap_set_bit (si->visited, n);
-
- /* Label and union our incoming edges's points to sets. */
- first_pred = -1U;
- EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
- {
- unsigned int w = si->node_mapping[i];
- if (!bitmap_bit_p (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])
- {
- if (!graph->points_to[n])
- {
- if (first_pred == -1U)
- first_pred = w;
- else
- {
- graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
- bitmap_ior (graph->points_to[n],
- graph->points_to[first_pred],
- graph->points_to[w]);
- }
- }
- else
- bitmap_ior_into(graph->points_to[n], graph->points_to[w]);
- }
- }
-
- /* Indirect nodes get fresh variables and a new pointer equiv class. */
- if (!bitmap_bit_p (graph->direct_nodes, n))
- {
- if (!graph->points_to[n])
- {
- graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
- if (first_pred != -1U)
- bitmap_copy (graph->points_to[n], graph->points_to[first_pred]);
- }
- bitmap_set_bit (graph->points_to[n], FIRST_REF_NODE + n);
- graph->pointer_label[n] = pointer_equiv_class++;
- equiv_class_label_t ecl;
- ecl = equiv_class_lookup_or_add (pointer_equiv_class_table,
- graph->points_to[n]);
- ecl->equivalence_class = graph->pointer_label[n];
- return;
- }
-
- /* If there was only a single non-empty predecessor the pointer equiv
- class is the same. */
- if (!graph->points_to[n])
- {
- if (first_pred != -1U)
- {
- graph->pointer_label[n] = graph->pointer_label[first_pred];
- graph->points_to[n] = graph->points_to[first_pred];
- }
- return;
- }
-
- if (!bitmap_empty_p (graph->points_to[n]))
- {
- equiv_class_label_t ecl;
- ecl = equiv_class_lookup_or_add (pointer_equiv_class_table,
- graph->points_to[n]);
- if (ecl->equivalence_class == 0)
- ecl->equivalence_class = pointer_equiv_class++;
- else
- {
- BITMAP_FREE (graph->points_to[n]);
- graph->points_to[n] = ecl->labels;
- }
- graph->pointer_label[n] = ecl->equivalence_class;
- }
-}
-
-/* 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 (!bitmap_bit_p (si->visited, si->node_mapping[i]))
- condense_visit (graph, si, si->node_mapping[i]);
-
- bitmap_clear (si->visited);
- /* Actually the label the nodes for pointer equivalences */
- for (i = 0; i < FIRST_REF_NODE; i++)
- if (!bitmap_bit_p (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;
-
- 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. */
- equiv_class_label_t ecl;
- ecl = equiv_class_lookup_or_add (location_equiv_class_table, pointed_by);
- if (ecl->equivalence_class == 0)
- ecl->equivalence_class = location_equiv_class++;
- 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] = ecl->equivalence_class;
-
- }
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- for (i = 0; i < FIRST_REF_NODE; i++)
- {
- unsigned j = si->node_mapping[i];
- if (j != i)
- fprintf (dump_file, "%s node id %d (%s) mapped to SCC leader "
- "node id %d (%s)\n",
- bitmap_bit_p (graph->direct_nodes, i)
- ? "Direct" : "Indirect", i, get_varinfo (i)->name,
- j, get_varinfo (j)->name);
- else
- fprintf (dump_file,
- "Equivalence classes for %s node id %d (%s): pointer %d"
- ", location %d\n",
- bitmap_bit_p (graph->direct_nodes, i)
- ? "direct" : "indirect", i, get_varinfo (i)->name,
- graph->pointer_label[i], graph->loc_label[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_EACH_VEC_ELT (constraints, i, c)
- {
- 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_EACH_VEC_ELT (constraints, i, c)
- {
- struct constraint_expr lhs = c->lhs;
- struct constraint_expr rhs = c->rhs;
- unsigned int lhsvar = find (lhs.var);
- unsigned int rhsvar = find (rhs.var);
- 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);
- fprintf (dump_file, "\n");
- }
- 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);
- fprintf (dump_file, "\n");
- }
- 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> queue = vNULL;
- 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))
- queue.safe_push (i);
- }
- }
-
- for (queuepos = 0;
- queue.iterate (queuepos, &i);
- queuepos++)
- {
- unify_nodes (graph, to, i, true);
- }
- queue.release ();
- 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 = BITMAP_ALLOC (NULL);
-
- /* 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]))
- || graph->complex[i].length () > 0))
- bitmap_set_bit (changed, i);
- }
-
- /* Allocate a bitmap to be used to store the changed bits. */
- pts = BITMAP_ALLOC (&pta_obstack);
-
- while (!bitmap_empty_p (changed))
- {
- unsigned int i;
- struct topo_info *ti = init_topo_info ();
- stats.iterations++;
-
- bitmap_obstack_initialize (&iteration_obstack);
-
- compute_topo_order (graph, ti);
-
- while (ti->topo_order.length () != 0)
- {
-
- i = ti->topo_order.pop ();
-
- /* 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 (bitmap_clear_bit (changed, i))
- {
- unsigned int j;
- constraint_t c;
- bitmap solution;
- vec<constraint_t> complex = graph->complex[i];
- varinfo_t vi = get_varinfo (i);
- bool solution_empty;
-
- /* Compute the changed set of solution bits. */
- if (vi->oldsolution)
- bitmap_and_compl (pts, vi->solution, vi->oldsolution);
- else
- bitmap_copy (pts, vi->solution);
-
- if (bitmap_empty_p (pts))
- continue;
-
- if (vi->oldsolution)
- bitmap_ior_into (vi->oldsolution, pts);
- else
- {
- vi->oldsolution = BITMAP_ALLOC (&oldpta_obstack);
- bitmap_copy (vi->oldsolution, pts);
- }
-
- solution = vi->solution;
- solution_empty = bitmap_empty_p (solution);
-
- /* Process the complex constraints */
- FOR_EACH_VEC_ELT (complex, j, c)
- {
- /* 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)
- {
- bitmap_iterator bi;
- unsigned eff_escaped_id = find (escaped_id);
-
- /* 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;
-
- /* If we propagate from ESCAPED use ESCAPED as
- placeholder. */
- if (i == eff_escaped_id)
- flag = bitmap_set_bit (tmp, escaped_id);
- else
- flag = set_union_with_increment (tmp, pts, 0);
-
- if (flag)
- {
- get_varinfo (to)->solution = tmp;
- bitmap_set_bit (changed, to);
- }
- }
- }
- }
- }
- free_topo_info (ti);
- bitmap_obstack_release (&iteration_obstack);
- }
-
- BITMAP_FREE (pts);
- BITMAP_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 = NULL;
- char *temp;
- int num_printed = 0;
-
- if (!dump_file)
- return "NULL";
-
- if (TREE_CODE (decl) == SSA_NAME)
- {
- res = get_name (decl);
- if (res)
- num_printed = asprintf (&temp, "%s_%u", res, SSA_NAME_VERSION (decl));
- else
- num_printed = asprintf (&temp, "_%u", SSA_NAME_VERSION (decl));
- if (num_printed > 0)
- {
- res = ggc_strdup (temp);
- free (temp);
- }
- }
- else if (DECL_P (decl))
- {
- if (DECL_ASSEMBLER_NAME_SET_P (decl))
- res = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (decl));
- else
- {
- res = get_name (decl);
- if (!res)
- {
- num_printed = asprintf (&temp, "D.%u", DECL_UID (decl));
- if (num_printed > 0)
- {
- res = ggc_strdup (temp);
- free (temp);
- }
- }
- }
- }
- if (res != NULL)
- return res;
-
- return "NULL";
-}
-
-/* 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 scalar constraint expression for a new temporary variable. */
-
-static struct constraint_expr
-new_scalar_tmp_constraint_exp (const char *name)
-{
- struct constraint_expr tmp;
- varinfo_t vi;
-
- vi = new_var_info (NULL_TREE, name);
- vi->offset = 0;
- vi->size = -1;
- vi->fullsize = -1;
- vi->is_full_var = 1;
-
- tmp.var = vi->id;
- tmp.type = SCALAR;
- tmp.offset = 0;
-
- return tmp;
-}
-
-/* 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> *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 (TREE_CODE (t) == SSA_NAME || DECL_P (t));
-
- /* For parameters, get at the points-to set for the actual parm
- decl. */
- if (TREE_CODE (t) == SSA_NAME
- && SSA_NAME_IS_DEFAULT_DEF (t)
- && (TREE_CODE (SSA_NAME_VAR (t)) == PARM_DECL
- || TREE_CODE (SSA_NAME_VAR (t)) == RESULT_DECL))
- {
- get_constraint_for_ssa_var (SSA_NAME_VAR (t), results, address_p);
- return;
- }
-
- /* For global variables resort to the alias target. */
- if (TREE_CODE (t) == VAR_DECL
- && (TREE_STATIC (t) || DECL_EXTERNAL (t)))
- {
- struct varpool_node *node = varpool_get_node (t);
- if (node && node->alias)
- {
- node = varpool_variable_node (node, NULL);
- t = node->symbol.decl;
- }
- }
-
- 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
- && !vi->is_full_var)
- {
- for (; vi; vi = vi->next)
- {
- cexpr.var = vi->id;
- results->safe_push (cexpr);
- }
- return;
- }
-
- results->safe_push (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 < varmap.length ());
- gcc_assert (lhs.var < varmap.length ());
-
- /* If we didn't get any useful constraint from the lhs we get
- &ANYTHING as fallback from get_constraint_for. Deal with
- it here by turning it into *ANYTHING. */
- if (lhs.type == ADDRESSOF
- && lhs.var == anything_id)
- lhs.type = DEREF;
-
- /* ADDRESSOF on the lhs is invalid. */
- gcc_assert (lhs.type != ADDRESSOF);
-
- /* We shouldn't add constraints from things that cannot have pointers.
- It's not completely trivial to avoid in the callers, so do it here. */
- if (rhs.type != ADDRESSOF
- && !get_varinfo (rhs.var)->may_have_pointers)
- return;
-
- /* Likewise adding to the solution of a non-pointer var isn't useful. */
- if (!get_varinfo (lhs.var)->may_have_pointers)
- return;
-
- /* This can happen in our IR with things like n->a = *p */
- if (rhs.type == DEREF && lhs.type == DEREF && rhs.var != anything_id)
- {
- /* Split into tmp = *rhs, *lhs = tmp */
- struct constraint_expr tmplhs;
- tmplhs = new_scalar_tmp_constraint_exp ("doubledereftmp");
- 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 */
- struct constraint_expr tmplhs;
- tmplhs = new_scalar_tmp_constraint_exp ("derefaddrtmp");
- process_constraint (new_constraint (tmplhs, rhs));
- process_constraint (new_constraint (lhs, tmplhs));
- }
- else
- {
- gcc_assert (rhs.type != ADDRESSOF || rhs.offset == 0);
- constraints.safe_push (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)) * BITS_PER_UNIT
- + 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> *results)
-{
- struct constraint_expr c;
- unsigned int j, n;
- HOST_WIDE_INT 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_rhs (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. */
- if (offset == NULL_TREE
- || TREE_CODE (offset) != INTEGER_CST)
- rhsoffset = UNKNOWN_OFFSET;
- else
- {
- /* Sign-extend the offset. */
- double_int soffset = tree_to_double_int (offset)
- .sext (TYPE_PRECISION (TREE_TYPE (offset)));
- if (!soffset.fits_shwi ())
- rhsoffset = UNKNOWN_OFFSET;
- else
- {
- /* Make sure the bit-offset also fits. */
- HOST_WIDE_INT rhsunitoffset = soffset.low;
- rhsoffset = rhsunitoffset * BITS_PER_UNIT;
- if (rhsunitoffset != rhsoffset / BITS_PER_UNIT)
- rhsoffset = UNKNOWN_OFFSET;
- }
- }
-
- get_constraint_for_rhs (ptr, results);
- if (rhsoffset == 0)
- return;
-
- /* As we are eventually appending to the solution do not use
- vec::iterate here. */
- n = results->length ();
- for (j = 0; j < n; j++)
- {
- varinfo_t curr;
- c = (*results)[j];
- curr = get_varinfo (c.var);
-
- if (c.type == ADDRESSOF
- /* If this varinfo represents a full variable just use it. */
- && curr->is_full_var)
- c.offset = 0;
- else if (c.type == ADDRESSOF
- /* If we do not know the offset add all subfields. */
- && rhsoffset == UNKNOWN_OFFSET)
- {
- varinfo_t temp = lookup_vi_for_tree (curr->decl);
- do
- {
- struct constraint_expr c2;
- c2.var = temp->id;
- c2.type = ADDRESSOF;
- c2.offset = 0;
- if (c2.var != c.var)
- results->safe_push (c2);
- temp = temp->next;
- }
- while (temp);
- }
- else if (c.type == ADDRESSOF)
- {
- varinfo_t temp;
- unsigned HOST_WIDE_INT offset = curr->offset + rhsoffset;
-
- /* Search the sub-field which overlaps with the
- pointed-to offset. 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 and first
- sub-fields are such conservative results.
- ??? If we always had a sub-field for &object + 1 then
- we could represent this in a more precise way. */
- if (rhsoffset < 0
- && curr->offset < offset)
- offset = 0;
- temp = first_or_preceding_vi_for_offset (curr, offset);
-
- /* 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 != offset
- && temp->next != NULL)
- {
- struct constraint_expr c2;
- c2.var = temp->next->id;
- c2.type = ADDRESSOF;
- c2.offset = 0;
- results->safe_push (c2);
- }
- c.var = temp->id;
- c.offset = 0;
- }
- else
- c.offset = rhsoffset;
-
- (*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.
- If lhs_p is true then the constraint expression is assumed to be used
- as the lhs. */
-
-static void
-get_constraint_for_component_ref (tree t, vec<ce_s> *results,
- bool address_p, bool lhs_p)
-{
- tree orig_t = t;
- HOST_WIDE_INT bitsize = -1;
- HOST_WIDE_INT bitmaxsize = -1;
- HOST_WIDE_INT bitpos;
- tree forzero;
-
- /* Some people like to do cute things like take the address of
- &0->a.b */
- forzero = t;
- while (handled_component_p (forzero)
- || INDIRECT_REF_P (forzero)
- || TREE_CODE (forzero) == MEM_REF)
- 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;
- results->safe_push (temp);
- return;
- }
-
- /* Handle type-punning through unions. If we are extracting a pointer
- from a union via a possibly type-punning access that pointer
- points to anything, similar to a conversion of an integer to
- a pointer. */
- if (!lhs_p)
- {
- tree u;
- for (u = t;
- TREE_CODE (u) == COMPONENT_REF || TREE_CODE (u) == ARRAY_REF;
- u = TREE_OPERAND (u, 0))
- if (TREE_CODE (u) == COMPONENT_REF
- && TREE_CODE (TREE_TYPE (TREE_OPERAND (u, 0))) == UNION_TYPE)
- {
- struct constraint_expr temp;
-
- temp.offset = 0;
- temp.var = anything_id;
- temp.type = ADDRESSOF;
- results->safe_push (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, lhs_p);
- gcc_assert (results->length () == 1);
- struct constraint_expr &result = results->last ();
-
- 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;
- results->pop ();
- 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;
- results->safe_push (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 && results->length () == 0)
- {
- curr = get_varinfo (cexpr.var);
- while (curr->next != NULL)
- curr = curr->next;
- cexpr.var = curr->id;
- results->safe_push (cexpr);
- }
- else if (results->length () == 0)
- /* 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. */
- /* Or accessing only padding via type-punning to a type
- that has a filed just in padding space. */
- {
- cexpr.type = SCALAR;
- cexpr.var = anything_id;
- cexpr.offset = 0;
- results->safe_push (cexpr);
- }
- }
- 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 (result.type == DEREF)
- {
- /* If we do not know exactly where the access goes say so. Note
- that only for non-structure accesses we know that we access
- at most one subfiled of any variable. */
- if (bitpos == -1
- || bitsize != bitmaxsize
- || AGGREGATE_TYPE_P (TREE_TYPE (orig_t))
- || result.offset == UNKNOWN_OFFSET)
- result.offset = UNKNOWN_OFFSET;
- else
- result.offset += bitpos;
- }
- else if (result.type == ADDRESSOF)
- {
- /* We can end up here for component references on a
- VIEW_CONVERT_EXPR <>(&foobar). */
- result.type = SCALAR;
- result.var = anything_id;
- result.offset = 0;
- }
- else
- gcc_unreachable ();
-}
-
-
-/* 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> *constraints)
-{
- struct constraint_expr *c;
- unsigned int i = 0;
-
- FOR_EACH_VEC_ELT (*constraints, i, c)
- {
- if (c->type == SCALAR)
- c->type = DEREF;
- else if (c->type == ADDRESSOF)
- c->type = SCALAR;
- else if (c->type == DEREF)
- {
- struct constraint_expr tmplhs;
- tmplhs = new_scalar_tmp_constraint_exp ("dereftmp");
- process_constraint (new_constraint (tmplhs, *c));
- c->var = tmplhs.var;
- }
- else
- gcc_unreachable ();
- }
-}
-
-/* Given a tree T, return the constraint expression for taking the
- address of it. */
-
-static void
-get_constraint_for_address_of (tree t, vec<ce_s> *results)
-{
- struct constraint_expr *c;
- unsigned int i;
-
- get_constraint_for_1 (t, results, true, true);
-
- FOR_EACH_VEC_ELT (*results, i, c)
- {
- if (c->type == DEREF)
- c->type = SCALAR;
- else
- c->type = ADDRESSOF;
- }
-}
-
-/* Given a tree T, return the constraint expression for it. */
-
-static void
-get_constraint_for_1 (tree t, vec<ce_s> *results, bool address_p,
- bool lhs_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 ((TREE_CODE (t) == INTEGER_CST
- && integer_zerop (t))
- /* The only valid CONSTRUCTORs in gimple with pointer typed
- elements are zero-initializer. But in IPA mode we also
- process global initializers, so verify at least. */
- || (TREE_CODE (t) == CONSTRUCTOR
- && CONSTRUCTOR_NELTS (t) == 0))
- {
- if (flag_delete_null_pointer_checks)
- temp.var = nothing_id;
- else
- temp.var = nonlocal_id;
- temp.type = ADDRESSOF;
- temp.offset = 0;
- results->safe_push (temp);
- return;
- }
-
- /* String constants are read-only. */
- if (TREE_CODE (t) == STRING_CST)
- {
- temp.var = readonly_id;
- temp.type = SCALAR;
- temp.offset = 0;
- results->safe_push (temp);
- return;
- }
-
- switch (TREE_CODE_CLASS (TREE_CODE (t)))
- {
- case tcc_expression:
- {
- switch (TREE_CODE (t))
- {
- case ADDR_EXPR:
- get_constraint_for_address_of (TREE_OPERAND (t, 0), results);
- return;
- default:;
- }
- break;
- }
- case tcc_reference:
- {
- switch (TREE_CODE (t))
- {
- case MEM_REF:
- {
- struct constraint_expr cs;
- varinfo_t vi, curr;
- get_constraint_for_ptr_offset (TREE_OPERAND (t, 0),
- TREE_OPERAND (t, 1), results);
- do_deref (results);
-
- /* If we are not taking the address then make sure to process
- all subvariables we might access. */
- if (address_p)
- return;
-
- cs = results->last ();
- if (cs.type == DEREF
- && type_can_have_subvars (TREE_TYPE (t)))
- {
- /* For dereferences this means we have to defer it
- to solving time. */
- results->last ().offset = UNKNOWN_OFFSET;
- return;
- }
- if (cs.type != SCALAR)
- return;
-
- vi = get_varinfo (cs.var);
- curr = vi->next;
- if (!vi->is_full_var
- && curr)
- {
- unsigned HOST_WIDE_INT size;
- if (host_integerp (TYPE_SIZE (TREE_TYPE (t)), 1))
- size = TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (t)));
- else
- size = -1;
- for (; curr; curr = curr->next)
- {
- if (curr->offset - vi->offset < size)
- {
- cs.var = curr->id;
- results->safe_push (cs);
- }
- else
- break;
- }
- }
- return;
- }
- case ARRAY_REF:
- case ARRAY_RANGE_REF:
- case COMPONENT_REF:
- get_constraint_for_component_ref (t, results, address_p, lhs_p);
- return;
- case VIEW_CONVERT_EXPR:
- get_constraint_for_1 (TREE_OPERAND (t, 0), results, address_p,
- lhs_p);
- return;
- /* We are missing handling for TARGET_MEM_REF here. */
- default:;
- }
- break;
- }
- case tcc_exceptional:
- {
- switch (TREE_CODE (t))
- {
- case SSA_NAME:
- {
- get_constraint_for_ssa_var (t, results, address_p);
- return;
- }
- case CONSTRUCTOR:
- {
- unsigned int i;
- tree val;
- vec<ce_s> tmp = vNULL;
- FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (t), i, val)
- {
- struct constraint_expr *rhsp;
- unsigned j;
- get_constraint_for_1 (val, &tmp, address_p, lhs_p);
- FOR_EACH_VEC_ELT (tmp, j, rhsp)
- results->safe_push (*rhsp);
- tmp.truncate (0);
- }
- tmp.release ();
- /* We do not know whether the constructor was complete,
- so technically we have to add &NOTHING or &ANYTHING
- like we do for an empty constructor as well. */
- return;
- }
- default:;
- }
- break;
- }
- case tcc_declaration:
- {
- get_constraint_for_ssa_var (t, results, address_p);
- return;
- }
- case tcc_constant:
- {
- /* We cannot refer to automatic variables through constants. */
- temp.type = ADDRESSOF;
- temp.var = nonlocal_id;
- temp.offset = 0;
- results->safe_push (temp);
- return;
- }
- default:;
- }
-
- /* The default fallback is a constraint from anything. */
- temp.type = ADDRESSOF;
- temp.var = anything_id;
- temp.offset = 0;
- results->safe_push (temp);
-}
-
-/* Given a gimple tree T, return the constraint expression vector for it. */
-
-static void
-get_constraint_for (tree t, vec<ce_s> *results)
-{
- gcc_assert (results->length () == 0);
-
- get_constraint_for_1 (t, results, false, true);
-}
-
-/* Given a gimple tree T, return the constraint expression vector for it
- to be used as the rhs of a constraint. */
-
-static void
-get_constraint_for_rhs (tree t, vec<ce_s> *results)
-{
- gcc_assert (results->length () == 0);
-
- get_constraint_for_1 (t, results, false, false);
-}
-
-
-/* Efficiently generates constraints from all entries in *RHSC to all
- entries in *LHSC. */
-
-static void
-process_all_all_constraints (vec<ce_s> lhsc,
- vec<ce_s> rhsc)
-{
- struct constraint_expr *lhsp, *rhsp;
- unsigned i, j;
-
- if (lhsc.length () <= 1 || rhsc.length () <= 1)
- {
- FOR_EACH_VEC_ELT (lhsc, i, lhsp)
- FOR_EACH_VEC_ELT (rhsc, j, rhsp)
- process_constraint (new_constraint (*lhsp, *rhsp));
- }
- else
- {
- struct constraint_expr tmp;
- tmp = new_scalar_tmp_constraint_exp ("allalltmp");
- FOR_EACH_VEC_ELT (rhsc, i, rhsp)
- process_constraint (new_constraint (tmp, *rhsp));
- FOR_EACH_VEC_ELT (lhsc, i, lhsp)
- process_constraint (new_constraint (*lhsp, tmp));
- }
-}
-
-/* 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 *lhsp, *rhsp;
- vec<ce_s> lhsc = vNULL;
- vec<ce_s> rhsc = vNULL;
- unsigned j;
-
- get_constraint_for (lhsop, &lhsc);
- get_constraint_for_rhs (rhsop, &rhsc);
- lhsp = &lhsc[0];
- rhsp = &rhsc[0];
- if (lhsp->type == DEREF
- || (lhsp->type == ADDRESSOF && lhsp->var == anything_id)
- || rhsp->type == DEREF)
- {
- if (lhsp->type == DEREF)
- {
- gcc_assert (lhsc.length () == 1);
- lhsp->offset = UNKNOWN_OFFSET;
- }
- if (rhsp->type == DEREF)
- {
- gcc_assert (rhsc.length () == 1);
- rhsp->offset = UNKNOWN_OFFSET;
- }
- process_all_all_constraints (lhsc, rhsc);
- }
- else if (lhsp->type == SCALAR
- && (rhsp->type == SCALAR
- || rhsp->type == ADDRESSOF))
- {
- HOST_WIDE_INT lhssize, lhsmaxsize, lhsoffset;
- HOST_WIDE_INT rhssize, rhsmaxsize, rhsoffset;
- unsigned k = 0;
- get_ref_base_and_extent (lhsop, &lhsoffset, &lhssize, &lhsmaxsize);
- get_ref_base_and_extent (rhsop, &rhsoffset, &rhssize, &rhsmaxsize);
- for (j = 0; lhsc.iterate (j, &lhsp);)
- {
- varinfo_t lhsv, rhsv;
- rhsp = &rhsc[k];
- lhsv = get_varinfo (lhsp->var);
- rhsv = get_varinfo (rhsp->var);
- if (lhsv->may_have_pointers
- && (lhsv->is_full_var
- || rhsv->is_full_var
- || ranges_overlap_p (lhsv->offset + rhsoffset, lhsv->size,
- rhsv->offset + lhsoffset, rhsv->size)))
- process_constraint (new_constraint (*lhsp, *rhsp));
- if (!rhsv->is_full_var
- && (lhsv->is_full_var
- || (lhsv->offset + rhsoffset + lhsv->size
- > rhsv->offset + lhsoffset + rhsv->size)))
- {
- ++k;
- if (k >= rhsc.length ())
- break;
- }
- else
- ++j;
- }
- }
- else
- gcc_unreachable ();
-
- lhsc.release ();
- rhsc.release ();
-}
-
-/* Create constraints ID = { rhsc }. */
-
-static void
-make_constraints_to (unsigned id, vec<ce_s> rhsc)
-{
- struct constraint_expr *c;
- struct constraint_expr includes;
- unsigned int j;
-
- includes.var = id;
- includes.offset = 0;
- includes.type = SCALAR;
-
- FOR_EACH_VEC_ELT (rhsc, j, c)
- process_constraint (new_constraint (includes, *c));
-}
-
-/* Create a constraint ID = OP. */
-
-static void
-make_constraint_to (unsigned id, tree op)
-{
- vec<ce_s> rhsc = vNULL;
- get_constraint_for_rhs (op, &rhsc);
- make_constraints_to (id, rhsc);
- rhsc.release ();
-}
-
-/* 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));
-}
-
-/* Create a constraint ID = FROM. */
-
-static void
-make_copy_constraint (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 = SCALAR;
- process_constraint (new_constraint (lhs, rhs));
-}
-
-/* Make constraints necessary to make OP escape. */
-
-static void
-make_escape_constraint (tree op)
-{
- make_constraint_to (escaped_id, op);
-}
-
-/* Add constraints to that the solution of VI is transitively closed. */
-
-static void
-make_transitive_closure_constraints (varinfo_t vi)
-{
- struct constraint_expr lhs, rhs;
-
- /* VAR = *VAR; */
- lhs.type = SCALAR;
- lhs.var = vi->id;
- lhs.offset = 0;
- rhs.type = DEREF;
- rhs.var = vi->id;
- rhs.offset = 0;
- process_constraint (new_constraint (lhs, rhs));
-
- /* VAR = VAR + UNKNOWN; */
- lhs.type = SCALAR;
- lhs.var = vi->id;
- lhs.offset = 0;
- rhs.type = SCALAR;
- rhs.var = vi->id;
- rhs.offset = UNKNOWN_OFFSET;
- process_constraint (new_constraint (lhs, rhs));
-}
-
-/* Temporary storage for fake var decls. */
-struct obstack fake_var_decl_obstack;
-
-/* Build a fake VAR_DECL acting as referrer to a DECL_UID. */
-
-static tree
-build_fake_var_decl (tree type)
-{
- tree decl = (tree) XOBNEW (&fake_var_decl_obstack, struct tree_var_decl);
- memset (decl, 0, sizeof (struct tree_var_decl));
- TREE_SET_CODE (decl, VAR_DECL);
- TREE_TYPE (decl) = type;
- DECL_UID (decl) = allocate_decl_uid ();
- SET_DECL_PT_UID (decl, -1);
- layout_decl (decl, 0);
- return decl;
-}
-
-/* Create a new artificial heap variable with NAME.
- Return the created variable. */
-
-static varinfo_t
-make_heapvar (const char *name)
-{
- varinfo_t vi;
- tree heapvar;
-
- heapvar = build_fake_var_decl (ptr_type_node);
- DECL_EXTERNAL (heapvar) = 1;
-
- vi = new_var_info (heapvar, name);
- vi->is_artificial_var = true;
- vi->is_heap_var = true;
- vi->is_unknown_size_var = true;
- vi->offset = 0;
- vi->fullsize = ~0;
- vi->size = ~0;
- vi->is_full_var = true;
- insert_vi_for_tree (heapvar, vi);
-
- return vi;
-}
-
-/* Create a new artificial heap variable with NAME and make a
- constraint from it to LHS. Set flags according to a tag used
- for tracking restrict pointers. */
-
-static varinfo_t
-make_constraint_from_restrict (varinfo_t lhs, const char *name)
-{
- varinfo_t vi = make_heapvar (name);
- vi->is_global_var = 1;
- vi->may_have_pointers = 1;
- make_constraint_from (lhs, vi->id);
- return vi;
-}
-
-/* Create a new artificial heap variable with NAME and make a
- constraint from it to LHS. Set flags according to a tag used
- for tracking restrict pointers and make the artificial heap
- point to global memory. */
-
-static varinfo_t
-make_constraint_from_global_restrict (varinfo_t lhs, const char *name)
-{
- varinfo_t vi = make_constraint_from_restrict (lhs, name);
- make_copy_constraint (vi, nonlocal_id);
- return vi;
-}
-
-/* In IPA mode there are varinfos for different aspects of reach
- function designator. One for the points-to set of the return
- value, one for the variables that are clobbered by the function,
- one for its uses and one for each parameter (including a single
- glob for remaining variadic arguments). */
-
-enum { fi_clobbers = 1, fi_uses = 2,
- fi_static_chain = 3, fi_result = 4, fi_parm_base = 5 };
-
-/* Get a constraint for the requested part of a function designator FI
- when operating in IPA mode. */
-
-static struct constraint_expr
-get_function_part_constraint (varinfo_t fi, unsigned part)
-{
- struct constraint_expr c;
-
- gcc_assert (in_ipa_mode);
-
- if (fi->id == anything_id)
- {
- /* ??? We probably should have a ANYFN special variable. */
- c.var = anything_id;
- c.offset = 0;
- c.type = SCALAR;
- }
- else if (TREE_CODE (fi->decl) == FUNCTION_DECL)
- {
- varinfo_t ai = first_vi_for_offset (fi, part);
- if (ai)
- c.var = ai->id;
- else
- c.var = anything_id;
- c.offset = 0;
- c.type = SCALAR;
- }
- else
- {
- c.var = fi->id;
- c.offset = part;
- c.type = DEREF;
- }
-
- return c;
-}
-
-/* For non-IPA mode, generate constraints necessary for a call on the
- RHS. */
-
-static void
-handle_rhs_call (gimple stmt, vec<ce_s> *results)
-{
- struct constraint_expr rhsc;
- unsigned i;
- bool returns_uses = false;
-
- for (i = 0; i < gimple_call_num_args (stmt); ++i)
- {
- tree arg = gimple_call_arg (stmt, i);
- int flags = gimple_call_arg_flags (stmt, i);
-
- /* If the argument is not used we can ignore it. */
- if (flags & EAF_UNUSED)
- continue;
-
- /* As we compute ESCAPED context-insensitive we do not gain
- any precision with just EAF_NOCLOBBER but not EAF_NOESCAPE
- set. The argument would still get clobbered through the
- escape solution. */
- if ((flags & EAF_NOCLOBBER)
- && (flags & EAF_NOESCAPE))
- {
- varinfo_t uses = get_call_use_vi (stmt);
- if (!(flags & EAF_DIRECT))
- {
- varinfo_t tem = new_var_info (NULL_TREE, "callarg");
- make_constraint_to (tem->id, arg);
- make_transitive_closure_constraints (tem);
- make_copy_constraint (uses, tem->id);
- }
- else
- make_constraint_to (uses->id, arg);
- returns_uses = true;
- }
- else if (flags & EAF_NOESCAPE)
- {
- struct constraint_expr lhs, rhs;
- varinfo_t uses = get_call_use_vi (stmt);
- varinfo_t clobbers = get_call_clobber_vi (stmt);
- varinfo_t tem = new_var_info (NULL_TREE, "callarg");
- make_constraint_to (tem->id, arg);
- if (!(flags & EAF_DIRECT))
- make_transitive_closure_constraints (tem);
- make_copy_constraint (uses, tem->id);
- make_copy_constraint (clobbers, tem->id);
- /* Add *tem = nonlocal, do not add *tem = callused as
- EAF_NOESCAPE parameters do not escape to other parameters
- and all other uses appear in NONLOCAL as well. */
- lhs.type = DEREF;
- lhs.var = tem->id;
- lhs.offset = 0;
- rhs.type = SCALAR;
- rhs.var = nonlocal_id;
- rhs.offset = 0;
- process_constraint (new_constraint (lhs, rhs));
- returns_uses = true;
- }
- else
- make_escape_constraint (arg);
- }
-
- /* If we added to the calls uses solution make sure we account for
- pointers to it to be returned. */
- if (returns_uses)
- {
- rhsc.var = get_call_use_vi (stmt)->id;
- rhsc.offset = 0;
- rhsc.type = SCALAR;
- results->safe_push (rhsc);
- }
-
- /* The static chain escapes as well. */
- if (gimple_call_chain (stmt))
- make_escape_constraint (gimple_call_chain (stmt));
-
- /* And if we applied NRV the address of the return slot escapes as well. */
- if (gimple_call_return_slot_opt_p (stmt)
- && gimple_call_lhs (stmt) != NULL_TREE
- && TREE_ADDRESSABLE (TREE_TYPE (gimple_call_lhs (stmt))))
- {
- vec<ce_s> tmpc = vNULL;
- struct constraint_expr lhsc, *c;
- get_constraint_for_address_of (gimple_call_lhs (stmt), &tmpc);
- lhsc.var = escaped_id;
- lhsc.offset = 0;
- lhsc.type = SCALAR;
- FOR_EACH_VEC_ELT (tmpc, i, c)
- process_constraint (new_constraint (lhsc, *c));
- tmpc.release ();
- }
-
- /* Regular functions return nonlocal memory. */
- rhsc.var = nonlocal_id;
- rhsc.offset = 0;
- rhsc.type = SCALAR;
- results->safe_push (rhsc);
-}
-
-/* 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 (gimple stmt, tree lhs, int flags, vec<ce_s> rhsc,
- tree fndecl)
-{
- vec<ce_s> lhsc = vNULL;
-
- get_constraint_for (lhs, &lhsc);
- /* If the store is to a global decl make sure to
- add proper escape constraints. */
- lhs = get_base_address (lhs);
- if (lhs
- && DECL_P (lhs)
- && is_global_var (lhs))
- {
- struct constraint_expr tmpc;
- tmpc.var = escaped_id;
- tmpc.offset = 0;
- tmpc.type = SCALAR;
- lhsc.safe_push (tmpc);
- }
-
- /* If the call returns an argument unmodified override the rhs
- constraints. */
- flags = gimple_call_return_flags (stmt);
- if (flags & ERF_RETURNS_ARG
- && (flags & ERF_RETURN_ARG_MASK) < gimple_call_num_args (stmt))
- {
- tree arg;
- rhsc.create (0);
- arg = gimple_call_arg (stmt, flags & ERF_RETURN_ARG_MASK);
- get_constraint_for (arg, &rhsc);
- process_all_all_constraints (lhsc, rhsc);
- rhsc.release ();
- }
- else if (flags & ERF_NOALIAS)
- {
- varinfo_t vi;
- struct constraint_expr tmpc;
- rhsc.create (0);
- vi = make_heapvar ("HEAP");
- /* We delay marking allocated storage global until we know if
- it escapes. */
- DECL_EXTERNAL (vi->decl) = 0;
- vi->is_global_var = 0;
- /* If this is not a real malloc call assume the memory was
- initialized and thus may point to global memory. All
- builtin functions with the malloc attribute behave in a sane way. */
- if (!fndecl
- || DECL_BUILT_IN_CLASS (fndecl) != BUILT_IN_NORMAL)
- make_constraint_from (vi, nonlocal_id);
- tmpc.var = vi->id;
- tmpc.offset = 0;
- tmpc.type = ADDRESSOF;
- rhsc.safe_push (tmpc);
- process_all_all_constraints (lhsc, rhsc);
- rhsc.release ();
- }
- else
- process_all_all_constraints (lhsc, rhsc);
-
- lhsc.release ();
-}
-
-/* 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, vec<ce_s> *results)
-{
- struct constraint_expr rhsc;
- unsigned int k;
-
- /* Treat nested const functions the same as pure functions as far
- as the static chain is concerned. */
- if (gimple_call_chain (stmt))
- {
- varinfo_t uses = get_call_use_vi (stmt);
- make_transitive_closure_constraints (uses);
- make_constraint_to (uses->id, gimple_call_chain (stmt));
- rhsc.var = uses->id;
- rhsc.offset = 0;
- rhsc.type = SCALAR;
- results->safe_push (rhsc);
- }
-
- /* May return arguments. */
- for (k = 0; k < gimple_call_num_args (stmt); ++k)
- {
- tree arg = gimple_call_arg (stmt, k);
- vec<ce_s> argc = vNULL;
- unsigned i;
- struct constraint_expr *argp;
- get_constraint_for_rhs (arg, &argc);
- FOR_EACH_VEC_ELT (argc, i, argp)
- results->safe_push (*argp);
- argc.release ();
- }
-
- /* May return addresses of globals. */
- rhsc.var = nonlocal_id;
- rhsc.offset = 0;
- rhsc.type = ADDRESSOF;
- results->safe_push (rhsc);
-}
-
-/* For non-IPA mode, generate constraints necessary for a call to a
- pure function in statement STMT. */
-
-static void
-handle_pure_call (gimple stmt, vec<ce_s> *results)
-{
- struct constraint_expr rhsc;
- unsigned i;
- varinfo_t uses = NULL;
-
- /* 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 (!uses)
- {
- uses = get_call_use_vi (stmt);
- make_transitive_closure_constraints (uses);
- }
- make_constraint_to (uses->id, arg);
- }
-
- /* The static chain is used as well. */
- if (gimple_call_chain (stmt))
- {
- if (!uses)
- {
- uses = get_call_use_vi (stmt);
- make_transitive_closure_constraints (uses);
- }
- make_constraint_to (uses->id, gimple_call_chain (stmt));
- }
-
- /* Pure functions may return call-used and nonlocal memory. */
- if (uses)
- {
- rhsc.var = uses->id;
- rhsc.offset = 0;
- rhsc.type = SCALAR;
- results->safe_push (rhsc);
- }
- rhsc.var = nonlocal_id;
- rhsc.offset = 0;
- rhsc.type = SCALAR;
- results->safe_push (rhsc);
-}
-
-
-/* Return the varinfo for the callee of CALL. */
-
-static varinfo_t
-get_fi_for_callee (gimple call)
-{
- tree decl, fn = gimple_call_fn (call);
-
- if (fn && TREE_CODE (fn) == OBJ_TYPE_REF)
- fn = OBJ_TYPE_REF_EXPR (fn);
-
- /* 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. */
- decl = gimple_call_addr_fndecl (fn);
- if (decl)
- return get_vi_for_tree (decl);
-
- /* If the function is anything other than a SSA name pointer we have no
- clue and should be getting ANYFN (well, ANYTHING for now). */
- if (!fn || TREE_CODE (fn) != SSA_NAME)
- return get_varinfo (anything_id);
-
- if (SSA_NAME_IS_DEFAULT_DEF (fn)
- && (TREE_CODE (SSA_NAME_VAR (fn)) == PARM_DECL
- || TREE_CODE (SSA_NAME_VAR (fn)) == RESULT_DECL))
- fn = SSA_NAME_VAR (fn);
-
- return get_vi_for_tree (fn);
-}
-
-/* Create constraints for the builtin call T. Return true if the call
- was handled, otherwise false. */
-
-static bool
-find_func_aliases_for_builtin_call (gimple t)
-{
- tree fndecl = gimple_call_fndecl (t);
- vec<ce_s> lhsc = vNULL;
- vec<ce_s> rhsc = vNULL;
- varinfo_t fi;
-
- if (gimple_call_builtin_p (t, BUILT_IN_NORMAL))
- /* ??? All builtins that are handled here need to be handled
- in the alias-oracle query functions explicitly! */
- switch (DECL_FUNCTION_CODE (fndecl))
- {
- /* All the following functions return a pointer to the same object
- as their first argument points to. The functions do not add
- to the ESCAPED solution. The functions make the first argument
- pointed to memory point to what the second argument pointed to
- memory points to. */
- case BUILT_IN_STRCPY:
- case BUILT_IN_STRNCPY:
- case BUILT_IN_BCOPY:
- case BUILT_IN_MEMCPY:
- case BUILT_IN_MEMMOVE:
- case BUILT_IN_MEMPCPY:
- case BUILT_IN_STPCPY:
- case BUILT_IN_STPNCPY:
- case BUILT_IN_STRCAT:
- case BUILT_IN_STRNCAT:
- case BUILT_IN_STRCPY_CHK:
- case BUILT_IN_STRNCPY_CHK:
- case BUILT_IN_MEMCPY_CHK:
- case BUILT_IN_MEMMOVE_CHK:
- case BUILT_IN_MEMPCPY_CHK:
- case BUILT_IN_STPCPY_CHK:
- case BUILT_IN_STPNCPY_CHK:
- case BUILT_IN_STRCAT_CHK:
- case BUILT_IN_STRNCAT_CHK:
- case BUILT_IN_TM_MEMCPY:
- case BUILT_IN_TM_MEMMOVE:
- {
- tree res = gimple_call_lhs (t);
- tree dest = gimple_call_arg (t, (DECL_FUNCTION_CODE (fndecl)
- == BUILT_IN_BCOPY ? 1 : 0));
- tree src = gimple_call_arg (t, (DECL_FUNCTION_CODE (fndecl)
- == BUILT_IN_BCOPY ? 0 : 1));
- if (res != NULL_TREE)
- {
- get_constraint_for (res, &lhsc);
- if (DECL_FUNCTION_CODE (fndecl) == BUILT_IN_MEMPCPY
- || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_STPCPY
- || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_STPNCPY
- || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_MEMPCPY_CHK
- || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_STPCPY_CHK
- || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_STPNCPY_CHK)
- get_constraint_for_ptr_offset (dest, NULL_TREE, &rhsc);
- else
- get_constraint_for (dest, &rhsc);
- process_all_all_constraints (lhsc, rhsc);
- lhsc.release ();
- rhsc.release ();
- }
- get_constraint_for_ptr_offset (dest, NULL_TREE, &lhsc);
- get_constraint_for_ptr_offset (src, NULL_TREE, &rhsc);
- do_deref (&lhsc);
- do_deref (&rhsc);
- process_all_all_constraints (lhsc, rhsc);
- lhsc.release ();
- rhsc.release ();
- return true;
- }
- case BUILT_IN_MEMSET:
- case BUILT_IN_MEMSET_CHK:
- case BUILT_IN_TM_MEMSET:
- {
- tree res = gimple_call_lhs (t);
- tree dest = gimple_call_arg (t, 0);
- unsigned i;
- ce_s *lhsp;
- struct constraint_expr ac;
- if (res != NULL_TREE)
- {
- get_constraint_for (res, &lhsc);
- get_constraint_for (dest, &rhsc);
- process_all_all_constraints (lhsc, rhsc);
- lhsc.release ();
- rhsc.release ();
- }
- get_constraint_for_ptr_offset (dest, NULL_TREE, &lhsc);
- do_deref (&lhsc);
- if (flag_delete_null_pointer_checks
- && integer_zerop (gimple_call_arg (t, 1)))
- {
- ac.type = ADDRESSOF;
- ac.var = nothing_id;
- }
- else
- {
- ac.type = SCALAR;
- ac.var = integer_id;
- }
- ac.offset = 0;
- FOR_EACH_VEC_ELT (lhsc, i, lhsp)
- process_constraint (new_constraint (*lhsp, ac));
- lhsc.release ();
- return true;
- }
- case BUILT_IN_ASSUME_ALIGNED:
- {
- tree res = gimple_call_lhs (t);
- tree dest = gimple_call_arg (t, 0);
- if (res != NULL_TREE)
- {
- get_constraint_for (res, &lhsc);
- get_constraint_for (dest, &rhsc);
- process_all_all_constraints (lhsc, rhsc);
- lhsc.release ();
- rhsc.release ();
- }
- return true;
- }
- /* All the following functions do not return pointers, do not
- modify the points-to sets of memory reachable from their
- arguments and do not add to the ESCAPED solution. */
- case BUILT_IN_SINCOS:
- case BUILT_IN_SINCOSF:
- case BUILT_IN_SINCOSL:
- case BUILT_IN_FREXP:
- case BUILT_IN_FREXPF:
- case BUILT_IN_FREXPL:
- case BUILT_IN_GAMMA_R:
- case BUILT_IN_GAMMAF_R:
- case BUILT_IN_GAMMAL_R:
- case BUILT_IN_LGAMMA_R:
- case BUILT_IN_LGAMMAF_R:
- case BUILT_IN_LGAMMAL_R:
- case BUILT_IN_MODF:
- case BUILT_IN_MODFF:
- case BUILT_IN_MODFL:
- case BUILT_IN_REMQUO:
- case BUILT_IN_REMQUOF:
- case BUILT_IN_REMQUOL:
- case BUILT_IN_FREE:
- return true;
- case BUILT_IN_STRDUP:
- case BUILT_IN_STRNDUP:
- if (gimple_call_lhs (t))
- {
- handle_lhs_call (t, gimple_call_lhs (t), gimple_call_flags (t),
- vNULL, fndecl);
- get_constraint_for_ptr_offset (gimple_call_lhs (t),
- NULL_TREE, &lhsc);
- get_constraint_for_ptr_offset (gimple_call_arg (t, 0),
- NULL_TREE, &rhsc);
- do_deref (&lhsc);
- do_deref (&rhsc);
- process_all_all_constraints (lhsc, rhsc);
- lhsc.release ();
- rhsc.release ();
- return true;
- }
- break;
- /* Trampolines are special - they set up passing the static
- frame. */
- case BUILT_IN_INIT_TRAMPOLINE:
- {
- tree tramp = gimple_call_arg (t, 0);
- tree nfunc = gimple_call_arg (t, 1);
- tree frame = gimple_call_arg (t, 2);
- unsigned i;
- struct constraint_expr lhs, *rhsp;
- if (in_ipa_mode)
- {
- varinfo_t nfi = NULL;
- gcc_assert (TREE_CODE (nfunc) == ADDR_EXPR);
- nfi = lookup_vi_for_tree (TREE_OPERAND (nfunc, 0));
- if (nfi)
- {
- lhs = get_function_part_constraint (nfi, fi_static_chain);
- get_constraint_for (frame, &rhsc);
- FOR_EACH_VEC_ELT (rhsc, i, rhsp)
- process_constraint (new_constraint (lhs, *rhsp));
- rhsc.release ();
-
- /* Make the frame point to the function for
- the trampoline adjustment call. */
- get_constraint_for (tramp, &lhsc);
- do_deref (&lhsc);
- get_constraint_for (nfunc, &rhsc);
- process_all_all_constraints (lhsc, rhsc);
- rhsc.release ();
- lhsc.release ();
-
- return true;
- }
- }
- /* Else fallthru to generic handling which will let
- the frame escape. */
- break;
- }
- case BUILT_IN_ADJUST_TRAMPOLINE:
- {
- tree tramp = gimple_call_arg (t, 0);
- tree res = gimple_call_lhs (t);
- if (in_ipa_mode && res)
- {
- get_constraint_for (res, &lhsc);
- get_constraint_for (tramp, &rhsc);
- do_deref (&rhsc);
- process_all_all_constraints (lhsc, rhsc);
- rhsc.release ();
- lhsc.release ();
- }
- return true;
- }
- CASE_BUILT_IN_TM_STORE (1):
- CASE_BUILT_IN_TM_STORE (2):
- CASE_BUILT_IN_TM_STORE (4):
- CASE_BUILT_IN_TM_STORE (8):
- CASE_BUILT_IN_TM_STORE (FLOAT):
- CASE_BUILT_IN_TM_STORE (DOUBLE):
- CASE_BUILT_IN_TM_STORE (LDOUBLE):
- CASE_BUILT_IN_TM_STORE (M64):
- CASE_BUILT_IN_TM_STORE (M128):
- CASE_BUILT_IN_TM_STORE (M256):
- {
- tree addr = gimple_call_arg (t, 0);
- tree src = gimple_call_arg (t, 1);
-
- get_constraint_for (addr, &lhsc);
- do_deref (&lhsc);
- get_constraint_for (src, &rhsc);
- process_all_all_constraints (lhsc, rhsc);
- lhsc.release ();
- rhsc.release ();
- return true;
- }
- CASE_BUILT_IN_TM_LOAD (1):
- CASE_BUILT_IN_TM_LOAD (2):
- CASE_BUILT_IN_TM_LOAD (4):
- CASE_BUILT_IN_TM_LOAD (8):
- CASE_BUILT_IN_TM_LOAD (FLOAT):
- CASE_BUILT_IN_TM_LOAD (DOUBLE):
- CASE_BUILT_IN_TM_LOAD (LDOUBLE):
- CASE_BUILT_IN_TM_LOAD (M64):
- CASE_BUILT_IN_TM_LOAD (M128):
- CASE_BUILT_IN_TM_LOAD (M256):
- {
- tree dest = gimple_call_lhs (t);
- tree addr = gimple_call_arg (t, 0);
-
- get_constraint_for (dest, &lhsc);
- get_constraint_for (addr, &rhsc);
- do_deref (&rhsc);
- process_all_all_constraints (lhsc, rhsc);
- lhsc.release ();
- rhsc.release ();
- return true;
- }
- /* Variadic argument handling needs to be handled in IPA
- mode as well. */
- case BUILT_IN_VA_START:
- {
- tree valist = gimple_call_arg (t, 0);
- struct constraint_expr rhs, *lhsp;
- unsigned i;
- get_constraint_for (valist, &lhsc);
- do_deref (&lhsc);
- /* The va_list gets access to pointers in variadic
- arguments. Which we know in the case of IPA analysis
- and otherwise are just all nonlocal variables. */
- if (in_ipa_mode)
- {
- fi = lookup_vi_for_tree (cfun->decl);
- rhs = get_function_part_constraint (fi, ~0);
- rhs.type = ADDRESSOF;
- }
- else
- {
- rhs.var = nonlocal_id;
- rhs.type = ADDRESSOF;
- rhs.offset = 0;
- }
- FOR_EACH_VEC_ELT (lhsc, i, lhsp)
- process_constraint (new_constraint (*lhsp, rhs));
- lhsc.release ();
- /* va_list is clobbered. */
- make_constraint_to (get_call_clobber_vi (t)->id, valist);
- return true;
- }
- /* va_end doesn't have any effect that matters. */
- case BUILT_IN_VA_END:
- return true;
- /* Alternate return. Simply give up for now. */
- case BUILT_IN_RETURN:
- {
- fi = NULL;
- if (!in_ipa_mode
- || !(fi = get_vi_for_tree (cfun->decl)))
- make_constraint_from (get_varinfo (escaped_id), anything_id);
- else if (in_ipa_mode
- && fi != NULL)
- {
- struct constraint_expr lhs, rhs;
- lhs = get_function_part_constraint (fi, fi_result);
- rhs.var = anything_id;
- rhs.offset = 0;
- rhs.type = SCALAR;
- process_constraint (new_constraint (lhs, rhs));
- }
- return true;
- }
- /* printf-style functions may have hooks to set pointers to
- point to somewhere into the generated string. Leave them
- for a later excercise... */
- default:
- /* Fallthru to general call handling. */;
- }
-
- return false;
-}
-
-/* Create constraints for the call T. */
-
-static void
-find_func_aliases_for_call (gimple t)
-{
- tree fndecl = gimple_call_fndecl (t);
- vec<ce_s> lhsc = vNULL;
- vec<ce_s> rhsc = vNULL;
- varinfo_t fi;
-
- if (fndecl != NULL_TREE
- && DECL_BUILT_IN (fndecl)
- && find_func_aliases_for_builtin_call (t))
- return;
-
- fi = get_fi_for_callee (t);
- if (!in_ipa_mode
- || (fndecl && !fi->is_fn_info))
- {
- vec<ce_s> rhsc = vNULL;
- 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|ECF_NOVOPS))
- {
- if (gimple_call_lhs (t))
- handle_const_call (t, &rhsc);
- }
- /* 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|ECF_LOOPING_CONST_OR_PURE))
- handle_pure_call (t, &rhsc);
- else
- handle_rhs_call (t, &rhsc);
- if (gimple_call_lhs (t))
- handle_lhs_call (t, gimple_call_lhs (t), flags, rhsc, fndecl);
- rhsc.release ();
- }
- else
- {
- tree lhsop;
- unsigned j;
-
- /* 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_rhs (arg, &rhsc);
- lhs = get_function_part_constraint (fi, fi_parm_base + j);
- while (rhsc.length () != 0)
- {
- rhsp = &rhsc.last ();
- process_constraint (new_constraint (lhs, *rhsp));
- rhsc.pop ();
- }
- }
-
- /* If we are returning a value, assign it to the result. */
- lhsop = gimple_call_lhs (t);
- if (lhsop)
- {
- struct constraint_expr rhs;
- struct constraint_expr *lhsp;
-
- get_constraint_for (lhsop, &lhsc);
- rhs = get_function_part_constraint (fi, fi_result);
- if (fndecl
- && DECL_RESULT (fndecl)
- && DECL_BY_REFERENCE (DECL_RESULT (fndecl)))
- {
- vec<ce_s> tem = vNULL;
- tem.safe_push (rhs);
- do_deref (&tem);
- rhs = tem[0];
- tem.release ();
- }
- FOR_EACH_VEC_ELT (lhsc, j, lhsp)
- process_constraint (new_constraint (*lhsp, rhs));
- }
-
- /* If we pass the result decl by reference, honor that. */
- if (lhsop
- && fndecl
- && DECL_RESULT (fndecl)
- && DECL_BY_REFERENCE (DECL_RESULT (fndecl)))
- {
- struct constraint_expr lhs;
- struct constraint_expr *rhsp;
-
- get_constraint_for_address_of (lhsop, &rhsc);
- lhs = get_function_part_constraint (fi, fi_result);
- FOR_EACH_VEC_ELT (rhsc, j, rhsp)
- process_constraint (new_constraint (lhs, *rhsp));
- rhsc.release ();
- }
-
- /* If we use a static chain, pass it along. */
- if (gimple_call_chain (t))
- {
- struct constraint_expr lhs;
- struct constraint_expr *rhsp;
-
- get_constraint_for (gimple_call_chain (t), &rhsc);
- lhs = get_function_part_constraint (fi, fi_static_chain);
- FOR_EACH_VEC_ELT (rhsc, j, rhsp)
- process_constraint (new_constraint (lhs, *rhsp));
- }
- }
-}
-
-/* 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> lhsc = vNULL;
- vec<ce_s> rhsc = vNULL;
- struct constraint_expr *c;
- varinfo_t fi;
-
- /* Now build constraints expressions. */
- if (gimple_code (t) == GIMPLE_PHI)
- {
- 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 strippedrhs = PHI_ARG_DEF (t, i);
-
- STRIP_NOPS (strippedrhs);
- get_constraint_for_rhs (gimple_phi_arg_def (t, i), &rhsc);
-
- FOR_EACH_VEC_ELT (lhsc, j, c)
- {
- struct constraint_expr *c2;
- while (rhsc.length () > 0)
- {
- c2 = &rhsc.last ();
- process_constraint (new_constraint (*c, *c2));
- rhsc.pop ();
- }
- }
- }
- }
- /* 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))
- find_func_aliases_for_call (t);
-
- /* 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))
- {
- /* 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 && TREE_CLOBBER_P (rhsop))
- /* Ignore clobbers, they don't actually store anything into
- the LHS. */
- ;
- else if (rhsop && AGGREGATE_TYPE_P (TREE_TYPE (lhsop)))
- do_structure_copy (lhsop, rhsop);
- else
- {
- enum tree_code code = gimple_assign_rhs_code (t);
-
- get_constraint_for (lhsop, &lhsc);
-
- if (code == POINTER_PLUS_EXPR)
- get_constraint_for_ptr_offset (gimple_assign_rhs1 (t),
- gimple_assign_rhs2 (t), &rhsc);
- else if (code == BIT_AND_EXPR
- && TREE_CODE (gimple_assign_rhs2 (t)) == INTEGER_CST)
- {
- /* Aligning a pointer via a BIT_AND_EXPR is offsetting
- the pointer. Handle it by offsetting it by UNKNOWN. */
- get_constraint_for_ptr_offset (gimple_assign_rhs1 (t),
- NULL_TREE, &rhsc);
- }
- else if ((CONVERT_EXPR_CODE_P (code)
- && !(POINTER_TYPE_P (gimple_expr_type (t))
- && !POINTER_TYPE_P (TREE_TYPE (rhsop))))
- || gimple_assign_single_p (t))
- get_constraint_for_rhs (rhsop, &rhsc);
- else if (code == COND_EXPR)
- {
- /* The result is a merge of both COND_EXPR arms. */
- vec<ce_s> tmp = vNULL;
- struct constraint_expr *rhsp;
- unsigned i;
- get_constraint_for_rhs (gimple_assign_rhs2 (t), &rhsc);
- get_constraint_for_rhs (gimple_assign_rhs3 (t), &tmp);
- FOR_EACH_VEC_ELT (tmp, i, rhsp)
- rhsc.safe_push (*rhsp);
- tmp.release ();
- }
- else if (truth_value_p (code))
- /* Truth value results are not pointer (parts). Or at least
- very very unreasonable obfuscation of a part. */
- ;
- else
- {
- /* All other operations are merges. */
- vec<ce_s> tmp = vNULL;
- struct constraint_expr *rhsp;
- unsigned i, j;
- get_constraint_for_rhs (gimple_assign_rhs1 (t), &rhsc);
- for (i = 2; i < gimple_num_ops (t); ++i)
- {
- get_constraint_for_rhs (gimple_op (t, i), &tmp);
- FOR_EACH_VEC_ELT (tmp, j, rhsp)
- rhsc.safe_push (*rhsp);
- tmp.truncate (0);
- }
- tmp.release ();
- }
- process_all_all_constraints (lhsc, rhsc);
- }
- /* If there is a store to a global variable the rhs escapes. */
- if ((lhsop = get_base_address (lhsop)) != NULL_TREE
- && DECL_P (lhsop)
- && is_global_var (lhsop)
- && (!in_ipa_mode
- || DECL_EXTERNAL (lhsop) || TREE_PUBLIC (lhsop)))
- make_escape_constraint (rhsop);
- }
- /* Handle escapes through return. */
- else if (gimple_code (t) == GIMPLE_RETURN
- && gimple_return_retval (t) != NULL_TREE)
- {
- fi = NULL;
- if (!in_ipa_mode
- || !(fi = get_vi_for_tree (cfun->decl)))
- make_escape_constraint (gimple_return_retval (t));
- else if (in_ipa_mode
- && fi != NULL)
- {
- struct constraint_expr lhs ;
- struct constraint_expr *rhsp;
- unsigned i;
-
- lhs = get_function_part_constraint (fi, fi_result);
- get_constraint_for_rhs (gimple_return_retval (t), &rhsc);
- FOR_EACH_VEC_ELT (rhsc, i, rhsp)
- process_constraint (new_constraint (lhs, *rhsp));
- }
- }
- /* Handle asms conservatively by adding escape constraints to everything. */
- else if (gimple_code (t) == GIMPLE_ASM)
- {
- unsigned i, noutputs;
- const char **oconstraints;
- const char *constraint;
- bool allows_mem, allows_reg, is_inout;
-
- noutputs = gimple_asm_noutputs (t);
- oconstraints = XALLOCAVEC (const char *, noutputs);
-
- for (i = 0; i < noutputs; ++i)
- {
- tree link = gimple_asm_output_op (t, i);
- tree op = TREE_VALUE (link);
-
- constraint = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
- oconstraints[i] = constraint;
- parse_output_constraint (&constraint, i, 0, 0, &allows_mem,
- &allows_reg, &is_inout);
-
- /* A memory constraint makes the address of the operand escape. */
- if (!allows_reg && allows_mem)
- make_escape_constraint (build_fold_addr_expr (op));
-
- /* The asm may read global memory, so outputs may point to
- any global memory. */
- if (op)
- {
- vec<ce_s> lhsc = vNULL;
- struct constraint_expr rhsc, *lhsp;
- unsigned j;
- get_constraint_for (op, &lhsc);
- rhsc.var = nonlocal_id;
- rhsc.offset = 0;
- rhsc.type = SCALAR;
- FOR_EACH_VEC_ELT (lhsc, j, lhsp)
- process_constraint (new_constraint (*lhsp, rhsc));
- lhsc.release ();
- }
- }
- for (i = 0; i < gimple_asm_ninputs (t); ++i)
- {
- tree link = gimple_asm_input_op (t, i);
- tree op = TREE_VALUE (link);
-
- constraint = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
-
- parse_input_constraint (&constraint, 0, 0, noutputs, 0, oconstraints,
- &allows_mem, &allows_reg);
-
- /* A memory constraint makes the address of the operand escape. */
- if (!allows_reg && allows_mem)
- make_escape_constraint (build_fold_addr_expr (op));
- /* Strictly we'd only need the constraint to ESCAPED if
- the asm clobbers memory, otherwise using something
- along the lines of per-call clobbers/uses would be enough. */
- else if (op)
- make_escape_constraint (op);
- }
- }
-
- rhsc.release ();
- lhsc.release ();
-}
-
-
-/* Create a constraint adding to the clobber set of FI the memory
- pointed to by PTR. */
-
-static void
-process_ipa_clobber (varinfo_t fi, tree ptr)
-{
- vec<ce_s> ptrc = vNULL;
- struct constraint_expr *c, lhs;
- unsigned i;
- get_constraint_for_rhs (ptr, &ptrc);
- lhs = get_function_part_constraint (fi, fi_clobbers);
- FOR_EACH_VEC_ELT (ptrc, i, c)
- process_constraint (new_constraint (lhs, *c));
- ptrc.release ();
-}
-
-/* Walk statement T setting up clobber and use constraints according to the
- references found in T. This function is a main part of the
- IPA constraint builder. */
-
-static void
-find_func_clobbers (gimple origt)
-{
- gimple t = origt;
- vec<ce_s> lhsc = vNULL;
- vec<ce_s> rhsc = vNULL;
- varinfo_t fi;
-
- /* Add constraints for clobbered/used in IPA mode.
- We are not interested in what automatic variables are clobbered
- or used as we only use the information in the caller to which
- they do not escape. */
- gcc_assert (in_ipa_mode);
-
- /* If the stmt refers to memory in any way it better had a VUSE. */
- if (gimple_vuse (t) == NULL_TREE)
- return;
-
- /* We'd better have function information for the current function. */
- fi = lookup_vi_for_tree (cfun->decl);
- gcc_assert (fi != NULL);
-
- /* Account for stores in assignments and calls. */
- if (gimple_vdef (t) != NULL_TREE
- && gimple_has_lhs (t))
- {
- tree lhs = gimple_get_lhs (t);
- tree tem = lhs;
- while (handled_component_p (tem))
- tem = TREE_OPERAND (tem, 0);
- if ((DECL_P (tem)
- && !auto_var_in_fn_p (tem, cfun->decl))
- || INDIRECT_REF_P (tem)
- || (TREE_CODE (tem) == MEM_REF
- && !(TREE_CODE (TREE_OPERAND (tem, 0)) == ADDR_EXPR
- && auto_var_in_fn_p
- (TREE_OPERAND (TREE_OPERAND (tem, 0), 0), cfun->decl))))
- {
- struct constraint_expr lhsc, *rhsp;
- unsigned i;
- lhsc = get_function_part_constraint (fi, fi_clobbers);
- get_constraint_for_address_of (lhs, &rhsc);
- FOR_EACH_VEC_ELT (rhsc, i, rhsp)
- process_constraint (new_constraint (lhsc, *rhsp));
- rhsc.release ();
- }
- }
-
- /* Account for uses in assigments and returns. */
- if (gimple_assign_single_p (t)
- || (gimple_code (t) == GIMPLE_RETURN
- && gimple_return_retval (t) != NULL_TREE))
- {
- tree rhs = (gimple_assign_single_p (t)
- ? gimple_assign_rhs1 (t) : gimple_return_retval (t));
- tree tem = rhs;
- while (handled_component_p (tem))
- tem = TREE_OPERAND (tem, 0);
- if ((DECL_P (tem)
- && !auto_var_in_fn_p (tem, cfun->decl))
- || INDIRECT_REF_P (tem)
- || (TREE_CODE (tem) == MEM_REF
- && !(TREE_CODE (TREE_OPERAND (tem, 0)) == ADDR_EXPR
- && auto_var_in_fn_p
- (TREE_OPERAND (TREE_OPERAND (tem, 0), 0), cfun->decl))))
- {
- struct constraint_expr lhs, *rhsp;
- unsigned i;
- lhs = get_function_part_constraint (fi, fi_uses);
- get_constraint_for_address_of (rhs, &rhsc);
- FOR_EACH_VEC_ELT (rhsc, i, rhsp)
- process_constraint (new_constraint (lhs, *rhsp));
- rhsc.release ();
- }
- }
-
- if (is_gimple_call (t))
- {
- varinfo_t cfi = NULL;
- tree decl = gimple_call_fndecl (t);
- struct constraint_expr lhs, rhs;
- unsigned i, j;
-
- /* For builtins we do not have separate function info. For those
- we do not generate escapes for we have to generate clobbers/uses. */
- if (gimple_call_builtin_p (t, BUILT_IN_NORMAL))
- switch (DECL_FUNCTION_CODE (decl))
- {
- /* The following functions use and clobber memory pointed to
- by their arguments. */
- case BUILT_IN_STRCPY:
- case BUILT_IN_STRNCPY:
- case BUILT_IN_BCOPY:
- case BUILT_IN_MEMCPY:
- case BUILT_IN_MEMMOVE:
- case BUILT_IN_MEMPCPY:
- case BUILT_IN_STPCPY:
- case BUILT_IN_STPNCPY:
- case BUILT_IN_STRCAT:
- case BUILT_IN_STRNCAT:
- case BUILT_IN_STRCPY_CHK:
- case BUILT_IN_STRNCPY_CHK:
- case BUILT_IN_MEMCPY_CHK:
- case BUILT_IN_MEMMOVE_CHK:
- case BUILT_IN_MEMPCPY_CHK:
- case BUILT_IN_STPCPY_CHK:
- case BUILT_IN_STPNCPY_CHK:
- case BUILT_IN_STRCAT_CHK:
- case BUILT_IN_STRNCAT_CHK:
- {
- tree dest = gimple_call_arg (t, (DECL_FUNCTION_CODE (decl)
- == BUILT_IN_BCOPY ? 1 : 0));
- tree src = gimple_call_arg (t, (DECL_FUNCTION_CODE (decl)
- == BUILT_IN_BCOPY ? 0 : 1));
- unsigned i;
- struct constraint_expr *rhsp, *lhsp;
- get_constraint_for_ptr_offset (dest, NULL_TREE, &lhsc);
- lhs = get_function_part_constraint (fi, fi_clobbers);
- FOR_EACH_VEC_ELT (lhsc, i, lhsp)
- process_constraint (new_constraint (lhs, *lhsp));
- lhsc.release ();
- get_constraint_for_ptr_offset (src, NULL_TREE, &rhsc);
- lhs = get_function_part_constraint (fi, fi_uses);
- FOR_EACH_VEC_ELT (rhsc, i, rhsp)
- process_constraint (new_constraint (lhs, *rhsp));
- rhsc.release ();
- return;
- }
- /* The following function clobbers memory pointed to by
- its argument. */
- case BUILT_IN_MEMSET:
- case BUILT_IN_MEMSET_CHK:
- {
- tree dest = gimple_call_arg (t, 0);
- unsigned i;
- ce_s *lhsp;
- get_constraint_for_ptr_offset (dest, NULL_TREE, &lhsc);
- lhs = get_function_part_constraint (fi, fi_clobbers);
- FOR_EACH_VEC_ELT (lhsc, i, lhsp)
- process_constraint (new_constraint (lhs, *lhsp));
- lhsc.release ();
- return;
- }
- /* The following functions clobber their second and third
- arguments. */
- case BUILT_IN_SINCOS:
- case BUILT_IN_SINCOSF:
- case BUILT_IN_SINCOSL:
- {
- process_ipa_clobber (fi, gimple_call_arg (t, 1));
- process_ipa_clobber (fi, gimple_call_arg (t, 2));
- return;
- }
- /* The following functions clobber their second argument. */
- case BUILT_IN_FREXP:
- case BUILT_IN_FREXPF:
- case BUILT_IN_FREXPL:
- case BUILT_IN_LGAMMA_R:
- case BUILT_IN_LGAMMAF_R:
- case BUILT_IN_LGAMMAL_R:
- case BUILT_IN_GAMMA_R:
- case BUILT_IN_GAMMAF_R:
- case BUILT_IN_GAMMAL_R:
- case BUILT_IN_MODF:
- case BUILT_IN_MODFF:
- case BUILT_IN_MODFL:
- {
- process_ipa_clobber (fi, gimple_call_arg (t, 1));
- return;
- }
- /* The following functions clobber their third argument. */
- case BUILT_IN_REMQUO:
- case BUILT_IN_REMQUOF:
- case BUILT_IN_REMQUOL:
- {
- process_ipa_clobber (fi, gimple_call_arg (t, 2));
- return;
- }
- /* The following functions neither read nor clobber memory. */
- case BUILT_IN_ASSUME_ALIGNED:
- case BUILT_IN_FREE:
- return;
- /* Trampolines are of no interest to us. */
- case BUILT_IN_INIT_TRAMPOLINE:
- case BUILT_IN_ADJUST_TRAMPOLINE:
- return;
- case BUILT_IN_VA_START:
- case BUILT_IN_VA_END:
- return;
- /* printf-style functions may have hooks to set pointers to
- point to somewhere into the generated string. Leave them
- for a later excercise... */
- default:
- /* Fallthru to general call handling. */;
- }
-
- /* Parameters passed by value are used. */
- lhs = get_function_part_constraint (fi, fi_uses);
- for (i = 0; i < gimple_call_num_args (t); i++)
- {
- struct constraint_expr *rhsp;
- tree arg = gimple_call_arg (t, i);
-
- if (TREE_CODE (arg) == SSA_NAME
- || is_gimple_min_invariant (arg))
- continue;
-
- get_constraint_for_address_of (arg, &rhsc);
- FOR_EACH_VEC_ELT (rhsc, j, rhsp)
- process_constraint (new_constraint (lhs, *rhsp));
- rhsc.release ();
- }
-
- /* Build constraints for propagating clobbers/uses along the
- callgraph edges. */
- cfi = get_fi_for_callee (t);
- if (cfi->id == anything_id)
- {
- if (gimple_vdef (t))
- make_constraint_from (first_vi_for_offset (fi, fi_clobbers),
- anything_id);
- make_constraint_from (first_vi_for_offset (fi, fi_uses),
- anything_id);
- return;
- }
-
- /* For callees without function info (that's external functions),
- ESCAPED is clobbered and used. */
- if (gimple_call_fndecl (t)
- && !cfi->is_fn_info)
- {
- varinfo_t vi;
-
- if (gimple_vdef (t))
- make_copy_constraint (first_vi_for_offset (fi, fi_clobbers),
- escaped_id);
- make_copy_constraint (first_vi_for_offset (fi, fi_uses), escaped_id);
-
- /* Also honor the call statement use/clobber info. */
- if ((vi = lookup_call_clobber_vi (t)) != NULL)
- make_copy_constraint (first_vi_for_offset (fi, fi_clobbers),
- vi->id);
- if ((vi = lookup_call_use_vi (t)) != NULL)
- make_copy_constraint (first_vi_for_offset (fi, fi_uses),
- vi->id);
- return;
- }
-
- /* Otherwise the caller clobbers and uses what the callee does.
- ??? This should use a new complex constraint that filters
- local variables of the callee. */
- if (gimple_vdef (t))
- {
- lhs = get_function_part_constraint (fi, fi_clobbers);
- rhs = get_function_part_constraint (cfi, fi_clobbers);
- process_constraint (new_constraint (lhs, rhs));
- }
- lhs = get_function_part_constraint (fi, fi_uses);
- rhs = get_function_part_constraint (cfi, fi_uses);
- process_constraint (new_constraint (lhs, rhs));
- }
- else if (gimple_code (t) == GIMPLE_ASM)
- {
- /* ??? Ick. We can do better. */
- if (gimple_vdef (t))
- make_constraint_from (first_vi_for_offset (fi, fi_clobbers),
- anything_id);
- make_constraint_from (first_vi_for_offset (fi, fi_uses),
- anything_id);
- }
-
- rhsc.release ();
-}
-
-
-/* Find the first varinfo in the same variable as START 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)
-{
- /* If the offset is outside of the variable, bail out. */
- if (offset >= start->fullsize)
- return NULL;
-
- /* If we cannot reach offset from start, lookup the first field
- and start from there. */
- if (start->offset > offset)
- start = lookup_vi_for_tree (start->decl);
-
- while (start)
- {
- /* 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 >= start->offset
- && (offset - start->offset) < start->size)
- return start;
-
- start= start->next;
- }
-
- return NULL;
-}
-
-/* Find the first varinfo in the same variable as START that overlaps with
- OFFSET. If there is no such varinfo the varinfo directly preceding
- OFFSET is returned. */
-
-static varinfo_t
-first_or_preceding_vi_for_offset (varinfo_t start,
- unsigned HOST_WIDE_INT offset)
-{
- /* If we cannot reach offset from start, lookup the first field
- and start from there. */
- if (start->offset > offset)
- start = lookup_vi_for_tree (start->decl);
-
- /* 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 we got beyond the offset we look for return the field
- directly preceding offset which may be the last field. */
- while (start->next
- && offset >= start->offset
- && !((offset - start->offset) < start->size))
- start = start->next;
-
- return start;
-}
-
-
-/* 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 must_have_pointers : 1;
-
- unsigned may_have_pointers : 1;
-
- unsigned only_restrict_pointers : 1;
-};
-typedef struct fieldoff fieldoff_s;
-
-
-/* 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> fieldstack)
-{
- fieldstack.qsort (fieldoff_compare);
-}
-
-/* Return true if T is a type that can have subvars. */
-
-static inline bool
-type_can_have_subvars (const_tree t)
-{
- /* Aggregates without overlapping fields can have subvars. */
- return TREE_CODE (t) == RECORD_TYPE;
-}
-
-/* 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))
- return false;
-
- return type_can_have_subvars (TREE_TYPE (v));
-}
-
-/* Return true if T is a type that does contain pointers. */
-
-static bool
-type_must_have_pointers (tree type)
-{
- if (POINTER_TYPE_P (type))
- return true;
-
- if (TREE_CODE (type) == ARRAY_TYPE)
- return type_must_have_pointers (TREE_TYPE (type));
-
- /* A function or method can have pointers as arguments, so track
- those separately. */
- if (TREE_CODE (type) == FUNCTION_TYPE
- || TREE_CODE (type) == METHOD_TYPE)
- return true;
-
- return false;
-}
-
-static bool
-field_must_have_pointers (tree t)
-{
- return type_must_have_pointers (TREE_TYPE (t));
-}
-
-/* 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 false if the caller is supposed to handle the field we
- recursed for. */
-
-static bool
-push_fields_onto_fieldstack (tree type, vec<fieldoff_s> *fieldstack,
- HOST_WIDE_INT offset)
-{
- tree field;
- bool empty_p = true;
-
- if (TREE_CODE (type) != RECORD_TYPE)
- return false;
-
- /* 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 (fieldstack->length () > MAX_FIELDS_FOR_FIELD_SENSITIVE)
- return false;
-
- for (field = TYPE_FIELDS (type); field; field = DECL_CHAIN (field))
- if (TREE_CODE (field) == FIELD_DECL)
- {
- bool push = false;
- 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 (!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;
- bool must_have_pointers_p;
-
- if (!fieldstack->is_empty ())
- pair = &fieldstack->last ();
-
- /* If there isn't anything at offset zero, create sth. */
- if (!pair
- && offset + foff != 0)
- {
- fieldoff_s e = {0, offset + foff, false, false, false, false};
- pair = fieldstack->safe_push (e);
- }
-
- if (!DECL_SIZE (field)
- || !host_integerp (DECL_SIZE (field), 1))
- has_unknown_size = true;
-
- /* If adjacent fields do not contain pointers merge them. */
- must_have_pointers_p = field_must_have_pointers (field);
- if (pair
- && !has_unknown_size
- && !must_have_pointers_p
- && !pair->must_have_pointers
- && !pair->has_unknown_size
- && pair->offset + (HOST_WIDE_INT)pair->size == offset + foff)
- {
- pair->size += TREE_INT_CST_LOW (DECL_SIZE (field));
- }
- else
- {
- fieldoff_s e;
- e.offset = offset + foff;
- e.has_unknown_size = has_unknown_size;
- if (!has_unknown_size)
- e.size = TREE_INT_CST_LOW (DECL_SIZE (field));
- else
- e.size = -1;
- e.must_have_pointers = must_have_pointers_p;
- e.may_have_pointers = true;
- e.only_restrict_pointers
- = (!has_unknown_size
- && POINTER_TYPE_P (TREE_TYPE (field))
- && TYPE_RESTRICT (TREE_TYPE (field)));
- fieldstack->safe_push (e);
- }
- }
-
- empty_p = false;
- }
-
- return !empty_p;
-}
-
-/* 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 num = 0;
- tree t;
-
- /* Capture named arguments for K&R functions. They do not
- have a prototype and thus no TYPE_ARG_TYPES. */
- for (t = DECL_ARGUMENTS (decl); t; t = DECL_CHAIN (t))
- ++num;
-
- /* Check if the function has variadic arguments. */
- for (t = TYPE_ARG_TYPES (TREE_TYPE (decl)); t; t = TREE_CHAIN (t))
- if (TREE_VALUE (t) == void_type_node)
- break;
- if (!t)
- *is_varargs = true;
-
- return num;
-}
-
-/* Creation function node for DECL, using NAME, and return the index
- of the variable we've created for the function. */
-
-static varinfo_t
-create_function_info_for (tree decl, const char *name)
-{
- struct function *fn = DECL_STRUCT_FUNCTION (decl);
- varinfo_t vi, prev_vi;
- tree arg;
- unsigned int i;
- bool is_varargs = false;
- unsigned int num_args = count_num_arguments (decl, &is_varargs);
-
- /* Create the variable info. */
-
- vi = new_var_info (decl, name);
- vi->offset = 0;
- vi->size = 1;
- vi->fullsize = fi_parm_base + num_args;
- vi->is_fn_info = 1;
- vi->may_have_pointers = false;
- if (is_varargs)
- vi->fullsize = ~0;
- insert_vi_for_tree (vi->decl, vi);
-
- prev_vi = vi;
-
- /* Create a variable for things the function clobbers and one for
- things the function uses. */
- {
- varinfo_t clobbervi, usevi;
- const char *newname;
- char *tempname;
-
- asprintf (&tempname, "%s.clobber", name);
- newname = ggc_strdup (tempname);
- free (tempname);
-
- clobbervi = new_var_info (NULL, newname);
- clobbervi->offset = fi_clobbers;
- clobbervi->size = 1;
- clobbervi->fullsize = vi->fullsize;
- clobbervi->is_full_var = true;
- clobbervi->is_global_var = false;
- gcc_assert (prev_vi->offset < clobbervi->offset);
- prev_vi->next = clobbervi;
- prev_vi = clobbervi;
-
- asprintf (&tempname, "%s.use", name);
- newname = ggc_strdup (tempname);
- free (tempname);
-
- usevi = new_var_info (NULL, newname);
- usevi->offset = fi_uses;
- usevi->size = 1;
- usevi->fullsize = vi->fullsize;
- usevi->is_full_var = true;
- usevi->is_global_var = false;
- gcc_assert (prev_vi->offset < usevi->offset);
- prev_vi->next = usevi;
- prev_vi = usevi;
- }
-
- /* And one for the static chain. */
- if (fn->static_chain_decl != NULL_TREE)
- {
- varinfo_t chainvi;
- const char *newname;
- char *tempname;
-
- asprintf (&tempname, "%s.chain", name);
- newname = ggc_strdup (tempname);
- free (tempname);
-
- chainvi = new_var_info (fn->static_chain_decl, newname);
- chainvi->offset = fi_static_chain;
- chainvi->size = 1;
- chainvi->fullsize = vi->fullsize;
- chainvi->is_full_var = true;
- chainvi->is_global_var = false;
- gcc_assert (prev_vi->offset < chainvi->offset);
- prev_vi->next = chainvi;
- prev_vi = chainvi;
- insert_vi_for_tree (fn->static_chain_decl, chainvi);
- }
-
- /* 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;
- tree resultdecl = decl;
-
- if (DECL_RESULT (decl))
- resultdecl = DECL_RESULT (decl);
-
- asprintf (&tempname, "%s.result", name);
- newname = ggc_strdup (tempname);
- free (tempname);
-
- resultvi = new_var_info (resultdecl, newname);
- resultvi->offset = fi_result;
- resultvi->size = 1;
- resultvi->fullsize = vi->fullsize;
- resultvi->is_full_var = true;
- if (DECL_RESULT (decl))
- resultvi->may_have_pointers = true;
- gcc_assert (prev_vi->offset < resultvi->offset);
- prev_vi->next = resultvi;
- prev_vi = resultvi;
- if (DECL_RESULT (decl))
- insert_vi_for_tree (DECL_RESULT (decl), resultvi);
- }
-
- /* Set up variables for each argument. */
- arg = DECL_ARGUMENTS (decl);
- for (i = 0; i < num_args; i++)
- {
- varinfo_t argvi;
- const char *newname;
- char *tempname;
- tree argdecl = decl;
-
- if (arg)
- argdecl = arg;
-
- asprintf (&tempname, "%s.arg%d", name, i);
- newname = ggc_strdup (tempname);
- free (tempname);
-
- argvi = new_var_info (argdecl, newname);
- argvi->offset = fi_parm_base + i;
- argvi->size = 1;
- argvi->is_full_var = true;
- argvi->fullsize = vi->fullsize;
- if (arg)
- argvi->may_have_pointers = true;
- gcc_assert (prev_vi->offset < argvi->offset);
- prev_vi->next = argvi;
- prev_vi = argvi;
- if (arg)
- {
- insert_vi_for_tree (arg, argvi);
- arg = DECL_CHAIN (arg);
- }
- }
-
- /* Add one representative for all further args. */
- if (is_varargs)
- {
- varinfo_t argvi;
- const char *newname;
- char *tempname;
- tree decl;
-
- asprintf (&tempname, "%s.varargs", name);
- newname = ggc_strdup (tempname);
- free (tempname);
-
- /* We need sth that can be pointed to for va_start. */
- decl = build_fake_var_decl (ptr_type_node);
-
- argvi = new_var_info (decl, newname);
- argvi->offset = fi_parm_base + num_args;
- argvi->size = ~0;
- argvi->is_full_var = true;
- argvi->is_heap_var = true;
- argvi->fullsize = vi->fullsize;
- gcc_assert (prev_vi->offset < argvi->offset);
- prev_vi->next = argvi;
- prev_vi = argvi;
- }
-
- return vi;
-}
-
-
-/* Return true if FIELDSTACK contains fields that overlap.
- FIELDSTACK is assumed to be sorted by offset. */
-
-static bool
-check_for_overlaps (vec<fieldoff_s> fieldstack)
-{
- fieldoff_s *fo = NULL;
- unsigned int i;
- HOST_WIDE_INT lastoffset = -1;
-
- FOR_EACH_VEC_ELT (fieldstack, i, fo)
- {
- 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 varinfo_t
-create_variable_info_for_1 (tree decl, const char *name)
-{
- varinfo_t vi, newvi;
- tree decl_type = TREE_TYPE (decl);
- tree declsize = DECL_P (decl) ? DECL_SIZE (decl) : TYPE_SIZE (decl_type);
- vec<fieldoff_s> fieldstack = vNULL;
- fieldoff_s *fo;
- unsigned int i;
-
- if (!declsize
- || !host_integerp (declsize, 1))
- {
- vi = new_var_info (decl, name);
- vi->offset = 0;
- vi->size = ~0;
- vi->fullsize = ~0;
- vi->is_unknown_size_var = true;
- vi->is_full_var = true;
- vi->may_have_pointers = true;
- return vi;
- }
-
- /* Collect field information. */
- if (use_field_sensitive
- && var_can_have_subvars (decl)
- /* ??? Force us to not use subfields for global initializers
- in IPA mode. Else we'd have to parse arbitrary initializers. */
- && !(in_ipa_mode
- && is_global_var (decl)
- && DECL_INITIAL (decl)))
- {
- fieldoff_s *fo = NULL;
- bool notokay = false;
- unsigned int i;
-
- push_fields_onto_fieldstack (decl_type, &fieldstack, 0);
-
- for (i = 0; !notokay && fieldstack.iterate (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 (notokay)
- fieldstack.release ();
- }
-
- /* If we didn't end up collecting sub-variables create a full
- variable for the decl. */
- if (fieldstack.length () <= 1
- || fieldstack.length () > MAX_FIELDS_FOR_FIELD_SENSITIVE)
- {
- vi = new_var_info (decl, name);
- vi->offset = 0;
- vi->may_have_pointers = true;
- vi->fullsize = TREE_INT_CST_LOW (declsize);
- vi->size = vi->fullsize;
- vi->is_full_var = true;
- fieldstack.release ();
- return vi;
- }
-
- vi = new_var_info (decl, name);
- vi->fullsize = TREE_INT_CST_LOW (declsize);
- for (i = 0, newvi = vi;
- fieldstack.iterate (i, &fo);
- ++i, newvi = newvi->next)
- {
- const char *newname = "NULL";
- char *tempname;
-
- if (dump_file)
- {
- asprintf (&tempname, "%s." HOST_WIDE_INT_PRINT_DEC
- "+" HOST_WIDE_INT_PRINT_DEC, name, fo->offset, fo->size);
- newname = ggc_strdup (tempname);
- free (tempname);
- }
- newvi->name = newname;
- newvi->offset = fo->offset;
- newvi->size = fo->size;
- newvi->fullsize = vi->fullsize;
- newvi->may_have_pointers = fo->may_have_pointers;
- newvi->only_restrict_pointers = fo->only_restrict_pointers;
- if (i + 1 < fieldstack.length ())
- newvi->next = new_var_info (decl, name);
- }
-
- fieldstack.release ();
-
- return vi;
-}
-
-static unsigned int
-create_variable_info_for (tree decl, const char *name)
-{
- varinfo_t vi = create_variable_info_for_1 (decl, name);
- unsigned int id = vi->id;
-
- insert_vi_for_tree (decl, vi);
-
- if (TREE_CODE (decl) != VAR_DECL)
- return id;
-
- /* Create initial constraints for globals. */
- for (; vi; vi = vi->next)
- {
- if (!vi->may_have_pointers
- || !vi->is_global_var)
- continue;
-
- /* Mark global restrict qualified pointers. */
- if ((POINTER_TYPE_P (TREE_TYPE (decl))
- && TYPE_RESTRICT (TREE_TYPE (decl)))
- || vi->only_restrict_pointers)
- {
- make_constraint_from_global_restrict (vi, "GLOBAL_RESTRICT");
- continue;
- }
-
- /* In non-IPA mode the initializer from nonlocal is all we need. */
- if (!in_ipa_mode
- || DECL_HARD_REGISTER (decl))
- make_copy_constraint (vi, nonlocal_id);
-
- /* In IPA mode parse the initializer and generate proper constraints
- for it. */
- else
- {
- struct varpool_node *vnode = varpool_get_node (decl);
-
- /* For escaped variables initialize them from nonlocal. */
- if (!varpool_all_refs_explicit_p (vnode))
- make_copy_constraint (vi, nonlocal_id);
-
- /* If this is a global variable with an initializer and we are in
- IPA mode generate constraints for it. */
- if (DECL_INITIAL (decl)
- && vnode->analyzed)
- {
- vec<ce_s> rhsc = vNULL;
- struct constraint_expr lhs, *rhsp;
- unsigned i;
- get_constraint_for_rhs (DECL_INITIAL (decl), &rhsc);
- lhs.var = vi->id;
- lhs.offset = 0;
- lhs.type = SCALAR;
- FOR_EACH_VEC_ELT (rhsc, i, rhsp)
- process_constraint (new_constraint (lhs, *rhsp));
- /* If this is a variable that escapes from the unit
- the initializer escapes as well. */
- if (!varpool_all_refs_explicit_p (vnode))
- {
- lhs.var = escaped_id;
- lhs.offset = 0;
- lhs.type = SCALAR;
- FOR_EACH_VEC_ELT (rhsc, i, rhsp)
- process_constraint (new_constraint (lhs, *rhsp));
- }
- rhsc.release ();
- }
- }
- }
-
- return id;
-}
-
-/* Print out the points-to solution for VAR to FILE. */
-
-static void
-dump_solution_for_var (FILE *file, unsigned int var)
-{
- varinfo_t vi = get_varinfo (var);
- unsigned int i;
- bitmap_iterator bi;
-
- /* Dump the solution for unified vars anyway, this avoids difficulties
- in scanning dumps in the testsuite. */
- fprintf (file, "%s = { ", vi->name);
- vi = get_varinfo (find (var));
- EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
- fprintf (file, "%s ", get_varinfo (i)->name);
- fprintf (file, "}");
-
- /* But note when the variable was unified. */
- if (vi->id != var)
- fprintf (file, " same as %s", vi->name);
-
- fprintf (file, "\n");
-}
-
-/* Print the points-to solution for VAR to stdout. */
-
-DEBUG_FUNCTION 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;
-
- /* For each incoming pointer argument arg, create the constraint ARG
- = NONLOCAL or a dummy variable if it is a restrict qualified
- passed-by-reference argument. */
- for (t = DECL_ARGUMENTS (current_function_decl); t; t = DECL_CHAIN (t))
- {
- varinfo_t p = get_vi_for_tree (t);
-
- /* For restrict qualified pointers to objects passed by
- reference build a real representative for the pointed-to object.
- Treat restrict qualified references the same. */
- if (TYPE_RESTRICT (TREE_TYPE (t))
- && ((DECL_BY_REFERENCE (t) && POINTER_TYPE_P (TREE_TYPE (t)))
- || TREE_CODE (TREE_TYPE (t)) == REFERENCE_TYPE)
- && !type_contains_placeholder_p (TREE_TYPE (TREE_TYPE (t))))
- {
- struct constraint_expr lhsc, rhsc;
- varinfo_t vi;
- tree heapvar = build_fake_var_decl (TREE_TYPE (TREE_TYPE (t)));
- DECL_EXTERNAL (heapvar) = 1;
- vi = create_variable_info_for_1 (heapvar, "PARM_NOALIAS");
- insert_vi_for_tree (heapvar, vi);
- lhsc.var = p->id;
- lhsc.type = SCALAR;
- lhsc.offset = 0;
- rhsc.var = vi->id;
- rhsc.type = ADDRESSOF;
- rhsc.offset = 0;
- process_constraint (new_constraint (lhsc, rhsc));
- for (; vi; vi = vi->next)
- if (vi->may_have_pointers)
- {
- if (vi->only_restrict_pointers)
- make_constraint_from_global_restrict (vi, "GLOBAL_RESTRICT");
- else
- make_copy_constraint (vi, nonlocal_id);
- }
- continue;
- }
-
- if (POINTER_TYPE_P (TREE_TYPE (t))
- && TYPE_RESTRICT (TREE_TYPE (t)))
- make_constraint_from_global_restrict (p, "PARM_RESTRICT");
- else
- {
- for (; p; p = p->next)
- {
- if (p->only_restrict_pointers)
- make_constraint_from_global_restrict (p, "PARM_RESTRICT");
- else if (p->may_have_pointers)
- 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. */
-
-static void
-set_uids_in_ptset (bitmap into, bitmap from, struct pt_solution *pt)
-{
- unsigned int i;
- bitmap_iterator bi;
-
- 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)
- {
- /* If we are in IPA mode we will not recompute points-to
- sets after inlining so make sure they stay valid. */
- if (in_ipa_mode
- && !DECL_PT_UID_SET_P (vi->decl))
- SET_DECL_PT_UID (vi->decl, DECL_UID (vi->decl));
-
- /* Add the decl to the points-to set. Note that the points-to
- set contains global variables. */
- bitmap_set_bit (into, DECL_PT_UID (vi->decl));
- if (vi->is_global_var)
- pt->vars_contains_global = true;
- }
- }
-}
-
-
-/* Compute the points-to solution *PT for the variable VI. */
-
-static struct pt_solution
-find_what_var_points_to (varinfo_t orig_vi)
-{
- unsigned int i;
- bitmap_iterator bi;
- bitmap finished_solution;
- bitmap result;
- varinfo_t vi;
- void **slot;
- struct pt_solution *pt;
-
- /* This variable may have been collapsed, let's get the real
- variable. */
- vi = get_varinfo (find (orig_vi->id));
-
- /* See if we have already computed the solution and return it. */
- slot = pointer_map_insert (final_solutions, vi);
- if (*slot != NULL)
- return *(struct pt_solution *)*slot;
-
- *slot = pt = XOBNEW (&final_solutions_obstack, struct pt_solution);
- memset (pt, 0, sizeof (struct pt_solution));
-
- /* 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)
- {
- if (vi->id == nothing_id)
- pt->null = 1;
- else if (vi->id == escaped_id)
- {
- if (in_ipa_mode)
- pt->ipa_escaped = 1;
- else
- pt->escaped = 1;
- }
- else if (vi->id == nonlocal_id)
- pt->nonlocal = 1;
- else if (vi->is_heap_var)
- /* We represent heapvars in the points-to set properly. */
- ;
- else if (vi->id == readonly_id)
- /* Nobody cares. */
- ;
- else if (vi->id == anything_id
- || vi->id == integer_id)
- pt->anything = 1;
- }
- }
-
- /* Instead of doing extra work, simply do not create
- elaborate points-to information for pt_anything pointers. */
- if (pt->anything)
- return *pt;
-
- /* Share the final set of variables when possible. */
- finished_solution = BITMAP_GGC_ALLOC ();
- stats.points_to_sets_created++;
-
- set_uids_in_ptset (finished_solution, vi->solution, pt);
- result = shared_bitmap_lookup (finished_solution);
- if (!result)
- {
- shared_bitmap_add (finished_solution);
- pt->vars = finished_solution;
- }
- else
- {
- pt->vars = result;
- bitmap_clear (finished_solution);
- }
-
- return *pt;
-}
-
-/* Given a pointer variable P, fill in its points-to set. */
-
-static void
-find_what_p_points_to (tree p)
-{
- struct ptr_info_def *pi;
- tree lookup_p = p;
- varinfo_t vi;
-
- /* For parameters, get at the points-to set for the actual parm
- decl. */
- if (TREE_CODE (p) == SSA_NAME
- && SSA_NAME_IS_DEFAULT_DEF (p)
- && (TREE_CODE (SSA_NAME_VAR (p)) == PARM_DECL
- || TREE_CODE (SSA_NAME_VAR (p)) == RESULT_DECL))
- lookup_p = SSA_NAME_VAR (p);
-
- vi = lookup_vi_for_tree (lookup_p);
- if (!vi)
- return;
-
- pi = get_ptr_info (p);
- pi->pt = find_what_var_points_to (vi);
-}
-
-
-/* Query statistics for points-to solutions. */
-
-static struct {
- unsigned HOST_WIDE_INT pt_solution_includes_may_alias;
- unsigned HOST_WIDE_INT pt_solution_includes_no_alias;
- unsigned HOST_WIDE_INT pt_solutions_intersect_may_alias;
- unsigned HOST_WIDE_INT pt_solutions_intersect_no_alias;
-} pta_stats;
-
-void
-dump_pta_stats (FILE *s)
-{
- fprintf (s, "\nPTA query stats:\n");
- fprintf (s, " pt_solution_includes: "
- HOST_WIDE_INT_PRINT_DEC" disambiguations, "
- HOST_WIDE_INT_PRINT_DEC" queries\n",
- pta_stats.pt_solution_includes_no_alias,
- pta_stats.pt_solution_includes_no_alias
- + pta_stats.pt_solution_includes_may_alias);
- fprintf (s, " pt_solutions_intersect: "
- HOST_WIDE_INT_PRINT_DEC" disambiguations, "
- HOST_WIDE_INT_PRINT_DEC" queries\n",
- pta_stats.pt_solutions_intersect_no_alias,
- pta_stats.pt_solutions_intersect_no_alias
- + pta_stats.pt_solutions_intersect_may_alias);
-}
-
-
-/* Reset the points-to solution *PT to a conservative default
- (point to anything). */
-
-void
-pt_solution_reset (struct pt_solution *pt)
-{
- memset (pt, 0, sizeof (struct pt_solution));
- pt->anything = true;
-}
-
-/* Set the points-to solution *PT to point only to the variables
- in VARS. VARS_CONTAINS_GLOBAL specifies whether that contains
- global variables and VARS_CONTAINS_RESTRICT specifies whether
- it contains restrict tag variables. */
-
-void
-pt_solution_set (struct pt_solution *pt, bitmap vars, bool vars_contains_global)
-{
- memset (pt, 0, sizeof (struct pt_solution));
- pt->vars = vars;
- pt->vars_contains_global = vars_contains_global;
-}
-
-/* Set the points-to solution *PT to point only to the variable VAR. */
-
-void
-pt_solution_set_var (struct pt_solution *pt, tree var)
-{
- memset (pt, 0, sizeof (struct pt_solution));
- pt->vars = BITMAP_GGC_ALLOC ();
- bitmap_set_bit (pt->vars, DECL_PT_UID (var));
- pt->vars_contains_global = is_global_var (var);
-}
-
-/* Computes the union of the points-to solutions *DEST and *SRC and
- stores the result in *DEST. This changes the points-to bitmap
- of *DEST and thus may not be used if that might be shared.
- The points-to bitmap of *SRC and *DEST will not be shared after
- this function if they were not before. */
-
-static void
-pt_solution_ior_into (struct pt_solution *dest, struct pt_solution *src)
-{
- dest->anything |= src->anything;
- if (dest->anything)
- {
- pt_solution_reset (dest);
- return;
- }
-
- dest->nonlocal |= src->nonlocal;
- dest->escaped |= src->escaped;
- dest->ipa_escaped |= src->ipa_escaped;
- dest->null |= src->null;
- dest->vars_contains_global |= src->vars_contains_global;
- if (!src->vars)
- return;
-
- if (!dest->vars)
- dest->vars = BITMAP_GGC_ALLOC ();
- bitmap_ior_into (dest->vars, src->vars);
-}
-
-/* Return true if the points-to solution *PT is empty. */
-
-bool
-pt_solution_empty_p (struct pt_solution *pt)
-{
- if (pt->anything
- || pt->nonlocal)
- return false;
-
- if (pt->vars
- && !bitmap_empty_p (pt->vars))
- return false;
-
- /* If the solution includes ESCAPED, check if that is empty. */
- if (pt->escaped
- && !pt_solution_empty_p (&cfun->gimple_df->escaped))
- return false;
-
- /* If the solution includes ESCAPED, check if that is empty. */
- if (pt->ipa_escaped
- && !pt_solution_empty_p (&ipa_escaped_pt))
- return false;
-
- return true;
-}
-
-/* Return true if the points-to solution *PT only point to a single var, and
- return the var uid in *UID. */
-
-bool
-pt_solution_singleton_p (struct pt_solution *pt, unsigned *uid)
-{
- if (pt->anything || pt->nonlocal || pt->escaped || pt->ipa_escaped
- || pt->null || pt->vars == NULL
- || !bitmap_single_bit_set_p (pt->vars))
- return false;
-
- *uid = bitmap_first_set_bit (pt->vars);
- return true;
-}
-
-/* Return true if the points-to solution *PT includes global memory. */
-
-bool
-pt_solution_includes_global (struct pt_solution *pt)
-{
- if (pt->anything
- || pt->nonlocal
- || pt->vars_contains_global)
- return true;
-
- if (pt->escaped)
- return pt_solution_includes_global (&cfun->gimple_df->escaped);
-
- if (pt->ipa_escaped)
- return pt_solution_includes_global (&ipa_escaped_pt);
-
- /* ??? This predicate is not correct for the IPA-PTA solution
- as we do not properly distinguish between unit escape points
- and global variables. */
- if (cfun->gimple_df->ipa_pta)
- return true;
-
- return false;
-}
-
-/* Return true if the points-to solution *PT includes the variable
- declaration DECL. */
-
-static bool
-pt_solution_includes_1 (struct pt_solution *pt, const_tree decl)
-{
- if (pt->anything)
- return true;
-
- if (pt->nonlocal
- && is_global_var (decl))
- return true;
-
- if (pt->vars
- && bitmap_bit_p (pt->vars, DECL_PT_UID (decl)))
- return true;
-
- /* If the solution includes ESCAPED, check it. */
- if (pt->escaped
- && pt_solution_includes_1 (&cfun->gimple_df->escaped, decl))
- return true;
-
- /* If the solution includes ESCAPED, check it. */
- if (pt->ipa_escaped
- && pt_solution_includes_1 (&ipa_escaped_pt, decl))
- return true;
-
- return false;
-}
-
-bool
-pt_solution_includes (struct pt_solution *pt, const_tree decl)
-{
- bool res = pt_solution_includes_1 (pt, decl);
- if (res)
- ++pta_stats.pt_solution_includes_may_alias;
- else
- ++pta_stats.pt_solution_includes_no_alias;
- return res;
-}
-
-/* Return true if both points-to solutions PT1 and PT2 have a non-empty
- intersection. */
-
-static bool
-pt_solutions_intersect_1 (struct pt_solution *pt1, struct pt_solution *pt2)
-{
- if (pt1->anything || pt2->anything)
- return true;
-
- /* If either points to unknown global memory and the other points to
- any global memory they alias. */
- if ((pt1->nonlocal
- && (pt2->nonlocal
- || pt2->vars_contains_global))
- || (pt2->nonlocal
- && pt1->vars_contains_global))
- return true;
-
- /* Check the escaped solution if required. */
- if ((pt1->escaped || pt2->escaped)
- && !pt_solution_empty_p (&cfun->gimple_df->escaped))
- {
- /* If both point to escaped memory and that solution
- is not empty they alias. */
- if (pt1->escaped && pt2->escaped)
- return true;
-
- /* If either points to escaped memory see if the escaped solution
- intersects with the other. */
- if ((pt1->escaped
- && pt_solutions_intersect_1 (&cfun->gimple_df->escaped, pt2))
- || (pt2->escaped
- && pt_solutions_intersect_1 (&cfun->gimple_df->escaped, pt1)))
- return true;
- }
-
- /* Check the escaped solution if required.
- ??? Do we need to check the local against the IPA escaped sets? */
- if ((pt1->ipa_escaped || pt2->ipa_escaped)
- && !pt_solution_empty_p (&ipa_escaped_pt))
- {
- /* If both point to escaped memory and that solution
- is not empty they alias. */
- if (pt1->ipa_escaped && pt2->ipa_escaped)
- return true;
-
- /* If either points to escaped memory see if the escaped solution
- intersects with the other. */
- if ((pt1->ipa_escaped
- && pt_solutions_intersect_1 (&ipa_escaped_pt, pt2))
- || (pt2->ipa_escaped
- && pt_solutions_intersect_1 (&ipa_escaped_pt, pt1)))
- return true;
- }
-
- /* Now both pointers alias if their points-to solution intersects. */
- return (pt1->vars
- && pt2->vars
- && bitmap_intersect_p (pt1->vars, pt2->vars));
-}
-
-bool
-pt_solutions_intersect (struct pt_solution *pt1, struct pt_solution *pt2)
-{
- bool res = pt_solutions_intersect_1 (pt1, pt2);
- if (res)
- ++pta_stats.pt_solutions_intersect_may_alias;
- else
- ++pta_stats.pt_solutions_intersect_no_alias;
- return res;
-}
-
-
-/* Dump points-to information to OUTFILE. */
-
-static 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 < varmap.length (); i++)
- {
- varinfo_t vi = get_varinfo (i);
- if (!vi->may_have_pointers)
- continue;
- dump_solution_for_var (outfile, i);
- }
-}
-
-
-/* Debug points-to information to stderr. */
-
-DEBUG_FUNCTION 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;
- varinfo_t var_anything;
- varinfo_t var_nothing;
- varinfo_t var_readonly;
- varinfo_t var_escaped;
- varinfo_t var_nonlocal;
- varinfo_t var_storedanything;
- varinfo_t var_integer;
-
- /* Create the NULL variable, used to represent that a variable points
- to NULL. */
- var_nothing = new_var_info (NULL_TREE, "NULL");
- gcc_assert (var_nothing->id == nothing_id);
- var_nothing->is_artificial_var = 1;
- var_nothing->offset = 0;
- var_nothing->size = ~0;
- var_nothing->fullsize = ~0;
- var_nothing->is_special_var = 1;
- var_nothing->may_have_pointers = 0;
- var_nothing->is_global_var = 0;
-
- /* Create the ANYTHING variable, used to represent that a variable
- points to some unknown piece of memory. */
- var_anything = new_var_info (NULL_TREE, "ANYTHING");
- gcc_assert (var_anything->id == anything_id);
- 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. */
- 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. */
- constraints.safe_push (new_constraint (lhs, rhs));
-
- /* Create the READONLY variable, used to represent that a variable
- points to readonly memory. */
- var_readonly = new_var_info (NULL_TREE, "READONLY");
- gcc_assert (var_readonly->id == readonly_id);
- 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;
-
- /* 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. */
- var_escaped = new_var_info (NULL_TREE, "ESCAPED");
- gcc_assert (var_escaped->id == escaped_id);
- var_escaped->is_artificial_var = 1;
- var_escaped->offset = 0;
- var_escaped->size = ~0;
- var_escaped->fullsize = ~0;
- var_escaped->is_special_var = 0;
-
- /* Create the NONLOCAL variable, used to represent the set of nonlocal
- memory. */
- var_nonlocal = new_var_info (NULL_TREE, "NONLOCAL");
- gcc_assert (var_nonlocal->id == nonlocal_id);
- var_nonlocal->is_artificial_var = 1;
- var_nonlocal->offset = 0;
- var_nonlocal->size = ~0;
- var_nonlocal->fullsize = ~0;
- var_nonlocal->is_special_var = 1;
-
- /* 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));
-
- /* ESCAPED = ESCAPED + UNKNOWN_OFFSET, because if a sub-field escapes the
- whole variable escapes. */
- lhs.type = SCALAR;
- lhs.var = escaped_id;
- lhs.offset = 0;
- rhs.type = SCALAR;
- rhs.var = escaped_id;
- rhs.offset = UNKNOWN_OFFSET;
- process_constraint (new_constraint (lhs, rhs));
-
- /* *ESCAPED = NONLOCAL. This is true because we have to assume
- everything pointed to by escaped points to what global memory can
- point to. */
- lhs.type = DEREF;
- lhs.var = escaped_id;
- lhs.offset = 0;
- rhs.type = SCALAR;
- rhs.var = nonlocal_id;
- rhs.offset = 0;
- process_constraint (new_constraint (lhs, rhs));
-
- /* NONLOCAL = &NONLOCAL, NONLOCAL = &ESCAPED. This is true because
- global memory may point to global memory and escaped memory. */
- lhs.type = SCALAR;
- lhs.var = nonlocal_id;
- lhs.offset = 0;
- rhs.type = ADDRESSOF;
- rhs.var = nonlocal_id;
- rhs.offset = 0;
- process_constraint (new_constraint (lhs, rhs));
- rhs.type = ADDRESSOF;
- rhs.var = escaped_id;
- rhs.offset = 0;
- process_constraint (new_constraint (lhs, rhs));
-
- /* Create the STOREDANYTHING variable, used to represent the set of
- variables stored to *ANYTHING. */
- var_storedanything = new_var_info (NULL_TREE, "STOREDANYTHING");
- gcc_assert (var_storedanything->id == storedanything_id);
- var_storedanything->is_artificial_var = 1;
- var_storedanything->offset = 0;
- var_storedanything->size = ~0;
- var_storedanything->fullsize = ~0;
- var_storedanything->is_special_var = 0;
-
- /* Create the INTEGER variable, used to represent that a variable points
- to what an INTEGER "points to". */
- var_integer = new_var_info (NULL_TREE, "INTEGER");
- gcc_assert (var_integer->id == integer_id);
- 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;
-
- /* 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));
-}
-
-/* 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.create (8);
- varmap.create (8);
- vi_for_tree = pointer_map_create ();
- call_stmt_vars = pointer_map_create ();
-
- memset (&stats, 0, sizeof (stats));
- shared_bitmap_table = htab_create (511, shared_bitmap_hash,
- shared_bitmap_eq, free);
- init_base_vars ();
-
- gcc_obstack_init (&fake_var_decl_obstack);
-
- final_solutions = pointer_map_create ();
- gcc_obstack_init (&final_solutions_obstack);
-}
-
-/* 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 = varmap.length ();
- 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);
-}
-
-/* Solve the constraint set. */
-
-static void
-solve_constraints (void)
-{
- struct scc_info *si;
-
- if (dump_file)
- fprintf (dump_file,
- "\nCollapsing static cycles and doing variable "
- "substitution\n");
-
- init_graph (varmap.length () * 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);
-
- /* Attach complex constraints to graph nodes. */
- 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 && (dump_flags & TDF_GRAPH))
- {
- fprintf (dump_file, "\n\n// The constraint graph before solve-graph "
- "in dot format:\n");
- dump_constraint_graph (dump_file);
- fprintf (dump_file, "\n\n");
- }
-
- if (dump_file)
- fprintf (dump_file, "Solving graph\n");
-
- solve_graph (graph);
-
- if (dump_file && (dump_flags & TDF_GRAPH))
- {
- fprintf (dump_file, "\n\n// The constraint graph after solve-graph "
- "in dot format:\n");
- dump_constraint_graph (dump_file);
- fprintf (dump_file, "\n\n");
- }
-
- if (dump_file)
- dump_sa_points_to_info (dump_file);
-}
-
-/* Create points-to sets for the current function. See the comments
- at the start of the file for an algorithmic overview. */
-
-static void
-compute_points_to_sets (void)
-{
- basic_block bb;
- unsigned i;
- varinfo_t vi;
-
- timevar_push (TV_TREE_PTA);
-
- init_alias_vars ();
-
- intra_create_variable_infos ();
-
- /* Now walk all statements and build the constraint set. */
- 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 (! virtual_operand_p (gimple_phi_result (phi)))
- find_func_aliases (phi);
- }
-
- for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
- {
- gimple stmt = gsi_stmt (gsi);
-
- find_func_aliases (stmt);
- }
- }
-
- if (dump_file)
- {
- fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
- dump_constraints (dump_file, 0);
- }
-
- /* From the constraints compute the points-to sets. */
- solve_constraints ();
-
- /* Compute the points-to set for ESCAPED used for call-clobber analysis. */
- cfun->gimple_df->escaped = find_what_var_points_to (get_varinfo (escaped_id));
-
- /* Make sure the ESCAPED solution (which is used as placeholder in
- other solutions) does not reference itself. This simplifies
- points-to solution queries. */
- cfun->gimple_df->escaped.escaped = 0;
-
- /* Mark escaped HEAP variables as global. */
- FOR_EACH_VEC_ELT (varmap, i, vi)
- if (vi->is_heap_var
- && !vi->is_global_var)
- DECL_EXTERNAL (vi->decl) = vi->is_global_var
- = pt_solution_includes (&cfun->gimple_df->escaped, vi->decl);
-
- /* Compute the points-to sets for pointer SSA_NAMEs. */
- for (i = 0; i < num_ssa_names; ++i)
- {
- tree ptr = ssa_name (i);
- if (ptr
- && POINTER_TYPE_P (TREE_TYPE (ptr)))
- find_what_p_points_to (ptr);
- }
-
- /* Compute the call-used/clobbered sets. */
- FOR_EACH_BB (bb)
- {
- gimple_stmt_iterator gsi;
-
- for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
- {
- gimple stmt = gsi_stmt (gsi);
- struct pt_solution *pt;
- if (!is_gimple_call (stmt))
- continue;
-
- pt = gimple_call_use_set (stmt);
- if (gimple_call_flags (stmt) & ECF_CONST)
- memset (pt, 0, sizeof (struct pt_solution));
- else if ((vi = lookup_call_use_vi (stmt)) != NULL)
- {
- *pt = find_what_var_points_to (vi);
- /* Escaped (and thus nonlocal) variables are always
- implicitly used by calls. */
- /* ??? ESCAPED can be empty even though NONLOCAL
- always escaped. */
- pt->nonlocal = 1;
- pt->escaped = 1;
- }
- else
- {
- /* If there is nothing special about this call then
- we have made everything that is used also escape. */
- *pt = cfun->gimple_df->escaped;
- pt->nonlocal = 1;
- }
-
- pt = gimple_call_clobber_set (stmt);
- if (gimple_call_flags (stmt) & (ECF_CONST|ECF_PURE|ECF_NOVOPS))
- memset (pt, 0, sizeof (struct pt_solution));
- else if ((vi = lookup_call_clobber_vi (stmt)) != NULL)
- {
- *pt = find_what_var_points_to (vi);
- /* Escaped (and thus nonlocal) variables are always
- implicitly clobbered by calls. */
- /* ??? ESCAPED can be empty even though NONLOCAL
- always escaped. */
- pt->nonlocal = 1;
- pt->escaped = 1;
- }
- else
- {
- /* If there is nothing special about this call then
- we have made everything that is used also escape. */
- *pt = cfun->gimple_df->escaped;
- pt->nonlocal = 1;
- }
- }
- }
-
- timevar_pop (TV_TREE_PTA);
-}
-
-
-/* Delete created points-to sets. */
-
-static 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);
- pointer_map_destroy (call_stmt_vars);
- bitmap_obstack_release (&pta_obstack);
- constraints.release ();
-
- for (i = 0; i < graph->size; i++)
- graph->complex[i].release ();
- free (graph->complex);
-
- free (graph->rep);
- free (graph->succs);
- free (graph->pe);
- free (graph->pe_rep);
- free (graph->indirect_cycles);
- free (graph);
-
- varmap.release ();
- free_alloc_pool (variable_info_pool);
- free_alloc_pool (constraint_pool);
-
- obstack_free (&fake_var_decl_obstack, NULL);
-
- pointer_map_destroy (final_solutions);
- obstack_free (&final_solutions_obstack, NULL);
-}
-
-
-/* Compute points-to information for every SSA_NAME pointer in the
- current function and compute the transitive closure of escaped
- variables to re-initialize the call-clobber states of local variables. */
-
-unsigned int
-compute_may_aliases (void)
-{
- if (cfun->gimple_df->ipa_pta)
- {
- if (dump_file)
- {
- fprintf (dump_file, "\nNot re-computing points-to information "
- "because IPA points-to information is available.\n\n");
-
- /* But still dump what we have remaining it. */
- dump_alias_info (dump_file);
- }
-
- return 0;
- }
-
- /* For each pointer P_i, determine the sets of variables that P_i may
- point-to. Compute the reachability set of escaped and call-used
- variables. */
- compute_points_to_sets ();
-
- /* Debugging dumps. */
- if (dump_file)
- dump_alias_info (dump_file);
-
- /* Deallocate memory used by aliasing data structures and the internal
- points-to solution. */
- delete_points_to_sets ();
-
- gcc_assert (!need_ssa_update_p (cfun));
-
- return 0;
-}
-
-static bool
-gate_tree_pta (void)
-{
- return flag_tree_pta;
-}
-
-/* A dummy pass to cause points-to information to be computed via
- TODO_rebuild_alias. */
-
-struct gimple_opt_pass pass_build_alias =
-{
- {
- GIMPLE_PASS,
- "alias", /* name */
- OPTGROUP_NONE, /* optinfo_flags */
- gate_tree_pta, /* gate */
- NULL, /* execute */
- NULL, /* sub */
- NULL, /* next */
- 0, /* static_pass_number */
- TV_NONE, /* tv_id */
- PROP_cfg | PROP_ssa, /* properties_required */
- 0, /* properties_provided */
- 0, /* properties_destroyed */
- 0, /* todo_flags_start */
- TODO_rebuild_alias /* todo_flags_finish */
- }
-};
-
-/* A dummy pass to cause points-to information to be computed via
- TODO_rebuild_alias. */
-
-struct gimple_opt_pass pass_build_ealias =
-{
- {
- GIMPLE_PASS,
- "ealias", /* name */
- OPTGROUP_NONE, /* optinfo_flags */
- gate_tree_pta, /* gate */
- NULL, /* execute */
- NULL, /* sub */
- NULL, /* next */
- 0, /* static_pass_number */
- TV_NONE, /* tv_id */
- PROP_cfg | PROP_ssa, /* properties_required */
- 0, /* properties_provided */
- 0, /* properties_destroyed */
- 0, /* todo_flags_start */
- TODO_rebuild_alias /* todo_flags_finish */
- }
-};
-
-
-/* Return true if we should execute IPA PTA. */
-static bool
-gate_ipa_pta (void)
-{
- return (optimize
- && flag_ipa_pta
- /* Don't bother doing anything if the program has errors. */
- && !seen_error ());
-}
-
-/* IPA PTA solutions for ESCAPED. */
-struct pt_solution ipa_escaped_pt
- = { true, false, false, false, false, false, NULL };
-
-/* Associate node with varinfo DATA. Worker for
- cgraph_for_node_and_aliases. */
-static bool
-associate_varinfo_to_alias (struct cgraph_node *node, void *data)
-{
- if (node->alias || node->thunk.thunk_p)
- insert_vi_for_tree (node->symbol.decl, (varinfo_t)data);
- return false;
-}
-
-/* Execute the driver for IPA PTA. */
-static unsigned int
-ipa_pta_execute (void)
-{
- struct cgraph_node *node;
- struct varpool_node *var;
- int from;
-
- in_ipa_mode = 1;
-
- init_alias_vars ();
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- dump_symtab (dump_file);
- fprintf (dump_file, "\n");
- }
-
- /* Build the constraints. */
- FOR_EACH_DEFINED_FUNCTION (node)
- {
- varinfo_t vi;
- /* Nodes without a body are not interesting. Especially do not
- visit clones at this point for now - we get duplicate decls
- there for inline clones at least. */
- if (!cgraph_function_with_gimple_body_p (node))
- continue;
-
- gcc_assert (!node->clone_of);
-
- vi = create_function_info_for (node->symbol.decl,
- alias_get_name (node->symbol.decl));
- cgraph_for_node_and_aliases (node, associate_varinfo_to_alias, vi, true);
- }
-
- /* Create constraints for global variables and their initializers. */
- FOR_EACH_VARIABLE (var)
- {
- if (var->alias)
- continue;
-
- get_vi_for_tree (var->symbol.decl);
- }
-
- if (dump_file)
- {
- fprintf (dump_file,
- "Generating constraints for global initializers\n\n");
- dump_constraints (dump_file, 0);
- fprintf (dump_file, "\n");
- }
- from = constraints.length ();
-
- FOR_EACH_DEFINED_FUNCTION (node)
- {
- struct function *func;
- basic_block bb;
-
- /* Nodes without a body are not interesting. */
- if (!cgraph_function_with_gimple_body_p (node))
- continue;
-
- if (dump_file)
- {
- fprintf (dump_file,
- "Generating constraints for %s", cgraph_node_name (node));
- if (DECL_ASSEMBLER_NAME_SET_P (node->symbol.decl))
- fprintf (dump_file, " (%s)",
- IDENTIFIER_POINTER
- (DECL_ASSEMBLER_NAME (node->symbol.decl)));
- fprintf (dump_file, "\n");
- }
-
- func = DECL_STRUCT_FUNCTION (node->symbol.decl);
- push_cfun (func);
-
- /* For externally visible or attribute used annotated functions use
- local constraints for their arguments.
- For local functions we see all callers and thus do not need initial
- constraints for parameters. */
- if (node->symbol.used_from_other_partition
- || node->symbol.externally_visible
- || node->symbol.force_output)
- {
- intra_create_variable_infos ();
-
- /* We also need to make function return values escape. Nothing
- escapes by returning from main though. */
- if (!MAIN_NAME_P (DECL_NAME (node->symbol.decl)))
- {
- varinfo_t fi, rvi;
- fi = lookup_vi_for_tree (node->symbol.decl);
- rvi = first_vi_for_offset (fi, fi_result);
- if (rvi && rvi->offset == fi_result)
- {
- struct constraint_expr includes;
- struct constraint_expr var;
- includes.var = escaped_id;
- includes.offset = 0;
- includes.type = SCALAR;
- var.var = rvi->id;
- var.offset = 0;
- var.type = SCALAR;
- process_constraint (new_constraint (includes, var));
- }
- }
- }
-
- /* Build constriants for the function body. */
- 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 (! virtual_operand_p (gimple_phi_result (phi)))
- find_func_aliases (phi);
- }
-
- for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
- {
- gimple stmt = gsi_stmt (gsi);
-
- find_func_aliases (stmt);
- find_func_clobbers (stmt);
- }
- }
-
- pop_cfun ();
-
- if (dump_file)
- {
- fprintf (dump_file, "\n");
- dump_constraints (dump_file, from);
- fprintf (dump_file, "\n");
- }
- from = constraints.length ();
- }
-
- /* From the constraints compute the points-to sets. */
- solve_constraints ();
-
- /* Compute the global points-to sets for ESCAPED.
- ??? Note that the computed escape set is not correct
- for the whole unit as we fail to consider graph edges to
- externally visible functions. */
- ipa_escaped_pt = find_what_var_points_to (get_varinfo (escaped_id));
-
- /* Make sure the ESCAPED solution (which is used as placeholder in
- other solutions) does not reference itself. This simplifies
- points-to solution queries. */
- ipa_escaped_pt.ipa_escaped = 0;
-
- /* Assign the points-to sets to the SSA names in the unit. */
- FOR_EACH_DEFINED_FUNCTION (node)
- {
- tree ptr;
- struct function *fn;
- unsigned i;
- varinfo_t fi;
- basic_block bb;
- struct pt_solution uses, clobbers;
- struct cgraph_edge *e;
-
- /* Nodes without a body are not interesting. */
- if (!cgraph_function_with_gimple_body_p (node))
- continue;
-
- fn = DECL_STRUCT_FUNCTION (node->symbol.decl);
-
- /* Compute the points-to sets for pointer SSA_NAMEs. */
- FOR_EACH_VEC_ELT (*fn->gimple_df->ssa_names, i, ptr)
- {
- if (ptr
- && POINTER_TYPE_P (TREE_TYPE (ptr)))
- find_what_p_points_to (ptr);
- }
-
- /* Compute the call-use and call-clobber sets for all direct calls. */
- fi = lookup_vi_for_tree (node->symbol.decl);
- gcc_assert (fi->is_fn_info);
- clobbers
- = find_what_var_points_to (first_vi_for_offset (fi, fi_clobbers));
- uses = find_what_var_points_to (first_vi_for_offset (fi, fi_uses));
- for (e = node->callers; e; e = e->next_caller)
- {
- if (!e->call_stmt)
- continue;
-
- *gimple_call_clobber_set (e->call_stmt) = clobbers;
- *gimple_call_use_set (e->call_stmt) = uses;
- }
-
- /* Compute the call-use and call-clobber sets for indirect calls
- and calls to external functions. */
- FOR_EACH_BB_FN (bb, fn)
- {
- gimple_stmt_iterator gsi;
-
- for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
- {
- gimple stmt = gsi_stmt (gsi);
- struct pt_solution *pt;
- varinfo_t vi;
- tree decl;
-
- if (!is_gimple_call (stmt))
- continue;
-
- /* Handle direct calls to external functions. */
- decl = gimple_call_fndecl (stmt);
- if (decl
- && (!(fi = lookup_vi_for_tree (decl))
- || !fi->is_fn_info))
- {
- pt = gimple_call_use_set (stmt);
- if (gimple_call_flags (stmt) & ECF_CONST)
- memset (pt, 0, sizeof (struct pt_solution));
- else if ((vi = lookup_call_use_vi (stmt)) != NULL)
- {
- *pt = find_what_var_points_to (vi);
- /* Escaped (and thus nonlocal) variables are always
- implicitly used by calls. */
- /* ??? ESCAPED can be empty even though NONLOCAL
- always escaped. */
- pt->nonlocal = 1;
- pt->ipa_escaped = 1;
- }
- else
- {
- /* If there is nothing special about this call then
- we have made everything that is used also escape. */
- *pt = ipa_escaped_pt;
- pt->nonlocal = 1;
- }
-
- pt = gimple_call_clobber_set (stmt);
- if (gimple_call_flags (stmt) & (ECF_CONST|ECF_PURE|ECF_NOVOPS))
- memset (pt, 0, sizeof (struct pt_solution));
- else if ((vi = lookup_call_clobber_vi (stmt)) != NULL)
- {
- *pt = find_what_var_points_to (vi);
- /* Escaped (and thus nonlocal) variables are always
- implicitly clobbered by calls. */
- /* ??? ESCAPED can be empty even though NONLOCAL
- always escaped. */
- pt->nonlocal = 1;
- pt->ipa_escaped = 1;
- }
- else
- {
- /* If there is nothing special about this call then
- we have made everything that is used also escape. */
- *pt = ipa_escaped_pt;
- pt->nonlocal = 1;
- }
- }
-
- /* Handle indirect calls. */
- if (!decl
- && (fi = get_fi_for_callee (stmt)))
- {
- /* We need to accumulate all clobbers/uses of all possible
- callees. */
- fi = get_varinfo (find (fi->id));
- /* If we cannot constrain the set of functions we'll end up
- calling we end up using/clobbering everything. */
- if (bitmap_bit_p (fi->solution, anything_id)
- || bitmap_bit_p (fi->solution, nonlocal_id)
- || bitmap_bit_p (fi->solution, escaped_id))
- {
- pt_solution_reset (gimple_call_clobber_set (stmt));
- pt_solution_reset (gimple_call_use_set (stmt));
- }
- else
- {
- bitmap_iterator bi;
- unsigned i;
- struct pt_solution *uses, *clobbers;
-
- uses = gimple_call_use_set (stmt);
- clobbers = gimple_call_clobber_set (stmt);
- memset (uses, 0, sizeof (struct pt_solution));
- memset (clobbers, 0, sizeof (struct pt_solution));
- EXECUTE_IF_SET_IN_BITMAP (fi->solution, 0, i, bi)
- {
- struct pt_solution sol;
-
- vi = get_varinfo (i);
- if (!vi->is_fn_info)
- {
- /* ??? We could be more precise here? */
- uses->nonlocal = 1;
- uses->ipa_escaped = 1;
- clobbers->nonlocal = 1;
- clobbers->ipa_escaped = 1;
- continue;
- }
-
- if (!uses->anything)
- {
- sol = find_what_var_points_to
- (first_vi_for_offset (vi, fi_uses));
- pt_solution_ior_into (uses, &sol);
- }
- if (!clobbers->anything)
- {
- sol = find_what_var_points_to
- (first_vi_for_offset (vi, fi_clobbers));
- pt_solution_ior_into (clobbers, &sol);
- }
- }
- }
- }
- }
- }
-
- fn->gimple_df->ipa_pta = true;
- }
-
- delete_points_to_sets ();
-
- in_ipa_mode = 0;
-
- return 0;
-}
-
-struct simple_ipa_opt_pass pass_ipa_pta =
-{
- {
- SIMPLE_IPA_PASS,
- "pta", /* name */
- OPTGROUP_NONE, /* optinfo_flags */
- 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 */
- }
-};