Home | History | Annotate | Download | only in dominator_tree 
      1 // Copyright (c) 2018 Google LLC
      2 //
      3 // Licensed under the Apache License, Version 2.0 (the "License");
      4 // you may not use this file except in compliance with the License.
      5 // You may obtain a copy of the License at
      6 //
      7 //     http://www.apache.org/licenses/LICENSE-2.0
      8 //
      9 // Unless required by applicable law or agreed to in writing, software
     10 // distributed under the License is distributed on an "AS IS" BASIS,
     11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     12 // See the License for the specific language governing permissions and
     13 // limitations under the License.
     14 
     15 #include <memory>
     16 #include <string>
     17 
     18 #include "gmock/gmock.h"
     19 #include "gtest/gtest.h"
     20 #include "source/opt/build_module.h"
     21 #include "source/opt/ir_context.h"
     22 
     23 namespace spvtools {
     24 namespace opt {
     25 namespace {
     26 
     27 using CommonDominatorsTest = ::testing::Test;
     28 
     29 const std::string text = R"(
     30 OpCapability Shader
     31 OpMemoryModel Logical GLSL450
     32 OpEntryPoint Fragment %func "func"
     33 %void = OpTypeVoid
     34 %bool = OpTypeBool
     35 %true = OpConstantTrue %bool
     36 %functy = OpTypeFunction %void
     37 %func = OpFunction %void None %functy
     38 %1 = OpLabel
     39 OpBranch %2
     40 %2 = OpLabel
     41 OpLoopMerge %3 %4 None
     42 OpBranch %5
     43 %5 = OpLabel
     44 OpBranchConditional %true %3 %4
     45 %4 = OpLabel
     46 OpBranch %2
     47 %3 = OpLabel
     48 OpSelectionMerge %6 None
     49 OpBranchConditional %true %7 %8
     50 %7 = OpLabel
     51 OpBranch %6
     52 %8 = OpLabel
     53 OpBranch %9
     54 %9 = OpLabel
     55 OpBranch %6
     56 %6 = OpLabel
     57 OpBranch %10
     58 %11 = OpLabel
     59 OpBranch %10
     60 %10 = OpLabel
     61 OpReturn
     62 OpFunctionEnd
     63 )";
     64 
     65 BasicBlock* GetBlock(uint32_t id, std::unique_ptr<IRContext>& context) {
     66   return context->get_instr_block(context->get_def_use_mgr()->GetDef(id));
     67 }
     68 
     69 TEST(CommonDominatorsTest, SameBlock) {
     70   std::unique_ptr<IRContext> context =
     71       BuildModule(SPV_ENV_UNIVERSAL_1_2, nullptr, text,
     72                   SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
     73   EXPECT_NE(nullptr, context);
     74 
     75   DominatorAnalysis* analysis =
     76       context->GetDominatorAnalysis(&*context->module()->begin());
     77 
     78   for (auto& block : *context->module()->begin()) {
     79     EXPECT_EQ(&block, analysis->CommonDominator(&block, &block));
     80   }
     81 }
     82 
     83 TEST(CommonDominatorsTest, ParentAndChild) {
     84   std::unique_ptr<IRContext> context =
     85       BuildModule(SPV_ENV_UNIVERSAL_1_2, nullptr, text,
     86                   SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
     87   EXPECT_NE(nullptr, context);
     88 
     89   DominatorAnalysis* analysis =
     90       context->GetDominatorAnalysis(&*context->module()->begin());
     91 
     92   EXPECT_EQ(
     93       GetBlock(1u, context),
     94       analysis->CommonDominator(GetBlock(1u, context), GetBlock(2u, context)));
     95   EXPECT_EQ(
     96       GetBlock(2u, context),
     97       analysis->CommonDominator(GetBlock(2u, context), GetBlock(5u, context)));
     98   EXPECT_EQ(
     99       GetBlock(1u, context),
    100       analysis->CommonDominator(GetBlock(1u, context), GetBlock(5u, context)));
    101 }
    102 
    103 TEST(CommonDominatorsTest, BranchSplit) {
    104   std::unique_ptr<IRContext> context =
    105       BuildModule(SPV_ENV_UNIVERSAL_1_2, nullptr, text,
    106                   SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
    107   EXPECT_NE(nullptr, context);
    108 
    109   DominatorAnalysis* analysis =
    110       context->GetDominatorAnalysis(&*context->module()->begin());
    111 
    112   EXPECT_EQ(
    113       GetBlock(3u, context),
    114       analysis->CommonDominator(GetBlock(7u, context), GetBlock(8u, context)));
    115   EXPECT_EQ(
    116       GetBlock(3u, context),
    117       analysis->CommonDominator(GetBlock(7u, context), GetBlock(9u, context)));
    118 }
    119 
    120 TEST(CommonDominatorsTest, LoopContinueAndMerge) {
    121   std::unique_ptr<IRContext> context =
    122       BuildModule(SPV_ENV_UNIVERSAL_1_2, nullptr, text,
    123                   SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
    124   EXPECT_NE(nullptr, context);
    125 
    126   DominatorAnalysis* analysis =
    127       context->GetDominatorAnalysis(&*context->module()->begin());
    128 
    129   EXPECT_EQ(
    130       GetBlock(5u, context),
    131       analysis->CommonDominator(GetBlock(3u, context), GetBlock(4u, context)));
    132 }
    133 
    134 TEST(CommonDominatorsTest, NoCommonDominator) {
    135   std::unique_ptr<IRContext> context =
    136       BuildModule(SPV_ENV_UNIVERSAL_1_2, nullptr, text,
    137                   SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
    138   EXPECT_NE(nullptr, context);
    139 
    140   DominatorAnalysis* analysis =
    141       context->GetDominatorAnalysis(&*context->module()->begin());
    142 
    143   EXPECT_EQ(nullptr, analysis->CommonDominator(GetBlock(10u, context),
    144                                                GetBlock(11u, context)));
    145   EXPECT_EQ(nullptr, analysis->CommonDominator(GetBlock(11u, context),
    146                                                GetBlock(6u, context)));
    147 }
    148 
    149 }  // namespace
    150 }  // namespace opt
    151 }  // namespace spvtools
    152