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 "elk_eu.h"
29 #include "elk_fs.h"
30 #include "elk_fs_live_variables.h"
31 #include "elk_vec4.h"
32 #include "elk_cfg.h"
33 #include "elk_shader.h"
34 #include <new>
35
36 using namespace elk;
37
38 /** @file elk_fs_schedule_instructions.cpp
39 *
40 * List scheduling of FS instructions.
41 *
42 * The basic model of the list scheduler is to take a basic block,
43 * compute a DAG of the dependencies (RAW ordering with latency, WAW
44 * ordering with latency, WAR ordering), and make a list of the DAG heads.
45 * Heuristically pick a DAG head, then put all the children that are
46 * now DAG heads into the list of things to schedule.
47 *
48 * The heuristic is the important part. We're trying to be cheap,
49 * since actually computing the optimal scheduling is NP complete.
50 * What we do is track a "current clock". When we schedule a node, we
51 * update the earliest-unblocked clock time of its children, and
52 * increment the clock. Then, when trying to schedule, we just pick
53 * the earliest-unblocked instruction to schedule.
54 *
55 * Note that often there will be many things which could execute
56 * immediately, and there are a range of heuristic options to choose
57 * from in picking among those.
58 */
59
60 static bool debug = false;
61
62 class elk_instruction_scheduler;
63 struct elk_schedule_node_child;
64
65 class elk_schedule_node : public exec_node
66 {
67 public:
68 void set_latency_gfx4();
69 void set_latency_gfx7(const struct elk_isa_info *isa);
70
71 elk_backend_instruction *inst;
72 elk_schedule_node_child *children;
73 int children_count;
74 int children_cap;
75 int initial_parent_count;
76 int initial_unblocked_time;
77 int latency;
78
79 /**
80 * This is the sum of the instruction's latency plus the maximum delay of
81 * its children, or just the issue_time if it's a leaf node.
82 */
83 int delay;
84
85 /**
86 * Preferred exit node among the (direct or indirect) successors of this
87 * node. Among the scheduler nodes blocked by this node, this will be the
88 * one that may cause earliest program termination, or NULL if none of the
89 * successors is an exit node.
90 */
91 elk_schedule_node *exit;
92
93 /**
94 * How many cycles this instruction takes to issue.
95 *
96 * Instructions in gen hardware are handled one simd4 vector at a time,
97 * with 1 cycle per vector dispatched. Thus SIMD8 pixel shaders take 2
98 * cycles to dispatch and SIMD16 (compressed) instructions take 4.
99 */
100 int issue_time;
101
102 /* Temporary data used during the scheduling process. */
103 struct {
104 int parent_count;
105 int unblocked_time;
106
107 /**
108 * Which iteration of pushing groups of children onto the candidates list
109 * this node was a part of.
110 */
111 unsigned cand_generation;
112 } tmp;
113 };
114
115 struct elk_schedule_node_child {
116 elk_schedule_node *n;
117 int effective_latency;
118 };
119
120 static inline void
reset_node_tmp(elk_schedule_node * n)121 reset_node_tmp(elk_schedule_node *n)
122 {
123 n->tmp.parent_count = n->initial_parent_count;
124 n->tmp.unblocked_time = n->initial_unblocked_time;
125 n->tmp.cand_generation = 0;
126 }
127
128 /**
129 * Lower bound of the scheduling time after which one of the instructions
130 * blocked by this node may lead to program termination.
131 *
132 * exit_unblocked_time() determines a strict partial ordering relation '«' on
133 * the set of scheduler nodes as follows:
134 *
135 * n « m <-> exit_unblocked_time(n) < exit_unblocked_time(m)
136 *
137 * which can be used to heuristically order nodes according to how early they
138 * can unblock an exit node and lead to program termination.
139 */
140 static inline int
exit_tmp_unblocked_time(const elk_schedule_node * n)141 exit_tmp_unblocked_time(const elk_schedule_node *n)
142 {
143 return n->exit ? n->exit->tmp.unblocked_time : INT_MAX;
144 }
145
146 static inline int
exit_initial_unblocked_time(const elk_schedule_node * n)147 exit_initial_unblocked_time(const elk_schedule_node *n)
148 {
149 return n->exit ? n->exit->initial_unblocked_time : INT_MAX;
150 }
151
152 void
set_latency_gfx4()153 elk_schedule_node::set_latency_gfx4()
154 {
155 int chans = 8;
156 int math_latency = 22;
157
158 switch (inst->opcode) {
159 case ELK_SHADER_OPCODE_RCP:
160 this->latency = 1 * chans * math_latency;
161 break;
162 case ELK_SHADER_OPCODE_RSQ:
163 this->latency = 2 * chans * math_latency;
164 break;
165 case ELK_SHADER_OPCODE_INT_QUOTIENT:
166 case ELK_SHADER_OPCODE_SQRT:
167 case ELK_SHADER_OPCODE_LOG2:
168 /* full precision log. partial is 2. */
169 this->latency = 3 * chans * math_latency;
170 break;
171 case ELK_SHADER_OPCODE_INT_REMAINDER:
172 case ELK_SHADER_OPCODE_EXP2:
173 /* full precision. partial is 3, same throughput. */
174 this->latency = 4 * chans * math_latency;
175 break;
176 case ELK_SHADER_OPCODE_POW:
177 this->latency = 8 * chans * math_latency;
178 break;
179 case ELK_SHADER_OPCODE_SIN:
180 case ELK_SHADER_OPCODE_COS:
181 /* minimum latency, max is 12 rounds. */
182 this->latency = 5 * chans * math_latency;
183 break;
184 default:
185 this->latency = 2;
186 break;
187 }
188 }
189
190 void
set_latency_gfx7(const struct elk_isa_info * isa)191 elk_schedule_node::set_latency_gfx7(const struct elk_isa_info *isa)
192 {
193 const bool is_haswell = isa->devinfo->verx10 == 75;
194
195 switch (inst->opcode) {
196 case ELK_OPCODE_MAD:
197 /* 2 cycles
198 * (since the last two src operands are in different register banks):
199 * 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 };
200 *
201 * 3 cycles on IVB, 4 on HSW
202 * (since the last two src operands are in the same register bank):
203 * 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 };
204 *
205 * 18 cycles on IVB, 16 on HSW
206 * (since the last two src operands are in different register banks):
207 * 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 };
208 * mov(8) null g4<4,5,1>F { align16 WE_normal 1Q };
209 *
210 * 20 cycles on IVB, 18 on HSW
211 * (since the last two src operands are in the same register bank):
212 * 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 };
213 * mov(8) null g4<4,4,1>F { align16 WE_normal 1Q };
214 */
215
216 /* Our register allocator doesn't know about register banks, so use the
217 * higher latency.
218 */
219 latency = is_haswell ? 16 : 18;
220 break;
221
222 case ELK_OPCODE_LRP:
223 /* 2 cycles
224 * (since the last two src operands are in different register banks):
225 * 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 };
226 *
227 * 3 cycles on IVB, 4 on HSW
228 * (since the last two src operands are in the same register bank):
229 * 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 };
230 *
231 * 16 cycles on IVB, 14 on HSW
232 * (since the last two src operands are in different register banks):
233 * 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 };
234 * mov(8) null g4<4,4,1>F { align16 WE_normal 1Q };
235 *
236 * 16 cycles
237 * (since the last two src operands are in the same register bank):
238 * 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 };
239 * mov(8) null g4<4,4,1>F { align16 WE_normal 1Q };
240 */
241
242 /* Our register allocator doesn't know about register banks, so use the
243 * higher latency.
244 */
245 latency = 14;
246 break;
247
248 case ELK_SHADER_OPCODE_RCP:
249 case ELK_SHADER_OPCODE_RSQ:
250 case ELK_SHADER_OPCODE_SQRT:
251 case ELK_SHADER_OPCODE_LOG2:
252 case ELK_SHADER_OPCODE_EXP2:
253 case ELK_SHADER_OPCODE_SIN:
254 case ELK_SHADER_OPCODE_COS:
255 /* 2 cycles:
256 * math inv(8) g4<1>F g2<0,1,0>F null { align1 WE_normal 1Q };
257 *
258 * 18 cycles:
259 * math inv(8) g4<1>F g2<0,1,0>F null { align1 WE_normal 1Q };
260 * mov(8) null g4<8,8,1>F { align1 WE_normal 1Q };
261 *
262 * Same for exp2, log2, rsq, sqrt, sin, cos.
263 */
264 latency = is_haswell ? 14 : 16;
265 break;
266
267 case ELK_SHADER_OPCODE_POW:
268 /* 2 cycles:
269 * math pow(8) g4<1>F g2<0,1,0>F g2.1<0,1,0>F { align1 WE_normal 1Q };
270 *
271 * 26 cycles:
272 * math pow(8) g4<1>F g2<0,1,0>F g2.1<0,1,0>F { align1 WE_normal 1Q };
273 * mov(8) null g4<8,8,1>F { align1 WE_normal 1Q };
274 */
275 latency = is_haswell ? 22 : 24;
276 break;
277
278 case ELK_SHADER_OPCODE_TEX:
279 case ELK_SHADER_OPCODE_TXD:
280 case ELK_SHADER_OPCODE_TXF:
281 case ELK_SHADER_OPCODE_TXF_LZ:
282 case ELK_SHADER_OPCODE_TXL:
283 case ELK_SHADER_OPCODE_TXL_LZ:
284 /* 18 cycles:
285 * mov(8) g115<1>F 0F { align1 WE_normal 1Q };
286 * mov(8) g114<1>F 0F { align1 WE_normal 1Q };
287 * send(8) g4<1>UW g114<8,8,1>F
288 * sampler (10, 0, 0, 1) mlen 2 rlen 4 { align1 WE_normal 1Q };
289 *
290 * 697 +/-49 cycles (min 610, n=26):
291 * mov(8) g115<1>F 0F { align1 WE_normal 1Q };
292 * mov(8) g114<1>F 0F { align1 WE_normal 1Q };
293 * send(8) g4<1>UW g114<8,8,1>F
294 * sampler (10, 0, 0, 1) mlen 2 rlen 4 { align1 WE_normal 1Q };
295 * mov(8) null g4<8,8,1>F { align1 WE_normal 1Q };
296 *
297 * So the latency on our first texture load of the batchbuffer takes
298 * ~700 cycles, since the caches are cold at that point.
299 *
300 * 840 +/- 92 cycles (min 720, n=25):
301 * mov(8) g115<1>F 0F { align1 WE_normal 1Q };
302 * mov(8) g114<1>F 0F { align1 WE_normal 1Q };
303 * send(8) g4<1>UW g114<8,8,1>F
304 * sampler (10, 0, 0, 1) mlen 2 rlen 4 { align1 WE_normal 1Q };
305 * mov(8) null g4<8,8,1>F { align1 WE_normal 1Q };
306 * send(8) g4<1>UW g114<8,8,1>F
307 * sampler (10, 0, 0, 1) mlen 2 rlen 4 { align1 WE_normal 1Q };
308 * mov(8) null g4<8,8,1>F { align1 WE_normal 1Q };
309 *
310 * On the second load, it takes just an extra ~140 cycles, and after
311 * accounting for the 14 cycles of the MOV's latency, that makes ~130.
312 *
313 * 683 +/- 49 cycles (min = 602, n=47):
314 * mov(8) g115<1>F 0F { align1 WE_normal 1Q };
315 * mov(8) g114<1>F 0F { align1 WE_normal 1Q };
316 * send(8) g4<1>UW g114<8,8,1>F
317 * sampler (10, 0, 0, 1) mlen 2 rlen 4 { align1 WE_normal 1Q };
318 * send(8) g50<1>UW g114<8,8,1>F
319 * sampler (10, 0, 0, 1) mlen 2 rlen 4 { align1 WE_normal 1Q };
320 * mov(8) null g4<8,8,1>F { align1 WE_normal 1Q };
321 *
322 * The unit appears to be pipelined, since this matches up with the
323 * cache-cold case, despite there being two loads here. If you replace
324 * the g4 in the MOV to null with g50, it's still 693 +/- 52 (n=39).
325 *
326 * So, take some number between the cache-hot 140 cycles and the
327 * cache-cold 700 cycles. No particular tuning was done on this.
328 *
329 * I haven't done significant testing of the non-TEX opcodes. TXL at
330 * least looked about the same as TEX.
331 */
332 latency = 200;
333 break;
334
335 case ELK_SHADER_OPCODE_TXS:
336 /* Testing textureSize(sampler2D, 0), one load was 420 +/- 41
337 * cycles (n=15):
338 * mov(8) g114<1>UD 0D { align1 WE_normal 1Q };
339 * send(8) g6<1>UW g114<8,8,1>F
340 * sampler (10, 0, 10, 1) mlen 1 rlen 4 { align1 WE_normal 1Q };
341 * mov(16) g6<1>F g6<8,8,1>D { align1 WE_normal 1Q };
342 *
343 *
344 * Two loads was 535 +/- 30 cycles (n=19):
345 * mov(16) g114<1>UD 0D { align1 WE_normal 1H };
346 * send(16) g6<1>UW g114<8,8,1>F
347 * sampler (10, 0, 10, 2) mlen 2 rlen 8 { align1 WE_normal 1H };
348 * mov(16) g114<1>UD 0D { align1 WE_normal 1H };
349 * mov(16) g6<1>F g6<8,8,1>D { align1 WE_normal 1H };
350 * send(16) g8<1>UW g114<8,8,1>F
351 * sampler (10, 0, 10, 2) mlen 2 rlen 8 { align1 WE_normal 1H };
352 * mov(16) g8<1>F g8<8,8,1>D { align1 WE_normal 1H };
353 * add(16) g6<1>F g6<8,8,1>F g8<8,8,1>F { align1 WE_normal 1H };
354 *
355 * Since the only caches that should matter are just the
356 * instruction/state cache containing the surface state, assume that we
357 * always have hot caches.
358 */
359 latency = 100;
360 break;
361
362 case ELK_FS_OPCODE_VARYING_PULL_CONSTANT_LOAD_GFX4:
363 case ELK_FS_OPCODE_UNIFORM_PULL_CONSTANT_LOAD:
364 case ELK_VS_OPCODE_PULL_CONSTANT_LOAD:
365 /* testing using varying-index pull constants:
366 *
367 * 16 cycles:
368 * mov(8) g4<1>D g2.1<0,1,0>F { align1 WE_normal 1Q };
369 * send(8) g4<1>F g4<8,8,1>D
370 * data (9, 2, 3) mlen 1 rlen 1 { align1 WE_normal 1Q };
371 *
372 * ~480 cycles:
373 * mov(8) g4<1>D g2.1<0,1,0>F { align1 WE_normal 1Q };
374 * send(8) g4<1>F g4<8,8,1>D
375 * data (9, 2, 3) mlen 1 rlen 1 { align1 WE_normal 1Q };
376 * mov(8) null g4<8,8,1>F { align1 WE_normal 1Q };
377 *
378 * ~620 cycles:
379 * mov(8) g4<1>D g2.1<0,1,0>F { align1 WE_normal 1Q };
380 * send(8) g4<1>F g4<8,8,1>D
381 * data (9, 2, 3) mlen 1 rlen 1 { align1 WE_normal 1Q };
382 * mov(8) null g4<8,8,1>F { align1 WE_normal 1Q };
383 * send(8) g4<1>F g4<8,8,1>D
384 * data (9, 2, 3) mlen 1 rlen 1 { align1 WE_normal 1Q };
385 * mov(8) null g4<8,8,1>F { align1 WE_normal 1Q };
386 *
387 * So, if it's cache-hot, it's about 140. If it's cache cold, it's
388 * about 460. We expect to mostly be cache hot, so pick something more
389 * in that direction.
390 */
391 latency = 200;
392 break;
393
394 case ELK_SHADER_OPCODE_GFX7_SCRATCH_READ:
395 /* Testing a load from offset 0, that had been previously written:
396 *
397 * send(8) g114<1>UW g0<8,8,1>F data (0, 0, 0) mlen 1 rlen 1 { align1 WE_normal 1Q };
398 * mov(8) null g114<8,8,1>F { align1 WE_normal 1Q };
399 *
400 * The cycles spent seemed to be grouped around 40-50 (as low as 38),
401 * then around 140. Presumably this is cache hit vs miss.
402 */
403 latency = 50;
404 break;
405
406 case ELK_VEC4_OPCODE_UNTYPED_ATOMIC:
407 /* See GFX7_DATAPORT_DC_UNTYPED_ATOMIC_OP */
408 latency = 14000;
409 break;
410
411 case ELK_VEC4_OPCODE_UNTYPED_SURFACE_READ:
412 case ELK_VEC4_OPCODE_UNTYPED_SURFACE_WRITE:
413 /* See also GFX7_DATAPORT_DC_UNTYPED_SURFACE_READ */
414 latency = is_haswell ? 300 : 600;
415 break;
416
417 case ELK_SHADER_OPCODE_SEND:
418 switch (inst->sfid) {
419 case ELK_SFID_SAMPLER: {
420 unsigned msg_type = (inst->desc >> 12) & 0x1f;
421 switch (msg_type) {
422 case GFX5_SAMPLER_MESSAGE_SAMPLE_RESINFO:
423 case GFX6_SAMPLER_MESSAGE_SAMPLE_SAMPLEINFO:
424 /* See also ELK_SHADER_OPCODE_TXS */
425 latency = 100;
426 break;
427
428 default:
429 /* See also ELK_SHADER_OPCODE_TEX */
430 latency = 200;
431 break;
432 }
433 break;
434 }
435
436 case GFX6_SFID_DATAPORT_CONSTANT_CACHE:
437 /* See ELK_FS_OPCODE_UNIFORM_PULL_CONSTANT_LOAD */
438 latency = 200;
439 break;
440
441 case GFX6_SFID_DATAPORT_RENDER_CACHE:
442 switch (elk_fb_desc_msg_type(isa->devinfo, inst->desc)) {
443 case GFX7_DATAPORT_RC_TYPED_SURFACE_WRITE:
444 case GFX7_DATAPORT_RC_TYPED_SURFACE_READ:
445 /* See also ELK_SHADER_OPCODE_TYPED_SURFACE_READ */
446 assert(!is_haswell);
447 latency = 600;
448 break;
449
450 case GFX7_DATAPORT_RC_TYPED_ATOMIC_OP:
451 /* See also ELK_SHADER_OPCODE_TYPED_ATOMIC */
452 assert(!is_haswell);
453 latency = 14000;
454 break;
455
456 case GFX6_DATAPORT_WRITE_MESSAGE_RENDER_TARGET_WRITE:
457 /* completely fabricated number */
458 latency = 600;
459 break;
460
461 default:
462 unreachable("Unknown render cache message");
463 }
464 break;
465
466 case GFX7_SFID_DATAPORT_DATA_CACHE:
467 switch ((inst->desc >> 14) & 0x1f) {
468 case ELK_DATAPORT_READ_MESSAGE_OWORD_BLOCK_READ:
469 case GFX7_DATAPORT_DC_UNALIGNED_OWORD_BLOCK_READ:
470 case GFX6_DATAPORT_WRITE_MESSAGE_OWORD_BLOCK_WRITE:
471 /* We have no data for this but assume it's a little faster than
472 * untyped surface read/write.
473 */
474 latency = 200;
475 break;
476
477 case GFX7_DATAPORT_DC_DWORD_SCATTERED_READ:
478 case GFX6_DATAPORT_WRITE_MESSAGE_DWORD_SCATTERED_WRITE:
479 case HSW_DATAPORT_DC_PORT0_BYTE_SCATTERED_READ:
480 case HSW_DATAPORT_DC_PORT0_BYTE_SCATTERED_WRITE:
481 /* We have no data for this but assume it's roughly the same as
482 * untyped surface read/write.
483 */
484 latency = 300;
485 break;
486
487 case GFX7_DATAPORT_DC_UNTYPED_SURFACE_READ:
488 case GFX7_DATAPORT_DC_UNTYPED_SURFACE_WRITE:
489 /* Test code:
490 * mov(8) g112<1>UD 0x00000000UD { align1 WE_all 1Q };
491 * mov(1) g112.7<1>UD g1.7<0,1,0>UD { align1 WE_all };
492 * mov(8) g113<1>UD 0x00000000UD { align1 WE_normal 1Q };
493 * send(8) g4<1>UD g112<8,8,1>UD
494 * data (38, 6, 5) mlen 2 rlen 1 { align1 WE_normal 1Q };
495 * .
496 * . [repeats 8 times]
497 * .
498 * mov(8) g112<1>UD 0x00000000UD { align1 WE_all 1Q };
499 * mov(1) g112.7<1>UD g1.7<0,1,0>UD { align1 WE_all };
500 * mov(8) g113<1>UD 0x00000000UD { align1 WE_normal 1Q };
501 * send(8) g4<1>UD g112<8,8,1>UD
502 * data (38, 6, 5) mlen 2 rlen 1 { align1 WE_normal 1Q };
503 *
504 * Running it 100 times as fragment shader on a 128x128 quad
505 * gives an average latency of 583 cycles per surface read,
506 * standard deviation 0.9%.
507 */
508 assert(!is_haswell);
509 latency = 600;
510 break;
511
512 case GFX7_DATAPORT_DC_UNTYPED_ATOMIC_OP:
513 /* Test code:
514 * mov(8) g112<1>ud 0x00000000ud { align1 WE_all 1Q };
515 * mov(1) g112.7<1>ud g1.7<0,1,0>ud { align1 WE_all };
516 * mov(8) g113<1>ud 0x00000000ud { align1 WE_normal 1Q };
517 * send(8) g4<1>ud g112<8,8,1>ud
518 * data (38, 5, 6) mlen 2 rlen 1 { align1 WE_normal 1Q };
519 *
520 * Running it 100 times as fragment shader on a 128x128 quad
521 * gives an average latency of 13867 cycles per atomic op,
522 * standard deviation 3%. Note that this is a rather
523 * pessimistic estimate, the actual latency in cases with few
524 * collisions between threads and favorable pipelining has been
525 * seen to be reduced by a factor of 100.
526 */
527 assert(!is_haswell);
528 latency = 14000;
529 break;
530
531 default:
532 unreachable("Unknown data cache message");
533 }
534 break;
535
536 case HSW_SFID_DATAPORT_DATA_CACHE_1:
537 switch (elk_dp_desc_msg_type(isa->devinfo, inst->desc)) {
538 case HSW_DATAPORT_DC_PORT1_UNTYPED_SURFACE_READ:
539 case HSW_DATAPORT_DC_PORT1_UNTYPED_SURFACE_WRITE:
540 case HSW_DATAPORT_DC_PORT1_TYPED_SURFACE_READ:
541 case HSW_DATAPORT_DC_PORT1_TYPED_SURFACE_WRITE:
542 case GFX8_DATAPORT_DC_PORT1_A64_UNTYPED_SURFACE_WRITE:
543 case GFX8_DATAPORT_DC_PORT1_A64_UNTYPED_SURFACE_READ:
544 case GFX8_DATAPORT_DC_PORT1_A64_SCATTERED_WRITE:
545 case GFX9_DATAPORT_DC_PORT1_A64_SCATTERED_READ:
546 case GFX8_DATAPORT_DC_PORT1_A64_OWORD_BLOCK_READ:
547 case GFX8_DATAPORT_DC_PORT1_A64_OWORD_BLOCK_WRITE:
548 /* See also GFX7_DATAPORT_DC_UNTYPED_SURFACE_READ */
549 latency = 300;
550 break;
551
552 case HSW_DATAPORT_DC_PORT1_UNTYPED_ATOMIC_OP:
553 case HSW_DATAPORT_DC_PORT1_UNTYPED_ATOMIC_OP_SIMD4X2:
554 case HSW_DATAPORT_DC_PORT1_TYPED_ATOMIC_OP_SIMD4X2:
555 case HSW_DATAPORT_DC_PORT1_TYPED_ATOMIC_OP:
556 case GFX8_DATAPORT_DC_PORT1_A64_UNTYPED_ATOMIC_OP:
557 /* See also GFX7_DATAPORT_DC_UNTYPED_ATOMIC_OP */
558 latency = 14000;
559 break;
560
561 default:
562 unreachable("Unknown data cache message");
563 }
564 break;
565
566 case GFX7_SFID_PIXEL_INTERPOLATOR:
567 latency = 50; /* TODO */
568 break;
569
570 case ELK_SFID_URB:
571 latency = 200;
572 break;
573
574 default:
575 unreachable("Unknown SFID");
576 }
577 break;
578
579 default:
580 /* 2 cycles:
581 * mul(8) g4<1>F g2<0,1,0>F 0.5F { align1 WE_normal 1Q };
582 *
583 * 16 cycles:
584 * mul(8) g4<1>F g2<0,1,0>F 0.5F { align1 WE_normal 1Q };
585 * mov(8) null g4<8,8,1>F { align1 WE_normal 1Q };
586 */
587 latency = 14;
588 break;
589 }
590 }
591
592 class elk_instruction_scheduler {
593 public:
elk_instruction_scheduler(void * mem_ctx,const elk_backend_shader * s,int grf_count,int grf_write_scale,bool post_reg_alloc)594 elk_instruction_scheduler(void *mem_ctx, const elk_backend_shader *s, int grf_count,
595 int grf_write_scale, bool post_reg_alloc):
596 bs(s)
597 {
598 this->mem_ctx = mem_ctx;
599 this->lin_ctx = linear_context(this->mem_ctx);
600 this->grf_count = grf_count;
601 this->post_reg_alloc = post_reg_alloc;
602
603 this->last_grf_write = linear_zalloc_array(lin_ctx, elk_schedule_node *, grf_count * grf_write_scale);
604
605 this->nodes_len = s->cfg->last_block()->end_ip + 1;
606 this->nodes = linear_zalloc_array(lin_ctx, elk_schedule_node, this->nodes_len);
607
608 const struct intel_device_info *devinfo = bs->devinfo;
609 const struct elk_isa_info *isa = &bs->compiler->isa;
610
611 elk_schedule_node *n = nodes;
612 foreach_block_and_inst(block, elk_backend_instruction, inst, s->cfg) {
613 n->inst = inst;
614
615 /* We can't measure Gfx6 timings directly but expect them to be much
616 * closer to Gfx7 than Gfx4.
617 */
618 if (!post_reg_alloc)
619 n->latency = 1;
620 else if (devinfo->ver >= 6)
621 n->set_latency_gfx7(isa);
622 else
623 n->set_latency_gfx4();
624
625 n++;
626 }
627 assert(n == nodes + nodes_len);
628
629 current.block = NULL;
630 current.start = NULL;
631 current.end = NULL;
632 current.len = 0;
633 current.time = 0;
634 current.cand_generation = 0;
635 current.available.make_empty();
636 }
637
638 void add_barrier_deps(elk_schedule_node *n);
639 void add_cross_lane_deps(elk_schedule_node *n);
640 void add_dep(elk_schedule_node *before, elk_schedule_node *after, int latency);
641 void add_dep(elk_schedule_node *before, elk_schedule_node *after);
642
643 void set_current_block(elk_bblock_t *block);
644 void compute_delays();
645 void compute_exits();
646
647 void schedule(elk_schedule_node *chosen);
648 void update_children(elk_schedule_node *chosen);
649
650 void *mem_ctx;
651 linear_ctx *lin_ctx;
652
653 elk_schedule_node *nodes;
654 int nodes_len;
655
656 /* Current block being processed. */
657 struct {
658 elk_bblock_t *block;
659
660 /* Range of nodes in the block. End will point to first node
661 * address after the block, i.e. the range is [start, end).
662 */
663 elk_schedule_node *start;
664 elk_schedule_node *end;
665 int len;
666
667 int scheduled;
668
669 unsigned cand_generation;
670 int time;
671 exec_list available;
672 } current;
673
674 bool post_reg_alloc;
675 int grf_count;
676 const elk_backend_shader *bs;
677
678 /**
679 * Last instruction to have written the grf (or a channel in the grf, for the
680 * scalar backend)
681 */
682 elk_schedule_node **last_grf_write;
683 };
684
685 class elk_fs_instruction_scheduler : public elk_instruction_scheduler
686 {
687 public:
688 elk_fs_instruction_scheduler(void *mem_ctx, const elk_fs_visitor *v, int grf_count, int hw_reg_count,
689 int block_count, bool post_reg_alloc);
690 void calculate_deps();
691 bool is_compressed(const elk_fs_inst *inst);
692 elk_schedule_node *choose_instruction_to_schedule();
693 int calculate_issue_time(elk_backend_instruction *inst);
694
695 void count_reads_remaining(elk_backend_instruction *inst);
696 void setup_liveness(elk_cfg_t *cfg);
697 void update_register_pressure(elk_backend_instruction *inst);
698 int get_register_pressure_benefit(elk_backend_instruction *inst);
699 void clear_last_grf_write();
700
701 void schedule_instructions();
702 void run(instruction_scheduler_mode mode);
703
704 const elk_fs_visitor *v;
705 unsigned hw_reg_count;
706 int reg_pressure;
707 instruction_scheduler_mode mode;
708
709 /*
710 * The register pressure at the beginning of each basic block.
711 */
712
713 int *reg_pressure_in;
714
715 /*
716 * The virtual GRF's whose range overlaps the beginning of each basic block.
717 */
718
719 BITSET_WORD **livein;
720
721 /*
722 * The virtual GRF's whose range overlaps the end of each basic block.
723 */
724
725 BITSET_WORD **liveout;
726
727 /*
728 * The hardware GRF's whose range overlaps the end of each basic block.
729 */
730
731 BITSET_WORD **hw_liveout;
732
733 /*
734 * Whether we've scheduled a write for this virtual GRF yet.
735 */
736
737 bool *written;
738
739 /*
740 * How many reads we haven't scheduled for this virtual GRF yet.
741 */
742
743 int *reads_remaining;
744
745 /*
746 * How many reads we haven't scheduled for this hardware GRF yet.
747 */
748
749 int *hw_reads_remaining;
750
751 };
752
elk_fs_instruction_scheduler(void * mem_ctx,const elk_fs_visitor * v,int grf_count,int hw_reg_count,int block_count,bool post_reg_alloc)753 elk_fs_instruction_scheduler::elk_fs_instruction_scheduler(void *mem_ctx, const elk_fs_visitor *v,
754 int grf_count, int hw_reg_count,
755 int block_count, bool post_reg_alloc)
756 : elk_instruction_scheduler(mem_ctx, v, grf_count, /* grf_write_scale */ 16,
757 post_reg_alloc),
758 v(v)
759 {
760 this->hw_reg_count = hw_reg_count;
761 this->mode = SCHEDULE_NONE;
762 this->reg_pressure = 0;
763
764 if (!post_reg_alloc) {
765 this->reg_pressure_in = linear_zalloc_array(lin_ctx, int, block_count);
766
767 this->livein = linear_alloc_array(lin_ctx, BITSET_WORD *, block_count);
768 for (int i = 0; i < block_count; i++)
769 this->livein[i] = linear_zalloc_array(lin_ctx, BITSET_WORD,
770 BITSET_WORDS(grf_count));
771
772 this->liveout = linear_alloc_array(lin_ctx, BITSET_WORD *, block_count);
773 for (int i = 0; i < block_count; i++)
774 this->liveout[i] = linear_zalloc_array(lin_ctx, BITSET_WORD,
775 BITSET_WORDS(grf_count));
776
777 this->hw_liveout = linear_alloc_array(lin_ctx, BITSET_WORD *, block_count);
778 for (int i = 0; i < block_count; i++)
779 this->hw_liveout[i] = linear_zalloc_array(lin_ctx, BITSET_WORD,
780 BITSET_WORDS(hw_reg_count));
781
782 setup_liveness(v->cfg);
783
784 this->written = linear_alloc_array(lin_ctx, bool, grf_count);
785
786 this->reads_remaining = linear_alloc_array(lin_ctx, int, grf_count);
787
788 this->hw_reads_remaining = linear_alloc_array(lin_ctx, int, hw_reg_count);
789 } else {
790 this->reg_pressure_in = NULL;
791 this->livein = NULL;
792 this->liveout = NULL;
793 this->hw_liveout = NULL;
794 this->written = NULL;
795 this->reads_remaining = NULL;
796 this->hw_reads_remaining = NULL;
797 }
798
799 foreach_block(block, v->cfg) {
800 set_current_block(block);
801
802 for (elk_schedule_node *n = current.start; n < current.end; n++)
803 n->issue_time = calculate_issue_time(n->inst);
804
805 calculate_deps();
806 compute_delays();
807 compute_exits();
808 }
809 }
810
811 static bool
is_src_duplicate(elk_fs_inst * inst,int src)812 is_src_duplicate(elk_fs_inst *inst, int src)
813 {
814 for (int i = 0; i < src; i++)
815 if (inst->src[i].equals(inst->src[src]))
816 return true;
817
818 return false;
819 }
820
821 void
count_reads_remaining(elk_backend_instruction * be)822 elk_fs_instruction_scheduler::count_reads_remaining(elk_backend_instruction *be)
823 {
824 assert(reads_remaining);
825
826 elk_fs_inst *inst = (elk_fs_inst *)be;
827
828 for (int i = 0; i < inst->sources; i++) {
829 if (is_src_duplicate(inst, i))
830 continue;
831
832 if (inst->src[i].file == VGRF) {
833 reads_remaining[inst->src[i].nr]++;
834 } else if (inst->src[i].file == FIXED_GRF) {
835 if (inst->src[i].nr >= hw_reg_count)
836 continue;
837
838 for (unsigned j = 0; j < regs_read(inst, i); j++)
839 hw_reads_remaining[inst->src[i].nr + j]++;
840 }
841 }
842 }
843
844 void
setup_liveness(elk_cfg_t * cfg)845 elk_fs_instruction_scheduler::setup_liveness(elk_cfg_t *cfg)
846 {
847 const fs_live_variables &live = v->live_analysis.require();
848
849 /* First, compute liveness on a per-GRF level using the in/out sets from
850 * liveness calculation.
851 */
852 for (int block = 0; block < cfg->num_blocks; block++) {
853 for (int i = 0; i < live.num_vars; i++) {
854 if (BITSET_TEST(live.block_data[block].livein, i)) {
855 int vgrf = live.vgrf_from_var[i];
856 if (!BITSET_TEST(livein[block], vgrf)) {
857 reg_pressure_in[block] += v->alloc.sizes[vgrf];
858 BITSET_SET(livein[block], vgrf);
859 }
860 }
861
862 if (BITSET_TEST(live.block_data[block].liveout, i))
863 BITSET_SET(liveout[block], live.vgrf_from_var[i]);
864 }
865 }
866
867 /* Now, extend the live in/live out sets for when a range crosses a block
868 * boundary, which matches what our register allocator/interference code
869 * does to account for force_writemask_all and incompatible exec_mask's.
870 */
871 for (int block = 0; block < cfg->num_blocks - 1; block++) {
872 for (int i = 0; i < grf_count; i++) {
873 if (live.vgrf_start[i] <= cfg->blocks[block]->end_ip &&
874 live.vgrf_end[i] >= cfg->blocks[block + 1]->start_ip) {
875 if (!BITSET_TEST(livein[block + 1], i)) {
876 reg_pressure_in[block + 1] += v->alloc.sizes[i];
877 BITSET_SET(livein[block + 1], i);
878 }
879
880 BITSET_SET(liveout[block], i);
881 }
882 }
883 }
884
885 int *payload_last_use_ip = ralloc_array(NULL, int, hw_reg_count);
886 v->calculate_payload_ranges(hw_reg_count, payload_last_use_ip);
887
888 for (unsigned i = 0; i < hw_reg_count; i++) {
889 if (payload_last_use_ip[i] == -1)
890 continue;
891
892 for (int block = 0; block < cfg->num_blocks; block++) {
893 if (cfg->blocks[block]->start_ip <= payload_last_use_ip[i])
894 reg_pressure_in[block]++;
895
896 if (cfg->blocks[block]->end_ip <= payload_last_use_ip[i])
897 BITSET_SET(hw_liveout[block], i);
898 }
899 }
900
901 ralloc_free(payload_last_use_ip);
902 }
903
904 void
update_register_pressure(elk_backend_instruction * be)905 elk_fs_instruction_scheduler::update_register_pressure(elk_backend_instruction *be)
906 {
907 assert(reads_remaining);
908
909 elk_fs_inst *inst = (elk_fs_inst *)be;
910
911 if (inst->dst.file == VGRF) {
912 written[inst->dst.nr] = true;
913 }
914
915 for (int i = 0; i < inst->sources; i++) {
916 if (is_src_duplicate(inst, i))
917 continue;
918
919 if (inst->src[i].file == VGRF) {
920 reads_remaining[inst->src[i].nr]--;
921 } else if (inst->src[i].file == FIXED_GRF &&
922 inst->src[i].nr < hw_reg_count) {
923 for (unsigned off = 0; off < regs_read(inst, i); off++)
924 hw_reads_remaining[inst->src[i].nr + off]--;
925 }
926 }
927 }
928
929 int
get_register_pressure_benefit(elk_backend_instruction * be)930 elk_fs_instruction_scheduler::get_register_pressure_benefit(elk_backend_instruction *be)
931 {
932 elk_fs_inst *inst = (elk_fs_inst *)be;
933 int benefit = 0;
934 const int block_idx = current.block->num;
935
936 if (inst->dst.file == VGRF) {
937 if (!BITSET_TEST(livein[block_idx], inst->dst.nr) &&
938 !written[inst->dst.nr])
939 benefit -= v->alloc.sizes[inst->dst.nr];
940 }
941
942 for (int i = 0; i < inst->sources; i++) {
943 if (is_src_duplicate(inst, i))
944 continue;
945
946 if (inst->src[i].file == VGRF &&
947 !BITSET_TEST(liveout[block_idx], inst->src[i].nr) &&
948 reads_remaining[inst->src[i].nr] == 1)
949 benefit += v->alloc.sizes[inst->src[i].nr];
950
951 if (inst->src[i].file == FIXED_GRF &&
952 inst->src[i].nr < hw_reg_count) {
953 for (unsigned off = 0; off < regs_read(inst, i); off++) {
954 int reg = inst->src[i].nr + off;
955 if (!BITSET_TEST(hw_liveout[block_idx], reg) &&
956 hw_reads_remaining[reg] == 1) {
957 benefit++;
958 }
959 }
960 }
961 }
962
963 return benefit;
964 }
965
966 class elk_vec4_instruction_scheduler : public elk_instruction_scheduler
967 {
968 public:
969 elk_vec4_instruction_scheduler(void *mem_ctx, const vec4_visitor *v, int grf_count);
970 void calculate_deps();
971 elk_schedule_node *choose_instruction_to_schedule();
972 const vec4_visitor *v;
973
974 void run();
975 };
976
elk_vec4_instruction_scheduler(void * mem_ctx,const vec4_visitor * v,int grf_count)977 elk_vec4_instruction_scheduler::elk_vec4_instruction_scheduler(void *mem_ctx, const vec4_visitor *v,
978 int grf_count)
979 : elk_instruction_scheduler(mem_ctx, v, grf_count, /* grf_write_scale */ 1,
980 /* post_reg_alloc */ true),
981 v(v)
982 {
983 }
984
985 void
set_current_block(elk_bblock_t * block)986 elk_instruction_scheduler::set_current_block(elk_bblock_t *block)
987 {
988 current.block = block;
989 current.start = nodes + block->start_ip;
990 current.len = block->end_ip - block->start_ip + 1;
991 current.end = current.start + current.len;
992 current.time = 0;
993 current.scheduled = 0;
994 current.cand_generation = 1;
995 }
996
997 /** Computation of the delay member of each node. */
998 void
compute_delays()999 elk_instruction_scheduler::compute_delays()
1000 {
1001 for (elk_schedule_node *n = current.end - 1; n >= current.start; n--) {
1002 if (!n->children_count) {
1003 n->delay = n->issue_time;
1004 } else {
1005 for (int i = 0; i < n->children_count; i++) {
1006 assert(n->children[i].n->delay);
1007 n->delay = MAX2(n->delay, n->latency + n->children[i].n->delay);
1008 }
1009 }
1010 }
1011 }
1012
1013 void
compute_exits()1014 elk_instruction_scheduler::compute_exits()
1015 {
1016 /* Calculate a lower bound of the scheduling time of each node in the
1017 * graph. This is analogous to the node's critical path but calculated
1018 * from the top instead of from the bottom of the block.
1019 */
1020 for (elk_schedule_node *n = current.start; n < current.end; n++) {
1021 for (int i = 0; i < n->children_count; i++) {
1022 elk_schedule_node_child *child = &n->children[i];
1023 child->n->initial_unblocked_time =
1024 MAX2(child->n->initial_unblocked_time,
1025 n->initial_unblocked_time + n->issue_time + child->effective_latency);
1026 }
1027 }
1028
1029 /* Calculate the exit of each node by induction based on the exit nodes of
1030 * its children. The preferred exit of a node is the one among the exit
1031 * nodes of its children which can be unblocked first according to the
1032 * optimistic unblocked time estimate calculated above.
1033 */
1034 for (elk_schedule_node *n = current.end - 1; n >= current.start; n--) {
1035 n->exit = (n->inst->opcode == ELK_OPCODE_HALT ? n : NULL);
1036
1037 for (int i = 0; i < n->children_count; i++) {
1038 if (exit_initial_unblocked_time(n->children[i].n) < exit_initial_unblocked_time(n))
1039 n->exit = n->children[i].n->exit;
1040 }
1041 }
1042 }
1043
1044 /**
1045 * Add a dependency between two instruction nodes.
1046 *
1047 * The @after node will be scheduled after @before. We will try to
1048 * schedule it @latency cycles after @before, but no guarantees there.
1049 */
1050 void
add_dep(elk_schedule_node * before,elk_schedule_node * after,int latency)1051 elk_instruction_scheduler::add_dep(elk_schedule_node *before, elk_schedule_node *after,
1052 int latency)
1053 {
1054 if (!before || !after)
1055 return;
1056
1057 assert(before != after);
1058
1059 for (int i = 0; i < before->children_count; i++) {
1060 elk_schedule_node_child *child = &before->children[i];
1061 if (child->n == after) {
1062 child->effective_latency = MAX2(child->effective_latency, latency);
1063 return;
1064 }
1065 }
1066
1067 if (before->children_cap <= before->children_count) {
1068 if (before->children_cap < 16)
1069 before->children_cap = 16;
1070 else
1071 before->children_cap *= 2;
1072
1073 before->children = reralloc(mem_ctx, before->children,
1074 elk_schedule_node_child,
1075 before->children_cap);
1076 }
1077
1078 elk_schedule_node_child *child = &before->children[before->children_count];
1079 child->n = after;
1080 child->effective_latency = latency;
1081 before->children_count++;
1082 after->initial_parent_count++;
1083 }
1084
1085 void
add_dep(elk_schedule_node * before,elk_schedule_node * after)1086 elk_instruction_scheduler::add_dep(elk_schedule_node *before, elk_schedule_node *after)
1087 {
1088 if (!before)
1089 return;
1090
1091 add_dep(before, after, before->latency);
1092 }
1093
1094 static bool
is_scheduling_barrier(const elk_backend_instruction * inst)1095 is_scheduling_barrier(const elk_backend_instruction *inst)
1096 {
1097 return inst->opcode == ELK_SHADER_OPCODE_HALT_TARGET ||
1098 inst->is_control_flow() ||
1099 inst->has_side_effects();
1100 }
1101
1102 static bool
has_cross_lane_access(const elk_fs_inst * inst)1103 has_cross_lane_access(const elk_fs_inst *inst)
1104 {
1105 /* FINISHME:
1106 *
1107 * This function is likely incomplete in terms of identify cross lane
1108 * accesses.
1109 */
1110 if (inst->opcode == ELK_SHADER_OPCODE_BROADCAST ||
1111 inst->opcode == ELK_SHADER_OPCODE_READ_SR_REG ||
1112 inst->opcode == ELK_SHADER_OPCODE_CLUSTER_BROADCAST ||
1113 inst->opcode == ELK_SHADER_OPCODE_SHUFFLE ||
1114 inst->opcode == ELK_FS_OPCODE_LOAD_LIVE_CHANNELS ||
1115 inst->opcode == ELK_SHADER_OPCODE_FIND_LAST_LIVE_CHANNEL ||
1116 inst->opcode == ELK_SHADER_OPCODE_FIND_LIVE_CHANNEL)
1117 return true;
1118
1119 for (unsigned s = 0; s < inst->sources; s++) {
1120 if (inst->src[s].file == VGRF) {
1121 if (inst->src[s].stride == 0)
1122 return true;
1123 }
1124 }
1125
1126 return false;
1127 }
1128
1129 /**
1130 * Sometimes we really want this node to execute after everything that
1131 * was before it and before everything that followed it. This adds
1132 * the deps to do so.
1133 */
1134 void
add_barrier_deps(elk_schedule_node * n)1135 elk_instruction_scheduler::add_barrier_deps(elk_schedule_node *n)
1136 {
1137 for (elk_schedule_node *prev = n - 1; prev >= current.start; prev--) {
1138 add_dep(prev, n, 0);
1139 if (is_scheduling_barrier(prev->inst))
1140 break;
1141 }
1142
1143 for (elk_schedule_node *next = n + 1; next < current.end; next++) {
1144 add_dep(n, next, 0);
1145 if (is_scheduling_barrier(next->inst))
1146 break;
1147 }
1148 }
1149
1150 /**
1151 * Because some instructions like HALT can disable lanes, scheduling prior to
1152 * a cross lane access should not be allowed, otherwise we could end up with
1153 * later instructions accessing uninitialized data.
1154 */
1155 void
add_cross_lane_deps(elk_schedule_node * n)1156 elk_instruction_scheduler::add_cross_lane_deps(elk_schedule_node *n)
1157 {
1158 for (elk_schedule_node *prev = n - 1; prev >= current.start; prev--) {
1159 if (has_cross_lane_access((elk_fs_inst*)prev->inst))
1160 add_dep(prev, n, 0);
1161 }
1162 }
1163
1164 /* instruction scheduling needs to be aware of when an MRF write
1165 * actually writes 2 MRFs.
1166 */
1167 bool
is_compressed(const elk_fs_inst * inst)1168 elk_fs_instruction_scheduler::is_compressed(const elk_fs_inst *inst)
1169 {
1170 return inst->exec_size == 16;
1171 }
1172
1173 /* Clears last_grf_write to be ready to start calculating deps for a block
1174 * again.
1175 *
1176 * Since pre-ra grf_count scales with instructions, and instructions scale with
1177 * BBs, we don't want to memset all of last_grf_write per block or you'll end up
1178 * O(n^2) with number of blocks. For shaders using softfp64, we get a *lot* of
1179 * blocks.
1180 *
1181 * We don't bother being careful for post-ra, since then grf_count doesn't scale
1182 * with instructions.
1183 */
1184 void
clear_last_grf_write()1185 elk_fs_instruction_scheduler::clear_last_grf_write()
1186 {
1187 if (!post_reg_alloc) {
1188 for (elk_schedule_node *n = current.start; n < current.end; n++) {
1189 elk_fs_inst *inst = (elk_fs_inst *)n->inst;
1190
1191 if (inst->dst.file == VGRF) {
1192 /* Don't bother being careful with regs_written(), quicker to just clear 2 cachelines. */
1193 memset(&last_grf_write[inst->dst.nr * 16], 0, sizeof(*last_grf_write) * 16);
1194 }
1195 }
1196 } else {
1197 memset(last_grf_write, 0, sizeof(*last_grf_write) * grf_count * 16);
1198 }
1199 }
1200
1201 void
calculate_deps()1202 elk_fs_instruction_scheduler::calculate_deps()
1203 {
1204 /* Pre-register-allocation, this tracks the last write per VGRF offset.
1205 * After register allocation, reg_offsets are gone and we track individual
1206 * GRF registers.
1207 */
1208 elk_schedule_node *last_mrf_write[ELK_MAX_MRF_ALL];
1209 elk_schedule_node *last_conditional_mod[8] = {};
1210 elk_schedule_node *last_accumulator_write = NULL;
1211 /* Fixed HW registers are assumed to be separate from the virtual
1212 * GRFs, so they can be tracked separately. We don't really write
1213 * to fixed GRFs much, so don't bother tracking them on a more
1214 * granular level.
1215 */
1216 elk_schedule_node *last_fixed_grf_write = NULL;
1217
1218 memset(last_mrf_write, 0, sizeof(last_mrf_write));
1219
1220 /* top-to-bottom dependencies: RAW and WAW. */
1221 for (elk_schedule_node *n = current.start; n < current.end; n++) {
1222 elk_fs_inst *inst = (elk_fs_inst *)n->inst;
1223
1224 if (is_scheduling_barrier(inst))
1225 add_barrier_deps(n);
1226
1227 if (inst->opcode == ELK_OPCODE_HALT ||
1228 inst->opcode == ELK_SHADER_OPCODE_HALT_TARGET)
1229 add_cross_lane_deps(n);
1230
1231 /* read-after-write deps. */
1232 for (int i = 0; i < inst->sources; i++) {
1233 if (inst->src[i].file == VGRF) {
1234 if (post_reg_alloc) {
1235 for (unsigned r = 0; r < regs_read(inst, i); r++)
1236 add_dep(last_grf_write[inst->src[i].nr + r], n);
1237 } else {
1238 for (unsigned r = 0; r < regs_read(inst, i); r++) {
1239 add_dep(last_grf_write[inst->src[i].nr * 16 +
1240 inst->src[i].offset / REG_SIZE + r], n);
1241 }
1242 }
1243 } else if (inst->src[i].file == FIXED_GRF) {
1244 if (post_reg_alloc) {
1245 for (unsigned r = 0; r < regs_read(inst, i); r++)
1246 add_dep(last_grf_write[inst->src[i].nr + r], n);
1247 } else {
1248 add_dep(last_fixed_grf_write, n);
1249 }
1250 } else if (inst->src[i].is_accumulator()) {
1251 add_dep(last_accumulator_write, n);
1252 } else if (inst->src[i].file == ARF && !inst->src[i].is_null()) {
1253 add_barrier_deps(n);
1254 }
1255 }
1256
1257 if (inst->base_mrf != -1) {
1258 for (int i = 0; i < inst->mlen; i++) {
1259 /* It looks like the MRF regs are released in the send
1260 * instruction once it's sent, not when the result comes
1261 * back.
1262 */
1263 add_dep(last_mrf_write[inst->base_mrf + i], n);
1264 }
1265 }
1266
1267 if (const unsigned mask = inst->flags_read(v->devinfo)) {
1268 assert(mask < (1 << ARRAY_SIZE(last_conditional_mod)));
1269
1270 for (unsigned i = 0; i < ARRAY_SIZE(last_conditional_mod); i++) {
1271 if (mask & (1 << i))
1272 add_dep(last_conditional_mod[i], n);
1273 }
1274 }
1275
1276 if (inst->reads_accumulator_implicitly()) {
1277 add_dep(last_accumulator_write, n);
1278 }
1279
1280 /* write-after-write deps. */
1281 if (inst->dst.file == VGRF) {
1282 if (post_reg_alloc) {
1283 for (unsigned r = 0; r < regs_written(inst); r++) {
1284 add_dep(last_grf_write[inst->dst.nr + r], n);
1285 last_grf_write[inst->dst.nr + r] = n;
1286 }
1287 } else {
1288 for (unsigned r = 0; r < regs_written(inst); r++) {
1289 add_dep(last_grf_write[inst->dst.nr * 16 +
1290 inst->dst.offset / REG_SIZE + r], n);
1291 last_grf_write[inst->dst.nr * 16 +
1292 inst->dst.offset / REG_SIZE + r] = n;
1293 }
1294 }
1295 } else if (inst->dst.file == MRF) {
1296 int reg = inst->dst.nr & ~ELK_MRF_COMPR4;
1297
1298 add_dep(last_mrf_write[reg], n);
1299 last_mrf_write[reg] = n;
1300 if (is_compressed(inst)) {
1301 if (inst->dst.nr & ELK_MRF_COMPR4)
1302 reg += 4;
1303 else
1304 reg++;
1305 add_dep(last_mrf_write[reg], n);
1306 last_mrf_write[reg] = n;
1307 }
1308 } else if (inst->dst.file == FIXED_GRF) {
1309 if (post_reg_alloc) {
1310 for (unsigned r = 0; r < regs_written(inst); r++) {
1311 add_dep(last_grf_write[inst->dst.nr + r], n);
1312 last_grf_write[inst->dst.nr + r] = n;
1313 }
1314 } else {
1315 add_dep(last_fixed_grf_write, n);
1316 last_fixed_grf_write = n;
1317 }
1318 } else if (inst->dst.is_accumulator()) {
1319 add_dep(last_accumulator_write, n);
1320 last_accumulator_write = n;
1321 } else if (inst->dst.file == ARF && !inst->dst.is_null()) {
1322 add_barrier_deps(n);
1323 }
1324
1325 if (inst->mlen > 0 && inst->base_mrf != -1) {
1326 for (unsigned i = 0; i < inst->implied_mrf_writes(); i++) {
1327 add_dep(last_mrf_write[inst->base_mrf + i], n);
1328 last_mrf_write[inst->base_mrf + i] = n;
1329 }
1330 }
1331
1332 if (const unsigned mask = inst->flags_written(v->devinfo)) {
1333 assert(mask < (1 << ARRAY_SIZE(last_conditional_mod)));
1334
1335 for (unsigned i = 0; i < ARRAY_SIZE(last_conditional_mod); i++) {
1336 if (mask & (1 << i)) {
1337 add_dep(last_conditional_mod[i], n, 0);
1338 last_conditional_mod[i] = n;
1339 }
1340 }
1341 }
1342
1343 if (inst->writes_accumulator_implicitly(v->devinfo) &&
1344 !inst->dst.is_accumulator()) {
1345 add_dep(last_accumulator_write, n);
1346 last_accumulator_write = n;
1347 }
1348 }
1349
1350 clear_last_grf_write();
1351
1352 /* bottom-to-top dependencies: WAR */
1353 memset(last_mrf_write, 0, sizeof(last_mrf_write));
1354 memset(last_conditional_mod, 0, sizeof(last_conditional_mod));
1355 last_accumulator_write = NULL;
1356 last_fixed_grf_write = NULL;
1357
1358 for (elk_schedule_node *n = current.end - 1; n >= current.start; n--) {
1359 elk_fs_inst *inst = (elk_fs_inst *)n->inst;
1360
1361 /* write-after-read deps. */
1362 for (int i = 0; i < inst->sources; i++) {
1363 if (inst->src[i].file == VGRF) {
1364 if (post_reg_alloc) {
1365 for (unsigned r = 0; r < regs_read(inst, i); r++)
1366 add_dep(n, last_grf_write[inst->src[i].nr + r], 0);
1367 } else {
1368 for (unsigned r = 0; r < regs_read(inst, i); r++) {
1369 add_dep(n, last_grf_write[inst->src[i].nr * 16 +
1370 inst->src[i].offset / REG_SIZE + r], 0);
1371 }
1372 }
1373 } else if (inst->src[i].file == FIXED_GRF) {
1374 if (post_reg_alloc) {
1375 for (unsigned r = 0; r < regs_read(inst, i); r++)
1376 add_dep(n, last_grf_write[inst->src[i].nr + r], 0);
1377 } else {
1378 add_dep(n, last_fixed_grf_write, 0);
1379 }
1380 } else if (inst->src[i].is_accumulator()) {
1381 add_dep(n, last_accumulator_write, 0);
1382 } else if (inst->src[i].file == ARF && !inst->src[i].is_null()) {
1383 add_barrier_deps(n);
1384 }
1385 }
1386
1387 if (inst->base_mrf != -1) {
1388 for (int i = 0; i < inst->mlen; i++) {
1389 /* It looks like the MRF regs are released in the send
1390 * instruction once it's sent, not when the result comes
1391 * back.
1392 */
1393 add_dep(n, last_mrf_write[inst->base_mrf + i], 2);
1394 }
1395 }
1396
1397 if (const unsigned mask = inst->flags_read(v->devinfo)) {
1398 assert(mask < (1 << ARRAY_SIZE(last_conditional_mod)));
1399
1400 for (unsigned i = 0; i < ARRAY_SIZE(last_conditional_mod); i++) {
1401 if (mask & (1 << i))
1402 add_dep(n, last_conditional_mod[i]);
1403 }
1404 }
1405
1406 if (inst->reads_accumulator_implicitly()) {
1407 add_dep(n, last_accumulator_write);
1408 }
1409
1410 /* Update the things this instruction wrote, so earlier reads
1411 * can mark this as WAR dependency.
1412 */
1413 if (inst->dst.file == VGRF) {
1414 if (post_reg_alloc) {
1415 for (unsigned r = 0; r < regs_written(inst); r++)
1416 last_grf_write[inst->dst.nr + r] = n;
1417 } else {
1418 for (unsigned r = 0; r < regs_written(inst); r++) {
1419 last_grf_write[inst->dst.nr * 16 +
1420 inst->dst.offset / REG_SIZE + r] = n;
1421 }
1422 }
1423 } else if (inst->dst.file == MRF) {
1424 int reg = inst->dst.nr & ~ELK_MRF_COMPR4;
1425
1426 last_mrf_write[reg] = n;
1427
1428 if (is_compressed(inst)) {
1429 if (inst->dst.nr & ELK_MRF_COMPR4)
1430 reg += 4;
1431 else
1432 reg++;
1433
1434 last_mrf_write[reg] = n;
1435 }
1436 } else if (inst->dst.file == FIXED_GRF) {
1437 if (post_reg_alloc) {
1438 for (unsigned r = 0; r < regs_written(inst); r++)
1439 last_grf_write[inst->dst.nr + r] = n;
1440 } else {
1441 last_fixed_grf_write = n;
1442 }
1443 } else if (inst->dst.is_accumulator()) {
1444 last_accumulator_write = n;
1445 } else if (inst->dst.file == ARF && !inst->dst.is_null()) {
1446 add_barrier_deps(n);
1447 }
1448
1449 if (inst->mlen > 0 && inst->base_mrf != -1) {
1450 for (unsigned i = 0; i < inst->implied_mrf_writes(); i++) {
1451 last_mrf_write[inst->base_mrf + i] = n;
1452 }
1453 }
1454
1455 if (const unsigned mask = inst->flags_written(v->devinfo)) {
1456 assert(mask < (1 << ARRAY_SIZE(last_conditional_mod)));
1457
1458 for (unsigned i = 0; i < ARRAY_SIZE(last_conditional_mod); i++) {
1459 if (mask & (1 << i))
1460 last_conditional_mod[i] = n;
1461 }
1462 }
1463
1464 if (inst->writes_accumulator_implicitly(v->devinfo)) {
1465 last_accumulator_write = n;
1466 }
1467 }
1468
1469 clear_last_grf_write();
1470 }
1471
1472 void
calculate_deps()1473 elk_vec4_instruction_scheduler::calculate_deps()
1474 {
1475 elk_schedule_node *last_mrf_write[ELK_MAX_MRF_ALL];
1476 elk_schedule_node *last_conditional_mod = NULL;
1477 elk_schedule_node *last_accumulator_write = NULL;
1478 /* Fixed HW registers are assumed to be separate from the virtual
1479 * GRFs, so they can be tracked separately. We don't really write
1480 * to fixed GRFs much, so don't bother tracking them on a more
1481 * granular level.
1482 */
1483 elk_schedule_node *last_fixed_grf_write = NULL;
1484
1485 memset(last_grf_write, 0, grf_count * sizeof(*last_grf_write));
1486 memset(last_mrf_write, 0, sizeof(last_mrf_write));
1487
1488 /* top-to-bottom dependencies: RAW and WAW. */
1489 for (elk_schedule_node *n = current.start; n < current.end; n++) {
1490 vec4_instruction *inst = (vec4_instruction *)n->inst;
1491
1492 if (is_scheduling_barrier(inst))
1493 add_barrier_deps(n);
1494
1495 /* read-after-write deps. */
1496 for (int i = 0; i < 3; i++) {
1497 if (inst->src[i].file == VGRF) {
1498 for (unsigned j = 0; j < regs_read(inst, i); ++j)
1499 add_dep(last_grf_write[inst->src[i].nr + j], n);
1500 } else if (inst->src[i].file == FIXED_GRF) {
1501 add_dep(last_fixed_grf_write, n);
1502 } else if (inst->src[i].is_accumulator()) {
1503 assert(last_accumulator_write);
1504 add_dep(last_accumulator_write, n);
1505 } else if (inst->src[i].file == ARF && !inst->src[i].is_null()) {
1506 add_barrier_deps(n);
1507 }
1508 }
1509
1510 if (inst->reads_g0_implicitly())
1511 add_dep(last_fixed_grf_write, n);
1512
1513 if (!inst->is_send_from_grf()) {
1514 for (int i = 0; i < inst->mlen; i++) {
1515 /* It looks like the MRF regs are released in the send
1516 * instruction once it's sent, not when the result comes
1517 * back.
1518 */
1519 add_dep(last_mrf_write[inst->base_mrf + i], n);
1520 }
1521 }
1522
1523 if (inst->reads_flag()) {
1524 assert(last_conditional_mod);
1525 add_dep(last_conditional_mod, n);
1526 }
1527
1528 if (inst->reads_accumulator_implicitly()) {
1529 assert(last_accumulator_write);
1530 add_dep(last_accumulator_write, n);
1531 }
1532
1533 /* write-after-write deps. */
1534 if (inst->dst.file == VGRF) {
1535 for (unsigned j = 0; j < regs_written(inst); ++j) {
1536 add_dep(last_grf_write[inst->dst.nr + j], n);
1537 last_grf_write[inst->dst.nr + j] = n;
1538 }
1539 } else if (inst->dst.file == MRF) {
1540 add_dep(last_mrf_write[inst->dst.nr], n);
1541 last_mrf_write[inst->dst.nr] = n;
1542 } else if (inst->dst.file == FIXED_GRF) {
1543 add_dep(last_fixed_grf_write, n);
1544 last_fixed_grf_write = n;
1545 } else if (inst->dst.is_accumulator()) {
1546 add_dep(last_accumulator_write, n);
1547 last_accumulator_write = n;
1548 } else if (inst->dst.file == ARF && !inst->dst.is_null()) {
1549 add_barrier_deps(n);
1550 }
1551
1552 if (inst->mlen > 0 && !inst->is_send_from_grf()) {
1553 for (unsigned i = 0; i < inst->implied_mrf_writes(); i++) {
1554 add_dep(last_mrf_write[inst->base_mrf + i], n);
1555 last_mrf_write[inst->base_mrf + i] = n;
1556 }
1557 }
1558
1559 if (inst->writes_flag(v->devinfo)) {
1560 add_dep(last_conditional_mod, n, 0);
1561 last_conditional_mod = n;
1562 }
1563
1564 if (inst->writes_accumulator_implicitly(v->devinfo) &&
1565 !inst->dst.is_accumulator()) {
1566 add_dep(last_accumulator_write, n);
1567 last_accumulator_write = n;
1568 }
1569 }
1570
1571 /* bottom-to-top dependencies: WAR */
1572 memset(last_grf_write, 0, grf_count * sizeof(*last_grf_write));
1573 memset(last_mrf_write, 0, sizeof(last_mrf_write));
1574 last_conditional_mod = NULL;
1575 last_accumulator_write = NULL;
1576 last_fixed_grf_write = NULL;
1577
1578 for (elk_schedule_node *n = current.end - 1; n >= current.start; n--) {
1579 vec4_instruction *inst = (vec4_instruction *)n->inst;
1580
1581 /* write-after-read deps. */
1582 for (int i = 0; i < 3; i++) {
1583 if (inst->src[i].file == VGRF) {
1584 for (unsigned j = 0; j < regs_read(inst, i); ++j)
1585 add_dep(n, last_grf_write[inst->src[i].nr + j]);
1586 } else if (inst->src[i].file == FIXED_GRF) {
1587 add_dep(n, last_fixed_grf_write);
1588 } else if (inst->src[i].is_accumulator()) {
1589 add_dep(n, last_accumulator_write);
1590 } else if (inst->src[i].file == ARF && !inst->src[i].is_null()) {
1591 add_barrier_deps(n);
1592 }
1593 }
1594
1595 if (!inst->is_send_from_grf()) {
1596 for (int i = 0; i < inst->mlen; i++) {
1597 /* It looks like the MRF regs are released in the send
1598 * instruction once it's sent, not when the result comes
1599 * back.
1600 */
1601 add_dep(n, last_mrf_write[inst->base_mrf + i], 2);
1602 }
1603 }
1604
1605 if (inst->reads_flag()) {
1606 add_dep(n, last_conditional_mod);
1607 }
1608
1609 if (inst->reads_accumulator_implicitly()) {
1610 add_dep(n, last_accumulator_write);
1611 }
1612
1613 /* Update the things this instruction wrote, so earlier reads
1614 * can mark this as WAR dependency.
1615 */
1616 if (inst->dst.file == VGRF) {
1617 for (unsigned j = 0; j < regs_written(inst); ++j)
1618 last_grf_write[inst->dst.nr + j] = n;
1619 } else if (inst->dst.file == MRF) {
1620 last_mrf_write[inst->dst.nr] = n;
1621 } else if (inst->dst.file == FIXED_GRF) {
1622 last_fixed_grf_write = n;
1623 } else if (inst->dst.is_accumulator()) {
1624 last_accumulator_write = n;
1625 } else if (inst->dst.file == ARF && !inst->dst.is_null()) {
1626 add_barrier_deps(n);
1627 }
1628
1629 if (inst->mlen > 0 && !inst->is_send_from_grf()) {
1630 for (unsigned i = 0; i < inst->implied_mrf_writes(); i++) {
1631 last_mrf_write[inst->base_mrf + i] = n;
1632 }
1633 }
1634
1635 if (inst->writes_flag(v->devinfo)) {
1636 last_conditional_mod = n;
1637 }
1638
1639 if (inst->writes_accumulator_implicitly(v->devinfo)) {
1640 last_accumulator_write = n;
1641 }
1642 }
1643 }
1644
1645 elk_schedule_node *
choose_instruction_to_schedule()1646 elk_fs_instruction_scheduler::choose_instruction_to_schedule()
1647 {
1648 elk_schedule_node *chosen = NULL;
1649
1650 if (mode == SCHEDULE_PRE || mode == SCHEDULE_POST) {
1651 int chosen_time = 0;
1652
1653 /* Of the instructions ready to execute or the closest to being ready,
1654 * choose the one most likely to unblock an early program exit, or
1655 * otherwise the oldest one.
1656 */
1657 foreach_in_list(elk_schedule_node, n, ¤t.available) {
1658 if (!chosen ||
1659 exit_tmp_unblocked_time(n) < exit_tmp_unblocked_time(chosen) ||
1660 (exit_tmp_unblocked_time(n) == exit_tmp_unblocked_time(chosen) &&
1661 n->tmp.unblocked_time < chosen_time)) {
1662 chosen = n;
1663 chosen_time = n->tmp.unblocked_time;
1664 }
1665 }
1666 } else {
1667 int chosen_register_pressure_benefit = 0;
1668
1669 /* Before register allocation, we don't care about the latencies of
1670 * instructions. All we care about is reducing live intervals of
1671 * variables so that we can avoid register spilling, or get SIMD16
1672 * shaders which naturally do a better job of hiding instruction
1673 * latency.
1674 */
1675 foreach_in_list(elk_schedule_node, n, ¤t.available) {
1676 elk_fs_inst *inst = (elk_fs_inst *)n->inst;
1677
1678 if (!chosen) {
1679 chosen = n;
1680 chosen_register_pressure_benefit =
1681 get_register_pressure_benefit(chosen->inst);
1682 continue;
1683 }
1684
1685 /* Most important: If we can definitely reduce register pressure, do
1686 * so immediately.
1687 */
1688 int register_pressure_benefit = get_register_pressure_benefit(n->inst);
1689
1690 if (register_pressure_benefit > 0 &&
1691 register_pressure_benefit > chosen_register_pressure_benefit) {
1692 chosen = n;
1693 chosen_register_pressure_benefit = register_pressure_benefit;
1694 continue;
1695 } else if (chosen_register_pressure_benefit > 0 &&
1696 (register_pressure_benefit <
1697 chosen_register_pressure_benefit)) {
1698 continue;
1699 }
1700
1701 if (mode == SCHEDULE_PRE_LIFO) {
1702 /* Prefer instructions that recently became available for
1703 * scheduling. These are the things that are most likely to
1704 * (eventually) make a variable dead and reduce register pressure.
1705 * Typical register pressure estimates don't work for us because
1706 * most of our pressure comes from texturing, where no single
1707 * instruction to schedule will make a vec4 value dead.
1708 */
1709 if (n->tmp.cand_generation > chosen->tmp.cand_generation) {
1710 chosen = n;
1711 chosen_register_pressure_benefit = register_pressure_benefit;
1712 continue;
1713 } else if (n->tmp.cand_generation < chosen->tmp.cand_generation) {
1714 continue;
1715 }
1716
1717 /* On MRF-using chips, prefer non-SEND instructions. If we don't
1718 * do this, then because we prefer instructions that just became
1719 * candidates, we'll end up in a pattern of scheduling a SEND,
1720 * then the MRFs for the next SEND, then the next SEND, then the
1721 * MRFs, etc., without ever consuming the results of a send.
1722 */
1723 if (v->devinfo->ver < 7) {
1724 elk_fs_inst *chosen_inst = (elk_fs_inst *)chosen->inst;
1725
1726 /* We use size_written > 4 * exec_size as our test for the kind
1727 * of send instruction to avoid -- only sends generate many
1728 * regs, and a single-result send is probably actually reducing
1729 * register pressure.
1730 */
1731 if (inst->size_written <= 4 * inst->exec_size &&
1732 chosen_inst->size_written > 4 * chosen_inst->exec_size) {
1733 chosen = n;
1734 chosen_register_pressure_benefit = register_pressure_benefit;
1735 continue;
1736 } else if (inst->size_written > chosen_inst->size_written) {
1737 continue;
1738 }
1739 }
1740 }
1741
1742 /* For instructions pushed on the cands list at the same time, prefer
1743 * the one with the highest delay to the end of the program. This is
1744 * most likely to have its values able to be consumed first (such as
1745 * for a large tree of lowered ubo loads, which appear reversed in
1746 * the instruction stream with respect to when they can be consumed).
1747 */
1748 if (n->delay > chosen->delay) {
1749 chosen = n;
1750 chosen_register_pressure_benefit = register_pressure_benefit;
1751 continue;
1752 } else if (n->delay < chosen->delay) {
1753 continue;
1754 }
1755
1756 /* Prefer the node most likely to unblock an early program exit.
1757 */
1758 if (exit_tmp_unblocked_time(n) < exit_tmp_unblocked_time(chosen)) {
1759 chosen = n;
1760 chosen_register_pressure_benefit = register_pressure_benefit;
1761 continue;
1762 } else if (exit_tmp_unblocked_time(n) > exit_tmp_unblocked_time(chosen)) {
1763 continue;
1764 }
1765
1766 /* If all other metrics are equal, we prefer the first instruction in
1767 * the list (program execution).
1768 */
1769 }
1770 }
1771
1772 return chosen;
1773 }
1774
1775 elk_schedule_node *
choose_instruction_to_schedule()1776 elk_vec4_instruction_scheduler::choose_instruction_to_schedule()
1777 {
1778 elk_schedule_node *chosen = NULL;
1779 int chosen_time = 0;
1780
1781 /* Of the instructions ready to execute or the closest to being ready,
1782 * choose the oldest one.
1783 */
1784 foreach_in_list(elk_schedule_node, n, ¤t.available) {
1785 if (!chosen || n->tmp.unblocked_time < chosen_time) {
1786 chosen = n;
1787 chosen_time = n->tmp.unblocked_time;
1788 }
1789 }
1790
1791 return chosen;
1792 }
1793
1794 int
calculate_issue_time(elk_backend_instruction * inst0)1795 elk_fs_instruction_scheduler::calculate_issue_time(elk_backend_instruction *inst0)
1796 {
1797 const struct elk_isa_info *isa = &v->compiler->isa;
1798 const elk_fs_inst *inst = static_cast<elk_fs_inst *>(inst0);
1799 const unsigned overhead = v->grf_used && elk_has_bank_conflict(isa, inst) ?
1800 DIV_ROUND_UP(inst->dst.component_size(inst->exec_size), REG_SIZE) : 0;
1801 if (is_compressed(inst))
1802 return 4 + overhead;
1803 else
1804 return 2 + overhead;
1805 }
1806
1807 void
schedule(elk_schedule_node * chosen)1808 elk_instruction_scheduler::schedule(elk_schedule_node *chosen)
1809 {
1810 assert(current.scheduled < current.len);
1811 current.scheduled++;
1812
1813 assert(chosen);
1814 chosen->remove();
1815 current.block->instructions.push_tail(chosen->inst);
1816
1817 /* If we expected a delay for scheduling, then bump the clock to reflect
1818 * that. In reality, the hardware will switch to another hyperthread
1819 * and may not return to dispatching our thread for a while even after
1820 * we're unblocked. After this, we have the time when the chosen
1821 * instruction will start executing.
1822 */
1823 current.time = MAX2(current.time, chosen->tmp.unblocked_time);
1824
1825 /* Update the clock for how soon an instruction could start after the
1826 * chosen one.
1827 */
1828 current.time += chosen->issue_time;
1829
1830 if (debug) {
1831 fprintf(stderr, "clock %4d, scheduled: ", current.time);
1832 bs->dump_instruction(chosen->inst);
1833 }
1834 }
1835
1836 void
update_children(elk_schedule_node * chosen)1837 elk_instruction_scheduler::update_children(elk_schedule_node *chosen)
1838 {
1839 /* Now that we've scheduled a new instruction, some of its
1840 * children can be promoted to the list of instructions ready to
1841 * be scheduled. Update the children's unblocked time for this
1842 * DAG edge as we do so.
1843 */
1844 for (int i = chosen->children_count - 1; i >= 0; i--) {
1845 elk_schedule_node_child *child = &chosen->children[i];
1846
1847 child->n->tmp.unblocked_time = MAX2(child->n->tmp.unblocked_time,
1848 current.time + child->effective_latency);
1849
1850 if (debug) {
1851 fprintf(stderr, "\tchild %d, %d parents: ", i, child->n->tmp.parent_count);
1852 bs->dump_instruction(child->n->inst);
1853 }
1854
1855 child->n->tmp.cand_generation = current.cand_generation;
1856 child->n->tmp.parent_count--;
1857 if (child->n->tmp.parent_count == 0) {
1858 if (debug) {
1859 fprintf(stderr, "\t\tnow available\n");
1860 }
1861 current.available.push_head(child->n);
1862 }
1863 }
1864 current.cand_generation++;
1865
1866 /* Shared resource: the mathbox. There's one mathbox per EU on Gfx6+
1867 * but it's more limited pre-gfx6, so if we send something off to it then
1868 * the next math instruction isn't going to make progress until the first
1869 * is done.
1870 */
1871 if (bs->devinfo->ver < 6 && chosen->inst->is_math()) {
1872 foreach_in_list(elk_schedule_node, n, ¤t.available) {
1873 if (n->inst->is_math())
1874 n->tmp.unblocked_time = MAX2(n->tmp.unblocked_time,
1875 current.time + chosen->latency);
1876 }
1877 }
1878 }
1879
1880 void
schedule_instructions()1881 elk_fs_instruction_scheduler::schedule_instructions()
1882 {
1883 if (!post_reg_alloc)
1884 reg_pressure = reg_pressure_in[current.block->num];
1885
1886 assert(current.available.is_empty());
1887 for (elk_schedule_node *n = current.start; n < current.end; n++) {
1888 reset_node_tmp(n);
1889
1890 /* Add DAG heads to the list of available instructions. */
1891 if (n->tmp.parent_count == 0)
1892 current.available.push_tail(n);
1893 }
1894
1895 current.block->instructions.make_empty();
1896
1897 while (!current.available.is_empty()) {
1898 elk_schedule_node *chosen = choose_instruction_to_schedule();
1899 schedule(chosen);
1900
1901 if (!post_reg_alloc) {
1902 reg_pressure -= get_register_pressure_benefit(chosen->inst);
1903 update_register_pressure(chosen->inst);
1904 if (debug)
1905 fprintf(stderr, "(register pressure %d)\n", reg_pressure);
1906 }
1907
1908 update_children(chosen);
1909 }
1910 }
1911
1912 void
run(instruction_scheduler_mode mode)1913 elk_fs_instruction_scheduler::run(instruction_scheduler_mode mode)
1914 {
1915 this->mode = mode;
1916
1917 if (debug && !post_reg_alloc) {
1918 fprintf(stderr, "\nInstructions before scheduling (reg_alloc %d)\n",
1919 post_reg_alloc);
1920 bs->dump_instructions();
1921 }
1922
1923 if (!post_reg_alloc) {
1924 memset(reads_remaining, 0, grf_count * sizeof(*reads_remaining));
1925 memset(hw_reads_remaining, 0, hw_reg_count * sizeof(*hw_reads_remaining));
1926 memset(written, 0, grf_count * sizeof(*written));
1927 }
1928
1929 foreach_block(block, v->cfg) {
1930 set_current_block(block);
1931
1932 if (!post_reg_alloc) {
1933 for (elk_schedule_node *n = current.start; n < current.end; n++)
1934 count_reads_remaining(n->inst);
1935 }
1936
1937 schedule_instructions();
1938 }
1939
1940 if (debug && !post_reg_alloc) {
1941 fprintf(stderr, "\nInstructions after scheduling (reg_alloc %d)\n",
1942 post_reg_alloc);
1943 bs->dump_instructions();
1944 }
1945 }
1946
1947 void
run()1948 elk_vec4_instruction_scheduler::run()
1949 {
1950 foreach_block(block, v->cfg) {
1951 set_current_block(block);
1952
1953 for (elk_schedule_node *n = current.start; n < current.end; n++) {
1954 /* We always execute as two vec4s in parallel. */
1955 n->issue_time = 2;
1956 }
1957
1958 calculate_deps();
1959
1960 compute_delays();
1961 compute_exits();
1962
1963 assert(current.available.is_empty());
1964 for (elk_schedule_node *n = current.start; n < current.end; n++) {
1965 reset_node_tmp(n);
1966
1967 /* Add DAG heads to the list of available instructions. */
1968 if (n->tmp.parent_count == 0)
1969 current.available.push_tail(n);
1970 }
1971
1972 current.block->instructions.make_empty();
1973
1974 while (!current.available.is_empty()) {
1975 elk_schedule_node *chosen = choose_instruction_to_schedule();
1976 schedule(chosen);
1977 update_children(chosen);
1978 }
1979 }
1980 }
1981
1982 elk_fs_instruction_scheduler *
prepare_scheduler(void * mem_ctx)1983 elk_fs_visitor::prepare_scheduler(void *mem_ctx)
1984 {
1985 const int grf_count = alloc.count;
1986
1987 elk_fs_instruction_scheduler *empty = rzalloc(mem_ctx, elk_fs_instruction_scheduler);
1988 return new (empty) elk_fs_instruction_scheduler(mem_ctx, this, grf_count, first_non_payload_grf,
1989 cfg->num_blocks, /* post_reg_alloc */ false);
1990 }
1991
1992 void
schedule_instructions_pre_ra(elk_fs_instruction_scheduler * sched,instruction_scheduler_mode mode)1993 elk_fs_visitor::schedule_instructions_pre_ra(elk_fs_instruction_scheduler *sched,
1994 instruction_scheduler_mode mode)
1995 {
1996 if (mode == SCHEDULE_NONE)
1997 return;
1998
1999 sched->run(mode);
2000
2001 invalidate_analysis(DEPENDENCY_INSTRUCTIONS);
2002 }
2003
2004 void
schedule_instructions_post_ra()2005 elk_fs_visitor::schedule_instructions_post_ra()
2006 {
2007 const bool post_reg_alloc = true;
2008 const int grf_count = reg_unit(devinfo) * grf_used;
2009
2010 void *mem_ctx = ralloc_context(NULL);
2011
2012 elk_fs_instruction_scheduler sched(mem_ctx, this, grf_count, first_non_payload_grf,
2013 cfg->num_blocks, post_reg_alloc);
2014 sched.run(SCHEDULE_POST);
2015
2016 ralloc_free(mem_ctx);
2017
2018 invalidate_analysis(DEPENDENCY_INSTRUCTIONS);
2019 }
2020
2021 void
opt_schedule_instructions()2022 vec4_visitor::opt_schedule_instructions()
2023 {
2024 void *mem_ctx = ralloc_context(NULL);
2025
2026 elk_vec4_instruction_scheduler sched(mem_ctx, this, prog_data->total_grf);
2027 sched.run();
2028
2029 ralloc_free(mem_ctx);
2030
2031 invalidate_analysis(DEPENDENCY_INSTRUCTIONS);
2032 }
2033