1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
|
/*
* Copyright © 2014 Intel Corporation
*
* Permission is hereby granted, free of charge, to any person obtaining a
* copy of this software and associated documentation files (the "Software"),
* to deal in the Software without restriction, including without limitation
* the rights to use, copy, modify, merge, publish, distribute, sublicense,
* and/or sell copies of the Software, and to permit persons to whom the
* Software is furnished to do so, subject to the following conditions:
*
* The above copyright notice and this permission notice (including the next
* paragraph) shall be included in all copies or substantial portions of the
* Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
* IN THE SOFTWARE.
*
* Authors:
* Jason Ekstrand (jason@jlekstrand.net)
*
*/
#include "nir.h"
/*
* Implements Global Code Motion. A description of GCM can be found in
* "Global Code Motion; Global Value Numbering" by Cliff Click.
* Unfortunately, the algorithm presented in the paper is broken in a
* number of ways. The algorithm used here differs substantially from the
* one in the paper but it is, in my opinion, much easier to read and
* verify correcness.
*/
struct gcm_block_info {
/* Number of loops this block is inside */
unsigned loop_depth;
/* The last instruction inserted into this block. This is used as we
* traverse the instructions and insert them back into the program to
* put them in the right order.
*/
nir_instr *last_instr;
};
struct gcm_state {
nir_function_impl *impl;
nir_instr *instr;
/* Marks all instructions that have been visited by the curren pass */
BITSET_WORD *visited;
/* Marks instructions that are "pinned", i.e. cannot be moved from their
* basic block by code motion */
BITSET_WORD *pinned;
/* The list of non-pinned instructions. As we do the late scheduling,
* we pull non-pinned instructions out of their blocks and place them in
* this list. This saves us from having linked-list problems when we go
* to put instructions back in their blocks.
*/
struct exec_list instrs;
struct gcm_block_info *blocks;
};
/* Recursively walks the CFG and builds the block_info structure */
static void
gcm_build_block_info(struct exec_list *cf_list, struct gcm_state *state,
unsigned loop_depth)
{
foreach_list_typed(nir_cf_node, node, node, cf_list) {
switch (node->type) {
case nir_cf_node_block: {
nir_block *block = nir_cf_node_as_block(node);
state->blocks[block->index].loop_depth = loop_depth;
break;
}
case nir_cf_node_if: {
nir_if *if_stmt = nir_cf_node_as_if(node);
gcm_build_block_info(&if_stmt->then_list, state, loop_depth);
gcm_build_block_info(&if_stmt->else_list, state, loop_depth);
break;
}
case nir_cf_node_loop: {
nir_loop *loop = nir_cf_node_as_loop(node);
gcm_build_block_info(&loop->body, state, loop_depth + 1);
break;
}
default:
unreachable("Invalid CF node type");
}
}
}
/* Walks the instruction list and marks immovable instructions as pinned */
static bool
gcm_pin_instructions_block(nir_block *block, void *void_state)
{
struct gcm_state *state = void_state;
nir_foreach_instr_safe(block, instr) {
bool pinned;
switch (instr->type) {
case nir_instr_type_alu:
switch (nir_instr_as_alu(instr)->op) {
case nir_op_fddx:
case nir_op_fddy:
case nir_op_fddx_fine:
case nir_op_fddy_fine:
case nir_op_fddx_coarse:
case nir_op_fddy_coarse:
/* These can only go in uniform control flow; pin them for now */
pinned = true;
default:
pinned = false;
}
break;
case nir_instr_type_tex:
/* We need to pin texture ops that do partial derivatives */
pinned = nir_instr_as_tex(instr)->op == nir_texop_txd;
break;
case nir_instr_type_load_const:
pinned = false;
break;
case nir_instr_type_intrinsic: {
const nir_intrinsic_info *info =
&nir_intrinsic_infos[nir_instr_as_intrinsic(instr)->intrinsic];
pinned = !(info->flags & NIR_INTRINSIC_CAN_ELIMINATE) ||
!(info->flags & NIR_INTRINSIC_CAN_REORDER);
break;
}
case nir_instr_type_jump:
case nir_instr_type_ssa_undef:
case nir_instr_type_phi:
pinned = true;
break;
default:
unreachable("Invalid instruction type in GCM");
}
if (pinned)
BITSET_SET(state->pinned, instr->index);
}
return true;
}
static void
gcm_schedule_early_instr(nir_instr *instr, struct gcm_state *state);
/** Update an instructions schedule for the given source
*
* This function is called iteratively as we walk the sources of an
* instruction. It ensures that the given source instruction has been
* scheduled and then update this instruction's block if the source
* instruction is lower down the tree.
*/
static bool
gcm_schedule_early_src(nir_src *src, void *void_state)
{
struct gcm_state *state = void_state;
nir_instr *instr = state->instr;
assert(src->is_ssa);
gcm_schedule_early_instr(src->ssa->parent_instr, void_state);
/* While the index isn't a proper dominance depth, it does have the
* property that if A dominates B then A->index <= B->index. Since we
* know that this instruction must have been dominated by all of its
* sources at some point (even if it's gone through value-numbering),
* all of the sources must lie on the same branch of the dominance tree.
* Therefore, we can just go ahead and just compare indices.
*/
if (instr->block->index < src->ssa->parent_instr->block->index)
instr->block = src->ssa->parent_instr->block;
/* We need to restore the state instruction because it may have been
* changed through the gcm_schedule_early_instr call above. Since we
* may still be iterating through sources and future calls to
* gcm_schedule_early_src for the same instruction will still need it.
*/
state->instr = instr;
return true;
}
/** Schedules an instruction early
*
* This function performs a recursive depth-first search starting at the
* given instruction and proceeding through the sources to schedule
* instructions as early as they can possibly go in the dominance tree.
* The instructions are "scheduled" by updating their instr->block field.
*/
static void
gcm_schedule_early_instr(nir_instr *instr, struct gcm_state *state)
{
if (BITSET_TEST(state->visited, instr->index))
return;
BITSET_SET(state->visited, instr->index);
/* Pinned instructions are already scheduled so we don't need to do
* anything. Also, bailing here keeps us from ever following the
* sources of phi nodes which can be back-edges.
*/
if (BITSET_TEST(state->pinned, instr->index))
return;
/* Start with the instruction at the top. As we iterate over the
* sources, it will get moved down as needed.
*/
instr->block = state->impl->start_block;
state->instr = instr;
nir_foreach_src(instr, gcm_schedule_early_src, state);
}
static bool
gcm_schedule_early_block(nir_block *block, void *state)
{
nir_foreach_instr(block, instr)
gcm_schedule_early_instr(instr, state);
return true;
}
static void
gcm_schedule_late_instr(nir_instr *instr, struct gcm_state *state);
/** Schedules the instruction associated with the given SSA def late
*
* This function works by first walking all of the uses of the given SSA
* definition, ensuring that they are scheduled, and then computing the LCA
* (least common ancestor) of its uses. It then schedules this instruction
* as close to the LCA as possible while trying to stay out of loops.
*/
static bool
gcm_schedule_late_def(nir_ssa_def *def, void *void_state)
{
struct gcm_state *state = void_state;
nir_block *lca = NULL;
struct set_entry *entry;
set_foreach(def->uses, entry) {
nir_instr *use_instr = (nir_instr *)entry->key;
gcm_schedule_late_instr(use_instr, state);
/* Phi instructions are a bit special. SSA definitions don't have to
* dominate the sources of the phi nodes that use them; instead, they
* have to dominate the predecessor block corresponding to the phi
* source. We handle this by looking through the sources, finding
* any that are usingg this SSA def, and using those blocks instead
* of the one the phi lives in.
*/
if (use_instr->type == nir_instr_type_phi) {
nir_phi_instr *phi = nir_instr_as_phi(use_instr);
nir_foreach_phi_src(phi, phi_src) {
if (phi_src->src.ssa == def)
lca = nir_dominance_lca(lca, phi_src->pred);
}
} else {
lca = nir_dominance_lca(lca, use_instr->block);
}
}
set_foreach(def->if_uses, entry) {
nir_if *if_stmt = (nir_if *)entry->key;
/* For if statements, we consider the block to be the one immediately
* preceding the if CF node.
*/
nir_block *pred_block =
nir_cf_node_as_block(nir_cf_node_prev(&if_stmt->cf_node));
lca = nir_dominance_lca(lca, pred_block);
}
/* Some instructions may never be used. We'll just leave them scheduled
* early and let dead code clean them up.
*/
if (lca == NULL)
return true;
/* We know have the LCA of all of the uses. If our invariants hold,
* this is dominated by the block that we chose when scheduling early.
* We now walk up the dominance tree and pick the lowest block that is
* as far outside loops as we can get.
*/
nir_block *best = lca;
while (lca != def->parent_instr->block) {
assert(lca);
if (state->blocks[lca->index].loop_depth <
state->blocks[best->index].loop_depth)
best = lca;
lca = lca->imm_dom;
}
def->parent_instr->block = best;
return true;
}
/** Schedules an instruction late
*
* This function performs a depth-first search starting at the given
* instruction and proceeding through its uses to schedule instructions as
* late as they can reasonably go in the dominance tree. The instructions
* are "scheduled" by updating their instr->block field.
*
* The name of this function is actually a bit of a misnomer as it doesn't
* schedule them "as late as possible" as the paper implies. Instead, it
* first finds the lates possible place it can schedule the instruction and
* then possibly schedules it earlier than that. The actual location is as
* far down the tree as we can go while trying to stay out of loops.
*/
static void
gcm_schedule_late_instr(nir_instr *instr, struct gcm_state *state)
{
if (BITSET_TEST(state->visited, instr->index))
return;
BITSET_SET(state->visited, instr->index);
/* Pinned instructions are already scheduled so we don't need to do
* anything. Also, bailing here keeps us from ever following phi nodes
* which can be back-edges.
*/
if (BITSET_TEST(state->pinned, instr->index))
return;
nir_foreach_ssa_def(instr, gcm_schedule_late_def, state);
}
static bool
gcm_schedule_late_block(nir_block *block, void *void_state)
{
struct gcm_state *state = void_state;
nir_foreach_instr_safe(block, instr) {
gcm_schedule_late_instr(instr, state);
if (!BITSET_TEST(state->pinned, instr->index)) {
/* If this is an instruction we can move, go ahead and pull it out
* of the program and put it on the instrs list. This keeps us
* from causing linked list confusion when we're trying to put
* everything in its proper place.
*
* Note that we don't use nir_instr_remove here because that also
* cleans up uses and defs and we want to keep that information.
*/
exec_node_remove(&instr->node);
exec_list_push_tail(&state->instrs, &instr->node);
}
}
return true;
}
static void
gcm_place_instr(nir_instr *instr, struct gcm_state *state);
static bool
gcm_place_instr_def(nir_ssa_def *def, void *state)
{
struct set_entry *entry;
set_foreach(def->uses, entry)
gcm_place_instr((nir_instr *)entry->key, state);
return false;
}
/** Places an instrution back into the program
*
* The earlier passes of GCM simply choose blocks for each instruction and
* otherwise leave them alone. This pass actually places the instructions
* into their chosen blocks.
*
* To do so, we use a standard post-order depth-first search linearization
* algorithm. We walk over the uses of the given instruction and ensure
* that they are placed and then place this instruction. Because we are
* working on multiple blocks at a time, we keep track of the last inserted
* instruction per-block in the state structure's block_info array. When
* we insert an instruction in a block we insert it before the last
* instruction inserted in that block rather than the last instruction
* inserted globally.
*/
static void
gcm_place_instr(nir_instr *instr, struct gcm_state *state)
{
if (BITSET_TEST(state->visited, instr->index))
return;
BITSET_SET(state->visited, instr->index);
/* Phi nodes are our once source of back-edges. Since right now we are
* only doing scheduling within blocks, we don't need to worry about
* them since they are always at the top. Just skip them completely.
*/
if (instr->type == nir_instr_type_phi) {
assert(BITSET_TEST(state->pinned, instr->index));
return;
}
nir_foreach_ssa_def(instr, gcm_place_instr_def, state);
if (BITSET_TEST(state->pinned, instr->index)) {
/* Pinned instructions have an implicit dependence on the pinned
* instructions that come after them in the block. Since the pinned
* instructions will naturally "chain" together, we only need to
* explicitly visit one of them.
*/
for (nir_instr *after = nir_instr_next(instr);
after;
after = nir_instr_next(after)) {
if (BITSET_TEST(state->pinned, after->index)) {
gcm_place_instr(after, state);
break;
}
}
}
struct gcm_block_info *block_info = &state->blocks[instr->block->index];
if (!BITSET_TEST(state->pinned, instr->index)) {
exec_node_remove(&instr->node);
if (block_info->last_instr) {
exec_node_insert_node_before(&block_info->last_instr->node,
&instr->node);
} else {
/* Schedule it at the end of the block */
nir_instr *jump_instr = nir_block_last_instr(instr->block);
if (jump_instr && jump_instr->type == nir_instr_type_jump) {
exec_node_insert_node_before(&jump_instr->node, &instr->node);
} else {
exec_list_push_tail(&instr->block->instr_list, &instr->node);
}
}
}
block_info->last_instr = instr;
}
static void
opt_gcm_impl(nir_function_impl *impl)
{
struct gcm_state state;
unsigned num_instrs = nir_index_instrs(impl);
unsigned instr_words = BITSET_WORDS(num_instrs);
state.impl = impl;
state.instr = NULL;
state.visited = rzalloc_array(NULL, BITSET_WORD, instr_words);
state.pinned = rzalloc_array(NULL, BITSET_WORD, instr_words);
exec_list_make_empty(&state.instrs);
state.blocks = rzalloc_array(NULL, struct gcm_block_info, impl->num_blocks);
nir_metadata_require(impl, nir_metadata_block_index |
nir_metadata_dominance);
gcm_build_block_info(&impl->body, &state, 0);
nir_foreach_block(impl, gcm_pin_instructions_block, &state);
nir_foreach_block(impl, gcm_schedule_early_block, &state);
memset(state.visited, 0, instr_words * sizeof(*state.visited));
nir_foreach_block(impl, gcm_schedule_late_block, &state);
memset(state.visited, 0, instr_words * sizeof(*state.visited));
while (!exec_list_is_empty(&state.instrs)) {
nir_instr *instr = exec_node_data(nir_instr,
state.instrs.tail_pred, node);
gcm_place_instr(instr, &state);
}
ralloc_free(state.visited);
ralloc_free(state.blocks);
}
void
nir_opt_gcm(nir_shader *shader)
{
nir_foreach_overload(shader, overload) {
if (overload->impl)
opt_gcm_impl(overload->impl);
}
}
|