[SCEV] Generate AddRec for trivial and LCSSA phis outside of loop header (WIP)

[bmahjour]

Summary

The current implementation of createAddRecFromPHI() returns immediately if the phi is not in the loop header. This causes some trivial phi nodes to be represented as SCEVUnknown instead of a proper recurrence. This patch improves the result of SCEV for such cases.
For example consider:

define i64 @test1(i32 signext %n, float* %A) {
entry:
  %0 = sext i32 %n to i64
  br label %do.body

do.body:                                          ; preds = %do.body, %entry
  %indvars.iv = phi i64 [ %indvars.iv.next, %do.body ], [ 0, %entry ]
  %arrayidx = getelementptr inbounds float, float* %A, i64 %indvars.iv
  store float 1.000000e+00, float* %arrayidx, align 4
  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
  %cmp = icmp slt i64 %indvars.iv.next, %0
  br i1 %cmp, label %do.body, label %do.end

do.end:                                           ; preds = %do.body
  %add.lcssa.wide = phi i64 [ %indvars.iv.next, %do.body ]
  ret i64 %add.lcssa.wide
}

The SCEV for %add.lcssa.wide is:

--> %add.lcssa.wide U: [1,2147483648) S: [1,2147483648)

This patch makes it generate the following instead:

--> {1,+,1}<nuw><nsw><%do.body> U: [1,2147483648) S: [1,2147483648) --> (1 smax (sext i32 %n to i64)) U: [1,2147483648) S: [1,2147483648)

[Meinersbur]

[suggestion] The scope of the lcssa PHI node and the definition of its value are in different loops, hence calling getSCEVAtScope at the lcssa's scope may simplify the expression. This might even be mandatory since SCEV should be canonical.

[serious] createAddRecFromPHI might be directly called be called getSCEV such that %indvars.iv.next isn't in the cache yet. Therefore the result changes depending on the order in which getSCEV is called.

llvm/lib/Analysis/ScalarEvolution.cpp

5017

Did you consider using getExistingSCEV to check whether it already has been computed?

5326

Why insering this into createAddRecFromPHI and not createNodeForPHI, its only caller?

5332–5335

[serious] Shouldn't this code handle the case? It explicitly mentions the risk of breaking LCSSA, why isn't this the case for your code?

[fhahn]

llvm/lib/Analysis/ScalarEvolution.cpp

5332–5335

I think the problem here is that SCEVExpander does not preserve LCSSA at the moment while expanding expressions and looking through LCSSA would break LCSSA form while expanding SCEVs that would refer to a LCSSA instruction without looking through them.

Getting rid of that restriction was discussed in D68194 as well and I have been working on set of follow up patches that make SCEVExpander preserve LCSSA while expanding. I've put up the WIP patches at D71538 and D71539. There are still a few problems/refactors pending before they are ready though.

[bmahjour]

Address Michael's comments.

[bmahjour]

In D71492#1784331, @Meinersbur wrote:

[suggestion] The scope of the lcssa PHI node and the definition of its value are in different loops, hence calling getSCEVAtScope at the lcssa's scope may simplify the expression. This might even be mandatory since SCEV should be canonical.

If by "lcssa`s scope" you mean the scope at which the lcssa phi instruction appears, then it's not going to help in this case. The scope is the function (outside of any loop). If you pass nullptr to getSCEVAtScope it continues to produce SCEVUnknown.

[serious] createAddRecFromPHI might be directly called be called getSCEV such that %indvars.iv.next isn't in the cache yet. Therefore the result changes depending on the order in which getSCEV is called.

Yes, I was originally concerned that calling getSCEV could cause an infinite loop for cyclic phis, but I gave it more thought and I couldn't come up with a valid IR that can cause the infinite loop. I've changed it to use getSCEV and documented my reasoning for why I don't think a cycle is possible.

llvm/lib/Analysis/ScalarEvolution.cpp

5017

I've replaced this with a call to getSCEV(). Please also see my comment above.

5326

ok, I'll put it at the start of createNodeForPHI.

5332–5335

@fhahn are you considering the other types of non-trivial phis in your patches? eg. %tmp24 = phi i64 [ %tmp14, %bb22 ], [ %tmp14, %bb13 ] in the LIT test bellow.

I think this patch can complement D71539 assuming preservation of LCSSA by SCEVExpander goes in first. For now I can mark this as a child of your patch, unless you'd like to fit this change into yours to handle non-LCSSA trivial phis too.

[fhahn]

llvm/lib/Analysis/ScalarEvolution.cpp

5332–5335

@fhahn are you considering the other types of non-trivial phis in your patches? eg. %tmp24 = phi i64 [ %tmp14, %bb22 ], [ %tmp14, %bb13 ] in the LIT test bellow.

I *think* that should be handled by my patches automatically, as it just lifts the LI.replacementPreservesLCSSAForm restriction below and the PHI you mentioned should be simplified to %tmp14 by SimplifyInstruction.

[Meinersbur]

What is the status of this? Does it depend on D71538?

If D71538 goes in, are this patch and D71539 equivalent?

[fhahn]

In D71492#1879327, @Meinersbur wrote:

What is the status of this? Does it depend on D71538?

If D71538 goes in, are this patch and D71539 equivalent?

I need to find some time to update the linked patches. But I plan to make some progress over the next week

[bmahjour]

This has been superseded by https://reviews.llvm.org/D71539

llvm/lib/Analysis/ScalarEvolution.cpp

const SCEV *ScalarEvolution::createSimpleAffineAddRec(PHINode *PN,
   if (auto *BEInst = dyn_cast<Instruction>(BEValueV))
     if (isLoopInvariant(Accum, L) && isAddRecNeverPoison(BEInst, L))
       (void)getAddRecExpr(getAddExpr(StartVal, Accum), Accum, L, Flags);
 
   return PHISCEV;
 }
 
 const SCEV *ScalarEvolution::createAddRecFromPHI(PHINode *PN) {
+  // If all incoming values of the phi are the same and that unique incoming
+  // value has already been computed, register and return the same SCEV for
+  // that phi.
+  Value *UniqueIncomingValue = PN->hasConstantValue();
+  if (UniqueIncomingValue && !isa<UndefValue>(UniqueIncomingValue) &&
+      ValueExprMap.find_as(UniqueIncomingValue) != ValueExprMap.end()) {
+    const SCEV *Result = ValueExprMap[UniqueIncomingValue];
+    ValueExprMap[SCEVCallbackVH(PN, this)] = Result;
+    return Result;
+  }
+
   const Loop *L = LI.getLoopFor(PN->getParent());
   if (!L || L->getHeader() != PN->getParent())
     return nullptr;
 
   // The loop may have multiple entrances or multiple exits; we can analyze
   // this phi as an addrec if it has a unique entry value and a unique
   // backedge value.
   Value *BEValueV = nullptr, *StartValueV = nullptr;
if (BI && BI->isConditional() &&
         IsAvailableOnEntry(L, DT, getSCEV(RHS), PN->getParent()))
       return createNodeForSelectOrPHI(PN, Cond, LHS, RHS);
   }
 
   return nullptr;
 }
 
 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);
 }
 

llvm/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:

llvm/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
 

llvm/test/Analysis/ScalarEvolution/trivial-phis.ll

+; RUN: opt < %s -analyze -scalar-evolution | FileCheck %s
+
+; CHECK-LABEL @test1
+; CHECK: %add.lcssa.wide = phi i64 [ %indvars.iv.next, %do.body ]
+; CHECK-NEXT: --> {1,+,1}<nuw><nsw><%do.body>
+
+define i64 @test1(i32 signext %n, float* %A) {
+entry:
+  %0 = sext i32 %n to i64
+  br label %do.body
+
+do.body:                                          ; preds = %do.body, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %do.body ], [ 0, %entry ]
+  %arrayidx = getelementptr inbounds float, float* %A, i64 %indvars.iv
+  store float 1.000000e+00, float* %arrayidx, align 4
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %cmp = icmp slt i64 %indvars.iv.next, %0
+  br i1 %cmp, label %do.body, label %do.end
+
+do.end:                                           ; preds = %do.body
+  %add.lcssa.wide = phi i64 [ %indvars.iv.next, %do.body ]
+  ret i64 %add.lcssa.wide
+}
+
+; CHECK-LABEL @test2
+; CHECK: %tmp24 = phi i64 [ %tmp14, %bb22 ], [ %tmp14, %bb13 ]
+; CHECK-NEXT: -->  {1,+,1}<nuw><nsw><%bb13>
+
+define void @test2(i64 %arg, i32* noalias %arg1) {
+bb:
+  %tmp = icmp slt i64 0, %arg
+  br i1 %tmp, label %bb7, label %bb48
+
+bb7:                                              ; preds = %bb
+  br label %bb8
+
+bb8:                                              ; preds = %bb44, %bb7
+  %tmp9 = phi i64 [ 0, %bb7 ], [ %tmp45, %bb44 ]
+  %tmp10 = add nsw i64 %arg, -1
+  %tmp11 = icmp slt i64 1, %tmp10
+  br i1 %tmp11, label %bb12, label %bb43
+
+bb12:                                             ; preds = %bb8
+  br label %bb13
+
+bb13:                                             ; preds = %bb39, %bb12
+  %tmp14 = phi i64 [ 1, %bb12 ], [ %tmp40, %bb39 ]
+  %tmp15 = icmp slt i64 0, %arg
+  br i1 %tmp15, label %bb16, label %bb23
+
+bb16:                                             ; preds = %bb13
+  br label %bb17
+
+bb17:                                             ; preds = %bb19, %bb16
+  %tmp18 = phi i64 [ 0, %bb16 ], [ %tmp20, %bb19 ]
+  br label %bb19
+
+bb19:                                             ; preds = %bb17
+  %tmp20 = add nuw nsw i64 %tmp18, 1
+  %tmp21 = icmp slt i64 %tmp20, %arg
+  br i1 %tmp21, label %bb17, label %bb22
+
+bb22:                                             ; preds = %bb19
+  br label %bb23
+
+bb23:                                             ; preds = %bb22, %bb13
+  %tmp24 = phi i64 [ %tmp14, %bb22 ], [ %tmp14, %bb13 ]
+  %tmp25 = icmp slt i64 0, %arg
+  br i1 %tmp25, label %bb26, label %bb37
+
+bb26:                                             ; preds = %bb23
+  br label %bb27
+
+bb27:                                             ; preds = %bb33, %bb26
+  %tmp28 = phi i64 [ 0, %bb26 ], [ %tmp34, %bb33 ]
+  %tmp29 = mul nsw i64 %tmp9, %arg
+  %tmp30 = getelementptr inbounds i32, i32* %arg1, i64 %tmp24
+  %tmp31 = getelementptr inbounds i32, i32* %tmp30, i64 %tmp29
+  %tmp32 = load i32, i32* %tmp31, align 4
+  br label %bb33
+
+bb33:                                             ; preds = %bb27
+  %tmp34 = add nuw nsw i64 %tmp28, 1
+  %tmp35 = icmp slt i64 %tmp34, %arg
+  br i1 %tmp35, label %bb27, label %bb36
+
+bb36:                                             ; preds = %bb33
+  br label %bb37
+
+bb37:                                             ; preds = %bb36, %bb23
+  %tmp38 = phi i64 [ %tmp24, %bb36 ], [ %tmp24, %bb23 ]
+  br label %bb39
+
+bb39:                                             ; preds = %bb37
+  %tmp40 = add nuw nsw i64 %tmp38, 1
+  %tmp41 = icmp slt i64 %tmp40, %tmp10
+  br i1 %tmp41, label %bb13, label %bb42
+
+bb42:                                             ; preds = %bb39
+  br label %bb43
+
+bb43:                                             ; preds = %bb42, %bb8
+  br label %bb44
+
+bb44:                                             ; preds = %bb43
+  %tmp45 = add nuw nsw i64 %tmp9, 1
+  %tmp46 = icmp slt i64 %tmp45, %arg
+  br i1 %tmp46, label %bb8, label %bb47
+
+bb47:                                             ; preds = %bb44
+  br label %bb48
+
+bb48:                                             ; preds = %bb47, %bb
+  ret void
+}

llvm/test/Transforms/IndVarSimplify/lftr-pr20680.ll

 ; CHECK:       for.inc:
 ; CHECK-NEXT:    [[TMP11:%.*]] = phi i32 [ [[TMP10]], [[FOR_INC_LR_PH]] ], [ [[INC:%.*]], [[FOR_INC]] ]
 ; CHECK-NEXT:    [[INC]] = add nsw i32 [[TMP11]], 1
 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[INC]], 1
 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_INC]], label [[FOR_COND8_FOR_COND2_LOOPEXIT_CRIT_EDGE:%.*]]
 ; CHECK:       for.cond2.for.inc13_crit_edge.us-lcssa.us-lcssa:
 ; CHECK-NEXT:    br label [[FOR_COND2_FOR_INC13_CRIT_EDGE_US_LCSSA]]
 ; CHECK:       for.cond2.for.inc13_crit_edge.us-lcssa:
-; CHECK-NEXT:    [[COND_LCSSA_PH:%.*]] = phi i32 [ [[INDVARS_IV]], [[FOR_COND2_FOR_INC13_CRIT_EDGE_US_LCSSA_US_LCSSA]] ], [ [[INDVARS_IV]], [[FOR_COND2_FOR_INC13_CRIT_EDGE_US_LCSSA_US_LCSSA_US]] ]
 ; CHECK-NEXT:    br label [[FOR_COND2_FOR_INC13_CRIT_EDGE]]
 ; CHECK:       for.cond2.for.inc13_crit_edge:
-; CHECK-NEXT:    [[COND_LCSSA:%.*]] = phi i32 [ [[COND_LCSSA_PH]], [[FOR_COND2_FOR_INC13_CRIT_EDGE_US_LCSSA]] ], [ [[COND_LCSSA_PH_US]], [[FOR_COND2_FOR_INC13_CRIT_EDGE_US_LCSSA_US]] ]
+; CHECK-NEXT:    [[COND_LCSSA:%.*]] = phi i32 [ [[INDVARS_IV]], [[FOR_COND2_FOR_INC13_CRIT_EDGE_US_LCSSA]] ], [ [[COND_LCSSA_PH_US]], [[FOR_COND2_FOR_INC13_CRIT_EDGE_US_LCSSA_US]] ]
 ; CHECK-NEXT:    store i32 [[COND_LCSSA]], i32* @c, align 4
 ; CHECK-NEXT:    br label [[FOR_INC13]]
 ; CHECK:       for.inc13:
 ; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nsw i32 [[INDVARS_IV]], 1
 ; CHECK-NEXT:    [[EXITCOND4:%.*]] = icmp ne i32 [[INDVARS_IV_NEXT]], 0
 ; CHECK-NEXT:    br i1 [[EXITCOND4]], label [[FOR_COND2_PREHEADER]], label [[FOR_END15:%.*]]
 ; CHECK:       for.end15:
 ; CHECK-NEXT:    ret void