Codegen Optimizer API
This patch adds the classes Optimizer and OptimizationPass, which
define the core API of the codegen optimization.
A single (trivial) optimization is added that removes NOP
expressions from a graph.
Change-Id: I0430d6ffc61a474f997475ff787a81a9c69cfe23
diff --git a/include/ceres/codegen/internal/eliminate_nops.h b/include/ceres/codegen/internal/eliminate_nops.h
new file mode 100644
index 0000000..864aa0c
--- /dev/null
+++ b/include/ceres/codegen/internal/eliminate_nops.h
@@ -0,0 +1,67 @@
+// Ceres Solver - A fast non-linear least squares minimizer
+// Copyright 2020 Google Inc. All rights reserved.
+// http://code.google.com/p/ceres-solver/
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are met:
+//
+// * Redistributions of source code must retain the above copyright notice,
+// this list of conditions and the following disclaimer.
+// * Redistributions in binary form must reproduce the above copyright notice,
+// this list of conditions and the following disclaimer in the documentation
+// and/or other materials provided with the distribution.
+// * Neither the name of Google Inc. nor the names of its contributors may be
+// used to endorse or promote products derived from this software without
+// specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+// POSSIBILITY OF SUCH DAMAGE.
+//
+// Author: darius.rueckert@fau.de (Darius Rueckert)
+//
+#ifndef CERES_PUBLIC_CODEGEN_INTERNAL_ELIMINATE_NOPS_H_
+#define CERES_PUBLIC_CODEGEN_INTERNAL_ELIMINATE_NOPS_H_
+
+#include "ceres/codegen/internal/expression_graph.h"
+#include "ceres/codegen/internal/optimization_pass_summary.h"
+
+namespace ceres {
+namespace internal {
+
+// [OptimizationPass] NOP Cleanup
+//
+// Short Description:
+// Removes all expression with type==ExpressionType::NOP.
+//
+// Description:
+// Removing an expression not at the end requires reindexing of all later
+// expressions. Therefore, other optimization passes replace expression with
+// NOP instead of removing them. This optimization pass removes all NOPs back
+// to front.
+// The returned value is equal to the number of removed NOPs.
+//
+// Example:
+// v_0 = 1;
+// // NOP
+// v_2 = 2;
+// v_3 = v_0 + v_2
+// Transforms to:
+// v_0 = 1;
+// v_1 = 2;
+// v_2 = v_0 + v_1;
+
+OptimizationPassSummary EliminateNops(ExpressionGraph* graph);
+
+} // namespace internal
+} // namespace ceres
+
+#endif // CERES_PUBLIC_CODEGEN_INTERNAL_ELIMINATE_NOPS_H_
diff --git a/include/ceres/codegen/internal/optimization_pass_summary.h b/include/ceres/codegen/internal/optimization_pass_summary.h
new file mode 100644
index 0000000..1e376af
--- /dev/null
+++ b/include/ceres/codegen/internal/optimization_pass_summary.h
@@ -0,0 +1,51 @@
+// Ceres Solver - A fast non-linear least squares minimizer
+// Copyright 2020 Google Inc. All rights reserved.
+// http://code.google.com/p/ceres-solver/
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are met:
+//
+// * Redistributions of source code must retain the above copyright notice,
+// this list of conditions and the following disclaimer.
+// * Redistributions in binary form must reproduce the above copyright notice,
+// this list of conditions and the following disclaimer in the documentation
+// and/or other materials provided with the distribution.
+// * Neither the name of Google Inc. nor the names of its contributors may be
+// used to endorse or promote products derived from this software without
+// specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+// POSSIBILITY OF SUCH DAMAGE.
+//
+// Author: darius.rueckert@fau.de (Darius Rueckert)
+//
+#ifndef CERES_PUBLIC_CODEGEN_INTERNAL_OPTIMIZATION_PASS_SUMMARY_H_
+#define CERES_PUBLIC_CODEGEN_INTERNAL_OPTIMIZATION_PASS_SUMMARY_H_
+
+#include <string>
+
+namespace ceres {
+namespace internal {
+
+struct OptimizationPassSummary {
+ bool expression_graph_changed = false;
+ std::string optimization_pass_name;
+ int num_expressions_replaced_by_nop = 0;
+ int num_expressions_removed = 0;
+ int num_expressions_inserted = 0;
+ int num_expressions_modified = 0;
+};
+
+} // namespace internal
+} // namespace ceres
+
+#endif // CERES_PUBLIC_CODEGEN_INTERNAL_OPTIMIZATION_PASS_SUMMARY_H_
diff --git a/include/ceres/codegen/internal/optimize_expression_graph.h b/include/ceres/codegen/internal/optimize_expression_graph.h
new file mode 100644
index 0000000..8e06e8b
--- /dev/null
+++ b/include/ceres/codegen/internal/optimize_expression_graph.h
@@ -0,0 +1,74 @@
+// Ceres Solver - A fast non-linear least squares minimizer
+// Copyright 2020 Google Inc. All rights reserved.
+// http://code.google.com/p/ceres-solver/
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are met:
+//
+// * Redistributions of source code must retain the above copyright notice,
+// this list of conditions and the following disclaimer.
+// * Redistributions in binary form must reproduce the above copyright notice,
+// this list of conditions and the following disclaimer in the documentation
+// and/or other materials provided with the distribution.
+// * Neither the name of Google Inc. nor the names of its contributors may be
+// used to endorse or promote products derived from this software without
+// specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+// POSSIBILITY OF SUCH DAMAGE.
+//
+// Author: darius.rueckert@fau.de (Darius Rueckert)
+//
+#ifndef CERES_PUBLIC_CODEGEN_INTERNAL_OPTIMIZE_EXPRESSION_GRAPH_H_
+#define CERES_PUBLIC_CODEGEN_INTERNAL_OPTIMIZE_EXPRESSION_GRAPH_H_
+
+#include <memory>
+#include <vector>
+
+#include "ceres/codegen/internal/expression_graph.h"
+#include "ceres/codegen/internal/optimization_pass_summary.h"
+
+namespace ceres {
+namespace internal {
+
+struct OptimizeExpressionGraphOptions {
+ int max_num_iterations = 100;
+ bool eliminate_nops = true;
+};
+
+struct OptimizeExpressionGraphSummary {
+ int num_iterations;
+ std::vector<OptimizationPassSummary> summaries;
+};
+
+// Optimize the given ExpressionGraph in-place according to the defined
+// OptimizeExpressionGraphOptions. This will change the ExpressionGraph, but the
+// generated code will output the same numerical values.
+//
+// The Optimization iteratively applies all OptimizationPasses until the graph
+// does not change anymore or max_num_iterations is reached. Pseudo Code:
+//
+// for(int it = 0; it < max_num_iterations; ++it) {
+// graph.hasChanged = false;
+// for each pass in OptimizationPasses
+// pass.applyTo(graph)
+// if(!graph.hasChanged)
+// break;
+// }
+//
+OptimizeExpressionGraphSummary OptimizeExpressionGraph(
+ const OptimizeExpressionGraphOptions& options, ExpressionGraph* graph);
+
+} // namespace internal
+} // namespace ceres
+
+#endif // CERES_PUBLIC_CODEGEN_INTERNAL_OPTIMIZE_EXPRESSION_GRAPH_H_
diff --git a/internal/ceres/CMakeLists.txt b/internal/ceres/CMakeLists.txt
index 020a183..1611870 100644
--- a/internal/ceres/CMakeLists.txt
+++ b/internal/ceres/CMakeLists.txt
@@ -154,6 +154,8 @@
expression.cc
expression_graph.cc
expression_ref.cc
+ codegen/optimize_expression_graph.cc
+ codegen/eliminate_nops.cc
)
list(APPEND CERES_INTERNAL_SRC ${CERES_CODEGEN_SRC})
endif(CODE_GENERATION)
diff --git a/internal/ceres/codegen/CMakeLists.txt b/internal/ceres/codegen/CMakeLists.txt
index 7362aef..db21f9c 100644
--- a/internal/ceres/codegen/CMakeLists.txt
+++ b/internal/ceres/codegen/CMakeLists.txt
@@ -53,5 +53,6 @@
ceres_test(expression_graph)
ceres_test(expression_ref)
ceres_test(code_generator)
+ ceres_test(eliminate_nops)
set(CMAKE_CXX_FLAGS ${CXX_FLAGS_OLD})
endif()
diff --git a/internal/ceres/codegen/eliminate_nops.cc b/internal/ceres/codegen/eliminate_nops.cc
new file mode 100644
index 0000000..f94a873
--- /dev/null
+++ b/internal/ceres/codegen/eliminate_nops.cc
@@ -0,0 +1,55 @@
+// Ceres Solver - A fast non-linear least squares minimizer
+// Copyright 2019 Google Inc. All rights reserved.
+// http://code.google.com/p/ceres-solver/
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are met:
+//
+// * Redistributions of source code must retain the above copyright notice,
+// this list of conditions and the following disclaimer.
+// * Redistributions in binary form must reproduce the above copyright notice,
+// this list of conditions and the following disclaimer in the documentation
+// and/or other materials provided with the distribution.
+// * Neither the name of Google Inc. nor the names of its contributors may be
+// used to endorse or promote products derived from this software without
+// specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+// POSSIBILITY OF SUCH DAMAGE.
+//
+// Author: darius.rueckert@fau.de (Darius Rueckert)
+
+#include "ceres/codegen/internal/eliminate_nops.h"
+
+#include "glog/logging.h"
+
+namespace ceres {
+namespace internal {
+
+OptimizationPassSummary EliminateNops(ExpressionGraph* graph) {
+ OptimizationPassSummary summary;
+
+ for (ExpressionId id = 0; id < graph->Size(); ++id) {
+ Expression& expr = graph->ExpressionForId(id);
+
+ if (expr.type() == ExpressionType::NOP) {
+ graph->Erase(id);
+ id--;
+ summary.expression_graph_changed = true;
+ summary.num_expressions_removed++;
+ }
+ }
+ return summary;
+}
+
+} // namespace internal
+} // namespace ceres
diff --git a/internal/ceres/codegen/eliminate_nops_test.cc b/internal/ceres/codegen/eliminate_nops_test.cc
new file mode 100644
index 0000000..4b196b1
--- /dev/null
+++ b/internal/ceres/codegen/eliminate_nops_test.cc
@@ -0,0 +1,110 @@
+// Ceres Solver - A fast non-linear least squares minimizer
+// Copyright 2020 Google Inc. All rights reserved.
+// http://code.google.com/p/ceres-solver/
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are met:
+//
+// * Redistributions of source code must retain the above copyright notice,
+// this list of conditions and the following disclaimer.
+// * Redistributions in binary form must reproduce the above copyright notice,
+// this list of conditions and the following disclaimer in the documentation
+// and/or other materials provided with the distribution.
+// * Neither the name of Google Inc. nor the names of its contributors may be
+// used to endorse or promote products derived from this software without
+// specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+// POSSIBILITY OF SUCH DAMAGE.
+//
+// Author: darius.rueckert@fau.de (Darius Rueckert)
+//
+#define CERES_CODEGEN
+
+#include "ceres/codegen/internal/eliminate_nops.h"
+
+#include "ceres/codegen/internal/code_generator.h"
+#include "ceres/codegen/internal/expression_graph.h"
+#include "ceres/codegen/internal/expression_ref.h"
+#include "gtest/gtest.h"
+
+namespace ceres {
+namespace internal {
+
+using T = ExpressionRef;
+
+TEST(EliminateNops, SimpleLinear) {
+ StartRecordingExpressions();
+ {
+ T a = T(0);
+ // The Expression default constructor creates a NOP.
+ AddExpressionToGraph(Expression());
+ AddExpressionToGraph(Expression());
+ T b = T(2);
+ AddExpressionToGraph(Expression());
+ MakeOutput(b, "residual[0]");
+ AddExpressionToGraph(Expression());
+ }
+ auto graph = StopRecordingExpressions();
+
+ StartRecordingExpressions();
+ {
+ T a = T(0);
+ T b = T(2);
+ MakeOutput(b, "residual[0]");
+ }
+ auto reference = StopRecordingExpressions();
+
+ auto summary = EliminateNops(&graph);
+ EXPECT_TRUE(summary.expression_graph_changed);
+ EXPECT_EQ(graph, reference);
+}
+
+TEST(EliminateNops, Branches) {
+ StartRecordingExpressions();
+ {
+ T a = T(0);
+ // The Expression default constructor creates a NOP.
+ AddExpressionToGraph(Expression());
+ AddExpressionToGraph(Expression());
+ T b = T(2);
+ CERES_IF(a < b) {
+ AddExpressionToGraph(Expression());
+ T c = T(3);
+ }
+ CERES_ELSE {
+ AddExpressionToGraph(Expression());
+ MakeOutput(b, "residual[0]");
+ AddExpressionToGraph(Expression());
+ }
+ CERES_ENDIF
+ AddExpressionToGraph(Expression());
+ }
+ auto graph = StopRecordingExpressions();
+
+ StartRecordingExpressions();
+ {
+ T a = T(0);
+ T b = T(2);
+ CERES_IF(a < b) { T c = T(3); }
+ CERES_ELSE { MakeOutput(b, "residual[0]"); }
+ CERES_ENDIF
+ }
+ auto reference = StopRecordingExpressions();
+
+ auto summary = EliminateNops(&graph);
+ EXPECT_TRUE(summary.expression_graph_changed);
+ EXPECT_EQ(graph, reference);
+}
+
+} // namespace internal
+} // namespace ceres
diff --git a/internal/ceres/codegen/optimize_expression_graph.cc b/internal/ceres/codegen/optimize_expression_graph.cc
new file mode 100644
index 0000000..5414dc6
--- /dev/null
+++ b/internal/ceres/codegen/optimize_expression_graph.cc
@@ -0,0 +1,60 @@
+// Ceres Solver - A fast non-linear least squares minimizer
+// Copyright 2019 Google Inc. All rights reserved.
+// http://code.google.com/p/ceres-solver/
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are met:
+//
+// * Redistributions of source code must retain the above copyright notice,
+// this list of conditions and the following disclaimer.
+// * Redistributions in binary form must reproduce the above copyright notice,
+// this list of conditions and the following disclaimer in the documentation
+// and/or other materials provided with the distribution.
+// * Neither the name of Google Inc. nor the names of its contributors may be
+// used to endorse or promote products derived from this software without
+// specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+// POSSIBILITY OF SUCH DAMAGE.
+//
+// Author: darius.rueckert@fau.de (Darius Rueckert)
+
+#include "ceres/codegen/internal/optimize_expression_graph.h"
+
+#include "ceres/codegen/internal/eliminate_nops.h"
+#include "glog/logging.h"
+namespace ceres {
+namespace internal {
+
+OptimizeExpressionGraphSummary OptimizeExpressionGraph(
+ const OptimizeExpressionGraphOptions& options, ExpressionGraph* graph) {
+ OptimizeExpressionGraphSummary summary;
+ summary.num_iterations = 0;
+ while (summary.num_iterations < options.max_num_iterations) {
+ summary.num_iterations++;
+ bool changed = false;
+
+ if (options.eliminate_nops) {
+ auto pass_summary = EliminateNops(graph);
+ changed |= pass_summary.expression_graph_changed;
+ summary.summaries.push_back(pass_summary);
+ }
+
+ if (!changed) {
+ break;
+ }
+ }
+ return summary;
+}
+
+} // namespace internal
+} // namespace ceres
