Try to reuse existing value during SCEV expansion

[qcolombet]

Hi Wei,

I leave the actual review to Andy and Hal as I do not know the internals of this API at all.

That being said, the changes itself look strange to me and if we are just looking at making CSE and such, I would just calling the related passes at the right places.

Anyway, here are a couple of high level comments.

Thanks,
-Quentin

lib/Analysis/ScalarEvolutionExpander.cpp

1649 ↗

(On Diff #32339)

This seems for the users of the SCEV API to know that when all those conditions apply, it needs to create a new value.

lib/Transforms/Vectorize/LoopVectorize.cpp

2602 ↗

(On Diff #32339)

The formatting of the comment looks strange and the comment itself is hard to digest.
Could you rephrase?
Also, don’t we have a split method directly on the DT?
Having to explicitly add the block to DT seems error prone to me.

[wmi]

Quentin, thanks for the review.

That being said, the changes itself look strange to me and if we are just looking at making CSE and such, I would just calling the related passes at the right places.

Yes, if CSE can fully clean up the redundencies, that way looks simpler and cleaner. I am not sure which is the best way to fix the problem. The patch is proposed just as an alternative I can think of to fully clean up such redundencies. I expect people having better understanding of SCEV to provide some suggestions here.

lib/Analysis/ScalarEvolutionExpander.cpp

1649 ↗

(On Diff #32339)

Yes, that is a precise description about the use of the code above.

lib/Transforms/Vectorize/LoopVectorize.cpp

2602 ↗

(On Diff #32339)

Sorry, I will fix the comment.

The comment is trying to say the SCEV expansion may query the DT at the same time when the func createEmptyLoop generates new bypass blocks. This is before InnerLoopVectorizer::updateAnalysis update the whole DT so we need to maintain the DT incrementally. I don't know the common way to do that so I just move the code originally in InnerLoopVectorizer::updateAnalysis forward.

[hfinkel]

In D12090#226980, @wmi wrote:

Quentin, thanks for the review.

That being said, the changes itself look strange to me and if we are just looking at making CSE and such, I would just calling the related passes at the right places.

Yes, if CSE can fully clean up the redundencies, that way looks simpler and cleaner. I am not sure which is the best way to fix the problem. The patch is proposed just as an alternative I can think of to fully clean up such redundencies. I expect people having better understanding of SCEV to provide some suggestions here.

It seems that CSE will only handle the more-trivial cases. If constant folding, or reassociation, etc. has changed the form of the expressions, then CSE won't help. I think handling at least some of this in SCEV does make sense.

That having been said, adding a Value* and the enum to every SCEV adds an overhead to every SCEV created, even though most of them are never expanded. Would it be better to keep this information on the side (in a DenseMap or similar)?

[wmi]

In D12090#234842, @hfinkel wrote:

In D12090#226980, @wmi wrote:

Quentin, thanks for the review.

That being said, the changes itself look strange to me and if we are just looking at making CSE and such, I would just calling the related passes at the right places.

Yes, if CSE can fully clean up the redundencies, that way looks simpler and cleaner. I am not sure which is the best way to fix the problem. The patch is proposed just as an alternative I can think of to fully clean up such redundencies. I expect people having better understanding of SCEV to provide some suggestions here.

It seems that CSE will only handle the more-trivial cases. If constant folding, or reassociation, etc. has changed the form of the expressions, then CSE won't help. I think handling at least some of this in SCEV does make sense.

That having been said, adding a Value* and the enum to every SCEV adds an overhead to every SCEV created, even though most of them are never expanded. Would it be better to keep this information on the side (in a DenseMap or similar)?

Yes, keeping the information in a map looks better. I will change it.

[wmi]

Move Value * and enum from SCEV class to maps in ScalarEvolution class.
performance test result of llvm testsuite is neutral on a x86-64 sandybridge.

[hfinkel]

include/llvm/Analysis/ScalarEvolution.h

104 ↗

(On Diff #34043)

This now looks only like an unnecessary formatting change.

lib/Analysis/ScalarEvolution.cpp

3374 ↗

(On Diff #34043)

This makes me a bit uncomfortable; you're relying on the fact that, if a Value* is removed, then no new Value* will be created in the same location, or if that does happen, the new Value* won't be used with getSCEV(). Nothing really guarantees this, however.

One option is to hold WeakVH as the values in your map. Another option is to enhance the SCEVCallbackVH implementation to update the ExprValueMap directly. Given that you seem to have already done the SCEVCallbackVH update below, maybe the additional check is just unnecessary now.

[wmi]

This makes me a bit uncomfortable; you're relying on the fact that, if a Value* is removed, then no new Value* will be created in the same location, or if that does happen, the new Value* won't be used with getSCEV(). Nothing really guarantees this, however.
One option is to hold WeakVH as the values in your map. Another option is to enhance the SCEVCallbackVH implementation to update the ExprValueMap directly. Given that you seem to have already done the SCEVCallbackVH update below, maybe the additional check is just unnecessary now.

Thanks! It is a problem indeed. I took the first option and used WeakVH in the map.

[hfinkel]

lib/Analysis/ScalarEvolutionExpander.cpp

1646 ↗

(On Diff #35675)

Why are we reusing an existing value only for AddRecs?

I see in the summary that you say:

The intuition is, if only SCEV doesn't contain scAddRecExpr, using the original value to expand will not nullify valid loop transformations.

But I don't see the downside to always reusing an available value from that. Another potentially-problematic issue is that SCEVs may not be unique, and I'm a bit concerned about always taking only the first or last such value encountered, because it imposes an indirect constraint on the users of ScalarEvolution and the expander to ensure that they always visit all such values in some deterministic order. This is not currently the case. Moreover, it can be problematic if, for example, you symbolically compute X-Y first, and then call getSCEV on a value that happens to be X-Y, will expand differently than calling getSCEV on that value and doing the symbolic calculation later.

Also, if we are going to restrict these to a subclass of SCEVs, why wouldn't you only store the values/SCEV pair in the map if the SCEV satisfies hasAnyRec?

[wmi]

lib/Analysis/ScalarEvolutionExpander.cpp

1646 ↗

(On Diff #35675)

Why are we reusing an existing value only for AddRecs?

No, we are reusing an existing value only for scevs which are not scAddRecExpr. The downside to use existing value for scAddRecExpr is that it may nullify some optimization done by LSR. (I think only scAddRecExpr type scev is substantially involved in LSR optimization)

Another potentially-problematic issue is that SCEVs may not be unique, and I'm a bit concerned about always taking only the first or last such value encountered, because it imposes an indirect constraint on the users of ScalarEvolution and the expander to ensure that they always visit all such values in some deterministic order. This is not currently the case. Moreover, it can be problematic if, for example, you symbolically compute X-Y first, and then call getSCEV on a value that happens to be X-Y, will expand differently than calling getSCEV on that value and doing the symbolic calculation later.

I guess your point is: multiple values can be mapped to the same SCEV. Only one of those values will be recorded in ExprValueMap and will be used in expansion. To get the maximum optimization opportunity, the values must be encountered/expanded in a certain order.

However, I think the same problem exists either even without the patch because the fact that mulitple values can be mapped to the same SCEV is true w/wo the patch (This is determined by ScalarEvolution::createSCEV and we didn't change it in the patch).

value = X-Y
...
To expand S1.

Suppose X-Y and X'-Y' will both be mapped to S1. Whether S1 will be expanded to X-Y or X'-Y' depends on which one is first encountered by getSCEV. This is true even without the patch.

Also, if we are going to restrict these to a subclass of SCEVs, why wouldn't you only store the values/SCEV pair in the map if the SCEV satisfies hasAnyRec?

I think you mean not to store the value/scAddRecExpr pair in the map. It can make the map smaller. I will change it.

[hfinkel]

lib/Analysis/ScalarEvolutionExpander.cpp

1646 ↗

(On Diff #35675)

No, we are reusing an existing value only for scevs which are not scAddRecExpr. The downside to use existing value for scAddRecExpr is that it may nullify some optimization done by LSR. (I think only scAddRecExpr type scev is substantially involved in LSR optimization)

I'm very afraid here of creating an quirky interface that, while appearing to offer a general set of facilities, contains a set of unexpected behaviors tailored to a specific consumer (LSR, in this case). Regardless, ScalarEvolutionExpander already contains a special 'LSRMode', and we should key and LSR-specific customizations off of that. In the general case, we should have a consistent behavior.

[wmi]

lib/Analysis/ScalarEvolutionExpander.cpp

1646 ↗

(On Diff #35675)

1. I rethought your previous comments about uncertainty of the expansion result and found something I can improve. Thanks for those comments.

A case is like this:

BBi:
%sub2 = %x - %y;
...
BBj:
%x = load %a;
%y = load %b;
%sub1 = %x - %y;
...
%i_0 = %sub1;
for.body:

%i_1 = PHI (%i_0, %i_next)
%i_next = %i_1 + 1;
%cmp = icmp slt %i_next, %z
br i1 %cmp, label %for.body, label %for.end

for.end:

If we expand the SCEV when we try to get the backedge count, without the patch it will be "%z - (%x - %y) - 1", with the patch it may be "%z - %sub1 - 1" if %sub1 is recorded in SCEV of "%x - %y", or it may be "%z - %sub2 - 1" if %sub2 is recorded in SCEV of "%x - %y". It is also possible that BBi cannot reach BBj, so SCEV also may expand to "%z - (%x - %y) - 1" with the patch.

This can be improved. I can record the set of all possible Values mapped to the same SCEV in ExprValueMap. In SCEVExpander::expand, I will select one value from the set which will dominate the insert point, so in the case above, SCEV will only be expanded to "%z - %sub1 - 1" if BBi cannot reach BBj, so reuse will be realized every time and there will be much less uncertainty in the expansion result.

2. For another concern you raised, although existing behavior of SCEVExpander::expand is more consistent -- it always literally generates all the computations SCEV represents, it sacrifices the opportunity to reuse existing values. The patch introduces some inconsistency. The inconsistency is that we keep the expansion behavior of scAddRecExpr the same as without the patch, but may reuse existing values when expanding other kinds of SCEV (So the inconsistency here is actually an improvement when expanding non-scAddRecExpr SCEVs). I think about the generaility of the interface, besides LSR, other components can still use the interface the same as before and believe the interface will generate equal value -- without affecting correctness, but possibly with less cost. And I think I can describe the inconsistency more clearly in comments to remove potential confusion from the users of the interface.

[wmi]

Update the patch (Sorry for not updating it for a long time).

This can be improved. I can record the set of all possible Values mapped to the same SCEV in ExprValueMap. In SCEVExpander::expand, I will select one value from the set which will dominate the insert point.

1. The improvement is implemented. Because there can be multiple Value mapping to the same SCEV, record the mapping from SCEV to vector<WeakVH> in ExprValueMap. During SCEV expansion, choose one Value from the vector which can dominate the insertPt. The update to the unittest test/Transforms/IndVarSimplify/udiv.ll reflects the usage of the change. IndVars doesn't emit a udiv in for.body.preheader BB after the change. %div1 will be reused there.

I'm very afraid here of creating an quirky interface that, while appearing to offer a general set of facilities, contains a set of unexpected behaviors tailored to a specific consumer (LSR, in this case). Regardless, ScalarEvolutionExpander already contains a special 'LSRMode', and we should key and LSR-specific customizations off of that. In the general case, we should have a consistent behavior.

2. This concern has not been addressed very well. I still don't have a good solution for it right now. What I have done for it is to add a comment describing the status before func SCEVExpander::expand.

[wmi]

Ping.

Thanks,
Wei.

[sanjoy]

Some minor nits inline.

Overall, I agree with Hal's judgement that any LSR specific behavior should be guarded on LSRMode; both so that the reason for the limitation is obvious, and also to not unnecessarily (and, to the end user, inexplicably) do a worse job than we could have done.

lib/Analysis/ScalarEvolution.cpp

3314 ↗

(On Diff #39695)

I'd rename this to containsAddRecurrence.

3317 ↗

(On Diff #39695)

Why not return I->second;?

3319 ↗

(On Diff #39695)

Can't you use a SCEVTraversal here?

lib/Analysis/ScalarEvolutionExpander.cpp

1650 ↗

(On Diff #39695)

Nit: LLVM naming style is auto const &Ent : *Vec.

lib/Transforms/Vectorize/LoopVectorize.cpp

2598 ↗

(On Diff #39695)

Nit: wrapping

[wmi]

Overall, I agree with Hal's judgement that any LSR specific behavior should be guarded on LSRMode;

Thanks for the explaination. I misunderstood Hal's comment and thought existing use of LSRMode is already bad so I shouldn't add another use of LSRMode (My bad English). That is why I say I cannot figure out a better way to make the interface clean.

Now the behavior of SCEVExpander::expand is defined clearer in its function header comment:

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 transformed SCEV from being reverted. Otherwise,
the expansion will try to reuse Value from ExprValueMap, and only when it
fails, expand the SCEV literally.

lib/Analysis/ScalarEvolution.cpp

3319 ↗

(On Diff #39695)

That is much better. Done.

[wmi]

Addressed Hal and Sanjoy's comments.

Other changes:

1. Change vector to set in ExprValueMap.
2. Add test scev-expander-existing-value.ll.

[hfinkel]

include/llvm/Analysis/ScalarEvolution.h

253 ↗

(On Diff #42488)

store the analysis result about -> record

259 ↗

(On Diff #42488)

As I note later, you probably want a SetVector here, not a std::set. Also, std::set is generally much slower than DenseSet, so we should use the latter if possible (SetVector uses a DenseSet).

lib/Analysis/ScalarEvolutionExpander.cpp

1608 ↗

(On Diff #42488)

LSR -> LSR's

1654 ↗

(On Diff #42488)

LSR -> LSR's

1659 ↗

(On Diff #42488)

You're iterating over the elements of a set here, and those have WeakVH (i.e. pointer-valued) keys. That seems unlikely to be deterministic.

SetVector seems like a better choice.

lib/Transforms/Vectorize/LoopVectorize.cpp

2600 ↗

(On Diff #42488)

func -> function (no need to abbreviate here)

[wmi]

Addressed Hal's comments. Changed std::set<WeakVH> to SetVector<WeakVH, std::vector<WeakVH>, DenseSet<WeakVH>>.

[hfinkel]

include/llvm/Analysis/ScalarEvolution.h

211 ↗

(On Diff #42502)

SetVector is defined as:

template <typename T, typename Vector = std::vector<T>,
          typename Set = DenseSet<T>>
class SetVector {
...

and so

,std::vector<WeakVH>, DenseSet<WeakVH>

should be implied by the first template argument. If this can be simplified to:

typedef SetVector<WeakVH> WeakVHSetType;

then please do.

(but, you also need to change the WeakVH type, see below)

include/llvm/IR/ValueHandle.h

177 ↗

(On Diff #42502)

I apologize, because I believe I was the one who implied this would work. But that fact that you had to add this here reminded me that it won't. The problem is that a WeakVH's value changes when the underlying Value is removed (it changes from the pointer value to nullptr). Thus, we can't use these as keys in a set (or map) because the key needs to remain fixed (otherwise it will be in the wrong bucket, or in the wrong order for a sorted set, after the change).

We need instead to use a different kind of ValueHandle that can remove itself from its parent map once the underlying value goes away. The good news is that we already have implementations of this: We have a ValueMap class (include/llvm/IR/ValueMap.h), and we have SCEV's ValueExprMapType type SCEVCallbackVH.

All things considered, I think that just using raw pointers in the SetVectors is probably your best option, and enhance SCEVCallbackVH to also remove outdated Values (for every value in one of those vectors, we must already have an entry in ValueExprMap which should have the same lifetime). Thus, in SCEVCallbackVH's callback, you can use the associated SCEV* to lookup the correct SetVector<Value*> and remove the necessary entry (SetVector has a convenient 'remove' member function for this purpose).

[wmi]

Thanks for detecting the potential error, and your suggestion to use SCEVCallbackVH's callback instead of WeakVH looks feasible.

I just looked at ScalarEvolution::getSCEV again and believed ExprValueMap[S].insert(WeakVH(V)) will be called only once for the same Value (It will not happen that two instances of the same Value are inserted to the set). So can we simply use a std::vector<WeakVH> instead of SetVector, which may be cheaper because SetVector uses std::vector inside of it.

[wmi]

I try std::vector and find it is possible for ExprValueMap to have duplicate Values in the vector because createSCEV will be called multiple times for the same PHI Value. Another weakness is there may be multiple WeakVHs with nullptr Values staying in the vector.

So I still follow Hal's suggestion to use SetVector<Value *>.

ScalarEvolution::eraseValueFromMap is created to ensure whenever V->S is removed from ValueExprMap, V is also removed from the set of ExprValueMap[S] . In this way, entry in ValueExprMap will always have equal or longer life time than corresponding entry in ExprValueMap. So when V is deleted and V is in a SetVector of ExprValueMap, ValueExprMap[V] can always be used as the Key of ExprValueMap.

[wmi]

Ping.

[hfinkel]

lib/Analysis/ScalarEvolution.cpp

3319 ↗

(On Diff #42927)

I'd name this FoundOne (instead of FindOne), because it indicates whether or not an AddRec was found, not a directive for the future search).

3370 ↗

(On Diff #42927)

I appreciate this idea, but please don't do this by default. In a build with asserts, this check makes Value removal O(N^2). If you'd like to have this check, you'll need a separate flag. This reminds me of EnableExpensiveChecks in lib/CodeGen/SelectionDAG/LegalizeTypes.cpp.

lib/Transforms/Vectorize/LoopVectorize.cpp

2598 ↗

(On Diff #42927)

dominate -> dominator

[wmi]

lib/Analysis/ScalarEvolution.cpp

3370 ↗

(On Diff #42927)

I put the check under VerifySCEVMap option (similar as VerifySCEV option).

And I moved the check to ScalarEvolution::getSCEVValues from ScalarEvolution::eraseValueFromMap, so it can ensure every Value set returned by getSCEVValues don't have dangling value inside of it.

[hfinkel]

LGTM.

[wmi]

Thank you for your patience and thank you for providing many helpful
suggestions!

Wei.

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

 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_SCALAREVOLUTION_H
 #define LLVM_ANALYSIS_SCALAREVOLUTION_H
 
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/FoldingSet.h"
+#include "llvm/ADT/SetVector.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Operator.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/IR/ValueHandle.h"
 #include "llvm/Pass.h"
private:
 
     /// The loop information for the function we are currently analyzing.
     ///
     LoopInfo &LI;
 
     /// This SCEV is used to represent unknown trip counts and things.
     std::unique_ptr<SCEVCouldNotCompute> CouldNotCompute;
 
+    /// HasRecMapType - The typedef for HasRecMap.
+    ///
+    typedef DenseMap<const SCEV *, bool> HasRecMapType;
+
+    /// HasRecMap -- This is a cache to record whether a SCEV contains
+    /// any scAddRecExpr.
+    HasRecMapType HasRecMap;
+
+    /// ExprValueMapType - The typedef for ExprValueMap.
+    ///
+    typedef DenseMap<const SCEV *, SetVector<Value *>> ExprValueMapType;
+
+    /// ExprValueMap -- This map records the original values from which
+    /// the SCEV expr is generated from.
+    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.
     ///
     ValueExprMapType ValueExprMap;
public:
     /// return true.
     uint64_t getTypeSizeInBits(Type *Ty) const;
 
     /// Return a type with the same bitwidth as the given type and which
     /// represents how SCEV will treat the given type, for which isSCEVable must
     /// return true. For pointer types, this is the pointer-sized integer type.
     Type *getEffectiveSCEVType(Type *Ty) const;
 
+    /// containsAddRecurrence - Return true if the SCEV is a scAddRecExpr or
+    /// it contains scAddRecExpr. The result will be cached in HasRecMap.
+    ///
+    bool containsAddRecurrence(const SCEV *S);
+
+    /// getSCEVValues - Return the Value set from which the SCEV expr is
+    /// generated.
+    SetVector<Value *> *getSCEVValues(const SCEV *S);
+
+    /// eraseValueFromMap - 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);
 
     const SCEV *getConstant(ConstantInt *V);
     const SCEV *getConstant(const APInt& Val);
     const SCEV *getConstant(Type *Ty, uint64_t V, bool isSigned = false);
     const SCEV *getTruncateExpr(const SCEV *Op, Type *Ty);

llvm/trunk/lib/Analysis/ScalarEvolution.cpp

MaxBruteForceIterations("scalar-evolution-max-iterations", cl::ReallyHidden,
                                  "symbolically execute a constant "
                                  "derived loop"),
                         cl::init(100));
 
 // FIXME: Enable this with XDEBUG when the test suite is clean.
 static cl::opt<bool>
 VerifySCEV("verify-scev",
            cl::desc("Verify ScalarEvolution's backedge taken counts (slow)"));
+static cl::opt<bool>
+    VerifySCEVMap("verify-scev-maps",
+                  cl::desc("Verify no dangling value in ScalarEvolution's"
+                           "ExprValueMap (slow)"));
 
 //===----------------------------------------------------------------------===//
 //                           SCEV class definitions
 //===----------------------------------------------------------------------===//
 
 //===----------------------------------------------------------------------===//
 // Implementation of the SCEV class.
 //
bool ScalarEvolution::checkValidity(const SCEV *S) const {
 
   FindInvalidSCEVUnknown F;
   SCEVTraversal<FindInvalidSCEVUnknown> ST(F);
   ST.visitAll(S);
 
   return !F.FindOne;
 }
 
+namespace {
+// Helper class working with SCEVTraversal to figure out if a SCEV contains
+// a sub SCEV of scAddRecExpr type.  FindInvalidSCEVUnknown::FoundOne is set
+// iff if such sub scAddRecExpr type SCEV is found.
+struct FindAddRecurrence {
+  bool FoundOne;
+  FindAddRecurrence() : FoundOne(false) {}
+
+  bool follow(const SCEV *S) {
+    switch (static_cast<SCEVTypes>(S->getSCEVType())) {
+    case scAddRecExpr:
+      FoundOne = true;
+    case scConstant:
+    case scUnknown:
+    case scCouldNotCompute:
+      return false;
+    default:
+      return true;
+    }
+  }
+  bool isDone() const { return FoundOne; }
+};
+}
+
+bool ScalarEvolution::containsAddRecurrence(const SCEV *S) {
+  HasRecMapType::iterator I = HasRecMap.find_as(S);
+  if (I != HasRecMap.end())
+    return I->second;
+
+  FindAddRecurrence F;
+  SCEVTraversal<FindAddRecurrence> ST(F);
+  ST.visitAll(S);
+  HasRecMap.insert(std::make_pair(S, F.FoundOne));
+  return F.FoundOne;
+}
+
+/// getSCEVValues - Return the Value set from S.
+SetVector<Value *> *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));
+  }
+#endif
+  return &SI->second;
+}
+
+/// eraseValueFromMap - 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].
+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);
+    ValueExprMap.erase(V);
+  }
+}
+
 /// getSCEV - 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.
+    std::pair<ValueExprMapType::iterator, bool> Pair =
         ValueExprMap.insert(std::make_pair(SCEVCallbackVH(V, this), S));
+    if (Pair.second)
+      ExprValueMap[S].insert(V);
   }
   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;
+    forgetMemoizedResults(S);
     ValueExprMap.erase(I);
   }
   return nullptr;
 }
 
 /// getNegativeSCEV - Return a SCEV corresponding to -V = -1*V
 ///
 const SCEV *ScalarEvolution::getNegativeSCEV(const SCEV *V,

 //===----------------------------------------------------------------------===//
 //                   SCEVCallbackVH Class Implementation
 //===----------------------------------------------------------------------===//
 
 void ScalarEvolution::SCEVCallbackVH::deleted() {
   assert(SE && "SCEVCallbackVH called with a null ScalarEvolution!");
   if (PHINode *PN = dyn_cast<PHINode>(getValPtr()))
     SE->ConstantEvolutionLoopExitValue.erase(PN);
-  SE->ValueExprMap.erase(getValPtr());
+  SE->eraseValueFromMap(getValPtr());
   // this now dangles!
 }
 
 void ScalarEvolution::SCEVCallbackVH::allUsesReplacedWith(Value *V) {
   assert(SE && "SCEVCallbackVH called with a null ScalarEvolution!");
 
   // Forget all the expressions associated with users of the old value,
   // so that future queries will recompute the expressions using the new
   // value.
   Value *Old = getValPtr();
   SmallVector<User *, 16> Worklist(Old->user_begin(), Old->user_end());
   SmallPtrSet<User *, 8> Visited;
   while (!Worklist.empty()) {
     User *U = Worklist.pop_back_val();
     // Deleting the Old value will cause this to dangle. Postpone
     // that until everything else is done.
     if (U == Old)
       continue;
     if (!Visited.insert(U).second)
       continue;
     if (PHINode *PN = dyn_cast<PHINode>(U))
       SE->ConstantEvolutionLoopExitValue.erase(PN);
-    SE->ValueExprMap.erase(U);
+    SE->eraseValueFromMap(U);
     Worklist.insert(Worklist.end(), U->user_begin(), U->user_end());
   }
   // Delete the Old value.
   if (PHINode *PN = dyn_cast<PHINode>(Old))
     SE->ConstantEvolutionLoopExitValue.erase(PN);
-  SE->ValueExprMap.erase(Old);
+  SE->eraseValueFromMap(Old);
   // this now dangles!
 }
 
 ScalarEvolution::SCEVCallbackVH::SCEVCallbackVH(Value *V, ScalarEvolution *se)
   : CallbackVH(V), SE(se) {}
 
 //===----------------------------------------------------------------------===//
 //                   ScalarEvolution Class Implementation
ScalarEvolution::~ScalarEvolution() {
   // destructors, so that they release their references to their values.
   for (SCEVUnknown *U = FirstUnknown; U;) {
     SCEVUnknown *Tmp = U;
     U = U->Next;
     Tmp->~SCEVUnknown();
   }
   FirstUnknown = nullptr;
 
+  ExprValueMap.clear();
   ValueExprMap.clear();
+  HasRecMap.clear();
 
   // Free any extra memory created for ExitNotTakenInfo in the unlikely event
   // that a loop had multiple computable exits.
   for (auto &BTCI : BackedgeTakenCounts)
     BTCI.second.clear();
 
   assert(PendingLoopPredicates.empty() && "isImpliedCond garbage");
   assert(!WalkingBEDominatingConds && "isLoopBackedgeGuardedByCond garbage!");

 }
 
 void ScalarEvolution::forgetMemoizedResults(const SCEV *S) {
   ValuesAtScopes.erase(S);
   LoopDispositions.erase(S);
   BlockDispositions.erase(S);
   UnsignedRanges.erase(S);
   SignedRanges.erase(S);
+  ExprValueMap.erase(S);
+  HasRecMap.erase(S);
 
   for (DenseMap<const Loop*, BackedgeTakenInfo>::iterator I =
          BackedgeTakenCounts.begin(), E = BackedgeTakenCounts.end(); I != E; ) {
     BackedgeTakenInfo &BEInfo = I->second;
     if (BEInfo.hasOperand(S, this)) {
       BEInfo.clear();
       BackedgeTakenCounts.erase(I++);
     }

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;
 }
 
+// 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) {
   // Compute an insertion point for this SCEV object. Hoist the instructions
   // as far out in the loop nest as possible.
   Instruction *InsertPt = &*Builder.GetInsertPoint();
   for (Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock());;
        L = L->getParentLoop())
     if (SE.isLoopInvariant(S, L)) {
       if (!L) break;
Value *SCEVExpander::expand(const SCEV *S) {
   auto I = InsertedExpressions.find(std::make_pair(S, InsertPt));
   if (I != InsertedExpressions.end())
     return I->second;
 
   BuilderType::InsertPointGuard Guard(Builder);
   Builder.SetInsertPoint(InsertPt);
 
   // Expand the expression into instructions.
-  Value *V = visit(S);
+  SetVector<Value *> *Set = SE.getSCEVValues(S);
+  Value *V = nullptr;
+  // 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.
+  if (!(LSRMode && SE.containsAddRecurrence(S))) {
+    if (Set) {
+      // Choose a Value from the set which dominates the insertPt.
+      for (auto const &Ent : *Set) {
+        if (Ent && isa<Instruction>(Ent) && S->getType() == Ent->getType() &&
+            SE.DT.dominates(cast<Instruction>(Ent), InsertPt)) {
+          V = Ent;
+          break;
+        }
+      }
+    }
+  }
+  if (!V)
+    V = visit(S);
 
   // 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;

llvm/trunk/lib/Transforms/Vectorize/LoopVectorize.cpp

void InnerLoopVectorizer::emitMinimumIterationCountCheck(Loop *L,
   // adding one to the backedge-taken count will not overflow.
   Value *CheckMinIters =
     Builder.CreateICmpULT(Count,
                           ConstantInt::get(Count->getType(), VF * UF),
                           "min.iters.check");
   
   BasicBlock *NewBB = BB->splitBasicBlock(BB->getTerminator(),
                                           "min.iters.checked");
+  // Update dominator tree immediately if the generated block is a
+  // LoopBypassBlock because SCEV expansions to generate loop bypass
+  // checks may query it before the current function is finished.
+  DT->addNewBlock(NewBB, BB);
   if (L->getParentLoop())
     L->getParentLoop()->addBasicBlockToLoop(NewBB, *LI);
   ReplaceInstWithInst(BB->getTerminator(),
                       BranchInst::Create(Bypass, NewBB, CheckMinIters));
   LoopBypassBlocks.push_back(BB);
 }
 
 void InnerLoopVectorizer::emitVectorLoopEnteredCheck(Loop *L,
                                                      BasicBlock *Bypass) {
   Value *TC = getOrCreateVectorTripCount(L);
   BasicBlock *BB = L->getLoopPreheader();
   IRBuilder<> Builder(BB->getTerminator());
   
   // Now, compare the new count to zero. If it is zero skip the vector loop and
   // jump to the scalar loop.
   Value *Cmp = Builder.CreateICmpEQ(TC, Constant::getNullValue(TC->getType()),
                                     "cmp.zero");
 
   // Generate code to check that the loop's trip count that we computed by
   // adding one to the backedge-taken count will not overflow.
   BasicBlock *NewBB = BB->splitBasicBlock(BB->getTerminator(),
                                           "vector.ph");
+  // Update dominator tree immediately if the generated block is a
+  // LoopBypassBlock because SCEV expansions to generate loop bypass
+  // checks may query it before the current function is finished.
+  DT->addNewBlock(NewBB, BB);
   if (L->getParentLoop())
     L->getParentLoop()->addBasicBlockToLoop(NewBB, *LI);
   ReplaceInstWithInst(BB->getTerminator(),
                       BranchInst::Create(Bypass, NewBB, Cmp));
   LoopBypassBlocks.push_back(BB);
 }
 
 void InnerLoopVectorizer::emitSCEVChecks(Loop *L, BasicBlock *Bypass) {
void InnerLoopVectorizer::emitSCEVChecks(Loop *L, BasicBlock *Bypass) {
 
   if (auto *C = dyn_cast<ConstantInt>(SCEVCheck))
     if (C->isZero())
       return;
 
   // Create a new block containing the stride check.
   BB->setName("vector.scevcheck");
   auto *NewBB = BB->splitBasicBlock(BB->getTerminator(), "vector.ph");
+  // Update dominator tree immediately if the generated block is a
+  // LoopBypassBlock because SCEV expansions to generate loop bypass
+  // checks may query it before the current function is finished.
+  DT->addNewBlock(NewBB, BB);
   if (L->getParentLoop())
     L->getParentLoop()->addBasicBlockToLoop(NewBB, *LI);
   ReplaceInstWithInst(BB->getTerminator(),
                       BranchInst::Create(Bypass, NewBB, SCEVCheck));
   LoopBypassBlocks.push_back(BB);
   AddedSafetyChecks = true;
 }
 
void InnerLoopVectorizer::emitMemRuntimeChecks(Loop *L,
   std::tie(FirstCheckInst, MemRuntimeCheck) =
       Legal->getLAI()->addRuntimeChecks(BB->getTerminator());
   if (!MemRuntimeCheck)
     return;
 
   // Create a new block containing the memory check.
   BB->setName("vector.memcheck");
   auto *NewBB = BB->splitBasicBlock(BB->getTerminator(), "vector.ph");
+  // Update dominator tree immediately if the generated block is a
+  // LoopBypassBlock because SCEV expansions to generate loop bypass
+  // checks may query it before the current function is finished.
+  DT->addNewBlock(NewBB, BB);
   if (L->getParentLoop())
     L->getParentLoop()->addBasicBlockToLoop(NewBB, *LI);
   ReplaceInstWithInst(BB->getTerminator(),
                       BranchInst::Create(Bypass, NewBB, MemRuntimeCheck));
   LoopBypassBlocks.push_back(BB);
   AddedSafetyChecks = true;
 }
 

 void InnerLoopVectorizer::updateAnalysis() {
   // Forget the original basic block.
   PSE.getSE()->forgetLoop(OrigLoop);
 
   // Update the dominator tree information.
   assert(DT->properlyDominates(LoopBypassBlocks.front(), LoopExitBlock) &&
          "Entry does not dominate exit.");
 
-  for (unsigned I = 1, E = LoopBypassBlocks.size(); I != E; ++I)
-    DT->addNewBlock(LoopBypassBlocks[I], LoopBypassBlocks[I-1]);
-  DT->addNewBlock(LoopVectorPreHeader, LoopBypassBlocks.back());
-
   // We don't predicate stores by this point, so the vector body should be a
   // single loop.
   assert(LoopVectorBody.size() == 1 && "Expected single block loop!");
   DT->addNewBlock(LoopVectorBody[0], LoopVectorPreHeader);
 
   DT->addNewBlock(LoopMiddleBlock, LoopVectorBody.back());
   DT->addNewBlock(LoopScalarPreHeader, LoopBypassBlocks[0]);
   DT->changeImmediateDominator(LoopScalarBody, LoopScalarPreHeader);

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

+; RUN: opt < %s -loop-vectorize -force-vector-width=4 -verify-scev-maps -S |FileCheck %s
+
+; SCEV expansion uses existing value when the SCEV has no AddRec expr.
+; CHECK: select
+; CHECK-NOT: select
+
+@a = common global [1000 x i16] zeroinitializer, align 16
+
+define i32 @foo(i32 %x, i32 %y) {
+entry:
+  %cmp = icmp slt i32 %x, %y
+  %cond = select i1 %cmp, i32 %x, i32 %y
+  %cmp1.10 = icmp sgt i32 %cond, 0
+  br i1 %cmp1.10, label %for.body.lr.ph, label %for.end
+
+for.body.lr.ph:                                   ; preds = %entry
+  %tmp = sext i32 %cond to i64
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %for.body.lr.ph
+  %indvars.iv = phi i64 [ 0, %for.body.lr.ph ], [ %indvars.iv.next, %for.body ]
+  %total.011 = phi i32 [ 0, %for.body.lr.ph ], [ %add, %for.body ]
+  %arrayidx = getelementptr inbounds [1000 x i16], [1000 x i16]* @a, i64 0, i64 %indvars.iv
+  %tmp1 = load i16, i16* %arrayidx, align 2
+  %conv = sext i16 %tmp1 to i32
+  %add = add nsw i32 %conv, %total.011
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %cmp1 = icmp slt i64 %indvars.iv.next, %tmp
+  br i1 %cmp1, 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
+  %total.0.lcssa = phi i32 [ 0, %entry ], [ %add.lcssa, %for.end.loopexit ]
+  ret i32 %total.0.lcssa
+}

llvm/trunk/test/CodeGen/Thumb2/2009-12-01-LoopIVUsers.ll

 ; RUN: opt < %s -O3 | \
 ; RUN:   llc -mtriple=thumbv7-apple-darwin10 -mattr=+neon | FileCheck %s
 
 target datalayout = "e-p:32:32:32-i1:8:32-i8:8:32-i16:16:32-i32:32:32-i64:32:32-f32:32:32-f64:32:32-v64:64:64-v128:128:128-a0:0:32"
 
 define void @fred(i32 %three_by_three, i8* %in, double %dt1, i32 %x_size, i32 %y_size, i8* %bp) nounwind {
 entry:
 ; -- The loop following the load should only use a single add-literation
 ;    instruction.
 ; CHECK: vldr
-; CHECK: adds r{{[0-9]+.*}}#1
 ; CHECK-NOT: adds
 ; CHECK: subsections_via_symbols
 
 
   %three_by_three_addr = alloca i32               ; <i32*> [#uses=2]
   %in_addr = alloca i8*                           ; <i8**> [#uses=2]
   %dt_addr = alloca float                         ; <float*> [#uses=4]
   %x_size_addr = alloca i32                       ; <i32*> [#uses=2]

llvm/trunk/test/Transforms/IRCE/decrementing-loop.ll

 
  out.of.bounds:
   ret void
 
  exit:
   ret void
 
 ; CHECK: loop.preheader:
-; CHECK:   [[indvar_start:[^ ]+]] = add i32 %n, -1
 ; CHECK:   [[not_len:[^ ]+]] = sub i32 -1, %len
 ; CHECK:   [[not_n:[^ ]+]] = sub i32 -1, %n
 ; CHECK:   [[not_len_hiclamp_cmp:[^ ]+]] = icmp sgt i32 [[not_len]], [[not_n]]
 ; CHECK:   [[not_len_hiclamp:[^ ]+]] = select i1 [[not_len_hiclamp_cmp]], i32 [[not_len]], i32 [[not_n]]
 ; CHECK:   [[len_hiclamp:[^ ]+]] = sub i32 -1, [[not_len_hiclamp]]
 ; CHECK:   [[not_exit_preloop_at_cmp:[^ ]+]] = icmp sgt i32 [[len_hiclamp]], 0
 ; CHECK:   [[not_exit_preloop_at:[^ ]+]] = select i1 [[not_exit_preloop_at_cmp]], i32 [[len_hiclamp]], i32 0
 ; CHECK:   %exit.preloop.at = add i32 [[not_exit_preloop_at]], -1
 }
 
 !0 = !{i32 0, i32 2147483647}
 !1 = !{!"branch_weights", i32 64, i32 4}

llvm/trunk/test/Transforms/IndVarSimplify/lftr-address-space-pointers.ll

 ; RUN: opt -S -indvars -o - %s | FileCheck %s
 target datalayout = "e-p:32:32:32-p1:64:64:64-p2:8:8:8-p3:16:16:16-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:32-n8:16:32:64"
 
 ; Derived from ptriv in lftr-reuse.ll
 define void @ptriv_as2(i8 addrspace(2)* %base, i32 %n) nounwind {
 ; CHECK-LABEL: @ptriv_as2(
 entry:
   %idx.trunc = trunc i32 %n to i8
   %add.ptr = getelementptr inbounds i8, i8 addrspace(2)* %base, i8 %idx.trunc
   %cmp1 = icmp ult i8 addrspace(2)* %base, %add.ptr
   br i1 %cmp1, label %for.body, label %for.end
 
 ; Make sure the added GEP has the right index type
-; CHECK: %lftr.limit = getelementptr i8, i8 addrspace(2)* %base, i8 %0
+; CHECK: %lftr.limit = getelementptr i8, i8 addrspace(2)* %base, i8 %idx.trunc
 
 ; CHECK: for.body:
 ; CHECK: phi i8 addrspace(2)*
 ; CHECK-NOT: phi
 ; CHECK-NOT: add{{^rspace}}
 ; CHECK: icmp ne i8 addrspace(2)*
 ; CHECK: br i1
 for.body:

 ; CHECK-LABEL: @ptriv_as3(
 entry:
   %idx.trunc = trunc i32 %n to i16
   %add.ptr = getelementptr inbounds i8, i8 addrspace(3)* %base, i16 %idx.trunc
   %cmp1 = icmp ult i8 addrspace(3)* %base, %add.ptr
   br i1 %cmp1, label %for.body, label %for.end
 
 ; Make sure the added GEP has the right index type
-; CHECK: %lftr.limit = getelementptr i8, i8 addrspace(3)* %base, i16 %0
+; CHECK: %lftr.limit = getelementptr i8, i8 addrspace(3)* %base, i16 %idx.trunc
 
 ; CHECK: for.body:
 ; CHECK: phi i8 addrspace(3)*
 ; CHECK-NOT: phi
 ; CHECK-NOT: add{{^rspace}}
 ; CHECK: icmp ne i8 addrspace(3)*
 ; CHECK: br i1
 for.body:

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

 ; RUN: opt -S -indvars < %s | FileCheck %s
 
 target datalayout = "E-m:e-i64:64-n32:64"
 target triple = "powerpc64-unknown-linux-gnu"
 
 define void @f(i32* %end.s, i8** %loc, i32 %p) {
 ; CHECK-LABEL: @f(
 entry:
-; CHECK:  [[P_SEXT:%[0-9a-z]+]] = sext i32 %p to i64
-; CHECK:  [[END:%[0-9a-z]+]] = getelementptr i32, i32* %end.s, i64 [[P_SEXT]]
-
   %end = getelementptr inbounds i32, i32* %end.s, i32 %p
   %init = bitcast i32* %end.s to i8*
   br label %while.body.i
 
 while.body.i:
   %ptr = phi i8* [ %ptr.inc, %while.body.i ], [ %init, %entry ]
   %ptr.inc = getelementptr inbounds i8, i8* %ptr, i8 1
   %ptr.inc.cast = bitcast i8* %ptr.inc to i32*
   %cmp.i = icmp eq i32* %ptr.inc.cast, %end
   br i1 %cmp.i, label %loop.exit, label %while.body.i
 
 loop.exit:
 ; CHECK: loop.exit:
-; CHECK: [[END_BCASTED:%[a-z0-9]+]] = bitcast i32* %scevgep to i8*
+; CHECK: [[END_BCASTED:%[a-z0-9]+]] = bitcast i32* %end to i8*
 ; CHECK: store i8* [[END_BCASTED]], i8** %loc
   %ptr.inc.lcssa = phi i8* [ %ptr.inc, %while.body.i ]
   store i8* %ptr.inc.lcssa, i8** %loc
   ret void
 }

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

while.end:                                        ; preds = %while.cond.while.end_crit_edge, %while.cond.preheader
   %call40 = tail call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([11 x i8], [11 x i8]* @.str, i64 0, i64 0), i32 %count.0.lcssa) nounwind ; <i32> [#uses=0]
   ret i32 0
 }
 
 declare i32 @atoi(i8* nocapture) nounwind readonly
 
 declare i32 @printf(i8* nocapture, ...) nounwind
 
-; IndVars shouldn't be afraid to emit a udiv here, since there's a udiv in
-; the original code.
+; IndVars doesn't emit a udiv in for.body.preheader since SCEVExpander::expand will
+; find out there's already a udiv in the original code.
 
 ; CHECK-LABEL: @foo(
 ; CHECK: for.body.preheader:
-; CHECK-NEXT: udiv
+; CHECK-NOT: udiv
 
 define void @foo(double* %p, i64 %n) nounwind {
 entry:
   %div0 = udiv i64 %n, 7                          ; <i64> [#uses=1]
   %div1 = add i64 %div0, 1
   %cmp2 = icmp ult i64 0, %div1                   ; <i1> [#uses=1]
   br i1 %cmp2, label %for.body.preheader, label %for.end
 

llvm/trunk/test/Transforms/IndVarSimplify/ult-sub-to-eq.ll

for.body:                                         ; preds = %entry, %for.body
   %cmp = icmp ult i32 %3, %sub
   br i1 %cmp, label %for.body, label %for.end
 
 for.end:                                          ; preds = %for.body, %entry
   ret void
 
 ; CHECK-LABEL: @test1(
 
-; First check that we move the sub into the preheader, it doesn't have to be
-; executed if %cmp4 == false
-; CHECK: for.body.preheader:
-; CHECK: sub i32 %data_len, %sample
-; CHECK: br label %for.body
-
-; Second, check that we turn the IV test into an eq.
+; check that we turn the IV test into an eq.
 ; CHECK: %lftr.wideiv = trunc i64 %indvars.iv.next to i32
-; CHECK: %exitcond = icmp ne i32 %lftr.wideiv, %0
+; CHECK: %exitcond = icmp ne i32 %lftr.wideiv, %sub
 ; CHECK: br i1 %exitcond, label %for.body, label %for.end.loopexit
 }
 

llvm/trunk/test/Transforms/LoopStrengthReduce/post-inc-icmpzero.ll

 ; RUN: opt -loop-reduce -S < %s | FileCheck %s
 ; PR9939
 
 ; LSR should properly handle the post-inc offset when folding the
 ; non-IV operand of an icmp into the IV.
 
-; CHECK:   [[r1:%[a-z0-9]+]] = sub i64 %sub.ptr.lhs.cast, %sub.ptr.rhs.cast
-; CHECK:   [[r2:%[a-z0-9]+]] = lshr i64 [[r1]], 1
+; CHECK:   [[r1:%[a-z0-9\.]+]] = sub i64 %sub.ptr.lhs.cast, %sub.ptr.rhs.cast
+; CHECK:   [[r2:%[a-z0-9\.]+]] = lshr exact i64 [[r1]], 1
+; CHECK: for.body.lr.ph:
 ; CHECK:   [[r3:%[a-z0-9]+]] = shl i64 [[r2]], 1
 ; CHECK:   br label %for.body
 ; CHECK: for.body:
 ; CHECK:   %lsr.iv2 = phi i64 [ %lsr.iv.next, %for.body ], [ [[r3]], %for.body.lr.ph ]
 ; CHECK:   %lsr.iv.next = add i64 %lsr.iv2, -2
 ; CHECK:   %lsr.iv.next3 = inttoptr i64 %lsr.iv.next to i16*
 ; CHECK:   %cmp27 = icmp eq i16* %lsr.iv.next3, null