summaryrefslogtreecommitdiff
path: root/src/shader_recompiler/frontend/maxwell/control_flow.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/shader_recompiler/frontend/maxwell/control_flow.cpp')
-rw-r--r--src/shader_recompiler/frontend/maxwell/control_flow.cpp426
1 files changed, 154 insertions, 272 deletions
diff --git a/src/shader_recompiler/frontend/maxwell/control_flow.cpp b/src/shader_recompiler/frontend/maxwell/control_flow.cpp
index 21ee98137..e766b555b 100644
--- a/src/shader_recompiler/frontend/maxwell/control_flow.cpp
+++ b/src/shader_recompiler/frontend/maxwell/control_flow.cpp
@@ -17,38 +17,49 @@
17#include "shader_recompiler/frontend/maxwell/location.h" 17#include "shader_recompiler/frontend/maxwell/location.h"
18 18
19namespace Shader::Maxwell::Flow { 19namespace Shader::Maxwell::Flow {
20namespace {
21struct Compare {
22 bool operator()(const Block& lhs, Location rhs) const noexcept {
23 return lhs.begin < rhs;
24 }
25
26 bool operator()(Location lhs, const Block& rhs) const noexcept {
27 return lhs < rhs.begin;
28 }
29
30 bool operator()(const Block& lhs, const Block& rhs) const noexcept {
31 return lhs.begin < rhs.begin;
32 }
33};
34} // Anonymous namespace
20 35
21static u32 BranchOffset(Location pc, Instruction inst) { 36static u32 BranchOffset(Location pc, Instruction inst) {
22 return pc.Offset() + inst.branch.Offset() + 8; 37 return pc.Offset() + inst.branch.Offset() + 8;
23} 38}
24 39
25static std::array<Block, 2> Split(Block&& block, Location pc, BlockId new_id) { 40static void Split(Block* old_block, Block* new_block, Location pc) {
26 if (pc <= block.begin || pc >= block.end) { 41 if (pc <= old_block->begin || pc >= old_block->end) {
27 throw InvalidArgument("Invalid address to split={}", pc); 42 throw InvalidArgument("Invalid address to split={}", pc);
28 } 43 }
29 return { 44 *new_block = Block{
30 Block{ 45 .begin{pc},
31 .begin{block.begin}, 46 .end{old_block->end},
32 .end{pc}, 47 .end_class{old_block->end_class},
33 .end_class{EndClass::Branch}, 48 .stack{old_block->stack},
34 .id{block.id}, 49 .cond{old_block->cond},
35 .stack{block.stack}, 50 .branch_true{old_block->branch_true},
36 .cond{true}, 51 .branch_false{old_block->branch_false},
37 .branch_true{new_id}, 52 .ir{nullptr},
38 .branch_false{UNREACHABLE_BLOCK_ID}, 53 };
39 .imm_predecessors{}, 54 *old_block = Block{
40 }, 55 .begin{old_block->begin},
41 Block{ 56 .end{pc},
42 .begin{pc}, 57 .end_class{EndClass::Branch},
43 .end{block.end}, 58 .stack{std::move(old_block->stack)},
44 .end_class{block.end_class}, 59 .cond{IR::Condition{true}},
45 .id{new_id}, 60 .branch_true{new_block},
46 .stack{std::move(block.stack)}, 61 .branch_false{nullptr},
47 .cond{block.cond}, 62 .ir{nullptr},
48 .branch_true{block.branch_true},
49 .branch_false{block.branch_false},
50 .imm_predecessors{},
51 },
52 }; 63 };
53} 64}
54 65
@@ -112,7 +123,7 @@ static bool HasFlowTest(Opcode opcode) {
112 123
113static std::string NameOf(const Block& block) { 124static std::string NameOf(const Block& block) {
114 if (block.begin.IsVirtual()) { 125 if (block.begin.IsVirtual()) {
115 return fmt::format("\"Virtual {}\"", block.id); 126 return fmt::format("\"Virtual {}\"", block.begin);
116 } else { 127 } else {
117 return fmt::format("\"{}\"", block.begin); 128 return fmt::format("\"{}\"", block.begin);
118 } 129 }
@@ -158,126 +169,23 @@ bool Block::Contains(Location pc) const noexcept {
158Function::Function(Location start_address) 169Function::Function(Location start_address)
159 : entrypoint{start_address}, labels{{ 170 : entrypoint{start_address}, labels{{
160 .address{start_address}, 171 .address{start_address},
161 .block_id{0}, 172 .block{nullptr},
162 .stack{}, 173 .stack{},
163 }} {} 174 }} {}
164 175
165void Function::BuildBlocksMap() { 176CFG::CFG(Environment& env_, ObjectPool<Block>& block_pool_, Location start_address)
166 const size_t num_blocks{NumBlocks()}; 177 : env{env_}, block_pool{block_pool_} {
167 blocks_map.resize(num_blocks);
168 for (size_t block_index = 0; block_index < num_blocks; ++block_index) {
169 Block& block{blocks_data[block_index]};
170 blocks_map[block.id] = &block;
171 }
172}
173
174void Function::BuildImmediatePredecessors() {
175 for (const Block& block : blocks_data) {
176 if (block.branch_true != UNREACHABLE_BLOCK_ID) {
177 blocks_map[block.branch_true]->imm_predecessors.push_back(block.id);
178 }
179 if (block.branch_false != UNREACHABLE_BLOCK_ID) {
180 blocks_map[block.branch_false]->imm_predecessors.push_back(block.id);
181 }
182 }
183}
184
185void Function::BuildPostOrder() {
186 boost::container::small_vector<BlockId, 0x110> block_stack;
187 post_order_map.resize(NumBlocks());
188
189 Block& first_block{blocks_data[blocks.front()]};
190 first_block.post_order_visited = true;
191 block_stack.push_back(first_block.id);
192
193 const auto visit_branch = [&](BlockId block_id, BlockId branch_id) {
194 if (branch_id == UNREACHABLE_BLOCK_ID) {
195 return false;
196 }
197 if (blocks_map[branch_id]->post_order_visited) {
198 return false;
199 }
200 blocks_map[branch_id]->post_order_visited = true;
201
202 // Calling push_back twice is faster than insert on msvc
203 block_stack.push_back(block_id);
204 block_stack.push_back(branch_id);
205 return true;
206 };
207 while (!block_stack.empty()) {
208 const Block* const block{blocks_map[block_stack.back()]};
209 block_stack.pop_back();
210
211 if (!visit_branch(block->id, block->branch_true) &&
212 !visit_branch(block->id, block->branch_false)) {
213 post_order_map[block->id] = static_cast<u32>(post_order_blocks.size());
214 post_order_blocks.push_back(block->id);
215 }
216 }
217}
218
219void Function::BuildImmediateDominators() {
220 auto transform_block_id{std::views::transform([this](BlockId id) { return blocks_map[id]; })};
221 auto reverse_order_but_first{std::views::reverse | std::views::drop(1) | transform_block_id};
222 auto has_idom{std::views::filter([](Block* block) { return block->imm_dominator; })};
223 auto intersect{[this](Block* finger1, Block* finger2) {
224 while (finger1 != finger2) {
225 while (post_order_map[finger1->id] < post_order_map[finger2->id]) {
226 finger1 = finger1->imm_dominator;
227 }
228 while (post_order_map[finger2->id] < post_order_map[finger1->id]) {
229 finger2 = finger2->imm_dominator;
230 }
231 }
232 return finger1;
233 }};
234 for (Block& block : blocks_data) {
235 block.imm_dominator = nullptr;
236 }
237 Block* const start_block{&blocks_data[blocks.front()]};
238 start_block->imm_dominator = start_block;
239
240 bool changed{true};
241 while (changed) {
242 changed = false;
243 for (Block* const block : post_order_blocks | reverse_order_but_first) {
244 Block* new_idom{};
245 for (Block* predecessor : block->imm_predecessors | transform_block_id | has_idom) {
246 new_idom = new_idom ? intersect(predecessor, new_idom) : predecessor;
247 }
248 changed |= block->imm_dominator != new_idom;
249 block->imm_dominator = new_idom;
250 }
251 }
252}
253
254void Function::BuildDominanceFrontier() {
255 auto transform_block_id{std::views::transform([this](BlockId id) { return blocks_map[id]; })};
256 auto has_enough_predecessors{[](Block& block) { return block.imm_predecessors.size() >= 2; }};
257 for (Block& block : blocks_data | std::views::filter(has_enough_predecessors)) {
258 for (Block* current : block.imm_predecessors | transform_block_id) {
259 while (current != block.imm_dominator) {
260 current->dominance_frontiers.push_back(current->id);
261 current = current->imm_dominator;
262 }
263 }
264 }
265}
266
267CFG::CFG(Environment& env_, Location start_address) : env{env_} {
268 VisitFunctions(start_address);
269
270 for (Function& function : functions) {
271 function.BuildBlocksMap();
272 function.BuildImmediatePredecessors();
273 function.BuildPostOrder();
274 function.BuildImmediateDominators();
275 function.BuildDominanceFrontier();
276 }
277}
278
279void CFG::VisitFunctions(Location start_address) {
280 functions.emplace_back(start_address); 178 functions.emplace_back(start_address);
179 functions.back().labels.back().block = block_pool.Create(Block{
180 .begin{start_address},
181 .end{start_address},
182 .end_class{EndClass::Branch},
183 .stack{},
184 .cond{IR::Condition{true}},
185 .branch_true{nullptr},
186 .branch_false{nullptr},
187 .ir{nullptr},
188 });
281 for (FunctionId function_id = 0; function_id < functions.size(); ++function_id) { 189 for (FunctionId function_id = 0; function_id < functions.size(); ++function_id) {
282 while (!functions[function_id].labels.empty()) { 190 while (!functions[function_id].labels.empty()) {
283 Function& function{functions[function_id]}; 191 Function& function{functions[function_id]};
@@ -294,35 +202,16 @@ void CFG::AnalyzeLabel(FunctionId function_id, Label& label) {
294 return; 202 return;
295 } 203 }
296 // Try to find the next block 204 // Try to find the next block
297 Function* function{&functions[function_id]}; 205 Function* const function{&functions[function_id]};
298 Location pc{label.address}; 206 Location pc{label.address};
299 const auto next{std::upper_bound(function->blocks.begin(), function->blocks.end(), pc, 207 const auto next_it{function->blocks.upper_bound(pc, Compare{})};
300 [function](Location pc, u32 block_index) { 208 const bool is_last{next_it == function->blocks.end()};
301 return pc < function->blocks_data[block_index].begin; 209 Block* const next{is_last ? nullptr : &*next_it};
302 })};
303 const auto next_index{std::distance(function->blocks.begin(), next)};
304 const bool is_last{next == function->blocks.end()};
305 Location next_pc;
306 BlockId next_id{UNREACHABLE_BLOCK_ID};
307 if (!is_last) {
308 next_pc = function->blocks_data[*next].begin;
309 next_id = function->blocks_data[*next].id;
310 }
311 // Insert before the next block 210 // Insert before the next block
312 Block block{ 211 Block* const block{label.block};
313 .begin{pc},
314 .end{pc},
315 .end_class{EndClass::Branch},
316 .id{label.block_id},
317 .stack{std::move(label.stack)},
318 .cond{true},
319 .branch_true{UNREACHABLE_BLOCK_ID},
320 .branch_false{UNREACHABLE_BLOCK_ID},
321 .imm_predecessors{},
322 };
323 // Analyze instructions until it reaches an already visited block or there's a branch 212 // Analyze instructions until it reaches an already visited block or there's a branch
324 bool is_branch{false}; 213 bool is_branch{false};
325 while (is_last || pc < next_pc) { 214 while (!next || pc < next->begin) {
326 is_branch = AnalyzeInst(block, function_id, pc) == AnalysisState::Branch; 215 is_branch = AnalyzeInst(block, function_id, pc) == AnalysisState::Branch;
327 if (is_branch) { 216 if (is_branch) {
328 break; 217 break;
@@ -332,43 +221,36 @@ void CFG::AnalyzeLabel(FunctionId function_id, Label& label) {
332 if (!is_branch) { 221 if (!is_branch) {
333 // If the block finished without a branch, 222 // If the block finished without a branch,
334 // it means that the next instruction is already visited, jump to it 223 // it means that the next instruction is already visited, jump to it
335 block.end = pc; 224 block->end = pc;
336 block.cond = true; 225 block->cond = IR::Condition{true};
337 block.branch_true = next_id; 226 block->branch_true = next;
338 block.branch_false = UNREACHABLE_BLOCK_ID; 227 block->branch_false = nullptr;
339 } 228 }
340 // Function's pointer might be invalid, resolve it again 229 // Function's pointer might be invalid, resolve it again
341 function = &functions[function_id]; 230 // Insert the new block
342 const u32 new_block_index = static_cast<u32>(function->blocks_data.size()); 231 functions[function_id].blocks.insert(*block);
343 function->blocks.insert(function->blocks.begin() + next_index, new_block_index);
344 function->blocks_data.push_back(std::move(block));
345} 232}
346 233
347bool CFG::InspectVisitedBlocks(FunctionId function_id, const Label& label) { 234bool CFG::InspectVisitedBlocks(FunctionId function_id, const Label& label) {
348 const Location pc{label.address}; 235 const Location pc{label.address};
349 Function& function{functions[function_id]}; 236 Function& function{functions[function_id]};
350 const auto it{std::ranges::find_if(function.blocks, [&function, pc](u32 block_index) { 237 const auto it{
351 return function.blocks_data[block_index].Contains(pc); 238 std::ranges::find_if(function.blocks, [pc](auto& block) { return block.Contains(pc); })};
352 })};
353 if (it == function.blocks.end()) { 239 if (it == function.blocks.end()) {
354 // Address has not been visited 240 // Address has not been visited
355 return false; 241 return false;
356 } 242 }
357 Block& block{function.blocks_data[*it]}; 243 Block* const visited_block{&*it};
358 if (block.begin == pc) { 244 if (visited_block->begin == pc) {
359 throw LogicError("Dangling branch"); 245 throw LogicError("Dangling block");
360 } 246 }
361 const u32 first_index{*it}; 247 Block* const new_block{label.block};
362 const u32 second_index{static_cast<u32>(function.blocks_data.size())}; 248 Split(visited_block, new_block, pc);
363 const std::array new_indices{first_index, second_index}; 249 function.blocks.insert(it, *new_block);
364 std::array split_blocks{Split(std::move(block), pc, label.block_id)};
365 function.blocks_data[*it] = std::move(split_blocks[0]);
366 function.blocks_data.push_back(std::move(split_blocks[1]));
367 function.blocks.insert(function.blocks.erase(it), new_indices.begin(), new_indices.end());
368 return true; 250 return true;
369} 251}
370 252
371CFG::AnalysisState CFG::AnalyzeInst(Block& block, FunctionId function_id, Location pc) { 253CFG::AnalysisState CFG::AnalyzeInst(Block* block, FunctionId function_id, Location pc) {
372 const Instruction inst{env.ReadInstruction(pc.Offset())}; 254 const Instruction inst{env.ReadInstruction(pc.Offset())};
373 const Opcode opcode{Decode(inst.raw)}; 255 const Opcode opcode{Decode(inst.raw)};
374 switch (opcode) { 256 switch (opcode) {
@@ -390,12 +272,12 @@ CFG::AnalysisState CFG::AnalyzeInst(Block& block, FunctionId function_id, Locati
390 AnalyzeBRX(block, pc, inst, IsAbsoluteJump(opcode)); 272 AnalyzeBRX(block, pc, inst, IsAbsoluteJump(opcode));
391 break; 273 break;
392 case Opcode::RET: 274 case Opcode::RET:
393 block.end_class = EndClass::Return; 275 block->end_class = EndClass::Return;
394 break; 276 break;
395 default: 277 default:
396 break; 278 break;
397 } 279 }
398 block.end = pc; 280 block->end = pc;
399 return AnalysisState::Branch; 281 return AnalysisState::Branch;
400 case Opcode::BRK: 282 case Opcode::BRK:
401 case Opcode::CONT: 283 case Opcode::CONT:
@@ -404,9 +286,9 @@ CFG::AnalysisState CFG::AnalyzeInst(Block& block, FunctionId function_id, Locati
404 if (!AnalyzeBranch(block, function_id, pc, inst, opcode)) { 286 if (!AnalyzeBranch(block, function_id, pc, inst, opcode)) {
405 return AnalysisState::Continue; 287 return AnalysisState::Continue;
406 } 288 }
407 const auto [stack_pc, new_stack]{block.stack.Pop(OpcodeToken(opcode))}; 289 const auto [stack_pc, new_stack]{block->stack.Pop(OpcodeToken(opcode))};
408 block.branch_true = AddLabel(block, new_stack, stack_pc, function_id); 290 block->branch_true = AddLabel(block, new_stack, stack_pc, function_id);
409 block.end = pc; 291 block->end = pc;
410 return AnalysisState::Branch; 292 return AnalysisState::Branch;
411 } 293 }
412 case Opcode::PBK: 294 case Opcode::PBK:
@@ -414,7 +296,7 @@ CFG::AnalysisState CFG::AnalyzeInst(Block& block, FunctionId function_id, Locati
414 case Opcode::PEXIT: 296 case Opcode::PEXIT:
415 case Opcode::PLONGJMP: 297 case Opcode::PLONGJMP:
416 case Opcode::SSY: 298 case Opcode::SSY:
417 block.stack.Push(OpcodeToken(opcode), BranchOffset(pc, inst)); 299 block->stack.Push(OpcodeToken(opcode), BranchOffset(pc, inst));
418 return AnalysisState::Continue; 300 return AnalysisState::Continue;
419 case Opcode::EXIT: 301 case Opcode::EXIT:
420 return AnalyzeEXIT(block, function_id, pc, inst); 302 return AnalyzeEXIT(block, function_id, pc, inst);
@@ -444,51 +326,51 @@ CFG::AnalysisState CFG::AnalyzeInst(Block& block, FunctionId function_id, Locati
444 return AnalysisState::Branch; 326 return AnalysisState::Branch;
445} 327}
446 328
447void CFG::AnalyzeCondInst(Block& block, FunctionId function_id, Location pc, 329void CFG::AnalyzeCondInst(Block* block, FunctionId function_id, Location pc,
448 EndClass insn_end_class, IR::Condition cond) { 330 EndClass insn_end_class, IR::Condition cond) {
449 if (block.begin != pc) { 331 if (block->begin != pc) {
450 // If the block doesn't start in the conditional instruction 332 // If the block doesn't start in the conditional instruction
451 // mark it as a label to visit it later 333 // mark it as a label to visit it later
452 block.end = pc; 334 block->end = pc;
453 block.cond = true; 335 block->cond = IR::Condition{true};
454 block.branch_true = AddLabel(block, block.stack, pc, function_id); 336 block->branch_true = AddLabel(block, block->stack, pc, function_id);
455 block.branch_false = UNREACHABLE_BLOCK_ID; 337 block->branch_false = nullptr;
456 return; 338 return;
457 } 339 }
458 // Impersonate the visited block with a virtual block 340 // Create a virtual block and a conditional block
459 // Jump from this virtual to the real conditional instruction and the next instruction 341 Block* const conditional_block{block_pool.Create()};
460 Function& function{functions[function_id]}; 342 Block virtual_block{
461 const BlockId conditional_block_id{++function.current_block_id}; 343 .begin{block->begin.Virtual()},
462 function.blocks.push_back(static_cast<u32>(function.blocks_data.size())); 344 .end{block->begin.Virtual()},
463 Block& virtual_block{function.blocks_data.emplace_back(Block{
464 .begin{}, // Virtual block
465 .end{},
466 .end_class{EndClass::Branch}, 345 .end_class{EndClass::Branch},
467 .id{block.id}, // Impersonating 346 .stack{block->stack},
468 .stack{block.stack},
469 .cond{cond}, 347 .cond{cond},
470 .branch_true{conditional_block_id}, 348 .branch_true{conditional_block},
471 .branch_false{UNREACHABLE_BLOCK_ID}, 349 .branch_false{nullptr},
472 .imm_predecessors{}, 350 .ir{nullptr},
473 })}; 351 };
474 // Set the end properties of the conditional instruction and give it a new identity 352 // Save the contents of the visited block in the conditional block
475 Block& conditional_block{block}; 353 *conditional_block = std::move(*block);
476 conditional_block.end = pc; 354 // Impersonate the visited block with a virtual block
477 conditional_block.end_class = insn_end_class; 355 *block = std::move(virtual_block);
478 conditional_block.id = conditional_block_id; 356 // Set the end properties of the conditional instruction
357 conditional_block->end = pc;
358 conditional_block->end_class = insn_end_class;
479 // Add a label to the instruction after the conditional instruction 359 // Add a label to the instruction after the conditional instruction
480 const BlockId endif_block_id{AddLabel(conditional_block, block.stack, pc + 1, function_id)}; 360 Block* const endif_block{AddLabel(conditional_block, block->stack, pc + 1, function_id)};
481 // Branch to the next instruction from the virtual block 361 // Branch to the next instruction from the virtual block
482 virtual_block.branch_false = endif_block_id; 362 block->branch_false = endif_block;
483 // And branch to it from the conditional instruction if it is a branch 363 // And branch to it from the conditional instruction if it is a branch
484 if (insn_end_class == EndClass::Branch) { 364 if (insn_end_class == EndClass::Branch) {
485 conditional_block.cond = true; 365 conditional_block->cond = IR::Condition{true};
486 conditional_block.branch_true = endif_block_id; 366 conditional_block->branch_true = endif_block;
487 conditional_block.branch_false = UNREACHABLE_BLOCK_ID; 367 conditional_block->branch_false = nullptr;
488 } 368 }
369 // Finally insert the condition block into the list of blocks
370 functions[function_id].blocks.insert(*conditional_block);
489} 371}
490 372
491bool CFG::AnalyzeBranch(Block& block, FunctionId function_id, Location pc, Instruction inst, 373bool CFG::AnalyzeBranch(Block* block, FunctionId function_id, Location pc, Instruction inst,
492 Opcode opcode) { 374 Opcode opcode) {
493 if (inst.branch.is_cbuf) { 375 if (inst.branch.is_cbuf) {
494 throw NotImplementedException("Branch with constant buffer offset"); 376 throw NotImplementedException("Branch with constant buffer offset");
@@ -500,21 +382,21 @@ bool CFG::AnalyzeBranch(Block& block, FunctionId function_id, Location pc, Instr
500 const bool has_flow_test{HasFlowTest(opcode)}; 382 const bool has_flow_test{HasFlowTest(opcode)};
501 const IR::FlowTest flow_test{has_flow_test ? inst.branch.flow_test.Value() : IR::FlowTest::T}; 383 const IR::FlowTest flow_test{has_flow_test ? inst.branch.flow_test.Value() : IR::FlowTest::T};
502 if (pred != Predicate{true} || flow_test != IR::FlowTest::T) { 384 if (pred != Predicate{true} || flow_test != IR::FlowTest::T) {
503 block.cond = IR::Condition(flow_test, static_cast<IR::Pred>(pred.index), pred.negated); 385 block->cond = IR::Condition(flow_test, static_cast<IR::Pred>(pred.index), pred.negated);
504 block.branch_false = AddLabel(block, block.stack, pc + 1, function_id); 386 block->branch_false = AddLabel(block, block->stack, pc + 1, function_id);
505 } else { 387 } else {
506 block.cond = true; 388 block->cond = IR::Condition{true};
507 } 389 }
508 return true; 390 return true;
509} 391}
510 392
511void CFG::AnalyzeBRA(Block& block, FunctionId function_id, Location pc, Instruction inst, 393void CFG::AnalyzeBRA(Block* block, FunctionId function_id, Location pc, Instruction inst,
512 bool is_absolute) { 394 bool is_absolute) {
513 const Location bra_pc{is_absolute ? inst.branch.Absolute() : BranchOffset(pc, inst)}; 395 const Location bra_pc{is_absolute ? inst.branch.Absolute() : BranchOffset(pc, inst)};
514 block.branch_true = AddLabel(block, block.stack, bra_pc, function_id); 396 block->branch_true = AddLabel(block, block->stack, bra_pc, function_id);
515} 397}
516 398
517void CFG::AnalyzeBRX(Block&, Location, Instruction, bool is_absolute) { 399void CFG::AnalyzeBRX(Block*, Location, Instruction, bool is_absolute) {
518 throw NotImplementedException("{}", is_absolute ? "JMX" : "BRX"); 400 throw NotImplementedException("{}", is_absolute ? "JMX" : "BRX");
519} 401}
520 402
@@ -528,7 +410,7 @@ void CFG::AnalyzeCAL(Location pc, Instruction inst, bool is_absolute) {
528 } 410 }
529} 411}
530 412
531CFG::AnalysisState CFG::AnalyzeEXIT(Block& block, FunctionId function_id, Location pc, 413CFG::AnalysisState CFG::AnalyzeEXIT(Block* block, FunctionId function_id, Location pc,
532 Instruction inst) { 414 Instruction inst) {
533 const IR::FlowTest flow_test{inst.branch.flow_test}; 415 const IR::FlowTest flow_test{inst.branch.flow_test};
534 const Predicate pred{inst.Pred()}; 416 const Predicate pred{inst.Pred()};
@@ -537,41 +419,52 @@ CFG::AnalysisState CFG::AnalyzeEXIT(Block& block, FunctionId function_id, Locati
537 return AnalysisState::Continue; 419 return AnalysisState::Continue;
538 } 420 }
539 if (pred != Predicate{true} || flow_test != IR::FlowTest::T) { 421 if (pred != Predicate{true} || flow_test != IR::FlowTest::T) {
540 if (block.stack.Peek(Token::PEXIT).has_value()) { 422 if (block->stack.Peek(Token::PEXIT).has_value()) {
541 throw NotImplementedException("Conditional EXIT with PEXIT token"); 423 throw NotImplementedException("Conditional EXIT with PEXIT token");
542 } 424 }
543 const IR::Condition cond{flow_test, static_cast<IR::Pred>(pred.index), pred.negated}; 425 const IR::Condition cond{flow_test, static_cast<IR::Pred>(pred.index), pred.negated};
544 AnalyzeCondInst(block, function_id, pc, EndClass::Exit, cond); 426 AnalyzeCondInst(block, function_id, pc, EndClass::Exit, cond);
545 return AnalysisState::Branch; 427 return AnalysisState::Branch;
546 } 428 }
547 if (const std::optional<Location> exit_pc{block.stack.Peek(Token::PEXIT)}) { 429 if (const std::optional<Location> exit_pc{block->stack.Peek(Token::PEXIT)}) {
548 const Stack popped_stack{block.stack.Remove(Token::PEXIT)}; 430 const Stack popped_stack{block->stack.Remove(Token::PEXIT)};
549 block.cond = true; 431 block->cond = IR::Condition{true};
550 block.branch_true = AddLabel(block, popped_stack, *exit_pc, function_id); 432 block->branch_true = AddLabel(block, popped_stack, *exit_pc, function_id);
551 block.branch_false = UNREACHABLE_BLOCK_ID; 433 block->branch_false = nullptr;
552 return AnalysisState::Branch; 434 return AnalysisState::Branch;
553 } 435 }
554 block.end = pc; 436 block->end = pc;
555 block.end_class = EndClass::Exit; 437 block->end_class = EndClass::Exit;
556 return AnalysisState::Branch; 438 return AnalysisState::Branch;
557} 439}
558 440
559BlockId CFG::AddLabel(const Block& block, Stack stack, Location pc, FunctionId function_id) { 441Block* CFG::AddLabel(Block* block, Stack stack, Location pc, FunctionId function_id) {
560 Function& function{functions[function_id]}; 442 Function& function{functions[function_id]};
561 if (block.begin == pc) { 443 if (block->begin == pc) {
562 return block.id; 444 // Jumps to itself
445 return block;
563 } 446 }
564 const auto target{std::ranges::find(function.blocks_data, pc, &Block::begin)}; 447 if (const auto it{function.blocks.find(pc, Compare{})}; it != function.blocks.end()) {
565 if (target != function.blocks_data.end()) { 448 // Block already exists and it has been visited
566 return target->id; 449 return &*it;
567 } 450 }
568 const BlockId block_id{++function.current_block_id}; 451 // TODO: FIX DANGLING BLOCKS
452 Block* const new_block{block_pool.Create(Block{
453 .begin{pc},
454 .end{pc},
455 .end_class{EndClass::Branch},
456 .stack{stack},
457 .cond{IR::Condition{true}},
458 .branch_true{nullptr},
459 .branch_false{nullptr},
460 .ir{nullptr},
461 })};
569 function.labels.push_back(Label{ 462 function.labels.push_back(Label{
570 .address{pc}, 463 .address{pc},
571 .block_id{block_id}, 464 .block{new_block},
572 .stack{std::move(stack)}, 465 .stack{std::move(stack)},
573 }); 466 });
574 return block_id; 467 return new_block;
575} 468}
576 469
577std::string CFG::Dot() const { 470std::string CFG::Dot() const {
@@ -581,18 +474,12 @@ std::string CFG::Dot() const {
581 for (const Function& function : functions) { 474 for (const Function& function : functions) {
582 dot += fmt::format("\tsubgraph cluster_{} {{\n", function.entrypoint); 475 dot += fmt::format("\tsubgraph cluster_{} {{\n", function.entrypoint);
583 dot += fmt::format("\t\tnode [style=filled];\n"); 476 dot += fmt::format("\t\tnode [style=filled];\n");
584 for (const u32 block_index : function.blocks) { 477 for (const Block& block : function.blocks) {
585 const Block& block{function.blocks_data[block_index]};
586 const std::string name{NameOf(block)}; 478 const std::string name{NameOf(block)};
587 const auto add_branch = [&](BlockId branch_id, bool add_label) { 479 const auto add_branch = [&](Block* branch, bool add_label) {
588 const auto it{std::ranges::find(function.blocks_data, branch_id, &Block::id)}; 480 dot += fmt::format("\t\t{}->{}", name, NameOf(*branch));
589 dot += fmt::format("\t\t{}->", name); 481 if (add_label && block.cond != IR::Condition{true} &&
590 if (it == function.blocks_data.end()) { 482 block.cond != IR::Condition{false}) {
591 dot += fmt::format("\"Unknown label {}\"", branch_id);
592 } else {
593 dot += NameOf(*it);
594 };
595 if (add_label && block.cond != true && block.cond != false) {
596 dot += fmt::format(" [label=\"{}\"]", block.cond); 483 dot += fmt::format(" [label=\"{}\"]", block.cond);
597 } 484 }
598 dot += '\n'; 485 dot += '\n';
@@ -600,10 +487,10 @@ std::string CFG::Dot() const {
600 dot += fmt::format("\t\t{};\n", name); 487 dot += fmt::format("\t\t{};\n", name);
601 switch (block.end_class) { 488 switch (block.end_class) {
602 case EndClass::Branch: 489 case EndClass::Branch:
603 if (block.cond != false) { 490 if (block.cond != IR::Condition{false}) {
604 add_branch(block.branch_true, true); 491 add_branch(block.branch_true, true);
605 } 492 }
606 if (block.cond != true) { 493 if (block.cond != IR::Condition{true}) {
607 add_branch(block.branch_false, false); 494 add_branch(block.branch_false, false);
608 } 495 }
609 break; 496 break;
@@ -619,12 +506,6 @@ std::string CFG::Dot() const {
619 node_uid); 506 node_uid);
620 ++node_uid; 507 ++node_uid;
621 break; 508 break;
622 case EndClass::Unreachable:
623 dot += fmt::format("\t\t{}->N{};\n", name, node_uid);
624 dot += fmt::format(
625 "\t\tN{} [label=\"Unreachable\"][shape=square][style=stripped];\n", node_uid);
626 ++node_uid;
627 break;
628 } 509 }
629 } 510 }
630 if (function.entrypoint == 8) { 511 if (function.entrypoint == 8) {
@@ -635,10 +516,11 @@ std::string CFG::Dot() const {
635 dot += "\t}\n"; 516 dot += "\t}\n";
636 } 517 }
637 if (!functions.empty()) { 518 if (!functions.empty()) {
638 if (functions.front().blocks.empty()) { 519 auto& function{functions.front()};
520 if (function.blocks.empty()) {
639 dot += "Start;\n"; 521 dot += "Start;\n";
640 } else { 522 } else {
641 dot += fmt::format("\tStart -> {};\n", NameOf(functions.front().blocks_data.front())); 523 dot += fmt::format("\tStart -> {};\n", NameOf(*function.blocks.begin()));
642 } 524 }
643 dot += fmt::format("\tStart [shape=diamond];\n"); 525 dot += fmt::format("\tStart [shape=diamond];\n");
644 } 526 }