Dead-code-elimination requires a notion of "impure" ops, how should we model this?

[doug-q]

Dead code elimination is a well known concept in compilers. https://en.wikipedia.org/wiki/Dead-code_elimination

See #1807 for issues with our existing dead-code-elimination, which at time of writing lives in and around ConstFoldPass::find_needed_nodes .

By dead, we mean "it's outputs aren't used". This is similar but different to "unreachable" which means "no dynamic trace of the program executes that basic block". It's always safe to remove unreachable basic blocks.

Our dead code elimination must eliminate "dead" ops, for which we need a definition of "dead". Some examples of ops that are surely dead:

• an int.iadd whose outputs are not used
• a DFG whose outputs are not used, and where all transitive children are dead.
• A private (See Decide on which functions are "public" #1752) FuncDefn that has no out-neighbours.

Some ops that are surely not dead:

• an int.add whose outputs are wired to the Output node of a public FuncDefn
• A QFree whose input is wired to the Input node of a public FuncDefn
• a DFG whose outputs are wired to the Output node of a public FuncDefn
  • an int.iadd whose outputs are wired to the Output node of that DFG

Are the following ops dead?

• A panic node with no inputs or outputs (other than the error) in a live DFG
• A panic node in a DFG with no inputs or outputs?
• A "2-node QAlloc -> QFree subgraph" in a live DFG?

Does the addition of order edges between the input and output nodes and the panic nodes affect the above?

Focusing now on the panic case, I assume that we want all panics in a live DFG to be live, irrespective of their connections.

Options:

• Put a "never-dce" flag on OpDef. (maybe in misc?).

  • Extension ops with this flag are never dead.
  • Parent ops with transitive children with this flag are never dead
  • Calls to unknown functions(CallIndirect, FuncDecl) are never dead
  • calls to known dead functions are dead
  • If we come up with a more sophisticated model of side effects, ops can opt into that by clearing this flag.

• Ops connected (perhaps through order edges) to the output node of their parent dataflow block are never dead unless their parent is.

  • Should order edges from the input node also keep an op alive?
  • Constructors of HUGRs must ensure that a parent node is made alive if it has a child they need alive. For example, they should ensure that a DFG containing a panic has:
    • An internal order edge keeping the panic alive
    • An order edge keeping the DFG alive
    • And so on for all transitive parents of the DFG.

• Create a linear "state token" and thread it through all impure ops

  • print, panic, etc get an extra input and output
  • Constructors of HUGRs must deal with threading this through
  • Rewriting from pure -> impure becomes impractical

My view is we should move forward with a "never-dce" flag.

[acl-cqc]

Nice write-up @doug-q :).

We might wish to note there are several distinct reasons why nodes might be "never-dce" - it's probably OK to combine these but there might be reasons to distinguish

• stateful side-effects, e.g. print, or non-q free
• panic/abort (aka a "control effect" IIUC)
• infinite, or potentially-infinite (unbounded) TailLoop, or call to potentially-infinite-recursive function
  Both the last two would of course prevent any consumers of their output values from being evaluated, so this is about non-consumers, specifically the idea that nodes using outputs of a DFG do not evaluate if the DFG doesn't finish evaluating all of its children (even if those output values of the DFG are ready). IOW, that the DFG is a scheduling barrier. (If it were not, you could delay that no-output panic until after the rest of the program, and I don't think we want that.)

While the "linear state token" allows rewriting in the opposite impure->pure direction, even there one wants to do a lot more tidying up.

Side comment, but I'd like to unify treatment of "never-dce" ops/nodes with unbounded TailLoops somehow.

[zrho]

Isn't a major design point of HUGR that it uses "value semantics", i.e. data dependencies are all there is? The "never-dce" and order edge approaches feel like hacks in that light while the "linear state token" expresses precisely what we want, both conceptually and pragmatically. It makes control dependencies into data dependencies where we want it, and so requires no additional attention to corner cases regarding ordering or effects. It marks effectfulness directly in the type of an operation. It is immediately clear how it interacts with control flow. This is also a solution that some people in PL semantics research have arrived at (see e.g. Universal Properties of Impure Programming Languages or Promonads and String Diagrams for Effectful Categories).

A panic node with no inputs or outputs (other than the error) in a live DFG
A panic node in a DFG with no inputs or outputs?
A "2-node QAlloc -> QFree subgraph" in a live DFG?

These should definitely be dead.

Rewriting from pure -> impure becomes impractical

Can you explain what you mean here?

[acl-cqc]

I am generally with Lukas here - or rather, I agree this is definitely the right thing to do in principle. The devil is in that

Rewriting from pure -> impure becomes impractical

And similarly impure -> pure. So the pure->impure case is where I perform an optimization that takes code that can be DCE'd, and replaces it with code that's (presumably) more efficient, but has side effects - for example, memory allocation and/or deallocation. We now need to thread the allocation-state-token into code that didn't need it before, perhaps many levels deep inside "pure" conditionals, loops, cfgs, etc. This is feasible but quite awkward/annoying and, in particular, might destroy the notion of a rewrite being "local" (if it requires changing the signature of everything above it in the hierarchy).

The impure -> pure case arises when, say, we remove an entire alloc->....->dealloc chain - suddenly we no longer need the allocation-state-token to be passed in. This is perhaps less serious - we can leave the token being passed through unused without breaking anything, just that we'll fail to get full benefit of the optimisation until we remove it. For example, suppose the alloc->dealloc, or some other state/token-using construct, is within one Case of a Conditional which we discover always branches another way - there is no longer any need to pass the state/token through the other Cases, nor the Conditional itself, or its ancestors. Although non-essential, removing this could enable greater flexibility in parallelisation and/or scheduling of other nodes around the now-pure one (e.g. others that still use the token).

Note that state/order edges are easier to add/remove (no signature updates), but still require traversing an arbitrary #levels up the hierarchy, and we'd need well-defined metadata explaining which state/order edges were there for that purpose and could safely be removed vs. still being needed for other reasons.

[acl-cqc]

Conversely - supposing we did wire a state-token through, and had library methods to make that easy, or something.

We still need to avoid removing even unused TailLoops/CFGs if they might not terminate, as doing so would change the termination behaviour of the program. So, would we want to wire a "might-terminate" token through those? (And then remove it if we prove termination? I foresee bugs where we forget to wire the might-terminate-token in, and then later analyses assume that absence of said token means the loop is known to terminate...)

[acl-cqc]

So at present we have two mechanisms for forcing evaluation of things.

1. StateOrder edges, which are good for forcing, erm, ordering
2. The spec that evaluating a DFG causes evaluation of everything inside it.

The latter means that, given e.g. DFG_1 depends on DFG_2 where DFG_2 contains an infinite loop but doesn't use the result of that loop, we cannot execute DFG_1 (because DFG_2 never terminates).

Thus, the "InlineDFG" rewrite is looking dangerous....we should probably insert StateOrder edges from all nodes not connected to the inlined DFG's Output node, to all successors of the DFG, and from all predecessors of the DFG to all nodes not connected from the inlined DFG's Input.

Is there a better way?

Passing tokens is one way, although I think this can work, I fear it may be quite painful if we use that to handle all the cases. Might we have a better mechanism? I wonder if some notion of "effect system" might address both this and #1894.

[acl-cqc]

Could we remove the idea that executing a DFG requires executing everything in it, and require order edges to express this constraint? This is a bit like reintroducing the "causal cone" although we do not require every op be in the cone - only that if ops are not in the cone, they may be removed by DCE ?

• This is not really consistent with the idea that we can't remove a potentially-non-terminating thing because then we change the semantics of the program. I.e. we would be changing the semantics whether or not the diverging op was in the causal cone or not
• And things might be in the causal cone by value edges (because we are using their results) - e.g. we rewrite (complex loop that might or not eventually produce a value) * 0 to 0.
• So we'd have to keep the loop in the causal cone via "order edges" as well (because it might not terminate - we could skip the extra order edges only if we knew it always terminated?)

And/or, can we replace order edges by linear types?

• We'd need ways to introduce new linear types - none of these have data, but we can't use unit (i.e. Sum( () ) because they are not interchangeable). Perhaps just a CustomType for each?
• Then we can allow copy/merge operations, or not.
• ....and we feed a token in at the top of the outer Hugr and it comes out the bottom? There's no data in it so I guess this is straightforward - IOW lowering just has to take the edge into account when topsorting, then ignore it.
• Might we want ops that produce/consume (discard) tokens out of thin air? This seems both useful and mildly dangerous - perhaps a "run_with_token" op that does a direct call (to some code that has token input+output) and mirrors the non-token inputs/outputs? (i.e. feat: Allow extension operations to have child graphs #1546)

[zrho]

Some thoughts on the rewriting when state is encoded via a linear type that is passed through:

So the pure->impure case is where I perform an optimization that takes code that can be DCE'd, and replaces it with code that's (presumably) more efficient, but has side effects - for example, memory allocation and/or deallocation.

When you start with a pure program and replace it with an impure one for efficiency, you'd probably want the effects to be local. For instance for memory allocation and mutation, you could create a local heap, pass around that heap as a linear value, and then deallocate the heap in the end. Overall the program's interface is not changed. This would be similar to using a State or ST monad in Haskell, where at the boundary you use runState or runST so that the overall program still has a pure interface.

Rewriting a pure program into an impure one that has effects which do not commute with the outside world in this way would have chaotic consequences anyway. For instance, take a program with pure ops A and B that do not have data dependencies between them and rewrite both A and B into stateful versions A' and B'. If the order of A' and B' is derived from the order of A and B before the rewrite and the effects of A' and B' interfere, then the semantics of the rewritten program depends on the order of the pure operations A and B. One might then be tempted to insert order edges between A and B but that would lead to an extremely brittle system in which you'd have to schedule pure ops depending on your knowledge on how they become rewritten later.

The impure -> pure case arises when, say, we remove an entire alloc->....->dealloc chain - suddenly we no longer need the allocation-state-token to be passed in. This is perhaps less serious - we can leave the token being passed through unused without breaking anything, just that we'll fail to get full benefit of the optimisation until we remove it. For example, suppose the alloc->dealloc, or some other state/token-using construct, is within one Case of a Conditional which we discover always branches another way - there is no longer any need to pass the state/token through the other Cases, nor the Conditional itself, or its ancestors. Although non-essential, removing this could enable greater flexibility in parallelisation and/or scheduling of other nodes around the now-pure one (e.g. others that still use the token).

This case touches on what I meant with linear effect types not needing anything special: You can end up in the same situation with conditionals or loops where any kind of data is passed into the conditional/loop needlessly. An optimisation pass that detects this and makes the data bypass the cond/loop would then give you a "purification" optimisation for free.

[acl-cqc]

Yes, it is a bit like runState and so on.

• Might we need to get hold of the global heap, in order to have somewhere to allocate a "local heap"? If the "heap" is only there to support reference semantics, then it makes sense for the local heap to live "on the stack" from the point of view of the surrounding context, i.e. the global heap does not need to be passed in. If the "heap" is there because we have more memory available on the heap and less on the stack, then not so good. Our pure-functional "DAG" view suggests that stack size is not a concern so we are probably OK.
• I think it is plausible that we could rewrite A and B each into locally-stateful sequences of ops, but such that the two sequences must not be interleaved - you can still do either sequence before the other, but not overlapping. (Maybe each of them uses a common "scratch" area, that's too large to allocate both at once - or, say, two mergesorts)

[acl-cqc]

I'm wondering about some kind of effect system for "impure" ops but I'm not clear whether this is the same or separate from just having value edges to restrict ordering.

We can have value edges that are "splittable", enabling parallelism, something like:

• Suppose a custom carrier type Linear<T> which is linear regardless of T. Instances are zero-sized (and don't actually contain any T's).
• Now suppose we have two custom types A<T> and B<T>, with no way of actually constructing instances.
• split<T>(input: Linear<T>) -> (out1: Linear<A<T>>, out2: Linear<B<T>>) and merge<T>(in1: Linear<A<T>>, in2: Linear<B<T>>) then allow fork/join parallelism, with the type system ensuring proper nesting of split/merge. Everything spawned must finish and be brought back together at the end.

However, this is not very flexible - e.g. we cannot have the DAG with edges In -> B, In -> C, C -> D, C -> E, B -> F, D -> F, E -> Out, F -> Out because In splits to B and C and C splits to D and E but F tries to merge B and D. ISTR there are type systems which do track this kind of thing....

There is also the question of whether we can really know in advance all the reasons why a particular op might have an ordering requirement (so we can put the appropriate linear input/output ports on it). At the least, I suspect these reasons will change at different stages of compilation (as we start to track more things), requiring "lowering" ops to similar-but-different ops with more/different ports.

[acl-cqc]

Current thinking at https://github.com/quantinuum-dev/hugrverse/issues/116