[Libre-soc-dev] adding PartitionedSignal support to nmigen's If/Switch/Case

[Luke Kenneth Casson Leighton]

---
crowd-funded eco-conscious hardware: https://www.crowdsupply.com/eoma68

On Tue, Sep 21, 2021 at 3:27 AM Jacob Lifshay <programmerjake at gmail.com> wrote:
>
> On Mon, Sep 20, 2021, 18:50 Luke Kenneth Casson Leighton <lkcl at lkcl.net>
> wrote:
>
> > ---
> > crowd-funded eco-conscious hardware: https://www.crowdsupply.com/eoma68
> >
> > On Tue, Sep 21, 2021 at 1:36 AM Jacob Lifshay <programmerjake at gmail.com>
> > wrote:
> > >
> > > from what I can see, nmigen threads the If and Switch/Case signals all
> > the
> > > way through the IR
>
>
> > yes.  by which time they are just Signals.
>
>
> actually, by adding a part and
> > mux function to class Value, then converting nmigen.Part and nmigen.Mux
> > defined as "def Mux(a, b): return a.mux(b)" EXACTLY as is done in
> > the python operator module, not even the nmigen IR sees different
> > types because it is the object.part() and object.mux()'s responsibility
> > to convert down to standard nmigen Signals.
> >
>
> If/Switch/Case are fundamentally different than Mux/Part/+/*/etc. and can't
> be handled in the same way -- they are control-flow-based, whereas
> Mux/Part/etc. are all only data-flow based.

If/Switch/Case *use* Mux/Part/Cat.  unfortunately it's been several months
since i investigated, so am going to have to look again and rediscover this.

> yosys's process passes are the
> code that does the control-flow to data-flow translation. This difference
> was apparently not noticed, hence why you apparently thought we could do
> the same kind of thing as was done for mux/part/etc.
>
> To implement PartitionedSignal support for If/Switch/Case, we would need a
> full-on vectorization pass -- this is similar to translating SIMT gpu code
> into explicit-vectors & predication.

the trick that i noticed is that Partitioned-Mux is basically a batch of
independent Muxes.

that means that at the right strategic point the translation may be delegated
to PartitionedSignal to perform the required for-loop.

i knew exactly where that could be done, several months ago, and unfortunately
i now have to find it again.

>
> > > and ends up leaving them to yosys's process_* passes to
> > > translate to logic -- adding support for new types will be a major job.
> >
> > nope, not at all.  if you believe this then you have fundamentally
> > misunderstood
> > the scope and design.
>
>
> you've fundamentally missed my point...the code we would end up writing *in
> PartitionedSignal* would be a functional duplicate (actually even more
> complex due to vectorization) of what currently exists in yosys's process
> passes. nmigen passes the switch/if/case statements *unmodified* to yosys.
> nmigen *does not* do any lowering to muxes that we could hook into, it
> leaves that all to yosys.

i worked out that by simply having the for-loop in nmigen it can generate
*multiple* independent switch statements, one per "byte" of the "Partitioned"
work.

by insisting on a rule that PartitionedBool have all bits set when handed
to PartitionedMux, the problem is solved.

[there are two possible implementations of PartitionedBool:
(1) the LSB of a given partition is set to indicate yes/no
(2) *ALL* bits of a given partition are set to indicate yes/no
by choosing (2) it makes PartitionedMux incredibly simple]

https://git.libre-soc.org/?p=ieee754fpu.git;a=blob;f=src/ieee754/part_mux/part_mux.py;hb=HEAD#l33

> >
> nmigen's If/Switch/Case fundamentally assume the boolean conditions (the
> output of the if condition/case matching logic) it uses are 1 bit wide, it
> doesn't support vectors of boolean conditions.

this is what i was referring to about the PartitionedBool.
when i last looked, i identified that there is *one* key strategic point where
that boolean condition is now no longer 1 bit wide, it is PartitionedBool
bits wide.

problem solved.

> it would require major
> refactoring to be usable for our purposes,

that would be unacceptable and, i believe, unnecessary.

> the  alternative is to implement
> the same logic ourselves (essentially reimplementing yosys's process
> passes).

yeah we're not doing that as a first pass.

> >
> > > From what I see, we have several options available:
> > > 1. take the do-it-ourselves approach of having nmigen If, Switch, and
> > Case
> > > all just defer to PartitionedSignal methods, this requires reimplementing
> > > inside PartitionedSignal what is currently a major portion of nmigen and
> > > basically all of yosys's process logic.
> >
> > no.  look again.  it is *absolutely not* the case that yosys or nmigen
> > itself
> > need know *anything* about data types other than those that yosys and
> > the IR generated and targetted by nmigen.
> >
>
> it *does* need to know since a vector of boolean conditions is
> fundamentally different than a 1-bit-wide boolean condition.

what i came up with was to put in an abstraction level where that
decision-making is delegated to something e.g. PartitionedBool.

the *existing* nmigen code then doesn't care that PartitionedBool
performed a for-loop and used PartitionedMux underneath.

i'm annoyed with myself for having left this for so long, i now
can't remember exactly what lines of code in nmigen i was
actually looking at.

> we *can* take
> the option of bypassing nmigen and yosys's if/switch/case logic completely,
> but we'd need to reimplement it all in PartitionedSignal.

yeah we're not doing that either, unless it turns out to be aaabbsolutely
necessary.

so far i'm not convinced it is.

l.