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