1 /*
2 * Copyright © 2010 Intel Corporation
3 *
4 * Permission is hereby granted, free of charge, to any person obtaining a
5 * copy of this software and associated documentation files (the "Software"),
6 * to deal in the Software without restriction, including without limitation
7 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
8 * and/or sell copies of the Software, and to permit persons to whom the
9 * Software is furnished to do so, subject to the following conditions:
10 *
11 * The above copyright notice and this permission notice (including the next
12 * paragraph) shall be included in all copies or substantial portions of the
13 * Software.
14 *
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
18 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
20 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
21 * IN THE SOFTWARE.
22 *
23 * Authors:
24 * Eric Anholt <eric@anholt.net>
25 *
26 */
27
28 #include "brw_eu.h"
29 #include "brw_fs.h"
30 #include "brw_fs_live_variables.h"
31 #include "brw_cfg.h"
32 #include "brw_shader.h"
33 #include <new>
34
35 using namespace brw;
36
37 /** @file brw_fs_schedule_instructions.cpp
38 *
39 * List scheduling of FS instructions.
40 *
41 * The basic model of the list scheduler is to take a basic block,
42 * compute a DAG of the dependencies (RAW ordering with latency, WAW
43 * ordering with latency, WAR ordering), and make a list of the DAG heads.
44 * Heuristically pick a DAG head, then put all the children that are
45 * now DAG heads into the list of things to schedule.
46 *
47 * The heuristic is the important part. We're trying to be cheap,
48 * since actually computing the optimal scheduling is NP complete.
49 * What we do is track a "current clock". When we schedule a node, we
50 * update the earliest-unblocked clock time of its children, and
51 * increment the clock. Then, when trying to schedule, we just pick
52 * the earliest-unblocked instruction to schedule.
53 *
54 * Note that often there will be many things which could execute
55 * immediately, and there are a range of heuristic options to choose
56 * from in picking among those.
57 */
58
59 static bool debug = false;
60
61 class instruction_scheduler;
62 struct schedule_node_child;
63
64 class schedule_node : public exec_node
65 {
66 public:
67 void set_latency(const struct brw_isa_info *isa);
68
69 backend_instruction *inst;
70 schedule_node_child *children;
71 int children_count;
72 int children_cap;
73 int initial_parent_count;
74 int initial_unblocked_time;
75 int latency;
76
77 /**
78 * This is the sum of the instruction's latency plus the maximum delay of
79 * its children, or just the issue_time if it's a leaf node.
80 */
81 int delay;
82
83 /**
84 * Preferred exit node among the (direct or indirect) successors of this
85 * node. Among the scheduler nodes blocked by this node, this will be the
86 * one that may cause earliest program termination, or NULL if none of the
87 * successors is an exit node.
88 */
89 schedule_node *exit;
90
91 /**
92 * How many cycles this instruction takes to issue.
93 *
94 * Instructions in gen hardware are handled one simd4 vector at a time,
95 * with 1 cycle per vector dispatched. Thus SIMD8 pixel shaders take 2
96 * cycles to dispatch and SIMD16 (compressed) instructions take 4.
97 */
98 int issue_time;
99
100 /* Temporary data used during the scheduling process. */
101 struct {
102 int parent_count;
103 int unblocked_time;
104
105 /**
106 * Which iteration of pushing groups of children onto the candidates list
107 * this node was a part of.
108 */
109 unsigned cand_generation;
110 } tmp;
111 };
112
113 struct schedule_node_child {
114 schedule_node *n;
115 int effective_latency;
116 };
117
118 static inline void
reset_node_tmp(schedule_node * n)119 reset_node_tmp(schedule_node *n)
120 {
121 n->tmp.parent_count = n->initial_parent_count;
122 n->tmp.unblocked_time = n->initial_unblocked_time;
123 n->tmp.cand_generation = 0;
124 }
125
126 /**
127 * Lower bound of the scheduling time after which one of the instructions
128 * blocked by this node may lead to program termination.
129 *
130 * exit_unblocked_time() determines a strict partial ordering relation '«' on
131 * the set of scheduler nodes as follows:
132 *
133 * n « m <-> exit_unblocked_time(n) < exit_unblocked_time(m)
134 *
135 * which can be used to heuristically order nodes according to how early they
136 * can unblock an exit node and lead to program termination.
137 */
138 static inline int
exit_tmp_unblocked_time(const schedule_node * n)139 exit_tmp_unblocked_time(const schedule_node *n)
140 {
141 return n->exit ? n->exit->tmp.unblocked_time : INT_MAX;
142 }
143
144 static inline int
exit_initial_unblocked_time(const schedule_node * n)145 exit_initial_unblocked_time(const schedule_node *n)
146 {
147 return n->exit ? n->exit->initial_unblocked_time : INT_MAX;
148 }
149
150 void
set_latency(const struct brw_isa_info * isa)151 schedule_node::set_latency(const struct brw_isa_info *isa)
152 {
153 switch (inst->opcode) {
154 case BRW_OPCODE_MAD:
155 /* 2 cycles
156 * (since the last two src operands are in different register banks):
157 * mad(8) g4<1>F g2.2<4,4,1>F.x g2<4,4,1>F.x g3.1<4,4,1>F.x { align16 WE_normal 1Q };
158 *
159 * 3 cycles on IVB, 4 on HSW
160 * (since the last two src operands are in the same register bank):
161 * mad(8) g4<1>F g2.2<4,4,1>F.x g2<4,4,1>F.x g2.1<4,4,1>F.x { align16 WE_normal 1Q };
162 *
163 * 18 cycles on IVB, 16 on HSW
164 * (since the last two src operands are in different register banks):
165 * mad(8) g4<1>F g2.2<4,4,1>F.x g2<4,4,1>F.x g3.1<4,4,1>F.x { align16 WE_normal 1Q };
166 * mov(8) null g4<4,5,1>F { align16 WE_normal 1Q };
167 *
168 * 20 cycles on IVB, 18 on HSW
169 * (since the last two src operands are in the same register bank):
170 * mad(8) g4<1>F g2.2<4,4,1>F.x g2<4,4,1>F.x g2.1<4,4,1>F.x { align16 WE_normal 1Q };
171 * mov(8) null g4<4,4,1>F { align16 WE_normal 1Q };
172 */
173
174 /* Our register allocator doesn't know about register banks, so use the
175 * higher latency.
176 */
177 latency = 18;
178 break;
179
180 case BRW_OPCODE_LRP:
181 /* 2 cycles
182 * (since the last two src operands are in different register banks):
183 * lrp(8) g4<1>F g2.2<4,4,1>F.x g2<4,4,1>F.x g3.1<4,4,1>F.x { align16 WE_normal 1Q };
184 *
185 * 3 cycles on IVB, 4 on HSW
186 * (since the last two src operands are in the same register bank):
187 * lrp(8) g4<1>F g2.2<4,4,1>F.x g2<4,4,1>F.x g2.1<4,4,1>F.x { align16 WE_normal 1Q };
188 *
189 * 16 cycles on IVB, 14 on HSW
190 * (since the last two src operands are in different register banks):
191 * lrp(8) g4<1>F g2.2<4,4,1>F.x g2<4,4,1>F.x g3.1<4,4,1>F.x { align16 WE_normal 1Q };
192 * mov(8) null g4<4,4,1>F { align16 WE_normal 1Q };
193 *
194 * 16 cycles
195 * (since the last two src operands are in the same register bank):
196 * lrp(8) g4<1>F g2.2<4,4,1>F.x g2<4,4,1>F.x g2.1<4,4,1>F.x { align16 WE_normal 1Q };
197 * mov(8) null g4<4,4,1>F { align16 WE_normal 1Q };
198 */
199
200 /* Our register allocator doesn't know about register banks, so use the
201 * higher latency.
202 */
203 latency = 14;
204 break;
205
206 case SHADER_OPCODE_RCP:
207 case SHADER_OPCODE_RSQ:
208 case SHADER_OPCODE_SQRT:
209 case SHADER_OPCODE_LOG2:
210 case SHADER_OPCODE_EXP2:
211 case SHADER_OPCODE_SIN:
212 case SHADER_OPCODE_COS:
213 /* 2 cycles:
214 * math inv(8) g4<1>F g2<0,1,0>F null { align1 WE_normal 1Q };
215 *
216 * 18 cycles:
217 * math inv(8) g4<1>F g2<0,1,0>F null { align1 WE_normal 1Q };
218 * mov(8) null g4<8,8,1>F { align1 WE_normal 1Q };
219 *
220 * Same for exp2, log2, rsq, sqrt, sin, cos.
221 */
222 latency = 16;
223 break;
224
225 case SHADER_OPCODE_POW:
226 /* 2 cycles:
227 * math pow(8) g4<1>F g2<0,1,0>F g2.1<0,1,0>F { align1 WE_normal 1Q };
228 *
229 * 26 cycles:
230 * math pow(8) g4<1>F g2<0,1,0>F g2.1<0,1,0>F { align1 WE_normal 1Q };
231 * mov(8) null g4<8,8,1>F { align1 WE_normal 1Q };
232 */
233 latency = 24;
234 break;
235
236 case SHADER_OPCODE_TEX:
237 case SHADER_OPCODE_TXD:
238 case SHADER_OPCODE_TXF:
239 case SHADER_OPCODE_TXF_LZ:
240 case SHADER_OPCODE_TXL:
241 case SHADER_OPCODE_TXL_LZ:
242 /* 18 cycles:
243 * mov(8) g115<1>F 0F { align1 WE_normal 1Q };
244 * mov(8) g114<1>F 0F { align1 WE_normal 1Q };
245 * send(8) g4<1>UW g114<8,8,1>F
246 * sampler (10, 0, 0, 1) mlen 2 rlen 4 { align1 WE_normal 1Q };
247 *
248 * 697 +/-49 cycles (min 610, n=26):
249 * mov(8) g115<1>F 0F { align1 WE_normal 1Q };
250 * mov(8) g114<1>F 0F { align1 WE_normal 1Q };
251 * send(8) g4<1>UW g114<8,8,1>F
252 * sampler (10, 0, 0, 1) mlen 2 rlen 4 { align1 WE_normal 1Q };
253 * mov(8) null g4<8,8,1>F { align1 WE_normal 1Q };
254 *
255 * So the latency on our first texture load of the batchbuffer takes
256 * ~700 cycles, since the caches are cold at that point.
257 *
258 * 840 +/- 92 cycles (min 720, n=25):
259 * mov(8) g115<1>F 0F { align1 WE_normal 1Q };
260 * mov(8) g114<1>F 0F { align1 WE_normal 1Q };
261 * send(8) g4<1>UW g114<8,8,1>F
262 * sampler (10, 0, 0, 1) mlen 2 rlen 4 { align1 WE_normal 1Q };
263 * mov(8) null g4<8,8,1>F { align1 WE_normal 1Q };
264 * send(8) g4<1>UW g114<8,8,1>F
265 * sampler (10, 0, 0, 1) mlen 2 rlen 4 { align1 WE_normal 1Q };
266 * mov(8) null g4<8,8,1>F { align1 WE_normal 1Q };
267 *
268 * On the second load, it takes just an extra ~140 cycles, and after
269 * accounting for the 14 cycles of the MOV's latency, that makes ~130.
270 *
271 * 683 +/- 49 cycles (min = 602, n=47):
272 * mov(8) g115<1>F 0F { align1 WE_normal 1Q };
273 * mov(8) g114<1>F 0F { align1 WE_normal 1Q };
274 * send(8) g4<1>UW g114<8,8,1>F
275 * sampler (10, 0, 0, 1) mlen 2 rlen 4 { align1 WE_normal 1Q };
276 * send(8) g50<1>UW g114<8,8,1>F
277 * sampler (10, 0, 0, 1) mlen 2 rlen 4 { align1 WE_normal 1Q };
278 * mov(8) null g4<8,8,1>F { align1 WE_normal 1Q };
279 *
280 * The unit appears to be pipelined, since this matches up with the
281 * cache-cold case, despite there being two loads here. If you replace
282 * the g4 in the MOV to null with g50, it's still 693 +/- 52 (n=39).
283 *
284 * So, take some number between the cache-hot 140 cycles and the
285 * cache-cold 700 cycles. No particular tuning was done on this.
286 *
287 * I haven't done significant testing of the non-TEX opcodes. TXL at
288 * least looked about the same as TEX.
289 */
290 latency = 200;
291 break;
292
293 case SHADER_OPCODE_TXS:
294 /* Testing textureSize(sampler2D, 0), one load was 420 +/- 41
295 * cycles (n=15):
296 * mov(8) g114<1>UD 0D { align1 WE_normal 1Q };
297 * send(8) g6<1>UW g114<8,8,1>F
298 * sampler (10, 0, 10, 1) mlen 1 rlen 4 { align1 WE_normal 1Q };
299 * mov(16) g6<1>F g6<8,8,1>D { align1 WE_normal 1Q };
300 *
301 *
302 * Two loads was 535 +/- 30 cycles (n=19):
303 * mov(16) g114<1>UD 0D { align1 WE_normal 1H };
304 * send(16) g6<1>UW g114<8,8,1>F
305 * sampler (10, 0, 10, 2) mlen 2 rlen 8 { align1 WE_normal 1H };
306 * mov(16) g114<1>UD 0D { align1 WE_normal 1H };
307 * mov(16) g6<1>F g6<8,8,1>D { align1 WE_normal 1H };
308 * send(16) g8<1>UW g114<8,8,1>F
309 * sampler (10, 0, 10, 2) mlen 2 rlen 8 { align1 WE_normal 1H };
310 * mov(16) g8<1>F g8<8,8,1>D { align1 WE_normal 1H };
311 * add(16) g6<1>F g6<8,8,1>F g8<8,8,1>F { align1 WE_normal 1H };
312 *
313 * Since the only caches that should matter are just the
314 * instruction/state cache containing the surface state, assume that we
315 * always have hot caches.
316 */
317 latency = 100;
318 break;
319
320 case FS_OPCODE_UNIFORM_PULL_CONSTANT_LOAD:
321 /* testing using varying-index pull constants:
322 *
323 * 16 cycles:
324 * mov(8) g4<1>D g2.1<0,1,0>F { align1 WE_normal 1Q };
325 * send(8) g4<1>F g4<8,8,1>D
326 * data (9, 2, 3) mlen 1 rlen 1 { align1 WE_normal 1Q };
327 *
328 * ~480 cycles:
329 * mov(8) g4<1>D g2.1<0,1,0>F { align1 WE_normal 1Q };
330 * send(8) g4<1>F g4<8,8,1>D
331 * data (9, 2, 3) mlen 1 rlen 1 { align1 WE_normal 1Q };
332 * mov(8) null g4<8,8,1>F { align1 WE_normal 1Q };
333 *
334 * ~620 cycles:
335 * mov(8) g4<1>D g2.1<0,1,0>F { align1 WE_normal 1Q };
336 * send(8) g4<1>F g4<8,8,1>D
337 * data (9, 2, 3) mlen 1 rlen 1 { align1 WE_normal 1Q };
338 * mov(8) null g4<8,8,1>F { align1 WE_normal 1Q };
339 * send(8) g4<1>F g4<8,8,1>D
340 * data (9, 2, 3) mlen 1 rlen 1 { align1 WE_normal 1Q };
341 * mov(8) null g4<8,8,1>F { align1 WE_normal 1Q };
342 *
343 * So, if it's cache-hot, it's about 140. If it's cache cold, it's
344 * about 460. We expect to mostly be cache hot, so pick something more
345 * in that direction.
346 */
347 latency = 200;
348 break;
349
350 case SHADER_OPCODE_SEND:
351 switch (inst->sfid) {
352 case BRW_SFID_SAMPLER: {
353 unsigned msg_type = (inst->desc >> 12) & 0x1f;
354 switch (msg_type) {
355 case GFX5_SAMPLER_MESSAGE_SAMPLE_RESINFO:
356 case GFX6_SAMPLER_MESSAGE_SAMPLE_SAMPLEINFO:
357 /* See also SHADER_OPCODE_TXS */
358 latency = 100;
359 break;
360
361 default:
362 /* See also SHADER_OPCODE_TEX */
363 latency = 200;
364 break;
365 }
366 break;
367 }
368
369 case GFX6_SFID_DATAPORT_CONSTANT_CACHE:
370 /* See FS_OPCODE_UNIFORM_PULL_CONSTANT_LOAD */
371 latency = 200;
372 break;
373
374 case GFX6_SFID_DATAPORT_RENDER_CACHE:
375 switch (brw_fb_desc_msg_type(isa->devinfo, inst->desc)) {
376 case GFX7_DATAPORT_RC_TYPED_SURFACE_WRITE:
377 case GFX7_DATAPORT_RC_TYPED_SURFACE_READ:
378 /* See also SHADER_OPCODE_TYPED_SURFACE_READ */
379 latency = 600;
380 break;
381
382 case GFX7_DATAPORT_RC_TYPED_ATOMIC_OP:
383 /* See also SHADER_OPCODE_TYPED_ATOMIC */
384 latency = 14000;
385 break;
386
387 case GFX6_DATAPORT_WRITE_MESSAGE_RENDER_TARGET_WRITE:
388 /* completely fabricated number */
389 latency = 600;
390 break;
391
392 default:
393 unreachable("Unknown render cache message");
394 }
395 break;
396
397 case GFX7_SFID_DATAPORT_DATA_CACHE:
398 switch ((inst->desc >> 14) & 0x1f) {
399 case BRW_DATAPORT_READ_MESSAGE_OWORD_BLOCK_READ:
400 case GFX7_DATAPORT_DC_UNALIGNED_OWORD_BLOCK_READ:
401 case GFX6_DATAPORT_WRITE_MESSAGE_OWORD_BLOCK_WRITE:
402 /* We have no data for this but assume it's a little faster than
403 * untyped surface read/write.
404 */
405 latency = 200;
406 break;
407
408 case GFX7_DATAPORT_DC_DWORD_SCATTERED_READ:
409 case GFX6_DATAPORT_WRITE_MESSAGE_DWORD_SCATTERED_WRITE:
410 case HSW_DATAPORT_DC_PORT0_BYTE_SCATTERED_READ:
411 case HSW_DATAPORT_DC_PORT0_BYTE_SCATTERED_WRITE:
412 /* We have no data for this but assume it's roughly the same as
413 * untyped surface read/write.
414 */
415 latency = 300;
416 break;
417
418 case GFX7_DATAPORT_DC_UNTYPED_SURFACE_READ:
419 case GFX7_DATAPORT_DC_UNTYPED_SURFACE_WRITE:
420 /* Test code:
421 * mov(8) g112<1>UD 0x00000000UD { align1 WE_all 1Q };
422 * mov(1) g112.7<1>UD g1.7<0,1,0>UD { align1 WE_all };
423 * mov(8) g113<1>UD 0x00000000UD { align1 WE_normal 1Q };
424 * send(8) g4<1>UD g112<8,8,1>UD
425 * data (38, 6, 5) mlen 2 rlen 1 { align1 WE_normal 1Q };
426 * .
427 * . [repeats 8 times]
428 * .
429 * mov(8) g112<1>UD 0x00000000UD { align1 WE_all 1Q };
430 * mov(1) g112.7<1>UD g1.7<0,1,0>UD { align1 WE_all };
431 * mov(8) g113<1>UD 0x00000000UD { align1 WE_normal 1Q };
432 * send(8) g4<1>UD g112<8,8,1>UD
433 * data (38, 6, 5) mlen 2 rlen 1 { align1 WE_normal 1Q };
434 *
435 * Running it 100 times as fragment shader on a 128x128 quad
436 * gives an average latency of 583 cycles per surface read,
437 * standard deviation 0.9%.
438 */
439 latency = 600;
440 break;
441
442 case GFX7_DATAPORT_DC_UNTYPED_ATOMIC_OP:
443 /* Test code:
444 * mov(8) g112<1>ud 0x00000000ud { align1 WE_all 1Q };
445 * mov(1) g112.7<1>ud g1.7<0,1,0>ud { align1 WE_all };
446 * mov(8) g113<1>ud 0x00000000ud { align1 WE_normal 1Q };
447 * send(8) g4<1>ud g112<8,8,1>ud
448 * data (38, 5, 6) mlen 2 rlen 1 { align1 WE_normal 1Q };
449 *
450 * Running it 100 times as fragment shader on a 128x128 quad
451 * gives an average latency of 13867 cycles per atomic op,
452 * standard deviation 3%. Note that this is a rather
453 * pessimistic estimate, the actual latency in cases with few
454 * collisions between threads and favorable pipelining has been
455 * seen to be reduced by a factor of 100.
456 */
457 latency = 14000;
458 break;
459
460 default:
461 unreachable("Unknown data cache message");
462 }
463 break;
464
465 case HSW_SFID_DATAPORT_DATA_CACHE_1:
466 switch (brw_dp_desc_msg_type(isa->devinfo, inst->desc)) {
467 case HSW_DATAPORT_DC_PORT1_UNTYPED_SURFACE_READ:
468 case HSW_DATAPORT_DC_PORT1_UNTYPED_SURFACE_WRITE:
469 case HSW_DATAPORT_DC_PORT1_TYPED_SURFACE_READ:
470 case HSW_DATAPORT_DC_PORT1_TYPED_SURFACE_WRITE:
471 case GFX8_DATAPORT_DC_PORT1_A64_UNTYPED_SURFACE_WRITE:
472 case GFX8_DATAPORT_DC_PORT1_A64_UNTYPED_SURFACE_READ:
473 case GFX8_DATAPORT_DC_PORT1_A64_SCATTERED_WRITE:
474 case GFX9_DATAPORT_DC_PORT1_A64_SCATTERED_READ:
475 case GFX9_DATAPORT_DC_PORT1_A64_OWORD_BLOCK_READ:
476 case GFX9_DATAPORT_DC_PORT1_A64_OWORD_BLOCK_WRITE:
477 /* See also GFX7_DATAPORT_DC_UNTYPED_SURFACE_READ */
478 latency = 300;
479 break;
480
481 case HSW_DATAPORT_DC_PORT1_UNTYPED_ATOMIC_OP:
482 case HSW_DATAPORT_DC_PORT1_UNTYPED_ATOMIC_OP_SIMD4X2:
483 case HSW_DATAPORT_DC_PORT1_TYPED_ATOMIC_OP_SIMD4X2:
484 case HSW_DATAPORT_DC_PORT1_TYPED_ATOMIC_OP:
485 case GFX9_DATAPORT_DC_PORT1_UNTYPED_ATOMIC_FLOAT_OP:
486 case GFX8_DATAPORT_DC_PORT1_A64_UNTYPED_ATOMIC_OP:
487 case GFX9_DATAPORT_DC_PORT1_A64_UNTYPED_ATOMIC_FLOAT_OP:
488 case GFX12_DATAPORT_DC_PORT1_A64_UNTYPED_ATOMIC_HALF_INT_OP:
489 case GFX12_DATAPORT_DC_PORT1_A64_UNTYPED_ATOMIC_HALF_FLOAT_OP:
490 /* See also GFX7_DATAPORT_DC_UNTYPED_ATOMIC_OP */
491 latency = 14000;
492 break;
493
494 default:
495 unreachable("Unknown data cache message");
496 }
497 break;
498
499 case GFX7_SFID_PIXEL_INTERPOLATOR:
500 latency = 50; /* TODO */
501 break;
502
503 case GFX12_SFID_UGM:
504 case GFX12_SFID_TGM:
505 case GFX12_SFID_SLM:
506 switch (lsc_msg_desc_opcode(isa->devinfo, inst->desc)) {
507 case LSC_OP_LOAD:
508 case LSC_OP_STORE:
509 case LSC_OP_LOAD_CMASK:
510 case LSC_OP_STORE_CMASK:
511 latency = 300;
512 break;
513 case LSC_OP_FENCE:
514 case LSC_OP_ATOMIC_INC:
515 case LSC_OP_ATOMIC_DEC:
516 case LSC_OP_ATOMIC_LOAD:
517 case LSC_OP_ATOMIC_STORE:
518 case LSC_OP_ATOMIC_ADD:
519 case LSC_OP_ATOMIC_SUB:
520 case LSC_OP_ATOMIC_MIN:
521 case LSC_OP_ATOMIC_MAX:
522 case LSC_OP_ATOMIC_UMIN:
523 case LSC_OP_ATOMIC_UMAX:
524 case LSC_OP_ATOMIC_CMPXCHG:
525 case LSC_OP_ATOMIC_FADD:
526 case LSC_OP_ATOMIC_FSUB:
527 case LSC_OP_ATOMIC_FMIN:
528 case LSC_OP_ATOMIC_FMAX:
529 case LSC_OP_ATOMIC_FCMPXCHG:
530 case LSC_OP_ATOMIC_AND:
531 case LSC_OP_ATOMIC_OR:
532 case LSC_OP_ATOMIC_XOR:
533 latency = 1400;
534 break;
535 default:
536 unreachable("unsupported new data port message instruction");
537 }
538 break;
539
540 case GEN_RT_SFID_BINDLESS_THREAD_DISPATCH:
541 case GEN_RT_SFID_RAY_TRACE_ACCELERATOR:
542 /* TODO.
543 *
544 * We'll assume for the moment that this is pretty quick as it
545 * doesn't actually return any data.
546 */
547 latency = 200;
548 break;
549
550 case BRW_SFID_URB:
551 latency = 200;
552 break;
553
554 default:
555 unreachable("Unknown SFID");
556 }
557 break;
558
559 case BRW_OPCODE_DPAS:
560 switch (inst->rcount) {
561 case 1:
562 latency = 21;
563 break;
564 case 2:
565 latency = 22;
566 break;
567 case 8:
568 default:
569 latency = 32;
570 break;
571 }
572 break;
573
574 default:
575 /* 2 cycles:
576 * mul(8) g4<1>F g2<0,1,0>F 0.5F { align1 WE_normal 1Q };
577 *
578 * 16 cycles:
579 * mul(8) g4<1>F g2<0,1,0>F 0.5F { align1 WE_normal 1Q };
580 * mov(8) null g4<8,8,1>F { align1 WE_normal 1Q };
581 */
582 latency = 14;
583 break;
584 }
585 }
586
587 class instruction_scheduler {
588 public:
instruction_scheduler(void * mem_ctx,const backend_shader * s,int grf_count,int grf_write_scale,bool post_reg_alloc)589 instruction_scheduler(void *mem_ctx, const backend_shader *s, int grf_count,
590 int grf_write_scale, bool post_reg_alloc):
591 bs(s)
592 {
593 this->mem_ctx = mem_ctx;
594 this->lin_ctx = linear_context(this->mem_ctx);
595 this->grf_count = grf_count;
596 this->post_reg_alloc = post_reg_alloc;
597
598 this->last_grf_write = linear_zalloc_array(lin_ctx, schedule_node *, grf_count * grf_write_scale);
599
600 this->nodes_len = s->cfg->last_block()->end_ip + 1;
601 this->nodes = linear_zalloc_array(lin_ctx, schedule_node, this->nodes_len);
602
603 const struct brw_isa_info *isa = &bs->compiler->isa;
604
605 schedule_node *n = nodes;
606 foreach_block_and_inst(block, backend_instruction, inst, s->cfg) {
607 n->inst = inst;
608
609 if (!post_reg_alloc)
610 n->latency = 1;
611 else
612 n->set_latency(isa);
613
614 n++;
615 }
616 assert(n == nodes + nodes_len);
617
618 current.block = NULL;
619 current.start = NULL;
620 current.end = NULL;
621 current.len = 0;
622 current.time = 0;
623 current.cand_generation = 0;
624 current.available.make_empty();
625 }
626
627 void add_barrier_deps(schedule_node *n);
628 void add_cross_lane_deps(schedule_node *n);
629 void add_dep(schedule_node *before, schedule_node *after, int latency);
630 void add_dep(schedule_node *before, schedule_node *after);
631
632 void set_current_block(bblock_t *block);
633 void compute_delays();
634 void compute_exits();
635
636 void schedule(schedule_node *chosen);
637 void update_children(schedule_node *chosen);
638
639 void *mem_ctx;
640 linear_ctx *lin_ctx;
641
642 schedule_node *nodes;
643 int nodes_len;
644
645 /* Current block being processed. */
646 struct {
647 bblock_t *block;
648
649 /* Range of nodes in the block. End will point to first node
650 * address after the block, i.e. the range is [start, end).
651 */
652 schedule_node *start;
653 schedule_node *end;
654 int len;
655
656 int scheduled;
657
658 unsigned cand_generation;
659 int time;
660 exec_list available;
661 } current;
662
663 bool post_reg_alloc;
664 int grf_count;
665 const backend_shader *bs;
666
667 /**
668 * Last instruction to have written the grf (or a channel in the grf, for the
669 * scalar backend)
670 */
671 schedule_node **last_grf_write;
672 };
673
674 class fs_instruction_scheduler : public instruction_scheduler
675 {
676 public:
677 fs_instruction_scheduler(void *mem_ctx, const fs_visitor *v, int grf_count, int hw_reg_count,
678 int block_count, bool post_reg_alloc);
679 void calculate_deps();
680 bool is_compressed(const fs_inst *inst);
681 schedule_node *choose_instruction_to_schedule();
682 int calculate_issue_time(backend_instruction *inst);
683
684 void count_reads_remaining(backend_instruction *inst);
685 void setup_liveness(cfg_t *cfg);
686 void update_register_pressure(backend_instruction *inst);
687 int get_register_pressure_benefit(backend_instruction *inst);
688 void clear_last_grf_write();
689
690 void schedule_instructions();
691 void run(instruction_scheduler_mode mode);
692
693 const fs_visitor *v;
694 unsigned hw_reg_count;
695 int reg_pressure;
696 instruction_scheduler_mode mode;
697
698 /*
699 * The register pressure at the beginning of each basic block.
700 */
701
702 int *reg_pressure_in;
703
704 /*
705 * The virtual GRF's whose range overlaps the beginning of each basic block.
706 */
707
708 BITSET_WORD **livein;
709
710 /*
711 * The virtual GRF's whose range overlaps the end of each basic block.
712 */
713
714 BITSET_WORD **liveout;
715
716 /*
717 * The hardware GRF's whose range overlaps the end of each basic block.
718 */
719
720 BITSET_WORD **hw_liveout;
721
722 /*
723 * Whether we've scheduled a write for this virtual GRF yet.
724 */
725
726 bool *written;
727
728 /*
729 * How many reads we haven't scheduled for this virtual GRF yet.
730 */
731
732 int *reads_remaining;
733
734 /*
735 * How many reads we haven't scheduled for this hardware GRF yet.
736 */
737
738 int *hw_reads_remaining;
739
740 };
741
fs_instruction_scheduler(void * mem_ctx,const fs_visitor * v,int grf_count,int hw_reg_count,int block_count,bool post_reg_alloc)742 fs_instruction_scheduler::fs_instruction_scheduler(void *mem_ctx, const fs_visitor *v,
743 int grf_count, int hw_reg_count,
744 int block_count, bool post_reg_alloc)
745 : instruction_scheduler(mem_ctx, v, grf_count, /* grf_write_scale */ 16,
746 post_reg_alloc),
747 v(v)
748 {
749 this->hw_reg_count = hw_reg_count;
750 this->mode = SCHEDULE_NONE;
751 this->reg_pressure = 0;
752
753 if (!post_reg_alloc) {
754 this->reg_pressure_in = linear_zalloc_array(lin_ctx, int, block_count);
755
756 this->livein = linear_alloc_array(lin_ctx, BITSET_WORD *, block_count);
757 for (int i = 0; i < block_count; i++)
758 this->livein[i] = linear_zalloc_array(lin_ctx, BITSET_WORD,
759 BITSET_WORDS(grf_count));
760
761 this->liveout = linear_alloc_array(lin_ctx, BITSET_WORD *, block_count);
762 for (int i = 0; i < block_count; i++)
763 this->liveout[i] = linear_zalloc_array(lin_ctx, BITSET_WORD,
764 BITSET_WORDS(grf_count));
765
766 this->hw_liveout = linear_alloc_array(lin_ctx, BITSET_WORD *, block_count);
767 for (int i = 0; i < block_count; i++)
768 this->hw_liveout[i] = linear_zalloc_array(lin_ctx, BITSET_WORD,
769 BITSET_WORDS(hw_reg_count));
770
771 setup_liveness(v->cfg);
772
773 this->written = linear_alloc_array(lin_ctx, bool, grf_count);
774
775 this->reads_remaining = linear_alloc_array(lin_ctx, int, grf_count);
776
777 this->hw_reads_remaining = linear_alloc_array(lin_ctx, int, hw_reg_count);
778 } else {
779 this->reg_pressure_in = NULL;
780 this->livein = NULL;
781 this->liveout = NULL;
782 this->hw_liveout = NULL;
783 this->written = NULL;
784 this->reads_remaining = NULL;
785 this->hw_reads_remaining = NULL;
786 }
787
788 foreach_block(block, v->cfg) {
789 set_current_block(block);
790
791 for (schedule_node *n = current.start; n < current.end; n++)
792 n->issue_time = calculate_issue_time(n->inst);
793
794 calculate_deps();
795 compute_delays();
796 compute_exits();
797 }
798 }
799
800 static bool
is_src_duplicate(fs_inst * inst,int src)801 is_src_duplicate(fs_inst *inst, int src)
802 {
803 for (int i = 0; i < src; i++)
804 if (inst->src[i].equals(inst->src[src]))
805 return true;
806
807 return false;
808 }
809
810 void
count_reads_remaining(backend_instruction * be)811 fs_instruction_scheduler::count_reads_remaining(backend_instruction *be)
812 {
813 assert(reads_remaining);
814
815 fs_inst *inst = (fs_inst *)be;
816
817 for (int i = 0; i < inst->sources; i++) {
818 if (is_src_duplicate(inst, i))
819 continue;
820
821 if (inst->src[i].file == VGRF) {
822 reads_remaining[inst->src[i].nr]++;
823 } else if (inst->src[i].file == FIXED_GRF) {
824 if (inst->src[i].nr >= hw_reg_count)
825 continue;
826
827 for (unsigned j = 0; j < regs_read(inst, i); j++)
828 hw_reads_remaining[inst->src[i].nr + j]++;
829 }
830 }
831 }
832
833 void
setup_liveness(cfg_t * cfg)834 fs_instruction_scheduler::setup_liveness(cfg_t *cfg)
835 {
836 const fs_live_variables &live = v->live_analysis.require();
837
838 /* First, compute liveness on a per-GRF level using the in/out sets from
839 * liveness calculation.
840 */
841 for (int block = 0; block < cfg->num_blocks; block++) {
842 for (int i = 0; i < live.num_vars; i++) {
843 if (BITSET_TEST(live.block_data[block].livein, i)) {
844 int vgrf = live.vgrf_from_var[i];
845 if (!BITSET_TEST(livein[block], vgrf)) {
846 reg_pressure_in[block] += v->alloc.sizes[vgrf];
847 BITSET_SET(livein[block], vgrf);
848 }
849 }
850
851 if (BITSET_TEST(live.block_data[block].liveout, i))
852 BITSET_SET(liveout[block], live.vgrf_from_var[i]);
853 }
854 }
855
856 /* Now, extend the live in/live out sets for when a range crosses a block
857 * boundary, which matches what our register allocator/interference code
858 * does to account for force_writemask_all and incompatible exec_mask's.
859 */
860 for (int block = 0; block < cfg->num_blocks - 1; block++) {
861 for (int i = 0; i < grf_count; i++) {
862 if (live.vgrf_start[i] <= cfg->blocks[block]->end_ip &&
863 live.vgrf_end[i] >= cfg->blocks[block + 1]->start_ip) {
864 if (!BITSET_TEST(livein[block + 1], i)) {
865 reg_pressure_in[block + 1] += v->alloc.sizes[i];
866 BITSET_SET(livein[block + 1], i);
867 }
868
869 BITSET_SET(liveout[block], i);
870 }
871 }
872 }
873
874 int payload_last_use_ip[hw_reg_count];
875 v->calculate_payload_ranges(hw_reg_count, payload_last_use_ip);
876
877 for (unsigned i = 0; i < hw_reg_count; i++) {
878 if (payload_last_use_ip[i] == -1)
879 continue;
880
881 for (int block = 0; block < cfg->num_blocks; block++) {
882 if (cfg->blocks[block]->start_ip <= payload_last_use_ip[i])
883 reg_pressure_in[block]++;
884
885 if (cfg->blocks[block]->end_ip <= payload_last_use_ip[i])
886 BITSET_SET(hw_liveout[block], i);
887 }
888 }
889 }
890
891 void
update_register_pressure(backend_instruction * be)892 fs_instruction_scheduler::update_register_pressure(backend_instruction *be)
893 {
894 assert(reads_remaining);
895
896 fs_inst *inst = (fs_inst *)be;
897
898 if (inst->dst.file == VGRF) {
899 written[inst->dst.nr] = true;
900 }
901
902 for (int i = 0; i < inst->sources; i++) {
903 if (is_src_duplicate(inst, i))
904 continue;
905
906 if (inst->src[i].file == VGRF) {
907 reads_remaining[inst->src[i].nr]--;
908 } else if (inst->src[i].file == FIXED_GRF &&
909 inst->src[i].nr < hw_reg_count) {
910 for (unsigned off = 0; off < regs_read(inst, i); off++)
911 hw_reads_remaining[inst->src[i].nr + off]--;
912 }
913 }
914 }
915
916 int
get_register_pressure_benefit(backend_instruction * be)917 fs_instruction_scheduler::get_register_pressure_benefit(backend_instruction *be)
918 {
919 fs_inst *inst = (fs_inst *)be;
920 int benefit = 0;
921 const int block_idx = current.block->num;
922
923 if (inst->dst.file == VGRF) {
924 if (!BITSET_TEST(livein[block_idx], inst->dst.nr) &&
925 !written[inst->dst.nr])
926 benefit -= v->alloc.sizes[inst->dst.nr];
927 }
928
929 for (int i = 0; i < inst->sources; i++) {
930 if (is_src_duplicate(inst, i))
931 continue;
932
933 if (inst->src[i].file == VGRF &&
934 !BITSET_TEST(liveout[block_idx], inst->src[i].nr) &&
935 reads_remaining[inst->src[i].nr] == 1)
936 benefit += v->alloc.sizes[inst->src[i].nr];
937
938 if (inst->src[i].file == FIXED_GRF &&
939 inst->src[i].nr < hw_reg_count) {
940 for (unsigned off = 0; off < regs_read(inst, i); off++) {
941 int reg = inst->src[i].nr + off;
942 if (!BITSET_TEST(hw_liveout[block_idx], reg) &&
943 hw_reads_remaining[reg] == 1) {
944 benefit++;
945 }
946 }
947 }
948 }
949
950 return benefit;
951 }
952
953 void
set_current_block(bblock_t * block)954 instruction_scheduler::set_current_block(bblock_t *block)
955 {
956 current.block = block;
957 current.start = nodes + block->start_ip;
958 current.len = block->end_ip - block->start_ip + 1;
959 current.end = current.start + current.len;
960 current.time = 0;
961 current.scheduled = 0;
962 current.cand_generation = 1;
963 }
964
965 /** Computation of the delay member of each node. */
966 void
compute_delays()967 instruction_scheduler::compute_delays()
968 {
969 for (schedule_node *n = current.end - 1; n >= current.start; n--) {
970 if (!n->children_count) {
971 n->delay = n->issue_time;
972 } else {
973 for (int i = 0; i < n->children_count; i++) {
974 assert(n->children[i].n->delay);
975 n->delay = MAX2(n->delay, n->latency + n->children[i].n->delay);
976 }
977 }
978 }
979 }
980
981 void
compute_exits()982 instruction_scheduler::compute_exits()
983 {
984 /* Calculate a lower bound of the scheduling time of each node in the
985 * graph. This is analogous to the node's critical path but calculated
986 * from the top instead of from the bottom of the block.
987 */
988 for (schedule_node *n = current.start; n < current.end; n++) {
989 for (int i = 0; i < n->children_count; i++) {
990 schedule_node_child *child = &n->children[i];
991 child->n->initial_unblocked_time =
992 MAX2(child->n->initial_unblocked_time,
993 n->initial_unblocked_time + n->issue_time + child->effective_latency);
994 }
995 }
996
997 /* Calculate the exit of each node by induction based on the exit nodes of
998 * its children. The preferred exit of a node is the one among the exit
999 * nodes of its children which can be unblocked first according to the
1000 * optimistic unblocked time estimate calculated above.
1001 */
1002 for (schedule_node *n = current.end - 1; n >= current.start; n--) {
1003 n->exit = (n->inst->opcode == BRW_OPCODE_HALT ? n : NULL);
1004
1005 for (int i = 0; i < n->children_count; i++) {
1006 if (exit_initial_unblocked_time(n->children[i].n) < exit_initial_unblocked_time(n))
1007 n->exit = n->children[i].n->exit;
1008 }
1009 }
1010 }
1011
1012 /**
1013 * Add a dependency between two instruction nodes.
1014 *
1015 * The @after node will be scheduled after @before. We will try to
1016 * schedule it @latency cycles after @before, but no guarantees there.
1017 */
1018 void
add_dep(schedule_node * before,schedule_node * after,int latency)1019 instruction_scheduler::add_dep(schedule_node *before, schedule_node *after,
1020 int latency)
1021 {
1022 if (!before || !after)
1023 return;
1024
1025 assert(before != after);
1026
1027 for (int i = 0; i < before->children_count; i++) {
1028 schedule_node_child *child = &before->children[i];
1029 if (child->n == after) {
1030 child->effective_latency = MAX2(child->effective_latency, latency);
1031 return;
1032 }
1033 }
1034
1035 if (before->children_cap <= before->children_count) {
1036 if (before->children_cap < 16)
1037 before->children_cap = 16;
1038 else
1039 before->children_cap *= 2;
1040
1041 before->children = reralloc(mem_ctx, before->children,
1042 schedule_node_child,
1043 before->children_cap);
1044 }
1045
1046 schedule_node_child *child = &before->children[before->children_count];
1047 child->n = after;
1048 child->effective_latency = latency;
1049 before->children_count++;
1050 after->initial_parent_count++;
1051 }
1052
1053 void
add_dep(schedule_node * before,schedule_node * after)1054 instruction_scheduler::add_dep(schedule_node *before, schedule_node *after)
1055 {
1056 if (!before)
1057 return;
1058
1059 add_dep(before, after, before->latency);
1060 }
1061
1062 static bool
is_scheduling_barrier(const backend_instruction * inst)1063 is_scheduling_barrier(const backend_instruction *inst)
1064 {
1065 return inst->opcode == SHADER_OPCODE_HALT_TARGET ||
1066 inst->is_control_flow() ||
1067 inst->has_side_effects();
1068 }
1069
1070 static bool
has_cross_lane_access(const fs_inst * inst)1071 has_cross_lane_access(const fs_inst *inst)
1072 {
1073 /* FINISHME:
1074 *
1075 * This function is likely incomplete in terms of identify cross lane
1076 * accesses.
1077 */
1078 if (inst->opcode == SHADER_OPCODE_BROADCAST ||
1079 inst->opcode == SHADER_OPCODE_READ_SR_REG ||
1080 inst->opcode == SHADER_OPCODE_CLUSTER_BROADCAST ||
1081 inst->opcode == SHADER_OPCODE_SHUFFLE ||
1082 inst->opcode == FS_OPCODE_LOAD_LIVE_CHANNELS ||
1083 inst->opcode == SHADER_OPCODE_LOAD_LIVE_CHANNELS ||
1084 inst->opcode == SHADER_OPCODE_FIND_LAST_LIVE_CHANNEL ||
1085 inst->opcode == SHADER_OPCODE_FIND_LIVE_CHANNEL)
1086 return true;
1087
1088 for (unsigned s = 0; s < inst->sources; s++) {
1089 if (inst->src[s].file == VGRF) {
1090 if (inst->src[s].stride == 0)
1091 return true;
1092 }
1093 }
1094
1095 return false;
1096 }
1097
1098 /**
1099 * Sometimes we really want this node to execute after everything that
1100 * was before it and before everything that followed it. This adds
1101 * the deps to do so.
1102 */
1103 void
add_barrier_deps(schedule_node * n)1104 instruction_scheduler::add_barrier_deps(schedule_node *n)
1105 {
1106 for (schedule_node *prev = n - 1; prev >= current.start; prev--) {
1107 add_dep(prev, n, 0);
1108 if (is_scheduling_barrier(prev->inst))
1109 break;
1110 }
1111
1112 for (schedule_node *next = n + 1; next < current.end; next++) {
1113 add_dep(n, next, 0);
1114 if (is_scheduling_barrier(next->inst))
1115 break;
1116 }
1117 }
1118
1119 /**
1120 * Because some instructions like HALT can disable lanes, scheduling prior to
1121 * a cross lane access should not be allowed, otherwise we could end up with
1122 * later instructions accessing uninitialized data.
1123 */
1124 void
add_cross_lane_deps(schedule_node * n)1125 instruction_scheduler::add_cross_lane_deps(schedule_node *n)
1126 {
1127 for (schedule_node *prev = n - 1; prev >= current.start; prev--) {
1128 if (has_cross_lane_access((fs_inst*)prev->inst))
1129 add_dep(prev, n, 0);
1130 }
1131 }
1132
1133 /* instruction scheduling needs to be aware of when an MRF write
1134 * actually writes 2 MRFs.
1135 */
1136 bool
is_compressed(const fs_inst * inst)1137 fs_instruction_scheduler::is_compressed(const fs_inst *inst)
1138 {
1139 return inst->exec_size == 16;
1140 }
1141
1142 /* Clears last_grf_write to be ready to start calculating deps for a block
1143 * again.
1144 *
1145 * Since pre-ra grf_count scales with instructions, and instructions scale with
1146 * BBs, we don't want to memset all of last_grf_write per block or you'll end up
1147 * O(n^2) with number of blocks. For shaders using softfp64, we get a *lot* of
1148 * blocks.
1149 *
1150 * We don't bother being careful for post-ra, since then grf_count doesn't scale
1151 * with instructions.
1152 */
1153 void
clear_last_grf_write()1154 fs_instruction_scheduler::clear_last_grf_write()
1155 {
1156 if (!post_reg_alloc) {
1157 for (schedule_node *n = current.start; n < current.end; n++) {
1158 fs_inst *inst = (fs_inst *)n->inst;
1159
1160 if (inst->dst.file == VGRF) {
1161 /* Don't bother being careful with regs_written(), quicker to just clear 2 cachelines. */
1162 memset(&last_grf_write[inst->dst.nr * 16], 0, sizeof(*last_grf_write) * 16);
1163 }
1164 }
1165 } else {
1166 memset(last_grf_write, 0, sizeof(*last_grf_write) * grf_count * 16);
1167 }
1168 }
1169
1170 void
calculate_deps()1171 fs_instruction_scheduler::calculate_deps()
1172 {
1173 /* Pre-register-allocation, this tracks the last write per VGRF offset.
1174 * After register allocation, reg_offsets are gone and we track individual
1175 * GRF registers.
1176 */
1177 schedule_node *last_conditional_mod[8] = {};
1178 schedule_node *last_accumulator_write = NULL;
1179 /* Fixed HW registers are assumed to be separate from the virtual
1180 * GRFs, so they can be tracked separately. We don't really write
1181 * to fixed GRFs much, so don't bother tracking them on a more
1182 * granular level.
1183 */
1184 schedule_node *last_fixed_grf_write = NULL;
1185
1186 /* top-to-bottom dependencies: RAW and WAW. */
1187 for (schedule_node *n = current.start; n < current.end; n++) {
1188 fs_inst *inst = (fs_inst *)n->inst;
1189
1190 if (is_scheduling_barrier(inst))
1191 add_barrier_deps(n);
1192
1193 if (inst->opcode == BRW_OPCODE_HALT ||
1194 inst->opcode == SHADER_OPCODE_HALT_TARGET)
1195 add_cross_lane_deps(n);
1196
1197 /* read-after-write deps. */
1198 for (int i = 0; i < inst->sources; i++) {
1199 if (inst->src[i].file == VGRF) {
1200 if (post_reg_alloc) {
1201 for (unsigned r = 0; r < regs_read(inst, i); r++)
1202 add_dep(last_grf_write[inst->src[i].nr + r], n);
1203 } else {
1204 for (unsigned r = 0; r < regs_read(inst, i); r++) {
1205 add_dep(last_grf_write[inst->src[i].nr * 16 +
1206 inst->src[i].offset / REG_SIZE + r], n);
1207 }
1208 }
1209 } else if (inst->src[i].file == FIXED_GRF) {
1210 if (post_reg_alloc) {
1211 for (unsigned r = 0; r < regs_read(inst, i); r++)
1212 add_dep(last_grf_write[inst->src[i].nr + r], n);
1213 } else {
1214 add_dep(last_fixed_grf_write, n);
1215 }
1216 } else if (inst->src[i].is_accumulator()) {
1217 add_dep(last_accumulator_write, n);
1218 } else if (inst->src[i].file == ARF && !inst->src[i].is_null()) {
1219 add_barrier_deps(n);
1220 }
1221 }
1222
1223 if (const unsigned mask = inst->flags_read(v->devinfo)) {
1224 assert(mask < (1 << ARRAY_SIZE(last_conditional_mod)));
1225
1226 for (unsigned i = 0; i < ARRAY_SIZE(last_conditional_mod); i++) {
1227 if (mask & (1 << i))
1228 add_dep(last_conditional_mod[i], n);
1229 }
1230 }
1231
1232 if (inst->reads_accumulator_implicitly()) {
1233 add_dep(last_accumulator_write, n);
1234 }
1235
1236 /* write-after-write deps. */
1237 if (inst->dst.file == VGRF) {
1238 if (post_reg_alloc) {
1239 for (unsigned r = 0; r < regs_written(inst); r++) {
1240 add_dep(last_grf_write[inst->dst.nr + r], n);
1241 last_grf_write[inst->dst.nr + r] = n;
1242 }
1243 } else {
1244 for (unsigned r = 0; r < regs_written(inst); r++) {
1245 add_dep(last_grf_write[inst->dst.nr * 16 +
1246 inst->dst.offset / REG_SIZE + r], n);
1247 last_grf_write[inst->dst.nr * 16 +
1248 inst->dst.offset / REG_SIZE + r] = n;
1249 }
1250 }
1251 } else if (inst->dst.file == FIXED_GRF) {
1252 if (post_reg_alloc) {
1253 for (unsigned r = 0; r < regs_written(inst); r++) {
1254 add_dep(last_grf_write[inst->dst.nr + r], n);
1255 last_grf_write[inst->dst.nr + r] = n;
1256 }
1257 } else {
1258 add_dep(last_fixed_grf_write, n);
1259 last_fixed_grf_write = n;
1260 }
1261 } else if (inst->dst.is_accumulator()) {
1262 add_dep(last_accumulator_write, n);
1263 last_accumulator_write = n;
1264 } else if (inst->dst.file == ARF && !inst->dst.is_null()) {
1265 add_barrier_deps(n);
1266 }
1267
1268 if (const unsigned mask = inst->flags_written(v->devinfo)) {
1269 assert(mask < (1 << ARRAY_SIZE(last_conditional_mod)));
1270
1271 for (unsigned i = 0; i < ARRAY_SIZE(last_conditional_mod); i++) {
1272 if (mask & (1 << i)) {
1273 add_dep(last_conditional_mod[i], n, 0);
1274 last_conditional_mod[i] = n;
1275 }
1276 }
1277 }
1278
1279 if (inst->writes_accumulator_implicitly(v->devinfo) &&
1280 !inst->dst.is_accumulator()) {
1281 add_dep(last_accumulator_write, n);
1282 last_accumulator_write = n;
1283 }
1284 }
1285
1286 clear_last_grf_write();
1287
1288 /* bottom-to-top dependencies: WAR */
1289 memset(last_conditional_mod, 0, sizeof(last_conditional_mod));
1290 last_accumulator_write = NULL;
1291 last_fixed_grf_write = NULL;
1292
1293 for (schedule_node *n = current.end - 1; n >= current.start; n--) {
1294 fs_inst *inst = (fs_inst *)n->inst;
1295
1296 /* write-after-read deps. */
1297 for (int i = 0; i < inst->sources; i++) {
1298 if (inst->src[i].file == VGRF) {
1299 if (post_reg_alloc) {
1300 for (unsigned r = 0; r < regs_read(inst, i); r++)
1301 add_dep(n, last_grf_write[inst->src[i].nr + r], 0);
1302 } else {
1303 for (unsigned r = 0; r < regs_read(inst, i); r++) {
1304 add_dep(n, last_grf_write[inst->src[i].nr * 16 +
1305 inst->src[i].offset / REG_SIZE + r], 0);
1306 }
1307 }
1308 } else if (inst->src[i].file == FIXED_GRF) {
1309 if (post_reg_alloc) {
1310 for (unsigned r = 0; r < regs_read(inst, i); r++)
1311 add_dep(n, last_grf_write[inst->src[i].nr + r], 0);
1312 } else {
1313 add_dep(n, last_fixed_grf_write, 0);
1314 }
1315 } else if (inst->src[i].is_accumulator()) {
1316 add_dep(n, last_accumulator_write, 0);
1317 } else if (inst->src[i].file == ARF && !inst->src[i].is_null()) {
1318 add_barrier_deps(n);
1319 }
1320 }
1321
1322 if (const unsigned mask = inst->flags_read(v->devinfo)) {
1323 assert(mask < (1 << ARRAY_SIZE(last_conditional_mod)));
1324
1325 for (unsigned i = 0; i < ARRAY_SIZE(last_conditional_mod); i++) {
1326 if (mask & (1 << i))
1327 add_dep(n, last_conditional_mod[i]);
1328 }
1329 }
1330
1331 if (inst->reads_accumulator_implicitly()) {
1332 add_dep(n, last_accumulator_write);
1333 }
1334
1335 /* Update the things this instruction wrote, so earlier reads
1336 * can mark this as WAR dependency.
1337 */
1338 if (inst->dst.file == VGRF) {
1339 if (post_reg_alloc) {
1340 for (unsigned r = 0; r < regs_written(inst); r++)
1341 last_grf_write[inst->dst.nr + r] = n;
1342 } else {
1343 for (unsigned r = 0; r < regs_written(inst); r++) {
1344 last_grf_write[inst->dst.nr * 16 +
1345 inst->dst.offset / REG_SIZE + r] = n;
1346 }
1347 }
1348 } else if (inst->dst.file == FIXED_GRF) {
1349 if (post_reg_alloc) {
1350 for (unsigned r = 0; r < regs_written(inst); r++)
1351 last_grf_write[inst->dst.nr + r] = n;
1352 } else {
1353 last_fixed_grf_write = n;
1354 }
1355 } else if (inst->dst.is_accumulator()) {
1356 last_accumulator_write = n;
1357 } else if (inst->dst.file == ARF && !inst->dst.is_null()) {
1358 add_barrier_deps(n);
1359 }
1360
1361 if (const unsigned mask = inst->flags_written(v->devinfo)) {
1362 assert(mask < (1 << ARRAY_SIZE(last_conditional_mod)));
1363
1364 for (unsigned i = 0; i < ARRAY_SIZE(last_conditional_mod); i++) {
1365 if (mask & (1 << i))
1366 last_conditional_mod[i] = n;
1367 }
1368 }
1369
1370 if (inst->writes_accumulator_implicitly(v->devinfo)) {
1371 last_accumulator_write = n;
1372 }
1373 }
1374
1375 clear_last_grf_write();
1376 }
1377
1378 schedule_node *
choose_instruction_to_schedule()1379 fs_instruction_scheduler::choose_instruction_to_schedule()
1380 {
1381 schedule_node *chosen = NULL;
1382
1383 if (mode == SCHEDULE_PRE || mode == SCHEDULE_POST) {
1384 int chosen_time = 0;
1385
1386 /* Of the instructions ready to execute or the closest to being ready,
1387 * choose the one most likely to unblock an early program exit, or
1388 * otherwise the oldest one.
1389 */
1390 foreach_in_list(schedule_node, n, ¤t.available) {
1391 if (!chosen ||
1392 exit_tmp_unblocked_time(n) < exit_tmp_unblocked_time(chosen) ||
1393 (exit_tmp_unblocked_time(n) == exit_tmp_unblocked_time(chosen) &&
1394 n->tmp.unblocked_time < chosen_time)) {
1395 chosen = n;
1396 chosen_time = n->tmp.unblocked_time;
1397 }
1398 }
1399 } else {
1400 int chosen_register_pressure_benefit = 0;
1401
1402 /* Before register allocation, we don't care about the latencies of
1403 * instructions. All we care about is reducing live intervals of
1404 * variables so that we can avoid register spilling, or get SIMD16
1405 * shaders which naturally do a better job of hiding instruction
1406 * latency.
1407 */
1408 foreach_in_list(schedule_node, n, ¤t.available) {
1409 if (!chosen) {
1410 chosen = n;
1411 chosen_register_pressure_benefit =
1412 get_register_pressure_benefit(chosen->inst);
1413 continue;
1414 }
1415
1416 /* Most important: If we can definitely reduce register pressure, do
1417 * so immediately.
1418 */
1419 int register_pressure_benefit = get_register_pressure_benefit(n->inst);
1420
1421 if (register_pressure_benefit > 0 &&
1422 register_pressure_benefit > chosen_register_pressure_benefit) {
1423 chosen = n;
1424 chosen_register_pressure_benefit = register_pressure_benefit;
1425 continue;
1426 } else if (chosen_register_pressure_benefit > 0 &&
1427 (register_pressure_benefit <
1428 chosen_register_pressure_benefit)) {
1429 continue;
1430 }
1431
1432 if (mode == SCHEDULE_PRE_LIFO) {
1433 /* Prefer instructions that recently became available for
1434 * scheduling. These are the things that are most likely to
1435 * (eventually) make a variable dead and reduce register pressure.
1436 * Typical register pressure estimates don't work for us because
1437 * most of our pressure comes from texturing, where no single
1438 * instruction to schedule will make a vec4 value dead.
1439 */
1440 if (n->tmp.cand_generation > chosen->tmp.cand_generation) {
1441 chosen = n;
1442 chosen_register_pressure_benefit = register_pressure_benefit;
1443 continue;
1444 } else if (n->tmp.cand_generation < chosen->tmp.cand_generation) {
1445 continue;
1446 }
1447 }
1448
1449 /* For instructions pushed on the cands list at the same time, prefer
1450 * the one with the highest delay to the end of the program. This is
1451 * most likely to have its values able to be consumed first (such as
1452 * for a large tree of lowered ubo loads, which appear reversed in
1453 * the instruction stream with respect to when they can be consumed).
1454 */
1455 if (n->delay > chosen->delay) {
1456 chosen = n;
1457 chosen_register_pressure_benefit = register_pressure_benefit;
1458 continue;
1459 } else if (n->delay < chosen->delay) {
1460 continue;
1461 }
1462
1463 /* Prefer the node most likely to unblock an early program exit.
1464 */
1465 if (exit_tmp_unblocked_time(n) < exit_tmp_unblocked_time(chosen)) {
1466 chosen = n;
1467 chosen_register_pressure_benefit = register_pressure_benefit;
1468 continue;
1469 } else if (exit_tmp_unblocked_time(n) > exit_tmp_unblocked_time(chosen)) {
1470 continue;
1471 }
1472
1473 /* If all other metrics are equal, we prefer the first instruction in
1474 * the list (program execution).
1475 */
1476 }
1477 }
1478
1479 return chosen;
1480 }
1481
1482 int
calculate_issue_time(backend_instruction * inst0)1483 fs_instruction_scheduler::calculate_issue_time(backend_instruction *inst0)
1484 {
1485 const struct brw_isa_info *isa = &v->compiler->isa;
1486 const fs_inst *inst = static_cast<fs_inst *>(inst0);
1487 const unsigned overhead = v->grf_used && has_bank_conflict(isa, inst) ?
1488 DIV_ROUND_UP(inst->dst.component_size(inst->exec_size), REG_SIZE) : 0;
1489 if (is_compressed(inst))
1490 return 4 + overhead;
1491 else
1492 return 2 + overhead;
1493 }
1494
1495 void
schedule(schedule_node * chosen)1496 instruction_scheduler::schedule(schedule_node *chosen)
1497 {
1498 assert(current.scheduled < current.len);
1499 current.scheduled++;
1500
1501 assert(chosen);
1502 chosen->remove();
1503 current.block->instructions.push_tail(chosen->inst);
1504
1505 /* If we expected a delay for scheduling, then bump the clock to reflect
1506 * that. In reality, the hardware will switch to another hyperthread
1507 * and may not return to dispatching our thread for a while even after
1508 * we're unblocked. After this, we have the time when the chosen
1509 * instruction will start executing.
1510 */
1511 current.time = MAX2(current.time, chosen->tmp.unblocked_time);
1512
1513 /* Update the clock for how soon an instruction could start after the
1514 * chosen one.
1515 */
1516 current.time += chosen->issue_time;
1517
1518 if (debug) {
1519 fprintf(stderr, "clock %4d, scheduled: ", current.time);
1520 bs->dump_instruction(chosen->inst);
1521 }
1522 }
1523
1524 void
update_children(schedule_node * chosen)1525 instruction_scheduler::update_children(schedule_node *chosen)
1526 {
1527 /* Now that we've scheduled a new instruction, some of its
1528 * children can be promoted to the list of instructions ready to
1529 * be scheduled. Update the children's unblocked time for this
1530 * DAG edge as we do so.
1531 */
1532 for (int i = chosen->children_count - 1; i >= 0; i--) {
1533 schedule_node_child *child = &chosen->children[i];
1534
1535 child->n->tmp.unblocked_time = MAX2(child->n->tmp.unblocked_time,
1536 current.time + child->effective_latency);
1537
1538 if (debug) {
1539 fprintf(stderr, "\tchild %d, %d parents: ", i, child->n->tmp.parent_count);
1540 bs->dump_instruction(child->n->inst);
1541 }
1542
1543 child->n->tmp.cand_generation = current.cand_generation;
1544 child->n->tmp.parent_count--;
1545 if (child->n->tmp.parent_count == 0) {
1546 if (debug) {
1547 fprintf(stderr, "\t\tnow available\n");
1548 }
1549 current.available.push_head(child->n);
1550 }
1551 }
1552 current.cand_generation++;
1553 }
1554
1555 void
schedule_instructions()1556 fs_instruction_scheduler::schedule_instructions()
1557 {
1558 if (!post_reg_alloc)
1559 reg_pressure = reg_pressure_in[current.block->num];
1560
1561 assert(current.available.is_empty());
1562 for (schedule_node *n = current.start; n < current.end; n++) {
1563 reset_node_tmp(n);
1564
1565 /* Add DAG heads to the list of available instructions. */
1566 if (n->tmp.parent_count == 0)
1567 current.available.push_tail(n);
1568 }
1569
1570 current.block->instructions.make_empty();
1571
1572 while (!current.available.is_empty()) {
1573 schedule_node *chosen = choose_instruction_to_schedule();
1574 schedule(chosen);
1575
1576 if (!post_reg_alloc) {
1577 reg_pressure -= get_register_pressure_benefit(chosen->inst);
1578 update_register_pressure(chosen->inst);
1579 if (debug)
1580 fprintf(stderr, "(register pressure %d)\n", reg_pressure);
1581 }
1582
1583 update_children(chosen);
1584 }
1585 }
1586
1587 void
run(instruction_scheduler_mode mode)1588 fs_instruction_scheduler::run(instruction_scheduler_mode mode)
1589 {
1590 this->mode = mode;
1591
1592 if (debug && !post_reg_alloc) {
1593 fprintf(stderr, "\nInstructions before scheduling (reg_alloc %d)\n",
1594 post_reg_alloc);
1595 bs->dump_instructions();
1596 }
1597
1598 if (!post_reg_alloc) {
1599 memset(reads_remaining, 0, grf_count * sizeof(*reads_remaining));
1600 memset(hw_reads_remaining, 0, hw_reg_count * sizeof(*hw_reads_remaining));
1601 memset(written, 0, grf_count * sizeof(*written));
1602 }
1603
1604 foreach_block(block, v->cfg) {
1605 set_current_block(block);
1606
1607 if (!post_reg_alloc) {
1608 for (schedule_node *n = current.start; n < current.end; n++)
1609 count_reads_remaining(n->inst);
1610 }
1611
1612 schedule_instructions();
1613 }
1614
1615 if (debug && !post_reg_alloc) {
1616 fprintf(stderr, "\nInstructions after scheduling (reg_alloc %d)\n",
1617 post_reg_alloc);
1618 bs->dump_instructions();
1619 }
1620 }
1621
1622 fs_instruction_scheduler *
prepare_scheduler(void * mem_ctx)1623 fs_visitor::prepare_scheduler(void *mem_ctx)
1624 {
1625 const int grf_count = alloc.count;
1626
1627 fs_instruction_scheduler *empty = rzalloc(mem_ctx, fs_instruction_scheduler);
1628 return new (empty) fs_instruction_scheduler(mem_ctx, this, grf_count, first_non_payload_grf,
1629 cfg->num_blocks, /* post_reg_alloc */ false);
1630 }
1631
1632 void
schedule_instructions_pre_ra(fs_instruction_scheduler * sched,instruction_scheduler_mode mode)1633 fs_visitor::schedule_instructions_pre_ra(fs_instruction_scheduler *sched,
1634 instruction_scheduler_mode mode)
1635 {
1636 if (mode == SCHEDULE_NONE)
1637 return;
1638
1639 sched->run(mode);
1640
1641 invalidate_analysis(DEPENDENCY_INSTRUCTIONS);
1642 }
1643
1644 void
schedule_instructions_post_ra()1645 fs_visitor::schedule_instructions_post_ra()
1646 {
1647 const bool post_reg_alloc = true;
1648 const int grf_count = reg_unit(devinfo) * grf_used;
1649
1650 void *mem_ctx = ralloc_context(NULL);
1651
1652 fs_instruction_scheduler sched(mem_ctx, this, grf_count, first_non_payload_grf,
1653 cfg->num_blocks, post_reg_alloc);
1654 sched.run(SCHEDULE_POST);
1655
1656 ralloc_free(mem_ctx);
1657
1658 invalidate_analysis(DEPENDENCY_INSTRUCTIONS);
1659 }
1660