title: Compiler written in Java: Peephole optimizer implementation
body: <p>I'm writing a compiler for a subset of Pascal. The compiler produces machine instructions for a made-up machine. I want to write a peephole optimizer for this machine language, but I'm having trouble substituting some of the more complicated patterns.</p>
  
  <h3>Peephole optimizer specification</h3>
  
  <p>I've researched several different approaches to writing a peephole optimizer, and I've settled on a back-end approach:</p>
  
  <ul>
  <li>The Encoder makes a call to an <code>emit()</code> function every time a machine instruction is to be generated.</li>
  <li><code>emit(Instruction currentInstr)</code> checks a table of peephole optimizations:
  
  <ul>
  <li>If the current instruction matches the tail of a pattern: 
  
  <ol>
  <li>Check previously emitted instructions for matching</li>
  <li>If all instructions matched the pattern, apply the optimization, modifying the tail end of the code store</li>
  </ol></li>
  <li>If no optimization was found, emit the instruction as usual</li>
  </ul></li>
  </ul>
  
  <h3>Current design approach</h3>
  
  <p>The method is easy enough, it's the implementation I'm having trouble with. In my compiler, machine instructions are stored in an <code>Instruction</code> class. I wrote an <code>InstructionMatch</code> class stores regular expressions meant to match each component of a machine instruction. Its <code>equals(Instruction instr)</code> method returns <code>true</code> if the patterns match some machine instruction <code>instr</code>.</p>
  
  <p>However, I can't manage to fully <em>apply</em> the rules I have. First off, I feel that given my current approach, I'll end up with a mess of needless objects. Given that a complete list of peephole optimizations numbers can number around 400 patterns, this will get out of hand fast. Furthermore, I can't actually get more difficult substitutions working with this approach (see "My question").</p>
  
  <h3>Alternate approaches</h3>
  
  <p>One paper I've read folds previous instructions into one long string, using regular expressions to match and substitute, and converting the string back to machine instructions. This seemed like a bad approach to me, please correct me if I'm wrong.</p>
  
  <h3>Example patterns, pattern syntax</h3>
  
  <pre class="lang-none prettyprint-override"><code>x: JUMP x+1; x+1: JUMP y  --&gt;  x: JUMP y
  LOADL x; LOADL y; add     --&gt;  LOADL x+y
  LOADA d[r]; STOREI (n)    --&gt;  STORE (n) d[r]
  </code></pre>
  
  <p>Note that each of these example patterns is just a human-readable representation of the following machine instruction template:</p>
  
  <pre><code>op_code register n d
  </code></pre>
  
  <p>(n usually indicates the number of words, and d an address displacement). The syntax <code>x: &lt;instr&gt;</code> indicates that the instruction is stored at address <code>x</code> in the code store.</p>
  
  <p>So, the instruction <code>LOADL 17</code> is equivalent to the full machine instruction <code>5 0 0 17</code> when the <code>LOADL</code> opcode is 5 (<code>n</code> and <code>r</code> are unused in this instruction)</p>
  
  <h3>My question</h3>
  
  <p>So, given that background, my question is this: How do I effectively match and replace patterns when I need to include parts of previous instructions as variables in my replacement? For example, I can simply replace all instances of <code>LOADL 1; add</code> with the increment machine instruction - I don't need any part of the previous instructions to do this. But I'm at a loss of how to effectively use the 'x' and 'y' values of my second example in the substitution pattern.</p>
  
  <p><strong>edit</strong>: I should mention that each field of an <code>Instruction</code> class is just an integer (as is normal for machine instructions). Any use of 'x' or 'y' in the pattern table is a variable to stand in for any integer value.</p>