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