From cd68f2b17642a76ed8f76b233ffce76f777be55a Mon Sep 17 00:00:00 2001 From: Jeremy Hayes Date: Thu, 25 Jan 2018 16:32:01 -0700 Subject: [PATCH] Add adjacency validation pass Validate OpPhi predecessors. Validate OpLoopMerge successors. Validate OpSelectionMerge successors. Fix collateral damage to existing tests. Remove ValidateIdWithMessage.OpSampledImageUsedInOpPhiBad. --- Android.mk | 1 + source/CMakeLists.txt | 1 + source/validate.cpp | 4 + source/validate.h | 12 ++ source/validate_adjacency.cpp | 84 ++++++++++++ test/opt/cfg_cleanup_test.cpp | 18 +-- test/val/CMakeLists.txt | 6 + test/val/val_adjacency_test.cpp | 285 ++++++++++++++++++++++++++++++++++++++++ test/val/val_id_test.cpp | 28 ++-- 9 files changed, 409 insertions(+), 30 deletions(-) create mode 100644 source/validate_adjacency.cpp create mode 100644 test/val/val_adjacency_test.cpp diff --git a/Android.mk b/Android.mk index 902c682..b4d56ce 100644 --- a/Android.mk +++ b/Android.mk @@ -33,6 +33,7 @@ SPVTOOLS_SRC_FILES := \ source/val/instruction.cpp \ source/val/validation_state.cpp \ source/validate.cpp \ + source/validate_adjacency.cpp \ source/validate_arithmetics.cpp \ source/validate_atomics.cpp \ source/validate_bitwise.cpp \ diff --git a/source/CMakeLists.txt b/source/CMakeLists.txt index 61a4112..91111f6 100644 --- a/source/CMakeLists.txt +++ b/source/CMakeLists.txt @@ -281,6 +281,7 @@ set(SPIRV_SOURCES ${CMAKE_CURRENT_SOURCE_DIR}/text.cpp ${CMAKE_CURRENT_SOURCE_DIR}/text_handler.cpp ${CMAKE_CURRENT_SOURCE_DIR}/validate.cpp + ${CMAKE_CURRENT_SOURCE_DIR}/validate_adjacency.cpp ${CMAKE_CURRENT_SOURCE_DIR}/validate_arithmetics.cpp ${CMAKE_CURRENT_SOURCE_DIR}/validate_atomics.cpp ${CMAKE_CURRENT_SOURCE_DIR}/validate_bitwise.cpp diff --git a/source/validate.cpp b/source/validate.cpp index 6bfabe1..a51f2e0 100644 --- a/source/validate.cpp +++ b/source/validate.cpp @@ -290,6 +290,10 @@ spv_result_t ValidateBinaryUsingContextAndValidationState( << id_str.substr(0, id_str.size() - 1); } + // Validate the preconditions involving adjacent instructions. e.g. SpvOpPhi + // must only be preceeded by SpvOpLabel, SpvOpPhi, or SpvOpLine. + if (auto error = ValidateAdjacency(*vstate)) return error; + // CFG checks are performed after the binary has been parsed // and the CFGPass has collected information about the control flow if (auto error = PerformCfgChecks(*vstate)) return error; diff --git a/source/validate.h b/source/validate.h index a1ea297..5871b2f 100644 --- a/source/validate.h +++ b/source/validate.h @@ -63,6 +63,18 @@ spv_result_t UpdateIdUse(ValidationState_t& _); /// @return SPV_SUCCESS if no errors are found. SPV_ERROR_INVALID_ID otherwise spv_result_t CheckIdDefinitionDominateUse(const ValidationState_t& _); +/// @brief This function checks for preconditions involving the adjacent +/// instructions. +/// +/// This function will iterate over all instructions and check for any required +/// predecessor and/or successor instructions. e.g. SpvOpPhi must only be +/// preceeded by SpvOpLabel, SpvOpPhi, or SpvOpLine. +/// +/// @param[in] _ the validation state of the module +/// +/// @return SPV_SUCCESS if no errors are found. SPV_ERROR_INVALID_DATA otherwise +spv_result_t ValidateAdjacency(ValidationState_t& _); + /// @brief Updates the immediate dominator for each of the block edges /// /// Updates the immediate dominator of the blocks for each of the edges diff --git a/source/validate_adjacency.cpp b/source/validate_adjacency.cpp new file mode 100644 index 0000000..75cea52 --- /dev/null +++ b/source/validate_adjacency.cpp @@ -0,0 +1,84 @@ +// Copyright (c) 2018 LunarG Inc. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +// Validates correctness of the intra-block preconditions of SPIR-V +// instructions. + +#include "validate.h" + +#include + +#include "diagnostic.h" +#include "opcode.h" +#include "val/instruction.h" +#include "val/validation_state.h" + +namespace libspirv { + +spv_result_t ValidateAdjacency(ValidationState_t& _) { + const auto& instructions = _.ordered_instructions(); + for (auto i = instructions.cbegin(); i != instructions.cend(); ++i) { + switch (i->opcode()) { + case SpvOpPhi: + if (i != instructions.cbegin()) { + switch (prev(i)->opcode()) { + case SpvOpLabel: + case SpvOpPhi: + case SpvOpLine: + break; + default: + return _.diag(SPV_ERROR_INVALID_DATA) + << "OpPhi must appear before all non-OpPhi instructions " + << "(except for OpLine, which can be mixed with OpPhi)."; + } + } + break; + case SpvOpLoopMerge: + if (next(i) != instructions.cend()) { + switch (next(i)->opcode()) { + case SpvOpBranch: + case SpvOpBranchConditional: + break; + default: + return _.diag(SPV_ERROR_INVALID_DATA) + << "OpLoopMerge must immediately precede either an " + << "OpBranch or OpBranchConditional instruction. " + << "OpLoopMerge must be the second-to-last instruction in " + << "its block."; + } + } + break; + case SpvOpSelectionMerge: + if (next(i) != instructions.cend()) { + switch (next(i)->opcode()) { + case SpvOpBranchConditional: + case SpvOpSwitch: + break; + default: + return _.diag(SPV_ERROR_INVALID_DATA) + << "OpSelectionMerge must immediately precede either an " + << "OpBranchConditional or OpSwitch instruction. " + << "OpSelectionMerge must be the second-to-last " + << "instruction in its block."; + } + } + default: + break; + } + } + + return SPV_SUCCESS; +} + +} // namespace libspirv diff --git a/test/opt/cfg_cleanup_test.cpp b/test/opt/cfg_cleanup_test.cpp index aa6ac77..d4442c7 100644 --- a/test/opt/cfg_cleanup_test.cpp +++ b/test/opt/cfg_cleanup_test.cpp @@ -48,7 +48,6 @@ OpDecorate %outf4 Location 0 const std::string body_before = R"(%main = OpFunction %void None %6 %14 = OpLabel -OpSelectionMerge %17 None OpBranch %18 %19 = OpLabel %20 = OpLoad %float %inf @@ -68,15 +67,14 @@ OpFunctionEnd const std::string body_after = R"(%main = OpFunction %void None %6 %14 = OpLabel -OpSelectionMerge %15 None -OpBranch %16 -%16 = OpLabel +OpBranch %15 +%15 = OpLabel %20 = OpLoad %float %inf %21 = OpFAdd %float %20 %float_n0_5 %22 = OpCompositeConstruct %v4float %21 %21 %21 %21 OpStore %outf4 %22 -OpBranch %15 -%15 = OpLabel +OpBranch %19 +%19 = OpLabel OpReturn OpFunctionEnd )"; @@ -106,7 +104,6 @@ TEST_F(CFGCleanupTest, RemoveDecorations) { %main = OpFunction %void None %6 %14 = OpLabel %x = OpVariable %_ptr_Function_float Function - OpSelectionMerge %17 None OpBranch %18 %19 = OpLabel %dead = OpVariable %_ptr_Function_float Function @@ -136,12 +133,11 @@ OpDecorate %x RelaxedPrecision %main = OpFunction %void None %6 %11 = OpLabel %x = OpVariable %_ptr_Function_float Function -OpSelectionMerge %12 None -OpBranch %13 -%13 = OpLabel -OpStore %x %float_4 OpBranch %12 %12 = OpLabel +OpStore %x %float_4 +OpBranch %14 +%14 = OpLabel OpReturn OpFunctionEnd )"; diff --git a/test/val/CMakeLists.txt b/test/val/CMakeLists.txt index c290755..b167308 100644 --- a/test/val/CMakeLists.txt +++ b/test/val/CMakeLists.txt @@ -169,3 +169,9 @@ add_spvtools_unittest(TARGET val_extensions ${VAL_TEST_COMMON_SRCS} LIBS ${SPIRV_TOOLS} ) + +add_spvtools_unittest(TARGET val_adjacency + SRCS val_adjacency_test.cpp + ${VAL_TEST_COMMON_SRCS} + LIBS ${SPIRV_TOOLS} +) diff --git a/test/val/val_adjacency_test.cpp b/test/val/val_adjacency_test.cpp new file mode 100644 index 0000000..586cf7e --- /dev/null +++ b/test/val/val_adjacency_test.cpp @@ -0,0 +1,285 @@ +// Copyright (c) 2018 LunarG Inc. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +#include +#include + +#include "gmock/gmock.h" +#include "unit_spirv.h" +#include "val_fixtures.h" + +namespace { + +using ::testing::HasSubstr; +using ::testing::Not; + +using ValidateAdjacency = spvtest::ValidateBase; + +TEST_F(ValidateAdjacency, OpPhiBeginsModuleFail) { + const std::string module = R"( +%result = OpPhi %bool %true %true_label %false %false_label +OpCapability Shader +OpMemoryModel Logical GLSL450 +OpEntryPoint Fragment %main "main" +%void = OpTypeVoid +%bool = OpTypeBool +%true = OpConstantTrue %bool +%false = OpConstantFalse %bool +%func = OpTypeFunction %void +%main = OpFunction %void None %func +%main_entry = OpLabel +OpBranch %true_label +%true_label = OpLabel +OpBranch %false_label +%false_label = OpLabel +OpBranch %end_label +OpReturn +OpFunctionEnd +)"; + + CompileSuccessfully(module); + EXPECT_EQ(SPV_ERROR_INVALID_ID, ValidateInstructions()); + EXPECT_THAT(getDiagnosticString(), HasSubstr("ID 1 has not been defined")); +} + +TEST_F(ValidateAdjacency, OpLoopMergeEndsModuleFail) { + const std::string module = R"( +OpCapability Shader +OpMemoryModel Logical GLSL450 +OpEntryPoint Fragment %main "main" +%void = OpTypeVoid +%func = OpTypeFunction %void +%main = OpFunction %void None %func +%main_entry = OpLabel +OpBranch %loop +%loop = OpLabel +OpLoopMerge %end %loop None +)"; + + CompileSuccessfully(module); + EXPECT_EQ(SPV_ERROR_INVALID_LAYOUT, ValidateInstructions()); + EXPECT_THAT(getDiagnosticString(), + HasSubstr("Missing OpFunctionEnd at end of module")); +} + +TEST_F(ValidateAdjacency, OpSelectionMergeEndsModuleFail) { + const std::string module = R"( +OpCapability Shader +OpMemoryModel Logical GLSL450 +OpEntryPoint Fragment %main "main" +%void = OpTypeVoid +%func = OpTypeFunction %void +%main = OpFunction %void None %func +%main_entry = OpLabel +OpBranch %merge +%merge = OpLabel +OpSelectionMerge %merge None +)"; + + CompileSuccessfully(module); + EXPECT_EQ(SPV_ERROR_INVALID_LAYOUT, ValidateInstructions()); + EXPECT_THAT(getDiagnosticString(), + HasSubstr("Missing OpFunctionEnd at end of module")); +} + +std::string GenerateShaderCode( + const std::string& body, + const std::string& capabilities_and_extensions = "OpCapability Shader", + const std::string& execution_model = "Fragment") { + std::ostringstream ss; + ss << capabilities_and_extensions << "\n"; + ss << "OpMemoryModel Logical GLSL450\n"; + ss << "OpEntryPoint " << execution_model << " %main \"main\"\n"; + + ss << R"( +%string = OpString "" +%void = OpTypeVoid +%bool = OpTypeBool +%int = OpTypeInt 32 0 +%true = OpConstantTrue %bool +%false = OpConstantFalse %bool +%zero = OpConstant %int 0 +%func = OpTypeFunction %void +%main = OpFunction %void None %func +%main_entry = OpLabel +)"; + + ss << body; + + ss << R"( +OpReturn +OpFunctionEnd)"; + + return ss.str(); +} + +TEST_F(ValidateAdjacency, OpPhiPreceededByOpLabelSuccess) { + const std::string body = R"( +OpSelectionMerge %end_label None +OpBranchConditional %true %true_label %false_label +%true_label = OpLabel +OpBranch %end_label +%false_label = OpLabel +OpBranch %end_label +%end_label = OpLabel +%line = OpLine %string 0 0 +%result = OpPhi %bool %true %true_label %false %false_label +)"; + + CompileSuccessfully(GenerateShaderCode(body)); + EXPECT_EQ(SPV_SUCCESS, ValidateInstructions()); +} + +TEST_F(ValidateAdjacency, OpPhiPreceededByOpPhiSuccess) { + const std::string body = R"( +OpSelectionMerge %end_label None +OpBranchConditional %true %true_label %false_label +%true_label = OpLabel +OpBranch %end_label +%false_label = OpLabel +OpBranch %end_label +%end_label = OpLabel +%1 = OpPhi %bool %true %true_label %false %false_label +%2 = OpPhi %bool %true %true_label %false %false_label +)"; + + CompileSuccessfully(GenerateShaderCode(body)); + EXPECT_EQ(SPV_SUCCESS, ValidateInstructions()); +} + +TEST_F(ValidateAdjacency, OpPhiPreceededByOpLineSuccess) { + const std::string body = R"( +OpSelectionMerge %end_label None +OpBranchConditional %true %true_label %false_label +%true_label = OpLabel +OpBranch %end_label +%false_label = OpLabel +OpBranch %end_label +%end_label = OpLabel +%line = OpLine %string 0 0 +%result = OpPhi %bool %true %true_label %false %false_label +)"; + + CompileSuccessfully(GenerateShaderCode(body)); + EXPECT_EQ(SPV_SUCCESS, ValidateInstructions()); +} + +TEST_F(ValidateAdjacency, OpPhiPreceededByBadOpFail) { + const std::string body = R"( +OpSelectionMerge %end_label None +OpBranchConditional %true %true_label %false_label +%true_label = OpLabel +OpBranch %end_label +%false_label = OpLabel +OpBranch %end_label +%end_label = OpLabel +OpNop +%result = OpPhi %bool %true %true_label %false %false_label +)"; + + CompileSuccessfully(GenerateShaderCode(body)); + EXPECT_EQ(SPV_ERROR_INVALID_DATA, ValidateInstructions()); + EXPECT_THAT(getDiagnosticString(), + HasSubstr("OpPhi must appear before all non-OpPhi instructions")); +} + +TEST_F(ValidateAdjacency, OpLoopMergePreceedsOpBranchSuccess) { + const std::string body = R"( +OpBranch %loop +%loop = OpLabel +OpLoopMerge %end %loop None +OpBranch %loop +%end = OpLabel +)"; + + CompileSuccessfully(GenerateShaderCode(body)); + EXPECT_EQ(SPV_SUCCESS, ValidateInstructions()); +} + +TEST_F(ValidateAdjacency, OpLoopMergePreceedsOpBranchConditionalSuccess) { + const std::string body = R"( +OpBranch %loop +%loop = OpLabel +OpLoopMerge %end %loop None +OpBranchConditional %true %loop %end +%end = OpLabel +)"; + + CompileSuccessfully(GenerateShaderCode(body)); + EXPECT_EQ(SPV_SUCCESS, ValidateInstructions()); +} + +TEST_F(ValidateAdjacency, OpLoopMergePreceedsBadOpFail) { + const std::string body = R"( +OpBranch %loop +%loop = OpLabel +OpLoopMerge %end %loop None +OpNop +OpBranchConditional %true %loop %end +%end = OpLabel +)"; + + CompileSuccessfully(GenerateShaderCode(body)); + EXPECT_EQ(SPV_ERROR_INVALID_DATA, ValidateInstructions()); + EXPECT_THAT(getDiagnosticString(), + HasSubstr("OpLoopMerge must immediately precede either an " + "OpBranch or OpBranchConditional instruction.")); +} + +TEST_F(ValidateAdjacency, OpSelectionMergePreceedsOpBranchConditionalSuccess) { + const std::string body = R"( +OpSelectionMerge %end_label None +OpBranchConditional %true %true_label %false_label +%true_label = OpLabel +OpBranch %end_label +%false_label = OpLabel +OpBranch %end_label +%end_label = OpLabel +)"; + + CompileSuccessfully(GenerateShaderCode(body)); + EXPECT_EQ(SPV_SUCCESS, ValidateInstructions()); +} + +TEST_F(ValidateAdjacency, OpSelectionMergePreceedsOpSwitchSuccess) { + const std::string body = R"( +OpSelectionMerge %merge None +OpSwitch %zero %merge 0 %label +%label = OpLabel +OpBranch %merge +%merge = OpLabel +)"; + + CompileSuccessfully(GenerateShaderCode(body)); + EXPECT_EQ(SPV_SUCCESS, ValidateInstructions()); +} + +TEST_F(ValidateAdjacency, OpSelectionMergePreceedsBadOpFail) { + const std::string body = R"( +OpSelectionMerge %merge None +OpNop +OpSwitch %zero %merge 0 %label +%label = OpLabel +OpBranch %merge +%merge = OpLabel +)"; + + CompileSuccessfully(GenerateShaderCode(body)); + EXPECT_EQ(SPV_ERROR_INVALID_DATA, ValidateInstructions()); + EXPECT_THAT(getDiagnosticString(), + HasSubstr("OpSelectionMerge must immediately precede either an " + "OpBranchConditional or OpSwitch instruction")); +} + +} // anonymous namespace diff --git a/test/val/val_id_test.cpp b/test/val/val_id_test.cpp index 8278b16..cf12a7e 100644 --- a/test/val/val_id_test.cpp +++ b/test/val/val_id_test.cpp @@ -122,8 +122,6 @@ string BranchConditionalSetup = R"( %voidfunc = OpTypeFunction %void %main = OpFunction %void None %voidfunc %lmain = OpLabel - - OpSelectionMerge %end None )"; string BranchConditionalTail = R"( @@ -3517,21 +3515,6 @@ OpFunctionEnd)"; "'23' as an operand of '24'.")); } -// Invalid: OpSampledImage result is used by OpPhi -TEST_F(ValidateIdWithMessage, OpSampledImageUsedInOpPhiBad) { - string spirv = kGLSL450MemoryModel + sampledImageSetup + R"( -%smpld_img = OpSampledImage %sampled_image_type %image_inst %sampler_inst -%phi_result = OpPhi %sampled_image_type %smpld_img %label_1 -OpReturn -OpFunctionEnd)"; - CompileSuccessfully(spirv.c_str()); - EXPECT_EQ(SPV_ERROR_INVALID_ID, ValidateInstructions()); - EXPECT_THAT(getDiagnosticString(), - HasSubstr("Result from OpSampledImage instruction must not " - "appear as operands of OpPhi. Found result '23' " - "as an operand of '24'.")); -} - // Valid: Get a float in a matrix using CompositeExtract. // Valid: Insert float into a matrix using CompositeInsert. TEST_F(ValidateIdWithMessage, CompositeExtractInsertGood) { @@ -3939,6 +3922,7 @@ TEST_F(ValidateIdWithMessage, OpVectorShuffleLiterals) { TEST_F(ValidateIdWithMessage, OpBranchConditionalGood) { string spirv = BranchConditionalSetup + R"( %branch_cond = OpINotEqual %bool %i0 %i1 + OpSelectionMerge %end None OpBranchConditional %branch_cond %target_t %target_f )" + BranchConditionalTail; @@ -3949,6 +3933,7 @@ TEST_F(ValidateIdWithMessage, OpBranchConditionalGood) { TEST_F(ValidateIdWithMessage, OpBranchConditionalWithWeightsGood) { string spirv = BranchConditionalSetup + R"( %branch_cond = OpINotEqual %bool %i0 %i1 + OpSelectionMerge %end None OpBranchConditional %branch_cond %target_t %target_f 1 1 )" + BranchConditionalTail; @@ -3958,7 +3943,8 @@ TEST_F(ValidateIdWithMessage, OpBranchConditionalWithWeightsGood) { TEST_F(ValidateIdWithMessage, OpBranchConditional_CondIsScalarInt) { string spirv = BranchConditionalSetup + R"( - OpBranchConditional %i0 %target_t %target_f + OpSelectionMerge %end None + OpBranchConditional %i0 %target_t %target_f )" + BranchConditionalTail; CompileSuccessfully(spirv.c_str()); @@ -3971,6 +3957,7 @@ TEST_F(ValidateIdWithMessage, OpBranchConditional_CondIsScalarInt) { TEST_F(ValidateIdWithMessage, OpBranchConditional_TrueTargetIsNotLabel) { string spirv = BranchConditionalSetup + R"( + OpSelectionMerge %end None OpBranchConditional %i0 %i0 %target_f )" + BranchConditionalTail; @@ -3989,7 +3976,8 @@ TEST_F(ValidateIdWithMessage, OpBranchConditional_TrueTargetIsNotLabel) { TEST_F(ValidateIdWithMessage, OpBranchConditional_FalseTargetIsNotLabel) { string spirv = BranchConditionalSetup + R"( - OpBranchConditional %i0 %target_t %i0 + OpSelectionMerge %end None + OpBranchConditional %i0 %target_t %i0 )" + BranchConditionalTail; CompileSuccessfully(spirv.c_str()); @@ -4008,6 +3996,7 @@ TEST_F(ValidateIdWithMessage, OpBranchConditional_FalseTargetIsNotLabel) { TEST_F(ValidateIdWithMessage, OpBranchConditional_NotEnoughWeights) { string spirv = BranchConditionalSetup + R"( %branch_cond = OpINotEqual %bool %i0 %i1 + OpSelectionMerge %end None OpBranchConditional %branch_cond %target_t %target_f 1 )" + BranchConditionalTail; @@ -4021,6 +4010,7 @@ TEST_F(ValidateIdWithMessage, OpBranchConditional_NotEnoughWeights) { TEST_F(ValidateIdWithMessage, OpBranchConditional_TooManyWeights) { string spirv = BranchConditionalSetup + R"( %branch_cond = OpINotEqual %bool %i0 %i1 + OpSelectionMerge %end None OpBranchConditional %branch_cond %target_t %target_f 1 2 3 )" + BranchConditionalTail; -- 2.7.4