Hi Jakob,
I've a problem related to the commit #155362.
Consider the following snippet:
void bar(float* f) {
...
}
void foo(float* f, int idx) {
int hi = idx>>3;
int lo = idx&7;
bar(&f[hi*8+lo]); // hi*8 + lo == idx
bar(&f[hi*10+lo]);
}
Before 155362 revision InstCombine was able to optimize hi*8+lo to idx by
applying following patterns:
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.
Thanks,
Aleksey
--------------------------------------------------------------------
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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20130604/e9b8f677/attachment.html>
> 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
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.
On Jun 4, 2013, at 6:27 AM, "Bader, Aleksey A" <aleksey.a.bader at intel.com> wrote:> Hi Jakob, > > I’ve a problem related to the commit #155362. > > Consider the following snippet: > void bar(float* f) { > … > } > void foo(float* f, int idx) { > int hi = idx>>3; > int lo = idx&7; > bar(&f[hi*8+lo]); // hi*8 + lo == idx > bar(&f[hi*10+lo]); > } > > Before 155362 revision InstCombine was able to optimize hi*8+lo to idx by applying following patterns: > 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.Actually, your own code illustrates the problem with this transformation. Suppose you were using SCEV to analyze the behavior of the to f[] memory references: f[hi*8 + lo] f[hi*10 + lo] If you rewrite 'hi*8 + lo' to ‘idx’, the affine relationship between the two memory references is no longer visible, and SCEV will probably tell you that the offsets are unrelated. The fundamental problem is that there is no such thing as a canonical form of an expression DAG. Some expression graphs, like this one, can take different forms that each enable different analyses. Which one is correct? I think that the right approach in this case is to preserve the relationships that were already exposed in the original code. That is why pattern 4* is disabled when the inner expression has multiple uses. It preserves the relationships that are expressed through the ‘hi’ variable. Thanks, /jakob