[SROA] propagate !range metadata when moving loads

[arielb1]

Summary

This tries to propagate !range metadata to a pre-existing load when a load is optimized out. This is done instead of adding an assume because converting loads to and from assumes creates a lot of IR.

This requires D37215 in order to work, but I've put it in a separate patch because it affects a different section of the code (and also for easier bisection if this introduces a regression).

[hfinkel]

lib/Transforms/Utils/Local.cpp

1898

return here.

lib/Transforms/Utils/PromoteMemoryToRegister.cpp

315

Huh?

318

Brace on previous line.

328

Two space indent.

329

We should refactor this (calling this function here seems odd - the load is not an assume). I think that you're trying to reuse the logic here for the dominance checking, which is fine, but you don't need the isEphemeralValueOf check). Please feel free to break isValidAssumeForContext into two parts, and reuse here the first part.

330

Odd indentation.

[arielb1]

address review comments

[hfinkel]

This looks good, but, have you checked for compile-time regressions? I'm concerned here because:

We've now made addAssumptionsFromMetadata linear in the number of instructions between the instruction and its replacement. That should be documented with the function declaration (at least). As the replacement always dominates the original instruction, when they're in the same BB, we'll always be doing that linear walk. As you're making the walk go through normal loads, I can imagine this becoming quadratic in some inputs (unless there's something about the way that SROA uses this that prevents that, and if so, we need to document that too).

If this can become quadratic, I think we'll want to maintain some kind of BB-region analysis, there we partition each BB into regions based on guaranteed execution, and then use that instead of walking.

include/llvm/Analysis/ValueTracking.h

375

reached and executed -> later executed

lib/Transforms/Utils/PromoteMemoryToRegister.cpp

314

Brace on previous line.

316

Do you need the llvm:: here? If not, please remove it.

[arielb1]

Don't use ValueTracking's isGuaranteedToBeExecuted to avoid potential O(n^2). This is much uglier but should be O(n log n) in all cases.

[arielb1]

style

[hfinkel]

lib/Transforms/Utils/PromoteMemoryToRegister.cpp

166

... guaranteed to execute once the first one executes.

191

How is that renumbering handled correctly?

Also, there's some assumption here that we don't insert new instructions that would break apart an existing internal? (I'm guessing not, as that seems like it would be a semantics-changing transformation, and we don't do that here, but we should document the assumptions here).

214

Line too long (and you should just use auto here).

266

Odd indentation.

313

Odd indentation.

368–369

Odd indentation.

471

Odd indentation.

891

Odd indentation.

[arielb1]

address review comments

[hfinkel]

You can benchmarks on the ValueTracking change? How did those turn out?

lib/Transforms/Utils/PromoteMemoryToRegister.cpp

170

Variable names start with a capital letter.

245

Start comments with a capital letter.

251

Local variable names start with a capital letter.

261

If we that -> If we find that

[arielb1]

address review comments

[hfinkel]

In D37216#861566, @hfinkel wrote:

You can benchmarks on the ValueTracking change? How did those turn out?

Great. This LGTM.

[arielb1]

This *still* hasn't committed. What is this waiting for?

[arielb1]

Ok. I was just going over my todo list for in-progress items.

[arielb1]

Has this still not landed in this month? Did this become blocked on anything?

[lebedev.ri]

In D37216#910089, @arielb1 wrote:

Has this still not landed in this month? Did this become blocked on anything?

Once the differential is accepted, you are supposed to commit it. There is no auto-commit.
If you don't have commit rights yet, you should request them.
Or you can ask others to commit it for you.

[nagisa]

Would be nice if somebody committed this. None of us have the commit bit.

[davide]

In D37216#935153, @nagisa wrote:

Would be nice if somebody committed this. None of us have the commit bit.

Please rebase the patch on ToT and I'll commit for you.

[arielb1]

Rebased and ready to land

[davide]

rL319096, cheers.

[davide]

Ariel, we had to revert this because it broke some bots. Feel free to fix the assertion and update the patch

[nox]

In D37216#937116, @davide wrote:

Ariel, we had to revert this because it broke some bots. Feel free to fix the assertion and update the patch

What was the failing assertion?

include/llvm/Analysis/ValueTracking.h

template <typename T> class ArrayRef;
   /// Return true if this pointer couldn't possibly be null. If the context
   /// instruction and dominator tree are specified, perform context-sensitive
   /// analysis and return true if the pointer couldn't possibly be null at the
   /// specified instruction.
   bool isKnownNonNullAt(const Value *V,
                         const Instruction *CtxI = nullptr,
                         const DominatorTree *DT = nullptr);
 
+  /// Return true if, when CxtI executes, it is guaranteed that either
+  /// I had executed already or that I is guaranteed to be reached and
+  /// be executed.
+  ///
+  /// The useful property this guarantees is that if I exhibits undefined
+  /// behavior under some circumstances, then the whole program will exhibit
+  /// undefined behavior at CxtI.
+  bool isGuaranteedToBeExecuted(const Instruction *I, const Instruction *CxtI,
+        const DominatorTree *DT = nullptr);
+
   /// Return true if it is valid to use the assumptions provided by an
   /// assume intrinsic, I, at the point in the control-flow identified by the
   /// context instruction, CxtI.
   bool isValidAssumeForContext(const Instruction *I, const Instruction *CxtI,
                                const DominatorTree *DT = nullptr);
 
   enum class OverflowResult { AlwaysOverflows, MayOverflow, NeverOverflows };
   OverflowResult computeOverflowForUnsignedMul(const Value *LHS,

lib/Analysis/ValueTracking.cpp

if (all_of(V->users(), [&](const User *U) { return EphValues.count(U); })) {
            WorkSet.push_back(*J);
       }
     }
   }
 
   return false;
 }
 
-bool llvm::isValidAssumeForContext(const Instruction *Inv,
-                                   const Instruction *CxtI,
-                                   const DominatorTree *DT) {
-
-  // There are two restrictions on the use of an assume:
-  //  1. The assume must dominate the context (or the control flow must
-  //     reach the assume whenever it reaches the context).
-  //  2. The context must not be in the assume's set of ephemeral values
-  //     (otherwise we will use the assume to prove that the condition
-  //     feeding the assume is trivially true, thus causing the removal of
-  //     the assume).
-
+bool llvm::isGuaranteedToBeExecuted(const Instruction *Inv,
+            const Instruction *CxtI,
+            const DominatorTree *DT) {
   if (DT) {
     if (DT->dominates(Inv, CxtI))
       return true;
   } else if (Inv->getParent() == CxtI->getParent()->getSinglePredecessor()) {
     // We don't have a DT, but this trivially dominates.
     return true;
   }
 
   // With or without a DT, the only remaining case we will check is if the
   // instructions are in the same BB.  Give up if that is not the case.
   if (Inv->getParent() != CxtI->getParent())
     return false;
 
-  // If we have a dom tree, then we now know that the assume doens't dominate
-  // the other instruction.  If we don't have a dom tree then we can check if
-  // the assume is first in the BB.
+  // If we have a dom tree, then we now know that Inv doens't dominate the
+  // other instruction.  If we don't have a dom tree then we can check if
+  // Inv is first in the BB.
   if (!DT) {
     // Search forward from the assume until we reach the context (or the end
     // of the block); the common case is that the assume will come first.
     for (auto I = std::next(BasicBlock::const_iterator(Inv)),
          IE = Inv->getParent()->end(); I != IE; ++I)
       if (&*I == CxtI)
         return true;
   }
 
-  // Don't let an assume affect itself - this would cause the problems
-  // `isEphemeralValueOf` is trying to prevent, and it would also make
-  // the loop below go out of bounds.
-  if (Inv == CxtI)
-    return false;
-
-  // The context comes first, but they're both in the same block. Make sure
+  // The context comes first, but they're both in the same block.  Make sure
   // there is nothing in between that might interrupt the control flow.
-  for (BasicBlock::const_iterator I =
-         std::next(BasicBlock::const_iterator(CxtI)), IE(Inv);
+  for (BasicBlock::const_iterator I = BasicBlock::const_iterator(CxtI), IE(Inv);
        I != IE; ++I)
     if (!isGuaranteedToTransferExecutionToSuccessor(&*I))
       return false;
 
-  return !isEphemeralValueOf(Inv, CxtI);
+  return true;
+}
+
+bool llvm::isValidAssumeForContext(const Instruction *I,
+           const Instruction *CxtI,
+           const DominatorTree *DT) {
+  // There are two restrictions on the use of an assume:
+  //  1. The assume must dominate the context (or the control flow must
+  //     reach the assume whenever it reaches the context).
+  //  2. The context must not be in the assume's set of ephemeral values
+  //     (otherwise we will use the assume to prove that the condition
+  //     feeding the assume is trivially true, thus causing the removal of
+  //     the assume).
+
+  return isGuaranteedToBeExecuted(I, CxtI, DT) &&
+    !isEphemeralValueOf(I, CxtI);
 }
 
 static void computeKnownBitsFromAssume(const Value *V, KnownBits &Known,
                                        unsigned Depth, const Query &Q) {
   // Use of assumptions is context-sensitive. If we don't have a context, we
   // cannot use them!
   if (!Q.AC || !Q.CxtI)
     return;

lib/Transforms/Scalar/SROA.cpp

if (VecTy) {
       if (LI.isVolatile())
         NewLI->setAtomic(LI.getOrdering(), LI.getSyncScopeID());
 
       // Any !nonnull metadata or !range metadata on the old load is also valid
       // on the new load. This is even true in some cases even when the loads
       // are different types, for example by mapping !nonnull metadata to
       // !range metadata by modeling the null pointer constant converted to the
       // integer type.
-      // FIXME: Add support for range metadata here. Currently the utilities
-      // for this don't propagate range metadata in trivial cases from one
-      // integer load to another, don't handle non-addrspace-0 null pointers
-      // correctly, and don't have any support for mapping ranges as the
-      // integer type becomes winder or narrower.
       if (MDNode *N = LI.getMetadata(LLVMContext::MD_nonnull))
         copyNonnullMetadata(LI, N, *NewLI);
-
-      // Try to preserve nonnull metadata
+      if (MDNode *N = LI.getMetadata(LLVMContext::MD_range))
+        copyRangeMetadata(DL, LI, N, *NewLI);
       V = NewLI;
 
       // If this is an integer load past the end of the slice (which means the
       // bytes outside the slice are undef or this load is dead) just forcibly
       // fix the integer size with correct handling of endianness.
       if (auto *AITy = dyn_cast<IntegerType>(NewAllocaTy))
         if (auto *TITy = dyn_cast<IntegerType>(TargetTy))
           if (AITy->getBitWidth() < TITy->getBitWidth()) {
for (;;) {
       auto AS = LI->getPointerAddressSpace();
       auto *PartPtrTy = PartTy->getPointerTo(AS);
       LoadInst *PLoad = IRB.CreateAlignedLoad(
           getAdjustedPtr(IRB, DL, BasePtr,
                          APInt(DL.getPointerSizeInBits(AS), PartOffset),
                          PartPtrTy, BasePtr->getName() + "."),
           getAdjustedAlignment(LI, PartOffset, DL), /*IsVolatile*/ false,
           LI->getName());
-      PLoad->copyMetadata(*LI, LLVMContext::MD_mem_parallel_loop_access); 
+      PLoad->copyMetadata(*LI, LLVMContext::MD_mem_parallel_loop_access);
 
       // Append this load onto the list of split loads so we can find it later
       // to rewrite the stores.
       SplitLoads.push_back(PLoad);
 
       // Now build a new slice for the alloca.
       NewSlices.push_back(
           Slice(BaseOffset + PartOffset, BaseOffset + PartOffset + PartSize,

lib/Transforms/Utils/Local.cpp

void llvm::copyNonnullMetadata(const LoadInst &OldLI, MDNode *N,
   auto *NonNullInt = ConstantExpr::getAdd(NullInt, ConstantInt::get(ITy, 1));
   NewLI.setMetadata(LLVMContext::MD_range,
                     MDB.createRange(NonNullInt, NullInt));
 }
 
 void llvm::copyRangeMetadata(const DataLayout &DL, const LoadInst &OldLI,
                              MDNode *N, LoadInst &NewLI) {
   auto *NewTy = NewLI.getType();
+  auto *OldTy = OldLI.getType();
 
-  // Give up unless it is converted to a pointer where there is a single very
-  // valuable mapping we can do reliably.
-  // FIXME: It would be nice to propagate this in more ways, but the type
-  // conversions make it hard.
-  if (!NewTy->isPointerTy())
+  if (DL.getTypeStoreSizeInBits(NewTy) == DL.getTypeSizeInBits(OldTy) &&
+      NewTy->isIntegerTy()) {
+    // An integer with the same number of bits - give it the range
+    // metadata!.
+    NewLI.setMetadata(LLVMContext::MD_range, N);
     return;
+  }
 
+  if (NewTy->isPointerTy()) {
+    // Try to convert the !range metadata to !nonnull metadata on the
+    // new pointer.
     unsigned BitWidth = DL.getTypeSizeInBits(NewTy);
     if (!getConstantRangeFromMetadata(*N).contains(APInt(BitWidth, 0))) {
       MDNode *NN = MDNode::get(OldLI.getContext(), None);
       NewLI.setMetadata(LLVMContext::MD_nonnull, NN);
     }
   }
+}
 
 namespace {
 /// A potential constituent of a bitreverse or bswap expression. See
 /// collectBitParts for a fuller explanation.
 struct BitPart {
   BitPart(Value *P, unsigned BW) : Provider(P) {
     Provenance.resize(BW);
   }

lib/Transforms/Utils/PromoteMemoryToRegister.cpp

public:
 
   RenamePassData(BasicBlock *B, BasicBlock *P, ValVector V)
       : BB(B), Pred(P), Values(std::move(V)) {}
   BasicBlock *BB;
   BasicBlock *Pred;
   ValVector Values;
 };
 
 /// \brief This assigns and keeps a per-bb relative ordering of load/store
 /// instructions in the block that directly load or store an alloca.
 ///
 /// This functionality is important because it avoids scanning large basic
 /// blocks multiple times when promoting many allocas in the same block.
 class LargeBlockInfo {
   /// \brief For each instruction that we track, keep the index of the
   /// instruction.
   ///
   /// The index starts out as the number of the instruction from the start of
   /// the block.
   DenseMap<const Instruction *, unsigned> InstNumbers;
 
 public:
 
   /// This code only looks at accesses to allocas.
   static bool isInterestingInstruction(const Instruction *I) {
     return (isa<LoadInst>(I) && isa<AllocaInst>(I->getOperand(0))) ||
            (isa<StoreInst>(I) && isa<AllocaInst>(I->getOperand(1)));
   }
 
   /// Get or calculate the index of the specified instruction.
   unsigned getInstructionIndex(const Instruction *I) {
     assert(isInterestingInstruction(I) &&
            "Not a load/store to/from an alloca?");
 
     // If we already have this instruction number, return it.
     DenseMap<const Instruction *, unsigned>::iterator It = InstNumbers.find(I);
     if (It != InstNumbers.end())
       return It->second;
 
     // Scan the whole block to get the instruction.  This accumulates
     // information for every interesting instruction in the block, in order to
     // avoid gratuitus rescans.
     const BasicBlock *BB = I->getParent();
     unsigned InstNo = 0;
     for (const Instruction &BBI : *BB)
       if (isInterestingInstruction(&BBI))
         InstNumbers[&BBI] = InstNo++;
     It = InstNumbers.find(I);
 
     assert(It != InstNumbers.end() && "Didn't insert instruction?");
     return It->second;
   }
 
   void deleteValue(const Instruction *I) { InstNumbers.erase(I); }
 
   void clear() { InstNumbers.clear(); }
 };
 
 struct PromoteMem2Reg {
   /// The alloca instructions being promoted.
   std::vector<AllocaInst *> Allocas;
   DominatorTree &DT;
+  const DataLayout &DL;
   DIBuilder DIB;
   /// A cache of @llvm.assume intrinsics used by SimplifyInstruction.
   AssumptionCache *AC;
 
   const SimplifyQuery SQ;
   /// Reverse mapping of Allocas.
   DenseMap<AllocaInst *, unsigned> AllocaLookup;
 
   /// \brief The PhiNodes we're adding.
   ///
   /// That map is used to simplify some Phi nodes as we iterate over it, so
   /// it should have deterministic iterators.  We could use a MapVector, but
   /// since we already maintain a map from BasicBlock* to a stable numbering
   /// (BBNumbers), the DenseMap is more efficient (also supports removal).
   DenseMap<std::pair<unsigned, unsigned>, PHINode *> NewPhiNodes;
 
   /// For each PHI node, keep track of which entry in Allocas it corresponds
   /// to.
   DenseMap<PHINode *, unsigned> PhiToAllocaMap;
 
   /// If we are updating an AliasSetTracker, then for each alloca that is of
   /// pointer type, we keep track of what to copyValue to the inserted PHI
   /// nodes here.
   std::vector<Value *> PointerAllocaValues;
 
   /// For each alloca, we keep track of the dbg.declare intrinsic that
   /// describes it, if any, so that we can convert it to a dbg.value
   /// intrinsic if the alloca gets promoted.
   SmallVector<DbgDeclareInst *, 8> AllocaDbgDeclares;
 
   /// The set of basic blocks the renamer has already visited.
   ///
   SmallPtrSet<BasicBlock *, 16> Visited;
 
   /// Contains a stable numbering of basic blocks to avoid non-determinstic
   /// behavior.
   DenseMap<BasicBlock *, unsigned> BBNumbers;
 
   /// Lazily compute the number of predecessors a block has.
   DenseMap<const BasicBlock *, unsigned> BBNumPreds;
 
 public:
   PromoteMem2Reg(ArrayRef<AllocaInst *> Allocas, DominatorTree &DT,
                  AssumptionCache *AC)
       : Allocas(Allocas.begin(), Allocas.end()), DT(DT),
+  DL(DT.getRoot()->getParent()->getParent()->getDataLayout()),
         DIB(*DT.getRoot()->getParent()->getParent(), /*AllowUnresolved*/ false),
-        AC(AC), SQ(DT.getRoot()->getParent()->getParent()->getDataLayout(),
-                   nullptr, &DT, AC) {}
+        AC(AC), SQ(DL, nullptr, &DT, AC) {}
 
   void run();
 
 private:
   void RemoveFromAllocasList(unsigned &AllocaIdx) {
     Allocas[AllocaIdx] = Allocas.back();
     Allocas.pop_back();
     --AllocaIdx;
static void addAssumeNonNull(AssumptionCache *AC, LoadInst *LI) {
   ICmpInst *LoadNotNull = new ICmpInst(ICmpInst::ICMP_NE, LI,
                                        Constant::getNullValue(LI->getType()));
   LoadNotNull->insertAfter(LI);
   CallInst *CI = CallInst::Create(AssumeIntrinsic, {LoadNotNull});
   CI->insertAfter(LoadNotNull);
   AC->registerAssumption(CI);
 }
 
+static void addAssumptionsFromMetadata(LoadInst *LI,
+               Value *ReplVal,
+               DominatorTree &DT,
+               const DataLayout &DL,
+               AssumptionCache *AC)
+{
+  if (LI->getMetadata(LLVMContext::MD_nonnull) &&
+      !llvm::isKnownNonNullAt(ReplVal, LI, &DT)) {
+    addAssumeNonNull(AC, LI);
+  }
+
+  if (auto *N = LI->getMetadata(LLVMContext::MD_range)) {
+    // Range metadata is harder to use as an assumption,
+    // so don't try to add one, but *do* try to copy
+    // the metadata to a load in the same BB.
+    if (LoadInst *NewLI = dyn_cast<LoadInst>(ReplVal)) {
+      DEBUG(dbgs() << "trying to move !range metadata from" <<
+        *LI << " to" << *NewLI << "\n");
+      if (isGuaranteedToBeExecuted(LI, NewLI, &DT)) {
+        copyRangeMetadata(DL, *LI, N, *NewLI);
+      }
+    }
+  }
+}
+
 static void removeLifetimeIntrinsicUsers(AllocaInst *AI) {
   // Knowing that this alloca is promotable, we know that it's safe to kill all
   // instructions except for load and store.
 
   for (auto UI = AI->user_begin(), UE = AI->user_end(); UI != UE;) {
     Instruction *I = cast<Instruction>(*UI);
     ++UI;
     if (isa<LoadInst>(I) || isa<StoreInst>(I))

 /// When there is only a single store, we can use the domtree to trivially
 /// replace all of the dominated loads with the stored value. Do so, and return
 /// true if this has successfully promoted the alloca entirely. If this returns
 /// false there were some loads which were not dominated by the single store
 /// and thus must be phi-ed with undef. We fall back to the standard alloca
 /// promotion algorithm in that case.
 static bool rewriteSingleStoreAlloca(AllocaInst *AI, AllocaInfo &Info,
                                      LargeBlockInfo &LBI, DominatorTree &DT,
+             const DataLayout &DL,
                                      AssumptionCache *AC) {
   StoreInst *OnlyStore = Info.OnlyStore;
   bool StoringGlobalVal = !isa<Instruction>(OnlyStore->getOperand(0));
   BasicBlock *StoreBB = OnlyStore->getParent();
   int StoreIndex = -1;
 
   // Clear out UsingBlocks.  We will reconstruct it here if needed.
   Info.UsingBlocks.clear();
 
for (auto UI = AI->user_begin(), E = AI->user_end(); UI != E;) {
     // If the replacement value is the load, this must occur in unreachable
     // code.
     if (ReplVal == LI)
       ReplVal = UndefValue::get(LI->getType());
 
     // If the load was marked as nonnull we don't want to lose
     // that information when we erase this Load. So we preserve
     // it with an assume.
-    if (AC && LI->getMetadata(LLVMContext::MD_nonnull) &&
-        !llvm::isKnownNonNullAt(ReplVal, LI, &DT))
-      addAssumeNonNull(AC, LI);
+    addAssumptionsFromMetadata(LI, ReplVal, DT, DL, AC);
 
     LI->replaceAllUsesWith(ReplVal);
     LI->eraseFromParent();
     LBI.deleteValue(LI);
   }
 
   // Finally, after the scan, check to see if the store is all that is left.
   if (!Info.UsingBlocks.empty())

 ///    int t = *A;
 ///    if (!first_iteration)
 ///      use(t);
 ///    *A = 42;
 ///  }
 static bool promoteSingleBlockAlloca(AllocaInst *AI, const AllocaInfo &Info,
                                      LargeBlockInfo &LBI,
                                      DominatorTree &DT,
+             const DataLayout &DL,
                                      AssumptionCache *AC) {
   // The trickiest case to handle is when we have large blocks. Because of this,
   // this code is optimized assuming that large blocks happen.  This does not
   // significantly pessimize the small block case.  This uses LargeBlockInfo to
   // make it efficient to get the index of various operations in the block.
 
   // Walk the use-def list of the alloca, getting the locations of all stores.
   typedef SmallVector<std::pair<unsigned, StoreInst *>, 64> StoresByIndexTy;
if (I == StoresByIndex.begin()) {
         // There is no store before this load, bail out (load may be affected
         // by the following stores - see main comment).
         return false;
     } else {
       // Otherwise, there was a store before this load, the load takes its value.
       // Note, if the load was marked as nonnull we don't want to lose that
       // information when we erase it. So we preserve it with an assume.
       Value *ReplVal = std::prev(I)->second->getOperand(0);
-      if (AC && LI->getMetadata(LLVMContext::MD_nonnull) &&
-          !llvm::isKnownNonNullAt(ReplVal, LI, &DT))
-        addAssumeNonNull(AC, LI);
+      addAssumptionsFromMetadata(LI, ReplVal, DT, DL, AC);
 
       LI->replaceAllUsesWith(ReplVal);
     }
 
     LI->eraseFromParent();
     LBI.deleteValue(LI);
   }
 
for (unsigned AllocaNum = 0; AllocaNum != Allocas.size(); ++AllocaNum) {
 
     // Calculate the set of read and write-locations for each alloca.  This is
     // analogous to finding the 'uses' and 'definitions' of each variable.
     Info.AnalyzeAlloca(AI);
 
     // If there is only a single store to this value, replace any loads of
     // it that are directly dominated by the definition with the value stored.
     if (Info.DefiningBlocks.size() == 1) {
-      if (rewriteSingleStoreAlloca(AI, Info, LBI, DT, AC)) {
+      if (rewriteSingleStoreAlloca(AI, Info, LBI, DT, DL, AC)) {
         // The alloca has been processed, move on.
         RemoveFromAllocasList(AllocaNum);
         ++NumSingleStore;
         continue;
       }
     }
 
     // If the alloca is only read and written in one basic block, just perform a
     // linear sweep over the block to eliminate it.
     if (Info.OnlyUsedInOneBlock &&
-        promoteSingleBlockAlloca(AI, Info, LBI, DT, AC)) {
+        promoteSingleBlockAlloca(AI, Info, LBI, DT, DL, AC)) {
       // The alloca has been processed, move on.
       RemoveFromAllocasList(AllocaNum);
       continue;
     }
 
     // If we haven't computed a numbering for the BB's in the function, do so
     // now.
     if (BBNumbers.empty()) {

 
 /// \brief Recursively traverse the CFG of the function, renaming loads and
 /// stores to the allocas which we are promoting.
 ///
 /// IncomingVals indicates what value each Alloca contains on exit from the
 /// predecessor block Pred.
 void PromoteMem2Reg::RenamePass(BasicBlock *BB, BasicBlock *Pred,
                                 RenamePassData::ValVector &IncomingVals,
                                 std::vector<RenamePassData> &Worklist) {
 NextIteration:
   // If we are inserting any phi nodes into this BB, they will already be in the
   // block.
   if (PHINode *APN = dyn_cast<PHINode>(BB->begin())) {
     // If we have PHI nodes to update, compute the number of edges from Pred to
     // BB.
     if (PhiToAllocaMap.count(APN)) {
       // We want to be able to distinguish between PHI nodes being inserted by
if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
       if (AI == AllocaLookup.end())
         continue;
 
       Value *V = IncomingVals[AI->second];
 
       // If the load was marked as nonnull we don't want to lose
       // that information when we erase this Load. So we preserve
       // it with an assume.
-      if (AC && LI->getMetadata(LLVMContext::MD_nonnull) &&
-          !llvm::isKnownNonNullAt(V, LI, &DT))
-        addAssumeNonNull(AC, LI);
+      addAssumptionsFromMetadata(LI, V, DT, DL, AC);
 
       // Anything using the load now uses the current value.
       LI->replaceAllUsesWith(V);
       BB->getInstList().erase(LI);
     } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
       // Delete this instruction and mark the name as the current holder of the
       // value
       AllocaInst *Dest = dyn_cast<AllocaInst>(SI->getPointerOperand());

test/Transforms/SROA/preserve-nonnull.ll

 ; RUN: opt < %s -sroa -S | FileCheck %s
 ;
 ; Make sure that SROA doesn't lose nonnull metadata
 ; on loads from allocas that get optimized out.
 
+%pair = type { i64, [0 x i64], [1 x i64] }
+
 declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture writeonly, i8* nocapture readonly, i64, i32, i1)
 
 ; Check that we do basic propagation of nonnull when rewriting.
 define i8* @propagate_nonnull(i32* %v) {
 ; CHECK-LABEL: define i8* @propagate_nonnull(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    %[[A:.*]] = alloca i8*
 ; CHECK-NEXT:    %[[V_CAST:.*]] = bitcast i32* %v to i8*
entry:
   %buf = alloca float*
   %_arg_i8 = bitcast float** %arg to i8*
   %_buf_i8 = bitcast float** %buf to i8*
   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %_buf_i8, i8* %_arg_i8, i64 8, i32 8, i1 false)
   %ret = load float*, float** %buf, align 8, !nonnull !0
   ret float* %ret
 }
 
+; Make sure we propagate the !range attribute when we expand loads.
+define i64 @propagate_range(%pair* dereferenceable(16)) {
+; CHECK-LABEL: define i64 @propagate_range(
+; CHECK-NEXT:  start:
+; CHECK-NEXT:      %[[SROA_IDX:.*]] = getelementptr inbounds %pair
+; CHECK-NEXT:      %[[RESULT:.*]] = load i64, i64* %[[SROA_IDX]], align 8, !range !1
+; CHECK:           ret i64 %[[RESULT]]
+start:
+  %a = alloca %pair
+  %1 = bitcast %pair* %0 to i8*
+  %2 = bitcast %pair* %a to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %2, i8* %1, i64 16, i32 8, i1 false)
+  %3 = getelementptr inbounds %pair, %pair* %a, i32 0, i32 0
+  %4 = load i64, i64* %3, !range !1
+  ret i64 %4
+}
+
 ; Make sure we properly handle the !nonnull attribute when we convert
 ; a pointer load to an integer load.
 ; FIXME: While this doesn't do anythnig actively harmful today, it really
 ; should propagate the !nonnull metadata to range metadata. The irony is, it
 ; *does* initially, but then we lose that !range metadata before we finish
 ; SROA.
 define i8* @propagate_nonnull_to_int() {
 ; CHECK-LABEL: define i8* @propagate_nonnull_to_int(
entry:
   %a.gep1.cast = bitcast i8** %a.gep1 to i64*
   store i64 42, i64* %a.gep1.cast
   store i64 0, i64* %a.gep0.cast
   %load = load i8*, i8** %a.gep1, align 8, !nonnull !0
   ret i8* %load
 }
 
 !0 = !{}
+!1 = !{i64 0, i64 2}