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