From b51b80980c57b61b061aa203a9d481e51af2c5cd Mon Sep 17 00:00:00 2001 From: David Neto Date: Fri, 5 Aug 2016 11:14:21 -0400 Subject: [PATCH] Validator cfg fixes - Find unreachable continue targets. Look for back edges with a DFS traversal separate from the dominance traversals, where we count the OpLoopMerge from the header to the continue target as an edge in the graph. - It's ok for a loop to have multiple back edges, provided they are all from the same block, and we call that the latch block. This may require a clarification/fix in the SPIR-V spec. - Compute postdominance correctly for infinite loop: Bias *predecessor* traversal root finding so that you use a later block in the original list. This ensures that for certain simple infinite loops in the CFG where neither block branches to a node without successors, that we'll compute the loop header as dominating the latch block, and the latch block as postdominating the loop header. --- source/val/Function.cpp | 46 +++++++++++++- source/val/Function.h | 9 +++ source/validate_cfg.cpp | 53 ++++++++-------- test/Validate.CFG.cpp | 157 ++++++++++++++++++++++++++++++++++++++++++------ 4 files changed, 220 insertions(+), 45 deletions(-) diff --git a/source/val/Function.cpp b/source/val/Function.cpp index 73007c1..68bf532 100644 --- a/source/val/Function.cpp +++ b/source/val/Function.cpp @@ -50,7 +50,9 @@ using libspirv::BasicBlock; // Computes a minimal set of root nodes required to traverse, in the forward // direction, the CFG represented by the given vector of blocks, and successor -// and predecessor functions. +// and predecessor functions. When considering adding two nodes, each having +// predecessors, favour using the one that appears earlier on the input blocks +// list. std::vector TraversalRoots(const std::vector& blocks, libspirv::get_blocks_func succ_func, libspirv::get_blocks_func pred_func) { @@ -200,7 +202,6 @@ void Function::RegisterBlockEnd(vector next_list, assert( current_block_ && "RegisterBlockEnd can only be called when parsing a binary in a block"); - vector next_blocks; next_blocks.reserve(next_list.size()); @@ -215,6 +216,21 @@ void Function::RegisterBlockEnd(vector next_list, next_blocks.push_back(&inserted_block->second); } + if (current_block_->is_type(kBlockTypeLoop)) { + // For each loop header, record the set of its successors, and include + // its continue target if the continue target is not the loop header + // itself. + std::vector& next_blocks_plus_continue_target = + loop_header_successors_plus_continue_target_map_[current_block_]; + next_blocks_plus_continue_target = next_blocks; + // If this block is marked as Loop-type, then the continue construct is + // the most recently created CFG construct. + auto continue_target = cfg_constructs_.back().entry_block(); + if (continue_target != current_block_) { + next_blocks_plus_continue_target.push_back(continue_target); + } + } + current_block_->RegisterBranchInstruction(branch_instruction); current_block_->RegisterSuccessors(next_blocks); current_block_ = nullptr; @@ -292,6 +308,16 @@ Function::GetBlocksFunction Function::AugmentedCFGSuccessorsFunction() const { }; } +Function::GetBlocksFunction +Function::AugmentedCFGSuccessorsFunctionIncludingHeaderToContinueEdge() const { + return [this](const BasicBlock* block) { + auto where = loop_header_successors_plus_continue_target_map_.find(block); + return where == loop_header_successors_plus_continue_target_map_.end() + ? AugmentedCFGSuccessorsFunction()(block) + : &(*where).second; + }; +} + Function::GetBlocksFunction Function::AugmentedCFGPredecessorsFunction() const { return [this](const BasicBlock* block) { auto where = augmented_predecessors_map_.find(block); @@ -306,7 +332,21 @@ void Function::ComputeAugmentedCFG() { auto succ_func = [](const BasicBlock* b) { return b->successors(); }; auto pred_func = [](const BasicBlock* b) { return b->predecessors(); }; auto sources = TraversalRoots(ordered_blocks_, succ_func, pred_func); - auto sinks = TraversalRoots(ordered_blocks_, pred_func, succ_func); + + // For the predecessor traversals, reverse the order of blocks. This + // will affect the post-dominance calculation as follows: + // - Suppose you have blocks A and B, with A appearing before B in + // the list of blocks. + // - Also, A branches only to B, and B branches only to A. + // - We want to compute A as dominating B, and B as post-dominating B. + // By using reversed blocks for predecessor traversal roots discovery, + // we'll add an edge from B to the pseudo-exit node, rather than from A. + // All this is needed to correctly process the dominance/post-dominance + // constraint when A is a loop header that points to itself as its + // own continue target, and B is the latch block for the loop. + std::vector reversed_blocks(ordered_blocks_.rbegin(), + ordered_blocks_.rend()); + auto sinks = TraversalRoots(reversed_blocks, pred_func, succ_func); // Wire up the pseudo entry block. augmented_successors_map_[&pseudo_entry_block_] = sources; diff --git a/source/val/Function.h b/source/val/Function.h index cdf868c..d9a0ae0 100644 --- a/source/val/Function.h +++ b/source/val/Function.h @@ -180,6 +180,9 @@ class Function { std::function*(const BasicBlock*)>; /// Returns the block successors function for the augmented CFG. GetBlocksFunction AugmentedCFGSuccessorsFunction() const; + /// Like AugmentedCFGSuccessorsFunction, but also includes a forward edge from + /// a loop header block to its continue target, if they are different blocks. + GetBlocksFunction AugmentedCFGSuccessorsFunctionIncludingHeaderToContinueEdge() const; /// Returns the block predecessors function for the augmented CFG. GetBlocksFunction AugmentedCFGPredecessorsFunction() const; @@ -262,6 +265,12 @@ class Function { std::unordered_map> augmented_predecessors_map_; + // Maps a structured loop header to its CFG successors and also its + // continue target if that continue target is not the loop header + // itself. This might have duplicates. + std::unordered_map> + loop_header_successors_plus_continue_target_map_; + /// The constructs that are available in this function std::list cfg_constructs_; diff --git a/source/validate_cfg.cpp b/source/validate_cfg.cpp index a901d66..6342a91 100644 --- a/source/validate_cfg.cpp +++ b/source/validate_cfg.cpp @@ -30,7 +30,7 @@ #include #include -#include +#include #include #include #include @@ -237,7 +237,6 @@ void UpdateContinueConstructExitBlocks( uint32_t back_edge_block_id; uint32_t loop_header_block_id; tie(back_edge_block_id, loop_header_block_id) = edge; - auto is_this_header = [=](Construct& c) { return c.type() == ConstructType::kLoop && c.entry_block()->id() == loop_header_block_id; @@ -314,7 +313,9 @@ spv_result_t StructuredControlFlowChecks( const vector>& back_edges) { /// Check all backedges target only loop headers and have exactly one /// back-edge branching to it - set loop_headers; + + // Map a loop header to blocks with back-edges to the loop header. + std::map> loop_latch_blocks; for (auto back_edge : back_edges) { uint32_t back_edge_block; uint32_t header_block; @@ -325,26 +326,20 @@ spv_result_t StructuredControlFlowChecks( << _.getIdName(header_block) << ") can only be formed between a block and a loop header."; } - bool success; - tie(ignore, success) = loop_headers.insert(header_block); - if (!success) { - // TODO(umar): List the back-edge blocks that are branching to loop - // header - return _.diag(SPV_ERROR_INVALID_CFG) - << "Loop header " << _.getIdName(header_block) - << " targeted by multiple back-edges"; - } + loop_latch_blocks[header_block].insert(back_edge_block); } // Check the loop headers have exactly one back-edge branching to it - for (BasicBlock* block : function.ordered_blocks()) { - if (block->reachable() && block->is_type(kBlockTypeLoop) && - loop_headers.count(block->id()) != 1) { + for (BasicBlock* loop_header : function.ordered_blocks()) { + if (!loop_header->reachable()) continue; + if (!loop_header->is_type(kBlockTypeLoop)) continue; + auto loop_header_id = loop_header->id(); + auto num_latch_blocks = loop_latch_blocks[loop_header_id].size(); + if (num_latch_blocks != 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"; + << "Loop header " << _.getIdName(loop_header_id) + << " is targeted by " << num_latch_blocks + << " back-edge blocks but the standard requires exactly one"; } } @@ -418,15 +413,15 @@ spv_result_t PerformCfgChecks(ValidationState_t& _) { vector postorder; vector postdom_postorder; vector> back_edges; + auto ignore_block = [](cbb_ptr) {}; + auto ignore_edge = [](cbb_ptr, cbb_ptr) {}; if (!function.ordered_blocks().empty()) { /// calculate dominators DepthFirstTraversal(function.first_block(), function.AugmentedCFGSuccessorsFunction(), - [](cbb_ptr) {}, + ignore_block, [&](cbb_ptr b) { postorder.push_back(b); }, - [&](cbb_ptr from, cbb_ptr to) { - back_edges.emplace_back(from->id(), to->id()); - }); + ignore_edge); auto edges = libspirv::CalculateDominators( postorder, function.AugmentedCFGPredecessorsFunction()); for (auto edge : edges) { @@ -436,14 +431,22 @@ spv_result_t PerformCfgChecks(ValidationState_t& _) { /// calculate post dominators DepthFirstTraversal(function.pseudo_exit_block(), function.AugmentedCFGPredecessorsFunction(), - [](cbb_ptr) {}, + ignore_block, [&](cbb_ptr b) { postdom_postorder.push_back(b); }, - [&](cbb_ptr, cbb_ptr) {}); + ignore_edge); auto postdom_edges = libspirv::CalculateDominators( postdom_postorder, function.AugmentedCFGSuccessorsFunction()); for (auto edge : postdom_edges) { edge.first->SetImmediatePostDominator(edge.second); } + /// calculate back edges. + DepthFirstTraversal( + function.pseudo_entry_block(), + function + .AugmentedCFGSuccessorsFunctionIncludingHeaderToContinueEdge(), + ignore_block, ignore_block, [&](cbb_ptr from, cbb_ptr to) { + back_edges.emplace_back(from->id(), to->id()); + }); } UpdateContinueConstructExitBlocks(function, back_edges); diff --git a/test/Validate.CFG.cpp b/test/Validate.CFG.cpp index 1866bf2..6a1920e 100644 --- a/test/Validate.CFG.cpp +++ b/test/Validate.CFG.cpp @@ -937,22 +937,24 @@ TEST_P(ValidateCFG, BranchingToSameNonLoopHeaderBlockBad) { } } -TEST_P(ValidateCFG, MultipleBackEdgesToLoopHeaderBad) { +TEST_P(ValidateCFG, MultipleBackEdgeBlocksToLoopHeaderBad) { bool is_shader = GetParam() == SpvCapabilityShader; Block entry("entry"); Block loop("loop", SpvOpBranchConditional); - Block cont("cont", SpvOpBranchConditional); + Block back0("back0"); + Block back1("back1"); Block merge("merge", SpvOpReturn); entry.SetBody("%cond = OpSLessThan %intt %one %two\n"); - if (is_shader) loop.SetBody("OpLoopMerge %merge %loop None\n"); + if (is_shader) loop.SetBody("OpLoopMerge %merge %back0 None\n"); - string str = header(GetParam()) + nameOps("cont", "loop") + types_consts() + - "%func = OpFunction %voidt None %funct\n"; + string str = header(GetParam()) + nameOps("loop", "back0", "back1") + + types_consts() + "%func = OpFunction %voidt None %funct\n"; str += entry >> loop; - str += loop >> vector({cont, merge}); - str += cont >> vector({loop, loop}); + str += loop >> vector({back0, back1}); + str += back0 >> loop; + str += back1 >> loop; str += merge; str += "OpFunctionEnd"; @@ -961,7 +963,9 @@ TEST_P(ValidateCFG, MultipleBackEdgesToLoopHeaderBad) { ASSERT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions()); EXPECT_THAT(getDiagnosticString(), MatchesRegex( - "Loop header .\\[loop\\] targeted by multiple back-edges")); + "Loop header .\\[loop\\] is targeted by 2 back-edge blocks " + "but the standard requires exactly one")) + << str; } else { ASSERT_EQ(SPV_SUCCESS, ValidateInstructions()); } @@ -1027,7 +1031,7 @@ TEST_P(ValidateCFG, BranchOutOfConstructToMergeBad) { EXPECT_THAT(getDiagnosticString(), MatchesRegex("The continue construct with the continue target " ".\\[loop\\] is not post dominated by the " - "back-edge block .\\[cont\\]")); + "back-edge block .\\[cont\\]")) << str; } else { ASSERT_EQ(SPV_SUCCESS, ValidateInstructions()); } @@ -1109,10 +1113,35 @@ OpDecorate %id BuiltIn GlobalInvocationId str += "OpFunctionEnd"; CompileSuccessfully(str); - ASSERT_EQ(SPV_SUCCESS, ValidateInstructions()); + EXPECT_EQ(SPV_SUCCESS, ValidateInstructions()); } -TEST_F(ValidateCFG, LoopWithoutBackEdgesBad) { +TEST_F(ValidateCFG, LoopWithZeroBackEdgesBad) { + string str = R"( + OpCapability Shader + OpMemoryModel Logical GLSL450 + OpEntryPoint Fragment %main "main" + OpName %loop "loop" +%voidt = OpTypeVoid +%funct = OpTypeFunction %voidt +%main = OpFunction %voidt None %funct +%loop = OpLabel + OpLoopMerge %exit %exit None + OpBranch %exit +%exit = OpLabel + OpReturn + OpFunctionEnd +)"; + CompileSuccessfully(str); + ASSERT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions()); + EXPECT_THAT( + getDiagnosticString(), + MatchesRegex("Loop header .\\[loop\\] is targeted by " + "0 back-edge blocks but the standard requires exactly " + "one")); +} + +TEST_F(ValidateCFG, LoopWithBackEdgeFromUnreachableContinueConstructGood) { string str = R"( OpCapability Shader OpMemoryModel Logical GLSL450 @@ -1135,18 +1164,15 @@ TEST_F(ValidateCFG, LoopWithoutBackEdgesBad) { OpBranchConditional %cond %body %exit %body = OpLabel OpReturn -%cont = OpLabel - OpBranch %loop +%cont = OpLabel ; Reachable only from OpLoopMerge ContinueTarget parameter + OpBranch %loop ; Should be considered a back-edge %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")); + EXPECT_EQ(SPV_SUCCESS, ValidateInstructions()) << getDiagnosticString(); } TEST_P(ValidateCFG, @@ -1184,6 +1210,103 @@ TEST_P(ValidateCFG, EXPECT_EQ(SPV_SUCCESS, ValidateInstructions()) << getDiagnosticString(); } +TEST_P(ValidateCFG, ContinueTargetCanBeMergeBlockForNestedStructureGood) { + // This example is valid. It shows that the validator can't just add + // an edge from the loop head to the continue target. If that edge + // is added, then the "if_merge" block is both the continue target + // for the loop and also the merge block for the nested selection, but + // then it wouldn't be dominated by "if_head", the header block for the + // nested selection. + bool is_shader = GetParam() == SpvCapabilityShader; + Block entry("entry"); + Block loop("loop"); + Block if_head("if_head", SpvOpBranchConditional); + Block if_true("if_true"); + Block if_merge("if_merge", SpvOpBranchConditional); + Block merge("merge", SpvOpReturn); + + entry.SetBody("%cond = OpSLessThan %intt %one %two\n"); + if (is_shader) { + loop.SetBody("OpLoopMerge %merge %if_merge None\n"); + if_head.SetBody("OpSelectionMerge %if_merge None\n"); + } + + string str = header(GetParam()) + nameOps("entry", "loop", "if_head", + "if_true", "if_merge", "merge") + + types_consts() + "%func = OpFunction %voidt None %funct\n"; + + str += entry >> loop; + str += loop >> if_head; + str += if_head >> vector({if_true, if_merge}); + str += if_true >> if_merge; + str += if_merge >> vector({loop, merge}); + str += merge; + str += "OpFunctionEnd"; + + CompileSuccessfully(str); + EXPECT_EQ(SPV_SUCCESS, ValidateInstructions()) << getDiagnosticString(); +} + +TEST_P(ValidateCFG, SingleLatchBlockMultipleBranchesToLoopHeader) { + // This test case ensures we allow both branches of a loop latch block + // to go back to the loop header. It still counts as a single back edge. + bool is_shader = GetParam() == SpvCapabilityShader; + Block entry("entry"); + Block loop("loop", SpvOpBranchConditional); + Block latch("latch", SpvOpBranchConditional); + Block merge("merge", SpvOpReturn); + + entry.SetBody("%cond = OpSLessThan %intt %one %two\n"); + if (is_shader) { + loop.SetBody("OpLoopMerge %merge %latch None\n"); + } + + string str = header(GetParam()) + nameOps("entry", "loop", "latch", "merge") + + types_consts() + "%func = OpFunction %voidt None %funct\n"; + + str += entry >> loop; + str += loop >> vector({latch, merge}); + str += latch >> vector({loop, loop}); // This is the key + str += merge; + str += "OpFunctionEnd"; + + CompileSuccessfully(str); + EXPECT_EQ(SPV_SUCCESS, ValidateInstructions()) << str + << getDiagnosticString(); +} + +TEST_P(ValidateCFG, SingleLatchBlockHeaderContinueTargetIsItselfGood) { + // This test case ensures we don't count a Continue Target from a loop + // header to itself as a self-loop when computing back edges. + // Also, it detects that there is an edge from %latch to the pseudo-exit + // node, rather than from %loop. In particular, it detects that we + // have used the *reverse* textual order of blocks when computing + // predecessor traversal roots. + bool is_shader = GetParam() == SpvCapabilityShader; + Block entry("entry"); + Block loop("loop"); + Block latch("latch"); + Block merge("merge", SpvOpReturn); + + entry.SetBody("%cond = OpSLessThan %intt %one %two\n"); + if (is_shader) { + loop.SetBody("OpLoopMerge %merge %loop None\n"); + } + + string str = header(GetParam()) + nameOps("entry", "loop", "latch", "merge") + + types_consts() + "%func = OpFunction %voidt None %funct\n"; + + str += entry >> loop; + str += loop >> latch; + str += latch >> loop; + str += merge; + str += "OpFunctionEnd"; + + CompileSuccessfully(str); + EXPECT_EQ(SPV_SUCCESS, ValidateInstructions()) << str + << getDiagnosticString(); +} + /// TODO(umar): Switch instructions /// TODO(umar): Nested CFG constructs } /// namespace -- 2.7.4