Blender V5.3
gpu_shader_dead_code_elimination.hh
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2026 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
8
9#include "BLI_bit_vector.hh"
10#include "BLI_map.hh"
11#include "BLI_set.hh"
12#include "BLI_vector.hh"
13
15
16namespace blender::gpu {
17
18/* -------------------------------------------------------------------- */
21
22/* Token stream that parses (some) symbols definitions, build a graph of usage and then prune
23 * unused definitions for a given set of entry point functions. */
28
29 private:
30 /* Data to output. Think of it as a lazy string builder. */
31 Vector<StringRef> stream;
32 /* Total output length. */
33 size_t total_length = 0;
34 /* Ranges of character in the stream to remove when constructing the result. */
36
37 /* Simple circular buffer to access last few token data. */
38 class TokenHistoryBuffer {
39 private:
40 std::array<Token, 2> buffer;
41 int head = 0;
42
43 public:
44 TokenHistoryBuffer(Token invalid) : buffer({invalid, invalid}) {}
45
46 void push(Token tok)
47 {
48 buffer[head] = tok;
49 head = (head + 1) % buffer.size();
50 }
51
52 /* Access elements from newest (0) to oldest (count-1). */
53 const Token &operator[](int index) const
54 {
55 BLI_assert(index < buffer.size());
56 int actual_index = (head + buffer.size() - index - 1) % buffer.size();
57 return buffer[actual_index];
58 }
59 } token_history;
60
61 struct FunctionDeclaration {
62 Token type, name, end;
63 };
64
65 struct FunctionGraph {
66 Vector<FunctionDeclaration> declarations;
67 /* Function call (from, to). */
69 } graph;
70
71 TokenAtom current_fn = 0;
72
73 /* State of the parser. Some section have DCE turned off because of unsupported syntax. */
74 bool enabled_ = true;
75
76 int stack_depth = 0;
77
78 const TokenAtom return_atom;
79 const TokenAtom thread_atom;
80 const TokenAtom device_atom;
81
82 /* Bit vector allowing to filter atoms that designate builtin functions or constructors that we
83 * should avoid creating graph for. */
84 bits::BitVector<> builtin_atoms;
85
86 public:
87 PruningStream(Token invalid_tok,
88 TokenAtom return_atom,
89 TokenAtom thread_atom,
90 TokenAtom device_atom,
91 Span<TokenAtom> builtin_atoms)
92 : token_history(invalid_tok),
93 return_atom(return_atom),
94 thread_atom(thread_atom),
95 device_atom(device_atom),
96 /* Reserve enough for all atoms, even generated ones during macro expansions. */
97 builtin_atoms(0x10000)
98 {
99 for (auto atom : builtin_atoms) {
100 /* Atom values can only be separated by at least 2 values. */
101 this->builtin_atoms[atom / 2].set(true);
102 }
103 }
104
105 void set_enabled_parsing(bool value)
106 {
107 enabled_ = value;
108 }
109
115 {
116 if (str.is_empty()) {
117 return *this;
118 }
119
120 if (!stream.is_empty()) {
121 StringRef &last = stream.last();
122 /* Check if the memory addresses are contiguous */
123 if (last.data() + last.size() == str.data()) {
124 last = StringRef(last.data(), last.size() + str.size());
125 }
126 else {
127 stream.append(str);
128 }
129 }
130 else {
131 stream.append(str);
132 }
133
134 total_length += str.size();
135 return *this;
136 }
137
139 {
140 if (!enabled_) {
141 return;
142 }
143 parse_token_impl(set_start_char(tok));
144 }
145
146 BLI_NOINLINE void parse_token_range(const Token start, const Token end)
147 {
148 if (!enabled_) {
149 return;
150 }
151 const char *start_char = start.str_with_whitespace().data();
152
153 Token tok = start;
154
155 /* Process first 2 token to avoid branching in the loop. */
156 parse_token_impl(set_start_char(tok));
157 if (tok == end) {
158 return;
159 }
160 tok = tok.next();
161 parse_token_impl(set_start_char(tok, start_char));
162 if (tok == end) {
163 return;
164 }
165 tok = tok.next();
166
167 blender::IndexRange range(int(end) - int(tok) + 1);
168 Span<TokenType> types(&tok.type(), range.size());
169
170 for (int i : range) {
171 switch (types[i]) {
172 case TokenType::ParOpen:
173 /* Fill the needed history JIT. */
174 {
175 Token curr = tok.next(i);
176 Token prev_1 = curr.prev();
177 while (prev_1.type() == lexit::NewLine) {
178 prev_1 = prev_1.prev();
179 }
180 Token prev_2 = prev_1.prev();
181 while (prev_2.type() == lexit::NewLine) {
182 prev_2 = prev_2.prev();
183 }
184 token_history.push(set_start_char(prev_2, start_char));
185 token_history.push(set_start_char(prev_1, start_char));
186 }
187 process_function();
188 break;
189 case TokenType::BracketOpen:
190 stack_depth += (current_fn != 0);
191 break;
192 case TokenType::BracketClose:
193 stack_depth -= (current_fn != 0);
195 case TokenType::SemiColon:
196 /* Finding a semicolon in global scope after a function signature means that this is
197 * a forward declaration. Step out of function in this case. */
198 register_function_end(set_start_char(tok.next(i), start_char));
199 break;
200 default:
201 break;
202 }
203 }
204
205 /* Register last two tokens. */
206 token_history.push(set_start_char(end.prev(), start_char));
207 token_history.push(set_start_char(end, start_char));
208 }
209
210 std::string str() const
211 {
212 if (total_length == 0) {
213 return {};
214 }
215
216 std::string result;
217 result.reserve(total_length);
218
219 size_t global_offset = 0;
220 const auto *rem_it = removals.begin();
221
222 for (const auto &segment : stream) {
223 size_t seg_idx = 0;
224 /* Process the current segment until we reach its end */
225 while (seg_idx < segment.size()) {
226 size_t current_global_pos = global_offset + seg_idx;
227 /* If no active removals remain, copy the rest of the segment. */
228 if (rem_it == removals.end()) {
229 result.append(segment, seg_idx, std::string::npos);
230 break;
231 }
232
233 auto [r_start, r_end] = *rem_it;
234 /* Safety check: ensure we haven't somehow passed the removal (if unsorted) */
235 BLI_assert(current_global_pos < r_end);
236
237 if (current_global_pos < r_start) {
238 /* We are before the removal starts.
239 * Copy until the segment ends OR the removal starts */
240 size_t len = std::min(size_t(segment.size()) - seg_idx, r_start - current_global_pos);
241 result.append(segment, seg_idx, len);
242 seg_idx += len;
243 continue;
244 }
245
246 /* We are inside the removal range.
247 * Process until the segment ends OR the removal ends */
248 size_t len = std::min(size_t(segment.size()) - seg_idx, r_end - current_global_pos);
249 /* Replace the removed chunk by newlines. */
250 std::string_view chunk(segment.data() + seg_idx, len);
251 size_t newlines = std::count(chunk.begin(), chunk.end(), '\n');
252 result.append(newlines, '\n');
253 seg_idx += len;
254 /* If we reached the end of this removal range, move to the next one */
255 if (global_offset + seg_idx >= r_end) {
256 ++rem_it;
257 }
258 }
259 /* Update global offset before moving to next segment */
260 global_offset += segment.size();
261 }
262
263 return result;
264 }
265
266 void optimize(const Span<TokenAtom> entry_points)
267 {
268 prune_unused_functions(entry_points);
269 }
270
271 private:
272 Token set_start_char(Token tok, const char *start_offset = nullptr)
273 {
274 int offset = start_offset ? tok.str_with_whitespace().data() - start_offset : 0;
275 tok.flag = int32_t(this->total_length + offset);
276 return tok;
277 }
278
279 BLI_INLINE_METHOD void parse_token_impl(const Token tok)
280 {
281 switch (tok.type()) {
282 case TokenType::NewLine:
283 return;
284 case TokenType::ParOpen:
285 process_function();
286 break;
287 case TokenType::BracketOpen:
288 stack_depth += (current_fn != 0);
289 break;
290 case TokenType::BracketClose:
291 stack_depth -= (current_fn != 0);
293 case TokenType::SemiColon:
294 /* Finding a semicolon in global scope after a function signature means that this is
295 * a forward declaration. Step out of function in this case. */
296 register_function_end(tok);
297 break;
298 default:
299 break;
300 }
301 token_history.push(tok);
302 }
303
304 void process_function()
305 {
306 Token name_tok = token_history[0];
307 if (name_tok.type() != TokenType::Word) {
308 return;
309 }
310
311 Token type_tok = token_history[1];
312
313 /* Filter MSL & GLSL specific identifiers that could have confused the parser. */
314 if (type_tok.atom() == thread_atom || type_tok.atom() == device_atom) {
315 return;
316 }
317 if (builtin_atoms[name_tok.atom() / 2]) {
318 return;
319 }
320
321 if (type_tok.type() == TokenType::Word && type_tok.atom() != return_atom) {
322 register_function_declaration(type_tok, name_tok);
323 }
324 else if (current_fn != 0) {
325 register_function_call(name_tok);
326 }
327 }
328
329 BLI_INLINE_METHOD void register_function_end(Token tok)
330 {
331 if (stack_depth == 0 && current_fn != 0) {
332 graph.declarations.last().end = tok;
333 current_fn = 0;
334 }
335 }
336
337 /* Register function declaration at this token position.
338 * Associate ID with the token string if first encountering the symbol.
339 * Does not differentiate overloads. */
340 void register_function_declaration(Token type_tok, Token name_tok)
341 {
342 BLI_assert_msg(graph.declarations.is_empty() ||
343 graph.declarations.last().name.flag != graph.declarations.last().end.flag,
344 "Missing call to register_function_end");
345
346 graph.declarations.append(FunctionDeclaration{type_tok, name_tok, name_tok});
347 current_fn = name_tok.atom();
348 }
349
350 /* Register a function call made inside the body of a function by creating an edge inside the
351 * graph. */
352 void register_function_call(Token name_tok)
353 {
354 graph.edges.append_as(current_fn, name_tok.atom());
355 }
356
357 Map<TokenAtom, Vector<TokenAtom>> build_adjacency()
358 {
359 Map<TokenAtom, Vector<TokenAtom>> adj;
360 adj.reserve(graph.declarations.size());
361 for (const auto &[from, to] : graph.edges) {
362 adj.lookup_or_add_default(from).append(to);
363 }
364 return adj;
365 }
366
367 Set<TokenAtom> compute_used_functions(Span<TokenAtom> &roots)
368 {
369 Set<TokenAtom> used;
370 used.reserve(graph.declarations.size());
371
372 auto adj = build_adjacency();
373
374 std::vector<TokenAtom> stack;
375 stack.reserve(64);
376
377 for (TokenAtom root : roots) {
378 if (used.add(root)) {
379 stack.push_back(root);
380 }
381
382 while (!stack.empty()) {
383 TokenAtom f = stack.back();
384 stack.pop_back();
385
386 const auto *calls = adj.lookup_ptr(f);
387 if (calls == nullptr) {
388 continue;
389 }
390
391 for (TokenAtom callee : *calls) {
392 if (used.add(callee)) {
393 stack.push_back(callee);
394 }
395 }
396 }
397 }
398
399 return used;
400 }
401
402 void prune_unused_functions(Span<TokenAtom> entry_points)
403 {
404 Set<TokenAtom> used = compute_used_functions(entry_points);
405
406 for (auto [type_tok, name_tok, end_tok] : graph.declarations) {
407 if (used.contains(name_tok.atom())) {
408 continue;
409 }
410
411 if (name_tok.flag == end_tok.flag) {
412 removals.clear();
413 BLI_assert("Bug in parser, function name not detected");
414 break;
415 }
416
417 remove_range(type_tok.flag, end_tok.flag + 1);
418 }
419 }
420
421 /* Remove a range of character from the final string but keeping spaces. */
422 void remove_range(int start_char, int end_char)
423 {
424 removals.append_as(start_char, end_char);
425 }
426};
427
429
430} // namespace blender::gpu
#define ATTR_FALLTHROUGH
#define BLI_INLINE_METHOD
#define BLI_assert(a)
#define BLI_NOINLINE
#define BLI_assert_msg(a, msg)
SIMD_FORCE_INLINE btVector3 & operator[](int i)
Get a mutable reference to a row of the matrix as a vector.
constexpr StringRef()
constexpr int64_t size() const
constexpr int64_t size() const
constexpr const char * data() const
ccl_device_inline dual1 len(const ccl_private dual< T > &a)
Definition math_dual.h:263
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
signed int int32_t
Definition BKE_text.h:78
uint16_t TokenAtom
Definition types.hh:159
TokenType
Definition types.hh:41
@ NewLine
Definition types.hh:46
BLI_NOINLINE void parse_token(const Token tok)
BLI_NOINLINE void parse_token_range(const Token start, const Token end)
PruningStream(Token invalid_tok, TokenAtom return_atom, TokenAtom thread_atom, TokenAtom device_atom, Span< TokenAtom > builtin_atoms)
PruningStream & operator<<(StringRef str)
void optimize(const Span< TokenAtom > entry_points)
Token prev(int i=1) const
Definition lexit.hh:376
const TokenType & type() const
Definition lexit.hh:354
std::string_view str_with_whitespace() const
Definition lexit.hh:388
Token next(int i=1) const
Definition lexit.hh:372
int32_t flag
Definition lexit.hh:53