1 /* 2 * Copyright (C) 2014 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #include "dead_code_elimination.h" 18 19 #include "arch/x86/instruction_set_features_x86.h" 20 #include "code_generator_x86.h" 21 #include "driver/compiler_options.h" 22 #include "graph_checker.h" 23 #include "optimizing_unit_test.h" 24 #include "pretty_printer.h" 25 26 #include "gtest/gtest.h" 27 28 namespace art { 29 30 class DeadCodeEliminationTest : public OptimizingUnitTest { 31 protected: 32 void TestCode(const std::vector<uint16_t>& data, 33 const std::string& expected_before, 34 const std::string& expected_after); 35 }; 36 37 void DeadCodeEliminationTest::TestCode(const std::vector<uint16_t>& data, 38 const std::string& expected_before, 39 const std::string& expected_after) { 40 HGraph* graph = CreateCFG(data); 41 ASSERT_NE(graph, nullptr); 42 43 StringPrettyPrinter printer_before(graph); 44 printer_before.VisitInsertionOrder(); 45 std::string actual_before = printer_before.str(); 46 ASSERT_EQ(actual_before, expected_before); 47 48 std::unique_ptr<const X86InstructionSetFeatures> features_x86( 49 X86InstructionSetFeatures::FromCppDefines()); 50 x86::CodeGeneratorX86 codegenX86(graph, *features_x86.get(), CompilerOptions()); 51 HDeadCodeElimination(graph, nullptr /* stats */, "dead_code_elimination").Run(); 52 GraphChecker graph_checker(graph); 53 graph_checker.Run(); 54 ASSERT_TRUE(graph_checker.IsValid()); 55 56 StringPrettyPrinter printer_after(graph); 57 printer_after.VisitInsertionOrder(); 58 std::string actual_after = printer_after.str(); 59 ASSERT_EQ(actual_after, expected_after); 60 } 61 62 /** 63 * Small three-register program. 64 * 65 * 16-bit 66 * offset 67 * ------ 68 * v1 <- 1 0. const/4 v1, #+1 69 * v0 <- 0 1. const/4 v0, #+0 70 * if v1 >= 0 goto L1 2. if-gez v1, +3 71 * v0 <- v1 4. move v0, v1 72 * L1: v2 <- v0 + v1 5. add-int v2, v0, v1 73 * return-void 7. return 74 */ 75 TEST_F(DeadCodeEliminationTest, AdditionAndConditionalJump) { 76 const std::vector<uint16_t> data = THREE_REGISTERS_CODE_ITEM( 77 Instruction::CONST_4 | 1 << 8 | 1 << 12, 78 Instruction::CONST_4 | 0 << 8 | 0 << 12, 79 Instruction::IF_GEZ | 1 << 8, 3, 80 Instruction::MOVE | 0 << 8 | 1 << 12, 81 Instruction::ADD_INT | 2 << 8, 0 | 1 << 8, 82 Instruction::RETURN_VOID); 83 84 std::string expected_before = 85 "BasicBlock 0, succ: 1\n" 86 " 3: IntConstant [9, 8, 5]\n" 87 " 4: IntConstant [8, 5]\n" 88 " 1: SuspendCheck\n" 89 " 2: Goto 1\n" 90 "BasicBlock 1, pred: 0, succ: 5, 2\n" 91 " 5: GreaterThanOrEqual(3, 4) [6]\n" 92 " 6: If(5)\n" 93 "BasicBlock 2, pred: 1, succ: 3\n" 94 " 7: Goto 3\n" 95 "BasicBlock 3, pred: 5, 2, succ: 4\n" 96 " 8: Phi(4, 3) [9]\n" 97 " 9: Add(8, 3)\n" 98 " 10: ReturnVoid\n" 99 "BasicBlock 4, pred: 3\n" 100 " 11: Exit\n" 101 "BasicBlock 5, pred: 1, succ: 3\n" 102 " 0: Goto 3\n"; 103 104 // Expected difference after dead code elimination. 105 diff_t expected_diff = { 106 { " 3: IntConstant [9, 8, 5]\n", " 3: IntConstant [8, 5]\n" }, 107 { " 8: Phi(4, 3) [9]\n", " 8: Phi(4, 3)\n" }, 108 { " 9: Add(8, 3)\n", removed } 109 }; 110 std::string expected_after = Patch(expected_before, expected_diff); 111 112 TestCode(data, expected_before, expected_after); 113 } 114 115 /** 116 * Three-register program with jumps leading to the creation of many 117 * blocks. 118 * 119 * The intent of this test is to ensure that all dead instructions are 120 * actually pruned at compile-time, thanks to the (backward) 121 * post-order traversal of the the dominator tree. 122 * 123 * 16-bit 124 * offset 125 * ------ 126 * v0 <- 0 0. const/4 v0, #+0 127 * v1 <- 1 1. const/4 v1, #+1 128 * v2 <- v0 + v1 2. add-int v2, v0, v1 129 * goto L2 4. goto +4 130 * L1: v1 <- v0 + 3 5. add-int/lit16 v1, v0, #+3 131 * goto L3 7. goto +4 132 * L2: v0 <- v2 + 2 8. add-int/lit16 v0, v2, #+2 133 * goto L1 10. goto +(-5) 134 * L3: v2 <- v1 + 4 11. add-int/lit16 v2, v1, #+4 135 * return 13. return-void 136 */ 137 TEST_F(DeadCodeEliminationTest, AdditionsAndInconditionalJumps) { 138 const std::vector<uint16_t> data = THREE_REGISTERS_CODE_ITEM( 139 Instruction::CONST_4 | 0 << 8 | 0 << 12, 140 Instruction::CONST_4 | 1 << 8 | 1 << 12, 141 Instruction::ADD_INT | 2 << 8, 0 | 1 << 8, 142 Instruction::GOTO | 4 << 8, 143 Instruction::ADD_INT_LIT16 | 1 << 8 | 0 << 12, 3, 144 Instruction::GOTO | 4 << 8, 145 Instruction::ADD_INT_LIT16 | 0 << 8 | 2 << 12, 2, 146 static_cast<uint16_t>(Instruction::GOTO | 0xFFFFFFFB << 8), 147 Instruction::ADD_INT_LIT16 | 2 << 8 | 1 << 12, 4, 148 Instruction::RETURN_VOID); 149 150 std::string expected_before = 151 "BasicBlock 0, succ: 1\n" 152 " 2: IntConstant [4]\n" 153 " 3: IntConstant [4]\n" 154 " 6: IntConstant [7]\n" 155 " 9: IntConstant [10]\n" 156 " 12: IntConstant [13]\n" 157 " 0: SuspendCheck\n" 158 " 1: Goto 1\n" 159 "BasicBlock 1, pred: 0, succ: 3\n" 160 " 4: Add(2, 3) [7]\n" 161 " 5: Goto 3\n" 162 "BasicBlock 2, pred: 3, succ: 4\n" 163 " 10: Add(7, 9) [13]\n" 164 " 11: Goto 4\n" 165 "BasicBlock 3, pred: 1, succ: 2\n" 166 " 7: Add(4, 6) [10]\n" 167 " 8: Goto 2\n" 168 "BasicBlock 4, pred: 2, succ: 5\n" 169 " 13: Add(10, 12)\n" 170 " 14: ReturnVoid\n" 171 "BasicBlock 5, pred: 4\n" 172 " 15: Exit\n"; 173 174 std::string expected_after = 175 "BasicBlock 0, succ: 1\n" 176 " 0: SuspendCheck\n" 177 " 1: Goto 1\n" 178 "BasicBlock 1, pred: 0, succ: 5\n" 179 " 14: ReturnVoid\n" 180 "BasicBlock 5, pred: 1\n" 181 " 15: Exit\n"; 182 183 TestCode(data, expected_before, expected_after); 184 } 185 186 } // namespace art 187
