[SCEV] Teach computeSCEVAtScope benefit from one-input Phi. PR39673

[mkazantsev]

Summary

SCEV does not propagate arguments through one-input Phis for sake of LCSSA
form preservation. So whenever computeSCEVAtScope is asked about such Phi,
it will not go ahead and try to analyze its input. However it is possible that when
an this input leaves the loop through LCSSA Phi, it is a provable constant.

This patch teaches computeSCEVAtScope about this case. We can generalize it
later, but so far we can only replace LCSSA Phis with their constant loop-exiting
values.

[mkazantsev]

Ping?

[reames]

LGTM

I'm fine with this landing, since the patch is an obvious improvement. However, I have to admit I don't understand the interaction between LCSSA and SCEV here. Why does SCEV need to care that a phi might be a LCSSA phi? They seem orthogonal. Maybe *some particular caller* might need to care, but that seems like a different issue?

[uabelho]

Hi,

Should we/someone push this?

I don't know, but I haven't seen much/any activity from mkazantsev in llvm
for some time now, so I'm not sure if someone else should commit this change?

It does seem to fix the regression described in
https://bugs.llvm.org/show_bug.cgi?id=39673
but myself I've no idea if the change makes sense or not.

llvm/trunk/lib/Analysis/ScalarEvolution.cpp

if (Instruction *I = dyn_cast<Instruction>(SU->getValue())) {
             // 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);
             if (RV) return getSCEV(RV);
           }
         }
+
+        // If there is a single-input Phi, evaluate it at our scope. If we can
+        // prove that this replacement does not break LCSSA form, use new value.
+        if (PN->getNumOperands() == 1) {
+          const SCEV *Input = getSCEV(PN->getOperand(0));
+          const SCEV *InputAtScope = getSCEVAtScope(Input, L);
+          // TODO: We can generalize it using LI.replacementPreservesLCSSAForm,
+          // for the simplest case just support constants.
+          if (isa<SCEVConstant>(InputAtScope)) return InputAtScope;
+        }
       }
 
       // Okay, this is an expression that we cannot symbolically evaluate
       // into a SCEV.  Check to see if it's possible to symbolically evaluate
       // the arguments into constants, and if so, try to constant propagate the
       // result.  This is particularly useful for computing loop exit values.
       if (CanConstantFold(I)) {
         SmallVector<Constant *, 4> Operands;

llvm/trunk/test/Transforms/IndVarSimplify/pr39673.ll

 ; CHECK-NEXT:    [[K2:%.*]] = phi i16 [ [[K2_ADD:%.*]], [[LOOP2]] ], [ 182, [[LOOP2_PREHEADER]] ]
 ; CHECK-NEXT:    [[L2:%.*]] = phi i16 [ [[L2_ADD:%.*]], [[LOOP2]] ], [ 0, [[LOOP2_PREHEADER]] ]
 ; CHECK-NEXT:    [[L2_ADD]] = add nuw nsw i16 [[L2]], 1
 ; CHECK-NEXT:    tail call void @foo(i16 [[K2]])
 ; CHECK-NEXT:    [[K2_ADD]] = add nuw nsw i16 [[K2]], 1
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i16 [[L2_ADD]], 2
 ; CHECK-NEXT:    br i1 [[CMP2]], label [[LOOP2]], label [[LOOP2_END:%.*]]
 ; CHECK:       loop2.end:
-; CHECK-NEXT:    [[K2_ADD_LCSSA:%.*]] = phi i16 [ [[K2_ADD]], [[LOOP2]] ]
-; CHECK-NEXT:    ret i16 [[K2_ADD_LCSSA]]
+; CHECK-NEXT:    ret i16 184
 ;
 entry:
   br label %loop1
 
 loop1:                                           ; preds = %entry, %loop1
   %k1 = phi i16 [ 180, %entry ], [ %k1.add, %loop1 ]
   %l1 = phi i16 [ 0, %entry ], [ %l1.add, %loop1 ]
   %k1.add = add nuw nsw i16 %k1, 1