From 8dd3d93cf66beaa432686d2912ad3eeae2408dca Mon Sep 17 00:00:00 2001
From: GregF <greg@LunarG.com>
Date: Tue, 28 Nov 2017 16:18:05 -0700
Subject: [PATCH] AggressiveDCE: Add merge and continue branches for live loop.

This ensures that an if-break is not eliminated from a loop.

This fixes issue #989
---
 source/opt/aggressive_dead_code_elim_pass.cpp | 17 ++++++
 source/opt/aggressive_dead_code_elim_pass.h   |  3 +
 test/opt/aggressive_dead_code_elim_test.cpp   | 81 +++++++++++++++++++++++++++
 3 files changed, 101 insertions(+)

diff --git a/source/opt/aggressive_dead_code_elim_pass.cpp b/source/opt/aggressive_dead_code_elim_pass.cpp
index d8c5164..4704d40 100644
--- a/source/opt/aggressive_dead_code_elim_pass.cpp
+++ b/source/opt/aggressive_dead_code_elim_pass.cpp
@@ -31,6 +31,7 @@ const uint32_t kTypePointerStorageClassInIdx = 0;
 const uint32_t kEntryPointFunctionIdInIdx = 1;
 const uint32_t kSelectionMergeMergeBlockIdInIdx = 0;
 const uint32_t kLoopMergeMergeBlockIdInIdx = 0;
+const uint32_t kLoopMergeContinueBlockIdInIdx = 1;
 
 }  // namespace
 
@@ -163,6 +164,14 @@ void AggressiveDCEPass::AddBranch(uint32_t labelId, ir::BasicBlock* bp) {
   bp->AddInstruction(std::move(newBranch));
 }
 
+void AggressiveDCEPass::AddBranchesToWorklist(uint32_t labelId) {
+  get_def_use_mgr()->ForEachUser(labelId, [this](ir::Instruction* user) {
+    SpvOp op = user->opcode();
+    if (op == SpvOpBranchConditional || op == SpvOpBranch)
+      if (!IsLive(user)) AddToWorklist(user);
+  });
+}
+
 bool AggressiveDCEPass::AggressiveDCE(ir::Function* func) {
   // Compute map from instruction to block
   ComputeInst2BlockMap(func);
@@ -289,6 +298,14 @@ bool AggressiveDCEPass::AggressiveDCE(ir::Function* func) {
         ProcessLoad(varId);
       });
     }
+    // If loop merge, add all branches to continue and merge blocks
+    // to worklist
+    else if (liveInst->opcode() == SpvOpLoopMerge) {
+      AddBranchesToWorklist(
+          liveInst->GetSingleWordInOperand(kLoopMergeContinueBlockIdInIdx));
+      AddBranchesToWorklist(
+          liveInst->GetSingleWordInOperand(kLoopMergeMergeBlockIdInIdx));
+    }
     // If function parameter, treat as if it's result id is loaded from
     else if (liveInst->opcode() == SpvOpFunctionParameter) {
       ProcessLoad(liveInst->result_id());
diff --git a/source/opt/aggressive_dead_code_elim_pass.h b/source/opt/aggressive_dead_code_elim_pass.h
index 6540f3e..024d82c 100644
--- a/source/opt/aggressive_dead_code_elim_pass.h
+++ b/source/opt/aggressive_dead_code_elim_pass.h
@@ -101,6 +101,9 @@ class AggressiveDCEPass : public MemPass {
   // Add branch to |labelId| to end of block |bp|.
   void AddBranch(uint32_t labelId, ir::BasicBlock* bp);
 
+  // Add all branches to |labelId| to worklist if not already live
+  void AddBranchesToWorklist(uint32_t labelId);
+
   // For function |func|, mark all Stores to non-function-scope variables
   // and block terminating instructions as live. Recursively mark the values
   // they use. When complete, delete any non-live instructions. Return true
diff --git a/test/opt/aggressive_dead_code_elim_test.cpp b/test/opt/aggressive_dead_code_elim_test.cpp
index 0fc7b20..2531435 100644
--- a/test/opt/aggressive_dead_code_elim_test.cpp
+++ b/test/opt/aggressive_dead_code_elim_test.cpp
@@ -2108,6 +2108,87 @@ OpFunctionEnd
   SinglePassRunAndCheck<opt::AggressiveDCEPass>(assembly, assembly, true, true);
 }
 
+TEST_F(AggressiveDCETest, NoEliminateIfBreak) {
+  // Note: Assembly optimized from GLSL
+  //
+  // #version 450 
+  // 
+  // layout(location=0) in vec4 InColor;
+  // layout(location=0) out vec4 OutColor;
+  // 
+  // void main()
+  // {
+  //     float f = 0.0;
+  //     for (;;) {
+  //         f += 2.0;
+  //         if (f > 20.0)
+  //             break;
+  //     }
+  // 
+  //     OutColor = InColor / f;
+  // }
+
+  const std::string assembly =
+      R"(OpCapability Shader
+%1 = OpExtInstImport "GLSL.std.450"
+OpMemoryModel Logical GLSL450
+OpEntryPoint Fragment %main "main" %OutColor %InColor
+OpExecutionMode %main OriginUpperLeft
+OpSource GLSL 450
+OpName %main "main"
+OpName %f "f"
+OpName %OutColor "OutColor"
+OpName %InColor "InColor"
+OpDecorate %OutColor Location 0
+OpDecorate %InColor Location 0
+%void = OpTypeVoid
+%7 = OpTypeFunction %void
+%float = OpTypeFloat 32
+%_ptr_Function_float = OpTypePointer Function %float
+%float_0 = OpConstant %float 0
+%float_2 = OpConstant %float 2
+%float_20 = OpConstant %float 20
+%bool = OpTypeBool
+%v4float = OpTypeVector %float 4
+%_ptr_Output_v4float = OpTypePointer Output %v4float
+%OutColor = OpVariable %_ptr_Output_v4float Output
+%_ptr_Input_v4float = OpTypePointer Input %v4float
+%InColor = OpVariable %_ptr_Input_v4float Input
+%main = OpFunction %void None %7
+%17 = OpLabel
+%f = OpVariable %_ptr_Function_float Function
+OpStore %f %float_0
+OpBranch %18
+%18 = OpLabel
+OpLoopMerge %19 %20 None
+OpBranch %21
+%21 = OpLabel
+%22 = OpLoad %float %f
+%23 = OpFAdd %float %22 %float_2
+OpStore %f %23
+%24 = OpLoad %float %f
+%25 = OpFOrdGreaterThan %bool %24 %float_20
+OpSelectionMerge %26 None
+OpBranchConditional %25 %27 %26
+%27 = OpLabel
+OpBranch %19
+%26 = OpLabel
+OpBranch %20
+%20 = OpLabel
+OpBranch %18
+%19 = OpLabel
+%28 = OpLoad %v4float %InColor
+%29 = OpLoad %float %f
+%30 = OpCompositeConstruct %v4float %29 %29 %29 %29
+%31 = OpFDiv %v4float %28 %30
+OpStore %OutColor %31
+OpReturn
+OpFunctionEnd
+)";
+
+  SinglePassRunAndCheck<opt::AggressiveDCEPass>(assembly, assembly, true, true);
+}
+
 TEST_F(AggressiveDCETest, EliminateEntireFunctionBody) {
   // #version 450
   //
-- 
2.7.4