/* Tree based points-to analysis
- Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012
- Free Software Foundation, Inc.
+ Copyright (C) 2005-2014 Free Software Foundation, Inc.
Contributed by Daniel Berlin <dberlin@dberlin.org>
This file is part of GCC.
#include "system.h"
#include "coretypes.h"
#include "tm.h"
-#include "ggc.h"
#include "obstack.h"
#include "bitmap.h"
+#include "sbitmap.h"
#include "flags.h"
+#include "predict.h"
+#include "vec.h"
+#include "hashtab.h"
+#include "hash-set.h"
+#include "machmode.h"
+#include "hard-reg-set.h"
+#include "input.h"
+#include "function.h"
+#include "dominance.h"
+#include "cfg.h"
#include "basic-block.h"
#include "tree.h"
-#include "tree-flow.h"
-#include "tree-inline.h"
-#include "diagnostic-core.h"
+#include "stor-layout.h"
+#include "stmt.h"
+#include "hash-table.h"
+#include "tree-ssa-alias.h"
+#include "internal-fn.h"
+#include "gimple-expr.h"
+#include "is-a.h"
#include "gimple.h"
-#include "hashtab.h"
-#include "function.h"
+#include "gimple-iterator.h"
+#include "gimple-ssa.h"
+#include "hash-map.h"
+#include "plugin-api.h"
+#include "ipa-ref.h"
#include "cgraph.h"
+#include "stringpool.h"
+#include "tree-ssanames.h"
+#include "tree-into-ssa.h"
+#include "expr.h"
+#include "tree-dfa.h"
+#include "tree-inline.h"
+#include "diagnostic-core.h"
#include "tree-pass.h"
#include "alloc-pool.h"
#include "splay-tree.h"
#include "params.h"
-#include "cgraph.h"
#include "alias.h"
-#include "pointer-set.h"
/* The idea behind this analyzer is to generate set constraints from the
program, then solve the resulting constraints in order to generate the
/* True if this represents a IPA function info. */
unsigned int is_fn_info : 1;
- /* A link to the variable for the next field in this structure. */
- struct variable_info *next;
+ /* The ID of the variable for the next field in this structure
+ or zero for the last field in this structure. */
+ unsigned next;
+
+ /* The ID of the variable for the first field in this structure. */
+ unsigned head;
/* Offset of this variable, in bits, from the base variable */
unsigned HOST_WIDE_INT offset;
/* Pool of variable info structures. */
static alloc_pool variable_info_pool;
-
+/* Map varinfo to final pt_solution. */
+static hash_map<varinfo_t, pt_solution *> *final_solutions;
+struct obstack final_solutions_obstack;
/* Table of variable info structures for constraint variables.
Indexed directly by variable info id. */
return varmap[n];
}
-/* Static IDs for the special variables. */
-enum { nothing_id = 0, anything_id = 1, readonly_id = 2,
- escaped_id = 3, nonlocal_id = 4,
- storedanything_id = 5, integer_id = 6 };
+/* Return the next variable in the list of sub-variables of VI
+ or NULL if VI is the last sub-variable. */
+
+static inline varinfo_t
+vi_next (varinfo_t vi)
+{
+ return get_varinfo (vi->next);
+}
+
+/* Static IDs for the special variables. Variable ID zero is unused
+ and used as terminator for the sub-variable chain. */
+enum { nothing_id = 1, anything_id = 2, string_id = 3,
+ escaped_id = 4, nonlocal_id = 5,
+ storedanything_id = 6, integer_id = 7 };
/* Return a new variable info structure consisting for a variable
named NAME, and using constraint graph node NODE. Append it
&& DECL_HARD_REGISTER (t)));
ret->solution = BITMAP_ALLOC (&pta_obstack);
ret->oldsolution = NULL;
- ret->next = NULL;
+ ret->next = 0;
+ ret->head = ret->id;
stats.total_vars++;
/* A map mapping call statements to per-stmt variables for uses
and clobbers specific to the call. */
-struct pointer_map_t *call_stmt_vars;
+static hash_map<gimple, varinfo_t> *call_stmt_vars;
/* Lookup or create the variable for the call statement CALL. */
static varinfo_t
get_call_vi (gimple call)
{
- void **slot_p;
varinfo_t vi, vi2;
- slot_p = pointer_map_insert (call_stmt_vars, call);
- if (*slot_p)
- return (varinfo_t) *slot_p;
+ bool existed;
+ varinfo_t *slot_p = &call_stmt_vars->get_or_insert (call, &existed);
+ if (existed)
+ return *slot_p;
vi = new_var_info (NULL_TREE, "CALLUSED");
vi->offset = 0;
vi->fullsize = 2;
vi->is_full_var = true;
- vi->next = vi2 = new_var_info (NULL_TREE, "CALLCLOBBERED");
+ vi2 = new_var_info (NULL_TREE, "CALLCLOBBERED");
vi2->offset = 1;
vi2->size = 1;
vi2->fullsize = 2;
vi2->is_full_var = true;
- *slot_p = (void *) vi;
+ vi->next = vi2->id;
+
+ *slot_p = vi;
return vi;
}
static varinfo_t
lookup_call_use_vi (gimple call)
{
- void **slot_p;
-
- slot_p = pointer_map_contains (call_stmt_vars, call);
+ varinfo_t *slot_p = call_stmt_vars->get (call);
if (slot_p)
- return (varinfo_t) *slot_p;
+ return *slot_p;
return NULL;
}
if (!uses)
return NULL;
- return uses->next;
+ return vi_next (uses);
}
/* Lookup or create the variable for the call statement CALL representing
static varinfo_t ATTRIBUTE_UNUSED
get_call_clobber_vi (gimple call)
{
- return get_call_vi (call)->next;
+ return vi_next (get_call_vi (call));
}
};
/* Use 0x8000... as special unknown offset. */
-#define UNKNOWN_OFFSET ((HOST_WIDE_INT)-1 << (HOST_BITS_PER_WIDE_INT-1))
+#define UNKNOWN_OFFSET HOST_WIDE_INT_MIN
typedef struct constraint_expr ce_s;
static void get_constraint_for_1 (tree, vec<ce_s> *, bool, bool);
static unsigned int
find (unsigned int node)
{
- gcc_assert (node < graph->size);
+ gcc_checking_assert (node < graph->size);
if (graph->rep[node] != node)
return graph->rep[node] = find (graph->rep[node]);
return node;
static bool
unite (unsigned int to, unsigned int from)
{
- gcc_assert (to < graph->size && from < graph->size);
+ gcc_checking_assert (to < graph->size && from < graph->size);
if (to != from && graph->rep[from] != to)
{
graph->rep[from] = to;
/* The next lines print the nodes in the graph together with the
complex constraints attached to them. */
- for (i = 0; i < graph->size; i++)
+ for (i = 1; i < graph->size; i++)
{
+ if (i == FIRST_REF_NODE)
+ continue;
if (find (i) != i)
continue;
if (i < FIRST_REF_NODE)
/* Go over the edges. */
fprintf (file, "\n // Edges in the constraint graph:\n");
- for (i = 0; i < graph->size; i++)
+ for (i = 1; i < graph->size; i++)
{
unsigned j;
bitmap_iterator bi;
return found;
}
-/* Union two constraint vectors, TO and FROM. Put the result in TO. */
+/* Union two constraint vectors, TO and FROM. Put the result in TO.
+ Returns true of TO set is changed. */
-static void
+static bool
constraint_set_union (vec<constraint_t> *to,
vec<constraint_t> *from)
{
int i;
constraint_t c;
+ bool any_change = false;
FOR_EACH_VEC_ELT (*from, i, c)
{
{
unsigned int place = to->lower_bound (c, constraint_less);
to->safe_insert (place, c);
+ any_change = true;
}
}
+ return any_change;
}
-/* Expands the solution in SET to all sub-fields of variables included.
- Union the expanded result into RESULT. */
+/* Expands the solution in SET to all sub-fields of variables included. */
-static void
-solution_set_expand (bitmap result, bitmap set)
+static bitmap
+solution_set_expand (bitmap set, bitmap *expanded)
{
bitmap_iterator bi;
- bitmap vars = NULL;
unsigned j;
- /* In a first pass record all variables we need to add all
- sub-fields off. This avoids quadratic behavior. */
+ if (*expanded)
+ return *expanded;
+
+ *expanded = BITMAP_ALLOC (&iteration_obstack);
+
+ /* In a first pass expand to the head of the variables we need to
+ add all sub-fields off. This avoids quadratic behavior. */
EXECUTE_IF_SET_IN_BITMAP (set, 0, j, bi)
{
varinfo_t v = get_varinfo (j);
if (v->is_artificial_var
|| v->is_full_var)
continue;
- v = lookup_vi_for_tree (v->decl);
- if (vars == NULL)
- vars = BITMAP_ALLOC (NULL);
- bitmap_set_bit (vars, v->id);
+ bitmap_set_bit (*expanded, v->head);
}
- /* 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)
+ /* In the second pass now expand all head variables with subfields. */
+ EXECUTE_IF_SET_IN_BITMAP (*expanded, 0, j, bi)
{
- EXECUTE_IF_SET_IN_BITMAP (vars, 0, j, bi)
- {
- varinfo_t v = get_varinfo (j);
- for (; v != NULL; v = v->next)
- bitmap_set_bit (result, v->id);
- }
- BITMAP_FREE (vars);
+ varinfo_t v = get_varinfo (j);
+ if (v->head != j)
+ continue;
+ for (v = vi_next (v); v != NULL; v = vi_next (v))
+ bitmap_set_bit (*expanded, v->id);
}
+
+ /* And finally set the rest of the bits from SET. */
+ bitmap_ior_into (*expanded, set);
+
+ return *expanded;
}
-/* Take a solution set SET, add OFFSET to each member of the set, and
- overwrite SET with the result when done. */
+/* Union solution sets TO and DELTA, and add INC to each member of DELTA in the
+ process. */
-static void
-solution_set_add (bitmap set, HOST_WIDE_INT offset)
+static bool
+set_union_with_increment (bitmap to, bitmap delta, HOST_WIDE_INT inc,
+ bitmap *expanded_delta)
{
- bitmap result = BITMAP_ALLOC (&iteration_obstack);
- unsigned int i;
+ bool changed = false;
bitmap_iterator bi;
+ unsigned int i;
+
+ /* If the solution of DELTA contains anything it is good enough to transfer
+ this to TO. */
+ if (bitmap_bit_p (delta, anything_id))
+ return bitmap_set_bit (to, anything_id);
/* If the offset is unknown we have to expand the solution to
all subfields. */
- if (offset == UNKNOWN_OFFSET)
+ if (inc == UNKNOWN_OFFSET)
{
- solution_set_expand (set, set);
- return;
+ delta = solution_set_expand (delta, expanded_delta);
+ changed |= bitmap_ior_into (to, delta);
+ return changed;
}
- EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
+ /* For non-zero offset union the offsetted solution into the destination. */
+ EXECUTE_IF_SET_IN_BITMAP (delta, 0, i, bi)
{
varinfo_t vi = get_varinfo (i);
if (vi->is_artificial_var
|| vi->is_unknown_size_var
|| vi->is_full_var)
- bitmap_set_bit (result, i);
+ changed |= bitmap_set_bit (to, i);
else
{
- unsigned HOST_WIDE_INT fieldoffset = vi->offset + offset;
+ HOST_WIDE_INT fieldoffset = vi->offset + inc;
+ unsigned HOST_WIDE_INT size = vi->size;
/* If the offset makes the pointer point to before the
variable use offset zero for the field lookup. */
- if (offset < 0
- && fieldoffset > vi->offset)
- fieldoffset = 0;
-
- if (offset != 0)
+ if (fieldoffset < 0)
+ vi = get_varinfo (vi->head);
+ else
vi = first_or_preceding_vi_for_offset (vi, fieldoffset);
- bitmap_set_bit (result, vi->id);
- /* If the result is not exactly at fieldoffset include the next
- field as well. See get_constraint_for_ptr_offset for more
- rationale. */
- if (vi->offset != fieldoffset
- && vi->next != NULL)
- bitmap_set_bit (result, vi->next->id);
+ do
+ {
+ changed |= bitmap_set_bit (to, vi->id);
+ if (vi->is_full_var
+ || vi->next == 0)
+ break;
+
+ /* We have to include all fields that overlap the current field
+ shifted by inc. */
+ vi = vi_next (vi);
+ }
+ while (vi->offset < fieldoffset + size);
}
}
- bitmap_copy (set, result);
- BITMAP_FREE (result);
-}
-
-/* Union solution sets TO and FROM, and add INC to each member of FROM in the
- process. */
-
-static bool
-set_union_with_increment (bitmap to, bitmap from, HOST_WIDE_INT inc)
-{
- if (inc == 0)
- return bitmap_ior_into (to, from);
- else
- {
- bitmap tmp;
- bool res;
-
- tmp = BITMAP_ALLOC (&iteration_obstack);
- bitmap_copy (tmp, from);
- solution_set_add (tmp, inc);
- res = bitmap_ior_into (to, tmp);
- BITMAP_FREE (tmp);
- return res;
- }
+ return changed;
}
/* Insert constraint C into the list of complex constraints for graph
/* Condense two variable nodes into a single variable node, by moving
- all associated info from SRC to TO. */
+ all associated info from FROM to TO. Returns true if TO node's
+ constraint set changes after the merge. */
-static void
+static bool
merge_node_constraints (constraint_graph_t graph, unsigned int to,
unsigned int from)
{
unsigned int i;
constraint_t c;
+ bool any_change = false;
- gcc_assert (find (from) == to);
+ gcc_checking_assert (find (from) == to);
/* Move all complex constraints from src node into to node */
FOR_EACH_VEC_ELT (graph->complex[from], i, c)
{
- /* In complex constraints for node src, we may have either
- a = *src, and *src = a, or an offseted constraint which are
+ /* In complex constraints for node FROM, we may have either
+ a = *FROM, and *FROM = a, or an offseted constraint which are
always added to the rhs node's constraints. */
if (c->rhs.type == DEREF)
c->lhs.var = to;
else
c->rhs.var = to;
+
}
- constraint_set_union (&graph->complex[to], &graph->complex[from]);
+ any_change = constraint_set_union (&graph->complex[to],
+ &graph->complex[from]);
graph->complex[from].release ();
+ return any_change;
}
}
-/* 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
graph->address_taken = BITMAP_ALLOC (&predbitmap_obstack);
bitmap_clear (graph->direct_nodes);
- for (j = 0; j < FIRST_REF_NODE; j++)
+ for (j = 1; j < FIRST_REF_NODE; j++)
{
if (!get_varinfo (j)->is_special_var)
bitmap_set_bit (graph->direct_nodes, j);
v = get_varinfo (rhsvar);
if (!v->is_full_var)
{
- v = lookup_vi_for_tree (v->decl);
+ v = get_varinfo (v->head);
do
{
bitmap_clear_bit (graph->direct_nodes, v->id);
- v = v->next;
+ v = vi_next (v);
}
while (v != NULL);
}
else if (rhs.type == ADDRESSOF)
{
/* x = &y */
- gcc_assert (find (rhs.var) == rhs.var);
+ gcc_checking_assert (find (rhs.var) == rhs.var);
bitmap_set_bit (get_varinfo (lhsvar)->solution, rhsvar);
}
else if (lhsvar > anything_id
if (!bitmap_bit_p (si->visited, w))
scc_visit (graph, si, w);
- {
- unsigned int t = find (w);
- unsigned int nnode = find (n);
- gcc_assert (nnode == n);
- if (si->dfs[t] < si->dfs[nnode])
- si->dfs[n] = si->dfs[t];
- }
+ unsigned int t = find (w);
+ gcc_checking_assert (find (n) == n);
+ if (si->dfs[t] < si->dfs[n])
+ si->dfs[n] = si->dfs[t];
}
/* See if any components have been identified. */
unify_nodes (constraint_graph_t graph, unsigned int to, unsigned int from,
bool update_changed)
{
+ gcc_checking_assert (to != from && find (to) == to);
- 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,
stats.unified_vars_static++;
merge_graph_nodes (graph, to, from);
- merge_node_constraints (graph, to, from);
+ if (merge_node_constraints (graph, to, from))
+ {
+ if (update_changed)
+ bitmap_set_bit (changed, to);
+ }
/* Mark TO as changed if FROM was changed. If TO was already marked
as changed, decrease the changed count. */
if (update_changed
- && bitmap_bit_p (changed, from))
- {
- bitmap_clear_bit (changed, from);
- bitmap_set_bit (changed, to);
- }
- if (get_varinfo (from)->solution)
+ && bitmap_clear_bit (changed, from))
+ bitmap_set_bit (changed, to);
+ varinfo_t fromvi = get_varinfo (from);
+ if (fromvi->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))
+ varinfo_t tovi = get_varinfo (to);
+ if (bitmap_ior_into (tovi->solution, fromvi->solution))
{
if (update_changed)
bitmap_set_bit (changed, to);
}
- BITMAP_FREE (get_varinfo (from)->solution);
- if (get_varinfo (from)->oldsolution)
- BITMAP_FREE (get_varinfo (from)->oldsolution);
+ BITMAP_FREE (fromvi->solution);
+ if (fromvi->oldsolution)
+ BITMAP_FREE (fromvi->oldsolution);
if (stats.iterations > 0
- && get_varinfo (to)->oldsolution)
- BITMAP_FREE (get_varinfo (to)->oldsolution);
- }
- if (valid_graph_edge (graph, to, to))
- {
- if (graph->succs[to])
- bitmap_clear_bit (graph->succs[to], to);
+ && tovi->oldsolution)
+ BITMAP_FREE (tovi->oldsolution);
}
+ if (graph->succs[to])
+ bitmap_clear_bit (graph->succs[to], to);
}
/* Information needed to compute the topological ordering of a graph. */
static void
do_sd_constraint (constraint_graph_t graph, constraint_t c,
- bitmap delta)
+ bitmap delta, bitmap *expanded_delta)
{
unsigned int lhs = c->lhs.var;
bool flag = false;
HOST_WIDE_INT roffset = c->rhs.offset;
/* Our IL does not allow this. */
- gcc_assert (c->lhs.offset == 0);
+ gcc_checking_assert (c->lhs.offset == 0);
/* If the solution of Y contains anything it is good enough to transfer
this to the LHS. */
dereferenced at all valid offsets. */
if (roffset == UNKNOWN_OFFSET)
{
- solution_set_expand (delta, delta);
+ delta = solution_set_expand (delta, expanded_delta);
/* No further offset processing is necessary. */
roffset = 0;
}
{
varinfo_t v = get_varinfo (j);
HOST_WIDE_INT fieldoffset = v->offset + roffset;
+ unsigned HOST_WIDE_INT size = v->size;
unsigned int t;
if (v->is_full_var)
- fieldoffset = v->offset;
+ ;
else if (roffset != 0)
- v = first_vi_for_offset (v, fieldoffset);
- /* If the access is outside of the variable we can ignore it. */
- if (!v)
- continue;
+ {
+ if (fieldoffset < 0)
+ v = get_varinfo (v->head);
+ else
+ v = first_or_preceding_vi_for_offset (v, fieldoffset);
+ }
+ /* We have to include all fields that overlap the current field
+ shifted by roffset. */
do
{
t = find (v->id);
&& add_graph_edge (graph, lhs, t))
flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
- /* If the variable is not exactly at the requested offset
- we have to include the next one. */
- if (v->offset == (unsigned HOST_WIDE_INT)fieldoffset
- || v->next == NULL)
+ if (v->is_full_var
+ || v->next == 0)
break;
- v = v->next;
- fieldoffset = v->offset;
+ v = vi_next (v);
}
- while (1);
+ while (v->offset < fieldoffset + size);
}
done:
as the starting solution for x. */
static void
-do_ds_constraint (constraint_t c, bitmap delta)
+do_ds_constraint (constraint_t c, bitmap delta, bitmap *expanded_delta)
{
unsigned int rhs = c->rhs.var;
bitmap sol = get_varinfo (rhs)->solution;
bool escaped_p = false;
/* Our IL does not allow this. */
- gcc_assert (c->rhs.offset == 0);
+ gcc_checking_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. */
dereferenced at all valid offsets. */
if (loff == UNKNOWN_OFFSET)
{
- solution_set_expand (delta, delta);
+ delta = solution_set_expand (delta, expanded_delta);
loff = 0;
}
varinfo_t v = get_varinfo (j);
unsigned int t;
HOST_WIDE_INT fieldoffset = v->offset + loff;
+ unsigned HOST_WIDE_INT size = v->size;
if (v->is_full_var)
- fieldoffset = v->offset;
+ ;
else if (loff != 0)
- v = first_vi_for_offset (v, fieldoffset);
- /* If the access is outside of the variable we can ignore it. */
- if (!v)
- continue;
+ {
+ if (fieldoffset < 0)
+ v = get_varinfo (v->head);
+ else
+ v = first_or_preceding_vi_for_offset (v, fieldoffset);
+ }
+ /* We have to include all fields that overlap the current field
+ shifted by loff. */
do
{
if (v->may_have_pointers)
bitmap_set_bit (changed, t);
}
- /* If the variable is not exactly at the requested offset
- we have to include the next one. */
- if (v->offset == (unsigned HOST_WIDE_INT)fieldoffset
- || v->next == NULL)
+ if (v->is_full_var
+ || v->next == 0)
break;
- v = v->next;
- fieldoffset = v->offset;
+ v = vi_next (v);
}
- while (1);
+ while (v->offset < fieldoffset + size);
}
}
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)
+do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta,
+ bitmap *expanded_delta)
{
if (c->lhs.type == DEREF)
{
if (c->rhs.type == ADDRESSOF)
{
- gcc_unreachable();
+ gcc_unreachable ();
}
else
{
/* *x = y */
- do_ds_constraint (c, delta);
+ do_ds_constraint (c, delta, expanded_delta);
}
}
else if (c->rhs.type == DEREF)
{
/* x = *y */
if (!(get_varinfo (c->lhs.var)->is_special_var))
- do_sd_constraint (graph, c, delta);
+ do_sd_constraint (graph, c, delta, expanded_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;
+ gcc_checking_assert (c->rhs.type == SCALAR && c->lhs.type == SCALAR
+ && c->rhs.offset != 0 && c->lhs.offset == 0);
tmp = get_varinfo (c->lhs.var)->solution;
- flag = set_union_with_increment (tmp, solution, c->rhs.offset);
+ flag = set_union_with_increment (tmp, delta, c->rhs.offset,
+ expanded_delta);
if (flag)
- {
- get_varinfo (c->lhs.var)->solution = tmp;
- bitmap_set_bit (changed, c->lhs.var);
- }
+ bitmap_set_bit (changed, c->lhs.var);
}
}
} *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;
+/* Equiv_class_label hashtable helpers. */
-/* A hashtable for mapping a bitmap of labels->location equivalence
- classes. */
-static htab_t location_equiv_class_table;
+struct equiv_class_hasher : typed_free_remove <equiv_class_label>
+{
+ typedef equiv_class_label value_type;
+ typedef equiv_class_label compare_type;
+ static inline hashval_t hash (const value_type *);
+ static inline bool equal (const value_type *, const compare_type *);
+};
/* Hash function for a equiv_class_label_t */
-static hashval_t
-equiv_class_label_hash (const void *p)
+inline hashval_t
+equiv_class_hasher::hash (const value_type *ecl)
{
- 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)
+inline bool
+equiv_class_hasher::equal (const value_type *eql1, const compare_type *eql2)
{
- const_equiv_class_label_t const eql1 = (const_equiv_class_label_t) p1;
- const_equiv_class_label_t const eql2 = (const_equiv_class_label_t) p2;
return (eql1->hashcode == eql2->hashcode
&& bitmap_equal_p (eql1->labels, eql2->labels));
}
-/* Lookup a equivalence class in TABLE by the bitmap of LABELS it
- contains. */
+/* A hashtable for mapping a bitmap of labels->pointer equivalence
+ classes. */
+static hash_table<equiv_class_hasher> *pointer_equiv_class_table;
+
+/* A hashtable for mapping a bitmap of labels->location equivalence
+ classes. */
+static hash_table<equiv_class_hasher> *location_equiv_class_table;
+
+/* Lookup a equivalence class in TABLE by the bitmap of LABELS with
+ hash HAS it contains. Sets *REF_LABELS to the bitmap LABELS
+ is equivalent to. */
-static unsigned int
-equiv_class_lookup (htab_t table, bitmap labels)
+static equiv_class_label *
+equiv_class_lookup_or_add (hash_table<equiv_class_hasher> *table,
+ bitmap labels)
{
- void **slot;
- struct equiv_class_label ecl;
+ equiv_class_label **slot;
+ equiv_class_label ecl;
ecl.labels = labels;
ecl.hashcode = bitmap_hash (labels);
+ slot = table->find_slot (&ecl, INSERT);
+ if (!*slot)
+ {
+ *slot = XNEW (struct equiv_class_label);
+ (*slot)->labels = labels;
+ (*slot)->hashcode = ecl.hashcode;
+ (*slot)->equivalence_class = 0;
+ }
- 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;
+ return *slot;
}
/* Perform offline variable substitution.
bitmap_iterator bi;
unsigned int my_dfs;
- gcc_assert (si->node_mapping[n] == n);
+ gcc_checking_assert (si->node_mapping[n] == n);
bitmap_set_bit (si->visited, n);
si->dfs[n] = si->current_index ++;
my_dfs = si->dfs[n];
if (!bitmap_bit_p (si->visited, w))
condense_visit (graph, si, w);
- {
- unsigned int t = si->node_mapping[w];
- unsigned int nnode = si->node_mapping[n];
- gcc_assert (nnode == n);
- if (si->dfs[t] < si->dfs[nnode])
- si->dfs[n] = si->dfs[t];
- }
+ unsigned int t = si->node_mapping[w];
+ gcc_checking_assert (si->node_mapping[n] == n);
+ if (si->dfs[t] < si->dfs[n])
+ si->dfs[n] = si->dfs[t];
}
/* Visit all the implicit predecessors. */
if (!bitmap_bit_p (si->visited, w))
condense_visit (graph, si, w);
- {
- unsigned int t = si->node_mapping[w];
- unsigned int nnode = si->node_mapping[n];
- gcc_assert (nnode == n);
- if (si->dfs[t] < si->dfs[nnode])
- si->dfs[n] = si->dfs[t];
- }
+ unsigned int t = si->node_mapping[w];
+ gcc_assert (si->node_mapping[n] == n);
+ if (si->dfs[t] < si->dfs[n])
+ si->dfs[n] = si->dfs[t];
}
/* See if any components have been identified. */
si->scc_stack.safe_push (n);
}
-/* Label pointer equivalences. */
+/* Label pointer equivalences.
+
+ This performs a value numbering of the constraint graph to
+ discover which variables will always have the same points-to sets
+ under the current set of constraints.
+
+ The way it value numbers is to store the set of points-to bits
+ generated by the constraints and graph edges. This is just used as a
+ hash and equality comparison. The *actual set of points-to bits* is
+ completely irrelevant, in that we don't care about being able to
+ extract them later.
+
+ The equality values (currently bitmaps) just have to satisfy a few
+ constraints, the main ones being:
+ 1. The combining operation must be order independent.
+ 2. The end result of a given set of operations must be unique iff the
+ combination of input values is unique
+ 3. Hashable. */
static void
label_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
{
- unsigned int i;
+ unsigned int i, first_pred;
bitmap_iterator bi;
- bitmap_set_bit (si->visited, n);
- if (!graph->points_to[n])
- graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
+ bitmap_set_bit (si->visited, n);
/* Label and union our incoming edges's points to sets. */
+ first_pred = -1U;
EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
{
unsigned int w = si->node_mapping[i];
continue;
if (graph->points_to[w])
- bitmap_ior_into(graph->points_to[n], graph->points_to[w]);
+ {
+ if (!graph->points_to[n])
+ {
+ if (first_pred == -1U)
+ first_pred = w;
+ else
+ {
+ graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
+ bitmap_ior (graph->points_to[n],
+ graph->points_to[first_pred],
+ graph->points_to[w]);
+ }
+ }
+ else
+ bitmap_ior_into (graph->points_to[n], graph->points_to[w]);
+ }
}
- /* Indirect nodes get fresh variables. */
+
+ /* Indirect nodes get fresh variables and a new pointer equiv class. */
if (!bitmap_bit_p (graph->direct_nodes, n))
- bitmap_set_bit (graph->points_to[n], FIRST_REF_NODE + n);
+ {
+ if (!graph->points_to[n])
+ {
+ graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
+ if (first_pred != -1U)
+ bitmap_copy (graph->points_to[n], graph->points_to[first_pred]);
+ }
+ bitmap_set_bit (graph->points_to[n], FIRST_REF_NODE + n);
+ graph->pointer_label[n] = pointer_equiv_class++;
+ equiv_class_label_t ecl;
+ ecl = equiv_class_lookup_or_add (pointer_equiv_class_table,
+ graph->points_to[n]);
+ ecl->equivalence_class = graph->pointer_label[n];
+ return;
+ }
+
+ /* If there was only a single non-empty predecessor the pointer equiv
+ class is the same. */
+ if (!graph->points_to[n])
+ {
+ if (first_pred != -1U)
+ {
+ graph->pointer_label[n] = graph->pointer_label[first_pred];
+ graph->points_to[n] = graph->points_to[first_pred];
+ }
+ return;
+ }
if (!bitmap_empty_p (graph->points_to[n]))
{
- unsigned int label = equiv_class_lookup (pointer_equiv_class_table,
- graph->points_to[n]);
- if (!label)
+ equiv_class_label_t ecl;
+ ecl = equiv_class_lookup_or_add (pointer_equiv_class_table,
+ graph->points_to[n]);
+ if (ecl->equivalence_class == 0)
+ ecl->equivalence_class = pointer_equiv_class++;
+ else
+ {
+ BITMAP_FREE (graph->points_to[n]);
+ graph->points_to[n] = ecl->labels;
+ }
+ graph->pointer_label[n] = ecl->equivalence_class;
+ }
+}
+
+/* Print the pred graph in dot format. */
+
+static void
+dump_pred_graph (struct scc_info *si, FILE *file)
+{
+ unsigned int i;
+
+ /* Only print the graph if it has already been initialized: */
+ if (!graph)
+ return;
+
+ /* Prints the header of the dot file: */
+ fprintf (file, "strict digraph {\n");
+ fprintf (file, " node [\n shape = box\n ]\n");
+ fprintf (file, " edge [\n fontsize = \"12\"\n ]\n");
+ fprintf (file, "\n // List of nodes and complex constraints in "
+ "the constraint graph:\n");
+
+ /* The next lines print the nodes in the graph together with the
+ complex constraints attached to them. */
+ for (i = 1; i < graph->size; i++)
+ {
+ if (i == FIRST_REF_NODE)
+ continue;
+ if (si->node_mapping[i] != i)
+ continue;
+ if (i < FIRST_REF_NODE)
+ fprintf (file, "\"%s\"", get_varinfo (i)->name);
+ else
+ fprintf (file, "\"*%s\"", get_varinfo (i - FIRST_REF_NODE)->name);
+ if (graph->points_to[i]
+ && !bitmap_empty_p (graph->points_to[i]))
+ {
+ fprintf (file, "[label=\"%s = {", get_varinfo (i)->name);
+ unsigned j;
+ bitmap_iterator bi;
+ EXECUTE_IF_SET_IN_BITMAP (graph->points_to[i], 0, j, bi)
+ fprintf (file, " %d", j);
+ fprintf (file, " }\"]");
+ }
+ fprintf (file, ";\n");
+ }
+
+ /* Go over the edges. */
+ fprintf (file, "\n // Edges in the constraint graph:\n");
+ for (i = 1; i < graph->size; i++)
+ {
+ unsigned j;
+ bitmap_iterator bi;
+ if (si->node_mapping[i] != i)
+ continue;
+ EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[i], 0, j, bi)
{
- label = pointer_equiv_class++;
- equiv_class_add (pointer_equiv_class_table,
- label, graph->points_to[n]);
+ unsigned from = si->node_mapping[j];
+ if (from < FIRST_REF_NODE)
+ fprintf (file, "\"%s\"", get_varinfo (from)->name);
+ else
+ fprintf (file, "\"*%s\"", get_varinfo (from - FIRST_REF_NODE)->name);
+ fprintf (file, " -> ");
+ if (i < FIRST_REF_NODE)
+ fprintf (file, "\"%s\"", get_varinfo (i)->name);
+ else
+ fprintf (file, "\"*%s\"", get_varinfo (i - FIRST_REF_NODE)->name);
+ fprintf (file, ";\n");
}
- graph->pointer_label[n] = label;
}
+
+ /* Prints the tail of the dot file. */
+ fprintf (file, "}\n");
}
/* Perform offline variable substitution, discovering equivalence
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_table = new hash_table<equiv_class_hasher> (511);
+ location_equiv_class_table
+ = new hash_table<equiv_class_hasher> (511);
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++)
+ for (i = 1; i < FIRST_REF_NODE; i++)
if (!bitmap_bit_p (si->visited, si->node_mapping[i]))
condense_visit (graph, si, si->node_mapping[i]);
+ if (dump_file && (dump_flags & TDF_GRAPH))
+ {
+ fprintf (dump_file, "\n\n// The constraint graph before var-substitution "
+ "in dot format:\n");
+ dump_pred_graph (si, dump_file);
+ fprintf (dump_file, "\n\n");
+ }
+
bitmap_clear (si->visited);
/* Actually the label the nodes for pointer equivalences */
- for (i = 0; i < FIRST_REF_NODE; i++)
+ for (i = 1; i < FIRST_REF_NODE; i++)
if (!bitmap_bit_p (si->visited, si->node_mapping[i]))
label_visit (graph, si, si->node_mapping[i]);
/* Calculate location equivalence labels. */
- for (i = 0; i < FIRST_REF_NODE; i++)
+ for (i = 1; i < FIRST_REF_NODE; i++)
{
bitmap pointed_by;
bitmap_iterator bi;
unsigned int j;
- unsigned int label;
if (!graph->pointed_by[i])
continue;
/* 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);
- }
+ equiv_class_label_t ecl;
+ ecl = equiv_class_lookup_or_add (location_equiv_class_table, pointed_by);
+ if (ecl->equivalence_class == 0)
+ ecl->equivalence_class = location_equiv_class++;
else
{
if (dump_file && (dump_flags & TDF_DETAILS))
get_varinfo (i)->name);
BITMAP_FREE (pointed_by);
}
- graph->loc_label[i] = label;
+ graph->loc_label[i] = ecl->equivalence_class;
}
if (dump_file && (dump_flags & TDF_DETAILS))
- for (i = 0; i < FIRST_REF_NODE; i++)
+ for (i = 1; i < FIRST_REF_NODE; i++)
{
- bool direct_node = bitmap_bit_p (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]]);
+ unsigned j = si->node_mapping[i];
+ if (j != i)
+ {
+ fprintf (dump_file, "%s node id %d ",
+ bitmap_bit_p (graph->direct_nodes, i)
+ ? "Direct" : "Indirect", i);
+ if (i < FIRST_REF_NODE)
+ fprintf (dump_file, "\"%s\"", get_varinfo (i)->name);
+ else
+ fprintf (dump_file, "\"*%s\"",
+ get_varinfo (i - FIRST_REF_NODE)->name);
+ fprintf (dump_file, " mapped to SCC leader node id %d ", j);
+ if (j < FIRST_REF_NODE)
+ fprintf (dump_file, "\"%s\"\n", get_varinfo (j)->name);
+ else
+ fprintf (dump_file, "\"*%s\"\n",
+ get_varinfo (j - FIRST_REF_NODE)->name);
+ }
+ else
+ {
+ fprintf (dump_file,
+ "Equivalence classes for %s node id %d ",
+ bitmap_bit_p (graph->direct_nodes, i)
+ ? "direct" : "indirect", i);
+ if (i < FIRST_REF_NODE)
+ fprintf (dump_file, "\"%s\"", get_varinfo (i)->name);
+ else
+ fprintf (dump_file, "\"*%s\"",
+ get_varinfo (i - FIRST_REF_NODE)->name);
+ fprintf (dump_file,
+ ": pointer %d, location %d\n",
+ graph->pointer_label[i], graph->loc_label[i]);
+ }
}
/* Quickly eliminate our non-pointer variables. */
- for (i = 0; i < FIRST_REF_NODE; i++)
+ for (i = 1; i < FIRST_REF_NODE; i++)
{
unsigned int node = si->node_mapping[i];
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);
+ delete pointer_equiv_class_table;
+ pointer_equiv_class_table = NULL;
+ delete location_equiv_class_table;
+ location_equiv_class_table = NULL;
bitmap_obstack_release (&iteration_obstack);
}
if (!bitmap_bit_p (graph->address_taken, node))
{
- gcc_assert (label < graph->size);
+ gcc_checking_assert (label < graph->size);
if (graph->eq_rep[label] != -1)
{
}
else
{
- gcc_assert (label < graph->size);
+ gcc_checking_assert (label < graph->size);
graph->pe[node] = label;
if (graph->pe_rep[label] == -1)
graph->pe_rep[label] = node;
/* Go through the pointer equivalences and unite them to their
representative, if they aren't already. */
- for (i = 0; i < FIRST_REF_NODE; i++)
+ for (i = 1; i < FIRST_REF_NODE; i++)
{
unsigned int label = graph->pe[i];
if (label)
struct scc_info *si)
{
int i;
- unsigned int j;
constraint_t c;
- for (j = 0; j < graph->size; j++)
+#ifdef ENABLE_CHECKING
+ for (unsigned int j = 0; j < graph->size; j++)
gcc_assert (find (j) == j);
+#endif
FOR_EACH_VEC_ELT (constraints, i, c)
{
rhsvar = find_equivalent_node (graph, rhsvar, rhslabel);
c->lhs.var = lhsvar;
c->rhs.var = rhsvar;
-
}
}
&& !bitmap_empty_p (get_varinfo (node)->solution))
{
unsigned int i;
- vec<unsigned> queue = vNULL;
+ auto_vec<unsigned> queue;
int queuepos;
unsigned int to = find (graph->indirect_cycles[node]);
bitmap_iterator bi;
{
unify_nodes (graph, to, i, true);
}
- queue.release ();
return true;
}
return false;
changed = BITMAP_ALLOC (NULL);
/* Mark all initial non-collapsed nodes as changed. */
- for (i = 0; i < size; i++)
+ for (i = 1; i < size; i++)
{
varinfo_t ivi = get_varinfo (i);
if (find (i) == i && !bitmap_empty_p (ivi->solution)
varinfo_t vi = get_varinfo (i);
bool solution_empty;
- /* Compute the changed set of solution bits. */
- if (vi->oldsolution)
+ /* Compute the changed set of solution bits. If anything
+ is in the solution just propagate that. */
+ if (bitmap_bit_p (vi->solution, anything_id))
+ {
+ /* If anything is also in the old solution there is
+ nothing to do.
+ ??? But we shouldn't ended up with "changed" set ... */
+ if (vi->oldsolution
+ && bitmap_bit_p (vi->oldsolution, anything_id))
+ continue;
+ bitmap_copy (pts, get_varinfo (find (anything_id))->solution);
+ }
+ else if (vi->oldsolution)
bitmap_and_compl (pts, vi->solution, vi->oldsolution);
else
bitmap_copy (pts, vi->solution);
solution_empty = bitmap_empty_p (solution);
/* Process the complex constraints */
+ bitmap expanded_pts = NULL;
FOR_EACH_VEC_ELT (complex, j, c)
{
/* XXX: This is going to unsort the constraints in
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);
+ do_complex_constraint (graph, c, pts, &expanded_pts);
}
+ BITMAP_FREE (expanded_pts);
solution_empty = bitmap_empty_p (solution);
if (i == eff_escaped_id)
flag = bitmap_set_bit (tmp, escaped_id);
else
- flag = set_union_with_increment (tmp, pts, 0);
+ flag = bitmap_ior_into (tmp, pts);
if (flag)
- {
- get_varinfo (to)->solution = tmp;
- bitmap_set_bit (changed, to);
- }
+ bitmap_set_bit (changed, to);
}
}
}
}
/* Map from trees to variable infos. */
-static struct pointer_map_t *vi_for_tree;
+static hash_map<tree, varinfo_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;
+ gcc_assert (!vi_for_tree->put (t, vi));
}
/* Find the variable info for tree T in VI_FOR_TREE. If T does not
static varinfo_t
lookup_vi_for_tree (tree t)
{
- void **slot = pointer_map_contains (vi_for_tree, t);
+ varinfo_t *slot = vi_for_tree->get (t);
if (slot == NULL)
return NULL;
- return (varinfo_t) *slot;
+ return *slot;
}
/* Return a printable name for DECL */
static varinfo_t
get_vi_for_tree (tree t)
{
- void **slot = pointer_map_contains (vi_for_tree, t);
+ varinfo_t *slot = vi_for_tree->get (t);
if (slot == NULL)
return get_varinfo (create_variable_info_for (t, alias_get_name (t)));
- return (varinfo_t) *slot;
+ return *slot;
}
/* Get a scalar constraint expression for a new temporary variable. */
if (TREE_CODE (t) == VAR_DECL
&& (TREE_STATIC (t) || DECL_EXTERNAL (t)))
{
- struct varpool_node *node = varpool_get_node (t);
- if (node && node->alias)
+ varpool_node *node = varpool_node::get (t);
+ if (node && node->alias && node->analyzed)
{
- node = varpool_variable_node (node, NULL);
- t = node->symbol.decl;
+ node = node->ultimate_alias_target ();
+ t = node->decl;
}
}
cexpr.var = vi->id;
cexpr.type = SCALAR;
cexpr.offset = 0;
- /* If we determine the result is "anything", and we know this is readonly,
- say it points to readonly memory instead. */
- if (cexpr.var == anything_id && TREE_READONLY (t))
- {
- gcc_unreachable ();
- cexpr.type = ADDRESSOF;
- cexpr.var = readonly_id;
- }
/* If we are not taking the address of the constraint expr, add all
sub-fiels of the variable as well. */
if (!address_p
&& !vi->is_full_var)
{
- for (; vi; vi = vi->next)
+ for (; vi; vi = vi_next (vi))
{
cexpr.var = vi->id;
results->safe_push (cexpr);
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))
+ if (!tree_fits_shwi_p (DECL_FIELD_OFFSET (fdecl))
+ || !tree_fits_shwi_p (DECL_FIELD_BIT_OFFSET (fdecl)))
return -1;
- return (TREE_INT_CST_LOW (DECL_FIELD_OFFSET (fdecl)) * BITS_PER_UNIT
- + TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (fdecl)));
+ return (tree_to_shwi (DECL_FIELD_OFFSET (fdecl)) * BITS_PER_UNIT
+ + tree_to_shwi (DECL_FIELD_BIT_OFFSET (fdecl)));
}
else
{
/* Sign-extend the offset. */
- double_int soffset = tree_to_double_int (offset)
- .sext (TYPE_PRECISION (TREE_TYPE (offset)));
- if (!soffset.fits_shwi ())
+ offset_int soffset = offset_int::from (offset, SIGNED);
+ if (!wi::fits_shwi_p (soffset))
rhsoffset = UNKNOWN_OFFSET;
else
{
/* Make sure the bit-offset also fits. */
- HOST_WIDE_INT rhsunitoffset = soffset.low;
+ HOST_WIDE_INT rhsunitoffset = soffset.to_shwi ();
rhsoffset = rhsunitoffset * BITS_PER_UNIT;
if (rhsunitoffset != rhsoffset / BITS_PER_UNIT)
rhsoffset = UNKNOWN_OFFSET;
if (c.type == ADDRESSOF
/* If this varinfo represents a full variable just use it. */
&& curr->is_full_var)
- c.offset = 0;
+ ;
else if (c.type == ADDRESSOF
/* If we do not know the offset add all subfields. */
&& rhsoffset == UNKNOWN_OFFSET)
{
- varinfo_t temp = lookup_vi_for_tree (curr->decl);
+ varinfo_t temp = get_varinfo (curr->head);
do
{
struct constraint_expr c2;
c2.offset = 0;
if (c2.var != c.var)
results->safe_push (c2);
- temp = temp->next;
+ temp = vi_next (temp);
}
while (temp);
}
varinfo_t temp;
unsigned HOST_WIDE_INT offset = curr->offset + rhsoffset;
- /* Search the sub-field which overlaps with the
- pointed-to offset. If the result is outside of the variable
- we have to provide a conservative result, as the variable is
- still reachable from the resulting pointer (even though it
- technically cannot point to anything). The last and first
- sub-fields are such conservative results.
- ??? If we always had a sub-field for &object + 1 then
- we could represent this in a more precise way. */
+ /* If curr->offset + rhsoffset is less than zero adjust it. */
if (rhsoffset < 0
&& curr->offset < offset)
offset = 0;
- temp = first_or_preceding_vi_for_offset (curr, offset);
- /* If the found variable is not exactly at the pointed to
- result, we have to include the next variable in the
- solution as well. Otherwise two increments by offset / 2
- do not result in the same or a conservative superset
- solution. */
- if (temp->offset != offset
- && temp->next != NULL)
+ /* We have to include all fields that overlap the current
+ field shifted by rhsoffset. And we include at least
+ the last or the first field of the variable to represent
+ reachability of off-bound addresses, in particular &object + 1,
+ conservatively correct. */
+ temp = first_or_preceding_vi_for_offset (curr, offset);
+ c.var = temp->id;
+ c.offset = 0;
+ temp = vi_next (temp);
+ while (temp
+ && temp->offset < offset + curr->size)
{
struct constraint_expr c2;
- c2.var = temp->next->id;
+ c2.var = temp->id;
c2.type = ADDRESSOF;
c2.offset = 0;
results->safe_push (c2);
+ temp = vi_next (temp);
}
- c.var = temp->id;
- c.offset = 0;
+ }
+ else if (c.type == SCALAR)
+ {
+ gcc_assert (c.offset == 0);
+ c.offset = rhsoffset;
}
else
- c.offset = rhsoffset;
+ /* We shouldn't get any DEREFs here. */
+ gcc_unreachable ();
(*results)[j] = c;
}
return;
}
- /* Handle type-punning through unions. If we are extracting a pointer
- from a union via a possibly type-punning access that pointer
- points to anything, similar to a conversion of an integer to
- a pointer. */
- if (!lhs_p)
- {
- tree u;
- for (u = t;
- TREE_CODE (u) == COMPONENT_REF || TREE_CODE (u) == ARRAY_REF;
- u = TREE_OPERAND (u, 0))
- if (TREE_CODE (u) == COMPONENT_REF
- && TREE_CODE (TREE_TYPE (TREE_OPERAND (u, 0))) == UNION_TYPE)
- {
- struct constraint_expr temp;
-
- temp.offset = 0;
- temp.var = anything_id;
- temp.type = ADDRESSOF;
- results->safe_push (temp);
- return;
- }
- }
-
t = get_ref_base_and_extent (t, &bitpos, &bitsize, &bitmaxsize);
/* Pretend to take the address of the base, we'll take care of
varinfo_t curr;
results->pop ();
cexpr.offset = 0;
- for (curr = get_varinfo (cexpr.var); curr; curr = curr->next)
+ for (curr = get_varinfo (cexpr.var); curr; curr = vi_next (curr))
{
if (ranges_overlap_p (curr->offset, curr->size,
bitpos, bitmaxsize))
if (address_p && results->length () == 0)
{
curr = get_varinfo (cexpr.var);
- while (curr->next != NULL)
- curr = curr->next;
+ while (curr->next != 0)
+ curr = vi_next (curr);
cexpr.var = curr->id;
results->safe_push (cexpr);
}
return;
}
- /* String constants are read-only. */
+ /* String constants are read-only, ideally we'd have a CONST_DECL
+ for those. */
if (TREE_CODE (t) == STRING_CST)
{
- temp.var = readonly_id;
+ temp.var = string_id;
temp.type = SCALAR;
temp.offset = 0;
results->safe_push (temp);
return;
vi = get_varinfo (cs.var);
- curr = vi->next;
+ curr = vi_next (vi);
if (!vi->is_full_var
&& curr)
{
unsigned HOST_WIDE_INT size;
- if (host_integerp (TYPE_SIZE (TREE_TYPE (t)), 1))
- size = TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (t)));
+ if (tree_fits_uhwi_p (TYPE_SIZE (TREE_TYPE (t))))
+ size = tree_to_uhwi (TYPE_SIZE (TREE_TYPE (t)));
else
size = -1;
- for (; curr; curr = curr->next)
+ for (; curr; curr = vi_next (curr))
{
if (curr->offset - vi->offset < size)
{
{
unsigned int i;
tree val;
- vec<ce_s> tmp = vNULL;
+ auto_vec<ce_s> tmp;
FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (t), i, val)
{
struct constraint_expr *rhsp;
results->safe_push (*rhsp);
tmp.truncate (0);
}
- tmp.release ();
/* We do not know whether the constructor was complete,
so technically we have to add &NOTHING or &ANYTHING
like we do for an empty constructor as well. */
do_structure_copy (tree lhsop, tree rhsop)
{
struct constraint_expr *lhsp, *rhsp;
- vec<ce_s> lhsc = vNULL;
- vec<ce_s> rhsc = vNULL;
+ auto_vec<ce_s> lhsc;
+ auto_vec<ce_s> rhsc;
unsigned j;
get_constraint_for (lhsop, &lhsc);
}
else
gcc_unreachable ();
-
- lhsc.release ();
- rhsc.release ();
}
/* Create constraints ID = { rhsc }. */
static void
make_constraint_to (unsigned id, tree op)
{
- vec<ce_s> rhsc = vNULL;
+ auto_vec<ce_s> rhsc;
get_constraint_for_rhs (op, &rhsc);
make_constraints_to (id, rhsc);
- rhsc.release ();
}
/* Create a constraint ID = &FROM. */
lhs.offset = 0;
rhs.type = DEREF;
rhs.var = vi->id;
- rhs.offset = 0;
- process_constraint (new_constraint (lhs, rhs));
-
- /* VAR = VAR + UNKNOWN; */
- lhs.type = SCALAR;
- lhs.var = vi->id;
- lhs.offset = 0;
- rhs.type = SCALAR;
- rhs.var = vi->id;
rhs.offset = UNKNOWN_OFFSET;
process_constraint (new_constraint (lhs, rhs));
}
&& gimple_call_lhs (stmt) != NULL_TREE
&& TREE_ADDRESSABLE (TREE_TYPE (gimple_call_lhs (stmt))))
{
- vec<ce_s> tmpc = vNULL;
+ auto_vec<ce_s> tmpc;
struct constraint_expr lhsc, *c;
get_constraint_for_address_of (gimple_call_lhs (stmt), &tmpc);
lhsc.var = escaped_id;
lhsc.type = SCALAR;
FOR_EACH_VEC_ELT (tmpc, i, c)
process_constraint (new_constraint (lhsc, *c));
- tmpc.release ();
}
/* Regular functions return nonlocal memory. */
handle_lhs_call (gimple stmt, tree lhs, int flags, vec<ce_s> rhsc,
tree fndecl)
{
- vec<ce_s> lhsc = vNULL;
+ auto_vec<ce_s> lhsc;
get_constraint_for (lhs, &lhsc);
/* If the store is to a global decl make sure to
/* If the call returns an argument unmodified override the rhs
constraints. */
- flags = gimple_call_return_flags (stmt);
if (flags & ERF_RETURNS_ARG
&& (flags & ERF_RETURN_ARG_MASK) < gimple_call_num_args (stmt))
{
struct constraint_expr tmpc;
rhsc.create (0);
vi = make_heapvar ("HEAP");
- /* We delay marking allocated storage global until we know if
- it escapes. */
+ /* We are marking allocated storage local, we deal with it becoming
+ global by escaping and setting of vars_contains_escaped_heap. */
DECL_EXTERNAL (vi->decl) = 0;
vi->is_global_var = 0;
/* If this is not a real malloc call assume the memory was
}
else
process_all_all_constraints (lhsc, rhsc);
-
- lhsc.release ();
}
/* For non-IPA mode, generate constraints necessary for a call of a
for (k = 0; k < gimple_call_num_args (stmt); ++k)
{
tree arg = gimple_call_arg (stmt, k);
- vec<ce_s> argc = vNULL;
+ auto_vec<ce_s> argc;
unsigned i;
struct constraint_expr *argp;
get_constraint_for_rhs (arg, &argc);
FOR_EACH_VEC_ELT (argc, i, argp)
results->safe_push (*argp);
- argc.release ();
}
/* May return addresses of globals. */
was handled, otherwise false. */
static bool
-find_func_aliases_for_builtin_call (gimple t)
+find_func_aliases_for_builtin_call (struct function *fn, gimple t)
{
tree fndecl = gimple_call_fndecl (t);
- vec<ce_s> lhsc = vNULL;
- vec<ce_s> rhsc = vNULL;
+ auto_vec<ce_s, 2> lhsc;
+ auto_vec<ce_s, 4> rhsc;
varinfo_t fi;
- if (fndecl != NULL_TREE
- && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)
+ if (gimple_call_builtin_p (t, BUILT_IN_NORMAL))
/* ??? All builtins that are handled here need to be handled
in the alias-oracle query functions explicitly! */
switch (DECL_FUNCTION_CODE (fndecl))
else
get_constraint_for (dest, &rhsc);
process_all_all_constraints (lhsc, rhsc);
- lhsc.release ();
- rhsc.release ();
+ lhsc.truncate (0);
+ rhsc.truncate (0);
}
get_constraint_for_ptr_offset (dest, NULL_TREE, &lhsc);
get_constraint_for_ptr_offset (src, NULL_TREE, &rhsc);
do_deref (&lhsc);
do_deref (&rhsc);
process_all_all_constraints (lhsc, rhsc);
- lhsc.release ();
- rhsc.release ();
return true;
}
case BUILT_IN_MEMSET:
get_constraint_for (res, &lhsc);
get_constraint_for (dest, &rhsc);
process_all_all_constraints (lhsc, rhsc);
- lhsc.release ();
- rhsc.release ();
+ lhsc.truncate (0);
}
get_constraint_for_ptr_offset (dest, NULL_TREE, &lhsc);
do_deref (&lhsc);
ac.offset = 0;
FOR_EACH_VEC_ELT (lhsc, i, lhsp)
process_constraint (new_constraint (*lhsp, ac));
- lhsc.release ();
+ return true;
+ }
+ case BUILT_IN_POSIX_MEMALIGN:
+ {
+ tree ptrptr = gimple_call_arg (t, 0);
+ get_constraint_for (ptrptr, &lhsc);
+ do_deref (&lhsc);
+ varinfo_t vi = make_heapvar ("HEAP");
+ /* We are marking allocated storage local, we deal with it becoming
+ global by escaping and setting of vars_contains_escaped_heap. */
+ DECL_EXTERNAL (vi->decl) = 0;
+ vi->is_global_var = 0;
+ struct constraint_expr tmpc;
+ tmpc.var = vi->id;
+ tmpc.offset = 0;
+ tmpc.type = ADDRESSOF;
+ rhsc.safe_push (tmpc);
+ process_all_all_constraints (lhsc, rhsc);
return true;
}
case BUILT_IN_ASSUME_ALIGNED:
get_constraint_for (res, &lhsc);
get_constraint_for (dest, &rhsc);
process_all_all_constraints (lhsc, rhsc);
- lhsc.release ();
- rhsc.release ();
}
return true;
}
return true;
case BUILT_IN_STRDUP:
case BUILT_IN_STRNDUP:
+ case BUILT_IN_REALLOC:
if (gimple_call_lhs (t))
{
- handle_lhs_call (t, gimple_call_lhs (t), gimple_call_flags (t),
+ handle_lhs_call (t, gimple_call_lhs (t),
+ gimple_call_return_flags (t) | ERF_NOALIAS,
vNULL, fndecl);
get_constraint_for_ptr_offset (gimple_call_lhs (t),
NULL_TREE, &lhsc);
do_deref (&lhsc);
do_deref (&rhsc);
process_all_all_constraints (lhsc, rhsc);
- lhsc.release ();
- rhsc.release ();
+ lhsc.truncate (0);
+ rhsc.truncate (0);
+ /* For realloc the resulting pointer can be equal to the
+ argument as well. But only doing this wouldn't be
+ correct because with ptr == 0 realloc behaves like malloc. */
+ if (DECL_FUNCTION_CODE (fndecl) == BUILT_IN_REALLOC)
+ {
+ get_constraint_for (gimple_call_lhs (t), &lhsc);
+ get_constraint_for (gimple_call_arg (t, 0), &rhsc);
+ process_all_all_constraints (lhsc, rhsc);
+ }
return true;
}
break;
+ /* String / character search functions return a pointer into the
+ source string or NULL. */
+ case BUILT_IN_INDEX:
+ case BUILT_IN_STRCHR:
+ case BUILT_IN_STRRCHR:
+ case BUILT_IN_MEMCHR:
+ case BUILT_IN_STRSTR:
+ case BUILT_IN_STRPBRK:
+ if (gimple_call_lhs (t))
+ {
+ tree src = gimple_call_arg (t, 0);
+ get_constraint_for_ptr_offset (src, NULL_TREE, &rhsc);
+ constraint_expr nul;
+ nul.var = nothing_id;
+ nul.offset = 0;
+ nul.type = ADDRESSOF;
+ rhsc.safe_push (nul);
+ get_constraint_for (gimple_call_lhs (t), &lhsc);
+ process_all_all_constraints (lhsc, rhsc);
+ }
+ return true;
/* Trampolines are special - they set up passing the static
frame. */
case BUILT_IN_INIT_TRAMPOLINE:
lhs = get_function_part_constraint (nfi, fi_static_chain);
get_constraint_for (frame, &rhsc);
FOR_EACH_VEC_ELT (rhsc, i, rhsp)
- process_constraint (new_constraint (lhs, *rhsp));
- rhsc.release ();
+ process_constraint (new_constraint (lhs, *rhsp));
+ rhsc.truncate (0);
/* Make the frame point to the function for
the trampoline adjustment call. */
do_deref (&lhsc);
get_constraint_for (nfunc, &rhsc);
process_all_all_constraints (lhsc, rhsc);
- rhsc.release ();
- lhsc.release ();
return true;
}
get_constraint_for (tramp, &rhsc);
do_deref (&rhsc);
process_all_all_constraints (lhsc, rhsc);
- rhsc.release ();
- lhsc.release ();
}
return true;
}
do_deref (&lhsc);
get_constraint_for (src, &rhsc);
process_all_all_constraints (lhsc, rhsc);
- lhsc.release ();
- rhsc.release ();
return true;
}
CASE_BUILT_IN_TM_LOAD (1):
get_constraint_for (addr, &rhsc);
do_deref (&rhsc);
process_all_all_constraints (lhsc, rhsc);
- lhsc.release ();
- rhsc.release ();
return true;
}
/* Variadic argument handling needs to be handled in IPA
and otherwise are just all nonlocal variables. */
if (in_ipa_mode)
{
- fi = lookup_vi_for_tree (cfun->decl);
+ fi = lookup_vi_for_tree (fn->decl);
rhs = get_function_part_constraint (fi, ~0);
rhs.type = ADDRESSOF;
}
}
FOR_EACH_VEC_ELT (lhsc, i, lhsp)
process_constraint (new_constraint (*lhsp, rhs));
- lhsc.release ();
/* va_list is clobbered. */
make_constraint_to (get_call_clobber_vi (t)->id, valist);
return true;
{
fi = NULL;
if (!in_ipa_mode
- || !(fi = get_vi_for_tree (cfun->decl)))
+ || !(fi = get_vi_for_tree (fn->decl)))
make_constraint_from (get_varinfo (escaped_id), anything_id);
else if (in_ipa_mode
&& fi != NULL)
}
/* printf-style functions may have hooks to set pointers to
point to somewhere into the generated string. Leave them
- for a later excercise... */
+ for a later exercise... */
default:
/* Fallthru to general call handling. */;
}
/* Create constraints for the call T. */
static void
-find_func_aliases_for_call (gimple t)
+find_func_aliases_for_call (struct function *fn, gimple t)
{
tree fndecl = gimple_call_fndecl (t);
- vec<ce_s> lhsc = vNULL;
- vec<ce_s> rhsc = vNULL;
varinfo_t fi;
if (fndecl != NULL_TREE
&& DECL_BUILT_IN (fndecl)
- && find_func_aliases_for_builtin_call (t))
+ && find_func_aliases_for_builtin_call (fn, t))
return;
fi = get_fi_for_callee (t);
if (!in_ipa_mode
|| (fndecl && !fi->is_fn_info))
{
- vec<ce_s> rhsc = vNULL;
+ auto_vec<ce_s, 16> rhsc;
int flags = gimple_call_flags (t);
/* Const functions can return their arguments and addresses
else
handle_rhs_call (t, &rhsc);
if (gimple_call_lhs (t))
- handle_lhs_call (t, gimple_call_lhs (t), flags, rhsc, fndecl);
- rhsc.release ();
+ handle_lhs_call (t, gimple_call_lhs (t),
+ gimple_call_return_flags (t), rhsc, fndecl);
}
else
{
+ auto_vec<ce_s, 2> rhsc;
tree lhsop;
unsigned j;
lhsop = gimple_call_lhs (t);
if (lhsop)
{
+ auto_vec<ce_s, 2> lhsc;
struct constraint_expr rhs;
struct constraint_expr *lhsp;
&& DECL_RESULT (fndecl)
&& DECL_BY_REFERENCE (DECL_RESULT (fndecl)))
{
- vec<ce_s> tem = vNULL;
- tem.safe_push (rhs);
+ auto_vec<ce_s, 2> tem;
+ tem.quick_push (rhs);
do_deref (&tem);
+ gcc_checking_assert (tem.length () == 1);
rhs = tem[0];
- tem.release ();
}
FOR_EACH_VEC_ELT (lhsc, j, lhsp)
process_constraint (new_constraint (*lhsp, rhs));
lhs = get_function_part_constraint (fi, fi_result);
FOR_EACH_VEC_ELT (rhsc, j, rhsp)
process_constraint (new_constraint (lhs, *rhsp));
- rhsc.release ();
+ rhsc.truncate (0);
}
/* If we use a static chain, pass it along. */
when building alias sets and computing alias grouping heuristics. */
static void
-find_func_aliases (gimple origt)
+find_func_aliases (struct function *fn, gimple origt)
{
gimple t = origt;
- vec<ce_s> lhsc = vNULL;
- vec<ce_s> rhsc = vNULL;
+ auto_vec<ce_s, 16> lhsc;
+ auto_vec<ce_s, 16> rhsc;
struct constraint_expr *c;
varinfo_t fi;
In non-ipa mode, we need to generate constraints for each
pointer passed by address. */
else if (is_gimple_call (t))
- find_func_aliases_for_call (t);
+ find_func_aliases_for_call (fn, t);
/* Otherwise, just a regular assignment statement. Only care about
operations with pointer result, others are dealt with as escape
get_constraint_for (lhsop, &lhsc);
- if (code == POINTER_PLUS_EXPR)
+ if (FLOAT_TYPE_P (TREE_TYPE (lhsop)))
+ /* If the operation produces a floating point result then
+ assume the value is not produced to transfer a pointer. */
+ ;
+ else if (code == POINTER_PLUS_EXPR)
get_constraint_for_ptr_offset (gimple_assign_rhs1 (t),
gimple_assign_rhs2 (t), &rhsc);
else if (code == BIT_AND_EXPR
else if (code == COND_EXPR)
{
/* The result is a merge of both COND_EXPR arms. */
- vec<ce_s> tmp = vNULL;
+ auto_vec<ce_s, 2> tmp;
struct constraint_expr *rhsp;
unsigned i;
get_constraint_for_rhs (gimple_assign_rhs2 (t), &rhsc);
get_constraint_for_rhs (gimple_assign_rhs3 (t), &tmp);
FOR_EACH_VEC_ELT (tmp, i, rhsp)
rhsc.safe_push (*rhsp);
- tmp.release ();
}
else if (truth_value_p (code))
/* Truth value results are not pointer (parts). Or at least
else
{
/* All other operations are merges. */
- vec<ce_s> tmp = vNULL;
+ auto_vec<ce_s, 4> tmp;
struct constraint_expr *rhsp;
unsigned i, j;
get_constraint_for_rhs (gimple_assign_rhs1 (t), &rhsc);
rhsc.safe_push (*rhsp);
tmp.truncate (0);
}
- tmp.release ();
}
process_all_all_constraints (lhsc, rhsc);
}
{
fi = NULL;
if (!in_ipa_mode
- || !(fi = get_vi_for_tree (cfun->decl)))
+ || !(fi = get_vi_for_tree (fn->decl)))
make_escape_constraint (gimple_return_retval (t));
else if (in_ipa_mode
&& fi != NULL)
any global memory. */
if (op)
{
- vec<ce_s> lhsc = vNULL;
+ auto_vec<ce_s, 2> lhsc;
struct constraint_expr rhsc, *lhsp;
unsigned j;
get_constraint_for (op, &lhsc);
rhsc.type = SCALAR;
FOR_EACH_VEC_ELT (lhsc, j, lhsp)
process_constraint (new_constraint (*lhsp, rhsc));
- lhsc.release ();
}
}
for (i = 0; i < gimple_asm_ninputs (t); ++i)
make_escape_constraint (op);
}
}
-
- rhsc.release ();
- lhsc.release ();
}
IPA constraint builder. */
static void
-find_func_clobbers (gimple origt)
+find_func_clobbers (struct function *fn, gimple origt)
{
gimple t = origt;
- vec<ce_s> lhsc = vNULL;
- vec<ce_s> rhsc = vNULL;
+ auto_vec<ce_s, 16> lhsc;
+ auto_vec<ce_s, 16> rhsc;
varinfo_t fi;
/* Add constraints for clobbered/used in IPA mode.
return;
/* We'd better have function information for the current function. */
- fi = lookup_vi_for_tree (cfun->decl);
+ fi = lookup_vi_for_tree (fn->decl);
gcc_assert (fi != NULL);
/* Account for stores in assignments and calls. */
while (handled_component_p (tem))
tem = TREE_OPERAND (tem, 0);
if ((DECL_P (tem)
- && !auto_var_in_fn_p (tem, cfun->decl))
+ && !auto_var_in_fn_p (tem, fn->decl))
|| INDIRECT_REF_P (tem)
|| (TREE_CODE (tem) == MEM_REF
&& !(TREE_CODE (TREE_OPERAND (tem, 0)) == ADDR_EXPR
&& auto_var_in_fn_p
- (TREE_OPERAND (TREE_OPERAND (tem, 0), 0), cfun->decl))))
+ (TREE_OPERAND (TREE_OPERAND (tem, 0), 0), fn->decl))))
{
struct constraint_expr lhsc, *rhsp;
unsigned i;
get_constraint_for_address_of (lhs, &rhsc);
FOR_EACH_VEC_ELT (rhsc, i, rhsp)
process_constraint (new_constraint (lhsc, *rhsp));
- rhsc.release ();
+ rhsc.truncate (0);
}
}
while (handled_component_p (tem))
tem = TREE_OPERAND (tem, 0);
if ((DECL_P (tem)
- && !auto_var_in_fn_p (tem, cfun->decl))
+ && !auto_var_in_fn_p (tem, fn->decl))
|| INDIRECT_REF_P (tem)
|| (TREE_CODE (tem) == MEM_REF
&& !(TREE_CODE (TREE_OPERAND (tem, 0)) == ADDR_EXPR
&& auto_var_in_fn_p
- (TREE_OPERAND (TREE_OPERAND (tem, 0), 0), cfun->decl))))
+ (TREE_OPERAND (TREE_OPERAND (tem, 0), 0), fn->decl))))
{
struct constraint_expr lhs, *rhsp;
unsigned i;
get_constraint_for_address_of (rhs, &rhsc);
FOR_EACH_VEC_ELT (rhsc, i, rhsp)
process_constraint (new_constraint (lhs, *rhsp));
- rhsc.release ();
+ rhsc.truncate (0);
}
}
/* For builtins we do not have separate function info. For those
we do not generate escapes for we have to generate clobbers/uses. */
- if (decl
- && DECL_BUILT_IN_CLASS (decl) == BUILT_IN_NORMAL)
+ if (gimple_call_builtin_p (t, BUILT_IN_NORMAL))
switch (DECL_FUNCTION_CODE (decl))
{
/* The following functions use and clobber memory pointed to
lhs = get_function_part_constraint (fi, fi_clobbers);
FOR_EACH_VEC_ELT (lhsc, i, lhsp)
process_constraint (new_constraint (lhs, *lhsp));
- lhsc.release ();
get_constraint_for_ptr_offset (src, NULL_TREE, &rhsc);
lhs = get_function_part_constraint (fi, fi_uses);
FOR_EACH_VEC_ELT (rhsc, i, rhsp)
process_constraint (new_constraint (lhs, *rhsp));
- rhsc.release ();
return;
}
/* The following function clobbers memory pointed to by
its argument. */
case BUILT_IN_MEMSET:
case BUILT_IN_MEMSET_CHK:
+ case BUILT_IN_POSIX_MEMALIGN:
{
tree dest = gimple_call_arg (t, 0);
unsigned i;
lhs = get_function_part_constraint (fi, fi_clobbers);
FOR_EACH_VEC_ELT (lhsc, i, lhsp)
process_constraint (new_constraint (lhs, *lhsp));
- lhsc.release ();
return;
}
/* The following functions clobber their second and third
return;
/* printf-style functions may have hooks to set pointers to
point to somewhere into the generated string. Leave them
- for a later excercise... */
+ for a later exercise... */
default:
/* Fallthru to general call handling. */;
}
get_constraint_for_address_of (arg, &rhsc);
FOR_EACH_VEC_ELT (rhsc, j, rhsp)
process_constraint (new_constraint (lhs, *rhsp));
- rhsc.release ();
+ rhsc.truncate (0);
}
/* Build constraints for propagating clobbers/uses along the
make_constraint_from (first_vi_for_offset (fi, fi_uses),
anything_id);
}
-
- rhsc.release ();
}
/* If we cannot reach offset from start, lookup the first field
and start from there. */
if (start->offset > offset)
- start = lookup_vi_for_tree (start->decl);
+ start = get_varinfo (start->head);
while (start)
{
&& (offset - start->offset) < start->size)
return start;
- start= start->next;
+ start = vi_next (start);
}
return NULL;
/* If we cannot reach offset from start, lookup the first field
and start from there. */
if (start->offset > offset)
- start = lookup_vi_for_tree (start->decl);
+ start = get_varinfo (start->head);
/* We may not find a variable in the field list with the actual
offset when when we have glommed a structure to a variable.
while (start->next
&& offset >= start->offset
&& !((offset - start->offset) < start->size))
- start = start->next;
+ start = vi_next (start);
return start;
}
}
if (!DECL_SIZE (field)
- || !host_integerp (DECL_SIZE (field), 1))
+ || !tree_fits_uhwi_p (DECL_SIZE (field)))
has_unknown_size = true;
/* If adjacent fields do not contain pointers merge them. */
&& !pair->has_unknown_size
&& pair->offset + (HOST_WIDE_INT)pair->size == offset + foff)
{
- pair->size += TREE_INT_CST_LOW (DECL_SIZE (field));
+ pair->size += tree_to_uhwi (DECL_SIZE (field));
}
else
{
e.offset = offset + foff;
e.has_unknown_size = has_unknown_size;
if (!has_unknown_size)
- e.size = TREE_INT_CST_LOW (DECL_SIZE (field));
+ e.size = tree_to_uhwi (DECL_SIZE (field));
else
e.size = -1;
e.must_have_pointers = must_have_pointers_p;
clobbervi->is_full_var = true;
clobbervi->is_global_var = false;
gcc_assert (prev_vi->offset < clobbervi->offset);
- prev_vi->next = clobbervi;
+ prev_vi->next = clobbervi->id;
prev_vi = clobbervi;
asprintf (&tempname, "%s.use", name);
usevi->is_full_var = true;
usevi->is_global_var = false;
gcc_assert (prev_vi->offset < usevi->offset);
- prev_vi->next = usevi;
+ prev_vi->next = usevi->id;
prev_vi = usevi;
}
chainvi->is_full_var = true;
chainvi->is_global_var = false;
gcc_assert (prev_vi->offset < chainvi->offset);
- prev_vi->next = chainvi;
+ prev_vi->next = chainvi->id;
prev_vi = chainvi;
insert_vi_for_tree (fn->static_chain_decl, chainvi);
}
if (DECL_RESULT (decl))
resultvi->may_have_pointers = true;
gcc_assert (prev_vi->offset < resultvi->offset);
- prev_vi->next = resultvi;
+ prev_vi->next = resultvi->id;
prev_vi = resultvi;
if (DECL_RESULT (decl))
insert_vi_for_tree (DECL_RESULT (decl), resultvi);
if (arg)
argvi->may_have_pointers = true;
gcc_assert (prev_vi->offset < argvi->offset);
- prev_vi->next = argvi;
+ prev_vi->next = argvi->id;
prev_vi = argvi;
if (arg)
{
argvi->is_heap_var = true;
argvi->fullsize = vi->fullsize;
gcc_assert (prev_vi->offset < argvi->offset);
- prev_vi->next = argvi;
+ prev_vi->next = argvi->id;
prev_vi = argvi;
}
varinfo_t vi, newvi;
tree decl_type = TREE_TYPE (decl);
tree declsize = DECL_P (decl) ? DECL_SIZE (decl) : TYPE_SIZE (decl_type);
- vec<fieldoff_s> fieldstack = vNULL;
+ auto_vec<fieldoff_s> fieldstack;
fieldoff_s *fo;
unsigned int i;
+ varpool_node *vnode;
if (!declsize
- || !host_integerp (declsize, 1))
+ || !tree_fits_uhwi_p (declsize))
{
vi = new_var_info (decl, name);
vi->offset = 0;
in IPA mode. Else we'd have to parse arbitrary initializers. */
&& !(in_ipa_mode
&& is_global_var (decl)
- && DECL_INITIAL (decl)))
+ && (vnode = varpool_node::get (decl))
+ && vnode->get_constructor ()))
{
fieldoff_s *fo = NULL;
bool notokay = false;
vi = new_var_info (decl, name);
vi->offset = 0;
vi->may_have_pointers = true;
- vi->fullsize = TREE_INT_CST_LOW (declsize);
+ vi->fullsize = tree_to_uhwi (declsize);
vi->size = vi->fullsize;
vi->is_full_var = true;
fieldstack.release ();
}
vi = new_var_info (decl, name);
- vi->fullsize = TREE_INT_CST_LOW (declsize);
+ vi->fullsize = tree_to_uhwi (declsize);
for (i = 0, newvi = vi;
fieldstack.iterate (i, &fo);
- ++i, newvi = newvi->next)
+ ++i, newvi = vi_next (newvi))
{
const char *newname = "NULL";
char *tempname;
newvi->may_have_pointers = fo->may_have_pointers;
newvi->only_restrict_pointers = fo->only_restrict_pointers;
if (i + 1 < fieldstack.length ())
- newvi->next = new_var_info (decl, name);
+ {
+ varinfo_t tem = new_var_info (decl, name);
+ newvi->next = tem->id;
+ tem->head = vi->id;
+ }
}
- fieldstack.release ();
-
return vi;
}
return id;
/* Create initial constraints for globals. */
- for (; vi; vi = vi->next)
+ for (; vi; vi = vi_next (vi))
{
if (!vi->may_have_pointers
|| !vi->is_global_var)
for it. */
else
{
- struct varpool_node *vnode = varpool_get_node (decl);
+ varpool_node *vnode = varpool_node::get (decl);
/* For escaped variables initialize them from nonlocal. */
- if (!varpool_all_refs_explicit_p (vnode))
+ if (!vnode->all_refs_explicit_p ())
make_copy_constraint (vi, nonlocal_id);
/* If this is a global variable with an initializer and we are in
IPA mode generate constraints for it. */
- if (DECL_INITIAL (decl)
- && vnode->analyzed)
+ if (vnode->get_constructor ()
+ && vnode->definition)
{
- vec<ce_s> rhsc = vNULL;
+ auto_vec<ce_s> rhsc;
struct constraint_expr lhs, *rhsp;
unsigned i;
- get_constraint_for_rhs (DECL_INITIAL (decl), &rhsc);
+ get_constraint_for_rhs (vnode->get_constructor (), &rhsc);
lhs.var = vi->id;
lhs.offset = 0;
lhs.type = SCALAR;
process_constraint (new_constraint (lhs, *rhsp));
/* If this is a variable that escapes from the unit
the initializer escapes as well. */
- if (!varpool_all_refs_explicit_p (vnode))
+ if (!vnode->all_refs_explicit_p ())
{
lhs.var = escaped_id;
lhs.offset = 0;
FOR_EACH_VEC_ELT (rhsc, i, rhsp)
process_constraint (new_constraint (lhs, *rhsp));
}
- rhsc.release ();
}
}
}
fprintf (file, "\n");
}
-/* Print the points-to solution for VAR to stdout. */
+/* Print the points-to solution for VAR to stderr. */
DEBUG_FUNCTION void
debug_solution_for_var (unsigned int var)
{
- dump_solution_for_var (stdout, var);
+ dump_solution_for_var (stderr, var);
}
/* Create varinfo structures for all of the variables in the
function for intraprocedural mode. */
static void
-intra_create_variable_infos (void)
+intra_create_variable_infos (struct function *fn)
{
tree t;
/* For each incoming pointer argument arg, create the constraint ARG
= NONLOCAL or a dummy variable if it is a restrict qualified
passed-by-reference argument. */
- for (t = DECL_ARGUMENTS (current_function_decl); t; t = DECL_CHAIN (t))
+ for (t = DECL_ARGUMENTS (fn->decl); t; t = DECL_CHAIN (t))
{
varinfo_t p = get_vi_for_tree (t);
rhsc.type = ADDRESSOF;
rhsc.offset = 0;
process_constraint (new_constraint (lhsc, rhsc));
- for (; vi; vi = vi->next)
+ for (; vi; vi = vi_next (vi))
if (vi->may_have_pointers)
{
if (vi->only_restrict_pointers)
make_constraint_from_global_restrict (p, "PARM_RESTRICT");
else
{
- for (; p; p = p->next)
+ for (; p; p = vi_next (p))
{
if (p->only_restrict_pointers)
make_constraint_from_global_restrict (p, "PARM_RESTRICT");
}
/* Add a constraint for a result decl that is passed by reference. */
- if (DECL_RESULT (cfun->decl)
- && DECL_BY_REFERENCE (DECL_RESULT (cfun->decl)))
+ if (DECL_RESULT (fn->decl)
+ && DECL_BY_REFERENCE (DECL_RESULT (fn->decl)))
{
- varinfo_t p, result_vi = get_vi_for_tree (DECL_RESULT (cfun->decl));
+ varinfo_t p, result_vi = get_vi_for_tree (DECL_RESULT (fn->decl));
- for (p = result_vi; p; p = p->next)
+ for (p = result_vi; p; p = vi_next (p))
make_constraint_from (p, nonlocal_id);
}
/* Add a constraint for the incoming static chain parameter. */
- if (cfun->static_chain_decl != NULL_TREE)
+ if (fn->static_chain_decl != NULL_TREE)
{
- varinfo_t p, chain_vi = get_vi_for_tree (cfun->static_chain_decl);
+ varinfo_t p, chain_vi = get_vi_for_tree (fn->static_chain_decl);
- for (p = chain_vi; p; p = p->next)
+ for (p = chain_vi; p; p = vi_next (p))
make_constraint_from (p, nonlocal_id);
}
}
} *shared_bitmap_info_t;
typedef const struct shared_bitmap_info *const_shared_bitmap_info_t;
-static htab_t shared_bitmap_table;
+/* Shared_bitmap hashtable helpers. */
+
+struct shared_bitmap_hasher : typed_free_remove <shared_bitmap_info>
+{
+ typedef shared_bitmap_info value_type;
+ typedef shared_bitmap_info compare_type;
+ static inline hashval_t hash (const value_type *);
+ static inline bool equal (const value_type *, const compare_type *);
+};
/* Hash function for a shared_bitmap_info_t */
-static hashval_t
-shared_bitmap_hash (const void *p)
+inline hashval_t
+shared_bitmap_hasher::hash (const value_type *bi)
{
- const_shared_bitmap_info_t const bi = (const_shared_bitmap_info_t) p;
return bi->hashcode;
}
/* Equality function for two shared_bitmap_info_t's. */
-static int
-shared_bitmap_eq (const void *p1, const void *p2)
+inline bool
+shared_bitmap_hasher::equal (const value_type *sbi1, const compare_type *sbi2)
{
- const_shared_bitmap_info_t const sbi1 = (const_shared_bitmap_info_t) p1;
- const_shared_bitmap_info_t const sbi2 = (const_shared_bitmap_info_t) p2;
return bitmap_equal_p (sbi1->pt_vars, sbi2->pt_vars);
}
+/* Shared_bitmap hashtable. */
+
+static hash_table<shared_bitmap_hasher> *shared_bitmap_table;
+
/* Lookup a bitmap in the shared bitmap hashtable, and return an already
existing instance if there is one, NULL otherwise. */
static bitmap
shared_bitmap_lookup (bitmap pt_vars)
{
- void **slot;
+ shared_bitmap_info **slot;
struct shared_bitmap_info sbi;
sbi.pt_vars = pt_vars;
sbi.hashcode = bitmap_hash (pt_vars);
- slot = htab_find_slot_with_hash (shared_bitmap_table, &sbi,
- sbi.hashcode, NO_INSERT);
+ slot = shared_bitmap_table->find_slot (&sbi, NO_INSERT);
if (!slot)
return NULL;
else
- return ((shared_bitmap_info_t) *slot)->pt_vars;
+ return (*slot)->pt_vars;
}
static void
shared_bitmap_add (bitmap pt_vars)
{
- void **slot;
+ shared_bitmap_info **slot;
shared_bitmap_info_t sbi = XNEW (struct shared_bitmap_info);
sbi->pt_vars = pt_vars;
sbi->hashcode = bitmap_hash (pt_vars);
- slot = htab_find_slot_with_hash (shared_bitmap_table, sbi,
- sbi->hashcode, INSERT);
+ slot = shared_bitmap_table->find_slot (sbi, INSERT);
gcc_assert (!*slot);
- *slot = (void *) sbi;
+ *slot = sbi;
}
{
unsigned int i;
bitmap_iterator bi;
+ varinfo_t escaped_vi = get_varinfo (find (escaped_id));
+ bool everything_escaped
+ = escaped_vi->solution && bitmap_bit_p (escaped_vi->solution, anything_id);
EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
{
if (vi->is_artificial_var && !vi->is_heap_var)
continue;
+ if (everything_escaped
+ || (escaped_vi->solution
+ && bitmap_bit_p (escaped_vi->solution, i)))
+ {
+ pt->vars_contains_escaped = true;
+ pt->vars_contains_escaped_heap = vi->is_heap_var;
+ }
+
if (TREE_CODE (vi->decl) == VAR_DECL
|| TREE_CODE (vi->decl) == PARM_DECL
|| TREE_CODE (vi->decl) == RESULT_DECL)
set contains global variables. */
bitmap_set_bit (into, DECL_PT_UID (vi->decl));
if (vi->is_global_var)
- pt->vars_contains_global = true;
+ pt->vars_contains_nonlocal = true;
}
}
}
/* Compute the points-to solution *PT for the variable VI. */
-static void
-find_what_var_points_to (varinfo_t orig_vi, struct pt_solution *pt)
+static struct pt_solution
+find_what_var_points_to (varinfo_t orig_vi)
{
unsigned int i;
bitmap_iterator bi;
bitmap finished_solution;
bitmap result;
varinfo_t vi;
-
- memset (pt, 0, sizeof (struct pt_solution));
+ struct pt_solution *pt;
/* This variable may have been collapsed, let's get the real
variable. */
vi = get_varinfo (find (orig_vi->id));
+ /* See if we have already computed the solution and return it. */
+ pt_solution **slot = &final_solutions->get_or_insert (vi);
+ if (*slot != NULL)
+ return **slot;
+
+ *slot = pt = XOBNEW (&final_solutions_obstack, struct pt_solution);
+ memset (pt, 0, sizeof (struct pt_solution));
+
/* Translate artificial variables into SSA_NAME_PTR_INFO
attributes. */
EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
pt->ipa_escaped = 1;
else
pt->escaped = 1;
+ /* Expand some special vars of ESCAPED in-place here. */
+ varinfo_t evi = get_varinfo (find (escaped_id));
+ if (bitmap_bit_p (evi->solution, nonlocal_id))
+ pt->nonlocal = 1;
}
else if (vi->id == nonlocal_id)
pt->nonlocal = 1;
else if (vi->is_heap_var)
/* We represent heapvars in the points-to set properly. */
;
- else if (vi->id == readonly_id)
- /* Nobody cares. */
+ else if (vi->id == string_id)
+ /* Nobody cares - STRING_CSTs are read-only entities. */
;
else if (vi->id == anything_id
|| vi->id == integer_id)
/* Instead of doing extra work, simply do not create
elaborate points-to information for pt_anything pointers. */
if (pt->anything)
- return;
+ return *pt;
/* Share the final set of variables when possible. */
finished_solution = BITMAP_GGC_ALLOC ();
pt->vars = result;
bitmap_clear (finished_solution);
}
+
+ return *pt;
}
/* Given a pointer variable P, fill in its points-to set. */
return;
pi = get_ptr_info (p);
- find_what_var_points_to (vi, &pi->pt);
+ pi->pt = find_what_var_points_to (vi);
}
it contains restrict tag variables. */
void
-pt_solution_set (struct pt_solution *pt, bitmap vars, bool vars_contains_global)
+pt_solution_set (struct pt_solution *pt, bitmap vars,
+ bool vars_contains_nonlocal)
{
memset (pt, 0, sizeof (struct pt_solution));
pt->vars = vars;
- pt->vars_contains_global = vars_contains_global;
+ pt->vars_contains_nonlocal = vars_contains_nonlocal;
+ pt->vars_contains_escaped
+ = (cfun->gimple_df->escaped.anything
+ || bitmap_intersect_p (cfun->gimple_df->escaped.vars, vars));
}
/* Set the points-to solution *PT to point only to the variable VAR. */
memset (pt, 0, sizeof (struct pt_solution));
pt->vars = BITMAP_GGC_ALLOC ();
bitmap_set_bit (pt->vars, DECL_PT_UID (var));
- pt->vars_contains_global = is_global_var (var);
+ pt->vars_contains_nonlocal = is_global_var (var);
+ pt->vars_contains_escaped
+ = (cfun->gimple_df->escaped.anything
+ || bitmap_bit_p (cfun->gimple_df->escaped.vars, DECL_PT_UID (var)));
}
/* Computes the union of the points-to solutions *DEST and *SRC and
dest->escaped |= src->escaped;
dest->ipa_escaped |= src->ipa_escaped;
dest->null |= src->null;
- dest->vars_contains_global |= src->vars_contains_global;
+ dest->vars_contains_nonlocal |= src->vars_contains_nonlocal;
+ dest->vars_contains_escaped |= src->vars_contains_escaped;
+ dest->vars_contains_escaped_heap |= src->vars_contains_escaped_heap;
if (!src->vars)
return;
{
if (pt->anything
|| pt->nonlocal
- || pt->vars_contains_global)
+ || pt->vars_contains_nonlocal
+ /* The following is a hack to make the malloc escape hack work.
+ In reality we'd need different sets for escaped-through-return
+ and escaped-to-callees and passes would need to be updated. */
+ || pt->vars_contains_escaped_heap)
return true;
+ /* 'escaped' is also a placeholder so we have to look into it. */
if (pt->escaped)
return pt_solution_includes_global (&cfun->gimple_df->escaped);
any global memory they alias. */
if ((pt1->nonlocal
&& (pt2->nonlocal
- || pt2->vars_contains_global))
+ || pt2->vars_contains_nonlocal))
|| (pt2->nonlocal
- && pt1->vars_contains_global))
+ && pt1->vars_contains_nonlocal))
return true;
- /* Check the escaped solution if required. */
- if ((pt1->escaped || pt2->escaped)
- && !pt_solution_empty_p (&cfun->gimple_df->escaped))
- {
- /* If both point to escaped memory and that solution
- is not empty they alias. */
- if (pt1->escaped && pt2->escaped)
- return true;
-
- /* If either points to escaped memory see if the escaped solution
- intersects with the other. */
- if ((pt1->escaped
- && pt_solutions_intersect_1 (&cfun->gimple_df->escaped, pt2))
- || (pt2->escaped
- && pt_solutions_intersect_1 (&cfun->gimple_df->escaped, pt1)))
- return true;
- }
+ /* If either points to all escaped memory and the other points to
+ any escaped memory they alias. */
+ if ((pt1->escaped
+ && (pt2->escaped
+ || pt2->vars_contains_escaped))
+ || (pt2->escaped
+ && pt1->vars_contains_escaped))
+ return true;
/* Check the escaped solution if required.
??? Do we need to check the local against the IPA escaped sets? */
stats.num_implicit_edges);
}
- for (i = 0; i < varmap.length (); i++)
+ for (i = 1; i < varmap.length (); i++)
{
varinfo_t vi = get_varinfo (i);
if (!vi->may_have_pointers)
struct constraint_expr lhs, rhs;
varinfo_t var_anything;
varinfo_t var_nothing;
- varinfo_t var_readonly;
+ varinfo_t var_string;
varinfo_t var_escaped;
varinfo_t var_nonlocal;
varinfo_t var_storedanything;
varinfo_t var_integer;
+ /* Variable ID zero is reserved and should be NULL. */
+ varmap.safe_push (NULL);
+
/* Create the NULL variable, used to represent that a variable points
to NULL. */
var_nothing = new_var_info (NULL_TREE, "NULL");
var_anything->is_artificial_var = 1;
var_anything->size = ~0;
var_anything->offset = 0;
- var_anything->next = NULL;
var_anything->fullsize = ~0;
var_anything->is_special_var = 1;
but this one are redundant. */
constraints.safe_push (new_constraint (lhs, rhs));
- /* Create the READONLY variable, used to represent that a variable
- points to readonly memory. */
- var_readonly = new_var_info (NULL_TREE, "READONLY");
- gcc_assert (var_readonly->id == readonly_id);
- var_readonly->is_artificial_var = 1;
- var_readonly->offset = 0;
- var_readonly->size = ~0;
- var_readonly->fullsize = ~0;
- var_readonly->next = NULL;
- var_readonly->is_special_var = 1;
-
- /* readonly memory points to anything, in order to make deref
- easier. In reality, it points to anything the particular
- readonly variable can point to, but we don't track this
- separately. */
- lhs.type = SCALAR;
- lhs.var = readonly_id;
- lhs.offset = 0;
- rhs.type = ADDRESSOF;
- rhs.var = readonly_id; /* FIXME */
- rhs.offset = 0;
- process_constraint (new_constraint (lhs, rhs));
+ /* Create the STRING variable, used to represent that a variable
+ points to a string literal. String literals don't contain
+ pointers so STRING doesn't point to anything. */
+ var_string = new_var_info (NULL_TREE, "STRING");
+ gcc_assert (var_string->id == string_id);
+ var_string->is_artificial_var = 1;
+ var_string->offset = 0;
+ var_string->size = ~0;
+ var_string->fullsize = ~0;
+ var_string->is_special_var = 1;
+ var_string->may_have_pointers = 0;
/* Create the ESCAPED variable, used to represent the set of escaped
memory. */
var_integer->size = ~0;
var_integer->fullsize = ~0;
var_integer->offset = 0;
- var_integer->next = NULL;
var_integer->is_special_var = 1;
/* INTEGER = ANYTHING, because we don't know where a dereference of
sizeof (struct variable_info), 30);
constraints.create (8);
varmap.create (8);
- vi_for_tree = pointer_map_create ();
- call_stmt_vars = pointer_map_create ();
+ vi_for_tree = new hash_map<tree, varinfo_t>;
+ call_stmt_vars = new hash_map<gimple, varinfo_t>;
memset (&stats, 0, sizeof (stats));
- shared_bitmap_table = htab_create (511, shared_bitmap_hash,
- shared_bitmap_eq, free);
+ shared_bitmap_table = new hash_table<shared_bitmap_hasher> (511);
init_base_vars ();
gcc_obstack_init (&fake_var_decl_obstack);
+
+ final_solutions = new hash_map<varinfo_t, pt_solution *>;
+ gcc_obstack_init (&final_solutions_obstack);
}
/* Remove the REF and ADDRESS edges from GRAPH, as well as all the
/* Clear the implicit ref and address nodes from the successor
lists. */
- for (i = 0; i < FIRST_REF_NODE; i++)
+ for (i = 1; i < FIRST_REF_NODE; i++)
{
if (graph->succs[i])
bitmap_clear_range (graph->succs[i], FIRST_REF_NODE,
}
/* Free the successor list for the non-ref nodes. */
- for (i = FIRST_REF_NODE; i < graph->size; i++)
+ for (i = FIRST_REF_NODE + 1; i < graph->size; i++)
{
if (graph->succs[i])
BITMAP_FREE (graph->succs[i]);
init_alias_vars ();
- intra_create_variable_infos ();
+ intra_create_variable_infos (cfun);
/* Now walk all statements and build the constraint set. */
- FOR_EACH_BB (bb)
+ FOR_EACH_BB_FN (bb, cfun)
{
gimple_stmt_iterator gsi;
gimple phi = gsi_stmt (gsi);
if (! virtual_operand_p (gimple_phi_result (phi)))
- find_func_aliases (phi);
+ find_func_aliases (cfun, phi);
}
for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
{
gimple stmt = gsi_stmt (gsi);
- find_func_aliases (stmt);
+ find_func_aliases (cfun, stmt);
}
}
solve_constraints ();
/* Compute the points-to set for ESCAPED used for call-clobber analysis. */
- find_what_var_points_to (get_varinfo (escaped_id),
- &cfun->gimple_df->escaped);
+ cfun->gimple_df->escaped = find_what_var_points_to (get_varinfo (escaped_id));
/* Make sure the ESCAPED solution (which is used as placeholder in
other solutions) does not reference itself. This simplifies
points-to solution queries. */
cfun->gimple_df->escaped.escaped = 0;
- /* Mark escaped HEAP variables as global. */
- FOR_EACH_VEC_ELT (varmap, i, vi)
- if (vi->is_heap_var
- && !vi->is_global_var)
- DECL_EXTERNAL (vi->decl) = vi->is_global_var
- = pt_solution_includes (&cfun->gimple_df->escaped, vi->decl);
-
/* Compute the points-to sets for pointer SSA_NAMEs. */
for (i = 0; i < num_ssa_names; ++i)
{
}
/* Compute the call-used/clobbered sets. */
- FOR_EACH_BB (bb)
+ FOR_EACH_BB_FN (bb, cfun)
{
gimple_stmt_iterator gsi;
memset (pt, 0, sizeof (struct pt_solution));
else if ((vi = lookup_call_use_vi (stmt)) != NULL)
{
- find_what_var_points_to (vi, pt);
+ *pt = find_what_var_points_to (vi);
/* Escaped (and thus nonlocal) variables are always
implicitly used by calls. */
/* ??? ESCAPED can be empty even though NONLOCAL
memset (pt, 0, sizeof (struct pt_solution));
else if ((vi = lookup_call_clobber_vi (stmt)) != NULL)
{
- find_what_var_points_to (vi, pt);
+ *pt = find_what_var_points_to (vi);
/* Escaped (and thus nonlocal) variables are always
implicitly clobbered by calls. */
/* ??? ESCAPED can be empty even though NONLOCAL
{
unsigned int i;
- htab_delete (shared_bitmap_table);
+ delete shared_bitmap_table;
+ shared_bitmap_table = NULL;
if (dump_file && (dump_flags & TDF_STATS))
fprintf (dump_file, "Points to sets created:%d\n",
stats.points_to_sets_created);
- pointer_map_destroy (vi_for_tree);
- pointer_map_destroy (call_stmt_vars);
+ delete vi_for_tree;
+ delete call_stmt_vars;
bitmap_obstack_release (&pta_obstack);
constraints.release ();
free_alloc_pool (constraint_pool);
obstack_free (&fake_var_decl_obstack, NULL);
+
+ delete final_solutions;
+ obstack_free (&final_solutions_obstack, NULL);
}
return 0;
}
-static bool
-gate_tree_pta (void)
-{
- return flag_tree_pta;
-}
-
/* A dummy pass to cause points-to information to be computed via
TODO_rebuild_alias. */
-struct gimple_opt_pass pass_build_alias =
-{
- {
- GIMPLE_PASS,
- "alias", /* name */
- OPTGROUP_NONE, /* optinfo_flags */
- gate_tree_pta, /* gate */
- NULL, /* execute */
- NULL, /* sub */
- NULL, /* next */
- 0, /* static_pass_number */
- TV_NONE, /* tv_id */
- PROP_cfg | PROP_ssa, /* properties_required */
- 0, /* properties_provided */
- 0, /* properties_destroyed */
- 0, /* todo_flags_start */
- TODO_rebuild_alias /* todo_flags_finish */
- }
+namespace {
+
+const pass_data pass_data_build_alias =
+{
+ GIMPLE_PASS, /* type */
+ "alias", /* name */
+ OPTGROUP_NONE, /* optinfo_flags */
+ TV_NONE, /* tv_id */
+ ( PROP_cfg | PROP_ssa ), /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_rebuild_alias, /* todo_flags_finish */
};
+class pass_build_alias : public gimple_opt_pass
+{
+public:
+ pass_build_alias (gcc::context *ctxt)
+ : gimple_opt_pass (pass_data_build_alias, ctxt)
+ {}
+
+ /* opt_pass methods: */
+ virtual bool gate (function *) { return flag_tree_pta; }
+
+}; // class pass_build_alias
+
+} // anon namespace
+
+gimple_opt_pass *
+make_pass_build_alias (gcc::context *ctxt)
+{
+ return new pass_build_alias (ctxt);
+}
+
/* A dummy pass to cause points-to information to be computed via
TODO_rebuild_alias. */
-struct gimple_opt_pass pass_build_ealias =
-{
- {
- GIMPLE_PASS,
- "ealias", /* name */
- OPTGROUP_NONE, /* optinfo_flags */
- gate_tree_pta, /* gate */
- NULL, /* execute */
- NULL, /* sub */
- NULL, /* next */
- 0, /* static_pass_number */
- TV_NONE, /* tv_id */
- PROP_cfg | PROP_ssa, /* properties_required */
- 0, /* properties_provided */
- 0, /* properties_destroyed */
- 0, /* todo_flags_start */
- TODO_rebuild_alias /* todo_flags_finish */
- }
+namespace {
+
+const pass_data pass_data_build_ealias =
+{
+ GIMPLE_PASS, /* type */
+ "ealias", /* name */
+ OPTGROUP_NONE, /* optinfo_flags */
+ TV_NONE, /* tv_id */
+ ( PROP_cfg | PROP_ssa ), /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_rebuild_alias, /* todo_flags_finish */
};
+class pass_build_ealias : public gimple_opt_pass
+{
+public:
+ pass_build_ealias (gcc::context *ctxt)
+ : gimple_opt_pass (pass_data_build_ealias, ctxt)
+ {}
-/* Return true if we should execute IPA PTA. */
-static bool
-gate_ipa_pta (void)
+ /* opt_pass methods: */
+ virtual bool gate (function *) { return flag_tree_pta; }
+
+}; // class pass_build_ealias
+
+} // anon namespace
+
+gimple_opt_pass *
+make_pass_build_ealias (gcc::context *ctxt)
{
- return (optimize
- && flag_ipa_pta
- /* Don't bother doing anything if the program has errors. */
- && !seen_error ());
+ return new pass_build_ealias (ctxt);
}
+
/* IPA PTA solutions for ESCAPED. */
struct pt_solution ipa_escaped_pt
- = { true, false, false, false, false, false, NULL };
+ = { true, false, false, false, false, false, false, false, NULL };
/* Associate node with varinfo DATA. Worker for
cgraph_for_node_and_aliases. */
static bool
associate_varinfo_to_alias (struct cgraph_node *node, void *data)
{
- if (node->alias || node->thunk.thunk_p)
- insert_vi_for_tree (node->symbol.decl, (varinfo_t)data);
+ if ((node->alias || node->thunk.thunk_p)
+ && node->analyzed)
+ insert_vi_for_tree (node->decl, (varinfo_t)data);
return false;
}
ipa_pta_execute (void)
{
struct cgraph_node *node;
- struct varpool_node *var;
+ varpool_node *var;
int from;
in_ipa_mode = 1;
if (dump_file && (dump_flags & TDF_DETAILS))
{
- dump_symtab (dump_file);
+ symtab_node::dump_table (dump_file);
fprintf (dump_file, "\n");
}
/* Nodes without a body are not interesting. Especially do not
visit clones at this point for now - we get duplicate decls
there for inline clones at least. */
- if (!cgraph_function_with_gimple_body_p (node))
+ if (!node->has_gimple_body_p () || node->clone_of)
continue;
+ node->get_body ();
gcc_assert (!node->clone_of);
- vi = create_function_info_for (node->symbol.decl,
- alias_get_name (node->symbol.decl));
- cgraph_for_node_and_aliases (node, associate_varinfo_to_alias, vi, true);
+ vi = create_function_info_for (node->decl,
+ alias_get_name (node->decl));
+ node->call_for_symbol_thunks_and_aliases
+ (associate_varinfo_to_alias, vi, true);
}
/* Create constraints for global variables and their initializers. */
FOR_EACH_VARIABLE (var)
{
- if (var->alias)
+ if (var->alias && var->analyzed)
continue;
- get_vi_for_tree (var->symbol.decl);
+ get_vi_for_tree (var->decl);
}
if (dump_file)
basic_block bb;
/* Nodes without a body are not interesting. */
- if (!cgraph_function_with_gimple_body_p (node))
+ if (!node->has_gimple_body_p () || node->clone_of)
continue;
if (dump_file)
{
fprintf (dump_file,
- "Generating constraints for %s", cgraph_node_name (node));
- if (DECL_ASSEMBLER_NAME_SET_P (node->symbol.decl))
+ "Generating constraints for %s", node->name ());
+ if (DECL_ASSEMBLER_NAME_SET_P (node->decl))
fprintf (dump_file, " (%s)",
IDENTIFIER_POINTER
- (DECL_ASSEMBLER_NAME (node->symbol.decl)));
+ (DECL_ASSEMBLER_NAME (node->decl)));
fprintf (dump_file, "\n");
}
- func = DECL_STRUCT_FUNCTION (node->symbol.decl);
- push_cfun (func);
+ func = DECL_STRUCT_FUNCTION (node->decl);
+ gcc_assert (cfun == NULL);
/* For externally visible or attribute used annotated functions use
local constraints for their arguments.
For local functions we see all callers and thus do not need initial
constraints for parameters. */
- if (node->symbol.used_from_other_partition
- || node->symbol.externally_visible
- || node->symbol.force_output)
+ if (node->used_from_other_partition
+ || node->externally_visible
+ || node->force_output)
{
- intra_create_variable_infos ();
+ intra_create_variable_infos (func);
/* We also need to make function return values escape. Nothing
escapes by returning from main though. */
- if (!MAIN_NAME_P (DECL_NAME (node->symbol.decl)))
+ if (!MAIN_NAME_P (DECL_NAME (node->decl)))
{
varinfo_t fi, rvi;
- fi = lookup_vi_for_tree (node->symbol.decl);
+ fi = lookup_vi_for_tree (node->decl);
rvi = first_vi_for_offset (fi, fi_result);
if (rvi && rvi->offset == fi_result)
{
gimple phi = gsi_stmt (gsi);
if (! virtual_operand_p (gimple_phi_result (phi)))
- find_func_aliases (phi);
+ find_func_aliases (func, phi);
}
for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
{
gimple stmt = gsi_stmt (gsi);
- find_func_aliases (stmt);
- find_func_clobbers (stmt);
+ find_func_aliases (func, stmt);
+ find_func_clobbers (func, stmt);
}
}
- pop_cfun ();
-
if (dump_file)
{
fprintf (dump_file, "\n");
??? Note that the computed escape set is not correct
for the whole unit as we fail to consider graph edges to
externally visible functions. */
- find_what_var_points_to (get_varinfo (escaped_id), &ipa_escaped_pt);
+ ipa_escaped_pt = find_what_var_points_to (get_varinfo (escaped_id));
/* Make sure the ESCAPED solution (which is used as placeholder in
other solutions) does not reference itself. This simplifies
tree ptr;
struct function *fn;
unsigned i;
- varinfo_t fi;
basic_block bb;
- struct pt_solution uses, clobbers;
- struct cgraph_edge *e;
/* Nodes without a body are not interesting. */
- if (!cgraph_function_with_gimple_body_p (node))
+ if (!node->has_gimple_body_p () || node->clone_of)
continue;
- fn = DECL_STRUCT_FUNCTION (node->symbol.decl);
+ fn = DECL_STRUCT_FUNCTION (node->decl);
/* Compute the points-to sets for pointer SSA_NAMEs. */
FOR_EACH_VEC_ELT (*fn->gimple_df->ssa_names, i, ptr)
find_what_p_points_to (ptr);
}
- /* Compute the call-use and call-clobber sets for all direct calls. */
- fi = lookup_vi_for_tree (node->symbol.decl);
- gcc_assert (fi->is_fn_info);
- find_what_var_points_to (first_vi_for_offset (fi, fi_clobbers),
- &clobbers);
- find_what_var_points_to (first_vi_for_offset (fi, fi_uses), &uses);
- for (e = node->callers; e; e = e->next_caller)
- {
- if (!e->call_stmt)
- continue;
-
- *gimple_call_clobber_set (e->call_stmt) = clobbers;
- *gimple_call_use_set (e->call_stmt) = uses;
- }
-
/* Compute the call-use and call-clobber sets for indirect calls
and calls to external functions. */
FOR_EACH_BB_FN (bb, fn)
{
gimple stmt = gsi_stmt (gsi);
struct pt_solution *pt;
- varinfo_t vi;
+ varinfo_t vi, fi;
tree decl;
if (!is_gimple_call (stmt))
continue;
- /* Handle direct calls to external functions. */
+ /* Handle direct calls to functions with body. */
decl = gimple_call_fndecl (stmt);
if (decl
- && (!(fi = lookup_vi_for_tree (decl))
- || !fi->is_fn_info))
+ && (fi = lookup_vi_for_tree (decl))
+ && fi->is_fn_info)
+ {
+ *gimple_call_clobber_set (stmt)
+ = find_what_var_points_to
+ (first_vi_for_offset (fi, fi_clobbers));
+ *gimple_call_use_set (stmt)
+ = find_what_var_points_to
+ (first_vi_for_offset (fi, fi_uses));
+ }
+ /* Handle direct calls to external functions. */
+ else if (decl)
{
pt = gimple_call_use_set (stmt);
if (gimple_call_flags (stmt) & ECF_CONST)
memset (pt, 0, sizeof (struct pt_solution));
else if ((vi = lookup_call_use_vi (stmt)) != NULL)
{
- find_what_var_points_to (vi, pt);
+ *pt = find_what_var_points_to (vi);
/* Escaped (and thus nonlocal) variables are always
implicitly used by calls. */
/* ??? ESCAPED can be empty even though NONLOCAL
memset (pt, 0, sizeof (struct pt_solution));
else if ((vi = lookup_call_clobber_vi (stmt)) != NULL)
{
- find_what_var_points_to (vi, pt);
+ *pt = find_what_var_points_to (vi);
/* Escaped (and thus nonlocal) variables are always
implicitly clobbered by calls. */
/* ??? ESCAPED can be empty even though NONLOCAL
pt->nonlocal = 1;
}
}
-
/* Handle indirect calls. */
- if (!decl
- && (fi = get_fi_for_callee (stmt)))
+ else if (!decl
+ && (fi = get_fi_for_callee (stmt)))
{
/* We need to accumulate all clobbers/uses of all possible
callees. */
if (!uses->anything)
{
- find_what_var_points_to
- (first_vi_for_offset (vi, fi_uses), &sol);
+ sol = find_what_var_points_to
+ (first_vi_for_offset (vi, fi_uses));
pt_solution_ior_into (uses, &sol);
}
if (!clobbers->anything)
{
- find_what_var_points_to
- (first_vi_for_offset (vi, fi_clobbers), &sol);
+ sol = find_what_var_points_to
+ (first_vi_for_offset (vi, fi_clobbers));
pt_solution_ior_into (clobbers, &sol);
}
}
return 0;
}
-struct simple_ipa_opt_pass pass_ipa_pta =
-{
- {
- SIMPLE_IPA_PASS,
- "pta", /* name */
- OPTGROUP_NONE, /* optinfo_flags */
- gate_ipa_pta, /* gate */
- ipa_pta_execute, /* execute */
- NULL, /* sub */
- NULL, /* next */
- 0, /* static_pass_number */
- TV_IPA_PTA, /* tv_id */
- 0, /* properties_required */
- 0, /* properties_provided */
- 0, /* properties_destroyed */
- 0, /* todo_flags_start */
- TODO_update_ssa /* todo_flags_finish */
- }
+namespace {
+
+const pass_data pass_data_ipa_pta =
+{
+ SIMPLE_IPA_PASS, /* type */
+ "pta", /* name */
+ OPTGROUP_NONE, /* optinfo_flags */
+ TV_IPA_PTA, /* tv_id */
+ 0, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ 0, /* todo_flags_finish */
};
+
+class pass_ipa_pta : public simple_ipa_opt_pass
+{
+public:
+ pass_ipa_pta (gcc::context *ctxt)
+ : simple_ipa_opt_pass (pass_data_ipa_pta, ctxt)
+ {}
+
+ /* opt_pass methods: */
+ virtual bool gate (function *)
+ {
+ return (optimize
+ && flag_ipa_pta
+ /* Don't bother doing anything if the program has errors. */
+ && !seen_error ());
+ }
+
+ virtual unsigned int execute (function *) { return ipa_pta_execute (); }
+
+}; // class pass_ipa_pta
+
+} // anon namespace
+
+simple_ipa_opt_pass *
+make_pass_ipa_pta (gcc::context *ctxt)
+{
+ return new pass_ipa_pta (ctxt);
+}