Initial implementation of if conversion

* Handles simple cases only
* Identifies phis in blocks with two predecessors and attempts to
convert the phi to an select
 * does not perform code motion currently so the converted values must
 dominate the join point (e.g. can't be defined in the branches)
 * limited for now to two predecessors, but can be extended to handle
 more cases
* Adding if conversion to -O and -Os

2 files changed, 156 insertions, 0 deletions

diff --git a/test/opt/dominator_tree/CMakeLists.txt b/test/opt/dominator_tree/CMakeLists.txt
index 22778e49..31a5f322 100644
--- a/test/opt/dominator_tree/CMakeLists.txt
+++ b/test/opt/dominator_tree/CMakeLists.txt
@@ -72,3 +72,8 @@ add_spvtools_unittest(TARGET dominator_generated
          generated.cpp
     LIBS SPIRV-Tools-opt
 )
+
+add_spvtools_unittest(TARGET dominator_common_dominators
+    SRCS common_dominators.cpp
+    LIBS SPIRV-Tools-opt
+)
diff --git a/test/opt/dominator_tree/common_dominators.cpp b/test/opt/dominator_tree/common_dominators.cpp
new file mode 100644
index 00000000..612dc454
--- /dev/null
+++ b/test/opt/dominator_tree/common_dominators.cpp
@@ -0,0 +1,151 @@
+// Copyright (c) 2018 Google LLC
+//
+// 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 <gmock/gmock.h>
+#include <gtest/gtest.h>
+
+#include "opt/build_module.h"
+#include "opt/ir_context.h"
+
+namespace {
+
+using namespace spvtools;
+using CommonDominatorsTest = ::testing::Test;
+
+const std::string text = R"(
+OpCapability Shader
+OpMemoryModel Logical GLSL450
+OpEntryPoint Fragment %func "func"
+%void = OpTypeVoid
+%bool = OpTypeBool
+%true = OpConstantTrue %bool
+%functy = OpTypeFunction %void
+%func = OpFunction %void None %functy
+%1 = OpLabel
+OpBranch %2
+%2 = OpLabel
+OpLoopMerge %3 %4 None
+OpBranch %5
+%5 = OpLabel
+OpBranchConditional %true %3 %4
+%4 = OpLabel
+OpBranch %2
+%3 = OpLabel
+OpSelectionMerge %6 None
+OpBranchConditional %true %7 %8
+%7 = OpLabel
+OpBranch %6
+%8 = OpLabel
+OpBranch %9
+%9 = OpLabel
+OpBranch %6
+%6 = OpLabel
+OpBranch %10
+%11 = OpLabel
+OpBranch %10
+%10 = OpLabel
+OpReturn
+OpFunctionEnd
+)";
+
+ir::BasicBlock* GetBlock(uint32_t id, std::unique_ptr<ir::IRContext>& context) {
+  return context->get_instr_block(context->get_def_use_mgr()->GetDef(id));
+}
+
+TEST(CommonDominatorsTest, SameBlock) {
+  std::unique_ptr<ir::IRContext> context =
+      BuildModule(SPV_ENV_UNIVERSAL_1_2, nullptr, text,
+                  SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
+  EXPECT_NE(nullptr, context);
+
+  ir::CFG cfg(context->module());
+  opt::DominatorAnalysis* analysis =
+      context->GetDominatorAnalysis(&*context->module()->begin(), cfg);
+
+  for (auto& block : *context->module()->begin()) {
+    EXPECT_EQ(&block, analysis->CommonDominator(&block, &block));
+  }
+}
+
+TEST(CommonDominatorsTest, ParentAndChild) {
+  std::unique_ptr<ir::IRContext> context =
+      BuildModule(SPV_ENV_UNIVERSAL_1_2, nullptr, text,
+                  SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
+  EXPECT_NE(nullptr, context);
+
+  ir::CFG cfg(context->module());
+  opt::DominatorAnalysis* analysis =
+      context->GetDominatorAnalysis(&*context->module()->begin(), cfg);
+
+  EXPECT_EQ(
+      GetBlock(1u, context),
+      analysis->CommonDominator(GetBlock(1u, context), GetBlock(2u, context)));
+  EXPECT_EQ(
+      GetBlock(2u, context),
+      analysis->CommonDominator(GetBlock(2u, context), GetBlock(5u, context)));
+  EXPECT_EQ(
+      GetBlock(1u, context),
+      analysis->CommonDominator(GetBlock(1u, context), GetBlock(5u, context)));
+}
+
+TEST(CommonDominatorsTest, BranchSplit) {
+  std::unique_ptr<ir::IRContext> context =
+      BuildModule(SPV_ENV_UNIVERSAL_1_2, nullptr, text,
+                  SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
+  EXPECT_NE(nullptr, context);
+
+  ir::CFG cfg(context->module());
+  opt::DominatorAnalysis* analysis =
+      context->GetDominatorAnalysis(&*context->module()->begin(), cfg);
+
+  EXPECT_EQ(
+      GetBlock(3u, context),
+      analysis->CommonDominator(GetBlock(7u, context), GetBlock(8u, context)));
+  EXPECT_EQ(
+      GetBlock(3u, context),
+      analysis->CommonDominator(GetBlock(7u, context), GetBlock(9u, context)));
+}
+
+TEST(CommonDominatorsTest, LoopContinueAndMerge) {
+  std::unique_ptr<ir::IRContext> context =
+      BuildModule(SPV_ENV_UNIVERSAL_1_2, nullptr, text,
+                  SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
+  EXPECT_NE(nullptr, context);
+
+  ir::CFG cfg(context->module());
+  opt::DominatorAnalysis* analysis =
+      context->GetDominatorAnalysis(&*context->module()->begin(), cfg);
+
+  EXPECT_EQ(
+      GetBlock(5u, context),
+      analysis->CommonDominator(GetBlock(3u, context), GetBlock(4u, context)));
+}
+
+TEST(CommonDominatorsTest, NoCommonDominator) {
+  std::unique_ptr<ir::IRContext> context =
+      BuildModule(SPV_ENV_UNIVERSAL_1_2, nullptr, text,
+                  SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
+  EXPECT_NE(nullptr, context);
+
+  ir::CFG cfg(context->module());
+  opt::DominatorAnalysis* analysis =
+      context->GetDominatorAnalysis(&*context->module()->begin(), cfg);
+
+  EXPECT_EQ(nullptr, analysis->CommonDominator(GetBlock(10u, context),
+                                               GetBlock(11u, context)));
+  EXPECT_EQ(nullptr, analysis->CommonDominator(GetBlock(11u, context),
+                                               GetBlock(6u, context)));
+}
+
+}  // anonymous namespace