ralloc_util.cc revision d61ba4ba6fcde666adb5d5c81b1c32f0534fb2c8
1/* 2 * Copyright (C) 2011 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/* This file contains register alloction support. */ 18 19#include "dex/compiler_ir.h" 20#include "dex/compiler_internals.h" 21#include "mir_to_lir-inl.h" 22 23namespace art { 24 25/* 26 * Free all allocated temps in the temp pools. Note that this does 27 * not affect the "liveness" of a temp register, which will stay 28 * live until it is either explicitly killed or reallocated. 29 */ 30void Mir2Lir::ResetRegPool() { 31 GrowableArray<RegisterInfo*>::Iterator iter(&tempreg_info_); 32 for (RegisterInfo* info = iter.Next(); info != NULL; info = iter.Next()) { 33 info->in_use = false; 34 } 35 // Reset temp tracking sanity check. 36 if (kIsDebugBuild) { 37 live_sreg_ = INVALID_SREG; 38 } 39} 40 41 /* 42 * Set up temp & preserved register pools specialized by target. 43 * Note: num_regs may be zero. 44 */ 45void Mir2Lir::CompilerInitPool(RegisterInfo* regs, int* reg_nums, int num) { 46 for (int i = 0; i < num; i++) { 47 uint32_t reg_number = reg_nums[i]; 48 regs[i].reg = reg_number; 49 regs[i].in_use = false; 50 regs[i].is_temp = false; 51 regs[i].pair = false; 52 regs[i].live = false; 53 regs[i].dirty = false; 54 regs[i].s_reg = INVALID_SREG; 55 size_t map_size = reginfo_map_.Size(); 56 if (reg_number >= map_size) { 57 for (uint32_t i = 0; i < ((reg_number - map_size) + 1); i++) { 58 reginfo_map_.Insert(NULL); 59 } 60 } 61 reginfo_map_.Put(reg_number, ®s[i]); 62 } 63} 64 65void Mir2Lir::DumpRegPool(RegisterInfo* p, int num_regs) { 66 LOG(INFO) << "================================================"; 67 for (int i = 0; i < num_regs; i++) { 68 LOG(INFO) << StringPrintf( 69 "R[%d]: T:%d, U:%d, P:%d, p:%d, LV:%d, D:%d, SR:%d", 70 p[i].reg, p[i].is_temp, p[i].in_use, p[i].pair, p[i].partner, 71 p[i].live, p[i].dirty, p[i].s_reg); 72 } 73 LOG(INFO) << "================================================"; 74} 75 76void Mir2Lir::DumpCoreRegPool() { 77 DumpRegPool(reg_pool_->core_regs, reg_pool_->num_core_regs); 78} 79 80void Mir2Lir::DumpFpRegPool() { 81 DumpRegPool(reg_pool_->FPRegs, reg_pool_->num_fp_regs); 82} 83 84void Mir2Lir::ClobberSRegBody(RegisterInfo* p, int num_regs, int s_reg) { 85 for (int i = 0; i< num_regs; i++) { 86 if (p[i].s_reg == s_reg) { 87 if (p[i].is_temp) { 88 p[i].live = false; 89 } 90 p[i].def_start = NULL; 91 p[i].def_end = NULL; 92 } 93 } 94} 95 96/* 97 * Break the association between a Dalvik vreg and a physical temp register of either register 98 * class. 99 * TODO: Ideally, the public version of this code should not exist. Besides its local usage 100 * in the register utilities, is is also used by code gen routines to work around a deficiency in 101 * local register allocation, which fails to distinguish between the "in" and "out" identities 102 * of Dalvik vregs. This can result in useless register copies when the same Dalvik vreg 103 * is used both as the source and destination register of an operation in which the type 104 * changes (for example: INT_TO_FLOAT v1, v1). Revisit when improved register allocation is 105 * addressed. 106 */ 107void Mir2Lir::ClobberSReg(int s_reg) { 108 /* Reset live temp tracking sanity checker */ 109 if (kIsDebugBuild) { 110 if (s_reg == live_sreg_) { 111 live_sreg_ = INVALID_SREG; 112 } 113 } 114 ClobberSRegBody(reg_pool_->core_regs, reg_pool_->num_core_regs, s_reg); 115 ClobberSRegBody(reg_pool_->FPRegs, reg_pool_->num_fp_regs, s_reg); 116} 117 118/* 119 * SSA names associated with the initial definitions of Dalvik 120 * registers are the same as the Dalvik register number (and 121 * thus take the same position in the promotion_map. However, 122 * the special Method* and compiler temp resisters use negative 123 * v_reg numbers to distinguish them and can have an arbitrary 124 * ssa name (above the last original Dalvik register). This function 125 * maps SSA names to positions in the promotion_map array. 126 */ 127int Mir2Lir::SRegToPMap(int s_reg) { 128 DCHECK_LT(s_reg, mir_graph_->GetNumSSARegs()); 129 DCHECK_GE(s_reg, 0); 130 int v_reg = mir_graph_->SRegToVReg(s_reg); 131 if (v_reg >= 0) { 132 DCHECK_LT(v_reg, cu_->num_dalvik_registers); 133 return v_reg; 134 } else { 135 int pos = std::abs(v_reg) - std::abs(SSA_METHOD_BASEREG); 136 DCHECK_LE(pos, cu_->num_compiler_temps); 137 return cu_->num_dalvik_registers + pos; 138 } 139} 140 141void Mir2Lir::RecordCorePromotion(int reg, int s_reg) { 142 int p_map_idx = SRegToPMap(s_reg); 143 int v_reg = mir_graph_->SRegToVReg(s_reg); 144 GetRegInfo(reg)->in_use = true; 145 core_spill_mask_ |= (1 << reg); 146 // Include reg for later sort 147 core_vmap_table_.push_back(reg << VREG_NUM_WIDTH | (v_reg & ((1 << VREG_NUM_WIDTH) - 1))); 148 num_core_spills_++; 149 promotion_map_[p_map_idx].core_location = kLocPhysReg; 150 promotion_map_[p_map_idx].core_reg = reg; 151} 152 153/* Reserve a callee-save register. Return -1 if none available */ 154int Mir2Lir::AllocPreservedCoreReg(int s_reg) { 155 int res = -1; 156 RegisterInfo* core_regs = reg_pool_->core_regs; 157 for (int i = 0; i < reg_pool_->num_core_regs; i++) { 158 if (!core_regs[i].is_temp && !core_regs[i].in_use) { 159 res = core_regs[i].reg; 160 RecordCorePromotion(res, s_reg); 161 break; 162 } 163 } 164 return res; 165} 166 167void Mir2Lir::RecordFpPromotion(int reg, int s_reg) { 168 int p_map_idx = SRegToPMap(s_reg); 169 int v_reg = mir_graph_->SRegToVReg(s_reg); 170 GetRegInfo(reg)->in_use = true; 171 MarkPreservedSingle(v_reg, reg); 172 promotion_map_[p_map_idx].fp_location = kLocPhysReg; 173 promotion_map_[p_map_idx].FpReg = reg; 174} 175 176// Reserve a callee-save fp single register. 177int Mir2Lir::AllocPreservedSingle(int s_reg) { 178 int res = -1; // Return code if none available. 179 RegisterInfo* FPRegs = reg_pool_->FPRegs; 180 for (int i = 0; i < reg_pool_->num_fp_regs; i++) { 181 if (!FPRegs[i].is_temp && !FPRegs[i].in_use) { 182 res = FPRegs[i].reg; 183 RecordFpPromotion(res, s_reg); 184 break; 185 } 186 } 187 return res; 188} 189 190/* 191 * Somewhat messy code here. We want to allocate a pair of contiguous 192 * physical single-precision floating point registers starting with 193 * an even numbered reg. It is possible that the paired s_reg (s_reg+1) 194 * has already been allocated - try to fit if possible. Fail to 195 * allocate if we can't meet the requirements for the pair of 196 * s_reg<=sX[even] & (s_reg+1)<= sX+1. 197 */ 198int Mir2Lir::AllocPreservedDouble(int s_reg) { 199 int res = -1; // Assume failure 200 int v_reg = mir_graph_->SRegToVReg(s_reg); 201 int p_map_idx = SRegToPMap(s_reg); 202 if (promotion_map_[p_map_idx+1].fp_location == kLocPhysReg) { 203 // Upper reg is already allocated. Can we fit? 204 int high_reg = promotion_map_[p_map_idx+1].FpReg; 205 if ((high_reg & 1) == 0) { 206 // High reg is even - fail. 207 return res; 208 } 209 // Is the low reg of the pair free? 210 RegisterInfo* p = GetRegInfo(high_reg-1); 211 if (p->in_use || p->is_temp) { 212 // Already allocated or not preserved - fail. 213 return res; 214 } 215 // OK - good to go. 216 res = p->reg; 217 p->in_use = true; 218 DCHECK_EQ((res & 1), 0); 219 MarkPreservedSingle(v_reg, res); 220 } else { 221 RegisterInfo* FPRegs = reg_pool_->FPRegs; 222 for (int i = 0; i < reg_pool_->num_fp_regs; i++) { 223 if (!FPRegs[i].is_temp && !FPRegs[i].in_use && 224 ((FPRegs[i].reg & 0x1) == 0x0) && 225 !FPRegs[i+1].is_temp && !FPRegs[i+1].in_use && 226 ((FPRegs[i+1].reg & 0x1) == 0x1) && 227 (FPRegs[i].reg + 1) == FPRegs[i+1].reg) { 228 res = FPRegs[i].reg; 229 FPRegs[i].in_use = true; 230 MarkPreservedSingle(v_reg, res); 231 FPRegs[i+1].in_use = true; 232 DCHECK_EQ(res + 1, FPRegs[i+1].reg); 233 MarkPreservedSingle(v_reg+1, res+1); 234 break; 235 } 236 } 237 } 238 if (res != -1) { 239 promotion_map_[p_map_idx].fp_location = kLocPhysReg; 240 promotion_map_[p_map_idx].FpReg = res; 241 promotion_map_[p_map_idx+1].fp_location = kLocPhysReg; 242 promotion_map_[p_map_idx+1].FpReg = res + 1; 243 } 244 return res; 245} 246 247int Mir2Lir::AllocTempBody(RegisterInfo* p, int num_regs, int* next_temp, 248 bool required) { 249 int next = *next_temp; 250 for (int i = 0; i< num_regs; i++) { 251 if (next >= num_regs) 252 next = 0; 253 if (p[next].is_temp && !p[next].in_use && !p[next].live) { 254 Clobber(p[next].reg); 255 p[next].in_use = true; 256 p[next].pair = false; 257 *next_temp = next + 1; 258 return p[next].reg; 259 } 260 next++; 261 } 262 next = *next_temp; 263 for (int i = 0; i< num_regs; i++) { 264 if (next >= num_regs) 265 next = 0; 266 if (p[next].is_temp && !p[next].in_use) { 267 Clobber(p[next].reg); 268 p[next].in_use = true; 269 p[next].pair = false; 270 *next_temp = next + 1; 271 return p[next].reg; 272 } 273 next++; 274 } 275 if (required) { 276 CodegenDump(); 277 DumpRegPool(reg_pool_->core_regs, 278 reg_pool_->num_core_regs); 279 LOG(FATAL) << "No free temp registers"; 280 } 281 return -1; // No register available 282} 283 284// REDO: too many assumptions. 285int Mir2Lir::AllocTempDouble() { 286 RegisterInfo* p = reg_pool_->FPRegs; 287 int num_regs = reg_pool_->num_fp_regs; 288 /* Start looking at an even reg */ 289 int next = reg_pool_->next_fp_reg & ~0x1; 290 291 // First try to avoid allocating live registers 292 for (int i = 0; i < num_regs; i+=2) { 293 if (next >= num_regs) 294 next = 0; 295 if ((p[next].is_temp && !p[next].in_use && !p[next].live) && 296 (p[next+1].is_temp && !p[next+1].in_use && !p[next+1].live)) { 297 Clobber(p[next].reg); 298 Clobber(p[next+1].reg); 299 p[next].in_use = true; 300 p[next+1].in_use = true; 301 DCHECK_EQ((p[next].reg+1), p[next+1].reg); 302 DCHECK_EQ((p[next].reg & 0x1), 0); 303 reg_pool_->next_fp_reg = next + 2; 304 if (reg_pool_->next_fp_reg >= num_regs) { 305 reg_pool_->next_fp_reg = 0; 306 } 307 return p[next].reg; 308 } 309 next += 2; 310 } 311 next = reg_pool_->next_fp_reg & ~0x1; 312 313 // No choice - find a pair and kill it. 314 for (int i = 0; i < num_regs; i+=2) { 315 if (next >= num_regs) 316 next = 0; 317 if (p[next].is_temp && !p[next].in_use && p[next+1].is_temp && 318 !p[next+1].in_use) { 319 Clobber(p[next].reg); 320 Clobber(p[next+1].reg); 321 p[next].in_use = true; 322 p[next+1].in_use = true; 323 DCHECK_EQ((p[next].reg+1), p[next+1].reg); 324 DCHECK_EQ((p[next].reg & 0x1), 0); 325 reg_pool_->next_fp_reg = next + 2; 326 if (reg_pool_->next_fp_reg >= num_regs) { 327 reg_pool_->next_fp_reg = 0; 328 } 329 return p[next].reg; 330 } 331 next += 2; 332 } 333 LOG(FATAL) << "No free temp registers (pair)"; 334 return -1; 335} 336 337/* Return a temp if one is available, -1 otherwise */ 338int Mir2Lir::AllocFreeTemp() { 339 return AllocTempBody(reg_pool_->core_regs, 340 reg_pool_->num_core_regs, 341 ®_pool_->next_core_reg, false); 342} 343 344int Mir2Lir::AllocTemp() { 345 return AllocTempBody(reg_pool_->core_regs, 346 reg_pool_->num_core_regs, 347 ®_pool_->next_core_reg, true); 348} 349 350int Mir2Lir::AllocTempFloat() { 351 return AllocTempBody(reg_pool_->FPRegs, 352 reg_pool_->num_fp_regs, 353 ®_pool_->next_fp_reg, true); 354} 355 356Mir2Lir::RegisterInfo* Mir2Lir::AllocLiveBody(RegisterInfo* p, int num_regs, int s_reg) { 357 if (s_reg == -1) 358 return NULL; 359 for (int i = 0; i < num_regs; i++) { 360 if ((p[i].s_reg == s_reg) && p[i].live) { 361 if (p[i].is_temp) 362 p[i].in_use = true; 363 return &p[i]; 364 } 365 } 366 return NULL; 367} 368 369Mir2Lir::RegisterInfo* Mir2Lir::AllocLive(int s_reg, int reg_class) { 370 RegisterInfo* res = NULL; 371 switch (reg_class) { 372 case kAnyReg: 373 res = AllocLiveBody(reg_pool_->FPRegs, 374 reg_pool_->num_fp_regs, s_reg); 375 if (res) 376 break; 377 /* Intentional fallthrough */ 378 case kCoreReg: 379 res = AllocLiveBody(reg_pool_->core_regs, 380 reg_pool_->num_core_regs, s_reg); 381 break; 382 case kFPReg: 383 res = AllocLiveBody(reg_pool_->FPRegs, 384 reg_pool_->num_fp_regs, s_reg); 385 break; 386 default: 387 LOG(FATAL) << "Invalid register type"; 388 } 389 return res; 390} 391 392void Mir2Lir::FreeTemp(int reg) { 393 RegisterInfo* p = GetRegInfo(reg); 394 if (p->is_temp) { 395 p->in_use = false; 396 } 397 p->pair = false; 398} 399 400Mir2Lir::RegisterInfo* Mir2Lir::IsLive(int reg) { 401 RegisterInfo* p = GetRegInfo(reg); 402 return p->live ? p : NULL; 403} 404 405Mir2Lir::RegisterInfo* Mir2Lir::IsTemp(int reg) { 406 RegisterInfo* p = GetRegInfo(reg); 407 return (p->is_temp) ? p : NULL; 408} 409 410Mir2Lir::RegisterInfo* Mir2Lir::IsPromoted(int reg) { 411 RegisterInfo* p = GetRegInfo(reg); 412 return (p->is_temp) ? NULL : p; 413} 414 415bool Mir2Lir::IsDirty(int reg) { 416 RegisterInfo* p = GetRegInfo(reg); 417 return p->dirty; 418} 419 420/* 421 * Similar to AllocTemp(), but forces the allocation of a specific 422 * register. No check is made to see if the register was previously 423 * allocated. Use with caution. 424 */ 425void Mir2Lir::LockTemp(int reg) { 426 RegisterInfo* p = GetRegInfo(reg); 427 DCHECK(p->is_temp); 428 p->in_use = true; 429 p->live = false; 430} 431 432void Mir2Lir::ResetDef(int reg) { 433 ResetDefBody(GetRegInfo(reg)); 434} 435 436void Mir2Lir::NullifyRange(LIR *start, LIR *finish, int s_reg1, int s_reg2) { 437 if (start && finish) { 438 LIR *p; 439 DCHECK_EQ(s_reg1, s_reg2); 440 for (p = start; ; p = p->next) { 441 NopLIR(p); 442 if (p == finish) 443 break; 444 } 445 } 446} 447 448/* 449 * Mark the beginning and end LIR of a def sequence. Note that 450 * on entry start points to the LIR prior to the beginning of the 451 * sequence. 452 */ 453void Mir2Lir::MarkDef(RegLocation rl, LIR *start, LIR *finish) { 454 DCHECK(!rl.wide); 455 DCHECK(start && start->next); 456 DCHECK(finish); 457 RegisterInfo* p = GetRegInfo(rl.low_reg); 458 p->def_start = start->next; 459 p->def_end = finish; 460} 461 462/* 463 * Mark the beginning and end LIR of a def sequence. Note that 464 * on entry start points to the LIR prior to the beginning of the 465 * sequence. 466 */ 467void Mir2Lir::MarkDefWide(RegLocation rl, LIR *start, LIR *finish) { 468 DCHECK(rl.wide); 469 DCHECK(start && start->next); 470 DCHECK(finish); 471 RegisterInfo* p = GetRegInfo(rl.low_reg); 472 ResetDef(rl.high_reg); // Only track low of pair 473 p->def_start = start->next; 474 p->def_end = finish; 475} 476 477RegLocation Mir2Lir::WideToNarrow(RegLocation rl) { 478 DCHECK(rl.wide); 479 if (rl.location == kLocPhysReg) { 480 RegisterInfo* info_lo = GetRegInfo(rl.low_reg); 481 RegisterInfo* info_hi = GetRegInfo(rl.high_reg); 482 if (info_lo->is_temp) { 483 info_lo->pair = false; 484 info_lo->def_start = NULL; 485 info_lo->def_end = NULL; 486 } 487 if (info_hi->is_temp) { 488 info_hi->pair = false; 489 info_hi->def_start = NULL; 490 info_hi->def_end = NULL; 491 } 492 } 493 rl.wide = false; 494 return rl; 495} 496 497void Mir2Lir::ResetDefLoc(RegLocation rl) { 498 DCHECK(!rl.wide); 499 RegisterInfo* p = IsTemp(rl.low_reg); 500 if (p && !(cu_->disable_opt & (1 << kSuppressLoads))) { 501 DCHECK(!p->pair); 502 NullifyRange(p->def_start, p->def_end, p->s_reg, rl.s_reg_low); 503 } 504 ResetDef(rl.low_reg); 505} 506 507void Mir2Lir::ResetDefLocWide(RegLocation rl) { 508 DCHECK(rl.wide); 509 RegisterInfo* p_low = IsTemp(rl.low_reg); 510 RegisterInfo* p_high = IsTemp(rl.high_reg); 511 if (p_low && !(cu_->disable_opt & (1 << kSuppressLoads))) { 512 DCHECK(p_low->pair); 513 NullifyRange(p_low->def_start, p_low->def_end, p_low->s_reg, rl.s_reg_low); 514 } 515 if (p_high && !(cu_->disable_opt & (1 << kSuppressLoads))) { 516 DCHECK(p_high->pair); 517 } 518 ResetDef(rl.low_reg); 519 ResetDef(rl.high_reg); 520} 521 522void Mir2Lir::ResetDefTracking() { 523 for (int i = 0; i< reg_pool_->num_core_regs; i++) { 524 ResetDefBody(®_pool_->core_regs[i]); 525 } 526 for (int i = 0; i< reg_pool_->num_fp_regs; i++) { 527 ResetDefBody(®_pool_->FPRegs[i]); 528 } 529} 530 531void Mir2Lir::ClobberAllRegs() { 532 GrowableArray<RegisterInfo*>::Iterator iter(&tempreg_info_); 533 for (RegisterInfo* info = iter.Next(); info != NULL; info = iter.Next()) { 534 info->live = false; 535 info->s_reg = INVALID_SREG; 536 info->def_start = NULL; 537 info->def_end = NULL; 538 info->pair = false; 539 } 540} 541 542// Make sure nothing is live and dirty 543void Mir2Lir::FlushAllRegsBody(RegisterInfo* info, int num_regs) { 544 for (int i = 0; i < num_regs; i++) { 545 if (info[i].live && info[i].dirty) { 546 if (info[i].pair) { 547 FlushRegWide(info[i].reg, info[i].partner); 548 } else { 549 FlushReg(info[i].reg); 550 } 551 } 552 } 553} 554 555void Mir2Lir::FlushAllRegs() { 556 FlushAllRegsBody(reg_pool_->core_regs, 557 reg_pool_->num_core_regs); 558 FlushAllRegsBody(reg_pool_->FPRegs, 559 reg_pool_->num_fp_regs); 560 ClobberAllRegs(); 561} 562 563 564// TUNING: rewrite all of this reg stuff. Probably use an attribute table 565bool Mir2Lir::RegClassMatches(int reg_class, int reg) { 566 if (reg_class == kAnyReg) { 567 return true; 568 } else if (reg_class == kCoreReg) { 569 return !IsFpReg(reg); 570 } else { 571 return IsFpReg(reg); 572 } 573} 574 575void Mir2Lir::MarkLive(int reg, int s_reg) { 576 RegisterInfo* info = GetRegInfo(reg); 577 if ((info->reg == reg) && (info->s_reg == s_reg) && info->live) { 578 return; /* already live */ 579 } else if (s_reg != INVALID_SREG) { 580 ClobberSReg(s_reg); 581 if (info->is_temp) { 582 info->live = true; 583 } 584 } else { 585 /* Can't be live if no associated s_reg */ 586 DCHECK(info->is_temp); 587 info->live = false; 588 } 589 info->s_reg = s_reg; 590} 591 592void Mir2Lir::MarkTemp(int reg) { 593 RegisterInfo* info = GetRegInfo(reg); 594 tempreg_info_.Insert(info); 595 info->is_temp = true; 596} 597 598void Mir2Lir::UnmarkTemp(int reg) { 599 RegisterInfo* info = GetRegInfo(reg); 600 tempreg_info_.Delete(info); 601 info->is_temp = false; 602} 603 604void Mir2Lir::MarkPair(int low_reg, int high_reg) { 605 DCHECK_NE(low_reg, high_reg); 606 RegisterInfo* info_lo = GetRegInfo(low_reg); 607 RegisterInfo* info_hi = GetRegInfo(high_reg); 608 info_lo->pair = info_hi->pair = true; 609 info_lo->partner = high_reg; 610 info_hi->partner = low_reg; 611} 612 613void Mir2Lir::MarkClean(RegLocation loc) { 614 RegisterInfo* info = GetRegInfo(loc.low_reg); 615 info->dirty = false; 616 if (loc.wide) { 617 info = GetRegInfo(loc.high_reg); 618 info->dirty = false; 619 } 620} 621 622void Mir2Lir::MarkDirty(RegLocation loc) { 623 if (loc.home) { 624 // If already home, can't be dirty 625 return; 626 } 627 RegisterInfo* info = GetRegInfo(loc.low_reg); 628 info->dirty = true; 629 if (loc.wide) { 630 info = GetRegInfo(loc.high_reg); 631 info->dirty = true; 632 } 633} 634 635void Mir2Lir::MarkInUse(int reg) { 636 RegisterInfo* info = GetRegInfo(reg); 637 info->in_use = true; 638} 639 640void Mir2Lir::CopyRegInfo(int new_reg, int old_reg) { 641 RegisterInfo* new_info = GetRegInfo(new_reg); 642 RegisterInfo* old_info = GetRegInfo(old_reg); 643 // Target temp status must not change 644 bool is_temp = new_info->is_temp; 645 *new_info = *old_info; 646 // Restore target's temp status 647 new_info->is_temp = is_temp; 648 new_info->reg = new_reg; 649} 650 651bool Mir2Lir::CheckCorePoolSanity() { 652 for (static int i = 0; i < reg_pool_->num_core_regs; i++) { 653 if (reg_pool_->core_regs[i].pair) { 654 static int my_reg = reg_pool_->core_regs[i].reg; 655 static int my_sreg = reg_pool_->core_regs[i].s_reg; 656 static int partner_reg = reg_pool_->core_regs[i].partner; 657 static RegisterInfo* partner = GetRegInfo(partner_reg); 658 DCHECK(partner != NULL); 659 DCHECK(partner->pair); 660 DCHECK_EQ(my_reg, partner->partner); 661 static int partner_sreg = partner->s_reg; 662 if (my_sreg == INVALID_SREG) { 663 DCHECK_EQ(partner_sreg, INVALID_SREG); 664 } else { 665 int diff = my_sreg - partner_sreg; 666 DCHECK((diff == -1) || (diff == 1)); 667 } 668 } 669 if (!reg_pool_->core_regs[i].live) { 670 DCHECK(reg_pool_->core_regs[i].def_start == NULL); 671 DCHECK(reg_pool_->core_regs[i].def_end == NULL); 672 } 673 } 674 return true; 675} 676 677/* 678 * Return an updated location record with current in-register status. 679 * If the value lives in live temps, reflect that fact. No code 680 * is generated. If the live value is part of an older pair, 681 * clobber both low and high. 682 * TUNING: clobbering both is a bit heavy-handed, but the alternative 683 * is a bit complex when dealing with FP regs. Examine code to see 684 * if it's worthwhile trying to be more clever here. 685 */ 686 687RegLocation Mir2Lir::UpdateLoc(RegLocation loc) { 688 DCHECK(!loc.wide); 689 DCHECK(CheckCorePoolSanity()); 690 if (loc.location != kLocPhysReg) { 691 DCHECK((loc.location == kLocDalvikFrame) || 692 (loc.location == kLocCompilerTemp)); 693 RegisterInfo* info_lo = AllocLive(loc.s_reg_low, kAnyReg); 694 if (info_lo) { 695 if (info_lo->pair) { 696 Clobber(info_lo->reg); 697 Clobber(info_lo->partner); 698 FreeTemp(info_lo->reg); 699 } else { 700 loc.low_reg = info_lo->reg; 701 loc.location = kLocPhysReg; 702 } 703 } 704 } 705 706 return loc; 707} 708 709/* see comments for update_loc */ 710RegLocation Mir2Lir::UpdateLocWide(RegLocation loc) { 711 DCHECK(loc.wide); 712 DCHECK(CheckCorePoolSanity()); 713 if (loc.location != kLocPhysReg) { 714 DCHECK((loc.location == kLocDalvikFrame) || 715 (loc.location == kLocCompilerTemp)); 716 // Are the dalvik regs already live in physical registers? 717 RegisterInfo* info_lo = AllocLive(loc.s_reg_low, kAnyReg); 718 RegisterInfo* info_hi = AllocLive(GetSRegHi(loc.s_reg_low), kAnyReg); 719 bool match = true; 720 match = match && (info_lo != NULL); 721 match = match && (info_hi != NULL); 722 // Are they both core or both FP? 723 match = match && (IsFpReg(info_lo->reg) == IsFpReg(info_hi->reg)); 724 // If a pair of floating point singles, are they properly aligned? 725 if (match && IsFpReg(info_lo->reg)) { 726 match &= ((info_lo->reg & 0x1) == 0); 727 match &= ((info_hi->reg - info_lo->reg) == 1); 728 } 729 // If previously used as a pair, it is the same pair? 730 if (match && (info_lo->pair || info_hi->pair)) { 731 match = (info_lo->pair == info_hi->pair); 732 match &= ((info_lo->reg == info_hi->partner) && 733 (info_hi->reg == info_lo->partner)); 734 } 735 if (match) { 736 // Can reuse - update the register usage info 737 loc.low_reg = info_lo->reg; 738 loc.high_reg = info_hi->reg; 739 loc.location = kLocPhysReg; 740 MarkPair(loc.low_reg, loc.high_reg); 741 DCHECK(!IsFpReg(loc.low_reg) || ((loc.low_reg & 0x1) == 0)); 742 return loc; 743 } 744 // Can't easily reuse - clobber and free any overlaps 745 if (info_lo) { 746 Clobber(info_lo->reg); 747 FreeTemp(info_lo->reg); 748 if (info_lo->pair) 749 Clobber(info_lo->partner); 750 } 751 if (info_hi) { 752 Clobber(info_hi->reg); 753 FreeTemp(info_hi->reg); 754 if (info_hi->pair) 755 Clobber(info_hi->partner); 756 } 757 } 758 return loc; 759} 760 761 762/* For use in cases we don't know (or care) width */ 763RegLocation Mir2Lir::UpdateRawLoc(RegLocation loc) { 764 if (loc.wide) 765 return UpdateLocWide(loc); 766 else 767 return UpdateLoc(loc); 768} 769 770RegLocation Mir2Lir::EvalLocWide(RegLocation loc, int reg_class, bool update) { 771 DCHECK(loc.wide); 772 int32_t new_regs; 773 int32_t low_reg; 774 int32_t high_reg; 775 776 loc = UpdateLocWide(loc); 777 778 /* If already in registers, we can assume proper form. Right reg class? */ 779 if (loc.location == kLocPhysReg) { 780 DCHECK_EQ(IsFpReg(loc.low_reg), IsFpReg(loc.high_reg)); 781 DCHECK(!IsFpReg(loc.low_reg) || ((loc.low_reg & 0x1) == 0)); 782 if (!RegClassMatches(reg_class, loc.low_reg)) { 783 /* Wrong register class. Reallocate and copy */ 784 new_regs = AllocTypedTempPair(loc.fp, reg_class); 785 low_reg = new_regs & 0xff; 786 high_reg = (new_regs >> 8) & 0xff; 787 OpRegCopyWide(low_reg, high_reg, loc.low_reg, loc.high_reg); 788 CopyRegInfo(low_reg, loc.low_reg); 789 CopyRegInfo(high_reg, loc.high_reg); 790 Clobber(loc.low_reg); 791 Clobber(loc.high_reg); 792 loc.low_reg = low_reg; 793 loc.high_reg = high_reg; 794 MarkPair(loc.low_reg, loc.high_reg); 795 DCHECK(!IsFpReg(loc.low_reg) || ((loc.low_reg & 0x1) == 0)); 796 } 797 return loc; 798 } 799 800 DCHECK_NE(loc.s_reg_low, INVALID_SREG); 801 DCHECK_NE(GetSRegHi(loc.s_reg_low), INVALID_SREG); 802 803 new_regs = AllocTypedTempPair(loc.fp, reg_class); 804 loc.low_reg = new_regs & 0xff; 805 loc.high_reg = (new_regs >> 8) & 0xff; 806 807 MarkPair(loc.low_reg, loc.high_reg); 808 if (update) { 809 loc.location = kLocPhysReg; 810 MarkLive(loc.low_reg, loc.s_reg_low); 811 // Does this wide value live in two registers or one vector register? 812 if (loc.low_reg != loc.high_reg) { 813 MarkLive(loc.high_reg, GetSRegHi(loc.s_reg_low)); 814 } 815 } 816 DCHECK(!IsFpReg(loc.low_reg) || ((loc.low_reg & 0x1) == 0)); 817 return loc; 818} 819 820RegLocation Mir2Lir::EvalLoc(RegLocation loc, int reg_class, bool update) { 821 int new_reg; 822 823 if (loc.wide) 824 return EvalLocWide(loc, reg_class, update); 825 826 loc = UpdateLoc(loc); 827 828 if (loc.location == kLocPhysReg) { 829 if (!RegClassMatches(reg_class, loc.low_reg)) { 830 /* Wrong register class. Realloc, copy and transfer ownership */ 831 new_reg = AllocTypedTemp(loc.fp, reg_class); 832 OpRegCopy(new_reg, loc.low_reg); 833 CopyRegInfo(new_reg, loc.low_reg); 834 Clobber(loc.low_reg); 835 loc.low_reg = new_reg; 836 } 837 return loc; 838 } 839 840 DCHECK_NE(loc.s_reg_low, INVALID_SREG); 841 842 new_reg = AllocTypedTemp(loc.fp, reg_class); 843 loc.low_reg = new_reg; 844 845 if (update) { 846 loc.location = kLocPhysReg; 847 MarkLive(loc.low_reg, loc.s_reg_low); 848 } 849 return loc; 850} 851 852/* USE SSA names to count references of base Dalvik v_regs. */ 853void Mir2Lir::CountRefs(RefCounts* core_counts, RefCounts* fp_counts, size_t num_regs) { 854 for (int i = 0; i < mir_graph_->GetNumSSARegs(); i++) { 855 RegLocation loc = mir_graph_->reg_location_[i]; 856 RefCounts* counts = loc.fp ? fp_counts : core_counts; 857 int p_map_idx = SRegToPMap(loc.s_reg_low); 858 if (loc.fp) { 859 if (loc.wide) { 860 // Treat doubles as a unit, using upper half of fp_counts array. 861 counts[p_map_idx + num_regs].count += mir_graph_->GetUseCount(i); 862 i++; 863 } else { 864 counts[p_map_idx].count += mir_graph_->GetUseCount(i); 865 } 866 } else if (!IsInexpensiveConstant(loc)) { 867 counts[p_map_idx].count += mir_graph_->GetUseCount(i); 868 } 869 } 870} 871 872/* qsort callback function, sort descending */ 873static int SortCounts(const void *val1, const void *val2) { 874 const Mir2Lir::RefCounts* op1 = reinterpret_cast<const Mir2Lir::RefCounts*>(val1); 875 const Mir2Lir::RefCounts* op2 = reinterpret_cast<const Mir2Lir::RefCounts*>(val2); 876 // Note that we fall back to sorting on reg so we get stable output 877 // on differing qsort implementations (such as on host and target or 878 // between local host and build servers). 879 return (op1->count == op2->count) 880 ? (op1->s_reg - op2->s_reg) 881 : (op1->count < op2->count ? 1 : -1); 882} 883 884void Mir2Lir::DumpCounts(const RefCounts* arr, int size, const char* msg) { 885 LOG(INFO) << msg; 886 for (int i = 0; i < size; i++) { 887 if ((arr[i].s_reg & STARTING_DOUBLE_SREG) != 0) { 888 LOG(INFO) << "s_reg[D" << (arr[i].s_reg & ~STARTING_DOUBLE_SREG) << "]: " << arr[i].count; 889 } else { 890 LOG(INFO) << "s_reg[" << arr[i].s_reg << "]: " << arr[i].count; 891 } 892 } 893} 894 895/* 896 * Note: some portions of this code required even if the kPromoteRegs 897 * optimization is disabled. 898 */ 899void Mir2Lir::DoPromotion() { 900 int reg_bias = cu_->num_compiler_temps + 1; 901 int dalvik_regs = cu_->num_dalvik_registers; 902 int num_regs = dalvik_regs + reg_bias; 903 const int promotion_threshold = 1; 904 905 // Allow target code to add any special registers 906 AdjustSpillMask(); 907 908 /* 909 * Simple register promotion. Just do a static count of the uses 910 * of Dalvik registers. Note that we examine the SSA names, but 911 * count based on original Dalvik register name. Count refs 912 * separately based on type in order to give allocation 913 * preference to fp doubles - which must be allocated sequential 914 * physical single fp registers starting with an even-numbered 915 * reg. 916 * TUNING: replace with linear scan once we have the ability 917 * to describe register live ranges for GC. 918 */ 919 RefCounts *core_regs = 920 static_cast<RefCounts*>(arena_->Alloc(sizeof(RefCounts) * num_regs, 921 ArenaAllocator::kAllocRegAlloc)); 922 RefCounts *FpRegs = 923 static_cast<RefCounts *>(arena_->Alloc(sizeof(RefCounts) * num_regs * 2, 924 ArenaAllocator::kAllocRegAlloc)); 925 // Set ssa names for original Dalvik registers 926 for (int i = 0; i < dalvik_regs; i++) { 927 core_regs[i].s_reg = FpRegs[i].s_reg = i; 928 } 929 // Set ssa name for Method* 930 core_regs[dalvik_regs].s_reg = mir_graph_->GetMethodSReg(); 931 FpRegs[dalvik_regs].s_reg = mir_graph_->GetMethodSReg(); // For consistecy. 932 FpRegs[dalvik_regs + num_regs].s_reg = mir_graph_->GetMethodSReg(); // for consistency. 933 // Set ssa names for compiler_temps 934 for (int i = 1; i <= cu_->num_compiler_temps; i++) { 935 CompilerTemp* ct = mir_graph_->compiler_temps_.Get(i); 936 core_regs[dalvik_regs + i].s_reg = ct->s_reg; 937 FpRegs[dalvik_regs + i].s_reg = ct->s_reg; 938 FpRegs[num_regs + dalvik_regs + i].s_reg = ct->s_reg; 939 } 940 941 // Duplicate in upper half to represent possible fp double starting sregs. 942 for (int i = 0; i < num_regs; i++) { 943 FpRegs[num_regs + i].s_reg = FpRegs[i].s_reg | STARTING_DOUBLE_SREG; 944 } 945 946 // Sum use counts of SSA regs by original Dalvik vreg. 947 CountRefs(core_regs, FpRegs, num_regs); 948 949 950 // Sort the count arrays 951 qsort(core_regs, num_regs, sizeof(RefCounts), SortCounts); 952 qsort(FpRegs, num_regs * 2, sizeof(RefCounts), SortCounts); 953 954 if (cu_->verbose) { 955 DumpCounts(core_regs, num_regs, "Core regs after sort"); 956 DumpCounts(FpRegs, num_regs * 2, "Fp regs after sort"); 957 } 958 959 if (!(cu_->disable_opt & (1 << kPromoteRegs))) { 960 // Promote FpRegs 961 for (int i = 0; (i < (num_regs * 2)) && (FpRegs[i].count >= promotion_threshold); i++) { 962 int p_map_idx = SRegToPMap(FpRegs[i].s_reg & ~STARTING_DOUBLE_SREG); 963 if ((FpRegs[i].s_reg & STARTING_DOUBLE_SREG) != 0) { 964 if ((promotion_map_[p_map_idx].fp_location != kLocPhysReg) && 965 (promotion_map_[p_map_idx + 1].fp_location != kLocPhysReg)) { 966 int low_sreg = FpRegs[i].s_reg & ~STARTING_DOUBLE_SREG; 967 // Ignore result - if can't alloc double may still be able to alloc singles. 968 AllocPreservedDouble(low_sreg); 969 } 970 } else if (promotion_map_[p_map_idx].fp_location != kLocPhysReg) { 971 int reg = AllocPreservedSingle(FpRegs[i].s_reg); 972 if (reg < 0) { 973 break; // No more left. 974 } 975 } 976 } 977 978 // Promote core regs 979 for (int i = 0; (i < num_regs) && 980 (core_regs[i].count >= promotion_threshold); i++) { 981 int p_map_idx = SRegToPMap(core_regs[i].s_reg); 982 if (promotion_map_[p_map_idx].core_location != 983 kLocPhysReg) { 984 int reg = AllocPreservedCoreReg(core_regs[i].s_reg); 985 if (reg < 0) { 986 break; // No more left 987 } 988 } 989 } 990 } 991 992 // Now, update SSA names to new home locations 993 for (int i = 0; i < mir_graph_->GetNumSSARegs(); i++) { 994 RegLocation *curr = &mir_graph_->reg_location_[i]; 995 int p_map_idx = SRegToPMap(curr->s_reg_low); 996 if (!curr->wide) { 997 if (curr->fp) { 998 if (promotion_map_[p_map_idx].fp_location == kLocPhysReg) { 999 curr->location = kLocPhysReg; 1000 curr->low_reg = promotion_map_[p_map_idx].FpReg; 1001 curr->home = true; 1002 } 1003 } else { 1004 if (promotion_map_[p_map_idx].core_location == kLocPhysReg) { 1005 curr->location = kLocPhysReg; 1006 curr->low_reg = promotion_map_[p_map_idx].core_reg; 1007 curr->home = true; 1008 } 1009 } 1010 curr->high_reg = INVALID_REG; 1011 } else { 1012 if (curr->high_word) { 1013 continue; 1014 } 1015 if (curr->fp) { 1016 if ((promotion_map_[p_map_idx].fp_location == kLocPhysReg) && 1017 (promotion_map_[p_map_idx+1].fp_location == 1018 kLocPhysReg)) { 1019 int low_reg = promotion_map_[p_map_idx].FpReg; 1020 int high_reg = promotion_map_[p_map_idx+1].FpReg; 1021 // Doubles require pair of singles starting at even reg 1022 if (((low_reg & 0x1) == 0) && ((low_reg + 1) == high_reg)) { 1023 curr->location = kLocPhysReg; 1024 curr->low_reg = low_reg; 1025 curr->high_reg = high_reg; 1026 curr->home = true; 1027 } 1028 } 1029 } else { 1030 if ((promotion_map_[p_map_idx].core_location == kLocPhysReg) 1031 && (promotion_map_[p_map_idx+1].core_location == 1032 kLocPhysReg)) { 1033 curr->location = kLocPhysReg; 1034 curr->low_reg = promotion_map_[p_map_idx].core_reg; 1035 curr->high_reg = promotion_map_[p_map_idx+1].core_reg; 1036 curr->home = true; 1037 } 1038 } 1039 } 1040 } 1041 if (cu_->verbose) { 1042 DumpPromotionMap(); 1043 } 1044} 1045 1046/* Returns sp-relative offset in bytes for a VReg */ 1047int Mir2Lir::VRegOffset(int v_reg) { 1048 return StackVisitor::GetVRegOffset(cu_->code_item, core_spill_mask_, 1049 fp_spill_mask_, frame_size_, v_reg); 1050} 1051 1052/* Returns sp-relative offset in bytes for a SReg */ 1053int Mir2Lir::SRegOffset(int s_reg) { 1054 return VRegOffset(mir_graph_->SRegToVReg(s_reg)); 1055} 1056 1057/* Mark register usage state and return long retloc */ 1058RegLocation Mir2Lir::GetReturnWide(bool is_double) { 1059 RegLocation gpr_res = LocCReturnWide(); 1060 RegLocation fpr_res = LocCReturnDouble(); 1061 RegLocation res = is_double ? fpr_res : gpr_res; 1062 Clobber(res.low_reg); 1063 Clobber(res.high_reg); 1064 LockTemp(res.low_reg); 1065 LockTemp(res.high_reg); 1066 // Does this wide value live in two registers or one vector register? 1067 if (res.low_reg != res.high_reg) { 1068 MarkPair(res.low_reg, res.high_reg); 1069 } 1070 return res; 1071} 1072 1073RegLocation Mir2Lir::GetReturn(bool is_float) { 1074 RegLocation gpr_res = LocCReturn(); 1075 RegLocation fpr_res = LocCReturnFloat(); 1076 RegLocation res = is_float ? fpr_res : gpr_res; 1077 Clobber(res.low_reg); 1078 if (cu_->instruction_set == kMips) { 1079 MarkInUse(res.low_reg); 1080 } else { 1081 LockTemp(res.low_reg); 1082 } 1083 return res; 1084} 1085 1086void Mir2Lir::SimpleRegAlloc() { 1087 DoPromotion(); 1088 1089 if (cu_->verbose && !(cu_->disable_opt & (1 << kPromoteRegs))) { 1090 LOG(INFO) << "After Promotion"; 1091 mir_graph_->DumpRegLocTable(mir_graph_->reg_location_, mir_graph_->GetNumSSARegs()); 1092 } 1093 1094 /* Set the frame size */ 1095 frame_size_ = ComputeFrameSize(); 1096} 1097 1098/* 1099 * Get the "real" sreg number associated with an s_reg slot. In general, 1100 * s_reg values passed through codegen are the SSA names created by 1101 * dataflow analysis and refer to slot numbers in the mir_graph_->reg_location 1102 * array. However, renaming is accomplished by simply replacing RegLocation 1103 * entries in the reglocation[] array. Therefore, when location 1104 * records for operands are first created, we need to ask the locRecord 1105 * identified by the dataflow pass what it's new name is. 1106 */ 1107int Mir2Lir::GetSRegHi(int lowSreg) { 1108 return (lowSreg == INVALID_SREG) ? INVALID_SREG : lowSreg + 1; 1109} 1110 1111bool Mir2Lir::oat_live_out(int s_reg) { 1112 // For now. 1113 return true; 1114} 1115 1116int Mir2Lir::oatSSASrc(MIR* mir, int num) { 1117 DCHECK_GT(mir->ssa_rep->num_uses, num); 1118 return mir->ssa_rep->uses[num]; 1119} 1120 1121} // namespace art 1122