Line data Source code
1 : /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2 : * vim: set ts=8 sts=4 et sw=4 tw=99:
3 : * This Source Code Form is subject to the terms of the Mozilla Public
4 : * License, v. 2.0. If a copy of the MPL was not distributed with this
5 : * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6 :
7 : #ifndef jit_RegisterAllocator_h
8 : #define jit_RegisterAllocator_h
9 :
10 : #include "mozilla/Attributes.h"
11 : #include "mozilla/MathAlgorithms.h"
12 :
13 : #include "jit/LIR.h"
14 : #include "jit/MIRGenerator.h"
15 : #include "jit/MIRGraph.h"
16 :
17 : // Generic structures and functions for use by register allocators.
18 :
19 : namespace js {
20 : namespace jit {
21 :
22 : class LIRGenerator;
23 :
24 : // Structure for running a liveness analysis on a finished register allocation.
25 : // This analysis can be used for two purposes:
26 : //
27 : // - Check the integrity of the allocation, i.e. that the reads and writes of
28 : // physical values preserve the semantics of the original virtual registers.
29 : //
30 : // - Populate safepoints with live registers, GC thing and value data, to
31 : // streamline the process of prototyping new allocators.
32 8 : struct AllocationIntegrityState
33 : {
34 8 : explicit AllocationIntegrityState(LIRGraph& graph)
35 8 : : graph(graph)
36 8 : {}
37 :
38 : // Record all virtual registers in the graph. This must be called before
39 : // register allocation, to pick up the original LUses.
40 : MOZ_MUST_USE bool record();
41 :
42 : // Perform the liveness analysis on the graph, and assert on an invalid
43 : // allocation. This must be called after register allocation, to pick up
44 : // all assigned physical values. If populateSafepoints is specified,
45 : // safepoints will be filled in with liveness information.
46 : MOZ_MUST_USE bool check(bool populateSafepoints);
47 :
48 : private:
49 :
50 : LIRGraph& graph;
51 :
52 : // For all instructions and phis in the graph, keep track of the virtual
53 : // registers for all inputs and outputs of the nodes. These are overwritten
54 : // in place during register allocation. This information is kept on the
55 : // side rather than in the instructions and phis themselves to avoid
56 : // debug-builds-only bloat in the size of the involved structures.
57 :
58 1900 : struct InstructionInfo {
59 : Vector<LAllocation, 2, SystemAllocPolicy> inputs;
60 : Vector<LDefinition, 0, SystemAllocPolicy> temps;
61 : Vector<LDefinition, 1, SystemAllocPolicy> outputs;
62 :
63 183 : InstructionInfo()
64 183 : { }
65 :
66 1717 : InstructionInfo(const InstructionInfo& o)
67 1717 : {
68 3434 : AutoEnterOOMUnsafeRegion oomUnsafe;
69 5151 : if (!inputs.appendAll(o.inputs) ||
70 3434 : !temps.appendAll(o.temps) ||
71 1717 : !outputs.appendAll(o.outputs))
72 : {
73 0 : oomUnsafe.crash("InstructionInfo::InstructionInfo");
74 : }
75 1717 : }
76 : };
77 : Vector<InstructionInfo, 0, SystemAllocPolicy> instructions;
78 :
79 806 : struct BlockInfo {
80 : Vector<InstructionInfo, 5, SystemAllocPolicy> phis;
81 403 : BlockInfo() {}
82 403 : BlockInfo(const BlockInfo& o) {
83 806 : AutoEnterOOMUnsafeRegion oomUnsafe;
84 403 : if (!phis.appendAll(o.phis))
85 0 : oomUnsafe.crash("BlockInfo::BlockInfo");
86 403 : }
87 : };
88 : Vector<BlockInfo, 0, SystemAllocPolicy> blocks;
89 :
90 : Vector<LDefinition*, 20, SystemAllocPolicy> virtualRegisters;
91 :
92 : // Describes a correspondence that should hold at the end of a block.
93 : // The value which was written to vreg in the original LIR should be
94 : // physically stored in alloc after the register allocation.
95 12510 : struct IntegrityItem
96 : {
97 : LBlock* block;
98 : uint32_t vreg;
99 : LAllocation alloc;
100 :
101 : // Order of insertion into seen, for sorting.
102 : uint32_t index;
103 :
104 : typedef IntegrityItem Lookup;
105 12510 : static HashNumber hash(const IntegrityItem& item) {
106 12510 : HashNumber hash = item.alloc.hash();
107 12510 : hash = mozilla::RotateLeft(hash, 4) ^ item.vreg;
108 12510 : hash = mozilla::RotateLeft(hash, 4) ^ HashNumber(item.block->mir()->id());
109 12510 : return hash;
110 : }
111 5637 : static bool match(const IntegrityItem& one, const IntegrityItem& two) {
112 5637 : return one.block == two.block
113 5630 : && one.vreg == two.vreg
114 11267 : && one.alloc == two.alloc;
115 : }
116 : };
117 :
118 : // Items still to be processed.
119 : Vector<IntegrityItem, 10, SystemAllocPolicy> worklist;
120 :
121 : // Set of all items that have already been processed.
122 : typedef HashSet<IntegrityItem, IntegrityItem, SystemAllocPolicy> IntegrityItemSet;
123 : IntegrityItemSet seen;
124 :
125 : MOZ_MUST_USE bool checkIntegrity(LBlock* block, LInstruction* ins, uint32_t vreg,
126 : LAllocation alloc, bool populateSafepoints);
127 : MOZ_MUST_USE bool checkSafepointAllocation(LInstruction* ins, uint32_t vreg, LAllocation alloc,
128 : bool populateSafepoints);
129 : MOZ_MUST_USE bool addPredecessor(LBlock* block, uint32_t vreg, LAllocation alloc);
130 :
131 : void dump();
132 : };
133 :
134 : // Represents with better-than-instruction precision a position in the
135 : // instruction stream.
136 : //
137 : // An issue comes up when performing register allocation as to how to represent
138 : // information such as "this register is only needed for the input of
139 : // this instruction, it can be clobbered in the output". Just having ranges
140 : // of instruction IDs is insufficiently expressive to denote all possibilities.
141 : // This class solves this issue by associating an extra bit with the instruction
142 : // ID which indicates whether the position is the input half or output half of
143 : // an instruction.
144 : class CodePosition
145 : {
146 : private:
147 46068 : constexpr explicit CodePosition(uint32_t bits)
148 46068 : : bits_(bits)
149 46068 : { }
150 :
151 : static const unsigned int INSTRUCTION_SHIFT = 1;
152 : static const unsigned int SUBPOSITION_MASK = 1;
153 : uint32_t bits_;
154 :
155 : public:
156 : static const CodePosition MAX;
157 : static const CodePosition MIN;
158 :
159 : // This is the half of the instruction this code position represents, as
160 : // described in the huge comment above.
161 : enum SubPosition {
162 : INPUT,
163 : OUTPUT
164 : };
165 :
166 54104 : constexpr CodePosition() : bits_(0)
167 54104 : { }
168 :
169 54581 : CodePosition(uint32_t instruction, SubPosition where) {
170 54581 : MOZ_ASSERT(instruction < 0x80000000u);
171 54581 : MOZ_ASSERT(((uint32_t)where & SUBPOSITION_MASK) == (uint32_t)where);
172 54581 : bits_ = (instruction << INSTRUCTION_SHIFT) | (uint32_t)where;
173 54581 : }
174 :
175 16394 : uint32_t ins() const {
176 16394 : return bits_ >> INSTRUCTION_SHIFT;
177 : }
178 :
179 8575 : uint32_t bits() const {
180 8575 : return bits_;
181 : }
182 :
183 6203 : SubPosition subpos() const {
184 6203 : return (SubPosition)(bits_ & SUBPOSITION_MASK);
185 : }
186 :
187 140772 : bool operator <(CodePosition other) const {
188 140772 : return bits_ < other.bits_;
189 : }
190 :
191 974636 : bool operator <=(CodePosition other) const {
192 974636 : return bits_ <= other.bits_;
193 : }
194 :
195 47253 : bool operator !=(CodePosition other) const {
196 47253 : return bits_ != other.bits_;
197 : }
198 :
199 61421 : bool operator ==(CodePosition other) const {
200 61421 : return bits_ == other.bits_;
201 : }
202 :
203 58169 : bool operator >(CodePosition other) const {
204 58169 : return bits_ > other.bits_;
205 : }
206 :
207 152592 : bool operator >=(CodePosition other) const {
208 152592 : return bits_ >= other.bits_;
209 : }
210 :
211 17119 : uint32_t operator -(CodePosition other) const {
212 17119 : MOZ_ASSERT(bits_ >= other.bits_);
213 17119 : return bits_ - other.bits_;
214 : }
215 :
216 718 : CodePosition previous() const {
217 718 : MOZ_ASSERT(*this != MIN);
218 718 : return CodePosition(bits_ - 1);
219 : }
220 45350 : CodePosition next() const {
221 45350 : MOZ_ASSERT(*this != MAX);
222 45350 : return CodePosition(bits_ + 1);
223 : }
224 : };
225 :
226 : // Structure to track all moves inserted next to instructions in a graph.
227 : class InstructionDataMap
228 : {
229 : FixedList<LNode*> insData_;
230 :
231 : public:
232 8 : InstructionDataMap()
233 8 : : insData_()
234 8 : { }
235 :
236 8 : MOZ_MUST_USE bool init(MIRGenerator* gen, uint32_t numInstructions) {
237 8 : if (!insData_.init(gen->alloc(), numInstructions))
238 0 : return false;
239 8 : memset(&insData_[0], 0, sizeof(LNode*) * numInstructions);
240 8 : return true;
241 : }
242 :
243 16394 : LNode*& operator[](CodePosition pos) {
244 16394 : return operator[](pos.ins());
245 : }
246 : LNode* const& operator[](CodePosition pos) const {
247 : return operator[](pos.ins());
248 : }
249 22720 : LNode*& operator[](uint32_t ins) {
250 22720 : return insData_[ins];
251 : }
252 : LNode* const& operator[](uint32_t ins) const {
253 : return insData_[ins];
254 : }
255 : };
256 :
257 : // Common superclass for register allocators.
258 8 : class RegisterAllocator
259 : {
260 : void operator=(const RegisterAllocator&) = delete;
261 : RegisterAllocator(const RegisterAllocator&) = delete;
262 :
263 : protected:
264 : // Context
265 : MIRGenerator* mir;
266 : LIRGenerator* lir;
267 : LIRGraph& graph;
268 :
269 : // Pool of all registers that should be considered allocateable
270 : AllocatableRegisterSet allRegisters_;
271 :
272 : // Computed data
273 : InstructionDataMap insData;
274 : Vector<CodePosition, 12, SystemAllocPolicy> entryPositions;
275 : Vector<CodePosition, 12, SystemAllocPolicy> exitPositions;
276 :
277 8 : RegisterAllocator(MIRGenerator* mir, LIRGenerator* lir, LIRGraph& graph)
278 8 : : mir(mir),
279 : lir(lir),
280 : graph(graph),
281 8 : allRegisters_(RegisterSet::All())
282 : {
283 8 : if (mir->compilingWasm()) {
284 : #if defined(JS_CODEGEN_X64) || defined(JS_CODEGEN_ARM) || \
285 : defined(JS_CODEGEN_MIPS32) || defined(JS_CODEGEN_MIPS64)
286 0 : allRegisters_.take(AnyRegister(HeapReg));
287 : #elif defined(JS_CODEGEN_ARM64)
288 : allRegisters_.take(AnyRegister(HeapReg));
289 : allRegisters_.take(AnyRegister(HeapLenReg));
290 : #endif
291 0 : allRegisters_.take(FramePointer);
292 : } else {
293 : #if defined(JS_CODEGEN_X86) || defined(JS_CODEGEN_X64) || defined(JS_CODEGEN_ARM64)
294 8 : if (mir->instrumentedProfiling())
295 0 : allRegisters_.take(AnyRegister(FramePointer));
296 : #endif
297 : }
298 8 : }
299 :
300 : MOZ_MUST_USE bool init();
301 :
302 34521 : TempAllocator& alloc() const {
303 34521 : return mir->alloc();
304 : }
305 :
306 5482 : CodePosition outputOf(const LNode* ins) const {
307 5482 : return ins->isPhi()
308 0 : ? outputOf(ins->toPhi())
309 5482 : : outputOf(ins->toInstruction());
310 : }
311 0 : CodePosition outputOf(const LPhi* ins) const {
312 : // All phis in a block write their outputs after all of them have
313 : // read their inputs. Consequently, it doesn't make sense to talk
314 : // about code positions in the middle of a series of phis.
315 0 : LBlock* block = ins->block();
316 0 : return CodePosition(block->getPhi(block->numPhis() - 1)->id(), CodePosition::OUTPUT);
317 : }
318 16999 : CodePosition outputOf(const LInstruction* ins) const {
319 16999 : return CodePosition(ins->id(), CodePosition::OUTPUT);
320 : }
321 3719 : CodePosition inputOf(const LNode* ins) const {
322 3719 : return ins->isPhi()
323 108 : ? inputOf(ins->toPhi())
324 3827 : : inputOf(ins->toInstruction());
325 : }
326 108 : CodePosition inputOf(const LPhi* ins) const {
327 : // All phis in a block read their inputs before any of them write their
328 : // outputs. Consequently, it doesn't make sense to talk about code
329 : // positions in the middle of a series of phis.
330 108 : return CodePosition(ins->block()->getPhi(0)->id(), CodePosition::INPUT);
331 : }
332 37412 : CodePosition inputOf(const LInstruction* ins) const {
333 37412 : return CodePosition(ins->id(), CodePosition::INPUT);
334 : }
335 25241 : CodePosition entryOf(const LBlock* block) {
336 25241 : return entryPositions[block->mir()->id()];
337 : }
338 16151 : CodePosition exitOf(const LBlock* block) {
339 16151 : return exitPositions[block->mir()->id()];
340 : }
341 :
342 : LMoveGroup* getInputMoveGroup(LInstruction* ins);
343 : LMoveGroup* getFixReuseMoveGroup(LInstruction* ins);
344 : LMoveGroup* getMoveGroupAfter(LInstruction* ins);
345 :
346 4792 : CodePosition minimalDefEnd(LNode* ins) {
347 : // Compute the shortest interval that captures vregs defined by ins.
348 : // Watch for instructions that are followed by an OSI point.
349 : // If moves are introduced between the instruction and the OSI point then
350 : // safepoint information for the instruction may be incorrect.
351 : while (true) {
352 4792 : LNode* next = insData[ins->id() + 1];
353 4792 : if (!next->isOsiPoint())
354 3954 : break;
355 838 : ins = next;
356 838 : }
357 :
358 3954 : return outputOf(ins);
359 : }
360 :
361 : void dumpInstructions();
362 : };
363 :
364 : static inline AnyRegister
365 265 : GetFixedRegister(const LDefinition* def, const LUse* use)
366 : {
367 265 : return def->isFloatReg()
368 : ? AnyRegister(FloatRegister::FromCode(use->registerCode()))
369 265 : : AnyRegister(Register::FromCode(use->registerCode()));
370 : }
371 :
372 : } // namespace jit
373 : } // namespace js
374 :
375 : #endif /* jit_RegisterAllocator_h */
|
