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