| \brief Annotations allow for generic
| manipulation of neural network operations.
| The base class contains a saved void* pointer
| for external use. Derived classes add richer
| semantics to the annotation and it is
| encouraged to use them.
| \brief A basic block holds a reference to
| a subgraph of the data flow graph as well as
| an ordering on instruction execution. Basic
| blocks are used for control flow analysis.
| \brief Control flow graph is a graph of basic
| blocks that can be used as an analysis tool.
|
| \note G Must be of type Graph<T, U>.
| Attempts to create a realistic dataflow
| graph that shows a fuse procedure.
|
\brief Edge within a NomGraph.
| This file defines utilities for matching
| subgraphs.
|
| MatchGraph is a graph of MatchPredicate
| and it contains utilities for subgraph
| matching.
|
| (TODO) the subgraph matching methods
| currently still requires a root match
| node to be passed in.
|
| We should improve the matching algorithm
| to eliminate this requirement.
|
| MatchGraph is a graph of MatchPredicate.
|
| MatchPredicate needs a predicate for
| node matching and
|
| - includeInSubgraph: whether this
| node and nodes/edges reachable from
| it should be included in the return matched
| subgraph (if the pattern matches).
|
| This is useful in case we would like to
| specify a matching pattern but do not
| want part of the pattern to be included
| in the returned subgraph.
|
| - A count, which means we may want to match
| this node multiple times from its incoming
| edges. The count can be unlimited (think
| about it as a regex star).
|
| - If nonTerminal flag is set, it means
| we will not consider outgoing edges
| from the node when doing subgraph matching.
|
| ———–
| @brief
|
| A simple graph implementation
|
| Everything is owned by the graph to simplify
| storage concerns.
|
\brief NomNode within a NomGraph.
| ———–
| @brief
|
| This class enables a listener pattern.
|
| It is to be used with a “curious recursive
| pattern” i.e. Derived : public Notifier
| {}
|
| Implements accessors for a generic type T. If
| the type is not specified (i.e., void template
| type) then the partial specification gives an
| empty type.
| ———–
| @brief
|
| Effectively a constant reference to
| a graph.
|
| ———–
| @note
|
| A Subgraph could actually point to an
| entire NomGraph.
|
| Subgraphs can only contain references
| to nodes/edges in a NomGraph.
|
| They are technically mutable, but this
| should be viewed as a construction helper
| rather than a fact to be exploited. There
| are no deleters, for example.
|
| ———–
| @brief
|
| Tarjans algorithm implementation.
|
| See details on how the algorithm works
| here: https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
|
| The algorithm works by annotating nodes,
| but we want to be able to handle generic
| graphs. Thus, we wrap the input graph
| with nodes that contain data composed
| of references to the original graph
| (for later recovery) and the data required
| for the algorithm (see NodeWrapper).
|
| We then run the algorithm and return
| a reverse-topologically sorted vector
| of strongly connect components in the
| form of Subgraphs on the Graph.
|
| ———–
| @note
|
| Head/Tail is used in reverse in Tarjan’s
| early papers.
|
| \bug Edges not included in returned
| subgraphs.
|
| Very simple random number generator
| used to generate platform independent
| random test data.
|
| \brief Topological sort using DFS.
|
| This algorithm takes a Graph object and
| returns node references in topological order.
| Although these seem generic, they make
| subtle assumptions about the structure
| of the graph that is 100% valid for NNModule
| graphs but not any graph (such as data
| being a unique_ptr).
|
| ———–
| @brief
|
| A binary graph matching algorithm based
| on Kahn’s algorithm.
|
TODO: move this to more generic location.
TODO: [algo] improve this algorithm, as it is horrendously inefficient.
Convert a graph to dot string.
| Convert a graph to dot string and annotate
| subgraph clusters.
|
Convert a subgraph to dot string.
Create an operator
Create an output tensor node
\brief Create subgraph object from graph.
\brief Deletes a referenced node from the control flow graph.
| \brief Map all nodes to their dominance
| frontiers: a set of nodes that does not
| strictly dominate the given node but does
| dominate an immediate predecessor. This is
| useful as it is the exact location for the
| insertion of phi nodes in SSA representation.
| \brief A dominator tree finder. Runs in
| O(M*N), there exist more efficient
| implementations.
|
| High level description of the algorithm:
|
| 1) Find a map of {node}->{dominator set}
| –
| allNodes = reachable(root)
| for n in nodes:
| temporarily delete n from the graph
| dom[n] = allNodes - reachable(root)
| restore n to the graph
|
| 2) Construct tree from that map
| –
| starting at root, BFS in dominatorMap:
| if newnode has inedge, delete it
| draw edge from parent to child
| Get the name of the node regardless of
| underlying type.
|
Get all nodes tracked by CF graph
NeuralNetData specific helpers.
| The node has a unique consumer (there
| may be multiple edges from output to
| the single consumer).
|
| ———–
| @brief
|
| Map all nodes in the graph to their immediate
| dominators.
|
| ———–
| @brief
|
| Induces edges on a subgraph by connecting
| all nodes that are connected in the original
| graph.
|
\brief Helper for dominator tree finding.
| Set all consumers of first argument
| to consume the second argument
|
Call reset before creating a new TestMatchGraph.
| ———–
| @brief
|
| A function wrapper to infer the graph
| template parameters.
|
| Node matches a criteria (string) if
| the data string is the same as the criteria.
| Special case: “*” will match any thing.
|
| Our test graph looks like this:
| +—––+
| | entry |
| +—––+
| |
| |
| v
| +—––+
| | 1 |
| +—––+
| |
| |
| v
| +—+ +—––+
| | 4 | <– | 2 |
| +—+ +—––+
| | |
| | |
| | v
| | +—––+
| | | 3 |
| | +—––+
| | |
| | |
| | v
| | +—––+
| +—–> | 6 |
| +—––+
| |
| |
| v
| +—+ +—––+
| | 5 | –> | 7 |
| +—+ +—––+
| |
| |
| v
| +—––+
| | exit |
| +—––+
|
| Here is the code used to generate the dot file
| for it:
|
| auto str = nom::converters::convertToDotString(&graph,
| [](nom::Graph
std::string::NodeRef node) {
| std::map<std::string, std::string> labelMap;
| labelMap[“label”] = node->data();
| return labelMap;
| });
| \brief A function wrapper to infer the graph
| template parameters.
|
| TODO change this to const GraphT& g
| Helper methods to make it less verbose
| to create match graphs.
|