Timeline View¶

The timeline view produces a detailed report of each instruction's state transitions through an instruction pipeline. This view is enabled by the command line option -timeline. As instructions transition through the various stages of the pipeline, their states are depicted in the view report. These states are represented by the following characters:

Below is the timeline view for a subset of the dot-product example located in test/tools/llvm-mca/X86/BtVer2/dot-product.s and processed by llvm-mca using the following command:

$ llvm-mca -mtriple=x86_64-unknown-unknown -mcpu=btver2 -iterations=3 -timeline dot-product.s

Timeline view:


                    012345
Index     0123456789
[0,0]     DeeER.    .    .   vmulps   %xmm0, %xmm1, %xmm2
[0,1]     D==eeeER  .    .   vhaddps  %xmm2, %xmm2, %xmm3
[0,2]     .D====eeeER    .   vhaddps  %xmm3, %xmm3, %xmm4
[1,0]     .DeeE-----R    .   vmulps   %xmm0, %xmm1, %xmm2
[1,1]     . D=eeeE---R   .   vhaddps  %xmm2, %xmm2, %xmm3
[1,2]     . D====eeeER   .   vhaddps  %xmm3, %xmm3, %xmm4
[2,0]     .  DeeE-----R  .   vmulps   %xmm0, %xmm1, %xmm2
[2,1]     .  D====eeeER  .   vhaddps  %xmm2, %xmm2, %xmm3
[2,2]     .   D======eeeER   vhaddps  %xmm3, %xmm3, %xmm4
Average Wait times (based on the timeline view):
[0]: Executions
[1]: Average time spent waiting in a scheduler's queue
[2]: Average time spent waiting in a scheduler's queue while ready
[3]: Average time elapsed from WB until retire stage


      [0]    [1]    [2]    [3]
0.     3     1.0    1.0    3.3       vmulps   %xmm0, %xmm1, %xmm2
1.     3     3.3    0.7    1.0       vhaddps  %xmm2, %xmm2, %xmm3
2.     3     5.7    0.0    0.0       vhaddps  %xmm3, %xmm3, %xmm4


       3     3.3    0.5    1.4       <total>

The timeline view is interesting because it shows instruction state changes during execution. It also gives an idea of how the tool processes instructions executed on the target, and how their timing information might be calculated.

The timeline view is structured in two tables. The first table shows instructions changing state over time (measured in cycles); the second table (named Average Wait times) reports useful timing statistics, which should help diagnose performance bottlenecks caused by long data dependencies and sub-optimal usage of hardware resources.

An instruction in the timeline view is identified by a pair of indices, where the first index identifies an iteration, and the second index is the instruction index (i.e., where it appears in the code sequence). Since this example was generated using 3 iterations: -iterations=3, the iteration indices range from 0-2 inclusively.

Excluding the first and last column, the remaining columns are in cycles. Cycles are numbered sequentially starting from 0.

From the example output above, we know the following:

Instruction [1,0] (i.e., vmulps from iteration #1) does not have to wait in the scheduler's queue for the operands to become available. By the time vmulps is dispatched, operands are already available, and pipeline JFPU1 is ready to serve another instruction. So the instruction can be immediately issued on the JFPU1 pipeline. That is demonstrated by the fact that the instruction only spent 1cy in the scheduler's queue.

There is a gap of 5 cycles between the write-back stage and the retire event. That is because instructions must retire in program order, so [1,0] has to wait for [0,2] to be retired first (i.e., it has to wait until cycle 10).

In the example, all instructions are in a RAW (Read After Write) dependency chain. Register %xmm2 written by vmulps is immediately used by the first vhaddps, and register %xmm3 written by the first vhaddps is used by the second vhaddps. Long data dependencies negatively impact the ILP (Instruction Level Parallelism).

In the dot-product example, there are anti-dependencies introduced by instructions from different iterations. However, those dependencies can be removed at register renaming stage (at the cost of allocating register aliases, and therefore consuming physical registers).

Table Average Wait times helps diagnose performance issues that are caused by the presence of long latency instructions and potentially long data dependencies which may limit the ILP. Last row, <total>, shows a global average over all instructions measured. Note that llvm-mca, by default, assumes at least 1cy between the dispatch event and the issue event.

When the performance is limited by data dependencies and/or long latency instructions, the number of cycles spent while in the ready state is expected to be very small when compared with the total number of cycles spent in the scheduler's queue. The difference between the two counters is a good indicator of how large of an impact data dependencies had on the execution of the instructions. When performance is mostly limited by the lack of hardware resources, the delta between the two counters is small. However, the number of cycles spent in the queue tends to be larger (i.e., more than 1-3cy), especially when compared to other low latency instructions.

Bottleneck Analysis¶

The -bottleneck-analysis command line option enables the analysis of performance bottlenecks.

This analysis is potentially expensive. It attempts to correlate increases in backend pressure (caused by pipeline resource pressure and data dependencies) to dynamic dispatch stalls.

Below is an example of -bottleneck-analysis output generated by llvm-mca for 500 iterations of the dot-product example on btver2.

Cycles with backend pressure increase [ 48.07% ]
Throughput Bottlenecks:


  Resource Pressure       [ 47.77% ]


  - JFPA  [ 47.77% ]


  - JFPU0  [ 47.77% ]


  Data Dependencies:      [ 0.30% ]


  - Register Dependencies [ 0.30% ]


  - Memory Dependencies   [ 0.00% ]
Critical sequence based on the simulation:


              Instruction                         Dependency Information


 +----< 2.    vhaddps %xmm3, %xmm3, %xmm4


 |


 |    < loop carried >


 |


 |      0.    vmulps  %xmm0, %xmm1, %xmm2


 +----> 1.    vhaddps %xmm2, %xmm2, %xmm3         ## RESOURCE interference:  JFPA [ probability: 74% ]


 +----> 2.    vhaddps %xmm3, %xmm3, %xmm4         ## REGISTER dependency:  %xmm3


 |


 |    < loop carried >


 |


 +----> 1.    vhaddps %xmm2, %xmm2, %xmm3         ## RESOURCE interference:  JFPA [ probability: 74% ]

According to the analysis, throughput is limited by resource pressure and not by data dependencies. The analysis observed increases in backend pressure during 48.07% of the simulated run. Almost all those pressure increase events were caused by contention on processor resources JFPA/JFPU0.

The critical sequence is the most expensive sequence of instructions according to the simulation. It is annotated to provide extra information about critical register dependencies and resource interferences between instructions.

Instructions from the critical sequence are expected to significantly impact performance. By construction, the accuracy of this analysis is strongly dependent on the simulation and (as always) by the quality of the processor model in llvm.

Bottleneck analysis is currently not supported for processors with an in-order backend.

Extra Statistics to Further Diagnose Performance Issues¶

The -all-stats command line option enables extra statistics and performance counters for the dispatch logic, the reorder buffer, the retire control unit, and the register file.

Below is an example of -all-stats output generated by llvm-mca for 300 iterations of the dot-product example discussed in the previous sections.

Dynamic Dispatch Stall Cycles:
RAT     - Register unavailable:                      0
RCU     - Retire tokens unavailable:                 0
SCHEDQ  - Scheduler full:                            272  (44.6%)
LQ      - Load queue full:                           0
SQ      - Store queue full:                          0
GROUP   - Static restrictions on the dispatch group: 0
Dispatch Logic - number of cycles where we saw N micro opcodes dispatched:
[# dispatched], [# cycles]


 0,              24  (3.9%)


 1,              272  (44.6%)


 2,              314  (51.5%)
Schedulers - number of cycles where we saw N micro opcodes issued:
[# issued], [# cycles]


 0,          7  (1.1%)


 1,          306  (50.2%)


 2,          297  (48.7%)
Scheduler's queue usage:
[1] Resource name.
[2] Average number of used buffer entries.
[3] Maximum number of used buffer entries.
[4] Total number of buffer entries.


 [1]            [2]        [3]        [4]
JALU01           0          0          20
JFPU01           17         18         18
JLSAGU           0          0          12
Retire Control Unit - number of cycles where we saw N instructions retired:
[# retired], [# cycles]


 0,           109  (17.9%)


 1,           102  (16.7%)


 2,           399  (65.4%)
Total ROB Entries:                64
Max Used ROB Entries:             35  ( 54.7% )
Average Used ROB Entries per cy:  32  ( 50.0% )
Register File statistics:
Total number of mappings created:    900
Max number of mappings used:         35
*  Register File #1 -- JFpuPRF:


   Number of physical registers:     72


   Total number of mappings created: 900


   Max number of mappings used:      35
*  Register File #2 -- JIntegerPRF:


   Number of physical registers:     64


   Total number of mappings created: 0


   Max number of mappings used:      0

If we look at the Dynamic Dispatch Stall Cycles table, we see the counter for SCHEDQ reports 272 cycles. This counter is incremented every time the dispatch logic is unable to dispatch a full group because the scheduler's queue is full.

Looking at the Dispatch Logic table, we see that the pipeline was only able to dispatch two micro opcodes 51.5% of the time. The dispatch group was limited to one micro opcode 44.6% of the cycles, which corresponds to 272 cycles. The dispatch statistics are displayed by either using the command option -all-stats or -dispatch-stats.

The next table, Schedulers, presents a histogram displaying a count, representing the number of micro opcodes issued on some number of cycles. In this case, of the 610 simulated cycles, single opcodes were issued 306 times (50.2%) and there were 7 cycles where no opcodes were issued.

The Scheduler's queue usage table shows that the average and maximum number of buffer entries (i.e., scheduler queue entries) used at runtime. Resource JFPU01 reached its maximum (18 of 18 queue entries). Note that AMD Jaguar implements three schedulers:

The dot-product is a kernel of three floating point instructions (a vector multiply followed by two horizontal adds). That explains why only the floating point scheduler appears to be used.

A full scheduler queue is either caused by data dependency chains or by a sub-optimal usage of hardware resources. Sometimes, resource pressure can be mitigated by rewriting the kernel using different instructions that consume different scheduler resources. Schedulers with a small queue are less resilient to bottlenecks caused by the presence of long data dependencies. The scheduler statistics are displayed by using the command option -all-stats or -scheduler-stats.

The next table, Retire Control Unit, presents a histogram displaying a count, representing the number of instructions retired on some number of cycles. In this case, of the 610 simulated cycles, two instructions were retired during the same cycle 399 times (65.4%) and there were 109 cycles where no instructions were retired. The retire statistics are displayed by using the command option -all-stats or -retire-stats.

The last table presented is Register File statistics. Each physical register file (PRF) used by the pipeline is presented in this table. In the case of AMD Jaguar, there are two register files, one for floating-point registers (JFpuPRF) and one for integer registers (JIntegerPRF). The table shows that of the 900 instructions processed, there were 900 mappings created. Since this dot-product example utilized only floating point registers, the JFPuPRF was responsible for creating the 900 mappings. However, we see that the pipeline only used a maximum of 35 of 72 available register slots at any given time. We can conclude that the floating point PRF was the only register file used for the example, and that it was never resource constrained. The register file statistics are displayed by using the command option -all-stats or -register-file-stats.

In this example, we can conclude that the IPC is mostly limited by data dependencies, and not by resource pressure.

Instruction Flow¶

This section describes the instruction flow through the default pipeline of llvm-mca, as well as the functional units involved in the process.

The default pipeline implements the following sequence of stages used to process instructions.

The in-order pipeline implements the following sequence of stages: * InOrderIssue (Instruction is issued to the processor pipelines). * Retire (Instruction is retired; writes are architecturally committed).

llvm-mca assumes that instructions have all been decoded and placed into a queue before the simulation start. Therefore, the instruction fetch and decode stages are not modeled. Performance bottlenecks in the frontend are not diagnosed. Also, llvm-mca does not model branch prediction.

Instruction Dispatch¶

During the dispatch stage, instructions are picked in program order from a queue of already decoded instructions, and dispatched in groups to the simulated hardware schedulers.

The size of a dispatch group depends on the availability of the simulated hardware resources. The processor dispatch width defaults to the value of the IssueWidth in LLVM's scheduling model.

An instruction can be dispatched if:

Scheduling models can optionally specify which register files are available on the processor. llvm-mca uses that information to initialize register file descriptors. Users can limit the number of physical registers that are globally available for register renaming by using the command option -register-file-size. A value of zero for this option means unbounded. By knowing how many registers are available for renaming, the tool can predict dispatch stalls caused by the lack of physical registers.

The number of reorder buffer entries consumed by an instruction depends on the number of micro-opcodes specified for that instruction by the target scheduling model. The reorder buffer is responsible for tracking the progress of instructions that are "in-flight", and retiring them in program order. The number of entries in the reorder buffer defaults to the value specified by field MicroOpBufferSize in the target scheduling model.

Instructions that are dispatched to the schedulers consume scheduler buffer entries. llvm-mca queries the scheduling model to determine the set of buffered resources consumed by an instruction. Buffered resources are treated like scheduler resources.

Instruction Issue¶

Each processor scheduler implements a buffer of instructions. An instruction has to wait in the scheduler's buffer until input register operands become available. Only at that point, does the instruction becomes eligible for execution and may be issued (potentially out-of-order) for execution. Instruction latencies are computed by llvm-mca with the help of the scheduling model.

llvm-mca's scheduler is designed to simulate multiple processor schedulers. The scheduler is responsible for tracking data dependencies, and dynamically selecting which processor resources are consumed by instructions. It delegates the management of processor resource units and resource groups to a resource manager. The resource manager is responsible for selecting resource units that are consumed by instructions. For example, if an instruction consumes 1cy of a resource group, the resource manager selects one of the available units from the group; by default, the resource manager uses a round-robin selector to guarantee that resource usage is uniformly distributed between all units of a group.

llvm-mca's scheduler internally groups instructions into three sets:

Depending on the operands availability, instructions that are dispatched to the scheduler are either placed into the WaitSet or into the ReadySet.

Every cycle, the scheduler checks if instructions can be moved from the WaitSet to the ReadySet, and if instructions from the ReadySet can be issued to the underlying pipelines. The algorithm prioritizes older instructions over younger instructions.

Write-Back and Retire Stage¶

Issued instructions are moved from the ReadySet to the IssuedSet. There, instructions wait until they reach the write-back stage. At that point, they get removed from the queue and the retire control unit is notified.

When instructions are executed, the retire control unit flags the instruction as "ready to retire."

Instructions are retired in program order. The register file is notified of the retirement so that it can free the physical registers that were allocated for the instruction during the register renaming stage.

Load/Store Unit and Memory Consistency Model¶

To simulate an out-of-order execution of memory operations, llvm-mca utilizes a simulated load/store unit (LSUnit) to simulate the speculative execution of loads and stores.

Each load (or store) consumes an entry in the load (or store) queue. Users can specify flags -lqueue and -squeue to limit the number of entries in the load and store queues respectively. The queues are unbounded by default.

The LSUnit implements a relaxed consistency model for memory loads and stores. The rules are:

By default, the LSUnit optimistically assumes that loads do not alias (-noalias=true) store operations. Under this assumption, younger loads are always allowed to pass older stores. Essentially, the LSUnit does not attempt to run any alias analysis to predict when loads and stores do not alias with each other.

Note that, in the case of write-combining memory, rule 3 could be relaxed to allow reordering of non-aliasing store operations. That being said, at the moment, there is no way to further relax the memory model (-noalias is the only option). Essentially, there is no option to specify a different memory type (e.g., write-back, write-combining, write-through; etc.) and consequently to weaken, or strengthen, the memory model.

Other limitations are:

The LSUnit does not attempt to predict if a load or store hits or misses the L1 cache. It only knows if an instruction "MayLoad" and/or "MayStore." For loads, the scheduling model provides an "optimistic" load-to-use latency (which usually matches the load-to-use latency for when there is a hit in the L1D).

llvm-mca does not know about serializing operations or memory-barrier like instructions. The LSUnit conservatively assumes that an instruction which has both "MayLoad" and unmodeled side effects behaves like a "soft" load-barrier. That means, it serializes loads without forcing a flush of the load queue. Similarly, instructions that "MayStore" and have unmodeled side effects are treated like store barriers. A full memory barrier is a "MayLoad" and "MayStore" instruction with unmodeled side effects. This is inaccurate, but it is the best that we can do at the moment with the current information available in LLVM.

A load/store barrier consumes one entry of the load/store queue. A load/store barrier enforces ordering of loads/stores. A younger load cannot pass a load barrier. Also, a younger store cannot pass a store barrier. A younger load has to wait for the memory/load barrier to execute. A load/store barrier is "executed" when it becomes the oldest entry in the load/store queue(s). That also means, by construction, all of the older loads/stores have been executed.

In conclusion, the full set of load/store consistency rules are:

In-order Issue and Execute¶

In-order processors are modelled as a single InOrderIssueStage stage. It bypasses Dispatch, Scheduler and Load/Store unit. Instructions are issued as soon as their operand registers are available and resource requirements are met. Multiple instructions can be issued in one cycle according to the value of the IssueWidth parameter in LLVM's scheduling model.

Once issued, an instruction is moved to IssuedInst set until it is ready to retire. llvm-mca ensures that writes are committed in-order. However, an instruction is allowed to commit writes and retire out-of-order if RetireOOO property is true for at least one of its writes.

Custom Behaviour¶

Due to certain instructions not being expressed perfectly within their scheduling model, llvm-mca isn't always able to simulate them perfectly. Modifying the scheduling model isn't always a viable option though (maybe because the instruction is modeled incorrectly on purpose or the instruction's behaviour is quite complex). The CustomBehaviour class can be used in these cases to enforce proper instruction modeling (often by customizing data dependencies and detecting hazards that llvm-ma has no way of knowing about).

llvm-mca comes with one generic and multiple target specific CustomBehaviour classes. The generic class will be used if the -disable-cb flag is used or if a target specific CustomBehaviour class doesn't exist for that target. (The generic class does nothing.) Currently, the CustomBehaviour class is only a part of the in-order pipeline, but there are plans to add it to the out-of-order pipeline in the future.

CustomBehaviour's main method is checkCustomHazard() which uses the current instruction and a list of all instructions still executing within the pipeline to determine if the current instruction should be dispatched. As output, the method returns an integer representing the number of cycles that the current instruction must stall for (this can be an underestimate if you don't know the exact number and a value of 0 represents no stall).

If you'd like to add a CustomBehaviour class for a target that doesn't already have one, refer to an existing implementation to see how to set it up. Remember to look at (and add to) /llvm-mca/lib/CMakeLists.txt.