Portal de Periódicos da CAPES

Type-directed flow analysis for typed intermediate languages

1997; Springer Science+Business Media; Linguagem: Inglês

10.1007/bfb0032745

1611-3349

Suresh Jagannathan, Stephen Weeks, Andrew K. Wright,

Software Engineering Research

Flow analysis is especially valuable for optimizing functional languages because control-flow information is not syntactically apparent in higher-order programs. Flow analyses typically operate on untyped languages. However, recent compilers for typed functional languages such as ML and Haskell use a typed intermediate language to expose data representations for optimization. This paper presents a polyvariant flow analysis framework for the predicative subset of system F, a common basis for typed intermediate languages. Analyses in this framework can take advantage of types to analyze programs more precisely. We study a specific analysis called S RT that uses types to control polyvariance. We prove that S RT respects types: whenever it assigns abstract value $$\hat \upsilon$$ to a variable and the type system assigns type σ to the same variable, then $$\left[ {\hat \upsilon } \right] \subseteq \left[ \sigma \right]$$ , where [ · ] denotes a set of values. S RT does not terminate 1569 1655 V 3 for some programs. We present several variants of S RT that are better suited to practical use.