List of DFG simplificable patterns

possible_dfg_simplifications.md

List of DFG simplificable patterns (within a single DFG node)

This list includes some data flow patterns which can be simplified for better human comprehension. There may ne some overlapping between different patterns.

Saved and restored register

push rax
pop rax
add rax, 2
push rax
pop rax

This kind of sequences can be simplified by simply removing one or more instructions. In order to find candidate instructions we need to identify the largest intervals before and after which the sym expr. of the target value remains unchanged. We can then remove all the instructions in between.

Wanted outcome:

mov rax, 10

Chain of moves

Example 1:

mov rax, 10
mov [rbx], rax
mov rdx, [rbx]
mov rsi, rdx

Example 2:

mov rax, 10
push rax
pop rdx
mov rsi, rdx

Problem: it is not possible to simplify the expression by simply removing noisy instructions. One possible approach would be creating a new simpler sequence of instructions (or pseudo instructions) semantically identical to the original sequence:

mov rsi, 10

Implementation ideas:

• Write a SMT to LLVM converter and use LLVM optimization passes.
• Simplify SMT expressions using a solver and generate pseudo code from there.

Arithmetic operations

mov rax, 13
add rax, 10
sub rax, 2

Any sequence of arithmetic operations with constans can be simplified in a single assignment. The above example can be simplified with mov rax, 11.

Handle complete overwrites

Example 1:

mov rax, 12
xor eax, eax
lea rdx, [rax+1]

Example 2:

mov rax,12
sub rax, rax
add rax, 1

In both examples rax is completely overwritten by the second instruction, however since the second instruction uses the value of rax also the first instruction is considered as part of the slice despite the fact that, no matter what valu rax would have before the second instruction, the second instruction will produce always the same result.