WaitingOnGraph class template. More...
#include "llvm/ExecutionEngine/Orc/WaitingOnGraph.h"
Classes | |
| struct | EmitResult |
| class | SimplifyResult |
| class | SuperNode |
| class | SuperNodeBuilder |
| Build SuperNodes from (definition-set, dependence-set) pairs. More... | |
Public Types | |
| enum class | ExternalState { None , Ready , Failed } |
| using | ContainerId = ContainerIdT |
| using | ElementId = ElementIdT |
| using | ElementSet = DenseSet<ElementId> |
| using | ContainerElementsMap = DenseMap<ContainerId, ElementSet> |
Public Member Functions | |
| template<typename GetExternalStateFn> | |
| EmitResult | emit (SimplifyResult SR, GetExternalStateFn &&GetExternalState) |
| Add the given SuperNodes to the graph, returning any SuperNodes that move to the Ready or Failed states as a result. | |
| std::vector< std::unique_ptr< SuperNode > > | fail (const ContainerElementsMap &Failed) |
| Identify the given symbols as Failed. | |
| bool | validate (raw_ostream &Log) |
Static Public Member Functions | |
| static SimplifyResult | simplify (std::vector< std::unique_ptr< SuperNode > > SNs) |
| Preprocess a list of SuperNodes to remove all intra-SN dependencies. | |
Friends | |
| class | WaitingOnGraphTest |
Detailed Description
class llvm::orc::detail::WaitingOnGraph< ContainerIdT, ElementIdT >
WaitingOnGraph class template.
This type is intended to provide efficient dependence tracking for Symbols in an ORC program.
WaitingOnGraph models a directed graph with four partitions:
- Not-yet-emitted nodes: Nodes identified as waited-on in an emit operation.
- Emitted nodes: Nodes emitted and waiting on some non-empty set of other nodes.
- Ready nodes: Nodes emitted and not waiting on any other nodes (either because they weren't waiting on any nodes when they were emitted, or because all transitively waited-on nodes have since been emitted).
- Failed nodes: Nodes that have been marked as failed-to-emit, and nodes that were found to transitively wait-on some failed node.
Nodes are added to the graph by emit and fail operations.
The emit operation takes a bipartite local dependence graph as an argument and returns... a. the set of nodes (both existing and newly added from the local dependence graph) whose waiting-on set is the empty set, and... b. the set of newly added nodes that are found to depend on failed nodes.
The fail operation takes a set of failed nodes and returns the set of Emitted nodes that were waiting on the failed nodes.
The concrete representation adopts several approaches for efficiency:
- Only Emitted and Not-yet-emitted nodes are represented explicitly. Ready and Failed nodes are represented by the values returned by the GetExternalStateFn argument to emit.
- Labels are (Container, Element) pairs that are intended to represent ORC symbols (ORC uses types Container = JITDylib, Element = NonOwningSymbolStringPtr). The internal representation of the graph is optimized on the assumption that there are many more Elements (symbol names) than Containers (JITDylibs) used to construct the labels. (Consider for example the common case where most JIT'd code is placed in a single "main" JITDylib).
- The data structure stores SuperNodes which have multiple labels. This reduces the number of nodes and edges in the graph in the common case where many JIT symbols have the same set of dependencies. SuperNodes are coalesced when their dependence sets become equal.
- The simplify method can be applied to an initial local dependence graph (as a list of SuperNodes) to eliminate any internal dependence relationships that would have to be propagated internally by emit. Access to the WaitingOnGraph is assumed to be guarded by a mutex (ORC will access it from multiple threads) so this allows some pre-processing to be performed outside the mutex.
Definition at line 81 of file WaitingOnGraph.h.
Member Typedef Documentation
◆ ContainerElementsMap
| using llvm::orc::detail::WaitingOnGraph< ContainerIdT, ElementIdT >::ContainerElementsMap = DenseMap<ContainerId, ElementSet> |
Definition at line 88 of file WaitingOnGraph.h.
◆ ContainerId
| using llvm::orc::detail::WaitingOnGraph< ContainerIdT, ElementIdT >::ContainerId = ContainerIdT |
Definition at line 85 of file WaitingOnGraph.h.
◆ ElementId
| using llvm::orc::detail::WaitingOnGraph< ContainerIdT, ElementIdT >::ElementId = ElementIdT |
Definition at line 86 of file WaitingOnGraph.h.
◆ ElementSet
| using llvm::orc::detail::WaitingOnGraph< ContainerIdT, ElementIdT >::ElementSet = DenseSet<ElementId> |
Definition at line 87 of file WaitingOnGraph.h.
Member Enumeration Documentation
◆ ExternalState
|
strong |
| Enumerator | |
|---|---|
| None | |
| Ready | |
| Failed | |
Definition at line 287 of file WaitingOnGraph.h.
Member Function Documentation
◆ emit()
|
inline |
Add the given SuperNodes to the graph, returning any SuperNodes that move to the Ready or Failed states as a result.
The GetExternalState function is used to represent SuperNodes that have already become Ready or Failed (since such nodes are not explicitly represented in the graph).
Definition at line 295 of file WaitingOnGraph.h.
◆ fail()
|
inline |
Identify the given symbols as Failed.
The elements of the Failed map will not be included in the returned result, so clients should take whatever actions are needed to mark this as failed in their external representation.
Definition at line 373 of file WaitingOnGraph.h.
◆ simplify()
|
inlinestatic |
Preprocess a list of SuperNodes to remove all intra-SN dependencies.
Definition at line 260 of file WaitingOnGraph.h.
◆ validate()
|
inline |
Definition at line 416 of file WaitingOnGraph.h.
Friends And Related Symbol Documentation
◆ WaitingOnGraphTest
|
friend |
Definition at line 82 of file WaitingOnGraph.h.
The documentation for this class was generated from the following file:
- include/llvm/ExecutionEngine/Orc/WaitingOnGraph.h
Generated on for LLVM by
1.14.0