1// Copyright 2012 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#include "src/lithium.h" 6 7#include "src/v8.h" 8 9#include "src/scopes.h" 10#include "src/serialize.h" 11 12#if V8_TARGET_ARCH_IA32 13#include "src/ia32/lithium-ia32.h" // NOLINT 14#include "src/ia32/lithium-codegen-ia32.h" // NOLINT 15#elif V8_TARGET_ARCH_X64 16#include "src/x64/lithium-x64.h" // NOLINT 17#include "src/x64/lithium-codegen-x64.h" // NOLINT 18#elif V8_TARGET_ARCH_ARM 19#include "src/arm/lithium-arm.h" // NOLINT 20#include "src/arm/lithium-codegen-arm.h" // NOLINT 21#elif V8_TARGET_ARCH_MIPS 22#include "src/mips/lithium-mips.h" // NOLINT 23#include "src/mips/lithium-codegen-mips.h" // NOLINT 24#elif V8_TARGET_ARCH_ARM64 25#include "src/arm64/lithium-arm64.h" // NOLINT 26#include "src/arm64/lithium-codegen-arm64.h" // NOLINT 27#elif V8_TARGET_ARCH_MIPS64 28#include "src/mips64/lithium-mips64.h" // NOLINT 29#include "src/mips64/lithium-codegen-mips64.h" // NOLINT 30#elif V8_TARGET_ARCH_X87 31#include "src/x87/lithium-x87.h" // NOLINT 32#include "src/x87/lithium-codegen-x87.h" // NOLINT 33#else 34#error "Unknown architecture." 35#endif 36 37namespace v8 { 38namespace internal { 39 40 41void LOperand::PrintTo(StringStream* stream) { 42 LUnallocated* unalloc = NULL; 43 switch (kind()) { 44 case INVALID: 45 stream->Add("(0)"); 46 break; 47 case UNALLOCATED: 48 unalloc = LUnallocated::cast(this); 49 stream->Add("v%d", unalloc->virtual_register()); 50 if (unalloc->basic_policy() == LUnallocated::FIXED_SLOT) { 51 stream->Add("(=%dS)", unalloc->fixed_slot_index()); 52 break; 53 } 54 switch (unalloc->extended_policy()) { 55 case LUnallocated::NONE: 56 break; 57 case LUnallocated::FIXED_REGISTER: { 58 int reg_index = unalloc->fixed_register_index(); 59 if (reg_index < 0 || 60 reg_index >= Register::kMaxNumAllocatableRegisters) { 61 stream->Add("(=invalid_reg#%d)", reg_index); 62 } else { 63 const char* register_name = 64 Register::AllocationIndexToString(reg_index); 65 stream->Add("(=%s)", register_name); 66 } 67 break; 68 } 69 case LUnallocated::FIXED_DOUBLE_REGISTER: { 70 int reg_index = unalloc->fixed_register_index(); 71 if (reg_index < 0 || 72 reg_index >= DoubleRegister::kMaxNumAllocatableRegisters) { 73 stream->Add("(=invalid_double_reg#%d)", reg_index); 74 } else { 75 const char* double_register_name = 76 DoubleRegister::AllocationIndexToString(reg_index); 77 stream->Add("(=%s)", double_register_name); 78 } 79 break; 80 } 81 case LUnallocated::MUST_HAVE_REGISTER: 82 stream->Add("(R)"); 83 break; 84 case LUnallocated::MUST_HAVE_DOUBLE_REGISTER: 85 stream->Add("(D)"); 86 break; 87 case LUnallocated::WRITABLE_REGISTER: 88 stream->Add("(WR)"); 89 break; 90 case LUnallocated::SAME_AS_FIRST_INPUT: 91 stream->Add("(1)"); 92 break; 93 case LUnallocated::ANY: 94 stream->Add("(-)"); 95 break; 96 } 97 break; 98 case CONSTANT_OPERAND: 99 stream->Add("[constant:%d]", index()); 100 break; 101 case STACK_SLOT: 102 stream->Add("[stack:%d]", index()); 103 break; 104 case DOUBLE_STACK_SLOT: 105 stream->Add("[double_stack:%d]", index()); 106 break; 107 case REGISTER: { 108 int reg_index = index(); 109 if (reg_index < 0 || reg_index >= Register::kMaxNumAllocatableRegisters) { 110 stream->Add("(=invalid_reg#%d|R)", reg_index); 111 } else { 112 stream->Add("[%s|R]", Register::AllocationIndexToString(reg_index)); 113 } 114 break; 115 } 116 case DOUBLE_REGISTER: { 117 int reg_index = index(); 118 if (reg_index < 0 || 119 reg_index >= DoubleRegister::kMaxNumAllocatableRegisters) { 120 stream->Add("(=invalid_double_reg#%d|R)", reg_index); 121 } else { 122 stream->Add("[%s|R]", 123 DoubleRegister::AllocationIndexToString(reg_index)); 124 } 125 break; 126 } 127 } 128} 129 130 131template<LOperand::Kind kOperandKind, int kNumCachedOperands> 132LSubKindOperand<kOperandKind, kNumCachedOperands>* 133LSubKindOperand<kOperandKind, kNumCachedOperands>::cache = NULL; 134 135 136template<LOperand::Kind kOperandKind, int kNumCachedOperands> 137void LSubKindOperand<kOperandKind, kNumCachedOperands>::SetUpCache() { 138 if (cache) return; 139 cache = new LSubKindOperand[kNumCachedOperands]; 140 for (int i = 0; i < kNumCachedOperands; i++) { 141 cache[i].ConvertTo(kOperandKind, i); 142 } 143} 144 145 146template<LOperand::Kind kOperandKind, int kNumCachedOperands> 147void LSubKindOperand<kOperandKind, kNumCachedOperands>::TearDownCache() { 148 delete[] cache; 149 cache = NULL; 150} 151 152 153void LOperand::SetUpCaches() { 154#define LITHIUM_OPERAND_SETUP(name, type, number) L##name::SetUpCache(); 155 LITHIUM_OPERAND_LIST(LITHIUM_OPERAND_SETUP) 156#undef LITHIUM_OPERAND_SETUP 157} 158 159 160void LOperand::TearDownCaches() { 161#define LITHIUM_OPERAND_TEARDOWN(name, type, number) L##name::TearDownCache(); 162 LITHIUM_OPERAND_LIST(LITHIUM_OPERAND_TEARDOWN) 163#undef LITHIUM_OPERAND_TEARDOWN 164} 165 166 167bool LParallelMove::IsRedundant() const { 168 for (int i = 0; i < move_operands_.length(); ++i) { 169 if (!move_operands_[i].IsRedundant()) return false; 170 } 171 return true; 172} 173 174 175void LParallelMove::PrintDataTo(StringStream* stream) const { 176 bool first = true; 177 for (int i = 0; i < move_operands_.length(); ++i) { 178 if (!move_operands_[i].IsEliminated()) { 179 LOperand* source = move_operands_[i].source(); 180 LOperand* destination = move_operands_[i].destination(); 181 if (!first) stream->Add(" "); 182 first = false; 183 if (source->Equals(destination)) { 184 destination->PrintTo(stream); 185 } else { 186 destination->PrintTo(stream); 187 stream->Add(" = "); 188 source->PrintTo(stream); 189 } 190 stream->Add(";"); 191 } 192 } 193} 194 195 196void LEnvironment::PrintTo(StringStream* stream) { 197 stream->Add("[id=%d|", ast_id().ToInt()); 198 if (deoptimization_index() != Safepoint::kNoDeoptimizationIndex) { 199 stream->Add("deopt_id=%d|", deoptimization_index()); 200 } 201 stream->Add("parameters=%d|", parameter_count()); 202 stream->Add("arguments_stack_height=%d|", arguments_stack_height()); 203 for (int i = 0; i < values_.length(); ++i) { 204 if (i != 0) stream->Add(";"); 205 if (values_[i] == NULL) { 206 stream->Add("[hole]"); 207 } else { 208 values_[i]->PrintTo(stream); 209 } 210 } 211 stream->Add("]"); 212} 213 214 215void LPointerMap::RecordPointer(LOperand* op, Zone* zone) { 216 // Do not record arguments as pointers. 217 if (op->IsStackSlot() && op->index() < 0) return; 218 DCHECK(!op->IsDoubleRegister() && !op->IsDoubleStackSlot()); 219 pointer_operands_.Add(op, zone); 220} 221 222 223void LPointerMap::RemovePointer(LOperand* op) { 224 // Do not record arguments as pointers. 225 if (op->IsStackSlot() && op->index() < 0) return; 226 DCHECK(!op->IsDoubleRegister() && !op->IsDoubleStackSlot()); 227 for (int i = 0; i < pointer_operands_.length(); ++i) { 228 if (pointer_operands_[i]->Equals(op)) { 229 pointer_operands_.Remove(i); 230 --i; 231 } 232 } 233} 234 235 236void LPointerMap::RecordUntagged(LOperand* op, Zone* zone) { 237 // Do not record arguments as pointers. 238 if (op->IsStackSlot() && op->index() < 0) return; 239 DCHECK(!op->IsDoubleRegister() && !op->IsDoubleStackSlot()); 240 untagged_operands_.Add(op, zone); 241} 242 243 244void LPointerMap::PrintTo(StringStream* stream) { 245 stream->Add("{"); 246 for (int i = 0; i < pointer_operands_.length(); ++i) { 247 if (i != 0) stream->Add(";"); 248 pointer_operands_[i]->PrintTo(stream); 249 } 250 stream->Add("}"); 251} 252 253 254int StackSlotOffset(int index) { 255 if (index >= 0) { 256 // Local or spill slot. Skip the frame pointer, function, and 257 // context in the fixed part of the frame. 258 return -(index + 1) * kPointerSize - 259 StandardFrameConstants::kFixedFrameSizeFromFp; 260 } else { 261 // Incoming parameter. Skip the return address. 262 return -(index + 1) * kPointerSize + kFPOnStackSize + kPCOnStackSize; 263 } 264} 265 266 267LChunk::LChunk(CompilationInfo* info, HGraph* graph) 268 : spill_slot_count_(0), 269 info_(info), 270 graph_(graph), 271 instructions_(32, info->zone()), 272 pointer_maps_(8, info->zone()), 273 inlined_closures_(1, info->zone()), 274 deprecation_dependencies_(MapLess(), MapAllocator(info->zone())), 275 stability_dependencies_(MapLess(), MapAllocator(info->zone())) {} 276 277 278LLabel* LChunk::GetLabel(int block_id) const { 279 HBasicBlock* block = graph_->blocks()->at(block_id); 280 int first_instruction = block->first_instruction_index(); 281 return LLabel::cast(instructions_[first_instruction]); 282} 283 284 285int LChunk::LookupDestination(int block_id) const { 286 LLabel* cur = GetLabel(block_id); 287 while (cur->replacement() != NULL) { 288 cur = cur->replacement(); 289 } 290 return cur->block_id(); 291} 292 293Label* LChunk::GetAssemblyLabel(int block_id) const { 294 LLabel* label = GetLabel(block_id); 295 DCHECK(!label->HasReplacement()); 296 return label->label(); 297} 298 299 300void LChunk::MarkEmptyBlocks() { 301 LPhase phase("L_Mark empty blocks", this); 302 for (int i = 0; i < graph()->blocks()->length(); ++i) { 303 HBasicBlock* block = graph()->blocks()->at(i); 304 int first = block->first_instruction_index(); 305 int last = block->last_instruction_index(); 306 LInstruction* first_instr = instructions()->at(first); 307 LInstruction* last_instr = instructions()->at(last); 308 309 LLabel* label = LLabel::cast(first_instr); 310 if (last_instr->IsGoto()) { 311 LGoto* goto_instr = LGoto::cast(last_instr); 312 if (label->IsRedundant() && 313 !label->is_loop_header()) { 314 bool can_eliminate = true; 315 for (int i = first + 1; i < last && can_eliminate; ++i) { 316 LInstruction* cur = instructions()->at(i); 317 if (cur->IsGap()) { 318 LGap* gap = LGap::cast(cur); 319 if (!gap->IsRedundant()) { 320 can_eliminate = false; 321 } 322 } else { 323 can_eliminate = false; 324 } 325 } 326 if (can_eliminate) { 327 label->set_replacement(GetLabel(goto_instr->block_id())); 328 } 329 } 330 } 331 } 332} 333 334 335void LChunk::AddInstruction(LInstruction* instr, HBasicBlock* block) { 336 LInstructionGap* gap = new (zone()) LInstructionGap(block); 337 gap->set_hydrogen_value(instr->hydrogen_value()); 338 int index = -1; 339 if (instr->IsControl()) { 340 instructions_.Add(gap, zone()); 341 index = instructions_.length(); 342 instructions_.Add(instr, zone()); 343 } else { 344 index = instructions_.length(); 345 instructions_.Add(instr, zone()); 346 instructions_.Add(gap, zone()); 347 } 348 if (instr->HasPointerMap()) { 349 pointer_maps_.Add(instr->pointer_map(), zone()); 350 instr->pointer_map()->set_lithium_position(index); 351 } 352} 353 354 355LConstantOperand* LChunk::DefineConstantOperand(HConstant* constant) { 356 return LConstantOperand::Create(constant->id(), zone()); 357} 358 359 360int LChunk::GetParameterStackSlot(int index) const { 361 // The receiver is at index 0, the first parameter at index 1, so we 362 // shift all parameter indexes down by the number of parameters, and 363 // make sure they end up negative so they are distinguishable from 364 // spill slots. 365 int result = index - info()->num_parameters() - 1; 366 367 DCHECK(result < 0); 368 return result; 369} 370 371 372// A parameter relative to ebp in the arguments stub. 373int LChunk::ParameterAt(int index) { 374 DCHECK(-1 <= index); // -1 is the receiver. 375 return (1 + info()->scope()->num_parameters() - index) * 376 kPointerSize; 377} 378 379 380LGap* LChunk::GetGapAt(int index) const { 381 return LGap::cast(instructions_[index]); 382} 383 384 385bool LChunk::IsGapAt(int index) const { 386 return instructions_[index]->IsGap(); 387} 388 389 390int LChunk::NearestGapPos(int index) const { 391 while (!IsGapAt(index)) index--; 392 return index; 393} 394 395 396void LChunk::AddGapMove(int index, LOperand* from, LOperand* to) { 397 GetGapAt(index)->GetOrCreateParallelMove( 398 LGap::START, zone())->AddMove(from, to, zone()); 399} 400 401 402HConstant* LChunk::LookupConstant(LConstantOperand* operand) const { 403 return HConstant::cast(graph_->LookupValue(operand->index())); 404} 405 406 407Representation LChunk::LookupLiteralRepresentation( 408 LConstantOperand* operand) const { 409 return graph_->LookupValue(operand->index())->representation(); 410} 411 412 413void LChunk::CommitDependencies(Handle<Code> code) const { 414 for (MapSet::const_iterator it = deprecation_dependencies_.begin(), 415 iend = deprecation_dependencies_.end(); it != iend; ++it) { 416 Handle<Map> map = *it; 417 DCHECK(!map->is_deprecated()); 418 DCHECK(map->CanBeDeprecated()); 419 Map::AddDependentCode(map, DependentCode::kTransitionGroup, code); 420 } 421 422 for (MapSet::const_iterator it = stability_dependencies_.begin(), 423 iend = stability_dependencies_.end(); it != iend; ++it) { 424 Handle<Map> map = *it; 425 DCHECK(map->is_stable()); 426 DCHECK(map->CanTransition()); 427 Map::AddDependentCode(map, DependentCode::kPrototypeCheckGroup, code); 428 } 429 430 info_->CommitDependencies(code); 431} 432 433 434LChunk* LChunk::NewChunk(HGraph* graph) { 435 DisallowHandleAllocation no_handles; 436 DisallowHeapAllocation no_gc; 437 graph->DisallowAddingNewValues(); 438 int values = graph->GetMaximumValueID(); 439 CompilationInfo* info = graph->info(); 440 if (values > LUnallocated::kMaxVirtualRegisters) { 441 info->AbortOptimization(kNotEnoughVirtualRegistersForValues); 442 return NULL; 443 } 444 LAllocator allocator(values, graph); 445 LChunkBuilder builder(info, graph, &allocator); 446 LChunk* chunk = builder.Build(); 447 if (chunk == NULL) return NULL; 448 449 if (!allocator.Allocate(chunk)) { 450 info->AbortOptimization(kNotEnoughVirtualRegistersRegalloc); 451 return NULL; 452 } 453 454 chunk->set_allocated_double_registers( 455 allocator.assigned_double_registers()); 456 457 return chunk; 458} 459 460 461Handle<Code> LChunk::Codegen() { 462 MacroAssembler assembler(info()->isolate(), NULL, 0); 463 LOG_CODE_EVENT(info()->isolate(), 464 CodeStartLinePosInfoRecordEvent( 465 assembler.positions_recorder())); 466 // TODO(yangguo) remove this once the code serializer handles code stubs. 467 if (info()->will_serialize()) assembler.enable_serializer(); 468 LCodeGen generator(this, &assembler, info()); 469 470 MarkEmptyBlocks(); 471 472 if (generator.GenerateCode()) { 473 generator.CheckEnvironmentUsage(); 474 CodeGenerator::MakeCodePrologue(info(), "optimized"); 475 Code::Flags flags = info()->flags(); 476 Handle<Code> code = 477 CodeGenerator::MakeCodeEpilogue(&assembler, flags, info()); 478 generator.FinishCode(code); 479 CommitDependencies(code); 480 code->set_is_crankshafted(true); 481 void* jit_handler_data = 482 assembler.positions_recorder()->DetachJITHandlerData(); 483 LOG_CODE_EVENT(info()->isolate(), 484 CodeEndLinePosInfoRecordEvent(*code, jit_handler_data)); 485 486 CodeGenerator::PrintCode(code, info()); 487 DCHECK(!(info()->isolate()->serializer_enabled() && 488 info()->GetMustNotHaveEagerFrame() && 489 generator.NeedsEagerFrame())); 490 return code; 491 } 492 assembler.AbortedCodeGeneration(); 493 return Handle<Code>::null(); 494} 495 496 497void LChunk::set_allocated_double_registers(BitVector* allocated_registers) { 498 allocated_double_registers_ = allocated_registers; 499 BitVector* doubles = allocated_double_registers(); 500 BitVector::Iterator iterator(doubles); 501 while (!iterator.Done()) { 502 if (info()->saves_caller_doubles()) { 503 if (kDoubleSize == kPointerSize * 2) { 504 spill_slot_count_ += 2; 505 } else { 506 spill_slot_count_++; 507 } 508 } 509 iterator.Advance(); 510 } 511} 512 513 514void LChunkBuilderBase::Abort(BailoutReason reason) { 515 info()->AbortOptimization(reason); 516 status_ = ABORTED; 517} 518 519 520void LChunkBuilderBase::Retry(BailoutReason reason) { 521 info()->RetryOptimization(reason); 522 status_ = ABORTED; 523} 524 525 526LEnvironment* LChunkBuilderBase::CreateEnvironment( 527 HEnvironment* hydrogen_env, int* argument_index_accumulator, 528 ZoneList<HValue*>* objects_to_materialize) { 529 if (hydrogen_env == NULL) return NULL; 530 531 LEnvironment* outer = 532 CreateEnvironment(hydrogen_env->outer(), argument_index_accumulator, 533 objects_to_materialize); 534 BailoutId ast_id = hydrogen_env->ast_id(); 535 DCHECK(!ast_id.IsNone() || 536 hydrogen_env->frame_type() != JS_FUNCTION); 537 538 int omitted_count = (hydrogen_env->frame_type() == JS_FUNCTION) 539 ? 0 540 : hydrogen_env->specials_count(); 541 542 int value_count = hydrogen_env->length() - omitted_count; 543 LEnvironment* result = 544 new(zone()) LEnvironment(hydrogen_env->closure(), 545 hydrogen_env->frame_type(), 546 ast_id, 547 hydrogen_env->parameter_count(), 548 argument_count_, 549 value_count, 550 outer, 551 hydrogen_env->entry(), 552 zone()); 553 int argument_index = *argument_index_accumulator; 554 555 // Store the environment description into the environment 556 // (with holes for nested objects) 557 for (int i = 0; i < hydrogen_env->length(); ++i) { 558 if (hydrogen_env->is_special_index(i) && 559 hydrogen_env->frame_type() != JS_FUNCTION) { 560 continue; 561 } 562 LOperand* op; 563 HValue* value = hydrogen_env->values()->at(i); 564 CHECK(!value->IsPushArguments()); // Do not deopt outgoing arguments 565 if (value->IsArgumentsObject() || value->IsCapturedObject()) { 566 op = LEnvironment::materialization_marker(); 567 } else { 568 op = UseAny(value); 569 } 570 result->AddValue(op, 571 value->representation(), 572 value->CheckFlag(HInstruction::kUint32)); 573 } 574 575 // Recursively store the nested objects into the environment 576 for (int i = 0; i < hydrogen_env->length(); ++i) { 577 if (hydrogen_env->is_special_index(i)) continue; 578 579 HValue* value = hydrogen_env->values()->at(i); 580 if (value->IsArgumentsObject() || value->IsCapturedObject()) { 581 AddObjectToMaterialize(value, objects_to_materialize, result); 582 } 583 } 584 585 if (hydrogen_env->frame_type() == JS_FUNCTION) { 586 *argument_index_accumulator = argument_index; 587 } 588 589 return result; 590} 591 592 593// Add an object to the supplied environment and object materialization list. 594// 595// Notes: 596// 597// We are building three lists here: 598// 599// 1. In the result->object_mapping_ list (added to by the 600// LEnvironment::Add*Object methods), we store the lengths (number 601// of fields) of the captured objects in depth-first traversal order, or 602// in case of duplicated objects, we store the index to the duplicate object 603// (with a tag to differentiate between captured and duplicated objects). 604// 605// 2. The object fields are stored in the result->values_ list 606// (added to by the LEnvironment.AddValue method) sequentially as lists 607// of fields with holes for nested objects (the holes will be expanded 608// later by LCodegen::AddToTranslation according to the 609// LEnvironment.object_mapping_ list). 610// 611// 3. The auxiliary objects_to_materialize array stores the hydrogen values 612// in the same order as result->object_mapping_ list. This is used 613// to detect duplicate values and calculate the corresponding object index. 614void LChunkBuilderBase::AddObjectToMaterialize(HValue* value, 615 ZoneList<HValue*>* objects_to_materialize, LEnvironment* result) { 616 int object_index = objects_to_materialize->length(); 617 // Store the hydrogen value into the de-duplication array 618 objects_to_materialize->Add(value, zone()); 619 // Find out whether we are storing a duplicated value 620 int previously_materialized_object = -1; 621 for (int prev = 0; prev < object_index; ++prev) { 622 if (objects_to_materialize->at(prev) == value) { 623 previously_materialized_object = prev; 624 break; 625 } 626 } 627 // Store the captured object length (or duplicated object index) 628 // into the environment. For duplicated objects, we stop here. 629 int length = value->OperandCount(); 630 bool is_arguments = value->IsArgumentsObject(); 631 if (previously_materialized_object >= 0) { 632 result->AddDuplicateObject(previously_materialized_object); 633 return; 634 } else { 635 result->AddNewObject(is_arguments ? length - 1 : length, is_arguments); 636 } 637 // Store the captured object's fields into the environment 638 for (int i = is_arguments ? 1 : 0; i < length; ++i) { 639 LOperand* op; 640 HValue* arg_value = value->OperandAt(i); 641 if (arg_value->IsArgumentsObject() || arg_value->IsCapturedObject()) { 642 // Insert a hole for nested objects 643 op = LEnvironment::materialization_marker(); 644 } else { 645 DCHECK(!arg_value->IsPushArguments()); 646 // For ordinary values, tell the register allocator we need the value 647 // to be alive here 648 op = UseAny(arg_value); 649 } 650 result->AddValue(op, 651 arg_value->representation(), 652 arg_value->CheckFlag(HInstruction::kUint32)); 653 } 654 // Recursively store all the nested captured objects into the environment 655 for (int i = is_arguments ? 1 : 0; i < length; ++i) { 656 HValue* arg_value = value->OperandAt(i); 657 if (arg_value->IsArgumentsObject() || arg_value->IsCapturedObject()) { 658 AddObjectToMaterialize(arg_value, objects_to_materialize, result); 659 } 660 } 661} 662 663 664LPhase::~LPhase() { 665 if (ShouldProduceTraceOutput()) { 666 isolate()->GetHTracer()->TraceLithium(name(), chunk_); 667 } 668} 669 670 671} } // namespace v8::internal 672