Peephole Optimization

After all the instructions have been generated and all the missing information has been added to Mode, it is time to go through the instructions again and eliminate all the redundancies before any code is generated. This is achieved via a process called peephole optimization as follows. Starting at the top, ALE looks at pairs of instructions and try to either eliminate one or merge the two together. Then it moves down by one instruction and does the same to the next pair until it has considered all instructions.

• Merging:
  
  
  

  type Path, Type1	$\Longrightarrow$	type Path, (Type1 $\sqcup$ Type2)
  type Path, Type2

  Given two instructions type Path,Type1 and type Path,Type2, we know that the two types Type1 and Type2 must be unifiable because they share the same path; therefore, we can merge the two instructions into one: type Path, (Type1 $\sqcup$ Type2).

• Deletion:
  
  
  

  type Path, Type	$\Longrightarrow$	...Path ...
  ...Path ...

  Given the instruction type Path, Type and another instruction containing Path to a feature F, we can eliminate the first instruction because we know Type $\sqsubseteq$ intro(F). This means that when trying to get the value of F by a post-order traversal of Path, ALE has to process the instruction type Path, Type anyway.