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 dataclasses
import dataclass
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`."""
90 container
: "TreeBitwiseLut"
91 parent
: "_TreeMuxNode | None"
92 child0
: "_TreeMuxNode | None"
93 child1
: "_TreeMuxNode | None"
97 def child_index(self
):
98 """index of this node, when looked up in this node's parent's children.
100 if self
.parent
is None:
102 return int(self
.parent
.child1
is self
)
104 def add_child(self
, child_index
):
106 out
=Signal(self
.container
.width
),
107 container
=self
.container
, parent
=self
,
108 child0
=None, child1
=None, depth
=1 + self
.depth
)
110 assert self
.child1
is None
113 assert self
.child0
is None
115 node
.out
.name
= "node_out_" + node
.key_str
122 while node
.parent
is not None:
123 retval
.append(node
.child_index
)
130 k
= ['x'] * self
.container
.input_count
131 for i
, v
in enumerate(self
.key
):
132 k
[i
] = '1' if v
else '0'
133 return '0b' + ''.join(reversed(k
))
136 class TreeBitwiseLut(Elaboratable
):
137 """Tree-based version of BitwiseLut. Has identical API, so see `BitwiseLut`
138 for API documentation. This version may produce more efficient hardware.
141 def __init__(self
, input_count
, width
):
142 self
.input_count
= input_count
146 return Signal(width
, name
=f
"input{i}")
147 self
.inputs
= tuple(inp(i
) for i
in range(input_count
))
148 self
.output
= Signal(width
)
149 self
.lut
= Signal(2 ** input_count
)
150 self
._tree
_root
= _TreeMuxNode(
151 out
=self
.output
, container
=self
, parent
=None,
152 child0
=None, child1
=None, depth
=0)
153 self
._build
_tree
(self
._tree
_root
)
155 def _build_tree(self
, node
):
156 if node
.depth
< self
.input_count
:
157 self
._build
_tree
(node
.add_child(0))
158 self
._build
_tree
(node
.add_child(1))
160 def _elaborate_tree(self
, m
, node
):
161 if node
.depth
< self
.input_count
:
162 mux
= BitwiseMux(self
.width
)
163 setattr(m
.submodules
, "mux_" + node
.key_str
, mux
)
165 mux
.f
.eq(node
.child0
.out
),
166 mux
.t
.eq(node
.child1
.out
),
167 mux
.sel
.eq(self
.inputs
[node
.depth
]),
168 node
.out
.eq(mux
.output
),
170 self
._elaborate
_tree
(m
, node
.child0
)
171 self
._elaborate
_tree
(m
, node
.child1
)
173 index
= int(node
.key_str
, base
=2)
174 m
.d
.comb
+= node
.out
.eq(Repl(self
.lut
[index
], self
.width
))
176 def elaborate(self
, platform
):
178 self
._elaborate
_tree
(m
, self
._tree
_root
)
182 return [*self
.inputs
, self
.lut
, self
.output
]
185 # useful to see what is going on:
186 # yosys <<<"read_ilang sim_test_out/__main__.TestBitwiseLut.test_tree/0.il; proc;;; show top"