variable substitution. */
int *eq_rep;
- /* Pointer equivalence node for a node. if pe[a] != a, then node a
- can be united with node pe[a] after initial constraint building. */
+ /* Pointer equivalence label for a node. All nodes with the same
+ pointer equivalence label can be unified together at some point
+ (either during constraint optimization or after the constraint
+ graph is built). */
unsigned int *pe;
/* Pointer equivalence representative for a label. This is used to
graph->indirect_cycles = XNEWVEC (int, graph->size);
graph->rep = XNEWVEC (unsigned int, graph->size);
graph->complex = XCNEWVEC (VEC(constraint_t, heap) *, size);
- graph->pe = XNEWVEC (unsigned int, graph->size);
+ graph->pe = XCNEWVEC (unsigned int, graph->size);
graph->pe_rep = XNEWVEC (int, graph->size);
for (j = 0; j < graph->size; j++)
{
graph->rep[j] = j;
- graph->pe[j] = j;
graph->pe_rep[j] = -1;
graph->indirect_cycles[j] = -1;
}
changed_count--;
}
}
-
- /* If the solution changes because of the merging, we need to mark
- the variable as changed. */
- if (bitmap_ior_into (get_varinfo (to)->solution,
- get_varinfo (from)->solution))
+ if (get_varinfo (from)->solution)
{
- if (update_changed && !TEST_BIT (changed, to))
+ /* If the solution changes because of the merging, we need to mark
+ the variable as changed. */
+ if (bitmap_ior_into (get_varinfo (to)->solution,
+ get_varinfo (from)->solution))
{
- SET_BIT (changed, to);
- changed_count++;
+ if (update_changed && !TEST_BIT (changed, to))
+ {
+ SET_BIT (changed, to);
+ changed_count++;
+ }
+ }
+
+ BITMAP_FREE (get_varinfo (from)->solution);
+ BITMAP_FREE (get_varinfo (from)->oldsolution);
+
+ if (stats.iterations > 0)
+ {
+ BITMAP_FREE (get_varinfo (to)->oldsolution);
+ get_varinfo (to)->oldsolution = BITMAP_ALLOC (&oldpta_obstack);
}
}
-
- BITMAP_FREE (get_varinfo (from)->solution);
- BITMAP_FREE (get_varinfo (from)->oldsolution);
-
- if (stats.iterations > 0)
- {
- BITMAP_FREE (get_varinfo (to)->oldsolution);
- get_varinfo (to)->oldsolution = BITMAP_ALLOC (&oldpta_obstack);
- }
-
if (valid_graph_edge (graph, to, to))
{
if (graph->succs[to])
else if (add_graph_edge (graph, lhs, t))
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:
}
}
}
- else if (0 && dump_file && !(get_varinfo (j)->is_special_var))
- fprintf (dump_file, "Untypesafe usage in do_ds_constraint\n");
}
}
/* Condense the nodes, which means to find SCC's, count incoming
predecessors, and unite nodes in SCC's. */
- for (i = 0; i < LAST_REF_NODE; i++)
+ for (i = 0; i < FIRST_REF_NODE; i++)
if (!TEST_BIT (si->visited, si->node_mapping[i]))
condense_visit (graph, si, si->node_mapping[i]);
sbitmap_zero (si->visited);
/* Actually the label the nodes for pointer equivalences */
- for (i = 0; i < LAST_REF_NODE; i++)
+ for (i = 0; i < FIRST_REF_NODE; i++)
if (!TEST_BIT (si->visited, si->node_mapping[i]))
label_visit (graph, si, si->node_mapping[i]);
{
unsigned int node = si->node_mapping[i];
- if (graph->pointer_label[node] == 0
- && TEST_BIT (graph->direct_nodes, node))
+ if (graph->pointer_label[node] == 0)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file,
/* Go through the pointer equivalences and unite them to their
representative, if they aren't already. */
- for (i = 0; i < graph->size; i++)
+ for (i = 0; i < FIRST_REF_NODE; i++)
{
unsigned int label = graph->pe[i];
- int label_rep = graph->pe_rep[label];
-
- if (label != i && unite (label_rep, i))
- unify_nodes (graph, label_rep, i, false);
+ if (label)
+ {
+ int label_rep = graph->pe_rep[label];
+
+ if (label_rep == -1)
+ continue;
+
+ label_rep = find (label_rep);
+ if (label_rep >= 0 && unite (label_rep, find (i)))
+ unify_nodes (graph, label_rep, i, false);
+ }
}
}
the constraint. */
if (lhslabel == 0)
{
- if (!TEST_BIT (graph->direct_nodes, lhsnode))
- lhslabel = graph->pointer_label[lhsnode] = pointer_equiv_class++;
- else
+ if (dump_file && (dump_flags & TDF_DETAILS))
{
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
-
- fprintf (dump_file, "%s is a non-pointer variable,"
- "ignoring constraint:",
- get_varinfo (lhs.var)->name);
- dump_constraint (dump_file, c);
- }
- VEC_replace (constraint_t, constraints, i, NULL);
- continue;
+
+ fprintf (dump_file, "%s is a non-pointer variable,"
+ "ignoring constraint:",
+ get_varinfo (lhs.var)->name);
+ dump_constraint (dump_file, c);
}
+ VEC_replace (constraint_t, constraints, i, NULL);
+ continue;
}
if (rhslabel == 0)
{
- if (!TEST_BIT (graph->direct_nodes, rhsnode))
- rhslabel = graph->pointer_label[rhsnode] = pointer_equiv_class++;
- else
+ if (dump_file && (dump_flags & TDF_DETAILS))
{
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
-
- fprintf (dump_file, "%s is a non-pointer variable,"
- "ignoring constraint:",
- get_varinfo (rhs.var)->name);
- dump_constraint (dump_file, c);
- }
- VEC_replace (constraint_t, constraints, i, NULL);
- continue;
+
+ fprintf (dump_file, "%s is a non-pointer variable,"
+ "ignoring constraint:",
+ get_varinfo (rhs.var)->name);
+ dump_constraint (dump_file, c);
}
+ VEC_replace (constraint_t, constraints, i, NULL);
+ continue;
}
lhsvar = find_equivalent_node (graph, lhsvar, lhslabel);
}
-/* Return true if an access to [ACCESSPOS, ACCESSSIZE]
- overlaps with a field at [FIELDPOS, FIELDSIZE] */
-
-static bool
-offset_overlaps_with_access (const unsigned HOST_WIDE_INT fieldpos,
- const unsigned HOST_WIDE_INT fieldsize,
- const unsigned HOST_WIDE_INT accesspos,
- const unsigned HOST_WIDE_INT accesssize)
-{
- if (fieldpos == accesspos && fieldsize == accesssize)
- return true;
- if (accesspos >= fieldpos && accesspos < (fieldpos + fieldsize))
- return true;
- if (accesspos < fieldpos && (accesspos + accesssize > fieldpos))
- return true;
-
- return false;
-}
-
/* Given a COMPONENT_REF T, return the constraint_expr for it. */
static void
t = get_ref_base_and_extent (t, &bitpos, &bitsize, &bitmaxsize);
- /* String constants are readonly, so there is nothing to really do
- here. */
- if (TREE_CODE (t) == STRING_CST)
- return;
-
get_constraint_for (t, results);
result = VEC_last (ce_s, *results);
result->offset = bitpos;
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))
+ if (ranges_overlap_p (curr->offset, curr->size,
+ result->offset, bitmaxsize))
{
result->var = curr->id;
break;
return;
}
+ /* String constants are read-only. */
+ if (TREE_CODE (t) == STRING_CST)
+ {
+ temp.var = readonly_id;
+ temp.type = SCALAR;
+ 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 NOP_EXPR:
- case CONVERT_EXPR:
- case NON_LVALUE_EXPR:
+ CASE_CONVERT:
{
tree op = TREE_OPERAND (t, 0);
}
}
+/* This structure is used during pushing fields onto the fieldstack
+ to track the offset of the field, since bitpos_of_field gives it
+ relative to its immediate containing type, and we want it relative
+ to the ultimate containing object. */
+
+struct fieldoff
+{
+ /* Type of the field. */
+ tree type;
+
+ /* Size, in bits, of the field. */
+ tree size;
+
+ /* Field. */
+ tree decl;
+
+ /* Offset from the base of the base containing object to this field. */
+ HOST_WIDE_INT offset;
+};
+typedef struct fieldoff fieldoff_s;
+
+DEF_VEC_O(fieldoff_s);
+DEF_VEC_ALLOC_O(fieldoff_s,heap);
+
/* qsort comparison function for two fieldoff's PA and PB */
static int
}
/* Sort a fieldstack according to the field offset and sizes. */
-void
+static void
sort_fieldstack (VEC(fieldoff_s,heap) *fieldstack)
{
qsort (VEC_address (fieldoff_s, fieldstack),
fieldoff_compare);
}
-/* Given a TYPE, and a vector of field offsets FIELDSTACK, push all the fields
- of TYPE onto fieldstack, recording their offsets along the way.
- OFFSET is used to keep track of the offset in this entire structure, rather
- than just the immediately containing structure. Returns the number
- of fields pushed.
- HAS_UNION is set to true if we find a union type as a field of
- TYPE. ADDRESSABLE_TYPE is the type of the outermost object that could have
- its address taken. */
+/* Return true if V is a tree that we can have subvars for.
+ Normally, this is any aggregate type. Also complex
+ types which are not gimple registers can have subvars. */
-int
-push_fields_onto_fieldstack (tree type, VEC(fieldoff_s,heap) **fieldstack,
- HOST_WIDE_INT offset, bool *has_union,
- tree addressable_type)
+static inline bool
+var_can_have_subvars (const_tree v)
{
- tree field;
- int count = 0;
+ /* Volatile variables should never have subvars. */
+ if (TREE_THIS_VOLATILE (v))
+ return false;
- 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;
- real_part->alias_set = -1;
-
- 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;
- img_part->alias_set = -1;
-
- return 2;
- }
+ /* Non decls or memory tags can never have subvars. */
+ if (!DECL_P (v) || MTAG_P (v))
+ return false;
- if (TREE_CODE (type) == ARRAY_TYPE)
- {
- tree sz = TYPE_SIZE (type);
- tree elsz = TYPE_SIZE (TREE_TYPE (type));
- HOST_WIDE_INT nr;
- int i;
+ /* Aggregates without overlapping fields can have subvars. */
+ if (TREE_CODE (TREE_TYPE (v)) == RECORD_TYPE)
+ return true;
- 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;
+ return false;
+}
- nr = TREE_INT_CST_LOW (sz) / TREE_INT_CST_LOW (elsz);
- if (nr > SALIAS_MAX_ARRAY_ELEMENTS)
- return 0;
+/* Given a TYPE, and a vector of field offsets FIELDSTACK, push all
+ the fields of TYPE onto fieldstack, recording their offsets along
+ the way.
- 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))) /* var_can_have_subvars */
- push = true;
- else if (!(pushed = push_fields_onto_fieldstack
- (TREE_TYPE (type), fieldstack,
- offset + i * TREE_INT_CST_LOW (elsz), has_union,
- (TYPE_NONALIASED_COMPONENT (type)
- ? addressable_type
- : TREE_TYPE (type)))))
- /* Empty structures may have actual size, like in C++. So
- see if we didn't push any subfields and the size is
- nonzero, push the field onto the stack */
- 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);
- if (TYPE_NONALIASED_COMPONENT (type))
- pair->alias_set = get_alias_set (addressable_type);
- else
- pair->alias_set = -1;
- count++;
- }
- else
- count += pushed;
- }
+ OFFSET is used to keep track of the offset in this entire
+ structure, rather than just the immediately containing structure.
+ Returns the number of fields pushed.
- return count;
- }
+ HAS_UNION is set to true if we find a union type as a field of
+ TYPE. */
+
+static 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) != RECORD_TYPE)
+ return 0;
+
+ /* If the vector of fields is growing too big, bail out early.
+ Callers check for VEC_length <= MAX_FIELDS_FOR_FIELD_SENSITIVE, make
+ sure this fails. */
+ if (VEC_length (fieldoff_s, *fieldstack) > MAX_FIELDS_FOR_FIELD_SENSITIVE)
+ return 0;
for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
if (TREE_CODE (field) == FIELD_DECL)
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_NONADDRESSABLE_P (field)
- ? addressable_type
- : TREE_TYPE (field))))
- && DECL_SIZE (field)
- && !integer_zerop (DECL_SIZE (field)))
- /* Empty structures may have actual size, like in C++. So
+ (TREE_TYPE (field),
+ fieldstack,
+ offset + bitpos_of_field (field),
+ has_union))
+ && (DECL_SIZE (field)
+ && !integer_zerop (DECL_SIZE (field))))
+ /* Empty structures may have actual size, like in C++. So
see if we didn't push any subfields and the size is
- nonzero, push the field onto the stack */
+ nonzero, push the field onto the stack. */
push = true;
if (push)
pair->size = DECL_SIZE (field);
pair->decl = field;
pair->offset = offset + bitpos_of_field (field);
- if (DECL_NONADDRESSABLE_P (field))
- pair->alias_set = get_alias_set (addressable_type);
- else
- pair->alias_set = -1;
count++;
}
else
|| TREE_CODE (decltype) == QUAL_UNION_TYPE;
if (var_can_have_subvars (decl) && use_field_sensitive && !hasunion)
{
- push_fields_onto_fieldstack (decltype, &fieldstack, 0, &hasunion,
- decltype);
+ push_fields_onto_fieldstack (decltype, &fieldstack, 0, &hasunion);
if (hasunion)
{
VEC_free (fieldoff_s, heap, fieldstack);
}
}
-
/* If the variable doesn't have subvars, we may end up needing to
sort the field list and create fake variables for all the
fields. */
&& !notokay
&& !vi->is_unknown_size_var
&& var_can_have_subvars (decl)
+ && VEC_length (fieldoff_s, fieldstack) > 1
&& VEC_length (fieldoff_s, fieldstack) <= MAX_FIELDS_FOR_FIELD_SENSITIVE)
{
unsigned int newindex = VEC_length (varinfo_t, varmap);
stats.total_vars++;
}
- VEC_free (fieldoff_s, heap, fieldstack);
}
+
+ VEC_free (fieldoff_s, heap, fieldstack);
+
return index;
}
{
unsigned int i;
bitmap_iterator bi;
- subvar_t sv;
- alias_set_type ptr_alias_set = get_alias_set (TREE_TYPE (ptr));
+
+ gcc_assert (POINTER_TYPE_P (TREE_TYPE (ptr)));
EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
{
varinfo_t vi = get_varinfo (i);
- alias_set_type var_alias_set;
/* The only artificial variables that are allowed in a may-alias
set are heap variables. */
if (vi->is_artificial_var && !vi->is_heap_var)
continue;
- if (vi->has_union && get_subvars_for_var (vi->decl) != NULL)
- {
- /* Variables containing unions may need to be converted to
- their SFT's, because SFT's can have unions and we cannot. */
- for (sv = get_subvars_for_var (vi->decl); sv; sv = sv->next)
- bitmap_set_bit (into, DECL_UID (sv->var));
- }
- else if (TREE_CODE (vi->decl) == VAR_DECL
- || TREE_CODE (vi->decl) == PARM_DECL
- || TREE_CODE (vi->decl) == RESULT_DECL)
+ if (TREE_CODE (vi->decl) == VAR_DECL
+ || TREE_CODE (vi->decl) == PARM_DECL
+ || TREE_CODE (vi->decl) == RESULT_DECL)
{
- if (var_can_have_subvars (vi->decl)
- && get_subvars_for_var (vi->decl))
- {
- /* If VI->DECL is an aggregate for which we created
- SFTs, add the SFT corresponding to VI->OFFSET. */
- tree sft = get_subvar_at (vi->decl, vi->offset);
- gcc_assert (sft);
- if (sft)
- {
- var_alias_set = get_alias_set (sft);
- if (no_tbaa_pruning
- || (!is_derefed && !vi->directly_dereferenced)
- || alias_sets_conflict_p (ptr_alias_set, var_alias_set))
- bitmap_set_bit (into, DECL_UID (sft));
- }
- }
+ /* Just add VI->DECL to the alias set.
+ Don't type prune artificial vars. */
+ if (vi->is_artificial_var)
+ bitmap_set_bit (into, DECL_UID (vi->decl));
else
{
- /* Otherwise, just add VI->DECL to the alias set.
- Don't type prune artificial vars. */
- if (vi->is_artificial_var)
- bitmap_set_bit (into, DECL_UID (vi->decl));
- else
- {
- var_alias_set = get_alias_set (vi->decl);
- if (no_tbaa_pruning
- || (!is_derefed && !vi->directly_dereferenced)
- || alias_sets_conflict_p (ptr_alias_set, var_alias_set))
- bitmap_set_bit (into, DECL_UID (vi->decl));
- }
+ alias_set_type var_alias_set, ptr_alias_set;
+ var_alias_set = get_alias_set (vi->decl);
+ ptr_alias_set = get_alias_set (TREE_TYPE (TREE_TYPE (ptr)));
+ if (no_tbaa_pruning
+ || (!is_derefed && !vi->directly_dereferenced)
+ || alias_sets_conflict_p (ptr_alias_set, var_alias_set))
+ bitmap_set_bit (into, DECL_UID (vi->decl));
}
}
}
static void
merge_smts_into (tree p, bitmap solution)
{
- unsigned int i;
- bitmap_iterator bi;
tree smt;
bitmap aliases;
tree var = p;
smt = var_ann (var)->symbol_mem_tag;
if (smt)
{
- alias_set_type smtset = get_alias_set (TREE_TYPE (smt));
-
- /* Need to set the SMT subsets first before this
- will work properly. */
+ /* The smt itself isn't included in its aliases. */
bitmap_set_bit (solution, DECL_UID (smt));
- EXECUTE_IF_SET_IN_BITMAP (used_smts, 0, i, bi)
- {
- tree newsmt = referenced_var (i);
- tree newsmttype = TREE_TYPE (newsmt);
-
- if (alias_set_subset_of (get_alias_set (newsmttype),
- smtset))
- bitmap_set_bit (solution, i);
- }
aliases = MTAG_ALIASES (smt);
if (aliases)
/* Nothing currently asks about structure fields directly,
but when they do, we need code here to hand back the
points-to set. */
- if (!var_can_have_subvars (vi->decl)
- || get_subvars_for_var (vi->decl) == NULL)
- return false;
+ return false;
}
else
{
}
/* Share the final set of variables when possible. */
-
finished_solution = BITMAP_GGC_ALLOC ();
stats.points_to_sets_created++;
/* Instead of using pt_anything, we merge in the SMT aliases
for the underlying SMT. In addition, if they could have
- pointed to anything, they could point to global memory.
- But we cannot do that for ref-all pointers because these
- aliases have not been computed yet. */
+ pointed to anything, they could point to global memory. */
if (was_pt_anything)
{
- if (PTR_IS_REF_ALL (p))
- {
- pi->pt_anything = 1;
- return false;
- }
-
merge_smts_into (p, finished_solution);
pi->pt_global_mem = 1;
}
- set_uids_in_ptset (vi->decl, finished_solution, vi->solution,
+ set_uids_in_ptset (p, finished_solution, vi->solution,
vi->directly_dereferenced,
vi->no_tbaa_pruning);
result = shared_bitmap_lookup (finished_solution);
{
if (node->analyzed && cgraph_is_master_clone (node))
{
- struct function *cfun = DECL_STRUCT_FUNCTION (node->decl);
+ struct function *func = 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);
+ push_cfun (func);
current_function_decl = node->decl;
- FOR_EACH_BB_FN (bb, cfun)
+ FOR_EACH_BB_FN (bb, func)
{
block_stmt_iterator bsi;
tree phi;
return 0;
}
-struct tree_opt_pass pass_ipa_pta =
+struct simple_ipa_opt_pass pass_ipa_pta =
{
+ {
+ SIMPLE_IPA_PASS,
"pta", /* name */
gate_ipa_pta, /* gate */
ipa_pta_execute, /* execute */
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
- TODO_update_ssa, /* todo_flags_finish */
- 0 /* letter */
+ TODO_update_ssa /* todo_flags_finish */
+ }
};
/* Initialize the heapvar for statement mapping. */
OSDN Git Service
