Comment by aleclm | Hacker News Reader

Comment by aleclm | Hacker News Reader

Parent Full thread

> Do you have examples of your decompilation, and how it compares to state of the art that uses other approaches?

We don't have any exhaustive comparison, and for sure IDA are better than what we currently produce in many aspects (we're not at 1.0 release), but I can tell you where we want to go:

1. Automatic data structures detection: our goal is to basically never emit pointer arithmetic but automatically reconstruct data types so you see `pointer->field2 = 3` instead of `*(pointer + 8) = 3`. And we want to do this exploiting global (interprocedural) information, not just within a single function. AFAIK, this has never been done out of academia. https://twitter.com/_revng/status/1674788459213631505

2. Emit way less gotos, ideally none. That's one of the things that makes the code hard to read. https://rev.ng/downloads/asiaccs-2020-paper.pdf

But again, I invite you to register for the beta and wait for the blog post where we'll show some recent developments.

> Do you run optimizations on your generated LLVM IR to clean it up and canonicalize it?

Sure, but it's not just about cleaning it up. LLVM has a set of analyses that we exploit to detect access patterns and automatically detect data structures containing arrays too.

LLVM is so nice: it's scalable, you can recompile it, there's lots of analyses and you don't need to reinvent the wheel with six edges.

I read a paper once that a more ideal goal would be to not aim for goto free code, but instead aim at decompilation output that matches the source input best. The idea being that some C programs are really implemented as gotos and it's more natural to decompile them that way. This suggests some low % of gotos is the best rather than zero. Thoughts?

I was writing a response to the paper (which compares with rev.ng), but never managed to complete it. I wanted to make a thread on Twitter about it, but it was getting longer and longer, more like a blog post.

If you're really interested, drop me an e-mail and I'll forward it to you.

The bottom line is more or less summarized in my other response in this thread.

> Emit way less gotos, ideally none

I vaguely remember two questions regarding this when a "No More Gotos" paper was published:

1. What if programmer did use gotos, and without them you can't really map code structure to language's available control flow mechanisms?

2. What if compiler decided to duplicate or deduplicate some basic blocks?

Time to revisit original paper, and also read yours, to see what is said about these :)

1) Our goal is emitting goto rarely, not excluding them entirely. However, most of the gotos one sees in IDA are due limitations in control-flow recovery, example:

    switch (x) {
    case 0:
      do_0();
    // Missing case 1
    case 2:
      do_2();
    case 3:
      do_3();
    default:
      do_default();
    }

IDA will produce something like...

    if (x > 3)
      goto label;

    switch (x) {
    case 0:
      do_0();
    case 1:
    label:
      do_default();
    case 2:
      do_2();
    case 3:
      do_3();
    }

gotos originally present in the original code are almost never the reason you see a goto in IDA.

In any case, in presence of gotos, we currently duplicate code and sometimes this is good.

Imagine the following code snippet which represents a legitimate use of gotos:

    int *x = malloc(sizeof(int));
    if (x == NULL)
      goto cleanup;

    int *y = malloc(sizeof(int));
    if (y == NULL)
      goto cleanup;

    do_stuff(x, y);

    cleanup:
    if (x != NULL)
      free(x);
    if (y != NULL)
      free(y);

    return;

By "inlining" the gotos and doing some trivial optimizations we'd get:

    int *x = malloc(sizeof(int));
    if (x == NULL)
      return;

    int *y = malloc(sizeof(int));
    if (y == NULL) {
      free(x);
      return;
    }

    do_stuff(x, y);

    free(x);
    free(y);
    return;

Which is not bad a at all IMO.

2) We don't deal with duplication, it's way less of a problem, usually. For deduplication, if it leads to gotos, we duplicate.

Reply on news.ycombinator.com