Type analysis of Prolog is of primary importance for high-performance compilers since type information may lead to better indexing and to sophisticated specializations of unification and built-in predicates, to name a few. However, these optimization often require a sophisticated type inference system capable of inferring disjunctive and recursive types, and hence expensive in computation time. The purpose of this paper is to describe a type analysis system for Prolog based on abstract interpretation and type graphs (i.e., disjunctive rational trees) with this functionality. The system (about 15,000 lines of C) consists of the combination of a generic fixpoint algorithm, a generic pattern domain, and a type graph domain. The main contribution of the paper is to show that this approach can be engineered to be practical for medium-sized programs without sacrificing accuracy. The main technical contribution to achieve this result is a novel widening operator for type graphs which appears to be accurate and effective in keeping the sizes of the graphs, and hence the computation time, reasonably small.
