# EFA 3
###### tags: `efa` `design`
## Interprocedural analysis
It is important to understand *what question are we answering*.
The question can be formulated as follows:
* can we exclude that register X is not an argument (return value)?
* do we have strong proof that register X is an argument (return value)?
* is there at least a strong hint that register X is an argument (return value)?
Lattice:
```graphviz
digraph {
rankdir = BT
node [shape=box]
No [peripheries=2]
No -> Yes
}
```
## Intraprocedural analyses
<center>
| Name | Direction | Works on |
| ------ | --------- | ----------------------- |
| UAOF | Forward | Function arguments |
| RAOFC | Backward | Call site arguments |
| URVOF | Backward | Function return values |
| URVOFC | Forward | Call site return values |
</center>
## UsedArgumentsOfFunction (UAOF)
* Question: is register X an argument, is it unused or is it either a dead argument or not an argument at all?
* Starting point: function entry point
* Forward
* How: if we find a read before a write to that register *on at least one path*
* Collection point: any node
* Old names: `UsedArgumentsOfFunction` and `DeadRegisterArgumentsOfFunction`
### Motivating examples
`rdi` read before being written to, therefore it's an argument:
```x86asm=
a:
mov rax, rdi
ret
```
Callee has an argument, the caller has too:
```x86asm=
a:
call b ; rdi is an argument of b
ret
```
### Lattice
```graphviz
digraph UsedArgumentsOfFunction {
node [shape=box]
rankdir=BT;
NoOrDead;
Unused [peripheries=2];
Yes;
# Lattice
NoOrDead->Unused;
Unused->Yes;
}
```
### Transfer functions
```graphviz
digraph UsedArgumentsOfFunction {
node [shape=box]
NoOrDead;
Unused [peripheries=2];
Yes;
# Transfer functions
Unused->Yes [label="Read"];
Unused->NoOrDead [label="Write"];
}
```
### Promotion to interprocedural lattice
* `Yes` becomes `Yes`
* `NoOrDead` becomes `No`
* `Unused` becomes `No`
### Interprocedural inputs and outputs
Remember: "$A \rightarrow B$" means "$A$ has effects on $B$".
So, $\forall$ function $F$:
```graphviz
digraph {
node [shape=box]
UAOF [peripheries=2,label="UAOF(F)"]
CalleeArgument [label="C.Argument"]
CalleeArgument -> UAOF [label=" ∀C, C∈F.Callees"]
UAOF -> FArgument
FArgument [label="F.Argument"]
}
```
## RegisterArgumentsOfFunctionCall (RAOFC)
* Goal: say if a register is an argument of a function call
* Starting point: call site
* Backward
* How: if we find a write to a register whose value is not read by anyone else before the call site *on all paths*
* Collection points: entry point
* Old names: `RegisterArgumentsOfFunctionCall` and `DeadReturnValuesOfFunctionCall`
*Note*: `WeakWrite` here is used to prevent return values in register `x` of function calls to always and automatically become arguments of all the function calls reachable from them on paths that do not read/write `x`. This would be too aggressive.
### Motivating examples
`rdi` is written before a call to a function that does not preserve it, therefore it is an argument of the callee:
```x86asm=
a:
mov rdi, 42
call b ; b does not preserve rdi
ret
```
A call to `b` is preceded by a call to a function that is known to return `rax`, therefore it's an argument of `b`:
```x86asm=
c:
call a ; rax is a return value of b
call b
ret
```
### Lattice
```graphviz
digraph RegisterArgumentsOfFunctionCall {
node [shape=box]
rankdir=BT;
Bottom;
Unused [peripheries=2];
Yes;
No;
# Lattice
Bottom->Yes;
Bottom->Unused;
Yes->No;
Unused->No;
}
```
### Transfer functions
```graphviz
digraph RegisterArgumentsOfFunctionCall {
node [shape=box]
Unused [peripheries=2];
Yes;
No;
# Transfer functions
Unused->Yes [label="Write"];
Unused->No [label="Read"];
Unused->No [label="TheCall"];
# Prevent return values to become arguments right away
Unused->No [label="WeakWrite"];
}
```
### Promotion to interprocedural lattice
* `Yes` becomes `Yes`
* `No` becomes `No`
* `Unused` becomes `No`
### Interprocedural inputs and outputs
Remember: "$A \rightarrow B$" means "$A$ has effects on $B$".
So, $\forall$ callsite $CS1$:
```graphviz
digraph {
node [shape=box]
RAOFC [peripheries=2,label="RAOFC(CS1)"]
PreviousCallSitesReturnValues [label="CS.Callee.ReturnValue"]
PreviousCallSitesReturnValues -> RAOFC [label=" ∀CS, CS∈CS1.PreviousCallSites"]
CallerArgument -> RAOFC
CallerArgument [label="CS1.Caller.Argument"]
CalleeArgument [label="CS1.Callee.Argument"]
RAOFC -> CalleeArgument
}
```
```x86asm=
a:
call x ; call site
```
## UsedReturnValuesOfFunction (URVOF)
* Goal: say if a register is a return value (possibly dead on call sites) of a function
* Starting point: return instructions and tail calls
* Backward
* How: if we find a write to a register whose value is not read by anyone else before the return *on all paths*
* Collection points: any node
* Old names: `UsedReturnValuesOfFunction`
### Motivating examples
"Dead" assignment to `rax` before a `ret`, therefore `rax` is a return value of the function:
```x86asm=
a:
mov rax, 42
ret
```
Forwarding a return value:
```x86asm=
a:
call b ; returns rax
ret
```
### Lattice
```graphviz
digraph UsedReturnValuesOfFunction {
rankdir=BT;
node [shape=box]
Bottom;
Unused [peripheries=2];
YesOrDead;
No;
# Lattice
Bottom->YesOrDead;
Bottom->Unused;
YesOrDead->No;
Unused->No;
}
```
### Transfer functions
```graphviz
digraph UsedReturnValuesOfFunction {
node [shape=box]
Unused [peripheries=2];
YesOrDead;
No;
# Transfer functions
Unused->YesOrDead [label="Write"];
Unused->No [label="Read"];
}
```
### Promotion to interprocedural lattice
* `YesOrDead` becomes `Yes`
* `No` becomes `No`
* `Unused` becomes `No`
### Interprocedural inputs and outputs
Remember: "$A \rightarrow B$" means "$A$ has effects on $B$".
So, $\forall$ function $F$:
```graphviz
digraph {
node [shape=box]
URVOF [peripheries=2,label="URVOF(F)"]
CalleeReturnValue [label="C.ReturnValue"]
CalleeReturnValue -> URVOF [label=" ∀C, C∈F.Callees"]
URVOF -> FReturnValue
FReturnValue [label="F.ReturnValue"]
}
```
## UsedReturnValuesOfFunctionCall (URVOFC)
* Goal: say if a register is a return value of a function call
* Starting point: call site
* Forward
* How: if we find a read before a write to that register *on at least one path*
* Collection points: any node
* Old names: `UsedReturnValuesOfFunctionCall`
### Motivating examples
`rax` is read after a call to a function `b` that does not preserve `rax`, therefore `rax` is a return value of `b`:
```x86asm=
a:
call b ; b does not preserve rax
mov rbx, rax
ret
```
`rax` is the argument of a function called after a call to `b`, therefore it's a return value of the `b`:
```x86asm=
a:
call b
call c ; rax is an argument of c
ret
```
### Lattice
```graphviz
digraph UsedReturnValuesOfFunctionCall {
node [shape=box];
rankdir=BT;
NoOrDead;
Unused [peripheries=2];
Yes;
# Lattice
NoOrDead->Unused;
Unused->Yes;
}
```
### Transfer functions
```graphviz
digraph UsedReturnValuesOfFunctionCall {
node [shape=box];
NoOrDead;
Unused [peripheries=2];
Yes;
# Transfer functions
Unused->Yes [label="Read"];
Unused->NoOrDead [label="Write"];
Unused->NoOrDead [label="TheCall"];
}
```
### Promotion to interprocedural lattice
* `Yes` becomes `Yes`
* `NoOrDead` becomes `No`
* `Unused` becomes `No`
### Interprocedural inputs and outputs
Remember: "$A \rightarrow B$" means "$A$ has effects on $B$".
So, $\forall$ callsite $F1$:
```graphviz
digraph {
node [shape=box]
URVOFC [peripheries=2,label="URVOFC(F1)"]
NextCallSitesArguments [label="CS.Callee.Argument"]
NextCallSitesArguments -> URVOFC [label=" ∀CS, CS∈F1.NextCallSites"]
CalleeReturnValue -> URVOFC
CalleeReturnValue [label="F1.Callee.ReturnValue"]
CallerReturnValue [label="F1.Caller.ReturnValue"]
URVOFC -> CallerReturnValue
}
```