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