Dissertation/Thesis Abstract

Flow-Sensitive Control-Flow Analysis in Linear-Log Time
by Adams, Michael D., Ph.D., Indiana University, 2011, 266; 3488016
Abstract (Summary)

The flexibility of dynamically typed languages such as JavaScript, Python, Ruby, and Scheme comes at the cost of run-time type checks. Some of these checks can be eliminated via control-flow analysis. However, traditional control-flow analysis (CFA) is not ideal for this task as it ignores flow-sensitive information that can be gained from dynamic type predicates, such as JavaScript's instanceof and Scheme's pair?, and from type-restricted operators, such as Scheme's car. Yet, adding flow-sensitivity to a traditional CFA worsens the already significant compile-time cost of traditional CFA. This makes it unsuitable for use in just-in-time compilers.

In response, this dissertation presents a fast, flow-sensitive type-recovery algorithm based on the linear-time, flow-insensitive sub-0CFA. The algorithm has been implemented as an experimental optimization into Chez Scheme compiler, where it has proven to be effective, justifying the elimination of about 60% of run-time type checks in a large set of bench-marks. The algorithm processes on average over 100,000 lines of code per second and scales well asymptotically, running in only O(n log n) time. This compile-time performance and scalability is achieved through a novel combination of data structures and algorithms.

Supplemental Files

Some files may require a special program or browser plug-in. More Information

Indexing (document details)
Advisor: Dybvig, R. Kent
Commitee: Ahmed, Amal, Leivant, Daniel, Sabry, Amr
School: Indiana University
Department: Informatics
School Location: United States -- Indiana
Source: DAI-B 73/04, Dissertation Abstracts International
Subjects: Computer science
Keywords: Control-flow, Flow sensitivity, Linear-log time, Type recovery
Publication Number: 3488016
ISBN: 978-1-267-07777-6
Copyright © 2021 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy