Use ValueOffsetPair to enhance value reuse during SCEV expansion.

[wmi]

Summary

This patch is an expansion to http://reviews.llvm.org/D12090.

In D12090, the ExprValueMap was added to reuse existing value during SCEV expansion. However, const folding and sext/zext distribution can make the reuse difficult. I found a common case where the reuse opportunity was missed like this:

Loop lowerbound is intconst 2. Loop upperbound is a complex expr.
%lowerbound = 2
%smax = select ...
%complexexpr = add nsw %i32 %smax, -1
%upperbound = sext i32 %complexexpr i64

When we build SCEV for upperbound, %complexexpr is mapped to SCEV S1: (-1 + X smax Y) <nsw>
%upperbound is mapped to SCEV S2 = sext(S1) = sext((-1 + X smax Y) <nsw>) = (-1 + sext(X smax Y)) <nsw> (sext distribution for SCEV applied here)
Both S1 and S2 will have reuse value entries in ExprValueMap.

Then when we compute loop iteration number based on upperbound SCEV S2 and lowerbound 2: it is S2 - 2 + 1 = -2 + sext(X smax Y) (const folding applied here). Note we only have S1 and S2 in ExprValueMap so we don't have reuse entry for -2 + sext(X smax Y) or sext(X smax Y) so we have to expand "-2 + sext(X smax Y)" literally. When X and Y are also complex expression, it will produce a lot of redundent code.

The patch is proposing to save {Value, Offset} pair instead of just Value in ExprValueMap, and if a SCEV can be splitted into a stripped SCEV part plus an int offset, the mapping "stripped SCEV -> {Value, Offset}" will be added into ExprValueMap, so we won't worry missing reuse opportunity because of const folding.

For %upperbound which is mapped to SCEV S2 = (-1 + sext(X smax Y)), in addition to save mapping "S2 -> %upperbound" into ExprValueMap (Represented as S2 -> {%upperbound, 0}), it will split S2 into two parts: "stripped SCEV S3" + "offset -1". Here S3 is "sext(X smax Y)". Mapping "S3 -> {%upperbound, -1}" will also be saved into ExprValueMap.

Then when scev expander did code expansion for loop iteration number: -2 + sext(X smax Y), it will find out SCEV S3: sext(X smax Y) is in ExprValueMap (The entry: S3 -> {%upperbound, -1}), so it knows to reuse %upperbound - (-1) to represent sext(X smax Y), instead of expanding S3 literally.

[wmi]

Ping.

[sanjoy]

I generally like the idea, but I have some implementation specific comments inline.

include/llvm/Analysis/ScalarEvolution.h

509 ↗

(On Diff #60613)

I think this first part of the explanation can be made easier to
follow if we write in a more explicit way:

Suppose we know S1 expands to V1, and

  S1 = S2 + C_a
  S3 = S2 + C_b

where C_a and C_b are different SCEVConstants.  Then we'd like to
expand S3 as V1 - C_a + C_b.

The second part is fine, but please make it a obvious that it
semantically maps S to {expand(S + Offset), Offset}, that is, if
S is mapped to {V, Offset} then expand(S) is V - Offset.

lib/Analysis/ScalarEvolution.cpp

3392 ↗

(On Diff #60613)

Why not use dyn_cast?

3401 ↗

(On Diff #60613)

Again, please use dyn_cast. For instance, here you can do:

auto *ConstOp = dyn_cast<SCEVConstant>(Op1);
auto *NonConstOp = dyn_cast<SCEVConstant>(Op2);
if (!ConstOp && NonConstOp)
  std::swap(ConstOp, NonConstOp);
if (!ConstOp)
  return {S, nullptr};

However, since SCEV expressions are ordered in complexity, you should only ever need to check the first operand -- if there is a constant operand, then it will be the first one.

Once you've made these simplifications, if the function becomes small enough I'd suggest just inlining it into its caller. If it isn't small enough, please make it a static helper function -- there is no need for this to live in the ScalarEvolution interface.

3413 ↗

(On Diff #60613)

We don't repeat function names in new code.

3441 ↗

(On Diff #60613)

How about:

if (SetVector<ValueOffsetPair> *SV = getSCEVValues(S))
  SV->remove(...);

?

Same below.

3483 ↗

(On Diff #60613)

Use isa<> instead of directly comparing getSCEVType.

[wmi]

include/llvm/Analysis/ScalarEvolution.h

509 ↗

(On Diff #60613)

Thanks for helping to rephrase the comment. It makes the comment much clearer. Comment fixed as suggested.

lib/Analysis/ScalarEvolution.cpp

3392 ↗

(On Diff #60613)

Change it to isa<SCEVAddExpr>(S) instead.

3401 ↗

(On Diff #60613)

Thanks for the suggestion which simplifies the func a lot. I change the function to be static.

3413 ↗

(On Diff #60613)

Fixed.

3441 ↗

(On Diff #60613)

That is better. Fixed.

[wmi]

Sanjoy, thanks for the review. comments addressed.

[wmi]

Ping.

[sanjoy]

lgtm modulo minor stuff (please fix and then directly check in)

lib/Analysis/ScalarEvolution.cpp

3396 ↗

(On Diff #61577)

I think it is better to just cast to SCEVAddExpr to keep the code clear. Also, I'd prefer const auto *.

3470 ↗

(On Diff #61577)

Nit: Stripped -> {V, Offset} to match actual code variable names.

3470 ↗

(On Diff #61577)

Nit: Start with uppercase after period s/it/It/

3472 ↗

(On Diff #61577)

same here.

lib/Analysis/ScalarEvolutionExpander.cpp

1896 ↗

(On Diff #61577)

Can't you just do:

if (Value *Val = FindValueInExprValueMap(S, At).first)
  ScalarEvolution::ValueOffsetPair VO = FindValueInExprValueMap(S, At);

llvm/trunk/include/llvm/Analysis/ScalarEvolution.h

private:
     ///
     typedef DenseMap<const SCEV *, bool> HasRecMapType;
 
     /// This is a cache to record whether a SCEV contains any scAddRecExpr.
     HasRecMapType HasRecMap;
 
     /// The typedef for ExprValueMap.
     ///
-    typedef DenseMap<const SCEV *, SetVector<Value *>> ExprValueMapType;
+    typedef std::pair<Value *, ConstantInt *> ValueOffsetPair;
+    typedef DenseMap<const SCEV *, SetVector<ValueOffsetPair>> ExprValueMapType;
 
     /// ExprValueMap -- This map records the original values from which
     /// the SCEV expr is generated from.
+    ///
+    /// We want to represent the mapping as SCEV -> ValueOffsetPair instead
+    /// of SCEV -> Value:
+    /// Suppose we know S1 expands to V1, and
+    ///  S1 = S2 + C_a
+    ///  S3 = S2 + C_b
+    /// where C_a and C_b are different SCEVConstants. Then we'd like to
+    /// expand S3 as V1 - C_a + C_b instead of expanding S2 literally.
+    /// It is helpful when S2 is a complex SCEV expr.
+    ///
+    /// In order to do that, we represent ExprValueMap as a mapping from
+    /// SCEV to ValueOffsetPair. We will save both S1->{V1, 0} and
+    /// S2->{V1, C_a} into the map when we create SCEV for V1. When S3
+    /// is expanded, it will first expand S2 to V1 - C_a because of
+    /// S2->{V1, C_a} in the map, then expand S3 to V1 - C_a + C_b.
+    ///
+    /// Note: S->{V, Offset} in the ExprValueMap means S can be expanded
+    /// to V - Offset.
     ExprValueMapType ExprValueMap;
 
     /// The typedef for ValueExprMap.
     ///
     typedef DenseMap<SCEVCallbackVH, const SCEV *, DenseMapInfo<Value *> >
       ValueExprMapType;
 
     /// This is a cache of the values we have analyzed so far.
public:
     Type *getEffectiveSCEVType(Type *Ty) const;
 
     /// Return true if the SCEV is a scAddRecExpr or it contains
     /// scAddRecExpr. The result will be cached in HasRecMap.
     ///
     bool containsAddRecurrence(const SCEV *S);
 
     /// Return the Value set from which the SCEV expr is generated.
-    SetVector<Value *> *getSCEVValues(const SCEV *S);
+    SetVector<ValueOffsetPair> *getSCEVValues(const SCEV *S);
 
     /// Erase Value from ValueExprMap and ExprValueMap.
     void eraseValueFromMap(Value *V);
 
     /// Return a SCEV expression for the full generality of the specified
     /// expression.
     const SCEV *getSCEV(Value *V);
 

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

private:
 
     /// \brief Expand a SCEVAddExpr with a pointer type into a GEP
     /// instead of using ptrtoint+arithmetic+inttoptr.
     Value *expandAddToGEP(const SCEV *const *op_begin,
                           const SCEV *const *op_end,
                           PointerType *PTy, Type *Ty, Value *V);
 
     /// \brief Find a previous Value in ExprValueMap for expand.
-    Value *FindValueInExprValueMap(const SCEV *S, const Instruction *InsertPt);
+    ScalarEvolution::ValueOffsetPair
+    FindValueInExprValueMap(const SCEV *S, const Instruction *InsertPt);
 
     Value *expand(const SCEV *S);
 
     /// \brief Insert code to directly compute the specified SCEV expression
     /// into the program.  The inserted code is inserted into the SCEVExpander's
     /// current insertion point. If a type is specified, the result will be
     /// expanded to have that type, with a cast if necessary.
     Value *expandCodeFor(const SCEV *SH, Type *Ty = nullptr);

llvm/trunk/lib/Analysis/ScalarEvolution.cpp

bool ScalarEvolution::containsAddRecurrence(const SCEV *S) {
 
   FindAddRecurrence F;
   SCEVTraversal<FindAddRecurrence> ST(F);
   ST.visitAll(S);
   HasRecMap.insert({S, F.FoundOne});
   return F.FoundOne;
 }
 
-/// Return the Value set from S.
-SetVector<Value *> *ScalarEvolution::getSCEVValues(const SCEV *S) {
+/// Try to split a SCEVAddExpr into a pair of {SCEV, ConstantInt}.
+/// If \p S is a SCEVAddExpr and is composed of a sub SCEV S' and an
+/// offset I, then return {S', I}, else return {\p S, nullptr}.
+static std::pair<const SCEV *, ConstantInt *> splitAddExpr(const SCEV *S) {
+  const auto *Add = dyn_cast<SCEVAddExpr>(S);
+  if (!Add)
+    return {S, nullptr};
+
+  if (Add->getNumOperands() != 2)
+    return {S, nullptr};
+
+  auto *ConstOp = dyn_cast<SCEVConstant>(Add->getOperand(0));
+  if (!ConstOp)
+    return {S, nullptr};
+
+  return {Add->getOperand(1), ConstOp->getValue()};
+}
+
+/// Return the ValueOffsetPair set for \p S. \p S can be represented
+/// by the value and offset from any ValueOffsetPair in the set.
+SetVector<ScalarEvolution::ValueOffsetPair> *
+ScalarEvolution::getSCEVValues(const SCEV *S) {
   ExprValueMapType::iterator SI = ExprValueMap.find_as(S);
   if (SI == ExprValueMap.end())
     return nullptr;
 #ifndef NDEBUG
   if (VerifySCEVMap) {
     // Check there is no dangling Value in the set returned.
     for (const auto &VE : SI->second)
-      assert(ValueExprMap.count(VE));
+      assert(ValueExprMap.count(VE.first));
   }
 #endif
   return &SI->second;
 }
 
-/// Erase Value from ValueExprMap and ExprValueMap.  If ValueExprMap.erase(V) is
-/// not used together with forgetMemoizedResults(S), eraseValueFromMap should be
-/// used instead to ensure whenever V->S is removed from ValueExprMap, V is also
-/// removed from the set of ExprValueMap[S].
+/// Erase Value from ValueExprMap and ExprValueMap. ValueExprMap.erase(V)
+/// cannot be used separately. eraseValueFromMap should be used to remove
+/// V from ValueExprMap and ExprValueMap at the same time.
 void ScalarEvolution::eraseValueFromMap(Value *V) {
   ValueExprMapType::iterator I = ValueExprMap.find_as(V);
   if (I != ValueExprMap.end()) {
     const SCEV *S = I->second;
-    SetVector<Value *> *SV = getSCEVValues(S);
-    // Remove V from the set of ExprValueMap[S]
-    if (SV)
-      SV->remove(V);
+    // Remove {V, 0} from the set of ExprValueMap[S]
+    if (SetVector<ValueOffsetPair> *SV = getSCEVValues(S))
+      SV->remove({V, nullptr});
+
+    // Remove {V, Offset} from the set of ExprValueMap[Stripped]
+    const SCEV *Stripped;
+    ConstantInt *Offset;
+    std::tie(Stripped, Offset) = splitAddExpr(S);
+    if (Offset != nullptr) {
+      if (SetVector<ValueOffsetPair> *SV = getSCEVValues(Stripped))
+        SV->remove({V, Offset});
+    }
     ValueExprMap.erase(V);
   }
 }
 
 /// Return an existing SCEV if it exists, otherwise analyze the expression and
 /// create a new one.
 const SCEV *ScalarEvolution::getSCEV(Value *V) {
   assert(isSCEVable(V->getType()) && "Value is not SCEVable!");
 
   const SCEV *S = getExistingSCEV(V);
   if (S == nullptr) {
     S = createSCEV(V);
     // During PHI resolution, it is possible to create two SCEVs for the same
     // V, so it is needed to double check whether V->S is inserted into
-    // ValueExprMap before insert S->V into ExprValueMap.
+    // ValueExprMap before insert S->{V, 0} into ExprValueMap.
     std::pair<ValueExprMapType::iterator, bool> Pair =
         ValueExprMap.insert({SCEVCallbackVH(V, this), S});
-    if (Pair.second)
-      ExprValueMap[S].insert(V);
+    if (Pair.second) {
+      ExprValueMap[S].insert({V, nullptr});
+
+      // If S == Stripped + Offset, add Stripped -> {V, Offset} into
+      // ExprValueMap.
+      const SCEV *Stripped = S;
+      ConstantInt *Offset = nullptr;
+      std::tie(Stripped, Offset) = splitAddExpr(S);
+      // If stripped is SCEVUnknown, don't bother to save
+      // Stripped -> {V, offset}. It doesn't simplify and sometimes even
+      // increase the complexity of the expansion code.
+      // If V is GetElementPtrInst, don't save Stripped -> {V, offset}
+      // because it may generate add/sub instead of GEP in SCEV expansion.
+      if (Offset != nullptr && !isa<SCEVUnknown>(Stripped) &&
+          !isa<GetElementPtrInst>(V))
+        ExprValueMap[Stripped].insert({V, Offset});
+    }
   }
   return S;
 }
 
 const SCEV *ScalarEvolution::getExistingSCEV(Value *V) {
   assert(isSCEVable(V->getType()) && "Value is not SCEVable!");
 
   ValueExprMapType::iterator I = ValueExprMap.find_as(V);
   if (I != ValueExprMap.end()) {
     const SCEV *S = I->second;
     if (checkValidity(S))
       return S;
+    eraseValueFromMap(V);
     forgetMemoizedResults(S);
-    ValueExprMap.erase(I);
   }
   return nullptr;
 }
 
 /// Return a SCEV corresponding to -V = -1*V
 ///
 const SCEV *ScalarEvolution::getNegativeSCEV(const SCEV *V,
                                              SCEV::NoWrapFlags Flags) {
if (It != ValueExprMap.end()) {
       // by createNodeForPHI, or it's a single-value PHI. In the first case,
       // additional loop trip count information isn't going to change anything.
       // In the second case, createNodeForPHI will perform the necessary
       // updates on its own when it gets to that point. In the third, we do
       // want to forget the SCEVUnknown.
       if (!isa<PHINode>(I) ||
           !isa<SCEVUnknown>(Old) ||
           (I != PN && Old == SymName)) {
+        eraseValueFromMap(It->first);
         forgetMemoizedResults(Old);
-        ValueExprMap.erase(It);
       }
     }
 
     PushDefUseChildren(I, Worklist);
   }
 }
 
 namespace {
if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(BEValue)) {
         }
       }
     }
 
     // Remove the temporary PHI node SCEV that has been inserted while intending
     // to create an AddRecExpr for this PHI node. We can not keep this temporary
     // as it will prevent later (possibly simpler) SCEV expressions to be added
     // to the ValueExprMap.
-    ValueExprMap.erase(PN);
+    eraseValueFromMap(PN);
   }
 
   return nullptr;
 }
 
 // Checks if the SCEV S is available at BB.  S is considered available at BB
 // if S can be materialized at BB without introducing a fault.
 static bool IsAvailableOnEntry(const Loop *L, DominatorTree &DT, const SCEV *S,
while (!Worklist.empty()) {
 
         // SCEVUnknown for a PHI either means that it has an unrecognized
         // structure, or it's a PHI that's in the progress of being computed
         // by createNodeForPHI.  In the former case, additional loop trip
         // count information isn't going to change anything. In the later
         // case, createNodeForPHI will perform the necessary updates on its
         // own when it gets to that point.
         if (!isa<PHINode>(I) || !isa<SCEVUnknown>(Old)) {
+          eraseValueFromMap(It->first);
           forgetMemoizedResults(Old);
-          ValueExprMap.erase(It);
         }
         if (PHINode *PN = dyn_cast<PHINode>(I))
           ConstantEvolutionLoopExitValue.erase(PN);
       }
 
       PushDefUseChildren(I, Worklist);
     }
   }
void ScalarEvolution::forgetLoop(const Loop *L) {
   while (!Worklist.empty()) {
     Instruction *I = Worklist.pop_back_val();
     if (!Visited.insert(I).second)
       continue;
 
     ValueExprMapType::iterator It =
       ValueExprMap.find_as(static_cast<Value *>(I));
     if (It != ValueExprMap.end()) {
+      eraseValueFromMap(It->first);
       forgetMemoizedResults(It->second);
-      ValueExprMap.erase(It);
       if (PHINode *PN = dyn_cast<PHINode>(I))
         ConstantEvolutionLoopExitValue.erase(PN);
     }
 
     PushDefUseChildren(I, Worklist);
   }
 
   // Forget all contained loops too, to avoid dangling entries in the
void ScalarEvolution::forgetValue(Value *V) {
   while (!Worklist.empty()) {
     I = Worklist.pop_back_val();
     if (!Visited.insert(I).second)
       continue;
 
     ValueExprMapType::iterator It =
       ValueExprMap.find_as(static_cast<Value *>(I));
     if (It != ValueExprMap.end()) {
+      eraseValueFromMap(It->first);
       forgetMemoizedResults(It->second);
-      ValueExprMap.erase(It);
       if (PHINode *PN = dyn_cast<PHINode>(I))
         ConstantEvolutionLoopExitValue.erase(PN);
     }
 
     PushDefUseChildren(I, Worklist);
   }
 }
 

llvm/trunk/lib/Analysis/ScalarEvolutionExpander.cpp

Value *SCEVExpander::expandCodeFor(const SCEV *SH, Type *Ty) {
   if (Ty) {
     assert(SE.getTypeSizeInBits(Ty) == SE.getTypeSizeInBits(SH->getType()) &&
            "non-trivial casts should be done with the SCEVs directly!");
     V = InsertNoopCastOfTo(V, Ty);
   }
   return V;
 }
 
-Value *SCEVExpander::FindValueInExprValueMap(const SCEV *S,
-                                             const Instruction *InsertPt) {
-  SetVector<Value *> *Set = SE.getSCEVValues(S);
+ScalarEvolution::ValueOffsetPair
+SCEVExpander::FindValueInExprValueMap(const SCEV *S,
+  SetVector<ScalarEvolution::ValueOffsetPair> *Set = SE.getSCEVValues(S);
   // If the expansion is not in CanonicalMode, and the SCEV contains any
   // sub scAddRecExpr type SCEV, it is required to expand the SCEV literally.
   if (CanonicalMode || !SE.containsAddRecurrence(S)) {
     // If S is scConstant, it may be worse to reuse an existing Value.
     if (S->getSCEVType() != scConstant && Set) {
       // Choose a Value from the set which dominates the insertPt.
       // insertPt should be inside the Value's parent loop so as not to break
       // the LCSSA form.
-      for (auto const &Ent : *Set) {
+      for (auto const &VOPair : *Set) {
+        Value *V = VOPair.first;
+        ConstantInt *Offset = VOPair.second;
         Instruction *EntInst = nullptr;
-        if (Ent && isa<Instruction>(Ent) &&
-            (EntInst = cast<Instruction>(Ent)) &&
-            S->getType() == Ent->getType() &&
+        if (V && isa<Instruction>(V) && (EntInst = cast<Instruction>(V)) &&
+            S->getType() == V->getType() &&
             EntInst->getFunction() == InsertPt->getFunction() &&
             SE.DT.dominates(EntInst, InsertPt) &&
             (SE.LI.getLoopFor(EntInst->getParent()) == nullptr ||
-             SE.LI.getLoopFor(EntInst->getParent())->contains(InsertPt))) {
-          return Ent;
-        }
-      }
-    }
-  }
-  return nullptr;
+             SE.LI.getLoopFor(EntInst->getParent())->contains(InsertPt)))
+          return {V, Offset};
+  return {nullptr, nullptr};
 }
 
 // The expansion of SCEV will either reuse a previous Value in ExprValueMap,
 // or expand the SCEV literally. Specifically, if the expansion is in LSRMode,
 // and the SCEV contains any sub scAddRecExpr type SCEV, it will be expanded
 // literally, to prevent LSR's transformed SCEV from being reverted. Otherwise,
 // the expansion will try to reuse Value from ExprValueMap, and only when it
 // fails, expand the SCEV literally.
Value *SCEVExpander::expand(const SCEV *S) {
   auto I = InsertedExpressions.find(std::make_pair(S, InsertPt));
   if (I != InsertedExpressions.end())
     return I->second;
 
   SCEVInsertPointGuard Guard(Builder, this);
   Builder.SetInsertPoint(InsertPt);
 
   // Expand the expression into instructions.
-  Value *V = FindValueInExprValueMap(S, InsertPt);
+  ScalarEvolution::ValueOffsetPair VO = FindValueInExprValueMap(S, InsertPt);
+  Value *V = VO.first;
 
   if (!V)
     V = visit(S);
+  else if (VO.second) {
+    V = Builder.CreateSub(V, VO.second);
+  }
 
   // Remember the expanded value for this SCEV at this location.
   //
   // This is independent of PostIncLoops. The mapped value simply materializes
   // the expression at this insertion point. If the mapped value happened to be
   // a postinc expansion, it could be reused by a non-postinc user, but only if
   // its insertion point was already at the head of the loop.
   InsertedExpressions[std::make_pair(S, InsertPt)] = V;
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))
+  if (Value *Val = FindValueInExprValueMap(S, At).first)
     return Val;
 
   // There is potential to make this significantly smarter, but this simple
   // heuristic already gets some interesting cases.
 
   // Can not find suitable value.
   return nullptr;
 }

llvm/trunk/test/Analysis/ScalarEvolution/scev-expander-existing-value-offset.ll

+; RUN: opt < %s -loop-vectorize -force-vector-interleave=1 -force-vector-width=4 -S |FileCheck %s
+; SCEV expansion uses existing value or value + offset to reduce duplicate code expansion so foo should only generate one select inst after loop vectorization.
+; CHECK-LABEL: @foo(
+; CHECK: select
+; CHECK-NOT: select
+
+@ySrcL = common global i8* null, align 8
+@smL = common global i32 0, align 4
+
+define void @foo(i32 %rwL, i32 %kL, i32 %xfL) {
+entry:
+  %sub = add nsw i32 %rwL, -1
+  %shr = ashr i32 %xfL, 6
+  %cmp.i = icmp slt i32 %sub, %shr
+  %cond.i = select i1 %cmp.i, i32 %sub, i32 %shr
+  %cmp6 = icmp sgt i32 %cond.i, %kL
+  br i1 %cmp6, label %for.body.lr.ph, label %for.end
+
+for.body.lr.ph:                                   ; preds = %entry
+  %tmp = load i8*, i8** @ySrcL, align 8
+  %tmp1 = sext i32 %kL to i64
+  %tmp2 = sext i32 %cond.i to i64
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %for.body.lr.ph
+  %indvars.iv = phi i64 [ %tmp1, %for.body.lr.ph ], [ %indvars.iv.next, %for.body ]
+  %reduct.07 = phi i32 [ 0, %for.body.lr.ph ], [ %add, %for.body ]
+  %arrayidx = getelementptr inbounds i8, i8* %tmp, i64 %indvars.iv
+  %tmp3 = load i8, i8* %arrayidx, align 1
+  %conv = zext i8 %tmp3 to i32
+  %add = add nsw i32 %conv, %reduct.07
+  %indvars.iv.next = add nsw i64 %indvars.iv, 1
+  %cmp = icmp slt i64 %indvars.iv.next, %tmp2
+  br i1 %cmp, label %for.body, label %for.end.loopexit
+
+for.end.loopexit:                                 ; preds = %for.body
+  %add.lcssa = phi i32 [ %add, %for.body ]
+  br label %for.end
+
+for.end:                                          ; preds = %for.end.loopexit, %entry
+  %reduct.0.lcssa = phi i32 [ 0, %entry ], [ %add.lcssa, %for.end.loopexit ]
+  store i32 %reduct.0.lcssa, i32* @smL, align 4
+  ret void
+}
+; RUN: opt < %s -loop-vectorize -force-vector-interleave=1 -force-vector-width=4 -S |FileCheck %s
+; SCEV expansion uses existing value or value + offset to reduce duplicate code expansion so foo should only generate one select inst after loop vectorization.
+; CHECK-LABEL: @foo(
+; CHECK: select
+; CHECK-NOT: select
+
+@ySrcL = common global i8* null, align 8
+@smL = common global i32 0, align 4
+
+define void @foo(i32 %rwL, i32 %kL, i32 %xfL) {
+entry:
+  %sub = add nsw i32 %rwL, -1
+  %shr = ashr i32 %xfL, 6
+  %cmp.i = icmp slt i32 %sub, %shr
+  %cond.i = select i1 %cmp.i, i32 %sub, i32 %shr
+  %cmp6 = icmp sgt i32 %cond.i, %kL
+  br i1 %cmp6, label %for.body.lr.ph, label %for.end
+
+for.body.lr.ph:                                   ; preds = %entry
+  %tmp = load i8*, i8** @ySrcL, align 8
+  %tmp1 = sext i32 %kL to i64
+  %tmp2 = sext i32 %cond.i to i64
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %for.body.lr.ph
+  %indvars.iv = phi i64 [ %tmp1, %for.body.lr.ph ], [ %indvars.iv.next, %for.body ]
+  %reduct.07 = phi i32 [ 0, %for.body.lr.ph ], [ %add, %for.body ]
+  %arrayidx = getelementptr inbounds i8, i8* %tmp, i64 %indvars.iv
+  %tmp3 = load i8, i8* %arrayidx, align 1
+  %conv = zext i8 %tmp3 to i32
+  %add = add nsw i32 %conv, %reduct.07
+  %indvars.iv.next = add nsw i64 %indvars.iv, 1
+  %cmp = icmp slt i64 %indvars.iv.next, %tmp2
+  br i1 %cmp, label %for.body, label %for.end.loopexit
+
+for.end.loopexit:                                 ; preds = %for.body
+  %add.lcssa = phi i32 [ %add, %for.body ]
+  br label %for.end
+
+for.end:                                          ; preds = %for.end.loopexit, %entry
+  %reduct.0.lcssa = phi i32 [ 0, %entry ], [ %add.lcssa, %for.end.loopexit ]
+  store i32 %reduct.0.lcssa, i32* @smL, align 4
+  ret void
+}