I have a project which includes a disassembler which makes old virtual machine formats playable online. It's a very simple disassembler; it basically processes the instructions outputting a code fragment which continues until it gets to any kind of branch or jump statement. The branch will set the program counter to its new value, and then the disassembler will produce a new code fragment again continuing until it reaches any branch.

I would like to move to a true decompiler which can turn this unstructured mess into true if statements and loops. I've seen at least two algorithms for this, namely the Relooper algorithm and the Stackifier algorithm, and I think I can mostly understand how they work at a high level, but I'm feeling stuck for how to implement them. These algorithm descriptions leave out, naturally, the details of what kinds of structs and enums you'd use to implement them. The Relooper uses three types of blocks, Simple, Loop, and Multiple, but it doesn't explain what sort of structs you'd need to expose to the algorithm before it can produce an output with just its Simple, Loop, and Multiple blocks.

I've realised I can't jump straight to using an algorithm like the Relooper, I need to learn more about compilers/decompilers first. Most resources I've seen on compilers start by parsing source code, whereas I need to start with a disassembler. Can you make any recommendations on resources explaining how to implement a decompiler based on a disassembler?

  • $\begingroup$ I'm hoping this question isn't too broad. If it's not on-topic here I'd appreciate any advice for how I can pull it into shape, if that's possible. Or if it should be migrated to Reverse Engineering or somewhere else. $\endgroup$ Oct 6, 2020 at 6:54
  • $\begingroup$ Welcome to COMPUTER SCIENCE @SE. There is quite a difference between taking the output of one specific compiler $C$ and producing something $C$ would produce an equivalent output for (especially with $C$ not applying code improvements / including debugging information) and taking arbitrary assembly/machine code and producing an equivalent structured program in a language of choice. $\endgroup$
    – greybeard
    Oct 7, 2020 at 7:35
  • $\begingroup$ @greybeard Indeed. I'm not looking for an exact round-trip-able decompiler. And yet there is a common core of theory and principles of decompilation. (For example most decompilers will build on the structured program theorem. The Relooper and Stackifer algorithms both do. My question is how to get to the point where either can be used. It may be too broad a question.) $\endgroup$ Oct 7, 2020 at 11:09


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.