OLD | NEW |
1 // Copyright 2014 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_REGISTER_ALLOCATOR_H_ | 5 #ifndef V8_REGISTER_ALLOCATOR_H_ |
6 #define V8_REGISTER_ALLOCATOR_H_ | 6 #define V8_REGISTER_ALLOCATOR_H_ |
7 | 7 |
8 #include "src/compiler/instruction.h" | 8 #include "src/compiler/instruction.h" |
9 #include "src/zone-containers.h" | 9 #include "src/zone-containers.h" |
10 | 10 |
(...skipping 179 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
190 } | 190 } |
191 LiveRange* next() const { return next_; } | 191 LiveRange* next() const { return next_; } |
192 bool IsChild() const { return parent() != nullptr; } | 192 bool IsChild() const { return parent() != nullptr; } |
193 int id() const { return id_; } | 193 int id() const { return id_; } |
194 bool IsFixed() const { return id_ < 0; } | 194 bool IsFixed() const { return id_ < 0; } |
195 bool IsEmpty() const { return first_interval() == nullptr; } | 195 bool IsEmpty() const { return first_interval() == nullptr; } |
196 InstructionOperand* CreateAssignedOperand(Zone* zone) const; | 196 InstructionOperand* CreateAssignedOperand(Zone* zone) const; |
197 int assigned_register() const { return assigned_register_; } | 197 int assigned_register() const { return assigned_register_; } |
198 int spill_start_index() const { return spill_start_index_; } | 198 int spill_start_index() const { return spill_start_index_; } |
199 void set_assigned_register(int reg, Zone* zone); | 199 void set_assigned_register(int reg, Zone* zone); |
200 void MakeSpilled(); | 200 void MakeSpilled(Zone* zone); |
201 bool is_phi() const { return is_phi_; } | 201 bool is_phi() const { return is_phi_; } |
202 void set_is_phi(bool is_phi) { is_phi_ = 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_; } | 203 bool is_non_loop_phi() const { return is_non_loop_phi_; } |
204 void set_is_non_loop_phi(bool 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; | 205 is_non_loop_phi_ = is_non_loop_phi; |
206 } | 206 } |
207 | 207 |
208 // Returns use position in this live range that follows both start | 208 // Returns use position in this live range that follows both start |
209 // and last processed use position. | 209 // and last processed use position. |
210 // Modifies internal state of live range! | 210 // Modifies internal state of live range! |
(...skipping 42 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
253 LifetimePosition Start() const { | 253 LifetimePosition Start() const { |
254 DCHECK(!IsEmpty()); | 254 DCHECK(!IsEmpty()); |
255 return first_interval()->start(); | 255 return first_interval()->start(); |
256 } | 256 } |
257 | 257 |
258 LifetimePosition End() const { | 258 LifetimePosition End() const { |
259 DCHECK(!IsEmpty()); | 259 DCHECK(!IsEmpty()); |
260 return last_interval_->end(); | 260 return last_interval_->end(); |
261 } | 261 } |
262 | 262 |
263 enum class SpillType { kNoSpillType, kSpillOperand, kSpillRange }; | 263 bool HasAllocatedSpillOperand() const; |
264 SpillType spill_type() const { return spill_type_; } | 264 InstructionOperand* GetSpillOperand() const { return spill_operand_; } |
265 InstructionOperand* GetSpillOperand() const { | 265 void SetSpillOperand(InstructionOperand* operand); |
266 return spill_type_ == SpillType::kSpillOperand ? spill_operand_ : nullptr; | |
267 } | |
268 SpillRange* GetSpillRange() const { | |
269 return spill_type_ == SpillType::kSpillRange ? spill_range_ : nullptr; | |
270 } | |
271 bool HasNoSpillType() const { return spill_type_ == SpillType::kNoSpillType; } | |
272 bool HasSpillOperand() const { | |
273 return spill_type_ == SpillType::kSpillOperand; | |
274 } | |
275 bool HasSpillRange() const { return spill_type_ == SpillType::kSpillRange; } | |
276 | 266 |
277 void SpillAtDefinition(Zone* zone, int gap_index, | 267 void SetSpillRange(SpillRange* spill_range) { spill_range_ = spill_range; } |
278 InstructionOperand* operand); | 268 SpillRange* GetSpillRange() const { return spill_range_; } |
279 void SetSpillOperand(InstructionOperand* operand); | |
280 void SetSpillRange(SpillRange* spill_range); | |
281 void CommitSpillOperand(InstructionOperand* operand); | 269 void CommitSpillOperand(InstructionOperand* operand); |
282 void CommitSpillsAtDefinition(InstructionSequence* sequence, | |
283 InstructionOperand* operand); | |
284 | 270 |
285 void SetSpillStartIndex(int start) { | 271 void SetSpillStartIndex(int start) { |
286 spill_start_index_ = Min(start, spill_start_index_); | 272 spill_start_index_ = Min(start, spill_start_index_); |
287 } | 273 } |
288 | 274 |
289 bool ShouldBeAllocatedBefore(const LiveRange* other) const; | 275 bool ShouldBeAllocatedBefore(const LiveRange* other) const; |
290 bool CanCover(LifetimePosition position) const; | 276 bool CanCover(LifetimePosition position) const; |
291 bool Covers(LifetimePosition position); | 277 bool Covers(LifetimePosition position); |
292 LifetimePosition FirstIntersection(LiveRange* other); | 278 LifetimePosition FirstIntersection(LiveRange* other); |
293 | 279 |
294 // Add a new interval or a new use position to this live range. | 280 // Add a new interval or a new use position to this live range. |
295 void EnsureInterval(LifetimePosition start, LifetimePosition end, Zone* zone); | 281 void EnsureInterval(LifetimePosition start, LifetimePosition end, Zone* zone); |
296 void AddUseInterval(LifetimePosition start, LifetimePosition end, Zone* zone); | 282 void AddUseInterval(LifetimePosition start, LifetimePosition end, Zone* zone); |
297 void AddUsePosition(LifetimePosition pos, InstructionOperand* operand, | 283 void AddUsePosition(LifetimePosition pos, InstructionOperand* operand, |
298 InstructionOperand* hint, Zone* zone); | 284 InstructionOperand* hint, Zone* zone); |
299 | 285 |
300 // Shorten the most recently added interval by setting a new start. | 286 // Shorten the most recently added interval by setting a new start. |
301 void ShortenTo(LifetimePosition start); | 287 void ShortenTo(LifetimePosition start); |
302 | 288 |
303 #ifdef DEBUG | 289 #ifdef DEBUG |
304 // True if target overlaps an existing interval. | 290 // True if target overlaps an existing interval. |
305 bool HasOverlap(UseInterval* target) const; | 291 bool HasOverlap(UseInterval* target) const; |
306 void Verify() const; | 292 void Verify() const; |
307 #endif | 293 #endif |
308 | 294 |
309 private: | 295 private: |
310 struct SpillAtDefinitionList; | 296 void ConvertOperands(Zone* zone); |
311 | |
312 void ConvertUsesToOperand(InstructionOperand* op); | 297 void ConvertUsesToOperand(InstructionOperand* op); |
313 UseInterval* FirstSearchIntervalForPosition(LifetimePosition position) const; | 298 UseInterval* FirstSearchIntervalForPosition(LifetimePosition position) const; |
314 void AdvanceLastProcessedMarker(UseInterval* to_start_of, | 299 void AdvanceLastProcessedMarker(UseInterval* to_start_of, |
315 LifetimePosition but_not_past) const; | 300 LifetimePosition but_not_past) const; |
316 | 301 |
317 // TODO(dcarney): pack this structure better. | |
318 int id_; | 302 int id_; |
319 bool spilled_; | 303 bool spilled_; |
320 bool is_phi_; | 304 bool is_phi_; |
321 bool is_non_loop_phi_; | 305 bool is_non_loop_phi_; |
322 RegisterKind kind_; | 306 RegisterKind kind_; |
323 int assigned_register_; | 307 int assigned_register_; |
324 UseInterval* last_interval_; | 308 UseInterval* last_interval_; |
325 UseInterval* first_interval_; | 309 UseInterval* first_interval_; |
326 UsePosition* first_pos_; | 310 UsePosition* first_pos_; |
327 LiveRange* parent_; | 311 LiveRange* parent_; |
328 LiveRange* next_; | 312 LiveRange* next_; |
329 // This is used as a cache, it doesn't affect correctness. | 313 // This is used as a cache, it doesn't affect correctness. |
330 mutable UseInterval* current_interval_; | 314 mutable UseInterval* current_interval_; |
331 UsePosition* last_processed_use_; | 315 UsePosition* last_processed_use_; |
332 // This is used as a cache, it's invalid outside of BuildLiveRanges. | 316 // This is used as a cache, it's invalid outside of BuildLiveRanges. |
333 InstructionOperand* current_hint_operand_; | 317 InstructionOperand* current_hint_operand_; |
| 318 InstructionOperand* spill_operand_; |
334 int spill_start_index_; | 319 int spill_start_index_; |
335 SpillType spill_type_; | 320 SpillRange* spill_range_; |
336 union { | |
337 InstructionOperand* spill_operand_; | |
338 SpillRange* spill_range_; | |
339 }; | |
340 SpillAtDefinitionList* spills_at_definition_; | |
341 | 321 |
342 friend class RegisterAllocator; // Assigns to kind_. | 322 friend class RegisterAllocator; // Assigns to kind_. |
343 | 323 |
344 DISALLOW_COPY_AND_ASSIGN(LiveRange); | 324 DISALLOW_COPY_AND_ASSIGN(LiveRange); |
345 }; | 325 }; |
346 | 326 |
347 | 327 |
348 class SpillRange FINAL : public ZoneObject { | 328 class SpillRange FINAL : public ZoneObject { |
349 public: | 329 public: |
350 SpillRange(LiveRange* range, Zone* zone); | 330 SpillRange(LiveRange* range, Zone* zone); |
(...skipping 50 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
401 void BuildLiveRanges(); | 381 void BuildLiveRanges(); |
402 bool ExistsUseWithoutDefinition(); | 382 bool ExistsUseWithoutDefinition(); |
403 | 383 |
404 // Phase 4: compute register assignments. | 384 // Phase 4: compute register assignments. |
405 void AllocateGeneralRegisters(); | 385 void AllocateGeneralRegisters(); |
406 void AllocateDoubleRegisters(); | 386 void AllocateDoubleRegisters(); |
407 | 387 |
408 // Phase 5: reassign spill splots for maximal reuse. | 388 // Phase 5: reassign spill splots for maximal reuse. |
409 void ReuseSpillSlots(); | 389 void ReuseSpillSlots(); |
410 | 390 |
411 // Phase 6: commit assignment. | 391 // Phase 6: compute values for pointer maps. |
412 void CommitAssignment(); | |
413 | |
414 // Phase 7: compute values for pointer maps. | |
415 void PopulatePointerMaps(); // TODO(titzer): rename to PopulateReferenceMaps. | 392 void PopulatePointerMaps(); // TODO(titzer): rename to PopulateReferenceMaps. |
416 | 393 |
417 // Phase 8: reconnect split ranges with moves. | 394 // Phase 7: reconnect split ranges with moves. |
418 void ConnectRanges(); | 395 void ConnectRanges(); |
419 | 396 |
420 // Phase 9: insert moves to connect ranges across basic blocks. | 397 // Phase 8: insert moves to connect ranges across basic blocks. |
421 void ResolveControlFlow(); | 398 void ResolveControlFlow(); |
422 | 399 |
423 private: | 400 private: |
424 int GetVirtualRegister() { | 401 int GetVirtualRegister() { |
425 int vreg = code()->NextVirtualRegister(); | 402 int vreg = code()->NextVirtualRegister(); |
426 if (vreg >= UnallocatedOperand::kMaxVirtualRegisters) { | 403 if (vreg >= UnallocatedOperand::kMaxVirtualRegisters) { |
427 allocation_ok_ = false; | 404 allocation_ok_ = false; |
428 // Maintain the invariant that we return something below the maximum. | 405 // Maintain the invariant that we return something below the maximum. |
429 return 0; | 406 return 0; |
430 } | 407 } |
(...skipping 202 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
633 #endif | 610 #endif |
634 | 611 |
635 DISALLOW_COPY_AND_ASSIGN(RegisterAllocator); | 612 DISALLOW_COPY_AND_ASSIGN(RegisterAllocator); |
636 }; | 613 }; |
637 | 614 |
638 } // namespace compiler | 615 } // namespace compiler |
639 } // namespace internal | 616 } // namespace internal |
640 } // namespace v8 | 617 } // namespace v8 |
641 | 618 |
642 #endif // V8_REGISTER_ALLOCATOR_H_ | 619 #endif // V8_REGISTER_ALLOCATOR_H_ |
OLD | NEW |