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