RSoC 1st Stage Report

RSoC

Radeco (Zhuo Zhang)

For radeco-lib, I started with fixing the build fails. It last for a long time, from the simple mis-typing to some logical errors like infinite recursion. Now, the newest Pull Request could pass the test, although Value Set Analysis was disabled for I haven't finish this stage.

After that, I rewrote the algorithm for Common Subexpression Elimination (CSE). Now radeco-lib could find out nearly all the common subexpressions and eliminated the ones within a single basic block. The main idea is sorting the operands of commutative opcodes before CSE by a simple sorting algorithm on SSA. Future work, when the whole working chain is finished, on CSE will be concentrating on cross-blocks elimination.

My main task in 1st stage was building the Memory SSA, or in other words, starting Data Flow Analysis on memory. It's a long-term work involving Memory SSA Generation, Value Set Analysis (VSA) and Type Inference Analysis. Sadly, I only finished the first part in 1st stage. Now, radeco-lib could generate raw Memory SSA, which only included three kinds of variables and didn't distinguish different variables of the same kind. If we want more accurate result, we should move into VSA. By the way, the three kinds of variables are local variables which are used on the stack, global variables which are placed onto .bss/.data/.rodata segments and extra variables which are heap variables. All the three kinds of variables correspond the concept, Memory-Regions, in VSA. Thus, the generation would be easily moving forwards.

Nowadays, radeco-lib could support the first part of decompiler, taking radare2 as disassembler, translating ESIL into radecoIL based on SSA, doing CSE and Constant Propagation, and then generating raw Memory SSA. Also, as mentioned, the next step of my job would be concentrating on VSA and Type Inference. It's an urgent work and if we finish these, the Data Flow Analysis of radeco-lib could be accomplished. I managed to finish these in the 2nd stage and hope the first part of Radeco could work.