chromium / native_client / nacl-gcc / f80d6b9ee7f94755c697ffb7194fb01dd0c537dd / . / gcc / tree-ssa-structalias.c

/* Tree based points-to analysis | |

Copyright (C) 2005, 2006, 2007, 2008, 2009 Free Software Foundation, Inc. | |

Contributed by Daniel Berlin <dberlin@dberlin.org> | |

This file is part of GCC. | |

GCC is free software; you can redistribute it and/or modify | |

under the terms of the GNU General Public License as published by | |

the Free Software Foundation; either version 3 of the License, or | |

(at your option) any later version. | |

GCC is distributed in the hope that it will be useful, | |

but WITHOUT ANY WARRANTY; without even the implied warranty of | |

MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |

GNU General Public License for more details. | |

You should have received a copy of the GNU General Public License | |

along with GCC; see the file COPYING3. If not see | |

<http://www.gnu.org/licenses/>. */ | |

#include "config.h" | |

#include "system.h" | |

#include "coretypes.h" | |

#include "tm.h" | |

#include "ggc.h" | |

#include "obstack.h" | |

#include "bitmap.h" | |

#include "flags.h" | |

#include "rtl.h" | |

#include "tm_p.h" | |

#include "hard-reg-set.h" | |

#include "basic-block.h" | |

#include "output.h" | |

#include "tree.h" | |

#include "c-common.h" | |

#include "tree-flow.h" | |

#include "tree-inline.h" | |

#include "varray.h" | |

#include "c-tree.h" | |

#include "diagnostic.h" | |

#include "toplev.h" | |

#include "gimple.h" | |

#include "hashtab.h" | |

#include "function.h" | |

#include "cgraph.h" | |

#include "tree-pass.h" | |

#include "timevar.h" | |

#include "alloc-pool.h" | |

#include "splay-tree.h" | |

#include "params.h" | |

#include "tree-ssa-structalias.h" | |

#include "cgraph.h" | |

#include "alias.h" | |

#include "pointer-set.h" | |

/* The idea behind this analyzer is to generate set constraints from the | |

program, then solve the resulting constraints in order to generate the | |

points-to sets. | |

Set constraints are a way of modeling program analysis problems that | |

involve sets. They consist of an inclusion constraint language, | |

describing the variables (each variable is a set) and operations that | |

are involved on the variables, and a set of rules that derive facts | |

from these operations. To solve a system of set constraints, you derive | |

all possible facts under the rules, which gives you the correct sets | |

as a consequence. | |

See "Efficient Field-sensitive pointer analysis for C" by "David | |

J. Pearce and Paul H. J. Kelly and Chris Hankin, at | |

http://citeseer.ist.psu.edu/pearce04efficient.html | |

Also see "Ultra-fast Aliasing Analysis using CLA: A Million Lines | |

of C Code in a Second" by ""Nevin Heintze and Olivier Tardieu" at | |

http://citeseer.ist.psu.edu/heintze01ultrafast.html | |

There are three types of real constraint expressions, DEREF, | |

ADDRESSOF, and SCALAR. Each constraint expression consists | |

of a constraint type, a variable, and an offset. | |

SCALAR is a constraint expression type used to represent x, whether | |

it appears on the LHS or the RHS of a statement. | |

DEREF is a constraint expression type used to represent *x, whether | |

it appears on the LHS or the RHS of a statement. | |

ADDRESSOF is a constraint expression used to represent &x, whether | |

it appears on the LHS or the RHS of a statement. | |

Each pointer variable in the program is assigned an integer id, and | |

each field of a structure variable is assigned an integer id as well. | |

Structure variables are linked to their list of fields through a "next | |

field" in each variable that points to the next field in offset | |

order. | |

Each variable for a structure field has | |

1. "size", that tells the size in bits of that field. | |

2. "fullsize, that tells the size in bits of the entire structure. | |

3. "offset", that tells the offset in bits from the beginning of the | |

structure to this field. | |

Thus, | |

struct f | |

{ | |

int a; | |

int b; | |

} foo; | |

int *bar; | |

looks like | |

foo.a -> id 1, size 32, offset 0, fullsize 64, next foo.b | |

foo.b -> id 2, size 32, offset 32, fullsize 64, next NULL | |

bar -> id 3, size 32, offset 0, fullsize 32, next NULL | |

In order to solve the system of set constraints, the following is | |

done: | |

1. Each constraint variable x has a solution set associated with it, | |

Sol(x). | |

2. Constraints are separated into direct, copy, and complex. | |

Direct constraints are ADDRESSOF constraints that require no extra | |

processing, such as P = &Q | |

Copy constraints are those of the form P = Q. | |

Complex constraints are all the constraints involving dereferences | |

and offsets (including offsetted copies). | |

3. All direct constraints of the form P = &Q are processed, such | |

that Q is added to Sol(P) | |

4. All complex constraints for a given constraint variable are stored in a | |

linked list attached to that variable's node. | |

5. A directed graph is built out of the copy constraints. Each | |

constraint variable is a node in the graph, and an edge from | |

Q to P is added for each copy constraint of the form P = Q | |

6. The graph is then walked, and solution sets are | |

propagated along the copy edges, such that an edge from Q to P | |

causes Sol(P) <- Sol(P) union Sol(Q). | |

7. As we visit each node, all complex constraints associated with | |

that node are processed by adding appropriate copy edges to the graph, or the | |

appropriate variables to the solution set. | |

8. The process of walking the graph is iterated until no solution | |

sets change. | |

Prior to walking the graph in steps 6 and 7, We perform static | |

cycle elimination on the constraint graph, as well | |

as off-line variable substitution. | |

TODO: Adding offsets to pointer-to-structures can be handled (IE not punted | |

on and turned into anything), but isn't. You can just see what offset | |

inside the pointed-to struct it's going to access. | |

TODO: Constant bounded arrays can be handled as if they were structs of the | |

same number of elements. | |

TODO: Modeling heap and incoming pointers becomes much better if we | |

add fields to them as we discover them, which we could do. | |

TODO: We could handle unions, but to be honest, it's probably not | |

worth the pain or slowdown. */ | |

static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map))) | |

htab_t heapvar_for_stmt; | |

static bool use_field_sensitive = true; | |

static int in_ipa_mode = 0; | |

/* Used for predecessor bitmaps. */ | |

static bitmap_obstack predbitmap_obstack; | |

/* Used for points-to sets. */ | |

static bitmap_obstack pta_obstack; | |

/* Used for oldsolution members of variables. */ | |

static bitmap_obstack oldpta_obstack; | |

/* Used for per-solver-iteration bitmaps. */ | |

static bitmap_obstack iteration_obstack; | |

static unsigned int create_variable_info_for (tree, const char *); | |

typedef struct constraint_graph *constraint_graph_t; | |

static void unify_nodes (constraint_graph_t, unsigned int, unsigned int, bool); | |

DEF_VEC_P(constraint_t); | |

DEF_VEC_ALLOC_P(constraint_t,heap); | |

#define EXECUTE_IF_IN_NONNULL_BITMAP(a, b, c, d) \ | |

if (a) \ | |

EXECUTE_IF_SET_IN_BITMAP (a, b, c, d) | |

static struct constraint_stats | |

{ | |

unsigned int total_vars; | |

unsigned int nonpointer_vars; | |

unsigned int unified_vars_static; | |

unsigned int unified_vars_dynamic; | |

unsigned int iterations; | |

unsigned int num_edges; | |

unsigned int num_implicit_edges; | |

unsigned int points_to_sets_created; | |

} stats; | |

struct variable_info | |

{ | |

/* ID of this variable */ | |

unsigned int id; | |

/* True if this is a variable created by the constraint analysis, such as | |

heap variables and constraints we had to break up. */ | |

unsigned int is_artificial_var:1; | |

/* True if this is a special variable whose solution set should not be | |

changed. */ | |

unsigned int is_special_var:1; | |

/* True for variables whose size is not known or variable. */ | |

unsigned int is_unknown_size_var:1; | |

/* True for (sub-)fields that represent a whole variable. */ | |

unsigned int is_full_var : 1; | |

/* True if this is a heap variable. */ | |

unsigned int is_heap_var:1; | |

/* True if we may not use TBAA to prune references to this | |

variable. This is used for C++ placement new. */ | |

unsigned int no_tbaa_pruning : 1; | |

/* True if this field may contain pointers. */ | |

unsigned int may_have_pointers : 1; | |

/* Variable id this was collapsed to due to type unsafety. Zero if | |

this variable was not collapsed. This should be unused completely | |

after build_succ_graph, or something is broken. */ | |

unsigned int collapsed_to; | |

/* A link to the variable for the next field in this structure. */ | |

struct variable_info *next; | |

/* Offset of this variable, in bits, from the base variable */ | |

unsigned HOST_WIDE_INT offset; | |

/* Size of the variable, in bits. */ | |

unsigned HOST_WIDE_INT size; | |

/* Full size of the base variable, in bits. */ | |

unsigned HOST_WIDE_INT fullsize; | |

/* Name of this variable */ | |

const char *name; | |

/* Tree that this variable is associated with. */ | |

tree decl; | |

/* Points-to set for this variable. */ | |

bitmap solution; | |

/* Old points-to set for this variable. */ | |

bitmap oldsolution; | |

}; | |

typedef struct variable_info *varinfo_t; | |

static varinfo_t first_vi_for_offset (varinfo_t, unsigned HOST_WIDE_INT); | |

static varinfo_t lookup_vi_for_tree (tree); | |

/* Pool of variable info structures. */ | |

static alloc_pool variable_info_pool; | |

DEF_VEC_P(varinfo_t); | |

DEF_VEC_ALLOC_P(varinfo_t, heap); | |

/* Table of variable info structures for constraint variables. | |

Indexed directly by variable info id. */ | |

static VEC(varinfo_t,heap) *varmap; | |

/* Return the varmap element N */ | |

static inline varinfo_t | |

get_varinfo (unsigned int n) | |

{ | |

return VEC_index (varinfo_t, varmap, n); | |

} | |

/* Return the varmap element N, following the collapsed_to link. */ | |

static inline varinfo_t | |

get_varinfo_fc (unsigned int n) | |

{ | |

varinfo_t v = VEC_index (varinfo_t, varmap, n); | |

if (v->collapsed_to != 0) | |

return get_varinfo (v->collapsed_to); | |

return v; | |

} | |

/* Static IDs for the special variables. */ | |

enum { nothing_id = 0, anything_id = 1, readonly_id = 2, | |

escaped_id = 3, nonlocal_id = 4, callused_id = 5, | |

storedanything_id = 6, integer_id = 7 }; | |

/* Variable that represents the unknown pointer. */ | |

static varinfo_t var_anything; | |

static tree anything_tree; | |

/* Variable that represents the NULL pointer. */ | |

static varinfo_t var_nothing; | |

static tree nothing_tree; | |

/* Variable that represents read only memory. */ | |

static varinfo_t var_readonly; | |

static tree readonly_tree; | |

/* Variable that represents escaped memory. */ | |

static varinfo_t var_escaped; | |

static tree escaped_tree; | |

/* Variable that represents nonlocal memory. */ | |

static varinfo_t var_nonlocal; | |

static tree nonlocal_tree; | |

/* Variable that represents call-used memory. */ | |

static varinfo_t var_callused; | |

static tree callused_tree; | |

/* Variable that represents variables that are stored to anything. */ | |

static varinfo_t var_storedanything; | |

static tree storedanything_tree; | |

/* Variable that represents integers. This is used for when people do things | |

like &0->a.b. */ | |

static varinfo_t var_integer; | |

static tree integer_tree; | |

/* Lookup a heap var for FROM, and return it if we find one. */ | |

static tree | |

heapvar_lookup (tree from) | |

{ | |

struct tree_map *h, in; | |

in.base.from = from; | |

h = (struct tree_map *) htab_find_with_hash (heapvar_for_stmt, &in, | |

htab_hash_pointer (from)); | |

if (h) | |

return h->to; | |

return NULL_TREE; | |

} | |

/* Insert a mapping FROM->TO in the heap var for statement | |

hashtable. */ | |

static void | |

heapvar_insert (tree from, tree to) | |

{ | |

struct tree_map *h; | |

void **loc; | |

h = GGC_NEW (struct tree_map); | |

h->hash = htab_hash_pointer (from); | |

h->base.from = from; | |

h->to = to; | |

loc = htab_find_slot_with_hash (heapvar_for_stmt, h, h->hash, INSERT); | |

*(struct tree_map **) loc = h; | |

} | |

/* Return a new variable info structure consisting for a variable | |

named NAME, and using constraint graph node NODE. */ | |

static varinfo_t | |

new_var_info (tree t, unsigned int id, const char *name) | |

{ | |

varinfo_t ret = (varinfo_t) pool_alloc (variable_info_pool); | |

tree var; | |

ret->id = id; | |

ret->name = name; | |

ret->decl = t; | |

ret->is_artificial_var = false; | |

ret->is_heap_var = false; | |

ret->is_special_var = false; | |

ret->is_unknown_size_var = false; | |

ret->is_full_var = false; | |

ret->may_have_pointers = true; | |

var = t; | |

if (TREE_CODE (var) == SSA_NAME) | |

var = SSA_NAME_VAR (var); | |

ret->no_tbaa_pruning = (DECL_P (var) | |

&& POINTER_TYPE_P (TREE_TYPE (var)) | |

&& DECL_NO_TBAA_P (var)); | |

ret->solution = BITMAP_ALLOC (&pta_obstack); | |

ret->oldsolution = BITMAP_ALLOC (&oldpta_obstack); | |

ret->next = NULL; | |

ret->collapsed_to = 0; | |

return ret; | |

} | |

typedef enum {SCALAR, DEREF, ADDRESSOF} constraint_expr_type; | |

/* An expression that appears in a constraint. */ | |

struct constraint_expr | |

{ | |

/* Constraint type. */ | |

constraint_expr_type type; | |

/* Variable we are referring to in the constraint. */ | |

unsigned int var; | |

/* Offset, in bits, of this constraint from the beginning of | |

variables it ends up referring to. | |

IOW, in a deref constraint, we would deref, get the result set, | |

then add OFFSET to each member. */ | |

unsigned HOST_WIDE_INT offset; | |

}; | |

typedef struct constraint_expr ce_s; | |

DEF_VEC_O(ce_s); | |

DEF_VEC_ALLOC_O(ce_s, heap); | |

static void get_constraint_for_1 (tree, VEC(ce_s, heap) **, bool); | |

static void get_constraint_for (tree, VEC(ce_s, heap) **); | |

static void do_deref (VEC (ce_s, heap) **); | |

/* Our set constraints are made up of two constraint expressions, one | |

LHS, and one RHS. | |

As described in the introduction, our set constraints each represent an | |

operation between set valued variables. | |

*/ | |

struct constraint | |

{ | |

struct constraint_expr lhs; | |

struct constraint_expr rhs; | |

}; | |

/* List of constraints that we use to build the constraint graph from. */ | |

static VEC(constraint_t,heap) *constraints; | |

static alloc_pool constraint_pool; | |

DEF_VEC_I(int); | |

DEF_VEC_ALLOC_I(int, heap); | |

/* The constraint graph is represented as an array of bitmaps | |

containing successor nodes. */ | |

struct constraint_graph | |

{ | |

/* Size of this graph, which may be different than the number of | |

nodes in the variable map. */ | |

unsigned int size; | |

/* Explicit successors of each node. */ | |

bitmap *succs; | |

/* Implicit predecessors of each node (Used for variable | |

substitution). */ | |

bitmap *implicit_preds; | |

/* Explicit predecessors of each node (Used for variable substitution). */ | |

bitmap *preds; | |

/* Indirect cycle representatives, or -1 if the node has no indirect | |

cycles. */ | |

int *indirect_cycles; | |

/* Representative node for a node. rep[a] == a unless the node has | |

been unified. */ | |

unsigned int *rep; | |

/* Equivalence class representative for a label. This is used for | |

variable substitution. */ | |

int *eq_rep; | |

/* Pointer equivalence label for a node. All nodes with the same | |

pointer equivalence label can be unified together at some point | |

(either during constraint optimization or after the constraint | |

graph is built). */ | |

unsigned int *pe; | |

/* Pointer equivalence representative for a label. This is used to | |

handle nodes that are pointer equivalent but not location | |

equivalent. We can unite these once the addressof constraints | |

are transformed into initial points-to sets. */ | |

int *pe_rep; | |

/* Pointer equivalence label for each node, used during variable | |

substitution. */ | |

unsigned int *pointer_label; | |

/* Location equivalence label for each node, used during location | |

equivalence finding. */ | |

unsigned int *loc_label; | |

/* Pointed-by set for each node, used during location equivalence | |

finding. This is pointed-by rather than pointed-to, because it | |

is constructed using the predecessor graph. */ | |

bitmap *pointed_by; | |

/* Points to sets for pointer equivalence. This is *not* the actual | |

points-to sets for nodes. */ | |

bitmap *points_to; | |

/* Bitmap of nodes where the bit is set if the node is a direct | |

node. Used for variable substitution. */ | |

sbitmap direct_nodes; | |

/* Bitmap of nodes where the bit is set if the node is address | |

taken. Used for variable substitution. */ | |

bitmap address_taken; | |

/* Vector of complex constraints for each graph node. Complex | |

constraints are those involving dereferences or offsets that are | |

not 0. */ | |

VEC(constraint_t,heap) **complex; | |

}; | |

static constraint_graph_t graph; | |

/* During variable substitution and the offline version of indirect | |

cycle finding, we create nodes to represent dereferences and | |

address taken constraints. These represent where these start and | |

end. */ | |

#define FIRST_REF_NODE (VEC_length (varinfo_t, varmap)) | |

#define LAST_REF_NODE (FIRST_REF_NODE + (FIRST_REF_NODE - 1)) | |

/* Return the representative node for NODE, if NODE has been unioned | |

with another NODE. | |

This function performs path compression along the way to finding | |

the representative. */ | |

static unsigned int | |

find (unsigned int node) | |

{ | |

gcc_assert (node < graph->size); | |

if (graph->rep[node] != node) | |

return graph->rep[node] = find (graph->rep[node]); | |

return node; | |

} | |

/* Union the TO and FROM nodes to the TO nodes. | |

Note that at some point in the future, we may want to do | |

union-by-rank, in which case we are going to have to return the | |

node we unified to. */ | |

static bool | |

unite (unsigned int to, unsigned int from) | |

{ | |

gcc_assert (to < graph->size && from < graph->size); | |

if (to != from && graph->rep[from] != to) | |

{ | |

graph->rep[from] = to; | |

return true; | |

} | |

return false; | |

} | |

/* Create a new constraint consisting of LHS and RHS expressions. */ | |

static constraint_t | |

new_constraint (const struct constraint_expr lhs, | |

const struct constraint_expr rhs) | |

{ | |

constraint_t ret = (constraint_t) pool_alloc (constraint_pool); | |

ret->lhs = lhs; | |

ret->rhs = rhs; | |

return ret; | |

} | |

/* Print out constraint C to FILE. */ | |

void | |

dump_constraint (FILE *file, constraint_t c) | |

{ | |

if (c->lhs.type == ADDRESSOF) | |

fprintf (file, "&"); | |

else if (c->lhs.type == DEREF) | |

fprintf (file, "*"); | |

fprintf (file, "%s", get_varinfo_fc (c->lhs.var)->name); | |

if (c->lhs.offset != 0) | |

fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->lhs.offset); | |

fprintf (file, " = "); | |

if (c->rhs.type == ADDRESSOF) | |

fprintf (file, "&"); | |

else if (c->rhs.type == DEREF) | |

fprintf (file, "*"); | |

fprintf (file, "%s", get_varinfo_fc (c->rhs.var)->name); | |

if (c->rhs.offset != 0) | |

fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->rhs.offset); | |

fprintf (file, "\n"); | |

} | |

/* Print out constraint C to stderr. */ | |

void | |

debug_constraint (constraint_t c) | |

{ | |

dump_constraint (stderr, c); | |

} | |

/* Print out all constraints to FILE */ | |

void | |

dump_constraints (FILE *file) | |

{ | |

int i; | |

constraint_t c; | |

for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++) | |

dump_constraint (file, c); | |

} | |

/* Print out all constraints to stderr. */ | |

void | |

debug_constraints (void) | |

{ | |

dump_constraints (stderr); | |

} | |

/* Print out to FILE the edge in the constraint graph that is created by | |

constraint c. The edge may have a label, depending on the type of | |

constraint that it represents. If complex1, e.g: a = *b, then the label | |

is "=*", if complex2, e.g: *a = b, then the label is "*=", if | |

complex with an offset, e.g: a = b + 8, then the label is "+". | |

Otherwise the edge has no label. */ | |

void | |

dump_constraint_edge (FILE *file, constraint_t c) | |

{ | |

if (c->rhs.type != ADDRESSOF) | |

{ | |

const char *src = get_varinfo_fc (c->rhs.var)->name; | |

const char *dst = get_varinfo_fc (c->lhs.var)->name; | |

fprintf (file, " \"%s\" -> \"%s\" ", src, dst); | |

/* Due to preprocessing of constraints, instructions like *a = *b are | |

illegal; thus, we do not have to handle such cases. */ | |

if (c->lhs.type == DEREF) | |

fprintf (file, " [ label=\"*=\" ] ;\n"); | |

else if (c->rhs.type == DEREF) | |

fprintf (file, " [ label=\"=*\" ] ;\n"); | |

else | |

{ | |

/* We must check the case where the constraint is an offset. | |

In this case, it is treated as a complex constraint. */ | |

if (c->rhs.offset != c->lhs.offset) | |

fprintf (file, " [ label=\"+\" ] ;\n"); | |

else | |

fprintf (file, " ;\n"); | |

} | |

} | |

} | |

/* Print the constraint graph in dot format. */ | |

void | |

dump_constraint_graph (FILE *file) | |

{ | |

unsigned int i=0, size; | |

constraint_t c; | |

/* Only print the graph if it has already been initialized: */ | |

if (!graph) | |

return; | |

/* Print the constraints used to produce the constraint graph. The | |

constraints will be printed as comments in the dot file: */ | |

fprintf (file, "\n\n/* Constraints used in the constraint graph:\n"); | |

dump_constraints (file); | |

fprintf (file, "*/\n"); | |

/* Prints the header of the dot file: */ | |

fprintf (file, "\n\n// The constraint graph in dot format:\n"); | |

fprintf (file, "strict digraph {\n"); | |

fprintf (file, " node [\n shape = box\n ]\n"); | |

fprintf (file, " edge [\n fontsize = \"12\"\n ]\n"); | |

fprintf (file, "\n // List of nodes in the constraint graph:\n"); | |

/* The next lines print the nodes in the graph. In order to get the | |

number of nodes in the graph, we must choose the minimum between the | |

vector VEC (varinfo_t, varmap) and graph->size. If the graph has not | |

yet been initialized, then graph->size == 0, otherwise we must only | |

read nodes that have an entry in VEC (varinfo_t, varmap). */ | |

size = VEC_length (varinfo_t, varmap); | |

size = size < graph->size ? size : graph->size; | |

for (i = 0; i < size; i++) | |

{ | |

const char *name = get_varinfo_fc (graph->rep[i])->name; | |

fprintf (file, " \"%s\" ;\n", name); | |

} | |

/* Go over the list of constraints printing the edges in the constraint | |

graph. */ | |

fprintf (file, "\n // The constraint edges:\n"); | |

for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++) | |

if (c) | |

dump_constraint_edge (file, c); | |

/* Prints the tail of the dot file. By now, only the closing bracket. */ | |

fprintf (file, "}\n\n\n"); | |

} | |

/* Print out the constraint graph to stderr. */ | |

void | |

debug_constraint_graph (void) | |

{ | |

dump_constraint_graph (stderr); | |

} | |

/* SOLVER FUNCTIONS | |

The solver is a simple worklist solver, that works on the following | |

algorithm: | |

sbitmap changed_nodes = all zeroes; | |

changed_count = 0; | |

For each node that is not already collapsed: | |

changed_count++; | |

set bit in changed nodes | |

while (changed_count > 0) | |

{ | |

compute topological ordering for constraint graph | |

find and collapse cycles in the constraint graph (updating | |

changed if necessary) | |

for each node (n) in the graph in topological order: | |

changed_count--; | |

Process each complex constraint associated with the node, | |

updating changed if necessary. | |

For each outgoing edge from n, propagate the solution from n to | |

the destination of the edge, updating changed as necessary. | |

} */ | |

/* Return true if two constraint expressions A and B are equal. */ | |

static bool | |

constraint_expr_equal (struct constraint_expr a, struct constraint_expr b) | |

{ | |

return a.type == b.type && a.var == b.var && a.offset == b.offset; | |

} | |

/* Return true if constraint expression A is less than constraint expression | |

B. This is just arbitrary, but consistent, in order to give them an | |

ordering. */ | |

static bool | |

constraint_expr_less (struct constraint_expr a, struct constraint_expr b) | |

{ | |

if (a.type == b.type) | |

{ | |

if (a.var == b.var) | |

return a.offset < b.offset; | |

else | |

return a.var < b.var; | |

} | |

else | |

return a.type < b.type; | |

} | |

/* Return true if constraint A is less than constraint B. This is just | |

arbitrary, but consistent, in order to give them an ordering. */ | |

static bool | |

constraint_less (const constraint_t a, const constraint_t b) | |

{ | |

if (constraint_expr_less (a->lhs, b->lhs)) | |

return true; | |

else if (constraint_expr_less (b->lhs, a->lhs)) | |

return false; | |

else | |

return constraint_expr_less (a->rhs, b->rhs); | |

} | |

/* Return true if two constraints A and B are equal. */ | |

static bool | |

constraint_equal (struct constraint a, struct constraint b) | |

{ | |

return constraint_expr_equal (a.lhs, b.lhs) | |

&& constraint_expr_equal (a.rhs, b.rhs); | |

} | |

/* Find a constraint LOOKFOR in the sorted constraint vector VEC */ | |

static constraint_t | |

constraint_vec_find (VEC(constraint_t,heap) *vec, | |

struct constraint lookfor) | |

{ | |

unsigned int place; | |

constraint_t found; | |

if (vec == NULL) | |

return NULL; | |

place = VEC_lower_bound (constraint_t, vec, &lookfor, constraint_less); | |

if (place >= VEC_length (constraint_t, vec)) | |

return NULL; | |

found = VEC_index (constraint_t, vec, place); | |

if (!constraint_equal (*found, lookfor)) | |

return NULL; | |

return found; | |

} | |

/* Union two constraint vectors, TO and FROM. Put the result in TO. */ | |

static void | |

constraint_set_union (VEC(constraint_t,heap) **to, | |

VEC(constraint_t,heap) **from) | |

{ | |

int i; | |

constraint_t c; | |

for (i = 0; VEC_iterate (constraint_t, *from, i, c); i++) | |

{ | |

if (constraint_vec_find (*to, *c) == NULL) | |

{ | |

unsigned int place = VEC_lower_bound (constraint_t, *to, c, | |

constraint_less); | |

VEC_safe_insert (constraint_t, heap, *to, place, c); | |

} | |

} | |

} | |

/* Take a solution set SET, add OFFSET to each member of the set, and | |

overwrite SET with the result when done. */ | |

static void | |

solution_set_add (bitmap set, unsigned HOST_WIDE_INT offset) | |

{ | |

bitmap result = BITMAP_ALLOC (&iteration_obstack); | |

unsigned int i; | |

bitmap_iterator bi; | |

EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi) | |

{ | |

varinfo_t vi = get_varinfo (i); | |

/* If this is a variable with just one field just set its bit | |

in the result. */ | |

if (vi->is_artificial_var | |

|| vi->is_unknown_size_var | |

|| vi->is_full_var) | |

bitmap_set_bit (result, i); | |

else | |

{ | |

unsigned HOST_WIDE_INT fieldoffset = vi->offset + offset; | |

varinfo_t v = first_vi_for_offset (vi, fieldoffset); | |

/* If the result is outside of the variable use the last field. */ | |

if (!v) | |

{ | |

v = vi; | |

while (v->next != NULL) | |

v = v->next; | |

} | |

bitmap_set_bit (result, v->id); | |

/* If the result is not exactly at fieldoffset include the next | |

field as well. See get_constraint_for_ptr_offset for more | |

rationale. */ | |

if (v->offset != fieldoffset | |

&& v->next != NULL) | |

bitmap_set_bit (result, v->next->id); | |

} | |

} | |

bitmap_copy (set, result); | |

BITMAP_FREE (result); | |

} | |

/* Union solution sets TO and FROM, and add INC to each member of FROM in the | |

process. */ | |

static bool | |

set_union_with_increment (bitmap to, bitmap from, unsigned HOST_WIDE_INT inc) | |

{ | |

if (inc == 0) | |

return bitmap_ior_into (to, from); | |

else | |

{ | |

bitmap tmp; | |

bool res; | |

tmp = BITMAP_ALLOC (&iteration_obstack); | |

bitmap_copy (tmp, from); | |

solution_set_add (tmp, inc); | |

res = bitmap_ior_into (to, tmp); | |

BITMAP_FREE (tmp); | |

return res; | |

} | |

} | |

/* Insert constraint C into the list of complex constraints for graph | |

node VAR. */ | |

static void | |

insert_into_complex (constraint_graph_t graph, | |

unsigned int var, constraint_t c) | |

{ | |

VEC (constraint_t, heap) *complex = graph->complex[var]; | |

unsigned int place = VEC_lower_bound (constraint_t, complex, c, | |

constraint_less); | |

/* Only insert constraints that do not already exist. */ | |

if (place >= VEC_length (constraint_t, complex) | |

|| !constraint_equal (*c, *VEC_index (constraint_t, complex, place))) | |

VEC_safe_insert (constraint_t, heap, graph->complex[var], place, c); | |

} | |

/* Condense two variable nodes into a single variable node, by moving | |

all associated info from SRC to TO. */ | |

static void | |

merge_node_constraints (constraint_graph_t graph, unsigned int to, | |

unsigned int from) | |

{ | |

unsigned int i; | |

constraint_t c; | |

gcc_assert (find (from) == to); | |

/* Move all complex constraints from src node into to node */ | |

for (i = 0; VEC_iterate (constraint_t, graph->complex[from], i, c); i++) | |

{ | |

/* In complex constraints for node src, we may have either | |

a = *src, and *src = a, or an offseted constraint which are | |

always added to the rhs node's constraints. */ | |

if (c->rhs.type == DEREF) | |

c->rhs.var = to; | |

else if (c->lhs.type == DEREF) | |

c->lhs.var = to; | |

else | |

c->rhs.var = to; | |

} | |

constraint_set_union (&graph->complex[to], &graph->complex[from]); | |

VEC_free (constraint_t, heap, graph->complex[from]); | |

graph->complex[from] = NULL; | |

} | |

/* Remove edges involving NODE from GRAPH. */ | |

static void | |

clear_edges_for_node (constraint_graph_t graph, unsigned int node) | |

{ | |

if (graph->succs[node]) | |

BITMAP_FREE (graph->succs[node]); | |

} | |

/* Merge GRAPH nodes FROM and TO into node TO. */ | |

static void | |

merge_graph_nodes (constraint_graph_t graph, unsigned int to, | |

unsigned int from) | |

{ | |

if (graph->indirect_cycles[from] != -1) | |

{ | |

/* If we have indirect cycles with the from node, and we have | |

none on the to node, the to node has indirect cycles from the | |

from node now that they are unified. | |

If indirect cycles exist on both, unify the nodes that they | |

are in a cycle with, since we know they are in a cycle with | |

each other. */ | |

if (graph->indirect_cycles[to] == -1) | |

graph->indirect_cycles[to] = graph->indirect_cycles[from]; | |

} | |

/* Merge all the successor edges. */ | |

if (graph->succs[from]) | |

{ | |

if (!graph->succs[to]) | |

graph->succs[to] = BITMAP_ALLOC (&pta_obstack); | |

bitmap_ior_into (graph->succs[to], | |

graph->succs[from]); | |

} | |

clear_edges_for_node (graph, from); | |

} | |

/* Add an indirect graph edge to GRAPH, going from TO to FROM if | |

it doesn't exist in the graph already. */ | |

static void | |

add_implicit_graph_edge (constraint_graph_t graph, unsigned int to, | |

unsigned int from) | |

{ | |

if (to == from) | |

return; | |

if (!graph->implicit_preds[to]) | |

graph->implicit_preds[to] = BITMAP_ALLOC (&predbitmap_obstack); | |

if (bitmap_set_bit (graph->implicit_preds[to], from)) | |

stats.num_implicit_edges++; | |

} | |

/* Add a predecessor graph edge to GRAPH, going from TO to FROM if | |

it doesn't exist in the graph already. | |

Return false if the edge already existed, true otherwise. */ | |

static void | |

add_pred_graph_edge (constraint_graph_t graph, unsigned int to, | |

unsigned int from) | |

{ | |

if (!graph->preds[to]) | |

graph->preds[to] = BITMAP_ALLOC (&predbitmap_obstack); | |

bitmap_set_bit (graph->preds[to], from); | |

} | |

/* Add a graph edge to GRAPH, going from FROM to TO if | |

it doesn't exist in the graph already. | |

Return false if the edge already existed, true otherwise. */ | |

static bool | |

add_graph_edge (constraint_graph_t graph, unsigned int to, | |

unsigned int from) | |

{ | |

if (to == from) | |

{ | |

return false; | |

} | |

else | |

{ | |

bool r = false; | |

if (!graph->succs[from]) | |

graph->succs[from] = BITMAP_ALLOC (&pta_obstack); | |

if (bitmap_set_bit (graph->succs[from], to)) | |

{ | |

r = true; | |

if (to < FIRST_REF_NODE && from < FIRST_REF_NODE) | |

stats.num_edges++; | |

} | |

return r; | |

} | |

} | |

/* Return true if {DEST.SRC} is an existing graph edge in GRAPH. */ | |

static bool | |

valid_graph_edge (constraint_graph_t graph, unsigned int src, | |

unsigned int dest) | |

{ | |

return (graph->succs[dest] | |

&& bitmap_bit_p (graph->succs[dest], src)); | |

} | |

/* Initialize the constraint graph structure to contain SIZE nodes. */ | |

static void | |

init_graph (unsigned int size) | |

{ | |

unsigned int j; | |

graph = XCNEW (struct constraint_graph); | |

graph->size = size; | |

graph->succs = XCNEWVEC (bitmap, graph->size); | |

graph->indirect_cycles = XNEWVEC (int, graph->size); | |

graph->rep = XNEWVEC (unsigned int, graph->size); | |

graph->complex = XCNEWVEC (VEC(constraint_t, heap) *, size); | |

graph->pe = XCNEWVEC (unsigned int, graph->size); | |

graph->pe_rep = XNEWVEC (int, graph->size); | |

for (j = 0; j < graph->size; j++) | |

{ | |

graph->rep[j] = j; | |

graph->pe_rep[j] = -1; | |

graph->indirect_cycles[j] = -1; | |

} | |

} | |

/* Build the constraint graph, adding only predecessor edges right now. */ | |

static void | |

build_pred_graph (void) | |

{ | |

int i; | |

constraint_t c; | |

unsigned int j; | |

graph->implicit_preds = XCNEWVEC (bitmap, graph->size); | |

graph->preds = XCNEWVEC (bitmap, graph->size); | |

graph->pointer_label = XCNEWVEC (unsigned int, graph->size); | |

graph->loc_label = XCNEWVEC (unsigned int, graph->size); | |

graph->pointed_by = XCNEWVEC (bitmap, graph->size); | |

graph->points_to = XCNEWVEC (bitmap, graph->size); | |

graph->eq_rep = XNEWVEC (int, graph->size); | |

graph->direct_nodes = sbitmap_alloc (graph->size); | |

graph->address_taken = BITMAP_ALLOC (&predbitmap_obstack); | |

sbitmap_zero (graph->direct_nodes); | |

for (j = 0; j < FIRST_REF_NODE; j++) | |

{ | |

if (!get_varinfo (j)->is_special_var) | |

SET_BIT (graph->direct_nodes, j); | |

} | |

for (j = 0; j < graph->size; j++) | |

graph->eq_rep[j] = -1; | |

for (j = 0; j < VEC_length (varinfo_t, varmap); j++) | |

graph->indirect_cycles[j] = -1; | |

for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++) | |

{ | |

struct constraint_expr lhs = c->lhs; | |

struct constraint_expr rhs = c->rhs; | |

unsigned int lhsvar = get_varinfo_fc (lhs.var)->id; | |

unsigned int rhsvar = get_varinfo_fc (rhs.var)->id; | |

if (lhs.type == DEREF) | |

{ | |

/* *x = y. */ | |

if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR) | |

add_pred_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar); | |

} | |

else if (rhs.type == DEREF) | |

{ | |

/* x = *y */ | |

if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR) | |

add_pred_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar); | |

else | |

RESET_BIT (graph->direct_nodes, lhsvar); | |

} | |

else if (rhs.type == ADDRESSOF) | |

{ | |

varinfo_t v; | |

/* x = &y */ | |

if (graph->points_to[lhsvar] == NULL) | |

graph->points_to[lhsvar] = BITMAP_ALLOC (&predbitmap_obstack); | |

bitmap_set_bit (graph->points_to[lhsvar], rhsvar); | |

if (graph->pointed_by[rhsvar] == NULL) | |

graph->pointed_by[rhsvar] = BITMAP_ALLOC (&predbitmap_obstack); | |

bitmap_set_bit (graph->pointed_by[rhsvar], lhsvar); | |

/* Implicitly, *x = y */ | |

add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar); | |

/* All related variables are no longer direct nodes. */ | |

RESET_BIT (graph->direct_nodes, rhsvar); | |

v = get_varinfo (rhsvar); | |

if (!v->is_full_var) | |

{ | |

v = lookup_vi_for_tree (v->decl); | |

do | |

{ | |

RESET_BIT (graph->direct_nodes, v->id); | |

v = v->next; | |

} | |

while (v != NULL); | |

} | |

bitmap_set_bit (graph->address_taken, rhsvar); | |

} | |

else if (lhsvar > anything_id | |

&& lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0) | |

{ | |

/* x = y */ | |

add_pred_graph_edge (graph, lhsvar, rhsvar); | |

/* Implicitly, *x = *y */ | |

add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar, | |

FIRST_REF_NODE + rhsvar); | |

} | |

else if (lhs.offset != 0 || rhs.offset != 0) | |

{ | |

if (rhs.offset != 0) | |

RESET_BIT (graph->direct_nodes, lhs.var); | |

else if (lhs.offset != 0) | |

RESET_BIT (graph->direct_nodes, rhs.var); | |

} | |

} | |

} | |

/* Build the constraint graph, adding successor edges. */ | |

static void | |

build_succ_graph (void) | |

{ | |

unsigned i, t; | |

constraint_t c; | |

for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++) | |

{ | |

struct constraint_expr lhs; | |

struct constraint_expr rhs; | |

unsigned int lhsvar; | |

unsigned int rhsvar; | |

if (!c) | |

continue; | |

lhs = c->lhs; | |

rhs = c->rhs; | |

lhsvar = find (get_varinfo_fc (lhs.var)->id); | |

rhsvar = find (get_varinfo_fc (rhs.var)->id); | |

if (lhs.type == DEREF) | |

{ | |

if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR) | |

add_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar); | |

} | |

else if (rhs.type == DEREF) | |

{ | |

if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR) | |

add_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar); | |

} | |

else if (rhs.type == ADDRESSOF) | |

{ | |

/* x = &y */ | |

gcc_assert (find (get_varinfo_fc (rhs.var)->id) | |

== get_varinfo_fc (rhs.var)->id); | |

bitmap_set_bit (get_varinfo (lhsvar)->solution, rhsvar); | |

} | |

else if (lhsvar > anything_id | |

&& lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0) | |

{ | |

add_graph_edge (graph, lhsvar, rhsvar); | |

} | |

} | |

/* Add edges from STOREDANYTHING to all non-direct nodes. */ | |

t = find (storedanything_id); | |

for (i = integer_id + 1; i < FIRST_REF_NODE; ++i) | |

{ | |

if (!TEST_BIT (graph->direct_nodes, i)) | |

add_graph_edge (graph, find (i), t); | |

} | |

} | |

/* Changed variables on the last iteration. */ | |

static unsigned int changed_count; | |

static sbitmap changed; | |

DEF_VEC_I(unsigned); | |

DEF_VEC_ALLOC_I(unsigned,heap); | |

/* Strongly Connected Component visitation info. */ | |

struct scc_info | |

{ | |

sbitmap visited; | |

sbitmap deleted; | |

unsigned int *dfs; | |

unsigned int *node_mapping; | |

int current_index; | |

VEC(unsigned,heap) *scc_stack; | |

}; | |

/* Recursive routine to find strongly connected components in GRAPH. | |

SI is the SCC info to store the information in, and N is the id of current | |

graph node we are processing. | |

This is Tarjan's strongly connected component finding algorithm, as | |

modified by Nuutila to keep only non-root nodes on the stack. | |

The algorithm can be found in "On finding the strongly connected | |

connected components in a directed graph" by Esko Nuutila and Eljas | |

Soisalon-Soininen, in Information Processing Letters volume 49, | |

number 1, pages 9-14. */ | |

static void | |

scc_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n) | |

{ | |

unsigned int i; | |

bitmap_iterator bi; | |

unsigned int my_dfs; | |

SET_BIT (si->visited, n); | |

si->dfs[n] = si->current_index ++; | |

my_dfs = si->dfs[n]; | |

/* Visit all the successors. */ | |

EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[n], 0, i, bi) | |

{ | |

unsigned int w; | |

if (i > LAST_REF_NODE) | |

break; | |

w = find (i); | |

if (TEST_BIT (si->deleted, w)) | |

continue; | |

if (!TEST_BIT (si->visited, w)) | |

scc_visit (graph, si, w); | |

{ | |

unsigned int t = find (w); | |

unsigned int nnode = find (n); | |

gcc_assert (nnode == n); | |

if (si->dfs[t] < si->dfs[nnode]) | |

si->dfs[n] = si->dfs[t]; | |

} | |

} | |

/* See if any components have been identified. */ | |

if (si->dfs[n] == my_dfs) | |

{ | |

if (VEC_length (unsigned, si->scc_stack) > 0 | |

&& si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs) | |

{ | |

bitmap scc = BITMAP_ALLOC (NULL); | |

bool have_ref_node = n >= FIRST_REF_NODE; | |

unsigned int lowest_node; | |

bitmap_iterator bi; | |

bitmap_set_bit (scc, n); | |

while (VEC_length (unsigned, si->scc_stack) != 0 | |

&& si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs) | |

{ | |

unsigned int w = VEC_pop (unsigned, si->scc_stack); | |

bitmap_set_bit (scc, w); | |

if (w >= FIRST_REF_NODE) | |

have_ref_node = true; | |

} | |

lowest_node = bitmap_first_set_bit (scc); | |

gcc_assert (lowest_node < FIRST_REF_NODE); | |

/* Collapse the SCC nodes into a single node, and mark the | |

indirect cycles. */ | |

EXECUTE_IF_SET_IN_BITMAP (scc, 0, i, bi) | |

{ | |

if (i < FIRST_REF_NODE) | |

{ | |

if (unite (lowest_node, i)) | |

unify_nodes (graph, lowest_node, i, false); | |

} | |

else | |

{ | |

unite (lowest_node, i); | |

graph->indirect_cycles[i - FIRST_REF_NODE] = lowest_node; | |

} | |

} | |

} | |

SET_BIT (si->deleted, n); | |

} | |

else | |

VEC_safe_push (unsigned, heap, si->scc_stack, n); | |

} | |

/* Unify node FROM into node TO, updating the changed count if | |

necessary when UPDATE_CHANGED is true. */ | |

static void | |

unify_nodes (constraint_graph_t graph, unsigned int to, unsigned int from, | |

bool update_changed) | |

{ | |

gcc_assert (to != from && find (to) == to); | |

if (dump_file && (dump_flags & TDF_DETAILS)) | |

fprintf (dump_file, "Unifying %s to %s\n", | |

get_varinfo (from)->name, | |

get_varinfo (to)->name); | |

if (update_changed) | |

stats.unified_vars_dynamic++; | |

else | |

stats.unified_vars_static++; | |

merge_graph_nodes (graph, to, from); | |

merge_node_constraints (graph, to, from); | |

if (get_varinfo (from)->no_tbaa_pruning) | |

get_varinfo (to)->no_tbaa_pruning = true; | |

/* Mark TO as changed if FROM was changed. If TO was already marked | |

as changed, decrease the changed count. */ | |

if (update_changed && TEST_BIT (changed, from)) | |

{ | |

RESET_BIT (changed, from); | |

if (!TEST_BIT (changed, to)) | |

SET_BIT (changed, to); | |

else | |

{ | |

gcc_assert (changed_count > 0); | |

changed_count--; | |

} | |

} | |

if (get_varinfo (from)->solution) | |

{ | |

/* If the solution changes because of the merging, we need to mark | |

the variable as changed. */ | |

if (bitmap_ior_into (get_varinfo (to)->solution, | |

get_varinfo (from)->solution)) | |

{ | |

if (update_changed && !TEST_BIT (changed, to)) | |

{ | |

SET_BIT (changed, to); | |

changed_count++; | |

} | |

} | |

BITMAP_FREE (get_varinfo (from)->solution); | |

BITMAP_FREE (get_varinfo (from)->oldsolution); | |

if (stats.iterations > 0) | |

{ | |

BITMAP_FREE (get_varinfo (to)->oldsolution); | |

get_varinfo (to)->oldsolution = BITMAP_ALLOC (&oldpta_obstack); | |

} | |

} | |

if (valid_graph_edge (graph, to, to)) | |

{ | |

if (graph->succs[to]) | |

bitmap_clear_bit (graph->succs[to], to); | |

} | |

} | |

/* Information needed to compute the topological ordering of a graph. */ | |

struct topo_info | |

{ | |

/* sbitmap of visited nodes. */ | |

sbitmap visited; | |

/* Array that stores the topological order of the graph, *in | |

reverse*. */ | |

VEC(unsigned,heap) *topo_order; | |

}; | |

/* Initialize and return a topological info structure. */ | |

static struct topo_info * | |

init_topo_info (void) | |

{ | |

size_t size = graph->size; | |

struct topo_info *ti = XNEW (struct topo_info); | |

ti->visited = sbitmap_alloc (size); | |

sbitmap_zero (ti->visited); | |

ti->topo_order = VEC_alloc (unsigned, heap, 1); | |

return ti; | |

} | |

/* Free the topological sort info pointed to by TI. */ | |

static void | |

free_topo_info (struct topo_info *ti) | |

{ | |

sbitmap_free (ti->visited); | |

VEC_free (unsigned, heap, ti->topo_order); | |

free (ti); | |

} | |

/* Visit the graph in topological order, and store the order in the | |

topo_info structure. */ | |

static void | |

topo_visit (constraint_graph_t graph, struct topo_info *ti, | |

unsigned int n) | |

{ | |

bitmap_iterator bi; | |

unsigned int j; | |

SET_BIT (ti->visited, n); | |

if (graph->succs[n]) | |

EXECUTE_IF_SET_IN_BITMAP (graph->succs[n], 0, j, bi) | |

{ | |

if (!TEST_BIT (ti->visited, j)) | |

topo_visit (graph, ti, j); | |

} | |

VEC_safe_push (unsigned, heap, ti->topo_order, n); | |

} | |

/* Return true if variable N + OFFSET is a legal field of N. */ | |

static bool | |

type_safe (unsigned int n, unsigned HOST_WIDE_INT *offset) | |

{ | |

varinfo_t ninfo = get_varinfo (n); | |

/* For things we've globbed to single variables, any offset into the | |

variable acts like the entire variable, so that it becomes offset | |

0. */ | |

if (ninfo->is_special_var | |

|| ninfo->is_artificial_var | |

|| ninfo->is_unknown_size_var | |

|| ninfo->is_full_var) | |

{ | |

*offset = 0; | |

return true; | |

} | |

return (get_varinfo (n)->offset + *offset) < get_varinfo (n)->fullsize; | |

} | |

/* Process a constraint C that represents x = *y, using DELTA as the | |

starting solution. */ | |

static void | |

do_sd_constraint (constraint_graph_t graph, constraint_t c, | |

bitmap delta) | |

{ | |

unsigned int lhs = c->lhs.var; | |

bool flag = false; | |

bitmap sol = get_varinfo (lhs)->solution; | |

unsigned int j; | |

bitmap_iterator bi; | |

/* For x = *ESCAPED and x = *CALLUSED we want to compute the | |

reachability set of the rhs var. As a pointer to a sub-field | |

of a variable can also reach all other fields of the variable | |

we simply have to expand the solution to contain all sub-fields | |

if one sub-field is contained. */ | |

if (c->rhs.var == find (escaped_id) | |

|| c->rhs.var == find (callused_id)) | |

{ | |

bitmap vars = NULL; | |

/* In a first pass record all variables we need to add all | |

sub-fields off. This avoids quadratic behavior. */ | |

EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi) | |

{ | |

varinfo_t v = get_varinfo (j); | |

if (v->is_full_var) | |

continue; | |

v = lookup_vi_for_tree (v->decl); | |

if (v->next != NULL) | |

{ | |

if (vars == NULL) | |

vars = BITMAP_ALLOC (NULL); | |

bitmap_set_bit (vars, v->id); | |

} | |

} | |

/* In the second pass now do the addition to the solution and | |

to speed up solving add it to the delta as well. */ | |

if (vars != NULL) | |

{ | |

EXECUTE_IF_SET_IN_BITMAP (vars, 0, j, bi) | |

{ | |

varinfo_t v = get_varinfo (j); | |

for (; v != NULL; v = v->next) | |

{ | |

if (bitmap_set_bit (sol, v->id)) | |

{ | |

flag = true; | |

bitmap_set_bit (delta, v->id); | |

} | |

} | |

} | |

BITMAP_FREE (vars); | |

} | |

} | |

if (bitmap_bit_p (delta, anything_id)) | |

{ | |

flag |= bitmap_set_bit (sol, anything_id); | |

goto done; | |

} | |

/* For each variable j in delta (Sol(y)), add | |

an edge in the graph from j to x, and union Sol(j) into Sol(x). */ | |

EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi) | |

{ | |

unsigned HOST_WIDE_INT roffset = c->rhs.offset; | |

if (type_safe (j, &roffset)) | |

{ | |

varinfo_t v; | |

unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + roffset; | |

unsigned int t; | |

v = first_vi_for_offset (get_varinfo (j), fieldoffset); | |

/* If the access is outside of the variable we can ignore it. */ | |

if (!v) | |

continue; | |

t = find (v->id); | |

/* Adding edges from the special vars is pointless. | |

They don't have sets that can change. */ | |

if (get_varinfo (t)->is_special_var) | |

flag |= bitmap_ior_into (sol, get_varinfo (t)->solution); | |

/* Merging the solution from ESCAPED needlessly increases | |

the set. Use ESCAPED as representative instead. | |

Same for CALLUSED. */ | |

else if (get_varinfo (t)->id == find (escaped_id)) | |

flag |= bitmap_set_bit (sol, escaped_id); | |

else if (get_varinfo (t)->id == find (callused_id)) | |

flag |= bitmap_set_bit (sol, callused_id); | |

else if (add_graph_edge (graph, lhs, t)) | |

flag |= bitmap_ior_into (sol, get_varinfo (t)->solution); | |

} | |

} | |

done: | |

/* If the LHS solution changed, mark the var as changed. */ | |

if (flag) | |

{ | |

get_varinfo (lhs)->solution = sol; | |

if (!TEST_BIT (changed, lhs)) | |

{ | |

SET_BIT (changed, lhs); | |

changed_count++; | |

} | |

} | |

} | |

/* Process a constraint C that represents *x = y. */ | |

static void | |

do_ds_constraint (constraint_t c, bitmap delta) | |

{ | |

unsigned int rhs = c->rhs.var; | |

bitmap sol = get_varinfo (rhs)->solution; | |

unsigned int j; | |

bitmap_iterator bi; | |

/* Our IL does not allow this. */ | |

gcc_assert (c->rhs.offset == 0); | |

/* If the solution of y contains ANYTHING simply use the ANYTHING | |

solution. This avoids needlessly increasing the points-to sets. */ | |

if (bitmap_bit_p (sol, anything_id)) | |

sol = get_varinfo (find (anything_id))->solution; | |

/* If the solution for x contains ANYTHING we have to merge the | |

solution of y into all pointer variables which we do via | |

STOREDANYTHING. */ | |

if (bitmap_bit_p (delta, anything_id)) | |

{ | |

unsigned t = find (storedanything_id); | |

if (add_graph_edge (graph, t, rhs)) | |

{ | |

if (bitmap_ior_into (get_varinfo (t)->solution, sol)) | |

{ | |

if (!TEST_BIT (changed, t)) | |

{ | |

SET_BIT (changed, t); | |

changed_count++; | |

} | |

} | |

} | |

return; | |

} | |

/* For each member j of delta (Sol(x)), add an edge from y to j and | |

union Sol(y) into Sol(j) */ | |

EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi) | |

{ | |

unsigned HOST_WIDE_INT loff = c->lhs.offset; | |

if (type_safe (j, &loff) && !(get_varinfo (j)->is_special_var)) | |

{ | |

varinfo_t v; | |

unsigned int t; | |

unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + loff; | |

v = first_vi_for_offset (get_varinfo (j), fieldoffset); | |

/* If the access is outside of the variable we can ignore it. */ | |

if (!v) | |

continue; | |

if (v->may_have_pointers) | |

{ | |

t = find (v->id); | |

if (add_graph_edge (graph, t, rhs)) | |

{ | |

if (bitmap_ior_into (get_varinfo (t)->solution, sol)) | |

{ | |

if (t == rhs) | |

sol = get_varinfo (rhs)->solution; | |

if (!TEST_BIT (changed, t)) | |

{ | |

SET_BIT (changed, t); | |

changed_count++; | |

} | |

} | |

} | |

} | |

} | |

} | |

} | |

/* Handle a non-simple (simple meaning requires no iteration), | |

constraint (IE *x = &y, x = *y, *x = y, and x = y with offsets involved). */ | |

static void | |

do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta) | |

{ | |

if (c->lhs.type == DEREF) | |

{ | |

if (c->rhs.type == ADDRESSOF) | |

{ | |

gcc_unreachable(); | |

} | |

else | |

{ | |

/* *x = y */ | |

do_ds_constraint (c, delta); | |

} | |

} | |

else if (c->rhs.type == DEREF) | |

{ | |

/* x = *y */ | |

if (!(get_varinfo (c->lhs.var)->is_special_var)) | |

do_sd_constraint (graph, c, delta); | |

} | |

else | |

{ | |

bitmap tmp; | |

bitmap solution; | |

bool flag = false; | |

gcc_assert (c->rhs.type == SCALAR && c->lhs.type == SCALAR); | |

solution = get_varinfo (c->rhs.var)->solution; | |

tmp = get_varinfo (c->lhs.var)->solution; | |

flag = set_union_with_increment (tmp, solution, c->rhs.offset); | |

if (flag) | |

{ | |

get_varinfo (c->lhs.var)->solution = tmp; | |

if (!TEST_BIT (changed, c->lhs.var)) | |

{ | |

SET_BIT (changed, c->lhs.var); | |

changed_count++; | |

} | |

} | |

} | |

} | |

/* Initialize and return a new SCC info structure. */ | |

static struct scc_info * | |

init_scc_info (size_t size) | |

{ | |

struct scc_info *si = XNEW (struct scc_info); | |

size_t i; | |

si->current_index = 0; | |

si->visited = sbitmap_alloc (size); | |

sbitmap_zero (si->visited); | |

si->deleted = sbitmap_alloc (size); | |

sbitmap_zero (si->deleted); | |

si->node_mapping = XNEWVEC (unsigned int, size); | |

si->dfs = XCNEWVEC (unsigned int, size); | |

for (i = 0; i < size; i++) | |

si->node_mapping[i] = i; | |

si->scc_stack = VEC_alloc (unsigned, heap, 1); | |

return si; | |

} | |

/* Free an SCC info structure pointed to by SI */ | |

static void | |

free_scc_info (struct scc_info *si) | |

{ | |

sbitmap_free (si->visited); | |

sbitmap_free (si->deleted); | |

free (si->node_mapping); | |

free (si->dfs); | |

VEC_free (unsigned, heap, si->scc_stack); | |

free (si); | |

} | |

/* Find indirect cycles in GRAPH that occur, using strongly connected | |

components, and note them in the indirect cycles map. | |

This technique comes from Ben Hardekopf and Calvin Lin, | |

"It Pays to be Lazy: Fast and Accurate Pointer Analysis for Millions of | |

Lines of Code", submitted to PLDI 2007. */ | |

static void | |

find_indirect_cycles (constraint_graph_t graph) | |

{ | |

unsigned int i; | |

unsigned int size = graph->size; | |

struct scc_info *si = init_scc_info (size); | |

for (i = 0; i < MIN (LAST_REF_NODE, size); i ++ ) | |

if (!TEST_BIT (si->visited, i) && find (i) == i) | |

scc_visit (graph, si, i); | |

free_scc_info (si); | |

} | |

/* Compute a topological ordering for GRAPH, and store the result in the | |

topo_info structure TI. */ | |

static void | |

compute_topo_order (constraint_graph_t graph, | |

struct topo_info *ti) | |

{ | |

unsigned int i; | |

unsigned int size = graph->size; | |

for (i = 0; i != size; ++i) | |

if (!TEST_BIT (ti->visited, i) && find (i) == i) | |

topo_visit (graph, ti, i); | |

} | |

/* Structure used to for hash value numbering of pointer equivalence | |

classes. */ | |

typedef struct equiv_class_label | |

{ | |

hashval_t hashcode; | |

unsigned int equivalence_class; | |

bitmap labels; | |

} *equiv_class_label_t; | |

typedef const struct equiv_class_label *const_equiv_class_label_t; | |

/* A hashtable for mapping a bitmap of labels->pointer equivalence | |

classes. */ | |

static htab_t pointer_equiv_class_table; | |

/* A hashtable for mapping a bitmap of labels->location equivalence | |

classes. */ | |

static htab_t location_equiv_class_table; | |

/* Hash function for a equiv_class_label_t */ | |

static hashval_t | |

equiv_class_label_hash (const void *p) | |

{ | |

const_equiv_class_label_t const ecl = (const_equiv_class_label_t) p; | |

return ecl->hashcode; | |

} | |

/* Equality function for two equiv_class_label_t's. */ | |

static int | |

equiv_class_label_eq (const void *p1, const void *p2) | |

{ | |

const_equiv_class_label_t const eql1 = (const_equiv_class_label_t) p1; | |

const_equiv_class_label_t const eql2 = (const_equiv_class_label_t) p2; | |

return bitmap_equal_p (eql1->labels, eql2->labels); | |

} | |

/* Lookup a equivalence class in TABLE by the bitmap of LABELS it | |

contains. */ | |

static unsigned int | |

equiv_class_lookup (htab_t table, bitmap labels) | |

{ | |

void **slot; | |

struct equiv_class_label ecl; | |

ecl.labels = labels; | |

ecl.hashcode = bitmap_hash (labels); | |

slot = htab_find_slot_with_hash (table, &ecl, | |

ecl.hashcode, NO_INSERT); | |

if (!slot) | |

return 0; | |

else | |

return ((equiv_class_label_t) *slot)->equivalence_class; | |

} | |

/* Add an equivalence class named EQUIVALENCE_CLASS with labels LABELS | |

to TABLE. */ | |

static void | |

equiv_class_add (htab_t table, unsigned int equivalence_class, | |

bitmap labels) | |

{ | |

void **slot; | |

equiv_class_label_t ecl = XNEW (struct equiv_class_label); | |

ecl->labels = labels; | |

ecl->equivalence_class = equivalence_class; | |

ecl->hashcode = bitmap_hash (labels); | |

slot = htab_find_slot_with_hash (table, ecl, | |

ecl->hashcode, INSERT); | |

gcc_assert (!*slot); | |

*slot = (void *) ecl; | |

} | |

/* Perform offline variable substitution. | |

This is a worst case quadratic time way of identifying variables | |

that must have equivalent points-to sets, including those caused by | |

static cycles, and single entry subgraphs, in the constraint graph. | |

The technique is described in "Exploiting Pointer and Location | |

Equivalence to Optimize Pointer Analysis. In the 14th International | |

Static Analysis Symposium (SAS), August 2007." It is known as the | |

"HU" algorithm, and is equivalent to value numbering the collapsed | |

constraint graph including evaluating unions. | |

The general method of finding equivalence classes is as follows: | |

Add fake nodes (REF nodes) and edges for *a = b and a = *b constraints. | |

Initialize all non-REF nodes to be direct nodes. | |

For each constraint a = a U {b}, we set pts(a) = pts(a) u {fresh | |

variable} | |

For each constraint containing the dereference, we also do the same | |

thing. | |

We then compute SCC's in the graph and unify nodes in the same SCC, | |

including pts sets. | |

For each non-collapsed node x: | |

Visit all unvisited explicit incoming edges. | |

Ignoring all non-pointers, set pts(x) = Union of pts(a) for y | |

where y->x. | |

Lookup the equivalence class for pts(x). | |

If we found one, equivalence_class(x) = found class. | |

Otherwise, equivalence_class(x) = new class, and new_class is | |

added to the lookup table. | |

All direct nodes with the same equivalence class can be replaced | |

with a single representative node. | |

All unlabeled nodes (label == 0) are not pointers and all edges | |

involving them can be eliminated. | |

We perform these optimizations during rewrite_constraints | |

In addition to pointer equivalence class finding, we also perform | |

location equivalence class finding. This is the set of variables | |

that always appear together in points-to sets. We use this to | |

compress the size of the points-to sets. */ | |

/* Current maximum pointer equivalence class id. */ | |

static int pointer_equiv_class; | |

/* Current maximum location equivalence class id. */ | |

static int location_equiv_class; | |

/* Recursive routine to find strongly connected components in GRAPH, | |

and label it's nodes with DFS numbers. */ | |

static void | |

condense_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n) | |

{ | |

unsigned int i; | |

bitmap_iterator bi; | |

unsigned int my_dfs; | |

gcc_assert (si->node_mapping[n] == n); | |

SET_BIT (si->visited, n); | |

si->dfs[n] = si->current_index ++; | |

my_dfs = si->dfs[n]; | |

/* Visit all the successors. */ | |

EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi) | |

{ | |

unsigned int w = si->node_mapping[i]; | |

if (TEST_BIT (si->deleted, w)) | |

continue; | |

if (!TEST_BIT (si->visited, w)) | |

condense_visit (graph, si, w); | |

{ | |

unsigned int t = si->node_mapping[w]; | |

unsigned int nnode = si->node_mapping[n]; | |

gcc_assert (nnode == n); | |

if (si->dfs[t] < si->dfs[nnode]) | |

si->dfs[n] = si->dfs[t]; | |

} | |

} | |

/* Visit all the implicit predecessors. */ | |

EXECUTE_IF_IN_NONNULL_BITMAP (graph->implicit_preds[n], 0, i, bi) | |

{ | |

unsigned int w = si->node_mapping[i]; | |

if (TEST_BIT (si->deleted, w)) | |

continue; | |

if (!TEST_BIT (si->visited, w)) | |

condense_visit (graph, si, w); | |

{ | |

unsigned int t = si->node_mapping[w]; | |

unsigned int nnode = si->node_mapping[n]; | |

gcc_assert (nnode == n); | |

if (si->dfs[t] < si->dfs[nnode]) | |

si->dfs[n] = si->dfs[t]; | |

} | |

} | |

/* See if any components have been identified. */ | |

if (si->dfs[n] == my_dfs) | |

{ | |

while (VEC_length (unsigned, si->scc_stack) != 0 | |

&& si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs) | |

{ | |

unsigned int w = VEC_pop (unsigned, si->scc_stack); | |

si->node_mapping[w] = n; | |

if (!TEST_BIT (graph->direct_nodes, w)) | |

RESET_BIT (graph->direct_nodes, n); | |

/* Unify our nodes. */ | |

if (graph->preds[w]) | |

{ | |

if (!graph->preds[n]) | |

graph->preds[n] = BITMAP_ALLOC (&predbitmap_obstack); | |

bitmap_ior_into (graph->preds[n], graph->preds[w]); | |

} | |

if (graph->implicit_preds[w]) | |

{ | |

if (!graph->implicit_preds[n]) | |

graph->implicit_preds[n] = BITMAP_ALLOC (&predbitmap_obstack); | |

bitmap_ior_into (graph->implicit_preds[n], | |

graph->implicit_preds[w]); | |

} | |

if (graph->points_to[w]) | |

{ | |

if (!graph->points_to[n]) | |

graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack); | |

bitmap_ior_into (graph->points_to[n], | |

graph->points_to[w]); | |

} | |

} | |

SET_BIT (si->deleted, n); | |

} | |

else | |

VEC_safe_push (unsigned, heap, si->scc_stack, n); | |

} | |

/* Label pointer equivalences. */ | |

static void | |

label_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n) | |

{ | |

unsigned int i; | |

bitmap_iterator bi; | |

SET_BIT (si->visited, n); | |

if (!graph->points_to[n]) | |

graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack); | |

/* Label and union our incoming edges's points to sets. */ | |

EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi) | |

{ | |

unsigned int w = si->node_mapping[i]; | |

if (!TEST_BIT (si->visited, w)) | |

label_visit (graph, si, w); | |

/* Skip unused edges */ | |

if (w == n || graph->pointer_label[w] == 0) | |

continue; | |

if (graph->points_to[w]) | |

bitmap_ior_into(graph->points_to[n], graph->points_to[w]); | |

} | |

/* Indirect nodes get fresh variables. */ | |

if (!TEST_BIT (graph->direct_nodes, n)) | |

bitmap_set_bit (graph->points_to[n], FIRST_REF_NODE + n); | |

if (!bitmap_empty_p (graph->points_to[n])) | |

{ | |

unsigned int label = equiv_class_lookup (pointer_equiv_class_table, | |

graph->points_to[n]); | |

if (!label) | |

{ | |

label = pointer_equiv_class++; | |

equiv_class_add (pointer_equiv_class_table, | |

label, graph->points_to[n]); | |

} | |

graph->pointer_label[n] = label; | |

} | |

} | |

/* Perform offline variable substitution, discovering equivalence | |

classes, and eliminating non-pointer variables. */ | |

static struct scc_info * | |

perform_var_substitution (constraint_graph_t graph) | |

{ | |

unsigned int i; | |

unsigned int size = graph->size; | |

struct scc_info *si = init_scc_info (size); | |

bitmap_obstack_initialize (&iteration_obstack); | |

pointer_equiv_class_table = htab_create (511, equiv_class_label_hash, | |

equiv_class_label_eq, free); | |

location_equiv_class_table = htab_create (511, equiv_class_label_hash, | |

equiv_class_label_eq, free); | |

pointer_equiv_class = 1; | |

location_equiv_class = 1; | |

/* Condense the nodes, which means to find SCC's, count incoming | |

predecessors, and unite nodes in SCC's. */ | |

for (i = 0; i < FIRST_REF_NODE; i++) | |

if (!TEST_BIT (si->visited, si->node_mapping[i])) | |

condense_visit (graph, si, si->node_mapping[i]); | |

sbitmap_zero (si->visited); | |

/* Actually the label the nodes for pointer equivalences */ | |

for (i = 0; i < FIRST_REF_NODE; i++) | |

if (!TEST_BIT (si->visited, si->node_mapping[i])) | |

label_visit (graph, si, si->node_mapping[i]); | |

/* Calculate location equivalence labels. */ | |

for (i = 0; i < FIRST_REF_NODE; i++) | |

{ | |

bitmap pointed_by; | |

bitmap_iterator bi; | |

unsigned int j; | |

unsigned int label; | |

if (!graph->pointed_by[i]) | |

continue; | |

pointed_by = BITMAP_ALLOC (&iteration_obstack); | |

/* Translate the pointed-by mapping for pointer equivalence | |

labels. */ | |

EXECUTE_IF_SET_IN_BITMAP (graph->pointed_by[i], 0, j, bi) | |

{ | |

bitmap_set_bit (pointed_by, | |

graph->pointer_label[si->node_mapping[j]]); | |

} | |

/* The original pointed_by is now dead. */ | |

BITMAP_FREE (graph->pointed_by[i]); | |

/* Look up the location equivalence label if one exists, or make | |

one otherwise. */ | |

label = equiv_class_lookup (location_equiv_class_table, | |

pointed_by); | |

if (label == 0) | |

{ | |

label = location_equiv_class++; | |

equiv_class_add (location_equiv_class_table, | |

label, pointed_by); | |

} | |

else | |

{ | |

if (dump_file && (dump_flags & TDF_DETAILS)) | |

fprintf (dump_file, "Found location equivalence for node %s\n", | |

get_varinfo (i)->name); | |

BITMAP_FREE (pointed_by); | |

} | |

graph->loc_label[i] = label; | |

} | |

if (dump_file && (dump_flags & TDF_DETAILS)) | |

for (i = 0; i < FIRST_REF_NODE; i++) | |

{ | |

bool direct_node = TEST_BIT (graph->direct_nodes, i); | |

fprintf (dump_file, | |

"Equivalence classes for %s node id %d:%s are pointer: %d" | |

", location:%d\n", | |

direct_node ? "Direct node" : "Indirect node", i, | |

get_varinfo (i)->name, | |

graph->pointer_label[si->node_mapping[i]], | |

graph->loc_label[si->node_mapping[i]]); | |

} | |

/* Quickly eliminate our non-pointer variables. */ | |

for (i = 0; i < FIRST_REF_NODE; i++) | |

{ | |

unsigned int node = si->node_mapping[i]; | |

if (graph->pointer_label[node] == 0) | |

{ | |

if (dump_file && (dump_flags & TDF_DETAILS)) | |

fprintf (dump_file, | |

"%s is a non-pointer variable, eliminating edges.\n", | |

get_varinfo (node)->name); | |

stats.nonpointer_vars++; | |

clear_edges_for_node (graph, node); | |

} | |

} | |

return si; | |

} | |

/* Free information that was only necessary for variable | |

substitution. */ | |

static void | |

free_var_substitution_info (struct scc_info *si) | |

{ | |

free_scc_info (si); | |

free (graph->pointer_label); | |

free (graph->loc_label); | |

free (graph->pointed_by); | |

free (graph->points_to); | |

free (graph->eq_rep); | |

sbitmap_free (graph->direct_nodes); | |

htab_delete (pointer_equiv_class_table); | |

htab_delete (location_equiv_class_table); | |

bitmap_obstack_release (&iteration_obstack); | |

} | |

/* Return an existing node that is equivalent to NODE, which has | |

equivalence class LABEL, if one exists. Return NODE otherwise. */ | |

static unsigned int | |

find_equivalent_node (constraint_graph_t graph, | |

unsigned int node, unsigned int label) | |

{ | |

/* If the address version of this variable is unused, we can | |

substitute it for anything else with the same label. | |

Otherwise, we know the pointers are equivalent, but not the | |

locations, and we can unite them later. */ | |

if (!bitmap_bit_p (graph->address_taken, node)) | |

{ | |

gcc_assert (label < graph->size); | |

if (graph->eq_rep[label] != -1) | |

{ | |

/* Unify the two variables since we know they are equivalent. */ | |

if (unite (graph->eq_rep[label], node)) | |

unify_nodes (graph, graph->eq_rep[label], node, false); | |

return graph->eq_rep[label]; | |

} | |

else | |

{ | |

graph->eq_rep[label] = node; | |

graph->pe_rep[label] = node; | |

} | |

} | |

else | |

{ | |

gcc_assert (label < graph->size); | |

graph->pe[node] = label; | |

if (graph->pe_rep[label] == -1) | |

graph->pe_rep[label] = node; | |

} | |

return node; | |

} | |

/* Unite pointer equivalent but not location equivalent nodes in | |

GRAPH. This may only be performed once variable substitution is | |

finished. */ | |

static void | |

unite_pointer_equivalences (constraint_graph_t graph) | |

{ | |

unsigned int i; | |

/* Go through the pointer equivalences and unite them to their | |

representative, if they aren't already. */ | |

for (i = 0; i < FIRST_REF_NODE; i++) | |

{ | |

unsigned int label = graph->pe[i]; | |

if (label) | |

{ | |

int label_rep = graph->pe_rep[label]; | |

if (label_rep == -1) | |

continue; | |

label_rep = find (label_rep); | |

if (label_rep >= 0 && unite (label_rep, find (i))) | |

unify_nodes (graph, label_rep, i, false); | |

} | |

} | |

} | |

/* Move complex constraints to the GRAPH nodes they belong to. */ | |

static void | |

move_complex_constraints (constraint_graph_t graph) | |

{ | |

int i; | |

constraint_t c; | |

for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++) | |

{ | |

if (c) | |

{ | |

struct constraint_expr lhs = c->lhs; | |

struct constraint_expr rhs = c->rhs; | |

if (lhs.type == DEREF) | |

{ | |

insert_into_complex (graph, lhs.var, c); | |

} | |

else if (rhs.type == DEREF) | |

{ | |

if (!(get_varinfo (lhs.var)->is_special_var)) | |

insert_into_complex (graph, rhs.var, c); | |

} | |

else if (rhs.type != ADDRESSOF && lhs.var > anything_id | |

&& (lhs.offset != 0 || rhs.offset != 0)) | |

{ | |

insert_into_complex (graph, rhs.var, c); | |

} | |

} | |

} | |

} | |

/* Optimize and rewrite complex constraints while performing | |

collapsing of equivalent nodes. SI is the SCC_INFO that is the | |

result of perform_variable_substitution. */ | |

static void | |

rewrite_constraints (constraint_graph_t graph, | |

struct scc_info *si) | |

{ | |

int i; | |

unsigned int j; | |

constraint_t c; | |

for (j = 0; j < graph->size; j++) | |

gcc_assert (find (j) == j); | |

for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++) | |

{ | |

struct constraint_expr lhs = c->lhs; | |

struct constraint_expr rhs = c->rhs; | |

unsigned int lhsvar = find (get_varinfo_fc (lhs.var)->id); | |

unsigned int rhsvar = find (get_varinfo_fc (rhs.var)->id); | |

unsigned int lhsnode, rhsnode; | |

unsigned int lhslabel, rhslabel; | |

lhsnode = si->node_mapping[lhsvar]; | |

rhsnode = si->node_mapping[rhsvar]; | |

lhslabel = graph->pointer_label[lhsnode]; | |

rhslabel = graph->pointer_label[rhsnode]; | |

/* See if it is really a non-pointer variable, and if so, ignore | |

the constraint. */ | |

if (lhslabel == 0) | |

{ | |

if (dump_file && (dump_flags & TDF_DETAILS)) | |

{ | |

fprintf (dump_file, "%s is a non-pointer variable," | |

"ignoring constraint:", | |

get_varinfo (lhs.var)->name); | |

dump_constraint (dump_file, c); | |

} | |

VEC_replace (constraint_t, constraints, i, NULL); | |

continue; | |

} | |

if (rhslabel == 0) | |

{ | |

if (dump_file && (dump_flags & TDF_DETAILS)) | |

{ | |

fprintf (dump_file, "%s is a non-pointer variable," | |

"ignoring constraint:", | |

get_varinfo (rhs.var)->name); | |

dump_constraint (dump_file, c); | |

} | |

VEC_replace (constraint_t, constraints, i, NULL); | |

continue; | |

} | |

lhsvar = find_equivalent_node (graph, lhsvar, lhslabel); | |

rhsvar = find_equivalent_node (graph, rhsvar, rhslabel); | |

c->lhs.var = lhsvar; | |

c->rhs.var = rhsvar; | |

} | |

} | |

/* Eliminate indirect cycles involving NODE. Return true if NODE was | |

part of an SCC, false otherwise. */ | |

static bool | |

eliminate_indirect_cycles (unsigned int node) | |

{ | |

if (graph->indirect_cycles[node] != -1 | |

&& !bitmap_empty_p (get_varinfo (node)->solution)) | |

{ | |

unsigned int i; | |

VEC(unsigned,heap) *queue = NULL; | |

int queuepos; | |

unsigned int to = find (graph->indirect_cycles[node]); | |

bitmap_iterator bi; | |

/* We can't touch the solution set and call unify_nodes | |

at the same time, because unify_nodes is going to do | |

bitmap unions into it. */ | |

EXECUTE_IF_SET_IN_BITMAP (get_varinfo (node)->solution, 0, i, bi) | |

{ | |

if (find (i) == i && i != to) | |

{ | |

if (unite (to, i)) | |

VEC_safe_push (unsigned, heap, queue, i); | |

} | |

} | |

for (queuepos = 0; | |

VEC_iterate (unsigned, queue, queuepos, i); | |

queuepos++) | |

{ | |

unify_nodes (graph, to, i, true); | |

} | |

VEC_free (unsigned, heap, queue); | |

return true; | |

} | |

return false; | |

} | |

/* Solve the constraint graph GRAPH using our worklist solver. | |

This is based on the PW* family of solvers from the "Efficient Field | |

Sensitive Pointer Analysis for C" paper. | |

It works by iterating over all the graph nodes, processing the complex | |

constraints and propagating the copy constraints, until everything stops | |

changed. This corresponds to steps 6-8 in the solving list given above. */ | |

static void | |

solve_graph (constraint_graph_t graph) | |

{ | |

unsigned int size = graph->size; | |

unsigned int i; | |

bitmap pts; | |

changed_count = 0; | |

changed = sbitmap_alloc (size); | |

sbitmap_zero (changed); | |

/* Mark all initial non-collapsed nodes as changed. */ | |

for (i = 0; i < size; i++) | |

{ | |

varinfo_t ivi = get_varinfo (i); | |

if (find (i) == i && !bitmap_empty_p (ivi->solution) | |

&& ((graph->succs[i] && !bitmap_empty_p (graph->succs[i])) | |

|| VEC_length (constraint_t, graph->complex[i]) > 0)) | |

{ | |

SET_BIT (changed, i); | |

changed_count++; | |

} | |

} | |

/* Allocate a bitmap to be used to store the changed bits. */ | |

pts = BITMAP_ALLOC (&pta_obstack); | |

while (changed_count > 0) | |

{ | |

unsigned int i; | |

struct topo_info *ti = init_topo_info (); | |

stats.iterations++; | |

bitmap_obstack_initialize (&iteration_obstack); | |

compute_topo_order (graph, ti); | |

while (VEC_length (unsigned, ti->topo_order) != 0) | |

{ | |

i = VEC_pop (unsigned, ti->topo_order); | |

/* If this variable is not a representative, skip it. */ | |

if (find (i) != i) | |

continue; | |

/* In certain indirect cycle cases, we may merge this | |

variable to another. */ | |

if (eliminate_indirect_cycles (i) && find (i) != i) | |

continue; | |

/* If the node has changed, we need to process the | |

complex constraints and outgoing edges again. */ | |

if (TEST_BIT (changed, i)) | |

{ | |

unsigned int j; | |

constraint_t c; | |

bitmap solution; | |

VEC(constraint_t,heap) *complex = graph->complex[i]; | |

bool solution_empty; | |

RESET_BIT (changed, i); | |

changed_count--; | |

/* Compute the changed set of solution bits. */ | |

bitmap_and_compl (pts, get_varinfo (i)->solution, | |

get_varinfo (i)->oldsolution); | |

if (bitmap_empty_p (pts)) | |

continue; | |

bitmap_ior_into (get_varinfo (i)->oldsolution, pts); | |

solution = get_varinfo (i)->solution; | |

solution_empty = bitmap_empty_p (solution); | |

/* Process the complex constraints */ | |

for (j = 0; VEC_iterate (constraint_t, complex, j, c); j++) | |

{ | |

/* XXX: This is going to unsort the constraints in | |

some cases, which will occasionally add duplicate | |

constraints during unification. This does not | |

affect correctness. */ | |

c->lhs.var = find (c->lhs.var); | |

c->rhs.var = find (c->rhs.var); | |

/* The only complex constraint that can change our | |

solution to non-empty, given an empty solution, | |

is a constraint where the lhs side is receiving | |

some set from elsewhere. */ | |

if (!solution_empty || c->lhs.type != DEREF) | |

do_complex_constraint (graph, c, pts); | |

} | |

solution_empty = bitmap_empty_p (solution); | |

if (!solution_empty | |

/* Do not propagate the ESCAPED/CALLUSED solutions. */ | |

&& i != find (escaped_id) | |

&& i != find (callused_id)) | |

{ | |

bitmap_iterator bi; | |

/* Propagate solution to all successors. */ | |

EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i], | |

0, j, bi) | |

{ | |

bitmap tmp; | |

bool flag; | |

unsigned int to = find (j); | |

tmp = get_varinfo (to)->solution; | |

flag = false; | |

/* Don't try to propagate to ourselves. */ | |

if (to == i) | |

continue; | |

flag = set_union_with_increment (tmp, pts, 0); | |

if (flag) | |

{ | |

get_varinfo (to)->solution = tmp; | |

if (!TEST_BIT (changed, to)) | |

{ | |

SET_BIT (changed, to); | |

changed_count++; | |

} | |

} | |

} | |

} | |

} | |

} | |

free_topo_info (ti); | |

bitmap_obstack_release (&iteration_obstack); | |

} | |

BITMAP_FREE (pts); | |

sbitmap_free (changed); | |

bitmap_obstack_release (&oldpta_obstack); | |

} | |

/* Map from trees to variable infos. */ | |

static struct pointer_map_t *vi_for_tree; | |

/* Insert ID as the variable id for tree T in the vi_for_tree map. */ | |

static void | |

insert_vi_for_tree (tree t, varinfo_t vi) | |

{ | |

void **slot = pointer_map_insert (vi_for_tree, t); | |

gcc_assert (vi); | |

gcc_assert (*slot == NULL); | |

*slot = vi; | |

} | |

/* Find the variable info for tree T in VI_FOR_TREE. If T does not | |

exist in the map, return NULL, otherwise, return the varinfo we found. */ | |

static varinfo_t | |

lookup_vi_for_tree (tree t) | |

{ | |

void **slot = pointer_map_contains (vi_for_tree, t); | |

if (slot == NULL) | |

return NULL; | |

return (varinfo_t) *slot; | |

} | |

/* Return a printable name for DECL */ | |

static const char * | |

alias_get_name (tree decl) | |

{ | |

const char *res = get_name (decl); | |

char *temp; | |

int num_printed = 0; | |

if (res != NULL) | |

return res; | |

res = "NULL"; | |

if (!dump_file) | |

return res; | |

if (TREE_CODE (decl) == SSA_NAME) | |

{ | |

num_printed = asprintf (&temp, "%s_%u", | |

alias_get_name (SSA_NAME_VAR (decl)), | |

SSA_NAME_VERSION (decl)); | |

} | |

else if (DECL_P (decl)) | |

{ | |

num_printed = asprintf (&temp, "D.%u", DECL_UID (decl)); | |

} | |

if (num_printed > 0) | |

{ | |

res = ggc_strdup (temp); | |

free (temp); | |

} | |

return res; | |

} | |

/* Find the variable id for tree T in the map. | |

If T doesn't exist in the map, create an entry for it and return it. */ | |

static varinfo_t | |

get_vi_for_tree (tree t) | |

{ | |

void **slot = pointer_map_contains (vi_for_tree, t); | |

if (slot == NULL) | |

return get_varinfo (create_variable_info_for (t, alias_get_name (t))); | |

return (varinfo_t) *slot; | |

} | |

/* Get a constraint expression for a new temporary variable. */ | |

static struct constraint_expr | |

get_constraint_exp_for_temp (tree t) | |

{ | |

struct constraint_expr cexpr; | |

gcc_assert (SSA_VAR_P (t)); | |

cexpr.type = SCALAR; | |

cexpr.var = get_vi_for_tree (t)->id; | |

cexpr.offset = 0; | |

return cexpr; | |

} | |

/* Get a constraint expression vector from an SSA_VAR_P node. | |

If address_p is true, the result will be taken its address of. */ | |

static void | |

get_constraint_for_ssa_var (tree t, VEC(ce_s, heap) **results, bool address_p) | |

{ | |

struct constraint_expr cexpr; | |

varinfo_t vi; | |

/* We allow FUNCTION_DECLs here even though it doesn't make much sense. */ | |

gcc_assert (SSA_VAR_P (t) || DECL_P (t)); | |

/* For parameters, get at the points-to set for the actual parm | |

decl. */ | |

if (TREE_CODE (t) == SSA_NAME | |

&& TREE_CODE (SSA_NAME_VAR (t)) == PARM_DECL | |

&& SSA_NAME_IS_DEFAULT_DEF (t)) | |

{ | |

get_constraint_for_ssa_var (SSA_NAME_VAR (t), results, address_p); | |

return; | |

} | |

vi = get_vi_for_tree (t); | |

cexpr.var = vi->id; | |

cexpr.type = SCALAR; | |

cexpr.offset = 0; | |

/* If we determine the result is "anything", and we know this is readonly, | |

say it points to readonly memory instead. */ | |

if (cexpr.var == anything_id && TREE_READONLY (t)) | |

{ | |

gcc_unreachable (); | |

cexpr.type = ADDRESSOF; | |

cexpr.var = readonly_id; | |

} | |

/* If we are not taking the address of the constraint expr, add all | |

sub-fiels of the variable as well. */ | |

if (!address_p) | |

{ | |

for (; vi; vi = vi->next) | |

{ | |

cexpr.var = vi->id; | |

VEC_safe_push (ce_s, heap, *results, &cexpr); | |

} | |

return; | |

} | |

VEC_safe_push (ce_s, heap, *results, &cexpr); | |

} | |

/* Process constraint T, performing various simplifications and then | |

adding it to our list of overall constraints. */ | |

static void | |

process_constraint (constraint_t t) | |

{ | |

struct constraint_expr rhs = t->rhs; | |

struct constraint_expr lhs = t->lhs; | |

gcc_assert (rhs.var < VEC_length (varinfo_t, varmap)); | |

gcc_assert (lhs.var < VEC_length (varinfo_t, varmap)); | |

/* ANYTHING == ANYTHING is pointless. */ | |

if (lhs.var == anything_id && rhs.var == anything_id) | |

return; | |

/* If we have &ANYTHING = something, convert to SOMETHING = &ANYTHING) */ | |

else if (lhs.var == anything_id && lhs.type == ADDRESSOF) | |

{ | |

rhs = t->lhs; | |

t->lhs = t->rhs; | |

t->rhs = rhs; | |

process_constraint (t); | |

} | |

/* This can happen in our IR with things like n->a = *p */ | |

else if (rhs.type == DEREF && lhs.type == DEREF && rhs.var != anything_id) | |

{ | |

/* Split into tmp = *rhs, *lhs = tmp */ | |

tree rhsdecl = get_varinfo (rhs.var)->decl; | |

tree pointertype = TREE_TYPE (rhsdecl); | |

tree pointedtotype = TREE_TYPE (pointertype); | |

tree tmpvar = create_tmp_var_raw (pointedtotype, "doubledereftmp"); | |

struct constraint_expr tmplhs = get_constraint_exp_for_temp (tmpvar); | |

process_constraint (new_constraint (tmplhs, rhs)); | |

process_constraint (new_constraint (lhs, tmplhs)); | |

} | |

else if (rhs.type == ADDRESSOF && lhs.type == DEREF) | |

{ | |

/* Split into tmp = &rhs, *lhs = tmp */ | |

tree rhsdecl = get_varinfo (rhs.var)->decl; | |

tree pointertype = TREE_TYPE (rhsdecl); | |

tree tmpvar = create_tmp_var_raw (pointertype, "derefaddrtmp"); | |

struct constraint_expr tmplhs = get_constraint_exp_for_temp (tmpvar); | |

process_constraint (new_constraint (tmplhs, rhs)); | |

process_constraint (new_constraint (lhs, tmplhs)); | |

} | |

else | |

{ | |

gcc_assert (rhs.type != ADDRESSOF || rhs.offset == 0); | |

VEC_safe_push (constraint_t, heap, constraints, t); | |

} | |

} | |

/* Return true if T is a type that could contain pointers. */ | |

static bool | |

type_could_have_pointers (tree type) | |

{ | |

if (POINTER_TYPE_P (type)) | |

return true; | |

if (TREE_CODE (type) == ARRAY_TYPE) | |

return type_could_have_pointers (TREE_TYPE (type)); | |

return AGGREGATE_TYPE_P (type); | |

} | |

/* Return true if T is a variable of a type that could contain | |

pointers. */ | |

static bool | |

could_have_pointers (tree t) | |

{ | |

return type_could_have_pointers (TREE_TYPE (t)); | |

} | |

/* Return the position, in bits, of FIELD_DECL from the beginning of its | |

structure. */ | |

static HOST_WIDE_INT | |

bitpos_of_field (const tree fdecl) | |

{ | |

if (!host_integerp (DECL_FIELD_OFFSET (fdecl), 0) | |

|| !host_integerp (DECL_FIELD_BIT_OFFSET (fdecl), 0)) | |

return -1; | |

return (TREE_INT_CST_LOW (DECL_FIELD_OFFSET (fdecl)) * 8 | |

+ TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (fdecl))); | |

} | |

/* Get constraint expressions for offsetting PTR by OFFSET. Stores the | |

resulting constraint expressions in *RESULTS. */ | |

static void | |

get_constraint_for_ptr_offset (tree ptr, tree offset, | |

VEC (ce_s, heap) **results) | |

{ | |

struct constraint_expr c; | |

unsigned int j, n; | |

unsigned HOST_WIDE_INT rhsunitoffset, rhsoffset; | |

/* If we do not do field-sensitive PTA adding offsets to pointers | |

does not change the points-to solution. */ | |

if (!use_field_sensitive) | |

{ | |

get_constraint_for (ptr, results); | |

return; | |

} | |

/* If the offset is not a non-negative integer constant that fits | |

in a HOST_WIDE_INT, we have to fall back to a conservative | |

solution which includes all sub-fields of all pointed-to | |

variables of ptr. | |

??? As we do not have the ability to express this, fall back | |

to anything. */ | |

if (!host_integerp (offset, 1)) | |

{ | |

struct constraint_expr temp; | |

temp.var = anything_id; | |

temp.type = SCALAR; | |

temp.offset = 0; | |

VEC_safe_push (ce_s, heap, *results, &temp); | |

return; | |

} | |

/* Make sure the bit-offset also fits. */ | |

rhsunitoffset = TREE_INT_CST_LOW (offset); | |

rhsoffset = rhsunitoffset * BITS_PER_UNIT; | |

if (rhsunitoffset != rhsoffset / BITS_PER_UNIT) | |

{ | |

struct constraint_expr temp; | |

temp.var = anything_id; | |

temp.type = SCALAR; | |

temp.offset = 0; | |

VEC_safe_push (ce_s, heap, *results, &temp); | |

return; | |

} | |

get_constraint_for (ptr, results); | |

if (rhsoffset == 0) | |

return; | |

/* As we are eventually appending to the solution do not use | |

VEC_iterate here. */ | |

n = VEC_length (ce_s, *results); | |

for (j = 0; j < n; j++) | |

{ | |

varinfo_t curr; | |

c = *VEC_index (ce_s, *results, j); | |

curr = get_varinfo (c.var); | |

if (c.type == ADDRESSOF | |

&& !curr->is_full_var) | |

{ | |

varinfo_t temp, curr = get_varinfo (c.var); | |

/* Search the sub-field which overlaps with the | |

pointed-to offset. As we deal with positive offsets | |

only, we can start the search from the current variable. */ | |

temp = first_vi_for_offset (curr, curr->offset + rhsoffset); | |

/* If the result is outside of the variable we have to provide | |

a conservative result, as the variable is still reachable | |

from the resulting pointer (even though it technically | |

cannot point to anything). The last sub-field is such | |

a conservative result. | |

??? If we always had a sub-field for &object + 1 then | |

we could represent this in a more precise way. */ | |