llvm dev - Sep 2015 - Re: Problem with LSR

Anyone?

2015-09-17 20:59 GMT+03:00 Anton Nadolskiy <anton.nadolskiy at gmail.com>:
> Hello, folks!
>
> I need help with LSR optimization.
>
> I've spent pretty much trying to understand what's going on here,
but
> still don’t understand some things.
>
> *First*, what is Scale in Formula? Consider *for(i=0; i < n; i++)*. The
> initial formula for ICMP use will be:
>
> (1)    reg({%n,+,-1}<nw><%for.body>)
>
> Next we build other forms:
>
>     (2)     reg(%n) + 1*reg({0,+,-1}
>     (3)     reg({(-1 * %n),+,1}
>     (4)     reg((-1 * %n)) + 1*reg({0,+,1}
>     (5)     reg(%n) + -1*reg({0,+,1}
>     (6)     reg((-1 * %n)) + -1*reg({0,+,-1}
>
> I’m wondering about (4) and (6). What’s negative scale? It affects
> formula’s cost, so, for example, (4) loses to (5).
>
> *Second*, we change ICMP to compare against zero, so we get *for(i=n; i
>
> 0; i--)* and (1) for initial formula.
>
> But we’re not considering
>     (7)     reg((-1 * %n)) + reg({0,+,1}
>
> which corresponds to our initial *for(i=0; i < n; i++)*.
>
> Again, I don’t know what’s the difference between this and (4) and (6),
> bit it will win (5) at least.
>
>  Now, I also want (7) to win (1), in cases like this
>
>
>
>
>
>
>
>
>
>
> *void foo( int n,  int red[], int green[],  int blue[], int alpha[],
>           int rdest[],  int gdest[], int bdest[],  int adest[] ){
>  for (int i=0;i<n;i++) {               red[i]   = rdest[i];
>  green[i] = gdest[i];               blue[i]  = bdest[i];
>  alpha[i] = adest[i];                   }}*
>
> Just compile it with GCC and CLANG and see how bad the things are. (.text
> section is 64 bytes for GCC and 184 for CLANG). I'm talking about x86,
not
> sure for other architectures.
>
> The problem is that we shouldn’t change loop direction, i.e. apply (1). If
> you replace *n* in example above with constant, everything will be
> fine. (because
> *-1024 + reg({0,+,1}* will win *reg({1024,+,-1}*)
>
>  Even with (7) it will always lose to (1), because (1) has less registers.
>
> So, any ideas on this?
>
> P.S. I was thinking about a hack, when in certain conditions we just
> explicitly lower formula’s cost (NumRegs -= 1), but this is probably not
> the best way.
>
>
> Thanks,
> > Anton
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150924/c53b45a4/attachment.html>

On Thu, Sep 24, 2015 at 9:13 AM, Anton Nadolskiy via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
> Anyone?
>
To back you up with a repost from another thread: LSR is counter
productive for easy to understand cases on x86.  Take this simple
array copy for example where my assessment seems similar yours.

void copy(int* src, int* dst, unsigned int size) {
    for (unsigned int i = 0; i < size; ++i)
        dst[i] = src[i];
}

The hot spot for i686 contains 6 instructions with LSR:

8b 32          mov    (%edx),%esi
89 31          mov    %esi,(%ecx)
83 c1 04     add    $0x4,%ecx
83 c2 04     add    $0x4,%edx
48              dec    %eax
75 f3          jne    11 <copy+0x11>

but only 5 instructions *without* LSR.

8b 3c b2      mov    (%edx,%esi,4),%edi
89 3c b1      mov    %edi,(%ecx,%esi,4)
46               inc    %esi
39 c6          cmp    %eax,%esi
75 f5           jne    14 <copy+0x14>

My interpretation of this problem was that LSR starts analysis with an
SCEV that counts down toward zero even in an upward counting loop.  A
more natural fit would be an initial IV going from 0 to some limit,
but there does not seem to be a way to express this sort of SCEV.  The
initial condition puts an artificially high cost on solutions with
upward counting registers since none match the "free" down counting
SCEV.  Notice the weird 'dec %eax' showing up as an artifact.  The
best solution with base-index scale 4 addressing was considered by
LSR, but incorrectly deemed to be too expensive.