From 1ddbf6d4b37979a9f11a203c12befd5ae8b65df4 Mon Sep 17 00:00:00 2001 From: Nicolas Geoffray Date: Wed, 1 Oct 2014 14:59:23 +0000 Subject: Revert "Introduce a class to implement optimization passes." This reverts commit bf9cd7ba2118a75f5aa9b56241c4d5fa00dedeb8. Change-Id: I0a483446666c9c24c45925a5fc199debdefd8b3e --- compiler/optimizing/constant_folding.cc | 47 --- compiler/optimizing/constant_folding.h | 48 --- compiler/optimizing/constant_folding_test.cc | 491 ---------------------- compiler/optimizing/constant_propagation.cc | 47 +++ compiler/optimizing/constant_propagation.h | 43 ++ compiler/optimizing/constant_propagation_test.cc | 487 +++++++++++++++++++++ compiler/optimizing/dead_code_elimination.cc | 2 +- compiler/optimizing/dead_code_elimination.h | 16 +- compiler/optimizing/dead_code_elimination_test.cc | 17 +- compiler/optimizing/graph_checker.h | 20 +- compiler/optimizing/graph_visualizer.cc | 2 +- compiler/optimizing/graph_visualizer.h | 2 +- compiler/optimizing/optimization.cc | 41 -- compiler/optimizing/optimization.h | 79 ---- compiler/optimizing/optimizing_compiler.cc | 5 - 15 files changed, 597 insertions(+), 750 deletions(-) delete mode 100644 compiler/optimizing/constant_folding.cc delete mode 100644 compiler/optimizing/constant_folding.h delete mode 100644 compiler/optimizing/constant_folding_test.cc create mode 100644 compiler/optimizing/constant_propagation.cc create mode 100644 compiler/optimizing/constant_propagation.h create mode 100644 compiler/optimizing/constant_propagation_test.cc delete mode 100644 compiler/optimizing/optimization.cc delete mode 100644 compiler/optimizing/optimization.h (limited to 'compiler/optimizing') diff --git a/compiler/optimizing/constant_folding.cc b/compiler/optimizing/constant_folding.cc deleted file mode 100644 index 0b3ad9809f..0000000000 --- a/compiler/optimizing/constant_folding.cc +++ /dev/null @@ -1,47 +0,0 @@ -/* - * 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_folding.h" - -namespace art { - -void HConstantFolding::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_folding.h b/compiler/optimizing/constant_folding.h deleted file mode 100644 index d2acfa6973..0000000000 --- a/compiler/optimizing/constant_folding.h +++ /dev/null @@ -1,48 +0,0 @@ -/* - * 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_FOLDING_H_ -#define ART_COMPILER_OPTIMIZING_CONSTANT_FOLDING_H_ - -#include "nodes.h" -#include "optimization.h" - -namespace art { - -/** - * Optimization pass performing a simple constant-expression - * evaluation on the SSA form. - * - * This class is named art::HConstantFolding to avoid name - * clashes with the art::ConstantPropagation class defined in - * compiler/dex/post_opt_passes.h. - */ -class HConstantFolding : public HOptimization { - public: - HConstantFolding(HGraph* graph, const HGraphVisualizer& visualizer) - : HOptimization(graph, true, kConstantFoldingPassName, visualizer) {} - - virtual void Run() OVERRIDE; - - static constexpr const char* kConstantFoldingPassName = "constant_folding"; - - private: - DISALLOW_COPY_AND_ASSIGN(HConstantFolding); -}; - -} // namespace art - -#endif // ART_COMPILER_OPTIMIZING_CONSTANT_FOLDING_H_ diff --git a/compiler/optimizing/constant_folding_test.cc b/compiler/optimizing/constant_folding_test.cc deleted file mode 100644 index 9f2041dfc5..0000000000 --- a/compiler/optimizing/constant_folding_test.cc +++ /dev/null @@ -1,491 +0,0 @@ -/* - * 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 "code_generator_x86.h" -#include "constant_folding.h" -#include "dead_code_elimination.h" -#include "graph_checker.h" -#include "optimizing_unit_test.h" -#include "pretty_printer.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); - - x86::CodeGeneratorX86 codegen(graph); - HGraphVisualizer visualizer(nullptr, graph, codegen, ""); - HConstantFolding(graph, visualizer).Run(); - SSAChecker ssa_checker(&allocator, graph); - ssa_checker.VisitInsertionOrder(); - ASSERT_TRUE(ssa_checker.IsValid()); - - 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); - - HDeadCodeElimination(graph, visualizer).Run(); - ssa_checker.VisitInsertionOrder(); - ASSERT_TRUE(ssa_checker.IsValid()); - - 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); -} - - -/** - * 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(ConstantFolding, 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 folding. - 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(ConstantFolding, 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 folding. - 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(ConstantFolding, 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 folding. - 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(ConstantFolding, 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 folding. - 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(ConstantFolding, 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 folding. - 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(ConstantFolding, 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(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 folding. - 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(ConstantFolding, 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 folding. - 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/constant_propagation.cc b/compiler/optimizing/constant_propagation.cc new file mode 100644 index 0000000000..d675164fa4 --- /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 0000000000..0729881888 --- /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 0000000000..5c8c709439 --- /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(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/dead_code_elimination.cc b/compiler/optimizing/dead_code_elimination.cc index 55188510f0..fe2adc77d0 100644 --- a/compiler/optimizing/dead_code_elimination.cc +++ b/compiler/optimizing/dead_code_elimination.cc @@ -20,7 +20,7 @@ namespace art { -void HDeadCodeElimination::Run() { +void DeadCodeElimination::Run() { // Process basic blocks in post-order in the dominator tree, so that // a dead instruction depending on another dead instruction is // removed. diff --git a/compiler/optimizing/dead_code_elimination.h b/compiler/optimizing/dead_code_elimination.h index a4446ae04d..48739be494 100644 --- a/compiler/optimizing/dead_code_elimination.h +++ b/compiler/optimizing/dead_code_elimination.h @@ -18,7 +18,6 @@ #define ART_COMPILER_OPTIMIZING_DEAD_CODE_ELIMINATION_H_ #include "nodes.h" -#include "optimization.h" namespace art { @@ -26,18 +25,17 @@ namespace art { * Optimization pass performing dead code elimination (removal of * unused variables/instructions) on the SSA form. */ -class HDeadCodeElimination : public HOptimization { +class DeadCodeElimination : public ValueObject { public: - HDeadCodeElimination(HGraph* graph, const HGraphVisualizer& visualizer) - : HOptimization(graph, true, kDeadCodeEliminationPassName, visualizer) {} + explicit DeadCodeElimination(HGraph* graph) + : graph_(graph) {} - virtual void Run() OVERRIDE; - - static constexpr const char* kDeadCodeEliminationPassName = - "dead_code_elimination"; + void Run(); private: - DISALLOW_COPY_AND_ASSIGN(HDeadCodeElimination); + HGraph* const graph_; + + DISALLOW_COPY_AND_ASSIGN(DeadCodeElimination); }; } // namespace art diff --git a/compiler/optimizing/dead_code_elimination_test.cc b/compiler/optimizing/dead_code_elimination_test.cc index 25e9555435..245bcb21d5 100644 --- a/compiler/optimizing/dead_code_elimination_test.cc +++ b/compiler/optimizing/dead_code_elimination_test.cc @@ -14,11 +14,10 @@ * limitations under the License. */ -#include "code_generator_x86.h" #include "dead_code_elimination.h" +#include "pretty_printer.h" #include "graph_checker.h" #include "optimizing_unit_test.h" -#include "pretty_printer.h" #include "gtest/gtest.h" @@ -40,17 +39,16 @@ static void TestCode(const uint16_t* data, std::string actual_before = printer_before.str(); ASSERT_EQ(actual_before, expected_before); - x86::CodeGeneratorX86 codegen(graph); - HGraphVisualizer visualizer(nullptr, graph, codegen, ""); - HDeadCodeElimination(graph, visualizer).Run(); - SSAChecker ssa_checker(&allocator, graph); - ssa_checker.VisitInsertionOrder(); - ASSERT_TRUE(ssa_checker.IsValid()); + DeadCodeElimination(graph).Run(); StringPrettyPrinter printer_after(graph); printer_after.VisitInsertionOrder(); std::string actual_after = printer_after.str(); ASSERT_EQ(actual_after, expected_after); + + SSAChecker ssa_checker(&allocator, graph); + ssa_checker.VisitInsertionOrder(); + ASSERT_TRUE(ssa_checker.IsValid()); } @@ -96,7 +94,6 @@ TEST(DeadCodeElimination, AdditionAndConditionalJump) { "BasicBlock 5, pred: 1, succ: 3\n" " 21: Goto 3\n"; - // Expected difference after dead code elimination. diff_t expected_diff = { { " 3: IntConstant [15, 22, 8]\n", " 3: IntConstant [22, 8]\n" }, { " 22: Phi(3, 5) [15]\n", " 22: Phi(3, 5)\n" }, @@ -167,7 +164,7 @@ TEST(DeadCodeElimination, AdditionsAndInconditionalJumps) { "BasicBlock 5, pred: 4\n" " 28: Exit\n"; - // Expected difference after dead code elimination. + // Expected difference after constant propagation. diff_t expected_diff = { { " 13: IntConstant [14]\n", removed }, { " 24: IntConstant [25]\n", removed }, diff --git a/compiler/optimizing/graph_checker.h b/compiler/optimizing/graph_checker.h index 4fb07e0ae4..34a770b5f3 100644 --- a/compiler/optimizing/graph_checker.h +++ b/compiler/optimizing/graph_checker.h @@ -19,19 +19,15 @@ #include "nodes.h" -#include - namespace art { // A control-flow graph visitor performing various checks. class GraphChecker : public HGraphVisitor { public: - GraphChecker(ArenaAllocator* allocator, HGraph* graph, - const char* dump_prefix = "art::GraphChecker: ") + GraphChecker(ArenaAllocator* allocator, HGraph* graph) : HGraphVisitor(graph), allocator_(allocator), - errors_(allocator, 0), - dump_prefix_(dump_prefix) {} + errors_(allocator, 0) {} // Check `block`. virtual void VisitBasicBlock(HBasicBlock* block) OVERRIDE; @@ -49,13 +45,6 @@ class GraphChecker : public HGraphVisitor { return errors_; } - // Print detected errors on output stream `os`. - void Dump(std::ostream& os) { - for (size_t i = 0, e = errors_.Size(); i < e; ++i) { - os << dump_prefix_ << errors_.Get(i) << std::endl; - } - } - protected: ArenaAllocator* const allocator_; // The block currently visited. @@ -64,9 +53,6 @@ class GraphChecker : public HGraphVisitor { GrowableArray errors_; private: - // String displayed before dumped errors. - const char* dump_prefix_; - DISALLOW_COPY_AND_ASSIGN(GraphChecker); }; @@ -77,7 +63,7 @@ class SSAChecker : public GraphChecker { typedef GraphChecker super_type; SSAChecker(ArenaAllocator* allocator, HGraph* graph) - : GraphChecker(allocator, graph, "art::SSAChecker: ") {} + : GraphChecker(allocator, graph) {} // Perform SSA form checks on `block`. virtual void VisitBasicBlock(HBasicBlock* block) OVERRIDE; diff --git a/compiler/optimizing/graph_visualizer.cc b/compiler/optimizing/graph_visualizer.cc index fabae21788..0fb4737db2 100644 --- a/compiler/optimizing/graph_visualizer.cc +++ b/compiler/optimizing/graph_visualizer.cc @@ -307,7 +307,7 @@ HGraphVisualizer::HGraphVisualizer(std::ostream* output, printer.EndTag("compilation"); } -void HGraphVisualizer::DumpGraph(const char* pass_name) const { +void HGraphVisualizer::DumpGraph(const char* pass_name) { if (!is_enabled_) { return; } diff --git a/compiler/optimizing/graph_visualizer.h b/compiler/optimizing/graph_visualizer.h index e45bba367b..6e2c6fd11f 100644 --- a/compiler/optimizing/graph_visualizer.h +++ b/compiler/optimizing/graph_visualizer.h @@ -61,7 +61,7 @@ class HGraphVisualizer : public ValueObject { * If this visualizer is enabled, emit the compilation information * in `output_`. */ - void DumpGraph(const char* pass_name) const; + void DumpGraph(const char* pass_name); private: std::ostream* const output_; diff --git a/compiler/optimizing/optimization.cc b/compiler/optimizing/optimization.cc deleted file mode 100644 index 7263691f5e..0000000000 --- a/compiler/optimizing/optimization.cc +++ /dev/null @@ -1,41 +0,0 @@ -/* - * 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 "optimization.h" - -#include "graph_checker.h" - -namespace art { - -void HOptimization::Execute() { - Run(); - visualizer_.DumpGraph(pass_name_); - Check(); -} - -void HOptimization::Check() { - if (kIsDebugBuild) { - if (is_in_ssa_form_) { - SSAChecker checker(graph_->GetArena(), graph_); - CheckInternal(&checker); - } else { - GraphChecker checker(graph_->GetArena(), graph_); - CheckInternal(&checker); - } - } -} - -} // namespace art diff --git a/compiler/optimizing/optimization.h b/compiler/optimizing/optimization.h deleted file mode 100644 index 1ad0d303e5..0000000000 --- a/compiler/optimizing/optimization.h +++ /dev/null @@ -1,79 +0,0 @@ -/* - * 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_OPTIMIZATION_H_ -#define ART_COMPILER_OPTIMIZING_OPTIMIZATION_H_ - -#include "graph_visualizer.h" -#include "nodes.h" - -namespace art { - -/** - * Abstraction to implement an optimization pass. - */ -class HOptimization : public ValueObject { - public: - HOptimization(HGraph* graph, - bool is_in_ssa_form, - const char* pass_name, - const HGraphVisualizer& visualizer) - : graph_(graph), - is_in_ssa_form_(is_in_ssa_form), - pass_name_(pass_name), - visualizer_(visualizer) {} - - virtual ~HOptimization() {} - - // Execute the optimization pass. - void Execute(); - - // Return the name of the pass. - const char* GetPassName() const { return pass_name_; } - - // Peform the analysis itself. - virtual void Run() = 0; - - private: - // Verify the graph; abort if it is not valid. - void Check(); - - template - void CheckInternal(T* checker) { - checker->VisitInsertionOrder(); - if (!checker->IsValid()) { - LOG(FATAL) << Dumpable(*checker); - } - } - - protected: - HGraph* const graph_; - - private: - // Does the analyzed graph use SSA form? - bool is_in_ssa_form_; - // Optimization pass name. - const char* pass_name_; - // A graph visualiser invoked during the execution of the - // optimization pass if non null. - const HGraphVisualizer& visualizer_; - - DISALLOW_COPY_AND_ASSIGN(HOptimization); -}; - -} // namespace art - -#endif // ART_COMPILER_OPTIMIZING_OPTIMIZATION_H_ diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc index ee5091bbb5..65bdb18812 100644 --- a/compiler/optimizing/optimizing_compiler.cc +++ b/compiler/optimizing/optimizing_compiler.cc @@ -22,8 +22,6 @@ #include "builder.h" #include "code_generator.h" #include "compiler.h" -#include "constant_folding.h" -#include "dead_code_elimination.h" #include "driver/compiler_driver.h" #include "driver/dex_compilation_unit.h" #include "graph_visualizer.h" @@ -262,9 +260,6 @@ CompiledMethod* OptimizingCompiler::TryCompile(const DexFile::CodeItem* code_ite visualizer.DumpGraph("ssa"); graph->FindNaturalLoops(); - HDeadCodeElimination(graph, visualizer).Execute(); - HConstantFolding(graph, visualizer).Execute(); - SsaRedundantPhiElimination(graph).Run(); SsaDeadPhiElimination(graph).Run(); InstructionSimplifier(graph).Run(); -- cgit v1.2.3