LLVM-RegisterAllocation The difference between defineVirtReg and definePhysReg

  In the Register allocation pass, there are two kinds of registers which could be deal with. Physical Register is represented the register of the real machine. Virtual register is represented the register which are not real one. The virtual register is an assumption in IR representation for making register allocation easily. One of target of register allocation pass is to transform the virtual register to physical register.  When defining physical register or virtual register, there are some different implementation in these functions.

In the definePhysReg, checking the state of physical register (see whether it is free or represented by one virtual register). If it is allocated to virtual register (it is possibly been used in the last instruction), we have to spill the value to the memory. Therefore, we create the instruction to store the value to memory, and set the physical register reserved for the instruction.

void RAFast::definePhysReg(MachineInstr *MI, unsigned PhysReg,
00408                            RegState NewState) {
00409   markRegUsedInInstr(PhysReg);
00410   switch (unsigned VirtReg = PhysRegState[PhysReg]) {
00411   case regDisabled:
00412     break;
00413   default:
00414     spillVirtReg(MI, VirtReg);
00415     // Fall through.
00416   case regFree:
00417   case regReserved:
00418     PhysRegState[PhysReg] = NewState;
00419     return;
00420   }
00421 
00422   // This is a disabled register, disable all aliases.
00423   PhysRegState[PhysReg] = NewState;
00424   for (MCRegAliasIterator AI(PhysReg, TRI, false); AI.isValid(); ++AI) {
00425     unsigned Alias = *AI;
00426     switch (unsigned VirtReg = PhysRegState[Alias]) {
00427     case regDisabled:
00428       break;
00429     default:
00430       spillVirtReg(MI, VirtReg);
00431       // Fall through.
00432     case regFree:
00433     case regReserved:
00434       PhysRegState[Alias] = regDisabled;
00435       if (TRI->isSuperRegister(PhysReg, Alias))
00436         return;
00437       break;
00438     }
00439   } 

                           

defineVirtReg is a little bit interesting, because it will map the virtual register to physical register. It firstly insert the new livereg to LiveRegMap, and know whether this is the new virtual register. LiveReg is the struct which contain the information about which physical register is held in the virtual register. LiveRegMap is the sparseSet to store LiveReg structs and track the available physical register. 

struct LiveReg {
00071       MachineInstr *LastUse;    // Last instr to use reg.
00072       unsigned VirtReg;         // Virtual register number.
00073       unsigned PhysReg;         // Currently held here.
00074       unsigned short LastOpNum; // OpNum on LastUse.
00075       bool Dirty;               // Register needs spill.
00076 
00077       explicit LiveReg(unsigned v)
00078         : LastUse(nullptr), VirtReg(v), PhysReg(0), LastOpNum(0), Dirty(false){}
00079 
00080       unsigned getSparseSetIndex() const {
00081         return TargetRegisterInfo::virtReg2Index(VirtReg);
00082       }
00083     };

  

If the LiveReg is new, it would allocate the physical register to the virtual register. Otherwise, it would determine whether the last use is the same instruction. if the last use is not the same instruction, it should kill it.

 RAFast::LiveRegMap::iterator
00590 RAFast::defineVirtReg(MachineInstr *MI, unsigned OpNum,
00591                       unsigned VirtReg, unsigned Hint) {
00592   assert(TargetRegisterInfo::isVirtualRegister(VirtReg) &&
00593          "Not a virtual register");
00594   LiveRegMap::iterator LRI;
00595   bool New;
00596   std::tie(LRI, New) = LiveVirtRegs.insert(LiveReg(VirtReg));
00597   if (New) {
00598     // If there is no hint, peek at the only use of this register.
00599     if ((!Hint || !TargetRegisterInfo::isPhysicalRegister(Hint)) &&
00600         MRI->hasOneNonDBGUse(VirtReg)) {
00601       const MachineInstr &UseMI = *MRI->use_instr_nodbg_begin(VirtReg);
00602       // It's a copy, use the destination register as a hint.
00603       if (UseMI.isCopyLike())
00604         Hint = UseMI.getOperand(0).getReg();
00605     }
00606     LRI = allocVirtReg(MI, LRI, Hint);
00607   } else if (LRI->LastUse) {
00608     // Redefining a live register - kill at the last use, unless it is this
00609     // instruction defining VirtReg multiple times.
00610     if (LRI->LastUse != MI || LRI->LastUse->getOperand(LRI->LastOpNum).isUse())
00611       addKillFlag(*LRI);
00612   }
00613   assert(LRI->PhysReg && "Register not assigned");
00614   LRI->LastUse = MI;
00615   LRI->LastOpNum = OpNum;
00616   LRI->Dirty = true;
00617   markRegUsedInInstr(LRI->PhysReg);
00618   return LRI;
00619 }

Reference:
1. LLVM Document http://llvm.org/docs/index.html
2. http://llvm.org/doxygen/RegAllocFast_8cpp_source.html#l01122

  RAFast::allocVirtReg is the way to allocate the virtual register to physical register in defineVirtReg. In the definVirtReg, when the virtual register is the new one in live interval, it is necessary to allocate the physical register to the virtual register. Therefore, the aim of allocVirtReg is to find the accessible physical register and allocate to it.

  Firstly, in the RAFast::allocVirtReg, it should find the target register class which has the same kind of registers.  Machine Register Information class is designed to provide the information of the registers. 

  const TargetRegisterClass * rc = MRI->getRegClass(VirtReg);

  It means that MRI has the map from virtual register to some identical register class

in the register class, it has many same functional registers, such as (EAX, EBX, EDX, are all 32 bit registers). TargetRegisterClass has the iterator for the begin machine register and the final machine register. 

   

  Otherwise, the target register info has many register class, because the registers in every different platform are categoried by the class in the LLVM. It means that the same registers (same function, 32 bits for example )are in the same group. Virtual registers are different by their targets (32 bit or 8 bits), it could be allocated by the MRI depended on the their function. Therefore, the 32 bits virtual registers are only could be allocated to the 32 bits physical registers.

  

  

 The hint in the allocVirtReg is the physical register, the free is determined in the allocateBasicblock. Therefore, the hint can be used directly, when the hint is valid. The hint is possible the target register, we have to calculate the spillcost of the hint. 

There are three different result:

Firstly, if the hint is not dirty register, than the definePhyReg is used to allocate the physical register.

Second, we try to find the free register and allocate it to the virtual register.

Third, the program scan all the registers and calculate the cost all the registers which find the lowest spill cost and allocate the physical register which has lowest spill cost to the virtual register.

RegisterAllocation2

In the First scan, try to find the direct use of physics register and define it. If the number of physical registers are enough for using in the instruction, it is clear that these physical registers are defined and the live unit can be calculated. In the first scan, the count of number virtual registers is also performed.

00930       if (TargetRegisterInfo::isVirtualRegister(Reg)) {
00931         VirtOpEnd = i+1;
00932         if (MO.isUse()) {
00933           hasTiedOps = hasTiedOps ||
00934                               MCID.getOperandConstraint(i, MCOI::TIED_TO) != -1;
00935         } else {
00936           if (MO.isEarlyClobber())
00937             hasEarlyClobbers = true;
00938           if (MO.getSubReg() && MI->readsVirtualRegister(Reg))
00939             hasPartialRedefs = true;
00940         }
00941         continue;
00942       }

 IN THE Second scan, it would determine on the registers whether they are used are not. If the virtual register is used and the virtual register is new,    it should try to load the frame index from the stack.

RAFast::reloadVirtualReg

00631   if (New) {
00632     LRI = allocVirtReg(MI, LRI, Hint);
00633     const TargetRegisterClass *RC = MRI->getRegClass(VirtReg);
00634     int FrameIndex = getStackSpaceFor(VirtReg, RC);
00635     DEBUG(dbgs() << "Reloading " << PrintReg(VirtReg, TRI) << " into "
00636                  << PrintReg(LRI->PhysReg, TRI) << "\n");
00637     TII->loadRegFromStackSlot(*MBB, MI, LRI->PhysReg, FrameIndex, RC, TRI);
00638     ++NumLoads;
00639   } else if (LRI->Dirty) {

  

 In the third scan, it would focus on the defs which is possible virtual register or physical register. In the beginning of the for loop, it tries to find the defs which are not deal with. If there are virtual registers it would defineVirtReg and

in the defineVirtReg it will call the definePhysicReg finally, otherwise, it will call definePhysReg as they are physical regiters.

01025     for (unsigned i = 0; i != DefOpEnd; ++i) {
01026       MachineOperand &MO = MI->getOperand(i);
01027       if (!MO.isReg() || !MO.isDef() || !MO.getReg() || MO.isEarlyClobber())
01028         continue;
01029       unsigned Reg = MO.getReg();
01030 
01031       if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
01032         if (!MRI->isAllocatable(Reg)) continue;
01033         definePhysReg(MI, Reg, MO.isDead() ? regFree : regReserved);
01034         continue;
01035       }
01036       LiveRegMap::iterator LRI = defineVirtReg(MI, i, Reg, CopySrc);
01037       unsigned PhysReg = LRI->PhysReg;
01038       if (setPhysReg(MI, i, PhysReg)) {
01039         VirtDead.push_back(Reg);
01040         CopyDst = 0; // cancel coalescing;
01041       } else
01042         CopyDst = (CopyDst == Reg || CopyDst == PhysReg) ? PhysReg : 0;
01043     }

Introduction LLVM Fast Register Allocation Part1

In this post, it focuses on the FastRegisterAllocator. First, in the targetpassconfig::addMachinePasses, function addOptimizedRegAlloc or addFastRegAlloc will called depending on whether the program in optimized or not. TargetPassConfig::createRegAllocPass will create the target-selected regalloc pass. TargetPassConfig::createTargetRegisterAllocator will called to return createGreedyRegisterAllocator or createFastRegisterAllocator. createFastRegisterAllocator will create RAFast which is the object do the fast register allocation strategy. 

Let us study the runOnMachineFunction to know how the pass work.  In the beginning, some info objects  will be initialized, such as MF, MRI, TRI, TII. These objects provide essential informaiton during register allocating. 
 In the outer loop, it iterate each basic block which is represend by the global pointer MBB.  
  The allocatebasicblock is the function which do the fast register allocation in each block.
   for (MachineFunction::iterator MBBi = Fn.begin(), MBBe = Fn.end();
          MBBi != MBBe; ++MBBi) {

              MBB = &*MBBi;
              AllocateBasicBlock();
   }
In the AllocateBasicBlock, the loop each livein register which is represented by the livein_iterator. The livein_iterator is the iterator of vector which track the live-in register in the basic block. Each physical register will be checked whether it is  in the allocatable register  class, then the register is defined. 

The process will go to the while loop which loop each machineinstr. In the while loop, the DEBUG Macro will record the debug information if necessary. If the machineinstr has debugvalue, the it will go through each operands in the machineinstr, and create new machineisntr in the basic block if necessary.

If the machineinstr does not have debugvalue, then the machineinstr will go through three scan which will introduced in the future posts. 

Reference:
LLVM Document: http://llvm.org/docs/CodeGenerator.html
doxygen: http://llvm.org/doxygen/index.html
LLVM Project Blog: http://blog.llvm.org/2011/09/greedy-register-allocation-in-llvm-30.html