matt-kempster / m2c

A MIPS and PowerPC decompiler.
GNU General Public License v3.0
396 stars 48 forks source link

IR pattern matching & register flow analysis #214

Closed zbanks closed 2 years ago

zbanks commented 2 years ago

This PR uses the instruction input/output/clobber access sets to compute a dependency/usage graph before the translate stage. This is then used to do IR pattern matching, to match the PPC float conversion patterns even when the instructions are reordered, reused, or split across multiple basic blocks.

It's really tempting to bring in a graph utility library like networkx, but I don't think it's worth the dependency yet.

The biggest caveat is that the IR pattern-matching algorithm is somewhat naive and can be slow: it's technically O(n^m) with n being the input asm length, and m being the pattern length. Practically, it about ~doubles the runtime in the worst case for a few functions in the PPC test projects I was looking at. I think this is a fine tradeoff for now?

Aside from the PPC patterns, the changes here aren't intended to have any significant output diffs, but they do change:

zbanks commented 2 years ago

I'm also happy to refactor IrMatch/TryIrMatch with TryMatchState from asm_pattern.py to reduce code duplication -- but I wanted to wait until the rest of the changes were mostly stable.

zbanks commented 2 years ago

Still need to tackle the changes to flow_graph.py/ir_pattern.py, but I wanted to check that my initial refactor of StackLocation is fine. Namely, I've simplified some of the logic in translate.py that makes some of the checks a bit weaker -- but I haven't found any output diffs in the e2e tests or MM, OOT, or PM.

simonlindholm commented 2 years ago

Still need to tackle the changes to flow_graph.py/ir_pattern.py, but I wanted to check that my initial refactor of StackLocation is fine.

Looks reasonable to me.

simonlindholm commented 2 years ago

As another option, we could leave StackLocation as is (with a size), but add a member function for "split this into bytes/words" (which would use a separate type) and use the split-up version when computing dependencies. I could see having the original size available when doing analysis on stack variables in translate in the future. (For example it would enable rolling back the translate changes.) But we can leave that for later once it actually turns out to be needed.