Is it feasible to convert "pipeline" dialect" to "FSM" directly?

hi, I am curiouse that there is no conversion from “pipeline” dialect to “FSM” , it is feasible ? or some body have done some investigation already ? I am planing to writte such a pass , any sugguestion is welcom .

The current conversion from the Pipeline dialect goes to Calyx, and @mortbopet has been working on a conversion from there to the FSM dialect. But to answer your original question, yes, it is definitely feasible to go directly to FSM and HW/Comb/Seq dialects from the Pipeline dialect. It’s been discussed before by myself, @mortbopet, and @jopperm.

Originally, we thought we could take advantage of Calyx’s higher level of abstraction to simplify the conversion, but in reality, the Pipeline representation is fairly low level, and we could cut the Calyx step out completely. I think this would be a useful angle to explore.

Regarding the implementation, I’m not sure if you have something in mind, but @jopperm and @mortbopet have previously suggested that the simplest FSM for a pipeline like this is basically just a shift register. That is, for a given initiation of the pipeline, we know which stage should be active at each cycle. So, we could come up with a bit pattern, shift it through a shift register, and use the shift register to enable each pipeline stage.

Just to be clear, this missing conversion would be with respect to the pipeline.while op, correct? (as opposed to the pipeline.pipeline op).

As @mikeurbach mentions, it should indeed be possible to go from pipeline.while to a HW/comb/Seq datapath with an FSM-based controller.

@mikeurbach the implementation that you propose sounds (to me) like a description of how a simple FSM controller could be constructed using HW/Comb/Seq primitives.
I’d hope that the FSM dialect (a graph of states and transitions) will be suitable for describing an equally efficient controller. Now, the question is then - is it?

Two examples of implementing a pipeline FSM controller in the fsm dailect would be. Assume that the controller controls a 4-stage pipeline with a single go input that either runs or stalls the pipeline.

Elaborated FSM

A shift-register based controller could in theory be described by the elaborated set of possible states which such a pipeline might have. In the case of a 4-stage pipeline that amounts to 2^4 possible states… a lot…!

fsm.machine @top(%go: i1) -> (i4) attributes {initialState = "S"} {
  %c0000 = hw.constant 0b0000 : i4 // pseudo
  %c1000 = hw.constant 0b1000 : i4 // pseudo
  // ...

  fsm.state @S_0_0_0_0 output  {
    fsm.output %c0000 : i4
  } transitions {
    fsm.transition @S_1_0_0_0 guard {
      fsm.return %go
    }
  }
  
  fsm.state @S_1_0_0_0 output  {
    fsm.output %c1000 : i4
  } transitions {
    fsm.transition @S_1_1_0_0 guard {
      fsm.return %go
    }
    fsm.transition @S_0_1_0_0
  }

  // ... repeat for all 2^4 states.
} 

Variable based

The above serves as a nice motivation for why the fsm.variable op was introduced. In this case, we use an fsm variable to compress the elaborated FSM described above. This is essentially the shift-register FSM that @mikeurbach described, but implemented using the fsm dialect to handle the wiring minutiae.

fsm.machine @top(%go: i1) -> (i4) attributes {initialState = "S"} {
  %stage_enable = fsm.variable "stage_enable" {initValue = 0 : i4} : i4
  fsm.state @S output  {
    fsm.output %stage_enable : i4
  } transitions {
    fsm.transition @S action {
      %0 = concat(stage_enable[3:1], %go) // pseudocode
      fsm.update %stage_enable, %next_stage_enable : i4
    }
  }
}

So long story short, it should be possible. As for now, the FSM dialect doesn’t really do anything, apart from serving as an intermediate point to lessen the burden of generating a hw.module-based FSM. I’d very much hope to see work on whether the abstraction lends itself to analysis and optimization.
As a closing comment, i’d also like to see work looking into whether the pipeline.pipeline op could be lowered to FSM or if it’s already too low level, and too much of the control semantics have already been lowered out in this representation. This seems significant, since pipeline.while should be able to be lowered to pipeline,pipeline and thus we’d only need a single lowering path to FSM+HW/Comb/Seq.

1 Like

Yes, thanks for showing this. That’s what I had in mind!

This is a good question.