CQCL/hugr

Add a `Const` deduplication pass

Opened this issue · 0 comments

A natural pass to run on a Hugr is to group Const nodes into equivalence classes, and to remove all-but-one of each equivalence class. This shrinks the Hugr, reducing the work of future passes. The existence of such a deduplication pass frees up other passes to freely create Const nodes as is convenient.

Note that CustomConst is not required to support equality, so we must be mindful that some Consts will always be in their own signleton equivalence class. Nevertheless, many will deduplicate very well: Bools, ints, unary sums.
I suggest:

  • adding to CustomConst:
  /// An optional hash of `Self`. 
  ///
  /// if `x.const_equals(y)` then it must be that `x.try_hash().unwrap() == y.try_hash().unwrap()`.
  /// if `x.try_hash().is_some()` then it must be that `x.const_equals(x)`. 
  fn try_hash(&self) -> Option<u64> { None }
  • Add a try_hash implementation for Value.
  • Add a pass to hugr-passes that:
    • walks the Hugr collecting all Const nodes into equivalence classes, using try_hash and <Value as PartialEq>.
    • Moves one member of each equivalence class to the top level, and rewrites each LoadConstant to use one of these chosen nodes.
      • One might instead choose not to go directly to the top level, instead to the "greatest command parent". I don't see a reason to prefer this.
    • Removes any unreferenced Consts.
    • (Optional) For any two LoadConstants A,B using the same Const, where one A dominates B (This includes there being no FuncDefn node in a "hierarchy path" between them") rewrite all users of B to use A.
      • Remove any unreferenced LoadConstants.