SIMPLE AND EFFECTIVE ANALYSIS OF STATICALLY-TYPED OBJECT-ORIENTED PROGRAMS

To use modem hardware effectively, compilers need extensive control-fl ow information. Unfortunately, the frequent method invocations in obje ct-oriented languages obscure control flow. in this paper, we describe and evaluate a range of analysis techniques to convert method invocat ions into direct calls for statically-typed object-oriented languages and thus improve control-flow information in object-oriented languages . We present simple algorithms for type hierarchy analysis, aggregate analysis, and interprocedural and intraprocedural type propagation. Th ese algorithms are also fast, O(\procedures\ Sigma(p)(procedures) n( p) v(p)) worst case time (linear in practice) for our slowest analys is, where n(p) is the size of procedure p and v(p) is the number of va riables in procedure p, and are thus practical for use in a compiler. When they fail, we introduce cause analysis to reveal the source of im precision and suggest where more powerful algorithms may be warranted. We show that our simple analyses perform almost as well as an oracle that resolves all method invocations that invoke only a single procedu re.