get_subvar_at (tree var, unsigned HOST_WIDE_INT offset)
{
subvar_t sv = get_subvars_for_var (var);
- unsigned int i;
+ int low, high;
+
+ low = 0;
+ high = VEC_length (tree, sv) - 1;
+ while (low <= high)
+ {
+ int mid = (low + high) / 2;
+ tree subvar = VEC_index (tree, sv, mid);
+ if (SFT_OFFSET (subvar) == offset)
+ return subvar;
+ else if (SFT_OFFSET (subvar) < offset)
+ low = mid + 1;
+ else
+ high = mid - 1;
+ }
+
+ return NULL_TREE;
+}
+
+
+/* Return the first subvariable in SV that overlaps [offset, offset + size[.
+ NULL_TREE is returned, if there is no overlapping subvariable, else *I
+ is set to the index in the SV vector of the first overlap. */
+
+static inline tree
+get_first_overlapping_subvar (subvar_t sv, unsigned HOST_WIDE_INT offset,
+ unsigned HOST_WIDE_INT size, unsigned int *i)
+{
+ int low = 0;
+ int high = VEC_length (tree, sv) - 1;
+ int mid;
tree subvar;
- /* ??? Binary search would be possible here. */
- for (i = 0; VEC_iterate (tree, sv, i, subvar); ++i)
- if (SFT_OFFSET (subvar) == offset)
+ if (low > high)
+ return NULL_TREE;
+
+ /* Binary search for offset. */
+ do
+ {
+ mid = (low + high) / 2;
+ subvar = VEC_index (tree, sv, mid);
+ if (SFT_OFFSET (subvar) == offset)
+ {
+ *i = mid;
+ return subvar;
+ }
+ else if (SFT_OFFSET (subvar) < offset)
+ low = mid + 1;
+ else
+ high = mid - 1;
+ }
+ while (low <= high);
+
+ /* As we didn't find a subvar with offset, adjust to return the
+ first overlapping one. */
+ if (SFT_OFFSET (subvar) < offset
+ && SFT_OFFSET (subvar) + SFT_SIZE (subvar) <= offset)
+ {
+ mid += 1;
+ if ((unsigned)mid >= VEC_length (tree, sv))
+ return NULL_TREE;
+ subvar = VEC_index (tree, sv, mid);
+ }
+ else if (SFT_OFFSET (subvar) > offset
+ && size <= SFT_OFFSET (subvar) - offset)
+ {
+ mid -= 1;
+ if (mid < 0)
+ return NULL_TREE;
+ subvar = VEC_index (tree, sv, mid);
+ }
+
+ if (overlap_subvar (offset, size, subvar, NULL))
+ {
+ *i = mid;
return subvar;
+ }
return NULL_TREE;
}
+
/* 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. */
This is necessary because foop only actually points to foo's first
member, so that is all the points-to set contains. However, an access
to foop->a may be touching some single SFT if we have created some
- SFT's for a structure. If AS_PTO is false, just add VAR to the vops. */
+ SFT's for a structure. */
static bool
-add_vars_for_offset (tree full_ref, tree var, HOST_WIDE_INT offset,
- HOST_WIDE_INT size, bool is_call_site, bool is_def,
- bool as_pto)
+add_vars_for_offset (tree var,
+ unsigned HOST_WIDE_INT offset, unsigned HOST_WIDE_INT size,
+ bool is_def, bitmap mpt_vars)
{
bool added = false;
+ tree subvar;
subvar_t sv;
unsigned int i;
- tree subvar;
+ /* Adjust offset by the pointed-to location. */
+ offset += SFT_OFFSET (var);
- /* Call-clobbered tags may have non-call-clobbered
- symbols in their alias sets. Ignore them if we are
- adding VOPs for a call site. */
- if (is_call_site && !is_call_clobbered (var))
+ /* Add all subvars of var that overlap with the access.
+ Binary search for the first relevant SFT. */
+ sv = get_subvars_for_var (SFT_PARENT_VAR (var));
+ if (!get_first_overlapping_subvar (sv, offset, size, &i))
return false;
- /* For SFTs we have to consider all subvariables of the parent var. */
- if (TREE_CODE (var) != STRUCT_FIELD_TAG
- || !as_pto)
+ for (; VEC_iterate (tree, sv, i, subvar); ++i)
{
- /* If we do not know the full reference tree or if the access is
- unspecified [0, -1], we cannot prune it. Otherwise try doing
- so using access_can_touch_variable. */
- if (full_ref
- && !(offset == 0 && size == -1)
- && !access_can_touch_variable (full_ref, var, offset, size))
- return false;
-
- if (is_def)
- append_vdef (var);
- else
- append_vuse (var);
- return true;
- }
-
- sv = get_subvars_for_var (SFT_PARENT_VAR (var));
- for (i = 0; VEC_iterate (tree, sv, i, subvar); ++i)
- {
- /* Once we hit the end of the parts that could touch,
- stop looking. */
- if (size != -1
- && SFT_OFFSET (var) + offset + size <= SFT_OFFSET (subvar))
+ if (size <= SFT_OFFSET (subvar) - offset)
break;
- if (overlap_subvar (SFT_OFFSET (var) + offset, size, subvar, NULL))
+
+ /* Avoid adding a SFT that is contained in the same MPT as the
+ pointed-to location as this MPT will be added as alias anyway. */
+ if (!mpt_vars
+ || !bitmap_bit_p (mpt_vars, DECL_UID (subvar)))
{
- added = true;
if (is_def)
append_vdef (subvar);
else
append_vuse (subvar);
}
+ added = true;
}
- return added;
-}
-/* Consider all SFTs in ALIASES as points-to location and add virtual
- operands for the SFT parent var for the access FULL_REF at OFFSET
- and size SIZE. IS_CALL_SITE is true if the stmt of the reference is
- a call. IS_DEF is true if we should add VDEF virtual operands,
- otherwise we'll add VUSEs. *NONE_ADDED is set to false once the first
- virtual operand was added. */
-
-static void
-add_vars_for_bitmap (bitmap aliases, tree full_ref,
- HOST_WIDE_INT offset, HOST_WIDE_INT size,
- bool is_call_site, bool is_def, bool *none_added)
-{
- bitmap_iterator bi;
- unsigned int i;
-
- EXECUTE_IF_SET_IN_BITMAP (aliases, 0, i, bi)
- {
- tree al = referenced_var (i);
-
- gcc_assert (TREE_CODE (al) != MEMORY_PARTITION_TAG);
-
- if (TREE_CODE (al) == STRUCT_FIELD_TAG)
- *none_added &= !add_vars_for_offset (full_ref, al, offset, size,
- is_call_site, is_def, true);
- }
+ return added;
}
/* Add VAR to the virtual operands array. FLAGS is as in
But only if we start with NMT aliases. */
if (TREE_CODE (al) == MEMORY_PARTITION_TAG
&& TREE_CODE (var) == NAME_MEMORY_TAG)
- add_vars_for_bitmap (MPT_SYMBOLS (al), full_ref, offset, size,
- is_call_site, flags & opf_def, &none_added);
- none_added &= !add_vars_for_offset (full_ref, al, offset, size,
- is_call_site, flags & opf_def,
- TREE_CODE (var) == NAME_MEMORY_TAG);
+ {
+ bitmap_iterator bi;
+ unsigned int i;
+
+ EXECUTE_IF_SET_IN_BITMAP (MPT_SYMBOLS (al), 0, i, bi)
+ {
+ tree ptsft = referenced_var (i);
+
+ if (TREE_CODE (ptsft) == STRUCT_FIELD_TAG)
+ none_added &= !add_vars_for_offset (ptsft, offset, size,
+ flags & opf_def,
+ MPT_SYMBOLS (al));
+ }
+ }
+
+ /* For SFTs we have to consider all subvariables of the parent var
+ if it is a potential points-to location. */
+ if (TREE_CODE (al) == STRUCT_FIELD_TAG
+ && TREE_CODE (var) == NAME_MEMORY_TAG)
+ none_added &= !add_vars_for_offset (al, offset, size,
+ flags & opf_def, NULL);
+ else
+ {
+ /* Call-clobbered tags may have non-call-clobbered
+ symbols in their alias sets. Ignore them if we are
+ adding VOPs for a call site. */
+ if (is_call_site && !is_call_clobbered (al))
+ continue;
+
+ /* If we do not know the full reference tree or if the access is
+ unspecified [0, -1], we cannot prune it. Otherwise try doing
+ so using access_can_touch_variable. */
+ if (full_ref
+ && !(offset == 0 && size == -1)
+ && !access_can_touch_variable (full_ref, al, offset, size))
+ continue;
+
+ if (flags & opf_def)
+ append_vdef (al);
+ else
+ append_vuse (al);
+ none_added = false;
+ }
}
if (flags & opf_def)
OSDN Git Service
