Combining static analysis and profiling for estimating execution times

Effective static analyses have been proposed which infer bounds on the number of resolutions. These have the advantage of being independent from the platform on which the programs are executed and have been shown to be useful in a number of applications, such as granularity control in parallel execution. On the other hand, in distributed computation scenarios where platforms with different capabilities come into play, it is necessary to express costs in metrics that include the characteristics of the platform. In particular, it is specially interesting to be able to infer upper and lower bounds on actual execution times. With this objective in mind, we propose an approach which combines compile-time analysis for cost bounds with a one-time profiling of a given platform in order to determine the valúes of certain parameters for that platform. These parameters calibrate a cost model which, from then on, is able to compute statically time bound functions for procedures and to predict with a significant degree of accuracy the execution times of such procedures in that concrete platform. The approach has been implemented and integrated in the CiaoPP system.

Experiments in context-sensitive analysis of modular programs

Several models for context-sensitive analysis of modular programs have been proposed, each with different characteristics and representing different trade-offs. The advantage of these context-sensitive analyses is that they provide information which is potentially more accurate than that provided by context-free analyses. Such information can then be applied to validating/debugging the program and/or to specializing the program in order to obtain important performance improvements. Some very preliminary experimental results have also been reported for some of these models which provided initial evidence on their potential. However, further experimentation, which is needed in order to understand the many issues left open and to show that the proposed modes scale and are usable in the context of large, real-life modular programs, was left as future work. The aim of this paper is two-fold. On one hand we provide an empirical comparison of the different models proposed in previous work, as well as experimental data on the different choices left open in those designs. On the other hand we explore the scalability of these models by using larger modular programs as benchmarks. The results have been obtained from a realistic implementation of the models, integrated in a production-quality compiler (CiaoPP/Ciao). Our experimental results shed light on the practical implications of the different design choices and of the models themselves. We also show that contextsensitive analysis of modular programs is indeed feasible in practice, and that in certain critical cases it provides better performance results than those achievable by analyzing the whole program at once, specially in terms of memory consumption and when reanalyzing after making changes to a program, as is often the case during program development.

Efficient top-down set-sharing analysis using cliques

Abstract. We study the problem of efficient, scalable set-sharing analysis of logic programs. We use the idea of representing sharing information as a pair of abstract substitutions, one of which is a worst-case sharing representation called a clique set, which was previously proposed for the case of inferring pair-sharing. We use the clique-set representation for (1) inferring actual set-sharing information, and (2) analysis within a top-down framework. In particular, we define the new abstract functions required by standard top-down analyses, both for sharing alone and also for the case of including freeness in addition to sharing. We use cliques both as an alternative representation and as widening, defining several widening operators. Our experimental evaluation supports the conclusión that, for inferring set-sharing, as it was the case for inferring pair-sharing, precisión losses are limited, while useful efficieney gains are obtained. We also derive useful conclusions regarding the interactions between thresholds, precisión, efficieney and cost of widening. At the limit, the clique-set representation allowed analyzing some programs that exceeded memory capacity using classical sharing representations.

Multivariant non-failure analysis via standard abstract interpretation

Non-failure analysis aims at inferring that predicate calis in a program will never fail. This type of information has many applications in functional/logic programming. It is essential for determining lower bounds on the computational cost of calis, useful in the context of program parallelization, instrumental in partial evaluation and other program transformations, and has also been used in query optimization. In this paper, we re-cast the non-failure analysis proposed by Debray et al. as an abstract interpretation, which not only allows to investígate it from a standard and well understood theoretical framework, but has also several practical advantages. It allows us to incorpórate non-failure analysis into a standard, generic abstract interpretation engine. The analysis thus benefits from the fixpoint propagation algorithm, which leads to improved information propagation. Also, the analysis takes advantage of the multi-variance of the generic engine, so that it is now able to infer sepárate non-failure information for different cali patterns. Moreover, the implementation is simpler, and allows to perform non-failure and covering analyses alongside other analyses, such as those for modes and types, in the same framework. Finally, besides the precisión improvements and the additional simplicity, our implementation (in the Ciao/CiaoPP multiparadigm programming system) also shows better efRciency.

Global analysis of standard prolog programs

Abstract interpretation-based data-flow analysis of logic programs is, at this point, relatively well understood from the point of view of general frameworks and abstract domains. On the other hand, comparatively little attention has been given to the problems which arise when analysis of a full, practical dialect of the Prolog language is attempted, and only few solutions to these problems have been proposed to date. Existing proposals generally restrict in one way or another the classes of programs which can be analyzed. This paper attempts to fill this gap by considering a full dialect of Prolog, essentially the recent ISO standard, pointing out the problems that may arise in the analysis of such a dialect, and proposing a combination of known and novel solutions that together allow the correct analysis of arbitrary programs which use the full power of the language.

Goal dependent vs goal independent analysis of logic programs

Goal independent analysis of logic programs is commonly discussed in the context of the bottom-up approach. However, while the literature is rich in descriptions of top-down analysers and their application, practical experience with bottom-up analysis is still in a preliminary stage. Moreover, the practical use of existing top-down frameworks for goal independent analysis has not been addressed in a practical system. We illustrate the efficient use of existing goal dependent, top-down frameworks for abstract interpretation in performing goal independent analyses of logic programs much the same as those usually derived from bottom-up frameworks. We present several optimizations for this flavour of top-down analysis. The approach is fully implemented within an existing top-down framework. Several implementation tradeoffs are discussed as well as the influence of domain characteristics. An experimental evaluation including a comparison with a bottom-up analysis for the domain Prop is presented. We conclude that the technique can offer advantages with respect to standard goal dependent analyses.

On the practicality of global flow analysis of logic programs

This paper addresses the issue of the practicality of global flow analysis in logic program compilation, in terms of both speed and precision of analysis. It discusses design and implementation aspects of two practical abstract interpretation-based flow analysis systems: MA3, the MOO Andparallel Analyzer and Annotator; and Ms, an experimental mode inference system developed for SB-Prolog. The paper also provides performance data obtained from these implementations. Based on these results, it is concluded that the overhead of global flow analysis is not prohibitive, while the results of analysis can be quite precise and useful.

Programming with global analysis

Global data-flow analysis of (constraint) logic programs, which is generally based on abstract interpretation [7], is reaching a comparatively high level of maturity. A natural question is whether it is time for its routine incorporation in standard compilers, something which, beyond a few experimental systems, has not happened to date. Such incorporation arguably makes good sense only if: • the range of applications of global analysis is large enough to justify the additional complication in the compiler, and • global analysis technology can deal with all the features of "practical" languages (e.g., the ISO-Prolog built-ins) and "scales up" for large programs. We present a tutorial overview of a number of concepts and techniques directly related to the issues above, with special emphasis on the first one. In particular, we concéntrate on novel uses of global analysis during program development and debugging, rather than on the more traditional application área of program optimization. The idea of using abstract interpretation for validation and diagnosis has been studied in the context of imperative programming [2] and also of logic programming. The latter work includes issues such as using approximations to reduce the burden posed on programmers by declarative debuggers [6, 3] and automatically generating and checking assertions [4, 5] (which includes the more traditional type checking of strongly typed languages, such as Gódel or Mercury [1, 8, 9]) We also review some solutions for scalability including modular analysis, incremental analysis, and widening. Finally, we discuss solutions for dealing with meta-predicates, side-effects, delay declarations, constraints, dynamic predicates, and other such features which may appear in practical languages. In the discussion we will draw both from the literature and from our experience and that of others in the development and use of the CIAO system analyzer. In order to emphasize the practical aspects of the solutions discussed, the presentation of several concepts will be illustrated by examples run on the CIAO system, which makes extensive use of global analysis and assertions.

A practical application of sharing and freeness inference

Abstract is not available.

A generic framework for context-sensitive analysis of modular programs

Context-sensitive analysis provides information which is potentially more accurate than that provided by context-free analysis. Such information can then be applied in order to validate/debug the program and/or to specialize the program obtaining important improvements. Unfortunately, context-sensitive analysis of modular programs poses important theoretical and practical problems. One solution, used in several proposals, is to resort to context-free analysis. Other proposals do address context-sensitive analysis, but are only applicable when the description domain used satisfies rather restrictive properties. In this paper, we argüe that a general framework for context-sensitive analysis of modular programs, Le., one that allows using all the domains which have proved useful in practice in the non-modular setting, is indeed feasible and very useful. Driven by our experience in the design and implementation of analysis and specialization techniques in the context of CiaoPP, the Ciao system preprocessor, in this paper we discuss a number of design goals for context-sensitive analysis of modular programs as well as the problems which arise in trying to meet these goals. We also provide a high-level description of a framework for analysis of modular programs which does substantially meet these objectives. This framework is generic in that it can be instantiated in different ways in order to adapt to different contexts. Finally, the behavior of the different instantiations w.r.t. the design goals that motivate our work is also discussed.

Two efficient representations for set-sharing analysis in logic programs

Set-Sharing analysis, the classic Jacobs and Langen's domain, has been widely used to infer several interesting properties of programs at compile-time such as occurs-check reduction, automatic parallelization, flnite-tree analysis, etc. However, performing abstract uniflcation over this domain implies the use of a closure operation which makes the number of sharing groups grow exponentially. Much attention has been given in the literature to mitígate this key inefficiency in this otherwise very useful domain. In this paper we present two novel alternative representations for the traditional set-sharing domain, tSH and tNSH. which compress efficiently the number of elements into fewer elements enabling more efficient abstract operations, including abstract uniflcation, without any loss of accuracy. Our experimental evaluation supports that both representations can reduce dramatically the number of sharing groups showing they can be more practical solutions towards scalable set-sharing.

Some issues in analysis and specialization of modular ciao-prolog programs

Separating programs into modules is a well-known technique which has proven very useful in program development and maintenance. Starting by introducing a number of possible scenarios, in this paper we study different issues which appear when developing analysis and specialization techniques for modular logic programming. We discuss a number of design alternatives and their consequences for the different scenarios considered and describe where applicable the decisions made in the Ciao system analyzer and specializer. In our discussion we use the module system of Ciao Prolog. This is both for concreteness and because Ciao Prolog is a second-generation Prolog system which has been designed with global analysis and specialization in mind, and which has a strict module system. The aim of this work is not to provide a theoretical basis on modular analysis and specialization, but rather to discuss some interesting practical issues.

Electromagnetic analysis of periodic structures under a waveguide viewpoint

The fundamental objective of this Ph. D. dissertation is to demonstrate that, under particular circumstances which cover most of the structures with practical interest, periodic structures can be understood and analyzed by means of closed waveguide theories and techniques. To that aim, in the first place a transversely periodic cylindrical structure is considered and the wave equation, under a combination of perfectly conducting and periodic boundary conditions, is studied. This theoretical study runs parallel to the classic analysis of perfectly conducting closed waveguides. Under the light shed by the aforementioned study it is clear that, under certain very common periodicity conditions, transversely periodic cylindrical structures share a lot of properties with closed waveguides. Particularly, they can be characterized by a complete set of TEM, TE and TM modes. As a result, this Ph. D. dissertation introduces the transversely periodic waveguide concept. Once the analogies between the modes of a transversely periodic waveguide and the ones of a closed waveguide have been established, a generalization of a well-known closed waveguide characterization method, the generalized Transverse Resonance Technique, is developed for the obtention of transversely periodic modes. At this point, all the necessary elements for the consideration of discontinuities between two different transversely periodic waveguides are at our disposal. The analysis of this type of discontinuities will be carried out by means of another well known closed waveguide method, the Mode Matching technique. This Ph. D. dissertation contains a sufficient number of examples, including the analysis of a wire-medium slab, a cross-shaped patches periodic surface and a parallel plate waveguide with a textured surface, that demonstrate that the Transverse Resonance Technique - Mode Matching hybrid is highly precise, efficient and versatile. Thus, the initial statement: ”periodic structures can be understood and analyzed by means of closed waveguide theories and techniques”, will be corroborated. Finally, this Ph. D. dissertation contains an adaptation of the aforementioned generalized Transverse Resonance Technique by means of which the analysis of laterally open periodic waveguides, such as the well known Substrate Integrated Waveguides, can be carried out without any approximation. The analysis of this type of structures has suscitated a lot of interest in the recent past and the previous analysis techniques proposed always resorted to some kind of fictitious wall to close the structure. vii Resumen El principal objetivo de esta tesis doctoral es demostrar que, bajo ciertas circunstancias que se cumplen para la gran mayoría de estructuras con interés práctico, las estructuras periódicas se pueden analizar y entender con conceptos y técnicas propias de las guías de onda cerradas. Para ello, en un primer lugar se considera una estructura cilíndrical transversalmente periódica y se estudia la ecuación de onda bajo una combinación de condiciones de contorno periódicas y de conductor perfecto. Este estudio teórico y de caracter general, sigue el análisis clásico de las guías de onda cerradas por conductor eléctrico perfecto. A la luz de los resultados queda claro que, bajo ciertas condiciones de periodicidad (muy comunes en la práctica) las estructuras cilíndricas transversalmente periódicas guardan multitud de analogías con las guías de onda cerradas. En particular, pueden ser descritas mediante un conjunto completo de modos TEM, TE y TM. Por ello, ésta tesis introduce el concepto de guía de onda transversalmente periódica. Una vez establecidas las similitudes entre las soluciones de la ecuación de onda, bajo una combinación de condiciones de contorno periódicas y de conductor perfecto, y los modos de guías de onda cerradas, se lleva a cabo, con éxito, la adaptación de un conocido método de caracterización de guías de onda cerradas, la técnica de la Resonancia Transversal Generalizada, para la obtención de los modos de guías transversalmente periódicas. En este punto, se tienen todos los elementos necesarios para considerar discontinuidades entre guías de onda transversalmente periódicas. El analisis de este tipo de discontinuidades se llevará a cabo mediante otro conocido método de análisis de estructuras cerradas, el Ajuste Modal. Esta tesis muestra multitud de ejemplos, como por ejemplo el análisis de un wire-medium slab, una superficie de parches con forma de cruz o una guía de placas paralelas donde una de dichas placas tiene cierta textura, en los que se demuestra que el método híbrido formado por la Resonancia Transversal Generalizada y el Ajuste Modal, es tremendamente preciso, eficiente y versátil y confirmará la validez de el enunciado inicial: ”las estructuras periódicas se pueden analizar y entender con conceptos y técnicas propias de las guías de onda cerradas” Para terminar, esta tésis doctoral incluye también una modificación de la técnica de la Resonancia Transversal Generalizada mediante la cual es posible abordar el análisis de estructuras periódica abiertas en los laterales, como por ejemplo las famosas guías de onda integradas en sustrato, sin ninguna aproximación. El análisis de este tipo de estructuras ha despertado mucho interés en los últimos años y las técnicas de análisis propuestas hasta ix el momento acostumbran a recurrir a algún tipo de pared ficticia para simular el carácter abierto de la estructura.

Termination and cost analysis: Complexity and precision issues

The research in this thesis is related to static cost and termination analysis. Cost analysis aims at estimating the amount of resources that a given program consumes during the execution, and termination analysis aims at proving that the execution of a given program will eventually terminate. These analyses are strongly related, indeed cost analysis techniques heavily rely on techniques developed for termination analysis. Precision, scalability, and applicability are essential in static analysis in general. Precision is related to the quality of the inferred results, scalability to the size of programs that can be analyzed, and applicability to the class of programs that can be handled by the analysis (independently from precision and scalability issues). This thesis addresses these aspects in the context of cost and termination analysis, from both practical and theoretical perspectives. For cost analysis, we concentrate on the problem of solving cost relations (a form of recurrence relations) into closed-form upper and lower bounds, which is the heart of most modern cost analyzers, and also where most of the precision and applicability limitations can be found. We develop tools, and their underlying theoretical foundations, for solving cost relations that overcome the limitations of existing approaches, and demonstrate superiority in both precision and applicability. A unique feature of our techniques is the ability to smoothly handle both lower and upper bounds, by reversing the corresponding notions in the underlying theory. For termination analysis, we study the hardness of the problem of deciding termination for a speci�c form of simple loops that arise in the context of cost analysis. This study gives a better understanding of the (theoretical) limits of scalability and applicability for both termination and cost analysis.

Data-Flow analysis of prolog programs with extra-logical features

Abstract interpretation-based data-flow analysis of logic programs is at this point relatively well understood from the point of view of general frameworks and abstract domains. On the other hand, comparatively little attention has been given to the problems which arise when analysis of a full, practical dialect of the Prolog language is attempted, and only few solutions to these problems have been proposed to date. Such problems relate to dealing correctly with all builtins, including meta-logical and extra-logical predicates, with dynamic predicates (where the program is modified during execution), and with the absence of certain program text during compilation. Existing proposals for dealing with such issues generally restrict in one way or another the classes of programs which can be analyzed if the information from analysis is to be used for program optimization. This paper attempts to fill this gap by considering a full dialect of Prolog, essentially following the recently proposed ISO standard, pointing out the problems that may arise in the analysis of such a dialect, and proposing a combination of known and novel solutions that together allow the correct analysis of arbitrary programs using the full power of the language.