This is an archive of the discontinued LLVM Phabricator instance.

[SCEVExpand] do not hoist divisions by zero (PR30935)
ClosedPublic

Authored by sebpop on Nov 29 2016, 9:44 AM.

Details

Summary

SCEVExpand computes the insertion point for the components of a SCEV to be code generated.
When it comes to generating code for a division SCEVexpand would not be able to check (at compilation time) all the conditions necessary to avoid a division by zero.
The patch disables hoisting of expressions containing divisions by anything other than constants in order to avoid hoisting these expressions past conditions that should hold before doing the division.

The patch passes check-all on x86_64-linux.

Diff Detail

Repository
rL LLVM

Event Timeline

sebpop updated this revision to Diff 79593.Nov 29 2016, 9:44 AM
sebpop retitled this revision from to [SCEVExpand] do not hoist divisions by zero (PR30935).
sebpop updated this object.
sebpop added reviewers: sanjoy, spatel, atrick.
sebpop added subscribers: llvm-commits, hiraditya.
sanjoy requested changes to this revision.Nov 29 2016, 10:10 AM
sanjoy edited edge metadata.

I tried to address this some time back in rL286437, but that had to be reverted due to PR30976. Can you please take a look and make sure that this patch does not have the same problem?

Also, does the C++ unit test case from rL286437 also pass with this patch? If so, that would be nice to include too.

llvm/lib/Analysis/ScalarEvolutionExpander.cpp
1670 ↗(On Diff #79593)

Use const auto *

1673 ↗(On Diff #79593)

What about divisions by constant zero? If they can't happen, then add an assert here.

This revision now requires changes to proceed.Nov 29 2016, 10:10 AM

I tried to address this some time back in rL286437, but that had to be reverted due to PR30976. Can you please take a look and make sure that this patch does not have the same problem?

Also, does the C++ unit test case from rL286437 also pass with this patch? If so, that would be nice to include too.

Yes this patch also fixes PR30942: I marked it as a duplicate of the earlier PR30935.
The patch does not ICE the compiler on the testcase of PR30976.

Thanks Sanjoy for the review: I will submit an updated patch.

sebpop updated this revision to Diff 79638.Nov 29 2016, 2:01 PM
sebpop edited edge metadata.

Updated patch with all suggestions from Sanjoy.

sebpop planned changes to this revision.Nov 29 2016, 2:27 PM

Sanjoy, I think your previous patch has fixed one more place SCEVExpander::InsertBinop():
the second assert from your unittest is still failing with the current patch:

EXPECT_EQ(DivInst->getParent(), DivFromScratchExpansionInst->getParent());

that is an expression built from scratch and inserted in the code at the same place as "x/y".
Let me fix that other place as well.

sebpop updated this revision to Diff 79649.Nov 29 2016, 2:59 PM
sebpop edited edge metadata.

Added the unittest and the change to make it pass: InsertBinop() should not hoist divisions by zero.

Hi,

I don't think this patch properly addresses PR30976 -- it only hides the symptom. For instance, this new test case crashes SCEVExpander even with this fix: https://reviews.llvm.org/differential/diff/79708/

I think the fundamental problem is that there is no clear distinction in SCEVExpander between hoisting for optimization and hoisting for correctness (i.e. for the right domination properties to hold). We need to fix that before we can fix PR30976.

llvm/lib/Analysis/ScalarEvolutionExpander.cpp
170 ↗(On Diff #79649)

Why do you need the inline keyword here?

1679 ↗(On Diff #79649)

This looks too complicated to be within the condition of an if -- can you extract out a bool SafeToHoist = ...?

1687 ↗(On Diff #79649)

Why not return SC->getValue()->isZero();?

Hi,

I don't think this patch properly addresses PR30976 -- it only hides the symptom. For instance, this new test case crashes SCEVExpander even with this fix: https://reviews.llvm.org/differential/diff/79708/

I think I've addressed the underlying problem with r289397 so this (along with the test case above) should be okay to go in, pending review comments.

This revision was automatically updated to reflect the committed changes.
atrick edited edge metadata.Dec 12 2016, 8:23 AM

How do you know this won't move division that used to be outside the loop (possibly multiple levels) inside the innermost loop?

How do you know this won't move division that used to be outside the loop (possibly multiple levels) inside the innermost loop?

You are right: expanding SCEV expressions could lead to a loss in performance.
I'm not sure we have all the information we need to generate code at least as efficient as the one we started from.

How do you know this won't move division that used to be outside the loop (possibly multiple levels) inside the innermost loop?

At least for the easy case where the expressions are the same, and one div expression is dominating the other loop nested one,
a post processing pass like PRE should be able to find the redundancy and eliminate the inner computation.

There are still two problems:

  • scev folds expressions and the expressions to be code generated do not necessarily end up to be the exact expressions as computed in the code,
  • in the case of Polly's use of SCEVExpand the analyzed code belongs to a different region than the place where we need to insert the code. Polly does code versioning: it places the original loop in the then clause and starts generating code in the else clause. So no matter how hard we try to find the div expression in the code above, we won't find it, because it is probably not needed in the new code except in the expansion of the scev.