[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 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.

this pretty much invalidates all of the assumptions made below, but i'll
go through them for completeness.

> 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.

> 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.

> I'd estimate 2-3 months full-time
> work just for the implementation ignoring formal proofs with minimal
> modifications to nmigen and no modifications to yosys. This is probably the
> option lkcl was originally thinking of, but I think he underestimated its
> difficulty.

no, i did not.  i spent several months looking at this.

the only thing that is questionable is whether a PartitionedBool type
is needed and if that needs to be understood / abstracted by nmigen.
i haven't looked at the nmigen source for some months, however i
vaguely recall that there was one place deep inside the IR
case-statement code (which handles all m.If/Else and all m.Switch/Case
conversion) that assumed bool was a single bit.

that *may* need to be (again) abstracted out to a PartitionedBool,
which will be a class whose sole exclusive job is to convert to basic
nmigen types, i.e. "bits".

yosys IN ABSOLUTELY NO WAY SHAPE OR FORM NEITHER AT
THE YOSYS LEVEL NOR THE IR LEVEL needs to know about that
type, because by the time it reaches yosys it hsa ALREADY BEEN
CONVERTED TO A STRAIGHT STANDARD SIGNAL.

this is far, FAR simpler than you believe it to be.  it is one of those
"strategic" minimalist changes that took some considerable time
amd care to identify.

> 2. figure out how to thread PartitionedSignal through nmigen

i've already done the analysis. it's actually incredibly simple.
it's so simple that it's a matter of "i can't possibly believe it
could be that simple"

https://bugs.libre-soc.org/show_bug.cgi?id=458#c4

< and yosys,

NO.

> this will require easily >4mo work and seems highly likely to be rejected
> by nmigen and yosys upstreams.

to give you some idea: whitequark has *already* understood it, likes
the idea, understands that it is beneficial, and has **NOT IN ANY WAY
SHAPE OR FORM* said, "this will require massive upstream modifications
of yosys".

once she understood that it was a viable and necessary idea, she got it
straight away, and understood what was needed to make it work.

the discussion that i had with her involved *general abstractions*. someone
else suggested a ComplexNumberSignal as a potential idea.  another
one would be a GaloisFieldSignal or a FixedSizeFloatingPointSignal
and many others, where it would be completely insane to consider
burdening yosys with each and every one of those types.  the possibility
did not even come up because we both understood that it was perfectly
achievable within nmigen alone.

this should tell you everything you need to know, i.e. that you have
fundamentally misunderstood and drastically overestimated what
needs to be done.

> 3. (my preference):
> write our code to use Mux instead of If/Switch/Case when dealing with
> PartitionedSignal; this will reduce readability of our code,

which is unacceptable, given the complexity, and is precisely why
i investigated finding the strategic point in nmigen that needs modification.

it turned out to be extremely simple: follow python operator class.
extend the same concept to nmigen.

> but will be waay easier to do.

the cost of *throwing away* and rewriting over 60,000 lines of HDL -
the entirety of the IEEE754 library for a start - is unthinkable and
completely out of the question.

particularly given that the actual modifcations needed to nmigen -
NOT YOSYS - nmigen - are of the order of tens of lines of code.
[the unit tests however will need to be quite comprehensive]

nmigen's m.If/Else and m.Switch/Case constructs map down
onto case statements in an AST parser phase.  those case
statements are then in turn mapped onto nmigen MUX, CAT
and PART.

by the time the m.If/Else and m.Switch/Case statements are
done, the entire AST is completely devoid of all evidence of
If/Else, and pure IR-level Mux and IR-level case/switch is
all that is left.

therefore, by providing an over-ride mechanism whereby
MUX, CAT and PART may redirect to kls.__MUX__,
kls.__CAT__ and kls.__PART__ respectively, it becomes
the responsibility of PartitionedSignal to *provide* those
functions, and to do so by mapping **ONLY TO BASIC TYPES
SUPPORTED BY NMIGEN**.

PartitionedSignal.Mux has already been written.  Part needs
some thought.  Cat likewise.  they basically involve dynamic
for-loops.

it *really is* that localised.

there are some gotchas: Signals (particularly shifters and
multipliers) will need to be declared big enough to cope with
all possible sizes.  likewise, ArrayProxy is unlikely to work
(a variable-sized redirection array??) or at the very least
will require some extremely advanced work.
[which is precisely why i did NOT include it in the proposal]

it's not a "total dead straightforward" conversion process.
however it is far, FAR better than the alternatives, which are truly
staggeringly costly both to develop and maintain.

l.