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 <set>
17 #include <utility>
18 #include <vector>
19
20 #include "source/opt/loop_dependence.h"
21 #include "source/opt/loop_descriptor.h"
22 #include "test/opt/assembly_builder.h"
23 #include "test/opt/function_utils.h"
24 #include "test/opt/pass_fixture.h"
25 #include "test/opt/pass_utils.h"
26
27 namespace spvtools {
28 namespace opt {
29 namespace {
30
31 using DependencyAnalysis = ::testing::Test;
32
33 /*
34 Generated from the following GLSL fragment shader
35 with --eliminate-local-multi-store
36 #version 440 core
37 void main(){
38 int[10] arr;
39 int[10] arr2;
40 int a = 2;
41 for (int i = 0; i < 10; i++) {
42 arr[a] = arr[3];
43 arr[a*2] = arr[a+3];
44 arr[6] = arr2[6];
45 arr[a+5] = arr2[7];
46 }
47 }
48 */
TEST(DependencyAnalysis,ZIV)49 TEST(DependencyAnalysis, ZIV) {
50 const std::string text = R"( OpCapability Shader
51 %1 = OpExtInstImport "GLSL.std.450"
52 OpMemoryModel Logical GLSL450
53 OpEntryPoint Fragment %4 "main"
54 OpExecutionMode %4 OriginUpperLeft
55 OpSource GLSL 440
56 OpName %4 "main"
57 OpName %25 "arr"
58 OpName %39 "arr2"
59 %2 = OpTypeVoid
60 %3 = OpTypeFunction %2
61 %6 = OpTypeInt 32 1
62 %7 = OpTypePointer Function %6
63 %9 = OpConstant %6 2
64 %11 = OpConstant %6 0
65 %18 = OpConstant %6 10
66 %19 = OpTypeBool
67 %21 = OpTypeInt 32 0
68 %22 = OpConstant %21 10
69 %23 = OpTypeArray %6 %22
70 %24 = OpTypePointer Function %23
71 %27 = OpConstant %6 3
72 %38 = OpConstant %6 6
73 %44 = OpConstant %6 5
74 %46 = OpConstant %6 7
75 %51 = OpConstant %6 1
76 %4 = OpFunction %2 None %3
77 %5 = OpLabel
78 %25 = OpVariable %24 Function
79 %39 = OpVariable %24 Function
80 OpBranch %12
81 %12 = OpLabel
82 %53 = OpPhi %6 %11 %5 %52 %15
83 OpLoopMerge %14 %15 None
84 OpBranch %16
85 %16 = OpLabel
86 %20 = OpSLessThan %19 %53 %18
87 OpBranchConditional %20 %13 %14
88 %13 = OpLabel
89 %28 = OpAccessChain %7 %25 %27
90 %29 = OpLoad %6 %28
91 %30 = OpAccessChain %7 %25 %9
92 OpStore %30 %29
93 %32 = OpIMul %6 %9 %9
94 %34 = OpIAdd %6 %9 %27
95 %35 = OpAccessChain %7 %25 %34
96 %36 = OpLoad %6 %35
97 %37 = OpAccessChain %7 %25 %32
98 OpStore %37 %36
99 %40 = OpAccessChain %7 %39 %38
100 %41 = OpLoad %6 %40
101 %42 = OpAccessChain %7 %25 %38
102 OpStore %42 %41
103 %45 = OpIAdd %6 %9 %44
104 %47 = OpAccessChain %7 %39 %46
105 %48 = OpLoad %6 %47
106 %49 = OpAccessChain %7 %25 %45
107 OpStore %49 %48
108 OpBranch %15
109 %15 = OpLabel
110 %52 = OpIAdd %6 %53 %51
111 OpBranch %12
112 %14 = OpLabel
113 OpReturn
114 OpFunctionEnd
115 )";
116 std::unique_ptr<IRContext> context =
117 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
118 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
119 Module* module = context->module();
120 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
121 << text << std::endl;
122 const Function* f = spvtest::GetFunction(module, 4);
123 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
124
125 Loop* loop = &ld.GetLoopByIndex(0);
126 std::vector<const Loop*> loops{loop};
127 LoopDependenceAnalysis analysis{context.get(), loops};
128
129 const Instruction* store[4];
130 int stores_found = 0;
131 for (const Instruction& inst : *spvtest::GetBasicBlock(f, 13)) {
132 if (inst.opcode() == spv::Op::OpStore) {
133 store[stores_found] = &inst;
134 ++stores_found;
135 }
136 }
137
138 for (int i = 0; i < 4; ++i) {
139 EXPECT_TRUE(store[i]);
140 }
141
142 // 29 -> 30 tests looking through constants.
143 {
144 DistanceVector distance_vector{loops.size()};
145 EXPECT_TRUE(analysis.GetDependence(context->get_def_use_mgr()->GetDef(29),
146 store[0], &distance_vector));
147 }
148
149 // 36 -> 37 tests looking through additions.
150 {
151 DistanceVector distance_vector{loops.size()};
152 EXPECT_TRUE(analysis.GetDependence(context->get_def_use_mgr()->GetDef(36),
153 store[1], &distance_vector));
154 }
155
156 // 41 -> 42 tests looking at same index across two different arrays.
157 {
158 DistanceVector distance_vector{loops.size()};
159 EXPECT_TRUE(analysis.GetDependence(context->get_def_use_mgr()->GetDef(41),
160 store[2], &distance_vector));
161 }
162
163 // 48 -> 49 tests looking through additions for same index in two different
164 // arrays.
165 {
166 DistanceVector distance_vector{loops.size()};
167 EXPECT_TRUE(analysis.GetDependence(context->get_def_use_mgr()->GetDef(48),
168 store[3], &distance_vector));
169 }
170 }
171
172 /*
173 Generated from the following GLSL fragment shader
174 with --eliminate-local-multi-store
175 #version 440 core
176 layout(location = 0) in vec4 c;
177 void main(){
178 int[10] arr;
179 int[10] arr2;
180 int[10] arr3;
181 int[10] arr4;
182 int[10] arr5;
183 int N = int(c.x);
184 for (int i = 0; i < N; i++) {
185 arr[2*N] = arr[N];
186 arr2[2*N+1] = arr2[N];
187 arr3[2*N] = arr3[N-1];
188 arr4[N] = arr5[N];
189 }
190 }
191 */
TEST(DependencyAnalysis,SymbolicZIV)192 TEST(DependencyAnalysis, SymbolicZIV) {
193 const std::string text = R"( OpCapability Shader
194 %1 = OpExtInstImport "GLSL.std.450"
195 OpMemoryModel Logical GLSL450
196 OpEntryPoint Fragment %4 "main" %12
197 OpExecutionMode %4 OriginUpperLeft
198 OpSource GLSL 440
199 OpName %4 "main"
200 OpName %12 "c"
201 OpName %33 "arr"
202 OpName %41 "arr2"
203 OpName %50 "arr3"
204 OpName %58 "arr4"
205 OpName %60 "arr5"
206 OpDecorate %12 Location 0
207 %2 = OpTypeVoid
208 %3 = OpTypeFunction %2
209 %6 = OpTypeInt 32 1
210 %7 = OpTypePointer Function %6
211 %9 = OpTypeFloat 32
212 %10 = OpTypeVector %9 4
213 %11 = OpTypePointer Input %10
214 %12 = OpVariable %11 Input
215 %13 = OpTypeInt 32 0
216 %14 = OpConstant %13 0
217 %15 = OpTypePointer Input %9
218 %20 = OpConstant %6 0
219 %28 = OpTypeBool
220 %30 = OpConstant %13 10
221 %31 = OpTypeArray %6 %30
222 %32 = OpTypePointer Function %31
223 %34 = OpConstant %6 2
224 %44 = OpConstant %6 1
225 %4 = OpFunction %2 None %3
226 %5 = OpLabel
227 %33 = OpVariable %32 Function
228 %41 = OpVariable %32 Function
229 %50 = OpVariable %32 Function
230 %58 = OpVariable %32 Function
231 %60 = OpVariable %32 Function
232 %16 = OpAccessChain %15 %12 %14
233 %17 = OpLoad %9 %16
234 %18 = OpConvertFToS %6 %17
235 OpBranch %21
236 %21 = OpLabel
237 %67 = OpPhi %6 %20 %5 %66 %24
238 OpLoopMerge %23 %24 None
239 OpBranch %25
240 %25 = OpLabel
241 %29 = OpSLessThan %28 %67 %18
242 OpBranchConditional %29 %22 %23
243 %22 = OpLabel
244 %36 = OpIMul %6 %34 %18
245 %38 = OpAccessChain %7 %33 %18
246 %39 = OpLoad %6 %38
247 %40 = OpAccessChain %7 %33 %36
248 OpStore %40 %39
249 %43 = OpIMul %6 %34 %18
250 %45 = OpIAdd %6 %43 %44
251 %47 = OpAccessChain %7 %41 %18
252 %48 = OpLoad %6 %47
253 %49 = OpAccessChain %7 %41 %45
254 OpStore %49 %48
255 %52 = OpIMul %6 %34 %18
256 %54 = OpISub %6 %18 %44
257 %55 = OpAccessChain %7 %50 %54
258 %56 = OpLoad %6 %55
259 %57 = OpAccessChain %7 %50 %52
260 OpStore %57 %56
261 %62 = OpAccessChain %7 %60 %18
262 %63 = OpLoad %6 %62
263 %64 = OpAccessChain %7 %58 %18
264 OpStore %64 %63
265 OpBranch %24
266 %24 = OpLabel
267 %66 = OpIAdd %6 %67 %44
268 OpBranch %21
269 %23 = OpLabel
270 OpReturn
271 OpFunctionEnd
272 )";
273 std::unique_ptr<IRContext> context =
274 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
275 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
276 Module* module = context->module();
277 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
278 << text << std::endl;
279 const Function* f = spvtest::GetFunction(module, 4);
280 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
281
282 Loop* loop = &ld.GetLoopByIndex(0);
283 std::vector<const Loop*> loops{loop};
284 LoopDependenceAnalysis analysis{context.get(), loops};
285
286 const Instruction* store[4];
287 int stores_found = 0;
288 for (const Instruction& inst : *spvtest::GetBasicBlock(f, 22)) {
289 if (inst.opcode() == spv::Op::OpStore) {
290 store[stores_found] = &inst;
291 ++stores_found;
292 }
293 }
294
295 for (int i = 0; i < 4; ++i) {
296 EXPECT_TRUE(store[i]);
297 }
298
299 // independent due to loop bounds (won't enter if N <= 0).
300 // 39 -> 40 tests looking through symbols and multiplicaiton.
301 {
302 DistanceVector distance_vector{loops.size()};
303 EXPECT_TRUE(analysis.GetDependence(context->get_def_use_mgr()->GetDef(39),
304 store[0], &distance_vector));
305 }
306
307 // 48 -> 49 tests looking through symbols and multiplication + addition.
308 {
309 DistanceVector distance_vector{loops.size()};
310 EXPECT_TRUE(analysis.GetDependence(context->get_def_use_mgr()->GetDef(48),
311 store[1], &distance_vector));
312 }
313
314 // 56 -> 57 tests looking through symbols and arithmetic on load and store.
315 {
316 DistanceVector distance_vector{loops.size()};
317 EXPECT_TRUE(analysis.GetDependence(context->get_def_use_mgr()->GetDef(56),
318 store[2], &distance_vector));
319 }
320
321 // independent as different arrays
322 // 63 -> 64 tests looking through symbols and load/store from/to different
323 // arrays.
324 {
325 DistanceVector distance_vector{loops.size()};
326 EXPECT_TRUE(analysis.GetDependence(context->get_def_use_mgr()->GetDef(63),
327 store[3], &distance_vector));
328 }
329 }
330
331 /*
332 Generated from the following GLSL fragment shader
333 with --eliminate-local-multi-store
334 #version 440 core
335 void a(){
336 int[10] arr;
337 int[11] arr2;
338 int[20] arr3;
339 int[20] arr4;
340 int a = 2;
341 for (int i = 0; i < 10; i++) {
342 arr[i] = arr[i];
343 arr2[i] = arr2[i+1];
344 arr3[i] = arr3[i-1];
345 arr4[2*i] = arr4[i];
346 }
347 }
348 void b(){
349 int[10] arr;
350 int[11] arr2;
351 int[20] arr3;
352 int[20] arr4;
353 int a = 2;
354 for (int i = 10; i > 0; i--) {
355 arr[i] = arr[i];
356 arr2[i] = arr2[i+1];
357 arr3[i] = arr3[i-1];
358 arr4[2*i] = arr4[i];
359 }
360 }
361
362 void main() {
363 a();
364 b();
365 }
366 */
TEST(DependencyAnalysis,SIV)367 TEST(DependencyAnalysis, SIV) {
368 const std::string text = R"( OpCapability Shader
369 %1 = OpExtInstImport "GLSL.std.450"
370 OpMemoryModel Logical GLSL450
371 OpEntryPoint Fragment %4 "main"
372 OpExecutionMode %4 OriginUpperLeft
373 OpSource GLSL 440
374 OpName %4 "main"
375 OpName %6 "a("
376 OpName %8 "b("
377 OpName %12 "a"
378 OpName %14 "i"
379 OpName %29 "arr"
380 OpName %38 "arr2"
381 OpName %49 "arr3"
382 OpName %56 "arr4"
383 OpName %65 "a"
384 OpName %66 "i"
385 OpName %74 "arr"
386 OpName %80 "arr2"
387 OpName %87 "arr3"
388 OpName %94 "arr4"
389 %2 = OpTypeVoid
390 %3 = OpTypeFunction %2
391 %10 = OpTypeInt 32 1
392 %11 = OpTypePointer Function %10
393 %13 = OpConstant %10 2
394 %15 = OpConstant %10 0
395 %22 = OpConstant %10 10
396 %23 = OpTypeBool
397 %25 = OpTypeInt 32 0
398 %26 = OpConstant %25 10
399 %27 = OpTypeArray %10 %26
400 %28 = OpTypePointer Function %27
401 %35 = OpConstant %25 11
402 %36 = OpTypeArray %10 %35
403 %37 = OpTypePointer Function %36
404 %41 = OpConstant %10 1
405 %46 = OpConstant %25 20
406 %47 = OpTypeArray %10 %46
407 %48 = OpTypePointer Function %47
408 %4 = OpFunction %2 None %3
409 %5 = OpLabel
410 %103 = OpFunctionCall %2 %6
411 %104 = OpFunctionCall %2 %8
412 OpReturn
413 OpFunctionEnd
414 %6 = OpFunction %2 None %3
415 %7 = OpLabel
416 %12 = OpVariable %11 Function
417 %14 = OpVariable %11 Function
418 %29 = OpVariable %28 Function
419 %38 = OpVariable %37 Function
420 %49 = OpVariable %48 Function
421 %56 = OpVariable %48 Function
422 OpStore %12 %13
423 OpStore %14 %15
424 OpBranch %16
425 %16 = OpLabel
426 %105 = OpPhi %10 %15 %7 %64 %19
427 OpLoopMerge %18 %19 None
428 OpBranch %20
429 %20 = OpLabel
430 %24 = OpSLessThan %23 %105 %22
431 OpBranchConditional %24 %17 %18
432 %17 = OpLabel
433 %32 = OpAccessChain %11 %29 %105
434 %33 = OpLoad %10 %32
435 %34 = OpAccessChain %11 %29 %105
436 OpStore %34 %33
437 %42 = OpIAdd %10 %105 %41
438 %43 = OpAccessChain %11 %38 %42
439 %44 = OpLoad %10 %43
440 %45 = OpAccessChain %11 %38 %105
441 OpStore %45 %44
442 %52 = OpISub %10 %105 %41
443 %53 = OpAccessChain %11 %49 %52
444 %54 = OpLoad %10 %53
445 %55 = OpAccessChain %11 %49 %105
446 OpStore %55 %54
447 %58 = OpIMul %10 %13 %105
448 %60 = OpAccessChain %11 %56 %105
449 %61 = OpLoad %10 %60
450 %62 = OpAccessChain %11 %56 %58
451 OpStore %62 %61
452 OpBranch %19
453 %19 = OpLabel
454 %64 = OpIAdd %10 %105 %41
455 OpStore %14 %64
456 OpBranch %16
457 %18 = OpLabel
458 OpReturn
459 OpFunctionEnd
460 %8 = OpFunction %2 None %3
461 %9 = OpLabel
462 %65 = OpVariable %11 Function
463 %66 = OpVariable %11 Function
464 %74 = OpVariable %28 Function
465 %80 = OpVariable %37 Function
466 %87 = OpVariable %48 Function
467 %94 = OpVariable %48 Function
468 OpStore %65 %13
469 OpStore %66 %22
470 OpBranch %67
471 %67 = OpLabel
472 %106 = OpPhi %10 %22 %9 %102 %70
473 OpLoopMerge %69 %70 None
474 OpBranch %71
475 %71 = OpLabel
476 %73 = OpSGreaterThan %23 %106 %15
477 OpBranchConditional %73 %68 %69
478 %68 = OpLabel
479 %77 = OpAccessChain %11 %74 %106
480 %78 = OpLoad %10 %77
481 %79 = OpAccessChain %11 %74 %106
482 OpStore %79 %78
483 %83 = OpIAdd %10 %106 %41
484 %84 = OpAccessChain %11 %80 %83
485 %85 = OpLoad %10 %84
486 %86 = OpAccessChain %11 %80 %106
487 OpStore %86 %85
488 %90 = OpISub %10 %106 %41
489 %91 = OpAccessChain %11 %87 %90
490 %92 = OpLoad %10 %91
491 %93 = OpAccessChain %11 %87 %106
492 OpStore %93 %92
493 %96 = OpIMul %10 %13 %106
494 %98 = OpAccessChain %11 %94 %106
495 %99 = OpLoad %10 %98
496 %100 = OpAccessChain %11 %94 %96
497 OpStore %100 %99
498 OpBranch %70
499 %70 = OpLabel
500 %102 = OpISub %10 %106 %41
501 OpStore %66 %102
502 OpBranch %67
503 %69 = OpLabel
504 OpReturn
505 OpFunctionEnd
506 )";
507 std::unique_ptr<IRContext> context =
508 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
509 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
510 Module* module = context->module();
511 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
512 << text << std::endl;
513 // For the loop in function a.
514 {
515 const Function* f = spvtest::GetFunction(module, 6);
516 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
517
518 Loop* loop = &ld.GetLoopByIndex(0);
519 std::vector<const Loop*> loops{loop};
520 LoopDependenceAnalysis analysis{context.get(), loops};
521
522 const Instruction* store[4];
523 int stores_found = 0;
524 for (const Instruction& inst : *spvtest::GetBasicBlock(f, 17)) {
525 if (inst.opcode() == spv::Op::OpStore) {
526 store[stores_found] = &inst;
527 ++stores_found;
528 }
529 }
530
531 for (int i = 0; i < 4; ++i) {
532 EXPECT_TRUE(store[i]);
533 }
534
535 // = dependence
536 // 33 -> 34 tests looking at SIV in same array.
537 {
538 DistanceVector distance_vector{loops.size()};
539 EXPECT_FALSE(analysis.GetDependence(
540 context->get_def_use_mgr()->GetDef(33), store[0], &distance_vector));
541 EXPECT_EQ(distance_vector.GetEntries()[0].dependence_information,
542 DistanceEntry::DependenceInformation::DISTANCE);
543 EXPECT_EQ(distance_vector.GetEntries()[0].direction,
544 DistanceEntry::Directions::EQ);
545 EXPECT_EQ(distance_vector.GetEntries()[0].distance, 0);
546 }
547
548 // > -1 dependence
549 // 44 -> 45 tests looking at SIV in same array with addition.
550 {
551 DistanceVector distance_vector{loops.size()};
552 EXPECT_FALSE(analysis.GetDependence(
553 context->get_def_use_mgr()->GetDef(44), store[1], &distance_vector));
554 EXPECT_EQ(distance_vector.GetEntries()[0].dependence_information,
555 DistanceEntry::DependenceInformation::DISTANCE);
556 EXPECT_EQ(distance_vector.GetEntries()[0].direction,
557 DistanceEntry::Directions::GT);
558 EXPECT_EQ(distance_vector.GetEntries()[0].distance, -1);
559 }
560
561 // < 1 dependence
562 // 54 -> 55 tests looking at SIV in same array with subtraction.
563 {
564 DistanceVector distance_vector{loops.size()};
565 EXPECT_FALSE(analysis.GetDependence(
566 context->get_def_use_mgr()->GetDef(54), store[2], &distance_vector));
567 EXPECT_EQ(distance_vector.GetEntries()[0].dependence_information,
568 DistanceEntry::DependenceInformation::DISTANCE);
569 EXPECT_EQ(distance_vector.GetEntries()[0].direction,
570 DistanceEntry::Directions::LT);
571 EXPECT_EQ(distance_vector.GetEntries()[0].distance, 1);
572 }
573
574 // <=> dependence
575 // 61 -> 62 tests looking at SIV in same array with multiplication.
576 {
577 DistanceVector distance_vector{loops.size()};
578 EXPECT_FALSE(analysis.GetDependence(
579 context->get_def_use_mgr()->GetDef(61), store[3], &distance_vector));
580 EXPECT_EQ(distance_vector.GetEntries()[0].dependence_information,
581 DistanceEntry::DependenceInformation::UNKNOWN);
582 EXPECT_EQ(distance_vector.GetEntries()[0].direction,
583 DistanceEntry::Directions::ALL);
584 }
585 }
586 // For the loop in function b.
587 {
588 const Function* f = spvtest::GetFunction(module, 8);
589 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
590
591 Loop* loop = &ld.GetLoopByIndex(0);
592 std::vector<const Loop*> loops{loop};
593 LoopDependenceAnalysis analysis{context.get(), loops};
594
595 const Instruction* store[4];
596 int stores_found = 0;
597 for (const Instruction& inst : *spvtest::GetBasicBlock(f, 68)) {
598 if (inst.opcode() == spv::Op::OpStore) {
599 store[stores_found] = &inst;
600 ++stores_found;
601 }
602 }
603
604 for (int i = 0; i < 4; ++i) {
605 EXPECT_TRUE(store[i]);
606 }
607
608 // = dependence
609 // 78 -> 79 tests looking at SIV in same array.
610 {
611 DistanceVector distance_vector{loops.size()};
612 EXPECT_FALSE(analysis.GetDependence(
613 context->get_def_use_mgr()->GetDef(78), store[0], &distance_vector));
614 EXPECT_EQ(distance_vector.GetEntries()[0].dependence_information,
615 DistanceEntry::DependenceInformation::DISTANCE);
616 EXPECT_EQ(distance_vector.GetEntries()[0].direction,
617 DistanceEntry::Directions::EQ);
618 EXPECT_EQ(distance_vector.GetEntries()[0].distance, 0);
619 }
620
621 // < 1 dependence
622 // 85 -> 86 tests looking at SIV in same array with addition.
623 {
624 DistanceVector distance_vector{loops.size()};
625 EXPECT_FALSE(analysis.GetDependence(
626 context->get_def_use_mgr()->GetDef(85), store[1], &distance_vector));
627 EXPECT_EQ(distance_vector.GetEntries()[0].dependence_information,
628 DistanceEntry::DependenceInformation::DISTANCE);
629 EXPECT_EQ(distance_vector.GetEntries()[0].direction,
630 DistanceEntry::Directions::LT);
631 EXPECT_EQ(distance_vector.GetEntries()[0].distance, 1);
632 }
633
634 // > -1 dependence
635 // 92 -> 93 tests looking at SIV in same array with subtraction.
636 {
637 DistanceVector distance_vector{loops.size()};
638 EXPECT_FALSE(analysis.GetDependence(
639 context->get_def_use_mgr()->GetDef(92), store[2], &distance_vector));
640 EXPECT_EQ(distance_vector.GetEntries()[0].dependence_information,
641 DistanceEntry::DependenceInformation::DISTANCE);
642 EXPECT_EQ(distance_vector.GetEntries()[0].direction,
643 DistanceEntry::Directions::GT);
644 EXPECT_EQ(distance_vector.GetEntries()[0].distance, -1);
645 }
646
647 // <=> dependence
648 // 99 -> 100 tests looking at SIV in same array with multiplication.
649 {
650 DistanceVector distance_vector{loops.size()};
651 EXPECT_FALSE(analysis.GetDependence(
652 context->get_def_use_mgr()->GetDef(99), store[3], &distance_vector));
653 EXPECT_EQ(distance_vector.GetEntries()[0].dependence_information,
654 DistanceEntry::DependenceInformation::UNKNOWN);
655 EXPECT_EQ(distance_vector.GetEntries()[0].direction,
656 DistanceEntry::Directions::ALL);
657 }
658 }
659 }
660
661 /*
662 Generated from the following GLSL fragment shader
663 with --eliminate-local-multi-store
664 #version 440 core
665 layout(location = 0) in vec4 c;
666 void a() {
667 int[13] arr;
668 int[15] arr2;
669 int[18] arr3;
670 int[18] arr4;
671 int N = int(c.x);
672 int C = 2;
673 int a = 2;
674 for (int i = 0; i < N; i++) { // Bounds are N - 1
675 arr[i+2*N] = arr[i+N]; // |distance| = N
676 arr2[i+N] = arr2[i+2*N] + C; // |distance| = N
677 arr3[2*i+2*N+1] = arr3[2*i+N+1]; // |distance| = N
678 arr4[a*i+N+1] = arr4[a*i+2*N+1]; // |distance| = N
679 }
680 }
681 void b() {
682 int[13] arr;
683 int[15] arr2;
684 int[18] arr3;
685 int[18] arr4;
686 int N = int(c.x);
687 int C = 2;
688 int a = 2;
689 for (int i = N; i > 0; i--) { // Bounds are N - 1
690 arr[i+2*N] = arr[i+N]; // |distance| = N
691 arr2[i+N] = arr2[i+2*N] + C; // |distance| = N
692 arr3[2*i+2*N+1] = arr3[2*i+N+1]; // |distance| = N
693 arr4[a*i+N+1] = arr4[a*i+2*N+1]; // |distance| = N
694 }
695 }
696 void main(){
697 a();
698 b();
699 }*/
TEST(DependencyAnalysis,SymbolicSIV)700 TEST(DependencyAnalysis, SymbolicSIV) {
701 const std::string text = R"( OpCapability Shader
702 %1 = OpExtInstImport "GLSL.std.450"
703 OpMemoryModel Logical GLSL450
704 OpEntryPoint Fragment %4 "main" %16
705 OpExecutionMode %4 OriginUpperLeft
706 OpSource GLSL 440
707 OpName %4 "main"
708 OpName %6 "a("
709 OpName %8 "b("
710 OpName %12 "N"
711 OpName %16 "c"
712 OpName %23 "C"
713 OpName %25 "a"
714 OpName %26 "i"
715 OpName %40 "arr"
716 OpName %54 "arr2"
717 OpName %70 "arr3"
718 OpName %86 "arr4"
719 OpName %105 "N"
720 OpName %109 "C"
721 OpName %110 "a"
722 OpName %111 "i"
723 OpName %120 "arr"
724 OpName %131 "arr2"
725 OpName %144 "arr3"
726 OpName %159 "arr4"
727 OpDecorate %16 Location 0
728 %2 = OpTypeVoid
729 %3 = OpTypeFunction %2
730 %10 = OpTypeInt 32 1
731 %11 = OpTypePointer Function %10
732 %13 = OpTypeFloat 32
733 %14 = OpTypeVector %13 4
734 %15 = OpTypePointer Input %14
735 %16 = OpVariable %15 Input
736 %17 = OpTypeInt 32 0
737 %18 = OpConstant %17 0
738 %19 = OpTypePointer Input %13
739 %24 = OpConstant %10 2
740 %27 = OpConstant %10 0
741 %35 = OpTypeBool
742 %37 = OpConstant %17 13
743 %38 = OpTypeArray %10 %37
744 %39 = OpTypePointer Function %38
745 %51 = OpConstant %17 15
746 %52 = OpTypeArray %10 %51
747 %53 = OpTypePointer Function %52
748 %67 = OpConstant %17 18
749 %68 = OpTypeArray %10 %67
750 %69 = OpTypePointer Function %68
751 %76 = OpConstant %10 1
752 %4 = OpFunction %2 None %3
753 %5 = OpLabel
754 %178 = OpFunctionCall %2 %6
755 %179 = OpFunctionCall %2 %8
756 OpReturn
757 OpFunctionEnd
758 %6 = OpFunction %2 None %3
759 %7 = OpLabel
760 %12 = OpVariable %11 Function
761 %23 = OpVariable %11 Function
762 %25 = OpVariable %11 Function
763 %26 = OpVariable %11 Function
764 %40 = OpVariable %39 Function
765 %54 = OpVariable %53 Function
766 %70 = OpVariable %69 Function
767 %86 = OpVariable %69 Function
768 %20 = OpAccessChain %19 %16 %18
769 %21 = OpLoad %13 %20
770 %22 = OpConvertFToS %10 %21
771 OpStore %12 %22
772 OpStore %23 %24
773 OpStore %25 %24
774 OpStore %26 %27
775 OpBranch %28
776 %28 = OpLabel
777 %180 = OpPhi %10 %27 %7 %104 %31
778 OpLoopMerge %30 %31 None
779 OpBranch %32
780 %32 = OpLabel
781 %36 = OpSLessThan %35 %180 %22
782 OpBranchConditional %36 %29 %30
783 %29 = OpLabel
784 %43 = OpIMul %10 %24 %22
785 %44 = OpIAdd %10 %180 %43
786 %47 = OpIAdd %10 %180 %22
787 %48 = OpAccessChain %11 %40 %47
788 %49 = OpLoad %10 %48
789 %50 = OpAccessChain %11 %40 %44
790 OpStore %50 %49
791 %57 = OpIAdd %10 %180 %22
792 %60 = OpIMul %10 %24 %22
793 %61 = OpIAdd %10 %180 %60
794 %62 = OpAccessChain %11 %54 %61
795 %63 = OpLoad %10 %62
796 %65 = OpIAdd %10 %63 %24
797 %66 = OpAccessChain %11 %54 %57
798 OpStore %66 %65
799 %72 = OpIMul %10 %24 %180
800 %74 = OpIMul %10 %24 %22
801 %75 = OpIAdd %10 %72 %74
802 %77 = OpIAdd %10 %75 %76
803 %79 = OpIMul %10 %24 %180
804 %81 = OpIAdd %10 %79 %22
805 %82 = OpIAdd %10 %81 %76
806 %83 = OpAccessChain %11 %70 %82
807 %84 = OpLoad %10 %83
808 %85 = OpAccessChain %11 %70 %77
809 OpStore %85 %84
810 %89 = OpIMul %10 %24 %180
811 %91 = OpIAdd %10 %89 %22
812 %92 = OpIAdd %10 %91 %76
813 %95 = OpIMul %10 %24 %180
814 %97 = OpIMul %10 %24 %22
815 %98 = OpIAdd %10 %95 %97
816 %99 = OpIAdd %10 %98 %76
817 %100 = OpAccessChain %11 %86 %99
818 %101 = OpLoad %10 %100
819 %102 = OpAccessChain %11 %86 %92
820 OpStore %102 %101
821 OpBranch %31
822 %31 = OpLabel
823 %104 = OpIAdd %10 %180 %76
824 OpStore %26 %104
825 OpBranch %28
826 %30 = OpLabel
827 OpReturn
828 OpFunctionEnd
829 %8 = OpFunction %2 None %3
830 %9 = OpLabel
831 %105 = OpVariable %11 Function
832 %109 = OpVariable %11 Function
833 %110 = OpVariable %11 Function
834 %111 = OpVariable %11 Function
835 %120 = OpVariable %39 Function
836 %131 = OpVariable %53 Function
837 %144 = OpVariable %69 Function
838 %159 = OpVariable %69 Function
839 %106 = OpAccessChain %19 %16 %18
840 %107 = OpLoad %13 %106
841 %108 = OpConvertFToS %10 %107
842 OpStore %105 %108
843 OpStore %109 %24
844 OpStore %110 %24
845 OpStore %111 %108
846 OpBranch %113
847 %113 = OpLabel
848 %181 = OpPhi %10 %108 %9 %177 %116
849 OpLoopMerge %115 %116 None
850 OpBranch %117
851 %117 = OpLabel
852 %119 = OpSGreaterThan %35 %181 %27
853 OpBranchConditional %119 %114 %115
854 %114 = OpLabel
855 %123 = OpIMul %10 %24 %108
856 %124 = OpIAdd %10 %181 %123
857 %127 = OpIAdd %10 %181 %108
858 %128 = OpAccessChain %11 %120 %127
859 %129 = OpLoad %10 %128
860 %130 = OpAccessChain %11 %120 %124
861 OpStore %130 %129
862 %134 = OpIAdd %10 %181 %108
863 %137 = OpIMul %10 %24 %108
864 %138 = OpIAdd %10 %181 %137
865 %139 = OpAccessChain %11 %131 %138
866 %140 = OpLoad %10 %139
867 %142 = OpIAdd %10 %140 %24
868 %143 = OpAccessChain %11 %131 %134
869 OpStore %143 %142
870 %146 = OpIMul %10 %24 %181
871 %148 = OpIMul %10 %24 %108
872 %149 = OpIAdd %10 %146 %148
873 %150 = OpIAdd %10 %149 %76
874 %152 = OpIMul %10 %24 %181
875 %154 = OpIAdd %10 %152 %108
876 %155 = OpIAdd %10 %154 %76
877 %156 = OpAccessChain %11 %144 %155
878 %157 = OpLoad %10 %156
879 %158 = OpAccessChain %11 %144 %150
880 OpStore %158 %157
881 %162 = OpIMul %10 %24 %181
882 %164 = OpIAdd %10 %162 %108
883 %165 = OpIAdd %10 %164 %76
884 %168 = OpIMul %10 %24 %181
885 %170 = OpIMul %10 %24 %108
886 %171 = OpIAdd %10 %168 %170
887 %172 = OpIAdd %10 %171 %76
888 %173 = OpAccessChain %11 %159 %172
889 %174 = OpLoad %10 %173
890 %175 = OpAccessChain %11 %159 %165
891 OpStore %175 %174
892 OpBranch %116
893 %116 = OpLabel
894 %177 = OpISub %10 %181 %76
895 OpStore %111 %177
896 OpBranch %113
897 %115 = OpLabel
898 OpReturn
899 OpFunctionEnd
900 )";
901 std::unique_ptr<IRContext> context =
902 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
903 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
904 Module* module = context->module();
905 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
906 << text << std::endl;
907 // For the loop in function a.
908 {
909 const Function* f = spvtest::GetFunction(module, 6);
910 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
911
912 Loop* loop = &ld.GetLoopByIndex(0);
913 std::vector<const Loop*> loops{loop};
914 LoopDependenceAnalysis analysis{context.get(), loops};
915
916 const Instruction* store[4];
917 int stores_found = 0;
918 for (const Instruction& inst : *spvtest::GetBasicBlock(f, 29)) {
919 if (inst.opcode() == spv::Op::OpStore) {
920 store[stores_found] = &inst;
921 ++stores_found;
922 }
923 }
924
925 for (int i = 0; i < 4; ++i) {
926 EXPECT_TRUE(store[i]);
927 }
928
929 // independent due to loop bounds (won't enter when N <= 0)
930 // 49 -> 50 tests looking through SIV and symbols with multiplication
931 {
932 DistanceVector distance_vector{loops.size()};
933 // Independent but not yet supported.
934 EXPECT_FALSE(analysis.GetDependence(
935 context->get_def_use_mgr()->GetDef(49), store[0], &distance_vector));
936 }
937
938 // 63 -> 66 tests looking through SIV and symbols with multiplication and +
939 // C
940 {
941 DistanceVector distance_vector{loops.size()};
942 // Independent.
943 EXPECT_TRUE(analysis.GetDependence(context->get_def_use_mgr()->GetDef(63),
944 store[1], &distance_vector));
945 }
946
947 // 84 -> 85 tests looking through arithmetic on SIV and symbols
948 {
949 DistanceVector distance_vector{loops.size()};
950 // Independent but not yet supported.
951 EXPECT_FALSE(analysis.GetDependence(
952 context->get_def_use_mgr()->GetDef(84), store[2], &distance_vector));
953 }
954
955 // 101 -> 102 tests looking through symbol arithmetic on SIV and symbols
956 {
957 DistanceVector distance_vector{loops.size()};
958 // Independent.
959 EXPECT_TRUE(analysis.GetDependence(
960 context->get_def_use_mgr()->GetDef(101), store[3], &distance_vector));
961 }
962 }
963 // For the loop in function b.
964 {
965 const Function* f = spvtest::GetFunction(module, 8);
966 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
967
968 Loop* loop = &ld.GetLoopByIndex(0);
969 std::vector<const Loop*> loops{loop};
970 LoopDependenceAnalysis analysis{context.get(), loops};
971
972 const Instruction* store[4];
973 int stores_found = 0;
974 for (const Instruction& inst : *spvtest::GetBasicBlock(f, 114)) {
975 if (inst.opcode() == spv::Op::OpStore) {
976 store[stores_found] = &inst;
977 ++stores_found;
978 }
979 }
980
981 for (int i = 0; i < 4; ++i) {
982 EXPECT_TRUE(store[i]);
983 }
984
985 // independent due to loop bounds (won't enter when N <= 0).
986 // 129 -> 130 tests looking through SIV and symbols with multiplication.
987 {
988 DistanceVector distance_vector{loops.size()};
989 // Independent but not yet supported.
990 EXPECT_FALSE(analysis.GetDependence(
991 context->get_def_use_mgr()->GetDef(129), store[0], &distance_vector));
992 }
993
994 // 140 -> 143 tests looking through SIV and symbols with multiplication and
995 // + C.
996 {
997 DistanceVector distance_vector{loops.size()};
998 // Independent.
999 EXPECT_TRUE(analysis.GetDependence(
1000 context->get_def_use_mgr()->GetDef(140), store[1], &distance_vector));
1001 }
1002
1003 // 157 -> 158 tests looking through arithmetic on SIV and symbols.
1004 {
1005 DistanceVector distance_vector{loops.size()};
1006 // Independent but not yet supported.
1007 EXPECT_FALSE(analysis.GetDependence(
1008 context->get_def_use_mgr()->GetDef(157), store[2], &distance_vector));
1009 }
1010
1011 // 174 -> 175 tests looking through symbol arithmetic on SIV and symbols.
1012 {
1013 DistanceVector distance_vector{loops.size()};
1014 // Independent.
1015 EXPECT_TRUE(analysis.GetDependence(
1016 context->get_def_use_mgr()->GetDef(174), store[3], &distance_vector));
1017 }
1018 }
1019 }
1020
1021 /*
1022 Generated from the following GLSL fragment shader
1023 with --eliminate-local-multi-store
1024 #version 440 core
1025 void a() {
1026 int[6] arr;
1027 int N = 5;
1028 for (int i = 1; i < N; i++) {
1029 arr[i] = arr[N-i];
1030 }
1031 }
1032 void b() {
1033 int[6] arr;
1034 int N = 5;
1035 for (int i = 1; i < N; i++) {
1036 arr[N-i] = arr[i];
1037 }
1038 }
1039 void c() {
1040 int[11] arr;
1041 int N = 10;
1042 for (int i = 1; i < N; i++) {
1043 arr[i] = arr[N-i+1];
1044 }
1045 }
1046 void d() {
1047 int[11] arr;
1048 int N = 10;
1049 for (int i = 1; i < N; i++) {
1050 arr[N-i+1] = arr[i];
1051 }
1052 }
1053 void e() {
1054 int[6] arr;
1055 int N = 5;
1056 for (int i = N; i > 0; i--) {
1057 arr[i] = arr[N-i];
1058 }
1059 }
1060 void f() {
1061 int[6] arr;
1062 int N = 5;
1063 for (int i = N; i > 0; i--) {
1064 arr[N-i] = arr[i];
1065 }
1066 }
1067 void g() {
1068 int[11] arr;
1069 int N = 10;
1070 for (int i = N; i > 0; i--) {
1071 arr[i] = arr[N-i+1];
1072 }
1073 }
1074 void h() {
1075 int[11] arr;
1076 int N = 10;
1077 for (int i = N; i > 0; i--) {
1078 arr[N-i+1] = arr[i];
1079 }
1080 }
1081 void main(){
1082 a();
1083 b();
1084 c();
1085 d();
1086 e();
1087 f();
1088 g();
1089 h();
1090 }
1091 */
TEST(DependencyAnalysis,Crossing)1092 TEST(DependencyAnalysis, Crossing) {
1093 const std::string text = R"( OpCapability Shader
1094 %1 = OpExtInstImport "GLSL.std.450"
1095 OpMemoryModel Logical GLSL450
1096 OpEntryPoint Fragment %4 "main"
1097 OpExecutionMode %4 OriginUpperLeft
1098 OpSource GLSL 440
1099 OpName %4 "main"
1100 OpName %6 "a("
1101 OpName %8 "b("
1102 OpName %10 "c("
1103 OpName %12 "d("
1104 OpName %14 "e("
1105 OpName %16 "f("
1106 OpName %18 "g("
1107 OpName %20 "h("
1108 OpName %24 "N"
1109 OpName %26 "i"
1110 OpName %41 "arr"
1111 OpName %51 "N"
1112 OpName %52 "i"
1113 OpName %61 "arr"
1114 OpName %71 "N"
1115 OpName %73 "i"
1116 OpName %85 "arr"
1117 OpName %96 "N"
1118 OpName %97 "i"
1119 OpName %106 "arr"
1120 OpName %117 "N"
1121 OpName %118 "i"
1122 OpName %128 "arr"
1123 OpName %138 "N"
1124 OpName %139 "i"
1125 OpName %148 "arr"
1126 OpName %158 "N"
1127 OpName %159 "i"
1128 OpName %168 "arr"
1129 OpName %179 "N"
1130 OpName %180 "i"
1131 OpName %189 "arr"
1132 %2 = OpTypeVoid
1133 %3 = OpTypeFunction %2
1134 %22 = OpTypeInt 32 1
1135 %23 = OpTypePointer Function %22
1136 %25 = OpConstant %22 5
1137 %27 = OpConstant %22 1
1138 %35 = OpTypeBool
1139 %37 = OpTypeInt 32 0
1140 %38 = OpConstant %37 6
1141 %39 = OpTypeArray %22 %38
1142 %40 = OpTypePointer Function %39
1143 %72 = OpConstant %22 10
1144 %82 = OpConstant %37 11
1145 %83 = OpTypeArray %22 %82
1146 %84 = OpTypePointer Function %83
1147 %126 = OpConstant %22 0
1148 %4 = OpFunction %2 None %3
1149 %5 = OpLabel
1150 %200 = OpFunctionCall %2 %6
1151 %201 = OpFunctionCall %2 %8
1152 %202 = OpFunctionCall %2 %10
1153 %203 = OpFunctionCall %2 %12
1154 %204 = OpFunctionCall %2 %14
1155 %205 = OpFunctionCall %2 %16
1156 %206 = OpFunctionCall %2 %18
1157 %207 = OpFunctionCall %2 %20
1158 OpReturn
1159 OpFunctionEnd
1160 %6 = OpFunction %2 None %3
1161 %7 = OpLabel
1162 %24 = OpVariable %23 Function
1163 %26 = OpVariable %23 Function
1164 %41 = OpVariable %40 Function
1165 OpStore %24 %25
1166 OpStore %26 %27
1167 OpBranch %28
1168 %28 = OpLabel
1169 %208 = OpPhi %22 %27 %7 %50 %31
1170 OpLoopMerge %30 %31 None
1171 OpBranch %32
1172 %32 = OpLabel
1173 %36 = OpSLessThan %35 %208 %25
1174 OpBranchConditional %36 %29 %30
1175 %29 = OpLabel
1176 %45 = OpISub %22 %25 %208
1177 %46 = OpAccessChain %23 %41 %45
1178 %47 = OpLoad %22 %46
1179 %48 = OpAccessChain %23 %41 %208
1180 OpStore %48 %47
1181 OpBranch %31
1182 %31 = OpLabel
1183 %50 = OpIAdd %22 %208 %27
1184 OpStore %26 %50
1185 OpBranch %28
1186 %30 = OpLabel
1187 OpReturn
1188 OpFunctionEnd
1189 %8 = OpFunction %2 None %3
1190 %9 = OpLabel
1191 %51 = OpVariable %23 Function
1192 %52 = OpVariable %23 Function
1193 %61 = OpVariable %40 Function
1194 OpStore %51 %25
1195 OpStore %52 %27
1196 OpBranch %53
1197 %53 = OpLabel
1198 %209 = OpPhi %22 %27 %9 %70 %56
1199 OpLoopMerge %55 %56 None
1200 OpBranch %57
1201 %57 = OpLabel
1202 %60 = OpSLessThan %35 %209 %25
1203 OpBranchConditional %60 %54 %55
1204 %54 = OpLabel
1205 %64 = OpISub %22 %25 %209
1206 %66 = OpAccessChain %23 %61 %209
1207 %67 = OpLoad %22 %66
1208 %68 = OpAccessChain %23 %61 %64
1209 OpStore %68 %67
1210 OpBranch %56
1211 %56 = OpLabel
1212 %70 = OpIAdd %22 %209 %27
1213 OpStore %52 %70
1214 OpBranch %53
1215 %55 = OpLabel
1216 OpReturn
1217 OpFunctionEnd
1218 %10 = OpFunction %2 None %3
1219 %11 = OpLabel
1220 %71 = OpVariable %23 Function
1221 %73 = OpVariable %23 Function
1222 %85 = OpVariable %84 Function
1223 OpStore %71 %72
1224 OpStore %73 %27
1225 OpBranch %74
1226 %74 = OpLabel
1227 %210 = OpPhi %22 %27 %11 %95 %77
1228 OpLoopMerge %76 %77 None
1229 OpBranch %78
1230 %78 = OpLabel
1231 %81 = OpSLessThan %35 %210 %72
1232 OpBranchConditional %81 %75 %76
1233 %75 = OpLabel
1234 %89 = OpISub %22 %72 %210
1235 %90 = OpIAdd %22 %89 %27
1236 %91 = OpAccessChain %23 %85 %90
1237 %92 = OpLoad %22 %91
1238 %93 = OpAccessChain %23 %85 %210
1239 OpStore %93 %92
1240 OpBranch %77
1241 %77 = OpLabel
1242 %95 = OpIAdd %22 %210 %27
1243 OpStore %73 %95
1244 OpBranch %74
1245 %76 = OpLabel
1246 OpReturn
1247 OpFunctionEnd
1248 %12 = OpFunction %2 None %3
1249 %13 = OpLabel
1250 %96 = OpVariable %23 Function
1251 %97 = OpVariable %23 Function
1252 %106 = OpVariable %84 Function
1253 OpStore %96 %72
1254 OpStore %97 %27
1255 OpBranch %98
1256 %98 = OpLabel
1257 %211 = OpPhi %22 %27 %13 %116 %101
1258 OpLoopMerge %100 %101 None
1259 OpBranch %102
1260 %102 = OpLabel
1261 %105 = OpSLessThan %35 %211 %72
1262 OpBranchConditional %105 %99 %100
1263 %99 = OpLabel
1264 %109 = OpISub %22 %72 %211
1265 %110 = OpIAdd %22 %109 %27
1266 %112 = OpAccessChain %23 %106 %211
1267 %113 = OpLoad %22 %112
1268 %114 = OpAccessChain %23 %106 %110
1269 OpStore %114 %113
1270 OpBranch %101
1271 %101 = OpLabel
1272 %116 = OpIAdd %22 %211 %27
1273 OpStore %97 %116
1274 OpBranch %98
1275 %100 = OpLabel
1276 OpReturn
1277 OpFunctionEnd
1278 %14 = OpFunction %2 None %3
1279 %15 = OpLabel
1280 %117 = OpVariable %23 Function
1281 %118 = OpVariable %23 Function
1282 %128 = OpVariable %40 Function
1283 OpStore %117 %25
1284 OpStore %118 %25
1285 OpBranch %120
1286 %120 = OpLabel
1287 %212 = OpPhi %22 %25 %15 %137 %123
1288 OpLoopMerge %122 %123 None
1289 OpBranch %124
1290 %124 = OpLabel
1291 %127 = OpSGreaterThan %35 %212 %126
1292 OpBranchConditional %127 %121 %122
1293 %121 = OpLabel
1294 %132 = OpISub %22 %25 %212
1295 %133 = OpAccessChain %23 %128 %132
1296 %134 = OpLoad %22 %133
1297 %135 = OpAccessChain %23 %128 %212
1298 OpStore %135 %134
1299 OpBranch %123
1300 %123 = OpLabel
1301 %137 = OpISub %22 %212 %27
1302 OpStore %118 %137
1303 OpBranch %120
1304 %122 = OpLabel
1305 OpReturn
1306 OpFunctionEnd
1307 %16 = OpFunction %2 None %3
1308 %17 = OpLabel
1309 %138 = OpVariable %23 Function
1310 %139 = OpVariable %23 Function
1311 %148 = OpVariable %40 Function
1312 OpStore %138 %25
1313 OpStore %139 %25
1314 OpBranch %141
1315 %141 = OpLabel
1316 %213 = OpPhi %22 %25 %17 %157 %144
1317 OpLoopMerge %143 %144 None
1318 OpBranch %145
1319 %145 = OpLabel
1320 %147 = OpSGreaterThan %35 %213 %126
1321 OpBranchConditional %147 %142 %143
1322 %142 = OpLabel
1323 %151 = OpISub %22 %25 %213
1324 %153 = OpAccessChain %23 %148 %213
1325 %154 = OpLoad %22 %153
1326 %155 = OpAccessChain %23 %148 %151
1327 OpStore %155 %154
1328 OpBranch %144
1329 %144 = OpLabel
1330 %157 = OpISub %22 %213 %27
1331 OpStore %139 %157
1332 OpBranch %141
1333 %143 = OpLabel
1334 OpReturn
1335 OpFunctionEnd
1336 %18 = OpFunction %2 None %3
1337 %19 = OpLabel
1338 %158 = OpVariable %23 Function
1339 %159 = OpVariable %23 Function
1340 %168 = OpVariable %84 Function
1341 OpStore %158 %72
1342 OpStore %159 %72
1343 OpBranch %161
1344 %161 = OpLabel
1345 %214 = OpPhi %22 %72 %19 %178 %164
1346 OpLoopMerge %163 %164 None
1347 OpBranch %165
1348 %165 = OpLabel
1349 %167 = OpSGreaterThan %35 %214 %126
1350 OpBranchConditional %167 %162 %163
1351 %162 = OpLabel
1352 %172 = OpISub %22 %72 %214
1353 %173 = OpIAdd %22 %172 %27
1354 %174 = OpAccessChain %23 %168 %173
1355 %175 = OpLoad %22 %174
1356 %176 = OpAccessChain %23 %168 %214
1357 OpStore %176 %175
1358 OpBranch %164
1359 %164 = OpLabel
1360 %178 = OpISub %22 %214 %27
1361 OpStore %159 %178
1362 OpBranch %161
1363 %163 = OpLabel
1364 OpReturn
1365 OpFunctionEnd
1366 %20 = OpFunction %2 None %3
1367 %21 = OpLabel
1368 %179 = OpVariable %23 Function
1369 %180 = OpVariable %23 Function
1370 %189 = OpVariable %84 Function
1371 OpStore %179 %72
1372 OpStore %180 %72
1373 OpBranch %182
1374 %182 = OpLabel
1375 %215 = OpPhi %22 %72 %21 %199 %185
1376 OpLoopMerge %184 %185 None
1377 OpBranch %186
1378 %186 = OpLabel
1379 %188 = OpSGreaterThan %35 %215 %126
1380 OpBranchConditional %188 %183 %184
1381 %183 = OpLabel
1382 %192 = OpISub %22 %72 %215
1383 %193 = OpIAdd %22 %192 %27
1384 %195 = OpAccessChain %23 %189 %215
1385 %196 = OpLoad %22 %195
1386 %197 = OpAccessChain %23 %189 %193
1387 OpStore %197 %196
1388 OpBranch %185
1389 %185 = OpLabel
1390 %199 = OpISub %22 %215 %27
1391 OpStore %180 %199
1392 OpBranch %182
1393 %184 = OpLabel
1394 OpReturn
1395 OpFunctionEnd
1396 )";
1397 std::unique_ptr<IRContext> context =
1398 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
1399 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
1400 Module* module = context->module();
1401 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
1402 << text << std::endl;
1403
1404 // First two tests can be split into two loops.
1405 // Tests even crossing subscripts from low to high indexes.
1406 // 47 -> 48
1407 {
1408 const Function* f = spvtest::GetFunction(module, 6);
1409 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
1410
1411 Loop* loop = &ld.GetLoopByIndex(0);
1412 std::vector<const Loop*> loops{loop};
1413 LoopDependenceAnalysis analysis{context.get(), loops};
1414
1415 const Instruction* store = nullptr;
1416 for (const Instruction& inst : *spvtest::GetBasicBlock(f, 29)) {
1417 if (inst.opcode() == spv::Op::OpStore) {
1418 store = &inst;
1419 }
1420 }
1421 DistanceVector distance_vector{loops.size()};
1422 EXPECT_FALSE(analysis.GetDependence(context->get_def_use_mgr()->GetDef(47),
1423 store, &distance_vector));
1424 }
1425
1426 // Tests even crossing subscripts from high to low indexes.
1427 // 67 -> 68
1428 {
1429 const Function* f = spvtest::GetFunction(module, 8);
1430 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
1431
1432 Loop* loop = &ld.GetLoopByIndex(0);
1433 std::vector<const Loop*> loops{loop};
1434 LoopDependenceAnalysis analysis{context.get(), loops};
1435
1436 const Instruction* store = nullptr;
1437 for (const Instruction& inst : *spvtest::GetBasicBlock(f, 54)) {
1438 if (inst.opcode() == spv::Op::OpStore) {
1439 store = &inst;
1440 }
1441 }
1442 DistanceVector distance_vector{loops.size()};
1443 EXPECT_FALSE(analysis.GetDependence(context->get_def_use_mgr()->GetDef(67),
1444 store, &distance_vector));
1445 }
1446
1447 // Next two tests can have an end peeled, then be split.
1448 // Tests uneven crossing subscripts from low to high indexes.
1449 // 92 -> 93
1450 {
1451 const Function* f = spvtest::GetFunction(module, 10);
1452 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
1453
1454 Loop* loop = &ld.GetLoopByIndex(0);
1455 std::vector<const Loop*> loops{loop};
1456 LoopDependenceAnalysis analysis{context.get(), loops};
1457
1458 const Instruction* store = nullptr;
1459 for (const Instruction& inst : *spvtest::GetBasicBlock(f, 75)) {
1460 if (inst.opcode() == spv::Op::OpStore) {
1461 store = &inst;
1462 }
1463 }
1464 DistanceVector distance_vector{loops.size()};
1465 EXPECT_FALSE(analysis.GetDependence(context->get_def_use_mgr()->GetDef(92),
1466 store, &distance_vector));
1467 }
1468
1469 // Tests uneven crossing subscripts from high to low indexes.
1470 // 113 -> 114
1471 {
1472 const Function* f = spvtest::GetFunction(module, 12);
1473 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
1474
1475 Loop* loop = &ld.GetLoopByIndex(0);
1476 std::vector<const Loop*> loops{loop};
1477 LoopDependenceAnalysis analysis{context.get(), loops};
1478
1479 const Instruction* store = nullptr;
1480 for (const Instruction& inst : *spvtest::GetBasicBlock(f, 99)) {
1481 if (inst.opcode() == spv::Op::OpStore) {
1482 store = &inst;
1483 }
1484 }
1485 DistanceVector distance_vector{loops.size()};
1486 EXPECT_FALSE(analysis.GetDependence(context->get_def_use_mgr()->GetDef(113),
1487 store, &distance_vector));
1488 }
1489
1490 // First two tests can be split into two loops.
1491 // Tests even crossing subscripts from low to high indexes.
1492 // 134 -> 135
1493 {
1494 const Function* f = spvtest::GetFunction(module, 14);
1495 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
1496
1497 Loop* loop = &ld.GetLoopByIndex(0);
1498 std::vector<const Loop*> loops{loop};
1499 LoopDependenceAnalysis analysis{context.get(), loops};
1500
1501 const Instruction* store = nullptr;
1502 for (const Instruction& inst : *spvtest::GetBasicBlock(f, 121)) {
1503 if (inst.opcode() == spv::Op::OpStore) {
1504 store = &inst;
1505 }
1506 }
1507 DistanceVector distance_vector{loops.size()};
1508 EXPECT_FALSE(analysis.GetDependence(context->get_def_use_mgr()->GetDef(134),
1509 store, &distance_vector));
1510 }
1511
1512 // Tests even crossing subscripts from high to low indexes.
1513 // 154 -> 155
1514 {
1515 const Function* f = spvtest::GetFunction(module, 16);
1516 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
1517
1518 Loop* loop = &ld.GetLoopByIndex(0);
1519 std::vector<const Loop*> loops{loop};
1520 LoopDependenceAnalysis analysis{context.get(), loops};
1521
1522 const Instruction* store = nullptr;
1523 for (const Instruction& inst : *spvtest::GetBasicBlock(f, 142)) {
1524 if (inst.opcode() == spv::Op::OpStore) {
1525 store = &inst;
1526 }
1527 }
1528 DistanceVector distance_vector{loops.size()};
1529 EXPECT_FALSE(analysis.GetDependence(context->get_def_use_mgr()->GetDef(154),
1530 store, &distance_vector));
1531 }
1532
1533 // Next two tests can have an end peeled, then be split.
1534 // Tests uneven crossing subscripts from low to high indexes.
1535 // 175 -> 176
1536 {
1537 const Function* f = spvtest::GetFunction(module, 18);
1538 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
1539
1540 Loop* loop = &ld.GetLoopByIndex(0);
1541 std::vector<const Loop*> loops{loop};
1542 LoopDependenceAnalysis analysis{context.get(), loops};
1543
1544 const Instruction* store = nullptr;
1545 for (const Instruction& inst : *spvtest::GetBasicBlock(f, 162)) {
1546 if (inst.opcode() == spv::Op::OpStore) {
1547 store = &inst;
1548 }
1549 }
1550 DistanceVector distance_vector{loops.size()};
1551 EXPECT_FALSE(analysis.GetDependence(context->get_def_use_mgr()->GetDef(175),
1552 store, &distance_vector));
1553 }
1554
1555 // Tests uneven crossing subscripts from high to low indexes.
1556 // 196 -> 197
1557 {
1558 const Function* f = spvtest::GetFunction(module, 20);
1559 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
1560
1561 Loop* loop = &ld.GetLoopByIndex(0);
1562 std::vector<const Loop*> loops{loop};
1563 LoopDependenceAnalysis analysis{context.get(), loops};
1564
1565 const Instruction* store = nullptr;
1566 for (const Instruction& inst : *spvtest::GetBasicBlock(f, 183)) {
1567 if (inst.opcode() == spv::Op::OpStore) {
1568 store = &inst;
1569 }
1570 }
1571 DistanceVector distance_vector{loops.size()};
1572 EXPECT_FALSE(analysis.GetDependence(context->get_def_use_mgr()->GetDef(196),
1573 store, &distance_vector));
1574 }
1575 }
1576
1577 /*
1578 Generated from the following GLSL fragment shader
1579 with --eliminate-local-multi-store
1580 #version 440 core
1581 void a() {
1582 int[10] arr;
1583 for (int i = 0; i < 10; i++) {
1584 arr[0] = arr[i]; // peel first
1585 arr[i] = arr[0]; // peel first
1586 arr[9] = arr[i]; // peel last
1587 arr[i] = arr[9]; // peel last
1588 }
1589 }
1590 void b() {
1591 int[11] arr;
1592 for (int i = 0; i <= 10; i++) {
1593 arr[0] = arr[i]; // peel first
1594 arr[i] = arr[0]; // peel first
1595 arr[10] = arr[i]; // peel last
1596 arr[i] = arr[10]; // peel last
1597
1598 }
1599 }
1600 void c() {
1601 int[11] arr;
1602 for (int i = 10; i > 0; i--) {
1603 arr[10] = arr[i]; // peel first
1604 arr[i] = arr[10]; // peel first
1605 arr[1] = arr[i]; // peel last
1606 arr[i] = arr[1]; // peel last
1607
1608 }
1609 }
1610 void d() {
1611 int[11] arr;
1612 for (int i = 10; i >= 0; i--) {
1613 arr[10] = arr[i]; // peel first
1614 arr[i] = arr[10]; // peel first
1615 arr[0] = arr[i]; // peel last
1616 arr[i] = arr[0]; // peel last
1617
1618 }
1619 }
1620 void main(){
1621 a();
1622 b();
1623 c();
1624 d();
1625 }
1626 */
TEST(DependencyAnalysis,WeakZeroSIV)1627 TEST(DependencyAnalysis, WeakZeroSIV) {
1628 const std::string text = R"( OpCapability Shader
1629 %1 = OpExtInstImport "GLSL.std.450"
1630 OpMemoryModel Logical GLSL450
1631 OpEntryPoint Fragment %4 "main"
1632 OpExecutionMode %4 OriginUpperLeft
1633 OpSource GLSL 440
1634 OpName %4 "main"
1635 OpName %6 "a("
1636 OpName %8 "b("
1637 OpName %10 "c("
1638 OpName %12 "d("
1639 OpName %16 "i"
1640 OpName %31 "arr"
1641 OpName %52 "i"
1642 OpName %63 "arr"
1643 OpName %82 "i"
1644 OpName %90 "arr"
1645 OpName %109 "i"
1646 OpName %117 "arr"
1647 %2 = OpTypeVoid
1648 %3 = OpTypeFunction %2
1649 %14 = OpTypeInt 32 1
1650 %15 = OpTypePointer Function %14
1651 %17 = OpConstant %14 0
1652 %24 = OpConstant %14 10
1653 %25 = OpTypeBool
1654 %27 = OpTypeInt 32 0
1655 %28 = OpConstant %27 10
1656 %29 = OpTypeArray %14 %28
1657 %30 = OpTypePointer Function %29
1658 %40 = OpConstant %14 9
1659 %50 = OpConstant %14 1
1660 %60 = OpConstant %27 11
1661 %61 = OpTypeArray %14 %60
1662 %62 = OpTypePointer Function %61
1663 %4 = OpFunction %2 None %3
1664 %5 = OpLabel
1665 %136 = OpFunctionCall %2 %6
1666 %137 = OpFunctionCall %2 %8
1667 %138 = OpFunctionCall %2 %10
1668 %139 = OpFunctionCall %2 %12
1669 OpReturn
1670 OpFunctionEnd
1671 %6 = OpFunction %2 None %3
1672 %7 = OpLabel
1673 %16 = OpVariable %15 Function
1674 %31 = OpVariable %30 Function
1675 OpStore %16 %17
1676 OpBranch %18
1677 %18 = OpLabel
1678 %140 = OpPhi %14 %17 %7 %51 %21
1679 OpLoopMerge %20 %21 None
1680 OpBranch %22
1681 %22 = OpLabel
1682 %26 = OpSLessThan %25 %140 %24
1683 OpBranchConditional %26 %19 %20
1684 %19 = OpLabel
1685 %33 = OpAccessChain %15 %31 %140
1686 %34 = OpLoad %14 %33
1687 %35 = OpAccessChain %15 %31 %17
1688 OpStore %35 %34
1689 %37 = OpAccessChain %15 %31 %17
1690 %38 = OpLoad %14 %37
1691 %39 = OpAccessChain %15 %31 %140
1692 OpStore %39 %38
1693 %42 = OpAccessChain %15 %31 %140
1694 %43 = OpLoad %14 %42
1695 %44 = OpAccessChain %15 %31 %40
1696 OpStore %44 %43
1697 %46 = OpAccessChain %15 %31 %40
1698 %47 = OpLoad %14 %46
1699 %48 = OpAccessChain %15 %31 %140
1700 OpStore %48 %47
1701 OpBranch %21
1702 %21 = OpLabel
1703 %51 = OpIAdd %14 %140 %50
1704 OpStore %16 %51
1705 OpBranch %18
1706 %20 = OpLabel
1707 OpReturn
1708 OpFunctionEnd
1709 %8 = OpFunction %2 None %3
1710 %9 = OpLabel
1711 %52 = OpVariable %15 Function
1712 %63 = OpVariable %62 Function
1713 OpStore %52 %17
1714 OpBranch %53
1715 %53 = OpLabel
1716 %141 = OpPhi %14 %17 %9 %81 %56
1717 OpLoopMerge %55 %56 None
1718 OpBranch %57
1719 %57 = OpLabel
1720 %59 = OpSLessThanEqual %25 %141 %24
1721 OpBranchConditional %59 %54 %55
1722 %54 = OpLabel
1723 %65 = OpAccessChain %15 %63 %141
1724 %66 = OpLoad %14 %65
1725 %67 = OpAccessChain %15 %63 %17
1726 OpStore %67 %66
1727 %69 = OpAccessChain %15 %63 %17
1728 %70 = OpLoad %14 %69
1729 %71 = OpAccessChain %15 %63 %141
1730 OpStore %71 %70
1731 %73 = OpAccessChain %15 %63 %141
1732 %74 = OpLoad %14 %73
1733 %75 = OpAccessChain %15 %63 %24
1734 OpStore %75 %74
1735 %77 = OpAccessChain %15 %63 %24
1736 %78 = OpLoad %14 %77
1737 %79 = OpAccessChain %15 %63 %141
1738 OpStore %79 %78
1739 OpBranch %56
1740 %56 = OpLabel
1741 %81 = OpIAdd %14 %141 %50
1742 OpStore %52 %81
1743 OpBranch %53
1744 %55 = OpLabel
1745 OpReturn
1746 OpFunctionEnd
1747 %10 = OpFunction %2 None %3
1748 %11 = OpLabel
1749 %82 = OpVariable %15 Function
1750 %90 = OpVariable %62 Function
1751 OpStore %82 %24
1752 OpBranch %83
1753 %83 = OpLabel
1754 %142 = OpPhi %14 %24 %11 %108 %86
1755 OpLoopMerge %85 %86 None
1756 OpBranch %87
1757 %87 = OpLabel
1758 %89 = OpSGreaterThan %25 %142 %17
1759 OpBranchConditional %89 %84 %85
1760 %84 = OpLabel
1761 %92 = OpAccessChain %15 %90 %142
1762 %93 = OpLoad %14 %92
1763 %94 = OpAccessChain %15 %90 %24
1764 OpStore %94 %93
1765 %96 = OpAccessChain %15 %90 %24
1766 %97 = OpLoad %14 %96
1767 %98 = OpAccessChain %15 %90 %142
1768 OpStore %98 %97
1769 %100 = OpAccessChain %15 %90 %142
1770 %101 = OpLoad %14 %100
1771 %102 = OpAccessChain %15 %90 %50
1772 OpStore %102 %101
1773 %104 = OpAccessChain %15 %90 %50
1774 %105 = OpLoad %14 %104
1775 %106 = OpAccessChain %15 %90 %142
1776 OpStore %106 %105
1777 OpBranch %86
1778 %86 = OpLabel
1779 %108 = OpISub %14 %142 %50
1780 OpStore %82 %108
1781 OpBranch %83
1782 %85 = OpLabel
1783 OpReturn
1784 OpFunctionEnd
1785 %12 = OpFunction %2 None %3
1786 %13 = OpLabel
1787 %109 = OpVariable %15 Function
1788 %117 = OpVariable %62 Function
1789 OpStore %109 %24
1790 OpBranch %110
1791 %110 = OpLabel
1792 %143 = OpPhi %14 %24 %13 %135 %113
1793 OpLoopMerge %112 %113 None
1794 OpBranch %114
1795 %114 = OpLabel
1796 %116 = OpSGreaterThanEqual %25 %143 %17
1797 OpBranchConditional %116 %111 %112
1798 %111 = OpLabel
1799 %119 = OpAccessChain %15 %117 %143
1800 %120 = OpLoad %14 %119
1801 %121 = OpAccessChain %15 %117 %24
1802 OpStore %121 %120
1803 %123 = OpAccessChain %15 %117 %24
1804 %124 = OpLoad %14 %123
1805 %125 = OpAccessChain %15 %117 %143
1806 OpStore %125 %124
1807 %127 = OpAccessChain %15 %117 %143
1808 %128 = OpLoad %14 %127
1809 %129 = OpAccessChain %15 %117 %17
1810 OpStore %129 %128
1811 %131 = OpAccessChain %15 %117 %17
1812 %132 = OpLoad %14 %131
1813 %133 = OpAccessChain %15 %117 %143
1814 OpStore %133 %132
1815 OpBranch %113
1816 %113 = OpLabel
1817 %135 = OpISub %14 %143 %50
1818 OpStore %109 %135
1819 OpBranch %110
1820 %112 = OpLabel
1821 OpReturn
1822 OpFunctionEnd
1823 )";
1824
1825 std::unique_ptr<IRContext> context =
1826 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
1827 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
1828 Module* module = context->module();
1829 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
1830 << text << std::endl;
1831 // For the loop in function a
1832 {
1833 const Function* f = spvtest::GetFunction(module, 6);
1834 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
1835
1836 Loop* loop = &ld.GetLoopByIndex(0);
1837 std::vector<const Loop*> loops{loop};
1838 LoopDependenceAnalysis analysis{context.get(), loops};
1839
1840 const Instruction* store[4];
1841 int stores_found = 0;
1842 for (const Instruction& inst : *spvtest::GetBasicBlock(f, 19)) {
1843 if (inst.opcode() == spv::Op::OpStore) {
1844 store[stores_found] = &inst;
1845 ++stores_found;
1846 }
1847 }
1848
1849 for (int i = 0; i < 4; ++i) {
1850 EXPECT_TRUE(store[i]);
1851 }
1852
1853 // Tests identifying peel first with weak zero with destination as zero
1854 // index.
1855 // 34 -> 35
1856 {
1857 DistanceVector distance_vector{loops.size()};
1858 EXPECT_FALSE(analysis.GetDependence(
1859 context->get_def_use_mgr()->GetDef(34), store[0], &distance_vector));
1860 EXPECT_EQ(distance_vector.GetEntries()[0].dependence_information,
1861 DistanceEntry::DependenceInformation::PEEL);
1862 EXPECT_TRUE(distance_vector.GetEntries()[0].peel_first);
1863 }
1864
1865 // Tests identifying peel first with weak zero with source as zero index.
1866 // 38 -> 39
1867 {
1868 DistanceVector distance_vector{loops.size()};
1869 EXPECT_FALSE(analysis.GetDependence(
1870 context->get_def_use_mgr()->GetDef(38), store[1], &distance_vector));
1871 EXPECT_EQ(distance_vector.GetEntries()[0].dependence_information,
1872 DistanceEntry::DependenceInformation::PEEL);
1873 EXPECT_TRUE(distance_vector.GetEntries()[0].peel_first);
1874 }
1875
1876 // Tests identifying peel first with weak zero with destination as zero
1877 // index.
1878 // 43 -> 44
1879 {
1880 DistanceVector distance_vector{loops.size()};
1881 EXPECT_FALSE(analysis.GetDependence(
1882 context->get_def_use_mgr()->GetDef(43), store[2], &distance_vector));
1883 EXPECT_EQ(distance_vector.GetEntries()[0].dependence_information,
1884 DistanceEntry::DependenceInformation::PEEL);
1885 EXPECT_TRUE(distance_vector.GetEntries()[0].peel_last);
1886 }
1887
1888 // Tests identifying peel first with weak zero with source as zero index.
1889 // 47 -> 48
1890 {
1891 DistanceVector distance_vector{loops.size()};
1892 EXPECT_FALSE(analysis.GetDependence(
1893 context->get_def_use_mgr()->GetDef(47), store[3], &distance_vector));
1894 EXPECT_EQ(distance_vector.GetEntries()[0].dependence_information,
1895 DistanceEntry::DependenceInformation::PEEL);
1896 EXPECT_TRUE(distance_vector.GetEntries()[0].peel_last);
1897 }
1898 }
1899 // For the loop in function b
1900 {
1901 const Function* f = spvtest::GetFunction(module, 8);
1902 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
1903
1904 Loop* loop = &ld.GetLoopByIndex(0);
1905 std::vector<const Loop*> loops{loop};
1906 LoopDependenceAnalysis analysis{context.get(), loops};
1907
1908 const Instruction* store[4];
1909 int stores_found = 0;
1910 for (const Instruction& inst : *spvtest::GetBasicBlock(f, 54)) {
1911 if (inst.opcode() == spv::Op::OpStore) {
1912 store[stores_found] = &inst;
1913 ++stores_found;
1914 }
1915 }
1916
1917 for (int i = 0; i < 4; ++i) {
1918 EXPECT_TRUE(store[i]);
1919 }
1920
1921 // Tests identifying peel first with weak zero with destination as zero
1922 // index.
1923 // 66 -> 67
1924 {
1925 DistanceVector distance_vector{loops.size()};
1926 EXPECT_FALSE(analysis.GetDependence(
1927 context->get_def_use_mgr()->GetDef(66), store[0], &distance_vector));
1928 EXPECT_EQ(distance_vector.GetEntries()[0].dependence_information,
1929 DistanceEntry::DependenceInformation::PEEL);
1930 EXPECT_TRUE(distance_vector.GetEntries()[0].peel_first);
1931 }
1932
1933 // Tests identifying peel first with weak zero with source as zero index.
1934 // 70 -> 71
1935 {
1936 DistanceVector distance_vector{loops.size()};
1937 EXPECT_FALSE(analysis.GetDependence(
1938 context->get_def_use_mgr()->GetDef(70), store[1], &distance_vector));
1939 EXPECT_EQ(distance_vector.GetEntries()[0].dependence_information,
1940 DistanceEntry::DependenceInformation::PEEL);
1941 EXPECT_TRUE(distance_vector.GetEntries()[0].peel_first);
1942 }
1943
1944 // Tests identifying peel first with weak zero with destination as zero
1945 // index.
1946 // 74 -> 75
1947 {
1948 DistanceVector distance_vector{loops.size()};
1949 EXPECT_FALSE(analysis.GetDependence(
1950 context->get_def_use_mgr()->GetDef(74), store[2], &distance_vector));
1951 EXPECT_EQ(distance_vector.GetEntries()[0].dependence_information,
1952 DistanceEntry::DependenceInformation::PEEL);
1953 EXPECT_TRUE(distance_vector.GetEntries()[0].peel_last);
1954 }
1955
1956 // Tests identifying peel first with weak zero with source as zero index.
1957 // 78 -> 79
1958 {
1959 DistanceVector distance_vector{loops.size()};
1960 EXPECT_FALSE(analysis.GetDependence(
1961 context->get_def_use_mgr()->GetDef(78), store[3], &distance_vector));
1962 EXPECT_EQ(distance_vector.GetEntries()[0].dependence_information,
1963 DistanceEntry::DependenceInformation::PEEL);
1964 EXPECT_TRUE(distance_vector.GetEntries()[0].peel_last);
1965 }
1966 }
1967 // For the loop in function c
1968 {
1969 const Function* f = spvtest::GetFunction(module, 10);
1970 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
1971
1972 Loop* loop = &ld.GetLoopByIndex(0);
1973 std::vector<const Loop*> loops{loop};
1974 LoopDependenceAnalysis analysis{context.get(), loops};
1975 const Instruction* store[4];
1976 int stores_found = 0;
1977 for (const Instruction& inst : *spvtest::GetBasicBlock(f, 84)) {
1978 if (inst.opcode() == spv::Op::OpStore) {
1979 store[stores_found] = &inst;
1980 ++stores_found;
1981 }
1982 }
1983
1984 for (int i = 0; i < 4; ++i) {
1985 EXPECT_TRUE(store[i]);
1986 }
1987
1988 // Tests identifying peel first with weak zero with destination as zero
1989 // index.
1990 // 93 -> 94
1991 {
1992 DistanceVector distance_vector{loops.size()};
1993 EXPECT_FALSE(analysis.GetDependence(
1994 context->get_def_use_mgr()->GetDef(93), store[0], &distance_vector));
1995 EXPECT_EQ(distance_vector.GetEntries()[0].dependence_information,
1996 DistanceEntry::DependenceInformation::PEEL);
1997 EXPECT_TRUE(distance_vector.GetEntries()[0].peel_first);
1998 }
1999
2000 // Tests identifying peel first with weak zero with source as zero index.
2001 // 97 -> 98
2002 {
2003 DistanceVector distance_vector{loops.size()};
2004 EXPECT_FALSE(analysis.GetDependence(
2005 context->get_def_use_mgr()->GetDef(97), store[1], &distance_vector));
2006 EXPECT_EQ(distance_vector.GetEntries()[0].dependence_information,
2007 DistanceEntry::DependenceInformation::PEEL);
2008 EXPECT_TRUE(distance_vector.GetEntries()[0].peel_first);
2009 }
2010
2011 // Tests identifying peel first with weak zero with destination as zero
2012 // index.
2013 // 101 -> 102
2014 {
2015 DistanceVector distance_vector{loops.size()};
2016 EXPECT_FALSE(analysis.GetDependence(
2017 context->get_def_use_mgr()->GetDef(101), store[2], &distance_vector));
2018 EXPECT_EQ(distance_vector.GetEntries()[0].dependence_information,
2019 DistanceEntry::DependenceInformation::PEEL);
2020 EXPECT_TRUE(distance_vector.GetEntries()[0].peel_last);
2021 }
2022
2023 // Tests identifying peel first with weak zero with source as zero index.
2024 // 105 -> 106
2025 {
2026 DistanceVector distance_vector{loops.size()};
2027 EXPECT_FALSE(analysis.GetDependence(
2028 context->get_def_use_mgr()->GetDef(105), store[3], &distance_vector));
2029 EXPECT_EQ(distance_vector.GetEntries()[0].dependence_information,
2030 DistanceEntry::DependenceInformation::PEEL);
2031 EXPECT_TRUE(distance_vector.GetEntries()[0].peel_last);
2032 }
2033 }
2034 // For the loop in function d
2035 {
2036 const Function* f = spvtest::GetFunction(module, 12);
2037 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
2038
2039 Loop* loop = &ld.GetLoopByIndex(0);
2040 std::vector<const Loop*> loops{loop};
2041 LoopDependenceAnalysis analysis{context.get(), loops};
2042
2043 const Instruction* store[4];
2044 int stores_found = 0;
2045 for (const Instruction& inst : *spvtest::GetBasicBlock(f, 111)) {
2046 if (inst.opcode() == spv::Op::OpStore) {
2047 store[stores_found] = &inst;
2048 ++stores_found;
2049 }
2050 }
2051
2052 for (int i = 0; i < 4; ++i) {
2053 EXPECT_TRUE(store[i]);
2054 }
2055
2056 // Tests identifying peel first with weak zero with destination as zero
2057 // index.
2058 // 120 -> 121
2059 {
2060 DistanceVector distance_vector{loops.size()};
2061 EXPECT_FALSE(analysis.GetDependence(
2062 context->get_def_use_mgr()->GetDef(120), store[0], &distance_vector));
2063 EXPECT_EQ(distance_vector.GetEntries()[0].dependence_information,
2064 DistanceEntry::DependenceInformation::PEEL);
2065 EXPECT_TRUE(distance_vector.GetEntries()[0].peel_first);
2066 }
2067
2068 // Tests identifying peel first with weak zero with source as zero index.
2069 // 124 -> 125
2070 {
2071 DistanceVector distance_vector{loops.size()};
2072 EXPECT_FALSE(analysis.GetDependence(
2073 context->get_def_use_mgr()->GetDef(124), store[1], &distance_vector));
2074 EXPECT_EQ(distance_vector.GetEntries()[0].dependence_information,
2075 DistanceEntry::DependenceInformation::PEEL);
2076 EXPECT_TRUE(distance_vector.GetEntries()[0].peel_first);
2077 }
2078
2079 // Tests identifying peel first with weak zero with destination as zero
2080 // index.
2081 // 128 -> 129
2082 {
2083 DistanceVector distance_vector{loops.size()};
2084 EXPECT_FALSE(analysis.GetDependence(
2085 context->get_def_use_mgr()->GetDef(128), store[2], &distance_vector));
2086 EXPECT_EQ(distance_vector.GetEntries()[0].dependence_information,
2087 DistanceEntry::DependenceInformation::PEEL);
2088 EXPECT_TRUE(distance_vector.GetEntries()[0].peel_last);
2089 }
2090
2091 // Tests identifying peel first with weak zero with source as zero index.
2092 // 132 -> 133
2093 {
2094 DistanceVector distance_vector{loops.size()};
2095 EXPECT_FALSE(analysis.GetDependence(
2096 context->get_def_use_mgr()->GetDef(132), store[3], &distance_vector));
2097 EXPECT_EQ(distance_vector.GetEntries()[0].dependence_information,
2098 DistanceEntry::DependenceInformation::PEEL);
2099 EXPECT_TRUE(distance_vector.GetEntries()[0].peel_last);
2100 }
2101 }
2102 }
2103
2104 /*
2105 Generated from the following GLSL fragment shader
2106 with --eliminate-local-multi-store
2107 #version 440 core
2108 void main(){
2109 int[10][10] arr;
2110 for (int i = 0; i < 10; i++) {
2111 arr[i][i] = arr[i][i];
2112 arr[0][i] = arr[1][i];
2113 arr[1][i] = arr[0][i];
2114 arr[i][0] = arr[i][1];
2115 arr[i][1] = arr[i][0];
2116 arr[0][1] = arr[1][0];
2117 }
2118 }
2119 */
TEST(DependencyAnalysis,MultipleSubscriptZIVSIV)2120 TEST(DependencyAnalysis, MultipleSubscriptZIVSIV) {
2121 const std::string text = R"( OpCapability Shader
2122 %1 = OpExtInstImport "GLSL.std.450"
2123 OpMemoryModel Logical GLSL450
2124 OpEntryPoint Fragment %4 "main"
2125 OpExecutionMode %4 OriginUpperLeft
2126 OpSource GLSL 440
2127 OpName %4 "main"
2128 OpName %8 "i"
2129 OpName %24 "arr"
2130 %2 = OpTypeVoid
2131 %3 = OpTypeFunction %2
2132 %6 = OpTypeInt 32 1
2133 %7 = OpTypePointer Function %6
2134 %9 = OpConstant %6 0
2135 %16 = OpConstant %6 10
2136 %17 = OpTypeBool
2137 %19 = OpTypeInt 32 0
2138 %20 = OpConstant %19 10
2139 %21 = OpTypeArray %6 %20
2140 %22 = OpTypeArray %21 %20
2141 %23 = OpTypePointer Function %22
2142 %33 = OpConstant %6 1
2143 %4 = OpFunction %2 None %3
2144 %5 = OpLabel
2145 %8 = OpVariable %7 Function
2146 %24 = OpVariable %23 Function
2147 OpStore %8 %9
2148 OpBranch %10
2149 %10 = OpLabel
2150 %58 = OpPhi %6 %9 %5 %57 %13
2151 OpLoopMerge %12 %13 None
2152 OpBranch %14
2153 %14 = OpLabel
2154 %18 = OpSLessThan %17 %58 %16
2155 OpBranchConditional %18 %11 %12
2156 %11 = OpLabel
2157 %29 = OpAccessChain %7 %24 %58 %58
2158 %30 = OpLoad %6 %29
2159 %31 = OpAccessChain %7 %24 %58 %58
2160 OpStore %31 %30
2161 %35 = OpAccessChain %7 %24 %33 %58
2162 %36 = OpLoad %6 %35
2163 %37 = OpAccessChain %7 %24 %9 %58
2164 OpStore %37 %36
2165 %40 = OpAccessChain %7 %24 %9 %58
2166 %41 = OpLoad %6 %40
2167 %42 = OpAccessChain %7 %24 %33 %58
2168 OpStore %42 %41
2169 %45 = OpAccessChain %7 %24 %58 %33
2170 %46 = OpLoad %6 %45
2171 %47 = OpAccessChain %7 %24 %58 %9
2172 OpStore %47 %46
2173 %50 = OpAccessChain %7 %24 %58 %9
2174 %51 = OpLoad %6 %50
2175 %52 = OpAccessChain %7 %24 %58 %33
2176 OpStore %52 %51
2177 %53 = OpAccessChain %7 %24 %33 %9
2178 %54 = OpLoad %6 %53
2179 %55 = OpAccessChain %7 %24 %9 %33
2180 OpStore %55 %54
2181 OpBranch %13
2182 %13 = OpLabel
2183 %57 = OpIAdd %6 %58 %33
2184 OpStore %8 %57
2185 OpBranch %10
2186 %12 = OpLabel
2187 OpReturn
2188 OpFunctionEnd
2189 )";
2190
2191 std::unique_ptr<IRContext> context =
2192 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
2193 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
2194 Module* module = context->module();
2195 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
2196 << text << std::endl;
2197 const Function* f = spvtest::GetFunction(module, 4);
2198 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
2199
2200 Loop* loop = &ld.GetLoopByIndex(0);
2201 std::vector<const Loop*> loops{loop};
2202 LoopDependenceAnalysis analysis{context.get(), loops};
2203
2204 const Instruction* store[6];
2205 int stores_found = 0;
2206 for (const Instruction& inst : *spvtest::GetBasicBlock(f, 11)) {
2207 if (inst.opcode() == spv::Op::OpStore) {
2208 store[stores_found] = &inst;
2209 ++stores_found;
2210 }
2211 }
2212
2213 for (int i = 0; i < 6; ++i) {
2214 EXPECT_TRUE(store[i]);
2215 }
2216
2217 // 30 -> 31
2218 {
2219 DistanceVector distance_vector{loops.size()};
2220 EXPECT_FALSE(analysis.GetDependence(context->get_def_use_mgr()->GetDef(30),
2221 store[0], &distance_vector));
2222 EXPECT_EQ(distance_vector.GetEntries()[0].dependence_information,
2223 DistanceEntry::DependenceInformation::DISTANCE);
2224 EXPECT_EQ(distance_vector.GetEntries()[0].direction,
2225 DistanceEntry::Directions::EQ);
2226 EXPECT_EQ(distance_vector.GetEntries()[0].distance, 0);
2227 }
2228
2229 // 36 -> 37
2230 {
2231 DistanceVector distance_vector{loops.size()};
2232 EXPECT_TRUE(analysis.GetDependence(context->get_def_use_mgr()->GetDef(36),
2233 store[1], &distance_vector));
2234 }
2235
2236 // 41 -> 42
2237 {
2238 DistanceVector distance_vector{loops.size()};
2239 EXPECT_TRUE(analysis.GetDependence(context->get_def_use_mgr()->GetDef(41),
2240 store[2], &distance_vector));
2241 }
2242
2243 // 46 -> 47
2244 {
2245 DistanceVector distance_vector{loops.size()};
2246 EXPECT_TRUE(analysis.GetDependence(context->get_def_use_mgr()->GetDef(46),
2247 store[3], &distance_vector));
2248 EXPECT_EQ(distance_vector.GetEntries()[0].dependence_information,
2249 DistanceEntry::DependenceInformation::DISTANCE);
2250 EXPECT_EQ(distance_vector.GetEntries()[0].direction,
2251 DistanceEntry::Directions::EQ);
2252 EXPECT_EQ(distance_vector.GetEntries()[0].distance, 0);
2253 }
2254
2255 // 51 -> 52
2256 {
2257 DistanceVector distance_vector{loops.size()};
2258 EXPECT_TRUE(analysis.GetDependence(context->get_def_use_mgr()->GetDef(51),
2259 store[4], &distance_vector));
2260 EXPECT_EQ(distance_vector.GetEntries()[0].dependence_information,
2261 DistanceEntry::DependenceInformation::DISTANCE);
2262 EXPECT_EQ(distance_vector.GetEntries()[0].direction,
2263 DistanceEntry::Directions::EQ);
2264 EXPECT_EQ(distance_vector.GetEntries()[0].distance, 0);
2265 }
2266
2267 // 54 -> 55
2268 {
2269 DistanceVector distance_vector{loops.size()};
2270 EXPECT_TRUE(analysis.GetDependence(context->get_def_use_mgr()->GetDef(54),
2271 store[5], &distance_vector));
2272 }
2273 }
2274
2275 /*
2276 Generated from the following GLSL fragment shader
2277 with --eliminate-local-multi-store
2278 #version 440 core
2279 void a(){
2280 int[10] arr;
2281 for (int i = 0; i < 10; i++) {
2282 for (int j = 0; j < 10; j++) {
2283 arr[j] = arr[j];
2284 }
2285 }
2286 }
2287 void b(){
2288 int[10] arr;
2289 for (int i = 0; i < 10; i++) {
2290 for (int j = 0; j < 10; j++) {
2291 arr[i] = arr[i];
2292 }
2293 }
2294 }
2295 void main() {
2296 a();
2297 b();
2298 }
2299 */
TEST(DependencyAnalysis,IrrelevantSubscripts)2300 TEST(DependencyAnalysis, IrrelevantSubscripts) {
2301 const std::string text = R"( OpCapability Shader
2302 %1 = OpExtInstImport "GLSL.std.450"
2303 OpMemoryModel Logical GLSL450
2304 OpEntryPoint Fragment %4 "main"
2305 OpExecutionMode %4 OriginUpperLeft
2306 OpSource GLSL 440
2307 OpName %4 "main"
2308 OpName %6 "a("
2309 OpName %8 "b("
2310 OpName %12 "i"
2311 OpName %23 "j"
2312 OpName %35 "arr"
2313 OpName %46 "i"
2314 OpName %54 "j"
2315 OpName %62 "arr"
2316 %2 = OpTypeVoid
2317 %3 = OpTypeFunction %2
2318 %10 = OpTypeInt 32 1
2319 %11 = OpTypePointer Function %10
2320 %13 = OpConstant %10 0
2321 %20 = OpConstant %10 10
2322 %21 = OpTypeBool
2323 %31 = OpTypeInt 32 0
2324 %32 = OpConstant %31 10
2325 %33 = OpTypeArray %10 %32
2326 %34 = OpTypePointer Function %33
2327 %42 = OpConstant %10 1
2328 %4 = OpFunction %2 None %3
2329 %5 = OpLabel
2330 %72 = OpFunctionCall %2 %6
2331 %73 = OpFunctionCall %2 %8
2332 OpReturn
2333 OpFunctionEnd
2334 %6 = OpFunction %2 None %3
2335 %7 = OpLabel
2336 %12 = OpVariable %11 Function
2337 %23 = OpVariable %11 Function
2338 %35 = OpVariable %34 Function
2339 OpStore %12 %13
2340 OpBranch %14
2341 %14 = OpLabel
2342 %74 = OpPhi %10 %13 %7 %45 %17
2343 OpLoopMerge %16 %17 None
2344 OpBranch %18
2345 %18 = OpLabel
2346 %22 = OpSLessThan %21 %74 %20
2347 OpBranchConditional %22 %15 %16
2348 %15 = OpLabel
2349 OpStore %23 %13
2350 OpBranch %24
2351 %24 = OpLabel
2352 %75 = OpPhi %10 %13 %15 %43 %27
2353 OpLoopMerge %26 %27 None
2354 OpBranch %28
2355 %28 = OpLabel
2356 %30 = OpSLessThan %21 %75 %20
2357 OpBranchConditional %30 %25 %26
2358 %25 = OpLabel
2359 %38 = OpAccessChain %11 %35 %75
2360 %39 = OpLoad %10 %38
2361 %40 = OpAccessChain %11 %35 %75
2362 OpStore %40 %39
2363 OpBranch %27
2364 %27 = OpLabel
2365 %43 = OpIAdd %10 %75 %42
2366 OpStore %23 %43
2367 OpBranch %24
2368 %26 = OpLabel
2369 OpBranch %17
2370 %17 = OpLabel
2371 %45 = OpIAdd %10 %74 %42
2372 OpStore %12 %45
2373 OpBranch %14
2374 %16 = OpLabel
2375 OpReturn
2376 OpFunctionEnd
2377 %8 = OpFunction %2 None %3
2378 %9 = OpLabel
2379 %46 = OpVariable %11 Function
2380 %54 = OpVariable %11 Function
2381 %62 = OpVariable %34 Function
2382 OpStore %46 %13
2383 OpBranch %47
2384 %47 = OpLabel
2385 %77 = OpPhi %10 %13 %9 %71 %50
2386 OpLoopMerge %49 %50 None
2387 OpBranch %51
2388 %51 = OpLabel
2389 %53 = OpSLessThan %21 %77 %20
2390 OpBranchConditional %53 %48 %49
2391 %48 = OpLabel
2392 OpStore %54 %13
2393 OpBranch %55
2394 %55 = OpLabel
2395 %78 = OpPhi %10 %13 %48 %69 %58
2396 OpLoopMerge %57 %58 None
2397 OpBranch %59
2398 %59 = OpLabel
2399 %61 = OpSLessThan %21 %78 %20
2400 OpBranchConditional %61 %56 %57
2401 %56 = OpLabel
2402 %65 = OpAccessChain %11 %62 %77
2403 %66 = OpLoad %10 %65
2404 %67 = OpAccessChain %11 %62 %77
2405 OpStore %67 %66
2406 OpBranch %58
2407 %58 = OpLabel
2408 %69 = OpIAdd %10 %78 %42
2409 OpStore %54 %69
2410 OpBranch %55
2411 %57 = OpLabel
2412 OpBranch %50
2413 %50 = OpLabel
2414 %71 = OpIAdd %10 %77 %42
2415 OpStore %46 %71
2416 OpBranch %47
2417 %49 = OpLabel
2418 OpReturn
2419 OpFunctionEnd
2420 )";
2421
2422 std::unique_ptr<IRContext> context =
2423 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
2424 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
2425 Module* module = context->module();
2426 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
2427 << text << std::endl;
2428 // For the loop in function a
2429 {
2430 const Function* f = spvtest::GetFunction(module, 6);
2431 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
2432
2433 std::vector<const Loop*> loops{&ld.GetLoopByIndex(1),
2434 &ld.GetLoopByIndex(0)};
2435 LoopDependenceAnalysis analysis{context.get(), loops};
2436
2437 const Instruction* store[1];
2438 int stores_found = 0;
2439 for (const Instruction& inst : *spvtest::GetBasicBlock(f, 25)) {
2440 if (inst.opcode() == spv::Op::OpStore) {
2441 store[stores_found] = &inst;
2442 ++stores_found;
2443 }
2444 }
2445
2446 for (int i = 0; i < 1; ++i) {
2447 EXPECT_TRUE(store[i]);
2448 }
2449
2450 // 39 -> 40
2451 {
2452 DistanceVector distance_vector{loops.size()};
2453 analysis.SetDebugStream(std::cout);
2454 EXPECT_FALSE(analysis.GetDependence(
2455 context->get_def_use_mgr()->GetDef(39), store[0], &distance_vector));
2456 EXPECT_EQ(distance_vector.GetEntries()[0].dependence_information,
2457 DistanceEntry::DependenceInformation::IRRELEVANT);
2458 EXPECT_EQ(distance_vector.GetEntries()[1].dependence_information,
2459 DistanceEntry::DependenceInformation::DISTANCE);
2460 EXPECT_EQ(distance_vector.GetEntries()[1].distance, 0);
2461 }
2462 }
2463
2464 // For the loop in function b
2465 {
2466 const Function* f = spvtest::GetFunction(module, 8);
2467 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
2468
2469 std::vector<const Loop*> loops{&ld.GetLoopByIndex(1),
2470 &ld.GetLoopByIndex(0)};
2471 LoopDependenceAnalysis analysis{context.get(), loops};
2472
2473 const Instruction* store[1];
2474 int stores_found = 0;
2475 for (const Instruction& inst : *spvtest::GetBasicBlock(f, 56)) {
2476 if (inst.opcode() == spv::Op::OpStore) {
2477 store[stores_found] = &inst;
2478 ++stores_found;
2479 }
2480 }
2481
2482 for (int i = 0; i < 1; ++i) {
2483 EXPECT_TRUE(store[i]);
2484 }
2485
2486 // 66 -> 67
2487 {
2488 DistanceVector distance_vector{loops.size()};
2489 EXPECT_FALSE(analysis.GetDependence(
2490 context->get_def_use_mgr()->GetDef(66), store[0], &distance_vector));
2491 EXPECT_EQ(distance_vector.GetEntries()[0].dependence_information,
2492 DistanceEntry::DependenceInformation::DISTANCE);
2493 EXPECT_EQ(distance_vector.GetEntries()[0].distance, 0);
2494 EXPECT_EQ(distance_vector.GetEntries()[1].dependence_information,
2495 DistanceEntry::DependenceInformation::IRRELEVANT);
2496 }
2497 }
2498 }
2499
CheckDependenceAndDirection(const Instruction * source,const Instruction * destination,bool expected_dependence,DistanceVector expected_distance,LoopDependenceAnalysis * analysis)2500 void CheckDependenceAndDirection(const Instruction* source,
2501 const Instruction* destination,
2502 bool expected_dependence,
2503 DistanceVector expected_distance,
2504 LoopDependenceAnalysis* analysis) {
2505 DistanceVector dv_entry(2);
2506 EXPECT_EQ(expected_dependence,
2507 analysis->GetDependence(source, destination, &dv_entry));
2508 EXPECT_EQ(expected_distance, dv_entry);
2509 }
2510
2511 /*
2512 Generated from the following GLSL fragment shader
2513 with --eliminate-local-multi-store
2514 #version 440 core
2515 layout(location = 0) in vec4 c;
2516 void main(){
2517 int[10] arr;
2518 int a = 2;
2519 int b = 3;
2520 int N = int(c.x);
2521 for (int i = 0; i < 10; i++) {
2522 for (int j = 2; j < 10; j++) {
2523 arr[i] = arr[j]; // 0
2524 arr[j] = arr[i]; // 1
2525 arr[j-2] = arr[i+3]; // 2
2526 arr[j-a] = arr[i+b]; // 3
2527 arr[2*i] = arr[4*j+3]; // 4, independent
2528 arr[2*i] = arr[4*j]; // 5
2529 arr[i+j] = arr[i+j]; // 6
2530 arr[10*i+j] = arr[10*i+j]; // 7
2531 arr[10*i+10*j] = arr[10*i+10*j+3]; // 8, independent
2532 arr[10*i+10*j] = arr[10*i+N*j+3]; // 9, bail out because of N coefficient
2533 arr[10*i+10*j] = arr[10*i+10*j+N]; // 10, bail out because of N constant
2534 // term
2535 arr[10*i+N*j] = arr[10*i+10*j+3]; // 11, bail out because of N coefficient
2536 arr[10*i+10*j+N] = arr[10*i+10*j]; // 12, bail out because of N constant
2537 // term
2538 arr[10*i] = arr[5*j]; // 13, independent
2539 arr[5*i] = arr[10*j]; // 14, independent
2540 arr[9*i] = arr[3*j]; // 15, independent
2541 arr[3*i] = arr[9*j]; // 16, independent
2542 }
2543 }
2544 }
2545 */
TEST(DependencyAnalysis,MIV)2546 TEST(DependencyAnalysis, MIV) {
2547 const std::string text = R"(
2548 OpCapability Shader
2549 %1 = OpExtInstImport "GLSL.std.450"
2550 OpMemoryModel Logical GLSL450
2551 OpEntryPoint Fragment %4 "main" %16
2552 OpExecutionMode %4 OriginUpperLeft
2553 OpSource GLSL 440
2554 OpName %4 "main"
2555 OpName %8 "a"
2556 OpName %10 "b"
2557 OpName %12 "N"
2558 OpName %16 "c"
2559 OpName %23 "i"
2560 OpName %34 "j"
2561 OpName %45 "arr"
2562 OpDecorate %16 Location 0
2563 %2 = OpTypeVoid
2564 %3 = OpTypeFunction %2
2565 %6 = OpTypeInt 32 1
2566 %7 = OpTypePointer Function %6
2567 %9 = OpConstant %6 2
2568 %11 = OpConstant %6 3
2569 %13 = OpTypeFloat 32
2570 %14 = OpTypeVector %13 4
2571 %15 = OpTypePointer Input %14
2572 %16 = OpVariable %15 Input
2573 %17 = OpTypeInt 32 0
2574 %18 = OpConstant %17 0
2575 %19 = OpTypePointer Input %13
2576 %24 = OpConstant %6 0
2577 %31 = OpConstant %6 10
2578 %32 = OpTypeBool
2579 %42 = OpConstant %17 10
2580 %43 = OpTypeArray %6 %42
2581 %44 = OpTypePointer Function %43
2582 %74 = OpConstant %6 4
2583 %184 = OpConstant %6 5
2584 %197 = OpConstant %6 9
2585 %213 = OpConstant %6 1
2586 %218 = OpUndef %6
2587 %4 = OpFunction %2 None %3
2588 %5 = OpLabel
2589 %8 = OpVariable %7 Function
2590 %10 = OpVariable %7 Function
2591 %12 = OpVariable %7 Function
2592 %23 = OpVariable %7 Function
2593 %34 = OpVariable %7 Function
2594 %45 = OpVariable %44 Function
2595 OpStore %8 %9
2596 OpStore %10 %11
2597 %20 = OpAccessChain %19 %16 %18
2598 %21 = OpLoad %13 %20
2599 %22 = OpConvertFToS %6 %21
2600 OpStore %12 %22
2601 OpStore %23 %24
2602 OpBranch %25
2603 %25 = OpLabel
2604 %217 = OpPhi %6 %24 %5 %216 %28
2605 %219 = OpPhi %6 %218 %5 %220 %28
2606 OpLoopMerge %27 %28 None
2607 OpBranch %29
2608 %29 = OpLabel
2609 %33 = OpSLessThan %32 %217 %31
2610 OpBranchConditional %33 %26 %27
2611 %26 = OpLabel
2612 OpStore %34 %9
2613 OpBranch %35
2614 %35 = OpLabel
2615 %220 = OpPhi %6 %9 %26 %214 %38
2616 OpLoopMerge %37 %38 None
2617 OpBranch %39
2618 %39 = OpLabel
2619 %41 = OpSLessThan %32 %220 %31
2620 OpBranchConditional %41 %36 %37
2621 %36 = OpLabel
2622 %48 = OpAccessChain %7 %45 %220
2623 %49 = OpLoad %6 %48
2624 %50 = OpAccessChain %7 %45 %217
2625 OpStore %50 %49
2626 %53 = OpAccessChain %7 %45 %217
2627 %54 = OpLoad %6 %53
2628 %55 = OpAccessChain %7 %45 %220
2629 OpStore %55 %54
2630 %57 = OpISub %6 %220 %9
2631 %59 = OpIAdd %6 %217 %11
2632 %60 = OpAccessChain %7 %45 %59
2633 %61 = OpLoad %6 %60
2634 %62 = OpAccessChain %7 %45 %57
2635 OpStore %62 %61
2636 %65 = OpISub %6 %220 %9
2637 %68 = OpIAdd %6 %217 %11
2638 %69 = OpAccessChain %7 %45 %68
2639 %70 = OpLoad %6 %69
2640 %71 = OpAccessChain %7 %45 %65
2641 OpStore %71 %70
2642 %73 = OpIMul %6 %9 %217
2643 %76 = OpIMul %6 %74 %220
2644 %77 = OpIAdd %6 %76 %11
2645 %78 = OpAccessChain %7 %45 %77
2646 %79 = OpLoad %6 %78
2647 %80 = OpAccessChain %7 %45 %73
2648 OpStore %80 %79
2649 %82 = OpIMul %6 %9 %217
2650 %84 = OpIMul %6 %74 %220
2651 %85 = OpAccessChain %7 %45 %84
2652 %86 = OpLoad %6 %85
2653 %87 = OpAccessChain %7 %45 %82
2654 OpStore %87 %86
2655 %90 = OpIAdd %6 %217 %220
2656 %93 = OpIAdd %6 %217 %220
2657 %94 = OpAccessChain %7 %45 %93
2658 %95 = OpLoad %6 %94
2659 %96 = OpAccessChain %7 %45 %90
2660 OpStore %96 %95
2661 %98 = OpIMul %6 %31 %217
2662 %100 = OpIAdd %6 %98 %220
2663 %102 = OpIMul %6 %31 %217
2664 %104 = OpIAdd %6 %102 %220
2665 %105 = OpAccessChain %7 %45 %104
2666 %106 = OpLoad %6 %105
2667 %107 = OpAccessChain %7 %45 %100
2668 OpStore %107 %106
2669 %109 = OpIMul %6 %31 %217
2670 %111 = OpIMul %6 %31 %220
2671 %112 = OpIAdd %6 %109 %111
2672 %114 = OpIMul %6 %31 %217
2673 %116 = OpIMul %6 %31 %220
2674 %117 = OpIAdd %6 %114 %116
2675 %118 = OpIAdd %6 %117 %11
2676 %119 = OpAccessChain %7 %45 %118
2677 %120 = OpLoad %6 %119
2678 %121 = OpAccessChain %7 %45 %112
2679 OpStore %121 %120
2680 %123 = OpIMul %6 %31 %217
2681 %125 = OpIMul %6 %31 %220
2682 %126 = OpIAdd %6 %123 %125
2683 %128 = OpIMul %6 %31 %217
2684 %131 = OpIMul %6 %22 %220
2685 %132 = OpIAdd %6 %128 %131
2686 %133 = OpIAdd %6 %132 %11
2687 %134 = OpAccessChain %7 %45 %133
2688 %135 = OpLoad %6 %134
2689 %136 = OpAccessChain %7 %45 %126
2690 OpStore %136 %135
2691 %138 = OpIMul %6 %31 %217
2692 %140 = OpIMul %6 %31 %220
2693 %141 = OpIAdd %6 %138 %140
2694 %143 = OpIMul %6 %31 %217
2695 %145 = OpIMul %6 %31 %220
2696 %146 = OpIAdd %6 %143 %145
2697 %148 = OpIAdd %6 %146 %22
2698 %149 = OpAccessChain %7 %45 %148
2699 %150 = OpLoad %6 %149
2700 %151 = OpAccessChain %7 %45 %141
2701 OpStore %151 %150
2702 %153 = OpIMul %6 %31 %217
2703 %156 = OpIMul %6 %22 %220
2704 %157 = OpIAdd %6 %153 %156
2705 %159 = OpIMul %6 %31 %217
2706 %161 = OpIMul %6 %31 %220
2707 %162 = OpIAdd %6 %159 %161
2708 %163 = OpIAdd %6 %162 %11
2709 %164 = OpAccessChain %7 %45 %163
2710 %165 = OpLoad %6 %164
2711 %166 = OpAccessChain %7 %45 %157
2712 OpStore %166 %165
2713 %168 = OpIMul %6 %31 %217
2714 %170 = OpIMul %6 %31 %220
2715 %171 = OpIAdd %6 %168 %170
2716 %173 = OpIAdd %6 %171 %22
2717 %175 = OpIMul %6 %31 %217
2718 %177 = OpIMul %6 %31 %220
2719 %178 = OpIAdd %6 %175 %177
2720 %179 = OpAccessChain %7 %45 %178
2721 %180 = OpLoad %6 %179
2722 %181 = OpAccessChain %7 %45 %173
2723 OpStore %181 %180
2724 %183 = OpIMul %6 %31 %217
2725 %186 = OpIMul %6 %184 %220
2726 %187 = OpAccessChain %7 %45 %186
2727 %188 = OpLoad %6 %187
2728 %189 = OpAccessChain %7 %45 %183
2729 OpStore %189 %188
2730 %191 = OpIMul %6 %184 %217
2731 %193 = OpIMul %6 %31 %220
2732 %194 = OpAccessChain %7 %45 %193
2733 %195 = OpLoad %6 %194
2734 %196 = OpAccessChain %7 %45 %191
2735 OpStore %196 %195
2736 %199 = OpIMul %6 %197 %217
2737 %201 = OpIMul %6 %11 %220
2738 %202 = OpAccessChain %7 %45 %201
2739 %203 = OpLoad %6 %202
2740 %204 = OpAccessChain %7 %45 %199
2741 OpStore %204 %203
2742 %206 = OpIMul %6 %11 %217
2743 %208 = OpIMul %6 %197 %220
2744 %209 = OpAccessChain %7 %45 %208
2745 %210 = OpLoad %6 %209
2746 %211 = OpAccessChain %7 %45 %206
2747 OpStore %211 %210
2748 OpBranch %38
2749 %38 = OpLabel
2750 %214 = OpIAdd %6 %220 %213
2751 OpStore %34 %214
2752 OpBranch %35
2753 %37 = OpLabel
2754 OpBranch %28
2755 %28 = OpLabel
2756 %216 = OpIAdd %6 %217 %213
2757 OpStore %23 %216
2758 OpBranch %25
2759 %27 = OpLabel
2760 OpReturn
2761 OpFunctionEnd
2762 )";
2763
2764 std::unique_ptr<IRContext> context =
2765 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
2766 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
2767 Module* module = context->module();
2768 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
2769 << text << std::endl;
2770 const Function* f = spvtest::GetFunction(module, 4);
2771 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
2772
2773 std::vector<const Loop*> loops{&ld.GetLoopByIndex(0), &ld.GetLoopByIndex(1)};
2774
2775 LoopDependenceAnalysis analysis{context.get(), loops};
2776
2777 const int instructions_expected = 17;
2778 const Instruction* store[instructions_expected];
2779 const Instruction* load[instructions_expected];
2780 int stores_found = 0;
2781 int loads_found = 0;
2782
2783 int block_id = 36;
2784 ASSERT_TRUE(spvtest::GetBasicBlock(f, block_id));
2785
2786 for (const Instruction& inst : *spvtest::GetBasicBlock(f, block_id)) {
2787 if (inst.opcode() == spv::Op::OpStore) {
2788 store[stores_found] = &inst;
2789 ++stores_found;
2790 }
2791
2792 if (inst.opcode() == spv::Op::OpLoad) {
2793 load[loads_found] = &inst;
2794 ++loads_found;
2795 }
2796 }
2797
2798 EXPECT_EQ(instructions_expected, stores_found);
2799 EXPECT_EQ(instructions_expected, loads_found);
2800
2801 auto directions_all = DistanceEntry(DistanceEntry::Directions::ALL);
2802 auto directions_none = DistanceEntry(DistanceEntry::Directions::NONE);
2803
2804 auto dependent = DistanceVector({directions_all, directions_all});
2805 auto independent = DistanceVector({directions_none, directions_none});
2806
2807 CheckDependenceAndDirection(load[0], store[0], false, dependent, &analysis);
2808 CheckDependenceAndDirection(load[1], store[1], false, dependent, &analysis);
2809 CheckDependenceAndDirection(load[2], store[2], false, dependent, &analysis);
2810 CheckDependenceAndDirection(load[3], store[3], false, dependent, &analysis);
2811 CheckDependenceAndDirection(load[4], store[4], true, independent, &analysis);
2812 CheckDependenceAndDirection(load[5], store[5], false, dependent, &analysis);
2813 CheckDependenceAndDirection(load[6], store[6], false, dependent, &analysis);
2814 CheckDependenceAndDirection(load[7], store[7], false, dependent, &analysis);
2815 CheckDependenceAndDirection(load[8], store[8], true, independent, &analysis);
2816 CheckDependenceAndDirection(load[9], store[9], false, dependent, &analysis);
2817 CheckDependenceAndDirection(load[10], store[10], false, dependent, &analysis);
2818 CheckDependenceAndDirection(load[11], store[11], false, dependent, &analysis);
2819 CheckDependenceAndDirection(load[12], store[12], false, dependent, &analysis);
2820 CheckDependenceAndDirection(load[13], store[13], true, independent,
2821 &analysis);
2822 CheckDependenceAndDirection(load[14], store[14], true, independent,
2823 &analysis);
2824 CheckDependenceAndDirection(load[15], store[15], true, independent,
2825 &analysis);
2826 CheckDependenceAndDirection(load[16], store[16], true, independent,
2827 &analysis);
2828 }
2829
PartitionSubscripts(const Instruction * instruction_0,const Instruction * instruction_1,LoopDependenceAnalysis * analysis,std::vector<std::vector<int>> expected_ids)2830 void PartitionSubscripts(const Instruction* instruction_0,
2831 const Instruction* instruction_1,
2832 LoopDependenceAnalysis* analysis,
2833 std::vector<std::vector<int>> expected_ids) {
2834 auto subscripts_0 = analysis->GetSubscripts(instruction_0);
2835 auto subscripts_1 = analysis->GetSubscripts(instruction_1);
2836
2837 std::vector<std::set<std::pair<Instruction*, Instruction*>>>
2838 expected_partition{};
2839
2840 for (const auto& partition : expected_ids) {
2841 expected_partition.push_back(
2842 std::set<std::pair<Instruction*, Instruction*>>{});
2843 for (auto id : partition) {
2844 expected_partition.back().insert({subscripts_0[id], subscripts_1[id]});
2845 }
2846 }
2847
2848 EXPECT_EQ(expected_partition,
2849 analysis->PartitionSubscripts(subscripts_0, subscripts_1));
2850 }
2851
2852 /*
2853 Generated from the following GLSL fragment shader
2854 with --eliminate-local-multi-store
2855 #version 440 core
2856 void main(){
2857 int[10][10][10][10] arr;
2858 for (int i = 0; i < 10; i++) {
2859 for (int j = 0; j < 10; j++) {
2860 for (int k = 0; k < 10; k++) {
2861 for (int l = 0; l < 10; l++) {
2862 arr[i][j][k][l] = arr[i][j][k][l]; // 0, all independent
2863 arr[i][j][k][l] = arr[i][j][l][0]; // 1, last 2 coupled
2864 arr[i][j][k][l] = arr[j][i][k][l]; // 2, first 2 coupled
2865 arr[i][j][k][l] = arr[l][j][k][i]; // 3, first & last coupled
2866 arr[i][j][k][l] = arr[i][k][j][l]; // 4, middle 2 coupled
2867 arr[i+j][j][k][l] = arr[i][j][k][l]; // 5, first 2 coupled
2868 arr[i+j+k][j][k][l] = arr[i][j][k][l]; // 6, first 3 coupled
2869 arr[i+j+k+l][j][k][l] = arr[i][j][k][l]; // 7, all 4 coupled
2870 arr[i][j][k][l] = arr[i][l][j][k]; // 8, last 3 coupled
2871 arr[i][j-k][k][l] = arr[i][j][l][k]; // 9, last 3 coupled
2872 arr[i][j][k][l] = arr[l][i][j][k]; // 10, all 4 coupled
2873 arr[i][j][k][l] = arr[j][i][l][k]; // 11, 2 coupled partitions (i,j) &
2874 (l&k)
2875 arr[i][j][k][l] = arr[k][l][i][j]; // 12, 2 coupled partitions (i,k) &
2876 (j&l)
2877 }
2878 }
2879 }
2880 }
2881 }
2882 */
TEST(DependencyAnalysis,SubscriptPartitioning)2883 TEST(DependencyAnalysis, SubscriptPartitioning) {
2884 const std::string text = R"(
2885 OpCapability Shader
2886 %1 = OpExtInstImport "GLSL.std.450"
2887 OpMemoryModel Logical GLSL450
2888 OpEntryPoint Fragment %4 "main"
2889 OpExecutionMode %4 OriginUpperLeft
2890 OpSource GLSL 440
2891 OpName %4 "main"
2892 OpName %8 "i"
2893 OpName %19 "j"
2894 OpName %27 "k"
2895 OpName %35 "l"
2896 OpName %50 "arr"
2897 %2 = OpTypeVoid
2898 %3 = OpTypeFunction %2
2899 %6 = OpTypeInt 32 1
2900 %7 = OpTypePointer Function %6
2901 %9 = OpConstant %6 0
2902 %16 = OpConstant %6 10
2903 %17 = OpTypeBool
2904 %43 = OpTypeInt 32 0
2905 %44 = OpConstant %43 10
2906 %45 = OpTypeArray %6 %44
2907 %46 = OpTypeArray %45 %44
2908 %47 = OpTypeArray %46 %44
2909 %48 = OpTypeArray %47 %44
2910 %49 = OpTypePointer Function %48
2911 %208 = OpConstant %6 1
2912 %217 = OpUndef %6
2913 %4 = OpFunction %2 None %3
2914 %5 = OpLabel
2915 %8 = OpVariable %7 Function
2916 %19 = OpVariable %7 Function
2917 %27 = OpVariable %7 Function
2918 %35 = OpVariable %7 Function
2919 %50 = OpVariable %49 Function
2920 OpStore %8 %9
2921 OpBranch %10
2922 %10 = OpLabel
2923 %216 = OpPhi %6 %9 %5 %215 %13
2924 %218 = OpPhi %6 %217 %5 %221 %13
2925 %219 = OpPhi %6 %217 %5 %222 %13
2926 %220 = OpPhi %6 %217 %5 %223 %13
2927 OpLoopMerge %12 %13 None
2928 OpBranch %14
2929 %14 = OpLabel
2930 %18 = OpSLessThan %17 %216 %16
2931 OpBranchConditional %18 %11 %12
2932 %11 = OpLabel
2933 OpStore %19 %9
2934 OpBranch %20
2935 %20 = OpLabel
2936 %221 = OpPhi %6 %9 %11 %213 %23
2937 %222 = OpPhi %6 %219 %11 %224 %23
2938 %223 = OpPhi %6 %220 %11 %225 %23
2939 OpLoopMerge %22 %23 None
2940 OpBranch %24
2941 %24 = OpLabel
2942 %26 = OpSLessThan %17 %221 %16
2943 OpBranchConditional %26 %21 %22
2944 %21 = OpLabel
2945 OpStore %27 %9
2946 OpBranch %28
2947 %28 = OpLabel
2948 %224 = OpPhi %6 %9 %21 %211 %31
2949 %225 = OpPhi %6 %223 %21 %226 %31
2950 OpLoopMerge %30 %31 None
2951 OpBranch %32
2952 %32 = OpLabel
2953 %34 = OpSLessThan %17 %224 %16
2954 OpBranchConditional %34 %29 %30
2955 %29 = OpLabel
2956 OpStore %35 %9
2957 OpBranch %36
2958 %36 = OpLabel
2959 %226 = OpPhi %6 %9 %29 %209 %39
2960 OpLoopMerge %38 %39 None
2961 OpBranch %40
2962 %40 = OpLabel
2963 %42 = OpSLessThan %17 %226 %16
2964 OpBranchConditional %42 %37 %38
2965 %37 = OpLabel
2966 %59 = OpAccessChain %7 %50 %216 %221 %224 %226
2967 %60 = OpLoad %6 %59
2968 %61 = OpAccessChain %7 %50 %216 %221 %224 %226
2969 OpStore %61 %60
2970 %69 = OpAccessChain %7 %50 %216 %221 %226 %9
2971 %70 = OpLoad %6 %69
2972 %71 = OpAccessChain %7 %50 %216 %221 %224 %226
2973 OpStore %71 %70
2974 %80 = OpAccessChain %7 %50 %221 %216 %224 %226
2975 %81 = OpLoad %6 %80
2976 %82 = OpAccessChain %7 %50 %216 %221 %224 %226
2977 OpStore %82 %81
2978 %91 = OpAccessChain %7 %50 %226 %221 %224 %216
2979 %92 = OpLoad %6 %91
2980 %93 = OpAccessChain %7 %50 %216 %221 %224 %226
2981 OpStore %93 %92
2982 %102 = OpAccessChain %7 %50 %216 %224 %221 %226
2983 %103 = OpLoad %6 %102
2984 %104 = OpAccessChain %7 %50 %216 %221 %224 %226
2985 OpStore %104 %103
2986 %107 = OpIAdd %6 %216 %221
2987 %115 = OpAccessChain %7 %50 %216 %221 %224 %226
2988 %116 = OpLoad %6 %115
2989 %117 = OpAccessChain %7 %50 %107 %221 %224 %226
2990 OpStore %117 %116
2991 %120 = OpIAdd %6 %216 %221
2992 %122 = OpIAdd %6 %120 %224
2993 %130 = OpAccessChain %7 %50 %216 %221 %224 %226
2994 %131 = OpLoad %6 %130
2995 %132 = OpAccessChain %7 %50 %122 %221 %224 %226
2996 OpStore %132 %131
2997 %135 = OpIAdd %6 %216 %221
2998 %137 = OpIAdd %6 %135 %224
2999 %139 = OpIAdd %6 %137 %226
3000 %147 = OpAccessChain %7 %50 %216 %221 %224 %226
3001 %148 = OpLoad %6 %147
3002 %149 = OpAccessChain %7 %50 %139 %221 %224 %226
3003 OpStore %149 %148
3004 %158 = OpAccessChain %7 %50 %216 %226 %221 %224
3005 %159 = OpLoad %6 %158
3006 %160 = OpAccessChain %7 %50 %216 %221 %224 %226
3007 OpStore %160 %159
3008 %164 = OpISub %6 %221 %224
3009 %171 = OpAccessChain %7 %50 %216 %221 %226 %224
3010 %172 = OpLoad %6 %171
3011 %173 = OpAccessChain %7 %50 %216 %164 %224 %226
3012 OpStore %173 %172
3013 %182 = OpAccessChain %7 %50 %226 %216 %221 %224
3014 %183 = OpLoad %6 %182
3015 %184 = OpAccessChain %7 %50 %216 %221 %224 %226
3016 OpStore %184 %183
3017 %193 = OpAccessChain %7 %50 %221 %216 %226 %224
3018 %194 = OpLoad %6 %193
3019 %195 = OpAccessChain %7 %50 %216 %221 %224 %226
3020 OpStore %195 %194
3021 %204 = OpAccessChain %7 %50 %224 %226 %216 %221
3022 %205 = OpLoad %6 %204
3023 %206 = OpAccessChain %7 %50 %216 %221 %224 %226
3024 OpStore %206 %205
3025 OpBranch %39
3026 %39 = OpLabel
3027 %209 = OpIAdd %6 %226 %208
3028 OpStore %35 %209
3029 OpBranch %36
3030 %38 = OpLabel
3031 OpBranch %31
3032 %31 = OpLabel
3033 %211 = OpIAdd %6 %224 %208
3034 OpStore %27 %211
3035 OpBranch %28
3036 %30 = OpLabel
3037 OpBranch %23
3038 %23 = OpLabel
3039 %213 = OpIAdd %6 %221 %208
3040 OpStore %19 %213
3041 OpBranch %20
3042 %22 = OpLabel
3043 OpBranch %13
3044 %13 = OpLabel
3045 %215 = OpIAdd %6 %216 %208
3046 OpStore %8 %215
3047 OpBranch %10
3048 %12 = OpLabel
3049 OpReturn
3050 OpFunctionEnd
3051 )";
3052
3053 std::unique_ptr<IRContext> context =
3054 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
3055 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
3056 Module* module = context->module();
3057 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
3058 << text << std::endl;
3059 const Function* f = spvtest::GetFunction(module, 4);
3060 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
3061
3062 std::vector<const Loop*> loop_nest{
3063 &ld.GetLoopByIndex(0), &ld.GetLoopByIndex(1), &ld.GetLoopByIndex(2),
3064 &ld.GetLoopByIndex(3)};
3065 LoopDependenceAnalysis analysis{context.get(), loop_nest};
3066
3067 const int instructions_expected = 13;
3068 const Instruction* store[instructions_expected];
3069 const Instruction* load[instructions_expected];
3070 int stores_found = 0;
3071 int loads_found = 0;
3072
3073 int block_id = 37;
3074 ASSERT_TRUE(spvtest::GetBasicBlock(f, block_id));
3075
3076 for (const Instruction& inst : *spvtest::GetBasicBlock(f, block_id)) {
3077 if (inst.opcode() == spv::Op::OpStore) {
3078 store[stores_found] = &inst;
3079 ++stores_found;
3080 }
3081
3082 if (inst.opcode() == spv::Op::OpLoad) {
3083 load[loads_found] = &inst;
3084 ++loads_found;
3085 }
3086 }
3087
3088 EXPECT_EQ(instructions_expected, stores_found);
3089 EXPECT_EQ(instructions_expected, loads_found);
3090
3091 PartitionSubscripts(load[0], store[0], &analysis, {{0}, {1}, {2}, {3}});
3092 PartitionSubscripts(load[1], store[1], &analysis, {{0}, {1}, {2, 3}});
3093 PartitionSubscripts(load[2], store[2], &analysis, {{0, 1}, {2}, {3}});
3094 PartitionSubscripts(load[3], store[3], &analysis, {{0, 3}, {1}, {2}});
3095 PartitionSubscripts(load[4], store[4], &analysis, {{0}, {1, 2}, {3}});
3096 PartitionSubscripts(load[5], store[5], &analysis, {{0, 1}, {2}, {3}});
3097 PartitionSubscripts(load[6], store[6], &analysis, {{0, 1, 2}, {3}});
3098 PartitionSubscripts(load[7], store[7], &analysis, {{0, 1, 2, 3}});
3099 PartitionSubscripts(load[8], store[8], &analysis, {{0}, {1, 2, 3}});
3100 PartitionSubscripts(load[9], store[9], &analysis, {{0}, {1, 2, 3}});
3101 PartitionSubscripts(load[10], store[10], &analysis, {{0, 1, 2, 3}});
3102 PartitionSubscripts(load[11], store[11], &analysis, {{0, 1}, {2, 3}});
3103 PartitionSubscripts(load[12], store[12], &analysis, {{0, 2}, {1, 3}});
3104 }
3105
3106 /*
3107 Generated from the following GLSL fragment shader
3108 with --eliminate-local-multi-store
3109
3110 #version 440 core
3111 void a() {
3112 int[10][10] arr;
3113 for (int i = 0; i < 10; ++i) {
3114 for (int j = 0; j < 10; ++j) {
3115 // Dependent, distance vector (1, -1)
3116 arr[i+1][i+j] = arr[i][i+j];
3117 }
3118 }
3119 }
3120
3121 void b() {
3122 int[10][10] arr;
3123 for (int i = 0; i < 10; ++i) {
3124 // Independent
3125 arr[i+1][i+2] = arr[i][i] + 2;
3126 }
3127 }
3128
3129 void c() {
3130 int[10][10] arr;
3131 for (int i = 0; i < 10; ++i) {
3132 // Dependence point (1,2)
3133 arr[i][i] = arr[1][i-1] + 2;
3134 }
3135 }
3136
3137 void d() {
3138 int[10][10][10] arr;
3139 for (int i = 0; i < 10; ++i) {
3140 for (int j = 0; j < 10; ++j) {
3141 for (int k = 0; k < 10; ++k) {
3142 // Dependent, distance vector (1,1,-1)
3143 arr[j-i][i+1][j+k] = arr[j-i][i][j+k];
3144 }
3145 }
3146 }
3147 }
3148
3149 void e() {
3150 int[10][10] arr;
3151 for (int i = 0; i < 10; ++i) {
3152 for (int j = 0; j < 10; ++j) {
3153 // Independent with GCD after propagation
3154 arr[i][2*j+i] = arr[i][2*j-i+5];
3155 }
3156 }
3157 }
3158
3159 void main(){
3160 a();
3161 b();
3162 c();
3163 d();
3164 e();
3165 }
3166 */
TEST(DependencyAnalysis,Delta)3167 TEST(DependencyAnalysis, Delta) {
3168 const std::string text = R"(
3169 OpCapability Shader
3170 %1 = OpExtInstImport "GLSL.std.450"
3171 OpMemoryModel Logical GLSL450
3172 OpEntryPoint Fragment %4 "main"
3173 OpExecutionMode %4 OriginUpperLeft
3174 OpSource GLSL 440
3175 OpName %4 "main"
3176 OpName %6 "a("
3177 OpName %8 "b("
3178 OpName %10 "c("
3179 OpName %12 "d("
3180 OpName %14 "e("
3181 OpName %18 "i"
3182 OpName %29 "j"
3183 OpName %42 "arr"
3184 OpName %60 "i"
3185 OpName %68 "arr"
3186 OpName %82 "i"
3187 OpName %90 "arr"
3188 OpName %101 "i"
3189 OpName %109 "j"
3190 OpName %117 "k"
3191 OpName %127 "arr"
3192 OpName %152 "i"
3193 OpName %160 "j"
3194 OpName %168 "arr"
3195 %2 = OpTypeVoid
3196 %3 = OpTypeFunction %2
3197 %16 = OpTypeInt 32 1
3198 %17 = OpTypePointer Function %16
3199 %19 = OpConstant %16 0
3200 %26 = OpConstant %16 10
3201 %27 = OpTypeBool
3202 %37 = OpTypeInt 32 0
3203 %38 = OpConstant %37 10
3204 %39 = OpTypeArray %16 %38
3205 %40 = OpTypeArray %39 %38
3206 %41 = OpTypePointer Function %40
3207 %44 = OpConstant %16 1
3208 %72 = OpConstant %16 2
3209 %125 = OpTypeArray %40 %38
3210 %126 = OpTypePointer Function %125
3211 %179 = OpConstant %16 5
3212 %4 = OpFunction %2 None %3
3213 %5 = OpLabel
3214 %188 = OpFunctionCall %2 %6
3215 %189 = OpFunctionCall %2 %8
3216 %190 = OpFunctionCall %2 %10
3217 %191 = OpFunctionCall %2 %12
3218 %192 = OpFunctionCall %2 %14
3219 OpReturn
3220 OpFunctionEnd
3221 %6 = OpFunction %2 None %3
3222 %7 = OpLabel
3223 %18 = OpVariable %17 Function
3224 %29 = OpVariable %17 Function
3225 %42 = OpVariable %41 Function
3226 OpStore %18 %19
3227 OpBranch %20
3228 %20 = OpLabel
3229 %193 = OpPhi %16 %19 %7 %59 %23
3230 OpLoopMerge %22 %23 None
3231 OpBranch %24
3232 %24 = OpLabel
3233 %28 = OpSLessThan %27 %193 %26
3234 OpBranchConditional %28 %21 %22
3235 %21 = OpLabel
3236 OpStore %29 %19
3237 OpBranch %30
3238 %30 = OpLabel
3239 %194 = OpPhi %16 %19 %21 %57 %33
3240 OpLoopMerge %32 %33 None
3241 OpBranch %34
3242 %34 = OpLabel
3243 %36 = OpSLessThan %27 %194 %26
3244 OpBranchConditional %36 %31 %32
3245 %31 = OpLabel
3246 %45 = OpIAdd %16 %193 %44
3247 %48 = OpIAdd %16 %193 %194
3248 %52 = OpIAdd %16 %193 %194
3249 %53 = OpAccessChain %17 %42 %193 %52
3250 %54 = OpLoad %16 %53
3251 %55 = OpAccessChain %17 %42 %45 %48
3252 OpStore %55 %54
3253 OpBranch %33
3254 %33 = OpLabel
3255 %57 = OpIAdd %16 %194 %44
3256 OpStore %29 %57
3257 OpBranch %30
3258 %32 = OpLabel
3259 OpBranch %23
3260 %23 = OpLabel
3261 %59 = OpIAdd %16 %193 %44
3262 OpStore %18 %59
3263 OpBranch %20
3264 %22 = OpLabel
3265 OpReturn
3266 OpFunctionEnd
3267 %8 = OpFunction %2 None %3
3268 %9 = OpLabel
3269 %60 = OpVariable %17 Function
3270 %68 = OpVariable %41 Function
3271 OpStore %60 %19
3272 OpBranch %61
3273 %61 = OpLabel
3274 %196 = OpPhi %16 %19 %9 %81 %64
3275 OpLoopMerge %63 %64 None
3276 OpBranch %65
3277 %65 = OpLabel
3278 %67 = OpSLessThan %27 %196 %26
3279 OpBranchConditional %67 %62 %63
3280 %62 = OpLabel
3281 %70 = OpIAdd %16 %196 %44
3282 %73 = OpIAdd %16 %196 %72
3283 %76 = OpAccessChain %17 %68 %196 %196
3284 %77 = OpLoad %16 %76
3285 %78 = OpIAdd %16 %77 %72
3286 %79 = OpAccessChain %17 %68 %70 %73
3287 OpStore %79 %78
3288 OpBranch %64
3289 %64 = OpLabel
3290 %81 = OpIAdd %16 %196 %44
3291 OpStore %60 %81
3292 OpBranch %61
3293 %63 = OpLabel
3294 OpReturn
3295 OpFunctionEnd
3296 %10 = OpFunction %2 None %3
3297 %11 = OpLabel
3298 %82 = OpVariable %17 Function
3299 %90 = OpVariable %41 Function
3300 OpStore %82 %19
3301 OpBranch %83
3302 %83 = OpLabel
3303 %197 = OpPhi %16 %19 %11 %100 %86
3304 OpLoopMerge %85 %86 None
3305 OpBranch %87
3306 %87 = OpLabel
3307 %89 = OpSLessThan %27 %197 %26
3308 OpBranchConditional %89 %84 %85
3309 %84 = OpLabel
3310 %94 = OpISub %16 %197 %44
3311 %95 = OpAccessChain %17 %90 %44 %94
3312 %96 = OpLoad %16 %95
3313 %97 = OpIAdd %16 %96 %72
3314 %98 = OpAccessChain %17 %90 %197 %197
3315 OpStore %98 %97
3316 OpBranch %86
3317 %86 = OpLabel
3318 %100 = OpIAdd %16 %197 %44
3319 OpStore %82 %100
3320 OpBranch %83
3321 %85 = OpLabel
3322 OpReturn
3323 OpFunctionEnd
3324 %12 = OpFunction %2 None %3
3325 %13 = OpLabel
3326 %101 = OpVariable %17 Function
3327 %109 = OpVariable %17 Function
3328 %117 = OpVariable %17 Function
3329 %127 = OpVariable %126 Function
3330 OpStore %101 %19
3331 OpBranch %102
3332 %102 = OpLabel
3333 %198 = OpPhi %16 %19 %13 %151 %105
3334 OpLoopMerge %104 %105 None
3335 OpBranch %106
3336 %106 = OpLabel
3337 %108 = OpSLessThan %27 %198 %26
3338 OpBranchConditional %108 %103 %104
3339 %103 = OpLabel
3340 OpStore %109 %19
3341 OpBranch %110
3342 %110 = OpLabel
3343 %199 = OpPhi %16 %19 %103 %149 %113
3344 OpLoopMerge %112 %113 None
3345 OpBranch %114
3346 %114 = OpLabel
3347 %116 = OpSLessThan %27 %199 %26
3348 OpBranchConditional %116 %111 %112
3349 %111 = OpLabel
3350 OpStore %117 %19
3351 OpBranch %118
3352 %118 = OpLabel
3353 %201 = OpPhi %16 %19 %111 %147 %121
3354 OpLoopMerge %120 %121 None
3355 OpBranch %122
3356 %122 = OpLabel
3357 %124 = OpSLessThan %27 %201 %26
3358 OpBranchConditional %124 %119 %120
3359 %119 = OpLabel
3360 %130 = OpISub %16 %199 %198
3361 %132 = OpIAdd %16 %198 %44
3362 %135 = OpIAdd %16 %199 %201
3363 %138 = OpISub %16 %199 %198
3364 %142 = OpIAdd %16 %199 %201
3365 %143 = OpAccessChain %17 %127 %138 %198 %142
3366 %144 = OpLoad %16 %143
3367 %145 = OpAccessChain %17 %127 %130 %132 %135
3368 OpStore %145 %144
3369 OpBranch %121
3370 %121 = OpLabel
3371 %147 = OpIAdd %16 %201 %44
3372 OpStore %117 %147
3373 OpBranch %118
3374 %120 = OpLabel
3375 OpBranch %113
3376 %113 = OpLabel
3377 %149 = OpIAdd %16 %199 %44
3378 OpStore %109 %149
3379 OpBranch %110
3380 %112 = OpLabel
3381 OpBranch %105
3382 %105 = OpLabel
3383 %151 = OpIAdd %16 %198 %44
3384 OpStore %101 %151
3385 OpBranch %102
3386 %104 = OpLabel
3387 OpReturn
3388 OpFunctionEnd
3389 %14 = OpFunction %2 None %3
3390 %15 = OpLabel
3391 %152 = OpVariable %17 Function
3392 %160 = OpVariable %17 Function
3393 %168 = OpVariable %41 Function
3394 OpStore %152 %19
3395 OpBranch %153
3396 %153 = OpLabel
3397 %204 = OpPhi %16 %19 %15 %187 %156
3398 OpLoopMerge %155 %156 None
3399 OpBranch %157
3400 %157 = OpLabel
3401 %159 = OpSLessThan %27 %204 %26
3402 OpBranchConditional %159 %154 %155
3403 %154 = OpLabel
3404 OpStore %160 %19
3405 OpBranch %161
3406 %161 = OpLabel
3407 %205 = OpPhi %16 %19 %154 %185 %164
3408 OpLoopMerge %163 %164 None
3409 OpBranch %165
3410 %165 = OpLabel
3411 %167 = OpSLessThan %27 %205 %26
3412 OpBranchConditional %167 %162 %163
3413 %162 = OpLabel
3414 %171 = OpIMul %16 %72 %205
3415 %173 = OpIAdd %16 %171 %204
3416 %176 = OpIMul %16 %72 %205
3417 %178 = OpISub %16 %176 %204
3418 %180 = OpIAdd %16 %178 %179
3419 %181 = OpAccessChain %17 %168 %204 %180
3420 %182 = OpLoad %16 %181
3421 %183 = OpAccessChain %17 %168 %204 %173
3422 OpStore %183 %182
3423 OpBranch %164
3424 %164 = OpLabel
3425 %185 = OpIAdd %16 %205 %44
3426 OpStore %160 %185
3427 OpBranch %161
3428 %163 = OpLabel
3429 OpBranch %156
3430 %156 = OpLabel
3431 %187 = OpIAdd %16 %204 %44
3432 OpStore %152 %187
3433 OpBranch %153
3434 %155 = OpLabel
3435 OpReturn
3436 OpFunctionEnd
3437 )";
3438
3439 std::unique_ptr<IRContext> context =
3440 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
3441 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
3442 ASSERT_NE(nullptr, context);
3443 Module* module = context->module();
3444 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
3445 << text << std::endl;
3446
3447 {
3448 const Function* f = spvtest::GetFunction(module, 6);
3449 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
3450
3451 const Instruction* store = nullptr;
3452 const Instruction* load = nullptr;
3453
3454 int block_id = 31;
3455 ASSERT_TRUE(spvtest::GetBasicBlock(f, block_id));
3456
3457 for (const Instruction& inst : *spvtest::GetBasicBlock(f, block_id)) {
3458 if (inst.opcode() == spv::Op::OpStore) {
3459 store = &inst;
3460 }
3461
3462 if (inst.opcode() == spv::Op::OpLoad) {
3463 load = &inst;
3464 }
3465 }
3466
3467 EXPECT_NE(nullptr, store);
3468 EXPECT_NE(nullptr, load);
3469
3470 std::vector<const Loop*> loop_nest{&ld.GetLoopByIndex(0),
3471 &ld.GetLoopByIndex(1)};
3472 LoopDependenceAnalysis analysis{context.get(), loop_nest};
3473
3474 DistanceVector dv_entry(loop_nest.size());
3475
3476 std::vector<DistanceEntry> expected_entries{
3477 DistanceEntry(DistanceEntry::Directions::LT, 1),
3478 DistanceEntry(DistanceEntry::Directions::LT, 1)};
3479
3480 DistanceVector expected_distance_vector(expected_entries);
3481
3482 auto is_independent = analysis.GetDependence(load, store, &dv_entry);
3483
3484 EXPECT_FALSE(is_independent);
3485 EXPECT_EQ(expected_distance_vector, dv_entry);
3486 }
3487
3488 {
3489 const Function* f = spvtest::GetFunction(module, 8);
3490 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
3491
3492 const Instruction* store = nullptr;
3493 const Instruction* load = nullptr;
3494
3495 int block_id = 62;
3496 ASSERT_TRUE(spvtest::GetBasicBlock(f, block_id));
3497
3498 for (const Instruction& inst : *spvtest::GetBasicBlock(f, block_id)) {
3499 if (inst.opcode() == spv::Op::OpStore) {
3500 store = &inst;
3501 }
3502
3503 if (inst.opcode() == spv::Op::OpLoad) {
3504 load = &inst;
3505 }
3506 }
3507
3508 EXPECT_NE(nullptr, store);
3509 EXPECT_NE(nullptr, load);
3510
3511 std::vector<const Loop*> loop_nest{&ld.GetLoopByIndex(0)};
3512 LoopDependenceAnalysis analysis{context.get(), loop_nest};
3513
3514 DistanceVector dv_entry(loop_nest.size());
3515 auto is_independent = analysis.GetDependence(load, store, &dv_entry);
3516
3517 EXPECT_TRUE(is_independent);
3518 }
3519
3520 {
3521 const Function* f = spvtest::GetFunction(module, 10);
3522 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
3523
3524 const Instruction* store = nullptr;
3525 const Instruction* load = nullptr;
3526
3527 int block_id = 84;
3528 ASSERT_TRUE(spvtest::GetBasicBlock(f, block_id));
3529
3530 for (const Instruction& inst : *spvtest::GetBasicBlock(f, block_id)) {
3531 if (inst.opcode() == spv::Op::OpStore) {
3532 store = &inst;
3533 }
3534
3535 if (inst.opcode() == spv::Op::OpLoad) {
3536 load = &inst;
3537 }
3538 }
3539
3540 EXPECT_NE(nullptr, store);
3541 EXPECT_NE(nullptr, load);
3542
3543 std::vector<const Loop*> loop_nest{&ld.GetLoopByIndex(0)};
3544 LoopDependenceAnalysis analysis{context.get(), loop_nest};
3545
3546 DistanceVector dv_entry(loop_nest.size());
3547 auto is_independent = analysis.GetDependence(load, store, &dv_entry);
3548
3549 DistanceVector expected_distance_vector({DistanceEntry(1, 2)});
3550
3551 EXPECT_FALSE(is_independent);
3552 EXPECT_EQ(expected_distance_vector, dv_entry);
3553 }
3554
3555 {
3556 const Function* f = spvtest::GetFunction(module, 12);
3557 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
3558
3559 const Instruction* store = nullptr;
3560 const Instruction* load = nullptr;
3561
3562 int block_id = 119;
3563 ASSERT_TRUE(spvtest::GetBasicBlock(f, block_id));
3564
3565 for (const Instruction& inst : *spvtest::GetBasicBlock(f, block_id)) {
3566 if (inst.opcode() == spv::Op::OpStore) {
3567 store = &inst;
3568 }
3569
3570 if (inst.opcode() == spv::Op::OpLoad) {
3571 load = &inst;
3572 }
3573 }
3574
3575 EXPECT_NE(nullptr, store);
3576 EXPECT_NE(nullptr, load);
3577
3578 std::vector<const Loop*> loop_nest{
3579 &ld.GetLoopByIndex(0), &ld.GetLoopByIndex(1), &ld.GetLoopByIndex(2)};
3580 LoopDependenceAnalysis analysis{context.get(), loop_nest};
3581
3582 DistanceVector dv_entry(loop_nest.size());
3583
3584 std::vector<DistanceEntry> expected_entries{
3585 DistanceEntry(DistanceEntry::Directions::LT, 1),
3586 DistanceEntry(DistanceEntry::Directions::LT, 1),
3587 DistanceEntry(DistanceEntry::Directions::GT, -1)};
3588
3589 DistanceVector expected_distance_vector(expected_entries);
3590
3591 auto is_independent = analysis.GetDependence(store, load, &dv_entry);
3592
3593 EXPECT_FALSE(is_independent);
3594 EXPECT_EQ(expected_distance_vector, dv_entry);
3595 }
3596
3597 {
3598 const Function* f = spvtest::GetFunction(module, 14);
3599 LoopDescriptor& ld = *context->GetLoopDescriptor(f);
3600
3601 const Instruction* store = nullptr;
3602 const Instruction* load = nullptr;
3603
3604 int block_id = 162;
3605 ASSERT_TRUE(spvtest::GetBasicBlock(f, block_id));
3606
3607 for (const Instruction& inst : *spvtest::GetBasicBlock(f, block_id)) {
3608 if (inst.opcode() == spv::Op::OpStore) {
3609 store = &inst;
3610 }
3611
3612 if (inst.opcode() == spv::Op::OpLoad) {
3613 load = &inst;
3614 }
3615 }
3616
3617 EXPECT_NE(nullptr, store);
3618 EXPECT_NE(nullptr, load);
3619
3620 std::vector<const Loop*> loop_nest{&ld.GetLoopByIndex(0),
3621 &ld.GetLoopByIndex(1)};
3622 LoopDependenceAnalysis analysis{context.get(), loop_nest};
3623
3624 DistanceVector dv_entry(loop_nest.size());
3625 auto is_independent = analysis.GetDependence(load, store, &dv_entry);
3626
3627 EXPECT_TRUE(is_independent);
3628 }
3629 }
3630
TEST(DependencyAnalysis,ConstraintIntersection)3631 TEST(DependencyAnalysis, ConstraintIntersection) {
3632 LoopDependenceAnalysis analysis{nullptr, std::vector<const Loop*>{}};
3633 auto scalar_evolution = analysis.GetScalarEvolution();
3634 {
3635 // One is none. Other should be returned
3636 auto none = analysis.make_constraint<DependenceNone>();
3637 auto x = scalar_evolution->CreateConstant(1);
3638 auto y = scalar_evolution->CreateConstant(10);
3639 auto point = analysis.make_constraint<DependencePoint>(x, y, nullptr);
3640
3641 auto ret_0 = analysis.IntersectConstraints(none, point, nullptr, nullptr);
3642
3643 auto ret_point_0 = ret_0->AsDependencePoint();
3644 ASSERT_NE(nullptr, ret_point_0);
3645 EXPECT_EQ(*x, *ret_point_0->GetSource());
3646 EXPECT_EQ(*y, *ret_point_0->GetDestination());
3647
3648 auto ret_1 = analysis.IntersectConstraints(point, none, nullptr, nullptr);
3649
3650 auto ret_point_1 = ret_1->AsDependencePoint();
3651 ASSERT_NE(nullptr, ret_point_1);
3652 EXPECT_EQ(*x, *ret_point_1->GetSource());
3653 EXPECT_EQ(*y, *ret_point_1->GetDestination());
3654 }
3655
3656 {
3657 // Both distances
3658 auto x = scalar_evolution->CreateConstant(1);
3659 auto y = scalar_evolution->CreateConstant(10);
3660
3661 auto distance_0 = analysis.make_constraint<DependenceDistance>(x, nullptr);
3662 auto distance_1 = analysis.make_constraint<DependenceDistance>(y, nullptr);
3663
3664 // Equal distances
3665 auto ret_0 =
3666 analysis.IntersectConstraints(distance_1, distance_1, nullptr, nullptr);
3667
3668 auto ret_distance = ret_0->AsDependenceDistance();
3669 ASSERT_NE(nullptr, ret_distance);
3670 EXPECT_EQ(*y, *ret_distance->GetDistance());
3671
3672 // Non-equal distances
3673 auto ret_1 =
3674 analysis.IntersectConstraints(distance_0, distance_1, nullptr, nullptr);
3675 EXPECT_NE(nullptr, ret_1->AsDependenceEmpty());
3676 }
3677
3678 {
3679 // Both points
3680 auto x = scalar_evolution->CreateConstant(1);
3681 auto y = scalar_evolution->CreateConstant(10);
3682
3683 auto point_0 = analysis.make_constraint<DependencePoint>(x, y, nullptr);
3684 auto point_1 = analysis.make_constraint<DependencePoint>(x, y, nullptr);
3685 auto point_2 = analysis.make_constraint<DependencePoint>(y, y, nullptr);
3686
3687 // Equal points
3688 auto ret_0 =
3689 analysis.IntersectConstraints(point_0, point_1, nullptr, nullptr);
3690 auto ret_point_0 = ret_0->AsDependencePoint();
3691 ASSERT_NE(nullptr, ret_point_0);
3692 EXPECT_EQ(*x, *ret_point_0->GetSource());
3693 EXPECT_EQ(*y, *ret_point_0->GetDestination());
3694
3695 // Non-equal points
3696 auto ret_1 =
3697 analysis.IntersectConstraints(point_0, point_2, nullptr, nullptr);
3698 EXPECT_NE(nullptr, ret_1->AsDependenceEmpty());
3699 }
3700
3701 {
3702 // Both lines, parallel
3703 auto a0 = scalar_evolution->CreateConstant(3);
3704 auto b0 = scalar_evolution->CreateConstant(6);
3705 auto c0 = scalar_evolution->CreateConstant(9);
3706
3707 auto a1 = scalar_evolution->CreateConstant(6);
3708 auto b1 = scalar_evolution->CreateConstant(12);
3709 auto c1 = scalar_evolution->CreateConstant(18);
3710
3711 auto line_0 = analysis.make_constraint<DependenceLine>(a0, b0, c0, nullptr);
3712 auto line_1 = analysis.make_constraint<DependenceLine>(a1, b1, c1, nullptr);
3713
3714 // Same line, both ways
3715 auto ret_0 =
3716 analysis.IntersectConstraints(line_0, line_1, nullptr, nullptr);
3717 auto ret_1 =
3718 analysis.IntersectConstraints(line_1, line_0, nullptr, nullptr);
3719
3720 auto ret_line_0 = ret_0->AsDependenceLine();
3721 auto ret_line_1 = ret_1->AsDependenceLine();
3722
3723 EXPECT_NE(nullptr, ret_line_0);
3724 EXPECT_NE(nullptr, ret_line_1);
3725
3726 // Non-intersecting parallel lines
3727 auto c2 = scalar_evolution->CreateConstant(12);
3728 auto line_2 = analysis.make_constraint<DependenceLine>(a1, b1, c2, nullptr);
3729
3730 auto ret_2 =
3731 analysis.IntersectConstraints(line_0, line_2, nullptr, nullptr);
3732 auto ret_3 =
3733 analysis.IntersectConstraints(line_2, line_0, nullptr, nullptr);
3734
3735 EXPECT_NE(nullptr, ret_2->AsDependenceEmpty());
3736 EXPECT_NE(nullptr, ret_3->AsDependenceEmpty());
3737
3738 auto c3 = scalar_evolution->CreateConstant(20);
3739 auto line_3 = analysis.make_constraint<DependenceLine>(a1, b1, c3, nullptr);
3740
3741 auto ret_4 =
3742 analysis.IntersectConstraints(line_0, line_3, nullptr, nullptr);
3743 auto ret_5 =
3744 analysis.IntersectConstraints(line_3, line_0, nullptr, nullptr);
3745
3746 EXPECT_NE(nullptr, ret_4->AsDependenceEmpty());
3747 EXPECT_NE(nullptr, ret_5->AsDependenceEmpty());
3748 }
3749
3750 {
3751 // Non-constant line
3752 auto unknown = scalar_evolution->CreateCantComputeNode();
3753 auto constant = scalar_evolution->CreateConstant(10);
3754
3755 auto line_0 = analysis.make_constraint<DependenceLine>(constant, constant,
3756 constant, nullptr);
3757 auto line_1 = analysis.make_constraint<DependenceLine>(unknown, unknown,
3758 unknown, nullptr);
3759
3760 auto ret_0 =
3761 analysis.IntersectConstraints(line_0, line_1, nullptr, nullptr);
3762 auto ret_1 =
3763 analysis.IntersectConstraints(line_1, line_0, nullptr, nullptr);
3764
3765 EXPECT_NE(nullptr, ret_0->AsDependenceNone());
3766 EXPECT_NE(nullptr, ret_1->AsDependenceNone());
3767 }
3768
3769 {
3770 auto bound_0 = scalar_evolution->CreateConstant(0);
3771 auto bound_1 = scalar_evolution->CreateConstant(20);
3772
3773 auto a0 = scalar_evolution->CreateConstant(1);
3774 auto b0 = scalar_evolution->CreateConstant(2);
3775 auto c0 = scalar_evolution->CreateConstant(6);
3776
3777 auto a1 = scalar_evolution->CreateConstant(-1);
3778 auto b1 = scalar_evolution->CreateConstant(2);
3779 auto c1 = scalar_evolution->CreateConstant(2);
3780
3781 auto line_0 = analysis.make_constraint<DependenceLine>(a0, b0, c0, nullptr);
3782 auto line_1 = analysis.make_constraint<DependenceLine>(a1, b1, c1, nullptr);
3783
3784 // Intersecting lines, has integer solution, in bounds
3785 auto ret_0 =
3786 analysis.IntersectConstraints(line_0, line_1, bound_0, bound_1);
3787 auto ret_1 =
3788 analysis.IntersectConstraints(line_1, line_0, bound_0, bound_1);
3789
3790 auto ret_point_0 = ret_0->AsDependencePoint();
3791 auto ret_point_1 = ret_1->AsDependencePoint();
3792
3793 EXPECT_NE(nullptr, ret_point_0);
3794 EXPECT_NE(nullptr, ret_point_1);
3795
3796 auto const_2 = scalar_evolution->CreateConstant(2);
3797
3798 EXPECT_EQ(*const_2, *ret_point_0->GetSource());
3799 EXPECT_EQ(*const_2, *ret_point_0->GetDestination());
3800
3801 EXPECT_EQ(*const_2, *ret_point_1->GetSource());
3802 EXPECT_EQ(*const_2, *ret_point_1->GetDestination());
3803
3804 // Intersecting lines, has integer solution, out of bounds
3805 auto ret_2 =
3806 analysis.IntersectConstraints(line_0, line_1, bound_0, bound_0);
3807 auto ret_3 =
3808 analysis.IntersectConstraints(line_1, line_0, bound_0, bound_0);
3809
3810 EXPECT_NE(nullptr, ret_2->AsDependenceEmpty());
3811 EXPECT_NE(nullptr, ret_3->AsDependenceEmpty());
3812
3813 auto a2 = scalar_evolution->CreateConstant(-4);
3814 auto b2 = scalar_evolution->CreateConstant(1);
3815 auto c2 = scalar_evolution->CreateConstant(0);
3816
3817 auto a3 = scalar_evolution->CreateConstant(4);
3818 auto b3 = scalar_evolution->CreateConstant(1);
3819 auto c3 = scalar_evolution->CreateConstant(4);
3820
3821 auto line_2 = analysis.make_constraint<DependenceLine>(a2, b2, c2, nullptr);
3822 auto line_3 = analysis.make_constraint<DependenceLine>(a3, b3, c3, nullptr);
3823
3824 // Intersecting, no integer solution
3825 auto ret_4 =
3826 analysis.IntersectConstraints(line_2, line_3, bound_0, bound_1);
3827 auto ret_5 =
3828 analysis.IntersectConstraints(line_3, line_2, bound_0, bound_1);
3829
3830 EXPECT_NE(nullptr, ret_4->AsDependenceEmpty());
3831 EXPECT_NE(nullptr, ret_5->AsDependenceEmpty());
3832
3833 auto unknown = scalar_evolution->CreateCantComputeNode();
3834
3835 // Non-constant bound
3836 auto ret_6 =
3837 analysis.IntersectConstraints(line_0, line_1, unknown, bound_1);
3838 auto ret_7 =
3839 analysis.IntersectConstraints(line_1, line_0, bound_0, unknown);
3840
3841 EXPECT_NE(nullptr, ret_6->AsDependenceNone());
3842 EXPECT_NE(nullptr, ret_7->AsDependenceNone());
3843 }
3844
3845 {
3846 auto constant_0 = scalar_evolution->CreateConstant(0);
3847 auto constant_1 = scalar_evolution->CreateConstant(1);
3848 auto constant_neg_1 = scalar_evolution->CreateConstant(-1);
3849 auto constant_2 = scalar_evolution->CreateConstant(2);
3850 auto constant_neg_2 = scalar_evolution->CreateConstant(-2);
3851
3852 auto point_0_0 = analysis.make_constraint<DependencePoint>(
3853 constant_0, constant_0, nullptr);
3854 auto point_0_1 = analysis.make_constraint<DependencePoint>(
3855 constant_0, constant_1, nullptr);
3856 auto point_1_0 = analysis.make_constraint<DependencePoint>(
3857 constant_1, constant_0, nullptr);
3858 auto point_1_1 = analysis.make_constraint<DependencePoint>(
3859 constant_1, constant_1, nullptr);
3860 auto point_1_2 = analysis.make_constraint<DependencePoint>(
3861 constant_1, constant_2, nullptr);
3862 auto point_1_neg_1 = analysis.make_constraint<DependencePoint>(
3863 constant_1, constant_neg_1, nullptr);
3864 auto point_neg_1_1 = analysis.make_constraint<DependencePoint>(
3865 constant_neg_1, constant_1, nullptr);
3866
3867 auto line_y_0 = analysis.make_constraint<DependenceLine>(
3868 constant_0, constant_1, constant_0, nullptr);
3869 auto line_y_1 = analysis.make_constraint<DependenceLine>(
3870 constant_0, constant_1, constant_1, nullptr);
3871 auto line_y_2 = analysis.make_constraint<DependenceLine>(
3872 constant_0, constant_1, constant_2, nullptr);
3873
3874 // Parallel horizontal lines, y = 0 & y = 1, should return no intersection
3875 auto ret =
3876 analysis.IntersectConstraints(line_y_0, line_y_1, nullptr, nullptr);
3877
3878 EXPECT_NE(nullptr, ret->AsDependenceEmpty());
3879
3880 // Parallel horizontal lines, y = 1 & y = 2, should return no intersection
3881 auto ret_y_12 =
3882 analysis.IntersectConstraints(line_y_1, line_y_2, nullptr, nullptr);
3883
3884 EXPECT_NE(nullptr, ret_y_12->AsDependenceEmpty());
3885
3886 // Same horizontal lines, y = 0 & y = 0, should return the line
3887 auto ret_y_same_0 =
3888 analysis.IntersectConstraints(line_y_0, line_y_0, nullptr, nullptr);
3889
3890 EXPECT_NE(nullptr, ret_y_same_0->AsDependenceLine());
3891
3892 // Same horizontal lines, y = 1 & y = 1, should return the line
3893 auto ret_y_same_1 =
3894 analysis.IntersectConstraints(line_y_1, line_y_1, nullptr, nullptr);
3895
3896 EXPECT_NE(nullptr, ret_y_same_1->AsDependenceLine());
3897
3898 auto line_x_0 = analysis.make_constraint<DependenceLine>(
3899 constant_1, constant_0, constant_0, nullptr);
3900 auto line_x_1 = analysis.make_constraint<DependenceLine>(
3901 constant_1, constant_0, constant_1, nullptr);
3902 auto line_x_2 = analysis.make_constraint<DependenceLine>(
3903 constant_1, constant_0, constant_2, nullptr);
3904 auto line_2x_1 = analysis.make_constraint<DependenceLine>(
3905 constant_2, constant_0, constant_1, nullptr);
3906 auto line_2x_2 = analysis.make_constraint<DependenceLine>(
3907 constant_2, constant_0, constant_2, nullptr);
3908
3909 // Parallel vertical lines, x = 0 & x = 1, should return no intersection
3910 auto ret_x =
3911 analysis.IntersectConstraints(line_x_0, line_x_1, nullptr, nullptr);
3912
3913 EXPECT_NE(nullptr, ret_x->AsDependenceEmpty());
3914
3915 // Parallel vertical lines, x = 1 & x = 2, should return no intersection
3916 auto ret_x_12 =
3917 analysis.IntersectConstraints(line_x_1, line_x_2, nullptr, nullptr);
3918
3919 EXPECT_NE(nullptr, ret_x_12->AsDependenceEmpty());
3920
3921 // Parallel vertical lines, 2x = 1 & 2x = 2, should return no intersection
3922 auto ret_2x_2_2x_1 =
3923 analysis.IntersectConstraints(line_2x_2, line_2x_1, nullptr, nullptr);
3924
3925 EXPECT_NE(nullptr, ret_2x_2_2x_1->AsDependenceEmpty());
3926
3927 // same line, 2x=2 & x = 1
3928 auto ret_2x_2_x_1 =
3929 analysis.IntersectConstraints(line_2x_2, line_x_1, nullptr, nullptr);
3930
3931 EXPECT_NE(nullptr, ret_2x_2_x_1->AsDependenceLine());
3932
3933 // Same vertical lines, x = 0 & x = 0, should return the line
3934 auto ret_x_same_0 =
3935 analysis.IntersectConstraints(line_x_0, line_x_0, nullptr, nullptr);
3936
3937 EXPECT_NE(nullptr, ret_x_same_0->AsDependenceLine());
3938 // EXPECT_EQ(*line_x_0, *ret_x_same_0->AsDependenceLine());
3939
3940 // Same vertical lines, x = 1 & x = 1, should return the line
3941 auto ret_x_same_1 =
3942 analysis.IntersectConstraints(line_x_1, line_x_1, nullptr, nullptr);
3943
3944 EXPECT_NE(nullptr, ret_x_same_1->AsDependenceLine());
3945 EXPECT_EQ(*line_x_1, *ret_x_same_1->AsDependenceLine());
3946
3947 // x=1 & y = 0, intersect at (1, 0)
3948 auto ret_1_0 = analysis.IntersectConstraints(line_x_1, line_y_0,
3949 constant_neg_1, constant_2);
3950
3951 auto ret_point_1_0 = ret_1_0->AsDependencePoint();
3952 EXPECT_NE(nullptr, ret_point_1_0);
3953 EXPECT_EQ(*point_1_0, *ret_point_1_0);
3954
3955 // x=1 & y = 1, intersect at (1, 1)
3956 auto ret_1_1 = analysis.IntersectConstraints(line_x_1, line_y_1,
3957 constant_neg_1, constant_2);
3958
3959 auto ret_point_1_1 = ret_1_1->AsDependencePoint();
3960 EXPECT_NE(nullptr, ret_point_1_1);
3961 EXPECT_EQ(*point_1_1, *ret_point_1_1);
3962
3963 // x=0 & y = 0, intersect at (0, 0)
3964 auto ret_0_0 = analysis.IntersectConstraints(line_x_0, line_y_0,
3965 constant_neg_1, constant_2);
3966
3967 auto ret_point_0_0 = ret_0_0->AsDependencePoint();
3968 EXPECT_NE(nullptr, ret_point_0_0);
3969 EXPECT_EQ(*point_0_0, *ret_point_0_0);
3970
3971 // x=0 & y = 1, intersect at (0, 1)
3972 auto ret_0_1 = analysis.IntersectConstraints(line_x_0, line_y_1,
3973 constant_neg_1, constant_2);
3974 auto ret_point_0_1 = ret_0_1->AsDependencePoint();
3975 EXPECT_NE(nullptr, ret_point_0_1);
3976 EXPECT_EQ(*point_0_1, *ret_point_0_1);
3977
3978 // x = 1 & y = 2
3979 auto ret_1_2 = analysis.IntersectConstraints(line_x_1, line_y_2,
3980 constant_neg_1, constant_2);
3981 auto ret_point_1_2 = ret_1_2->AsDependencePoint();
3982 EXPECT_NE(nullptr, ret_point_1_2);
3983 EXPECT_EQ(*point_1_2, *ret_point_1_2);
3984
3985 auto line_x_y_0 = analysis.make_constraint<DependenceLine>(
3986 constant_1, constant_1, constant_0, nullptr);
3987 auto line_x_y_1 = analysis.make_constraint<DependenceLine>(
3988 constant_1, constant_1, constant_1, nullptr);
3989
3990 // x+y=0 & x=0, intersect (0, 0)
3991 auto ret_xy_0_x_0 = analysis.IntersectConstraints(
3992 line_x_y_0, line_x_0, constant_neg_1, constant_2);
3993
3994 EXPECT_NE(nullptr, ret_xy_0_x_0->AsDependencePoint());
3995 EXPECT_EQ(*point_0_0, *ret_xy_0_x_0);
3996
3997 // x+y=0 & y=0, intersect (0, 0)
3998 auto ret_xy_0_y_0 = analysis.IntersectConstraints(
3999 line_x_y_0, line_y_0, constant_neg_1, constant_2);
4000
4001 EXPECT_NE(nullptr, ret_xy_0_y_0->AsDependencePoint());
4002 EXPECT_EQ(*point_0_0, *ret_xy_0_y_0);
4003
4004 // x+y=0 & x=1, intersect (1, -1)
4005 auto ret_xy_0_x_1 = analysis.IntersectConstraints(
4006 line_x_y_0, line_x_1, constant_neg_2, constant_2);
4007
4008 EXPECT_NE(nullptr, ret_xy_0_x_1->AsDependencePoint());
4009 EXPECT_EQ(*point_1_neg_1, *ret_xy_0_x_1);
4010
4011 // x+y=0 & y=1, intersect (-1, 1)
4012 auto ret_xy_0_y_1 = analysis.IntersectConstraints(
4013 line_x_y_0, line_y_1, constant_neg_2, constant_2);
4014
4015 EXPECT_NE(nullptr, ret_xy_0_y_1->AsDependencePoint());
4016 EXPECT_EQ(*point_neg_1_1, *ret_xy_0_y_1);
4017
4018 // x=0 & x+y=0, intersect (0, 0)
4019 auto ret_x_0_xy_0 = analysis.IntersectConstraints(
4020 line_x_0, line_x_y_0, constant_neg_1, constant_2);
4021
4022 EXPECT_NE(nullptr, ret_x_0_xy_0->AsDependencePoint());
4023 EXPECT_EQ(*point_0_0, *ret_x_0_xy_0);
4024
4025 // y=0 & x+y=0, intersect (0, 0)
4026 auto ret_y_0_xy_0 = analysis.IntersectConstraints(
4027 line_y_0, line_x_y_0, constant_neg_1, constant_2);
4028
4029 EXPECT_NE(nullptr, ret_y_0_xy_0->AsDependencePoint());
4030 EXPECT_EQ(*point_0_0, *ret_y_0_xy_0);
4031
4032 // x=1 & x+y=0, intersect (1, -1)
4033 auto ret_x_1_xy_0 = analysis.IntersectConstraints(
4034 line_x_1, line_x_y_0, constant_neg_2, constant_2);
4035
4036 EXPECT_NE(nullptr, ret_x_1_xy_0->AsDependencePoint());
4037 EXPECT_EQ(*point_1_neg_1, *ret_x_1_xy_0);
4038
4039 // y=1 & x+y=0, intersect (-1, 1)
4040 auto ret_y_1_xy_0 = analysis.IntersectConstraints(
4041 line_y_1, line_x_y_0, constant_neg_2, constant_2);
4042
4043 EXPECT_NE(nullptr, ret_y_1_xy_0->AsDependencePoint());
4044 EXPECT_EQ(*point_neg_1_1, *ret_y_1_xy_0);
4045
4046 // x+y=1 & x=0, intersect (0, 1)
4047 auto ret_xy_1_x_0 = analysis.IntersectConstraints(
4048 line_x_y_1, line_x_0, constant_neg_1, constant_2);
4049
4050 EXPECT_NE(nullptr, ret_xy_1_x_0->AsDependencePoint());
4051 EXPECT_EQ(*point_0_1, *ret_xy_1_x_0);
4052
4053 // x+y=1 & y=0, intersect (1, 0)
4054 auto ret_xy_1_y_0 = analysis.IntersectConstraints(
4055 line_x_y_1, line_y_0, constant_neg_1, constant_2);
4056
4057 EXPECT_NE(nullptr, ret_xy_1_y_0->AsDependencePoint());
4058 EXPECT_EQ(*point_1_0, *ret_xy_1_y_0);
4059
4060 // x+y=1 & x=1, intersect (1, 0)
4061 auto ret_xy_1_x_1 = analysis.IntersectConstraints(
4062 line_x_y_1, line_x_1, constant_neg_1, constant_2);
4063
4064 EXPECT_NE(nullptr, ret_xy_1_x_1->AsDependencePoint());
4065 EXPECT_EQ(*point_1_0, *ret_xy_1_x_1);
4066
4067 // x+y=1 & y=1, intersect (0, 1)
4068 auto ret_xy_1_y_1 = analysis.IntersectConstraints(
4069 line_x_y_1, line_y_1, constant_neg_1, constant_2);
4070
4071 EXPECT_NE(nullptr, ret_xy_1_y_1->AsDependencePoint());
4072 EXPECT_EQ(*point_0_1, *ret_xy_1_y_1);
4073
4074 // x=0 & x+y=1, intersect (0, 1)
4075 auto ret_x_0_xy_1 = analysis.IntersectConstraints(
4076 line_x_0, line_x_y_1, constant_neg_1, constant_2);
4077
4078 EXPECT_NE(nullptr, ret_x_0_xy_1->AsDependencePoint());
4079 EXPECT_EQ(*point_0_1, *ret_x_0_xy_1);
4080
4081 // y=0 & x+y=1, intersect (1, 0)
4082 auto ret_y_0_xy_1 = analysis.IntersectConstraints(
4083 line_y_0, line_x_y_1, constant_neg_1, constant_2);
4084
4085 EXPECT_NE(nullptr, ret_y_0_xy_1->AsDependencePoint());
4086 EXPECT_EQ(*point_1_0, *ret_y_0_xy_1);
4087
4088 // x=1 & x+y=1, intersect (1, 0)
4089 auto ret_x_1_xy_1 = analysis.IntersectConstraints(
4090 line_x_1, line_x_y_1, constant_neg_2, constant_2);
4091
4092 EXPECT_NE(nullptr, ret_x_1_xy_1->AsDependencePoint());
4093 EXPECT_EQ(*point_1_0, *ret_x_1_xy_1);
4094
4095 // y=1 & x+y=1, intersect (0, 1)
4096 auto ret_y_1_xy_1 = analysis.IntersectConstraints(
4097 line_y_1, line_x_y_1, constant_neg_2, constant_2);
4098
4099 EXPECT_NE(nullptr, ret_y_1_xy_1->AsDependencePoint());
4100 EXPECT_EQ(*point_0_1, *ret_y_1_xy_1);
4101 }
4102
4103 {
4104 // Line and point
4105 auto a = scalar_evolution->CreateConstant(3);
4106 auto b = scalar_evolution->CreateConstant(10);
4107 auto c = scalar_evolution->CreateConstant(16);
4108
4109 auto line = analysis.make_constraint<DependenceLine>(a, b, c, nullptr);
4110
4111 // Point on line
4112 auto x = scalar_evolution->CreateConstant(2);
4113 auto y = scalar_evolution->CreateConstant(1);
4114 auto point_0 = analysis.make_constraint<DependencePoint>(x, y, nullptr);
4115
4116 auto ret_0 = analysis.IntersectConstraints(line, point_0, nullptr, nullptr);
4117 auto ret_1 = analysis.IntersectConstraints(point_0, line, nullptr, nullptr);
4118
4119 auto ret_point_0 = ret_0->AsDependencePoint();
4120 auto ret_point_1 = ret_1->AsDependencePoint();
4121 ASSERT_NE(nullptr, ret_point_0);
4122 ASSERT_NE(nullptr, ret_point_1);
4123
4124 EXPECT_EQ(*x, *ret_point_0->GetSource());
4125 EXPECT_EQ(*y, *ret_point_0->GetDestination());
4126
4127 EXPECT_EQ(*x, *ret_point_1->GetSource());
4128 EXPECT_EQ(*y, *ret_point_1->GetDestination());
4129
4130 // Point not on line
4131 auto point_1 = analysis.make_constraint<DependencePoint>(a, a, nullptr);
4132
4133 auto ret_2 = analysis.IntersectConstraints(line, point_1, nullptr, nullptr);
4134 auto ret_3 = analysis.IntersectConstraints(point_1, line, nullptr, nullptr);
4135
4136 EXPECT_NE(nullptr, ret_2->AsDependenceEmpty());
4137 EXPECT_NE(nullptr, ret_3->AsDependenceEmpty());
4138
4139 // Non-constant
4140 auto unknown = scalar_evolution->CreateCantComputeNode();
4141
4142 auto point_2 =
4143 analysis.make_constraint<DependencePoint>(unknown, x, nullptr);
4144
4145 auto ret_4 = analysis.IntersectConstraints(line, point_2, nullptr, nullptr);
4146 auto ret_5 = analysis.IntersectConstraints(point_2, line, nullptr, nullptr);
4147
4148 EXPECT_NE(nullptr, ret_4->AsDependenceNone());
4149 EXPECT_NE(nullptr, ret_5->AsDependenceNone());
4150 }
4151
4152 {
4153 // Distance and point
4154 auto d = scalar_evolution->CreateConstant(5);
4155 auto distance = analysis.make_constraint<DependenceDistance>(d, nullptr);
4156
4157 // Point on line
4158 auto x = scalar_evolution->CreateConstant(10);
4159 auto point_0 = analysis.make_constraint<DependencePoint>(d, x, nullptr);
4160
4161 auto ret_0 =
4162 analysis.IntersectConstraints(distance, point_0, nullptr, nullptr);
4163 auto ret_1 =
4164 analysis.IntersectConstraints(point_0, distance, nullptr, nullptr);
4165
4166 auto ret_point_0 = ret_0->AsDependencePoint();
4167 auto ret_point_1 = ret_1->AsDependencePoint();
4168 ASSERT_NE(nullptr, ret_point_0);
4169 ASSERT_NE(nullptr, ret_point_1);
4170
4171 // Point not on line
4172 auto point_1 = analysis.make_constraint<DependencePoint>(x, x, nullptr);
4173
4174 auto ret_2 =
4175 analysis.IntersectConstraints(distance, point_1, nullptr, nullptr);
4176 auto ret_3 =
4177 analysis.IntersectConstraints(point_1, distance, nullptr, nullptr);
4178
4179 EXPECT_NE(nullptr, ret_2->AsDependenceEmpty());
4180 EXPECT_NE(nullptr, ret_3->AsDependenceEmpty());
4181
4182 // Non-constant
4183 auto unknown = scalar_evolution->CreateCantComputeNode();
4184 auto unknown_distance =
4185 analysis.make_constraint<DependenceDistance>(unknown, nullptr);
4186
4187 auto ret_4 = analysis.IntersectConstraints(unknown_distance, point_1,
4188 nullptr, nullptr);
4189 auto ret_5 = analysis.IntersectConstraints(point_1, unknown_distance,
4190 nullptr, nullptr);
4191
4192 EXPECT_NE(nullptr, ret_4->AsDependenceNone());
4193 EXPECT_NE(nullptr, ret_5->AsDependenceNone());
4194 }
4195 }
4196
4197 } // namespace
4198 } // namespace opt
4199 } // namespace spvtools
4200