1// Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file
2// for details. All rights reserved. Use of this source code is governed by a
3// BSD-style license that can be found in the LICENSE file.
4
5#include "vm/compiler/backend/locations.h"
6
7#include "vm/compiler/assembler/assembler.h"
8#include "vm/compiler/backend/il_printer.h"
9#include "vm/log.h"
10#include "vm/stack_frame.h"
11
12namespace dart {
13
14const char* Location::RepresentationToCString(Representation repr) {
15 switch (repr) {
16#define REPR_CASE(Name) \
17 case k##Name: \
18 return #Name;
19 FOR_EACH_REPRESENTATION_KIND(REPR_CASE)
20#undef KIND_CASE
21 default:
22 UNREACHABLE();
23 }
24 return nullptr;
25}
26
27bool Location::ParseRepresentation(const char* str, Representation* out) {
28 ASSERT(str != nullptr && out != nullptr);
29#define KIND_CASE(Name) \
30 if (strcmp(str, #Name) == 0) { \
31 *out = k##Name; \
32 return true; \
33 }
34 FOR_EACH_REPRESENTATION_KIND(KIND_CASE)
35#undef KIND_CASE
36 return false;
37}
38
39intptr_t RegisterSet::RegisterCount(intptr_t registers) {
40 // Brian Kernighan's algorithm for counting the bits set.
41 intptr_t count = 0;
42 while (registers != 0) {
43 ++count;
44 // Clear the least significant bit set.
45 registers &= (static_cast<uintptr_t>(registers) - 1);
46 }
47 return count;
48}
49
50void RegisterSet::DebugPrint() {
51 for (intptr_t i = 0; i < kNumberOfCpuRegisters; i++) {
52 Register r = static_cast<Register>(i);
53 if (ContainsRegister(r)) {
54 THR_Print("%s %s\n", RegisterNames::RegisterName(r),
55 IsTagged(r) ? "tagged" : "untagged");
56 }
57 }
58
59 for (intptr_t i = 0; i < kNumberOfFpuRegisters; i++) {
60 FpuRegister r = static_cast<FpuRegister>(i);
61 if (ContainsFpuRegister(r)) {
62 THR_Print("%s\n", RegisterNames::FpuRegisterName(r));
63 }
64 }
65}
66
67LocationSummary::LocationSummary(Zone* zone,
68 intptr_t input_count,
69 intptr_t temp_count,
70 LocationSummary::ContainsCall contains_call)
71 : num_inputs_(input_count),
72 num_temps_(temp_count),
73 output_location_(), // out(0)->IsInvalid() unless later set.
74 stack_bitmap_(NULL),
75 contains_call_(contains_call),
76 live_registers_() {
77#if defined(DEBUG)
78 writable_inputs_ = 0;
79#endif
80 input_locations_ = zone->Alloc<Location>(num_inputs_);
81 temp_locations_ = zone->Alloc<Location>(num_temps_);
82}
83
84LocationSummary* LocationSummary::Make(
85 Zone* zone,
86 intptr_t input_count,
87 Location out,
88 LocationSummary::ContainsCall contains_call) {
89 LocationSummary* summary =
90 new (zone) LocationSummary(zone, input_count, 0, contains_call);
91 for (intptr_t i = 0; i < input_count; i++) {
92 summary->set_in(i, Location::RequiresRegister());
93 }
94 summary->set_out(0, out);
95 return summary;
96}
97
98static bool ValidOutputForAlwaysCalls(const Location& loc) {
99 return loc.IsMachineRegister() || loc.IsInvalid() || loc.IsPairLocation();
100}
101
102void LocationSummary::set_in(intptr_t index, Location loc) {
103 ASSERT(index >= 0);
104 ASSERT(index < num_inputs_);
105#if defined(DEBUG)
106 // See FlowGraphAllocator::ProcessOneInstruction for explanation of these
107 // restrictions.
108 if (always_calls()) {
109 if (loc.IsUnallocated()) {
110 ASSERT(loc.policy() == Location::kAny);
111 } else if (loc.IsPairLocation()) {
112 ASSERT(!loc.AsPairLocation()->At(0).IsUnallocated() ||
113 loc.AsPairLocation()->At(0).policy() == Location::kAny);
114 ASSERT(!loc.AsPairLocation()->At(0).IsUnallocated() ||
115 loc.AsPairLocation()->At(0).policy() == Location::kAny);
116 }
117 if (index == 0 && out(0).IsUnallocated() &&
118 out(0).policy() == Location::kSameAsFirstInput) {
119 ASSERT(ValidOutputForAlwaysCalls(loc));
120 }
121 }
122#endif
123 input_locations_[index] = loc;
124}
125
126void LocationSummary::set_out(intptr_t index, Location loc) {
127 ASSERT(index == 0);
128 ASSERT(!always_calls() || ValidOutputForAlwaysCalls(loc) ||
129 (loc.IsUnallocated() && loc.policy() == Location::kSameAsFirstInput &&
130 num_inputs_ > 0 && ValidOutputForAlwaysCalls(in(0))));
131 output_location_ = loc;
132}
133
134Location Location::Pair(Location first, Location second) {
135 PairLocation* pair_location = new PairLocation();
136 ASSERT((reinterpret_cast<intptr_t>(pair_location) & kLocationTagMask) == 0);
137 pair_location->SetAt(0, first);
138 pair_location->SetAt(1, second);
139 Location loc(reinterpret_cast<uword>(pair_location) | kPairLocationTag);
140 return loc;
141}
142
143PairLocation* Location::AsPairLocation() const {
144 ASSERT(IsPairLocation());
145 return reinterpret_cast<PairLocation*>(value_ & ~kLocationTagMask);
146}
147
148Location Location::Component(intptr_t i) const {
149 return AsPairLocation()->At(i);
150}
151
152Location LocationRegisterOrConstant(Value* value) {
153 ConstantInstr* constant = value->definition()->AsConstant();
154 return ((constant != NULL) && compiler::Assembler::IsSafe(constant->value()))
155 ? Location::Constant(constant)
156 : Location::RequiresRegister();
157}
158
159Location LocationRegisterOrSmiConstant(Value* value) {
160 ConstantInstr* constant = value->definition()->AsConstant();
161 return ((constant != NULL) &&
162 compiler::Assembler::IsSafeSmi(constant->value()))
163 ? Location::Constant(constant)
164 : Location::RequiresRegister();
165}
166
167Location LocationWritableRegisterOrSmiConstant(Value* value) {
168 ConstantInstr* constant = value->definition()->AsConstant();
169 return ((constant != NULL) &&
170 compiler::Assembler::IsSafeSmi(constant->value()))
171 ? Location::Constant(constant)
172 : Location::WritableRegister();
173}
174
175Location LocationFixedRegisterOrConstant(Value* value, Register reg) {
176 ASSERT(((1 << reg) & kDartAvailableCpuRegs) != 0);
177 ConstantInstr* constant = value->definition()->AsConstant();
178 return ((constant != NULL) && compiler::Assembler::IsSafe(constant->value()))
179 ? Location::Constant(constant)
180 : Location::RegisterLocation(reg);
181}
182
183Location LocationFixedRegisterOrSmiConstant(Value* value, Register reg) {
184 ASSERT(((1 << reg) & kDartAvailableCpuRegs) != 0);
185 ConstantInstr* constant = value->definition()->AsConstant();
186 return ((constant != NULL) &&
187 compiler::Assembler::IsSafeSmi(constant->value()))
188 ? Location::Constant(constant)
189 : Location::RegisterLocation(reg);
190}
191
192Location LocationAnyOrConstant(Value* value) {
193 ConstantInstr* constant = value->definition()->AsConstant();
194 return ((constant != NULL) && compiler::Assembler::IsSafe(constant->value()))
195 ? Location::Constant(constant)
196 : Location::Any();
197}
198
199compiler::Address LocationToStackSlotAddress(Location loc) {
200 return compiler::Address(loc.base_reg(), loc.ToStackSlotOffset());
201}
202
203intptr_t Location::ToStackSlotOffset() const {
204 return stack_index() * compiler::target::kWordSize;
205}
206
207const Object& Location::constant() const {
208 return constant_instruction()->value();
209}
210
211const char* Location::Name() const {
212 switch (kind()) {
213 case kInvalid:
214 return "?";
215 case kRegister:
216 return RegisterNames::RegisterName(reg());
217 case kFpuRegister:
218 return RegisterNames::FpuRegisterName(fpu_reg());
219 case kStackSlot:
220 return "S";
221 case kDoubleStackSlot:
222 return "DS";
223 case kQuadStackSlot:
224 return "QS";
225 case kUnallocated:
226 switch (policy()) {
227 case kAny:
228 return "A";
229 case kPrefersRegister:
230 return "P";
231 case kRequiresRegister:
232 return "R";
233 case kRequiresFpuRegister:
234 return "DR";
235 case kWritableRegister:
236 return "WR";
237 case kSameAsFirstInput:
238 return "0";
239 }
240 UNREACHABLE();
241 default:
242 if (IsConstant()) {
243 return "C";
244 } else {
245 ASSERT(IsPairLocation());
246 return "2P";
247 }
248 }
249 return "?";
250}
251
252void Location::PrintTo(BaseTextBuffer* f) const {
253 if (!FLAG_support_il_printer) {
254 return;
255 }
256 if (kind() == kStackSlot) {
257 f->Printf("S%+" Pd "", stack_index());
258 } else if (kind() == kDoubleStackSlot) {
259 f->Printf("DS%+" Pd "", stack_index());
260 } else if (kind() == kQuadStackSlot) {
261 f->Printf("QS%+" Pd "", stack_index());
262 } else if (IsPairLocation()) {
263 f->AddString("(");
264 AsPairLocation()->At(0).PrintTo(f);
265 f->AddString(", ");
266 AsPairLocation()->At(1).PrintTo(f);
267 f->AddString(")");
268 } else {
269 f->Printf("%s", Name());
270 }
271}
272
273const char* Location::ToCString() const {
274 char buffer[1024];
275 BufferFormatter bf(buffer, 1024);
276 PrintTo(&bf);
277 return Thread::Current()->zone()->MakeCopyOfString(buffer);
278}
279
280void Location::Print() const {
281 if (kind() == kStackSlot) {
282 THR_Print("S%+" Pd "", stack_index());
283 } else {
284 THR_Print("%s", Name());
285 }
286}
287
288Location Location::Copy() const {
289 if (IsPairLocation()) {
290 PairLocation* pair = AsPairLocation();
291 ASSERT(!pair->At(0).IsPairLocation());
292 ASSERT(!pair->At(1).IsPairLocation());
293 return Location::Pair(pair->At(0).Copy(), pair->At(1).Copy());
294 } else {
295 // Copy by value.
296 return *this;
297 }
298}
299
300Location LocationArgumentsDescriptorLocation() {
301 return Location::RegisterLocation(ARGS_DESC_REG);
302}
303
304Location LocationExceptionLocation() {
305 return Location::RegisterLocation(kExceptionObjectReg);
306}
307
308Location LocationStackTraceLocation() {
309 return Location::RegisterLocation(kStackTraceObjectReg);
310}
311
312Location LocationRemapForSlowPath(Location loc,
313 Definition* def,
314 intptr_t* cpu_reg_slots,
315 intptr_t* fpu_reg_slots) {
316 if (loc.IsRegister()) {
317 intptr_t index = cpu_reg_slots[loc.reg()];
318 ASSERT(index >= 0);
319 return Location::StackSlot(
320 compiler::target::frame_layout.FrameSlotForVariableIndex(-index),
321 FPREG);
322 } else if (loc.IsFpuRegister()) {
323 intptr_t index = fpu_reg_slots[loc.fpu_reg()];
324 ASSERT(index >= 0);
325 switch (def->representation()) {
326 case kUnboxedDouble: // SlowPathEnvironmentFor sees _one_ register
327 case kUnboxedFloat: // both for doubles and floats.
328 return Location::DoubleStackSlot(
329 compiler::target::frame_layout.FrameSlotForVariableIndex(-index),
330 FPREG);
331
332 case kUnboxedFloat32x4:
333 case kUnboxedInt32x4:
334 case kUnboxedFloat64x2:
335 return Location::QuadStackSlot(
336 compiler::target::frame_layout.FrameSlotForVariableIndex(-index),
337 FPREG);
338
339 default:
340 UNREACHABLE();
341 }
342 } else if (loc.IsPairLocation()) {
343 ASSERT(def->representation() == kUnboxedInt64);
344 PairLocation* value_pair = loc.AsPairLocation();
345 intptr_t index_lo;
346 intptr_t index_hi;
347
348 if (value_pair->At(0).IsRegister()) {
349 index_lo = compiler::target::frame_layout.FrameSlotForVariableIndex(
350 -cpu_reg_slots[value_pair->At(0).reg()]);
351 } else {
352 ASSERT(value_pair->At(0).IsStackSlot());
353 index_lo = value_pair->At(0).stack_index();
354 }
355
356 if (value_pair->At(1).IsRegister()) {
357 index_hi = compiler::target::frame_layout.FrameSlotForVariableIndex(
358 -cpu_reg_slots[value_pair->At(1).reg()]);
359 } else {
360 ASSERT(value_pair->At(1).IsStackSlot());
361 index_hi = value_pair->At(1).stack_index();
362 }
363
364 return Location::Pair(Location::StackSlot(index_lo, FPREG),
365 Location::StackSlot(index_hi, FPREG));
366 } else if (loc.IsInvalid() && def->IsMaterializeObject()) {
367 def->AsMaterializeObject()->RemapRegisters(cpu_reg_slots, fpu_reg_slots);
368 return loc;
369 }
370
371 return loc;
372}
373
374void LocationSummary::PrintTo(BaseTextBuffer* f) const {
375 if (!FLAG_support_il_printer) {
376 return;
377 }
378 if (input_count() > 0) {
379 f->AddString(" (");
380 for (intptr_t i = 0; i < input_count(); i++) {
381 if (i != 0) f->AddString(", ");
382 in(i).PrintTo(f);
383 }
384 f->AddString(")");
385 }
386
387 if (temp_count() > 0) {
388 f->AddString(" [");
389 for (intptr_t i = 0; i < temp_count(); i++) {
390 if (i != 0) f->AddString(", ");
391 temp(i).PrintTo(f);
392 }
393 f->AddString("]");
394 }
395
396 if (!out(0).IsInvalid()) {
397 f->AddString(" => ");
398 out(0).PrintTo(f);
399 }
400
401 if (always_calls()) f->AddString(" C");
402}
403
404#if defined(DEBUG)
405void LocationSummary::DiscoverWritableInputs() {
406 if (!HasCallOnSlowPath()) {
407 return;
408 }
409
410 for (intptr_t i = 0; i < input_count(); i++) {
411 if (in(i).IsUnallocated() &&
412 (in(i).policy() == Location::kWritableRegister)) {
413 writable_inputs_ |= 1 << i;
414 }
415 }
416}
417
418void LocationSummary::CheckWritableInputs() {
419 ASSERT(HasCallOnSlowPath());
420 for (intptr_t i = 0; i < input_count(); i++) {
421 if ((writable_inputs_ & (1 << i)) != 0) {
422 // Writable registers have to be manually preserved because
423 // with the right representation because register allocator does not know
424 // how they are used within the instruction template.
425 ASSERT(in(i).IsMachineRegister());
426 ASSERT(live_registers()->Contains(in(i)));
427 }
428 }
429}
430#endif
431
432} // namespace dart
433