summaryrefslogtreecommitdiff
path: root/src/video_core/shader/ast.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/video_core/shader/ast.cpp')
-rw-r--r--src/video_core/shader/ast.cpp752
1 files changed, 0 insertions, 752 deletions
diff --git a/src/video_core/shader/ast.cpp b/src/video_core/shader/ast.cpp
deleted file mode 100644
index db11144c7..000000000
--- a/src/video_core/shader/ast.cpp
+++ /dev/null
@@ -1,752 +0,0 @@
1// Copyright 2019 yuzu Emulator Project
2// Licensed under GPLv2 or any later version
3// Refer to the license.txt file included.
4
5#include <string>
6#include <string_view>
7
8#include <fmt/format.h>
9
10#include "common/assert.h"
11#include "common/common_types.h"
12#include "video_core/shader/ast.h"
13#include "video_core/shader/expr.h"
14
15namespace VideoCommon::Shader {
16
17ASTZipper::ASTZipper() = default;
18
19void ASTZipper::Init(const ASTNode new_first, const ASTNode parent) {
20 ASSERT(new_first->manager == nullptr);
21 first = new_first;
22 last = new_first;
23
24 ASTNode current = first;
25 while (current) {
26 current->manager = this;
27 current->parent = parent;
28 last = current;
29 current = current->next;
30 }
31}
32
33void ASTZipper::PushBack(const ASTNode new_node) {
34 ASSERT(new_node->manager == nullptr);
35 new_node->previous = last;
36 if (last) {
37 last->next = new_node;
38 }
39 new_node->next.reset();
40 last = new_node;
41 if (!first) {
42 first = new_node;
43 }
44 new_node->manager = this;
45}
46
47void ASTZipper::PushFront(const ASTNode new_node) {
48 ASSERT(new_node->manager == nullptr);
49 new_node->previous.reset();
50 new_node->next = first;
51 if (first) {
52 first->previous = new_node;
53 }
54 if (last == first) {
55 last = new_node;
56 }
57 first = new_node;
58 new_node->manager = this;
59}
60
61void ASTZipper::InsertAfter(const ASTNode new_node, const ASTNode at_node) {
62 ASSERT(new_node->manager == nullptr);
63 if (!at_node) {
64 PushFront(new_node);
65 return;
66 }
67 const ASTNode next = at_node->next;
68 if (next) {
69 next->previous = new_node;
70 }
71 new_node->previous = at_node;
72 if (at_node == last) {
73 last = new_node;
74 }
75 new_node->next = next;
76 at_node->next = new_node;
77 new_node->manager = this;
78}
79
80void ASTZipper::InsertBefore(const ASTNode new_node, const ASTNode at_node) {
81 ASSERT(new_node->manager == nullptr);
82 if (!at_node) {
83 PushBack(new_node);
84 return;
85 }
86 const ASTNode previous = at_node->previous;
87 if (previous) {
88 previous->next = new_node;
89 }
90 new_node->next = at_node;
91 if (at_node == first) {
92 first = new_node;
93 }
94 new_node->previous = previous;
95 at_node->previous = new_node;
96 new_node->manager = this;
97}
98
99void ASTZipper::DetachTail(ASTNode node) {
100 ASSERT(node->manager == this);
101 if (node == first) {
102 first.reset();
103 last.reset();
104 return;
105 }
106
107 last = node->previous;
108 last->next.reset();
109 node->previous.reset();
110
111 ASTNode current = std::move(node);
112 while (current) {
113 current->manager = nullptr;
114 current->parent.reset();
115 current = current->next;
116 }
117}
118
119void ASTZipper::DetachSegment(const ASTNode start, const ASTNode end) {
120 ASSERT(start->manager == this && end->manager == this);
121 if (start == end) {
122 DetachSingle(start);
123 return;
124 }
125 const ASTNode prev = start->previous;
126 const ASTNode post = end->next;
127 if (!prev) {
128 first = post;
129 } else {
130 prev->next = post;
131 }
132 if (!post) {
133 last = prev;
134 } else {
135 post->previous = prev;
136 }
137 start->previous.reset();
138 end->next.reset();
139 ASTNode current = start;
140 bool found = false;
141 while (current) {
142 current->manager = nullptr;
143 current->parent.reset();
144 found |= current == end;
145 current = current->next;
146 }
147 ASSERT(found);
148}
149
150void ASTZipper::DetachSingle(const ASTNode node) {
151 ASSERT(node->manager == this);
152 const ASTNode prev = node->previous;
153 const ASTNode post = node->next;
154 node->previous.reset();
155 node->next.reset();
156 if (!prev) {
157 first = post;
158 } else {
159 prev->next = post;
160 }
161 if (!post) {
162 last = prev;
163 } else {
164 post->previous = prev;
165 }
166
167 node->manager = nullptr;
168 node->parent.reset();
169}
170
171void ASTZipper::Remove(const ASTNode node) {
172 ASSERT(node->manager == this);
173 const ASTNode next = node->next;
174 const ASTNode previous = node->previous;
175 if (previous) {
176 previous->next = next;
177 }
178 if (next) {
179 next->previous = previous;
180 }
181 node->parent.reset();
182 node->manager = nullptr;
183 if (node == last) {
184 last = previous;
185 }
186 if (node == first) {
187 first = next;
188 }
189}
190
191class ExprPrinter final {
192public:
193 void operator()(const ExprAnd& expr) {
194 inner += "( ";
195 std::visit(*this, *expr.operand1);
196 inner += " && ";
197 std::visit(*this, *expr.operand2);
198 inner += ')';
199 }
200
201 void operator()(const ExprOr& expr) {
202 inner += "( ";
203 std::visit(*this, *expr.operand1);
204 inner += " || ";
205 std::visit(*this, *expr.operand2);
206 inner += ')';
207 }
208
209 void operator()(const ExprNot& expr) {
210 inner += "!";
211 std::visit(*this, *expr.operand1);
212 }
213
214 void operator()(const ExprPredicate& expr) {
215 inner += fmt::format("P{}", expr.predicate);
216 }
217
218 void operator()(const ExprCondCode& expr) {
219 inner += fmt::format("CC{}", expr.cc);
220 }
221
222 void operator()(const ExprVar& expr) {
223 inner += fmt::format("V{}", expr.var_index);
224 }
225
226 void operator()(const ExprBoolean& expr) {
227 inner += expr.value ? "true" : "false";
228 }
229
230 void operator()(const ExprGprEqual& expr) {
231 inner += fmt::format("(gpr_{} == {})", expr.gpr, expr.value);
232 }
233
234 const std::string& GetResult() const {
235 return inner;
236 }
237
238private:
239 std::string inner;
240};
241
242class ASTPrinter {
243public:
244 void operator()(const ASTProgram& ast) {
245 scope++;
246 inner += "program {\n";
247 ASTNode current = ast.nodes.GetFirst();
248 while (current) {
249 Visit(current);
250 current = current->GetNext();
251 }
252 inner += "}\n";
253 scope--;
254 }
255
256 void operator()(const ASTIfThen& ast) {
257 ExprPrinter expr_parser{};
258 std::visit(expr_parser, *ast.condition);
259 inner += fmt::format("{}if ({}) {{\n", Indent(), expr_parser.GetResult());
260 scope++;
261 ASTNode current = ast.nodes.GetFirst();
262 while (current) {
263 Visit(current);
264 current = current->GetNext();
265 }
266 scope--;
267 inner += fmt::format("{}}}\n", Indent());
268 }
269
270 void operator()(const ASTIfElse& ast) {
271 inner += Indent();
272 inner += "else {\n";
273
274 scope++;
275 ASTNode current = ast.nodes.GetFirst();
276 while (current) {
277 Visit(current);
278 current = current->GetNext();
279 }
280 scope--;
281
282 inner += Indent();
283 inner += "}\n";
284 }
285
286 void operator()(const ASTBlockEncoded& ast) {
287 inner += fmt::format("{}Block({}, {});\n", Indent(), ast.start, ast.end);
288 }
289
290 void operator()([[maybe_unused]] const ASTBlockDecoded& ast) {
291 inner += Indent();
292 inner += "Block;\n";
293 }
294
295 void operator()(const ASTVarSet& ast) {
296 ExprPrinter expr_parser{};
297 std::visit(expr_parser, *ast.condition);
298 inner += fmt::format("{}V{} := {};\n", Indent(), ast.index, expr_parser.GetResult());
299 }
300
301 void operator()(const ASTLabel& ast) {
302 inner += fmt::format("Label_{}:\n", ast.index);
303 }
304
305 void operator()(const ASTGoto& ast) {
306 ExprPrinter expr_parser{};
307 std::visit(expr_parser, *ast.condition);
308 inner +=
309 fmt::format("{}({}) -> goto Label_{};\n", Indent(), expr_parser.GetResult(), ast.label);
310 }
311
312 void operator()(const ASTDoWhile& ast) {
313 ExprPrinter expr_parser{};
314 std::visit(expr_parser, *ast.condition);
315 inner += fmt::format("{}do {{\n", Indent());
316 scope++;
317 ASTNode current = ast.nodes.GetFirst();
318 while (current) {
319 Visit(current);
320 current = current->GetNext();
321 }
322 scope--;
323 inner += fmt::format("{}}} while ({});\n", Indent(), expr_parser.GetResult());
324 }
325
326 void operator()(const ASTReturn& ast) {
327 ExprPrinter expr_parser{};
328 std::visit(expr_parser, *ast.condition);
329 inner += fmt::format("{}({}) -> {};\n", Indent(), expr_parser.GetResult(),
330 ast.kills ? "discard" : "exit");
331 }
332
333 void operator()(const ASTBreak& ast) {
334 ExprPrinter expr_parser{};
335 std::visit(expr_parser, *ast.condition);
336 inner += fmt::format("{}({}) -> break;\n", Indent(), expr_parser.GetResult());
337 }
338
339 void Visit(const ASTNode& node) {
340 std::visit(*this, *node->GetInnerData());
341 }
342
343 const std::string& GetResult() const {
344 return inner;
345 }
346
347private:
348 std::string_view Indent() {
349 if (space_segment_scope == scope) {
350 return space_segment;
351 }
352
353 // Ensure that we don't exceed our view.
354 ASSERT(scope * 2 < spaces.size());
355
356 space_segment = spaces.substr(0, scope * 2);
357 space_segment_scope = scope;
358 return space_segment;
359 }
360
361 std::string inner{};
362 std::string_view space_segment;
363
364 u32 scope{};
365 u32 space_segment_scope{};
366
367 static constexpr std::string_view spaces{" "};
368};
369
370std::string ASTManager::Print() const {
371 ASTPrinter printer{};
372 printer.Visit(main_node);
373 return printer.GetResult();
374}
375
376ASTManager::ASTManager(bool do_full_decompile, bool disable_else_derivation_)
377 : full_decompile{do_full_decompile}, disable_else_derivation{disable_else_derivation_} {}
378
379ASTManager::~ASTManager() {
380 Clear();
381}
382
383void ASTManager::Init() {
384 main_node = ASTBase::Make<ASTProgram>(ASTNode{});
385 program = std::get_if<ASTProgram>(main_node->GetInnerData());
386 false_condition = MakeExpr<ExprBoolean>(false);
387}
388
389void ASTManager::DeclareLabel(u32 address) {
390 const auto pair = labels_map.emplace(address, labels_count);
391 if (pair.second) {
392 labels_count++;
393 labels.resize(labels_count);
394 }
395}
396
397void ASTManager::InsertLabel(u32 address) {
398 const u32 index = labels_map[address];
399 const ASTNode label = ASTBase::Make<ASTLabel>(main_node, index);
400 labels[index] = label;
401 program->nodes.PushBack(label);
402}
403
404void ASTManager::InsertGoto(Expr condition, u32 address) {
405 const u32 index = labels_map[address];
406 const ASTNode goto_node = ASTBase::Make<ASTGoto>(main_node, std::move(condition), index);
407 gotos.push_back(goto_node);
408 program->nodes.PushBack(goto_node);
409}
410
411void ASTManager::InsertBlock(u32 start_address, u32 end_address) {
412 ASTNode block = ASTBase::Make<ASTBlockEncoded>(main_node, start_address, end_address);
413 program->nodes.PushBack(std::move(block));
414}
415
416void ASTManager::InsertReturn(Expr condition, bool kills) {
417 ASTNode node = ASTBase::Make<ASTReturn>(main_node, std::move(condition), kills);
418 program->nodes.PushBack(std::move(node));
419}
420
421// The decompile algorithm is based on
422// "Taming control flow: A structured approach to eliminating goto statements"
423// by AM Erosa, LJ Hendren 1994. In general, the idea is to get gotos to be
424// on the same structured level as the label which they jump to. This is done,
425// through outward/inward movements and lifting. Once they are at the same
426// level, you can enclose them in an "if" structure or a "do-while" structure.
427void ASTManager::Decompile() {
428 auto it = gotos.begin();
429 while (it != gotos.end()) {
430 const ASTNode goto_node = *it;
431 const auto label_index = goto_node->GetGotoLabel();
432 if (!label_index) {
433 return;
434 }
435 const ASTNode label = labels[*label_index];
436 if (!full_decompile) {
437 // We only decompile backward jumps
438 if (!IsBackwardsJump(goto_node, label)) {
439 it++;
440 continue;
441 }
442 }
443 if (IndirectlyRelated(goto_node, label)) {
444 while (!DirectlyRelated(goto_node, label)) {
445 MoveOutward(goto_node);
446 }
447 }
448 if (DirectlyRelated(goto_node, label)) {
449 u32 goto_level = goto_node->GetLevel();
450 const u32 label_level = label->GetLevel();
451 while (label_level < goto_level) {
452 MoveOutward(goto_node);
453 goto_level--;
454 }
455 // TODO(Blinkhawk): Implement Lifting and Inward Movements
456 }
457 if (label->GetParent() == goto_node->GetParent()) {
458 bool is_loop = false;
459 ASTNode current = goto_node->GetPrevious();
460 while (current) {
461 if (current == label) {
462 is_loop = true;
463 break;
464 }
465 current = current->GetPrevious();
466 }
467
468 if (is_loop) {
469 EncloseDoWhile(goto_node, label);
470 } else {
471 EncloseIfThen(goto_node, label);
472 }
473 it = gotos.erase(it);
474 continue;
475 }
476 it++;
477 }
478 if (full_decompile) {
479 for (const ASTNode& label : labels) {
480 auto& manager = label->GetManager();
481 manager.Remove(label);
482 }
483 labels.clear();
484 } else {
485 auto label_it = labels.begin();
486 while (label_it != labels.end()) {
487 bool can_remove = true;
488 ASTNode label = *label_it;
489 for (const ASTNode& goto_node : gotos) {
490 const auto label_index = goto_node->GetGotoLabel();
491 if (!label_index) {
492 return;
493 }
494 ASTNode& glabel = labels[*label_index];
495 if (glabel == label) {
496 can_remove = false;
497 break;
498 }
499 }
500 if (can_remove) {
501 label->MarkLabelUnused();
502 }
503 }
504 }
505}
506
507bool ASTManager::IsBackwardsJump(ASTNode goto_node, ASTNode label_node) const {
508 u32 goto_level = goto_node->GetLevel();
509 u32 label_level = label_node->GetLevel();
510 while (goto_level > label_level) {
511 goto_level--;
512 goto_node = goto_node->GetParent();
513 }
514 while (label_level > goto_level) {
515 label_level--;
516 label_node = label_node->GetParent();
517 }
518 while (goto_node->GetParent() != label_node->GetParent()) {
519 goto_node = goto_node->GetParent();
520 label_node = label_node->GetParent();
521 }
522 ASTNode current = goto_node->GetPrevious();
523 while (current) {
524 if (current == label_node) {
525 return true;
526 }
527 current = current->GetPrevious();
528 }
529 return false;
530}
531
532bool ASTManager::IndirectlyRelated(const ASTNode& first, const ASTNode& second) const {
533 return !(first->GetParent() == second->GetParent() || DirectlyRelated(first, second));
534}
535
536bool ASTManager::DirectlyRelated(const ASTNode& first, const ASTNode& second) const {
537 if (first->GetParent() == second->GetParent()) {
538 return false;
539 }
540 const u32 first_level = first->GetLevel();
541 const u32 second_level = second->GetLevel();
542 u32 min_level;
543 u32 max_level;
544 ASTNode max;
545 ASTNode min;
546 if (first_level > second_level) {
547 min_level = second_level;
548 min = second;
549 max_level = first_level;
550 max = first;
551 } else {
552 min_level = first_level;
553 min = first;
554 max_level = second_level;
555 max = second;
556 }
557
558 while (max_level > min_level) {
559 max_level--;
560 max = max->GetParent();
561 }
562
563 return min->GetParent() == max->GetParent();
564}
565
566void ASTManager::ShowCurrentState(std::string_view state) const {
567 LOG_CRITICAL(HW_GPU, "\nState {}:\n\n{}\n", state, Print());
568 SanityCheck();
569}
570
571void ASTManager::SanityCheck() const {
572 for (const auto& label : labels) {
573 if (!label->GetParent()) {
574 LOG_CRITICAL(HW_GPU, "Sanity Check Failed");
575 }
576 }
577}
578
579void ASTManager::EncloseDoWhile(ASTNode goto_node, ASTNode label) {
580 ASTZipper& zipper = goto_node->GetManager();
581 const ASTNode loop_start = label->GetNext();
582 if (loop_start == goto_node) {
583 zipper.Remove(goto_node);
584 return;
585 }
586 const ASTNode parent = label->GetParent();
587 const Expr condition = goto_node->GetGotoCondition();
588 zipper.DetachSegment(loop_start, goto_node);
589 const ASTNode do_while_node = ASTBase::Make<ASTDoWhile>(parent, condition);
590 ASTZipper* sub_zipper = do_while_node->GetSubNodes();
591 sub_zipper->Init(loop_start, do_while_node);
592 zipper.InsertAfter(do_while_node, label);
593 sub_zipper->Remove(goto_node);
594}
595
596void ASTManager::EncloseIfThen(ASTNode goto_node, ASTNode label) {
597 ASTZipper& zipper = goto_node->GetManager();
598 const ASTNode if_end = label->GetPrevious();
599 if (if_end == goto_node) {
600 zipper.Remove(goto_node);
601 return;
602 }
603 const ASTNode prev = goto_node->GetPrevious();
604 const Expr condition = goto_node->GetGotoCondition();
605 bool do_else = false;
606 if (!disable_else_derivation && prev->IsIfThen()) {
607 const Expr if_condition = prev->GetIfCondition();
608 do_else = ExprAreEqual(if_condition, condition);
609 }
610 const ASTNode parent = label->GetParent();
611 zipper.DetachSegment(goto_node, if_end);
612 ASTNode if_node;
613 if (do_else) {
614 if_node = ASTBase::Make<ASTIfElse>(parent);
615 } else {
616 Expr neg_condition = MakeExprNot(condition);
617 if_node = ASTBase::Make<ASTIfThen>(parent, neg_condition);
618 }
619 ASTZipper* sub_zipper = if_node->GetSubNodes();
620 sub_zipper->Init(goto_node, if_node);
621 zipper.InsertAfter(if_node, prev);
622 sub_zipper->Remove(goto_node);
623}
624
625void ASTManager::MoveOutward(ASTNode goto_node) {
626 ASTZipper& zipper = goto_node->GetManager();
627 const ASTNode parent = goto_node->GetParent();
628 ASTZipper& zipper2 = parent->GetManager();
629 const ASTNode grandpa = parent->GetParent();
630 const bool is_loop = parent->IsLoop();
631 const bool is_else = parent->IsIfElse();
632 const bool is_if = parent->IsIfThen();
633
634 const ASTNode prev = goto_node->GetPrevious();
635 const ASTNode post = goto_node->GetNext();
636
637 const Expr condition = goto_node->GetGotoCondition();
638 zipper.DetachSingle(goto_node);
639 if (is_loop) {
640 const u32 var_index = NewVariable();
641 const Expr var_condition = MakeExpr<ExprVar>(var_index);
642 const ASTNode var_node = ASTBase::Make<ASTVarSet>(parent, var_index, condition);
643 const ASTNode var_node_init = ASTBase::Make<ASTVarSet>(parent, var_index, false_condition);
644 zipper2.InsertBefore(var_node_init, parent);
645 zipper.InsertAfter(var_node, prev);
646 goto_node->SetGotoCondition(var_condition);
647 const ASTNode break_node = ASTBase::Make<ASTBreak>(parent, var_condition);
648 zipper.InsertAfter(break_node, var_node);
649 } else if (is_if || is_else) {
650 const u32 var_index = NewVariable();
651 const Expr var_condition = MakeExpr<ExprVar>(var_index);
652 const ASTNode var_node = ASTBase::Make<ASTVarSet>(parent, var_index, condition);
653 const ASTNode var_node_init = ASTBase::Make<ASTVarSet>(parent, var_index, false_condition);
654 if (is_if) {
655 zipper2.InsertBefore(var_node_init, parent);
656 } else {
657 zipper2.InsertBefore(var_node_init, parent->GetPrevious());
658 }
659 zipper.InsertAfter(var_node, prev);
660 goto_node->SetGotoCondition(var_condition);
661 if (post) {
662 zipper.DetachTail(post);
663 const ASTNode if_node = ASTBase::Make<ASTIfThen>(parent, MakeExprNot(var_condition));
664 ASTZipper* sub_zipper = if_node->GetSubNodes();
665 sub_zipper->Init(post, if_node);
666 zipper.InsertAfter(if_node, var_node);
667 }
668 } else {
669 UNREACHABLE();
670 }
671 const ASTNode next = parent->GetNext();
672 if (is_if && next && next->IsIfElse()) {
673 zipper2.InsertAfter(goto_node, next);
674 goto_node->SetParent(grandpa);
675 return;
676 }
677 zipper2.InsertAfter(goto_node, parent);
678 goto_node->SetParent(grandpa);
679}
680
681class ASTClearer {
682public:
683 ASTClearer() = default;
684
685 void operator()(const ASTProgram& ast) {
686 ASTNode current = ast.nodes.GetFirst();
687 while (current) {
688 Visit(current);
689 current = current->GetNext();
690 }
691 }
692
693 void operator()(const ASTIfThen& ast) {
694 ASTNode current = ast.nodes.GetFirst();
695 while (current) {
696 Visit(current);
697 current = current->GetNext();
698 }
699 }
700
701 void operator()(const ASTIfElse& ast) {
702 ASTNode current = ast.nodes.GetFirst();
703 while (current) {
704 Visit(current);
705 current = current->GetNext();
706 }
707 }
708
709 void operator()([[maybe_unused]] const ASTBlockEncoded& ast) {}
710
711 void operator()(ASTBlockDecoded& ast) {
712 ast.nodes.clear();
713 }
714
715 void operator()([[maybe_unused]] const ASTVarSet& ast) {}
716
717 void operator()([[maybe_unused]] const ASTLabel& ast) {}
718
719 void operator()([[maybe_unused]] const ASTGoto& ast) {}
720
721 void operator()(const ASTDoWhile& ast) {
722 ASTNode current = ast.nodes.GetFirst();
723 while (current) {
724 Visit(current);
725 current = current->GetNext();
726 }
727 }
728
729 void operator()([[maybe_unused]] const ASTReturn& ast) {}
730
731 void operator()([[maybe_unused]] const ASTBreak& ast) {}
732
733 void Visit(const ASTNode& node) {
734 std::visit(*this, *node->GetInnerData());
735 node->Clear();
736 }
737};
738
739void ASTManager::Clear() {
740 if (!main_node) {
741 return;
742 }
743 ASTClearer clearer{};
744 clearer.Visit(main_node);
745 main_node.reset();
746 program = nullptr;
747 labels_map.clear();
748 labels.clear();
749 gotos.clear();
750}
751
752} // namespace VideoCommon::Shader
HIC SVNT DRACONES