[PATCH][RFC] Instrument alias oracle
Richard Guenther
rguenther@suse.de
Fri Feb 6 14:49:00 GMT 2009
I am somewhat stuck with finding a reasonable coarse/fine instrumentation
level with either counters or timevars for the alias-oracle. Diego, as
you requested this you may have an idea here.
Basically there are multiple entires into the oracle each of which may
end up calling other entries. Pushing/popping a timevar on every
entry will make that pushing/popping very costly (I guess I could
try optimizing recursive pushing/popping of the same timevar in
timevar.c), so the patch below adds it to the most expensive entry
but also attributes the callback time (which is in its only use
right now SCCVN lookup code).
As a different but iteresting instrumentation kind the patch
instruments all different disambiguations in refs_may_alias_p
with statistic counters, only bailing out on must-aliases but
continuing to count other disambiguators even if a previous
one said no-alias. This allows telling apart the most effective
disambiguators and may help sorting them. This instrumentation
is costly as well, and somehow even makes the code more ugly.
So - do we just want to attribute all alias-oracle time to
a single timevar? Which also uglifies code as you have to
pop the timevar on every function exit, like for example if
one would push at the entry of refs_may_alias_p.
Thoughts?
Richard.
2009-02-06 Richard Guenther <rguenther@suse.de>
* timevar.def (TV_ALIAS_STMT_WALK): New timevar.
* tree-ssa-alias.c (refs_may_alias_p): Instrument with counters.
(walk_non_aliased_vuses): Account to TV_ALIAS_STMT_WALK.
Index: alias-improvements/gcc/timevar.def
===================================================================
*** alias-improvements.orig/gcc/timevar.def 2009-01-20 09:21:37.000000000 +0100
--- alias-improvements/gcc/timevar.def 2009-02-04 15:53:54.000000000 +0100
*************** DEFTIMEVAR (TV_DF_NOTE , "df reg d
*** 69,74 ****
--- 69,75 ----
DEFTIMEVAR (TV_REG_STATS , "register information")
DEFTIMEVAR (TV_ALIAS_ANALYSIS , "alias analysis")
+ DEFTIMEVAR (TV_ALIAS_STMT_WALK , "alias stmt walking")
DEFTIMEVAR (TV_REG_SCAN , "register scan")
DEFTIMEVAR (TV_REBUILD_JUMP , "rebuild jump labels")
/* Timing in various stages of the compiler. */
Index: alias-improvements/gcc/tree-ssa-alias.c
===================================================================
*** alias-improvements.orig/gcc/tree-ssa-alias.c 2009-02-04 15:36:58.000000000 +0100
--- alias-improvements/gcc/tree-ssa-alias.c 2009-02-04 17:15:31.000000000 +0100
*************** same_type_for_tbaa (tree type1, tree typ
*** 384,389 ****
--- 384,429 ----
return 0;
}
+ #if 0
+ #define ALIAS_START
+ #define MUST_ALIAS return true
+ #define MAY_ALIAS return true
+ #define NO_ALIAS return false
+ #define ALIAS_END return true
+ #else
+ #define ALIAS_START \
+ bool ALIAS_res = true; \
+ do { \
+ statistics_counter_event (cfun, "may alias queries", 1); \
+ } while (0)
+ #define STRINGIFY1(x) # x
+ #define STRINGIFY(x) STRINGIFY1(x)
+ #define MUST_ALIAS \
+ do { \
+ statistics_counter_event (cfun, "must alias " STRINGIFY(__LINE__), 1); \
+ return true; \
+ } while (0)
+ #define MAY_ALIAS \
+ do { \
+ statistics_counter_event (cfun, "may alias " STRINGIFY(__LINE__), 1); \
+ } while (0)
+ #define NO_ALIAS \
+ do { \
+ statistics_counter_event (cfun, "no alias " STRINGIFY(__LINE__), 1); \
+ if (ALIAS_res) \
+ statistics_counter_event (cfun, "no alias 1st " STRINGIFY(__LINE__), 1); \
+ ALIAS_res = false; \
+ } while (0)
+ #define ALIAS_END \
+ do { \
+ if (ALIAS_res) \
+ statistics_counter_event (cfun, "may alias", 1); \
+ else \
+ statistics_counter_event (cfun, "no alias", 1); \
+ return ALIAS_res; \
+ } while (0)
+ #endif
+
/* Return true, if the two memory references REF1 and REF2 may alias. */
bool
*************** refs_may_alias_p (tree ref1, tree ref2)
*** 394,399 ****
--- 434,440 ----
HOST_WIDE_INT size1 = -1, size2 = -1;
HOST_WIDE_INT max_size1 = -1, max_size2 = -1;
alias_set_type base1_alias_set, base2_alias_set;
+ ALIAS_START;
gcc_assert ((SSA_VAR_P (ref1)
|| handled_component_p (ref1)
*************** refs_may_alias_p (tree ref1, tree ref2)
*** 407,413 ****
/* Defer to TBAA if possible. */
if (flag_strict_aliasing
&& !alias_sets_conflict_p (get_alias_set (ref1), get_alias_set (ref2)))
! return false;
/* Decompose the references into their base objects and the access. */
base1 = get_ref_base_and_extent (ref1, &offset1, &size1, &max_size1);
--- 448,454 ----
/* Defer to TBAA if possible. */
if (flag_strict_aliasing
&& !alias_sets_conflict_p (get_alias_set (ref1), get_alias_set (ref2)))
! NO_ALIAS;
/* Decompose the references into their base objects and the access. */
base1 = get_ref_base_and_extent (ref1, &offset1, &size1, &max_size1);
*************** refs_may_alias_p (tree ref1, tree ref2)
*** 429,436 ****
&& SSA_VAR_P (base2))
{
if (!operand_equal_p (base1, base2, 0))
! return false;
! return ranges_overlap_p (offset1, max_size1, offset2, max_size2);
}
/* If only one reference is based on a variable, they cannot alias if
--- 470,480 ----
&& SSA_VAR_P (base2))
{
if (!operand_equal_p (base1, base2, 0))
! NO_ALIAS;
! if (ranges_overlap_p (offset1, max_size1, offset2, max_size2))
! MAY_ALIAS;
! else
! NO_ALIAS;
}
/* If only one reference is based on a variable, they cannot alias if
*************** refs_may_alias_p (tree ref1, tree ref2)
*** 443,460 ****
{
if (max_size1 != -1
&& !ranges_overlap_p (0, offset1 + max_size1, offset2, max_size2))
! return false;
if (!may_point_to_decl (TREE_OPERAND (base2, 0), base1))
! return false;
}
else if (SSA_VAR_P (base2)
&& INDIRECT_REF_P (base1))
{
if (max_size2 != -1
&& !ranges_overlap_p (offset1, max_size1, 0, offset2 + max_size2))
! return false;
if (!may_point_to_decl (TREE_OPERAND (base1, 0), base2))
! return false;
}
/* If both bases are based on pointers they cannot alias if they may not
--- 487,504 ----
{
if (max_size1 != -1
&& !ranges_overlap_p (0, offset1 + max_size1, offset2, max_size2))
! NO_ALIAS;
if (!may_point_to_decl (TREE_OPERAND (base2, 0), base1))
! NO_ALIAS;
}
else if (SSA_VAR_P (base2)
&& INDIRECT_REF_P (base1))
{
if (max_size2 != -1
&& !ranges_overlap_p (offset1, max_size1, 0, offset2 + max_size2))
! NO_ALIAS;
if (!may_point_to_decl (TREE_OPERAND (base1, 0), base2))
! NO_ALIAS;
}
/* If both bases are based on pointers they cannot alias if they may not
*************** refs_may_alias_p (tree ref1, tree ref2)
*** 465,501 ****
{
if (operand_equal_p (TREE_OPERAND (base1, 0),
TREE_OPERAND (base2, 0), 0))
! return ranges_overlap_p (offset1, max_size1, offset2, max_size2);
if (!may_point_to_same_object (TREE_OPERAND (base1, 0),
TREE_OPERAND (base2, 0)))
! return false;
}
/* Disambiguations that rely on strict aliasing rules follow. */
if (!flag_strict_aliasing)
! return true;
/* If one base is a TARGET_MEM_REF weird things are allowed. */
if (TREE_CODE (base1) == TARGET_MEM_REF
|| TREE_CODE (base2) == TARGET_MEM_REF)
! return true;
/* If the alias set for a pointer access is zero all bets are off. */
base1_alias_set = get_alias_set (base1);
if (INDIRECT_REF_P (base1)
&& base1_alias_set == 0)
! return true;
base2_alias_set = get_alias_set (base2);
if (INDIRECT_REF_P (base2)
&& base2_alias_set == 0)
! return true;
/* If both references are through the same type, they do not alias
if the accesses do not overlap. This does extra disambiguation
for mixed/pointer accesses but requires strict aliasing. */
if (same_type_for_tbaa (TREE_TYPE (base1), TREE_TYPE (base2)) == 1)
! return ranges_overlap_p (offset1, max_size1, offset2, max_size2);
/* The only way to access a variable is through a pointer dereference
of the same alias set or a subset of it. */
--- 509,557 ----
{
if (operand_equal_p (TREE_OPERAND (base1, 0),
TREE_OPERAND (base2, 0), 0))
! {
! if (ranges_overlap_p (offset1, max_size1, offset2, max_size2))
! MAY_ALIAS;
! else
! NO_ALIAS;
! }
if (!may_point_to_same_object (TREE_OPERAND (base1, 0),
TREE_OPERAND (base2, 0)))
! NO_ALIAS;
! else
! MAY_ALIAS;
}
/* Disambiguations that rely on strict aliasing rules follow. */
if (!flag_strict_aliasing)
! MUST_ALIAS;
/* If one base is a TARGET_MEM_REF weird things are allowed. */
if (TREE_CODE (base1) == TARGET_MEM_REF
|| TREE_CODE (base2) == TARGET_MEM_REF)
! MUST_ALIAS;
/* If the alias set for a pointer access is zero all bets are off. */
base1_alias_set = get_alias_set (base1);
if (INDIRECT_REF_P (base1)
&& base1_alias_set == 0)
! MUST_ALIAS;
base2_alias_set = get_alias_set (base2);
if (INDIRECT_REF_P (base2)
&& base2_alias_set == 0)
! MUST_ALIAS;
/* If both references are through the same type, they do not alias
if the accesses do not overlap. This does extra disambiguation
for mixed/pointer accesses but requires strict aliasing. */
if (same_type_for_tbaa (TREE_TYPE (base1), TREE_TYPE (base2)) == 1)
! {
! if (ranges_overlap_p (offset1, max_size1, offset2, max_size2))
! MAY_ALIAS;
! else
! NO_ALIAS;
! }
/* The only way to access a variable is through a pointer dereference
of the same alias set or a subset of it. */
*************** refs_may_alias_p (tree ref1, tree ref2)
*** 506,517 ****
|| (SSA_VAR_P (base2)
&& INDIRECT_REF_P (base1)
&& !alias_set_subset_of (base1_alias_set, base2_alias_set))))
! return false;
/* If the base objects do not conflict, references based on them
cannot either. */
if (!alias_sets_conflict_p (base1_alias_set, base2_alias_set))
! return false;
/* If one reference is a component references through pointers try to find a
common base and apply offset based disambiguation. This handles
--- 562,573 ----
|| (SSA_VAR_P (base2)
&& INDIRECT_REF_P (base1)
&& !alias_set_subset_of (base1_alias_set, base2_alias_set))))
! NO_ALIAS;
/* If the base objects do not conflict, references based on them
cannot either. */
if (!alias_sets_conflict_p (base1_alias_set, base2_alias_set))
! NO_ALIAS;
/* If one reference is a component references through pointers try to find a
common base and apply offset based disambiguation. This handles
*************** refs_may_alias_p (tree ref1, tree ref2)
*** 537,549 ****
same_p = same_type_for_tbaa (TREE_TYPE (*refp), TREE_TYPE (base1));
/* If we couldn't compare types we have to bail out. */
if (same_p == -1)
! return true;
else if (same_p == 1)
{
HOST_WIDE_INT offadj, sztmp, msztmp;
get_ref_base_and_extent (*refp, &offadj, &sztmp, &msztmp);
offset2 -= offadj;
! return ranges_overlap_p (offset1, max_size1, offset2, max_size2);
}
/* If we didn't find a common base, try the other way around. */
refp = &TREE_OPERAND (ref1, 0);
--- 593,608 ----
same_p = same_type_for_tbaa (TREE_TYPE (*refp), TREE_TYPE (base1));
/* If we couldn't compare types we have to bail out. */
if (same_p == -1)
! MAY_ALIAS;
else if (same_p == 1)
{
HOST_WIDE_INT offadj, sztmp, msztmp;
get_ref_base_and_extent (*refp, &offadj, &sztmp, &msztmp);
offset2 -= offadj;
! if (ranges_overlap_p (offset1, max_size1, offset2, max_size2))
! MAY_ALIAS;
! else
! NO_ALIAS;
}
/* If we didn't find a common base, try the other way around. */
refp = &TREE_OPERAND (ref1, 0);
*************** refs_may_alias_p (tree ref1, tree ref2)
*** 554,575 ****
same_p = same_type_for_tbaa (TREE_TYPE (*refp), TREE_TYPE (base2));
/* If we couldn't compare types we have to bail out. */
if (same_p == -1)
! return true;
else if (same_p == 1)
{
HOST_WIDE_INT offadj, sztmp, msztmp;
get_ref_base_and_extent (*refp, &offadj, &sztmp, &msztmp);
offset1 -= offadj;
! return ranges_overlap_p (offset1, max_size1, offset2, max_size2);
}
/* If we have two type access paths B1.path1 and B2.path2 they may
only alias if either B1 is in B2.path2 or B2 is in B1.path1. */
! return false;
}
! return true;
}
/* If the call CALL may use the memory reference REF return true,
otherwise return false. */
--- 613,645 ----
same_p = same_type_for_tbaa (TREE_TYPE (*refp), TREE_TYPE (base2));
/* If we couldn't compare types we have to bail out. */
if (same_p == -1)
! MAY_ALIAS;
else if (same_p == 1)
{
HOST_WIDE_INT offadj, sztmp, msztmp;
get_ref_base_and_extent (*refp, &offadj, &sztmp, &msztmp);
offset1 -= offadj;
! if (ranges_overlap_p (offset1, max_size1, offset2, max_size2))
! MAY_ALIAS;
! else
! NO_ALIAS;
}
/* If we have two type access paths B1.path1 and B2.path2 they may
only alias if either B1 is in B2.path2 or B2 is in B1.path1. */
! NO_ALIAS;
}
! ALIAS_END;
}
+ #undef ALIAS_START
+ #undef MUST_ALIAS
+ #undef MAY_ALIAS
+ #undef NO_ALIAS
+ #undef ALIAS_END
+ #undef STRINGIFY
+ #undef STRINGIFY1
+
/* If the call CALL may use the memory reference REF return true,
otherwise return false. */
*************** walk_non_aliased_vuses (tree ref, tree v
*** 825,834 ****
--- 895,907 ----
bitmap visited = NULL;
void *res;
+ timevar_push (TV_ALIAS_STMT_WALK);
+
do
{
gimple def_stmt;
+ /* ??? Do we want to account this to TV_ALIAS_STMT_WALK? */
res = (*walker) (ref, vuse, data);
if (res)
break;
*************** walk_non_aliased_vuses (tree ref, tree v
*** 850,854 ****
--- 923,929 ----
if (visited)
BITMAP_FREE (visited);
+ timevar_pop (TV_ALIAS_STMT_WALK);
+
return res;
}
More information about the Gcc-patches
mailing list