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

[dantrushin]

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.

[dantrushin]

llvm/lib/Analysis/ScalarEvolution.cpp

8247

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]

llvm/lib/Analysis/ScalarEvolution.cpp

8238

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.

8247

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]

llvm/lib/Analysis/ScalarEvolution.cpp

8247

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]

llvm/lib/Analysis/ScalarEvolution.cpp

8247

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]

llvm/lib/Analysis/ScalarEvolution.cpp

8247

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

[xbolva00]

llvm/test/Analysis/ScalarEvolution/pr44605.ll

2

Use update scripts from utils/ ?

32

Check for correct result please

[dantrushin]

• Changed source code comment
• Ran test case through update_test_checks

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

8246

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.

[dantrushin]

• Check that PHI's input is the PHI from the same block(loop);
• Add comment to test explaining its complexity

[dantrushin]

llvm/lib/Analysis/ScalarEvolution.cpp

8246

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

[merge_guards_bot]

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

[mkazantsev]

LGTM with nit (see inline).

llvm/lib/Analysis/ScalarEvolution.cpp

8246

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]

Introduced lambda according to comments.

[merge_guards_bot]

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]

llvm/lib/Analysis/ScalarEvolution.cpp

8247

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]

llvm/lib/Analysis/ScalarEvolution.cpp

8247

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.

[dantrushin]

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

[sanjoy.google]

llvm/lib/Analysis/ScalarEvolution.cpp

8247

Do we still need the IsAvailableOnEntry?

[merge_guards_bot]

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]

llvm/lib/Analysis/ScalarEvolution.cpp

8247

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]

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?)

[lebedev.ri]

llvm/test/Analysis/ScalarEvolution/pr44605.ll

2

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

[merge_guards_bot]

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_guards_bot]

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]

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

[dantrushin]

Ping

[lebedev.ri]

llvm/lib/Analysis/ScalarEvolution.cpp

8246

Why not just LI->isLoopInvariant(BackedgeVal)?

[dantrushin]

Remove redundant lambda

[dantrushin]

Ping

[Meinersbur]

LGTM

[reames]

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. :)

[Meinersbur]

This comment was removed by Meinersbur.

[Meinersbur]

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

llvm/lib/Analysis/ScalarEvolution.cpp

if (Instruction *I = dyn_cast<Instruction>(SU->getValue())) {
                   MultipleInitValues = true;
                   break;
                 }
               }
             }
             if (!MultipleInitValues && InitValue)
               return getSCEV(InitValue);
           }
-          // Do we have a loop invariant value flowing around the backedge
+          // Do we have a PHI value we can materialize
           // for a loop which must execute the backedge?
           if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount) &&
               isKnownPositive(BackedgeTakenCount) &&
               PN->getNumIncomingValues() == 2) {
             unsigned InLoopPred = LI->contains(PN->getIncomingBlock(0)) ? 0 : 1;
-            const SCEV *OnBackedge = getSCEV(PN->getIncomingValue(InLoopPred));
-            if (IsAvailableOnEntry(LI, DT, OnBackedge, PN->getParent()))
+            BasicBlock *Header = PN->getParent();
+            Value *BackedgeVal = PN->getIncomingValue(InLoopPred);
+            const SCEV *OnBackedge = getSCEV(BackedgeVal);
+            if (!(isa<PHINode>(BackedgeVal) &&
+                  cast<PHINode>(BackedgeVal)->getParent() == Header) &&
+                IsAvailableOnEntry(LI, DT, OnBackedge, Header))
               return OnBackedge;
           }
           if (auto *BTCC = dyn_cast<SCEVConstant>(BackedgeTakenCount)) {
             // Okay, we know how many times the containing loop executes.  If
             // this is a constant evolving PHI node, get the final value at
             // the specified iteration number.
             Constant *RV =
                 getConstantEvolutionLoopExitValue(PN, BTCC->getAPInt(), LI);

llvm/test/Analysis/ScalarEvolution/pr44605.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; NOTE: Only %local_6_6 and %local_3_4 nodes are important here.
+;       All other instructions are needed to lure LLVM into executing
+;       specific code to trigger a bug.
+; RUN: opt < %s -indvars -S | FileCheck %s
+define i32 @test() {
+; CHECK-LABEL: @test(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[OUTER:%.*]]
+; CHECK:       outer:
+; CHECK-NEXT:    [[LOCAL_6_6:%.*]] = phi i32 [ 10, [[ENTRY:%.*]] ], [ [[TMP5:%.*]], [[LATCH:%.*]] ]
+; CHECK-NEXT:    [[LOCAL_4_5:%.*]] = phi i32 [ 56587, [[ENTRY]] ], [ 0, [[LATCH]] ]
+; CHECK-NEXT:    [[LOCAL_3_4:%.*]] = phi i32 [ 2, [[ENTRY]] ], [ [[LOCAL_6_6]], [[LATCH]] ]
+; CHECK-NEXT:    [[DOTUDIV:%.*]] = udiv i32 [[LOCAL_6_6]], 8361
+; CHECK-NEXT:    br label [[INNER:%.*]]
+; CHECK:       inner:
+; CHECK-NEXT:    [[LOCAL_7_3:%.*]] = phi i32 [ 2, [[OUTER]] ], [ [[TMP3:%.*]], [[INNER]] ]
+; CHECK-NEXT:    [[LOCAL_4_5_PN:%.*]] = phi i32 [ [[LOCAL_4_5]], [[OUTER]] ], [ [[TMP2:%.*]], [[INNER]] ]
+; CHECK-NEXT:    [[LOCAL_3_31:%.*]] = mul i32 [[LOCAL_4_5_PN]], [[DOTUDIV]]
+; CHECK-NEXT:    [[TMP0:%.*]] = mul nuw nsw i32 [[LOCAL_7_3]], [[DOTUDIV]]
+; CHECK-NEXT:    [[TMP1:%.*]] = sub i32 [[TMP0]], [[LOCAL_3_4]]
+; CHECK-NEXT:    [[TMP2]] = add i32 [[TMP1]], [[LOCAL_3_31]]
+; CHECK-NEXT:    [[TMP3]] = add nuw nsw i32 [[LOCAL_7_3]], 1
+; CHECK-NEXT:    [[TMP4:%.*]] = icmp ugt i32 [[LOCAL_7_3]], 4
+; CHECK-NEXT:    br i1 [[TMP4]], label [[LATCH]], label [[INNER]]
+; CHECK:       latch:
+; CHECK-NEXT:    [[DOTLCSSA:%.*]] = phi i32 [ [[TMP2]], [[INNER]] ]
+; CHECK-NEXT:    [[TMP5]] = add nuw nsw i32 [[LOCAL_6_6]], 1
+; CHECK-NEXT:    [[TMP6:%.*]] = icmp ugt i32 [[LOCAL_6_6]], 276
+; CHECK-NEXT:    br i1 [[TMP6]], label [[RETURN:%.*]], label [[OUTER]]
+; CHECK:       return:
+; CHECK-NEXT:    [[DOTLCSSA_LCSSA:%.*]] = phi i32 [ [[DOTLCSSA]], [[LATCH]] ]
+; CHECK-NEXT:    ret i32 [[DOTLCSSA_LCSSA]]
+;
+entry:
+  br label %outer
+
+outer:
+  %local_6_6 = phi i32 [ 10, %entry ], [ %5, %latch ]
+  %local_4_5 = phi i32 [ 56587, %entry ], [ 0, %latch ]
+  %local_3_4 = phi i32 [ 2, %entry ], [ %local_6_6, %latch ]
+  %.udiv = udiv i32 %local_6_6, 8361
+  br label %inner
+
+inner:
+  %local_7_3 = phi i32 [ 2, %outer ], [ %3, %inner ]
+  %local_4_5.pn = phi i32 [ %local_4_5, %outer ], [ %2, %inner ]
+  %local_3_31 = mul i32 %local_4_5.pn, %.udiv
+  %0 = mul i32 %local_7_3, %.udiv
+  %1 = sub i32 %0, %local_3_4
+  %2 = add i32 %1, %local_3_31
+  %3 = add nuw nsw i32 %local_7_3, 1
+  %4 = icmp ugt i32 %local_7_3, 4
+  br i1 %4, label %latch, label %inner
+
+latch:
+  %.lcssa = phi i32 [ %2, %inner ]
+  %5 = add nuw nsw i32 %local_6_6, 1
+  %6 = icmp ugt i32 %local_6_6, 276
+  br i1 %6, label %return, label %outer
+
+return:
+  %.lcssa.lcssa = phi i32 [ %.lcssa, %latch ]
+  ret i32 %.lcssa.lcssa
+
+}
+