Optimization Scope

[acl-cqc]

For controlling what interfaces an optimization must preserve (typically functions, but also perhaps the entrypoint if a DFG)

We may want ability to tell passes not to waste compute time on optimizing other parts, but this is less of an issue - few classical compilers bother very much! Instead the preferred way is to split your Hugr into several, optimize them separately/differently, and then link them back together.

Hence, propose to combine these two concepts into a single enum:

#[non_exhaustive]
enum OptimizationScope<N> {
   SpecificFuncs (Vec<N>), // heavily discouraged because serialization renumbers - maybe remove altogether and require setting visibility??
    // maybe SpecificPublicFunctions(Vec<String>), etc. etc.

   AllPublic (include_entrypoint: bool), // true has no effect if entrypoint==module-root

   All (include_entrypoint: bool), // true has no effect if entrypoint==module-root

   Aggressive, // if entrypoint is module root, then AllPublic(false); else just entrypoint

   Local, // use entrypoint, do not recurse (possibly error on module-entrypoint?)
}

Default == All(true) as this is pretty conservative. Indeed, perhaps too conservative: All means DeadFunctionRemoval can't remove unused private functions! (It makes no sense to allow removal of functions but not alteration; a pass could create a new function, change all calls to use that, and remove the old one!)

Add ComposablePass::set_scope (breaking change as new pass method)

Note SpecificFuncs requires them all to be top-level/module children, so cannot express arbitrary entrypoint

There is some method to_nodes<H: HugrView>(&OptimizationScope, &H) -> Vec<H::Node> (all elements of which are not guaranteed to be module children), but this might be hidden. (Or, this might want to return 2*Vec: places to examine/transform, and funcs whose semantics to preserve - the former must be a superset of the latter but usually plus reachable funcs - e.g. if we are preserving interface of public funcs, we might still butcher up the private ones according to how they are used.)

[aborgna-q]

• All means DeadFunctionRemoval can't remove unused private functions!

  Why is that?
  Saying that we want to optimize every function shouldn't prevent DCE to remove private ones?

• Aggressive doesn't really convey a scope, I'd say that's rather a name for a set of passes.
  I think that should be named Recursive (or RecursiveEntrypoint)

• All has no need for include_entrypoint, no? The entrypoint will always be included by the recursive run.

• Related to the last one, I think we should always preserve the entrypoint region's semantics, independently on if it's a private function, a nested region somewhere, or anything else.

• to_nodes would be expensive to compute all the time, especially since we need to recompute it after each pass application. Most passes don't really need to run it, since they can traverse recursively from the top-level nodes (targets in the next section). We could have an -> impl Iterator<Item = Node> that produces just those from a scope.

Variants

As you mention in the last paragraph, we need to clarify targets vs allowed scope.

• targets are regions we want to optimize
• scope are regions we allow optimizing
• preserve are functions we want to keep with the same definition. This should probably always include the entrypoint region.

Setting	Targets	Scope	Preserve
All	The whole hugr	The whole hugr	All public functions
AllPublic	All public fns + descendants, and optionally the entrypoint	The whole hugr?	All public fns
NamedFns(<fns_names>)	Named functions + descendants	Only named functions + private ones?	All public functions
Recursive	Entrypoint region and descendants	Entrypoint and descendants?	The rest of the hugr
Local	Flat entrypoint region	Flat entrypoint region	The rest of the hugr

Examples

• DeadCodeElimination with Local / Recursive scope doesn't modify anything.
• DeadCodeElimination with All/AllPublic/NamedFns removes unused private fns.
  • Do we allow removing unused public fns? Which scope should allow that? (Note that DCE is quite a specific case, most passes shouldn't need to address this)
• UntuplePass on Local modifies the entrypoint region only.
• UntuplePass on any other scope modifies the specified regions and traverses the hierarchy recursively.

[acl-cqc]

Good points. I like your terminology. However given there are so many goals/restrictions ("variants") we should probably try to reduce them: which of those can we instead handle via linking? I think targets and/or scope. (Presumably targets is always a subset of scope...I mean, not totally necessary, but if scope is smaller than targets, then the targets outside scope can only be optimized by means of optimizing in-scope callees.)

I think in my original outline I was taking scope and targets both to be the whole Hugr (no ability to differentiate the two) - this largely solves the tricky problem of RemoveDeadFuncs. Except Local restricts scope/targets (and probably prevents RemoveDeadFuncs from doing anything? At least for non-module-entrypoint Hugrs). The enum then primarily determines preserve.

All means DeadFunctionRemoval can't remove unused private functions!

Why is that?
Saying that we want to optimize every function shouldn't prevent DCE to remove private ones?

==> If you are preserveing the private functions then you can't remove them

Aggressive doesn't really convey a scope, I'd say that's rather a name for a set of passes.

Yes, fair! 👍

I think that should be named Recursive (or RecursiveEntrypoint)

Yes, or something - I think we need to be clear, for each variant, what it does for both a module-entrypoint Hugr, and a non-module-entrypoint Hugr. (One option could be, variant does not apply to that kind of hugr - in which case we can have an error; most likely we have to add separately to each ComposablePass's error variants, but that's generally ok)

All has no need for include_entrypoint, no? The entrypoint will always be included by the recursive run.

I was meaning, does it need to preserve the entrypoint semantics...but as you say:

Related to the last one, I think we should always preserve the entrypoint region's semantics, independently on if it's a private function, a nested region somewhere, or anything else.

Yeah, that seems reasonable; it's good to bear in mind that we can override the entrypoint temporarily.

[acl-cqc]

Another option - perhaps preserve == targets? I mean, preserve are things you want to keep as callable; it seems likely that you might want to optimize them! (targets being greater than preserve makes so sense; targets being less than preserve is plausible, but I'm not sure it seems important enough to care).

Then enum elements could allow some setting of both scope and targets.

However, scope is also about semantic preservation, right? I mean preserve is about preserving behaviour for all possible arguments (to a function/entrypoint), and scope is also (?) about avoiding optimizations that might affect different notions of behaviour, e.g. physical vs logical qubits?

[aborgna-q]

targets being greater than preserve makes so sense; targets being less than preserve is plausible

I think the main case for $\text{targets} \subset \text{preserve}$ are the local optimizations.
I may want to do some expensive quantum resynthesis in a region / its children without targeting nor modifying the rest of the hugr.

[acl-cqc]

Ok synthesizing, how about....

• EntrypointFlat and EntrypointSubtree (or EntrypointRecursive) if you must - these set scope = the entrypoint region or subtree, targets = preserve = the entrypoint computation
• Everything else sets scope = the whole Hugr, preserve = target = various options (All/AllPublic, always including the entrypoint as well). This allows optimization in the other bits, but this should be intended to optimize the preserve/target bit

I may want to do some expensive quantum resynthesis in a region / its children without targeting nor modifying the rest of the hugr.

This is handled by EntrypointXXX; if you want to iterate over multiple entrypoints that's fine; if you want to optimize those (multiple entries) but not other stuff then move just those bits into a new Hugr with Decls for the other stuff, optimize the whole of that, then link the (unoptimized) Defns back in.
(If you really want, you could optimize the whole Hugr with just the critical bits marked as preserve, then link the unoptimized Hugr back in overwriting the noncritical bits back to how they where; the critical bits could thus be optimized with knowledge of the other functions, but the other functions kept unchanged following linking)