circt icon indicating copy to clipboard operation
circt copied to clipboard

[FirRegLowering] Reimplement forward slice analysis with SCC

Open prithayan opened this issue 1 year ago • 4 comments

Implement an iterative SCC analysis to compute the forward slice analysis of FirRegOp.

prithayan avatar Dec 05 '23 02:12 prithayan

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

seldridge avatar Dec 05 '23 04:12 seldridge

Yeah, probably we can just reuse ResultIterator :)

uenoku avatar Dec 05 '23 05:12 uenoku

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.

prithayan avatar Dec 05 '23 15:12 prithayan

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

  1. Start from %r1. SCC is {{%r1, %mux}, {%r2}} because the edge between %mux and %r2 cannot be used due to filter.
  2. Start from %r2. SCC is {{%r2, %mux}, {%r1}}.
  3. Start from %mux (probably not happen in your implementation). SCC is {{%mux}, {%r1}, {%r2}} because %mux can reach to neither %r1 nor %r2.

uenoku avatar Dec 18 '23 05:12 uenoku