Automatic inference of models for statistical code compression

This paper describes experiments that apply machine learning to compress co mputer programs, formalizing and automating decisions about instruction enc oding that have traditionally been made by humans in a more ad hoc manner. A program accepts a large training set of program material in a conventiona l compiler intermediate representation (IR) and automatically infers a deci sion tree that separates IR code into streams that compress much better tha n the undifferentiated whole. Driving a conventional arithmetic compressor with this model yields code 30% smaller than the previous record for IR cod e compression, and 24% smaller than an ambitious optimizing compiler feedin g an ambitious general-purpose data compressor.