From b891845b533628d5c2240963d8a59937f800148b Mon Sep 17 00:00:00 2001 From: qining Date: Tue, 16 Aug 2016 13:06:03 -0400 Subject: [PATCH] Refine the DefUseManager * Fix the behavior when analyzing an individual instruction: * exisiting instruction: Clear the original records and re-analyze it as a new instruction. * new instruction with exisiting result id: Clear the original records of the exisiting result id. This means the records of the analyzed result-id-defining instruction will be overwritten by the record of the new instruction with the same result id. * new instruction with new result id or without result id: Just update the internal records to incorperate the new instruction. * Add tests for analyzing individual instruction w/o an exisiting module. * Refactor ClearInst() implementation * Remove ClearDef() function. * Fixed a bug in DefUseManager::ReplaceAllUsesWith() that OpName instruction may trigger the assertion incorrectly. * update the blurbs for EraseUseRecordsOfOperandIds() --- source/opt/def_use_manager.cpp | 105 ++++++++++------ source/opt/def_use_manager.h | 35 +++--- test/opt/test_def_use.cpp | 263 +++++++++++++++++++++++++++++++++++++++++ 3 files changed, 355 insertions(+), 48 deletions(-) diff --git a/source/opt/def_use_manager.cpp b/source/opt/def_use_manager.cpp index 455a51b..8cdc8f6 100644 --- a/source/opt/def_use_manager.cpp +++ b/source/opt/def_use_manager.cpp @@ -38,10 +38,22 @@ namespace analysis { void DefUseManager::AnalyzeInstDefUse(ir::Instruction* inst) { const uint32_t def_id = inst->result_id(); - // Clear the records of def_id first if it has been recorded before. - ClearDef(def_id); + if (def_id != 0) { + auto iter = id_to_def_.find(def_id); + if (iter != id_to_def_.end()) { + // Clear the original instruction that defining the same result id of the + // new instruction. + ClearInst(iter->second); + } + id_to_def_[def_id] = inst; + } else { + ClearInst(inst); + } - if (def_id != 0) id_to_def_[def_id] = inst; + // Create entry for the given instruction. Note that the instruction may + // not have any in-operands. In such cases, we still need a entry for those + // instructions so this manager knows it has seen the instruction later. + inst_to_used_ids_[inst] = {}; for (uint32_t i = 0; i < inst->NumOperands(); ++i) { switch (inst->GetOperand(i).type) { @@ -53,7 +65,7 @@ void DefUseManager::AnalyzeInstDefUse(ir::Instruction* inst) { uint32_t use_id = inst->GetSingleWordOperand(i); // use_id is used by the instruction generating def_id. id_to_uses_[use_id].push_back({inst, i}); - if (def_id != 0) result_id_to_used_ids_[def_id].push_back(use_id); + inst_to_used_ids_[inst].push_back(use_id); } break; default: break; @@ -62,24 +74,30 @@ void DefUseManager::AnalyzeInstDefUse(ir::Instruction* inst) { } ir::Instruction* DefUseManager::GetDef(uint32_t id) { - if (id_to_def_.count(id) == 0) return nullptr; - return id_to_def_.at(id); + auto iter = id_to_def_.find(id); + if (iter == id_to_def_.end()) return nullptr; + return iter->second; } UseList* DefUseManager::GetUses(uint32_t id) { - if (id_to_uses_.count(id) == 0) return nullptr; - return &id_to_uses_.at(id); + auto iter = id_to_uses_.find(id); + if (iter == id_to_uses_.end()) return nullptr; + return &iter->second; } bool DefUseManager::KillDef(uint32_t id) { - if (id_to_def_.count(id) == 0) return false; - - ir::Instruction* defining_inst = id_to_def_.at(id); - ClearDef(id); - defining_inst->ToNop(); + auto iter = id_to_def_.find(id); + if (iter == id_to_def_.end()) return false; + KillInst(iter->second); return true; } +void DefUseManager::KillInst(ir::Instruction* inst) { + if (!inst) return; + ClearInst(inst); + inst->ToNop(); +} + bool DefUseManager::ReplaceAllUsesWith(uint32_t before, uint32_t after) { if (before == after) return false; if (id_to_uses_.count(before) == 0) return false; @@ -88,14 +106,21 @@ bool DefUseManager::ReplaceAllUsesWith(uint32_t before, uint32_t after) { ++it) { const uint32_t type_result_id_count = (it->inst->result_id() != 0) + (it->inst->type_id() != 0); - if (!it->operand_index) { - assert(it->inst->type_id() != 0 && - "result type id considered as using while the instruction doesn't " - "have a result type id"); - it->inst->SetResultType(after); + + if (it->operand_index < type_result_id_count) { + // Update the type_id. Note that result id is immutable so it should + // never be updated. + if (it->inst->type_id() != 0 && it->operand_index == 0) { + it->inst->SetResultType(after); + } else if (it->inst->type_id() == 0) { + assert(false && + "Result type id considered as using while the instruction " + "doesn't have a result type id."); + } else { + assert(false && "Trying Setting the result id which is immutable."); + } } else { - assert(it->operand_index >= type_result_id_count && - "the operand to be set is not an in-operand."); + // Update an in-operand. uint32_t in_operand_pos = it->operand_index - type_result_id_count; // Make the modification in the instruction. it->inst->SetInOperand(in_operand_pos, {after}); @@ -109,30 +134,42 @@ bool DefUseManager::ReplaceAllUsesWith(uint32_t before, uint32_t after) { } void DefUseManager::AnalyzeDefUse(ir::Module* module) { + if (!module) return; module->ForEachInst(std::bind(&DefUseManager::AnalyzeInstDefUse, this, std::placeholders::_1)); } -void DefUseManager::ClearDef(uint32_t def_id) { - if (id_to_def_.count(def_id) == 0) return; +void DefUseManager::ClearInst(ir::Instruction* inst) { + auto iter = inst_to_used_ids_.find(inst); + if (iter != inst_to_used_ids_.end()) { + EraseUseRecordsOfOperandIds(inst); + if (inst->result_id() != 0) { + id_to_uses_.erase(inst->result_id()); // Remove all uses of this id. + id_to_def_.erase(inst->result_id()); + } + } +} +void DefUseManager::EraseUseRecordsOfOperandIds(const ir::Instruction* inst) { // Go through all ids used by this instruction, remove this instruction's // uses of them. - for (const auto use_id : result_id_to_used_ids_[def_id]) { - if (id_to_uses_.count(use_id) == 0) continue; - auto& uses = id_to_uses_[use_id]; - for (auto it = uses.begin(); it != uses.end();) { - if (it->inst->result_id() == def_id) { - it = uses.erase(it); - } else { - ++it; + auto iter = inst_to_used_ids_.find(inst); + if (iter != inst_to_used_ids_.end()) { + for (const auto use_id : iter->second) { + auto uses_iter = id_to_uses_.find(use_id); + if (uses_iter == id_to_uses_.end()) continue; + auto& uses = uses_iter->second; + for (auto it = uses.begin(); it != uses.end();) { + if (it->inst == inst) { + it = uses.erase(it); + } else { + ++it; + } } + if (uses.empty()) id_to_uses_.erase(use_id); } - if (uses.empty()) id_to_uses_.erase(use_id); + inst_to_used_ids_.erase(inst); } - result_id_to_used_ids_.erase(def_id); - id_to_uses_.erase(def_id); // Remove all uses of this id. - id_to_def_.erase(def_id); } } // namespace analysis diff --git a/source/opt/def_use_manager.h b/source/opt/def_use_manager.h index 99d073f..77483a1 100644 --- a/source/opt/def_use_manager.h +++ b/source/opt/def_use_manager.h @@ -80,10 +80,13 @@ class DefUseManager { // Turns the instruction defining the given |id| into a Nop. Returns true on // success, false if the given |id| is not defined at all. This method also - // erases both the uses of |id| and the |id|-generating instruction's use - // information kept in this manager, but not the operands in the original - // instructions. + // erases both the uses of |id| and the information of this |id|-generating + // instruction's uses of its operands. bool KillDef(uint32_t id); + // Turns the given instruction |inst| to a Nop. This method erases the + // information of the given instruction's uses of its operands. If |inst| + // defines an result id, the uses of the result id will also be erased. + void KillInst(ir::Instruction* inst); // Replaces all uses of |before| id with |after| id. Returns true if any // replacement happens. This method does not kill the definition of the // |before| id. If |after| is the same as |before|, does nothing and returns @@ -91,24 +94,28 @@ class DefUseManager { bool ReplaceAllUsesWith(uint32_t before, uint32_t after); private: + using InstToUsedIdsMap = + std::unordered_map>; + // Analyzes the defs and uses in the given |module| and populates data - // structures in this class. + // structures in this class. Does nothing if |module| is nullptr. void AnalyzeDefUse(ir::Module* module); - // Clear the internal def-use record of a defined id if the given |def_id| is - // recorded by this manager. This method will erase both the uses of |def_id| - // and the |def_id|-generating instruction's use information kept in this - // manager, but not the operands in the original instructions. - void ClearDef(uint32_t def_id); + // Clear the internal def-use record of the given instruction |inst|. This + // method will update the use information of the operand ids of |inst|. The + // record: |inst| uses an |id|, will be removed from the use records of |id|. + // If |inst| defines an result id, the use record of this result id will also + // be removed. Does nothing if |inst| was not analyzed before. + void ClearInst(ir::Instruction* inst); - using ResultIdToUsedIdsMap = - std::unordered_map>; + // Erases the records that a given instruction uses its operand ids. + void EraseUseRecordsOfOperandIds(const ir::Instruction* inst); IdToDefMap id_to_def_; // Mapping from ids to their definitions IdToUsesMap id_to_uses_; // Mapping from ids to their uses - // Mapping from result ids to the ids used in the instructions generating the - // result ids. - ResultIdToUsedIdsMap result_id_to_used_ids_; + // Mapping from instructions to the ids used in the instructions generating + // the result ids. + InstToUsedIdsMap inst_to_used_ids_; }; } // namespace analysis diff --git a/test/opt/test_def_use.cpp b/test/opt/test_def_use.cpp index 0a27506..608a7ca 100644 --- a/test/opt/test_def_use.cpp +++ b/test/opt/test_def_use.cpp @@ -25,6 +25,7 @@ // MATERIALS OR THE USE OR OTHER DEALINGS IN THE MATERIALS. #include +#include #include #include @@ -1151,4 +1152,266 @@ TEST(DefUseTest, OpSwitch) { } } +// Creates an |result_id| = OpTypeInt 32 1 instruction. +ir::Instruction Int32TypeInstruction(uint32_t result_id) { + return ir::Instruction(SpvOp::SpvOpTypeInt, 0, result_id, + {ir::Operand(SPV_OPERAND_TYPE_LITERAL_INTEGER, {32}), + ir::Operand(SPV_OPERAND_TYPE_LITERAL_INTEGER, {1})}); +} + +// Creates an |result_id| = OpConstantTrue/Flase |type_id| instruction. +ir::Instruction ConstantBoolInstruction(bool value, uint32_t type_id, + uint32_t result_id) { + return ir::Instruction( + value ? SpvOp::SpvOpConstantTrue : SpvOp::SpvOpConstantFalse, type_id, + result_id, {}); +} + +// Creates an |result_id| = OpLabel instruction. +ir::Instruction LabelInstruction(uint32_t result_id) { + return ir::Instruction(SpvOp::SpvOpLabel, 0, result_id, {}); +} + +// Creates an OpBranch |target_id| instruction. +ir::Instruction BranchInstruction(uint32_t target_id) { + return ir::Instruction(SpvOp::SpvOpBranch, 0, 0, + { + ir::Operand(SPV_OPERAND_TYPE_ID, {target_id}), + }); +} + +// Test case for analyzing individual instructions. +struct AnalyzeInstDefUseTestCase { + std::vector insts; // instrutions to be analyzed in order. + const char* module_text; + InstDefUse expected_define_use; +}; + +using AnalyzeInstDefUseTest = + ::testing::TestWithParam; + +// Test the analyzing result for individual instructions. +TEST_P(AnalyzeInstDefUseTest, Case) { + auto tc = GetParam(); + + // Build module. + std::unique_ptr module = + SpvTools(SPV_ENV_UNIVERSAL_1_1).BuildModule(tc.module_text); + ASSERT_NE(nullptr, module); + + // Analyze the instructions. + opt::analysis::DefUseManager manager(module.get()); + for (ir::Instruction& inst : tc.insts) { + manager.AnalyzeInstDefUse(&inst); + } + + CheckDef(tc.expected_define_use, manager.id_to_defs()); + CheckUse(tc.expected_define_use, manager.id_to_uses()); +} + +// clang-format off +INSTANTIATE_TEST_CASE_P( + TestCase, AnalyzeInstDefUseTest, + ::testing::ValuesIn(std::vector{ + { // A type declaring instruction. + {Int32TypeInstruction(1)}, + "", + { + // defs + {{1, "%1 = OpTypeInt 32 1"}}, + {}, // no uses + }, + }, + { // A type declaring instruction and a constant value. + { + Int32TypeInstruction(1), + ConstantBoolInstruction(true, 1, 2), + }, + "", + { + { // defs + {1, "%1 = OpTypeInt 32 1"}, + {2, "%2 = OpConstantTrue %1"}, // It is fine the SPIR-V code here is invalid. + }, + { // uses + {1, {"%2 = OpConstantTrue %1"}}, + }, + }, + }, + { // Analyze two instrutions that have same result id. The def use info + // of the result id from the first instruction should be overwritten by + // the second instruction. + { + ConstantBoolInstruction(true, 1, 2), + // The def-use info of the following instruction should overwrite the + // records of the above one. + ConstantBoolInstruction(false, 3, 2), + }, + "", + { + // defs + {{2, "%2 = OpConstantFalse %3"}}, + // uses + {{3, {"%2 = OpConstantFalse %3"}}} + } + }, + { // Analyze forward reference instruction, also instruction that does + // not have result id. + { + BranchInstruction(2), + LabelInstruction(2), + }, + "", + { + // defs + {{2, "%2 = OpLabel"}}, + // uses + {{2, {"OpBranch %2"}}}, + } + }, + { // Analyzing an additional instruction with new result id to an + // existing module. + { + ConstantBoolInstruction(true, 1, 2), + }, + "%1 = OpTypeInt 32 1 ", + { + { // defs + {1, "%1 = OpTypeInt 32 1"}, + {2, "%2 = OpConstantTrue %1"}, + }, + { // uses + {1, {"%2 = OpConstantTrue %1"}}, + }, + } + }, + { // Analyzing an additional instruction with existing result id to an + // existing module. + { + ConstantBoolInstruction(true, 1, 2), + }, + "%1 = OpTypeInt 32 1 " + "%2 = OpTypeBool ", + { + { // defs + {1, "%1 = OpTypeInt 32 1"}, + {2, "%2 = OpConstantTrue %1"}, + }, + { // uses + {1, {"%2 = OpConstantTrue %1"}}, + }, + } + }, + })); +// clang-format on + +struct KillInstTestCase { + const char* before; + std::unordered_set indices_for_inst_to_kill; + const char* after; + InstDefUse expected_define_use; +}; + +using KillInstTest = ::testing::TestWithParam; + +TEST_P(KillInstTest, Case) { + auto tc = GetParam(); + + // Build module. + std::unique_ptr module = + SpvTools(SPV_ENV_UNIVERSAL_1_1).BuildModule(tc.before); + ASSERT_NE(nullptr, module); + + // KillInst + uint32_t index = 0; + opt::analysis::DefUseManager manager(module.get()); + module->ForEachInst([&index, &tc, &manager](ir::Instruction* inst) { + if (tc.indices_for_inst_to_kill.count(index) != 0) { + manager.KillInst(inst); + } + index++; + }); + + EXPECT_EQ(tc.after, DisassembleModule(module.get())); + CheckDef(tc.expected_define_use, manager.id_to_defs()); + CheckUse(tc.expected_define_use, manager.id_to_uses()); +} + +// clang-format off +INSTANTIATE_TEST_CASE_P( + TestCase, KillInstTest, + ::testing::ValuesIn(std::vector{ + // Kill id defining instructions. + { + "%2 = OpFunction %1 None %3 " + "%4 = OpLabel " + " OpBranch %5 " + "%5 = OpLabel " + " OpBranch %6 " + "%6 = OpLabel " + " OpBranch %4 " + "%7 = OpLabel " + " OpReturn " + " OpFunctionEnd", + {0, 3, 5, 7}, + "OpNop\n" + "%4 = OpLabel\n" + "OpBranch %5\n" + "OpNop\n" + "OpBranch %6\n" + "OpNop\n" + "OpBranch %4\n" + "OpNop\n" + "OpReturn\n" + "OpFunctionEnd", + { + // defs + {{4, "%4 = OpLabel"}}, + // uses + {{4, {"OpBranch %4"}}} + } + }, + // Kill instructions that do not have result ids. + { + "%2 = OpFunction %1 None %3 " + "%4 = OpLabel " + " OpBranch %5 " + "%5 = OpLabel " + " OpBranch %6 " + "%6 = OpLabel " + " OpBranch %4 " + "%7 = OpLabel " + " OpReturn " + " OpFunctionEnd", + {2, 4}, + "%2 = OpFunction %1 None %3\n" + "%4 = OpLabel\n" + "OpNop\n" + "%5 = OpLabel\n" + "OpNop\n" + "%6 = OpLabel\n" + "OpBranch %4\n" + "%7 = OpLabel\n" + "OpReturn\n" + "OpFunctionEnd", + { + // defs + { + {2, "%2 = OpFunction %1 None %3"}, + {4, "%4 = OpLabel"}, + {5, "%5 = OpLabel"}, + {6, "%6 = OpLabel"}, + {7, "%7 = OpLabel"}, + }, + // uses + { + {1, {"%2 = OpFunction %1 None %3"}}, + {3, {"%2 = OpFunction %1 None %3"}}, + {4, {"OpBranch %4"}}, + } + } + }, + })); +// clang-format on + } // anonymous namespace -- 2.7.4