aco: Add README which explains about what ACO is and how it works.
[mesa.git] / src / amd / compiler / README.md
1 # Welcome to ACO
2
3 ACO (short for *AMD compiler*) is a back-end compiler for AMD GCN / RDNA GPUs, based on the NIR compiler infrastructure.
4 Simply put, ACO translates shader programs from the NIR intermediate representation into a GCN / RDNA binary which the GPU can execute.
5
6 ## Motivation
7
8 Why did we choose to develop a new compiler backend?
9
10 1. We'd like to give gamers a fluid, stutter-free experience, so we prioritize compilation speed.
11 2. Good divergence analysis allows us to better optimize runtime performance.
12 3. Issues can be fixed within mesa releases, independently of the schedule of other projects.
13
14 ## Control flow
15
16 Modern GPUs are SIMD machines that execute the shader in parallel.
17 In case of GCN / RDNA the parallelism is achieved by executing the shader on several waves, and each wave has several lanes (32 or 64).
18 When every lane executes exactly the same instructions, and takes the same path, it's uniform control flow;
19 otherwise when some lanes take one path while other lanes take a different path, it's divergent.
20
21 Each hardware lane corresponds to a shader invocation from a software perspective.
22
23 The hardware doesn't directly support divergence,
24 so in case of divergent control flow, the GPU must execute both code paths, each with some lanes disabled.
25 This is why divergence is a performance concern in shader programming.
26
27 ACO deals with divergent control flow by maintaining two control flow graphs (CFG):
28
29 * logical CFG - directly translated from NIR and shows the intended control flow of the program.
30 * linear CFG - created according to Whole-Function Vectorization by Ralf Karrenberg and Sebastian Hack.
31 The linear CFG represents how the program is physically executed on GPU and may contain additional blocks for control flow handling and to avoid critical edges.
32 Note that all nodes of the logical CFG also participate in the linear CFG, but not vice versa.
33
34 ## Compilation phases
35
36 #### Instruction Selection
37
38 The instruction selection is based around the divergence analysis and works in 3 passes on the NIR shader.
39
40 1. The divergence analysis pass calculates for each SSA definition if its value is guaranteed to be uniform across all threads of the workgroup.
41 2. We determine the register class for each SSA definition.
42 3. Actual instruction selection. The advanced divergence analysis allows for better usage of the scalar unit, scalar memory loads and the scalar register file.
43
44 We have two types of instructions:
45
46 * Hardware instructions as specified by the GCN / RDNA instruction set architecture manuals.
47 * Pseudo instructions which are helpers that encapsulate more complex functionality.
48 They eventually get lowered to real hardware instructions.
49
50 Each instruction can have operands (temporaries that it reads), and definitions (temporaries that it writes).
51 Temporaries can be fixed to a specific register, or just specify a register class (either a single register, or a vector of several registers).
52
53 #### Value Numbering
54
55 The value numbering pass is necessary for two reasons: the lack of descriptor load representation in NIR,
56 and every NIR instruction that gets emitted as multiple ACO instructions also has potential for CSE.
57 This pass does dominator-tree value numbering.
58
59 #### Optimization
60
61 In this phase, simpler instructions are combined into more complex instructions (like the different versions of multiply-add as well as neg, abs, clamp, and output modifiers) and constants are inlined, moves are eliminated, etc.
62 Exactly which optimizations are performed depends on the hardware for which the shader is being compiled.
63
64 #### Setup of reduction temporaries
65
66 This pass is responsible for making sure that register allocation is correct for reductions, by adding pseudo instructions that utilize linear VGPRs.
67 When a temporary has a linear VGPR register class, this means that the variable is considered *live* in the linear control flow graph.
68
69 #### Insert exec mask
70
71 In the GCN/RDNA architecture, there is a special register called `exec` which is used for manually controlling which VALU threads (aka. *lanes*) are active. The value of `exec` has to change in divergent branches, loops, etc. and it needs to be restored after the branch or loop is complete. This pass ensures that the correct lanes are active in every branch.
72
73 #### Live-Variable Analysis
74
75 A live-variable analysis is used to calculate the register need of the shader.
76 This information is used for spilling and scheduling before register allocation.
77
78 #### Spilling
79
80 First, we lower the shader program to CSSA form.
81 Then, if the register demand exceeds the global limit, this pass lowers register usage by temporarily storing excess scalar values in free vector registers, or excess vector values in scratch memory, and reloading them when needed. It is based on the paper "Register Spilling and Live-Range Splitting for SSA-Form Programs".
82
83 #### Instruction Scheduling
84
85 Scheduling is another NP-complete problem where basically all known heuristics suffer from unpredictable change in register pressure. For that reason, the implemented scheduler does not completely re-schedule all instructions, but only aims to move up memory loads as far as possible without exceeding the maximum register limit for the pre-calculated wave count. The reason this works is that ILP is very limited on GCN. This approach looks promising so far.
86
87 #### Register Allocation
88
89 The register allocator works on SSA (as opposed to LLVM's which works on virtual registers). The SSA properties guarantee that there are always as many registers available as needed. The problem is that some instructions require a vector of neighboring registers to be available, but the free regs might be scattered. In this case, the register allocator inserts shuffle code (moving some temporaries to other registers) to make space for the variable. The assumption is that it is (almost) always better to have a few more moves than to sacrifice a wave. The RA does SSA-reconstruction on the fly, which makes its runtime linear.
90
91 #### SSA Elimination
92
93 The next step is a pass out of SSA by inserting parallelcopies at the end of blocks to match the phi nodes' semantics.
94
95 #### Lower to HW instructions
96
97 Most pseudo instructions are lowered to actual machine instructions.
98 These are mostly parallel copy instructions created by instruction selection or register allocation and spill/reload code.
99
100 #### Insert wait states
101
102 GCN requires some wait states to be manually inserted in order to ensure correct behavior on memory instructions and some register dependencies.
103 This means that we need to insert `s_waitcnt` instructions (and its variants) so that the shader program waits until the eg. a memory operation is complete.
104
105 #### Resolve hazards and insert NOPs
106
107 Some instructions require wait states or other instructions to resolve hazards which are not handled by the hardware.
108 This pass makes sure that no known hazards occour.
109
110 #### Emit program - Assembler
111
112 The assembler emits the actual binary that will be sent to the hardware for execution. ACO's assembler is straight-forward because all instructions have their format, opcode, registers and potential fields already available, so it only needs to cater to the some differences between each hardware generation.
113
114 ## Supported shader stages
115
116 Hardware stages (as executed on the chip) don't exactly match software stages (as defined in OpenGL / Vulkan).
117 Which software stage gets executed on which hardware stage depends on what kind of software stages are present in the current pipeline.
118
119 An important difference is that VS is always the first stage to run in SW models,
120 whereas HW VS refers to the last HW stage before fragment shading in GCN/RDNA terminology.
121 That's why, among other things, the HW VS is no longer used to execute the SW VS when tesselation or geometry shading are used.
122
123 #### Glossary of software stages
124
125 * VS = Vertex Shader
126 * TCS = Tessellation Control Shader, equivalent to D3D HS = Hull Shader
127 * TES = Tessellation Evaluation Shader, equivalent to D3D DS = Domain Shader
128 * GS = Geometry Shader
129 * FS = Fragment Shader, equivalent to D3D PS = Pixel Shader
130 * CS = Compute Shader
131
132 #### Glossary of hardware stages
133
134 * LS = Local Shader (merged into HS on GFX9+), only runs SW VS when tessellation is used
135 * HS = Hull Shader, the HW equivalent of a Tessellation Control Shader, runs before the fixed function hardware performs tessellation
136 * ES = Export Shader (merged into GS on GFX9+), if there is a GS in the SW pipeline, the preceding stage (ie. SW VS or SW TES) always has to run on this HW stage
137 * GS = Geometry Shader, also known as legacy GS
138 * VS = Vertex Shader, **not equivalent to SW VS**: when there is a GS in the SW pipeline this stage runs a "GS copy" shader, otherwise it always runs the SW stage before FS
139 * NGG = Next Generation Geometry, a new hardware stage that replaces legacy HW GS and HW VS on RDNA GPUs
140 * PS = Pixel Shader, the HW equivalent to SW FS
141 * CS = Compute Shader
142
143 ##### Notes about HW VS and the "GS copy" shader
144
145 HW PS reads its inputs from a special buffer that only HW VS can write to, using export instructions.
146 However, GS store their output in VRAM (except GFX10/NGG).
147 So in order for HW PS to be able to read the GS outputs, we must run something on the VS stage which reads the GS outputs
148 from VRAM and exports them to this special buffer. This is what we call a "GS copy" shader.
149 From a HW perspective the "GS copy" shader is in fact VS (it runs on the HW VS stage),
150 but from a SW perspective it's not part of the traditional pipeline,
151 it's just some "glue code" that we need for outputs to play nicely.
152
153 On GFX10/NGG this limitation no longer exists, as the HW NGG GS can now export directly where it needs to.
154
155 ##### Notes about merged shaders
156
157 The merged stages on GFX9 (and GFX10/legacy) are: LSHS and ESGS. On GFX10/NGG the ESGS is merged with HW VS into NGG GS.
158
159 This might be confusing due to a mismatch between the number of invocations of these shaders.
160 For example, ES is per-vertex, but GS is per-primitive.
161 This is why merged shaders get an argument called `merged_wave_info` which tells how many invocations each part needs,
162 and there is some code at the beginning of each part to ensure the correct number of invocations by disabling some threads.
163 So, think about these as two independent shader programs slapped together.
164
165 ### Which software stage runs on which hardware stage?
166
167 #### Graphics Pipeline
168
169 ##### GFX6-8:
170
171 * Each SW stage has its own HW stage
172 * LS and HS share the same LDS space, so LS can store its output to LDS, where HS can read it
173 * HS, ES, GS outputs are stored in VRAM, next stage reads these from VRAM
174 * GS outputs got to VRAM, so they have to be copied by a GS copy shader running on the HW VS stage
175
176 | GFX6-8 HW stages: | LS | HS | ES | GS | VS | PS | ACO terminology |
177 | -----------------------:|:----|:----|:----|:----|:-------|:---|:----------------|
178 | SW stages: only VS+PS: | | | | | VS | FS | `vertex_vs`, `fragment_fs` |
179 | with tess: | VS | TCS | | | TES | FS | `vertex_ls`, `tess_control_hs`, `tess_eval_vs`, `fragment_fs` |
180 | with GS: | | | VS | GS | GS copy| FS | `vertex_es`, `geometry_gs`, `gs_copy_vs`, `fragment_fs` |
181 | with both: | VS | TCS | TES | GS | GS copy| FS | `vertex_ls`, `tess_control_hs`, `tess_eval_es`, `geometry_gs`, `gs_copy_vs`, `fragment_fs` |
182
183 ##### GFX9+ (including GFX10/legacy):
184
185 * HW LS and HS stages are merged, and the merged shader still uses LDS in the same way as before
186 * HW ES and GS stages are merged, so ES outputs can go to LDS instead of VRAM
187 * LSHS outputs and ESGS outputs are still stored in VRAM, so a GS copy shader is still necessary
188
189 | GFX9+ HW stages: | LSHS | ESGS | VS | PS | ACO terminology |
190 | -----------------------:|:----------|:----------|:-------|:---|:----------------|
191 | SW stages: only VS+PS: | | | VS | FS | `vertex_vs`, `fragment_fs` |
192 | with tess: | VS + TCS | | TES | FS | `vertex_tess_control_hs`, `tess_eval_vs`, `fragment_fs` |
193 | with GS: | | VS + GS | GS copy| FS | `vertex_geometry_gs`, `gs_copy_vs`, `fragment_fs` |
194 | with both: | VS + TCS | TES + GS | GS copy| FS | `vertex_tess_control_hs`, `tess_eval_geometry_gs`, `gs_copy_vs`, `fragment_fs` |
195
196 ##### NGG (GFX10+ only):
197
198 * HW GS and VS stages are now merged, and NGG GS can export directly
199 * GS copy shaders are no longer needed
200
201 | GFX10/NGG HW stages: | LSHS | NGG GS | PS | ACO terminology |
202 | -----------------------:|:----------|:-------------------|:---|:----------------|
203 | SW stages: only VS+PS: | | VS | FS | `ngg_vertex_gs`, `fragment_fs` |
204 | with tess: | VS + TCS | TES | FS | `vertex_tess_control_hs`, `ngg_tess_eval_gs`, `fragment_fs` |
205 | with GS: | | VS + GS | FS | `ngg_vertex_geometry_gs`, `fragment_fs` |
206 | with both: | VS + TCS | TES + GS | FS | `vertex_tess_control_hs`, `ngg_tess_eval_geometry_gs`, `fragment_fs` |
207
208 #### Compute pipeline
209
210 GFX6-10:
211
212 * Note that the SW CS always runs on the HW CS stage on all HW generations.
213
214 | GFX6-10 HW stage | CS | ACO terminology |
215 | -----------------------:|:-----|:----------------|
216 | SW stage | CS | `compute_cs` |
217
218
219 ## How to debug
220
221 Handy `RADV_DEBUG` options that help with ACO debugging:
222
223 * `nocache` - you always want to use this when debugging, otherwise you risk using a broken shader from the cache.
224 * `shaders` - makes ACO print the IR after register allocation, as well as the disassembled shader binary.
225 * `metashaders` - does the same thing as `shaders` but for built-in RADV shaders.
226 * `preoptir` - makes ACO print the final NIR shader before instruction selection, as well as the ACO IR after instruction selection.
227 * `nongg` - disables NGG support
228
229 We also have `ACO_DEBUG` options:
230
231 * `validateir` - Validate the ACO IR between compilation stages. By default, enabled in debug builds and disabled in release builds.
232 * `validatera` - Perform a RA (register allocation) validation.
233 * `perfwarn` - Warn when sub-optimal instructions are found.
234 * `force-waitcnt` - Forces ACO to emit a wait state after each instruction when there is something to wait for. Harms performance.
235 * `novn` - Disables the ACO value numbering stage.
236 * `noopt` - Disables the ACO optimizer.
237 * `nosched` - Disables the ACO scheduler.
238
239 Note that you need to **combine these options into a comma-separated list**, for example: `RADV_DEBUG=nocache,shaders` otherwise only the last one will take effect. (This is how all environment variables work, yet this is an often made mistake.) Example:
240
241 ```
242 RADV_DEBUG=nocache,shaders ACO_DEBUG=validateir,validatera vkcube
243 ```
244
245 Here are some good practices we learned while debugging visual corruption and hangs.
246
247 1. Bisecting shaders:
248 * Use renderdoc when examining shaders. This is deterministic while real games often use multi-threading or change the order in which shaders get compiled.
249 * Edit `radv_shader.c` or `radv_pipeline.c` to change if they are compiled with LLVM or ACO.
250 2. Things to check early:
251 * Disable value_numbering, optimizer and/or scheduler.
252 Note that if any of these change the output, it does not necessarily mean that the error is there, as register assignment does also change.
253 3. Finding the instruction causing a hang:
254 * The ability to directly manipulate the binaries gives us an easy way to find the exact instruction which causes the hang.
255 Use NULL exports (for FS and VS) and `s_endpgm` to end the shader early to find the problematic instruction.
256 4. Other faulty instructions:
257 * Use print_asm and check for illegal instructions.
258 * Compare to the ACO IR to see if the assembly matches what we want (this can take a while).
259 Typical issues might be a wrong instruction format leading to a wrong opcode or an sgpr used for vgpr field.
260 5. Comparing to the LLVM backend:
261 * If everything else didn't help, we probably just do something wrong. The LLVM backend is quite mature, so its output might help find differences, but this can be a long road.