1 // Copyright (c) 2018 Google LLC.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #include <memory>
16 #include <string>
17 #include <unordered_set>
18 #include <vector>
19
20 #include "gmock/gmock.h"
21 #include "source/opt/iterator.h"
22 #include "source/opt/loop_dependence.h"
23 #include "source/opt/loop_descriptor.h"
24 #include "source/opt/pass.h"
25 #include "source/opt/scalar_analysis.h"
26 #include "source/opt/tree_iterator.h"
27 #include "test/opt/assembly_builder.h"
28 #include "test/opt/function_utils.h"
29 #include "test/opt/pass_fixture.h"
30 #include "test/opt/pass_utils.h"
31
32 namespace spvtools {
33 namespace opt {
34 namespace {
35
36 using DependencyAnalysisHelpers = ::testing::Test;
37
38 /*
39 Generated from the following GLSL fragment shader
40 with --eliminate-local-multi-store
41 #version 440 core
42 void a() {
43 int[10][10] arr;
44 int i = 0;
45 int j = 0;
46 for (; i < 10 && j < 10; i++, j++) {
47 arr[i][j] = arr[i][j];
48 }
49 }
50 void b() {
51 int[10] arr;
52 for (int i = 0; i < 10; i+=2) {
53 arr[i] = arr[i];
54 }
55 }
56 void main(){
57 a();
58 b();
59 }
60 */
TEST(DependencyAnalysisHelpers,UnsupportedLoops)61 TEST(DependencyAnalysisHelpers, UnsupportedLoops) {
62 const std::string text = R"( OpCapability Shader
63 %1 = OpExtInstImport "GLSL.std.450"
64 OpMemoryModel Logical GLSL450
65 OpEntryPoint Fragment %4 "main"
66 OpExecutionMode %4 OriginUpperLeft
67 OpSource GLSL 440
68 OpName %4 "main"
69 OpName %6 "a("
70 OpName %8 "b("
71 OpName %12 "i"
72 OpName %14 "j"
73 OpName %32 "arr"
74 OpName %45 "i"
75 OpName %54 "arr"
76 %2 = OpTypeVoid
77 %3 = OpTypeFunction %2
78 %10 = OpTypeInt 32 1
79 %11 = OpTypePointer Function %10
80 %13 = OpConstant %10 0
81 %21 = OpConstant %10 10
82 %22 = OpTypeBool
83 %27 = OpTypeInt 32 0
84 %28 = OpConstant %27 10
85 %29 = OpTypeArray %10 %28
86 %30 = OpTypeArray %29 %28
87 %31 = OpTypePointer Function %30
88 %41 = OpConstant %10 1
89 %53 = OpTypePointer Function %29
90 %60 = OpConstant %10 2
91 %4 = OpFunction %2 None %3
92 %5 = OpLabel
93 %63 = OpFunctionCall %2 %6
94 %64 = OpFunctionCall %2 %8
95 OpReturn
96 OpFunctionEnd
97 %6 = OpFunction %2 None %3
98 %7 = OpLabel
99 %12 = OpVariable %11 Function
100 %14 = OpVariable %11 Function
101 %32 = OpVariable %31 Function
102 OpStore %12 %13
103 OpStore %14 %13
104 OpBranch %15
105 %15 = OpLabel
106 %65 = OpPhi %10 %13 %7 %42 %18
107 %66 = OpPhi %10 %13 %7 %44 %18
108 OpLoopMerge %17 %18 None
109 OpBranch %19
110 %19 = OpLabel
111 %23 = OpSLessThan %22 %65 %21
112 %25 = OpSLessThan %22 %66 %21
113 %26 = OpLogicalAnd %22 %23 %25
114 OpBranchConditional %26 %16 %17
115 %16 = OpLabel
116 %37 = OpAccessChain %11 %32 %65 %66
117 %38 = OpLoad %10 %37
118 %39 = OpAccessChain %11 %32 %65 %66
119 OpStore %39 %38
120 OpBranch %18
121 %18 = OpLabel
122 %42 = OpIAdd %10 %65 %41
123 OpStore %12 %42
124 %44 = OpIAdd %10 %66 %41
125 OpStore %14 %44
126 OpBranch %15
127 %17 = OpLabel
128 OpReturn
129 OpFunctionEnd
130 %8 = OpFunction %2 None %3
131 %9 = OpLabel
132 %45 = OpVariable %11 Function
133 %54 = OpVariable %53 Function
134 OpStore %45 %13
135 OpBranch %46
136 %46 = OpLabel
137 %67 = OpPhi %10 %13 %9 %62 %49
138 OpLoopMerge %48 %49 None
139 OpBranch %50
140 %50 = OpLabel
141 %52 = OpSLessThan %22 %67 %21
142 OpBranchConditional %52 %47 %48
143 %47 = OpLabel
144 %57 = OpAccessChain %11 %54 %67
145 %58 = OpLoad %10 %57
146 %59 = OpAccessChain %11 %54 %67
147 OpStore %59 %58
148 OpBranch %49
149 %49 = OpLabel
150 %62 = OpIAdd %10 %67 %60
151 OpStore %45 %62
152 OpBranch %46
153 %48 = OpLabel
154 OpReturn
155 OpFunctionEnd
156 )";
157 std::unique_ptr<IRContext> context =
158 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
159 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
160 Module* module = context->module();
161 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
162 << text << std::endl;
163 {
164 // Function a
165 const Function* f = spvtest::GetFunction(module, 6);
166 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
167
168 Loop* loop = &ld.GetLoopByIndex(0);
169 std::vector<const Loop*> loops{loop};
170 LoopDependenceAnalysis analysis{context.get(), loops};
171
172 const Instruction* store[1] = {nullptr};
173 int stores_found = 0;
174 for (const Instruction& inst : *spvtest::GetBasicBlock(f, 16)) {
175 if (inst.opcode() == SpvOp::SpvOpStore) {
176 store[stores_found] = &inst;
177 ++stores_found;
178 }
179 }
180 // 38 -> 39
181 DistanceVector distance_vector{loops.size()};
182 EXPECT_FALSE(analysis.IsSupportedLoop(loops[0]));
183 EXPECT_FALSE(analysis.GetDependence(context->get_def_use_mgr()->GetDef(38),
184 store[0], &distance_vector));
185 EXPECT_EQ(distance_vector.GetEntries()[0].dependence_information,
186 DistanceEntry::DependenceInformation::UNKNOWN);
187 EXPECT_EQ(distance_vector.GetEntries()[0].direction,
188 DistanceEntry::Directions::ALL);
189 }
190 {
191 // Function b
192 const Function* f = spvtest::GetFunction(module, 8);
193 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
194
195 Loop* loop = &ld.GetLoopByIndex(0);
196 std::vector<const Loop*> loops{loop};
197 LoopDependenceAnalysis analysis{context.get(), loops};
198
199 const Instruction* store[1] = {nullptr};
200 int stores_found = 0;
201 for (const Instruction& inst : *spvtest::GetBasicBlock(f, 47)) {
202 if (inst.opcode() == SpvOp::SpvOpStore) {
203 store[stores_found] = &inst;
204 ++stores_found;
205 }
206 }
207 // 58 -> 59
208 DistanceVector distance_vector{loops.size()};
209 EXPECT_FALSE(analysis.IsSupportedLoop(loops[0]));
210 EXPECT_FALSE(analysis.GetDependence(context->get_def_use_mgr()->GetDef(58),
211 store[0], &distance_vector));
212 EXPECT_EQ(distance_vector.GetEntries()[0].dependence_information,
213 DistanceEntry::DependenceInformation::UNKNOWN);
214 EXPECT_EQ(distance_vector.GetEntries()[0].direction,
215 DistanceEntry::Directions::ALL);
216 }
217 }
218
219 /*
220 Generated from the following GLSL fragment shader
221 with --eliminate-local-multi-store
222 #version 440 core
223 void a() {
224 for (int i = -10; i < 0; i++) {
225
226 }
227 }
228 void b() {
229 for (int i = -5; i < 5; i++) {
230
231 }
232 }
233 void c() {
234 for (int i = 0; i < 10; i++) {
235
236 }
237 }
238 void d() {
239 for (int i = 5; i < 15; i++) {
240
241 }
242 }
243 void e() {
244 for (int i = -10; i <= 0; i++) {
245
246 }
247 }
248 void f() {
249 for (int i = -5; i <= 5; i++) {
250
251 }
252 }
253 void g() {
254 for (int i = 0; i <= 10; i++) {
255
256 }
257 }
258 void h() {
259 for (int i = 5; i <= 15; i++) {
260
261 }
262 }
263 void i() {
264 for (int i = 0; i > -10; i--) {
265
266 }
267 }
268 void j() {
269 for (int i = 5; i > -5; i--) {
270
271 }
272 }
273 void k() {
274 for (int i = 10; i > 0; i--) {
275
276 }
277 }
278 void l() {
279 for (int i = 15; i > 5; i--) {
280
281 }
282 }
283 void m() {
284 for (int i = 0; i >= -10; i--) {
285
286 }
287 }
288 void n() {
289 for (int i = 5; i >= -5; i--) {
290
291 }
292 }
293 void o() {
294 for (int i = 10; i >= 0; i--) {
295
296 }
297 }
298 void p() {
299 for (int i = 15; i >= 5; i--) {
300
301 }
302 }
303 void main(){
304 a();
305 b();
306 c();
307 d();
308 e();
309 f();
310 g();
311 h();
312 i();
313 j();
314 k();
315 l();
316 m();
317 n();
318 o();
319 p();
320 }
321 */
TEST(DependencyAnalysisHelpers,loop_information)322 TEST(DependencyAnalysisHelpers, loop_information) {
323 const std::string text = R"( OpCapability Shader
324 %1 = OpExtInstImport "GLSL.std.450"
325 OpMemoryModel Logical GLSL450
326 OpEntryPoint Fragment %4 "main"
327 OpExecutionMode %4 OriginUpperLeft
328 OpSource GLSL 440
329 OpName %4 "main"
330 OpName %6 "a("
331 OpName %8 "b("
332 OpName %10 "c("
333 OpName %12 "d("
334 OpName %14 "e("
335 OpName %16 "f("
336 OpName %18 "g("
337 OpName %20 "h("
338 OpName %22 "i("
339 OpName %24 "j("
340 OpName %26 "k("
341 OpName %28 "l("
342 OpName %30 "m("
343 OpName %32 "n("
344 OpName %34 "o("
345 OpName %36 "p("
346 OpName %40 "i"
347 OpName %54 "i"
348 OpName %66 "i"
349 OpName %77 "i"
350 OpName %88 "i"
351 OpName %98 "i"
352 OpName %108 "i"
353 OpName %118 "i"
354 OpName %128 "i"
355 OpName %138 "i"
356 OpName %148 "i"
357 OpName %158 "i"
358 OpName %168 "i"
359 OpName %178 "i"
360 OpName %188 "i"
361 OpName %198 "i"
362 %2 = OpTypeVoid
363 %3 = OpTypeFunction %2
364 %38 = OpTypeInt 32 1
365 %39 = OpTypePointer Function %38
366 %41 = OpConstant %38 -10
367 %48 = OpConstant %38 0
368 %49 = OpTypeBool
369 %52 = OpConstant %38 1
370 %55 = OpConstant %38 -5
371 %62 = OpConstant %38 5
372 %73 = OpConstant %38 10
373 %84 = OpConstant %38 15
374 %4 = OpFunction %2 None %3
375 %5 = OpLabel
376 %208 = OpFunctionCall %2 %6
377 %209 = OpFunctionCall %2 %8
378 %210 = OpFunctionCall %2 %10
379 %211 = OpFunctionCall %2 %12
380 %212 = OpFunctionCall %2 %14
381 %213 = OpFunctionCall %2 %16
382 %214 = OpFunctionCall %2 %18
383 %215 = OpFunctionCall %2 %20
384 %216 = OpFunctionCall %2 %22
385 %217 = OpFunctionCall %2 %24
386 %218 = OpFunctionCall %2 %26
387 %219 = OpFunctionCall %2 %28
388 %220 = OpFunctionCall %2 %30
389 %221 = OpFunctionCall %2 %32
390 %222 = OpFunctionCall %2 %34
391 %223 = OpFunctionCall %2 %36
392 OpReturn
393 OpFunctionEnd
394 %6 = OpFunction %2 None %3
395 %7 = OpLabel
396 %40 = OpVariable %39 Function
397 OpStore %40 %41
398 OpBranch %42
399 %42 = OpLabel
400 %224 = OpPhi %38 %41 %7 %53 %45
401 OpLoopMerge %44 %45 None
402 OpBranch %46
403 %46 = OpLabel
404 %50 = OpSLessThan %49 %224 %48
405 OpBranchConditional %50 %43 %44
406 %43 = OpLabel
407 OpBranch %45
408 %45 = OpLabel
409 %53 = OpIAdd %38 %224 %52
410 OpStore %40 %53
411 OpBranch %42
412 %44 = OpLabel
413 OpReturn
414 OpFunctionEnd
415 %8 = OpFunction %2 None %3
416 %9 = OpLabel
417 %54 = OpVariable %39 Function
418 OpStore %54 %55
419 OpBranch %56
420 %56 = OpLabel
421 %225 = OpPhi %38 %55 %9 %65 %59
422 OpLoopMerge %58 %59 None
423 OpBranch %60
424 %60 = OpLabel
425 %63 = OpSLessThan %49 %225 %62
426 OpBranchConditional %63 %57 %58
427 %57 = OpLabel
428 OpBranch %59
429 %59 = OpLabel
430 %65 = OpIAdd %38 %225 %52
431 OpStore %54 %65
432 OpBranch %56
433 %58 = OpLabel
434 OpReturn
435 OpFunctionEnd
436 %10 = OpFunction %2 None %3
437 %11 = OpLabel
438 %66 = OpVariable %39 Function
439 OpStore %66 %48
440 OpBranch %67
441 %67 = OpLabel
442 %226 = OpPhi %38 %48 %11 %76 %70
443 OpLoopMerge %69 %70 None
444 OpBranch %71
445 %71 = OpLabel
446 %74 = OpSLessThan %49 %226 %73
447 OpBranchConditional %74 %68 %69
448 %68 = OpLabel
449 OpBranch %70
450 %70 = OpLabel
451 %76 = OpIAdd %38 %226 %52
452 OpStore %66 %76
453 OpBranch %67
454 %69 = OpLabel
455 OpReturn
456 OpFunctionEnd
457 %12 = OpFunction %2 None %3
458 %13 = OpLabel
459 %77 = OpVariable %39 Function
460 OpStore %77 %62
461 OpBranch %78
462 %78 = OpLabel
463 %227 = OpPhi %38 %62 %13 %87 %81
464 OpLoopMerge %80 %81 None
465 OpBranch %82
466 %82 = OpLabel
467 %85 = OpSLessThan %49 %227 %84
468 OpBranchConditional %85 %79 %80
469 %79 = OpLabel
470 OpBranch %81
471 %81 = OpLabel
472 %87 = OpIAdd %38 %227 %52
473 OpStore %77 %87
474 OpBranch %78
475 %80 = OpLabel
476 OpReturn
477 OpFunctionEnd
478 %14 = OpFunction %2 None %3
479 %15 = OpLabel
480 %88 = OpVariable %39 Function
481 OpStore %88 %41
482 OpBranch %89
483 %89 = OpLabel
484 %228 = OpPhi %38 %41 %15 %97 %92
485 OpLoopMerge %91 %92 None
486 OpBranch %93
487 %93 = OpLabel
488 %95 = OpSLessThanEqual %49 %228 %48
489 OpBranchConditional %95 %90 %91
490 %90 = OpLabel
491 OpBranch %92
492 %92 = OpLabel
493 %97 = OpIAdd %38 %228 %52
494 OpStore %88 %97
495 OpBranch %89
496 %91 = OpLabel
497 OpReturn
498 OpFunctionEnd
499 %16 = OpFunction %2 None %3
500 %17 = OpLabel
501 %98 = OpVariable %39 Function
502 OpStore %98 %55
503 OpBranch %99
504 %99 = OpLabel
505 %229 = OpPhi %38 %55 %17 %107 %102
506 OpLoopMerge %101 %102 None
507 OpBranch %103
508 %103 = OpLabel
509 %105 = OpSLessThanEqual %49 %229 %62
510 OpBranchConditional %105 %100 %101
511 %100 = OpLabel
512 OpBranch %102
513 %102 = OpLabel
514 %107 = OpIAdd %38 %229 %52
515 OpStore %98 %107
516 OpBranch %99
517 %101 = OpLabel
518 OpReturn
519 OpFunctionEnd
520 %18 = OpFunction %2 None %3
521 %19 = OpLabel
522 %108 = OpVariable %39 Function
523 OpStore %108 %48
524 OpBranch %109
525 %109 = OpLabel
526 %230 = OpPhi %38 %48 %19 %117 %112
527 OpLoopMerge %111 %112 None
528 OpBranch %113
529 %113 = OpLabel
530 %115 = OpSLessThanEqual %49 %230 %73
531 OpBranchConditional %115 %110 %111
532 %110 = OpLabel
533 OpBranch %112
534 %112 = OpLabel
535 %117 = OpIAdd %38 %230 %52
536 OpStore %108 %117
537 OpBranch %109
538 %111 = OpLabel
539 OpReturn
540 OpFunctionEnd
541 %20 = OpFunction %2 None %3
542 %21 = OpLabel
543 %118 = OpVariable %39 Function
544 OpStore %118 %62
545 OpBranch %119
546 %119 = OpLabel
547 %231 = OpPhi %38 %62 %21 %127 %122
548 OpLoopMerge %121 %122 None
549 OpBranch %123
550 %123 = OpLabel
551 %125 = OpSLessThanEqual %49 %231 %84
552 OpBranchConditional %125 %120 %121
553 %120 = OpLabel
554 OpBranch %122
555 %122 = OpLabel
556 %127 = OpIAdd %38 %231 %52
557 OpStore %118 %127
558 OpBranch %119
559 %121 = OpLabel
560 OpReturn
561 OpFunctionEnd
562 %22 = OpFunction %2 None %3
563 %23 = OpLabel
564 %128 = OpVariable %39 Function
565 OpStore %128 %48
566 OpBranch %129
567 %129 = OpLabel
568 %232 = OpPhi %38 %48 %23 %137 %132
569 OpLoopMerge %131 %132 None
570 OpBranch %133
571 %133 = OpLabel
572 %135 = OpSGreaterThan %49 %232 %41
573 OpBranchConditional %135 %130 %131
574 %130 = OpLabel
575 OpBranch %132
576 %132 = OpLabel
577 %137 = OpISub %38 %232 %52
578 OpStore %128 %137
579 OpBranch %129
580 %131 = OpLabel
581 OpReturn
582 OpFunctionEnd
583 %24 = OpFunction %2 None %3
584 %25 = OpLabel
585 %138 = OpVariable %39 Function
586 OpStore %138 %62
587 OpBranch %139
588 %139 = OpLabel
589 %233 = OpPhi %38 %62 %25 %147 %142
590 OpLoopMerge %141 %142 None
591 OpBranch %143
592 %143 = OpLabel
593 %145 = OpSGreaterThan %49 %233 %55
594 OpBranchConditional %145 %140 %141
595 %140 = OpLabel
596 OpBranch %142
597 %142 = OpLabel
598 %147 = OpISub %38 %233 %52
599 OpStore %138 %147
600 OpBranch %139
601 %141 = OpLabel
602 OpReturn
603 OpFunctionEnd
604 %26 = OpFunction %2 None %3
605 %27 = OpLabel
606 %148 = OpVariable %39 Function
607 OpStore %148 %73
608 OpBranch %149
609 %149 = OpLabel
610 %234 = OpPhi %38 %73 %27 %157 %152
611 OpLoopMerge %151 %152 None
612 OpBranch %153
613 %153 = OpLabel
614 %155 = OpSGreaterThan %49 %234 %48
615 OpBranchConditional %155 %150 %151
616 %150 = OpLabel
617 OpBranch %152
618 %152 = OpLabel
619 %157 = OpISub %38 %234 %52
620 OpStore %148 %157
621 OpBranch %149
622 %151 = OpLabel
623 OpReturn
624 OpFunctionEnd
625 %28 = OpFunction %2 None %3
626 %29 = OpLabel
627 %158 = OpVariable %39 Function
628 OpStore %158 %84
629 OpBranch %159
630 %159 = OpLabel
631 %235 = OpPhi %38 %84 %29 %167 %162
632 OpLoopMerge %161 %162 None
633 OpBranch %163
634 %163 = OpLabel
635 %165 = OpSGreaterThan %49 %235 %62
636 OpBranchConditional %165 %160 %161
637 %160 = OpLabel
638 OpBranch %162
639 %162 = OpLabel
640 %167 = OpISub %38 %235 %52
641 OpStore %158 %167
642 OpBranch %159
643 %161 = OpLabel
644 OpReturn
645 OpFunctionEnd
646 %30 = OpFunction %2 None %3
647 %31 = OpLabel
648 %168 = OpVariable %39 Function
649 OpStore %168 %48
650 OpBranch %169
651 %169 = OpLabel
652 %236 = OpPhi %38 %48 %31 %177 %172
653 OpLoopMerge %171 %172 None
654 OpBranch %173
655 %173 = OpLabel
656 %175 = OpSGreaterThanEqual %49 %236 %41
657 OpBranchConditional %175 %170 %171
658 %170 = OpLabel
659 OpBranch %172
660 %172 = OpLabel
661 %177 = OpISub %38 %236 %52
662 OpStore %168 %177
663 OpBranch %169
664 %171 = OpLabel
665 OpReturn
666 OpFunctionEnd
667 %32 = OpFunction %2 None %3
668 %33 = OpLabel
669 %178 = OpVariable %39 Function
670 OpStore %178 %62
671 OpBranch %179
672 %179 = OpLabel
673 %237 = OpPhi %38 %62 %33 %187 %182
674 OpLoopMerge %181 %182 None
675 OpBranch %183
676 %183 = OpLabel
677 %185 = OpSGreaterThanEqual %49 %237 %55
678 OpBranchConditional %185 %180 %181
679 %180 = OpLabel
680 OpBranch %182
681 %182 = OpLabel
682 %187 = OpISub %38 %237 %52
683 OpStore %178 %187
684 OpBranch %179
685 %181 = OpLabel
686 OpReturn
687 OpFunctionEnd
688 %34 = OpFunction %2 None %3
689 %35 = OpLabel
690 %188 = OpVariable %39 Function
691 OpStore %188 %73
692 OpBranch %189
693 %189 = OpLabel
694 %238 = OpPhi %38 %73 %35 %197 %192
695 OpLoopMerge %191 %192 None
696 OpBranch %193
697 %193 = OpLabel
698 %195 = OpSGreaterThanEqual %49 %238 %48
699 OpBranchConditional %195 %190 %191
700 %190 = OpLabel
701 OpBranch %192
702 %192 = OpLabel
703 %197 = OpISub %38 %238 %52
704 OpStore %188 %197
705 OpBranch %189
706 %191 = OpLabel
707 OpReturn
708 OpFunctionEnd
709 %36 = OpFunction %2 None %3
710 %37 = OpLabel
711 %198 = OpVariable %39 Function
712 OpStore %198 %84
713 OpBranch %199
714 %199 = OpLabel
715 %239 = OpPhi %38 %84 %37 %207 %202
716 OpLoopMerge %201 %202 None
717 OpBranch %203
718 %203 = OpLabel
719 %205 = OpSGreaterThanEqual %49 %239 %62
720 OpBranchConditional %205 %200 %201
721 %200 = OpLabel
722 OpBranch %202
723 %202 = OpLabel
724 %207 = OpISub %38 %239 %52
725 OpStore %198 %207
726 OpBranch %199
727 %201 = OpLabel
728 OpReturn
729 OpFunctionEnd
730 )";
731 std::unique_ptr<IRContext> context =
732 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
733 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
734 Module* module = context->module();
735 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
736 << text << std::endl;
737 {
738 // Function a
739 const Function* f = spvtest::GetFunction(module, 6);
740 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
741 Loop* loop = &ld.GetLoopByIndex(0);
742 std::vector<const Loop*> loops{loop};
743 LoopDependenceAnalysis analysis{context.get(), loops};
744
745 EXPECT_EQ(
746 analysis.GetLowerBound(loop)->AsSEConstantNode()->FoldToSingleValue(),
747 -10);
748 EXPECT_EQ(
749 analysis.GetUpperBound(loop)->AsSEConstantNode()->FoldToSingleValue(),
750 -1);
751
752 EXPECT_EQ(
753 analysis.GetTripCount(loop)->AsSEConstantNode()->FoldToSingleValue(),
754 10);
755
756 EXPECT_EQ(analysis.GetFirstTripInductionNode(loop),
757 analysis.GetScalarEvolution()->CreateConstant(-10));
758
759 EXPECT_EQ(analysis.GetFinalTripInductionNode(
760 loop, analysis.GetScalarEvolution()->CreateConstant(1)),
761 analysis.GetScalarEvolution()->CreateConstant(-1));
762 }
763 {
764 // Function b
765 const Function* f = spvtest::GetFunction(module, 8);
766 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
767 Loop* loop = &ld.GetLoopByIndex(0);
768 std::vector<const Loop*> loops{loop};
769 LoopDependenceAnalysis analysis{context.get(), loops};
770
771 EXPECT_EQ(
772 analysis.GetLowerBound(loop)->AsSEConstantNode()->FoldToSingleValue(),
773 -5);
774 EXPECT_EQ(
775 analysis.GetUpperBound(loop)->AsSEConstantNode()->FoldToSingleValue(),
776 4);
777
778 EXPECT_EQ(
779 analysis.GetTripCount(loop)->AsSEConstantNode()->FoldToSingleValue(),
780 10);
781
782 EXPECT_EQ(analysis.GetFirstTripInductionNode(loop),
783 analysis.GetScalarEvolution()->CreateConstant(-5));
784
785 EXPECT_EQ(analysis.GetFinalTripInductionNode(
786 loop, analysis.GetScalarEvolution()->CreateConstant(1)),
787 analysis.GetScalarEvolution()->CreateConstant(4));
788 }
789 {
790 // Function c
791 const Function* f = spvtest::GetFunction(module, 10);
792 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
793 Loop* loop = &ld.GetLoopByIndex(0);
794 std::vector<const Loop*> loops{loop};
795 LoopDependenceAnalysis analysis{context.get(), loops};
796
797 EXPECT_EQ(
798 analysis.GetLowerBound(loop)->AsSEConstantNode()->FoldToSingleValue(),
799 0);
800 EXPECT_EQ(
801 analysis.GetUpperBound(loop)->AsSEConstantNode()->FoldToSingleValue(),
802 9);
803
804 EXPECT_EQ(
805 analysis.GetTripCount(loop)->AsSEConstantNode()->FoldToSingleValue(),
806 10);
807
808 EXPECT_EQ(analysis.GetFirstTripInductionNode(loop),
809 analysis.GetScalarEvolution()->CreateConstant(0));
810
811 EXPECT_EQ(analysis.GetFinalTripInductionNode(
812 loop, analysis.GetScalarEvolution()->CreateConstant(1)),
813 analysis.GetScalarEvolution()->CreateConstant(9));
814 }
815 {
816 // Function d
817 const Function* f = spvtest::GetFunction(module, 12);
818 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
819 Loop* loop = &ld.GetLoopByIndex(0);
820 std::vector<const Loop*> loops{loop};
821 LoopDependenceAnalysis analysis{context.get(), loops};
822
823 EXPECT_EQ(
824 analysis.GetLowerBound(loop)->AsSEConstantNode()->FoldToSingleValue(),
825 5);
826 EXPECT_EQ(
827 analysis.GetUpperBound(loop)->AsSEConstantNode()->FoldToSingleValue(),
828 14);
829
830 EXPECT_EQ(
831 analysis.GetTripCount(loop)->AsSEConstantNode()->FoldToSingleValue(),
832 10);
833
834 EXPECT_EQ(analysis.GetFirstTripInductionNode(loop),
835 analysis.GetScalarEvolution()->CreateConstant(5));
836
837 EXPECT_EQ(analysis.GetFinalTripInductionNode(
838 loop, analysis.GetScalarEvolution()->CreateConstant(1)),
839 analysis.GetScalarEvolution()->CreateConstant(14));
840 }
841 {
842 // Function e
843 const Function* f = spvtest::GetFunction(module, 14);
844 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
845 Loop* loop = &ld.GetLoopByIndex(0);
846 std::vector<const Loop*> loops{loop};
847 LoopDependenceAnalysis analysis{context.get(), loops};
848
849 EXPECT_EQ(
850 analysis.GetLowerBound(loop)->AsSEConstantNode()->FoldToSingleValue(),
851 -10);
852 EXPECT_EQ(
853 analysis.GetUpperBound(loop)->AsSEConstantNode()->FoldToSingleValue(),
854 0);
855
856 EXPECT_EQ(
857 analysis.GetTripCount(loop)->AsSEConstantNode()->FoldToSingleValue(),
858 11);
859
860 EXPECT_EQ(analysis.GetFirstTripInductionNode(loop),
861 analysis.GetScalarEvolution()->CreateConstant(-10));
862
863 EXPECT_EQ(analysis.GetFinalTripInductionNode(
864 loop, analysis.GetScalarEvolution()->CreateConstant(1)),
865 analysis.GetScalarEvolution()->CreateConstant(0));
866 }
867 {
868 // Function f
869 const Function* f = spvtest::GetFunction(module, 16);
870 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
871 Loop* loop = &ld.GetLoopByIndex(0);
872 std::vector<const Loop*> loops{loop};
873 LoopDependenceAnalysis analysis{context.get(), loops};
874
875 EXPECT_EQ(
876 analysis.GetLowerBound(loop)->AsSEConstantNode()->FoldToSingleValue(),
877 -5);
878 EXPECT_EQ(
879 analysis.GetUpperBound(loop)->AsSEConstantNode()->FoldToSingleValue(),
880 5);
881
882 EXPECT_EQ(
883 analysis.GetTripCount(loop)->AsSEConstantNode()->FoldToSingleValue(),
884 11);
885
886 EXPECT_EQ(analysis.GetFirstTripInductionNode(loop),
887 analysis.GetScalarEvolution()->CreateConstant(-5));
888
889 EXPECT_EQ(analysis.GetFinalTripInductionNode(
890 loop, analysis.GetScalarEvolution()->CreateConstant(1)),
891 analysis.GetScalarEvolution()->CreateConstant(5));
892 }
893 {
894 // Function g
895 const Function* f = spvtest::GetFunction(module, 18);
896 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
897 Loop* loop = &ld.GetLoopByIndex(0);
898 std::vector<const Loop*> loops{loop};
899 LoopDependenceAnalysis analysis{context.get(), loops};
900
901 EXPECT_EQ(
902 analysis.GetLowerBound(loop)->AsSEConstantNode()->FoldToSingleValue(),
903 0);
904 EXPECT_EQ(
905 analysis.GetUpperBound(loop)->AsSEConstantNode()->FoldToSingleValue(),
906 10);
907
908 EXPECT_EQ(
909 analysis.GetTripCount(loop)->AsSEConstantNode()->FoldToSingleValue(),
910 11);
911
912 EXPECT_EQ(analysis.GetFirstTripInductionNode(loop),
913 analysis.GetScalarEvolution()->CreateConstant(0));
914
915 EXPECT_EQ(analysis.GetFinalTripInductionNode(
916 loop, analysis.GetScalarEvolution()->CreateConstant(1)),
917 analysis.GetScalarEvolution()->CreateConstant(10));
918 }
919 {
920 // Function h
921 const Function* f = spvtest::GetFunction(module, 20);
922 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
923 Loop* loop = &ld.GetLoopByIndex(0);
924 std::vector<const Loop*> loops{loop};
925 LoopDependenceAnalysis analysis{context.get(), loops};
926
927 EXPECT_EQ(
928 analysis.GetLowerBound(loop)->AsSEConstantNode()->FoldToSingleValue(),
929 5);
930 EXPECT_EQ(
931 analysis.GetUpperBound(loop)->AsSEConstantNode()->FoldToSingleValue(),
932 15);
933
934 EXPECT_EQ(
935 analysis.GetTripCount(loop)->AsSEConstantNode()->FoldToSingleValue(),
936 11);
937
938 EXPECT_EQ(analysis.GetFirstTripInductionNode(loop),
939 analysis.GetScalarEvolution()->CreateConstant(5));
940
941 EXPECT_EQ(analysis.GetFinalTripInductionNode(
942 loop, analysis.GetScalarEvolution()->CreateConstant(1)),
943 analysis.GetScalarEvolution()->CreateConstant(15));
944 }
945 {
946 // Function i
947 const Function* f = spvtest::GetFunction(module, 22);
948 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
949 Loop* loop = &ld.GetLoopByIndex(0);
950 std::vector<const Loop*> loops{loop};
951 LoopDependenceAnalysis analysis{context.get(), loops};
952
953 EXPECT_EQ(
954 analysis.GetLowerBound(loop)->AsSEConstantNode()->FoldToSingleValue(),
955 0);
956 EXPECT_EQ(
957 analysis.GetUpperBound(loop)->AsSEConstantNode()->FoldToSingleValue(),
958 -9);
959
960 EXPECT_EQ(
961 analysis.GetTripCount(loop)->AsSEConstantNode()->FoldToSingleValue(),
962 10);
963
964 EXPECT_EQ(analysis.GetFirstTripInductionNode(loop),
965 analysis.GetScalarEvolution()->CreateConstant(0));
966
967 EXPECT_EQ(analysis.GetFinalTripInductionNode(
968 loop, analysis.GetScalarEvolution()->CreateConstant(-1)),
969 analysis.GetScalarEvolution()->CreateConstant(-9));
970 }
971 {
972 // Function j
973 const Function* f = spvtest::GetFunction(module, 24);
974 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
975 Loop* loop = &ld.GetLoopByIndex(0);
976 std::vector<const Loop*> loops{loop};
977 LoopDependenceAnalysis analysis{context.get(), loops};
978
979 EXPECT_EQ(
980 analysis.GetLowerBound(loop)->AsSEConstantNode()->FoldToSingleValue(),
981 5);
982 EXPECT_EQ(
983 analysis.GetUpperBound(loop)->AsSEConstantNode()->FoldToSingleValue(),
984 -4);
985
986 EXPECT_EQ(
987 analysis.GetTripCount(loop)->AsSEConstantNode()->FoldToSingleValue(),
988 10);
989
990 EXPECT_EQ(analysis.GetFirstTripInductionNode(loop),
991 analysis.GetScalarEvolution()->CreateConstant(5));
992
993 EXPECT_EQ(analysis.GetFinalTripInductionNode(
994 loop, analysis.GetScalarEvolution()->CreateConstant(-1)),
995 analysis.GetScalarEvolution()->CreateConstant(-4));
996 }
997 {
998 // Function k
999 const Function* f = spvtest::GetFunction(module, 26);
1000 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
1001 Loop* loop = &ld.GetLoopByIndex(0);
1002 std::vector<const Loop*> loops{loop};
1003 LoopDependenceAnalysis analysis{context.get(), loops};
1004
1005 EXPECT_EQ(
1006 analysis.GetLowerBound(loop)->AsSEConstantNode()->FoldToSingleValue(),
1007 10);
1008 EXPECT_EQ(
1009 analysis.GetUpperBound(loop)->AsSEConstantNode()->FoldToSingleValue(),
1010 1);
1011
1012 EXPECT_EQ(
1013 analysis.GetTripCount(loop)->AsSEConstantNode()->FoldToSingleValue(),
1014 10);
1015
1016 EXPECT_EQ(analysis.GetFirstTripInductionNode(loop),
1017 analysis.GetScalarEvolution()->CreateConstant(10));
1018
1019 EXPECT_EQ(analysis.GetFinalTripInductionNode(
1020 loop, analysis.GetScalarEvolution()->CreateConstant(-1)),
1021 analysis.GetScalarEvolution()->CreateConstant(1));
1022 }
1023 {
1024 // Function l
1025 const Function* f = spvtest::GetFunction(module, 28);
1026 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
1027 Loop* loop = &ld.GetLoopByIndex(0);
1028 std::vector<const Loop*> loops{loop};
1029 LoopDependenceAnalysis analysis{context.get(), loops};
1030
1031 EXPECT_EQ(
1032 analysis.GetLowerBound(loop)->AsSEConstantNode()->FoldToSingleValue(),
1033 15);
1034 EXPECT_EQ(
1035 analysis.GetUpperBound(loop)->AsSEConstantNode()->FoldToSingleValue(),
1036 6);
1037
1038 EXPECT_EQ(
1039 analysis.GetTripCount(loop)->AsSEConstantNode()->FoldToSingleValue(),
1040 10);
1041
1042 EXPECT_EQ(analysis.GetFirstTripInductionNode(loop),
1043 analysis.GetScalarEvolution()->CreateConstant(15));
1044
1045 EXPECT_EQ(analysis.GetFinalTripInductionNode(
1046 loop, analysis.GetScalarEvolution()->CreateConstant(-1)),
1047 analysis.GetScalarEvolution()->CreateConstant(6));
1048 }
1049 {
1050 // Function m
1051 const Function* f = spvtest::GetFunction(module, 30);
1052 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
1053 Loop* loop = &ld.GetLoopByIndex(0);
1054 std::vector<const Loop*> loops{loop};
1055 LoopDependenceAnalysis analysis{context.get(), loops};
1056
1057 EXPECT_EQ(
1058 analysis.GetLowerBound(loop)->AsSEConstantNode()->FoldToSingleValue(),
1059 0);
1060 EXPECT_EQ(
1061 analysis.GetUpperBound(loop)->AsSEConstantNode()->FoldToSingleValue(),
1062 -10);
1063
1064 EXPECT_EQ(
1065 analysis.GetTripCount(loop)->AsSEConstantNode()->FoldToSingleValue(),
1066 11);
1067
1068 EXPECT_EQ(analysis.GetFirstTripInductionNode(loop),
1069 analysis.GetScalarEvolution()->CreateConstant(0));
1070
1071 EXPECT_EQ(analysis.GetFinalTripInductionNode(
1072 loop, analysis.GetScalarEvolution()->CreateConstant(-1)),
1073 analysis.GetScalarEvolution()->CreateConstant(-10));
1074 }
1075 {
1076 // Function n
1077 const Function* f = spvtest::GetFunction(module, 32);
1078 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
1079 Loop* loop = &ld.GetLoopByIndex(0);
1080 std::vector<const Loop*> loops{loop};
1081 LoopDependenceAnalysis analysis{context.get(), loops};
1082
1083 EXPECT_EQ(
1084 analysis.GetLowerBound(loop)->AsSEConstantNode()->FoldToSingleValue(),
1085 5);
1086 EXPECT_EQ(
1087 analysis.GetUpperBound(loop)->AsSEConstantNode()->FoldToSingleValue(),
1088 -5);
1089
1090 EXPECT_EQ(
1091 analysis.GetTripCount(loop)->AsSEConstantNode()->FoldToSingleValue(),
1092 11);
1093
1094 EXPECT_EQ(analysis.GetFirstTripInductionNode(loop),
1095 analysis.GetScalarEvolution()->CreateConstant(5));
1096
1097 EXPECT_EQ(analysis.GetFinalTripInductionNode(
1098 loop, analysis.GetScalarEvolution()->CreateConstant(-1)),
1099 analysis.GetScalarEvolution()->CreateConstant(-5));
1100 }
1101 {
1102 // Function o
1103 const Function* f = spvtest::GetFunction(module, 34);
1104 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
1105 Loop* loop = &ld.GetLoopByIndex(0);
1106 std::vector<const Loop*> loops{loop};
1107 LoopDependenceAnalysis analysis{context.get(), loops};
1108
1109 EXPECT_EQ(
1110 analysis.GetLowerBound(loop)->AsSEConstantNode()->FoldToSingleValue(),
1111 10);
1112 EXPECT_EQ(
1113 analysis.GetUpperBound(loop)->AsSEConstantNode()->FoldToSingleValue(),
1114 0);
1115
1116 EXPECT_EQ(
1117 analysis.GetTripCount(loop)->AsSEConstantNode()->FoldToSingleValue(),
1118 11);
1119
1120 EXPECT_EQ(analysis.GetFirstTripInductionNode(loop),
1121 analysis.GetScalarEvolution()->CreateConstant(10));
1122
1123 EXPECT_EQ(analysis.GetFinalTripInductionNode(
1124 loop, analysis.GetScalarEvolution()->CreateConstant(-1)),
1125 analysis.GetScalarEvolution()->CreateConstant(0));
1126 }
1127 {
1128 // Function p
1129 const Function* f = spvtest::GetFunction(module, 36);
1130 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
1131 Loop* loop = &ld.GetLoopByIndex(0);
1132 std::vector<const Loop*> loops{loop};
1133 LoopDependenceAnalysis analysis{context.get(), loops};
1134
1135 EXPECT_EQ(
1136 analysis.GetLowerBound(loop)->AsSEConstantNode()->FoldToSingleValue(),
1137 15);
1138 EXPECT_EQ(
1139 analysis.GetUpperBound(loop)->AsSEConstantNode()->FoldToSingleValue(),
1140 5);
1141
1142 EXPECT_EQ(
1143 analysis.GetTripCount(loop)->AsSEConstantNode()->FoldToSingleValue(),
1144 11);
1145
1146 EXPECT_EQ(analysis.GetFirstTripInductionNode(loop),
1147 analysis.GetScalarEvolution()->CreateConstant(15));
1148
1149 EXPECT_EQ(analysis.GetFinalTripInductionNode(
1150 loop, analysis.GetScalarEvolution()->CreateConstant(-1)),
1151 analysis.GetScalarEvolution()->CreateConstant(5));
1152 }
1153 }
1154
1155 /*
1156 Generated from the following GLSL fragment shader
1157 with --eliminate-local-multi-store
1158 #version 440 core
1159 void main(){
1160 for (int i = 0; i < 10; i++) {
1161
1162 }
1163 }
1164 */
TEST(DependencyAnalysisHelpers,bounds_checks)1165 TEST(DependencyAnalysisHelpers, bounds_checks) {
1166 const std::string text = R"( OpCapability Shader
1167 %1 = OpExtInstImport "GLSL.std.450"
1168 OpMemoryModel Logical GLSL450
1169 OpEntryPoint Fragment %4 "main"
1170 OpExecutionMode %4 OriginUpperLeft
1171 OpSource GLSL 440
1172 OpName %4 "main"
1173 OpName %8 "i"
1174 %2 = OpTypeVoid
1175 %3 = OpTypeFunction %2
1176 %6 = OpTypeInt 32 1
1177 %7 = OpTypePointer Function %6
1178 %9 = OpConstant %6 0
1179 %16 = OpConstant %6 10
1180 %17 = OpTypeBool
1181 %20 = OpConstant %6 1
1182 %4 = OpFunction %2 None %3
1183 %5 = OpLabel
1184 %8 = OpVariable %7 Function
1185 OpStore %8 %9
1186 OpBranch %10
1187 %10 = OpLabel
1188 %22 = OpPhi %6 %9 %5 %21 %13
1189 OpLoopMerge %12 %13 None
1190 OpBranch %14
1191 %14 = OpLabel
1192 %18 = OpSLessThan %17 %22 %16
1193 OpBranchConditional %18 %11 %12
1194 %11 = OpLabel
1195 OpBranch %13
1196 %13 = OpLabel
1197 %21 = OpIAdd %6 %22 %20
1198 OpStore %8 %21
1199 OpBranch %10
1200 %12 = OpLabel
1201 OpReturn
1202 OpFunctionEnd
1203 )";
1204 std::unique_ptr<IRContext> context =
1205 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
1206 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
1207 Module* module = context->module();
1208 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
1209 << text << std::endl;
1210 // We need a shader that includes a loop for this test so we can build a
1211 // LoopDependenceAnalaysis
1212 const Function* f = spvtest::GetFunction(module, 4);
1213 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
1214 Loop* loop = &ld.GetLoopByIndex(0);
1215 std::vector<const Loop*> loops{loop};
1216 LoopDependenceAnalysis analysis{context.get(), loops};
1217
1218 EXPECT_TRUE(analysis.IsWithinBounds(0, 0, 0));
1219 EXPECT_TRUE(analysis.IsWithinBounds(0, -1, 0));
1220 EXPECT_TRUE(analysis.IsWithinBounds(0, 0, 1));
1221 EXPECT_TRUE(analysis.IsWithinBounds(0, -1, 1));
1222 EXPECT_TRUE(analysis.IsWithinBounds(-2, -2, -2));
1223 EXPECT_TRUE(analysis.IsWithinBounds(-2, -3, 0));
1224 EXPECT_TRUE(analysis.IsWithinBounds(-2, 0, -3));
1225 EXPECT_TRUE(analysis.IsWithinBounds(2, 2, 2));
1226 EXPECT_TRUE(analysis.IsWithinBounds(2, 3, 0));
1227
1228 EXPECT_FALSE(analysis.IsWithinBounds(2, 3, 3));
1229 EXPECT_FALSE(analysis.IsWithinBounds(0, 1, 5));
1230 EXPECT_FALSE(analysis.IsWithinBounds(0, -1, -4));
1231 EXPECT_FALSE(analysis.IsWithinBounds(-2, -4, -3));
1232 }
1233
1234 /*
1235 Generated from the following GLSL fragment shader
1236 with --eliminate-local-multi-store
1237 #version 440 core
1238 layout(location = 0) in vec4 in_vec;
1239 // Loop iterates from constant to symbolic
1240 void a() {
1241 int N = int(in_vec.x);
1242 int arr[10];
1243 for (int i = 0; i < N; i++) { // Bounds are N - 0 - 1
1244 arr[i] = arr[i+N]; // |distance| = N
1245 arr[i+N] = arr[i]; // |distance| = N
1246 }
1247 }
1248 void b() {
1249 int N = int(in_vec.x);
1250 int arr[10];
1251 for (int i = 0; i <= N; i++) { // Bounds are N - 0
1252 arr[i] = arr[i+N]; // |distance| = N
1253 arr[i+N] = arr[i]; // |distance| = N
1254 }
1255 }
1256 void c() {
1257 int N = int(in_vec.x);
1258 int arr[10];
1259 for (int i = 9; i > N; i--) { // Bounds are 9 - N - 1
1260 arr[i] = arr[i+N]; // |distance| = N
1261 arr[i+N] = arr[i]; // |distance| = N
1262 }
1263 }
1264 void d() {
1265 int N = int(in_vec.x);
1266 int arr[10];
1267 for (int i = 9; i >= N; i--) { // Bounds are 9 - N
1268 arr[i] = arr[i+N]; // |distance| = N
1269 arr[i+N] = arr[i]; // |distance| = N
1270 }
1271 }
1272 void main(){
1273 a();
1274 b();
1275 c();
1276 d();
1277 }
1278 */
TEST(DependencyAnalysisHelpers,const_to_symbolic)1279 TEST(DependencyAnalysisHelpers, const_to_symbolic) {
1280 const std::string text = R"( OpCapability Shader
1281 %1 = OpExtInstImport "GLSL.std.450"
1282 OpMemoryModel Logical GLSL450
1283 OpEntryPoint Fragment %4 "main" %20
1284 OpExecutionMode %4 OriginUpperLeft
1285 OpSource GLSL 440
1286 OpName %4 "main"
1287 OpName %6 "a("
1288 OpName %8 "b("
1289 OpName %10 "c("
1290 OpName %12 "d("
1291 OpName %16 "N"
1292 OpName %20 "in_vec"
1293 OpName %27 "i"
1294 OpName %41 "arr"
1295 OpName %59 "N"
1296 OpName %63 "i"
1297 OpName %72 "arr"
1298 OpName %89 "N"
1299 OpName %93 "i"
1300 OpName %103 "arr"
1301 OpName %120 "N"
1302 OpName %124 "i"
1303 OpName %133 "arr"
1304 OpDecorate %20 Location 0
1305 %2 = OpTypeVoid
1306 %3 = OpTypeFunction %2
1307 %14 = OpTypeInt 32 1
1308 %15 = OpTypePointer Function %14
1309 %17 = OpTypeFloat 32
1310 %18 = OpTypeVector %17 4
1311 %19 = OpTypePointer Input %18
1312 %20 = OpVariable %19 Input
1313 %21 = OpTypeInt 32 0
1314 %22 = OpConstant %21 0
1315 %23 = OpTypePointer Input %17
1316 %28 = OpConstant %14 0
1317 %36 = OpTypeBool
1318 %38 = OpConstant %21 10
1319 %39 = OpTypeArray %14 %38
1320 %40 = OpTypePointer Function %39
1321 %57 = OpConstant %14 1
1322 %94 = OpConstant %14 9
1323 %4 = OpFunction %2 None %3
1324 %5 = OpLabel
1325 %150 = OpFunctionCall %2 %6
1326 %151 = OpFunctionCall %2 %8
1327 %152 = OpFunctionCall %2 %10
1328 %153 = OpFunctionCall %2 %12
1329 OpReturn
1330 OpFunctionEnd
1331 %6 = OpFunction %2 None %3
1332 %7 = OpLabel
1333 %16 = OpVariable %15 Function
1334 %27 = OpVariable %15 Function
1335 %41 = OpVariable %40 Function
1336 %24 = OpAccessChain %23 %20 %22
1337 %25 = OpLoad %17 %24
1338 %26 = OpConvertFToS %14 %25
1339 OpStore %16 %26
1340 OpStore %27 %28
1341 OpBranch %29
1342 %29 = OpLabel
1343 %154 = OpPhi %14 %28 %7 %58 %32
1344 OpLoopMerge %31 %32 None
1345 OpBranch %33
1346 %33 = OpLabel
1347 %37 = OpSLessThan %36 %154 %26
1348 OpBranchConditional %37 %30 %31
1349 %30 = OpLabel
1350 %45 = OpIAdd %14 %154 %26
1351 %46 = OpAccessChain %15 %41 %45
1352 %47 = OpLoad %14 %46
1353 %48 = OpAccessChain %15 %41 %154
1354 OpStore %48 %47
1355 %51 = OpIAdd %14 %154 %26
1356 %53 = OpAccessChain %15 %41 %154
1357 %54 = OpLoad %14 %53
1358 %55 = OpAccessChain %15 %41 %51
1359 OpStore %55 %54
1360 OpBranch %32
1361 %32 = OpLabel
1362 %58 = OpIAdd %14 %154 %57
1363 OpStore %27 %58
1364 OpBranch %29
1365 %31 = OpLabel
1366 OpReturn
1367 OpFunctionEnd
1368 %8 = OpFunction %2 None %3
1369 %9 = OpLabel
1370 %59 = OpVariable %15 Function
1371 %63 = OpVariable %15 Function
1372 %72 = OpVariable %40 Function
1373 %60 = OpAccessChain %23 %20 %22
1374 %61 = OpLoad %17 %60
1375 %62 = OpConvertFToS %14 %61
1376 OpStore %59 %62
1377 OpStore %63 %28
1378 OpBranch %64
1379 %64 = OpLabel
1380 %155 = OpPhi %14 %28 %9 %88 %67
1381 OpLoopMerge %66 %67 None
1382 OpBranch %68
1383 %68 = OpLabel
1384 %71 = OpSLessThanEqual %36 %155 %62
1385 OpBranchConditional %71 %65 %66
1386 %65 = OpLabel
1387 %76 = OpIAdd %14 %155 %62
1388 %77 = OpAccessChain %15 %72 %76
1389 %78 = OpLoad %14 %77
1390 %79 = OpAccessChain %15 %72 %155
1391 OpStore %79 %78
1392 %82 = OpIAdd %14 %155 %62
1393 %84 = OpAccessChain %15 %72 %155
1394 %85 = OpLoad %14 %84
1395 %86 = OpAccessChain %15 %72 %82
1396 OpStore %86 %85
1397 OpBranch %67
1398 %67 = OpLabel
1399 %88 = OpIAdd %14 %155 %57
1400 OpStore %63 %88
1401 OpBranch %64
1402 %66 = OpLabel
1403 OpReturn
1404 OpFunctionEnd
1405 %10 = OpFunction %2 None %3
1406 %11 = OpLabel
1407 %89 = OpVariable %15 Function
1408 %93 = OpVariable %15 Function
1409 %103 = OpVariable %40 Function
1410 %90 = OpAccessChain %23 %20 %22
1411 %91 = OpLoad %17 %90
1412 %92 = OpConvertFToS %14 %91
1413 OpStore %89 %92
1414 OpStore %93 %94
1415 OpBranch %95
1416 %95 = OpLabel
1417 %156 = OpPhi %14 %94 %11 %119 %98
1418 OpLoopMerge %97 %98 None
1419 OpBranch %99
1420 %99 = OpLabel
1421 %102 = OpSGreaterThan %36 %156 %92
1422 OpBranchConditional %102 %96 %97
1423 %96 = OpLabel
1424 %107 = OpIAdd %14 %156 %92
1425 %108 = OpAccessChain %15 %103 %107
1426 %109 = OpLoad %14 %108
1427 %110 = OpAccessChain %15 %103 %156
1428 OpStore %110 %109
1429 %113 = OpIAdd %14 %156 %92
1430 %115 = OpAccessChain %15 %103 %156
1431 %116 = OpLoad %14 %115
1432 %117 = OpAccessChain %15 %103 %113
1433 OpStore %117 %116
1434 OpBranch %98
1435 %98 = OpLabel
1436 %119 = OpISub %14 %156 %57
1437 OpStore %93 %119
1438 OpBranch %95
1439 %97 = OpLabel
1440 OpReturn
1441 OpFunctionEnd
1442 %12 = OpFunction %2 None %3
1443 %13 = OpLabel
1444 %120 = OpVariable %15 Function
1445 %124 = OpVariable %15 Function
1446 %133 = OpVariable %40 Function
1447 %121 = OpAccessChain %23 %20 %22
1448 %122 = OpLoad %17 %121
1449 %123 = OpConvertFToS %14 %122
1450 OpStore %120 %123
1451 OpStore %124 %94
1452 OpBranch %125
1453 %125 = OpLabel
1454 %157 = OpPhi %14 %94 %13 %149 %128
1455 OpLoopMerge %127 %128 None
1456 OpBranch %129
1457 %129 = OpLabel
1458 %132 = OpSGreaterThanEqual %36 %157 %123
1459 OpBranchConditional %132 %126 %127
1460 %126 = OpLabel
1461 %137 = OpIAdd %14 %157 %123
1462 %138 = OpAccessChain %15 %133 %137
1463 %139 = OpLoad %14 %138
1464 %140 = OpAccessChain %15 %133 %157
1465 OpStore %140 %139
1466 %143 = OpIAdd %14 %157 %123
1467 %145 = OpAccessChain %15 %133 %157
1468 %146 = OpLoad %14 %145
1469 %147 = OpAccessChain %15 %133 %143
1470 OpStore %147 %146
1471 OpBranch %128
1472 %128 = OpLabel
1473 %149 = OpISub %14 %157 %57
1474 OpStore %124 %149
1475 OpBranch %125
1476 %127 = OpLabel
1477 OpReturn
1478 OpFunctionEnd
1479 )";
1480 std::unique_ptr<IRContext> context =
1481 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
1482 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
1483 Module* module = context->module();
1484 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
1485 << text << std::endl;
1486
1487 {
1488 // Function a
1489 const Function* f = spvtest::GetFunction(module, 6);
1490 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
1491 Loop* loop = &ld.GetLoopByIndex(0);
1492 std::vector<const Loop*> loops{loop};
1493 LoopDependenceAnalysis analysis{context.get(), loops};
1494
1495 const Instruction* stores[2];
1496 int stores_found = 0;
1497 for (const Instruction& inst : *spvtest::GetBasicBlock(f, 30)) {
1498 if (inst.opcode() == SpvOp::SpvOpStore) {
1499 stores[stores_found] = &inst;
1500 ++stores_found;
1501 }
1502 }
1503
1504 for (int i = 0; i < 2; ++i) {
1505 EXPECT_TRUE(stores[i]);
1506 }
1507
1508 // 47 -> 48
1509 {
1510 // Analyse and simplify the instruction behind the access chain of this
1511 // load.
1512 Instruction* load_var = context->get_def_use_mgr()->GetDef(
1513 context->get_def_use_mgr()
1514 ->GetDef(context->get_def_use_mgr()
1515 ->GetDef(47)
1516 ->GetSingleWordInOperand(0))
1517 ->GetSingleWordInOperand(1));
1518 SENode* load = analysis.GetScalarEvolution()->SimplifyExpression(
1519 analysis.GetScalarEvolution()->AnalyzeInstruction(load_var));
1520
1521 // Analyse and simplify the instruction behind the access chain of this
1522 // store.
1523 Instruction* store_var = context->get_def_use_mgr()->GetDef(
1524 context->get_def_use_mgr()
1525 ->GetDef(stores[0]->GetSingleWordInOperand(0))
1526 ->GetSingleWordInOperand(1));
1527 SENode* store = analysis.GetScalarEvolution()->SimplifyExpression(
1528 analysis.GetScalarEvolution()->AnalyzeInstruction(store_var));
1529
1530 SENode* delta = analysis.GetScalarEvolution()->SimplifyExpression(
1531 analysis.GetScalarEvolution()->CreateSubtraction(load, store));
1532
1533 // Independent and supported.
1534 EXPECT_TRUE(analysis.IsProvablyOutsideOfLoopBounds(
1535 loop, delta, store->AsSERecurrentNode()->GetCoefficient()));
1536 }
1537
1538 // 54 -> 55
1539 {
1540 // Analyse and simplify the instruction behind the access chain of this
1541 // load.
1542 Instruction* load_var = context->get_def_use_mgr()->GetDef(
1543 context->get_def_use_mgr()
1544 ->GetDef(context->get_def_use_mgr()
1545 ->GetDef(54)
1546 ->GetSingleWordInOperand(0))
1547 ->GetSingleWordInOperand(1));
1548 SENode* load = analysis.GetScalarEvolution()->SimplifyExpression(
1549 analysis.GetScalarEvolution()->AnalyzeInstruction(load_var));
1550
1551 // Analyse and simplify the instruction behind the access chain of this
1552 // store.
1553 Instruction* store_var = context->get_def_use_mgr()->GetDef(
1554 context->get_def_use_mgr()
1555 ->GetDef(stores[1]->GetSingleWordInOperand(0))
1556 ->GetSingleWordInOperand(1));
1557 SENode* store = analysis.GetScalarEvolution()->SimplifyExpression(
1558 analysis.GetScalarEvolution()->AnalyzeInstruction(store_var));
1559
1560 SENode* delta = analysis.GetScalarEvolution()->SimplifyExpression(
1561 analysis.GetScalarEvolution()->CreateSubtraction(load, store));
1562
1563 // Independent but not supported.
1564 EXPECT_FALSE(analysis.IsProvablyOutsideOfLoopBounds(
1565 loop, delta, store->AsSERecurrentNode()->GetCoefficient()));
1566 }
1567 }
1568 {
1569 // Function b
1570 const Function* f = spvtest::GetFunction(module, 8);
1571 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
1572 Loop* loop = &ld.GetLoopByIndex(0);
1573 std::vector<const Loop*> loops{loop};
1574 LoopDependenceAnalysis analysis{context.get(), loops};
1575
1576 const Instruction* stores[2];
1577 int stores_found = 0;
1578 for (const Instruction& inst : *spvtest::GetBasicBlock(f, 65)) {
1579 if (inst.opcode() == SpvOp::SpvOpStore) {
1580 stores[stores_found] = &inst;
1581 ++stores_found;
1582 }
1583 }
1584
1585 for (int i = 0; i < 2; ++i) {
1586 EXPECT_TRUE(stores[i]);
1587 }
1588
1589 // 78 -> 79
1590 {
1591 // Analyse and simplify the instruction behind the access chain of this
1592 // load.
1593 Instruction* load_var = context->get_def_use_mgr()->GetDef(
1594 context->get_def_use_mgr()
1595 ->GetDef(context->get_def_use_mgr()
1596 ->GetDef(78)
1597 ->GetSingleWordInOperand(0))
1598 ->GetSingleWordInOperand(1));
1599 SENode* load = analysis.GetScalarEvolution()->SimplifyExpression(
1600 analysis.GetScalarEvolution()->AnalyzeInstruction(load_var));
1601 // Analyse and simplify the instruction behind the access chain of this
1602 // store.
1603 Instruction* store_var = context->get_def_use_mgr()->GetDef(
1604 context->get_def_use_mgr()
1605 ->GetDef(stores[0]->GetSingleWordInOperand(0))
1606 ->GetSingleWordInOperand(1));
1607 SENode* store = analysis.GetScalarEvolution()->SimplifyExpression(
1608 analysis.GetScalarEvolution()->AnalyzeInstruction(store_var));
1609
1610 SENode* delta = analysis.GetScalarEvolution()->SimplifyExpression(
1611 analysis.GetScalarEvolution()->CreateSubtraction(load, store));
1612
1613 // Dependent.
1614 EXPECT_FALSE(analysis.IsProvablyOutsideOfLoopBounds(
1615 loop, delta, store->AsSERecurrentNode()->GetCoefficient()));
1616 }
1617
1618 // 85 -> 86
1619 {
1620 // Analyse and simplify the instruction behind the access chain of this
1621 // load.
1622 Instruction* load_var = context->get_def_use_mgr()->GetDef(
1623 context->get_def_use_mgr()
1624 ->GetDef(context->get_def_use_mgr()
1625 ->GetDef(85)
1626 ->GetSingleWordInOperand(0))
1627 ->GetSingleWordInOperand(1));
1628 SENode* load = analysis.GetScalarEvolution()->SimplifyExpression(
1629 analysis.GetScalarEvolution()->AnalyzeInstruction(load_var));
1630 // Analyse and simplify the instruction behind the access chain of this
1631 // store.
1632 Instruction* store_var = context->get_def_use_mgr()->GetDef(
1633 context->get_def_use_mgr()
1634 ->GetDef(stores[1]->GetSingleWordInOperand(0))
1635 ->GetSingleWordInOperand(1));
1636 SENode* store = analysis.GetScalarEvolution()->SimplifyExpression(
1637 analysis.GetScalarEvolution()->AnalyzeInstruction(store_var));
1638
1639 SENode* delta = analysis.GetScalarEvolution()->SimplifyExpression(
1640 analysis.GetScalarEvolution()->CreateSubtraction(load, store));
1641
1642 // Dependent.
1643 EXPECT_FALSE(analysis.IsProvablyOutsideOfLoopBounds(
1644 loop, delta, store->AsSERecurrentNode()->GetCoefficient()));
1645 }
1646 }
1647 {
1648 // Function c
1649 const Function* f = spvtest::GetFunction(module, 10);
1650 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
1651 Loop* loop = &ld.GetLoopByIndex(0);
1652 std::vector<const Loop*> loops{loop};
1653 LoopDependenceAnalysis analysis{context.get(), loops};
1654
1655 const Instruction* stores[2];
1656 int stores_found = 0;
1657 for (const Instruction& inst : *spvtest::GetBasicBlock(f, 96)) {
1658 if (inst.opcode() == SpvOp::SpvOpStore) {
1659 stores[stores_found] = &inst;
1660 ++stores_found;
1661 }
1662 }
1663
1664 for (int i = 0; i < 2; ++i) {
1665 EXPECT_TRUE(stores[i]);
1666 }
1667
1668 // 109 -> 110
1669 {
1670 // Analyse and simplify the instruction behind the access chain of this
1671 // load.
1672 Instruction* load_var = context->get_def_use_mgr()->GetDef(
1673 context->get_def_use_mgr()
1674 ->GetDef(context->get_def_use_mgr()
1675 ->GetDef(109)
1676 ->GetSingleWordInOperand(0))
1677 ->GetSingleWordInOperand(1));
1678 SENode* load = analysis.GetScalarEvolution()->SimplifyExpression(
1679 analysis.GetScalarEvolution()->AnalyzeInstruction(load_var));
1680 // Analyse and simplify the instruction behind the access chain of this
1681 // store.
1682 Instruction* store_var = context->get_def_use_mgr()->GetDef(
1683 context->get_def_use_mgr()
1684 ->GetDef(stores[0]->GetSingleWordInOperand(0))
1685 ->GetSingleWordInOperand(1));
1686 SENode* store = analysis.GetScalarEvolution()->SimplifyExpression(
1687 analysis.GetScalarEvolution()->AnalyzeInstruction(store_var));
1688
1689 SENode* delta = analysis.GetScalarEvolution()->SimplifyExpression(
1690 analysis.GetScalarEvolution()->CreateSubtraction(load, store));
1691
1692 // Independent but not supported.
1693 EXPECT_FALSE(analysis.IsProvablyOutsideOfLoopBounds(
1694 loop, delta, store->AsSERecurrentNode()->GetCoefficient()));
1695 }
1696
1697 // 116 -> 117
1698 {
1699 // Analyse and simplify the instruction behind the access chain of this
1700 // load.
1701 Instruction* load_var = context->get_def_use_mgr()->GetDef(
1702 context->get_def_use_mgr()
1703 ->GetDef(context->get_def_use_mgr()
1704 ->GetDef(116)
1705 ->GetSingleWordInOperand(0))
1706 ->GetSingleWordInOperand(1));
1707 SENode* load = analysis.GetScalarEvolution()->SimplifyExpression(
1708 analysis.GetScalarEvolution()->AnalyzeInstruction(load_var));
1709 // Analyse and simplify the instruction behind the access chain of this
1710 // store.
1711 Instruction* store_var = context->get_def_use_mgr()->GetDef(
1712 context->get_def_use_mgr()
1713 ->GetDef(stores[1]->GetSingleWordInOperand(0))
1714 ->GetSingleWordInOperand(1));
1715 SENode* store = analysis.GetScalarEvolution()->SimplifyExpression(
1716 analysis.GetScalarEvolution()->AnalyzeInstruction(store_var));
1717
1718 SENode* delta = analysis.GetScalarEvolution()->SimplifyExpression(
1719 analysis.GetScalarEvolution()->CreateSubtraction(load, store));
1720
1721 // Independent but not supported.
1722 EXPECT_FALSE(analysis.IsProvablyOutsideOfLoopBounds(
1723 loop, delta, store->AsSERecurrentNode()->GetCoefficient()));
1724 }
1725 }
1726 {
1727 // Function d
1728 const Function* f = spvtest::GetFunction(module, 12);
1729 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
1730 Loop* loop = &ld.GetLoopByIndex(0);
1731 std::vector<const Loop*> loops{loop};
1732 LoopDependenceAnalysis analysis{context.get(), loops};
1733
1734 const Instruction* stores[2];
1735 int stores_found = 0;
1736 for (const Instruction& inst : *spvtest::GetBasicBlock(f, 126)) {
1737 if (inst.opcode() == SpvOp::SpvOpStore) {
1738 stores[stores_found] = &inst;
1739 ++stores_found;
1740 }
1741 }
1742
1743 for (int i = 0; i < 2; ++i) {
1744 EXPECT_TRUE(stores[i]);
1745 }
1746
1747 // 139 -> 140
1748 {
1749 // Analyse and simplify the instruction behind the access chain of this
1750 // load.
1751 Instruction* load_var = context->get_def_use_mgr()->GetDef(
1752 context->get_def_use_mgr()
1753 ->GetDef(context->get_def_use_mgr()
1754 ->GetDef(139)
1755 ->GetSingleWordInOperand(0))
1756 ->GetSingleWordInOperand(1));
1757 SENode* load = analysis.GetScalarEvolution()->SimplifyExpression(
1758 analysis.GetScalarEvolution()->AnalyzeInstruction(load_var));
1759 // Analyse and simplify the instruction behind the access chain of this
1760 // store.
1761 Instruction* store_var = context->get_def_use_mgr()->GetDef(
1762 context->get_def_use_mgr()
1763 ->GetDef(stores[0]->GetSingleWordInOperand(0))
1764 ->GetSingleWordInOperand(1));
1765 SENode* store = analysis.GetScalarEvolution()->SimplifyExpression(
1766 analysis.GetScalarEvolution()->AnalyzeInstruction(store_var));
1767
1768 SENode* delta = analysis.GetScalarEvolution()->SimplifyExpression(
1769 analysis.GetScalarEvolution()->CreateSubtraction(load, store));
1770
1771 // Dependent.
1772 EXPECT_FALSE(analysis.IsProvablyOutsideOfLoopBounds(
1773 loop, delta, store->AsSERecurrentNode()->GetCoefficient()));
1774 }
1775
1776 // 146 -> 147
1777 {
1778 // Analyse and simplify the instruction behind the access chain of this
1779 // load.
1780 Instruction* load_var = context->get_def_use_mgr()->GetDef(
1781 context->get_def_use_mgr()
1782 ->GetDef(context->get_def_use_mgr()
1783 ->GetDef(146)
1784 ->GetSingleWordInOperand(0))
1785 ->GetSingleWordInOperand(1));
1786 SENode* load = analysis.GetScalarEvolution()->SimplifyExpression(
1787 analysis.GetScalarEvolution()->AnalyzeInstruction(load_var));
1788 // Analyse and simplify the instruction behind the access chain of this
1789 // store.
1790 Instruction* store_var = context->get_def_use_mgr()->GetDef(
1791 context->get_def_use_mgr()
1792 ->GetDef(stores[1]->GetSingleWordInOperand(0))
1793 ->GetSingleWordInOperand(1));
1794 SENode* store = analysis.GetScalarEvolution()->SimplifyExpression(
1795 analysis.GetScalarEvolution()->AnalyzeInstruction(store_var));
1796
1797 SENode* delta = analysis.GetScalarEvolution()->SimplifyExpression(
1798 analysis.GetScalarEvolution()->CreateSubtraction(load, store));
1799
1800 // Dependent.
1801 EXPECT_FALSE(analysis.IsProvablyOutsideOfLoopBounds(
1802 loop, delta, store->AsSERecurrentNode()->GetCoefficient()));
1803 }
1804 }
1805 }
1806
1807 /*
1808 Generated from the following GLSL fragment shader
1809 with --eliminate-local-multi-store
1810 #version 440 core
1811 layout(location = 0) in vec4 in_vec;
1812 // Loop iterates from symbolic to constant
1813 void a() {
1814 int N = int(in_vec.x);
1815 int arr[10];
1816 for (int i = N; i < 9; i++) { // Bounds are 9 - N - 1
1817 arr[i] = arr[i+N]; // |distance| = N
1818 arr[i+N] = arr[i]; // |distance| = N
1819 }
1820 }
1821 void b() {
1822 int N = int(in_vec.x);
1823 int arr[10];
1824 for (int i = N; i <= 9; i++) { // Bounds are 9 - N
1825 arr[i] = arr[i+N]; // |distance| = N
1826 arr[i+N] = arr[i]; // |distance| = N
1827 }
1828 }
1829 void c() {
1830 int N = int(in_vec.x);
1831 int arr[10];
1832 for (int i = N; i > 0; i--) { // Bounds are N - 0 - 1
1833 arr[i] = arr[i+N]; // |distance| = N
1834 arr[i+N] = arr[i]; // |distance| = N
1835 }
1836 }
1837 void d() {
1838 int N = int(in_vec.x);
1839 int arr[10];
1840 for (int i = N; i >= 0; i--) { // Bounds are N - 0
1841 arr[i] = arr[i+N]; // |distance| = N
1842 arr[i+N] = arr[i]; // |distance| = N
1843 }
1844 }
1845 void main(){
1846 a();
1847 b();
1848 c();
1849 d();
1850 }
1851 */
TEST(DependencyAnalysisHelpers,symbolic_to_const)1852 TEST(DependencyAnalysisHelpers, symbolic_to_const) {
1853 const std::string text = R"( OpCapability Shader
1854 %1 = OpExtInstImport "GLSL.std.450"
1855 OpMemoryModel Logical GLSL450
1856 OpEntryPoint Fragment %4 "main" %20
1857 OpExecutionMode %4 OriginUpperLeft
1858 OpSource GLSL 440
1859 OpName %4 "main"
1860 OpName %6 "a("
1861 OpName %8 "b("
1862 OpName %10 "c("
1863 OpName %12 "d("
1864 OpName %16 "N"
1865 OpName %20 "in_vec"
1866 OpName %27 "i"
1867 OpName %41 "arr"
1868 OpName %59 "N"
1869 OpName %63 "i"
1870 OpName %72 "arr"
1871 OpName %89 "N"
1872 OpName %93 "i"
1873 OpName %103 "arr"
1874 OpName %120 "N"
1875 OpName %124 "i"
1876 OpName %133 "arr"
1877 OpDecorate %20 Location 0
1878 %2 = OpTypeVoid
1879 %3 = OpTypeFunction %2
1880 %14 = OpTypeInt 32 1
1881 %15 = OpTypePointer Function %14
1882 %17 = OpTypeFloat 32
1883 %18 = OpTypeVector %17 4
1884 %19 = OpTypePointer Input %18
1885 %20 = OpVariable %19 Input
1886 %21 = OpTypeInt 32 0
1887 %22 = OpConstant %21 0
1888 %23 = OpTypePointer Input %17
1889 %35 = OpConstant %14 9
1890 %36 = OpTypeBool
1891 %38 = OpConstant %21 10
1892 %39 = OpTypeArray %14 %38
1893 %40 = OpTypePointer Function %39
1894 %57 = OpConstant %14 1
1895 %101 = OpConstant %14 0
1896 %4 = OpFunction %2 None %3
1897 %5 = OpLabel
1898 %150 = OpFunctionCall %2 %6
1899 %151 = OpFunctionCall %2 %8
1900 %152 = OpFunctionCall %2 %10
1901 %153 = OpFunctionCall %2 %12
1902 OpReturn
1903 OpFunctionEnd
1904 %6 = OpFunction %2 None %3
1905 %7 = OpLabel
1906 %16 = OpVariable %15 Function
1907 %27 = OpVariable %15 Function
1908 %41 = OpVariable %40 Function
1909 %24 = OpAccessChain %23 %20 %22
1910 %25 = OpLoad %17 %24
1911 %26 = OpConvertFToS %14 %25
1912 OpStore %16 %26
1913 OpStore %27 %26
1914 OpBranch %29
1915 %29 = OpLabel
1916 %154 = OpPhi %14 %26 %7 %58 %32
1917 OpLoopMerge %31 %32 None
1918 OpBranch %33
1919 %33 = OpLabel
1920 %37 = OpSLessThan %36 %154 %35
1921 OpBranchConditional %37 %30 %31
1922 %30 = OpLabel
1923 %45 = OpIAdd %14 %154 %26
1924 %46 = OpAccessChain %15 %41 %45
1925 %47 = OpLoad %14 %46
1926 %48 = OpAccessChain %15 %41 %154
1927 OpStore %48 %47
1928 %51 = OpIAdd %14 %154 %26
1929 %53 = OpAccessChain %15 %41 %154
1930 %54 = OpLoad %14 %53
1931 %55 = OpAccessChain %15 %41 %51
1932 OpStore %55 %54
1933 OpBranch %32
1934 %32 = OpLabel
1935 %58 = OpIAdd %14 %154 %57
1936 OpStore %27 %58
1937 OpBranch %29
1938 %31 = OpLabel
1939 OpReturn
1940 OpFunctionEnd
1941 %8 = OpFunction %2 None %3
1942 %9 = OpLabel
1943 %59 = OpVariable %15 Function
1944 %63 = OpVariable %15 Function
1945 %72 = OpVariable %40 Function
1946 %60 = OpAccessChain %23 %20 %22
1947 %61 = OpLoad %17 %60
1948 %62 = OpConvertFToS %14 %61
1949 OpStore %59 %62
1950 OpStore %63 %62
1951 OpBranch %65
1952 %65 = OpLabel
1953 %155 = OpPhi %14 %62 %9 %88 %68
1954 OpLoopMerge %67 %68 None
1955 OpBranch %69
1956 %69 = OpLabel
1957 %71 = OpSLessThanEqual %36 %155 %35
1958 OpBranchConditional %71 %66 %67
1959 %66 = OpLabel
1960 %76 = OpIAdd %14 %155 %62
1961 %77 = OpAccessChain %15 %72 %76
1962 %78 = OpLoad %14 %77
1963 %79 = OpAccessChain %15 %72 %155
1964 OpStore %79 %78
1965 %82 = OpIAdd %14 %155 %62
1966 %84 = OpAccessChain %15 %72 %155
1967 %85 = OpLoad %14 %84
1968 %86 = OpAccessChain %15 %72 %82
1969 OpStore %86 %85
1970 OpBranch %68
1971 %68 = OpLabel
1972 %88 = OpIAdd %14 %155 %57
1973 OpStore %63 %88
1974 OpBranch %65
1975 %67 = OpLabel
1976 OpReturn
1977 OpFunctionEnd
1978 %10 = OpFunction %2 None %3
1979 %11 = OpLabel
1980 %89 = OpVariable %15 Function
1981 %93 = OpVariable %15 Function
1982 %103 = OpVariable %40 Function
1983 %90 = OpAccessChain %23 %20 %22
1984 %91 = OpLoad %17 %90
1985 %92 = OpConvertFToS %14 %91
1986 OpStore %89 %92
1987 OpStore %93 %92
1988 OpBranch %95
1989 %95 = OpLabel
1990 %156 = OpPhi %14 %92 %11 %119 %98
1991 OpLoopMerge %97 %98 None
1992 OpBranch %99
1993 %99 = OpLabel
1994 %102 = OpSGreaterThan %36 %156 %101
1995 OpBranchConditional %102 %96 %97
1996 %96 = OpLabel
1997 %107 = OpIAdd %14 %156 %92
1998 %108 = OpAccessChain %15 %103 %107
1999 %109 = OpLoad %14 %108
2000 %110 = OpAccessChain %15 %103 %156
2001 OpStore %110 %109
2002 %113 = OpIAdd %14 %156 %92
2003 %115 = OpAccessChain %15 %103 %156
2004 %116 = OpLoad %14 %115
2005 %117 = OpAccessChain %15 %103 %113
2006 OpStore %117 %116
2007 OpBranch %98
2008 %98 = OpLabel
2009 %119 = OpISub %14 %156 %57
2010 OpStore %93 %119
2011 OpBranch %95
2012 %97 = OpLabel
2013 OpReturn
2014 OpFunctionEnd
2015 %12 = OpFunction %2 None %3
2016 %13 = OpLabel
2017 %120 = OpVariable %15 Function
2018 %124 = OpVariable %15 Function
2019 %133 = OpVariable %40 Function
2020 %121 = OpAccessChain %23 %20 %22
2021 %122 = OpLoad %17 %121
2022 %123 = OpConvertFToS %14 %122
2023 OpStore %120 %123
2024 OpStore %124 %123
2025 OpBranch %126
2026 %126 = OpLabel
2027 %157 = OpPhi %14 %123 %13 %149 %129
2028 OpLoopMerge %128 %129 None
2029 OpBranch %130
2030 %130 = OpLabel
2031 %132 = OpSGreaterThanEqual %36 %157 %101
2032 OpBranchConditional %132 %127 %128
2033 %127 = OpLabel
2034 %137 = OpIAdd %14 %157 %123
2035 %138 = OpAccessChain %15 %133 %137
2036 %139 = OpLoad %14 %138
2037 %140 = OpAccessChain %15 %133 %157
2038 OpStore %140 %139
2039 %143 = OpIAdd %14 %157 %123
2040 %145 = OpAccessChain %15 %133 %157
2041 %146 = OpLoad %14 %145
2042 %147 = OpAccessChain %15 %133 %143
2043 OpStore %147 %146
2044 OpBranch %129
2045 %129 = OpLabel
2046 %149 = OpISub %14 %157 %57
2047 OpStore %124 %149
2048 OpBranch %126
2049 %128 = OpLabel
2050 OpReturn
2051 OpFunctionEnd
2052 )";
2053 std::unique_ptr<IRContext> context =
2054 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
2055 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
2056 Module* module = context->module();
2057 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
2058 << text << std::endl;
2059 {
2060 // Function a
2061 const Function* f = spvtest::GetFunction(module, 6);
2062 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
2063 Loop* loop = &ld.GetLoopByIndex(0);
2064 std::vector<const Loop*> loops{loop};
2065 LoopDependenceAnalysis analysis{context.get(), loops};
2066
2067 const Instruction* stores[2];
2068 int stores_found = 0;
2069 for (const Instruction& inst : *spvtest::GetBasicBlock(f, 30)) {
2070 if (inst.opcode() == SpvOp::SpvOpStore) {
2071 stores[stores_found] = &inst;
2072 ++stores_found;
2073 }
2074 }
2075
2076 for (int i = 0; i < 2; ++i) {
2077 EXPECT_TRUE(stores[i]);
2078 }
2079
2080 // 47 -> 48
2081 {
2082 // Analyse and simplify the instruction behind the access chain of this
2083 // load.
2084 Instruction* load_var = context->get_def_use_mgr()->GetDef(
2085 context->get_def_use_mgr()
2086 ->GetDef(context->get_def_use_mgr()
2087 ->GetDef(47)
2088 ->GetSingleWordInOperand(0))
2089 ->GetSingleWordInOperand(1));
2090 SENode* load = analysis.GetScalarEvolution()->SimplifyExpression(
2091 analysis.GetScalarEvolution()->AnalyzeInstruction(load_var));
2092
2093 // Analyse and simplify the instruction behind the access chain of this
2094 // store.
2095 Instruction* store_var = context->get_def_use_mgr()->GetDef(
2096 context->get_def_use_mgr()
2097 ->GetDef(stores[0]->GetSingleWordInOperand(0))
2098 ->GetSingleWordInOperand(1));
2099 SENode* store = analysis.GetScalarEvolution()->SimplifyExpression(
2100 analysis.GetScalarEvolution()->AnalyzeInstruction(store_var));
2101
2102 SENode* delta = analysis.GetScalarEvolution()->SimplifyExpression(
2103 analysis.GetScalarEvolution()->CreateSubtraction(load, store));
2104
2105 // Independent but not supported.
2106 EXPECT_FALSE(analysis.IsProvablyOutsideOfLoopBounds(
2107 loop, delta, store->AsSERecurrentNode()->GetCoefficient()));
2108 }
2109
2110 // 54 -> 55
2111 {
2112 // Analyse and simplify the instruction behind the access chain of this
2113 // load.
2114 Instruction* load_var = context->get_def_use_mgr()->GetDef(
2115 context->get_def_use_mgr()
2116 ->GetDef(context->get_def_use_mgr()
2117 ->GetDef(54)
2118 ->GetSingleWordInOperand(0))
2119 ->GetSingleWordInOperand(1));
2120 SENode* load = analysis.GetScalarEvolution()->SimplifyExpression(
2121 analysis.GetScalarEvolution()->AnalyzeInstruction(load_var));
2122
2123 // Analyse and simplify the instruction behind the access chain of this
2124 // store.
2125 Instruction* store_var = context->get_def_use_mgr()->GetDef(
2126 context->get_def_use_mgr()
2127 ->GetDef(stores[1]->GetSingleWordInOperand(0))
2128 ->GetSingleWordInOperand(1));
2129 SENode* store = analysis.GetScalarEvolution()->SimplifyExpression(
2130 analysis.GetScalarEvolution()->AnalyzeInstruction(store_var));
2131
2132 SENode* delta = analysis.GetScalarEvolution()->SimplifyExpression(
2133 analysis.GetScalarEvolution()->CreateSubtraction(load, store));
2134
2135 // Independent but not supported.
2136 EXPECT_FALSE(analysis.IsProvablyOutsideOfLoopBounds(
2137 loop, delta, store->AsSERecurrentNode()->GetCoefficient()));
2138 }
2139 }
2140 {
2141 // Function b
2142 const Function* f = spvtest::GetFunction(module, 8);
2143 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
2144 Loop* loop = &ld.GetLoopByIndex(0);
2145 std::vector<const Loop*> loops{loop};
2146 LoopDependenceAnalysis analysis{context.get(), loops};
2147
2148 const Instruction* stores[2];
2149 int stores_found = 0;
2150 for (const Instruction& inst : *spvtest::GetBasicBlock(f, 66)) {
2151 if (inst.opcode() == SpvOp::SpvOpStore) {
2152 stores[stores_found] = &inst;
2153 ++stores_found;
2154 }
2155 }
2156
2157 for (int i = 0; i < 2; ++i) {
2158 EXPECT_TRUE(stores[i]);
2159 }
2160
2161 // 78 -> 79
2162 {
2163 // Analyse and simplify the instruction behind the access chain of this
2164 // load.
2165 Instruction* load_var = context->get_def_use_mgr()->GetDef(
2166 context->get_def_use_mgr()
2167 ->GetDef(context->get_def_use_mgr()
2168 ->GetDef(78)
2169 ->GetSingleWordInOperand(0))
2170 ->GetSingleWordInOperand(1));
2171 SENode* load = analysis.GetScalarEvolution()->SimplifyExpression(
2172 analysis.GetScalarEvolution()->AnalyzeInstruction(load_var));
2173
2174 // Analyse and simplify the instruction behind the access chain of this
2175 // store.
2176 Instruction* store_var = context->get_def_use_mgr()->GetDef(
2177 context->get_def_use_mgr()
2178 ->GetDef(stores[0]->GetSingleWordInOperand(0))
2179 ->GetSingleWordInOperand(1));
2180 SENode* store = analysis.GetScalarEvolution()->SimplifyExpression(
2181 analysis.GetScalarEvolution()->AnalyzeInstruction(store_var));
2182
2183 SENode* delta = analysis.GetScalarEvolution()->SimplifyExpression(
2184 analysis.GetScalarEvolution()->CreateSubtraction(load, store));
2185
2186 // Dependent.
2187 EXPECT_FALSE(analysis.IsProvablyOutsideOfLoopBounds(
2188 loop, delta, store->AsSERecurrentNode()->GetCoefficient()));
2189 }
2190
2191 // 85 -> 86
2192 {
2193 // Analyse and simplify the instruction behind the access chain of this
2194 // load.
2195 Instruction* load_var = context->get_def_use_mgr()->GetDef(
2196 context->get_def_use_mgr()
2197 ->GetDef(context->get_def_use_mgr()
2198 ->GetDef(85)
2199 ->GetSingleWordInOperand(0))
2200 ->GetSingleWordInOperand(1));
2201 SENode* load = analysis.GetScalarEvolution()->SimplifyExpression(
2202 analysis.GetScalarEvolution()->AnalyzeInstruction(load_var));
2203
2204 // Analyse and simplify the instruction behind the access chain of this
2205 // store.
2206 Instruction* store_var = context->get_def_use_mgr()->GetDef(
2207 context->get_def_use_mgr()
2208 ->GetDef(stores[1]->GetSingleWordInOperand(0))
2209 ->GetSingleWordInOperand(1));
2210 SENode* store = analysis.GetScalarEvolution()->SimplifyExpression(
2211 analysis.GetScalarEvolution()->AnalyzeInstruction(store_var));
2212
2213 SENode* delta = analysis.GetScalarEvolution()->SimplifyExpression(
2214 analysis.GetScalarEvolution()->CreateSubtraction(load, store));
2215
2216 // Dependent.
2217 EXPECT_FALSE(analysis.IsProvablyOutsideOfLoopBounds(
2218 loop, delta, store->AsSERecurrentNode()->GetCoefficient()));
2219 }
2220 }
2221 {
2222 // Function c
2223 const Function* f = spvtest::GetFunction(module, 10);
2224 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
2225 Loop* loop = &ld.GetLoopByIndex(0);
2226 std::vector<const Loop*> loops{loop};
2227 LoopDependenceAnalysis analysis{context.get(), loops};
2228
2229 const Instruction* stores[2];
2230 int stores_found = 0;
2231 for (const Instruction& inst : *spvtest::GetBasicBlock(f, 96)) {
2232 if (inst.opcode() == SpvOp::SpvOpStore) {
2233 stores[stores_found] = &inst;
2234 ++stores_found;
2235 }
2236 }
2237
2238 for (int i = 0; i < 2; ++i) {
2239 EXPECT_TRUE(stores[i]);
2240 }
2241
2242 // 109 -> 110
2243 {
2244 // Analyse and simplify the instruction behind the access chain of this
2245 // load.
2246 Instruction* load_var = context->get_def_use_mgr()->GetDef(
2247 context->get_def_use_mgr()
2248 ->GetDef(context->get_def_use_mgr()
2249 ->GetDef(109)
2250 ->GetSingleWordInOperand(0))
2251 ->GetSingleWordInOperand(1));
2252 SENode* load = analysis.GetScalarEvolution()->SimplifyExpression(
2253 analysis.GetScalarEvolution()->AnalyzeInstruction(load_var));
2254
2255 // Analyse and simplify the instruction behind the access chain of this
2256 // store.
2257 Instruction* store_var = context->get_def_use_mgr()->GetDef(
2258 context->get_def_use_mgr()
2259 ->GetDef(stores[0]->GetSingleWordInOperand(0))
2260 ->GetSingleWordInOperand(1));
2261 SENode* store = analysis.GetScalarEvolution()->SimplifyExpression(
2262 analysis.GetScalarEvolution()->AnalyzeInstruction(store_var));
2263
2264 SENode* delta = analysis.GetScalarEvolution()->SimplifyExpression(
2265 analysis.GetScalarEvolution()->CreateSubtraction(load, store));
2266
2267 // Independent and supported.
2268 EXPECT_TRUE(analysis.IsProvablyOutsideOfLoopBounds(
2269 loop, delta, store->AsSERecurrentNode()->GetCoefficient()));
2270 }
2271
2272 // 116 -> 117
2273 {
2274 // Analyse and simplify the instruction behind the access chain of this
2275 // load.
2276 Instruction* load_var = context->get_def_use_mgr()->GetDef(
2277 context->get_def_use_mgr()
2278 ->GetDef(context->get_def_use_mgr()
2279 ->GetDef(116)
2280 ->GetSingleWordInOperand(0))
2281 ->GetSingleWordInOperand(1));
2282 SENode* load = analysis.GetScalarEvolution()->SimplifyExpression(
2283 analysis.GetScalarEvolution()->AnalyzeInstruction(load_var));
2284
2285 // Analyse and simplify the instruction behind the access chain of this
2286 // store.
2287 Instruction* store_var = context->get_def_use_mgr()->GetDef(
2288 context->get_def_use_mgr()
2289 ->GetDef(stores[1]->GetSingleWordInOperand(0))
2290 ->GetSingleWordInOperand(1));
2291 SENode* store = analysis.GetScalarEvolution()->SimplifyExpression(
2292 analysis.GetScalarEvolution()->AnalyzeInstruction(store_var));
2293
2294 SENode* delta = analysis.GetScalarEvolution()->SimplifyExpression(
2295 analysis.GetScalarEvolution()->CreateSubtraction(load, store));
2296
2297 // Independent but not supported.
2298 EXPECT_FALSE(analysis.IsProvablyOutsideOfLoopBounds(
2299 loop, delta, store->AsSERecurrentNode()->GetCoefficient()));
2300 }
2301 }
2302 {
2303 // Function d
2304 const Function* f = spvtest::GetFunction(module, 12);
2305 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
2306 Loop* loop = &ld.GetLoopByIndex(0);
2307 std::vector<const Loop*> loops{loop};
2308 LoopDependenceAnalysis analysis{context.get(), loops};
2309
2310 const Instruction* stores[2];
2311 int stores_found = 0;
2312 for (const Instruction& inst : *spvtest::GetBasicBlock(f, 127)) {
2313 if (inst.opcode() == SpvOp::SpvOpStore) {
2314 stores[stores_found] = &inst;
2315 ++stores_found;
2316 }
2317 }
2318
2319 for (int i = 0; i < 2; ++i) {
2320 EXPECT_TRUE(stores[i]);
2321 }
2322
2323 // 139 -> 140
2324 {
2325 // Analyse and simplify the instruction behind the access chain of this
2326 // load.
2327 Instruction* load_var = context->get_def_use_mgr()->GetDef(
2328 context->get_def_use_mgr()
2329 ->GetDef(context->get_def_use_mgr()
2330 ->GetDef(139)
2331 ->GetSingleWordInOperand(0))
2332 ->GetSingleWordInOperand(1));
2333 SENode* load = analysis.GetScalarEvolution()->SimplifyExpression(
2334 analysis.GetScalarEvolution()->AnalyzeInstruction(load_var));
2335
2336 // Analyse and simplify the instruction behind the access chain of this
2337 // store.
2338 Instruction* store_var = context->get_def_use_mgr()->GetDef(
2339 context->get_def_use_mgr()
2340 ->GetDef(stores[0]->GetSingleWordInOperand(0))
2341 ->GetSingleWordInOperand(1));
2342 SENode* store = analysis.GetScalarEvolution()->SimplifyExpression(
2343 analysis.GetScalarEvolution()->AnalyzeInstruction(store_var));
2344
2345 SENode* delta = analysis.GetScalarEvolution()->SimplifyExpression(
2346 analysis.GetScalarEvolution()->CreateSubtraction(load, store));
2347
2348 // Dependent
2349 EXPECT_FALSE(analysis.IsProvablyOutsideOfLoopBounds(
2350 loop, delta, store->AsSERecurrentNode()->GetCoefficient()));
2351 }
2352
2353 // 146 -> 147
2354 {
2355 // Analyse and simplify the instruction behind the access chain of this
2356 // load.
2357 Instruction* load_var = context->get_def_use_mgr()->GetDef(
2358 context->get_def_use_mgr()
2359 ->GetDef(context->get_def_use_mgr()
2360 ->GetDef(146)
2361 ->GetSingleWordInOperand(0))
2362 ->GetSingleWordInOperand(1));
2363 SENode* load = analysis.GetScalarEvolution()->SimplifyExpression(
2364 analysis.GetScalarEvolution()->AnalyzeInstruction(load_var));
2365
2366 // Analyse and simplify the instruction behind the access chain of this
2367 // store.
2368 Instruction* store_var = context->get_def_use_mgr()->GetDef(
2369 context->get_def_use_mgr()
2370 ->GetDef(stores[1]->GetSingleWordInOperand(0))
2371 ->GetSingleWordInOperand(1));
2372 SENode* store = analysis.GetScalarEvolution()->SimplifyExpression(
2373 analysis.GetScalarEvolution()->AnalyzeInstruction(store_var));
2374
2375 SENode* delta = analysis.GetScalarEvolution()->SimplifyExpression(
2376 analysis.GetScalarEvolution()->CreateSubtraction(load, store));
2377
2378 // Dependent
2379 EXPECT_FALSE(analysis.IsProvablyOutsideOfLoopBounds(
2380 loop, delta, store->AsSERecurrentNode()->GetCoefficient()));
2381 }
2382 }
2383 }
2384
2385 /*
2386 Generated from the following GLSL fragment shader
2387 with --eliminate-local-multi-store
2388 #version 440 core
2389 layout(location = 0) in vec4 in_vec;
2390 // Loop iterates from symbolic to symbolic
2391 void a() {
2392 int M = int(in_vec.x);
2393 int N = int(in_vec.y);
2394 int arr[10];
2395 for (int i = M; i < N; i++) { // Bounds are N - M - 1
2396 arr[i+M+N] = arr[i+M+2*N]; // |distance| = N
2397 arr[i+M+2*N] = arr[i+M+N]; // |distance| = N
2398 }
2399 }
2400 void b() {
2401 int M = int(in_vec.x);
2402 int N = int(in_vec.y);
2403 int arr[10];
2404 for (int i = M; i <= N; i++) { // Bounds are N - M
2405 arr[i+M+N] = arr[i+M+2*N]; // |distance| = N
2406 arr[i+M+2*N] = arr[i+M+N]; // |distance| = N
2407 }
2408 }
2409 void c() {
2410 int M = int(in_vec.x);
2411 int N = int(in_vec.y);
2412 int arr[10];
2413 for (int i = M; i > N; i--) { // Bounds are M - N - 1
2414 arr[i+M+N] = arr[i+M+2*N]; // |distance| = N
2415 arr[i+M+2*N] = arr[i+M+N]; // |distance| = N
2416 }
2417 }
2418 void d() {
2419 int M = int(in_vec.x);
2420 int N = int(in_vec.y);
2421 int arr[10];
2422 for (int i = M; i >= N; i--) { // Bounds are M - N
2423 arr[i+M+N] = arr[i+M+2*N]; // |distance| = N
2424 arr[i+M+2*N] = arr[i+M+N]; // |distance| = N
2425 }
2426 }
2427 void main(){
2428 a();
2429 b();
2430 c();
2431 d();
2432 }
2433 */
TEST(DependencyAnalysisHelpers,symbolic_to_symbolic)2434 TEST(DependencyAnalysisHelpers, symbolic_to_symbolic) {
2435 const std::string text = R"( OpCapability Shader
2436 %1 = OpExtInstImport "GLSL.std.450"
2437 OpMemoryModel Logical GLSL450
2438 OpEntryPoint Fragment %4 "main" %20
2439 OpExecutionMode %4 OriginUpperLeft
2440 OpSource GLSL 440
2441 OpName %4 "main"
2442 OpName %6 "a("
2443 OpName %8 "b("
2444 OpName %10 "c("
2445 OpName %12 "d("
2446 OpName %16 "M"
2447 OpName %20 "in_vec"
2448 OpName %27 "N"
2449 OpName %32 "i"
2450 OpName %46 "arr"
2451 OpName %79 "M"
2452 OpName %83 "N"
2453 OpName %87 "i"
2454 OpName %97 "arr"
2455 OpName %128 "M"
2456 OpName %132 "N"
2457 OpName %136 "i"
2458 OpName %146 "arr"
2459 OpName %177 "M"
2460 OpName %181 "N"
2461 OpName %185 "i"
2462 OpName %195 "arr"
2463 OpDecorate %20 Location 0
2464 %2 = OpTypeVoid
2465 %3 = OpTypeFunction %2
2466 %14 = OpTypeInt 32 1
2467 %15 = OpTypePointer Function %14
2468 %17 = OpTypeFloat 32
2469 %18 = OpTypeVector %17 4
2470 %19 = OpTypePointer Input %18
2471 %20 = OpVariable %19 Input
2472 %21 = OpTypeInt 32 0
2473 %22 = OpConstant %21 0
2474 %23 = OpTypePointer Input %17
2475 %28 = OpConstant %21 1
2476 %41 = OpTypeBool
2477 %43 = OpConstant %21 10
2478 %44 = OpTypeArray %14 %43
2479 %45 = OpTypePointer Function %44
2480 %55 = OpConstant %14 2
2481 %77 = OpConstant %14 1
2482 %4 = OpFunction %2 None %3
2483 %5 = OpLabel
2484 %226 = OpFunctionCall %2 %6
2485 %227 = OpFunctionCall %2 %8
2486 %228 = OpFunctionCall %2 %10
2487 %229 = OpFunctionCall %2 %12
2488 OpReturn
2489 OpFunctionEnd
2490 %6 = OpFunction %2 None %3
2491 %7 = OpLabel
2492 %16 = OpVariable %15 Function
2493 %27 = OpVariable %15 Function
2494 %32 = OpVariable %15 Function
2495 %46 = OpVariable %45 Function
2496 %24 = OpAccessChain %23 %20 %22
2497 %25 = OpLoad %17 %24
2498 %26 = OpConvertFToS %14 %25
2499 OpStore %16 %26
2500 %29 = OpAccessChain %23 %20 %28
2501 %30 = OpLoad %17 %29
2502 %31 = OpConvertFToS %14 %30
2503 OpStore %27 %31
2504 OpStore %32 %26
2505 OpBranch %34
2506 %34 = OpLabel
2507 %230 = OpPhi %14 %26 %7 %78 %37
2508 OpLoopMerge %36 %37 None
2509 OpBranch %38
2510 %38 = OpLabel
2511 %42 = OpSLessThan %41 %230 %31
2512 OpBranchConditional %42 %35 %36
2513 %35 = OpLabel
2514 %49 = OpIAdd %14 %230 %26
2515 %51 = OpIAdd %14 %49 %31
2516 %54 = OpIAdd %14 %230 %26
2517 %57 = OpIMul %14 %55 %31
2518 %58 = OpIAdd %14 %54 %57
2519 %59 = OpAccessChain %15 %46 %58
2520 %60 = OpLoad %14 %59
2521 %61 = OpAccessChain %15 %46 %51
2522 OpStore %61 %60
2523 %64 = OpIAdd %14 %230 %26
2524 %66 = OpIMul %14 %55 %31
2525 %67 = OpIAdd %14 %64 %66
2526 %70 = OpIAdd %14 %230 %26
2527 %72 = OpIAdd %14 %70 %31
2528 %73 = OpAccessChain %15 %46 %72
2529 %74 = OpLoad %14 %73
2530 %75 = OpAccessChain %15 %46 %67
2531 OpStore %75 %74
2532 OpBranch %37
2533 %37 = OpLabel
2534 %78 = OpIAdd %14 %230 %77
2535 OpStore %32 %78
2536 OpBranch %34
2537 %36 = OpLabel
2538 OpReturn
2539 OpFunctionEnd
2540 %8 = OpFunction %2 None %3
2541 %9 = OpLabel
2542 %79 = OpVariable %15 Function
2543 %83 = OpVariable %15 Function
2544 %87 = OpVariable %15 Function
2545 %97 = OpVariable %45 Function
2546 %80 = OpAccessChain %23 %20 %22
2547 %81 = OpLoad %17 %80
2548 %82 = OpConvertFToS %14 %81
2549 OpStore %79 %82
2550 %84 = OpAccessChain %23 %20 %28
2551 %85 = OpLoad %17 %84
2552 %86 = OpConvertFToS %14 %85
2553 OpStore %83 %86
2554 OpStore %87 %82
2555 OpBranch %89
2556 %89 = OpLabel
2557 %231 = OpPhi %14 %82 %9 %127 %92
2558 OpLoopMerge %91 %92 None
2559 OpBranch %93
2560 %93 = OpLabel
2561 %96 = OpSLessThanEqual %41 %231 %86
2562 OpBranchConditional %96 %90 %91
2563 %90 = OpLabel
2564 %100 = OpIAdd %14 %231 %82
2565 %102 = OpIAdd %14 %100 %86
2566 %105 = OpIAdd %14 %231 %82
2567 %107 = OpIMul %14 %55 %86
2568 %108 = OpIAdd %14 %105 %107
2569 %109 = OpAccessChain %15 %97 %108
2570 %110 = OpLoad %14 %109
2571 %111 = OpAccessChain %15 %97 %102
2572 OpStore %111 %110
2573 %114 = OpIAdd %14 %231 %82
2574 %116 = OpIMul %14 %55 %86
2575 %117 = OpIAdd %14 %114 %116
2576 %120 = OpIAdd %14 %231 %82
2577 %122 = OpIAdd %14 %120 %86
2578 %123 = OpAccessChain %15 %97 %122
2579 %124 = OpLoad %14 %123
2580 %125 = OpAccessChain %15 %97 %117
2581 OpStore %125 %124
2582 OpBranch %92
2583 %92 = OpLabel
2584 %127 = OpIAdd %14 %231 %77
2585 OpStore %87 %127
2586 OpBranch %89
2587 %91 = OpLabel
2588 OpReturn
2589 OpFunctionEnd
2590 %10 = OpFunction %2 None %3
2591 %11 = OpLabel
2592 %128 = OpVariable %15 Function
2593 %132 = OpVariable %15 Function
2594 %136 = OpVariable %15 Function
2595 %146 = OpVariable %45 Function
2596 %129 = OpAccessChain %23 %20 %22
2597 %130 = OpLoad %17 %129
2598 %131 = OpConvertFToS %14 %130
2599 OpStore %128 %131
2600 %133 = OpAccessChain %23 %20 %28
2601 %134 = OpLoad %17 %133
2602 %135 = OpConvertFToS %14 %134
2603 OpStore %132 %135
2604 OpStore %136 %131
2605 OpBranch %138
2606 %138 = OpLabel
2607 %232 = OpPhi %14 %131 %11 %176 %141
2608 OpLoopMerge %140 %141 None
2609 OpBranch %142
2610 %142 = OpLabel
2611 %145 = OpSGreaterThan %41 %232 %135
2612 OpBranchConditional %145 %139 %140
2613 %139 = OpLabel
2614 %149 = OpIAdd %14 %232 %131
2615 %151 = OpIAdd %14 %149 %135
2616 %154 = OpIAdd %14 %232 %131
2617 %156 = OpIMul %14 %55 %135
2618 %157 = OpIAdd %14 %154 %156
2619 %158 = OpAccessChain %15 %146 %157
2620 %159 = OpLoad %14 %158
2621 %160 = OpAccessChain %15 %146 %151
2622 OpStore %160 %159
2623 %163 = OpIAdd %14 %232 %131
2624 %165 = OpIMul %14 %55 %135
2625 %166 = OpIAdd %14 %163 %165
2626 %169 = OpIAdd %14 %232 %131
2627 %171 = OpIAdd %14 %169 %135
2628 %172 = OpAccessChain %15 %146 %171
2629 %173 = OpLoad %14 %172
2630 %174 = OpAccessChain %15 %146 %166
2631 OpStore %174 %173
2632 OpBranch %141
2633 %141 = OpLabel
2634 %176 = OpISub %14 %232 %77
2635 OpStore %136 %176
2636 OpBranch %138
2637 %140 = OpLabel
2638 OpReturn
2639 OpFunctionEnd
2640 %12 = OpFunction %2 None %3
2641 %13 = OpLabel
2642 %177 = OpVariable %15 Function
2643 %181 = OpVariable %15 Function
2644 %185 = OpVariable %15 Function
2645 %195 = OpVariable %45 Function
2646 %178 = OpAccessChain %23 %20 %22
2647 %179 = OpLoad %17 %178
2648 %180 = OpConvertFToS %14 %179
2649 OpStore %177 %180
2650 %182 = OpAccessChain %23 %20 %28
2651 %183 = OpLoad %17 %182
2652 %184 = OpConvertFToS %14 %183
2653 OpStore %181 %184
2654 OpStore %185 %180
2655 OpBranch %187
2656 %187 = OpLabel
2657 %233 = OpPhi %14 %180 %13 %225 %190
2658 OpLoopMerge %189 %190 None
2659 OpBranch %191
2660 %191 = OpLabel
2661 %194 = OpSGreaterThanEqual %41 %233 %184
2662 OpBranchConditional %194 %188 %189
2663 %188 = OpLabel
2664 %198 = OpIAdd %14 %233 %180
2665 %200 = OpIAdd %14 %198 %184
2666 %203 = OpIAdd %14 %233 %180
2667 %205 = OpIMul %14 %55 %184
2668 %206 = OpIAdd %14 %203 %205
2669 %207 = OpAccessChain %15 %195 %206
2670 %208 = OpLoad %14 %207
2671 %209 = OpAccessChain %15 %195 %200
2672 OpStore %209 %208
2673 %212 = OpIAdd %14 %233 %180
2674 %214 = OpIMul %14 %55 %184
2675 %215 = OpIAdd %14 %212 %214
2676 %218 = OpIAdd %14 %233 %180
2677 %220 = OpIAdd %14 %218 %184
2678 %221 = OpAccessChain %15 %195 %220
2679 %222 = OpLoad %14 %221
2680 %223 = OpAccessChain %15 %195 %215
2681 OpStore %223 %222
2682 OpBranch %190
2683 %190 = OpLabel
2684 %225 = OpISub %14 %233 %77
2685 OpStore %185 %225
2686 OpBranch %187
2687 %189 = OpLabel
2688 OpReturn
2689 OpFunctionEnd
2690 )";
2691 std::unique_ptr<IRContext> context =
2692 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
2693 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
2694 Module* module = context->module();
2695 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
2696 << text << std::endl;
2697 {
2698 // Function a
2699 const Function* f = spvtest::GetFunction(module, 6);
2700 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
2701 Loop* loop = &ld.GetLoopByIndex(0);
2702 std::vector<const Loop*> loops{loop};
2703 LoopDependenceAnalysis analysis{context.get(), loops};
2704
2705 const Instruction* stores[2];
2706 int stores_found = 0;
2707 for (const Instruction& inst : *spvtest::GetBasicBlock(f, 35)) {
2708 if (inst.opcode() == SpvOp::SpvOpStore) {
2709 stores[stores_found] = &inst;
2710 ++stores_found;
2711 }
2712 }
2713
2714 for (int i = 0; i < 2; ++i) {
2715 EXPECT_TRUE(stores[i]);
2716 }
2717
2718 // 60 -> 61
2719 {
2720 // Analyse and simplify the instruction behind the access chain of this
2721 // load.
2722 Instruction* load_var = context->get_def_use_mgr()->GetDef(
2723 context->get_def_use_mgr()
2724 ->GetDef(context->get_def_use_mgr()
2725 ->GetDef(60)
2726 ->GetSingleWordInOperand(0))
2727 ->GetSingleWordInOperand(1));
2728 SENode* load = analysis.GetScalarEvolution()->SimplifyExpression(
2729 analysis.GetScalarEvolution()->AnalyzeInstruction(load_var));
2730
2731 // Analyse and simplify the instruction behind the access chain of this
2732 // store.
2733 Instruction* store_var = context->get_def_use_mgr()->GetDef(
2734 context->get_def_use_mgr()
2735 ->GetDef(stores[0]->GetSingleWordInOperand(0))
2736 ->GetSingleWordInOperand(1));
2737 SENode* store = analysis.GetScalarEvolution()->SimplifyExpression(
2738 analysis.GetScalarEvolution()->AnalyzeInstruction(store_var));
2739
2740 SENode* delta = analysis.GetScalarEvolution()->SimplifyExpression(
2741 analysis.GetScalarEvolution()->CreateSubtraction(load, store));
2742
2743 EXPECT_FALSE(analysis.IsProvablyOutsideOfLoopBounds(
2744 loop, delta, store->AsSERecurrentNode()->GetCoefficient()));
2745 }
2746
2747 // 74 -> 75
2748 {
2749 // Analyse and simplify the instruction behind the access chain of this
2750 // load.
2751 Instruction* load_var = context->get_def_use_mgr()->GetDef(
2752 context->get_def_use_mgr()
2753 ->GetDef(context->get_def_use_mgr()
2754 ->GetDef(74)
2755 ->GetSingleWordInOperand(0))
2756 ->GetSingleWordInOperand(1));
2757 SENode* load = analysis.GetScalarEvolution()->SimplifyExpression(
2758 analysis.GetScalarEvolution()->AnalyzeInstruction(load_var));
2759
2760 // Analyse and simplify the instruction behind the access chain of this
2761 // store.
2762 Instruction* store_var = context->get_def_use_mgr()->GetDef(
2763 context->get_def_use_mgr()
2764 ->GetDef(stores[1]->GetSingleWordInOperand(0))
2765 ->GetSingleWordInOperand(1));
2766 SENode* store = analysis.GetScalarEvolution()->SimplifyExpression(
2767 analysis.GetScalarEvolution()->AnalyzeInstruction(store_var));
2768
2769 SENode* delta = analysis.GetScalarEvolution()->SimplifyExpression(
2770 analysis.GetScalarEvolution()->CreateSubtraction(load, store));
2771
2772 EXPECT_FALSE(analysis.IsProvablyOutsideOfLoopBounds(
2773 loop, delta, store->AsSERecurrentNode()->GetCoefficient()));
2774 }
2775 }
2776 {
2777 // Function b
2778 const Function* f = spvtest::GetFunction(module, 8);
2779 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
2780 Loop* loop = &ld.GetLoopByIndex(0);
2781 std::vector<const Loop*> loops{loop};
2782 LoopDependenceAnalysis analysis{context.get(), loops};
2783
2784 const Instruction* stores[2];
2785 int stores_found = 0;
2786 for (const Instruction& inst : *spvtest::GetBasicBlock(f, 90)) {
2787 if (inst.opcode() == SpvOp::SpvOpStore) {
2788 stores[stores_found] = &inst;
2789 ++stores_found;
2790 }
2791 }
2792
2793 for (int i = 0; i < 2; ++i) {
2794 EXPECT_TRUE(stores[i]);
2795 }
2796
2797 // 110 -> 111
2798 {
2799 // Analyse and simplify the instruction behind the access chain of this
2800 // load.
2801 Instruction* load_var = context->get_def_use_mgr()->GetDef(
2802 context->get_def_use_mgr()
2803 ->GetDef(context->get_def_use_mgr()
2804 ->GetDef(110)
2805 ->GetSingleWordInOperand(0))
2806 ->GetSingleWordInOperand(1));
2807 SENode* load = analysis.GetScalarEvolution()->SimplifyExpression(
2808 analysis.GetScalarEvolution()->AnalyzeInstruction(load_var));
2809
2810 // Analyse and simplify the instruction behind the access chain of this
2811 // store.
2812 Instruction* store_var = context->get_def_use_mgr()->GetDef(
2813 context->get_def_use_mgr()
2814 ->GetDef(stores[0]->GetSingleWordInOperand(0))
2815 ->GetSingleWordInOperand(1));
2816 SENode* store = analysis.GetScalarEvolution()->SimplifyExpression(
2817 analysis.GetScalarEvolution()->AnalyzeInstruction(store_var));
2818
2819 SENode* delta = analysis.GetScalarEvolution()->SimplifyExpression(
2820 analysis.GetScalarEvolution()->CreateSubtraction(load, store));
2821
2822 EXPECT_FALSE(analysis.IsProvablyOutsideOfLoopBounds(
2823 loop, delta, store->AsSERecurrentNode()->GetCoefficient()));
2824 }
2825
2826 // 124 -> 125
2827 {
2828 // Analyse and simplify the instruction behind the access chain of this
2829 // load.
2830 Instruction* load_var = context->get_def_use_mgr()->GetDef(
2831 context->get_def_use_mgr()
2832 ->GetDef(context->get_def_use_mgr()
2833 ->GetDef(124)
2834 ->GetSingleWordInOperand(0))
2835 ->GetSingleWordInOperand(1));
2836 SENode* load = analysis.GetScalarEvolution()->SimplifyExpression(
2837 analysis.GetScalarEvolution()->AnalyzeInstruction(load_var));
2838
2839 // Analyse and simplify the instruction behind the access chain of this
2840 // store.
2841 Instruction* store_var = context->get_def_use_mgr()->GetDef(
2842 context->get_def_use_mgr()
2843 ->GetDef(stores[1]->GetSingleWordInOperand(0))
2844 ->GetSingleWordInOperand(1));
2845 SENode* store = analysis.GetScalarEvolution()->SimplifyExpression(
2846 analysis.GetScalarEvolution()->AnalyzeInstruction(store_var));
2847
2848 SENode* delta = analysis.GetScalarEvolution()->SimplifyExpression(
2849 analysis.GetScalarEvolution()->CreateSubtraction(load, store));
2850
2851 EXPECT_FALSE(analysis.IsProvablyOutsideOfLoopBounds(
2852 loop, delta, store->AsSERecurrentNode()->GetCoefficient()));
2853 }
2854 }
2855 {
2856 // Function c
2857 const Function* f = spvtest::GetFunction(module, 10);
2858 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
2859 Loop* loop = &ld.GetLoopByIndex(0);
2860 std::vector<const Loop*> loops{loop};
2861 LoopDependenceAnalysis analysis{context.get(), loops};
2862
2863 const Instruction* stores[2];
2864 int stores_found = 0;
2865 for (const Instruction& inst : *spvtest::GetBasicBlock(f, 139)) {
2866 if (inst.opcode() == SpvOp::SpvOpStore) {
2867 stores[stores_found] = &inst;
2868 ++stores_found;
2869 }
2870 }
2871
2872 for (int i = 0; i < 2; ++i) {
2873 EXPECT_TRUE(stores[i]);
2874 }
2875
2876 // 159 -> 160
2877 {
2878 // Analyse and simplify the instruction behind the access chain of this
2879 // load.
2880 Instruction* load_var = context->get_def_use_mgr()->GetDef(
2881 context->get_def_use_mgr()
2882 ->GetDef(context->get_def_use_mgr()
2883 ->GetDef(159)
2884 ->GetSingleWordInOperand(0))
2885 ->GetSingleWordInOperand(1));
2886 SENode* load = analysis.GetScalarEvolution()->SimplifyExpression(
2887 analysis.GetScalarEvolution()->AnalyzeInstruction(load_var));
2888
2889 // Analyse and simplify the instruction behind the access chain of this
2890 // store.
2891 Instruction* store_var = context->get_def_use_mgr()->GetDef(
2892 context->get_def_use_mgr()
2893 ->GetDef(stores[0]->GetSingleWordInOperand(0))
2894 ->GetSingleWordInOperand(1));
2895 SENode* store = analysis.GetScalarEvolution()->SimplifyExpression(
2896 analysis.GetScalarEvolution()->AnalyzeInstruction(store_var));
2897
2898 SENode* delta = analysis.GetScalarEvolution()->SimplifyExpression(
2899 analysis.GetScalarEvolution()->CreateSubtraction(load, store));
2900
2901 EXPECT_FALSE(analysis.IsProvablyOutsideOfLoopBounds(
2902 loop, delta, store->AsSERecurrentNode()->GetCoefficient()));
2903 }
2904
2905 // 173 -> 174
2906 {
2907 // Analyse and simplify the instruction behind the access chain of this
2908 // load.
2909 Instruction* load_var = context->get_def_use_mgr()->GetDef(
2910 context->get_def_use_mgr()
2911 ->GetDef(context->get_def_use_mgr()
2912 ->GetDef(173)
2913 ->GetSingleWordInOperand(0))
2914 ->GetSingleWordInOperand(1));
2915 SENode* load = analysis.GetScalarEvolution()->SimplifyExpression(
2916 analysis.GetScalarEvolution()->AnalyzeInstruction(load_var));
2917
2918 // Analyse and simplify the instruction behind the access chain of this
2919 // store.
2920 Instruction* store_var = context->get_def_use_mgr()->GetDef(
2921 context->get_def_use_mgr()
2922 ->GetDef(stores[1]->GetSingleWordInOperand(0))
2923 ->GetSingleWordInOperand(1));
2924 SENode* store = analysis.GetScalarEvolution()->SimplifyExpression(
2925 analysis.GetScalarEvolution()->AnalyzeInstruction(store_var));
2926
2927 SENode* delta = analysis.GetScalarEvolution()->SimplifyExpression(
2928 analysis.GetScalarEvolution()->CreateSubtraction(load, store));
2929
2930 EXPECT_FALSE(analysis.IsProvablyOutsideOfLoopBounds(
2931 loop, delta, store->AsSERecurrentNode()->GetCoefficient()));
2932 }
2933 }
2934 {
2935 // Function d
2936 const Function* f = spvtest::GetFunction(module, 12);
2937 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
2938 Loop* loop = &ld.GetLoopByIndex(0);
2939 std::vector<const Loop*> loops{loop};
2940 LoopDependenceAnalysis analysis{context.get(), loops};
2941
2942 const Instruction* stores[2];
2943 int stores_found = 0;
2944 for (const Instruction& inst : *spvtest::GetBasicBlock(f, 188)) {
2945 if (inst.opcode() == SpvOp::SpvOpStore) {
2946 stores[stores_found] = &inst;
2947 ++stores_found;
2948 }
2949 }
2950
2951 for (int i = 0; i < 2; ++i) {
2952 EXPECT_TRUE(stores[i]);
2953 }
2954
2955 // 208 -> 209
2956 {
2957 // Analyse and simplify the instruction behind the access chain of this
2958 // load.
2959 Instruction* load_var = context->get_def_use_mgr()->GetDef(
2960 context->get_def_use_mgr()
2961 ->GetDef(context->get_def_use_mgr()
2962 ->GetDef(208)
2963 ->GetSingleWordInOperand(0))
2964 ->GetSingleWordInOperand(1));
2965 SENode* load = analysis.GetScalarEvolution()->SimplifyExpression(
2966 analysis.GetScalarEvolution()->AnalyzeInstruction(load_var));
2967
2968 // Analyse and simplify the instruction behind the access chain of this
2969 // store.
2970 Instruction* store_var = context->get_def_use_mgr()->GetDef(
2971 context->get_def_use_mgr()
2972 ->GetDef(stores[0]->GetSingleWordInOperand(0))
2973 ->GetSingleWordInOperand(1));
2974 SENode* store = analysis.GetScalarEvolution()->SimplifyExpression(
2975 analysis.GetScalarEvolution()->AnalyzeInstruction(store_var));
2976
2977 SENode* delta = analysis.GetScalarEvolution()->SimplifyExpression(
2978 analysis.GetScalarEvolution()->CreateSubtraction(load, store));
2979
2980 EXPECT_FALSE(analysis.IsProvablyOutsideOfLoopBounds(
2981 loop, delta, store->AsSERecurrentNode()->GetCoefficient()));
2982 }
2983
2984 // 222 -> 223
2985 {
2986 // Analyse and simplify the instruction behind the access chain of this
2987 // load.
2988 Instruction* load_var = context->get_def_use_mgr()->GetDef(
2989 context->get_def_use_mgr()
2990 ->GetDef(context->get_def_use_mgr()
2991 ->GetDef(222)
2992 ->GetSingleWordInOperand(0))
2993 ->GetSingleWordInOperand(1));
2994 SENode* load = analysis.GetScalarEvolution()->SimplifyExpression(
2995 analysis.GetScalarEvolution()->AnalyzeInstruction(load_var));
2996
2997 // Analyse and simplify the instruction behind the access chain of this
2998 // store.
2999 Instruction* store_var = context->get_def_use_mgr()->GetDef(
3000 context->get_def_use_mgr()
3001 ->GetDef(stores[1]->GetSingleWordInOperand(0))
3002 ->GetSingleWordInOperand(1));
3003 SENode* store = analysis.GetScalarEvolution()->SimplifyExpression(
3004 analysis.GetScalarEvolution()->AnalyzeInstruction(store_var));
3005
3006 SENode* delta = analysis.GetScalarEvolution()->SimplifyExpression(
3007 analysis.GetScalarEvolution()->CreateSubtraction(load, store));
3008
3009 EXPECT_FALSE(analysis.IsProvablyOutsideOfLoopBounds(
3010 loop, delta, store->AsSERecurrentNode()->GetCoefficient()));
3011 }
3012 }
3013 }
3014
3015 } // namespace
3016 } // namespace opt
3017 } // namespace spvtools
3018