From 6c61bf2dfadf70ab5fe1b0fb918ba03b7afa2396 Mon Sep 17 00:00:00 2001 From: Umar Arshad Date: Fri, 22 Jul 2016 16:27:21 -0400 Subject: [PATCH] Fixes segfault for loops without back-edges Fixes https://github.com/KhronosGroup/SPIRV-Tools/issues/270 --- source/validate_cfg.cpp | 66 ++++++++++++++++++++++++++++++++++++------------- test/Validate.CFG.cpp | 37 +++++++++++++++++++++++++++ 2 files changed, 86 insertions(+), 17 deletions(-) diff --git a/source/validate_cfg.cpp b/source/validate_cfg.cpp index a95f2cd..054bf04 100644 --- a/source/validate_cfg.cpp +++ b/source/validate_cfg.cpp @@ -32,6 +32,7 @@ #include #include #include +#include #include #include #include @@ -47,12 +48,14 @@ using std::function; using std::get; using std::ignore; using std::make_pair; +using std::make_tuple; using std::numeric_limits; using std::pair; using std::set; using std::string; using std::tie; using std::transform; +using std::tuple; using std::unordered_map; using std::unordered_set; using std::vector; @@ -268,22 +271,10 @@ void UpdateContinueConstructExitBlocks( } } -/// Constructs an error message for construct validation errors -string ConstructErrorString(const Construct& construct, - const string& header_string, - const string& exit_string, - bool post_dominate = false) { - string construct_name; - string header_name; - string exit_name; - string dominate_text; - if (post_dominate) { - dominate_text = "is not post dominated by"; - } else { - dominate_text = "does not dominate"; - } +tuple ConstructNames(ConstructType type) { + string construct_name, header_name, exit_name; - switch (construct.type()) { + switch (type) { case ConstructType::kSelection: construct_name = "selection"; header_name = "selection header"; @@ -301,12 +292,31 @@ string ConstructErrorString(const Construct& construct, break; case ConstructType::kCase: construct_name = "case"; - header_name = "case block"; - exit_name = "exit block"; // TODO(umar): there has to be a better name + header_name = "case entry block"; + exit_name = "case exit block"; break; default: assert(1 == 0 && "Not defined type"); } + + return make_tuple(construct_name, header_name, exit_name); +} + +/// Constructs an error message for construct validation errors +string ConstructErrorString(const Construct& construct, + const string& header_string, + const string& exit_string, + bool post_dominate = false) { + string construct_name, header_name, exit_name, dominate_text; + if (post_dominate) { + dominate_text = "is not post dominated by"; + } else { + dominate_text = "does not dominate"; + } + + tie(construct_name, header_name, exit_name) = + ConstructNames(construct.type()); + // TODO(umar): Add header block for continue constructs to error message return "The " + construct_name + " construct with the " + header_name + " " + header_string + " " + dominate_text + " the " + exit_name + " " + @@ -340,11 +350,33 @@ spv_result_t StructuredControlFlowChecks( } } + // Check the loop headers have exactly one back-edge branching to it + for (BasicBlock* block : function.ordered_blocks()) { + if (block->is_type(kBlockTypeLoop) && + loop_headers.count(block->id()) != 1) { + return _.diag(SPV_ERROR_INVALID_CFG) + << "Loop with header " + _.getIdName(block->id()) + + " is targeted by " + << loop_headers.count(block->id()) + << " back-edges but the standard requires exactly one"; + } + } + // Check construct rules for (const Construct& construct : function.constructs()) { auto header = construct.entry_block(); auto merge = construct.exit_block(); + if (!merge) { + string construct_name, header_name, exit_name; + tie(construct_name, header_name, exit_name) = + ConstructNames(construct.type()); + return _.diag(SPV_ERROR_INTERNAL) + << "Construct " + construct_name + " with " + header_name + " " + + _.getIdName(header->id()) + " does not have a " + + exit_name + ". This may be a bug in the validator."; + } + // if the merge block is reachable then it's dominated by the header if (merge->reachable() && find(merge->dom_begin(), merge->dom_end(), header) == diff --git a/test/Validate.CFG.cpp b/test/Validate.CFG.cpp index 4027946..e9d7dad 100644 --- a/test/Validate.CFG.cpp +++ b/test/Validate.CFG.cpp @@ -1004,6 +1004,43 @@ OpDecorate %id BuiltIn GlobalInvocationId ASSERT_EQ(SPV_SUCCESS, ValidateInstructions()); } +TEST_F(ValidateCFG, LoopWithoutBackEdgesBad) { + string str = R"( + OpCapability Shader + OpMemoryModel Logical GLSL450 + OpEntryPoint Fragment %main "main" + OpName %loop "loop" +%voidt = OpTypeVoid +%funct = OpTypeFunction %voidt +%floatt = OpTypeFloat 32 +%boolt = OpTypeBool +%one = OpConstant %floatt 1 +%two = OpConstant %floatt 2 +%main = OpFunction %voidt None %funct +%entry = OpLabel + OpBranch %loop +%loop = OpLabel + OpLoopMerge %exit %cont None + OpBranch %16 +%16 = OpLabel +%cond = OpFOrdLessThan %boolt %one %two + OpBranchConditional %cond %body %exit +%body = OpLabel + OpReturn +%cont = OpLabel + OpBranch %loop +%exit = OpLabel + OpReturn + OpFunctionEnd +)"; + + CompileSuccessfully(str); + ASSERT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions()); + EXPECT_THAT(getDiagnosticString(), + MatchesRegex("Loop with header .\\[loop\\] is targeted by 0 " + "back-edges but the standard requires exactly one")); +} + /// TODO(umar): Switch instructions /// TODO(umar): Nested CFG constructs } /// namespace -- 2.7.4