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