michael@0: /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
michael@0:  * vim: set ts=8 sts=4 et sw=4 tw=99:
michael@0:  * This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: #include "jit/StupidAllocator.h"
michael@0: 
michael@0: #include "jstypes.h"
michael@0: 
michael@0: using namespace js;
michael@0: using namespace js::jit;
michael@0: 
michael@0: static inline uint32_t
michael@0: DefaultStackSlot(uint32_t vreg)
michael@0: {
michael@0:     return vreg * sizeof(Value);
michael@0: }
michael@0: 
michael@0: LAllocation *
michael@0: StupidAllocator::stackLocation(uint32_t vreg)
michael@0: {
michael@0:     LDefinition *def = virtualRegisters[vreg];
michael@0:     if (def->policy() == LDefinition::PRESET && def->output()->isArgument())
michael@0:         return def->output();
michael@0: 
michael@0:     return new(alloc()) LStackSlot(DefaultStackSlot(vreg));
michael@0: }
michael@0: 
michael@0: StupidAllocator::RegisterIndex
michael@0: StupidAllocator::registerIndex(AnyRegister reg)
michael@0: {
michael@0:     for (size_t i = 0; i < registerCount; i++) {
michael@0:         if (reg == registers[i].reg)
michael@0:             return i;
michael@0:     }
michael@0:     MOZ_ASSUME_UNREACHABLE("Bad register");
michael@0: }
michael@0: 
michael@0: bool
michael@0: StupidAllocator::init()
michael@0: {
michael@0:     if (!RegisterAllocator::init())
michael@0:         return false;
michael@0: 
michael@0:     if (!virtualRegisters.appendN((LDefinition *)nullptr, graph.numVirtualRegisters()))
michael@0:         return false;
michael@0: 
michael@0:     for (size_t i = 0; i < graph.numBlocks(); i++) {
michael@0:         LBlock *block = graph.getBlock(i);
michael@0:         for (LInstructionIterator ins = block->begin(); ins != block->end(); ins++) {
michael@0:             for (size_t j = 0; j < ins->numDefs(); j++) {
michael@0:                 LDefinition *def = ins->getDef(j);
michael@0:                 if (def->policy() != LDefinition::PASSTHROUGH)
michael@0:                     virtualRegisters[def->virtualRegister()] = def;
michael@0:             }
michael@0: 
michael@0:             for (size_t j = 0; j < ins->numTemps(); j++) {
michael@0:                 LDefinition *def = ins->getTemp(j);
michael@0:                 if (def->isBogusTemp())
michael@0:                     continue;
michael@0:                 virtualRegisters[def->virtualRegister()] = def;
michael@0:             }
michael@0:         }
michael@0:         for (size_t j = 0; j < block->numPhis(); j++) {
michael@0:             LPhi *phi = block->getPhi(j);
michael@0:             LDefinition *def = phi->getDef(0);
michael@0:             uint32_t vreg = def->virtualRegister();
michael@0: 
michael@0:             virtualRegisters[vreg] = def;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     // Assign physical registers to the tracked allocation.
michael@0:     {
michael@0:         registerCount = 0;
michael@0:         RegisterSet remainingRegisters(allRegisters_);
michael@0:         while (!remainingRegisters.empty(/* float = */ false))
michael@0:             registers[registerCount++].reg = AnyRegister(remainingRegisters.takeGeneral());
michael@0:         while (!remainingRegisters.empty(/* float = */ true))
michael@0:             registers[registerCount++].reg = AnyRegister(remainingRegisters.takeFloat());
michael@0:         JS_ASSERT(registerCount <= MAX_REGISTERS);
michael@0:     }
michael@0: 
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: bool
michael@0: StupidAllocator::allocationRequiresRegister(const LAllocation *alloc, AnyRegister reg)
michael@0: {
michael@0:     if (alloc->isRegister() && alloc->toRegister() == reg)
michael@0:         return true;
michael@0:     if (alloc->isUse()) {
michael@0:         const LUse *use = alloc->toUse();
michael@0:         if (use->policy() == LUse::FIXED) {
michael@0:             AnyRegister usedReg = GetFixedRegister(virtualRegisters[use->virtualRegister()], use);
michael@0:             if (usedReg == reg)
michael@0:                 return true;
michael@0:         }
michael@0:     }
michael@0:     return false;
michael@0: }
michael@0: 
michael@0: bool
michael@0: StupidAllocator::registerIsReserved(LInstruction *ins, AnyRegister reg)
michael@0: {
michael@0:     // Whether reg is already reserved for an input or output of ins.
michael@0:     for (LInstruction::InputIterator alloc(*ins); alloc.more(); alloc.next()) {
michael@0:         if (allocationRequiresRegister(*alloc, reg))
michael@0:             return true;
michael@0:     }
michael@0:     for (size_t i = 0; i < ins->numTemps(); i++) {
michael@0:         if (allocationRequiresRegister(ins->getTemp(i)->output(), reg))
michael@0:             return true;
michael@0:     }
michael@0:     for (size_t i = 0; i < ins->numDefs(); i++) {
michael@0:         if (allocationRequiresRegister(ins->getDef(i)->output(), reg))
michael@0:             return true;
michael@0:     }
michael@0:     return false;
michael@0: }
michael@0: 
michael@0: AnyRegister
michael@0: StupidAllocator::ensureHasRegister(LInstruction *ins, uint32_t vreg)
michael@0: {
michael@0:     // Ensure that vreg is held in a register before ins.
michael@0: 
michael@0:     // Check if the virtual register is already held in a physical register.
michael@0:     RegisterIndex existing = findExistingRegister(vreg);
michael@0:     if (existing != UINT32_MAX) {
michael@0:         if (registerIsReserved(ins, registers[existing].reg)) {
michael@0:             evictRegister(ins, existing);
michael@0:         } else {
michael@0:             registers[existing].age = ins->id();
michael@0:             return registers[existing].reg;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     RegisterIndex best = allocateRegister(ins, vreg);
michael@0:     loadRegister(ins, vreg, best, virtualRegisters[vreg]->type());
michael@0: 
michael@0:     return registers[best].reg;
michael@0: }
michael@0: 
michael@0: StupidAllocator::RegisterIndex
michael@0: StupidAllocator::allocateRegister(LInstruction *ins, uint32_t vreg)
michael@0: {
michael@0:     // Pick a register for vreg, evicting an existing register if necessary.
michael@0:     // Spill code will be placed before ins, and no existing allocated input
michael@0:     // for ins will be touched.
michael@0:     JS_ASSERT(ins);
michael@0: 
michael@0:     LDefinition *def = virtualRegisters[vreg];
michael@0:     JS_ASSERT(def);
michael@0: 
michael@0:     RegisterIndex best = UINT32_MAX;
michael@0: 
michael@0:     for (size_t i = 0; i < registerCount; i++) {
michael@0:         AnyRegister reg = registers[i].reg;
michael@0: 
michael@0:         if (reg.isFloat() != def->isFloatReg())
michael@0:             continue;
michael@0: 
michael@0:         // Skip the register if it is in use for an allocated input or output.
michael@0:         if (registerIsReserved(ins, reg))
michael@0:             continue;
michael@0: 
michael@0:         if (registers[i].vreg == MISSING_ALLOCATION ||
michael@0:             best == UINT32_MAX ||
michael@0:             registers[best].age > registers[i].age)
michael@0:         {
michael@0:             best = i;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     evictRegister(ins, best);
michael@0:     return best;
michael@0: }
michael@0: 
michael@0: void
michael@0: StupidAllocator::syncRegister(LInstruction *ins, RegisterIndex index)
michael@0: {
michael@0:     if (registers[index].dirty) {
michael@0:         LMoveGroup *input = getInputMoveGroup(ins->id());
michael@0:         LAllocation *source = new(alloc()) LAllocation(registers[index].reg);
michael@0: 
michael@0:         uint32_t existing = registers[index].vreg;
michael@0:         LAllocation *dest = stackLocation(existing);
michael@0:         input->addAfter(source, dest, registers[index].type);
michael@0: 
michael@0:         registers[index].dirty = false;
michael@0:     }
michael@0: }
michael@0: 
michael@0: void
michael@0: StupidAllocator::evictRegister(LInstruction *ins, RegisterIndex index)
michael@0: {
michael@0:     syncRegister(ins, index);
michael@0:     registers[index].set(MISSING_ALLOCATION);
michael@0: }
michael@0: 
michael@0: void
michael@0: StupidAllocator::loadRegister(LInstruction *ins, uint32_t vreg, RegisterIndex index, LDefinition::Type type)
michael@0: {
michael@0:     // Load a vreg from its stack location to a register.
michael@0:     LMoveGroup *input = getInputMoveGroup(ins->id());
michael@0:     LAllocation *source = stackLocation(vreg);
michael@0:     LAllocation *dest = new(alloc()) LAllocation(registers[index].reg);
michael@0:     input->addAfter(source, dest, type);
michael@0:     registers[index].set(vreg, ins);
michael@0:     registers[index].type = type;
michael@0: }
michael@0: 
michael@0: StupidAllocator::RegisterIndex
michael@0: StupidAllocator::findExistingRegister(uint32_t vreg)
michael@0: {
michael@0:     for (size_t i = 0; i < registerCount; i++) {
michael@0:         if (registers[i].vreg == vreg)
michael@0:             return i;
michael@0:     }
michael@0:     return UINT32_MAX;
michael@0: }
michael@0: 
michael@0: bool
michael@0: StupidAllocator::go()
michael@0: {
michael@0:     // This register allocator is intended to be as simple as possible, while
michael@0:     // still being complicated enough to share properties with more complicated
michael@0:     // allocators. Namely, physical registers may be used to carry virtual
michael@0:     // registers across LIR instructions, but not across basic blocks.
michael@0:     //
michael@0:     // This algorithm does not pay any attention to liveness. It is performed
michael@0:     // as a single forward pass through the basic blocks in the program. As
michael@0:     // virtual registers and temporaries are defined they are assigned physical
michael@0:     // registers, evicting existing allocations in an LRU fashion.
michael@0: 
michael@0:     // For virtual registers not carried in a register, a canonical spill
michael@0:     // location is used. Each vreg has a different spill location; since we do
michael@0:     // not track liveness we cannot determine that two vregs have disjoint
michael@0:     // lifetimes. Thus, the maximum stack height is the number of vregs (scaled
michael@0:     // by two on 32 bit platforms to allow storing double values).
michael@0:     graph.setLocalSlotCount(DefaultStackSlot(graph.numVirtualRegisters()));
michael@0: 
michael@0:     if (!init())
michael@0:         return false;
michael@0: 
michael@0:     for (size_t blockIndex = 0; blockIndex < graph.numBlocks(); blockIndex++) {
michael@0:         LBlock *block = graph.getBlock(blockIndex);
michael@0:         JS_ASSERT(block->mir()->id() == blockIndex);
michael@0: 
michael@0:         for (size_t i = 0; i < registerCount; i++)
michael@0:             registers[i].set(MISSING_ALLOCATION);
michael@0: 
michael@0:         for (LInstructionIterator iter = block->begin(); iter != block->end(); iter++) {
michael@0:             LInstruction *ins = *iter;
michael@0: 
michael@0:             if (ins == *block->rbegin())
michael@0:                 syncForBlockEnd(block, ins);
michael@0: 
michael@0:             allocateForInstruction(ins);
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: void
michael@0: StupidAllocator::syncForBlockEnd(LBlock *block, LInstruction *ins)
michael@0: {
michael@0:     // Sync any dirty registers, and update the synced state for phi nodes at
michael@0:     // each successor of a block. We cannot conflate the storage for phis with
michael@0:     // that of their inputs, as we cannot prove the live ranges of the phi and
michael@0:     // its input do not overlap. The values for the two may additionally be
michael@0:     // different, as the phi could be for the value of the input in a previous
michael@0:     // loop iteration.
michael@0: 
michael@0:     for (size_t i = 0; i < registerCount; i++)
michael@0:         syncRegister(ins, i);
michael@0: 
michael@0:     LMoveGroup *group = nullptr;
michael@0: 
michael@0:     MBasicBlock *successor = block->mir()->successorWithPhis();
michael@0:     if (successor) {
michael@0:         uint32_t position = block->mir()->positionInPhiSuccessor();
michael@0:         LBlock *lirsuccessor = graph.getBlock(successor->id());
michael@0:         for (size_t i = 0; i < lirsuccessor->numPhis(); i++) {
michael@0:             LPhi *phi = lirsuccessor->getPhi(i);
michael@0: 
michael@0:             uint32_t sourcevreg = phi->getOperand(position)->toUse()->virtualRegister();
michael@0:             uint32_t destvreg = phi->getDef(0)->virtualRegister();
michael@0: 
michael@0:             if (sourcevreg == destvreg)
michael@0:                 continue;
michael@0: 
michael@0:             LAllocation *source = stackLocation(sourcevreg);
michael@0:             LAllocation *dest = stackLocation(destvreg);
michael@0: 
michael@0:             if (!group) {
michael@0:                 // The moves we insert here need to happen simultaneously with
michael@0:                 // each other, yet after any existing moves before the instruction.
michael@0:                 LMoveGroup *input = getInputMoveGroup(ins->id());
michael@0:                 if (input->numMoves() == 0) {
michael@0:                     group = input;
michael@0:                 } else {
michael@0:                     group = LMoveGroup::New(alloc());
michael@0:                     block->insertAfter(input, group);
michael@0:                 }
michael@0:             }
michael@0: 
michael@0:             group->add(source, dest, phi->getDef(0)->type());
michael@0:         }
michael@0:     }
michael@0: }
michael@0: 
michael@0: void
michael@0: StupidAllocator::allocateForInstruction(LInstruction *ins)
michael@0: {
michael@0:     // Sync all registers before making a call.
michael@0:     if (ins->isCall()) {
michael@0:         for (size_t i = 0; i < registerCount; i++)
michael@0:             syncRegister(ins, i);
michael@0:     }
michael@0: 
michael@0:     // Allocate for inputs which are required to be in registers.
michael@0:     for (LInstruction::InputIterator alloc(*ins); alloc.more(); alloc.next()) {
michael@0:         if (!alloc->isUse())
michael@0:             continue;
michael@0:         LUse *use = alloc->toUse();
michael@0:         uint32_t vreg = use->virtualRegister();
michael@0:         if (use->policy() == LUse::REGISTER) {
michael@0:             AnyRegister reg = ensureHasRegister(ins, vreg);
michael@0:             alloc.replace(LAllocation(reg));
michael@0:         } else if (use->policy() == LUse::FIXED) {
michael@0:             AnyRegister reg = GetFixedRegister(virtualRegisters[vreg], use);
michael@0:             RegisterIndex index = registerIndex(reg);
michael@0:             if (registers[index].vreg != vreg) {
michael@0:                 evictRegister(ins, index);
michael@0:                 RegisterIndex existing = findExistingRegister(vreg);
michael@0:                 if (existing != UINT32_MAX)
michael@0:                     evictRegister(ins, existing);
michael@0:                 loadRegister(ins, vreg, index, virtualRegisters[vreg]->type());
michael@0:             }
michael@0:             alloc.replace(LAllocation(reg));
michael@0:         } else {
michael@0:             // Inputs which are not required to be in a register are not
michael@0:             // allocated until after temps/definitions, as the latter may need
michael@0:             // to evict registers which hold these inputs.
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     // Find registers to hold all temporaries and outputs of the instruction.
michael@0:     for (size_t i = 0; i < ins->numTemps(); i++) {
michael@0:         LDefinition *def = ins->getTemp(i);
michael@0:         if (!def->isBogusTemp())
michael@0:             allocateForDefinition(ins, def);
michael@0:     }
michael@0:     for (size_t i = 0; i < ins->numDefs(); i++) {
michael@0:         LDefinition *def = ins->getDef(i);
michael@0:         if (def->policy() != LDefinition::PASSTHROUGH)
michael@0:             allocateForDefinition(ins, def);
michael@0:     }
michael@0: 
michael@0:     // Allocate for remaining inputs which do not need to be in registers.
michael@0:     for (LInstruction::InputIterator alloc(*ins); alloc.more(); alloc.next()) {
michael@0:         if (!alloc->isUse())
michael@0:             continue;
michael@0:         LUse *use = alloc->toUse();
michael@0:         uint32_t vreg = use->virtualRegister();
michael@0:         JS_ASSERT(use->policy() != LUse::REGISTER && use->policy() != LUse::FIXED);
michael@0: 
michael@0:         RegisterIndex index = findExistingRegister(vreg);
michael@0:         if (index == UINT32_MAX) {
michael@0:             LAllocation *stack = stackLocation(use->virtualRegister());
michael@0:             alloc.replace(*stack);
michael@0:         } else {
michael@0:             registers[index].age = ins->id();
michael@0:             alloc.replace(LAllocation(registers[index].reg));
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     // If this is a call, evict all registers except for those holding outputs.
michael@0:     if (ins->isCall()) {
michael@0:         for (size_t i = 0; i < registerCount; i++) {
michael@0:             if (!registers[i].dirty)
michael@0:                 registers[i].set(MISSING_ALLOCATION);
michael@0:         }
michael@0:     }
michael@0: }
michael@0: 
michael@0: void
michael@0: StupidAllocator::allocateForDefinition(LInstruction *ins, LDefinition *def)
michael@0: {
michael@0:     uint32_t vreg = def->virtualRegister();
michael@0: 
michael@0:     CodePosition from;
michael@0:     if ((def->output()->isRegister() && def->policy() == LDefinition::PRESET) ||
michael@0:         def->policy() == LDefinition::MUST_REUSE_INPUT)
michael@0:     {
michael@0:         // Result will be in a specific register, spill any vreg held in
michael@0:         // that register before the instruction.
michael@0:         RegisterIndex index =
michael@0:             registerIndex(def->policy() == LDefinition::PRESET
michael@0:                           ? def->output()->toRegister()
michael@0:                           : ins->getOperand(def->getReusedInput())->toRegister());
michael@0:         evictRegister(ins, index);
michael@0:         registers[index].set(vreg, ins, true);
michael@0:         registers[index].type = virtualRegisters[vreg]->type();
michael@0:         def->setOutput(LAllocation(registers[index].reg));
michael@0:     } else if (def->policy() == LDefinition::PRESET) {
michael@0:         // The result must be a stack location.
michael@0:         def->setOutput(*stackLocation(vreg));
michael@0:     } else {
michael@0:         // Find a register to hold the result of the instruction.
michael@0:         RegisterIndex best = allocateRegister(ins, vreg);
michael@0:         registers[best].set(vreg, ins, true);
michael@0:         registers[best].type = virtualRegisters[vreg]->type();
michael@0:         def->setOutput(LAllocation(registers[best].reg));
michael@0:     }
michael@0: }