OLD | NEW |
1 // Copyright 2012 the V8 project authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #ifndef V8_LITHIUM_ALLOCATOR_H_ | 5 #ifndef V8_REGISTER_ALLOCATOR_H_ |
6 #define V8_LITHIUM_ALLOCATOR_H_ | 6 #define V8_REGISTER_ALLOCATOR_H_ |
7 | |
8 #include "src/v8.h" | |
9 | 7 |
10 #include "src/allocation.h" | 8 #include "src/allocation.h" |
11 #include "src/lithium.h" | 9 #include "src/compiler/instruction.h" |
| 10 #include "src/compiler/node.h" |
| 11 #include "src/compiler/schedule.h" |
| 12 #include "src/macro-assembler.h" |
12 #include "src/zone.h" | 13 #include "src/zone.h" |
13 | 14 |
14 namespace v8 { | 15 namespace v8 { |
15 namespace internal { | 16 namespace internal { |
16 | 17 |
17 // Forward declarations. | 18 // Forward declarations. |
18 class HBasicBlock; | |
19 class HGraph; | |
20 class HInstruction; | |
21 class HPhi; | |
22 class HTracer; | |
23 class HValue; | |
24 class BitVector; | 19 class BitVector; |
25 class StringStream; | 20 class InstructionOperand; |
| 21 class UnallocatedOperand; |
| 22 class ParallelMove; |
| 23 class PointerMap; |
26 | 24 |
27 class LPlatformChunk; | 25 namespace compiler { |
28 class LOperand; | 26 |
29 class LUnallocated; | 27 enum RegisterKind { |
30 class LGap; | 28 UNALLOCATED_REGISTERS, |
31 class LParallelMove; | 29 GENERAL_REGISTERS, |
32 class LPointerMap; | 30 DOUBLE_REGISTERS |
| 31 }; |
33 | 32 |
34 | 33 |
35 // This class represents a single point of a LOperand's lifetime. | 34 // This class represents a single point of a InstructionOperand's lifetime. For |
36 // For each lithium instruction there are exactly two lifetime positions: | 35 // each instruction there are exactly two lifetime positions: the beginning and |
37 // the beginning and the end of the instruction. Lifetime positions for | 36 // the end of the instruction. Lifetime positions for different instructions are |
38 // different lithium instructions are disjoint. | 37 // disjoint. |
39 class LifetimePosition { | 38 class LifetimePosition { |
40 public: | 39 public: |
41 // Return the lifetime position that corresponds to the beginning of | 40 // Return the lifetime position that corresponds to the beginning of |
42 // the instruction with the given index. | 41 // the instruction with the given index. |
43 static LifetimePosition FromInstructionIndex(int index) { | 42 static LifetimePosition FromInstructionIndex(int index) { |
44 return LifetimePosition(index * kStep); | 43 return LifetimePosition(index * kStep); |
45 } | 44 } |
46 | 45 |
47 // Returns a numeric representation of this lifetime position. | 46 // Returns a numeric representation of this lifetime position. |
48 int Value() const { | 47 int Value() const { return value_; } |
49 return value_; | |
50 } | |
51 | 48 |
52 // Returns the index of the instruction to which this lifetime position | 49 // Returns the index of the instruction to which this lifetime position |
53 // corresponds. | 50 // corresponds. |
54 int InstructionIndex() const { | 51 int InstructionIndex() const { |
55 ASSERT(IsValid()); | 52 ASSERT(IsValid()); |
56 return value_ / kStep; | 53 return value_ / kStep; |
57 } | 54 } |
58 | 55 |
59 // Returns true if this lifetime position corresponds to the instruction | 56 // Returns true if this lifetime position corresponds to the instruction |
60 // start. | 57 // start. |
61 bool IsInstructionStart() const { | 58 bool IsInstructionStart() const { return (value_ & (kStep - 1)) == 0; } |
62 return (value_ & (kStep - 1)) == 0; | |
63 } | |
64 | 59 |
65 // Returns the lifetime position for the start of the instruction which | 60 // Returns the lifetime position for the start of the instruction which |
66 // corresponds to this lifetime position. | 61 // corresponds to this lifetime position. |
67 LifetimePosition InstructionStart() const { | 62 LifetimePosition InstructionStart() const { |
68 ASSERT(IsValid()); | 63 ASSERT(IsValid()); |
69 return LifetimePosition(value_ & ~(kStep - 1)); | 64 return LifetimePosition(value_ & ~(kStep - 1)); |
70 } | 65 } |
71 | 66 |
72 // Returns the lifetime position for the end of the instruction which | 67 // Returns the lifetime position for the end of the instruction which |
73 // corresponds to this lifetime position. | 68 // corresponds to this lifetime position. |
74 LifetimePosition InstructionEnd() const { | 69 LifetimePosition InstructionEnd() const { |
75 ASSERT(IsValid()); | 70 ASSERT(IsValid()); |
76 return LifetimePosition(InstructionStart().Value() + kStep/2); | 71 return LifetimePosition(InstructionStart().Value() + kStep / 2); |
77 } | 72 } |
78 | 73 |
79 // Returns the lifetime position for the beginning of the next instruction. | 74 // Returns the lifetime position for the beginning of the next instruction. |
80 LifetimePosition NextInstruction() const { | 75 LifetimePosition NextInstruction() const { |
81 ASSERT(IsValid()); | 76 ASSERT(IsValid()); |
82 return LifetimePosition(InstructionStart().Value() + kStep); | 77 return LifetimePosition(InstructionStart().Value() + kStep); |
83 } | 78 } |
84 | 79 |
85 // Returns the lifetime position for the beginning of the previous | 80 // Returns the lifetime position for the beginning of the previous |
86 // instruction. | 81 // instruction. |
(...skipping 18 matching lines...) Expand all Loading... |
105 // crash bug in GDB. | 100 // crash bug in GDB. |
106 return LifetimePosition(kMaxInt); | 101 return LifetimePosition(kMaxInt); |
107 } | 102 } |
108 | 103 |
109 private: | 104 private: |
110 static const int kStep = 2; | 105 static const int kStep = 2; |
111 | 106 |
112 // Code relies on kStep being a power of two. | 107 // Code relies on kStep being a power of two. |
113 STATIC_ASSERT(IS_POWER_OF_TWO(kStep)); | 108 STATIC_ASSERT(IS_POWER_OF_TWO(kStep)); |
114 | 109 |
115 explicit LifetimePosition(int value) : value_(value) { } | 110 explicit LifetimePosition(int value) : value_(value) {} |
116 | 111 |
117 int value_; | 112 int value_; |
118 }; | 113 }; |
119 | 114 |
120 | 115 |
121 enum RegisterKind { | |
122 UNALLOCATED_REGISTERS, | |
123 GENERAL_REGISTERS, | |
124 DOUBLE_REGISTERS | |
125 }; | |
126 | |
127 | |
128 // A register-allocator view of a Lithium instruction. It contains the id of | |
129 // the output operand and a list of input operand uses. | |
130 | |
131 class LInstruction; | |
132 class LEnvironment; | |
133 | |
134 // Iterator for non-null temp operands. | |
135 class TempIterator BASE_EMBEDDED { | |
136 public: | |
137 inline explicit TempIterator(LInstruction* instr); | |
138 inline bool Done(); | |
139 inline LOperand* Current(); | |
140 inline void Advance(); | |
141 | |
142 private: | |
143 inline void SkipUninteresting(); | |
144 LInstruction* instr_; | |
145 int limit_; | |
146 int current_; | |
147 }; | |
148 | |
149 | |
150 // Iterator for non-constant input operands. | |
151 class InputIterator BASE_EMBEDDED { | |
152 public: | |
153 inline explicit InputIterator(LInstruction* instr); | |
154 inline bool Done(); | |
155 inline LOperand* Current(); | |
156 inline void Advance(); | |
157 | |
158 private: | |
159 inline void SkipUninteresting(); | |
160 LInstruction* instr_; | |
161 int limit_; | |
162 int current_; | |
163 }; | |
164 | |
165 | |
166 class UseIterator BASE_EMBEDDED { | |
167 public: | |
168 inline explicit UseIterator(LInstruction* instr); | |
169 inline bool Done(); | |
170 inline LOperand* Current(); | |
171 inline void Advance(); | |
172 | |
173 private: | |
174 InputIterator input_iterator_; | |
175 DeepIterator env_iterator_; | |
176 }; | |
177 | |
178 | |
179 // Representation of the non-empty interval [start,end[. | 116 // Representation of the non-empty interval [start,end[. |
180 class UseInterval: public ZoneObject { | 117 class UseInterval : public ZoneObject { |
181 public: | 118 public: |
182 UseInterval(LifetimePosition start, LifetimePosition end) | 119 UseInterval(LifetimePosition start, LifetimePosition end) |
183 : start_(start), end_(end), next_(NULL) { | 120 : start_(start), end_(end), next_(NULL) { |
184 ASSERT(start.Value() < end.Value()); | 121 ASSERT(start.Value() < end.Value()); |
185 } | 122 } |
186 | 123 |
187 LifetimePosition start() const { return start_; } | 124 LifetimePosition start() const { return start_; } |
188 LifetimePosition end() const { return end_; } | 125 LifetimePosition end() const { return end_; } |
189 UseInterval* next() const { return next_; } | 126 UseInterval* next() const { return next_; } |
190 | 127 |
191 // Split this interval at the given position without effecting the | 128 // Split this interval at the given position without effecting the |
192 // live range that owns it. The interval must contain the position. | 129 // live range that owns it. The interval must contain the position. |
193 void SplitAt(LifetimePosition pos, Zone* zone); | 130 void SplitAt(LifetimePosition pos, Zone* zone); |
194 | 131 |
195 // If this interval intersects with other return smallest position | 132 // If this interval intersects with other return smallest position |
196 // that belongs to both of them. | 133 // that belongs to both of them. |
197 LifetimePosition Intersect(const UseInterval* other) const { | 134 LifetimePosition Intersect(const UseInterval* other) const { |
198 if (other->start().Value() < start_.Value()) return other->Intersect(this); | 135 if (other->start().Value() < start_.Value()) return other->Intersect(this); |
199 if (other->start().Value() < end_.Value()) return other->start(); | 136 if (other->start().Value() < end_.Value()) return other->start(); |
200 return LifetimePosition::Invalid(); | 137 return LifetimePosition::Invalid(); |
201 } | 138 } |
202 | 139 |
203 bool Contains(LifetimePosition point) const { | 140 bool Contains(LifetimePosition point) const { |
204 return start_.Value() <= point.Value() && point.Value() < end_.Value(); | 141 return start_.Value() <= point.Value() && point.Value() < end_.Value(); |
205 } | 142 } |
206 | 143 |
207 private: | |
208 void set_start(LifetimePosition start) { start_ = start; } | 144 void set_start(LifetimePosition start) { start_ = start; } |
209 void set_next(UseInterval* next) { next_ = next; } | 145 void set_next(UseInterval* next) { next_ = next; } |
210 | 146 |
211 LifetimePosition start_; | 147 LifetimePosition start_; |
212 LifetimePosition end_; | 148 LifetimePosition end_; |
213 UseInterval* next_; | 149 UseInterval* next_; |
214 | |
215 friend class LiveRange; // Assigns to start_. | |
216 }; | 150 }; |
217 | 151 |
218 // Representation of a use position. | 152 // Representation of a use position. |
219 class UsePosition: public ZoneObject { | 153 class UsePosition : public ZoneObject { |
220 public: | 154 public: |
221 UsePosition(LifetimePosition pos, LOperand* operand, LOperand* hint); | 155 UsePosition(LifetimePosition pos, InstructionOperand* operand, |
| 156 InstructionOperand* hint); |
222 | 157 |
223 LOperand* operand() const { return operand_; } | 158 InstructionOperand* operand() const { return operand_; } |
224 bool HasOperand() const { return operand_ != NULL; } | 159 bool HasOperand() const { return operand_ != NULL; } |
225 | 160 |
226 LOperand* hint() const { return hint_; } | 161 InstructionOperand* hint() const { return hint_; } |
227 bool HasHint() const; | 162 bool HasHint() const; |
228 bool RequiresRegister() const; | 163 bool RequiresRegister() const; |
229 bool RegisterIsBeneficial() const; | 164 bool RegisterIsBeneficial() const; |
230 | 165 |
231 LifetimePosition pos() const { return pos_; } | 166 LifetimePosition pos() const { return pos_; } |
232 UsePosition* next() const { return next_; } | 167 UsePosition* next() const { return next_; } |
233 | 168 |
234 private: | |
235 void set_next(UsePosition* next) { next_ = next; } | 169 void set_next(UsePosition* next) { next_ = next; } |
236 | 170 |
237 LOperand* const operand_; | 171 InstructionOperand* const operand_; |
238 LOperand* const hint_; | 172 InstructionOperand* const hint_; |
239 LifetimePosition const pos_; | 173 LifetimePosition const pos_; |
240 UsePosition* next_; | 174 UsePosition* next_; |
241 bool requires_reg_; | 175 bool requires_reg_; |
242 bool register_beneficial_; | 176 bool register_beneficial_; |
243 | |
244 friend class LiveRange; | |
245 }; | 177 }; |
246 | 178 |
247 // Representation of SSA values' live ranges as a collection of (continuous) | 179 // Representation of SSA values' live ranges as a collection of (continuous) |
248 // intervals over the instruction ordering. | 180 // intervals over the instruction ordering. |
249 class LiveRange: public ZoneObject { | 181 class LiveRange : public ZoneObject { |
250 public: | 182 public: |
251 static const int kInvalidAssignment = 0x7fffffff; | 183 static const int kInvalidAssignment = 0x7fffffff; |
252 | 184 |
253 LiveRange(int id, Zone* zone); | 185 LiveRange(int id, Zone* zone); |
254 | 186 |
255 UseInterval* first_interval() const { return first_interval_; } | 187 UseInterval* first_interval() const { return first_interval_; } |
256 UsePosition* first_pos() const { return first_pos_; } | 188 UsePosition* first_pos() const { return first_pos_; } |
257 LiveRange* parent() const { return parent_; } | 189 LiveRange* parent() const { return parent_; } |
258 LiveRange* TopLevel() { return (parent_ == NULL) ? this : parent_; } | 190 LiveRange* TopLevel() { return (parent_ == NULL) ? this : parent_; } |
259 LiveRange* next() const { return next_; } | 191 LiveRange* next() const { return next_; } |
260 bool IsChild() const { return parent() != NULL; } | 192 bool IsChild() const { return parent() != NULL; } |
261 int id() const { return id_; } | 193 int id() const { return id_; } |
262 bool IsFixed() const { return id_ < 0; } | 194 bool IsFixed() const { return id_ < 0; } |
263 bool IsEmpty() const { return first_interval() == NULL; } | 195 bool IsEmpty() const { return first_interval() == NULL; } |
264 LOperand* CreateAssignedOperand(Zone* zone); | 196 InstructionOperand* CreateAssignedOperand(Zone* zone); |
265 int assigned_register() const { return assigned_register_; } | 197 int assigned_register() const { return assigned_register_; } |
266 int spill_start_index() const { return spill_start_index_; } | 198 int spill_start_index() const { return spill_start_index_; } |
267 void set_assigned_register(int reg, Zone* zone); | 199 void set_assigned_register(int reg, Zone* zone); |
268 void MakeSpilled(Zone* zone); | 200 void MakeSpilled(Zone* zone); |
| 201 bool is_phi() const { return is_phi_; } |
| 202 void set_is_phi(bool is_phi) { is_phi_ = is_phi; } |
| 203 bool is_non_loop_phi() const { return is_non_loop_phi_; } |
| 204 void set_is_non_loop_phi(bool is_non_loop_phi) { |
| 205 is_non_loop_phi_ = is_non_loop_phi; |
| 206 } |
269 | 207 |
270 // Returns use position in this live range that follows both start | 208 // Returns use position in this live range that follows both start |
271 // and last processed use position. | 209 // and last processed use position. |
272 // Modifies internal state of live range! | 210 // Modifies internal state of live range! |
273 UsePosition* NextUsePosition(LifetimePosition start); | 211 UsePosition* NextUsePosition(LifetimePosition start); |
274 | 212 |
275 // Returns use position for which register is required in this live | 213 // Returns use position for which register is required in this live |
276 // range and which follows both start and last processed use position | 214 // range and which follows both start and last processed use position |
277 // Modifies internal state of live range! | 215 // Modifies internal state of live range! |
278 UsePosition* NextRegisterPosition(LifetimePosition start); | 216 UsePosition* NextRegisterPosition(LifetimePosition start); |
(...skipping 15 matching lines...) Expand all Loading... |
294 // All uses following the given position will be moved from this | 232 // All uses following the given position will be moved from this |
295 // live range to the result live range. | 233 // live range to the result live range. |
296 void SplitAt(LifetimePosition position, LiveRange* result, Zone* zone); | 234 void SplitAt(LifetimePosition position, LiveRange* result, Zone* zone); |
297 | 235 |
298 RegisterKind Kind() const { return kind_; } | 236 RegisterKind Kind() const { return kind_; } |
299 bool HasRegisterAssigned() const { | 237 bool HasRegisterAssigned() const { |
300 return assigned_register_ != kInvalidAssignment; | 238 return assigned_register_ != kInvalidAssignment; |
301 } | 239 } |
302 bool IsSpilled() const { return spilled_; } | 240 bool IsSpilled() const { return spilled_; } |
303 | 241 |
304 LOperand* current_hint_operand() const { | 242 InstructionOperand* current_hint_operand() const { |
305 ASSERT(current_hint_operand_ == FirstHint()); | 243 ASSERT(current_hint_operand_ == FirstHint()); |
306 return current_hint_operand_; | 244 return current_hint_operand_; |
307 } | 245 } |
308 LOperand* FirstHint() const { | 246 InstructionOperand* FirstHint() const { |
309 UsePosition* pos = first_pos_; | 247 UsePosition* pos = first_pos_; |
310 while (pos != NULL && !pos->HasHint()) pos = pos->next(); | 248 while (pos != NULL && !pos->HasHint()) pos = pos->next(); |
311 if (pos != NULL) return pos->hint(); | 249 if (pos != NULL) return pos->hint(); |
312 return NULL; | 250 return NULL; |
313 } | 251 } |
314 | 252 |
315 LifetimePosition Start() const { | 253 LifetimePosition Start() const { |
316 ASSERT(!IsEmpty()); | 254 ASSERT(!IsEmpty()); |
317 return first_interval()->start(); | 255 return first_interval()->start(); |
318 } | 256 } |
319 | 257 |
320 LifetimePosition End() const { | 258 LifetimePosition End() const { |
321 ASSERT(!IsEmpty()); | 259 ASSERT(!IsEmpty()); |
322 return last_interval_->end(); | 260 return last_interval_->end(); |
323 } | 261 } |
324 | 262 |
325 bool HasAllocatedSpillOperand() const; | 263 bool HasAllocatedSpillOperand() const; |
326 LOperand* GetSpillOperand() const { return spill_operand_; } | 264 InstructionOperand* GetSpillOperand() const { return spill_operand_; } |
327 void SetSpillOperand(LOperand* operand); | 265 void SetSpillOperand(InstructionOperand* operand); |
328 | 266 |
329 void SetSpillStartIndex(int start) { | 267 void SetSpillStartIndex(int start) { |
330 spill_start_index_ = Min(start, spill_start_index_); | 268 spill_start_index_ = Min(start, spill_start_index_); |
331 } | 269 } |
332 | 270 |
333 bool ShouldBeAllocatedBefore(const LiveRange* other) const; | 271 bool ShouldBeAllocatedBefore(const LiveRange* other) const; |
334 bool CanCover(LifetimePosition position) const; | 272 bool CanCover(LifetimePosition position) const; |
335 bool Covers(LifetimePosition position); | 273 bool Covers(LifetimePosition position); |
336 LifetimePosition FirstIntersection(LiveRange* other); | 274 LifetimePosition FirstIntersection(LiveRange* other); |
337 | 275 |
338 // Add a new interval or a new use position to this live range. | 276 // Add a new interval or a new use position to this live range. |
339 void EnsureInterval(LifetimePosition start, | 277 void EnsureInterval(LifetimePosition start, LifetimePosition end, Zone* zone); |
340 LifetimePosition end, | 278 void AddUseInterval(LifetimePosition start, LifetimePosition end, Zone* zone); |
341 Zone* zone); | 279 void AddUsePosition(LifetimePosition pos, InstructionOperand* operand, |
342 void AddUseInterval(LifetimePosition start, | 280 InstructionOperand* hint, Zone* zone); |
343 LifetimePosition end, | |
344 Zone* zone); | |
345 void AddUsePosition(LifetimePosition pos, | |
346 LOperand* operand, | |
347 LOperand* hint, | |
348 Zone* zone); | |
349 | 281 |
350 // Shorten the most recently added interval by setting a new start. | 282 // Shorten the most recently added interval by setting a new start. |
351 void ShortenTo(LifetimePosition start); | 283 void ShortenTo(LifetimePosition start); |
352 | 284 |
353 #ifdef DEBUG | 285 #ifdef DEBUG |
354 // True if target overlaps an existing interval. | 286 // True if target overlaps an existing interval. |
355 bool HasOverlap(UseInterval* target) const; | 287 bool HasOverlap(UseInterval* target) const; |
356 void Verify() const; | 288 void Verify() const; |
357 #endif | 289 #endif |
358 | 290 |
359 private: | 291 private: |
360 void ConvertOperands(Zone* zone); | 292 void ConvertOperands(Zone* zone); |
361 UseInterval* FirstSearchIntervalForPosition(LifetimePosition position) const; | 293 UseInterval* FirstSearchIntervalForPosition(LifetimePosition position) const; |
362 void AdvanceLastProcessedMarker(UseInterval* to_start_of, | 294 void AdvanceLastProcessedMarker(UseInterval* to_start_of, |
363 LifetimePosition but_not_past) const; | 295 LifetimePosition but_not_past) const; |
364 | 296 |
365 int id_; | 297 int id_; |
366 bool spilled_; | 298 bool spilled_; |
| 299 bool is_phi_; |
| 300 bool is_non_loop_phi_; |
367 RegisterKind kind_; | 301 RegisterKind kind_; |
368 int assigned_register_; | 302 int assigned_register_; |
369 UseInterval* last_interval_; | 303 UseInterval* last_interval_; |
370 UseInterval* first_interval_; | 304 UseInterval* first_interval_; |
371 UsePosition* first_pos_; | 305 UsePosition* first_pos_; |
372 LiveRange* parent_; | 306 LiveRange* parent_; |
373 LiveRange* next_; | 307 LiveRange* next_; |
374 // This is used as a cache, it doesn't affect correctness. | 308 // This is used as a cache, it doesn't affect correctness. |
375 mutable UseInterval* current_interval_; | 309 mutable UseInterval* current_interval_; |
376 UsePosition* last_processed_use_; | 310 UsePosition* last_processed_use_; |
377 // This is used as a cache, it's invalid outside of BuildLiveRanges. | 311 // This is used as a cache, it's invalid outside of BuildLiveRanges. |
378 LOperand* current_hint_operand_; | 312 InstructionOperand* current_hint_operand_; |
379 LOperand* spill_operand_; | 313 InstructionOperand* spill_operand_; |
380 int spill_start_index_; | 314 int spill_start_index_; |
381 | 315 |
382 friend class LAllocator; // Assigns to kind_. | 316 friend class RegisterAllocator; // Assigns to kind_. |
383 }; | 317 }; |
384 | 318 |
385 | 319 |
386 class LAllocator BASE_EMBEDDED { | 320 class RegisterAllocator BASE_EMBEDDED { |
387 public: | 321 public: |
388 LAllocator(int first_virtual_register, HGraph* graph); | 322 explicit RegisterAllocator(InstructionSequence* code); |
389 | 323 |
390 static void TraceAlloc(const char* msg, ...); | 324 static void TraceAlloc(const char* msg, ...); |
391 | 325 |
392 // Checks whether the value of a given virtual register is tagged. | 326 // Checks whether the value of a given virtual register is a reference. |
| 327 // TODO(titzer): rename this to IsReference. |
393 bool HasTaggedValue(int virtual_register) const; | 328 bool HasTaggedValue(int virtual_register) const; |
394 | 329 |
395 // Returns the register kind required by the given virtual register. | 330 // Returns the register kind required by the given virtual register. |
396 RegisterKind RequiredRegisterKind(int virtual_register) const; | 331 RegisterKind RequiredRegisterKind(int virtual_register) const; |
397 | 332 |
398 bool Allocate(LChunk* chunk); | 333 bool Allocate(); |
399 | 334 |
400 const ZoneList<LiveRange*>* live_ranges() const { return &live_ranges_; } | 335 const ZoneList<LiveRange*>* live_ranges() const { return &live_ranges_; } |
401 const Vector<LiveRange*>* fixed_live_ranges() const { | 336 const Vector<LiveRange*>* fixed_live_ranges() const { |
402 return &fixed_live_ranges_; | 337 return &fixed_live_ranges_; |
403 } | 338 } |
404 const Vector<LiveRange*>* fixed_double_live_ranges() const { | 339 const Vector<LiveRange*>* fixed_double_live_ranges() const { |
405 return &fixed_double_live_ranges_; | 340 return &fixed_double_live_ranges_; |
406 } | 341 } |
407 | 342 |
408 LPlatformChunk* chunk() const { return chunk_; } | 343 inline InstructionSequence* code() const { return code_; } |
409 HGraph* graph() const { return graph_; } | 344 |
410 Isolate* isolate() const { return graph_->isolate(); } | 345 // This zone is for datastructures only needed during register allocation. |
411 Zone* zone() { return &zone_; } | 346 inline Zone* zone() { return &zone_; } |
| 347 |
| 348 // This zone is for InstructionOperands and moves that live beyond register |
| 349 // allocation. |
| 350 inline Zone* code_zone() { return code()->zone(); } |
412 | 351 |
413 int GetVirtualRegister() { | 352 int GetVirtualRegister() { |
414 if (next_virtual_register_ >= LUnallocated::kMaxVirtualRegisters) { | 353 int vreg = code()->NextVirtualRegister(); |
| 354 if (vreg >= UnallocatedOperand::kMaxVirtualRegisters) { |
415 allocation_ok_ = false; | 355 allocation_ok_ = false; |
416 // Maintain the invariant that we return something below the maximum. | 356 // Maintain the invariant that we return something below the maximum. |
417 return 0; | 357 return 0; |
418 } | 358 } |
419 return next_virtual_register_++; | 359 return vreg; |
420 } | 360 } |
421 | 361 |
422 bool AllocationOk() { return allocation_ok_; } | 362 bool AllocationOk() { return allocation_ok_; } |
423 | 363 |
424 void MarkAsOsrEntry() { | |
425 // There can be only one. | |
426 ASSERT(!has_osr_entry_); | |
427 // Simply set a flag to find and process instruction later. | |
428 has_osr_entry_ = true; | |
429 } | |
430 | |
431 #ifdef DEBUG | 364 #ifdef DEBUG |
432 void Verify() const; | 365 void Verify() const; |
433 #endif | 366 #endif |
434 | 367 |
435 BitVector* assigned_registers() { | 368 BitVector* assigned_registers() { return assigned_registers_; } |
436 return assigned_registers_; | 369 BitVector* assigned_double_registers() { return assigned_double_registers_; } |
437 } | |
438 BitVector* assigned_double_registers() { | |
439 return assigned_double_registers_; | |
440 } | |
441 | 370 |
442 private: | 371 private: |
443 void MeetRegisterConstraints(); | 372 void MeetRegisterConstraints(); |
444 void ResolvePhis(); | 373 void ResolvePhis(); |
445 void BuildLiveRanges(); | 374 void BuildLiveRanges(); |
446 void AllocateGeneralRegisters(); | 375 void AllocateGeneralRegisters(); |
447 void AllocateDoubleRegisters(); | 376 void AllocateDoubleRegisters(); |
448 void ConnectRanges(); | 377 void ConnectRanges(); |
449 void ResolveControlFlow(); | 378 void ResolveControlFlow(); |
450 void PopulatePointerMaps(); | 379 void PopulatePointerMaps(); // TODO(titzer): rename to PopulateReferenceMaps. |
451 void AllocateRegisters(); | 380 void AllocateRegisters(); |
452 bool CanEagerlyResolveControlFlow(HBasicBlock* block) const; | 381 bool CanEagerlyResolveControlFlow(BasicBlock* block) const; |
453 inline bool SafePointsAreInOrder() const; | 382 inline bool SafePointsAreInOrder() const; |
454 | 383 |
455 // Liveness analysis support. | 384 // Liveness analysis support. |
456 void InitializeLivenessAnalysis(); | 385 void InitializeLivenessAnalysis(); |
457 BitVector* ComputeLiveOut(HBasicBlock* block); | 386 BitVector* ComputeLiveOut(BasicBlock* block); |
458 void AddInitialIntervals(HBasicBlock* block, BitVector* live_out); | 387 void AddInitialIntervals(BasicBlock* block, BitVector* live_out); |
459 void ProcessInstructions(HBasicBlock* block, BitVector* live); | 388 bool IsOutputRegisterOf(Instruction* instr, int index); |
460 void MeetRegisterConstraints(HBasicBlock* block); | 389 bool IsOutputDoubleRegisterOf(Instruction* instr, int index); |
461 void MeetConstraintsBetween(LInstruction* first, | 390 void ProcessInstructions(BasicBlock* block, BitVector* live); |
462 LInstruction* second, | 391 void MeetRegisterConstraints(BasicBlock* block); |
| 392 void MeetConstraintsBetween(Instruction* first, Instruction* second, |
463 int gap_index); | 393 int gap_index); |
464 void ResolvePhis(HBasicBlock* block); | 394 void ResolvePhis(BasicBlock* block); |
465 | 395 |
466 // Helper methods for building intervals. | 396 // Helper methods for building intervals. |
467 LOperand* AllocateFixed(LUnallocated* operand, int pos, bool is_tagged); | 397 InstructionOperand* AllocateFixed(UnallocatedOperand* operand, int pos, |
468 LiveRange* LiveRangeFor(LOperand* operand); | 398 bool is_tagged); |
469 void Define(LifetimePosition position, LOperand* operand, LOperand* hint); | 399 LiveRange* LiveRangeFor(InstructionOperand* operand); |
470 void Use(LifetimePosition block_start, | 400 void Define(LifetimePosition position, InstructionOperand* operand, |
471 LifetimePosition position, | 401 InstructionOperand* hint); |
472 LOperand* operand, | 402 void Use(LifetimePosition block_start, LifetimePosition position, |
473 LOperand* hint); | 403 InstructionOperand* operand, InstructionOperand* hint); |
474 void AddConstraintsGapMove(int index, LOperand* from, LOperand* to); | 404 void AddConstraintsGapMove(int index, InstructionOperand* from, |
| 405 InstructionOperand* to); |
475 | 406 |
476 // Helper methods for updating the life range lists. | 407 // Helper methods for updating the life range lists. |
477 void AddToActive(LiveRange* range); | 408 void AddToActive(LiveRange* range); |
478 void AddToInactive(LiveRange* range); | 409 void AddToInactive(LiveRange* range); |
479 void AddToUnhandledSorted(LiveRange* range); | 410 void AddToUnhandledSorted(LiveRange* range); |
480 void AddToUnhandledUnsorted(LiveRange* range); | 411 void AddToUnhandledUnsorted(LiveRange* range); |
481 void SortUnhandled(); | 412 void SortUnhandled(); |
482 bool UnhandledIsSorted(); | 413 bool UnhandledIsSorted(); |
483 void ActiveToHandled(LiveRange* range); | 414 void ActiveToHandled(LiveRange* range); |
484 void ActiveToInactive(LiveRange* range); | 415 void ActiveToInactive(LiveRange* range); |
485 void InactiveToHandled(LiveRange* range); | 416 void InactiveToHandled(LiveRange* range); |
486 void InactiveToActive(LiveRange* range); | 417 void InactiveToActive(LiveRange* range); |
487 void FreeSpillSlot(LiveRange* range); | 418 void FreeSpillSlot(LiveRange* range); |
488 LOperand* TryReuseSpillSlot(LiveRange* range); | 419 InstructionOperand* TryReuseSpillSlot(LiveRange* range); |
489 | 420 |
490 // Helper methods for allocating registers. | 421 // Helper methods for allocating registers. |
491 bool TryAllocateFreeReg(LiveRange* range); | 422 bool TryAllocateFreeReg(LiveRange* range); |
492 void AllocateBlockedReg(LiveRange* range); | 423 void AllocateBlockedReg(LiveRange* range); |
493 | 424 |
494 // Live range splitting helpers. | 425 // Live range splitting helpers. |
495 | 426 |
496 // Split the given range at the given position. | 427 // Split the given range at the given position. |
497 // If range starts at or after the given position then the | 428 // If range starts at or after the given position then the |
498 // original range is returned. | 429 // original range is returned. |
499 // Otherwise returns the live range that starts at pos and contains | 430 // Otherwise returns the live range that starts at pos and contains |
500 // all uses from the original range that follow pos. Uses at pos will | 431 // all uses from the original range that follow pos. Uses at pos will |
501 // still be owned by the original range after splitting. | 432 // still be owned by the original range after splitting. |
502 LiveRange* SplitRangeAt(LiveRange* range, LifetimePosition pos); | 433 LiveRange* SplitRangeAt(LiveRange* range, LifetimePosition pos); |
503 | 434 |
504 // Split the given range in a position from the interval [start, end]. | 435 // Split the given range in a position from the interval [start, end]. |
505 LiveRange* SplitBetween(LiveRange* range, | 436 LiveRange* SplitBetween(LiveRange* range, LifetimePosition start, |
506 LifetimePosition start, | |
507 LifetimePosition end); | 437 LifetimePosition end); |
508 | 438 |
509 // Find a lifetime position in the interval [start, end] which | 439 // Find a lifetime position in the interval [start, end] which |
510 // is optimal for splitting: it is either header of the outermost | 440 // is optimal for splitting: it is either header of the outermost |
511 // loop covered by this interval or the latest possible position. | 441 // loop covered by this interval or the latest possible position. |
512 LifetimePosition FindOptimalSplitPos(LifetimePosition start, | 442 LifetimePosition FindOptimalSplitPos(LifetimePosition start, |
513 LifetimePosition end); | 443 LifetimePosition end); |
514 | 444 |
515 // Spill the given life range after position pos. | 445 // Spill the given life range after position pos. |
516 void SpillAfter(LiveRange* range, LifetimePosition pos); | 446 void SpillAfter(LiveRange* range, LifetimePosition pos); |
517 | 447 |
518 // Spill the given life range after position [start] and up to position [end]. | 448 // Spill the given life range after position [start] and up to position [end]. |
519 void SpillBetween(LiveRange* range, | 449 void SpillBetween(LiveRange* range, LifetimePosition start, |
520 LifetimePosition start, | |
521 LifetimePosition end); | 450 LifetimePosition end); |
522 | 451 |
523 // Spill the given life range after position [start] and up to position [end]. | 452 // Spill the given life range after position [start] and up to position [end]. |
524 // Range is guaranteed to be spilled at least until position [until]. | 453 // Range is guaranteed to be spilled at least until position [until]. |
525 void SpillBetweenUntil(LiveRange* range, | 454 void SpillBetweenUntil(LiveRange* range, LifetimePosition start, |
526 LifetimePosition start, | 455 LifetimePosition until, LifetimePosition end); |
527 LifetimePosition until, | |
528 LifetimePosition end); | |
529 | 456 |
530 void SplitAndSpillIntersecting(LiveRange* range); | 457 void SplitAndSpillIntersecting(LiveRange* range); |
531 | 458 |
532 // If we are trying to spill a range inside the loop try to | 459 // If we are trying to spill a range inside the loop try to |
533 // hoist spill position out to the point just before the loop. | 460 // hoist spill position out to the point just before the loop. |
534 LifetimePosition FindOptimalSpillingPos(LiveRange* range, | 461 LifetimePosition FindOptimalSpillingPos(LiveRange* range, |
535 LifetimePosition pos); | 462 LifetimePosition pos); |
536 | 463 |
537 void Spill(LiveRange* range); | 464 void Spill(LiveRange* range); |
538 bool IsBlockBoundary(LifetimePosition pos); | 465 bool IsBlockBoundary(LifetimePosition pos); |
539 | 466 |
540 // Helper methods for resolving control flow. | 467 // Helper methods for resolving control flow. |
541 void ResolveControlFlow(LiveRange* range, | 468 void ResolveControlFlow(LiveRange* range, BasicBlock* block, |
542 HBasicBlock* block, | 469 BasicBlock* pred); |
543 HBasicBlock* pred); | |
544 | 470 |
545 inline void SetLiveRangeAssignedRegister(LiveRange* range, int reg); | 471 inline void SetLiveRangeAssignedRegister(LiveRange* range, int reg); |
546 | 472 |
547 // Return parallel move that should be used to connect ranges split at the | 473 // Return parallel move that should be used to connect ranges split at the |
548 // given position. | 474 // given position. |
549 LParallelMove* GetConnectingParallelMove(LifetimePosition pos); | 475 ParallelMove* GetConnectingParallelMove(LifetimePosition pos); |
550 | 476 |
551 // Return the block which contains give lifetime position. | 477 // Return the block which contains give lifetime position. |
552 HBasicBlock* GetBlock(LifetimePosition pos); | 478 BasicBlock* GetBlock(LifetimePosition pos); |
553 | 479 |
554 // Helper methods for the fixed registers. | 480 // Helper methods for the fixed registers. |
555 int RegisterCount() const; | 481 int RegisterCount() const; |
556 static int FixedLiveRangeID(int index) { return -index - 1; } | 482 static int FixedLiveRangeID(int index) { return -index - 1; } |
557 static int FixedDoubleLiveRangeID(int index); | 483 static int FixedDoubleLiveRangeID(int index); |
558 LiveRange* FixedLiveRangeFor(int index); | 484 LiveRange* FixedLiveRangeFor(int index); |
559 LiveRange* FixedDoubleLiveRangeFor(int index); | 485 LiveRange* FixedDoubleLiveRangeFor(int index); |
560 LiveRange* LiveRangeFor(int index); | 486 LiveRange* LiveRangeFor(int index); |
561 HPhi* LookupPhi(LOperand* operand) const; | 487 GapInstruction* GetLastGap(BasicBlock* block); |
562 LGap* GetLastGap(HBasicBlock* block); | |
563 | 488 |
564 const char* RegisterName(int allocation_index); | 489 const char* RegisterName(int allocation_index); |
565 | 490 |
566 inline bool IsGapAt(int index); | 491 inline Instruction* InstructionAt(int index) { |
567 | 492 return code()->InstructionAt(index); |
568 inline LInstruction* InstructionAt(int index); | 493 } |
569 | |
570 inline LGap* GapAt(int index); | |
571 | 494 |
572 Zone zone_; | 495 Zone zone_; |
573 | 496 InstructionSequence* code_; |
574 LPlatformChunk* chunk_; | |
575 | 497 |
576 // During liveness analysis keep a mapping from block id to live_in sets | 498 // During liveness analysis keep a mapping from block id to live_in sets |
577 // for blocks already analyzed. | 499 // for blocks already analyzed. |
578 ZoneList<BitVector*> live_in_sets_; | 500 ZoneList<BitVector*> live_in_sets_; |
579 | 501 |
580 // Liveness analysis results. | 502 // Liveness analysis results. |
581 ZoneList<LiveRange*> live_ranges_; | 503 ZoneList<LiveRange*> live_ranges_; |
582 | 504 |
583 // Lists of live ranges | 505 // Lists of live ranges |
584 EmbeddedVector<LiveRange*, Register::kMaxNumAllocatableRegisters> | 506 EmbeddedVector<LiveRange*, Register::kMaxNumAllocatableRegisters> |
585 fixed_live_ranges_; | 507 fixed_live_ranges_; |
586 EmbeddedVector<LiveRange*, DoubleRegister::kMaxNumAllocatableRegisters> | 508 EmbeddedVector<LiveRange*, DoubleRegister::kMaxNumAllocatableRegisters> |
587 fixed_double_live_ranges_; | 509 fixed_double_live_ranges_; |
588 ZoneList<LiveRange*> unhandled_live_ranges_; | 510 ZoneList<LiveRange*> unhandled_live_ranges_; |
589 ZoneList<LiveRange*> active_live_ranges_; | 511 ZoneList<LiveRange*> active_live_ranges_; |
590 ZoneList<LiveRange*> inactive_live_ranges_; | 512 ZoneList<LiveRange*> inactive_live_ranges_; |
591 ZoneList<LiveRange*> reusable_slots_; | 513 ZoneList<LiveRange*> reusable_slots_; |
592 | 514 |
593 // Next virtual register number to be assigned to temporaries. | |
594 int next_virtual_register_; | |
595 int first_artificial_register_; | |
596 GrowableBitVector double_artificial_registers_; | |
597 | |
598 RegisterKind mode_; | 515 RegisterKind mode_; |
599 int num_registers_; | 516 int num_registers_; |
600 | 517 |
601 BitVector* assigned_registers_; | 518 BitVector* assigned_registers_; |
602 BitVector* assigned_double_registers_; | 519 BitVector* assigned_double_registers_; |
603 | 520 |
604 HGraph* graph_; | |
605 | |
606 bool has_osr_entry_; | |
607 | |
608 // Indicates success or failure during register allocation. | 521 // Indicates success or failure during register allocation. |
609 bool allocation_ok_; | 522 bool allocation_ok_; |
610 | 523 |
611 #ifdef DEBUG | 524 #ifdef DEBUG |
612 LifetimePosition allocation_finger_; | 525 LifetimePosition allocation_finger_; |
613 #endif | 526 #endif |
614 | 527 |
615 DISALLOW_COPY_AND_ASSIGN(LAllocator); | 528 DISALLOW_COPY_AND_ASSIGN(RegisterAllocator); |
616 }; | 529 }; |
617 | 530 |
618 | 531 |
619 class LAllocatorPhase : public CompilationPhase { | 532 class RegisterAllocatorPhase : public CompilationPhase { |
620 public: | 533 public: |
621 LAllocatorPhase(const char* name, LAllocator* allocator); | 534 RegisterAllocatorPhase(const char* name, RegisterAllocator* allocator); |
622 ~LAllocatorPhase(); | 535 ~RegisterAllocatorPhase(); |
623 | 536 |
624 private: | 537 private: |
625 LAllocator* allocator_; | 538 RegisterAllocator* allocator_; |
626 unsigned allocator_zone_start_allocation_size_; | 539 unsigned allocator_zone_start_allocation_size_; |
627 | 540 |
628 DISALLOW_COPY_AND_ASSIGN(LAllocatorPhase); | 541 DISALLOW_COPY_AND_ASSIGN(RegisterAllocatorPhase); |
629 }; | 542 }; |
| 543 } |
| 544 } |
| 545 } // namespace v8::internal::compiler |
630 | 546 |
631 | 547 #endif // V8_REGISTER_ALLOCATOR_H_ |
632 } } // namespace v8::internal | |
633 | |
634 #endif // V8_LITHIUM_ALLOCATOR_H_ | |
OLD | NEW |