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...)