Addressing Fundamental Bottlenecks in Link-Time and Dynamic Optimization

The popularity of object-oriented programming languages, component libraries, and dynamically linked libraries all significantly limit the effectiveness of static analysis and optimization. These trends have led to significant recent interest in link-time interprocedural optimization and runtime optimization. Unfortunately, these approaches present some difficult technical challenges that have limited their use so far. One common limitation is that machine-level object code (the output of traditional source-level compilers) can be very diflicult to analyze and transform. Link-time and runtime optimizers working with machine code generally cannot perform sophisticated high-level analyses and optimizations, e.g., sophisticated pointer analysis exploiting high-level type information and function signatures, data structure layout reorganization, loop transformations requiring array dependence analysis, and many others. A second fundamental limitation of runtime optimization is its runtime overhead, which remains a major limiting factor despite a long history of research. There appears little reason to believe that this fundamental trade-off can be mitigated through software alone.