Abstract
In previous work we have shown that more precise type analysis can be achieved by exploiting union types and static single assignment (SSA) intermediate representation (IR) of code.
In this paper we exploit static single information (SSI), an extension of SSA proposed in literature and adopted by some compilers, to allow assignments of more precise types to variables in conditional branches. In particular, SSI can be exploited rather easily and effectively to infer more precise types in dynamic object-oriented languages, where explicit runtime typechecking is frequently used.
We show how the use of SSI form can be smoothly integrated with abstract compilation, our approach to static type analysis. In particular, we define abstract compilation based on union and nominal types for a simple dynamic object-oriented language in SSI form with a runtime typechecking operator, to show how precise type inference can be.
This work has been partially supported by MIUR DISCO - Distribution, Interaction, Specification, Composition for Object Systems.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
An, J., Chaudhuri, A., Foster, J.S., Hicks, M.: Dynamic inference of static types for Ruby. In: POPL, pp. 459–472 (2011)
Ananian, C.S.: The static single information form. Technical Report MITLCS-TR-801. MIT (1999)
Ancona, D., Ancona, M., Cuni, A., Matsakis, N.: RPython: a Step Towards Reconciling Dynamically and Statically Typed OO Languages. In: DLS 2007, pp. 53–64. ACM (2007)
Ancona, D., Corradi, A., Lagorio, G., Damiani, F.: Abstract Compilation of Object-Oriented Languages into Coinductive CLP(X): Can Type Inference Meet Verification? In: Beckert, B., Marché, C. (eds.) FoVeOOS 2010. LNCS, vol. 6528, pp. 31–45. Springer, Heidelberg (2011)
Ancona, D., Lagorio, G.: Coinductive Type Systems for Object-Oriented Languages. In: Drossopoulou, S. (ed.) ECOOP 2009. LNCS, vol. 5653, pp. 2–26. Springer, Heidelberg (2009)
Ancona, D., Lagorio, G.: Idealized coinductive type systems for imperative object-oriented programs. RAIRO - Theoretical Informatics and Applications 45(1), 3–33 (2011)
Anderson, C., Giannini, P., Drossopoulou, S.: Towards Type Inference for JavaScript. In: Gao, X.-X. (ed.) ECOOP 2005. LNCS, vol. 3586, pp. 428–452. Springer, Heidelberg (2005)
Cytron, R., Ferrante, J., Rosen, B.K., Wegman, M.N., Zadeck, F.K.: Efficiently computing static single assignment form and the control dependence graph. TOPLAS 13, 451–490 (1991)
Das, D., Ramakrishna, U.: A practical and fast iterative algorithm for phi-function computation using DJ graphs. TOPLAS 27(3), 426–440 (2005)
Alpern, B., et al.: The jalapeño virtual machine. IBM Systems Journal 39 (2000)
Foster, J.S., Terauchi, T., Aiken, A.: Flow-sensitive type qualifiers. In: PLDI, pp. 1–12 (2002)
Griesemer, R., Mitrovic, S.: A compiler for the java hotspottm virtual machine. In: The School of Niklaus Wirth, ”The Art of Simplicity”, pp. 133–152 (2000)
Heidegger, P., Thiemann, P.: Recency Types for Analyzing Scripting Languages. In: D’Hondt, T. (ed.) ECOOP 2010. LNCS, vol. 6183, pp. 200–224. Springer, Heidelberg (2010)
Holloway, G.: The machine-SUIF static single assignment library. Technical report, Harvard School of Engineering and Applied Sciences (2001)
Novillo, D.: Tree SSA - a new optimization infrastructure for GCC. In: GCC Developers’ Summit, pp. 181–193 (2003)
Simon, L., Bansal, A., Mallya, A., Gupta, G.: Co-Logic Programming: Extending Logic Programming with Coinduction. In: Arge, L., Cachin, C., Jurdziński, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol. 4596, pp. 472–483. Springer, Heidelberg (2007)
Simon, L., Mallya, A., Bansal, A., Gupta, G.: Coinductive Logic Programming. In: Etalle, S., Truszczyński, M. (eds.) ICLP 2006. LNCS, vol. 4079, pp. 330–345. Springer, Heidelberg (2006)
Singer, J.: Static single information form in machine SUIF. Technical report, University of Cambridge Computer Laboratory, UK (2004)
Singer, J.: Static Program Analysis based on Virtual Register Renaming. PhD thesis, Christs College (2005)
Tavares, A., Pereira, F.M., Bigonha, M., Bigonha, R.: Efficient SSI conversion. In: SBLP 2010 (2010)
Winther, J.: Guarded type promotion (eliminating redundant casts in Java). In: FTfJP 2011. ACM (2011)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 IFIP International Federation for Information Processing
About this paper
Cite this paper
Ancona, D., Lagorio, G. (2012). Static Single Information Form for Abstract Compilation. In: Baeten, J.C.M., Ball, T., de Boer, F.S. (eds) Theoretical Computer Science. TCS 2012. Lecture Notes in Computer Science, vol 7604. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-33475-7_2
Download citation
DOI: https://doi.org/10.1007/978-3-642-33475-7_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-33474-0
Online ISBN: 978-3-642-33475-7
eBook Packages: Computer ScienceComputer Science (R0)