Page MenuHomePhabricator

[SCEV] Enhance SCEVFindUnsafe for division
ClosedPublic

Authored by mkazantsev on Oct 24 2017, 4:34 AM.

Details

Summary

This patch allows SCEVFindUnsafe algorithm to tread division by any non-positive
value as safe. Previously, it could only recognize non-zero constants.

Diff Detail

Event Timeline

mkazantsev created this revision.Oct 24 2017, 4:34 AM
sanjoy accepted this revision.Oct 24 2017, 9:39 AM
sanjoy added inline comments.
test/Transforms/IndVarSimplify/udiv.ll
172 ↗(On Diff #120039)

Put something else instead of undef here for completeness, loading from undef is UB.

This revision is now accepted and ready to land.Oct 24 2017, 9:39 AM
mkazantsev added inline comments.Oct 24 2017, 10:46 AM
test/Transforms/IndVarSimplify/udiv.ll
172 ↗(On Diff #120039)

Ok, will do before checking in.

This revision was automatically updated to reflect the committed changes.
eastig reopened this revision.Oct 26 2017, 8:56 AM
eastig added subscribers: qcolombet, wmi, eastig.

Hi,
This patch caused SingleSource/Benchmarks/Shootout/shootout-sieve regression on Arm public bots:

http://lnt.llvm.org/db_default/v4/nts/76950 13.43%
http://lnt.llvm.org/db_default/v4/nts/77068 10.61%

The affected pass is LSR.
I'll provide more data shortly.

Thanks,
Evgeny Astigeevich
The ARM Compiler Optimization team leader

This revision is now accepted and ready to land.Oct 26 2017, 8:56 AM

I attached


Comparing them I can see a number of operations in a loop is increased.

Compiler options:
clang -c -S --target=aarch64-linux-gnueabi -DNDEBUG -O3 -DNDEBUG -mcpu=cortex-a57 -fomit-frame-pointer sieve.c

Reverted as https://reviews.llvm.org/rL316739. I will try to understand what happens.

Hi Evgeny!

I see the difference before the LSR: for the last loop, in the *** IR Dump Before Loop Strength Reduction *** section we have two more Phis. It has two more Phis and more instructions in body (with repeating pattern). Most likely it is unrolling changed the number of unrolled iterations.

For first two loops, in one case it just changed iteration space from 0->len to len->0 which shouldn't have significant performance impact; in another case nothing changed but variable name.

So I believe that problem dwells before LSR, most likely in unrolling.

Hi Max,

Thank you for initial investigation. I'll try to debug the unrolling.

Thanks,
Evgeny



Hi Max,

I did some debugging. It's definitely LSR. Compare test.good.ll and test.bad.ll produced from test.ll with

opt -loop-reduce -S -o - test.ll

Thanks,
Evgeny

This revision was automatically updated to reflect the committed changes.
Herald added a project: Restricted Project. · View Herald TranscriptOct 7 2019, 5:20 AM