File Manager

003 File Manager

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

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

📁 ..
📄 AArch64TargetParser.def(12.01 KB)
📄 AArch64TargetParser.h(4.89 KB)
📄 AMDGPUMetadata.h(17.98 KB)
📄 AMDHSAKernelDescriptor.h(7.63 KB)
📄 ARMAttributeParser.h(3.2 KB)
📄 ARMBuildAttributes.h(8.6 KB)
📄 ARMEHABI.h(3.72 KB)
📄 ARMTargetParser.def(18.94 KB)
📄 ARMTargetParser.h(8.76 KB)
📄 ARMWinEH.h(18.27 KB)
📄 AlignOf.h(1.56 KB)
📄 Alignment.h(12.95 KB)
📄 Allocator.h(16.54 KB)
📄 AllocatorBase.h(3.87 KB)
📄 ArrayRecycler.h(4.78 KB)
📄 Atomic.h(1.09 KB)
📄 AtomicOrdering.h(6.01 KB)
📄 Automaton.h(9.64 KB)
📄 Base64.h(1.84 KB)
📄 BinaryByteStream.h(9.14 KB)
📄 BinaryItemStream.h(3.63 KB)
📄 BinaryStream.h(3.75 KB)
📄 BinaryStreamArray.h(12.46 KB)
📄 BinaryStreamError.h(1.29 KB)
📄 BinaryStreamReader.h(11.01 KB)
📄 BinaryStreamRef.h(10.09 KB)
📄 BinaryStreamWriter.h(7.79 KB)
📄 BlockFrequency.h(2.41 KB)
📄 BranchProbability.h(7.92 KB)
📄 BuryPointer.h(1.03 KB)
📄 CBindingWrapping.h(1.86 KB)
📄 CFGDiff.h(9.95 KB)
📄 CFGUpdate.h(4.12 KB)
📄 COM.h(1004 B)
📄 CRC.h(1.63 KB)
📄 CachePruning.h(3.5 KB)
📄 Capacity.h(972 B)
📄 Casting.h(13.92 KB)
📄 CheckedArithmetic.h(3.71 KB)
📄 Chrono.h(5.78 KB)
📄 CodeGen.h(1.96 KB)
📄 CodeGenCoverage.h(1.18 KB)
📄 CommandLine.h(71.22 KB)
📄 Compiler.h(19.5 KB)
📄 Compression.h(1.39 KB)
📄 ConvertUTF.h(11.4 KB)
📄 CrashRecoveryContext.h(9.26 KB)
📄 DJB.h(1.05 KB)
📄 DOTGraphTraits.h(5.58 KB)
📄 DataExtractor.h(30.28 KB)
📄 DataTypes.h(775 B)
📄 Debug.h(4.7 KB)
📄 DebugCounter.h(7.01 KB)
📄 DynamicLibrary.h(5.77 KB)
📄 ELFAttributeParser.h(2.22 KB)
📄 ELFAttributes.h(1.02 KB)
📄 Endian.h(14.28 KB)
📄 EndianStream.h(1.93 KB)
📄 Errc.h(3.8 KB)
📄 Errno.h(1.45 KB)
📄 Error.h(43.82 KB)
📄 ErrorHandling.h(6.39 KB)
📄 ErrorOr.h(7.48 KB)
📄 ExtensibleRTTI.h(4.02 KB)
📄 FileCheck.h(6.69 KB)
📄 FileCollector.h(3.74 KB)
📄 FileOutputBuffer.h(3.36 KB)
📄 FileSystem.h(53.03 KB)
📄 FileUtilities.h(3.83 KB)
📄 Format.h(9.45 KB)
📄 FormatAdapters.h(3.38 KB)
📄 FormatCommon.h(2.05 KB)
📄 FormatProviders.h(15.27 KB)
📄 FormatVariadic.h(9.88 KB)
📄 FormatVariadicDetails.h(5.3 KB)
📄 FormattedStream.h(6.42 KB)
📄 GenericDomTree.h(30.89 KB)
📄 GenericDomTreeConstruction.h(63.42 KB)
📄 GenericIteratedDominanceFrontier.h(7.31 KB)
📄 GlobPattern.h(1.35 KB)
📄 GraphWriter.h(11.79 KB)
📄 Host.h(2.68 KB)
📄 InitLLVM.h(1.79 KB)
📄 ItaniumManglingCanonicalizer.h(3.17 KB)
📄 JSON.h(28.25 KB)
📄 KnownBits.h(8.35 KB)
📄 LEB128.h(5.74 KB)
📄 LineIterator.h(2.62 KB)
📄 Locale.h(223 B)
📄 LockFileManager.h(3.13 KB)
📄 LowLevelTypeImpl.h(11.94 KB)
📄 MD5.h(3.39 KB)
📄 MSVCErrorWorkarounds.h(2.62 KB)
📄 MachineValueType.h(42.37 KB)
📄 ManagedStatic.h(4.21 KB)
📄 MathExtras.h(32.81 KB)
📄 MemAlloc.h(3.21 KB)
📄 Memory.h(6.94 KB)
📄 MemoryBuffer.h(10.98 KB)
📄 MipsABIFlags.h(3.92 KB)
📄 Mutex.h(2.14 KB)
📄 NativeFormatting.h(1.64 KB)
📄 OnDiskHashTable.h(21.97 KB)
📄 OptimizedStructLayout.h(5.89 KB)
📄 Parallel.h(5.99 KB)
📄 Path.h(15.6 KB)
📄 PluginLoader.h(1.29 KB)
📄 PointerLikeTypeTraits.h(5.69 KB)
📄 PrettyStackTrace.h(4.45 KB)
📄 Printable.h(1.5 KB)
📄 Process.h(9.31 KB)
📄 Program.h(10.35 KB)
📄 RISCVAttributeParser.h(1.15 KB)
📄 RISCVAttributes.h(1.2 KB)
📄 RISCVTargetParser.def(446 B)
📄 RWMutex.h(5.65 KB)
📄 RandomNumberGenerator.h(2.29 KB)
📄 Recycler.h(3.47 KB)
📄 RecyclingAllocator.h(2.38 KB)
📄 Regex.h(4.37 KB)
📄 Registry.h(5.14 KB)
📄 ReverseIteration.h(360 B)
📄 SHA1.h(2.37 KB)
📄 SMLoc.h(1.78 KB)
📄 SMTAPI.h(16.33 KB)
📄 SaveAndRestore.h(1.02 KB)
📄 ScaledNumber.h(30.65 KB)
📄 ScopedPrinter.h(11.39 KB)
📄 Signals.h(5.22 KB)
📄 Signposts.h(1.29 KB)
📄 SmallVectorMemoryBuffer.h(2.28 KB)
📁 Solaris
📄 SourceMgr.h(10.37 KB)
📄 SpecialCaseList.h(6.01 KB)
📄 StringSaver.h(1.94 KB)
📄 SuffixTree.h(13.15 KB)
📄 SwapByteOrder.h(4.8 KB)
📄 SymbolRemappingReader.h(4.36 KB)
📄 SystemUtils.h(1.02 KB)
📄 TarWriter.h(941 B)
📄 TargetOpcodes.def(22.01 KB)
📄 TargetParser.h(4.08 KB)
📄 TargetRegistry.h(46.87 KB)
📄 TargetSelect.h(6.2 KB)
📄 TaskQueue.h(4.24 KB)
📄 ThreadLocal.h(2.08 KB)
📄 ThreadPool.h(3.44 KB)
📄 Threading.h(10.62 KB)
📄 TimeProfiler.h(3.46 KB)
📄 Timer.h(8.93 KB)
📄 ToolOutputFile.h(2.24 KB)
📄 TrailingObjects.h(15.19 KB)
📄 TrigramIndex.h(2.84 KB)
📄 TypeName.h(2.13 KB)
📄 TypeSize.h(8.53 KB)
📄 Unicode.h(2.5 KB)
📄 UnicodeCharRanges.h(3.27 KB)
📄 Valgrind.h(1.16 KB)
📄 VersionTuple.h(5.22 KB)
📄 VirtualFileSystem.h(28.28 KB)
📄 Watchdog.h(1.15 KB)
📄 Win64EH.h(4.82 KB)
📁 Windows
📄 WindowsError.h(541 B)
📄 WithColor.h(4.64 KB)
📄 X86DisassemblerDecoderCommon.h(29.39 KB)
📄 X86TargetParser.def(8.21 KB)
📄 X86TargetParser.h(3.57 KB)
📄 YAMLParser.h(16.29 KB)
📄 YAMLTraits.h(67.62 KB)
📄 circular_raw_ostream.h(4.97 KB)
📄 raw_os_ostream.h(1.29 KB)
📄 raw_ostream.h(20.82 KB)
📄 raw_sha1_ostream.h(1.29 KB)
📄 thread.h(1.33 KB)
📄 type_traits.h(6.75 KB)
📄 xxhash.h(1.92 KB)

Editing: CFGDiff.h

//===- CFGDiff.h - Define a CFG snapshot. -----------------------*- 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
//
//===----------------------------------------------------------------------===//
//
// This file defines specializations of GraphTraits that allows generic
// algorithms to see a different snapshot of a CFG.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_SUPPORT_CFGDIFF_H
#define LLVM_SUPPORT_CFGDIFF_H

#include "llvm/ADT/GraphTraits.h"
#include "llvm/ADT/iterator.h"
#include "llvm/ADT/iterator_range.h"
#include "llvm/Support/CFGUpdate.h"
#include "llvm/Support/type_traits.h"
#include <cassert>
#include <cstddef>
#include <iterator>

// Two booleans are used to define orders in graphs:
// InverseGraph defines when we need to reverse the whole graph and is as such
// also equivalent to applying updates in reverse.
// InverseEdge defines whether we want to change the edges direction. E.g., for
// a non-inversed graph, the children are naturally the successors when
// InverseEdge is false and the predecessors when InverseEdge is true.

// We define two base clases that call into GraphDiff, one for successors
// (CFGSuccessors), where InverseEdge is false, and one for predecessors
// (CFGPredecessors), where InverseEdge is true.
// FIXME: Further refactoring may merge the two base classes into a single one
// templated / parametrized on using succ_iterator/pred_iterator and false/true
// for the InverseEdge.

// CFGViewChildren and CFGViewPredecessors, both can be parametrized to
// consider the graph inverted or not (i.e. InverseGraph). Successors
// implicitly has InverseEdge = false and Predecessors implicitly has
// InverseEdge = true (see calls to GraphDiff methods in there). The GraphTraits
// instantiations that follow define the value of InverseGraph.

// GraphTraits instantiations:
// - GraphDiff<BasicBlock *> is equivalent to InverseGraph = false
// - GraphDiff<Inverse<BasicBlock *>> is equivalent to InverseGraph = true
// - second pair item is BasicBlock *, then InverseEdge = false (so it inherits
// from CFGViewChildren).
// - second pair item is Inverse<BasicBlock *>, then InverseEdge = true (so it
// inherits from CFGViewPredecessors).

// The 4 GraphTraits are as follows:
// 1. std::pair<const GraphDiff<BasicBlock *> *, BasicBlock *>> :
//        CFGViewChildren<false>
// Regular CFG, children means successors, InverseGraph = false,
// InverseEdge = false.
// 2. std::pair<const GraphDiff<Inverse<BasicBlock *>> *, BasicBlock *>> :
//        CFGViewChildren<true>
// Reverse the graph, get successors but reverse-apply updates,
// InverseGraph = true, InverseEdge = false.
// 3. std::pair<const GraphDiff<BasicBlock *> *, Inverse<BasicBlock *>>> :
//        CFGViewPredecessors<false>
// Regular CFG, reverse edges, so children mean predecessors,
// InverseGraph = false, InverseEdge = true.
// 4. std::pair<const GraphDiff<Inverse<BasicBlock *>> *, Inverse<BasicBlock *>>
//        : CFGViewPredecessors<true>
// Reverse the graph and the edges, InverseGraph = true, InverseEdge = true.

namespace llvm {

// GraphDiff defines a CFG snapshot: given a set of Update<NodePtr>, provide
// utilities to skip edges marked as deleted and return a set of edges marked as
// newly inserted. The current diff treats the CFG as a graph rather than a
// multigraph. Added edges are pruned to be unique, and deleted edges will
// remove all existing edges between two blocks.
template <typename NodePtr, bool InverseGraph = false> class GraphDiff {
  using UpdateMapType = SmallDenseMap<NodePtr, SmallVector<NodePtr, 2>>;
  struct EdgesInsertedDeleted {
    UpdateMapType Succ;
    UpdateMapType Pred;
  };
  // Store Deleted edges on position 0, and Inserted edges on position 1.
  EdgesInsertedDeleted Edges[2];
  // By default, it is assumed that, given a CFG and a set of updates, we wish
  // to apply these updates as given. If UpdatedAreReverseApplied is set, the
  // updates will be applied in reverse: deleted edges are considered re-added
  // and inserted edges are considered deleted when returning children.
  bool UpdatedAreReverseApplied;
  // Using a singleton empty vector for all node requests with no
  // children.
  SmallVector<NodePtr, 0> Empty;

// Keep the list of legalized updates for a deterministic order of updates
  // when using a GraphDiff for incremental updates in the DominatorTree.
  // The list is kept in reverse to allow popping from end.
  SmallVector<cfg::Update<NodePtr>, 4> LegalizedUpdates;

void printMap(raw_ostream &OS, const UpdateMapType &M) const {
    for (auto Pair : M)
      for (auto Child : Pair.second) {
        OS << "(";
        Pair.first->printAsOperand(OS, false);
        OS << ", ";
        Child->printAsOperand(OS, false);
        OS << ") ";
      }
    OS << "\n";
  }

public:
  GraphDiff() : UpdatedAreReverseApplied(false) {}
  GraphDiff(ArrayRef<cfg::Update<NodePtr>> Updates,
            bool ReverseApplyUpdates = false) {
    cfg::LegalizeUpdates<NodePtr>(Updates, LegalizedUpdates, InverseGraph,
                                  /*ReverseResultOrder=*/true);
    // The legalized updates are stored in reverse so we can pop_back when doing
    // incremental updates.
    for (auto U : LegalizedUpdates) {
      unsigned IsInsert =
          (U.getKind() == cfg::UpdateKind::Insert) == !ReverseApplyUpdates;
      Edges[IsInsert].Succ[U.getFrom()].push_back(U.getTo());
      Edges[IsInsert].Pred[U.getTo()].push_back(U.getFrom());
    }
    UpdatedAreReverseApplied = ReverseApplyUpdates;
  }

auto getLegalizedUpdates() const {
    return make_range(LegalizedUpdates.begin(), LegalizedUpdates.end());
  }

unsigned getNumLegalizedUpdates() const { return LegalizedUpdates.size(); }

cfg::Update<NodePtr> popUpdateForIncrementalUpdates() {
    assert(!LegalizedUpdates.empty() && "No updates to apply!");
    auto U = LegalizedUpdates.pop_back_val();
    unsigned IsInsert =
        (U.getKind() == cfg::UpdateKind::Insert) == !UpdatedAreReverseApplied;
    auto &SuccList = Edges[IsInsert].Succ[U.getFrom()];
    assert(SuccList.back() == U.getTo());
    SuccList.pop_back();
    if (SuccList.empty())
      Edges[IsInsert].Succ.erase(U.getFrom());

auto &PredList = Edges[IsInsert].Pred[U.getTo()];
    assert(PredList.back() == U.getFrom());
    PredList.pop_back();
    if (PredList.empty())
      Edges[IsInsert].Pred.erase(U.getTo());
    return U;
  }

bool ignoreChild(const NodePtr BB, NodePtr EdgeEnd, bool InverseEdge) const {
    // Used to filter nullptr in clang.
    if (EdgeEnd == nullptr)
      return true;
    auto &DeleteChildren =
        (InverseEdge != InverseGraph) ? Edges[0].Pred : Edges[0].Succ;
    auto It = DeleteChildren.find(BB);
    if (It == DeleteChildren.end())
      return false;
    auto &EdgesForBB = It->second;
    return llvm::find(EdgesForBB, EdgeEnd) != EdgesForBB.end();
  }

iterator_range<typename SmallVectorImpl<NodePtr>::const_iterator>
  getAddedChildren(const NodePtr BB, bool InverseEdge) const {
    auto &InsertChildren =
        (InverseEdge != InverseGraph) ? Edges[1].Pred : Edges[1].Succ;
    auto It = InsertChildren.find(BB);
    if (It == InsertChildren.end())
      return make_range(Empty.begin(), Empty.end());
    return make_range(It->second.begin(), It->second.end());
  }

void print(raw_ostream &OS) const {
    OS << "===== GraphDiff: CFG edge changes to create a CFG snapshot. \n"
          "===== (Note: notion of children/inverse_children depends on "
          "the direction of edges and the graph.)\n";
    OS << "Children to insert:\n\t";
    printMap(OS, Edges[1].Succ);
    OS << "Children to delete:\n\t";
    printMap(OS, Edges[0].Succ);
    OS << "Inverse_children to insert:\n\t";
    printMap(OS, Edges[1].Pred);
    OS << "Inverse_children to delete:\n\t";
    printMap(OS, Edges[0].Pred);
    OS << "\n";
  }

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  LLVM_DUMP_METHOD void dump() const { print(dbgs()); }
#endif
};

template <typename GraphT, bool InverseGraph = false, bool InverseEdge = false,
          typename GT = GraphTraits<GraphT>>
struct CFGViewChildren {
  using DataRef = const GraphDiff<typename GT::NodeRef, InverseGraph> *;
  using NodeRef = std::pair<DataRef, typename GT::NodeRef>;

template<typename Range>
  static auto makeChildRange(Range &&R, DataRef DR) {
    using Iter = WrappedPairNodeDataIterator<decltype(std::forward<Range>(R).begin()), NodeRef, DataRef>;
    return make_range(Iter(R.begin(), DR), Iter(R.end(), DR));
  }

static auto children(NodeRef N) {

// filter iterator init:
    auto R = make_range(GT::child_begin(N.second), GT::child_end(N.second));
    // This lambda is copied into the iterators and persists to callers, ensure
    // captures are by value or otherwise have sufficient lifetime.
    auto First = make_filter_range(makeChildRange(R, N.first), [N](NodeRef C) {
      return !C.first->ignoreChild(N.second, C.second, InverseEdge);
    });

// new inserts iterator init:
    auto InsertVec = N.first->getAddedChildren(N.second, InverseEdge);
    auto Second = makeChildRange(InsertVec, N.first);

auto CR = concat<NodeRef>(First, Second);

// concat_range contains references to other ranges, returning it would
    // leave those references dangling - the iterators contain
    // other iterators by value so they're safe to return.
    return make_range(CR.begin(), CR.end());
  }

static auto child_begin(NodeRef N) {
    return children(N).begin();
  }

static auto child_end(NodeRef N) {
    return children(N).end();
  }

using ChildIteratorType = decltype(child_end(std::declval<NodeRef>()));
};

template <typename T, bool B>
struct GraphTraits<std::pair<const GraphDiff<T, B> *, T>>
    : CFGViewChildren<T, B> {};
template <typename T, bool B>
struct GraphTraits<std::pair<const GraphDiff<T, B> *, Inverse<T>>>
    : CFGViewChildren<Inverse<T>, B, true> {};
} // end namespace llvm

#endif // LLVM_SUPPORT_CFGDIFF_H

003 File Manager

Editing: CFGDiff.h

Upload File

Create Folder