Automatic inference and fast interpretation of peephole optimization rules†

Peephole optimizers that are driven by machine descriptions are generally more thorough but less efficient than their classical rule-directed counterparts. This paper describes a system that addresses this shortcoming. It automatically infers rules by tracking the behaviour of a description-directed optimizer on a testbed, and it adapts a classical optimizer to interpret these rules efficiently. Experiments show that an easily constructed testbed can generate rules similar to those in a large hand-written rulebase. This software forms part of a compiler that simplifies retargeting by substituting peephole optimization for case analysis.