1/*
2 * Copyright (C) 2014 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17#ifndef ART_COMPILER_OPTIMIZING_LOCATIONS_H_
18#define ART_COMPILER_OPTIMIZING_LOCATIONS_H_
19
20#include "base/arena_containers.h"
21#include "base/arena_object.h"
22#include "base/bit_field.h"
23#include "base/bit_vector.h"
24#include "base/value_object.h"
25
26namespace art {
27
28class HConstant;
29class HInstruction;
30class Location;
31
32std::ostream& operator<<(std::ostream& os, const Location& location);
33
34/**
35 * A Location is an abstraction over the potential location
36 * of an instruction. It could be in register or stack.
37 */
38class Location : public ValueObject {
39 public:
40  enum OutputOverlap {
41    kOutputOverlap,
42    kNoOutputOverlap
43  };
44
45  enum Kind {
46    kInvalid = 0,
47    kConstant = 1,
48    kStackSlot = 2,  // 32bit stack slot.
49    kDoubleStackSlot = 3,  // 64bit stack slot.
50
51    kRegister = 4,  // Core register.
52
53    // We do not use the value 5 because it conflicts with kLocationConstantMask.
54    kDoNotUse5 = 5,
55
56    kFpuRegister = 6,  // Float register.
57
58    kRegisterPair = 7,  // Long register.
59
60    kFpuRegisterPair = 8,  // Double register.
61
62    // We do not use the value 9 because it conflicts with kLocationConstantMask.
63    kDoNotUse9 = 9,
64
65    // Unallocated location represents a location that is not fixed and can be
66    // allocated by a register allocator.  Each unallocated location has
67    // a policy that specifies what kind of location is suitable. Payload
68    // contains register allocation policy.
69    kUnallocated = 10,
70  };
71
72  Location() : ValueObject(), value_(kInvalid) {
73    // Verify that non-constant location kinds do not interfere with kConstant.
74    static_assert((kInvalid & kLocationConstantMask) != kConstant, "TagError");
75    static_assert((kUnallocated & kLocationConstantMask) != kConstant, "TagError");
76    static_assert((kStackSlot & kLocationConstantMask) != kConstant, "TagError");
77    static_assert((kDoubleStackSlot & kLocationConstantMask) != kConstant, "TagError");
78    static_assert((kRegister & kLocationConstantMask) != kConstant, "TagError");
79    static_assert((kFpuRegister & kLocationConstantMask) != kConstant, "TagError");
80    static_assert((kRegisterPair & kLocationConstantMask) != kConstant, "TagError");
81    static_assert((kFpuRegisterPair & kLocationConstantMask) != kConstant, "TagError");
82    static_assert((kConstant & kLocationConstantMask) == kConstant, "TagError");
83
84    DCHECK(!IsValid());
85  }
86
87  Location(const Location& other) : value_(other.value_) {}
88
89  Location& operator=(const Location& other) {
90    value_ = other.value_;
91    return *this;
92  }
93
94  bool IsConstant() const {
95    return (value_ & kLocationConstantMask) == kConstant;
96  }
97
98  static Location ConstantLocation(HConstant* constant) {
99    DCHECK(constant != nullptr);
100    return Location(kConstant | reinterpret_cast<uintptr_t>(constant));
101  }
102
103  HConstant* GetConstant() const {
104    DCHECK(IsConstant());
105    return reinterpret_cast<HConstant*>(value_ & ~kLocationConstantMask);
106  }
107
108  bool IsValid() const {
109    return value_ != kInvalid;
110  }
111
112  bool IsInvalid() const {
113    return !IsValid();
114  }
115
116  // Empty location. Used if there the location should be ignored.
117  static Location NoLocation() {
118    return Location();
119  }
120
121  // Register locations.
122  static Location RegisterLocation(int reg) {
123    return Location(kRegister, reg);
124  }
125
126  static Location FpuRegisterLocation(int reg) {
127    return Location(kFpuRegister, reg);
128  }
129
130  static Location RegisterPairLocation(int low, int high) {
131    return Location(kRegisterPair, low << 16 | high);
132  }
133
134  static Location FpuRegisterPairLocation(int low, int high) {
135    return Location(kFpuRegisterPair, low << 16 | high);
136  }
137
138  bool IsRegister() const {
139    return GetKind() == kRegister;
140  }
141
142  bool IsFpuRegister() const {
143    return GetKind() == kFpuRegister;
144  }
145
146  bool IsRegisterPair() const {
147    return GetKind() == kRegisterPair;
148  }
149
150  bool IsFpuRegisterPair() const {
151    return GetKind() == kFpuRegisterPair;
152  }
153
154  bool IsRegisterKind() const {
155    return IsRegister() || IsFpuRegister() || IsRegisterPair() || IsFpuRegisterPair();
156  }
157
158  int reg() const {
159    DCHECK(IsRegister() || IsFpuRegister());
160    return GetPayload();
161  }
162
163  int low() const {
164    DCHECK(IsPair());
165    return GetPayload() >> 16;
166  }
167
168  int high() const {
169    DCHECK(IsPair());
170    return GetPayload() & 0xFFFF;
171  }
172
173  template <typename T>
174  T AsRegister() const {
175    DCHECK(IsRegister());
176    return static_cast<T>(reg());
177  }
178
179  template <typename T>
180  T AsFpuRegister() const {
181    DCHECK(IsFpuRegister());
182    return static_cast<T>(reg());
183  }
184
185  template <typename T>
186  T AsRegisterPairLow() const {
187    DCHECK(IsRegisterPair());
188    return static_cast<T>(low());
189  }
190
191  template <typename T>
192  T AsRegisterPairHigh() const {
193    DCHECK(IsRegisterPair());
194    return static_cast<T>(high());
195  }
196
197  template <typename T>
198  T AsFpuRegisterPairLow() const {
199    DCHECK(IsFpuRegisterPair());
200    return static_cast<T>(low());
201  }
202
203  template <typename T>
204  T AsFpuRegisterPairHigh() const {
205    DCHECK(IsFpuRegisterPair());
206    return static_cast<T>(high());
207  }
208
209  bool IsPair() const {
210    return IsRegisterPair() || IsFpuRegisterPair();
211  }
212
213  Location ToLow() const {
214    if (IsRegisterPair()) {
215      return Location::RegisterLocation(low());
216    } else if (IsFpuRegisterPair()) {
217      return Location::FpuRegisterLocation(low());
218    } else {
219      DCHECK(IsDoubleStackSlot());
220      return Location::StackSlot(GetStackIndex());
221    }
222  }
223
224  Location ToHigh() const {
225    if (IsRegisterPair()) {
226      return Location::RegisterLocation(high());
227    } else if (IsFpuRegisterPair()) {
228      return Location::FpuRegisterLocation(high());
229    } else {
230      DCHECK(IsDoubleStackSlot());
231      return Location::StackSlot(GetHighStackIndex(4));
232    }
233  }
234
235  static uintptr_t EncodeStackIndex(intptr_t stack_index) {
236    DCHECK(-kStackIndexBias <= stack_index);
237    DCHECK(stack_index < kStackIndexBias);
238    return static_cast<uintptr_t>(kStackIndexBias + stack_index);
239  }
240
241  static Location StackSlot(intptr_t stack_index) {
242    uintptr_t payload = EncodeStackIndex(stack_index);
243    Location loc(kStackSlot, payload);
244    // Ensure that sign is preserved.
245    DCHECK_EQ(loc.GetStackIndex(), stack_index);
246    return loc;
247  }
248
249  bool IsStackSlot() const {
250    return GetKind() == kStackSlot;
251  }
252
253  static Location DoubleStackSlot(intptr_t stack_index) {
254    uintptr_t payload = EncodeStackIndex(stack_index);
255    Location loc(kDoubleStackSlot, payload);
256    // Ensure that sign is preserved.
257    DCHECK_EQ(loc.GetStackIndex(), stack_index);
258    return loc;
259  }
260
261  bool IsDoubleStackSlot() const {
262    return GetKind() == kDoubleStackSlot;
263  }
264
265  intptr_t GetStackIndex() const {
266    DCHECK(IsStackSlot() || IsDoubleStackSlot());
267    // Decode stack index manually to preserve sign.
268    return GetPayload() - kStackIndexBias;
269  }
270
271  intptr_t GetHighStackIndex(uintptr_t word_size) const {
272    DCHECK(IsDoubleStackSlot());
273    // Decode stack index manually to preserve sign.
274    return GetPayload() - kStackIndexBias + word_size;
275  }
276
277  Kind GetKind() const {
278    return IsConstant() ? kConstant : KindField::Decode(value_);
279  }
280
281  bool Equals(Location other) const {
282    return value_ == other.value_;
283  }
284
285  bool Contains(Location other) const {
286    if (Equals(other)) {
287      return true;
288    } else if (IsPair() || IsDoubleStackSlot()) {
289      return ToLow().Equals(other) || ToHigh().Equals(other);
290    }
291    return false;
292  }
293
294  bool OverlapsWith(Location other) const {
295    // Only check the overlapping case that can happen with our register allocation algorithm.
296    bool overlap = Contains(other) || other.Contains(*this);
297    if (kIsDebugBuild && !overlap) {
298      // Note: These are also overlapping cases. But we are not able to handle them in
299      // ParallelMoveResolverWithSwap. Make sure that we do not meet such case with our compiler.
300      if ((IsPair() && other.IsPair()) || (IsDoubleStackSlot() && other.IsDoubleStackSlot())) {
301        DCHECK(!Contains(other.ToLow()));
302        DCHECK(!Contains(other.ToHigh()));
303      }
304    }
305    return overlap;
306  }
307
308  const char* DebugString() const {
309    switch (GetKind()) {
310      case kInvalid: return "I";
311      case kRegister: return "R";
312      case kStackSlot: return "S";
313      case kDoubleStackSlot: return "DS";
314      case kUnallocated: return "U";
315      case kConstant: return "C";
316      case kFpuRegister: return "F";
317      case kRegisterPair: return "RP";
318      case kFpuRegisterPair: return "FP";
319      case kDoNotUse5:  // fall-through
320      case kDoNotUse9:
321        LOG(FATAL) << "Should not use this location kind";
322    }
323    UNREACHABLE();
324    return "?";
325  }
326
327  // Unallocated locations.
328  enum Policy {
329    kAny,
330    kRequiresRegister,
331    kRequiresFpuRegister,
332    kSameAsFirstInput,
333  };
334
335  bool IsUnallocated() const {
336    return GetKind() == kUnallocated;
337  }
338
339  static Location UnallocatedLocation(Policy policy) {
340    return Location(kUnallocated, PolicyField::Encode(policy));
341  }
342
343  // Any free register is suitable to replace this unallocated location.
344  static Location Any() {
345    return UnallocatedLocation(kAny);
346  }
347
348  static Location RequiresRegister() {
349    return UnallocatedLocation(kRequiresRegister);
350  }
351
352  static Location RequiresFpuRegister() {
353    return UnallocatedLocation(kRequiresFpuRegister);
354  }
355
356  static Location RegisterOrConstant(HInstruction* instruction);
357  static Location RegisterOrInt32Constant(HInstruction* instruction);
358  static Location ByteRegisterOrConstant(int reg, HInstruction* instruction);
359  static Location FpuRegisterOrConstant(HInstruction* instruction);
360  static Location FpuRegisterOrInt32Constant(HInstruction* instruction);
361
362  // The location of the first input to the instruction will be
363  // used to replace this unallocated location.
364  static Location SameAsFirstInput() {
365    return UnallocatedLocation(kSameAsFirstInput);
366  }
367
368  Policy GetPolicy() const {
369    DCHECK(IsUnallocated());
370    return PolicyField::Decode(GetPayload());
371  }
372
373  uintptr_t GetEncoding() const {
374    return GetPayload();
375  }
376
377 private:
378  // Number of bits required to encode Kind value.
379  static constexpr uint32_t kBitsForKind = 4;
380  static constexpr uint32_t kBitsForPayload = kBitsPerIntPtrT - kBitsForKind;
381  static constexpr uintptr_t kLocationConstantMask = 0x3;
382
383  explicit Location(uintptr_t value) : value_(value) {}
384
385  Location(Kind kind, uintptr_t payload)
386      : value_(KindField::Encode(kind) | PayloadField::Encode(payload)) {}
387
388  uintptr_t GetPayload() const {
389    return PayloadField::Decode(value_);
390  }
391
392  typedef BitField<Kind, 0, kBitsForKind> KindField;
393  typedef BitField<uintptr_t, kBitsForKind, kBitsForPayload> PayloadField;
394
395  // Layout for kUnallocated locations payload.
396  typedef BitField<Policy, 0, 3> PolicyField;
397
398  // Layout for stack slots.
399  static const intptr_t kStackIndexBias =
400      static_cast<intptr_t>(1) << (kBitsForPayload - 1);
401
402  // Location either contains kind and payload fields or a tagged handle for
403  // a constant locations. Values of enumeration Kind are selected in such a
404  // way that none of them can be interpreted as a kConstant tag.
405  uintptr_t value_;
406};
407std::ostream& operator<<(std::ostream& os, const Location::Kind& rhs);
408std::ostream& operator<<(std::ostream& os, const Location::Policy& rhs);
409
410class RegisterSet : public ValueObject {
411 public:
412  RegisterSet() : core_registers_(0), floating_point_registers_(0) {}
413
414  void Add(Location loc) {
415    if (loc.IsRegister()) {
416      core_registers_ |= (1 << loc.reg());
417    } else {
418      DCHECK(loc.IsFpuRegister());
419      floating_point_registers_ |= (1 << loc.reg());
420    }
421  }
422
423  void Remove(Location loc) {
424    if (loc.IsRegister()) {
425      core_registers_ &= ~(1 << loc.reg());
426    } else {
427      DCHECK(loc.IsFpuRegister()) << loc;
428      floating_point_registers_ &= ~(1 << loc.reg());
429    }
430  }
431
432  bool ContainsCoreRegister(uint32_t id) const {
433    return Contains(core_registers_, id);
434  }
435
436  bool ContainsFloatingPointRegister(uint32_t id) const {
437    return Contains(floating_point_registers_, id);
438  }
439
440  static bool Contains(uint32_t register_set, uint32_t reg) {
441    return (register_set & (1 << reg)) != 0;
442  }
443
444  size_t GetNumberOfRegisters() const {
445    return __builtin_popcount(core_registers_) + __builtin_popcount(floating_point_registers_);
446  }
447
448  uint32_t GetCoreRegisters() const {
449    return core_registers_;
450  }
451
452  uint32_t GetFloatingPointRegisters() const {
453    return floating_point_registers_;
454  }
455
456 private:
457  uint32_t core_registers_;
458  uint32_t floating_point_registers_;
459
460  DISALLOW_COPY_AND_ASSIGN(RegisterSet);
461};
462
463static constexpr bool kIntrinsified = true;
464
465/**
466 * The code generator computes LocationSummary for each instruction so that
467 * the instruction itself knows what code to generate: where to find the inputs
468 * and where to place the result.
469 *
470 * The intent is to have the code for generating the instruction independent of
471 * register allocation. A register allocator just has to provide a LocationSummary.
472 */
473class LocationSummary : public ArenaObject<kArenaAllocLocationSummary> {
474 public:
475  enum CallKind {
476    kNoCall,
477    kCallOnSlowPath,
478    kCall
479  };
480
481  LocationSummary(HInstruction* instruction,
482                  CallKind call_kind = kNoCall,
483                  bool intrinsified = false);
484
485  void SetInAt(uint32_t at, Location location) {
486    inputs_[at] = location;
487  }
488
489  Location InAt(uint32_t at) const {
490    return inputs_[at];
491  }
492
493  size_t GetInputCount() const {
494    return inputs_.size();
495  }
496
497  void SetOut(Location location, Location::OutputOverlap overlaps = Location::kOutputOverlap) {
498    DCHECK(output_.IsInvalid());
499    output_overlaps_ = overlaps;
500    output_ = location;
501  }
502
503  void UpdateOut(Location location) {
504    // There are two reasons for updating an output:
505    // 1) Parameters, where we only know the exact stack slot after
506    //    doing full register allocation.
507    // 2) Unallocated location.
508    DCHECK(output_.IsStackSlot() || output_.IsDoubleStackSlot() || output_.IsUnallocated());
509    output_ = location;
510  }
511
512  void AddTemp(Location location) {
513    temps_.push_back(location);
514  }
515
516  Location GetTemp(uint32_t at) const {
517    return temps_[at];
518  }
519
520  void SetTempAt(uint32_t at, Location location) {
521    DCHECK(temps_[at].IsUnallocated() || temps_[at].IsInvalid());
522    temps_[at] = location;
523  }
524
525  size_t GetTempCount() const {
526    return temps_.size();
527  }
528
529  bool HasTemps() const { return !temps_.empty(); }
530
531  Location Out() const { return output_; }
532
533  bool CanCall() const { return call_kind_ != kNoCall; }
534  bool WillCall() const { return call_kind_ == kCall; }
535  bool OnlyCallsOnSlowPath() const { return call_kind_ == kCallOnSlowPath; }
536  bool NeedsSafepoint() const { return CanCall(); }
537
538  void SetStackBit(uint32_t index) {
539    stack_mask_->SetBit(index);
540  }
541
542  void ClearStackBit(uint32_t index) {
543    stack_mask_->ClearBit(index);
544  }
545
546  void SetRegisterBit(uint32_t reg_id) {
547    register_mask_ |= (1 << reg_id);
548  }
549
550  uint32_t GetRegisterMask() const {
551    return register_mask_;
552  }
553
554  bool RegisterContainsObject(uint32_t reg_id) {
555    return RegisterSet::Contains(register_mask_, reg_id);
556  }
557
558  void AddLiveRegister(Location location) {
559    live_registers_.Add(location);
560  }
561
562  BitVector* GetStackMask() const {
563    return stack_mask_;
564  }
565
566  RegisterSet* GetLiveRegisters() {
567    return &live_registers_;
568  }
569
570  size_t GetNumberOfLiveRegisters() const {
571    return live_registers_.GetNumberOfRegisters();
572  }
573
574  bool OutputUsesSameAs(uint32_t input_index) const {
575    return (input_index == 0)
576        && output_.IsUnallocated()
577        && (output_.GetPolicy() == Location::kSameAsFirstInput);
578  }
579
580  bool IsFixedInput(uint32_t input_index) const {
581    Location input = inputs_[input_index];
582    return input.IsRegister()
583        || input.IsFpuRegister()
584        || input.IsPair()
585        || input.IsStackSlot()
586        || input.IsDoubleStackSlot();
587  }
588
589  bool OutputCanOverlapWithInputs() const {
590    return output_overlaps_ == Location::kOutputOverlap;
591  }
592
593  bool Intrinsified() const {
594    return intrinsified_;
595  }
596
597  void SetIntrinsified(bool intrinsified) {
598    intrinsified_ = intrinsified;
599  }
600
601 private:
602  ArenaVector<Location> inputs_;
603  ArenaVector<Location> temps_;
604  // Whether the output overlaps with any of the inputs. If it overlaps, then it cannot
605  // share the same register as the inputs.
606  Location::OutputOverlap output_overlaps_;
607  Location output_;
608  const CallKind call_kind_;
609
610  // Mask of objects that live in the stack.
611  BitVector* stack_mask_;
612
613  // Mask of objects that live in register.
614  uint32_t register_mask_;
615
616  // Registers that are in use at this position.
617  RegisterSet live_registers_;
618
619  // Whether these are locations for an intrinsified call.
620  bool intrinsified_;
621
622  ART_FRIEND_TEST(RegisterAllocatorTest, ExpectedInRegisterHint);
623  ART_FRIEND_TEST(RegisterAllocatorTest, SameAsFirstInputHint);
624  DISALLOW_COPY_AND_ASSIGN(LocationSummary);
625};
626
627}  // namespace art
628
629#endif  // ART_COMPILER_OPTIMIZING_LOCATIONS_H_
630