migen/fhdl/namer.py

   1 from collections import OrderedDict
   2 from itertools import combinations
   3
   4 from migen.fhdl.structure import *
   5
   6
   7 class _Node:
   8     def __init__(self):
   9         self.signal_count = 0
  10         self.numbers = set()
  11         self.use_name = False
  12         self.use_number = False
  13         self.children = OrderedDict()
  14
  15
  16 def _display_tree(filename, tree):
  17     from migen.util.treeviz import RenderNode
  18
  19     def _to_render_node(name, node):
  20         children = [_to_render_node(k, v) for k, v in node.children.items()]
  21         if node.use_name:
  22             if node.use_number:
  23                 color = (0.5, 0.9, 0.8)
  24             else:
  25                 color = (0.8, 0.5, 0.9)
  26         else:
  27             if node.use_number:
  28                 color = (0.9, 0.8, 0.5)
  29             else:
  30                 color = (0.8, 0.8, 0.8)
  31         label = "{0}\n{1} signals\n{2}".format(name, node.signal_count, node.numbers)
  32         return RenderNode(label, children, color=color)
  33
  34     top = _to_render_node("top", tree)
  35     top.to_svg(filename)
  36
  37
  38 def _build_tree(signals, basic_tree=None):
  39     root = _Node()
  40     for signal in signals:
  41         current_b = basic_tree
  42         current = root
  43         current.signal_count += 1
  44         for name, number in signal.backtrace:
  45             if basic_tree is None:
  46                 use_number = False
  47             else:
  48                 current_b = current_b.children[name]
  49                 use_number = current_b.use_number
  50             if use_number:
  51                 key = (name, number)
  52             else:
  53                 key = name
  54             try:
  55                 current = current.children[key]
  56             except KeyError:
  57                 new = _Node()
  58                 current.children[key] = new
  59                 current = new
  60             current.numbers.add(number)
  61             if use_number:
  62                 current.all_numbers = sorted(current_b.numbers)
  63             current.signal_count += 1
  64     return root
  65
  66
  67 def _set_use_name(node, node_name=""):
  68     cnames = [(k, _set_use_name(v, k)) for k, v in node.children.items()]
  69     for (c1_prefix, c1_names), (c2_prefix, c2_names) in combinations(cnames, 2):
  70         if not c1_names.isdisjoint(c2_names):
  71             node.children[c1_prefix].use_name = True
  72             node.children[c2_prefix].use_name = True
  73     r = set()
  74     for c_prefix, c_names in cnames:
  75         if node.children[c_prefix].use_name:
  76             for c_name in c_names:
  77                 r.add((c_prefix, ) + c_name)
  78         else:
  79             r |= c_names
  80
  81     if node.signal_count > sum(c.signal_count for c in node.children.values()):
  82         node.use_name = True
  83         r.add((node_name, ))
  84
  85     return r
  86
  87
  88 def _name_signal(tree, signal):
  89     elements = []
  90     treepos = tree
  91     for step_name, step_n in signal.backtrace:
  92         try:
  93             treepos = treepos.children[(step_name, step_n)]
  94             use_number = True
  95         except KeyError:
  96             treepos = treepos.children[step_name]
  97             use_number = False
  98         if treepos.use_name:
  99             elname = step_name
 100             if use_number:
 101                 elname += str(treepos.all_numbers.index(step_n))
 102             elements.append(elname)
 103     return "_".join(elements)
 104
 105
 106 def _build_pnd_from_tree(tree, signals):
 107     return dict((signal, _name_signal(tree, signal)) for signal in signals)
 108
 109
 110 def _invert_pnd(pnd):
 111     inv_pnd = dict()
 112     for k, v in pnd.items():
 113         inv_pnd[v] = inv_pnd.get(v, [])
 114         inv_pnd[v].append(k)
 115     return inv_pnd
 116
 117
 118 def _list_conflicting_signals(pnd):
 119     inv_pnd = _invert_pnd(pnd)
 120     r = set()
 121     for k, v in inv_pnd.items():
 122         if len(v) > 1:
 123             r.update(v)
 124     return r
 125
 126
 127 def _set_use_number(tree, signals):
 128     for signal in signals:
 129         current = tree
 130         for step_name, step_n in signal.backtrace:
 131             current = current.children[step_name]
 132             current.use_number = current.signal_count > len(current.numbers) and len(current.numbers) > 1
 133
 134 _debug = False
 135
 136
 137 def _build_pnd_for_group(group_n, signals):
 138     basic_tree = _build_tree(signals)
 139     _set_use_name(basic_tree)
 140     if _debug:
 141         _display_tree("tree{0}_basic.svg".format(group_n), basic_tree)
 142     pnd = _build_pnd_from_tree(basic_tree, signals)
 143
 144     # If there are conflicts, try splitting the tree by numbers
 145     # on paths taken by conflicting signals.
 146     conflicting_signals = _list_conflicting_signals(pnd)
 147     if conflicting_signals:
 148         _set_use_number(basic_tree, conflicting_signals)
 149         if _debug:
 150             print("namer: using split-by-number strategy (group {0})".format(group_n))
 151             _display_tree("tree{0}_marked.svg".format(group_n), basic_tree)
 152         numbered_tree = _build_tree(signals, basic_tree)
 153         _set_use_name(numbered_tree)
 154         if _debug:
 155             _display_tree("tree{0}_numbered.svg".format(group_n), numbered_tree)
 156         pnd = _build_pnd_from_tree(numbered_tree, signals)
 157     else:
 158         if _debug:
 159             print("namer: using basic strategy (group {0})".format(group_n))
 160
 161     # ...then add number suffixes by DUID
 162     inv_pnd = _invert_pnd(pnd)
 163     duid_suffixed = False
 164     for name, signals in inv_pnd.items():
 165         if len(signals) > 1:
 166             duid_suffixed = True
 167             for n, signal in enumerate(sorted(signals, key=lambda x: x.duid)):
 168                 pnd[signal] += str(n)
 169     if _debug and duid_suffixed:
 170         print("namer: using DUID suffixes (group {0})".format(group_n))
 171
 172     return pnd
 173
 174
 175 def _build_signal_groups(signals):
 176     r = []
 177     for signal in signals:
 178         # build chain of related signals
 179         related_list = []
 180         cur_signal = signal
 181         while cur_signal is not None:
 182             related_list.insert(0, cur_signal)
 183             cur_signal = cur_signal.related
 184         # add to groups
 185         for _ in range(len(related_list) - len(r)):
 186             r.append(set())
 187         for target_set, source_signal in zip(r, related_list):
 188             target_set.add(source_signal)
 189     # with the algorithm above and a list of all signals,
 190     # a signal appears in all groups of a lower number than its.
 191     # make signals appear only in their group of highest number.
 192     for s1, s2 in zip(r, r[1:]):
 193         s1 -= s2
 194     return r
 195
 196
 197 def _build_pnd(signals):
 198     groups = _build_signal_groups(signals)
 199     gpnds = [_build_pnd_for_group(n, gsignals) for n, gsignals in enumerate(groups)]
 200
 201     pnd = dict()
 202     for gn, gpnd in enumerate(gpnds):
 203         for signal, name in gpnd.items():
 204             result = name
 205             cur_gn = gn
 206             cur_signal = signal
 207             while cur_signal.related is not None:
 208                 cur_signal = cur_signal.related
 209                 cur_gn -= 1
 210                 result = gpnds[cur_gn][cur_signal] + "_" + result
 211             pnd[signal] = result
 212
 213     return pnd
 214
 215
 216 def build_namespace(signals, reserved_keywords=set()):
 217     pnd = _build_pnd(signals)
 218     ns = Namespace(pnd, reserved_keywords)
 219     # register signals with name_override
 220     for signal in signals:
 221         if signal.name_override is not None:
 222             ns.get_name(signal)
 223     return ns
 224
 225
 226 class Namespace:
 227     def __init__(self, pnd, reserved_keywords=set()):
 228         self.counts = {k: 1 for k in reserved_keywords}
 229         self.sigs = {}
 230         self.pnd = pnd
 231         self.clock_domains = dict()
 232
 233     def get_name(self, sig):
 234         if isinstance(sig, ClockSignal):
 235             sig = self.clock_domains[sig.cd].clk
 236         if isinstance(sig, ResetSignal):
 237             sig = self.clock_domains[sig.cd].rst
 238             if sig is None:
 239                 raise ValueError("Attempted to obtain name of non-existent "
 240                                  "reset signal of domain "+sig.cd)
 241
 242         if sig.name_override is not None:
 243             sig_name = sig.name_override
 244         else:
 245             sig_name = self.pnd[sig]
 246         try:
 247             n = self.sigs[sig]
 248         except KeyError:
 249             try:
 250                 n = self.counts[sig_name]
 251             except KeyError:
 252                 n = 0
 253             self.sigs[sig] = n
 254             self.counts[sig_name] = n + 1
 255         if n:
 256             return sig_name + "_" + str(n)
 257         else:
 258             return sig_name