Should we track functions with side-effects?

[mark-koch]

We need to ensure the ordering of side-effectful functions like result, panic, rng_seed, rng_next, etc.

Since there are no dataflow dependencies between those functions, we have to emit extra order-edges between them within a basic block. This requires tracking of these effects by the compiler and is not trivial:

• A function calling another side-effectful function becomes side-effectful itself
• A call of a higher-order function could also be side-effectful, so we need to track this in the function type, not only the function definition. Or be conservative and assume that any indirect call can have any side-effects.
• There are different kinds of side effects: E.g. it's not required to specify the order between result and rng_next since their side-effects don't interfer

[cqc-alec]

See also https://github.com/CQCL/tket2/issues/748 . Having a linear "state" type passed through these calls seems like a good solution. (We would need several such types, one per type of state).

[mark-koch]

But should we expose this to the user? Having to pass the state around seems very cumbersome for things like result or panic

[cqc-alec]

Agree it would be nice to avoid exposing to the user if we can.

[mark-koch]

Some thoughts on how to do this:

• Add an extendable type of SideEffect that captures different kinds of side effects (e.g. PRNG, IO, ...)
• Each builtin function specifies its set of side effects
• During type checking, construct a call-graph
• Run a fixed point iteration over the call graph to infer the side effects of user-defined functions. Assume that indirect calls have all possible side effects.
• During Hugr generation, insert order edges in each basic block to ensure odering of conflicting side-effects
• We also need to ensure ordering of basic blocks when unrolling control-flow. To do this, we need to:
  • Infer the side-effects of each basic block
  • For each BB, compute the set of BBs that can reach it and that are reachable from it
  • If any of those interfer with the side-effects of the current BB, we need to somehow mark that they may not be reordered during unrolling
  • How would this look like in Hugr? Maybe inter-graph and dom order edges?

[aborgna-q]

MLIR has something similar with their "categorization" of side-effect types, but they use numeric "stages" to order execution inside a single basic block. In our case using order edges should work correctly.

Mind that we may want separate shared vs unique side-effect producers. We don't want to enforce order between quantum gates with no data-dependency, but we want those to always come before some other operation that depends on the global quantum state. The order edges can be added only for unique operations, connecting them to the subset of shared side-effect operations with no data dependencies between them.

[cqc-alec]

Interesting note from that MLIR page:

This rationale only applies to operations used in CFG regions. Side effect modeling in graph regions is TBD.