# EFA4
Hopefully the final version
---
## Goals
For each function
* detect which registers are arguments
* detect which registers are return values
---
## Observation #1
### Marking all registers as args is *correct*
But not very accurate.
(same for return values)
---
## Assumption #1
No register is read uninitialized
---
## Assumption #2
There are no dead register assignments
---
## EFA4 goal
EFA4 returns a set of arguments/return values
1. that is minimal, and
2. doesn't contradict assumption #1 and #2
----
## Contradiction of assumption #1
*No register is read uninitialized*
```x86asm=
myfunction:
add rdi, 3
mov rax, rdi
ret
```
Stating that `rdi` is *not* an argument means that
`rdi` is read uninitialized
----
## Contradiction of assumption #2
*There are not dead register assignments*
```x86asm=
myfunction:
add rdi, 3
mov rax, rdi
ret
```
Stating that `rax` is *not* a return value means that
`mov rax, rdi` is dead
---
# Summary
1. Double down on the two assumptions
2. Accept mistakes in case they do not hold
3. If assembly seems to violate them
add an argument/return value
---
# How
1. Design `-Wuninitialized`
2. Design a dead assignment analysis
3. Use results to detect assumptiosn violation
4. Add arguments/return values accordingly
---
## Detecting uninitialized variables uses
Simply use a liveness analysis.
----
## Liveness analysis
* Backward analysis, start from exit points
* Transfer function:
* `read $REG`: add `$REG` to the set
* `write $REG`: remove `$REG` from the set
* Combine operator: union
----
## The variables at the entry point have uninitialized reads
We mark them as arguments
to avoid violation of assumption #1
----
## Example #1
```graphviz
digraph {
node [shape=box]
A [label="",peripheries=2];
B [label="read rdi"];
C [label=""];
D [label="ret"];
A -> B -> D;
A -> C -> D;
}
```
----
## Example #2
```graphviz
digraph {
node [shape=box]
A [label="write rdi",peripheries=2];
B [label="read rdi"];
C [label=""];
D [label="ret"];
A -> B -> D;
A -> C -> D;
}
```
---
## Detecting dead assignments
Simply use a reaching definition analysis.
----
## What's eaching definition analysis?
It tells you what writes affect a certain read.
```x86asm=intel
myfunction:
mov rdi, 3 ; First write to rdi
mov rdi, 4 ; Second write to rdi
mov rax, rdi ; rdi is being read
ret
```
Analysis results: the read of `rdi` is *reached* by the second write, but not by the first.
----
## The analysis
* Forward analysis, start from the entry point
* Transfer function: $\forall{}$ `write $REG`
1) add `write $REG` to the set
2) remove all the other `write $REG`
* Combine operator: union
----
## When is an assignment dead?
An assignment `write $REG` is dead
if it doesn't reach any `read $REG` instruction.
----
## Back to EFA4
* We look for dead assignments before `ret`s
* Introduce a "virtual read" before `ret`
* Look for writes reaching *only* a virtual read
* Their target is a return value!
----
## Example #1
```graphviz
digraph {
node [shape=box]
A [label="",peripheries=2];
B [label="write rax"];
C [label=""];
D [label="ret"];
A -> B -> D;
A -> C -> D;
}
```
----
## Example #1
```graphviz
digraph {
node [shape=box]
A [label="",peripheries=2];
B [label="write rax"];
C [label=""];
D [label="read rax\lret\l"];
A -> B -> D;
A -> C -> D;
}
```
---
## But wait there's more
----
## Return values of call sites
The reasoning to detect *arguments* of a function
can be used to detect *return values* of call sites.
----
## Return values of call sites
An uninitialized read of a register after a call site
suggests that the register has been returned by the call.
```x86asm=
myfunction:
call function
add rax, 2
ret
```
*(assuming `function` does not preserve `rax`)*
----
## Arguments of call sites
The reasoning to detect return values of a function
can be used to detect *arguments* of call sites.
----
## Arguments of call sites
A dead assignment before a call site
suggests that the register is an argument for the call.
```x86asm=
myfunction:
mov rdi, 2
call function
ret
```
*(assuming `function` does not preserve `rdi`)*
---
## The interprocedural part
These *intra*procedural analyses are run until fixed-point in an *inter*procedural analysis.
----
## Example
```x86asm=
foo:
call bar
ret
bar:
mov rax, rdi
ret
```
1. Initially assume no arguments (*minimality*)
2. Analyze `foo`: `bar` has no args, same for `foo`
3. Analyze `bar`: you discover it has an argument
4. Analyze `foo`: now `foo` has an argument too
----
## Does it converge?
Yes:
* We start from having no arguments.
* Then, we only *add* arguments.
* Worst case: you add all registers one by one.
Yes, that's a monotone framework.
---
# Questions?