The convexity check is too expensive for simple rewrites

[aborgna-q]

SimpleRewrite are defined from a subgraph of the original HUGR and a replacement.
In general, correctness cannot be ensured when the subgraph is not convex (that is, some nodes exist between some of the subgraph outputs and some of the inputs).

Consider for example the following DAG, where we have selected two nodes (n0 and n1) as the rewrite target.

graph LR
    inp0[" "] --> n0
    inpm[" "] --> mid["middle"]
    n0 --> mid
    n0 --> n1
    mid --> outm[" "]
    mid --> n1
    n1 --> out1[" "]

    classDef highlight fill:#843334;
    classDef void fill:#0000,stroke:#0000;
    class n0,n1 highlight;
    class inpm,inp0,outm,out1 void;

Loading

and then replace it with a single node

graph LR
    inp0[" "] --> n
    n --> out1[" "]
    n --> mid
    mid --> n
    inpm[" "] --> mid["middle"]
    mid --> outm[" "]

    classDef highlight fill:#843334;
    classDef void fill:#0000,stroke:#0000;
    class n highlight;
    class inpm,inp0,outm,out1 void;

Loading

this ends up producing an invalid HUGR with a loop containing the middle node.

For this reason we require the rewrite subgraph to always be convex.

Complexity of convexity checking

In general, checking convexity for a subset of nodes $S \subseteq V$ in a DAG $(V, E)$ requires exploring the light-cones for both the boundary inputs and outputs of the set. If the cones intersect, then there are nodes in both the past and future of the subgraph.

portgraph::TopoConvexChecker optimises this process by first computing a topological ordering $T: V -> \mathbb{N}$ for the whole graph.
For a subset $S$, if there exists a node $v$ that certifies the non-convexity then $min_{u \in S} T(u) \le T(v) \le max_{u \in S} T(u)$.
On each is_convex call, the checker explores the light cones while filtering out any node with a $T$ order outside the range of the subset.

This optimisation helps in practice, but it doesn't improve worst case complexity of $O(n)$. In addition, the offline initialization of the checker already incurs a traversal of the full graph to compute the toposort.

Real life use

SiblingSubgraph provides _with_checker variants on its interface that let one reuse an already initialized convex checker on the same graph. This is used by badger to avoid the full traversals for each rewrite.

But for one-off operations like the lowering rewrites we sometimes cannot reuse the convex checker, and end up regenerating it for each operation. This gets really expensive, fast. See #1652.

Can we avoid the convexity work altogether? (CQCL/portgraph#161)

When the subgraph contains a single node, it is trivially convex.

In some multi-node cases, we don't actually need the subgraph to be convex. Specifically, we can always execute a rewrite if the replacement does not introduce any new order relation between the boundary ports. Formally:

Given a subgraph $S \subseteq V$ with boundary ports $B = {p_i}_i$, let $\prec$ be the partial order on $B$ induced by S.
Let $\tilde{S}$ be the rewrite replacement, with corresponding boundary $\tilde{B} = {\tilde{p_i}}_i$ and induced partial order $\tilde\prec$.

If $\forall_{i,j} (\tilde{p_i} \tilde{\prec} \tilde{p_j} \implies p_i \prec p_j)$ , then the rewrite is safe to apply even for non-convex subgraphs.

Note that this can be computed by solely looking at $S$ and $\tilde S$, and the cost is roughtly $O((|S| + |\tilde{S}|) * (max\ node\ multiplicity))$

One-off optimisation (CQCL/portgraph#160)

For the case where we initialize a TopoConvexChecker and use it before discarding it it would actually be faster to explore a lightcone directly. This has the same O(n) complexity, but in practice we may not need to explore the whole hugr as we do when preparing the toposort.

We could furthermore filter nodes by hierarchical region. When all the subgraph nodes share the same parent, we can reduce the traversal to only nodes inside the region.

Questions

• Does the property for rewritable convex subgraphs make sense? Can it be weakened? Should we implement it, and automatically avoid the TopoConvexChecker when possible?

• Should we try the "one-off rewrite" optimisation?

• Can we optimise the general case?