1 // Copyright (c) 2017 Google Inc.
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 #include <vector>
18
19 #include "gmock/gmock.h"
20 #include "source/opt/dominator_analysis.h"
21 #include "source/opt/pass.h"
22 #include "test/opt/assembly_builder.h"
23 #include "test/opt/function_utils.h"
24 #include "test/opt/pass_fixture.h"
25 #include "test/opt/pass_utils.h"
26
27 namespace spvtools {
28 namespace opt {
29 namespace {
30
31 using ::testing::UnorderedElementsAre;
32 using PassClassTest = PassTest<::testing::Test>;
33
34 /*
35 Generated from the following GLSL
36 #version 440 core
37 layout(location = 0) out vec4 c;
38 layout(location = 1)in vec4 in_val;
39 void main(){
40 if ( in_val.x < 10) {
41 int z = 0;
42 int i = 0;
43 for (i = 0; i < in_val.y; ++i) {
44 z += i;
45 }
46 c = vec4(i,i,i,i);
47 } else {
48 c = vec4(1,1,1,1);
49 }
50 }
51 */
TEST_F(PassClassTest,BasicVisitFromEntryPoint)52 TEST_F(PassClassTest, BasicVisitFromEntryPoint) {
53 const std::string text = R"(
54 OpCapability Shader
55 %1 = OpExtInstImport "GLSL.std.450"
56 OpMemoryModel Logical GLSL450
57 OpEntryPoint Fragment %4 "main" %9 %43
58 OpExecutionMode %4 OriginUpperLeft
59 OpSource GLSL 440
60 OpName %4 "main"
61 OpName %9 "in_val"
62 OpName %22 "z"
63 OpName %24 "i"
64 OpName %43 "c"
65 OpDecorate %9 Location 1
66 OpDecorate %43 Location 0
67 %2 = OpTypeVoid
68 %3 = OpTypeFunction %2
69 %6 = OpTypeFloat 32
70 %7 = OpTypeVector %6 4
71 %8 = OpTypePointer Input %7
72 %9 = OpVariable %8 Input
73 %10 = OpTypeInt 32 0
74 %11 = OpConstant %10 0
75 %12 = OpTypePointer Input %6
76 %15 = OpConstant %6 10
77 %16 = OpTypeBool
78 %20 = OpTypeInt 32 1
79 %21 = OpTypePointer Function %20
80 %23 = OpConstant %20 0
81 %32 = OpConstant %10 1
82 %40 = OpConstant %20 1
83 %42 = OpTypePointer Output %7
84 %43 = OpVariable %42 Output
85 %54 = OpConstant %6 1
86 %55 = OpConstantComposite %7 %54 %54 %54 %54
87 %4 = OpFunction %2 None %3
88 %5 = OpLabel
89 %22 = OpVariable %21 Function
90 %24 = OpVariable %21 Function
91 %13 = OpAccessChain %12 %9 %11
92 %14 = OpLoad %6 %13
93 %17 = OpFOrdLessThan %16 %14 %15
94 OpSelectionMerge %19 None
95 OpBranchConditional %17 %18 %53
96 %18 = OpLabel
97 OpStore %22 %23
98 OpStore %24 %23
99 OpStore %24 %23
100 OpBranch %25
101 %25 = OpLabel
102 OpLoopMerge %27 %28 None
103 OpBranch %29
104 %29 = OpLabel
105 %30 = OpLoad %20 %24
106 %31 = OpConvertSToF %6 %30
107 %33 = OpAccessChain %12 %9 %32
108 %34 = OpLoad %6 %33
109 %35 = OpFOrdLessThan %16 %31 %34
110 OpBranchConditional %35 %26 %27
111 %26 = OpLabel
112 %36 = OpLoad %20 %24
113 %37 = OpLoad %20 %22
114 %38 = OpIAdd %20 %37 %36
115 OpStore %22 %38
116 OpBranch %28
117 %28 = OpLabel
118 %39 = OpLoad %20 %24
119 %41 = OpIAdd %20 %39 %40
120 OpStore %24 %41
121 OpBranch %25
122 %27 = OpLabel
123 %44 = OpLoad %20 %24
124 %45 = OpConvertSToF %6 %44
125 %46 = OpLoad %20 %24
126 %47 = OpConvertSToF %6 %46
127 %48 = OpLoad %20 %24
128 %49 = OpConvertSToF %6 %48
129 %50 = OpLoad %20 %24
130 %51 = OpConvertSToF %6 %50
131 %52 = OpCompositeConstruct %7 %45 %47 %49 %51
132 OpStore %43 %52
133 OpBranch %19
134 %53 = OpLabel
135 OpStore %43 %55
136 OpBranch %19
137 %19 = OpLabel
138 OpReturn
139 OpFunctionEnd
140 )";
141 // clang-format on
142 std::unique_ptr<IRContext> context =
143 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
144 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
145 Module* module = context->module();
146 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
147 << text << std::endl;
148
149 const Function* f = spvtest::GetFunction(module, 4);
150 CFG cfg(module);
151 PostDominatorAnalysis* analysis = context->GetPostDominatorAnalysis(f);
152
153 EXPECT_TRUE(analysis->Dominates(19, 18));
154 EXPECT_TRUE(analysis->Dominates(19, 5));
155 EXPECT_TRUE(analysis->Dominates(19, 53));
156 EXPECT_TRUE(analysis->Dominates(19, 19));
157 EXPECT_TRUE(analysis->Dominates(19, 25));
158 EXPECT_TRUE(analysis->Dominates(19, 29));
159 EXPECT_TRUE(analysis->Dominates(19, 27));
160 EXPECT_TRUE(analysis->Dominates(19, 26));
161 EXPECT_TRUE(analysis->Dominates(19, 28));
162
163 EXPECT_TRUE(analysis->Dominates(27, 18));
164 EXPECT_TRUE(analysis->Dominates(27, 25));
165 EXPECT_TRUE(analysis->Dominates(27, 29));
166 EXPECT_TRUE(analysis->Dominates(27, 27));
167 EXPECT_TRUE(analysis->Dominates(27, 26));
168 EXPECT_TRUE(analysis->Dominates(27, 28));
169
170 EXPECT_FALSE(analysis->Dominates(27, 19));
171 EXPECT_FALSE(analysis->Dominates(27, 5));
172 EXPECT_FALSE(analysis->Dominates(27, 53));
173
174 EXPECT_FALSE(analysis->StrictlyDominates(19, 19));
175
176 EXPECT_TRUE(analysis->StrictlyDominates(19, 18));
177 EXPECT_TRUE(analysis->StrictlyDominates(19, 5));
178 EXPECT_TRUE(analysis->StrictlyDominates(19, 53));
179 EXPECT_TRUE(analysis->StrictlyDominates(19, 25));
180 EXPECT_TRUE(analysis->StrictlyDominates(19, 29));
181 EXPECT_TRUE(analysis->StrictlyDominates(19, 27));
182 EXPECT_TRUE(analysis->StrictlyDominates(19, 26));
183 EXPECT_TRUE(analysis->StrictlyDominates(19, 28));
184
185 // These would be expected true for a normal, non post, dominator tree
186 EXPECT_FALSE(analysis->Dominates(5, 18));
187 EXPECT_FALSE(analysis->Dominates(5, 53));
188 EXPECT_FALSE(analysis->Dominates(5, 19));
189 EXPECT_FALSE(analysis->Dominates(5, 25));
190 EXPECT_FALSE(analysis->Dominates(5, 29));
191 EXPECT_FALSE(analysis->Dominates(5, 27));
192 EXPECT_FALSE(analysis->Dominates(5, 26));
193 EXPECT_FALSE(analysis->Dominates(5, 28));
194
195 EXPECT_FALSE(analysis->StrictlyDominates(5, 18));
196 EXPECT_FALSE(analysis->StrictlyDominates(5, 53));
197 EXPECT_FALSE(analysis->StrictlyDominates(5, 19));
198 EXPECT_FALSE(analysis->StrictlyDominates(5, 25));
199 EXPECT_FALSE(analysis->StrictlyDominates(5, 29));
200 EXPECT_FALSE(analysis->StrictlyDominates(5, 27));
201 EXPECT_FALSE(analysis->StrictlyDominates(5, 26));
202 EXPECT_FALSE(analysis->StrictlyDominates(5, 28));
203 }
204
205 } // namespace
206 } // namespace opt
207 } // namespace spvtools
208