[UnrolledInstAnalyzer] Use MSSA to find stored values outside of loop.

[fhahn]

Summary

In UnrolledInstAnalyzer, we already simplify the addresses of loads
inside the loop to a base pointer and offset. We can use this
information to check if we can find a store outside the loop that is a
def for the load, if unrolled.o

To find potentially defining stores, this patch uses MemorySSA. I am not
entirely sure if it is a good idea to rely on MemorySSA here already.
@asbirlea, what do you think?

If it makes sense to use MemorySSA here, I'd make sure we preserve it
during loop unrolling. I guess we would have to make sure it gets
preserved until the next MemorySSA user in the pipeline, to negate the
compile time impact.

[asbirlea]

Here are a couple of answers/discussion points:

First of, could you please elaborate a bit more on what you're trying to check for? Is it stores before the loop, after the loop or both?
Normally we'd use the walker on the instruction (MSSA->getWalker()->getClobberingMemoryAccess(&I)) to look before the loop. Ideally we'd avoid going into the innards of MSSA in loop passes, so if a usecase not covered by the walker is needed that should be added either to a walker or to the updater.
It looks like a good use of MemorySSA, but the search should happen behind an API.

Secondly, in the new pass manager it is necessary for MSSA to be preserved by all loop passes in the same loop pipeline, because analyses are not actually invalidated until the entire loop pipeline is done. Hence it's possible to end up using an invalidated analysis and only notice this on a crash, miscompile or non-deterministic behavior. This occurred in D65060 and I tried to add a safety net in D66376 to prevent this from happening again (LPM2 will not use MSSA even if LoopUnroll is taught to preserve it, until all other passes in LPM2 all preserve it).

As far as preserving MemorySSA in LoopUnroll, this is a complex task. I had started work in this, but I did not complete it because unrolling does a lot of cloning/copying, and adding instructions "out of nowhere" to MSSA can lead to complex updates. It may be worth evaluating if updating MSSA is worth it for the unroll pass, or if it's faster to rebuild it from scratch. I did not get a chance to make this evaluation.

[fhahn]

In D67612#1671530, @asbirlea wrote:

Here are a couple of answers/discussion points:

First of, could you please elaborate a bit more on what you're trying to check for? Is it stores before the loop, after the loop or both?

The idea here is to check stores before the loop and use the store to determine the loaded value in a specific loop iteration. We only do that if we can determine a base pointer + constant offset for a certain loop iteration.

Normally we'd use the walker on the instruction (MSSA->getWalker()->getClobberingMemoryAccess(&I)) to look before the loop. Ideally we'd avoid going into the innards of MSSA in loop passes, so if a usecase not covered by the walker is needed that should be added either to a walker or to the updater.
It looks like a good use of MemorySSA, but the search should happen behind an API.

Right, but the walker just does a single step, which might not be the defining instructions we are looking for. Would the recommended way to implement this to implement a new walker, which just looks for a MemDef with said base pointer + offset?

Secondly, in the new pass manager it is necessary for MSSA to be preserved by all loop passes in the same loop pipeline, because analyses are not actually invalidated until the entire loop pipeline is done. Hence it's possible to end up using an invalidated analysis and only notice this on a crash, miscompile or non-deterministic behavior. This occurred in D65060 and I tried to add a safety net in D66376 to prevent this from happening again (LPM2 will not use MSSA even if LoopUnroll is taught to preserve it, until all other passes in LPM2 all preserve it).

As far as preserving MemorySSA in LoopUnroll, this is a complex task. I had started work in this, but I did not complete it because unrolling does a lot of cloning/copying, and adding instructions "out of nowhere" to MSSA can lead to complex updates. It may be worth evaluating if updating MSSA is worth it for the unroll pass, or if it's faster to rebuild it from scratch. I did not get a chance to make this evaluation.

Right, I expect this to be a fair bit of work, but I'd be happy to look into it as pre-requisite for this patch.

[asbirlea]

In D67612#1671599, @fhahn wrote:

In D67612#1671530, @asbirlea wrote:

Here are a couple of answers/discussion points:

First of, could you please elaborate a bit more on what you're trying to check for? Is it stores before the loop, after the loop or both?

The idea here is to check stores before the loop and use the store to determine the loaded value in a specific loop iteration. We only do that if we can determine a base pointer + constant offset for a certain loop iteration.

This is the part I do not understand. It looks like the LoadInst is considered "free" and not marked towards the cost of the unroll if there is a store with the same base pointer + offset.
Is that always the case? If there is an interfering MemoryAccess between the two (the walker's answer), then the LoadInst is not free.
I'm not that familiar with the code here, so feel free to correct me if I misunderstood.

Normally we'd use the walker on the instruction (MSSA->getWalker()->getClobberingMemoryAccess(&I)) to look before the loop. Ideally we'd avoid going into the innards of MSSA in loop passes, so if a usecase not covered by the walker is needed that should be added either to a walker or to the updater.
It looks like a good use of MemorySSA, but the search should happen behind an API.

Right, but the walker just does a single step, which might not be the defining instructions we are looking for. Would the recommended way to implement this to implement a new walker, which just looks for a MemDef with said base pointer + offset?

Yes, if this is your goal, having a new walker do this would be the way to go.

Secondly, in the new pass manager it is necessary for MSSA to be preserved by all loop passes in the same loop pipeline, because analyses are not actually invalidated until the entire loop pipeline is done. Hence it's possible to end up using an invalidated analysis and only notice this on a crash, miscompile or non-deterministic behavior. This occurred in D65060 and I tried to add a safety net in D66376 to prevent this from happening again (LPM2 will not use MSSA even if LoopUnroll is taught to preserve it, until all other passes in LPM2 all preserve it).

As far as preserving MemorySSA in LoopUnroll, this is a complex task. I had started work in this, but I did not complete it because unrolling does a lot of cloning/copying, and adding instructions "out of nowhere" to MSSA can lead to complex updates. It may be worth evaluating if updating MSSA is worth it for the unroll pass, or if it's faster to rebuild it from scratch. I did not get a chance to make this evaluation.

Right, I expect this to be a fair bit of work, but I'd be happy to look into it as pre-requisite for this patch.

[fhahn]

In D67612#1671613, @asbirlea wrote:

In D67612#1671599, @fhahn wrote:

The idea here is to check stores before the loop and use the store to determine the loaded value in a specific loop iteration. We only do that if we can determine a base pointer + constant offset for a certain loop iteration.

This is the part I do not understand. It looks like the LoadInst is considered "free" and not marked towards the cost of the unroll if there is a store with the same base pointer + offset.
Is that always the case? If there is an interfering MemoryAccess between the two (the walker's answer), then the LoadInst is not free.
I'm not that familiar with the code here, so feel free to correct me if I misunderstood.

It is probably more me not being as familiar with the MemorySSA API. I thought def_chain() would include all memory defs, that could clobber the load, in reverse order. With that in mind, if we hit a non-store or cannot compute the base pointer & offset, we exit. We probably also need another check to make sure we do not miss base pointers that alias. Does that make sense?

[fhahn]

In D67612#1671617, @fhahn wrote:

In D67612#1671613, @asbirlea wrote:

In D67612#1671599, @fhahn wrote:

The idea here is to check stores before the loop and use the store to determine the loaded value in a specific loop iteration. We only do that if we can determine a base pointer + constant offset for a certain loop iteration.

This is the part I do not understand. It looks like the LoadInst is considered "free" and not marked towards the cost of the unroll if there is a store with the same base pointer + offset.
Is that always the case? If there is an interfering MemoryAccess between the two (the walker's answer), then the LoadInst is not free.
I'm not that familiar with the code here, so feel free to correct me if I misunderstood.

It is probably more me not being as familiar with the MemorySSA API. I thought def_chain() would include all memory defs, that could clobber the load, in reverse order. With that in mind, if we hit a non-store or cannot compute the base pointer & offset, we exit. We probably also need another check to make sure we do not miss base pointers that alias. Does that make sense?

In other words, I was looking for a convenience method abstracts that walking as a range iterator.

[asbirlea]

Would something like this work for your purpose?

if (MSSA) {
    auto *D = MSSA->getWalker()->getClobberingMemoryAccess(&I);
    if (MemoryDef *MD = dyn_cast<MemoryDef>(D))
        if (StoreInst *SI = dyn_cast<StoreInst>(MD->getMemoryInst())) 
            if (Optional<SimplifiedAddress> MaybeSimpAddr =
                simplifyNonLoopAddress(SI->getPointerOperand()))
                if (MaybeSimpAddr->Base == AddrBase &&
                    MaybeSimpAddr->Offset == SimplifiedAddrOp)
                    return true;
}

I don't know if you want to return false; on some of those branches or continue with the checks below.

The walker will stop at the first access that may alias the Load. If it's not a Def, it's a Phi and it should give up, similarly if it's a Def but not a Store. Then, only if it's a store and has the conditions you added, the load can be folded/cost is ignored.

[fhahn]

In D67612#1671640, @asbirlea wrote:

Would something like this work for your purpose?

if (MSSA) {
    auto *D = MSSA->getWalker()->getClobberingMemoryAccess(&I);
    if (MemoryDef *MD = dyn_cast<MemoryDef>(D))
        if (StoreInst *SI = dyn_cast<StoreInst>(MD->getMemoryInst())) 
            if (Optional<SimplifiedAddress> MaybeSimpAddr =
                simplifyNonLoopAddress(SI->getPointerOperand()))
                if (MaybeSimpAddr->Base == AddrBase &&
                    MaybeSimpAddr->Offset == SimplifiedAddrOp)
                    return true;
}

I don't know if you want to return false; on some of those branches or continue with the checks below.

The walker will stop at the first access that may alias the Load. If it's not a Def, it's a Phi and it should give up, similarly if it's a Def but not a Store. Then, only if it's a store and has the conditions you added, the load can be folded/cost is ignored.

Yep, but that lets us only look at a single def, right? The load in the loop will be clobbered by multiple store, so the first one returned might not be the one we are interested in. Because we look at the load in a certain iteration, we may be able to simplify the pointer to a base pointer + constant offset. We should be able to skip MemDefs, if we can prove they store to different offsets for the same base pointer.

[asbirlea]

MSSA should have already done this verification. The walker will skip over stores that do not clobber the load or other MemoryAccess-es that do not interfere with the load.
So if there is a Store with the same pointer and different offset, the aliasing result for the two should be that they don't alias, and the walker will continue until it finds an access that does clobber the load.

[asbirlea]

Perhaps worth mentioning that the walker also does phi translation when walking defs upward.

[efriedma]

I think I see the gap in communication here.

If you ask MSSA for the closest definition for a load inside a loop, it will return the closest store which might alias the load at any iteration. This is what you want if you want to, for example, eliminate a load using a stored value.

What we really want here, though, is not MSSA for the load, as it exists in the loop. Instead the question is, what would MSSA return after the loop is unrolled? (It might not return the same def: alias analysis has more information after unrolling.) We could speculatively unroll the loop and recompute MSSA, but that would be really expensive. Instead, the code here is walking through the defs to try to find the def that will be relevant after unrolling.

[fhahn]

In D67612#1681623, @efriedma wrote:

I think I see the gap in communication here.

If you ask MSSA for the closest definition for a load inside a loop, it will return the closest store which might alias the load at any iteration. This is what you want if you want to, for example, eliminate a load using a stored value.

What we really want here, though, is not MSSA for the load, as it exists in the loop. Instead the question is, what would MSSA return after the loop is unrolled? (It might not return the same def: alias analysis has more information after unrolling.) We could speculatively unroll the loop and recompute MSSA, but that would be really expensive. Instead, the code here is walking through the defs to try to find the def that will be relevant after unrolling.

Thanks for clarifying Eli! @asbirlea, does this make more sense now?

For a bit more context: UnrolledInstAnalyzer simulates unrolling the loop and for each iteration it tries to estimate what can be simplified in that iteration. So when it analyzes the first iteration, it knows what the concrete value of the induction variable will be. If we can simplify an address computation to a base address + offset using that information, we look at clobbering stores outside the loop of the original load, and see if we can find a store that stores exactly to the same location. Note that memorySSA does not have this additional information and the load in the loop will be clobbered by any store that involves an address covered by the loop.

The underlying motivation to do that is that such store/load pairs can be eliminated after unrolling and should not count towards the size of the unrolled loop.

[fhahn]

ping

@asbirlea do the additional comments by Eli and myself make things clearer (sorry for just coming back to this now)

[asbirlea]

Sorry, I forgot about this one, thank you for the reminder!

Yes, the explanation makes sense to me.

I would go with adding the logic for how to walk the defs into a Walker.
There are quite a few things that need to be changed in the above code using the def_chain.
e.g.:
There are no MemoryUses, so that check is not needed.
The chain stops at a MemoryPhi, where you currently break (give up). The way this is written right now, this will always break, and it can be improved with walking the backedge (walkers do this).
The def_chain starts off by getting the defining access for the given Load (Use), which may skip Stores (Defs) it does not alias in the same iteration. But that load may alias the stores in another iteration, so walking *all* defs above current use seems appropriate.
I don't know how nested loops are handled here.

llvm/include/llvm/Analysis/LoopUnrollAnalyzer.h

 // potential effects that loop unrolling might have, such as enabling constant
 // propagation and other optimizations.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_LOOPUNROLLANALYZER_H
 #define LLVM_ANALYSIS_LOOPUNROLLANALYZER_H
 
+#include "llvm/ADT/Optional.h"
 #include "llvm/Analysis/InstructionSimplify.h"
+#include "llvm/Analysis/MemorySSA.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
 #include "llvm/IR/InstVisitor.h"
 
 // This class is used to get an estimate of the optimization effects that we
 // could get from complete loop unrolling. It comes from the fact that some
 // loads might be replaced with concrete constant values and that could trigger
 // a chain of instruction simplifications.
 //
class UnrolledInstAnalyzer : private InstVisitor<UnrolledInstAnalyzer, bool> {
   struct SimplifiedAddress {
     Value *Base = nullptr;
     ConstantInt *Offset = nullptr;
   };
 
 public:
   UnrolledInstAnalyzer(unsigned Iteration,
                        DenseMap<Value *, Constant *> &SimplifiedValues,
-                       ScalarEvolution &SE, const Loop *L)
-      : SimplifiedValues(SimplifiedValues), SE(SE), L(L) {
-      IterationNumber = SE.getConstant(APInt(64, Iteration));
+                       ScalarEvolution &SE, const Loop *L, MemorySSA *MSSA)
+      : SimplifiedValues(SimplifiedValues), SE(SE), L(L), MSSA(MSSA) {
   }
 
   // Allow access to the initial visit method.
   using Base::visit;
 
 private:
   /// A cache of pointer bases and constant-folded offsets corresponding
   /// to GEP (or derived from GEP) instructions.
private:
   /// of simplified values specific to this iteration.  The idea is to propagate
   /// any special information we have about loads that can be replaced with
   /// constants after complete unrolling, and account for likely simplifications
   /// post-unrolling.
   DenseMap<Value *, Constant *> &SimplifiedValues;
 
   ScalarEvolution &SE;
   const Loop *L;
+  MemorySSA *MSSA;
 
   bool simplifyInstWithSCEV(Instruction *I);
 
   /// Try to simplify an address computation outside of the loop body, so we can
   /// compare it with simplified addresses in the loop.
-  void simplifyNonLoopAddress(Value *V);
+  Optional<SimplifiedAddress> simplifyNonLoopAddress(Value *V);
 
   bool visitInstruction(Instruction &I) { return simplifyInstWithSCEV(&I); }
   bool visitBinaryOperator(BinaryOperator &I);
   bool visitLoad(LoadInst &I);
   bool visitCastInst(CastInst &I);
   bool visitCmpInst(CmpInst &I);
   bool visitPHINode(PHINode &PN);
 };
 }
 #endif

llvm/include/llvm/Transforms/Utils/UnrollLoop.h

 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H
 #define LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/StringRef.h"
+#include "llvm/Analysis/MemorySSA.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/Transforms/Utils/ValueMapper.h"
 
 namespace llvm {
 
 class AssumptionCache;
 class BasicBlock;
 class BlockFrequencyInfo;
LoopUnrollResult UnrollAndJamLoop(Loop *L, unsigned Count, unsigned TripCount,
                                   Loop **EpilogueLoop = nullptr);
 
 bool isSafeToUnrollAndJam(Loop *L, ScalarEvolution &SE, DominatorTree &DT,
                           DependenceInfo &DI);
 
 bool computeUnrollCount(Loop *L, const TargetTransformInfo &TTI,
                         DominatorTree &DT, LoopInfo *LI, ScalarEvolution &SE,
                         const SmallPtrSetImpl<const Value *> &EphValues,
-                        OptimizationRemarkEmitter *ORE, unsigned &TripCount,
-                        unsigned MaxTripCount, unsigned &TripMultiple,
-                        unsigned LoopSize,
+                        OptimizationRemarkEmitter *ORE, MemorySSA *MSSA,
+                        unsigned &TripCount, unsigned MaxTripCount,
+                        unsigned &TripMultiple, unsigned LoopSize,
                         TargetTransformInfo::UnrollingPreferences &UP,
                         bool &UseUpperBound);
 
 void remapInstruction(Instruction *I, ValueToValueMapTy &VMap);
 
 void simplifyLoopAfterUnroll(Loop *L, bool SimplifyIVs, LoopInfo *LI,
                              ScalarEvolution *SE, DominatorTree *DT,
                              AssumptionCache *AC);

llvm/lib/Analysis/LoopUnrollAnalyzer.cpp

if (!Offset)
     return false;
   SimplifiedAddress Address;
   Address.Base = Base->getValue();
   Address.Offset = Offset->getValue();
   SimplifiedAddresses[I] = Address;
   return false;
 }
 
-void UnrolledInstAnalyzer::simplifyNonLoopAddress(Value *V) {
+Optional<UnrolledInstAnalyzer::SimplifiedAddress>
+UnrolledInstAnalyzer::simplifyNonLoopAddress(Value *V) {
   Instruction *Inst = dyn_cast<Instruction>(V);
   // For now we only try to simplify address computation instructions outside
   // the current loop.
   if (!Inst || !Inst->getType()->isPointerTy() ||
       !SE.isSCEVable(Inst->getType()) || L->contains(Inst))
-    return;
+    return {};
   auto Iter = SimplifiedAddresses.find(Inst);
   if (Iter != SimplifiedAddresses.end())
-    return;
+    return {};
 
   const SCEV *S = SE.getSCEV(Inst);
   // Check if the offset from the base address becomes a constant.
   auto *Base = dyn_cast<SCEVUnknown>(SE.getPointerBase(S));
   if (!Base)
-    return;
+    return {};
   auto *Offset = dyn_cast<SCEVConstant>(SE.getMinusSCEV(S, Base));
   if (!Offset)
-    return;
+    return {};
 
   SimplifiedAddress Address;
   Address.Base = Base->getValue();
   Address.Offset = Offset->getValue();
   SimplifiedAddresses[V] = Address;
+  return Address;
 }
 
 /// Try to simplify binary operator I.
 ///
 /// TODO: Probably it's worth to hoist the code for estimating the
 /// simplifications effects to a separate class, since we have a very similar
 /// code in InlineCost already.
 bool UnrolledInstAnalyzer::visitBinaryOperator(BinaryOperator &I) {

 /// Try to fold load I.
 bool UnrolledInstAnalyzer::visitLoad(LoadInst &I) {
   Value *AddrOp = I.getPointerOperand();
 
   auto AddressIt = SimplifiedAddresses.find(AddrOp);
   if (AddressIt == SimplifiedAddresses.end())
     return false;
   ConstantInt *SimplifiedAddrOp = AddressIt->second.Offset;
+  Value *AddrBase = AddressIt->second.Base;
 
-  auto *GV = dyn_cast<GlobalVariable>(AddressIt->second.Base);
+  if (MSSA) {
+    // Try to find a defining store using the simplified address of the load.
+    const MemoryAccess *MemAcc = MSSA->getMemoryAccess(&I);
+    for (auto *D : def_chain(MemAcc)) {
+      if (isa<MemoryUse>(D))
+        continue;
+      const MemoryDef *MD = dyn_cast<MemoryDef>(D);
+      if (!MD)
+        break;
+      StoreInst *SI = dyn_cast_or_null<StoreInst>(MD->getMemoryInst());
+      if (!SI)
+        break;
+      Optional<SimplifiedAddress> MaybeSimpAddr =
+          simplifyNonLoopAddress(SI->getPointerOperand());
+      if (!MaybeSimpAddr)
+        break;
+
+      if (MaybeSimpAddr->Base == AddrBase &&
+          MaybeSimpAddr->Offset == SimplifiedAddrOp)
+        return true;
+    }
+  }
+
+  auto *GV = dyn_cast<GlobalVariable>(AddrBase);
   // We're only interested in loads that can be completely folded to a
   // constant.
   if (!GV || !GV->hasDefinitiveInitializer() || !GV->isConstant())
     return false;
 
   ConstantDataSequential *CDS =
       dyn_cast<ConstantDataSequential>(GV->getInitializer());
   if (!CDS)

llvm/lib/Transforms/Scalar/LoopUnrollAndJamPass.cpp

static bool computeUnrollAndJamCount(
   // First up use computeUnrollCount from the loop unroller to get a count
   // for unrolling the outer loop, plus any loops requiring explicit
   // unrolling we leave to the unroller. This uses UP.Threshold /
   // UP.PartialThreshold / UP.MaxCount to come up with sensible loop values.
   // We have already checked that the loop has no unroll.* pragmas.
   unsigned MaxTripCount = 0;
   bool UseUpperBound = false;
   bool ExplicitUnroll = computeUnrollCount(
-      L, TTI, DT, LI, SE, EphValues, ORE, OuterTripCount, MaxTripCount,
+      L, TTI, DT, LI, SE, EphValues, ORE, nullptr, OuterTripCount, MaxTripCount,
       OuterTripMultiple, OuterLoopSize, UP, UseUpperBound);
   if (ExplicitUnroll || UseUpperBound) {
     // If the user explicitly set the loop as unrolled, dont UnJ it. Leave it
     // for the unroller instead.
     LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; explicit count set by "
                          "computeUnrollCount\n");
     UP.Count = 0;
     return false;

llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp

 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/BlockFrequencyInfo.h"
 #include "llvm/Analysis/CodeMetrics.h"
 #include "llvm/Analysis/LazyBlockFrequencyInfo.h"
 #include "llvm/Analysis/LoopAnalysisManager.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/LoopPass.h"
 #include "llvm/Analysis/LoopUnrollAnalyzer.h"
+#include "llvm/Analysis/MemorySSA.h"
 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
 #include "llvm/Analysis/ProfileSummaryInfo.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/Constants.h"

 /// (UnrolledCost) and dynamic cost of the original loop (RolledDynamicCost). By
 /// dynamic cost we mean that we won't count costs of blocks that are known not
 /// to be executed (i.e. if we have a branch in the loop and we know that at the
 /// given iteration its condition would be resolved to true, we won't add up the
 /// cost of the 'false'-block).
 /// \returns Optional value, holding the RolledDynamicCost and UnrolledCost. If
 /// the analysis failed (no benefits expected from the unrolling, or the loop is
 /// too big to analyze), the returned value is None.
-static Optional<EstimatedUnrollCost> analyzeLoopUnrollCost(
-    const Loop *L, unsigned TripCount, DominatorTree &DT, ScalarEvolution &SE,
+static Optional<EstimatedUnrollCost>
+analyzeLoopUnrollCost(const Loop *L, unsigned TripCount, DominatorTree &DT,
+                      ScalarEvolution &SE,
                       const SmallPtrSetImpl<const Value *> &EphValues,
-    const TargetTransformInfo &TTI, unsigned MaxUnrolledLoopSize) {
+                      const TargetTransformInfo &TTI, MemorySSA *MSSA,
+                      unsigned MaxUnrolledLoopSize) {
   // We want to be able to scale offsets by the trip count and add more offsets
   // to them without checking for overflows, and we already don't want to
   // analyze *massive* trip counts, so we force the max to be reasonably small.
   assert(UnrollMaxIterationsCountToAnalyze <
              (unsigned)(std::numeric_limits<int>::max() / 2) &&
          "The unroll iterations max is too large!");
 
   // Only analyze inner loops. We can't properly estimate cost of nested loops
for (Instruction &I : *L->getHeader()) {
         SimplifiedInputValues.push_back({PHI, C});
     }
 
     // Now clear and re-populate the map for the next iteration.
     SimplifiedValues.clear();
     while (!SimplifiedInputValues.empty())
       SimplifiedValues.insert(SimplifiedInputValues.pop_back_val());
 
-    UnrolledInstAnalyzer Analyzer(Iteration, SimplifiedValues, SE, L);
+    UnrolledInstAnalyzer Analyzer(Iteration, SimplifiedValues, SE, L, MSSA);
 
     BBWorklist.clear();
     BBWorklist.insert(L->getHeader());
     // Note that we *must not* cache the size, this loop grows the worklist.
     for (unsigned Idx = 0; Idx != BBWorklist.size(); ++Idx) {
       BasicBlock *BB = BBWorklist[Idx];
 
       // Visit all instructions in the given basic block and try to simplify

 // that are specific to to the LoopUnroll pass (which, for instance, are
 // irrelevant for the LoopUnrollAndJam pass).
 // FIXME: This function is used by LoopUnroll and LoopUnrollAndJam, but consumes
 // many LoopUnroll-specific options. The shared functionality should be
 // refactored into it own function.
 bool llvm::computeUnrollCount(
     Loop *L, const TargetTransformInfo &TTI, DominatorTree &DT, LoopInfo *LI,
     ScalarEvolution &SE, const SmallPtrSetImpl<const Value *> &EphValues,
-    OptimizationRemarkEmitter *ORE, unsigned &TripCount, unsigned MaxTripCount,
-    unsigned &TripMultiple, unsigned LoopSize,
+    OptimizationRemarkEmitter *ORE, MemorySSA *MSSA, unsigned &TripCount,
+    unsigned MaxTripCount, unsigned &TripMultiple, unsigned LoopSize,
     TargetTransformInfo::UnrollingPreferences &UP, bool &UseUpperBound) {
 
   // Check for explicit Count.
   // 1st priority is unroll count set by "unroll-count" option.
   bool UserUnrollCount = UnrollCount.getNumOccurrences() > 0;
   if (UserUnrollCount) {
     UP.Count = UnrollCount;
     UP.AllowExpensiveTripCount = true;
if (getUnrolledLoopSize(LoopSize, UP) < UP.Threshold) {
       TripCount = FullUnrollTripCount;
       TripMultiple = UP.UpperBound ? 1 : TripMultiple;
       return ExplicitUnroll;
     } else {
       // The loop isn't that small, but we still can fully unroll it if that
       // helps to remove a significant number of instructions.
       // To check that, run additional analysis on the loop.
       if (Optional<EstimatedUnrollCost> Cost = analyzeLoopUnrollCost(
-              L, FullUnrollTripCount, DT, SE, EphValues, TTI,
+              L, FullUnrollTripCount, DT, SE, EphValues, TTI, MSSA,
               UP.Threshold * UP.MaxPercentThresholdBoost / 100)) {
         unsigned Boost =
             getFullUnrollBoostingFactor(*Cost, UP.MaxPercentThresholdBoost);
         if (Cost->UnrolledCost < UP.Threshold * Boost / 100) {
           UseUpperBound = (MaxTripCount == FullUnrollTripCount);
           TripCount = FullUnrollTripCount;
           TripMultiple = UP.UpperBound ? 1 : TripMultiple;
           return ExplicitUnroll;
if (UP.Count < 2)
     UP.Count = 0;
   return ExplicitUnroll;
 }
 
 static LoopUnrollResult tryToUnrollLoop(
     Loop *L, DominatorTree &DT, LoopInfo *LI, ScalarEvolution &SE,
     const TargetTransformInfo &TTI, AssumptionCache &AC,
     OptimizationRemarkEmitter &ORE, BlockFrequencyInfo *BFI,
-    ProfileSummaryInfo *PSI, bool PreserveLCSSA, int OptLevel,
+    ProfileSummaryInfo *PSI, MemorySSA *MSSA, bool PreserveLCSSA, int OptLevel,
     bool OnlyWhenForced, bool ForgetAllSCEV, Optional<unsigned> ProvidedCount,
     Optional<unsigned> ProvidedThreshold, Optional<bool> ProvidedAllowPartial,
     Optional<bool> ProvidedRuntime, Optional<bool> ProvidedUpperBound,
     Optional<bool> ProvidedAllowPeeling,
     Optional<bool> ProvidedAllowProfileBasedPeeling) {
   LLVM_DEBUG(dbgs() << "Loop Unroll: F["
                     << L->getHeader()->getParent()->getName() << "] Loop %"
                     << L->getHeader()->getName() << "\n");
if (!(UP.UpperBound || MaxOrZero) || MaxTripCount > UnrollMaxUpperBound) {
       MaxTripCount = 0;
     }
   }
 
   // computeUnrollCount() decides whether it is beneficial to use upper bound to
   // fully unroll the loop.
   bool UseUpperBound = false;
   bool IsCountSetExplicitly = computeUnrollCount(
-      L, TTI, DT, LI, SE, EphValues, &ORE, TripCount, MaxTripCount,
+      L, TTI, DT, LI, SE, EphValues, &ORE, MSSA, TripCount, MaxTripCount,
       TripMultiple, LoopSize, UP, UseUpperBound);
   if (!UP.Count)
     return LoopUnrollResult::Unmodified;
   // Unroll factor (Count) must be less or equal to TripCount.
   if (TripCount && UP.Count > TripCount)
     UP.Count = TripCount;
 
   // Save loop properties before it is transformed.
bool runOnLoop(Loop *L, LPPassManager &LPM) override {
     const TargetTransformInfo &TTI =
         getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
     auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
     // For the old PM, we can't use OptimizationRemarkEmitter as an analysis
     // pass.  Function analyses need to be preserved across loop transformations
     // but ORE cannot be preserved (see comment before the pass definition).
     OptimizationRemarkEmitter ORE(&F);
     bool PreserveLCSSA = mustPreserveAnalysisID(LCSSAID);
+    MemorySSA *MSSA = &getAnalysis<MemorySSAWrapperPass>().getMSSA();
 
-    LoopUnrollResult Result = tryToUnrollLoop(
-        L, DT, LI, SE, TTI, AC, ORE, nullptr, nullptr, PreserveLCSSA, OptLevel,
-        OnlyWhenForced, ForgetAllSCEV, ProvidedCount, ProvidedThreshold,
-        ProvidedAllowPartial, ProvidedRuntime, ProvidedUpperBound,
+    LoopUnrollResult Result =
+        tryToUnrollLoop(L, DT, LI, SE, TTI, AC, ORE, nullptr, nullptr, MSSA,
+                        PreserveLCSSA, OptLevel, OnlyWhenForced, ForgetAllSCEV,
+                        ProvidedCount, ProvidedThreshold, ProvidedAllowPartial,
+                        ProvidedRuntime, ProvidedUpperBound,
                         ProvidedAllowPeeling, ProvidedAllowProfileBasedPeeling);
 
     if (Result == LoopUnrollResult::FullyUnrolled)
       LPM.markLoopAsDeleted(*L);
 
     return Result != LoopUnrollResult::Unmodified;
   }
 
   /// This transformation requires natural loop information & requires that
   /// loop preheaders be inserted into the CFG...
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<AssumptionCacheTracker>();
     AU.addRequired<TargetTransformInfoWrapperPass>();
+    AU.addRequired<MemorySSAWrapperPass>();
     // FIXME: Loop passes are required to preserve domtree, and for now we just
     // recreate dom info if anything gets unrolled.
     getLoopAnalysisUsage(AU);
   }
 };
 
 } // end anonymous namespace
 
 char LoopUnroll::ID = 0;
 
 INITIALIZE_PASS_BEGIN(LoopUnroll, "loop-unroll", "Unroll loops", false, false)
 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
 INITIALIZE_PASS_DEPENDENCY(LoopPass)
+INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
 INITIALIZE_PASS_END(LoopUnroll, "loop-unroll", "Unroll loops", false, false)
 
 Pass *llvm::createLoopUnrollPass(int OptLevel, bool OnlyWhenForced,
                                  bool ForgetAllSCEV, int Threshold, int Count,
                                  int AllowPartial, int Runtime, int UpperBound,
                                  int AllowPeeling) {
   // TODO: It would make more sense for this function to take the optionals
PreservedAnalyses LoopFullUnrollPass::run(Loop &L, LoopAnalysisManager &AM,
 
   auto *ORE = FAM.getCachedResult<OptimizationRemarkEmitterAnalysis>(*F);
   // FIXME: This should probably be optional rather than required.
   if (!ORE)
     report_fatal_error(
         "LoopFullUnrollPass: OptimizationRemarkEmitterAnalysis not "
         "cached at a higher level");
 
+  auto *MSSAA = FAM.getCachedResult<MemorySSAAnalysis>(*F);
+  MemorySSA *MSSA = MSSAA ? &MSSAA->getMSSA() : nullptr;
   // Keep track of the previous loop structure so we can identify new loops
   // created by unrolling.
   Loop *ParentL = L.getParentLoop();
   SmallPtrSet<Loop *, 4> OldLoops;
   if (ParentL)
     OldLoops.insert(ParentL->begin(), ParentL->end());
   else
     OldLoops.insert(AR.LI.begin(), AR.LI.end());
 
   std::string LoopName = L.getName();
 
   bool Changed = tryToUnrollLoop(&L, AR.DT, &AR.LI, AR.SE, AR.TTI, AR.AC, *ORE,
-                                 /*BFI*/ nullptr, /*PSI*/ nullptr,
+                                 /*BFI*/ nullptr, /*PSI*/ nullptr, MSSA,
                                  /*PreserveLCSSA*/ true, OptLevel,
                                  OnlyWhenForced, ForgetSCEV, /*Count*/ None,
                                  /*Threshold*/ None, /*AllowPartial*/ false,
                                  /*Runtime*/ false, /*UpperBound*/ false,
                                  /*AllowPeeling*/ false,
                                  /*AllowProfileBasedPeeling*/ false) !=
                  LoopUnrollResult::Unmodified;
   if (!Changed)

 PreservedAnalyses LoopUnrollPass::run(Function &F,
                                       FunctionAnalysisManager &AM) {
   auto &SE = AM.getResult<ScalarEvolutionAnalysis>(F);
   auto &LI = AM.getResult<LoopAnalysis>(F);
   auto &TTI = AM.getResult<TargetIRAnalysis>(F);
   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
   auto &AC = AM.getResult<AssumptionAnalysis>(F);
   auto &ORE = AM.getResult<OptimizationRemarkEmitterAnalysis>(F);
+  auto &MSSA = AM.getResult<MemorySSAAnalysis>(F).getMSSA();
 
   LoopAnalysisManager *LAM = nullptr;
   if (auto *LAMProxy = AM.getCachedResult<LoopAnalysisManagerFunctionProxy>(F))
     LAM = &LAMProxy->getManager();
 
   const ModuleAnalysisManager &MAM =
       AM.getResult<ModuleAnalysisManagerFunctionProxy>(F).getManager();
   ProfileSummaryInfo *PSI =
#endif
     // bloating it further.
     Optional<bool> LocalAllowPeeling = UnrollOpts.AllowPeeling;
     if (PSI && PSI->hasHugeWorkingSetSize())
       LocalAllowPeeling = false;
     std::string LoopName = L.getName();
     // The API here is quite complex to call and we allow to select some
     // flavors of unrolling during construction time (by setting UnrollOpts).
     LoopUnrollResult Result = tryToUnrollLoop(
-        &L, DT, &LI, SE, TTI, AC, ORE, BFI, PSI,
+        &L, DT, &LI, SE, TTI, AC, ORE, BFI, PSI, &MSSA,
         /*PreserveLCSSA*/ true, UnrollOpts.OptLevel, UnrollOpts.OnlyWhenForced,
         UnrollOpts.ForgetSCEV, /*Count*/ None,
         /*Threshold*/ None, UnrollOpts.AllowPartial, UnrollOpts.AllowRuntime,
         UnrollOpts.AllowUpperBound, LocalAllowPeeling,
         UnrollOpts.AllowProfileBasedPeeling);
     Changed |= Result != LoopUnrollResult::Unmodified;
 
     // The parent must not be damaged by unrolling!

llvm/test/Transforms/LoopUnroll/unrolled-inst-analyzer-pointers.ll

 ; RUN: opt -loop-unroll -debug < %s 2>&1 | FileCheck %s
 
 ; REQUIRES: asserts
 
 ; Check that we simplify pointers outside of the loop for comparisons.
-; %cmp1.i.i is free when unrolling.
+; %cmp1.i.i is free when unrolling, so is the load %.pre3
 
 define i32 @test_2_iters(i32 %a, i32 %b, i32 %c, i32 %d) optsize {
 ; CHECK-LABEL: Loop Unroll: F[test_2_iters] Loop %loop
 ; CHECK-NEXT:  Loop Size = 7
 ; CHECK-NEXT:  Starting LoopUnroll profitability analysis...
 ; CHECK-NEXT:   Analyzing iteration 0
 ; CHECK-NEXT:   Analyzing iteration 1
 ; CHECK-NEXT:  Adding cost of instruction (iteration 1): 1   %spec.select.i.i = select i1 %cmp.i.i.i, i32* %incdec.ptr.i.i8, i32* %spec.select.i.i7
 ; CHECK-NEXT:  Adding cost of instruction (iteration 1): 1   %cmp.i.i.i = icmp slt i32 %.pre, %.pre3
+; CHECK-NEXT:  Adding cost of instruction (iteration 1): 1   %.pre = load i32, i32* %spec.select.i.i7, align 4
+; CHECK-NEXT:  Adding cost of instruction (iteration 0): 1   %incdec.ptr.i.i = getelementptr inbounds i32, i32* %incdec.ptr.i.i8, i64 1
+; CHECK-NEXT:  Adding cost of instruction (iteration 0): 1   %spec.select.i.i = select i1 %cmp.i.i.i, i32* %incdec.ptr.i.i8, i32* %spec.select.i.i7
+; CHECK-NEXT:  Adding cost of instruction (iteration 0): 1   %cmp.i.i.i = icmp slt i32 %.pre, %.pre3
+; CHECK-NEXT:  Adding cost of instruction (iteration 0): 1   %.pre = load i32, i32* %spec.select.i.i7, align 4
+; CHECK-NEXT:  Analysis finished:
+; CHECK-NEXT:    UnrolledCost: 7, RolledDynamicCost: 14
+
+
+entry:
+  %ref.tmp = alloca [4 x i32], align 4
+  %0 = bitcast [4 x i32]* %ref.tmp to i8*
+  %arrayinit.begin = getelementptr inbounds [4 x i32], [4 x i32]* %ref.tmp, i64 0, i64 0
+  store i32 %a, i32* %arrayinit.begin, align 4
+  %arrayinit.element = getelementptr inbounds [4 x i32], [4 x i32]* %ref.tmp, i64 0, i64 1
+  store i32 %b, i32* %arrayinit.element, align 4
+  %arrayinit.element1 = getelementptr inbounds [4 x i32], [4 x i32]* %ref.tmp, i64 0, i64 2
+  store i32 %c, i32* %arrayinit.element1, align 4
+  %arrayinit.element2 = getelementptr inbounds [4 x i32], [4 x i32]* %ref.tmp, i64 0, i64 3
+  store i32 %d, i32* %arrayinit.element2, align 4
+  %add.ptr.i.i = getelementptr inbounds [4 x i32], [4 x i32]* %ref.tmp, i64 0, i64 4
+  %cmp.i.i.i4 = icmp slt i32 %a, %b
+  %spec.select.i.i5 = select i1 %cmp.i.i.i4, i32* %arrayinit.element, i32* %arrayinit.begin
+  %incdec.ptr.i.i6 = getelementptr inbounds [4 x i32], [4 x i32]* %ref.tmp, i64 0, i64 2
+  br label %loop
+
+loop:                           ; preds = %entry, %loop
+  %incdec.ptr.i.i8 = phi i32* [ %incdec.ptr.i.i6, %entry ], [ %incdec.ptr.i.i, %loop ]
+  %spec.select.i.i7 = phi i32* [ %spec.select.i.i5, %entry ], [ %spec.select.i.i, %loop ]
+  %.pre = load i32, i32* %spec.select.i.i7, align 4
+  %.pre3 = load i32, i32* %incdec.ptr.i.i8, align 4
+  %cmp.i.i.i = icmp slt i32 %.pre, %.pre3
+  %spec.select.i.i = select i1 %cmp.i.i.i, i32* %incdec.ptr.i.i8, i32* %spec.select.i.i7
+  %incdec.ptr.i.i = getelementptr inbounds i32, i32* %incdec.ptr.i.i8, i64 1
+  %cmp1.i.i = icmp eq i32* %incdec.ptr.i.i, %add.ptr.i.i
+  br i1 %cmp1.i.i, label %exit, label %loop
+
+exit:                           ; preds = %loop
+  %1 = load i32, i32* %spec.select.i.i, align 4
+  ret i32 %1
+}
+
+
+; Same as test_2_iters, except that we have a store to an unknown index,
+; potentially clobbering all stores with known indices.
+
+define i32 @test_2_iters_unknown_clobber(i32 %a, i32 %b, i32 %c, i32 %d, i64 %idx) optsize {
+; CHECK-LABEL: Loop Unroll: F[test_2_iters_unknown_clobber] Loop %loop
+; CHECK-NEXT:  Loop Size = 7
+; CHECK-NEXT:  Starting LoopUnroll profitability analysis...
+; CHECK-NEXT:   Analyzing iteration 0
+; CHECK-NEXT:   Analyzing iteration 1
+; CHECK-NEXT:  Adding cost of instruction (iteration 1): 1   %spec.select.i.i = select i1 %cmp.i.i.i, i32* %incdec.ptr.i.i8, i32* %spec.select.i.i7
+; CHECK-NEXT:  Adding cost of instruction (iteration 1): 1   %cmp.i.i.i = icmp slt i32 %.pre, %.pre3
 ; CHECK-NEXT:  Adding cost of instruction (iteration 1): 1   %.pre3 = load i32, i32* %incdec.ptr.i.i8, align 4
 ; CHECK-NEXT:  Adding cost of instruction (iteration 1): 1   %.pre = load i32, i32* %spec.select.i.i7, align 4
 ; CHECK-NEXT:  Adding cost of instruction (iteration 0): 1   %incdec.ptr.i.i = getelementptr inbounds i32, i32* %incdec.ptr.i.i8, i64 1
 ; CHECK-NEXT:  Adding cost of instruction (iteration 0): 1   %spec.select.i.i = select i1 %cmp.i.i.i, i32* %incdec.ptr.i.i8, i32* %spec.select.i.i7
 ; CHECK-NEXT:  Adding cost of instruction (iteration 0): 1   %cmp.i.i.i = icmp slt i32 %.pre, %.pre3
 ; CHECK-NEXT:  Adding cost of instruction (iteration 0): 1   %.pre3 = load i32, i32* %incdec.ptr.i.i8, align 4
 ; CHECK-NEXT:  Adding cost of instruction (iteration 0): 1   %.pre = load i32, i32* %spec.select.i.i7, align 4
 ; CHECK-NEXT:  Analysis finished:
 ; CHECK-NEXT:    UnrolledCost: 9, RolledDynamicCost: 14
-
-
 entry:
   %ref.tmp = alloca [4 x i32], align 4
   %0 = bitcast [4 x i32]* %ref.tmp to i8*
   %arrayinit.begin = getelementptr inbounds [4 x i32], [4 x i32]* %ref.tmp, i64 0, i64 0
   store i32 %a, i32* %arrayinit.begin, align 4
   %arrayinit.element = getelementptr inbounds [4 x i32], [4 x i32]* %ref.tmp, i64 0, i64 1
   store i32 %b, i32* %arrayinit.element, align 4
   %arrayinit.element1 = getelementptr inbounds [4 x i32], [4 x i32]* %ref.tmp, i64 0, i64 2
   store i32 %c, i32* %arrayinit.element1, align 4
   %arrayinit.element2 = getelementptr inbounds [4 x i32], [4 x i32]* %ref.tmp, i64 0, i64 3
   store i32 %d, i32* %arrayinit.element2, align 4
+  %arrayinit.element3 = getelementptr inbounds [4 x i32], [4 x i32]* %ref.tmp, i64 0, i64 %idx
+  store i32 %d, i32* %arrayinit.element3, align 4
   %add.ptr.i.i = getelementptr inbounds [4 x i32], [4 x i32]* %ref.tmp, i64 0, i64 4
   %cmp.i.i.i4 = icmp slt i32 %a, %b
   %spec.select.i.i5 = select i1 %cmp.i.i.i4, i32* %arrayinit.element, i32* %arrayinit.begin
   %incdec.ptr.i.i6 = getelementptr inbounds [4 x i32], [4 x i32]* %ref.tmp, i64 0, i64 2
   br label %loop
 
 loop:                           ; preds = %entry, %loop
   %incdec.ptr.i.i8 = phi i32* [ %incdec.ptr.i.i6, %entry ], [ %incdec.ptr.i.i, %loop ]

llvm/unittests/Analysis/UnrollAnalyzerTest.cpp

bool runOnFunction(Function &F) override {
     BasicBlock *Header = &*FI++;
     Loop *L = LI->getLoopFor(Header);
     BasicBlock *Exiting = L->getExitingBlock();
 
     SimplifiedValuesVector.clear();
     TripCount = SE->getSmallConstantTripCount(L, Exiting);
     for (unsigned Iteration = 0; Iteration < TripCount; Iteration++) {
       DenseMap<Value *, Constant *> SimplifiedValues;
-      UnrolledInstAnalyzer Analyzer(Iteration, SimplifiedValues, *SE, L);
+      UnrolledInstAnalyzer Analyzer(Iteration, SimplifiedValues, *SE, L,
+                                    nullptr);
       for (auto *BB : L->getBlocks())
         for (Instruction &I : *BB)
           Analyzer.visit(I);
       SimplifiedValuesVector.push_back(SimplifiedValues);
     }
     return false;
   }
   void getAnalysisUsage(AnalysisUsage &AU) const override {