This is an archive of the discontinued LLVM Phabricator instance.

[SCEV] Use backedge SCEV of PHI only if its input is loop invariant
ClosedPublic

Authored by dantrushin on Jan 22 2020, 5:58 AM.

Details

Summary

For the PHI node

    
%1 = phi [%A, %entry], [%X, %latch]

it is incorrect to use SCEV of backedge val %X as an exit value
of PHI unless %X is loop invariant.
This is because exit value of %1 is value of %X at one-before-last
iteration of the loop.

Diff Detail

Event Timeline

dantrushin created this revision.Jan 22 2020, 5:58 AM
Herald added a project: Restricted Project. · View Herald TranscriptJan 22 2020, 5:58 AM
dantrushin marked an inline comment as done.Jan 22 2020, 6:02 AM
dantrushin added inline comments.
llvm/lib/Analysis/ScalarEvolution.cpp
8292

Bailing out here when any PHI is seen, because I did not find convinient API to get SCEV at previous iteration.
Is there one?

sanjoy.google added inline comments.Jan 22 2020, 8:13 AM
llvm/lib/Analysis/ScalarEvolution.cpp
8283

This comment needs to be fixed IMO. It isn't necessarily a loop invariant value; we're really checking for a value that can be materialized outside the loop.

8292

I don't think you need to go through SCEV here. You can just pick the llvm::Value for the PHI for the backedge and get the SCEV for that.

dantrushin marked an inline comment as done.Jan 22 2020, 8:59 AM
dantrushin added inline comments.
llvm/lib/Analysis/ScalarEvolution.cpp
8292

Excuse me, I don't understand (or, rather my comment was unclear).

Existing code already does that. In terms of test case below, PN is PHI %local_3_4
Its backedge Value is %local_6_6 which is another PHI from the same block.
But using %local_6_6's SCEV as value for %local_3_4 is wrong, because %local_3_4 uses value of %local_6_6
from previous iteration
So my fix is not to perform this optimization when PHI's input is another PHI

Or you mean something else?

sanjoy.google added inline comments.Jan 22 2020, 9:07 AM
llvm/lib/Analysis/ScalarEvolution.cpp
8292

I was unclear as well.

I'm suggesting we do this:

Value *BackedgeVal = PN->getIncomingValue(InLoopPred);
if (auto* InputPN = dyn_cast<PHINode>(BackedgeVal)) {
  if (InputPN->getParent() == PN->getBlock()) {
    // PHI translation
    BackedgeVal = InputPN->getIncomingValue(InLoopPred);
  }
}
const SCEV *OnBackedge = getSCEV(BackedgeVal);
// ... no other change
dantrushin marked an inline comment as done.Jan 22 2020, 9:17 AM
dantrushin added inline comments.
llvm/lib/Analysis/ScalarEvolution.cpp
8292

That gave me even "wronger" answer :)
Correct answer for the test is -276.
Current LLVM produces -277
With your suggestion I get -278.

xbolva00 added inline comments.
llvm/test/Analysis/ScalarEvolution/pr44605.ll
2

Use update scripts from utils/ ?

32

Check for correct result please

  • Changed source code comment
  • Ran test case through update_test_checks
dantrushin marked 3 inline comments as done.Jan 22 2020, 9:55 AM
mkazantsev added inline comments.Jan 23 2020, 12:36 AM
llvm/lib/Analysis/ScalarEvolution.cpp
8291

Your check is overprotective. If BackedgeVal is a Phi from another loop than PN's (e.g. outer loop or some other loop going before it), it is OK to use it as exit value. The problem only happens if PN->getLoop() == BackedgeVal->getLoop(), am I correct?

llvm/test/Analysis/ScalarEvolution/pr44605.ll
47

Does the test really need all these computations inside? It's tad too much code, not clear what of it is important. If you can reduce the test please do.

  • Check that PHI's input is the PHI from the same block(loop);
  • Add comment to test explaining its complexity
dantrushin marked 6 inline comments as done.Jan 23 2020, 1:58 AM
dantrushin added inline comments.
llvm/lib/Analysis/ScalarEvolution.cpp
8291

You're right.
I've been cutting edges to keep code cleaner ;)

llvm/test/Analysis/ScalarEvolution/pr44605.ll
47

Yes. They all needed to outsmart LLVM and make it execute this code.
All that matters in fact, are just two PHIs, %local_6_6 and %local_3_4

Unit tests: pass. 62134 tests passed, 0 failed and 808 were skipped.

clang-tidy: fail. clang-tidy found 68 errors and 215 warnings.

clang-format: pass.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

LGTM with nit (see inline).

llvm/lib/Analysis/ScalarEvolution.cpp
8291

Looks correct now, but I'd rather ask you to factor out this check into a lambda (smth like IsPhiFromSameBlock); makes it easier to understand what happens.

dantrushin marked 2 inline comments as done.

Introduced lambda according to comments.

dantrushin marked an inline comment as done.Jan 23 2020, 3:08 AM

Unit tests: pass. 62134 tests passed, 0 failed and 808 were skipped.

clang-tidy: fail. clang-tidy found 68 errors and 215 warnings.

clang-format: pass.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

sanjoy.google added inline comments.Jan 23 2020, 7:31 AM
llvm/lib/Analysis/ScalarEvolution.cpp
8292

I see. I now think that the problem is not with using a PHI node, but with any loop varying value. IOW if you have:

loop:
  A = PHI(0, B)
  B = SomethingWhoseValueChangesOnEachIteration();

then the exit value of A is *not* B, even if the loop body is guaranteed to execute more than once. The exit value of A is the value of B in the one-beofore-last iteration, not B in the last iteration.

So even with your change, if I modify your unit test to have %local_3_4 = phi i32 [ 2, %entry ], [ %5, %latch ] then we will run into the same problem even with your change.

Does that sound right?

dantrushin marked an inline comment as done.Jan 23 2020, 8:11 AM
dantrushin added inline comments.
llvm/lib/Analysis/ScalarEvolution.cpp
8292

Ugh. You're right.
It looks like original comment was correct about loop invariant, it's just D63224 missed correct check for that...
I'll rework the patch.

Rework patch to actually reqiure PHI backedge value to be loop invariant,
as original comment stated.

dantrushin retitled this revision from [SCEV] Do not use backedge SCEV of PHI if its input is another PHI to [SCEV] Use backedge SCEV of PHI only if its input is loop invariant.Jan 23 2020, 10:01 AM
dantrushin edited the summary of this revision. (Show Details)
dantrushin marked an inline comment as done.
sanjoy.google added inline comments.Jan 23 2020, 10:04 AM
llvm/lib/Analysis/ScalarEvolution.cpp
8292

Do we still need the IsAvailableOnEntry?

Unit tests: fail. 62137 tests passed, 5 failed and 811 were skipped.

failed: libc++.std/language_support/cmp/cmp_partialord/partialord.pass.cpp
failed: libc++.std/language_support/cmp/cmp_strongeq/cmp.strongeq.pass.cpp
failed: libc++.std/language_support/cmp/cmp_strongord/strongord.pass.cpp
failed: libc++.std/language_support/cmp/cmp_weakeq/cmp.weakeq.pass.cpp
failed: libc++.std/language_support/cmp/cmp_weakord/weakord.pass.cpp

clang-tidy: pass.

clang-format: pass.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

Pre-merge checks is in beta. Report issue. Please join beta or enable it for your project.

dantrushin marked an inline comment as done.Jan 23 2020, 11:06 AM
dantrushin added inline comments.
llvm/lib/Analysis/ScalarEvolution.cpp
8292

I'm not quite sure.
For the value dominance, it should be safe. Can we have problems with SCEV reaching this loop from another loop nest?

dantrushin edited the summary of this revision. (Show Details)

Get rid of IsAvailableOnEntry, as supposedly, loop invariant value
should be available on loop entry already.
(But again, was it really needed in original version?
PHI operand should be available. Can its SCEV be not?)

dantrushin marked an inline comment as done.Jan 24 2020, 7:52 AM
lebedev.ri added inline comments.
llvm/test/Analysis/ScalarEvolution/pr44605.ll
2

Precommit the test? It isn't very obvious what effect the fix has on the output.

Unit tests: fail. 62137 tests passed, 5 failed and 811 were skipped.

failed: libc++.std/language_support/cmp/cmp_partialord/partialord.pass.cpp
failed: libc++.std/language_support/cmp/cmp_strongeq/cmp.strongeq.pass.cpp
failed: libc++.std/language_support/cmp/cmp_strongord/strongord.pass.cpp
failed: libc++.std/language_support/cmp/cmp_weakeq/cmp.weakeq.pass.cpp
failed: libc++.std/language_support/cmp/cmp_weakord/weakord.pass.cpp

clang-tidy: pass.

clang-format: pass.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

Pre-merge checks is in beta. Report issue. Please join beta or enable it for your project.

Unit tests: fail. 62137 tests passed, 5 failed and 811 were skipped.

failed: libc++.std/language_support/cmp/cmp_partialord/partialord.pass.cpp
failed: libc++.std/language_support/cmp/cmp_strongeq/cmp.strongeq.pass.cpp
failed: libc++.std/language_support/cmp/cmp_strongord/strongord.pass.cpp
failed: libc++.std/language_support/cmp/cmp_weakeq/cmp.weakeq.pass.cpp
failed: libc++.std/language_support/cmp/cmp_weakord/weakord.pass.cpp

clang-tidy: pass.

clang-format: pass.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

Pre-merge checks is in beta. Report issue. Please join beta or enable it for your project.

Merge guard bot failures are not related to this change, they were caused by bad clang commit...

lebedev.ri added inline comments.Mar 2 2020, 9:40 AM
llvm/lib/Analysis/ScalarEvolution.cpp
8291

Why not just LI->isLoopInvariant(BackedgeVal)?

Remove redundant lambda

dantrushin marked an inline comment as done.Mar 12 2020, 12:06 PM
Meinersbur accepted this revision.Mar 28 2020, 3:38 AM
Meinersbur added a subscriber: Meinersbur.

LGTM

This revision is now accepted and ready to land.Mar 28 2020, 3:38 AM
This revision was automatically updated to reflect the committed changes.

This patch bugged me when I first saw it go by; finally got back to looking at it today.

After reading the code, I'm fairly sure this is papering over an issue. The description given in the review and the patch discussion seem to indicate the believed problem was around using a loop variant value from the previous iteration of the loop as the value for a phi's exit, but the previous code appears to have handled that. IsAvailableOnEntry should be returning true only for cases where the value is either currently invariant, or can be made invariant through SCEVExpander.

What I suspect is actually going on this test case is there's some mismatch between IsAvailableOnEntry and the actual expansion logic. As a wild guess, we've seen issues around nsw/nuw flags in the past which have never been fully tracked down, it's possible this is another of those.

I spent some time today seeing if anything obvious fell out, but didn't make much progress on this investigation. The test case is involved enough that the reasoning is quite complicated.

To be clear, I am not asking for a revert or any other specific action to be taken. I'm just recording my concern for the record. If someone later comes along tracking down a performance regression, I want the context to be on the review thread. There's a decent chance that later person might be me. :)

This comment was removed by Meinersbur.

I removed my previous comment because I missed "outer loop" where my example applied to a single loop only.