Annotation Language

The goal of the annotation language is to convey library-specific information to the compiler in a simple declarative manner. While it's clear that more sophisticated specifications could support more sophisticated optimizations, our goal is to show that a few simple annotations can enable many useful optimizations. Simplicity is important because we expect our language users to be library experts who do not necessarily have expertise in compilers or formal specifications.

In designing the language, we studied several libraries to determine the most useful ways of optimizing them. We noticed that library operations could easily be integrated into many traditional optimizations, such as dead-code elimination, copy propagation and loop-invariant code motion. These optimizations are effective and well understood, and they require only minimal information to enable. For example, to enable loop invariant code motion, the annotations need to indicate which library procedures have no side-effects. We also observed that many library-specific optimizations replace a general-purpose library call with a more specific one that takes advantage of information about the calling context. This form of specialization not only improves performance, it often creates additional opportunities for traditional optimizations. Thus, our annotation language consists of two classes of annotations: basic annotations for enabling traditional optimizations, and advanced annotations for specifying library-specific specialization.

  

Figure: Part of the annotations for the PLAPACK parallel linear algebra library. (1) The header provides access to definitions in the library header files. (2) The property annotations define abstract object states which are used for analysis and specialization. (3) Each library procedure has its own set of annotations. (4) The basic annotations summarize the dataflow and pointer behavior of the procedure. (5) The advanced annotations specify analysis rules for abstract interpretation and specialization rules that use the resulting information.

We present the annotation language by first describing the target library: the PLAPACK parallel linear algebra library [25]. The remainder of the section then describes the language constructs in detail, using a fragment of the PLAPACK annotations as a source of examples. These annotations capture the information used to produce the results in Section . A complete grammar is presented in the appendix.