| dc.description |
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 <italic>O</italic>(<italic>n</italic> log <italic>n</italic>) time. This compile-time performance and
scalability is achieved through a novel combination of data structures and algorithms. |
|