https://gcc.gnu.org/bugzilla/show_bug.cgi?id=122569
Bug ID: 122569
Summary: Fails to pattern match ctz/clz from DeBruijn
Product: gcc
Version: unknown
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: tree-optimization
Assignee: unassigned at gcc dot gnu.org
Reporter: fxue at os dot amperecomputing.com
Target Milestone: ---
Some Debruijin clz/ctz patterns can not be recognized.
1. Variant of Pr120031, Debruijin mapping array is of long integer type.
{
static const unsigned long DeBruijnBytePos[32] = {0, 1, 28, 2, 29, 14, 24, 3,
30, 22, 20, 15, 25, 17, 4, 8,
31, 27, 13, 23, 21, 19, 16, 7,
26, 12, 18, 6, 11, 5, 10, 9};
return DeBruijnBytePos[((unsigned int) ((val & -(int) val) * 0x077CB531U)) >>
27];
}
2. Variant of PR120032, if absorbing 31 substract constant into the array,
pattern match fails.
{
static const unsigned int DeBruijnClz[32] = {31, 22, 30, 21, 18, 10, 29, 2,
20, 17, 15, 13, 9, 6, 28, 1,
23, 19, 11, 3, 16, 14, 7, 24,
12, 4, 8, 25, 5, 26, 27, 0};
val |= val >> 1;
val |= val >> 2;
val |= val >> 4;
val |= val >> 8;
val |= val >> 16;
return DeBruijnClz[(val * 0x07C4ACDDU) >> 27];
}
3. Variant of PR120032, use a value who has same LSB as "val" (other bits are
zero) via expression (val - (val >> 1)), pattern match fails.
{
static const unsigned int DeBruijnClz[32] = {0, 1, 10, 2, 11, 14, 22, 3,
30, 12, 15, 17, 19, 23, 26, 4,
31, 9, 13, 21, 29, 16, 18, 25,
8, 20, 28, 24, 7, 27, 6, 5};
val |= val >> 1;
val |= val >> 2;
val |= val >> 4;
val |= val >> 8;
val |= val >> 16;
return 31 - DeBruijnClz[((val - (val >> 1)) * 0x07C4ACDDU) >> 27];
}
