lithium.h revision 85b71799222b55eb5dd74ea26efe0c64ab655c8c
1// Copyright 2011 the V8 project authors. All rights reserved. 2// Redistribution and use in source and binary forms, with or without 3// modification, are permitted provided that the following conditions are 4// met: 5// 6// * Redistributions of source code must retain the above copyright 7// notice, this list of conditions and the following disclaimer. 8// * Redistributions in binary form must reproduce the above 9// copyright notice, this list of conditions and the following 10// disclaimer in the documentation and/or other materials provided 11// with the distribution. 12// * Neither the name of Google Inc. nor the names of its 13// contributors may be used to endorse or promote products derived 14// from this software without specific prior written permission. 15// 16// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 28#ifndef V8_LITHIUM_H_ 29#define V8_LITHIUM_H_ 30 31#include "allocation.h" 32#include "hydrogen.h" 33#include "safepoint-table.h" 34 35namespace v8 { 36namespace internal { 37 38class LOperand: public ZoneObject { 39 public: 40 enum Kind { 41 INVALID, 42 UNALLOCATED, 43 CONSTANT_OPERAND, 44 STACK_SLOT, 45 DOUBLE_STACK_SLOT, 46 REGISTER, 47 DOUBLE_REGISTER, 48 ARGUMENT 49 }; 50 51 LOperand() : value_(KindField::encode(INVALID)) { } 52 53 Kind kind() const { return KindField::decode(value_); } 54 int index() const { return static_cast<int>(value_) >> kKindFieldWidth; } 55 bool IsConstantOperand() const { return kind() == CONSTANT_OPERAND; } 56 bool IsStackSlot() const { return kind() == STACK_SLOT; } 57 bool IsDoubleStackSlot() const { return kind() == DOUBLE_STACK_SLOT; } 58 bool IsRegister() const { return kind() == REGISTER; } 59 bool IsDoubleRegister() const { return kind() == DOUBLE_REGISTER; } 60 bool IsArgument() const { return kind() == ARGUMENT; } 61 bool IsUnallocated() const { return kind() == UNALLOCATED; } 62 bool Equals(LOperand* other) const { return value_ == other->value_; } 63 int VirtualRegister(); 64 65 void PrintTo(StringStream* stream); 66 void ConvertTo(Kind kind, int index) { 67 value_ = KindField::encode(kind); 68 value_ |= index << kKindFieldWidth; 69 ASSERT(this->index() == index); 70 } 71 72 protected: 73 static const int kKindFieldWidth = 3; 74 class KindField : public BitField<Kind, 0, kKindFieldWidth> { }; 75 76 LOperand(Kind kind, int index) { ConvertTo(kind, index); } 77 78 unsigned value_; 79}; 80 81 82class LUnallocated: public LOperand { 83 public: 84 enum Policy { 85 NONE, 86 ANY, 87 FIXED_REGISTER, 88 FIXED_DOUBLE_REGISTER, 89 FIXED_SLOT, 90 MUST_HAVE_REGISTER, 91 WRITABLE_REGISTER, 92 SAME_AS_FIRST_INPUT, 93 IGNORE 94 }; 95 96 // Lifetime of operand inside the instruction. 97 enum Lifetime { 98 // USED_AT_START operand is guaranteed to be live only at 99 // instruction start. Register allocator is free to assign the same register 100 // to some other operand used inside instruction (i.e. temporary or 101 // output). 102 USED_AT_START, 103 104 // USED_AT_END operand is treated as live until the end of 105 // instruction. This means that register allocator will not reuse it's 106 // register for any other operand inside instruction. 107 USED_AT_END 108 }; 109 110 explicit LUnallocated(Policy policy) : LOperand(UNALLOCATED, 0) { 111 Initialize(policy, 0, USED_AT_END); 112 } 113 114 LUnallocated(Policy policy, int fixed_index) : LOperand(UNALLOCATED, 0) { 115 Initialize(policy, fixed_index, USED_AT_END); 116 } 117 118 LUnallocated(Policy policy, Lifetime lifetime) : LOperand(UNALLOCATED, 0) { 119 Initialize(policy, 0, lifetime); 120 } 121 122 // The superclass has a KindField. Some policies have a signed fixed 123 // index in the upper bits. 124 static const int kPolicyWidth = 4; 125 static const int kLifetimeWidth = 1; 126 static const int kVirtualRegisterWidth = 17; 127 128 static const int kPolicyShift = kKindFieldWidth; 129 static const int kLifetimeShift = kPolicyShift + kPolicyWidth; 130 static const int kVirtualRegisterShift = kLifetimeShift + kLifetimeWidth; 131 static const int kFixedIndexShift = 132 kVirtualRegisterShift + kVirtualRegisterWidth; 133 134 class PolicyField : public BitField<Policy, kPolicyShift, kPolicyWidth> { }; 135 136 class LifetimeField 137 : public BitField<Lifetime, kLifetimeShift, kLifetimeWidth> { 138 }; 139 140 class VirtualRegisterField 141 : public BitField<unsigned, 142 kVirtualRegisterShift, 143 kVirtualRegisterWidth> { 144 }; 145 146 static const int kMaxVirtualRegisters = 1 << (kVirtualRegisterWidth + 1); 147 static const int kMaxFixedIndex = 63; 148 static const int kMinFixedIndex = -64; 149 150 bool HasIgnorePolicy() const { return policy() == IGNORE; } 151 bool HasNoPolicy() const { return policy() == NONE; } 152 bool HasAnyPolicy() const { 153 return policy() == ANY; 154 } 155 bool HasFixedPolicy() const { 156 return policy() == FIXED_REGISTER || 157 policy() == FIXED_DOUBLE_REGISTER || 158 policy() == FIXED_SLOT; 159 } 160 bool HasRegisterPolicy() const { 161 return policy() == WRITABLE_REGISTER || policy() == MUST_HAVE_REGISTER; 162 } 163 bool HasSameAsInputPolicy() const { 164 return policy() == SAME_AS_FIRST_INPUT; 165 } 166 Policy policy() const { return PolicyField::decode(value_); } 167 void set_policy(Policy policy) { 168 value_ = PolicyField::update(value_, policy); 169 } 170 int fixed_index() const { 171 return static_cast<int>(value_) >> kFixedIndexShift; 172 } 173 174 unsigned virtual_register() const { 175 return VirtualRegisterField::decode(value_); 176 } 177 178 void set_virtual_register(unsigned id) { 179 value_ = VirtualRegisterField::update(value_, id); 180 } 181 182 LUnallocated* CopyUnconstrained() { 183 LUnallocated* result = new LUnallocated(ANY); 184 result->set_virtual_register(virtual_register()); 185 return result; 186 } 187 188 static LUnallocated* cast(LOperand* op) { 189 ASSERT(op->IsUnallocated()); 190 return reinterpret_cast<LUnallocated*>(op); 191 } 192 193 bool IsUsedAtStart() { 194 return LifetimeField::decode(value_) == USED_AT_START; 195 } 196 197 private: 198 void Initialize(Policy policy, int fixed_index, Lifetime lifetime) { 199 value_ |= PolicyField::encode(policy); 200 value_ |= LifetimeField::encode(lifetime); 201 value_ |= fixed_index << kFixedIndexShift; 202 ASSERT(this->fixed_index() == fixed_index); 203 } 204}; 205 206 207class LMoveOperands BASE_EMBEDDED { 208 public: 209 LMoveOperands(LOperand* source, LOperand* destination) 210 : source_(source), destination_(destination) { 211 } 212 213 LOperand* source() const { return source_; } 214 void set_source(LOperand* operand) { source_ = operand; } 215 216 LOperand* destination() const { return destination_; } 217 void set_destination(LOperand* operand) { destination_ = operand; } 218 219 // The gap resolver marks moves as "in-progress" by clearing the 220 // destination (but not the source). 221 bool IsPending() const { 222 return destination_ == NULL && source_ != NULL; 223 } 224 225 // True if this move a move into the given destination operand. 226 bool Blocks(LOperand* operand) const { 227 return !IsEliminated() && source()->Equals(operand); 228 } 229 230 // A move is redundant if it's been eliminated, if its source and 231 // destination are the same, or if its destination is unneeded. 232 bool IsRedundant() const { 233 return IsEliminated() || source_->Equals(destination_) || IsIgnored(); 234 } 235 236 bool IsIgnored() const { 237 return destination_ != NULL && 238 destination_->IsUnallocated() && 239 LUnallocated::cast(destination_)->HasIgnorePolicy(); 240 } 241 242 // We clear both operands to indicate move that's been eliminated. 243 void Eliminate() { source_ = destination_ = NULL; } 244 bool IsEliminated() const { 245 ASSERT(source_ != NULL || destination_ == NULL); 246 return source_ == NULL; 247 } 248 249 private: 250 LOperand* source_; 251 LOperand* destination_; 252}; 253 254 255class LConstantOperand: public LOperand { 256 public: 257 static LConstantOperand* Create(int index) { 258 ASSERT(index >= 0); 259 if (index < kNumCachedOperands) return &cache[index]; 260 return new LConstantOperand(index); 261 } 262 263 static LConstantOperand* cast(LOperand* op) { 264 ASSERT(op->IsConstantOperand()); 265 return reinterpret_cast<LConstantOperand*>(op); 266 } 267 268 static void SetupCache(); 269 270 private: 271 static const int kNumCachedOperands = 128; 272 static LConstantOperand cache[]; 273 274 LConstantOperand() : LOperand() { } 275 explicit LConstantOperand(int index) : LOperand(CONSTANT_OPERAND, index) { } 276}; 277 278 279class LArgument: public LOperand { 280 public: 281 explicit LArgument(int index) : LOperand(ARGUMENT, index) { } 282 283 static LArgument* cast(LOperand* op) { 284 ASSERT(op->IsArgument()); 285 return reinterpret_cast<LArgument*>(op); 286 } 287}; 288 289 290class LStackSlot: public LOperand { 291 public: 292 static LStackSlot* Create(int index) { 293 ASSERT(index >= 0); 294 if (index < kNumCachedOperands) return &cache[index]; 295 return new LStackSlot(index); 296 } 297 298 static LStackSlot* cast(LOperand* op) { 299 ASSERT(op->IsStackSlot()); 300 return reinterpret_cast<LStackSlot*>(op); 301 } 302 303 static void SetupCache(); 304 305 private: 306 static const int kNumCachedOperands = 128; 307 static LStackSlot cache[]; 308 309 LStackSlot() : LOperand() { } 310 explicit LStackSlot(int index) : LOperand(STACK_SLOT, index) { } 311}; 312 313 314class LDoubleStackSlot: public LOperand { 315 public: 316 static LDoubleStackSlot* Create(int index) { 317 ASSERT(index >= 0); 318 if (index < kNumCachedOperands) return &cache[index]; 319 return new LDoubleStackSlot(index); 320 } 321 322 static LDoubleStackSlot* cast(LOperand* op) { 323 ASSERT(op->IsStackSlot()); 324 return reinterpret_cast<LDoubleStackSlot*>(op); 325 } 326 327 static void SetupCache(); 328 329 private: 330 static const int kNumCachedOperands = 128; 331 static LDoubleStackSlot cache[]; 332 333 LDoubleStackSlot() : LOperand() { } 334 explicit LDoubleStackSlot(int index) : LOperand(DOUBLE_STACK_SLOT, index) { } 335}; 336 337 338class LRegister: public LOperand { 339 public: 340 static LRegister* Create(int index) { 341 ASSERT(index >= 0); 342 if (index < kNumCachedOperands) return &cache[index]; 343 return new LRegister(index); 344 } 345 346 static LRegister* cast(LOperand* op) { 347 ASSERT(op->IsRegister()); 348 return reinterpret_cast<LRegister*>(op); 349 } 350 351 static void SetupCache(); 352 353 private: 354 static const int kNumCachedOperands = 16; 355 static LRegister cache[]; 356 357 LRegister() : LOperand() { } 358 explicit LRegister(int index) : LOperand(REGISTER, index) { } 359}; 360 361 362class LDoubleRegister: public LOperand { 363 public: 364 static LDoubleRegister* Create(int index) { 365 ASSERT(index >= 0); 366 if (index < kNumCachedOperands) return &cache[index]; 367 return new LDoubleRegister(index); 368 } 369 370 static LDoubleRegister* cast(LOperand* op) { 371 ASSERT(op->IsDoubleRegister()); 372 return reinterpret_cast<LDoubleRegister*>(op); 373 } 374 375 static void SetupCache(); 376 377 private: 378 static const int kNumCachedOperands = 16; 379 static LDoubleRegister cache[]; 380 381 LDoubleRegister() : LOperand() { } 382 explicit LDoubleRegister(int index) : LOperand(DOUBLE_REGISTER, index) { } 383}; 384 385 386class LParallelMove : public ZoneObject { 387 public: 388 LParallelMove() : move_operands_(4) { } 389 390 void AddMove(LOperand* from, LOperand* to) { 391 move_operands_.Add(LMoveOperands(from, to)); 392 } 393 394 bool IsRedundant() const; 395 396 const ZoneList<LMoveOperands>* move_operands() const { 397 return &move_operands_; 398 } 399 400 void PrintDataTo(StringStream* stream) const; 401 402 private: 403 ZoneList<LMoveOperands> move_operands_; 404}; 405 406 407class LPointerMap: public ZoneObject { 408 public: 409 explicit LPointerMap(int position) 410 : pointer_operands_(8), position_(position), lithium_position_(-1) { } 411 412 const ZoneList<LOperand*>* operands() const { return &pointer_operands_; } 413 int position() const { return position_; } 414 int lithium_position() const { return lithium_position_; } 415 416 void set_lithium_position(int pos) { 417 ASSERT(lithium_position_ == -1); 418 lithium_position_ = pos; 419 } 420 421 void RecordPointer(LOperand* op); 422 void PrintTo(StringStream* stream); 423 424 private: 425 ZoneList<LOperand*> pointer_operands_; 426 int position_; 427 int lithium_position_; 428}; 429 430 431class LEnvironment: public ZoneObject { 432 public: 433 LEnvironment(Handle<JSFunction> closure, 434 int ast_id, 435 int parameter_count, 436 int argument_count, 437 int value_count, 438 LEnvironment* outer) 439 : closure_(closure), 440 arguments_stack_height_(argument_count), 441 deoptimization_index_(Safepoint::kNoDeoptimizationIndex), 442 translation_index_(-1), 443 ast_id_(ast_id), 444 parameter_count_(parameter_count), 445 pc_offset_(-1), 446 values_(value_count), 447 representations_(value_count), 448 spilled_registers_(NULL), 449 spilled_double_registers_(NULL), 450 outer_(outer) { 451 } 452 453 Handle<JSFunction> closure() const { return closure_; } 454 int arguments_stack_height() const { return arguments_stack_height_; } 455 int deoptimization_index() const { return deoptimization_index_; } 456 int translation_index() const { return translation_index_; } 457 int ast_id() const { return ast_id_; } 458 int parameter_count() const { return parameter_count_; } 459 int pc_offset() const { return pc_offset_; } 460 LOperand** spilled_registers() const { return spilled_registers_; } 461 LOperand** spilled_double_registers() const { 462 return spilled_double_registers_; 463 } 464 const ZoneList<LOperand*>* values() const { return &values_; } 465 LEnvironment* outer() const { return outer_; } 466 467 void AddValue(LOperand* operand, Representation representation) { 468 values_.Add(operand); 469 representations_.Add(representation); 470 } 471 472 bool HasTaggedValueAt(int index) const { 473 return representations_[index].IsTagged(); 474 } 475 476 void Register(int deoptimization_index, 477 int translation_index, 478 int pc_offset) { 479 ASSERT(!HasBeenRegistered()); 480 deoptimization_index_ = deoptimization_index; 481 translation_index_ = translation_index; 482 pc_offset_ = pc_offset; 483 } 484 bool HasBeenRegistered() const { 485 return deoptimization_index_ != Safepoint::kNoDeoptimizationIndex; 486 } 487 488 void SetSpilledRegisters(LOperand** registers, 489 LOperand** double_registers) { 490 spilled_registers_ = registers; 491 spilled_double_registers_ = double_registers; 492 } 493 494 void PrintTo(StringStream* stream); 495 496 private: 497 Handle<JSFunction> closure_; 498 int arguments_stack_height_; 499 int deoptimization_index_; 500 int translation_index_; 501 int ast_id_; 502 int parameter_count_; 503 int pc_offset_; 504 ZoneList<LOperand*> values_; 505 ZoneList<Representation> representations_; 506 507 // Allocation index indexed arrays of spill slot operands for registers 508 // that are also in spill slots at an OSR entry. NULL for environments 509 // that do not correspond to an OSR entry. 510 LOperand** spilled_registers_; 511 LOperand** spilled_double_registers_; 512 513 LEnvironment* outer_; 514 515 friend class LCodegen; 516}; 517 518 519// Iterates over the non-null, non-constant operands in an environment. 520class ShallowIterator BASE_EMBEDDED { 521 public: 522 explicit ShallowIterator(LEnvironment* env) 523 : env_(env), 524 limit_(env != NULL ? env->values()->length() : 0), 525 current_(0) { 526 SkipUninteresting(); 527 } 528 529 bool Done() { return current_ >= limit_; } 530 531 LOperand* Current() { 532 ASSERT(!Done()); 533 return env_->values()->at(current_); 534 } 535 536 void Advance() { 537 ASSERT(!Done()); 538 ++current_; 539 SkipUninteresting(); 540 } 541 542 LEnvironment* env() { return env_; } 543 544 private: 545 bool ShouldSkip(LOperand* op) { 546 return op == NULL || op->IsConstantOperand() || op->IsArgument(); 547 } 548 549 // Skip until something interesting, beginning with and including current_. 550 void SkipUninteresting() { 551 while (current_ < limit_ && ShouldSkip(env_->values()->at(current_))) { 552 ++current_; 553 } 554 } 555 556 LEnvironment* env_; 557 int limit_; 558 int current_; 559}; 560 561 562// Iterator for non-null, non-constant operands incl. outer environments. 563class DeepIterator BASE_EMBEDDED { 564 public: 565 explicit DeepIterator(LEnvironment* env) 566 : current_iterator_(env) { 567 SkipUninteresting(); 568 } 569 570 bool Done() { return current_iterator_.Done(); } 571 572 LOperand* Current() { 573 ASSERT(!current_iterator_.Done()); 574 return current_iterator_.Current(); 575 } 576 577 void Advance() { 578 current_iterator_.Advance(); 579 SkipUninteresting(); 580 } 581 582 private: 583 void SkipUninteresting() { 584 while (current_iterator_.env() != NULL && current_iterator_.Done()) { 585 current_iterator_ = ShallowIterator(current_iterator_.env()->outer()); 586 } 587 } 588 589 ShallowIterator current_iterator_; 590}; 591 592 593int ElementsKindToShiftSize(ElementsKind elements_kind); 594 595 596} } // namespace v8::internal 597 598#endif // V8_LITHIUM_H_ 599