Peephole Optimizer Format

[AllanWang]

I thought about this a while back but didn't have time to write about it until now.

For peephole, I think the easiest way is to just expose the instruction list as is, and offer some helper functions (things like if a label is used). We won't allow navigation to other labels, which will also avoid the cycle problem. I'm not sure how much benefit will come from navigation anyways; it's mainly if branching is useless, ie from assigning the same thing to a var regardless of the path. At that point it isn't really peephole

[julianlore]

At a basic level, it's not really about assigning a variable, but if branching or even checking is useless. Our previous optimizer had a decent amount of patterns that had to navigate to labels. Off the top of my head, an example pattern could be something like:

iload_1
ifeq label_0
iload_0
return
label_0:
iload_1
return

to

iload_1
return

[AllanWang]

And you were able to fully traverse to other labels? I don't see a really elegant way of doing that without making everything mutable.

If we do allow access and modification for branches, then I don't see how we'll combine all the effect at the end

[julianlore]

Yes we were able to fully traverse.
Yeah, that's what I was thinking (in C it was mutable). But we could use ST and make each label a ref or something.
It'll complicate it but without traversal a lot of the patterns can't be implemented.

[AllanWang]

There's no point using haskell at that point then. We might have the option to make apis such as

replace :: Label -> Int -> [IRData] which replaces the first n items with our new content and resolve it after each step. If we used ST we'd end up having functions to lazily remove state whenever we access it.

[AllanWang]

The benefit of something like that is we don't need to use recursion either, so the problem won't blow up exponentially. But it's probably still less efficient

[AllanWang]

I'd probably just expose a similar interface to

https://github.com/comp520/Peephole-Template/blob/master/JOOSA-src/optimize.c

We can ignore the is_* functions for the most part

---

Functions

• Is label dead
• Get label position
• Replaces :: Int -> [IRData] -> * (replaces first n items with new list, which may be empty)
• Stack effect (https://github.com/comp520/Peephole-Template/blob/ec79308171eb9240218bf3145639ce668f00ef4f/JOOSA-src/optimize.c#L585) though we can probably split this into multiple functions