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