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: Automaton.h

//===-- Automaton.h - Support for driving TableGen-produced DFAs ----------===//
//
// 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 implements class that drive and introspect deterministic finite-
// state automata (DFAs) as generated by TableGen's -gen-automata backend.
//
// For a description of how to define an automaton, see
// include/llvm/TableGen/Automaton.td.
//
// One important detail is that these deterministic automata are created from
// (potentially) nondeterministic definitions. Therefore a unique sequence of
// input symbols will produce one path through the DFA but multiple paths
// through the original NFA. An automaton by default only returns "accepted" or
// "not accepted", but frequently we want to analyze what NFA path was taken.
// Finding a path through the NFA states that results in a DFA state can help
// answer *what* the solution to a problem was, not just that there exists a
// solution.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_SUPPORT_AUTOMATON_H
#define LLVM_SUPPORT_AUTOMATON_H

#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Support/Allocator.h"
#include <deque>
#include <map>
#include <memory>
#include <unordered_map>
#include <vector>

namespace llvm {

using NfaPath = SmallVector<uint64_t, 4>;

/// Forward define the pair type used by the automata transition info tables.
///
/// Experimental results with large tables have shown a significant (multiple
/// orders of magnitude) parsing speedup by using a custom struct here with a
/// trivial constructor rather than std::pair<uint64_t, uint64_t>.
struct NfaStatePair {
  uint64_t FromDfaState, ToDfaState;

bool operator<(const NfaStatePair &Other) const {
    return std::make_tuple(FromDfaState, ToDfaState) <
           std::make_tuple(Other.FromDfaState, Other.ToDfaState);
  }
};

namespace internal {
/// The internal class that maintains all possible paths through an NFA based
/// on a path through the DFA.
class NfaTranscriber {
private:
  /// Cached transition table. This is a table of NfaStatePairs that contains
  /// zero-terminated sequences pointed to by DFA transitions.
  ArrayRef<NfaStatePair> TransitionInfo;

/// A simple linked-list of traversed states that can have a shared tail. The
  /// traversed path is stored in reverse order with the latest state as the
  /// head.
  struct PathSegment {
    uint64_t State;
    PathSegment *Tail;
  };

/// We allocate segment objects frequently. Allocate them upfront and dispose
  /// at the end of a traversal rather than hammering the system allocator.
  SpecificBumpPtrAllocator<PathSegment> Allocator;

/// Heads of each tracked path. These are not ordered.
  std::deque<PathSegment *> Heads;

/// The returned paths. This is populated during getPaths.
  SmallVector<NfaPath, 4> Paths;

/// Create a new segment and return it.
  PathSegment *makePathSegment(uint64_t State, PathSegment *Tail) {
    PathSegment *P = Allocator.Allocate();
    *P = {State, Tail};
    return P;
  }

/// Pairs defines a sequence of possible NFA transitions for a single DFA
  /// transition.
  void transition(ArrayRef<NfaStatePair> Pairs) {
    // Iterate over all existing heads. We will mutate the Heads deque during
    // iteration.
    unsigned NumHeads = Heads.size();
    for (unsigned I = 0; I < NumHeads; ++I) {
      PathSegment *Head = Heads[I];
      // The sequence of pairs is sorted. Select the set of pairs that
      // transition from the current head state.
      auto PI = lower_bound(Pairs, NfaStatePair{Head->State, 0ULL});
      auto PE = upper_bound(Pairs, NfaStatePair{Head->State, INT64_MAX});
      // For every transition from the current head state, add a new path
      // segment.
      for (; PI != PE; ++PI)
        if (PI->FromDfaState == Head->State)
          Heads.push_back(makePathSegment(PI->ToDfaState, Head));
    }
    // Now we've iterated over all the initial heads and added new ones,
    // dispose of the original heads.
    Heads.erase(Heads.begin(), std::next(Heads.begin(), NumHeads));
  }

public:
  NfaTranscriber(ArrayRef<NfaStatePair> TransitionInfo)
      : TransitionInfo(TransitionInfo) {
    reset();
  }

ArrayRef<NfaStatePair> getTransitionInfo() const {
    return TransitionInfo;
  }

void reset() {
    Paths.clear();
    Heads.clear();
    Allocator.DestroyAll();
    // The initial NFA state is 0.
    Heads.push_back(makePathSegment(0ULL, nullptr));
  }

void transition(unsigned TransitionInfoIdx) {
    unsigned EndIdx = TransitionInfoIdx;
    while (TransitionInfo[EndIdx].ToDfaState != 0)
      ++EndIdx;
    ArrayRef<NfaStatePair> Pairs(&TransitionInfo[TransitionInfoIdx],
                                 EndIdx - TransitionInfoIdx);
    transition(Pairs);
  }

ArrayRef<NfaPath> getPaths() {
    Paths.clear();
    for (auto *Head : Heads) {
      NfaPath P;
      while (Head->State != 0) {
        P.push_back(Head->State);
        Head = Head->Tail;
      }
      std::reverse(P.begin(), P.end());
      Paths.push_back(std::move(P));
    }
    return Paths;
  }
};
} // namespace internal

/// A deterministic finite-state automaton. The automaton is defined in
/// TableGen; this object drives an automaton defined by tblgen-emitted tables.
///
/// An automaton accepts a sequence of input tokens ("actions"). This class is
/// templated on the type of these actions.
template <typename ActionT> class Automaton {
  /// Map from {State, Action} to {NewState, TransitionInfoIdx}.
  /// TransitionInfoIdx is used by the DfaTranscriber to analyze the transition.
  /// FIXME: This uses a std::map because ActionT can be a pair type including
  /// an enum. In particular DenseMapInfo<ActionT> must be defined to use
  /// DenseMap here.
  /// This is a shared_ptr to allow very quick copy-construction of Automata; this
  /// state is immutable after construction so this is safe.
  using MapTy = std::map<std::pair<uint64_t, ActionT>, std::pair<uint64_t, unsigned>>;
  std::shared_ptr<MapTy> M;
  /// An optional transcription object. This uses much more state than simply
  /// traversing the DFA for acceptance, so is heap allocated.
  std::shared_ptr<internal::NfaTranscriber> Transcriber;
  /// The initial DFA state is 1.
  uint64_t State = 1;
  /// True if we should transcribe and false if not (even if Transcriber is defined).
  bool Transcribe;

public:
  /// Create an automaton.
  /// \param Transitions The Transitions table as created by TableGen. Note that
  ///                    because the action type differs per automaton, the
  ///                    table type is templated as ArrayRef<InfoT>.
  /// \param TranscriptionTable The TransitionInfo table as created by TableGen.
  ///
  /// Providing the TranscriptionTable argument as non-empty will enable the
  /// use of transcription, which analyzes the possible paths in the original
  /// NFA taken by the DFA. NOTE: This is substantially more work than simply
  /// driving the DFA, so unless you require the getPaths() method leave this
  /// empty.
  template <typename InfoT>
  Automaton(ArrayRef<InfoT> Transitions,
            ArrayRef<NfaStatePair> TranscriptionTable = {}) {
    if (!TranscriptionTable.empty())
      Transcriber =
          std::make_shared<internal::NfaTranscriber>(TranscriptionTable);
    Transcribe = Transcriber != nullptr;
    M = std::make_shared<MapTy>();
    for (const auto &I : Transitions)
      // Greedily read and cache the transition table.
      M->emplace(std::make_pair(I.FromDfaState, I.Action),
                 std::make_pair(I.ToDfaState, I.InfoIdx));
  }
  Automaton(const Automaton &Other)
      : M(Other.M), State(Other.State), Transcribe(Other.Transcribe) {
    // Transcriber is not thread-safe, so create a new instance on copy.
    if (Other.Transcriber)
      Transcriber = std::make_shared<internal::NfaTranscriber>(
          Other.Transcriber->getTransitionInfo());
  }

/// Reset the automaton to its initial state.
  void reset() {
    State = 1;
    if (Transcriber)
      Transcriber->reset();
  }

/// Enable or disable transcription. Transcription is only available if
  /// TranscriptionTable was provided to the constructor.
  void enableTranscription(bool Enable = true) {
    assert(Transcriber &&
           "Transcription is only available if TranscriptionTable was provided "
           "to the Automaton constructor");
    Transcribe = Enable;
  }

/// Transition the automaton based on input symbol A. Return true if the
  /// automaton transitioned to a valid state, false if the automaton
  /// transitioned to an invalid state.
  ///
  /// If this function returns false, all methods are undefined until reset() is
  /// called.
  bool add(const ActionT &A) {
    auto I = M->find({State, A});
    if (I == M->end())
      return false;
    if (Transcriber && Transcribe)
      Transcriber->transition(I->second.second);
    State = I->second.first;
    return true;
  }

/// Return true if the automaton can be transitioned based on input symbol A.
  bool canAdd(const ActionT &A) {
    auto I = M->find({State, A});
    return I != M->end();
  }

/// Obtain a set of possible paths through the input nondeterministic
  /// automaton that could be obtained from the sequence of input actions
  /// presented to this deterministic automaton.
  ArrayRef<NfaPath> getNfaPaths() {
    assert(Transcriber && Transcribe &&
           "Can only obtain NFA paths if transcribing!");
    return Transcriber->getPaths();
  }
};

} // namespace llvm

#endif // LLVM_SUPPORT_AUTOMATON_H

003 File Manager

Editing: Automaton.h

Upload File

Create Folder