[MDL] First full integration of MDL with LLVM

[reidtatge]

Summary

This is the first full integration with the mainline LLVM Repo. This will be (shortly) broken into smaller commits which focus on individual parts for review. The components roughly break down as:

• Deltas to Target library code: ~1000
• Deltas to CodeGen and MC libraries: ~2800
• New utilities: ~20000
• Documentation: ~5000

The MDL language provides an alternate way (from TableGen) to describe a target micro-architecture (ie an alternative to Schedules and Itineraries) to the CodeGen and MC libraries. It provides all the capability of Tablegen Schedules and Itineraries, but can efficiently describe much more complex processors.

You can find the RFC with more detailed descriptions of this work at discourse.llvm.org/t/rfc-mdl-a-micro-architecture-description-language-for-llvm (from Nov 2022). Detailed documentation about the design and the MDL language (and the RFC) can be found in
the repo at llvm/docs/Mdl/.

This is the first integration of work that we plan to expand going forward, and we'd like to land this to avoid bitrot and make the work
available to others. This integration is fully integrated - it can extract microarchitecture information from TableGen, create equivalent
MDL descriptions, and compile and use that information in CodeGen and MC libraries. This works for any target that has Schedules or Itineraries (AArch64, AMDGPU, AMDGPU/R600, ARM, Hexagon, Lanai, Mips, PowerPC, RISCV,
Sparc, SystemZ, and X86).

MDL support is enabled using the LLVM_ENABLE_MDL cmake parameter. When enabled, we build the MDL compiler and a tool to scrape necessary information from tablegen files, then use this information in backend libraries instead of using TableGen generated information. When not enabled (the default), all the MDL-specific code is guarded by runtime flags that disable it.

We welcome comments and suggestions, and look forward to your feedback.

[reidtatge]

It looks like I rebased with a version that includes the commit you
reverted. This is messy...

[reidtatge]

Fixed build problems

[lattner]

This is exciting! Please start a thread to discuss integrating this on the forum, this is a significant enough change and addition that I expect many folks to have opinions.

[michaelmaitland]

I am super pumped to hear more about MDL on our call later today. The thought that you've given to being able to model complex behavior is exciting!

I've given some comments and asked some questions on the documentation I've read so far. The question I keep asking myself is why we need MDL. It sounds like you've done a really thorough job of understanding what the limitations of the TableGen based scheduling constructs are, and you've presented a set of alternative constructs to address these issues. For example, you point out that forwarding is modeled between instructions and it may be more effective to model it between resources. Why don't we accomplish this using a TableGen approach?

llvm/docs/Mdl/ForwardingNetworks.md

81

Could this combination be represented by adjusting the ReadAdvance to accommodate both characteristics? For example, if a Read happens 3 cycles later in the pipeline and the input delivers its input 2 cycles sooner, can't we do this:

def : ReadAdvance<MyRead, !add(2, 3), [WriteThatGetsForwarded]>
def : ReadAdvance<MyRead, 3, [ /* All other Writes that do not get forwarded*/]>

Maybe it would be annoying to enumerate All other Writes, but I think we could modify ReadAdvance to support an exclude argument that might look something like this:

def : ReadAdvance<MyRead, !add(2, 3), [WriteThatGetsForwarded]>
def : ReadAdvance<MyRead, 3, excludeWrites=[WriteThatGetsForwarded]>

89

I am currently working on a RISCV patch that will make model forwarding by using ReadAdvances. I think I am able to represent forwarded-read and a late-operand-read for the same instruction without any modification to ReadAdvance class.

92

Are you sure that forwarding cannot be modeled for these instructions by adding ReadAdvance entries for the input operands?

98

The reason we didn't model any ReadAdvances wasn't because it was tedious, but because we weren't modeling our writes correctly in the first place. Now that we've had some time to do a better job at representing writes, we plan on implementing forwarding networks on the SiFive7 scheduler model.

99

We have found that modeling latency for vector instructions more accurately can lead to a 10% speedup on some benchmarks. I'm not sure I agree that modeling latency is not critical in this case.

117

I think this is a really nice idea. In hardware, forwarding is often property of functional units, not the instructions that run on those units.

However, it may be the case that functional unit X only forwards vector operands or only forwards scalar operands. Can we capture this behavior if we only discuss resource -> resource?

You say below:

A relatively common case would be instruction operands that are _not_ connected to the forwarding network.  We need a reasonable way to model these exceptions.

It's likely we'd use this to model the idea I present above. Can you add an example of how to model exceptions in this documentation?

206

Is there a reason why we need a new language to model the forwarding as between resources instead of between reads and writes?

[reidtatge]

Will do.

[reidtatge]

In D158790#4626610, @lattner wrote:

This is exciting! Please start a thread to discuss integrating this on the forum, this is a significant enough change and addition that I expect many folks to have opinions.

Hey Chris, there is the RFC (from last year) I mentioned in the notes above. Were you suggesting something else?

[reidtatge]

Hi Michael, responses to your questions and comments!

llvm/docs/Mdl/ForwardingNetworks.md

81

Yes, I'd agree that this is reasonably doable in tablegen doing something like what you proposed. I think the drawback of this approach is that the nodes in your forwarding network are instructions, rather than functional units, so its a very large graph. The MDL approach is to model the functional-unit-based graph, then deal with relatively rare exceptions on an instruction-by-instruction basis. So you can describe a full forwarding network with just a few lines of description.

89

Yeah, I agree you could do that, as you suggested in the earlier comment.

92

I should clarify that statement - I meant to say that tdscan can't extract forwarding information for those CPUs. Certainly you can add ReadAdvance records to any CPU. But since you have to do it for every single input operand (which usually aren't explicitly modeled at all) and annotate all the SchedWrites, its a lot of work. Forwarding networks are usually relatively simple, since they're typically based on FUs (of which there are 10's), not instructions (of which there are 1000's).

98

Cool. You might try modeling it in the MDL language too. :-)

99

Agreed. I should amend that comment to clarify the thought.

117

To answer the first question: (example vector vs scalar forwarding)
Yes, there's an easy way to model this. Functional unit X can be modeled as a "derived" or "compound" functional unit:

func_unit VECTOR:SCALAR X(...);
func_unit VECTOR Y();
func_unit SCALAR Z();

This declares that X contains both a VECTOR unit and a SCALAR unit, and the forwarding network can specify them separately. So you could say:

forward VECTOR -> VECTOR        and/or
forward SCALAR -> SCALAR         and/or
forward X -> Y

etc.

To answer the second question about exceptions:
The language currently doesn't have a method for specifying exceptions on an instruction-by-instruction basis. Our thesis is that this doesn't happen much, and can be done on a functional unit (or sub-functional-unit) basis. But we could certainly add something to the language without much trouble.

An issue that we don't address today is that its possible that a functional unit might forward just a single output value for instructions, because it only has a single connection to the forwarding network. I'm not aware of any processors that do this, but we might want to be able to manage that possibility.

206

No, this was just explaining the rationale behind the MDL language decisions.

llvm/docs/Mdl/ForwardingNetworks.md

+
+## Modeling Forwarding Networks
+
+Reid Tatge         [e-mail]
+
+
+[TOC]
+
+
+
+### Introduction
+
+To reduce the apparent latency between instructions that write and read register values, CPUs use “forwarding” networks: a set of connections between processor functional units which move data directly between the functional units, rather than routing them through a register file. This network reduces the latency between instructions running on connected units.
+
+Forwarding networks are usually not “complete”, where all functional units are connected to all other functional units.  Instead, the network typically only connects units which are physically close to each other, and in particular each unit to itself.  In practice, the network can be quite sparse. However, its worth noting that a fully connected, uniform network doesn’t have to be explicitly modeled at all.
+
+
+### Background
+
+If we want to accurately model latencies between instructions, we need to comprehend forwarding networks.  The need to accurately model latencies varies by the class of architecture we’re modeling:
+
+
+
+1. Dynamic-issue machines,
+2. Statically scheduled machines with protected pipelines,
+3. Statically scheduled machines with unprotected pipelines.
+
+We’d like to model each of these classes effectively. 
+
+The primary issue common to all three architecture classes is the need to model the behavior of instructions that can issue on more than one functional unit.  If the forwarding network is non-uniform, the effective latency can potentially be different on each candidate unit. Further, if we’re compiling for a dynamic-issue machine, we cannot statically determine which functional unit it will be issued on.  On a statically scheduled machine, we cannot determine its “final” behavior until we’ve assigned a functional unit to the instruction instance. 
+
+Here’s a more concrete example: we have two instructions _A_ and _B_.  _A_ can run on functional units _A<sub>1</sub>_ and _A<sub>2</sub>_, while _B_ can run on _B<sub>1</sub>_ or _B<sub>2</sub>_.  We have a forwarding path only between _A<sub>1</sub>_ and _B<sub>1</sub>._
+
+On a dynamic-issue machine, we _cannot_ know which unit the instructions issue on, so we can’t, with certainty, determine the latency between _A_ and _B_, so we must use a heuristic, perhaps best-case, worst-case, or some other heuristic.
+
+On a statically scheduled machine, if the instructions haven’t been assigned functional units, we similarly cannot know for certain what the latency will be. Again we must use a heuristic, but for an unprotected pipeline we must be conservative.  Another approach for this class of machine is to prune or restrict the functional unit candidates for the instructions so that we can make more accurate latency calculations.
+
+
+#### Dynamic-Issue Machines
+
+This class of machine describes most modern general-purpose microprocessors: ARM, X86, PPC, Mips, etc.  They are superscalar, multi-issue, out-of-order machines which dynamically issue and aggressively reorder the execution of instructions to avoid pipeline stalls. They typically have comprehensive forwarding networks, including full register renaming support.  Further, several of these processors decompose the exposed ISA instructions into undocumented micro-ops which are separately issued into one of several parallel pipelines. 
+
+For this class of architecture, precise modeling of the latency between pairs of instructions is at best a heuristic that is useful for motivating the order of instructions in memory, and grouping of instructions that can be issued in parallel.
+
+Note that this is not an excuse to provide an inadequate compiler model for these architectures, just an observation that it is generally impossible to provide a perfect model. We are largely just trying to help the processor do a better job. 
+
+
+#### Statically scheduled machines with protected pipelines
+
+In this machine class, instructions are issued and executed in-order, but the processor inserts stalls when the input values of an instruction are not available yet.  This includes many VLIW’s and embedded microcontrollers (including Google TPUs).
+
+For these processors, the goal is to generate code which avoids predictable stalls, and therefore we need more accurate latency information than in a dynamic-issue machine. Non-uniform forwarding networks can complicate this, so the compiler may use heuristics or a functional-unit allocation mechanism to improve the accuracy of latency calculations.
+
+
+#### Statically scheduled machines with unprotected pipelines
+
+This is a smaller class of machine where the processor has few or no hardware assists for managing latency, typically found in embedded accelerators (TI’s C6x VLIW processors, for example).
+
+For these processors, the compiler is fully responsible for ordering instructions such that all of an instruction’s inputs are available when needed by the instruction.  Although ambiguous cases are less common for this class of architecture, in those cases the compiler must make conservative assumptions about required latencies.
+
+
+### LLVM SchedModel Approach
+
+LLVM uses “Read Resources” and “Write Resources” to model each instruction’s register reads and writes.  In general, resources associated with an instruction’s operands model when the reads or writes takes place in the execution pipeline.  In the simple case, the latency between two dependent instructions can be calculated by using the difference between the write resource (in the writing instruction) and the read resource (in the reading instruction):
+
+  Latency (Instr<sub>def</sub> → Instr<sub>use</sub>) = WriteResourceLatency<sub>def</sub> - ReadAdvanceLatency<sub>use</sub> + 1
+
+The ReadAdvance latency provides an adjustment to the latency between a pair of instructions. There are generally two kinds of adjustments:
+
+
+
+1. A reduction in latency due to the presence of a forwarding network, which delivers input operands to a functional unit earlier than instruction pipeline would indicate.
+2. A reduction in latency due to an instruction reading its input operand(s) later in the pipeline than normal.
+
+We refer to these as a forwarded-read and a late-operand-read, respectively. The primary difference between these reads is that a late-operand-read latency always applies to an instruction, but a forwarded-read latency is only applied if the def instruction has a particular set of write-resource ids - ie, the value is forwarded to the read instruction.
+
+When calculating latencies between two instructions, LLVM first calculates the latency for the writing instruction, and notes the instruction’s Write Resource id. It uses the Write Resource Id to lookup the read latency adjustment in the ReadAdvance table.  The latency is then calculated as, effectively:
+
+        Latency (Inst<sub>def</sub> → Inst<sub>use</sub>) = WriteResourceLatency<sub>def</sub> - ReadAdvance<sub>use</sub>[WriteResource<sub>def</sub>]
+
+A ReadAdvance resource can optionally specify a set of write resources (ValidWrites) which indicate that the adjustment is associated with a forwarding network.  An empty ValidWrites attribute indicates a late-operand-read.  So tablegen can represent both adjustment types (described above), but it _cannot_ represent a combination of the two for a single instruction.
+
+This approach conflates the behavior of an instruction (when it reads its operands) with the latency adjustment of the forwarding network that delivers values earlier or later to an instruction.  In the MDL approach, we want to decouple these behaviors.
+
+A few more observations about the tablegen approach to latency adjustment:
+
+
+
+1. Only three targets use SchedModel forwarding (AArch64, ARM, and PPC), and only three targets (ARM, PPC, and Hexagon) use Itinerary forwarding,
+2. X86 _only _implements late-reads of operands (and has a few bugs in that logic), and no forwarding,
+3. The SchedModel forwarding implementations are very sparse.  It appears that its generally been used to “cherry-pick” a few “important” cases, and in the few CPUs that model forwarding, most instructions don’t have forwarding information associated with them,
+4.  In the few CPUs that model forwarding, the vast majority of instructions don’t have ReadAdvance entries associated with input operands.  Consequently, forwarding cannot be modeled for these instructions.
+
+Or, more generally:
+
+
+
+1. Modeling forwarding networks in tablegen is tedious, so existing implementations are sparse, resulting in uneven support for forwarding across instructions.
+2. Thats ok, since latency calculations are simply a non-critical heuristic for general-purpose processors.
+3. Trying to replicate this in the MDL language - in an automatic way (tdscan) - is difficult.
+
+
+### LLVM Itinerary Approach
+
+We don’t currently support Itinerary-based modeling.
+
+Forwarding using Itineraries is only used for ARM (A9 only), PPC (for three CPUs), and Hexagon.
+
+
+### MDL Approach
+
+The MDL approach to forwarding networks is based on a several principles:
+
+
+
+*   Each instruction (or instruction class) describes its own behavior, and may have different specified behaviors on different functional units.
+*   A forwarding network impacts the behavior of a functional unit, _not_ instructions that run on it.  Therefore it is orthogonal to the specification of instruction behaviors.
+
+This is subtly different from the LLVM approach, which conflates forwarding with the behavior of the instruction, rather than a function of the datapath.
+
+In effect, we want a latency calculation that explicitly separates the instruction behavior from the forwarding network behavior:
+
+        Latency (Inst<sub>def</sub> → Inst<sub>use</sub>) = WritePhase<sub>def</sub> - ReadPhase<sub>use</sub> + 1 - 
+
+                                                                                            ForwardingCycles[FU<sub>def</sub>, FU<sub>use</sub>]
+
+In this model, there are three factors that affect the latency between a pair of instructions:
+
+
+
+*   The pipeline phase in which the write occurs
+*   The pipeline phase in which the read occurs
+*   An adjustment made for the forwarding network between the two functional units
+
+In other words: ideally, we’d like to use instruction information (SchedWrites and ReadAdvance resources) to calculate the latency between two instructions, and then independently adjust this latency based on the presence of a forwarding path between the functional units that the two instructions execute on.
+
+From a language definition perspective, we use an approach that is tied to the description of a forwarding network as a feature of the processor datapath.  Its not an attribute of instructions or even functional units, but rather a relationship between functional units.
+
+There are several types of situations that we want to handle cleanly:
+
+
+
+1. All functional units are forwarded to all other functional units, or no forwarding is implemented.  These are essentially equivalent, and shouldn’t require any explicit modeling.
+2. The forwarding network is _nearly _uniform, or extremely sparse.  In either case, we’d like a minimum description of the network, either describing connections that exist, or describing which connections are missing.
+3. Arbitrary networks - neither sparse nor uniform.
+4. (Optional) Handle the common case where units are only forwarded to themselves.
+
+To describe a forwarding network, we need to describe each path in the network based on a CPU’s functional units.  For example:
+
+
+```
+  forward FU1 → FU1, FU2, FU3;
+```
+
+
+This asserts that results produced in FU1 are forwarded to units FU1 (itself, in this case), FU2, and FU3.The functional unit names could be functional unit template names, functional unit group names, or instance names - specifying a template or group name would include all functional units of that type (or group) in the CPU or cluster. To specify a particular instance of a functional unit, use its instance name instead:
+
+
+```
+  func_unit LOAD my_load1();
+func_unit LOAD my_load2();
+  func_unit ADD my_add1();
+  func_unit ADD my_add2();
+  forward my_load1 → my_load1, my_add1;
+  forward my_load2 → my_load2, my_add2;
+  …
+```
+
+
+This defines the network, and we’d like to be able to specify the latency adjustment for each edge in the network, which can be used, optionally, by instructions. Here’s how to do that:
+
+  `forward my_load1 → my_load1(1), my_add1(2);`
+
+This is interpreted as _my\_load1_ saving 1 cycle when forwarding to itself, and saving 2 cycles when forwarding to _my\_add1_.  Note that the adjustment could be negative numbers as well, indicating that the forwarding path is missing, resulting in longer latencies.
+
+Here’s a simple example of a forwarding network.  Each “forward” statement specifies a functional unit, and a list of units it forwards to. 
+
+  `cpu my_cpu {`
+
+
+```
+    func_unit MUL my_mul();
+    func_unit ADD my_add();
+    func_unit LOAD my_load();
+    func_unit STORE my_store();
+    func_unit BRANCH my_branch();
+
+
+  forward MUL → MUL(1), ADD(2);
+    forward ADD → ADD(1), LOAD(3);
+    forward STORE → ADD(1), MUL(2);
+}
+```
+
+
+In general, we don’t expect instruction-specific forwarding behavior on a functional unit connected to the forwarding network, so for typical cases, we expect this description to generally be sufficient to describe most architectures. However, there can be exceptions.  A relatively common case would be instruction operands that are _not_ connected to the forwarding network.  We need a reasonable way to model these exceptions. 
+
+
+#### Representation of the network
+
+Each CPU has a specific number of functional units it implements.  The basic representation is simply a 2-dimensional adjacency matrix, with the edges annotated with the latency adjustment. Although we expect the network to be sparse (or empty), we need this to be fast, so we’ll use a “dense” representation, since the sizes involved are rather small.  A typical processor has fewer than  a dozen functional units, so we can use a simple 2-dimensional array of signed chars to represent the graph, and positive or negative latency adjustments.
+
+
+#### Extracting the forwarding network from SchedModels with TdScan
+
+Since SchedModel descriptions tend to conflate forwarding with instructions that read operands in later pipeline phases, we want to separate these two concerns when we generate an MDL description.  Our fundamental assumption is that forwarding to a functional unit has the same behavior for all instructions that run on that functional unit: the value is delivered to the unit some number of cycles - typically 1 - earlier than if the forwarding path wasn’t implemented. 
+
+So our first step is to extract the forwarding network using the ReadAdvance records associated with forwarding information (the ones that have ValidWrites).  Using this information, we can generate a graph of forwarding latencies between every pair of instructions, and derive the overall forwarding graph.
+
+So the approach we use in TdScan is that we use the forwarding information to find the minimal forwarding path between every pair of units, then use that information to inform the forwarding benefit for all instructions that execute on the receiving unit.   In very rare cases in current targets, the forwarding latency specified in tablegen is negative. Which we could interpret as an “early operand read” for the involved instructions. 
+
+So given our desired formula for calculating latency:
+
+        Latency (Inst<sub>def</sub> → Inst<sub>use</sub>) = WriteLatency<sub>def</sub> - ReadLatency<sub>use</sub> + 1 - 
+
+                                                                                            ForwardingCycles[FU<sub>def</sub>, FU<sub>use</sub>]
+
+We first calculate ForwardingCycles for each pair of functional units described in tablegen.  When generating latency records for ReadAdvance resources which have ValidUnits, we decrement the ReadAdvance amount by the calculated ForwardingCycles for that forwarding path. This can be a little complicated, so lets start with a simple case.
+
+If we have an instruction ABC running on “UnitA” which has a ReadAdvance with a cycle count of 1, and has forwarding paths from “UnitB”, “UnitC”, and “UnitD”, each with a forwarding latency to “UnitA” of 1.  In this case, we don’t need to generate the explicit “use” reference of 1, since it is subsumed by the forwarding adjustment. 
+
+For a more complicated case, say we have an instruction FMA running on “UnitA” which has a ReadAdvance with a cycle count of 4, and has forwarding paths from “UnitB” and “UnitC”, and we have the following forwarding graph:
+
+    UnitB forwards to UnitA with cycles= &lt;1, 4>
+
+    UnitC forwards to UnitA with cycles= &lt;2, 4>
+
+The &lt;1, 4> notation implies that some instructions asserted that the forwarding latency between B and A was 1, and some instructions (such as FMA) asserted it was 4.  Our first observation is that this doesn’t necessarily make sense - the forwarding path either exists or it doesn’t, and it shouldn’t be different for different instructions.  This is (I believe) an artifact of the LLVM approach of conflating “late operand reads” with “forwarding cycles”.  In this case, (for UnitB to UnitA), we split the 4 cycle latency between forwarding (1 cycle) and late operand reads (3 cycles), and generate a “use” record with a 3-cycle latency.  
+
+Our second observation is that since UnitC has a different forwarding latency than UnitB, we don’t have a single convenient way of describing the latency of the FMA instruction wrt both forwarding paths.
+
+The last observation is that most instructions do not have any LLVM forwarding information associated with them.  We also need to differentiate between ReadAdvances used for late-operand reads, and those used to represent forwarding.   Differentiating late-operand-reads from forwarding reads requires some explicit way of annotating which is which in the generated description.  There are three cases here (no forwarding info, late-operand-read, and forwarding read), and we need a way to communicate the three cases.
+
+In the case there is no forwarding information provided for an instruction, we need to _not_ model forwarding information for these instructions, assuming we want to match LLVM’s behavior.
+
+There’s an easy solution: instructions which don’t have input operand read resources also don’t use forwarding information.  This is perhaps inaccurate, but we can match llvm’s behavior.
+
+There are a few approaches to differentiating between late-operand-reads and forwarding reads, none of them are ideal.  If we want to match LLVM’s behavior exactly, we would also have to annotate references that _don’t _use forwarding, but _do _have explicit references.
+
+The current approach that we’ve implemented is to treat all ReadAdvances as late-operand-reads.  This produces a “best-case” latency calculation, since we assume the operand is always read late.  Note that a number of architectures (like X86, RISCV) don’t model _any_ forwarding, but only model late-read-operands. In other words, their heuristic is to assume a best-case latency. This isn’t an unreasonable approach, particularly if the target machine has a fully-connected, uniform forwarding network.
+
+Bottom line, we have forwarding support in the MDL language, but because of the incomplete and/or conflated operand reads in tablegen, its not easy to translate an LLVM description into MDL in a reasonable way.  
+