This reverts commit r319096 and r319097.

Revert "[SROA] Propagate !range metadata when moving loads."
Revert "[Mem2Reg] Clang-format unformatted parts of this file. NFCI."

Davide says they broke a bot.

llvm-svn: 319131

1 files changed, 17 insertions, 147 deletions

diff --git a/llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp b/llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp
index c14b4bd5f17..fcd3bd08482 100644
--- a/llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp
+++ b/llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp
@@ -17,7 +17,6 @@
 
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
-#include "llvm/ADT/Optional.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
@@ -49,7 +48,7 @@
 #include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Transforms/Utils/PromoteMemToReg.h"
 #include <algorithm>
-
+#include <cassert>
 #include <iterator>
 #include <utility>
 #include <vector>
@@ -178,16 +177,6 @@ public:
   ValVector Values;
 };
 
-/// \brief Semi-open interval of instructions that are guaranteed to
-/// all execute if the first one does.
-class GuaranteedExecutionRange {
-public:
-  unsigned Start;
-  unsigned End;
-
-  GuaranteedExecutionRange(unsigned S, unsigned E) : Start(S), End(E) {}
-};
-
 /// \brief This assigns and keeps a per-bb relative ordering of load/store
 /// instructions in the block that directly load or store an alloca.
 ///
@@ -201,108 +190,14 @@ class LargeBlockInfo {
   /// the block.
   DenseMap<const Instruction *, unsigned> InstNumbers;
 
-  /// \brief For each basic block we track, keep track of the intervals
-  /// of instruction numbers of instructions that transfer control
-  /// to their successors, for propagating metadata.
-  DenseMap<const BasicBlock *,
-           Optional<SmallVector<GuaranteedExecutionRange, 4>>>
-      GuaranteedExecutionIntervals;
-
 public:
-  /// This code looks for stores to allocas, and for loads both for
-  /// allocas and for transferring metadata.
+
+  /// This code only looks at accesses to allocas.
   static bool isInterestingInstruction(const Instruction *I) {
-    return isa<LoadInst>(I) ||
+    return (isa<LoadInst>(I) && isa<AllocaInst>(I->getOperand(0))) ||
            (isa<StoreInst>(I) && isa<AllocaInst>(I->getOperand(1)));
   }
 
-  /// Compute the GuaranteedExecutionIntervals for a given BB.
-  ///
-  /// This is valid and remains valid as long as each interesting
-  /// instruction (see isInterestingInstruction) that
-  ///   A) existed when this LBI was cleared
-  ///   B) has not been deleted (deleting interesting instructions is fine)
-  /// are run in the same program executions and in the same order
-  /// as when this LBI was cleared.
-  ///
-  /// Because `PromoteMemoryToRegister` does not move memory loads at
-  /// all, this assumption is satisfied in this pass.
-  SmallVector<GuaranteedExecutionRange, 4> computeGEI(const BasicBlock *BB) {
-    SmallVector<GuaranteedExecutionRange, 4> GuaranteedExecutionIntervals;
-
-    unsigned InstNo = 0;
-    bool InRange = false;
-    unsigned FirstInstInRange = 0;
-    for (const Instruction &BBI : *BB) {
-      if (isGuaranteedToTransferExecutionToSuccessor(&BBI)) {
-        if (!InRange && isInterestingInstruction(&BBI)) {
-          InRange = true;
-          FirstInstInRange = InstNo;
-        }
-      } else {
-        if (InRange) {
-          assert(FirstInstInRange < InstNo &&
-                 "Can't push an empty range here.");
-          GuaranteedExecutionIntervals.emplace_back(FirstInstInRange, InstNo);
-        }
-        InRange = false;
-      }
-
-      if (isInterestingInstruction(&BBI)) {
-        auto It = InstNumbers.find(&BBI);
-        assert(It != InstNumbers.end() && InstNo <= It->second &&
-               "missing number for interesting instruction");
-        InstNo = It->second + 1;
-      }
-    }
-
-    if (InRange) {
-      assert(FirstInstInRange < InstNo && "Can't push an empty range here.");
-      GuaranteedExecutionIntervals.emplace_back(FirstInstInRange, InstNo);
-    }
-
-    return GuaranteedExecutionIntervals;
-  }
-
-  /// Return true if, when CxtI executes, it is guaranteed that either
-  /// I had executed already or that I is guaranteed to be later 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 *CxtI, const Instruction *I) {
-    const BasicBlock *BB = CxtI->getParent();
-
-    if (BB != I->getParent()) {
-      // Instructions in different basic blocks, so control flow
-      // can diverge between them (we could track this with
-      // postdoms, but we don't bother).
-      return false;
-    }
-
-    unsigned Index1 = getInstructionIndex(CxtI);
-    unsigned Index2 = getInstructionIndex(I);
-
-    auto &BBGEI = GuaranteedExecutionIntervals[BB];
-    if (!BBGEI.hasValue()) {
-      BBGEI.emplace(computeGEI(BB));
-    }
-
-    // We want to check whether I and CxtI are in the same range. To do that,
-    // we notice that CxtI can only be in the first range R where
-    // CxtI.end < R.end. If we find that range using binary search,
-    // we can check whether I and CxtI are both in it.
-    GuaranteedExecutionRange Bound(Index1, Index1);
-    auto R = std::upper_bound(
-        BBGEI->begin(), BBGEI->end(), Bound,
-        [](GuaranteedExecutionRange I_, GuaranteedExecutionRange R) {
-          return I_.End < R.End;
-        });
-
-    return R != BBGEI->end() && R->Start <= Index1 && Index1 < R->End &&
-           R->Start <= Index2 && Index2 < R->End;
-  }
-
   /// Get or calculate the index of the specified instruction.
   unsigned getInstructionIndex(const Instruction *I) {
     assert(isInterestingInstruction(I) &&
@@ -318,11 +213,9 @@ public:
     // avoid gratuitus rescans.
     const BasicBlock *BB = I->getParent();
     unsigned InstNo = 0;
-    GuaranteedExecutionIntervals.erase(BB);
     for (const Instruction &BBI : *BB)
       if (isInterestingInstruction(&BBI))
         InstNumbers[&BBI] = InstNo++;
-
     It = InstNumbers.find(I);
 
     assert(It != InstNumbers.end() && "Didn't insert instruction?");
@@ -331,10 +224,7 @@ public:
 
   void deleteValue(const Instruction *I) { InstNumbers.erase(I); }
 
-  void clear() {
-    InstNumbers.clear();
-    GuaranteedExecutionIntervals.clear();
-  }
+  void clear() { InstNumbers.clear(); }
 };
 
 struct PromoteMem2Reg {
@@ -412,7 +302,7 @@ private:
                            const SmallPtrSetImpl<BasicBlock *> &DefBlocks,
                            SmallPtrSetImpl<BasicBlock *> &LiveInBlocks);
   void RenamePass(BasicBlock *BB, BasicBlock *Pred,
-                  RenamePassData::ValVector &IncVals, LargeBlockInfo &LBI,
+                  RenamePassData::ValVector &IncVals,
                   std::vector<RenamePassData> &Worklist);
   bool QueuePhiNode(BasicBlock *BB, unsigned AllocaIdx, unsigned &Version);
 };
@@ -431,29 +321,6 @@ static void addAssumeNonNull(AssumptionCache *AC, LoadInst *LI) {
   AC->registerAssumption(CI);
 }
 
-static void addAssumptionsFromMetadata(LoadInst *LI, Value *ReplVal,
-                                       DominatorTree &DT, const DataLayout &DL,
-                                       LargeBlockInfo &LBI,
-                                       AssumptionCache *AC) {
-  if (LI->getMetadata(LLVMContext::MD_nonnull) &&
-      !isKnownNonZero(ReplVal, DL, 0, AC, 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 (LBI.isGuaranteedToBeExecuted(LI, NewLI)) {
-        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.
@@ -542,7 +409,9 @@ static bool rewriteSingleStoreAlloca(AllocaInst *AI, AllocaInfo &Info,
     // 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.
-    addAssumptionsFromMetadata(LI, ReplVal, DT, DL, LBI, AC);
+    if (AC && LI->getMetadata(LLVMContext::MD_nonnull) &&
+        !isKnownNonZero(ReplVal, DL, 0, AC, LI, &DT))
+      addAssumeNonNull(AC, LI);
 
     LI->replaceAllUsesWith(ReplVal);
     LI->eraseFromParent();
@@ -636,7 +505,9 @@ static bool promoteSingleBlockAlloca(AllocaInst *AI, const AllocaInfo &Info,
       // 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);
-      addAssumptionsFromMetadata(LI, ReplVal, DT, DL, LBI, AC);
+      if (AC && LI->getMetadata(LLVMContext::MD_nonnull) &&
+          !isKnownNonZero(ReplVal, DL, 0, AC, LI, &DT))
+        addAssumeNonNull(AC, LI);
 
       LI->replaceAllUsesWith(ReplVal);
     }
@@ -772,6 +643,7 @@ void PromoteMem2Reg::run() {
 
   if (Allocas.empty())
     return; // All of the allocas must have been trivial!
+
   LBI.clear();
 
   // Set the incoming values for the basic block to be null values for all of
@@ -789,10 +661,9 @@ void PromoteMem2Reg::run() {
     RenamePassData RPD = std::move(RenamePassWorkList.back());
     RenamePassWorkList.pop_back();
     // RenamePass may add new worklist entries.
-    RenamePass(RPD.BB, RPD.Pred, RPD.Values, LBI, RenamePassWorkList);
+    RenamePass(RPD.BB, RPD.Pred, RPD.Values, RenamePassWorkList);
   } while (!RenamePassWorkList.empty());
 
-  LBI.clear();
   // The renamer uses the Visited set to avoid infinite loops.  Clear it now.
   Visited.clear();
 
@@ -1004,7 +875,6 @@ bool PromoteMem2Reg::QueuePhiNode(BasicBlock *BB, unsigned AllocaNo,
 /// predecessor block Pred.
 void PromoteMem2Reg::RenamePass(BasicBlock *BB, BasicBlock *Pred,
                                 RenamePassData::ValVector &IncomingVals,
-                                LargeBlockInfo &LBI,
                                 std::vector<RenamePassData> &Worklist) {
 NextIteration:
   // If we are inserting any phi nodes into this BB, they will already be in the
@@ -1071,12 +941,13 @@ NextIteration:
       // 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.
-      addAssumptionsFromMetadata(LI, V, DT, SQ.DL, LBI, AC);
+      if (AC && LI->getMetadata(LLVMContext::MD_nonnull) &&
+          !isKnownNonZero(V, SQ.DL, 0, AC, LI, &DT))
+        addAssumeNonNull(AC, LI);
 
       // Anything using the load now uses the current value.
       LI->replaceAllUsesWith(V);
       BB->getInstList().erase(LI);
-      LBI.deleteValue(LI);
     } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
       // Delete this instruction and mark the name as the current holder of the
       // value
@@ -1094,7 +965,6 @@ NextIteration:
       for (DbgInfoIntrinsic *DII : AllocaDbgDeclares[ai->second])
         ConvertDebugDeclareToDebugValue(DII, SI, DIB);
       BB->getInstList().erase(SI);
-      LBI.deleteValue(SI);
     }
   }