[Decompiler] Decompile `vector` as a proof of concept for the VU compiler/decompiler features

Running the decompiler

In the config file, set:

  "dgo_names":["CGO/GAME.CGO"]
"allowed_objects":["vector"]
  "analyze_expressions":false

this will do a basic disassembly on vector. It's expected that this basic mode will have a very high rate of success, of if problems appear here, they represent real issues.

Here's what to look for in the output:

Disassembly

This pass recognizes MIPS instructions and always succeeds in all Jak 1 code.

fp uses resolved: 27 / 27 (100.000 %)
Decoded 1854 / 1854 (100.000 %)

CFG

This pass builds up a graph which represents the loops and branches inside each function.

1 functions (1.45%) failed to build control flow graph

there is one failure here, in vector=. This is either a sign of an unimplemented case in the decompiler (rare at this point), or the GOAL code has inline assembly with branching. On functions which fail this pass, they will output some debug information that can be process by dot to make a fancy picture of the failed control flow graph. In this case vector= has an irregular control flow pattern that I believe is not GOAL, so it must be decompiled manually. Without this pass, most future passes will not be attempted.

Atomic Op Conversion

This converts instructions, or small groups of instructions into "atomic ops", the smallest individual operations considered by the decompiler in later passes.

Converting to atomic ops...
69/69/69 (successful/attempted/total)

this should almost always work.

Type Analysis

Note: this is already done for vector, so you can ignore this for now.

This pass is likely to cause problems. It attempts to solve for a type in each register at each instruction. It may be possible to get this pass stuck in a loop, though this hasn't happened in a long time. This represents a bug in the algorithm, and you should open an issue so it can be fixed.

Running type analysis...
67/67/69/69 (success/attempted/non-asm/total)

Currently it requires:

Knowing the types of arguments of each function
Knowing the types of functions/methods used in the function.

These can be entered in all-types.gc. I recommend making a section for each file. See gcommon at the very top for an example. You can also override types using type_hints.json. This is like using a C-style cast. It is possible to use this to create an unsolvable type analysis and it will get stuck in a loop.

We see that type analysis only was attempted on 67 out of the 69. This means that the decompiler did not know the types for two functions. To enter the types, modify all-types.gc. Search in the output for ;; WARN: Type Propagation failed: Function rand-vu-sphere-point! has unknown type or similar to find the functions that were not attempted.

Unfortunately there are some cases where the decompiler cannot yet figure out types. These include:

Accessing static data (like lw a0, L113(fp) loads a word, but we cannot figure out its type yet)
Using the stack pointer sp to access objects allocated on the stack
Advanced usage of the process pointer s6
Calling format with a sufficiently complicated string. If it can figure out the set of all possible strings at the format call, it will figure out how many arguments each string has. But if it can't figure this out (rare), it won't know how many arguments the format takes.

Register Usage and Variable Passes

Both of these should succeed. This figures out where registers go live and go dead (used in expression building and structuring) and split registers into typed variables. If the previous passes did not succeed, the results of this pass may be strange.

Structuring

This takes the register usage info and control flow graph, and builds it into GOAL expressions. It also begins building up dereference operations, just based on the type analysis pass.

Expressions

Once these passes are good, you can turn on analyze_expressions

Here is an example of the output, with comments for explanation

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; .function vector-xz-length-max! ;; use this name in configuration files
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  ;stack: total 0x30, fp? 0 ra? 1 ep? 1 ;; prologue info, ignore
  ;stack_vars: 8 bytes at 8
  ;gprs: gp s5
;; this is the types in each each reg-var.
;;  v1-4: float  a0-0: vector a1-0: float  f0-0: float  f0-1: float 

;; The BX: are basic blocks
;; The LX: are labels
;; instructions are:
;;  assembly op   ;; (atomic op, using reg-var)[index of atomic op] [<input types>] -> [<output types>] consumed
;;   (sometimes there may be multiple instructions per atomic op)

;; this is the prologue
L34:
    daddiu sp, sp, -48
    sd ra, 0(sp)
    sq s5, 16(sp)
    sq gp, 32(sp)
;; B0 will always mark the start of the actual code
B0:
    or gp, a0, r0             ;; (set! arg0 arg0)[0] [a0: vector ] -> [gp: vector ] cs: a0 
    or s5, a1, r0             ;; (set! arg1 arg1)[1] [a1: float ] -> [s5: float ] cs: a1 
    lw t9, vector-xz-length(s7);; (set! t9-0 vector-xz-length)[2] [] -> [t9: (function vector float) ]
    or a0, gp, r0             ;; (set! a0-1 arg0)[3] [gp: vector ] -> [a0: vector ]
    jalr ra, t9               ;; (call! a0-1)[4]   [a0: vector t9: (function vector float) ] -> [v0: float ] cs: a0 t9 
    sll v0, ra, 0

    mtc1 f0, v0               ;; (set! f0-0 (gpr->fpr v0-0))[5] [v0: float ] -> [] cs: v0 
    mtc1 f1, r0               ;; (set! f1-0 0)[6]  [] -> []
    c.eq.s f0, f1             ;; (b! (=.s f0-0 f1-0) L35 (set! v1-0 #t))[7] [] -> [v1: symbol ] cs: f1 
    bc1t L35
    daddiu v1, s7, 8

B1:
    or v1, s7, r0             ;; (set! v1-0 '#f)[8] [] -> [v1: '#f ]
B2:
L35:
    bnel s7, v1, L36          ;; (bl! (truthy v1-0) L36 (no-delay!))[9] [v1: symbol ] -> [] cs: v1 
B3:
    or v1, v1, r0             ;; (set! v1-1 v1-0)[10] [v1: symbol ] -> [v1: symbol ] cs: v1 

B4:
    mtc1 f1, s5               ;; (set! f1-1 (gpr->fpr arg1))[11] [s5: float ] -> []
    c.lt.s f0, f1             ;; (b! (<.s f0-0 f1-1) L36 (set! v1-1 #t))[12] [] -> [v1: symbol ] cs: f1 
    bc1t L36
    daddiu v1, s7, 8

B5:
    or v1, s7, r0             ;; (set! v1-1 '#f)[13] [] -> [v1: '#f ]
B6:
L36:
    bne s7, v1, L37           ;; (b! (truthy v1-1) L37 (set! v1-2 #f))[14] [v1: symbol ] -> [v1: '#f ] cs: v1 
    or v1, s7, r0

B7:
    mtc1 f1, s5               ;; (set! f1-2 (gpr->fpr arg1))[15] [s5: float ] -> [] cs: s5 
    div.s f0, f0, f1          ;; (set! f0-0 (/.s f0-0 f1-2))[16] [] -> [] cs: f1 f0 
    mtc1 f1, r0               ;; (set! f1-3 0)[17] [] -> []
    c.eq.s f0, f1             ;; (b! (=.s f0-0 f1-3) L37 (set! v1-3 #f))[18] [] -> [v1: '#f ] cs: f1 
    bc1t L37
    or v1, s7, r0

B8:
    lwc1 f1, 0(gp)            ;; (set! f1-4 (l.f arg0))[19] [gp: vector ] -> []
    div.s f1, f1, f0          ;; (set! f1-5 (/.s f1-4 f0-0))[20] [] -> [] cs: f1 
    swc1 f1, 0(gp)            ;; (s.f! arg0 f1-5)[21] [gp: vector ] -> [] cs: f1 
    lwc1 f1, 8(gp)            ;; (set! f1-6 (l.f (+ arg0 8)))[22] [gp: vector ] -> []
    div.s f0, f1, f0          ;; (set! f0-1 (/.s f1-6 f0-0))[23] [] -> [] cs: f0 f1 
    swc1 f0, 8(gp)            ;; (s.f! (+ arg0 8) f0-1)[24] [gp: vector ] -> []
    mfc1 v1, f0               ;; (set! v1-4 (fpr->gpr f0-1))[25] [] -> [v1: float ] cs: f0 
B9:
L37:
    or v0, gp, r0             ;; (set! v0-1 arg0)[26] [gp: vector ] -> [v0: vector ] cs: gp 
    ld ra, 0(sp)
    lq gp, 32(sp)
    lq s5, 16(sp)
    jr ra
    daddiu sp, sp, 48

    sll r0, r0, 0
    sll r0, r0, 0
    sll r0, r0, 0
;; control flow structure. this shows how the blocks above can be structured.
(seq
  (cond
   ((seq (sc ((seq (cond (b0 b1)) b2) b3) (cond (b4 b5))) b6) (cond (b7 b8)))
   )
  b9
  )

;; the output, using the variable names in var_names.json
(defun vector-xz-length-max! ((arg0 vector) (arg1 float))
  (local-vars (v1-4 float) (f0-0 float) (f0-1 float))
  (set! f0-0 (vector-xz-length arg0))
  (when (not (or (= f0-0 0) (< f0-0 arg1)))
   (set! f0-0 (/ f0-0 arg1))
   (when (!= f0-0 0)
    (set! (-> arg0 data 0) (/ (-> arg0 data 0) f0-0))
    (set! f0-1 (/ (-> arg0 data 2) f0-0))
    (set! (-> arg0 data 2) f0-1)
    (set! v1-4 f0-1)
    )
   )
  arg0
  )

;; this debug output is from before the expression building pass.
;; when that pass fails, it often goes very wrong, so this can be useful for debugging.
;; DEBUG OUTPUT BELOW THIS LINE:
(begin
  (if
   (begin
    (or
     (begin
      (set! t9-0 vector-xz-length)
      (set! a0-1 a0-0)
      (set! v0-0 (call! a0-1))
      (set! f0-0 (gpr->fpr v0-0))
      (set! f1-0 0)
      (set! v1-0 (=.s f0-0 f1-0))
      v1-0
      )
     (begin (set! f1-1 (gpr->fpr a1-0)) (set! v1-1 (<.s f0-0 f1-1)))
     )
    (not v1-1)
    )
   (when
    (begin
     (set! f1-2 (gpr->fpr a1-0))
     (set! f0-0 (/.s f0-0 f1-2))
     (set! f1-3 0)
     (!=.s f0-0 f1-3)
     )
    (set! f1-4 (-> a0-0 data 0))
    (set! f1-5 (/.s f1-4 f0-0))
    (set! (-> a0-0 data 0) f1-5)
    (set! f1-6 (-> a0-0 data 2))
    (set! f0-1 (/.s f1-6 f0-0))
    (set! (-> a0-0 data 2) f0-1)
    (set! v1-4 (fpr->gpr f0-1))
    )
   )
  (set! v0-1 a0-0)
  (ret-value v0-1)
  )

In this case, the output from the decompiler is pretty good. There are two issues:

The (set! v1-4 f0-1) should be eliminated. I plan to add something to fix this soon.
This should be one expression
```
(set! f0-1 (/ (-> arg0 data 2) f0-0))
(set! (-> arg0 data 2) f0-1)
```
usually this works, so this is a decompiler bug.

Neither of these are a big deal, and if you don't care to clean up all these little things, it is okay. It would be nice to give the arguments nicer names in var_names.json, like vec, and max-len or something like that, and maybe rename f0-0 to len.

open-goal / jak-project