[LLVMdev] Missing InstCombine optimization.

[Bader, Aleksey A]

Hi Rafael,

> We used handle arbitrary  ((idx >> A) << B), right? 
We used to handle three patterns, which were deferred:
(from Jakob's log message)
  These transformations are deferred:
  
    (X >>? C) << C   --> X & (-1 << C)  (When X >> C has multiple uses)   <--- my case
    (X >>? C1) << C2 --> X << (C2-C1) & (-1 << C2)   (When C2 > C1)
    (X >>? C1) << C2 --> X >>? (C1-C2) & (-1 << C2)  (When C1 > C2)

So ((idx >> A) << A) (when idx >> A has multiple uses) was intentionally deferred.

> Maybe it is enough to handle   ((idx >> A) << A) in instcombine?
It would be enough for my particular case, but apparently is not be enough for some other cases.
I don't quite understand the motivation behind the original commit, that is why I need your assistance on fixing this issue.
It seems like applying "((X >> C) << C) -> X & -C" rule in instcombine is not efficient in some other cases.
Does anyone know such cases?
Otherwise the fix is very simple - just add back a few deleted lines of code.

Thanks,
Aleksey

-----Original Message-----
From: Rafael Espíndola [mailto:rafael.espindola at gmail.com] 
Sent: Tuesday, June 04, 2013 11:58 PM
To: Bader, Aleksey A
Cc: Jakob Stoklund Olesen; LLVM Developers Mailing List
Subject: Re: [LLVMdev] Missing InstCombine optimization.

> 1.       hi*8 -> hi << 3
>
> 2.       ((idx >> 3) << 3) -> idx & -8
>
> 3.       hi*8+lo -> hi*8 | lo
>
> 4.       (idx & -8) | (idx & 7) -> idx & (-8 | 7) -> idx
>
>
>
> After 155362 pattern #2 is deferred to DAGCombine stage, so 
> InstCombine is unable to apply pattern #4:
>
>         4*. ((idx >> 3) << 3) | (idx & 7) -> idx // SimplifyOr can’t 
> handle it.
>
>
>
> So now LLVM IR contains a couple of redundant operations:
>
>   %mul312 = shl nsw i32 %shr, 3 ; hi*8
>
>   %add313 = or i32 %mul312, %and ; hi*8 + lo == idx
>
>
>
> These few additional operations over index prevent our analysis pass 
> from recognizing memory access patterns and I believe could harm not only us.
>
> I think 4* optimization can be safely done at LLVM IR level.
>
> Can you suggest the best way to fix this issue? I suppose adding new 
> pattern just for particular 4* case is not the best way.


We used handle arbitrary  ((idx >> A) << B), right? Maybe it is enough
to handle   ((idx >> A) << A) in instcombine?

Cheers,
Rafael

--------------------------------------------------------------------
Closed Joint Stock Company Intel A/O
Registered legal address: Krylatsky Hills Business Park, 
17 Krylatskaya Str., Bldg 4, Moscow 121614, 
Russian Federation

This e-mail and any attachments may contain confidential material for
the sole use of the intended recipient(s). Any review or distribution
by others is strictly prohibited. If you are not the intended
recipient, please contact the sender and delete all copies.