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