* [PATCH] Speedup PTA
@ 2013-03-18 12:51 Richard Biener
0 siblings, 0 replies; only message in thread
From: Richard Biener @ 2013-03-18 12:51 UTC (permalink / raw)
To: gcc-patches
This patch, long on my TODO list, speeds up PTA by removing the
costly hashtable lookup when looking for related fields of
a sub-variable. Instead we now keep a pointer to the first
field. For space-savings I changed head/next to be the variable
info ID instead. This speeds up a fortran testcase by 10%.
Bootstrap & regtest running on x86_64-unknown-linux-gnu.
Richard.
2013-03-18 Richard Biener <rguenther@suse.de>
* tree-ssa-structalias.c (struct variable_info): Add pointer
to the first field of an aggregate with sub-vars. Make
this and the pointer to the next subfield its ID.
(vi_next): New function.
(nothing_id, anything_id, readonly_id, escaped_id, nonlocal_id,
storedanything_id, integer_id): Increment by one.
(new_var_info, get_call_vi, lookup_call_clobber_vi,
get_call_clobber_vi): Adjust.
(solution_set_expand): Simplify and speedup.
(solution_set_add): Inline into ...
(set_union_with_increment): ... this. Adjust accordingly.
(do_sd_constraint): Likewise.
(do_ds_constraint): Likewise.
(do_complex_constraint): Simplify.
(build_pred_graph): Adjust.
(solve_graph): Likewise. Simplify and speedup.
(get_constraint_for_ssa_var, get_constraint_for_ptr_offset,
get_constraint_for_component_ref, get_constraint_for_1,
first_vi_for_offset, first_or_preceding_vi_for_offset,
create_function_info_for, create_variable_info_for_1,
create_variable_info_for, intra_create_variable_infos): Adjust.
(init_base_vars): Push NULL for ID zero.
(compute_points_to_sets): Adjust.
Index: gcc/tree-ssa-structalias.c
===================================================================
*** gcc/tree-ssa-structalias.c.orig 2013-03-18 12:41:57.000000000 +0100
--- gcc/tree-ssa-structalias.c 2013-03-18 13:38:23.141158010 +0100
*************** struct variable_info
*** 268,275 ****
/* True if this represents a IPA function info. */
unsigned int is_fn_info : 1;
! /* A link to the variable for the next field in this structure. */
! struct variable_info *next;
/* Offset of this variable, in bits, from the base variable */
unsigned HOST_WIDE_INT offset;
--- 268,279 ----
/* True if this represents a IPA function info. */
unsigned int is_fn_info : 1;
! /* 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;
*************** get_varinfo (unsigned int n)
*** 319,328 ****
return varmap[n];
}
! /* Static IDs for the special variables. */
! enum { nothing_id = 0, anything_id = 1, readonly_id = 2,
! escaped_id = 3, nonlocal_id = 4,
! storedanything_id = 5, integer_id = 6 };
/* Return a new variable info structure consisting for a variable
named NAME, and using constraint graph node NODE. Append it
--- 323,342 ----
return varmap[n];
}
! /* 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, readonly_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
*************** new_var_info (tree t, const char *name)
*** 355,361 ****
&& DECL_HARD_REGISTER (t)));
ret->solution = BITMAP_ALLOC (&pta_obstack);
ret->oldsolution = NULL;
! ret->next = NULL;
stats.total_vars++;
--- 369,376 ----
&& DECL_HARD_REGISTER (t)));
ret->solution = BITMAP_ALLOC (&pta_obstack);
ret->oldsolution = NULL;
! ret->next = 0;
! ret->head = ret->id;
stats.total_vars++;
*************** get_call_vi (gimple call)
*** 387,398 ****
vi->fullsize = 2;
vi->is_full_var = true;
! vi->next = vi2 = new_var_info (NULL_TREE, "CALLCLOBBERED");
vi2->offset = 1;
vi2->size = 1;
vi2->fullsize = 2;
vi2->is_full_var = true;
*slot_p = (void *) vi;
return vi;
}
--- 402,415 ----
vi->fullsize = 2;
vi->is_full_var = true;
! vi2 = new_var_info (NULL_TREE, "CALLCLOBBERED");
vi2->offset = 1;
vi2->size = 1;
vi2->fullsize = 2;
vi2->is_full_var = true;
+ vi->next = vi2->id;
+
*slot_p = (void *) vi;
return vi;
}
*************** lookup_call_clobber_vi (gimple call)
*** 422,428 ****
if (!uses)
return NULL;
! return uses->next;
}
/* Lookup or create the variable for the call statement CALL representing
--- 439,445 ----
if (!uses)
return NULL;
! return vi_next (uses);
}
/* Lookup or create the variable for the call statement CALL representing
*************** get_call_use_vi (gimple call)
*** 440,446 ****
static varinfo_t ATTRIBUTE_UNUSED
get_call_clobber_vi (gimple call)
{
! return get_call_vi (call)->next;
}
--- 457,463 ----
static varinfo_t ATTRIBUTE_UNUSED
get_call_clobber_vi (gimple call)
{
! return vi_next (get_call_vi (call));
}
*************** dump_constraint_graph (FILE *file)
*** 701,708 ****
/* The next lines print the nodes in the graph together with the
complex constraints attached to them. */
! for (i = 0; i < graph->size; i++)
{
if (find (i) != i)
continue;
if (i < FIRST_REF_NODE)
--- 718,727 ----
/* 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 (find (i) != i)
continue;
if (i < FIRST_REF_NODE)
*************** dump_constraint_graph (FILE *file)
*** 726,732 ****
/* Go over the edges. */
fprintf (file, "\n // Edges in the constraint graph:\n");
! for (i = 0; i < graph->size; i++)
{
unsigned j;
bitmap_iterator bi;
--- 745,751 ----
/* 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;
*************** constraint_set_union (vec<constraint_t>
*** 881,943 ****
}
}
! /* Expands the solution in SET to all sub-fields of variables included.
! Union the expanded result into RESULT. */
static void
! solution_set_expand (bitmap result, bitmap set)
{
bitmap_iterator bi;
- bitmap vars = NULL;
unsigned j;
! /* In a first pass record all variables we need to add all
! sub-fields off. This avoids quadratic behavior. */
EXECUTE_IF_SET_IN_BITMAP (set, 0, j, bi)
{
varinfo_t v = get_varinfo (j);
if (v->is_artificial_var
|| v->is_full_var)
continue;
! v = lookup_vi_for_tree (v->decl);
! if (vars == NULL)
! vars = BITMAP_ALLOC (NULL);
! bitmap_set_bit (vars, v->id);
}
! /* In the second pass now do the addition to the solution and
! to speed up solving add it to the delta as well. */
! if (vars != NULL)
{
! EXECUTE_IF_SET_IN_BITMAP (vars, 0, j, bi)
! {
! varinfo_t v = get_varinfo (j);
! for (; v != NULL; v = v->next)
! bitmap_set_bit (result, v->id);
! }
! BITMAP_FREE (vars);
}
}
! /* Take a solution set SET, add OFFSET to each member of the set, and
! overwrite SET with the result when done. */
! static void
! solution_set_add (bitmap set, HOST_WIDE_INT offset)
{
! bitmap result = BITMAP_ALLOC (&iteration_obstack);
! unsigned int i;
bitmap_iterator bi;
/* If the offset is unknown we have to expand the solution to
all subfields. */
! if (offset == UNKNOWN_OFFSET)
{
! solution_set_expand (set, set);
! return;
}
! EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
{
varinfo_t vi = get_varinfo (i);
--- 900,970 ----
}
}
! /* Expands the solution in SET to all sub-fields of variables included. */
static void
! solution_set_expand (bitmap set)
{
bitmap_iterator bi;
unsigned j;
! /* 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;
! bitmap_set_bit (set, v->head);
}
! /* In the second pass now expand all head variables with subfields. */
! EXECUTE_IF_SET_IN_BITMAP (set, 0, j, bi)
{
! varinfo_t v = get_varinfo (j);
! if (v->is_artificial_var
! || v->is_full_var
! || v->head != j)
! continue;
! for (v = vi_next (v); v != NULL; v = vi_next (v))
! bitmap_set_bit (set, v->id);
}
}
! /* 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)
{
! bool changed = false;
bitmap_iterator bi;
+ unsigned int i;
+
+ /* If the solution of FROM contains anything it is good enough to transfer
+ this to TO. */
+ if (bitmap_bit_p (from, anything_id))
+ return bitmap_set_bit (to, anything_id);
+
+ /* For zero offset simply union the solution into the destination. */
+ if (inc == 0)
+ return bitmap_ior_into (to, from);
/* If the offset is unknown we have to expand the solution to
all subfields. */
! if (inc == UNKNOWN_OFFSET)
{
! bitmap tmp = BITMAP_ALLOC (&iteration_obstack);
! bitmap_copy (tmp, from);
! solution_set_expand (tmp);
! changed |= bitmap_ior_into (to, tmp);
! BITMAP_FREE (tmp);
! return changed;
}
! /* For non-zero offset union the offsetted solution into the destination. */
! EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
{
varinfo_t vi = get_varinfo (i);
*************** solution_set_add (bitmap set, HOST_WIDE_
*** 946,999 ****
if (vi->is_artificial_var
|| vi->is_unknown_size_var
|| vi->is_full_var)
! bitmap_set_bit (result, i);
else
{
! unsigned HOST_WIDE_INT fieldoffset = vi->offset + offset;
/* If the offset makes the pointer point to before the
variable use offset zero for the field lookup. */
! if (offset < 0
&& fieldoffset > vi->offset)
fieldoffset = 0;
! if (offset != 0)
! vi = first_or_preceding_vi_for_offset (vi, fieldoffset);
! bitmap_set_bit (result, vi->id);
/* If the result is not exactly at fieldoffset include the next
field as well. See get_constraint_for_ptr_offset for more
rationale. */
if (vi->offset != fieldoffset
! && vi->next != NULL)
! bitmap_set_bit (result, vi->next->id);
}
}
! bitmap_copy (set, result);
! BITMAP_FREE (result);
! }
!
! /* Union solution sets TO and FROM, and add INC to each member of FROM in the
! process. */
!
! static bool
! set_union_with_increment (bitmap to, bitmap from, HOST_WIDE_INT inc)
! {
! if (inc == 0)
! return bitmap_ior_into (to, from);
! else
! {
! bitmap tmp;
! bool res;
!
! tmp = BITMAP_ALLOC (&iteration_obstack);
! bitmap_copy (tmp, from);
! solution_set_add (tmp, inc);
! res = bitmap_ior_into (to, tmp);
! BITMAP_FREE (tmp);
! return res;
! }
}
/* Insert constraint C into the list of complex constraints for graph
--- 973,1002 ----
if (vi->is_artificial_var
|| vi->is_unknown_size_var
|| vi->is_full_var)
! changed |= bitmap_set_bit (to, i);
else
{
! unsigned HOST_WIDE_INT fieldoffset = vi->offset + inc;
/* If the offset makes the pointer point to before the
variable use offset zero for the field lookup. */
! if (inc < 0
&& fieldoffset > vi->offset)
fieldoffset = 0;
! vi = first_or_preceding_vi_for_offset (vi, fieldoffset);
! changed |= bitmap_set_bit (to, 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 != 0)
! changed |= bitmap_set_bit (to, vi->next);
}
}
! return changed;
}
/* Insert constraint C into the list of complex constraints for graph
*************** build_pred_graph (void)
*** 1190,1196 ****
graph->address_taken = BITMAP_ALLOC (&predbitmap_obstack);
bitmap_clear (graph->direct_nodes);
! for (j = 0; j < FIRST_REF_NODE; j++)
{
if (!get_varinfo (j)->is_special_var)
bitmap_set_bit (graph->direct_nodes, j);
--- 1193,1199 ----
graph->address_taken = BITMAP_ALLOC (&predbitmap_obstack);
bitmap_clear (graph->direct_nodes);
! for (j = 1; j < FIRST_REF_NODE; j++)
{
if (!get_varinfo (j)->is_special_var)
bitmap_set_bit (graph->direct_nodes, j);
*************** build_pred_graph (void)
*** 1244,1254 ****
v = get_varinfo (rhsvar);
if (!v->is_full_var)
{
! v = lookup_vi_for_tree (v->decl);
do
{
bitmap_clear_bit (graph->direct_nodes, v->id);
! v = v->next;
}
while (v != NULL);
}
--- 1247,1257 ----
v = get_varinfo (rhsvar);
if (!v->is_full_var)
{
! v = get_varinfo (v->head);
do
{
bitmap_clear_bit (graph->direct_nodes, v->id);
! v = vi_next (v);
}
while (v != NULL);
}
*************** do_sd_constraint (constraint_graph_t gra
*** 1578,1584 ****
dereferenced at all valid offsets. */
if (roffset == UNKNOWN_OFFSET)
{
! solution_set_expand (delta, delta);
/* No further offset processing is necessary. */
roffset = 0;
}
--- 1581,1587 ----
dereferenced at all valid offsets. */
if (roffset == UNKNOWN_OFFSET)
{
! solution_set_expand (delta);
/* No further offset processing is necessary. */
roffset = 0;
}
*************** do_sd_constraint (constraint_graph_t gra
*** 1618,1627 ****
/* If the variable is not exactly at the requested offset
we have to include the next one. */
if (v->offset == (unsigned HOST_WIDE_INT)fieldoffset
! || v->next == NULL)
break;
! v = v->next;
fieldoffset = v->offset;
}
while (1);
--- 1621,1630 ----
/* 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 == 0)
break;
! v = vi_next (v);
fieldoffset = v->offset;
}
while (1);
*************** do_ds_constraint (constraint_t c, bitmap
*** 1676,1682 ****
dereferenced at all valid offsets. */
if (loff == UNKNOWN_OFFSET)
{
! solution_set_expand (delta, delta);
loff = 0;
}
--- 1679,1685 ----
dereferenced at all valid offsets. */
if (loff == UNKNOWN_OFFSET)
{
! solution_set_expand (delta);
loff = 0;
}
*************** do_ds_constraint (constraint_t c, bitmap
*** 1724,1733 ****
/* If the variable is not exactly at the requested offset
we have to include the next one. */
if (v->offset == (unsigned HOST_WIDE_INT)fieldoffset
! || v->next == NULL)
break;
! v = v->next;
fieldoffset = v->offset;
}
while (1);
--- 1727,1736 ----
/* 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 == 0)
break;
! v = vi_next (v);
fieldoffset = v->offset;
}
while (1);
*************** do_complex_constraint (constraint_graph_
*** 1771,1780 ****
flag = set_union_with_increment (tmp, solution, c->rhs.offset);
if (flag)
! {
! get_varinfo (c->lhs.var)->solution = tmp;
! bitmap_set_bit (changed, c->lhs.var);
! }
}
}
--- 1774,1780 ----
flag = set_union_with_increment (tmp, solution, c->rhs.offset);
if (flag)
! bitmap_set_bit (changed, c->lhs.var);
}
}
*************** dump_pred_graph (struct scc_info *si, FI
*** 2160,2167 ****
/* The next lines print the nodes in the graph together with the
complex constraints attached to them. */
! for (i = 0; i < graph->size; i++)
{
if (si->node_mapping[i] != i)
continue;
if (i < FIRST_REF_NODE)
--- 2160,2169 ----
/* 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)
*************** dump_pred_graph (struct scc_info *si, FI
*** 2183,2189 ****
/* Go over the edges. */
fprintf (file, "\n // Edges in the constraint graph:\n");
! for (i = 0; i < graph->size; i++)
{
unsigned j;
bitmap_iterator bi;
--- 2185,2191 ----
/* 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;
*************** perform_var_substitution (constraint_gra
*** 2229,2235 ****
/* Condense the nodes, which means to find SCC's, count incoming
predecessors, and unite nodes in SCC's. */
! for (i = 0; i < FIRST_REF_NODE; i++)
if (!bitmap_bit_p (si->visited, si->node_mapping[i]))
condense_visit (graph, si, si->node_mapping[i]);
--- 2231,2237 ----
/* Condense the nodes, which means to find SCC's, count incoming
predecessors, and unite nodes in SCC's. */
! 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]);
*************** perform_var_substitution (constraint_gra
*** 2243,2254 ****
bitmap_clear (si->visited);
/* Actually the label the nodes for pointer equivalences */
! for (i = 0; i < FIRST_REF_NODE; i++)
if (!bitmap_bit_p (si->visited, si->node_mapping[i]))
label_visit (graph, si, si->node_mapping[i]);
/* Calculate location equivalence labels. */
! for (i = 0; i < FIRST_REF_NODE; i++)
{
bitmap pointed_by;
bitmap_iterator bi;
--- 2245,2256 ----
bitmap_clear (si->visited);
/* Actually the label the nodes for pointer equivalences */
! 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 = 1; i < FIRST_REF_NODE; i++)
{
bitmap pointed_by;
bitmap_iterator bi;
*************** perform_var_substitution (constraint_gra
*** 2286,2292 ****
}
if (dump_file && (dump_flags & TDF_DETAILS))
! for (i = 0; i < FIRST_REF_NODE; i++)
{
unsigned j = si->node_mapping[i];
if (j != i)
--- 2288,2294 ----
}
if (dump_file && (dump_flags & TDF_DETAILS))
! for (i = 1; i < FIRST_REF_NODE; i++)
{
unsigned j = si->node_mapping[i];
if (j != i)
*************** perform_var_substitution (constraint_gra
*** 2306,2312 ****
/* Quickly eliminate our non-pointer variables. */
! for (i = 0; i < FIRST_REF_NODE; i++)
{
unsigned int node = si->node_mapping[i];
--- 2308,2314 ----
/* Quickly eliminate our non-pointer variables. */
! for (i = 1; i < FIRST_REF_NODE; i++)
{
unsigned int node = si->node_mapping[i];
*************** unite_pointer_equivalences (constraint_g
*** 2393,2399 ****
/* Go through the pointer equivalences and unite them to their
representative, if they aren't already. */
! for (i = 0; i < FIRST_REF_NODE; i++)
{
unsigned int label = graph->pe[i];
if (label)
--- 2395,2401 ----
/* Go through the pointer equivalences and unite them to their
representative, if they aren't already. */
! for (i = 1; i < FIRST_REF_NODE; i++)
{
unsigned int label = graph->pe[i];
if (label)
*************** solve_graph (constraint_graph_t graph)
*** 2570,2576 ****
changed = BITMAP_ALLOC (NULL);
/* Mark all initial non-collapsed nodes as changed. */
! for (i = 0; i < size; i++)
{
varinfo_t ivi = get_varinfo (i);
if (find (i) == i && !bitmap_empty_p (ivi->solution)
--- 2572,2578 ----
changed = BITMAP_ALLOC (NULL);
/* Mark all initial non-collapsed nodes as changed. */
! for (i = 1; i < size; i++)
{
varinfo_t ivi = get_varinfo (i);
if (find (i) == i && !bitmap_empty_p (ivi->solution)
*************** solve_graph (constraint_graph_t graph)
*** 2617,2624 ****
varinfo_t vi = get_varinfo (i);
bool solution_empty;
! /* Compute the changed set of solution bits. */
! if (vi->oldsolution)
bitmap_and_compl (pts, vi->solution, vi->oldsolution);
else
bitmap_copy (pts, vi->solution);
--- 2619,2637 ----
varinfo_t vi = get_varinfo (i);
bool solution_empty;
! /* 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);
*************** solve_graph (constraint_graph_t graph)
*** 2682,2694 ****
if (i == eff_escaped_id)
flag = bitmap_set_bit (tmp, escaped_id);
else
! flag = set_union_with_increment (tmp, pts, 0);
if (flag)
! {
! get_varinfo (to)->solution = tmp;
! bitmap_set_bit (changed, to);
! }
}
}
}
--- 2695,2704 ----
if (i == eff_escaped_id)
flag = bitmap_set_bit (tmp, escaped_id);
else
! flag = bitmap_ior_into (tmp, pts);
if (flag)
! bitmap_set_bit (changed, to);
}
}
}
*************** get_constraint_for_ssa_var (tree t, vec<
*** 2866,2872 ****
if (!address_p
&& !vi->is_full_var)
{
! for (; vi; vi = vi->next)
{
cexpr.var = vi->id;
results->safe_push (cexpr);
--- 2876,2882 ----
if (!address_p
&& !vi->is_full_var)
{
! for (; vi; vi = vi_next (vi))
{
cexpr.var = vi->id;
results->safe_push (cexpr);
*************** get_constraint_for_ptr_offset (tree ptr,
*** 3013,3019 ****
/* If we do not know the offset add all subfields. */
&& rhsoffset == UNKNOWN_OFFSET)
{
! varinfo_t temp = lookup_vi_for_tree (curr->decl);
do
{
struct constraint_expr c2;
--- 3023,3029 ----
/* If we do not know the offset add all subfields. */
&& rhsoffset == UNKNOWN_OFFSET)
{
! varinfo_t temp = get_varinfo (curr->head);
do
{
struct constraint_expr c2;
*************** get_constraint_for_ptr_offset (tree ptr,
*** 3022,3028 ****
c2.offset = 0;
if (c2.var != c.var)
results->safe_push (c2);
! temp = temp->next;
}
while (temp);
}
--- 3032,3038 ----
c2.offset = 0;
if (c2.var != c.var)
results->safe_push (c2);
! temp = vi_next (temp);
}
while (temp);
}
*************** get_constraint_for_ptr_offset (tree ptr,
*** 3050,3059 ****
do not result in the same or a conservative superset
solution. */
if (temp->offset != offset
! && temp->next != NULL)
{
struct constraint_expr c2;
! c2.var = temp->next->id;
c2.type = ADDRESSOF;
c2.offset = 0;
results->safe_push (c2);
--- 3060,3069 ----
do not result in the same or a conservative superset
solution. */
if (temp->offset != offset
! && temp->next != 0)
{
struct constraint_expr c2;
! c2.var = temp->next;
c2.type = ADDRESSOF;
c2.offset = 0;
results->safe_push (c2);
*************** get_constraint_for_component_ref (tree t
*** 3156,3162 ****
varinfo_t curr;
results->pop ();
cexpr.offset = 0;
! for (curr = get_varinfo (cexpr.var); curr; curr = curr->next)
{
if (ranges_overlap_p (curr->offset, curr->size,
bitpos, bitmaxsize))
--- 3166,3172 ----
varinfo_t curr;
results->pop ();
cexpr.offset = 0;
! for (curr = get_varinfo (cexpr.var); curr; curr = vi_next (curr))
{
if (ranges_overlap_p (curr->offset, curr->size,
bitpos, bitmaxsize))
*************** get_constraint_for_component_ref (tree t
*** 3173,3180 ****
if (address_p && results->length () == 0)
{
curr = get_varinfo (cexpr.var);
! while (curr->next != NULL)
! curr = curr->next;
cexpr.var = curr->id;
results->safe_push (cexpr);
}
--- 3183,3190 ----
if (address_p && results->length () == 0)
{
curr = get_varinfo (cexpr.var);
! while (curr->next != 0)
! curr = vi_next (curr);
cexpr.var = curr->id;
results->safe_push (cexpr);
}
*************** get_constraint_for_1 (tree t, vec<ce_s>
*** 3370,3376 ****
return;
vi = get_varinfo (cs.var);
! curr = vi->next;
if (!vi->is_full_var
&& curr)
{
--- 3380,3386 ----
return;
vi = get_varinfo (cs.var);
! curr = vi_next (vi);
if (!vi->is_full_var
&& curr)
{
*************** get_constraint_for_1 (tree t, vec<ce_s>
*** 3379,3385 ****
size = TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (t)));
else
size = -1;
! for (; curr; curr = curr->next)
{
if (curr->offset - vi->offset < size)
{
--- 3389,3395 ----
size = TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (t)));
else
size = -1;
! for (; curr; curr = vi_next (curr))
{
if (curr->offset - vi->offset < size)
{
*************** first_vi_for_offset (varinfo_t start, un
*** 5075,5081 ****
/* If we cannot reach offset from start, lookup the first field
and start from there. */
if (start->offset > offset)
! start = lookup_vi_for_tree (start->decl);
while (start)
{
--- 5085,5091 ----
/* If we cannot reach offset from start, lookup the first field
and start from there. */
if (start->offset > offset)
! start = get_varinfo (start->head);
while (start)
{
*************** first_vi_for_offset (varinfo_t start, un
*** 5087,5093 ****
&& (offset - start->offset) < start->size)
return start;
! start= start->next;
}
return NULL;
--- 5097,5103 ----
&& (offset - start->offset) < start->size)
return start;
! start = vi_next (start);
}
return NULL;
*************** first_or_preceding_vi_for_offset (varinf
*** 5104,5110 ****
/* If we cannot reach offset from start, lookup the first field
and start from there. */
if (start->offset > offset)
! start = lookup_vi_for_tree (start->decl);
/* We may not find a variable in the field list with the actual
offset when when we have glommed a structure to a variable.
--- 5114,5120 ----
/* If we cannot reach offset from start, lookup the first field
and start from there. */
if (start->offset > offset)
! 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.
*************** first_or_preceding_vi_for_offset (varinf
*** 5115,5121 ****
while (start->next
&& offset >= start->offset
&& !((offset - start->offset) < start->size))
! start = start->next;
return start;
}
--- 5125,5131 ----
while (start->next
&& offset >= start->offset
&& !((offset - start->offset) < start->size))
! start = vi_next (start);
return start;
}
*************** create_function_info_for (tree decl, con
*** 5398,5404 ****
clobbervi->is_full_var = true;
clobbervi->is_global_var = false;
gcc_assert (prev_vi->offset < clobbervi->offset);
! prev_vi->next = clobbervi;
prev_vi = clobbervi;
asprintf (&tempname, "%s.use", name);
--- 5408,5414 ----
clobbervi->is_full_var = true;
clobbervi->is_global_var = false;
gcc_assert (prev_vi->offset < clobbervi->offset);
! prev_vi->next = clobbervi->id;
prev_vi = clobbervi;
asprintf (&tempname, "%s.use", name);
*************** create_function_info_for (tree decl, con
*** 5412,5418 ****
usevi->is_full_var = true;
usevi->is_global_var = false;
gcc_assert (prev_vi->offset < usevi->offset);
! prev_vi->next = usevi;
prev_vi = usevi;
}
--- 5422,5428 ----
usevi->is_full_var = true;
usevi->is_global_var = false;
gcc_assert (prev_vi->offset < usevi->offset);
! prev_vi->next = usevi->id;
prev_vi = usevi;
}
*************** create_function_info_for (tree decl, con
*** 5434,5440 ****
chainvi->is_full_var = true;
chainvi->is_global_var = false;
gcc_assert (prev_vi->offset < chainvi->offset);
! prev_vi->next = chainvi;
prev_vi = chainvi;
insert_vi_for_tree (fn->static_chain_decl, chainvi);
}
--- 5444,5450 ----
chainvi->is_full_var = true;
chainvi->is_global_var = false;
gcc_assert (prev_vi->offset < chainvi->offset);
! prev_vi->next = chainvi->id;
prev_vi = chainvi;
insert_vi_for_tree (fn->static_chain_decl, chainvi);
}
*************** create_function_info_for (tree decl, con
*** 5463,5469 ****
if (DECL_RESULT (decl))
resultvi->may_have_pointers = true;
gcc_assert (prev_vi->offset < resultvi->offset);
! prev_vi->next = resultvi;
prev_vi = resultvi;
if (DECL_RESULT (decl))
insert_vi_for_tree (DECL_RESULT (decl), resultvi);
--- 5473,5479 ----
if (DECL_RESULT (decl))
resultvi->may_have_pointers = true;
gcc_assert (prev_vi->offset < resultvi->offset);
! prev_vi->next = resultvi->id;
prev_vi = resultvi;
if (DECL_RESULT (decl))
insert_vi_for_tree (DECL_RESULT (decl), resultvi);
*************** create_function_info_for (tree decl, con
*** 5493,5499 ****
if (arg)
argvi->may_have_pointers = true;
gcc_assert (prev_vi->offset < argvi->offset);
! prev_vi->next = argvi;
prev_vi = argvi;
if (arg)
{
--- 5503,5509 ----
if (arg)
argvi->may_have_pointers = true;
gcc_assert (prev_vi->offset < argvi->offset);
! prev_vi->next = argvi->id;
prev_vi = argvi;
if (arg)
{
*************** create_function_info_for (tree decl, con
*** 5524,5530 ****
argvi->is_heap_var = true;
argvi->fullsize = vi->fullsize;
gcc_assert (prev_vi->offset < argvi->offset);
! prev_vi->next = argvi;
prev_vi = argvi;
}
--- 5534,5540 ----
argvi->is_heap_var = true;
argvi->fullsize = vi->fullsize;
gcc_assert (prev_vi->offset < argvi->offset);
! prev_vi->next = argvi->id;
prev_vi = argvi;
}
*************** create_variable_info_for_1 (tree decl, c
*** 5638,5644 ****
vi->fullsize = TREE_INT_CST_LOW (declsize);
for (i = 0, newvi = vi;
fieldstack.iterate (i, &fo);
! ++i, newvi = newvi->next)
{
const char *newname = "NULL";
char *tempname;
--- 5648,5654 ----
vi->fullsize = TREE_INT_CST_LOW (declsize);
for (i = 0, newvi = vi;
fieldstack.iterate (i, &fo);
! ++i, newvi = vi_next (newvi))
{
const char *newname = "NULL";
char *tempname;
*************** create_variable_info_for_1 (tree decl, c
*** 5657,5663 ****
newvi->may_have_pointers = fo->may_have_pointers;
newvi->only_restrict_pointers = fo->only_restrict_pointers;
if (i + 1 < fieldstack.length ())
! newvi->next = new_var_info (decl, name);
}
fieldstack.release ();
--- 5667,5677 ----
newvi->may_have_pointers = fo->may_have_pointers;
newvi->only_restrict_pointers = fo->only_restrict_pointers;
if (i + 1 < fieldstack.length ())
! {
! varinfo_t tem = new_var_info (decl, name);
! newvi->next = tem->id;
! tem->head = vi->id;
! }
}
fieldstack.release ();
*************** create_variable_info_for (tree decl, con
*** 5677,5683 ****
return id;
/* Create initial constraints for globals. */
! for (; vi; vi = vi->next)
{
if (!vi->may_have_pointers
|| !vi->is_global_var)
--- 5691,5697 ----
return id;
/* Create initial constraints for globals. */
! for (; vi; vi = vi_next (vi))
{
if (!vi->may_have_pointers
|| !vi->is_global_var)
*************** intra_create_variable_infos (void)
*** 5807,5813 ****
rhsc.type = ADDRESSOF;
rhsc.offset = 0;
process_constraint (new_constraint (lhsc, rhsc));
! for (; vi; vi = vi->next)
if (vi->may_have_pointers)
{
if (vi->only_restrict_pointers)
--- 5821,5827 ----
rhsc.type = ADDRESSOF;
rhsc.offset = 0;
process_constraint (new_constraint (lhsc, rhsc));
! for (; vi; vi = vi_next (vi))
if (vi->may_have_pointers)
{
if (vi->only_restrict_pointers)
*************** intra_create_variable_infos (void)
*** 5823,5829 ****
make_constraint_from_global_restrict (p, "PARM_RESTRICT");
else
{
! for (; p; p = p->next)
{
if (p->only_restrict_pointers)
make_constraint_from_global_restrict (p, "PARM_RESTRICT");
--- 5837,5843 ----
make_constraint_from_global_restrict (p, "PARM_RESTRICT");
else
{
! for (; p; p = vi_next (p))
{
if (p->only_restrict_pointers)
make_constraint_from_global_restrict (p, "PARM_RESTRICT");
*************** intra_create_variable_infos (void)
*** 5839,5845 ****
{
varinfo_t p, result_vi = get_vi_for_tree (DECL_RESULT (cfun->decl));
! for (p = result_vi; p; p = p->next)
make_constraint_from (p, nonlocal_id);
}
--- 5853,5859 ----
{
varinfo_t p, result_vi = get_vi_for_tree (DECL_RESULT (cfun->decl));
! for (p = result_vi; p; p = vi_next (p))
make_constraint_from (p, nonlocal_id);
}
*************** intra_create_variable_infos (void)
*** 5848,5854 ****
{
varinfo_t p, chain_vi = get_vi_for_tree (cfun->static_chain_decl);
! for (p = chain_vi; p; p = p->next)
make_constraint_from (p, nonlocal_id);
}
}
--- 5862,5868 ----
{
varinfo_t p, chain_vi = get_vi_for_tree (cfun->static_chain_decl);
! for (p = chain_vi; p; p = vi_next (p))
make_constraint_from (p, nonlocal_id);
}
}
*************** dump_sa_points_to_info (FILE *outfile)
*** 6363,6369 ****
stats.num_implicit_edges);
}
! for (i = 0; i < varmap.length (); i++)
{
varinfo_t vi = get_varinfo (i);
if (!vi->may_have_pointers)
--- 6377,6383 ----
stats.num_implicit_edges);
}
! for (i = 1; i < varmap.length (); i++)
{
varinfo_t vi = get_varinfo (i);
if (!vi->may_have_pointers)
*************** init_base_vars (void)
*** 6397,6402 ****
--- 6411,6419 ----
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");
*************** init_base_vars (void)
*** 6416,6422 ****
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;
--- 6433,6438 ----
*************** init_base_vars (void)
*** 6443,6449 ****
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
--- 6459,6464 ----
*************** init_base_vars (void)
*** 6540,6546 ****
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
--- 6555,6560 ----
*************** remove_preds_and_fake_succs (constraint_
*** 6595,6601 ****
/* Clear the implicit ref and address nodes from the successor
lists. */
! for (i = 0; i < FIRST_REF_NODE; i++)
{
if (graph->succs[i])
bitmap_clear_range (graph->succs[i], FIRST_REF_NODE,
--- 6609,6615 ----
/* Clear the implicit ref and address nodes from the successor
lists. */
! for (i = 1; i < FIRST_REF_NODE; i++)
{
if (graph->succs[i])
bitmap_clear_range (graph->succs[i], FIRST_REF_NODE,
*************** remove_preds_and_fake_succs (constraint_
*** 6603,6609 ****
}
/* Free the successor list for the non-ref nodes. */
! for (i = FIRST_REF_NODE; i < graph->size; i++)
{
if (graph->succs[i])
BITMAP_FREE (graph->succs[i]);
--- 6617,6623 ----
}
/* Free the successor list for the non-ref nodes. */
! for (i = FIRST_REF_NODE + 1; i < graph->size; i++)
{
if (graph->succs[i])
BITMAP_FREE (graph->succs[i]);
*************** compute_points_to_sets (void)
*** 6750,6756 ****
/* 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);
--- 6764,6771 ----
/* Mark escaped HEAP variables as global. */
FOR_EACH_VEC_ELT (varmap, i, vi)
! if (vi
! && 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);
^ permalink raw reply [flat|nested] only message in thread
only message in thread, other threads:[~2013-03-18 12:51 UTC | newest]
Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2013-03-18 12:51 [PATCH] Speedup PTA Richard Biener
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).