1 // Copyright (c) 2021 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 "source/lint/divergence_analysis.h"
16
17 #include <string>
18
19 #include "gtest/gtest.h"
20 #include "source/opt/build_module.h"
21 #include "source/opt/ir_context.h"
22 #include "source/opt/module.h"
23 #include "spirv-tools/libspirv.h"
24
25 namespace spvtools {
26 namespace lint {
27 namespace {
28
CLIMessageConsumer(spv_message_level_t level,const char *,const spv_position_t & position,const char * message)29 void CLIMessageConsumer(spv_message_level_t level, const char*,
30 const spv_position_t& position, const char* message) {
31 switch (level) {
32 case SPV_MSG_FATAL:
33 case SPV_MSG_INTERNAL_ERROR:
34 case SPV_MSG_ERROR:
35 std::cerr << "error: line " << position.index << ": " << message
36 << std::endl;
37 break;
38 case SPV_MSG_WARNING:
39 std::cout << "warning: line " << position.index << ": " << message
40 << std::endl;
41 break;
42 case SPV_MSG_INFO:
43 std::cout << "info: line " << position.index << ": " << message
44 << std::endl;
45 break;
46 default:
47 break;
48 }
49 }
50
51 class DivergenceTest : public ::testing::Test {
52 protected:
53 std::unique_ptr<opt::IRContext> context_;
54 std::unique_ptr<DivergenceAnalysis> divergence_;
55
Build(std::string text,uint32_t function_id=1)56 void Build(std::string text, uint32_t function_id = 1) {
57 context_ = BuildModule(SPV_ENV_UNIVERSAL_1_0, CLIMessageConsumer, text,
58 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
59 ASSERT_NE(nullptr, context_.get());
60 opt::Module* module = context_->module();
61 ASSERT_NE(nullptr, module);
62 // First function should have the given ID.
63 ASSERT_NE(module->begin(), module->end());
64 opt::Function* function = &*module->begin();
65 ASSERT_EQ(function->result_id(), function_id);
66 divergence_.reset(new DivergenceAnalysis(*context_));
67 divergence_->Run(function);
68 }
69 };
70
71 // Makes assertions a bit shorter.
72 using Level = DivergenceAnalysis::DivergenceLevel;
73
74 namespace {
Preamble()75 std::string Preamble() {
76 return R"(
77 OpCapability Shader
78 OpMemoryModel Logical GLSL450
79 OpEntryPoint Fragment %1 "main" %x %y
80 OpExecutionMode %1 OriginLowerLeft
81 OpDecorate %y Flat
82 %void = OpTypeVoid
83 %void_f = OpTypeFunction %void
84 %bool = OpTypeBool
85 %float = OpTypeFloat 32
86 %false = OpConstantFalse %bool
87 %true = OpConstantTrue %bool
88 %zero = OpConstant %float 0
89 %one = OpConstant %float 1
90 %x_t = OpTypePointer Input %float
91 %x = OpVariable %x_t Input
92 %y = OpVariable %x_t Input
93 %1 = OpFunction %void None %void_f
94 )";
95 }
96 } // namespace
97
TEST_F(DivergenceTest,SimpleTest)98 TEST_F(DivergenceTest, SimpleTest) {
99 // pseudocode:
100 // %10:
101 // %11 = load x
102 // if (%12 = (%11 < 0)) {
103 // %13:
104 // // do nothing
105 // }
106 // %14:
107 // return
108 ASSERT_NO_FATAL_FAILURE(Build(Preamble() + R"(
109 %10 = OpLabel
110 %11 = OpLoad %float %x
111 %12 = OpFOrdLessThan %bool %11 %zero
112 OpSelectionMerge %14 None
113 OpBranchConditional %12 %13 %14
114 %13 = OpLabel
115 OpBranch %14
116 %14 = OpLabel
117 OpReturn
118 OpFunctionEnd
119 )"));
120 // Control flow divergence.
121 EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(10));
122 EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(13));
123 EXPECT_EQ(12, divergence_->GetDivergenceSource(13));
124 EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(14));
125 // Value divergence.
126 EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(11));
127 EXPECT_EQ(0, divergence_->GetDivergenceSource(11));
128 EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(12));
129 EXPECT_EQ(11, divergence_->GetDivergenceSource(12));
130 }
131
TEST_F(DivergenceTest,FlowTypesTest)132 TEST_F(DivergenceTest, FlowTypesTest) {
133 // pseudocode:
134 // %10:
135 // %11 = load x
136 // %12 = x < 0 // data -> data
137 // if (%12) {
138 // %13: // data -> control
139 // if (true) {
140 // %14: // control -> control
141 // }
142 // %15:
143 // %16 = 1
144 // } else {
145 // %17:
146 // %18 = 2
147 // }
148 // %19:
149 // %19 = phi(%16 from %15, %18 from %17) // control -> data
150 // return
151 ASSERT_NO_FATAL_FAILURE(Build(Preamble() + R"(
152 %10 = OpLabel
153 %11 = OpLoad %float %x
154 %12 = OpFOrdLessThan %bool %11 %zero
155 OpSelectionMerge %19 None
156 OpBranchConditional %12 %13 %17
157 %13 = OpLabel
158 OpSelectionMerge %15 None
159 OpBranchConditional %true %14 %15
160 %14 = OpLabel
161 OpBranch %15
162 %15 = OpLabel
163 %16 = OpFAdd %float %zero %zero
164 OpBranch %19
165 %17 = OpLabel
166 %18 = OpFAdd %float %zero %one
167 OpBranch %19
168 %19 = OpLabel
169 %20 = OpPhi %float %16 %15 %18 %17
170 OpReturn
171 OpFunctionEnd
172 )"));
173 EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(10));
174
175 EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(11));
176 EXPECT_EQ(0, divergence_->GetDivergenceSource(11));
177
178 EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(12));
179 EXPECT_EQ(11, divergence_->GetDivergenceSource(12));
180
181 EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(13));
182 EXPECT_EQ(12, divergence_->GetDivergenceSource(13));
183 EXPECT_EQ(10, divergence_->GetDivergenceDependenceSource(13));
184
185 EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(14));
186 EXPECT_EQ(13, divergence_->GetDivergenceSource(14));
187
188 EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(15));
189 EXPECT_EQ(12, divergence_->GetDivergenceSource(15));
190 EXPECT_EQ(10, divergence_->GetDivergenceDependenceSource(15));
191
192 EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(16));
193
194 EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(17));
195 EXPECT_EQ(12, divergence_->GetDivergenceSource(17));
196 EXPECT_EQ(10, divergence_->GetDivergenceDependenceSource(17));
197
198 EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(18));
199
200 EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(19));
201
202 EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(20));
203 EXPECT_TRUE(divergence_->GetDivergenceSource(20) == 15 ||
204 divergence_->GetDivergenceDependenceSource(20) == 17)
205 << "Got: " << divergence_->GetDivergenceDependenceSource(20);
206 }
207
TEST_F(DivergenceTest,ExitDependenceTest)208 TEST_F(DivergenceTest, ExitDependenceTest) {
209 // pseudocode:
210 // %10:
211 // %11 = load x
212 // %12 = %11 < 0
213 // %13:
214 // do {
215 // %14:
216 // if (%12) {
217 // %15:
218 // continue;
219 // }
220 // %16:
221 // %17:
222 // continue;
223 // } %18: while(false);
224 // %19:
225 // return
226 ASSERT_NO_FATAL_FAILURE(Build(Preamble() + R"(
227 %10 = OpLabel
228 %11 = OpLoad %float %x
229 %12 = OpFOrdLessThan %bool %11 %zero ; data -> data
230 OpBranch %13
231 %13 = OpLabel
232 OpLoopMerge %19 %18 None
233 OpBranch %14
234 %14 = OpLabel
235 OpSelectionMerge %16 None
236 OpBranchConditional %12 %15 %16
237 %15 = OpLabel
238 OpBranch %18 ; continue
239 %16 = OpLabel
240 OpBranch %17
241 %17 = OpLabel
242 OpBranch %18 ; continue
243 %18 = OpLabel
244 OpBranchConditional %false %13 %19
245 %19 = OpLabel
246 OpReturn
247 OpFunctionEnd
248 )"));
249
250 EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(10));
251
252 EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(11));
253 EXPECT_EQ(0, divergence_->GetDivergenceSource(11));
254
255 EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(12));
256 EXPECT_EQ(11, divergence_->GetDivergenceSource(12));
257
258 // Since both branches continue, there's no divergent control dependence
259 // to 13.
260 EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(13));
261
262 EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(14));
263
264 EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(15));
265 EXPECT_EQ(12, divergence_->GetDivergenceSource(15));
266 EXPECT_EQ(14, divergence_->GetDivergenceDependenceSource(15));
267
268 // These two blocks are outside the if but are still control dependent.
269 EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(16));
270 EXPECT_EQ(12, divergence_->GetDivergenceSource(16));
271 EXPECT_EQ(14, divergence_->GetDivergenceDependenceSource(16));
272 EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(17));
273 EXPECT_EQ(12, divergence_->GetDivergenceSource(17));
274 EXPECT_EQ(14, divergence_->GetDivergenceDependenceSource(17));
275
276 EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(18));
277
278 EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(19));
279 }
280
TEST_F(DivergenceTest,ReconvergencePromotionTest)281 TEST_F(DivergenceTest, ReconvergencePromotionTest) {
282 // pseudocode:
283 // %10:
284 // %11 = load y
285 // %12 = %11 < 0
286 // if (%12) {
287 // %13:
288 // %14:
289 // %15:
290 // if (true) {
291 // %16:
292 // }
293 // // Reconvergence *not* guaranteed as
294 // // control is not uniform on the IG level
295 // // at %15.
296 // %17:
297 // %18:
298 // %19:
299 // %20 = load x
300 // }
301 // %21:
302 // %22 = phi(%11, %20)
303 // return
304 ASSERT_NO_FATAL_FAILURE(Build(Preamble() + R"(
305 %10 = OpLabel
306 %11 = OpLoad %float %y
307 %12 = OpFOrdLessThan %bool %11 %zero
308 OpSelectionMerge %21 None
309 OpBranchConditional %12 %13 %21
310 %13 = OpLabel
311 OpBranch %14
312 %14 = OpLabel
313 OpBranch %15
314 %15 = OpLabel
315 OpSelectionMerge %17 None
316 OpBranchConditional %true %16 %17
317 %16 = OpLabel
318 OpBranch %17
319 %17 = OpLabel
320 OpBranch %18
321 %18 = OpLabel
322 OpBranch %19
323 %19 = OpLabel
324 %20 = OpLoad %float %y
325 OpBranch %21
326 %21 = OpLabel
327 %22 = OpPhi %float %11 %10 %20 %19
328 OpReturn
329 OpFunctionEnd
330 )"));
331 ASSERT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(10));
332 ASSERT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(21));
333
334 ASSERT_EQ(Level::kPartiallyUniform, divergence_->GetDivergenceLevel(11));
335 ASSERT_EQ(0, divergence_->GetDivergenceSource(11));
336 ASSERT_EQ(Level::kPartiallyUniform, divergence_->GetDivergenceLevel(12));
337 ASSERT_EQ(11, divergence_->GetDivergenceSource(12));
338 ASSERT_EQ(Level::kPartiallyUniform, divergence_->GetDivergenceLevel(13));
339 ASSERT_EQ(12, divergence_->GetDivergenceSource(13));
340 ASSERT_EQ(10, divergence_->GetDivergenceDependenceSource(13));
341 ASSERT_EQ(Level::kPartiallyUniform, divergence_->GetDivergenceLevel(14));
342 ASSERT_EQ(12, divergence_->GetDivergenceSource(14));
343 ASSERT_EQ(10, divergence_->GetDivergenceDependenceSource(14));
344 ASSERT_EQ(Level::kPartiallyUniform, divergence_->GetDivergenceLevel(15));
345 ASSERT_EQ(12, divergence_->GetDivergenceSource(15));
346 ASSERT_EQ(10, divergence_->GetDivergenceDependenceSource(15));
347 ASSERT_EQ(Level::kPartiallyUniform, divergence_->GetDivergenceLevel(16));
348 ASSERT_EQ(15, divergence_->GetDivergenceSource(16));
349
350 ASSERT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(17));
351 ASSERT_EQ(12, divergence_->GetDivergenceSource(17));
352 ASSERT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(18));
353 ASSERT_EQ(12, divergence_->GetDivergenceSource(18));
354 ASSERT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(19));
355 ASSERT_EQ(12, divergence_->GetDivergenceSource(19));
356
357 ASSERT_EQ(Level::kPartiallyUniform, divergence_->GetDivergenceLevel(20));
358 ASSERT_EQ(0, divergence_->GetDivergenceSource(20));
359 ASSERT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(22));
360 ASSERT_EQ(19, divergence_->GetDivergenceSource(22));
361 ASSERT_EQ(10, divergence_->GetDivergenceDependenceSource(15));
362 }
363
TEST_F(DivergenceTest,FunctionCallTest)364 TEST_F(DivergenceTest, FunctionCallTest) {
365 // pseudocode:
366 // %2() {
367 // %20:
368 // %21 = load x
369 // %22 = %21 < 0
370 // if (%22) {
371 // %23:
372 // return
373 // }
374 // %24:
375 // return
376 // }
377 //
378 // main() {
379 // %10:
380 // %11 = %2();
381 // // Reconvergence *not* guaranteed.
382 // %12:
383 // return
384 // }
385 ASSERT_NO_FATAL_FAILURE(Build(Preamble() + R"(
386 %10 = OpLabel
387 %11 = OpFunctionCall %void %2
388 OpBranch %12
389 %12 = OpLabel
390 OpReturn
391 OpFunctionEnd
392
393 %2 = OpFunction %void None %void_f
394 %20 = OpLabel
395 %21 = OpLoad %float %x
396 %22 = OpFOrdLessThan %bool %21 %zero
397 OpSelectionMerge %24 None
398 OpBranchConditional %22 %23 %24
399 %23 = OpLabel
400 OpReturn
401 %24 = OpLabel
402 OpReturn
403 OpFunctionEnd
404 )"));
405
406 EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(10));
407 // Conservatively assume function return value is uniform.
408 EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(11));
409 // TODO(dongja): blocks reachable from diverging function calls should be
410 // divergent.
411 // EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(12));
412 EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(12)); // Wrong!
413 }
414
TEST_F(DivergenceTest,LateMergeTest)415 TEST_F(DivergenceTest, LateMergeTest) {
416 // pseudocode:
417 // %10:
418 // %11 = load y
419 // %12 = %11 < 0
420 // [merge: %15]
421 // if (%12) {
422 // %13:
423 // }
424 // %14: // Reconvergence hasn't happened by here.
425 // %15:
426 // return
427 ASSERT_NO_FATAL_FAILURE(Build(Preamble() + R"(
428 %10 = OpLabel
429 %11 = OpLoad %float %x
430 %12 = OpFOrdLessThan %bool %11 %zero
431 OpSelectionMerge %15 None
432 OpBranchConditional %12 %13 %14
433 %13 = OpLabel
434 OpBranch %14
435 %14 = OpLabel
436 OpBranch %15
437 %15 = OpLabel
438 OpReturn
439 OpFunctionEnd
440 )"));
441
442 EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(10));
443 EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(11));
444 EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(12));
445 EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(13));
446 // TODO(dongja):
447 // EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(14));
448 EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(14)); // Wrong!
449 EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(15));
450 }
451
452 // The following series of tests makes sure that we find the least fixpoint.
TEST_F(DivergenceTest,UniformFixpointTest)453 TEST_F(DivergenceTest, UniformFixpointTest) {
454 // pseudocode:
455 // %10:
456 // %20 = load x
457 // %21 = load y
458 // do {
459 // %11:
460 // %12:
461 // %13 = phi(%zero from %11, %14 from %16)
462 // %14 = %13 + 1
463 // %15 = %13 < 1
464 // } %16: while (%15)
465 // %17:
466 ASSERT_NO_FATAL_FAILURE(Build(Preamble() + R"(
467 %10 = OpLabel
468 %20 = OpLoad %float %x
469 %21 = OpLoad %float %y
470 OpBranch %11
471 %11 = OpLabel
472 %13 = OpPhi %float %zero %10 %14 %16
473 OpLoopMerge %17 %16 None
474 OpBranch %12
475 %12 = OpLabel
476 %14 = OpFAdd %float %13 %one
477 %15 = OpFOrdLessThan %bool %13 %one
478 OpBranch %16
479 %16 = OpLabel
480 OpBranchConditional %15 %11 %17
481 %17 = OpLabel
482 OpReturn
483 OpFunctionEnd
484 )"));
485
486 EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(10));
487 EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(11));
488 EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(12));
489 EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(13));
490 EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(14));
491 EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(15));
492 EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(16));
493 EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(17));
494 }
495
TEST_F(DivergenceTest,PartiallyUniformFixpointTest)496 TEST_F(DivergenceTest, PartiallyUniformFixpointTest) {
497 // pseudocode:
498 // %10:
499 // %20 = load x
500 // %21 = load y
501 // do {
502 // %11:
503 // %12:
504 // %13 = phi(%zero from %11, %14 from %16)
505 // %14 = %13 + 1
506 // %15 = %13 < %21
507 // } %16: while (%15)
508 // %17:
509 ASSERT_NO_FATAL_FAILURE(Build(Preamble() + R"(
510 %10 = OpLabel
511 %20 = OpLoad %float %x
512 %21 = OpLoad %float %y
513 OpBranch %11
514 %11 = OpLabel
515 %13 = OpPhi %float %zero %10 %14 %16
516 OpLoopMerge %17 %16 None
517 OpBranch %12
518 %12 = OpLabel
519 %14 = OpFAdd %float %13 %one
520 %15 = OpFOrdLessThan %bool %13 %21
521 OpBranch %16
522 %16 = OpLabel
523 OpBranchConditional %15 %11 %17
524 %17 = OpLabel
525 OpReturn
526 OpFunctionEnd
527 )"));
528
529 EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(10));
530 EXPECT_EQ(Level::kPartiallyUniform, divergence_->GetDivergenceLevel(11));
531 EXPECT_EQ(Level::kPartiallyUniform, divergence_->GetDivergenceLevel(12));
532 EXPECT_EQ(Level::kPartiallyUniform, divergence_->GetDivergenceLevel(13));
533 EXPECT_EQ(Level::kPartiallyUniform, divergence_->GetDivergenceLevel(14));
534 EXPECT_EQ(Level::kPartiallyUniform, divergence_->GetDivergenceLevel(15));
535 EXPECT_EQ(Level::kPartiallyUniform, divergence_->GetDivergenceLevel(16));
536 EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(17));
537 }
538
TEST_F(DivergenceTest,DivergentFixpointTest)539 TEST_F(DivergenceTest, DivergentFixpointTest) {
540 // pseudocode:
541 // %10:
542 // %20 = load x
543 // %21 = load y
544 // do {
545 // %11:
546 // %12:
547 // %13 = phi(%zero from %11, %14 from %16)
548 // %14 = %13 + 1
549 // %15 = %13 < %20
550 // } %16: while (%15)
551 // %17:
552 ASSERT_NO_FATAL_FAILURE(Build(Preamble() + R"(
553 %10 = OpLabel
554 %20 = OpLoad %float %x
555 %21 = OpLoad %float %y
556 OpBranch %11
557 %11 = OpLabel
558 %13 = OpPhi %float %zero %10 %14 %16
559 OpLoopMerge %17 %16 None
560 OpBranch %12
561 %12 = OpLabel
562 %14 = OpFAdd %float %13 %one
563 %15 = OpFOrdLessThan %bool %13 %20
564 OpBranch %16
565 %16 = OpLabel
566 OpBranchConditional %15 %11 %17
567 %17 = OpLabel
568 OpReturn
569 OpFunctionEnd
570 )"));
571
572 EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(10));
573 EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(11));
574 EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(12));
575 EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(13));
576 EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(14));
577 EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(15));
578 EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(16));
579 EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(17));
580 }
581
TEST_F(DivergenceTest,DivergentOverridesPartiallyUniformTest)582 TEST_F(DivergenceTest, DivergentOverridesPartiallyUniformTest) {
583 // pseudocode:
584 // %10:
585 // %20 = load x
586 // %21 = load y
587 // %11:
588 // do {
589 // %12:
590 // %13 = phi(%21 from %11, %14 from %16)
591 // %14 = %13 + 1
592 // %15 = %13 < %20
593 // } %16: while (%15)
594 // %17:
595 ASSERT_NO_FATAL_FAILURE(Build(Preamble() + R"(
596 %10 = OpLabel
597 %20 = OpLoad %float %x
598 %21 = OpLoad %float %y
599 OpBranch %11
600 %11 = OpLabel
601 %13 = OpPhi %float %zero %10 %14 %16
602 OpLoopMerge %17 %16 None
603 OpBranch %12
604 %12 = OpLabel
605 %14 = OpFAdd %float %13 %one
606 %15 = OpFOrdLessThan %bool %13 %20
607 OpBranch %16
608 %16 = OpLabel
609 OpBranchConditional %15 %11 %17
610 %17 = OpLabel
611 OpReturn
612 OpFunctionEnd
613 )"));
614
615 EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(10));
616 EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(11));
617 EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(12));
618 EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(13));
619 EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(14));
620 EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(15));
621 EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(16));
622 EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(17));
623 }
624
TEST_F(DivergenceTest,NestedFixpointTest)625 TEST_F(DivergenceTest, NestedFixpointTest) {
626 // pseudocode:
627 // %10:
628 // %20 = load x
629 // %21 = load y
630 // do {
631 // %22:
632 // %23:
633 // %24 = phi(%zero from %22, %25 from %26)
634 // %11:
635 // do {
636 // %12:
637 // %13 = phi(%zero from %11, %14 from %16)
638 // %14 = %13 + 1
639 // %15 = %13 < %24
640 // } %16: while (%15)
641 // %17:
642 // %25 = load x
643 // } %26: while (false)
644 // %27:
645 // return
646 ASSERT_NO_FATAL_FAILURE(Build(Preamble() + R"(
647 %10 = OpLabel
648 %20 = OpLoad %float %x
649 %21 = OpLoad %float %y
650 OpBranch %22
651 %22 = OpLabel
652 %24 = OpPhi %float %zero %10 %25 %26
653 OpLoopMerge %27 %26 None
654 OpBranch %23
655 %23 = OpLabel
656 OpBranch %11
657 %11 = OpLabel
658 %13 = OpPhi %float %zero %23 %14 %16
659 OpLoopMerge %17 %16 None
660 OpBranch %12
661 %12 = OpLabel
662 %14 = OpFAdd %float %13 %one
663 %15 = OpFOrdLessThan %bool %13 %24
664 OpBranch %16
665 %16 = OpLabel
666 OpBranchConditional %15 %11 %17
667 %17 = OpLabel
668 %25 = OpLoad %float %x
669 OpBranch %26
670 %26 = OpLabel
671 OpBranchConditional %false %22 %27
672 %27 = OpLabel
673 OpReturn
674 OpFunctionEnd
675 )"));
676 // This test makes sure that divergent values flowing upward can influence the
677 // fixpoint of a loop.
678 EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(10));
679 EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(11));
680 EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(12));
681 EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(13));
682 EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(14));
683 EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(15));
684 EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(16));
685 // Control of the outer loop is still uniform.
686 EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(17));
687 EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(22));
688 EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(23));
689 // Seed divergent values.
690 EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(24));
691 EXPECT_EQ(Level::kDivergent, divergence_->GetDivergenceLevel(25));
692 // Outer loop control.
693 EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(26));
694 // Merged.
695 EXPECT_EQ(Level::kUniform, divergence_->GetDivergenceLevel(27));
696 }
697
698 } // namespace
699 } // namespace lint
700 } // namespace spvtools
701