locations.h revision 96f89a290eb67d7bf4b1636798fa28df14309cc7 
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/bit_field.h"
21#include "utils/allocation.h"
22#include "utils/growable_array.h"
23#include "utils/managed_register.h"
24
25namespace art {
26
27class HConstant;
28class HInstruction;
29
30/**
31 * A Location is an abstraction over the potential location
32 * of an instruction. It could be in register or stack.
33 */
34class Location : public ValueObject {
35 public:
36  enum Kind {
37    kInvalid = 0,
38    kConstant = 1,
39    kStackSlot = 2,  // Word size slot.
40    kDoubleStackSlot = 3,  // 64bit stack slot.
41    kRegister = 4,
42    // On 32bits architectures, quick can pass a long where the
43    // low bits are in the last parameter register, and the high
44    // bits are in a stack slot. The kQuickParameter kind is for
45    // handling this special case.
46    kQuickParameter = 5,
47
48    // Unallocated location represents a location that is not fixed and can be
49    // allocated by a register allocator.  Each unallocated location has
50    // a policy that specifies what kind of location is suitable. Payload
51    // contains register allocation policy.
52    kUnallocated = 6,
53  };
54
55  Location() : value_(kInvalid) {
56    // Verify that non-tagged location kinds do not interfere with kConstantTag.
57    COMPILE_ASSERT((kInvalid & kLocationTagMask) != kConstant, TagError);
58    COMPILE_ASSERT((kUnallocated & kLocationTagMask) != kConstant, TagError);
59    COMPILE_ASSERT((kStackSlot & kLocationTagMask) != kConstant, TagError);
60    COMPILE_ASSERT((kDoubleStackSlot & kLocationTagMask) != kConstant, TagError);
61    COMPILE_ASSERT((kRegister & kLocationTagMask) != kConstant, TagError);
62    COMPILE_ASSERT((kConstant & kLocationTagMask) == kConstant, TagError);
63    COMPILE_ASSERT((kQuickParameter & kLocationTagMask) == kConstant, TagError);
64
65    DCHECK(!IsValid());
66  }
67
68  Location(const Location& other) : ValueObject(), value_(other.value_) {}
69
70  Location& operator=(const Location& other) {
71    value_ = other.value_;
72    return *this;
73  }
74
75  bool IsConstant() const {
76    return (value_ & kLocationTagMask) == kConstant;
77  }
78
79  static Location ConstantLocation(HConstant* constant) {
80    DCHECK(constant != nullptr);
81    return Location(kConstant | reinterpret_cast<uword>(constant));
82  }
83
84  HConstant* GetConstant() const {
85    DCHECK(IsConstant());
86    return reinterpret_cast<HConstant*>(value_ & ~kLocationTagMask);
87  }
88
89  bool IsValid() const {
90    return value_ != kInvalid;
91  }
92
93  bool IsInvalid() const {
94    return !IsValid();
95  }
96
97  // Empty location. Used if there the location should be ignored.
98  static Location NoLocation() {
99    return Location();
100  }
101
102  // Register locations.
103  static Location RegisterLocation(ManagedRegister reg) {
104    return Location(kRegister, reg.RegId());
105  }
106
107  bool IsRegister() const {
108    return GetKind() == kRegister;
109  }
110
111  ManagedRegister reg() const {
112    DCHECK(IsRegister());
113    return static_cast<ManagedRegister>(GetPayload());
114  }
115
116  static uword EncodeStackIndex(intptr_t stack_index) {
117    DCHECK(-kStackIndexBias <= stack_index);
118    DCHECK(stack_index < kStackIndexBias);
119    return static_cast<uword>(kStackIndexBias + stack_index);
120  }
121
122  static Location StackSlot(intptr_t stack_index) {
123    uword payload = EncodeStackIndex(stack_index);
124    Location loc(kStackSlot, payload);
125    // Ensure that sign is preserved.
126    DCHECK_EQ(loc.GetStackIndex(), stack_index);
127    return loc;
128  }
129
130  bool IsStackSlot() const {
131    return GetKind() == kStackSlot;
132  }
133
134  static Location DoubleStackSlot(intptr_t stack_index) {
135    uword payload = EncodeStackIndex(stack_index);
136    Location loc(kDoubleStackSlot, payload);
137    // Ensure that sign is preserved.
138    DCHECK_EQ(loc.GetStackIndex(), stack_index);
139    return loc;
140  }
141
142  bool IsDoubleStackSlot() const {
143    return GetKind() == kDoubleStackSlot;
144  }
145
146  intptr_t GetStackIndex() const {
147    DCHECK(IsStackSlot() || IsDoubleStackSlot());
148    // Decode stack index manually to preserve sign.
149    return GetPayload() - kStackIndexBias;
150  }
151
152  intptr_t GetHighStackIndex(uintptr_t word_size) const {
153    DCHECK(IsDoubleStackSlot());
154    // Decode stack index manually to preserve sign.
155    return GetPayload() - kStackIndexBias + word_size;
156  }
157
158  static Location QuickParameter(uint32_t parameter_index) {
159    return Location(kQuickParameter, parameter_index);
160  }
161
162  uint32_t GetQuickParameterIndex() const {
163    DCHECK(IsQuickParameter());
164    return GetPayload();
165  }
166
167  bool IsQuickParameter() const {
168    return GetKind() == kQuickParameter;
169  }
170
171  arm::ArmManagedRegister AsArm() const;
172  x86::X86ManagedRegister AsX86() const;
173  x86_64::X86_64ManagedRegister AsX86_64() const;
174
175  Kind GetKind() const {
176    return KindField::Decode(value_);
177  }
178
179  bool Equals(Location other) const {
180    return value_ == other.value_;
181  }
182
183  const char* DebugString() const {
184    switch (GetKind()) {
185      case kInvalid: return "I";
186      case kRegister: return "R";
187      case kStackSlot: return "S";
188      case kDoubleStackSlot: return "DS";
189      case kQuickParameter: return "Q";
190      case kUnallocated: return "U";
191      case kConstant: return "C";
192    }
193    return "?";
194  }
195
196  // Unallocated locations.
197  enum Policy {
198    kAny,
199    kRequiresRegister,
200    kSameAsFirstInput,
201  };
202
203  bool IsUnallocated() const {
204    return GetKind() == kUnallocated;
205  }
206
207  static Location UnallocatedLocation(Policy policy) {
208    return Location(kUnallocated, PolicyField::Encode(policy));
209  }
210
211  // Any free register is suitable to replace this unallocated location.
212  static Location Any() {
213    return UnallocatedLocation(kAny);
214  }
215
216  static Location RequiresRegister() {
217    return UnallocatedLocation(kRequiresRegister);
218  }
219
220  static Location RegisterOrConstant(HInstruction* instruction);
221
222  // The location of the first input to the instruction will be
223  // used to replace this unallocated location.
224  static Location SameAsFirstInput() {
225    return UnallocatedLocation(kSameAsFirstInput);
226  }
227
228  Policy GetPolicy() const {
229    DCHECK(IsUnallocated());
230    return PolicyField::Decode(GetPayload());
231  }
232
233  uword GetEncoding() const {
234    return GetPayload();
235  }
236
237 private:
238  // Number of bits required to encode Kind value.
239  static constexpr uint32_t kBitsForKind = 4;
240  static constexpr uint32_t kBitsForPayload = kWordSize * kBitsPerByte - kBitsForKind;
241  static constexpr uword kLocationTagMask = 0x3;
242
243  explicit Location(uword value) : value_(value) {}
244
245  Location(Kind kind, uword payload)
246      : value_(KindField::Encode(kind) | PayloadField::Encode(payload)) {}
247
248  uword GetPayload() const {
249    return PayloadField::Decode(value_);
250  }
251
252  typedef BitField<Kind, 0, kBitsForKind> KindField;
253  typedef BitField<uword, kBitsForKind, kBitsForPayload> PayloadField;
254
255  // Layout for kUnallocated locations payload.
256  typedef BitField<Policy, 0, 3> PolicyField;
257
258  // Layout for stack slots.
259  static const intptr_t kStackIndexBias =
260      static_cast<intptr_t>(1) << (kBitsForPayload - 1);
261
262  // Location either contains kind and payload fields or a tagged handle for
263  // a constant locations. Values of enumeration Kind are selected in such a
264  // way that none of them can be interpreted as a kConstant tag.
265  uword value_;
266};
267
268/**
269 * The code generator computes LocationSummary for each instruction so that
270 * the instruction itself knows what code to generate: where to find the inputs
271 * and where to place the result.
272 *
273 * The intent is to have the code for generating the instruction independent of
274 * register allocation. A register allocator just has to provide a LocationSummary.
275 */
276class LocationSummary : public ArenaObject {
277 public:
278  explicit LocationSummary(HInstruction* instruction);
279
280  void SetInAt(uint32_t at, Location location) {
281    inputs_.Put(at, location);
282  }
283
284  Location InAt(uint32_t at) const {
285    return inputs_.Get(at);
286  }
287
288  size_t GetInputCount() const {
289    return inputs_.Size();
290  }
291
292  void SetOut(Location location) {
293    output_ = Location(location);
294  }
295
296  void AddTemp(Location location) {
297    temps_.Add(location);
298  }
299
300  Location GetTemp(uint32_t at) const {
301    return temps_.Get(at);
302  }
303
304  void SetTempAt(uint32_t at, Location location) {
305    temps_.Put(at, location);
306  }
307
308  size_t GetTempCount() const {
309    return temps_.Size();
310  }
311
312  Location Out() const { return output_; }
313
314 private:
315  GrowableArray<Location> inputs_;
316  GrowableArray<Location> temps_;
317  Location output_;
318
319  DISALLOW_COPY_AND_ASSIGN(LocationSummary);
320};
321
322}  // namespace art
323
324#endif  // ART_COMPILER_OPTIMIZING_LOCATIONS_H_
325