> (A << B) eq/ne 0
Yes that is correct. But for detecting such pattern you You have to detect B
and make sure B is boolean. GIMPLE transfers that Boolean to integer before
shifting.
After many hours of debugging, I think I managed to find out what is going on.
+/* cmp : ==, != */
+/* ((B0 << x) cmp 0) -> B0 cmp 0 */
+(for cmp (eq ne)
+ (simplify
+ (cmp (lshift (convert@3 boolean_valued_p@0) @1) integer_zerop@2)
+ (if (TREE_CODE (TREE_TYPE (@3)) == INTEGER_TYPE
+ && (GIMPLE || !TREE_SIDE_EFFECTS (@1)))
+(cmp @0 @2
So when I am transforming something like above pattern to (cmp @0 @2) there is
a type mismatch between @0 and @2.
@0 is boolean and @2 is integer. That type mismatch does cause a lot of
headache when going through resimplification.
Best wishes,
Navid.
From: Jeff Law
Sent: Wednesday, November 24, 2021 15:11
To: Navid Rahimi; gcc@gcc.gnu.org
Subject: [EXTERNAL] Re: Question about match.pd
On 11/24/2021 2:19 PM, Navid Rahimi via Gcc wrote:
> Hi GCC community,
>
> I have a question about pattern matching in match.pd.
>
> So I have a pattern like this [1]:
> #define CMP !=
> bool f(bool c, int i) { return (c << i) CMP 0; }
> bool g(bool c, int i) { return c CMP 0;}
>
> It is verifiably correct to transfer f to g [2]. Although this pattern looks
> simple, but the problem rises because GIMPLE converts booleans to int before
> "<<" operation.
> So at the end you have boolean->integer->boolean conversion and the shift
> will happen on the integer in the middle.
>
> For example, for something like:
>
> bool g(bool c){return (c << 22);}
>
> The GIMPLE is:
> _Bool g (_Bool c)
> {
>int _1;
>int _2;
>_Bool _4;
>
> [local count: 1073741824]:
>_1 = (int) c_3(D);
>_2 = _1 << 22;
>_4 = _2 != 0;
>return _4;
> }
>
> I wrote a patch to fix this problem in match.pd:
>
> +(match boolean_valued_p
> + @0
> + (if (TREE_CODE (type) == BOOLEAN_TYPE
> + && TYPE_PRECISION (type) == 1)))
> +(for op (tcc_comparison truth_and truth_andif truth_or truth_orif truth_xor)
> + (match boolean_valued_p
> + (op @0 @1)))
> +(match boolean_valued_p
> + (truth_not @0))
>
> +/* cmp : ==, != */
> +/* ((B0 << x) cmp 0) -> B0 cmp 0 */
> +(for cmp (eq ne)
> + (simplify
> + (cmp (lshift (convert@3 boolean_valued_p@0) @1) integer_zerop@2)
> + (if (TREE_CODE (TREE_TYPE (@3)) == INTEGER_TYPE
> + && (GIMPLE || !TREE_SIDE_EFFECTS (@1)))
> +(cmp @0 @2
>
>
> But the problem is I am not able to restrict to the cases I am interested in.
> There are many hits in other libraries I have tried compiling with
> trunk+patch.
>
> Any feedback?
>
> 1)
> https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgcc.gnu.org%2Fbugzilla%2Fshow_bug.cgi%3Fid%3D98956&data=04%7C01%7Cnavidrahimi%40microsoft.com%7Caa8c9c8213a245c7ae9d08d9af9fc8ae%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637733923073627850%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=25KlLcsftTmN83rVawoKKaTPJdCdFlmtXMj%2BwsrKWbo%3D&reserved=0
> 2)
> https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Falive2.llvm.org%2Fce%2Fz%2FUUTJ_v&data=04%7C01%7Cnavidrahimi%40microsoft.com%7Caa8c9c8213a245c7ae9d08d9af9fc8ae%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637733923073637846%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=fwN9%2BB0VObPyuUS2fOtj14i%2BHJIiRhyyjZM4LOF4AP8%3D&reserved=0
It would help to also see the cases you're triggering that you do not
want to trigger.
Could we think of the optimization opportunity in a different way?
(A << B) eq/ne 0 -> A eq/ne (0U >> B)
And I would expect the 0U >> B to get simplified to 0.
Would looking at things that way help?
jeff
