| OLD | NEW |
|---|
| (Empty) |
| 1 // Copyright 2011 the V8 project authors. All rights reserved. | |
| 2 // Use of this source code is governed by a BSD-style license that can be | |
| 3 // found in the LICENSE file. | |
| 4 | |
| 5 #if V8_TARGET_ARCH_IA32 | |
| 6 | |
| 7 #include "src/ia32/lithium-codegen-ia32.h" | |
| 8 #include "src/ia32/lithium-gap-resolver-ia32.h" | |
| 9 #include "src/register-configuration.h" | |
| 10 | |
| 11 namespace v8 { | |
| 12 namespace internal { | |
| 13 | |
| 14 LGapResolver::LGapResolver(LCodeGen* owner) | |
| 15 : cgen_(owner), | |
| 16 moves_(32, owner->zone()), | |
| 17 source_uses_(), | |
| 18 destination_uses_(), | |
| 19 spilled_register_(-1) {} | |
| 20 | |
| 21 | |
| 22 void LGapResolver::Resolve(LParallelMove* parallel_move) { | |
| 23 DCHECK(HasBeenReset()); | |
| 24 // Build up a worklist of moves. | |
| 25 BuildInitialMoveList(parallel_move); | |
| 26 | |
| 27 for (int i = 0; i < moves_.length(); ++i) { | |
| 28 LMoveOperands move = moves_[i]; | |
| 29 // Skip constants to perform them last. They don't block other moves | |
| 30 // and skipping such moves with register destinations keeps those | |
| 31 // registers free for the whole algorithm. | |
| 32 if (!move.IsEliminated() && !move.source()->IsConstantOperand()) { | |
| 33 PerformMove(i); | |
| 34 } | |
| 35 } | |
| 36 | |
| 37 // Perform the moves with constant sources. | |
| 38 for (int i = 0; i < moves_.length(); ++i) { | |
| 39 if (!moves_[i].IsEliminated()) { | |
| 40 DCHECK(moves_[i].source()->IsConstantOperand()); | |
| 41 EmitMove(i); | |
| 42 } | |
| 43 } | |
| 44 | |
| 45 Finish(); | |
| 46 DCHECK(HasBeenReset()); | |
| 47 } | |
| 48 | |
| 49 | |
| 50 void LGapResolver::BuildInitialMoveList(LParallelMove* parallel_move) { | |
| 51 // Perform a linear sweep of the moves to add them to the initial list of | |
| 52 // moves to perform, ignoring any move that is redundant (the source is | |
| 53 // the same as the destination, the destination is ignored and | |
| 54 // unallocated, or the move was already eliminated). | |
| 55 const ZoneList<LMoveOperands>* moves = parallel_move->move_operands(); | |
| 56 for (int i = 0; i < moves->length(); ++i) { | |
| 57 LMoveOperands move = moves->at(i); | |
| 58 if (!move.IsRedundant()) AddMove(move); | |
| 59 } | |
| 60 Verify(); | |
| 61 } | |
| 62 | |
| 63 | |
| 64 void LGapResolver::PerformMove(int index) { | |
| 65 // Each call to this function performs a move and deletes it from the move | |
| 66 // graph. We first recursively perform any move blocking this one. We | |
| 67 // mark a move as "pending" on entry to PerformMove in order to detect | |
| 68 // cycles in the move graph. We use operand swaps to resolve cycles, | |
| 69 // which means that a call to PerformMove could change any source operand | |
| 70 // in the move graph. | |
| 71 | |
| 72 DCHECK(!moves_[index].IsPending()); | |
| 73 DCHECK(!moves_[index].IsRedundant()); | |
| 74 | |
| 75 // Clear this move's destination to indicate a pending move. The actual | |
| 76 // destination is saved on the side. | |
| 77 DCHECK(moves_[index].source() != NULL); // Or else it will look eliminated. | |
| 78 LOperand* destination = moves_[index].destination(); | |
| 79 moves_[index].set_destination(NULL); | |
| 80 | |
| 81 // Perform a depth-first traversal of the move graph to resolve | |
| 82 // dependencies. Any unperformed, unpending move with a source the same | |
| 83 // as this one's destination blocks this one so recursively perform all | |
| 84 // such moves. | |
| 85 for (int i = 0; i < moves_.length(); ++i) { | |
| 86 LMoveOperands other_move = moves_[i]; | |
| 87 if (other_move.Blocks(destination) && !other_move.IsPending()) { | |
| 88 // Though PerformMove can change any source operand in the move graph, | |
| 89 // this call cannot create a blocking move via a swap (this loop does | |
| 90 // not miss any). Assume there is a non-blocking move with source A | |
| 91 // and this move is blocked on source B and there is a swap of A and | |
| 92 // B. Then A and B must be involved in the same cycle (or they would | |
| 93 // not be swapped). Since this move's destination is B and there is | |
| 94 // only a single incoming edge to an operand, this move must also be | |
| 95 // involved in the same cycle. In that case, the blocking move will | |
| 96 // be created but will be "pending" when we return from PerformMove. | |
| 97 PerformMove(i); | |
| 98 } | |
| 99 } | |
| 100 | |
| 101 // We are about to resolve this move and don't need it marked as | |
| 102 // pending, so restore its destination. | |
| 103 moves_[index].set_destination(destination); | |
| 104 | |
| 105 // This move's source may have changed due to swaps to resolve cycles and | |
| 106 // so it may now be the last move in the cycle. If so remove it. | |
| 107 if (moves_[index].source()->Equals(destination)) { | |
| 108 RemoveMove(index); | |
| 109 return; | |
| 110 } | |
| 111 | |
| 112 // The move may be blocked on a (at most one) pending move, in which case | |
| 113 // we have a cycle. Search for such a blocking move and perform a swap to | |
| 114 // resolve it. | |
| 115 for (int i = 0; i < moves_.length(); ++i) { | |
| 116 LMoveOperands other_move = moves_[i]; | |
| 117 if (other_move.Blocks(destination)) { | |
| 118 DCHECK(other_move.IsPending()); | |
| 119 EmitSwap(index); | |
| 120 return; | |
| 121 } | |
| 122 } | |
| 123 | |
| 124 // This move is not blocked. | |
| 125 EmitMove(index); | |
| 126 } | |
| 127 | |
| 128 | |
| 129 void LGapResolver::AddMove(LMoveOperands move) { | |
| 130 LOperand* source = move.source(); | |
| 131 if (source->IsRegister()) ++source_uses_[source->index()]; | |
| 132 | |
| 133 LOperand* destination = move.destination(); | |
| 134 if (destination->IsRegister()) ++destination_uses_[destination->index()]; | |
| 135 | |
| 136 moves_.Add(move, cgen_->zone()); | |
| 137 } | |
| 138 | |
| 139 | |
| 140 void LGapResolver::RemoveMove(int index) { | |
| 141 LOperand* source = moves_[index].source(); | |
| 142 if (source->IsRegister()) { | |
| 143 --source_uses_[source->index()]; | |
| 144 DCHECK(source_uses_[source->index()] >= 0); | |
| 145 } | |
| 146 | |
| 147 LOperand* destination = moves_[index].destination(); | |
| 148 if (destination->IsRegister()) { | |
| 149 --destination_uses_[destination->index()]; | |
| 150 DCHECK(destination_uses_[destination->index()] >= 0); | |
| 151 } | |
| 152 | |
| 153 moves_[index].Eliminate(); | |
| 154 } | |
| 155 | |
| 156 | |
| 157 int LGapResolver::CountSourceUses(LOperand* operand) { | |
| 158 int count = 0; | |
| 159 for (int i = 0; i < moves_.length(); ++i) { | |
| 160 if (!moves_[i].IsEliminated() && moves_[i].source()->Equals(operand)) { | |
| 161 ++count; | |
| 162 } | |
| 163 } | |
| 164 return count; | |
| 165 } | |
| 166 | |
| 167 | |
| 168 Register LGapResolver::GetFreeRegisterNot(Register reg) { | |
| 169 int skip_index = reg.is(no_reg) ? -1 : reg.code(); | |
| 170 const RegisterConfiguration* config = RegisterConfiguration::ArchDefault(); | |
| 171 for (int i = 0; i < config->num_allocatable_general_registers(); ++i) { | |
| 172 int code = config->GetAllocatableGeneralCode(i); | |
| 173 if (source_uses_[code] == 0 && destination_uses_[code] > 0 && | |
| 174 code != skip_index) { | |
| 175 return Register::from_code(code); | |
| 176 } | |
| 177 } | |
| 178 return no_reg; | |
| 179 } | |
| 180 | |
| 181 | |
| 182 bool LGapResolver::HasBeenReset() { | |
| 183 if (!moves_.is_empty()) return false; | |
| 184 if (spilled_register_ >= 0) return false; | |
| 185 const RegisterConfiguration* config = RegisterConfiguration::ArchDefault(); | |
| 186 for (int i = 0; i < config->num_allocatable_general_registers(); ++i) { | |
| 187 int code = config->GetAllocatableGeneralCode(i); | |
| 188 if (source_uses_[code] != 0) return false; | |
| 189 if (destination_uses_[code] != 0) return false; | |
| 190 } | |
| 191 return true; | |
| 192 } | |
| 193 | |
| 194 | |
| 195 void LGapResolver::Verify() { | |
| 196 #ifdef ENABLE_SLOW_DCHECKS | |
| 197 // No operand should be the destination for more than one move. | |
| 198 for (int i = 0; i < moves_.length(); ++i) { | |
| 199 LOperand* destination = moves_[i].destination(); | |
| 200 for (int j = i + 1; j < moves_.length(); ++j) { | |
| 201 SLOW_DCHECK(!destination->Equals(moves_[j].destination())); | |
| 202 } | |
| 203 } | |
| 204 #endif | |
| 205 } | |
| 206 | |
| 207 | |
| 208 #define __ ACCESS_MASM(cgen_->masm()) | |
| 209 | |
| 210 void LGapResolver::Finish() { | |
| 211 if (spilled_register_ >= 0) { | |
| 212 __ pop(Register::from_code(spilled_register_)); | |
| 213 spilled_register_ = -1; | |
| 214 } | |
| 215 moves_.Rewind(0); | |
| 216 } | |
| 217 | |
| 218 | |
| 219 void LGapResolver::EnsureRestored(LOperand* operand) { | |
| 220 if (operand->IsRegister() && operand->index() == spilled_register_) { | |
| 221 __ pop(Register::from_code(spilled_register_)); | |
| 222 spilled_register_ = -1; | |
| 223 } | |
| 224 } | |
| 225 | |
| 226 | |
| 227 Register LGapResolver::EnsureTempRegister() { | |
| 228 // 1. We may have already spilled to create a temp register. | |
| 229 if (spilled_register_ >= 0) { | |
| 230 return Register::from_code(spilled_register_); | |
| 231 } | |
| 232 | |
| 233 // 2. We may have a free register that we can use without spilling. | |
| 234 Register free = GetFreeRegisterNot(no_reg); | |
| 235 if (!free.is(no_reg)) return free; | |
| 236 | |
| 237 // 3. Prefer to spill a register that is not used in any remaining move | |
| 238 // because it will not need to be restored until the end. | |
| 239 const RegisterConfiguration* config = RegisterConfiguration::ArchDefault(); | |
| 240 for (int i = 0; i < config->num_allocatable_general_registers(); ++i) { | |
| 241 int code = config->GetAllocatableGeneralCode(i); | |
| 242 if (source_uses_[code] == 0 && destination_uses_[code] == 0) { | |
| 243 Register scratch = Register::from_code(code); | |
| 244 __ push(scratch); | |
| 245 spilled_register_ = code; | |
| 246 return scratch; | |
| 247 } | |
| 248 } | |
| 249 | |
| 250 // 4. Use an arbitrary register. Register 0 is as arbitrary as any other. | |
| 251 spilled_register_ = config->GetAllocatableGeneralCode(0); | |
| 252 Register scratch = Register::from_code(spilled_register_); | |
| 253 __ push(scratch); | |
| 254 return scratch; | |
| 255 } | |
| 256 | |
| 257 | |
| 258 void LGapResolver::EmitMove(int index) { | |
| 259 LOperand* source = moves_[index].source(); | |
| 260 LOperand* destination = moves_[index].destination(); | |
| 261 EnsureRestored(source); | |
| 262 EnsureRestored(destination); | |
| 263 | |
| 264 // Dispatch on the source and destination operand kinds. Not all | |
| 265 // combinations are possible. | |
| 266 if (source->IsRegister()) { | |
| 267 DCHECK(destination->IsRegister() || destination->IsStackSlot()); | |
| 268 Register src = cgen_->ToRegister(source); | |
| 269 Operand dst = cgen_->ToOperand(destination); | |
| 270 __ mov(dst, src); | |
| 271 | |
| 272 } else if (source->IsStackSlot()) { | |
| 273 DCHECK(destination->IsRegister() || destination->IsStackSlot()); | |
| 274 Operand src = cgen_->ToOperand(source); | |
| 275 if (destination->IsRegister()) { | |
| 276 Register dst = cgen_->ToRegister(destination); | |
| 277 __ mov(dst, src); | |
| 278 } else { | |
| 279 // Spill on demand to use a temporary register for memory-to-memory | |
| 280 // moves. | |
| 281 Register tmp = EnsureTempRegister(); | |
| 282 Operand dst = cgen_->ToOperand(destination); | |
| 283 __ mov(tmp, src); | |
| 284 __ mov(dst, tmp); | |
| 285 } | |
| 286 | |
| 287 } else if (source->IsConstantOperand()) { | |
| 288 LConstantOperand* constant_source = LConstantOperand::cast(source); | |
| 289 if (destination->IsRegister()) { | |
| 290 Register dst = cgen_->ToRegister(destination); | |
| 291 Representation r = cgen_->IsSmi(constant_source) | |
| 292 ? Representation::Smi() : Representation::Integer32(); | |
| 293 if (cgen_->IsInteger32(constant_source)) { | |
| 294 __ Move(dst, cgen_->ToImmediate(constant_source, r)); | |
| 295 } else { | |
| 296 __ LoadObject(dst, cgen_->ToHandle(constant_source)); | |
| 297 } | |
| 298 } else if (destination->IsDoubleRegister()) { | |
| 299 double v = cgen_->ToDouble(constant_source); | |
| 300 uint64_t int_val = bit_cast<uint64_t, double>(v); | |
| 301 int32_t lower = static_cast<int32_t>(int_val); | |
| 302 int32_t upper = static_cast<int32_t>(int_val >> kBitsPerInt); | |
| 303 XMMRegister dst = cgen_->ToDoubleRegister(destination); | |
| 304 if (int_val == 0) { | |
| 305 __ xorps(dst, dst); | |
| 306 } else { | |
| 307 __ push(Immediate(upper)); | |
| 308 __ push(Immediate(lower)); | |
| 309 __ movsd(dst, Operand(esp, 0)); | |
| 310 __ add(esp, Immediate(kDoubleSize)); | |
| 311 } | |
| 312 } else { | |
| 313 DCHECK(destination->IsStackSlot()); | |
| 314 Operand dst = cgen_->ToOperand(destination); | |
| 315 Representation r = cgen_->IsSmi(constant_source) | |
| 316 ? Representation::Smi() : Representation::Integer32(); | |
| 317 if (cgen_->IsInteger32(constant_source)) { | |
| 318 __ Move(dst, cgen_->ToImmediate(constant_source, r)); | |
| 319 } else { | |
| 320 Register tmp = EnsureTempRegister(); | |
| 321 __ LoadObject(tmp, cgen_->ToHandle(constant_source)); | |
| 322 __ mov(dst, tmp); | |
| 323 } | |
| 324 } | |
| 325 | |
| 326 } else if (source->IsDoubleRegister()) { | |
| 327 XMMRegister src = cgen_->ToDoubleRegister(source); | |
| 328 if (destination->IsDoubleRegister()) { | |
| 329 XMMRegister dst = cgen_->ToDoubleRegister(destination); | |
| 330 __ movaps(dst, src); | |
| 331 } else { | |
| 332 DCHECK(destination->IsDoubleStackSlot()); | |
| 333 Operand dst = cgen_->ToOperand(destination); | |
| 334 __ movsd(dst, src); | |
| 335 } | |
| 336 } else if (source->IsDoubleStackSlot()) { | |
| 337 DCHECK(destination->IsDoubleRegister() || | |
| 338 destination->IsDoubleStackSlot()); | |
| 339 Operand src = cgen_->ToOperand(source); | |
| 340 if (destination->IsDoubleRegister()) { | |
| 341 XMMRegister dst = cgen_->ToDoubleRegister(destination); | |
| 342 __ movsd(dst, src); | |
| 343 } else { | |
| 344 // We rely on having xmm0 available as a fixed scratch register. | |
| 345 Operand dst = cgen_->ToOperand(destination); | |
| 346 __ movsd(xmm0, src); | |
| 347 __ movsd(dst, xmm0); | |
| 348 } | |
| 349 } else { | |
| 350 UNREACHABLE(); | |
| 351 } | |
| 352 | |
| 353 RemoveMove(index); | |
| 354 } | |
| 355 | |
| 356 | |
| 357 void LGapResolver::EmitSwap(int index) { | |
| 358 LOperand* source = moves_[index].source(); | |
| 359 LOperand* destination = moves_[index].destination(); | |
| 360 EnsureRestored(source); | |
| 361 EnsureRestored(destination); | |
| 362 | |
| 363 // Dispatch on the source and destination operand kinds. Not all | |
| 364 // combinations are possible. | |
| 365 if (source->IsRegister() && destination->IsRegister()) { | |
| 366 // Register-register. | |
| 367 Register src = cgen_->ToRegister(source); | |
| 368 Register dst = cgen_->ToRegister(destination); | |
| 369 __ xchg(dst, src); | |
| 370 | |
| 371 } else if ((source->IsRegister() && destination->IsStackSlot()) || | |
| 372 (source->IsStackSlot() && destination->IsRegister())) { | |
| 373 // Register-memory. Use a free register as a temp if possible. Do not | |
| 374 // spill on demand because the simple spill implementation cannot avoid | |
| 375 // spilling src at this point. | |
| 376 Register tmp = GetFreeRegisterNot(no_reg); | |
| 377 Register reg = | |
| 378 cgen_->ToRegister(source->IsRegister() ? source : destination); | |
| 379 Operand mem = | |
| 380 cgen_->ToOperand(source->IsRegister() ? destination : source); | |
| 381 if (tmp.is(no_reg)) { | |
| 382 __ xor_(reg, mem); | |
| 383 __ xor_(mem, reg); | |
| 384 __ xor_(reg, mem); | |
| 385 } else { | |
| 386 __ mov(tmp, mem); | |
| 387 __ mov(mem, reg); | |
| 388 __ mov(reg, tmp); | |
| 389 } | |
| 390 | |
| 391 } else if (source->IsStackSlot() && destination->IsStackSlot()) { | |
| 392 // Memory-memory. Spill on demand to use a temporary. If there is a | |
| 393 // free register after that, use it as a second temporary. | |
| 394 Register tmp0 = EnsureTempRegister(); | |
| 395 Register tmp1 = GetFreeRegisterNot(tmp0); | |
| 396 Operand src = cgen_->ToOperand(source); | |
| 397 Operand dst = cgen_->ToOperand(destination); | |
| 398 if (tmp1.is(no_reg)) { | |
| 399 // Only one temp register available to us. | |
| 400 __ mov(tmp0, dst); | |
| 401 __ xor_(tmp0, src); | |
| 402 __ xor_(src, tmp0); | |
| 403 __ xor_(tmp0, src); | |
| 404 __ mov(dst, tmp0); | |
| 405 } else { | |
| 406 __ mov(tmp0, dst); | |
| 407 __ mov(tmp1, src); | |
| 408 __ mov(dst, tmp1); | |
| 409 __ mov(src, tmp0); | |
| 410 } | |
| 411 } else if (source->IsDoubleRegister() && destination->IsDoubleRegister()) { | |
| 412 // XMM register-register swap. We rely on having xmm0 | |
| 413 // available as a fixed scratch register. | |
| 414 XMMRegister src = cgen_->ToDoubleRegister(source); | |
| 415 XMMRegister dst = cgen_->ToDoubleRegister(destination); | |
| 416 __ movaps(xmm0, src); | |
| 417 __ movaps(src, dst); | |
| 418 __ movaps(dst, xmm0); | |
| 419 } else if (source->IsDoubleRegister() || destination->IsDoubleRegister()) { | |
| 420 // XMM register-memory swap. We rely on having xmm0 | |
| 421 // available as a fixed scratch register. | |
| 422 DCHECK(source->IsDoubleStackSlot() || destination->IsDoubleStackSlot()); | |
| 423 XMMRegister reg = cgen_->ToDoubleRegister(source->IsDoubleRegister() | |
| 424 ? source | |
| 425 : destination); | |
| 426 Operand other = | |
| 427 cgen_->ToOperand(source->IsDoubleRegister() ? destination : source); | |
| 428 __ movsd(xmm0, other); | |
| 429 __ movsd(other, reg); | |
| 430 __ movaps(reg, xmm0); | |
| 431 } else if (source->IsDoubleStackSlot() && destination->IsDoubleStackSlot()) { | |
| 432 // Double-width memory-to-memory. Spill on demand to use a general | |
| 433 // purpose temporary register and also rely on having xmm0 available as | |
| 434 // a fixed scratch register. | |
| 435 Register tmp = EnsureTempRegister(); | |
| 436 Operand src0 = cgen_->ToOperand(source); | |
| 437 Operand src1 = cgen_->HighOperand(source); | |
| 438 Operand dst0 = cgen_->ToOperand(destination); | |
| 439 Operand dst1 = cgen_->HighOperand(destination); | |
| 440 __ movsd(xmm0, dst0); // Save destination in xmm0. | |
| 441 __ mov(tmp, src0); // Then use tmp to copy source to destination. | |
| 442 __ mov(dst0, tmp); | |
| 443 __ mov(tmp, src1); | |
| 444 __ mov(dst1, tmp); | |
| 445 __ movsd(src0, xmm0); | |
| 446 | |
| 447 } else { | |
| 448 // No other combinations are possible. | |
| 449 UNREACHABLE(); | |
| 450 } | |
| 451 | |
| 452 // The swap of source and destination has executed a move from source to | |
| 453 // destination. | |
| 454 RemoveMove(index); | |
| 455 | |
| 456 // Any unperformed (including pending) move with a source of either | |
| 457 // this move's source or destination needs to have their source | |
| 458 // changed to reflect the state of affairs after the swap. | |
| 459 for (int i = 0; i < moves_.length(); ++i) { | |
| 460 LMoveOperands other_move = moves_[i]; | |
| 461 if (other_move.Blocks(source)) { | |
| 462 moves_[i].set_source(destination); | |
| 463 } else if (other_move.Blocks(destination)) { | |
| 464 moves_[i].set_source(source); | |
| 465 } | |
| 466 } | |
| 467 | |
| 468 // In addition to swapping the actual uses as sources, we need to update | |
| 469 // the use counts. | |
| 470 if (source->IsRegister() && destination->IsRegister()) { | |
| 471 int temp = source_uses_[source->index()]; | |
| 472 source_uses_[source->index()] = source_uses_[destination->index()]; | |
| 473 source_uses_[destination->index()] = temp; | |
| 474 } else if (source->IsRegister()) { | |
| 475 // We don't have use counts for non-register operands like destination. | |
| 476 // Compute those counts now. | |
| 477 source_uses_[source->index()] = CountSourceUses(source); | |
| 478 } else if (destination->IsRegister()) { | |
| 479 source_uses_[destination->index()] = CountSourceUses(destination); | |
| 480 } | |
| 481 } | |
| 482 | |
| 483 #undef __ | |
| 484 | |
| 485 } // namespace internal | |
| 486 } // namespace v8 | |
| 487 | |
| 488 #endif // V8_TARGET_ARCH_IA32 | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 1405363003:
Move Hydrogen and Lithium to src/crankshaft/ (Closed)
Base URL: https://chromium.googlesource.com/v8/v8.git@master