docs/ir-why-not.md

   1 Survey of Intermediate Representations/Languanges (IR/IL) for Decompilation
   2 ===========================================================================
   3
   4 ScratchABlock uses PseudoC, a machine-independent assembler with C-like
   5 syntax,
   6 [an idea inspired](https://radare.gitbooks.io/radare2book/content/visual_mode/visual_disassembly.html#asmpseudo-enable-pseudo-syntax)
   7 by Radare2.
   8
   9 This documents why other existing compiler/decompiler IRs were not
  10 chosen instead.
  11
  12 UNCOL
  13 -----
  14
  15 This entry may serve as an epigraph (and was added later than the majority
  16 of content below). The problem of common intermediate representation is
  17 as old as the computing itself, with "UNCOL" (universal computer-oriented
  18 language) being proposed as early as 1958:
  19
  20 * https://en.wikipedia.org/wiki/UNCOL
  21
  22 LLVM IR
  23 -------
  24
  25 LLVM IR is by definition in SSA form, and converting normal code to SSA
  26 form (and back) is a task on its own. Also, LLVM IR has obfuscation
  27 features like implicit labels (https://llvm.org/bugs/show_bug.cgi?id=16043).
  28 Finally, LLVM IR is strictly typed, with high-level types. These are
  29 counter-productive for disassembly representation, where machine instruction
  30 deal with simple, dynamic types.
  31
  32 BinNavi REIL, Valgrind VEX
  33 --------------------------
  34
  35 All these decompiler IRs are designed with CISC X86 architecture in
  36 mind, and take for granted that a single machine instruction will be
  37 converted to several IR instructions. That alone makes them not
  38 human-friendly, but they also feature over-explicit, verbose syntax.
  39
  40 VEX is [used by angr](https://docs.angr.io/docs/ir.html). They also
  41 [explain](https://docs.angr.io/docs/faq.html#why-did-you-choose-vex-instead-of-another-ir-such-as-llvm-reil-bap-etc)
  42 why they didn't choose LLVM IR, etc.
  43
  44 Radare2 ESIL
  45 ------------
  46
  47 https://github.com/radare/radare2/wiki/ESIL
  48
  49 "Forth-like representation for every opcode", which makes it a joke
  50 of human-readability.
  51
  52 Bare Bones Backend IR
  53 ---------------------
  54
  55 https://webkit.org/docs/b3/
  56
  57 B3 IR wasn't known to the author when ScratchABlock was started. What's
  58 insightful though is a quote from [this page](https://trac.webkit.org/wiki/FTLJIT):
  59 "The FTL JIT started out as a marriage of the DFG and LLVM. We are phasing out LLVM
  60 support [...]. We are moving the FTL JIT to use the B3 backend instead of LLVM.
  61 B3 is WebKit's own creation. WebKit tends to perform better with the B3." So,
  62 people tried LLIR and associated technologies, and figured they can do better
  63 and less bloated on their own. Per the main page, "B3 comprises a
  64 [C-like SSA IR](https://webkit.org/docs/b3/intermediate-representation.html)".
  65 C-likeness in their terms mean: a) uses function call syntax to represent
  66 operations; b) uses a simple type system (comparing to LLIR's). In this regard,
  67 PseudoC is only further extension of this idea, using native C operators where
  68 possible, and otherwise trying to stick to "real" C syntax. For example, B3 IR's
  69
  70     Int32 @2 = Add(@0, @1)
  71
  72 corresponds to PseudoC's (assuming implicit size of registers to be 32):
  73
  74     $r2 = $r0 + $r1
  75
  76 So, overall, B3 IR and PseudoC are very similar, and differences come from
  77 different target usage (B3 IR is JIT IR, PseudoC is decompilation IR).
  78
  79 HHVM IR
  80 -------
  81
  82 Another IR which wasn't known to the author when ScratchABlock was started.
  83
  84 Facebook's PHP HipHop VM (HHVM) uses own IR, HHIR. Just quoting
  85 [slide 36](https://image.slidesharecdn.com/hhvmonaarch64-bud17-400k1-170320163554/95/hhvm-on-aarch64-bud17400k1-36-638.jpg?cb=1490027817)
  86 of https://www.slideshare.net/linaroorg/hhvm-on-aarch64-bud17400k1:
  87 "LLVM? Have you heard of it?" "Why don't you just use LLVM?" "We tried it:
  88 a) No noticeable performance gains; b) LLVM's MCJIT is too heavyweight".
  89
  90 (No comparison of HHIR and PseudoC, HHIR is pretty much adhoc IR for HHVM
  91 grounded in its PHP nature. The point is, oftentimes it's easier to use
  92 something else, even if adhoc, than a bloated pseudo-standard like LLIR).
  93
  94 QBE IL
  95 ------
  96
  97 http://c9x.me/compile/doc/il.html
  98
  99 I watched QBE project for a while, but only recently figured that its
 100 intermediate language is well documented.
 101
 102 Creton IL
 103 ---------
 104
 105 * https://cretonne.readthedocs.io/en/latest/langref.html
 106 * https://cretonne.readthedocs.io/en/latest/compare-llvm.html
 107
 108 Didn't exist when ScratchABlock was started. Uses an interesting syntactic
 109 sugar for Phi functions: instead of having them explicitly, it has "basic
 110 block parameters", in a way very similar to function parameters, and
 111 every jump specifies actual values for these "parameters".
 112
 113 C--
 114 ---
 115
 116 http://www.cs.tufts.edu/~nr/c--/
 117 http://www.cs.tufts.edu/~nr/c--/extern/man2.pdf
 118
 119 Unlike many entries in this list with comments like "wasn't known to me
 120 before ScratchABlock was started" or "didn't exist before ScratchABlock
 121 was started", C-- was (remotely) known to me for a long-long time. Actually,
 122 I heard about it yet when there was no Interwebs and the program exchange
 123 was happening via floppy disks, i.e. at the end of 20th century, which,
 124 checking the C-- timeline, was soon after C-- was initially appeared
 125 (1997). Given this, I guess it's fair to say that C-- was a meta-mental
 126 model of ScratchABlock IR, and ScratchABlock IR is the closest to C--.
 127
 128 C-- has different aims and purpose though, for example it supports garbage
 129 collection interface, exception handling, etc. Overall, featureset and
 130 usecases for C-- and ScratchABlock definitely overlap, but are different.
 131
 132 Miasm IR
 133 --------
 134
 135 https://github.com/cea-sec/miasm
 136
 137 Miasm has its [own IR](https://github.com/cea-sec/miasm#intermediate-representation).
 138
 139 FalconRE IR
 140 -----------
 141
 142 https://github.com/falconre/falcon
 143
 144 Just as everyone else, FalconRE has its [own IR](https://docs.rs/falcon/0.3.1/falcon/il/index.html),
 145 at least this time "with strong influences from RREIL and Binary Ninja's LLIL".
 146
 147 This [blog post](http://reversing.io/posts/the-il-nop/) has insightful
 148 comments about some other PRs:
 149
 150 > I have experienced the, “Joys,” of VEX IR in Angr’s pyvex, and
 151 > the forever popular LLVM IR.
 152
 153 > With Falcon, I wanted to design a simple, expression-based IL. I originally
 154 > arrived at five Operation types:
 155 >  * Assign { dst: Scalar,       src: Expression }
 156 >  * Store  { index: Expression, src: Expression }
 157 >  * Load   { dst: Scalar,       src: Expression }
 158 >  * Branch { target: Expression }
 159 >  * Raise  { expr: Expression }
 160
 161 PseudoC doesn't even try to specifically distinguish loads and stores - for
 162 it, they are assignments just the same. Of course, if for some analysis
 163 they're useful, they can be easily separated: loads are just assignments
 164 with memory reference on RHS, store - on LHS.
 165
 166 > ILs by readability
 167 >
 168 > Binary Ninja is the first IL I know of which made it a point to have a
 169 > readable IL. If you haven’t spent a lot of time looking at ILs for
 170 > reverse-engineering, the experience is typically like reading a computer
 171 > program written by your friend’s nephew who is having trouble with their
 172 > Introduction to Java course,  and is pretty sure their program to find the
 173 > greatest number in an array is complete, but they’re having some trouble
 174 > and here’s 300 lines of code and I guess they don’t teach whitespace
 175 > anymore and all_the_variablesLookLike_THIS. It can be annoying.
 176 >
 177 > RREIL is not readable. VEX IR is not readable.
 178
 179 D'oh. Nuff said. I couldn't say better, and actually, I didn't, but quoted
 180 Keith Cooper and Linda Torczon in ScratchABlock README instead.
 181
 182 > Falcon encodes intra-procedural direct branches, including conditional
 183 > intra-procedural direct branches, implicitly as optionally guarded edges
 184 > in the ControlFlowGraph.
 185
 186 Well, of course. In ScratchABlock, original instructions remain after
 187 parsing, but most transformations start with removing them using
 188 the `remove_trailing_jumps` pass.
 189
 190 > I ended up replacing the Raise operation with the much more verbose,
 191 > and battle-ready, Intrinsic operation.
 192
 193 In PseudoC, "Intrinsic" is called "special function".
 194
 195 > If-Then-Else, or Ite Expression
 196 > I originally left the Ite expression out of Falcon IL very consciously.
 197 > After a while, I relented, and now Falcon has an Ite expression.
 198
 199 ScratchABlock/PseudoC approaches this problem differently, given that its
 200 original usage is decompilation in the first place. So, besides "basic"
 201 PseudoC form, there're also "lifted" forms of PseudoC with consecutively
 202 higher and higher level control flow structures (like If-Then-Else). Granted,
 203 there's [currently] no parser for such a form, but nonetheless it exists
 204 in the CFG representation and can be processed and/or dumped.
 205
 206 References
 207 ----------
 208 * http://indefinitestudies.org/2009/04/03/a-quick-survey-on-intermediate-representations-for-program-analysis/
 209 * [angr FAQ: Why did you choose VEX instead of another IR (such as LLVM, REIL, BAP, etc)?](https://docs.angr.io/docs/faq.html#why-did-you-choose-vex-instead-of-another-ir-such-as-llvm-reil-bap-etc)
 210 * [FalconRE: The IL Nop](http://reversing.io/posts/the-il-nop/)