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 "source/opt/scalar_analysis.h"
16
17 #include <memory>
18 #include <vector>
19
20 #include "gmock/gmock.h"
21 #include "source/opt/pass.h"
22 #include "test/opt/assembly_builder.h"
23 #include "test/opt/function_utils.h"
24 #include "test/opt/pass_fixture.h"
25 #include "test/opt/pass_utils.h"
26
27 namespace spvtools {
28 namespace opt {
29 namespace {
30
31 using ::testing::UnorderedElementsAre;
32 using ScalarAnalysisTest = PassTest<::testing::Test>;
33
34 /*
35 Generated from the following GLSL + --eliminate-local-multi-store
36
37 #version 410 core
38 layout (location = 1) out float array[10];
39 void main() {
40 for (int i = 0; i < 10; ++i) {
41 array[i] = array[i+1];
42 }
43 }
44 */
TEST_F(ScalarAnalysisTest,BasicEvolutionTest)45 TEST_F(ScalarAnalysisTest, BasicEvolutionTest) {
46 const std::string text = R"(
47 OpCapability Shader
48 %1 = OpExtInstImport "GLSL.std.450"
49 OpMemoryModel Logical GLSL450
50 OpEntryPoint Fragment %4 "main" %24
51 OpExecutionMode %4 OriginUpperLeft
52 OpSource GLSL 410
53 OpName %4 "main"
54 OpName %24 "array"
55 OpDecorate %24 Location 1
56 %2 = OpTypeVoid
57 %3 = OpTypeFunction %2
58 %6 = OpTypeInt 32 1
59 %7 = OpTypePointer Function %6
60 %9 = OpConstant %6 0
61 %16 = OpConstant %6 10
62 %17 = OpTypeBool
63 %19 = OpTypeFloat 32
64 %20 = OpTypeInt 32 0
65 %21 = OpConstant %20 10
66 %22 = OpTypeArray %19 %21
67 %23 = OpTypePointer Output %22
68 %24 = OpVariable %23 Output
69 %27 = OpConstant %6 1
70 %29 = OpTypePointer Output %19
71 %4 = OpFunction %2 None %3
72 %5 = OpLabel
73 OpBranch %10
74 %10 = OpLabel
75 %35 = OpPhi %6 %9 %5 %34 %13
76 OpLoopMerge %12 %13 None
77 OpBranch %14
78 %14 = OpLabel
79 %18 = OpSLessThan %17 %35 %16
80 OpBranchConditional %18 %11 %12
81 %11 = OpLabel
82 %28 = OpIAdd %6 %35 %27
83 %30 = OpAccessChain %29 %24 %28
84 %31 = OpLoad %19 %30
85 %32 = OpAccessChain %29 %24 %35
86 OpStore %32 %31
87 OpBranch %13
88 %13 = OpLabel
89 %34 = OpIAdd %6 %35 %27
90 OpBranch %10
91 %12 = OpLabel
92 OpReturn
93 OpFunctionEnd
94 )";
95 // clang-format on
96 std::unique_ptr<IRContext> context =
97 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
98 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
99 Module* module = context->module();
100 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
101 << text << std::endl;
102 const Function* f = spvtest::GetFunction(module, 4);
103 ScalarEvolutionAnalysis analysis{context.get()};
104
105 const Instruction* store = nullptr;
106 const Instruction* load = nullptr;
107 for (const Instruction& inst : *spvtest::GetBasicBlock(f, 11)) {
108 if (inst.opcode() == spv::Op::OpStore) {
109 store = &inst;
110 }
111 if (inst.opcode() == spv::Op::OpLoad) {
112 load = &inst;
113 }
114 }
115
116 EXPECT_NE(load, nullptr);
117 EXPECT_NE(store, nullptr);
118
119 Instruction* access_chain =
120 context->get_def_use_mgr()->GetDef(load->GetSingleWordInOperand(0));
121
122 Instruction* child = context->get_def_use_mgr()->GetDef(
123 access_chain->GetSingleWordInOperand(1));
124 const SENode* node = analysis.AnalyzeInstruction(child);
125
126 EXPECT_NE(node, nullptr);
127
128 // Unsimplified node should have the form of ADD(REC(0,1), 1)
129 EXPECT_EQ(node->GetType(), SENode::Add);
130
131 const SENode* child_1 = node->GetChild(0);
132 EXPECT_TRUE(child_1->GetType() == SENode::Constant ||
133 child_1->GetType() == SENode::RecurrentAddExpr);
134
135 const SENode* child_2 = node->GetChild(1);
136 EXPECT_TRUE(child_2->GetType() == SENode::Constant ||
137 child_2->GetType() == SENode::RecurrentAddExpr);
138
139 SENode* simplified = analysis.SimplifyExpression(const_cast<SENode*>(node));
140 // Simplified should be in the form of REC(1,1)
141 EXPECT_EQ(simplified->GetType(), SENode::RecurrentAddExpr);
142
143 EXPECT_EQ(simplified->GetChild(0)->GetType(), SENode::Constant);
144 EXPECT_EQ(simplified->GetChild(0)->AsSEConstantNode()->FoldToSingleValue(),
145 1);
146
147 EXPECT_EQ(simplified->GetChild(1)->GetType(), SENode::Constant);
148 EXPECT_EQ(simplified->GetChild(1)->AsSEConstantNode()->FoldToSingleValue(),
149 1);
150
151 EXPECT_EQ(simplified->GetChild(0), simplified->GetChild(1));
152 }
153
154 /*
155 Generated from the following GLSL + --eliminate-local-multi-store
156
157 #version 410 core
158 layout (location = 1) out float array[10];
159 layout (location = 2) flat in int loop_invariant;
160 void main() {
161 for (int i = 0; i < 10; ++i) {
162 array[i] = array[i+loop_invariant];
163 }
164 }
165
166 */
TEST_F(ScalarAnalysisTest,LoadTest)167 TEST_F(ScalarAnalysisTest, LoadTest) {
168 const std::string text = R"(
169 OpCapability Shader
170 %1 = OpExtInstImport "GLSL.std.450"
171 OpMemoryModel Logical GLSL450
172 OpEntryPoint Fragment %2 "main" %3 %4
173 OpExecutionMode %2 OriginUpperLeft
174 OpSource GLSL 430
175 OpName %2 "main"
176 OpName %3 "array"
177 OpName %4 "loop_invariant"
178 OpDecorate %3 Location 1
179 OpDecorate %4 Flat
180 OpDecorate %4 Location 2
181 %5 = OpTypeVoid
182 %6 = OpTypeFunction %5
183 %7 = OpTypeInt 32 1
184 %8 = OpTypePointer Function %7
185 %9 = OpConstant %7 0
186 %10 = OpConstant %7 10
187 %11 = OpTypeBool
188 %12 = OpTypeFloat 32
189 %13 = OpTypeInt 32 0
190 %14 = OpConstant %13 10
191 %15 = OpTypeArray %12 %14
192 %16 = OpTypePointer Output %15
193 %3 = OpVariable %16 Output
194 %17 = OpTypePointer Input %7
195 %4 = OpVariable %17 Input
196 %18 = OpTypePointer Output %12
197 %19 = OpConstant %7 1
198 %2 = OpFunction %5 None %6
199 %20 = OpLabel
200 OpBranch %21
201 %21 = OpLabel
202 %22 = OpPhi %7 %9 %20 %23 %24
203 OpLoopMerge %25 %24 None
204 OpBranch %26
205 %26 = OpLabel
206 %27 = OpSLessThan %11 %22 %10
207 OpBranchConditional %27 %28 %25
208 %28 = OpLabel
209 %29 = OpLoad %7 %4
210 %30 = OpIAdd %7 %22 %29
211 %31 = OpAccessChain %18 %3 %30
212 %32 = OpLoad %12 %31
213 %33 = OpAccessChain %18 %3 %22
214 OpStore %33 %32
215 OpBranch %24
216 %24 = OpLabel
217 %23 = OpIAdd %7 %22 %19
218 OpBranch %21
219 %25 = OpLabel
220 OpReturn
221 OpFunctionEnd
222 )";
223 // clang-format on
224 std::unique_ptr<IRContext> context =
225 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
226 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
227 Module* module = context->module();
228 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
229 << text << std::endl;
230 const Function* f = spvtest::GetFunction(module, 2);
231 ScalarEvolutionAnalysis analysis{context.get()};
232
233 const Instruction* load = nullptr;
234 for (const Instruction& inst : *spvtest::GetBasicBlock(f, 28)) {
235 if (inst.opcode() == spv::Op::OpLoad) {
236 load = &inst;
237 }
238 }
239
240 EXPECT_NE(load, nullptr);
241
242 Instruction* access_chain =
243 context->get_def_use_mgr()->GetDef(load->GetSingleWordInOperand(0));
244
245 Instruction* child = context->get_def_use_mgr()->GetDef(
246 access_chain->GetSingleWordInOperand(1));
247 // const SENode* node =
248 // analysis.GetNodeFromInstruction(child->unique_id());
249
250 const SENode* node = analysis.AnalyzeInstruction(child);
251
252 EXPECT_NE(node, nullptr);
253
254 // Unsimplified node should have the form of ADD(REC(0,1), X)
255 EXPECT_EQ(node->GetType(), SENode::Add);
256
257 const SENode* child_1 = node->GetChild(0);
258 EXPECT_TRUE(child_1->GetType() == SENode::ValueUnknown ||
259 child_1->GetType() == SENode::RecurrentAddExpr);
260
261 const SENode* child_2 = node->GetChild(1);
262 EXPECT_TRUE(child_2->GetType() == SENode::ValueUnknown ||
263 child_2->GetType() == SENode::RecurrentAddExpr);
264
265 SENode* simplified = analysis.SimplifyExpression(const_cast<SENode*>(node));
266 EXPECT_EQ(simplified->GetType(), SENode::RecurrentAddExpr);
267
268 const SERecurrentNode* rec = simplified->AsSERecurrentNode();
269
270 EXPECT_NE(rec->GetChild(0), rec->GetChild(1));
271
272 EXPECT_EQ(rec->GetOffset()->GetType(), SENode::ValueUnknown);
273
274 EXPECT_EQ(rec->GetCoefficient()->GetType(), SENode::Constant);
275 EXPECT_EQ(rec->GetCoefficient()->AsSEConstantNode()->FoldToSingleValue(), 1u);
276 }
277
278 /*
279 Generated from the following GLSL + --eliminate-local-multi-store
280
281 #version 410 core
282 layout (location = 1) out float array[10];
283 layout (location = 2) flat in int loop_invariant;
284 void main() {
285 array[0] = array[loop_invariant * 2 + 4 + 5 - 24 - loop_invariant -
286 loop_invariant+ 16 * 3];
287 }
288
289 */
TEST_F(ScalarAnalysisTest,SimplifySimple)290 TEST_F(ScalarAnalysisTest, SimplifySimple) {
291 const std::string text = R"(
292 OpCapability Shader
293 %1 = OpExtInstImport "GLSL.std.450"
294 OpMemoryModel Logical GLSL450
295 OpEntryPoint Fragment %2 "main" %3 %4
296 OpExecutionMode %2 OriginUpperLeft
297 OpSource GLSL 430
298 OpName %2 "main"
299 OpName %3 "array"
300 OpName %4 "loop_invariant"
301 OpDecorate %3 Location 1
302 OpDecorate %4 Flat
303 OpDecorate %4 Location 2
304 %5 = OpTypeVoid
305 %6 = OpTypeFunction %5
306 %7 = OpTypeFloat 32
307 %8 = OpTypeInt 32 0
308 %9 = OpConstant %8 10
309 %10 = OpTypeArray %7 %9
310 %11 = OpTypePointer Output %10
311 %3 = OpVariable %11 Output
312 %12 = OpTypeInt 32 1
313 %13 = OpConstant %12 0
314 %14 = OpTypePointer Input %12
315 %4 = OpVariable %14 Input
316 %15 = OpConstant %12 2
317 %16 = OpConstant %12 4
318 %17 = OpConstant %12 5
319 %18 = OpConstant %12 24
320 %19 = OpConstant %12 48
321 %20 = OpTypePointer Output %7
322 %2 = OpFunction %5 None %6
323 %21 = OpLabel
324 %22 = OpLoad %12 %4
325 %23 = OpIMul %12 %22 %15
326 %24 = OpIAdd %12 %23 %16
327 %25 = OpIAdd %12 %24 %17
328 %26 = OpISub %12 %25 %18
329 %28 = OpISub %12 %26 %22
330 %30 = OpISub %12 %28 %22
331 %31 = OpIAdd %12 %30 %19
332 %32 = OpAccessChain %20 %3 %31
333 %33 = OpLoad %7 %32
334 %34 = OpAccessChain %20 %3 %13
335 OpStore %34 %33
336 OpReturn
337 OpFunctionEnd
338 )";
339 // clang-format on
340 std::unique_ptr<IRContext> context =
341 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
342 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
343 Module* module = context->module();
344 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
345 << text << std::endl;
346 const Function* f = spvtest::GetFunction(module, 2);
347 ScalarEvolutionAnalysis analysis{context.get()};
348
349 const Instruction* load = nullptr;
350 for (const Instruction& inst : *spvtest::GetBasicBlock(f, 21)) {
351 if (inst.opcode() == spv::Op::OpLoad && inst.result_id() == 33) {
352 load = &inst;
353 }
354 }
355
356 EXPECT_NE(load, nullptr);
357
358 Instruction* access_chain =
359 context->get_def_use_mgr()->GetDef(load->GetSingleWordInOperand(0));
360
361 Instruction* child = context->get_def_use_mgr()->GetDef(
362 access_chain->GetSingleWordInOperand(1));
363
364 const SENode* node = analysis.AnalyzeInstruction(child);
365
366 // Unsimplified is a very large graph with an add at the top.
367 EXPECT_NE(node, nullptr);
368 EXPECT_EQ(node->GetType(), SENode::Add);
369
370 // Simplified node should resolve down to a constant expression as the loads
371 // will eliminate themselves.
372 SENode* simplified = analysis.SimplifyExpression(const_cast<SENode*>(node));
373
374 EXPECT_EQ(simplified->GetType(), SENode::Constant);
375 EXPECT_EQ(simplified->AsSEConstantNode()->FoldToSingleValue(), 33u);
376 }
377
378 /*
379 Generated from the following GLSL + --eliminate-local-multi-store
380
381 #version 410 core
382 layout(location = 0) in vec4 c;
383 layout (location = 1) out float array[10];
384 void main() {
385 int N = int(c.x);
386 for (int i = 0; i < 10; ++i) {
387 array[i] = array[i];
388 array[i] = array[i-1];
389 array[i] = array[i+1];
390 array[i+1] = array[i+1];
391 array[i+N] = array[i+N];
392 array[i] = array[i+N];
393 }
394 }
395
396 */
TEST_F(ScalarAnalysisTest,Simplify)397 TEST_F(ScalarAnalysisTest, Simplify) {
398 const std::string text = R"( OpCapability Shader
399 %1 = OpExtInstImport "GLSL.std.450"
400 OpMemoryModel Logical GLSL450
401 OpEntryPoint Fragment %4 "main" %12 %33
402 OpExecutionMode %4 OriginUpperLeft
403 OpSource GLSL 410
404 OpName %4 "main"
405 OpName %8 "N"
406 OpName %12 "c"
407 OpName %19 "i"
408 OpName %33 "array"
409 OpDecorate %12 Location 0
410 OpDecorate %33 Location 1
411 %2 = OpTypeVoid
412 %3 = OpTypeFunction %2
413 %6 = OpTypeInt 32 1
414 %7 = OpTypePointer Function %6
415 %9 = OpTypeFloat 32
416 %10 = OpTypeVector %9 4
417 %11 = OpTypePointer Input %10
418 %12 = OpVariable %11 Input
419 %13 = OpTypeInt 32 0
420 %14 = OpConstant %13 0
421 %15 = OpTypePointer Input %9
422 %20 = OpConstant %6 0
423 %27 = OpConstant %6 10
424 %28 = OpTypeBool
425 %30 = OpConstant %13 10
426 %31 = OpTypeArray %9 %30
427 %32 = OpTypePointer Output %31
428 %33 = OpVariable %32 Output
429 %36 = OpTypePointer Output %9
430 %42 = OpConstant %6 1
431 %4 = OpFunction %2 None %3
432 %5 = OpLabel
433 %8 = OpVariable %7 Function
434 %19 = OpVariable %7 Function
435 %16 = OpAccessChain %15 %12 %14
436 %17 = OpLoad %9 %16
437 %18 = OpConvertFToS %6 %17
438 OpStore %8 %18
439 OpStore %19 %20
440 OpBranch %21
441 %21 = OpLabel
442 %78 = OpPhi %6 %20 %5 %77 %24
443 OpLoopMerge %23 %24 None
444 OpBranch %25
445 %25 = OpLabel
446 %29 = OpSLessThan %28 %78 %27
447 OpBranchConditional %29 %22 %23
448 %22 = OpLabel
449 %37 = OpAccessChain %36 %33 %78
450 %38 = OpLoad %9 %37
451 %39 = OpAccessChain %36 %33 %78
452 OpStore %39 %38
453 %43 = OpISub %6 %78 %42
454 %44 = OpAccessChain %36 %33 %43
455 %45 = OpLoad %9 %44
456 %46 = OpAccessChain %36 %33 %78
457 OpStore %46 %45
458 %49 = OpIAdd %6 %78 %42
459 %50 = OpAccessChain %36 %33 %49
460 %51 = OpLoad %9 %50
461 %52 = OpAccessChain %36 %33 %78
462 OpStore %52 %51
463 %54 = OpIAdd %6 %78 %42
464 %56 = OpIAdd %6 %78 %42
465 %57 = OpAccessChain %36 %33 %56
466 %58 = OpLoad %9 %57
467 %59 = OpAccessChain %36 %33 %54
468 OpStore %59 %58
469 %62 = OpIAdd %6 %78 %18
470 %65 = OpIAdd %6 %78 %18
471 %66 = OpAccessChain %36 %33 %65
472 %67 = OpLoad %9 %66
473 %68 = OpAccessChain %36 %33 %62
474 OpStore %68 %67
475 %72 = OpIAdd %6 %78 %18
476 %73 = OpAccessChain %36 %33 %72
477 %74 = OpLoad %9 %73
478 %75 = OpAccessChain %36 %33 %78
479 OpStore %75 %74
480 OpBranch %24
481 %24 = OpLabel
482 %77 = OpIAdd %6 %78 %42
483 OpStore %19 %77
484 OpBranch %21
485 %23 = OpLabel
486 OpReturn
487 OpFunctionEnd
488 )";
489 // clang-format on
490 std::unique_ptr<IRContext> context =
491 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
492 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
493 Module* module = context->module();
494 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
495 << text << std::endl;
496 const Function* f = spvtest::GetFunction(module, 4);
497 ScalarEvolutionAnalysis analysis{context.get()};
498
499 const Instruction* loads[6];
500 const Instruction* stores[6];
501 int load_count = 0;
502 int store_count = 0;
503
504 for (const Instruction& inst : *spvtest::GetBasicBlock(f, 22)) {
505 if (inst.opcode() == spv::Op::OpLoad) {
506 loads[load_count] = &inst;
507 ++load_count;
508 }
509 if (inst.opcode() == spv::Op::OpStore) {
510 stores[store_count] = &inst;
511 ++store_count;
512 }
513 }
514
515 EXPECT_EQ(load_count, 6);
516 EXPECT_EQ(store_count, 6);
517
518 Instruction* load_access_chain;
519 Instruction* store_access_chain;
520 Instruction* load_child;
521 Instruction* store_child;
522 SENode* load_node;
523 SENode* store_node;
524 SENode* subtract_node;
525 SENode* simplified_node;
526
527 // Testing [i] - [i] == 0
528 load_access_chain =
529 context->get_def_use_mgr()->GetDef(loads[0]->GetSingleWordInOperand(0));
530 store_access_chain =
531 context->get_def_use_mgr()->GetDef(stores[0]->GetSingleWordInOperand(0));
532
533 load_child = context->get_def_use_mgr()->GetDef(
534 load_access_chain->GetSingleWordInOperand(1));
535 store_child = context->get_def_use_mgr()->GetDef(
536 store_access_chain->GetSingleWordInOperand(1));
537
538 load_node = analysis.AnalyzeInstruction(load_child);
539 store_node = analysis.AnalyzeInstruction(store_child);
540
541 subtract_node = analysis.CreateSubtraction(store_node, load_node);
542 simplified_node = analysis.SimplifyExpression(subtract_node);
543 EXPECT_EQ(simplified_node->GetType(), SENode::Constant);
544 EXPECT_EQ(simplified_node->AsSEConstantNode()->FoldToSingleValue(), 0u);
545
546 // Testing [i] - [i-1] == 1
547 load_access_chain =
548 context->get_def_use_mgr()->GetDef(loads[1]->GetSingleWordInOperand(0));
549 store_access_chain =
550 context->get_def_use_mgr()->GetDef(stores[1]->GetSingleWordInOperand(0));
551
552 load_child = context->get_def_use_mgr()->GetDef(
553 load_access_chain->GetSingleWordInOperand(1));
554 store_child = context->get_def_use_mgr()->GetDef(
555 store_access_chain->GetSingleWordInOperand(1));
556
557 load_node = analysis.AnalyzeInstruction(load_child);
558 store_node = analysis.AnalyzeInstruction(store_child);
559
560 subtract_node = analysis.CreateSubtraction(store_node, load_node);
561 simplified_node = analysis.SimplifyExpression(subtract_node);
562
563 EXPECT_EQ(simplified_node->GetType(), SENode::Constant);
564 EXPECT_EQ(simplified_node->AsSEConstantNode()->FoldToSingleValue(), 1u);
565
566 // Testing [i] - [i+1] == -1
567 load_access_chain =
568 context->get_def_use_mgr()->GetDef(loads[2]->GetSingleWordInOperand(0));
569 store_access_chain =
570 context->get_def_use_mgr()->GetDef(stores[2]->GetSingleWordInOperand(0));
571
572 load_child = context->get_def_use_mgr()->GetDef(
573 load_access_chain->GetSingleWordInOperand(1));
574 store_child = context->get_def_use_mgr()->GetDef(
575 store_access_chain->GetSingleWordInOperand(1));
576
577 load_node = analysis.AnalyzeInstruction(load_child);
578 store_node = analysis.AnalyzeInstruction(store_child);
579
580 subtract_node = analysis.CreateSubtraction(store_node, load_node);
581 simplified_node = analysis.SimplifyExpression(subtract_node);
582 EXPECT_EQ(simplified_node->GetType(), SENode::Constant);
583 EXPECT_EQ(simplified_node->AsSEConstantNode()->FoldToSingleValue(), -1);
584
585 // Testing [i+1] - [i+1] == 0
586 load_access_chain =
587 context->get_def_use_mgr()->GetDef(loads[3]->GetSingleWordInOperand(0));
588 store_access_chain =
589 context->get_def_use_mgr()->GetDef(stores[3]->GetSingleWordInOperand(0));
590
591 load_child = context->get_def_use_mgr()->GetDef(
592 load_access_chain->GetSingleWordInOperand(1));
593 store_child = context->get_def_use_mgr()->GetDef(
594 store_access_chain->GetSingleWordInOperand(1));
595
596 load_node = analysis.AnalyzeInstruction(load_child);
597 store_node = analysis.AnalyzeInstruction(store_child);
598
599 subtract_node = analysis.CreateSubtraction(store_node, load_node);
600 simplified_node = analysis.SimplifyExpression(subtract_node);
601 EXPECT_EQ(simplified_node->GetType(), SENode::Constant);
602 EXPECT_EQ(simplified_node->AsSEConstantNode()->FoldToSingleValue(), 0u);
603
604 // Testing [i+N] - [i+N] == 0
605 load_access_chain =
606 context->get_def_use_mgr()->GetDef(loads[4]->GetSingleWordInOperand(0));
607 store_access_chain =
608 context->get_def_use_mgr()->GetDef(stores[4]->GetSingleWordInOperand(0));
609
610 load_child = context->get_def_use_mgr()->GetDef(
611 load_access_chain->GetSingleWordInOperand(1));
612 store_child = context->get_def_use_mgr()->GetDef(
613 store_access_chain->GetSingleWordInOperand(1));
614
615 load_node = analysis.AnalyzeInstruction(load_child);
616 store_node = analysis.AnalyzeInstruction(store_child);
617
618 subtract_node = analysis.CreateSubtraction(store_node, load_node);
619
620 simplified_node = analysis.SimplifyExpression(subtract_node);
621 EXPECT_EQ(simplified_node->GetType(), SENode::Constant);
622 EXPECT_EQ(simplified_node->AsSEConstantNode()->FoldToSingleValue(), 0u);
623
624 // Testing [i] - [i+N] == -N
625 load_access_chain =
626 context->get_def_use_mgr()->GetDef(loads[5]->GetSingleWordInOperand(0));
627 store_access_chain =
628 context->get_def_use_mgr()->GetDef(stores[5]->GetSingleWordInOperand(0));
629
630 load_child = context->get_def_use_mgr()->GetDef(
631 load_access_chain->GetSingleWordInOperand(1));
632 store_child = context->get_def_use_mgr()->GetDef(
633 store_access_chain->GetSingleWordInOperand(1));
634
635 load_node = analysis.AnalyzeInstruction(load_child);
636 store_node = analysis.AnalyzeInstruction(store_child);
637
638 subtract_node = analysis.CreateSubtraction(store_node, load_node);
639 simplified_node = analysis.SimplifyExpression(subtract_node);
640 EXPECT_EQ(simplified_node->GetType(), SENode::Negative);
641 }
642
643 /*
644 Generated from the following GLSL + --eliminate-local-multi-store
645
646 #version 430
647 layout(location = 1) out float array[10];
648 layout(location = 2) flat in int loop_invariant;
649 void main(void) {
650 for (int i = 0; i < 10; ++i) {
651 array[i * 2 + i * 5] = array[i * i * 2];
652 array[i * 2] = array[i * 5];
653 }
654 }
655
656 */
657
TEST_F(ScalarAnalysisTest,SimplifyMultiplyInductions)658 TEST_F(ScalarAnalysisTest, SimplifyMultiplyInductions) {
659 const std::string text = R"(
660 OpCapability Shader
661 %1 = OpExtInstImport "GLSL.std.450"
662 OpMemoryModel Logical GLSL450
663 OpEntryPoint Fragment %2 "main" %3 %4
664 OpExecutionMode %2 OriginUpperLeft
665 OpSource GLSL 430
666 OpName %2 "main"
667 OpName %5 "i"
668 OpName %3 "array"
669 OpName %4 "loop_invariant"
670 OpDecorate %3 Location 1
671 OpDecorate %4 Flat
672 OpDecorate %4 Location 2
673 %6 = OpTypeVoid
674 %7 = OpTypeFunction %6
675 %8 = OpTypeInt 32 1
676 %9 = OpTypePointer Function %8
677 %10 = OpConstant %8 0
678 %11 = OpConstant %8 10
679 %12 = OpTypeBool
680 %13 = OpTypeFloat 32
681 %14 = OpTypeInt 32 0
682 %15 = OpConstant %14 10
683 %16 = OpTypeArray %13 %15
684 %17 = OpTypePointer Output %16
685 %3 = OpVariable %17 Output
686 %18 = OpConstant %8 2
687 %19 = OpConstant %8 5
688 %20 = OpTypePointer Output %13
689 %21 = OpConstant %8 1
690 %22 = OpTypePointer Input %8
691 %4 = OpVariable %22 Input
692 %2 = OpFunction %6 None %7
693 %23 = OpLabel
694 %5 = OpVariable %9 Function
695 OpStore %5 %10
696 OpBranch %24
697 %24 = OpLabel
698 %25 = OpPhi %8 %10 %23 %26 %27
699 OpLoopMerge %28 %27 None
700 OpBranch %29
701 %29 = OpLabel
702 %30 = OpSLessThan %12 %25 %11
703 OpBranchConditional %30 %31 %28
704 %31 = OpLabel
705 %32 = OpIMul %8 %25 %18
706 %33 = OpIMul %8 %25 %19
707 %34 = OpIAdd %8 %32 %33
708 %35 = OpIMul %8 %25 %25
709 %36 = OpIMul %8 %35 %18
710 %37 = OpAccessChain %20 %3 %36
711 %38 = OpLoad %13 %37
712 %39 = OpAccessChain %20 %3 %34
713 OpStore %39 %38
714 %40 = OpIMul %8 %25 %18
715 %41 = OpIMul %8 %25 %19
716 %42 = OpAccessChain %20 %3 %41
717 %43 = OpLoad %13 %42
718 %44 = OpAccessChain %20 %3 %40
719 OpStore %44 %43
720 OpBranch %27
721 %27 = OpLabel
722 %26 = OpIAdd %8 %25 %21
723 OpStore %5 %26
724 OpBranch %24
725 %28 = OpLabel
726 OpReturn
727 OpFunctionEnd
728 )";
729 std::unique_ptr<IRContext> context =
730 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
731 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
732 Module* module = context->module();
733 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
734 << text << std::endl;
735 const Function* f = spvtest::GetFunction(module, 2);
736 ScalarEvolutionAnalysis analysis{context.get()};
737
738 const Instruction* loads[2] = {nullptr, nullptr};
739 const Instruction* stores[2] = {nullptr, nullptr};
740 int load_count = 0;
741 int store_count = 0;
742
743 for (const Instruction& inst : *spvtest::GetBasicBlock(f, 31)) {
744 if (inst.opcode() == spv::Op::OpLoad) {
745 loads[load_count] = &inst;
746 ++load_count;
747 }
748 if (inst.opcode() == spv::Op::OpStore) {
749 stores[store_count] = &inst;
750 ++store_count;
751 }
752 }
753
754 EXPECT_EQ(load_count, 2);
755 EXPECT_EQ(store_count, 2);
756
757 Instruction* load_access_chain =
758 context->get_def_use_mgr()->GetDef(loads[0]->GetSingleWordInOperand(0));
759 Instruction* store_access_chain =
760 context->get_def_use_mgr()->GetDef(stores[0]->GetSingleWordInOperand(0));
761
762 Instruction* load_child = context->get_def_use_mgr()->GetDef(
763 load_access_chain->GetSingleWordInOperand(1));
764 Instruction* store_child = context->get_def_use_mgr()->GetDef(
765 store_access_chain->GetSingleWordInOperand(1));
766
767 SENode* store_node = analysis.AnalyzeInstruction(store_child);
768
769 SENode* store_simplified = analysis.SimplifyExpression(store_node);
770
771 load_access_chain =
772 context->get_def_use_mgr()->GetDef(loads[1]->GetSingleWordInOperand(0));
773 store_access_chain =
774 context->get_def_use_mgr()->GetDef(stores[1]->GetSingleWordInOperand(0));
775 load_child = context->get_def_use_mgr()->GetDef(
776 load_access_chain->GetSingleWordInOperand(1));
777 store_child = context->get_def_use_mgr()->GetDef(
778 store_access_chain->GetSingleWordInOperand(1));
779
780 SENode* second_store =
781 analysis.SimplifyExpression(analysis.AnalyzeInstruction(store_child));
782 SENode* second_load =
783 analysis.SimplifyExpression(analysis.AnalyzeInstruction(load_child));
784 SENode* combined_add = analysis.SimplifyExpression(
785 analysis.CreateAddNode(second_load, second_store));
786
787 // We're checking that the two recurrent expression have been correctly
788 // folded. In store_simplified they will have been folded as the entire
789 // expression was simplified as one. In combined_add the two expressions have
790 // been simplified one after the other which means the recurrent expressions
791 // aren't exactly the same but should still be folded as they are with respect
792 // to the same loop.
793 EXPECT_EQ(combined_add, store_simplified);
794 }
795
796 /*
797 Generated from the following GLSL + --eliminate-local-multi-store
798
799 #version 430
800 void main(void) {
801 for (int i = 0; i < 10; --i) {
802 array[i] = array[i];
803 }
804 }
805
806 */
807
TEST_F(ScalarAnalysisTest,SimplifyNegativeSteps)808 TEST_F(ScalarAnalysisTest, SimplifyNegativeSteps) {
809 const std::string text = R"(
810 OpCapability Shader
811 %1 = OpExtInstImport "GLSL.std.450"
812 OpMemoryModel Logical GLSL450
813 OpEntryPoint Fragment %2 "main" %3 %4
814 OpExecutionMode %2 OriginUpperLeft
815 OpSource GLSL 430
816 OpName %2 "main"
817 OpName %5 "i"
818 OpName %3 "array"
819 OpName %4 "loop_invariant"
820 OpDecorate %3 Location 1
821 OpDecorate %4 Flat
822 OpDecorate %4 Location 2
823 %6 = OpTypeVoid
824 %7 = OpTypeFunction %6
825 %8 = OpTypeInt 32 1
826 %9 = OpTypePointer Function %8
827 %10 = OpConstant %8 0
828 %11 = OpConstant %8 10
829 %12 = OpTypeBool
830 %13 = OpTypeFloat 32
831 %14 = OpTypeInt 32 0
832 %15 = OpConstant %14 10
833 %16 = OpTypeArray %13 %15
834 %17 = OpTypePointer Output %16
835 %3 = OpVariable %17 Output
836 %18 = OpTypePointer Output %13
837 %19 = OpConstant %8 1
838 %20 = OpTypePointer Input %8
839 %4 = OpVariable %20 Input
840 %2 = OpFunction %6 None %7
841 %21 = OpLabel
842 %5 = OpVariable %9 Function
843 OpStore %5 %10
844 OpBranch %22
845 %22 = OpLabel
846 %23 = OpPhi %8 %10 %21 %24 %25
847 OpLoopMerge %26 %25 None
848 OpBranch %27
849 %27 = OpLabel
850 %28 = OpSLessThan %12 %23 %11
851 OpBranchConditional %28 %29 %26
852 %29 = OpLabel
853 %30 = OpAccessChain %18 %3 %23
854 %31 = OpLoad %13 %30
855 %32 = OpAccessChain %18 %3 %23
856 OpStore %32 %31
857 OpBranch %25
858 %25 = OpLabel
859 %24 = OpISub %8 %23 %19
860 OpStore %5 %24
861 OpBranch %22
862 %26 = OpLabel
863 OpReturn
864 OpFunctionEnd
865 )";
866 std::unique_ptr<IRContext> context =
867 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
868 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
869 Module* module = context->module();
870 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
871 << text << std::endl;
872 const Function* f = spvtest::GetFunction(module, 2);
873 ScalarEvolutionAnalysis analysis{context.get()};
874
875 const Instruction* loads[1] = {nullptr};
876 int load_count = 0;
877
878 for (const Instruction& inst : *spvtest::GetBasicBlock(f, 29)) {
879 if (inst.opcode() == spv::Op::OpLoad) {
880 loads[load_count] = &inst;
881 ++load_count;
882 }
883 }
884
885 EXPECT_EQ(load_count, 1);
886
887 Instruction* load_access_chain =
888 context->get_def_use_mgr()->GetDef(loads[0]->GetSingleWordInOperand(0));
889 Instruction* load_child = context->get_def_use_mgr()->GetDef(
890 load_access_chain->GetSingleWordInOperand(1));
891
892 SENode* load_node = analysis.AnalyzeInstruction(load_child);
893
894 EXPECT_TRUE(load_node);
895 EXPECT_EQ(load_node->GetType(), SENode::RecurrentAddExpr);
896 EXPECT_TRUE(load_node->AsSERecurrentNode());
897
898 SENode* child_1 = load_node->AsSERecurrentNode()->GetCoefficient();
899 SENode* child_2 = load_node->AsSERecurrentNode()->GetOffset();
900
901 EXPECT_EQ(child_1->GetType(), SENode::Constant);
902 EXPECT_EQ(child_2->GetType(), SENode::Constant);
903
904 EXPECT_EQ(child_1->AsSEConstantNode()->FoldToSingleValue(), -1);
905 EXPECT_EQ(child_2->AsSEConstantNode()->FoldToSingleValue(), 0u);
906
907 SERecurrentNode* load_simplified =
908 analysis.SimplifyExpression(load_node)->AsSERecurrentNode();
909
910 EXPECT_TRUE(load_simplified);
911 EXPECT_EQ(load_node, load_simplified);
912
913 EXPECT_EQ(load_simplified->GetType(), SENode::RecurrentAddExpr);
914 EXPECT_TRUE(load_simplified->AsSERecurrentNode());
915
916 SENode* simplified_child_1 =
917 load_simplified->AsSERecurrentNode()->GetCoefficient();
918 SENode* simplified_child_2 =
919 load_simplified->AsSERecurrentNode()->GetOffset();
920
921 EXPECT_EQ(child_1, simplified_child_1);
922 EXPECT_EQ(child_2, simplified_child_2);
923 }
924
925 /*
926 Generated from the following GLSL + --eliminate-local-multi-store
927
928 #version 430
929 void main(void) {
930 for (int i = 0; i < 10; --i) {
931 array[i] = array[i];
932 }
933 }
934
935 */
936
TEST_F(ScalarAnalysisTest,SimplifyInductionsAndLoads)937 TEST_F(ScalarAnalysisTest, SimplifyInductionsAndLoads) {
938 const std::string text = R"(
939 OpCapability Shader
940 %1 = OpExtInstImport "GLSL.std.450"
941 OpMemoryModel Logical GLSL450
942 OpEntryPoint Fragment %2 "main" %3 %4
943 OpExecutionMode %2 OriginUpperLeft
944 OpSource GLSL 430
945 OpName %2 "main"
946 OpName %5 "i"
947 OpName %3 "array"
948 OpName %4 "N"
949 OpDecorate %3 Location 1
950 OpDecorate %4 Flat
951 OpDecorate %4 Location 2
952 %6 = OpTypeVoid
953 %7 = OpTypeFunction %6
954 %8 = OpTypeInt 32 1
955 %9 = OpTypePointer Function %8
956 %10 = OpConstant %8 0
957 %11 = OpConstant %8 10
958 %12 = OpTypeBool
959 %13 = OpTypeFloat 32
960 %14 = OpTypeInt 32 0
961 %15 = OpConstant %14 10
962 %16 = OpTypeArray %13 %15
963 %17 = OpTypePointer Output %16
964 %3 = OpVariable %17 Output
965 %18 = OpConstant %8 2
966 %19 = OpTypePointer Input %8
967 %4 = OpVariable %19 Input
968 %20 = OpTypePointer Output %13
969 %21 = OpConstant %8 1
970 %2 = OpFunction %6 None %7
971 %22 = OpLabel
972 %5 = OpVariable %9 Function
973 OpStore %5 %10
974 OpBranch %23
975 %23 = OpLabel
976 %24 = OpPhi %8 %10 %22 %25 %26
977 OpLoopMerge %27 %26 None
978 OpBranch %28
979 %28 = OpLabel
980 %29 = OpSLessThan %12 %24 %11
981 OpBranchConditional %29 %30 %27
982 %30 = OpLabel
983 %31 = OpLoad %8 %4
984 %32 = OpIMul %8 %18 %31
985 %33 = OpIAdd %8 %24 %32
986 %35 = OpIAdd %8 %24 %31
987 %36 = OpAccessChain %20 %3 %35
988 %37 = OpLoad %13 %36
989 %38 = OpAccessChain %20 %3 %33
990 OpStore %38 %37
991 %39 = OpIMul %8 %18 %24
992 %41 = OpIMul %8 %18 %31
993 %42 = OpIAdd %8 %39 %41
994 %43 = OpIAdd %8 %42 %21
995 %44 = OpIMul %8 %18 %24
996 %46 = OpIAdd %8 %44 %31
997 %47 = OpIAdd %8 %46 %21
998 %48 = OpAccessChain %20 %3 %47
999 %49 = OpLoad %13 %48
1000 %50 = OpAccessChain %20 %3 %43
1001 OpStore %50 %49
1002 OpBranch %26
1003 %26 = OpLabel
1004 %25 = OpISub %8 %24 %21
1005 OpStore %5 %25
1006 OpBranch %23
1007 %27 = OpLabel
1008 OpReturn
1009 OpFunctionEnd
1010 )";
1011 std::unique_ptr<IRContext> context =
1012 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
1013 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
1014 Module* module = context->module();
1015 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
1016 << text << std::endl;
1017 const Function* f = spvtest::GetFunction(module, 2);
1018 ScalarEvolutionAnalysis analysis{context.get()};
1019
1020 std::vector<const Instruction*> loads{};
1021 std::vector<const Instruction*> stores{};
1022
1023 for (const Instruction& inst : *spvtest::GetBasicBlock(f, 30)) {
1024 if (inst.opcode() == spv::Op::OpLoad) {
1025 loads.push_back(&inst);
1026 }
1027 if (inst.opcode() == spv::Op::OpStore) {
1028 stores.push_back(&inst);
1029 }
1030 }
1031
1032 EXPECT_EQ(loads.size(), 3u);
1033 EXPECT_EQ(stores.size(), 2u);
1034 {
1035 Instruction* store_access_chain = context->get_def_use_mgr()->GetDef(
1036 stores[0]->GetSingleWordInOperand(0));
1037
1038 Instruction* store_child = context->get_def_use_mgr()->GetDef(
1039 store_access_chain->GetSingleWordInOperand(1));
1040
1041 SENode* store_node = analysis.AnalyzeInstruction(store_child);
1042
1043 SENode* store_simplified = analysis.SimplifyExpression(store_node);
1044
1045 Instruction* load_access_chain =
1046 context->get_def_use_mgr()->GetDef(loads[1]->GetSingleWordInOperand(0));
1047
1048 Instruction* load_child = context->get_def_use_mgr()->GetDef(
1049 load_access_chain->GetSingleWordInOperand(1));
1050
1051 SENode* load_node = analysis.AnalyzeInstruction(load_child);
1052
1053 SENode* load_simplified = analysis.SimplifyExpression(load_node);
1054
1055 SENode* difference =
1056 analysis.CreateSubtraction(store_simplified, load_simplified);
1057
1058 SENode* difference_simplified = analysis.SimplifyExpression(difference);
1059
1060 // Check that i+2*N - i*N, turns into just N when both sides have already
1061 // been simplified into a single recurrent expression.
1062 EXPECT_EQ(difference_simplified->GetType(), SENode::ValueUnknown);
1063
1064 // Check that the inverse, i*N - i+2*N turns into -N.
1065 SENode* difference_inverse = analysis.SimplifyExpression(
1066 analysis.CreateSubtraction(load_simplified, store_simplified));
1067
1068 EXPECT_EQ(difference_inverse->GetType(), SENode::Negative);
1069 EXPECT_EQ(difference_inverse->GetChild(0)->GetType(), SENode::ValueUnknown);
1070 EXPECT_EQ(difference_inverse->GetChild(0), difference_simplified);
1071 }
1072
1073 {
1074 Instruction* store_access_chain = context->get_def_use_mgr()->GetDef(
1075 stores[1]->GetSingleWordInOperand(0));
1076
1077 Instruction* store_child = context->get_def_use_mgr()->GetDef(
1078 store_access_chain->GetSingleWordInOperand(1));
1079 SENode* store_node = analysis.AnalyzeInstruction(store_child);
1080 SENode* store_simplified = analysis.SimplifyExpression(store_node);
1081
1082 Instruction* load_access_chain =
1083 context->get_def_use_mgr()->GetDef(loads[2]->GetSingleWordInOperand(0));
1084
1085 Instruction* load_child = context->get_def_use_mgr()->GetDef(
1086 load_access_chain->GetSingleWordInOperand(1));
1087
1088 SENode* load_node = analysis.AnalyzeInstruction(load_child);
1089
1090 SENode* load_simplified = analysis.SimplifyExpression(load_node);
1091
1092 SENode* difference =
1093 analysis.CreateSubtraction(store_simplified, load_simplified);
1094 SENode* difference_simplified = analysis.SimplifyExpression(difference);
1095
1096 // Check that 2*i + 2*N + 1 - 2*i + N + 1, turns into just N when both
1097 // sides have already been simplified into a single recurrent expression.
1098 EXPECT_EQ(difference_simplified->GetType(), SENode::ValueUnknown);
1099
1100 // Check that the inverse, (2*i + N + 1) - (2*i + 2*N + 1) turns into -N.
1101 SENode* difference_inverse = analysis.SimplifyExpression(
1102 analysis.CreateSubtraction(load_simplified, store_simplified));
1103
1104 EXPECT_EQ(difference_inverse->GetType(), SENode::Negative);
1105 EXPECT_EQ(difference_inverse->GetChild(0)->GetType(), SENode::ValueUnknown);
1106 EXPECT_EQ(difference_inverse->GetChild(0), difference_simplified);
1107 }
1108 }
1109
1110 /* Generated from the following GLSL + --eliminate-local-multi-store
1111
1112 #version 430
1113 layout(location = 1) out float array[10];
1114 layout(location = 2) flat in int N;
1115 void main(void) {
1116 int step = 0;
1117 for (int i = 0; i < N; i += step) {
1118 step++;
1119 }
1120 }
1121 */
TEST_F(ScalarAnalysisTest,InductionWithVariantStep)1122 TEST_F(ScalarAnalysisTest, InductionWithVariantStep) {
1123 const std::string text = R"(
1124 OpCapability Shader
1125 %1 = OpExtInstImport "GLSL.std.450"
1126 OpMemoryModel Logical GLSL450
1127 OpEntryPoint Fragment %2 "main" %3 %4
1128 OpExecutionMode %2 OriginUpperLeft
1129 OpSource GLSL 430
1130 OpName %2 "main"
1131 OpName %5 "step"
1132 OpName %6 "i"
1133 OpName %3 "N"
1134 OpName %4 "array"
1135 OpDecorate %3 Flat
1136 OpDecorate %3 Location 2
1137 OpDecorate %4 Location 1
1138 %7 = OpTypeVoid
1139 %8 = OpTypeFunction %7
1140 %9 = OpTypeInt 32 1
1141 %10 = OpTypePointer Function %9
1142 %11 = OpConstant %9 0
1143 %12 = OpTypePointer Input %9
1144 %3 = OpVariable %12 Input
1145 %13 = OpTypeBool
1146 %14 = OpConstant %9 1
1147 %15 = OpTypeFloat 32
1148 %16 = OpTypeInt 32 0
1149 %17 = OpConstant %16 10
1150 %18 = OpTypeArray %15 %17
1151 %19 = OpTypePointer Output %18
1152 %4 = OpVariable %19 Output
1153 %2 = OpFunction %7 None %8
1154 %20 = OpLabel
1155 %5 = OpVariable %10 Function
1156 %6 = OpVariable %10 Function
1157 OpStore %5 %11
1158 OpStore %6 %11
1159 OpBranch %21
1160 %21 = OpLabel
1161 %22 = OpPhi %9 %11 %20 %23 %24
1162 %25 = OpPhi %9 %11 %20 %26 %24
1163 OpLoopMerge %27 %24 None
1164 OpBranch %28
1165 %28 = OpLabel
1166 %29 = OpLoad %9 %3
1167 %30 = OpSLessThan %13 %25 %29
1168 OpBranchConditional %30 %31 %27
1169 %31 = OpLabel
1170 %23 = OpIAdd %9 %22 %14
1171 OpStore %5 %23
1172 OpBranch %24
1173 %24 = OpLabel
1174 %26 = OpIAdd %9 %25 %23
1175 OpStore %6 %26
1176 OpBranch %21
1177 %27 = OpLabel
1178 OpReturn
1179 OpFunctionEnd
1180 )";
1181 std::unique_ptr<IRContext> context =
1182 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text,
1183 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
1184 Module* module = context->module();
1185 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n"
1186 << text << std::endl;
1187 const Function* f = spvtest::GetFunction(module, 2);
1188 ScalarEvolutionAnalysis analysis{context.get()};
1189
1190 std::vector<const Instruction*> phis{};
1191
1192 for (const Instruction& inst : *spvtest::GetBasicBlock(f, 21)) {
1193 if (inst.opcode() == spv::Op::OpPhi) {
1194 phis.push_back(&inst);
1195 }
1196 }
1197
1198 EXPECT_EQ(phis.size(), 2u);
1199 SENode* phi_node_1 = analysis.AnalyzeInstruction(phis[0]);
1200 SENode* phi_node_2 = analysis.AnalyzeInstruction(phis[1]);
1201 EXPECT_NE(phi_node_1, nullptr);
1202 EXPECT_NE(phi_node_2, nullptr);
1203
1204 EXPECT_EQ(phi_node_1->GetType(), SENode::RecurrentAddExpr);
1205 EXPECT_EQ(phi_node_2->GetType(), SENode::CanNotCompute);
1206
1207 SENode* simplified_1 = analysis.SimplifyExpression(phi_node_1);
1208 SENode* simplified_2 = analysis.SimplifyExpression(phi_node_2);
1209
1210 EXPECT_EQ(simplified_1->GetType(), SENode::RecurrentAddExpr);
1211 EXPECT_EQ(simplified_2->GetType(), SENode::CanNotCompute);
1212 }
1213
1214 } // namespace
1215 } // namespace opt
1216 } // namespace spvtools
1217