Add global redundancy elimination
Adds a pass that looks for redundant instruction in a function, and
removes them. The algorithm is a hash table based value numbering
algorithm that traverses the dominator tree.
This pass removes completely redundant instructions, not partially
redundant ones.
diff --git a/Android.mk b/Android.mk
index 29ea52d..1bcd1b1 100644
--- a/Android.mk
+++ b/Android.mk
@@ -90,6 +90,7 @@
source/opt/pass.cpp \
source/opt/pass_manager.cpp \
source/opt/propagator.cpp \
+ source/opt/redundancy_elimination.cpp \
source/opt/remove_duplicates_pass.cpp \
source/opt/set_spec_constant_default_value_pass.cpp \
source/opt/strength_reduction_pass.cpp \
diff --git a/include/spirv-tools/optimizer.hpp b/include/spirv-tools/optimizer.hpp
index 805132c..eea50a8 100644
--- a/include/spirv-tools/optimizer.hpp
+++ b/include/spirv-tools/optimizer.hpp
@@ -432,6 +432,11 @@
// This pass will look for instructions in the same basic block that compute the
// same value, and remove the redundant ones.
Optimizer::PassToken CreateLocalRedundancyEliminationPass();
+
+// Create global value numbering pass.
+// This pass will look for instructions where the same value is computed on all
+// paths leading to the instruction. Those instructions are deleted.
+Optimizer::PassToken CreateRedundancyEliminationPass();
} // namespace spvtools
#endif // SPIRV_TOOLS_OPTIMIZER_HPP_
diff --git a/source/opt/CMakeLists.txt b/source/opt/CMakeLists.txt
index 278adae..4a9f437 100644
--- a/source/opt/CMakeLists.txt
+++ b/source/opt/CMakeLists.txt
@@ -55,6 +55,7 @@
pass.h
pass_manager.h
propagator.h
+ redundancy_elimination.h
reflect.h
remove_duplicates_pass.h
set_spec_constant_default_value_pass.h
@@ -106,6 +107,7 @@
pass.cpp
pass_manager.cpp
propagator.cpp
+ redundancy_elimination.cpp
remove_duplicates_pass.cpp
set_spec_constant_default_value_pass.cpp
strength_reduction_pass.cpp
diff --git a/source/opt/local_redundancy_elimination.cpp b/source/opt/local_redundancy_elimination.cpp
index 45ba012..0184883 100644
--- a/source/opt/local_redundancy_elimination.cpp
+++ b/source/opt/local_redundancy_elimination.cpp
@@ -30,8 +30,8 @@
// Keeps track of all ids that contain a given value number. We keep
// track of multiple values because they could have the same value, but
// different decorations.
- std::vector<std::vector<uint32_t>> value_to_ids;
- if (EliminateRedundanciesInBB(&bb, &vnTable, &value_to_ids))
+ std::map<uint32_t, uint32_t> value_to_ids;
+ if (EliminateRedundanciesInBB(&bb, vnTable, &value_to_ids))
modified = true;
}
}
@@ -39,8 +39,8 @@
}
bool LocalRedundancyEliminationPass::EliminateRedundanciesInBB(
- ir::BasicBlock* block, ValueNumberTable* vnTable,
- std::vector<std::vector<uint32_t>>* value_to_ids) {
+ ir::BasicBlock* block, const ValueNumberTable& vnTable,
+ std::map<uint32_t, uint32_t>* value_to_ids) {
bool modified = false;
auto func = [this, vnTable, &modified, value_to_ids](ir::Instruction* inst) {
@@ -48,38 +48,18 @@
return;
}
- uint32_t value = vnTable->GetValueNumber(inst);
+ uint32_t value = vnTable.GetValueNumber(inst);
if (value == 0) {
return;
}
- if (value >= value_to_ids->size()) {
- value_to_ids->resize(value + 1);
- }
-
- // Now that we have the value number of the instruction, we use
- // |value_to_ids| to get other ids that contain the same value. If we can
- // find an id in that set which has the same decorations, we can replace all
- // uses of the result of |inst| by that id.
- std::vector<uint32_t>& candidate_set = (*value_to_ids)[value];
- bool found_replacement = false;
- for (uint32_t candidate_id : candidate_set) {
- if (get_decoration_mgr()->HaveTheSameDecorations(inst->result_id(),
- candidate_id)) {
- context()->KillNamesAndDecorates(inst);
- context()->ReplaceAllUsesWith(inst->result_id(), candidate_id);
- context()->KillInst(inst);
- modified = true;
- found_replacement = true;
- break;
- }
- }
-
- // If we did not find a replacement, then add it as a candidate for later
- // instructions.
- if (!found_replacement) {
- candidate_set.push_back(inst->result_id());
+ auto candidate = value_to_ids->insert({value, inst->result_id()});
+ if (!candidate.second) {
+ context()->KillNamesAndDecorates(inst);
+ context()->ReplaceAllUsesWith(inst->result_id(), candidate.first->second);
+ context()->KillInst(inst);
+ modified = true;
}
};
block->ForEachInst(func);
diff --git a/source/opt/local_redundancy_elimination.h b/source/opt/local_redundancy_elimination.h
index e714c17..b599e66 100644
--- a/source/opt/local_redundancy_elimination.h
+++ b/source/opt/local_redundancy_elimination.h
@@ -33,18 +33,29 @@
public:
const char* name() const override { return "local-redundancy-elimination"; }
Status Process(ir::IRContext*) override;
+ virtual ir::IRContext::Analysis GetPreservedAnalyses() override {
+ return ir::IRContext::kAnalysisDefUse |
+ ir::IRContext::kAnalysisInstrToBlockMapping |
+ ir::IRContext::kAnalysisDecorations |
+ ir::IRContext::kAnalysisCombinators | ir::IRContext::kAnalysisCFG |
+ ir::IRContext::kAnalysisDominatorAnalysis;
+ }
- private:
- // Deletes instructions in |block| whose value is in |vnTable| or is computed
- // earlier in |block|. The values computed in |block| are added to |vnTable|.
- // |value_to_ids| is a map from a value number to the result ids known to
- // contain those values. The definition of the ids in value_to_ids must
- // dominate |block|. One value needs to map to multiple ids because the ids
- // may contain the same value, but have different decorations. Returns true
- // if the module is changed.
- bool EliminateRedundanciesInBB(
- ir::BasicBlock* block, ValueNumberTable* vnTable,
- std::vector<std::vector<uint32_t>>* value_to_ids);
+ protected:
+ // Deletes instructions in |block| whose value is in |value_to_ids| or is
+ // computed earlier in |block|.
+ //
+ // |vnTable| must have computed a value number for every result id defined
+ // in |bb|.
+ //
+ // |value_to_ids| is a map from value number to ids. If {vn, id} is in
+ // |value_to_ids| then vn is the value number of id, and the definition of id
+ // dominates |bb|.
+ //
+ // Returns true if the module is changed.
+ bool EliminateRedundanciesInBB(ir::BasicBlock* block,
+ const ValueNumberTable& vnTable,
+ std::map<uint32_t, uint32_t>* value_to_ids);
};
} // namespace opt
diff --git a/source/opt/optimizer.cpp b/source/opt/optimizer.cpp
index 5013e34..2c9fb34 100644
--- a/source/opt/optimizer.cpp
+++ b/source/opt/optimizer.cpp
@@ -94,7 +94,7 @@
.RegisterPass(CreateBlockMergePass())
.RegisterPass(CreateLocalMultiStoreElimPass())
.RegisterPass(CreateInsertExtractElimPass())
- .RegisterPass(CreateLocalRedundancyEliminationPass())
+ .RegisterPass(CreateRedundancyEliminationPass())
// Currently exposing driver bugs resulting in crashes (#946)
// .RegisterPass(CreateCommonUniformElimPass())
.RegisterPass(CreateDeadVariableEliminationPass());
@@ -113,7 +113,7 @@
.RegisterPass(CreateBlockMergePass())
.RegisterPass(CreateLocalMultiStoreElimPass())
.RegisterPass(CreateInsertExtractElimPass())
- .RegisterPass(CreateLocalRedundancyEliminationPass())
+ .RegisterPass(CreateRedundancyEliminationPass())
// Currently exposing driver bugs resulting in crashes (#946)
// .RegisterPass(CreateCommonUniformElimPass())
.RegisterPass(CreateDeadVariableEliminationPass());
@@ -282,4 +282,9 @@
return MakeUnique<Optimizer::PassToken::Impl>(
MakeUnique<opt::LocalRedundancyEliminationPass>());
}
+
+Optimizer::PassToken CreateRedundancyEliminationPass() {
+ return MakeUnique<Optimizer::PassToken::Impl>(
+ MakeUnique<opt::RedundancyEliminationPass>());
+}
} // namespace spvtools
diff --git a/source/opt/passes.h b/source/opt/passes.h
index da5f910..9c1c580 100644
--- a/source/opt/passes.h
+++ b/source/opt/passes.h
@@ -39,6 +39,7 @@
#include "local_ssa_elim_pass.h"
#include "merge_return_pass.h"
#include "null_pass.h"
+#include "redundancy_elimination.h"
#include "set_spec_constant_default_value_pass.h"
#include "strength_reduction_pass.h"
#include "strip_debug_info_pass.h"
diff --git a/source/opt/redundancy_elimination.cpp b/source/opt/redundancy_elimination.cpp
new file mode 100644
index 0000000..7e5c01d
--- /dev/null
+++ b/source/opt/redundancy_elimination.cpp
@@ -0,0 +1,58 @@
+// Copyright (c) 2017 Google Inc.
+//
+// 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 "redundancy_elimination.h"
+
+#include "value_number_table.h"
+
+namespace spvtools {
+namespace opt {
+
+Pass::Status RedundancyEliminationPass::Process(ir::IRContext* c) {
+ InitializeProcessing(c);
+
+ bool modified = false;
+ ValueNumberTable vnTable(context());
+
+ for (auto& func : *get_module()) {
+ // Build the dominator tree for this function. It is how the code is
+ // traversed.
+ opt::DominatorTree& dom_tree =
+ context()->GetDominatorAnalysis(&func, *context()->cfg())->GetDomTree();
+
+ // Keeps track of all ids that contain a given value number. We keep
+ // track of multiple values because they could have the same value, but
+ // different decorations.
+ std::map<uint32_t, uint32_t> value_to_ids;
+
+ if (EliminateRedundanciesFrom(dom_tree.GetRoot(), vnTable, value_to_ids)) {
+ modified = true;
+ }
+ }
+ return (modified ? Status::SuccessWithChange : Status::SuccessWithoutChange);
+}
+
+bool RedundancyEliminationPass::EliminateRedundanciesFrom(
+ DominatorTreeNode* bb, const ValueNumberTable& vnTable,
+ std::map<uint32_t, uint32_t> value_to_ids) {
+ bool modified = EliminateRedundanciesInBB(bb->bb_, vnTable, &value_to_ids);
+
+ for (auto dominated_bb : bb->children_) {
+ modified |= EliminateRedundanciesFrom(dominated_bb, vnTable, value_to_ids);
+ }
+
+ return modified;
+}
+} // namespace opt
+} // namespace spvtools
diff --git a/source/opt/redundancy_elimination.h b/source/opt/redundancy_elimination.h
new file mode 100644
index 0000000..634ecc3
--- /dev/null
+++ b/source/opt/redundancy_elimination.h
@@ -0,0 +1,54 @@
+// Copyright (c) 2017 Google Inc.
+//
+// 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 LIBSPIRV_OPT_REDUNDANCY_ELIMINATION_H_
+#define LIBSPIRV_OPT_REDUNDANCY_ELIMINATION_H_
+
+#include "ir_context.h"
+#include "local_redundancy_elimination.h"
+#include "pass.h"
+#include "value_number_table.h"
+
+namespace spvtools {
+namespace opt {
+
+// This pass implements total redundancy elimination. This is the same as
+// local redundancy elimination except it looks across basic block boundaries.
+// An instruction, inst, is totally redundant if there is another instruction
+// that dominates inst, and also computes the same value.
+class RedundancyEliminationPass : public LocalRedundancyEliminationPass {
+ public:
+ const char* name() const override { return "redundancy-elimination"; }
+ Status Process(ir::IRContext*) override;
+
+ protected:
+ // Removes for all total redundancies in the function starting at |bb|.
+ //
+ // |vnTable| must have computed a value number for every result id defined
+ // in the function containing |bb|.
+ //
+ // |value_to_ids| is a map from value number to ids. If {vn, id} is in
+ // |value_to_ids| then vn is the value number of id, and the defintion of id
+ // dominates |bb|.
+ //
+ // Returns true if at least one instruction is deleted.
+ bool EliminateRedundanciesFrom(DominatorTreeNode* bb,
+ const ValueNumberTable& vnTable,
+ std::map<uint32_t, uint32_t> value_to_ids);
+};
+
+} // namespace opt
+} // namespace spvtools
+
+#endif // LIBSPIRV_OPT_REDUNDANCY_ELIMINATION_H_
diff --git a/source/opt/value_number_table.cpp b/source/opt/value_number_table.cpp
index d0d2876..7f5b7ce 100644
--- a/source/opt/value_number_table.cpp
+++ b/source/opt/value_number_table.cpp
@@ -21,7 +21,8 @@
namespace spvtools {
namespace opt {
-uint32_t ValueNumberTable::GetValueNumber(spvtools::ir::Instruction* inst) {
+uint32_t ValueNumberTable::GetValueNumber(
+ spvtools::ir::Instruction* inst) const {
assert(inst->result_id() != 0 &&
"inst must have a result id to get a value number.");
diff --git a/source/opt/value_number_table.h b/source/opt/value_number_table.h
index d7651ba..8ad20df 100644
--- a/source/opt/value_number_table.h
+++ b/source/opt/value_number_table.h
@@ -56,13 +56,13 @@
// Returns the value number of the value computed by |inst|. |inst| must have
// a result id that will hold the computed value. If no value number has been
// assigned to the result id, then the return value is 0.
- uint32_t GetValueNumber(spvtools::ir::Instruction* inst);
+ uint32_t GetValueNumber(spvtools::ir::Instruction* inst) const;
// Returns the value number of the value contain in |id|. Returns 0 if it
// has not been assigned a value number.
- inline uint32_t GetValueNumber(uint32_t id);
+ inline uint32_t GetValueNumber(uint32_t id) const;
- ir::IRContext* context() { return context_; }
+ ir::IRContext* context() const { return context_; }
private:
// Assigns a value number to every result id in the module.
@@ -82,10 +82,9 @@
std::unordered_map<uint32_t, uint32_t> id_to_value_;
ir::IRContext* context_;
uint32_t next_value_number_;
-
};
-uint32_t ValueNumberTable::GetValueNumber(uint32_t id) {
+uint32_t ValueNumberTable::GetValueNumber(uint32_t id) const {
return GetValueNumber(context()->get_def_use_mgr()->GetDef(id));
}
diff --git a/test/opt/CMakeLists.txt b/test/opt/CMakeLists.txt
index 36af223..3273e85 100644
--- a/test/opt/CMakeLists.txt
+++ b/test/opt/CMakeLists.txt
@@ -225,3 +225,9 @@
SRCS propagator_test.cpp
LIBS SPIRV-Tools-opt
)
+
+add_spvtools_unittest(TARGET redundancy_elimination
+ SRCS redundancy_elimination_test.cpp pass_utils.cpp
+ LIBS SPIRV-Tools-opt
+)
+
diff --git a/test/opt/redundancy_elimination_test.cpp b/test/opt/redundancy_elimination_test.cpp
new file mode 100644
index 0000000..a257313
--- /dev/null
+++ b/test/opt/redundancy_elimination_test.cpp
@@ -0,0 +1,276 @@
+// Copyright (c) 2017 Google Inc.
+//
+// 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 "opt/value_number_table.h"
+
+#include "assembly_builder.h"
+#include "gmock/gmock.h"
+#include "opt/build_module.h"
+#include "pass_fixture.h"
+#include "pass_utils.h"
+
+namespace {
+
+using namespace spvtools;
+
+using ::testing::HasSubstr;
+using ::testing::MatchesRegex;
+
+using RedundancyEliminationTest = PassTest<::testing::Test>;
+
+#ifdef SPIRV_EFFCEE
+// Test that it can get a simple case of local redundancy elimination.
+// The rest of the test check for extra functionality.
+TEST_F(RedundancyEliminationTest, RemoveRedundantLocalAdd) {
+ const std::string text = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %2 "main"
+ OpExecutionMode %2 OriginUpperLeft
+ OpSource GLSL 430
+ %3 = OpTypeVoid
+ %4 = OpTypeFunction %3
+ %5 = OpTypeFloat 32
+ %6 = OpTypePointer Function %5
+ %2 = OpFunction %3 None %4
+ %7 = OpLabel
+ %8 = OpVariable %6 Function
+ %9 = OpLoad %5 %8
+ %10 = OpFAdd %5 %9 %9
+; CHECK: OpFAdd
+; CHECK-NOT: OpFAdd
+ %11 = OpFAdd %5 %9 %9
+ OpReturn
+ OpFunctionEnd
+ )";
+ SinglePassRunAndMatch<opt::RedundancyEliminationPass>(text);
+}
+
+// Remove a redundant add across basic blocks.
+TEST_F(RedundancyEliminationTest, RemoveRedundantAdd) {
+ const std::string text = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %2 "main"
+ OpExecutionMode %2 OriginUpperLeft
+ OpSource GLSL 430
+ %3 = OpTypeVoid
+ %4 = OpTypeFunction %3
+ %5 = OpTypeFloat 32
+ %6 = OpTypePointer Function %5
+ %2 = OpFunction %3 None %4
+ %7 = OpLabel
+ %8 = OpVariable %6 Function
+ %9 = OpLoad %5 %8
+ %10 = OpFAdd %5 %9 %9
+ OpBranch %11
+ %11 = OpLabel
+; CHECK: OpFAdd
+; CHECK-NOT: OpFAdd
+ %12 = OpFAdd %5 %9 %9
+ OpReturn
+ OpFunctionEnd
+ )";
+ SinglePassRunAndMatch<opt::RedundancyEliminationPass>(text);
+}
+
+// Remove a redundant add going through a multiple basic blocks.
+TEST_F(RedundancyEliminationTest, RemoveRedundantAddDiamond) {
+ const std::string text = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %2 "main"
+ OpExecutionMode %2 OriginUpperLeft
+ OpSource GLSL 430
+ %3 = OpTypeVoid
+ %4 = OpTypeFunction %3
+ %5 = OpTypeFloat 32
+ %6 = OpTypePointer Function %5
+ %7 = OpTypeBool
+ %8 = OpConstantTrue %7
+ %2 = OpFunction %3 None %4
+ %9 = OpLabel
+ %10 = OpVariable %6 Function
+ %11 = OpLoad %5 %10
+ %12 = OpFAdd %5 %11 %11
+; CHECK: OpFAdd
+; CHECK-NOT: OpFAdd
+ OpBranchConditional %8 %13 %14
+ %13 = OpLabel
+ OpBranch %15
+ %14 = OpLabel
+ OpBranch %15
+ %15 = OpLabel
+ %16 = OpFAdd %5 %11 %11
+ OpReturn
+ OpFunctionEnd
+
+ )";
+ SinglePassRunAndMatch<opt::RedundancyEliminationPass>(text);
+}
+
+// Remove a redundant add in a side node.
+TEST_F(RedundancyEliminationTest, RemoveRedundantAddInSideNode) {
+ const std::string text = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %2 "main"
+ OpExecutionMode %2 OriginUpperLeft
+ OpSource GLSL 430
+ %3 = OpTypeVoid
+ %4 = OpTypeFunction %3
+ %5 = OpTypeFloat 32
+ %6 = OpTypePointer Function %5
+ %7 = OpTypeBool
+ %8 = OpConstantTrue %7
+ %2 = OpFunction %3 None %4
+ %9 = OpLabel
+ %10 = OpVariable %6 Function
+ %11 = OpLoad %5 %10
+ %12 = OpFAdd %5 %11 %11
+; CHECK: OpFAdd
+; CHECK-NOT: OpFAdd
+ OpBranchConditional %8 %13 %14
+ %13 = OpLabel
+ OpBranch %15
+ %14 = OpLabel
+ %16 = OpFAdd %5 %11 %11
+ OpBranch %15
+ %15 = OpLabel
+ OpReturn
+ OpFunctionEnd
+
+ )";
+ SinglePassRunAndMatch<opt::RedundancyEliminationPass>(text);
+}
+
+// Remove a redundant add whose value is in the result of a phi node.
+TEST_F(RedundancyEliminationTest, RemoveRedundantAddWithPhi) {
+ const std::string text = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %2 "main"
+ OpExecutionMode %2 OriginUpperLeft
+ OpSource GLSL 430
+ %3 = OpTypeVoid
+ %4 = OpTypeFunction %3
+ %5 = OpTypeFloat 32
+ %6 = OpTypePointer Function %5
+ %7 = OpTypeBool
+ %8 = OpConstantTrue %7
+ %2 = OpFunction %3 None %4
+ %9 = OpLabel
+ %10 = OpVariable %6 Function
+ %11 = OpLoad %5 %10
+ OpBranchConditional %8 %13 %14
+ %13 = OpLabel
+ %add1 = OpFAdd %5 %11 %11
+; CHECK: OpFAdd
+ OpBranch %15
+ %14 = OpLabel
+ %add2 = OpFAdd %5 %11 %11
+; CHECK: OpFAdd
+ OpBranch %15
+ %15 = OpLabel
+; CHECK: OpPhi
+ %phi = OpPhi %5 %add1 %13 %add2 %14
+; CHECK-NOT: OpFAdd
+ %16 = OpFAdd %5 %11 %11
+ OpReturn
+ OpFunctionEnd
+
+ )";
+ SinglePassRunAndMatch<opt::RedundancyEliminationPass>(text);
+}
+
+// Keep the add because it is redundant on some paths, but not all paths.
+TEST_F(RedundancyEliminationTest, KeepPartiallyRedundantAdd) {
+ const std::string text = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %2 "main"
+ OpExecutionMode %2 OriginUpperLeft
+ OpSource GLSL 430
+ %3 = OpTypeVoid
+ %4 = OpTypeFunction %3
+ %5 = OpTypeFloat 32
+ %6 = OpTypePointer Function %5
+ %7 = OpTypeBool
+ %8 = OpConstantTrue %7
+ %2 = OpFunction %3 None %4
+ %9 = OpLabel
+ %10 = OpVariable %6 Function
+ %11 = OpLoad %5 %10
+ OpBranchConditional %8 %13 %14
+ %13 = OpLabel
+ %add = OpFAdd %5 %11 %11
+ OpBranch %15
+ %14 = OpLabel
+ OpBranch %15
+ %15 = OpLabel
+ %16 = OpFAdd %5 %11 %11
+ OpReturn
+ OpFunctionEnd
+
+ )";
+ auto result = SinglePassRunAndDisassemble<opt::RedundancyEliminationPass>(
+ text, /* skip_nop = */ true);
+ EXPECT_EQ(opt::Pass::Status::SuccessWithoutChange, std::get<1>(result));
+}
+
+// Keep the add. Even if it is redundant on all paths, there is no single id
+// whose definition dominates the add and contains the same value.
+TEST_F(RedundancyEliminationTest, KeepRedundantAddWithoutPhi) {
+ const std::string text = R"(
+ OpCapability Shader
+ %1 = OpExtInstImport "GLSL.std.450"
+ OpMemoryModel Logical GLSL450
+ OpEntryPoint Fragment %2 "main"
+ OpExecutionMode %2 OriginUpperLeft
+ OpSource GLSL 430
+ %3 = OpTypeVoid
+ %4 = OpTypeFunction %3
+ %5 = OpTypeFloat 32
+ %6 = OpTypePointer Function %5
+ %7 = OpTypeBool
+ %8 = OpConstantTrue %7
+ %2 = OpFunction %3 None %4
+ %9 = OpLabel
+ %10 = OpVariable %6 Function
+ %11 = OpLoad %5 %10
+ OpBranchConditional %8 %13 %14
+ %13 = OpLabel
+ %add1 = OpFAdd %5 %11 %11
+ OpBranch %15
+ %14 = OpLabel
+ %add2 = OpFAdd %5 %11 %11
+ OpBranch %15
+ %15 = OpLabel
+ %16 = OpFAdd %5 %11 %11
+ OpReturn
+ OpFunctionEnd
+
+ )";
+ auto result = SinglePassRunAndDisassemble<opt::RedundancyEliminationPass>(
+ text, /* skip_nop = */ true);
+ EXPECT_EQ(opt::Pass::Status::SuccessWithoutChange, std::get<1>(result));
+}
+#endif
+} // anonymous namespace
diff --git a/tools/opt/opt.cpp b/tools/opt/opt.cpp
index 972f153..bd72034 100644
--- a/tools/opt/opt.cpp
+++ b/tools/opt/opt.cpp
@@ -197,6 +197,9 @@
'spirv-opt --merge-blocks -O ...' applies the transformation
--merge-blocks followed by all the transformations implied by
-O.
+ --redundancy-elimination
+ Looks for instructions in the same function that compute the
+ same value, and deletes the redundant ones.
--relax-store-struct
Allow store from one struct type to a different type with
compatible layout and members. This option is forwarded to the
@@ -389,6 +392,8 @@
optimizer->RegisterPass(CreateCFGCleanupPass());
} else if (0 == strcmp(cur_arg, "--local-redundancy-elimination")) {
optimizer->RegisterPass(CreateLocalRedundancyEliminationPass());
+ } else if (0 == strcmp(cur_arg, "--redundancy-elimination")) {
+ optimizer->RegisterPass(CreateRedundancyEliminationPass());
} else if (0 == strcmp(cur_arg, "--relax-store-struct")) {
options->relax_struct_store = true;
} else if (0 == strcmp(cur_arg, "-O")) {
