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