File Manager

003 File Manager

Current Path: /usr/src/contrib/llvm-project/llvm/lib/Support

usr / src / contrib / llvm-project / llvm / lib / Support /

📁 ..
📄 AArch64TargetParser.cpp(8 KB)
📄 ABIBreak.cpp(811 B)
📄 AMDGPUMetadata.cpp(9.37 KB)
📄 APFloat.cpp(155.26 KB)
📄 APInt.cpp(98.08 KB)
📄 APSInt.cpp(1.44 KB)
📄 ARMAttributeParser.cpp(13.94 KB)
📄 ARMBuildAttrs.cpp(3.45 KB)
📄 ARMTargetParser.cpp(18.09 KB)
📄 ARMWinEH.cpp(1.08 KB)
📄 Allocator.cpp(1.35 KB)
📄 Atomic.cpp(1.6 KB)
📄 BinaryStreamError.cpp(1.76 KB)
📄 BinaryStreamReader.cpp(5.24 KB)
📄 BinaryStreamRef.cpp(4.76 KB)
📄 BinaryStreamWriter.cpp(3.36 KB)
📄 BlockFrequency.cpp(2.12 KB)
📄 BranchProbability.cpp(3.44 KB)
📄 BuryPointer.cpp(1.11 KB)
📄 COM.cpp(737 B)
📄 COPYRIGHT.regex(2.65 KB)
📄 CRC.cpp(5.23 KB)
📄 CachePruning.cpp(10.33 KB)
📄 Chrono.cpp(3.17 KB)
📄 CodeGenCoverage.cpp(3.61 KB)
📄 CommandLine.cpp(89.06 KB)
📄 Compression.cpp(3.84 KB)
📄 ConvertUTF.cpp(27.27 KB)
📄 ConvertUTFWrapper.cpp(8.66 KB)
📄 CrashRecoveryContext.cpp(15.45 KB)
📄 DAGDeltaAlgorithm.cpp(12.47 KB)
📄 DJB.cpp(2.71 KB)
📄 DataExtractor.cpp(7.25 KB)
📄 Debug.cpp(5.64 KB)
📄 DebugCounter.cpp(4.95 KB)
📄 DeltaAlgorithm.cpp(3.41 KB)
📄 DynamicLibrary.cpp(6.25 KB)
📄 ELFAttributeParser.cpp(7.27 KB)
📄 ELFAttributes.cpp(1.27 KB)
📄 Errno.cpp(2.18 KB)
📄 Error.cpp(4.72 KB)
📄 ErrorHandling.cpp(11.08 KB)
📄 ExtensibleRTTI.cpp(446 B)
📄 FileCheck.cpp(95.77 KB)
📄 FileCheckImpl.h(34.14 KB)
📄 FileCollector.cpp(9.01 KB)
📄 FileOutputBuffer.cpp(6.62 KB)
📄 FileUtilities.cpp(10.81 KB)
📄 FoldingSet.cpp(15.89 KB)
📄 FormatVariadic.cpp(5.17 KB)
📄 FormattedStream.cpp(5.29 KB)
📄 GlobPattern.cpp(5 KB)
📄 GraphWriter.cpp(9.21 KB)
📄 Hashing.cpp(1.16 KB)
📄 Host.cpp(51.63 KB)
📄 InitLLVM.cpp(1.92 KB)
📄 IntEqClasses.cpp(2.18 KB)
📄 IntervalMap.cpp(4.4 KB)
📄 ItaniumManglingCanonicalizer.cpp(10.77 KB)
📄 JSON.cpp(19.1 KB)
📄 KnownBits.cpp(3.78 KB)
📄 LEB128.cpp(1.19 KB)
📄 LineIterator.cpp(2.61 KB)
📄 Locale.cpp(377 B)
📄 LockFileManager.cpp(10.64 KB)
📄 LowLevelType.cpp(2.09 KB)
📄 MD5.cpp(8.99 KB)
📄 ManagedStatic.cpp(2.37 KB)
📄 MathExtras.cpp(913 B)
📄 MemAlloc.cpp(1.01 KB)
📄 Memory.cpp(1.57 KB)
📄 MemoryBuffer.cpp(18.99 KB)
📄 NativeFormatting.cpp(7.54 KB)
📄 OptimizedStructLayout.cpp(16.7 KB)
📄 Optional.cpp(530 B)
📄 Parallel.cpp(5.08 KB)
📄 Path.cpp(36.52 KB)
📄 PluginLoader.cpp(1.63 KB)
📄 PrettyStackTrace.cpp(10.33 KB)
📄 Process.cpp(3.27 KB)
📄 Program.cpp(3.54 KB)
📄 RISCVAttributeParser.cpp(2.06 KB)
📄 RISCVAttributes.cpp(970 B)
📄 RWMutex.cpp(3.23 KB)
📄 RandomNumberGenerator.cpp(2.86 KB)
📄 Regex.cpp(6.38 KB)
📄 SHA1.cpp(10.43 KB)
📄 ScaledNumber.cpp(9.09 KB)
📄 ScopedPrinter.cpp(1.19 KB)
📄 Signals.cpp(8.35 KB)
📄 Signposts.cpp(3.24 KB)
📄 SmallPtrSet.cpp(9.21 KB)
📄 SmallVector.cpp(3.99 KB)
📄 SourceMgr.cpp(20.08 KB)
📄 SpecialCaseList.cpp(7.48 KB)
📄 Statistic.cpp(8.85 KB)
📄 StringExtras.cpp(4.34 KB)
📄 StringMap.cpp(9.31 KB)
📄 StringRef.cpp(17.41 KB)
📄 StringSaver.cpp(882 B)
📄 SuffixTree.cpp(7.23 KB)
📄 SymbolRemappingReader.cpp(2.94 KB)
📄 SystemUtils.cpp(1.06 KB)
📄 TarWriter.cpp(7.23 KB)
📄 TargetParser.cpp(9.86 KB)
📄 TargetRegistry.cpp(4.6 KB)
📄 ThreadLocal.cpp(1.68 KB)
📄 ThreadPool.cpp(4.4 KB)
📄 Threading.cpp(4.55 KB)
📄 TimeProfiler.cpp(11.63 KB)
📄 Timer.cpp(14.14 KB)
📄 ToolOutputFile.cpp(1.83 KB)
📄 TrigramIndex.cpp(3.24 KB)
📄 Triple.cpp(53.17 KB)
📄 Twine.cpp(4.6 KB)
📄 Unicode.cpp(20.14 KB)
📄 UnicodeCaseFold.cpp(15.32 KB)
📁 Unix
📄 Valgrind.cpp(1.6 KB)
📄 VersionTuple.cpp(2.74 KB)
📄 VirtualFileSystem.cpp(74.17 KB)
📄 Watchdog.cpp(738 B)
📁 Windows
📄 WithColor.cpp(4.35 KB)
📄 X86TargetParser.cpp(27.21 KB)
📄 YAMLParser.cpp(68.53 KB)
📄 YAMLTraits.cpp(28.37 KB)
📄 Z3Solver.cpp(31.44 KB)
📄 circular_raw_ostream.cpp(1.3 KB)
📄 raw_os_ostream.cpp(995 B)
📄 raw_ostream.cpp(28.97 KB)
📄 regcomp.c(39.42 KB)
📄 regengine.inc(26.49 KB)
📄 regerror.c(4.42 KB)
📄 regex2.h(6.82 KB)
📄 regex_impl.h(3.63 KB)
📄 regexec.c(5.71 KB)
📄 regfree.c(2.49 KB)
📄 regstrlcpy.c(1.56 KB)
📄 regutils.h(2.25 KB)
📄 xxhash.cpp(4.07 KB)

Editing: 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 <iterator>
#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) {}
};

}

DAGDeltaAlgorithmImpl::DAGDeltaAlgorithmImpl(
    DAGDeltaAlgorithm &DDA, const changeset_ty &Changes,
    const std::vector<edge_ty> &Dependencies)
    : DDA(DDA) {
  for (changeset_ty::const_iterator it = Changes.begin(),
         ie = Changes.end(); it != ie; ++it) {
    Predecessors.insert(std::make_pair(*it, std::vector<change_ty>()));
    Successors.insert(std::make_pair(*it, std::vector<change_ty>()));
  }
  for (std::vector<edge_ty>::const_iterator it = Dependencies.begin(),
         ie = Dependencies.end(); it != ie; ++it) {
    Predecessors[it->second].push_back(it->first);
    Successors[it->first].push_back(it->second);
  }

// Compute the roots.
  for (changeset_ty::const_iterator it = Changes.begin(),
         ie = Changes.end(); it != ie; ++it)
    if (succ_begin(*it) == succ_end(*it))
      Roots.push_back(*it);

// 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 (changeset_ty::const_iterator it = Changes.begin(),
         ie = Changes.end(); it != ie; ++it)
    PredClosure.insert(std::make_pair(*it, std::set<change_ty>()));
  for (changeset_ty::const_iterator it = Changes.begin(),
         ie = Changes.end(); it != ie; ++it)
    for (succ_closure_iterator_ty it2 = succ_closure_begin(*it),
           ie2 = succ_closure_end(*it); it2 != ie2; ++it2)
      PredClosure[*it2].insert(*it);

// 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 (changeset_ty::const_iterator it = Changes.begin(), ie = Changes.end();
         it != ie; ++it) {
      llvm::errs() << format("  %-4d: [", *it);
      for (pred_closure_iterator_ty it2 = pred_closure_begin(*it),
                                    ie2 = pred_closure_end(*it);
           it2 != ie2; ++it2) {
        if (it2 != pred_closure_begin(*it))
          llvm::errs() << ", ";
        llvm::errs() << *it2;
      }
      llvm::errs() << "]\n";
    }

llvm::errs() << "Successor Closure:\n";
    for (changeset_ty::const_iterator it = Changes.begin(), ie = Changes.end();
         it != ie; ++it) {
      llvm::errs() << format("  %-4d: [", *it);
      for (succ_closure_iterator_ty it2 = succ_closure_begin(*it),
                                    ie2 = succ_closure_end(*it);
           it2 != ie2; ++it2) {
        if (it2 != succ_closure_begin(*it))
          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 (changeset_ty::const_iterator it = Changes.begin(),
         ie = Changes.end(); it != ie; ++it)
    Extended.insert(pred_closure_begin(*it), pred_closure_end(*it));

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 (changeset_ty::const_iterator it = CurrentMinSet.begin(),
           ie = CurrentMinSet.end(); it != ie; ++it)
      CurrentSet.insert(pred_begin(*it), pred_end(*it));

// 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();
}

003 File Manager

Editing: DAGDeltaAlgorithm.cpp

Upload File

Create Folder