Home | History | Annotate | Download | only in src 
      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 
     32 namespace v8 {
     33 namespace internal {
     34 
     35 
     36 void 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 
    102 template<LOperand::Kind kOperandKind, int kNumCachedOperands>
    103 LSubKindOperand<kOperandKind, kNumCachedOperands>*
    104 LSubKindOperand<kOperandKind, kNumCachedOperands>::cache = NULL;
    105 
    106 
    107 template<LOperand::Kind kOperandKind, int kNumCachedOperands>
    108 void 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 
    117 template<LOperand::Kind kOperandKind, int kNumCachedOperands>
    118 void LSubKindOperand<kOperandKind, kNumCachedOperands>::TearDownCache() {
    119   delete[] cache;
    120 }
    121 
    122 
    123 void 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 
    130 void 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 
    137 bool 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 
    145 void 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 
    166 void 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 
    185 void 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 
    193 void 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 
    206 void 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 
    214 void 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 
    224 int 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 
    237 LChunk::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 
    249 LLabel* 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 
    256 int 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 
    264 Label* LChunk::GetAssemblyLabel(int block_id) const {
    265   LLabel* label = GetLabel(block_id);
    266   ASSERT(!label->HasReplacement());
    267   return label->label();
    268 }
    269 
    270 
    271 void 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 
    306 void 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 
    326 LConstantOperand* LChunk::DefineConstantOperand(HConstant* constant) {
    327   return LConstantOperand::Create(constant->id(), zone());
    328 }
    329 
    330 
    331 int 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.
    344 int 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 
    351 LGap* LChunk::GetGapAt(int index) const {
    352   return LGap::cast(instructions_[index]);
    353 }
    354 
    355 
    356 bool LChunk::IsGapAt(int index) const {
    357   return instructions_[index]->IsGap();
    358 }
    359 
    360 
    361 int LChunk::NearestGapPos(int index) const {
    362   while (!IsGapAt(index)) index--;
    363   return index;
    364 }
    365 
    366 
    367 void LChunk::AddGapMove(int index, LOperand* from, LOperand* to) {
    368   GetGapAt(index)->GetOrCreateParallelMove(
    369       LGap::START, zone())->AddMove(from, to, zone());
    370 }
    371 
    372 
    373 HConstant* LChunk::LookupConstant(LConstantOperand* operand) const {
    374   return HConstant::cast(graph_->LookupValue(operand->index()));
    375 }
    376 
    377 
    378 Representation LChunk::LookupLiteralRepresentation(
    379     LConstantOperand* operand) const {
    380   return graph_->LookupValue(operand->index())->representation();
    381 }
    382 
    383 
    384 void 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 
    405 LChunk* 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 
    432 Handle<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 
    466 void 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 
    483 LEnvironment* 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.
    565 void 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 
    615 LPhase::~LPhase() {
    616   if (ShouldProduceTraceOutput()) {
    617     isolate()->GetHTracer()->TraceLithium(name(), chunk_);
    618   }
    619 }
    620 
    621 
    622 } }  // namespace v8::internal
    623