tree-ssa-structalias.c [plain text]
#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "ggc.h"
#include "obstack.h"
#include "bitmap.h"
#include "flags.h"
#include "rtl.h"
#include "tm_p.h"
#include "hard-reg-set.h"
#include "basic-block.h"
#include "output.h"
#include "errors.h"
#include "diagnostic.h"
#include "tree.h"
#include "c-common.h"
#include "tree-flow.h"
#include "tree-inline.h"
#include "varray.h"
#include "c-tree.h"
#include "tree-gimple.h"
#include "hashtab.h"
#include "function.h"
#include "cgraph.h"
#include "tree-pass.h"
#include "timevar.h"
#include "alloc-pool.h"
#include "splay-tree.h"
#include "params.h"
#include "tree-ssa-structalias.h"
#include "cgraph.h"
static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map)))
htab_t heapvar_for_stmt;
tree nonlocal_all;
static bool use_field_sensitive = true;
static int in_ipa_mode = 0;
static bitmap_obstack predbitmap_obstack;
static bitmap_obstack ptabitmap_obstack;
static bitmap_obstack iteration_obstack;
static unsigned int create_variable_info_for (tree, const char *);
static void build_constraint_graph (void);
DEF_VEC_P(constraint_t);
DEF_VEC_ALLOC_P(constraint_t,heap);
#define EXECUTE_IF_IN_NONNULL_BITMAP(a, b, c, d) \
if (a) \
EXECUTE_IF_SET_IN_BITMAP (a, b, c, d)
static struct constraint_stats
{
unsigned int total_vars;
unsigned int collapsed_vars;
unsigned int unified_vars_static;
unsigned int unified_vars_dynamic;
unsigned int iterations;
unsigned int num_edges;
} stats;
struct variable_info
{
unsigned int id;
const char *name;
tree decl;
unsigned HOST_WIDE_INT offset;
unsigned HOST_WIDE_INT size;
unsigned HOST_WIDE_INT fullsize;
struct variable_info *next;
unsigned int node;
unsigned int address_taken:1;
unsigned int indirect_target:1;
unsigned int directly_dereferenced:1;
unsigned int is_artificial_var:1;
unsigned int is_special_var:1;
unsigned int is_unknown_size_var:1;
unsigned int has_union:1;
unsigned int is_heap_var:1;
bitmap solution;
bitmap variables;
VEC(constraint_t,heap) *complex;
struct variable_info *collapsed_to;
};
typedef struct variable_info *varinfo_t;
static varinfo_t first_vi_for_offset (varinfo_t, unsigned HOST_WIDE_INT);
static alloc_pool variable_info_pool;
DEF_VEC_P(varinfo_t);
DEF_VEC_ALLOC_P(varinfo_t, heap);
static VEC(varinfo_t,heap) *varmap;
static inline varinfo_t
get_varinfo (unsigned int n)
{
return VEC_index(varinfo_t, varmap, n);
}
static inline varinfo_t
get_varinfo_fc (unsigned int n)
{
varinfo_t v = VEC_index(varinfo_t, varmap, n);
if (v->collapsed_to)
return v->collapsed_to;
return v;
}
static varinfo_t var_anything;
static tree anything_tree;
static unsigned int anything_id;
static varinfo_t var_nothing;
static tree nothing_tree;
static unsigned int nothing_id;
static varinfo_t var_readonly;
static tree readonly_tree;
static unsigned int readonly_id;
static varinfo_t var_integer;
static tree integer_tree;
static unsigned int integer_id;
static varinfo_t var_escaped_vars;
static tree escaped_vars_tree;
static unsigned int escaped_vars_id;
static unsigned int nonlocal_vars_id;
static tree
heapvar_lookup (tree from)
{
struct tree_map *h, in;
in.from = from;
h = htab_find_with_hash (heapvar_for_stmt, &in, htab_hash_pointer (from));
if (h)
return h->to;
return NULL_TREE;
}
static void
heapvar_insert (tree from, tree to)
{
struct tree_map *h;
void **loc;
h = ggc_alloc (sizeof (struct tree_map));
h->hash = htab_hash_pointer (from);
h->from = from;
h->to = to;
loc = htab_find_slot_with_hash (heapvar_for_stmt, h, h->hash, INSERT);
*(struct tree_map **) loc = h;
}
static varinfo_t
new_var_info (tree t, unsigned int id, const char *name, unsigned int node)
{
varinfo_t ret = pool_alloc (variable_info_pool);
ret->id = id;
ret->name = name;
ret->decl = t;
ret->node = node;
ret->address_taken = false;
ret->indirect_target = false;
ret->directly_dereferenced = false;
ret->is_artificial_var = false;
ret->is_heap_var = false;
ret->is_special_var = false;
ret->is_unknown_size_var = false;
ret->has_union = false;
ret->solution = BITMAP_ALLOC (&ptabitmap_obstack);
ret->variables = BITMAP_ALLOC (&ptabitmap_obstack);
ret->complex = NULL;
ret->next = NULL;
ret->collapsed_to = NULL;
return ret;
}
typedef enum {SCALAR, DEREF, ADDRESSOF} constraint_expr_type;
struct constraint_expr
{
constraint_expr_type type;
unsigned int var;
unsigned HOST_WIDE_INT offset;
};
typedef struct constraint_expr ce_s;
DEF_VEC_O(ce_s);
DEF_VEC_ALLOC_O(ce_s, heap);
static void get_constraint_for (tree, VEC(ce_s, heap) **);
static void do_deref (VEC (ce_s, heap) **);
struct constraint
{
struct constraint_expr lhs;
struct constraint_expr rhs;
};
static VEC(constraint_t,heap) *constraints;
static alloc_pool constraint_pool;
struct constraint_edge
{
unsigned int dest;
bitmap weights;
};
typedef struct constraint_edge *constraint_edge_t;
static alloc_pool constraint_edge_pool;
static constraint_edge_t
new_constraint_edge (unsigned int dest)
{
constraint_edge_t ret = pool_alloc (constraint_edge_pool);
ret->dest = dest;
ret->weights = NULL;
return ret;
}
DEF_VEC_P(constraint_edge_t);
DEF_VEC_ALLOC_P(constraint_edge_t,heap);
struct constraint_graph
{
bitmap *zero_weight_succs;
bitmap *zero_weight_preds;
VEC(constraint_edge_t,heap) **succs;
VEC(constraint_edge_t,heap) **preds;
};
typedef struct constraint_graph *constraint_graph_t;
static constraint_graph_t graph;
static int graph_size;
static constraint_t
new_constraint (const struct constraint_expr lhs,
const struct constraint_expr rhs)
{
constraint_t ret = pool_alloc (constraint_pool);
ret->lhs = lhs;
ret->rhs = rhs;
return ret;
}
void
dump_constraint (FILE *file, constraint_t c)
{
if (c->lhs.type == ADDRESSOF)
fprintf (file, "&");
else if (c->lhs.type == DEREF)
fprintf (file, "*");
fprintf (file, "%s", get_varinfo_fc (c->lhs.var)->name);
if (c->lhs.offset != 0)
fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->lhs.offset);
fprintf (file, " = ");
if (c->rhs.type == ADDRESSOF)
fprintf (file, "&");
else if (c->rhs.type == DEREF)
fprintf (file, "*");
fprintf (file, "%s", get_varinfo_fc (c->rhs.var)->name);
if (c->rhs.offset != 0)
fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->rhs.offset);
fprintf (file, "\n");
}
void
debug_constraint (constraint_t c)
{
dump_constraint (stderr, c);
}
void
dump_constraints (FILE *file)
{
int i;
constraint_t c;
for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
dump_constraint (file, c);
}
void
debug_constraints (void)
{
dump_constraints (stderr);
}
static bool
constraint_expr_equal (struct constraint_expr a, struct constraint_expr b)
{
return a.type == b.type && a.var == b.var && a.offset == b.offset;
}
static bool
constraint_expr_less (struct constraint_expr a, struct constraint_expr b)
{
if (a.type == b.type)
{
if (a.var == b.var)
return a.offset < b.offset;
else
return a.var < b.var;
}
else
return a.type < b.type;
}
static bool
constraint_less (const constraint_t a, const constraint_t b)
{
if (constraint_expr_less (a->lhs, b->lhs))
return true;
else if (constraint_expr_less (b->lhs, a->lhs))
return false;
else
return constraint_expr_less (a->rhs, b->rhs);
}
static bool
constraint_equal (struct constraint a, struct constraint b)
{
return constraint_expr_equal (a.lhs, b.lhs)
&& constraint_expr_equal (a.rhs, b.rhs);
}
static constraint_t
constraint_vec_find (VEC(constraint_t,heap) *vec,
struct constraint lookfor)
{
unsigned int place;
constraint_t found;
if (vec == NULL)
return NULL;
place = VEC_lower_bound (constraint_t, vec, &lookfor, constraint_less);
if (place >= VEC_length (constraint_t, vec))
return NULL;
found = VEC_index (constraint_t, vec, place);
if (!constraint_equal (*found, lookfor))
return NULL;
return found;
}
static void
constraint_set_union (VEC(constraint_t,heap) **to,
VEC(constraint_t,heap) **from)
{
int i;
constraint_t c;
for (i = 0; VEC_iterate (constraint_t, *from, i, c); i++)
{
if (constraint_vec_find (*to, *c) == NULL)
{
unsigned int place = VEC_lower_bound (constraint_t, *to, c,
constraint_less);
VEC_safe_insert (constraint_t, heap, *to, place, c);
}
}
}
static void
solution_set_add (bitmap set, unsigned HOST_WIDE_INT offset)
{
bitmap result = BITMAP_ALLOC (&iteration_obstack);
unsigned int i;
bitmap_iterator bi;
EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
{
if ((get_varinfo (i)->offset + offset) < get_varinfo (i)->fullsize)
{
unsigned HOST_WIDE_INT fieldoffset = get_varinfo (i)->offset + offset;
varinfo_t v = first_vi_for_offset (get_varinfo (i), fieldoffset);
if (!v)
continue;
bitmap_set_bit (result, v->id);
}
else if (get_varinfo (i)->is_artificial_var
|| get_varinfo (i)->has_union
|| get_varinfo (i)->is_unknown_size_var)
{
bitmap_set_bit (result, i);
}
}
bitmap_copy (set, result);
BITMAP_FREE (result);
}
static bool
set_union_with_increment (bitmap to, bitmap from, unsigned HOST_WIDE_INT inc)
{
if (inc == 0)
return bitmap_ior_into (to, from);
else
{
bitmap tmp;
bool res;
tmp = BITMAP_ALLOC (&iteration_obstack);
bitmap_copy (tmp, from);
solution_set_add (tmp, inc);
res = bitmap_ior_into (to, tmp);
BITMAP_FREE (tmp);
return res;
}
}
static void
insert_into_complex (unsigned int var, constraint_t c)
{
varinfo_t vi = get_varinfo (var);
unsigned int place = VEC_lower_bound (constraint_t, vi->complex, c,
constraint_less);
VEC_safe_insert (constraint_t, heap, vi->complex, place, c);
}
static bool
constraint_edge_equal (struct constraint_edge a, struct constraint_edge b)
{
return a.dest == b.dest;
}
static bool
constraint_edge_less (const constraint_edge_t a, const constraint_edge_t b)
{
if (a->dest < b->dest)
return true;
return false;
}
static constraint_edge_t
constraint_edge_vec_find (VEC(constraint_edge_t,heap) *vec,
struct constraint_edge lookfor)
{
unsigned int place;
constraint_edge_t edge = NULL;
place = VEC_lower_bound (constraint_edge_t, vec, &lookfor,
constraint_edge_less);
if (place >= VEC_length (constraint_edge_t, vec))
return NULL;
edge = VEC_index (constraint_edge_t, vec, place);
if (!constraint_edge_equal (*edge, lookfor))
return NULL;
return edge;
}
static void
condense_varmap_nodes (unsigned int to, unsigned int src)
{
varinfo_t tovi = get_varinfo (to);
varinfo_t srcvi = get_varinfo (src);
unsigned int i;
constraint_t c;
bitmap_iterator bi;
srcvi->node = to;
EXECUTE_IF_SET_IN_BITMAP (srcvi->variables, 0, i, bi)
get_varinfo (i)->node = to;
bitmap_set_bit (tovi->variables, src);
bitmap_ior_into (tovi->variables, srcvi->variables);
bitmap_clear (srcvi->variables);
for (i = 0; VEC_iterate (constraint_t, srcvi->complex, i, c); i++)
{
if (c->rhs.type == DEREF)
c->rhs.var = to;
else
c->lhs.var = to;
}
constraint_set_union (&tovi->complex, &srcvi->complex);
VEC_free (constraint_t, heap, srcvi->complex);
srcvi->complex = NULL;
}
static void
erase_graph_self_edge (constraint_graph_t graph, unsigned int src)
{
VEC(constraint_edge_t,heap) *predvec = graph->preds[src];
VEC(constraint_edge_t,heap) *succvec = graph->succs[src];
struct constraint_edge edge;
unsigned int place;
edge.dest = src;
place = VEC_lower_bound (constraint_edge_t, succvec, &edge,
constraint_edge_less);
#ifdef ENABLE_CHECKING
{
constraint_edge_t tmp = VEC_index (constraint_edge_t, succvec, place);
gcc_assert (constraint_edge_equal (*tmp, edge));
}
#endif
VEC_ordered_remove (constraint_edge_t, succvec, place);
place = VEC_lower_bound (constraint_edge_t, predvec, &edge,
constraint_edge_less);
#ifdef ENABLE_CHECKING
{
constraint_edge_t tmp = VEC_index (constraint_edge_t, predvec, place);
gcc_assert (constraint_edge_equal (*tmp, edge));
}
#endif
VEC_ordered_remove (constraint_edge_t, predvec, place);
}
static void
clear_edges_for_node (constraint_graph_t graph, unsigned int node)
{
VEC(constraint_edge_t,heap) *succvec = graph->succs[node];
VEC(constraint_edge_t,heap) *predvec = graph->preds[node];
bitmap_iterator bi;
unsigned int j;
constraint_edge_t c = NULL;
int i;
EXECUTE_IF_IN_NONNULL_BITMAP (graph->zero_weight_succs[node], 0, j, bi)
if (j != node)
bitmap_clear_bit (graph->zero_weight_preds[j], node);
for (i = 0; VEC_iterate (constraint_edge_t, succvec, i, c); i++)
if (c->dest != node)
{
unsigned int place;
struct constraint_edge lookfor;
constraint_edge_t result;
lookfor.dest = node;
place = VEC_lower_bound (constraint_edge_t, graph->preds[c->dest],
&lookfor, constraint_edge_less);
result = VEC_ordered_remove (constraint_edge_t,
graph->preds[c->dest], place);
pool_free (constraint_edge_pool, result);
}
EXECUTE_IF_IN_NONNULL_BITMAP (graph->zero_weight_preds[node], 0, j, bi)
if (j != node)
bitmap_clear_bit (graph->zero_weight_succs[j], node);
for (i =0; VEC_iterate (constraint_edge_t, predvec, i, c); i++)
if (c->dest != node)
{
unsigned int place;
struct constraint_edge lookfor;
constraint_edge_t result;
lookfor.dest = node;
place = VEC_lower_bound (constraint_edge_t, graph->succs[c->dest],
&lookfor, constraint_edge_less);
result = VEC_ordered_remove (constraint_edge_t,
graph->succs[c->dest], place);
pool_free (constraint_edge_pool, result);
}
if (graph->zero_weight_preds[node])
{
BITMAP_FREE (graph->zero_weight_preds[node]);
graph->zero_weight_preds[node] = NULL;
}
if (graph->zero_weight_succs[node])
{
BITMAP_FREE (graph->zero_weight_succs[node]);
graph->zero_weight_succs[node] = NULL;
}
VEC_free (constraint_edge_t, heap, graph->preds[node]);
VEC_free (constraint_edge_t, heap, graph->succs[node]);
graph->preds[node] = NULL;
graph->succs[node] = NULL;
}
static bool edge_added = false;
static bool
add_graph_edge (constraint_graph_t graph, unsigned int src, unsigned int dest)
{
unsigned int place;
VEC(constraint_edge_t,heap) *vec;
struct constraint_edge newe;
newe.dest = dest;
vec = graph->preds[src];
place = VEC_lower_bound (constraint_edge_t, vec, &newe,
constraint_edge_less);
if (place == VEC_length (constraint_edge_t, vec)
|| VEC_index (constraint_edge_t, vec, place)->dest != dest)
{
constraint_edge_t edge = new_constraint_edge (dest);
VEC_safe_insert (constraint_edge_t, heap, graph->preds[src],
place, edge);
edge = new_constraint_edge (src);
place = VEC_lower_bound (constraint_edge_t, graph->succs[dest],
edge, constraint_edge_less);
VEC_safe_insert (constraint_edge_t, heap, graph->succs[dest],
place, edge);
edge_added = true;
stats.num_edges++;
return true;
}
else
return false;
}
static bitmap *
get_graph_weights (constraint_graph_t graph, unsigned int src,
unsigned int dest)
{
constraint_edge_t edge;
VEC(constraint_edge_t,heap) *vec;
struct constraint_edge lookfor;
lookfor.dest = dest;
vec = graph->preds[src];
edge = constraint_edge_vec_find (vec, lookfor);
gcc_assert (edge != NULL);
return &edge->weights;
}
static bitmap
allocate_graph_weights (constraint_graph_t graph, unsigned int src,
unsigned int dest)
{
bitmap result;
constraint_edge_t edge;
VEC(constraint_edge_t,heap) *vec;
struct constraint_edge lookfor;
result = BITMAP_ALLOC (&ptabitmap_obstack);
lookfor.dest = dest;
vec = graph->preds[src];
edge = constraint_edge_vec_find (vec, lookfor);
gcc_assert (edge != NULL);
edge->weights = result;
lookfor.dest = src;
vec = graph->succs[dest];
edge = constraint_edge_vec_find (vec, lookfor);
gcc_assert (edge != NULL);
edge->weights = result;
return result;
}
static void
merge_graph_nodes (constraint_graph_t graph, unsigned int to,
unsigned int from)
{
VEC(constraint_edge_t,heap) *succvec = graph->succs[from];
VEC(constraint_edge_t,heap) *predvec = graph->preds[from];
int i;
constraint_edge_t c;
unsigned int j;
bitmap_iterator bi;
if (graph->zero_weight_preds[from])
{
if (!graph->zero_weight_preds[to])
graph->zero_weight_preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
EXECUTE_IF_SET_IN_BITMAP (graph->zero_weight_preds[from], 0, j, bi)
{
if (j != to)
{
bitmap_clear_bit (graph->zero_weight_succs[j], from);
bitmap_set_bit (graph->zero_weight_succs[j], to);
}
}
bitmap_ior_into (graph->zero_weight_preds[to],
graph->zero_weight_preds[from]);
}
if (graph->zero_weight_succs[from])
{
if (!graph->zero_weight_succs[to])
graph->zero_weight_succs[to] = BITMAP_ALLOC (&ptabitmap_obstack);
EXECUTE_IF_SET_IN_BITMAP (graph->zero_weight_succs[from], 0, j, bi)
{
bitmap_clear_bit (graph->zero_weight_preds[j], from);
bitmap_set_bit (graph->zero_weight_preds[j], to);
}
bitmap_ior_into (graph->zero_weight_succs[to],
graph->zero_weight_succs[from]);
}
for (i = 0; VEC_iterate (constraint_edge_t, predvec, i, c); i++)
{
unsigned int d = c->dest;
bitmap temp;
bitmap *weights;
if (c->dest == from)
d = to;
add_graph_edge (graph, to, d);
temp = *(get_graph_weights (graph, from, c->dest));
if (temp)
{
weights = get_graph_weights (graph, to, d);
if (!*weights)
*weights = allocate_graph_weights (graph, to, d);
bitmap_ior_into (*weights, temp);
}
}
for (i = 0; VEC_iterate (constraint_edge_t, succvec, i, c); i++)
{
unsigned int d = c->dest;
bitmap temp;
bitmap *weights;
if (c->dest == from)
d = to;
add_graph_edge (graph, d, to);
temp = *(get_graph_weights (graph, c->dest, from));
if (temp)
{
weights = get_graph_weights (graph, d, to);
if (!*weights)
*weights = allocate_graph_weights (graph, d, to);
bitmap_ior_into (*weights, temp);
}
}
clear_edges_for_node (graph, from);
}
static bool
int_add_graph_edge (constraint_graph_t graph, unsigned int to,
unsigned int from, unsigned HOST_WIDE_INT weight)
{
if (to == from && weight == 0)
{
return false;
}
else
{
bool r = false;
if (weight == 0)
{
if (!graph->zero_weight_preds[to])
graph->zero_weight_preds[to] = BITMAP_ALLOC (&predbitmap_obstack);
if (!graph->zero_weight_succs[from])
graph->zero_weight_succs[from] = BITMAP_ALLOC (&ptabitmap_obstack);
if (!bitmap_bit_p (graph->zero_weight_succs[from], to))
{
edge_added = true;
r = true;
stats.num_edges++;
bitmap_set_bit (graph->zero_weight_preds[to], from);
bitmap_set_bit (graph->zero_weight_succs[from], to);
}
}
else
{
bitmap *weights;
r = add_graph_edge (graph, to, from);
weights = get_graph_weights (graph, to, from);
if (!*weights)
{
r = true;
*weights = allocate_graph_weights (graph, to, from);
bitmap_set_bit (*weights, weight);
}
else
{
r |= !bitmap_bit_p (*weights, weight);
bitmap_set_bit (*weights, weight);
}
}
return r;
}
}
static bool
valid_graph_edge (constraint_graph_t graph, unsigned int src,
unsigned int dest)
{
struct constraint_edge lookfor;
lookfor.dest = src;
return (graph->zero_weight_succs[dest]
&& bitmap_bit_p (graph->zero_weight_succs[dest], src))
|| constraint_edge_vec_find (graph->succs[dest], lookfor) != NULL;
}
static bool
valid_weighted_graph_edge (constraint_graph_t graph, unsigned int src,
unsigned int dest)
{
struct constraint_edge lookfor;
lookfor.dest = src;
return graph->preds[src]
&& constraint_edge_vec_find (graph->succs[dest], lookfor) != NULL;
}
static void
build_constraint_graph (void)
{
int i = 0;
constraint_t c;
graph = XNEW (struct constraint_graph);
graph_size = VEC_length (varinfo_t, varmap) + 1;
graph->succs = XCNEWVEC (VEC(constraint_edge_t,heap) *, graph_size);
graph->preds = XCNEWVEC (VEC(constraint_edge_t,heap) *, graph_size);
graph->zero_weight_succs = XCNEWVEC (bitmap, graph_size);
graph->zero_weight_preds = XCNEWVEC (bitmap, graph_size);
for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
{
struct constraint_expr lhs = c->lhs;
struct constraint_expr rhs = c->rhs;
unsigned int lhsvar = get_varinfo_fc (lhs.var)->id;
unsigned int rhsvar = get_varinfo_fc (rhs.var)->id;
if (lhs.type == DEREF)
{
if (rhs.type == ADDRESSOF || rhsvar > anything_id)
insert_into_complex (lhsvar, c);
}
else if (rhs.type == DEREF)
{
if (!(get_varinfo (lhsvar)->is_special_var))
insert_into_complex (rhsvar, c);
}
else if (rhs.type == ADDRESSOF)
{
bitmap_set_bit (get_varinfo (lhsvar)->solution, rhsvar);
}
else if (lhsvar > anything_id)
{
if (lhsvar != rhsvar || rhs.offset != 0 || lhs.offset != 0)
{
int_add_graph_edge (graph, lhs.var, rhs.var, rhs.offset);
}
}
}
}
static unsigned int changed_count;
static sbitmap changed;
DEF_VEC_I(unsigned);
DEF_VEC_ALLOC_I(unsigned,heap);
struct scc_info
{
sbitmap visited;
sbitmap in_component;
int current_index;
unsigned int *visited_index;
VEC(unsigned,heap) *scc_stack;
VEC(unsigned,heap) *unification_queue;
};
static void
scc_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
{
unsigned int i;
bitmap_iterator bi;
gcc_assert (get_varinfo (n)->node == n);
SET_BIT (si->visited, n);
RESET_BIT (si->in_component, n);
si->visited_index[n] = si->current_index ++;
EXECUTE_IF_IN_NONNULL_BITMAP (graph->zero_weight_succs[n], 0, i, bi)
{
unsigned int w = i;
if (!TEST_BIT (si->visited, w))
scc_visit (graph, si, w);
if (!TEST_BIT (si->in_component, w))
{
unsigned int t = get_varinfo (w)->node;
unsigned int nnode = get_varinfo (n)->node;
if (si->visited_index[t] < si->visited_index[nnode])
get_varinfo (n)->node = t;
}
}
if (get_varinfo (n)->node == n)
{
unsigned int t = si->visited_index[n];
SET_BIT (si->in_component, n);
while (VEC_length (unsigned, si->scc_stack) != 0
&& t < si->visited_index[VEC_last (unsigned, si->scc_stack)])
{
unsigned int w = VEC_pop (unsigned, si->scc_stack);
get_varinfo (w)->node = n;
SET_BIT (si->in_component, w);
VEC_safe_push (unsigned, heap, si->unification_queue, w);
}
}
else
VEC_safe_push (unsigned, heap, si->scc_stack, n);
}
static void
collapse_nodes (constraint_graph_t graph, unsigned int to, unsigned int from)
{
bitmap tosol, fromsol;
condense_varmap_nodes (to, from);
tosol = get_varinfo (to)->solution;
fromsol = get_varinfo (from)->solution;
bitmap_ior_into (tosol, fromsol);
merge_graph_nodes (graph, to, from);
if (valid_graph_edge (graph, to, to))
{
if (graph->zero_weight_preds[to])
{
bitmap_clear_bit (graph->zero_weight_preds[to], to);
bitmap_clear_bit (graph->zero_weight_succs[to], to);
}
if (valid_weighted_graph_edge (graph, to, to))
{
bitmap weights = *(get_graph_weights (graph, to, to));
if (!weights || bitmap_empty_p (weights))
erase_graph_self_edge (graph, to);
}
}
BITMAP_FREE (fromsol);
get_varinfo (to)->address_taken |= get_varinfo (from)->address_taken;
get_varinfo (to)->indirect_target |= get_varinfo (from)->indirect_target;
}
static void
process_unification_queue (constraint_graph_t graph, struct scc_info *si,
bool update_changed)
{
size_t i = 0;
bitmap tmp = BITMAP_ALLOC (update_changed ? &iteration_obstack : NULL);
bitmap_clear (tmp);
while (i != VEC_length (unsigned, si->unification_queue))
{
unsigned int tounify = VEC_index (unsigned, si->unification_queue, i);
unsigned int n = get_varinfo (tounify)->node;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Unifying %s to %s\n",
get_varinfo (tounify)->name,
get_varinfo (n)->name);
if (update_changed)
stats.unified_vars_dynamic++;
else
stats.unified_vars_static++;
bitmap_ior_into (tmp, get_varinfo (tounify)->solution);
merge_graph_nodes (graph, n, tounify);
condense_varmap_nodes (n, tounify);
if (update_changed && TEST_BIT (changed, tounify))
{
RESET_BIT (changed, tounify);
if (!TEST_BIT (changed, n))
SET_BIT (changed, n);
else
{
gcc_assert (changed_count > 0);
changed_count--;
}
}
bitmap_clear (get_varinfo (tounify)->solution);
++i;
if (i == VEC_length (unsigned, si->unification_queue)
|| get_varinfo (VEC_index (unsigned, si->unification_queue, i))->node != n)
{
if (bitmap_ior_into (get_varinfo (n)->solution, tmp))
{
if (update_changed && !TEST_BIT (changed, n))
{
SET_BIT (changed, n);
changed_count++;
}
}
bitmap_clear (tmp);
if (valid_graph_edge (graph, n, n))
{
if (graph->zero_weight_succs[n])
{
if (graph->zero_weight_preds[n])
bitmap_clear_bit (graph->zero_weight_preds[n], n);
bitmap_clear_bit (graph->zero_weight_succs[n], n);
}
if (valid_weighted_graph_edge (graph, n, n))
{
bitmap weights = *(get_graph_weights (graph, n, n));
if (!weights || bitmap_empty_p (weights))
erase_graph_self_edge (graph, n);
}
}
}
}
BITMAP_FREE (tmp);
}
struct topo_info
{
sbitmap visited;
VEC(unsigned,heap) *topo_order;
};
static struct topo_info *
init_topo_info (void)
{
size_t size = VEC_length (varinfo_t, varmap);
struct topo_info *ti = XNEW (struct topo_info);
ti->visited = sbitmap_alloc (size);
sbitmap_zero (ti->visited);
ti->topo_order = VEC_alloc (unsigned, heap, 1);
return ti;
}
static void
free_topo_info (struct topo_info *ti)
{
sbitmap_free (ti->visited);
VEC_free (unsigned, heap, ti->topo_order);
free (ti);
}
static void
topo_visit (constraint_graph_t graph, struct topo_info *ti,
unsigned int n)
{
VEC(constraint_edge_t,heap) *succs = graph->succs[n];
bitmap temp;
bitmap_iterator bi;
constraint_edge_t c;
int i;
unsigned int j;
SET_BIT (ti->visited, n);
if (VEC_length (constraint_edge_t, succs) != 0)
{
temp = BITMAP_ALLOC (&iteration_obstack);
if (graph->zero_weight_succs[n])
bitmap_ior_into (temp, graph->zero_weight_succs[n]);
for (i = 0; VEC_iterate (constraint_edge_t, succs, i, c); i++)
bitmap_set_bit (temp, c->dest);
}
else
temp = graph->zero_weight_succs[n];
if (temp)
EXECUTE_IF_SET_IN_BITMAP (temp, 0, j, bi)
{
if (!TEST_BIT (ti->visited, j))
topo_visit (graph, ti, j);
}
VEC_safe_push (unsigned, heap, ti->topo_order, n);
}
static bool
type_safe (unsigned int n, unsigned HOST_WIDE_INT *offset)
{
varinfo_t ninfo = get_varinfo (n);
if (ninfo->is_special_var
|| ninfo->is_artificial_var
|| ninfo->is_unknown_size_var)
{
*offset = 0;
return true;
}
return (get_varinfo (n)->offset + *offset) < get_varinfo (n)->fullsize;
}
static void
do_da_constraint (constraint_graph_t graph ATTRIBUTE_UNUSED,
constraint_t c, bitmap delta)
{
unsigned int rhs = c->rhs.var;
unsigned int j;
bitmap_iterator bi;
EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
{
unsigned HOST_WIDE_INT offset = c->lhs.offset;
if (type_safe (j, &offset) && !(get_varinfo (j)->is_special_var))
{
varinfo_t v;
unsigned int t;
bitmap sol;
unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + offset;
v = first_vi_for_offset (get_varinfo (j), fieldoffset);
if (!v)
continue;
t = v->node;
sol = get_varinfo (t)->solution;
if (!bitmap_bit_p (sol, rhs))
{
bitmap_set_bit (sol, rhs);
if (!TEST_BIT (changed, t))
{
SET_BIT (changed, t);
changed_count++;
}
}
}
else if (0 && dump_file && !(get_varinfo (j)->is_special_var))
fprintf (dump_file, "Untypesafe usage in do_da_constraint.\n");
}
}
static void
do_sd_constraint (constraint_graph_t graph, constraint_t c,
bitmap delta)
{
unsigned int lhs = get_varinfo (c->lhs.var)->node;
bool flag = false;
bitmap sol = get_varinfo (lhs)->solution;
unsigned int j;
bitmap_iterator bi;
if (bitmap_bit_p (delta, anything_id))
{
flag = !bitmap_bit_p (sol, anything_id);
if (flag)
bitmap_set_bit (sol, anything_id);
goto done;
}
EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
{
unsigned HOST_WIDE_INT roffset = c->rhs.offset;
if (type_safe (j, &roffset))
{
varinfo_t v;
unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + roffset;
unsigned int t;
v = first_vi_for_offset (get_varinfo (j), fieldoffset);
if (!v)
continue;
t = v->node;
if (get_varinfo (t) ->is_special_var)
flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
else if (int_add_graph_edge (graph, lhs, t, 0))
flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
}
else if (0 && dump_file && !(get_varinfo (j)->is_special_var))
fprintf (dump_file, "Untypesafe usage in do_sd_constraint\n");
}
done:
if (flag)
{
get_varinfo (lhs)->solution = sol;
if (!TEST_BIT (changed, lhs))
{
SET_BIT (changed, lhs);
changed_count++;
}
}
}
static void
do_ds_constraint (constraint_graph_t graph, constraint_t c, bitmap delta)
{
unsigned int rhs = get_varinfo (c->rhs.var)->node;
unsigned HOST_WIDE_INT roff = c->rhs.offset;
bitmap sol = get_varinfo (rhs)->solution;
unsigned int j;
bitmap_iterator bi;
if (bitmap_bit_p (sol, anything_id))
{
EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
{
varinfo_t jvi = get_varinfo (j);
unsigned int t;
unsigned int loff = c->lhs.offset;
unsigned HOST_WIDE_INT fieldoffset = jvi->offset + loff;
varinfo_t v;
v = first_vi_for_offset (get_varinfo (j), fieldoffset);
if (!v)
continue;
t = v->node;
if (!bitmap_bit_p (get_varinfo (t)->solution, anything_id))
{
bitmap_set_bit (get_varinfo (t)->solution, anything_id);
if (!TEST_BIT (changed, t))
{
SET_BIT (changed, t);
changed_count++;
}
}
}
return;
}
EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
{
unsigned HOST_WIDE_INT loff = c->lhs.offset;
if (type_safe (j, &loff) && !(get_varinfo(j)->is_special_var))
{
varinfo_t v;
unsigned int t;
unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + loff;
v = first_vi_for_offset (get_varinfo (j), fieldoffset);
if (!v)
continue;
t = v->node;
if (int_add_graph_edge (graph, t, rhs, roff))
{
bitmap tmp = get_varinfo (t)->solution;
if (set_union_with_increment (tmp, sol, roff))
{
get_varinfo (t)->solution = tmp;
if (t == rhs)
sol = get_varinfo (rhs)->solution;
if (!TEST_BIT (changed, t))
{
SET_BIT (changed, t);
changed_count++;
}
}
}
}
else if (0 && dump_file && !(get_varinfo (j)->is_special_var))
fprintf (dump_file, "Untypesafe usage in do_ds_constraint\n");
}
}
static void
do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta)
{
if (c->lhs.type == DEREF)
{
if (c->rhs.type == ADDRESSOF)
{
do_da_constraint (graph, c, delta);
}
else
{
do_ds_constraint (graph, c, delta);
}
}
else
{
if (!(get_varinfo (c->lhs.var)->is_special_var))
do_sd_constraint (graph, c, delta);
}
}
static struct scc_info *
init_scc_info (void)
{
struct scc_info *si = XNEW (struct scc_info);
size_t size = VEC_length (varinfo_t, varmap);
si->current_index = 0;
si->visited = sbitmap_alloc (size);
sbitmap_zero (si->visited);
si->in_component = sbitmap_alloc (size);
sbitmap_ones (si->in_component);
si->visited_index = XCNEWVEC (unsigned int, size + 1);
si->scc_stack = VEC_alloc (unsigned, heap, 1);
si->unification_queue = VEC_alloc (unsigned, heap, 1);
return si;
}
static void
free_scc_info (struct scc_info *si)
{
sbitmap_free (si->visited);
sbitmap_free (si->in_component);
free (si->visited_index);
VEC_free (unsigned, heap, si->scc_stack);
VEC_free (unsigned, heap, si->unification_queue);
free(si);
}
static void
find_and_collapse_graph_cycles (constraint_graph_t graph, bool update_changed)
{
unsigned int i;
unsigned int size = VEC_length (varinfo_t, varmap);
struct scc_info *si = init_scc_info ();
for (i = 0; i != size; ++i)
if (!TEST_BIT (si->visited, i) && get_varinfo (i)->node == i)
scc_visit (graph, si, i);
process_unification_queue (graph, si, update_changed);
free_scc_info (si);
}
static void
compute_topo_order (constraint_graph_t graph,
struct topo_info *ti)
{
unsigned int i;
unsigned int size = VEC_length (varinfo_t, varmap);
for (i = 0; i != size; ++i)
if (!TEST_BIT (ti->visited, i) && get_varinfo (i)->node == i)
topo_visit (graph, ti, i);
}
static bool
bitmap_other_than_zero_bit_set (bitmap b)
{
unsigned int i;
bitmap_iterator bi;
if (bitmap_empty_p (b))
return false;
EXECUTE_IF_SET_IN_BITMAP (b, 1, i, bi)
return true;
return false;
}
static void
perform_var_substitution (constraint_graph_t graph)
{
struct topo_info *ti = init_topo_info ();
bitmap_obstack_initialize (&iteration_obstack);
compute_topo_order (graph, ti);
while (VEC_length (unsigned, ti->topo_order) != 0)
{
unsigned int i = VEC_pop (unsigned, ti->topo_order);
unsigned int pred;
varinfo_t vi = get_varinfo (i);
bool okay_to_elim = false;
unsigned int root = VEC_length (varinfo_t, varmap);
VEC(constraint_edge_t,heap) *predvec = graph->preds[i];
constraint_edge_t ce = NULL;
bitmap tmp;
unsigned int k;
bitmap_iterator bi;
if (vi->address_taken || vi->indirect_target)
continue;
EXECUTE_IF_IN_NONNULL_BITMAP (graph->zero_weight_preds[i], 0, k, bi)
{
unsigned int w;
w = get_varinfo (k)->node;
if (!okay_to_elim)
{
root = w;
okay_to_elim = true;
}
else if (w != root)
{
okay_to_elim = false;
break;
}
tmp = BITMAP_ALLOC (NULL);
bitmap_and_compl (tmp, get_varinfo (i)->solution,
get_varinfo (w)->solution);
if (!bitmap_empty_p (tmp))
{
okay_to_elim = false;
BITMAP_FREE (tmp);
break;
}
BITMAP_FREE (tmp);
}
if (okay_to_elim)
for (pred = 0;
VEC_iterate (constraint_edge_t, predvec, pred, ce);
pred++)
{
bitmap weight;
unsigned int w;
weight = *(get_graph_weights (graph, i, ce->dest));
if (weight && bitmap_other_than_zero_bit_set (weight))
{
okay_to_elim = false;
break;
}
w = get_varinfo (ce->dest)->node;
if (!okay_to_elim)
{
root = w;
okay_to_elim = true;
}
else if (w != root)
{
okay_to_elim = false;
break;
}
tmp = BITMAP_ALLOC (NULL);
bitmap_and_compl (tmp, get_varinfo (i)->solution,
get_varinfo (w)->solution);
if (!bitmap_empty_p (tmp))
{
okay_to_elim = false;
BITMAP_FREE (tmp);
break;
}
BITMAP_FREE (tmp);
}
if (root != get_varinfo (i)->node && okay_to_elim)
{
get_varinfo (i)->node = root;
collapse_nodes (graph, root, i);
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Collapsing %s into %s\n",
get_varinfo (i)->name,
get_varinfo (root)->name);
stats.collapsed_vars++;
}
}
bitmap_obstack_release (&iteration_obstack);
free_topo_info (ti);
}
static void
solve_graph (constraint_graph_t graph)
{
unsigned int size = VEC_length (varinfo_t, varmap);
unsigned int i;
changed_count = size;
changed = sbitmap_alloc (size);
sbitmap_ones (changed);
for (i = 0; i < size; i++)
if (get_varinfo (i)->node != i)
changed_count--;
while (changed_count > 0)
{
unsigned int i;
struct topo_info *ti = init_topo_info ();
stats.iterations++;
bitmap_obstack_initialize (&iteration_obstack);
if (edge_added)
{
if (stats.iterations > 1)
find_and_collapse_graph_cycles (graph, true);
edge_added = false;
}
compute_topo_order (graph, ti);
while (VEC_length (unsigned, ti->topo_order) != 0)
{
i = VEC_pop (unsigned, ti->topo_order);
gcc_assert (get_varinfo (i)->node == i);
if (TEST_BIT (changed, i))
{
unsigned int j;
constraint_t c;
constraint_edge_t e = NULL;
bitmap solution;
bitmap_iterator bi;
VEC(constraint_t,heap) *complex = get_varinfo (i)->complex;
VEC(constraint_edge_t,heap) *succs;
bool solution_empty;
RESET_BIT (changed, i);
changed_count--;
solution = get_varinfo (i)->solution;
solution_empty = bitmap_empty_p (solution);
for (j = 0; VEC_iterate (constraint_t, complex, j, c); j++)
{
if (!solution_empty || c->lhs.type != DEREF)
do_complex_constraint (graph, c, solution);
}
solution_empty = bitmap_empty_p (solution);
if (!solution_empty)
{
succs = graph->succs[i];
EXECUTE_IF_IN_NONNULL_BITMAP (graph->zero_weight_succs[i],
0, j, bi)
{
bitmap tmp = get_varinfo (j)->solution;
bool flag = false;
flag = set_union_with_increment (tmp, solution, 0);
if (flag)
{
get_varinfo (j)->solution = tmp;
if (!TEST_BIT (changed, j))
{
SET_BIT (changed, j);
changed_count++;
}
}
}
for (j = 0; VEC_iterate (constraint_edge_t, succs, j, e); j++)
{
bitmap tmp = get_varinfo (e->dest)->solution;
bool flag = false;
unsigned int k;
bitmap weights = e->weights;
bitmap_iterator bi;
gcc_assert (weights && !bitmap_empty_p (weights));
EXECUTE_IF_SET_IN_BITMAP (weights, 0, k, bi)
flag |= set_union_with_increment (tmp, solution, k);
if (flag)
{
get_varinfo (e->dest)->solution = tmp;
if (!TEST_BIT (changed, e->dest))
{
SET_BIT (changed, e->dest);
changed_count++;
}
}
}
}
}
}
free_topo_info (ti);
bitmap_obstack_release (&iteration_obstack);
}
sbitmap_free (changed);
}
static htab_t id_for_tree;
typedef struct tree_id
{
tree t;
unsigned int id;
} *tree_id_t;
static hashval_t
tree_id_hash (const void *p)
{
const tree_id_t ta = (tree_id_t) p;
return htab_hash_pointer (ta->t);
}
static int
tree_id_eq (const void *p1, const void *p2)
{
const tree_id_t ta1 = (tree_id_t) p1;
const tree_id_t ta2 = (tree_id_t) p2;
return ta1->t == ta2->t;
}
static void
insert_id_for_tree (tree t, int id)
{
void **slot;
struct tree_id finder;
tree_id_t new_pair;
finder.t = t;
slot = htab_find_slot (id_for_tree, &finder, INSERT);
gcc_assert (*slot == NULL);
new_pair = XNEW (struct tree_id);
new_pair->t = t;
new_pair->id = id;
*slot = (void *)new_pair;
}
static bool
lookup_id_for_tree (tree t, unsigned int *id)
{
tree_id_t pair;
struct tree_id finder;
finder.t = t;
pair = htab_find (id_for_tree, &finder);
if (pair == NULL)
return false;
*id = pair->id;
return true;
}
static const char *
alias_get_name (tree decl)
{
const char *res = get_name (decl);
char *temp;
int num_printed = 0;
if (res != NULL)
return res;
res = "NULL";
if (!dump_file)
return res;
if (TREE_CODE (decl) == SSA_NAME)
{
num_printed = asprintf (&temp, "%s_%u",
alias_get_name (SSA_NAME_VAR (decl)),
SSA_NAME_VERSION (decl));
}
else if (DECL_P (decl))
{
num_printed = asprintf (&temp, "D.%u", DECL_UID (decl));
}
if (num_printed > 0)
{
res = ggc_strdup (temp);
free (temp);
}
return res;
}
static unsigned int
get_id_for_tree (tree t)
{
tree_id_t pair;
struct tree_id finder;
finder.t = t;
pair = htab_find (id_for_tree, &finder);
if (pair == NULL)
return create_variable_info_for (t, alias_get_name (t));
return pair->id;
}
static struct constraint_expr
get_constraint_exp_from_ssa_var (tree t)
{
struct constraint_expr cexpr;
gcc_assert (SSA_VAR_P (t) || DECL_P (t));
if (TREE_CODE (t) == SSA_NAME
&& TREE_CODE (SSA_NAME_VAR (t)) == PARM_DECL
&& default_def (SSA_NAME_VAR (t)) == t)
return get_constraint_exp_from_ssa_var (SSA_NAME_VAR (t));
cexpr.type = SCALAR;
cexpr.var = get_id_for_tree (t);
if (cexpr.var == anything_id && TREE_READONLY (t))
{
cexpr.type = ADDRESSOF;
cexpr.var = readonly_id;
}
cexpr.offset = 0;
return cexpr;
}
static void
process_constraint (constraint_t t)
{
struct constraint_expr rhs = t->rhs;
struct constraint_expr lhs = t->lhs;
gcc_assert (rhs.var < VEC_length (varinfo_t, varmap));
gcc_assert (lhs.var < VEC_length (varinfo_t, varmap));
if (lhs.type == DEREF)
get_varinfo (lhs.var)->directly_dereferenced = true;
if (rhs.type == DEREF)
get_varinfo (rhs.var)->directly_dereferenced = true;
if (lhs.var == anything_id && rhs.var == anything_id)
return;
else if (lhs.var == anything_id && lhs.type == ADDRESSOF)
{
rhs = t->lhs;
t->lhs = t->rhs;
t->rhs = rhs;
process_constraint (t);
}
else if (rhs.type == DEREF && lhs.type == DEREF && rhs.var != anything_id)
{
tree rhsdecl = get_varinfo (rhs.var)->decl;
tree pointertype = TREE_TYPE (rhsdecl);
tree pointedtotype = TREE_TYPE (pointertype);
tree tmpvar = create_tmp_var_raw (pointedtotype, "doubledereftmp");
struct constraint_expr tmplhs = get_constraint_exp_from_ssa_var (tmpvar);
gcc_assert (!AGGREGATE_TYPE_P (pointedtotype)
|| get_varinfo (rhs.var)->is_unknown_size_var);
process_constraint (new_constraint (tmplhs, rhs));
process_constraint (new_constraint (lhs, tmplhs));
}
else if (rhs.type == ADDRESSOF)
{
varinfo_t vi;
gcc_assert (rhs.offset == 0);
if (lhs.var != escaped_vars_id)
for (vi = get_varinfo (rhs.var); vi != NULL; vi = vi->next)
vi->address_taken = true;
VEC_safe_push (constraint_t, heap, constraints, t);
}
else
{
if (lhs.type != DEREF && rhs.type == DEREF)
get_varinfo (lhs.var)->indirect_target = true;
VEC_safe_push (constraint_t, heap, constraints, t);
}
}
static bool
could_have_pointers (tree t)
{
tree type = TREE_TYPE (t);
if (POINTER_TYPE_P (type) || AGGREGATE_TYPE_P (type)
|| TREE_CODE (type) == COMPLEX_TYPE)
return true;
return false;
}
static unsigned HOST_WIDE_INT
bitpos_of_field (const tree fdecl)
{
if (TREE_CODE (DECL_FIELD_OFFSET (fdecl)) != INTEGER_CST
|| TREE_CODE (DECL_FIELD_BIT_OFFSET (fdecl)) != INTEGER_CST)
return -1;
return (tree_low_cst (DECL_FIELD_OFFSET (fdecl), 1) * 8)
+ tree_low_cst (DECL_FIELD_BIT_OFFSET (fdecl), 1);
}
static bool
offset_overlaps_with_access (const unsigned HOST_WIDE_INT fieldpos,
const unsigned HOST_WIDE_INT fieldsize,
const unsigned HOST_WIDE_INT accesspos,
const unsigned HOST_WIDE_INT accesssize)
{
if (fieldpos == accesspos && fieldsize == accesssize)
return true;
if (accesspos >= fieldpos && accesspos < (fieldpos + fieldsize))
return true;
if (accesspos < fieldpos && (accesspos + accesssize > fieldpos))
return true;
return false;
}
static void
get_constraint_for_component_ref (tree t, VEC(ce_s, heap) **results)
{
tree orig_t = t;
HOST_WIDE_INT bitsize = -1;
HOST_WIDE_INT bitmaxsize = -1;
HOST_WIDE_INT bitpos;
tree forzero;
struct constraint_expr *result;
unsigned int beforelength = VEC_length (ce_s, *results);
forzero = t;
while (!SSA_VAR_P (forzero) && !CONSTANT_CLASS_P (forzero))
forzero = TREE_OPERAND (forzero, 0);
if (CONSTANT_CLASS_P (forzero) && integer_zerop (forzero))
{
struct constraint_expr temp;
temp.offset = 0;
temp.var = integer_id;
temp.type = SCALAR;
VEC_safe_push (ce_s, heap, *results, &temp);
return;
}
t = get_ref_base_and_extent (t, &bitpos, &bitsize, &bitmaxsize);
if (TREE_CODE (t) == STRING_CST)
return;
get_constraint_for (t, results);
result = VEC_last (ce_s, *results);
result->offset = bitpos;
gcc_assert (beforelength + 1 == VEC_length (ce_s, *results));
if (TREE_CODE (t) != ADDR_EXPR && result->type == ADDRESSOF)
result->type = SCALAR;
if (result->type == SCALAR)
{
if (result->offset < get_varinfo (result->var)->fullsize
&& bitmaxsize != 0)
{
varinfo_t curr;
for (curr = get_varinfo (result->var); curr; curr = curr->next)
{
if (offset_overlaps_with_access (curr->offset, curr->size,
result->offset, bitmaxsize))
{
result->var = curr->id;
break;
}
}
gcc_assert (curr || ref_contains_array_ref (orig_t));
}
else if (bitmaxsize == 0)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Access to zero-sized part of variable,"
"ignoring\n");
}
else
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Access to past the end of variable, ignoring\n");
result->offset = 0;
}
}
static void
do_deref (VEC (ce_s, heap) **constraints)
{
struct constraint_expr *c;
unsigned int i = 0;
for (i = 0; VEC_iterate (ce_s, *constraints, i, c); i++)
{
if (c->type == SCALAR)
c->type = DEREF;
else if (c->type == ADDRESSOF)
c->type = SCALAR;
else if (c->type == DEREF)
{
tree tmpvar = create_tmp_var_raw (ptr_type_node, "dereftmp");
struct constraint_expr tmplhs = get_constraint_exp_from_ssa_var (tmpvar);
process_constraint (new_constraint (tmplhs, *c));
c->var = tmplhs.var;
}
else
gcc_unreachable ();
}
}
static tree
create_nonlocal_var (tree type)
{
tree nonlocal = create_tmp_var_raw (type, "NONLOCAL");
if (referenced_vars)
add_referenced_var (nonlocal);
DECL_EXTERNAL (nonlocal) = 1;
return nonlocal;
}
static void
get_constraint_for (tree t, VEC (ce_s, heap) **results)
{
struct constraint_expr temp;
if (TREE_CODE (t) == INTEGER_CST
&& !POINTER_TYPE_P (TREE_TYPE (t)))
{
temp.var = integer_id;
temp.type = SCALAR;
temp.offset = 0;
VEC_safe_push (ce_s, heap, *results, &temp);
return;
}
else if (TREE_CODE (t) == INTEGER_CST
&& integer_zerop (t))
{
temp.var = nothing_id;
temp.type = ADDRESSOF;
temp.offset = 0;
VEC_safe_push (ce_s, heap, *results, &temp);
return;
}
switch (TREE_CODE_CLASS (TREE_CODE (t)))
{
case tcc_expression:
{
switch (TREE_CODE (t))
{
case ADDR_EXPR:
{
struct constraint_expr *c;
unsigned int i;
tree exp = TREE_OPERAND (t, 0);
tree pttype = TREE_TYPE (TREE_TYPE (t));
get_constraint_for (exp, results);
if ((handled_component_p (exp)
&& ref_contains_array_ref (exp))
|| TREE_CODE (TREE_TYPE (exp)) == ARRAY_TYPE)
{
struct constraint_expr *origrhs;
varinfo_t origvar;
struct constraint_expr tmp;
if (VEC_length (ce_s, *results) == 0)
return;
gcc_assert (VEC_length (ce_s, *results) == 1);
origrhs = VEC_last (ce_s, *results);
tmp = *origrhs;
VEC_pop (ce_s, *results);
origvar = get_varinfo (origrhs->var);
for (; origvar; origvar = origvar->next)
{
tmp.var = origvar->id;
VEC_safe_push (ce_s, heap, *results, &tmp);
}
}
else if (VEC_length (ce_s, *results) == 1
&& (AGGREGATE_TYPE_P (pttype)
|| TREE_CODE (pttype) == COMPLEX_TYPE))
{
struct constraint_expr *origrhs;
varinfo_t origvar;
struct constraint_expr tmp;
gcc_assert (VEC_length (ce_s, *results) == 1);
origrhs = VEC_last (ce_s, *results);
tmp = *origrhs;
VEC_pop (ce_s, *results);
origvar = get_varinfo (origrhs->var);
for (; origvar; origvar = origvar->next)
{
tmp.var = origvar->id;
VEC_safe_push (ce_s, heap, *results, &tmp);
}
}
for (i = 0; VEC_iterate (ce_s, *results, i, c); i++)
{
if (c->type == DEREF)
c->type = SCALAR;
else
c->type = ADDRESSOF;
}
return;
}
break;
case CALL_EXPR:
if (call_expr_flags (t) & (ECF_MALLOC | ECF_MAY_BE_ALLOCA))
{
varinfo_t vi;
tree heapvar = heapvar_lookup (t);
if (heapvar == NULL)
{
heapvar = create_tmp_var_raw (ptr_type_node, "HEAP");
DECL_EXTERNAL (heapvar) = 1;
if (referenced_vars)
add_referenced_var (heapvar);
heapvar_insert (t, heapvar);
}
temp.var = create_variable_info_for (heapvar,
alias_get_name (heapvar));
vi = get_varinfo (temp.var);
vi->is_artificial_var = 1;
vi->is_heap_var = 1;
temp.type = ADDRESSOF;
temp.offset = 0;
VEC_safe_push (ce_s, heap, *results, &temp);
return;
}
else
{
temp.var = escaped_vars_id;
temp.type = SCALAR;
temp.offset = 0;
VEC_safe_push (ce_s, heap, *results, &temp);
return;
}
break;
default:
{
temp.type = ADDRESSOF;
temp.var = anything_id;
temp.offset = 0;
VEC_safe_push (ce_s, heap, *results, &temp);
return;
}
}
}
case tcc_reference:
{
switch (TREE_CODE (t))
{
case INDIRECT_REF:
{
get_constraint_for (TREE_OPERAND (t, 0), results);
do_deref (results);
return;
}
case ARRAY_REF:
case ARRAY_RANGE_REF:
case COMPONENT_REF:
get_constraint_for_component_ref (t, results);
return;
default:
{
temp.type = ADDRESSOF;
temp.var = anything_id;
temp.offset = 0;
VEC_safe_push (ce_s, heap, *results, &temp);
return;
}
}
}
case tcc_unary:
{
switch (TREE_CODE (t))
{
case NOP_EXPR:
case CONVERT_EXPR:
case NON_LVALUE_EXPR:
{
tree op = TREE_OPERAND (t, 0);
if (!(POINTER_TYPE_P (TREE_TYPE (t))
&& ! POINTER_TYPE_P (TREE_TYPE (op))))
{
get_constraint_for (op, results);
return;
}
}
default:
{
temp.type = ADDRESSOF;
temp.var = anything_id;
temp.offset = 0;
VEC_safe_push (ce_s, heap, *results, &temp);
return;
}
}
}
case tcc_exceptional:
{
switch (TREE_CODE (t))
{
case PHI_NODE:
{
get_constraint_for (PHI_RESULT (t), results);
return;
}
break;
case SSA_NAME:
{
struct constraint_expr temp;
temp = get_constraint_exp_from_ssa_var (t);
VEC_safe_push (ce_s, heap, *results, &temp);
return;
}
break;
default:
{
temp.type = ADDRESSOF;
temp.var = anything_id;
temp.offset = 0;
VEC_safe_push (ce_s, heap, *results, &temp);
return;
}
}
}
case tcc_declaration:
{
struct constraint_expr temp;
temp = get_constraint_exp_from_ssa_var (t);
VEC_safe_push (ce_s, heap, *results, &temp);
return;
}
default:
{
temp.type = ADDRESSOF;
temp.var = anything_id;
temp.offset = 0;
VEC_safe_push (ce_s, heap, *results, &temp);
return;
}
}
}
static bool
do_simple_structure_copy (const struct constraint_expr lhs,
const struct constraint_expr rhs,
const unsigned HOST_WIDE_INT size)
{
varinfo_t p = get_varinfo (lhs.var);
unsigned HOST_WIDE_INT pstart, last;
pstart = p->offset;
last = p->offset + size;
for (; p && p->offset < last; p = p->next)
{
varinfo_t q;
struct constraint_expr templhs = lhs;
struct constraint_expr temprhs = rhs;
unsigned HOST_WIDE_INT fieldoffset;
templhs.var = p->id;
q = get_varinfo (temprhs.var);
fieldoffset = p->offset - pstart;
q = first_vi_for_offset (q, q->offset + fieldoffset);
if (!q)
return false;
temprhs.var = q->id;
process_constraint (new_constraint (templhs, temprhs));
}
return true;
}
static void
do_rhs_deref_structure_copy (const struct constraint_expr lhs,
const struct constraint_expr rhs,
const unsigned HOST_WIDE_INT size)
{
varinfo_t p = get_varinfo (lhs.var);
unsigned HOST_WIDE_INT pstart,last;
pstart = p->offset;
last = p->offset + size;
for (; p && p->offset < last; p = p->next)
{
varinfo_t q;
struct constraint_expr templhs = lhs;
struct constraint_expr temprhs = rhs;
unsigned HOST_WIDE_INT fieldoffset;
if (templhs.type == SCALAR)
templhs.var = p->id;
else
templhs.offset = p->offset;
q = get_varinfo (temprhs.var);
fieldoffset = p->offset - pstart;
temprhs.offset += fieldoffset;
process_constraint (new_constraint (templhs, temprhs));
}
}
static void
do_lhs_deref_structure_copy (const struct constraint_expr lhs,
const struct constraint_expr rhs,
const unsigned HOST_WIDE_INT size)
{
varinfo_t p = get_varinfo (rhs.var);
unsigned HOST_WIDE_INT pstart,last;
pstart = p->offset;
last = p->offset + size;
for (; p && p->offset < last; p = p->next)
{
varinfo_t q;
struct constraint_expr templhs = lhs;
struct constraint_expr temprhs = rhs;
unsigned HOST_WIDE_INT fieldoffset;
if (temprhs.type == SCALAR)
temprhs.var = p->id;
else
temprhs.offset = p->offset;
q = get_varinfo (templhs.var);
fieldoffset = p->offset - pstart;
templhs.offset += fieldoffset;
process_constraint (new_constraint (templhs, temprhs));
}
}
static unsigned int
collapse_rest_of_var (unsigned int var)
{
varinfo_t currvar = get_varinfo (var);
varinfo_t field;
for (field = currvar->next; field; field = field->next)
{
if (dump_file)
fprintf (dump_file, "Type safety: Collapsing var %s into %s\n",
field->name, currvar->name);
gcc_assert (!field->collapsed_to);
field->collapsed_to = currvar;
}
currvar->next = NULL;
currvar->size = currvar->fullsize - currvar->offset;
return currvar->id;
}
static void
do_structure_copy (tree lhsop, tree rhsop)
{
struct constraint_expr lhs, rhs, tmp;
VEC (ce_s, heap) *lhsc = NULL, *rhsc = NULL;
varinfo_t p;
unsigned HOST_WIDE_INT lhssize;
unsigned HOST_WIDE_INT rhssize;
get_constraint_for (lhsop, &lhsc);
get_constraint_for (rhsop, &rhsc);
gcc_assert (VEC_length (ce_s, lhsc) == 1);
gcc_assert (VEC_length (ce_s, rhsc) == 1);
lhs = *(VEC_last (ce_s, lhsc));
rhs = *(VEC_last (ce_s, rhsc));
VEC_free (ce_s, heap, lhsc);
VEC_free (ce_s, heap, rhsc);
if (lhs.var <= integer_id && !(get_varinfo (rhs.var)->is_special_var))
{
tmp = lhs;
lhs = rhs;
rhs = tmp;
}
if (rhs.type == ADDRESSOF && !(get_varinfo (rhs.var)->is_special_var))
{
rhs.type = ADDRESSOF;
rhs.var = anything_id;
}
if (rhs.var <= integer_id)
{
for (p = get_varinfo (lhs.var); p; p = p->next)
{
struct constraint_expr templhs = lhs;
struct constraint_expr temprhs = rhs;
if (templhs.type == SCALAR )
templhs.var = p->id;
else
templhs.offset += p->offset;
process_constraint (new_constraint (templhs, temprhs));
}
}
else
{
tree rhstype = TREE_TYPE (rhsop);
tree lhstype = TREE_TYPE (lhsop);
tree rhstypesize;
tree lhstypesize;
lhstypesize = DECL_P (lhsop) ? DECL_SIZE (lhsop) : TYPE_SIZE (lhstype);
rhstypesize = DECL_P (rhsop) ? DECL_SIZE (rhsop) : TYPE_SIZE (rhstype);
if ((rhs.type == DEREF && TREE_CODE (rhstypesize) != INTEGER_CST)
|| (lhs.type == DEREF && TREE_CODE (lhstypesize) != INTEGER_CST))
{
rhs.var = anything_id;
rhs.type = ADDRESSOF;
rhs.offset = 0;
process_constraint (new_constraint (lhs, rhs));
return;
}
if (get_varinfo (rhs.var)->is_unknown_size_var)
rhssize = ~0;
else
rhssize = TREE_INT_CST_LOW (rhstypesize);
if (get_varinfo (lhs.var)->is_unknown_size_var)
lhssize = ~0;
else
lhssize = TREE_INT_CST_LOW (lhstypesize);
if (rhs.type == SCALAR && lhs.type == SCALAR)
{
if (!do_simple_structure_copy (lhs, rhs, MIN (lhssize, rhssize)))
{
lhs.var = collapse_rest_of_var (lhs.var);
rhs.var = collapse_rest_of_var (rhs.var);
lhs.offset = 0;
rhs.offset = 0;
lhs.type = SCALAR;
rhs.type = SCALAR;
process_constraint (new_constraint (lhs, rhs));
}
}
else if (lhs.type != DEREF && rhs.type == DEREF)
do_rhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
else if (lhs.type == DEREF && rhs.type != DEREF)
do_lhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
else
{
tree pointedtotype = lhstype;
tree tmpvar;
gcc_assert (rhs.type == DEREF && lhs.type == DEREF);
tmpvar = create_tmp_var_raw (pointedtotype, "structcopydereftmp");
do_structure_copy (tmpvar, rhsop);
do_structure_copy (lhsop, tmpvar);
}
}
}
static void
update_alias_info (tree stmt, struct alias_info *ai)
{
bitmap addr_taken;
use_operand_p use_p;
ssa_op_iter iter;
enum escape_type stmt_escape_type = is_escape_site (stmt);
tree op;
if (stmt_escape_type == ESCAPE_TO_CALL
|| stmt_escape_type == ESCAPE_TO_PURE_CONST)
{
ai->num_calls_found++;
if (stmt_escape_type == ESCAPE_TO_PURE_CONST)
ai->num_pure_const_calls_found++;
}
addr_taken = addresses_taken (stmt);
if (addr_taken)
{
bitmap_ior_into (addressable_vars, addr_taken);
if (stmt_escape_type != NO_ESCAPE)
{
bitmap_iterator bi;
unsigned i;
EXECUTE_IF_SET_IN_BITMAP (addr_taken, 0, i, bi)
{
tree rvar = referenced_var (i);
if (!unmodifiable_var_p (rvar))
mark_call_clobbered (rvar, stmt_escape_type);
}
}
}
FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
{
tree op, var;
var_ann_t v_ann;
struct ptr_info_def *pi;
bool is_store, is_potential_deref;
unsigned num_uses, num_derefs;
op = USE_FROM_PTR (use_p);
if (TREE_CODE (op) == ADDR_EXPR)
{
gcc_assert (TREE_CODE (stmt) == PHI_NODE);
add_to_addressable_set (TREE_OPERAND (op, 0), &addressable_vars);
continue;
}
if (TREE_CODE (op) != SSA_NAME)
continue;
var = SSA_NAME_VAR (op);
v_ann = var_ann (var);
gcc_assert (!may_be_aliased (var));
if (!POINTER_TYPE_P (TREE_TYPE (op)))
continue;
pi = get_ptr_info (op);
if (!TEST_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (op)))
{
SET_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (op));
VEC_safe_push (tree, heap, ai->processed_ptrs, op);
}
if (TREE_CODE (stmt) == PHI_NODE)
continue;
count_uses_and_derefs (op, stmt, &num_uses, &num_derefs, &is_store);
is_potential_deref = false;
if (TREE_CODE (stmt) == MODIFY_EXPR
&& TREE_CODE (TREE_OPERAND (stmt, 1)) == ADDR_EXPR
&& !is_gimple_val (TREE_OPERAND (stmt, 1)))
{
tree rhs = TREE_OPERAND (stmt, 1);
tree base = get_base_address (TREE_OPERAND (rhs, 0));
if (TREE_CODE (base) == INDIRECT_REF
&& TREE_OPERAND (base, 0) == op)
is_potential_deref = true;
}
if (num_derefs > 0 || is_potential_deref)
{
pi->is_dereferenced = 1;
NUM_REFERENCES_INC (v_ann);
if (is_store)
bitmap_set_bit (ai->dereferenced_ptrs_store, DECL_UID (var));
else
bitmap_set_bit (ai->dereferenced_ptrs_load, DECL_UID (var));
}
if (stmt_escape_type != NO_ESCAPE && num_derefs < num_uses)
{
pi->value_escapes_p = 1;
pi->escape_mask |= stmt_escape_type;
if (get_call_expr_in (stmt)
|| stmt_escape_type == ESCAPE_STORED_IN_GLOBAL)
{
bitmap_set_bit (ai->dereferenced_ptrs_store, DECL_UID (var));
pi->is_dereferenced = 1;
}
}
}
if (TREE_CODE (stmt) == PHI_NODE)
return;
FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
{
tree var = SSA_NAME_VAR (op);
var_ann_t ann = var_ann (var);
bitmap_set_bit (ai->written_vars, DECL_UID (var));
if (may_be_aliased (var))
NUM_REFERENCES_INC (ann);
}
FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_VIRTUAL_DEFS)
{
tree var = DECL_P (op) ? op : SSA_NAME_VAR (op);
bitmap_set_bit (ai->written_vars, DECL_UID (var));
}
}
static bool
handle_ptr_arith (VEC (ce_s, heap) *lhsc, tree expr)
{
tree op0, op1;
struct constraint_expr *c, *c2;
unsigned int i = 0;
unsigned int j = 0;
VEC (ce_s, heap) *temp = NULL;
unsigned int rhsoffset = 0;
if (TREE_CODE (expr) != PLUS_EXPR
&& TREE_CODE (expr) != MINUS_EXPR)
return false;
op0 = TREE_OPERAND (expr, 0);
op1 = TREE_OPERAND (expr, 1);
get_constraint_for (op0, &temp);
if (POINTER_TYPE_P (TREE_TYPE (op0))
&& TREE_CODE (op1) == INTEGER_CST
&& TREE_CODE (expr) == PLUS_EXPR)
{
rhsoffset = TREE_INT_CST_LOW (op1) * BITS_PER_UNIT;
}
else
return false;
for (i = 0; VEC_iterate (ce_s, lhsc, i, c); i++)
for (j = 0; VEC_iterate (ce_s, temp, j, c2); j++)
{
if (c2->type == ADDRESSOF && rhsoffset != 0)
{
varinfo_t temp = get_varinfo (c2->var);
temp = first_vi_for_offset (temp, rhsoffset);
if (temp == NULL)
continue;
c2->var = temp->id;
c2->offset = 0;
}
else
c2->offset = rhsoffset;
process_constraint (new_constraint (*c, *c2));
}
VEC_free (ce_s, heap, temp);
return true;
}
static void
find_func_aliases (tree origt)
{
tree t = origt;
VEC(ce_s, heap) *lhsc = NULL;
VEC(ce_s, heap) *rhsc = NULL;
struct constraint_expr *c;
if (TREE_CODE (t) == RETURN_EXPR && TREE_OPERAND (t, 0))
t = TREE_OPERAND (t, 0);
if (TREE_CODE (t) == PHI_NODE)
{
gcc_assert (!AGGREGATE_TYPE_P (TREE_TYPE (PHI_RESULT (t))));
if (could_have_pointers (PHI_RESULT (t)))
{
int i;
unsigned int j;
get_constraint_for (PHI_RESULT (t), &lhsc);
for (i = 0; i < PHI_NUM_ARGS (t); i++)
{
tree rhstype;
tree strippedrhs = PHI_ARG_DEF (t, i);
STRIP_NOPS (strippedrhs);
rhstype = TREE_TYPE (strippedrhs);
get_constraint_for (PHI_ARG_DEF (t, i), &rhsc);
for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++)
{
struct constraint_expr *c2;
while (VEC_length (ce_s, rhsc) > 0)
{
c2 = VEC_last (ce_s, rhsc);
process_constraint (new_constraint (*c, *c2));
VEC_pop (ce_s, rhsc);
}
}
}
}
}
else if (in_ipa_mode
&& ((TREE_CODE (t) == MODIFY_EXPR
&& TREE_CODE (TREE_OPERAND (t, 1)) == CALL_EXPR
&& !(call_expr_flags (TREE_OPERAND (t, 1))
& (ECF_MALLOC | ECF_MAY_BE_ALLOCA)))
|| (TREE_CODE (t) == CALL_EXPR
&& !(call_expr_flags (t)
& (ECF_MALLOC | ECF_MAY_BE_ALLOCA)))))
{
tree lhsop;
tree rhsop;
unsigned int varid;
tree arglist;
varinfo_t fi;
int i = 1;
tree decl;
if (TREE_CODE (t) == MODIFY_EXPR)
{
lhsop = TREE_OPERAND (t, 0);
rhsop = TREE_OPERAND (t, 1);
}
else
{
lhsop = NULL;
rhsop = t;
}
decl = get_callee_fndecl (rhsop);
if (decl)
{
varid = get_id_for_tree (decl);
}
else
{
decl = TREE_OPERAND (rhsop, 0);
varid = get_id_for_tree (decl);
}
fi = get_varinfo (varid);
arglist = TREE_OPERAND (rhsop, 1);
for (;arglist; arglist = TREE_CHAIN (arglist))
{
tree arg = TREE_VALUE (arglist);
struct constraint_expr lhs ;
struct constraint_expr *rhsp;
get_constraint_for (arg, &rhsc);
if (TREE_CODE (decl) != FUNCTION_DECL)
{
lhs.type = DEREF;
lhs.var = fi->id;
lhs.offset = i;
}
else
{
lhs.type = SCALAR;
lhs.var = first_vi_for_offset (fi, i)->id;
lhs.offset = 0;
}
while (VEC_length (ce_s, rhsc) != 0)
{
rhsp = VEC_last (ce_s, rhsc);
process_constraint (new_constraint (lhs, *rhsp));
VEC_pop (ce_s, rhsc);
}
i++;
}
if (lhsop)
{
struct constraint_expr rhs;
struct constraint_expr *lhsp;
unsigned int j = 0;
get_constraint_for (lhsop, &lhsc);
if (TREE_CODE (decl) != FUNCTION_DECL)
{
rhs.type = DEREF;
rhs.var = fi->id;
rhs.offset = i;
}
else
{
rhs.type = SCALAR;
rhs.var = first_vi_for_offset (fi, i)->id;
rhs.offset = 0;
}
for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++)
process_constraint (new_constraint (*lhsp, rhs));
}
}
else if (TREE_CODE (t) == MODIFY_EXPR)
{
tree lhsop = TREE_OPERAND (t, 0);
tree rhsop = TREE_OPERAND (t, 1);
int i;
if ((AGGREGATE_TYPE_P (TREE_TYPE (lhsop))
|| TREE_CODE (TREE_TYPE (lhsop)) == COMPLEX_TYPE)
&& (AGGREGATE_TYPE_P (TREE_TYPE (rhsop))
|| TREE_CODE (TREE_TYPE (lhsop)) == COMPLEX_TYPE))
{
do_structure_copy (lhsop, rhsop);
}
else
{
if (could_have_pointers (lhsop)
|| TREE_CODE (rhsop) == CALL_EXPR)
{
get_constraint_for (lhsop, &lhsc);
switch (TREE_CODE_CLASS (TREE_CODE (rhsop)))
{
case tcc_reference:
case tcc_declaration:
case tcc_constant:
case tcc_exceptional:
case tcc_expression:
case tcc_unary:
{
unsigned int j;
get_constraint_for (rhsop, &rhsc);
for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++)
{
struct constraint_expr *c2;
unsigned int k;
for (k = 0; VEC_iterate (ce_s, rhsc, k, c2); k++)
process_constraint (new_constraint (*c, *c2));
}
}
break;
case tcc_binary:
{
if (handle_ptr_arith (lhsc, rhsop))
break;
}
default:
for (i = 0; i < TREE_CODE_LENGTH (TREE_CODE (rhsop)); i++)
{
tree op = TREE_OPERAND (rhsop, i);
unsigned int j;
gcc_assert (VEC_length (ce_s, rhsc) == 0);
get_constraint_for (op, &rhsc);
for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++)
{
struct constraint_expr *c2;
while (VEC_length (ce_s, rhsc) > 0)
{
c2 = VEC_last (ce_s, rhsc);
process_constraint (new_constraint (*c, *c2));
VEC_pop (ce_s, rhsc);
}
}
}
}
}
}
}
mark_stmt_modified (origt);
VEC_free (ce_s, heap, rhsc);
VEC_free (ce_s, heap, lhsc);
}
static varinfo_t
first_vi_for_offset (varinfo_t start, unsigned HOST_WIDE_INT offset)
{
varinfo_t curr = start;
while (curr)
{
if (offset >= curr->offset && offset < (curr->offset + curr->size))
return curr;
curr = curr->next;
}
return NULL;
}
static void
insert_into_field_list (varinfo_t base, varinfo_t field)
{
varinfo_t prev = base;
varinfo_t curr = base->next;
field->next = curr;
prev->next = field;
}
static void
insert_into_field_list_sorted (varinfo_t base, varinfo_t field)
{
varinfo_t prev = base;
varinfo_t curr = base->next;
if (curr == NULL)
{
prev->next = field;
field->next = NULL;
}
else
{
while (curr)
{
if (field->offset <= curr->offset)
break;
prev = curr;
curr = curr->next;
}
field->next = prev->next;
prev->next = field;
}
}
static int
fieldoff_compare (const void *pa, const void *pb)
{
const fieldoff_s *foa = (const fieldoff_s *)pa;
const fieldoff_s *fob = (const fieldoff_s *)pb;
HOST_WIDE_INT foasize, fobsize;
if (foa->offset != fob->offset)
return foa->offset - fob->offset;
foasize = TREE_INT_CST_LOW (foa->size);
fobsize = TREE_INT_CST_LOW (fob->size);
return foasize - fobsize;
}
void
sort_fieldstack (VEC(fieldoff_s,heap) *fieldstack)
{
qsort (VEC_address (fieldoff_s, fieldstack),
VEC_length (fieldoff_s, fieldstack),
sizeof (fieldoff_s),
fieldoff_compare);
}
int
push_fields_onto_fieldstack (tree type, VEC(fieldoff_s,heap) **fieldstack,
HOST_WIDE_INT offset, bool *has_union)
{
tree field;
int count = 0;
if (TREE_CODE (type) == COMPLEX_TYPE)
{
fieldoff_s *real_part, *img_part;
real_part = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
real_part->type = TREE_TYPE (type);
real_part->size = TYPE_SIZE (TREE_TYPE (type));
real_part->offset = offset;
real_part->decl = NULL_TREE;
img_part = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
img_part->type = TREE_TYPE (type);
img_part->size = TYPE_SIZE (TREE_TYPE (type));
img_part->offset = offset + TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (type)));
img_part->decl = NULL_TREE;
return 2;
}
if (TREE_CODE (type) == ARRAY_TYPE)
{
tree sz = TYPE_SIZE (type);
tree elsz = TYPE_SIZE (TREE_TYPE (type));
HOST_WIDE_INT nr;
int i;
if (! sz
|| ! host_integerp (sz, 1)
|| TREE_INT_CST_LOW (sz) == 0
|| ! elsz
|| ! host_integerp (elsz, 1)
|| TREE_INT_CST_LOW (elsz) == 0)
return 0;
nr = TREE_INT_CST_LOW (sz) / TREE_INT_CST_LOW (elsz);
if (nr > SALIAS_MAX_ARRAY_ELEMENTS)
return 0;
for (i = 0; i < nr; ++i)
{
bool push = false;
int pushed = 0;
if (has_union
&& (TREE_CODE (TREE_TYPE (type)) == QUAL_UNION_TYPE
|| TREE_CODE (TREE_TYPE (type)) == UNION_TYPE))
*has_union = true;
if (!AGGREGATE_TYPE_P (TREE_TYPE (type)))
push = true;
else if (!(pushed = push_fields_onto_fieldstack
(TREE_TYPE (type), fieldstack,
offset + i * TREE_INT_CST_LOW (elsz), has_union)))
push = true;
if (push)
{
fieldoff_s *pair;
pair = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
pair->type = TREE_TYPE (type);
pair->size = elsz;
pair->decl = NULL_TREE;
pair->offset = offset + i * TREE_INT_CST_LOW (elsz);
count++;
}
else
count += pushed;
}
return count;
}
for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
if (TREE_CODE (field) == FIELD_DECL)
{
bool push = false;
int pushed = 0;
if (has_union
&& (TREE_CODE (TREE_TYPE (field)) == QUAL_UNION_TYPE
|| TREE_CODE (TREE_TYPE (field)) == UNION_TYPE))
*has_union = true;
if (!var_can_have_subvars (field))
push = true;
else if (!(pushed = push_fields_onto_fieldstack
(TREE_TYPE (field), fieldstack,
offset + bitpos_of_field (field), has_union))
&& DECL_SIZE (field)
&& !integer_zerop (DECL_SIZE (field)))
push = true;
if (push)
{
fieldoff_s *pair;
pair = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
pair->type = TREE_TYPE (field);
pair->size = DECL_SIZE (field);
pair->decl = field;
pair->offset = offset + bitpos_of_field (field);
count++;
}
else
count += pushed;
}
return count;
}
static void
make_constraint_from_escaped (varinfo_t vi)
{
struct constraint_expr lhs, rhs;
lhs.var = vi->id;
lhs.offset = 0;
lhs.type = SCALAR;
rhs.var = escaped_vars_id;
rhs.offset = 0;
rhs.type = SCALAR;
process_constraint (new_constraint (lhs, rhs));
}
static void
make_constraint_to_escaped (struct constraint_expr rhs)
{
struct constraint_expr lhs;
lhs.var = escaped_vars_id;
lhs.offset = 0;
lhs.type = SCALAR;
process_constraint (new_constraint (lhs, rhs));
}
static unsigned int
count_num_arguments (tree decl, bool *is_varargs)
{
unsigned int i = 0;
tree t;
for (t = TYPE_ARG_TYPES (TREE_TYPE (decl));
t;
t = TREE_CHAIN (t))
{
if (TREE_VALUE (t) == void_type_node)
break;
i++;
}
if (!t)
*is_varargs = true;
return i;
}
static unsigned int
create_function_info_for (tree decl, const char *name)
{
unsigned int index = VEC_length (varinfo_t, varmap);
varinfo_t vi;
tree arg;
unsigned int i;
bool is_varargs = false;
vi = new_var_info (decl, index, name, index);
vi->decl = decl;
vi->offset = 0;
vi->has_union = 0;
vi->size = 1;
vi->fullsize = count_num_arguments (decl, &is_varargs) + 1;
insert_id_for_tree (vi->decl, index);
VEC_safe_push (varinfo_t, heap, varmap, vi);
stats.total_vars++;
if (is_varargs)
{
vi->fullsize = ~0;
vi->size = ~0;
vi->is_unknown_size_var = true;
return index;
}
arg = DECL_ARGUMENTS (decl);
for (i = 1; i < vi->fullsize; i++)
{
varinfo_t argvi;
const char *newname;
char *tempname;
unsigned int newindex;
tree argdecl = decl;
if (arg)
argdecl = arg;
newindex = VEC_length (varinfo_t, varmap);
asprintf (&tempname, "%s.arg%d", name, i-1);
newname = ggc_strdup (tempname);
free (tempname);
argvi = new_var_info (argdecl, newindex,newname, newindex);
argvi->decl = argdecl;
VEC_safe_push (varinfo_t, heap, varmap, argvi);
argvi->offset = i;
argvi->size = 1;
argvi->fullsize = vi->fullsize;
argvi->has_union = false;
insert_into_field_list_sorted (vi, argvi);
stats.total_vars ++;
if (arg)
{
insert_id_for_tree (arg, newindex);
arg = TREE_CHAIN (arg);
}
}
if (DECL_RESULT (decl) != NULL
|| !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (decl))))
{
varinfo_t resultvi;
const char *newname;
char *tempname;
unsigned int newindex;
tree resultdecl = decl;
vi->fullsize ++;
if (DECL_RESULT (decl))
resultdecl = DECL_RESULT (decl);
newindex = VEC_length (varinfo_t, varmap);
asprintf (&tempname, "%s.result", name);
newname = ggc_strdup (tempname);
free (tempname);
resultvi = new_var_info (resultdecl, newindex, newname, newindex);
resultvi->decl = resultdecl;
VEC_safe_push (varinfo_t, heap, varmap, resultvi);
resultvi->offset = i;
resultvi->size = 1;
resultvi->fullsize = vi->fullsize;
resultvi->has_union = false;
insert_into_field_list_sorted (vi, resultvi);
stats.total_vars ++;
if (DECL_RESULT (decl))
insert_id_for_tree (DECL_RESULT (decl), newindex);
}
return index;
}
static bool
check_for_overlaps (VEC (fieldoff_s,heap) *fieldstack)
{
fieldoff_s *fo = NULL;
unsigned int i;
HOST_WIDE_INT lastoffset = -1;
for (i = 0; VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
{
if (fo->offset == lastoffset)
return true;
lastoffset = fo->offset;
}
return false;
}
static tree
find_global_initializers (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED,
void *viv)
{
varinfo_t vi = (varinfo_t)viv;
tree t = *tp;
switch (TREE_CODE (t))
{
case INDIRECT_REF:
case ADDR_EXPR:
{
struct constraint_expr *c;
size_t i;
VEC(ce_s, heap) *rhsc = NULL;
get_constraint_for (t, &rhsc);
for (i = 0; VEC_iterate (ce_s, rhsc, i, c); i++)
{
struct constraint_expr lhs;
lhs.var = vi->id;
lhs.type = SCALAR;
lhs.offset = 0;
process_constraint (new_constraint (lhs, *c));
}
VEC_free (ce_s, heap, rhsc);
}
break;
case VAR_DECL:
if (referenced_vars)
{
get_var_ann (t);
if (referenced_var_check_and_insert (t))
mark_sym_for_renaming (t);
}
break;
default:
break;
}
return NULL_TREE;
}
static unsigned int
create_variable_info_for (tree decl, const char *name)
{
unsigned int index = VEC_length (varinfo_t, varmap);
varinfo_t vi;
tree decltype = TREE_TYPE (decl);
tree declsize = DECL_P (decl) ? DECL_SIZE (decl) : TYPE_SIZE (decltype);
bool notokay = false;
bool hasunion;
bool is_global = DECL_P (decl) ? is_global_var (decl) : false;
VEC (fieldoff_s,heap) *fieldstack = NULL;
if (TREE_CODE (decl) == FUNCTION_DECL && in_ipa_mode)
return create_function_info_for (decl, name);
hasunion = TREE_CODE (decltype) == UNION_TYPE
|| TREE_CODE (decltype) == QUAL_UNION_TYPE;
if (var_can_have_subvars (decl) && use_field_sensitive && !hasunion)
{
push_fields_onto_fieldstack (decltype, &fieldstack, 0, &hasunion);
if (hasunion)
{
VEC_free (fieldoff_s, heap, fieldstack);
notokay = true;
}
}
vi = new_var_info (decl, index, name, index);
vi->decl = decl;
vi->offset = 0;
vi->has_union = hasunion;
if (!declsize
|| TREE_CODE (declsize) != INTEGER_CST
|| TREE_CODE (decltype) == UNION_TYPE
|| TREE_CODE (decltype) == QUAL_UNION_TYPE)
{
vi->is_unknown_size_var = true;
vi->fullsize = ~0;
vi->size = ~0;
}
else
{
vi->fullsize = TREE_INT_CST_LOW (declsize);
vi->size = vi->fullsize;
}
insert_id_for_tree (vi->decl, index);
VEC_safe_push (varinfo_t, heap, varmap, vi);
if (is_global && (!flag_whole_program || !in_ipa_mode))
{
make_constraint_from_escaped (vi);
if (may_be_aliased (vi->decl))
{
struct constraint_expr rhs;
rhs.var = index;
rhs.type = ADDRESSOF;
rhs.offset = 0;
make_constraint_to_escaped (rhs);
}
if (TREE_CODE (decl) != FUNCTION_DECL && DECL_INITIAL (decl))
{
walk_tree_without_duplicates (&DECL_INITIAL (decl),
find_global_initializers,
(void *)vi);
}
}
stats.total_vars++;
if (use_field_sensitive
&& !notokay
&& !vi->is_unknown_size_var
&& var_can_have_subvars (decl)
&& VEC_length (fieldoff_s, fieldstack) <= MAX_FIELDS_FOR_FIELD_SENSITIVE)
{
unsigned int newindex = VEC_length (varinfo_t, varmap);
fieldoff_s *fo = NULL;
unsigned int i;
for (i = 0; !notokay && VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
{
if (! fo->size
|| TREE_CODE (fo->size) != INTEGER_CST
|| fo->offset < 0)
{
notokay = true;
break;
}
}
if (!notokay)
{
sort_fieldstack (fieldstack);
notokay = check_for_overlaps (fieldstack);
}
if (VEC_length (fieldoff_s, fieldstack) != 0)
fo = VEC_index (fieldoff_s, fieldstack, 0);
if (fo == NULL || notokay)
{
vi->is_unknown_size_var = 1;
vi->fullsize = ~0;
vi->size = ~0;
VEC_free (fieldoff_s, heap, fieldstack);
return index;
}
vi->size = TREE_INT_CST_LOW (fo->size);
vi->offset = fo->offset;
for (i = VEC_length (fieldoff_s, fieldstack) - 1;
i >= 1 && VEC_iterate (fieldoff_s, fieldstack, i, fo);
i--)
{
varinfo_t newvi;
const char *newname = "NULL";
char *tempname;
newindex = VEC_length (varinfo_t, varmap);
if (dump_file)
{
if (fo->decl)
asprintf (&tempname, "%s.%s",
vi->name, alias_get_name (fo->decl));
else
asprintf (&tempname, "%s." HOST_WIDE_INT_PRINT_DEC,
vi->name, fo->offset);
newname = ggc_strdup (tempname);
free (tempname);
}
newvi = new_var_info (decl, newindex, newname, newindex);
newvi->offset = fo->offset;
newvi->size = TREE_INT_CST_LOW (fo->size);
newvi->fullsize = vi->fullsize;
insert_into_field_list (vi, newvi);
VEC_safe_push (varinfo_t, heap, varmap, newvi);
if (is_global && (!flag_whole_program || !in_ipa_mode))
{
if (may_be_aliased (vi->decl))
{
struct constraint_expr rhs;
rhs.var = newindex;
rhs.type = ADDRESSOF;
rhs.offset = 0;
make_constraint_to_escaped (rhs);
}
make_constraint_from_escaped (newvi);
}
stats.total_vars++;
}
VEC_free (fieldoff_s, heap, fieldstack);
}
return index;
}
void
dump_solution_for_var (FILE *file, unsigned int var)
{
varinfo_t vi = get_varinfo (var);
unsigned int i;
bitmap_iterator bi;
fprintf (file, "%s = { ", vi->name);
EXECUTE_IF_SET_IN_BITMAP (get_varinfo (vi->node)->solution, 0, i, bi)
{
fprintf (file, "%s ", get_varinfo (i)->name);
}
fprintf (file, "}\n");
}
void
debug_solution_for_var (unsigned int var)
{
dump_solution_for_var (stdout, var);
}
static void
intra_create_variable_infos (void)
{
tree t;
struct constraint_expr lhs, rhs;
varinfo_t nonlocal_vi;
for (t = DECL_ARGUMENTS (current_function_decl); t; t = TREE_CHAIN (t))
{
varinfo_t p;
unsigned int arg_id;
if (!could_have_pointers (t))
continue;
arg_id = get_id_for_tree (t);
if (POINTER_TYPE_P (TREE_TYPE (t))
&& flag_argument_noalias > 2)
{
varinfo_t vi;
tree heapvar = heapvar_lookup (t);
unsigned int id;
lhs.offset = 0;
lhs.type = SCALAR;
lhs.var = get_id_for_tree (t);
if (heapvar == NULL_TREE)
{
heapvar = create_tmp_var_raw (TREE_TYPE (TREE_TYPE (t)),
"PARM_NOALIAS");
DECL_EXTERNAL (heapvar) = 1;
if (referenced_vars)
add_referenced_var (heapvar);
heapvar_insert (t, heapvar);
}
id = get_id_for_tree (heapvar);
vi = get_varinfo (id);
vi->is_artificial_var = 1;
vi->is_heap_var = 1;
rhs.var = id;
rhs.type = ADDRESSOF;
rhs.offset = 0;
for (p = get_varinfo (lhs.var); p; p = p->next)
{
struct constraint_expr temp = lhs;
temp.var = p->id;
process_constraint (new_constraint (temp, rhs));
}
}
else
{
for (p = get_varinfo (arg_id); p; p = p->next)
make_constraint_from_escaped (p);
}
}
if (!nonlocal_all)
nonlocal_all = create_nonlocal_var (void_type_node);
nonlocal_vars_id = create_variable_info_for (nonlocal_all,
get_name (nonlocal_all));
nonlocal_vi = get_varinfo (nonlocal_vars_id);
nonlocal_vi->is_artificial_var = 1;
nonlocal_vi->is_heap_var = 1;
nonlocal_vi->is_unknown_size_var = 1;
nonlocal_vi->directly_dereferenced = true;
rhs.var = nonlocal_vars_id;
rhs.type = ADDRESSOF;
rhs.offset = 0;
lhs.var = escaped_vars_id;
lhs.type = SCALAR;
lhs.offset = 0;
process_constraint (new_constraint (lhs, rhs));
}
static void
set_uids_in_ptset (tree ptr, bitmap into, bitmap from)
{
unsigned int i;
bitmap_iterator bi;
subvar_t sv;
unsigned HOST_WIDE_INT ptr_alias_set = get_alias_set (TREE_TYPE (ptr));
EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
{
varinfo_t vi = get_varinfo (i);
unsigned HOST_WIDE_INT var_alias_set;
if (vi->is_artificial_var && !vi->is_heap_var)
continue;
if (vi->has_union && get_subvars_for_var (vi->decl) != NULL)
{
for (sv = get_subvars_for_var (vi->decl); sv; sv = sv->next)
bitmap_set_bit (into, DECL_UID (sv->var));
}
else if (TREE_CODE (vi->decl) == VAR_DECL
|| TREE_CODE (vi->decl) == PARM_DECL)
{
if (var_can_have_subvars (vi->decl)
&& get_subvars_for_var (vi->decl))
{
tree sft = get_subvar_at (vi->decl, vi->offset);
if (sft)
{
var_alias_set = get_alias_set (sft);
if (!vi->directly_dereferenced
|| alias_sets_conflict_p (ptr_alias_set, var_alias_set))
bitmap_set_bit (into, DECL_UID (sft));
}
}
else
{
if (vi->is_artificial_var)
bitmap_set_bit (into, DECL_UID (vi->decl));
else
{
var_alias_set = get_alias_set (vi->decl);
if (!vi->directly_dereferenced
|| alias_sets_conflict_p (ptr_alias_set, var_alias_set))
bitmap_set_bit (into, DECL_UID (vi->decl));
}
}
}
}
}
static bool have_alias_info = false;
bool
find_what_p_points_to (tree p)
{
unsigned int id = 0;
tree lookup_p = p;
if (!have_alias_info)
return false;
if (TREE_CODE (p) == SSA_NAME
&& TREE_CODE (SSA_NAME_VAR (p)) == PARM_DECL
&& default_def (SSA_NAME_VAR (p)) == p)
lookup_p = SSA_NAME_VAR (p);
if (lookup_id_for_tree (lookup_p, &id))
{
varinfo_t vi = get_varinfo (id);
if (vi->is_artificial_var)
return false;
if (vi->size != vi->fullsize)
{
if (!var_can_have_subvars (vi->decl)
|| get_subvars_for_var (vi->decl) == NULL)
return false;
}
else
{
struct ptr_info_def *pi = get_ptr_info (p);
unsigned int i;
bitmap_iterator bi;
vi = get_varinfo (vi->node);
EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
{
varinfo_t vi = get_varinfo (i);
if (vi->is_artificial_var)
{
if (vi->id == nothing_id)
pi->pt_null = 1;
else if (vi->id == anything_id)
pi->pt_anything = 1;
else if (vi->id == readonly_id)
pi->pt_anything = 1;
else if (vi->id == integer_id)
pi->pt_anything = 1;
else if (vi->is_heap_var)
pi->pt_global_mem = 1;
}
}
if (pi->pt_anything)
return false;
if (!pi->pt_vars)
pi->pt_vars = BITMAP_GGC_ALLOC ();
set_uids_in_ptset (vi->decl, pi->pt_vars, vi->solution);
if (bitmap_empty_p (pi->pt_vars))
pi->pt_vars = NULL;
return true;
}
}
return false;
}
void
dump_sa_points_to_info (FILE *outfile)
{
unsigned int i;
fprintf (outfile, "\nPoints-to sets\n\n");
if (dump_flags & TDF_STATS)
{
fprintf (outfile, "Stats:\n");
fprintf (outfile, "Total vars: %d\n", stats.total_vars);
fprintf (outfile, "Statically unified vars: %d\n",
stats.unified_vars_static);
fprintf (outfile, "Collapsed vars: %d\n", stats.collapsed_vars);
fprintf (outfile, "Dynamically unified vars: %d\n",
stats.unified_vars_dynamic);
fprintf (outfile, "Iterations: %d\n", stats.iterations);
fprintf (outfile, "Number of edges: %d\n", stats.num_edges);
}
for (i = 0; i < VEC_length (varinfo_t, varmap); i++)
dump_solution_for_var (outfile, i);
}
void
debug_sa_points_to_info (void)
{
dump_sa_points_to_info (stderr);
}
static void
init_base_vars (void)
{
struct constraint_expr lhs, rhs;
nothing_tree = create_tmp_var_raw (void_type_node, "NULL");
var_nothing = new_var_info (nothing_tree, 0, "NULL", 0);
insert_id_for_tree (nothing_tree, 0);
var_nothing->is_artificial_var = 1;
var_nothing->offset = 0;
var_nothing->size = ~0;
var_nothing->fullsize = ~0;
var_nothing->is_special_var = 1;
nothing_id = 0;
VEC_safe_push (varinfo_t, heap, varmap, var_nothing);
anything_tree = create_tmp_var_raw (void_type_node, "ANYTHING");
var_anything = new_var_info (anything_tree, 1, "ANYTHING", 1);
insert_id_for_tree (anything_tree, 1);
var_anything->is_artificial_var = 1;
var_anything->size = ~0;
var_anything->offset = 0;
var_anything->next = NULL;
var_anything->fullsize = ~0;
var_anything->is_special_var = 1;
anything_id = 1;
VEC_safe_push (varinfo_t, heap, varmap, var_anything);
lhs.type = SCALAR;
lhs.var = anything_id;
lhs.offset = 0;
rhs.type = ADDRESSOF;
rhs.var = anything_id;
rhs.offset = 0;
var_anything->address_taken = true;
VEC_safe_push (constraint_t, heap, constraints, new_constraint (lhs, rhs));
readonly_tree = create_tmp_var_raw (void_type_node, "READONLY");
var_readonly = new_var_info (readonly_tree, 2, "READONLY", 2);
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;
insert_id_for_tree (readonly_tree, 2);
readonly_id = 2;
VEC_safe_push (varinfo_t, heap, varmap, var_readonly);
lhs.type = SCALAR;
lhs.var = readonly_id;
lhs.offset = 0;
rhs.type = ADDRESSOF;
rhs.var = anything_id;
rhs.offset = 0;
process_constraint (new_constraint (lhs, rhs));
integer_tree = create_tmp_var_raw (void_type_node, "INTEGER");
var_integer = new_var_info (integer_tree, 3, "INTEGER", 3);
insert_id_for_tree (integer_tree, 3);
var_integer->is_artificial_var = 1;
var_integer->size = ~0;
var_integer->fullsize = ~0;
var_integer->offset = 0;
var_integer->next = NULL;
var_integer->is_special_var = 1;
integer_id = 3;
VEC_safe_push (varinfo_t, heap, varmap, var_integer);
lhs.type = SCALAR;
lhs.var = integer_id;
lhs.offset = 0;
rhs.type = ADDRESSOF;
rhs.var = anything_id;
rhs.offset = 0;
process_constraint (new_constraint (lhs, rhs));
escaped_vars_tree = create_tmp_var_raw (void_type_node, "ESCAPED_VARS");
var_escaped_vars = new_var_info (escaped_vars_tree, 4, "ESCAPED_VARS", 4);
insert_id_for_tree (escaped_vars_tree, 4);
var_escaped_vars->is_artificial_var = 1;
var_escaped_vars->size = ~0;
var_escaped_vars->fullsize = ~0;
var_escaped_vars->offset = 0;
var_escaped_vars->next = NULL;
escaped_vars_id = 4;
VEC_safe_push (varinfo_t, heap, varmap, var_escaped_vars);
lhs.type = SCALAR;
lhs.var = escaped_vars_id;
lhs.offset = 0;
rhs.type = DEREF;
rhs.var = escaped_vars_id;
rhs.offset = 0;
process_constraint (new_constraint (lhs, rhs));
}
static void
init_alias_vars (void)
{
bitmap_obstack_initialize (&ptabitmap_obstack);
bitmap_obstack_initialize (&predbitmap_obstack);
constraint_pool = create_alloc_pool ("Constraint pool",
sizeof (struct constraint), 30);
variable_info_pool = create_alloc_pool ("Variable info pool",
sizeof (struct variable_info), 30);
constraint_edge_pool = create_alloc_pool ("Constraint edges",
sizeof (struct constraint_edge), 30);
constraints = VEC_alloc (constraint_t, heap, 8);
varmap = VEC_alloc (varinfo_t, heap, 8);
id_for_tree = htab_create (10, tree_id_hash, tree_id_eq, free);
memset (&stats, 0, sizeof (stats));
init_base_vars ();
}
static void
find_escape_constraints (tree stmt)
{
enum escape_type stmt_escape_type = is_escape_site (stmt);
tree rhs;
VEC(ce_s, heap) *rhsc = NULL;
struct constraint_expr *c;
size_t i;
if (stmt_escape_type == NO_ESCAPE)
return;
if (TREE_CODE (stmt) == RETURN_EXPR)
{
if (!TREE_OPERAND (stmt, 0))
return;
if (TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR)
rhs = TREE_OPERAND (TREE_OPERAND (stmt, 0), 1);
else
rhs = TREE_OPERAND (stmt, 0);
get_constraint_for (rhs, &rhsc);
for (i = 0; VEC_iterate (ce_s, rhsc, i, c); i++)
make_constraint_to_escaped (*c);
VEC_free (ce_s, heap, rhsc);
return;
}
else if (TREE_CODE (stmt) == ASM_EXPR)
{
tree arg;
for (arg = ASM_INPUTS (stmt); arg; arg = TREE_CHAIN (arg))
{
rhsc = NULL;
get_constraint_for (TREE_VALUE (arg), &rhsc);
for (i = 0; VEC_iterate (ce_s, rhsc, i, c); i++)
make_constraint_to_escaped (*c);
VEC_free (ce_s, heap, rhsc);
}
return;
}
else if (TREE_CODE (stmt) == CALL_EXPR
|| (TREE_CODE (stmt) == MODIFY_EXPR
&& TREE_CODE (TREE_OPERAND (stmt, 1)) == CALL_EXPR))
{
tree arg;
if (TREE_CODE (stmt) == MODIFY_EXPR)
stmt = TREE_OPERAND (stmt, 1);
for (arg = TREE_OPERAND (stmt, 1); arg; arg = TREE_CHAIN (arg))
{
if (POINTER_TYPE_P (TREE_TYPE (TREE_VALUE (arg))))
{
rhsc = NULL;
get_constraint_for (TREE_VALUE (arg), &rhsc);
for (i = 0; VEC_iterate (ce_s, rhsc, i, c); i++)
make_constraint_to_escaped (*c);
VEC_free (ce_s, heap, rhsc);
}
}
return;
}
else
{
gcc_assert (TREE_CODE (stmt) == MODIFY_EXPR);
}
gcc_assert (stmt_escape_type == ESCAPE_BAD_CAST
|| stmt_escape_type == ESCAPE_STORED_IN_GLOBAL
|| stmt_escape_type == ESCAPE_UNKNOWN);
rhs = TREE_OPERAND (stmt, 1);
if (TREE_CODE (rhs) == NOP_EXPR
|| TREE_CODE (rhs) == CONVERT_EXPR
|| TREE_CODE (rhs) == NON_LVALUE_EXPR)
{
get_constraint_for (TREE_OPERAND (rhs, 0), &rhsc);
}
else if (CONSTANT_CLASS_P (rhs))
return;
else
{
get_constraint_for (rhs, &rhsc);
}
for (i = 0; VEC_iterate (ce_s, rhsc, i, c); i++)
make_constraint_to_escaped (*c);
VEC_free (ce_s, heap, rhsc);
}
void
compute_points_to_sets (struct alias_info *ai)
{
basic_block bb;
timevar_push (TV_TREE_PTA);
init_alias_vars ();
intra_create_variable_infos ();
FOR_EACH_BB (bb)
{
block_stmt_iterator bsi;
tree phi;
for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
{
if (is_gimple_reg (PHI_RESULT (phi)))
{
find_func_aliases (phi);
update_alias_info (phi, ai);
}
}
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
{
tree stmt = bsi_stmt (bsi);
find_func_aliases (stmt);
find_escape_constraints (stmt);
update_alias_info (stmt, ai);
}
}
build_constraint_graph ();
if (dump_file)
{
fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
dump_constraints (dump_file);
}
if (dump_file)
fprintf (dump_file,
"\nCollapsing static cycles and doing variable "
"substitution:\n");
find_and_collapse_graph_cycles (graph, false);
perform_var_substitution (graph);
if (dump_file)
fprintf (dump_file, "\nSolving graph:\n");
solve_graph (graph);
if (dump_file)
dump_sa_points_to_info (dump_file);
have_alias_info = true;
timevar_pop (TV_TREE_PTA);
}
void
delete_points_to_sets (void)
{
varinfo_t v;
int i;
htab_delete (id_for_tree);
bitmap_obstack_release (&ptabitmap_obstack);
bitmap_obstack_release (&predbitmap_obstack);
VEC_free (constraint_t, heap, constraints);
for (i = 0; VEC_iterate (varinfo_t, varmap, i, v); i++)
{
if (i >= graph_size)
break;
VEC_free (constraint_edge_t, heap, graph->succs[i]);
VEC_free (constraint_edge_t, heap, graph->preds[i]);
VEC_free (constraint_t, heap, v->complex);
}
free (graph->zero_weight_preds);
free (graph->zero_weight_succs);
free (graph->succs);
free (graph->preds);
free (graph);
VEC_free (varinfo_t, heap, varmap);
free_alloc_pool (variable_info_pool);
free_alloc_pool (constraint_pool);
free_alloc_pool (constraint_edge_pool);
have_alias_info = false;
}
static bool
gate_ipa_pta (void)
{
return (flag_unit_at_a_time != 0
&& flag_ipa_pta
&& !(errorcount || sorrycount));
}
static unsigned int
ipa_pta_execute (void)
{
struct cgraph_node *node;
in_ipa_mode = 1;
init_alias_heapvars ();
init_alias_vars ();
for (node = cgraph_nodes; node; node = node->next)
{
if (!node->analyzed || cgraph_is_master_clone (node))
{
unsigned int varid;
varid = create_function_info_for (node->decl,
cgraph_node_name (node));
if (node->local.externally_visible)
{
varinfo_t fi = get_varinfo (varid);
for (; fi; fi = fi->next)
make_constraint_from_escaped (fi);
}
}
}
for (node = cgraph_nodes; node; node = node->next)
{
if (node->analyzed && cgraph_is_master_clone (node))
{
struct function *cfun = DECL_STRUCT_FUNCTION (node->decl);
basic_block bb;
tree old_func_decl = current_function_decl;
if (dump_file)
fprintf (dump_file,
"Generating constraints for %s\n",
cgraph_node_name (node));
push_cfun (cfun);
current_function_decl = node->decl;
FOR_EACH_BB_FN (bb, cfun)
{
block_stmt_iterator bsi;
tree phi;
for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
{
if (is_gimple_reg (PHI_RESULT (phi)))
{
find_func_aliases (phi);
}
}
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
{
tree stmt = bsi_stmt (bsi);
find_func_aliases (stmt);
}
}
current_function_decl = old_func_decl;
pop_cfun ();
}
else
{
}
}
build_constraint_graph ();
if (dump_file)
{
fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
dump_constraints (dump_file);
}
if (dump_file)
fprintf (dump_file,
"\nCollapsing static cycles and doing variable "
"substitution:\n");
find_and_collapse_graph_cycles (graph, false);
perform_var_substitution (graph);
if (dump_file)
fprintf (dump_file, "\nSolving graph:\n");
solve_graph (graph);
if (dump_file)
dump_sa_points_to_info (dump_file);
in_ipa_mode = 0;
delete_alias_heapvars ();
delete_points_to_sets ();
return 0;
}
struct tree_opt_pass pass_ipa_pta =
{
"pta",
gate_ipa_pta,
ipa_pta_execute,
NULL,
NULL,
0,
TV_IPA_PTA,
0,
0,
0,
0,
0,
0
};
void
init_alias_heapvars (void)
{
heapvar_for_stmt = htab_create_ggc (11, tree_map_hash, tree_map_eq,
NULL);
nonlocal_all = NULL_TREE;
}
void
delete_alias_heapvars (void)
{
nonlocal_all = NULL_TREE;
htab_delete (heapvar_for_stmt);
}
#include "gt-tree-ssa-structalias.h"