[llvm-dev] [RFC] llvm-mca: a static performance analysis tool

Philip Reames via llvm-dev llvm-dev at lists.llvm.org
Fri Mar 2 09:33:37 PST 2018


This looks absolutely awesome.  Thank you for sharing your work; I can 
see many ways this will be useful.

Philip


On 03/01/2018 09:22 AM, Andrea Di Biagio via llvm-dev wrote:
> Hi all,
>
> At Sony we developed an LLVM based performance analysis tool named 
> llvm-mca. We
> currently use it internally to statically measure the performance of 
> code, and
> to help triage potential problems with target scheduling models.  We 
> decided to
> post this RFC because we are interested in the feedback from the 
> community, and
> we also believe that other people might be interested in a tool like this.
>
> llvm-mca uses information which is already available in LLVM (e.g. 
> scheduling
> models) to statically measure the performance of machine code in a 
> specific cpu.
> Performance is measured in terms of throughput as well as processor 
> resource
> consumption.  The tool currently works for processors with an out-of-order
> backend, for which there is a scheduling model available in LLVM.
>
> The main goal of this tool is not just to predict the performance of 
> the code
> when run on the target, but also help with diagnosing potential 
> performance
> issues.
>
> Given an assembly code sequence, llvm-mca estimates the IPC 
> (instructions per
> cycle), as well as hardware resources pressure. The analysis and 
> reporting style
> were inspired by the IACA tool from Intel.
>
> The presence of long data dependency chains, as well as poor usage of 
> hardware
> resources may lead to bottlenecks in the back-end.  The tool is able 
> to generate
> a detailed report which should help with identifying and analyzing 
> sources of
> bottlenecks.
>
> Scheduling models are mostly used to compute instruction latencies, to 
> obtain
> read-advance information, and understand how processor resources are 
> used by
> instructions.  By design, the quality of the performance analysis 
> conducted by
> the tool is inevitably affected by the quality of the target 
> scheduling models.
>
> However, scheduling models intentionally do not describe all 
> processors details,
> since the goal is just to enable the scheduling of machine 
> instructions during
> compilation. That means, there are processor details which are not 
> important for
> the purpose of scheduling instructions (and therefore not described by the
> scheduling model), but are very important for this tool.
>
> A few examples of details that are missing in scheduling models are:
>  - Maximum number of instructions retired per cycle.
>  - Actual dispatch width (it often differs from the issue width).
>  - Number of temporary registers available for renaming.
>  - Number of read/write ports in the register file(s).
>  - Length of the load/store queue in the LSUnit.
>
> It is also very difficult to find a "good" abstract model to describe the
> behavior of out-of-order processors. So, we have to keep in mind that 
> all of
> these aspects are going to affect the quality of the static analysis 
> performed
> by the tool.
>
> An extensive list of known limitations is reported in one of the last 
> sections
> of this document. There is also a section related to design problems 
> which must
> be addressed (hopefully with the help of the community).  At the 
> moment, the
> tool has been mostly tested for x86 targets, but there are still several
> limitations, some of which could be overcome by integrating extra 
> information
> into the scheduling models.
>
> As was mentioned before, this tool has been (and is still being) used 
> internally
> in Sony to debug/triage issues in the btver2 scheduling model. We have 
> also
> tested it on other targets to check how generic the tool is. In our 
> experience,
> the tool makes it easy to identify simple mistakes like "wrong number 
> of micro
> opcodes specified for an instruction", or "wrong set of hardware 
> resources".
> Some of these mistakes are quite common (sometimes on mature models 
> too), and
> often difficult to catch.  Reports generated by this tool are simple 
> to analyze,
> and contain enough details to help triage most performance problems.
>
> 1. How the tool works
> ---------------------
>
> The tool takes assembly code as input. Assembly code is parsed into a 
> sequence
> of MCInst with the help of the existing LLVM target assembly parsers. 
> The parsed
> sequence of MCInst is then analyzed by a 'Backend' module to generate a
> performance report.
>
> The Backend module internally emulates the execution of the machine code
> sequence in a loop of iterations (which by default is 70). At the end 
> of this
> process, the backend collects a number of statistics which are then 
> printed out
> in the form of a report.
>
> Here is an example of performance report generated by the tool for a 
> dot-product
> of two packed float vectors of four elements. The analysis is 
> conducted for
> target x86, cpu btver2:
>
> ///////////////////
>
> Iterations:     300
> Instructions:   900
> Total Cycles:   610
> Dispatch Width: 2
> IPC:            1.48
>
>
> Resources:
> [0] - JALU0
> [1] - JALU1
> [2] - JDiv
> [3] - JFPM
> [4] - JFPU0
> [5] - JFPU1
> [6] - JLAGU
> [7] - JSAGU
> [8] - JSTC
> [9] - JVIMUL
>
>
> Resource pressure per iteration:
> [0]    [1]    [2]    [3]    [4]    [5]    [6]    [7]    [8] [9]
>  -      -      -      -     2.00   1.00    -      -      - -
>
> Resource pressure by instruction:
> [0]    [1]    [2]    [3]    [4]    [5]    [6]    [7]    [8] [9]        
> Instructions:
>  -      -      -      -      -     1.00    -      -      - -         
> vmulps    %xmm0, %xmm1, %xmm2
>  -      -      -      -     1.00    -      -      -      - -         
> vhaddps    %xmm2, %xmm2, %xmm3
>  -      -      -      -     1.00    -      -      -      - -         
> vhaddps    %xmm3, %xmm3, %xmm4
>
>
> Instruction Info:
> [1]: #uOps
> [2]: Latency
> [3]: RThroughput
> [4]: MayLoad
> [5]: MayStore
> [6]: HasSideEffects
>
> [1]    [2]    [3]    [4]    [5]    [6]    Instructions:
>  1      2     1.00                        vmulps    %xmm0, %xmm1, %xmm2
>  1      3     1.00                        vhaddps    %xmm2, %xmm2, %xmm3
>  1      3     1.00                        vhaddps    %xmm3, %xmm3, %xmm4
>
> ///////////////////
>
> According to this report, the dot-product kernel has been executed 300 
> times,
> for a total of 900 instructions dynamically executed.
>
> The report is structured in three main sections.  A first section 
> collects a few
> performance numbers; the goal of this section is to give a very quick 
> overview
> of the performance throughput. In this example, the two important 
> perforamce
> indicators are a) the predicted total number of cycles, and b) the IPC.
> IPC is probably the most important throughput indicator. A big delta 
> between the
> Dispatch Width and the computed IPC is an indicator of potential 
> performance
> issues.
>
> The second section is the so-called "resource pressure view". This 
> view reports
> the average number of resource cycles consumed every iteration by 
> instructions
> for every processor resource unit available on the target. Information is
> structured in two tables. The first table reports the number of 
> resource cycles
> spent on average every iteration. The second table correlates the resource
> cycles to the machine instruction in the sequence. For example, every 
> iteration
> of the dot-product, instruction 'vmulps' always executes on resource 
> unit [5]
> (JFPU1 - floating point pipeline #1), consuming an average of 1 
> resource cycle
> per iteration.  Note that on Jaguar, vector FP multiply can only be 
> issued to
> pipeline JFPU1, while horizontal FP adds can only be issued to 
> pipeline JFPU0.
>
> The third (and last) section of the report shows the latency and 
> reciprocal
> throughput of every instruction in the sequence. That section also 
> reports extra
> information related to the number of micro opcodes, and opcode 
> properties (i.e.
> 'MayLoad', 'MayStore' and 'UnmodeledSideEffects').
>
> The resource pressure view helps with identifying bottlenecks caused 
> by high
> usage of specific hardware resources.  Situations with resource 
> pressure mainly
> concentrated on a few resources should, in general, be avoided. Ideally,
> pressure should be uniformly distributed between multiple resources.
>
> Timeline View
> -------------
>
> A detailed report of each instruction's state transitions over time can be
> enabled using the command line flag '-timeline'.  This prints an extra 
> section
> in the report which contains the so-called "timeline view". Below is the
> timeline view for the dot-product example from the previous section.
>
> ///////////////
> 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
> ///////////////
>
> The timeline view is very interesting because it shows how 
> instructions changed
> in state during execution.  It also gives an idea of how the tool "sees"
> instructions executed on the target.
>
> The timeline view is structured in two tables.  The first table shows how
> instructions change in 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 actual
> instruction index (i.e. where it appears in the code sequence).
>
> Excluding the first and last column, the remaining columns are in 
> cycles.  Cycles
> are numbered sequentially starting from 0.  The following characters 
> are used to
> describe the state of an instruction:
>
>  D : Instruction dispatched.
>  e : Instruction executing.
>  E : Instruction executed.
>  R : Instruction retired.
>  = : Instruction already dispatched, waiting to be executed.
>  - : Instruction executed, waiting to be retired.
>
> Based on the timeline view from the example, we know that:
>   - Instruction [1, 0] was dispatched at cycle 1.
>   - Instruction [1, 0] started executing at cycle 2.
>   - Instruction [1, 0] reached the write back stage at cycle 4.
>   - Instruction [1, 0] was retired at cycle 10.
>
> Instruction [1, 0] (i.e. the vmulps from iteration #1) doesn't have to 
> wait in
> the scheduler's queue for the operands to become available. By the 
> time the
> 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 unti cycle 10).
>
> In the dot-product example, all instructions are in a RAW (Read After 
> Write)
> dependency chain.  Register %xmm2 written by the 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 affect 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 temporary 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.  Note that the tool 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.  So the difference between the two counters is a good
> indicator of how big of an impact data dependencies had on the 
> execution of
> 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 bigger (i.e. more than 1-3cy) 
> especially
> when compared with other low latency instructions.
>
> Extra statistics to further diagnose performance issues.
> --------------------------------------------------------
>
> Flag '-verbose' 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 verbose output generated by the tool for the 
> dot-product
> example discussed in the previous sections.
>
> ///////////////////
> Iterations:     300
> Instructions:   900
> Total Cycles:   610
> Dispatch Width: 2
> IPC:            1.48
>
>
> Dynamic Dispatch Stall Cycles:
> RAT     - Register unavailable:                      0
> RCU     - Retire tokens unavailable:                 0
> SCHEDQ  - Scheduler full:                            272
> LQ      - Load queue full:                           0
> SQ      - Store queue full:                          0
> GROUP   - Static restrictions on the dispatch group: 0
>
>
> Register Alias Table:
> Total number of mappings created: 900
> Max number of mappings used:      35
>
>
> Dispatch Logic - number of cycles where we saw N instructions dispatched:
> [# dispatched], [# cycles]
>  0,              24  (3.9%)
>  1,              272  (44.6%)
>  2,              314  (51.5%)
>
>
> Schedulers - number of cycles where we saw N instructions issued:
> [# issued], [# cycles]
>  0,          7  (1.1%)
>  1,          306  (50.2%)
>  2,          297  (48.7%)
>
>
> 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%)
>
>
> Scheduler's queue usage:
> JALU01,  0/20
> JFPU01,  18/18
> JLSAGU,  0/12
> ///////////////////
>
> Based on the verbose report, the backend was only able to dispatch two
> instructions 51.5% of the time.  The dispatch group was limited to one
> instruction 44.6% of the cycles, which corresponds to 272 cycles.
>
> If we look at section "Dynamic Dispatch Stall Cycles", we can see how 
> counter
> SCHEDQ reports 272 cycles.  Counter SCHEDQ is incremented every time 
> the dispatch
> logic is unable to dispatch a full group of two instructions because the
> scheduler's queue is full.
>
> Section "Scheduler's queue usage" shows how the maximum number of 
> buffer entries
> (i.e. scheduler's queue entries) used at runtime for resource JFPU01 
> reached its
> maximum. Note that AMD Jaguar implements three schedulers:
>   * JALU01 - A scheduler for ALU instructions
>   * JLSAGU - A scheduler for address generation
>   * JFPU01 - A scheduler floating point operations.
>
> 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 according to section "Scheduler's queue
> usage".
>
> A full scheduler's 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.
>
> In this example, we can conclude that the IPC is mostly limited by data
> dependencies, and not by resource pressure.
>
> LLVM-MCA instruction flow
> -------------------------
>
> This section describes the instruction flow through the out-of-order 
> backend, as
> well as the functional units involved in the process.
>
> An instruction goes through a default sequence of stages:
>     - Dispatch (Instruction is dispatched to the schedulers).
>     - Issue (Instruction is issued to the processor pipelines).
>     - Write Back (Instruction is executed, and results are written back).
>     - Retire (Instruction is retired; writes are architecturally 
> committed).
>
> The tool only models the out-of-order portion of a processor. 
> Therefore, the
> instruction fetch and decode stages are not modeled. Performance 
> bottlenecks in
> the frontend are not diagnosed by this tool.  The tool assumes that 
> instructions
> have all been decoded and placed in a queue.  Also, the tool doesn't know
> anything about 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 hardware
> schedulers.  The dispatch logic is implemented by class DispatchUnit 
> in file
> Dispatch.h.
>
> The size of a dispatch group depends on the availability of hardware 
> resources,
> and it cannot exceed the value of field 'DispatchWidth' in class 
> DispatchUnit.
> Note that field DispatchWidth defaults to the value of field 
> 'IssueWidth' from
> the scheduling model.
>
> Users can override the DispatchWidth value with flag "-dispatch=<N>" 
> (where 'N'
> is an unsigned quantity).
>
> An instruction can be dispatched if:
>  - The size of the dispatch group is smaller than DispatchWidth
>  - There are enough entries in the reorder buffer
>  - There are enough temporary registers to do register renaming
>  - Schedulers are not full.
>
> Scheduling models don't describe register files, and therefore the 
> tool doesn't
> know if there is more than one register file, and how many temporaries are
> available for register renaming.
>
> By default, the tool (optimistically) assumes a single register file 
> with an
> unbounded number of temporary registers.  Users can limit the number of
> temporary registers available for register renaming using flag
> `-register-file-size=<N>`, where N is the number of temporaries.  A 
> value of
> zero for N means 'unbounded'.  Knowing how many temporaries are 
> available for
> register renaming, the tool can predict dispatch stalls caused by the 
> lack of
> temporaries.
>
> The number of reorder buffer entries consumed by an instruction 
> depends on the
> number of micro-opcodes it specifies in the target scheduling model 
> (see field
> 'NumMicroOpcodes' of tablegen class ProcWriteResources and its derived 
> classes;
> TargetSchedule.td).
>
> The reorder buffer is implemented by class RetireControlUnit (see 
> Dispatch.h).
> Its goal is to track the progress of instructions that are 
> "in-flight", and
> retire instructions in program order.  The number of entries in the 
> reorder
> buffer defaults to the value of field 'MicroOpBufferSize' from the target
> scheduling model.
>
> Instructions that are dispatched to the schedulers consume scheduler 
> buffer
> entries.  The tool queries the scheduling model to figure out the set of
> buffered resources consumed by an instruction.  Buffered resources are 
> treated
> like "scheduler" resources, and the field 'BufferSize' (from the processor
> resource tablegen definition) defines the size of the scheduler's queue.
>
> Zero latency instructions (for example NOP instructions) don't consume 
> scheduler
> resources.  However, those instructions still reserve a number of 
> slots in the
> reorder buffer.
>
> Instruction Issue
> -----------------
>
> As mentioned in the previous section, each scheduler resource 
> implements a queue
> of instructions.  An instruction has to wait in the scheduler's queue 
> 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) to a pipeline for execution.
>
> Instruction latencies can be computed by the tool with the help of the
> scheduling model; latency values are defined by the scheduling model 
> through
> ProcWriteResources objects.
>
> Class Scheduler (see file Scheduler.h) knows how to emulate multiple 
> processor
> schedulers.  A Scheduler is responsible for tracking data 
> dependencies, and
> dynamically select which processor resources are consumed/used by 
> instructions.
>
> Internally, the Scheduler class delegates the management of processor 
> resource
> units and resource groups to the ResourceManager class. 
> ResourceManager is also
> responsible for selecting resource units that are effectively consumed by
> instructions.  For example, if an instruction consumes 1cy of a 
> resource group,
> the ResourceManager object selects one of the available units from the 
> group; by
> default, it uses a round-robin selector to guarantee that resource 
> usage is
> uniformly distributed between all units of a group.
>
> Internally, class Scheduler implements three instruction queues:
>   - WaitQueue: a queue of instructions whose operands are not ready yet.
>   - ReadyQueue: a queue of instructions ready to execute.
>   - IssuedQueue: a queue of instructions executing.
>
> Depending on the operands availability, instructions that are 
> dispatched to the
> Scheduler are either placed into the WaitQueue or into the ReadyQueue.
>
> Every cycle, class Scheduler checks if instructions can be moved from the
> WaitQueue to the ReadyQueue, and if instructions from the ReadyQueue 
> can be
> issued to the underlying pipelines.  The algorithm prioritizes older
> instructions over younger instructions.
>
> Objects of class ResourceState (see Scheduler.h) describe processor 
> resources.
> There is an instance of class ResourceState for each single processor 
> resource
> specified by the scheduling model.  A ResourceState object for a processor
> resource with multiple units dynamically tracks the availability of 
> every single
> unit.  For example, the ResourceState of a resource group tracks the
> availability of every resource in that group.  Internally, ResourceState
> implements a round-robin selector to dynamically pick the next unit to 
> use from
> the group.
>
> Write-Back and Retire Stage
> ---------------------------
>
> Issued instructions are moved from the ReadyQueue to the IssuedQueue.  
> 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.
>
> On the event of "instruction executed", the retire control unit flags the
> instruction as "ready to retire".
>
> Instruction are retired in program order; an "instruction retired" 
> event is sent
> to the register file which frees the temporary registers allocated for the
> instruction at register renaming stage.
>
> Load/Store Unit and Memory Consistency Model
> --------------------------------------------
>
> The tool attempts to emulate out-of-order execution of memory 
> operations.  Class
> LSUnit (see file LSUnit.h) emulates a load/store unit implementing 
> queues for
> speculative execution of loads and stores.
>
> Each load (or store) consumes an entry in the load (or store) queue.  
> The number
> of slots in the load/store queues is unknown by the tool, since there 
> is no
> mention of it in the scheduling model.  In practice, users can specify 
> flag
> `-lqueue=N` (vic. `-squeue=N`) to limit the number of entries in the 
> queue to be
> equal to exactly N (an unsigned value). If N is zero, then the tool 
> assumes an
> unbounded queue (this is the default).
>
> LSUnit implements a relaxed consistency model for memory loads and 
> stores. The
> rules are:
> 1) A younger load is allowed to pass an older load only if there is no
>    intervening store in between the two loads.
> 2) An younger store is not allowed to pass an older store.
> 3) A younger store is not allowed to pass an older load.
> 4) A younger load is allowed to pass an older store provided that the 
> load does
>    not alias with the store.
>
> By default, this class conservatively (i.e. pessimistically) assumes 
> that loads
> always may-alias store operations.  Essentially, this LSUnit doesn't 
> perform any
> sort of alias analysis to rule out cases where loads and stores don't 
> overlap
> with each other.  The downside of this approach however is that 
> younger loads are
> never allowed to pass older stores.  To make it possible for a younger 
> load to
> pass an older store, users can use the command line flag -noalias.  Under
> 'noalias', a younger load is always allowed to pass an older store.
>
> Note that, in the case of write-combining memory, rule 2. could be 
> relaxed a bit
> to allow reordering of non-aliasing store operations.  That being 
> said, at the
> moment, there is no way to further relax the memory model (flag 
> -noalias is the
> only option).  Essentially, there is no option to specify a different 
> memory
> type (for example: write-back, write-combining, write-through; etc.) and
> consequently to weaken or strengthen the memory model.
>
> Other limitations are:
>  * LSUnit doesn't know when store-to-load forwarding may occur.
>  * LSUnit doesn't know anything about the cache hierarchy and memory 
> types.
>  * LSUnit doesn't know how to identify serializing operations and 
> memory fences.
>
> No assumption is made on the store buffer size.  As mentioned before, 
> LSUnit
> conservatively assumes a may-alias relation between loads and stores, 
> and it
> doesn't attempt to identify cases where store-to-load forwarding would 
> occur in
> practice.
>
> LSUnit doesn't attempt to predict whether 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).
>
> Class MCInstrDesc in LLVM doesn't know about serializing operations, nor
> memory-barrier like instructions.  LSUnit conservatively assumes that an
> instruction which has both 'MayLoad' and 'UnmodeledSideEffects' 
> behaves like a
> "soft" load-barrier.  That means, it serializes loads without forcing 
> a flush of
> the load queue.  Similarly, instructions flagged with both 'MayStore' and
> 'UnmodeledSideEffects' are treated like store barriers.  A full memory 
> barrier
> is a 'MayLoad' and 'MayStore' instruction with 
> 'UnmodeledSideEffects'.  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 the older loads/stores have been 
> executed.
>
> In conclusion the full set of rules is:
>   1. A store may not pass a previous store.
>   2. A load may not pass a previous store unless flag 'NoAlias' is set.
>   3. A load may pass a previous load.
>   4. A store may not pass a previous load (regardless of flag 'NoAlias').
>   5. A load has to wait until an older load barrier is fully executed.
>   6. A store has to wait until an older store barrier is fully executed.
>
> Known limitations
> -----------------
> Previous sections described cases where the tool is missing 
> information to give
> an accurate report.  For example, the first sections of this document 
> explained
> how the lack of knowledge about the processor negatively affects the 
> performance
> analysis.  The lack of knowledge is often a consequence of how 
> scheduling models
> are defined; as mentioned before, scheduling models intentionally 
> don't describe
> processors in fine details.
>
> The accuracy of the performance analysis is also affected by 
> assumptions made by
> the processor model used by the tool.
>
> Most recent Intel and AMD processors implement dedicated 
> LoopBuffer/OpCache in
> the hardware frontend to speedup the throughput in the presence of 
> tight loops.
> The presence of these buffers complicates the decoding logic, and requires
> knowledge on the branch predictor too.  Class 'SchedMachineModel' in 
> tablegen
> provides a field named 'LoopMicroOpBufferSize' which is used to 
> describe loop
> buffers.  However, the purpose of that field is to enable loop 
> unrolling of
> tight loops; essentially, it affects the cost model used by pass 
> loop-unroll.
>
> By design, the tool only cares about the out-of-order portion of a 
> processor,
> and consequently doesn't try to predict the frontend throughput.  
> Processors may
> implement complex decoding schemes; statically predicting the frontend
> throughput is in general beyond the scope of this tool.  For the same 
> reasons,
> this tool intentionally doesn't model branch prediction.  That being 
> said, this
> tool could be definitely extended in future to also account for the 
> hardware
> frontend when doing performance analysis.  This would inevitably 
> require extra
> (extensive) processor knowledge related to all the available decoding 
> paths in
> the hardware frontend.
>
> When computing the IPC, the tool assumes a zero-latency "perfect" 
> fetch&decode
> stage; the full sequence of decoded instructions is immediately 
> visible to the
> dispatch logic from the start.
>
> The tool doesn't know about simultaneous mutithreading. According to 
> the tool,
> processor resources are not statically/dynamically partitioned. Processor
> resources are fully available to the hardware thread executing the
> microbenchmark.
>
> The execution model implemented by this tool assumes that instructions are
> firstly dispatched in groups to hardware schedulers, and then issued to
> pipelines for execution.  The model assumes dynamic scheduling of 
> instructions.
> Instructions are placed in a queue and potentially executed 
> out-of-order (based
> on the operand availability). The dispatch stage is definitely 
> distinct from the
> issue stage.
>
> This model doesn't correctly describe processors where the 
> dispatch/issue is a
> single stage. This is what happens for example in VLIW processors, where
> instructions are packaged and statically scheduled at compile time; it 
> is up to
> the compiler to predict the latency of instructions and package issue 
> groups
> accordingly. For such targets, there is no dynamic scheduling done by the
> hardware.
>
> Existing classes (DispatchUnit, Scheduler, etc.) could be 
> extended/adapted to
> support processors with a single dispatch/issue stage. The execution 
> flow would
> require some changes in the way how existing components (i.e. 
> DispatchUnit,
> Scheduler, etc.) interact. This can be a future development.
>
> The following sections describes other known limitations.  The goal is 
> not to
> provide an extensive list of limitations; we want to report what we 
> believe are
> the most important limitations, and suggest possible methods to 
> overcome them.
>
> Load/Store barrier instructions and serializing operations
> ----------------------------------------------------------
> Section "Load/Store Unit and Memory Consistency Model" already 
> mentioned how
> LLVM doesn't know about serializing operations and memory barriers.  
> Most of it
> boils down to the fact that class MCInstrDesc (intentionally) doesn't 
> expose
> those properties.  Instead, both serializing operations and memory 
> barriers
> "have side-effects" according to MCInstrDesc.  That is because, at 
> least for
> scheduling purposes, knowing that an instruction has unmodeled side 
> effects is
> often enough to treat the instruction like a compiler scheduling barrier.
>
> A performance analysis tool could use the extra knowledge on barriers and
> serializing operations to generate a more accurate performance 
> report.  One way
> to improve this is by reserving a couple of bits in field 'Flags' from 
> class
> MCInstrDesc: one bit for barrier operations, and another bit to mark
> instructions as serializing operations.
>
> Lack of support for instruction itineraries
> -------------------------------------------
> The current version of the tool doesn't know how to process instruction
> itineraries.  This is probably one of the most important limitations, 
> since it
> affects a few out-of-order processors in LLVM.
>
> As mentioned in section 'Instruction Issue', class Scheduler delegates 
> to an
> instance of class ResourceManager the handling of processor resources.
> ResourceManager is where most of the scheduling logic is implemented.
>
> Adding support for instruction itineraries requires that we teach
> ResourceManager how to handle functional units and instruction 
> stages.  This
> development can be a future extension, and it would probably require a few
> changes to the ResourceManager interface.
>
> Instructions that affect control flow are not correctly modeled
> ---------------------------------------------------------------
> Examples of instructions that affect the control flow are: return, 
> indirect
> branches, calls, etc.  The tool doesn't try to predict/evaluate branch 
> targets.
> In particular, the tool doesn't model any sort of branch prediction, 
> nor does it
> attempt to track changes to the program counter.  The tool always 
> assumes that
> the input assembly sequence is the body of a microbenchmark (a simple loop
> executed for a number of iterations). The "next" instruction in 
> sequence is
> always the next instruction to dispatch.
>
> Call instructions default to an arbitrary high latency of 100cy. A 
> warning is
> generated if the tool encounters a call instruction in the sequence.  
> Return
> instructions are not evaluated, and therefore control flow is not 
> affected.
> However, the tool still queries the processor scheduling model to 
> obtain latency
> information for instructions that affect the control flow.
>
> Possible extensions to the scheduling model
> -------------------------------------------
> Section "Instruction Dispatch" explained how the tool doesn't know 
> about the
> register files, and temporaries available in each register file for 
> register
> renaming purposes.
>
> The LLVM scheduling model could be extended to better describe 
> register files.
> Ideally, scheduling model should be able to define:
>  - The size of each register file
>  - How many temporary registers are available for register renaming
>  - How register classes map to register files
>
> The scheduling model doesn't specify the retire throughput (i.e. how many
> instructions can be retired every cycle).  Users can specify flag
> `-max-retire-per-cycle=<uint>` to limit how many instructions the 
> retire control
> unit can retire every cycle.  Ideally, every processor should be able 
> to specify
> the retire throughput (for example, by adding an extra field to the 
> scheduling
> model tablegen class).
>
> Known limitations on X86 processors
> -----------------------------------
>
> 1) Partial register updates versus full register updates.
>
> On x86-64, a 32-bit GPR write fully updates the super-register. Example:
>       add %edi %eax    ## eax += edi
>
> Here, register %eax aliases the lower half of 64-bit register %rax. On 
> x86-64,
> register %rax is fully updated by the 'add' (the upper half of %rax is 
> zeroed).
> Essentially, it "kills" any previous definition of (the upper half of) 
> register
> %rax.
>
> On the other hand, 8/16 bit register writes only perform a so-called 
> "partial
> register update". Example:
>       add %di, %ax     ## ax += di
>
> Here, register %eax is only partially updated. To be more specific, 
> the lower
> half of %eax is set, and the upper half is left unchanged. There is 
> also no
> change in the upper 48 bits of register %rax.
>
> To get accurate performance analysis, the tool has to know which 
> instructions
> perform a partial register update, and which instructions fully update the
> destination's super-register.
>
> One way to expose this information is (again) via tablegen.  For 
> example, we
> could add a flag in the tablegen instruction class to tag instructions 
> that
> perform partial register updates. Something like this: 'bit
> hasPartialRegisterUpdate = 1'. However, this would force a `let
> hasPartialRegisterUpdate = 0` on several instruction definitions.
>
> Another approach is to have a MCSubtargetInfo hook similar to this:
>     virtual bool updatesSuperRegisters(unsigned short opcode) { return 
> false; }
>
> Targets will be able to override this method if needed.  Again, this 
> is just an
> idea. But the plan is to have this fixed as a future development.
>
> 2) Macro Op fusion.
>
> The tool doesn't know about macro-op fusion. On modern x86 processors, a
> 'cmp/test' followed by a 'jmp' is fused into a single macro 
> operation.  The
> advantage is that the fused pair only consumes a single slot in the 
> dispatch
> group.
>
> As a future development, the tool should be extended to address 
> macro-fusion.
> Ideally, we could have LLVM generate a table enumerating all the 
> opcode pairs
> that can be fused together. That table could be exposed to the tool 
> via the
> MCSubtargetInfo interface.  This is just an idea; there may be better 
> ways to
> implement this.
>
> 3) Intel processors: mixing legacy SSE with AVX instructions.
>
> On modern Intel processors with AVX, mixing legacy SSE code with AVX code
> negatively impacts the performance.  The tool is not aware of this 
> issue, and
> the performance penalty is not accounted when doing the analysis. This is
> something that we would like to improve in future.
>
> 4) Zero-latency register moves and Zero-idioms.
>
> Most modern AMD/Intel processors know how to optimize out 
> register-register
> moves and zero idioms at register renaming stage. The tool doesn't know
> about these patterns, and this may negatively impact the performance 
> analysis.
>
> Known design problems
> ---------------------
> This section describes two design issues that are currently affecting 
> the tool.
> The long term plan is to "fix" these issues.
>
> 1) Variant instructions not correctly modeled.
>
> The tool doesn't know how to analyze instructions with a "variant" 
> scheduling
> class descriptor. A variant scheduling class needs to be resolved 
> dynamically.
> The "actual" scheduling class often depends on the subtarget, as well as
> properties of the specific MachineInstr object.
>
> Unfortunately, the tool manipulates MCInst, and it doesn't know 
> anything about
> MachineInstr. As a consequence, the tool cannot use the existing machine
> subtarget hooks that are normally used to resolve the variant 
> scheduling class.
> This is a major design issue which mostly affects ARM/AArch64 targets.  It
> mostly boils down to the fact that the existing scheduling framework 
> was meant
> to work for MachineInstr.
>
> When the tool encounters a "variant" instruction, it assumes a generic 1cy
> latency. However, the tool would not be able to tell which processor 
> resources
> are effectively consumed by the variant instruction.
>
> 2) MCInst and MCInstrDesc.
>
> Performance analysis tools require data dependency information to 
> correctly
> predict the runtime performance of the code. This tool must always be 
> able to
> obtain the set of implicit/explicit register defs/uses for every 
> instruction of
> the input assembly sequence.
>
> In the first section of this document, it was mentioned how the tool 
> takes as
> input an assembly sequence. That sequence is parsed into a MCInst 
> sequence with
> the help of assembly parsers available from the targets.
>
> A MCInst is a very low-level instruction representation. The tool can 
> inspect
> the MCOperand sequence of an MCInst to identify register operands. 
> However,
> there is no way to tell register operands that are definitions from 
> register
> operands that are uses.
>
> In LLVM, class MCInstrDesc is used to fully describe target 
> instructions and
> their operands. The opcode of a machine instruction (a MachineInstr 
> object) can
> be used to query the instruction set through method `MCInstrInfo::get' 
> to obtain
> the associated MCInstrDesc object.
>
> However class MCInstrDesc describes properties and operands of 
> MachineInstr
> objects. Essentially, MCInstrDesc is not meant to be used to describe 
> MCInst
> objects.  To be more specific, MCInstrDesc objects are automatically 
> generated
> via tablegen from the instruction set description in the target .td 
> files.  For
> example, field `MCInstrDesc::NumDefs' is always equal to the 
> cardinality of the
> `(outs)` set from the tablegen instruction definition.
>
> By construction, register definitions always appear at the beginning 
> of the
> MachineOperands list in MachineInstr. Basically, the (outs) are the first
> operands of a MachineInstr, and the (ins) will come after in the 
> machine operand
> list. Knowing the number of register definitions is enough to identify
> all the register operands that are definitions.
>
> In a normal compilation process, MCInst objects are generated from 
> MachineInstr
> objects through a lowering step. By default the lowering logic simply 
> iterates
> over the machine operands of a MachineInstr, and converts/expands them 
> into
> equivalent MCOperand objects.
>
> The default lowering strategy has the advantage of preserving all of the
> above mentioned assumptions on the machine operand sequence. That 
> means, register
> definitions would still be at the beginning of the MCOperand sequence, and
> register uses would come after.
>
> Targets may still define custom lowering routines for specific 
> opcodes. Some of
> these routines may lower operands in a way that potentially breaks 
> (some of) the
> assumptions on the machine operand sequence which were valid for 
> MachineInstr.
> Luckily, this is not the most common form of lowering done by the 
> targets, and
> the vast majority of the MachineInstr are lowered based on the default 
> strategy
> which preserves the original machine operand sequence.  This is 
> especially true
> for x86, where the custom lowering logic always preserves the original 
> (i.e.
> from the MachineInstr) operand sequence.
>
> This tool currently works under the strong (and potentially incorrect)
> assumption that register def/uses in a MCInst can always be identified by
> querying the machine instruction descriptor for the opcode. This 
> assumption made
> it possible to develop this tool and get good numbers at least for the
> processors available in the x86 backend.
>
> That being said, the analysis is still potentially incorrect for other 
> targets.
> So we plan (with the help of the community) to find a proper mechanism 
> to map
> when possible MCOperand indices back to MachineOperand indices of the 
> equivalent
> MachineInstr.  This would be equivalent to describing changes made by the
> lowering step which affected the operand sequence. For example, we 
> could have an
> index for every register MCOperand (or -1, if the operand didn't exist 
> in the
> original MachineInstr). The mapping could look like this <0,1,3,2>.  Here,
> MCOperand #2 was obtained from the lowering of MachineOperand #3. etc.
>
> This information could be automatically generated via tablegen for all the
> instructions whose custom lowering step breaks assumptions made by the 
> tool on
> the register operand sequence (In general, these instructions should 
> be the
> minority of a target's instruction set). Unfortunately, we don't have that
> information now.  As a consequence, we assume that the number of explicit
> register definitions is the same number specified in MCInstrDesc.  We also
> assume that register definitions always come first in the operand 
> sequence.
>
> In conclusion: these are for now the strong assumptions made by the tool:
>   * The number of explicit and implicit register definitions in a MCInst
>     matches the number of explicit and implicit definitions specified 
> by the
>     MCInstrDesc object.
>   * Register uses always come after register definitions.
>   * If an opcode specifies an optional definition, then the optional
>     definition is always the last register operand in the sequence.
>
> Note that some of the information accessible from the MCInstrDesc is 
> always
> valid for MCInst. For example: implicit register defs, implicit 
> register uses
> and 'MayLoad/MayStore/HasUnmodeledSideEffects' opcode properties still 
> apply to
> MCInst. The tool knows about this, and uses that information during its
> analysis.
>
> What to do next
> ---------------
> The source code has been uploaded for review on phabricator at this 
> link: https://reviews.llvm.org/D43951.
>
> The review covers two patches:
> A first (very small) patch that always enables the generation of processor
> resource names in the SubtargetEmitter. Currently, the processor 
> resource names
> are only generated for debugging purposes, but are needed by the tool to
> generate user friendly reports, so we would like to always generate them.
> A second patch with the actual static analysis tool (in llvm/tools).
>
> Once these first two patches are committed, the plan is to keep 
> working on the
> tool with the help of the community to address all of the limitations 
> described
> by the previous sections, and find good solutions/fixes for the design 
> issues
> described by section "Known design problems".
>
> We hope the community will find this tool useful like we have.
>
> Special thanks to Simon Pilgrim, Filipe Cabecinhas and Greg Bedwell 
> who really
> helped me a lot by suggesting improvements and testing the tool.
>
> Thanks for your time.
> -Andrea
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20180302/8e72fade/attachment-0001.html>


More information about the llvm-dev mailing list