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/loop_descriptor.h"
21 #include "source/opt/loop_fusion.h"
22 #include "test/opt/pass_fixture.h"
23
24 namespace spvtools {
25 namespace opt {
26 namespace {
27
28 using FusionLegalTest = PassTest<::testing::Test>;
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 & checks,IRContext * context)42 void Match(const std::string& checks, IRContext* context) {
43 // Silence unused warnings with !defined(SPIRV_EFFCE)
44 (void)checks;
45
46 std::vector<uint32_t> bin;
47 context->module()->ToBinary(&bin, true);
48 EXPECT_TRUE(Validate(bin));
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, checks);
56 EXPECT_EQ(effcee::Result::Status::Ok, match_result.status())
57 << match_result.message() << "\nChecking result:\n"
58 << assembly;
59 }
60
61 /*
62 Generated from the following GLSL + --eliminate-local-multi-store
63
64 #version 440 core
65 void main() {
66 int[10] a;
67 int[10] b;
68 // No dependence, legal
69 for (int i = 0; i < 10; i++) {
70 a[i] = a[i]*2;
71 }
72 for (int i = 0; i < 10; i++) {
73 b[i] = b[i]+2;
74 }
75 }
76
77 */
TEST_F(FusionLegalTest,DifferentArraysInLoops)78 TEST_F(FusionLegalTest, DifferentArraysInLoops) {
79 std::string text = R"(
80 OpCapability Shader
81 %1 = OpExtInstImport "GLSL.std.450"
82 OpMemoryModel Logical GLSL450
83 OpEntryPoint Fragment %4 "main"
84 OpExecutionMode %4 OriginUpperLeft
85 OpSource GLSL 440
86 OpName %4 "main"
87 OpName %8 "i"
88 OpName %23 "a"
89 OpName %34 "i"
90 OpName %42 "b"
91 %2 = OpTypeVoid
92 %3 = OpTypeFunction %2
93 %6 = OpTypeInt 32 1
94 %7 = OpTypePointer Function %6
95 %9 = OpConstant %6 0
96 %16 = OpConstant %6 10
97 %17 = OpTypeBool
98 %19 = OpTypeInt 32 0
99 %20 = OpConstant %19 10
100 %21 = OpTypeArray %6 %20
101 %22 = OpTypePointer Function %21
102 %28 = OpConstant %6 2
103 %32 = OpConstant %6 1
104 %4 = OpFunction %2 None %3
105 %5 = OpLabel
106 %8 = OpVariable %7 Function
107 %23 = OpVariable %22 Function
108 %34 = OpVariable %7 Function
109 %42 = OpVariable %22 Function
110 OpStore %8 %9
111 OpBranch %10
112 %10 = OpLabel
113 %51 = OpPhi %6 %9 %5 %33 %13
114 OpLoopMerge %12 %13 None
115 OpBranch %14
116 %14 = OpLabel
117 %18 = OpSLessThan %17 %51 %16
118 OpBranchConditional %18 %11 %12
119 %11 = OpLabel
120 %26 = OpAccessChain %7 %23 %51
121 %27 = OpLoad %6 %26
122 %29 = OpIMul %6 %27 %28
123 %30 = OpAccessChain %7 %23 %51
124 OpStore %30 %29
125 OpBranch %13
126 %13 = OpLabel
127 %33 = OpIAdd %6 %51 %32
128 OpStore %8 %33
129 OpBranch %10
130 %12 = OpLabel
131 OpStore %34 %9
132 OpBranch %35
133 %35 = OpLabel
134 %52 = OpPhi %6 %9 %12 %50 %38
135 OpLoopMerge %37 %38 None
136 OpBranch %39
137 %39 = OpLabel
138 %41 = OpSLessThan %17 %52 %16
139 OpBranchConditional %41 %36 %37
140 %36 = OpLabel
141 %45 = OpAccessChain %7 %42 %52
142 %46 = OpLoad %6 %45
143 %47 = OpIAdd %6 %46 %28
144 %48 = OpAccessChain %7 %42 %52
145 OpStore %48 %47
146 OpBranch %38
147 %38 = OpLabel
148 %50 = OpIAdd %6 %52 %32
149 OpStore %34 %50
150 OpBranch %35
151 %37 = OpLabel
152 OpReturn
153 OpFunctionEnd
154 )";
155
156 std::unique_ptr<IRContext> context =
157 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
158 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
159 Module* module = context->module();
160 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
161 << text << std::endl;
162 Function& f = *module->begin();
163 LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
164 EXPECT_EQ(ld.NumLoops(), 2u);
165
166 auto loops = ld.GetLoopsInBinaryLayoutOrder();
167
168 LoopFusion fusion(context.get(), loops[0], loops[1]);
169
170 EXPECT_TRUE(fusion.AreCompatible());
171 EXPECT_TRUE(fusion.IsLegal());
172
173 fusion.Fuse();
174
175 std::string checks = R"(
176 CHECK: [[PHI:%\w+]] = OpPhi
177 CHECK-NEXT: OpLoopMerge
178 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
179 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_0]]
180 CHECK: [[STORE_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
181 CHECK-NEXT: OpStore [[STORE_0]]
182 CHECK-NOT: OpPhi
183 CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
184 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_1]]
185 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
186 CHECK-NEXT: OpStore [[STORE_1]]
187 )";
188
189 Match(checks, context.get());
190 auto& ld_final = *context->GetLoopDescriptor(&f);
191 EXPECT_EQ(ld_final.NumLoops(), 1u);
192 }
193
194 /*
195 Generated from the following GLSL + --eliminate-local-multi-store
196
197 #version 440 core
198 void main() {
199 int[10] a;
200 int[10] b;
201 int[10] c;
202 // Only loads to the same array, legal
203 for (int i = 0; i < 10; i++) {
204 b[i] = a[i]*2;
205 }
206 for (int i = 0; i < 10; i++) {
207 c[i] = a[i]+2;
208 }
209 }
210
211 */
TEST_F(FusionLegalTest,OnlyLoadsToSameArray)212 TEST_F(FusionLegalTest, OnlyLoadsToSameArray) {
213 std::string text = R"(
214 OpCapability Shader
215 %1 = OpExtInstImport "GLSL.std.450"
216 OpMemoryModel Logical GLSL450
217 OpEntryPoint Fragment %4 "main"
218 OpExecutionMode %4 OriginUpperLeft
219 OpSource GLSL 440
220 OpName %4 "main"
221 OpName %8 "i"
222 OpName %23 "b"
223 OpName %25 "a"
224 OpName %35 "i"
225 OpName %43 "c"
226 %2 = OpTypeVoid
227 %3 = OpTypeFunction %2
228 %6 = OpTypeInt 32 1
229 %7 = OpTypePointer Function %6
230 %9 = OpConstant %6 0
231 %16 = OpConstant %6 10
232 %17 = OpTypeBool
233 %19 = OpTypeInt 32 0
234 %20 = OpConstant %19 10
235 %21 = OpTypeArray %6 %20
236 %22 = OpTypePointer Function %21
237 %29 = OpConstant %6 2
238 %33 = OpConstant %6 1
239 %4 = OpFunction %2 None %3
240 %5 = OpLabel
241 %8 = OpVariable %7 Function
242 %23 = OpVariable %22 Function
243 %25 = OpVariable %22 Function
244 %35 = OpVariable %7 Function
245 %43 = OpVariable %22 Function
246 OpStore %8 %9
247 OpBranch %10
248 %10 = OpLabel
249 %52 = OpPhi %6 %9 %5 %34 %13
250 OpLoopMerge %12 %13 None
251 OpBranch %14
252 %14 = OpLabel
253 %18 = OpSLessThan %17 %52 %16
254 OpBranchConditional %18 %11 %12
255 %11 = OpLabel
256 %27 = OpAccessChain %7 %25 %52
257 %28 = OpLoad %6 %27
258 %30 = OpIMul %6 %28 %29
259 %31 = OpAccessChain %7 %23 %52
260 OpStore %31 %30
261 OpBranch %13
262 %13 = OpLabel
263 %34 = OpIAdd %6 %52 %33
264 OpStore %8 %34
265 OpBranch %10
266 %12 = OpLabel
267 OpStore %35 %9
268 OpBranch %36
269 %36 = OpLabel
270 %53 = OpPhi %6 %9 %12 %51 %39
271 OpLoopMerge %38 %39 None
272 OpBranch %40
273 %40 = OpLabel
274 %42 = OpSLessThan %17 %53 %16
275 OpBranchConditional %42 %37 %38
276 %37 = OpLabel
277 %46 = OpAccessChain %7 %25 %53
278 %47 = OpLoad %6 %46
279 %48 = OpIAdd %6 %47 %29
280 %49 = OpAccessChain %7 %43 %53
281 OpStore %49 %48
282 OpBranch %39
283 %39 = OpLabel
284 %51 = OpIAdd %6 %53 %33
285 OpStore %35 %51
286 OpBranch %36
287 %38 = OpLabel
288 OpReturn
289 OpFunctionEnd
290 )";
291
292 std::unique_ptr<IRContext> context =
293 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
294 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
295 Module* module = context->module();
296 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
297 << text << std::endl;
298 Function& f = *module->begin();
299 LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
300 EXPECT_EQ(ld.NumLoops(), 2u);
301
302 auto loops = ld.GetLoopsInBinaryLayoutOrder();
303
304 LoopFusion fusion(context.get(), loops[0], loops[1]);
305
306 EXPECT_TRUE(fusion.AreCompatible());
307 EXPECT_TRUE(fusion.IsLegal());
308
309 fusion.Fuse();
310
311 std::string checks = R"(
312 CHECK: [[PHI:%\w+]] = OpPhi
313 CHECK-NEXT: OpLoopMerge
314 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
315 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_0]]
316 CHECK: [[STORE_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
317 CHECK-NEXT: OpStore [[STORE_0]]
318 CHECK-NOT: OpPhi
319 CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
320 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_1]]
321 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
322 CHECK-NEXT: OpStore [[STORE_1]]
323 )";
324
325 Match(checks, context.get());
326 auto& ld_final = *context->GetLoopDescriptor(&f);
327 EXPECT_EQ(ld_final.NumLoops(), 1u);
328 }
329
330 /*
331 Generated from the following GLSL + --eliminate-local-multi-store
332
333 #version 440 core
334 void main() {
335 int[10] a;
336 int[10] b;
337 // No loop-carried dependences, legal
338 for (int i = 0; i < 10; i++) {
339 a[i] = a[i]*2;
340 }
341 for (int i = 0; i < 10; i++) {
342 b[i] = a[i]+2;
343 }
344 }
345
346 */
TEST_F(FusionLegalTest,NoLoopCarriedDependences)347 TEST_F(FusionLegalTest, NoLoopCarriedDependences) {
348 std::string text = R"(
349 OpCapability Shader
350 %1 = OpExtInstImport "GLSL.std.450"
351 OpMemoryModel Logical GLSL450
352 OpEntryPoint Fragment %4 "main"
353 OpExecutionMode %4 OriginUpperLeft
354 OpSource GLSL 440
355 OpName %4 "main"
356 OpName %8 "i"
357 OpName %23 "a"
358 OpName %34 "i"
359 OpName %42 "b"
360 %2 = OpTypeVoid
361 %3 = OpTypeFunction %2
362 %6 = OpTypeInt 32 1
363 %7 = OpTypePointer Function %6
364 %9 = OpConstant %6 0
365 %16 = OpConstant %6 10
366 %17 = OpTypeBool
367 %19 = OpTypeInt 32 0
368 %20 = OpConstant %19 10
369 %21 = OpTypeArray %6 %20
370 %22 = OpTypePointer Function %21
371 %28 = OpConstant %6 2
372 %32 = OpConstant %6 1
373 %4 = OpFunction %2 None %3
374 %5 = OpLabel
375 %8 = OpVariable %7 Function
376 %23 = OpVariable %22 Function
377 %34 = OpVariable %7 Function
378 %42 = OpVariable %22 Function
379 OpStore %8 %9
380 OpBranch %10
381 %10 = OpLabel
382 %51 = OpPhi %6 %9 %5 %33 %13
383 OpLoopMerge %12 %13 None
384 OpBranch %14
385 %14 = OpLabel
386 %18 = OpSLessThan %17 %51 %16
387 OpBranchConditional %18 %11 %12
388 %11 = OpLabel
389 %26 = OpAccessChain %7 %23 %51
390 %27 = OpLoad %6 %26
391 %29 = OpIMul %6 %27 %28
392 %30 = OpAccessChain %7 %23 %51
393 OpStore %30 %29
394 OpBranch %13
395 %13 = OpLabel
396 %33 = OpIAdd %6 %51 %32
397 OpStore %8 %33
398 OpBranch %10
399 %12 = OpLabel
400 OpStore %34 %9
401 OpBranch %35
402 %35 = OpLabel
403 %52 = OpPhi %6 %9 %12 %50 %38
404 OpLoopMerge %37 %38 None
405 OpBranch %39
406 %39 = OpLabel
407 %41 = OpSLessThan %17 %52 %16
408 OpBranchConditional %41 %36 %37
409 %36 = OpLabel
410 %45 = OpAccessChain %7 %23 %52
411 %46 = OpLoad %6 %45
412 %47 = OpIAdd %6 %46 %28
413 %48 = OpAccessChain %7 %42 %52
414 OpStore %48 %47
415 OpBranch %38
416 %38 = OpLabel
417 %50 = OpIAdd %6 %52 %32
418 OpStore %34 %50
419 OpBranch %35
420 %37 = OpLabel
421 OpReturn
422 OpFunctionEnd
423 )";
424
425 std::unique_ptr<IRContext> context =
426 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
427 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
428 Module* module = context->module();
429 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
430 << text << std::endl;
431 Function& f = *module->begin();
432 LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
433 EXPECT_EQ(ld.NumLoops(), 2u);
434
435 auto loops = ld.GetLoopsInBinaryLayoutOrder();
436
437 LoopFusion fusion(context.get(), loops[0], loops[1]);
438
439 EXPECT_TRUE(fusion.AreCompatible());
440 EXPECT_TRUE(fusion.IsLegal());
441
442 fusion.Fuse();
443
444 std::string checks = R"(
445 CHECK: [[PHI:%\w+]] = OpPhi
446 CHECK-NEXT: OpLoopMerge
447 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
448 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_0]]
449 CHECK: [[STORE_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
450 CHECK-NEXT: OpStore [[STORE_0]]
451 CHECK-NOT: OpPhi
452 CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
453 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_1]]
454 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
455 CHECK-NEXT: OpStore [[STORE_1]]
456 )";
457
458 Match(checks, context.get());
459 auto& ld_final = *context->GetLoopDescriptor(&f);
460 EXPECT_EQ(ld_final.NumLoops(), 1u);
461 }
462
463 /*
464 Generated from the following GLSL + --eliminate-local-multi-store
465
466 #version 440 core
467 void main() {
468 int[10] a;
469 int[10] b;
470 int[10] c;
471 // Parallelism inhibiting, but legal.
472 for (int i = 0; i < 10; i++) {
473 a[i] = b[i] + 1;
474 }
475 for (int i = 0; i < 10; i++) {
476 c[i] = a[i] + c[i-1];
477 }
478 }
479
480 */
TEST_F(FusionLegalTest,ExistingLoopCarriedDependence)481 TEST_F(FusionLegalTest, ExistingLoopCarriedDependence) {
482 std::string text = R"(
483 OpCapability Shader
484 %1 = OpExtInstImport "GLSL.std.450"
485 OpMemoryModel Logical GLSL450
486 OpEntryPoint Fragment %4 "main"
487 OpExecutionMode %4 OriginUpperLeft
488 OpSource GLSL 440
489 OpName %4 "main"
490 OpName %8 "i"
491 OpName %23 "a"
492 OpName %25 "b"
493 OpName %34 "i"
494 OpName %42 "c"
495 %2 = OpTypeVoid
496 %3 = OpTypeFunction %2
497 %6 = OpTypeInt 32 1
498 %7 = OpTypePointer Function %6
499 %9 = OpConstant %6 0
500 %16 = OpConstant %6 10
501 %17 = OpTypeBool
502 %19 = OpTypeInt 32 0
503 %20 = OpConstant %19 10
504 %21 = OpTypeArray %6 %20
505 %22 = OpTypePointer Function %21
506 %29 = OpConstant %6 1
507 %4 = OpFunction %2 None %3
508 %5 = OpLabel
509 %8 = OpVariable %7 Function
510 %23 = OpVariable %22 Function
511 %25 = OpVariable %22 Function
512 %34 = OpVariable %7 Function
513 %42 = OpVariable %22 Function
514 OpStore %8 %9
515 OpBranch %10
516 %10 = OpLabel
517 %55 = OpPhi %6 %9 %5 %33 %13
518 OpLoopMerge %12 %13 None
519 OpBranch %14
520 %14 = OpLabel
521 %18 = OpSLessThan %17 %55 %16
522 OpBranchConditional %18 %11 %12
523 %11 = OpLabel
524 %27 = OpAccessChain %7 %25 %55
525 %28 = OpLoad %6 %27
526 %30 = OpIAdd %6 %28 %29
527 %31 = OpAccessChain %7 %23 %55
528 OpStore %31 %30
529 OpBranch %13
530 %13 = OpLabel
531 %33 = OpIAdd %6 %55 %29
532 OpStore %8 %33
533 OpBranch %10
534 %12 = OpLabel
535 OpStore %34 %9
536 OpBranch %35
537 %35 = OpLabel
538 %56 = OpPhi %6 %9 %12 %54 %38
539 OpLoopMerge %37 %38 None
540 OpBranch %39
541 %39 = OpLabel
542 %41 = OpSLessThan %17 %56 %16
543 OpBranchConditional %41 %36 %37
544 %36 = OpLabel
545 %45 = OpAccessChain %7 %23 %56
546 %46 = OpLoad %6 %45
547 %48 = OpISub %6 %56 %29
548 %49 = OpAccessChain %7 %42 %48
549 %50 = OpLoad %6 %49
550 %51 = OpIAdd %6 %46 %50
551 %52 = OpAccessChain %7 %42 %56
552 OpStore %52 %51
553 OpBranch %38
554 %38 = OpLabel
555 %54 = OpIAdd %6 %56 %29
556 OpStore %34 %54
557 OpBranch %35
558 %37 = OpLabel
559 OpReturn
560 OpFunctionEnd
561 )";
562
563 std::unique_ptr<IRContext> context =
564 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
565 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
566 Module* module = context->module();
567 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
568 << text << std::endl;
569 Function& f = *module->begin();
570 LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
571 EXPECT_EQ(ld.NumLoops(), 2u);
572
573 auto loops = ld.GetLoopsInBinaryLayoutOrder();
574
575 LoopFusion fusion(context.get(), loops[0], loops[1]);
576
577 EXPECT_TRUE(fusion.AreCompatible());
578 EXPECT_TRUE(fusion.IsLegal());
579
580 fusion.Fuse();
581
582 std::string checks = R"(
583 CHECK: [[PHI:%\w+]] = OpPhi
584 CHECK-NEXT: OpLoopMerge
585 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
586 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_0]]
587 CHECK: [[STORE_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
588 CHECK-NEXT: OpStore [[STORE_0]]
589 CHECK-NOT: OpPhi
590 CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
591 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_1]]
592 CHECK: [[I_1:%\w+]] = OpISub {{%\w+}} [[PHI]] {{%\w+}}
593 CHECK-NEXT: [[LOAD_2:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[I_1]]
594 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_2]]
595 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
596 CHECK-NEXT: OpStore [[STORE_1]]
597 )";
598
599 Match(checks, context.get());
600 auto& ld_final = *context->GetLoopDescriptor(&f);
601 EXPECT_EQ(ld_final.NumLoops(), 1u);
602 }
603
604 /*
605 Generated from the following GLSL + --eliminate-local-multi-store
606
607 #version 440 core
608 void main() {
609 int[10] a;
610 int[10] b;
611 int[10] c;
612 // Creates a loop-carried dependence, but negative, so legal
613 for (int i = 0; i < 10; i++) {
614 a[i+1] = b[i] + 1;
615 }
616 for (int i = 0; i < 10; i++) {
617 c[i] = a[i] + 2;
618 }
619 }
620
621 */
TEST_F(FusionLegalTest,NegativeDistanceCreatedRAW)622 TEST_F(FusionLegalTest, NegativeDistanceCreatedRAW) {
623 std::string text = R"(
624 OpCapability Shader
625 %1 = OpExtInstImport "GLSL.std.450"
626 OpMemoryModel Logical GLSL450
627 OpEntryPoint Fragment %4 "main"
628 OpExecutionMode %4 OriginUpperLeft
629 OpSource GLSL 440
630 OpName %4 "main"
631 OpName %8 "i"
632 OpName %23 "a"
633 OpName %27 "b"
634 OpName %35 "i"
635 OpName %43 "c"
636 %2 = OpTypeVoid
637 %3 = OpTypeFunction %2
638 %6 = OpTypeInt 32 1
639 %7 = OpTypePointer Function %6
640 %9 = OpConstant %6 0
641 %16 = OpConstant %6 10
642 %17 = OpTypeBool
643 %19 = OpTypeInt 32 0
644 %20 = OpConstant %19 10
645 %21 = OpTypeArray %6 %20
646 %22 = OpTypePointer Function %21
647 %25 = OpConstant %6 1
648 %48 = OpConstant %6 2
649 %4 = OpFunction %2 None %3
650 %5 = OpLabel
651 %8 = OpVariable %7 Function
652 %23 = OpVariable %22 Function
653 %27 = OpVariable %22 Function
654 %35 = OpVariable %7 Function
655 %43 = OpVariable %22 Function
656 OpStore %8 %9
657 OpBranch %10
658 %10 = OpLabel
659 %53 = OpPhi %6 %9 %5 %34 %13
660 OpLoopMerge %12 %13 None
661 OpBranch %14
662 %14 = OpLabel
663 %18 = OpSLessThan %17 %53 %16
664 OpBranchConditional %18 %11 %12
665 %11 = OpLabel
666 %26 = OpIAdd %6 %53 %25
667 %29 = OpAccessChain %7 %27 %53
668 %30 = OpLoad %6 %29
669 %31 = OpIAdd %6 %30 %25
670 %32 = OpAccessChain %7 %23 %26
671 OpStore %32 %31
672 OpBranch %13
673 %13 = OpLabel
674 %34 = OpIAdd %6 %53 %25
675 OpStore %8 %34
676 OpBranch %10
677 %12 = OpLabel
678 OpStore %35 %9
679 OpBranch %36
680 %36 = OpLabel
681 %54 = OpPhi %6 %9 %12 %52 %39
682 OpLoopMerge %38 %39 None
683 OpBranch %40
684 %40 = OpLabel
685 %42 = OpSLessThan %17 %54 %16
686 OpBranchConditional %42 %37 %38
687 %37 = OpLabel
688 %46 = OpAccessChain %7 %23 %54
689 %47 = OpLoad %6 %46
690 %49 = OpIAdd %6 %47 %48
691 %50 = OpAccessChain %7 %43 %54
692 OpStore %50 %49
693 OpBranch %39
694 %39 = OpLabel
695 %52 = OpIAdd %6 %54 %25
696 OpStore %35 %52
697 OpBranch %36
698 %38 = OpLabel
699 OpReturn
700 OpFunctionEnd
701 )";
702
703 std::unique_ptr<IRContext> context =
704 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
705 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
706 Module* module = context->module();
707 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
708 << text << std::endl;
709 Function& f = *module->begin();
710
711 {
712 LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
713 EXPECT_EQ(ld.NumLoops(), 2u);
714
715 auto loops = ld.GetLoopsInBinaryLayoutOrder();
716
717 LoopFusion fusion(context.get(), loops[0], loops[1]);
718
719 EXPECT_TRUE(fusion.AreCompatible());
720 EXPECT_TRUE(fusion.IsLegal());
721
722 fusion.Fuse();
723
724 std::string checks = R"(
725 CHECK: [[PHI:%\w+]] = OpPhi
726 CHECK-NEXT: OpLoopMerge
727 CHECK: [[I_1:%\w+]] = OpIAdd {{%\w+}} [[PHI]] {{%\w+}}
728 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
729 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_0]]
730 CHECK: [[STORE_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[I_1]]
731 CHECK-NEXT: OpStore [[STORE_0]]
732 CHECK-NOT: OpPhi
733 CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
734 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_1]]
735 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
736 CHECK-NEXT: OpStore [[STORE_1]]
737 )";
738
739 Match(checks, context.get());
740 }
741
742 {
743 auto& ld = *context->GetLoopDescriptor(&f);
744 EXPECT_EQ(ld.NumLoops(), 1u);
745 }
746 }
747
748 /*
749 Generated from the following GLSL + --eliminate-local-multi-store
750
751 #version 440 core
752 void main() {
753 int[10] a;
754 int[10] b;
755 int[10] c;
756 // Legal
757 for (int i = 0; i < 10; i++) {
758 a[i+1] = b[i] + 1;
759 }
760 for (int i = 0; i < 10; i++) {
761 c[i] = a[i+1] + 2;
762 }
763 }
764
765 */
TEST_F(FusionLegalTest,NoLoopCarriedDependencesAdjustedIndex)766 TEST_F(FusionLegalTest, NoLoopCarriedDependencesAdjustedIndex) {
767 std::string text = R"(
768 OpCapability Shader
769 %1 = OpExtInstImport "GLSL.std.450"
770 OpMemoryModel Logical GLSL450
771 OpEntryPoint Fragment %4 "main"
772 OpExecutionMode %4 OriginUpperLeft
773 OpSource GLSL 440
774 OpName %4 "main"
775 OpName %8 "i"
776 OpName %23 "a"
777 OpName %27 "b"
778 OpName %35 "i"
779 OpName %43 "c"
780 %2 = OpTypeVoid
781 %3 = OpTypeFunction %2
782 %6 = OpTypeInt 32 1
783 %7 = OpTypePointer Function %6
784 %9 = OpConstant %6 0
785 %16 = OpConstant %6 10
786 %17 = OpTypeBool
787 %19 = OpTypeInt 32 0
788 %20 = OpConstant %19 10
789 %21 = OpTypeArray %6 %20
790 %22 = OpTypePointer Function %21
791 %25 = OpConstant %6 1
792 %49 = OpConstant %6 2
793 %4 = OpFunction %2 None %3
794 %5 = OpLabel
795 %8 = OpVariable %7 Function
796 %23 = OpVariable %22 Function
797 %27 = OpVariable %22 Function
798 %35 = OpVariable %7 Function
799 %43 = OpVariable %22 Function
800 OpStore %8 %9
801 OpBranch %10
802 %10 = OpLabel
803 %54 = OpPhi %6 %9 %5 %34 %13
804 OpLoopMerge %12 %13 None
805 OpBranch %14
806 %14 = OpLabel
807 %18 = OpSLessThan %17 %54 %16
808 OpBranchConditional %18 %11 %12
809 %11 = OpLabel
810 %26 = OpIAdd %6 %54 %25
811 %29 = OpAccessChain %7 %27 %54
812 %30 = OpLoad %6 %29
813 %31 = OpIAdd %6 %30 %25
814 %32 = OpAccessChain %7 %23 %26
815 OpStore %32 %31
816 OpBranch %13
817 %13 = OpLabel
818 %34 = OpIAdd %6 %54 %25
819 OpStore %8 %34
820 OpBranch %10
821 %12 = OpLabel
822 OpStore %35 %9
823 OpBranch %36
824 %36 = OpLabel
825 %55 = OpPhi %6 %9 %12 %53 %39
826 OpLoopMerge %38 %39 None
827 OpBranch %40
828 %40 = OpLabel
829 %42 = OpSLessThan %17 %55 %16
830 OpBranchConditional %42 %37 %38
831 %37 = OpLabel
832 %46 = OpIAdd %6 %55 %25
833 %47 = OpAccessChain %7 %23 %46
834 %48 = OpLoad %6 %47
835 %50 = OpIAdd %6 %48 %49
836 %51 = OpAccessChain %7 %43 %55
837 OpStore %51 %50
838 OpBranch %39
839 %39 = OpLabel
840 %53 = OpIAdd %6 %55 %25
841 OpStore %35 %53
842 OpBranch %36
843 %38 = OpLabel
844 OpReturn
845 OpFunctionEnd
846 )";
847
848 std::unique_ptr<IRContext> context =
849 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
850 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
851 Module* module = context->module();
852 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
853 << text << std::endl;
854 Function& f = *module->begin();
855 LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
856 EXPECT_EQ(ld.NumLoops(), 2u);
857
858 auto loops = ld.GetLoopsInBinaryLayoutOrder();
859
860 LoopFusion fusion(context.get(), loops[0], loops[1]);
861
862 EXPECT_TRUE(fusion.AreCompatible());
863 EXPECT_TRUE(fusion.IsLegal());
864
865 fusion.Fuse();
866
867 std::string checks = R"(
868 CHECK: [[PHI:%\w+]] = OpPhi
869 CHECK-NEXT: OpLoopMerge
870 CHECK: [[I_1:%\w+]] = OpIAdd {{%\w+}} [[PHI]] {{%\w+}}
871 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
872 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_0]]
873 CHECK: [[STORE_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[I_1]]
874 CHECK-NEXT: OpStore [[STORE_0]]
875 CHECK-NOT: OpPhi
876 CHECK: [[I_1:%\w+]] = OpIAdd {{%\w+}} [[PHI]] {{%\w+}}
877 CHECK-NEXT: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[I_1]]
878 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_1]]
879 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
880 CHECK-NEXT: OpStore [[STORE_1]]
881 )";
882
883 Match(checks, context.get());
884 auto& ld_final = *context->GetLoopDescriptor(&f);
885 EXPECT_EQ(ld_final.NumLoops(), 1u);
886 }
887
888 /*
889 Generated from the following GLSL + --eliminate-local-multi-store
890
891 #version 440 core
892 void main() {
893 int[10] a;
894 int[10] b;
895 int[10] c;
896 // Legal, independent locations in |a|, SIV
897 for (int i = 0; i < 10; i++) {
898 a[2*i+1] = b[i] + 1;
899 }
900 for (int i = 0; i < 10; i++) {
901 c[i] = a[2*i] + 2;
902 }
903 }
904
905 */
TEST_F(FusionLegalTest,IndependentSIV)906 TEST_F(FusionLegalTest, IndependentSIV) {
907 std::string text = R"(
908 OpCapability Shader
909 %1 = OpExtInstImport "GLSL.std.450"
910 OpMemoryModel Logical GLSL450
911 OpEntryPoint Fragment %4 "main"
912 OpExecutionMode %4 OriginUpperLeft
913 OpSource GLSL 440
914 OpName %4 "main"
915 OpName %8 "i"
916 OpName %23 "a"
917 OpName %29 "b"
918 OpName %37 "i"
919 OpName %45 "c"
920 %2 = OpTypeVoid
921 %3 = OpTypeFunction %2
922 %6 = OpTypeInt 32 1
923 %7 = OpTypePointer Function %6
924 %9 = OpConstant %6 0
925 %16 = OpConstant %6 10
926 %17 = OpTypeBool
927 %19 = OpTypeInt 32 0
928 %20 = OpConstant %19 10
929 %21 = OpTypeArray %6 %20
930 %22 = OpTypePointer Function %21
931 %24 = OpConstant %6 2
932 %27 = OpConstant %6 1
933 %4 = OpFunction %2 None %3
934 %5 = OpLabel
935 %8 = OpVariable %7 Function
936 %23 = OpVariable %22 Function
937 %29 = OpVariable %22 Function
938 %37 = OpVariable %7 Function
939 %45 = OpVariable %22 Function
940 OpStore %8 %9
941 OpBranch %10
942 %10 = OpLabel
943 %55 = OpPhi %6 %9 %5 %36 %13
944 OpLoopMerge %12 %13 None
945 OpBranch %14
946 %14 = OpLabel
947 %18 = OpSLessThan %17 %55 %16
948 OpBranchConditional %18 %11 %12
949 %11 = OpLabel
950 %26 = OpIMul %6 %24 %55
951 %28 = OpIAdd %6 %26 %27
952 %31 = OpAccessChain %7 %29 %55
953 %32 = OpLoad %6 %31
954 %33 = OpIAdd %6 %32 %27
955 %34 = OpAccessChain %7 %23 %28
956 OpStore %34 %33
957 OpBranch %13
958 %13 = OpLabel
959 %36 = OpIAdd %6 %55 %27
960 OpStore %8 %36
961 OpBranch %10
962 %12 = OpLabel
963 OpStore %37 %9
964 OpBranch %38
965 %38 = OpLabel
966 %56 = OpPhi %6 %9 %12 %54 %41
967 OpLoopMerge %40 %41 None
968 OpBranch %42
969 %42 = OpLabel
970 %44 = OpSLessThan %17 %56 %16
971 OpBranchConditional %44 %39 %40
972 %39 = OpLabel
973 %48 = OpIMul %6 %24 %56
974 %49 = OpAccessChain %7 %23 %48
975 %50 = OpLoad %6 %49
976 %51 = OpIAdd %6 %50 %24
977 %52 = OpAccessChain %7 %45 %56
978 OpStore %52 %51
979 OpBranch %41
980 %41 = OpLabel
981 %54 = OpIAdd %6 %56 %27
982 OpStore %37 %54
983 OpBranch %38
984 %40 = OpLabel
985 OpReturn
986 OpFunctionEnd
987 )";
988
989 std::unique_ptr<IRContext> context =
990 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
991 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
992 Module* module = context->module();
993 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
994 << text << std::endl;
995 Function& f = *module->begin();
996 LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
997 EXPECT_EQ(ld.NumLoops(), 2u);
998
999 auto loops = ld.GetLoopsInBinaryLayoutOrder();
1000
1001 LoopFusion fusion(context.get(), loops[0], loops[1]);
1002
1003 EXPECT_TRUE(fusion.AreCompatible());
1004 EXPECT_TRUE(fusion.IsLegal());
1005
1006 fusion.Fuse();
1007
1008 std::string checks = R"(
1009 CHECK: [[PHI:%\w+]] = OpPhi
1010 CHECK-NEXT: OpLoopMerge
1011 CHECK: [[I_2:%\w+]] = OpIMul {{%\w+}} {{%\w+}} [[PHI]]
1012 CHECK-NEXT: [[I_2_1:%\w+]] = OpIAdd {{%\w+}} [[I_2]] {{%\w+}}
1013 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
1014 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_0]]
1015 CHECK: [[STORE_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[I_2_1]]
1016 CHECK-NEXT: OpStore [[STORE_0]]
1017 CHECK-NOT: OpPhi
1018 CHECK: [[I_2:%\w+]] = OpIMul {{%\w+}} {{%\w+}} [[PHI]]
1019 CHECK-NEXT: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[I_2]]
1020 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_1]]
1021 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
1022 CHECK-NEXT: OpStore [[STORE_1]]
1023 )";
1024
1025 Match(checks, context.get());
1026 auto& ld_final = *context->GetLoopDescriptor(&f);
1027 EXPECT_EQ(ld_final.NumLoops(), 1u);
1028 }
1029
1030 /*
1031 Generated from the following GLSL + --eliminate-local-multi-store
1032
1033 #version 440 core
1034 void main() {
1035 int[10] a;
1036 int[10] b;
1037 int[10] c;
1038 // Legal, independent locations in |a|, ZIV
1039 for (int i = 0; i < 10; i++) {
1040 a[1] = b[i] + 1;
1041 }
1042 for (int i = 0; i < 10; i++) {
1043 c[i] = a[9] + 2;
1044 }
1045 }
1046
1047 */
TEST_F(FusionLegalTest,IndependentZIV)1048 TEST_F(FusionLegalTest, IndependentZIV) {
1049 std::string text = R"(
1050 OpCapability Shader
1051 %1 = OpExtInstImport "GLSL.std.450"
1052 OpMemoryModel Logical GLSL450
1053 OpEntryPoint Fragment %4 "main"
1054 OpExecutionMode %4 OriginUpperLeft
1055 OpSource GLSL 440
1056 OpName %4 "main"
1057 OpName %8 "i"
1058 OpName %23 "a"
1059 OpName %25 "b"
1060 OpName %33 "i"
1061 OpName %41 "c"
1062 %2 = OpTypeVoid
1063 %3 = OpTypeFunction %2
1064 %6 = OpTypeInt 32 1
1065 %7 = OpTypePointer Function %6
1066 %9 = OpConstant %6 0
1067 %16 = OpConstant %6 10
1068 %17 = OpTypeBool
1069 %19 = OpTypeInt 32 0
1070 %20 = OpConstant %19 10
1071 %21 = OpTypeArray %6 %20
1072 %22 = OpTypePointer Function %21
1073 %24 = OpConstant %6 1
1074 %43 = OpConstant %6 9
1075 %46 = OpConstant %6 2
1076 %4 = OpFunction %2 None %3
1077 %5 = OpLabel
1078 %8 = OpVariable %7 Function
1079 %23 = OpVariable %22 Function
1080 %25 = OpVariable %22 Function
1081 %33 = OpVariable %7 Function
1082 %41 = OpVariable %22 Function
1083 OpStore %8 %9
1084 OpBranch %10
1085 %10 = OpLabel
1086 %51 = OpPhi %6 %9 %5 %32 %13
1087 OpLoopMerge %12 %13 None
1088 OpBranch %14
1089 %14 = OpLabel
1090 %18 = OpSLessThan %17 %51 %16
1091 OpBranchConditional %18 %11 %12
1092 %11 = OpLabel
1093 %27 = OpAccessChain %7 %25 %51
1094 %28 = OpLoad %6 %27
1095 %29 = OpIAdd %6 %28 %24
1096 %30 = OpAccessChain %7 %23 %24
1097 OpStore %30 %29
1098 OpBranch %13
1099 %13 = OpLabel
1100 %32 = OpIAdd %6 %51 %24
1101 OpStore %8 %32
1102 OpBranch %10
1103 %12 = OpLabel
1104 OpStore %33 %9
1105 OpBranch %34
1106 %34 = OpLabel
1107 %52 = OpPhi %6 %9 %12 %50 %37
1108 OpLoopMerge %36 %37 None
1109 OpBranch %38
1110 %38 = OpLabel
1111 %40 = OpSLessThan %17 %52 %16
1112 OpBranchConditional %40 %35 %36
1113 %35 = OpLabel
1114 %44 = OpAccessChain %7 %23 %43
1115 %45 = OpLoad %6 %44
1116 %47 = OpIAdd %6 %45 %46
1117 %48 = OpAccessChain %7 %41 %52
1118 OpStore %48 %47
1119 OpBranch %37
1120 %37 = OpLabel
1121 %50 = OpIAdd %6 %52 %24
1122 OpStore %33 %50
1123 OpBranch %34
1124 %36 = OpLabel
1125 OpReturn
1126 OpFunctionEnd
1127 )";
1128
1129 std::unique_ptr<IRContext> context =
1130 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
1131 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
1132 Module* module = context->module();
1133 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
1134 << text << std::endl;
1135 Function& f = *module->begin();
1136 LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
1137 EXPECT_EQ(ld.NumLoops(), 2u);
1138
1139 auto loops = ld.GetLoopsInBinaryLayoutOrder();
1140
1141 LoopFusion fusion(context.get(), loops[0], loops[1]);
1142
1143 EXPECT_TRUE(fusion.AreCompatible());
1144 EXPECT_TRUE(fusion.IsLegal());
1145
1146 fusion.Fuse();
1147
1148 std::string checks = R"(
1149 CHECK: [[PHI:%\w+]] = OpPhi
1150 CHECK-NEXT: OpLoopMerge
1151 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
1152 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_0]]
1153 CHECK-NOT: OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
1154 CHECK: OpStore
1155 CHECK-NOT: OpPhi
1156 CHECK-NOT: OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
1157 CHECK: OpLoad
1158 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
1159 CHECK-NEXT: OpStore [[STORE_1]]
1160 )";
1161
1162 Match(checks, context.get());
1163 auto& ld_final = *context->GetLoopDescriptor(&f);
1164 EXPECT_EQ(ld_final.NumLoops(), 1u);
1165 }
1166
1167 /*
1168 Generated from the following GLSL + --eliminate-local-multi-store
1169
1170 #version 440 core
1171 void main() {
1172 int[20] a;
1173 int[10] b;
1174 int[10] c;
1175 // Legal, non-overlapping sections in |a|
1176 for (int i = 0; i < 10; i++) {
1177 a[i] = b[i] + 1;
1178 }
1179 for (int i = 0; i < 10; i++) {
1180 c[i] = a[i+10] + 2;
1181 }
1182 }
1183
1184 */
TEST_F(FusionLegalTest,NonOverlappingAccesses)1185 TEST_F(FusionLegalTest, NonOverlappingAccesses) {
1186 std::string text = R"(
1187 OpCapability Shader
1188 %1 = OpExtInstImport "GLSL.std.450"
1189 OpMemoryModel Logical GLSL450
1190 OpEntryPoint Fragment %4 "main"
1191 OpExecutionMode %4 OriginUpperLeft
1192 OpSource GLSL 440
1193 OpName %4 "main"
1194 OpName %8 "i"
1195 OpName %23 "a"
1196 OpName %28 "b"
1197 OpName %37 "i"
1198 OpName %45 "c"
1199 %2 = OpTypeVoid
1200 %3 = OpTypeFunction %2
1201 %6 = OpTypeInt 32 1
1202 %7 = OpTypePointer Function %6
1203 %9 = OpConstant %6 0
1204 %16 = OpConstant %6 10
1205 %17 = OpTypeBool
1206 %19 = OpTypeInt 32 0
1207 %20 = OpConstant %19 20
1208 %21 = OpTypeArray %6 %20
1209 %22 = OpTypePointer Function %21
1210 %25 = OpConstant %19 10
1211 %26 = OpTypeArray %6 %25
1212 %27 = OpTypePointer Function %26
1213 %32 = OpConstant %6 1
1214 %51 = OpConstant %6 2
1215 %4 = OpFunction %2 None %3
1216 %5 = OpLabel
1217 %8 = OpVariable %7 Function
1218 %23 = OpVariable %22 Function
1219 %28 = OpVariable %27 Function
1220 %37 = OpVariable %7 Function
1221 %45 = OpVariable %27 Function
1222 OpStore %8 %9
1223 OpBranch %10
1224 %10 = OpLabel
1225 %56 = OpPhi %6 %9 %5 %36 %13
1226 OpLoopMerge %12 %13 None
1227 OpBranch %14
1228 %14 = OpLabel
1229 %18 = OpSLessThan %17 %56 %16
1230 OpBranchConditional %18 %11 %12
1231 %11 = OpLabel
1232 %30 = OpAccessChain %7 %28 %56
1233 %31 = OpLoad %6 %30
1234 %33 = OpIAdd %6 %31 %32
1235 %34 = OpAccessChain %7 %23 %56
1236 OpStore %34 %33
1237 OpBranch %13
1238 %13 = OpLabel
1239 %36 = OpIAdd %6 %56 %32
1240 OpStore %8 %36
1241 OpBranch %10
1242 %12 = OpLabel
1243 OpStore %37 %9
1244 OpBranch %38
1245 %38 = OpLabel
1246 %57 = OpPhi %6 %9 %12 %55 %41
1247 OpLoopMerge %40 %41 None
1248 OpBranch %42
1249 %42 = OpLabel
1250 %44 = OpSLessThan %17 %57 %16
1251 OpBranchConditional %44 %39 %40
1252 %39 = OpLabel
1253 %48 = OpIAdd %6 %57 %16
1254 %49 = OpAccessChain %7 %23 %48
1255 %50 = OpLoad %6 %49
1256 %52 = OpIAdd %6 %50 %51
1257 %53 = OpAccessChain %7 %45 %57
1258 OpStore %53 %52
1259 OpBranch %41
1260 %41 = OpLabel
1261 %55 = OpIAdd %6 %57 %32
1262 OpStore %37 %55
1263 OpBranch %38
1264 %40 = OpLabel
1265 OpReturn
1266 OpFunctionEnd
1267 )";
1268
1269 std::unique_ptr<IRContext> context =
1270 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
1271 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
1272 Module* module = context->module();
1273 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
1274 << text << std::endl;
1275 Function& f = *module->begin();
1276 LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
1277 EXPECT_EQ(ld.NumLoops(), 2u);
1278
1279 auto loops = ld.GetLoopsInBinaryLayoutOrder();
1280
1281 LoopFusion fusion(context.get(), loops[0], loops[1]);
1282
1283 EXPECT_TRUE(fusion.AreCompatible());
1284 EXPECT_TRUE(fusion.IsLegal());
1285
1286 fusion.Fuse();
1287
1288 std::string checks = R"(
1289 CHECK: [[PHI:%\w+]] = OpPhi
1290 CHECK-NEXT: OpLoopMerge
1291 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
1292 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_0]]
1293 CHECK: [[STORE_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
1294 CHECK-NOT: OpPhi
1295 CHECK: [[I_10:%\w+]] = OpIAdd {{%\w+}} [[PHI]] {{%\w+}}
1296 CHECK-NEXT: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[I_10]]
1297 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_1]]
1298 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
1299 CHECK-NEXT: OpStore [[STORE_1]]
1300 )";
1301
1302 Match(checks, context.get());
1303
1304 auto& ld_final = *context->GetLoopDescriptor(&f);
1305 EXPECT_EQ(ld_final.NumLoops(), 1u);
1306 }
1307
1308 /*
1309 Generated from the following GLSL + --eliminate-local-multi-store
1310
1311 #version 440 core
1312 void main() {
1313 int[10] a;
1314 int[10] b;
1315 int[10] c;
1316 // Legal, 3 adjacent loops
1317 for (int i = 0; i < 10; i++) {
1318 a[i] = b[i] + 1;
1319 }
1320 for (int i = 0; i < 10; i++) {
1321 c[i] = a[i] + 2;
1322 }
1323 for (int i = 0; i < 10; i++) {
1324 b[i] = c[i] + 10;
1325 }
1326 }
1327
1328 */
TEST_F(FusionLegalTest,AdjacentLoops)1329 TEST_F(FusionLegalTest, AdjacentLoops) {
1330 std::string text = R"(
1331 OpCapability Shader
1332 %1 = OpExtInstImport "GLSL.std.450"
1333 OpMemoryModel Logical GLSL450
1334 OpEntryPoint Fragment %4 "main"
1335 OpExecutionMode %4 OriginUpperLeft
1336 OpSource GLSL 440
1337 OpName %4 "main"
1338 OpName %8 "i"
1339 OpName %23 "a"
1340 OpName %25 "b"
1341 OpName %34 "i"
1342 OpName %42 "c"
1343 OpName %52 "i"
1344 %2 = OpTypeVoid
1345 %3 = OpTypeFunction %2
1346 %6 = OpTypeInt 32 1
1347 %7 = OpTypePointer Function %6
1348 %9 = OpConstant %6 0
1349 %16 = OpConstant %6 10
1350 %17 = OpTypeBool
1351 %19 = OpTypeInt 32 0
1352 %20 = OpConstant %19 10
1353 %21 = OpTypeArray %6 %20
1354 %22 = OpTypePointer Function %21
1355 %29 = OpConstant %6 1
1356 %47 = OpConstant %6 2
1357 %4 = OpFunction %2 None %3
1358 %5 = OpLabel
1359 %8 = OpVariable %7 Function
1360 %23 = OpVariable %22 Function
1361 %25 = OpVariable %22 Function
1362 %34 = OpVariable %7 Function
1363 %42 = OpVariable %22 Function
1364 %52 = OpVariable %7 Function
1365 OpStore %8 %9
1366 OpBranch %10
1367 %10 = OpLabel
1368 %68 = OpPhi %6 %9 %5 %33 %13
1369 OpLoopMerge %12 %13 None
1370 OpBranch %14
1371 %14 = OpLabel
1372 %18 = OpSLessThan %17 %68 %16
1373 OpBranchConditional %18 %11 %12
1374 %11 = OpLabel
1375 %27 = OpAccessChain %7 %25 %68
1376 %28 = OpLoad %6 %27
1377 %30 = OpIAdd %6 %28 %29
1378 %31 = OpAccessChain %7 %23 %68
1379 OpStore %31 %30
1380 OpBranch %13
1381 %13 = OpLabel
1382 %33 = OpIAdd %6 %68 %29
1383 OpStore %8 %33
1384 OpBranch %10
1385 %12 = OpLabel
1386 OpStore %34 %9
1387 OpBranch %35
1388 %35 = OpLabel
1389 %69 = OpPhi %6 %9 %12 %51 %38
1390 OpLoopMerge %37 %38 None
1391 OpBranch %39
1392 %39 = OpLabel
1393 %41 = OpSLessThan %17 %69 %16
1394 OpBranchConditional %41 %36 %37
1395 %36 = OpLabel
1396 %45 = OpAccessChain %7 %23 %69
1397 %46 = OpLoad %6 %45
1398 %48 = OpIAdd %6 %46 %47
1399 %49 = OpAccessChain %7 %42 %69
1400 OpStore %49 %48
1401 OpBranch %38
1402 %38 = OpLabel
1403 %51 = OpIAdd %6 %69 %29
1404 OpStore %34 %51
1405 OpBranch %35
1406 %37 = OpLabel
1407 OpStore %52 %9
1408 OpBranch %53
1409 %53 = OpLabel
1410 %70 = OpPhi %6 %9 %37 %67 %56
1411 OpLoopMerge %55 %56 None
1412 OpBranch %57
1413 %57 = OpLabel
1414 %59 = OpSLessThan %17 %70 %16
1415 OpBranchConditional %59 %54 %55
1416 %54 = OpLabel
1417 %62 = OpAccessChain %7 %42 %70
1418 %63 = OpLoad %6 %62
1419 %64 = OpIAdd %6 %63 %16
1420 %65 = OpAccessChain %7 %25 %70
1421 OpStore %65 %64
1422 OpBranch %56
1423 %56 = OpLabel
1424 %67 = OpIAdd %6 %70 %29
1425 OpStore %52 %67
1426 OpBranch %53
1427 %55 = OpLabel
1428 OpReturn
1429 OpFunctionEnd
1430 )";
1431
1432 std::unique_ptr<IRContext> context =
1433 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
1434 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
1435 Module* module = context->module();
1436 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
1437 << text << std::endl;
1438 Function& f = *module->begin();
1439
1440 {
1441 LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
1442 EXPECT_EQ(ld.NumLoops(), 3u);
1443
1444 auto loops = ld.GetLoopsInBinaryLayoutOrder();
1445
1446 LoopFusion fusion(context.get(), loops[1], loops[2]);
1447
1448 EXPECT_TRUE(fusion.AreCompatible());
1449 EXPECT_TRUE(fusion.IsLegal());
1450
1451 fusion.Fuse();
1452 }
1453
1454 std::string checks = R"(
1455 CHECK: [[PHI_0:%\w+]] = OpPhi
1456 CHECK-NEXT: OpLoopMerge
1457 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]]
1458 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_0]]
1459 CHECK: [[STORE_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]]
1460 CHECK-NEXT: OpStore [[STORE_0]]
1461 CHECK: [[PHI_1:%\w+]] = OpPhi
1462 CHECK-NEXT: OpLoopMerge
1463 CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_1]]
1464 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_1]]
1465 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_1]]
1466 CHECK-NEXT: OpStore [[STORE_1]]
1467 CHECK-NOT: OpPhi
1468 CHECK: [[LOAD_2:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_1]]
1469 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_2]]
1470 CHECK: [[STORE_2:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_1]]
1471 CHECK-NEXT: OpStore [[STORE_2]]
1472 )";
1473
1474 Match(checks, context.get());
1475
1476 {
1477 LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
1478 EXPECT_EQ(ld.NumLoops(), 2u);
1479
1480 auto loops = ld.GetLoopsInBinaryLayoutOrder();
1481
1482 LoopFusion fusion(context.get(), loops[0], loops[1]);
1483
1484 EXPECT_TRUE(fusion.AreCompatible());
1485 EXPECT_TRUE(fusion.IsLegal());
1486
1487 fusion.Fuse();
1488 }
1489
1490 std::string checks_ = R"(
1491 CHECK: [[PHI:%\w+]] = OpPhi
1492 CHECK-NEXT: OpLoopMerge
1493 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
1494 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_0]]
1495 CHECK: [[STORE_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
1496 CHECK-NEXT: OpStore [[STORE_0]]
1497 CHECK-NOT: OpPhi
1498 CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
1499 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_1]]
1500 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
1501 CHECK-NEXT: OpStore [[STORE_1]]
1502 CHECK-NOT: OpPhi
1503 CHECK: [[LOAD_2:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
1504 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_2]]
1505 CHECK: [[STORE_2:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
1506 CHECK-NEXT: OpStore [[STORE_2]]
1507 )";
1508
1509 Match(checks_, context.get());
1510
1511 auto& ld_final = *context->GetLoopDescriptor(&f);
1512 EXPECT_EQ(ld_final.NumLoops(), 1u);
1513 }
1514
1515 /*
1516 Generated from the following GLSL + --eliminate-local-multi-store
1517
1518 #version 440 core
1519 void main() {
1520 int[10][10] a;
1521 int[10][10] b;
1522 int[10][10] c;
1523 // Legal inner loop fusion
1524 for (int i = 0; i < 10; i++) {
1525 for (int j = 0; j < 10; j++) {
1526 c[i][j] = a[i][j] + 2;
1527 }
1528 for (int j = 0; j < 10; j++) {
1529 b[i][j] = c[i][j] + 10;
1530 }
1531 }
1532 }
1533
1534 */
TEST_F(FusionLegalTest,InnerLoopFusion)1535 TEST_F(FusionLegalTest, InnerLoopFusion) {
1536 std::string text = R"(
1537 OpCapability Shader
1538 %1 = OpExtInstImport "GLSL.std.450"
1539 OpMemoryModel Logical GLSL450
1540 OpEntryPoint Fragment %4 "main"
1541 OpExecutionMode %4 OriginUpperLeft
1542 OpSource GLSL 440
1543 OpName %4 "main"
1544 OpName %8 "i"
1545 OpName %19 "j"
1546 OpName %32 "c"
1547 OpName %35 "a"
1548 OpName %46 "j"
1549 OpName %54 "b"
1550 %2 = OpTypeVoid
1551 %3 = OpTypeFunction %2
1552 %6 = OpTypeInt 32 1
1553 %7 = OpTypePointer Function %6
1554 %9 = OpConstant %6 0
1555 %16 = OpConstant %6 10
1556 %17 = OpTypeBool
1557 %27 = OpTypeInt 32 0
1558 %28 = OpConstant %27 10
1559 %29 = OpTypeArray %6 %28
1560 %30 = OpTypeArray %29 %28
1561 %31 = OpTypePointer Function %30
1562 %40 = OpConstant %6 2
1563 %44 = OpConstant %6 1
1564 %4 = OpFunction %2 None %3
1565 %5 = OpLabel
1566 %8 = OpVariable %7 Function
1567 %19 = OpVariable %7 Function
1568 %32 = OpVariable %31 Function
1569 %35 = OpVariable %31 Function
1570 %46 = OpVariable %7 Function
1571 %54 = OpVariable %31 Function
1572 OpStore %8 %9
1573 OpBranch %10
1574 %10 = OpLabel
1575 %67 = OpPhi %6 %9 %5 %66 %13
1576 OpLoopMerge %12 %13 None
1577 OpBranch %14
1578 %14 = OpLabel
1579 %18 = OpSLessThan %17 %67 %16
1580 OpBranchConditional %18 %11 %12
1581 %11 = OpLabel
1582 OpStore %19 %9
1583 OpBranch %20
1584 %20 = OpLabel
1585 %68 = OpPhi %6 %9 %11 %45 %23
1586 OpLoopMerge %22 %23 None
1587 OpBranch %24
1588 %24 = OpLabel
1589 %26 = OpSLessThan %17 %68 %16
1590 OpBranchConditional %26 %21 %22
1591 %21 = OpLabel
1592 %38 = OpAccessChain %7 %35 %67 %68
1593 %39 = OpLoad %6 %38
1594 %41 = OpIAdd %6 %39 %40
1595 %42 = OpAccessChain %7 %32 %67 %68
1596 OpStore %42 %41
1597 OpBranch %23
1598 %23 = OpLabel
1599 %45 = OpIAdd %6 %68 %44
1600 OpStore %19 %45
1601 OpBranch %20
1602 %22 = OpLabel
1603 OpStore %46 %9
1604 OpBranch %47
1605 %47 = OpLabel
1606 %69 = OpPhi %6 %9 %22 %64 %50
1607 OpLoopMerge %49 %50 None
1608 OpBranch %51
1609 %51 = OpLabel
1610 %53 = OpSLessThan %17 %69 %16
1611 OpBranchConditional %53 %48 %49
1612 %48 = OpLabel
1613 %59 = OpAccessChain %7 %32 %67 %69
1614 %60 = OpLoad %6 %59
1615 %61 = OpIAdd %6 %60 %16
1616 %62 = OpAccessChain %7 %54 %67 %69
1617 OpStore %62 %61
1618 OpBranch %50
1619 %50 = OpLabel
1620 %64 = OpIAdd %6 %69 %44
1621 OpStore %46 %64
1622 OpBranch %47
1623 %49 = OpLabel
1624 OpBranch %13
1625 %13 = OpLabel
1626 %66 = OpIAdd %6 %67 %44
1627 OpStore %8 %66
1628 OpBranch %10
1629 %12 = OpLabel
1630 OpReturn
1631 OpFunctionEnd
1632 )";
1633
1634 std::unique_ptr<IRContext> context =
1635 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
1636 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
1637 Module* module = context->module();
1638 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
1639 << text << std::endl;
1640 Function& f = *module->begin();
1641 LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
1642 EXPECT_EQ(ld.NumLoops(), 3u);
1643
1644 auto loops = ld.GetLoopsInBinaryLayoutOrder();
1645
1646 auto loop_0 = loops[0];
1647 auto loop_1 = loops[1];
1648 auto loop_2 = loops[2];
1649
1650 {
1651 LoopFusion fusion(context.get(), loop_0, loop_1);
1652 EXPECT_FALSE(fusion.AreCompatible());
1653 }
1654
1655 {
1656 LoopFusion fusion(context.get(), loop_0, loop_2);
1657 EXPECT_FALSE(fusion.AreCompatible());
1658 }
1659
1660 {
1661 LoopFusion fusion(context.get(), loop_1, loop_2);
1662 EXPECT_TRUE(fusion.AreCompatible());
1663 EXPECT_TRUE(fusion.IsLegal());
1664
1665 fusion.Fuse();
1666 }
1667
1668 std::string checks = R"(
1669 CHECK: [[PHI_0:%\w+]] = OpPhi
1670 CHECK-NEXT: OpLoopMerge
1671 CHECK: [[PHI_1:%\w+]] = OpPhi
1672 CHECK-NEXT: OpLoopMerge
1673 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] [[PHI_1]]
1674 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_0]]
1675 CHECK: [[STORE_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] [[PHI_1]]
1676 CHECK-NEXT: OpStore [[STORE_0]]
1677 CHECK-NOT: OpPhi
1678 CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] [[PHI_1]]
1679 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_1]]
1680 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] [[PHI_1]]
1681 CHECK-NEXT: OpStore [[STORE_1]]
1682 )";
1683
1684 Match(checks, context.get());
1685
1686 auto& ld_final = *context->GetLoopDescriptor(&f);
1687 EXPECT_EQ(ld_final.NumLoops(), 2u);
1688 }
1689
1690 /*
1691 Generated from the following GLSL + --eliminate-local-multi-store
1692
1693 // 12
1694 #version 440 core
1695 void main() {
1696 int[10][10] a;
1697 int[10][10] b;
1698 int[10][10] c;
1699 // Legal both
1700 for (int i = 0; i < 10; i++) {
1701 for (int j = 0; j < 10; j++) {
1702 c[i][j] = a[i][j] + 2;
1703 }
1704 }
1705 for (int i = 0; i < 10; i++) {
1706 for (int j = 0; j < 10; j++) {
1707 b[i][j] = c[i][j] + 10;
1708 }
1709 }
1710 }
1711
1712 */
TEST_F(FusionLegalTest,OuterAndInnerLoop)1713 TEST_F(FusionLegalTest, OuterAndInnerLoop) {
1714 std::string text = R"(
1715 OpCapability Shader
1716 %1 = OpExtInstImport "GLSL.std.450"
1717 OpMemoryModel Logical GLSL450
1718 OpEntryPoint Fragment %4 "main"
1719 OpExecutionMode %4 OriginUpperLeft
1720 OpSource GLSL 440
1721 OpName %4 "main"
1722 OpName %8 "i"
1723 OpName %19 "j"
1724 OpName %32 "c"
1725 OpName %35 "a"
1726 OpName %48 "i"
1727 OpName %56 "j"
1728 OpName %64 "b"
1729 %2 = OpTypeVoid
1730 %3 = OpTypeFunction %2
1731 %6 = OpTypeInt 32 1
1732 %7 = OpTypePointer Function %6
1733 %9 = OpConstant %6 0
1734 %16 = OpConstant %6 10
1735 %17 = OpTypeBool
1736 %27 = OpTypeInt 32 0
1737 %28 = OpConstant %27 10
1738 %29 = OpTypeArray %6 %28
1739 %30 = OpTypeArray %29 %28
1740 %31 = OpTypePointer Function %30
1741 %40 = OpConstant %6 2
1742 %44 = OpConstant %6 1
1743 %4 = OpFunction %2 None %3
1744 %5 = OpLabel
1745 %8 = OpVariable %7 Function
1746 %19 = OpVariable %7 Function
1747 %32 = OpVariable %31 Function
1748 %35 = OpVariable %31 Function
1749 %48 = OpVariable %7 Function
1750 %56 = OpVariable %7 Function
1751 %64 = OpVariable %31 Function
1752 OpStore %8 %9
1753 OpBranch %10
1754 %10 = OpLabel
1755 %77 = OpPhi %6 %9 %5 %47 %13
1756 OpLoopMerge %12 %13 None
1757 OpBranch %14
1758 %14 = OpLabel
1759 %18 = OpSLessThan %17 %77 %16
1760 OpBranchConditional %18 %11 %12
1761 %11 = OpLabel
1762 OpStore %19 %9
1763 OpBranch %20
1764 %20 = OpLabel
1765 %81 = OpPhi %6 %9 %11 %45 %23
1766 OpLoopMerge %22 %23 None
1767 OpBranch %24
1768 %24 = OpLabel
1769 %26 = OpSLessThan %17 %81 %16
1770 OpBranchConditional %26 %21 %22
1771 %21 = OpLabel
1772 %38 = OpAccessChain %7 %35 %77 %81
1773 %39 = OpLoad %6 %38
1774 %41 = OpIAdd %6 %39 %40
1775 %42 = OpAccessChain %7 %32 %77 %81
1776 OpStore %42 %41
1777 OpBranch %23
1778 %23 = OpLabel
1779 %45 = OpIAdd %6 %81 %44
1780 OpStore %19 %45
1781 OpBranch %20
1782 %22 = OpLabel
1783 OpBranch %13
1784 %13 = OpLabel
1785 %47 = OpIAdd %6 %77 %44
1786 OpStore %8 %47
1787 OpBranch %10
1788 %12 = OpLabel
1789 OpStore %48 %9
1790 OpBranch %49
1791 %49 = OpLabel
1792 %78 = OpPhi %6 %9 %12 %76 %52
1793 OpLoopMerge %51 %52 None
1794 OpBranch %53
1795 %53 = OpLabel
1796 %55 = OpSLessThan %17 %78 %16
1797 OpBranchConditional %55 %50 %51
1798 %50 = OpLabel
1799 OpStore %56 %9
1800 OpBranch %57
1801 %57 = OpLabel
1802 %79 = OpPhi %6 %9 %50 %74 %60
1803 OpLoopMerge %59 %60 None
1804 OpBranch %61
1805 %61 = OpLabel
1806 %63 = OpSLessThan %17 %79 %16
1807 OpBranchConditional %63 %58 %59
1808 %58 = OpLabel
1809 %69 = OpAccessChain %7 %32 %78 %79
1810 %70 = OpLoad %6 %69
1811 %71 = OpIAdd %6 %70 %16
1812 %72 = OpAccessChain %7 %64 %78 %79
1813 OpStore %72 %71
1814 OpBranch %60
1815 %60 = OpLabel
1816 %74 = OpIAdd %6 %79 %44
1817 OpStore %56 %74
1818 OpBranch %57
1819 %59 = OpLabel
1820 OpBranch %52
1821 %52 = OpLabel
1822 %76 = OpIAdd %6 %78 %44
1823 OpStore %48 %76
1824 OpBranch %49
1825 %51 = OpLabel
1826 OpReturn
1827 OpFunctionEnd
1828 )";
1829
1830 std::unique_ptr<IRContext> context =
1831 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
1832 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
1833 Module* module = context->module();
1834 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
1835 << text << std::endl;
1836 Function& f = *module->begin();
1837
1838 {
1839 LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
1840 EXPECT_EQ(ld.NumLoops(), 4u);
1841
1842 auto loops = ld.GetLoopsInBinaryLayoutOrder();
1843
1844 auto loop_0 = loops[0];
1845 auto loop_1 = loops[1];
1846 auto loop_2 = loops[2];
1847 auto loop_3 = loops[3];
1848
1849 {
1850 LoopFusion fusion(context.get(), loop_0, loop_1);
1851 EXPECT_FALSE(fusion.AreCompatible());
1852 }
1853
1854 {
1855 LoopFusion fusion(context.get(), loop_1, loop_2);
1856 EXPECT_FALSE(fusion.AreCompatible());
1857 }
1858
1859 {
1860 LoopFusion fusion(context.get(), loop_2, loop_3);
1861 EXPECT_FALSE(fusion.AreCompatible());
1862 }
1863
1864 {
1865 LoopFusion fusion(context.get(), loop_1, loop_3);
1866 EXPECT_FALSE(fusion.AreCompatible());
1867 }
1868
1869 {
1870 LoopFusion fusion(context.get(), loop_0, loop_2);
1871 EXPECT_TRUE(fusion.AreCompatible());
1872 EXPECT_TRUE(fusion.IsLegal());
1873 fusion.Fuse();
1874 }
1875
1876 std::string checks = R"(
1877 CHECK: [[PHI_0:%\w+]] = OpPhi
1878 CHECK-NEXT: OpLoopMerge
1879 CHECK: [[PHI_1:%\w+]] = OpPhi
1880 CHECK-NEXT: OpLoopMerge
1881 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] [[PHI_1]]
1882 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_0]]
1883 CHECK: [[STORE_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] [[PHI_1]]
1884 CHECK-NEXT: OpStore [[STORE_0]]
1885 CHECK: [[PHI_2:%\w+]] = OpPhi
1886 CHECK-NEXT: OpLoopMerge
1887 CHECK-NOT: OpPhi
1888 CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] [[PHI_2]]
1889 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_1]]
1890 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] [[PHI_2]]
1891 CHECK-NEXT: OpStore [[STORE_1]]
1892 )";
1893
1894 Match(checks, context.get());
1895 }
1896
1897 {
1898 auto& ld = *context->GetLoopDescriptor(&f);
1899 EXPECT_EQ(ld.NumLoops(), 3u);
1900
1901 auto loops = ld.GetLoopsInBinaryLayoutOrder();
1902 auto loop_0 = loops[0];
1903 auto loop_1 = loops[1];
1904 auto loop_2 = loops[2];
1905
1906 {
1907 LoopFusion fusion(context.get(), loop_0, loop_1);
1908 EXPECT_FALSE(fusion.AreCompatible());
1909 }
1910
1911 {
1912 LoopFusion fusion(context.get(), loop_0, loop_2);
1913 EXPECT_FALSE(fusion.AreCompatible());
1914 }
1915
1916 {
1917 LoopFusion fusion(context.get(), loop_1, loop_2);
1918 EXPECT_TRUE(fusion.AreCompatible());
1919 EXPECT_TRUE(fusion.IsLegal());
1920 fusion.Fuse();
1921 }
1922
1923 std::string checks = R"(
1924 CHECK: [[PHI_0:%\w+]] = OpPhi
1925 CHECK-NEXT: OpLoopMerge
1926 CHECK: [[PHI_1:%\w+]] = OpPhi
1927 CHECK-NEXT: OpLoopMerge
1928 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] [[PHI_1]]
1929 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_0]]
1930 CHECK: [[STORE_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] [[PHI_1]]
1931 CHECK-NEXT: OpStore [[STORE_0]]
1932 CHECK-NOT: OpPhi
1933 CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] [[PHI_1]]
1934 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_1]]
1935 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] [[PHI_1]]
1936 CHECK-NEXT: OpStore [[STORE_1]]
1937 )";
1938
1939 Match(checks, context.get());
1940 }
1941
1942 {
1943 auto& ld = *context->GetLoopDescriptor(&f);
1944 EXPECT_EQ(ld.NumLoops(), 2u);
1945 }
1946 }
1947
1948 /*
1949 Generated from the following GLSL + --eliminate-local-multi-store
1950
1951 #version 440 core
1952 void main() {
1953 int[10][10] a;
1954 int[10][10] b;
1955 int[10][10] c;
1956 // Legal both, more complex
1957 for (int i = 0; i < 10; i++) {
1958 for (int j = 0; j < 10; j++) {
1959 if (i % 2 == 0 && j % 2 == 0) {
1960 c[i][j] = a[i][j] + 2;
1961 }
1962 }
1963 }
1964 for (int i = 0; i < 10; i++) {
1965 for (int j = 0; j < 10; j++) {
1966 b[i][j] = c[i][j] + 10;
1967 }
1968 }
1969 }
1970
1971 */
TEST_F(FusionLegalTest,OuterAndInnerLoopMoreComplex)1972 TEST_F(FusionLegalTest, OuterAndInnerLoopMoreComplex) {
1973 std::string text = R"(
1974 OpCapability Shader
1975 %1 = OpExtInstImport "GLSL.std.450"
1976 OpMemoryModel Logical GLSL450
1977 OpEntryPoint Fragment %4 "main"
1978 OpExecutionMode %4 OriginUpperLeft
1979 OpSource GLSL 440
1980 OpName %4 "main"
1981 OpName %8 "i"
1982 OpName %19 "j"
1983 OpName %44 "c"
1984 OpName %47 "a"
1985 OpName %59 "i"
1986 OpName %67 "j"
1987 OpName %75 "b"
1988 %2 = OpTypeVoid
1989 %3 = OpTypeFunction %2
1990 %6 = OpTypeInt 32 1
1991 %7 = OpTypePointer Function %6
1992 %9 = OpConstant %6 0
1993 %16 = OpConstant %6 10
1994 %17 = OpTypeBool
1995 %28 = OpConstant %6 2
1996 %39 = OpTypeInt 32 0
1997 %40 = OpConstant %39 10
1998 %41 = OpTypeArray %6 %40
1999 %42 = OpTypeArray %41 %40
2000 %43 = OpTypePointer Function %42
2001 %55 = OpConstant %6 1
2002 %4 = OpFunction %2 None %3
2003 %5 = OpLabel
2004 %8 = OpVariable %7 Function
2005 %19 = OpVariable %7 Function
2006 %44 = OpVariable %43 Function
2007 %47 = OpVariable %43 Function
2008 %59 = OpVariable %7 Function
2009 %67 = OpVariable %7 Function
2010 %75 = OpVariable %43 Function
2011 OpStore %8 %9
2012 OpBranch %10
2013 %10 = OpLabel
2014 %88 = OpPhi %6 %9 %5 %58 %13
2015 OpLoopMerge %12 %13 None
2016 OpBranch %14
2017 %14 = OpLabel
2018 %18 = OpSLessThan %17 %88 %16
2019 OpBranchConditional %18 %11 %12
2020 %11 = OpLabel
2021 OpStore %19 %9
2022 OpBranch %20
2023 %20 = OpLabel
2024 %92 = OpPhi %6 %9 %11 %56 %23
2025 OpLoopMerge %22 %23 None
2026 OpBranch %24
2027 %24 = OpLabel
2028 %26 = OpSLessThan %17 %92 %16
2029 OpBranchConditional %26 %21 %22
2030 %21 = OpLabel
2031 %29 = OpSMod %6 %88 %28
2032 %30 = OpIEqual %17 %29 %9
2033 OpSelectionMerge %32 None
2034 OpBranchConditional %30 %31 %32
2035 %31 = OpLabel
2036 %34 = OpSMod %6 %92 %28
2037 %35 = OpIEqual %17 %34 %9
2038 OpBranch %32
2039 %32 = OpLabel
2040 %36 = OpPhi %17 %30 %21 %35 %31
2041 OpSelectionMerge %38 None
2042 OpBranchConditional %36 %37 %38
2043 %37 = OpLabel
2044 %50 = OpAccessChain %7 %47 %88 %92
2045 %51 = OpLoad %6 %50
2046 %52 = OpIAdd %6 %51 %28
2047 %53 = OpAccessChain %7 %44 %88 %92
2048 OpStore %53 %52
2049 OpBranch %38
2050 %38 = OpLabel
2051 OpBranch %23
2052 %23 = OpLabel
2053 %56 = OpIAdd %6 %92 %55
2054 OpStore %19 %56
2055 OpBranch %20
2056 %22 = OpLabel
2057 OpBranch %13
2058 %13 = OpLabel
2059 %58 = OpIAdd %6 %88 %55
2060 OpStore %8 %58
2061 OpBranch %10
2062 %12 = OpLabel
2063 OpStore %59 %9
2064 OpBranch %60
2065 %60 = OpLabel
2066 %89 = OpPhi %6 %9 %12 %87 %63
2067 OpLoopMerge %62 %63 None
2068 OpBranch %64
2069 %64 = OpLabel
2070 %66 = OpSLessThan %17 %89 %16
2071 OpBranchConditional %66 %61 %62
2072 %61 = OpLabel
2073 OpStore %67 %9
2074 OpBranch %68
2075 %68 = OpLabel
2076 %90 = OpPhi %6 %9 %61 %85 %71
2077 OpLoopMerge %70 %71 None
2078 OpBranch %72
2079 %72 = OpLabel
2080 %74 = OpSLessThan %17 %90 %16
2081 OpBranchConditional %74 %69 %70
2082 %69 = OpLabel
2083 %80 = OpAccessChain %7 %44 %89 %90
2084 %81 = OpLoad %6 %80
2085 %82 = OpIAdd %6 %81 %16
2086 %83 = OpAccessChain %7 %75 %89 %90
2087 OpStore %83 %82
2088 OpBranch %71
2089 %71 = OpLabel
2090 %85 = OpIAdd %6 %90 %55
2091 OpStore %67 %85
2092 OpBranch %68
2093 %70 = OpLabel
2094 OpBranch %63
2095 %63 = OpLabel
2096 %87 = OpIAdd %6 %89 %55
2097 OpStore %59 %87
2098 OpBranch %60
2099 %62 = OpLabel
2100 OpReturn
2101 OpFunctionEnd
2102 )";
2103
2104 std::unique_ptr<IRContext> context =
2105 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
2106 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
2107 Module* module = context->module();
2108 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
2109 << text << std::endl;
2110 Function& f = *module->begin();
2111
2112 {
2113 LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
2114 EXPECT_EQ(ld.NumLoops(), 4u);
2115
2116 auto loops = ld.GetLoopsInBinaryLayoutOrder();
2117
2118 auto loop_0 = loops[0];
2119 auto loop_1 = loops[1];
2120 auto loop_2 = loops[2];
2121 auto loop_3 = loops[3];
2122
2123 {
2124 LoopFusion fusion(context.get(), loop_0, loop_1);
2125 EXPECT_FALSE(fusion.AreCompatible());
2126 }
2127
2128 {
2129 LoopFusion fusion(context.get(), loop_1, loop_2);
2130 EXPECT_FALSE(fusion.AreCompatible());
2131 }
2132
2133 {
2134 LoopFusion fusion(context.get(), loop_2, loop_3);
2135 EXPECT_FALSE(fusion.AreCompatible());
2136 }
2137
2138 {
2139 LoopFusion fusion(context.get(), loop_1, loop_3);
2140 EXPECT_FALSE(fusion.AreCompatible());
2141 }
2142
2143 {
2144 LoopFusion fusion(context.get(), loop_0, loop_2);
2145 EXPECT_TRUE(fusion.AreCompatible());
2146 EXPECT_TRUE(fusion.IsLegal());
2147 fusion.Fuse();
2148 }
2149
2150 std::string checks = R"(
2151 CHECK: [[PHI_0:%\w+]] = OpPhi
2152 CHECK-NEXT: OpLoopMerge
2153 CHECK: [[PHI_1:%\w+]] = OpPhi
2154 CHECK-NEXT: OpLoopMerge
2155 CHECK: OpPhi
2156 CHECK-NEXT: OpSelectionMerge
2157 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] [[PHI_1]]
2158 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_0]]
2159 CHECK: [[STORE_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] [[PHI_1]]
2160 CHECK-NEXT: OpStore [[STORE_0]]
2161 CHECK: [[PHI_2:%\w+]] = OpPhi
2162 CHECK-NEXT: OpLoopMerge
2163 CHECK-NOT: OpPhi
2164 CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] [[PHI_2]]
2165 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_1]]
2166 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] [[PHI_2]]
2167 CHECK-NEXT: OpStore [[STORE_1]]
2168 )";
2169
2170 Match(checks, context.get());
2171 }
2172
2173 {
2174 LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
2175 EXPECT_EQ(ld.NumLoops(), 3u);
2176
2177 auto loops = ld.GetLoopsInBinaryLayoutOrder();
2178
2179 auto loop_0 = loops[0];
2180 auto loop_1 = loops[1];
2181 auto loop_2 = loops[2];
2182
2183 {
2184 LoopFusion fusion(context.get(), loop_0, loop_1);
2185 EXPECT_FALSE(fusion.AreCompatible());
2186 }
2187
2188 {
2189 LoopFusion fusion(context.get(), loop_0, loop_2);
2190 EXPECT_FALSE(fusion.AreCompatible());
2191 }
2192
2193 {
2194 LoopFusion fusion(context.get(), loop_1, loop_2);
2195 EXPECT_TRUE(fusion.AreCompatible());
2196 EXPECT_TRUE(fusion.IsLegal());
2197 fusion.Fuse();
2198 }
2199
2200 std::string checks = R"(
2201 CHECK: [[PHI_0:%\w+]] = OpPhi
2202 CHECK-NEXT: OpLoopMerge
2203 CHECK: [[PHI_1:%\w+]] = OpPhi
2204 CHECK-NEXT: OpLoopMerge
2205 CHECK: OpPhi
2206 CHECK-NEXT: OpSelectionMerge
2207 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] [[PHI_1]]
2208 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_0]]
2209 CHECK: [[STORE_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] [[PHI_1]]
2210 CHECK-NEXT: OpStore [[STORE_0]]
2211 CHECK-NOT: OpPhi
2212 CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] [[PHI_1]]
2213 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_1]]
2214 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] [[PHI_1]]
2215 CHECK-NEXT: OpStore [[STORE_1]]
2216 )";
2217
2218 Match(checks, context.get());
2219 }
2220
2221 {
2222 LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
2223 EXPECT_EQ(ld.NumLoops(), 2u);
2224 }
2225 }
2226
2227 /*
2228 Generated from the following GLSL + --eliminate-local-multi-store
2229
2230 #version 440 core
2231 void main() {
2232 int[10][10] a;
2233 int[10][10] b;
2234 int[10][10] c;
2235 // Outer would have been illegal to fuse, but since written
2236 // like this, inner loop fusion is legal.
2237 for (int i = 0; i < 10; i++) {
2238 for (int j = 0; j < 10; j++) {
2239 c[i][j] = a[i][j] + 2;
2240 }
2241 for (int j = 0; j < 10; j++) {
2242 b[i][j] = c[i+1][j] + 10;
2243 }
2244 }
2245 }
2246
2247 */
TEST_F(FusionLegalTest,InnerWithExistingDependenceOnOuter)2248 TEST_F(FusionLegalTest, InnerWithExistingDependenceOnOuter) {
2249 std::string text = R"(
2250 OpCapability Shader
2251 %1 = OpExtInstImport "GLSL.std.450"
2252 OpMemoryModel Logical GLSL450
2253 OpEntryPoint Fragment %4 "main"
2254 OpExecutionMode %4 OriginUpperLeft
2255 OpSource GLSL 440
2256 OpName %4 "main"
2257 OpName %8 "i"
2258 OpName %19 "j"
2259 OpName %32 "c"
2260 OpName %35 "a"
2261 OpName %46 "j"
2262 OpName %54 "b"
2263 %2 = OpTypeVoid
2264 %3 = OpTypeFunction %2
2265 %6 = OpTypeInt 32 1
2266 %7 = OpTypePointer Function %6
2267 %9 = OpConstant %6 0
2268 %16 = OpConstant %6 10
2269 %17 = OpTypeBool
2270 %27 = OpTypeInt 32 0
2271 %28 = OpConstant %27 10
2272 %29 = OpTypeArray %6 %28
2273 %30 = OpTypeArray %29 %28
2274 %31 = OpTypePointer Function %30
2275 %40 = OpConstant %6 2
2276 %44 = OpConstant %6 1
2277 %4 = OpFunction %2 None %3
2278 %5 = OpLabel
2279 %8 = OpVariable %7 Function
2280 %19 = OpVariable %7 Function
2281 %32 = OpVariable %31 Function
2282 %35 = OpVariable %31 Function
2283 %46 = OpVariable %7 Function
2284 %54 = OpVariable %31 Function
2285 OpStore %8 %9
2286 OpBranch %10
2287 %10 = OpLabel
2288 %68 = OpPhi %6 %9 %5 %67 %13
2289 OpLoopMerge %12 %13 None
2290 OpBranch %14
2291 %14 = OpLabel
2292 %18 = OpSLessThan %17 %68 %16
2293 OpBranchConditional %18 %11 %12
2294 %11 = OpLabel
2295 OpStore %19 %9
2296 OpBranch %20
2297 %20 = OpLabel
2298 %69 = OpPhi %6 %9 %11 %45 %23
2299 OpLoopMerge %22 %23 None
2300 OpBranch %24
2301 %24 = OpLabel
2302 %26 = OpSLessThan %17 %69 %16
2303 OpBranchConditional %26 %21 %22
2304 %21 = OpLabel
2305 %38 = OpAccessChain %7 %35 %68 %69
2306 %39 = OpLoad %6 %38
2307 %41 = OpIAdd %6 %39 %40
2308 %42 = OpAccessChain %7 %32 %68 %69
2309 OpStore %42 %41
2310 OpBranch %23
2311 %23 = OpLabel
2312 %45 = OpIAdd %6 %69 %44
2313 OpStore %19 %45
2314 OpBranch %20
2315 %22 = OpLabel
2316 OpStore %46 %9
2317 OpBranch %47
2318 %47 = OpLabel
2319 %70 = OpPhi %6 %9 %22 %65 %50
2320 OpLoopMerge %49 %50 None
2321 OpBranch %51
2322 %51 = OpLabel
2323 %53 = OpSLessThan %17 %70 %16
2324 OpBranchConditional %53 %48 %49
2325 %48 = OpLabel
2326 %58 = OpIAdd %6 %68 %44
2327 %60 = OpAccessChain %7 %32 %58 %70
2328 %61 = OpLoad %6 %60
2329 %62 = OpIAdd %6 %61 %16
2330 %63 = OpAccessChain %7 %54 %68 %70
2331 OpStore %63 %62
2332 OpBranch %50
2333 %50 = OpLabel
2334 %65 = OpIAdd %6 %70 %44
2335 OpStore %46 %65
2336 OpBranch %47
2337 %49 = OpLabel
2338 OpBranch %13
2339 %13 = OpLabel
2340 %67 = OpIAdd %6 %68 %44
2341 OpStore %8 %67
2342 OpBranch %10
2343 %12 = OpLabel
2344 OpReturn
2345 OpFunctionEnd
2346 )";
2347
2348 std::unique_ptr<IRContext> context =
2349 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
2350 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
2351 Module* module = context->module();
2352 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
2353 << text << std::endl;
2354 Function& f = *module->begin();
2355
2356 {
2357 LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
2358 EXPECT_EQ(ld.NumLoops(), 3u);
2359
2360 auto loops = ld.GetLoopsInBinaryLayoutOrder();
2361
2362 auto loop_0 = loops[0];
2363 auto loop_1 = loops[1];
2364 auto loop_2 = loops[2];
2365
2366 {
2367 LoopFusion fusion(context.get(), loop_0, loop_1);
2368 EXPECT_FALSE(fusion.AreCompatible());
2369 }
2370
2371 {
2372 LoopFusion fusion(context.get(), loop_0, loop_2);
2373 EXPECT_FALSE(fusion.AreCompatible());
2374 }
2375
2376 {
2377 LoopFusion fusion(context.get(), loop_1, loop_2);
2378 EXPECT_TRUE(fusion.AreCompatible());
2379 EXPECT_TRUE(fusion.IsLegal());
2380
2381 fusion.Fuse();
2382 }
2383 }
2384
2385 {
2386 LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
2387 EXPECT_EQ(ld.NumLoops(), 2u);
2388
2389 std::string checks = R"(
2390 CHECK: [[PHI_0:%\w+]] = OpPhi
2391 CHECK-NEXT: OpLoopMerge
2392 CHECK: [[PHI_1:%\w+]] = OpPhi
2393 CHECK-NEXT: OpLoopMerge
2394 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] [[PHI_1]]
2395 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_0]]
2396 CHECK: [[STORE_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] [[PHI_1]]
2397 CHECK-NEXT: OpStore [[STORE_0]]
2398 CHECK-NOT: OpPhi
2399 CHECK: [[I_1:%\w+]] = OpIAdd {{%\w+}} [[PHI_0]] {{%\w+}}
2400 CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[I_1]] [[PHI_1]]
2401 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_1]]
2402 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] [[PHI_1]]
2403 CHECK-NEXT: OpStore [[STORE_1]]
2404 )";
2405
2406 Match(checks, context.get());
2407 }
2408 }
2409
2410 /*
2411 Generated from the following GLSL + --eliminate-local-multi-store
2412
2413 #version 440 core
2414 void main() {
2415 int[10] a;
2416 int[10] b;
2417 int[10] c;
2418 // One dimensional arrays. Legal, outer dist 0, inner independent.
2419 for (int i = 0; i < 10; i++) {
2420 for (int j = 0; j < 10; j++) {
2421 c[i] = a[j] + 2;
2422 }
2423 }
2424 for (int i = 0; i < 10; i++) {
2425 for (int j = 0; j < 10; j++) {
2426 b[j] = c[i] + 10;
2427 }
2428 }
2429 }
2430
2431 */
TEST_F(FusionLegalTest,OuterAndInnerLoopOneDimArrays)2432 TEST_F(FusionLegalTest, OuterAndInnerLoopOneDimArrays) {
2433 std::string text = R"(
2434 OpCapability Shader
2435 %1 = OpExtInstImport "GLSL.std.450"
2436 OpMemoryModel Logical GLSL450
2437 OpEntryPoint Fragment %4 "main"
2438 OpExecutionMode %4 OriginUpperLeft
2439 OpSource GLSL 440
2440 OpName %4 "main"
2441 OpName %8 "i"
2442 OpName %19 "j"
2443 OpName %31 "c"
2444 OpName %33 "a"
2445 OpName %45 "i"
2446 OpName %53 "j"
2447 OpName %61 "b"
2448 %2 = OpTypeVoid
2449 %3 = OpTypeFunction %2
2450 %6 = OpTypeInt 32 1
2451 %7 = OpTypePointer Function %6
2452 %9 = OpConstant %6 0
2453 %16 = OpConstant %6 10
2454 %17 = OpTypeBool
2455 %27 = OpTypeInt 32 0
2456 %28 = OpConstant %27 10
2457 %29 = OpTypeArray %6 %28
2458 %30 = OpTypePointer Function %29
2459 %37 = OpConstant %6 2
2460 %41 = OpConstant %6 1
2461 %4 = OpFunction %2 None %3
2462 %5 = OpLabel
2463 %8 = OpVariable %7 Function
2464 %19 = OpVariable %7 Function
2465 %31 = OpVariable %30 Function
2466 %33 = OpVariable %30 Function
2467 %45 = OpVariable %7 Function
2468 %53 = OpVariable %7 Function
2469 %61 = OpVariable %30 Function
2470 OpStore %8 %9
2471 OpBranch %10
2472 %10 = OpLabel
2473 %72 = OpPhi %6 %9 %5 %44 %13
2474 OpLoopMerge %12 %13 None
2475 OpBranch %14
2476 %14 = OpLabel
2477 %18 = OpSLessThan %17 %72 %16
2478 OpBranchConditional %18 %11 %12
2479 %11 = OpLabel
2480 OpStore %19 %9
2481 OpBranch %20
2482 %20 = OpLabel
2483 %76 = OpPhi %6 %9 %11 %42 %23
2484 OpLoopMerge %22 %23 None
2485 OpBranch %24
2486 %24 = OpLabel
2487 %26 = OpSLessThan %17 %76 %16
2488 OpBranchConditional %26 %21 %22
2489 %21 = OpLabel
2490 %35 = OpAccessChain %7 %33 %76
2491 %36 = OpLoad %6 %35
2492 %38 = OpIAdd %6 %36 %37
2493 %39 = OpAccessChain %7 %31 %72
2494 OpStore %39 %38
2495 OpBranch %23
2496 %23 = OpLabel
2497 %42 = OpIAdd %6 %76 %41
2498 OpStore %19 %42
2499 OpBranch %20
2500 %22 = OpLabel
2501 OpBranch %13
2502 %13 = OpLabel
2503 %44 = OpIAdd %6 %72 %41
2504 OpStore %8 %44
2505 OpBranch %10
2506 %12 = OpLabel
2507 OpStore %45 %9
2508 OpBranch %46
2509 %46 = OpLabel
2510 %73 = OpPhi %6 %9 %12 %71 %49
2511 OpLoopMerge %48 %49 None
2512 OpBranch %50
2513 %50 = OpLabel
2514 %52 = OpSLessThan %17 %73 %16
2515 OpBranchConditional %52 %47 %48
2516 %47 = OpLabel
2517 OpStore %53 %9
2518 OpBranch %54
2519 %54 = OpLabel
2520 %74 = OpPhi %6 %9 %47 %69 %57
2521 OpLoopMerge %56 %57 None
2522 OpBranch %58
2523 %58 = OpLabel
2524 %60 = OpSLessThan %17 %74 %16
2525 OpBranchConditional %60 %55 %56
2526 %55 = OpLabel
2527 %64 = OpAccessChain %7 %31 %73
2528 %65 = OpLoad %6 %64
2529 %66 = OpIAdd %6 %65 %16
2530 %67 = OpAccessChain %7 %61 %74
2531 OpStore %67 %66
2532 OpBranch %57
2533 %57 = OpLabel
2534 %69 = OpIAdd %6 %74 %41
2535 OpStore %53 %69
2536 OpBranch %54
2537 %56 = OpLabel
2538 OpBranch %49
2539 %49 = OpLabel
2540 %71 = OpIAdd %6 %73 %41
2541 OpStore %45 %71
2542 OpBranch %46
2543 %48 = OpLabel
2544 OpReturn
2545 OpFunctionEnd
2546 )";
2547
2548 std::unique_ptr<IRContext> context =
2549 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
2550 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
2551 Module* module = context->module();
2552 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
2553 << text << std::endl;
2554 Function& f = *module->begin();
2555
2556 {
2557 LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
2558 EXPECT_EQ(ld.NumLoops(), 4u);
2559
2560 auto loops = ld.GetLoopsInBinaryLayoutOrder();
2561
2562 auto loop_0 = loops[0];
2563 auto loop_1 = loops[1];
2564 auto loop_2 = loops[2];
2565 auto loop_3 = loops[3];
2566
2567 {
2568 LoopFusion fusion(context.get(), loop_0, loop_1);
2569 EXPECT_FALSE(fusion.AreCompatible());
2570 }
2571
2572 {
2573 LoopFusion fusion(context.get(), loop_1, loop_2);
2574 EXPECT_FALSE(fusion.AreCompatible());
2575 }
2576
2577 {
2578 LoopFusion fusion(context.get(), loop_2, loop_3);
2579 EXPECT_FALSE(fusion.AreCompatible());
2580 }
2581
2582 {
2583 LoopFusion fusion(context.get(), loop_0, loop_2);
2584 EXPECT_TRUE(fusion.AreCompatible());
2585 EXPECT_TRUE(fusion.IsLegal());
2586 fusion.Fuse();
2587 }
2588
2589 std::string checks = R"(
2590 CHECK: [[PHI_0:%\w+]] = OpPhi
2591 CHECK-NEXT: OpLoopMerge
2592 CHECK: [[PHI_1:%\w+]] = OpPhi
2593 CHECK-NEXT: OpLoopMerge
2594 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_1]]
2595 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_0]]
2596 CHECK: [[STORE_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]]
2597 CHECK-NEXT: OpStore [[STORE_0]]
2598 CHECK: [[PHI_2:%\w+]] = OpPhi
2599 CHECK-NEXT: OpLoopMerge
2600 CHECK-NOT: OpPhi
2601 CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]]
2602 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_1]]
2603 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_2]]
2604 CHECK-NEXT: OpStore [[STORE_1]]
2605 )";
2606
2607 Match(checks, context.get());
2608 }
2609
2610 {
2611 LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
2612 EXPECT_EQ(ld.NumLoops(), 3u);
2613
2614 auto loops = ld.GetLoopsInBinaryLayoutOrder();
2615
2616 auto loop_0 = loops[0];
2617 auto loop_1 = loops[1];
2618 auto loop_2 = loops[2];
2619
2620 {
2621 LoopFusion fusion(context.get(), loop_0, loop_1);
2622 EXPECT_FALSE(fusion.AreCompatible());
2623 }
2624
2625 {
2626 LoopFusion fusion(context.get(), loop_0, loop_2);
2627 EXPECT_FALSE(fusion.AreCompatible());
2628 }
2629
2630 {
2631 LoopFusion fusion(context.get(), loop_1, loop_2);
2632 EXPECT_TRUE(fusion.AreCompatible());
2633 EXPECT_TRUE(fusion.IsLegal());
2634
2635 fusion.Fuse();
2636 }
2637
2638 std::string checks = R"(
2639 CHECK: [[PHI_0:%\w+]] = OpPhi
2640 CHECK-NEXT: OpLoopMerge
2641 CHECK: [[PHI_1:%\w+]] = OpPhi
2642 CHECK-NEXT: OpLoopMerge
2643 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_1]]
2644 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_0]]
2645 CHECK: [[STORE_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]]
2646 CHECK-NEXT: OpStore [[STORE_0]]
2647 CHECK-NOT: OpPhi
2648 CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]]
2649 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_1]]
2650 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_1]]
2651 CHECK-NEXT: OpStore [[STORE_1]]
2652 )";
2653
2654 Match(checks, context.get());
2655 }
2656 }
2657
2658 /*
2659 Generated from the following GLSL + --eliminate-local-multi-store
2660
2661 #version 440 core
2662 void main() {
2663 int[10] a;
2664 int[10] b;
2665 int[10] c;
2666 // Legal, creates a loop-carried dependence, but has negative distance
2667 for (int i = 0; i < 10; i++) {
2668 c[i] = a[i+1] + 1;
2669 }
2670 for (int i = 0; i < 10; i++) {
2671 a[i] = c[i] + 2;
2672 }
2673 }
2674
2675 */
TEST_F(FusionLegalTest,NegativeDistanceCreatedWAR)2676 TEST_F(FusionLegalTest, NegativeDistanceCreatedWAR) {
2677 std::string text = R"(
2678 OpCapability Shader
2679 %1 = OpExtInstImport "GLSL.std.450"
2680 OpMemoryModel Logical GLSL450
2681 OpEntryPoint Fragment %4 "main"
2682 OpExecutionMode %4 OriginUpperLeft
2683 OpSource GLSL 440
2684 OpName %4 "main"
2685 OpName %8 "i"
2686 OpName %23 "c"
2687 OpName %25 "a"
2688 OpName %35 "i"
2689 %2 = OpTypeVoid
2690 %3 = OpTypeFunction %2
2691 %6 = OpTypeInt 32 1
2692 %7 = OpTypePointer Function %6
2693 %9 = OpConstant %6 0
2694 %16 = OpConstant %6 10
2695 %17 = OpTypeBool
2696 %19 = OpTypeInt 32 0
2697 %20 = OpConstant %19 10
2698 %21 = OpTypeArray %6 %20
2699 %22 = OpTypePointer Function %21
2700 %27 = OpConstant %6 1
2701 %47 = OpConstant %6 2
2702 %4 = OpFunction %2 None %3
2703 %5 = OpLabel
2704 %8 = OpVariable %7 Function
2705 %23 = OpVariable %22 Function
2706 %25 = OpVariable %22 Function
2707 %35 = OpVariable %7 Function
2708 OpStore %8 %9
2709 OpBranch %10
2710 %10 = OpLabel
2711 %52 = OpPhi %6 %9 %5 %34 %13
2712 OpLoopMerge %12 %13 None
2713 OpBranch %14
2714 %14 = OpLabel
2715 %18 = OpSLessThan %17 %52 %16
2716 OpBranchConditional %18 %11 %12
2717 %11 = OpLabel
2718 %28 = OpIAdd %6 %52 %27
2719 %29 = OpAccessChain %7 %25 %28
2720 %30 = OpLoad %6 %29
2721 %31 = OpIAdd %6 %30 %27
2722 %32 = OpAccessChain %7 %23 %52
2723 OpStore %32 %31
2724 OpBranch %13
2725 %13 = OpLabel
2726 %34 = OpIAdd %6 %52 %27
2727 OpStore %8 %34
2728 OpBranch %10
2729 %12 = OpLabel
2730 OpStore %35 %9
2731 OpBranch %36
2732 %36 = OpLabel
2733 %53 = OpPhi %6 %9 %12 %51 %39
2734 OpLoopMerge %38 %39 None
2735 OpBranch %40
2736 %40 = OpLabel
2737 %42 = OpSLessThan %17 %53 %16
2738 OpBranchConditional %42 %37 %38
2739 %37 = OpLabel
2740 %45 = OpAccessChain %7 %23 %53
2741 %46 = OpLoad %6 %45
2742 %48 = OpIAdd %6 %46 %47
2743 %49 = OpAccessChain %7 %25 %53
2744 OpStore %49 %48
2745 OpBranch %39
2746 %39 = OpLabel
2747 %51 = OpIAdd %6 %53 %27
2748 OpStore %35 %51
2749 OpBranch %36
2750 %38 = OpLabel
2751 OpReturn
2752 OpFunctionEnd
2753 )";
2754
2755 std::unique_ptr<IRContext> context =
2756 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
2757 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
2758 Module* module = context->module();
2759 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
2760 << text << std::endl;
2761 Function& f = *module->begin();
2762
2763 {
2764 LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
2765 EXPECT_EQ(ld.NumLoops(), 2u);
2766
2767 auto loops = ld.GetLoopsInBinaryLayoutOrder();
2768
2769 LoopFusion fusion(context.get(), loops[0], loops[1]);
2770 EXPECT_TRUE(fusion.AreCompatible());
2771 EXPECT_TRUE(fusion.IsLegal());
2772
2773 fusion.Fuse();
2774
2775 std::string checks = R"(
2776 CHECK: [[PHI:%\w+]] = OpPhi
2777 CHECK: [[I_1:%\w+]] = OpIAdd {{%\w+}} [[PHI]] {{%\w+}}
2778 CHECK-NEXT: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[I_1]]
2779 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_0]]
2780 CHECK: [[STORE_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
2781 CHECK-NEXT: OpStore [[STORE_0]]
2782 CHECK-NOT: OpPhi
2783 CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
2784 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_1]]
2785 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
2786 CHECK-NEXT: OpStore [[STORE_1]]
2787 )";
2788
2789 Match(checks, context.get());
2790 }
2791
2792 {
2793 auto& ld = *context->GetLoopDescriptor(&f);
2794 EXPECT_EQ(ld.NumLoops(), 1u);
2795 }
2796 }
2797
2798 /*
2799 Generated from the following GLSL + --eliminate-local-multi-store
2800
2801 #version 440 core
2802 void main() {
2803 int[10] a;
2804 int[10] b;
2805 int[10] c;
2806 // Legal, creates a loop-carried dependence, but has negative distance
2807 for (int i = 0; i < 10; i++) {
2808 a[i+1] = b[i] + 1;
2809 }
2810 for (int i = 0; i < 10; i++) {
2811 a[i] = c[i+1] + 2;
2812 }
2813 }
2814
2815 */
TEST_F(FusionLegalTest,NegativeDistanceCreatedWAW)2816 TEST_F(FusionLegalTest, NegativeDistanceCreatedWAW) {
2817 std::string text = R"(
2818 OpCapability Shader
2819 %1 = OpExtInstImport "GLSL.std.450"
2820 OpMemoryModel Logical GLSL450
2821 OpEntryPoint Fragment %4 "main"
2822 OpExecutionMode %4 OriginUpperLeft
2823 OpSource GLSL 440
2824 OpName %4 "main"
2825 OpName %8 "i"
2826 OpName %23 "a"
2827 OpName %27 "b"
2828 OpName %35 "i"
2829 OpName %44 "c"
2830 %2 = OpTypeVoid
2831 %3 = OpTypeFunction %2
2832 %6 = OpTypeInt 32 1
2833 %7 = OpTypePointer Function %6
2834 %9 = OpConstant %6 0
2835 %16 = OpConstant %6 10
2836 %17 = OpTypeBool
2837 %19 = OpTypeInt 32 0
2838 %20 = OpConstant %19 10
2839 %21 = OpTypeArray %6 %20
2840 %22 = OpTypePointer Function %21
2841 %25 = OpConstant %6 1
2842 %49 = OpConstant %6 2
2843 %4 = OpFunction %2 None %3
2844 %5 = OpLabel
2845 %8 = OpVariable %7 Function
2846 %23 = OpVariable %22 Function
2847 %27 = OpVariable %22 Function
2848 %35 = OpVariable %7 Function
2849 %44 = OpVariable %22 Function
2850 OpStore %8 %9
2851 OpBranch %10
2852 %10 = OpLabel
2853 %54 = OpPhi %6 %9 %5 %34 %13
2854 OpLoopMerge %12 %13 None
2855 OpBranch %14
2856 %14 = OpLabel
2857 %18 = OpSLessThan %17 %54 %16
2858 OpBranchConditional %18 %11 %12
2859 %11 = OpLabel
2860 %26 = OpIAdd %6 %54 %25
2861 %29 = OpAccessChain %7 %27 %54
2862 %30 = OpLoad %6 %29
2863 %31 = OpIAdd %6 %30 %25
2864 %32 = OpAccessChain %7 %23 %26
2865 OpStore %32 %31
2866 OpBranch %13
2867 %13 = OpLabel
2868 %34 = OpIAdd %6 %54 %25
2869 OpStore %8 %34
2870 OpBranch %10
2871 %12 = OpLabel
2872 OpStore %35 %9
2873 OpBranch %36
2874 %36 = OpLabel
2875 %55 = OpPhi %6 %9 %12 %53 %39
2876 OpLoopMerge %38 %39 None
2877 OpBranch %40
2878 %40 = OpLabel
2879 %42 = OpSLessThan %17 %55 %16
2880 OpBranchConditional %42 %37 %38
2881 %37 = OpLabel
2882 %46 = OpIAdd %6 %55 %25
2883 %47 = OpAccessChain %7 %44 %46
2884 %48 = OpLoad %6 %47
2885 %50 = OpIAdd %6 %48 %49
2886 %51 = OpAccessChain %7 %23 %55
2887 OpStore %51 %50
2888 OpBranch %39
2889 %39 = OpLabel
2890 %53 = OpIAdd %6 %55 %25
2891 OpStore %35 %53
2892 OpBranch %36
2893 %38 = OpLabel
2894 OpReturn
2895 OpFunctionEnd
2896 )";
2897
2898 std::unique_ptr<IRContext> context =
2899 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
2900 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
2901 Module* module = context->module();
2902 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
2903 << text << std::endl;
2904 Function& f = *module->begin();
2905
2906 {
2907 LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
2908 EXPECT_EQ(ld.NumLoops(), 2u);
2909
2910 auto loops = ld.GetLoopsInBinaryLayoutOrder();
2911
2912 LoopFusion fusion(context.get(), loops[0], loops[1]);
2913 EXPECT_TRUE(fusion.AreCompatible());
2914 EXPECT_TRUE(fusion.IsLegal());
2915
2916 fusion.Fuse();
2917 }
2918
2919 {
2920 LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
2921 EXPECT_EQ(ld.NumLoops(), 1u);
2922
2923 std::string checks = R"(
2924 CHECK: [[PHI:%\w+]] = OpPhi
2925 CHECK-NEXT: OpLoopMerge
2926 CHECK: [[I_1:%\w+]] = OpIAdd {{%\w+}} [[PHI]] {{%\w+}}
2927 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
2928 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_0]]
2929 CHECK: [[STORE_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[I_1]]
2930 CHECK-NEXT: OpStore
2931 CHECK-NOT: OpPhi
2932 CHECK: [[I_1:%\w+]] = OpIAdd {{%\w+}} [[PHI]] {{%\w+}}
2933 CHECK-NEXT: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[I_1]]
2934 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_1]]
2935 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
2936 CHECK-NEXT: OpStore [[STORE_1]]
2937 )";
2938
2939 Match(checks, context.get());
2940 }
2941 }
2942
2943 /*
2944 Generated from the following GLSL + --eliminate-local-multi-store
2945
2946 #version 440 core
2947 void main() {
2948 int[10] a;
2949 int[10] b;
2950 int[10] c;
2951 // Legal, no loop-carried dependence
2952 for (int i = 0; i < 10; i++) {
2953 a[i] = b[i] + 1;
2954 }
2955 for (int i = 0; i < 10; i++) {
2956 a[i] = c[i+1] + 2;
2957 }
2958 }
2959
2960 */
TEST_F(FusionLegalTest,NoLoopCarriedDependencesWAW)2961 TEST_F(FusionLegalTest, NoLoopCarriedDependencesWAW) {
2962 std::string text = R"(
2963 OpCapability Shader
2964 %1 = OpExtInstImport "GLSL.std.450"
2965 OpMemoryModel Logical GLSL450
2966 OpEntryPoint Fragment %4 "main"
2967 OpExecutionMode %4 OriginUpperLeft
2968 OpSource GLSL 440
2969 OpName %4 "main"
2970 OpName %8 "i"
2971 OpName %23 "a"
2972 OpName %25 "b"
2973 OpName %34 "i"
2974 OpName %43 "c"
2975 %2 = OpTypeVoid
2976 %3 = OpTypeFunction %2
2977 %6 = OpTypeInt 32 1
2978 %7 = OpTypePointer Function %6
2979 %9 = OpConstant %6 0
2980 %16 = OpConstant %6 10
2981 %17 = OpTypeBool
2982 %19 = OpTypeInt 32 0
2983 %20 = OpConstant %19 10
2984 %21 = OpTypeArray %6 %20
2985 %22 = OpTypePointer Function %21
2986 %29 = OpConstant %6 1
2987 %48 = OpConstant %6 2
2988 %4 = OpFunction %2 None %3
2989 %5 = OpLabel
2990 %8 = OpVariable %7 Function
2991 %23 = OpVariable %22 Function
2992 %25 = OpVariable %22 Function
2993 %34 = OpVariable %7 Function
2994 %43 = OpVariable %22 Function
2995 OpStore %8 %9
2996 OpBranch %10
2997 %10 = OpLabel
2998 %53 = OpPhi %6 %9 %5 %33 %13
2999 OpLoopMerge %12 %13 None
3000 OpBranch %14
3001 %14 = OpLabel
3002 %18 = OpSLessThan %17 %53 %16
3003 OpBranchConditional %18 %11 %12
3004 %11 = OpLabel
3005 %27 = OpAccessChain %7 %25 %53
3006 %28 = OpLoad %6 %27
3007 %30 = OpIAdd %6 %28 %29
3008 %31 = OpAccessChain %7 %23 %53
3009 OpStore %31 %30
3010 OpBranch %13
3011 %13 = OpLabel
3012 %33 = OpIAdd %6 %53 %29
3013 OpStore %8 %33
3014 OpBranch %10
3015 %12 = OpLabel
3016 OpStore %34 %9
3017 OpBranch %35
3018 %35 = OpLabel
3019 %54 = OpPhi %6 %9 %12 %52 %38
3020 OpLoopMerge %37 %38 None
3021 OpBranch %39
3022 %39 = OpLabel
3023 %41 = OpSLessThan %17 %54 %16
3024 OpBranchConditional %41 %36 %37
3025 %36 = OpLabel
3026 %45 = OpIAdd %6 %54 %29
3027 %46 = OpAccessChain %7 %43 %45
3028 %47 = OpLoad %6 %46
3029 %49 = OpIAdd %6 %47 %48
3030 %50 = OpAccessChain %7 %23 %54
3031 OpStore %50 %49
3032 OpBranch %38
3033 %38 = OpLabel
3034 %52 = OpIAdd %6 %54 %29
3035 OpStore %34 %52
3036 OpBranch %35
3037 %37 = OpLabel
3038 OpReturn
3039 OpFunctionEnd
3040 )";
3041
3042 std::unique_ptr<IRContext> context =
3043 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
3044 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
3045 Module* module = context->module();
3046 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
3047 << text << std::endl;
3048 Function& f = *module->begin();
3049
3050 {
3051 LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
3052 EXPECT_EQ(ld.NumLoops(), 2u);
3053
3054 auto loops = ld.GetLoopsInBinaryLayoutOrder();
3055
3056 LoopFusion fusion(context.get(), loops[0], loops[1]);
3057 EXPECT_TRUE(fusion.AreCompatible());
3058 EXPECT_TRUE(fusion.IsLegal());
3059
3060 fusion.Fuse();
3061 }
3062
3063 {
3064 LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
3065 EXPECT_EQ(ld.NumLoops(), 1u);
3066
3067 std::string checks = R"(
3068 CHECK: [[PHI:%\w+]] = OpPhi
3069 CHECK-NEXT: OpLoopMerge
3070 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
3071 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_0]]
3072 CHECK: [[STORE_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
3073 CHECK-NEXT: OpStore [[STORE_0]]
3074 CHECK-NOT: OpPhi
3075 CHECK: [[I_1:%\w+]] = OpIAdd {{%\w+}} [[PHI]] {{%\w+}}
3076 CHECK-NEXT: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[I_1]]
3077 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_1]]
3078 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
3079 CHECK-NEXT: OpStore [[STORE_1]]
3080 )";
3081
3082 Match(checks, context.get());
3083 }
3084 }
3085
3086 /*
3087 Generated from the following GLSL + --eliminate-local-multi-store
3088
3089 #version 440 core
3090 void main() {
3091 int[10][10] a;
3092 int[10][10] b;
3093 int[10][10] c;
3094 // Legal outer. Continue and break are fine if nested in inner loops
3095 for (int i = 0; i < 10; i++) {
3096 for (int j = 0; j < 10; j++) {
3097 if (j % 2 == 0) {
3098 c[i][j] = a[i][j] + 2;
3099 } else {
3100 continue;
3101 }
3102 }
3103 }
3104 for (int i = 0; i < 10; i++) {
3105 for (int j = 0; j < 10; j++) {
3106 if (j % 2 == 0) {
3107 b[i][j] = c[i][j] + 10;
3108 } else {
3109 break;
3110 }
3111 }
3112 }
3113 }
3114
3115 */
TEST_F(FusionLegalTest,OuterloopWithBreakContinueInInner)3116 TEST_F(FusionLegalTest, OuterloopWithBreakContinueInInner) {
3117 std::string text = R"(
3118 OpCapability Shader
3119 %1 = OpExtInstImport "GLSL.std.450"
3120 OpMemoryModel Logical GLSL450
3121 OpEntryPoint Fragment %4 "main"
3122 OpExecutionMode %4 OriginUpperLeft
3123 OpSource GLSL 440
3124 OpName %4 "main"
3125 OpName %8 "i"
3126 OpName %19 "j"
3127 OpName %38 "c"
3128 OpName %41 "a"
3129 OpName %55 "i"
3130 OpName %63 "j"
3131 OpName %76 "b"
3132 %2 = OpTypeVoid
3133 %3 = OpTypeFunction %2
3134 %6 = OpTypeInt 32 1
3135 %7 = OpTypePointer Function %6
3136 %9 = OpConstant %6 0
3137 %16 = OpConstant %6 10
3138 %17 = OpTypeBool
3139 %28 = OpConstant %6 2
3140 %33 = OpTypeInt 32 0
3141 %34 = OpConstant %33 10
3142 %35 = OpTypeArray %6 %34
3143 %36 = OpTypeArray %35 %34
3144 %37 = OpTypePointer Function %36
3145 %51 = OpConstant %6 1
3146 %4 = OpFunction %2 None %3
3147 %5 = OpLabel
3148 %8 = OpVariable %7 Function
3149 %19 = OpVariable %7 Function
3150 %38 = OpVariable %37 Function
3151 %41 = OpVariable %37 Function
3152 %55 = OpVariable %7 Function
3153 %63 = OpVariable %7 Function
3154 %76 = OpVariable %37 Function
3155 OpStore %8 %9
3156 OpBranch %10
3157 %10 = OpLabel
3158 %91 = OpPhi %6 %9 %5 %54 %13
3159 OpLoopMerge %12 %13 None
3160 OpBranch %14
3161 %14 = OpLabel
3162 %18 = OpSLessThan %17 %91 %16
3163 OpBranchConditional %18 %11 %12
3164 %11 = OpLabel
3165 OpStore %19 %9
3166 OpBranch %20
3167 %20 = OpLabel
3168 %96 = OpPhi %6 %9 %11 %52 %23
3169 OpLoopMerge %22 %23 None
3170 OpBranch %24
3171 %24 = OpLabel
3172 %26 = OpSLessThan %17 %96 %16
3173 OpBranchConditional %26 %21 %22
3174 %21 = OpLabel
3175 %29 = OpSMod %6 %96 %28
3176 %30 = OpIEqual %17 %29 %9
3177 OpSelectionMerge %sel_merge None
3178 OpBranchConditional %30 %31 %48
3179 %31 = OpLabel
3180 %44 = OpAccessChain %7 %41 %91 %96
3181 %45 = OpLoad %6 %44
3182 %46 = OpIAdd %6 %45 %28
3183 %47 = OpAccessChain %7 %38 %91 %96
3184 OpStore %47 %46
3185 OpBranch %32
3186 %48 = OpLabel
3187 OpBranch %sel_merge
3188 %32 = OpLabel
3189 OpBranch %sel_merge
3190 %sel_merge = OpLabel
3191 OpBranch %23
3192 %23 = OpLabel
3193 %52 = OpIAdd %6 %96 %51
3194 OpStore %19 %52
3195 OpBranch %20
3196 %22 = OpLabel
3197 OpBranch %13
3198 %13 = OpLabel
3199 %54 = OpIAdd %6 %91 %51
3200 OpStore %8 %54
3201 OpBranch %10
3202 %12 = OpLabel
3203 OpStore %55 %9
3204 OpBranch %56
3205 %56 = OpLabel
3206 %92 = OpPhi %6 %9 %12 %90 %59
3207 OpLoopMerge %58 %59 None
3208 OpBranch %60
3209 %60 = OpLabel
3210 %62 = OpSLessThan %17 %92 %16
3211 OpBranchConditional %62 %57 %58
3212 %57 = OpLabel
3213 OpStore %63 %9
3214 OpBranch %64
3215 %64 = OpLabel
3216 %93 = OpPhi %6 %9 %57 %88 %67
3217 OpLoopMerge %66 %67 None
3218 OpBranch %68
3219 %68 = OpLabel
3220 %70 = OpSLessThan %17 %93 %16
3221 OpBranchConditional %70 %65 %66
3222 %65 = OpLabel
3223 %72 = OpSMod %6 %93 %28
3224 %73 = OpIEqual %17 %72 %9
3225 OpSelectionMerge %75 None
3226 OpBranchConditional %73 %74 %66
3227 %74 = OpLabel
3228 %81 = OpAccessChain %7 %38 %92 %93
3229 %82 = OpLoad %6 %81
3230 %83 = OpIAdd %6 %82 %16
3231 %84 = OpAccessChain %7 %76 %92 %93
3232 OpStore %84 %83
3233 OpBranch %75
3234 %75 = OpLabel
3235 OpBranch %67
3236 %67 = OpLabel
3237 %88 = OpIAdd %6 %93 %51
3238 OpStore %63 %88
3239 OpBranch %64
3240 %66 = OpLabel
3241 OpBranch %59
3242 %59 = OpLabel
3243 %90 = OpIAdd %6 %92 %51
3244 OpStore %55 %90
3245 OpBranch %56
3246 %58 = OpLabel
3247 OpReturn
3248 OpFunctionEnd
3249 )";
3250
3251 std::unique_ptr<IRContext> context =
3252 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
3253 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
3254 Module* module = context->module();
3255 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
3256 << text << std::endl;
3257 Function& f = *module->begin();
3258
3259 {
3260 LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
3261 EXPECT_EQ(ld.NumLoops(), 4u);
3262
3263 auto loops = ld.GetLoopsInBinaryLayoutOrder();
3264
3265 LoopFusion fusion(context.get(), loops[0], loops[2]);
3266 EXPECT_TRUE(fusion.AreCompatible());
3267 EXPECT_TRUE(fusion.IsLegal());
3268
3269 fusion.Fuse();
3270 }
3271
3272 {
3273 LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
3274 EXPECT_EQ(ld.NumLoops(), 3u);
3275
3276 auto loops = ld.GetLoopsInBinaryLayoutOrder();
3277
3278 LoopFusion fusion(context.get(), loops[1], loops[2]);
3279 EXPECT_FALSE(fusion.AreCompatible());
3280
3281 std::string checks = R"(
3282 CHECK: [[PHI_0:%\w+]] = OpPhi
3283 CHECK-NEXT: OpLoopMerge
3284 CHECK: [[PHI_1:%\w+]] = OpPhi
3285 CHECK-NEXT: OpLoopMerge
3286 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] [[PHI_1]]
3287 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_0]]
3288 CHECK: [[STORE_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] [[PHI_1]]
3289 CHECK-NEXT: OpStore [[STORE_0]]
3290 CHECK: [[PHI_2:%\w+]] = OpPhi
3291 CHECK-NEXT: OpLoopMerge
3292 CHECK-NOT: OpPhi
3293 CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] [[PHI_2]]
3294 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_1]]
3295 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] [[PHI_2]]
3296 CHECK-NEXT: OpStore [[STORE_1]]
3297 )";
3298
3299 Match(checks, context.get());
3300 }
3301 }
3302
3303 /*
3304 Generated from the following GLSL + --eliminate-local-multi-store
3305
3306 // j loop preheader removed manually
3307 #version 440 core
3308 void main() {
3309 int[10] a;
3310 int[10] b;
3311 int i = 0;
3312 int j = 0;
3313 // No loop-carried dependences, legal
3314 for (; i < 10; i++) {
3315 a[i] = a[i]*2;
3316 }
3317 for (; j < 10; j++) {
3318 b[j] = a[j]+2;
3319 }
3320 }
3321
3322 */
TEST_F(FusionLegalTest,DifferentArraysInLoopsNoPreheader)3323 TEST_F(FusionLegalTest, DifferentArraysInLoopsNoPreheader) {
3324 std::string text = R"(
3325 OpCapability Shader
3326 %1 = OpExtInstImport "GLSL.std.450"
3327 OpMemoryModel Logical GLSL450
3328 OpEntryPoint Fragment %4 "main"
3329 OpExecutionMode %4 OriginUpperLeft
3330 OpSource GLSL 440
3331 OpName %4 "main"
3332 OpName %8 "i"
3333 OpName %10 "j"
3334 OpName %24 "a"
3335 OpName %42 "b"
3336 %2 = OpTypeVoid
3337 %3 = OpTypeFunction %2
3338 %6 = OpTypeInt 32 1
3339 %7 = OpTypePointer Function %6
3340 %9 = OpConstant %6 0
3341 %17 = OpConstant %6 10
3342 %18 = OpTypeBool
3343 %20 = OpTypeInt 32 0
3344 %21 = OpConstant %20 10
3345 %22 = OpTypeArray %6 %21
3346 %23 = OpTypePointer Function %22
3347 %29 = OpConstant %6 2
3348 %33 = OpConstant %6 1
3349 %4 = OpFunction %2 None %3
3350 %5 = OpLabel
3351 %8 = OpVariable %7 Function
3352 %10 = OpVariable %7 Function
3353 %24 = OpVariable %23 Function
3354 %42 = OpVariable %23 Function
3355 OpStore %8 %9
3356 OpStore %10 %9
3357 OpBranch %11
3358 %11 = OpLabel
3359 %51 = OpPhi %6 %9 %5 %34 %14
3360 OpLoopMerge %35 %14 None
3361 OpBranch %15
3362 %15 = OpLabel
3363 %19 = OpSLessThan %18 %51 %17
3364 OpBranchConditional %19 %12 %35
3365 %12 = OpLabel
3366 %27 = OpAccessChain %7 %24 %51
3367 %28 = OpLoad %6 %27
3368 %30 = OpIMul %6 %28 %29
3369 %31 = OpAccessChain %7 %24 %51
3370 OpStore %31 %30
3371 OpBranch %14
3372 %14 = OpLabel
3373 %34 = OpIAdd %6 %51 %33
3374 OpStore %8 %34
3375 OpBranch %11
3376 %35 = OpLabel
3377 %52 = OpPhi %6 %9 %15 %50 %38
3378 OpLoopMerge %37 %38 None
3379 OpBranch %39
3380 %39 = OpLabel
3381 %41 = OpSLessThan %18 %52 %17
3382 OpBranchConditional %41 %36 %37
3383 %36 = OpLabel
3384 %45 = OpAccessChain %7 %24 %52
3385 %46 = OpLoad %6 %45
3386 %47 = OpIAdd %6 %46 %29
3387 %48 = OpAccessChain %7 %42 %52
3388 OpStore %48 %47
3389 OpBranch %38
3390 %38 = OpLabel
3391 %50 = OpIAdd %6 %52 %33
3392 OpStore %10 %50
3393 OpBranch %35
3394 %37 = OpLabel
3395 OpReturn
3396 OpFunctionEnd
3397 )";
3398
3399 std::unique_ptr<IRContext> context =
3400 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
3401 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
3402 Module* module = context->module();
3403 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
3404 << text << std::endl;
3405 Function& f = *module->begin();
3406
3407 {
3408 LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
3409 EXPECT_EQ(ld.NumLoops(), 2u);
3410
3411 auto loops = ld.GetLoopsInBinaryLayoutOrder();
3412
3413 {
3414 LoopFusion fusion(context.get(), loops[0], loops[1]);
3415 EXPECT_FALSE(fusion.AreCompatible());
3416 }
3417
3418 ld.CreatePreHeaderBlocksIfMissing();
3419
3420 {
3421 LoopFusion fusion(context.get(), loops[0], loops[1]);
3422 EXPECT_TRUE(fusion.AreCompatible());
3423 EXPECT_TRUE(fusion.IsLegal());
3424
3425 fusion.Fuse();
3426 }
3427 }
3428
3429 {
3430 LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
3431 EXPECT_EQ(ld.NumLoops(), 1u);
3432
3433 std::string checks = R"(
3434 CHECK: [[PHI:%\w+]] = OpPhi
3435 CHECK-NEXT: OpLoopMerge
3436 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
3437 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_0]]
3438 CHECK: [[STORE_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
3439 CHECK-NEXT: OpStore [[STORE_0]]
3440 CHECK-NOT: OpPhi
3441 CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
3442 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_1]]
3443 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
3444 CHECK-NEXT: OpStore [[STORE_1]]
3445 )";
3446
3447 Match(checks, context.get());
3448 }
3449 }
3450
3451 /*
3452 Generated from the following GLSL + --eliminate-local-multi-store
3453
3454 // j & k loop preheaders removed manually
3455 #version 440 core
3456 void main() {
3457 int[10] a;
3458 int[10] b;
3459 int i = 0;
3460 int j = 0;
3461 int k = 0;
3462 // No loop-carried dependences, legal
3463 for (; i < 10; i++) {
3464 a[i] = a[i]*2;
3465 }
3466 for (; j < 10; j++) {
3467 b[j] = a[j]+2;
3468 }
3469 for (; k < 10; k++) {
3470 a[k] = a[k]*2;
3471 }
3472 }
3473
3474 */
TEST_F(FusionLegalTest,AdjacentLoopsNoPreheaders)3475 TEST_F(FusionLegalTest, AdjacentLoopsNoPreheaders) {
3476 std::string text = R"(
3477 OpCapability Shader
3478 %1 = OpExtInstImport "GLSL.std.450"
3479 OpMemoryModel Logical GLSL450
3480 OpEntryPoint Fragment %4 "main"
3481 OpExecutionMode %4 OriginUpperLeft
3482 OpSource GLSL 440
3483 OpName %4 "main"
3484 OpName %8 "i"
3485 OpName %10 "j"
3486 OpName %11 "k"
3487 OpName %25 "a"
3488 OpName %43 "b"
3489 %2 = OpTypeVoid
3490 %3 = OpTypeFunction %2
3491 %6 = OpTypeInt 32 1
3492 %7 = OpTypePointer Function %6
3493 %9 = OpConstant %6 0
3494 %18 = OpConstant %6 10
3495 %19 = OpTypeBool
3496 %21 = OpTypeInt 32 0
3497 %22 = OpConstant %21 10
3498 %23 = OpTypeArray %6 %22
3499 %24 = OpTypePointer Function %23
3500 %30 = OpConstant %6 2
3501 %34 = OpConstant %6 1
3502 %4 = OpFunction %2 None %3
3503 %5 = OpLabel
3504 %8 = OpVariable %7 Function
3505 %10 = OpVariable %7 Function
3506 %11 = OpVariable %7 Function
3507 %25 = OpVariable %24 Function
3508 %43 = OpVariable %24 Function
3509 OpStore %8 %9
3510 OpStore %10 %9
3511 OpStore %11 %9
3512 OpBranch %12
3513 %12 = OpLabel
3514 %67 = OpPhi %6 %9 %5 %35 %15
3515 OpLoopMerge %36 %15 None
3516 OpBranch %16
3517 %16 = OpLabel
3518 %20 = OpSLessThan %19 %67 %18
3519 OpBranchConditional %20 %13 %36
3520 %13 = OpLabel
3521 %28 = OpAccessChain %7 %25 %67
3522 %29 = OpLoad %6 %28
3523 %31 = OpIMul %6 %29 %30
3524 %32 = OpAccessChain %7 %25 %67
3525 OpStore %32 %31
3526 OpBranch %15
3527 %15 = OpLabel
3528 %35 = OpIAdd %6 %67 %34
3529 OpStore %8 %35
3530 OpBranch %12
3531 %36 = OpLabel
3532 %68 = OpPhi %6 %9 %16 %51 %39
3533 OpLoopMerge %52 %39 None
3534 OpBranch %40
3535 %40 = OpLabel
3536 %42 = OpSLessThan %19 %68 %18
3537 OpBranchConditional %42 %37 %52
3538 %37 = OpLabel
3539 %46 = OpAccessChain %7 %25 %68
3540 %47 = OpLoad %6 %46
3541 %48 = OpIAdd %6 %47 %30
3542 %49 = OpAccessChain %7 %43 %68
3543 OpStore %49 %48
3544 OpBranch %39
3545 %39 = OpLabel
3546 %51 = OpIAdd %6 %68 %34
3547 OpStore %10 %51
3548 OpBranch %36
3549 %52 = OpLabel
3550 %70 = OpPhi %6 %9 %40 %66 %55
3551 OpLoopMerge %54 %55 None
3552 OpBranch %56
3553 %56 = OpLabel
3554 %58 = OpSLessThan %19 %70 %18
3555 OpBranchConditional %58 %53 %54
3556 %53 = OpLabel
3557 %61 = OpAccessChain %7 %25 %70
3558 %62 = OpLoad %6 %61
3559 %63 = OpIMul %6 %62 %30
3560 %64 = OpAccessChain %7 %25 %70
3561 OpStore %64 %63
3562 OpBranch %55
3563 %55 = OpLabel
3564 %66 = OpIAdd %6 %70 %34
3565 OpStore %11 %66
3566 OpBranch %52
3567 %54 = OpLabel
3568 OpReturn
3569 OpFunctionEnd
3570 )";
3571
3572 std::unique_ptr<IRContext> context =
3573 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
3574 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
3575 Module* module = context->module();
3576 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
3577 << text << std::endl;
3578 Function& f = *module->begin();
3579
3580 {
3581 LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
3582 EXPECT_EQ(ld.NumLoops(), 3u);
3583
3584 auto loops = ld.GetLoopsInBinaryLayoutOrder();
3585
3586 {
3587 LoopFusion fusion(context.get(), loops[0], loops[1]);
3588 EXPECT_FALSE(fusion.AreCompatible());
3589 }
3590
3591 ld.CreatePreHeaderBlocksIfMissing();
3592
3593 {
3594 LoopFusion fusion(context.get(), loops[0], loops[1]);
3595 EXPECT_TRUE(fusion.AreCompatible());
3596 EXPECT_TRUE(fusion.IsLegal());
3597
3598 fusion.Fuse();
3599 }
3600 }
3601
3602 {
3603 LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
3604 EXPECT_EQ(ld.NumLoops(), 2u);
3605
3606 std::string checks = R"(
3607 CHECK: [[PHI_0:%\w+]] = OpPhi
3608 CHECK-NEXT: OpLoopMerge
3609 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]]
3610 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_0]]
3611 CHECK: [[STORE_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]]
3612 CHECK-NEXT: OpStore [[STORE_0]]
3613 CHECK-NOT: OpPhi
3614 CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]]
3615 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_1]]
3616 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]]
3617 CHECK-NEXT: OpStore [[STORE_1]]
3618 CHECK: [[PHI_1:%\w+]] = OpPhi
3619 CHECK-NEXT: OpLoopMerge
3620 CHECK: [[LOAD_2:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_1]]
3621 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_2]]
3622 CHECK: [[STORE_2:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_1]]
3623 CHECK-NEXT: OpStore [[STORE_2]]
3624 )";
3625
3626 Match(checks, context.get());
3627
3628 auto loops = ld.GetLoopsInBinaryLayoutOrder();
3629
3630 LoopFusion fusion(context.get(), loops[0], loops[1]);
3631 EXPECT_TRUE(fusion.AreCompatible());
3632 EXPECT_TRUE(fusion.IsLegal());
3633
3634 fusion.Fuse();
3635 }
3636
3637 {
3638 LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
3639 EXPECT_EQ(ld.NumLoops(), 1u);
3640
3641 std::string checks = R"(
3642 CHECK: [[PHI:%\w+]] = OpPhi
3643 CHECK-NEXT: OpLoopMerge
3644 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
3645 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_0]]
3646 CHECK: [[STORE_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
3647 CHECK-NEXT: OpStore [[STORE_0]]
3648 CHECK-NOT: OpPhi
3649 CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
3650 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_1]]
3651 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
3652 CHECK-NEXT: OpStore [[STORE_1]]
3653 CHECK-NOT: OpPhi
3654 CHECK: [[LOAD_2:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
3655 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_2]]
3656 CHECK: [[STORE_2:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
3657 CHECK-NEXT: OpStore [[STORE_2]]
3658 )";
3659
3660 Match(checks, context.get());
3661 }
3662 }
3663
3664 /*
3665 Generated from the following GLSL + --eliminate-local-multi-store
3666
3667 #version 440 core
3668 void main() {
3669 int[10] a;
3670 int[10] b;
3671
3672 int sum_0 = 0;
3673 int sum_1 = 0;
3674
3675 // No loop-carried dependences, legal
3676 for (int i = 0; i < 10; i++) {
3677 sum_0 += a[i];
3678 }
3679 for (int j = 0; j < 10; j++) {
3680 sum_1 += b[j];
3681 }
3682
3683 int total = sum_0 + sum_1;
3684 }
3685
3686 */
TEST_F(FusionLegalTest,IndependentReductions)3687 TEST_F(FusionLegalTest, IndependentReductions) {
3688 std::string text = R"(
3689 OpCapability Shader
3690 %1 = OpExtInstImport "GLSL.std.450"
3691 OpMemoryModel Logical GLSL450
3692 OpEntryPoint Fragment %4 "main"
3693 OpExecutionMode %4 OriginUpperLeft
3694 OpSource GLSL 440
3695 OpName %4 "main"
3696 OpName %8 "sum_0"
3697 OpName %10 "sum_1"
3698 OpName %11 "i"
3699 OpName %25 "a"
3700 OpName %34 "j"
3701 OpName %42 "b"
3702 OpName %50 "total"
3703 %2 = OpTypeVoid
3704 %3 = OpTypeFunction %2
3705 %6 = OpTypeInt 32 1
3706 %7 = OpTypePointer Function %6
3707 %9 = OpConstant %6 0
3708 %18 = OpConstant %6 10
3709 %19 = OpTypeBool
3710 %21 = OpTypeInt 32 0
3711 %22 = OpConstant %21 10
3712 %23 = OpTypeArray %6 %22
3713 %24 = OpTypePointer Function %23
3714 %32 = OpConstant %6 1
3715 %4 = OpFunction %2 None %3
3716 %5 = OpLabel
3717 %8 = OpVariable %7 Function
3718 %10 = OpVariable %7 Function
3719 %11 = OpVariable %7 Function
3720 %25 = OpVariable %24 Function
3721 %34 = OpVariable %7 Function
3722 %42 = OpVariable %24 Function
3723 %50 = OpVariable %7 Function
3724 OpStore %8 %9
3725 OpStore %10 %9
3726 OpStore %11 %9
3727 OpBranch %12
3728 %12 = OpLabel
3729 %57 = OpPhi %6 %9 %5 %30 %15
3730 %54 = OpPhi %6 %9 %5 %33 %15
3731 OpLoopMerge %14 %15 None
3732 OpBranch %16
3733 %16 = OpLabel
3734 %20 = OpSLessThan %19 %54 %18
3735 OpBranchConditional %20 %13 %14
3736 %13 = OpLabel
3737 %27 = OpAccessChain %7 %25 %54
3738 %28 = OpLoad %6 %27
3739 %30 = OpIAdd %6 %57 %28
3740 OpStore %8 %30
3741 OpBranch %15
3742 %15 = OpLabel
3743 %33 = OpIAdd %6 %54 %32
3744 OpStore %11 %33
3745 OpBranch %12
3746 %14 = OpLabel
3747 OpStore %34 %9
3748 OpBranch %35
3749 %35 = OpLabel
3750 %58 = OpPhi %6 %9 %14 %47 %38
3751 %55 = OpPhi %6 %9 %14 %49 %38
3752 OpLoopMerge %37 %38 None
3753 OpBranch %39
3754 %39 = OpLabel
3755 %41 = OpSLessThan %19 %55 %18
3756 OpBranchConditional %41 %36 %37
3757 %36 = OpLabel
3758 %44 = OpAccessChain %7 %42 %55
3759 %45 = OpLoad %6 %44
3760 %47 = OpIAdd %6 %58 %45
3761 OpStore %10 %47
3762 OpBranch %38
3763 %38 = OpLabel
3764 %49 = OpIAdd %6 %55 %32
3765 OpStore %34 %49
3766 OpBranch %35
3767 %37 = OpLabel
3768 %53 = OpIAdd %6 %57 %58
3769 OpStore %50 %53
3770 OpReturn
3771 OpFunctionEnd
3772 )";
3773
3774 std::unique_ptr<IRContext> context =
3775 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
3776 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
3777 Module* module = context->module();
3778 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
3779 << text << std::endl;
3780 Function& f = *module->begin();
3781
3782 {
3783 LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
3784 EXPECT_EQ(ld.NumLoops(), 2u);
3785
3786 auto loops = ld.GetLoopsInBinaryLayoutOrder();
3787
3788 LoopFusion fusion(context.get(), loops[0], loops[1]);
3789 EXPECT_TRUE(fusion.AreCompatible());
3790 EXPECT_TRUE(fusion.IsLegal());
3791
3792 fusion.Fuse();
3793 }
3794
3795 {
3796 LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
3797 EXPECT_EQ(ld.NumLoops(), 1u);
3798
3799 std::string checks = R"(
3800 CHECK: [[SUM_0:%\w+]] = OpPhi
3801 CHECK-NEXT: [[SUM_1:%\w+]] = OpPhi
3802 CHECK-NEXT: [[PHI:%\w+]] = OpPhi
3803 CHECK-NEXT: OpLoopMerge
3804 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
3805 CHECK-NEXT: [[LOAD_RES_0:%\w+]] = OpLoad {{%\w+}} [[LOAD_0]]
3806 CHECK-NEXT: [[ADD_RES_0:%\w+]] = OpIAdd {{%\w+}} [[SUM_0]] [[LOAD_RES_0]]
3807 CHECK-NEXT: OpStore {{%\w+}} [[ADD_RES_0]]
3808 CHECK-NOT: OpPhi
3809 CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
3810 CHECK-NEXT: [[LOAD_RES_1:%\w+]] = OpLoad {{%\w+}} [[LOAD_1]]
3811 CHECK-NEXT: [[ADD_RES_1:%\w+]] = OpIAdd {{%\w+}} [[SUM_1]] [[LOAD_RES_1]]
3812 CHECK-NEXT: OpStore {{%\w+}} [[ADD_RES_1]]
3813 )";
3814
3815 Match(checks, context.get());
3816 }
3817 }
3818
3819 /*
3820 Generated from the following GLSL + --eliminate-local-multi-store
3821
3822 #version 440 core
3823 void main() {
3824 int[10] a;
3825 int[10] b;
3826
3827 int sum_0 = 0;
3828 int sum_1 = 0;
3829
3830 // No loop-carried dependences, legal
3831 for (int i = 0; i < 10; i++) {
3832 sum_0 += a[i];
3833 }
3834 for (int j = 0; j < 10; j++) {
3835 sum_1 += b[j];
3836 }
3837
3838 int total = sum_0 + sum_1;
3839 }
3840
3841 */
TEST_F(FusionLegalTest,IndependentReductionsOneLCSSA)3842 TEST_F(FusionLegalTest, IndependentReductionsOneLCSSA) {
3843 std::string text = R"(
3844 OpCapability Shader
3845 %1 = OpExtInstImport "GLSL.std.450"
3846 OpMemoryModel Logical GLSL450
3847 OpEntryPoint Fragment %4 "main"
3848 OpExecutionMode %4 OriginUpperLeft
3849 OpSource GLSL 440
3850 OpName %4 "main"
3851 OpName %8 "sum_0"
3852 OpName %10 "sum_1"
3853 OpName %11 "i"
3854 OpName %25 "a"
3855 OpName %34 "j"
3856 OpName %42 "b"
3857 OpName %50 "total"
3858 %2 = OpTypeVoid
3859 %3 = OpTypeFunction %2
3860 %6 = OpTypeInt 32 1
3861 %7 = OpTypePointer Function %6
3862 %9 = OpConstant %6 0
3863 %18 = OpConstant %6 10
3864 %19 = OpTypeBool
3865 %21 = OpTypeInt 32 0
3866 %22 = OpConstant %21 10
3867 %23 = OpTypeArray %6 %22
3868 %24 = OpTypePointer Function %23
3869 %32 = OpConstant %6 1
3870 %4 = OpFunction %2 None %3
3871 %5 = OpLabel
3872 %8 = OpVariable %7 Function
3873 %10 = OpVariable %7 Function
3874 %11 = OpVariable %7 Function
3875 %25 = OpVariable %24 Function
3876 %34 = OpVariable %7 Function
3877 %42 = OpVariable %24 Function
3878 %50 = OpVariable %7 Function
3879 OpStore %8 %9
3880 OpStore %10 %9
3881 OpStore %11 %9
3882 OpBranch %12
3883 %12 = OpLabel
3884 %57 = OpPhi %6 %9 %5 %30 %15
3885 %54 = OpPhi %6 %9 %5 %33 %15
3886 OpLoopMerge %14 %15 None
3887 OpBranch %16
3888 %16 = OpLabel
3889 %20 = OpSLessThan %19 %54 %18
3890 OpBranchConditional %20 %13 %14
3891 %13 = OpLabel
3892 %27 = OpAccessChain %7 %25 %54
3893 %28 = OpLoad %6 %27
3894 %30 = OpIAdd %6 %57 %28
3895 OpStore %8 %30
3896 OpBranch %15
3897 %15 = OpLabel
3898 %33 = OpIAdd %6 %54 %32
3899 OpStore %11 %33
3900 OpBranch %12
3901 %14 = OpLabel
3902 OpStore %34 %9
3903 OpBranch %35
3904 %35 = OpLabel
3905 %58 = OpPhi %6 %9 %14 %47 %38
3906 %55 = OpPhi %6 %9 %14 %49 %38
3907 OpLoopMerge %37 %38 None
3908 OpBranch %39
3909 %39 = OpLabel
3910 %41 = OpSLessThan %19 %55 %18
3911 OpBranchConditional %41 %36 %37
3912 %36 = OpLabel
3913 %44 = OpAccessChain %7 %42 %55
3914 %45 = OpLoad %6 %44
3915 %47 = OpIAdd %6 %58 %45
3916 OpStore %10 %47
3917 OpBranch %38
3918 %38 = OpLabel
3919 %49 = OpIAdd %6 %55 %32
3920 OpStore %34 %49
3921 OpBranch %35
3922 %37 = OpLabel
3923 %53 = OpIAdd %6 %57 %58
3924 OpStore %50 %53
3925 OpReturn
3926 OpFunctionEnd
3927 )";
3928
3929 std::unique_ptr<IRContext> context =
3930 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
3931 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
3932 Module* module = context->module();
3933 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
3934 << text << std::endl;
3935 Function& f = *module->begin();
3936
3937 {
3938 LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
3939 EXPECT_EQ(ld.NumLoops(), 2u);
3940
3941 auto loops = ld.GetLoopsInBinaryLayoutOrder();
3942
3943 LoopUtils utils_0(context.get(), loops[0]);
3944 utils_0.MakeLoopClosedSSA();
3945
3946 LoopFusion fusion(context.get(), loops[0], loops[1]);
3947 EXPECT_TRUE(fusion.AreCompatible());
3948 EXPECT_TRUE(fusion.IsLegal());
3949
3950 fusion.Fuse();
3951 }
3952
3953 {
3954 LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
3955 EXPECT_EQ(ld.NumLoops(), 1u);
3956
3957 std::string checks = R"(
3958 CHECK: [[SUM_0:%\w+]] = OpPhi
3959 CHECK-NEXT: [[SUM_1:%\w+]] = OpPhi
3960 CHECK-NEXT: [[PHI:%\w+]] = OpPhi
3961 CHECK-NEXT: OpLoopMerge
3962 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
3963 CHECK-NEXT: [[LOAD_RES_0:%\w+]] = OpLoad {{%\w+}} [[LOAD_0]]
3964 CHECK-NEXT: [[ADD_RES_0:%\w+]] = OpIAdd {{%\w+}} [[SUM_0]] [[LOAD_RES_0]]
3965 CHECK-NEXT: OpStore {{%\w+}} [[ADD_RES_0]]
3966 CHECK-NOT: OpPhi
3967 CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
3968 CHECK-NEXT: [[LOAD_RES_1:%\w+]] = OpLoad {{%\w+}} [[LOAD_1]]
3969 CHECK-NEXT: [[ADD_RES_1:%\w+]] = OpIAdd {{%\w+}} [[SUM_1]] [[LOAD_RES_1]]
3970 CHECK-NEXT: OpStore {{%\w+}} [[ADD_RES_1]]
3971 )";
3972
3973 Match(checks, context.get());
3974 }
3975 }
3976
3977 /*
3978 Generated from the following GLSL + --eliminate-local-multi-store
3979
3980 #version 440 core
3981 void main() {
3982 int[10] a;
3983 int[10] b;
3984
3985 int sum_0 = 0;
3986 int sum_1 = 0;
3987
3988 // No loop-carried dependences, legal
3989 for (int i = 0; i < 10; i++) {
3990 sum_0 += a[i];
3991 }
3992 for (int j = 0; j < 10; j++) {
3993 sum_1 += b[j];
3994 }
3995
3996 int total = sum_0 + sum_1;
3997 }
3998
3999 */
TEST_F(FusionLegalTest,IndependentReductionsBothLCSSA)4000 TEST_F(FusionLegalTest, IndependentReductionsBothLCSSA) {
4001 std::string text = R"(
4002 OpCapability Shader
4003 %1 = OpExtInstImport "GLSL.std.450"
4004 OpMemoryModel Logical GLSL450
4005 OpEntryPoint Fragment %4 "main"
4006 OpExecutionMode %4 OriginUpperLeft
4007 OpSource GLSL 440
4008 OpName %4 "main"
4009 OpName %8 "sum_0"
4010 OpName %10 "sum_1"
4011 OpName %11 "i"
4012 OpName %25 "a"
4013 OpName %34 "j"
4014 OpName %42 "b"
4015 OpName %50 "total"
4016 %2 = OpTypeVoid
4017 %3 = OpTypeFunction %2
4018 %6 = OpTypeInt 32 1
4019 %7 = OpTypePointer Function %6
4020 %9 = OpConstant %6 0
4021 %18 = OpConstant %6 10
4022 %19 = OpTypeBool
4023 %21 = OpTypeInt 32 0
4024 %22 = OpConstant %21 10
4025 %23 = OpTypeArray %6 %22
4026 %24 = OpTypePointer Function %23
4027 %32 = OpConstant %6 1
4028 %4 = OpFunction %2 None %3
4029 %5 = OpLabel
4030 %8 = OpVariable %7 Function
4031 %10 = OpVariable %7 Function
4032 %11 = OpVariable %7 Function
4033 %25 = OpVariable %24 Function
4034 %34 = OpVariable %7 Function
4035 %42 = OpVariable %24 Function
4036 %50 = OpVariable %7 Function
4037 OpStore %8 %9
4038 OpStore %10 %9
4039 OpStore %11 %9
4040 OpBranch %12
4041 %12 = OpLabel
4042 %57 = OpPhi %6 %9 %5 %30 %15
4043 %54 = OpPhi %6 %9 %5 %33 %15
4044 OpLoopMerge %14 %15 None
4045 OpBranch %16
4046 %16 = OpLabel
4047 %20 = OpSLessThan %19 %54 %18
4048 OpBranchConditional %20 %13 %14
4049 %13 = OpLabel
4050 %27 = OpAccessChain %7 %25 %54
4051 %28 = OpLoad %6 %27
4052 %30 = OpIAdd %6 %57 %28
4053 OpStore %8 %30
4054 OpBranch %15
4055 %15 = OpLabel
4056 %33 = OpIAdd %6 %54 %32
4057 OpStore %11 %33
4058 OpBranch %12
4059 %14 = OpLabel
4060 OpStore %34 %9
4061 OpBranch %35
4062 %35 = OpLabel
4063 %58 = OpPhi %6 %9 %14 %47 %38
4064 %55 = OpPhi %6 %9 %14 %49 %38
4065 OpLoopMerge %37 %38 None
4066 OpBranch %39
4067 %39 = OpLabel
4068 %41 = OpSLessThan %19 %55 %18
4069 OpBranchConditional %41 %36 %37
4070 %36 = OpLabel
4071 %44 = OpAccessChain %7 %42 %55
4072 %45 = OpLoad %6 %44
4073 %47 = OpIAdd %6 %58 %45
4074 OpStore %10 %47
4075 OpBranch %38
4076 %38 = OpLabel
4077 %49 = OpIAdd %6 %55 %32
4078 OpStore %34 %49
4079 OpBranch %35
4080 %37 = OpLabel
4081 %53 = OpIAdd %6 %57 %58
4082 OpStore %50 %53
4083 OpReturn
4084 OpFunctionEnd
4085 )";
4086
4087 std::unique_ptr<IRContext> context =
4088 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
4089 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
4090 Module* module = context->module();
4091 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
4092 << text << std::endl;
4093 Function& f = *module->begin();
4094
4095 {
4096 LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
4097 EXPECT_EQ(ld.NumLoops(), 2u);
4098
4099 auto loops = ld.GetLoopsInBinaryLayoutOrder();
4100
4101 LoopUtils utils_0(context.get(), loops[0]);
4102 utils_0.MakeLoopClosedSSA();
4103 LoopUtils utils_1(context.get(), loops[1]);
4104 utils_1.MakeLoopClosedSSA();
4105
4106 LoopFusion fusion(context.get(), loops[0], loops[1]);
4107 EXPECT_TRUE(fusion.AreCompatible());
4108 EXPECT_TRUE(fusion.IsLegal());
4109
4110 fusion.Fuse();
4111 }
4112
4113 {
4114 LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
4115 EXPECT_EQ(ld.NumLoops(), 1u);
4116
4117 std::string checks = R"(
4118 CHECK: [[SUM_0:%\w+]] = OpPhi
4119 CHECK-NEXT: [[SUM_1:%\w+]] = OpPhi
4120 CHECK-NEXT: [[PHI:%\w+]] = OpPhi
4121 CHECK-NEXT: OpLoopMerge
4122 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
4123 CHECK-NEXT: [[LOAD_RES_0:%\w+]] = OpLoad {{%\w+}} [[LOAD_0]]
4124 CHECK-NEXT: [[ADD_RES_0:%\w+]] = OpIAdd {{%\w+}} [[SUM_0]] [[LOAD_RES_0]]
4125 CHECK-NEXT: OpStore {{%\w+}} [[ADD_RES_0]]
4126 CHECK-NOT: OpPhi
4127 CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
4128 CHECK-NEXT: [[LOAD_RES_1:%\w+]] = OpLoad {{%\w+}} [[LOAD_1]]
4129 CHECK-NEXT: [[ADD_RES_1:%\w+]] = OpIAdd {{%\w+}} [[SUM_1]] [[LOAD_RES_1]]
4130 CHECK-NEXT: OpStore {{%\w+}} [[ADD_RES_1]]
4131 )";
4132
4133 Match(checks, context.get());
4134 }
4135 }
4136
4137 /*
4138 Generated from the following GLSL + --eliminate-local-multi-store
4139
4140 #version 440 core
4141 void main() {
4142 int[10] a;
4143 int[10] b;
4144
4145 int sum_0 = 0;
4146
4147 // No loop-carried dependences, legal
4148 for (int i = 0; i < 10; i++) {
4149 sum_0 += a[i];
4150 }
4151 for (int j = 0; j < 10; j++) {
4152 a[j] = b[j];
4153 }
4154 }
4155
4156 */
TEST_F(FusionLegalTest,LoadStoreReductionAndNonLoopCarriedDependence)4157 TEST_F(FusionLegalTest, LoadStoreReductionAndNonLoopCarriedDependence) {
4158 std::string text = R"(
4159 OpCapability Shader
4160 %1 = OpExtInstImport "GLSL.std.450"
4161 OpMemoryModel Logical GLSL450
4162 OpEntryPoint Fragment %4 "main"
4163 OpExecutionMode %4 OriginUpperLeft
4164 OpSource GLSL 440
4165 OpName %4 "main"
4166 OpName %8 "sum_0"
4167 OpName %10 "i"
4168 OpName %24 "a"
4169 OpName %33 "j"
4170 OpName %42 "b"
4171 %2 = OpTypeVoid
4172 %3 = OpTypeFunction %2
4173 %6 = OpTypeInt 32 1
4174 %7 = OpTypePointer Function %6
4175 %9 = OpConstant %6 0
4176 %17 = OpConstant %6 10
4177 %18 = OpTypeBool
4178 %20 = OpTypeInt 32 0
4179 %21 = OpConstant %20 10
4180 %22 = OpTypeArray %6 %21
4181 %23 = OpTypePointer Function %22
4182 %31 = OpConstant %6 1
4183 %4 = OpFunction %2 None %3
4184 %5 = OpLabel
4185 %8 = OpVariable %7 Function
4186 %10 = OpVariable %7 Function
4187 %24 = OpVariable %23 Function
4188 %33 = OpVariable %7 Function
4189 %42 = OpVariable %23 Function
4190 OpStore %8 %9
4191 OpStore %10 %9
4192 OpBranch %11
4193 %11 = OpLabel
4194 %51 = OpPhi %6 %9 %5 %29 %14
4195 %49 = OpPhi %6 %9 %5 %32 %14
4196 OpLoopMerge %13 %14 None
4197 OpBranch %15
4198 %15 = OpLabel
4199 %19 = OpSLessThan %18 %49 %17
4200 OpBranchConditional %19 %12 %13
4201 %12 = OpLabel
4202 %26 = OpAccessChain %7 %24 %49
4203 %27 = OpLoad %6 %26
4204 %29 = OpIAdd %6 %51 %27
4205 OpStore %8 %29
4206 OpBranch %14
4207 %14 = OpLabel
4208 %32 = OpIAdd %6 %49 %31
4209 OpStore %10 %32
4210 OpBranch %11
4211 %13 = OpLabel
4212 OpStore %33 %9
4213 OpBranch %34
4214 %34 = OpLabel
4215 %50 = OpPhi %6 %9 %13 %48 %37
4216 OpLoopMerge %36 %37 None
4217 OpBranch %38
4218 %38 = OpLabel
4219 %40 = OpSLessThan %18 %50 %17
4220 OpBranchConditional %40 %35 %36
4221 %35 = OpLabel
4222 %44 = OpAccessChain %7 %42 %50
4223 %45 = OpLoad %6 %44
4224 %46 = OpAccessChain %7 %24 %50
4225 OpStore %46 %45
4226 OpBranch %37
4227 %37 = OpLabel
4228 %48 = OpIAdd %6 %50 %31
4229 OpStore %33 %48
4230 OpBranch %34
4231 %36 = OpLabel
4232 OpReturn
4233 OpFunctionEnd
4234 )";
4235
4236 std::unique_ptr<IRContext> context =
4237 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
4238 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
4239 Module* module = context->module();
4240 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
4241 << text << std::endl;
4242 Function& f = *module->begin();
4243
4244 {
4245 LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
4246 EXPECT_EQ(ld.NumLoops(), 2u);
4247
4248 auto loops = ld.GetLoopsInBinaryLayoutOrder();
4249
4250 LoopFusion fusion(context.get(), loops[0], loops[1]);
4251 EXPECT_TRUE(fusion.AreCompatible());
4252 // TODO: Loop descriptor doesn't return induction variables but all OpPhi
4253 // in the header and LoopDependenceAnalysis falls over.
4254 // EXPECT_TRUE(fusion.IsLegal());
4255
4256 // fusion.Fuse();
4257 }
4258
4259 {
4260 // LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
4261 // EXPECT_EQ(ld.NumLoops(), 1u);
4262
4263 // std::string checks = R"(
4264 // CHECK: [[SUM_0:%\w+]] = OpPhi
4265 // CHECK-NEXT: [[PHI:%\w+]] = OpPhi
4266 // CHECK-NEXT: OpLoopMerge
4267 // CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
4268 // CHECK-NEXT: [[LOAD_RES_0:%\w+]] = OpLoad {{%\w+}} [[LOAD_0]]
4269 // CHECK-NEXT: [[ADD_RES_0:%\w+]] = OpIAdd {{%\w+}} [[SUM_0]] [[LOAD_RES_0]]
4270 // CHECK-NEXT: OpStore {{%\w+}} [[ADD_RES_0]]
4271 // CHECK-NOT: OpPhi
4272 // CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
4273 // CHECK-NEXT: [[LOAD_RES_1:%\w+]] = OpLoad {{%\w+}} [[LOAD_1]]
4274 // CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
4275 // CHECK-NEXT: OpStore [[STORE_1]] [[LOAD_RES_1]]
4276 // )";
4277
4278 // Match(checks, context.get());
4279 }
4280 }
4281
4282 /*
4283 Generated from the following GLSL + --eliminate-local-multi-store
4284
4285 #version 440 core
4286 int x;
4287 void main() {
4288 int[10] a;
4289 int[10] b;
4290
4291 // Legal.
4292 for (int i = 0; i < 10; i++) {
4293 x += a[i];
4294 }
4295 for (int j = 0; j < 10; j++) {
4296 b[j] = b[j]+1;
4297 }
4298 }
4299
4300 */
TEST_F(FusionLegalTest,ReductionAndNonLoopCarriedDependence)4301 TEST_F(FusionLegalTest, ReductionAndNonLoopCarriedDependence) {
4302 std::string text = R"(
4303 OpCapability Shader
4304 %1 = OpExtInstImport "GLSL.std.450"
4305 OpMemoryModel Logical GLSL450
4306 OpEntryPoint Fragment %4 "main"
4307 OpExecutionMode %4 OriginUpperLeft
4308 OpSource GLSL 440
4309 OpName %4 "main"
4310 OpName %8 "i"
4311 OpName %20 "x"
4312 OpName %25 "a"
4313 OpName %34 "j"
4314 OpName %42 "b"
4315 %2 = OpTypeVoid
4316 %3 = OpTypeFunction %2
4317 %6 = OpTypeInt 32 1
4318 %7 = OpTypePointer Function %6
4319 %9 = OpConstant %6 0
4320 %16 = OpConstant %6 10
4321 %17 = OpTypeBool
4322 %19 = OpTypePointer Private %6
4323 %20 = OpVariable %19 Private
4324 %21 = OpTypeInt 32 0
4325 %22 = OpConstant %21 10
4326 %23 = OpTypeArray %6 %22
4327 %24 = OpTypePointer Function %23
4328 %32 = OpConstant %6 1
4329 %4 = OpFunction %2 None %3
4330 %5 = OpLabel
4331 %8 = OpVariable %7 Function
4332 %25 = OpVariable %24 Function
4333 %34 = OpVariable %7 Function
4334 %42 = OpVariable %24 Function
4335 OpStore %8 %9
4336 OpBranch %10
4337 %10 = OpLabel
4338 %51 = OpPhi %6 %9 %5 %33 %13
4339 OpLoopMerge %12 %13 None
4340 OpBranch %14
4341 %14 = OpLabel
4342 %18 = OpSLessThan %17 %51 %16
4343 OpBranchConditional %18 %11 %12
4344 %11 = OpLabel
4345 %27 = OpAccessChain %7 %25 %51
4346 %28 = OpLoad %6 %27
4347 %29 = OpLoad %6 %20
4348 %30 = OpIAdd %6 %29 %28
4349 OpStore %20 %30
4350 OpBranch %13
4351 %13 = OpLabel
4352 %33 = OpIAdd %6 %51 %32
4353 OpStore %8 %33
4354 OpBranch %10
4355 %12 = OpLabel
4356 OpStore %34 %9
4357 OpBranch %35
4358 %35 = OpLabel
4359 %52 = OpPhi %6 %9 %12 %50 %38
4360 OpLoopMerge %37 %38 None
4361 OpBranch %39
4362 %39 = OpLabel
4363 %41 = OpSLessThan %17 %52 %16
4364 OpBranchConditional %41 %36 %37
4365 %36 = OpLabel
4366 %45 = OpAccessChain %7 %42 %52
4367 %46 = OpLoad %6 %45
4368 %47 = OpIAdd %6 %46 %32
4369 %48 = OpAccessChain %7 %42 %52
4370 OpStore %48 %47
4371 OpBranch %38
4372 %38 = OpLabel
4373 %50 = OpIAdd %6 %52 %32
4374 OpStore %34 %50
4375 OpBranch %35
4376 %37 = OpLabel
4377 OpReturn
4378 OpFunctionEnd
4379 )";
4380
4381 std::unique_ptr<IRContext> context =
4382 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
4383 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
4384 Module* module = context->module();
4385 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
4386 << text << std::endl;
4387 Function& f = *module->begin();
4388
4389 {
4390 LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
4391 EXPECT_EQ(ld.NumLoops(), 2u);
4392
4393 auto loops = ld.GetLoopsInBinaryLayoutOrder();
4394
4395 LoopFusion fusion(context.get(), loops[0], loops[1]);
4396 EXPECT_TRUE(fusion.AreCompatible());
4397 EXPECT_TRUE(fusion.IsLegal());
4398
4399 fusion.Fuse();
4400 }
4401
4402 {
4403 LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
4404 EXPECT_EQ(ld.NumLoops(), 1u);
4405
4406 std::string checks = R"(
4407 CHECK: OpName [[X:%\w+]] "x"
4408 CHECK: [[PHI:%\w+]] = OpPhi
4409 CHECK-NEXT: OpLoopMerge
4410 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
4411 CHECK-NEXT: [[LOAD_RES_0:%\w+]] = OpLoad {{%\w+}} [[LOAD_0]]
4412 CHECK-NEXT: [[X_LOAD:%\w+]] = OpLoad {{%\w+}} [[X]]
4413 CHECK-NEXT: [[ADD_RES_0:%\w+]] = OpIAdd {{%\w+}} [[X_LOAD]] [[LOAD_RES_0]]
4414 CHECK-NEXT: OpStore [[X]] [[ADD_RES_0]]
4415 CHECK-NOT: OpPhi
4416 CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
4417 CHECK-NEXT: {{%\w+}} = OpLoad {{%\w+}} [[LOAD_1]]
4418 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
4419 CHECK-NEXT: OpStore [[STORE_1]]
4420 )";
4421
4422 Match(checks, context.get());
4423 }
4424 }
4425
4426 /*
4427 Generated from the following GLSL + --eliminate-local-multi-store
4428
4429 #version 440 core
4430 struct TestStruct {
4431 int[10] a;
4432 int b;
4433 };
4434
4435 void main() {
4436 TestStruct test_0;
4437 TestStruct test_1;
4438 TestStruct test_2;
4439
4440 test_1.b = 2;
4441
4442 for (int i = 0; i < 10; i++) {
4443 test_0.a[i] = i;
4444 }
4445 for (int j = 0; j < 10; j++) {
4446 test_2 = test_1;
4447 }
4448 }
4449
4450 */
TEST_F(FusionLegalTest,ArrayInStruct)4451 TEST_F(FusionLegalTest, ArrayInStruct) {
4452 std::string text = R"(
4453 OpCapability Shader
4454 %1 = OpExtInstImport "GLSL.std.450"
4455 OpMemoryModel Logical GLSL450
4456 OpEntryPoint Fragment %4 "main"
4457 OpExecutionMode %4 OriginUpperLeft
4458 OpSource GLSL 440
4459 OpName %4 "main"
4460 OpName %10 "TestStruct"
4461 OpMemberName %10 0 "a"
4462 OpMemberName %10 1 "b"
4463 OpName %12 "test_1"
4464 OpName %17 "i"
4465 OpName %28 "test_0"
4466 OpName %34 "j"
4467 OpName %42 "test_2"
4468 %2 = OpTypeVoid
4469 %3 = OpTypeFunction %2
4470 %6 = OpTypeInt 32 1
4471 %7 = OpTypeInt 32 0
4472 %8 = OpConstant %7 10
4473 %9 = OpTypeArray %6 %8
4474 %10 = OpTypeStruct %9 %6
4475 %11 = OpTypePointer Function %10
4476 %13 = OpConstant %6 1
4477 %14 = OpConstant %6 2
4478 %15 = OpTypePointer Function %6
4479 %18 = OpConstant %6 0
4480 %25 = OpConstant %6 10
4481 %26 = OpTypeBool
4482 %4 = OpFunction %2 None %3
4483 %5 = OpLabel
4484 %12 = OpVariable %11 Function
4485 %17 = OpVariable %15 Function
4486 %28 = OpVariable %11 Function
4487 %34 = OpVariable %15 Function
4488 %42 = OpVariable %11 Function
4489 %16 = OpAccessChain %15 %12 %13
4490 OpStore %16 %14
4491 OpStore %17 %18
4492 OpBranch %19
4493 %19 = OpLabel
4494 %46 = OpPhi %6 %18 %5 %33 %22
4495 OpLoopMerge %21 %22 None
4496 OpBranch %23
4497 %23 = OpLabel
4498 %27 = OpSLessThan %26 %46 %25
4499 OpBranchConditional %27 %20 %21
4500 %20 = OpLabel
4501 %31 = OpAccessChain %15 %28 %18 %46
4502 OpStore %31 %46
4503 OpBranch %22
4504 %22 = OpLabel
4505 %33 = OpIAdd %6 %46 %13
4506 OpStore %17 %33
4507 OpBranch %19
4508 %21 = OpLabel
4509 OpStore %34 %18
4510 OpBranch %35
4511 %35 = OpLabel
4512 %47 = OpPhi %6 %18 %21 %45 %38
4513 OpLoopMerge %37 %38 None
4514 OpBranch %39
4515 %39 = OpLabel
4516 %41 = OpSLessThan %26 %47 %25
4517 OpBranchConditional %41 %36 %37
4518 %36 = OpLabel
4519 %43 = OpLoad %10 %12
4520 OpStore %42 %43
4521 OpBranch %38
4522 %38 = OpLabel
4523 %45 = OpIAdd %6 %47 %13
4524 OpStore %34 %45
4525 OpBranch %35
4526 %37 = OpLabel
4527 OpReturn
4528 OpFunctionEnd
4529 )";
4530
4531 std::unique_ptr<IRContext> context =
4532 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
4533 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
4534 Module* module = context->module();
4535 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
4536 << text << std::endl;
4537 Function& f = *module->begin();
4538
4539 {
4540 LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
4541 EXPECT_EQ(ld.NumLoops(), 2u);
4542
4543 auto loops = ld.GetLoopsInBinaryLayoutOrder();
4544
4545 LoopFusion fusion(context.get(), loops[0], loops[1]);
4546 EXPECT_TRUE(fusion.AreCompatible());
4547 EXPECT_TRUE(fusion.IsLegal());
4548
4549 fusion.Fuse();
4550 }
4551
4552 {
4553 LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
4554 EXPECT_EQ(ld.NumLoops(), 1u);
4555
4556 // clang-format off
4557 std::string checks = R"(
4558 CHECK: OpName [[TEST_1:%\w+]] "test_1"
4559 CHECK: OpName [[TEST_0:%\w+]] "test_0"
4560 CHECK: OpName [[TEST_2:%\w+]] "test_2"
4561 CHECK: [[PHI:%\w+]] = OpPhi
4562 CHECK-NEXT: OpLoopMerge
4563 CHECK: [[TEST_0_STORE:%\w+]] = OpAccessChain {{%\w+}} [[TEST_0]] {{%\w+}} {{%\w+}}
4564 CHECK-NEXT: OpStore [[TEST_0_STORE]] [[PHI]]
4565 CHECK-NOT: OpPhi
4566 CHECK: [[TEST_1_LOAD:%\w+]] = OpLoad {{%\w+}} [[TEST_1]]
4567 CHECK: OpStore [[TEST_2]] [[TEST_1_LOAD]]
4568 )";
4569 // clang-format on
4570
4571 Match(checks, context.get());
4572 }
4573 }
4574
4575 } // namespace
4576 } // namespace opt
4577 } // namespace spvtools
4578