caten/air
aIR(=AbstractIR) is a Caten's internal IR and is used to represent computations expressed as either Let-Binding Based IR or a DAG.
Each nodes are represented using a Node
structure, and their list (or tree structure) is maintained by the Graph
CLOS class. The compilation is performed by efficiently manipulating and optimizing the graph using a pattern matcher.
Note that All nodes must be declared using the defnode macro before compilation. This allows node-related errors to be detected and reported during compilation.
Node
[struct] Node
A node is a computation with input sources (reads)
and outputs (writes)
.
Before creating a node using make-node
, the node must be defined using defnode
. Attributes are defined by defnode.
- node-class[keyword] indicates the classification of the node (e.g.:
:BinaryOps, :UnaryOps
). This information is used for debugging purposes. - node-type[keyword] indicates the type of the node (e.g.:
:Add, :Sub, :Mul, :Div
). - node-id[symbol] a unique symbol that exists only once in the namespaces. (usually generated by gensym)
- node-writes[list] a list of symbols that represent the output buffers.
- node-reads[list] a list of symbols or numbers that represent the input buffers. (usually connected with the
(node-writes)
) - node-attr[Attribute] additional information about the node. (e.g.: reduction, dtype, type inference etc...)
[macro] defnode
Defines a new node.
(defnode (class type) (&rest direct-superclasses)
description
&key (placeholder 0) (verify 'identity) (slots))
- class[keyword] an identifier of the node class.
- type[keyword] an identifier of the node type.
- direct-superclasses[list of keyword] a list of superclasses.
- description[string] a description of the node.
- placeholder[(unsigned-byte 32) or -1] when mutating the node in-place, the compiler consumes the placeholder-th read buffer.
- verify[function] a function to verify the arguments.
- slots[list of (symbol &rest slot-options)] a list of slot definitions.
[function] make-node
Create a node with the given class
, type
, writes
, reads
, and attrs
. class
and type
should be defined by defnode
, otherwise the function will produce an error.
- class[keyword] indicates the classification of the node (e.g.:
:BinaryOps, :UnaryOps
). This information is used for debugging purposes. - type[keyword] indicates the type of the node (e.g.:
:Add, :Sub, :Mul, :Div
). - writes[list] a list of symbols that represent the output buffers.
- reads[list] a list of symbols or numbers that represent the input buffers. (usually connected with the
(node-writes)
) - attrs[keyword and value pairs] initializers for the Attribute class.
[function] copy-node
Create a deepcopy of the given node.[function] getattrs
Return the list of attributes of the node.[function] getattr
Return the value of the attributeid
of the node. If the attribute is not defined, it will produce an error. If allow-undefined
is t, it returns nil without error.
This function is setfable.
[function] remattr
Equivalent to:
Examples
Graph
[class] Graph
A Graph is a data structure used to handle a collection of nodes.
Graph has a list of nodes (nodes), node inputs (seen), and node outputs (outputs).
Unlike FastGraph
, Graph does not assume that the nodes form a DAG. Additionally, it guarantees that the nodes will not be sorted during each process of the Pattern Matcher. Graph structures, such as Let-Binding, are represented using Graph.
Note: Using Graph may lead to performance degradation if the graph is a DAG. Please use FastGraph instead.
[class] FastGraph
FastGraph
is a subclass of Graph
that implements faster node searches based on the assumption that the nodes form a DAG. (It is approximately 20 times faster than Graph, in the larger scale.)
Since FastGraph
stores nodes as a hash-table, there are some constraints on node operations. If necessary, converting between (->fast-graph graph)
and (->graph graph)
can be done frequently with minimal impact on performance.
[generic] copy-graph
Creates a copy of the given graph.[function] make-graph
Creates a new Graph object with the given nodes.[generic] graph-nodes
NIL
[generic] id->value
Returns a node whose node-writes includes the given id.[generic] id->users
Returns a list of nodes whose node-reads includes the given id.[generic] remnode
Removes all node where node-id =id
from the given graph.
[generic] insert-nodes
Inserts the given nodes (list) into the graph.[function] ->fast-graph
Creates a FastGraph object from the given graph.
[generic] ->graph
Converts the given graph to a fast graph.[generic] verify-graph
Verify the consistency of the graphs and simplify them by doing following things: - Checks if all variables are immutable - All variables appeared in read, are also defined in writes. - Purge all isolated graph - Sort nodes by time. - Set no-purge=T to ignore purge isolated graph step. This has no effect on FastGraph.Simplifier
[macro] defsimplifier
Defines a new simplifier namedname
. The defined function has a following form:
The graph
is a graph to simplify. The no-verify
is a flag to skip the verification process. The return-changed-p
is a flag to return the result of the simplification process, or a boolean indicating that the graph was changed during simplification process.. The speed
is an optimization level. The rules
are a list of simplification rules. Each rule has a form:
(TODO: Documentation)
(See also: ./source/aasm/constant-folding.lisp
)
Visualizer
[function] ->dot
Visualizes the graph using graphviz(requirement). Set open=t to open the resulting image in the default browser. A tmp file is created at the pathname location. The graph is saved as a .png and .html file. The title is used in the html file.