lib/CodeGen/RegAllocSimple.cpp

   1 //===-- RegAllocSimple.cpp - A simple generic register allocator --- ------===//
   2 //
   3 // This file implements a simple register allocator. *Very* simple.
   4 //
   5 //===----------------------------------------------------------------------===//
   6
   7 #include "llvm/CodeGen/MachineFunction.h"
   8 #include "llvm/CodeGen/MachineInstr.h"
   9 #include "llvm/Target/MachineInstrInfo.h"
  10 #include "llvm/Target/TargetMachine.h"
  11 #include "Support/Statistic.h"
  12 #include <iostream>
  13 #include <set>
  14
  15 /// PhysRegClassMap - Construct a mapping of physical register numbers to their
  16 /// register classes.
  17 ///
  18 /// NOTE: This class will eventually be pulled out to somewhere shared.
  19 ///
  20 class PhysRegClassMap {
  21   std::map<unsigned, const TargetRegisterClass*> PhysReg2RegClassMap;
  22 public:
  23   PhysRegClassMap(const MRegisterInfo *RI) {
  24     for (MRegisterInfo::const_iterator I = RI->regclass_begin(),
  25            E = RI->regclass_end(); I != E; ++I)
  26       for (unsigned i=0; i < (*I)->getNumRegs(); ++i)
  27         PhysReg2RegClassMap[(*I)->getRegister(i)] = *I;
  28   }
  29
  30   const TargetRegisterClass *operator[](unsigned Reg) {
  31     assert(PhysReg2RegClassMap[Reg] && "Register is not a known physreg!");
  32     return PhysReg2RegClassMap[Reg];
  33   }
  34
  35   const TargetRegisterClass *get(unsigned Reg) { return operator[](Reg); }
  36 };
  37
  38
  39 namespace {
  40   Statistic<> NumSpilled ("ra-simple", "Number of registers spilled");
  41   Statistic<> NumReloaded("ra-simple", "Number of registers reloaded");
  42
  43   class RegAllocSimple : public FunctionPass {
  44     TargetMachine &TM;
  45     MachineFunction *MF;
  46     const MRegisterInfo *RegInfo;
  47     unsigned NumBytesAllocated;
  48
  49     // Maps SSA Regs => offsets on the stack where these values are stored
  50     std::map<unsigned, unsigned> VirtReg2OffsetMap;
  51
  52     // Maps physical register to their register classes
  53     PhysRegClassMap PhysRegClasses;
  54
  55     // RegsUsed - Keep track of what registers are currently in use.
  56     std::set<unsigned> RegsUsed;
  57
  58     // RegClassIdx - Maps RegClass => which index we can take a register
  59     // from. Since this is a simple register allocator, when we need a register
  60     // of a certain class, we just take the next available one.
  61     std::map<const TargetRegisterClass*, unsigned> RegClassIdx;
  62
  63   public:
  64
  65     RegAllocSimple(TargetMachine &tm)
  66       : TM(tm), RegInfo(tm.getRegisterInfo()), PhysRegClasses(RegInfo) {
  67       RegsUsed.insert(RegInfo->getFramePointer());
  68       RegsUsed.insert(RegInfo->getStackPointer());
  69
  70       cleanupAfterFunction();
  71     }
  72
  73     bool runOnFunction(Function &Fn) {
  74       return runOnMachineFunction(MachineFunction::get(&Fn));
  75     }
  76
  77     virtual const char *getPassName() const {
  78       return "Simple Register Allocator";
  79     }
  80
  81   private:
  82     /// runOnMachineFunction - Register allocate the whole function
  83     bool runOnMachineFunction(MachineFunction &Fn);
  84
  85     /// AllocateBasicBlock - Register allocate the specified basic block.
  86     void AllocateBasicBlock(MachineBasicBlock &MBB);
  87
  88     /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions
  89     /// in predecessor basic blocks.
  90     void EliminatePHINodes(MachineBasicBlock &MBB);
  91
  92
  93     bool isAvailableReg(unsigned Reg) {
  94       // assert(Reg < MRegisterInfo::FirstVirtualReg && "...");
  95       return RegsUsed.find(Reg) == RegsUsed.end();
  96     }
  97
  98     /// allocateStackSpaceFor - This allocates space for the specified virtual
  99     /// register to be held on the stack.
 100     unsigned allocateStackSpaceFor(unsigned VirtReg,
 101                                    const TargetRegisterClass *regClass);
 102
 103     /// Given a virtual register, returns a physical register that is currently
 104     /// unused.
 105     ///
 106     /// Side effect: marks that register as being used until manually cleared
 107     ///
 108     unsigned getFreeReg(unsigned virtualReg);
 109
 110     /// Returns all `borrowed' registers back to the free pool
 111     void clearAllRegs() {
 112       RegClassIdx.clear();
 113     }
 114
 115     /// Invalidates any references, real or implicit, to physical registers
 116     ///
 117     void invalidatePhysRegs(const MachineInstr *MI) {
 118       unsigned Opcode = MI->getOpcode();
 119       const MachineInstrDescriptor &Desc = TM.getInstrInfo().get(Opcode);
 120       const unsigned *regs = Desc.ImplicitUses;
 121       while (*regs)
 122         RegsUsed.insert(*regs++);
 123
 124       regs = Desc.ImplicitDefs;
 125       while (*regs)
 126         RegsUsed.insert(*regs++);
 127     }
 128
 129     void cleanupAfterFunction() {
 130       VirtReg2OffsetMap.clear();
 131       NumBytesAllocated = 4;   // FIXME: This is X86 specific
 132     }
 133
 134     /// Moves value from memory into that register
 135     MachineBasicBlock::iterator
 136     moveUseToReg (MachineBasicBlock &MBB,
 137                   MachineBasicBlock::iterator I, unsigned VirtReg,
 138                   unsigned &PhysReg);
 139
 140     /// Saves reg value on the stack (maps virtual register to stack value)
 141     MachineBasicBlock::iterator
 142     saveVirtRegToStack (MachineBasicBlock &MBB,
 143                         MachineBasicBlock::iterator I, unsigned VirtReg,
 144                         unsigned PhysReg);
 145   };
 146
 147 }
 148
 149 /// allocateStackSpaceFor - This allocates space for the specified virtual
 150 /// register to be held on the stack.
 151 unsigned RegAllocSimple::allocateStackSpaceFor(unsigned VirtReg,
 152                                             const TargetRegisterClass *regClass)
 153 {
 154   if (VirtReg2OffsetMap.find(VirtReg) == VirtReg2OffsetMap.end()) {
 155     unsigned RegSize = regClass->getDataSize();
 156
 157     // Align NumBytesAllocated.  We should be using TargetData alignment stuff
 158     // to determine this, but we don't know the LLVM type associated with the
 159     // virtual register.  Instead, just align to a multiple of the size for now.
 160     NumBytesAllocated += RegSize-1;
 161     NumBytesAllocated = NumBytesAllocated/RegSize*RegSize;
 162
 163     // Assign the slot...
 164     VirtReg2OffsetMap[VirtReg] = NumBytesAllocated;
 165
 166     // Reserve the space!
 167     NumBytesAllocated += RegSize;
 168   }
 169   return VirtReg2OffsetMap[VirtReg];
 170 }
 171
 172 unsigned RegAllocSimple::getFreeReg(unsigned virtualReg) {
 173   const TargetRegisterClass* regClass = MF->getRegClass(virtualReg);
 174   unsigned physReg;
 175   assert(regClass);
 176   if (RegClassIdx.find(regClass) != RegClassIdx.end()) {
 177     unsigned regIdx = RegClassIdx[regClass]++;
 178     assert(regIdx < regClass->getNumRegs() && "Not enough registers!");
 179     physReg = regClass->getRegister(regIdx);
 180   } else {
 181     physReg = regClass->getRegister(0);
 182     // assert(physReg < regClass->getNumRegs() && "No registers in class!");
 183     RegClassIdx[regClass] = 1;
 184   }
 185
 186   if (isAvailableReg(physReg))
 187     return physReg;
 188   else
 189     return getFreeReg(virtualReg);
 190 }
 191
 192 MachineBasicBlock::iterator
 193 RegAllocSimple::moveUseToReg (MachineBasicBlock &MBB,
 194                               MachineBasicBlock::iterator I,
 195                               unsigned VirtReg, unsigned &PhysReg)
 196 {
 197   const TargetRegisterClass* regClass = MF->getRegClass(VirtReg);
 198   unsigned stackOffset = allocateStackSpaceFor(VirtReg, regClass);
 199   PhysReg = getFreeReg(VirtReg);
 200
 201   // Add move instruction(s)
 202   ++NumReloaded;
 203   return RegInfo->loadRegOffset2Reg(MBB, I, PhysReg,
 204                                     RegInfo->getFramePointer(),
 205                                     -stackOffset, regClass->getDataSize());
 206 }
 207
 208 MachineBasicBlock::iterator
 209 RegAllocSimple::saveVirtRegToStack (MachineBasicBlock &MBB,
 210                                     MachineBasicBlock::iterator I,
 211                                     unsigned VirtReg, unsigned PhysReg)
 212 {
 213   const TargetRegisterClass* regClass = MF->getRegClass(VirtReg);
 214   unsigned stackOffset = allocateStackSpaceFor(VirtReg, regClass);
 215
 216   // Add move instruction(s)
 217   ++NumSpilled;
 218   return RegInfo->storeReg2RegOffset(MBB, I, PhysReg,
 219                                      RegInfo->getFramePointer(),
 220                                      -stackOffset, regClass->getDataSize());
 221 }
 222
 223
 224 /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions in
 225 /// predecessor basic blocks.
 226 void RegAllocSimple::EliminatePHINodes(MachineBasicBlock &MBB) {
 227   const MachineInstrInfo &MII = TM.getInstrInfo();
 228
 229   while (MBB.front()->getOpcode() == 0) {
 230     MachineInstr *MI = MBB.front();
 231     // Unlink the PHI node from the basic block... but don't delete the PHI
 232     MBB.erase(MBB.begin());
 233
 234     // a preliminary pass that will invalidate any registers that
 235     // are used by the instruction (including implicit uses)
 236     invalidatePhysRegs(MI);
 237
 238     DEBUG(std::cerr << "num invalid regs: " << RegsUsed.size() << "\n");
 239     DEBUG(std::cerr << "num ops: " << MI->getNumOperands() << "\n");
 240     MachineOperand &targetReg = MI->getOperand(0);
 241
 242     // If it's a virtual register, allocate a physical one otherwise, just use
 243     // whatever register is there now note: it MUST be a register -- we're
 244     // assigning to it!
 245     //
 246     unsigned virtualReg = (unsigned) targetReg.getAllocatedRegNum();
 247     unsigned physReg;
 248     if (targetReg.isVirtualRegister()) {
 249       physReg = getFreeReg(virtualReg);
 250     } else {
 251       physReg = virtualReg;
 252     }
 253
 254     // Find the register class of the target register: should be the
 255     // same as the values we're trying to store there
 256     const TargetRegisterClass* regClass = PhysRegClasses[physReg];
 257     assert(regClass && "Target register class not found!");
 258     unsigned dataSize = regClass->getDataSize();
 259
 260     for (int i = MI->getNumOperands() - 1; i >= 2; i-=2) {
 261       MachineOperand &opVal = MI->getOperand(i-1);
 262
 263       // Get the MachineBasicBlock equivalent of the BasicBlock that is the
 264       // source path the phi
 265       MachineBasicBlock &opBlock = *MI->getOperand(i).getMachineBasicBlock();
 266
 267       // Check to make sure we haven't already emitted the copy for this block.
 268       // This can happen because PHI nodes may have multiple entries for the
 269       // same basic block.  It doesn't matter which entry we use though, because
 270       // all incoming values are guaranteed to be the same for a particular bb.
 271       //
 272       // Note that this is N^2 in the number of phi node entries, but since the
 273       // # of entries is tiny, this is not a problem.
 274       //
 275       bool HaveNotEmitted = true;
 276       for (int op = MI->getNumOperands() - 1; op != i; op -= 2)
 277         if (&opBlock == MI->getOperand(op).getMachineBasicBlock()) {
 278           HaveNotEmitted = false;
 279           break;
 280         }
 281
 282       if (HaveNotEmitted) {
 283         MachineBasicBlock::iterator opI = opBlock.end();
 284         MachineInstr *opMI = *--opI;
 285
 286         // must backtrack over ALL the branches in the previous block
 287         while (MII.isBranch(opMI->getOpcode()) && opI != opBlock.begin())
 288           opMI = *--opI;
 289
 290         // move back to the first branch instruction so new instructions
 291         // are inserted right in front of it and not in front of a non-branch
 292         if (!MII.isBranch(opMI->getOpcode()))
 293           ++opI;
 294
 295         // Retrieve the constant value from this op, move it to target
 296         // register of the phi
 297         if (opVal.isImmediate()) {
 298           opI = RegInfo->moveImm2Reg(opBlock, opI, physReg,
 299                                      (unsigned) opVal.getImmedValue(),
 300                                      dataSize);
 301         } else {
 302           // Allocate a physical register and add a move in the BB
 303           unsigned opVirtualReg = opVal.getAllocatedRegNum();
 304           unsigned opPhysReg;
 305           opI = moveUseToReg(opBlock, opI, opVirtualReg, physReg);
 306
 307         }
 308
 309         // Save that register value to the stack of the TARGET REG
 310         saveVirtRegToStack(opBlock, opI, virtualReg, physReg);
 311       }
 312
 313       // make regs available to other instructions
 314       clearAllRegs();
 315     }
 316
 317     // really delete the instruction
 318     delete MI;
 319   }
 320 }
 321
 322
 323 void RegAllocSimple::AllocateBasicBlock(MachineBasicBlock &MBB) {
 324   // Handle PHI instructions specially: add moves to each pred block
 325   EliminatePHINodes(MBB);
 326
 327   // loop over each instruction
 328   for (MachineBasicBlock::iterator I = MBB.begin(); I != MBB.end(); ++I) {
 329     // Made to combat the incorrect allocation of r2 = add r1, r1
 330     std::map<unsigned, unsigned> VirtReg2PhysRegMap;
 331
 332     MachineInstr *MI = *I;
 333
 334     // a preliminary pass that will invalidate any registers that
 335     // are used by the instruction (including implicit uses)
 336     invalidatePhysRegs(MI);
 337
 338     // Loop over uses, move from memory into registers
 339     for (int i = MI->getNumOperands() - 1; i >= 0; --i) {
 340       MachineOperand &op = MI->getOperand(i);
 341
 342       if (op.isVirtualRegister()) {
 343         unsigned virtualReg = (unsigned) op.getAllocatedRegNum();
 344         DEBUG(std::cerr << "op: " << op << "\n");
 345         DEBUG(std::cerr << "\t inst[" << i << "]: ";
 346               MI->print(std::cerr, TM));
 347
 348         // make sure the same virtual register maps to the same physical
 349         // register in any given instruction
 350         unsigned physReg;
 351         if (VirtReg2PhysRegMap.find(virtualReg) != VirtReg2PhysRegMap.end()) {
 352           physReg = VirtReg2PhysRegMap[virtualReg];
 353         } else {
 354           if (op.opIsDef()) {
 355             if (TM.getInstrInfo().isTwoAddrInstr(MI->getOpcode()) && i == 0) {
 356               // must be same register number as the first operand
 357               // This maps a = b + c into b += c, and saves b into a's spot
 358               assert(MI->getOperand(1).isRegister()  &&
 359                      MI->getOperand(1).getAllocatedRegNum() &&
 360                      MF->getRegClass(virtualReg) ==
 361                        PhysRegClasses[MI->getOperand(1).getAllocatedRegNum()] &&
 362                      "Two address instruction invalid!");
 363
 364               physReg = MI->getOperand(1).getAllocatedRegNum();
 365             } else {
 366               physReg = getFreeReg(virtualReg);
 367             }
 368             MachineBasicBlock::iterator J = I;
 369             J = saveVirtRegToStack(MBB, ++J, virtualReg, physReg);
 370             I = --J;
 371           } else {
 372             I = moveUseToReg(MBB, I, virtualReg, physReg);
 373           }
 374           VirtReg2PhysRegMap[virtualReg] = physReg;
 375         }
 376         MI->SetMachineOperandReg(i, physReg);
 377         DEBUG(std::cerr << "virt: " << virtualReg <<
 378               ", phys: " << op.getAllocatedRegNum() << "\n");
 379       }
 380     }
 381     clearAllRegs();
 382   }
 383 }
 384
 385 /// runOnMachineFunction - Register allocate the whole function
 386 ///
 387 bool RegAllocSimple::runOnMachineFunction(MachineFunction &Fn) {
 388   DEBUG(std::cerr << "Machine Function " << "\n");
 389   MF = &Fn;
 390
 391   for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();
 392        MBB != MBBe; ++MBB)
 393     AllocateBasicBlock(*MBB);
 394
 395   // add prologue we should preserve callee-save registers...
 396   RegInfo->emitPrologue(Fn, NumBytesAllocated);
 397
 398   const MachineInstrInfo &MII = TM.getInstrInfo();
 399
 400   // add epilogue to restore the callee-save registers
 401   // loop over the basic block
 402   for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();
 403        MBB != MBBe; ++MBB) {
 404     // check if last instruction is a RET
 405     if (MII.isReturn(MBB->back()->getOpcode())) {
 406       // this block has a return instruction, add epilogue
 407       RegInfo->emitEpilogue(*MBB, NumBytesAllocated);
 408     }
 409   }
 410
 411   cleanupAfterFunction();
 412   return false;  // We never modify the LLVM itself.
 413 }
 414
 415 Pass *createSimpleX86RegisterAllocator(TargetMachine &TM) {
 416   return new RegAllocSimple(TM);
 417 }