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