[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 ↗

(On Diff #66000)

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 ↗

(On Diff #66000)

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

274 ↗

(On Diff #66081)

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.

282 ↗

(On Diff #66081)

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

282 ↗

(On Diff #66081)

We don't use \brief in new code.

284 ↗

(On Diff #66081)

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

lib/Analysis/ScalarEvolutionExpander.cpp

1998 ↗

(On Diff #66081)

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

2 ↗

(On Diff #66081)

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

274 ↗

(On Diff #66081)

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.

282 ↗

(On Diff #66081)

Fixed.

284 ↗

(On Diff #66081)

Fixed.

lib/Analysis/ScalarEvolutionExpander.cpp

1998 ↗

(On Diff #66081)

Oh, that looks better. Thanks.

test/Analysis/ScalarEvolution/pr28705.ll

2 ↗

(On Diff #66081)

That is a careless mistake. Removed.

[wmi]

Address Sanjoy's comment.

[sanjoy]

lgtm

test/Analysis/ScalarEvolution/pr28705.ll

13 ↗

(On Diff #67064)

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

13 ↗

(On Diff #67064)

Fixed. Thanks.

[wmi]

Fix variable names in test.

llvm/trunk/include/llvm/Analysis/ScalarEvolutionExpander.h

 //===---- llvm/Analysis/ScalarEvolutionExpander.h - SCEV Exprs --*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file defines the classes used to generate code from scalar expressions.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_SCALAREVOLUTIONEXPANDER_H
 #define LLVM_ANALYSIS_SCALAREVOLUTIONEXPANDER_H
 
+#include "llvm/ADT/Optional.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
 #include "llvm/Analysis/ScalarEvolutionNormalization.h"
 #include "llvm/Analysis/TargetFolder.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/ValueHandle.h"
 #include <set>
 
 namespace llvm {
#endif
     /// \brief Return true if the specified instruction was inserted by the code
     /// rewriter.  If so, the client should not modify the instruction.
     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.
+    /// Try to find existing LLVM IR value for S available at the point At.
+    Value *getExactExistingExpansion(const SCEV *S, const Instruction *At,
+                                     Loop *L);
+
+    /// Try to find the ValueOffsetPair for S. The function is mainly
+    /// used to check whether S can be expanded cheaply.
+    /// If this returns a non-None value, we know we can codegen the
+    /// `ValueOffsetPair` into a suitable expansion identical with S
+    /// so that S can be expanded cheaply.
     ///
     /// 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);
+    ///
+    Optional<ScalarEvolution::ValueOffsetPair>
+    getRelatedExistingExpansion(const SCEV *S, const Instruction *At, Loop *L);
 
   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);

llvm/trunk/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,
+Value *SCEVExpander::getExactExistingExpansion(const SCEV *S,
                                                const Instruction *At, Loop *L) {
+  Optional<ScalarEvolution::ValueOffsetPair> VO =
+      getRelatedExistingExpansion(S, At, L);
+  if (VO && VO.getValue().second == nullptr)
+    return VO.getValue().first;
+  return nullptr;
+}
+
+Optional<ScalarEvolution::ValueOffsetPair>
+SCEVExpander::getRelatedExistingExpansion(const SCEV *S, const Instruction *At,
+                                          Loop *L) {
   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;
     Instruction *LHS, *RHS;
     BasicBlock *TrueBB, *FalseBB;
 
     if (!match(BB->getTerminator(),
                m_Br(m_ICmp(Pred, m_Instruction(LHS), m_Instruction(RHS)),
                     TrueBB, FalseBB)))
       continue;
 
     if (SE.getSCEV(LHS) == S && SE.DT.dominates(LHS, At))
-      return LHS;
+      return ScalarEvolution::ValueOffsetPair(LHS, nullptr);
 
     if (SE.getSCEV(RHS) == S && SE.DT.dominates(RHS, At))
-      return RHS;
+      return ScalarEvolution::ValueOffsetPair(RHS, nullptr);
   }
 
   // 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);
+  if (VO.first)
+    return VO;
 
   // There is potential to make this significantly smarter, but this simple
   // heuristic already gets some interesting cases.
 
   // Can not find suitable value.
-  return nullptr;
+  return None;
 }
 
 bool SCEVExpander::isHighCostExpansionHelper(
     const SCEV *S, Loop *L, const Instruction *At,
     SmallPtrSetImpl<const SCEV *> &Processed) {
 
   // If we can find an existing value for this scev avaliable at the point "At"
   // then consider the expression cheap.
-  if (At && findExistingExpansion(S, At, L) != nullptr)
+  if (At && getRelatedExistingExpansion(S, At, L))
     return false;
 
   // Zero/One operand expressions
   switch (S->getSCEVType()) {
   case scUnknown:
   case scConstant:
     return false;
   case scTruncate:
if (auto *UDivExpr = dyn_cast<SCEVUDivExpr>(S)) {
     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(
+    if (!getRelatedExistingExpansion(
             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;

llvm/trunk/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.getExactExistingExpansion(S, InsertPt, L))
     if (ExistingValue->getType() == ResultTy)
       return ExistingValue;
 
   // We didn't find anything, fall back to using SCEVExpander.
   return Rewriter.expandCodeFor(S, ResultTy, InsertPt);
 }
 
 //===----------------------------------------------------------------------===//

llvm/trunk/test/Analysis/ScalarEvolution/pr28705.ll

+; PR28705
+; RUN: opt < %s -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:
+  %iv = phi i32 [ 0, %for.body650.lr.ph ], [ %inc655, %for.body650 ]
+  %iv2 = phi i32 [ 1, %for.body650.lr.ph ], [ %inc.i.i, %for.body650 ]
+  %arrayidx.i.i1105 = getelementptr inbounds i8, i8* %ref.i1174, i32 %iv2
+  store i8 7, i8* %arrayidx.i.i1105, align 1
+  %inc.i.i = add i32 %iv2, 1
+  %inc655 = add i32 %iv, 1
+  %cmp648 = icmp eq i32 %inc655, %.sroa.speculated
+  br i1 %cmp648, label %loopexit, label %for.body650
+
+end:
+  ret void
+}