spirv-reduce: add OperandToUndefReductionPass (#2200)
* Add OperandToUndefReductionPass.
Fixes #2115.
Also added some tests that are similar to those in OperandToConstantReductionPassTest.
In addition, refactor FindOrCreateGlobalUndef into reduction_util.cpp. Fixes #2184.
Removed many documentation comments that were identical or very similar to the overridden function's documentation comment.
diff --git a/source/reduce/CMakeLists.txt b/source/reduce/CMakeLists.txt
index 57475ac..0a6bce9 100644
--- a/source/reduce/CMakeLists.txt
+++ b/source/reduce/CMakeLists.txt
@@ -13,11 +13,14 @@
# limitations under the License.
set(SPIRV_TOOLS_REDUCE_SOURCES
change_operand_reduction_opportunity.h
+ change_operand_to_undef_reduction_opportunity.h
operand_to_const_reduction_pass.h
+ operand_to_undef_reduction_pass.h
operand_to_dominating_id_reduction_pass.h
reducer.h
reduction_opportunity.h
reduction_pass.h
+ reduction_util.h
remove_instruction_reduction_opportunity.h
remove_opname_instruction_reduction_pass.h
remove_unreferenced_instruction_reduction_pass.h
@@ -25,11 +28,14 @@
structured_loop_to_selection_reduction_pass.h
change_operand_reduction_opportunity.cpp
+ change_operand_to_undef_reduction_opportunity.cpp
operand_to_const_reduction_pass.cpp
+ operand_to_undef_reduction_pass.cpp
operand_to_dominating_id_reduction_pass.cpp
reducer.cpp
reduction_opportunity.cpp
reduction_pass.cpp
+ reduction_util.cpp
remove_instruction_reduction_opportunity.cpp
remove_unreferenced_instruction_reduction_pass.cpp
remove_opname_instruction_reduction_pass.cpp
diff --git a/source/reduce/change_operand_reduction_opportunity.h b/source/reduce/change_operand_reduction_opportunity.h
index 9e43ec9..7e1fc8e 100644
--- a/source/reduce/change_operand_reduction_opportunity.h
+++ b/source/reduce/change_operand_reduction_opportunity.h
@@ -24,8 +24,7 @@
using namespace opt;
-// Captures the opportunity to change an id operand of an instruction to some
-// other id.
+// An opportunity to replace an id operand of an instruction with some other id.
class ChangeOperandReductionOpportunity : public ReductionOpportunity {
public:
// Constructs the opportunity to replace operand |operand_index| of |inst|
@@ -38,13 +37,9 @@
original_type_(inst->GetOperand(operand_index).type),
new_id_(new_id) {}
- // Determines whether the opportunity can be applied; it may have been viable
- // when discovered but later disabled by the application of some other
- // reduction opportunity.
bool PreconditionHolds() override;
protected:
- // Apply the change of operand.
void Apply() override;
private:
diff --git a/source/reduce/change_operand_to_undef_reduction_opportunity.cpp b/source/reduce/change_operand_to_undef_reduction_opportunity.cpp
new file mode 100644
index 0000000..8e33da6
--- /dev/null
+++ b/source/reduce/change_operand_to_undef_reduction_opportunity.cpp
@@ -0,0 +1,41 @@
+// Copyright (c) 2018 Google LLC
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "source/reduce/change_operand_to_undef_reduction_opportunity.h"
+
+#include "source/opt/ir_context.h"
+#include "source/reduce/reduction_util.h"
+
+namespace spvtools {
+namespace reduce {
+
+bool ChangeOperandToUndefReductionOpportunity::PreconditionHolds() {
+ // Check that the instruction still has the original operand.
+ return inst_->NumOperands() > operand_index_ &&
+ inst_->GetOperand(operand_index_).words[0] == original_id_;
+}
+
+void ChangeOperandToUndefReductionOpportunity::Apply() {
+ auto operand = inst_->GetOperand(operand_index_);
+ auto operand_id = operand.words[0];
+ auto operand_id_def = context_->get_def_use_mgr()->GetDef(operand_id);
+ auto operand_type_id = operand_id_def->type_id();
+ // The opportunity should not exist unless this holds.
+ assert(operand_type_id);
+ auto undef_id = FindOrCreateGlobalUndef(context_, operand_type_id);
+ inst_->SetOperand(operand_index_, {undef_id});
+}
+
+} // namespace reduce
+} // namespace spvtools
diff --git a/source/reduce/change_operand_to_undef_reduction_opportunity.h b/source/reduce/change_operand_to_undef_reduction_opportunity.h
new file mode 100644
index 0000000..ffd3155
--- /dev/null
+++ b/source/reduce/change_operand_to_undef_reduction_opportunity.h
@@ -0,0 +1,53 @@
+// Copyright (c) 2018 Google LLC
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#ifndef SOURCE_REDUCE_CHANGE_OPERAND_TO_UNDEF_REDUCTION_OPPORTUNITY_H_
+#define SOURCE_REDUCE_CHANGE_OPERAND_TO_UNDEF_REDUCTION_OPPORTUNITY_H_
+
+#include "source/opt/instruction.h"
+#include "source/reduce/reduction_opportunity.h"
+#include "spirv-tools/libspirv.h"
+
+namespace spvtools {
+namespace reduce {
+
+// An opportunity to replace an id operand of an instruction with undef.
+class ChangeOperandToUndefReductionOpportunity : public ReductionOpportunity {
+ public:
+ // Constructs the opportunity to replace operand |operand_index| of |inst|
+ // with undef.
+ ChangeOperandToUndefReductionOpportunity(opt::IRContext* context,
+ opt::Instruction* inst,
+ uint32_t operand_index)
+ : context_(context),
+ inst_(inst),
+ operand_index_(operand_index),
+ original_id_(inst->GetOperand(operand_index).words[0]) {}
+
+ bool PreconditionHolds() override;
+
+ protected:
+ void Apply() override;
+
+ private:
+ opt::IRContext* context_;
+ opt::Instruction* const inst_;
+ const uint32_t operand_index_;
+ const uint32_t original_id_;
+};
+
+} // namespace reduce
+} // namespace spvtools
+
+#endif // SOURCE_REDUCE_CHANGE_OPERAND_TO_UNDEF_REDUCTION_OPPORTUNITY_H_
diff --git a/source/reduce/operand_to_const_reduction_pass.cpp b/source/reduce/operand_to_const_reduction_pass.cpp
index 35c0f4b..4d04506 100644
--- a/source/reduce/operand_to_const_reduction_pass.cpp
+++ b/source/reduce/operand_to_const_reduction_pass.cpp
@@ -12,9 +12,10 @@
// See the License for the specific language governing permissions and
// limitations under the License.
-#include "operand_to_const_reduction_pass.h"
-#include "change_operand_reduction_opportunity.h"
+#include "source/reduce/operand_to_const_reduction_pass.h"
+
#include "source/opt/instruction.h"
+#include "source/reduce/change_operand_reduction_opportunity.h"
namespace spvtools {
namespace reduce {
diff --git a/source/reduce/operand_to_const_reduction_pass.h b/source/reduce/operand_to_const_reduction_pass.h
index fd7cfa0..4e7381e 100644
--- a/source/reduce/operand_to_const_reduction_pass.h
+++ b/source/reduce/operand_to_const_reduction_pass.h
@@ -15,12 +15,12 @@
#ifndef SOURCE_REDUCE_OPERAND_TO_CONST_REDUCTION_PASS_H_
#define SOURCE_REDUCE_OPERAND_TO_CONST_REDUCTION_PASS_H_
-#include "reduction_pass.h"
+#include "source/reduce/reduction_pass.h"
namespace spvtools {
namespace reduce {
-// A reduction pass for turning id operands of instructions into ids of
+// A reduction pass for replacing id operands of instructions with ids of
// constants. This reduces the extent to which ids of non-constants are used,
// paving the way for instructions that generate them to be eliminated by other
// passes.
@@ -33,12 +33,9 @@
~OperandToConstReductionPass() override = default;
- // The name of this pass.
std::string GetName() const final;
protected:
- // Finds all opportunities for replacing an operand with a constant in the
- // given module.
std::vector<std::unique_ptr<ReductionOpportunity>> GetAvailableOpportunities(
opt::IRContext* context) const final;
diff --git a/source/reduce/operand_to_dominating_id_reduction_pass.h b/source/reduce/operand_to_dominating_id_reduction_pass.h
index b62b6ae..36bb201 100644
--- a/source/reduce/operand_to_dominating_id_reduction_pass.h
+++ b/source/reduce/operand_to_dominating_id_reduction_pass.h
@@ -39,12 +39,9 @@
~OperandToDominatingIdReductionPass() override = default;
- // The name of this pass.
std::string GetName() const final;
protected:
- // Finds all opportunities for replacing an operand with a dominating
- // instruction in a given module.
std::vector<std::unique_ptr<ReductionOpportunity>> GetAvailableOpportunities(
opt::IRContext* context) const final;
diff --git a/source/reduce/operand_to_undef_reduction_pass.cpp b/source/reduce/operand_to_undef_reduction_pass.cpp
new file mode 100644
index 0000000..e3d8a8e
--- /dev/null
+++ b/source/reduce/operand_to_undef_reduction_pass.cpp
@@ -0,0 +1,94 @@
+// Copyright (c) 2018 Google LLC
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "source/reduce/operand_to_undef_reduction_pass.h"
+
+#include "source/opt/instruction.h"
+#include "source/reduce/change_operand_to_undef_reduction_opportunity.h"
+
+namespace spvtools {
+namespace reduce {
+
+using namespace opt;
+
+std::vector<std::unique_ptr<ReductionOpportunity>>
+OperandToUndefReductionPass::GetAvailableOpportunities(
+ IRContext* context) const {
+ std::vector<std::unique_ptr<ReductionOpportunity>> result;
+
+ for (auto& function : *context->module()) {
+ for (auto& block : function) {
+ for (auto& inst : block) {
+ // Skip instructions that result in a pointer type.
+ auto type_id = inst.type_id();
+ if (type_id) {
+ auto type_id_def = context->get_def_use_mgr()->GetDef(type_id);
+ if (type_id_def->opcode() == SpvOpTypePointer) {
+ continue;
+ }
+ }
+
+ // We iterate through the operands using an explicit index (rather
+ // than using a lambda) so that we use said index in the construction
+ // of a ChangeOperandToUndefReductionOpportunity
+ for (uint32_t index = 0; index < inst.NumOperands(); index++) {
+ const auto& operand = inst.GetOperand(index);
+
+ if (spvIsInIdType(operand.type)) {
+ const auto operand_id = operand.words[0];
+ auto operand_id_def =
+ context->get_def_use_mgr()->GetDef(operand_id);
+
+ // Skip constant and undef operands.
+ // We always want the reducer to make the module "smaller", which
+ // ensures termination.
+ // Therefore, we assume: id > undef id > constant id.
+ if (spvOpcodeIsConstantOrUndef(operand_id_def->opcode())) {
+ continue;
+ }
+
+ // Don't replace function operands with undef.
+ if (operand_id_def->opcode() == SpvOpFunction) {
+ continue;
+ }
+
+ // Only consider operands that have a type.
+ auto operand_type_id = operand_id_def->type_id();
+ if (operand_type_id) {
+ auto operand_type_id_def =
+ context->get_def_use_mgr()->GetDef(operand_type_id);
+
+ // Skip pointer operands.
+ if (operand_type_id_def->opcode() == SpvOpTypePointer) {
+ continue;
+ }
+
+ result.push_back(
+ MakeUnique<ChangeOperandToUndefReductionOpportunity>(
+ context, &inst, index));
+ }
+ }
+ }
+ }
+ }
+ }
+ return result;
+}
+
+std::string OperandToUndefReductionPass::GetName() const {
+ return "OperandToUndefReductionPass";
+}
+
+} // namespace reduce
+} // namespace spvtools
diff --git a/source/reduce/operand_to_undef_reduction_pass.h b/source/reduce/operand_to_undef_reduction_pass.h
new file mode 100644
index 0000000..e4ec603
--- /dev/null
+++ b/source/reduce/operand_to_undef_reduction_pass.h
@@ -0,0 +1,45 @@
+// Copyright (c) 2018 Google LLC
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#ifndef SOURCE_REDUCE_OPERAND_TO_UNDEF_REDUCTION_PASS_H_
+#define SOURCE_REDUCE_OPERAND_TO_UNDEF_REDUCTION_PASS_H_
+
+#include "source/reduce/reduction_pass.h"
+
+namespace spvtools {
+namespace reduce {
+
+// A reduction pass for replacing id operands of instructions with ids of undef.
+class OperandToUndefReductionPass : public ReductionPass {
+ public:
+ // Creates the reduction pass in the context of the given target environment
+ // |target_env|
+ explicit OperandToUndefReductionPass(const spv_target_env target_env)
+ : ReductionPass(target_env) {}
+
+ ~OperandToUndefReductionPass() override = default;
+
+ std::string GetName() const final;
+
+ protected:
+ std::vector<std::unique_ptr<ReductionOpportunity>> GetAvailableOpportunities(
+ opt::IRContext* context) const final;
+
+ private:
+};
+
+} // namespace reduce
+} // namespace spvtools
+
+#endif // SOURCE_REDUCE_OPERAND_TO_UNDEF_REDUCTION_PASS_H_
diff --git a/source/reduce/reduction_opportunity.h b/source/reduce/reduction_opportunity.h
index da382a2..703a50a 100644
--- a/source/reduce/reduction_opportunity.h
+++ b/source/reduce/reduction_opportunity.h
@@ -20,23 +20,24 @@
namespace spvtools {
namespace reduce {
-// Abstract class capturing an opportunity to apply a reducing transformation.
+// Abstract class: an opportunity to apply a reducing transformation.
class ReductionOpportunity {
public:
ReductionOpportunity() = default;
virtual ~ReductionOpportunity() = default;
- // Determines whether the opportunity can be applied; it may have been viable
- // when discovered but later disabled by the application of some other
- // reduction opportunity.
+ // Returns true if this opportunity has not been disabled by the application
+ // of another conflicting opportunity.
virtual bool PreconditionHolds() = 0;
- // A no-op if PreconditoinHolds() returns false; otherwise applies the
- // opportunity.
+ // Applies the opportunity, mutating the module from which the opportunity was
+ // created. It is a no-op if PreconditionHolds() returns false.
void TryToApply();
protected:
- // Apply the reduction opportunity.
+ // Applies the opportunity, mutating the module from which the opportunity was
+ // created.
+ // Precondition: PreconditionHolds() must return true.
virtual void Apply() = 0;
};
diff --git a/source/reduce/reduction_pass.h b/source/reduce/reduction_pass.h
index afb95cc..57e1c5f 100644
--- a/source/reduce/reduction_pass.h
+++ b/source/reduce/reduction_pass.h
@@ -39,13 +39,13 @@
virtual ~ReductionPass() = default;
- // Apply the reduction pass to the given binary.
+ // Applies the reduction pass to the given binary.
std::vector<uint32_t> TryApplyReduction(const std::vector<uint32_t>& binary);
- // Set a consumer to which relevant messages will be directed.
+ // Sets a consumer to which relevant messages will be directed.
void SetMessageConsumer(MessageConsumer consumer);
- // Determines whether the granularity with which reduction opportunities are
+ // Returns true if the granularity with which reduction opportunities are
// applied has reached a minimum.
bool ReachedMinimumGranularity() const;
@@ -54,8 +54,8 @@
virtual std::string GetName() const = 0;
protected:
- // Finds the reduction opportunities relevant to this pass that could be
- // applied to a given SPIR-V module.
+ // Finds and returns the reduction opportunities relevant to this pass that
+ // could be applied to the given SPIR-V module.
virtual std::vector<std::unique_ptr<ReductionOpportunity>>
GetAvailableOpportunities(opt::IRContext* context) const = 0;
diff --git a/source/reduce/reduction_util.cpp b/source/reduce/reduction_util.cpp
new file mode 100644
index 0000000..103d63f
--- /dev/null
+++ b/source/reduce/reduction_util.cpp
@@ -0,0 +1,44 @@
+// Copyright (c) 2018 Google LLC
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "source/reduce/reduction_util.h"
+
+#include "source/opt/ir_context.h"
+
+namespace spvtools {
+namespace reduce {
+
+using namespace opt;
+
+uint32_t FindOrCreateGlobalUndef(IRContext* context, uint32_t type_id) {
+ for (auto& inst : context->module()->types_values()) {
+ if (inst.opcode() != SpvOpUndef) {
+ continue;
+ }
+ if (inst.type_id() == type_id) {
+ return inst.result_id();
+ }
+ }
+ // TODO(2182): this is adapted from MemPass::Type2Undef. In due course it
+ // would be good to factor out this duplication.
+ const uint32_t undef_id = context->TakeNextId();
+ std::unique_ptr<Instruction> undef_inst(
+ new Instruction(context, SpvOpUndef, type_id, undef_id, {}));
+ assert(undef_id == undef_inst->result_id());
+ context->module()->AddGlobalValue(std::move(undef_inst));
+ return undef_id;
+}
+
+} // namespace reduce
+} // namespace spvtools
diff --git a/source/reduce/reduction_util.h b/source/reduce/reduction_util.h
new file mode 100644
index 0000000..d8efc97
--- /dev/null
+++ b/source/reduce/reduction_util.h
@@ -0,0 +1,33 @@
+// Copyright (c) 2018 Google LLC
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#ifndef SOURCE_REDUCE_REDUCTION_UTIL_H_
+#define SOURCE_REDUCE_REDUCTION_UTIL_H_
+
+#include "spirv-tools/libspirv.hpp"
+
+#include "source/opt/ir_context.h"
+#include "source/reduce/reduction_opportunity.h"
+
+namespace spvtools {
+namespace reduce {
+
+// Returns an OpUndef id from the global value list that is of the given type,
+// adding one if it does not exist.
+uint32_t FindOrCreateGlobalUndef(opt::IRContext* context, uint32_t type_id);
+
+} // namespace reduce
+} // namespace spvtools
+
+#endif // SOURCE_REDUCE_REDUCTION_UTIL_H_
diff --git a/source/reduce/remove_instruction_reduction_opportunity.h b/source/reduce/remove_instruction_reduction_opportunity.h
index 471ff15..e9f442e 100644
--- a/source/reduce/remove_instruction_reduction_opportunity.h
+++ b/source/reduce/remove_instruction_reduction_opportunity.h
@@ -23,18 +23,17 @@
using namespace opt;
-// Captures the opportunity to remove an instruction from the SPIR-V module.
+// An opportunity to remove an instruction from the SPIR-V module.
class RemoveInstructionReductionOpportunity : public ReductionOpportunity {
public:
// Constructs the opportunity to remove |inst|.
explicit RemoveInstructionReductionOpportunity(Instruction* inst)
: inst_(inst) {}
- // This kind of opportunity can be unconditionally applied.
+ // Always returns true, as this opportunity can always be applied.
bool PreconditionHolds() override;
protected:
- // Remove the instruction.
void Apply() override;
private:
diff --git a/source/reduce/remove_opname_instruction_reduction_pass.h b/source/reduce/remove_opname_instruction_reduction_pass.h
index d20b6e1..2990a49 100644
--- a/source/reduce/remove_opname_instruction_reduction_pass.h
+++ b/source/reduce/remove_opname_instruction_reduction_pass.h
@@ -21,8 +21,9 @@
namespace reduce {
// A reduction pass for removing OpName instructions. As well as making the
-// module smaller, removing an OpName instruction may create opportunities to
-// remove the instruction that create the id to which the OpName applies.
+// module smaller, removing an OpName instruction may create opportunities
+// for subsequently removing the instructions that create the ids to which the
+// OpName applies.
class RemoveOpNameInstructionReductionPass : public ReductionPass {
public:
// Creates the reduction pass in the context of the given target environment
@@ -32,12 +33,9 @@
~RemoveOpNameInstructionReductionPass() override = default;
- // The name of this pass.
std::string GetName() const final;
protected:
- // Finds all opportunities for removing opName instructions in the
- // given module.
std::vector<std::unique_ptr<ReductionOpportunity>> GetAvailableOpportunities(
opt::IRContext* context) const final;
diff --git a/source/reduce/remove_unreferenced_instruction_reduction_pass.h b/source/reduce/remove_unreferenced_instruction_reduction_pass.h
index 27c3fc2..44a0d55 100644
--- a/source/reduce/remove_unreferenced_instruction_reduction_pass.h
+++ b/source/reduce/remove_unreferenced_instruction_reduction_pass.h
@@ -22,7 +22,7 @@
// A reduction pass for removing non-control-flow instructions in blocks in
// cases where the instruction's id is not referenced. As well as making the
-// module smaller, removing an instruction that referenced particular ids may
+// module smaller, removing an instruction that references particular ids may
// create opportunities for subsequently removing the instructions that
// generated those ids.
class RemoveUnreferencedInstructionReductionPass : public ReductionPass {
@@ -35,12 +35,9 @@
~RemoveUnreferencedInstructionReductionPass() override = default;
- // The name of this pass.
std::string GetName() const final;
protected:
- // Finds all opportunities for removing unreferenced instructions in the
- // given module.
std::vector<std::unique_ptr<ReductionOpportunity>> GetAvailableOpportunities(
opt::IRContext* context) const final;
diff --git a/source/reduce/structured_loop_to_selection_reduction_opportunity.cpp b/source/reduce/structured_loop_to_selection_reduction_opportunity.cpp
index 679cfc1..bf0e085 100644
--- a/source/reduce/structured_loop_to_selection_reduction_opportunity.cpp
+++ b/source/reduce/structured_loop_to_selection_reduction_opportunity.cpp
@@ -12,9 +12,11 @@
// See the License for the specific language governing permissions and
// limitations under the License.
-#include "structured_loop_to_selection_reduction_opportunity.h"
+#include "source/reduce/structured_loop_to_selection_reduction_opportunity.h"
+
#include "source/opt/aggressive_dead_code_elim_pass.h"
#include "source/opt/ir_context.h"
+#include "source/reduce/reduction_util.h"
namespace spvtools {
namespace reduce {
@@ -191,7 +193,7 @@
to_block->ForEachPhiInst([this, &from_id](Instruction* phi_inst) {
// Add to the phi operand an (undef, from_id) pair to reflect the added
// edge.
- auto undef_id = FindOrCreateGlobalUndef(phi_inst->type_id());
+ auto undef_id = FindOrCreateGlobalUndef(context_, phi_inst->type_id());
phi_inst->AddOperand(Operand(SPV_OPERAND_TYPE_ID, {undef_id}));
phi_inst->AddOperand(Operand(SPV_OPERAND_TYPE_ID, {from_id}));
});
@@ -273,7 +275,8 @@
break;
}
} else {
- use->SetOperand(index, {FindOrCreateGlobalUndef(def.type_id())});
+ use->SetOperand(index,
+ {FindOrCreateGlobalUndef(context_, def.type_id())});
}
}
});
@@ -296,26 +299,6 @@
->Dominates(def, use);
}
-uint32_t StructuredLoopToSelectionReductionOpportunity::FindOrCreateGlobalUndef(
- uint32_t type_id) {
- for (auto& inst : context_->module()->types_values()) {
- if (inst.opcode() != SpvOpUndef) {
- continue;
- }
- if (inst.type_id() == type_id) {
- return inst.result_id();
- }
- }
- // TODO(2182): this is adapted from MemPass::Type2Undef. In due course it
- // would be good to factor out this duplication.
- const uint32_t undef_id = context_->TakeNextId();
- std::unique_ptr<Instruction> undef_inst(
- new Instruction(context_, SpvOpUndef, type_id, undef_id, {}));
- assert(undef_id == undef_inst->result_id());
- context_->module()->AddGlobalValue(std::move(undef_inst));
- return undef_id;
-}
-
uint32_t
StructuredLoopToSelectionReductionOpportunity::FindOrCreateGlobalVariable(
uint32_t pointer_type_id) {
diff --git a/source/reduce/structured_loop_to_selection_reduction_opportunity.h b/source/reduce/structured_loop_to_selection_reduction_opportunity.h
index b139016..71b0f0e 100644
--- a/source/reduce/structured_loop_to_selection_reduction_opportunity.h
+++ b/source/reduce/structured_loop_to_selection_reduction_opportunity.h
@@ -15,17 +15,17 @@
#ifndef SOURCE_REDUCE_CUT_LOOP_REDUCTION_OPPORTUNITY_H_
#define SOURCE_REDUCE_CUT_LOOP_REDUCTION_OPPORTUNITY_H_
-#include <source/opt/def_use_manager.h>
-#include "reduction_opportunity.h"
+#include "source/opt/def_use_manager.h"
#include "source/opt/dominator_analysis.h"
#include "source/opt/function.h"
+#include "source/reduce/reduction_opportunity.h"
namespace spvtools {
namespace reduce {
using namespace opt;
-// Captures an opportunity to replace a structured loop with a selection.
+// An opportunity to replace a structured loop with a selection.
class StructuredLoopToSelectionReductionOpportunity
: public ReductionOpportunity {
public:
@@ -38,13 +38,12 @@
loop_construct_header_(loop_construct_header),
enclosing_function_(enclosing_function) {}
- // We require the loop header to be reachable. A structured loop might
+ // Returns true if the loop header is reachable. A structured loop might
// become unreachable as a result of turning another structured loop into
// a selection.
bool PreconditionHolds() override;
protected:
- // Perform the structured loop to selection transformation.
void Apply() override;
private:
@@ -92,14 +91,6 @@
uint32_t use_index,
BasicBlock& def_block);
- // Checks whether the global value list has an OpUndef of the given type,
- // adding one if not, and returns the id of such an OpUndef.
- //
- // TODO(2184): This will likely be used by other reduction passes, so should
- // be factored out in due course. Parts of the spirv-opt framework provide
- // similar functionality, so there may be a case for further refactoring.
- uint32_t FindOrCreateGlobalUndef(uint32_t type_id);
-
// Checks whether the global value list has an OpVariable of the given pointer
// type, adding one if not, and returns the id of such an OpVariable.
//
diff --git a/source/reduce/structured_loop_to_selection_reduction_pass.h b/source/reduce/structured_loop_to_selection_reduction_pass.h
index 9c4d4ca..a1f88bc 100644
--- a/source/reduce/structured_loop_to_selection_reduction_pass.h
+++ b/source/reduce/structured_loop_to_selection_reduction_pass.h
@@ -46,12 +46,9 @@
~StructuredLoopToSelectionReductionPass() override = default;
- // The name of this pass.
std::string GetName() const final;
protected:
- // Finds all opportunities for transforming a structured loop to a selection
- // in the given module.
std::vector<std::unique_ptr<ReductionOpportunity>> GetAvailableOpportunities(
opt::IRContext* context) const final;
diff --git a/test/reduce/CMakeLists.txt b/test/reduce/CMakeLists.txt
index cdd27b9..b35cdb2 100644
--- a/test/reduce/CMakeLists.txt
+++ b/test/reduce/CMakeLists.txt
@@ -14,6 +14,7 @@
add_spvtools_unittest(TARGET reduce
SRCS operand_to_constant_reduction_pass_test.cpp
+ operand_to_undef_reduction_pass_test.cpp
operand_to_dominating_id_reduction_pass_test.cpp
reduce_test_util.cpp
reduce_test_util.h
diff --git a/test/reduce/operand_to_undef_reduction_pass_test.cpp b/test/reduce/operand_to_undef_reduction_pass_test.cpp
new file mode 100644
index 0000000..71bf96c
--- /dev/null
+++ b/test/reduce/operand_to_undef_reduction_pass_test.cpp
@@ -0,0 +1,226 @@
+// Copyright (c) 2018 Google LLC
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "source/reduce/operand_to_undef_reduction_pass.h"
+#include "source/opt/build_module.h"
+#include "test/reduce/reduce_test_util.h"
+
+namespace spvtools {
+namespace reduce {
+namespace {
+
+TEST(OperandToUndefReductionPassTest, BasicCheck) {
+ // The following shader has 10 opportunities for replacing with undef.
+
+ // #version 310 es
+ //
+ // precision highp float;
+ //
+ // layout(location=0) out vec4 _GLF_color;
+ //
+ // layout(set = 0, binding = 0) uniform buf0 {
+ // vec2 uniform1;
+ // };
+ //
+ // void main()
+ // {
+ // _GLF_color =
+ // vec4( // opportunity
+ // uniform1.x / 2.0, // opportunity x2 (2.0 is const)
+ // uniform1.y / uniform1.x, // opportunity x3
+ // uniform1.x + uniform1.x, // opportunity x3
+ // uniform1.y); // opportunity
+ // }
+
+ std::string original = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main" %9
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %4 "main"
+ OpName %9 "_GLF_color"
+ OpName %11 "buf0"
+ OpMemberName %11 0 "uniform1"
+ OpName %13 ""
+ OpDecorate %9 Location 0
+ OpMemberDecorate %11 0 Offset 0
+ OpDecorate %11 Block
+ OpDecorate %13 DescriptorSet 0
+ OpDecorate %13 Binding 0
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeFloat 32
+ %7 = OpTypeVector %6 4
+ %8 = OpTypePointer Output %7
+ %9 = OpVariable %8 Output
+ %10 = OpTypeVector %6 2
+ %11 = OpTypeStruct %10
+ %12 = OpTypePointer Uniform %11
+ %13 = OpVariable %12 Uniform
+ %14 = OpTypeInt 32 1
+ %15 = OpConstant %14 0
+ %16 = OpTypeInt 32 0
+ %17 = OpConstant %16 0
+ %18 = OpTypePointer Uniform %6
+ %21 = OpConstant %6 2
+ %23 = OpConstant %16 1
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %19 = OpAccessChain %18 %13 %15 %17
+ %20 = OpLoad %6 %19
+ %22 = OpFDiv %6 %20 %21 ; opportunity %20 (%21 is const)
+ %24 = OpAccessChain %18 %13 %15 %23
+ %25 = OpLoad %6 %24
+ %26 = OpAccessChain %18 %13 %15 %17
+ %27 = OpLoad %6 %26
+ %28 = OpFDiv %6 %25 %27 ; opportunity %25 %27
+ %29 = OpAccessChain %18 %13 %15 %17
+ %30 = OpLoad %6 %29
+ %31 = OpAccessChain %18 %13 %15 %17
+ %32 = OpLoad %6 %31
+ %33 = OpFAdd %6 %30 %32 ; opportunity %30 %32
+ %34 = OpAccessChain %18 %13 %15 %23
+ %35 = OpLoad %6 %34
+ %36 = OpCompositeConstruct %7 %22 %28 %33 %35 ; opportunity %22 %28 %33 %35
+ OpStore %9 %36 ; opportunity %36
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ // This is the same as original, except where noted.
+ std::string expected = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main" %9
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ OpName %4 "main"
+ OpName %9 "_GLF_color"
+ OpName %11 "buf0"
+ OpMemberName %11 0 "uniform1"
+ OpName %13 ""
+ OpDecorate %9 Location 0
+ OpMemberDecorate %11 0 Offset 0
+ OpDecorate %11 Block
+ OpDecorate %13 DescriptorSet 0
+ OpDecorate %13 Binding 0
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeFloat 32
+ %7 = OpTypeVector %6 4
+ %8 = OpTypePointer Output %7
+ %9 = OpVariable %8 Output
+ %10 = OpTypeVector %6 2
+ %11 = OpTypeStruct %10
+ %12 = OpTypePointer Uniform %11
+ %13 = OpVariable %12 Uniform
+ %14 = OpTypeInt 32 1
+ %15 = OpConstant %14 0
+ %16 = OpTypeInt 32 0
+ %17 = OpConstant %16 0
+ %18 = OpTypePointer Uniform %6
+ %21 = OpConstant %6 2
+ %23 = OpConstant %16 1
+ %37 = OpUndef %6 ; Added undef float as %37
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %19 = OpAccessChain %18 %13 %15 %17
+ %20 = OpLoad %6 %19
+ %22 = OpFDiv %6 %37 %21 ; Replaced with %37
+ %24 = OpAccessChain %18 %13 %15 %23
+ %25 = OpLoad %6 %24
+ %26 = OpAccessChain %18 %13 %15 %17
+ %27 = OpLoad %6 %26
+ %28 = OpFDiv %6 %37 %37 ; Replaced with %37 twice
+ %29 = OpAccessChain %18 %13 %15 %17
+ %30 = OpLoad %6 %29
+ %31 = OpAccessChain %18 %13 %15 %17
+ %32 = OpLoad %6 %31
+ %33 = OpFAdd %6 %30 %32
+ %34 = OpAccessChain %18 %13 %15 %23
+ %35 = OpLoad %6 %34
+ %36 = OpCompositeConstruct %7 %22 %28 %33 %35
+ OpStore %9 %36
+ OpReturn
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_3;
+ const auto consumer = nullptr;
+ const auto context =
+ BuildModule(env, consumer, original, kReduceAssembleOption);
+ const auto pass = TestSubclass<OperandToUndefReductionPass>(env);
+ const auto ops = pass.WrapGetAvailableOpportunities(context.get());
+
+ ASSERT_EQ(10, ops.size());
+
+ // Apply first three opportunities.
+ ASSERT_TRUE(ops[0]->PreconditionHolds());
+ ops[0]->TryToApply();
+ ASSERT_TRUE(ops[1]->PreconditionHolds());
+ ops[1]->TryToApply();
+ ASSERT_TRUE(ops[2]->PreconditionHolds());
+ ops[2]->TryToApply();
+
+ CheckEqual(env, expected, context.get());
+}
+
+TEST(OperandToUndefReductionPassTest, WithCalledFunction) {
+ // The following shader has no opportunities.
+ // Most importantly, the noted function operand is not changed.
+
+ std::string shader = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %4 "main" %10 %12
+ OpExecutionMode %4 OriginUpperLeft
+ OpSource ESSL 310
+ %2 = OpTypeVoid
+ %3 = OpTypeFunction %2
+ %6 = OpTypeFloat 32
+ %7 = OpTypeVector %6 4
+ %8 = OpTypeFunction %7
+ %9 = OpTypePointer Output %7
+ %10 = OpVariable %9 Output
+ %11 = OpTypePointer Input %7
+ %12 = OpVariable %11 Input
+ %13 = OpConstant %6 0
+ %14 = OpConstantComposite %7 %13 %13 %13 %13
+ %4 = OpFunction %2 None %3
+ %5 = OpLabel
+ %15 = OpFunctionCall %7 %16 ; do not replace %16 with undef
+ OpReturn
+ OpFunctionEnd
+ %16 = OpFunction %7 None %8
+ %17 = OpLabel
+ OpReturnValue %14
+ OpFunctionEnd
+ )";
+
+ const auto env = SPV_ENV_UNIVERSAL_1_3;
+ const auto consumer = nullptr;
+ const auto context =
+ BuildModule(env, consumer, shader, kReduceAssembleOption);
+ const auto pass = TestSubclass<OperandToUndefReductionPass>(env);
+ const auto ops = pass.WrapGetAvailableOpportunities(context.get());
+ ASSERT_EQ(0, ops.size());
+}
+
+} // namespace
+} // namespace reduce
+} // namespace spvtools
diff --git a/tools/reduce/reduce.cpp b/tools/reduce/reduce.cpp
index 390724a..65325f7 100644
--- a/tools/reduce/reduce.cpp
+++ b/tools/reduce/reduce.cpp
@@ -22,6 +22,7 @@
#include "source/opt/log.h"
#include "source/reduce/operand_to_const_reduction_pass.h"
#include "source/reduce/operand_to_dominating_id_reduction_pass.h"
+#include "source/reduce/operand_to_undef_reduction_pass.h"
#include "source/reduce/reducer.h"
#include "source/reduce/remove_opname_instruction_reduction_pass.h"
#include "source/reduce/remove_unreferenced_instruction_reduction_pass.h"
@@ -208,6 +209,8 @@
reducer.AddReductionPass(
spvtools::MakeUnique<RemoveOpNameInstructionReductionPass>(target_env));
reducer.AddReductionPass(
+ spvtools::MakeUnique<OperandToUndefReductionPass>(target_env));
+ reducer.AddReductionPass(
spvtools::MakeUnique<OperandToConstReductionPass>(target_env));
reducer.AddReductionPass(
spvtools::MakeUnique<OperandToDominatingIdReductionPass>(target_env));
