[SCEV] Fix runtime error caused by ValueOffsetPair

[wmi]

Summary

The patch is to fix the bug in https://llvm.org/bugs/show_bug.cgi?id=28705

Previously in SCEVExpander::findExistingExpansion, we returned the value part of the ValueOffsetPair returned by FindValueInExprValueMap directly no matter whether the offset is zero or not. I mistakenly thought SCEVExpander::findExistingExpansion was only used to check whether there was an existing value to be reused (This is true for all its uses in lib/Analysis/ScalarEvolutionExpander.cpp). I missed the fact that SCEVExpander::findExistingExpansion was also used in IndVarSimplify::expandSCEVIfNeeded and the value returned was used to replace exit value of induction variable in IndVarSimplify. It caused IndVarSimplify used a wrong value as the exit value of induction variable (The correct value should be "value - offset" expr).

The fix is to add an OnlyCheckIsNull param for SCEVExpander::findExistingExpansion. If OnlyCheckIsNull is false and ValueOffsetPair returned by FindValueInExprValueMap contains a non-zero offset, we will return nullptr. So that IndVarSimplify::expandSCEVIfNeeded will continue to use SCEVExpander::expandCodeFor to do the expansion.

I don't want SCEVExpander::findExistingExpansion to insert the "Value - Offset" expr based on ValueOffsetPair because it can insert the expr inside the loop. SCEVExpander::expandCodeFor contains the logic to choose a better insert point.

[sanjoy]

include/llvm/Analysis/ScalarEvolutionExpander.h

283

Hi Wei,

I'm not sure this is the best interface -- it still is too easy to make mistakes. I think there should be two entry points here (which can share code as appropriate):

• Value *getExactExistingExpansion : if this returns non-null, then we know that the return value is the exact expansion. We'll use this in IndVarSimplify (and potentially other places that don't want to generate additional code).
• Optional<ValueOffsetPair> getRelatedExistingExpansion: if this returns non- None, then we know we can codegen the ValueOffsetPair into a suitable expansion.

The first can be implemented in terms of the latter.

[wmi]

include/llvm/Analysis/ScalarEvolutionExpander.h

283

That is a good suggestion. Thanks.

[wmi]

Address Sanjoy's comments.

[sanjoy]

Just to be clear, you're going to squash this with rL276136 and check in the result?

include/llvm/Analysis/ScalarEvolutionExpander.h

273

s/func/function

Also, I'm not sure if we need to mention getRelatedExistingExpansion etc. here. I'd just directly state that it gives an expansion for S and nothing more.

281

s/find/find the/ or s/find/find a/
s/func/function/

281

We don't use \brief in new code.

283

s/If only return is non-None/If this returns a non-None value/

lib/Analysis/ScalarEvolutionExpander.cpp

1991

I don't think you need the hasValue. Applies to all the places where you've used the Optional as a boolean.

test/Analysis/ScalarEvolution/pr28705.ll

3

Why do you need debug-only?

[wmi]

Just to be clear, you're going to squash this with rL276136 and check in the result.

I can checkin them consecutively. which way do you think is better?

include/llvm/Analysis/ScalarEvolutionExpander.h

273

I wanted to emphasize their difference since they have similar names but different usages.

I simplified the comment to: /// Try to find existing LLVM IR value for S available at the point At.

281

Fixed.

283

Fixed.

lib/Analysis/ScalarEvolutionExpander.cpp

1991

Oh, that looks better. Thanks.

test/Analysis/ScalarEvolution/pr28705.ll

3

That is a careless mistake. Removed.

[wmi]

Address Sanjoy's comment.

[sanjoy]

lgtm

test/Analysis/ScalarEvolution/pr28705.ll

14

This is totally optional, but if I'd clean up the variable names a little bit before checkin. E.g. s/%I641.03128/%iv, s/ %DB.sroa.9.03127/%iv2 etc.

[wmi]

test/Analysis/ScalarEvolution/pr28705.ll

14

Fixed. Thanks.

[wmi]

Fix variable names in test.

include/llvm/Analysis/ScalarEvolutionExpander.h

#endif
     bool isInsertedInstruction(Instruction *I) const {
       return InsertedValues.count(I) || InsertedPostIncValues.count(I);
     }
 
     void setChainedPhi(PHINode *PN) { ChainedPhis.insert(PN); }
 
     /// \brief Try to find LLVM IR value for S available at the point At.
     ///
     /// L is a hint which tells in which loop to look for the suitable value.
     /// On success return value which is equivalent to the expanded S at point
     /// At. Return nullptr if value was not found.
     ///
     /// Note that this function does not perform an exhaustive search. I.e if it
     /// didn't find any value it does not mean that there is no such value.
-    Value *findExistingExpansion(const SCEV *S, const Instruction *At, Loop *L);
+    ///
+    /// \p OnlyCheckIsNull is used to indicate that we only care whether there
+    /// is an existing value to be reused, and will not insert the return value
+    /// into the IR.
+    Value *findExistingExpansion(const SCEV *S, const Instruction *At, Loop *L,
+                                 bool OnlyCheckIsNull = true);
 
   private:
     LLVMContext &getContext() const { return SE.getContext(); }
 
     /// \brief Recursive helper function for isHighCostExpansion.
     bool isHighCostExpansionHelper(const SCEV *S, Loop *L,
                                    const Instruction *At,
                                    SmallPtrSetImpl<const SCEV *> &Processed);

lib/Analysis/ScalarEvolutionExpander.cpp

if (OrigPhiRef->getType() != Phi->getType()) {
       NewIV = Builder.CreateTruncOrBitCast(OrigPhiRef, Phi->getType(), IVName);
     }
     Phi->replaceAllUsesWith(NewIV);
     DeadInsts.emplace_back(Phi);
   }
   return NumElim;
 }
 
-Value *SCEVExpander::findExistingExpansion(const SCEV *S,
-                                           const Instruction *At, Loop *L) {
+Value *SCEVExpander::findExistingExpansion(const SCEV *S, const Instruction *At,
+                                           Loop *L, bool OnlyCheckIsNull) {
   using namespace llvm::PatternMatch;
 
   SmallVector<BasicBlock *, 4> ExitingBlocks;
   L->getExitingBlocks(ExitingBlocks);
 
   // Look for suitable value in simple conditions at the loop exits.
   for (BasicBlock *BB : ExitingBlocks) {
     ICmpInst::Predicate Pred;
if (SE.getSCEV(LHS) == S && SE.DT.dominates(LHS, At))
       return LHS;
 
     if (SE.getSCEV(RHS) == S && SE.DT.dominates(RHS, At))
       return RHS;
   }
 
   // Use expand's logic which is used for reusing a previous Value in
   // ExprValueMap.
-  if (Value *Val = FindValueInExprValueMap(S, At).first)
-    return Val;
+  ScalarEvolution::ValueOffsetPair VO = FindValueInExprValueMap(S, At);
+  // When VO.second is not zero, the returned value VO.first doesn't equal
+  // to S and can only be used when OnlyCheckIsNull is true.
+  if (!VO.second || OnlyCheckIsNull)
+    return VO.first;
 
   // There is potential to make this significantly smarter, but this simple
   // heuristic already gets some interesting cases.
 
   // Can not find suitable value.
   return nullptr;
 }
 
if (!ExitingBB)
       return true;
 
     // At the beginning of this function we already tried to find existing value
     // for plain 'S'. Now try to lookup 'S + 1' since it is common pattern
     // involving division. This is just a simple search heuristic.
     if (!At)
       At = &ExitingBB->back();
     if (!findExistingExpansion(
             SE.getAddExpr(S, SE.getConstant(S->getType(), 1)), At, L))
       return true;
   }
 
   // HowManyLessThans uses a Max expression whenever the loop is not guarded by
   // the exit condition.
   if (isa<SCEVSMaxExpr>(S) || isa<SCEVUMaxExpr>(S))
     return true;
 

lib/Transforms/Scalar/IndVarSimplify.cpp

 };
 }
 
 Value *IndVarSimplify::expandSCEVIfNeeded(SCEVExpander &Rewriter, const SCEV *S,
                                           Loop *L, Instruction *InsertPt,
                                           Type *ResultTy) {
   // Before expanding S into an expensive LLVM expression, see if we can use an
   // already existing value as the expansion for S.
-  if (Value *ExistingValue = Rewriter.findExistingExpansion(S, InsertPt, L))
+  if (Value *ExistingValue =
+          Rewriter.findExistingExpansion(S, InsertPt, L, false))
     if (ExistingValue->getType() == ResultTy)
       return ExistingValue;
 
   // We didn't find anything, fall back to using SCEVExpander.
   return Rewriter.expandCodeFor(S, ResultTy, InsertPt);
 }
 
 //===----------------------------------------------------------------------===//

test/Analysis/ScalarEvolution/pr28705.ll

+; PR28705
+; RUN: opt < %s -indvars -debug-only=indvars -S | FileCheck %s
+
+; Check IndVarSimplify replaces the exitval use of the induction var "%inc.i.i"
+; with "%.sroa.speculated + 1".
+;
+; CHECK-LABEL: @foo(
+; CHECK: %[[EXIT:.+]] = sub i32 %.sroa.speculated, -1
+; CHECK: %DB.sroa.9.0.lcssa = phi i32 [ 1, %entry ], [ %[[EXIT]], %loopexit ]
+;
+define void @foo(i32 %sub.ptr.div.i, i8* %ref.i1174) local_unnamed_addr {
+entry:
+  %cmp.i1137 = icmp ugt i32 %sub.ptr.div.i, 3
+  %.sroa.speculated = select i1 %cmp.i1137, i32 3, i32 %sub.ptr.div.i
+  %cmp6483126 = icmp eq i32 %.sroa.speculated, 0
+  br i1 %cmp6483126, label %XZ.exit, label %for.body650.lr.ph
+
+for.body650.lr.ph:
+  br label %for.body650
+
+loopexit:
+  %inc.i.i.lcssa = phi i32 [ %inc.i.i, %for.body650 ]
+  br label %XZ.exit
+
+XZ.exit:
+  %DB.sroa.9.0.lcssa = phi i32 [ 1, %entry ], [ %inc.i.i.lcssa, %loopexit ]
+  br label %end
+
+for.body650:
+  %I641.03128 = phi i32 [ 0, %for.body650.lr.ph ], [ %inc655, %for.body650 ]
+  %DB.sroa.9.03127 = phi i32 [ 1, %for.body650.lr.ph ], [ %inc.i.i, %for.body650 ]
+  %arrayidx.i.i1105 = getelementptr inbounds i8, i8* %ref.i1174, i32 %DB.sroa.9.03127
+  store i8 7, i8* %arrayidx.i.i1105, align 1
+  %inc.i.i = add i32 %DB.sroa.9.03127, 1
+  %inc655 = add i32 %I641.03128, 1
+  %cmp648 = icmp eq i32 %inc655, %.sroa.speculated
+  br i1 %cmp648, label %loopexit, label %for.body650
+
+end:
+  ret void
+}