Nicolas Geoffray | 0d3f578 | 2014-05-14 09:43:38 +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 | |
| 17 | #include <fstream> |
| 18 | |
Mark Mendell | fb8d279 | 2015-03-31 22:16:59 -0400 | [diff] [blame] | 19 | #include "arch/x86/instruction_set_features_x86.h" |
Mathieu Chartier | b666f48 | 2015-02-18 14:33:14 -0800 | [diff] [blame] | 20 | #include "base/arena_allocator.h" |
Nicolas Geoffray | 0d3f578 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 21 | #include "base/stringprintf.h" |
| 22 | #include "builder.h" |
Nicolas Geoffray | 31d76b4 | 2014-06-09 15:02:22 +0100 | [diff] [blame] | 23 | #include "code_generator.h" |
Nicolas Geoffray | 8a16d97 | 2014-09-11 10:30:02 +0100 | [diff] [blame] | 24 | #include "code_generator_x86.h" |
Nicolas Geoffray | 0d3f578 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 25 | #include "dex_file.h" |
| 26 | #include "dex_instruction.h" |
Calin Juravle | cd6dffe | 2015-01-08 17:35:35 +0000 | [diff] [blame] | 27 | #include "driver/compiler_options.h" |
Nicolas Geoffray | 0d3f578 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 28 | #include "graph_visualizer.h" |
| 29 | #include "nodes.h" |
| 30 | #include "optimizing_unit_test.h" |
| 31 | #include "pretty_printer.h" |
| 32 | #include "ssa_builder.h" |
| 33 | #include "ssa_liveness_analysis.h" |
Nicolas Geoffray | 0d3f578 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 34 | |
| 35 | #include "gtest/gtest.h" |
| 36 | |
| 37 | namespace art { |
| 38 | |
| 39 | static void TestCode(const uint16_t* data, const int* expected_order, size_t number_of_blocks) { |
| 40 | ArenaPool pool; |
| 41 | ArenaAllocator allocator(&pool); |
Nicolas Geoffray | 0a23d74 | 2015-05-07 11:57:35 +0100 | [diff] [blame] | 42 | HGraph* graph = CreateGraph(&allocator); |
David Brazdil | 5e8b137 | 2015-01-23 14:39:08 +0000 | [diff] [blame] | 43 | HGraphBuilder builder(graph); |
Nicolas Geoffray | 0d3f578 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 44 | const DexFile::CodeItem* item = reinterpret_cast<const DexFile::CodeItem*>(data); |
David Brazdil | 5e8b137 | 2015-01-23 14:39:08 +0000 | [diff] [blame] | 45 | bool graph_built = builder.BuildGraph(*item); |
| 46 | ASSERT_TRUE(graph_built); |
Nicolas Geoffray | 0d3f578 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 47 | |
Nicolas Geoffray | e53798a | 2014-12-01 10:31:54 +0000 | [diff] [blame] | 48 | graph->TryBuildingSsa(); |
Nicolas Geoffray | 31d76b4 | 2014-06-09 15:02:22 +0100 | [diff] [blame] | 49 | |
Mark Mendell | fb8d279 | 2015-03-31 22:16:59 -0400 | [diff] [blame] | 50 | std::unique_ptr<const X86InstructionSetFeatures> features_x86( |
| 51 | X86InstructionSetFeatures::FromCppDefines()); |
| 52 | x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions()); |
Nicolas Geoffray | 0d9f17d | 2015-04-15 14:17:44 +0100 | [diff] [blame] | 53 | SsaLivenessAnalysis liveness(graph, &codegen); |
Nicolas Geoffray | 0d3f578 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 54 | liveness.Analyze(); |
| 55 | |
Nicolas Geoffray | 0d9f17d | 2015-04-15 14:17:44 +0100 | [diff] [blame] | 56 | ASSERT_EQ(graph->GetLinearOrder().Size(), number_of_blocks); |
Nicolas Geoffray | 0d3f578 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 57 | for (size_t i = 0; i < number_of_blocks; ++i) { |
Nicolas Geoffray | 0d9f17d | 2015-04-15 14:17:44 +0100 | [diff] [blame] | 58 | ASSERT_EQ(graph->GetLinearOrder().Get(i)->GetBlockId(), expected_order[i]); |
Nicolas Geoffray | 0d3f578 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 59 | } |
| 60 | } |
| 61 | |
| 62 | TEST(LinearizeTest, CFG1) { |
Nicolas Geoffray | 8f1a4d4 | 2014-05-16 09:36:00 +0100 | [diff] [blame] | 63 | // Structure of this graph (+ are back edges) |
Nicolas Geoffray | 0d3f578 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 64 | // Block0 |
| 65 | // | |
| 66 | // Block1 |
| 67 | // | |
Nicolas Geoffray | 8f1a4d4 | 2014-05-16 09:36:00 +0100 | [diff] [blame] | 68 | // Block2 ++++++ |
| 69 | // / \ + |
| 70 | // Block5 Block7 + |
| 71 | // | | + |
| 72 | // Block6 Block3 + |
| 73 | // + / \ + |
Nicolas Geoffray | 0d3f578 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 74 | // Block4 Block8 |
| 75 | |
| 76 | const uint16_t data[] = ONE_REGISTER_CODE_ITEM( |
| 77 | Instruction::CONST_4 | 0 | 0, |
| 78 | Instruction::IF_EQ, 5, |
| 79 | Instruction::IF_EQ, 0xFFFE, |
| 80 | Instruction::GOTO | 0xFE00, |
| 81 | Instruction::RETURN_VOID); |
| 82 | |
| 83 | const int blocks[] = {0, 1, 2, 7, 3, 4, 8, 5, 6}; |
| 84 | TestCode(data, blocks, 9); |
| 85 | } |
| 86 | |
| 87 | TEST(LinearizeTest, CFG2) { |
Nicolas Geoffray | 8f1a4d4 | 2014-05-16 09:36:00 +0100 | [diff] [blame] | 88 | // Structure of this graph (+ are back edges) |
Nicolas Geoffray | 0d3f578 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 89 | // Block0 |
| 90 | // | |
| 91 | // Block1 |
| 92 | // | |
Nicolas Geoffray | 8f1a4d4 | 2014-05-16 09:36:00 +0100 | [diff] [blame] | 93 | // Block2 ++++++ |
| 94 | // / \ + |
| 95 | // Block3 Block7 + |
| 96 | // | | + |
| 97 | // Block6 Block4 + |
| 98 | // + / \ + |
Nicolas Geoffray | 0d3f578 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 99 | // Block5 Block8 |
| 100 | |
| 101 | const uint16_t data[] = ONE_REGISTER_CODE_ITEM( |
| 102 | Instruction::CONST_4 | 0 | 0, |
| 103 | Instruction::IF_EQ, 3, |
| 104 | Instruction::RETURN_VOID, |
| 105 | Instruction::IF_EQ, 0xFFFD, |
| 106 | Instruction::GOTO | 0xFE00); |
| 107 | |
| 108 | const int blocks[] = {0, 1, 2, 7, 4, 5, 8, 3, 6}; |
| 109 | TestCode(data, blocks, 9); |
| 110 | } |
| 111 | |
| 112 | TEST(LinearizeTest, CFG3) { |
Nicolas Geoffray | 8f1a4d4 | 2014-05-16 09:36:00 +0100 | [diff] [blame] | 113 | // Structure of this graph (+ are back edges) |
Nicolas Geoffray | 0d3f578 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 114 | // Block0 |
| 115 | // | |
| 116 | // Block1 |
| 117 | // | |
Nicolas Geoffray | 8f1a4d4 | 2014-05-16 09:36:00 +0100 | [diff] [blame] | 118 | // Block2 ++++++ |
| 119 | // / \ + |
| 120 | // Block3 Block8 + |
| 121 | // | | + |
| 122 | // Block7 Block5 + |
| 123 | // / + \ + |
| 124 | // Block6 + Block9 |
| 125 | // | + |
| 126 | // Block4 ++ |
Nicolas Geoffray | 0d3f578 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 127 | const uint16_t data[] = ONE_REGISTER_CODE_ITEM( |
| 128 | Instruction::CONST_4 | 0 | 0, |
| 129 | Instruction::IF_EQ, 4, |
| 130 | Instruction::RETURN_VOID, |
| 131 | Instruction::GOTO | 0x0100, |
| 132 | Instruction::IF_EQ, 0xFFFC, |
| 133 | Instruction::GOTO | 0xFD00); |
| 134 | |
| 135 | const int blocks[] = {0, 1, 2, 8, 5, 6, 4, 9, 3, 7}; |
| 136 | TestCode(data, blocks, 10); |
| 137 | } |
| 138 | |
| 139 | TEST(LinearizeTest, CFG4) { |
Nicolas Geoffray | 8f1a4d4 | 2014-05-16 09:36:00 +0100 | [diff] [blame] | 140 | /* Structure of this graph (+ are back edges) |
Nicolas Geoffray | 0d3f578 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 141 | // Block0 |
| 142 | // | |
| 143 | // Block1 |
| 144 | // | |
| 145 | // Block2 |
Nicolas Geoffray | 8f1a4d4 | 2014-05-16 09:36:00 +0100 | [diff] [blame] | 146 | // / + \ |
| 147 | // Block6 + Block8 |
| 148 | // | + | |
| 149 | // Block7 + Block3 +++++++ |
| 150 | // + / \ + |
| 151 | // Block9 Block10 + |
| 152 | // | + |
| 153 | // Block4 + |
| 154 | // + / \ + |
Nicolas Geoffray | 0d3f578 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 155 | // Block5 Block11 |
Nicolas Geoffray | 8f1a4d4 | 2014-05-16 09:36:00 +0100 | [diff] [blame] | 156 | */ |
Nicolas Geoffray | 0d3f578 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 157 | const uint16_t data[] = ONE_REGISTER_CODE_ITEM( |
| 158 | Instruction::CONST_4 | 0 | 0, |
| 159 | Instruction::IF_EQ, 7, |
| 160 | Instruction::IF_EQ, 0xFFFE, |
| 161 | Instruction::IF_EQ, 0xFFFE, |
| 162 | Instruction::GOTO | 0xFE00, |
| 163 | Instruction::RETURN_VOID); |
| 164 | |
| 165 | const int blocks[] = {0, 1, 2, 8, 3, 10, 4, 5, 11, 9, 6, 7}; |
| 166 | TestCode(data, blocks, 12); |
| 167 | } |
| 168 | |
| 169 | TEST(LinearizeTest, CFG5) { |
Nicolas Geoffray | 8f1a4d4 | 2014-05-16 09:36:00 +0100 | [diff] [blame] | 170 | /* Structure of this graph (+ are back edges) |
Nicolas Geoffray | 0d3f578 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 171 | // Block0 |
| 172 | // | |
| 173 | // Block1 |
| 174 | // | |
| 175 | // Block2 |
Nicolas Geoffray | 8f1a4d4 | 2014-05-16 09:36:00 +0100 | [diff] [blame] | 176 | // / + \ |
| 177 | // Block3 + Block8 |
| 178 | // | + | |
| 179 | // Block7 + Block4 +++++++ |
| 180 | // + / \ + |
| 181 | // Block9 Block10 + |
| 182 | // | + |
| 183 | // Block5 + |
| 184 | // +/ \ + |
Nicolas Geoffray | 0d3f578 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 185 | // Block6 Block11 |
Nicolas Geoffray | 8f1a4d4 | 2014-05-16 09:36:00 +0100 | [diff] [blame] | 186 | */ |
Nicolas Geoffray | 0d3f578 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 187 | const uint16_t data[] = ONE_REGISTER_CODE_ITEM( |
| 188 | Instruction::CONST_4 | 0 | 0, |
| 189 | Instruction::IF_EQ, 3, |
| 190 | Instruction::RETURN_VOID, |
| 191 | Instruction::IF_EQ, 0xFFFD, |
| 192 | Instruction::IF_EQ, 0xFFFE, |
| 193 | Instruction::GOTO | 0xFE00); |
| 194 | |
| 195 | const int blocks[] = {0, 1, 2, 8, 4, 10, 5, 6, 11, 9, 3, 7}; |
| 196 | TestCode(data, blocks, 12); |
| 197 | } |
| 198 | |
Nicolas Geoffray | a8eed3a | 2014-11-24 17:47:10 +0000 | [diff] [blame] | 199 | TEST(LinearizeTest, CFG6) { |
| 200 | // Block0 |
| 201 | // | |
| 202 | // Block1 |
| 203 | // | |
| 204 | // Block2 ++++++++++++++ |
| 205 | // | + |
| 206 | // Block3 + |
| 207 | // / \ + |
| 208 | // Block8 Block4 + |
| 209 | // | / \ + |
| 210 | // Block5 <- Block9 Block6 + |
| 211 | // | |
| 212 | // Block7 |
| 213 | const uint16_t data[] = ONE_REGISTER_CODE_ITEM( |
| 214 | Instruction::CONST_4 | 0 | 0, |
| 215 | Instruction::GOTO | 0x0100, |
| 216 | Instruction::IF_EQ, 0x0004, |
| 217 | Instruction::IF_EQ, 0x0003, |
| 218 | Instruction::RETURN_VOID, |
| 219 | Instruction::GOTO | 0xFA00); |
| 220 | |
| 221 | const int blocks[] = {0, 1, 2, 3, 4, 6, 9, 8, 5, 7}; |
| 222 | TestCode(data, blocks, arraysize(blocks)); |
| 223 | } |
| 224 | |
| 225 | TEST(LinearizeTest, CFG7) { |
| 226 | // Structure of this graph (+ are back edges) |
| 227 | // Block0 |
| 228 | // | |
| 229 | // Block1 |
| 230 | // | |
| 231 | // Block2 ++++++++ |
| 232 | // | + |
| 233 | // Block3 + |
| 234 | // / \ + |
| 235 | // Block4 Block8 + |
| 236 | // / \ | + |
| 237 | // Block5 Block9 - Block6 + |
| 238 | // | |
| 239 | // Block7 |
| 240 | // |
| 241 | const uint16_t data[] = ONE_REGISTER_CODE_ITEM( |
| 242 | Instruction::CONST_4 | 0 | 0, |
| 243 | Instruction::GOTO | 0x0100, |
| 244 | Instruction::IF_EQ, 0x0005, |
| 245 | Instruction::IF_EQ, 0x0003, |
| 246 | Instruction::RETURN_VOID, |
| 247 | Instruction::GOTO | 0xFA00); |
| 248 | |
| 249 | const int blocks[] = {0, 1, 2, 3, 4, 9, 8, 6, 5, 7}; |
| 250 | TestCode(data, blocks, arraysize(blocks)); |
| 251 | } |
| 252 | |
Nicolas Geoffray | 0d3f578 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 253 | } // namespace art |