peephole optimization patterns

Question

I've been reading up on local optimization compiler techniques but I keep not getting how they're implemented. The idea is that the optimizer looks at a 'window' of the code every time and somehow detects patterns and replaces them with more optimized versions.

My question is, how does one discover these patterns? (let's say your platform is a VM that outputs assembly code for a made-up computer, like Schocken's Hack).

Do people actually inspect code manually (using Control Flow Graphs or DAGs or whatever) and then gather up all the patterns identified and code them into the optimizer? Or is there an automatic way.

For example, you feed the code-to-be-optimized in an analyzer, and it spews out said patterns. If so, how can one start writing one ?

Answer 1

The classic peephole optimizations aren't about strength reduction and the other things you name. They are 2-3 instruction sequences like for example

BRANCH FALSE $1
BRANCH $2
$1:

which can be reduced to

BRANCH TRUE $2

Sequences like this can arise in naive code generators such as come with single-pass compilers that don't generate ASTs, such as some COBOL compilers I have worked on.

Answer 2

It depends on you whether to write your own analyzer or use the existing ones. In either case your analyzer keeps checking the code until it is not more optimize. If you take an example of GCC, it has specific passes for optimization. Intermediate code of your program is given to these passes which executes one after another and optimize your code. Also any pass can execute more than once.
If you really want to go through how to write these optimizations, just go through passes.h file in GCC.