Simplify OpPhi instructions referencing unreachable continues

In dead branch elimination, we already recognize unreachable continue
blocks, and update OpPhi instruction accordingly.  This change adds an
extra check: if the head block has exactly 1 other incoming edge, then
replace the OpPhi with the value from that edge.

Fixes #1314.

diff --git a/source/opt/dead_branch_elim_pass.cpp b/source/opt/dead_branch_elim_pass.cpp
index be2f3be..98663de 100644 (file)
--- a/source/opt/dead_branch_elim_pass.cpp
+++ b/source/opt/dead_branch_elim_pass.cpp
@@ -211,12 +211,17 @@ bool DeadBranchElimPass::FixPhiNodesInLiveBlocks(
         operands.push_back(inst->GetOperand(0u));
         operands.push_back(inst->GetOperand(1u));
         // Iterate through the incoming labels and determine which to keep
-        // and/or modify.
+        // and/or modify.  If there in an unreachable continue block, there will
+        // be an edge from that block to the header.  We need to keep it to
+        // maintain the structured control flow.  If the header has more that 2
+        // incoming edges, then the OpPhi must have an entry for that edge.
+        // However, if there is only one other incoming edge, the OpPhi can be
+        // eliminated.
         for (uint32_t i = 1; i < inst->NumInOperands(); i += 2) {
           ir::BasicBlock* inc = GetParentBlock(inst->GetSingleWordInOperand(i));
           auto cont_iter = unreachable_continues.find(inc);
           if (cont_iter != unreachable_continues.end() &&
-              cont_iter->second == &block) {
+              cont_iter->second == &block && inst->NumInOperands() > 4) {
             if (get_def_use_mgr()
                     ->GetDef(inst->GetSingleWordInOperand(i - 1))
                     ->opcode() == SpvOpUndef) {
@@ -250,7 +255,8 @@ bool DeadBranchElimPass::FixPhiNodesInLiveBlocks(
           modified = true;
           uint32_t continue_id = block.ContinueBlockIdIfAny();
           if (!backedge_added && continue_id != 0 &&
-              unreachable_continues.count(GetParentBlock(continue_id))) {
+              unreachable_continues.count(GetParentBlock(continue_id)) &&
+              operands.size() > 4) {
             // Changed the backedge to branch from the continue block instead
             // of a successor of the continue block. Add an entry to the phi to
             // provide an undef for the continue block. Since the successor of

diff --git a/test/opt/dead_branch_elim_test.cpp b/test/opt/dead_branch_elim_test.cpp
index fbe528f..bbf094f 100644 (file)
--- a/test/opt/dead_branch_elim_test.cpp
+++ b/test/opt/dead_branch_elim_test.cpp
@@ -1415,13 +1415,11 @@ OpFunctionEnd
   SinglePassRunAndMatch<opt::DeadBranchElimPass>(text, true);
 }
 
-TEST_F(DeadBranchElimTest, UnreachableLoopMergeAndContinueTargets) {
+TEST_F(DeadBranchElimTest, RemovePhiWithUnreachableContinue) {
   const std::string text = R"(
-; CHECK: [[undef:%\w+]] = OpUndef %bool
 ; CHECK: [[entry:%\w+]] = OpLabel
 ; CHECK-NEXT: OpBranch [[header:%\w+]]
-; CHECK: OpPhi %bool %false [[entry]] [[undef]] [[continue:%\w+]]
-; CHECK-NEXT: OpLoopMerge [[merge:%\w+]] [[continue]] None
+; CHECK: OpLoopMerge [[merge:%\w+]] [[continue:%\w+]] None
 ; CHECK-NEXT: OpBranch [[ret:%\w+]]
 ; CHECK-NEXT: [[ret]] = OpLabel
 ; CHECK-NEXT: OpReturn
@@ -1458,6 +1456,54 @@ OpFunctionEnd
   SinglePassRunAndMatch<opt::DeadBranchElimPass>(text, true);
 }
 
+TEST_F(DeadBranchElimTest, UnreachableLoopMergeAndContinueTargets) {
+  const std::string text = R"(
+; CHECK: [[undef:%\w+]] = OpUndef %bool
+; CHECK: OpSelectionMerge [[header:%\w+]]
+; CHECK-NEXT: OpBranchConditional {{%\w+}} [[if_lab:%\w+]] [[else_lab:%\w+]]
+; CHECK: OpPhi %bool %false [[if_lab]] %false [[else_lab]] [[undef]] [[continue:%\w+]]
+; CHECK-NEXT: OpLoopMerge [[merge:%\w+]] [[continue]] None
+; CHECK-NEXT: OpBranch [[ret:%\w+]]
+; CHECK-NEXT: [[ret]] = OpLabel
+; CHECK-NEXT: OpReturn
+; CHECK: [[continue]] = OpLabel
+; CHECK-NEXT: OpBranch [[header]]
+; CHECK: [[merge]] = OpLabel
+; CHECK-NEXT: OpUnreachable
+OpCapability Kernel
+OpCapability Linkage
+OpMemoryModel Logical OpenCL
+OpName %func "func"
+OpDecorate %func LinkageAttributes "func" Export
+%bool = OpTypeBool
+%false = OpConstantFalse %bool
+%true = OpConstantTrue %bool
+%void = OpTypeVoid
+%funcTy = OpTypeFunction %void
+%func = OpFunction %void None %funcTy
+%1 = OpLabel
+%c = OpUndef %bool
+OpSelectionMerge %2 None
+OpBranchConditional %c %if %else
+%if = OpLabel
+OpBranch %2
+%else = OpLabel
+OpBranch %2
+%2 = OpLabel
+%phi = OpPhi %bool %false %if %false %else %true %continue
+OpLoopMerge %merge %continue None
+OpBranch %3
+%3 = OpLabel
+OpReturn
+%continue = OpLabel
+OpBranch %2
+%merge = OpLabel
+OpReturn
+OpFunctionEnd
+)";
+
+  SinglePassRunAndMatch<opt::DeadBranchElimPass>(text, true);
+}
 TEST_F(DeadBranchElimTest, EarlyReconvergence) {
   const std::string text = R"(
 ; CHECK-NOT: OpBranchConditional
@@ -1721,12 +1767,10 @@ OpFunctionEnd
 
 TEST_F(DeadBranchElimTest, ExtraBackedgeBlocksUnreachable) {
   const std::string text = R"(
-; CHECK: [[undef:%\w+]] = OpUndef
 ; CHECK: [[entry:%\w+]] = OpLabel
 ; CHECK-NEXT: OpBranch [[header:%\w+]]
 ; CHECK-NEXT: [[header]] = OpLabel
-; CHECK-NEXT: OpPhi %bool %true [[entry]] [[undef]] [[continue:%\w+]]
-; CHECK-NEXT: OpLoopMerge [[merge:%\w+]] [[continue]] None
+; CHECK-NEXT: OpLoopMerge [[merge:%\w+]] [[continue:%\w+]] None
 ; CHECK-NEXT: OpBranch [[merge]]
 ; CHECK-NEXT: [[continue]] = OpLabel
 ; CHECK-NEXT: OpBranch [[header]]
@@ -1777,7 +1821,6 @@ OpEntryPoint Fragment %func "func"
 %1 = OpLabel
 OpBranch %2
 %2 = OpLabel
-%3 = OpPhi %bool %true %1 %undef %5
 OpLoopMerge %4 %5 None
 OpBranch %6
 %6 = OpLabel
@@ -1849,14 +1892,10 @@ OpFunctionEnd
 
 TEST_F(DeadBranchElimTest, UnreachableContinuePhiInMerge) {
   const std::string text = R"(
-; CHECK: [[float_undef:%\w+]] = OpUndef %float
-; CHECK: [[int_undef:%\w+]] = OpUndef %int
 ; CHECK: [[entry:%\w+]] = OpLabel
 ; CHECK-NEXT: OpBranch [[header:%\w+]]
 ; CHECK-NEXT: [[header]] = OpLabel
-; CHECK-NEXT: OpPhi %float {{%\w+}} [[entry]] [[float_undef]] [[continue:%\w+]]
-; CHECK-NEXT: OpPhi %int {{%\w+}} [[entry]] [[int_undef]] [[continue]]
-; CHECK-NEXT: OpLoopMerge [[merge:%\w+]] [[continue]] None
+; CHECK-NEXT: OpLoopMerge [[merge:%\w+]] [[continue:%\w+]] None
 ; CHECK-NEXT: OpBranch [[label:%\w+]]
 ; CHECK-NEXT: [[label]] = OpLabel
 ; CHECK-NEXT: [[fadd:%\w+]] = OpFAdd