1 // Copyright 2014 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/compiler/instruction.h"
6
7 #include "src/compiler/common-operator.h"
8
9 namespace v8 {
10 namespace internal {
11 namespace compiler {
12
operator <<(OStream & os,const InstructionOperand & op)13 OStream& operator<<(OStream& os, const InstructionOperand& op) {
14 switch (op.kind()) {
15 case InstructionOperand::INVALID:
16 return os << "(0)";
17 case InstructionOperand::UNALLOCATED: {
18 const UnallocatedOperand* unalloc = UnallocatedOperand::cast(&op);
19 os << "v" << unalloc->virtual_register();
20 if (unalloc->basic_policy() == UnallocatedOperand::FIXED_SLOT) {
21 return os << "(=" << unalloc->fixed_slot_index() << "S)";
22 }
23 switch (unalloc->extended_policy()) {
24 case UnallocatedOperand::NONE:
25 return os;
26 case UnallocatedOperand::FIXED_REGISTER:
27 return os << "(=" << Register::AllocationIndexToString(
28 unalloc->fixed_register_index()) << ")";
29 case UnallocatedOperand::FIXED_DOUBLE_REGISTER:
30 return os << "(=" << DoubleRegister::AllocationIndexToString(
31 unalloc->fixed_register_index()) << ")";
32 case UnallocatedOperand::MUST_HAVE_REGISTER:
33 return os << "(R)";
34 case UnallocatedOperand::SAME_AS_FIRST_INPUT:
35 return os << "(1)";
36 case UnallocatedOperand::ANY:
37 return os << "(-)";
38 }
39 }
40 case InstructionOperand::CONSTANT:
41 return os << "[constant:" << op.index() << "]";
42 case InstructionOperand::IMMEDIATE:
43 return os << "[immediate:" << op.index() << "]";
44 case InstructionOperand::STACK_SLOT:
45 return os << "[stack:" << op.index() << "]";
46 case InstructionOperand::DOUBLE_STACK_SLOT:
47 return os << "[double_stack:" << op.index() << "]";
48 case InstructionOperand::REGISTER:
49 return os << "[" << Register::AllocationIndexToString(op.index())
50 << "|R]";
51 case InstructionOperand::DOUBLE_REGISTER:
52 return os << "[" << DoubleRegister::AllocationIndexToString(op.index())
53 << "|R]";
54 }
55 UNREACHABLE();
56 return os;
57 }
58
59
60 template <InstructionOperand::Kind kOperandKind, int kNumCachedOperands>
61 SubKindOperand<kOperandKind, kNumCachedOperands>*
62 SubKindOperand<kOperandKind, kNumCachedOperands>::cache = NULL;
63
64
65 template <InstructionOperand::Kind kOperandKind, int kNumCachedOperands>
SetUpCache()66 void SubKindOperand<kOperandKind, kNumCachedOperands>::SetUpCache() {
67 if (cache) return;
68 cache = new SubKindOperand[kNumCachedOperands];
69 for (int i = 0; i < kNumCachedOperands; i++) {
70 cache[i].ConvertTo(kOperandKind, i);
71 }
72 }
73
74
75 template <InstructionOperand::Kind kOperandKind, int kNumCachedOperands>
TearDownCache()76 void SubKindOperand<kOperandKind, kNumCachedOperands>::TearDownCache() {
77 delete[] cache;
78 cache = NULL;
79 }
80
81
SetUpCaches()82 void InstructionOperand::SetUpCaches() {
83 #define INSTRUCTION_OPERAND_SETUP(name, type, number) \
84 name##Operand::SetUpCache();
85 INSTRUCTION_OPERAND_LIST(INSTRUCTION_OPERAND_SETUP)
86 #undef INSTRUCTION_OPERAND_SETUP
87 }
88
89
TearDownCaches()90 void InstructionOperand::TearDownCaches() {
91 #define INSTRUCTION_OPERAND_TEARDOWN(name, type, number) \
92 name##Operand::TearDownCache();
93 INSTRUCTION_OPERAND_LIST(INSTRUCTION_OPERAND_TEARDOWN)
94 #undef INSTRUCTION_OPERAND_TEARDOWN
95 }
96
97
operator <<(OStream & os,const MoveOperands & mo)98 OStream& operator<<(OStream& os, const MoveOperands& mo) {
99 os << *mo.destination();
100 if (!mo.source()->Equals(mo.destination())) os << " = " << *mo.source();
101 return os << ";";
102 }
103
104
IsRedundant() const105 bool ParallelMove::IsRedundant() const {
106 for (int i = 0; i < move_operands_.length(); ++i) {
107 if (!move_operands_[i].IsRedundant()) return false;
108 }
109 return true;
110 }
111
112
operator <<(OStream & os,const ParallelMove & pm)113 OStream& operator<<(OStream& os, const ParallelMove& pm) {
114 bool first = true;
115 for (ZoneList<MoveOperands>::iterator move = pm.move_operands()->begin();
116 move != pm.move_operands()->end(); ++move) {
117 if (move->IsEliminated()) continue;
118 if (!first) os << " ";
119 first = false;
120 os << *move;
121 }
122 return os;
123 }
124
125
RecordPointer(InstructionOperand * op,Zone * zone)126 void PointerMap::RecordPointer(InstructionOperand* op, Zone* zone) {
127 // Do not record arguments as pointers.
128 if (op->IsStackSlot() && op->index() < 0) return;
129 DCHECK(!op->IsDoubleRegister() && !op->IsDoubleStackSlot());
130 pointer_operands_.Add(op, zone);
131 }
132
133
RemovePointer(InstructionOperand * op)134 void PointerMap::RemovePointer(InstructionOperand* op) {
135 // Do not record arguments as pointers.
136 if (op->IsStackSlot() && op->index() < 0) return;
137 DCHECK(!op->IsDoubleRegister() && !op->IsDoubleStackSlot());
138 for (int i = 0; i < pointer_operands_.length(); ++i) {
139 if (pointer_operands_[i]->Equals(op)) {
140 pointer_operands_.Remove(i);
141 --i;
142 }
143 }
144 }
145
146
RecordUntagged(InstructionOperand * op,Zone * zone)147 void PointerMap::RecordUntagged(InstructionOperand* op, Zone* zone) {
148 // Do not record arguments as pointers.
149 if (op->IsStackSlot() && op->index() < 0) return;
150 DCHECK(!op->IsDoubleRegister() && !op->IsDoubleStackSlot());
151 untagged_operands_.Add(op, zone);
152 }
153
154
operator <<(OStream & os,const PointerMap & pm)155 OStream& operator<<(OStream& os, const PointerMap& pm) {
156 os << "{";
157 for (ZoneList<InstructionOperand*>::iterator op =
158 pm.pointer_operands_.begin();
159 op != pm.pointer_operands_.end(); ++op) {
160 if (op != pm.pointer_operands_.begin()) os << ";";
161 os << *op;
162 }
163 return os << "}";
164 }
165
166
operator <<(OStream & os,const ArchOpcode & ao)167 OStream& operator<<(OStream& os, const ArchOpcode& ao) {
168 switch (ao) {
169 #define CASE(Name) \
170 case k##Name: \
171 return os << #Name;
172 ARCH_OPCODE_LIST(CASE)
173 #undef CASE
174 }
175 UNREACHABLE();
176 return os;
177 }
178
179
operator <<(OStream & os,const AddressingMode & am)180 OStream& operator<<(OStream& os, const AddressingMode& am) {
181 switch (am) {
182 case kMode_None:
183 return os;
184 #define CASE(Name) \
185 case kMode_##Name: \
186 return os << #Name;
187 TARGET_ADDRESSING_MODE_LIST(CASE)
188 #undef CASE
189 }
190 UNREACHABLE();
191 return os;
192 }
193
194
operator <<(OStream & os,const FlagsMode & fm)195 OStream& operator<<(OStream& os, const FlagsMode& fm) {
196 switch (fm) {
197 case kFlags_none:
198 return os;
199 case kFlags_branch:
200 return os << "branch";
201 case kFlags_set:
202 return os << "set";
203 }
204 UNREACHABLE();
205 return os;
206 }
207
208
operator <<(OStream & os,const FlagsCondition & fc)209 OStream& operator<<(OStream& os, const FlagsCondition& fc) {
210 switch (fc) {
211 case kEqual:
212 return os << "equal";
213 case kNotEqual:
214 return os << "not equal";
215 case kSignedLessThan:
216 return os << "signed less than";
217 case kSignedGreaterThanOrEqual:
218 return os << "signed greater than or equal";
219 case kSignedLessThanOrEqual:
220 return os << "signed less than or equal";
221 case kSignedGreaterThan:
222 return os << "signed greater than";
223 case kUnsignedLessThan:
224 return os << "unsigned less than";
225 case kUnsignedGreaterThanOrEqual:
226 return os << "unsigned greater than or equal";
227 case kUnsignedLessThanOrEqual:
228 return os << "unsigned less than or equal";
229 case kUnsignedGreaterThan:
230 return os << "unsigned greater than";
231 case kUnorderedEqual:
232 return os << "unordered equal";
233 case kUnorderedNotEqual:
234 return os << "unordered not equal";
235 case kUnorderedLessThan:
236 return os << "unordered less than";
237 case kUnorderedGreaterThanOrEqual:
238 return os << "unordered greater than or equal";
239 case kUnorderedLessThanOrEqual:
240 return os << "unordered less than or equal";
241 case kUnorderedGreaterThan:
242 return os << "unordered greater than";
243 case kOverflow:
244 return os << "overflow";
245 case kNotOverflow:
246 return os << "not overflow";
247 }
248 UNREACHABLE();
249 return os;
250 }
251
252
operator <<(OStream & os,const Instruction & instr)253 OStream& operator<<(OStream& os, const Instruction& instr) {
254 if (instr.OutputCount() > 1) os << "(";
255 for (size_t i = 0; i < instr.OutputCount(); i++) {
256 if (i > 0) os << ", ";
257 os << *instr.OutputAt(i);
258 }
259
260 if (instr.OutputCount() > 1) os << ") = ";
261 if (instr.OutputCount() == 1) os << " = ";
262
263 if (instr.IsGapMoves()) {
264 const GapInstruction* gap = GapInstruction::cast(&instr);
265 os << (instr.IsBlockStart() ? " block-start" : "gap ");
266 for (int i = GapInstruction::FIRST_INNER_POSITION;
267 i <= GapInstruction::LAST_INNER_POSITION; i++) {
268 os << "(";
269 if (gap->parallel_moves_[i] != NULL) os << *gap->parallel_moves_[i];
270 os << ") ";
271 }
272 } else if (instr.IsSourcePosition()) {
273 const SourcePositionInstruction* pos =
274 SourcePositionInstruction::cast(&instr);
275 os << "position (" << pos->source_position().raw() << ")";
276 } else {
277 os << ArchOpcodeField::decode(instr.opcode());
278 AddressingMode am = AddressingModeField::decode(instr.opcode());
279 if (am != kMode_None) {
280 os << " : " << AddressingModeField::decode(instr.opcode());
281 }
282 FlagsMode fm = FlagsModeField::decode(instr.opcode());
283 if (fm != kFlags_none) {
284 os << " && " << fm << " if "
285 << FlagsConditionField::decode(instr.opcode());
286 }
287 }
288 if (instr.InputCount() > 0) {
289 for (size_t i = 0; i < instr.InputCount(); i++) {
290 os << " " << *instr.InputAt(i);
291 }
292 }
293 return os << "\n";
294 }
295
296
operator <<(OStream & os,const Constant & constant)297 OStream& operator<<(OStream& os, const Constant& constant) {
298 switch (constant.type()) {
299 case Constant::kInt32:
300 return os << constant.ToInt32();
301 case Constant::kInt64:
302 return os << constant.ToInt64() << "l";
303 case Constant::kFloat64:
304 return os << constant.ToFloat64();
305 case Constant::kExternalReference:
306 return os << constant.ToExternalReference().address();
307 case Constant::kHeapObject:
308 return os << Brief(*constant.ToHeapObject());
309 }
310 UNREACHABLE();
311 return os;
312 }
313
314
GetLabel(BasicBlock * block)315 Label* InstructionSequence::GetLabel(BasicBlock* block) {
316 return GetBlockStart(block)->label();
317 }
318
319
GetBlockStart(BasicBlock * block)320 BlockStartInstruction* InstructionSequence::GetBlockStart(BasicBlock* block) {
321 return BlockStartInstruction::cast(InstructionAt(block->code_start_));
322 }
323
324
StartBlock(BasicBlock * block)325 void InstructionSequence::StartBlock(BasicBlock* block) {
326 block->code_start_ = static_cast<int>(instructions_.size());
327 BlockStartInstruction* block_start =
328 BlockStartInstruction::New(zone(), block);
329 AddInstruction(block_start, block);
330 }
331
332
EndBlock(BasicBlock * block)333 void InstructionSequence::EndBlock(BasicBlock* block) {
334 int end = static_cast<int>(instructions_.size());
335 DCHECK(block->code_start_ >= 0 && block->code_start_ < end);
336 block->code_end_ = end;
337 }
338
339
AddInstruction(Instruction * instr,BasicBlock * block)340 int InstructionSequence::AddInstruction(Instruction* instr, BasicBlock* block) {
341 // TODO(titzer): the order of these gaps is a holdover from Lithium.
342 GapInstruction* gap = GapInstruction::New(zone());
343 if (instr->IsControl()) instructions_.push_back(gap);
344 int index = static_cast<int>(instructions_.size());
345 instructions_.push_back(instr);
346 if (!instr->IsControl()) instructions_.push_back(gap);
347 if (instr->NeedsPointerMap()) {
348 DCHECK(instr->pointer_map() == NULL);
349 PointerMap* pointer_map = new (zone()) PointerMap(zone());
350 pointer_map->set_instruction_position(index);
351 instr->set_pointer_map(pointer_map);
352 pointer_maps_.push_back(pointer_map);
353 }
354 return index;
355 }
356
357
GetBasicBlock(int instruction_index)358 BasicBlock* InstructionSequence::GetBasicBlock(int instruction_index) {
359 // TODO(turbofan): Optimize this.
360 for (;;) {
361 DCHECK_LE(0, instruction_index);
362 Instruction* instruction = InstructionAt(instruction_index--);
363 if (instruction->IsBlockStart()) {
364 return BlockStartInstruction::cast(instruction)->block();
365 }
366 }
367 }
368
369
IsReference(int virtual_register) const370 bool InstructionSequence::IsReference(int virtual_register) const {
371 return references_.find(virtual_register) != references_.end();
372 }
373
374
IsDouble(int virtual_register) const375 bool InstructionSequence::IsDouble(int virtual_register) const {
376 return doubles_.find(virtual_register) != doubles_.end();
377 }
378
379
MarkAsReference(int virtual_register)380 void InstructionSequence::MarkAsReference(int virtual_register) {
381 references_.insert(virtual_register);
382 }
383
384
MarkAsDouble(int virtual_register)385 void InstructionSequence::MarkAsDouble(int virtual_register) {
386 doubles_.insert(virtual_register);
387 }
388
389
AddGapMove(int index,InstructionOperand * from,InstructionOperand * to)390 void InstructionSequence::AddGapMove(int index, InstructionOperand* from,
391 InstructionOperand* to) {
392 GapAt(index)->GetOrCreateParallelMove(GapInstruction::START, zone())->AddMove(
393 from, to, zone());
394 }
395
396
AddFrameStateDescriptor(FrameStateDescriptor * descriptor)397 InstructionSequence::StateId InstructionSequence::AddFrameStateDescriptor(
398 FrameStateDescriptor* descriptor) {
399 int deoptimization_id = static_cast<int>(deoptimization_entries_.size());
400 deoptimization_entries_.push_back(descriptor);
401 return StateId::FromInt(deoptimization_id);
402 }
403
GetFrameStateDescriptor(InstructionSequence::StateId state_id)404 FrameStateDescriptor* InstructionSequence::GetFrameStateDescriptor(
405 InstructionSequence::StateId state_id) {
406 return deoptimization_entries_[state_id.ToInt()];
407 }
408
409
GetFrameStateDescriptorCount()410 int InstructionSequence::GetFrameStateDescriptorCount() {
411 return static_cast<int>(deoptimization_entries_.size());
412 }
413
414
operator <<(OStream & os,const InstructionSequence & code)415 OStream& operator<<(OStream& os, const InstructionSequence& code) {
416 for (size_t i = 0; i < code.immediates_.size(); ++i) {
417 Constant constant = code.immediates_[i];
418 os << "IMM#" << i << ": " << constant << "\n";
419 }
420 int i = 0;
421 for (ConstantMap::const_iterator it = code.constants_.begin();
422 it != code.constants_.end(); ++i, ++it) {
423 os << "CST#" << i << ": v" << it->first << " = " << it->second << "\n";
424 }
425 for (int i = 0; i < code.BasicBlockCount(); i++) {
426 BasicBlock* block = code.BlockAt(i);
427
428 int bid = block->id();
429 os << "RPO#" << block->rpo_number_ << ": B" << bid;
430 CHECK(block->rpo_number_ == i);
431 if (block->IsLoopHeader()) {
432 os << " loop blocks: [" << block->rpo_number_ << ", " << block->loop_end_
433 << ")";
434 }
435 os << " instructions: [" << block->code_start_ << ", " << block->code_end_
436 << ")\n predecessors:";
437
438 BasicBlock::Predecessors predecessors = block->predecessors();
439 for (BasicBlock::Predecessors::iterator iter = predecessors.begin();
440 iter != predecessors.end(); ++iter) {
441 os << " B" << (*iter)->id();
442 }
443 os << "\n";
444
445 for (BasicBlock::const_iterator j = block->begin(); j != block->end();
446 ++j) {
447 Node* phi = *j;
448 if (phi->opcode() != IrOpcode::kPhi) continue;
449 os << " phi: v" << phi->id() << " =";
450 Node::Inputs inputs = phi->inputs();
451 for (Node::Inputs::iterator iter(inputs.begin()); iter != inputs.end();
452 ++iter) {
453 os << " v" << (*iter)->id();
454 }
455 os << "\n";
456 }
457
458 ScopedVector<char> buf(32);
459 for (int j = block->first_instruction_index();
460 j <= block->last_instruction_index(); j++) {
461 // TODO(svenpanne) Add some basic formatting to our streams.
462 SNPrintF(buf, "%5d", j);
463 os << " " << buf.start() << ": " << *code.InstructionAt(j);
464 }
465
466 os << " " << block->control_;
467
468 if (block->control_input_ != NULL) {
469 os << " v" << block->control_input_->id();
470 }
471
472 BasicBlock::Successors successors = block->successors();
473 for (BasicBlock::Successors::iterator iter = successors.begin();
474 iter != successors.end(); ++iter) {
475 os << " B" << (*iter)->id();
476 }
477 os << "\n";
478 }
479 return os;
480 }
481
482 } // namespace compiler
483 } // namespace internal
484 } // namespace v8
485