This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [PATCH] Speed up genattrtab
Hello,
> > this patch speeds up genattrtab significantly. All timings are done
> > on i686 (and config/i386/i386.md, of course).
> >
> > 1) Genattrtab spends most of its time simplifying complicated logical
> > expressions. The greatest bulk of them are just used to express
> > sets of alternatives. By adding a special representation of them
> > (EQ_ATTR_ALT), genattrtab becomes about 3 times faster! (from 103
> > seconds to 36).
> >
> > I have tested that I maintain correctness and efficiency
> > -- insn-attrtab.c is of course different, since sometimes we
> > optimize out things that were not optimized and vice versa,
> > and we do checks for membership into a set by checking
> > (1 << which_alternative) & set), but the changes I have
> > investigated are equivalent
> > -- the produced programs are identical
> > -- the compilation time is unchanged
> >
> > 2) I have also modified a few functions so that all strings are always
> > replaced by canonical copies, so that string equality can be verified
> > just by comparing pointers. This improves speed by another ~2% (to
> > 35 seconds).
> >
> > Bootstrapped and tested on i686.
>
> ...
> > + newexp = mk_attr_alt (1 << atoi (XSTR (exp, 1)));
>
> I don't see the part of the patch that checks whether this can
> overflow. In particular, rs6000 has 53 possible insn type attributes,
> and you're using 'int'.
>
> Could you split the second part out into a separate patch?
here is the first part (sets of alternatives) separated. I am working on the
second one.
Zdenek
Index: genattrtab.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/genattrtab.c,v
retrieving revision 1.136
diff -c -3 -p -r1.136 genattrtab.c
*** genattrtab.c 22 Aug 2003 06:45:14 -0000 1.136
--- genattrtab.c 23 Nov 2003 20:25:46 -0000
*************** static const char *attr_numeral (int);
*** 459,464 ****
--- 459,471 ----
static int attr_equal_p (rtx, rtx);
static rtx attr_copy_rtx (rtx);
static int attr_rtx_cost (rtx);
+ static bool attr_alt_subset_p (rtx, rtx);
+ static bool attr_alt_subset_of_compl_p (rtx, rtx);
+ static rtx attr_alt_intersection (rtx, rtx);
+ static rtx attr_alt_union (rtx, rtx);
+ static rtx attr_alt_complement (rtx);
+ static bool attr_alt_bit_p (rtx, int);
+ static rtx mk_attr_alt (int);
#define oballoc(size) obstack_alloc (hash_obstack, size)
*************** check_attr_test (rtx exp, int is_const,
*** 920,931 ****
if (attr == NULL)
{
if (! strcmp (XSTR (exp, 0), "alternative"))
! {
! XSTR (exp, 0) = alternative_name;
! /* This can't be simplified any further. */
! ATTR_IND_SIMPLIFIED_P (exp) = 1;
! return exp;
! }
else
fatal ("unknown attribute `%s' in EQ_ATTR", XSTR (exp, 0));
}
--- 927,933 ----
if (attr == NULL)
{
if (! strcmp (XSTR (exp, 0), "alternative"))
! return mk_attr_alt (1 << atoi (XSTR (exp, 1)));
else
fatal ("unknown attribute `%s' in EQ_ATTR", XSTR (exp, 0));
}
*************** check_attr_test (rtx exp, int is_const,
*** 965,980 ****
}
else
{
! /* Make an IOR tree of the possible values. */
! orexp = false_rtx;
! name_ptr = XSTR (exp, 1);
! while ((p = next_comma_elt (&name_ptr)) != NULL)
{
! newexp = attr_eq (XSTR (exp, 0), p);
! orexp = insert_right_side (IOR, orexp, newexp, -2, -2);
}
! return check_attr_test (orexp, is_const, lineno);
}
break;
--- 967,995 ----
}
else
{
! if (! strcmp (XSTR (exp, 0), "alternative"))
{
! int set = 0;
!
! name_ptr = XSTR (exp, 1);
! while ((p = next_comma_elt (&name_ptr)) != NULL)
! set |= 1 << atoi (p);
!
! return mk_attr_alt (set);
}
+ else
+ {
+ /* Make an IOR tree of the possible values. */
+ orexp = false_rtx;
+ name_ptr = XSTR (exp, 1);
+ while ((p = next_comma_elt (&name_ptr)) != NULL)
+ {
+ newexp = attr_eq (XSTR (exp, 0), p);
+ orexp = insert_right_side (IOR, orexp, newexp, -2, -2);
+ }
! return check_attr_test (orexp, is_const, lineno);
! }
}
break;
*************** encode_units_mask (rtx x)
*** 2186,2191 ****
--- 2201,2207 ----
case PC:
case CC0:
case EQ_ATTR:
+ case EQ_ATTR_ALT:
return x;
default:
*************** simplify_cond (rtx exp, int insn_code, i
*** 2496,2501 ****
--- 2512,2518 ----
/* If test is false, discard it and its value. */
for (j = i; j < len - 2; j++)
tests[j] = tests[j + 2];
+ i -= 2;
len -= 2;
}
*************** simplify_cond (rtx exp, int insn_code, i
*** 2512,2517 ****
--- 2529,2535 ----
for (j = i; j < len - 2; j++)
tests[j] = tests[j + 2];
len -= 2;
+ i -= 2;
}
else
*************** compute_alternative_mask (rtx exp, enum
*** 2682,2687 ****
--- 2700,2715 ----
&& XSTR (exp, 0) == alternative_name)
string = XSTR (exp, 1);
+ else if (GET_CODE (exp) == EQ_ATTR_ALT)
+ {
+ if (code == AND && XINT (exp, 1))
+ return XINT (exp, 0);
+
+ if (code == IOR && !XINT (exp, 1))
+ return XINT (exp, 0);
+
+ return 0;
+ }
else
return 0;
*************** compute_alternative_mask (rtx exp, enum
*** 2696,2712 ****
static rtx
make_alternative_compare (int mask)
{
! rtx newexp;
! int i;
!
! /* Find the bit. */
! for (i = 0; (mask & (1 << i)) == 0; i++)
! ;
!
! newexp = attr_rtx (EQ_ATTR, alternative_name, attr_numeral (i));
! ATTR_IND_SIMPLIFIED_P (newexp) = 1;
!
! return newexp;
}
/* If we are processing an (eq_attr "attr" "value") test, we find the value
--- 2724,2730 ----
static rtx
make_alternative_compare (int mask)
{
! return mk_attr_alt (mask);
}
/* If we are processing an (eq_attr "attr" "value") test, we find the value
*************** simplify_and_tree (rtx exp, rtx *pterm,
*** 2853,2859 ****
right = simplify_and_tree (XEXP (exp, 1), pterm, insn_code, insn_index);
if (left != XEXP (exp, 0) || right != XEXP (exp, 1))
{
! newexp = attr_rtx (GET_CODE (exp), left, right);
exp = simplify_test_exp_in_temp (newexp, insn_code, insn_index);
}
--- 2871,2877 ----
right = simplify_and_tree (XEXP (exp, 1), pterm, insn_code, insn_index);
if (left != XEXP (exp, 0) || right != XEXP (exp, 1))
{
! newexp = attr_rtx (AND, left, right);
exp = simplify_test_exp_in_temp (newexp, insn_code, insn_index);
}
*************** simplify_and_tree (rtx exp, rtx *pterm,
*** 2876,2882 ****
if (left != XEXP (exp, 0) || right != XEXP (exp, 1))
{
! newexp = attr_rtx (GET_CODE (exp), left, right);
exp = simplify_test_exp_in_temp (newexp, insn_code, insn_index);
}
--- 2894,2900 ----
if (left != XEXP (exp, 0) || right != XEXP (exp, 1))
{
! newexp = attr_rtx (IOR, left, right);
exp = simplify_test_exp_in_temp (newexp, insn_code, insn_index);
}
*************** simplify_and_tree (rtx exp, rtx *pterm,
*** 2894,2899 ****
--- 2912,2931 ----
else if (GET_CODE (*pterm) == NOT && exp == XEXP (*pterm, 0))
return false_rtx;
+ else if (GET_CODE (exp) == EQ_ATTR_ALT && GET_CODE (*pterm) == EQ_ATTR_ALT)
+ {
+ if (attr_alt_subset_p (*pterm, exp))
+ return true_rtx;
+
+ if (attr_alt_subset_of_compl_p (*pterm, exp))
+ return false_rtx;
+
+ if (attr_alt_subset_p (exp, *pterm))
+ *pterm = true_rtx;
+
+ return exp;
+ }
+
else if (GET_CODE (exp) == EQ_ATTR && GET_CODE (*pterm) == EQ_ATTR)
{
if (XSTR (exp, 0) != XSTR (*pterm, 0))
*************** attr_rtx_cost (rtx x)
*** 3037,3045 ****
return 10;
else
return 0;
case EQ_ATTR:
/* Alternatives don't result into function call. */
! if (!strcmp (XSTR (x, 0), "alternative"))
return 0;
else
return 5;
--- 3069,3080 ----
return 10;
else
return 0;
+
+ case EQ_ATTR_ALT:
+ return 0;
case EQ_ATTR:
/* Alternatives don't result into function call. */
! if (!strcmp (XSTR (x, 0), alternative_name))
return 0;
else
return 5;
*************** simplify_test_exp_in_temp (rtx exp, int
*** 3087,3092 ****
--- 3122,3267 ----
return attr_copy_rtx (x);
}
+ /* Returns true if S1 is a subset of S2. */
+
+ static bool
+ attr_alt_subset_p (rtx s1, rtx s2)
+ {
+ switch ((XINT (s1, 1) << 1) | XINT (s2, 1))
+ {
+ case (0 << 1) | 0:
+ return !(XINT (s1, 0) &~ XINT (s2, 0));
+
+ case (0 << 1) | 1:
+ return !(XINT (s1, 0) & XINT (s2, 0));
+
+ case (1 << 1) | 0:
+ return false;
+
+ case (1 << 1) | 1:
+ return !(XINT (s2, 0) &~ XINT (s1, 0));
+
+ default:
+ abort ();
+ }
+ }
+
+ /* Returns true if S1 is a subset of complement of S2. */
+
+ static bool attr_alt_subset_of_compl_p (rtx s1, rtx s2)
+ {
+ switch ((XINT (s1, 1) << 1) | XINT (s2, 1))
+ {
+ case (0 << 1) | 0:
+ return !(XINT (s1, 0) & XINT (s2, 0));
+
+ case (0 << 1) | 1:
+ return !(XINT (s1, 0) & ~XINT (s2, 0));
+
+ case (1 << 1) | 0:
+ return !(XINT (s2, 0) &~ XINT (s1, 0));
+
+ case (1 << 1) | 1:
+ return false;
+
+ default:
+ abort ();
+ }
+ }
+
+ /* Return EQ_ATTR_ALT expression representing intersection of S1 and S2. */
+
+ static rtx
+ attr_alt_intersection (rtx s1, rtx s2)
+ {
+ rtx result = rtx_alloc (EQ_ATTR_ALT);
+
+ switch ((XINT (s1, 1) << 1) | XINT (s2, 1))
+ {
+ case (0 << 1) | 0:
+ XINT (result, 0) = XINT (s1, 0) & XINT (s2, 0);
+ break;
+ case (0 << 1) | 1:
+ XINT (result, 0) = XINT (s1, 0) & ~XINT (s2, 0);
+ break;
+ case (1 << 1) | 0:
+ XINT (result, 0) = XINT (s2, 0) & ~XINT (s1, 0);
+ break;
+ case (1 << 1) | 1:
+ XINT (result, 0) = XINT (s1, 0) | XINT (s2, 0);
+ break;
+ default:
+ abort ();
+ }
+ XINT (result, 1) = XINT (s1, 1) & XINT (s2, 1);
+
+ return result;
+ }
+
+ /* Return EQ_ATTR_ALT expression representing union of S1 and S2. */
+
+ static rtx
+ attr_alt_union (rtx s1, rtx s2)
+ {
+ rtx result = rtx_alloc (EQ_ATTR_ALT);
+
+ switch ((XINT (s1, 1) << 1) | XINT (s2, 1))
+ {
+ case (0 << 1) | 0:
+ XINT (result, 0) = XINT (s1, 0) | XINT (s2, 0);
+ break;
+ case (0 << 1) | 1:
+ XINT (result, 0) = XINT (s2, 0) & ~XINT (s1, 0);
+ break;
+ case (1 << 1) | 0:
+ XINT (result, 0) = XINT (s1, 0) & ~XINT (s2, 0);
+ break;
+ case (1 << 1) | 1:
+ XINT (result, 0) = XINT (s1, 0) & XINT (s2, 0);
+ break;
+ default:
+ abort ();
+ }
+
+ XINT (result, 1) = XINT (s1, 1) | XINT (s2, 1);
+ return result;
+ }
+
+ /* Return EQ_ATTR_ALT expression representing complement of S. */
+
+ static rtx
+ attr_alt_complement (rtx s)
+ {
+ rtx result = rtx_alloc (EQ_ATTR_ALT);
+
+ XINT (result, 0) = XINT (s, 0);
+ XINT (result, 1) = 1 - XINT (s, 1);
+
+ return result;
+ }
+
+ /* Tests whether a bit B belongs to the set represented by S. */
+
+ static bool
+ attr_alt_bit_p (rtx s, int b)
+ {
+ return XINT (s, 1) ^ ((XINT (s, 0) >> b) & 1);
+ }
+
+ /* Return EQ_ATTR_ALT expression representing set containing elements set
+ in E. */
+
+ static rtx
+ mk_attr_alt (int e)
+ {
+ rtx result = rtx_alloc (EQ_ATTR_ALT);
+
+ XINT (result, 0) = e;
+ XINT (result, 1) = 0;
+
+ return result;
+ }
+
/* Given an expression, see if it can be simplified for a particular insn
code based on the values of other attributes being tested. This can
eliminate nested get_attr_... calls.
*************** simplify_test_exp (rtx exp, int insn_cod
*** 3105,3110 ****
--- 3280,3286 ----
struct insn_ent *ie;
int i;
rtx newexp = exp;
+ bool left_alt, right_alt;
/* Don't re-simplify something we already simplified. */
if (ATTR_IND_SIMPLIFIED_P (exp) || ATTR_CURR_SIMPLIFIED_P (exp))
*************** simplify_test_exp (rtx exp, int insn_cod
*** 3122,3127 ****
--- 3298,3310 ----
if (left == false_rtx)
return false_rtx;
+ if (GET_CODE (left) == EQ_ATTR_ALT
+ && GET_CODE (right) == EQ_ATTR_ALT)
+ {
+ exp = attr_alt_intersection (left, right);
+ return simplify_test_exp (exp, insn_code, insn_index);
+ }
+
/* If either side is an IOR and we have (eq_attr "alternative" ..")
present on both sides, apply the distributive law since this will
yield simplifications. */
*************** simplify_test_exp (rtx exp, int insn_cod
*** 3161,3175 ****
/* See if all or all but one of the insn's alternatives are specified
in this tree. Optimize if so. */
! else if (insn_code >= 0
! && (GET_CODE (left) == AND
! || (GET_CODE (left) == NOT
! && GET_CODE (XEXP (left, 0)) == EQ_ATTR
! && XSTR (XEXP (left, 0), 0) == alternative_name)
! || GET_CODE (right) == AND
! || (GET_CODE (right) == NOT
! && GET_CODE (XEXP (right, 0)) == EQ_ATTR
! && XSTR (XEXP (right, 0), 0) == alternative_name)))
{
i = compute_alternative_mask (exp, AND);
if (i & ~insn_alternatives[insn_code])
--- 3344,3368 ----
/* See if all or all but one of the insn's alternatives are specified
in this tree. Optimize if so. */
! if (GET_CODE (left) == NOT)
! left_alt = (GET_CODE (XEXP (left, 0)) == EQ_ATTR
! && XSTR (XEXP (left, 0), 0) == alternative_name);
! else
! left_alt = (GET_CODE (left) == EQ_ATTR_ALT
! && XINT (left, 1));
!
! if (GET_CODE (right) == NOT)
! right_alt = (GET_CODE (XEXP (right, 0)) == EQ_ATTR
! && XSTR (XEXP (right, 0), 0) == alternative_name);
! else
! right_alt = (GET_CODE (right) == EQ_ATTR_ALT
! && XINT (right, 1));
!
! if (insn_code >= 0
! && (GET_CODE (left) == AND
! || left_alt
! || GET_CODE (right) == AND
! || right_alt))
{
i = compute_alternative_mask (exp, AND);
if (i & ~insn_alternatives[insn_code])
*************** simplify_test_exp (rtx exp, int insn_cod
*** 3211,3216 ****
--- 3404,3416 ----
if (right == true_rtx)
return true_rtx;
+ if (GET_CODE (left) == EQ_ATTR_ALT
+ && GET_CODE (right) == EQ_ATTR_ALT)
+ {
+ exp = attr_alt_union (left, right);
+ return simplify_test_exp (exp, insn_code, insn_index);
+ }
+
right = simplify_or_tree (right, &left, insn_code, insn_index);
if (left == XEXP (exp, 0) && right == XEXP (exp, 1))
left = simplify_or_tree (left, &right, insn_code, insn_index);
*************** simplify_test_exp (rtx exp, int insn_cod
*** 3249,3257 ****
--- 3449,3461 ----
else if (insn_code >= 0
&& (GET_CODE (left) == IOR
+ || (GET_CODE (left) == EQ_ATTR_ALT
+ && !XINT (left, 1))
|| (GET_CODE (left) == EQ_ATTR
&& XSTR (left, 0) == alternative_name)
|| GET_CODE (right) == IOR
+ || (GET_CODE (right) == EQ_ATTR_ALT
+ && !XINT (right, 1))
|| (GET_CODE (right) == EQ_ATTR
&& XSTR (right, 0) == alternative_name)))
{
*************** simplify_test_exp (rtx exp, int insn_cod
*** 3301,3311 ****
if (left == false_rtx)
return true_rtx;
! else if (left == true_rtx)
return false_rtx;
/* Try to apply De`Morgan's laws. */
! else if (GET_CODE (left) == IOR)
{
newexp = attr_rtx (AND,
attr_rtx (NOT, XEXP (left, 0)),
--- 3505,3521 ----
if (left == false_rtx)
return true_rtx;
! if (left == true_rtx)
return false_rtx;
+ if (GET_CODE (left) == EQ_ATTR_ALT)
+ {
+ exp = attr_alt_complement (left);
+ return simplify_test_exp (exp, insn_code, insn_index);
+ }
+
/* Try to apply De`Morgan's laws. */
! if (GET_CODE (left) == IOR)
{
newexp = attr_rtx (AND,
attr_rtx (NOT, XEXP (left, 0)),
*************** simplify_test_exp (rtx exp, int insn_cod
*** 3327,3337 ****
--- 3537,3561 ----
}
break;
+ case EQ_ATTR_ALT:
+ if (current_alternative_string)
+ return attr_alt_bit_p (exp, atoi (current_alternative_string)) ? true_rtx : false_rtx;
+
+ if (!XINT (exp, 0))
+ return XINT (exp, 1) ? true_rtx : false_rtx;
+ break;
+
case EQ_ATTR:
if (current_alternative_string && XSTR (exp, 0) == alternative_name)
return (XSTR (exp, 1) == current_alternative_string
? true_rtx : false_rtx);
+ if (XSTR (exp, 0) == alternative_name)
+ {
+ newexp = mk_attr_alt (1 << atoi (XSTR (exp, 1)));
+ break;
+ }
+
/* Look at the value for this insn code in the specified attribute.
We normally can replace this comparison with the condition that
would give this insn the values being tested for. */
*************** write_test_expr (rtx exp, int flags)
*** 4490,4495 ****
--- 4714,4765 ----
write_test_expr (XEXP (exp, 0), flags);
break;
+ case EQ_ATTR_ALT:
+ {
+ int set = XINT (exp, 0), bit = 0;
+
+ if (flags & 1)
+ fatal ("EQ_ATTR_ALT not valid inside comparison");
+
+ if (!set)
+ fatal ("Empty EQ_ATTR_ALT should be optimized out");
+
+ if (!(set & (set - 1)))
+ {
+ if (!(set & 0xffff))
+ {
+ bit += 16;
+ set >>= 16;
+ }
+ if (!(set & 0xff))
+ {
+ bit += 8;
+ set >>= 8;
+ }
+ if (!(set & 0xf))
+ {
+ bit += 4;
+ set >>= 4;
+ }
+ if (!(set & 0x3))
+ {
+ bit += 2;
+ set >>= 2;
+ }
+ if (!(set & 1))
+ bit++;
+
+ printf ("which_alternative %s= %d",
+ XINT (exp, 1) ? "!" : "=", bit);
+ }
+ else
+ {
+ printf ("%s((1 << which_alternative) & 0x%x)",
+ XINT (exp, 1) ? "!" : "", set);
+ }
+ }
+ break;
+
/* Comparison test of an attribute with a value. Most of these will
have been removed by optimization. Handle "alternative"
specially and give error if EQ_ATTR present inside a comparison. */
*************** walk_attr_value (rtx exp)
*** 4709,4714 ****
--- 4979,4988 ----
case MATCH_OPERAND:
must_extract = 1;
return;
+
+ case EQ_ATTR_ALT:
+ must_extract = must_constrain = 1;
+ break;
case EQ_ATTR:
if (XSTR (exp, 0) == alternative_name)
Index: rtl.def
===================================================================
RCS file: /cvs/gcc/gcc/gcc/rtl.def,v
retrieving revision 1.73
diff -c -3 -p -r1.73 rtl.def
*** rtl.def 18 Oct 2003 18:45:15 -0000 1.73
--- rtl.def 23 Nov 2003 20:25:46 -0000
*************** DEF_RTL_EXPR(SET_ATTR_ALTERNATIVE, "set_
*** 582,587 ****
--- 582,591 ----
attribute name and the second is the comparison value. */
DEF_RTL_EXPR(EQ_ATTR, "eq_attr", "ss", 'x')
+ /* A special case of the above representing a set of alternatives. The first
+ operand is bitmap of the set, the second one is the default value. */
+ DEF_RTL_EXPR(EQ_ATTR_ALT, "eq_attr_alt", "ii", 'x')
+
/* A conditional expression which is true if the specified flag is
true for the insn being scheduled in reorg.