From 6136bf9e0b8f8a3fbaaca2edd927aa8dc7715d9d Mon Sep 17 00:00:00 2001 From: GregF Date: Fri, 26 May 2017 10:33:11 -0600 Subject: [PATCH] mem2reg: Add InsertExtractElimPass --- include/spirv-tools/optimizer.hpp | 12 ++ source/opt/CMakeLists.txt | 2 + source/opt/insert_extract_elim.cpp | 125 +++++++++++++ source/opt/insert_extract_elim.h | 77 ++++++++ source/opt/optimizer.cpp | 5 + source/opt/passes.h | 1 + test/opt/CMakeLists.txt | 5 + test/opt/insert_extract_elim_test.cpp | 334 ++++++++++++++++++++++++++++++++++ tools/opt/opt.cpp | 2 + 9 files changed, 563 insertions(+) create mode 100644 source/opt/insert_extract_elim.cpp create mode 100644 source/opt/insert_extract_elim.h create mode 100644 test/opt/insert_extract_elim_test.cpp diff --git a/include/spirv-tools/optimizer.hpp b/include/spirv-tools/optimizer.hpp index a5bcb0c..518fd9e 100644 --- a/include/spirv-tools/optimizer.hpp +++ b/include/spirv-tools/optimizer.hpp @@ -249,6 +249,18 @@ Optimizer::PassToken CreateLocalAccessChainConvertPass(); // as DeadBranchElimination which depend on values for their analysis. Optimizer::PassToken CreateLocalSingleStoreElimPass(); +// Creates an insert/extract elimination pass. +// This pass processes each entry point function in the module, searching for +// extracts on a sequence of inserts. It further searches the sequence for an +// insert with indices identical to the extract. If such an insert can be +// found before hitting a conflicting insert, the extract's result id is +// replaced with the id of the values from the insert. +// +// Besides removing extracts this pass enables subsequent dead code elimination +// passes to delete the inserts. This pass performs best after access chains are +// converted to inserts and extracts and local loads and stores are eliminated. +Optimizer::PassToken CreateInsertExtractElimPass(); + // Creates a compact ids pass. // The pass remaps result ids to a compact and gapless range starting from %1. Optimizer::PassToken CreateCompactIdsPass(); diff --git a/source/opt/CMakeLists.txt b/source/opt/CMakeLists.txt index 4e6ce65..72d4fcd 100644 --- a/source/opt/CMakeLists.txt +++ b/source/opt/CMakeLists.txt @@ -23,6 +23,7 @@ add_library(SPIRV-Tools-opt fold_spec_constant_op_and_composite_pass.h freeze_spec_constant_value_pass.h inline_pass.h + insert_extract_elim.h instruction.h ir_loader.h local_access_chain_convert_pass.h @@ -51,6 +52,7 @@ add_library(SPIRV-Tools-opt fold_spec_constant_op_and_composite_pass.cpp freeze_spec_constant_value_pass.cpp inline_pass.cpp + insert_extract_elim.cpp instruction.cpp ir_loader.cpp local_access_chain_convert_pass.cpp diff --git a/source/opt/insert_extract_elim.cpp b/source/opt/insert_extract_elim.cpp new file mode 100644 index 0000000..19d768f --- /dev/null +++ b/source/opt/insert_extract_elim.cpp @@ -0,0 +1,125 @@ +// Copyright (c) 2017 The Khronos Group Inc. +// Copyright (c) 2017 Valve Corporation +// Copyright (c) 2017 LunarG Inc. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +#include "insert_extract_elim.h" + +#include "iterator.h" + +static const int kSpvEntryPointFunctionId = 1; +static const int kSpvExtractCompositeId = 0; +static const int kSpvInsertObjectId = 0; +static const int kSpvInsertCompositeId = 1; + +namespace spvtools { +namespace opt { + +bool InsertExtractElimPass::ExtInsMatch(const ir::Instruction* extInst, + const ir::Instruction* insInst) const { + if (extInst->NumInOperands() != insInst->NumInOperands() - 1) + return false; + uint32_t numIdx = extInst->NumInOperands() - 1; + for (uint32_t i = 0; i < numIdx; ++i) + if (extInst->GetSingleWordInOperand(i + 1) != + insInst->GetSingleWordInOperand(i + 2)) + return false; + return true; +} + +bool InsertExtractElimPass::ExtInsConflict(const ir::Instruction* extInst, + const ir::Instruction* insInst) const { + if (extInst->NumInOperands() == insInst->NumInOperands() - 1) + return false; + uint32_t extNumIdx = extInst->NumInOperands() - 1; + uint32_t insNumIdx = insInst->NumInOperands() - 2; + uint32_t numIdx = std::min(extNumIdx, insNumIdx); + for (uint32_t i = 0; i < numIdx; ++i) + if (extInst->GetSingleWordInOperand(i + 1) != + insInst->GetSingleWordInOperand(i + 2)) + return false; + return true; +} + +bool InsertExtractElimPass::EliminateInsertExtract(ir::Function* func) { + bool modified = false; + for (auto bi = func->begin(); bi != func->end(); ++bi) { + for (auto ii = bi->begin(); ii != bi->end(); ++ii) { + switch (ii->opcode()) { + case SpvOpCompositeExtract: { + uint32_t cid = ii->GetSingleWordInOperand(kSpvExtractCompositeId); + ir::Instruction* cinst = def_use_mgr_->GetDef(cid); + uint32_t replId = 0; + while (cinst->opcode() == SpvOpCompositeInsert) { + if (ExtInsConflict(&*ii, cinst)) + break; + if (ExtInsMatch(&*ii, cinst)) { + replId = cinst->GetSingleWordInOperand(kSpvInsertObjectId); + break; + } + cid = cinst->GetSingleWordInOperand(kSpvInsertCompositeId); + cinst = def_use_mgr_->GetDef(cid); + } + if (replId != 0) { + const uint32_t extId = ii->result_id(); + (void)def_use_mgr_->ReplaceAllUsesWith(extId, replId); + def_use_mgr_->KillInst(&*ii); + modified = true; + } + } break; + default: + break; + } + } + } + return modified; +} + +void InsertExtractElimPass::Initialize(ir::Module* module) { + + module_ = module; + + // Initialize function and block maps + id2function_.clear(); + for (auto& fn : *module_) + id2function_[fn.result_id()] = &fn; + + // Do def/use on whole module + def_use_mgr_.reset(new analysis::DefUseManager(consumer(), module_)); +}; + +Pass::Status InsertExtractElimPass::ProcessImpl() { + bool modified = false; + + // Process all entry point functions. + for (auto& e : module_->entry_points()) { + ir::Function* fn = + id2function_[e.GetSingleWordOperand(kSpvEntryPointFunctionId)]; + modified = EliminateInsertExtract(fn) || modified; + } + + return modified ? Status::SuccessWithChange : Status::SuccessWithoutChange; +} + +InsertExtractElimPass::InsertExtractElimPass() + : module_(nullptr), def_use_mgr_(nullptr) {} + +Pass::Status InsertExtractElimPass::Process(ir::Module* module) { + Initialize(module); + return ProcessImpl(); +} + +} // namespace opt +} // namespace spvtools + diff --git a/source/opt/insert_extract_elim.h b/source/opt/insert_extract_elim.h new file mode 100644 index 0000000..cec4707 --- /dev/null +++ b/source/opt/insert_extract_elim.h @@ -0,0 +1,77 @@ +// Copyright (c) 2017 The Khronos Group Inc. +// Copyright (c) 2017 Valve Corporation +// Copyright (c) 2017 LunarG Inc. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +#ifndef LIBSPIRV_OPT_INSERT_EXTRACT_ELIM_PASS_H_ +#define LIBSPIRV_OPT_INSERT_EXTRACT_ELIM_PASS_H_ + + +#include +#include +#include +#include + +#include "basic_block.h" +#include "def_use_manager.h" +#include "module.h" +#include "pass.h" + +namespace spvtools { +namespace opt { + +// See optimizer.hpp for documentation. +class InsertExtractElimPass : public Pass { + public: + InsertExtractElimPass(); + const char* name() const override { return "insert_extract_elim"; } + Status Process(ir::Module*) override; + + private: + // Return true if indices of extract |extInst| and insert |insInst| match + bool ExtInsMatch( + const ir::Instruction* extInst, const ir::Instruction* insInst) const; + + // Return true if indices of extract |extInst| and insert |insInst| conflict, + // specifically, if the insert changes bits specified by the extract, but + // changes either more bits or less bits than the extract specifies, + // meaning the exact value being inserted cannot be used to replace + // the extract. + bool ExtInsConflict( + const ir::Instruction* extInst, const ir::Instruction* insInst) const; + + // Look for OpExtract on sequence of OpInserts in |func|. If there is an + // insert with identical indices, replace the extract with the value + // that is inserted if possible. Specifically, replace if there is no + // intervening insert which conflicts. + bool EliminateInsertExtract(ir::Function* func); + + void Initialize(ir::Module* module); + Pass::Status ProcessImpl(); + + // Module this pass is processing + ir::Module* module_; + + // Def-Uses for the module we are processing + std::unique_ptr def_use_mgr_; + + // Map from function's result id to function + std::unordered_map id2function_; +}; + +} // namespace opt +} // namespace spvtools + +#endif // LIBSPIRV_OPT_INSERT_EXTRACT_ELIM_PASS_H_ + diff --git a/source/opt/optimizer.cpp b/source/opt/optimizer.cpp index ca9ef5a..40cd75a 100644 --- a/source/opt/optimizer.cpp +++ b/source/opt/optimizer.cpp @@ -151,6 +151,11 @@ Optimizer::PassToken CreateLocalSingleStoreElimPass() { MakeUnique()); } +Optimizer::PassToken CreateInsertExtractElimPass() { + return MakeUnique( + MakeUnique()); +} + Optimizer::PassToken CreateCompactIdsPass() { return MakeUnique( MakeUnique()); diff --git a/source/opt/passes.h b/source/opt/passes.h index 259e0a0..3c5d6a7 100644 --- a/source/opt/passes.h +++ b/source/opt/passes.h @@ -22,6 +22,7 @@ #include "flatten_decoration_pass.h" #include "fold_spec_constant_op_and_composite_pass.h" #include "inline_pass.h" +#include "insert_extract_elim.h" #include "local_single_block_elim_pass.h" #include "local_single_store_elim_pass.h" #include "freeze_spec_constant_value_pass.h" diff --git a/test/opt/CMakeLists.txt b/test/opt/CMakeLists.txt index f8102b0..7461c12 100644 --- a/test/opt/CMakeLists.txt +++ b/test/opt/CMakeLists.txt @@ -58,6 +58,11 @@ add_spvtools_unittest(TARGET pass_inline LIBS SPIRV-Tools-opt ) +add_spvtools_unittest(TARGET pass_insert_extract_elim + SRCS insert_extract_elim_test.cpp pass_utils.cpp + LIBS SPIRV-Tools-opt +) + add_spvtools_unittest(TARGET pass_local_single_block_elim SRCS local_single_block_elim.cpp pass_utils.cpp LIBS SPIRV-Tools-opt diff --git a/test/opt/insert_extract_elim_test.cpp b/test/opt/insert_extract_elim_test.cpp new file mode 100644 index 0000000..18b31bb --- /dev/null +++ b/test/opt/insert_extract_elim_test.cpp @@ -0,0 +1,334 @@ +// Copyright (c) 2017 Valve Corporation +// Copyright (c) 2017 LunarG Inc. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +#include "pass_fixture.h" +#include "pass_utils.h" + +namespace { + +using namespace spvtools; + +using InsertExtractElimTest = PassTest<::testing::Test>; + +TEST_F(InsertExtractElimTest, Simple) { + // Note: The SPIR-V assembly has had store/load elimination + // performed to allow the inserts and extracts to directly + // reference each other. + // + // #version 140 + // + // in vec4 BaseColor; + // + // struct S_t { + // vec4 v0; + // vec4 v1; + // }; + // + // void main() + // { + // S_t s0; + // s0.v1 = BaseColor; + // gl_FragColor = s0.v1; + // } + + const std::string predefs = + R"(OpCapability Shader +%1 = OpExtInstImport "GLSL.std.450" +OpMemoryModel Logical GLSL450 +OpEntryPoint Fragment %main "main" %BaseColor %gl_FragColor +OpExecutionMode %main OriginUpperLeft +OpSource GLSL 140 +OpName %main "main" +OpName %S_t "S_t" +OpMemberName %S_t 0 "v0" +OpMemberName %S_t 1 "v1" +OpName %s0 "s0" +OpName %BaseColor "BaseColor" +OpName %gl_FragColor "gl_FragColor" +%void = OpTypeVoid +%8 = OpTypeFunction %void +%float = OpTypeFloat 32 +%v4float = OpTypeVector %float 4 +%S_t = OpTypeStruct %v4float %v4float +%_ptr_Function_S_t = OpTypePointer Function %S_t +%int = OpTypeInt 32 1 +%int_1 = OpConstant %int 1 +%_ptr_Input_v4float = OpTypePointer Input %v4float +%BaseColor = OpVariable %_ptr_Input_v4float Input +%_ptr_Function_v4float = OpTypePointer Function %v4float +%_ptr_Output_v4float = OpTypePointer Output %v4float +%gl_FragColor = OpVariable %_ptr_Output_v4float Output +)"; + + const std::string before = + R"(%main = OpFunction %void None %8 +%17 = OpLabel +%s0 = OpVariable %_ptr_Function_S_t Function +%18 = OpLoad %v4float %BaseColor +%19 = OpLoad %S_t %s0 +%20 = OpCompositeInsert %S_t %18 %19 1 +OpStore %s0 %20 +%21 = OpCompositeExtract %v4float %20 1 +OpStore %gl_FragColor %21 +OpReturn +OpFunctionEnd +)"; + + const std::string after = + R"(%main = OpFunction %void None %8 +%17 = OpLabel +%s0 = OpVariable %_ptr_Function_S_t Function +%18 = OpLoad %v4float %BaseColor +%19 = OpLoad %S_t %s0 +%20 = OpCompositeInsert %S_t %18 %19 1 +OpStore %s0 %20 +OpStore %gl_FragColor %18 +OpReturn +OpFunctionEnd +)"; + + SinglePassRunAndCheck(predefs + before, + predefs + after, true, true); +} + +TEST_F(InsertExtractElimTest, OptimizeAcrossNonConflictingInsert) { + // Note: The SPIR-V assembly has had store/load elimination + // performed to allow the inserts and extracts to directly + // reference each other. + // + // #version 140 + // + // in vec4 BaseColor; + // + // struct S_t { + // vec4 v0; + // vec4 v1; + // }; + // + // void main() + // { + // S_t s0; + // s0.v1 = BaseColor; + // s0.v0[2] = 0.0; + // gl_FragColor = s0.v1; + // } + + const std::string predefs = + R"(OpCapability Shader +%1 = OpExtInstImport "GLSL.std.450" +OpMemoryModel Logical GLSL450 +OpEntryPoint Fragment %main "main" %BaseColor %gl_FragColor +OpExecutionMode %main OriginUpperLeft +OpSource GLSL 140 +OpName %main "main" +OpName %S_t "S_t" +OpMemberName %S_t 0 "v0" +OpMemberName %S_t 1 "v1" +OpName %s0 "s0" +OpName %BaseColor "BaseColor" +OpName %gl_FragColor "gl_FragColor" +%void = OpTypeVoid +%8 = OpTypeFunction %void +%float = OpTypeFloat 32 +%v4float = OpTypeVector %float 4 +%S_t = OpTypeStruct %v4float %v4float +%_ptr_Function_S_t = OpTypePointer Function %S_t +%int = OpTypeInt 32 1 +%int_1 = OpConstant %int 1 +%float_0 = OpConstant %float 0 +%_ptr_Input_v4float = OpTypePointer Input %v4float +%BaseColor = OpVariable %_ptr_Input_v4float Input +%_ptr_Function_v4float = OpTypePointer Function %v4float +%_ptr_Output_v4float = OpTypePointer Output %v4float +%gl_FragColor = OpVariable %_ptr_Output_v4float Output +)"; + + const std::string before = + R"(%main = OpFunction %void None %8 +%18 = OpLabel +%s0 = OpVariable %_ptr_Function_S_t Function +%19 = OpLoad %v4float %BaseColor +%20 = OpLoad %S_t %s0 +%21 = OpCompositeInsert %S_t %19 %20 1 +%22 = OpCompositeInsert %S_t %float_0 %21 0 2 +OpStore %s0 %22 +%23 = OpCompositeExtract %v4float %22 1 +OpStore %gl_FragColor %23 +OpReturn +OpFunctionEnd +)"; + + const std::string after = + R"(%main = OpFunction %void None %8 +%18 = OpLabel +%s0 = OpVariable %_ptr_Function_S_t Function +%19 = OpLoad %v4float %BaseColor +%20 = OpLoad %S_t %s0 +%21 = OpCompositeInsert %S_t %19 %20 1 +%22 = OpCompositeInsert %S_t %float_0 %21 0 2 +OpStore %s0 %22 +OpStore %gl_FragColor %19 +OpReturn +OpFunctionEnd +)"; + + SinglePassRunAndCheck(predefs + before, + predefs + after, true, true); +} + +TEST_F(InsertExtractElimTest, ConflictingInsertPreventsOptimization) { + // Note: The SPIR-V assembly has had store/load elimination + // performed to allow the inserts and extracts to directly + // reference each other. + // + // #version 140 + // + // in vec4 BaseColor; + // + // struct S_t { + // vec4 v0; + // vec4 v1; + // }; + // + // void main() + // { + // S_t s0; + // s0.v1 = BaseColor; + // s0.v1[2] = 0.0; + // gl_FragColor = s0.v1; + // } + + const std::string assembly = + R"(OpCapability Shader +%1 = OpExtInstImport "GLSL.std.450" +OpMemoryModel Logical GLSL450 +OpEntryPoint Fragment %main "main" %BaseColor %gl_FragColor +OpExecutionMode %main OriginUpperLeft +OpSource GLSL 140 +OpName %main "main" +OpName %S_t "S_t" +OpMemberName %S_t 0 "v0" +OpMemberName %S_t 1 "v1" +OpName %s0 "s0" +OpName %BaseColor "BaseColor" +OpName %gl_FragColor "gl_FragColor" +%void = OpTypeVoid +%8 = OpTypeFunction %void +%float = OpTypeFloat 32 +%v4float = OpTypeVector %float 4 +%S_t = OpTypeStruct %v4float %v4float +%_ptr_Function_S_t = OpTypePointer Function %S_t +%int = OpTypeInt 32 1 +%int_1 = OpConstant %int 1 +%float_0 = OpConstant %float 0 +%_ptr_Input_v4float = OpTypePointer Input %v4float +%BaseColor = OpVariable %_ptr_Input_v4float Input +%_ptr_Function_v4float = OpTypePointer Function %v4float +%_ptr_Output_v4float = OpTypePointer Output %v4float +%gl_FragColor = OpVariable %_ptr_Output_v4float Output +%main = OpFunction %void None %8 +%18 = OpLabel +%s0 = OpVariable %_ptr_Function_S_t Function +%19 = OpLoad %v4float %BaseColor +%20 = OpLoad %S_t %s0 +%21 = OpCompositeInsert %S_t %19 %20 1 +%22 = OpCompositeInsert %S_t %float_0 %21 1 2 +OpStore %s0 %22 +%23 = OpCompositeExtract %v4float %22 1 +OpStore %gl_FragColor %23 +OpReturn +OpFunctionEnd +)"; + + SinglePassRunAndCheck(assembly, + assembly, true, true); +} + +TEST_F(InsertExtractElimTest, ConflictingInsertPreventsOptimization2) { + // Note: The SPIR-V assembly has had store/load elimination + // performed to allow the inserts and extracts to directly + // reference each other. + // + // #version 140 + // + // in vec4 BaseColor; + // + // struct S_t { + // vec4 v0; + // vec4 v1; + // }; + // + // void main() + // { + // S_t s0; + // s0.v1[1] = 1.0; + // s0.v1 = Baseline; + // gl_FragColor = vec4(s0.v1[1], 0.0, 0.0, 0.0); + // } + + const std::string assembly = + R"(OpCapability Shader +%1 = OpExtInstImport "GLSL.std.450" +OpMemoryModel Logical GLSL450 +OpEntryPoint Fragment %main "main" %BaseColor %gl_FragColor +OpExecutionMode %main OriginUpperLeft +OpSource GLSL 140 +OpName %main "main" +OpName %S_t "S_t" +OpMemberName %S_t 0 "v0" +OpMemberName %S_t 1 "v1" +OpName %s0 "s0" +OpName %BaseColor "BaseColor" +OpName %gl_FragColor "gl_FragColor" +%void = OpTypeVoid +%8 = OpTypeFunction %void +%float = OpTypeFloat 32 +%v4float = OpTypeVector %float 4 +%S_t = OpTypeStruct %v4float %v4float +%_ptr_Function_S_t = OpTypePointer Function %S_t +%int = OpTypeInt 32 1 +%int_1 = OpConstant %int 1 +%float_1 = OpConstant %float 1 +%uint = OpTypeInt 32 0 +%uint_1 = OpConstant %uint 1 +%_ptr_Function_float = OpTypePointer Function %float +%_ptr_Input_v4float = OpTypePointer Input %v4float +%BaseColor = OpVariable %_ptr_Input_v4float Input +%_ptr_Function_v4float = OpTypePointer Function %v4float +%_ptr_Output_v4float = OpTypePointer Output %v4float +%gl_FragColor = OpVariable %_ptr_Output_v4float Output +%float_0 = OpConstant %float 0 +%main = OpFunction %void None %8 +%22 = OpLabel +%s0 = OpVariable %_ptr_Function_S_t Function +%23 = OpLoad %S_t %s0 +%24 = OpCompositeInsert %S_t %float_1 %23 1 1 +%25 = OpLoad %v4float %BaseColor +%26 = OpCompositeInsert %S_t %25 %24 1 +%27 = OpCompositeExtract %float %26 1 1 +%28 = OpCompositeConstruct %v4float %27 %float_0 %float_0 %float_0 +OpStore %gl_FragColor %28 +OpReturn +OpFunctionEnd +)"; + + SinglePassRunAndCheck(assembly, + assembly, true, true); +} + +// TODO(greg-lunarg): Add tests to verify handling of these cases: +// + +} // anonymous namespace diff --git a/tools/opt/opt.cpp b/tools/opt/opt.cpp index d1fc4e6..48e7ef7 100644 --- a/tools/opt/opt.cpp +++ b/tools/opt/opt.cpp @@ -135,6 +135,8 @@ int main(int argc, char** argv) { optimizer.RegisterPass(CreateInlinePass()); } else if (0 == strcmp(cur_arg, "--convert-local-access-chains")) { optimizer.RegisterPass(CreateLocalAccessChainConvertPass()); + } else if (0 == strcmp(cur_arg, "--eliminate-insert-extract")) { + optimizer.RegisterPass(CreateInsertExtractElimPass()); } else if (0 == strcmp(cur_arg, "--eliminate-local-single-block")) { optimizer.RegisterPass(CreateLocalSingleBlockLoadStoreElimPass()); } else if (0 == strcmp(cur_arg, "--eliminate-local-single-store")) { -- 2.7.4