Merge "Initiate a constant propagation pass in the optimizing compiler."
diff --git a/build/Android.gtest.mk b/build/Android.gtest.mk
index ac07721..3f58527 100644
--- a/build/Android.gtest.mk
+++ b/build/Android.gtest.mk
@@ -141,6 +141,7 @@
compiler/oat_test.cc \
compiler/optimizing/codegen_test.cc \
compiler/optimizing/dead_code_elimination_test.cc \
+ compiler/optimizing/constant_propagation_test.cc \
compiler/optimizing/dominator_test.cc \
compiler/optimizing/find_loops_test.cc \
compiler/optimizing/graph_checker_test.cc \
diff --git a/compiler/Android.mk b/compiler/Android.mk
index 3d433d5..35cddf9 100644
--- a/compiler/Android.mk
+++ b/compiler/Android.mk
@@ -90,6 +90,7 @@
optimizing/code_generator_arm.cc \
optimizing/code_generator_x86.cc \
optimizing/code_generator_x86_64.cc \
+ optimizing/constant_propagation.cc \
optimizing/dead_code_elimination.cc \
optimizing/graph_checker.cc \
optimizing/graph_visualizer.cc \
diff --git a/compiler/optimizing/constant_propagation.cc b/compiler/optimizing/constant_propagation.cc
new file mode 100644
index 0000000..d675164
--- /dev/null
+++ b/compiler/optimizing/constant_propagation.cc
@@ -0,0 +1,47 @@
+/*
+ * Copyright (C) 2014 The Android Open Source Project
+ *
+ * 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 "constant_propagation.h"
+
+namespace art {
+
+void ConstantPropagation::Run() {
+ // Process basic blocks in reverse post-order in the dominator tree,
+ // so that an instruction turned into a constant, used as input of
+ // another instruction, may possibly be used to turn that second
+ // instruction into a constant as well.
+ for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
+ HBasicBlock* block = it.Current();
+ // Traverse this block's instructions in (forward) order and
+ // replace the ones that can be statically evaluated by a
+ // compile-time counterpart.
+ for (HInstructionIterator it(block->GetInstructions());
+ !it.Done(); it.Advance()) {
+ HInstruction* inst = it.Current();
+ // Constant folding: replace `c <- a op b' with a compile-time
+ // evaluation of `a op b' if `a' and `b' are constant.
+ if (inst->IsBinaryOperation()) {
+ HConstant* constant =
+ inst->AsBinaryOperation()->TryStaticEvaluation(graph_->GetArena());
+ if (constant != nullptr) {
+ inst->GetBlock()->ReplaceAndRemoveInstructionWith(inst, constant);
+ }
+ }
+ }
+ }
+}
+
+} // namespace art
diff --git a/compiler/optimizing/constant_propagation.h b/compiler/optimizing/constant_propagation.h
new file mode 100644
index 0000000..0729881
--- /dev/null
+++ b/compiler/optimizing/constant_propagation.h
@@ -0,0 +1,43 @@
+/*
+ * Copyright (C) 2014 The Android Open Source Project
+ *
+ * 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 ART_COMPILER_OPTIMIZING_CONSTANT_PROPAGATION_H_
+#define ART_COMPILER_OPTIMIZING_CONSTANT_PROPAGATION_H_
+
+#include "nodes.h"
+
+namespace art {
+
+/**
+ * Optimization pass performing a simple constant propagation on the
+ * SSA form.
+ */
+class ConstantPropagation : public ValueObject {
+ public:
+ explicit ConstantPropagation(HGraph* graph)
+ : graph_(graph) {}
+
+ void Run();
+
+ private:
+ HGraph* const graph_;
+
+ DISALLOW_COPY_AND_ASSIGN(ConstantPropagation);
+};
+
+} // namespace art
+
+#endif // ART_COMPILER_OPTIMIZING_CONSTANT_PROPAGATION_H_
diff --git a/compiler/optimizing/constant_propagation_test.cc b/compiler/optimizing/constant_propagation_test.cc
new file mode 100644
index 0000000..5c8c709
--- /dev/null
+++ b/compiler/optimizing/constant_propagation_test.cc
@@ -0,0 +1,487 @@
+/*
+ * Copyright (C) 2014 The Android Open Source Project
+ *
+ * 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 "constant_propagation.h"
+#include "dead_code_elimination.h"
+#include "pretty_printer.h"
+#include "graph_checker.h"
+#include "optimizing_unit_test.h"
+
+#include "gtest/gtest.h"
+
+namespace art {
+
+static void TestCode(const uint16_t* data,
+ const std::string& expected_before,
+ const std::string& expected_after_cp,
+ const std::string& expected_after_dce) {
+ ArenaPool pool;
+ ArenaAllocator allocator(&pool);
+ HGraph* graph = CreateCFG(&allocator, data);
+ ASSERT_NE(graph, nullptr);
+
+ graph->BuildDominatorTree();
+ graph->TransformToSSA();
+
+ StringPrettyPrinter printer_before(graph);
+ printer_before.VisitInsertionOrder();
+ std::string actual_before = printer_before.str();
+ ASSERT_EQ(expected_before, actual_before);
+
+ ConstantPropagation(graph).Run();
+
+ StringPrettyPrinter printer_after_cp(graph);
+ printer_after_cp.VisitInsertionOrder();
+ std::string actual_after_cp = printer_after_cp.str();
+ ASSERT_EQ(expected_after_cp, actual_after_cp);
+
+ DeadCodeElimination(graph).Run();
+
+ StringPrettyPrinter printer_after_dce(graph);
+ printer_after_dce.VisitInsertionOrder();
+ std::string actual_after_dce = printer_after_dce.str();
+ ASSERT_EQ(expected_after_dce, actual_after_dce);
+
+ SSAChecker ssa_checker(&allocator, graph);
+ ssa_checker.VisitInsertionOrder();
+ ASSERT_TRUE(ssa_checker.IsValid());
+}
+
+
+/**
+ * Tiny three-register program exercising int constant folding on addition.
+ *
+ * 16-bit
+ * offset
+ * ------
+ * v0 <- 1 0. const/4 v0, #+1
+ * v1 <- 2 1. const/4 v1, #+2
+ * v2 <- v0 + v1 2. add-int v2, v0, v1
+ * return v2 4. return v2
+ */
+TEST(ConstantPropagation, IntConstantFoldingOnAddition1) {
+ const uint16_t data[] = THREE_REGISTERS_CODE_ITEM(
+ Instruction::CONST_4 | 0 << 8 | 1 << 12,
+ Instruction::CONST_4 | 1 << 8 | 2 << 12,
+ Instruction::ADD_INT | 2 << 8, 0 | 1 << 8,
+ Instruction::RETURN | 2 << 8);
+
+ std::string expected_before =
+ "BasicBlock 0, succ: 1\n"
+ " 3: IntConstant [9]\n"
+ " 5: IntConstant [9]\n"
+ " 14: SuspendCheck\n"
+ " 15: Goto 1\n"
+ "BasicBlock 1, pred: 0, succ: 2\n"
+ " 9: Add(3, 5) [12]\n"
+ " 12: Return(9)\n"
+ "BasicBlock 2, pred: 1\n"
+ " 13: Exit\n";
+
+ // Expected difference after constant propagation.
+ diff_t expected_cp_diff = {
+ { " 3: IntConstant [9]\n", " 3: IntConstant\n" },
+ { " 5: IntConstant [9]\n", " 5: IntConstant\n" },
+ { " 9: Add(3, 5) [12]\n", " 16: IntConstant [12]\n" },
+ { " 12: Return(9)\n", " 12: Return(16)\n" }
+ };
+ std::string expected_after_cp = Patch(expected_before, expected_cp_diff);
+
+ // Expected difference after dead code elimination.
+ diff_t expected_dce_diff = {
+ { " 3: IntConstant\n", removed },
+ { " 5: IntConstant\n", removed }
+ };
+ std::string expected_after_dce = Patch(expected_after_cp, expected_dce_diff);
+
+ TestCode(data, expected_before, expected_after_cp, expected_after_dce);
+}
+
+/**
+ * Small three-register program exercising int constant folding on addition.
+ *
+ * 16-bit
+ * offset
+ * ------
+ * v0 <- 1 0. const/4 v0, #+1
+ * v1 <- 2 1. const/4 v1, #+2
+ * v0 <- v0 + v1 2. add-int/2addr v0, v1
+ * v1 <- 3 3. const/4 v1, #+3
+ * v2 <- 4 4. const/4 v2, #+4
+ * v1 <- v1 + v2 5. add-int/2addr v1, v2
+ * v2 <- v0 + v1 6. add-int v2, v0, v1
+ * return v2 8. return v2
+ */
+TEST(ConstantPropagation, IntConstantFoldingOnAddition2) {
+ const uint16_t data[] = THREE_REGISTERS_CODE_ITEM(
+ Instruction::CONST_4 | 0 << 8 | 1 << 12,
+ Instruction::CONST_4 | 1 << 8 | 2 << 12,
+ Instruction::ADD_INT_2ADDR | 0 << 8 | 1 << 12,
+ Instruction::CONST_4 | 1 << 8 | 3 << 12,
+ Instruction::CONST_4 | 2 << 8 | 4 << 12,
+ Instruction::ADD_INT_2ADDR | 1 << 8 | 2 << 12,
+ Instruction::ADD_INT | 2 << 8, 0 | 1 << 8,
+ Instruction::RETURN | 2 << 8);
+
+ std::string expected_before =
+ "BasicBlock 0, succ: 1\n"
+ " 3: IntConstant [9]\n"
+ " 5: IntConstant [9]\n"
+ " 11: IntConstant [17]\n"
+ " 13: IntConstant [17]\n"
+ " 26: SuspendCheck\n"
+ " 27: Goto 1\n"
+ "BasicBlock 1, pred: 0, succ: 2\n"
+ " 9: Add(3, 5) [21]\n"
+ " 17: Add(11, 13) [21]\n"
+ " 21: Add(9, 17) [24]\n"
+ " 24: Return(21)\n"
+ "BasicBlock 2, pred: 1\n"
+ " 25: Exit\n";
+
+ // Expected difference after constant propagation.
+ diff_t expected_cp_diff = {
+ { " 3: IntConstant [9]\n", " 3: IntConstant\n" },
+ { " 5: IntConstant [9]\n", " 5: IntConstant\n" },
+ { " 11: IntConstant [17]\n", " 11: IntConstant\n" },
+ { " 13: IntConstant [17]\n", " 13: IntConstant\n" },
+ { " 9: Add(3, 5) [21]\n", " 28: IntConstant\n" },
+ { " 17: Add(11, 13) [21]\n", " 29: IntConstant\n" },
+ { " 21: Add(9, 17) [24]\n", " 30: IntConstant [24]\n" },
+ { " 24: Return(21)\n", " 24: Return(30)\n" }
+ };
+ std::string expected_after_cp = Patch(expected_before, expected_cp_diff);
+
+ // Expected difference after dead code elimination.
+ diff_t expected_dce_diff = {
+ { " 3: IntConstant\n", removed },
+ { " 5: IntConstant\n", removed },
+ { " 11: IntConstant\n", removed },
+ { " 13: IntConstant\n", removed },
+ { " 28: IntConstant\n", removed },
+ { " 29: IntConstant\n", removed }
+ };
+ std::string expected_after_dce = Patch(expected_after_cp, expected_dce_diff);
+
+ TestCode(data, expected_before, expected_after_cp, expected_after_dce);
+}
+
+/**
+ * Tiny three-register program exercising int constant folding on subtraction.
+ *
+ * 16-bit
+ * offset
+ * ------
+ * v0 <- 3 0. const/4 v0, #+3
+ * v1 <- 2 1. const/4 v1, #+2
+ * v2 <- v0 - v1 2. sub-int v2, v0, v1
+ * return v2 4. return v2
+ */
+TEST(ConstantPropagation, IntConstantFoldingOnSubtraction) {
+ const uint16_t data[] = THREE_REGISTERS_CODE_ITEM(
+ Instruction::CONST_4 | 0 << 8 | 3 << 12,
+ Instruction::CONST_4 | 1 << 8 | 2 << 12,
+ Instruction::SUB_INT | 2 << 8, 0 | 1 << 8,
+ Instruction::RETURN | 2 << 8);
+
+ std::string expected_before =
+ "BasicBlock 0, succ: 1\n"
+ " 3: IntConstant [9]\n"
+ " 5: IntConstant [9]\n"
+ " 14: SuspendCheck\n"
+ " 15: Goto 1\n"
+ "BasicBlock 1, pred: 0, succ: 2\n"
+ " 9: Sub(3, 5) [12]\n"
+ " 12: Return(9)\n"
+ "BasicBlock 2, pred: 1\n"
+ " 13: Exit\n";
+
+ // Expected difference after constant propagation.
+ diff_t expected_cp_diff = {
+ { " 3: IntConstant [9]\n", " 3: IntConstant\n" },
+ { " 5: IntConstant [9]\n", " 5: IntConstant\n" },
+ { " 9: Sub(3, 5) [12]\n", " 16: IntConstant [12]\n" },
+ { " 12: Return(9)\n", " 12: Return(16)\n" }
+ };
+ std::string expected_after_cp = Patch(expected_before, expected_cp_diff);
+
+ // Expected difference after dead code elimination.
+ diff_t expected_dce_diff = {
+ { " 3: IntConstant\n", removed },
+ { " 5: IntConstant\n", removed }
+ };
+ std::string expected_after_dce = Patch(expected_after_cp, expected_dce_diff);
+
+ TestCode(data, expected_before, expected_after_cp, expected_after_dce);
+}
+
+#define SIX_REGISTERS_CODE_ITEM(...) \
+ { 6, 0, 0, 0, 0, 0, NUM_INSTRUCTIONS(__VA_ARGS__), 0, __VA_ARGS__ }
+
+/**
+ * Tiny three-register-pair program exercising long constant folding
+ * on addition.
+ *
+ * 16-bit
+ * offset
+ * ------
+ * (v0, v1) <- 1 0. const-wide/16 v0, #+1
+ * (v2, v3) <- 2 2. const-wide/16 v2, #+2
+ * (v4, v5) <-
+ * (v0, v1) + (v1, v2) 4. add-long v4, v0, v2
+ * return (v4, v5) 6. return-wide v4
+ */
+TEST(ConstantPropagation, LongConstantFoldingOnAddition) {
+ const uint16_t data[] = SIX_REGISTERS_CODE_ITEM(
+ Instruction::CONST_WIDE_16 | 0 << 8, 1,
+ Instruction::CONST_WIDE_16 | 2 << 8, 2,
+ Instruction::ADD_LONG | 4 << 8, 0 | 2 << 8,
+ Instruction::RETURN_WIDE | 4 << 8);
+
+ std::string expected_before =
+ "BasicBlock 0, succ: 1\n"
+ " 6: LongConstant [12]\n"
+ " 8: LongConstant [12]\n"
+ " 17: SuspendCheck\n"
+ " 18: Goto 1\n"
+ "BasicBlock 1, pred: 0, succ: 2\n"
+ " 12: Add(6, 8) [15]\n"
+ " 15: Return(12)\n"
+ "BasicBlock 2, pred: 1\n"
+ " 16: Exit\n";
+
+ // Expected difference after constant propagation.
+ diff_t expected_cp_diff = {
+ { " 6: LongConstant [12]\n", " 6: LongConstant\n" },
+ { " 8: LongConstant [12]\n", " 8: LongConstant\n" },
+ { " 12: Add(6, 8) [15]\n", " 19: LongConstant [15]\n" },
+ { " 15: Return(12)\n", " 15: Return(19)\n" }
+ };
+ std::string expected_after_cp = Patch(expected_before, expected_cp_diff);
+
+ // Expected difference after dead code elimination.
+ diff_t expected_dce_diff = {
+ { " 6: LongConstant\n", removed },
+ { " 8: LongConstant\n", removed }
+ };
+ std::string expected_after_dce = Patch(expected_after_cp, expected_dce_diff);
+
+ TestCode(data, expected_before, expected_after_cp, expected_after_dce);
+}
+
+/**
+ * Tiny three-register-pair program exercising long constant folding
+ * on subtraction.
+ *
+ * 16-bit
+ * offset
+ * ------
+ * (v0, v1) <- 3 0. const-wide/16 v0, #+3
+ * (v2, v3) <- 2 2. const-wide/16 v2, #+2
+ * (v4, v5) <-
+ * (v0, v1) - (v1, v2) 4. sub-long v4, v0, v2
+ * return (v4, v5) 6. return-wide v4
+ */
+TEST(ConstantPropagation, LongConstantFoldingOnSubtraction) {
+ const uint16_t data[] = SIX_REGISTERS_CODE_ITEM(
+ Instruction::CONST_WIDE_16 | 0 << 8, 3,
+ Instruction::CONST_WIDE_16 | 2 << 8, 2,
+ Instruction::SUB_LONG | 4 << 8, 0 | 2 << 8,
+ Instruction::RETURN_WIDE | 4 << 8);
+
+ std::string expected_before =
+ "BasicBlock 0, succ: 1\n"
+ " 6: LongConstant [12]\n"
+ " 8: LongConstant [12]\n"
+ " 17: SuspendCheck\n"
+ " 18: Goto 1\n"
+ "BasicBlock 1, pred: 0, succ: 2\n"
+ " 12: Sub(6, 8) [15]\n"
+ " 15: Return(12)\n"
+ "BasicBlock 2, pred: 1\n"
+ " 16: Exit\n";
+
+ // Expected difference after constant propagation.
+ diff_t expected_cp_diff = {
+ { " 6: LongConstant [12]\n", " 6: LongConstant\n" },
+ { " 8: LongConstant [12]\n", " 8: LongConstant\n" },
+ { " 12: Sub(6, 8) [15]\n", " 19: LongConstant [15]\n" },
+ { " 15: Return(12)\n", " 15: Return(19)\n" }
+ };
+ std::string expected_after_cp = Patch(expected_before, expected_cp_diff);
+
+ // Expected difference after dead code elimination.
+ diff_t expected_dce_diff = {
+ { " 6: LongConstant\n", removed },
+ { " 8: LongConstant\n", removed }
+ };
+ std::string expected_after_dce = Patch(expected_after_cp, expected_dce_diff);
+
+ TestCode(data, expected_before, expected_after_cp, expected_after_dce);
+}
+
+/**
+ * Three-register program with jumps leading to the creation of many
+ * blocks.
+ *
+ * The intent of this test is to ensure that all constant expressions
+ * are actually evaluated at compile-time, thanks to the reverse
+ * (forward) post-order traversal of the the dominator tree.
+ *
+ * 16-bit
+ * offset
+ * ------
+ * v0 <- 0 0. const/4 v0, #+0
+ * v1 <- 1 1. const/4 v1, #+1
+ * v2 <- v0 + v1 2. add-int v2, v0, v1
+ * goto L2 4. goto +4
+ * L1: v1 <- v0 + 3 5. add-int/lit16 v1, v0, #+3
+ * goto L3 7. goto +4
+ * L2: v0 <- v2 + 2 8. add-int/lit16 v0, v2, #+2
+ * goto L1 10. goto +(-5)
+ * L3: v2 <- v1 + 4 11. add-int/lit16 v2, v1, #+4
+ * return v2 13. return v2
+ */
+TEST(ConstantPropagation, IntConstantFoldingAndJumps) {
+ const uint16_t data[] = THREE_REGISTERS_CODE_ITEM(
+ Instruction::CONST_4 | 0 << 8 | 0 << 12,
+ Instruction::CONST_4 | 1 << 8 | 1 << 12,
+ Instruction::ADD_INT | 2 << 8, 0 | 1 << 8,
+ Instruction::GOTO | 4 << 8,
+ Instruction::ADD_INT_LIT16 | 1 << 8 | 0 << 12, 3,
+ Instruction::GOTO | 4 << 8,
+ Instruction::ADD_INT_LIT16 | 0 << 8 | 2 << 12, 2,
+ static_cast<uint16_t>(Instruction::GOTO | -5 << 8),
+ Instruction::ADD_INT_LIT16 | 2 << 8 | 1 << 12, 4,
+ Instruction::RETURN | 2 << 8);
+
+ std::string expected_before =
+ "BasicBlock 0, succ: 1\n"
+ " 3: IntConstant [9]\n"
+ " 5: IntConstant [9]\n"
+ " 13: IntConstant [14]\n"
+ " 18: IntConstant [19]\n"
+ " 24: IntConstant [25]\n"
+ " 30: SuspendCheck\n"
+ " 31: Goto 1\n"
+ "BasicBlock 1, pred: 0, succ: 3\n"
+ " 9: Add(3, 5) [19]\n"
+ " 11: Goto 3\n"
+ "BasicBlock 2, pred: 3, succ: 4\n"
+ " 14: Add(19, 13) [25]\n"
+ " 16: Goto 4\n"
+ "BasicBlock 3, pred: 1, succ: 2\n"
+ " 19: Add(9, 18) [14]\n"
+ " 21: SuspendCheck\n"
+ " 22: Goto 2\n"
+ "BasicBlock 4, pred: 2, succ: 5\n"
+ " 25: Add(14, 24) [28]\n"
+ " 28: Return(25)\n"
+ "BasicBlock 5, pred: 4\n"
+ " 29: Exit\n";
+
+ // Expected difference after constant propagation.
+ diff_t expected_cp_diff = {
+ { " 3: IntConstant [9]\n", " 3: IntConstant\n" },
+ { " 5: IntConstant [9]\n", " 5: IntConstant []\n" },
+ { " 13: IntConstant [14]\n", " 13: IntConstant\n" },
+ { " 18: IntConstant [19]\n", " 18: IntConstant\n" },
+ { " 24: IntConstant [25]\n", " 24: IntConstant\n" },
+ { " 9: Add(3, 5) [19]\n", " 32: IntConstant []\n" },
+ { " 14: Add(19, 13) [25]\n", " 34: IntConstant\n" },
+ { " 19: Add(9, 18) [14]\n", " 33: IntConstant []\n" },
+ { " 25: Add(14, 24) [28]\n", " 35: IntConstant [28]\n" },
+ { " 28: Return(25)\n", " 28: Return(35)\n"}
+ };
+ std::string expected_after_cp = Patch(expected_before, expected_cp_diff);
+
+ // Expected difference after dead code elimination.
+ diff_t expected_dce_diff = {
+ { " 3: IntConstant\n", removed },
+ { " 13: IntConstant\n", removed },
+ { " 18: IntConstant\n", removed },
+ { " 24: IntConstant\n", removed },
+ { " 34: IntConstant\n", removed },
+ };
+ std::string expected_after_dce = Patch(expected_after_cp, expected_dce_diff);
+
+ TestCode(data, expected_before, expected_after_cp, expected_after_dce);
+}
+
+
+/**
+ * Three-register program with a constant (static) condition.
+ *
+ * 16-bit
+ * offset
+ * ------
+ * v1 <- 1 0. const/4 v1, #+1
+ * v0 <- 0 1. const/4 v0, #+0
+ * if v1 >= 0 goto L1 2. if-gez v1, +3
+ * v0 <- v1 4. move v0, v1
+ * L1: v2 <- v0 + v1 5. add-int v2, v0, v1
+ * return-void 7. return
+ */
+TEST(ConstantPropagation, ConstantCondition) {
+ const uint16_t data[] = THREE_REGISTERS_CODE_ITEM(
+ Instruction::CONST_4 | 1 << 8 | 1 << 12,
+ Instruction::CONST_4 | 0 << 8 | 0 << 12,
+ Instruction::IF_GEZ | 1 << 8, 3,
+ Instruction::MOVE | 0 << 8 | 1 << 12,
+ Instruction::ADD_INT | 2 << 8, 0 | 1 << 8,
+ Instruction::RETURN_VOID);
+
+ std::string expected_before =
+ "BasicBlock 0, succ: 1\n"
+ " 3: IntConstant [15, 22, 8]\n"
+ " 5: IntConstant [22, 8]\n"
+ " 19: SuspendCheck\n"
+ " 20: Goto 1\n"
+ "BasicBlock 1, pred: 0, succ: 5, 2\n"
+ " 8: GreaterThanOrEqual(3, 5) [9]\n"
+ " 9: If(8)\n"
+ "BasicBlock 2, pred: 1, succ: 3\n"
+ " 12: Goto 3\n"
+ "BasicBlock 3, pred: 2, 5, succ: 4\n"
+ " 22: Phi(3, 5) [15]\n"
+ " 15: Add(22, 3)\n"
+ " 17: ReturnVoid\n"
+ "BasicBlock 4, pred: 3\n"
+ " 18: Exit\n"
+ "BasicBlock 5, pred: 1, succ: 3\n"
+ " 21: Goto 3\n";
+
+ // Expected difference after constant propagation.
+ diff_t expected_cp_diff = {
+ { " 3: IntConstant [15, 22, 8]\n", " 3: IntConstant [15, 22]\n" },
+ { " 5: IntConstant [22, 8]\n", " 5: IntConstant [22]\n" },
+ { " 8: GreaterThanOrEqual(3, 5) [9]\n", " 23: IntConstant [9]\n" },
+ { " 9: If(8)\n", " 9: If(23)\n" }
+ };
+ std::string expected_after_cp = Patch(expected_before, expected_cp_diff);
+
+ // Expected difference after dead code elimination.
+ diff_t expected_dce_diff = {
+ { " 3: IntConstant [15, 22]\n", " 3: IntConstant [22]\n" },
+ { " 22: Phi(3, 5) [15]\n", " 22: Phi(3, 5)\n" },
+ { " 15: Add(22, 3)\n", removed }
+ };
+ std::string expected_after_dce = Patch(expected_after_cp, expected_dce_diff);
+
+ TestCode(data, expected_before, expected_after_cp, expected_after_dce);
+}
+
+} // namespace art
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 06a55e8..376d1af 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -510,6 +510,18 @@
}
}
+HConstant* HBinaryOperation::TryStaticEvaluation(ArenaAllocator* allocator) const {
+ if (GetLeft()->IsIntConstant() && GetRight()->IsIntConstant()) {
+ int32_t value = Evaluate(GetLeft()->AsIntConstant()->GetValue(),
+ GetRight()->AsIntConstant()->GetValue());
+ return new(allocator) HIntConstant(value);
+ } else if (GetLeft()->IsLongConstant() && GetRight()->IsLongConstant()) {
+ int64_t value = Evaluate(GetLeft()->AsLongConstant()->GetValue(),
+ GetRight()->AsLongConstant()->GetValue());
+ return new(allocator) HLongConstant(value);
+ }
+ return nullptr;
+}
bool HCondition::NeedsMaterialization() const {
if (!HasOnlyOneUse()) {
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index aae65ec..d98d2ad 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -1014,6 +1014,15 @@
virtual bool CanBeMoved() const { return true; }
virtual bool InstructionDataEquals(HInstruction* other) const { return true; }
+ // Try to statically evaluate `operation` and return an HConstant
+ // containing the result of this evaluation. If `operation` cannot
+ // be evaluated as a constant, return nullptr.
+ HConstant* TryStaticEvaluation(ArenaAllocator* allocator) const;
+
+ // Apply this operation to `x` and `y`.
+ virtual int32_t Evaluate(int32_t x, int32_t y) const = 0;
+ virtual int64_t Evaluate(int64_t x, int64_t y) const = 0;
+
DECLARE_INSTRUCTION(BinaryOperation);
private:
@@ -1042,6 +1051,9 @@
HEqual(HInstruction* first, HInstruction* second)
: HCondition(first, second) {}
+ virtual int32_t Evaluate(int32_t x, int32_t y) const { return x == y; }
+ virtual int64_t Evaluate(int64_t x, int64_t y) const { return x == y; }
+
DECLARE_INSTRUCTION(Equal);
virtual IfCondition GetCondition() const {
@@ -1057,6 +1069,9 @@
HNotEqual(HInstruction* first, HInstruction* second)
: HCondition(first, second) {}
+ virtual int32_t Evaluate(int32_t x, int32_t y) const { return x != y; }
+ virtual int64_t Evaluate(int64_t x, int64_t y) const { return x != y; }
+
DECLARE_INSTRUCTION(NotEqual);
virtual IfCondition GetCondition() const {
@@ -1072,6 +1087,9 @@
HLessThan(HInstruction* first, HInstruction* second)
: HCondition(first, second) {}
+ virtual int32_t Evaluate(int32_t x, int32_t y) const { return x < y; }
+ virtual int64_t Evaluate(int64_t x, int64_t y) const { return x < y; }
+
DECLARE_INSTRUCTION(LessThan);
virtual IfCondition GetCondition() const {
@@ -1087,6 +1105,9 @@
HLessThanOrEqual(HInstruction* first, HInstruction* second)
: HCondition(first, second) {}
+ virtual int32_t Evaluate(int32_t x, int32_t y) const { return x <= y; }
+ virtual int64_t Evaluate(int64_t x, int64_t y) const { return x <= y; }
+
DECLARE_INSTRUCTION(LessThanOrEqual);
virtual IfCondition GetCondition() const {
@@ -1102,6 +1123,9 @@
HGreaterThan(HInstruction* first, HInstruction* second)
: HCondition(first, second) {}
+ virtual int32_t Evaluate(int32_t x, int32_t y) const { return x > y; }
+ virtual int64_t Evaluate(int64_t x, int64_t y) const { return x > y; }
+
DECLARE_INSTRUCTION(GreaterThan);
virtual IfCondition GetCondition() const {
@@ -1117,6 +1141,9 @@
HGreaterThanOrEqual(HInstruction* first, HInstruction* second)
: HCondition(first, second) {}
+ virtual int32_t Evaluate(int32_t x, int32_t y) const { return x >= y; }
+ virtual int64_t Evaluate(int64_t x, int64_t y) const { return x >= y; }
+
DECLARE_INSTRUCTION(GreaterThanOrEqual);
virtual IfCondition GetCondition() const {
@@ -1138,6 +1165,19 @@
DCHECK_EQ(type, second->GetType());
}
+ virtual int32_t Evaluate(int32_t x, int32_t y) const {
+ return
+ x == y ? 0 :
+ x > y ? 1 :
+ -1;
+ }
+ virtual int64_t Evaluate(int64_t x, int64_t y) const {
+ return
+ x == y ? 0 :
+ x > y ? 1 :
+ -1;
+ }
+
DECLARE_INSTRUCTION(Compare);
private:
@@ -1354,6 +1394,9 @@
virtual bool IsCommutative() { return true; }
+ virtual int32_t Evaluate(int32_t x, int32_t y) const { return x + y; }
+ virtual int64_t Evaluate(int64_t x, int64_t y) const { return x + y; }
+
DECLARE_INSTRUCTION(Add);
private:
@@ -1367,6 +1410,9 @@
virtual bool IsCommutative() { return false; }
+ virtual int32_t Evaluate(int32_t x, int32_t y) const { return x + y; }
+ virtual int64_t Evaluate(int64_t x, int64_t y) const { return x + y; }
+
DECLARE_INSTRUCTION(Sub);
private: