`llvm::LiveVariables` : Live Variable Analysis
====

LiveVariables.cpp implements Live Variable 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). (Taken from LiveVariables.cpp)

-----------------------------------------

* **Which analysis/transformation do you consider?**

`llvm::LiveVariables` : Live Variable Analysis

* **Where is it located in LLVM code base? (Main file or files)**

`{LLVM_src}/lib/CodeGen/LiveVariables.cpp`

* **Does the analysis take advantage of the SSA form? If so, how?**

Yes. This pass takes advantage of the SSA form.

This class computes live variable information for virual registers and _register allocatable_ physical register in a function. Physical registers are assumed to be live within a single block and uses dominance properties of SSA form to compute live variables for virtual registers. Live variable information is calculated in depth first order on the CFG of the function. This guarentees that the definition of variables is seen before its use due to dominance properties of SSA form (PHI nodes are handled as special case)

* **What data structures are used? Can you say something about the pass efficiency?**

The pass uses data structures such as std::vector<MachineBasicBlock*> to maintain information about Worklist. The list contains instructions (predecessors) in the basic block that were marked alive. There are no global data structures used in this pass.

I think the pass is efficient since it makes use of dominance properties of SSA form to compute live variables for virtual registers.

* **Give an example program and show the steps of the analysis on it.**

*C program*
```
b1: a = 3;
    b = 5;
    d = 4;
    x = 100;
    if a > b then
b2:    c = a + b;
       d = 2;
b3: endif
    c = 4;
    return b * d + c;
```

*Analysis*
```
// in: {}
b1: a = 3;
    b = 5;
    d = 4;
    x = 100; //x is never being used later thus not in the out set {a,b,d}
    if a > b then
// out: {a,b,d}    //union of all (in) successors of b1 => b2: {a,b}, and b3:{b,d}

// in: {a,b}
b2: c = a + b;
    d = 2;
// out: {b,d}

// in: {b,d}
b3: endif
    c = 4;
    return b * d + c;
// out:{}
```

*Summary*

| processing |	out-state | old in-state |	new in-state	| work list |
|---|---|---|---|---|
|b3|{}|{}|{b,d}|(b1,b2)|
|b1|{b,d}|{}|{}|(b2)|
|b2|{b,d}|{}|{a,b}|(b1)|
|b1|{a,b,d}|{}|{}|()|


* **What transformation in LLVM code can take advantage of the analysis?**
The result obtained from live variable analysis can be used in dead code elimination tranformation (-dce llvm pass) to check if any instructions that were used by removed instructions to see if they are newly dead.