[Libre-soc-bugs] [Bug 784] Implement cl* instructions for carry-less operations

bugzilla-daemon at libre-soc.org bugzilla-daemon at libre-soc.org
Tue Apr 5 18:50:22 BST 2022


https://bugs.libre-soc.org/show_bug.cgi?id=784

--- Comment #11 from Jacob Lifshay <programmerjake at gmail.com> ---
(In reply to Luke Kenneth Casson Leighton from comment #4)
> (In reply to Jacob Lifshay from comment #3)
> > I started adding CLDivRem, but ran into a yosys bug:
> > https://github.com/YosysHQ/yosys/issues/3268
> 
> intriguing.  relying on complex switch/case, not so hot, eh? :)

the complex switch case came from the dumb-and-obvious method i use in the
formal proof in TestEqualLeadingZeroCount. apparently yosys tries to create a
hashmap with an entry for each possible input value -- exponential in input
size.

> > I added TestEqualLeadingZeroCount which will be used in the cldivrem
> > algorithm for testing if two GF(2) polynomials have equal degrees. 
> 
> hmm hmm i was looking at this and thought, actually, finding the
> minimum cntlz of two things might be more useful?

that would be useful (or actually the count trailing zeros variant), but not
for cldivrem. the minimum cnttz is simply cnttz(a | b), so we don't need a
separate implementation of that.

> https://git.libre-soc.org/?p=nmigen-gf.git;a=blob;f=gf_reference/gfpinv.py;
> h=45b6dbbdd4cb19bdbfa0538fb9dfcb79981655fe;
> hb=926798b6e232f09a36773be07de2d90e3fd431a4
> 
> > It should
> > have a similar complexity to a binary addition (it uses binary addition
> > internally, the extraneous xor gates from addition are optimized out by
> > yosys).
> 
> are or should be? relying on complex low-level capability of yosys is
> not... wise.
> 
> > https://git.libre-soc.org/?p=nmigen-gf.git;a=blob;f=src/nmigen_gf/hdl/
> > cldivrem.py;h=9a89c43046e2535fb272f47efefe51fb256db482;
> > hb=423b3a3279e3637614a614ec7038ebaa7cabd6c0
> 
> nextpnr-ecp5 doesn't have carry-out, and both symbiflow and
> nextpnr-xilinx's use of CARRY4 are borked at the moment.
> also the balancing of carry propagation is not very good in
> yosys.

it's waay better than a 64-deep chain of gates, otherwise all cpus using yosys
would fail timing.

-- 
You are receiving this mail because:
You are on the CC list for the bug.


More information about the libre-soc-bugs mailing list