[SCEV] Don't bother preserving LCSSA in SCEV

[mkazantsev]

Summary

Preserving LCSSA of IR should be responsibility of transform passes. We should not try to
keep SCEV in LCSSA form because because of this we can lose some transform opportunitites.

[mkazantsev]

lib/Analysis/ScalarEvolution.cpp

5346–5347

Basically, I guess that we could just have deleted this check for same effect. Is there a reason to keep it? What's bad about breaking LCSSA in SCEV?

[fhahn]

LCSSA form is a property of the IR. As we do not change the IR here, there is no way we could destroy the LCSSA form of the underlying IR. If transformations use the extra info to destroy LCSSA form, they should be fixed.

LGTM, but please wait a bit with committing, in case the other reviewers have additional comments or I missed something.

lib/Analysis/ScalarEvolution.cpp

5342

This comment is obsolete now.

test/Transforms/LoopStrengthReduce/funclet.ll

48

not really related to this patch, but it is not really clear what gets checked here and elsewhere. I think it would be great if we could add a clear test case where this change is beneficial.

[sanjoy]

I'm okay with the direction, but I'm also worried that this breaks some subtle invariant between SCEV and SCEVExpander. Have you tried bootstrapping clang with this change to see if that shakes out any issues?

[mkazantsev]

I'll run some extensive testing to see if it's breaking something. If yes, we have bugs to fix ahead.

[mkazantsev]

My fuzz testing has detected LCSSA breaches. My conviction is that it's a right way to go, and the failures should be fixed where they are dont, but we can't merge it before the bugs are fixed there.

[mkazantsev]

Looks like there is a lot of places in code that expect that... :(

[fhahn]

In D57568#1395934, @mkazantsev wrote:

Looks like there is a lot of places in code that expect that... :(

:(

lib/Analysis/ScalarEvolution.cpp

 
 const SCEV *ScalarEvolution::createNodeForPHI(PHINode *PN) {
   if (const SCEV *S = createAddRecFromPHI(PN))
     return S;
 
   if (const SCEV *S = createNodeFromSelectLikePHI(PN))
     return S;
 
   // If the PHI has a single incoming value, follow that value, unless the
   // PHI's incoming blocks are in a different loop, in which case doing so
   // risks breaking LCSSA form. Instcombine would normally zap these, but
   // it doesn't have DominatorTree information, so it may miss cases.
   if (Value *V = SimplifyInstruction(PN, {getDataLayout(), &TLI, &DT, &AC}))
-    if (LI.replacementPreservesLCSSAForm(PN, V))
-      return getSCEV(V);
 
   // If it's not a loop phi, we can't handle it yet.
   return getUnknown(PN);
 }
 
 const SCEV *ScalarEvolution::createNodeForSelectOrPHI(Instruction *I,
                                                       Value *Cond,
                                                       Value *TrueVal,

test/Analysis/ScalarEvolution/solve-quadratic-i1.ll

 ; CHECK-NEXT:   -->  {3,+,1}<%b1> U: [3,6) S: [3,6)           Exits: 5                LoopDispositions: { %b1: Computable }
 ; CHECK-NEXT:   %v3 = add i16 %v0, %v2
 ; CHECK-NEXT:   -->  {3,+,4,+,1}<%b1> U: full-set S: full-set         Exits: 12               LoopDispositions: { %b1: Computable }
 ; CHECK-NEXT:   %v4 = and i16 %v3, 1
 ; CHECK-NEXT:   -->  (zext i1 {true,+,false,+,true}<%b1> to i16) U: [0,2) S: [0,2)            Exits: 0                LoopDispositions: { %b1: Computable }
 ; CHECK-NEXT:   %v6 = add nuw nsw i32 %v1, 1
 ; CHECK-NEXT:   -->  {4,+,1}<nuw><nsw><%b1> U: [4,7) S: [4,7)         Exits: 6                LoopDispositions: { %b1: Computable }
 ; CHECK-NEXT:   %v7 = phi i32 [ %v1, %b1 ]
-; CHECK-NEXT:   -->  %v7 U: [3,6) S: [3,6)
+; CHECK-NEXT:   --> {3,+,1}<nuw><nsw><%b1> U: [3,6) S: [3,6)
 ; CHECK-NEXT:   %v8 = phi i16 [ %v3, %b1 ]
-; CHECK-NEXT:   -->  %v8 U: full-set S: full-set
+; CHECK-NEXT:   --> {3,+,4,+,1}<%b1> U: full-set S: full-set
 ; CHECK-NEXT: Determining loop execution counts for: @f1
 ; CHECK-NEXT: Loop %b3: <multiple exits> Unpredictable backedge-taken count.
 ; CHECK-NEXT: Loop %b3: Unpredictable max backedge-taken count.
 ; CHECK-NEXT: Loop %b3: Unpredictable predicated backedge-taken count.
 ; CHECK-NEXT: Loop %b1: backedge-taken count is 2
 ; CHECK-NEXT: Loop %b1: max backedge-taken count is 2
 ; CHECK-NEXT: Loop %b1: Predicated backedge-taken count is 2
 ; CHECK-NEXT:  Predicates:

test/Analysis/ScalarEvolution/solve-quadratic-overflow.ll

 ; RUN: opt -analyze -scalar-evolution -S < %s | FileCheck %s
 
 ; The exit value from this loop was originally calculated as 0.
 ; The actual exit condition is 256*256 == 0 (in i16).
 
 ; CHECK: Printing analysis 'Scalar Evolution Analysis' for function 'f0':
 ; CHECK-NEXT: Classifying expressions for: @f0
 ; CHECK-NEXT:   %v1 = phi i16 [ 0, %b0 ], [ %v2, %b1 ]
 ; CHECK-NEXT:   -->  {0,+,-1}<%b1> U: [-255,1) S: [-255,1)            Exits: -255            LoopDispositions: { %b1: Computable }
 ; CHECK-NEXT:   %v2 = add i16 %v1, -1
 ; CHECK-NEXT:   -->  {-1,+,-1}<%b1> U: [-256,0) S: [-256,0)           Exits: -256            LoopDispositions: { %b1: Computable }
 ; CHECK-NEXT:   %v3 = mul i16 %v2, %v2
 ; CHECK-NEXT:   -->  {1,+,3,+,2}<%b1> U: full-set S: full-set         Exits: 0               LoopDispositions: { %b1: Computable }
 ; CHECK-NEXT:   %v5 = phi i16 [ %v2, %b1 ]
-; CHECK-NEXT:   -->  %v5 U: [-256,0) S: [-256,0)
+; CHECK-NEXT:   --> {-1,+,-1}<%b1> U: [-256,0) S: [-256,0)
 ; CHECK-NEXT:   %v6 = phi i16 [ %v3, %b1 ]
-; CHECK-NEXT:   -->  %v6 U: full-set S: full-set
+; CHECK-NEXT:   --> {1,+,3,+,2}<%b1> U: full-set S: full-set
 ; CHECK-NEXT:   %v7 = sext i16 %v5 to i32
-; CHECK-NEXT:   -->  (sext i16 %v5 to i32) U: [-256,0) S: [-256,0)
+; CHECK-NEXT:   --> {-1,+,-1}<nsw><%b1> U: [-256,0) S: [-256,0)
 ; CHECK-NEXT: Determining loop execution counts for: @f0
 ; CHECK-NEXT: Loop %b1: backedge-taken count is 255
 ; CHECK-NEXT: Loop %b1: max backedge-taken count is 255
 ; CHECK-NEXT: Loop %b1: Predicated backedge-taken count is 255
 ; CHECK-NEXT:  Predicates:
 ; CHECK-EMPTY:
 ; CHECK-NEXT: Loop %b1: Trip multiple is 256
 

test/Transforms/LoopStrengthReduce/funclet.ll

iter:                                             ; preds = %loop_body
   br i1 undef, label %unwind_out, label %loop_body
 
 unwind_out:                                       ; preds = %iter, %loop_body
   cleanupret from %cleanuppadi4.i.i.i unwind to caller
 }
 
 ; CHECK-LABEL: define void @f(
 ; CHECK: cleanuppad within none []
-; CHECK-NEXT: ptrtoint i8* %phi2 to i32
+; CHECK-NEXT: br
 
 define void @g() personality i32 (...)* @_except_handler3 {
 entry:
   br label %throw
 
 throw:                                            ; preds = %throw, %entry
   %tmp96 = getelementptr inbounds i8, i8* undef, i32 1
   invoke void @reserve()

 iter:                                             ; preds = %loop_body
   %tmp101 = getelementptr inbounds i8, i8* %tmp99, i32 1
   br i1 undef, label %unwind_out, label %loop_body
 }
 
 ; CHECK-LABEL: define void @g(
 ; CHECK: blah:
 ; CHECK-NEXT: catchpad within %cs []
-; CHECK-NEXT: ptrtoint i8* %phi2 to i32
+; CHECK-NEXT: br
 
 
 define void @h() personality i32 (...)* @_except_handler3 {
 entry:
   br label %throw
 
 throw:                                            ; preds = %throw, %entry
   %tmp96 = getelementptr inbounds i8, i8* undef, i32 1

 iter:                                             ; preds = %loop_body
   %tmp101 = getelementptr inbounds i8, i8* %tmp99, i32 1
   br i1 undef, label %unwind_out, label %loop_body
 }
 
 ; CHECK-LABEL: define void @h(
 ; CHECK: blug:
 ; CHECK: catchpad within %cs []
-; CHECK-NEXT: ptrtoint i8* %phi2 to i32
+; CHECK-NEXT: br
 
 define void @i() personality i32 (...)* @_except_handler3 {
 entry:
   br label %throw
 
 throw:                                            ; preds = %throw, %entry
   %tmp96 = getelementptr inbounds i8, i8* undef, i32 1
   invoke void @reserve()
iter:                                             ; preds = %loop_body
   %tmp101 = getelementptr inbounds i8, i8* %tmp99, i32 1
   br i1 undef, label %unwind_out, label %loop_body
 
 unwind_out:                                       ; preds = %iter, %loop_body
   unreachable
 }
 
 ; CHECK-LABEL: define void @i(
-; CHECK: ptrtoint i8* %phi2 to i32
+; CHECK-NOT: ptrtoint i8* %phi2 to i32
 
 define void @test1(i32* %b, i32* %c) personality i32 (...)* @__CxxFrameHandler3 {
 entry:
   br label %for.cond
 
 for.cond:                                         ; preds = %for.inc, %entry
   %d.0 = phi i32* [ %b, %entry ], [ %incdec.ptr, %for.inc ]
   invoke void @external(i32* %d.0)