Anticipatory Optimization in Domain Specific Translation

Anticipatory Optimization (AO) is a method for compiling compositions of abstract components (which are themselves composite data structures such as arrays, matrices, trees, record composites, etc.) so as to anticipate non-optimal structures in the compiled code (e.g., redundant iterations) and to compile the abstract components directly to optimized code without ever producing the non-optimal structures. Anticipatory Optimization is performed in the context of the domain specific operators and operands (i.e., composites) and is driven by the form and semantics of those operators and operands. In contrast, conventional optimizing strategies wait until the domain specific operators and operands (i.e., composites) have been compiled into programming language level code (e.g., C) before they even start the optimization process. By this time, the data flow, variable aliasing, and variable dependency knowledge implicit in the domain specific operators and operands has been lost. So, the first step in conventional optimization is to perform a difficult analysis process to recover this lost information, which will then be used to drive the optimization process. AO avoids such difficulties by using the implicit knowledge to directly generate optimized code.