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 %sel_merge 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 %sel_merge
3191          %32 = OpLabel
3192                OpBranch %sel_merge
3193   %sel_merge = OpLabel
3194                OpBranch %23
3195          %23 = OpLabel
3196          %52 = OpIAdd %6 %96 %51
3197                OpStore %19 %52
3198                OpBranch %20
3199          %22 = OpLabel
3200                OpBranch %13
3201          %13 = OpLabel
3202          %54 = OpIAdd %6 %91 %51
3203                OpStore %8 %54
3204                OpBranch %10
3205          %12 = OpLabel
3206                OpStore %55 %9
3207                OpBranch %56
3208          %56 = OpLabel
3209          %92 = OpPhi %6 %9 %12 %90 %59
3210                OpLoopMerge %58 %59 None
3211                OpBranch %60
3212          %60 = OpLabel
3213          %62 = OpSLessThan %17 %92 %16
3214                OpBranchConditional %62 %57 %58
3215          %57 = OpLabel
3216                OpStore %63 %9
3217                OpBranch %64
3218          %64 = OpLabel
3219          %93 = OpPhi %6 %9 %57 %88 %67
3220                OpLoopMerge %66 %67 None
3221                OpBranch %68
3222          %68 = OpLabel
3223          %70 = OpSLessThan %17 %93 %16
3224                OpBranchConditional %70 %65 %66
3225          %65 = OpLabel
3226          %72 = OpSMod %6 %93 %28
3227          %73 = OpIEqual %17 %72 %9
3228                OpSelectionMerge %75 None
3229                OpBranchConditional %73 %74 %66
3230          %74 = OpLabel
3231          %81 = OpAccessChain %7 %38 %92 %93
3232          %82 = OpLoad %6 %81
3233          %83 = OpIAdd %6 %82 %16
3234          %84 = OpAccessChain %7 %76 %92 %93
3235                OpStore %84 %83
3236                OpBranch %75
3237          %75 = OpLabel
3238                OpBranch %67
3239          %67 = OpLabel
3240          %88 = OpIAdd %6 %93 %51
3241                OpStore %63 %88
3242                OpBranch %64
3243          %66 = OpLabel
3244                OpBranch %59
3245          %59 = OpLabel
3246          %90 = OpIAdd %6 %92 %51
3247                OpStore %55 %90
3248                OpBranch %56
3249          %58 = OpLabel
3250                OpReturn
3251                OpFunctionEnd
3252     )";
3253 
3254   std::unique_ptr<IRContext> context =
3255       BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
3256                   SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
3257   Module* module = context->module();
3258   EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
3259                              << text << std::endl;
3260   Function& f = *module->begin();
3261 
3262   {
3263     LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
3264     EXPECT_EQ(ld.NumLoops(), 4u);
3265 
3266     auto loops = ld.GetLoopsInBinaryLayoutOrder();
3267 
3268     LoopFusion fusion(context.get(), loops[0], loops[2]);
3269     EXPECT_TRUE(fusion.AreCompatible());
3270     EXPECT_TRUE(fusion.IsLegal());
3271 
3272     fusion.Fuse();
3273   }
3274 
3275   {
3276     LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
3277     EXPECT_EQ(ld.NumLoops(), 3u);
3278 
3279     auto loops = ld.GetLoopsInBinaryLayoutOrder();
3280 
3281     LoopFusion fusion(context.get(), loops[1], loops[2]);
3282     EXPECT_FALSE(fusion.AreCompatible());
3283 
3284     std::string checks = R"(
3285 CHECK: [[PHI_0:%\w+]] = OpPhi
3286 CHECK-NEXT: OpLoopMerge
3287 CHECK: [[PHI_1:%\w+]] = OpPhi
3288 CHECK-NEXT: OpLoopMerge
3289 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] [[PHI_1]]
3290 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_0]]
3291 CHECK: [[STORE_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] [[PHI_1]]
3292 CHECK-NEXT: OpStore [[STORE_0]]
3293 CHECK: [[PHI_2:%\w+]] = OpPhi
3294 CHECK-NEXT: OpLoopMerge
3295 CHECK-NOT: OpPhi
3296 CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] [[PHI_2]]
3297 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_1]]
3298 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] [[PHI_2]]
3299 CHECK-NEXT: OpStore [[STORE_1]]
3300       )";
3301 
3302     Match(checks, context.get());
3303   }
3304 }
3305 
3306 /*
3307 Generated from the following GLSL + --eliminate-local-multi-store
3308 
3309 // j loop preheader removed manually
3310 #version 440 core
3311 void main() {
3312   int[10] a;
3313   int[10] b;
3314   int i = 0;
3315   int j = 0;
3316   // No loop-carried dependences, legal
3317   for (; i < 10; i++) {
3318     a[i] = a[i]*2;
3319   }
3320   for (; j < 10; j++) {
3321     b[j] = a[j]+2;
3322   }
3323 }
3324 
3325 */
TEST_F(FusionLegalTest,DifferentArraysInLoopsNoPreheader)3326 TEST_F(FusionLegalTest, DifferentArraysInLoopsNoPreheader) {
3327   std::string text = R"(
3328                OpCapability Shader
3329           %1 = OpExtInstImport "GLSL.std.450"
3330                OpMemoryModel Logical GLSL450
3331                OpEntryPoint Fragment %4 "main"
3332                OpExecutionMode %4 OriginUpperLeft
3333                OpSource GLSL 440
3334                OpName %4 "main"
3335                OpName %8 "i"
3336                OpName %10 "j"
3337                OpName %24 "a"
3338                OpName %42 "b"
3339           %2 = OpTypeVoid
3340           %3 = OpTypeFunction %2
3341           %6 = OpTypeInt 32 1
3342           %7 = OpTypePointer Function %6
3343           %9 = OpConstant %6 0
3344          %17 = OpConstant %6 10
3345          %18 = OpTypeBool
3346          %20 = OpTypeInt 32 0
3347          %21 = OpConstant %20 10
3348          %22 = OpTypeArray %6 %21
3349          %23 = OpTypePointer Function %22
3350          %29 = OpConstant %6 2
3351          %33 = OpConstant %6 1
3352           %4 = OpFunction %2 None %3
3353           %5 = OpLabel
3354           %8 = OpVariable %7 Function
3355          %10 = OpVariable %7 Function
3356          %24 = OpVariable %23 Function
3357          %42 = OpVariable %23 Function
3358                OpStore %8 %9
3359                OpStore %10 %9
3360                OpBranch %11
3361          %11 = OpLabel
3362          %51 = OpPhi %6 %9 %5 %34 %14
3363                OpLoopMerge %35 %14 None
3364                OpBranch %15
3365          %15 = OpLabel
3366          %19 = OpSLessThan %18 %51 %17
3367                OpBranchConditional %19 %12 %35
3368          %12 = OpLabel
3369          %27 = OpAccessChain %7 %24 %51
3370          %28 = OpLoad %6 %27
3371          %30 = OpIMul %6 %28 %29
3372          %31 = OpAccessChain %7 %24 %51
3373                OpStore %31 %30
3374                OpBranch %14
3375          %14 = OpLabel
3376          %34 = OpIAdd %6 %51 %33
3377                OpStore %8 %34
3378                OpBranch %11
3379          %35 = OpLabel
3380          %52 = OpPhi %6 %9 %15 %50 %38
3381                OpLoopMerge %37 %38 None
3382                OpBranch %39
3383          %39 = OpLabel
3384          %41 = OpSLessThan %18 %52 %17
3385                OpBranchConditional %41 %36 %37
3386          %36 = OpLabel
3387          %45 = OpAccessChain %7 %24 %52
3388          %46 = OpLoad %6 %45
3389          %47 = OpIAdd %6 %46 %29
3390          %48 = OpAccessChain %7 %42 %52
3391                OpStore %48 %47
3392                OpBranch %38
3393          %38 = OpLabel
3394          %50 = OpIAdd %6 %52 %33
3395                OpStore %10 %50
3396                OpBranch %35
3397          %37 = OpLabel
3398                OpReturn
3399                OpFunctionEnd
3400     )";
3401 
3402   std::unique_ptr<IRContext> context =
3403       BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
3404                   SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
3405   Module* module = context->module();
3406   EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
3407                              << text << std::endl;
3408   Function& f = *module->begin();
3409 
3410   {
3411     LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
3412     EXPECT_EQ(ld.NumLoops(), 2u);
3413 
3414     auto loops = ld.GetLoopsInBinaryLayoutOrder();
3415 
3416     {
3417       LoopFusion fusion(context.get(), loops[0], loops[1]);
3418       EXPECT_FALSE(fusion.AreCompatible());
3419     }
3420 
3421     ld.CreatePreHeaderBlocksIfMissing();
3422 
3423     {
3424       LoopFusion fusion(context.get(), loops[0], loops[1]);
3425       EXPECT_TRUE(fusion.AreCompatible());
3426       EXPECT_TRUE(fusion.IsLegal());
3427 
3428       fusion.Fuse();
3429     }
3430   }
3431 
3432   {
3433     LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
3434     EXPECT_EQ(ld.NumLoops(), 1u);
3435 
3436     std::string checks = R"(
3437 CHECK: [[PHI:%\w+]] = OpPhi
3438 CHECK-NEXT: OpLoopMerge
3439 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
3440 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_0]]
3441 CHECK: [[STORE_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
3442 CHECK-NEXT: OpStore [[STORE_0]]
3443 CHECK-NOT: OpPhi
3444 CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
3445 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_1]]
3446 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
3447 CHECK-NEXT: OpStore [[STORE_1]]
3448       )";
3449 
3450     Match(checks, context.get());
3451   }
3452 }
3453 
3454 /*
3455 Generated from the following GLSL + --eliminate-local-multi-store
3456 
3457 // j & k loop preheaders removed manually
3458 #version 440 core
3459 void main() {
3460   int[10] a;
3461   int[10] b;
3462   int i = 0;
3463   int j = 0;
3464   int k = 0;
3465   // No loop-carried dependences, legal
3466   for (; i < 10; i++) {
3467     a[i] = a[i]*2;
3468   }
3469   for (; j < 10; j++) {
3470     b[j] = a[j]+2;
3471   }
3472   for (; k < 10; k++) {
3473     a[k] = a[k]*2;
3474   }
3475 }
3476 
3477 */
TEST_F(FusionLegalTest,AdjacentLoopsNoPreheaders)3478 TEST_F(FusionLegalTest, AdjacentLoopsNoPreheaders) {
3479   std::string text = R"(
3480                OpCapability Shader
3481           %1 = OpExtInstImport "GLSL.std.450"
3482                OpMemoryModel Logical GLSL450
3483                OpEntryPoint Fragment %4 "main"
3484                OpExecutionMode %4 OriginUpperLeft
3485                OpSource GLSL 440
3486                OpName %4 "main"
3487                OpName %8 "i"
3488                OpName %10 "j"
3489                OpName %11 "k"
3490                OpName %25 "a"
3491                OpName %43 "b"
3492           %2 = OpTypeVoid
3493           %3 = OpTypeFunction %2
3494           %6 = OpTypeInt 32 1
3495           %7 = OpTypePointer Function %6
3496           %9 = OpConstant %6 0
3497          %18 = OpConstant %6 10
3498          %19 = OpTypeBool
3499          %21 = OpTypeInt 32 0
3500          %22 = OpConstant %21 10
3501          %23 = OpTypeArray %6 %22
3502          %24 = OpTypePointer Function %23
3503          %30 = OpConstant %6 2
3504          %34 = OpConstant %6 1
3505           %4 = OpFunction %2 None %3
3506           %5 = OpLabel
3507           %8 = OpVariable %7 Function
3508          %10 = OpVariable %7 Function
3509          %11 = OpVariable %7 Function
3510          %25 = OpVariable %24 Function
3511          %43 = OpVariable %24 Function
3512                OpStore %8 %9
3513                OpStore %10 %9
3514                OpStore %11 %9
3515                OpBranch %12
3516          %12 = OpLabel
3517          %67 = OpPhi %6 %9 %5 %35 %15
3518                OpLoopMerge %36 %15 None
3519                OpBranch %16
3520          %16 = OpLabel
3521          %20 = OpSLessThan %19 %67 %18
3522                OpBranchConditional %20 %13 %36
3523          %13 = OpLabel
3524          %28 = OpAccessChain %7 %25 %67
3525          %29 = OpLoad %6 %28
3526          %31 = OpIMul %6 %29 %30
3527          %32 = OpAccessChain %7 %25 %67
3528                OpStore %32 %31
3529                OpBranch %15
3530          %15 = OpLabel
3531          %35 = OpIAdd %6 %67 %34
3532                OpStore %8 %35
3533                OpBranch %12
3534          %36 = OpLabel
3535          %68 = OpPhi %6 %9 %16 %51 %39
3536                OpLoopMerge %52 %39 None
3537                OpBranch %40
3538          %40 = OpLabel
3539          %42 = OpSLessThan %19 %68 %18
3540                OpBranchConditional %42 %37 %52
3541          %37 = OpLabel
3542          %46 = OpAccessChain %7 %25 %68
3543          %47 = OpLoad %6 %46
3544          %48 = OpIAdd %6 %47 %30
3545          %49 = OpAccessChain %7 %43 %68
3546                OpStore %49 %48
3547                OpBranch %39
3548          %39 = OpLabel
3549          %51 = OpIAdd %6 %68 %34
3550                OpStore %10 %51
3551                OpBranch %36
3552          %52 = OpLabel
3553          %70 = OpPhi %6 %9 %40 %66 %55
3554                OpLoopMerge %54 %55 None
3555                OpBranch %56
3556          %56 = OpLabel
3557          %58 = OpSLessThan %19 %70 %18
3558                OpBranchConditional %58 %53 %54
3559          %53 = OpLabel
3560          %61 = OpAccessChain %7 %25 %70
3561          %62 = OpLoad %6 %61
3562          %63 = OpIMul %6 %62 %30
3563          %64 = OpAccessChain %7 %25 %70
3564                OpStore %64 %63
3565                OpBranch %55
3566          %55 = OpLabel
3567          %66 = OpIAdd %6 %70 %34
3568                OpStore %11 %66
3569                OpBranch %52
3570          %54 = OpLabel
3571                OpReturn
3572                OpFunctionEnd
3573     )";
3574 
3575   std::unique_ptr<IRContext> context =
3576       BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
3577                   SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
3578   Module* module = context->module();
3579   EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
3580                              << text << std::endl;
3581   Function& f = *module->begin();
3582 
3583   {
3584     LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
3585     EXPECT_EQ(ld.NumLoops(), 3u);
3586 
3587     auto loops = ld.GetLoopsInBinaryLayoutOrder();
3588 
3589     {
3590       LoopFusion fusion(context.get(), loops[0], loops[1]);
3591       EXPECT_FALSE(fusion.AreCompatible());
3592     }
3593 
3594     ld.CreatePreHeaderBlocksIfMissing();
3595 
3596     {
3597       LoopFusion fusion(context.get(), loops[0], loops[1]);
3598       EXPECT_TRUE(fusion.AreCompatible());
3599       EXPECT_TRUE(fusion.IsLegal());
3600 
3601       fusion.Fuse();
3602     }
3603   }
3604 
3605   {
3606     LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
3607     EXPECT_EQ(ld.NumLoops(), 2u);
3608 
3609     std::string checks = R"(
3610 CHECK: [[PHI_0:%\w+]] = OpPhi
3611 CHECK-NEXT: OpLoopMerge
3612 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]]
3613 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_0]]
3614 CHECK: [[STORE_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]]
3615 CHECK-NEXT: OpStore [[STORE_0]]
3616 CHECK-NOT: OpPhi
3617 CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]]
3618 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_1]]
3619 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]]
3620 CHECK-NEXT: OpStore [[STORE_1]]
3621 CHECK: [[PHI_1:%\w+]] = OpPhi
3622 CHECK-NEXT: OpLoopMerge
3623 CHECK: [[LOAD_2:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_1]]
3624 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_2]]
3625 CHECK: [[STORE_2:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_1]]
3626 CHECK-NEXT: OpStore [[STORE_2]]
3627       )";
3628 
3629     Match(checks, context.get());
3630 
3631     auto loops = ld.GetLoopsInBinaryLayoutOrder();
3632 
3633     LoopFusion fusion(context.get(), loops[0], loops[1]);
3634     EXPECT_TRUE(fusion.AreCompatible());
3635     EXPECT_TRUE(fusion.IsLegal());
3636 
3637     fusion.Fuse();
3638   }
3639 
3640   {
3641     LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
3642     EXPECT_EQ(ld.NumLoops(), 1u);
3643 
3644     std::string checks = R"(
3645 CHECK: [[PHI:%\w+]] = OpPhi
3646 CHECK-NEXT: OpLoopMerge
3647 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
3648 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_0]]
3649 CHECK: [[STORE_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
3650 CHECK-NEXT: OpStore [[STORE_0]]
3651 CHECK-NOT: OpPhi
3652 CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
3653 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_1]]
3654 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
3655 CHECK-NEXT: OpStore [[STORE_1]]
3656 CHECK-NOT: OpPhi
3657 CHECK: [[LOAD_2:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
3658 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_2]]
3659 CHECK: [[STORE_2:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
3660 CHECK-NEXT: OpStore [[STORE_2]]
3661       )";
3662 
3663     Match(checks, context.get());
3664   }
3665 }
3666 
3667 /*
3668 Generated from the following GLSL + --eliminate-local-multi-store
3669 
3670 #version 440 core
3671 void main() {
3672   int[10] a;
3673   int[10] b;
3674 
3675   int sum_0 = 0;
3676   int sum_1 = 0;
3677 
3678   // No loop-carried dependences, legal
3679   for (int i = 0; i < 10; i++) {
3680     sum_0 += a[i];
3681   }
3682   for (int j = 0; j < 10; j++) {
3683     sum_1 += b[j];
3684   }
3685 
3686   int total = sum_0 + sum_1;
3687 }
3688 
3689 */
TEST_F(FusionLegalTest,IndependentReductions)3690 TEST_F(FusionLegalTest, IndependentReductions) {
3691   std::string text = R"(
3692                OpCapability Shader
3693           %1 = OpExtInstImport "GLSL.std.450"
3694                OpMemoryModel Logical GLSL450
3695                OpEntryPoint Fragment %4 "main"
3696                OpExecutionMode %4 OriginUpperLeft
3697                OpSource GLSL 440
3698                OpName %4 "main"
3699                OpName %8 "sum_0"
3700                OpName %10 "sum_1"
3701                OpName %11 "i"
3702                OpName %25 "a"
3703                OpName %34 "j"
3704                OpName %42 "b"
3705                OpName %50 "total"
3706           %2 = OpTypeVoid
3707           %3 = OpTypeFunction %2
3708           %6 = OpTypeInt 32 1
3709           %7 = OpTypePointer Function %6
3710           %9 = OpConstant %6 0
3711          %18 = OpConstant %6 10
3712          %19 = OpTypeBool
3713          %21 = OpTypeInt 32 0
3714          %22 = OpConstant %21 10
3715          %23 = OpTypeArray %6 %22
3716          %24 = OpTypePointer Function %23
3717          %32 = OpConstant %6 1
3718           %4 = OpFunction %2 None %3
3719           %5 = OpLabel
3720           %8 = OpVariable %7 Function
3721          %10 = OpVariable %7 Function
3722          %11 = OpVariable %7 Function
3723          %25 = OpVariable %24 Function
3724          %34 = OpVariable %7 Function
3725          %42 = OpVariable %24 Function
3726          %50 = OpVariable %7 Function
3727                OpStore %8 %9
3728                OpStore %10 %9
3729                OpStore %11 %9
3730                OpBranch %12
3731          %12 = OpLabel
3732          %57 = OpPhi %6 %9 %5 %30 %15
3733          %54 = OpPhi %6 %9 %5 %33 %15
3734                OpLoopMerge %14 %15 None
3735                OpBranch %16
3736          %16 = OpLabel
3737          %20 = OpSLessThan %19 %54 %18
3738                OpBranchConditional %20 %13 %14
3739          %13 = OpLabel
3740          %27 = OpAccessChain %7 %25 %54
3741          %28 = OpLoad %6 %27
3742          %30 = OpIAdd %6 %57 %28
3743                OpStore %8 %30
3744                OpBranch %15
3745          %15 = OpLabel
3746          %33 = OpIAdd %6 %54 %32
3747                OpStore %11 %33
3748                OpBranch %12
3749          %14 = OpLabel
3750                OpStore %34 %9
3751                OpBranch %35
3752          %35 = OpLabel
3753          %58 = OpPhi %6 %9 %14 %47 %38
3754          %55 = OpPhi %6 %9 %14 %49 %38
3755                OpLoopMerge %37 %38 None
3756                OpBranch %39
3757          %39 = OpLabel
3758          %41 = OpSLessThan %19 %55 %18
3759                OpBranchConditional %41 %36 %37
3760          %36 = OpLabel
3761          %44 = OpAccessChain %7 %42 %55
3762          %45 = OpLoad %6 %44
3763          %47 = OpIAdd %6 %58 %45
3764                OpStore %10 %47
3765                OpBranch %38
3766          %38 = OpLabel
3767          %49 = OpIAdd %6 %55 %32
3768                OpStore %34 %49
3769                OpBranch %35
3770          %37 = OpLabel
3771          %53 = OpIAdd %6 %57 %58
3772                OpStore %50 %53
3773                OpReturn
3774                OpFunctionEnd
3775     )";
3776 
3777   std::unique_ptr<IRContext> context =
3778       BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
3779                   SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
3780   Module* module = context->module();
3781   EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
3782                              << text << std::endl;
3783   Function& f = *module->begin();
3784 
3785   {
3786     LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
3787     EXPECT_EQ(ld.NumLoops(), 2u);
3788 
3789     auto loops = ld.GetLoopsInBinaryLayoutOrder();
3790 
3791     LoopFusion fusion(context.get(), loops[0], loops[1]);
3792     EXPECT_TRUE(fusion.AreCompatible());
3793     EXPECT_TRUE(fusion.IsLegal());
3794 
3795     fusion.Fuse();
3796   }
3797 
3798   {
3799     LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
3800     EXPECT_EQ(ld.NumLoops(), 1u);
3801 
3802     std::string checks = R"(
3803 CHECK: [[SUM_0:%\w+]] = OpPhi
3804 CHECK-NEXT: [[SUM_1:%\w+]] = OpPhi
3805 CHECK-NEXT: [[PHI:%\w+]] = OpPhi
3806 CHECK-NEXT: OpLoopMerge
3807 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
3808 CHECK-NEXT: [[LOAD_RES_0:%\w+]] = OpLoad {{%\w+}} [[LOAD_0]]
3809 CHECK-NEXT: [[ADD_RES_0:%\w+]] = OpIAdd {{%\w+}} [[SUM_0]] [[LOAD_RES_0]]
3810 CHECK-NEXT: OpStore {{%\w+}} [[ADD_RES_0]]
3811 CHECK-NOT: OpPhi
3812 CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
3813 CHECK-NEXT: [[LOAD_RES_1:%\w+]] = OpLoad {{%\w+}} [[LOAD_1]]
3814 CHECK-NEXT: [[ADD_RES_1:%\w+]] = OpIAdd {{%\w+}} [[SUM_1]] [[LOAD_RES_1]]
3815 CHECK-NEXT: OpStore {{%\w+}} [[ADD_RES_1]]
3816       )";
3817 
3818     Match(checks, context.get());
3819   }
3820 }
3821 
3822 /*
3823 Generated from the following GLSL + --eliminate-local-multi-store
3824 
3825 #version 440 core
3826 void main() {
3827   int[10] a;
3828   int[10] b;
3829 
3830   int sum_0 = 0;
3831   int sum_1 = 0;
3832 
3833   // No loop-carried dependences, legal
3834   for (int i = 0; i < 10; i++) {
3835     sum_0 += a[i];
3836   }
3837   for (int j = 0; j < 10; j++) {
3838     sum_1 += b[j];
3839   }
3840 
3841   int total = sum_0 + sum_1;
3842 }
3843 
3844 */
TEST_F(FusionLegalTest,IndependentReductionsOneLCSSA)3845 TEST_F(FusionLegalTest, IndependentReductionsOneLCSSA) {
3846   std::string text = R"(
3847                OpCapability Shader
3848           %1 = OpExtInstImport "GLSL.std.450"
3849                OpMemoryModel Logical GLSL450
3850                OpEntryPoint Fragment %4 "main"
3851                OpExecutionMode %4 OriginUpperLeft
3852                OpSource GLSL 440
3853                OpName %4 "main"
3854                OpName %8 "sum_0"
3855                OpName %10 "sum_1"
3856                OpName %11 "i"
3857                OpName %25 "a"
3858                OpName %34 "j"
3859                OpName %42 "b"
3860                OpName %50 "total"
3861           %2 = OpTypeVoid
3862           %3 = OpTypeFunction %2
3863           %6 = OpTypeInt 32 1
3864           %7 = OpTypePointer Function %6
3865           %9 = OpConstant %6 0
3866          %18 = OpConstant %6 10
3867          %19 = OpTypeBool
3868          %21 = OpTypeInt 32 0
3869          %22 = OpConstant %21 10
3870          %23 = OpTypeArray %6 %22
3871          %24 = OpTypePointer Function %23
3872          %32 = OpConstant %6 1
3873           %4 = OpFunction %2 None %3
3874           %5 = OpLabel
3875           %8 = OpVariable %7 Function
3876          %10 = OpVariable %7 Function
3877          %11 = OpVariable %7 Function
3878          %25 = OpVariable %24 Function
3879          %34 = OpVariable %7 Function
3880          %42 = OpVariable %24 Function
3881          %50 = OpVariable %7 Function
3882                OpStore %8 %9
3883                OpStore %10 %9
3884                OpStore %11 %9
3885                OpBranch %12
3886          %12 = OpLabel
3887          %57 = OpPhi %6 %9 %5 %30 %15
3888          %54 = OpPhi %6 %9 %5 %33 %15
3889                OpLoopMerge %14 %15 None
3890                OpBranch %16
3891          %16 = OpLabel
3892          %20 = OpSLessThan %19 %54 %18
3893                OpBranchConditional %20 %13 %14
3894          %13 = OpLabel
3895          %27 = OpAccessChain %7 %25 %54
3896          %28 = OpLoad %6 %27
3897          %30 = OpIAdd %6 %57 %28
3898                OpStore %8 %30
3899                OpBranch %15
3900          %15 = OpLabel
3901          %33 = OpIAdd %6 %54 %32
3902                OpStore %11 %33
3903                OpBranch %12
3904          %14 = OpLabel
3905                OpStore %34 %9
3906                OpBranch %35
3907          %35 = OpLabel
3908          %58 = OpPhi %6 %9 %14 %47 %38
3909          %55 = OpPhi %6 %9 %14 %49 %38
3910                OpLoopMerge %37 %38 None
3911                OpBranch %39
3912          %39 = OpLabel
3913          %41 = OpSLessThan %19 %55 %18
3914                OpBranchConditional %41 %36 %37
3915          %36 = OpLabel
3916          %44 = OpAccessChain %7 %42 %55
3917          %45 = OpLoad %6 %44
3918          %47 = OpIAdd %6 %58 %45
3919                OpStore %10 %47
3920                OpBranch %38
3921          %38 = OpLabel
3922          %49 = OpIAdd %6 %55 %32
3923                OpStore %34 %49
3924                OpBranch %35
3925          %37 = OpLabel
3926          %53 = OpIAdd %6 %57 %58
3927                OpStore %50 %53
3928                OpReturn
3929                OpFunctionEnd
3930     )";
3931 
3932   std::unique_ptr<IRContext> context =
3933       BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
3934                   SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
3935   Module* module = context->module();
3936   EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
3937                              << text << std::endl;
3938   Function& f = *module->begin();
3939 
3940   {
3941     LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
3942     EXPECT_EQ(ld.NumLoops(), 2u);
3943 
3944     auto loops = ld.GetLoopsInBinaryLayoutOrder();
3945 
3946     LoopUtils utils_0(context.get(), loops[0]);
3947     utils_0.MakeLoopClosedSSA();
3948 
3949     LoopFusion fusion(context.get(), loops[0], loops[1]);
3950     EXPECT_TRUE(fusion.AreCompatible());
3951     EXPECT_TRUE(fusion.IsLegal());
3952 
3953     fusion.Fuse();
3954   }
3955 
3956   {
3957     LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
3958     EXPECT_EQ(ld.NumLoops(), 1u);
3959 
3960     std::string checks = R"(
3961 CHECK: [[SUM_0:%\w+]] = OpPhi
3962 CHECK-NEXT: [[SUM_1:%\w+]] = OpPhi
3963 CHECK-NEXT: [[PHI:%\w+]] = OpPhi
3964 CHECK-NEXT: OpLoopMerge
3965 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
3966 CHECK-NEXT: [[LOAD_RES_0:%\w+]] = OpLoad {{%\w+}} [[LOAD_0]]
3967 CHECK-NEXT: [[ADD_RES_0:%\w+]] = OpIAdd {{%\w+}} [[SUM_0]] [[LOAD_RES_0]]
3968 CHECK-NEXT: OpStore {{%\w+}} [[ADD_RES_0]]
3969 CHECK-NOT: OpPhi
3970 CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
3971 CHECK-NEXT: [[LOAD_RES_1:%\w+]] = OpLoad {{%\w+}} [[LOAD_1]]
3972 CHECK-NEXT: [[ADD_RES_1:%\w+]] = OpIAdd {{%\w+}} [[SUM_1]] [[LOAD_RES_1]]
3973 CHECK-NEXT: OpStore {{%\w+}} [[ADD_RES_1]]
3974       )";
3975 
3976     Match(checks, context.get());
3977   }
3978 }
3979 
3980 /*
3981 Generated from the following GLSL + --eliminate-local-multi-store
3982 
3983 #version 440 core
3984 void main() {
3985   int[10] a;
3986   int[10] b;
3987 
3988   int sum_0 = 0;
3989   int sum_1 = 0;
3990 
3991   // No loop-carried dependences, legal
3992   for (int i = 0; i < 10; i++) {
3993     sum_0 += a[i];
3994   }
3995   for (int j = 0; j < 10; j++) {
3996     sum_1 += b[j];
3997   }
3998 
3999   int total = sum_0 + sum_1;
4000 }
4001 
4002 */
TEST_F(FusionLegalTest,IndependentReductionsBothLCSSA)4003 TEST_F(FusionLegalTest, IndependentReductionsBothLCSSA) {
4004   std::string text = R"(
4005                OpCapability Shader
4006           %1 = OpExtInstImport "GLSL.std.450"
4007                OpMemoryModel Logical GLSL450
4008                OpEntryPoint Fragment %4 "main"
4009                OpExecutionMode %4 OriginUpperLeft
4010                OpSource GLSL 440
4011                OpName %4 "main"
4012                OpName %8 "sum_0"
4013                OpName %10 "sum_1"
4014                OpName %11 "i"
4015                OpName %25 "a"
4016                OpName %34 "j"
4017                OpName %42 "b"
4018                OpName %50 "total"
4019           %2 = OpTypeVoid
4020           %3 = OpTypeFunction %2
4021           %6 = OpTypeInt 32 1
4022           %7 = OpTypePointer Function %6
4023           %9 = OpConstant %6 0
4024          %18 = OpConstant %6 10
4025          %19 = OpTypeBool
4026          %21 = OpTypeInt 32 0
4027          %22 = OpConstant %21 10
4028          %23 = OpTypeArray %6 %22
4029          %24 = OpTypePointer Function %23
4030          %32 = OpConstant %6 1
4031           %4 = OpFunction %2 None %3
4032           %5 = OpLabel
4033           %8 = OpVariable %7 Function
4034          %10 = OpVariable %7 Function
4035          %11 = OpVariable %7 Function
4036          %25 = OpVariable %24 Function
4037          %34 = OpVariable %7 Function
4038          %42 = OpVariable %24 Function
4039          %50 = OpVariable %7 Function
4040                OpStore %8 %9
4041                OpStore %10 %9
4042                OpStore %11 %9
4043                OpBranch %12
4044          %12 = OpLabel
4045          %57 = OpPhi %6 %9 %5 %30 %15
4046          %54 = OpPhi %6 %9 %5 %33 %15
4047                OpLoopMerge %14 %15 None
4048                OpBranch %16
4049          %16 = OpLabel
4050          %20 = OpSLessThan %19 %54 %18
4051                OpBranchConditional %20 %13 %14
4052          %13 = OpLabel
4053          %27 = OpAccessChain %7 %25 %54
4054          %28 = OpLoad %6 %27
4055          %30 = OpIAdd %6 %57 %28
4056                OpStore %8 %30
4057                OpBranch %15
4058          %15 = OpLabel
4059          %33 = OpIAdd %6 %54 %32
4060                OpStore %11 %33
4061                OpBranch %12
4062          %14 = OpLabel
4063                OpStore %34 %9
4064                OpBranch %35
4065          %35 = OpLabel
4066          %58 = OpPhi %6 %9 %14 %47 %38
4067          %55 = OpPhi %6 %9 %14 %49 %38
4068                OpLoopMerge %37 %38 None
4069                OpBranch %39
4070          %39 = OpLabel
4071          %41 = OpSLessThan %19 %55 %18
4072                OpBranchConditional %41 %36 %37
4073          %36 = OpLabel
4074          %44 = OpAccessChain %7 %42 %55
4075          %45 = OpLoad %6 %44
4076          %47 = OpIAdd %6 %58 %45
4077                OpStore %10 %47
4078                OpBranch %38
4079          %38 = OpLabel
4080          %49 = OpIAdd %6 %55 %32
4081                OpStore %34 %49
4082                OpBranch %35
4083          %37 = OpLabel
4084          %53 = OpIAdd %6 %57 %58
4085                OpStore %50 %53
4086                OpReturn
4087                OpFunctionEnd
4088     )";
4089 
4090   std::unique_ptr<IRContext> context =
4091       BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
4092                   SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
4093   Module* module = context->module();
4094   EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
4095                              << text << std::endl;
4096   Function& f = *module->begin();
4097 
4098   {
4099     LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
4100     EXPECT_EQ(ld.NumLoops(), 2u);
4101 
4102     auto loops = ld.GetLoopsInBinaryLayoutOrder();
4103 
4104     LoopUtils utils_0(context.get(), loops[0]);
4105     utils_0.MakeLoopClosedSSA();
4106     LoopUtils utils_1(context.get(), loops[1]);
4107     utils_1.MakeLoopClosedSSA();
4108 
4109     LoopFusion fusion(context.get(), loops[0], loops[1]);
4110     EXPECT_TRUE(fusion.AreCompatible());
4111     EXPECT_TRUE(fusion.IsLegal());
4112 
4113     fusion.Fuse();
4114   }
4115 
4116   {
4117     LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
4118     EXPECT_EQ(ld.NumLoops(), 1u);
4119 
4120     std::string checks = R"(
4121 CHECK: [[SUM_0:%\w+]] = OpPhi
4122 CHECK-NEXT: [[SUM_1:%\w+]] = OpPhi
4123 CHECK-NEXT: [[PHI:%\w+]] = OpPhi
4124 CHECK-NEXT: OpLoopMerge
4125 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
4126 CHECK-NEXT: [[LOAD_RES_0:%\w+]] = OpLoad {{%\w+}} [[LOAD_0]]
4127 CHECK-NEXT: [[ADD_RES_0:%\w+]] = OpIAdd {{%\w+}} [[SUM_0]] [[LOAD_RES_0]]
4128 CHECK-NEXT: OpStore {{%\w+}} [[ADD_RES_0]]
4129 CHECK-NOT: OpPhi
4130 CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
4131 CHECK-NEXT: [[LOAD_RES_1:%\w+]] = OpLoad {{%\w+}} [[LOAD_1]]
4132 CHECK-NEXT: [[ADD_RES_1:%\w+]] = OpIAdd {{%\w+}} [[SUM_1]] [[LOAD_RES_1]]
4133 CHECK-NEXT: OpStore {{%\w+}} [[ADD_RES_1]]
4134       )";
4135 
4136     Match(checks, context.get());
4137   }
4138 }
4139 
4140 /*
4141 Generated from the following GLSL + --eliminate-local-multi-store
4142 
4143 #version 440 core
4144 void main() {
4145   int[10] a;
4146   int[10] b;
4147 
4148   int sum_0 = 0;
4149 
4150   // No loop-carried dependences, legal
4151   for (int i = 0; i < 10; i++) {
4152     sum_0 += a[i];
4153   }
4154   for (int j = 0; j < 10; j++) {
4155     a[j] = b[j];
4156   }
4157 }
4158 
4159 */
TEST_F(FusionLegalTest,LoadStoreReductionAndNonLoopCarriedDependence)4160 TEST_F(FusionLegalTest, LoadStoreReductionAndNonLoopCarriedDependence) {
4161   std::string text = R"(
4162                OpCapability Shader
4163           %1 = OpExtInstImport "GLSL.std.450"
4164                OpMemoryModel Logical GLSL450
4165                OpEntryPoint Fragment %4 "main"
4166                OpExecutionMode %4 OriginUpperLeft
4167                OpSource GLSL 440
4168                OpName %4 "main"
4169                OpName %8 "sum_0"
4170                OpName %10 "i"
4171                OpName %24 "a"
4172                OpName %33 "j"
4173                OpName %42 "b"
4174           %2 = OpTypeVoid
4175           %3 = OpTypeFunction %2
4176           %6 = OpTypeInt 32 1
4177           %7 = OpTypePointer Function %6
4178           %9 = OpConstant %6 0
4179          %17 = OpConstant %6 10
4180          %18 = OpTypeBool
4181          %20 = OpTypeInt 32 0
4182          %21 = OpConstant %20 10
4183          %22 = OpTypeArray %6 %21
4184          %23 = OpTypePointer Function %22
4185          %31 = OpConstant %6 1
4186           %4 = OpFunction %2 None %3
4187           %5 = OpLabel
4188           %8 = OpVariable %7 Function
4189          %10 = OpVariable %7 Function
4190          %24 = OpVariable %23 Function
4191          %33 = OpVariable %7 Function
4192          %42 = OpVariable %23 Function
4193                OpStore %8 %9
4194                OpStore %10 %9
4195                OpBranch %11
4196          %11 = OpLabel
4197          %51 = OpPhi %6 %9 %5 %29 %14
4198          %49 = OpPhi %6 %9 %5 %32 %14
4199                OpLoopMerge %13 %14 None
4200                OpBranch %15
4201          %15 = OpLabel
4202          %19 = OpSLessThan %18 %49 %17
4203                OpBranchConditional %19 %12 %13
4204          %12 = OpLabel
4205          %26 = OpAccessChain %7 %24 %49
4206          %27 = OpLoad %6 %26
4207          %29 = OpIAdd %6 %51 %27
4208                OpStore %8 %29
4209                OpBranch %14
4210          %14 = OpLabel
4211          %32 = OpIAdd %6 %49 %31
4212                OpStore %10 %32
4213                OpBranch %11
4214          %13 = OpLabel
4215                OpStore %33 %9
4216                OpBranch %34
4217          %34 = OpLabel
4218          %50 = OpPhi %6 %9 %13 %48 %37
4219                OpLoopMerge %36 %37 None
4220                OpBranch %38
4221          %38 = OpLabel
4222          %40 = OpSLessThan %18 %50 %17
4223                OpBranchConditional %40 %35 %36
4224          %35 = OpLabel
4225          %44 = OpAccessChain %7 %42 %50
4226          %45 = OpLoad %6 %44
4227          %46 = OpAccessChain %7 %24 %50
4228                OpStore %46 %45
4229                OpBranch %37
4230          %37 = OpLabel
4231          %48 = OpIAdd %6 %50 %31
4232                OpStore %33 %48
4233                OpBranch %34
4234          %36 = OpLabel
4235                OpReturn
4236                OpFunctionEnd
4237     )";
4238 
4239   std::unique_ptr<IRContext> context =
4240       BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
4241                   SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
4242   Module* module = context->module();
4243   EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
4244                              << text << std::endl;
4245   Function& f = *module->begin();
4246 
4247   {
4248     LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
4249     EXPECT_EQ(ld.NumLoops(), 2u);
4250 
4251     auto loops = ld.GetLoopsInBinaryLayoutOrder();
4252 
4253     LoopFusion fusion(context.get(), loops[0], loops[1]);
4254     EXPECT_TRUE(fusion.AreCompatible());
4255     // TODO: Loop descriptor doesn't return induction variables but all OpPhi
4256     // in the header and LoopDependenceAnalysis falls over.
4257     // EXPECT_TRUE(fusion.IsLegal());
4258 
4259     // fusion.Fuse();
4260   }
4261 
4262   {
4263     // LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
4264     // EXPECT_EQ(ld.NumLoops(), 1u);
4265 
4266     //       std::string checks = R"(
4267     // CHECK: [[SUM_0:%\w+]] = OpPhi
4268     // CHECK-NEXT: [[PHI:%\w+]] = OpPhi
4269     // CHECK-NEXT: OpLoopMerge
4270     // CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
4271     // CHECK-NEXT: [[LOAD_RES_0:%\w+]] = OpLoad {{%\w+}} [[LOAD_0]]
4272     // CHECK-NEXT: [[ADD_RES_0:%\w+]] = OpIAdd {{%\w+}} [[SUM_0]] [[LOAD_RES_0]]
4273     // CHECK-NEXT: OpStore {{%\w+}} [[ADD_RES_0]]
4274     // CHECK-NOT: OpPhi
4275     // CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
4276     // CHECK-NEXT: [[LOAD_RES_1:%\w+]] = OpLoad {{%\w+}} [[LOAD_1]]
4277     // CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
4278     // CHECK-NEXT: OpStore [[STORE_1]] [[LOAD_RES_1]]
4279     //       )";
4280 
4281     // Match(checks, context.get());
4282   }
4283 }
4284 
4285 /*
4286 Generated from the following GLSL + --eliminate-local-multi-store
4287 
4288 #version 440 core
4289 int x;
4290 void main() {
4291   int[10] a;
4292   int[10] b;
4293 
4294   // Legal.
4295   for (int i = 0; i < 10; i++) {
4296     x += a[i];
4297   }
4298   for (int j = 0; j < 10; j++) {
4299     b[j] = b[j]+1;
4300   }
4301 }
4302 
4303 */
TEST_F(FusionLegalTest,ReductionAndNonLoopCarriedDependence)4304 TEST_F(FusionLegalTest, ReductionAndNonLoopCarriedDependence) {
4305   std::string text = R"(
4306                OpCapability Shader
4307           %1 = OpExtInstImport "GLSL.std.450"
4308                OpMemoryModel Logical GLSL450
4309                OpEntryPoint Fragment %4 "main"
4310                OpExecutionMode %4 OriginUpperLeft
4311                OpSource GLSL 440
4312                OpName %4 "main"
4313                OpName %8 "i"
4314                OpName %20 "x"
4315                OpName %25 "a"
4316                OpName %34 "j"
4317                OpName %42 "b"
4318           %2 = OpTypeVoid
4319           %3 = OpTypeFunction %2
4320           %6 = OpTypeInt 32 1
4321           %7 = OpTypePointer Function %6
4322           %9 = OpConstant %6 0
4323          %16 = OpConstant %6 10
4324          %17 = OpTypeBool
4325          %19 = OpTypePointer Private %6
4326          %20 = OpVariable %19 Private
4327          %21 = OpTypeInt 32 0
4328          %22 = OpConstant %21 10
4329          %23 = OpTypeArray %6 %22
4330          %24 = OpTypePointer Function %23
4331          %32 = OpConstant %6 1
4332           %4 = OpFunction %2 None %3
4333           %5 = OpLabel
4334           %8 = OpVariable %7 Function
4335          %25 = OpVariable %24 Function
4336          %34 = OpVariable %7 Function
4337          %42 = OpVariable %24 Function
4338                OpStore %8 %9
4339                OpBranch %10
4340          %10 = OpLabel
4341          %51 = OpPhi %6 %9 %5 %33 %13
4342                OpLoopMerge %12 %13 None
4343                OpBranch %14
4344          %14 = OpLabel
4345          %18 = OpSLessThan %17 %51 %16
4346                OpBranchConditional %18 %11 %12
4347          %11 = OpLabel
4348          %27 = OpAccessChain %7 %25 %51
4349          %28 = OpLoad %6 %27
4350          %29 = OpLoad %6 %20
4351          %30 = OpIAdd %6 %29 %28
4352                OpStore %20 %30
4353                OpBranch %13
4354          %13 = OpLabel
4355          %33 = OpIAdd %6 %51 %32
4356                OpStore %8 %33
4357                OpBranch %10
4358          %12 = OpLabel
4359                OpStore %34 %9
4360                OpBranch %35
4361          %35 = OpLabel
4362          %52 = OpPhi %6 %9 %12 %50 %38
4363                OpLoopMerge %37 %38 None
4364                OpBranch %39
4365          %39 = OpLabel
4366          %41 = OpSLessThan %17 %52 %16
4367                OpBranchConditional %41 %36 %37
4368          %36 = OpLabel
4369          %45 = OpAccessChain %7 %42 %52
4370          %46 = OpLoad %6 %45
4371          %47 = OpIAdd %6 %46 %32
4372          %48 = OpAccessChain %7 %42 %52
4373                OpStore %48 %47
4374                OpBranch %38
4375          %38 = OpLabel
4376          %50 = OpIAdd %6 %52 %32
4377                OpStore %34 %50
4378                OpBranch %35
4379          %37 = OpLabel
4380                OpReturn
4381                OpFunctionEnd
4382     )";
4383 
4384   std::unique_ptr<IRContext> context =
4385       BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
4386                   SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
4387   Module* module = context->module();
4388   EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
4389                              << text << std::endl;
4390   Function& f = *module->begin();
4391 
4392   {
4393     LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
4394     EXPECT_EQ(ld.NumLoops(), 2u);
4395 
4396     auto loops = ld.GetLoopsInBinaryLayoutOrder();
4397 
4398     LoopFusion fusion(context.get(), loops[0], loops[1]);
4399     EXPECT_TRUE(fusion.AreCompatible());
4400     EXPECT_TRUE(fusion.IsLegal());
4401 
4402     fusion.Fuse();
4403   }
4404 
4405   {
4406     LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
4407     EXPECT_EQ(ld.NumLoops(), 1u);
4408 
4409     std::string checks = R"(
4410 CHECK: OpName [[X:%\w+]] "x"
4411 CHECK: [[PHI:%\w+]] = OpPhi
4412 CHECK-NEXT: OpLoopMerge
4413 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
4414 CHECK-NEXT: [[LOAD_RES_0:%\w+]] = OpLoad {{%\w+}} [[LOAD_0]]
4415 CHECK-NEXT: [[X_LOAD:%\w+]] = OpLoad {{%\w+}} [[X]]
4416 CHECK-NEXT: [[ADD_RES_0:%\w+]] = OpIAdd {{%\w+}} [[X_LOAD]] [[LOAD_RES_0]]
4417 CHECK-NEXT: OpStore [[X]] [[ADD_RES_0]]
4418 CHECK-NOT: OpPhi
4419 CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
4420 CHECK-NEXT: {{%\w+}} = OpLoad {{%\w+}} [[LOAD_1]]
4421 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]]
4422 CHECK-NEXT: OpStore [[STORE_1]]
4423       )";
4424 
4425     Match(checks, context.get());
4426   }
4427 }
4428 
4429 /*
4430 Generated from the following GLSL + --eliminate-local-multi-store
4431 
4432 #version 440 core
4433 struct TestStruct {
4434   int[10] a;
4435   int b;
4436 };
4437 
4438 void main() {
4439   TestStruct test_0;
4440   TestStruct test_1;
4441   TestStruct test_2;
4442 
4443   test_1.b = 2;
4444 
4445   for (int i = 0; i < 10; i++) {
4446     test_0.a[i] = i;
4447   }
4448   for (int j = 0; j < 10; j++) {
4449     test_2 = test_1;
4450   }
4451 }
4452 
4453 */
TEST_F(FusionLegalTest,ArrayInStruct)4454 TEST_F(FusionLegalTest, ArrayInStruct) {
4455   std::string text = R"(
4456                OpCapability Shader
4457           %1 = OpExtInstImport "GLSL.std.450"
4458                OpMemoryModel Logical GLSL450
4459                OpEntryPoint Fragment %4 "main"
4460                OpExecutionMode %4 OriginUpperLeft
4461                OpSource GLSL 440
4462                OpName %4 "main"
4463                OpName %10 "TestStruct"
4464                OpMemberName %10 0 "a"
4465                OpMemberName %10 1 "b"
4466                OpName %12 "test_1"
4467                OpName %17 "i"
4468                OpName %28 "test_0"
4469                OpName %34 "j"
4470                OpName %42 "test_2"
4471           %2 = OpTypeVoid
4472           %3 = OpTypeFunction %2
4473           %6 = OpTypeInt 32 1
4474           %7 = OpTypeInt 32 0
4475           %8 = OpConstant %7 10
4476           %9 = OpTypeArray %6 %8
4477          %10 = OpTypeStruct %9 %6
4478          %11 = OpTypePointer Function %10
4479          %13 = OpConstant %6 1
4480          %14 = OpConstant %6 2
4481          %15 = OpTypePointer Function %6
4482          %18 = OpConstant %6 0
4483          %25 = OpConstant %6 10
4484          %26 = OpTypeBool
4485           %4 = OpFunction %2 None %3
4486           %5 = OpLabel
4487          %12 = OpVariable %11 Function
4488          %17 = OpVariable %15 Function
4489          %28 = OpVariable %11 Function
4490          %34 = OpVariable %15 Function
4491          %42 = OpVariable %11 Function
4492          %16 = OpAccessChain %15 %12 %13
4493                OpStore %16 %14
4494                OpStore %17 %18
4495                OpBranch %19
4496          %19 = OpLabel
4497          %46 = OpPhi %6 %18 %5 %33 %22
4498                OpLoopMerge %21 %22 None
4499                OpBranch %23
4500          %23 = OpLabel
4501          %27 = OpSLessThan %26 %46 %25
4502                OpBranchConditional %27 %20 %21
4503          %20 = OpLabel
4504          %31 = OpAccessChain %15 %28 %18 %46
4505                OpStore %31 %46
4506                OpBranch %22
4507          %22 = OpLabel
4508          %33 = OpIAdd %6 %46 %13
4509                OpStore %17 %33
4510                OpBranch %19
4511          %21 = OpLabel
4512                OpStore %34 %18
4513                OpBranch %35
4514          %35 = OpLabel
4515          %47 = OpPhi %6 %18 %21 %45 %38
4516                OpLoopMerge %37 %38 None
4517                OpBranch %39
4518          %39 = OpLabel
4519          %41 = OpSLessThan %26 %47 %25
4520                OpBranchConditional %41 %36 %37
4521          %36 = OpLabel
4522          %43 = OpLoad %10 %12
4523                OpStore %42 %43
4524                OpBranch %38
4525          %38 = OpLabel
4526          %45 = OpIAdd %6 %47 %13
4527                OpStore %34 %45
4528                OpBranch %35
4529          %37 = OpLabel
4530                OpReturn
4531                OpFunctionEnd
4532     )";
4533 
4534   std::unique_ptr<IRContext> context =
4535       BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
4536                   SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
4537   Module* module = context->module();
4538   EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
4539                              << text << std::endl;
4540   Function& f = *module->begin();
4541 
4542   {
4543     LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
4544     EXPECT_EQ(ld.NumLoops(), 2u);
4545 
4546     auto loops = ld.GetLoopsInBinaryLayoutOrder();
4547 
4548     LoopFusion fusion(context.get(), loops[0], loops[1]);
4549     EXPECT_TRUE(fusion.AreCompatible());
4550     EXPECT_TRUE(fusion.IsLegal());
4551 
4552     fusion.Fuse();
4553   }
4554 
4555   {
4556     LoopDescriptor& ld = *context->GetLoopDescriptor(&f);
4557     EXPECT_EQ(ld.NumLoops(), 1u);
4558 
4559     // clang-format off
4560         std::string checks = R"(
4561 CHECK: OpName [[TEST_1:%\w+]] "test_1"
4562 CHECK: OpName [[TEST_0:%\w+]] "test_0"
4563 CHECK: OpName [[TEST_2:%\w+]] "test_2"
4564 CHECK: [[PHI:%\w+]] = OpPhi
4565 CHECK-NEXT: OpLoopMerge
4566 CHECK: [[TEST_0_STORE:%\w+]] = OpAccessChain {{%\w+}} [[TEST_0]] {{%\w+}} {{%\w+}}
4567 CHECK-NEXT: OpStore [[TEST_0_STORE]] [[PHI]]
4568 CHECK-NOT: OpPhi
4569 CHECK: [[TEST_1_LOAD:%\w+]] = OpLoad {{%\w+}} [[TEST_1]]
4570 CHECK: OpStore [[TEST_2]] [[TEST_1_LOAD]]
4571       )";
4572     // clang-format on
4573 
4574     Match(checks, context.get());
4575   }
4576 }
4577 
4578 }  // namespace
4579 }  // namespace opt
4580 }  // namespace spvtools
4581