0xMiden / 0xMiden/compiler

Implement peephole optimizer

Open
#31 0 comments 0 reactions 1 assignee Claimed by @bitwalker View on GitHub
codegen good first issue optimization
Dominant language
Rust
Stars
115
Forks
84
Avg merge
1d 8h
Merged PRs (30d)
15

Description

This is the first optimization pass I think we'll want to implement as we start to observe less-than-ideal instruction sequences in the generated MASM. Such sequences are likely to occur as an artifact of the stackification algorithm. Rather than add more complexity to that pass, it is more beneficial to post-process the output of the pass and collapse inefficient instruction sequences into more efficient forms using peephole optimization. We can then use this to inform changes to the stackification pass, by focusing on things which are not easily resolved by the peephole optimizer.

In particular, I'm expecting the following to be good candidates for this:

```[tasklist]
### Possible Optimizations
- [ ] Inefficient/noisy stack manipulation, e.g. `movup.4, drop, movup.3, drop, movup.2 drop, swap.1, drop` could become `swapw.1, dropw`
- [ ] Redundant/useless stack manipulation, e.g. `swap.1, swap.1` could be elided completely as such a sequence has no effect
- [ ] Inefficient arithmetic, e.g. `add.1, add.1` could become simply `add.2`
- [ ] Redundant arithmetic, e.g. `add.1, sub.1` could be elided completely
- [ ] Dead stores, e.g. `push.1, store.addr, push.2 store.addr` could be reduced to `push.2, store.addr` as the first store is never read
```

Some of these we could implement at a higher-level on the IR prior to stackification, but we'll want at least some degree of peephole optimization to clean up the output of stackification.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.