This is an archive of the discontinued LLVM Phabricator instance.

[SCEV] createAddRecFromPHI: Optimize for the most common case.
ClosedPublic

Authored by mzolotukhin on Apr 28 2017, 4:13 PM.

Details

Summary

The existing implementation creates a symbolic SCEV expression every
time we analyze a phi node and then has to remove it, when the analysis
is finished. This is very expensive, and in most of the cases it's also
unnecessary. According to the data I collected, ~60-70% of analyzed phi
nodes (measured on SPEC) have the following form:

PN = phi(Start, OP(Self, Constant))

Handling such cases separately significantly speeds this up.

Event Timeline

mzolotukhin created this revision.Apr 28 2017, 4:13 PM
sanjoy requested changes to this revision.May 2 2017, 7:11 PM
sanjoy added inline comments.
lib/Analysis/ScalarEvolution.cpp
4092

How about createSimpleAffineAddRec?

4097

Bad space?

4108

I'd avoid using getExistingSCEV here. Instead, how about checking L->isLoopInvariant(BO->RHS or BO->LHS) and if so, call getSCEV? Then you won't waste work since if L->isLoopInvariant(BO->RHS or BO->LHS) is true then you know you're going to be able to return an add recurrence.

4109

As discussed on IRC, please check if this is actually viable.

4118

If you do the check above on L->isLoopInvariant(BO->RHS or BO->LHS) then this won't be necessary.

4169

auto *.

This revision now requires changes to proceed.May 2 2017, 7:11 PM
mzolotukhin updated this revision to Diff 97737.May 3 2017, 3:45 PM
mzolotukhin edited edge metadata.
  • Address Sanjoy's remarks.

Thanks for taking a look, I've updated the patch.

The change in 2014-08-29-CompactUnwind.ll is caused by the fact that SCEV started to produce a simpler expression for %iv.i, which allowed LSR to optimize the test harder. The test seems to exercise instructions positions, so I tried to keep them untouched with this change. It's still a question why the original SCEV algorithm failed to construct the simpler expression for this case, I'll take a look at it later if I find a time.

Michael

sanjoy accepted this revision.May 3 2017, 3:49 PM

lgtm, but the test case change looks fishy. This change is NFC right?

include/llvm/Analysis/ScalarEvolution.h
820

Indent?

test/CodeGen/X86/2014-08-29-CompactUnwind.ll
27

Why did you change this?

This revision is now accepted and ready to land.May 3 2017, 3:49 PM
mzolotukhin updated this revision to Diff 97738.May 3 2017, 3:51 PM
  • Fix indentation.

This change is NFC right?

I wanted it to be so, but apparently it's not. See more details in my previous reply.

Michael

sanjoy added a comment.May 3 2017, 3:53 PM

Thanks for taking a look, I've updated the patch.

The change in 2014-08-29-CompactUnwind.ll is caused by the fact that SCEV started to produce a simpler expression for %iv.i, which allowed LSR to optimize the test harder.

Hm, I suspect this is because BEValue would be a SCEVUnknown in that case (== the symbolic phi) in the slow path since %iv.i+0 would be simplified to %iv.i.

So that means this change isn't quite NFC. Can you please add a dedicated test case checking the difference in behavior above ^?

The test seems to exercise instructions positions, so I tried to keep them untouched with this change. It's still a question why the original SCEV algorithm failed to construct the simpler expression for this case, I'll take a look at it later if I find a time.

Michael

This revision was automatically updated to reflect the committed changes.