[libre-riscv-dev] div/mod algorithm written in python

[Luke Kenneth Casson Leighton]

workaround.

the graphviz for "|"ing bits together is absolutely dreadful, plus the
RTL that would be generated is a massive chain of OR gates.

this is what "bool" is for (which is a yosys operator, that can be
optimised by the HW generator into a tree-structure-of-OR-gates).

i use a list and Cat(*list) to accumulate and compress the Signals,
and it results in really clean-looking graphviz.

the assignment of "test" to what is in the Mux was what "fixed" the
"problem".  examining the IL file, the input was 2 bits wide, somehow.
Mux must only have a 1-bit-wide signal, which is probably what the
problem was.

managed to get a yosys file and examined the graphviz: it looks really
clean.  the only thing is: by not using "reset_less=True" in the
signals, "rst" has been jammed into pretty much just about ******
everything.

the operation, setup and final graphviz look really clean.  operation
has some weird magic constants that seem to be repeated a lot: this is
probably down to an assignment to a python variable somewhere, that
then gets "innocently used" in a loop.  (1<<0b111) or
Const(1)<<Const(7) is probably the cause, where it would be better
just using a python number that gets *converted* to a Const (after the
calculation).  otherwise, nmigen thinks it should actually generate
RTL to *generate* (in hardware) that Constant.

yep, here we go:
            shifted_trial_bits = Const(trial_bits, log2_radix) << current_shift

if that's replaced with:
            shifted_trial_bits = Const(trial_bits<<current_shift,
log2_radix+current_shift)

an awful lot of those dreadful constants will disappear.  just tried
that... you'll need to take a look, and in particular examine the
graphviz because some of the magic constants are zero (probably the
Const is not long enough: a shift is making the top bit disappear).

root_times_radicand, quotient_root, divisor_radicant, they're all
multiplied by zero which is probably not what's wanted, at all.

l.

diff --git a/berkeley-softfloat-3 b/berkeley-softfloat-3
--- a/berkeley-softfloat-3
+++ b/berkeley-softfloat-3
@@ -1 +1 @@
-Subproject commit b64af41c3276f97f0e181920400ee056b9c88037
+Subproject commit b64af41c3276f97f0e181920400ee056b9c88037-dirty
diff --git a/src/ieee754/div_rem_sqrt_rsqrt/core.py
b/src/ieee754/div_rem_sqrt_rsqrt/core.py
index 63c1721..ffcd7ce 100644
--- a/src/ieee754/div_rem_sqrt_rsqrt/core.py
+++ b/src/ieee754/div_rem_sqrt_rsqrt/core.py
@@ -18,7 +18,7 @@ Formulas solved are:
 The remainder is the left-hand-side of the comparison minus the
 right-hand-side of the comparison in the above formulas.
 """
-from nmigen import (Elaboratable, Module, Signal, Const, Mux)
+from nmigen import (Elaboratable, Module, Signal, Const, Mux, Cat)
 import enum


@@ -351,14 +351,20 @@ class DivPipeCoreCalculateStage(Elaboratable):
                 bit_value ^= pass_flags[j]
             m.d.comb += next_bits.part(i, 1).eq(bit_value)

-        next_compare_rhs = 0
+        next_compare_rhs = Signal(radix, reset_less=True)
+        l = []
         for i in range(radix):
             next_flag = pass_flags[i + 1] if i + 1 < radix else 0
-            next_compare_rhs |= Mux(pass_flags[i] & ~next_flag,
+            flag = Signal(reset_less=True)
+            test = Signal(reset_less=True)
+            m.d.comb += test.eq((pass_flags[i] & ~next_flag))
+            m.d.comb += flag.eq(Mux(test,
                                     trial_compare_rhs_values[i],
-                                    0)
+                                    0))
+            l.append(flag)

-        m.d.comb += self.o.compare_rhs.eq(next_compare_rhs)
+        m.d.comb += next_compare_rhs.eq(Cat(*l))
+        m.d.comb += self.o.compare_rhs.eq(next_compare_rhs.bool())
         m.d.comb += self.o.root_times_radicand.eq(self.i.root_times_radicand
                                                   + ((self.i.divisor_radicand
                                                       * next_bits)

On Sun, Jul 7, 2019 at 12:25 PM Jacob Lifshay <programmerjake at gmail.com> wrote:
>
> On Sun, Jul 7, 2019, 04:23 Luke Kenneth Casson Leighton <lkcl at lkcl.net>
> wrote:
>
> > On Sun, Jul 7, 2019 at 11:24 AM Jacob Lifshay <programmerjake at gmail.com>
> > wrote:
> > >
> > > I refactored core.py into core.py and div_pipe.py.
> > > I also added tests that demonstrate integer and fractional division:
> > > test_algorithm.py:test_int_div/test_fract_div
> > >
> > > I added most of the test code for DivPipeCore, but there's a bug
> > > somewhere (probably in core.py) that makes nmigen generate invalid
> > > rtlil (yosys complains when trying to load it).
> >
> >  fascinating
> >
> > yosys> read_ilang div_pipe_core_bit_width_8_fract_width_4_radix_2.il
> > 1. Executing ILANG frontend.
> > Input filename: div_pipe_core_bit_width_8_fract_width_4_radix_2.il
> > ERROR: Found error in internal cell \div_pipe_core_calculate_7.$132
> > ($mux) at kernel/rtlil.cc:717:
> >   attribute \src "/home/lkcl/src/riscv/nmigen/nmigen/hdl/ir.py:42"
> >   cell $mux $132
> >     parameter \WIDTH 24
> >     connect \Y $129
> >     connect \S $130
> >     connect \B \trial_compare_rhs_1
> >     connect \A 24'000000000000000000000000
> >   end
> >
> > definitely one to raise on the yosys bugtracker.
> >
> I don't think it's a bug in yosys, since the simulator also crashes.
>
> >
> > _______________________________________________
> > libre-riscv-dev mailing list
> > libre-riscv-dev at lists.libre-riscv.org
> > http://lists.libre-riscv.org/mailman/listinfo/libre-riscv-dev
> >
> _______________________________________________
> libre-riscv-dev mailing list
> libre-riscv-dev at lists.libre-riscv.org
> http://lists.libre-riscv.org/mailman/listinfo/libre-riscv-dev