[Pipeline] Add retimeable pipeline operation

[mortbopet]

The pipeline.rtp operation represents a retimeable pipeline. The pipeline contains a single block representing a graph region. Pipeline stages are represented by pipeline.rt.register operations. Semantics of values crossing register boundaries are defined by lowering passes. The pipeline representation is centered around providing latency insensitive values (valid signals between stages). Such signals can either be removed (in the feedforward, statically scheduled case), used to control stalling (feedback, statically scheduled case) or in conjunction with handshake signals for dynamically scheduled pipelines.

Alongside this, some old, unused code (StandardToStaticLogic) is pruned to remove a maintenance burden associated with this change.

A typical flow would go like this:

An untimed datapath is defined:

pipeline.rtp(%in0 : i32, %in1 : i32,  %go : i1) -> (i32) {
    ^bb0:(%arg0 : i32, %arg1: i32, %go : i1):
    %add0 = comb.add %arg0, %arg1 : i32
    %add1 = comb.add %add0, %arg0 : i32
    %add2 = comb.add %add1, %arg1 : i32
    pipeline.rtp.return %add2 valid %go : i32
}

The datapath is scheduled (future pass). At this point, stage separating registers can be inserted at arbitrary points in the datapath.

pipeline.rtp(%in0 : i32, %in1 : i32, %go : i1) -> (i32) {
    ^bb0:(%arg0 : i32, %arg1: i32, %go : i1):
    %add0 = comb.add %arg0, %arg1 : i32

    %s0_valid = pipeline.stage when %go
    %add1 = comb.add %add0, %arg0 : i32

    %s1_valid = pipeline.stage when %s0_valid
    %add2 = comb.add %add1, %arg1 : i32

    pipeline.rtp.return %add2 valid %s1_valid : i32
}

Stage-crossing dependencies are made explicit through registers (future pass):

pipeline.rtp(%in0 : i32, %in1 : i32,  %go : i1) -> (i32) {
    ^bb0:(%arg0 : i32, %arg1: i32,  %go : i1):
    %add0 = comb.add %arg0, %arg1 : i32

    %s0_valid, %add0_r = pipeline.stage when %go regs (%add0: i32)
    %add1 = comb.add %add0_r, %arg0 : i32

    %s1_valid, %add1_r = pipeline.stage when %s0_valid regs (%add1: i32)
    %add2 = comb.add %add1_r, %arg1 : i32

    pipeline.rtp.return %add2 valid %s1_valid : i32
}

This representation can then be lowered to statically or dynamically scheduled pipelines.

[teqdruid]

The rename is all mixed in so the diff is impossible to read. will review once the rename is merged.

One comment: I hate the name "retimeable" -- it's a misnomer. What are you "timing" again? Additionally, it's really just a blob of logic which can optionally be pipelined OR run combinationally. I would prefer a much more generic name -- like 'dataflow', 'datapath', or something like that -- which implies what it contains and means rather than the intent of the transformation.

[mortbopet]

"retimeable" -- it's a misnomer. What are you "timing" again?

Naming is hard. Retimeable seemed like a good fit since the pipeline.stage operations can be freely added, removed and moved around within the body of the pipeline. Obviously it aliases with circuit retiming. I would be OK with pipeline.datapath - @mikeurbach thoughts?

Additionally, it's really just a blob of logic which can optionally be pipelined OR run combinationally

I don't think this is the sole intent of this op (though it might be, if we find that restriction to be the right thing to do). In the slides which @mikeurbach will present, it shows how this representation is also used to describe dataflows with delayed values across to-be-decided stages, backedges etc. - as such, a higher level of abstraction than just feed-forward combinational logic (which will be the immediate use-case that PyCDE will target).

[mortbopet]

This has now been rebased on top of the dialect name change.

[jopperm]

%g1 should be %s0_valid, right?

[jopperm]

Intriguing design! One question though: I assume the "middle" IR (w/ stages, w/o regs) is intended to conveniently transform the pipeline by moving around ops between stages. Given that the pipeline's body is a graph region, isn't it problematic then that the association of ops to stages is encoded by the relative location inside the block?

[mortbopet]

I assume the "middle" IR (w/ stages, w/o regs) is intended to conveniently transform the pipeline by moving around ops between stages

Correct!

Given that the pipeline's body is a graph region, isn't it problematic then that the association of ops to stages is encoded by the relative location inside the block?

It would be if a region being a graph region would imply a non-deterministic ordering between the order of operations in printed IR and in-memory. While this property is not formalized, I think it is a valid design point (and safe enough - I don't assume the underlying data structures will change any time soon).

The representation seems well suited for a pipelining representation - in a sense, it's a GraphRegion which implicitly states something about the topology of the graph through the reliance on operation ordering.

[mikeurbach]

the slides which @mikeurbach will present

For the record: https://docs.google.com/presentation/d/1PXgyVRmOMqf2PkshGgodLfwFiJAqh00E_yga2IAEvAM/edit#slide=id.gf491adc922_0_10. Still looking for an ODM slot to dicsuss, but some of what Morten proposes here is in slides 6-8.

in a sense, it's a GraphRegion which implicitly states something about the topology of the graph through the reliance on operation ordering.

That sounds reasonable to me, it's been done before: https://circt.llvm.org/docs/Dialects/SV/#svordered-circtsvorderedoutputop

[mortbopet]

@mikeurbach @teqdruid any further thoughts on this? Eager to get it into tree so i can post some of the related passes.

[mikeurbach]

Sorry I haven't had time to give this a proper review, but will try to get on that early this week.

[jopperm]

"retimeable" -- it's a misnomer. What are you "timing" again?

Naming is hard. Retimeable seemed like a good fit since the pipeline.stage operations can be freely added, removed and moved around within the body of the pipeline.

Actually, the "retimable" moniker made sense to me, for the reasons Morten listed 😉 Anyways, datapath would also SGTM. Or could this just be the PipelineOp in the pipeline dialect (like func.FuncOp)?

[mortbopet]

Actually, the "retimable" moniker made sense to me, for the reasons Morten listed 😉 Anyways, datapath would also SGTM. Or could this just be the PipelineOp in the pipeline dialect (like func.FuncOp)?

I have no issues with this - it seems like this op can represent most (all) semantics of a pipeline while, and I'd expect PipelineWhileOp to be able to lower to it. So this seems natural - will change.

[teqdruid]

Actually, the "retimable" moniker made sense to me, for the reasons Morten listed 😉 Anyways, datapath would also SGTM. Or could this just be the PipelineOp in the pipeline dialect (like func.FuncOp)?

I have no issues with this - it seems like this op can represent most (all) semantics of a pipeline while, and I'd expect PipelineWhileOp to be able to lower to it. So this seems natural - will change.

No objections here!

[mortbopet]

You're missing the error tests

Woops - added!

Can you break out and directly commit the PipelineWhile rename?

5fc5b1d3726edfee614482727f6044273dd1a6b7