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