Use structural reachability in CFG checks (#4849)
Fixes https://crbug.com/oss-fuzz48578
* Adds structural reachability to basic blocks
* calculated in same manner as reachability, but using structural
successors
* Change structured CFG validation to use structural reachability
instead of reachability
* Fix some invalid reducer cases
diff --git a/source/val/basic_block.cpp b/source/val/basic_block.cpp
index a489ae0..da05db3 100644
--- a/source/val/basic_block.cpp
+++ b/source/val/basic_block.cpp
@@ -30,6 +30,7 @@
successors_(),
type_(0),
reachable_(false),
+ structurally_reachable_(false),
label_(nullptr),
terminator_(nullptr) {}
diff --git a/source/val/basic_block.h b/source/val/basic_block.h
index f778aa0..be5657e 100644
--- a/source/val/basic_block.h
+++ b/source/val/basic_block.h
@@ -84,9 +84,12 @@
return &structural_successors_;
}
- /// Returns true if the block is structurally reachable in the CFG.
+ /// Returns true if the block is reachable in the CFG.
bool reachable() const { return reachable_; }
+ /// Returns true if the block is structurally reachable in the CFG.
+ bool structurally_reachable() const { return structurally_reachable_; }
+
/// Returns true if BasicBlock is of the given type
bool is_type(BlockType type) const {
if (type == kBlockTypeUndefined) return type_.none();
@@ -96,6 +99,11 @@
/// Sets the reachability of the basic block in the CFG
void set_reachable(bool reachability) { reachable_ = reachability; }
+ /// Sets the structural reachability of the basic block in the CFG
+ void set_structurally_reachable(bool reachability) {
+ structurally_reachable_ = reachability;
+ }
+
/// Sets the type of the BasicBlock
void set_type(BlockType type) {
if (type == kBlockTypeUndefined)
@@ -283,6 +291,9 @@
/// True if the block is reachable in the CFG
bool reachable_;
+ /// True if the block is structurally reachable in the CFG
+ bool structurally_reachable_;
+
/// label of this block, if any.
const Instruction* label_;
diff --git a/source/val/validate_cfg.cpp b/source/val/validate_cfg.cpp
index 506b5e5..d4ca20e 100644
--- a/source/val/validate_cfg.cpp
+++ b/source/val/validate_cfg.cpp
@@ -466,7 +466,7 @@
std::vector<BasicBlock*> stack;
stack.push_back(target_block);
std::unordered_set<const BasicBlock*> visited;
- bool target_reachable = target_block->reachable();
+ bool target_reachable = target_block->structurally_reachable();
int target_depth = function->GetBlockDepth(target_block);
while (!stack.empty()) {
auto block = stack.back();
@@ -476,7 +476,7 @@
if (!visited.insert(block).second) continue;
- if (target_reachable && block->reachable() &&
+ if (target_reachable && block->structurally_reachable() &&
target_block->structurally_dominates(*block)) {
// Still in the case construct.
for (auto successor : *block->successors()) {
@@ -549,7 +549,8 @@
if (seen_iter == seen_to_fall_through.end()) {
const auto target_block = function->GetBlock(target).first;
// OpSwitch must dominate all its case constructs.
- if (header->reachable() && target_block->reachable() &&
+ if (header->structurally_reachable() &&
+ target_block->structurally_reachable() &&
!header->structurally_dominates(*target_block)) {
return _.diag(SPV_ERROR_INVALID_CFG, header->label())
<< "Selection header " << _.getIdName(header->id())
@@ -653,7 +654,7 @@
}
// Skip unreachable blocks.
- if (!block->reachable()) continue;
+ if (!block->structurally_reachable()) continue;
if (terminator->opcode() == SpvOpBranchConditional) {
const auto true_label = terminator->GetOperandAs<uint32_t>(1);
@@ -708,7 +709,7 @@
// Check the loop headers have exactly one back-edge branching to it
for (BasicBlock* loop_header : function->ordered_blocks()) {
- if (!loop_header->reachable()) continue;
+ if (!loop_header->structurally_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();
@@ -723,7 +724,7 @@
// Check construct rules
for (const Construct& construct : function->constructs()) {
auto header = construct.entry_block();
- if (!header->reachable()) continue;
+ if (!header->structurally_reachable()) continue;
auto merge = construct.exit_block();
if (!merge) {
@@ -784,7 +785,7 @@
// Check that for all non-header blocks, all predecessors are within this
// construct.
for (auto pred : *block->predecessors()) {
- if (pred->reachable() && !construct_blocks.count(pred)) {
+ if (pred->structurally_reachable() && !construct_blocks.count(pred)) {
return _.diag(SPV_ERROR_INVALID_CFG, _.FindDef(pred->id()))
<< "block <ID> " << pred->id() << " branches to the "
<< construct_name << " construct, but not to the "
@@ -800,7 +801,7 @@
merge_inst.opcode() == SpvOpLoopMerge) {
uint32_t merge_id = merge_inst.GetOperandAs<uint32_t>(0);
auto merge_block = function->GetBlock(merge_id).first;
- if (merge_block->reachable() &&
+ if (merge_block->structurally_reachable() &&
!construct_blocks.count(merge_block)) {
return _.diag(SPV_ERROR_INVALID_CFG, _.FindDef(block->id()))
<< "Header block " << _.getIdName(block->id())
@@ -1113,6 +1114,26 @@
}
}
}
+
+ // Repeat for structural reachability.
+ for (auto& f : _.functions()) {
+ std::vector<BasicBlock*> stack;
+ auto entry = f.first_block();
+ // Skip function declarations.
+ if (entry) stack.push_back(entry);
+
+ while (!stack.empty()) {
+ auto block = stack.back();
+ stack.pop_back();
+
+ if (block->structurally_reachable()) continue;
+
+ block->set_structurally_reachable(true);
+ for (auto succ : *block->structural_successors()) {
+ stack.push_back(succ);
+ }
+ }
+ }
}
spv_result_t ControlFlowPass(ValidationState_t& _, const Instruction* inst) {
diff --git a/test/reduce/structured_loop_to_selection_test.cpp b/test/reduce/structured_loop_to_selection_test.cpp
index 0cfcfdf..d203f3e 100644
--- a/test/reduce/structured_loop_to_selection_test.cpp
+++ b/test/reduce/structured_loop_to_selection_test.cpp
@@ -2957,7 +2957,7 @@
OpLoopMerge %12 %13 None
OpBranch %12
%13 = OpLabel
- OpBranchConditional %6 %9 %11
+ OpBranch %11
%12 = OpLabel
OpBranch %10
%10 = OpLabel
@@ -2999,7 +2999,7 @@
OpLoopMerge %12 %13 None
OpBranch %12
%13 = OpLabel
- OpBranchConditional %6 %9 %11
+ OpBranch %11
%12 = OpLabel
OpBranch %9
%10 = OpLabel
@@ -3036,7 +3036,7 @@
OpSelectionMerge %12 None
OpBranchConditional %6 %12 %12
%13 = OpLabel
- OpBranchConditional %6 %9 %11
+ OpBranch %11
%12 = OpLabel
OpBranch %9
%10 = OpLabel
@@ -3050,8 +3050,7 @@
TEST(StructuredLoopToSelectionReductionPassTest,
UnreachableInnerLoopContinueBranchingToOuterLoopMerge2) {
- // In this test, the branch to the outer loop merge from the inner loop's
- // continue is part of a structured selection.
+ // In this test, the unreachable continue is composed of multiple blocks.
std::string shader = R"(
OpCapability Shader
%1 = OpExtInstImport "GLSL.std.450"
@@ -3073,8 +3072,7 @@
OpLoopMerge %12 %13 None
OpBranch %12
%13 = OpLabel
- OpSelectionMerge %14 None
- OpBranchConditional %6 %9 %14
+ OpBranch %14
%14 = OpLabel
OpBranch %11
%12 = OpLabel
@@ -3118,8 +3116,7 @@
OpLoopMerge %12 %13 None
OpBranch %12
%13 = OpLabel
- OpSelectionMerge %14 None
- OpBranchConditional %6 %9 %14
+ OpBranch %14
%14 = OpLabel
OpBranch %11
%12 = OpLabel
@@ -3158,8 +3155,7 @@
OpSelectionMerge %12 None
OpBranchConditional %6 %12 %12
%13 = OpLabel
- OpSelectionMerge %14 None
- OpBranchConditional %6 %9 %14
+ OpBranch %14
%14 = OpLabel
OpBranch %11
%12 = OpLabel
diff --git a/test/val/val_cfg_test.cpp b/test/val/val_cfg_test.cpp
index 2423b1e..ede51a9 100644
--- a/test/val/val_cfg_test.cpp
+++ b/test/val/val_cfg_test.cpp
@@ -4555,6 +4555,36 @@
"must be different labels"));
}
+TEST_F(ValidateCFG, BadBackEdgeUnreachableContinue) {
+ const std::string text = R"(
+OpCapability Shader
+OpCapability Linkage
+OpMemoryModel Logical GLSL450
+%1 = OpTypeVoid
+%2 = OpTypeFunction %1
+%3 = OpFunction %1 None %2
+%4 = OpLabel
+OpBranch %5
+%5 = OpLabel
+OpLoopMerge %6 %7 None
+OpBranch %8
+%8 = OpLabel
+OpBranch %5
+%7 = OpLabel
+OpUnreachable
+%6 = OpLabel
+OpUnreachable
+OpFunctionEnd
+)";
+
+ CompileSuccessfully(text);
+ EXPECT_EQ(SPV_ERROR_INVALID_CFG, ValidateInstructions());
+ EXPECT_THAT(
+ getDiagnosticString(),
+ HasSubstr("The continue construct with the continue target 7[%7] "
+ "does not structurally dominate the back-edge block 8[%8]"));
+}
+
} // namespace
} // namespace val
} // namespace spvtools
