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 <string>
16 #include <utility>
17 #include <vector>
18 
19 #include "gmock/gmock.h"
20 #include "source/opt/loop_descriptor.h"
21 #include "source/opt/loop_peeling.h"
22 #include "test/opt/pass_fixture.h"
23 
24 namespace spvtools {
25 namespace opt {
26 namespace {
27 
28 class PeelingPassTest : public PassTest<::testing::Test> {
29  public:
30   // Generic routine to run the loop peeling pass and check
AssembleAndRunPeelingTest(const std::string & text_head,const std::string & text_tail,spv::Op opcode,const std::string & res_id,const std::string & op1,const std::string & op2)31   LoopPeelingPass::LoopPeelingStats AssembleAndRunPeelingTest(
32       const std::string& text_head, const std::string& text_tail,
33       spv::Op opcode, const std::string& res_id, const std::string& op1,
34       const std::string& op2) {
35     std::string opcode_str;
36     switch (opcode) {
37       case spv::Op::OpSLessThan:
38         opcode_str = "OpSLessThan";
39         break;
40       case spv::Op::OpSGreaterThan:
41         opcode_str = "OpSGreaterThan";
42         break;
43       case spv::Op::OpSLessThanEqual:
44         opcode_str = "OpSLessThanEqual";
45         break;
46       case spv::Op::OpSGreaterThanEqual:
47         opcode_str = "OpSGreaterThanEqual";
48         break;
49       case spv::Op::OpIEqual:
50         opcode_str = "OpIEqual";
51         break;
52       case spv::Op::OpINotEqual:
53         opcode_str = "OpINotEqual";
54         break;
55       default:
56         assert(false && "Unhandled");
57         break;
58     }
59     std::string test_cond =
60         res_id + " = " + opcode_str + "  %bool " + op1 + " " + op2 + "\n";
61 
62     LoopPeelingPass::LoopPeelingStats stats;
63     SinglePassRunAndDisassemble<LoopPeelingPass>(
64         text_head + test_cond + text_tail, true, true, &stats);
65 
66     return stats;
67   }
68 
69   // Generic routine to run the loop peeling pass and check
RunPeelingTest(const std::string & text_head,const std::string & text_tail,spv::Op opcode,const std::string & res_id,const std::string & op1,const std::string & op2,size_t nb_of_loops)70   LoopPeelingPass::LoopPeelingStats RunPeelingTest(
71       const std::string& text_head, const std::string& text_tail,
72       spv::Op opcode, const std::string& res_id, const std::string& op1,
73       const std::string& op2, size_t nb_of_loops) {
74     LoopPeelingPass::LoopPeelingStats stats = AssembleAndRunPeelingTest(
75         text_head, text_tail, opcode, res_id, op1, op2);
76 
77     Function& f = *context()->module()->begin();
78     LoopDescriptor& ld = *context()->GetLoopDescriptor(&f);
79     EXPECT_EQ(ld.NumLoops(), nb_of_loops);
80 
81     return stats;
82   }
83 
84   using PeelTraceType =
85       std::vector<std::pair<LoopPeelingPass::PeelDirection, uint32_t>>;
86 
BuildAndCheckTrace(const std::string & text_head,const std::string & text_tail,spv::Op opcode,const std::string & res_id,const std::string & op1,const std::string & op2,const PeelTraceType & expected_peel_trace,size_t expected_nb_of_loops)87   void BuildAndCheckTrace(const std::string& text_head,
88                           const std::string& text_tail, spv::Op opcode,
89                           const std::string& res_id, const std::string& op1,
90                           const std::string& op2,
91                           const PeelTraceType& expected_peel_trace,
92                           size_t expected_nb_of_loops) {
93     auto stats = RunPeelingTest(text_head, text_tail, opcode, res_id, op1, op2,
94                                 expected_nb_of_loops);
95 
96     EXPECT_EQ(stats.peeled_loops_.size(), expected_peel_trace.size());
97     if (stats.peeled_loops_.size() != expected_peel_trace.size()) {
98       return;
99     }
100 
101     PeelTraceType::const_iterator expected_trace_it =
102         expected_peel_trace.begin();
103     decltype(stats.peeled_loops_)::const_iterator stats_it =
104         stats.peeled_loops_.begin();
105 
106     while (expected_trace_it != expected_peel_trace.end()) {
107       EXPECT_EQ(expected_trace_it->first, std::get<1>(*stats_it));
108       EXPECT_EQ(expected_trace_it->second, std::get<2>(*stats_it));
109       ++expected_trace_it;
110       ++stats_it;
111     }
112   }
113 };
114 
115 /*
116 Test are derivation of the following generated test from the following GLSL +
117 --eliminate-local-multi-store
118 
119 #version 330 core
120 void main() {
121   int a = 0;
122   for(int i = 1; i < 10; i += 2) {
123     if (i < 3) {
124       a += 2;
125     }
126   }
127 }
128 
129 The condition is interchanged to test < > <= >= == and peel before/after
130 opportunities.
131 */
TEST_F(PeelingPassTest,PeelingPassBasic)132 TEST_F(PeelingPassTest, PeelingPassBasic) {
133   const std::string text_head = R"(
134                OpCapability Shader
135           %1 = OpExtInstImport "GLSL.std.450"
136                OpMemoryModel Logical GLSL450
137                OpEntryPoint Fragment %main "main"
138                OpExecutionMode %main OriginLowerLeft
139                OpSource GLSL 330
140                OpName %main "main"
141                OpName %a "a"
142                OpName %i "i"
143        %void = OpTypeVoid
144           %3 = OpTypeFunction %void
145         %int = OpTypeInt 32 1
146 %_ptr_Function_int = OpTypePointer Function %int
147        %bool = OpTypeBool
148      %int_20 = OpConstant %int 20
149      %int_19 = OpConstant %int 19
150      %int_18 = OpConstant %int 18
151      %int_17 = OpConstant %int 17
152      %int_16 = OpConstant %int 16
153      %int_15 = OpConstant %int 15
154      %int_14 = OpConstant %int 14
155      %int_13 = OpConstant %int 13
156      %int_12 = OpConstant %int 12
157      %int_11 = OpConstant %int 11
158      %int_10 = OpConstant %int 10
159       %int_9 = OpConstant %int 9
160       %int_8 = OpConstant %int 8
161       %int_7 = OpConstant %int 7
162       %int_6 = OpConstant %int 6
163       %int_5 = OpConstant %int 5
164       %int_4 = OpConstant %int 4
165       %int_3 = OpConstant %int 3
166       %int_2 = OpConstant %int 2
167       %int_1 = OpConstant %int 1
168       %int_0 = OpConstant %int 0
169        %main = OpFunction %void None %3
170           %5 = OpLabel
171           %a = OpVariable %_ptr_Function_int Function
172           %i = OpVariable %_ptr_Function_int Function
173                OpStore %a %int_0
174                OpStore %i %int_0
175                OpBranch %11
176          %11 = OpLabel
177          %31 = OpPhi %int %int_0 %5 %33 %14
178          %32 = OpPhi %int %int_1 %5 %30 %14
179                OpLoopMerge %13 %14 None
180                OpBranch %15
181          %15 = OpLabel
182          %19 = OpSLessThan %bool %32 %int_20
183                OpBranchConditional %19 %12 %13
184          %12 = OpLabel
185   )";
186   const std::string text_tail = R"(
187                OpSelectionMerge %24 None
188                OpBranchConditional %22 %23 %24
189          %23 = OpLabel
190          %27 = OpIAdd %int %31 %int_2
191                OpStore %a %27
192                OpBranch %24
193          %24 = OpLabel
194          %33 = OpPhi %int %31 %12 %27 %23
195                OpBranch %14
196          %14 = OpLabel
197          %30 = OpIAdd %int %32 %int_2
198                OpStore %i %30
199                OpBranch %11
200          %13 = OpLabel
201                OpReturn
202                OpFunctionEnd
203   )";
204 
205   auto run_test = [&text_head, &text_tail, this](spv::Op opcode,
206                                                  const std::string& op1,
207                                                  const std::string& op2) {
208     auto stats =
209         RunPeelingTest(text_head, text_tail, opcode, "%22", op1, op2, 2);
210 
211     EXPECT_EQ(stats.peeled_loops_.size(), 1u);
212     if (stats.peeled_loops_.size() != 1u)
213       return std::pair<LoopPeelingPass::PeelDirection, uint32_t>{
214           LoopPeelingPass::PeelDirection::kNone, 0};
215 
216     return std::pair<LoopPeelingPass::PeelDirection, uint32_t>{
217         std::get<1>(*stats.peeled_loops_.begin()),
218         std::get<2>(*stats.peeled_loops_.begin())};
219   };
220 
221   // Test LT
222   // Peel before by a factor of 2.
223   {
224     SCOPED_TRACE("Peel before iv < 4");
225 
226     std::pair<LoopPeelingPass::PeelDirection, uint32_t> peel_info =
227         run_test(spv::Op::OpSLessThan, "%32", "%int_4");
228     EXPECT_EQ(peel_info.first, LoopPeelingPass::PeelDirection::kBefore);
229     EXPECT_EQ(peel_info.second, 2u);
230   }
231   {
232     SCOPED_TRACE("Peel before 4 > iv");
233 
234     std::pair<LoopPeelingPass::PeelDirection, uint32_t> peel_info =
235         run_test(spv::Op::OpSGreaterThan, "%int_4", "%32");
236     EXPECT_EQ(peel_info.first, LoopPeelingPass::PeelDirection::kBefore);
237     EXPECT_EQ(peel_info.second, 2u);
238   }
239   {
240     SCOPED_TRACE("Peel before iv < 5");
241 
242     std::pair<LoopPeelingPass::PeelDirection, uint32_t> peel_info =
243         run_test(spv::Op::OpSLessThan, "%32", "%int_5");
244     EXPECT_EQ(peel_info.first, LoopPeelingPass::PeelDirection::kBefore);
245     EXPECT_EQ(peel_info.second, 2u);
246   }
247   {
248     SCOPED_TRACE("Peel before 5 > iv");
249 
250     std::pair<LoopPeelingPass::PeelDirection, uint32_t> peel_info =
251         run_test(spv::Op::OpSGreaterThan, "%int_5", "%32");
252     EXPECT_EQ(peel_info.first, LoopPeelingPass::PeelDirection::kBefore);
253     EXPECT_EQ(peel_info.second, 2u);
254   }
255 
256   // Peel after by a factor of 2.
257   {
258     SCOPED_TRACE("Peel after iv < 16");
259 
260     std::pair<LoopPeelingPass::PeelDirection, uint32_t> peel_info =
261         run_test(spv::Op::OpSLessThan, "%32", "%int_16");
262     EXPECT_EQ(peel_info.first, LoopPeelingPass::PeelDirection::kAfter);
263     EXPECT_EQ(peel_info.second, 2u);
264   }
265   {
266     SCOPED_TRACE("Peel after 16 > iv");
267 
268     std::pair<LoopPeelingPass::PeelDirection, uint32_t> peel_info =
269         run_test(spv::Op::OpSGreaterThan, "%int_16", "%32");
270     EXPECT_EQ(peel_info.first, LoopPeelingPass::PeelDirection::kAfter);
271     EXPECT_EQ(peel_info.second, 2u);
272   }
273   {
274     SCOPED_TRACE("Peel after iv < 17");
275 
276     std::pair<LoopPeelingPass::PeelDirection, uint32_t> peel_info =
277         run_test(spv::Op::OpSLessThan, "%32", "%int_17");
278     EXPECT_EQ(peel_info.first, LoopPeelingPass::PeelDirection::kAfter);
279     EXPECT_EQ(peel_info.second, 2u);
280   }
281   {
282     SCOPED_TRACE("Peel after 17 > iv");
283 
284     std::pair<LoopPeelingPass::PeelDirection, uint32_t> peel_info =
285         run_test(spv::Op::OpSGreaterThan, "%int_17", "%32");
286     EXPECT_EQ(peel_info.first, LoopPeelingPass::PeelDirection::kAfter);
287     EXPECT_EQ(peel_info.second, 2u);
288   }
289 
290   // Test GT
291   // Peel before by a factor of 2.
292   {
293     SCOPED_TRACE("Peel before iv > 5");
294 
295     std::pair<LoopPeelingPass::PeelDirection, uint32_t> peel_info =
296         run_test(spv::Op::OpSGreaterThan, "%32", "%int_5");
297     EXPECT_EQ(peel_info.first, LoopPeelingPass::PeelDirection::kBefore);
298     EXPECT_EQ(peel_info.second, 2u);
299   }
300   {
301     SCOPED_TRACE("Peel before 5 < iv");
302 
303     std::pair<LoopPeelingPass::PeelDirection, uint32_t> peel_info =
304         run_test(spv::Op::OpSLessThan, "%int_5", "%32");
305     EXPECT_EQ(peel_info.first, LoopPeelingPass::PeelDirection::kBefore);
306     EXPECT_EQ(peel_info.second, 2u);
307   }
308   {
309     SCOPED_TRACE("Peel before iv > 4");
310 
311     std::pair<LoopPeelingPass::PeelDirection, uint32_t> peel_info =
312         run_test(spv::Op::OpSGreaterThan, "%32", "%int_4");
313     EXPECT_EQ(peel_info.first, LoopPeelingPass::PeelDirection::kBefore);
314     EXPECT_EQ(peel_info.second, 2u);
315   }
316   {
317     SCOPED_TRACE("Peel before 4 < iv");
318 
319     std::pair<LoopPeelingPass::PeelDirection, uint32_t> peel_info =
320         run_test(spv::Op::OpSLessThan, "%int_4", "%32");
321     EXPECT_EQ(peel_info.first, LoopPeelingPass::PeelDirection::kBefore);
322     EXPECT_EQ(peel_info.second, 2u);
323   }
324 
325   // Peel after by a factor of 2.
326   {
327     SCOPED_TRACE("Peel after iv > 16");
328 
329     std::pair<LoopPeelingPass::PeelDirection, uint32_t> peel_info =
330         run_test(spv::Op::OpSGreaterThan, "%32", "%int_16");
331     EXPECT_EQ(peel_info.first, LoopPeelingPass::PeelDirection::kAfter);
332     EXPECT_EQ(peel_info.second, 2u);
333   }
334   {
335     SCOPED_TRACE("Peel after 16 < iv");
336 
337     std::pair<LoopPeelingPass::PeelDirection, uint32_t> peel_info =
338         run_test(spv::Op::OpSLessThan, "%int_16", "%32");
339     EXPECT_EQ(peel_info.first, LoopPeelingPass::PeelDirection::kAfter);
340     EXPECT_EQ(peel_info.second, 2u);
341   }
342   {
343     SCOPED_TRACE("Peel after iv > 17");
344 
345     std::pair<LoopPeelingPass::PeelDirection, uint32_t> peel_info =
346         run_test(spv::Op::OpSGreaterThan, "%32", "%int_17");
347     EXPECT_EQ(peel_info.first, LoopPeelingPass::PeelDirection::kAfter);
348     EXPECT_EQ(peel_info.second, 2u);
349   }
350   {
351     SCOPED_TRACE("Peel after 17 < iv");
352 
353     std::pair<LoopPeelingPass::PeelDirection, uint32_t> peel_info =
354         run_test(spv::Op::OpSLessThan, "%int_17", "%32");
355     EXPECT_EQ(peel_info.first, LoopPeelingPass::PeelDirection::kAfter);
356     EXPECT_EQ(peel_info.second, 2u);
357   }
358 
359   // Test LE
360   // Peel before by a factor of 2.
361   {
362     SCOPED_TRACE("Peel before iv <= 4");
363 
364     std::pair<LoopPeelingPass::PeelDirection, uint32_t> peel_info =
365         run_test(spv::Op::OpSLessThanEqual, "%32", "%int_4");
366     EXPECT_EQ(peel_info.first, LoopPeelingPass::PeelDirection::kBefore);
367     EXPECT_EQ(peel_info.second, 2u);
368   }
369   {
370     SCOPED_TRACE("Peel before 4 => iv");
371 
372     std::pair<LoopPeelingPass::PeelDirection, uint32_t> peel_info =
373         run_test(spv::Op::OpSGreaterThanEqual, "%int_4", "%32");
374     EXPECT_EQ(peel_info.first, LoopPeelingPass::PeelDirection::kBefore);
375     EXPECT_EQ(peel_info.second, 2u);
376   }
377   {
378     SCOPED_TRACE("Peel before iv <= 3");
379 
380     std::pair<LoopPeelingPass::PeelDirection, uint32_t> peel_info =
381         run_test(spv::Op::OpSLessThanEqual, "%32", "%int_3");
382     EXPECT_EQ(peel_info.first, LoopPeelingPass::PeelDirection::kBefore);
383     EXPECT_EQ(peel_info.second, 2u);
384   }
385   {
386     SCOPED_TRACE("Peel before 3 => iv");
387 
388     std::pair<LoopPeelingPass::PeelDirection, uint32_t> peel_info =
389         run_test(spv::Op::OpSGreaterThanEqual, "%int_3", "%32");
390     EXPECT_EQ(peel_info.first, LoopPeelingPass::PeelDirection::kBefore);
391     EXPECT_EQ(peel_info.second, 2u);
392   }
393 
394   // Peel after by a factor of 2.
395   {
396     SCOPED_TRACE("Peel after iv <= 16");
397 
398     std::pair<LoopPeelingPass::PeelDirection, uint32_t> peel_info =
399         run_test(spv::Op::OpSLessThanEqual, "%32", "%int_16");
400     EXPECT_EQ(peel_info.first, LoopPeelingPass::PeelDirection::kAfter);
401     EXPECT_EQ(peel_info.second, 2u);
402   }
403   {
404     SCOPED_TRACE("Peel after 16 => iv");
405 
406     std::pair<LoopPeelingPass::PeelDirection, uint32_t> peel_info =
407         run_test(spv::Op::OpSGreaterThanEqual, "%int_16", "%32");
408     EXPECT_EQ(peel_info.first, LoopPeelingPass::PeelDirection::kAfter);
409     EXPECT_EQ(peel_info.second, 2u);
410   }
411   {
412     SCOPED_TRACE("Peel after iv <= 15");
413 
414     std::pair<LoopPeelingPass::PeelDirection, uint32_t> peel_info =
415         run_test(spv::Op::OpSLessThanEqual, "%32", "%int_15");
416     EXPECT_EQ(peel_info.first, LoopPeelingPass::PeelDirection::kAfter);
417     EXPECT_EQ(peel_info.second, 2u);
418   }
419   {
420     SCOPED_TRACE("Peel after 15 => iv");
421 
422     std::pair<LoopPeelingPass::PeelDirection, uint32_t> peel_info =
423         run_test(spv::Op::OpSGreaterThanEqual, "%int_15", "%32");
424     EXPECT_EQ(peel_info.first, LoopPeelingPass::PeelDirection::kAfter);
425     EXPECT_EQ(peel_info.second, 2u);
426   }
427 
428   // Test GE
429   // Peel before by a factor of 2.
430   {
431     SCOPED_TRACE("Peel before iv >= 5");
432 
433     std::pair<LoopPeelingPass::PeelDirection, uint32_t> peel_info =
434         run_test(spv::Op::OpSGreaterThanEqual, "%32", "%int_5");
435     EXPECT_EQ(peel_info.first, LoopPeelingPass::PeelDirection::kBefore);
436     EXPECT_EQ(peel_info.second, 2u);
437   }
438   {
439     SCOPED_TRACE("Peel before 35 >= iv");
440 
441     std::pair<LoopPeelingPass::PeelDirection, uint32_t> peel_info =
442         run_test(spv::Op::OpSLessThanEqual, "%int_5", "%32");
443     EXPECT_EQ(peel_info.first, LoopPeelingPass::PeelDirection::kBefore);
444     EXPECT_EQ(peel_info.second, 2u);
445   }
446   {
447     SCOPED_TRACE("Peel before iv >= 4");
448 
449     std::pair<LoopPeelingPass::PeelDirection, uint32_t> peel_info =
450         run_test(spv::Op::OpSGreaterThanEqual, "%32", "%int_4");
451     EXPECT_EQ(peel_info.first, LoopPeelingPass::PeelDirection::kBefore);
452     EXPECT_EQ(peel_info.second, 2u);
453   }
454   {
455     SCOPED_TRACE("Peel before 4 <= iv");
456 
457     std::pair<LoopPeelingPass::PeelDirection, uint32_t> peel_info =
458         run_test(spv::Op::OpSLessThanEqual, "%int_4", "%32");
459     EXPECT_EQ(peel_info.first, LoopPeelingPass::PeelDirection::kBefore);
460     EXPECT_EQ(peel_info.second, 2u);
461   }
462 
463   // Peel after by a factor of 2.
464   {
465     SCOPED_TRACE("Peel after iv >= 17");
466 
467     std::pair<LoopPeelingPass::PeelDirection, uint32_t> peel_info =
468         run_test(spv::Op::OpSGreaterThanEqual, "%32", "%int_17");
469     EXPECT_EQ(peel_info.first, LoopPeelingPass::PeelDirection::kAfter);
470     EXPECT_EQ(peel_info.second, 2u);
471   }
472   {
473     SCOPED_TRACE("Peel after 17 <= iv");
474 
475     std::pair<LoopPeelingPass::PeelDirection, uint32_t> peel_info =
476         run_test(spv::Op::OpSLessThanEqual, "%int_17", "%32");
477     EXPECT_EQ(peel_info.first, LoopPeelingPass::PeelDirection::kAfter);
478     EXPECT_EQ(peel_info.second, 2u);
479   }
480   {
481     SCOPED_TRACE("Peel after iv >= 16");
482 
483     std::pair<LoopPeelingPass::PeelDirection, uint32_t> peel_info =
484         run_test(spv::Op::OpSGreaterThanEqual, "%32", "%int_16");
485     EXPECT_EQ(peel_info.first, LoopPeelingPass::PeelDirection::kAfter);
486     EXPECT_EQ(peel_info.second, 2u);
487   }
488   {
489     SCOPED_TRACE("Peel after 16 <= iv");
490 
491     std::pair<LoopPeelingPass::PeelDirection, uint32_t> peel_info =
492         run_test(spv::Op::OpSLessThanEqual, "%int_16", "%32");
493     EXPECT_EQ(peel_info.first, LoopPeelingPass::PeelDirection::kAfter);
494     EXPECT_EQ(peel_info.second, 2u);
495   }
496 
497   // Test EQ
498   // Peel before by a factor of 1.
499   {
500     SCOPED_TRACE("Peel before iv == 1");
501 
502     std::pair<LoopPeelingPass::PeelDirection, uint32_t> peel_info =
503         run_test(spv::Op::OpIEqual, "%32", "%int_1");
504     EXPECT_EQ(peel_info.first, LoopPeelingPass::PeelDirection::kBefore);
505     EXPECT_EQ(peel_info.second, 1u);
506   }
507   {
508     SCOPED_TRACE("Peel before 1 == iv");
509 
510     std::pair<LoopPeelingPass::PeelDirection, uint32_t> peel_info =
511         run_test(spv::Op::OpIEqual, "%int_1", "%32");
512     EXPECT_EQ(peel_info.first, LoopPeelingPass::PeelDirection::kBefore);
513     EXPECT_EQ(peel_info.second, 1u);
514   }
515 
516   // Peel after by a factor of 1.
517   {
518     SCOPED_TRACE("Peel after iv == 19");
519 
520     std::pair<LoopPeelingPass::PeelDirection, uint32_t> peel_info =
521         run_test(spv::Op::OpIEqual, "%32", "%int_19");
522     EXPECT_EQ(peel_info.first, LoopPeelingPass::PeelDirection::kAfter);
523     EXPECT_EQ(peel_info.second, 1u);
524   }
525   {
526     SCOPED_TRACE("Peel after 19 == iv");
527 
528     std::pair<LoopPeelingPass::PeelDirection, uint32_t> peel_info =
529         run_test(spv::Op::OpIEqual, "%int_19", "%32");
530     EXPECT_EQ(peel_info.first, LoopPeelingPass::PeelDirection::kAfter);
531     EXPECT_EQ(peel_info.second, 1u);
532   }
533 
534   // Test NE
535   // Peel before by a factor of 1.
536   {
537     SCOPED_TRACE("Peel before iv != 1");
538 
539     std::pair<LoopPeelingPass::PeelDirection, uint32_t> peel_info =
540         run_test(spv::Op::OpINotEqual, "%32", "%int_1");
541     EXPECT_EQ(peel_info.first, LoopPeelingPass::PeelDirection::kBefore);
542     EXPECT_EQ(peel_info.second, 1u);
543   }
544   {
545     SCOPED_TRACE("Peel before 1 != iv");
546 
547     std::pair<LoopPeelingPass::PeelDirection, uint32_t> peel_info =
548         run_test(spv::Op::OpINotEqual, "%int_1", "%32");
549     EXPECT_EQ(peel_info.first, LoopPeelingPass::PeelDirection::kBefore);
550     EXPECT_EQ(peel_info.second, 1u);
551   }
552 
553   // Peel after by a factor of 1.
554   {
555     SCOPED_TRACE("Peel after iv != 19");
556 
557     std::pair<LoopPeelingPass::PeelDirection, uint32_t> peel_info =
558         run_test(spv::Op::OpINotEqual, "%32", "%int_19");
559     EXPECT_EQ(peel_info.first, LoopPeelingPass::PeelDirection::kAfter);
560     EXPECT_EQ(peel_info.second, 1u);
561   }
562   {
563     SCOPED_TRACE("Peel after 19 != iv");
564 
565     std::pair<LoopPeelingPass::PeelDirection, uint32_t> peel_info =
566         run_test(spv::Op::OpINotEqual, "%int_19", "%32");
567     EXPECT_EQ(peel_info.first, LoopPeelingPass::PeelDirection::kAfter);
568     EXPECT_EQ(peel_info.second, 1u);
569   }
570 
571   // No peel.
572   {
573     SCOPED_TRACE("No Peel: 20 => iv");
574 
575     auto stats = RunPeelingTest(text_head, text_tail, spv::Op::OpSLessThanEqual,
576                                 "%22", "%int_20", "%32", 1);
577 
578     EXPECT_EQ(stats.peeled_loops_.size(), 0u);
579   }
580 }
581 
582 /*
583 Test are derivation of the following generated test from the following GLSL +
584 --eliminate-local-multi-store
585 
586 #version 330 core
587 void main() {
588   int a = 0;
589   for(int i = 0; i < 10; ++i) {
590     if (i < 3) {
591       a += 2;
592     }
593     if (i < 1) {
594       a += 2;
595     }
596   }
597 }
598 
599 The condition is interchanged to test < > <= >= == and peel before/after
600 opportunities.
601 */
TEST_F(PeelingPassTest,MultiplePeelingPass)602 TEST_F(PeelingPassTest, MultiplePeelingPass) {
603   const std::string text_head = R"(
604                OpCapability Shader
605           %1 = OpExtInstImport "GLSL.std.450"
606                OpMemoryModel Logical GLSL450
607                OpEntryPoint Fragment %main "main"
608                OpExecutionMode %main OriginLowerLeft
609                OpSource GLSL 330
610                OpName %main "main"
611                OpName %a "a"
612                OpName %i "i"
613        %void = OpTypeVoid
614           %3 = OpTypeFunction %void
615         %int = OpTypeInt 32 1
616 %_ptr_Function_int = OpTypePointer Function %int
617        %bool = OpTypeBool
618      %int_10 = OpConstant %int 10
619       %int_9 = OpConstant %int 9
620       %int_8 = OpConstant %int 8
621       %int_7 = OpConstant %int 7
622       %int_6 = OpConstant %int 6
623       %int_5 = OpConstant %int 5
624       %int_4 = OpConstant %int 4
625       %int_3 = OpConstant %int 3
626       %int_2 = OpConstant %int 2
627       %int_1 = OpConstant %int 1
628       %int_0 = OpConstant %int 0
629        %main = OpFunction %void None %3
630           %5 = OpLabel
631           %a = OpVariable %_ptr_Function_int Function
632           %i = OpVariable %_ptr_Function_int Function
633                OpStore %a %int_0
634                OpStore %i %int_0
635                OpBranch %11
636          %11 = OpLabel
637          %37 = OpPhi %int %int_0 %5 %40 %14
638          %38 = OpPhi %int %int_0 %5 %36 %14
639                OpLoopMerge %13 %14 None
640                OpBranch %15
641          %15 = OpLabel
642          %19 = OpSLessThan %bool %38 %int_10
643                OpBranchConditional %19 %12 %13
644          %12 = OpLabel
645   )";
646   const std::string text_tail = R"(
647                OpSelectionMerge %24 None
648                OpBranchConditional %22 %23 %24
649          %23 = OpLabel
650          %27 = OpIAdd %int %37 %int_2
651                OpStore %a %27
652                OpBranch %24
653          %24 = OpLabel
654          %39 = OpPhi %int %37 %12 %27 %23
655          %30 = OpSLessThan %bool %38 %int_1
656                OpSelectionMerge %32 None
657                OpBranchConditional %30 %31 %32
658          %31 = OpLabel
659          %34 = OpIAdd %int %39 %int_2
660                OpStore %a %34
661                OpBranch %32
662          %32 = OpLabel
663          %40 = OpPhi %int %39 %24 %34 %31
664                OpBranch %14
665          %14 = OpLabel
666          %36 = OpIAdd %int %38 %int_1
667                OpStore %i %36
668                OpBranch %11
669          %13 = OpLabel
670                OpReturn
671                OpFunctionEnd
672   )";
673 
674   auto run_test = [&text_head, &text_tail, this](
675                       spv::Op opcode, const std::string& op1,
676                       const std::string& op2,
677                       const PeelTraceType& expected_peel_trace) {
678     BuildAndCheckTrace(text_head, text_tail, opcode, "%22", op1, op2,
679                        expected_peel_trace, expected_peel_trace.size() + 1);
680   };
681 
682   // Test LT
683   // Peel before by a factor of 3.
684   {
685     SCOPED_TRACE("Peel before iv < 3");
686 
687     run_test(spv::Op::OpSLessThan, "%38", "%int_3",
688              {{LoopPeelingPass::PeelDirection::kBefore, 3u}});
689   }
690   {
691     SCOPED_TRACE("Peel before 3 > iv");
692 
693     run_test(spv::Op::OpSGreaterThan, "%int_3", "%38",
694              {{LoopPeelingPass::PeelDirection::kBefore, 3u}});
695   }
696 
697   // Peel after by a factor of 2.
698   {
699     SCOPED_TRACE("Peel after iv < 8");
700 
701     run_test(spv::Op::OpSLessThan, "%38", "%int_8",
702              {{LoopPeelingPass::PeelDirection::kAfter, 2u}});
703   }
704   {
705     SCOPED_TRACE("Peel after 8 > iv");
706 
707     run_test(spv::Op::OpSGreaterThan, "%int_8", "%38",
708              {{LoopPeelingPass::PeelDirection::kAfter, 2u}});
709   }
710 
711   // Test GT
712   // Peel before by a factor of 2.
713   {
714     SCOPED_TRACE("Peel before iv > 2");
715 
716     run_test(spv::Op::OpSGreaterThan, "%38", "%int_2",
717              {{LoopPeelingPass::PeelDirection::kBefore, 2u}});
718   }
719   {
720     SCOPED_TRACE("Peel before 2 < iv");
721 
722     run_test(spv::Op::OpSLessThan, "%int_2", "%38",
723              {{LoopPeelingPass::PeelDirection::kBefore, 2u}});
724   }
725 
726   // Peel after by a factor of 3.
727   {
728     SCOPED_TRACE("Peel after iv > 7");
729 
730     run_test(spv::Op::OpSGreaterThan, "%38", "%int_7",
731              {{LoopPeelingPass::PeelDirection::kAfter, 3u}});
732   }
733   {
734     SCOPED_TRACE("Peel after 7 < iv");
735 
736     run_test(spv::Op::OpSLessThan, "%int_7", "%38",
737              {{LoopPeelingPass::PeelDirection::kAfter, 3u}});
738   }
739 
740   // Test LE
741   // Peel before by a factor of 2.
742   {
743     SCOPED_TRACE("Peel before iv <= 1");
744 
745     run_test(spv::Op::OpSLessThanEqual, "%38", "%int_1",
746              {{LoopPeelingPass::PeelDirection::kBefore, 2u}});
747   }
748   {
749     SCOPED_TRACE("Peel before 1 => iv");
750 
751     run_test(spv::Op::OpSGreaterThanEqual, "%int_1", "%38",
752              {{LoopPeelingPass::PeelDirection::kBefore, 2u}});
753   }
754 
755   // Peel after by a factor of 2.
756   {
757     SCOPED_TRACE("Peel after iv <= 7");
758 
759     run_test(spv::Op::OpSLessThanEqual, "%38", "%int_7",
760              {{LoopPeelingPass::PeelDirection::kAfter, 2u}});
761   }
762   {
763     SCOPED_TRACE("Peel after 7 => iv");
764 
765     run_test(spv::Op::OpSGreaterThanEqual, "%int_7", "%38",
766              {{LoopPeelingPass::PeelDirection::kAfter, 2u}});
767   }
768 
769   // Test GE
770   // Peel before by a factor of 2.
771   {
772     SCOPED_TRACE("Peel before iv >= 2");
773 
774     run_test(spv::Op::OpSGreaterThanEqual, "%38", "%int_2",
775              {{LoopPeelingPass::PeelDirection::kBefore, 2u}});
776   }
777   {
778     SCOPED_TRACE("Peel before 2 <= iv");
779 
780     run_test(spv::Op::OpSLessThanEqual, "%int_2", "%38",
781              {{LoopPeelingPass::PeelDirection::kBefore, 2u}});
782   }
783 
784   // Peel after by a factor of 2.
785   {
786     SCOPED_TRACE("Peel after iv >= 8");
787 
788     run_test(spv::Op::OpSGreaterThanEqual, "%38", "%int_8",
789              {{LoopPeelingPass::PeelDirection::kAfter, 2u}});
790   }
791   {
792     SCOPED_TRACE("Peel after 8 <= iv");
793 
794     run_test(spv::Op::OpSLessThanEqual, "%int_8", "%38",
795              {{LoopPeelingPass::PeelDirection::kAfter, 2u}});
796   }
797   // Test EQ
798   // Peel before by a factor of 1.
799   {
800     SCOPED_TRACE("Peel before iv == 0");
801 
802     run_test(spv::Op::OpIEqual, "%38", "%int_0",
803              {{LoopPeelingPass::PeelDirection::kBefore, 1u}});
804   }
805   {
806     SCOPED_TRACE("Peel before 0 == iv");
807 
808     run_test(spv::Op::OpIEqual, "%int_0", "%38",
809              {{LoopPeelingPass::PeelDirection::kBefore, 1u}});
810   }
811 
812   // Peel after by a factor of 1.
813   {
814     SCOPED_TRACE("Peel after iv == 9");
815 
816     run_test(spv::Op::OpIEqual, "%38", "%int_9",
817              {{LoopPeelingPass::PeelDirection::kBefore, 1u}});
818   }
819   {
820     SCOPED_TRACE("Peel after 9 == iv");
821 
822     run_test(spv::Op::OpIEqual, "%int_9", "%38",
823              {{LoopPeelingPass::PeelDirection::kBefore, 1u}});
824   }
825 
826   // Test NE
827   // Peel before by a factor of 1.
828   {
829     SCOPED_TRACE("Peel before iv != 0");
830 
831     run_test(spv::Op::OpINotEqual, "%38", "%int_0",
832              {{LoopPeelingPass::PeelDirection::kBefore, 1u}});
833   }
834   {
835     SCOPED_TRACE("Peel before 0 != iv");
836 
837     run_test(spv::Op::OpINotEqual, "%int_0", "%38",
838              {{LoopPeelingPass::PeelDirection::kBefore, 1u}});
839   }
840 
841   // Peel after by a factor of 1.
842   {
843     SCOPED_TRACE("Peel after iv != 9");
844 
845     run_test(spv::Op::OpINotEqual, "%38", "%int_9",
846              {{LoopPeelingPass::PeelDirection::kBefore, 1u}});
847   }
848   {
849     SCOPED_TRACE("Peel after 9 != iv");
850 
851     run_test(spv::Op::OpINotEqual, "%int_9", "%38",
852              {{LoopPeelingPass::PeelDirection::kBefore, 1u}});
853   }
854 }
855 
856 /*
857 Test are derivation of the following generated test from the following GLSL +
858 --eliminate-local-multi-store
859 
860 #version 330 core
861 void main() {
862   int a = 0;
863   for (int i = 0; i < 10; i++) {
864     for (int j = 0; j < 10; j++) {
865       if (i < 3) {
866         a += 2;
867       }
868     }
869   }
870 }
871 */
TEST_F(PeelingPassTest,PeelingNestedPass)872 TEST_F(PeelingPassTest, PeelingNestedPass) {
873   const std::string text_head = R"(
874                OpCapability Shader
875           %1 = OpExtInstImport "GLSL.std.450"
876                OpMemoryModel Logical GLSL450
877                OpEntryPoint Fragment %main "main"
878                OpExecutionMode %main OriginLowerLeft
879                OpSource GLSL 330
880                OpName %main "main"
881                OpName %a "a"
882                OpName %i "i"
883                OpName %j "j"
884        %void = OpTypeVoid
885           %3 = OpTypeFunction %void
886         %int = OpTypeInt 32 1
887 %_ptr_Function_int = OpTypePointer Function %int
888       %int_0 = OpConstant %int 0
889      %int_10 = OpConstant %int 10
890        %bool = OpTypeBool
891       %int_7 = OpConstant %int 7
892       %int_3 = OpConstant %int 3
893       %int_2 = OpConstant %int 2
894       %int_1 = OpConstant %int 1
895          %43 = OpUndef %int
896        %main = OpFunction %void None %3
897           %5 = OpLabel
898           %a = OpVariable %_ptr_Function_int Function
899           %i = OpVariable %_ptr_Function_int Function
900           %j = OpVariable %_ptr_Function_int Function
901                OpStore %a %int_0
902                OpStore %i %int_0
903                OpBranch %11
904          %11 = OpLabel
905          %41 = OpPhi %int %int_0 %5 %45 %14
906          %42 = OpPhi %int %int_0 %5 %40 %14
907          %44 = OpPhi %int %43 %5 %46 %14
908                OpLoopMerge %13 %14 None
909                OpBranch %15
910          %15 = OpLabel
911          %19 = OpSLessThan %bool %42 %int_10
912                OpBranchConditional %19 %12 %13
913          %12 = OpLabel
914                OpStore %j %int_0
915                OpBranch %21
916          %21 = OpLabel
917          %45 = OpPhi %int %41 %12 %47 %24
918          %46 = OpPhi %int %int_0 %12 %38 %24
919                OpLoopMerge %23 %24 None
920                OpBranch %25
921          %25 = OpLabel
922          %27 = OpSLessThan %bool %46 %int_10
923                OpBranchConditional %27 %22 %23
924          %22 = OpLabel
925   )";
926 
927   const std::string text_tail = R"(
928                OpSelectionMerge %32 None
929                OpBranchConditional %30 %31 %32
930          %31 = OpLabel
931          %35 = OpIAdd %int %45 %int_2
932                OpStore %a %35
933                OpBranch %32
934          %32 = OpLabel
935          %47 = OpPhi %int %45 %22 %35 %31
936                OpBranch %24
937          %24 = OpLabel
938          %38 = OpIAdd %int %46 %int_1
939                OpStore %j %38
940                OpBranch %21
941          %23 = OpLabel
942                OpBranch %14
943          %14 = OpLabel
944          %40 = OpIAdd %int %42 %int_1
945                OpStore %i %40
946                OpBranch %11
947          %13 = OpLabel
948                OpReturn
949                OpFunctionEnd
950   )";
951 
952   auto run_test =
953       [&text_head, &text_tail, this](
954           spv::Op opcode, const std::string& op1, const std::string& op2,
955           const PeelTraceType& expected_peel_trace, size_t nb_of_loops) {
956         BuildAndCheckTrace(text_head, text_tail, opcode, "%30", op1, op2,
957                            expected_peel_trace, nb_of_loops);
958       };
959 
960   // Peeling outer before by a factor of 3.
961   {
962     SCOPED_TRACE("Peel before iv_i < 3");
963 
964     // Expect peel before by a factor of 3 and 4 loops at the end.
965     run_test(spv::Op::OpSLessThan, "%42", "%int_3",
966              {{LoopPeelingPass::PeelDirection::kBefore, 3u}}, 4);
967   }
968   // Peeling outer loop after by a factor of 3.
969   {
970     SCOPED_TRACE("Peel after iv_i < 7");
971 
972     // Expect peel after by a factor of 3 and 4 loops at the end.
973     run_test(spv::Op::OpSLessThan, "%42", "%int_7",
974              {{LoopPeelingPass::PeelDirection::kAfter, 3u}}, 4);
975   }
976 
977   // Peeling inner loop before by a factor of 3.
978   {
979     SCOPED_TRACE("Peel before iv_j < 3");
980 
981     // Expect peel before by a factor of 3 and 3 loops at the end.
982     run_test(spv::Op::OpSLessThan, "%46", "%int_3",
983              {{LoopPeelingPass::PeelDirection::kBefore, 3u}}, 3);
984   }
985   // Peeling inner loop after by a factor of 3.
986   {
987     SCOPED_TRACE("Peel after iv_j < 7");
988 
989     // Expect peel after by a factor of 3 and 3 loops at the end.
990     run_test(spv::Op::OpSLessThan, "%46", "%int_7",
991              {{LoopPeelingPass::PeelDirection::kAfter, 3u}}, 3);
992   }
993 
994   // Not unworkable condition.
995   {
996     SCOPED_TRACE("No peel");
997 
998     // Expect no peeling and 2 loops at the end.
999     run_test(spv::Op::OpSLessThan, "%46", "%42", {}, 2);
1000   }
1001 
1002   // Could do a peeling of 3, but the goes over the threshold.
1003   {
1004     SCOPED_TRACE("Over threshold");
1005 
1006     size_t current_threshold = LoopPeelingPass::GetLoopPeelingThreshold();
1007     LoopPeelingPass::SetLoopPeelingThreshold(1u);
1008     // Expect no peeling and 2 loops at the end.
1009     run_test(spv::Op::OpSLessThan, "%46", "%int_7", {}, 2);
1010     LoopPeelingPass::SetLoopPeelingThreshold(current_threshold);
1011   }
1012 }
1013 /*
1014 Test are derivation of the following generated test from the following GLSL +
1015 --eliminate-local-multi-store
1016 
1017 #version 330 core
1018 void main() {
1019   int a = 0;
1020   for (int i = 0, j = 0; i < 10; j++, i++) {
1021     if (i < j) {
1022       a += 2;
1023     }
1024   }
1025 }
1026 */
TEST_F(PeelingPassTest,PeelingNoChanges)1027 TEST_F(PeelingPassTest, PeelingNoChanges) {
1028   const std::string text = R"(
1029                OpCapability Shader
1030           %1 = OpExtInstImport "GLSL.std.450"
1031                OpMemoryModel Logical GLSL450
1032                OpEntryPoint Fragment %main "main"
1033                OpExecutionMode %main OriginLowerLeft
1034                OpSource GLSL 330
1035                OpName %main "main"
1036                OpName %a "a"
1037                OpName %i "i"
1038                OpName %j "j"
1039        %void = OpTypeVoid
1040           %3 = OpTypeFunction %void
1041         %int = OpTypeInt 32 1
1042 %_ptr_Function_int = OpTypePointer Function %int
1043       %int_0 = OpConstant %int 0
1044      %int_10 = OpConstant %int 10
1045        %bool = OpTypeBool
1046       %int_2 = OpConstant %int 2
1047       %int_1 = OpConstant %int 1
1048        %main = OpFunction %void None %3
1049           %5 = OpLabel
1050           %a = OpVariable %_ptr_Function_int Function
1051           %i = OpVariable %_ptr_Function_int Function
1052           %j = OpVariable %_ptr_Function_int Function
1053                OpStore %a %int_0
1054                OpStore %i %int_0
1055                OpStore %j %int_0
1056                OpBranch %12
1057          %12 = OpLabel
1058          %34 = OpPhi %int %int_0 %5 %37 %15
1059          %35 = OpPhi %int %int_0 %5 %33 %15
1060          %36 = OpPhi %int %int_0 %5 %31 %15
1061                OpLoopMerge %14 %15 None
1062                OpBranch %16
1063          %16 = OpLabel
1064          %20 = OpSLessThan %bool %35 %int_10
1065                OpBranchConditional %20 %13 %14
1066          %13 = OpLabel
1067          %23 = OpSLessThan %bool %35 %36
1068                OpSelectionMerge %25 None
1069                OpBranchConditional %23 %24 %25
1070          %24 = OpLabel
1071          %28 = OpIAdd %int %34 %int_2
1072                OpStore %a %28
1073                OpBranch %25
1074          %25 = OpLabel
1075          %37 = OpPhi %int %34 %13 %28 %24
1076                OpBranch %15
1077          %15 = OpLabel
1078          %31 = OpIAdd %int %36 %int_1
1079                OpStore %j %31
1080          %33 = OpIAdd %int %35 %int_1
1081                OpStore %i %33
1082                OpBranch %12
1083          %14 = OpLabel
1084                OpReturn
1085                OpFunctionEnd
1086   )";
1087 
1088   {
1089     auto result =
1090         SinglePassRunAndDisassemble<LoopPeelingPass>(text, true, false);
1091 
1092     EXPECT_EQ(Pass::Status::SuccessWithoutChange, std::get<1>(result));
1093   }
1094 }
1095 
1096 }  // namespace
1097 }  // namespace opt
1098 }  // namespace spvtools
1099