Understanding and improving the performance of modern programming languages

Features of modern programming languages such as objects, method invocations, and automatic memory management have important software engineering benefits. Unfortunately, each of these features also have a performance overhead, and thus programs written in modern languages typically run slower than those written in traditional languages. This dissertation describes and evaluates fast techniques for reducing the overhead of two features of modern programming languages: objects and method invocations. To address the overhead of objects, and more specifically linked structures, we have designed a new alias analysis, type-based alias analysis (scTBAA), which uses types to disambiguate memory references in Modula-3 programs. scTBAA is fast: it is the first linear-time alias analysis algorithm. scTBAA is also the first alias analysis that analyzes heap objects and continues to be effective even if parts of the program are unavailable. We demonstrate that scTBAA reduces execution time for our programs by up to 10%. We also demonstrate, using our novel methodology, best possible analysis (scBPA), that scTBAA is close to perfect for our optimizations: we did not encounter any situations where a more powerful alias analysis is needed. To address the overhead of method invocations in object-oriented languages, and in particular, Modula-3, we have built and evaluated four type analyses, ranging from fast (worst-case linear) to quadratic time. Type hierarchy analysis resolves method invocations by examining the types in the program; Intraprocedural and interprocedural type propagation are intraprocedural and interprocedural data-flow analyses on types; Aggregate analysis incorporates scTBAA into intraprocedural and interprocedural type propagation. All except type hierarchy analysis work when parts of the program are unavailable. We demonstrate that our techniques for reducing the overhead of method invocations directly reduce execution time for our programs by up to 11% and indirectly reduce execution time by enabling compiler optimizations by up to 18%. We also demonstrate, using scBPA, that our type analyses are close to perfect: a more powerful analysis would resolve at most 7% more method invocations compared to our analyses. We also present a cause analysis which extends scBPA to pin point the weaknesses in our analyses