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