src/nmutil/lut.py

   1 # SPDX-License-Identifier: LGPL-3-or-later
   2 # Copyright 2021 Jacob Lifshay
   3 # Copyright (C) 2021 Luke Kenneth Casson Leighton <lkcl@lkcl.net>
   4
   5 # Funded by NLnet Assure Programme 2021-02-052, https://nlnet.nl/assure part
   6 # of Horizon 2020 EU Programme 957073.
   7
   8 """Bitwise logic operators implemented using a look-up table, like LUTs in
   9 FPGAs. Inspired by x86's `vpternlog[dq]` instructions.
  10
  11 https://bugs.libre-soc.org/show_bug.cgi?id=745
  12 https://www.felixcloutier.com/x86/vpternlogd:vpternlogq
  13 """
  14
  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
  20
  21 class BitwiseMux(Elaboratable):
  22     """Mux, but treating input/output Signals as bit vectors, rather than
  23     integers. This means each bit in the output is independently multiplexed
  24     based on the corresponding bit in each of the inputs.
  25     """
  26
  27     def __init__(self, width):
  28         self.sel = Signal(width)
  29         self.t = Signal(width)
  30         self.f = Signal(width)
  31         self.output = Signal(width)
  32
  33     def elaborate(self, platform):
  34         m = Module()
  35         m.d.comb += self.output.eq((~self.sel & self.f) | (self.sel & self.t))
  36         return m
  37
  38
  39 class BitwiseLut(Elaboratable):
  40     """Bitwise logic operators implemented using a look-up table, like LUTs in
  41     FPGAs. Inspired by x86's `vpternlog[dq]` instructions.
  42
  43     Each output bit `i` is set to `lut[Cat(inp[i] for inp in self.inputs)]`
  44     """
  45
  46     def __init__(self, input_count, width):
  47         """
  48         input_count: int
  49             the number of inputs. ternlog-style instructions have 3 inputs.
  50         width: int
  51             the number of bits in each input/output.
  52         """
  53         self.input_count = input_count
  54         self.width = width
  55
  56         def inp(i):
  57             return Signal(width, name=f"input{i}")
  58         self.inputs = tuple(inp(i) for i in range(input_count))  # inputs
  59         self.lut = Signal(2 ** input_count)                     # lookup input
  60         self.output = Signal(width)                             # output
  61
  62     def elaborate(self, platform):
  63         m = Module()
  64         comb = m.d.comb
  65         lut_array = Array(self.lut)  # create dynamic-indexable LUT array
  66         out = []
  67
  68         for bit in range(self.width):
  69             # take the bit'th bit of every input, create a LUT index from it
  70             index = Signal(self.input_count, name="index%d" % bit)
  71             comb += index.eq(Cat(inp[bit] for inp in self.inputs))
  72             # store output bit in a list - Cat() it after (simplifies graphviz)
  73             outbit = Signal(name="out%d" % bit)
  74             comb += outbit.eq(lut_array[index])
  75             out.append(outbit)
  76
  77         # finally Cat() all the output bits together
  78         comb += self.output.eq(Cat(*out))
  79         return m
  80
  81     def ports(self):
  82         return list(self.inputs) + [self.lut, self.output]
  83
  84
  85 class TreeBitwiseLut(Elaboratable):
  86     """Tree-based version of BitwiseLut. See BitwiseLut for API documentation.
  87     (good enough reason to say "see bitwiselut", but mention that
  88     the API is identical and explain why the second implementation
  89     exists, despite it being identical)
  90     """
  91
  92     def __init__(self, input_count, width):
  93         self.input_count = input_count
  94         self.width = width
  95
  96         def inp(i):
  97             return Signal(width, name=f"input{i}")
  98         self.inputs = tuple(inp(i) for i in range(input_count))
  99         self.output = Signal(width)
 100         self.lut = Signal(2 ** input_count)
 101         self._mux_inputs = {}
 102         self._build_mux_inputs()
 103
 104     def _make_key_str(self, *sel_values):
 105         k = ['x'] * self.input_count
 106         for i, v in enumerate(sel_values):
 107             k[i] = '1' if v else '0'
 108         return '0b' + ''.join(reversed(k))
 109
 110     def _build_mux_inputs(self, *sel_values):
 111         # XXX yyyeah using PHP-style functions-in-text... blech :)
 112         # XXX replace with name = mux_input_%s" % self._make_etcetc
 113         name = f"mux_input_{self._make_key_str(*sel_values)}"
 114         self._mux_inputs[sel_values] = Signal(self.width, name=name)
 115         if len(sel_values) < self.input_count:
 116             self._build_mux_inputs(*sel_values, False)
 117             self._build_mux_inputs(*sel_values, True)
 118
 119     def elaborate(self, platform):
 120         m = Module()
 121         m.d.comb += self.output.eq(self._mux_inputs[()])
 122         for sel_values, v in self._mux_inputs.items():
 123             if len(sel_values) < self.input_count:
 124                 # XXX yyyeah using PHP-style functions-in-text... blech :)
 125                 # XXX replace with name = mux_input_%s" % self._make_etcetc
 126                 mux_name = f"mux_{self._make_key_str(*sel_values)}"
 127                 mux = BitwiseMux(self.width)
 128                 setattr(m.submodules, mux_name, mux)
 129                 m.d.comb += [
 130                     mux.f.eq(self._mux_inputs[(*sel_values, False)]),
 131                     mux.t.eq(self._mux_inputs[(*sel_values, True)]),
 132                     mux.sel.eq(self.inputs[len(sel_values)]),
 133                     v.eq(mux.output),
 134                 ]
 135             else:
 136                 lut_index = 0
 137                 for i in range(self.input_count):
 138                     if sel_values[i]:
 139                         lut_index |= 2 ** i
 140                 m.d.comb += v.eq(Repl(self.lut[lut_index], self.width))
 141         return m
 142
 143     def ports(self):
 144         return [self.input, self.chunk_sizes, self.output]
 145
 146
 147 # useful to see what is going on:
 148 # yosys <<<"read_ilang sim_test_out/__main__.TestBitwiseLut.test_tree/0.il; proc;;; show top"