This is an archive of the discontinued LLVM Phabricator instance.

[SCEV] Enable verification in LoopPM
ClosedPublic

Authored by nikic on Feb 25 2022, 2:52 AM.

Details

Summary

Currently, we hardly ever actually run SCEV verification, even in tests with -verify-scev. This is because the NewPM LPM does not verify SCEV. The reason for this is that SCEV verification can actually change the result of subsequent SCEV queries, which means that you see different transformations depending on whether verification is enabled or not.

To allow verification in the LPM, this limits verification to BECounts that have actually been cached. It will not calculate new BECounts.

BackedgeTakenInfo::getExact() is still not entirely readonly, it still calls getUMinFromMismatchedTypes(). But I hope that this is not problematic in the same way. (This could be avoided by performing the umin in the other SCEV instance, but this would require duplicating some of the code.)

Diff Detail

Event Timeline

nikic created this revision.Feb 25 2022, 2:52 AM
nikic requested review of this revision.Feb 25 2022, 2:52 AM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 25 2022, 2:52 AM
nikic added a comment.Feb 25 2022, 3:38 AM

The pr35406.ll failure can be reduced to this:

define i32 @test() {
entry:
  br label %loop1

loop1:
  br i1 false, label %loop2, label %loop1.latch

loop2:
  %iv = phi i32 [ 0, %loop1 ], [ %iv.next, %loop2 ]
  %iv.next = add nuw nsw i32 %iv, 1
  %cmp = icmp ne i32 %iv.next, 1
  br i1 %cmp, label %loop1.latch, label %loop2

loop1.latch:
  br label %loop1
}

; opt -indvars

define i32 @test() {
entry:
  br label %loop1

loop1:                                            ; preds = %loop1.latch, %entry
  br i1 true, label %loop2.preheader, label %loop1.latch

loop2.preheader:                                  ; preds = %loop1
  br label %loop2

loop2:                                            ; preds = %loop2.preheader, %loop2
  br i1 true, label %loop1.latch.loopexit, label %loop2

loop1.latch.loopexit:                             ; preds = %loop2
  br label %loop1.latch

loop1.latch:                                      ; preds = %loop1.latch.loopexit, %loop1
  br label %loop1
}

In this case the BECount of the inner loop legitimately changes from 1 to 0, and this isn't wrong, because the loop is unreachable.

We make use of the fact that the loop is unreachable due to https://github.com/llvm/llvm-project/blob/20a093e2bc310283ec216ab47fddb68f0bdaa6f0/llvm/lib/Analysis/ScalarEvolution.cpp#L11024-L11027, introduced in D98706. And apparently this is already a known issue, with a variant reported in: https://github.com/llvm/llvm-project/issues/50523

I'm not really sure what to do about that. I think the options are a) give up on BECount verification entirely, b) drop that isImpliedCond() change, as I think it is of very limited practical value (the next SimplifyCFG will eliminate that code entirely, so it is irrelevant how we optimize it) or c) try to limit BECount verification to loops that are reachable, while taking into account constant branches.

Why can't we just give up verification of unreachable loops/blocks?

mkazantsev resigned from this revision.Mar 4 2022, 12:13 AM
Herald added a project: Restricted Project. · View Herald TranscriptMar 4 2022, 12:13 AM
nikic edited the summary of this revision. (Show Details)Mar 4 2022, 12:48 AM
nikic edited reviewers, added: fhahn, asbirlea, aeubanks; removed: mkazantsev.
reames accepted this revision.Mar 5 2022, 12:46 PM

LGTM

(I'm assuming that the unreachable loop issue was resolved. I think I remember seeing that change land at least.)

This revision is now accepted and ready to land.Mar 5 2022, 12:46 PM
This revision was landed with ongoing or failed builds.Mar 7 2022, 12:46 AM
This revision was automatically updated to reflect the committed changes.