{"header":{"message":"Implement base algorithm","description":null,"timestamp":"2024-04-30T02:54:09.725289086Z","authors":[{}]},"hash":"MFTKDEMKGE2MQ2KAYZAOWNGDLG4T3FX4SUIJGTQ4ZO65SCTRZ3NAC","authors":[{"key":"HEoBdDazRMaEHRZYU3bhWF1H1nw4HPwSGacwHU3HCqdH"}],"deps":{"hashes":[["MFTKDEMKGE2MQ2KAYZAOWNGDLG4T3FX4SUIJGTQ4ZO65SCTRZ3NAC","Implement base algorithm"],["AA",null],["7OVOGA6QKF5OJXOT6VP4Y6GOFI2ZZSBBK3QNK7CPFGN74F7O6HAAC","Import LLVM @ 15.0.7"]],"deps":["7OVOGA6QKF5OJXOT6VP4Y6GOFI2ZZSBBK3QNK7CPFGN74F7O6HAAC"],"known":[]},"hunks":[{"FileAdd":{"meta":{"basename":"RegAllocSimple.cpp","metadata":0},"context":[{"change":2,"pos":589763340}],"contents":[{"Add":"//===----------------------------------------------------------------------===//"},{"Add":"//"},{"Add":"/// A register allocator simplified from RegAllocFast.cpp"},{"Add":"//"},{"Add":"//===----------------------------------------------------------------------===//"},{"Add":""},{"Add":"#include \"llvm/ADT/Statistic.h\""},{"Add":"#include \"llvm/ADT/SmallSet.h\""},{"Add":"#include \"llvm/ADT/DenseMap.h\""},{"Add":"#include \"llvm/ADT/STLExtras.h\""},{"Add":""},{"Add":"#include \"llvm/CodeGen/MachineFunctionPass.h\""},{"Add":"#include \"llvm/CodeGen/MachineRegisterInfo.h\""},{"Add":"#include \"llvm/CodeGen/RegAllocRegistry.h\""},{"Add":"#include \"llvm/CodeGen/RegisterClassInfo.h\""},{"Add":"#include \"llvm/CodeGen/TargetInstrInfo.h\""},{"Add":"#include \"llvm/CodeGen/MachineFrameInfo.h\""},{"Add":"#include \"llvm/InitializePasses.h\""},{"Add":"#include \"llvm/Pass.h\""},{"Add":""},{"Add":"#include \"llvm/CodeGen/LiveIntervals.h\""},{"Add":"#include \"llvm/CodeGen/SlotIndexes.h\""},{"Add":""},{"Add":"using namespace llvm;"},{"Add":""},{"Add":"#define DEBUG_TYPE \"regalloc\""},{"Add":""},{"Add":"STATISTIC(NumStores, \"Number of stores (spills) added\");"},{"Add":"STATISTIC(NumLoads , \"Number of loads (reloads) added\");"},{"Add":""},{"Add":"namespace {"},{"Add":"/// This is class where you will implement your register allocator in"},{"Add":"class RegAllocSimple : public MachineFunctionPass {"},{"Add":"public:"},{"Add":" static char ID;"},{"Add":" RegAllocSimple() : MachineFunctionPass(ID) {}"},{"Add":""},{"Add":"private:"},{"Add":" /// Some information that might be useful for register allocation"},{"Add":" /// They are initialized in runOnMachineFunction"},{"Add":" MachineFrameInfo *MFI;"},{"Add":" MachineRegisterInfo *MRI;"},{"Add":" TargetRegisterInfo const *TRI;"},{"Add":" TargetInstrInfo const *TII;"},{"Add":" RegisterClassInfo RegClassInfo;"},{"Add":""},{"Add":" // Virtual register to physical register mapping for the current block"},{"Add":" DenseMap LiveVirtRegs;"},{"Add":" // Physical register to virtual register mapping for the current block"},{"Add":" DenseMap LivePhysRegs;"},{"Add":" // Virtual register to stack slot mapping for the current block"},{"Add":" DenseMap LiveSpills;"},{"Add":""},{"Add":" // Physical registers used in the current instruction"},{"Add":" SmallSet UsedInInstr;"},{"Add":""},{"Add":"public:"},{"Add":" StringRef getPassName() const override { return \"Simple Register Allocator\"; }"},{"Add":""},{"Add":" void getAnalysisUsage(AnalysisUsage &AU) const override "},{"Add":" {"},{"Add":" AU.setPreservesCFG();"},{"Add":" // At -O1/-O2, llc fails to schedule some required passes if this pass"},{"Add":" // does not preserve these anlyses; these are preserved by recomputing"},{"Add":" // them at the end of runOnFunction(), you can safely ignore these"},{"Add":" AU.addRequired();"},{"Add":" AU.addPreserved();"},{"Add":" AU.addRequired();"},{"Add":" AU.addPreserved();"},{"Add":" MachineFunctionPass::getAnalysisUsage(AU);"},{"Add":" }"},{"Add":""},{"Add":" /// Ask the Machine IR verifier to check some simple properties"},{"Add":" /// Enabled with the -verify-machineinstrs flag in llc"},{"Add":" MachineFunctionProperties getRequiredProperties() const override "},{"Add":" {"},{"Add":" return MachineFunctionProperties().set("},{"Add":" MachineFunctionProperties::Property::NoPHIs);"},{"Add":" }"},{"Add":""},{"Add":" MachineFunctionProperties getSetProperties() const override "},{"Add":" {"},{"Add":" return MachineFunctionProperties().set("},{"Add":" MachineFunctionProperties::Property::NoVRegs);"},{"Add":" }"},{"Add":""},{"Add":" MachineFunctionProperties getClearedProperties() const override "},{"Add":" {"},{"Add":" return MachineFunctionProperties().set("},{"Add":" MachineFunctionProperties::Property::IsSSA);"},{"Add":" }"},{"Add":""},{"Add":"private:"},{"Add":""},{"Add":" /// Allocate physical register for virtual register operand"},{"Add":" void allocateOperand(MachineOperand &MO, bool const isUse) "},{"Add":" {"},{"Add":" // If we've already allocated a phys register, we don't need to do anything"},{"Add":" auto it = LiveVirtRegs.find(MO);"},{"Add":" if (it != LiveVirtRegs.end()) {"},{"Add":" return;"},{"Add":" }"},{"Add":""},{"Add":" // Get a list of phys registers that can hold the operand in preferred order"},{"Add":" auto* RC = MRI->getRegClass(MO.getReg());"},{"Add":" auto AllocOrder = RegClassInfo.getOrder(RC);"},{"Add":""},{"Add":" MCPhysReg Reg = [AllocOrder, this]() {"},{"Add":" auto const regIsUsed = [this](MCPhysReg const& Reg){ return this->LivePhysRegs.find(Reg) != this->LivePhysRegs.end(); };"},{"Add":" auto const regIsSpillable = [this](MCPhysReg const& Reg){ return this->UsedInInstr.contains(Reg); };"},{"Add":" "},{"Add":" auto unusedPhysRegs = AllocOrder.drop_while(regIsUsed);"},{"Add":" if (unusedPhysRegs.empty()) {"},{"Add":" auto spillablePhysRegs = AllocOrder.drop_while(regIsSpillable);"},{"Add":" MCPhysReg spilled = spillablePhysRegs.front();"},{"Add":" auto virt_spilled = this->LivePhysRegs.find(spilled);"},{"Add":" assert(virt_spilled != this->LivePhysRegs.end() && \"Attempting to spill unbound physical register\");"},{"Add":""},{"Add":" this->spill(virt_spilled->second);"},{"Add":" return spilled;"},{"Add":" } else {"},{"Add":" return unusedPhysRegs.front();"},{"Add":" }"},{"Add":" }();"},{"Add":""},{"Add":" // If we are using a virtual register and it's not already live,"},{"Add":" // it must be spilled, so we reload it here."},{"Add":" if (isUse) {"},{"Add":" reload(MO, Reg);"},{"Add":" }"},{"Add":""},{"Add":" bindPhysReg(MO, Reg);"},{"Add":" UsedInInstr.insert(Reg);"},{"Add":" LiveVirtRegs.insert({MO, Reg});"},{"Add":" LivePhysRegs.insert({Reg, MO});"},{"Add":" }"},{"Add":""},{"Add":" void allocateInstruction(MachineInstr &MI) "},{"Add":" {"},{"Add":" static SmallVector Uses;"},{"Add":" static SmallVector RegMask;"},{"Add":" static SmallVector Defs;"},{"Add":" // We haven't allocated any physical registers yet"},{"Add":" UsedInInstr.clear();"},{"Add":" Uses.clear();"},{"Add":" RegMask.clear();"},{"Add":" Defs.clear();"},{"Add":""},{"Add":" // Split the operands into the categories we care about"},{"Add":" for (auto& MO: MI.operands()) {"},{"Add":" if (MO.isUse())"},{"Add":" Uses.emplace_back(MO);"},{"Add":" if (MO.isRegMask())"},{"Add":" RegMask.emplace_back(MO);"},{"Add":" if (MO.isDef())"},{"Add":" Defs.emplace_back(MO);"},{"Add":" }"},{"Add":""},{"Add":" auto const allocUse = [this](MachineOperand &MO){ this->allocateOperand(MO, true); };"},{"Add":" auto const allocDef = [this](MachineOperand &MO){ this->allocateOperand(MO, false); };"},{"Add":" "},{"Add":" // Allocate uses first"},{"Add":" for_each(Uses, allocUse);"},{"Add":""},{"Add":" // Spill all clobbered regs before a call"},{"Add":" for(auto& MO: RegMask) {"},{"Add":" for (auto &[O, R]: LiveVirtRegs)"},{"Add":" if (MO.clobbersPhysReg(R)) {"},{"Add":" spill(O);"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" // Allocate defs"},{"Add":" for_each(Defs, allocDef);"},{"Add":" }"},{"Add":""},{"Add":" void allocateBasicBlock(MachineBasicBlock &MBB) "},{"Add":" {"},{"Add":" // We haven't allocated any regs yet"},{"Add":" LiveVirtRegs.clear();"},{"Add":""},{"Add":" // Allocate each instruction"},{"Add":" for (auto &MI: MBB) {"},{"Add":" allocateInstruction(MI);"},{"Add":""},{"Add":" if (MI.isReturn())"},{"Add":" return; // We don't need to spill for returns"},{"Add":" }"},{"Add":" // Spill all live regs at the end"},{"Add":" for (auto &[O, _]: LiveVirtRegs) {"},{"Add":" spill(O);"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" bool runOnMachineFunction(MachineFunction &MF) override "},{"Add":" {"},{"Add":" // Get some useful information about the target"},{"Add":" MRI = &MF.getRegInfo();"},{"Add":" const TargetSubtargetInfo &STI = MF.getSubtarget();"},{"Add":" TRI = STI.getRegisterInfo();"},{"Add":" TII = STI.getInstrInfo();"},{"Add":" MFI = &MF.getFrameInfo();"},{"Add":" MRI->freezeReservedRegs(MF);"},{"Add":" RegClassInfo.runOnMachineFunction(MF);"},{"Add":""},{"Add":" // Allocate each basic block locally"},{"Add":" for (MachineBasicBlock &MBB : MF) {"},{"Add":" allocateBasicBlock(MBB);"},{"Add":" }"},{"Add":""},{"Add":" MRI->clearVirtRegs();"},{"Add":""},{"Add":" // Recompute the analyses that we marked as preserved above, you can"},{"Add":" // safely ignore this code"},{"Add":" SlotIndexes& SI = getAnalysis();"},{"Add":" SI.releaseMemory();"},{"Add":" SI.runOnMachineFunction(MF);"},{"Add":""},{"Add":" LiveIntervals& LI = getAnalysis();"},{"Add":" LI.releaseMemory();"},{"Add":" LI.runOnMachineFunction(MF);"},{"Add":""},{"Add":" return true;"},{"Add":" }"},{"Add":""},{"Add":" void bindPhysReg(MachineOperand &MO, MCPhysReg Reg)"},{"Add":" {"},{"Add":" auto idx = MO.getSubReg();"},{"Add":" if (idx) {"},{"Add":" Reg = TRI->getSubReg(Reg, idx);"},{"Add":" MO.setSubReg(0);"},{"Add":" }"},{"Add":" MO.setReg(Reg);"},{"Add":" if (MO.isKill())"},{"Add":" MO.setIsKill(false);"},{"Add":" else if (MO.isDead())"},{"Add":" MO.setIsDead(false);"},{"Add":" MO.setIsRenamable();"},{"Add":" }"},{"Add":""},{"Add":" void spill(MachineOperand &MO)"},{"Add":" {"},{"Add":" assert(MO.getReg().isPhysical() && \"Cannot spill something that is not a physical register\");"},{"Add":""},{"Add":" ++NumStores;"},{"Add":" // Clear the use"},{"Add":" LiveVirtRegs.erase(MO);"},{"Add":" LivePhysRegs.erase(MO.getReg());"},{"Add":" UsedInInstr.erase(MO.getReg());"},{"Add":""},{"Add":" // Get the stack slot to spill into"},{"Add":" auto* RC = MRI->getRegClass(MO.getReg());"},{"Add":" auto slot = MFI->CreateSpillStackObject(TRI->getSpillSize(*RC), TRI->getSpillAlign(*RC));"},{"Add":" "},{"Add":" // Spill the register"},{"Add":" TII->storeRegToStackSlot(*MO.getMBB(), MO.getMBB()->begin(), MO.getReg(), MO.isKill(), slot, RC, TRI); "},{"Add":""},{"Add":" LiveSpills.insert({MO, slot});"},{"Add":" }"},{"Add":""},{"Add":" void reload(MachineOperand &MO, MCPhysReg Dest)"},{"Add":" {"},{"Add":" assert(MO.getReg().isStack() && \"Cannot reload something that is not a stack slot\");"},{"Add":""},{"Add":" ++NumLoads;"},{"Add":" auto* RC = MRI->getRegClass(MO.getReg());"},{"Add":" auto slot = LiveSpills.find(MO);"},{"Add":" assert(slot != LiveSpills.end() && \"Did not find spill slot to reload\");"},{"Add":""},{"Add":" TII->loadRegFromStackSlot(*MO.getMBB(), MO.getMBB()->begin(), Dest, slot->second, RC, TRI);"},{"Add":""},{"Add":" LiveSpills.erase(MO);"},{"Add":" }"},{"Add":"};"},{"Add":"} // namespace"},{"Add":""},{"Add":"/// Create the initializer and register the pass"},{"Add":"char RegAllocSimple::ID = 0;"},{"Add":"FunctionPass *llvm::createSimpleRegisterAllocator() { return new RegAllocSimple(); }"},{"Add":"INITIALIZE_PASS(RegAllocSimple, \"regallocsimple\", \"Simple Register Allocator\", false, false)"},{"Add":"static RegisterRegAlloc simpleRegAlloc(\"simple\", \"simple register allocator\", createSimpleRegisterAllocator);"}]}}],"owner":"nuudlman","repo":"llvm","token":"sfOiKXlCFOM03d8TtmSLd05gPYV9Ar3BVdV615AotPc=","login":null}

…

Dependencies

Change contents