# Improving `switch` handling
###### tags: `presentation` `hour` `switch`
---
# `switch`
How are they lowered?
----
```c
switch (x) {
case 0:
return;
case 1:
return;
case 2:
return;
default:
return;
}
```
----
```x86asm=
_start:
cmp rax,0x3
ja end
jmp QWORD PTR [rax*8+jumptable]
zero:
ret
one:
ret
two:
ret
end:
ret
```
----
```x86asm=
.section .rodata
jumptable:
.quad one
.quad two
.quad three
.quad end
```
---
# Current state
* We're pretty good at devirtualizing them
* The decompile C code is too low-level
----
## What we emit
```c
if (_argument_rax < 3) {
switch (_segment[...]
._offset_1864
._member1[_argument_rax << 2 & 0x3FFFFFFFC]) {
case 18446744073709544792U: // 0xffffffffffffe558
```
----
## What we'd like to emit
```c
switch (_argument_rax) {
case 0:
case 1:
...
```
---
## A solution
----
## Find all the `switch`s
```cpp
for (SwitchInst *Switch : MyFunction) {
// ...
}
```
----
## Compute the DFG
```cpp
auto *Condition = Switch->getCondition()
// Use AVI to compute the DFG and constraints on its nodes
auto VM = ValueMaterializer::getValuesFor(Switch,
Condition,
...);
auto &DFG = VM.dataFlowGraph();
```
----
```graphviz
digraph {
node [shape=box]
rankdir = BT;
plus [label="+"]
mul [label="*"]
jump_table [label="&jump_table"]
pc -> plus -> jump_table
plus -> mul -> rax
mul -> 8
rax [label="rax\l[0, 2]\l",color=red]
}
```
----
## Ensure the values are the ones we expect
```cpp
if (VM.values() != Switch->getCaseValues()) {
revng_log("Unexpected values!");
continue;
}
```
----
## Find the red node
```cpp
auto *StartNode = getUniqueRedNode(...);
if (StartNode != nullptr)
continue;
```
----
## Recompute `case` values
```cpp
std::map<ConstantInt *, BasicBlock *> NewLabels;
for (ConstantInt *Value : StartNode->OracleRange) {
Old = DFG.materializeOne(Value);
NewLabels[Value] = Switch->getBlockFor(Old);
}
```
----
## Rebuild the `switch`
```cpp
Switch->setCondition(StartNode->Value);
// Recreate cases using NewLabels
```
----
# Done!
---
# What about `default`?
Can we detect it?
----
## Original code
```c
switch (x) {
case 0:
return 42;
case 1:
return 431;
case 2:
return 69;
default:
return 123;
}
```
----
## Pseudocode
```c
if (x < 3) {
switch (x) {
case 0:
return 42;
case 1:
return 431;
case 2:
return 69;
}
} else {
return 123;
}
```
----
Not perfect, but OK
----
## What if we drop `case 1`?
```c
switch (x) {
case 0:
return 42;
case 2:
return 69;
default:
return 123;
}
```
----
## The CFG
```graphviz
digraph {
node [shape=box]
pre_check [label="x < 3"];
switch;
switch -> case0 [label=0];
switch -> case2 [label=2];
switch -> default [label=1]
case0 [label="return 42"]
case2 [label="return 69"]
default [label="return 123"]
pre_check -> switch [label=yes]
pre_check -> default [label=no]
}
```
----
## Pseudocode
```c
if (x < 3) {
switch (x) {
case 0:
return 42;
case 1:
goto default_case;
case 2:
return 69;
}
} else {
default_case:
return 123;
}
```
----
# What do?
----
```graphviz
digraph {
node [shape=box]
pre_check [label="x < 3"];
switch [label="load (jump_table + 8 * x)"];
switch -> switch2;
switch2 [lable="switch"]
switch2 -> case0 [label=0];
switch2 -> case2 [label=2];
switch2 -> default [label=1]
case0 [label="return 42"]
case2 [label="return 69"]
default [label="return 123"]
pre_check -> switch [label=yes]
pre_check -> switch2 [label=no]
switch2 -> default [label="default"]
}
```
----
```graphviz
digraph {
node [shape=box]
pre_check [label=""];
switch2 [label="switch(x)"]
switch2 -> case0 [label=0];
switch2 -> case2 [label=2];
switch2 -> default [label=1]
case0 [label="return 42"]
case2 [label="return 69"]
default [label="return 123"]
pre_check -> switch2
switch2 -> default [label="default"]
}
```
---
# Thanks.
# Questions?