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 "builder.h" 18 #include "code_generator.h" 19 #include "dex_file.h" 20 #include "dex_instruction.h" 21 #include "nodes.h" 22 #include "optimizing_unit_test.h" 23 #include "register_allocator.h" 24 #include "ssa_liveness_analysis.h" 25 #include "utils/arena_allocator.h" 26 27 #include "gtest/gtest.h" 28 29 namespace art { 30 31 // Note: the register allocator tests rely on the fact that constants have live 32 // intervals and registers get allocated to them. 33 34 static bool Check(const uint16_t* data) { 35 ArenaPool pool; 36 ArenaAllocator allocator(&pool); 37 HGraphBuilder builder(&allocator); 38 const DexFile::CodeItem* item = reinterpret_cast<const DexFile::CodeItem*>(data); 39 HGraph* graph = builder.BuildGraph(*item); 40 graph->BuildDominatorTree(); 41 graph->TransformToSSA(); 42 graph->FindNaturalLoops(); 43 CodeGenerator* codegen = CodeGenerator::Create(&allocator, graph, kX86); 44 SsaLivenessAnalysis liveness(*graph, codegen); 45 liveness.Analyze(); 46 RegisterAllocator register_allocator(&allocator, codegen, liveness); 47 register_allocator.AllocateRegisters(); 48 return register_allocator.Validate(false); 49 } 50 51 /** 52 * Unit testing of RegisterAllocator::ValidateIntervals. Register allocator 53 * tests are based on this validation method. 54 */ 55 TEST(RegisterAllocatorTest, ValidateIntervals) { 56 ArenaPool pool; 57 ArenaAllocator allocator(&pool); 58 HGraph* graph = new (&allocator) HGraph(&allocator); 59 CodeGenerator* codegen = CodeGenerator::Create(&allocator, graph, kX86); 60 GrowableArray<LiveInterval*> intervals(&allocator, 0); 61 62 // Test with two intervals of the same range. 63 { 64 static constexpr size_t ranges[][2] = {{0, 42}}; 65 intervals.Add(BuildInterval(ranges, arraysize(ranges), &allocator, 0)); 66 intervals.Add(BuildInterval(ranges, arraysize(ranges), &allocator, 1)); 67 ASSERT_TRUE(RegisterAllocator::ValidateIntervals( 68 intervals, 0, *codegen, &allocator, true, false)); 69 70 intervals.Get(1)->SetRegister(0); 71 ASSERT_FALSE(RegisterAllocator::ValidateIntervals( 72 intervals, 0, *codegen, &allocator, true, false)); 73 intervals.Reset(); 74 } 75 76 // Test with two non-intersecting intervals. 77 { 78 static constexpr size_t ranges1[][2] = {{0, 42}}; 79 intervals.Add(BuildInterval(ranges1, arraysize(ranges1), &allocator, 0)); 80 static constexpr size_t ranges2[][2] = {{42, 43}}; 81 intervals.Add(BuildInterval(ranges2, arraysize(ranges2), &allocator, 1)); 82 ASSERT_TRUE(RegisterAllocator::ValidateIntervals( 83 intervals, 0, *codegen, &allocator, true, false)); 84 85 intervals.Get(1)->SetRegister(0); 86 ASSERT_TRUE(RegisterAllocator::ValidateIntervals( 87 intervals, 0, *codegen, &allocator, true, false)); 88 intervals.Reset(); 89 } 90 91 // Test with two non-intersecting intervals, with one with a lifetime hole. 92 { 93 static constexpr size_t ranges1[][2] = {{0, 42}, {45, 48}}; 94 intervals.Add(BuildInterval(ranges1, arraysize(ranges1), &allocator, 0)); 95 static constexpr size_t ranges2[][2] = {{42, 43}}; 96 intervals.Add(BuildInterval(ranges2, arraysize(ranges2), &allocator, 1)); 97 ASSERT_TRUE(RegisterAllocator::ValidateIntervals( 98 intervals, 0, *codegen, &allocator, true, false)); 99 100 intervals.Get(1)->SetRegister(0); 101 ASSERT_TRUE(RegisterAllocator::ValidateIntervals( 102 intervals, 0, *codegen, &allocator, true, false)); 103 intervals.Reset(); 104 } 105 106 // Test with intersecting intervals. 107 { 108 static constexpr size_t ranges1[][2] = {{0, 42}, {44, 48}}; 109 intervals.Add(BuildInterval(ranges1, arraysize(ranges1), &allocator, 0)); 110 static constexpr size_t ranges2[][2] = {{42, 47}}; 111 intervals.Add(BuildInterval(ranges2, arraysize(ranges2), &allocator, 1)); 112 ASSERT_TRUE(RegisterAllocator::ValidateIntervals( 113 intervals, 0, *codegen, &allocator, true, false)); 114 115 intervals.Get(1)->SetRegister(0); 116 ASSERT_FALSE(RegisterAllocator::ValidateIntervals( 117 intervals, 0, *codegen, &allocator, true, false)); 118 intervals.Reset(); 119 } 120 121 // Test with siblings. 122 { 123 static constexpr size_t ranges1[][2] = {{0, 42}, {44, 48}}; 124 intervals.Add(BuildInterval(ranges1, arraysize(ranges1), &allocator, 0)); 125 intervals.Get(0)->SplitAt(43); 126 static constexpr size_t ranges2[][2] = {{42, 47}}; 127 intervals.Add(BuildInterval(ranges2, arraysize(ranges2), &allocator, 1)); 128 ASSERT_TRUE(RegisterAllocator::ValidateIntervals( 129 intervals, 0, *codegen, &allocator, true, false)); 130 131 intervals.Get(1)->SetRegister(0); 132 // Sibling of the first interval has no register allocated to it. 133 ASSERT_TRUE(RegisterAllocator::ValidateIntervals( 134 intervals, 0, *codegen, &allocator, true, false)); 135 136 intervals.Get(0)->GetNextSibling()->SetRegister(0); 137 ASSERT_FALSE(RegisterAllocator::ValidateIntervals( 138 intervals, 0, *codegen, &allocator, true, false)); 139 } 140 } 141 142 TEST(RegisterAllocatorTest, CFG1) { 143 /* 144 * Test the following snippet: 145 * return 0; 146 * 147 * Which becomes the following graph: 148 * constant0 149 * goto 150 * | 151 * return 152 * | 153 * exit 154 */ 155 const uint16_t data[] = ONE_REGISTER_CODE_ITEM( 156 Instruction::CONST_4 | 0 | 0, 157 Instruction::RETURN); 158 159 ASSERT_TRUE(Check(data)); 160 } 161 162 TEST(RegisterAllocatorTest, Loop1) { 163 /* 164 * Test the following snippet: 165 * int a = 0; 166 * while (a == a) { 167 * a = 4; 168 * } 169 * return 5; 170 * 171 * Which becomes the following graph: 172 * constant0 173 * constant4 174 * constant5 175 * goto 176 * | 177 * goto 178 * | 179 * phi 180 * equal 181 * if +++++ 182 * | \ + 183 * | goto 184 * | 185 * return 186 * | 187 * exit 188 */ 189 190 const uint16_t data[] = TWO_REGISTERS_CODE_ITEM( 191 Instruction::CONST_4 | 0 | 0, 192 Instruction::IF_EQ, 4, 193 Instruction::CONST_4 | 4 << 12 | 0, 194 Instruction::GOTO | 0xFD00, 195 Instruction::CONST_4 | 5 << 12 | 1 << 8, 196 Instruction::RETURN | 1 << 8); 197 198 ASSERT_TRUE(Check(data)); 199 } 200 201 TEST(RegisterAllocatorTest, Loop2) { 202 /* 203 * Test the following snippet: 204 * int a = 0; 205 * while (a == 8) { 206 * a = 4 + 5; 207 * } 208 * return 6 + 7; 209 * 210 * Which becomes the following graph: 211 * constant0 212 * constant4 213 * constant5 214 * constant6 215 * constant7 216 * constant8 217 * goto 218 * | 219 * goto 220 * | 221 * phi 222 * equal 223 * if +++++ 224 * | \ + 225 * | 4 + 5 226 * | goto 227 * | 228 * 6 + 7 229 * return 230 * | 231 * exit 232 */ 233 234 const uint16_t data[] = TWO_REGISTERS_CODE_ITEM( 235 Instruction::CONST_4 | 0 | 0, 236 Instruction::CONST_4 | 8 << 12 | 1 << 8, 237 Instruction::IF_EQ | 1 << 8, 7, 238 Instruction::CONST_4 | 4 << 12 | 0 << 8, 239 Instruction::CONST_4 | 5 << 12 | 1 << 8, 240 Instruction::ADD_INT, 1 << 8 | 0, 241 Instruction::GOTO | 0xFA00, 242 Instruction::CONST_4 | 6 << 12 | 1 << 8, 243 Instruction::CONST_4 | 7 << 12 | 1 << 8, 244 Instruction::ADD_INT, 1 << 8 | 0, 245 Instruction::RETURN | 1 << 8); 246 247 ASSERT_TRUE(Check(data)); 248 } 249 250 static HGraph* BuildSSAGraph(const uint16_t* data, ArenaAllocator* allocator) { 251 HGraphBuilder builder(allocator); 252 const DexFile::CodeItem* item = reinterpret_cast<const DexFile::CodeItem*>(data); 253 HGraph* graph = builder.BuildGraph(*item); 254 graph->BuildDominatorTree(); 255 graph->TransformToSSA(); 256 graph->FindNaturalLoops(); 257 return graph; 258 } 259 260 TEST(RegisterAllocatorTest, Loop3) { 261 /* 262 * Test the following snippet: 263 * int a = 0 264 * do { 265 * b = a; 266 * a++; 267 * } while (a != 5) 268 * return b; 269 * 270 * Which becomes the following graph: 271 * constant0 272 * constant1 273 * constant5 274 * goto 275 * | 276 * goto 277 * |++++++++++++ 278 * phi + 279 * a++ + 280 * equals + 281 * if + 282 * |++++++++++++ 283 * return 284 * | 285 * exit 286 */ 287 288 const uint16_t data[] = THREE_REGISTERS_CODE_ITEM( 289 Instruction::CONST_4 | 0 | 0, 290 Instruction::ADD_INT_LIT8 | 1 << 8, 1 << 8, 291 Instruction::CONST_4 | 5 << 12 | 2 << 8, 292 Instruction::IF_NE | 1 << 8 | 2 << 12, 3, 293 Instruction::RETURN | 0 << 8, 294 Instruction::MOVE | 1 << 12 | 0 << 8, 295 Instruction::GOTO | 0xF900); 296 297 ArenaPool pool; 298 ArenaAllocator allocator(&pool); 299 HGraph* graph = BuildSSAGraph(data, &allocator); 300 CodeGenerator* codegen = CodeGenerator::Create(&allocator, graph, kX86); 301 SsaLivenessAnalysis liveness(*graph, codegen); 302 liveness.Analyze(); 303 RegisterAllocator register_allocator(&allocator, codegen, liveness); 304 register_allocator.AllocateRegisters(); 305 ASSERT_TRUE(register_allocator.Validate(false)); 306 307 HBasicBlock* loop_header = graph->GetBlocks().Get(2); 308 HPhi* phi = loop_header->GetFirstPhi()->AsPhi(); 309 310 LiveInterval* phi_interval = phi->GetLiveInterval(); 311 LiveInterval* loop_update = phi->InputAt(1)->GetLiveInterval(); 312 ASSERT_TRUE(phi_interval->HasRegister()); 313 ASSERT_TRUE(loop_update->HasRegister()); 314 ASSERT_NE(phi_interval->GetRegister(), loop_update->GetRegister()); 315 316 HBasicBlock* return_block = graph->GetBlocks().Get(3); 317 HReturn* ret = return_block->GetLastInstruction()->AsReturn(); 318 ASSERT_EQ(phi_interval->GetRegister(), ret->InputAt(0)->GetLiveInterval()->GetRegister()); 319 } 320 321 TEST(RegisterAllocatorTest, FirstRegisterUse) { 322 const uint16_t data[] = THREE_REGISTERS_CODE_ITEM( 323 Instruction::CONST_4 | 0 | 0, 324 Instruction::ADD_INT_LIT8 | 1 << 8, 1 << 8, 325 Instruction::ADD_INT_LIT8 | 0 << 8, 1 << 8, 326 Instruction::ADD_INT_LIT8 | 1 << 8, 1 << 8 | 1, 327 Instruction::RETURN_VOID); 328 329 ArenaPool pool; 330 ArenaAllocator allocator(&pool); 331 HGraph* graph = BuildSSAGraph(data, &allocator); 332 CodeGenerator* codegen = CodeGenerator::Create(&allocator, graph, kArm); 333 SsaLivenessAnalysis liveness(*graph, codegen); 334 liveness.Analyze(); 335 336 HAdd* first_add = graph->GetBlocks().Get(1)->GetFirstInstruction()->AsAdd(); 337 HAdd* last_add = graph->GetBlocks().Get(1)->GetLastInstruction()->GetPrevious()->AsAdd(); 338 ASSERT_EQ(last_add->InputAt(0), first_add); 339 LiveInterval* interval = first_add->GetLiveInterval(); 340 ASSERT_EQ(interval->GetEnd(), last_add->GetLifetimePosition() + 1); 341 ASSERT_TRUE(interval->GetNextSibling() == nullptr); 342 343 // We need a register for the output of the instruction. 344 ASSERT_EQ(interval->FirstRegisterUse(), first_add->GetLifetimePosition()); 345 346 // Split at the next instruction. 347 interval = interval->SplitAt(first_add->GetLifetimePosition() + 2); 348 // The user of the split is the last add. 349 ASSERT_EQ(interval->FirstRegisterUse(), last_add->GetLifetimePosition() + 1); 350 351 // Split before the last add. 352 LiveInterval* new_interval = interval->SplitAt(last_add->GetLifetimePosition() - 1); 353 // Ensure the current interval has no register use... 354 ASSERT_EQ(interval->FirstRegisterUse(), kNoLifetime); 355 // And the new interval has it for the last add. 356 ASSERT_EQ(new_interval->FirstRegisterUse(), last_add->GetLifetimePosition() + 1); 357 } 358 359 } // namespace art 360
