reduce: add large tests and fix (#2947)
* Add larger reducer tests.
* Fix conditional_branch_to_simple_conditional_branch_opportunity pass.
diff --git a/source/reduce/conditional_branch_to_simple_conditional_branch_opportunity_finder.cpp b/source/reduce/conditional_branch_to_simple_conditional_branch_opportunity_finder.cpp
index 2feca4a..0bd93b9 100644
--- a/source/reduce/conditional_branch_to_simple_conditional_branch_opportunity_finder.cpp
+++ b/source/reduce/conditional_branch_to_simple_conditional_branch_opportunity_finder.cpp
@@ -73,7 +73,7 @@
result.push_back(
MakeUnique<
ConditionalBranchToSimpleConditionalBranchReductionOpportunity>(
- block.terminator(), redirect_to_true));
+ context, block.terminator(), redirect_to_true));
}
}
}
diff --git a/source/reduce/conditional_branch_to_simple_conditional_branch_reduction_opportunity.cpp b/source/reduce/conditional_branch_to_simple_conditional_branch_reduction_opportunity.cpp
index 92c621e..d744773 100644
--- a/source/reduce/conditional_branch_to_simple_conditional_branch_reduction_opportunity.cpp
+++ b/source/reduce/conditional_branch_to_simple_conditional_branch_reduction_opportunity.cpp
@@ -19,12 +19,15 @@
namespace spvtools {
namespace reduce {
+using opt::IRContext;
using opt::Instruction;
ConditionalBranchToSimpleConditionalBranchReductionOpportunity::
ConditionalBranchToSimpleConditionalBranchReductionOpportunity(
- Instruction* conditional_branch_instruction, bool redirect_to_true)
- : conditional_branch_instruction_(conditional_branch_instruction),
+ IRContext* context, Instruction* conditional_branch_instruction,
+ bool redirect_to_true)
+ : context_(context),
+ conditional_branch_instruction_(conditional_branch_instruction),
redirect_to_true_(redirect_to_true) {}
bool ConditionalBranchToSimpleConditionalBranchReductionOpportunity::
@@ -43,11 +46,24 @@
uint32_t operand_to_copy =
redirect_to_true_ ? kTrueBranchOperandIndex : kFalseBranchOperandIndex;
+ auto old_successor_block_id =
+ conditional_branch_instruction_->GetSingleWordInOperand(
+ operand_to_modify);
+
// Do the branch redirection.
conditional_branch_instruction_->SetInOperand(
operand_to_modify,
{conditional_branch_instruction_->GetSingleWordInOperand(
operand_to_copy)});
+
+ // The old successor block may have phi instructions; these will need to
+ // respect the change in edges.
+ AdaptPhiInstructionsForRemovedEdge(
+ context_->get_instr_block(conditional_branch_instruction_)->id(),
+ context_->cfg()->block(old_successor_block_id));
+
+ // We have changed the CFG.
+ context_->InvalidateAnalysesExceptFor(IRContext::Analysis::kAnalysisNone);
}
} // namespace reduce
diff --git a/source/reduce/conditional_branch_to_simple_conditional_branch_reduction_opportunity.h b/source/reduce/conditional_branch_to_simple_conditional_branch_reduction_opportunity.h
index 421906b..1f9cb6d 100644
--- a/source/reduce/conditional_branch_to_simple_conditional_branch_reduction_opportunity.h
+++ b/source/reduce/conditional_branch_to_simple_conditional_branch_reduction_opportunity.h
@@ -31,7 +31,8 @@
// to the true target; otherwise, the true target will be changed to also
// point to the false target.
explicit ConditionalBranchToSimpleConditionalBranchReductionOpportunity(
- opt::Instruction* conditional_branch_instruction, bool redirect_to_true);
+ opt::IRContext* context, opt::Instruction* conditional_branch_instruction,
+ bool redirect_to_true);
bool PreconditionHolds() override;
@@ -39,6 +40,7 @@
void Apply() override;
private:
+ opt::IRContext* context_;
opt::Instruction* conditional_branch_instruction_;
// If true, the false target will be changed to point to the true target;
diff --git a/source/reduce/reduction_util.cpp b/source/reduce/reduction_util.cpp
index 2b2b7e6..6f128dc 100644
--- a/source/reduce/reduction_util.cpp
+++ b/source/reduce/reduction_util.cpp
@@ -44,5 +44,22 @@
return undef_id;
}
+void AdaptPhiInstructionsForRemovedEdge(uint32_t from_id,
+ opt::BasicBlock* to_block) {
+ to_block->ForEachPhiInst([&from_id](Instruction* phi_inst) {
+ Instruction::OperandList new_in_operands;
+ // Go through the OpPhi's input operands in (variable, parent) pairs.
+ for (uint32_t index = 0; index < phi_inst->NumInOperands(); index += 2) {
+ // Keep all pairs where the parent is not the block from which the edge
+ // is being removed.
+ if (phi_inst->GetInOperand(index + 1).words[0] != from_id) {
+ new_in_operands.push_back(phi_inst->GetInOperand(index));
+ new_in_operands.push_back(phi_inst->GetInOperand(index + 1));
+ }
+ }
+ phi_inst->SetInOperands(std::move(new_in_operands));
+ });
+}
+
} // namespace reduce
} // namespace spvtools
diff --git a/source/reduce/reduction_util.h b/source/reduce/reduction_util.h
index b8ffb6e..7e7e153 100644
--- a/source/reduce/reduction_util.h
+++ b/source/reduce/reduction_util.h
@@ -30,6 +30,11 @@
// adding one if it does not exist.
uint32_t FindOrCreateGlobalUndef(opt::IRContext* context, uint32_t type_id);
+// Removes any components of |to_block|'s phi instructions relating to
+// |from_id|.
+void AdaptPhiInstructionsForRemovedEdge(uint32_t from_id,
+ opt::BasicBlock* to_block);
+
} // namespace reduce
} // namespace spvtools
diff --git a/source/reduce/structured_loop_to_selection_reduction_opportunity.cpp b/source/reduce/structured_loop_to_selection_reduction_opportunity.cpp
index afc1298..88ea38e 100644
--- a/source/reduce/structured_loop_to_selection_reduction_opportunity.cpp
+++ b/source/reduce/structured_loop_to_selection_reduction_opportunity.cpp
@@ -168,23 +168,6 @@
}
void StructuredLoopToSelectionReductionOpportunity::
- AdaptPhiInstructionsForRemovedEdge(uint32_t from_id, BasicBlock* to_block) {
- to_block->ForEachPhiInst([&from_id](Instruction* phi_inst) {
- Instruction::OperandList new_in_operands;
- // Go through the OpPhi's input operands in (variable, parent) pairs.
- for (uint32_t index = 0; index < phi_inst->NumInOperands(); index += 2) {
- // Keep all pairs where the parent is not the block from which the edge
- // is being removed.
- if (phi_inst->GetInOperand(index + 1).words[0] != from_id) {
- new_in_operands.push_back(phi_inst->GetInOperand(index));
- new_in_operands.push_back(phi_inst->GetInOperand(index + 1));
- }
- }
- phi_inst->SetInOperands(std::move(new_in_operands));
- });
-}
-
-void StructuredLoopToSelectionReductionOpportunity::
AdaptPhiInstructionsForAddedEdge(uint32_t from_id, BasicBlock* to_block) {
to_block->ForEachPhiInst([this, &from_id](Instruction* phi_inst) {
// Add to the phi operand an (undef, from_id) pair to reflect the added
diff --git a/source/reduce/structured_loop_to_selection_reduction_opportunity.h b/source/reduce/structured_loop_to_selection_reduction_opportunity.h
index f6c065b..564811f 100644
--- a/source/reduce/structured_loop_to_selection_reduction_opportunity.h
+++ b/source/reduce/structured_loop_to_selection_reduction_opportunity.h
@@ -62,11 +62,6 @@
void RedirectEdge(uint32_t source_id, uint32_t original_target_id,
uint32_t new_target_id);
- // Removes any components of |to_block|'s phi instructions relating to
- // |from_id|.
- void AdaptPhiInstructionsForRemovedEdge(uint32_t from_id,
- opt::BasicBlock* to_block);
-
// Adds components to |to_block|'s phi instructions to account for a new
// incoming edge from |from_id|.
void AdaptPhiInstructionsForAddedEdge(uint32_t from_id,
diff --git a/test/reduce/reducer_test.cpp b/test/reduce/reducer_test.cpp
index 189e922..a650d3b 100644
--- a/test/reduce/reducer_test.cpp
+++ b/test/reduce/reducer_test.cpp
@@ -237,6 +237,202 @@
CheckEqual(kEnv, expected, binary_out);
}
+bool InterestingWhileOpcodeExists(const std::vector<uint32_t>& binary,
+ uint32_t opcode, uint32_t count, bool dump) {
+ if (dump) {
+ std::stringstream ss;
+ ss << "temp_" << count << ".spv";
+ DumpShader(binary, ss.str().c_str());
+ }
+
+ std::unique_ptr<IRContext> context =
+ BuildModule(kEnv, kMessageConsumer, binary.data(), binary.size());
+ assert(context);
+ bool interesting = false;
+ for (auto& function : *context->module()) {
+ context->cfg()->ForEachBlockInPostOrder(
+ &*function.begin(), [opcode, &interesting](BasicBlock* block) -> void {
+ for (auto& inst : *block) {
+ if (inst.opcode() == opcode) {
+ interesting = true;
+ break;
+ }
+ }
+ });
+ if (interesting) {
+ break;
+ }
+ }
+ return interesting;
+}
+
+bool InterestingWhileIMulReachable(const std::vector<uint32_t>& binary,
+ uint32_t count) {
+ return InterestingWhileOpcodeExists(binary, SpvOpIMul, count, false);
+}
+
+bool InterestingWhileSDivReachable(const std::vector<uint32_t>& binary,
+ uint32_t count) {
+ return InterestingWhileOpcodeExists(binary, SpvOpSDiv, count, false);
+}
+
+// The shader below was derived from the following GLSL, and optimized.
+// #version 310 es
+// precision highp float;
+// layout(location = 0) out vec4 _GLF_color;
+// int foo() {
+// int x = 1;
+// int y;
+// x = y / x; // SDiv
+// return x;
+// }
+// void main() {
+// int c;
+// while (bool(c)) {
+// do {
+// if (bool(c)) {
+// if (bool(c)) {
+// ++c;
+// } else {
+// _GLF_color.x = float(c*c); // IMul
+// }
+// return;
+// }
+// } while(bool(foo()));
+// return;
+// }
+// }
+const std::string kShaderWithLoopsDivAndMul = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main" %49
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %4 "main"
+ OpName %49 "_GLF_color"
+ OpDecorate %49 Location 0
+ OpDecorate %52 RelaxedPrecision
+ OpDecorate %77 RelaxedPrecision
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeInt 32 1
+ %12 = OpConstant %6 1
+ %27 = OpTypeBool
+ %28 = OpTypeInt 32 0
+ %29 = OpConstant %28 0
+ %46 = OpTypeFloat 32
+ %47 = OpTypeVector %46 4
+ %48 = OpTypePointer Output %47
+ %49 = OpVariable %48 Output
+ %54 = OpTypePointer Output %46
+ %64 = OpConstantFalse %27
+ %67 = OpConstantTrue %27
+ %81 = OpUndef %6
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ OpBranch %61
+ %61 = OpLabel
+ OpLoopMerge %60 %63 None
+ OpBranch %20
+ %20 = OpLabel
+ %30 = OpINotEqual %27 %81 %29
+ OpLoopMerge %22 %23 None
+ OpBranchConditional %30 %21 %22
+ %21 = OpLabel
+ OpBranch %31
+ %31 = OpLabel
+ OpLoopMerge %33 %38 None
+ OpBranch %32
+ %32 = OpLabel
+ OpSelectionMerge %38 None
+ OpBranchConditional %30 %37 %38
+ %37 = OpLabel
+ OpSelectionMerge %42 None
+ OpBranchConditional %30 %41 %45
+ %41 = OpLabel
+ OpBranch %42
+ %45 = OpLabel
+ %52 = OpIMul %6 %81 %81
+ %53 = OpConvertSToF %46 %52
+ %55 = OpAccessChain %54 %49 %29
+ OpStore %55 %53
+ OpBranch %42
+ %42 = OpLabel
+ OpBranch %33
+ %38 = OpLabel
+ %77 = OpSDiv %6 %81 %12
+ %58 = OpINotEqual %27 %77 %29
+ OpBranchConditional %58 %31 %33
+ %33 = OpLabel
+ %86 = OpPhi %27 %67 %42 %64 %38
+ OpSelectionMerge %68 None
+ OpBranchConditional %86 %22 %68
+ %68 = OpLabel
+ OpBranch %22
+ %23 = OpLabel
+ OpBranch %20
+ %22 = OpLabel
+ %90 = OpPhi %27 %64 %20 %86 %33 %67 %68
+ OpSelectionMerge %70 None
+ OpBranchConditional %90 %60 %70
+ %70 = OpLabel
+ OpBranch %60
+ %63 = OpLabel
+ OpBranch %61
+ %60 = OpLabel
+ OpReturn
+ OpFunctionEnd
+ )";
+
+TEST(ReducerTest, ShaderReduceWhileMulReachable) {
+ Reducer reducer(kEnv);
+
+ reducer.SetInterestingnessFunction(InterestingWhileIMulReachable);
+ reducer.AddDefaultReductionPasses();
+ reducer.SetMessageConsumer(kMessageConsumer);
+
+ std::vector<uint32_t> binary_in;
+ SpirvTools t(kEnv);
+
+ ASSERT_TRUE(
+ t.Assemble(kShaderWithLoopsDivAndMul, &binary_in, kReduceAssembleOption));
+ std::vector<uint32_t> binary_out;
+ spvtools::ReducerOptions reducer_options;
+ reducer_options.set_step_limit(500);
+ reducer_options.set_fail_on_validation_error(true);
+ spvtools::ValidatorOptions validator_options;
+
+ Reducer::ReductionResultStatus status = reducer.Run(
+ std::move(binary_in), &binary_out, reducer_options, validator_options);
+
+ ASSERT_EQ(status, Reducer::ReductionResultStatus::kComplete);
+}
+
+TEST(ReducerTest, ShaderReduceWhileDivReachable) {
+ Reducer reducer(kEnv);
+
+ reducer.SetInterestingnessFunction(InterestingWhileSDivReachable);
+ reducer.AddDefaultReductionPasses();
+ reducer.SetMessageConsumer(kMessageConsumer);
+
+ std::vector<uint32_t> binary_in;
+ SpirvTools t(kEnv);
+
+ ASSERT_TRUE(
+ t.Assemble(kShaderWithLoopsDivAndMul, &binary_in, kReduceAssembleOption));
+ std::vector<uint32_t> binary_out;
+ spvtools::ReducerOptions reducer_options;
+ reducer_options.set_step_limit(500);
+ reducer_options.set_fail_on_validation_error(true);
+ spvtools::ValidatorOptions validator_options;
+
+ Reducer::ReductionResultStatus status = reducer.Run(
+ std::move(binary_in), &binary_out, reducer_options, validator_options);
+
+ ASSERT_EQ(status, Reducer::ReductionResultStatus::kComplete);
+}
+
} // namespace
} // namespace reduce
} // namespace spvtools
