[NFC][DwarfDebug] Add test for variables with a single location which

don't span their entire scope.

The previous commit (6d1c40c171e) is an older version of the test.

Reviewed By: aprantl, vsk

Differential Revision: https://reviews.llvm.org/D79573

1 files changed, 273 insertions, 1 deletions

diff --git a/llvm/lib/Transforms/Utils/AssumeBundleBuilder.cpp b/llvm/lib/Transforms/Utils/AssumeBundleBuilder.cpp
index 6844fa0..4e47dd8 100644
--- a/llvm/lib/Transforms/Utils/AssumeBundleBuilder.cpp
+++ b/llvm/lib/Transforms/Utils/AssumeBundleBuilder.cpp
@@ -7,6 +7,7 @@
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Utils/AssumeBundleBuilder.h"
+#include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/MapVector.h"
 #include "llvm/Analysis/AssumeBundleQueries.h"
 #include "llvm/Analysis/AssumptionCache.h"
@@ -16,7 +17,9 @@
 #include "llvm/IR/InstIterator.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Module.h"
+#include "llvm/InitializePasses.h"
 #include "llvm/Support/CommandLine.h"
+#include "llvm/Transforms/Utils/Local.h"
 
 using namespace llvm;
 
@@ -90,7 +93,7 @@ struct AssumeBuilderState {
   }
 
   void addKnowledge(RetainedKnowledge RK) {
-    if (tryToPreserveWithoutAddingAssume(RK))
+    if (RK.AttrKind == Attribute::None || tryToPreserveWithoutAddingAssume(RK))
       return;
     MapKey Key{RK.WasOn, RK.AttrKind};
     auto Lookup = AssumedKnowledgeMap.find(Key);
@@ -210,6 +213,275 @@ void llvm::salvageKnowledge(Instruction *I, AssumptionCache *AC, DominatorTree*
   }
 }
 
+namespace {
+
+struct AssumeSimplify {
+  Function &F;
+  AssumptionCache ∾
+  DominatorTree *DT;
+  LLVMContext &C;
+  SmallDenseSet<IntrinsicInst *> CleanupToDo;
+  StringMapEntry<uint32_t> *IgnoreTag;
+  SmallDenseMap<BasicBlock *, SmallVector<IntrinsicInst *, 4>, 8> BBToAssume;
+  bool MadeChange = false;
+
+  AssumeSimplify(Function &F, AssumptionCache &AC, DominatorTree *DT,
+                 LLVMContext &C)
+      : F(F), AC(AC), DT(DT), C(C),
+        IgnoreTag(C.getOrInsertBundleTag(IgnoreBundleTag)) {}
+
+  void buildMapping(bool FilterBooleanArgument) {
+    BBToAssume.clear();
+    for (Value *V : AC.assumptions()) {
+      if (!V)
+        continue;
+      IntrinsicInst *Assume = cast<IntrinsicInst>(V);
+      if (FilterBooleanArgument) {
+        auto *Arg = dyn_cast<ConstantInt>(Assume->getOperand(0));
+        if (!Arg || Arg->isZero())
+          continue;
+      }
+      BBToAssume[Assume->getParent()].push_back(Assume);
+    }
+
+    for (auto &Elem : BBToAssume) {
+      llvm::sort(Elem.second,
+                 [](const IntrinsicInst *LHS, const IntrinsicInst *RHS) {
+                   return LHS->comesBefore(RHS);
+                 });
+    }
+  }
+
+  /// Remove all asumes in CleanupToDo if there boolean argument is true and
+  /// ForceCleanup is set or the assume doesn't hold valuable knowledge.
+  void RunCleanup(bool ForceCleanup) {
+    for (IntrinsicInst *Assume : CleanupToDo) {
+      auto *Arg = dyn_cast<ConstantInt>(Assume->getOperand(0));
+      if (!Arg || Arg->isZero() ||
+          (!ForceCleanup && !isAssumeWithEmptyBundle(*Assume)))
+        continue;
+      MadeChange = true;
+      Assume->eraseFromParent();
+    }
+    CleanupToDo.clear();
+  }
+
+  /// Remove knowledge stored in assume when it is already know by an attribute
+  /// or an other assume. This can when valid update an existing knowledge in an
+  /// attribute or an other assume.
+  void dropRedundantKnowledge() {
+    struct MapValue {
+      IntrinsicInst *Assume;
+      unsigned ArgValue;
+      CallInst::BundleOpInfo *BOI;
+    };
+    buildMapping(false);
+    SmallDenseMap<std::pair<Value *, Attribute::AttrKind>,
+                  SmallVector<MapValue, 2>, 16>
+        Knowledge;
+    for (BasicBlock *BB : depth_first(&F))
+      for (Value *V : BBToAssume[BB]) {
+        if (!V)
+          continue;
+        IntrinsicInst *Assume = cast<IntrinsicInst>(V);
+        for (CallInst::BundleOpInfo &BOI : Assume->bundle_op_infos()) {
+          auto RemoveFromAssume = [&]() {
+            CleanupToDo.insert(Assume);
+            if (BOI.Begin != BOI.End) {
+              Use *U = &Assume->op_begin()[BOI.Begin + ABA_WasOn];
+              U->set(UndefValue::get(U->get()->getType()));
+            }
+            BOI.Tag = IgnoreTag;
+          };
+          if (BOI.Tag == IgnoreTag) {
+            CleanupToDo.insert(Assume);
+            continue;
+          }
+          RetainedKnowledge RK = getKnowledgeFromBundle(*Assume, BOI);
+          if (auto *Arg = dyn_cast_or_null<Argument>(RK.WasOn)) {
+            bool HasSameKindAttr = Arg->hasAttribute(RK.AttrKind);
+            if (HasSameKindAttr)
+              if (!Attribute::doesAttrKindHaveArgument(RK.AttrKind) ||
+                  Arg->getAttribute(RK.AttrKind).getValueAsInt() >=
+                      RK.ArgValue) {
+                RemoveFromAssume();
+                continue;
+              }
+            if (isValidAssumeForContext(
+                    Assume, &*F.getEntryBlock().getFirstInsertionPt()) ||
+                Assume == &*F.getEntryBlock().getFirstInsertionPt()) {
+              if (HasSameKindAttr)
+                Arg->removeAttr(RK.AttrKind);
+              Arg->addAttr(Attribute::get(C, RK.AttrKind, RK.ArgValue));
+              MadeChange = true;
+              RemoveFromAssume();
+              continue;
+            }
+          }
+          auto &Lookup = Knowledge[{RK.WasOn, RK.AttrKind}];
+          for (MapValue &Elem : Lookup) {
+            if (!isValidAssumeForContext(Elem.Assume, Assume, DT))
+              continue;
+            if (Elem.ArgValue >= RK.ArgValue) {
+              RemoveFromAssume();
+              continue;
+            } else if (isValidAssumeForContext(Assume, Elem.Assume, DT)) {
+              Elem.Assume->op_begin()[Elem.BOI->Begin + ABA_Argument].set(
+                  ConstantInt::get(Type::getInt64Ty(C), RK.ArgValue));
+              MadeChange = true;
+              RemoveFromAssume();
+              continue;
+            }
+          }
+          Lookup.push_back({Assume, RK.ArgValue, &BOI});
+        }
+      }
+  }
+
+  using MergeIterator = SmallVectorImpl<IntrinsicInst *>::iterator;
+
+  /// Merge all Assumes from Begin to End in and insert the resulting assume as
+  /// high as possible in the basicblock.
+  void mergeRange(BasicBlock *BB, MergeIterator Begin, MergeIterator End) {
+    if (Begin == End || std::next(Begin) == End)
+      return;
+    /// Provide no additional information so that AssumeBuilderState doesn't
+    /// try to do any punning since it already has been done better.
+    AssumeBuilderState Builder(F.getParent());
+
+    /// For now it is initialized to the best value it could have
+    Instruction *InsertPt = BB->getFirstNonPHI();
+    if (isa<LandingPadInst>(InsertPt))
+      InsertPt = InsertPt->getNextNode();
+    for (IntrinsicInst *I : make_range(Begin, End)) {
+      CleanupToDo.insert(I);
+      for (CallInst::BundleOpInfo &BOI : I->bundle_op_infos()) {
+        RetainedKnowledge RK = getKnowledgeFromBundle(*I, BOI);
+        if (!RK)
+          continue;
+        Builder.addKnowledge(RK);
+        if (auto *I = dyn_cast_or_null<Instruction>(RK.WasOn))
+          if (I->getParent() == InsertPt->getParent() &&
+              (InsertPt->comesBefore(I) || InsertPt == I))
+            InsertPt = I->getNextNode();
+      }
+    }
+
+    /// Adjust InsertPt if it is before Begin, since mergeAssumes only
+    /// guarantees we can place the resulting assume between Begin and End.
+    if (InsertPt->comesBefore(*Begin))
+      for (auto It = (*Begin)->getIterator(), E = InsertPt->getIterator();
+           It != E; --It)
+        if (!isGuaranteedToTransferExecutionToSuccessor(&*It)) {
+          InsertPt = It->getNextNode();
+          break;
+        }
+    IntrinsicInst *MergedAssume = Builder.build();
+    if (!MergedAssume)
+      return;
+    MadeChange = true;
+    MergedAssume->insertBefore(InsertPt);
+    AC.registerAssumption(MergedAssume);
+  }
+
+  /// Merge assume when they are in the same BasicBlock and for all instruction
+  /// between them isGuaranteedToTransferExecutionToSuccessor returns true.
+  void mergeAssumes() {
+    buildMapping(true);
+
+    SmallVector<MergeIterator, 4> SplitPoints;
+    for (auto &Elem : BBToAssume) {
+      SmallVectorImpl<IntrinsicInst *> &AssumesInBB = Elem.second;
+      if (AssumesInBB.size() < 2)
+        continue;
+      /// AssumesInBB is already sorted by order in the block.
+
+      BasicBlock::iterator It = AssumesInBB.front()->getIterator();
+      BasicBlock::iterator E = AssumesInBB.back()->getIterator();
+      SplitPoints.push_back(AssumesInBB.begin());
+      MergeIterator LastSplit = AssumesInBB.begin();
+      for (; It != E; ++It)
+        if (!isGuaranteedToTransferExecutionToSuccessor(&*It)) {
+          for (; (*LastSplit)->comesBefore(&*It); ++LastSplit)
+            ;
+          if (SplitPoints.back() != LastSplit)
+            SplitPoints.push_back(LastSplit);
+        }
+      SplitPoints.push_back(AssumesInBB.end());
+      for (auto SplitIt = SplitPoints.begin();
+           SplitIt != std::prev(SplitPoints.end()); SplitIt++) {
+        mergeRange(Elem.first, *SplitIt, *(SplitIt + 1));
+      }
+      SplitPoints.clear();
+    }
+  }
+};
+
+bool simplifyAssumes(Function &F, AssumptionCache *AC, DominatorTree *DT) {
+  AssumeSimplify AS(F, *AC, DT, F.getContext());
+
+  /// Remove knowledge that is already known by a dominating other assume or an
+  /// attribute.
+  AS.dropRedundantKnowledge();
+
+  /// Remove assume that are empty.
+  AS.RunCleanup(false);
+
+  /// Merge assume in the same basicblock when possible.
+  AS.mergeAssumes();
+
+  /// Remove assume that were merged.
+  AS.RunCleanup(true);
+  return AS.MadeChange;
+}
+
+} // namespace
+
+PreservedAnalyses AssumeSimplifyPass::run(Function &F,
+                                          FunctionAnalysisManager &AM) {
+  if (!EnableKnowledgeRetention)
+    return PreservedAnalyses::all();
+  simplifyAssumes(F, &AM.getResult<AssumptionAnalysis>(F),
+                  AM.getCachedResult<DominatorTreeAnalysis>(F));
+  return PreservedAnalyses::all();
+}
+
+class AssumeSimplifyPassLegacyPass : public FunctionPass {
+public:
+  static char ID;
+
+  AssumeSimplifyPassLegacyPass() : FunctionPass(ID) {
+    initializeAssumeSimplifyPassLegacyPassPass(
+        *PassRegistry::getPassRegistry());
+  }
+  bool runOnFunction(Function &F) override {
+    if (skipFunction(F) || !EnableKnowledgeRetention)
+      return false;
+    DominatorTreeWrapperPass *DT =
+        getAnalysisIfAvailable<DominatorTreeWrapperPass>();
+    AssumptionCache &AC =
+        getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
+    return simplifyAssumes(F, &AC, DT ? &DT->getDomTree() : nullptr);
+  }
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.setPreservesAll();
+  }
+};
+
+char AssumeSimplifyPassLegacyPass::ID = 0;
+
+INITIALIZE_PASS_BEGIN(AssumeSimplifyPassLegacyPass, "assume-simplify",
+                      "Assume Simplify", false, false)
+INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
+INITIALIZE_PASS_END(AssumeSimplifyPassLegacyPass, "assume-simplify",
+                    "Assume Simplify", false, false)
+
+FunctionPass *llvm::createAssumeSimplifyPass() {
+  return new AssumeSimplifyPassLegacyPass();
+}
+
 PreservedAnalyses AssumeBuilderPass::run(Function &F,
                                          FunctionAnalysisManager &AM) {
   AssumptionCache* AC = AM.getCachedResult<AssumptionAnalysis>(F);