Intermediate changes

commit_hash:2ec2671384dd8e604d41bc5c52c2f7858e4afea6

1 files changed, 0 insertions, 352 deletions

diff --git a/contrib/libs/llvm14/lib/Support/DAGDeltaAlgorithm.cpp b/contrib/libs/llvm14/lib/Support/DAGDeltaAlgorithm.cpp
deleted file mode 100644
index f1b730e2b58..00000000000
--- a/contrib/libs/llvm14/lib/Support/DAGDeltaAlgorithm.cpp
+++ /dev/null
@@ -1,352 +0,0 @@
-//===--- DAGDeltaAlgorithm.cpp - A DAG Minimization Algorithm --*- C++ -*--===//
-//
-// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
-// See https://llvm.org/LICENSE.txt for license information.
-// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-//===----------------------------------------------------------------------===//
-//
-// The algorithm we use attempts to exploit the dependency information by
-// minimizing top-down. We start by constructing an initial root set R, and
-// then iteratively:
-//
-//   1. Minimize the set R using the test predicate:
-//       P'(S) = P(S union pred*(S))
-//
-//   2. Extend R to R' = R union pred(R).
-//
-// until a fixed point is reached.
-//
-// The idea is that we want to quickly prune entire portions of the graph, so we
-// try to find high-level nodes that can be eliminated with all of their
-// dependents.
-//
-// FIXME: The current algorithm doesn't actually provide a strong guarantee
-// about the minimality of the result. The problem is that after adding nodes to
-// the required set, we no longer consider them for elimination. For strictly
-// well formed predicates, this doesn't happen, but it commonly occurs in
-// practice when there are unmodelled dependencies. I believe we can resolve
-// this by allowing the required set to be minimized as well, but need more test
-// cases first.
-//
-//===----------------------------------------------------------------------===//
-
-#include "llvm/ADT/DAGDeltaAlgorithm.h"
-#include "llvm/ADT/DeltaAlgorithm.h"
-#include "llvm/Support/Debug.h"
-#include "llvm/Support/Format.h"
-#include "llvm/Support/raw_ostream.h"
-#include <algorithm>
-#include <cassert>
-#include <map>
-using namespace llvm;
-
-#define DEBUG_TYPE "dag-delta"
-
-namespace {
-
-class DAGDeltaAlgorithmImpl {
-  friend class DeltaActiveSetHelper;
-
-public:
-  typedef DAGDeltaAlgorithm::change_ty change_ty;
-  typedef DAGDeltaAlgorithm::changeset_ty changeset_ty;
-  typedef DAGDeltaAlgorithm::changesetlist_ty changesetlist_ty;
-  typedef DAGDeltaAlgorithm::edge_ty edge_ty;
-
-private:
-  typedef std::vector<change_ty>::iterator pred_iterator_ty;
-  typedef std::vector<change_ty>::iterator succ_iterator_ty;
-  typedef std::set<change_ty>::iterator pred_closure_iterator_ty;
-  typedef std::set<change_ty>::iterator succ_closure_iterator_ty;
-
-  DAGDeltaAlgorithm &DDA;
-
-  std::vector<change_ty> Roots;
-
-  /// Cache of failed test results. Successful test results are never cached
-  /// since we always reduce following a success. We maintain an independent
-  /// cache from that used by the individual delta passes because we may get
-  /// hits across multiple individual delta invocations.
-  mutable std::set<changeset_ty> FailedTestsCache;
-
-  // FIXME: Gross.
-  std::map<change_ty, std::vector<change_ty> > Predecessors;
-  std::map<change_ty, std::vector<change_ty> > Successors;
-
-  std::map<change_ty, std::set<change_ty> > PredClosure;
-  std::map<change_ty, std::set<change_ty> > SuccClosure;
-
-private:
-  pred_iterator_ty pred_begin(change_ty Node) {
-    assert(Predecessors.count(Node) && "Invalid node!");
-    return Predecessors[Node].begin();
-  }
-  pred_iterator_ty pred_end(change_ty Node) {
-    assert(Predecessors.count(Node) && "Invalid node!");
-    return Predecessors[Node].end();
-  }
-
-  pred_closure_iterator_ty pred_closure_begin(change_ty Node) {
-    assert(PredClosure.count(Node) && "Invalid node!");
-    return PredClosure[Node].begin();
-  }
-  pred_closure_iterator_ty pred_closure_end(change_ty Node) {
-    assert(PredClosure.count(Node) && "Invalid node!");
-    return PredClosure[Node].end();
-  }
-
-  succ_iterator_ty succ_begin(change_ty Node) {
-    assert(Successors.count(Node) && "Invalid node!");
-    return Successors[Node].begin();
-  }
-  succ_iterator_ty succ_end(change_ty Node) {
-    assert(Successors.count(Node) && "Invalid node!");
-    return Successors[Node].end();
-  }
-
-  succ_closure_iterator_ty succ_closure_begin(change_ty Node) {
-    assert(SuccClosure.count(Node) && "Invalid node!");
-    return SuccClosure[Node].begin();
-  }
-  succ_closure_iterator_ty succ_closure_end(change_ty Node) {
-    assert(SuccClosure.count(Node) && "Invalid node!");
-    return SuccClosure[Node].end();
-  }
-
-  void UpdatedSearchState(const changeset_ty &Changes,
-                          const changesetlist_ty &Sets,
-                          const changeset_ty &Required) {
-    DDA.UpdatedSearchState(Changes, Sets, Required);
-  }
-
-  /// ExecuteOneTest - Execute a single test predicate on the change set \p S.
-  bool ExecuteOneTest(const changeset_ty &S) {
-    // Check dependencies invariant.
-    LLVM_DEBUG({
-      for (changeset_ty::const_iterator it = S.begin(), ie = S.end(); it != ie;
-           ++it)
-        for (succ_iterator_ty it2 = succ_begin(*it), ie2 = succ_end(*it);
-             it2 != ie2; ++it2)
-          assert(S.count(*it2) && "Attempt to run invalid changeset!");
-    });
-
-    return DDA.ExecuteOneTest(S);
-  }
-
-public:
-  DAGDeltaAlgorithmImpl(DAGDeltaAlgorithm &DDA, const changeset_ty &Changes,
-                        const std::vector<edge_ty> &Dependencies);
-
-  changeset_ty Run();
-
-  /// GetTestResult - Get the test result for the active set \p Changes with
-  /// \p Required changes from the cache, executing the test if necessary.
-  ///
-  /// \param Changes - The set of active changes being minimized, which should
-  /// have their pred closure included in the test.
-  /// \param Required - The set of changes which have previously been
-  /// established to be required.
-  /// \return - The test result.
-  bool GetTestResult(const changeset_ty &Changes, const changeset_ty &Required);
-};
-
-/// Helper object for minimizing an active set of changes.
-class DeltaActiveSetHelper : public DeltaAlgorithm {
-  DAGDeltaAlgorithmImpl &DDAI;
-
-  const changeset_ty &Required;
-
-protected:
-  /// UpdatedSearchState - Callback used when the search state changes.
-  void UpdatedSearchState(const changeset_ty &Changes,
-                                  const changesetlist_ty &Sets) override {
-    DDAI.UpdatedSearchState(Changes, Sets, Required);
-  }
-
-  bool ExecuteOneTest(const changeset_ty &S) override {
-    return DDAI.GetTestResult(S, Required);
-  }
-
-public:
-  DeltaActiveSetHelper(DAGDeltaAlgorithmImpl &DDAI,
-                       const changeset_ty &Required)
-      : DDAI(DDAI), Required(Required) {}
-};
-
-} // namespace
-
-DAGDeltaAlgorithmImpl::DAGDeltaAlgorithmImpl(
-    DAGDeltaAlgorithm &DDA, const changeset_ty &Changes,
-    const std::vector<edge_ty> &Dependencies)
-    : DDA(DDA) {
-  for (change_ty Change : Changes) {
-    Predecessors.insert(std::make_pair(Change, std::vector<change_ty>()));
-    Successors.insert(std::make_pair(Change, std::vector<change_ty>()));
-  }
-  for (const edge_ty &Dep : Dependencies) {
-    Predecessors[Dep.second].push_back(Dep.first);
-    Successors[Dep.first].push_back(Dep.second);
-  }
-
-  // Compute the roots.
-  for (change_ty Change : Changes)
-    if (succ_begin(Change) == succ_end(Change))
-      Roots.push_back(Change);
-
-  // Pre-compute the closure of the successor relation.
-  std::vector<change_ty> Worklist(Roots.begin(), Roots.end());
-  while (!Worklist.empty()) {
-    change_ty Change = Worklist.back();
-    Worklist.pop_back();
-
-    std::set<change_ty> &ChangeSuccs = SuccClosure[Change];
-    for (pred_iterator_ty it = pred_begin(Change),
-           ie = pred_end(Change); it != ie; ++it) {
-      SuccClosure[*it].insert(Change);
-      SuccClosure[*it].insert(ChangeSuccs.begin(), ChangeSuccs.end());
-      Worklist.push_back(*it);
-    }
-  }
-
-  // Invert to form the predecessor closure map.
-  for (change_ty Change : Changes)
-    PredClosure.insert(std::make_pair(Change, std::set<change_ty>()));
-  for (change_ty Change : Changes)
-    for (succ_closure_iterator_ty it2 = succ_closure_begin(Change),
-                                  ie2 = succ_closure_end(Change);
-         it2 != ie2; ++it2)
-      PredClosure[*it2].insert(Change);
-
-  // Dump useful debug info.
-  LLVM_DEBUG({
-    llvm::errs() << "-- DAGDeltaAlgorithmImpl --\n";
-    llvm::errs() << "Changes: [";
-    for (changeset_ty::const_iterator it = Changes.begin(), ie = Changes.end();
-         it != ie; ++it) {
-      if (it != Changes.begin())
-        llvm::errs() << ", ";
-      llvm::errs() << *it;
-
-      if (succ_begin(*it) != succ_end(*it)) {
-        llvm::errs() << "(";
-        for (succ_iterator_ty it2 = succ_begin(*it), ie2 = succ_end(*it);
-             it2 != ie2; ++it2) {
-          if (it2 != succ_begin(*it))
-            llvm::errs() << ", ";
-          llvm::errs() << "->" << *it2;
-        }
-        llvm::errs() << ")";
-      }
-    }
-    llvm::errs() << "]\n";
-
-    llvm::errs() << "Roots: [";
-    for (std::vector<change_ty>::const_iterator it = Roots.begin(),
-                                                ie = Roots.end();
-         it != ie; ++it) {
-      if (it != Roots.begin())
-        llvm::errs() << ", ";
-      llvm::errs() << *it;
-    }
-    llvm::errs() << "]\n";
-
-    llvm::errs() << "Predecessor Closure:\n";
-    for (change_ty Change : Changes) {
-      llvm::errs() << format("  %-4d: [", Change);
-      for (pred_closure_iterator_ty it2 = pred_closure_begin(Change),
-                                    ie2 = pred_closure_end(Change);
-           it2 != ie2; ++it2) {
-        if (it2 != pred_closure_begin(Change))
-          llvm::errs() << ", ";
-        llvm::errs() << *it2;
-      }
-      llvm::errs() << "]\n";
-    }
-
-    llvm::errs() << "Successor Closure:\n";
-    for (change_ty Change : Changes) {
-      llvm::errs() << format("  %-4d: [", Change);
-      for (succ_closure_iterator_ty it2 = succ_closure_begin(Change),
-                                    ie2 = succ_closure_end(Change);
-           it2 != ie2; ++it2) {
-        if (it2 != succ_closure_begin(Change))
-          llvm::errs() << ", ";
-        llvm::errs() << *it2;
-      }
-      llvm::errs() << "]\n";
-    }
-
-    llvm::errs() << "\n\n";
-  });
-}
-
-bool DAGDeltaAlgorithmImpl::GetTestResult(const changeset_ty &Changes,
-                                          const changeset_ty &Required) {
-  changeset_ty Extended(Required);
-  Extended.insert(Changes.begin(), Changes.end());
-  for (change_ty Change : Changes)
-    Extended.insert(pred_closure_begin(Change), pred_closure_end(Change));
-
-  if (FailedTestsCache.count(Extended))
-    return false;
-
-  bool Result = ExecuteOneTest(Extended);
-  if (!Result)
-    FailedTestsCache.insert(Extended);
-
-  return Result;
-}
-
-DAGDeltaAlgorithm::changeset_ty
-DAGDeltaAlgorithmImpl::Run() {
-  // The current set of changes we are minimizing, starting at the roots.
-  changeset_ty CurrentSet(Roots.begin(), Roots.end());
-
-  // The set of required changes.
-  changeset_ty Required;
-
-  // Iterate until the active set of changes is empty. Convergence is guaranteed
-  // assuming input was a DAG.
-  //
-  // Invariant:  CurrentSet intersect Required == {}
-  // Invariant:  Required == (Required union succ*(Required))
-  while (!CurrentSet.empty()) {
-    LLVM_DEBUG({
-      llvm::errs() << "DAG_DD - " << CurrentSet.size() << " active changes, "
-                   << Required.size() << " required changes\n";
-    });
-
-    // Minimize the current set of changes.
-    DeltaActiveSetHelper Helper(*this, Required);
-    changeset_ty CurrentMinSet = Helper.Run(CurrentSet);
-
-    // Update the set of required changes. Since
-    //   CurrentMinSet subset CurrentSet
-    // and after the last iteration,
-    //   succ(CurrentSet) subset Required
-    // then
-    //   succ(CurrentMinSet) subset Required
-    // and our invariant on Required is maintained.
-    Required.insert(CurrentMinSet.begin(), CurrentMinSet.end());
-
-    // Replace the current set with the predecssors of the minimized set of
-    // active changes.
-    CurrentSet.clear();
-    for (change_ty CT : CurrentMinSet)
-      CurrentSet.insert(pred_begin(CT), pred_end(CT));
-
-    // FIXME: We could enforce CurrentSet intersect Required == {} here if we
-    // wanted to protect against cyclic graphs.
-  }
-
-  return Required;
-}
-
-void DAGDeltaAlgorithm::anchor() {
-}
-
-DAGDeltaAlgorithm::changeset_ty
-DAGDeltaAlgorithm::Run(const changeset_ty &Changes,
-                       const std::vector<edge_ty> &Dependencies) {
-  return DAGDeltaAlgorithmImpl(*this, Changes, Dependencies).Run();
-}