# PPA Assignment 2 Report
**Team members**
- Albert Akmukhametov
- Mark Esaian
- Ruslan Gilvanov
- Dzhemilya Vechtomova

**Repository with code**: [GitHub](https://github.com/kinjalik/PPA-Assignment2)
**Link to this report** (some maths and graphs may be more pretty there): [HackMD](https://hackmd.io/@kinjalik/ryX-CaSZ2)

## Language for analysis
We decided to use the [WhileLang](https://lrlucena.github.io/whilelang) proposed to use in Assignment description.

This is pretty simple single-procedure imperative language with single type (int), single loop instruction (while) and single conditional construct (if).

Example:

print "Enter the number of fibonacci numbers";
cnt := read;

print "Fibonacci Sequence of given size:";
a := 0;
b := 1;
n := 0;
while n <= cnt - 1 do {
  print b;
  b := a + b;
  a := b - a;
  n := n + 1
}

## Analysis description
We decided to implement **Live Variable Analysis**. As the result, for each instruction we will have set of "alive" varialbes, whose values will be used later.

This analysis may be useful for several optimizations (list is not comprehensive, of course):
- Elimination of unused variable assignments(i.e. variable is assigned, but its value is not used)
- Memory minimization (eg. if we have huge branch of code, where variable stored in register and will not die and will be passed through the block, we may unload from register to stack and when branch finished, load it to register again) (eg. if we have variable which will be dead, we can safely use its memory for the variable which will be declared and assigned later)

## Analysis properties
- **Domain**: variable names on each line of code
- **Transfer functions**:
- $GEN(n)$ aka $REF(n)$ --- set of variables which are used before any assignment at $n$
- $KILL(n)$ aka $DEF(n)$ or $ASS(n)$ (both names take place in our implementation) --- set of variables which are assigned at $n$
- $LIVE(n) = \left(\bigcup\limits_{s\in succ(n)} LIVE(s)\right)\setminus DEF(n) \cup REF(n)$ --- set of variables which are live at $n$ ($succ(n)$ --- set of successing instrucitons).
- **Confluence operator**: union
- **Initial values**: empty sets
- **Direction**: backwards
- **Sensetivity**: flow-sensetive

## How transer functions were derived.
$GEN(n)$ and $KILL(n)$ should be obvious - there are strictly corresponds to subject of analysis and its domain.

$LIVE(n)$ is simplificated join of two other functions:
- $outLive(n)$ --- set of live variable after the instruction in node $n$ is executed. Generally it is calculated in the followin manner:
$$outLive(n) = \bigcup\limits_{s\in succ(n)} inLive(s) $$
We just take all variables which are alive in sucecssive instructions.
- $inLive(n)$ --- set of live variables before the instruction in node $n$ is executed. Generally it is calculated in the following manner:
$$inLive(n) = \left(outLive(n)\setminus DEF(n)\right)\cup REF(n)$$
We take set of variables which will be alive after that instruction, exclude "killed" variables (which are defined in that instruction) and include alive variables (which are references in that instruction).

Initial values of each $outLive(n)$ and $inLive(n)$ are empty. We need to start CFG traversals from exit points and sequentially calculate these sets for each node. If on current iteration any of the set were updated, we need to perform another iteration further.

We can simply subsitutute $outLive$ into $inLive$ and got unified funciton for each node:
$$LIVE(n) = \left(\bigcup\limits_{s\in succ(n)} LIVE(s)\right)\setminus DEF(n) \cup REF(n) $$

## Implementation details
- **AST Parsing** --- ANTLR using [the grammar provided by language author](https://github.com/lrlucena/whilelang/#grammar)
- **CFG Building** --- complete using the Visitor over the AST
- **Analysis itself**
- Each iteration calculates $LIVE(n)$ for each node.
- Analysis happens until for any $n$ set of $LIVE(n)$ is updated. Or (for extreme and impossible cases) iteration limit meet.
- Usually 1 or 2 iterations are enough to complete the analysis due to its down-to-up nature.
- **Graph drawing** --- GraphViz code generation using [Dotlin](https://github.com/RCHowell/Dotlin) library

## How to run the demo
Just open it in IntelliJ Idea and run `LvaDemo` or `test` task.

Or use `gradlew`:

./gradlew clean test -i

This demo for each test program in `app/src/test/resources/examples/` will generate Markdown report with GraphViz blocks. Each graph block represents CFG at the beginning and after each iteration of the analysis. This input you may insert into HackMD or any other MD editor with supported GraphViz (but we tested only HackMD which was used to create this report).

## Example 1
### Code

c := 100;
print "Fibonacci Sequence";
print c;
a := 0;
b := 1;
while b <= 1000000 do {
  print b;
  b := a + b;
  a := b - a
}

### Steps of Analysis
#### Initial CFG

digraph {
	node[shape=box]
	1[label="c:=100"]
	1 -> 2
	2[label="print\"Fibonacci Sequence\""]
	2 -> 3
	3[label="printc"]
	3 -> 4
	4[label="a:=0"]
	4 -> 5
	5[label="b:=1"]
	5 -> 6
	6[label="while (b <= 1000000)"]
	6 -> 7
	7[label="printb"]
	7 -> 8
	8[label="b:=a+b"]
	8 -> 9
	9[label="a:=b-a"]
	9 -> 6
}

#### Iteration 0

digraph {
	node[shape=box]
	1[label="c:=100"]
	1 -> 2
	2[label="print\"Fibonacci Sequence\"
Live: c "]
	2 -> 3
	3[label="printc
Live: c "]
	3 -> 4
	4[label="a:=0"]
	4 -> 5
	5[label="b:=1
Live: a "]
	5 -> 6
	6[label="while (b <= 1000000)
Live: a b "]
	6 -> 7
	7[label="printb
Live: a b "]
	7 -> 8
	8[label="b:=a+b
Live: a b "]
	8 -> 9
	9[label="a:=b-a
Live: b a "]
	9 -> 6
}

#### Iteration 1

digraph {
	node[shape=box]
	1[label="c:=100"]
	1 -> 2
	2[label="print\"Fibonacci Sequence\"
Live: c "]
	2 -> 3
	3[label="printc
Live: c "]
	3 -> 4
	4[label="a:=0"]
	4 -> 5
	5[label="b:=1
Live: a "]
	5 -> 6
	6[label="while (b <= 1000000)
Live: a b "]
	6 -> 7
	7[label="printb
Live: a b "]
	7 -> 8
	8[label="b:=a+b
Live: a b "]
	8 -> 9
	9[label="a:=b-a
Live: b a "]
	9 -> 6
}

## Example 2
### Code

a := read;
b := a + 30;
if a <= 30 then {
    if b <= 40 then {
        a := 30
    } else {
        skip
    }
} else {
    skip
};
print a

### Steps of Analysis
#### Initial CFG

digraph {
	node[shape=box]
	1[label="a:=read"]
	1 -> 2
	2[label="b:=a+30"]
	2 -> 3
	3[label="if (a <= 30)"]
	3 -> 4
	3 -> 7
	4[label="if (b <= 40)"]
	4 -> 5
	4 -> 6
	7[label="skip"]
	7 -> 8
	5[label="a:=30"]
	5 -> 8
	6[label="skip"]
	6 -> 8
	8[label="printa"]
}

#### Iteration 0

digraph {
	node[shape=box]
	1[label="a:=read"]
	1 -> 2
	2[label="b:=a+30
Live: a "]
	2 -> 3
	3[label="if (a <= 30)
Live: a b "]
	3 -> 4
	3 -> 7
	4[label="if (b <= 40)
Live: a b "]
	4 -> 5
	4 -> 6
	7[label="skip
Live: a "]
	7 -> 8
	5[label="a:=30"]
	5 -> 8
	6[label="skip
Live: a "]
	6 -> 8
	8[label="printa
Live: a "]
}

#### Iteration 1

digraph {
	node[shape=box]
	1[label="a:=read"]
	1 -> 2
	2[label="b:=a+30
Live: a "]
	2 -> 3
	3[label="if (a <= 30)
Live: a b "]
	3 -> 4
	3 -> 7
	4[label="if (b <= 40)
Live: a b "]
	4 -> 5
	4 -> 6
	7[label="skip
Live: a "]
	7 -> 8
	5[label="a:=30"]
	5 -> 8
	6[label="skip
Live: a "]
	6 -> 8
	8[label="printa
Live: a "]
}