Pass Creation
This is a practitioner’s guide to using the Execution Framework. Before continuing, it is recommended you first review the Execution Framework Overview along with basic topics such as Graphs Concepts, Pass Concepts, and Execution Concepts.
There are two parts to adding a new pass to the pass pipeline. First, we need to define the new pass and then we need to register it.
There are multiple types of passes supported in EF. A full list can be found at PassType. To create a pass, we start
by implementing the relevant pass type’s interface. In practice, this will be either IPopulatePass or
IPartitionPass. In rare cases, a pass may inherit from IGlobalPass, but such a pass is discouraged for performance
reasons. Implementing population and partition passes is covered below.
Once a pass is implemented, it must be registered with one of the following macros:
OMNI_GRAPH_EXEC_REGISTER_POPULATE_PASS(), OMNI_GRAPH_EXEC_REGISTER_PARTITION_PASS(),
OMNI_GRAPH_EXEC_REGISTER_GLOBAL_PASS().
// Register MyPopulatePass against a symbol (node or node graph def) name
OMNI_GRAPH_EXEC_REGISTER_POPULATE_PASS(MyPopulatePass, "symbol_name");
// Register MyPartitionPass with a given priority
OMNI_GRAPH_EXEC_REGISTER_PARTITION_PASS(MyPartitionPass, 1);
// Register MyGlobalPass
OMNI_GRAPH_EXEC_REGISTER_GLOBAL_PASS(MyGlobalPass);
Implementing a Populate Pass
The example below implements a new populate pass that will instantiate a new MyInstancedDef definition and attach it
to any node or definition that matches the name given during registration.
class TestPopulateInstances : public Implements<IPopulatePass>
{
public:
TestPopulateInstances(IGraphBuilder*) noexcept
{
}
void run_abi(IGraphBuilder* builder, INode* node) noexcept override
{
omni::core::ObjectPtr<TestNodeGraphDef> nodeGraphDef{ TestNodeGraphDef::create(
builder, "MyInstancedDef") };
builder->setNodeGraphDef(node, nodeGraphDef);
}
};
Here, we register the pass, telling EF that this pass should be run on nodes named “my.special.node”.
OMNI_GRAPH_EXEC_REGISTER_POPULATE_PASS(TestPopulateInstances, "my.special.node");
We can also register the pass to run on nodes with a definition named “my.def.special” already attached to the node.
TestPopulateInstances pass to run on every node with “my.def.special” definition attached OMNI_GRAPH_EXEC_REGISTER_POPULATE_PASS(TestPopulateInstances, "my.def.special");
Above, we see that the name given during registration can match either the node name or definition name. See Pass Concepts to better understand EF’s algorithm for running population passes.
Implementing a Partition Pass
In this example, we will be partitioning the following graph using either manual or automatic partition generation
// ┌───────────────────┐
// │┌─────── B ───────┐│
// ││┌────┐ ┌────┐││
// │││ Ax ├─┬──►│ Bx │││
// ││└────┘ │ └────┘││
// ││ │ ┌────┐││
// ││ └──►│ Cx │││
// ││ └────┘││ ┌────┐
// ┌──────►│└─────────────────┘│ ┌─►│ I ├─┐
// │ └───────────────────┘ │ └────┘ │
// ┌────┐ │ ┌────┐ ┌────┐ ┌────┐ ┌────┐ │ ▼ ┌────┐
// │ A ├──┬─┴──────►│ Cx ├─┬──►│ Dx │────┬──►│ A2 ├───►│ H ├─┬┴─────────┴─►│ J │
// └────┘ │ └─┬──┘ │ └────┘ │ └────┘ └────┘ │ └────┘
// │ │ │ ┌────┐ │ │ ┌────┐
// │ │ └──►│ Ex │ │ └────────────►│ K │
// │ │ └────┘ │ └────┘
// │ └──────────────────┘
// │ ┌────┐ ┌────┐
// └─────►│ Fy ├────►│ Gy │
// └────┘ └────┘
//
// Nodes with matching definition (B/Ax, Cx, Fy, H), (B/Bx, Dx, Gy, J), (B/Cx, Ex, K)
//
The task for our first partition pass will be to recognize two clusters of nodes (B/Ax, B/Bx, B/Cx) and (Cx, Dx,
Ex), but not recognize (H, J, K) since node I causes the cluster to form a cycle after replacing. The following
implementation will do this manually from the run_abi() method.
class TestPartitionPassX : public Implements<IPartitionPass>
{
public:
TestPartitionPassX(IGraphBuilder*) noexcept
{
}
bool initialize_abi(ITopology* topology) noexcept override
{
return true;
}
void run_abi(INode* node) noexcept override
{
if (!isMatch(node, TestDefType::eType1))
return;
INode* nodeType2{ nullptr };
INode* nodeType3{ nullptr };
for (auto* child : node->getChildren())
{
if (isMatch(child, TestDefType::eType2))
nodeType2 = child;
else if (isMatch(child, TestDefType::eType3))
nodeType3 = child;
else if (!isMatch(child, TestDefType::eType4))
return;
}
if (nodeType2 && nodeType3)
{
std::array<INode*, 3> partition{ node, nodeType2, nodeType3 };
m_manualPartitions.emplace_back(std::move(partition));
}
}
void commit_abi(IGraphBuilder* builder) noexcept override
{
for (const auto& partition : m_manualPartitions)
{
// Verify partition pattern (trivial check in this case)
if (partition.size() != 3)
continue; // LCOV_EXCL_LINE
// Create override definition. Note that we exclude the definition from code coverage
// because the graph is never executed in this unit test.
NodeDefPtr nodeDef{ NodeDefLambda::create(
"PatternX", [](ExecutionTask& info) -> Status { return Status::eSuccess; }, // LCOV_EXCL_LINE
SchedulingInfo::eSerial) };
// Commit the change
builder->replacePartition(NodePartition(partition.data(), partition.size()), nodeDef.get());
}
}
private:
std::vector<std::array<INode*, 3>> m_manualPartitions;
};
Now let’s implement the same partitioning strategy but leverage the quickPartitioning() utility to forming clusters.
class TestPartitionPassX : public Implements<IPartitionPass>
{
public:
TestPartitionPassX(IGraphBuilder*) noexcept
{
}
bool initialize_abi(ITopology* topology) noexcept override
{
m_selectedNodes.reserve(topology->getMaxNodeIndex());
return true;
}
void run_abi(INode* node) noexcept override
{
if (isMatch(node, TestDefType::eType1) || isMatch(node, TestDefType::eType2) ||
isMatch(node, TestDefType::eType3))
{
m_selectedNodes.push_back(node);
}
}
void commit_abi(IGraphBuilder* builder) noexcept override
{
quickPartitioning(
builder->getTopology(), Span<INode*>(m_selectedNodes.data(), m_selectedNodes.size()),
[builder](INode** begin, uint64_t size)
{
// For the test, we will only allow partitions of size 3
if (size != 3)
return;
// Create override definition. Note that we exclude the definition from code coverage
// because the graph is never executed in this unit test.
NodeDefPtr nodeDef{ NodeDefLambda::create(
"PatternX", [](ExecutionTask& info) -> Status { return Status::eSuccess; }, // LCOV_EXCL_LINE
SchedulingInfo::eSerial) };
// Mutate the graph
builder->replacePartition(NodePartition(begin, size), nodeDef.get());
});
}
private:
std::vector<INode*> m_selectedNodes;
};
Finally, we have to remember to register our new pass.
OMNI_GRAPH_EXEC_REGISTER_PARTITION_PASS(TestPartitionPassX, 1);
Implementing a Global Pass
Users are discouraged from authoring global passes as they can severely slow down graph construction and/or create ordering issues if a specific execution order is required. For all these reasons, users should try implementing new functionality with the pass types above rather than global passes.
The following is a complete implementation of a global pass that EF useds to detect cycles in the graph.
class PassStronglyConnectedComponents : public Implements<IGlobalPass>
{
public:
static omni::core::ObjectPtr<PassStronglyConnectedComponents> create(
omni::core::ObjectParam<exec::unstable::IGraphBuilder> builder)
{
return omni::core::steal(new PassStronglyConnectedComponents(builder.get()));
}
protected:
PassStronglyConnectedComponents(IGraphBuilder*)
{
}
void run_abi(IGraphBuilder* builder) noexcept override
{
_detectCycles(builder, builder->getTopology());
}
private:
void _detectCycles(IGraphBuilder* builder, ITopology* topology)
{
struct SCC_NodeData
{
size_t index{ 0 };
size_t lowLink{ 0 };
uint32_t cycleParentCount{ 0 };
bool onStack{ false };
};
size_t globalIndex = 0;
std::stack<INode*> globalStack;
traverseDepthFirst<VisitAll, SCC_NodeData>(
topology->getRoot(),
[this, builder, &globalIndex, &globalStack](auto info, INode* prev, INode* curr)
{
auto pushStack = [&globalStack](INode* node, SCC_NodeData& data)
{
data.onStack = true;
globalStack.push(node);
};
auto popStack = [builder, &info, &globalStack]()
{
auto* top = globalStack.top();
globalStack.pop();
auto& userData = info.userData(top);
userData.onStack = false;
auto node = exec::unstable::cast<exec::unstable::IGraphBuilderNode>(top);
node->setCycleParentCount(userData.cycleParentCount);
return top;
};
auto& userData = info.userData(curr);
auto& userDataPrev = info.userData(prev);
if (info.isFirstVisit())
{
userData.index = userData.lowLink = globalIndex++;
pushStack(curr, userData);
info.continueVisit(curr);
userDataPrev.lowLink = std::min(userDataPrev.lowLink, userData.lowLink);
if (userData.lowLink == userData.index)
{
auto* top = popStack();
if (top != curr)
{
while (top != curr)
{
top = popStack();
}
}
}
auto nodeGraph = curr->getNodeGraphDef();
if (nodeGraph)
{
this->_detectCycles(builder, nodeGraph->getTopology());
}
}
else if (userData.onStack)
{
userDataPrev.lowLink = std::min(userDataPrev.lowLink, userData.index);
userData.cycleParentCount++;
}
});
}
};
Next Steps
Pass creation is often the first step to adding new functionality to EF. The next logical steps often involve adding custom definitions, graph traversals, and executors. See Definition Creation, Graph Traversal Guide, and Executor Creation for details.