1 /*
2 * Copyright 2022 Alyssa Rosenzweig
3 * Copyright 2021 Collabora, Ltd.
4 * Copyright 2014 Valve Corporation
5 * SPDX-License-Identifier: MIT
6 */
7
8 #include "util/compiler.h"
9 #include "agx_builder.h"
10
11 #define XXH_INLINE_ALL
12 #include "util/xxhash.h"
13
14 /*
15 * This pass handles CSE'ing repeated expressions created in the process of
16 * translating from NIR. Also, currently this is intra-block only, to make it
17 * work over multiple block we'd need to bring forward dominance calculation.
18 */
19
20 static inline uint32_t
HASH(uint32_t hash,unsigned data)21 HASH(uint32_t hash, unsigned data)
22 {
23 return XXH32(&data, sizeof(data), hash);
24 }
25
26 /* Hash an instruction. XXH32 isn't too speedy, so this is hotspot. */
27 static uint32_t
hash_instr(const void * data)28 hash_instr(const void *data)
29 {
30 const agx_instr *I = data;
31 uint32_t hash = 0;
32
33 /* Explicitly skip destinations, except for size and type */
34 agx_foreach_dest(I, d) {
35 hash = HASH(hash, ((uint32_t)I->dest[d].type) |
36 (((uint32_t)I->dest[d].size) << 16));
37 }
38
39 /* Hash the source array as-is */
40 hash = XXH32(I->src, sizeof(agx_index) * I->nr_srcs, hash);
41
42 /* Hash everything else in the instruction starting from the opcode */
43 hash = XXH32(&I->op, sizeof(agx_instr) - offsetof(agx_instr, op), hash);
44
45 return hash;
46 }
47
48 static bool
instrs_equal(const void * _i1,const void * _i2)49 instrs_equal(const void *_i1, const void *_i2)
50 {
51 const agx_instr *i1 = _i1, *i2 = _i2;
52
53 if (i1->op != i2->op)
54 return false;
55 if (i1->nr_srcs != i2->nr_srcs)
56 return false;
57 if (i1->nr_dests != i2->nr_dests)
58 return false;
59
60 /* Explicitly skip everything but size and type */
61 agx_foreach_dest(i1, d) {
62 if (i1->dest[d].type != i2->dest[d].type)
63 return false;
64 if (i1->dest[d].size != i2->dest[d].size)
65 return false;
66 }
67
68 agx_foreach_src(i1, s) {
69 agx_index s1 = i1->src[s], s2 = i2->src[s];
70
71 if (memcmp(&s1, &s2, sizeof(s1)) != 0)
72 return false;
73 }
74
75 if (i1->imm != i2->imm)
76 return false;
77 if (i1->invert_cond != i2->invert_cond)
78 return false;
79 if (i1->dim != i2->dim)
80 return false;
81 if (i1->offset != i2->offset)
82 return false;
83 if (i1->shadow != i2->shadow)
84 return false;
85 if (i1->shift != i2->shift)
86 return false;
87 if (i1->saturate != i2->saturate)
88 return false;
89 if (i1->mask != i2->mask)
90 return false;
91
92 return true;
93 }
94
95 /* Determines what instructions the above routines have to handle */
96 static bool
instr_can_cse(const agx_instr * I)97 instr_can_cse(const agx_instr *I)
98 {
99 return agx_opcodes_info[I->op].can_eliminate &&
100 agx_opcodes_info[I->op].can_reorder;
101 }
102
103 void
agx_opt_cse(agx_context * ctx)104 agx_opt_cse(agx_context *ctx)
105 {
106 struct set *instr_set = _mesa_set_create(NULL, hash_instr, instrs_equal);
107 agx_index *replacement = malloc(sizeof(agx_index) * ctx->alloc);
108
109 agx_foreach_block(ctx, block) {
110 memset(replacement, 0, sizeof(agx_index) * ctx->alloc);
111 _mesa_set_clear(instr_set, NULL);
112
113 agx_foreach_instr_in_block(block, instr) {
114 /* Rewrite as we go so we converge locally in 1 iteration */
115 agx_foreach_ssa_src(instr, s) {
116 agx_index repl = replacement[instr->src[s].value];
117 if (!agx_is_null(repl))
118 agx_replace_src(instr, s, repl);
119 }
120
121 if (!instr_can_cse(instr))
122 continue;
123
124 bool found;
125 struct set_entry *entry =
126 _mesa_set_search_or_add(instr_set, instr, &found);
127 if (found) {
128 const agx_instr *match = entry->key;
129
130 agx_foreach_dest(instr, d) {
131 replacement[instr->dest[d].value] = match->dest[d];
132 }
133 }
134 }
135 }
136
137 free(replacement);
138 _mesa_set_destroy(instr_set, NULL);
139 }
140