In English. Summaries in Estonian

Proceedings of the Estonian Academy of Sciences.


Volume 11 No. 4 December 2005


Special issue on Programming Languages and Software Tools


Preface; 267–268

Kai Koskimies and Merik Meriste

Binary code compression based on decision trees; 269–285

Tamás Gergely, Ferenc Havasi and Tibor Gyimóthy

Abstract. More and more embedded systems are used in the world. These machines have limited resources as, e.g., the background storage size. It is important to increase the storage capacity of these machines. A possible solution for this is compressing the files before they are written on the storage device. This is usually done by a general compresssor. There are files containing text or binary data and in many cases binary program code. A general compressor compresses all of them with almost the same efficiency. But a compressor, specialized for one type of input, would compress files of that type much better; thus using many special compressors would save space and increase the virtual capacity of the storage device. Using this idea, our goal was to create a compression algorithm for binary program code. Most compression methods can be separated into two parts: the model and the coder. In this paper we introduce a decision-tree based modelling method. We combined this method with an arithmetic coder and applied it in a modified JFFS2 file system of a Linux distribution, running on a PDA machine. The original file system used only one method for file compression (zlib), the modified file system uses many compressors, including our model-based one. This PDA machine has an ARM processor; thus our method was implemented for the compression of ARM instructions. The results were very promising: depending on the parameters of the method, at least 12.6% of the 13 MB image, created with only zlib compression, were saved, and it costed boot speed slowdown only at most 3 times.

Key words: embedded system, code compression, decision trees.

General flow-sensitive pointer analysis and call graph construction; 286–295

Endre Horváth, István Forgács, Ákos Kiss, Judit Jász and

Tibor Gyimóthy

Abstract. Pointer analysis is a well known, widely used and very important static program analysis technique. After having studied the literature in this field of research we found that most of the methods approach the problem in a flow-insensitive way, i.e. they do not use the control-flow information. Our goal was to develop a technique that is flow-sensitive and can be used in the analysis of large programs. During this process we have found that this method can give more accurate results if we build the call graph and compute the pointer information at the same time. In this paper we present two of our algorithms for pointer analysis and give some examples to help their comprehension. In the future these algorithms are planned to form the basis of a flow- and context-sensitive method, to be used in the impact analysis of real life applications.

Key words: pointer analysis, flow-sensitive, interprocedural.

A stylebase as a tool for modelling of quality-driven software architecture; 296–312

Janne Merilinna and Eila Niemelä

Abstract. The main goal of model-driven engineering (MDE) is to improve software quality by using models as a means of producing high-quality systems with decreased development costs. Thus MDE makes it possible to represent software solutions by models and to evaluate and maintain models instead of the source code. However, software quality, i.e. quality of models, depends on how the quality characteristics of a system or a systems family have been taken into account in the architecture development. The main contribution of this paper is a stylebase, a tool including architectural styles and patterns, and design patterns, intended to be used while architecting. The stylebase is an integrated part of the architect’s tooling environment, providing support for the design of the architecture and for quality evaluation of architectural models. The stylebase can be used as a part of a commercial tool and as an independent component of a distributed software development environment with heterogeneous modelling tools.

Key words: model-driven engineering, architectural pattern, design pattern, software quality.

Transfinite semantics in program slicing; 313–328

Härmel Nestra

Abstract. This paper studies mathematically some special kinds of transfinite trace semantics and investigates program slicing w.r.t. these semantics. Several general facts about slicing, which hold for a wide class of programming languages and their transfinite semantics, are proven. The principal part of the work is done on control flow graphs keeping the treatment abstracted from any concrete programming language. Structured control flow is not assumed but programs written in standard programming languages with structured control flow are among those to which our theory applies.

Key words: program slicing, transfinite semantics, transfinite iteration.

Commonalities of model relationships within product line processes; 329–346

Jari Peltonen and Maarit Harsu

Abstract. Product line processes use commonalities of products to provide the basis for various technological aids. From the point of view of the tool support, the most significant commonalities are the relationships among models. These relationships may cause interdependence of the model ele­ments and imply functionality to the tools supporting the process. Similarly, as the commonalities of the relationships within product line proces­ses provide the basis for automation, the commonalities of models and the relation­ships among different product line processes provide a common basis for the tool support for them. The main goal of our research is to pro­vide customizable tool support for product line processes in general. Hence, in this paper we study the nature and commonalities of models and model relationships in various product line processes from the viewpoint of tool support.

Key words: product line process, modelling, automation.

Towards compiler backend optimization for low energy consumption at instruction level; 347–357

Kimmo Surakka, Tommi Mikkonen, Hannu-Matti Järvinen,

Timo Vuorela and Jukka Vanhala

Abstract. Compiler backend is the part of a compiler that is responsible for generating compiled code. By optimizing the backend, one can easily create a tool chain for a new environment, where some restrictions are to be taken into account. One such restriction is energy consumption, which can be affected by code generation. In this paper, we discuss the different candidate optimizations that we have identified, and whether or not they can be implemented within the scope of the compiler backend.

Key words: energy consumption, compilers.


Contents of volume 11; 358–360