1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/js/src/jit/LinearScan.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,138 @@
1.4 +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
1.5 + * vim: set ts=8 sts=4 et sw=4 tw=99:
1.6 + * This Source Code Form is subject to the terms of the Mozilla Public
1.7 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.8 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.9 +
1.10 +#ifndef jit_LinearScan_h
1.11 +#define jit_LinearScan_h
1.12 +
1.13 +#include "jit/LiveRangeAllocator.h"
1.14 +#include "js/Vector.h"
1.15 +
1.16 +namespace js {
1.17 +namespace jit {
1.18 +
1.19 +class LinearScanVirtualRegister : public VirtualRegister
1.20 +{
1.21 + private:
1.22 + LAllocation *canonicalSpill_;
1.23 + CodePosition spillPosition_ ;
1.24 +
1.25 + bool spillAtDefinition_ : 1;
1.26 +
1.27 + // This bit is used to determine whether both halves of a nunbox have been
1.28 + // processed by freeAllocation().
1.29 + bool finished_ : 1;
1.30 +
1.31 + public:
1.32 + LinearScanVirtualRegister(TempAllocator &alloc)
1.33 + : VirtualRegister(alloc)
1.34 + {}
1.35 + void setCanonicalSpill(LAllocation *alloc) {
1.36 + canonicalSpill_ = alloc;
1.37 + }
1.38 + LAllocation *canonicalSpill() const {
1.39 + return canonicalSpill_;
1.40 + }
1.41 + unsigned canonicalSpillSlot() const {
1.42 + return canonicalSpill_->toStackSlot()->slot();
1.43 + }
1.44 + void setFinished() {
1.45 + finished_ = true;
1.46 + }
1.47 + bool finished() const {
1.48 + return finished_;
1.49 + }
1.50 + void setSpillAtDefinition(CodePosition pos) {
1.51 + spillAtDefinition_ = true;
1.52 + setSpillPosition(pos);
1.53 + }
1.54 + bool mustSpillAtDefinition() const {
1.55 + return spillAtDefinition_;
1.56 + }
1.57 + CodePosition spillPosition() const {
1.58 + return spillPosition_;
1.59 + }
1.60 + void setSpillPosition(CodePosition pos) {
1.61 + spillPosition_ = pos;
1.62 + }
1.63 +};
1.64 +
1.65 +class LinearScanAllocator
1.66 + : private LiveRangeAllocator<LinearScanVirtualRegister, /* forLSRA = */ true>
1.67 +{
1.68 + friend class C1Spewer;
1.69 + friend class JSONSpewer;
1.70 +
1.71 + // Work set of LiveIntervals, sorted by start() and then by priority,
1.72 + // non-monotonically descending from tail to head.
1.73 + class UnhandledQueue : public InlineList<LiveInterval>
1.74 + {
1.75 + public:
1.76 + void enqueueForward(LiveInterval *after, LiveInterval *interval);
1.77 + void enqueueBackward(LiveInterval *interval);
1.78 +
1.79 + void assertSorted();
1.80 +
1.81 + LiveInterval *dequeue();
1.82 + };
1.83 +
1.84 + typedef Vector<LiveInterval *, 0, SystemAllocPolicy> SlotList;
1.85 + SlotList finishedSlots_;
1.86 + SlotList finishedDoubleSlots_;
1.87 +#ifdef JS_NUNBOX32
1.88 + SlotList finishedNunboxSlots_;
1.89 +#endif
1.90 +
1.91 + // Run-time state
1.92 + UnhandledQueue unhandled;
1.93 + InlineList<LiveInterval> active;
1.94 + InlineList<LiveInterval> inactive;
1.95 + InlineList<LiveInterval> fixed;
1.96 + InlineList<LiveInterval> handled;
1.97 + LiveInterval *current;
1.98 +
1.99 + bool allocateRegisters();
1.100 + bool resolveControlFlow();
1.101 + bool reifyAllocations();
1.102 + bool populateSafepoints();
1.103 +
1.104 + // Optimization for the UnsortedQueue.
1.105 + void enqueueVirtualRegisterIntervals();
1.106 +
1.107 + uint32_t allocateSlotFor(const LiveInterval *interval);
1.108 + bool splitInterval(LiveInterval *interval, CodePosition pos);
1.109 + bool splitBlockingIntervals(LAllocation allocation);
1.110 + bool assign(LAllocation allocation);
1.111 + bool spill();
1.112 + void freeAllocation(LiveInterval *interval, LAllocation *alloc);
1.113 + void finishInterval(LiveInterval *interval);
1.114 + AnyRegister::Code findBestFreeRegister(CodePosition *freeUntil);
1.115 + AnyRegister::Code findBestBlockedRegister(CodePosition *nextUsed);
1.116 + bool canCoexist(LiveInterval *a, LiveInterval *b);
1.117 + bool moveInputAlloc(CodePosition pos, LAllocation *from, LAllocation *to, LDefinition::Type type);
1.118 + void setIntervalRequirement(LiveInterval *interval);
1.119 + bool isSpilledAt(LiveInterval *interval, CodePosition pos);
1.120 +
1.121 +#ifdef DEBUG
1.122 + void validateIntervals();
1.123 + void validateAllocations();
1.124 +#else
1.125 + inline void validateIntervals() { }
1.126 + inline void validateAllocations() { }
1.127 +#endif
1.128 +
1.129 + public:
1.130 + LinearScanAllocator(MIRGenerator *mir, LIRGenerator *lir, LIRGraph &graph)
1.131 + : LiveRangeAllocator<LinearScanVirtualRegister, /* forLSRA = */ true>(mir, lir, graph)
1.132 + {
1.133 + }
1.134 +
1.135 + bool go();
1.136 +};
1.137 +
1.138 +} // namespace jit
1.139 +} // namespace js
1.140 +
1.141 +#endif /* jit_LinearScan_h */
