From af0c51ac87ab2a87caa03fa108f0d164987a2764 Mon Sep 17 00:00:00 2001 From: Ben Cheng Date: Thu, 28 Mar 2013 11:14:20 -0700 Subject: [GCC 4.8] Initial check-in of GCC 4.8.0 Change-Id: I0719d8a6d0f69b367a6ab6f10eb75622dbf12771 --- gcc-4.8/gcc/tree-ssa-structalias.c | 7254 ++++++++++++++++++++++++++++++++++++ 1 file changed, 7254 insertions(+) create mode 100644 gcc-4.8/gcc/tree-ssa-structalias.c (limited to 'gcc-4.8/gcc/tree-ssa-structalias.c') diff --git a/gcc-4.8/gcc/tree-ssa-structalias.c b/gcc-4.8/gcc/tree-ssa-structalias.c new file mode 100644 index 000000000..31a4c49c6 --- /dev/null +++ b/gcc-4.8/gcc/tree-ssa-structalias.c @@ -0,0 +1,7254 @@ +/* Tree based points-to analysis + Copyright (C) 2005-2013 Free Software Foundation, Inc. + Contributed by Daniel Berlin + + 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 + . */ + +#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 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 *, bool, bool); +static void get_constraint_for (tree, vec *); +static void get_constraint_for_rhs (tree, vec *); +static void do_deref (vec *); + +/* 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 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 *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 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 *to, + vec *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 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 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 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 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 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 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 *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 *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 *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 *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 *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 *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 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 *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 *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 lhsc, + vec 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 lhsc = vNULL; + vec 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 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 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 *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 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 rhsc, + tree fndecl) +{ + vec 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 *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 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 *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 lhsc = vNULL; + vec 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 lhsc = vNULL; + vec 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 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 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 lhsc = vNULL; + vec 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 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 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 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 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 lhsc = vNULL; + vec 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 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 *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 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 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 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 */ + } +}; -- cgit v1.2.3