Allyn Dimock, Ian Westmacott, Robert Muller, Franklyn Turbak, J. B.
Wells, and Jeffrey Considine
Program
representation size in an intermediate language with intersection and union
types
In Types in Compilation, Third Int'l Workshop, TIC 2000, volume
2071 of LNCS, pages 27-52 Springer-Verlag, 2001
The CIL compiler for core Standard ML compiles whole
programs using the CIL typed intermediate language
with flow labels and intersection and union
types. Flow labels embed flow information in the
types and intersection and union types support
precise polyvariant type and flow information,
without the use of type-level abstraction or
quantification.
Compile-time representations of CIL types and terms
are potentially large compared to those for similar
types and terms in systems based on quantified
types. The listing-based nature of intersection and
union types, together with flow label annotations on
types, contribute to the size of CIL types. The CIL
term representation duplicates portions of the
program where intersection types are introduced and
union types are eliminated. This duplication makes
it easier to represent type information and to
introduce multiple representation conventions, but
incurs a compile-time space cost.
This paper presents empirical data on the
compile-time space costs of using CIL. These costs
can be made tractable using standard hash-consing
techniques. Surprisingly, the duplicating nature of
CIL has acceptable compile-time space performance in
practice on the benchmarks and flow analyses that we
have investigated. Increasing the precision of flow
analysis can significantly reduce compile-time space
costs. There is also preliminary evidence that the
flow information encoded in CIL's type system can
effectively guide data customization.
[ bib |
.html ]
Back
This file has been generated by
bibtex2html 1.61
Copyright notice: The documents contained
in these pages are included by the contributing authors as a means to
ensure timely dissemination of scholarly and technical work on a
non-commercial basis. Copyright and all rights therein are maintained
by the authors or by other copyright holders, notwithstanding that
they have offered their works here electronically. It is understood that all persons copying this information will
adhere to the terms and constraints invoked by each author's
copyright. These works
may not be reposted without the explicit permission of the copyright
holder.
If you experience problems downloading any of the files above,
it is most likely because your browser does not handle compressed
files correctly.
In particular, Netscape might save the file in the compressed
gz-format with extension .ps or
.pdf (indicating postscript or PDF, resp.). You can work around this by saving the file,
renaming it to .ps.gz or .pdf.gz, and then
uncrompress it.
