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/reduce/reducer.h"
16 #include "source/reduce/reduction_opportunity.h"
17 #include "source/reduce/remove_instruction_reduction_opportunity.h"
18 #include "test/reduce/reduce_test_util.h"
19 
20 namespace spvtools {
21 namespace reduce {
22 namespace {
23 
24 using opt::Function;
25 using opt::IRContext;
26 using opt::Instruction;
27 
28 // A reduction opportunity finder that finds opportunities to remove global
29 // values regardless of whether they are referenced. This is very likely to make
30 // the resulting module invalid.  We use this to test the reducer's behavior in
31 // the scenario where a bad reduction pass leads to an invalid module.
32 class BlindlyRemoveGlobalValuesReductionOpportunityFinder
33     : public ReductionOpportunityFinder {
34  public:
35   BlindlyRemoveGlobalValuesReductionOpportunityFinder() = default;
36 
37   ~BlindlyRemoveGlobalValuesReductionOpportunityFinder() override = default;
38 
39   // The name of this pass.
40   std::string GetName() const final { return "BlindlyRemoveGlobalValuesPass"; }
41 
42   // Finds opportunities to remove all global values.  Assuming they are all
43   // referenced (directly or indirectly) from elsewhere in the module, each such
44   // opportunity will make the module invalid.
45   std::vector<std::unique_ptr<ReductionOpportunity>> GetAvailableOpportunities(
46       IRContext* context, uint32_t /*unused*/) const final {
47     std::vector<std::unique_ptr<ReductionOpportunity>> result;
48     for (auto& inst : context->module()->types_values()) {
49       if (inst.HasResultId()) {
50         result.push_back(
51             MakeUnique<RemoveInstructionReductionOpportunity>(&inst));
52       }
53     }
54     return result;
55   }
56 };
57 
58 // A reduction opportunity that exists at the start of every function whose
59 // first instruction is an OpVariable instruction. When applied, the OpVariable
60 // instruction is duplicated (with a fresh result id). This allows each
61 // reduction step to increase the number of variables to check if the validator
62 // limits are enforced.
63 class OpVariableDuplicatorReductionOpportunity : public ReductionOpportunity {
64  public:
65   OpVariableDuplicatorReductionOpportunity(Function* function)
66       : function_(function) {}
67 
68   bool PreconditionHolds() override {
69     Instruction* first_instruction = &*function_->begin()[0].begin();
70     return first_instruction->opcode() == SpvOpVariable;
71   }
72 
73  protected:
74   void Apply() override {
75     // Duplicate the first OpVariable instruction.
76 
77     Instruction* first_instruction = &*function_->begin()[0].begin();
78     assert(first_instruction->opcode() == SpvOpVariable &&
79            "Expected first instruction to be OpVariable");
80     IRContext* context = first_instruction->context();
81     Instruction* cloned_instruction = first_instruction->Clone(context);
82     cloned_instruction->SetResultId(context->TakeNextId());
83     cloned_instruction->InsertBefore(first_instruction);
84   }
85 
86  private:
87   Function* function_;
88 };
89 
90 // A reduction opportunity finder that finds
91 // OpVariableDuplicatorReductionOpportunity.
92 class OpVariableDuplicatorReductionOpportunityFinder
93     : public ReductionOpportunityFinder {
94  public:
95   OpVariableDuplicatorReductionOpportunityFinder() = default;
96 
97   ~OpVariableDuplicatorReductionOpportunityFinder() override = default;
98 
99   std::string GetName() const final {
100     return "LocalVariableAdderReductionOpportunityFinder";
101   }
102 
103   std::vector<std::unique_ptr<ReductionOpportunity>> GetAvailableOpportunities(
104       IRContext* context, uint32_t /*unused*/) const final {
105     std::vector<std::unique_ptr<ReductionOpportunity>> result;
106     for (auto& function : *context->module()) {
107       Instruction* first_instruction = &*function.begin()[0].begin();
108       if (first_instruction->opcode() == SpvOpVariable) {
109         result.push_back(
110             MakeUnique<OpVariableDuplicatorReductionOpportunity>(&function));
111       }
112     }
113     return result;
114   }
115 };
116 
117 TEST(ValidationDuringReductionTest, CheckInvalidPassMakesNoProgress) {
118   // A module whose global values are all referenced, so that any application of
119   // MakeModuleInvalidPass will make the module invalid. Check that the reducer
120   // makes no progress, as every step will be invalid and treated as
121   // uninteresting.
122   std::string original = R"(
123                OpCapability Shader
124           %1 = OpExtInstImport "GLSL.std.450"
125                OpMemoryModel Logical GLSL450
126                OpEntryPoint Fragment %4 "main" %60
127                OpExecutionMode %4 OriginUpperLeft
128                OpSource ESSL 310
129                OpName %4 "main"
130                OpName %16 "buf2"
131                OpMemberName %16 0 "i"
132                OpName %18 ""
133                OpName %25 "buf1"
134                OpMemberName %25 0 "f"
135                OpName %27 ""
136                OpName %60 "_GLF_color"
137                OpMemberDecorate %16 0 Offset 0
138                OpDecorate %16 Block
139                OpDecorate %18 DescriptorSet 0
140                OpDecorate %18 Binding 2
141                OpMemberDecorate %25 0 Offset 0
142                OpDecorate %25 Block
143                OpDecorate %27 DescriptorSet 0
144                OpDecorate %27 Binding 1
145                OpDecorate %60 Location 0
146           %2 = OpTypeVoid
147           %3 = OpTypeFunction %2
148           %6 = OpTypeInt 32 1
149           %9 = OpConstant %6 0
150          %16 = OpTypeStruct %6
151          %17 = OpTypePointer Uniform %16
152          %18 = OpVariable %17 Uniform
153          %19 = OpTypePointer Uniform %6
154          %22 = OpTypeBool
155          %24 = OpTypeFloat 32
156          %25 = OpTypeStruct %24
157          %26 = OpTypePointer Uniform %25
158          %27 = OpVariable %26 Uniform
159          %28 = OpTypePointer Uniform %24
160          %31 = OpConstant %24 2
161          %56 = OpConstant %6 1
162          %58 = OpTypeVector %24 4
163          %59 = OpTypePointer Output %58
164          %60 = OpVariable %59 Output
165          %72 = OpUndef %24
166          %74 = OpUndef %6
167           %4 = OpFunction %2 None %3
168           %5 = OpLabel
169                OpBranch %10
170          %10 = OpLabel
171          %73 = OpPhi %6 %74 %5 %77 %34
172          %71 = OpPhi %24 %72 %5 %76 %34
173          %70 = OpPhi %6 %9 %5 %57 %34
174          %20 = OpAccessChain %19 %18 %9
175          %21 = OpLoad %6 %20
176          %23 = OpSLessThan %22 %70 %21
177                OpLoopMerge %12 %34 None
178                OpBranchConditional %23 %11 %12
179          %11 = OpLabel
180          %29 = OpAccessChain %28 %27 %9
181          %30 = OpLoad %24 %29
182          %32 = OpFOrdGreaterThan %22 %30 %31
183                OpSelectionMerge %90 None
184                OpBranchConditional %32 %33 %46
185          %33 = OpLabel
186          %40 = OpFAdd %24 %71 %30
187          %45 = OpISub %6 %73 %21
188                OpBranch %90
189          %46 = OpLabel
190          %50 = OpFMul %24 %71 %30
191          %54 = OpSDiv %6 %73 %21
192                OpBranch %90
193          %90 = OpLabel
194          %77 = OpPhi %6 %45 %33 %54 %46
195          %76 = OpPhi %24 %40 %33 %50 %46
196                OpBranch %34
197          %34 = OpLabel
198          %57 = OpIAdd %6 %70 %56
199                OpBranch %10
200          %12 = OpLabel
201          %61 = OpAccessChain %28 %27 %9
202          %62 = OpLoad %24 %61
203          %66 = OpConvertSToF %24 %21
204          %68 = OpConvertSToF %24 %73
205          %69 = OpCompositeConstruct %58 %62 %71 %66 %68
206                OpStore %60 %69
207                OpReturn
208                OpFunctionEnd
209   )";
210 
211   spv_target_env env = SPV_ENV_UNIVERSAL_1_3;
212   Reducer reducer(env);
213   reducer.SetMessageConsumer(NopDiagnostic);
214 
215   // Say that every module is interesting.
216   reducer.SetInterestingnessFunction(
217       [](const std::vector<uint32_t>&, uint32_t) -> bool { return true; });
218 
219   reducer.AddReductionPass(
220       MakeUnique<BlindlyRemoveGlobalValuesReductionOpportunityFinder>());
221 
222   std::vector<uint32_t> binary_in;
223   SpirvTools t(env);
224 
225   ASSERT_TRUE(t.Assemble(original, &binary_in, kReduceAssembleOption));
226   std::vector<uint32_t> binary_out;
227   spvtools::ReducerOptions reducer_options;
228   reducer_options.set_step_limit(500);
229   // Don't fail on a validation error; just treat it as uninteresting.
230   reducer_options.set_fail_on_validation_error(false);
231   spvtools::ValidatorOptions validator_options;
232 
233   Reducer::ReductionResultStatus status = reducer.Run(
234       std::move(binary_in), &binary_out, reducer_options, validator_options);
235 
236   ASSERT_EQ(status, Reducer::ReductionResultStatus::kComplete);
237 
238   // The reducer should have no impact.
239   CheckEqual(env, original, binary_out);
240 }
241 
242 TEST(ValidationDuringReductionTest, CheckNotAlwaysInvalidCanMakeProgress) {
243   // A module with just one unreferenced global value.  All but one application
244   // of MakeModuleInvalidPass will make the module invalid.
245   std::string original = R"(
246                OpCapability Shader
247           %1 = OpExtInstImport "GLSL.std.450"
248                OpMemoryModel Logical GLSL450
249                OpEntryPoint Fragment %4 "main" %60
250                OpExecutionMode %4 OriginUpperLeft
251                OpSource ESSL 310
252                OpName %4 "main"
253                OpName %16 "buf2"
254                OpMemberName %16 0 "i"
255                OpName %18 ""
256                OpName %25 "buf1"
257                OpMemberName %25 0 "f"
258                OpName %27 ""
259                OpName %60 "_GLF_color"
260                OpMemberDecorate %16 0 Offset 0
261                OpDecorate %16 Block
262                OpDecorate %18 DescriptorSet 0
263                OpDecorate %18 Binding 2
264                OpMemberDecorate %25 0 Offset 0
265                OpDecorate %25 Block
266                OpDecorate %27 DescriptorSet 0
267                OpDecorate %27 Binding 1
268                OpDecorate %60 Location 0
269           %2 = OpTypeVoid
270           %3 = OpTypeFunction %2
271           %6 = OpTypeInt 32 1
272           %9 = OpConstant %6 0
273          %16 = OpTypeStruct %6
274          %17 = OpTypePointer Uniform %16
275          %18 = OpVariable %17 Uniform
276          %19 = OpTypePointer Uniform %6
277          %22 = OpTypeBool
278          %24 = OpTypeFloat 32
279          %25 = OpTypeStruct %24
280          %26 = OpTypePointer Uniform %25
281          %27 = OpVariable %26 Uniform
282          %28 = OpTypePointer Uniform %24
283          %31 = OpConstant %24 2
284          %56 = OpConstant %6 1
285        %1000 = OpConstant %6 1000 ; It should be possible to remove this instruction without making the module invalid.
286          %58 = OpTypeVector %24 4
287          %59 = OpTypePointer Output %58
288          %60 = OpVariable %59 Output
289          %72 = OpUndef %24
290          %74 = OpUndef %6
291           %4 = OpFunction %2 None %3
292           %5 = OpLabel
293                OpBranch %10
294          %10 = OpLabel
295          %73 = OpPhi %6 %74 %5 %77 %34
296          %71 = OpPhi %24 %72 %5 %76 %34
297          %70 = OpPhi %6 %9 %5 %57 %34
298          %20 = OpAccessChain %19 %18 %9
299          %21 = OpLoad %6 %20
300          %23 = OpSLessThan %22 %70 %21
301                OpLoopMerge %12 %34 None
302                OpBranchConditional %23 %11 %12
303          %11 = OpLabel
304          %29 = OpAccessChain %28 %27 %9
305          %30 = OpLoad %24 %29
306          %32 = OpFOrdGreaterThan %22 %30 %31
307                OpSelectionMerge %90 None
308                OpBranchConditional %32 %33 %46
309          %33 = OpLabel
310          %40 = OpFAdd %24 %71 %30
311          %45 = OpISub %6 %73 %21
312                OpBranch %90
313          %46 = OpLabel
314          %50 = OpFMul %24 %71 %30
315          %54 = OpSDiv %6 %73 %21
316                OpBranch %90
317          %90 = OpLabel
318          %77 = OpPhi %6 %45 %33 %54 %46
319          %76 = OpPhi %24 %40 %33 %50 %46
320                OpBranch %34
321          %34 = OpLabel
322          %57 = OpIAdd %6 %70 %56
323                OpBranch %10
324          %12 = OpLabel
325          %61 = OpAccessChain %28 %27 %9
326          %62 = OpLoad %24 %61
327          %66 = OpConvertSToF %24 %21
328          %68 = OpConvertSToF %24 %73
329          %69 = OpCompositeConstruct %58 %62 %71 %66 %68
330                OpStore %60 %69
331                OpReturn
332                OpFunctionEnd
333   )";
334 
335   // This is the same as the original, except that the constant declaration of
336   // 1000 is gone.
337   std::string expected = R"(
338                OpCapability Shader
339           %1 = OpExtInstImport "GLSL.std.450"
340                OpMemoryModel Logical GLSL450
341                OpEntryPoint Fragment %4 "main" %60
342                OpExecutionMode %4 OriginUpperLeft
343                OpSource ESSL 310
344                OpName %4 "main"
345                OpName %16 "buf2"
346                OpMemberName %16 0 "i"
347                OpName %18 ""
348                OpName %25 "buf1"
349                OpMemberName %25 0 "f"
350                OpName %27 ""
351                OpName %60 "_GLF_color"
352                OpMemberDecorate %16 0 Offset 0
353                OpDecorate %16 Block
354                OpDecorate %18 DescriptorSet 0
355                OpDecorate %18 Binding 2
356                OpMemberDecorate %25 0 Offset 0
357                OpDecorate %25 Block
358                OpDecorate %27 DescriptorSet 0
359                OpDecorate %27 Binding 1
360                OpDecorate %60 Location 0
361           %2 = OpTypeVoid
362           %3 = OpTypeFunction %2
363           %6 = OpTypeInt 32 1
364           %9 = OpConstant %6 0
365          %16 = OpTypeStruct %6
366          %17 = OpTypePointer Uniform %16
367          %18 = OpVariable %17 Uniform
368          %19 = OpTypePointer Uniform %6
369          %22 = OpTypeBool
370          %24 = OpTypeFloat 32
371          %25 = OpTypeStruct %24
372          %26 = OpTypePointer Uniform %25
373          %27 = OpVariable %26 Uniform
374          %28 = OpTypePointer Uniform %24
375          %31 = OpConstant %24 2
376          %56 = OpConstant %6 1
377          %58 = OpTypeVector %24 4
378          %59 = OpTypePointer Output %58
379          %60 = OpVariable %59 Output
380          %72 = OpUndef %24
381          %74 = OpUndef %6
382           %4 = OpFunction %2 None %3
383           %5 = OpLabel
384                OpBranch %10
385          %10 = OpLabel
386          %73 = OpPhi %6 %74 %5 %77 %34
387          %71 = OpPhi %24 %72 %5 %76 %34
388          %70 = OpPhi %6 %9 %5 %57 %34
389          %20 = OpAccessChain %19 %18 %9
390          %21 = OpLoad %6 %20
391          %23 = OpSLessThan %22 %70 %21
392                OpLoopMerge %12 %34 None
393                OpBranchConditional %23 %11 %12
394          %11 = OpLabel
395          %29 = OpAccessChain %28 %27 %9
396          %30 = OpLoad %24 %29
397          %32 = OpFOrdGreaterThan %22 %30 %31
398                OpSelectionMerge %90 None
399                OpBranchConditional %32 %33 %46
400          %33 = OpLabel
401          %40 = OpFAdd %24 %71 %30
402          %45 = OpISub %6 %73 %21
403                OpBranch %90
404          %46 = OpLabel
405          %50 = OpFMul %24 %71 %30
406          %54 = OpSDiv %6 %73 %21
407                OpBranch %90
408          %90 = OpLabel
409          %77 = OpPhi %6 %45 %33 %54 %46
410          %76 = OpPhi %24 %40 %33 %50 %46
411                OpBranch %34
412          %34 = OpLabel
413          %57 = OpIAdd %6 %70 %56
414                OpBranch %10
415          %12 = OpLabel
416          %61 = OpAccessChain %28 %27 %9
417          %62 = OpLoad %24 %61
418          %66 = OpConvertSToF %24 %21
419          %68 = OpConvertSToF %24 %73
420          %69 = OpCompositeConstruct %58 %62 %71 %66 %68
421                OpStore %60 %69
422                OpReturn
423                OpFunctionEnd
424   )";
425 
426   spv_target_env env = SPV_ENV_UNIVERSAL_1_3;
427   Reducer reducer(env);
428   reducer.SetMessageConsumer(NopDiagnostic);
429 
430   // Say that every module is interesting.
431   reducer.SetInterestingnessFunction(
432       [](const std::vector<uint32_t>&, uint32_t) -> bool { return true; });
433 
434   reducer.AddReductionPass(
435       MakeUnique<BlindlyRemoveGlobalValuesReductionOpportunityFinder>());
436 
437   std::vector<uint32_t> binary_in;
438   SpirvTools t(env);
439 
440   ASSERT_TRUE(t.Assemble(original, &binary_in, kReduceAssembleOption));
441   std::vector<uint32_t> binary_out;
442   spvtools::ReducerOptions reducer_options;
443   reducer_options.set_step_limit(500);
444   // Don't fail on a validation error; just treat it as uninteresting.
445   reducer_options.set_fail_on_validation_error(false);
446   spvtools::ValidatorOptions validator_options;
447 
448   Reducer::ReductionResultStatus status = reducer.Run(
449       std::move(binary_in), &binary_out, reducer_options, validator_options);
450 
451   ASSERT_EQ(status, Reducer::ReductionResultStatus::kComplete);
452 
453   CheckEqual(env, expected, binary_out);
454 }
455 
456 // Sets up a Reducer for use in the CheckValidationOptions test; avoids
457 // repetition.
458 void SetupReducerForCheckValidationOptions(Reducer* reducer) {
459   reducer->SetMessageConsumer(NopDiagnostic);
460 
461   // Say that every module is interesting.
462   reducer->SetInterestingnessFunction(
463       [](const std::vector<uint32_t>&, uint32_t) -> bool { return true; });
464 
465   // Each "reduction" step will duplicate the first OpVariable instruction in
466   // the function.
467   reducer->AddReductionPass(
468       MakeUnique<OpVariableDuplicatorReductionOpportunityFinder>());
469 }
470 
471 TEST(ValidationDuringReductionTest, CheckValidationOptions) {
472   // A module that only validates when the "skip-block-layout" validator option
473   // is used. Also, the entry point's first instruction creates a local
474   // variable; this instruction will be duplicated on each reduction step.
475   std::string original = R"(
476                OpCapability Shader
477           %1 = OpExtInstImport "GLSL.std.450"
478                OpMemoryModel Logical GLSL450
479                OpEntryPoint Vertex %2 "Main" %3
480                OpSource HLSL 600
481                OpDecorate %3 BuiltIn Position
482                OpDecorate %4 DescriptorSet 0
483                OpDecorate %4 Binding 99
484                OpDecorate %5 ArrayStride 16
485                OpMemberDecorate %6 0 Offset 0
486                OpMemberDecorate %6 1 Offset 32
487                OpMemberDecorate %6 1 MatrixStride 16
488                OpMemberDecorate %6 1 ColMajor
489                OpMemberDecorate %6 2 Offset 96
490                OpMemberDecorate %6 3 Offset 100
491                OpMemberDecorate %6 4 Offset 112
492                OpMemberDecorate %6 4 MatrixStride 16
493                OpMemberDecorate %6 4 ColMajor
494                OpMemberDecorate %6 5 Offset 176
495                OpDecorate %6 Block
496           %7 = OpTypeFloat 32
497           %8 = OpTypeVector %7 4
498           %9 = OpTypeMatrix %8 4
499          %10 = OpTypeVector %7 2
500          %11 = OpTypeInt 32 1
501          %12 = OpTypeInt 32 0
502          %13 = OpConstant %12 2
503          %14 = OpConstant %11 1
504          %15 = OpConstant %11 5
505           %5 = OpTypeArray %8 %13
506           %6 = OpTypeStruct %5 %9 %12 %10 %9 %7
507          %16 = OpTypePointer Uniform %6
508          %17 = OpTypePointer Output %8
509          %18 = OpTypeVoid
510          %19 = OpTypeFunction %18
511          %20 = OpTypePointer Uniform %7
512           %4 = OpVariable %16 Uniform
513           %3 = OpVariable %17 Output
514          %21 = OpTypePointer Function %11
515           %2 = OpFunction %18 None %19
516          %22 = OpLabel
517          %23 = OpVariable %21 Function
518          %24 = OpAccessChain %20 %4 %15
519          %25 = OpLoad %7 %24
520          %26 = OpCompositeConstruct %8 %25 %25 %25 %25
521                OpStore %3 %26
522                OpReturn
523                OpFunctionEnd
524   )";
525 
526   spv_target_env env = SPV_ENV_UNIVERSAL_1_3;
527   std::vector<uint32_t> binary_in;
528   SpirvTools t(env);
529 
530   ASSERT_TRUE(t.Assemble(original, &binary_in, kReduceAssembleOption));
531   std::vector<uint32_t> binary_out;
532   spvtools::ReducerOptions reducer_options;
533   spvtools::ValidatorOptions validator_options;
534 
535   reducer_options.set_step_limit(3);
536   reducer_options.set_fail_on_validation_error(true);
537 
538   // Reduction should fail because the initial state is invalid without the
539   // "skip-block-layout" validator option. Note that the interestingness test
540   // always returns true.
541   {
542     Reducer reducer(env);
543     SetupReducerForCheckValidationOptions(&reducer);
544 
545     Reducer::ReductionResultStatus status =
546         reducer.Run(std::vector<uint32_t>(binary_in), &binary_out,
547                     reducer_options, validator_options);
548 
549     ASSERT_EQ(status, Reducer::ReductionResultStatus::kInitialStateInvalid);
550   }
551 
552   // Try again with validator option.
553   validator_options.SetSkipBlockLayout(true);
554 
555   // Reduction should hit step limit; module is seen as valid, interestingness
556   // test always succeeds, and the finder yields infinite opportunities.
557   {
558     Reducer reducer(env);
559     SetupReducerForCheckValidationOptions(&reducer);
560 
561     Reducer::ReductionResultStatus status =
562         reducer.Run(std::vector<uint32_t>(binary_in), &binary_out,
563                     reducer_options, validator_options);
564 
565     ASSERT_EQ(status, Reducer::ReductionResultStatus::kReachedStepLimit);
566   }
567 
568   // Now set a limit on the number of local variables.
569   validator_options.SetUniversalLimit(spv_validator_limit_max_local_variables,
570                                       2);
571 
572   // Reduction should now fail due to reaching an invalid state; after one step,
573   // a local variable is added and the module becomes "invalid" given the
574   // validator limits.
575   {
576     Reducer reducer(env);
577     SetupReducerForCheckValidationOptions(&reducer);
578 
579     Reducer::ReductionResultStatus status =
580         reducer.Run(std::vector<uint32_t>(binary_in), &binary_out,
581                     reducer_options, validator_options);
582 
583     ASSERT_EQ(status, Reducer::ReductionResultStatus::kStateInvalid);
584   }
585 }
586 
587 }  // namespace
588 }  // namespace reduce
589 }  // namespace spvtools
590