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 <vector>
17
18 #include "effcee/effcee.h"
19 #include "gmock/gmock.h"
20 #include "source/opt/build_module.h"
21 #include "source/opt/loop_descriptor.h"
22 #include "source/opt/loop_utils.h"
23 #include "test/opt/assembly_builder.h"
24 #include "test/opt/function_utils.h"
25
26 namespace spvtools {
27 namespace opt {
28 namespace {
29
Validate(const std::vector<uint32_t> & bin)30 bool Validate(const std::vector<uint32_t>& bin) {
31 spv_target_env target_env = SPV_ENV_UNIVERSAL_1_2;
32 spv_context spvContext = spvContextCreate(target_env);
33 spv_diagnostic diagnostic = nullptr;
34 spv_const_binary_t binary = {bin.data(), bin.size()};
35 spv_result_t error = spvValidate(spvContext, &binary, &diagnostic);
36 if (error != 0) spvDiagnosticPrint(diagnostic);
37 spvDiagnosticDestroy(diagnostic);
38 spvContextDestroy(spvContext);
39 return error == 0;
40 }
41
Match(const std::string & original,IRContext * context,bool do_validation=true)42 void Match(const std::string& original, IRContext* context,
43 bool do_validation = true) {
44 std::vector<uint32_t> bin;
45 context->module()->ToBinary(&bin, true);
46 if (do_validation) {
47 EXPECT_TRUE(Validate(bin));
48 }
49 std::string assembly;
50 SpirvTools tools(SPV_ENV_UNIVERSAL_1_2);
51 EXPECT_TRUE(
52 tools.Disassemble(bin, &assembly, SPV_BINARY_TO_TEXT_OPTION_NO_HEADER))
53 << "Disassembling failed for shader:\n"
54 << assembly << std::endl;
55 auto match_result = effcee::Match(assembly, original);
56 EXPECT_EQ(effcee::Result::Status::Ok, match_result.status())
57 << match_result.message() << "\nChecking result:\n"
58 << assembly;
59 }
60
61 using LCSSATest = ::testing::Test;
62
63 /*
64 Generated from the following GLSL + --eliminate-local-multi-store
65
66 #version 330 core
67 layout(location = 0) out vec4 c;
68 void main() {
69 int i = 0;
70 for (; i < 10; i++) {
71 }
72 if (i != 0) {
73 i = 1;
74 }
75 }
76 */
TEST_F(LCSSATest,SimpleLCSSA)77 TEST_F(LCSSATest, SimpleLCSSA) {
78 const std::string text = R"(
79 ; CHECK: OpLoopMerge [[merge:%\w+]] %19 None
80 ; CHECK: [[merge]] = OpLabel
81 ; CHECK-NEXT: [[phi:%\w+]] = OpPhi {{%\w+}} %30 %20
82 ; CHECK-NEXT: %27 = OpINotEqual {{%\w+}} [[phi]] %9
83 OpCapability Shader
84 %1 = OpExtInstImport "GLSL.std.450"
85 OpMemoryModel Logical GLSL450
86 OpEntryPoint Fragment %2 "main" %3
87 OpExecutionMode %2 OriginUpperLeft
88 OpSource GLSL 330
89 OpName %2 "main"
90 OpName %3 "c"
91 OpDecorate %3 Location 0
92 %5 = OpTypeVoid
93 %6 = OpTypeFunction %5
94 %7 = OpTypeInt 32 1
95 %8 = OpTypePointer Function %7
96 %9 = OpConstant %7 0
97 %10 = OpConstant %7 10
98 %11 = OpTypeBool
99 %12 = OpConstant %7 1
100 %13 = OpTypeFloat 32
101 %14 = OpTypeVector %13 4
102 %15 = OpTypePointer Output %14
103 %3 = OpVariable %15 Output
104 %2 = OpFunction %5 None %6
105 %16 = OpLabel
106 OpBranch %17
107 %17 = OpLabel
108 %30 = OpPhi %7 %9 %16 %25 %19
109 OpLoopMerge %18 %19 None
110 OpBranch %20
111 %20 = OpLabel
112 %22 = OpSLessThan %11 %30 %10
113 OpBranchConditional %22 %23 %18
114 %23 = OpLabel
115 OpBranch %19
116 %19 = OpLabel
117 %25 = OpIAdd %7 %30 %12
118 OpBranch %17
119 %18 = OpLabel
120 %27 = OpINotEqual %11 %30 %9
121 OpSelectionMerge %28 None
122 OpBranchConditional %27 %29 %28
123 %29 = OpLabel
124 OpBranch %28
125 %28 = OpLabel
126 %31 = OpPhi %7 %30 %18 %12 %29
127 OpReturn
128 OpFunctionEnd
129 )";
130 std::unique_ptr<IRContext> context =
131 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
132 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
133 Module* module = context->module();
134 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
135 << text << std::endl;
136 const Function* f = spvtest::GetFunction(module, 2);
137 LoopDescriptor ld{context.get(), f};
138
139 Loop* loop = ld[17];
140 EXPECT_FALSE(loop->IsLCSSA());
141 LoopUtils Util(context.get(), loop);
142 Util.MakeLoopClosedSSA();
143 EXPECT_TRUE(loop->IsLCSSA());
144 Match(text, context.get());
145 }
146
147 /*
148 Generated from the following GLSL + --eliminate-local-multi-store
149
150 #version 330 core
151 layout(location = 0) out vec4 c;
152 void main() {
153 int i = 0;
154 for (; i < 10; i++) {
155 }
156 if (i != 0) {
157 i = 1;
158 }
159 }
160 */
161 // Same test as above, but should reuse an existing phi.
TEST_F(LCSSATest,PhiReuseLCSSA)162 TEST_F(LCSSATest, PhiReuseLCSSA) {
163 const std::string text = R"(
164 ; CHECK: OpLoopMerge [[merge:%\w+]] %19 None
165 ; CHECK: [[merge]] = OpLabel
166 ; CHECK-NEXT: [[phi:%\w+]] = OpPhi {{%\w+}} %30 %20
167 ; CHECK-NEXT: %27 = OpINotEqual {{%\w+}} [[phi]] %9
168 OpCapability Shader
169 %1 = OpExtInstImport "GLSL.std.450"
170 OpMemoryModel Logical GLSL450
171 OpEntryPoint Fragment %2 "main" %3
172 OpExecutionMode %2 OriginUpperLeft
173 OpSource GLSL 330
174 OpName %2 "main"
175 OpName %3 "c"
176 OpDecorate %3 Location 0
177 %5 = OpTypeVoid
178 %6 = OpTypeFunction %5
179 %7 = OpTypeInt 32 1
180 %8 = OpTypePointer Function %7
181 %9 = OpConstant %7 0
182 %10 = OpConstant %7 10
183 %11 = OpTypeBool
184 %12 = OpConstant %7 1
185 %13 = OpTypeFloat 32
186 %14 = OpTypeVector %13 4
187 %15 = OpTypePointer Output %14
188 %3 = OpVariable %15 Output
189 %2 = OpFunction %5 None %6
190 %16 = OpLabel
191 OpBranch %17
192 %17 = OpLabel
193 %30 = OpPhi %7 %9 %16 %25 %19
194 OpLoopMerge %18 %19 None
195 OpBranch %20
196 %20 = OpLabel
197 %22 = OpSLessThan %11 %30 %10
198 OpBranchConditional %22 %23 %18
199 %23 = OpLabel
200 OpBranch %19
201 %19 = OpLabel
202 %25 = OpIAdd %7 %30 %12
203 OpBranch %17
204 %18 = OpLabel
205 %32 = OpPhi %7 %30 %20
206 %27 = OpINotEqual %11 %30 %9
207 OpSelectionMerge %28 None
208 OpBranchConditional %27 %29 %28
209 %29 = OpLabel
210 OpBranch %28
211 %28 = OpLabel
212 %31 = OpPhi %7 %30 %18 %12 %29
213 OpReturn
214 OpFunctionEnd
215 )";
216 std::unique_ptr<IRContext> context =
217 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
218 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
219 Module* module = context->module();
220 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
221 << text << std::endl;
222 const Function* f = spvtest::GetFunction(module, 2);
223 LoopDescriptor ld{context.get(), f};
224
225 Loop* loop = ld[17];
226 EXPECT_FALSE(loop->IsLCSSA());
227 LoopUtils Util(context.get(), loop);
228 Util.MakeLoopClosedSSA();
229 EXPECT_TRUE(loop->IsLCSSA());
230 Match(text, context.get());
231 }
232
233 /*
234 Generated from the following GLSL + --eliminate-local-multi-store
235
236 #version 330 core
237 layout(location = 0) out vec4 c;
238 void main() {
239 int i = 0;
240 int j = 0;
241 for (; i < 10; i++) {}
242 for (; j < 10; j++) {}
243 if (j != 0) {
244 i = 1;
245 }
246 }
247 */
TEST_F(LCSSATest,DualLoopLCSSA)248 TEST_F(LCSSATest, DualLoopLCSSA) {
249 const std::string text = R"(
250 ; CHECK: %20 = OpLabel
251 ; CHECK-NEXT: [[phi:%\w+]] = OpPhi %6 %17 %21
252 ; CHECK: %33 = OpLabel
253 ; CHECK-NEXT: {{%\w+}} = OpPhi {{%\w+}} [[phi]] %28 %11 %34
254 OpCapability Shader
255 %1 = OpExtInstImport "GLSL.std.450"
256 OpMemoryModel Logical GLSL450
257 OpEntryPoint Fragment %2 "main" %3
258 OpExecutionMode %2 OriginUpperLeft
259 OpSource GLSL 330
260 OpName %2 "main"
261 OpName %3 "c"
262 OpDecorate %3 Location 0
263 %4 = OpTypeVoid
264 %5 = OpTypeFunction %4
265 %6 = OpTypeInt 32 1
266 %7 = OpTypePointer Function %6
267 %8 = OpConstant %6 0
268 %9 = OpConstant %6 10
269 %10 = OpTypeBool
270 %11 = OpConstant %6 1
271 %12 = OpTypeFloat 32
272 %13 = OpTypeVector %12 4
273 %14 = OpTypePointer Output %13
274 %3 = OpVariable %14 Output
275 %2 = OpFunction %4 None %5
276 %15 = OpLabel
277 OpBranch %16
278 %16 = OpLabel
279 %17 = OpPhi %6 %8 %15 %18 %19
280 OpLoopMerge %20 %19 None
281 OpBranch %21
282 %21 = OpLabel
283 %22 = OpSLessThan %10 %17 %9
284 OpBranchConditional %22 %23 %20
285 %23 = OpLabel
286 OpBranch %19
287 %19 = OpLabel
288 %18 = OpIAdd %6 %17 %11
289 OpBranch %16
290 %20 = OpLabel
291 OpBranch %24
292 %24 = OpLabel
293 %25 = OpPhi %6 %8 %20 %26 %27
294 OpLoopMerge %28 %27 None
295 OpBranch %29
296 %29 = OpLabel
297 %30 = OpSLessThan %10 %25 %9
298 OpBranchConditional %30 %31 %28
299 %31 = OpLabel
300 OpBranch %27
301 %27 = OpLabel
302 %26 = OpIAdd %6 %25 %11
303 OpBranch %24
304 %28 = OpLabel
305 %32 = OpINotEqual %10 %25 %8
306 OpSelectionMerge %33 None
307 OpBranchConditional %32 %34 %33
308 %34 = OpLabel
309 OpBranch %33
310 %33 = OpLabel
311 %35 = OpPhi %6 %17 %28 %11 %34
312 OpReturn
313 OpFunctionEnd
314 )";
315 std::unique_ptr<IRContext> context =
316 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
317 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
318 Module* module = context->module();
319 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
320 << text << std::endl;
321 const Function* f = spvtest::GetFunction(module, 2);
322 LoopDescriptor ld{context.get(), f};
323
324 Loop* loop = ld[16];
325 EXPECT_FALSE(loop->IsLCSSA());
326 LoopUtils Util(context.get(), loop);
327 Util.MakeLoopClosedSSA();
328 EXPECT_TRUE(loop->IsLCSSA());
329 Match(text, context.get());
330 }
331
332 /*
333 Generated from the following GLSL + --eliminate-local-multi-store
334
335 #version 330 core
336 layout(location = 0) out vec4 c;
337 void main() {
338 int i = 0;
339 if (i != 0) {
340 for (; i < 10; i++) {}
341 }
342 if (i != 0) {
343 i = 1;
344 }
345 }
346 */
TEST_F(LCSSATest,PhiUserLCSSA)347 TEST_F(LCSSATest, PhiUserLCSSA) {
348 const std::string text = R"(
349 ; CHECK: OpLoopMerge [[merge:%\w+]] %22 None
350 ; CHECK: [[merge]] = OpLabel
351 ; CHECK-NEXT: [[phi:%\w+]] = OpPhi {{%\w+}} %20 %24
352 ; CHECK: %17 = OpLabel
353 ; CHECK-NEXT: {{%\w+}} = OpPhi {{%\w+}} %8 %15 [[phi]] %23
354 OpCapability Shader
355 %1 = OpExtInstImport "GLSL.std.450"
356 OpMemoryModel Logical GLSL450
357 OpEntryPoint Fragment %2 "main" %3
358 OpExecutionMode %2 OriginUpperLeft
359 OpSource GLSL 330
360 OpName %2 "main"
361 OpName %3 "c"
362 OpDecorate %3 Location 0
363 %4 = OpTypeVoid
364 %5 = OpTypeFunction %4
365 %6 = OpTypeInt 32 1
366 %7 = OpTypePointer Function %6
367 %8 = OpConstant %6 0
368 %9 = OpTypeBool
369 %10 = OpConstant %6 10
370 %11 = OpConstant %6 1
371 %12 = OpTypeFloat 32
372 %13 = OpTypeVector %12 4
373 %14 = OpTypePointer Output %13
374 %3 = OpVariable %14 Output
375 %2 = OpFunction %4 None %5
376 %15 = OpLabel
377 %16 = OpINotEqual %9 %8 %8
378 OpSelectionMerge %17 None
379 OpBranchConditional %16 %18 %17
380 %18 = OpLabel
381 OpBranch %19
382 %19 = OpLabel
383 %20 = OpPhi %6 %8 %18 %21 %22
384 OpLoopMerge %23 %22 None
385 OpBranch %24
386 %24 = OpLabel
387 %25 = OpSLessThan %9 %20 %10
388 OpBranchConditional %25 %26 %23
389 %26 = OpLabel
390 OpBranch %22
391 %22 = OpLabel
392 %21 = OpIAdd %6 %20 %11
393 OpBranch %19
394 %23 = OpLabel
395 OpBranch %17
396 %17 = OpLabel
397 %27 = OpPhi %6 %8 %15 %20 %23
398 %28 = OpINotEqual %9 %27 %8
399 OpSelectionMerge %29 None
400 OpBranchConditional %28 %30 %29
401 %30 = OpLabel
402 OpBranch %29
403 %29 = OpLabel
404 %31 = OpPhi %6 %27 %17 %11 %30
405 OpReturn
406 OpFunctionEnd
407 )";
408 std::unique_ptr<IRContext> context =
409 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
410 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
411 Module* module = context->module();
412 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
413 << text << std::endl;
414 const Function* f = spvtest::GetFunction(module, 2);
415 LoopDescriptor ld{context.get(), f};
416
417 Loop* loop = ld[19];
418 EXPECT_FALSE(loop->IsLCSSA());
419 LoopUtils Util(context.get(), loop);
420 Util.MakeLoopClosedSSA();
421 EXPECT_TRUE(loop->IsLCSSA());
422 Match(text, context.get());
423 }
424
425 /*
426 Generated from the following GLSL + --eliminate-local-multi-store
427
428 #version 330 core
429 void main() {
430 int i = 0;
431 if (i != 0) {
432 for (; i < 10; i++) {
433 if (i > 5) break;
434 }
435 }
436 if (i != 0) {
437 i = 1;
438 }
439 }
440 */
TEST_F(LCSSATest,LCSSAWithBreak)441 TEST_F(LCSSATest, LCSSAWithBreak) {
442 const std::string text = R"(
443 ; CHECK: OpLoopMerge [[merge:%\w+]] %19 None
444 ; CHECK: [[merge]] = OpLabel
445 ; CHECK-NEXT: [[phi:%\w+]] = OpPhi {{%\w+}} %17 %21 %17 %26
446 ; CHECK: %14 = OpLabel
447 ; CHECK-NEXT: {{%\w+}} = OpPhi {{%\w+}} %7 %12 [[phi]] [[merge]]
448 OpCapability Shader
449 %1 = OpExtInstImport "GLSL.std.450"
450 OpMemoryModel Logical GLSL450
451 OpEntryPoint Fragment %2 "main"
452 OpExecutionMode %2 OriginUpperLeft
453 OpSource GLSL 330
454 OpName %2 "main"
455 %3 = OpTypeVoid
456 %4 = OpTypeFunction %3
457 %5 = OpTypeInt 32 1
458 %6 = OpTypePointer Function %5
459 %7 = OpConstant %5 0
460 %8 = OpTypeBool
461 %9 = OpConstant %5 10
462 %10 = OpConstant %5 5
463 %11 = OpConstant %5 1
464 %2 = OpFunction %3 None %4
465 %12 = OpLabel
466 %13 = OpINotEqual %8 %7 %7
467 OpSelectionMerge %14 None
468 OpBranchConditional %13 %15 %14
469 %15 = OpLabel
470 OpBranch %16
471 %16 = OpLabel
472 %17 = OpPhi %5 %7 %15 %18 %19
473 OpLoopMerge %20 %19 None
474 OpBranch %21
475 %21 = OpLabel
476 %22 = OpSLessThan %8 %17 %9
477 OpBranchConditional %22 %23 %20
478 %23 = OpLabel
479 %24 = OpSGreaterThan %8 %17 %10
480 OpSelectionMerge %25 None
481 OpBranchConditional %24 %26 %25
482 %26 = OpLabel
483 OpBranch %20
484 %25 = OpLabel
485 OpBranch %19
486 %19 = OpLabel
487 %18 = OpIAdd %5 %17 %11
488 OpBranch %16
489 %20 = OpLabel
490 OpBranch %14
491 %14 = OpLabel
492 %27 = OpPhi %5 %7 %12 %17 %20
493 %28 = OpINotEqual %8 %27 %7
494 OpSelectionMerge %29 None
495 OpBranchConditional %28 %30 %29
496 %30 = OpLabel
497 OpBranch %29
498 %29 = OpLabel
499 %31 = OpPhi %5 %27 %14 %11 %30
500 OpReturn
501 OpFunctionEnd
502 )";
503 std::unique_ptr<IRContext> context =
504 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
505 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
506 Module* module = context->module();
507 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
508 << text << std::endl;
509 const Function* f = spvtest::GetFunction(module, 2);
510 LoopDescriptor ld{context.get(), f};
511
512 Loop* loop = ld[19];
513 EXPECT_FALSE(loop->IsLCSSA());
514 LoopUtils Util(context.get(), loop);
515 Util.MakeLoopClosedSSA();
516 EXPECT_TRUE(loop->IsLCSSA());
517 Match(text, context.get());
518 }
519
520 /*
521 Generated from the following GLSL + --eliminate-local-multi-store
522
523 #version 330 core
524 void main() {
525 int i = 0;
526 for (; i < 10; i++) {}
527 for (int j = i; j < 10;) { j = i + j; }
528 }
529 */
TEST_F(LCSSATest,LCSSAUseInNonEligiblePhi)530 TEST_F(LCSSATest, LCSSAUseInNonEligiblePhi) {
531 const std::string text = R"(
532 ; CHECK: %12 = OpLabel
533 ; CHECK-NEXT: [[def_to_close:%\w+]] = OpPhi {{%\w+}} {{%\w+}} {{%\w+}} {{%\w+}} [[continue:%\w+]]
534 ; CHECK-NEXT: OpLoopMerge [[merge:%\w+]] [[continue]] None
535 ; CHECK: [[merge]] = OpLabel
536 ; CHECK-NEXT: [[closing_phi:%\w+]] = OpPhi {{%\w+}} [[def_to_close]] %17
537 ; CHECK: %16 = OpLabel
538 ; CHECK-NEXT: [[use_in_phi:%\w+]] = OpPhi {{%\w+}} %21 %22 [[closing_phi]] [[merge]]
539 ; CHECK: OpIAdd {{%\w+}} [[closing_phi]] [[use_in_phi]]
540 OpCapability Shader
541 %1 = OpExtInstImport "GLSL.std.450"
542 OpMemoryModel Logical GLSL450
543 OpEntryPoint Fragment %2 "main"
544 OpExecutionMode %2 OriginUpperLeft
545 OpSource GLSL 330
546 OpName %2 "main"
547 %3 = OpTypeVoid
548 %4 = OpTypeFunction %3
549 %5 = OpTypeInt 32 1
550 %6 = OpTypePointer Function %5
551 %7 = OpConstant %5 0
552 %8 = OpConstant %5 10
553 %9 = OpTypeBool
554 %10 = OpConstant %5 1
555 %2 = OpFunction %3 None %4
556 %11 = OpLabel
557 OpBranch %12
558 %12 = OpLabel
559 %13 = OpPhi %5 %7 %11 %14 %15
560 OpLoopMerge %16 %15 None
561 OpBranch %17
562 %17 = OpLabel
563 %18 = OpSLessThan %9 %13 %8
564 OpBranchConditional %18 %19 %16
565 %19 = OpLabel
566 OpBranch %15
567 %15 = OpLabel
568 %14 = OpIAdd %5 %13 %10
569 OpBranch %12
570 %16 = OpLabel
571 %20 = OpPhi %5 %13 %17 %21 %22
572 OpLoopMerge %23 %22 None
573 OpBranch %24
574 %24 = OpLabel
575 %25 = OpSLessThan %9 %20 %8
576 OpBranchConditional %25 %26 %23
577 %26 = OpLabel
578 %21 = OpIAdd %5 %13 %20
579 OpBranch %22
580 %22 = OpLabel
581 OpBranch %16
582 %23 = OpLabel
583 OpReturn
584 OpFunctionEnd
585 )";
586 std::unique_ptr<IRContext> context =
587 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
588 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
589 Module* module = context->module();
590 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
591 << text << std::endl;
592 const Function* f = spvtest::GetFunction(module, 2);
593 LoopDescriptor ld{context.get(), f};
594
595 Loop* loop = ld[12];
596 EXPECT_FALSE(loop->IsLCSSA());
597 LoopUtils Util(context.get(), loop);
598 Util.MakeLoopClosedSSA();
599 EXPECT_TRUE(loop->IsLCSSA());
600 Match(text, context.get());
601 }
602
603 } // namespace
604 } // namespace opt
605 } // namespace spvtools
606