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