You should have received a copy of the GNU General Public License
along with GCC; if not, write to the Free Software
-Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
*/
#include "config.h"
#include "ggc.h"
#include "obstack.h"
#include "bitmap.h"
-#include "tree-ssa-structalias.h"
#include "flags.h"
#include "rtl.h"
#include "tm_p.h"
#include "basic-block.h"
#include "output.h"
#include "errors.h"
-#include "expr.h"
#include "diagnostic.h"
#include "tree.h"
#include "c-common.h"
#include "timevar.h"
#include "alloc-pool.h"
#include "splay-tree.h"
+#include "tree-ssa-structalias.h"
/* The idea behind this analyzer is to generate set constraints from the
program, then solve the resulting constraints in order to generate the
static bitmap_obstack ptabitmap_obstack;
static bitmap_obstack iteration_obstack;
DEF_VEC_P(constraint_t);
-DEF_VEC_ALLOC_P(constraint_t,gc);
+DEF_VEC_ALLOC_P(constraint_t,heap);
static struct constraint_stats
{
/* True for variables that have unions somewhere in them. */
unsigned int has_union:1;
+ /* True if this is a heap variable. */
+ unsigned int is_heap_var:1;
+
/* Points-to set for this variable. */
bitmap solution;
/* Vector of complex constraints for this node. Complex
constraints are those involving dereferences. */
- VEC(constraint_t,gc) *complex;
+ VEC(constraint_t,heap) *complex;
};
typedef struct variable_info *varinfo_t;
DEF_VEC_P(varinfo_t);
-DEF_VEC_ALLOC_P(varinfo_t, gc);
+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,gc) *varmap;
+static VEC(varinfo_t,heap) *varmap;
#define get_varinfo(n) VEC_index(varinfo_t, varmap, n)
/* Variable that represents the unknown pointer. */
static tree integer_tree;
static unsigned int integer_id;
+/* Variable that represents arbitrary offsets into an object. Used to
+ represent pointer arithmetic, which may not legally escape the
+ bounds of an object. */
+static varinfo_t var_anyoffset;
+static tree anyoffset_tree;
+static unsigned int anyoffset_id;
/* Return a new variable info structure consisting for a variable
named NAME, and using constraint graph node NODE. */
ret->address_taken = false;
ret->indirect_target = false;
ret->is_artificial_var = false;
+ ret->is_heap_var = false;
ret->is_unknown_size_var = false;
ret->solution = BITMAP_ALLOC (&ptabitmap_obstack);
bitmap_clear (ret->solution);
/* List of constraints that we use to build the constraint graph from. */
-static VEC(constraint_t,gc) *constraints;
+static VEC(constraint_t,heap) *constraints;
static alloc_pool constraint_pool;
/* An edge in the constraint graph. We technically have no use for
}
DEF_VEC_P(constraint_edge_t);
-DEF_VEC_ALLOC_P(constraint_edge_t,gc);
+DEF_VEC_ALLOC_P(constraint_edge_t,heap);
/* The constraint graph is simply a set of adjacency vectors, one per
IOW, all edges are "forward" edges, which is not like our CFG.
So remember that
preds[x]->src == x, and
- succs[x]->src == x*/
+ succs[x]->src == x. */
struct constraint_graph
{
- VEC(constraint_edge_t,gc) **succs;
- VEC(constraint_edge_t,gc) **preds;
+ VEC(constraint_edge_t,heap) **succs;
+ VEC(constraint_edge_t,heap) **preds;
};
typedef struct constraint_graph *constraint_graph_t;
/* Find a constraint LOOKFOR in the sorted constraint vector VEC */
static constraint_t
-constraint_vec_find (VEC(constraint_t,gc) *vec,
+constraint_vec_find (VEC(constraint_t,heap) *vec,
struct constraint lookfor)
{
unsigned int place;
/* Union two constraint vectors, TO and FROM. Put the result in TO. */
static void
-constraint_set_union (VEC(constraint_t,gc) **to,
- VEC(constraint_t,gc) **from)
+constraint_set_union (VEC(constraint_t,heap) **to,
+ VEC(constraint_t,heap) **from)
{
int i;
constraint_t c;
{
unsigned int place = VEC_lower_bound (constraint_t, *to, c,
constraint_less);
- VEC_safe_insert (constraint_t, gc, *to, place, c);
+ VEC_safe_insert (constraint_t, heap, *to, place, c);
}
}
}
varinfo_t vi = get_varinfo (var);
unsigned int place = VEC_lower_bound (constraint_t, vi->complex, c,
constraint_less);
- VEC_safe_insert (constraint_t, gc, vi->complex, place, c);
+ VEC_safe_insert (constraint_t, heap, vi->complex, place, c);
}
Return the edge, if found, NULL otherwise. */
static constraint_edge_t
-constraint_edge_vec_find (VEC(constraint_edge_t,gc) *vec,
+constraint_edge_vec_find (VEC(constraint_edge_t,heap) *vec,
struct constraint_edge lookfor)
{
unsigned int place;
c->lhs.var = to;
}
constraint_set_union (&tovi->complex, &srcvi->complex);
+ VEC_free (constraint_t, heap, srcvi->complex);
srcvi->complex = NULL;
}
static void
erase_graph_self_edge (constraint_graph_t graph, struct constraint_edge edge)
{
- VEC(constraint_edge_t,gc) *predvec = graph->preds[edge.src];
- VEC(constraint_edge_t,gc) *succvec = graph->succs[edge.dest];
+ VEC(constraint_edge_t,heap) *predvec = graph->preds[edge.src];
+ VEC(constraint_edge_t,heap) *succvec = graph->succs[edge.dest];
unsigned int place;
gcc_assert (edge.src == edge.dest);
static void
clear_edges_for_node (constraint_graph_t graph, unsigned int node)
{
- VEC(constraint_edge_t,gc) *succvec = graph->succs[node];
- VEC(constraint_edge_t,gc) *predvec = graph->preds[node];
+ VEC(constraint_edge_t,heap) *succvec = graph->succs[node];
+ VEC(constraint_edge_t,heap) *predvec = graph->preds[node];
constraint_edge_t c;
int i;
VEC_ordered_remove (constraint_edge_t, graph->succs[c->dest], place);
}
+ VEC_free (constraint_edge_t, heap, graph->preds[node]);
+ VEC_free (constraint_edge_t, heap, graph->succs[node]);
graph->preds[node] = NULL;
graph->succs[node] = NULL;
}
unsigned int place;
unsigned int src = newe.src;
unsigned int dest = newe.dest;
- VEC(constraint_edge_t,gc) *vec;
+ VEC(constraint_edge_t,heap) *vec;
vec = graph->preds[src];
place = VEC_lower_bound (constraint_edge_t, vec, &newe,
weightbitmap = BITMAP_ALLOC (&ptabitmap_obstack);
edge->weights = weightbitmap;
- VEC_safe_insert (constraint_edge_t, gc, graph->preds[edge->src],
+ VEC_safe_insert (constraint_edge_t, heap, graph->preds[edge->src],
place, edge);
edge = new_constraint_edge (dest, src);
edge->weights = weightbitmap;
place = VEC_lower_bound (constraint_edge_t, graph->succs[edge->src],
edge, constraint_edge_less);
- VEC_safe_insert (constraint_edge_t, gc, graph->succs[edge->src],
+ VEC_safe_insert (constraint_edge_t, heap, graph->succs[edge->src],
place, edge);
edge_added = true;
return true;
{
constraint_edge_t edge;
unsigned int src = lookfor.src;
- VEC(constraint_edge_t,gc) *vec;
+ VEC(constraint_edge_t,heap) *vec;
vec = graph->preds[src];
edge = constraint_edge_vec_find (vec, lookfor);
gcc_assert (edge != NULL);
merge_graph_nodes (constraint_graph_t graph, unsigned int to,
unsigned int from)
{
- VEC(constraint_edge_t,gc) *succvec = graph->succs[from];
- VEC(constraint_edge_t,gc) *predvec = graph->preds[from];
+ VEC(constraint_edge_t,heap) *succvec = graph->succs[from];
+ VEC(constraint_edge_t,heap) *predvec = graph->preds[from];
int i;
constraint_edge_t c;
int i = 0;
constraint_t c;
- graph = ggc_alloc (sizeof (struct constraint_graph));
- graph->succs = ggc_alloc_cleared (VEC_length (varinfo_t, varmap) * sizeof (*graph->succs));
- graph->preds = ggc_alloc_cleared (VEC_length (varinfo_t, varmap) * sizeof (*graph->preds));
+ graph = xmalloc (sizeof (struct constraint_graph));
+ graph->succs = xcalloc (VEC_length (varinfo_t, varmap),
+ sizeof (*graph->succs));
+ graph->preds = xcalloc (VEC_length (varinfo_t, varmap),
+ sizeof (*graph->preds));
+
for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
{
struct constraint_expr lhs = c->lhs;
}
}
}
+
+
/* Changed variables on the last iteration. */
static unsigned int changed_count;
static sbitmap changed;
-DEF_VEC_I(uint);
-DEF_VEC_ALLOC_I(uint,heap);
+DEF_VEC_I(unsigned);
+DEF_VEC_ALLOC_I(unsigned,heap);
/* Strongly Connected Component visitation info. */
sbitmap in_component;
int current_index;
unsigned int *visited_index;
- VEC(uint,heap) *scc_stack;
- VEC(uint,heap) *unification_queue;
+ VEC(unsigned,heap) *scc_stack;
+ VEC(unsigned,heap) *unification_queue;
};
{
unsigned int t = si->visited_index[n];
SET_BIT (si->in_component, n);
- while (VEC_length (uint, si->scc_stack) != 0
- && t < si->visited_index[VEC_last (uint, si->scc_stack)])
+ while (VEC_length (unsigned, si->scc_stack) != 0
+ && t < si->visited_index[VEC_last (unsigned, si->scc_stack)])
{
- unsigned int w = VEC_pop (uint, si->scc_stack);
+ unsigned int w = VEC_pop (unsigned, si->scc_stack);
get_varinfo (w)->node = n;
SET_BIT (si->in_component, w);
/* Mark this node for collapsing. */
- VEC_safe_push (uint, heap, si->unification_queue, w);
+ VEC_safe_push (unsigned, heap, si->unification_queue, w);
}
}
else
- VEC_safe_push (uint, heap, si->scc_stack, n);
+ VEC_safe_push (unsigned, heap, si->scc_stack, n);
}
changed rep's solution.
Delete any 0 weighted self-edges we now have for rep. */
- while (i != VEC_length (uint, si->unification_queue))
+ while (i != VEC_length (unsigned, si->unification_queue))
{
- unsigned int tounify = VEC_index (uint, si->unification_queue, i);
+ unsigned int tounify = VEC_index (unsigned, si->unification_queue, i);
unsigned int n = get_varinfo (tounify)->node;
if (dump_file && (dump_flags & TDF_DETAILS))
/* If we've either finished processing the entire queue, or
finished processing all nodes for component n, update the solution for
n. */
- if (i == VEC_length (uint, si->unification_queue)
- || get_varinfo (VEC_index (uint, si->unification_queue, i))->node != n)
+ if (i == VEC_length (unsigned, si->unification_queue)
+ || get_varinfo (VEC_index (unsigned, si->unification_queue, i))->node != n)
{
struct constraint_edge edge;
sbitmap visited;
/* Array that stores the topological order of the graph, *in
reverse*. */
- VEC(uint,heap) *topo_order;
+ VEC(unsigned,heap) *topo_order;
};
struct topo_info *ti = xmalloc (sizeof (struct topo_info));
ti->visited = sbitmap_alloc (size);
sbitmap_zero (ti->visited);
- ti->topo_order = VEC_alloc (uint, heap, 1);
+ ti->topo_order = VEC_alloc (unsigned, heap, 1);
return ti;
}
free_topo_info (struct topo_info *ti)
{
sbitmap_free (ti->visited);
- VEC_free (uint, heap, ti->topo_order);
+ VEC_free (unsigned, heap, ti->topo_order);
free (ti);
}
topo_visit (constraint_graph_t graph, struct topo_info *ti,
unsigned int n)
{
- VEC(constraint_edge_t,gc) *succs = graph->succs[n];
+ VEC(constraint_edge_t,heap) *succs = graph->succs[n];
constraint_edge_t c;
int i;
SET_BIT (ti->visited, n);
if (!TEST_BIT (ti->visited, c->dest))
topo_visit (graph, ti, c->dest);
}
- VEC_safe_push (uint, heap, ti->topo_order, n);
+ VEC_safe_push (unsigned, heap, ti->topo_order, n);
}
/* Return true if variable N + OFFSET is a legal field of N. */
si->in_component = sbitmap_alloc (size);
sbitmap_ones (si->in_component);
si->visited_index = xcalloc (sizeof (unsigned int), size + 1);
- si->scc_stack = VEC_alloc (uint, heap, 1);
- si->unification_queue = VEC_alloc (uint, heap, 1);
+ si->scc_stack = VEC_alloc (unsigned, heap, 1);
+ si->unification_queue = VEC_alloc (unsigned, heap, 1);
return si;
}
sbitmap_free (si->visited);
sbitmap_free (si->in_component);
free (si->visited_index);
- VEC_free (uint, heap, si->scc_stack);
- VEC_free (uint, heap, si->unification_queue);
+ VEC_free (unsigned, heap, si->scc_stack);
+ VEC_free (unsigned, heap, si->unification_queue);
free(si);
}
node in topological order. */
compute_topo_order (graph, ti);
- while (VEC_length (uint, ti->topo_order) != 0)
+ while (VEC_length (unsigned, ti->topo_order) != 0)
{
- unsigned int i = VEC_pop (uint, ti->topo_order);
+ unsigned int i = VEC_pop (unsigned, ti->topo_order);
unsigned int pred;
varinfo_t vi = get_varinfo (i);
bool okay_to_elim = false;
unsigned int root = VEC_length (varinfo_t, varmap);
- VEC(constraint_edge_t,gc) *predvec = graph->preds[i];
+ VEC(constraint_edge_t,heap) *predvec = graph->preds[i];
constraint_edge_t ce;
bitmap tmp;
compute_topo_order (graph, ti);
- while (VEC_length (uint, ti->topo_order) != 0)
+ while (VEC_length (unsigned, ti->topo_order) != 0)
{
- i = VEC_pop (uint, ti->topo_order);
+ i = VEC_pop (unsigned, ti->topo_order);
gcc_assert (get_varinfo (i)->node == i);
/* If the node has changed, we need to process the
constraint_t c;
constraint_edge_t e;
bitmap solution;
- VEC(constraint_t,gc) *complex = get_varinfo (i)->complex;
- VEC(constraint_edge_t,gc) *succs;
+ VEC(constraint_t,heap) *complex = get_varinfo (i)->complex;
+ VEC(constraint_edge_t,heap) *succs;
RESET_BIT (changed, i);
changed_count--;
cexpr.type = SCALAR;
- if (TREE_READONLY (t))
+ cexpr.var = get_id_for_tree (t);
+ /* 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))
{
cexpr.type = ADDRESSOF;
cexpr.var = readonly_id;
}
- else
- cexpr.var = get_id_for_tree (t);
cexpr.offset = 0;
return cexpr;
for (vi = get_varinfo (rhs.var); vi != NULL; vi = vi->next)
vi->address_taken = true;
- VEC_safe_push (constraint_t, gc, constraints, t);
+ VEC_safe_push (constraint_t, heap, constraints, t);
}
else
{
if (lhs.type != DEREF && rhs.type == DEREF)
get_varinfo (lhs.var)->indirect_target = true;
- VEC_safe_push (constraint_t, gc, constraints, t);
+ VEC_safe_push (constraint_t, heap, constraints, t);
}
}
}
+/* Return true if an access to [ACCESSPOS, ACCESSSIZE]
+ overlaps with a field at [FIELDPOS, FIELDSIZE] */
+
+static bool
+offset_overlaps_with_access (const unsigned HOST_WIDE_INT fieldpos,
+ const unsigned HOST_WIDE_INT fieldsize,
+ const unsigned HOST_WIDE_INT accesspos,
+ const unsigned HOST_WIDE_INT accesssize)
+{
+ if (fieldpos == accesspos && fieldsize == accesssize)
+ return true;
+ if (accesspos >= fieldpos && accesspos < (fieldpos + fieldsize))
+ return true;
+ if (accesspos < fieldpos && (accesspos + accesssize > fieldpos))
+ return true;
+
+ return false;
+}
+
/* Given a COMPONENT_REF T, return the constraint_expr for it. */
static struct constraint_expr
we may have to do something cute here. */
if (result.offset < get_varinfo (result.var)->fullsize)
- result.var = first_vi_for_offset (get_varinfo (result.var),
- result.offset)->id;
+ {
+ /* 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. */
+ varinfo_t curr;
+ for (curr = get_varinfo (result.var); curr; curr = curr->next)
+ {
+ if (offset_overlaps_with_access (curr->offset, curr->size,
+ result.offset, bitsize))
+ {
+ result.var = curr->id;
+ break;
+
+ }
+ }
+ /* assert that we found *some* field there. The user couldn't be
+ accessing *only* padding. */
+
+ gcc_assert (curr);
+ }
else
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Access to past the end of variable, ignoring\n");
&ANYTHING added. */
if (call_expr_flags (t) & (ECF_MALLOC | ECF_MAY_BE_ALLOCA))
{
- tree heapvar = create_tmp_var_raw (ptr_type_node, "HEAP");
+ varinfo_t vi;
+ tree heapvar;
+
+ heapvar = create_tmp_var_raw (ptr_type_node, "HEAP");
+ DECL_EXTERNAL (heapvar) = 1;
+ add_referenced_tmp_var (heapvar);
temp.var = create_variable_info_for (heapvar,
alias_get_name (heapvar));
- get_varinfo (temp.var)->is_artificial_var = 1;
+ vi = get_varinfo (temp.var);
+ vi->is_artificial_var = 1;
+ vi->is_heap_var = 1;
temp.type = ADDRESSOF;
temp.offset = 0;
return temp;
/* Cast from non-pointer to pointers are bad news for us.
Anything else, we see through */
- if (!(POINTER_TYPE_P (TREE_TYPE (t)) &&
- ! POINTER_TYPE_P (TREE_TYPE (op))))
+ if (!(POINTER_TYPE_P (TREE_TYPE (t))
+ && ! POINTER_TYPE_P (TREE_TYPE (op))))
return get_constraint_for (op);
+
+ /* FALLTHRU */
}
default:
{
const unsigned HOST_WIDE_INT size)
{
varinfo_t p = get_varinfo (lhs.var);
- unsigned HOST_WIDE_INT pstart,last;
-
+ unsigned HOST_WIDE_INT pstart, last;
pstart = p->offset;
last = p->offset + size;
for (; p && p->offset < last; p = p->next)
unsigned HOST_WIDE_INT lhssize;
unsigned HOST_WIDE_INT rhssize;
- lhssize = TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (lhsop)));
- rhssize = TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (rhsop)));
lhs = get_constraint_for (lhsop);
rhs = get_constraint_for (rhsop);
rhs = tmp;
}
- /* If the RHS is a special var, set all the LHS fields to that
- special var. */
+ /* This is fairly conservative for the RHS == ADDRESSOF case, in that it's
+ possible it's something we could handle. However, most cases falling
+ into this are dealing with transparent unions, which are slightly
+ weird. */
+ if (rhs.type == ADDRESSOF && rhs.var > integer_id)
+ {
+ rhs.type = ADDRESSOF;
+ rhs.var = anything_id;
+ }
+
+ /* If the RHS is a special var, or an addressof, set all the LHS fields to
+ that special var. */
if (rhs.var <= integer_id)
{
for (p = get_varinfo (lhs.var); p; p = p->next)
}
else
{
+ tree rhstype = TREE_TYPE (rhsop);
+ tree lhstype = TREE_TYPE (lhsop);
+ tree rhstypesize = TYPE_SIZE (rhstype);
+ tree lhstypesize = TYPE_SIZE (lhstype);
+
+ /* If we have a variably sized types on the rhs or lhs, and a deref
+ constraint, add the constraint, lhsconstraint = &ANYTHING.
+ This is conservatively correct because either the lhs is an unknown
+ sized var (if the constraint is SCALAR), or the lhs is a DEREF
+ constraint, and every variable it can point to must be unknown sized
+ anyway, so we don't need to worry about fields at all. */
+ if ((rhs.type == DEREF && TREE_CODE (rhstypesize) != INTEGER_CST)
+ || (lhs.type == DEREF && TREE_CODE (lhstypesize) != INTEGER_CST))
+ {
+ rhs.var = anything_id;
+ rhs.type = ADDRESSOF;
+ rhs.offset = 0;
+ process_constraint (new_constraint (lhs, rhs));
+ return;
+ }
+
+ /* The size only really matters insofar as we don't set more or less of
+ the variable. If we hit an unknown size var, the size should be the
+ whole darn thing. */
+ if (get_varinfo (rhs.var)->is_unknown_size_var)
+ rhssize = ~0;
+ else
+ rhssize = TREE_INT_CST_LOW (rhstypesize);
+
+ if (get_varinfo (lhs.var)->is_unknown_size_var)
+ lhssize = ~0;
+ else
+ lhssize = TREE_INT_CST_LOW (lhstypesize);
+
+
if (rhs.type == SCALAR && lhs.type == SCALAR)
do_simple_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
else if (lhs.type != DEREF && rhs.type == DEREF)
do_lhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
else
{
- tree rhsdecl = get_varinfo (rhs.var)->decl;
- tree pointertype = TREE_TYPE (rhsdecl);
- tree pointedtotype = TREE_TYPE (pointertype);
- tree tmpvar;
+ tree pointedtotype = lhstype;
+ tree tmpvar;
+
gcc_assert (rhs.type == DEREF && lhs.type == DEREF);
tmpvar = create_tmp_var_raw (pointedtotype, "structcopydereftmp");
- lhs = get_constraint_for (tmpvar);
- do_rhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
- rhs = lhs;
- lhs = get_constraint_for (lhsop);
- do_lhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
+ do_structure_copy (tmpvar, rhsop);
+ do_structure_copy (lhsop, tmpvar);
}
}
}
}
-/* Tree walker that is the heart of the aliasing infrastructure.
- TP is a pointer to the current tree.
- WALK_SUBTREES specifies whether to continue traversing subtrees or
- not.
- Returns NULL_TREE when we should stop.
-
- This function is the main part of the constraint builder. It
- walks the trees, calling the appropriate building functions
- to process various statements. */
+/* Update related alias information kept in AI. This is used when
+ building name tags, alias sets and deciding grouping heuristics.
+ STMT is the statement to process. This function also updates
+ ADDRESSABLE_VARS. */
static void
-find_func_aliases (tree t)
+update_alias_info (tree stmt, struct alias_info *ai)
+{
+ bitmap addr_taken;
+ use_operand_p use_p;
+ ssa_op_iter iter;
+ bool stmt_escapes_p = is_escape_site (stmt, ai);
+ tree op;
+
+ /* Mark all the variables whose address are taken by the statement. */
+ addr_taken = addresses_taken (stmt);
+ if (addr_taken)
+ {
+ bitmap_ior_into (addressable_vars, addr_taken);
+
+ /* If STMT is an escape point, all the addresses taken by it are
+ call-clobbered. */
+ if (stmt_escapes_p)
+ {
+ bitmap_iterator bi;
+ unsigned i;
+
+ EXECUTE_IF_SET_IN_BITMAP (addr_taken, 0, i, bi)
+ mark_call_clobbered (referenced_var (i));
+ }
+ }
+
+ /* Process each operand use. If an operand may be aliased, keep
+ track of how many times it's being used. For pointers, determine
+ whether they are dereferenced by the statement, or whether their
+ value escapes, etc. */
+ FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
+ {
+ tree op, var;
+ var_ann_t v_ann;
+ struct ptr_info_def *pi;
+ bool is_store;
+ unsigned num_uses, num_derefs;
+
+ op = USE_FROM_PTR (use_p);
+
+ /* If STMT is a PHI node, OP may be an ADDR_EXPR. If so, add it
+ to the set of addressable variables. */
+ if (TREE_CODE (op) == ADDR_EXPR)
+ {
+ gcc_assert (TREE_CODE (stmt) == PHI_NODE);
+
+ /* PHI nodes don't have annotations for pinning the set
+ of addresses taken, so we collect them here.
+
+ FIXME, should we allow PHI nodes to have annotations
+ so that they can be treated like regular statements?
+ Currently, they are treated as second-class
+ statements. */
+ add_to_addressable_set (TREE_OPERAND (op, 0), &addressable_vars);
+ continue;
+ }
+
+ /* Ignore constants. */
+ if (TREE_CODE (op) != SSA_NAME)
+ continue;
+
+ var = SSA_NAME_VAR (op);
+ v_ann = var_ann (var);
+
+ /* If the operand's variable may be aliased, keep track of how
+ many times we've referenced it. This is used for alias
+ grouping in compute_flow_insensitive_aliasing. */
+ if (may_be_aliased (var))
+ NUM_REFERENCES_INC (v_ann);
+
+ /* We are only interested in pointers. */
+ if (!POINTER_TYPE_P (TREE_TYPE (op)))
+ continue;
+
+ pi = get_ptr_info (op);
+
+ /* Add OP to AI->PROCESSED_PTRS, if it's not there already. */
+ if (!TEST_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (op)))
+ {
+ SET_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (op));
+ VARRAY_PUSH_TREE (ai->processed_ptrs, op);
+ }
+
+ /* If STMT is a PHI node, then it will not have pointer
+ dereferences and it will not be an escape point. */
+ if (TREE_CODE (stmt) == PHI_NODE)
+ continue;
+
+ /* Determine whether OP is a dereferenced pointer, and if STMT
+ is an escape point, whether OP escapes. */
+ count_uses_and_derefs (op, stmt, &num_uses, &num_derefs, &is_store);
+
+ if (num_derefs > 0)
+ {
+ /* Mark OP as dereferenced. In a subsequent pass,
+ dereferenced pointers that point to a set of
+ variables will be assigned a name tag to alias
+ all the variables OP points to. */
+ pi->is_dereferenced = 1;
+
+ /* Keep track of how many time we've dereferenced each
+ pointer. */
+ NUM_REFERENCES_INC (v_ann);
+
+ /* If this is a store operation, mark OP as being
+ dereferenced to store, otherwise mark it as being
+ dereferenced to load. */
+ if (is_store)
+ bitmap_set_bit (ai->dereferenced_ptrs_store, DECL_UID (var));
+ else
+ bitmap_set_bit (ai->dereferenced_ptrs_load, DECL_UID (var));
+ }
+
+ if (stmt_escapes_p && num_derefs < num_uses)
+ {
+ /* If STMT is an escape point and STMT contains at
+ least one direct use of OP, then the value of OP
+ escapes and so the pointed-to variables need to
+ be marked call-clobbered. */
+ pi->value_escapes_p = 1;
+
+ /* If the statement makes a function call, assume
+ that pointer OP will be dereferenced in a store
+ operation inside the called function. */
+ if (get_call_expr_in (stmt))
+ {
+ bitmap_set_bit (ai->dereferenced_ptrs_store, DECL_UID (var));
+ pi->is_dereferenced = 1;
+ }
+ }
+ }
+
+ if (TREE_CODE (stmt) == PHI_NODE)
+ return;
+
+ /* Update reference counter for definitions to any
+ potentially aliased variable. This is used in the alias
+ grouping heuristics. */
+ FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
+ {
+ tree var = SSA_NAME_VAR (op);
+ var_ann_t ann = var_ann (var);
+ bitmap_set_bit (ai->written_vars, DECL_UID (var));
+ if (may_be_aliased (var))
+ NUM_REFERENCES_INC (ann);
+
+ }
+
+ /* Mark variables in V_MAY_DEF operands as being written to. */
+ FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_VIRTUAL_DEFS)
+ {
+ tree var = DECL_P (op) ? op : SSA_NAME_VAR (op);
+ bitmap_set_bit (ai->written_vars, DECL_UID (var));
+ }
+}
+
+
+/* Handle pointer arithmetic EXPR when creating aliasing constraints.
+ Expressions of the type PTR + CST can be handled in two ways:
+
+ 1- If the constraint for PTR is ADDRESSOF for a non-structure
+ variable, then we can use it directly because adding or
+ subtracting a constant may not alter the original ADDRESSOF
+ constraing (i.e., pointer arithmetic may not legally go outside
+ an object's boundaries).
+
+ 2- If the constraint for PTR is ADDRESSOF for a structure variable,
+ then if CST is a compile-time constant that can be used as an
+ offset, we can determine which sub-variable will be pointed-to
+ by the expression.
+
+ Return true if the expression is handled. For any other kind of
+ expression, return false so that each operand can be added as a
+ separate constraint by the caller. */
+
+static bool
+handle_ptr_arith (struct constraint_expr lhs, tree expr)
+{
+ tree op0, op1;
+ struct constraint_expr base, offset;
+
+ if (TREE_CODE (expr) != PLUS_EXPR)
+ return false;
+
+ op0 = TREE_OPERAND (expr, 0);
+ op1 = TREE_OPERAND (expr, 1);
+
+ base = get_constraint_for (op0);
+
+ offset.var = anyoffset_id;
+ offset.type = ADDRESSOF;
+ offset.offset = 0;
+
+ process_constraint (new_constraint (lhs, base));
+ process_constraint (new_constraint (lhs, offset));
+
+ return true;
+}
+
+
+/* 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 (tree t, struct alias_info *ai)
{
struct constraint_expr lhs, rhs;
- switch (TREE_CODE (t))
- {
- case PHI_NODE:
- {
- int i;
- /* Only care about pointers and structures containing
- pointers. */
- if (POINTER_TYPE_P (TREE_TYPE (PHI_RESULT (t)))
- || AGGREGATE_TYPE_P (TREE_TYPE (PHI_RESULT (t))))
- {
- lhs = get_constraint_for (PHI_RESULT (t));
- for (i = 0; i < PHI_NUM_ARGS (t); i++)
- {
- rhs = get_constraint_for (PHI_ARG_DEF (t, i));
- process_constraint (new_constraint (lhs, rhs));
- }
- }
- }
- break;
+ /* Update various related attributes like escaped addresses, pointer
+ dereferences for loads and stores. This is used when creating
+ name tags and alias sets. */
+ update_alias_info (t, ai);
- case MODIFY_EXPR:
- {
- tree lhsop = TREE_OPERAND (t, 0);
- tree rhsop = TREE_OPERAND (t, 1);
- int i;
+ /* Now build constraints expressions. */
+ if (TREE_CODE (t) == PHI_NODE)
+ {
+ /* Only care about pointers and structures containing
+ pointers. */
+ if (POINTER_TYPE_P (TREE_TYPE (PHI_RESULT (t)))
+ || AGGREGATE_TYPE_P (TREE_TYPE (PHI_RESULT (t))))
+ {
+ int i;
- if (AGGREGATE_TYPE_P (TREE_TYPE (lhsop))
- && AGGREGATE_TYPE_P (TREE_TYPE (rhsop)))
- {
- do_structure_copy (lhsop, rhsop);
- }
- else
- {
- /* Only care about operations with pointers, structures
- containing pointers, dereferences, and call
- expressions. */
- if (POINTER_TYPE_P (TREE_TYPE (lhsop))
- || AGGREGATE_TYPE_P (TREE_TYPE (lhsop))
- || ref_contains_indirect_ref (lhsop)
- || TREE_CODE (rhsop) == CALL_EXPR)
- {
- lhs = get_constraint_for (lhsop);
- switch (TREE_CODE_CLASS (TREE_CODE (rhsop)))
- {
- /* RHS that consist of unary operations,
- exceptional types, or bare decls/constants, get
- handled directly by get_constraint_for. */
+ lhs = get_constraint_for (PHI_RESULT (t));
+ for (i = 0; i < PHI_NUM_ARGS (t); i++)
+ {
+ rhs = get_constraint_for (PHI_ARG_DEF (t, i));
+ process_constraint (new_constraint (lhs, rhs));
+ }
+ }
+ }
+ else if (TREE_CODE (t) == MODIFY_EXPR)
+ {
+ tree lhsop = TREE_OPERAND (t, 0);
+ tree rhsop = TREE_OPERAND (t, 1);
+ int i;
+
+ if (AGGREGATE_TYPE_P (TREE_TYPE (lhsop))
+ && AGGREGATE_TYPE_P (TREE_TYPE (rhsop)))
+ {
+ do_structure_copy (lhsop, rhsop);
+ }
+ else
+ {
+ /* Only care about operations with pointers, structures
+ containing pointers, dereferences, and call expressions. */
+ if (POINTER_TYPE_P (TREE_TYPE (lhsop))
+ || AGGREGATE_TYPE_P (TREE_TYPE (lhsop))
+ || ref_contains_indirect_ref (lhsop)
+ || TREE_CODE (rhsop) == CALL_EXPR)
+ {
+ lhs = get_constraint_for (lhsop);
+ switch (TREE_CODE_CLASS (TREE_CODE (rhsop)))
+ {
+ /* RHS that consist of unary operations,
+ exceptional types, or bare decls/constants, get
+ handled directly by get_constraint_for. */
case tcc_reference:
case tcc_declaration:
case tcc_constant:
case tcc_exceptional:
case tcc_expression:
case tcc_unary:
- {
- rhs = get_constraint_for (rhsop);
- process_constraint (new_constraint (lhs, rhs));
- }
+ {
+ rhs = get_constraint_for (rhsop);
+ process_constraint (new_constraint (lhs, rhs));
+
+ /* When taking the address of an aggregate
+ type, from the LHS we can access any field
+ of the RHS. */
+ if (rhs.type == ADDRESSOF
+ && rhs.var > anything_id
+ && AGGREGATE_TYPE_P (TREE_TYPE (TREE_TYPE (rhsop))))
+ {
+ rhs.var = anyoffset_id;
+ rhs.type = ADDRESSOF;
+ rhs.offset = 0;
+ process_constraint (new_constraint (lhs, rhs));
+ }
+ }
break;
- /* Otherwise, walk each operand. */
+ case tcc_binary:
+ {
+ /* For pointer arithmetic of the form
+ PTR + CST, we can simply use PTR's
+ constraint because pointer arithmetic is
+ not allowed to go out of bounds. */
+ if (handle_ptr_arith (lhs, rhsop))
+ break;
+ }
+ /* FALLTHRU */
+
+ /* Otherwise, walk each operand. Notice that we
+ can't use the operand interface because we need
+ to process expressions other than simple operands
+ (e.g. INDIRECT_REF, ADDR_EXPR, CALL_EXPR). */
default:
for (i = 0; i < TREE_CODE_LENGTH (TREE_CODE (rhsop)); i++)
{
rhs = get_constraint_for (op);
process_constraint (new_constraint (lhs, rhs));
}
- }
- }
- }
- }
- break;
-
- default:
- break;
+ }
+ }
+ }
}
+
+ /* After promoting variables and computing aliasing we will
+ need to re-scan most statements. FIXME: Try to minimize the
+ number of statements re-scanned. It's not really necessary to
+ re-scan *all* statements. */
+ mark_stmt_modified (t);
}
tree decltype = TREE_TYPE (decl);
bool notokay = false;
bool hasunion;
- subvar_t svars;
bool is_global = DECL_P (decl) ? is_global_var (decl) : false;
VEC (fieldoff_s,heap) *fieldstack = NULL;
- hasunion = TREE_CODE (decltype) == UNION_TYPE || TREE_CODE (decltype) == QUAL_UNION_TYPE;
+ hasunion = TREE_CODE (decltype) == UNION_TYPE
+ || TREE_CODE (decltype) == QUAL_UNION_TYPE;
if (var_can_have_subvars (decl) && use_field_sensitive && !hasunion)
{
push_fields_onto_fieldstack (decltype, &fieldstack, 0, &hasunion);
notokay = true;
}
}
-
- /* If this variable already has subvars, just create the variables for the
- subvars and we are done.
- NOTE: This assumes things haven't generated uses of previously
- unused structure fields. */
- if (use_field_sensitive
- && !notokay
- && var_can_have_subvars (decl)
- && var_ann (decl)
- && (svars = get_subvars_for_var (decl)))
- {
- subvar_t sv;
- varinfo_t base = NULL;
- unsigned int firstindex = index;
-
- for (sv = svars; sv; sv = sv->next)
- {
- /* For debugging purposes, this will print the names of the
- fields as "<var>.<offset>.<size>"
- This is only for debugging purposes. */
-#define PRINT_LONG_NAMES
-#ifdef PRINT_LONG_NAMES
- char *tempname;
- const char *newname;
-
- asprintf (&tempname,
- "%s." HOST_WIDE_INT_PRINT_DEC "." HOST_WIDE_INT_PRINT_DEC,
- alias_get_name (decl), sv->offset, sv->size);
- newname = ggc_strdup (tempname);
- free (tempname);
- vi = new_var_info (sv->var, index, newname, index);
-#else
- vi = new_var_info (sv->var, index, alias_get_name (sv->var), index);
-#endif
- vi->decl = sv->var;
- vi->fullsize = TREE_INT_CST_LOW (TYPE_SIZE (decltype));
- vi->size = sv->size;
- vi->offset = sv->offset;
- if (!base)
- {
- base = vi;
- insert_id_for_tree (decl, index);
- }
- else
- {
- insert_into_field_list (base, vi);
- }
- insert_id_for_tree (sv->var, index);
- VEC_safe_push (varinfo_t, gc, varmap, vi);
- if (is_global)
- make_constraint_to_anything (vi);
- index++;
-
- }
- return firstindex;
- }
/* If the variable doesn't have subvars, we may end up needing to
vi->offset = 0;
vi->has_union = hasunion;
if (!TYPE_SIZE (decltype)
- || TREE_CODE (TYPE_SIZE (decltype)) != INTEGER_CST
+ || TREE_CODE (TYPE_SIZE (decltype)) != INTEGER_CST
|| TREE_CODE (decltype) == ARRAY_TYPE
|| TREE_CODE (decltype) == UNION_TYPE
|| TREE_CODE (decltype) == QUAL_UNION_TYPE)
}
insert_id_for_tree (vi->decl, index);
- VEC_safe_push (varinfo_t, gc, varmap, vi);
+ VEC_safe_push (varinfo_t, heap, varmap, vi);
if (is_global)
make_constraint_to_anything (vi);
}
field = fo->field;
- gcc_assert (bitpos_of_field (field) == 0);
vi->size = TREE_INT_CST_LOW (DECL_SIZE (field));
for (i = 1; VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
{
newvi->size = TREE_INT_CST_LOW (DECL_SIZE (field));
newvi->fullsize = vi->fullsize;
insert_into_field_list (vi, newvi);
- VEC_safe_push (varinfo_t, gc, varmap, newvi);
+ VEC_safe_push (varinfo_t, heap, varmap, newvi);
if (is_global)
make_constraint_to_anything (newvi);
unsigned int i;
bitmap_iterator bi;
- fprintf (file, "%s = {", vi->name);
+ fprintf (file, "%s = { ", vi->name);
EXECUTE_IF_SET_IN_BITMAP (get_varinfo (vi->node)->solution, 0, i, bi)
{
- fprintf (file, "%s,", get_varinfo (i)->name);
+ fprintf (file, "%s ", get_varinfo (i)->name);
}
fprintf (file, "}\n");
}
lhs.type = SCALAR;
lhs.var = create_variable_info_for (t, alias_get_name (t));
- get_varinfo (lhs.var)->is_artificial_var = true;
rhs.var = anything_id;
rhs.type = ADDRESSOF;
rhs.offset = 0;
{
unsigned int i;
bitmap_iterator bi;
+ bool found_anyoffset = false;
+ subvar_t sv;
EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
{
varinfo_t vi = get_varinfo (i);
+
+ /* If we find ANYOFFSET in the solution and the solution
+ includes SFTs for some structure, then all the SFTs in that
+ structure will need to be added to the alias set. */
+ if (vi->id == anyoffset_id)
+ {
+ found_anyoffset = true;
+ continue;
+ }
+
+ /* 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;
- /* Variables containing unions may need to be converted to their
- SFT's, because SFT's can have unions and we cannot. */
if (vi->has_union && get_subvars_for_var (vi->decl) != NULL)
{
- subvar_t svars = get_subvars_for_var (vi->decl);
- subvar_t sv;
- for (sv = svars; sv; sv = sv->next)
- bitmap_set_bit (into, var_ann (sv->var)->uid);
+ /* Variables containing unions may need to be converted to
+ their SFT's, because SFT's can have unions and we cannot. */
+ for (sv = get_subvars_for_var (vi->decl); sv; sv = sv->next)
+ bitmap_set_bit (into, DECL_UID (sv->var));
}
- /* We may end up with labels in the points-to set because people
- take their address, and they are _DECL's. */
else if (TREE_CODE (vi->decl) == VAR_DECL
- || TREE_CODE (vi->decl) == PARM_DECL)
- bitmap_set_bit (into, var_ann (vi->decl)->uid);
-
-
+ || TREE_CODE (vi->decl) == PARM_DECL)
+ {
+ if (found_anyoffset
+ && var_can_have_subvars (vi->decl)
+ && get_subvars_for_var (vi->decl))
+ {
+ /* If ANYOFFSET is in the solution set and VI->DECL is
+ an aggregate variable with sub-variables, then any of
+ the SFTs inside VI->DECL may have been accessed. Add
+ all the sub-vars for VI->DECL. */
+ for (sv = get_subvars_for_var (vi->decl); sv; sv = sv->next)
+ bitmap_set_bit (into, DECL_UID (sv->var));
+ }
+ else if (var_can_have_subvars (vi->decl)
+ && get_subvars_for_var (vi->decl))
+ {
+ /* If VI->DECL is an aggregate for which we created
+ SFTs, add the SFT corresponding to VI->OFFSET. */
+ tree sft = get_subvar_at (vi->decl, vi->offset);
+ bitmap_set_bit (into, DECL_UID (sft));
+ }
+ else
+ {
+ /* Otherwise, just add VI->DECL to the alias set. */
+ bitmap_set_bit (into, DECL_UID (vi->decl));
+ }
+ }
}
}
-static int have_alias_info = false;
+
+
+static bool have_alias_info = false;
/* Given a pointer variable P, fill in its points-to set, or return
false if we can't. */
find_what_p_points_to (tree p)
{
unsigned int id = 0;
+
if (!have_alias_info)
return false;
+
if (lookup_id_for_tree (p, &id))
{
varinfo_t vi = get_varinfo (id);
if (vi->is_artificial_var)
return false;
- /* See if this is a field or a structure */
+ /* See if this is a field or a structure. */
if (vi->size != vi->fullsize)
{
+ /* Nothing currently asks about structure fields directly,
+ but when they do, we need code here to hand back the
+ points-to set. */
if (!var_can_have_subvars (vi->decl)
|| get_subvars_for_var (vi->decl) == NULL)
return false;
- /* Nothing currently asks about structure fields directly, but when
- they do, we need code here to hand back the points-to set. */
}
else
{
variable. */
vi = get_varinfo (vi->node);
- /* Make sure there aren't any artificial vars in the points to set.
- XXX: Note that we need to translate our heap variables to
- something. */
+ /* Translate artificial variables into SSA_NAME_PTR_INFO
+ attributes. */
EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
{
- if (get_varinfo (i)->is_artificial_var)
- return false;
+ varinfo_t vi = get_varinfo (i);
+
+ if (vi->is_artificial_var)
+ {
+ /* FIXME. READONLY should be handled better so that
+ flow insensitive aliasing can disregard writeable
+ aliases. */
+ if (vi->id == nothing_id)
+ pi->pt_null = 1;
+ else if (vi->id == anything_id)
+ pi->pt_anything = 1;
+ else if (vi->id == readonly_id)
+ pi->pt_anything = 1;
+ else if (vi->id == integer_id)
+ pi->pt_anything = 1;
+ else if (vi->is_heap_var)
+ pi->pt_global_mem = 1;
+ }
}
- pi->pt_anything = false;
+
+ if (pi->pt_anything)
+ return false;
+
if (!pi->pt_vars)
pi->pt_vars = BITMAP_GGC_ALLOC ();
+
set_uids_in_ptset (pi->pt_vars, vi->solution);
+
+ if (bitmap_empty_p (pi->pt_vars))
+ pi->pt_vars = NULL;
+
return true;
}
}
+
return false;
}
+
/* Initialize things necessary to perform PTA */
static void
bitmap_obstack_initialize (&ptabitmap_obstack);
}
-/* Dump the points-to information to OUTFILE. */
-static void
+/* Dump points-to information to OUTFILE. */
+
+void
dump_sa_points_to_info (FILE *outfile)
{
-
unsigned int i;
+
+ fprintf (outfile, "\nPoints-to sets\n\n");
+
if (dump_flags & TDF_STATS)
{
fprintf (outfile, "Stats:\n");
- fprintf (outfile, "Total vars:%d\n", stats.total_vars);
- fprintf (outfile, "Statically unified vars:%d\n", stats.unified_vars_static);
- fprintf (outfile, "Collapsed vars:%d\n", stats.collapsed_vars);
- fprintf (outfile, "Dynamically unified vars:%d\n", stats.unified_vars_dynamic);
- fprintf (outfile, "Iterations:%d\n", stats.iterations);
+ fprintf (outfile, "Total vars: %d\n", stats.total_vars);
+ fprintf (outfile, "Statically unified vars: %d\n",
+ stats.unified_vars_static);
+ fprintf (outfile, "Collapsed vars: %d\n", stats.collapsed_vars);
+ fprintf (outfile, "Dynamically unified vars: %d\n",
+ stats.unified_vars_dynamic);
+ fprintf (outfile, "Iterations: %d\n", stats.iterations);
}
+
for (i = 0; i < VEC_length (varinfo_t, varmap); i++)
dump_solution_for_var (outfile, i);
}
+/* Debug points-to information to stderr. */
+
+void
+debug_sa_points_to_info (void)
+{
+ dump_sa_points_to_info (stderr);
+}
+
+
/* Initialize the always-existing constraint variables for NULL
ANYTHING, READONLY, and INTEGER */
var_nothing->size = ~0;
var_nothing->fullsize = ~0;
nothing_id = 0;
- VEC_safe_push (varinfo_t, gc, varmap, var_nothing);
+ VEC_safe_push (varinfo_t, heap, varmap, var_nothing);
/* Create the ANYTHING variable, used to represent that a variable
points to some unknown piece of memory. */
/* Anything points to anything. This makes deref constraints just
work in the presence of linked list and other p = *p type loops,
by saying that *ANYTHING = ANYTHING. */
- VEC_safe_push (varinfo_t, gc, varmap, var_anything);
+ VEC_safe_push (varinfo_t, heap, varmap, var_anything);
lhs.type = SCALAR;
lhs.var = anything_id;
lhs.offset = 0;
rhs.var = anything_id;
rhs.offset = 0;
var_anything->address_taken = true;
- process_constraint (new_constraint (lhs, rhs));
+ /* This specifically does not use process_constraint because
+ process_constraint ignores all anything = anything constraints, since all
+ but this one are redundant. */
+ VEC_safe_push (constraint_t, heap, constraints, new_constraint (lhs, rhs));
/* Create the READONLY variable, used to represent that a variable
points to readonly memory. */
var_readonly->next = NULL;
insert_id_for_tree (readonly_tree, 2);
readonly_id = 2;
- VEC_safe_push (varinfo_t, gc, varmap, var_readonly);
+ VEC_safe_push (varinfo_t, heap, varmap, var_readonly);
/* readonly memory points to anything, in order to make deref
easier. In reality, it points to anything the particular
rhs.type = ADDRESSOF;
rhs.var = anything_id;
rhs.offset = 0;
- var_readonly->address_taken = true;
process_constraint (new_constraint (lhs, rhs));
var_integer->offset = 0;
var_integer->next = NULL;
integer_id = 3;
- VEC_safe_push (varinfo_t, gc, varmap, var_integer);
+ VEC_safe_push (varinfo_t, heap, varmap, var_integer);
+
+ /* *INTEGER = ANYTHING, because we don't know where a dereference of a random
+ integer will point to. */
+ lhs.type = SCALAR;
+ lhs.var = integer_id;
+ lhs.offset = 0;
+ rhs.type = ADDRESSOF;
+ rhs.var = anything_id;
+ rhs.offset = 0;
+ process_constraint (new_constraint (lhs, rhs));
+
+ /* Create the ANYOFFSET variable, used to represent an arbitrary offset
+ inside an object. This is similar to ANYTHING, but less drastic.
+ It means that the pointer can point anywhere inside an object,
+ but not outside of it. */
+ anyoffset_tree = create_tmp_var_raw (void_type_node, "ANYOFFSET");
+ anyoffset_id = 4;
+ var_anyoffset = new_var_info (anyoffset_tree, anyoffset_id, "ANYOFFSET",
+ anyoffset_id);
+ insert_id_for_tree (anyoffset_tree, anyoffset_id);
+ var_anyoffset->is_artificial_var = 1;
+ var_anyoffset->size = ~0;
+ var_anyoffset->offset = 0;
+ var_anyoffset->next = NULL;
+ var_anyoffset->fullsize = ~0;
+ VEC_safe_push (varinfo_t, heap, varmap, var_anyoffset);
+
+ /* ANYOFFSET points to ANYOFFSET. */
+ lhs.type = SCALAR;
+ lhs.var = anyoffset_id;
+ lhs.offset = 0;
+ rhs.type = ADDRESSOF;
+ rhs.var = anyoffset_id;
+ rhs.offset = 0;
+ process_constraint (new_constraint (lhs, rhs));
}
/* Create points-to sets for the current function. See the comments
at the start of the file for an algorithmic overview. */
-static void
-create_alias_vars (void)
+void
+compute_points_to_sets (struct alias_info *ai)
{
basic_block bb;
-
+ timevar_push (TV_TREE_PTA);
+
init_alias_vars ();
constraint_pool = create_alloc_pool ("Constraint pool",
constraint_edge_pool = create_alloc_pool ("Constraint edges",
sizeof (struct constraint_edge), 30);
- constraints = VEC_alloc (constraint_t, gc, 8);
- varmap = VEC_alloc (varinfo_t, gc, 8);
+ constraints = VEC_alloc (constraint_t, heap, 8);
+ varmap = VEC_alloc (varinfo_t, heap, 8);
id_for_tree = htab_create (10, tree_id_hash, tree_id_eq, free);
memset (&stats, 0, sizeof (stats));
-
+
init_base_vars ();
intra_create_variable_infos ();
for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
if (is_gimple_reg (PHI_RESULT (phi)))
- find_func_aliases (phi);
+ find_func_aliases (phi, ai);
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
- find_func_aliases (bsi_stmt (bsi));
+ find_func_aliases (bsi_stmt (bsi), ai);
}
build_constraint_graph ();
if (dump_file)
{
- fprintf (dump_file, "Constraints:\n");
+ fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
dump_constraints (dump_file);
}
if (dump_file)
- fprintf (dump_file, "Collapsing static cycles and doing variable substitution:\n");
+ fprintf (dump_file, "\nCollapsing static cycles and doing variable "
+ "substitution:\n");
find_and_collapse_graph_cycles (graph, false);
perform_var_substitution (graph);
if (dump_file)
- fprintf (dump_file, "Solving graph:\n");
+ fprintf (dump_file, "\nSolving graph:\n");
solve_graph (graph);
dump_sa_points_to_info (dump_file);
have_alias_info = true;
+
+ timevar_pop (TV_TREE_PTA);
}
-struct tree_opt_pass pass_build_pta =
-{
- "pta", /* name */
- NULL, /* gate */
- create_alias_vars, /* execute */
- NULL, /* sub */
- NULL, /* next */
- 0, /* static_pass_number */
- TV_TREE_PTA, /* tv_id */
- PROP_cfg, /* properties_required */
- PROP_pta, /* properties_provided */
- 0, /* properties_destroyed */
- 0, /* todo_flags_start */
- 0, /* todo_flags_finish */
- 0 /* letter */
-};
-
/* Delete created points-to sets. */
-static void
-delete_alias_vars (void)
+void
+delete_points_to_sets (void)
{
+ varinfo_t v;
+ int i;
+
htab_delete (id_for_tree);
+ bitmap_obstack_release (&ptabitmap_obstack);
+ VEC_free (constraint_t, heap, constraints);
+
+ for (i = 0; VEC_iterate (varinfo_t, varmap, i, v); i++)
+ {
+ VEC_free (constraint_edge_t, heap, graph->succs[i]);
+ VEC_free (constraint_edge_t, heap, graph->preds[i]);
+ VEC_free (constraint_t, heap, v->complex);
+ }
+ free (graph->succs);
+ free (graph->preds);
+ free (graph);
+
+ VEC_free (varinfo_t, heap, varmap);
free_alloc_pool (variable_info_pool);
free_alloc_pool (constraint_pool);
free_alloc_pool (constraint_edge_pool);
- bitmap_obstack_release (&ptabitmap_obstack);
+
have_alias_info = false;
}
-
-struct tree_opt_pass pass_del_pta =
-{
- NULL, /* name */
- NULL, /* gate */
- delete_alias_vars, /* execute */
- NULL, /* sub */
- NULL, /* next */
- 0, /* static_pass_number */
- TV_TREE_PTA, /* tv_id */
- PROP_pta, /* properties_required */
- 0, /* properties_provided */
- PROP_pta, /* properties_destroyed */
- 0, /* todo_flags_start */
- 0, /* todo_flags_finish */
- 0 /* letter */
-};
OSDN Git Service
