js/src/jit/RegisterAllocator.h@129ffea94266
js/src/jit/RegisterAllocator.h
Sat, 03 Jan 2015 20:18:00 +0100
- author
- Michael Schloh von Bennewitz <michael@schloh.com>
- date
- Sat, 03 Jan 2015 20:18:00 +0100
- branch
- TOR_BUG_3246
- changeset 7
- 129ffea94266
- permissions
- -rw-r--r--
Conditionally enable double key logic according to:
private browsing mode or privacy.thirdparty.isolate preference and
implement in GetCookieStringCommon and FindCookie where it counts...
With some reservations of how to convince FindCookie users to test
condition and pass a nullptr when disabling double key logic.
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/. */
7 #ifndef jit_RegisterAllocator_h
8 #define jit_RegisterAllocator_h
10 #include "mozilla/Attributes.h"
11 #include "mozilla/MathAlgorithms.h"
13 #include "jit/LIR.h"
14 #include "jit/MIRGenerator.h"
15 #include "jit/MIRGraph.h"
17 // Generic structures and functions for use by register allocators.
19 namespace js {
20 namespace jit {
22 class LIRGenerator;
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 struct AllocationIntegrityState
33 {
34 explicit AllocationIntegrityState(const LIRGraph &graph)
35 : graph(graph)
36 {}
38 // Record all virtual registers in the graph. This must be called before
39 // register allocation, to pick up the original LUses.
40 bool record();
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 bool check(bool populateSafepoints);
48 private:
50 const LIRGraph &graph;
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.
58 struct InstructionInfo {
59 Vector<LAllocation, 2, SystemAllocPolicy> inputs;
60 Vector<LDefinition, 0, SystemAllocPolicy> temps;
61 Vector<LDefinition, 1, SystemAllocPolicy> outputs;
63 InstructionInfo()
64 { }
66 InstructionInfo(const InstructionInfo &o)
67 {
68 inputs.appendAll(o.inputs);
69 temps.appendAll(o.temps);
70 outputs.appendAll(o.outputs);
71 }
72 };
73 Vector<InstructionInfo, 0, SystemAllocPolicy> instructions;
75 struct BlockInfo {
76 Vector<InstructionInfo, 5, SystemAllocPolicy> phis;
77 BlockInfo() {}
78 BlockInfo(const BlockInfo &o) {
79 phis.appendAll(o.phis);
80 }
81 };
82 Vector<BlockInfo, 0, SystemAllocPolicy> blocks;
84 Vector<LDefinition*, 20, SystemAllocPolicy> virtualRegisters;
86 // Describes a correspondence that should hold at the end of a block.
87 // The value which was written to vreg in the original LIR should be
88 // physically stored in alloc after the register allocation.
89 struct IntegrityItem
90 {
91 LBlock *block;
92 uint32_t vreg;
93 LAllocation alloc;
95 // Order of insertion into seen, for sorting.
96 uint32_t index;
98 typedef IntegrityItem Lookup;
99 static HashNumber hash(const IntegrityItem &item) {
100 HashNumber hash = item.alloc.hash();
101 hash = mozilla::RotateLeft(hash, 4) ^ item.vreg;
102 hash = mozilla::RotateLeft(hash, 4) ^ HashNumber(item.block->mir()->id());
103 return hash;
104 }
105 static bool match(const IntegrityItem &one, const IntegrityItem &two) {
106 return one.block == two.block
107 && one.vreg == two.vreg
108 && one.alloc == two.alloc;
109 }
110 };
112 // Items still to be processed.
113 Vector<IntegrityItem, 10, SystemAllocPolicy> worklist;
115 // Set of all items that have already been processed.
116 typedef HashSet<IntegrityItem, IntegrityItem, SystemAllocPolicy> IntegrityItemSet;
117 IntegrityItemSet seen;
119 bool checkIntegrity(LBlock *block, LInstruction *ins, uint32_t vreg, LAllocation alloc,
120 bool populateSafepoints);
121 bool checkSafepointAllocation(LInstruction *ins, uint32_t vreg, LAllocation alloc,
122 bool populateSafepoints);
123 bool addPredecessor(LBlock *block, uint32_t vreg, LAllocation alloc);
125 void dump();
126 };
128 // Represents with better-than-instruction precision a position in the
129 // instruction stream.
130 //
131 // An issue comes up when performing register allocation as to how to represent
132 // information such as "this register is only needed for the input of
133 // this instruction, it can be clobbered in the output". Just having ranges
134 // of instruction IDs is insufficiently expressive to denote all possibilities.
135 // This class solves this issue by associating an extra bit with the instruction
136 // ID which indicates whether the position is the input half or output half of
137 // an instruction.
138 class CodePosition
139 {
140 private:
141 MOZ_CONSTEXPR CodePosition(const uint32_t &bits)
142 : bits_(bits)
143 { }
145 static const unsigned int INSTRUCTION_SHIFT = 1;
146 static const unsigned int SUBPOSITION_MASK = 1;
147 uint32_t bits_;
149 public:
150 static const CodePosition MAX;
151 static const CodePosition MIN;
153 // This is the half of the instruction this code position represents, as
154 // described in the huge comment above.
155 enum SubPosition {
156 INPUT,
157 OUTPUT
158 };
160 MOZ_CONSTEXPR CodePosition() : bits_(0)
161 { }
163 CodePosition(uint32_t instruction, SubPosition where) {
164 JS_ASSERT(instruction < 0x80000000u);
165 JS_ASSERT(((uint32_t)where & SUBPOSITION_MASK) == (uint32_t)where);
166 bits_ = (instruction << INSTRUCTION_SHIFT) | (uint32_t)where;
167 }
169 uint32_t ins() const {
170 return bits_ >> INSTRUCTION_SHIFT;
171 }
173 uint32_t pos() const {
174 return bits_;
175 }
177 SubPosition subpos() const {
178 return (SubPosition)(bits_ & SUBPOSITION_MASK);
179 }
181 bool operator <(const CodePosition &other) const {
182 return bits_ < other.bits_;
183 }
185 bool operator <=(const CodePosition &other) const {
186 return bits_ <= other.bits_;
187 }
189 bool operator !=(const CodePosition &other) const {
190 return bits_ != other.bits_;
191 }
193 bool operator ==(const CodePosition &other) const {
194 return bits_ == other.bits_;
195 }
197 bool operator >(const CodePosition &other) const {
198 return bits_ > other.bits_;
199 }
201 bool operator >=(const CodePosition &other) const {
202 return bits_ >= other.bits_;
203 }
205 CodePosition previous() const {
206 JS_ASSERT(*this != MIN);
207 return CodePosition(bits_ - 1);
208 }
209 CodePosition next() const {
210 JS_ASSERT(*this != MAX);
211 return CodePosition(bits_ + 1);
212 }
213 };
215 // Structure to track moves inserted before or after an instruction.
216 class InstructionData
217 {
218 LInstruction *ins_;
219 LBlock *block_;
220 LMoveGroup *inputMoves_;
221 LMoveGroup *movesAfter_;
223 public:
224 void init(LInstruction *ins, LBlock *block) {
225 JS_ASSERT(!ins_);
226 JS_ASSERT(!block_);
227 ins_ = ins;
228 block_ = block;
229 }
230 LInstruction *ins() const {
231 return ins_;
232 }
233 LBlock *block() const {
234 return block_;
235 }
236 void setInputMoves(LMoveGroup *moves) {
237 inputMoves_ = moves;
238 }
239 LMoveGroup *inputMoves() const {
240 return inputMoves_;
241 }
242 void setMovesAfter(LMoveGroup *moves) {
243 movesAfter_ = moves;
244 }
245 LMoveGroup *movesAfter() const {
246 return movesAfter_;
247 }
248 };
250 // Structure to track all moves inserted next to instructions in a graph.
251 class InstructionDataMap
252 {
253 InstructionData *insData_;
254 uint32_t numIns_;
256 public:
257 InstructionDataMap()
258 : insData_(nullptr),
259 numIns_(0)
260 { }
262 bool init(MIRGenerator *gen, uint32_t numInstructions) {
263 insData_ = gen->allocate<InstructionData>(numInstructions);
264 numIns_ = numInstructions;
265 if (!insData_)
266 return false;
267 memset(insData_, 0, sizeof(InstructionData) * numInstructions);
268 return true;
269 }
271 InstructionData &operator[](const CodePosition &pos) {
272 JS_ASSERT(pos.ins() < numIns_);
273 return insData_[pos.ins()];
274 }
275 InstructionData &operator[](LInstruction *ins) {
276 JS_ASSERT(ins->id() < numIns_);
277 return insData_[ins->id()];
278 }
279 InstructionData &operator[](uint32_t ins) {
280 JS_ASSERT(ins < numIns_);
281 return insData_[ins];
282 }
283 };
285 // Common superclass for register allocators.
286 class RegisterAllocator
287 {
288 void operator=(const RegisterAllocator &) MOZ_DELETE;
289 RegisterAllocator(const RegisterAllocator &) MOZ_DELETE;
291 protected:
292 // Context
293 MIRGenerator *mir;
294 LIRGenerator *lir;
295 LIRGraph &graph;
297 // Pool of all registers that should be considered allocateable
298 RegisterSet allRegisters_;
300 // Computed data
301 InstructionDataMap insData;
303 RegisterAllocator(MIRGenerator *mir, LIRGenerator *lir, LIRGraph &graph)
304 : mir(mir),
305 lir(lir),
306 graph(graph),
307 allRegisters_(RegisterSet::All())
308 {
309 if (FramePointer != InvalidReg && mir->instrumentedProfiling())
310 allRegisters_.take(AnyRegister(FramePointer));
311 #if defined(JS_CODEGEN_X64)
312 if (mir->compilingAsmJS())
313 allRegisters_.take(AnyRegister(HeapReg));
314 #elif defined(JS_CODEGEN_ARM) || defined(JS_CODEGEN_MIPS)
315 if (mir->compilingAsmJS()) {
316 allRegisters_.take(AnyRegister(HeapReg));
317 allRegisters_.take(AnyRegister(GlobalReg));
318 allRegisters_.take(AnyRegister(NANReg));
319 }
320 #endif
321 }
323 bool init();
325 TempAllocator &alloc() const {
326 return mir->alloc();
327 }
329 static CodePosition outputOf(uint32_t pos) {
330 return CodePosition(pos, CodePosition::OUTPUT);
331 }
332 static CodePosition outputOf(const LInstruction *ins) {
333 return CodePosition(ins->id(), CodePosition::OUTPUT);
334 }
335 static CodePosition inputOf(uint32_t pos) {
336 return CodePosition(pos, CodePosition::INPUT);
337 }
338 static CodePosition inputOf(const LInstruction *ins) {
339 // Phi nodes "use" their inputs before the beginning of the block.
340 JS_ASSERT(!ins->isPhi());
341 return CodePosition(ins->id(), CodePosition::INPUT);
342 }
344 LMoveGroup *getInputMoveGroup(uint32_t ins);
345 LMoveGroup *getMoveGroupAfter(uint32_t ins);
347 LMoveGroup *getInputMoveGroup(CodePosition pos) {
348 return getInputMoveGroup(pos.ins());
349 }
350 LMoveGroup *getMoveGroupAfter(CodePosition pos) {
351 return getMoveGroupAfter(pos.ins());
352 }
354 CodePosition minimalDefEnd(LInstruction *ins) {
355 // Compute the shortest interval that captures vregs defined by ins.
356 // Watch for instructions that are followed by an OSI point and/or Nop.
357 // If moves are introduced between the instruction and the OSI point then
358 // safepoint information for the instruction may be incorrect.
359 while (true) {
360 LInstruction *next = insData[outputOf(ins).next()].ins();
361 if (!next->isNop() && !next->isOsiPoint())
362 break;
363 ins = next;
364 }
366 return outputOf(ins);
367 }
368 };
370 static inline AnyRegister
371 GetFixedRegister(const LDefinition *def, const LUse *use)
372 {
373 return def->isFloatReg()
374 ? AnyRegister(FloatRegister::FromCode(use->registerCode()))
375 : AnyRegister(Register::FromCode(use->registerCode()));
376 }
378 } // namespace jit
379 } // namespace js
381 #endif /* jit_RegisterAllocator_h */
