Roland Levillain | 72bceff | 2014-09-15 18:29:00 +0100 | [diff] [blame] | 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 | |
Mark Mendell | fb8d279 | 2015-03-31 22:16:59 -0400 | [diff] [blame] | 17 | #include "arch/x86/instruction_set_features_x86.h" |
Roland Levillain | 75be283 | 2014-10-17 17:02:00 +0100 | [diff] [blame] | 18 | #include "code_generator_x86.h" |
Roland Levillain | 72bceff | 2014-09-15 18:29:00 +0100 | [diff] [blame] | 19 | #include "dead_code_elimination.h" |
Calin Juravle | cd6dffe | 2015-01-08 17:35:35 +0000 | [diff] [blame] | 20 | #include "driver/compiler_options.h" |
Roland Levillain | 72bceff | 2014-09-15 18:29:00 +0100 | [diff] [blame] | 21 | #include "graph_checker.h" |
| 22 | #include "optimizing_unit_test.h" |
Roland Levillain | 75be283 | 2014-10-17 17:02:00 +0100 | [diff] [blame] | 23 | #include "pretty_printer.h" |
Roland Levillain | 72bceff | 2014-09-15 18:29:00 +0100 | [diff] [blame] | 24 | |
| 25 | #include "gtest/gtest.h" |
| 26 | |
| 27 | namespace art { |
| 28 | |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 29 | class DeadCodeEliminationTest : public CommonCompilerTest {}; |
| 30 | |
Roland Levillain | 72bceff | 2014-09-15 18:29:00 +0100 | [diff] [blame] | 31 | static void TestCode(const uint16_t* data, |
| 32 | const std::string& expected_before, |
| 33 | const std::string& expected_after) { |
| 34 | ArenaPool pool; |
| 35 | ArenaAllocator allocator(&pool); |
| 36 | HGraph* graph = CreateCFG(&allocator, data); |
| 37 | ASSERT_NE(graph, nullptr); |
| 38 | |
Roland Levillain | 72bceff | 2014-09-15 18:29:00 +0100 | [diff] [blame] | 39 | StringPrettyPrinter printer_before(graph); |
| 40 | printer_before.VisitInsertionOrder(); |
| 41 | std::string actual_before = printer_before.str(); |
| 42 | ASSERT_EQ(actual_before, expected_before); |
| 43 | |
Mark Mendell | fb8d279 | 2015-03-31 22:16:59 -0400 | [diff] [blame] | 44 | std::unique_ptr<const X86InstructionSetFeatures> features_x86( |
| 45 | X86InstructionSetFeatures::FromCppDefines()); |
| 46 | x86::CodeGeneratorX86 codegenX86(graph, *features_x86.get(), CompilerOptions()); |
Andreas Gampe | ca620d7 | 2016-11-08 08:09:33 -0800 | [diff] [blame^] | 47 | HDeadCodeElimination(graph, nullptr /* stats */, "dead_code_elimination").Run(); |
David Brazdil | badd826 | 2016-02-02 16:28:56 +0000 | [diff] [blame] | 48 | GraphChecker graph_checker(graph); |
| 49 | graph_checker.Run(); |
| 50 | ASSERT_TRUE(graph_checker.IsValid()); |
Roland Levillain | 72bceff | 2014-09-15 18:29:00 +0100 | [diff] [blame] | 51 | |
| 52 | StringPrettyPrinter printer_after(graph); |
| 53 | printer_after.VisitInsertionOrder(); |
| 54 | std::string actual_after = printer_after.str(); |
| 55 | ASSERT_EQ(actual_after, expected_after); |
Roland Levillain | 72bceff | 2014-09-15 18:29:00 +0100 | [diff] [blame] | 56 | } |
| 57 | |
Roland Levillain | 72bceff | 2014-09-15 18:29:00 +0100 | [diff] [blame] | 58 | /** |
| 59 | * Small three-register program. |
| 60 | * |
| 61 | * 16-bit |
| 62 | * offset |
| 63 | * ------ |
| 64 | * v1 <- 1 0. const/4 v1, #+1 |
| 65 | * v0 <- 0 1. const/4 v0, #+0 |
| 66 | * if v1 >= 0 goto L1 2. if-gez v1, +3 |
| 67 | * v0 <- v1 4. move v0, v1 |
| 68 | * L1: v2 <- v0 + v1 5. add-int v2, v0, v1 |
| 69 | * return-void 7. return |
| 70 | */ |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 71 | TEST_F(DeadCodeEliminationTest, AdditionAndConditionalJump) { |
Roland Levillain | 72bceff | 2014-09-15 18:29:00 +0100 | [diff] [blame] | 72 | const uint16_t data[] = THREE_REGISTERS_CODE_ITEM( |
| 73 | Instruction::CONST_4 | 1 << 8 | 1 << 12, |
| 74 | Instruction::CONST_4 | 0 << 8 | 0 << 12, |
| 75 | Instruction::IF_GEZ | 1 << 8, 3, |
| 76 | Instruction::MOVE | 0 << 8 | 1 << 12, |
| 77 | Instruction::ADD_INT | 2 << 8, 0 | 1 << 8, |
| 78 | Instruction::RETURN_VOID); |
| 79 | |
| 80 | std::string expected_before = |
David Brazdil | 86ea7ee | 2016-02-16 09:26:07 +0000 | [diff] [blame] | 81 | "BasicBlock 0, succ: 1\n" |
David Brazdil | dee58d6 | 2016-04-07 09:54:26 +0000 | [diff] [blame] | 82 | " 3: IntConstant [9, 8, 5]\n" |
| 83 | " 4: IntConstant [8, 5]\n" |
| 84 | " 1: SuspendCheck\n" |
| 85 | " 2: Goto 1\n" |
David Brazdil | 86ea7ee | 2016-02-16 09:26:07 +0000 | [diff] [blame] | 86 | "BasicBlock 1, pred: 0, succ: 5, 2\n" |
David Brazdil | dee58d6 | 2016-04-07 09:54:26 +0000 | [diff] [blame] | 87 | " 5: GreaterThanOrEqual(3, 4) [6]\n" |
| 88 | " 6: If(5)\n" |
David Brazdil | 86ea7ee | 2016-02-16 09:26:07 +0000 | [diff] [blame] | 89 | "BasicBlock 2, pred: 1, succ: 3\n" |
David Brazdil | dee58d6 | 2016-04-07 09:54:26 +0000 | [diff] [blame] | 90 | " 7: Goto 3\n" |
David Brazdil | 86ea7ee | 2016-02-16 09:26:07 +0000 | [diff] [blame] | 91 | "BasicBlock 3, pred: 5, 2, succ: 4\n" |
David Brazdil | dee58d6 | 2016-04-07 09:54:26 +0000 | [diff] [blame] | 92 | " 8: Phi(4, 3) [9]\n" |
| 93 | " 9: Add(8, 3)\n" |
| 94 | " 10: ReturnVoid\n" |
David Brazdil | 86ea7ee | 2016-02-16 09:26:07 +0000 | [diff] [blame] | 95 | "BasicBlock 4, pred: 3\n" |
David Brazdil | dee58d6 | 2016-04-07 09:54:26 +0000 | [diff] [blame] | 96 | " 11: Exit\n" |
David Brazdil | 86ea7ee | 2016-02-16 09:26:07 +0000 | [diff] [blame] | 97 | "BasicBlock 5, pred: 1, succ: 3\n" |
| 98 | " 0: Goto 3\n"; |
Roland Levillain | 72bceff | 2014-09-15 18:29:00 +0100 | [diff] [blame] | 99 | |
Roland Levillain | 75be283 | 2014-10-17 17:02:00 +0100 | [diff] [blame] | 100 | // Expected difference after dead code elimination. |
Roland Levillain | 72bceff | 2014-09-15 18:29:00 +0100 | [diff] [blame] | 101 | diff_t expected_diff = { |
David Brazdil | dee58d6 | 2016-04-07 09:54:26 +0000 | [diff] [blame] | 102 | { " 3: IntConstant [9, 8, 5]\n", " 3: IntConstant [8, 5]\n" }, |
| 103 | { " 8: Phi(4, 3) [9]\n", " 8: Phi(4, 3)\n" }, |
| 104 | { " 9: Add(8, 3)\n", removed } |
Roland Levillain | 72bceff | 2014-09-15 18:29:00 +0100 | [diff] [blame] | 105 | }; |
| 106 | std::string expected_after = Patch(expected_before, expected_diff); |
| 107 | |
| 108 | TestCode(data, expected_before, expected_after); |
| 109 | } |
| 110 | |
| 111 | /** |
| 112 | * Three-register program with jumps leading to the creation of many |
| 113 | * blocks. |
| 114 | * |
| 115 | * The intent of this test is to ensure that all dead instructions are |
| 116 | * actually pruned at compile-time, thanks to the (backward) |
| 117 | * post-order traversal of the the dominator tree. |
| 118 | * |
| 119 | * 16-bit |
| 120 | * offset |
| 121 | * ------ |
| 122 | * v0 <- 0 0. const/4 v0, #+0 |
| 123 | * v1 <- 1 1. const/4 v1, #+1 |
| 124 | * v2 <- v0 + v1 2. add-int v2, v0, v1 |
| 125 | * goto L2 4. goto +4 |
| 126 | * L1: v1 <- v0 + 3 5. add-int/lit16 v1, v0, #+3 |
| 127 | * goto L3 7. goto +4 |
| 128 | * L2: v0 <- v2 + 2 8. add-int/lit16 v0, v2, #+2 |
| 129 | * goto L1 10. goto +(-5) |
| 130 | * L3: v2 <- v1 + 4 11. add-int/lit16 v2, v1, #+4 |
| 131 | * return 13. return-void |
| 132 | */ |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 133 | TEST_F(DeadCodeEliminationTest, AdditionsAndInconditionalJumps) { |
Roland Levillain | 72bceff | 2014-09-15 18:29:00 +0100 | [diff] [blame] | 134 | const uint16_t data[] = THREE_REGISTERS_CODE_ITEM( |
| 135 | Instruction::CONST_4 | 0 << 8 | 0 << 12, |
| 136 | Instruction::CONST_4 | 1 << 8 | 1 << 12, |
| 137 | Instruction::ADD_INT | 2 << 8, 0 | 1 << 8, |
| 138 | Instruction::GOTO | 4 << 8, |
| 139 | Instruction::ADD_INT_LIT16 | 1 << 8 | 0 << 12, 3, |
| 140 | Instruction::GOTO | 4 << 8, |
| 141 | Instruction::ADD_INT_LIT16 | 0 << 8 | 2 << 12, 2, |
Andreas Gampe | 58554b7 | 2015-10-20 21:08:52 -0700 | [diff] [blame] | 142 | static_cast<uint16_t>(Instruction::GOTO | 0xFFFFFFFB << 8), |
Roland Levillain | 72bceff | 2014-09-15 18:29:00 +0100 | [diff] [blame] | 143 | Instruction::ADD_INT_LIT16 | 2 << 8 | 1 << 12, 4, |
| 144 | Instruction::RETURN_VOID); |
| 145 | |
| 146 | std::string expected_before = |
David Brazdil | 86ea7ee | 2016-02-16 09:26:07 +0000 | [diff] [blame] | 147 | "BasicBlock 0, succ: 1\n" |
David Brazdil | dee58d6 | 2016-04-07 09:54:26 +0000 | [diff] [blame] | 148 | " 2: IntConstant [4]\n" |
| 149 | " 3: IntConstant [4]\n" |
| 150 | " 6: IntConstant [7]\n" |
| 151 | " 9: IntConstant [10]\n" |
| 152 | " 12: IntConstant [13]\n" |
| 153 | " 0: SuspendCheck\n" |
| 154 | " 1: Goto 1\n" |
David Brazdil | 86ea7ee | 2016-02-16 09:26:07 +0000 | [diff] [blame] | 155 | "BasicBlock 1, pred: 0, succ: 3\n" |
David Brazdil | dee58d6 | 2016-04-07 09:54:26 +0000 | [diff] [blame] | 156 | " 4: Add(2, 3) [7]\n" |
| 157 | " 5: Goto 3\n" |
David Brazdil | 86ea7ee | 2016-02-16 09:26:07 +0000 | [diff] [blame] | 158 | "BasicBlock 2, pred: 3, succ: 4\n" |
David Brazdil | dee58d6 | 2016-04-07 09:54:26 +0000 | [diff] [blame] | 159 | " 10: Add(7, 9) [13]\n" |
| 160 | " 11: Goto 4\n" |
David Brazdil | 86ea7ee | 2016-02-16 09:26:07 +0000 | [diff] [blame] | 161 | "BasicBlock 3, pred: 1, succ: 2\n" |
David Brazdil | dee58d6 | 2016-04-07 09:54:26 +0000 | [diff] [blame] | 162 | " 7: Add(4, 6) [10]\n" |
| 163 | " 8: Goto 2\n" |
David Brazdil | 86ea7ee | 2016-02-16 09:26:07 +0000 | [diff] [blame] | 164 | "BasicBlock 4, pred: 2, succ: 5\n" |
David Brazdil | dee58d6 | 2016-04-07 09:54:26 +0000 | [diff] [blame] | 165 | " 13: Add(10, 12)\n" |
| 166 | " 14: ReturnVoid\n" |
David Brazdil | 86ea7ee | 2016-02-16 09:26:07 +0000 | [diff] [blame] | 167 | "BasicBlock 5, pred: 4\n" |
David Brazdil | dee58d6 | 2016-04-07 09:54:26 +0000 | [diff] [blame] | 168 | " 15: Exit\n"; |
Roland Levillain | 72bceff | 2014-09-15 18:29:00 +0100 | [diff] [blame] | 169 | |
David Brazdil | 1c533c1 | 2015-04-24 17:04:38 +0100 | [diff] [blame] | 170 | std::string expected_after = |
David Brazdil | 86ea7ee | 2016-02-16 09:26:07 +0000 | [diff] [blame] | 171 | "BasicBlock 0, succ: 1\n" |
David Brazdil | dee58d6 | 2016-04-07 09:54:26 +0000 | [diff] [blame] | 172 | " 0: SuspendCheck\n" |
| 173 | " 1: Goto 1\n" |
David Brazdil | 86ea7ee | 2016-02-16 09:26:07 +0000 | [diff] [blame] | 174 | "BasicBlock 1, pred: 0, succ: 5\n" |
David Brazdil | dee58d6 | 2016-04-07 09:54:26 +0000 | [diff] [blame] | 175 | " 14: ReturnVoid\n" |
David Brazdil | 86ea7ee | 2016-02-16 09:26:07 +0000 | [diff] [blame] | 176 | "BasicBlock 5, pred: 1\n" |
David Brazdil | dee58d6 | 2016-04-07 09:54:26 +0000 | [diff] [blame] | 177 | " 15: Exit\n"; |
Roland Levillain | 72bceff | 2014-09-15 18:29:00 +0100 | [diff] [blame] | 178 | |
| 179 | TestCode(data, expected_before, expected_after); |
| 180 | } |
| 181 | |
| 182 | } // namespace art |