Question about match.pd

Question about match.pd

[Navid Rahimi]

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;

  <bb 2> [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://gcc.gnu.org/bugzilla/show_bug.cgi?id=98956
2) https://alive2.llvm.org/ce/z/UUTJ_v

Best wishes,
Navid.

Re: Question about match.pd

[Jeff Law]

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;
>
>    <bb 2> [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://gcc.gnu.org/bugzilla/show_bug.cgi?id=98956
> 2) https://alive2.llvm.org/ce/z/UUTJ_v
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

Re: [EXTERNAL] Re: Question about match.pd

[Navid Rahimi]

> (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 <jeffreyalaw@gmail.com>
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;
>
>    <bb 2> [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&amp;data=04%7C01%7Cnavidrahimi%40microsoft.com%7Caa8c9c8213a245c7ae9d08d9af9fc8ae%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637733923073627850%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&amp;sdata=25KlLcsftTmN83rVawoKKaTPJdCdFlmtXMj%2BwsrKWbo%3D&amp;reserved=0
> 2) https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Falive2.llvm.org%2Fce%2Fz%2FUUTJ_v&amp;data=04%7C01%7Cnavidrahimi%40microsoft.com%7Caa8c9c8213a245c7ae9d08d9af9fc8ae%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637733923073637846%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&amp;sdata=fwN9%2BB0VObPyuUS2fOtj14i%2BHJIiRhyyjZM4LOF4AP8%3D&amp;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

Re: [EXTERNAL] Re: Question about match.pd

[Richard Biener]

On Thu, Nov 25, 2021 at 10:40 PM Navid Rahimi via Gcc <gcc@gcc.gnu.org> wrote:
>
> > (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.

Note it's the C language specification that requires this.

> 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.

Yeah, guess you need

   (cmp @0 { build_zero_cst (TREE_TYPE (@0); })

here.

>
>
> Best wishes,
> Navid.
>
> ________________________________________
> From: Jeff Law <jeffreyalaw@gmail.com>
> 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;
> >
> >    <bb 2> [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&amp;data=04%7C01%7Cnavidrahimi%40microsoft.com%7Caa8c9c8213a245c7ae9d08d9af9fc8ae%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637733923073627850%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&amp;sdata=25KlLcsftTmN83rVawoKKaTPJdCdFlmtXMj%2BwsrKWbo%3D&amp;reserved=0
> > 2) https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Falive2.llvm.org%2Fce%2Fz%2FUUTJ_v&amp;data=04%7C01%7Cnavidrahimi%40microsoft.com%7Caa8c9c8213a245c7ae9d08d9af9fc8ae%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637733923073637846%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&amp;sdata=fwN9%2BB0VObPyuUS2fOtj14i%2BHJIiRhyyjZM4LOF4AP8%3D&amp;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