llvm/llvm/lib/Support/DAGDeltaAlgorithm.cpp

//===--- 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>
usingnamespacellvm;

#define DEBUG_TYPE …

namespace {

class DAGDeltaAlgorithmImpl { … };

/// Helper object for minimizing an active set of changes.
class DeltaActiveSetHelper : public DeltaAlgorithm { … };

} // namespace

DAGDeltaAlgorithmImpl::DAGDeltaAlgorithmImpl(
    DAGDeltaAlgorithm &DDA, const changeset_ty &Changes,
    const std::vector<edge_ty> &Dependencies)
    : … { … }

bool DAGDeltaAlgorithmImpl::GetTestResult(const changeset_ty &Changes,
                                          const changeset_ty &Required) { … }

DAGDeltaAlgorithm::changeset_ty
DAGDeltaAlgorithmImpl::Run() { … }

void DAGDeltaAlgorithm::anchor() { … }

DAGDeltaAlgorithm::changeset_ty
DAGDeltaAlgorithm::Run(const changeset_ty &Changes,
                       const std::vector<edge_ty> &Dependencies) { … }