Efficient local type inference
- 19 October 2008
- conference paper
- conference paper
- Published by Association for Computing Machinery (ACM)
- Vol. 43 (10), 475-492
- https://doi.org/10.1145/1449764.1449802
Abstract
Inference of static types for local variables in Java bytecode is the first step of any serious tool that manipulates bytecode, be it for decompilation, transformation or analysis. It is important, therefore, to perform that step as accurately and efficiently as possible. Previous work has sought to give solutions with good worst-case complexity. We present a novel algorithm, which is optimised for the common case rather than worst-case performance. It works by first finding a set of minimal typings that are valid for all assignments, and then checking whether these minimal typings satisfy all uses. Unlike previous algorithms, it does not explicitly build a data structure of type constraints, and it is easy to implement efficiently. We prove that the algorithm produces a typing that is both sound (obeying the rules of the language) and as tight as possible. We then go on to present extensive experiments, comparing the results of the new algorithm against the previously best known method. The experiments include bytecode that is generated in other ways than compilation of Java source. The new algorithm is always faster, typically by a factor 6, but on some real benchmarks the gain is as high as a factor of 92. Furthermore, whereas that previous method is sometimes suboptimal, our algorithm always returns a tightest possible type. We also discuss in detail how we handle primitive types, which is a difficult issue due to the discrepancy in their treatment between Java bytecode and Java source. For the application to decompilation, however, it is very important to handle this correctly.Keywords
This publication has 13 references indexed in Scilit:
- Efficient local type inferenceACM SIGPLAN Notices, 2008
- Converting java programs to use generic librariesPublished by Association for Computing Machinery (ACM) ,2004
- Decompiling Java Bytecode: Problems, Traps and PitfallsLecture Notes in Computer Science, 2002
- Type elaboration and subtype completion for Java bytecodeACM Transactions on Programming Languages and Systems, 2001
- The Cartesian Product AlgorithmPublished by Springer Science and Business Media LLC ,2000
- Efficient Inference of Object TypesInformation and Computation, 1995
- Type inference of SELF: Analysis of objects with dynamic and multiple inheritanceSoftware: Practice and Experience, 1995
- Efficient inference of partial typesJournal of Computer and System Sciences, 1994
- Inferring types in SmalltalkPublished by Association for Computing Machinery (ACM) ,1981
- Power domainsJournal of Computer and System Sciences, 1978