The following patch avoids the cubic search for equal types by
collecting candidates and sorting them. The length() == 2
qsort optimization probably belongs to vec.h and additionally
we can avoid sorting the other vector if one has length() == 1.
Bootstrapped and tested on x86_64-unknown-linux-gnu, queued
for stage1.
Quick statistics show that for insn-recog we always have 1 - 1
compares (nonoverlapping_component_refs_p was crippled quite a bit
when we stopped stripping outermost non-COMPONENT_REF trees from
MEM_EXPRs). On this testcase the patch slows down the compiler
consistently by about 1% (but it's called 46 million times as part of
RTL PRE) - it seems we don't inline the fast path of
vec<tree_node const*, va_heap, vl_ptr>::safe_push(tree_node const*
const&) on auto_vec<>s with a constant initial size.
Eventually this function should move to the tree oracle and should
be made less restrictive as to what input it accepts. The following
is a patch that shouldn't change behavior in any ways.
Richard.
2014-02-12 Richard Biener <rguent...@suse.de>
* alias.c (ncr_compar): New function.
(nonoverlapping_component_refs_p): Re-implement in O (n log n).
Index: gcc/alias.c
===================================================================
*** gcc/alias.c (revision 207655)
--- gcc/alias.c (working copy)
*************** read_dependence (const_rtx mem, const_rt
*** 2259,2264 ****
--- 2261,2285 ----
return false;
}
+ /* qsort compare function to sort FIELD_DECLs after their
+ DECL_FIELD_CONTEXT TYPE_UID. */
+
+ static inline int
+ ncr_compar (const void *field1_, const void *field2_)
+ {
+ const_tree field1 = *(const_tree *) const_cast <void *>(field1_);
+ const_tree field2 = *(const_tree *) const_cast <void *>(field2_);
+ unsigned int uid1
+ = TYPE_UID (TYPE_MAIN_VARIANT (DECL_FIELD_CONTEXT (field1)));
+ unsigned int uid2
+ = TYPE_UID (TYPE_MAIN_VARIANT (DECL_FIELD_CONTEXT (field2)));
+ if (uid1 < uid2)
+ return -1;
+ else if (uid1 > uid2)
+ return 1;
+ return 0;
+ }
+
/* Return true if we can determine that the fields referenced cannot
overlap for any pair of objects. */
*************** static bool
*** 2266,2272 ****
nonoverlapping_component_refs_p (const_rtx rtlx, const_rtx rtly)
{
const_tree x = MEM_EXPR (rtlx), y = MEM_EXPR (rtly);
- const_tree fieldx, fieldy, typex, typey, orig_y;
if (!flag_strict_aliasing
|| !x || !y
--- 2287,2292 ----
*************** nonoverlapping_component_refs_p (const_r
*** 2274,2322 ****
|| TREE_CODE (y) != COMPONENT_REF)
return false;
! do
{
! /* The comparison has to be done at a common type, since we don't
! know how the inheritance hierarchy works. */
! orig_y = y;
! do
! {
! fieldx = TREE_OPERAND (x, 1);
! typex = TYPE_MAIN_VARIANT (DECL_FIELD_CONTEXT (fieldx));
!
! y = orig_y;
! do
! {
! fieldy = TREE_OPERAND (y, 1);
! typey = TYPE_MAIN_VARIANT (DECL_FIELD_CONTEXT (fieldy));
!
! if (typex == typey)
! goto found;
!
! y = TREE_OPERAND (y, 0);
! }
! while (y && TREE_CODE (y) == COMPONENT_REF);
! x = TREE_OPERAND (x, 0);
}
! while (x && TREE_CODE (x) == COMPONENT_REF);
! /* Never found a common type. */
! return false;
! found:
! /* If we're left with accessing different fields of a structure, then no
! possible overlap, unless they are both bitfields. */
! if (TREE_CODE (typex) == RECORD_TYPE && fieldx != fieldy)
! return !(DECL_BIT_FIELD (fieldx) && DECL_BIT_FIELD (fieldy));
! /* The comparison on the current field failed. If we're accessing
! a very nested structure, look at the next outer level. */
! x = TREE_OPERAND (x, 0);
! y = TREE_OPERAND (y, 0);
}
! while (x && y
! && TREE_CODE (x) == COMPONENT_REF
! && TREE_CODE (y) == COMPONENT_REF);
return false;
}
--- 2294,2382 ----
|| TREE_CODE (y) != COMPONENT_REF)
return false;
! auto_vec<const_tree, 16> fieldsx;
! while (TREE_CODE (x) == COMPONENT_REF)
{
! tree field = TREE_OPERAND (x, 1);
! tree type = TYPE_MAIN_VARIANT (DECL_FIELD_CONTEXT (field));
! if (TREE_CODE (type) == RECORD_TYPE)
! fieldsx.safe_push (field);
! x = TREE_OPERAND (x, 0);
! }
! if (fieldsx.length () == 0)
! return false;
! auto_vec<const_tree, 16> fieldsy;
! while (TREE_CODE (y) == COMPONENT_REF)
! {
! tree field = TREE_OPERAND (y, 1);
! tree type = TYPE_MAIN_VARIANT (DECL_FIELD_CONTEXT (field));
! if (TREE_CODE (type) == RECORD_TYPE)
! fieldsy.safe_push (TREE_OPERAND (y, 1));
! y = TREE_OPERAND (y, 0);
! }
! if (fieldsy.length () == 0)
! return false;
! /* Most common case first. */
! if (fieldsx.length () == 1
! && fieldsy.length () == 1)
! return ((TYPE_MAIN_VARIANT (DECL_FIELD_CONTEXT (fieldsx[0]))
! == TYPE_MAIN_VARIANT (DECL_FIELD_CONTEXT (fieldsy[0])))
! && fieldsx[0] != fieldsy[0]
! && !(DECL_BIT_FIELD (fieldsx[0]) && DECL_BIT_FIELD (fieldsy[0])));
!
! if (fieldsx.length () == 2)
! {
! if (ncr_compar (&fieldsx[0], &fieldsx[1]) == 1)
! {
! const_tree tem = fieldsx[0];
! fieldsx[0] = fieldsx[1];
! fieldsx[1] = tem;
}
! }
! else
! fieldsx.qsort (ncr_compar);
! if (fieldsy.length () == 2)
! {
! if (ncr_compar (&fieldsy[0], &fieldsy[1]) == 1)
! {
! const_tree tem = fieldsy[0];
! fieldsy[0] = fieldsy[1];
! fieldsy[1] = tem;
! }
! }
! else
! fieldsy.qsort (ncr_compar);
! unsigned i = 0, j = 0;
! do
! {
! const_tree fieldx = fieldsx[i];
! const_tree fieldy = fieldsy[j];
! tree typex = TYPE_MAIN_VARIANT (DECL_FIELD_CONTEXT (fieldx));
! tree typey = TYPE_MAIN_VARIANT (DECL_FIELD_CONTEXT (fieldy));
! if (typex == typey)
! {
! /* We're left with accessing different fields of a structure,
! no possible overlap, unless they are both bitfields. */
! if (fieldx != fieldy)
! return !(DECL_BIT_FIELD (fieldx) && DECL_BIT_FIELD (fieldy));
! }
! if (TYPE_UID (typex) < TYPE_UID (typey))
! {
! i++;
! if (i == fieldsx.length ())
! break;
! }
! else
! {
! j++;
! if (j == fieldsy.length ())
! break;
! }
}
! while (1);
return false;
}
