From 7c3de19ce75378e699dab024ecf1b30442030137 Mon Sep 17 00:00:00 2001 From: GregF Date: Wed, 23 Aug 2017 17:05:38 -0600 Subject: [PATCH] DeadBranchElim: Fix dead block detection to ignore backedges - DeadBranchElim: Make sure to mark orphan'd merge blocks and continue targets as live. - Add test with loop in dead branch - Add test that orphan'd merge block is handled. Fixes https://github.com/KhronosGroup/SPIRV-Tools/issues/776 --- source/opt/basic_block.cpp | 13 +++ source/opt/basic_block.h | 4 + source/opt/dead_branch_elim_pass.cpp | 16 +++- test/opt/dead_branch_elim_test.cpp | 173 ++++++++++++++++++++++++++++++++++- 4 files changed, 204 insertions(+), 2 deletions(-) diff --git a/source/opt/basic_block.cpp b/source/opt/basic_block.cpp index 8ab2ec1..7b24907 100644 --- a/source/opt/basic_block.cpp +++ b/source/opt/basic_block.cpp @@ -37,6 +37,19 @@ void BasicBlock::ForEachSuccessorLabel( } } +void BasicBlock::ForMergeAndContinueLabel( + const std::function& f) { + auto ii = insts_.end(); + --ii; + if (ii == insts_.begin()) return; + --ii; + if ((*ii)->opcode() == SpvOpSelectionMerge || + (*ii)->opcode() == SpvOpLoopMerge) + (*ii)->ForEachInId([&f](const uint32_t* idp) { + f(*idp); + }); +} + } // namespace ir } // namespace spvtools diff --git a/source/opt/basic_block.h b/source/opt/basic_block.h index b30abe4..9e46b99 100644 --- a/source/opt/basic_block.h +++ b/source/opt/basic_block.h @@ -85,6 +85,10 @@ class BasicBlock { void ForEachSuccessorLabel( const std::function& f); + // Runs the given function |f| on the merge and continue label, if any + void ForMergeAndContinueLabel( + const std::function& f); + private: // The enclosing function. Function* function_; diff --git a/source/opt/dead_branch_elim_pass.cpp b/source/opt/dead_branch_elim_pass.cpp index 8e225fe..ef25705 100644 --- a/source/opt/dead_branch_elim_pass.cpp +++ b/source/opt/dead_branch_elim_pass.cpp @@ -217,16 +217,30 @@ bool DeadBranchElimPass::EliminateDeadBranches(ir::Function* func) { def_use_mgr_->KillInst(br); def_use_mgr_->KillInst(mergeInst); + // Initialize live block set to the live label + std::unordered_set liveLabIds; + liveLabIds.insert(liveLabId); + // Iterate to merge block adding dead blocks to elimination set auto dbi = bi; ++dbi; uint32_t dLabId = (*dbi)->id(); while (dLabId != mergeLabId) { - if (!HasNonPhiRef(dLabId)) { + if (liveLabIds.find(dLabId) == liveLabIds.end()) { // Kill use/def for all instructions and mark block for elimination KillAllInsts(*dbi); elimBlocks.insert(*dbi); } + else { + // Mark all successors as live + (*dbi)->ForEachSuccessorLabel([&liveLabIds](const uint32_t succId){ + liveLabIds.insert(succId); + }); + // Mark merge and continue blocks as live + (*dbi)->ForMergeAndContinueLabel([&liveLabIds](const uint32_t succId){ + liveLabIds.insert(succId); + }); + } ++dbi; dLabId = (*dbi)->id(); } diff --git a/test/opt/dead_branch_elim_test.cpp b/test/opt/dead_branch_elim_test.cpp index 46958fb..286232e 100644 --- a/test/opt/dead_branch_elim_test.cpp +++ b/test/opt/dead_branch_elim_test.cpp @@ -624,7 +624,7 @@ OpFunctionEnd predefs + before, predefs + after, true, true); } -TEST_F(DeadBranchElimTest, NoOrphanMerge) { +TEST_F(DeadBranchElimTest, PreventOrphanMerge) { const std::string predefs = R"(OpCapability Shader @@ -694,6 +694,72 @@ OpFunctionEnd predefs + before, predefs + after, true, true); } +TEST_F(DeadBranchElimTest, HandleOrphanMerge) { + + const std::string predefs = + R"(OpCapability Shader +%1 = OpExtInstImport "GLSL.std.450" +OpMemoryModel Logical GLSL450 +OpEntryPoint Fragment %main "main" %gl_FragColor +OpExecutionMode %main OriginUpperLeft +OpSource GLSL 140 +OpName %main "main" +OpName %foo_ "foo(" +OpName %gl_FragColor "gl_FragColor" +OpDecorate %gl_FragColor Location 0 +%void = OpTypeVoid +%6 = OpTypeFunction %void +%float = OpTypeFloat 32 +%v4float = OpTypeVector %float 4 +%9 = OpTypeFunction %v4float +%bool = OpTypeBool +%true = OpConstantTrue %bool +%float_0 = OpConstant %float 0 +%13 = OpConstantComposite %v4float %float_0 %float_0 %float_0 %float_0 +%float_1 = OpConstant %float 1 +%15 = OpConstantComposite %v4float %float_1 %float_1 %float_1 %float_1 +%_ptr_Output_v4float = OpTypePointer Output %v4float +%gl_FragColor = OpVariable %_ptr_Output_v4float Output +%main = OpFunction %void None %6 +%17 = OpLabel +%18 = OpFunctionCall %v4float %foo_ +OpStore %gl_FragColor %18 +OpReturn +OpFunctionEnd +)"; + + const std::string before = + R"(%foo_ = OpFunction %v4float None %9 +%19 = OpLabel +OpSelectionMerge %20 None +OpBranchConditional %true %21 %22 +%21 = OpLabel +OpReturnValue %13 +%22 = OpLabel +OpReturnValue %15 +%20 = OpLabel +%23 = OpUndef %v4float +OpReturnValue %23 +OpFunctionEnd +)"; + + const std::string after = + R"(%foo_ = OpFunction %v4float None %9 +%19 = OpLabel +OpSelectionMerge %20 None +OpBranchConditional %true %21 %20 +%21 = OpLabel +OpReturnValue %13 +%20 = OpLabel +%23 = OpUndef %v4float +OpReturnValue %23 +OpFunctionEnd +)"; + + SinglePassRunAndCheck( + predefs + before, predefs + after, true, true); +} + TEST_F(DeadBranchElimTest, KeepContinueTargetWhenKillAfterMerge) { // #version 450 // void main() { @@ -897,6 +963,111 @@ OpFunctionEnd predefs_before + before, predefs_after + after, true, true); } +TEST_F(DeadBranchElimTest, LoopInDeadBranch) { + // #version 450 + // + // layout(location = 0) in vec4 BaseColor; + // layout(location = 0) out vec4 OutColor; + // + // void main() + // { + // vec4 v = BaseColor; + // if (false) + // for (int i=0; i<3; i++) + // v = v * 0.5; + // OutColor = v; + // } + + const std::string predefs = + R"(OpCapability Shader +%1 = OpExtInstImport "GLSL.std.450" +OpMemoryModel Logical GLSL450 +OpEntryPoint Fragment %main "main" %BaseColor %OutColor +OpExecutionMode %main OriginUpperLeft +OpSource GLSL 450 +OpName %main "main" +OpName %v "v" +OpName %BaseColor "BaseColor" +OpName %i "i" +OpName %OutColor "OutColor" +OpDecorate %BaseColor Location 0 +OpDecorate %OutColor Location 0 +%void = OpTypeVoid +%8 = OpTypeFunction %void +%float = OpTypeFloat 32 +%v4float = OpTypeVector %float 4 +%_ptr_Function_v4float = OpTypePointer Function %v4float +%_ptr_Input_v4float = OpTypePointer Input %v4float +%BaseColor = OpVariable %_ptr_Input_v4float Input +%bool = OpTypeBool +%false = OpConstantFalse %bool +%int = OpTypeInt 32 1 +%_ptr_Function_int = OpTypePointer Function %int +%int_0 = OpConstant %int 0 +%int_3 = OpConstant %int 3 +%float_0_5 = OpConstant %float 0.5 +%int_1 = OpConstant %int 1 +%_ptr_Output_v4float = OpTypePointer Output %v4float +%OutColor = OpVariable %_ptr_Output_v4float Output +)"; + + const std::string before = + R"(%main = OpFunction %void None %8 +%22 = OpLabel +%v = OpVariable %_ptr_Function_v4float Function +%i = OpVariable %_ptr_Function_int Function +%23 = OpLoad %v4float %BaseColor +OpStore %v %23 +OpSelectionMerge %24 None +OpBranchConditional %false %25 %24 +%25 = OpLabel +OpStore %i %int_0 +OpBranch %26 +%26 = OpLabel +OpLoopMerge %27 %28 None +OpBranch %29 +%29 = OpLabel +%30 = OpLoad %int %i +%31 = OpSLessThan %bool %30 %int_3 +OpBranchConditional %31 %32 %27 +%32 = OpLabel +%33 = OpLoad %v4float %v +%34 = OpVectorTimesScalar %v4float %33 %float_0_5 +OpStore %v %34 +OpBranch %28 +%28 = OpLabel +%35 = OpLoad %int %i +%36 = OpIAdd %int %35 %int_1 +OpStore %i %36 +OpBranch %26 +%27 = OpLabel +OpBranch %24 +%24 = OpLabel +%37 = OpLoad %v4float %v +OpStore %OutColor %37 +OpReturn +OpFunctionEnd +)"; + + const std::string after = + R"(%main = OpFunction %void None %8 +%22 = OpLabel +%v = OpVariable %_ptr_Function_v4float Function +%i = OpVariable %_ptr_Function_int Function +%23 = OpLoad %v4float %BaseColor +OpStore %v %23 +OpBranch %24 +%24 = OpLabel +%37 = OpLoad %v4float %v +OpStore %OutColor %37 +OpReturn +OpFunctionEnd +)"; + + SinglePassRunAndCheck( + predefs + before, predefs + after, true, true); +} + // TODO(greg-lunarg): Add tests to verify handling of these cases: // // More complex control flow -- 2.7.4