1 # SPDX-License-Identifier: LGPL-3-or-later
2 # Copyright 2021 Jacob Lifshay
3 # Copyright (C) 2021 Luke Kenneth Casson Leighton <lkcl@lkcl.net>
5 # Funded by NLnet Assure Programme 2021-02-052, https://nlnet.nl/assure part
6 # of Horizon 2020 EU Programme 957073.
8 """Bitwise logic operators implemented using a look-up table, like LUTs in
9 FPGAs. Inspired by x86's `vpternlog[dq]` instructions.
11 https://bugs.libre-soc.org/show_bug.cgi?id=745
12 https://www.felixcloutier.com/x86/vpternlogd:vpternlogq
15 from nmigen
.hdl
.ast
import Array
, Cat
, Repl
, Signal
16 from nmigen
.hdl
.dsl
import Module
17 from nmigen
.hdl
.ir
import Elaboratable
18 from nmigen
.cli
import rtlil
19 from nmutil
.plain_data
import plain_data
22 class BitwiseMux(Elaboratable
):
23 """Mux, but treating input/output Signals as bit vectors, rather than
24 integers. This means each bit in the output is independently multiplexed
25 based on the corresponding bit in each of the inputs.
28 def __init__(self
, width
):
29 self
.sel
= Signal(width
)
30 self
.t
= Signal(width
)
31 self
.f
= Signal(width
)
32 self
.output
= Signal(width
)
34 def elaborate(self
, platform
):
36 m
.d
.comb
+= self
.output
.eq((~self
.sel
& self
.f
) |
(self
.sel
& self
.t
))
40 class BitwiseLut(Elaboratable
):
41 """Bitwise logic operators implemented using a look-up table, like LUTs in
42 FPGAs. Inspired by x86's `vpternlog[dq]` instructions.
44 Each output bit `i` is set to `lut[Cat(inp[i] for inp in self.inputs)]`
47 def __init__(self
, input_count
, width
):
50 the number of inputs. ternlog-style instructions have 3 inputs.
52 the number of bits in each input/output.
54 self
.input_count
= input_count
58 return Signal(width
, name
=f
"input{i}")
59 self
.inputs
= tuple(inp(i
) for i
in range(input_count
)) # inputs
60 self
.lut
= Signal(2 ** input_count
) # lookup input
61 self
.output
= Signal(width
) # output
63 def elaborate(self
, platform
):
66 lut_array
= Array(self
.lut
) # create dynamic-indexable LUT array
69 for bit
in range(self
.width
):
70 # take the bit'th bit of every input, create a LUT index from it
71 index
= Signal(self
.input_count
, name
="index%d" % bit
)
72 comb
+= index
.eq(Cat(inp
[bit
] for inp
in self
.inputs
))
73 # store output bit in a list - Cat() it after (simplifies graphviz)
74 outbit
= Signal(name
="out%d" % bit
)
75 comb
+= outbit
.eq(lut_array
[index
])
78 # finally Cat() all the output bits together
79 comb
+= self
.output
.eq(Cat(*out
))
83 return list(self
.inputs
) + [self
.lut
, self
.output
]
88 """Mux in tree for `TreeBitwiseLut`.
92 container: TreeBitwiseLut
93 parent: _TreeMuxNode | None
94 child0: _TreeMuxNode | None
95 child1: _TreeMuxNode | None
98 __slots__
= "out", "container", "parent", "child0", "child1", "depth"
100 def __init__(self
, out
, container
, parent
, child0
, child1
, depth
):
103 container: TreeBitwiseLut
104 parent: _TreeMuxNode | None
105 child0: _TreeMuxNode | None
106 child1: _TreeMuxNode | None
110 self
.container
= container
117 def child_index(self
):
118 """index of this node, when looked up in this node's parent's children.
120 if self
.parent
is None:
122 return int(self
.parent
.child1
is self
)
124 def add_child(self
, child_index
):
126 out
=Signal(self
.container
.width
),
127 container
=self
.container
, parent
=self
,
128 child0
=None, child1
=None, depth
=1 + self
.depth
)
130 assert self
.child1
is None
133 assert self
.child0
is None
135 node
.out
.name
= "node_out_" + node
.key_str
142 while node
.parent
is not None:
143 retval
.append(node
.child_index
)
150 k
= ['x'] * self
.container
.input_count
151 for i
, v
in enumerate(self
.key
):
152 k
[i
] = '1' if v
else '0'
153 return '0b' + ''.join(reversed(k
))
156 class TreeBitwiseLut(Elaboratable
):
157 """Tree-based version of BitwiseLut. Has identical API, so see `BitwiseLut`
158 for API documentation. This version may produce more efficient hardware.
161 def __init__(self
, input_count
, width
):
162 self
.input_count
= input_count
166 return Signal(width
, name
=f
"input{i}")
167 self
.inputs
= tuple(inp(i
) for i
in range(input_count
))
168 self
.output
= Signal(width
)
169 self
.lut
= Signal(2 ** input_count
)
170 self
._tree
_root
= _TreeMuxNode(
171 out
=self
.output
, container
=self
, parent
=None,
172 child0
=None, child1
=None, depth
=0)
173 self
._build
_tree
(self
._tree
_root
)
175 def _build_tree(self
, node
):
176 if node
.depth
< self
.input_count
:
177 self
._build
_tree
(node
.add_child(0))
178 self
._build
_tree
(node
.add_child(1))
180 def _elaborate_tree(self
, m
, node
):
181 if node
.depth
< self
.input_count
:
182 mux
= BitwiseMux(self
.width
)
183 setattr(m
.submodules
, "mux_" + node
.key_str
, mux
)
185 mux
.f
.eq(node
.child0
.out
),
186 mux
.t
.eq(node
.child1
.out
),
187 mux
.sel
.eq(self
.inputs
[node
.depth
]),
188 node
.out
.eq(mux
.output
),
190 self
._elaborate
_tree
(m
, node
.child0
)
191 self
._elaborate
_tree
(m
, node
.child1
)
193 index
= int(node
.key_str
, base
=2)
194 m
.d
.comb
+= node
.out
.eq(Repl(self
.lut
[index
], self
.width
))
196 def elaborate(self
, platform
):
198 self
._elaborate
_tree
(m
, self
._tree
_root
)
202 return [*self
.inputs
, self
.lut
, self
.output
]
205 # useful to see what is going on:
206 # python3 src/nmutil/test/test_lut.py
207 # yosys <<<"read_ilang sim_test_out/__main__.TestBitwiseLut.test_tree/0.il; proc;;; show top"
209 if __name__
== '__main__':
210 dut
= BitwiseLut(2, 64)
211 vl
= rtlil
.convert(dut
, ports
=dut
.ports())
212 with
open("test_lut2.il", "w") as f
: