This is an archive of the discontinued LLVM Phabricator instance.

[SCEV] Add a threshold to restrict number of mul operands to be inlined into SCEV
ClosedPublic

Authored by lihuang on Oct 19 2016, 2:20 PM.

Details

Summary

[SCEV] Add a threshold to restrict number of mul operands to be inlined into SCEV

This is to solve the same slow-compile issue in SCEV that D3127 was trying to solve. But that patch is no longer active.

Without a threshold for mul ops inlining, getMulExpr could have exponential time complexity in the worst case. The case in PR18606 is an example that causes clang to hang.

However, this patch does not completely solve the slow-compile issue in SCEV. The reason is, not completely flattening the SCEV DAG will make SCEVRewriteVisitor another bottleneck, which visits the same SCEV multiple times and could take exponential time to finish. I will fix this in another patch.

Diff Detail

Repository
rL LLVM

Event Timeline

lihuang updated this revision to Diff 75216.Oct 19 2016, 2:20 PM
lihuang retitled this revision from to [SCEV] Add a threshold to restrict number of mul operands to be inlined into SCEV.
lihuang updated this object.
lihuang added a subscriber: llvm-commits.
sanjoy added inline comments.Oct 20 2016, 1:00 AM
lib/Analysis/ScalarEvolution.cpp
2514 ↗(On Diff #75216)

I'd have phrased the limit as a cap on the size of Ops (either Ops.size() directly, or a cap on the number of new elements added to Ops in this loop). Any specific reason why you chose this approach over that?

test/Analysis/ScalarEvolution/max-mulops-inline.ll
24 ↗(On Diff #75216)

Can this test case be simplified? For instance, why do we need a loop at all? Why not just have a sequence of multiplication instructions in a single basic block?

lihuang updated this revision to Diff 75338.Oct 20 2016, 12:56 PM
lihuang marked 2 inline comments as done.Oct 20 2016, 1:01 PM
lihuang added inline comments.
lib/Analysis/ScalarEvolution.cpp
2514 ↗(On Diff #75216)

I agree, limiting the size of Ops is the right way. My previous change was wrong, it's limiting the number of ops to be inlined in a single iteration.

test/Analysis/ScalarEvolution/max-mulops-inline.ll
24 ↗(On Diff #75216)

Yes I removed the loop. I thought I'd need a loop to trigger SCEV analysis. Thanks!

sanjoy accepted this revision.Oct 20 2016, 1:05 PM
sanjoy edited edge metadata.

lgtm

This revision is now accepted and ready to land.Oct 20 2016, 1:05 PM
This revision was automatically updated to reflect the committed changes.
lihuang marked 2 inline comments as done.