summaryrefslogtreecommitdiffstats
path: root/js/src/jit/StupidAllocator.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'js/src/jit/StupidAllocator.cpp')
-rw-r--r--js/src/jit/StupidAllocator.cpp434
1 files changed, 434 insertions, 0 deletions
diff --git a/js/src/jit/StupidAllocator.cpp b/js/src/jit/StupidAllocator.cpp
new file mode 100644
index 000000000..8e3ea6286
--- /dev/null
+++ b/js/src/jit/StupidAllocator.cpp
@@ -0,0 +1,434 @@
+/* -*- 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/. */
+
+#include "jit/StupidAllocator.h"
+
+#include "jstypes.h"
+
+using namespace js;
+using namespace js::jit;
+
+static inline uint32_t
+DefaultStackSlot(uint32_t vreg)
+{
+ // On x86/x64, we have to keep the stack aligned on 16 bytes for spilling
+ // SIMD registers. To avoid complexity in this stupid allocator, we just
+ // allocate 16 bytes stack slot for all vreg.
+ return vreg * 2 * sizeof(Value);
+}
+
+LAllocation*
+StupidAllocator::stackLocation(uint32_t vreg)
+{
+ LDefinition* def = virtualRegisters[vreg];
+ if (def->policy() == LDefinition::FIXED && def->output()->isArgument())
+ return def->output();
+
+ return new(alloc()) LStackSlot(DefaultStackSlot(vreg));
+}
+
+StupidAllocator::RegisterIndex
+StupidAllocator::registerIndex(AnyRegister reg)
+{
+ for (size_t i = 0; i < registerCount; i++) {
+ if (reg == registers[i].reg)
+ return i;
+ }
+ MOZ_CRASH("Bad register");
+}
+
+bool
+StupidAllocator::init()
+{
+ if (!RegisterAllocator::init())
+ return false;
+
+ if (!virtualRegisters.appendN((LDefinition*)nullptr, graph.numVirtualRegisters()))
+ return false;
+
+ for (size_t i = 0; i < graph.numBlocks(); i++) {
+ LBlock* block = graph.getBlock(i);
+ for (LInstructionIterator ins = block->begin(); ins != block->end(); ins++) {
+ for (size_t j = 0; j < ins->numDefs(); j++) {
+ LDefinition* def = ins->getDef(j);
+ virtualRegisters[def->virtualRegister()] = def;
+ }
+
+ for (size_t j = 0; j < ins->numTemps(); j++) {
+ LDefinition* def = ins->getTemp(j);
+ if (def->isBogusTemp())
+ continue;
+ virtualRegisters[def->virtualRegister()] = def;
+ }
+ }
+ for (size_t j = 0; j < block->numPhis(); j++) {
+ LPhi* phi = block->getPhi(j);
+ LDefinition* def = phi->getDef(0);
+ uint32_t vreg = def->virtualRegister();
+
+ virtualRegisters[vreg] = def;
+ }
+ }
+
+ // Assign physical registers to the tracked allocation.
+ {
+ registerCount = 0;
+ LiveRegisterSet remainingRegisters(allRegisters_.asLiveSet());
+ while (!remainingRegisters.emptyGeneral())
+ registers[registerCount++].reg = AnyRegister(remainingRegisters.takeAnyGeneral());
+
+ while (!remainingRegisters.emptyFloat())
+ registers[registerCount++].reg = AnyRegister(remainingRegisters.takeAnyFloat());
+
+ MOZ_ASSERT(registerCount <= MAX_REGISTERS);
+ }
+
+ return true;
+}
+
+bool
+StupidAllocator::allocationRequiresRegister(const LAllocation* alloc, AnyRegister reg)
+{
+ if (alloc->isRegister() && alloc->toRegister() == reg)
+ return true;
+ if (alloc->isUse()) {
+ const LUse* use = alloc->toUse();
+ if (use->policy() == LUse::FIXED) {
+ AnyRegister usedReg = GetFixedRegister(virtualRegisters[use->virtualRegister()], use);
+ if (usedReg.aliases(reg))
+ return true;
+ }
+ }
+ return false;
+}
+
+bool
+StupidAllocator::registerIsReserved(LInstruction* ins, AnyRegister reg)
+{
+ // Whether reg is already reserved for an input or output of ins.
+ for (LInstruction::InputIterator alloc(*ins); alloc.more(); alloc.next()) {
+ if (allocationRequiresRegister(*alloc, reg))
+ return true;
+ }
+ for (size_t i = 0; i < ins->numTemps(); i++) {
+ if (allocationRequiresRegister(ins->getTemp(i)->output(), reg))
+ return true;
+ }
+ for (size_t i = 0; i < ins->numDefs(); i++) {
+ if (allocationRequiresRegister(ins->getDef(i)->output(), reg))
+ return true;
+ }
+ return false;
+}
+
+AnyRegister
+StupidAllocator::ensureHasRegister(LInstruction* ins, uint32_t vreg)
+{
+ // Ensure that vreg is held in a register before ins.
+
+ // Check if the virtual register is already held in a physical register.
+ RegisterIndex existing = findExistingRegister(vreg);
+ if (existing != UINT32_MAX) {
+ if (registerIsReserved(ins, registers[existing].reg)) {
+ evictAliasedRegister(ins, existing);
+ } else {
+ registers[existing].age = ins->id();
+ return registers[existing].reg;
+ }
+ }
+
+ RegisterIndex best = allocateRegister(ins, vreg);
+ loadRegister(ins, vreg, best, virtualRegisters[vreg]->type());
+
+ return registers[best].reg;
+}
+
+StupidAllocator::RegisterIndex
+StupidAllocator::allocateRegister(LInstruction* ins, uint32_t vreg)
+{
+ // Pick a register for vreg, evicting an existing register if necessary.
+ // Spill code will be placed before ins, and no existing allocated input
+ // for ins will be touched.
+ MOZ_ASSERT(ins);
+
+ LDefinition* def = virtualRegisters[vreg];
+ MOZ_ASSERT(def);
+
+ RegisterIndex best = UINT32_MAX;
+
+ for (size_t i = 0; i < registerCount; i++) {
+ AnyRegister reg = registers[i].reg;
+
+ if (!def->isCompatibleReg(reg))
+ continue;
+
+ // Skip the register if it is in use for an allocated input or output.
+ if (registerIsReserved(ins, reg))
+ continue;
+
+ if (registers[i].vreg == MISSING_ALLOCATION ||
+ best == UINT32_MAX ||
+ registers[best].age > registers[i].age)
+ {
+ best = i;
+ }
+ }
+
+ evictAliasedRegister(ins, best);
+ return best;
+}
+
+void
+StupidAllocator::syncRegister(LInstruction* ins, RegisterIndex index)
+{
+ if (registers[index].dirty) {
+ LMoveGroup* input = getInputMoveGroup(ins);
+ LAllocation source(registers[index].reg);
+
+ uint32_t existing = registers[index].vreg;
+ LAllocation* dest = stackLocation(existing);
+ input->addAfter(source, *dest, registers[index].type);
+
+ registers[index].dirty = false;
+ }
+}
+
+void
+StupidAllocator::evictRegister(LInstruction* ins, RegisterIndex index)
+{
+ syncRegister(ins, index);
+ registers[index].set(MISSING_ALLOCATION);
+}
+
+void
+StupidAllocator::evictAliasedRegister(LInstruction* ins, RegisterIndex index)
+{
+ for (size_t i = 0; i < registers[index].reg.numAliased(); i++) {
+ uint32_t aindex = registerIndex(registers[index].reg.aliased(i));
+ syncRegister(ins, aindex);
+ registers[aindex].set(MISSING_ALLOCATION);
+ }
+}
+
+void
+StupidAllocator::loadRegister(LInstruction* ins, uint32_t vreg, RegisterIndex index, LDefinition::Type type)
+{
+ // Load a vreg from its stack location to a register.
+ LMoveGroup* input = getInputMoveGroup(ins);
+ LAllocation* source = stackLocation(vreg);
+ LAllocation dest(registers[index].reg);
+ input->addAfter(*source, dest, type);
+ registers[index].set(vreg, ins);
+ registers[index].type = type;
+}
+
+StupidAllocator::RegisterIndex
+StupidAllocator::findExistingRegister(uint32_t vreg)
+{
+ for (size_t i = 0; i < registerCount; i++) {
+ if (registers[i].vreg == vreg)
+ return i;
+ }
+ return UINT32_MAX;
+}
+
+bool
+StupidAllocator::go()
+{
+ // This register allocator is intended to be as simple as possible, while
+ // still being complicated enough to share properties with more complicated
+ // allocators. Namely, physical registers may be used to carry virtual
+ // registers across LIR instructions, but not across basic blocks.
+ //
+ // This algorithm does not pay any attention to liveness. It is performed
+ // as a single forward pass through the basic blocks in the program. As
+ // virtual registers and temporaries are defined they are assigned physical
+ // registers, evicting existing allocations in an LRU fashion.
+
+ // For virtual registers not carried in a register, a canonical spill
+ // location is used. Each vreg has a different spill location; since we do
+ // not track liveness we cannot determine that two vregs have disjoint
+ // lifetimes. Thus, the maximum stack height is the number of vregs (scaled
+ // by two on 32 bit platforms to allow storing double values).
+ graph.setLocalSlotCount(DefaultStackSlot(graph.numVirtualRegisters()));
+
+ if (!init())
+ return false;
+
+ for (size_t blockIndex = 0; blockIndex < graph.numBlocks(); blockIndex++) {
+ LBlock* block = graph.getBlock(blockIndex);
+ MOZ_ASSERT(block->mir()->id() == blockIndex);
+
+ for (size_t i = 0; i < registerCount; i++)
+ registers[i].set(MISSING_ALLOCATION);
+
+ for (LInstructionIterator iter = block->begin(); iter != block->end(); iter++) {
+ LInstruction* ins = *iter;
+
+ if (ins == *block->rbegin())
+ syncForBlockEnd(block, ins);
+
+ allocateForInstruction(ins);
+ }
+ }
+
+ return true;
+}
+
+void
+StupidAllocator::syncForBlockEnd(LBlock* block, LInstruction* ins)
+{
+ // Sync any dirty registers, and update the synced state for phi nodes at
+ // each successor of a block. We cannot conflate the storage for phis with
+ // that of their inputs, as we cannot prove the live ranges of the phi and
+ // its input do not overlap. The values for the two may additionally be
+ // different, as the phi could be for the value of the input in a previous
+ // loop iteration.
+
+ for (size_t i = 0; i < registerCount; i++)
+ syncRegister(ins, i);
+
+ LMoveGroup* group = nullptr;
+
+ MBasicBlock* successor = block->mir()->successorWithPhis();
+ if (successor) {
+ uint32_t position = block->mir()->positionInPhiSuccessor();
+ LBlock* lirsuccessor = successor->lir();
+ for (size_t i = 0; i < lirsuccessor->numPhis(); i++) {
+ LPhi* phi = lirsuccessor->getPhi(i);
+
+ uint32_t sourcevreg = phi->getOperand(position)->toUse()->virtualRegister();
+ uint32_t destvreg = phi->getDef(0)->virtualRegister();
+
+ if (sourcevreg == destvreg)
+ continue;
+
+ LAllocation* source = stackLocation(sourcevreg);
+ LAllocation* dest = stackLocation(destvreg);
+
+ if (!group) {
+ // The moves we insert here need to happen simultaneously with
+ // each other, yet after any existing moves before the instruction.
+ LMoveGroup* input = getInputMoveGroup(ins);
+ if (input->numMoves() == 0) {
+ group = input;
+ } else {
+ group = LMoveGroup::New(alloc());
+ block->insertAfter(input, group);
+ }
+ }
+
+ group->add(*source, *dest, phi->getDef(0)->type());
+ }
+ }
+}
+
+void
+StupidAllocator::allocateForInstruction(LInstruction* ins)
+{
+ // Sync all registers before making a call.
+ if (ins->isCall()) {
+ for (size_t i = 0; i < registerCount; i++)
+ syncRegister(ins, i);
+ }
+
+ // Allocate for inputs which are required to be in registers.
+ for (LInstruction::InputIterator alloc(*ins); alloc.more(); alloc.next()) {
+ if (!alloc->isUse())
+ continue;
+ LUse* use = alloc->toUse();
+ uint32_t vreg = use->virtualRegister();
+ if (use->policy() == LUse::REGISTER) {
+ AnyRegister reg = ensureHasRegister(ins, vreg);
+ alloc.replace(LAllocation(reg));
+ } else if (use->policy() == LUse::FIXED) {
+ AnyRegister reg = GetFixedRegister(virtualRegisters[vreg], use);
+ RegisterIndex index = registerIndex(reg);
+ if (registers[index].vreg != vreg) {
+ // Need to evict multiple registers
+ evictAliasedRegister(ins, registerIndex(reg));
+ // If this vreg is already assigned to an incorrect register
+ RegisterIndex existing = findExistingRegister(vreg);
+ if (existing != UINT32_MAX)
+ evictRegister(ins, existing);
+ loadRegister(ins, vreg, index, virtualRegisters[vreg]->type());
+ }
+ alloc.replace(LAllocation(reg));
+ } else {
+ // Inputs which are not required to be in a register are not
+ // allocated until after temps/definitions, as the latter may need
+ // to evict registers which hold these inputs.
+ }
+ }
+
+ // Find registers to hold all temporaries and outputs of the instruction.
+ for (size_t i = 0; i < ins->numTemps(); i++) {
+ LDefinition* def = ins->getTemp(i);
+ if (!def->isBogusTemp())
+ allocateForDefinition(ins, def);
+ }
+ for (size_t i = 0; i < ins->numDefs(); i++) {
+ LDefinition* def = ins->getDef(i);
+ allocateForDefinition(ins, def);
+ }
+
+ // Allocate for remaining inputs which do not need to be in registers.
+ for (LInstruction::InputIterator alloc(*ins); alloc.more(); alloc.next()) {
+ if (!alloc->isUse())
+ continue;
+ LUse* use = alloc->toUse();
+ uint32_t vreg = use->virtualRegister();
+ MOZ_ASSERT(use->policy() != LUse::REGISTER && use->policy() != LUse::FIXED);
+
+ RegisterIndex index = findExistingRegister(vreg);
+ if (index == UINT32_MAX) {
+ LAllocation* stack = stackLocation(use->virtualRegister());
+ alloc.replace(*stack);
+ } else {
+ registers[index].age = ins->id();
+ alloc.replace(LAllocation(registers[index].reg));
+ }
+ }
+
+ // If this is a call, evict all registers except for those holding outputs.
+ if (ins->isCall()) {
+ for (size_t i = 0; i < registerCount; i++) {
+ if (!registers[i].dirty)
+ registers[i].set(MISSING_ALLOCATION);
+ }
+ }
+}
+
+void
+StupidAllocator::allocateForDefinition(LInstruction* ins, LDefinition* def)
+{
+ uint32_t vreg = def->virtualRegister();
+
+ CodePosition from;
+ if ((def->output()->isRegister() && def->policy() == LDefinition::FIXED) ||
+ def->policy() == LDefinition::MUST_REUSE_INPUT)
+ {
+ // Result will be in a specific register, spill any vreg held in
+ // that register before the instruction.
+ RegisterIndex index =
+ registerIndex(def->policy() == LDefinition::FIXED
+ ? def->output()->toRegister()
+ : ins->getOperand(def->getReusedInput())->toRegister());
+ evictRegister(ins, index);
+ registers[index].set(vreg, ins, true);
+ registers[index].type = virtualRegisters[vreg]->type();
+ def->setOutput(LAllocation(registers[index].reg));
+ } else if (def->policy() == LDefinition::FIXED) {
+ // The result must be a stack location.
+ def->setOutput(*stackLocation(vreg));
+ } else {
+ // Find a register to hold the result of the instruction.
+ RegisterIndex best = allocateRegister(ins, vreg);
+ registers[best].set(vreg, ins, true);
+ registers[best].type = virtualRegisters[vreg]->type();
+ def->setOutput(LAllocation(registers[best].reg));
+ }
+}