| /* |
| * 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 "dead_code_elimination.h" |
| |
| #include "driver/compiler_options.h" |
| #include "graph_checker.h" |
| #include "optimizing_unit_test.h" |
| #include "pretty_printer.h" |
| |
| #include "gtest/gtest.h" |
| |
| namespace art { |
| |
| class DeadCodeEliminationTest : public OptimizingUnitTest { |
| protected: |
| void TestCode(const std::vector<uint16_t>& data, |
| const std::string& expected_before, |
| const std::string& expected_after); |
| }; |
| |
| void DeadCodeEliminationTest::TestCode(const std::vector<uint16_t>& data, |
| const std::string& expected_before, |
| const std::string& expected_after) { |
| HGraph* graph = CreateCFG(data); |
| ASSERT_NE(graph, nullptr); |
| |
| StringPrettyPrinter printer_before(graph); |
| printer_before.VisitInsertionOrder(); |
| std::string actual_before = printer_before.str(); |
| ASSERT_EQ(actual_before, expected_before); |
| |
| HDeadCodeElimination(graph, nullptr /* stats */, "dead_code_elimination").Run(); |
| GraphChecker graph_checker(graph); |
| graph_checker.Run(); |
| ASSERT_TRUE(graph_checker.IsValid()); |
| |
| StringPrettyPrinter printer_after(graph); |
| printer_after.VisitInsertionOrder(); |
| std::string actual_after = printer_after.str(); |
| ASSERT_EQ(actual_after, expected_after); |
| } |
| |
| /** |
| * Small three-register program. |
| * |
| * 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_F(DeadCodeEliminationTest, AdditionAndConditionalJump) { |
| const std::vector<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 [9, 8, 5]\n" |
| " 4: IntConstant [8, 5]\n" |
| " 1: SuspendCheck\n" |
| " 2: Goto 1\n" |
| "BasicBlock 1, pred: 0, succ: 5, 2\n" |
| " 5: GreaterThanOrEqual(3, 4) [6]\n" |
| " 6: If(5)\n" |
| "BasicBlock 2, pred: 1, succ: 3\n" |
| " 7: Goto 3\n" |
| "BasicBlock 3, pred: 5, 2, succ: 4\n" |
| " 8: Phi(4, 3) [9]\n" |
| " 9: Add(8, 3)\n" |
| " 10: ReturnVoid\n" |
| "BasicBlock 4, pred: 3\n" |
| " 11: Exit\n" |
| "BasicBlock 5, pred: 1, succ: 3\n" |
| " 0: Goto 3\n"; |
| |
| // Expected difference after dead code elimination. |
| diff_t expected_diff = { |
| { " 3: IntConstant [9, 8, 5]\n", " 3: IntConstant [8, 5]\n" }, |
| { " 8: Phi(4, 3) [9]\n", " 8: Phi(4, 3)\n" }, |
| { " 9: Add(8, 3)\n", removed } |
| }; |
| std::string expected_after = Patch(expected_before, expected_diff); |
| |
| TestCode(data, expected_before, expected_after); |
| } |
| |
| /** |
| * Three-register program with jumps leading to the creation of many |
| * blocks. |
| * |
| * The intent of this test is to ensure that all dead instructions are |
| * actually pruned at compile-time, thanks to the (backward) |
| * 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 13. return-void |
| */ |
| TEST_F(DeadCodeEliminationTest, AdditionsAndInconditionalJumps) { |
| const std::vector<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 | 0xFFFFFFFB << 8), |
| Instruction::ADD_INT_LIT16 | 2 << 8 | 1 << 12, 4, |
| Instruction::RETURN_VOID); |
| |
| std::string expected_before = |
| "BasicBlock 0, succ: 1\n" |
| " 2: IntConstant [4]\n" |
| " 3: IntConstant [4]\n" |
| " 6: IntConstant [7]\n" |
| " 9: IntConstant [10]\n" |
| " 12: IntConstant [13]\n" |
| " 0: SuspendCheck\n" |
| " 1: Goto 1\n" |
| "BasicBlock 1, pred: 0, succ: 3\n" |
| " 4: Add(2, 3) [7]\n" |
| " 5: Goto 3\n" |
| "BasicBlock 2, pred: 3, succ: 4\n" |
| " 10: Add(7, 9) [13]\n" |
| " 11: Goto 4\n" |
| "BasicBlock 3, pred: 1, succ: 2\n" |
| " 7: Add(4, 6) [10]\n" |
| " 8: Goto 2\n" |
| "BasicBlock 4, pred: 2, succ: 5\n" |
| " 13: Add(10, 12)\n" |
| " 14: ReturnVoid\n" |
| "BasicBlock 5, pred: 4\n" |
| " 15: Exit\n"; |
| |
| std::string expected_after = |
| "BasicBlock 0, succ: 1\n" |
| " 0: SuspendCheck\n" |
| " 1: Goto 1\n" |
| "BasicBlock 1, pred: 0, succ: 5\n" |
| " 14: ReturnVoid\n" |
| "BasicBlock 5, pred: 1\n" |
| " 15: Exit\n"; |
| |
| TestCode(data, expected_before, expected_after); |
| } |
| |
| } // namespace art |