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