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 : #include "jit/StupidAllocator.h"
8 :
9 : #include "jstypes.h"
10 :
11 : using namespace js;
12 : using namespace js::jit;
13 :
14 : static inline uint32_t
15 0 : DefaultStackSlot(uint32_t vreg)
16 : {
17 : // On x86/x64, we have to keep the stack aligned on 16 bytes for spilling
18 : // SIMD registers. To avoid complexity in this stupid allocator, we just
19 : // allocate 16 bytes stack slot for all vreg.
20 0 : return vreg * 2 * sizeof(Value);
21 : }
22 :
23 : LAllocation*
24 0 : StupidAllocator::stackLocation(uint32_t vreg)
25 : {
26 0 : LDefinition* def = virtualRegisters[vreg];
27 0 : if (def->policy() == LDefinition::FIXED && def->output()->isArgument())
28 0 : return def->output();
29 :
30 0 : return new(alloc()) LStackSlot(DefaultStackSlot(vreg));
31 : }
32 :
33 : StupidAllocator::RegisterIndex
34 0 : StupidAllocator::registerIndex(AnyRegister reg)
35 : {
36 0 : for (size_t i = 0; i < registerCount; i++) {
37 0 : if (reg == registers[i].reg)
38 0 : return i;
39 : }
40 0 : MOZ_CRASH("Bad register");
41 : }
42 :
43 : bool
44 0 : StupidAllocator::init()
45 : {
46 0 : if (!RegisterAllocator::init())
47 0 : return false;
48 :
49 0 : if (!virtualRegisters.appendN((LDefinition*)nullptr, graph.numVirtualRegisters()))
50 0 : return false;
51 :
52 0 : for (size_t i = 0; i < graph.numBlocks(); i++) {
53 0 : LBlock* block = graph.getBlock(i);
54 0 : for (LInstructionIterator ins = block->begin(); ins != block->end(); ins++) {
55 0 : for (size_t j = 0; j < ins->numDefs(); j++) {
56 0 : LDefinition* def = ins->getDef(j);
57 0 : virtualRegisters[def->virtualRegister()] = def;
58 : }
59 :
60 0 : for (size_t j = 0; j < ins->numTemps(); j++) {
61 0 : LDefinition* def = ins->getTemp(j);
62 0 : if (def->isBogusTemp())
63 0 : continue;
64 0 : virtualRegisters[def->virtualRegister()] = def;
65 : }
66 : }
67 0 : for (size_t j = 0; j < block->numPhis(); j++) {
68 0 : LPhi* phi = block->getPhi(j);
69 0 : LDefinition* def = phi->getDef(0);
70 0 : uint32_t vreg = def->virtualRegister();
71 :
72 0 : virtualRegisters[vreg] = def;
73 : }
74 : }
75 :
76 : // Assign physical registers to the tracked allocation.
77 : {
78 0 : registerCount = 0;
79 0 : LiveRegisterSet remainingRegisters(allRegisters_.asLiveSet());
80 0 : while (!remainingRegisters.emptyGeneral())
81 0 : registers[registerCount++].reg = AnyRegister(remainingRegisters.takeAnyGeneral());
82 :
83 0 : while (!remainingRegisters.emptyFloat())
84 0 : registers[registerCount++].reg =
85 0 : AnyRegister(remainingRegisters.takeAnyFloat<RegTypeName::Any>());
86 :
87 0 : MOZ_ASSERT(registerCount <= MAX_REGISTERS);
88 : }
89 :
90 0 : return true;
91 : }
92 :
93 : bool
94 0 : StupidAllocator::allocationRequiresRegister(const LAllocation* alloc, AnyRegister reg)
95 : {
96 0 : if (alloc->isRegister() && alloc->toRegister() == reg)
97 0 : return true;
98 0 : if (alloc->isUse()) {
99 0 : const LUse* use = alloc->toUse();
100 0 : if (use->policy() == LUse::FIXED) {
101 0 : AnyRegister usedReg = GetFixedRegister(virtualRegisters[use->virtualRegister()], use);
102 0 : if (usedReg.aliases(reg))
103 0 : return true;
104 : }
105 : }
106 0 : return false;
107 : }
108 :
109 : bool
110 0 : StupidAllocator::registerIsReserved(LInstruction* ins, AnyRegister reg)
111 : {
112 : // Whether reg is already reserved for an input or output of ins.
113 0 : for (LInstruction::InputIterator alloc(*ins); alloc.more(); alloc.next()) {
114 0 : if (allocationRequiresRegister(*alloc, reg))
115 0 : return true;
116 : }
117 0 : for (size_t i = 0; i < ins->numTemps(); i++) {
118 0 : if (allocationRequiresRegister(ins->getTemp(i)->output(), reg))
119 0 : return true;
120 : }
121 0 : for (size_t i = 0; i < ins->numDefs(); i++) {
122 0 : if (allocationRequiresRegister(ins->getDef(i)->output(), reg))
123 0 : return true;
124 : }
125 0 : return false;
126 : }
127 :
128 : AnyRegister
129 0 : StupidAllocator::ensureHasRegister(LInstruction* ins, uint32_t vreg)
130 : {
131 : // Ensure that vreg is held in a register before ins.
132 :
133 : // Check if the virtual register is already held in a physical register.
134 0 : RegisterIndex existing = findExistingRegister(vreg);
135 0 : if (existing != UINT32_MAX) {
136 0 : if (registerIsReserved(ins, registers[existing].reg)) {
137 0 : evictAliasedRegister(ins, existing);
138 : } else {
139 0 : registers[existing].age = ins->id();
140 0 : return registers[existing].reg;
141 : }
142 : }
143 :
144 0 : RegisterIndex best = allocateRegister(ins, vreg);
145 0 : loadRegister(ins, vreg, best, virtualRegisters[vreg]->type());
146 :
147 0 : return registers[best].reg;
148 : }
149 :
150 : StupidAllocator::RegisterIndex
151 0 : StupidAllocator::allocateRegister(LInstruction* ins, uint32_t vreg)
152 : {
153 : // Pick a register for vreg, evicting an existing register if necessary.
154 : // Spill code will be placed before ins, and no existing allocated input
155 : // for ins will be touched.
156 0 : MOZ_ASSERT(ins);
157 :
158 0 : LDefinition* def = virtualRegisters[vreg];
159 0 : MOZ_ASSERT(def);
160 :
161 0 : RegisterIndex best = UINT32_MAX;
162 :
163 0 : for (size_t i = 0; i < registerCount; i++) {
164 0 : AnyRegister reg = registers[i].reg;
165 :
166 0 : if (!def->isCompatibleReg(reg))
167 0 : continue;
168 :
169 : // Skip the register if it is in use for an allocated input or output.
170 0 : if (registerIsReserved(ins, reg))
171 0 : continue;
172 :
173 0 : if (registers[i].vreg == MISSING_ALLOCATION ||
174 0 : best == UINT32_MAX ||
175 0 : registers[best].age > registers[i].age)
176 : {
177 0 : best = i;
178 : }
179 : }
180 :
181 0 : evictAliasedRegister(ins, best);
182 0 : return best;
183 : }
184 :
185 : void
186 0 : StupidAllocator::syncRegister(LInstruction* ins, RegisterIndex index)
187 : {
188 0 : if (registers[index].dirty) {
189 0 : LMoveGroup* input = getInputMoveGroup(ins);
190 0 : LAllocation source(registers[index].reg);
191 :
192 0 : uint32_t existing = registers[index].vreg;
193 0 : LAllocation* dest = stackLocation(existing);
194 0 : input->addAfter(source, *dest, registers[index].type);
195 :
196 0 : registers[index].dirty = false;
197 : }
198 0 : }
199 :
200 : void
201 0 : StupidAllocator::evictRegister(LInstruction* ins, RegisterIndex index)
202 : {
203 0 : syncRegister(ins, index);
204 0 : registers[index].set(MISSING_ALLOCATION);
205 0 : }
206 :
207 : void
208 0 : StupidAllocator::evictAliasedRegister(LInstruction* ins, RegisterIndex index)
209 : {
210 0 : for (size_t i = 0; i < registers[index].reg.numAliased(); i++) {
211 0 : uint32_t aindex = registerIndex(registers[index].reg.aliased(i));
212 0 : syncRegister(ins, aindex);
213 0 : registers[aindex].set(MISSING_ALLOCATION);
214 : }
215 0 : }
216 :
217 : void
218 0 : StupidAllocator::loadRegister(LInstruction* ins, uint32_t vreg, RegisterIndex index, LDefinition::Type type)
219 : {
220 : // Load a vreg from its stack location to a register.
221 0 : LMoveGroup* input = getInputMoveGroup(ins);
222 0 : LAllocation* source = stackLocation(vreg);
223 0 : LAllocation dest(registers[index].reg);
224 0 : input->addAfter(*source, dest, type);
225 0 : registers[index].set(vreg, ins);
226 0 : registers[index].type = type;
227 0 : }
228 :
229 : StupidAllocator::RegisterIndex
230 0 : StupidAllocator::findExistingRegister(uint32_t vreg)
231 : {
232 0 : for (size_t i = 0; i < registerCount; i++) {
233 0 : if (registers[i].vreg == vreg)
234 0 : return i;
235 : }
236 0 : return UINT32_MAX;
237 : }
238 :
239 : bool
240 0 : StupidAllocator::go()
241 : {
242 : // This register allocator is intended to be as simple as possible, while
243 : // still being complicated enough to share properties with more complicated
244 : // allocators. Namely, physical registers may be used to carry virtual
245 : // registers across LIR instructions, but not across basic blocks.
246 : //
247 : // This algorithm does not pay any attention to liveness. It is performed
248 : // as a single forward pass through the basic blocks in the program. As
249 : // virtual registers and temporaries are defined they are assigned physical
250 : // registers, evicting existing allocations in an LRU fashion.
251 :
252 : // For virtual registers not carried in a register, a canonical spill
253 : // location is used. Each vreg has a different spill location; since we do
254 : // not track liveness we cannot determine that two vregs have disjoint
255 : // lifetimes. Thus, the maximum stack height is the number of vregs (scaled
256 : // by two on 32 bit platforms to allow storing double values).
257 0 : graph.setLocalSlotCount(DefaultStackSlot(graph.numVirtualRegisters()));
258 :
259 0 : if (!init())
260 0 : return false;
261 :
262 0 : for (size_t blockIndex = 0; blockIndex < graph.numBlocks(); blockIndex++) {
263 0 : LBlock* block = graph.getBlock(blockIndex);
264 0 : MOZ_ASSERT(block->mir()->id() == blockIndex);
265 :
266 0 : for (size_t i = 0; i < registerCount; i++)
267 0 : registers[i].set(MISSING_ALLOCATION);
268 :
269 0 : for (LInstructionIterator iter = block->begin(); iter != block->end(); iter++) {
270 0 : LInstruction* ins = *iter;
271 :
272 0 : if (ins == *block->rbegin())
273 0 : syncForBlockEnd(block, ins);
274 :
275 0 : allocateForInstruction(ins);
276 : }
277 : }
278 :
279 0 : return true;
280 : }
281 :
282 : void
283 0 : StupidAllocator::syncForBlockEnd(LBlock* block, LInstruction* ins)
284 : {
285 : // Sync any dirty registers, and update the synced state for phi nodes at
286 : // each successor of a block. We cannot conflate the storage for phis with
287 : // that of their inputs, as we cannot prove the live ranges of the phi and
288 : // its input do not overlap. The values for the two may additionally be
289 : // different, as the phi could be for the value of the input in a previous
290 : // loop iteration.
291 :
292 0 : for (size_t i = 0; i < registerCount; i++)
293 0 : syncRegister(ins, i);
294 :
295 0 : LMoveGroup* group = nullptr;
296 :
297 0 : MBasicBlock* successor = block->mir()->successorWithPhis();
298 0 : if (successor) {
299 0 : uint32_t position = block->mir()->positionInPhiSuccessor();
300 0 : LBlock* lirsuccessor = successor->lir();
301 0 : for (size_t i = 0; i < lirsuccessor->numPhis(); i++) {
302 0 : LPhi* phi = lirsuccessor->getPhi(i);
303 :
304 0 : uint32_t sourcevreg = phi->getOperand(position)->toUse()->virtualRegister();
305 0 : uint32_t destvreg = phi->getDef(0)->virtualRegister();
306 :
307 0 : if (sourcevreg == destvreg)
308 0 : continue;
309 :
310 0 : LAllocation* source = stackLocation(sourcevreg);
311 0 : LAllocation* dest = stackLocation(destvreg);
312 :
313 0 : if (!group) {
314 : // The moves we insert here need to happen simultaneously with
315 : // each other, yet after any existing moves before the instruction.
316 0 : LMoveGroup* input = getInputMoveGroup(ins);
317 0 : if (input->numMoves() == 0) {
318 0 : group = input;
319 : } else {
320 0 : group = LMoveGroup::New(alloc());
321 0 : block->insertAfter(input, group);
322 : }
323 : }
324 :
325 0 : group->add(*source, *dest, phi->getDef(0)->type());
326 : }
327 : }
328 0 : }
329 :
330 : void
331 0 : StupidAllocator::allocateForInstruction(LInstruction* ins)
332 : {
333 : // Sync all registers before making a call.
334 0 : if (ins->isCall()) {
335 0 : for (size_t i = 0; i < registerCount; i++)
336 0 : syncRegister(ins, i);
337 : }
338 :
339 : // Allocate for inputs which are required to be in registers.
340 0 : for (LInstruction::InputIterator alloc(*ins); alloc.more(); alloc.next()) {
341 0 : if (!alloc->isUse())
342 0 : continue;
343 0 : LUse* use = alloc->toUse();
344 0 : uint32_t vreg = use->virtualRegister();
345 0 : if (use->policy() == LUse::REGISTER) {
346 0 : AnyRegister reg = ensureHasRegister(ins, vreg);
347 0 : alloc.replace(LAllocation(reg));
348 0 : } else if (use->policy() == LUse::FIXED) {
349 0 : AnyRegister reg = GetFixedRegister(virtualRegisters[vreg], use);
350 0 : RegisterIndex index = registerIndex(reg);
351 0 : if (registers[index].vreg != vreg) {
352 : // Need to evict multiple registers
353 0 : evictAliasedRegister(ins, registerIndex(reg));
354 : // If this vreg is already assigned to an incorrect register
355 0 : RegisterIndex existing = findExistingRegister(vreg);
356 0 : if (existing != UINT32_MAX)
357 0 : evictRegister(ins, existing);
358 0 : loadRegister(ins, vreg, index, virtualRegisters[vreg]->type());
359 : }
360 0 : alloc.replace(LAllocation(reg));
361 : } else {
362 : // Inputs which are not required to be in a register are not
363 : // allocated until after temps/definitions, as the latter may need
364 : // to evict registers which hold these inputs.
365 : }
366 : }
367 :
368 : // Find registers to hold all temporaries and outputs of the instruction.
369 0 : for (size_t i = 0; i < ins->numTemps(); i++) {
370 0 : LDefinition* def = ins->getTemp(i);
371 0 : if (!def->isBogusTemp())
372 0 : allocateForDefinition(ins, def);
373 : }
374 0 : for (size_t i = 0; i < ins->numDefs(); i++) {
375 0 : LDefinition* def = ins->getDef(i);
376 0 : allocateForDefinition(ins, def);
377 : }
378 :
379 : // Allocate for remaining inputs which do not need to be in registers.
380 0 : for (LInstruction::InputIterator alloc(*ins); alloc.more(); alloc.next()) {
381 0 : if (!alloc->isUse())
382 0 : continue;
383 0 : LUse* use = alloc->toUse();
384 0 : uint32_t vreg = use->virtualRegister();
385 0 : MOZ_ASSERT(use->policy() != LUse::REGISTER && use->policy() != LUse::FIXED);
386 :
387 0 : RegisterIndex index = findExistingRegister(vreg);
388 0 : if (index == UINT32_MAX) {
389 0 : LAllocation* stack = stackLocation(use->virtualRegister());
390 0 : alloc.replace(*stack);
391 : } else {
392 0 : registers[index].age = ins->id();
393 0 : alloc.replace(LAllocation(registers[index].reg));
394 : }
395 : }
396 :
397 : // If this is a call, evict all registers except for those holding outputs.
398 0 : if (ins->isCall()) {
399 0 : for (size_t i = 0; i < registerCount; i++) {
400 0 : if (!registers[i].dirty)
401 0 : registers[i].set(MISSING_ALLOCATION);
402 : }
403 : }
404 0 : }
405 :
406 : void
407 0 : StupidAllocator::allocateForDefinition(LInstruction* ins, LDefinition* def)
408 : {
409 0 : uint32_t vreg = def->virtualRegister();
410 :
411 0 : CodePosition from;
412 0 : if ((def->output()->isRegister() && def->policy() == LDefinition::FIXED) ||
413 0 : def->policy() == LDefinition::MUST_REUSE_INPUT)
414 : {
415 : // Result will be in a specific register, spill any vreg held in
416 : // that register before the instruction.
417 : RegisterIndex index =
418 0 : registerIndex(def->policy() == LDefinition::FIXED
419 0 : ? def->output()->toRegister()
420 0 : : ins->getOperand(def->getReusedInput())->toRegister());
421 0 : evictRegister(ins, index);
422 0 : registers[index].set(vreg, ins, true);
423 0 : registers[index].type = virtualRegisters[vreg]->type();
424 0 : def->setOutput(LAllocation(registers[index].reg));
425 0 : } else if (def->policy() == LDefinition::FIXED) {
426 : // The result must be a stack location.
427 0 : def->setOutput(*stackLocation(vreg));
428 : } else {
429 : // Find a register to hold the result of the instruction.
430 0 : RegisterIndex best = allocateRegister(ins, vreg);
431 0 : registers[best].set(vreg, ins, true);
432 0 : registers[best].type = virtualRegisters[vreg]->type();
433 0 : def->setOutput(LAllocation(registers[best].reg));
434 : }
435 0 : }
|
