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 <string>
16
17#include "effcee/effcee.h"
18#include "gmock/gmock.h"
19#include "test/opt/pass_fixture.h"
20
21namespace spvtools {
22namespace opt {
23namespace {
24
25using FusionPassTest = PassTest<::testing::Test>;
26
27/*
28Generated from the following GLSL + --eliminate-local-multi-store
29
30#version 440 core
31void main() {
32  int[10] a;
33  int[10] b;
34  for (int i = 0; i < 10; i++) {
35    a[i] = a[i]*2;
36  }
37  for (int i = 0; i < 10; i++) {
38    b[i] = a[i]+2;
39  }
40}
41
42*/
43TEST_F(FusionPassTest, SimpleFusion) {
44  const std::string text = R"(
45; CHECK: OpPhi
46; CHECK: OpLoad
47; CHECK: OpStore
48; CHECK-NOT: OpPhi
49; CHECK: OpLoad
50; CHECK: OpStore
51
52               OpCapability Shader
53          %1 = OpExtInstImport "GLSL.std.450"
54               OpMemoryModel Logical GLSL450
55               OpEntryPoint Fragment %4 "main"
56               OpExecutionMode %4 OriginUpperLeft
57               OpSource GLSL 440
58               OpName %4 "main"
59               OpName %8 "i"
60               OpName %23 "a"
61               OpName %34 "i"
62               OpName %42 "b"
63          %2 = OpTypeVoid
64          %3 = OpTypeFunction %2
65          %6 = OpTypeInt 32 1
66          %7 = OpTypePointer Function %6
67          %9 = OpConstant %6 0
68         %16 = OpConstant %6 10
69         %17 = OpTypeBool
70         %19 = OpTypeInt 32 0
71         %20 = OpConstant %19 10
72         %21 = OpTypeArray %6 %20
73         %22 = OpTypePointer Function %21
74         %28 = OpConstant %6 2
75         %32 = OpConstant %6 1
76          %4 = OpFunction %2 None %3
77          %5 = OpLabel
78          %8 = OpVariable %7 Function
79         %23 = OpVariable %22 Function
80         %34 = OpVariable %7 Function
81         %42 = OpVariable %22 Function
82               OpStore %8 %9
83               OpBranch %10
84         %10 = OpLabel
85         %51 = OpPhi %6 %9 %5 %33 %13
86               OpLoopMerge %12 %13 None
87               OpBranch %14
88         %14 = OpLabel
89         %18 = OpSLessThan %17 %51 %16
90               OpBranchConditional %18 %11 %12
91         %11 = OpLabel
92         %26 = OpAccessChain %7 %23 %51
93         %27 = OpLoad %6 %26
94         %29 = OpIMul %6 %27 %28
95         %30 = OpAccessChain %7 %23 %51
96               OpStore %30 %29
97               OpBranch %13
98         %13 = OpLabel
99         %33 = OpIAdd %6 %51 %32
100               OpStore %8 %33
101               OpBranch %10
102         %12 = OpLabel
103               OpStore %34 %9
104               OpBranch %35
105         %35 = OpLabel
106         %52 = OpPhi %6 %9 %12 %50 %38
107               OpLoopMerge %37 %38 None
108               OpBranch %39
109         %39 = OpLabel
110         %41 = OpSLessThan %17 %52 %16
111               OpBranchConditional %41 %36 %37
112         %36 = OpLabel
113         %45 = OpAccessChain %7 %23 %52
114         %46 = OpLoad %6 %45
115         %47 = OpIAdd %6 %46 %28
116         %48 = OpAccessChain %7 %42 %52
117               OpStore %48 %47
118               OpBranch %38
119         %38 = OpLabel
120         %50 = OpIAdd %6 %52 %32
121               OpStore %34 %50
122               OpBranch %35
123         %37 = OpLabel
124               OpReturn
125               OpFunctionEnd
126  )";
127
128  SinglePassRunAndMatch<LoopFusionPass>(text, true, 20);
129}
130
131/*
132Generated from the following GLSL + --eliminate-local-multi-store
133
134#version 440 core
135void main() {
136  int[10] a;
137  int[10] b;
138  int[10] c;
139  for (int i = 0; i < 10; i++) {
140    a[i] = b[i] + 1;
141  }
142  for (int i = 0; i < 10; i++) {
143    c[i] = a[i] + 2;
144  }
145  for (int i = 0; i < 10; i++) {
146    b[i] = c[i] + 10;
147  }
148}
149
150*/
151TEST_F(FusionPassTest, ThreeLoopsFused) {
152  const std::string text = R"(
153; CHECK: OpPhi
154; CHECK: OpLoad
155; CHECK: OpStore
156; CHECK-NOT: OpPhi
157; CHECK: OpLoad
158; CHECK: OpStore
159; CHECK-NOT: OpPhi
160; CHECK: OpLoad
161; CHECK: OpStore
162
163               OpCapability Shader
164          %1 = OpExtInstImport "GLSL.std.450"
165               OpMemoryModel Logical GLSL450
166               OpEntryPoint Fragment %4 "main"
167               OpExecutionMode %4 OriginUpperLeft
168               OpSource GLSL 440
169               OpName %4 "main"
170               OpName %8 "i"
171               OpName %23 "a"
172               OpName %25 "b"
173               OpName %34 "i"
174               OpName %42 "c"
175               OpName %52 "i"
176          %2 = OpTypeVoid
177          %3 = OpTypeFunction %2
178          %6 = OpTypeInt 32 1
179          %7 = OpTypePointer Function %6
180          %9 = OpConstant %6 0
181         %16 = OpConstant %6 10
182         %17 = OpTypeBool
183         %19 = OpTypeInt 32 0
184         %20 = OpConstant %19 10
185         %21 = OpTypeArray %6 %20
186         %22 = OpTypePointer Function %21
187         %29 = OpConstant %6 1
188         %47 = OpConstant %6 2
189          %4 = OpFunction %2 None %3
190          %5 = OpLabel
191          %8 = OpVariable %7 Function
192         %23 = OpVariable %22 Function
193         %25 = OpVariable %22 Function
194         %34 = OpVariable %7 Function
195         %42 = OpVariable %22 Function
196         %52 = OpVariable %7 Function
197               OpStore %8 %9
198               OpBranch %10
199         %10 = OpLabel
200         %68 = OpPhi %6 %9 %5 %33 %13
201               OpLoopMerge %12 %13 None
202               OpBranch %14
203         %14 = OpLabel
204         %18 = OpSLessThan %17 %68 %16
205               OpBranchConditional %18 %11 %12
206         %11 = OpLabel
207         %27 = OpAccessChain %7 %25 %68
208         %28 = OpLoad %6 %27
209         %30 = OpIAdd %6 %28 %29
210         %31 = OpAccessChain %7 %23 %68
211               OpStore %31 %30
212               OpBranch %13
213         %13 = OpLabel
214         %33 = OpIAdd %6 %68 %29
215               OpStore %8 %33
216               OpBranch %10
217         %12 = OpLabel
218               OpStore %34 %9
219               OpBranch %35
220         %35 = OpLabel
221         %69 = OpPhi %6 %9 %12 %51 %38
222               OpLoopMerge %37 %38 None
223               OpBranch %39
224         %39 = OpLabel
225         %41 = OpSLessThan %17 %69 %16
226               OpBranchConditional %41 %36 %37
227         %36 = OpLabel
228         %45 = OpAccessChain %7 %23 %69
229         %46 = OpLoad %6 %45
230         %48 = OpIAdd %6 %46 %47
231         %49 = OpAccessChain %7 %42 %69
232               OpStore %49 %48
233               OpBranch %38
234         %38 = OpLabel
235         %51 = OpIAdd %6 %69 %29
236               OpStore %34 %51
237               OpBranch %35
238         %37 = OpLabel
239               OpStore %52 %9
240               OpBranch %53
241         %53 = OpLabel
242         %70 = OpPhi %6 %9 %37 %67 %56
243               OpLoopMerge %55 %56 None
244               OpBranch %57
245         %57 = OpLabel
246         %59 = OpSLessThan %17 %70 %16
247               OpBranchConditional %59 %54 %55
248         %54 = OpLabel
249         %62 = OpAccessChain %7 %42 %70
250         %63 = OpLoad %6 %62
251         %64 = OpIAdd %6 %63 %16
252         %65 = OpAccessChain %7 %25 %70
253               OpStore %65 %64
254               OpBranch %56
255         %56 = OpLabel
256         %67 = OpIAdd %6 %70 %29
257               OpStore %52 %67
258               OpBranch %53
259         %55 = OpLabel
260               OpReturn
261               OpFunctionEnd
262
263  )";
264
265  SinglePassRunAndMatch<LoopFusionPass>(text, true, 20);
266}
267
268/*
269Generated from the following GLSL + --eliminate-local-multi-store
270
271#version 440 core
272void main() {
273  int[10][10] a;
274  int[10][10] b;
275  int[10][10] c;
276  // Legal both
277  for (int i = 0; i < 10; i++) {
278    for (int j = 0; j < 10; j++) {
279      c[i][j] = a[i][j] + 2;
280    }
281  }
282  for (int i = 0; i < 10; i++) {
283    for (int j = 0; j < 10; j++) {
284      b[i][j] = c[i][j] + 10;
285    }
286  }
287}
288
289*/
290TEST_F(FusionPassTest, NestedLoopsFused) {
291  const std::string text = R"(
292; CHECK: OpPhi
293; CHECK: OpPhi
294; CHECK: OpLoad
295; CHECK: OpStore
296; CHECK-NOT: OpPhi
297; CHECK: OpLoad
298; CHECK: OpStore
299
300               OpCapability Shader
301          %1 = OpExtInstImport "GLSL.std.450"
302               OpMemoryModel Logical GLSL450
303               OpEntryPoint Fragment %4 "main"
304               OpExecutionMode %4 OriginUpperLeft
305               OpSource GLSL 440
306               OpName %4 "main"
307               OpName %8 "i"
308               OpName %19 "j"
309               OpName %32 "c"
310               OpName %35 "a"
311               OpName %48 "i"
312               OpName %56 "j"
313               OpName %64 "b"
314          %2 = OpTypeVoid
315          %3 = OpTypeFunction %2
316          %6 = OpTypeInt 32 1
317          %7 = OpTypePointer Function %6
318          %9 = OpConstant %6 0
319         %16 = OpConstant %6 10
320         %17 = OpTypeBool
321         %27 = OpTypeInt 32 0
322         %28 = OpConstant %27 10
323         %29 = OpTypeArray %6 %28
324         %30 = OpTypeArray %29 %28
325         %31 = OpTypePointer Function %30
326         %40 = OpConstant %6 2
327         %44 = OpConstant %6 1
328          %4 = OpFunction %2 None %3
329          %5 = OpLabel
330          %8 = OpVariable %7 Function
331         %19 = OpVariable %7 Function
332         %32 = OpVariable %31 Function
333         %35 = OpVariable %31 Function
334         %48 = OpVariable %7 Function
335         %56 = OpVariable %7 Function
336         %64 = OpVariable %31 Function
337               OpStore %8 %9
338               OpBranch %10
339         %10 = OpLabel
340         %77 = OpPhi %6 %9 %5 %47 %13
341               OpLoopMerge %12 %13 None
342               OpBranch %14
343         %14 = OpLabel
344         %18 = OpSLessThan %17 %77 %16
345               OpBranchConditional %18 %11 %12
346         %11 = OpLabel
347               OpStore %19 %9
348               OpBranch %20
349         %20 = OpLabel
350         %81 = OpPhi %6 %9 %11 %45 %23
351               OpLoopMerge %22 %23 None
352               OpBranch %24
353         %24 = OpLabel
354         %26 = OpSLessThan %17 %81 %16
355               OpBranchConditional %26 %21 %22
356         %21 = OpLabel
357         %38 = OpAccessChain %7 %35 %77 %81
358         %39 = OpLoad %6 %38
359         %41 = OpIAdd %6 %39 %40
360         %42 = OpAccessChain %7 %32 %77 %81
361               OpStore %42 %41
362               OpBranch %23
363         %23 = OpLabel
364         %45 = OpIAdd %6 %81 %44
365               OpStore %19 %45
366               OpBranch %20
367         %22 = OpLabel
368               OpBranch %13
369         %13 = OpLabel
370         %47 = OpIAdd %6 %77 %44
371               OpStore %8 %47
372               OpBranch %10
373         %12 = OpLabel
374               OpStore %48 %9
375               OpBranch %49
376         %49 = OpLabel
377         %78 = OpPhi %6 %9 %12 %76 %52
378               OpLoopMerge %51 %52 None
379               OpBranch %53
380         %53 = OpLabel
381         %55 = OpSLessThan %17 %78 %16
382               OpBranchConditional %55 %50 %51
383         %50 = OpLabel
384               OpStore %56 %9
385               OpBranch %57
386         %57 = OpLabel
387         %79 = OpPhi %6 %9 %50 %74 %60
388               OpLoopMerge %59 %60 None
389               OpBranch %61
390         %61 = OpLabel
391         %63 = OpSLessThan %17 %79 %16
392               OpBranchConditional %63 %58 %59
393         %58 = OpLabel
394         %69 = OpAccessChain %7 %32 %78 %79
395         %70 = OpLoad %6 %69
396         %71 = OpIAdd %6 %70 %16
397         %72 = OpAccessChain %7 %64 %78 %79
398               OpStore %72 %71
399               OpBranch %60
400         %60 = OpLabel
401         %74 = OpIAdd %6 %79 %44
402               OpStore %56 %74
403               OpBranch %57
404         %59 = OpLabel
405               OpBranch %52
406         %52 = OpLabel
407         %76 = OpIAdd %6 %78 %44
408               OpStore %48 %76
409               OpBranch %49
410         %51 = OpLabel
411               OpReturn
412               OpFunctionEnd
413  )";
414
415  SinglePassRunAndMatch<LoopFusionPass>(text, true, 20);
416}
417
418/*
419Generated from the following GLSL + --eliminate-local-multi-store
420
421#version 440 core
422void main() {
423  // Can't fuse, different step
424  for (int i = 0; i < 10; i++) {}
425  for (int j = 0; j < 10; j=j+2) {}
426}
427
428*/
429TEST_F(FusionPassTest, Incompatible) {
430  const std::string text = R"(
431; CHECK: OpPhi
432; CHECK-NEXT: OpLoopMerge
433; CHECK: OpPhi
434; CHECK-NEXT: OpLoopMerge
435
436               OpCapability Shader
437          %1 = OpExtInstImport "GLSL.std.450"
438               OpMemoryModel Logical GLSL450
439               OpEntryPoint Fragment %4 "main"
440               OpExecutionMode %4 OriginUpperLeft
441               OpSource GLSL 440
442               OpName %4 "main"
443               OpName %8 "i"
444               OpName %22 "j"
445          %2 = OpTypeVoid
446          %3 = OpTypeFunction %2
447          %6 = OpTypeInt 32 1
448          %7 = OpTypePointer Function %6
449          %9 = OpConstant %6 0
450         %16 = OpConstant %6 10
451         %17 = OpTypeBool
452         %20 = OpConstant %6 1
453         %31 = OpConstant %6 2
454          %4 = OpFunction %2 None %3
455          %5 = OpLabel
456          %8 = OpVariable %7 Function
457         %22 = OpVariable %7 Function
458               OpStore %8 %9
459               OpBranch %10
460         %10 = OpLabel
461         %33 = OpPhi %6 %9 %5 %21 %13
462               OpLoopMerge %12 %13 None
463               OpBranch %14
464         %14 = OpLabel
465         %18 = OpSLessThan %17 %33 %16
466               OpBranchConditional %18 %11 %12
467         %11 = OpLabel
468               OpBranch %13
469         %13 = OpLabel
470         %21 = OpIAdd %6 %33 %20
471               OpStore %8 %21
472               OpBranch %10
473         %12 = OpLabel
474               OpStore %22 %9
475               OpBranch %23
476         %23 = OpLabel
477         %34 = OpPhi %6 %9 %12 %32 %26
478               OpLoopMerge %25 %26 None
479               OpBranch %27
480         %27 = OpLabel
481         %29 = OpSLessThan %17 %34 %16
482               OpBranchConditional %29 %24 %25
483         %24 = OpLabel
484               OpBranch %26
485         %26 = OpLabel
486         %32 = OpIAdd %6 %34 %31
487               OpStore %22 %32
488               OpBranch %23
489         %25 = OpLabel
490               OpReturn
491               OpFunctionEnd
492  )";
493
494  SinglePassRunAndMatch<LoopFusionPass>(text, true, 20);
495}
496
497/*
498Generated from the following GLSL + --eliminate-local-multi-store
499
500#version 440 core
501void main() {
502  int[10] a;
503  int[10] b;
504  int[10] c;
505  // Illegal, loop-independent dependence will become a
506  // backward loop-carried antidependence
507  for (int i = 0; i < 10; i++) {
508    a[i] = b[i] + 1;
509  }
510  for (int i = 0; i < 10; i++) {
511    c[i] = a[i+1] + 2;
512  }
513}
514
515*/
516TEST_F(FusionPassTest, Illegal) {
517  std::string text = R"(
518; CHECK: OpPhi
519; CHECK-NEXT: OpLoopMerge
520; CHECK: OpLoad
521; CHECK: OpStore
522; CHECK: OpPhi
523; CHECK-NEXT: OpLoopMerge
524; CHECK: OpLoad
525; CHECK: OpStore
526
527               OpCapability Shader
528          %1 = OpExtInstImport "GLSL.std.450"
529               OpMemoryModel Logical GLSL450
530               OpEntryPoint Fragment %4 "main"
531               OpExecutionMode %4 OriginUpperLeft
532               OpSource GLSL 440
533               OpName %4 "main"
534               OpName %8 "i"
535               OpName %23 "a"
536               OpName %25 "b"
537               OpName %34 "i"
538               OpName %42 "c"
539          %2 = OpTypeVoid
540          %3 = OpTypeFunction %2
541          %6 = OpTypeInt 32 1
542          %7 = OpTypePointer Function %6
543          %9 = OpConstant %6 0
544         %16 = OpConstant %6 10
545         %17 = OpTypeBool
546         %19 = OpTypeInt 32 0
547         %20 = OpConstant %19 10
548         %21 = OpTypeArray %6 %20
549         %22 = OpTypePointer Function %21
550         %29 = OpConstant %6 1
551         %48 = OpConstant %6 2
552          %4 = OpFunction %2 None %3
553          %5 = OpLabel
554          %8 = OpVariable %7 Function
555         %23 = OpVariable %22 Function
556         %25 = OpVariable %22 Function
557         %34 = OpVariable %7 Function
558         %42 = OpVariable %22 Function
559               OpStore %8 %9
560               OpBranch %10
561         %10 = OpLabel
562         %53 = OpPhi %6 %9 %5 %33 %13
563               OpLoopMerge %12 %13 None
564               OpBranch %14
565         %14 = OpLabel
566         %18 = OpSLessThan %17 %53 %16
567               OpBranchConditional %18 %11 %12
568         %11 = OpLabel
569         %27 = OpAccessChain %7 %25 %53
570         %28 = OpLoad %6 %27
571         %30 = OpIAdd %6 %28 %29
572         %31 = OpAccessChain %7 %23 %53
573               OpStore %31 %30
574               OpBranch %13
575         %13 = OpLabel
576         %33 = OpIAdd %6 %53 %29
577               OpStore %8 %33
578               OpBranch %10
579         %12 = OpLabel
580               OpStore %34 %9
581               OpBranch %35
582         %35 = OpLabel
583         %54 = OpPhi %6 %9 %12 %52 %38
584               OpLoopMerge %37 %38 None
585               OpBranch %39
586         %39 = OpLabel
587         %41 = OpSLessThan %17 %54 %16
588               OpBranchConditional %41 %36 %37
589         %36 = OpLabel
590         %45 = OpIAdd %6 %54 %29
591         %46 = OpAccessChain %7 %23 %45
592         %47 = OpLoad %6 %46
593         %49 = OpIAdd %6 %47 %48
594         %50 = OpAccessChain %7 %42 %54
595               OpStore %50 %49
596               OpBranch %38
597         %38 = OpLabel
598         %52 = OpIAdd %6 %54 %29
599               OpStore %34 %52
600               OpBranch %35
601         %37 = OpLabel
602               OpReturn
603               OpFunctionEnd
604    )";
605
606  SinglePassRunAndMatch<LoopFusionPass>(text, true, 20);
607}
608
609/*
610Generated from the following GLSL + --eliminate-local-multi-store
611
612#version 440 core
613void main() {
614  int[10] a;
615  int[10] b;
616  for (int i = 0; i < 10; i++) {
617    a[i] = a[i]*2;
618  }
619  for (int i = 0; i < 10; i++) {
620    b[i] = a[i]+2;
621  }
622}
623
624*/
625TEST_F(FusionPassTest, TooManyRegisters) {
626  const std::string text = R"(
627; CHECK: OpPhi
628; CHECK-NEXT: OpLoopMerge
629; CHECK: OpLoad
630; CHECK: OpStore
631; CHECK: OpPhi
632; CHECK-NEXT: OpLoopMerge
633; CHECK: OpLoad
634; CHECK: OpStore
635
636               OpCapability Shader
637          %1 = OpExtInstImport "GLSL.std.450"
638               OpMemoryModel Logical GLSL450
639               OpEntryPoint Fragment %4 "main"
640               OpExecutionMode %4 OriginUpperLeft
641               OpSource GLSL 440
642               OpName %4 "main"
643               OpName %8 "i"
644               OpName %23 "a"
645               OpName %34 "i"
646               OpName %42 "b"
647          %2 = OpTypeVoid
648          %3 = OpTypeFunction %2
649          %6 = OpTypeInt 32 1
650          %7 = OpTypePointer Function %6
651          %9 = OpConstant %6 0
652         %16 = OpConstant %6 10
653         %17 = OpTypeBool
654         %19 = OpTypeInt 32 0
655         %20 = OpConstant %19 10
656         %21 = OpTypeArray %6 %20
657         %22 = OpTypePointer Function %21
658         %28 = OpConstant %6 2
659         %32 = OpConstant %6 1
660          %4 = OpFunction %2 None %3
661          %5 = OpLabel
662          %8 = OpVariable %7 Function
663         %23 = OpVariable %22 Function
664         %34 = OpVariable %7 Function
665         %42 = OpVariable %22 Function
666               OpStore %8 %9
667               OpBranch %10
668         %10 = OpLabel
669         %51 = OpPhi %6 %9 %5 %33 %13
670               OpLoopMerge %12 %13 None
671               OpBranch %14
672         %14 = OpLabel
673         %18 = OpSLessThan %17 %51 %16
674               OpBranchConditional %18 %11 %12
675         %11 = OpLabel
676         %26 = OpAccessChain %7 %23 %51
677         %27 = OpLoad %6 %26
678         %29 = OpIMul %6 %27 %28
679         %30 = OpAccessChain %7 %23 %51
680               OpStore %30 %29
681               OpBranch %13
682         %13 = OpLabel
683         %33 = OpIAdd %6 %51 %32
684               OpStore %8 %33
685               OpBranch %10
686         %12 = OpLabel
687               OpStore %34 %9
688               OpBranch %35
689         %35 = OpLabel
690         %52 = OpPhi %6 %9 %12 %50 %38
691               OpLoopMerge %37 %38 None
692               OpBranch %39
693         %39 = OpLabel
694         %41 = OpSLessThan %17 %52 %16
695               OpBranchConditional %41 %36 %37
696         %36 = OpLabel
697         %45 = OpAccessChain %7 %23 %52
698         %46 = OpLoad %6 %45
699         %47 = OpIAdd %6 %46 %28
700         %48 = OpAccessChain %7 %42 %52
701               OpStore %48 %47
702               OpBranch %38
703         %38 = OpLabel
704         %50 = OpIAdd %6 %52 %32
705               OpStore %34 %50
706               OpBranch %35
707         %37 = OpLabel
708               OpReturn
709               OpFunctionEnd
710  )";
711
712  SinglePassRunAndMatch<LoopFusionPass>(text, true, 5);
713}
714
715}  // namespace
716}  // namespace opt
717}  // namespace spvtools
718