[LLVMdev] Live ranges of physical registers

[Chris Lattner]

On Thu, 1 Jun 2006, Fernando Magno Quintao Pereira wrote:
>    I am coding a liveness analysis algorithm, and I found this comment
> on LiveVariables.cpp:
>
> Line 00195 - http://llvm.org/doxygen/LiveVariables_8cpp-source.html :
>
>  // PhysRegInfo - Keep track of which instruction was the last use of a
>  // physical register.  This is a purely local property, because all
> physical
>  // register references as presumed dead across basic blocks.
>
> Indeed, I am using the X86 architecture, and I could not find
> general purpose registers such as EAX, EBX, etc, alive in between basic
> blocks in the control flow graphs generated by LLVM.

Yup!

> (some specific registers, such as the stack pointer, will be, of
> course, alive). Could someone tell me a little bit about this?
> Is this property true due to the way LLVM generates code?
> Can I assume that registers available for register allocation will not
> be alive in between basic blocks?

Before register allocation, there are three types of registers:

1. Virtual registers.  These are in SSA form, and follow all the normal
    SSA properties.  These can be live across blocks.
2. Unallocatable physical registers (e.g. ESP).  These can be live
    anywhere and can be used/modified in ways the register allocator is not
    required to understand.
3. Allocatable physregs (e.g. EAX).  These are *required* to only be live
    within a machine basic block.  This restriction is primarily to
    simplify/speed up the compiler (at no loss of generality because vregs
    can always be used).  The live ranges of allocatable physregs should be
    short, e.g. an instruction selector may emit:

    EAX = vreg1234
    EDX = vreg4567
    div vreg1928
    vreg8910 = EAX

The set of allocatable physregs can be obtained with 
MRegisterInfo::getAllocatableSet.

Also, I'd suggest reading through the CodeGen/LiveVariables.cpp file.  It 
is pretty short and describes some of these issues.  Here's the file 
header comment:

// This file implements the LiveVariable analysis pass.  For each machine
// instruction in the function, this pass calculates the set of registers that
// are immediately dead after the instruction (i.e., the instruction calculates
// the value, but it is never used) and the set of registers that are used by
// the instruction, but are never used after the instruction (i.e., they are
// killed).
//
// This class computes live variables using are sparse implementation based on
// the machine code SSA form.  This class computes live variable information for
// each virtual and _register allocatable_ physical register in a function.  It
// uses the dominance properties of SSA form to efficiently compute live
// variables for virtual registers, and assumes that physical registers are only
// live within a single basic block (allowing it to do a single local analysis
// to resolve physical register lifetimes in each basic block).  If a physical
// register is not register allocatable, it is not tracked.  This is useful for
// things like the stack pointer and condition codes.


-Chris

-- 
http://nondot.org/sabre/
http://llvm.org/