|
Abstract : |
This paper introduces design-driven compilation, an approach in which the compiler uses design information to drive its analysis and verify that the program conforms to its design. Although this requires the programmer to formally specify some additional design information, it offers a range of benefits, such as: fidelity to the designer's high-level expectations, early and automatic detection of design nonconformance bugs; analysis modularity, with support for local analysis, separate compilation, and library support; and simplicity and efficiency of the compiler. We consider that the appropriate abstraction level for design information is the procedure level, with design specifications expressed as procedure interfaces. The key to the success of our approach is to combine high-level design specifications with powerful static analysis algorithms that handle the low-level details of verifying the design information. This paper reports our experience using design-driven compilation to automatically parallelize divide and conquer programs. The designer provides a design specification for pointer information, in the form of partial transfer functions, as well as a design specification for the regions of memory that each procedure accesses. The compiler first verifies the two pieces of design information then uses these specifications to detect the procedures that can execute in parallel. Our experimental results show that this approach enables the compiler to automatically parallelize a range of divide and conquer programs, that the complexity of the compiler decreases while its efficiency increases, and that, compared to the program, the design information is small, intuitive, and easy to provide., |
