Add a `Const` deduplication pass
Opened this issue · 0 comments
doug-q commented
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 Const
s 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 forValue
. - Add a pass to
hugr-passes
that:- walks the
Hugr
collecting allConst
nodes into equivalence classes, usingtry_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
Const
s. - (Optional) For any two
LoadConstant
sA
,B
using the sameConst
, where oneA
dominatesB
(This includes there being noFuncDefn
node in a "hierarchy path" between them") rewrite all users ofB
to useA
.- Remove any unreferenced
LoadConstants
.
- Remove any unreferenced
- walks the