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
17 #include "gtest/gtest.h"
18 #include "source/opt/build_module.h"
19 #include "source/opt/ir_context.h"
20
21 namespace spvtools {
22 namespace opt {
23 namespace {
24
25 using CommonDominatorsTest = ::testing::Test;
26
27 const std::string text = R"(
28 OpCapability Shader
29 OpMemoryModel Logical GLSL450
30 OpEntryPoint Fragment %func "func"
31 %void = OpTypeVoid
32 %bool = OpTypeBool
33 %true = OpConstantTrue %bool
34 %functy = OpTypeFunction %void
35 %func = OpFunction %void None %functy
36 %1 = OpLabel
37 OpBranch %2
38 %2 = OpLabel
39 OpLoopMerge %3 %4 None
40 OpBranch %5
41 %5 = OpLabel
42 OpBranchConditional %true %3 %4
43 %4 = OpLabel
44 OpBranch %2
45 %3 = OpLabel
46 OpSelectionMerge %6 None
47 OpBranchConditional %true %7 %8
48 %7 = OpLabel
49 OpBranch %6
50 %8 = OpLabel
51 OpBranch %9
52 %9 = OpLabel
53 OpBranch %6
54 %6 = OpLabel
55 OpBranch %10
56 %11 = OpLabel
57 OpBranch %10
58 %10 = OpLabel
59 OpReturn
60 OpFunctionEnd
61 )";
62
GetBlock(uint32_t id, std::unique_ptr<IRContext>& context)63 BasicBlock* GetBlock(uint32_t id, std::unique_ptr<IRContext>& context) {
64 return context->get_instr_block(context->get_def_use_mgr()->GetDef(id));
65 }
66
TEST(CommonDominatorsTest, SameBlock)67 TEST(CommonDominatorsTest, SameBlock) {
68 std::unique_ptr<IRContext> context =
69 BuildModule(SPV_ENV_UNIVERSAL_1_2, nullptr, text,
70 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
71 EXPECT_NE(nullptr, context);
72
73 DominatorAnalysis* analysis =
74 context->GetDominatorAnalysis(&*context->module()->begin());
75
76 for (auto& block : *context->module()->begin()) {
77 EXPECT_EQ(&block, analysis->CommonDominator(&block, &block));
78 }
79 }
80
TEST(CommonDominatorsTest, ParentAndChild)81 TEST(CommonDominatorsTest, ParentAndChild) {
82 std::unique_ptr<IRContext> context =
83 BuildModule(SPV_ENV_UNIVERSAL_1_2, nullptr, text,
84 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
85 EXPECT_NE(nullptr, context);
86
87 DominatorAnalysis* analysis =
88 context->GetDominatorAnalysis(&*context->module()->begin());
89
90 EXPECT_EQ(
91 GetBlock(1u, context),
92 analysis->CommonDominator(GetBlock(1u, context), GetBlock(2u, context)));
93 EXPECT_EQ(
94 GetBlock(2u, context),
95 analysis->CommonDominator(GetBlock(2u, context), GetBlock(5u, context)));
96 EXPECT_EQ(
97 GetBlock(1u, context),
98 analysis->CommonDominator(GetBlock(1u, context), GetBlock(5u, context)));
99 }
100
TEST(CommonDominatorsTest, BranchSplit)101 TEST(CommonDominatorsTest, BranchSplit) {
102 std::unique_ptr<IRContext> context =
103 BuildModule(SPV_ENV_UNIVERSAL_1_2, nullptr, text,
104 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
105 EXPECT_NE(nullptr, context);
106
107 DominatorAnalysis* analysis =
108 context->GetDominatorAnalysis(&*context->module()->begin());
109
110 EXPECT_EQ(
111 GetBlock(3u, context),
112 analysis->CommonDominator(GetBlock(7u, context), GetBlock(8u, context)));
113 EXPECT_EQ(
114 GetBlock(3u, context),
115 analysis->CommonDominator(GetBlock(7u, context), GetBlock(9u, context)));
116 }
117
TEST(CommonDominatorsTest, LoopContinueAndMerge)118 TEST(CommonDominatorsTest, LoopContinueAndMerge) {
119 std::unique_ptr<IRContext> context =
120 BuildModule(SPV_ENV_UNIVERSAL_1_2, nullptr, text,
121 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
122 EXPECT_NE(nullptr, context);
123
124 DominatorAnalysis* analysis =
125 context->GetDominatorAnalysis(&*context->module()->begin());
126
127 EXPECT_EQ(
128 GetBlock(5u, context),
129 analysis->CommonDominator(GetBlock(3u, context), GetBlock(4u, context)));
130 }
131
TEST(CommonDominatorsTest, NoCommonDominator)132 TEST(CommonDominatorsTest, NoCommonDominator) {
133 std::unique_ptr<IRContext> context =
134 BuildModule(SPV_ENV_UNIVERSAL_1_2, nullptr, text,
135 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
136 EXPECT_NE(nullptr, context);
137
138 DominatorAnalysis* analysis =
139 context->GetDominatorAnalysis(&*context->module()->begin());
140
141 EXPECT_EQ(nullptr, analysis->CommonDominator(GetBlock(10u, context),
142 GetBlock(11u, context)));
143 EXPECT_EQ(nullptr, analysis->CommonDominator(GetBlock(11u, context),
144 GetBlock(6u, context)));
145 }
146
147 } // namespace
148 } // namespace opt
149 } // namespace spvtools
150