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
PrintTo(StringStream * stream)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>
SetUpCache()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>
TearDownCache()118 void LSubKindOperand<kOperandKind, kNumCachedOperands>::TearDownCache() {
119 delete[] cache;
120 }
121
122
SetUpCaches()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
TearDownCaches()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
IsRedundant() const137 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
PrintDataTo(StringStream * stream) const145 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
PrintTo(StringStream * stream)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
RecordPointer(LOperand * op,Zone * zone)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
RemovePointer(LOperand * op)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
RecordUntagged(LOperand * op,Zone * zone)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
PrintTo(StringStream * stream)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
StackSlotOffset(int index)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
LChunk(CompilationInfo * info,HGraph * graph)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
GetLabel(int block_id) const249 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
LookupDestination(int block_id) const256 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
GetAssemblyLabel(int block_id) const264 Label* LChunk::GetAssemblyLabel(int block_id) const {
265 LLabel* label = GetLabel(block_id);
266 ASSERT(!label->HasReplacement());
267 return label->label();
268 }
269
270
MarkEmptyBlocks()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
AddInstruction(LInstruction * instr,HBasicBlock * block)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
DefineConstantOperand(HConstant * constant)326 LConstantOperand* LChunk::DefineConstantOperand(HConstant* constant) {
327 return LConstantOperand::Create(constant->id(), zone());
328 }
329
330
GetParameterStackSlot(int index) const331 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.
ParameterAt(int index)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
GetGapAt(int index) const351 LGap* LChunk::GetGapAt(int index) const {
352 return LGap::cast(instructions_[index]);
353 }
354
355
IsGapAt(int index) const356 bool LChunk::IsGapAt(int index) const {
357 return instructions_[index]->IsGap();
358 }
359
360
NearestGapPos(int index) const361 int LChunk::NearestGapPos(int index) const {
362 while (!IsGapAt(index)) index--;
363 return index;
364 }
365
366
AddGapMove(int index,LOperand * from,LOperand * to)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
LookupConstant(LConstantOperand * operand) const373 HConstant* LChunk::LookupConstant(LConstantOperand* operand) const {
374 return HConstant::cast(graph_->LookupValue(operand->index()));
375 }
376
377
LookupLiteralRepresentation(LConstantOperand * operand) const378 Representation LChunk::LookupLiteralRepresentation(
379 LConstantOperand* operand) const {
380 return graph_->LookupValue(operand->index())->representation();
381 }
382
383
CommitDependencies(Handle<Code> code) const384 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
NewChunk(HGraph * graph)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
Codegen()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
set_allocated_double_registers(BitVector * allocated_registers)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
CreateEnvironment(HEnvironment * hydrogen_env,int * argument_index_accumulator,ZoneList<HValue * > * objects_to_materialize)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.
AddObjectToMaterialize(HValue * value,ZoneList<HValue * > * objects_to_materialize,LEnvironment * result)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
~LPhase()615 LPhase::~LPhase() {
616 if (ShouldProduceTraceOutput()) {
617 isolate()->GetHTracer()->TraceLithium(name(), chunk_);
618 }
619 }
620
621
622 } } // namespace v8::internal
623