The data contained in this repository can be downloaded to your computer using one of several clients.
Please see the documentation of your version control software client for more information.
Please select the desired protocol below to get the URL.
This URL has Read-Only access.
main_repo / deps / v8 / src / register-allocator.h @ 40c0f755
History | View | Annotate | Download (10.6 KB)
1 | 40c0f755 | Ryan | // Copyright 2008 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 | #ifndef V8_REGISTER_ALLOCATOR_H_
|
||
29 | #define V8_REGISTER_ALLOCATOR_H_
|
||
30 | |||
31 | #include "macro-assembler.h" |
||
32 | |||
33 | namespace v8 { namespace internal { |
||
34 | |||
35 | |||
36 | // -------------------------------------------------------------------------
|
||
37 | // StaticType
|
||
38 | //
|
||
39 | // StaticType represent the type of an expression or a word at runtime.
|
||
40 | // The types are ordered by knowledge, so that if a value can come about
|
||
41 | // in more than one way, and there are different static types inferred
|
||
42 | // for the different ways, the types can be combined to a type that we
|
||
43 | // are still certain of (possibly just "unknown").
|
||
44 | |||
45 | class StaticType BASE_EMBEDDED { |
||
46 | public:
|
||
47 | StaticType() : static_type_(UNKNOWN_TYPE) {} |
||
48 | |||
49 | static StaticType unknown() { return StaticType(); } |
||
50 | static StaticType smi() { return StaticType(SMI_TYPE); } |
||
51 | static StaticType jsstring() { return StaticType(STRING_TYPE); } |
||
52 | static StaticType heap_object() { return StaticType(HEAP_OBJECT_TYPE); } |
||
53 | |||
54 | // Accessors
|
||
55 | bool is_unknown() { return static_type_ == UNKNOWN_TYPE; } |
||
56 | bool is_smi() { return static_type_ == SMI_TYPE; } |
||
57 | bool is_heap_object() { return (static_type_ & HEAP_OBJECT_TYPE) != 0; } |
||
58 | bool is_jsstring() { return static_type_ == STRING_TYPE; } |
||
59 | |||
60 | bool operator==(StaticType other) const { |
||
61 | return static_type_ == other.static_type_;
|
||
62 | } |
||
63 | |||
64 | // Find the best approximating type for a value.
|
||
65 | // The argument must not be NULL.
|
||
66 | static StaticType TypeOf(Object* object) {
|
||
67 | // Remember to make the most specific tests first. A string is also a heap
|
||
68 | // object, so test for string-ness first.
|
||
69 | if (object->IsSmi()) return smi(); |
||
70 | if (object->IsString()) return jsstring(); |
||
71 | if (object->IsHeapObject()) return heap_object(); |
||
72 | return unknown();
|
||
73 | } |
||
74 | |||
75 | // Merges two static types to a type that combines the knowledge
|
||
76 | // of both. If there is no way to combine (e.g., being a string *and*
|
||
77 | // being a smi), the resulting type is unknown.
|
||
78 | StaticType merge(StaticType other) { |
||
79 | StaticType x( |
||
80 | static_cast<StaticTypeEnum>(static_type_ & other.static_type_)); |
||
81 | return x;
|
||
82 | } |
||
83 | |||
84 | private:
|
||
85 | enum StaticTypeEnum {
|
||
86 | // Numbers are chosen so that least upper bound of the following
|
||
87 | // partial order is implemented by bitwise "and":
|
||
88 | //
|
||
89 | // string
|
||
90 | // |
|
||
91 | // heap-object smi
|
||
92 | // \ /
|
||
93 | // unknown
|
||
94 | //
|
||
95 | UNKNOWN_TYPE = 0x00,
|
||
96 | SMI_TYPE = 0x01,
|
||
97 | HEAP_OBJECT_TYPE = 0x02,
|
||
98 | STRING_TYPE = 0x04 | HEAP_OBJECT_TYPE
|
||
99 | }; |
||
100 | explicit StaticType(StaticTypeEnum static_type) : static_type_(static_type) {} |
||
101 | |||
102 | // StaticTypeEnum static_type_;
|
||
103 | byte static_type_; |
||
104 | }; |
||
105 | |||
106 | |||
107 | // -------------------------------------------------------------------------
|
||
108 | // Results
|
||
109 | //
|
||
110 | // Results encapsulate the compile-time values manipulated by the code
|
||
111 | // generator. They can represent registers or constants.
|
||
112 | |||
113 | class Result BASE_EMBEDDED { |
||
114 | public:
|
||
115 | enum Type {
|
||
116 | INVALID, |
||
117 | REGISTER, |
||
118 | CONSTANT |
||
119 | }; |
||
120 | |||
121 | // Construct an invalid result.
|
||
122 | explicit Result(CodeGenerator* cgen) |
||
123 | : static_type_(), |
||
124 | type_(INVALID), |
||
125 | cgen_(cgen) {} |
||
126 | |||
127 | // Construct a register Result.
|
||
128 | Result(Register reg, |
||
129 | CodeGenerator* cgen); |
||
130 | |||
131 | // Construct a register Result with a known static type.
|
||
132 | Result(Register reg, |
||
133 | CodeGenerator* cgen, |
||
134 | StaticType static_type); |
||
135 | |||
136 | // Construct a Result whose value is a compile-time constant.
|
||
137 | Result(Handle<Object> value, CodeGenerator * cgen) |
||
138 | : static_type_(StaticType::TypeOf(*value)), |
||
139 | type_(CONSTANT), |
||
140 | cgen_(cgen) { |
||
141 | data_.handle_ = value.location(); |
||
142 | } |
||
143 | |||
144 | // The copy constructor and assignment operators could each create a new
|
||
145 | // register reference.
|
||
146 | Result(const Result& other) {
|
||
147 | other.CopyTo(this); |
||
148 | } |
||
149 | |||
150 | Result& operator=(const Result& other) {
|
||
151 | if (this != &other) {
|
||
152 | Unuse(); |
||
153 | other.CopyTo(this); |
||
154 | } |
||
155 | return *this;
|
||
156 | } |
||
157 | |||
158 | inline ~Result();
|
||
159 | |||
160 | inline void Unuse(); |
||
161 | |||
162 | StaticType static_type() const { return static_type_; } |
||
163 | void set_static_type(StaticType static_type) { static_type_ = static_type; }
|
||
164 | |||
165 | Type type() const { return static_cast<Type>(type_); } |
||
166 | |||
167 | bool is_valid() const { return type() != INVALID; } |
||
168 | bool is_register() const { return type() == REGISTER; } |
||
169 | bool is_constant() const { return type() == CONSTANT; } |
||
170 | |||
171 | Register reg() const {
|
||
172 | ASSERT(type() == REGISTER); |
||
173 | return data_.reg_;
|
||
174 | } |
||
175 | |||
176 | Handle<Object> handle() const {
|
||
177 | ASSERT(type() == CONSTANT); |
||
178 | return Handle<Object>(data_.handle_);
|
||
179 | } |
||
180 | |||
181 | // Move this result to an arbitrary register. The register is not
|
||
182 | // necessarily spilled from the frame or even singly-referenced outside
|
||
183 | // it.
|
||
184 | void ToRegister();
|
||
185 | |||
186 | // Move this result to a specified register. The register is spilled from
|
||
187 | // the frame, and the register is singly-referenced (by this result)
|
||
188 | // outside the frame.
|
||
189 | void ToRegister(Register reg);
|
||
190 | |||
191 | private:
|
||
192 | StaticType static_type_; |
||
193 | byte type_; |
||
194 | |||
195 | union {
|
||
196 | Register reg_; |
||
197 | Object** handle_; |
||
198 | } data_; |
||
199 | |||
200 | CodeGenerator* cgen_; |
||
201 | |||
202 | void CopyTo(Result* destination) const; |
||
203 | }; |
||
204 | |||
205 | |||
206 | // -------------------------------------------------------------------------
|
||
207 | // Register file
|
||
208 | //
|
||
209 | // The register file tracks reference counts for the processor registers.
|
||
210 | // It is used by both the register allocator and the virtual frame.
|
||
211 | |||
212 | class RegisterFile BASE_EMBEDDED { |
||
213 | public:
|
||
214 | RegisterFile() { Reset(); } |
||
215 | |||
216 | void Reset() {
|
||
217 | for (int i = 0; i < kNumRegisters; i++) { |
||
218 | ref_counts_[i] = 0;
|
||
219 | } |
||
220 | } |
||
221 | |||
222 | // Predicates and accessors for the reference counts. The versions
|
||
223 | // that take a register code rather than a register are for
|
||
224 | // convenience in loops over the register codes.
|
||
225 | bool is_used(int reg_code) const { return ref_counts_[reg_code] > 0; } |
||
226 | bool is_used(Register reg) const { return is_used(reg.code()); } |
||
227 | int count(int reg_code) const { return ref_counts_[reg_code]; } |
||
228 | int count(Register reg) const { return count(reg.code()); } |
||
229 | |||
230 | // Record a use of a register by incrementing its reference count.
|
||
231 | void Use(Register reg) {
|
||
232 | ref_counts_[reg.code()]++; |
||
233 | } |
||
234 | |||
235 | // Record that a register will no longer be used by decrementing its
|
||
236 | // reference count.
|
||
237 | void Unuse(Register reg) {
|
||
238 | ASSERT(!reg.is(no_reg)); |
||
239 | ASSERT(is_used(reg.code())); |
||
240 | ref_counts_[reg.code()]--; |
||
241 | } |
||
242 | |||
243 | // Copy the reference counts from this register file to the other.
|
||
244 | void CopyTo(RegisterFile* other);
|
||
245 | |||
246 | private:
|
||
247 | int ref_counts_[kNumRegisters];
|
||
248 | |||
249 | // Very fast inlined loop to find a free register.
|
||
250 | // Used in RegisterAllocator::AllocateWithoutSpilling.
|
||
251 | // Returns kNumRegisters if no free register found.
|
||
252 | inline int ScanForFreeRegister() { |
||
253 | int i = 0; |
||
254 | for (; i < kNumRegisters ; ++i) {
|
||
255 | if (ref_counts_[i] == 0) break; |
||
256 | } |
||
257 | return i;
|
||
258 | } |
||
259 | |||
260 | friend class RegisterAllocator; |
||
261 | }; |
||
262 | |||
263 | |||
264 | // -------------------------------------------------------------------------
|
||
265 | // Register allocator
|
||
266 | //
|
||
267 | |||
268 | class RegisterAllocator BASE_EMBEDDED { |
||
269 | public:
|
||
270 | explicit RegisterAllocator(CodeGenerator* cgen) : cgen_(cgen) {} |
||
271 | |||
272 | // A register file with each of the reserved registers counted once.
|
||
273 | static RegisterFile Reserved();
|
||
274 | |||
275 | // Unuse all the reserved registers in a register file.
|
||
276 | static void UnuseReserved(RegisterFile* register_file); |
||
277 | |||
278 | // Predicates and accessors for the registers' reference counts.
|
||
279 | bool is_used(int reg_code) const { return registers_.is_used(reg_code); } |
||
280 | bool is_used(Register reg) const { return registers_.is_used(reg.code()); } |
||
281 | int count(int reg_code) const { return registers_.count(reg_code); } |
||
282 | int count(Register reg) const { return registers_.count(reg.code()); } |
||
283 | |||
284 | // Explicitly record a reference to a register.
|
||
285 | void Use(Register reg) { registers_.Use(reg); }
|
||
286 | |||
287 | // Explicitly record that a register will no longer be used.
|
||
288 | void Unuse(Register reg) { registers_.Unuse(reg); }
|
||
289 | |||
290 | // Initialize the register allocator for entry to a JS function. On
|
||
291 | // entry, the registers used by the JS calling convention are
|
||
292 | // externally referenced (ie, outside the virtual frame); and the
|
||
293 | // other registers are free.
|
||
294 | void Initialize();
|
||
295 | |||
296 | // Reset the register reference counts to free all non-reserved registers.
|
||
297 | // A frame-external reference is kept to each of the reserved registers.
|
||
298 | void Reset();
|
||
299 | |||
300 | // Allocate a free register and return a register result if possible or
|
||
301 | // fail and return an invalid result.
|
||
302 | Result Allocate(); |
||
303 | |||
304 | // Allocate a specific register if possible, spilling it from the frame if
|
||
305 | // necessary, or else fail and return an invalid result.
|
||
306 | Result Allocate(Register target); |
||
307 | |||
308 | // Allocate a free register without spilling any from the current frame or
|
||
309 | // fail and return an invalid result.
|
||
310 | Result AllocateWithoutSpilling(); |
||
311 | |||
312 | // Allocate a free byte register without spilling any from the
|
||
313 | // current frame or fail and return an invalid result.
|
||
314 | Result AllocateByteRegisterWithoutSpilling(); |
||
315 | |||
316 | // Copy the internal state to a register file, to be restored later by
|
||
317 | // RestoreFrom.
|
||
318 | void SaveTo(RegisterFile* register_file) {
|
||
319 | registers_.CopyTo(register_file); |
||
320 | } |
||
321 | |||
322 | void RestoreFrom(RegisterFile* register_file) {
|
||
323 | register_file->CopyTo(®isters_); |
||
324 | } |
||
325 | |||
326 | private:
|
||
327 | CodeGenerator* cgen_; |
||
328 | RegisterFile registers_; |
||
329 | }; |
||
330 | |||
331 | } } // namespace v8::internal
|
||
332 | |||
333 | #endif // V8_REGISTER_ALLOCATOR_H_ |