michael@0: /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
michael@0:  * vim: set ts=8 sts=4 et sw=4 tw=99:
michael@0:  * This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: #ifndef jit_LinearScan_h
michael@0: #define jit_LinearScan_h
michael@0: 
michael@0: #include "jit/LiveRangeAllocator.h"
michael@0: #include "js/Vector.h"
michael@0: 
michael@0: namespace js {
michael@0: namespace jit {
michael@0: 
michael@0: class LinearScanVirtualRegister : public VirtualRegister
michael@0: {
michael@0:   private:
michael@0:     LAllocation *canonicalSpill_;
michael@0:     CodePosition spillPosition_ ;
michael@0: 
michael@0:     bool spillAtDefinition_ : 1;
michael@0: 
michael@0:     // This bit is used to determine whether both halves of a nunbox have been
michael@0:     // processed by freeAllocation().
michael@0:     bool finished_ : 1;
michael@0: 
michael@0:   public:
michael@0:     LinearScanVirtualRegister(TempAllocator &alloc)
michael@0:       : VirtualRegister(alloc)
michael@0:     {}
michael@0:     void setCanonicalSpill(LAllocation *alloc) {
michael@0:         canonicalSpill_ = alloc;
michael@0:     }
michael@0:     LAllocation *canonicalSpill() const {
michael@0:         return canonicalSpill_;
michael@0:     }
michael@0:     unsigned canonicalSpillSlot() const {
michael@0:         return canonicalSpill_->toStackSlot()->slot();
michael@0:     }
michael@0:     void setFinished() {
michael@0:         finished_ = true;
michael@0:     }
michael@0:     bool finished() const {
michael@0:         return finished_;
michael@0:     }
michael@0:     void setSpillAtDefinition(CodePosition pos) {
michael@0:         spillAtDefinition_ = true;
michael@0:         setSpillPosition(pos);
michael@0:     }
michael@0:     bool mustSpillAtDefinition() const {
michael@0:         return spillAtDefinition_;
michael@0:     }
michael@0:     CodePosition spillPosition() const {
michael@0:         return spillPosition_;
michael@0:     }
michael@0:     void setSpillPosition(CodePosition pos) {
michael@0:         spillPosition_ = pos;
michael@0:     }
michael@0: };
michael@0: 
michael@0: class LinearScanAllocator
michael@0:   : private LiveRangeAllocator<LinearScanVirtualRegister, /* forLSRA = */ true>
michael@0: {
michael@0:     friend class C1Spewer;
michael@0:     friend class JSONSpewer;
michael@0: 
michael@0:     // Work set of LiveIntervals, sorted by start() and then by priority,
michael@0:     // non-monotonically descending from tail to head.
michael@0:     class UnhandledQueue : public InlineList<LiveInterval>
michael@0:     {
michael@0:       public:
michael@0:         void enqueueForward(LiveInterval *after, LiveInterval *interval);
michael@0:         void enqueueBackward(LiveInterval *interval);
michael@0: 
michael@0:         void assertSorted();
michael@0: 
michael@0:         LiveInterval *dequeue();
michael@0:     };
michael@0: 
michael@0:     typedef Vector<LiveInterval *, 0, SystemAllocPolicy> SlotList;
michael@0:     SlotList finishedSlots_;
michael@0:     SlotList finishedDoubleSlots_;
michael@0: #ifdef JS_NUNBOX32
michael@0:     SlotList finishedNunboxSlots_;
michael@0: #endif
michael@0: 
michael@0:     // Run-time state
michael@0:     UnhandledQueue unhandled;
michael@0:     InlineList<LiveInterval> active;
michael@0:     InlineList<LiveInterval> inactive;
michael@0:     InlineList<LiveInterval> fixed;
michael@0:     InlineList<LiveInterval> handled;
michael@0:     LiveInterval *current;
michael@0: 
michael@0:     bool allocateRegisters();
michael@0:     bool resolveControlFlow();
michael@0:     bool reifyAllocations();
michael@0:     bool populateSafepoints();
michael@0: 
michael@0:     // Optimization for the UnsortedQueue.
michael@0:     void enqueueVirtualRegisterIntervals();
michael@0: 
michael@0:     uint32_t allocateSlotFor(const LiveInterval *interval);
michael@0:     bool splitInterval(LiveInterval *interval, CodePosition pos);
michael@0:     bool splitBlockingIntervals(LAllocation allocation);
michael@0:     bool assign(LAllocation allocation);
michael@0:     bool spill();
michael@0:     void freeAllocation(LiveInterval *interval, LAllocation *alloc);
michael@0:     void finishInterval(LiveInterval *interval);
michael@0:     AnyRegister::Code findBestFreeRegister(CodePosition *freeUntil);
michael@0:     AnyRegister::Code findBestBlockedRegister(CodePosition *nextUsed);
michael@0:     bool canCoexist(LiveInterval *a, LiveInterval *b);
michael@0:     bool moveInputAlloc(CodePosition pos, LAllocation *from, LAllocation *to, LDefinition::Type type);
michael@0:     void setIntervalRequirement(LiveInterval *interval);
michael@0:     bool isSpilledAt(LiveInterval *interval, CodePosition pos);
michael@0: 
michael@0: #ifdef DEBUG
michael@0:     void validateIntervals();
michael@0:     void validateAllocations();
michael@0: #else
michael@0:     inline void validateIntervals() { }
michael@0:     inline void validateAllocations() { }
michael@0: #endif
michael@0: 
michael@0:   public:
michael@0:     LinearScanAllocator(MIRGenerator *mir, LIRGenerator *lir, LIRGraph &graph)
michael@0:       : LiveRangeAllocator<LinearScanVirtualRegister, /* forLSRA = */ true>(mir, lir, graph)
michael@0:     {
michael@0:     }
michael@0: 
michael@0:     bool go();
michael@0: };
michael@0: 
michael@0: } // namespace jit
michael@0: } // namespace js
michael@0: 
michael@0: #endif /* jit_LinearScan_h */