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_BacktrackingAllocator_h
michael@0: #define jit_BacktrackingAllocator_h
michael@0: 
michael@0: #include "mozilla/Array.h"
michael@0: 
michael@0: #include "ds/PriorityQueue.h"
michael@0: #include "ds/SplayTree.h"
michael@0: #include "jit/LiveRangeAllocator.h"
michael@0: 
michael@0: // Backtracking priority queue based register allocator based on that described
michael@0: // in the following blog post:
michael@0: //
michael@0: // http://blog.llvm.org/2011/09/greedy-register-allocation-in-llvm-30.html
michael@0: 
michael@0: namespace js {
michael@0: namespace jit {
michael@0: 
michael@0: // Information about a group of registers. Registers may be grouped together
michael@0: // when (a) all of their lifetimes are disjoint, (b) they are of the same type
michael@0: // (double / non-double) and (c) it is desirable that they have the same
michael@0: // allocation.
michael@0: struct VirtualRegisterGroup : public TempObject
michael@0: {
michael@0:     // All virtual registers in the group.
michael@0:     Vector<uint32_t, 2, IonAllocPolicy> registers;
michael@0: 
michael@0:     // Desired physical register to use for registers in the group.
michael@0:     LAllocation allocation;
michael@0: 
michael@0:     // Spill location to be shared by registers in the group.
michael@0:     LAllocation spill;
michael@0: 
michael@0:     explicit VirtualRegisterGroup(TempAllocator &alloc)
michael@0:       : registers(alloc), allocation(LUse(0, LUse::ANY)), spill(LUse(0, LUse::ANY))
michael@0:     {}
michael@0: 
michael@0:     uint32_t canonicalReg() {
michael@0:         uint32_t minimum = registers[0];
michael@0:         for (size_t i = 1; i < registers.length(); i++)
michael@0:             minimum = Min(minimum, registers[i]);
michael@0:         return minimum;
michael@0:     }
michael@0: };
michael@0: 
michael@0: class BacktrackingVirtualRegister : public VirtualRegister
michael@0: {
michael@0:     // If this register's definition is MUST_REUSE_INPUT, whether a copy must
michael@0:     // be introduced before the definition that relaxes the policy.
michael@0:     bool mustCopyInput_;
michael@0: 
michael@0:     // Spill location to use for this register.
michael@0:     LAllocation canonicalSpill_;
michael@0: 
michael@0:     // Code position above which the canonical spill cannot be used; such
michael@0:     // intervals may overlap other registers in the same group.
michael@0:     CodePosition canonicalSpillExclude_;
michael@0: 
michael@0:     // If this register is associated with a group of other registers,
michael@0:     // information about the group. This structure is shared between all
michael@0:     // registers in the group.
michael@0:     VirtualRegisterGroup *group_;
michael@0: 
michael@0:   public:
michael@0:     explicit BacktrackingVirtualRegister(TempAllocator &alloc)
michael@0:       : VirtualRegister(alloc)
michael@0:     {}
michael@0:     void setMustCopyInput() {
michael@0:         mustCopyInput_ = true;
michael@0:     }
michael@0:     bool mustCopyInput() {
michael@0:         return mustCopyInput_;
michael@0:     }
michael@0: 
michael@0:     void setCanonicalSpill(LAllocation alloc) {
michael@0:         JS_ASSERT(!alloc.isUse());
michael@0:         canonicalSpill_ = alloc;
michael@0:     }
michael@0:     const LAllocation *canonicalSpill() const {
michael@0:         return canonicalSpill_.isUse() ? nullptr : &canonicalSpill_;
michael@0:     }
michael@0: 
michael@0:     void setCanonicalSpillExclude(CodePosition pos) {
michael@0:         canonicalSpillExclude_ = pos;
michael@0:     }
michael@0:     bool hasCanonicalSpillExclude() const {
michael@0:         return canonicalSpillExclude_.pos() != 0;
michael@0:     }
michael@0:     CodePosition canonicalSpillExclude() const {
michael@0:         JS_ASSERT(hasCanonicalSpillExclude());
michael@0:         return canonicalSpillExclude_;
michael@0:     }
michael@0: 
michael@0:     void setGroup(VirtualRegisterGroup *group) {
michael@0:         group_ = group;
michael@0:     }
michael@0:     VirtualRegisterGroup *group() {
michael@0:         return group_;
michael@0:     }
michael@0: };
michael@0: 
michael@0: // A sequence of code positions, for tellings BacktrackingAllocator::splitAt
michael@0: // where to split.
michael@0: typedef js::Vector<CodePosition, 4, SystemAllocPolicy> SplitPositionVector;
michael@0: 
michael@0: class BacktrackingAllocator
michael@0:   : private LiveRangeAllocator<BacktrackingVirtualRegister, /* forLSRA = */ false>
michael@0: {
michael@0:     // Priority queue element: either an interval or group of intervals and the
michael@0:     // associated priority.
michael@0:     struct QueueItem
michael@0:     {
michael@0:         LiveInterval *interval;
michael@0:         VirtualRegisterGroup *group;
michael@0: 
michael@0:         QueueItem(LiveInterval *interval, size_t priority)
michael@0:           : interval(interval), group(nullptr), priority_(priority)
michael@0:         {}
michael@0: 
michael@0:         QueueItem(VirtualRegisterGroup *group, size_t priority)
michael@0:           : interval(nullptr), group(group), priority_(priority)
michael@0:         {}
michael@0: 
michael@0:         static size_t priority(const QueueItem &v) {
michael@0:             return v.priority_;
michael@0:         }
michael@0: 
michael@0:       private:
michael@0:         size_t priority_;
michael@0:     };
michael@0: 
michael@0:     PriorityQueue<QueueItem, QueueItem, 0, SystemAllocPolicy> allocationQueue;
michael@0: 
michael@0:     // A subrange over which a physical register is allocated.
michael@0:     struct AllocatedRange {
michael@0:         LiveInterval *interval;
michael@0:         const LiveInterval::Range *range;
michael@0: 
michael@0:         AllocatedRange()
michael@0:           : interval(nullptr), range(nullptr)
michael@0:         {}
michael@0: 
michael@0:         AllocatedRange(LiveInterval *interval, const LiveInterval::Range *range)
michael@0:           : interval(interval), range(range)
michael@0:         {}
michael@0: 
michael@0:         static int compare(const AllocatedRange &v0, const AllocatedRange &v1) {
michael@0:             // LiveInterval::Range includes 'from' but excludes 'to'.
michael@0:             if (v0.range->to.pos() <= v1.range->from.pos())
michael@0:                 return -1;
michael@0:             if (v0.range->from.pos() >= v1.range->to.pos())
michael@0:                 return 1;
michael@0:             return 0;
michael@0:         }
michael@0:     };
michael@0: 
michael@0:     typedef SplayTree<AllocatedRange, AllocatedRange> AllocatedRangeSet;
michael@0: 
michael@0:     // Each physical register is associated with the set of ranges over which
michael@0:     // that register is currently allocated.
michael@0:     struct PhysicalRegister {
michael@0:         bool allocatable;
michael@0:         AnyRegister reg;
michael@0:         AllocatedRangeSet allocations;
michael@0: 
michael@0:         PhysicalRegister() : allocatable(false) {}
michael@0:     };
michael@0:     mozilla::Array<PhysicalRegister, AnyRegister::Total> registers;
michael@0: 
michael@0:     // Ranges of code which are considered to be hot, for which good allocation
michael@0:     // should be prioritized.
michael@0:     AllocatedRangeSet hotcode;
michael@0: 
michael@0:   public:
michael@0:     BacktrackingAllocator(MIRGenerator *mir, LIRGenerator *lir, LIRGraph &graph)
michael@0:       : LiveRangeAllocator<BacktrackingVirtualRegister, /* forLSRA = */ false>(mir, lir, graph)
michael@0:     { }
michael@0: 
michael@0:     bool go();
michael@0: 
michael@0:   private:
michael@0: 
michael@0:     typedef Vector<LiveInterval *, 4, SystemAllocPolicy> LiveIntervalVector;
michael@0: 
michael@0:     bool init();
michael@0:     bool canAddToGroup(VirtualRegisterGroup *group, BacktrackingVirtualRegister *reg);
michael@0:     bool tryGroupRegisters(uint32_t vreg0, uint32_t vreg1);
michael@0:     bool tryGroupReusedRegister(uint32_t def, uint32_t use);
michael@0:     bool groupAndQueueRegisters();
michael@0:     bool tryAllocateFixed(LiveInterval *interval, bool *success, bool *pfixed, LiveInterval **pconflicting);
michael@0:     bool tryAllocateNonFixed(LiveInterval *interval, bool *success, bool *pfixed, LiveInterval **pconflicting);
michael@0:     bool processInterval(LiveInterval *interval);
michael@0:     bool processGroup(VirtualRegisterGroup *group);
michael@0:     bool setIntervalRequirement(LiveInterval *interval);
michael@0:     bool tryAllocateRegister(PhysicalRegister &r, LiveInterval *interval,
michael@0:                              bool *success, bool *pfixed, LiveInterval **pconflicting);
michael@0:     bool tryAllocateGroupRegister(PhysicalRegister &r, VirtualRegisterGroup *group,
michael@0:                                   bool *psuccess, bool *pfixed, LiveInterval **pconflicting);
michael@0:     bool evictInterval(LiveInterval *interval);
michael@0:     void distributeUses(LiveInterval *interval, const LiveIntervalVector &newIntervals);
michael@0:     bool split(LiveInterval *interval, const LiveIntervalVector &newIntervals);
michael@0:     bool requeueIntervals(const LiveIntervalVector &newIntervals);
michael@0:     void spill(LiveInterval *interval);
michael@0: 
michael@0:     bool isReusedInput(LUse *use, LInstruction *ins, bool considerCopy);
michael@0:     bool isRegisterUse(LUse *use, LInstruction *ins, bool considerCopy = false);
michael@0:     bool isRegisterDefinition(LiveInterval *interval);
michael@0:     bool addLiveInterval(LiveIntervalVector &intervals, uint32_t vreg,
michael@0:                          LiveInterval *spillInterval,
michael@0:                          CodePosition from, CodePosition to);
michael@0: 
michael@0:     bool resolveControlFlow();
michael@0:     bool reifyAllocations();
michael@0:     bool populateSafepoints();
michael@0: 
michael@0:     void dumpRegisterGroups();
michael@0:     void dumpLiveness();
michael@0:     void dumpAllocations();
michael@0: 
michael@0:     struct PrintLiveIntervalRange;
michael@0: 
michael@0:     bool minimalDef(const LiveInterval *interval, LInstruction *ins);
michael@0:     bool minimalUse(const LiveInterval *interval, LInstruction *ins);
michael@0:     bool minimalInterval(const LiveInterval *interval, bool *pfixed = nullptr);
michael@0: 
michael@0:     // Heuristic methods.
michael@0: 
michael@0:     size_t computePriority(const LiveInterval *interval);
michael@0:     size_t computeSpillWeight(const LiveInterval *interval);
michael@0: 
michael@0:     size_t computePriority(const VirtualRegisterGroup *group);
michael@0:     size_t computeSpillWeight(const VirtualRegisterGroup *group);
michael@0: 
michael@0:     bool chooseIntervalSplit(LiveInterval *interval, LiveInterval *conflict);
michael@0: 
michael@0:     bool splitAt(LiveInterval *interval,
michael@0:                  const SplitPositionVector &splitPositions);
michael@0:     bool trySplitAcrossHotcode(LiveInterval *interval, bool *success);
michael@0:     bool trySplitAfterLastRegisterUse(LiveInterval *interval, LiveInterval *conflict, bool *success);
michael@0:     bool splitAtAllRegisterUses(LiveInterval *interval);
michael@0:     bool splitAcrossCalls(LiveInterval *interval);
michael@0: };
michael@0: 
michael@0: } // namespace jit
michael@0: } // namespace js
michael@0: 
michael@0: #endif /* jit_BacktrackingAllocator_h */