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
GetBlock(uint32_t id,std::unique_ptr<IRContext> & context)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
TEST(CommonDominatorsTest,SameBlock)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
TEST(CommonDominatorsTest,ParentAndChild)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
TEST(CommonDominatorsTest,BranchSplit)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
TEST(CommonDominatorsTest,LoopContinueAndMerge)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
TEST(CommonDominatorsTest,NoCommonDominator)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