[Decompiler] Replace IR

[water111]

The original IR system was hacky, poorly designed, and has no unit tests, so it is being redesigned. Writing a decompiler is a new thing for me, so the code was very experimental and I didn't have a good idea of how the whole system would work when I designed it. Now that we know more, it's time to clean up and add tests.

The new system will have two representations. The first is AtomicOps and the second is Forms. The disassembled code will be converted to AtomicOps first, then the AtomicOps will be converted to Forms.

My plan is to keep the old representation around until the new representation is completed. Then we can delete all of IR1.

Atomic Op

The AtomicOp is the smallest possible operation from the point of view of the decompiler's type system and register use system. An Atomic Op can contain small, simple expressions, like for example: (set! v1 (+ v0 s1)). But you can't infinitely nest expressions, and there are restrictions on what you can put where. An AtomicOp itself has no "value" - it represents a sequence of MIPS instructions that the original GOAL compiler likely emitted together.

• Implement AtomicOp: [Decompiler - New IR] Add AtomicOp #181
• Convert Instruction to AtomicOps (replacement of BasicOpBuilder): [Decompiler] Write IR2 to file and implement some Atomic Op conversions #187
• Full test coverage of all AtomicOp conversions
  • Single Op tests: Add single op test cases #188
  • The rest of the tests: Improved test namings for multi-operations, added new ones, still a few failures #190
• Type propagation algorithm on AtomicOp: [Decompiler] Implement IR2 Type Analysis Pass #193
• Register usage algorithm on AtomicOp: [Decompiler] add IR2 register usage pass #194
• SSA conversion and naming (not implemented in IR1): [Decompiler] WIP Conversion to SSA and variable naming #195

Form

The Form is like a Lisp form. It can optionally have a value, or it can be used for side effects. It can be nested. Some forms represent control flow statements. Designing this part of the IR will be tricky, but it will be important to get right. In particular it needs to be easy to manipulate, and it needs to be able to look back at the AtomicOps its made up of to determine the types of registers and what variables they correspond with. Another tricky part is handling "internal substitution" on Forms that never existed as AtomicOp (see get_consumed() for example). It may be worth having some separation between "just a blob of code" and "something that can have internal references modified in expression stacking". Like how there is a concept of "set!" vs. "not a set!".

• Implement Form and FormElement: [Decompiler] Begin ir2 form implementation #197
  • Utilities to iterate through forms
  • inline single element sequences (or make all elements std::vector<BaseForm>) and special case size 1?
• Conversion of AtomicOp to Form: [Decompiler] Begin ir2 form implementation #197
• Conversion of CfgVtx to Form: [Decompiler] Begin ir2 form implementation #197
• Regression tests for the output of top_level->to_form() at this point : [Decompiler] Test framework for decompiler regression tests and gcommon tests #200
• Pass register usage data to Form as needed for expression building: partially in [Decompiler] Get used variables, handle function calls better, and minor cleanup #205
• Ability to search for variables / get ones that aren't eliminated as temps: [Decompiler] Get used variables, handle function calls better, and minor cleanup #205
• Make "register form" from sequence (not sure what to name this? it's a form that has the side effects of a sequence but "evaluates to" a register) [Decompiler] Expressions (Part 3) #213
• Stack implementation: [Decompiler] Add stacking framework #206
• Form stacking algorithm: [Decompiler] Expression Building #211 [Decompiler] Expressions (Part 3) #213
• Delete IR1!: [Decompiler] Remove most IR1 Analysis #207
• Deref replacmenent: [Decompiler] Expression Building #211
• Method replacement
• Store Replacement
• Type checked math ops
• Condition regrouping and simplification
• Adding variable scopes
• Function definition syntax
• Full tests for gkernel.

[water111]

As we develop IR2, we'll keep IR1 around and the default. This might cause some temporary code duplication until we remove IR1, but it will be extremely helpful to be switch between the two. It can be toggled here: https://github.com/water111/jak-project/blob/2901f4a99e1ff3152c98ee94ee833ec36fb34182/decompiler/config/jak1_ntsc_black_label.jsonc#L64

[water111]

IR2 is used for everything, other than generating the all-types file, which is a separate issue.