From 8af6e6a05207b1c9736bd80a89ec3aed1f96dfea Mon Sep 17 00:00:00 2001 From: Fernando Sahmkow Date: Mon, 24 Jun 2019 19:46:49 -0400 Subject: shader_ir: Implement a new shader scanner --- src/video_core/shader/control_flow.cpp | 393 +++++++++++++++++++++++++++++++++ 1 file changed, 393 insertions(+) create mode 100644 src/video_core/shader/control_flow.cpp (limited to 'src/video_core/shader/control_flow.cpp') diff --git a/src/video_core/shader/control_flow.cpp b/src/video_core/shader/control_flow.cpp new file mode 100644 index 000000000..fcf22c7f2 --- /dev/null +++ b/src/video_core/shader/control_flow.cpp @@ -0,0 +1,393 @@ + +#include +#include +#include +#include + +#include "common/assert.h" +#include "common/common_types.h" +#include "video_core/shader/control_flow.h" +#include "video_core/shader/shader_ir.h" + +namespace VideoCommon::Shader { + +using Tegra::Shader::Instruction; +using Tegra::Shader::OpCode; + +constexpr s32 unassigned_branch = -2; + +struct BlockBranchInfo { + Condition condition{}; + s32 address{exit_branch}; + bool kill{}; + bool is_sync{}; + bool is_brk{}; +}; + +struct BlockInfo { + BlockInfo() {} + u32 start{}; + u32 end{}; + bool visited{}; + BlockBranchInfo branch{}; + + bool IsInside(const u32 address) const { + return start <= address && address <= end; + } +}; + +struct Stamp { + Stamp() = default; + Stamp(u32 address, u32 target) : address{address}, target{target} {} + u32 address{}; + u32 target{}; + bool operator==(const Stamp& sb) const { + return std::tie(address, target) == std::tie(sb.address, sb.target); + } + bool operator<(const Stamp& sb) const { + return address < sb.address; + } + bool operator>(const Stamp& sb) const { + return address > sb.address; + } + bool operator<=(const Stamp& sb) const { + return address <= sb.address; + } + bool operator>=(const Stamp& sb) const { + return address >= sb.address; + } +}; + +struct CFGRebuildState { + explicit CFGRebuildState(const ProgramCode& program_code, const std::size_t program_size) + : program_code{program_code}, program_size{program_size} { + // queries.clear(); + block_info.clear(); + labels.clear(); + visited_address.clear(); + ssy_labels.clear(); + pbk_labels.clear(); + inspect_queries.clear(); + } + + std::vector block_info{}; + std::list inspect_queries{}; + // std::list queries{}; + std::unordered_set visited_address{}; + std::unordered_set labels{}; + std::set ssy_labels; + std::set pbk_labels; + const ProgramCode& program_code; + const std::size_t program_size; +}; + +enum class BlockCollision : u32 { None = 0, Found = 1, Inside = 2 }; + +std::pair::iterator> TryGetBlock(CFGRebuildState& state, + u32 address) { + auto it = state.block_info.begin(); + while (it != state.block_info.end()) { + if (it->start == address) { + return {BlockCollision::Found, it}; + } + if (it->IsInside(address)) { + return {BlockCollision::Inside, it}; + } + it++; + } + return {BlockCollision::None, it}; +} + +struct ParseInfo { + BlockBranchInfo branch_info{}; + u32 end_address{}; +}; + +BlockInfo* CreateBlockInfo(CFGRebuildState& state, u32 start, u32 end) { + auto& it = state.block_info.emplace_back(); + it.start = start; + it.end = end; + state.visited_address.insert(start); + return ⁢ +} + +Pred GetPredicate(u32 index, bool negated) { + return static_cast(index + (negated ? 8 : 0)); +} + +enum class ParseResult : u32 { + ControlCaught = 0, + BlockEnd = 1, + AbnormalFlow = 2, +}; + +ParseResult ParseCode(CFGRebuildState& state, u32 address, ParseInfo& parse_info) { + + u32 offset = static_cast(address); + u32 end_address = static_cast(state.program_size - 10U) * 8U; + + auto insert_label = ([](CFGRebuildState& state, u32 address) { + auto pair = state.labels.emplace(address); + if (pair.second) { + state.inspect_queries.push_back(address); + } + }); + + while (true) { + if (offset >= end_address) { + parse_info.branch_info.address = exit_branch; + break; + } + if (state.visited_address.count(offset) != 0) { + parse_info.branch_info.address = offset; + break; + } + const Instruction instr = {state.program_code[offset]}; + const auto opcode = OpCode::Decode(instr); + if (!opcode || opcode->get().GetType() != OpCode::Type::Flow) { + offset++; + continue; + } + + switch (opcode->get().GetId()) { + case OpCode::Id::EXIT: { + const auto pred_index = static_cast(instr.pred.pred_index); + parse_info.branch_info.condition.predicate = + GetPredicate(pred_index, instr.negate_pred != 0); + if (parse_info.branch_info.condition.predicate == Pred::NeverExecute) { + offset++; + continue; + } + const ConditionCode cc = instr.flow_condition_code; + parse_info.branch_info.condition.cc = cc; + if (cc == ConditionCode::F) { + offset++; + continue; + } + parse_info.branch_info.address = exit_branch; + parse_info.branch_info.kill = false; + parse_info.branch_info.is_sync = false; + parse_info.branch_info.is_brk = false; + parse_info.end_address = offset; + + return ParseResult::ControlCaught; + } + case OpCode::Id::BRA: { + if (instr.bra.constant_buffer != 0) { + return ParseResult::AbnormalFlow; + } + const auto pred_index = static_cast(instr.pred.pred_index); + parse_info.branch_info.condition.predicate = + GetPredicate(pred_index, instr.negate_pred != 0); + if (parse_info.branch_info.condition.predicate == Pred::NeverExecute) { + offset++; + continue; + } + const ConditionCode cc = instr.flow_condition_code; + parse_info.branch_info.condition.cc = cc; + if (cc == ConditionCode::F) { + offset++; + continue; + } + u32 branch_offset = offset + instr.bra.GetBranchTarget(); + if (branch_offset == 0) { + parse_info.branch_info.address = exit_branch; + } else { + parse_info.branch_info.address = branch_offset; + } + insert_label(state, branch_offset); + parse_info.branch_info.kill = false; + parse_info.branch_info.is_sync = false; + parse_info.branch_info.is_brk = false; + parse_info.end_address = offset; + + return ParseResult::ControlCaught; + } + case OpCode::Id::SYNC: { + parse_info.branch_info.condition; + const auto pred_index = static_cast(instr.pred.pred_index); + parse_info.branch_info.condition.predicate = + GetPredicate(pred_index, instr.negate_pred != 0); + if (parse_info.branch_info.condition.predicate == Pred::NeverExecute) { + offset++; + continue; + } + const ConditionCode cc = instr.flow_condition_code; + parse_info.branch_info.condition.cc = cc; + if (cc == ConditionCode::F) { + offset++; + continue; + } + parse_info.branch_info.address = unassigned_branch; + parse_info.branch_info.kill = false; + parse_info.branch_info.is_sync = true; + parse_info.branch_info.is_brk = false; + parse_info.end_address = offset; + + return ParseResult::ControlCaught; + } + case OpCode::Id::BRK: { + parse_info.branch_info.condition; + const auto pred_index = static_cast(instr.pred.pred_index); + parse_info.branch_info.condition.predicate = + GetPredicate(pred_index, instr.negate_pred != 0); + if (parse_info.branch_info.condition.predicate == Pred::NeverExecute) { + offset++; + continue; + } + const ConditionCode cc = instr.flow_condition_code; + parse_info.branch_info.condition.cc = cc; + if (cc == ConditionCode::F) { + offset++; + continue; + } + parse_info.branch_info.address = unassigned_branch; + parse_info.branch_info.kill = false; + parse_info.branch_info.is_sync = false; + parse_info.branch_info.is_brk = true; + parse_info.end_address = offset; + + return ParseResult::ControlCaught; + } + case OpCode::Id::KIL: { + parse_info.branch_info.condition; + const auto pred_index = static_cast(instr.pred.pred_index); + parse_info.branch_info.condition.predicate = + GetPredicate(pred_index, instr.negate_pred != 0); + if (parse_info.branch_info.condition.predicate == Pred::NeverExecute) { + offset++; + continue; + } + const ConditionCode cc = instr.flow_condition_code; + parse_info.branch_info.condition.cc = cc; + if (cc == ConditionCode::F) { + offset++; + continue; + } + parse_info.branch_info.address = exit_branch; + parse_info.branch_info.kill = true; + parse_info.branch_info.is_sync = false; + parse_info.branch_info.is_brk = false; + parse_info.end_address = offset; + + return ParseResult::ControlCaught; + } + case OpCode::Id::SSY: { + const u32 target = offset + instr.bra.GetBranchTarget(); + insert_label(state, target); + state.ssy_labels.emplace(offset, target); + break; + } + case OpCode::Id::PBK: { + const u32 target = offset + instr.bra.GetBranchTarget(); + insert_label(state, target); + state.pbk_labels.emplace(offset, target); + break; + } + default: + break; + } + + offset++; + } + parse_info.branch_info.kill = false; + parse_info.branch_info.is_sync = false; + parse_info.branch_info.is_brk = false; + parse_info.end_address = offset - 1; + return ParseResult::BlockEnd; +} + +bool TryInspectAddress(CFGRebuildState& state) { + if (state.inspect_queries.empty()) { + return false; + } + u32 address = state.inspect_queries.front(); + state.inspect_queries.pop_front(); + auto search_result = TryGetBlock(state, address); + BlockInfo* block_info; + switch (search_result.first) { + case BlockCollision::Found: { + return true; + break; + } + case BlockCollision::Inside: { + // This case is the tricky one: + // We need to Split the block in 2 sepprate blocks + auto it = search_result.second; + block_info = CreateBlockInfo(state, address, it->end); + it->end = address - 1; + block_info->branch = it->branch; + BlockBranchInfo forward_branch{}; + forward_branch.address = address; + it->branch = forward_branch; + return true; + break; + } + default: + break; + } + ParseInfo parse_info; + ParseResult parse_result = ParseCode(state, address, parse_info); + if (parse_result == ParseResult::AbnormalFlow) { + // if it's the end of the program, end it safely + // if it's AbnormalFlow, we end it as false, ending the CFG reconstruction + return false; + } + + block_info = CreateBlockInfo(state, address, parse_info.end_address); + block_info->branch = parse_info.branch_info; + if (parse_info.branch_info.condition.IsUnconditional()) { + return true; + } + + u32 fallthrough_address = parse_info.end_address + 1; + state.inspect_queries.push_front(fallthrough_address); + return true; +} + +bool ScanFlow(const ProgramCode& program_code, u32 program_size, u32 start_address, + ShaderCharacteristics& result_out) { + CFGRebuildState state{program_code, program_size}; + // Inspect Code and generate blocks + state.labels.clear(); + state.labels.emplace(start_address); + state.inspect_queries.push_back(start_address); + while (!state.inspect_queries.empty()) { + if (!TryInspectAddress(state)) { + return false; + } + } + std::sort(state.block_info.begin(), state.block_info.end(), + [](const BlockInfo& a, const BlockInfo& b) -> bool { return a.start < b.start; }); + // Remove unvisited blocks + result_out.blocks.clear(); + result_out.decompilable = false; + result_out.start = start_address; + result_out.end = start_address; + for (auto& block : state.block_info) { + ShaderBlock new_block{}; + new_block.start = block.start; + new_block.end = block.end; + new_block.branch.cond = block.branch.condition; + new_block.branch.kills = block.branch.kill; + new_block.branch.address = block.branch.address; + result_out.end = std::max(result_out.end, block.end); + result_out.blocks.push_back(new_block); + } + if (result_out.decompilable) { + return true; + } + auto back = result_out.blocks.begin(); + auto next = std::next(back); + while (next != result_out.blocks.end()) { + if (state.labels.count(next->start) == 0 && next->start == back->end + 1) { + back->end = next->end; + next = result_out.blocks.erase(next); + continue; + } + back = next; + next++; + } + return true; +} +} // namespace VideoCommon::Shader -- cgit v1.2.3 From 8a6fc529a968e007f01464abadd32f9b5eb0a26c Mon Sep 17 00:00:00 2001 From: Fernando Sahmkow Date: Mon, 24 Jun 2019 21:25:38 -0400 Subject: shader_ir: Implement BRX & BRA.CC --- src/video_core/shader/control_flow.cpp | 3 +++ 1 file changed, 3 insertions(+) (limited to 'src/video_core/shader/control_flow.cpp') diff --git a/src/video_core/shader/control_flow.cpp b/src/video_core/shader/control_flow.cpp index fcf22c7f2..a9de8f814 100644 --- a/src/video_core/shader/control_flow.cpp +++ b/src/video_core/shader/control_flow.cpp @@ -284,6 +284,9 @@ ParseResult ParseCode(CFGRebuildState& state, u32 address, ParseInfo& parse_info state.pbk_labels.emplace(offset, target); break; } + case OpCode::Id::BRX: { + return ParseResult::AbnormalFlow; + } default: break; } -- cgit v1.2.3 From 926b80102f1c00675a9f3956258a066bfe0c3642 Mon Sep 17 00:00:00 2001 From: Fernando Sahmkow Date: Tue, 25 Jun 2019 11:10:45 -0400 Subject: shader_ir: Decompile Flow Stack --- src/video_core/shader/control_flow.cpp | 167 ++++++++++++++++++++++++++++++--- 1 file changed, 156 insertions(+), 11 deletions(-) (limited to 'src/video_core/shader/control_flow.cpp') diff --git a/src/video_core/shader/control_flow.cpp b/src/video_core/shader/control_flow.cpp index a9de8f814..3af4c6190 100644 --- a/src/video_core/shader/control_flow.cpp +++ b/src/video_core/shader/control_flow.cpp @@ -1,6 +1,6 @@ #include -#include +#include #include #include @@ -16,12 +16,80 @@ using Tegra::Shader::OpCode; constexpr s32 unassigned_branch = -2; +struct ControlStack { + std::array stack; + u32 index{}; + + ControlStack() {} + + ControlStack(const ControlStack& cp) { + index = cp.index; + std::memcpy(stack.data(), cp.stack.data(), index * sizeof(u32)); + } + + bool Compare(const ControlStack& cs) const { + if (index != cs.index) { + return false; + } + return std::memcmp(stack.data(), cs.stack.data(), index * sizeof(u32)) == 0; + } + + bool SoftCompare(const ControlStack& cs) const { + if (index == 0 || cs.index == 0) { + return index == cs.index; + } + return Top() == cs.Top(); + } + + u32 Size() const { + return index; + } + + u32 Top() const { + return stack[index - 1]; + } + + bool Push(u32 address) { + if (index >= 20) { + return false; + } + stack[index] = address; + index++; + return true; + } + + bool Pop() { + if (index == 0) { + return false; + } + index--; + return true; + } +}; + +struct Query { + Query() {} + Query(const Query& q) : address{q.address}, ssy_stack{q.ssy_stack}, pbk_stack{q.pbk_stack} {} + u32 address; + ControlStack ssy_stack{}; + ControlStack pbk_stack{}; +}; + +struct BlockStack { + BlockStack() = default; + BlockStack(const BlockStack& b) : ssy_stack{b.ssy_stack}, pbk_stack{b.pbk_stack} {} + BlockStack(const Query& q) : ssy_stack{q.ssy_stack}, pbk_stack{q.pbk_stack} {} + ControlStack ssy_stack{}; + ControlStack pbk_stack{}; +}; + struct BlockBranchInfo { Condition condition{}; s32 address{exit_branch}; bool kill{}; bool is_sync{}; bool is_brk{}; + bool ignore{}; }; struct BlockInfo { @@ -64,19 +132,21 @@ struct CFGRebuildState { // queries.clear(); block_info.clear(); labels.clear(); - visited_address.clear(); + registered.clear(); ssy_labels.clear(); pbk_labels.clear(); inspect_queries.clear(); + queries.clear(); } std::vector block_info{}; std::list inspect_queries{}; - // std::list queries{}; - std::unordered_set visited_address{}; + std::list queries{}; + std::unordered_map registered{}; std::unordered_set labels{}; std::set ssy_labels; std::set pbk_labels; + std::unordered_map stacks{}; const ProgramCode& program_code; const std::size_t program_size; }; @@ -107,7 +177,8 @@ BlockInfo* CreateBlockInfo(CFGRebuildState& state, u32 start, u32 end) { auto& it = state.block_info.emplace_back(); it.start = start; it.end = end; - state.visited_address.insert(start); + u32 index = state.block_info.size() - 1; + state.registered.insert({start, index}); return ⁢ } @@ -136,10 +207,12 @@ ParseResult ParseCode(CFGRebuildState& state, u32 address, ParseInfo& parse_info while (true) { if (offset >= end_address) { parse_info.branch_info.address = exit_branch; + parse_info.branch_info.ignore = false; break; } - if (state.visited_address.count(offset) != 0) { + if (state.registered.count(offset) != 0) { parse_info.branch_info.address = offset; + parse_info.branch_info.ignore = true; break; } const Instruction instr = {state.program_code[offset]}; @@ -168,6 +241,7 @@ ParseResult ParseCode(CFGRebuildState& state, u32 address, ParseInfo& parse_info parse_info.branch_info.kill = false; parse_info.branch_info.is_sync = false; parse_info.branch_info.is_brk = false; + parse_info.branch_info.ignore = false; parse_info.end_address = offset; return ParseResult::ControlCaught; @@ -199,6 +273,7 @@ ParseResult ParseCode(CFGRebuildState& state, u32 address, ParseInfo& parse_info parse_info.branch_info.kill = false; parse_info.branch_info.is_sync = false; parse_info.branch_info.is_brk = false; + parse_info.branch_info.ignore = false; parse_info.end_address = offset; return ParseResult::ControlCaught; @@ -222,6 +297,7 @@ ParseResult ParseCode(CFGRebuildState& state, u32 address, ParseInfo& parse_info parse_info.branch_info.kill = false; parse_info.branch_info.is_sync = true; parse_info.branch_info.is_brk = false; + parse_info.branch_info.ignore = false; parse_info.end_address = offset; return ParseResult::ControlCaught; @@ -245,6 +321,7 @@ ParseResult ParseCode(CFGRebuildState& state, u32 address, ParseInfo& parse_info parse_info.branch_info.kill = false; parse_info.branch_info.is_sync = false; parse_info.branch_info.is_brk = true; + parse_info.branch_info.ignore = false; parse_info.end_address = offset; return ParseResult::ControlCaught; @@ -268,6 +345,7 @@ ParseResult ParseCode(CFGRebuildState& state, u32 address, ParseInfo& parse_info parse_info.branch_info.kill = true; parse_info.branch_info.is_sync = false; parse_info.branch_info.is_brk = false; + parse_info.branch_info.ignore = false; parse_info.end_address = offset; return ParseResult::ControlCaught; @@ -322,6 +400,7 @@ bool TryInspectAddress(CFGRebuildState& state) { block_info->branch = it->branch; BlockBranchInfo forward_branch{}; forward_branch.address = address; + forward_branch.ignore = true; it->branch = forward_branch; return true; break; @@ -348,6 +427,58 @@ bool TryInspectAddress(CFGRebuildState& state) { return true; } +bool TryQuery(CFGRebuildState& state) { + auto gather_labels = ([](ControlStack& cc, std::set labels, BlockInfo& block) { + Stamp start{block.start, 0}; + Stamp end{block.end, 0}; + auto gather_start = labels.lower_bound(start); + auto gather_end = labels.upper_bound(end); + while (gather_start != gather_end) { + cc.Push(gather_start->target); + gather_start++; + } + }); + if (state.queries.empty()) { + return false; + } + Query& q = state.queries.front(); + u32 block_index = state.registered[q.address]; + BlockInfo& block = state.block_info[block_index]; + if (block.visited) { + BlockStack& stack = state.stacks[q.address]; + bool all_okay = q.ssy_stack.Compare(stack.ssy_stack) && q.pbk_stack.Compare(stack.pbk_stack); + state.queries.pop_front(); + return all_okay; + } + block.visited = true; + BlockStack bs{q}; + state.stacks[q.address] = bs; + Query q2(q); + state.queries.pop_front(); + gather_labels(q2.ssy_stack, state.ssy_labels, block); + gather_labels(q2.pbk_stack, state.pbk_labels, block); + if (!block.branch.condition.IsUnconditional()) { + q2.address = block.end + 1; + state.queries.push_back(q2); + } + Query conditional_query{q2}; + if (block.branch.is_sync) { + if (block.branch.address == unassigned_branch) { + block.branch.address = conditional_query.ssy_stack.Top(); + } + conditional_query.ssy_stack.Pop(); + } + if (block.branch.is_brk) { + if (block.branch.address == unassigned_branch) { + block.branch.address = conditional_query.pbk_stack.Top(); + } + conditional_query.pbk_stack.Pop(); + } + conditional_query.address = block.branch.address; + state.queries.push_back(conditional_query); + return true; +} + bool ScanFlow(const ProgramCode& program_code, u32 program_size, u32 start_address, ShaderCharacteristics& result_out) { CFGRebuildState state{program_code, program_size}; @@ -360,20 +491,34 @@ bool ScanFlow(const ProgramCode& program_code, u32 program_size, u32 start_addre return false; } } + // Decompile Stacks + Query start_query{}; + start_query.address = start_address; + state.queries.push_back(start_query); + bool decompiled = true; + while (!state.queries.empty()) { + if (!TryQuery(state)) { + decompiled = false; + break; + } + } + // Sort and organize results std::sort(state.block_info.begin(), state.block_info.end(), [](const BlockInfo& a, const BlockInfo& b) -> bool { return a.start < b.start; }); - // Remove unvisited blocks result_out.blocks.clear(); - result_out.decompilable = false; + result_out.decompilable = decompiled; result_out.start = start_address; result_out.end = start_address; for (auto& block : state.block_info) { ShaderBlock new_block{}; new_block.start = block.start; new_block.end = block.end; - new_block.branch.cond = block.branch.condition; - new_block.branch.kills = block.branch.kill; - new_block.branch.address = block.branch.address; + new_block.ignore_branch = block.branch.ignore; + if (!new_block.ignore_branch) { + new_block.branch.cond = block.branch.condition; + new_block.branch.kills = block.branch.kill; + new_block.branch.address = block.branch.address; + } result_out.end = std::max(result_out.end, block.end); result_out.blocks.push_back(new_block); } -- cgit v1.2.3 From d5533b440c764093c04a4859b30fc78ddb0e0bbe Mon Sep 17 00:00:00 2001 From: Fernando Sahmkow Date: Tue, 25 Jun 2019 13:03:51 -0400 Subject: shader_ir: Unify blocks in decompiled shaders. --- src/video_core/shader/control_flow.cpp | 47 +++++++++++----------------------- 1 file changed, 15 insertions(+), 32 deletions(-) (limited to 'src/video_core/shader/control_flow.cpp') diff --git a/src/video_core/shader/control_flow.cpp b/src/video_core/shader/control_flow.cpp index 3af4c6190..c99d95b57 100644 --- a/src/video_core/shader/control_flow.cpp +++ b/src/video_core/shader/control_flow.cpp @@ -1,5 +1,6 @@ #include +#include #include #include #include @@ -104,28 +105,6 @@ struct BlockInfo { } }; -struct Stamp { - Stamp() = default; - Stamp(u32 address, u32 target) : address{address}, target{target} {} - u32 address{}; - u32 target{}; - bool operator==(const Stamp& sb) const { - return std::tie(address, target) == std::tie(sb.address, sb.target); - } - bool operator<(const Stamp& sb) const { - return address < sb.address; - } - bool operator>(const Stamp& sb) const { - return address > sb.address; - } - bool operator<=(const Stamp& sb) const { - return address <= sb.address; - } - bool operator>=(const Stamp& sb) const { - return address >= sb.address; - } -}; - struct CFGRebuildState { explicit CFGRebuildState(const ProgramCode& program_code, const std::size_t program_size) : program_code{program_code}, program_size{program_size} { @@ -144,8 +123,8 @@ struct CFGRebuildState { std::list queries{}; std::unordered_map registered{}; std::unordered_set labels{}; - std::set ssy_labels; - std::set pbk_labels; + std::map ssy_labels; + std::map pbk_labels; std::unordered_map stacks{}; const ProgramCode& program_code; const std::size_t program_size; @@ -393,7 +372,7 @@ bool TryInspectAddress(CFGRebuildState& state) { } case BlockCollision::Inside: { // This case is the tricky one: - // We need to Split the block in 2 sepprate blocks + // We need to Split the block in 2 sepparate blocks auto it = search_result.second; block_info = CreateBlockInfo(state, address, it->end); it->end = address - 1; @@ -428,13 +407,11 @@ bool TryInspectAddress(CFGRebuildState& state) { } bool TryQuery(CFGRebuildState& state) { - auto gather_labels = ([](ControlStack& cc, std::set labels, BlockInfo& block) { - Stamp start{block.start, 0}; - Stamp end{block.end, 0}; - auto gather_start = labels.lower_bound(start); - auto gather_end = labels.upper_bound(end); + auto gather_labels = ([](ControlStack& cc, std::map& labels, BlockInfo& block) { + auto gather_start = labels.lower_bound(block.start); + auto gather_end = labels.upper_bound(block.end); while (gather_start != gather_end) { - cc.Push(gather_start->target); + cc.Push(gather_start->second); gather_start++; } }); @@ -444,9 +421,13 @@ bool TryQuery(CFGRebuildState& state) { Query& q = state.queries.front(); u32 block_index = state.registered[q.address]; BlockInfo& block = state.block_info[block_index]; + // If the block is visted, check if the stacks match, else gather the ssy/pbk + // labels into the current stack and look if the branch at the end of the block + // consumes a label. Schedule new queries accordingly if (block.visited) { BlockStack& stack = state.stacks[q.address]; - bool all_okay = q.ssy_stack.Compare(stack.ssy_stack) && q.pbk_stack.Compare(stack.pbk_stack); + bool all_okay = (stack.ssy_stack.Size() == 0 || q.ssy_stack.Compare(stack.ssy_stack)) && + (stack.pbk_stack.Size() == 0 || q.pbk_stack.Compare(stack.pbk_stack)); state.queries.pop_front(); return all_okay; } @@ -523,8 +504,10 @@ bool ScanFlow(const ProgramCode& program_code, u32 program_size, u32 start_addre result_out.blocks.push_back(new_block); } if (result_out.decompilable) { + result_out.labels = std::move(state.labels); return true; } + // If it's not decompilable, merge the unlabelled blocks together auto back = result_out.blocks.begin(); auto next = std::next(back); while (next != result_out.blocks.end()) { -- cgit v1.2.3 From 01b21ee1e8e7455dd84ee7f22d33426caaaafdb3 Mon Sep 17 00:00:00 2001 From: Fernando Sahmkow Date: Tue, 25 Jun 2019 20:15:40 -0400 Subject: shader_ir: Corrections, documenting and asserting control_flow --- src/video_core/shader/control_flow.cpp | 80 ++++++++++++++++------------------ 1 file changed, 37 insertions(+), 43 deletions(-) (limited to 'src/video_core/shader/control_flow.cpp') diff --git a/src/video_core/shader/control_flow.cpp b/src/video_core/shader/control_flow.cpp index c99d95b57..deef0cd3a 100644 --- a/src/video_core/shader/control_flow.cpp +++ b/src/video_core/shader/control_flow.cpp @@ -1,3 +1,6 @@ +// Copyright 2019 yuzu Emulator Project +// Licensed under GPLv2 or any later version +// Refer to the license.txt file included. #include #include @@ -17,16 +20,18 @@ using Tegra::Shader::OpCode; constexpr s32 unassigned_branch = -2; +/*** + * 'ControlStack' represents a static stack of control jumps such as SSY and PBK + * stacks in Maxwell. + ***/ struct ControlStack { - std::array stack; + static constexpr std::size_t stack_fixed_size = 20; + std::array stack{}; u32 index{}; ControlStack() {} - ControlStack(const ControlStack& cp) { - index = cp.index; - std::memcpy(stack.data(), cp.stack.data(), index * sizeof(u32)); - } + ControlStack(const ControlStack& cp) = default; bool Compare(const ControlStack& cs) const { if (index != cs.index) { @@ -35,6 +40,7 @@ struct ControlStack { return std::memcmp(stack.data(), cs.stack.data(), index * sizeof(u32)) == 0; } + /// This compare just compares the top of the stack against one another bool SoftCompare(const ControlStack& cs) const { if (index == 0 || cs.index == 0) { return index == cs.index; @@ -51,7 +57,7 @@ struct ControlStack { } bool Push(u32 address) { - if (index >= 20) { + if (index >= stack.size()) { return false; } stack[index] = address; @@ -70,21 +76,23 @@ struct ControlStack { struct Query { Query() {} - Query(const Query& q) : address{q.address}, ssy_stack{q.ssy_stack}, pbk_stack{q.pbk_stack} {} - u32 address; + Query(const Query& q) = default; + u32 address{}; ControlStack ssy_stack{}; ControlStack pbk_stack{}; }; struct BlockStack { BlockStack() = default; - BlockStack(const BlockStack& b) : ssy_stack{b.ssy_stack}, pbk_stack{b.pbk_stack} {} + BlockStack(const BlockStack& b) = default; BlockStack(const Query& q) : ssy_stack{q.ssy_stack}, pbk_stack{q.pbk_stack} {} ControlStack ssy_stack{}; ControlStack pbk_stack{}; }; struct BlockBranchInfo { + BlockBranchInfo() = default; + BlockBranchInfo(const BlockBranchInfo& b) = default; Condition condition{}; s32 address{exit_branch}; bool kill{}; @@ -94,7 +102,7 @@ struct BlockBranchInfo { }; struct BlockInfo { - BlockInfo() {} + BlockInfo() = default; u32 start{}; u32 end{}; bool visited{}; @@ -107,24 +115,15 @@ struct BlockInfo { struct CFGRebuildState { explicit CFGRebuildState(const ProgramCode& program_code, const std::size_t program_size) - : program_code{program_code}, program_size{program_size} { - // queries.clear(); - block_info.clear(); - labels.clear(); - registered.clear(); - ssy_labels.clear(); - pbk_labels.clear(); - inspect_queries.clear(); - queries.clear(); - } + : program_code{program_code}, program_size{program_size} {} std::vector block_info{}; std::list inspect_queries{}; std::list queries{}; std::unordered_map registered{}; std::unordered_set labels{}; - std::map ssy_labels; - std::map pbk_labels; + std::map ssy_labels{}; + std::map pbk_labels{}; std::unordered_map stacks{}; const ProgramCode& program_code; const std::size_t program_size; @@ -156,7 +155,7 @@ BlockInfo* CreateBlockInfo(CFGRebuildState& state, u32 start, u32 end) { auto& it = state.block_info.emplace_back(); it.start = start; it.end = end; - u32 index = state.block_info.size() - 1; + const u32 index = static_cast(state.block_info.size() - 1); state.registered.insert({start, index}); return ⁢ } @@ -172,11 +171,10 @@ enum class ParseResult : u32 { }; ParseResult ParseCode(CFGRebuildState& state, u32 address, ParseInfo& parse_info) { - u32 offset = static_cast(address); - u32 end_address = static_cast(state.program_size - 10U) * 8U; + const u32 end_address = static_cast(state.program_size - 10U) * 8U; - auto insert_label = ([](CFGRebuildState& state, u32 address) { + const auto insert_label = ([](CFGRebuildState& state, u32 address) { auto pair = state.labels.emplace(address); if (pair.second) { state.inspect_queries.push_back(address); @@ -361,20 +359,18 @@ bool TryInspectAddress(CFGRebuildState& state) { if (state.inspect_queries.empty()) { return false; } - u32 address = state.inspect_queries.front(); + const u32 address = state.inspect_queries.front(); state.inspect_queries.pop_front(); - auto search_result = TryGetBlock(state, address); - BlockInfo* block_info; + const auto search_result = TryGetBlock(state, address); switch (search_result.first) { case BlockCollision::Found: { return true; - break; } case BlockCollision::Inside: { // This case is the tricky one: // We need to Split the block in 2 sepparate blocks auto it = search_result.second; - block_info = CreateBlockInfo(state, address, it->end); + BlockInfo* block_info = CreateBlockInfo(state, address, it->end); it->end = address - 1; block_info->branch = it->branch; BlockBranchInfo forward_branch{}; @@ -382,34 +378,32 @@ bool TryInspectAddress(CFGRebuildState& state) { forward_branch.ignore = true; it->branch = forward_branch; return true; - break; } default: break; } ParseInfo parse_info; - ParseResult parse_result = ParseCode(state, address, parse_info); + const ParseResult parse_result = ParseCode(state, address, parse_info); if (parse_result == ParseResult::AbnormalFlow) { - // if it's the end of the program, end it safely // if it's AbnormalFlow, we end it as false, ending the CFG reconstruction return false; } - block_info = CreateBlockInfo(state, address, parse_info.end_address); + BlockInfo* block_info = CreateBlockInfo(state, address, parse_info.end_address); block_info->branch = parse_info.branch_info; if (parse_info.branch_info.condition.IsUnconditional()) { return true; } - u32 fallthrough_address = parse_info.end_address + 1; + const u32 fallthrough_address = parse_info.end_address + 1; state.inspect_queries.push_front(fallthrough_address); return true; } bool TryQuery(CFGRebuildState& state) { - auto gather_labels = ([](ControlStack& cc, std::map& labels, BlockInfo& block) { + const auto gather_labels = ([](ControlStack& cc, std::map& labels, BlockInfo& block) { auto gather_start = labels.lower_bound(block.start); - auto gather_end = labels.upper_bound(block.end); + const auto gather_end = labels.upper_bound(block.end); while (gather_start != gather_end) { cc.Push(gather_start->second); gather_start++; @@ -419,21 +413,21 @@ bool TryQuery(CFGRebuildState& state) { return false; } Query& q = state.queries.front(); - u32 block_index = state.registered[q.address]; + const u32 block_index = state.registered[q.address]; BlockInfo& block = state.block_info[block_index]; // If the block is visted, check if the stacks match, else gather the ssy/pbk // labels into the current stack and look if the branch at the end of the block // consumes a label. Schedule new queries accordingly if (block.visited) { BlockStack& stack = state.stacks[q.address]; - bool all_okay = (stack.ssy_stack.Size() == 0 || q.ssy_stack.Compare(stack.ssy_stack)) && - (stack.pbk_stack.Size() == 0 || q.pbk_stack.Compare(stack.pbk_stack)); + const bool all_okay = + (stack.ssy_stack.Size() == 0 || q.ssy_stack.Compare(stack.ssy_stack)) && + (stack.pbk_stack.Size() == 0 || q.pbk_stack.Compare(stack.pbk_stack)); state.queries.pop_front(); return all_okay; } block.visited = true; - BlockStack bs{q}; - state.stacks[q.address] = bs; + state.stacks[q.address] = BlockStack{q}; Query q2(q); state.queries.pop_front(); gather_labels(q2.ssy_stack, state.ssy_labels, block); -- cgit v1.2.3 From d45fed303055fa699377bedcc3a7973bd03b7870 Mon Sep 17 00:00:00 2001 From: Fernando Sahmkow Date: Tue, 25 Jun 2019 20:40:38 -0400 Subject: shader_ir: Remove unnecessary constructors and use optional for ScanFlow result --- src/video_core/shader/control_flow.cpp | 21 ++++++--------------- 1 file changed, 6 insertions(+), 15 deletions(-) (limited to 'src/video_core/shader/control_flow.cpp') diff --git a/src/video_core/shader/control_flow.cpp b/src/video_core/shader/control_flow.cpp index deef0cd3a..6259ad594 100644 --- a/src/video_core/shader/control_flow.cpp +++ b/src/video_core/shader/control_flow.cpp @@ -29,10 +29,6 @@ struct ControlStack { std::array stack{}; u32 index{}; - ControlStack() {} - - ControlStack(const ControlStack& cp) = default; - bool Compare(const ControlStack& cs) const { if (index != cs.index) { return false; @@ -75,8 +71,6 @@ struct ControlStack { }; struct Query { - Query() {} - Query(const Query& q) = default; u32 address{}; ControlStack ssy_stack{}; ControlStack pbk_stack{}; @@ -91,8 +85,6 @@ struct BlockStack { }; struct BlockBranchInfo { - BlockBranchInfo() = default; - BlockBranchInfo(const BlockBranchInfo& b) = default; Condition condition{}; s32 address{exit_branch}; bool kill{}; @@ -102,7 +94,6 @@ struct BlockBranchInfo { }; struct BlockInfo { - BlockInfo() = default; u32 start{}; u32 end{}; bool visited{}; @@ -454,8 +445,8 @@ bool TryQuery(CFGRebuildState& state) { return true; } -bool ScanFlow(const ProgramCode& program_code, u32 program_size, u32 start_address, - ShaderCharacteristics& result_out) { +std::optional ScanFlow(const ProgramCode& program_code, u32 program_size, + u32 start_address) { CFGRebuildState state{program_code, program_size}; // Inspect Code and generate blocks state.labels.clear(); @@ -463,7 +454,7 @@ bool ScanFlow(const ProgramCode& program_code, u32 program_size, u32 start_addre state.inspect_queries.push_back(start_address); while (!state.inspect_queries.empty()) { if (!TryInspectAddress(state)) { - return false; + return {}; } } // Decompile Stacks @@ -480,7 +471,7 @@ bool ScanFlow(const ProgramCode& program_code, u32 program_size, u32 start_addre // Sort and organize results std::sort(state.block_info.begin(), state.block_info.end(), [](const BlockInfo& a, const BlockInfo& b) -> bool { return a.start < b.start; }); - result_out.blocks.clear(); + ShaderCharacteristics result_out{}; result_out.decompilable = decompiled; result_out.start = start_address; result_out.end = start_address; @@ -499,7 +490,7 @@ bool ScanFlow(const ProgramCode& program_code, u32 program_size, u32 start_addre } if (result_out.decompilable) { result_out.labels = std::move(state.labels); - return true; + return {result_out}; } // If it's not decompilable, merge the unlabelled blocks together auto back = result_out.blocks.begin(); @@ -513,6 +504,6 @@ bool ScanFlow(const ProgramCode& program_code, u32 program_size, u32 start_addre back = next; next++; } - return true; + return {result_out}; } } // namespace VideoCommon::Shader -- cgit v1.2.3 From cfb3db1a32975583b94a0df5f3ff0020254208c0 Mon Sep 17 00:00:00 2001 From: Fernando Sahmkow Date: Tue, 25 Jun 2019 20:56:04 -0400 Subject: shader_ir: Correct max sizing --- src/video_core/shader/control_flow.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/video_core/shader/control_flow.cpp') diff --git a/src/video_core/shader/control_flow.cpp b/src/video_core/shader/control_flow.cpp index 6259ad594..a26de6795 100644 --- a/src/video_core/shader/control_flow.cpp +++ b/src/video_core/shader/control_flow.cpp @@ -163,7 +163,7 @@ enum class ParseResult : u32 { ParseResult ParseCode(CFGRebuildState& state, u32 address, ParseInfo& parse_info) { u32 offset = static_cast(address); - const u32 end_address = static_cast(state.program_size - 10U) * 8U; + const u32 end_address = static_cast(state.program_size / 8U); const auto insert_label = ([](CFGRebuildState& state, u32 address) { auto pair = state.labels.emplace(address); -- cgit v1.2.3 From 34357b110c3f04f6b98ca586fd776b0df569b6d8 Mon Sep 17 00:00:00 2001 From: Fernando Sahmkow Date: Wed, 26 Jun 2019 12:19:43 -0400 Subject: shader_ir: Correct parsing of scheduling instructions and correct sizing --- src/video_core/shader/control_flow.cpp | 41 ++++++++++++++++++++++++---------- 1 file changed, 29 insertions(+), 12 deletions(-) (limited to 'src/video_core/shader/control_flow.cpp') diff --git a/src/video_core/shader/control_flow.cpp b/src/video_core/shader/control_flow.cpp index a26de6795..1775dfd81 100644 --- a/src/video_core/shader/control_flow.cpp +++ b/src/video_core/shader/control_flow.cpp @@ -20,10 +20,10 @@ using Tegra::Shader::OpCode; constexpr s32 unassigned_branch = -2; -/*** +/** * 'ControlStack' represents a static stack of control jumps such as SSY and PBK * stacks in Maxwell. - ***/ + **/ struct ControlStack { static constexpr std::size_t stack_fixed_size = 20; std::array stack{}; @@ -105,9 +105,11 @@ struct BlockInfo { }; struct CFGRebuildState { - explicit CFGRebuildState(const ProgramCode& program_code, const std::size_t program_size) - : program_code{program_code}, program_size{program_size} {} + explicit CFGRebuildState(const ProgramCode& program_code, const std::size_t program_size, + const u32 start) + : program_code{program_code}, program_size{program_size}, start{start} {} + u32 start{}; std::vector block_info{}; std::list inspect_queries{}; std::list queries{}; @@ -120,7 +122,7 @@ struct CFGRebuildState { const std::size_t program_size; }; -enum class BlockCollision : u32 { None = 0, Found = 1, Inside = 2 }; +enum class BlockCollision : u32 { None, Found, Inside }; std::pair::iterator> TryGetBlock(CFGRebuildState& state, u32 address) { @@ -155,15 +157,26 @@ Pred GetPredicate(u32 index, bool negated) { return static_cast(index + (negated ? 8 : 0)); } +/** + * Returns whether the instruction at the specified offset is a 'sched' instruction. + * Sched instructions always appear before a sequence of 3 instructions. + */ +constexpr bool IsSchedInstruction(u32 offset, u32 main_offset) { + constexpr u32 SchedPeriod = 4; + u32 absolute_offset = offset - main_offset; + + return (absolute_offset % SchedPeriod) == 0; +} + enum class ParseResult : u32 { - ControlCaught = 0, - BlockEnd = 1, - AbnormalFlow = 2, + ControlCaught, + BlockEnd, + AbnormalFlow, }; ParseResult ParseCode(CFGRebuildState& state, u32 address, ParseInfo& parse_info) { u32 offset = static_cast(address); - const u32 end_address = static_cast(state.program_size / 8U); + const u32 end_address = static_cast(state.program_size / sizeof(Instruction)); const auto insert_label = ([](CFGRebuildState& state, u32 address) { auto pair = state.labels.emplace(address); @@ -183,6 +196,10 @@ ParseResult ParseCode(CFGRebuildState& state, u32 address, ParseInfo& parse_info parse_info.branch_info.ignore = true; break; } + if (IsSchedInstruction(offset, state.start)) { + offset++; + continue; + } const Instruction instr = {state.program_code[offset]}; const auto opcode = OpCode::Decode(instr); if (!opcode || opcode->get().GetType() != OpCode::Type::Flow) { @@ -447,11 +464,11 @@ bool TryQuery(CFGRebuildState& state) { std::optional ScanFlow(const ProgramCode& program_code, u32 program_size, u32 start_address) { - CFGRebuildState state{program_code, program_size}; + CFGRebuildState state{program_code, program_size, start_address}; // Inspect Code and generate blocks state.labels.clear(); state.labels.emplace(start_address); - state.inspect_queries.push_back(start_address); + state.inspect_queries.push_back(state.start); while (!state.inspect_queries.empty()) { if (!TryInspectAddress(state)) { return {}; @@ -459,7 +476,7 @@ std::optional ScanFlow(const ProgramCode& program_code, u } // Decompile Stacks Query start_query{}; - start_query.address = start_address; + start_query.address = state.start; state.queries.push_back(start_query); bool decompiled = true; while (!state.queries.empty()) { -- cgit v1.2.3 From e7a88f0ab32625c1422583ce63d0f8f20086f7c3 Mon Sep 17 00:00:00 2001 From: Fernando Sahmkow Date: Wed, 26 Jun 2019 12:56:03 -0400 Subject: control_flow: Address feedback. --- src/video_core/shader/control_flow.cpp | 126 ++++++++++----------------------- 1 file changed, 37 insertions(+), 89 deletions(-) (limited to 'src/video_core/shader/control_flow.cpp') diff --git a/src/video_core/shader/control_flow.cpp b/src/video_core/shader/control_flow.cpp index 1775dfd81..7b424d65d 100644 --- a/src/video_core/shader/control_flow.cpp +++ b/src/video_core/shader/control_flow.cpp @@ -4,6 +4,7 @@ #include #include +#include #include #include #include @@ -20,68 +21,18 @@ using Tegra::Shader::OpCode; constexpr s32 unassigned_branch = -2; -/** - * 'ControlStack' represents a static stack of control jumps such as SSY and PBK - * stacks in Maxwell. - **/ -struct ControlStack { - static constexpr std::size_t stack_fixed_size = 20; - std::array stack{}; - u32 index{}; - - bool Compare(const ControlStack& cs) const { - if (index != cs.index) { - return false; - } - return std::memcmp(stack.data(), cs.stack.data(), index * sizeof(u32)) == 0; - } - - /// This compare just compares the top of the stack against one another - bool SoftCompare(const ControlStack& cs) const { - if (index == 0 || cs.index == 0) { - return index == cs.index; - } - return Top() == cs.Top(); - } - - u32 Size() const { - return index; - } - - u32 Top() const { - return stack[index - 1]; - } - - bool Push(u32 address) { - if (index >= stack.size()) { - return false; - } - stack[index] = address; - index++; - return true; - } - - bool Pop() { - if (index == 0) { - return false; - } - index--; - return true; - } -}; - struct Query { u32 address{}; - ControlStack ssy_stack{}; - ControlStack pbk_stack{}; + std::stack ssy_stack{}; + std::stack pbk_stack{}; }; struct BlockStack { BlockStack() = default; BlockStack(const BlockStack& b) = default; BlockStack(const Query& q) : ssy_stack{q.ssy_stack}, pbk_stack{q.pbk_stack} {} - ControlStack ssy_stack{}; - ControlStack pbk_stack{}; + std::stack ssy_stack{}; + std::stack pbk_stack{}; }; struct BlockBranchInfo { @@ -144,13 +95,13 @@ struct ParseInfo { u32 end_address{}; }; -BlockInfo* CreateBlockInfo(CFGRebuildState& state, u32 start, u32 end) { +BlockInfo& CreateBlockInfo(CFGRebuildState& state, u32 start, u32 end) { auto& it = state.block_info.emplace_back(); it.start = start; it.end = end; const u32 index = static_cast(state.block_info.size() - 1); state.registered.insert({start, index}); - return ⁢ + return it; } Pred GetPredicate(u32 index, bool negated) { @@ -174,16 +125,17 @@ enum class ParseResult : u32 { AbnormalFlow, }; -ParseResult ParseCode(CFGRebuildState& state, u32 address, ParseInfo& parse_info) { +std::pair ParseCode(CFGRebuildState& state, u32 address) { u32 offset = static_cast(address); const u32 end_address = static_cast(state.program_size / sizeof(Instruction)); + ParseInfo parse_info{}; - const auto insert_label = ([](CFGRebuildState& state, u32 address) { - auto pair = state.labels.emplace(address); + const auto insert_label = [](CFGRebuildState& state, u32 address) { + const auto pair = state.labels.emplace(address); if (pair.second) { state.inspect_queries.push_back(address); } - }); + }; while (true) { if (offset >= end_address) { @@ -229,11 +181,11 @@ ParseResult ParseCode(CFGRebuildState& state, u32 address, ParseInfo& parse_info parse_info.branch_info.ignore = false; parse_info.end_address = offset; - return ParseResult::ControlCaught; + return {ParseResult::ControlCaught, parse_info}; } case OpCode::Id::BRA: { if (instr.bra.constant_buffer != 0) { - return ParseResult::AbnormalFlow; + return {ParseResult::AbnormalFlow, parse_info}; } const auto pred_index = static_cast(instr.pred.pred_index); parse_info.branch_info.condition.predicate = @@ -248,7 +200,7 @@ ParseResult ParseCode(CFGRebuildState& state, u32 address, ParseInfo& parse_info offset++; continue; } - u32 branch_offset = offset + instr.bra.GetBranchTarget(); + const u32 branch_offset = offset + instr.bra.GetBranchTarget(); if (branch_offset == 0) { parse_info.branch_info.address = exit_branch; } else { @@ -261,10 +213,9 @@ ParseResult ParseCode(CFGRebuildState& state, u32 address, ParseInfo& parse_info parse_info.branch_info.ignore = false; parse_info.end_address = offset; - return ParseResult::ControlCaught; + return {ParseResult::ControlCaught, parse_info}; } case OpCode::Id::SYNC: { - parse_info.branch_info.condition; const auto pred_index = static_cast(instr.pred.pred_index); parse_info.branch_info.condition.predicate = GetPredicate(pred_index, instr.negate_pred != 0); @@ -285,10 +236,9 @@ ParseResult ParseCode(CFGRebuildState& state, u32 address, ParseInfo& parse_info parse_info.branch_info.ignore = false; parse_info.end_address = offset; - return ParseResult::ControlCaught; + return {ParseResult::ControlCaught, parse_info}; } case OpCode::Id::BRK: { - parse_info.branch_info.condition; const auto pred_index = static_cast(instr.pred.pred_index); parse_info.branch_info.condition.predicate = GetPredicate(pred_index, instr.negate_pred != 0); @@ -309,10 +259,9 @@ ParseResult ParseCode(CFGRebuildState& state, u32 address, ParseInfo& parse_info parse_info.branch_info.ignore = false; parse_info.end_address = offset; - return ParseResult::ControlCaught; + return {ParseResult::ControlCaught, parse_info}; } case OpCode::Id::KIL: { - parse_info.branch_info.condition; const auto pred_index = static_cast(instr.pred.pred_index); parse_info.branch_info.condition.predicate = GetPredicate(pred_index, instr.negate_pred != 0); @@ -333,7 +282,7 @@ ParseResult ParseCode(CFGRebuildState& state, u32 address, ParseInfo& parse_info parse_info.branch_info.ignore = false; parse_info.end_address = offset; - return ParseResult::ControlCaught; + return {ParseResult::ControlCaught, parse_info}; } case OpCode::Id::SSY: { const u32 target = offset + instr.bra.GetBranchTarget(); @@ -348,7 +297,7 @@ ParseResult ParseCode(CFGRebuildState& state, u32 address, ParseInfo& parse_info break; } case OpCode::Id::BRX: { - return ParseResult::AbnormalFlow; + return {ParseResult::AbnormalFlow, parse_info}; } default: break; @@ -360,7 +309,7 @@ ParseResult ParseCode(CFGRebuildState& state, u32 address, ParseInfo& parse_info parse_info.branch_info.is_sync = false; parse_info.branch_info.is_brk = false; parse_info.end_address = offset - 1; - return ParseResult::BlockEnd; + return {ParseResult::BlockEnd, parse_info}; } bool TryInspectAddress(CFGRebuildState& state) { @@ -377,10 +326,10 @@ bool TryInspectAddress(CFGRebuildState& state) { case BlockCollision::Inside: { // This case is the tricky one: // We need to Split the block in 2 sepparate blocks - auto it = search_result.second; - BlockInfo* block_info = CreateBlockInfo(state, address, it->end); + const auto it = search_result.second; + BlockInfo& block_info = CreateBlockInfo(state, address, it->end); it->end = address - 1; - block_info->branch = it->branch; + block_info.branch = it->branch; BlockBranchInfo forward_branch{}; forward_branch.address = address; forward_branch.ignore = true; @@ -390,15 +339,14 @@ bool TryInspectAddress(CFGRebuildState& state) { default: break; } - ParseInfo parse_info; - const ParseResult parse_result = ParseCode(state, address, parse_info); + const auto [parse_result, parse_info] = ParseCode(state, address); if (parse_result == ParseResult::AbnormalFlow) { // if it's AbnormalFlow, we end it as false, ending the CFG reconstruction return false; } - BlockInfo* block_info = CreateBlockInfo(state, address, parse_info.end_address); - block_info->branch = parse_info.branch_info; + BlockInfo& block_info = CreateBlockInfo(state, address, parse_info.end_address); + block_info.branch = parse_info.branch_info; if (parse_info.branch_info.condition.IsUnconditional()) { return true; } @@ -409,14 +357,15 @@ bool TryInspectAddress(CFGRebuildState& state) { } bool TryQuery(CFGRebuildState& state) { - const auto gather_labels = ([](ControlStack& cc, std::map& labels, BlockInfo& block) { + const auto gather_labels = [](std::stack& cc, std::map& labels, + BlockInfo& block) { auto gather_start = labels.lower_bound(block.start); const auto gather_end = labels.upper_bound(block.end); while (gather_start != gather_end) { - cc.Push(gather_start->second); + cc.push(gather_start->second); gather_start++; } - }); + }; if (state.queries.empty()) { return false; } @@ -428,9 +377,8 @@ bool TryQuery(CFGRebuildState& state) { // consumes a label. Schedule new queries accordingly if (block.visited) { BlockStack& stack = state.stacks[q.address]; - const bool all_okay = - (stack.ssy_stack.Size() == 0 || q.ssy_stack.Compare(stack.ssy_stack)) && - (stack.pbk_stack.Size() == 0 || q.pbk_stack.Compare(stack.pbk_stack)); + const bool all_okay = (stack.ssy_stack.size() == 0 || q.ssy_stack == stack.ssy_stack) && + (stack.pbk_stack.size() == 0 || q.pbk_stack == stack.pbk_stack); state.queries.pop_front(); return all_okay; } @@ -447,15 +395,15 @@ bool TryQuery(CFGRebuildState& state) { Query conditional_query{q2}; if (block.branch.is_sync) { if (block.branch.address == unassigned_branch) { - block.branch.address = conditional_query.ssy_stack.Top(); + block.branch.address = conditional_query.ssy_stack.top(); } - conditional_query.ssy_stack.Pop(); + conditional_query.ssy_stack.pop(); } if (block.branch.is_brk) { if (block.branch.address == unassigned_branch) { - block.branch.address = conditional_query.pbk_stack.Top(); + block.branch.address = conditional_query.pbk_stack.top(); } - conditional_query.pbk_stack.Pop(); + conditional_query.pbk_stack.pop(); } conditional_query.address = block.branch.address; state.queries.push_back(conditional_query); -- cgit v1.2.3 From dc4a93594cd74eb1f663213d3b340a83dd95842e Mon Sep 17 00:00:00 2001 From: Fernando Sahmkow Date: Wed, 26 Jun 2019 13:16:13 -0400 Subject: control_flow: Assert shaders bigger than limit. --- src/video_core/shader/control_flow.cpp | 2 ++ 1 file changed, 2 insertions(+) (limited to 'src/video_core/shader/control_flow.cpp') diff --git a/src/video_core/shader/control_flow.cpp b/src/video_core/shader/control_flow.cpp index 7b424d65d..bdf9d4dd4 100644 --- a/src/video_core/shader/control_flow.cpp +++ b/src/video_core/shader/control_flow.cpp @@ -139,6 +139,8 @@ std::pair ParseCode(CFGRebuildState& state, u32 address) while (true) { if (offset >= end_address) { + // ASSERT_OR_EXECUTE can't be used, as it ignores the break + ASSERT_MSG(false, "Shader passed the current limit!"); parse_info.branch_info.address = exit_branch; parse_info.branch_info.ignore = false; break; -- cgit v1.2.3 From e7c6045a03584ac5cd93e9030cdf4f47867f9ee3 Mon Sep 17 00:00:00 2001 From: Fernando Sahmkow Date: Thu, 27 Jun 2019 09:24:40 -0400 Subject: control_flow: Correct block breaking algorithm. --- src/video_core/shader/control_flow.cpp | 34 +++++++++++++++++----------------- 1 file changed, 17 insertions(+), 17 deletions(-) (limited to 'src/video_core/shader/control_flow.cpp') diff --git a/src/video_core/shader/control_flow.cpp b/src/video_core/shader/control_flow.cpp index bdf9d4dd4..fdcc970ff 100644 --- a/src/video_core/shader/control_flow.cpp +++ b/src/video_core/shader/control_flow.cpp @@ -75,19 +75,17 @@ struct CFGRebuildState { enum class BlockCollision : u32 { None, Found, Inside }; -std::pair::iterator> TryGetBlock(CFGRebuildState& state, - u32 address) { - auto it = state.block_info.begin(); - while (it != state.block_info.end()) { - if (it->start == address) { - return {BlockCollision::Found, it}; +std::pair TryGetBlock(CFGRebuildState& state, u32 address) { + const auto& blocks = state.block_info; + for (u32 index = 0; index < blocks.size(); index++) { + if (blocks[index].start == address) { + return {BlockCollision::Found, index}; } - if (it->IsInside(address)) { - return {BlockCollision::Inside, it}; + if (blocks[index].IsInside(address)) { + return {BlockCollision::Inside, index}; } - it++; } - return {BlockCollision::None, it}; + return {BlockCollision::None, -1}; } struct ParseInfo { @@ -318,24 +316,26 @@ bool TryInspectAddress(CFGRebuildState& state) { if (state.inspect_queries.empty()) { return false; } + const u32 address = state.inspect_queries.front(); state.inspect_queries.pop_front(); - const auto search_result = TryGetBlock(state, address); - switch (search_result.first) { + const auto [result, block_index] = TryGetBlock(state, address); + switch (result) { case BlockCollision::Found: { return true; } case BlockCollision::Inside: { // This case is the tricky one: // We need to Split the block in 2 sepparate blocks - const auto it = search_result.second; - BlockInfo& block_info = CreateBlockInfo(state, address, it->end); - it->end = address - 1; - block_info.branch = it->branch; + const u32 end = state.block_info[block_index].end; + BlockInfo& new_block = CreateBlockInfo(state, address, end); + BlockInfo& current_block = state.block_info[block_index]; + current_block.end = address - 1; + new_block.branch = current_block.branch; BlockBranchInfo forward_branch{}; forward_branch.address = address; forward_branch.ignore = true; - it->branch = forward_branch; + current_block.branch = forward_branch; return true; } default: -- cgit v1.2.3