circt
circt copied to clipboard
[FirRegLowering] Reimplement forward slice analysis with SCC
Implement an iterative SCC analysis to compute the forward slice analysis of FirRegOp.
Because I saw SCC fly by, this is a draft PR that implements group traits for FIRRTL connections: https://github.com/llvm/circt/pull/6491
I'm not convinced that this is fully working yet, as the SCCs I'm getting out don't look quite right. However, this may be a basis for leveraging LLVM infra for SCCs. There is some dummy code of how I started to use this here: https://github.com/llvm/circt/pull/6492
Yeah, probably we can just reuse ResultIterator :)
Thanks for the reference @seldridge, I did some initial experiments using the scc_iterator before implementing the iterative tarjan's and seemed like it might not help with the performance issue that we are trying to address. But I will do some more runs to confirm. It would be ideal to reuse the SCC infra.
hw.module @Foo(in %clock: !seq.clock, in %cond : i1, out o: i2){
%mux = comb.mux bin %cond, %r1, %r2 : i2
%r1 = seq.firreg %mux clock %clock : i2
%r2 = seq.firreg %mux clock %clock : i2
hw.output %r2: i2
}
This example should show why filter doesn't work. The constructed SCC depends on the order of root nodes (which should not be relevant in SCC construction):
- Start from %r1. SCC is
{{%r1, %mux}, {%r2}}because the edge between %mux and %r2 cannot be used due to filter. - Start from %r2. SCC is
{{%r2, %mux}, {%r1}}. - Start from %mux (probably not happen in your implementation). SCC is
{{%mux}, {%r1}, {%r2}}because %mux can reach to neither %r1 nor %r2.