This is an archive of the discontinued LLVM Phabricator instance.

[SCEV] Suppress hoisting insertion point of binops when unsafe
ClosedPublic

Authored by wristow on Dec 3 2018, 12:49 PM.

Details

Summary

InsertBinop tries to move insertion-points out of loops for expressions that are loop-invariant. This patch adds a new parameter, IsSafeToHost (default true), to guard that hoisting. This allows callers to suppress that hoisting for unsafe situations, such as divisions that may have a zero denominator.

This fixes PR38697.

Diff Detail

Event Timeline

wristow created this revision.Dec 3 2018, 12:49 PM
wristow added a subscriber: rnk.Dec 3 2018, 12:54 PM

Since the callers of SCEVExpander::InsertBinop "know" whether the binop being inserted is safe to hoist, this proposed solution of having the caller pass a parameter to indicate whether it's safe seems clean. But a simpler approach is to special-case the opcode Instruction::UDiv in InsertBinop.

An even simpler approach is to simply never hoist the insertion-point in InsertBinop. In fact, in the cases I've examined, SCEVExpander::expand always did the desired hoisting when it was safe, anyway. So removing the loop that I'm guarding here with the new parameter IsSafeToHoist is equivalent for those test-cases (the check-all tests all passed on x86_64-linux if I simply removed the loop entirely). I'd be happy to go with this approach of removing the hoisting loop, but I don't know for certain whether the hoisting is always redundant with other optimizations.

To try to understand (and in particular, to try to find a test-case that depended on that hoisting being done), I looked through the history of that hosting loop. I see it was added more than 8 years ago (r97642):

Make SCEVExpander and LSR more aggressive about hoisting expressions out
of loops.

But that revision didn't include any test-cases. So I'm at a loss to demonstrate whether there are any cases where the code-gen is improved by the hoisting.

In investigating this history, I noticed a couple of other interesting points.

First, the patch here, along with the recently committed patch of:
https://reviews.llvm.org/rL347934

is equivalent to a patch that was committed about a year ago:
https://reviews.llvm.org/rL289412

(As an aside, that year-old commit uses the simpler approach of special-casing the opcode Instruction::UDiv in InsertBinop to guard the loop, rather than having the caller pass an extra parameter to indicate when it's unsafe to hoist.)

Second, the reason this patch and the recently committed r347934 are needed (even though this was fixed a year ago by r289412), is because that year-old fix was reverted at r289453:

Reverts r289412. It caused an OOB PHI operand access in instcombine when
ASan is enabled. Reduction in progress.

@rnk: I wanted to give you a heads up that that problem may re-apear once this patch is reviewed and committed.

mkazantsev added inline comments.Dec 4 2018, 7:57 PM
llvm/lib/Analysis/ScalarEvolutionExpander.cpp
851

Limiting to constants looks super-conservative. How about getting SCEV for RHS and then asking SE isKnownPredicate(ICMP_NE, RHS, 0)?

wristow marked an inline comment as done.Dec 5 2018, 6:18 PM
wristow added inline comments.
llvm/lib/Analysis/ScalarEvolutionExpander.cpp
851

Sounds good.

That said, I've put this work on the back-burner for the moment, because the effectiveness of this patch depends on the change of rL347934 being in place, and that commit was reverted today (at rL348426), due to SEGVs happening in PHINode Simplification in Instcombine. That may be the same underlying problem that motivated the revert I previously mentioned that was done about a year ago:

Reverts r289412. It caused an OOB PHI operand access in instcombine when
ASan is enabled. Reduction in progress.

In any case, until the fix that was done as rL347934 is re-instated in some form, I'll hold off on making the fix discussed here.

wristow updated this revision to Diff 192943.Mar 29 2019, 4:54 PM

Limiting to constants looks super-conservative. How about getting SCEV for RHS and then asking SE isKnownPredicate(ICMP_NE, RHS, 0)?

Sounds good. ... In any case, until the fix that was done as rL347934 is re-instated in some form, I'll hold off on making the fix discussed here.

That fix has been reinstated at r356392 (D57428) so I'm now addressing this issue.

Taking the suggestion of isKnownPredicate(ICMP_NE, RHS, 0) from @mkazantsev, I see that for this situation, SE.isKnownNonZero(S->getRHS()) can be used. The resulting patch is then simpler than my original patch proposed here, and it adds the more aggressive analysis Max suggested. I've added additional tests in this update, which includes testing for that more aggressive behavior of the hoisting of a non-constant divisor that can be proven to be non-zero.

sanjoy requested changes to this revision.May 6 2019, 9:35 PM

Only minor nitpicky comments, will LGTM once these are fixed.

Normally I'd ask you to wait for Max, but looks like he is no longer at Azul and thus is not getting phabricator emails.

include/llvm/Analysis/ScalarEvolutionExpander.h
321 ↗(On Diff #192943)

I'd slightly prefer to not default this to anything, is that feasible?

test/Transforms/LoopVectorize/pr38697.ll
202 ↗(On Diff #192943)

We should give these instructions names so that updating the tests remains easy (use opt -instnamer).

228 ↗(On Diff #192943)

Can you please make these CHECK lines a bit more specific? Maybe using update_test_checks.py?

This revision now requires changes to proceed.May 6 2019, 9:35 PM
wristow updated this revision to Diff 198577.May 7 2019, 7:47 PM

Thanks for the review @sanjoy!

I've removed the default setting of the IsSafeToHoist argument, and I've used opt -instnamer to give the instructions names.

I also ran update_test_checks.py, but I felt compelled to edit the result down significantly (because there were so many instructions that were not related to the optimization, and I was worried it would make the resulting test too sensitive to unrelated changes in llvm). After editing it down to what I felt were the relevant instructions, I then also wanted to add some checks to verify that a division did not appear in places where it shouldn't be hoisted to. With that, I decided it was so different from the results of update_test_checks.py that I decided to remove the comment Assertions have been autogenerated by utils/update_test_checks.py. Bottom line: There are more explicit checks than I had originally, but not anywhere near the full set that would appear from that script. If you'd prefer that I leave the more substantial set of checks in place, let me know, and it will be easy for me to "un-do" much of the editing-down I did.

Herald added a project: Restricted Project. · View Herald TranscriptMay 7 2019, 7:47 PM
wristow marked 4 inline comments as done.May 7 2019, 7:50 PM
wristow added inline comments.
test/Transforms/LoopVectorize/pr38697.ll
228 ↗(On Diff #192943)

I've addressed this to some extent, but edited it down significantly. Let me know if you'd prefer the larger set of tests.

sanjoy accepted this revision.May 7 2019, 7:57 PM

lgtm

llvm/lib/Analysis/ScalarEvolutionExpander.cpp
833

Can you please add /*IsSafeToHoist*/ on these arguments?

This revision is now accepted and ready to land.May 7 2019, 7:57 PM
This revision was automatically updated to reflect the committed changes.
wristow marked an inline comment as done.
wristow marked an inline comment as done.May 8 2019, 11:49 AM

lgtm

Thanks for the review!