Annotations

[azidar]

Need compelling use cases for early exploration.

[jackkoenig]

Today, we had a Chisel Craft Dev meeting and annotations are very relevant to DSP in Chisel3+FIRRTL.

One important use case is range information for DSP data types. Consider the following use case:

val a = Wire(UInt(width = 4)) // Known range 0 - 10
val b = Wire(UInt(width = 4)) // Known range 0 - 10
val c = a * b // Known range 0 - 100
val d = c * c // Known range 0 - 10000

FIRRTL width inference will infer a width of 8 for c and 16 for d instead of 7 and 14 respectively. More intelligent width inference based on the actual ranges of the data is critical to creating high performance DSP circuits.

So given that the developer of a DSP library wants to be able to do this better width inference, they need a way of getting the known ranges from the Chisel code to their FIRRTL width inference pass. This is a clear case for annotations. The real question is if and if so, then how Chisel3 and FIRRTL should support annotations?

[jackkoenig]

One possible way to do this is to provide zero support for annotations in Chisel3 and FIRRTL. The library writer could then create annotation functions that map a named FIRRTL node to its annotation:

val a = Wire(UInt(width = 4))
annotateRange(a, 0, 10)

This could create a separate annotations file that is read in by the DSP width inference FIRRTL pass:

"module_name.a" -> 0 : 10

With perhaps a little bit of reflection magic, this could be handled completely by the library writer with no support from Chisel3 or FIRRTL.

This does lead to a problem in how do you annotate nodes that are not named, eg:

val b = Wire(UInt(width = 4))
b := UInt(3)

Is it possible to annotate the connect statement? Should it be?

One possible solution is to use the File Info annotation that is supported by Chisel and FIRRTL, perhaps the library writer could create some separate annotation mapping of this information. The main issue being they need to be able to independently create the same File Info data that Chisel ultimately will.

[jackkoenig]

Perhaps Chisel3 and FIRRTL should support annotations that the DSP library writer can attach to Chisel nodes that will be propagated the FIRRTL. One problem with this though is how annotations are propagated as the FIRRTL graph is transformed. If a node is transformed to another node, should it's annotations be propagated? What about if one node is split into 2 or many? Perhaps this support could be defined by the library writer and the FIRRTL compiler provides hooks to allow for custom propagation rules. I haven't been a part of the long history of Chisel development and arguments over things like this so I hope some of the more experienced developers could chime in. @azidar @jackbackrack @aswaterman @yunsup @sdtwigg @donggyukim

[azidar]

I feel annotations should be supported in the spec in the following way:

• A transformation accepts a circuit and annotation map, and produces a new circuit and rename map
• An annotation map is a list of annotations keyed by their component names
• A rename map is a list of circuit component names keyed by the old graph's component names
• A propagation takes an annotation map, a rename map, the old circuit, and the new circuit, and produces an updated annotation map
• A compiler is a sequence of transformations and propagations, ended by a backend which takes a circuit and writes to a file.

Given these definitions, we have the following properties:

• Transformations can be written in different programming languages
• Transformations are easily appended/inserted to make new compilers
• There is no complicated rules system of how annotations are propagated (an thus eliminating a huge source of potential bugs for interoperability)
• Propagations can be tailored to propagate their exact annotation
• All changes to the circuit/annotations have a clear and serializable history, so bugs can easily be found
• Invariants relating to given annotations can easily be checked (e.g. if all registers should be annotated, a propagation can always walk the graph to check this invariant).

[sdtwigg]

Whether you use an annotation map or carry the annotations along with the graph is an implementation detail. You can easily convert between one or the other. (In fact, if you think of the base hardware graph and the annotation map as tables in a database then the graph with annotations is simply an inner join on those tables.)

I don't like the claim that an annotation map 'simplifies' the problem of propagating annotations (the third bullet point). Any transformation that transforms the graph to add, remove, merge, split nodes would also have to know how to transform any annotations mapping to the original nodes in the graph. This is basically a variant of the 'Expression Problem.' In an annotation map system, you would have transformations that transform nodes without updating the map causing the map to refer to stale nodes. Similarly, you would have to serialize/deserialize the map to move between transforming programs anyway (unless you already are keeping all the information contained within one program).

A good place to start on tackling this problem would be to review how metadata and attributes work in LLVM. Essentially, most metadata is NOT guaranteed to have propagation guarantees (a transformation can drop the data) and uses of the metadata should account for this to ensure the program retains correct behavior. For example, it is OK to lose debugging symbols (although, most transformations are setup to properly propagate this and there are even special metadata nodes to provide structure to and reduce the boilerplate of this information). Range bounds are explicitly called out as an example case for metadata. They provide extra information to narrow the possible range for those identifiers. However, losing that information is recoverable because future transformations just take a more conservative estimate of the range. If this becomes problematic, you should adjust intervening transformations to be (your-)metadata-aware or move the metadata consuming transformation earlier.

The alternative is attributes, which come in various forms depending on what they are describing (function attributes, parameter attributes, etc.). However, the specification explicitly states what the attribute represents. Thus, they tend to have an influence on the behavior of the program (there are ones controlling if zero-extending or sign-extending parameters) and it is expected all transformations preserve their semantics. I group them with metadata because I consider them to be annotations that are so important, all transformations must preserve them.

It is tempting to try to solve the problem all at once (perhaps by defining a hybrid approach where you have attributes on metadata to describe how you want it propagated) but you still need to look at individual use cases to consider what possible propagation modes are interesting.

[azidar]

Whether you use an annotation map or carry the annotations along with the graph is an implementation detail. You can easily convert between one or the other. (In fact, if you think of the base hardware graph and the annotation map as tables in a database then the graph with annotations is simply an inner join on those tables.)

It isn't an implementation detail, because this would be part of the specification.

I don't like the claim that an annotation map 'simplifies' the problem of propagating annotations (the third bullet point).

That's not what the bullet says. It doesn't simplify the problem, it shifts who is responsible for solving it. Instead of a transformation needing to abide to a complicated set of rules for how annotations propagate, it simply creates a rename table. It is then the propagation pass's responsibility to update the stale annotation data.

Let's consider the example where I want to use someone else's transformation. The only thing I would need to do to propagate my annotation is to see generally what transformation is done, and write a propagation pass that updates my annotations. Let's see what happens under the following cases:

1. The transformation creates nodes that violate my annotations invariant. For example, my annotation is on every register, and a register got created. My propagation pass should have been checking for this, and gracefully error. I can then update my propagation pass to handle this case, or I decide the transformation is indeed illegal.
2. There is a bug in the propagation algorithm, and I drop an annotation. This is the worst type of bug because it is a silent failure. Eventually, I'll find the bug, and need to figure out where the annotation got dropped. Because the state of my circuit is observable between transformations, it is much easier to debug (even though I used someone else's transformation!). In general, propagation passes should be as strict as possible to limit these number of cases.
3. Transformation gives incorrect rename information. Propagation passes can look at the before and after circuits, so some cases of this can be detected. Otherwise, things will silently fail. The plus side is again, because the state of the entire compiler is easily observable between transformations, the circuits can be human inspected to help debug the transformation.

A good place to start on tackling this problem would be to review how metadata and attributes work in LLVM.

While I agree LLVM is a good starting point, just know that it is notoriously bad in that annotations can silently fail, and the most frustrating problems are debugging where the hell in the compiler your annotation got dropped. @colinschmidt and @yunsup can attest to that. My proposal makes the full state of the circuit and annotations observable between any transformation, and thus should vastly help with debugging dropped annotations.

[azidar]

See #154