1 // Copyright 2012 the V8 project authors. All rights reserved. 2 // Redistribution and use in source and binary forms, with or without 3 // modification, are permitted provided that the following conditions are 4 // met: 5 // 6 // * Redistributions of source code must retain the above copyright 7 // notice, this list of conditions and the following disclaimer. 8 // * Redistributions in binary form must reproduce the above 9 // copyright notice, this list of conditions and the following 10 // disclaimer in the documentation and/or other materials provided 11 // with the distribution. 12 // * Neither the name of Google Inc. nor the names of its 13 // contributors may be used to endorse or promote products derived 14 // from this software without specific prior written permission. 15 // 16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 28 #include "v8.h" 29 #include "lithium.h" 30 #include "scopes.h" 31 32 #if V8_TARGET_ARCH_IA32 33 #include "ia32/lithium-ia32.h" 34 #include "ia32/lithium-codegen-ia32.h" 35 #elif V8_TARGET_ARCH_X64 36 #include "x64/lithium-x64.h" 37 #include "x64/lithium-codegen-x64.h" 38 #elif V8_TARGET_ARCH_ARM 39 #include "arm/lithium-arm.h" 40 #include "arm/lithium-codegen-arm.h" 41 #elif V8_TARGET_ARCH_MIPS 42 #include "mips/lithium-mips.h" 43 #include "mips/lithium-codegen-mips.h" 44 #else 45 #error "Unknown architecture." 46 #endif 47 48 namespace v8 { 49 namespace internal { 50 51 52 void LOperand::PrintTo(StringStream* stream) { 53 LUnallocated* unalloc = NULL; 54 switch (kind()) { 55 case INVALID: 56 stream->Add("(0)"); 57 break; 58 case UNALLOCATED: 59 unalloc = LUnallocated::cast(this); 60 stream->Add("v%d", unalloc->virtual_register()); 61 if (unalloc->basic_policy() == LUnallocated::FIXED_SLOT) { 62 stream->Add("(=%dS)", unalloc->fixed_slot_index()); 63 break; 64 } 65 switch (unalloc->extended_policy()) { 66 case LUnallocated::NONE: 67 break; 68 case LUnallocated::FIXED_REGISTER: { 69 int reg_index = unalloc->fixed_register_index(); 70 const char* register_name = 71 Register::AllocationIndexToString(reg_index); 72 stream->Add("(=%s)", register_name); 73 break; 74 } 75 case LUnallocated::FIXED_DOUBLE_REGISTER: { 76 int reg_index = unalloc->fixed_register_index(); 77 const char* double_register_name = 78 DoubleRegister::AllocationIndexToString(reg_index); 79 stream->Add("(=%s)", double_register_name); 80 break; 81 } 82 case LUnallocated::MUST_HAVE_REGISTER: 83 stream->Add("(R)"); 84 break; 85 case LUnallocated::WRITABLE_REGISTER: 86 stream->Add("(WR)"); 87 break; 88 case LUnallocated::SAME_AS_FIRST_INPUT: 89 stream->Add("(1)"); 90 break; 91 case LUnallocated::ANY: 92 stream->Add("(-)"); 93 break; 94 } 95 break; 96 case CONSTANT_OPERAND: 97 stream->Add("[constant:%d]", index()); 98 break; 99 case STACK_SLOT: 100 stream->Add("[stack:%d]", index()); 101 break; 102 case DOUBLE_STACK_SLOT: 103 stream->Add("[double_stack:%d]", index()); 104 break; 105 case REGISTER: 106 stream->Add("[%s|R]", Register::AllocationIndexToString(index())); 107 break; 108 case DOUBLE_REGISTER: 109 stream->Add("[%s|R]", DoubleRegister::AllocationIndexToString(index())); 110 break; 111 case ARGUMENT: 112 stream->Add("[arg:%d]", index()); 113 break; 114 } 115 } 116 117 #define DEFINE_OPERAND_CACHE(name, type) \ 118 L##name* L##name::cache = NULL; \ 119 \ 120 void L##name::SetUpCache() { \ 121 if (cache) return; \ 122 cache = new L##name[kNumCachedOperands]; \ 123 for (int i = 0; i < kNumCachedOperands; i++) { \ 124 cache[i].ConvertTo(type, i); \ 125 } \ 126 } \ 127 \ 128 void L##name::TearDownCache() { \ 129 delete[] cache; \ 130 } 131 132 LITHIUM_OPERAND_LIST(DEFINE_OPERAND_CACHE) 133 #undef DEFINE_OPERAND_CACHE 134 135 void LOperand::SetUpCaches() { 136 #define LITHIUM_OPERAND_SETUP(name, type) L##name::SetUpCache(); 137 LITHIUM_OPERAND_LIST(LITHIUM_OPERAND_SETUP) 138 #undef LITHIUM_OPERAND_SETUP 139 } 140 141 142 void LOperand::TearDownCaches() { 143 #define LITHIUM_OPERAND_TEARDOWN(name, type) L##name::TearDownCache(); 144 LITHIUM_OPERAND_LIST(LITHIUM_OPERAND_TEARDOWN) 145 #undef LITHIUM_OPERAND_TEARDOWN 146 } 147 148 149 bool LParallelMove::IsRedundant() const { 150 for (int i = 0; i < move_operands_.length(); ++i) { 151 if (!move_operands_[i].IsRedundant()) return false; 152 } 153 return true; 154 } 155 156 157 void LParallelMove::PrintDataTo(StringStream* stream) const { 158 bool first = true; 159 for (int i = 0; i < move_operands_.length(); ++i) { 160 if (!move_operands_[i].IsEliminated()) { 161 LOperand* source = move_operands_[i].source(); 162 LOperand* destination = move_operands_[i].destination(); 163 if (!first) stream->Add(" "); 164 first = false; 165 if (source->Equals(destination)) { 166 destination->PrintTo(stream); 167 } else { 168 destination->PrintTo(stream); 169 stream->Add(" = "); 170 source->PrintTo(stream); 171 } 172 stream->Add(";"); 173 } 174 } 175 } 176 177 178 void LEnvironment::PrintTo(StringStream* stream) { 179 stream->Add("[id=%d|", ast_id().ToInt()); 180 if (deoptimization_index() != Safepoint::kNoDeoptimizationIndex) { 181 stream->Add("deopt_id=%d|", deoptimization_index()); 182 } 183 stream->Add("parameters=%d|", parameter_count()); 184 stream->Add("arguments_stack_height=%d|", arguments_stack_height()); 185 for (int i = 0; i < values_.length(); ++i) { 186 if (i != 0) stream->Add(";"); 187 if (values_[i] == NULL) { 188 stream->Add("[hole]"); 189 } else { 190 values_[i]->PrintTo(stream); 191 } 192 } 193 stream->Add("]"); 194 } 195 196 197 void LPointerMap::RecordPointer(LOperand* op, Zone* zone) { 198 // Do not record arguments as pointers. 199 if (op->IsStackSlot() && op->index() < 0) return; 200 ASSERT(!op->IsDoubleRegister() && !op->IsDoubleStackSlot()); 201 pointer_operands_.Add(op, zone); 202 } 203 204 205 void LPointerMap::RemovePointer(LOperand* op) { 206 // Do not record arguments as pointers. 207 if (op->IsStackSlot() && op->index() < 0) return; 208 ASSERT(!op->IsDoubleRegister() && !op->IsDoubleStackSlot()); 209 for (int i = 0; i < pointer_operands_.length(); ++i) { 210 if (pointer_operands_[i]->Equals(op)) { 211 pointer_operands_.Remove(i); 212 --i; 213 } 214 } 215 } 216 217 218 void LPointerMap::RecordUntagged(LOperand* op, Zone* zone) { 219 // Do not record arguments as pointers. 220 if (op->IsStackSlot() && op->index() < 0) return; 221 ASSERT(!op->IsDoubleRegister() && !op->IsDoubleStackSlot()); 222 untagged_operands_.Add(op, zone); 223 } 224 225 226 void LPointerMap::PrintTo(StringStream* stream) { 227 stream->Add("{"); 228 for (int i = 0; i < pointer_operands_.length(); ++i) { 229 if (i != 0) stream->Add(";"); 230 pointer_operands_[i]->PrintTo(stream); 231 } 232 stream->Add("} @%d", position()); 233 } 234 235 236 int ElementsKindToShiftSize(ElementsKind elements_kind) { 237 switch (elements_kind) { 238 case EXTERNAL_BYTE_ELEMENTS: 239 case EXTERNAL_PIXEL_ELEMENTS: 240 case EXTERNAL_UNSIGNED_BYTE_ELEMENTS: 241 return 0; 242 case EXTERNAL_SHORT_ELEMENTS: 243 case EXTERNAL_UNSIGNED_SHORT_ELEMENTS: 244 return 1; 245 case EXTERNAL_INT_ELEMENTS: 246 case EXTERNAL_UNSIGNED_INT_ELEMENTS: 247 case EXTERNAL_FLOAT_ELEMENTS: 248 return 2; 249 case EXTERNAL_DOUBLE_ELEMENTS: 250 case FAST_DOUBLE_ELEMENTS: 251 case FAST_HOLEY_DOUBLE_ELEMENTS: 252 return 3; 253 case FAST_SMI_ELEMENTS: 254 case FAST_ELEMENTS: 255 case FAST_HOLEY_SMI_ELEMENTS: 256 case FAST_HOLEY_ELEMENTS: 257 case DICTIONARY_ELEMENTS: 258 case NON_STRICT_ARGUMENTS_ELEMENTS: 259 return kPointerSizeLog2; 260 } 261 UNREACHABLE(); 262 return 0; 263 } 264 265 266 int StackSlotOffset(int index) { 267 if (index >= 0) { 268 // Local or spill slot. Skip the frame pointer, function, and 269 // context in the fixed part of the frame. 270 return -(index + 3) * kPointerSize; 271 } else { 272 // Incoming parameter. Skip the return address. 273 return -(index + 1) * kPointerSize + kFPOnStackSize + kPCOnStackSize; 274 } 275 } 276 277 278 LChunk::LChunk(CompilationInfo* info, HGraph* graph) 279 : spill_slot_count_(0), 280 info_(info), 281 graph_(graph), 282 instructions_(32, graph->zone()), 283 pointer_maps_(8, graph->zone()), 284 inlined_closures_(1, graph->zone()) { 285 } 286 287 288 LLabel* LChunk::GetLabel(int block_id) const { 289 HBasicBlock* block = graph_->blocks()->at(block_id); 290 int first_instruction = block->first_instruction_index(); 291 return LLabel::cast(instructions_[first_instruction]); 292 } 293 294 295 int LChunk::LookupDestination(int block_id) const { 296 LLabel* cur = GetLabel(block_id); 297 while (cur->replacement() != NULL) { 298 cur = cur->replacement(); 299 } 300 return cur->block_id(); 301 } 302 303 Label* LChunk::GetAssemblyLabel(int block_id) const { 304 LLabel* label = GetLabel(block_id); 305 ASSERT(!label->HasReplacement()); 306 return label->label(); 307 } 308 309 310 void LChunk::MarkEmptyBlocks() { 311 LPhase phase("L_Mark empty blocks", this); 312 for (int i = 0; i < graph()->blocks()->length(); ++i) { 313 HBasicBlock* block = graph()->blocks()->at(i); 314 int first = block->first_instruction_index(); 315 int last = block->last_instruction_index(); 316 LInstruction* first_instr = instructions()->at(first); 317 LInstruction* last_instr = instructions()->at(last); 318 319 LLabel* label = LLabel::cast(first_instr); 320 if (last_instr->IsGoto()) { 321 LGoto* goto_instr = LGoto::cast(last_instr); 322 if (label->IsRedundant() && 323 !label->is_loop_header()) { 324 bool can_eliminate = true; 325 for (int i = first + 1; i < last && can_eliminate; ++i) { 326 LInstruction* cur = instructions()->at(i); 327 if (cur->IsGap()) { 328 LGap* gap = LGap::cast(cur); 329 if (!gap->IsRedundant()) { 330 can_eliminate = false; 331 } 332 } else { 333 can_eliminate = false; 334 } 335 } 336 if (can_eliminate) { 337 label->set_replacement(GetLabel(goto_instr->block_id())); 338 } 339 } 340 } 341 } 342 } 343 344 345 void LChunk::AddInstruction(LInstruction* instr, HBasicBlock* block) { 346 LInstructionGap* gap = new(graph_->zone()) LInstructionGap(block); 347 gap->set_hydrogen_value(instr->hydrogen_value()); 348 int index = -1; 349 if (instr->IsControl()) { 350 instructions_.Add(gap, zone()); 351 index = instructions_.length(); 352 instructions_.Add(instr, zone()); 353 } else { 354 index = instructions_.length(); 355 instructions_.Add(instr, zone()); 356 instructions_.Add(gap, zone()); 357 } 358 if (instr->HasPointerMap()) { 359 pointer_maps_.Add(instr->pointer_map(), zone()); 360 instr->pointer_map()->set_lithium_position(index); 361 } 362 } 363 364 365 LConstantOperand* LChunk::DefineConstantOperand(HConstant* constant) { 366 return LConstantOperand::Create(constant->id(), zone()); 367 } 368 369 370 int LChunk::GetParameterStackSlot(int index) const { 371 // The receiver is at index 0, the first parameter at index 1, so we 372 // shift all parameter indexes down by the number of parameters, and 373 // make sure they end up negative so they are distinguishable from 374 // spill slots. 375 int result = index - info()->scope()->num_parameters() - 1; 376 ASSERT(result < 0); 377 return result; 378 } 379 380 381 // A parameter relative to ebp in the arguments stub. 382 int LChunk::ParameterAt(int index) { 383 ASSERT(-1 <= index); // -1 is the receiver. 384 return (1 + info()->scope()->num_parameters() - index) * 385 kPointerSize; 386 } 387 388 389 LGap* LChunk::GetGapAt(int index) const { 390 return LGap::cast(instructions_[index]); 391 } 392 393 394 bool LChunk::IsGapAt(int index) const { 395 return instructions_[index]->IsGap(); 396 } 397 398 399 int LChunk::NearestGapPos(int index) const { 400 while (!IsGapAt(index)) index--; 401 return index; 402 } 403 404 405 void LChunk::AddGapMove(int index, LOperand* from, LOperand* to) { 406 GetGapAt(index)->GetOrCreateParallelMove( 407 LGap::START, zone())->AddMove(from, to, zone()); 408 } 409 410 411 HConstant* LChunk::LookupConstant(LConstantOperand* operand) const { 412 return HConstant::cast(graph_->LookupValue(operand->index())); 413 } 414 415 416 Representation LChunk::LookupLiteralRepresentation( 417 LConstantOperand* operand) const { 418 return graph_->LookupValue(operand->index())->representation(); 419 } 420 421 422 LChunk* LChunk::NewChunk(HGraph* graph) { 423 DisallowHandleAllocation no_handles; 424 DisallowHeapAllocation no_gc; 425 int values = graph->GetMaximumValueID(); 426 CompilationInfo* info = graph->info(); 427 if (values > LUnallocated::kMaxVirtualRegisters) { 428 info->set_bailout_reason(kNotEnoughVirtualRegistersForValues); 429 return NULL; 430 } 431 LAllocator allocator(values, graph); 432 LChunkBuilder builder(info, graph, &allocator); 433 LChunk* chunk = builder.Build(); 434 if (chunk == NULL) return NULL; 435 436 if (!allocator.Allocate(chunk)) { 437 info->set_bailout_reason(kNotEnoughVirtualRegistersRegalloc); 438 return NULL; 439 } 440 441 chunk->set_allocated_double_registers( 442 allocator.assigned_double_registers()); 443 444 return chunk; 445 } 446 447 448 Handle<Code> LChunk::Codegen() { 449 MacroAssembler assembler(info()->isolate(), NULL, 0); 450 LOG_CODE_EVENT(info()->isolate(), 451 CodeStartLinePosInfoRecordEvent( 452 assembler.positions_recorder())); 453 LCodeGen generator(this, &assembler, info()); 454 455 MarkEmptyBlocks(); 456 457 if (generator.GenerateCode()) { 458 CodeGenerator::MakeCodePrologue(info(), "optimized"); 459 Code::Flags flags = info()->flags(); 460 Handle<Code> code = 461 CodeGenerator::MakeCodeEpilogue(&assembler, flags, info()); 462 generator.FinishCode(code); 463 code->set_is_crankshafted(true); 464 if (!code.is_null()) { 465 void* jit_handler_data = 466 assembler.positions_recorder()->DetachJITHandlerData(); 467 LOG_CODE_EVENT(info()->isolate(), 468 CodeEndLinePosInfoRecordEvent(*code, jit_handler_data)); 469 } 470 471 CodeGenerator::PrintCode(code, info()); 472 return code; 473 } 474 return Handle<Code>::null(); 475 } 476 477 478 void LChunk::set_allocated_double_registers(BitVector* allocated_registers) { 479 allocated_double_registers_ = allocated_registers; 480 BitVector* doubles = allocated_double_registers(); 481 BitVector::Iterator iterator(doubles); 482 while (!iterator.Done()) { 483 if (info()->saves_caller_doubles()) { 484 if (kDoubleSize == kPointerSize * 2) { 485 spill_slot_count_ += 2; 486 } else { 487 spill_slot_count_++; 488 } 489 } 490 iterator.Advance(); 491 } 492 } 493 494 495 LPhase::~LPhase() { 496 if (ShouldProduceTraceOutput()) { 497 isolate()->GetHTracer()->TraceLithium(name(), chunk_); 498 } 499 } 500 501 502 } } // namespace v8::internal 503