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