Use structural dominance to validate cfg (#4832)
* Structural dominance introduced in SPIR-V 1.6 rev2
* Changes the structured cfg validation to use structural dominance
* structural dominance is based on a cfg where merge and continue
declarations are counted as graph edges
* Basic blocks now track structural predecessors and structural
successors
* Add validation for entry into a loop
* Fixed an issue with inlining a single block loop
* The continue target needs to be moved to the latch block
* Simplify the calculation of structured exits
* no longer requires block depth
* Update many invalid tests
diff --git a/source/opt/inline_pass.cpp b/source/opt/inline_pass.cpp
index 2cc3125..6e73f1c 100644
--- a/source/opt/inline_pass.cpp
+++ b/source/opt/inline_pass.cpp
@@ -508,6 +508,37 @@
delete &*loop_merge_itr;
}
+void InlinePass::UpdateSingleBlockLoopContinueTarget(
+ uint32_t new_id, std::vector<std::unique_ptr<BasicBlock>>* new_blocks) {
+ auto& header = new_blocks->front();
+ auto* merge_inst = header->GetLoopMergeInst();
+
+ // The back-edge block is split at the branch to create a new back-edge
+ // block. The old block is modified to branch to the new block. The loop
+ // merge instruction is updated to declare the new block as the continue
+ // target. This has the effect of changing the loop from being a large
+ // continue construct and an empty loop construct to being a loop with a loop
+ // construct and a trivial continue construct. This change is made to satisfy
+ // structural dominance.
+
+ // Add the new basic block.
+ std::unique_ptr<BasicBlock> new_block =
+ MakeUnique<BasicBlock>(NewLabel(new_id));
+ auto& old_backedge = new_blocks->back();
+ auto old_branch = old_backedge->tail();
+
+ // Move the old back edge into the new block.
+ std::unique_ptr<Instruction> br(&*old_branch);
+ new_block->AddInstruction(std::move(br));
+
+ // Add a branch to the new block from the old back-edge block.
+ AddBranch(new_id, &old_backedge);
+ new_blocks->push_back(std::move(new_block));
+
+ // Update the loop's continue target to the new block.
+ merge_inst->SetInOperand(1u, {new_id});
+}
+
bool InlinePass::GenInlineCode(
std::vector<std::unique_ptr<BasicBlock>>* new_blocks,
std::vector<std::unique_ptr<Instruction>>* new_vars,
@@ -639,9 +670,19 @@
// Finalize inline code.
new_blocks->push_back(std::move(new_blk_ptr));
- if (caller_is_loop_header && (new_blocks->size() > 1))
+ if (caller_is_loop_header && (new_blocks->size() > 1)) {
MoveLoopMergeInstToFirstBlock(new_blocks);
+ // If the loop was a single basic block previously, update it's structure.
+ auto& header = new_blocks->front();
+ auto* merge_inst = header->GetLoopMergeInst();
+ if (merge_inst->GetSingleWordInOperand(1u) == header->id()) {
+ auto new_id = context()->TakeNextId();
+ if (new_id == 0) return false;
+ UpdateSingleBlockLoopContinueTarget(new_id, new_blocks);
+ }
+ }
+
// Update block map given replacement blocks.
for (auto& blk : *new_blocks) {
id2block_[blk->id()] = &*blk;
diff --git a/source/opt/inline_pass.h b/source/opt/inline_pass.h
index 9a5429b..f204395 100644
--- a/source/opt/inline_pass.h
+++ b/source/opt/inline_pass.h
@@ -235,6 +235,12 @@
// Move the OpLoopMerge from the last block back to the first.
void MoveLoopMergeInstToFirstBlock(
std::vector<std::unique_ptr<BasicBlock>>* new_blocks);
+
+ // Update the structure of single block loops so that the inlined code ends
+ // up in the loop construct and a new continue target is added to satisfy
+ // structural dominance.
+ void UpdateSingleBlockLoopContinueTarget(
+ uint32_t new_id, std::vector<std::unique_ptr<BasicBlock>>* new_blocks);
};
} // namespace opt
diff --git a/source/val/basic_block.cpp b/source/val/basic_block.cpp
index b2a8793..a489ae0 100644
--- a/source/val/basic_block.cpp
+++ b/source/val/basic_block.cpp
@@ -24,7 +24,8 @@
BasicBlock::BasicBlock(uint32_t label_id)
: id_(label_id),
immediate_dominator_(nullptr),
- immediate_post_dominator_(nullptr),
+ immediate_structural_dominator_(nullptr),
+ immediate_structural_post_dominator_(nullptr),
predecessors_(),
successors_(),
type_(0),
@@ -36,21 +37,32 @@
immediate_dominator_ = dom_block;
}
-void BasicBlock::SetImmediatePostDominator(BasicBlock* pdom_block) {
- immediate_post_dominator_ = pdom_block;
+void BasicBlock::SetImmediateStructuralDominator(BasicBlock* dom_block) {
+ immediate_structural_dominator_ = dom_block;
+}
+
+void BasicBlock::SetImmediateStructuralPostDominator(BasicBlock* pdom_block) {
+ immediate_structural_post_dominator_ = pdom_block;
}
const BasicBlock* BasicBlock::immediate_dominator() const {
return immediate_dominator_;
}
-const BasicBlock* BasicBlock::immediate_post_dominator() const {
- return immediate_post_dominator_;
+const BasicBlock* BasicBlock::immediate_structural_dominator() const {
+ return immediate_structural_dominator_;
+}
+
+const BasicBlock* BasicBlock::immediate_structural_post_dominator() const {
+ return immediate_structural_post_dominator_;
}
BasicBlock* BasicBlock::immediate_dominator() { return immediate_dominator_; }
-BasicBlock* BasicBlock::immediate_post_dominator() {
- return immediate_post_dominator_;
+BasicBlock* BasicBlock::immediate_structural_dominator() {
+ return immediate_structural_dominator_;
+}
+BasicBlock* BasicBlock::immediate_structural_post_dominator() {
+ return immediate_structural_post_dominator_;
}
void BasicBlock::RegisterSuccessors(
@@ -58,6 +70,10 @@
for (auto& block : next_blocks) {
block->predecessors_.push_back(this);
successors_.push_back(block);
+
+ // Register structural successors/predecessors too.
+ block->structural_predecessors_.push_back(this);
+ structural_successors_.push_back(block);
}
}
@@ -67,10 +83,16 @@
std::find(other.dom_begin(), other.dom_end(), this));
}
-bool BasicBlock::postdominates(const BasicBlock& other) const {
- return (this == &other) ||
- !(other.pdom_end() ==
- std::find(other.pdom_begin(), other.pdom_end(), this));
+bool BasicBlock::structurally_dominates(const BasicBlock& other) const {
+ return (this == &other) || !(other.structural_dom_end() ==
+ std::find(other.structural_dom_begin(),
+ other.structural_dom_end(), this));
+}
+
+bool BasicBlock::structurally_postdominates(const BasicBlock& other) const {
+ return (this == &other) || !(other.structural_pdom_end() ==
+ std::find(other.structural_pdom_begin(),
+ other.structural_pdom_end(), this));
}
BasicBlock::DominatorIterator::DominatorIterator() : current_(nullptr) {}
@@ -107,21 +129,43 @@
return DominatorIterator();
}
-const BasicBlock::DominatorIterator BasicBlock::pdom_begin() const {
- return DominatorIterator(
- this, [](const BasicBlock* b) { return b->immediate_post_dominator(); });
+const BasicBlock::DominatorIterator BasicBlock::structural_dom_begin() const {
+ return DominatorIterator(this, [](const BasicBlock* b) {
+ return b->immediate_structural_dominator();
+ });
}
-BasicBlock::DominatorIterator BasicBlock::pdom_begin() {
- return DominatorIterator(
- this, [](const BasicBlock* b) { return b->immediate_post_dominator(); });
+BasicBlock::DominatorIterator BasicBlock::structural_dom_begin() {
+ return DominatorIterator(this, [](const BasicBlock* b) {
+ return b->immediate_structural_dominator();
+ });
}
-const BasicBlock::DominatorIterator BasicBlock::pdom_end() const {
+const BasicBlock::DominatorIterator BasicBlock::structural_dom_end() const {
return DominatorIterator();
}
-BasicBlock::DominatorIterator BasicBlock::pdom_end() {
+BasicBlock::DominatorIterator BasicBlock::structural_dom_end() {
+ return DominatorIterator();
+}
+
+const BasicBlock::DominatorIterator BasicBlock::structural_pdom_begin() const {
+ return DominatorIterator(this, [](const BasicBlock* b) {
+ return b->immediate_structural_post_dominator();
+ });
+}
+
+BasicBlock::DominatorIterator BasicBlock::structural_pdom_begin() {
+ return DominatorIterator(this, [](const BasicBlock* b) {
+ return b->immediate_structural_post_dominator();
+ });
+}
+
+const BasicBlock::DominatorIterator BasicBlock::structural_pdom_end() const {
+ return DominatorIterator();
+}
+
+BasicBlock::DominatorIterator BasicBlock::structural_pdom_end() {
return DominatorIterator();
}
diff --git a/source/val/basic_block.h b/source/val/basic_block.h
index 47cd06d..f778aa0 100644
--- a/source/val/basic_block.h
+++ b/source/val/basic_block.h
@@ -64,7 +64,27 @@
/// Returns the successors of the BasicBlock
std::vector<BasicBlock*>* successors() { return &successors_; }
- /// Returns true if the block is reachable in the CFG
+ /// Returns the structural successors of the BasicBlock
+ std::vector<BasicBlock*>* structural_predecessors() {
+ return &structural_predecessors_;
+ }
+
+ /// Returns the structural predecessors of the BasicBlock
+ const std::vector<BasicBlock*>* structural_predecessors() const {
+ return &structural_predecessors_;
+ }
+
+ /// Returns the structural successors of the BasicBlock
+ std::vector<BasicBlock*>* structural_successors() {
+ return &structural_successors_;
+ }
+
+ /// Returns the structural predecessors of the BasicBlock
+ const std::vector<BasicBlock*>* structural_successors() const {
+ return &structural_successors_;
+ }
+
+ /// Returns true if the block is structurally reachable in the CFG.
bool reachable() const { return reachable_; }
/// Returns true if BasicBlock is of the given type
@@ -89,10 +109,15 @@
/// @param[in] dom_block The dominator block
void SetImmediateDominator(BasicBlock* dom_block);
+ /// Sets the immediate dominator of this basic block
+ ///
+ /// @param[in] dom_block The dominator block
+ void SetImmediateStructuralDominator(BasicBlock* dom_block);
+
/// Sets the immediate post dominator of this basic block
///
/// @param[in] pdom_block The post dominator block
- void SetImmediatePostDominator(BasicBlock* pdom_block);
+ void SetImmediateStructuralPostDominator(BasicBlock* pdom_block);
/// Returns the immediate dominator of this basic block
BasicBlock* immediate_dominator();
@@ -100,11 +125,17 @@
/// Returns the immediate dominator of this basic block
const BasicBlock* immediate_dominator() const;
- /// Returns the immediate post dominator of this basic block
- BasicBlock* immediate_post_dominator();
+ /// Returns the immediate dominator of this basic block
+ BasicBlock* immediate_structural_dominator();
+
+ /// Returns the immediate dominator of this basic block
+ const BasicBlock* immediate_structural_dominator() const;
/// Returns the immediate post dominator of this basic block
- const BasicBlock* immediate_post_dominator() const;
+ BasicBlock* immediate_structural_post_dominator();
+
+ /// Returns the immediate post dominator of this basic block
+ const BasicBlock* immediate_structural_post_dominator() const;
/// Returns the label instruction for the block, or nullptr if not set.
const Instruction* label() const { return label_; }
@@ -132,9 +163,18 @@
/// Assumes dominators have been computed.
bool dominates(const BasicBlock& other) const;
- /// Returns true if this block postdominates the other block.
- /// Assumes dominators have been computed.
- bool postdominates(const BasicBlock& other) const;
+ /// Returns true if this block structurally dominates the other block.
+ /// Assumes structural dominators have been computed.
+ bool structurally_dominates(const BasicBlock& other) const;
+
+ /// Returns true if this block structurally postdominates the other block.
+ /// Assumes structural dominators have been computed.
+ bool structurally_postdominates(const BasicBlock& other) const;
+
+ void RegisterStructuralSuccessor(BasicBlock* block) {
+ block->structural_predecessors_.push_back(this);
+ structural_successors_.push_back(block);
+ }
/// @brief A BasicBlock dominator iterator class
///
@@ -191,18 +231,32 @@
/// block
DominatorIterator dom_end();
+ /// Returns a dominator iterator which points to the current block
+ const DominatorIterator structural_dom_begin() const;
+
+ /// Returns a dominator iterator which points to the current block
+ DominatorIterator structural_dom_begin();
+
+ /// Returns a dominator iterator which points to one element past the first
+ /// block
+ const DominatorIterator structural_dom_end() const;
+
+ /// Returns a dominator iterator which points to one element past the first
+ /// block
+ DominatorIterator structural_dom_end();
+
/// Returns a post dominator iterator which points to the current block
- const DominatorIterator pdom_begin() const;
+ const DominatorIterator structural_pdom_begin() const;
/// Returns a post dominator iterator which points to the current block
- DominatorIterator pdom_begin();
+ DominatorIterator structural_pdom_begin();
/// Returns a post dominator iterator which points to one element past the
/// last block
- const DominatorIterator pdom_end() const;
+ const DominatorIterator structural_pdom_end() const;
/// Returns a post dominator iterator which points to one element past the
/// last block
- DominatorIterator pdom_end();
+ DominatorIterator structural_pdom_end();
private:
/// Id of the BasicBlock
@@ -211,8 +265,11 @@
/// Pointer to the immediate dominator of the BasicBlock
BasicBlock* immediate_dominator_;
- /// Pointer to the immediate dominator of the BasicBlock
- BasicBlock* immediate_post_dominator_;
+ /// Pointer to the immediate structural dominator of the BasicBlock
+ BasicBlock* immediate_structural_dominator_;
+
+ /// Pointer to the immediate structural post dominator of the BasicBlock
+ BasicBlock* immediate_structural_post_dominator_;
/// The set of predecessors of the BasicBlock
std::vector<BasicBlock*> predecessors_;
@@ -231,6 +288,9 @@
/// Terminator of this block.
const Instruction* terminator_;
+
+ std::vector<BasicBlock*> structural_predecessors_;
+ std::vector<BasicBlock*> structural_successors_;
};
/// @brief Returns true if the iterators point to the same element or if both
diff --git a/source/val/construct.cpp b/source/val/construct.cpp
index 251e2bb..6e367f3 100644
--- a/source/val/construct.cpp
+++ b/source/val/construct.cpp
@@ -70,60 +70,48 @@
void Construct::set_exit(BasicBlock* block) { exit_block_ = block; }
-Construct::ConstructBlockSet Construct::blocks(Function* function) const {
- auto header = entry_block();
- auto merge = exit_block();
- assert(header);
- int header_depth = function->GetBlockDepth(const_cast<BasicBlock*>(header));
- ConstructBlockSet construct_blocks;
- std::unordered_set<BasicBlock*> corresponding_headers;
- for (auto& other : corresponding_constructs()) {
- // The corresponding header can be the same block as this construct's
- // header for loops with no loop construct. In those cases, don't add the
- // loop header as it prevents finding any blocks in the construct.
- if (type() != ConstructType::kContinue || other->entry_block() != header) {
- corresponding_headers.insert(other->entry_block());
+Construct::ConstructBlockSet Construct::blocks(Function* /*function*/) const {
+ const auto header = entry_block();
+ const auto exit = exit_block();
+ const bool is_continue = type() == ConstructType::kContinue;
+ const bool is_loop = type() == ConstructType::kLoop;
+ const BasicBlock* continue_header = nullptr;
+ if (is_loop) {
+ // The only corresponding construct for a loop is the continue.
+ for (auto& other : corresponding_constructs()) {
+ continue_header = other->entry_block();
+ break;
}
}
std::vector<BasicBlock*> stack;
stack.push_back(const_cast<BasicBlock*>(header));
+ ConstructBlockSet construct_blocks;
while (!stack.empty()) {
- BasicBlock* block = stack.back();
+ auto* block = stack.back();
stack.pop_back();
- if (merge == block && ExitBlockIsMergeBlock()) {
- // Merge block is not part of the construct.
- continue;
- }
+ if (header->structurally_dominates(*block)) {
+ bool include = false;
+ if (is_continue && exit->structurally_postdominates(*block)) {
+ // Continue construct include blocks dominated by the continue target
+ // and post-dominated by the back-edge block.
+ include = true;
+ } else if (!exit->structurally_dominates(*block)) {
+ // Selection and loop constructs include blocks dominated by the header
+ // and not dominated by the merge.
+ include = true;
+ if (is_loop && continue_header->structurally_dominates(*block)) {
+ // Loop constructs have an additional constraint that they do not
+ // include blocks dominated by the continue construct. Since all
+ // blocks in the continue construct are dominated by the continue
+ // target, we just test for dominance by continue target.
+ include = false;
+ }
+ }
+ if (include) {
+ if (!construct_blocks.insert(block).second) continue;
- if (corresponding_headers.count(block)) {
- // Entered a corresponding construct.
- continue;
- }
-
- int block_depth = function->GetBlockDepth(block);
- if (block_depth < header_depth) {
- // Broke to outer construct.
- continue;
- }
-
- // In a loop, the continue target is at a depth of the loop construct + 1.
- // A selection construct nested directly within the loop construct is also
- // at the same depth. It is valid, however, to branch directly to the
- // continue target from within the selection construct.
- if (block != header && block_depth == header_depth &&
- type() == ConstructType::kSelection &&
- block->is_type(kBlockTypeContinue)) {
- // Continued to outer construct.
- continue;
- }
-
- if (!construct_blocks.insert(block).second) continue;
-
- if (merge != block) {
- for (auto succ : *block->successors()) {
- // All blocks in the construct must be dominated by the header.
- if (header->dominates(*succ)) {
+ for (auto succ : *block->structural_successors()) {
stack.push_back(succ);
}
}
@@ -181,11 +169,12 @@
for (auto& use : block->label()->uses()) {
if ((use.first->opcode() == SpvOpLoopMerge ||
use.first->opcode() == SpvOpSelectionMerge) &&
- use.second == 1 && use.first->block()->dominates(*block)) {
+ use.second == 1 &&
+ use.first->block()->structurally_dominates(*block)) {
return use.first->block();
}
}
- return block->immediate_dominator();
+ return block->immediate_structural_dominator();
};
bool seen_switch = false;
@@ -201,7 +190,7 @@
terminator->opcode() == SpvOpSwitch)) {
auto merge_target = merge_inst->GetOperandAs<uint32_t>(0u);
auto merge_block = merge_inst->function()->GetBlock(merge_target).first;
- if (merge_block->dominates(*header)) {
+ if (merge_block->structurally_dominates(*header)) {
block = NextBlock(block);
continue;
}
diff --git a/source/val/function.cpp b/source/val/function.cpp
index f3292b0..fc7ccd0 100644
--- a/source/val/function.cpp
+++ b/source/val/function.cpp
@@ -73,6 +73,8 @@
BasicBlock& continue_target_block = blocks_.at(continue_id);
assert(current_block_ &&
"RegisterLoopMerge must be called when called within a block");
+ current_block_->RegisterStructuralSuccessor(&merge_block);
+ current_block_->RegisterStructuralSuccessor(&continue_target_block);
current_block_->set_type(kBlockTypeLoop);
merge_block.set_type(kBlockTypeMerge);
@@ -101,6 +103,7 @@
current_block_->set_type(kBlockTypeSelection);
merge_block.set_type(kBlockTypeMerge);
merge_block_header_[&merge_block] = current_block_;
+ current_block_->RegisterStructuralSuccessor(&merge_block);
AddConstruct({ConstructType::kSelection, current_block(), &merge_block});
@@ -251,16 +254,6 @@
};
}
-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);
@@ -269,11 +262,35 @@
};
}
+Function::GetBlocksFunction Function::AugmentedStructuralCFGSuccessorsFunction()
+ const {
+ return [this](const BasicBlock* block) {
+ auto where = augmented_successors_map_.find(block);
+ return where == augmented_successors_map_.end()
+ ? block->structural_successors()
+ : &(*where).second;
+ };
+}
+
+Function::GetBlocksFunction
+Function::AugmentedStructuralCFGPredecessorsFunction() const {
+ return [this](const BasicBlock* block) {
+ auto where = augmented_predecessors_map_.find(block);
+ return where == augmented_predecessors_map_.end()
+ ? block->structural_predecessors()
+ : &(*where).second;
+ };
+}
+
void Function::ComputeAugmentedCFG() {
// Compute the successors of the pseudo-entry block, and
// the predecessors of the pseudo exit block.
- auto succ_func = [](const BasicBlock* b) { return b->successors(); };
- auto pred_func = [](const BasicBlock* b) { return b->predecessors(); };
+ auto succ_func = [](const BasicBlock* b) {
+ return b->structural_successors();
+ };
+ auto pred_func = [](const BasicBlock* b) {
+ return b->structural_predecessors();
+ };
CFA<BasicBlock>::ComputeAugmentedCFG(
ordered_blocks_, &pseudo_entry_block_, &pseudo_exit_block_,
&augmented_successors_map_, &augmented_predecessors_map_, succ_func,
diff --git a/source/val/function.h b/source/val/function.h
index 2fe30bd..126b1dc 100644
--- a/source/val/function.h
+++ b/source/val/function.h
@@ -184,12 +184,12 @@
std::function<const std::vector<BasicBlock*>*(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;
+ /// Returns the block structural successors function for the augmented CFG.
+ GetBlocksFunction AugmentedStructuralCFGSuccessorsFunction() const;
+ /// Returns the block structural predecessors function for the augmented CFG.
+ GetBlocksFunction AugmentedStructuralCFGPredecessorsFunction() const;
/// Returns the control flow nesting depth of the given basic block.
/// This function only works when you have structured control flow.
diff --git a/source/val/validate_cfg.cpp b/source/val/validate_cfg.cpp
index be05c9c..9806462 100644
--- a/source/val/validate_cfg.cpp
+++ b/source/val/validate_cfg.cpp
@@ -477,7 +477,7 @@
if (!visited.insert(block).second) continue;
if (target_reachable && block->reachable() &&
- target_block->dominates(*block)) {
+ target_block->structurally_dominates(*block)) {
// Still in the case construct.
for (auto successor : *block->successors()) {
stack.push_back(successor);
@@ -550,7 +550,7 @@
const auto target_block = function->GetBlock(target).first;
// OpSwitch must dominate all its case constructs.
if (header->reachable() && target_block->reachable() &&
- !header->dominates(*target_block)) {
+ !header->structurally_dominates(*target_block)) {
return _.diag(SPV_ERROR_INVALID_CFG, header->label())
<< "Selection header " << _.getIdName(header->id())
<< " does not dominate its case construct "
@@ -723,9 +723,10 @@
// Check construct rules
for (const Construct& construct : function->constructs()) {
auto header = construct.entry_block();
+ if (!header->reachable()) continue;
auto merge = construct.exit_block();
- if (header->reachable() && !merge) {
+ if (!merge) {
std::string construct_name, header_name, exit_name;
std::tie(construct_name, header_name, exit_name) =
ConstructNames(construct.type());
@@ -735,28 +736,27 @@
exit_name + ". This may be a bug in the validator.";
}
- // If the exit block is reachable then it's dominated by the
- // header.
- if (merge && merge->reachable()) {
- if (!header->dominates(*merge)) {
- return _.diag(SPV_ERROR_INVALID_CFG, _.FindDef(merge->id()))
- << ConstructErrorString(construct, _.getIdName(header->id()),
- _.getIdName(merge->id()),
- "does not dominate");
- }
- // If it's really a merge block for a selection or loop, then it must be
- // *strictly* dominated by the header.
- if (construct.ExitBlockIsMergeBlock() && (header == merge)) {
- return _.diag(SPV_ERROR_INVALID_CFG, _.FindDef(merge->id()))
- << ConstructErrorString(construct, _.getIdName(header->id()),
- _.getIdName(merge->id()),
- "does not strictly dominate");
- }
+ // If the header is reachable, the merge is guaranteed to be structurally
+ // reachable.
+ if (!header->structurally_dominates(*merge)) {
+ return _.diag(SPV_ERROR_INVALID_CFG, _.FindDef(merge->id()))
+ << ConstructErrorString(construct, _.getIdName(header->id()),
+ _.getIdName(merge->id()),
+ "does not dominate");
}
+ // If it's really a merge block for a selection or loop, then it must be
+ // *strictly* dominated by the header.
+ if (construct.ExitBlockIsMergeBlock() && (header == merge)) {
+ return _.diag(SPV_ERROR_INVALID_CFG, _.FindDef(merge->id()))
+ << ConstructErrorString(construct, _.getIdName(header->id()),
+ _.getIdName(merge->id()),
+ "does not strictly dominate");
+ }
+
// Check post-dominance for continue constructs. But dominance and
// post-dominance only make sense when the construct is reachable.
- if (header->reachable() && construct.type() == ConstructType::kContinue) {
- if (!merge->postdominates(*header)) {
+ if (construct.type() == ConstructType::kContinue) {
+ if (!merge->structurally_postdominates(*header)) {
return _.diag(SPV_ERROR_INVALID_CFG, _.FindDef(merge->id()))
<< ConstructErrorString(construct, _.getIdName(header->id()),
_.getIdName(merge->id()),
@@ -771,7 +771,7 @@
for (auto block : construct_blocks) {
// Check that all exits from the construct are via structured exits.
for (auto succ : *block->successors()) {
- if (block->reachable() && !construct_blocks.count(succ) &&
+ if (!construct_blocks.count(succ) &&
!construct.IsStructuredExit(_, succ)) {
return _.diag(SPV_ERROR_INVALID_CFG, _.FindDef(block->id()))
<< "block <ID> " << _.getIdName(block->id()) << " exits the "
@@ -813,6 +813,43 @@
}
}
+ if (construct.type() == ConstructType::kLoop) {
+ // If the continue target differs from the loop header, then check that
+ // all edges into the continue construct come from within the loop.
+ const auto index = header->terminator() - &_.ordered_instructions()[0];
+ const auto& merge_inst = _.ordered_instructions()[index - 1];
+ const auto continue_id = merge_inst.GetOperandAs<uint32_t>(1);
+ const auto* continue_inst = _.FindDef(continue_id);
+ // OpLabel instructions aren't stored as part of the basic block for
+ // legacy reaasons. Grab the next instruction and use it's block pointer
+ // instead.
+ const auto next_index =
+ (continue_inst - &_.ordered_instructions()[0]) + 1;
+ const auto& next_inst = _.ordered_instructions()[next_index];
+ const auto* continue_target = next_inst.block();
+ if (header->id() != continue_id) {
+ for (auto pred : *continue_target->predecessors()) {
+ // Ignore back-edges from within the continue construct.
+ bool is_back_edge = false;
+ for (auto back_edge : back_edges) {
+ uint32_t back_edge_block;
+ uint32_t header_block;
+ std::tie(back_edge_block, header_block) = back_edge;
+ if (header_block == continue_id && back_edge_block == pred->id())
+ is_back_edge = true;
+ }
+ if (!construct_blocks.count(pred) && !is_back_edge) {
+ return _.diag(SPV_ERROR_INVALID_CFG, pred->terminator())
+ << "Block " << _.getIdName(pred->id())
+ << " branches to the loop continue target "
+ << _.getIdName(continue_id)
+ << ", but is not contained in the associated loop construct "
+ << _.getIdName(header->id());
+ }
+ }
+ }
+ }
+
// Checks rules for case constructs.
if (construct.type() == ConstructType::kSelection &&
header->terminator()->opcode() == SpvOpSwitch) {
@@ -850,15 +887,12 @@
<< _.getIdName(function.id());
}
- // Set each block's immediate dominator and immediate postdominator,
- // and find all back-edges.
+ // Set each block's immediate dominator.
//
// We want to analyze all the blocks in the function, even in degenerate
// control flow cases including unreachable blocks. So use the augmented
// CFG to ensure we cover all the blocks.
std::vector<const BasicBlock*> postorder;
- std::vector<const BasicBlock*> postdom_postorder;
- std::vector<std::pair<uint32_t, uint32_t>> back_edges;
auto ignore_block = [](const BasicBlock*) {};
auto ignore_edge = [](const BasicBlock*, const BasicBlock*) {};
auto no_terminal_blocks = [](const BasicBlock*) { return false; };
@@ -874,30 +908,7 @@
if (edge.first != edge.second)
edge.first->SetImmediateDominator(edge.second);
}
-
- /// calculate post dominators
- CFA<BasicBlock>::DepthFirstTraversal(
- function.pseudo_exit_block(),
- function.AugmentedCFGPredecessorsFunction(), ignore_block,
- [&](const BasicBlock* b) { postdom_postorder.push_back(b); },
- ignore_edge, no_terminal_blocks);
- auto postdom_edges = CFA<BasicBlock>::CalculateDominators(
- postdom_postorder, function.AugmentedCFGSuccessorsFunction());
- for (auto edge : postdom_edges) {
- edge.first->SetImmediatePostDominator(edge.second);
- }
- /// calculate back edges.
- CFA<BasicBlock>::DepthFirstTraversal(
- function.pseudo_entry_block(),
- function
- .AugmentedCFGSuccessorsFunctionIncludingHeaderToContinueEdge(),
- ignore_block, ignore_block,
- [&](const BasicBlock* from, const BasicBlock* to) {
- back_edges.emplace_back(from->id(), to->id());
- },
- no_terminal_blocks);
}
- UpdateContinueConstructExitBlocks(function, back_edges);
auto& blocks = function.ordered_blocks();
if (!blocks.empty()) {
@@ -931,6 +942,52 @@
/// Structured control flow checks are only required for shader capabilities
if (_.HasCapability(SpvCapabilityShader)) {
+ // Calculate structural dominance.
+ postorder.clear();
+ std::vector<const BasicBlock*> postdom_postorder;
+ std::vector<std::pair<uint32_t, uint32_t>> back_edges;
+ if (!function.ordered_blocks().empty()) {
+ /// calculate dominators
+ CFA<BasicBlock>::DepthFirstTraversal(
+ function.first_block(),
+ function.AugmentedStructuralCFGSuccessorsFunction(), ignore_block,
+ [&](const BasicBlock* b) { postorder.push_back(b); }, ignore_edge,
+ no_terminal_blocks);
+ auto edges = CFA<BasicBlock>::CalculateDominators(
+ postorder, function.AugmentedStructuralCFGPredecessorsFunction());
+ for (auto edge : edges) {
+ if (edge.first != edge.second)
+ edge.first->SetImmediateStructuralDominator(edge.second);
+ }
+
+ /// calculate post dominators
+ CFA<BasicBlock>::DepthFirstTraversal(
+ function.pseudo_exit_block(),
+ function.AugmentedStructuralCFGPredecessorsFunction(), ignore_block,
+ [&](const BasicBlock* b) { postdom_postorder.push_back(b); },
+ ignore_edge, no_terminal_blocks);
+ auto postdom_edges = CFA<BasicBlock>::CalculateDominators(
+ postdom_postorder,
+ function.AugmentedStructuralCFGSuccessorsFunction());
+ for (auto edge : postdom_edges) {
+ edge.first->SetImmediateStructuralPostDominator(edge.second);
+ }
+ /// calculate back edges.
+ CFA<BasicBlock>::DepthFirstTraversal(
+ function.pseudo_entry_block(),
+ function.AugmentedStructuralCFGSuccessorsFunction(), ignore_block,
+ ignore_block,
+ [&](const BasicBlock* from, const BasicBlock* to) {
+ // A back edge must be a real edge. Since the augmented successors
+ // contain structural edges, filter those from consideration.
+ for (const auto* succ : *(from->successors())) {
+ if (succ == to) back_edges.emplace_back(from->id(), to->id());
+ }
+ },
+ no_terminal_blocks);
+ }
+ UpdateContinueConstructExitBlocks(function, back_edges);
+
if (auto error =
StructuredControlFlowChecks(_, &function, back_edges, postorder))
return error;
diff --git a/test/opt/aggressive_dead_code_elim_test.cpp b/test/opt/aggressive_dead_code_elim_test.cpp
index 25f8541..d15c79d 100644
--- a/test/opt/aggressive_dead_code_elim_test.cpp
+++ b/test/opt/aggressive_dead_code_elim_test.cpp
@@ -3541,9 +3541,11 @@
OpBranch %16
%16 = OpLabel
OpSelectionMerge %18 None
-OpSwitch %13 %18 0 %17 1 %15
+OpSwitch %13 %18 0 %17 1 %19
%17 = OpLabel
OpStore %3 %uint_1
+OpBranch %19
+%19 = OpLabel
OpBranch %15
%15 = OpLabel
OpBranch %12
diff --git a/test/opt/dead_branch_elim_test.cpp b/test/opt/dead_branch_elim_test.cpp
index b04c8f5..1095d3b 100644
--- a/test/opt/dead_branch_elim_test.cpp
+++ b/test/opt/dead_branch_elim_test.cpp
@@ -2570,9 +2570,8 @@
TEST_F(DeadBranchElimTest, SelectionMergeWithExitToLoop3) {
// Checks that if a selection merge construct contains a conditional branch
- // to the merge of a surrounding loop, the selection merge, and another block
- // inside the selection merge, then we must keep the OpSelectionMerge
- // instruction on that branch.
+ // to the selection merge, and another block inside the selection merge,
+ // then we must keep the OpSelectionMerge instruction on that branch.
const std::string predefs = R"(
OpCapability Shader
%1 = OpExtInstImport "GLSL.std.450"
@@ -2586,6 +2585,7 @@
%true = OpConstantTrue %bool
%uint = OpTypeInt 32 0
%undef_int = OpUndef %uint
+%undef_bool = OpUndef %bool
)";
const std::string body =
@@ -2596,7 +2596,7 @@
; CHECK-NEXT: OpBranch [[bb2:%\w+]]
; CHECK: [[bb2]] = OpLabel
; CHECK-NEXT: OpSelectionMerge [[sel_merge:%\w+]] None
-; CHECK-NEXT: OpSwitch {{%\w+}} [[sel_merge]] 0 [[loop_merge]] 1 [[bb3:%\w+]]
+; CHECK-NEXT: OpBranchConditional {{%\w+}} [[sel_merge]] [[bb3:%\w+]]
; CHECK: [[bb3]] = OpLabel
; CHECK-NEXT: OpBranch [[sel_merge]]
; CHECK: [[sel_merge]] = OpLabel
@@ -2613,7 +2613,8 @@
OpSelectionMerge %sel_merge None
OpBranchConditional %true %bb2 %bb4
%bb2 = OpLabel
-OpSwitch %undef_int %sel_merge 0 %loop_merge 1 %bb3
+;OpSwitch %undef_int %sel_merge 0 %loop_merge 1 %bb3
+OpBranchConditional %undef_bool %sel_merge %bb3
%bb3 = OpLabel
OpBranch %sel_merge
%bb4 = OpLabel
@@ -2632,9 +2633,8 @@
TEST_F(DeadBranchElimTest, SelectionMergeWithExitToLoopContinue3) {
// Checks that if a selection merge construct contains a conditional branch
- // to the merge of a surrounding loop, the selection merge, and another block
- // inside the selection merge, then we must keep the OpSelectionMerge
- // instruction on that branch.
+ // the selection merge, and another block inside the selection merge, then we
+ // must keep the OpSelectionMerge instruction on that branch.
const std::string predefs = R"(
OpCapability Shader
%1 = OpExtInstImport "GLSL.std.450"
@@ -2648,6 +2648,7 @@
%true = OpConstantTrue %bool
%uint = OpTypeInt 32 0
%undef_int = OpUndef %uint
+%undef_bool = OpUndef %bool
)";
const std::string body =
@@ -2660,7 +2661,7 @@
; CHECK-NEXT: OpBranch [[bb2:%\w+]]
; CHECK: [[bb2]] = OpLabel
; CHECK-NEXT: OpSelectionMerge [[sel_merge:%\w+]] None
-; CHECK-NEXT: OpSwitch {{%\w+}} [[sel_merge]] 0 [[loop_continue]] 1 [[bb3:%\w+]]
+; CHECK-NEXT: OpBranchConditional {{%\w+}} [[sel_merge]] [[bb3:%\w+]]
; CHECK: [[bb3]] = OpLabel
; CHECK-NEXT: OpBranch [[sel_merge]]
; CHECK: [[sel_merge]] = OpLabel
@@ -2679,131 +2680,7 @@
OpSelectionMerge %sel_merge None
OpBranchConditional %true %bb2 %bb4
%bb2 = OpLabel
-OpSwitch %undef_int %sel_merge 0 %cont 1 %bb3
-%bb3 = OpLabel
-OpBranch %sel_merge
-%bb4 = OpLabel
-OpBranch %sel_merge
-%sel_merge = OpLabel
-OpBranch %loop_merge
-%cont = OpLabel
-OpBranch %loop_header
-%loop_merge = OpLabel
-OpReturn
-OpFunctionEnd
-)";
-
- SinglePassRunAndMatch<DeadBranchElimPass>(predefs + body, true);
-}
-
-TEST_F(DeadBranchElimTest, SelectionMergeWithExitToLoop4) {
- // Same as |SelectionMergeWithExitToLoop|, except the branch in the selection
- // construct is an |OpSwitch| instead of an |OpConditionalBranch|. The
- // OpSelectionMerge instruction is not needed in this case either.
- const std::string predefs = R"(
-OpCapability Shader
-%1 = OpExtInstImport "GLSL.std.450"
-OpMemoryModel Logical GLSL450
-OpEntryPoint Fragment %main "main"
-OpExecutionMode %main OriginUpperLeft
-OpSource GLSL 140
-%void = OpTypeVoid
-%func_type = OpTypeFunction %void
-%bool = OpTypeBool
-%true = OpConstantTrue %bool
-%uint = OpTypeInt 32 0
-%undef_int = OpUndef %uint
-)";
-
- const std::string body =
- R"(
-; CHECK: OpLoopMerge [[loop_merge:%\w+]]
-; CHECK-NEXT: OpBranch [[bb1:%\w+]]
-; CHECK: [[bb1]] = OpLabel
-; CHECK-NEXT: OpBranch [[bb2:%\w+]]
-; CHECK: [[bb2]] = OpLabel
-; CHECK-NEXT: OpSelectionMerge
-; CHECK-NEXT: OpSwitch {{%\w+}} [[bb3:%\w+]] 0 [[loop_merge]] 1 [[bb3:%\w+]]
-; CHECK: [[bb3]] = OpLabel
-; CHECK-NEXT: OpBranch [[sel_merge:%\w+]]
-; CHECK: [[sel_merge]] = OpLabel
-; CHECK-NEXT: OpBranch [[loop_merge]]
-; CHECK: [[loop_merge]] = OpLabel
-; CHECK-NEXT: OpReturn
-%main = OpFunction %void None %func_type
-%entry_bb = OpLabel
-OpBranch %loop_header
-%loop_header = OpLabel
-OpLoopMerge %loop_merge %cont None
-OpBranch %bb1
-%bb1 = OpLabel
-OpSelectionMerge %sel_merge None
-OpBranchConditional %true %bb2 %bb4
-%bb2 = OpLabel
-OpSelectionMerge %bb3 None
-OpSwitch %undef_int %bb3 0 %loop_merge 1 %bb3
-%bb3 = OpLabel
-OpBranch %sel_merge
-%bb4 = OpLabel
-OpBranch %sel_merge
-%sel_merge = OpLabel
-OpBranch %loop_merge
-%cont = OpLabel
-OpBranch %loop_header
-%loop_merge = OpLabel
-OpReturn
-OpFunctionEnd
-)";
-
- SinglePassRunAndMatch<DeadBranchElimPass>(predefs + body, true);
-}
-
-TEST_F(DeadBranchElimTest, SelectionMergeWithExitToLoopContinue4) {
- // Same as |SelectionMergeWithExitToLoopContinue|, except the branch in the
- // selection construct is an |OpSwitch| instead of an |OpConditionalBranch|.
- // The OpSelectionMerge instruction is not needed in this case either.
- const std::string predefs = R"(
-OpCapability Shader
-%1 = OpExtInstImport "GLSL.std.450"
-OpMemoryModel Logical GLSL450
-OpEntryPoint Fragment %main "main"
-OpExecutionMode %main OriginUpperLeft
-OpSource GLSL 140
-%void = OpTypeVoid
-%func_type = OpTypeFunction %void
-%bool = OpTypeBool
-%true = OpConstantTrue %bool
-%uint = OpTypeInt 32 0
-%undef_int = OpUndef %uint
-)";
-
- const std::string body =
- R"(
-; CHECK: OpLoopMerge [[loop_merge:%\w+]] [[loop_cont:%\w+]]
-; CHECK-NEXT: OpBranch [[bb1:%\w+]]
-; CHECK: [[bb1]] = OpLabel
-; CHECK-NEXT: OpBranch [[bb2:%\w+]]
-; CHECK: [[bb2]] = OpLabel
-; CHECK-NEXT: OpSelectionMerge
-; CHECK-NEXT: OpSwitch {{%\w+}} [[bb3:%\w+]] 0 [[loop_cont]] 1 [[bb3:%\w+]]
-; CHECK: [[bb3]] = OpLabel
-; CHECK-NEXT: OpBranch [[sel_merge:%\w+]]
-; CHECK: [[sel_merge]] = OpLabel
-; CHECK-NEXT: OpBranch [[loop_merge]]
-; CHECK: [[loop_merge]] = OpLabel
-; CHECK-NEXT: OpReturn
-%main = OpFunction %void None %func_type
-%entry_bb = OpLabel
-OpBranch %loop_header
-%loop_header = OpLabel
-OpLoopMerge %loop_merge %cont None
-OpBranch %bb1
-%bb1 = OpLabel
-OpSelectionMerge %sel_merge None
-OpBranchConditional %true %bb2 %bb4
-%bb2 = OpLabel
-OpSelectionMerge %bb3 None
-OpSwitch %undef_int %bb3 0 %cont 1 %bb3
+OpBranchConditional %undef_bool %sel_merge %bb3
%bb3 = OpLabel
OpBranch %sel_merge
%bb4 = OpLabel
@@ -3036,9 +2913,11 @@
; CHECK-NEXT: OpLoopMerge [[outer_merge:%\w+]] [[outer_cont:%\w+]] None
; CHECK-NEXT: OpBranch [[inner:%\w+]]
; CHECK: [[inner]] = OpLabel
-; CHECK: OpLoopMerge [[outer_cont]] [[inner_cont:%\w+]] None
+; CHECK: OpLoopMerge [[inner_merge:%\w+]] [[inner_cont:%\w+]] None
; CHECK: [[inner_cont]] = OpLabel
; CHECK-NEXT: OpBranch [[inner]]
+; CHECK: [[inner_merge]] = OpLabel
+; CHECK-NEXT: OpUnreachable
; CHECK: [[outer_cont]] = OpLabel
; CHECK-NEXT: OpBranch [[outer]]
; CHECK: [[outer_merge]] = OpLabel
@@ -3058,7 +2937,7 @@
OpLoopMerge %outer_merge %outer_continue None
OpBranch %inner_loop
%inner_loop = OpLabel
-OpLoopMerge %outer_continue %inner_continue None
+OpLoopMerge %inner_merge %inner_continue None
OpBranch %inner_body
%inner_body = OpLabel
OpSelectionMerge %inner_continue None
@@ -3066,7 +2945,9 @@
%ret = OpLabel
OpReturn
%inner_continue = OpLabel
-OpBranchConditional %true %outer_continue %inner_loop
+OpBranchConditional %true %inner_merge %inner_loop
+%inner_merge = OpLabel
+OpBranch %outer_continue
%outer_continue = OpLabel
OpBranchConditional %true %outer_merge %outer_loop
%outer_merge = OpLabel
diff --git a/test/opt/inline_test.cpp b/test/opt/inline_test.cpp
index cefd8e5..d804f7c 100644
--- a/test/opt/inline_test.cpp
+++ b/test/opt/inline_test.cpp
@@ -1533,9 +1533,11 @@
%9 = OpLabel
OpBranch %10
%10 = OpLabel
-OpLoopMerge %12 %10 None
+OpLoopMerge %12 %15 None
OpBranch %14
%14 = OpLabel
+OpBranch %15
+%15 = OpLabel
OpBranchConditional %true %10 %12
%12 = OpLabel
OpReturn
@@ -1694,7 +1696,7 @@
OpBranch %13
%13 = OpLabel
%14 = OpCopyObject %bool %false
-OpLoopMerge %16 %13 None
+OpLoopMerge %16 %22 None
OpBranch %17
%17 = OpLabel
%19 = OpCopyObject %bool %true
@@ -1702,6 +1704,8 @@
OpBranchConditional %true %20 %20
%20 = OpLabel
%21 = OpPhi %bool %19 %17
+OpBranch %22
+%22 = OpLabel
OpBranchConditional %true %13 %16
%16 = OpLabel
OpReturn
diff --git a/test/opt/pass_merge_return_test.cpp b/test/opt/pass_merge_return_test.cpp
index 21960d1..04bd5d9 100644
--- a/test/opt/pass_merge_return_test.cpp
+++ b/test/opt/pass_merge_return_test.cpp
@@ -2231,7 +2231,7 @@
TEST_F(MergeReturnPassTest, UnreachableMergeAndContinue) {
// Make sure that the pass can handle a single block that is both a merge and
- // a continue.
+ // a continue. Note that this is invalid SPIR-V.
const std::string text =
R"(
OpCapability Shader
@@ -2265,7 +2265,7 @@
)";
SetAssembleOptions(SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
- auto result = SinglePassRunAndDisassemble<MergeReturnPass>(text, true, true);
+ auto result = SinglePassRunAndDisassemble<MergeReturnPass>(text, true, false);
// Not looking for any particular output. Other tests do that.
// Just want to make sure the check for unreachable blocks does not emit an
diff --git a/test/val/val_cfg_test.cpp b/test/val/val_cfg_test.cpp
index 7647746..afab3be 100644
--- a/test/val/val_cfg_test.cpp
+++ b/test/val/val_cfg_test.cpp
@@ -637,41 +637,6 @@
" %Main = OpFunction %void None %9\n"));
}
-TEST_P(ValidateCFG, HeaderDoesntDominatesMergeBad) {
- bool is_shader = GetParam() == SpvCapabilityShader;
- Block entry("entry");
- Block head("head", SpvOpBranchConditional);
- Block f("f");
- Block merge("merge", SpvOpReturn);
-
- head.SetBody("%cond = OpSLessThan %boolt %one %two\n");
-
- if (is_shader) head.AppendBody("OpSelectionMerge %merge None\n");
-
- std::string str = GetDefaultHeader(GetParam()) +
- nameOps("head", "merge", std::make_pair("func", "Main")) +
- types_consts() +
- "%func = OpFunction %voidt None %funct\n";
-
- str += entry >> merge;
- str += head >> std::vector<Block>({merge, f});
- str += f >> merge;
- str += merge;
- str += "OpFunctionEnd\n";
-
- CompileSuccessfully(str);
- if (is_shader) {
- ASSERT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
- EXPECT_THAT(
- getDiagnosticString(),
- MatchesRegex("The selection construct with the selection header "
- ".\\[%head\\] does not dominate the merge block "
- ".\\[%merge\\]\n %merge = OpLabel\n"));
- } else {
- ASSERT_EQ(SPV_SUCCESS, ValidateInstructions());
- }
-}
-
TEST_P(ValidateCFG, HeaderDoesntStrictlyDominateMergeBad) {
// If a merge block is reachable, then it must be strictly dominated by
// its header block.
@@ -907,16 +872,7 @@
TEST_P(ValidateCFG, UnreachableContinueUnreachableLoopInst) {
CompileSuccessfully(GetUnreachableContinueUnreachableLoopInst(GetParam()));
- if (GetParam() == SpvCapabilityShader) {
- // Shader causes additional structured CFG checks that cause a failure.
- ASSERT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
- EXPECT_THAT(getDiagnosticString(),
- HasSubstr("Back-edges (1[%branch] -> 3[%target]) can only be "
- "formed between a block and a loop header."));
-
- } else {
- ASSERT_EQ(SPV_SUCCESS, ValidateInstructions());
- }
+ ASSERT_EQ(SPV_SUCCESS, ValidateInstructions());
}
std::string GetUnreachableMergeWithComplexBody(SpvCapability cap) {
@@ -1070,12 +1026,10 @@
std::string header = GetDefaultHeader(cap);
Block entry("entry");
- Block foo("foo", SpvOpBranch);
Block branch("branch", SpvOpBranch);
Block merge("merge", SpvOpReturn);
Block target("target", SpvOpBranch);
- foo >> target;
target >> branch;
entry.AppendBody("%placeholder = OpVariable %intptrt Function\n");
@@ -1092,7 +1046,6 @@
str += branch >> std::vector<Block>({merge});
str += merge;
str += target;
- str += foo;
str += "OpFunctionEnd\n";
return str;
@@ -1156,6 +1109,7 @@
Block body("body", SpvOpBranchConditional);
Block t("t", SpvOpReturn);
Block f("f", SpvOpReturn);
+ Block pre_target("pre_target", SpvOpBranch);
target >> branch;
body.SetBody("%cond = OpSLessThan %boolt %one %two\n");
@@ -1163,10 +1117,10 @@
std::string str = header;
if (cap == SpvCapabilityShader) {
branch.AppendBody("OpLoopMerge %merge %target None\n");
- body.AppendBody("OpSelectionMerge %target None\n");
+ body.AppendBody("OpSelectionMerge %pre_target None\n");
}
- str += nameOps("branch", "merge", "target", "body", "t", "f",
+ str += nameOps("branch", "merge", "pre_target", "target", "body", "t", "f",
std::make_pair("func", "Main"));
str += types_consts();
str += "%func = OpFunction %voidt None %funct\n";
@@ -1176,6 +1130,7 @@
str += t;
str += f;
str += merge;
+ str += pre_target >> target;
str += target;
str += "OpFunctionEnd\n";
@@ -1296,9 +1251,10 @@
loop2.SetBody("OpLoopMerge %loop2_merge %loop2 None\n");
}
- std::string str = GetDefaultHeader(GetParam()) +
- nameOps("loop2", "loop2_merge") + types_consts() +
- "%func = OpFunction %voidt None %funct\n";
+ std::string str =
+ GetDefaultHeader(GetParam()) +
+ nameOps("loop1", "loop1_cont_break_block", "loop2", "loop2_merge") +
+ types_consts() + "%func = OpFunction %voidt None %funct\n";
str += entry >> loop1;
str += loop1 >> loop1_cont_break_block;
@@ -1824,40 +1780,6 @@
<< 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 %boolt %one %two\n");
- if (is_shader) {
- loop.SetBody("OpLoopMerge %merge %loop None\n");
- }
-
- std::string str = GetDefaultHeader(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();
-}
-
// Unit test to check the case where a basic block is the entry block of 2
// different constructs. In this case, the basic block is the entry block of a
// continue construct as well as a selection construct. See issue# 517 for more
@@ -2872,8 +2794,8 @@
CompileSuccessfully(text);
EXPECT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
EXPECT_THAT(getDiagnosticString(),
- HasSubstr("block <ID> 9 branches to the loop construct, but not "
- "to the loop header <ID> 7"));
+ HasSubstr("Back-edges (10[%10] -> 9[%9]) can only be formed "
+ "between a block and a loop header"));
}
TEST_F(ValidateCFG, LoopMergeMergeBlockNotLabel) {
@@ -3275,9 +3197,10 @@
CompileSuccessfully(text);
EXPECT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
- EXPECT_THAT(getDiagnosticString(),
- HasSubstr("block <ID> 13[%13] exits the selection headed by <ID> "
- "9[%9], but not via a structured exit"));
+ EXPECT_THAT(
+ getDiagnosticString(),
+ HasSubstr("The continue construct with the continue target 9[%9] is not "
+ "post dominated by the back-edge block 13[%13]"));
}
TEST_F(ValidateCFG, BreakFromSwitch) {
