nmigen/hdl/ir.py

   1 from abc import ABCMeta, abstractmethod
   2 from collections import defaultdict, OrderedDict
   3 from functools import reduce
   4 import warnings
   5 import traceback
   6 import sys
   7
   8 from .._utils import *
   9 from .._unused import *
  10 from .ast import *
  11 from .cd import *
  12
  13
  14 __all__ = ["UnusedElaboratable", "Elaboratable", "DriverConflict", "Fragment", "Instance"]
  15
  16
  17 class UnusedElaboratable(UnusedMustUse):
  18     pass
  19
  20
  21 class Elaboratable(MustUse, metaclass=ABCMeta):
  22     _MustUse__warning = UnusedElaboratable
  23
  24
  25 class DriverConflict(UserWarning):
  26     pass
  27
  28
  29 class Fragment:
  30     @staticmethod
  31     def get(obj, platform):
  32         code = None
  33         while True:
  34             if isinstance(obj, Fragment):
  35                 return obj
  36             elif isinstance(obj, Elaboratable):
  37                 code = obj.elaborate.__code__
  38                 obj._MustUse__used = True
  39                 obj = obj.elaborate(platform)
  40             elif hasattr(obj, "elaborate"):
  41                 warnings.warn(
  42                     message="Class {!r} is an elaboratable that does not explicitly inherit from "
  43                             "Elaboratable; doing so would improve diagnostics"
  44                             .format(type(obj)),
  45                     category=RuntimeWarning,
  46                     stacklevel=2)
  47                 code = obj.elaborate.__code__
  48                 obj = obj.elaborate(platform)
  49             else:
  50                 raise AttributeError("Object {!r} cannot be elaborated".format(obj))
  51             if obj is None and code is not None:
  52                 warnings.warn_explicit(
  53                     message=".elaborate() returned None; missing return statement?",
  54                     category=UserWarning,
  55                     filename=code.co_filename,
  56                     lineno=code.co_firstlineno)
  57
  58     def __init__(self):
  59         self.ports = SignalDict()
  60         self.drivers = OrderedDict()
  61         self.statements = []
  62         self.domains = OrderedDict()
  63         self.subfragments = []
  64         self.attrs = OrderedDict()
  65         self.generated = OrderedDict()
  66         self.flatten = False
  67
  68     def add_ports(self, *ports, dir):
  69         assert dir in ("i", "o", "io")
  70         for port in flatten(ports):
  71             self.ports[port] = dir
  72
  73     def iter_ports(self, dir=None):
  74         if dir is None:
  75             yield from self.ports
  76         else:
  77             for port, port_dir in self.ports.items():
  78                 if port_dir == dir:
  79                     yield port
  80
  81     def add_driver(self, signal, domain=None):
  82         if domain not in self.drivers:
  83             self.drivers[domain] = SignalSet()
  84         self.drivers[domain].add(signal)
  85
  86     def iter_drivers(self):
  87         for domain, signals in self.drivers.items():
  88             for signal in signals:
  89                 yield domain, signal
  90
  91     def iter_comb(self):
  92         if None in self.drivers:
  93             yield from self.drivers[None]
  94
  95     def iter_sync(self):
  96         for domain, signals in self.drivers.items():
  97             if domain is None:
  98                 continue
  99             for signal in signals:
 100                 yield domain, signal
 101
 102     def iter_signals(self):
 103         signals = SignalSet()
 104         signals |= self.ports.keys()
 105         for domain, domain_signals in self.drivers.items():
 106             if domain is not None:
 107                 cd = self.domains[domain]
 108                 signals.add(cd.clk)
 109                 if cd.rst is not None:
 110                     signals.add(cd.rst)
 111             signals |= domain_signals
 112         return signals
 113
 114     def add_domains(self, *domains):
 115         for domain in flatten(domains):
 116             assert isinstance(domain, ClockDomain)
 117             assert domain.name not in self.domains
 118             self.domains[domain.name] = domain
 119
 120     def iter_domains(self):
 121         yield from self.domains
 122
 123     def add_statements(self, *stmts):
 124         for stmt in Statement.cast(stmts):
 125             stmt._MustUse__used = True
 126             self.statements.append(stmt)
 127
 128     def add_subfragment(self, subfragment, name=None):
 129         assert isinstance(subfragment, Fragment)
 130         self.subfragments.append((subfragment, name))
 131
 132     def find_subfragment(self, name_or_index):
 133         if isinstance(name_or_index, int):
 134             if name_or_index < len(self.subfragments):
 135                 subfragment, name = self.subfragments[name_or_index]
 136                 return subfragment
 137             raise NameError("No subfragment at index #{}".format(name_or_index))
 138         else:
 139             for subfragment, name in self.subfragments:
 140                 if name == name_or_index:
 141                     return subfragment
 142             raise NameError("No subfragment with name '{}'".format(name_or_index))
 143
 144     def find_generated(self, *path):
 145         if len(path) > 1:
 146             path_component, *path = path
 147             return self.find_subfragment(path_component).find_generated(*path)
 148         else:
 149             item, = path
 150             return self.generated[item]
 151
 152     def elaborate(self, platform):
 153         return self
 154
 155     def _merge_subfragment(self, subfragment):
 156         # Merge subfragment's everything except clock domains into this fragment.
 157         # Flattening is done after clock domain propagation, so we can assume the domains
 158         # are already the same in every involved fragment in the first place.
 159         self.ports.update(subfragment.ports)
 160         for domain, signal in subfragment.iter_drivers():
 161             self.add_driver(signal, domain)
 162         self.statements += subfragment.statements
 163         self.subfragments += subfragment.subfragments
 164
 165         # Remove the merged subfragment.
 166         found = False
 167         for i, (check_subfrag, check_name) in enumerate(self.subfragments): # :nobr:
 168             if subfragment == check_subfrag:
 169                 del self.subfragments[i]
 170                 found = True
 171                 break
 172         assert found
 173
 174     def _resolve_hierarchy_conflicts(self, hierarchy=("top",), mode="warn"):
 175         assert mode in ("silent", "warn", "error")
 176
 177         driver_subfrags = SignalDict()
 178         memory_subfrags = OrderedDict()
 179         def add_subfrag(registry, entity, entry):
 180             # Because of missing domain insertion, at the point when this code runs, we have
 181             # a mixture of bound and unbound {Clock,Reset}Signals. Map the bound ones to
 182             # the actual signals (because the signal itself can be driven as well); but leave
 183             # the unbound ones as it is, because there's no concrete signal for it yet anyway.
 184             if isinstance(entity, ClockSignal) and entity.domain in self.domains:
 185                 entity = self.domains[entity.domain].clk
 186             elif isinstance(entity, ResetSignal) and entity.domain in self.domains:
 187                 entity = self.domains[entity.domain].rst
 188
 189             if entity not in registry:
 190                 registry[entity] = set()
 191             registry[entity].add(entry)
 192
 193         # For each signal driven by this fragment and/or its subfragments, determine which
 194         # subfragments also drive it.
 195         for domain, signal in self.iter_drivers():
 196             add_subfrag(driver_subfrags, signal, (None, hierarchy))
 197
 198         flatten_subfrags = set()
 199         for i, (subfrag, name) in enumerate(self.subfragments):
 200             if name is None:
 201                 name = "<unnamed #{}>".format(i)
 202             subfrag_hierarchy = hierarchy + (name,)
 203
 204             if subfrag.flatten:
 205                 # Always flatten subfragments that explicitly request it.
 206                 flatten_subfrags.add((subfrag, subfrag_hierarchy))
 207
 208             if isinstance(subfrag, Instance):
 209                 # For memories (which are subfragments, but semantically a part of superfragment),
 210                 # record that this fragment is driving it.
 211                 if subfrag.type in ("$memrd", "$memwr"):
 212                     memory = subfrag.parameters["MEMID"]
 213                     add_subfrag(memory_subfrags, memory, (None, hierarchy))
 214
 215                 # Never flatten instances.
 216                 continue
 217
 218             # First, recurse into subfragments and let them detect driver conflicts as well.
 219             subfrag_drivers, subfrag_memories = \
 220                 subfrag._resolve_hierarchy_conflicts(subfrag_hierarchy, mode)
 221
 222             # Second, classify subfragments by signals they drive and memories they use.
 223             for signal in subfrag_drivers:
 224                 add_subfrag(driver_subfrags, signal, (subfrag, subfrag_hierarchy))
 225             for memory in subfrag_memories:
 226                 add_subfrag(memory_subfrags, memory, (subfrag, subfrag_hierarchy))
 227
 228         # Find out the set of subfragments that needs to be flattened into this fragment
 229         # to resolve driver-driver conflicts.
 230         def flatten_subfrags_if_needed(subfrags):
 231             if len(subfrags) == 1:
 232                 return []
 233             flatten_subfrags.update((f, h) for f, h in subfrags if f is not None)
 234             return list(sorted(".".join(h) for f, h in subfrags))
 235
 236         for signal, subfrags in driver_subfrags.items():
 237             subfrag_names = flatten_subfrags_if_needed(subfrags)
 238             if not subfrag_names:
 239                 continue
 240
 241             # While we're at it, show a message.
 242             message = ("Signal '{}' is driven from multiple fragments: {}"
 243                        .format(signal, ", ".join(subfrag_names)))
 244             if mode == "error":
 245                 raise DriverConflict(message)
 246             elif mode == "warn":
 247                 message += "; hierarchy will be flattened"
 248                 warnings.warn_explicit(message, DriverConflict, *signal.src_loc)
 249
 250         for memory, subfrags in memory_subfrags.items():
 251             subfrag_names = flatten_subfrags_if_needed(subfrags)
 252             if not subfrag_names:
 253                 continue
 254
 255             # While we're at it, show a message.
 256             message = ("Memory '{}' is accessed from multiple fragments: {}"
 257                        .format(memory.name, ", ".join(subfrag_names)))
 258             if mode == "error":
 259                 raise DriverConflict(message)
 260             elif mode == "warn":
 261                 message += "; hierarchy will be flattened"
 262                 warnings.warn_explicit(message, DriverConflict, *memory.src_loc)
 263
 264         # Flatten hierarchy.
 265         for subfrag, subfrag_hierarchy in sorted(flatten_subfrags, key=lambda x: x[1]):
 266             self._merge_subfragment(subfrag)
 267
 268         # If we flattened anything, we might be in a situation where we have a driver conflict
 269         # again, e.g. if we had a tree of fragments like A --- B --- C where only fragments
 270         # A and C were driving a signal S. In that case, since B is not driving S itself,
 271         # processing B will not result in any flattening, but since B is transitively driving S,
 272         # processing A will flatten B into it. Afterwards, we have a tree like AB --- C, which
 273         # has another conflict.
 274         if any(flatten_subfrags):
 275             # Try flattening again.
 276             return self._resolve_hierarchy_conflicts(hierarchy, mode)
 277
 278         # Nothing was flattened, we're done!
 279         return (SignalSet(driver_subfrags.keys()),
 280                 set(memory_subfrags.keys()))
 281
 282     def _propagate_domains_up(self, hierarchy=("top",)):
 283         from .xfrm import DomainRenamer
 284
 285         domain_subfrags = defaultdict(lambda: set())
 286
 287         # For each domain defined by a subfragment, determine which subfragments define it.
 288         for i, (subfrag, name) in enumerate(self.subfragments):
 289             # First, recurse into subfragments and let them propagate domains up as well.
 290             hier_name = name
 291             if hier_name is None:
 292                 hier_name = "<unnamed #{}>".format(i)
 293             subfrag._propagate_domains_up(hierarchy + (hier_name,))
 294
 295             # Second, classify subfragments by domains they define.
 296             for domain_name, domain in subfrag.domains.items():
 297                 if domain.local:
 298                     continue
 299                 domain_subfrags[domain_name].add((subfrag, name, i))
 300
 301         # For each domain defined by more than one subfragment, rename the domain in each
 302         # of the subfragments such that they no longer conflict.
 303         for domain_name, subfrags in domain_subfrags.items():
 304             if len(subfrags) == 1:
 305                 continue
 306
 307             names = [n for f, n, i in subfrags]
 308             if not all(names):
 309                 names = sorted("<unnamed #{}>".format(i) if n is None else "'{}'".format(n)
 310                                for f, n, i in subfrags)
 311                 raise DomainError("Domain '{}' is defined by subfragments {} of fragment '{}'; "
 312                                   "it is necessary to either rename subfragment domains "
 313                                   "explicitly, or give names to subfragments"
 314                                   .format(domain_name, ", ".join(names), ".".join(hierarchy)))
 315
 316             if len(names) != len(set(names)):
 317                 names = sorted("#{}".format(i) for f, n, i in subfrags)
 318                 raise DomainError("Domain '{}' is defined by subfragments {} of fragment '{}', "
 319                                   "some of which have identical names; it is necessary to either "
 320                                   "rename subfragment domains explicitly, or give distinct names "
 321                                   "to subfragments"
 322                                   .format(domain_name, ", ".join(names), ".".join(hierarchy)))
 323
 324             for subfrag, name, i in subfrags:
 325                 domain_name_map = {domain_name: "{}_{}".format(name, domain_name)}
 326                 self.subfragments[i] = (DomainRenamer(domain_name_map)(subfrag), name)
 327
 328         # Finally, collect the (now unique) subfragment domains, and merge them into our domains.
 329         for subfrag, name in self.subfragments:
 330             for domain_name, domain in subfrag.domains.items():
 331                 if domain.local:
 332                     continue
 333                 self.add_domains(domain)
 334
 335     def _propagate_domains_down(self):
 336         # For each domain defined in this fragment, ensure it also exists in all subfragments.
 337         for subfrag, name in self.subfragments:
 338             for domain in self.iter_domains():
 339                 if domain in subfrag.domains:
 340                     assert self.domains[domain] is subfrag.domains[domain]
 341                 else:
 342                     subfrag.add_domains(self.domains[domain])
 343
 344             subfrag._propagate_domains_down()
 345
 346     def _create_missing_domains(self, missing_domain, *, platform=None):
 347         from .xfrm import DomainCollector
 348
 349         collector = DomainCollector()
 350         collector(self)
 351
 352         new_domains = []
 353         for domain_name in collector.used_domains - collector.defined_domains:
 354             if domain_name is None:
 355                 continue
 356             value = missing_domain(domain_name)
 357             if value is None:
 358                 raise DomainError("Domain '{}' is used but not defined".format(domain_name))
 359             if type(value) is ClockDomain:
 360                 self.add_domains(value)
 361                 # And expose ports on the newly added clock domain, since it is added directly
 362                 # and there was no chance to add any logic driving it.
 363                 new_domains.append(value)
 364             else:
 365                 new_fragment = Fragment.get(value, platform=platform)
 366                 if domain_name not in new_fragment.domains:
 367                     defined = new_fragment.domains.keys()
 368                     raise DomainError(
 369                         "Fragment returned by missing domain callback does not define "
 370                         "requested domain '{}' (defines {})."
 371                         .format(domain_name, ", ".join("'{}'".format(n) for n in defined)))
 372                 self.add_subfragment(new_fragment, "cd_{}".format(domain_name))
 373                 self.add_domains(new_fragment.domains.values())
 374         return new_domains
 375
 376     def _propagate_domains(self, missing_domain, *, platform=None):
 377         self._propagate_domains_up()
 378         self._propagate_domains_down()
 379         self._resolve_hierarchy_conflicts()
 380         new_domains = self._create_missing_domains(missing_domain, platform=platform)
 381         self._propagate_domains_down()
 382         return new_domains
 383
 384     def _prepare_use_def_graph(self, parent, level, uses, defs, ios, top):
 385         def add_uses(*sigs, self=self):
 386             for sig in flatten(sigs):
 387                 if sig not in uses:
 388                     uses[sig] = set()
 389                 uses[sig].add(self)
 390
 391         def add_defs(*sigs):
 392             for sig in flatten(sigs):
 393                 if sig not in defs:
 394                     defs[sig] = self
 395                 else:
 396                     assert defs[sig] is self
 397
 398         def add_io(*sigs):
 399             for sig in flatten(sigs):
 400                 if sig not in ios:
 401                     ios[sig] = self
 402                 else:
 403                     assert ios[sig] is self
 404
 405         # Collect all signals we're driving (on LHS of statements), and signals we're using
 406         # (on RHS of statements, or in clock domains).
 407         for stmt in self.statements:
 408             add_uses(stmt._rhs_signals())
 409             add_defs(stmt._lhs_signals())
 410
 411         for domain, _ in self.iter_sync():
 412             cd = self.domains[domain]
 413             add_uses(cd.clk)
 414             if cd.rst is not None:
 415                 add_uses(cd.rst)
 416
 417         # Repeat for subfragments.
 418         for subfrag, name in self.subfragments:
 419             if isinstance(subfrag, Instance):
 420                 for port_name, (value, dir) in subfrag.named_ports.items():
 421                     if dir == "i":
 422                         # Prioritize defs over uses.
 423                         rhs_without_outputs = value._rhs_signals() - subfrag.iter_ports(dir="o")
 424                         subfrag.add_ports(rhs_without_outputs, dir=dir)
 425                         add_uses(value._rhs_signals())
 426                     if dir == "o":
 427                         subfrag.add_ports(value._lhs_signals(), dir=dir)
 428                         add_defs(value._lhs_signals())
 429                     if dir == "io":
 430                         subfrag.add_ports(value._lhs_signals(), dir=dir)
 431                         add_io(value._lhs_signals())
 432             else:
 433                 parent[subfrag] = self
 434                 level [subfrag] = level[self] + 1
 435
 436                 subfrag._prepare_use_def_graph(parent, level, uses, defs, ios, top)
 437
 438     def _propagate_ports(self, ports, all_undef_as_ports):
 439         # Take this fragment graph:
 440         #
 441         #    __ B (def: q, use: p r)
 442         #   /
 443         #  A (def: p, use: q r)
 444         #   \
 445         #    \_ C (def: r, use: p q)
 446         #
 447         # We need to consider three cases.
 448         #   1. Signal p requires an input port in B;
 449         #   2. Signal r requires an output port in C;
 450         #   3. Signal r requires an output port in C and an input port in B.
 451         #
 452         # Adding these ports can be in general done in three steps for each signal:
 453         #   1. Find the least common ancestor of all uses and defs.
 454         #   2. Going upwards from the single def, add output ports.
 455         #   3. Going upwards from all uses, add input ports.
 456
 457         parent = {self: None}
 458         level  = {self: 0}
 459         uses   = SignalDict()
 460         defs   = SignalDict()
 461         ios    = SignalDict()
 462         self._prepare_use_def_graph(parent, level, uses, defs, ios, self)
 463
 464         ports = SignalSet(ports)
 465         if all_undef_as_ports:
 466             for sig in uses:
 467                 if sig in defs:
 468                     continue
 469                 ports.add(sig)
 470         for sig in ports:
 471             if sig not in uses:
 472                 uses[sig] = set()
 473             uses[sig].add(self)
 474
 475         @memoize
 476         def lca_of(fragu, fragv):
 477             # Normalize fragu to be deeper than fragv.
 478             if level[fragu] < level[fragv]:
 479                 fragu, fragv = fragv, fragu
 480             # Find ancestor of fragu on the same level as fragv.
 481             for _ in range(level[fragu] - level[fragv]):
 482                 fragu = parent[fragu]
 483             # If fragv was the ancestor of fragv, we're done.
 484             if fragu == fragv:
 485                 return fragu
 486             # Otherwise, they are at the same level but in different branches. Step both fragu
 487             # and fragv until we find the common ancestor.
 488             while parent[fragu] != parent[fragv]:
 489                 fragu = parent[fragu]
 490                 fragv = parent[fragv]
 491             return parent[fragu]
 492
 493         for sig in uses:
 494             if sig in defs:
 495                 lca  = reduce(lca_of, uses[sig], defs[sig])
 496             else:
 497                 lca  = reduce(lca_of, uses[sig])
 498
 499             for frag in uses[sig]:
 500                 if sig in defs and frag is defs[sig]:
 501                     continue
 502                 while frag != lca:
 503                     frag.add_ports(sig, dir="i")
 504                     frag = parent[frag]
 505
 506             if sig in defs:
 507                 frag = defs[sig]
 508                 while frag != lca:
 509                     frag.add_ports(sig, dir="o")
 510                     frag = parent[frag]
 511
 512         for sig in ios:
 513             frag = ios[sig]
 514             while frag is not None:
 515                 frag.add_ports(sig, dir="io")
 516                 frag = parent[frag]
 517
 518         for sig in ports:
 519             if sig in ios:
 520                 continue
 521             if sig in defs:
 522                 self.add_ports(sig, dir="o")
 523             else:
 524                 self.add_ports(sig, dir="i")
 525
 526     def prepare(self, ports=None, missing_domain=lambda name: ClockDomain(name)):
 527         from .xfrm import SampleLowerer, DomainLowerer
 528
 529         fragment = SampleLowerer()(self)
 530         new_domains = fragment._propagate_domains(missing_domain)
 531         fragment = DomainLowerer()(fragment)
 532         if ports is None:
 533             fragment._propagate_ports(ports=(), all_undef_as_ports=True)
 534         else:
 535             if not isinstance(ports, tuple) and not isinstance(ports, list):
 536                 msg = "`ports` must be either a list or a tuple, not {!r}"\
 537                         .format(ports)
 538                 if isinstance(ports, Value):
 539                     msg += " (did you mean `ports=(<signal>,)`, rather than `ports=<signal>`?)"
 540                 raise TypeError(msg)
 541             mapped_ports = []
 542             # Lower late bound signals like ClockSignal() to ports.
 543             port_lowerer = DomainLowerer(fragment.domains)
 544             for port in ports:
 545                 if not isinstance(port, (Signal, ClockSignal, ResetSignal)):
 546                     raise TypeError("Only signals may be added as ports, not {!r}"
 547                                     .format(port))
 548                 mapped_ports.append(port_lowerer.on_value(port))
 549             # Add ports for all newly created missing clock domains, since not doing so defeats
 550             # the purpose of domain auto-creation. (It's possible to refer to these ports before
 551             # the domain actually exists through late binding, but it's inconvenient.)
 552             for cd in new_domains:
 553                 mapped_ports.append(cd.clk)
 554                 if cd.rst is not None:
 555                     mapped_ports.append(cd.rst)
 556             fragment._propagate_ports(ports=mapped_ports, all_undef_as_ports=False)
 557         return fragment
 558
 559
 560 class Instance(Fragment):
 561     def __init__(self, type, *args, **kwargs):
 562         super().__init__()
 563
 564         self.type        = type
 565         self.parameters  = OrderedDict()
 566         self.named_ports = OrderedDict()
 567
 568         for (kind, name, value) in args:
 569             if kind == "a":
 570                 self.attrs[name] = value
 571             elif kind == "p":
 572                 self.parameters[name] = value
 573             elif kind in ("i", "o", "io"):
 574                 self.named_ports[name] = (Value.cast(value), kind)
 575             else:
 576                 raise NameError("Instance argument {!r} should be a tuple (kind, name, value) "
 577                                 "where kind is one of \"a\", \"p\", \"i\", \"o\", or \"io\""
 578                                 .format((kind, name, value)))
 579
 580         for kw, arg in kwargs.items():
 581             if kw.startswith("a_"):
 582                 self.attrs[kw[2:]] = arg
 583             elif kw.startswith("p_"):
 584                 self.parameters[kw[2:]] = arg
 585             elif kw.startswith("i_"):
 586                 self.named_ports[kw[2:]] = (Value.cast(arg), "i")
 587             elif kw.startswith("o_"):
 588                 self.named_ports[kw[2:]] = (Value.cast(arg), "o")
 589             elif kw.startswith("io_"):
 590                 self.named_ports[kw[3:]] = (Value.cast(arg), "io")
 591             else:
 592                 raise NameError("Instance keyword argument {}={!r} does not start with one of "
 593                                 "\"a_\", \"p_\", \"i_\", \"o_\", or \"io_\""
 594                                 .format(kw, arg))