[LCSSA] Compute SCEV of LCSSA phi if original instruction had SCEV

[nikic]

Summary

The backstory here is that the LCSSA invalidation we perform here is not really necessary from a SCEV perspective. However, other code may rely on the fact that invalidating only LCSSA phi nodes is sufficient for transforms like loop peeling (see https://reviews.llvm.org/D149331#4398582 for more details).

However, performing invalidation during LCSSA construction also means that SCEV expansion (which may need to construct LCSSA) can invalidate SCEV, which is somewhat unexpected and code may not be prepared to deal with it (see the added test case, reported at https://reviews.llvm.org/D149435#4428219).

Instead of invalidating SCEV, ensure that the LCSSA phi node also has cached SCEV if the original instruction did. This means that later invalidation of LCSSA phi nodes will work as expected. This should avoid both the above issues and be more efficient.

[uabelho]

I've verified that this fixes the problem I saw in https://reviews.llvm.org/D149435#4428219

Thanks!

[nikic]

Ping

[fhahn]

LGTM, thanks!

llvm/include/llvm/Analysis/ScalarEvolution.h

public:
   /// Return true if the SCEV expression contains a Value that has been
   /// optimised out and is now a nullptr.
   bool containsErasedValue(const SCEV *S) const;
 
   /// Return a SCEV expression for the full generality of the specified
   /// expression.
   const SCEV *getSCEV(Value *V);
 
+  /// Return an existing SCEV for V if there is one, otherwise return nullptr.
+  const SCEV *getExistingSCEV(Value *V);
+
   const SCEV *getConstant(ConstantInt *V);
   const SCEV *getConstant(const APInt &Val);
   const SCEV *getConstant(Type *Ty, uint64_t V, bool isSigned = false);
   const SCEV *getLosslessPtrToIntExpr(const SCEV *Op, unsigned Depth = 0);
   const SCEV *getPtrToIntExpr(const SCEV *Op, Type *Ty);
   const SCEV *getTruncateExpr(const SCEV *Op, Type *Ty, unsigned Depth = 0);
   const SCEV *getVScale(Type *Ty);
   const SCEV *getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth = 0);
private:
   void forgetMemoizedResultsImpl(const SCEV *S);
 
   /// Iterate over instructions in \p Worklist and their users. Erase entries
   /// from ValueExprMap and collect SCEV expressions in \p ToForget
   void visitAndClearUsers(SmallVectorImpl<Instruction *> &Worklist,
                           SmallPtrSetImpl<Instruction *> &Visited,
                           SmallVectorImpl<const SCEV *> &ToForget);
 
-  /// Return an existing SCEV for V if there is one, otherwise return nullptr.
-  const SCEV *getExistingSCEV(Value *V);
-
   /// Erase Value from ValueExprMap and ExprValueMap.
   void eraseValueFromMap(Value *V);
 
   /// Insert V to S mapping into ValueExprMap and ExprValueMap.
   void insertValueToMap(Value *V, const SCEV *S);
 
   /// Return false iff given SCEV contains a SCEVUnknown with NULL value-
   /// pointer.

llvm/lib/Transforms/Utils/LCSSA.cpp

while (!Worklist.empty()) {
 
     SmallVector<PHINode *, 16> AddedPHIs;
     SmallVector<PHINode *, 8> PostProcessPHIs;
 
     SmallVector<PHINode *, 4> LocalInsertedPHIs;
     SSAUpdater SSAUpdate(&LocalInsertedPHIs);
     SSAUpdate.Initialize(I->getType(), I->getName());
 
-    // Force re-computation of I, as some users now need to use the new PHI
-    // node.
-    if (SE)
-      SE->forgetValue(I);
-
     // Insert the LCSSA phi's into all of the exit blocks dominated by the
     // value, and add them to the Phi's map.
+    bool HasSCEV = SE && SE->isSCEVable(I->getType()) &&
+                   SE->getExistingSCEV(I) != nullptr;
     for (BasicBlock *ExitBB : ExitBlocks) {
       if (!DT.dominates(DomNode, DT.getNode(ExitBB)))
         continue;
 
       // If we already inserted something for this BB, don't reprocess it.
       if (SSAUpdate.HasValueForBlock(ExitBB))
         continue;
       PHINode *PN = PHINode::Create(I->getType(), PredCache.size(ExitBB),
for (BasicBlock *ExitBB : ExitBlocks) {
       // create PHIs in such an exit block, we are also inserting PHIs into L2's
       // header. This could break LCSSA form for L2 because these inserted PHIs
       // can also have uses outside of L2. Remember all PHIs in such situation
       // as to revisit than later on. FIXME: Remove this if indirectbr support
       // into LoopSimplify gets improved.
       if (auto *OtherLoop = LI.getLoopFor(ExitBB))
         if (!L->contains(OtherLoop))
           PostProcessPHIs.push_back(PN);
+
+      // If we have a cached SCEV for the original instruction, make sure the
+      // new LCSSA phi node is also cached. This makes sures that BECounts
+      // based on it will be invalidated when the LCSSA phi node is invalidated,
+      // which some passes rely on.
+      if (HasSCEV)
+        SE->getSCEV(PN);
     }
 
     // Rewrite all uses outside the loop in terms of the new PHIs we just
     // inserted.
     for (Use *UseToRewrite : UsesToRewrite) {
       Instruction *User = cast<Instruction>(UseToRewrite->getUser());
       BasicBlock *UserBB = User->getParent();
 

llvm/test/Transforms/IndVarSimplify/lcssa-preservation.ll

 ; CHECK-NEXT:    br label [[LOOP_1_OUTER]]
 ; CHECK:       loop.1.outer:
 ; CHECK-NEXT:    br label [[LOOP_1:%.*]]
 ; CHECK:       loop.1:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sle i64 [[A:%.*]], 2546175499358690212
 ; CHECK-NEXT:    [[CMP_EXT:%.*]] = zext i1 [[CMP]] to i8
 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP_1]], label [[LOOP_2_HEADER_PREHEADER:%.*]]
 ; CHECK:       loop.2.header.preheader:
-; CHECK-NEXT:    [[CMP_LCSSA:%.*]] = phi i1 [ [[CMP]], [[LOOP_1]] ]
+; CHECK-NEXT:    [[CMP_LCSSA2:%.*]] = phi i1 [ [[CMP]], [[LOOP_1]] ]
 ; CHECK-NEXT:    [[CMP_EXT_LCSSA:%.*]] = phi i8 [ [[CMP_EXT]], [[LOOP_1]] ]
 ; CHECK-NEXT:    br label [[LOOP_2_HEADER_OUTER:%.*]]
 ; CHECK:       loop.2.header.outer:
 ; CHECK-NEXT:    br label [[LOOP_2_HEADER:%.*]]
 ; CHECK:       loop.2.header:
 ; CHECK-NEXT:    switch i8 [[CMP_EXT_LCSSA]], label [[LOOP_1_LOOPEXIT:%.*]] [
 ; CHECK-NEXT:    i8 -1, label [[LOOP_2_LATCH:%.*]]
 ; CHECK-NEXT:    i8 1, label [[LOOP_2_LATCH]]
 ; CHECK-NEXT:    i8 4, label [[LOOP_2_HEADER]]
 ; CHECK-NEXT:    ]
 ; CHECK:       loop.2.latch:
-; CHECK-NEXT:    [[CMP_TRUNC_LCSSA1:%.*]] = phi i1 [ [[CMP_LCSSA]], [[LOOP_2_HEADER]] ], [ [[CMP_LCSSA]], [[LOOP_2_HEADER]] ]
+; CHECK-NEXT:    [[CMP_TRUNC_LCSSA1:%.*]] = phi i1 [ [[CMP_LCSSA2]], [[LOOP_2_HEADER]] ], [ [[CMP_LCSSA2]], [[LOOP_2_HEADER]] ]
 ; CHECK-NEXT:    call void @use(i1 [[CMP_TRUNC_LCSSA1]])
 ; CHECK-NEXT:    br label [[LOOP_2_HEADER_OUTER]]
 ;
 entry:
   br label %loop.1
 
 loop.1:
   %p.1 = phi i1 [ 0 , %entry ], [ %p.1, %loop.1 ], [ %p.2, %loop.2.header ]
loop.2.header:
   i8 4, label %loop.2.header
   ]
 
 loop.2.latch:
   call void @use(i1 %cmp.trunc)
   br label %loop.2.header
 }
 
+define void @D149435(i16 %arg) {
+; CHECK-LABEL: @D149435(
+; CHECK-NEXT:    br label [[LOOP1:%.*]]
+; CHECK:       loop1:
+; CHECK-NEXT:    [[FR:%.*]] = freeze i16 [[ARG:%.*]]
+; CHECK-NEXT:    [[ARRAYIDX_IDX:%.*]] = shl i16 [[FR]], 1
+; CHECK-NEXT:    [[OR:%.*]] = or i16 [[ARRAYIDX_IDX]], 1
+; CHECK-NEXT:    br i1 false, label [[LOOP1]], label [[LOOP2_PREHEADER:%.*]]
+; CHECK:       loop2.preheader:
+; CHECK-NEXT:    [[FR_LCSSA:%.*]] = phi i16 [ [[FR]], [[LOOP1]] ]
+; CHECK-NEXT:    [[OR_LCSSA:%.*]] = phi i16 [ [[OR]], [[LOOP1]] ]
+; CHECK-NEXT:    [[UMAX:%.*]] = call i16 @llvm.umax.i16(i16 [[OR_LCSSA]], i16 2)
+; CHECK-NEXT:    [[TMP1:%.*]] = add i16 [[UMAX]], -1
+; CHECK-NEXT:    [[TMP2:%.*]] = shl i16 [[FR_LCSSA]], 1
+; CHECK-NEXT:    [[TMP3:%.*]] = sub i16 [[TMP1]], [[TMP2]]
+; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq i16 [[TMP3]], 0
+; CHECK-NEXT:    [[UMAX1:%.*]] = call i16 @llvm.umax.i16(i16 [[ARG]], i16 2)
+; CHECK-NEXT:    [[TMP5:%.*]] = sub i16 [[UMAX1]], [[ARG]]
+; CHECK-NEXT:    [[TMP6:%.*]] = icmp eq i16 [[TMP5]], 0
+; CHECK-NEXT:    br label [[LOOP2:%.*]]
+; CHECK:       loop2:
+; CHECK-NEXT:    br i1 [[TMP4]], label [[TRAP:%.*]], label [[FOR_BODY8:%.*]]
+; CHECK:       for.body8:
+; CHECK-NEXT:    br i1 [[TMP6]], label [[TRAP]], label [[LOOP2_LATCH:%.*]]
+; CHECK:       loop2.latch:
+; CHECK-NEXT:    br i1 false, label [[LOOP2]], label [[TRAP]]
+; CHECK:       trap:
+; CHECK-NEXT:    unreachable
+;
+  br label %loop1
+
+loop1:
+  %fr = freeze i16 %arg
+  %arrayidx.idx = shl i16 %fr, 1
+  %or = or i16 %arrayidx.idx, 1
+  br i1 false, label %loop1, label %loop2.preheader
+
+loop2.preheader:
+  br label %loop2
+
+loop2:
+  %iv = phi i16 [ %iv.next, %loop2.latch ], [ 0, %loop2.preheader ]
+  %add = add i16 %or, %iv
+  %cmp = icmp ugt i16 %add, 1
+  br i1 %cmp, label %trap, label %for.body8
+
+for.body8:
+  %add2 = add i16 %arg, %iv
+  %cmp2 = icmp ugt i16 %add2, 1
+  br i1 %cmp2, label %trap, label %loop2.latch
+
+loop2.latch:
+  %iv.next = add i16 %iv, 1
+  br i1 false, label %loop2, label %trap
+
+trap:
+  unreachable
+}
+
 declare void @use(i1)