README
¶
graph
Documentation
¶
Index ¶
- Constants
- type ControlFlowGraph
- type Dfs
- type DominatorJoinGraph
- type DominatorTree
- type Graph
- func (g *Graph) AddEdge(from, to uint)
- func (g *Graph) ControlFlowGraph(entry uint) ControlFlowGraph
- func (g *Graph) Dfs(root uint) Dfs
- func (g *Graph) DominatorJoinGraph(entry uint) DominatorJoinGraph
- func (g *Graph) DominatorTree(entry uint) DominatorTree
- func (g *Graph) Equal(gt *Graph) bool
- func (g *Graph) LivenessAnalysis(use []set.Set[uint], def []set.Set[uint]) Liveness
- func (g *Graph) Size() uint
- type LinkEvalForest
- type Liveness
- type Node
Constants ¶
const Unreachable = ^uint(0)
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type ControlFlowGraph ¶
type ControlFlowGraph struct {
Graph
// BasicBlockToNodes[i] contains the set of nodes in the original graph that
// the i-th basic block contains.
BasicBlockToNodes [][]uint
// NodeToBasicBlock[i] contains the index of the basic block that the i-th
// node in the original graph belongs to.
// NodeToBasicBlock[i] = Unreachable if the original node i is not included
// in the control flow graph, i.e., it is unreachable from the entry node.
NodeToBasicBlock []uint
}
type Dfs ¶
type Dfs struct {
// PreOrder[v] is the index of v in the DFS pre-order traversal.
PreOrder []uint
// PreOrderReversed[i] is the node with the i-th index in the preorder.
PreOrderReversed []uint
// PostOrder[v] is the index of v in the DFS post-order traversal.
PostOrder []uint
// Timeline is a slice of length 2n, where each push and pop operation
// during the DFS traversal of the stack is recorded.
//
// Operations are ordered in chronological order. If Timeline[i] = k,
// where k in [0, n), then the i-th operation in the traversal was a push
// operation of the value k. Otherwise, if k in [n, 2n), then it represents
// a pop of the value k-n.
Timeline []uint
// Parent[v] is the parent of v in the DFS spanning tree.
// The parent of the root of the tree is itself.
Parent []uint
// Depth[v] is the depth of v in the DFS spanning tree.
Depth []uint
// SubtreeSize[v] is the size of the subtree of v in the DFS spanning tree,
// including v itself.
SubtreeSize []uint
}
type DominatorJoinGraph ¶
type DominatorJoinGraph struct {
DominatorTree
JoinGraph Graph
}
func (*DominatorJoinGraph) DominatorFrontier ¶
func (g *DominatorJoinGraph) DominatorFrontier(node uint) []uint
Computes the dominator frontier of the provided node in linear time.
Note if your purpose is to compute the dominator frontier of a set of multiple nodes, or the iterated dominator frontier, there are better methods then calling this method multiple times, resulting in a quadratic time. See the IteratedDominatorFrontier method for more information.
For more information, see https://doi.org/10.1145/199448.199464
func (*DominatorJoinGraph) IteratedDominatorFrontier ¶
func (g *DominatorJoinGraph) IteratedDominatorFrontier(nodes []uint) []uint
type DominatorTree ¶
type DominatorTree struct {
*Graph
Dfs
// ImmDom[v] is the immediate dominator of v, and by definition of the
// dominator tree, ImmDom[v] is the parent of v in the dominator tree.
//
// It is assumed that ImmDom[root] = root.
ImmDom []uint
}
func (*DominatorTree) IsDominatorOf ¶
func (t *DominatorTree) IsDominatorOf(dominator uint, dominated uint) bool
func (*DominatorTree) IsStrictDominatorOf ¶
func (t *DominatorTree) IsStrictDominatorOf(dominator uint, dominated uint) bool
type Graph ¶
type Graph struct {
Nodes []Node
}
func NewEmptyGraph ¶
func NewGraphFromRootedTree ¶
Converts a parent array that implicitly represents a rooted tree (by representing back edges only), into a full explicit graph representation, with explicit front edges.
Assumes that the root is identified by the only node v for which parent[v] = v.
func (*Graph) ControlFlowGraph ¶
func (g *Graph) ControlFlowGraph(entry uint) ControlFlowGraph
func (*Graph) Dfs ¶
Returns the 'Dfs' type that contains information about the graph that have been collected in a linear-time depth-first traversal of the graph from the provided node as the initial location.
func (*Graph) DominatorJoinGraph ¶
func (g *Graph) DominatorJoinGraph(entry uint) DominatorJoinGraph
func (*Graph) DominatorTree ¶
func (g *Graph) DominatorTree(entry uint) DominatorTree
Returns the 'DominatorTree' type that encapsulates the Dominator Tree data structure, and provides efficient queries of the dominators and immediate dominators of nodes.
Construction of the data structure is based on the Lengauer-Tarjan algorithm: https://doi.org/10.1145/357062.357071
func (*Graph) LivenessAnalysis ¶
type LinkEvalForest ¶
type LinkEvalForest struct {
// SemiDom[v] is the semidominator of node v in the forest.
// It is to be set by the user of the data structure.
// Initially, SemiDom[v] = v for all v.
SemiDom []uint
// Parent[v] is the direct parent of node v in the forest.
// If v is the root of the tree it is in, Parent[v] == v.
// The data structure is initialized with Parent[v] = v for all v.
Parent []uint
}
Nodes are assumed to be numbered [0, n), where n is the number of nodes.
func NewLinkEvalForest ¶
func NewLinkEvalForest(n uint) LinkEvalForest
func (*LinkEvalForest) Eval ¶
func (f *LinkEvalForest) Eval(v uint) uint
Eval(v) returns v if and only if it is the root in a tree of the forest. Otherwise, it returns a node u in the path from v to the root of the tree that contains v (not including the root itself), such that Semidominator(u) is minimal.
Since we are calculating the semidominators of vertices in reverse order, if evaluating a node that has yet to be processed and given a semidominator, the tree containing that node will be a singleton and thus it will be the root, and the node itself will be returned by definition.
If however, we evaluate a node that has already been processed, it must not be the root of the tree it is in, since right after processing a node we merge it with its parent. Then, the second case in the Eval definition applies, and we iterate over the ancestors of the node in the tree until reaching the root, returning the node with the minimal semidominator. On the way, we compress the path to the root of the tree, to speed up future evaluations.
For reference, see Henrik Knakkegaard Christensen's master's thesis, section 3.3, page 27: https://users-cs.au.dk/gerth/advising/thesis/henrik-knakkegaard-christensen.pdf
func (*LinkEvalForest) Link ¶
func (b *LinkEvalForest) Link(child uint, parent uint)
type Liveness ¶
type Liveness struct {
*Graph
// LiveIn[v] contains the set of variables that are live at the entry of
// the basic block represented by node v.
LiveIn []set.Set[uint]
// LiveOut[v] contains the set of variables that are live at the exit of
// the basic block represented by node v.
LiveOut []set.Set[uint]
}
Source Files