transformations. A large portion of maintenance efort is spent in understanding the logic of the original code. Our research presents an option to automatically transform a low-level program into a semantically equivalent version with high-level structures. Making the code more understandable with high-level structures can lead to faster and easier maintenance. This paper presents a case study on several implementations of the greatest common divisor in two low-level languages (assembly and MicroJava bytecode) and their SQAMIA 2022: Workshop on Software Quality, Analysis, Monitoring, Improvement, and Applications, September 11-14, ∗Corresponding author.
One of the most significant properties of software is its need to change due to new requirements or changes of the environment. By constantly changing a software product, the need for maintenance becomes more and more important, but at the same time more and more challenging. However, the maintainers are often left with low-level code or binaries as the only source of information about the program. Trying to understand the code and maintain it according to the needs can be a very costly process in the sense of necessary time and efort. This process often also relies on the experience and skills of the maintainer, which opens possibilities for additional errors. New developers are generally only trained in high-level languages, emphasising the problem. One solution for this is automation of the entire process by using helper tools which would make the original software more readable without causing new faults (of course given that the tools themselves are not faulty).
The research presented in this paper is based on FermaT transformation system and WSL
(Wide Spectrum Language) [
© 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). CEUR
This paper presents a case study on several implementations of the Euclidean algorithm (greatest common divisor), both in MicroJava bytecode and assembly. Being one of the first algorithms, it seems suitable to be one of the initial case studies of this research. The same automated transformation process has been applied to each of these samples and the results of the experiments have been presented.
The rest of the paper is organised as follows: Section 2 presents the case study of this paper, the greatest common divisor algorithm; in Section 3 the foundations of this work and the automated transformation process are explained; in Section 4 the related work is presented; Section 5 introduces the experiments and the results of this research and finally, in Section 6 we present the conclusions and the future work based on the observations made on current results.
The greatest common divisor algorithm (further referred to as GCD), or Euclidean algorithm is
considered to be one of the oldest nontrivial algorithms recorded. Its first written occurrence
was in Euclid’s Elements and it explains the calculation of the greatest common divisor of two
numbers [
The easiest and most natural approach to finding the GCD of two numbers would be to factor
both numbers and then multiply the common factors, raised to according powers. However, this
is far from the most eficient way of calculating the GCD and the Euclidean algorithm solves it
in a more eficient manner [
The original Euclidean algorithm is based on continuous subtraction. If A and B are two positive integers, their greatest common divisor can be found by continuously subtracting smaller from the larger value until they are equal. After the process is finished, any of the two numbers can be returned as the result.
The algorithm can also be represented as repeated calculation of the remainder of one number divided by another. The result is reached once the remainder is 0, and the repeated subtraction of the original algorithm can simply be replaced by remainder calculation in this improved version.
Current demands for software development are that it is delivered in the shortest time possible,
yet still with high level of quality and reliability. In order to preserve the reliability of the
software product, it is important to find means which would assure reliability throughout
diferent stages of the development process. As a solution to this problem, formal methods can
be used. Formal methods can be very useful for the overall reliability of software, since they can
be applied in diferent stages of software development and to diferent software artefacts [
WSL is a language used for reverse engineering of sequential systems [
WSL stands for Wide Spectrum Language, which describes its wide usage from abstract specifications to concrete runnable implementations. Apart from standard language constructs, WSL has another important extension, MetaWSL, used for writing code transformations in the language itself. Transformations are included in the system and their correctness can be automatically checked. Transformations can be of great use in processes such as creating programs from specifications, analysing programs and their properties or getting specifications from reverse engineering of programs.
Action systems are a special structure in WSL. It was designed to be able to emulate jumps and goto statements that are common to low-level programs. It consists of a collection of parameter-less procedures. One of them is marked as the start procedure and they can call each other with no limits. Once a procedure is finished, the control is returned to the call site. The only exception to this is the reserved name Z, a call to which immediately ends the execution of the whole action system. There can be multiple action systems in a program, and the flow of the program normally continues with the next statement when an action system terminates. There are three types of systems in relation to how the calls are used. The first one are recursive action systems, in which all of the calls return, and the system is terminated when the starting action terminates. The second one are the regular action systems in which the system is always terminated by a call to Z and none of the calls return to their sites. This type is important for many transformations, since this special property can be used for simplifications. The third type are the hybrid ones, which are a mix of the previous two, or, in other words, any that don’t fall into the previous categories.
Two tools were developed by the authors for translation of the original low-level code to
WSL – asm2wsl, which translates a subset of x86 assembly in the MASM/TASM dialect [
Transformations can be applied manually, by relying on one’s experience and expertise or
automatically, by using an existing helper tool [
Hill climbing [
After a transformation has been applied in the hill climbing process, the quality of the
potential solution is measured by a fitness function . The term draws its origin from evolutionary
computing. Generally speaking, the role of a fitness function is to define qualities which should
be met by a population. It defines the criteria for selection, which also means that it defines the
meaning of improvement. In terms of problem-solving, it represents the task which is solved in
evolutionary manner [
The fitness function indicates if the newly created solution shows an improvement, which
from the computing point of view means that it has better qualities for solving the problem at
hand. For this purpose, a simpler and more understandable program is the better one. Since the
iftness function represents the quality of a program as numeric values, the first choice are various
metric values. These metrics can be good indicators whether a solution is better structured
and therefore more understandable. In our previous work [
Both of the translation tools, as well as the transformation program are available under the terms of the GNU Public Licence on the project site1.
Although using hill climbing and fitness functions for automated reengineering is not so
widespread, there have been some tools and papers which share some of the ideas and objectives.
Hill climbing has not been frequently used for automatic program repair, however this approach
has been considered by Arcuri and Yao in [
Fitness functions have shown as useful in automated software repair for C programs [
FermaT has previously been successfully used in several industrial projects, where the original
assembly code was transformed to C and COBOL code. However, this process was significantly
adapted to the specific problems it was solving, unlike the hill climbing process which is always
the same and fully automated [
Using FermaT (possibly with a helper tool like FME), an experienced maintainer can raise the level of abstraction of low-level code. An example can be a direct implementation of subtracting the smaller number from the larger until they are the same in assembly, shown in Figure 1. It features macros with specific names that get recognised by the translator, as mentioned before. When this code is translated into WSL using asm2wsl it will expand into about 50 statements, which is an expected increase. A rather optimal path could be to apply the following transformations: Remove Redundant Vars, Flag Removal, Collapse Action System, Floop to while, Constant Propagation. The end result is a very clear implementation of Euclid’s algorithm in only 5 statements, shown in Figure 2. Note that the pretty printer for WSL is not in a C-like style, but leans much more toward a LISP-like indention, where the closing of a branching or a loop will be at the end of the block, on the same line, not in a new line on the same level as the opening.
start: mov mov compare: cmp je ja sub jmp greater: sub jmp ax,12 bx,8 ax,bx exit ;exit since they’re equal greater bx,ax compare ax,bx compare exit: ;exit out of the program print_num ax end_execution
Of course, since this is a program with hard coded starting values, the result is also always the same. Further simplification if possible by using Unroll loop and Constant propagation transformations repeatedly to just assign the final value 4 to ax and bx, and then even further into a simple PRINFLUSH(4).
Reaching this optimal path requires a lot of expertise from the maintainer and although very VAR < ax := 12, bx := 8 >: WHILE ax <> bx DO
IF ax >= bx THEN ax := ax - bx ELSE bx := bx - ax FI OD;
PRINFLUSH(ax) ENDVAR good final results could be achieved by manual selection and application of transformations, it is usually a much better option to use automated tools for these kinds of activities. Although the automated process might not reach the best solution using the same path as an expert would, the manual approach is in general less eficient by far in terms of the cost of the process.
There are several variants of the algorithm implementation that were used in these experiments. Some are written in assembly, and some in MicroJava and then compiled into bytecode. Many of these programs come in pairs, a variant with predefined values (i.e., hard coded) and a variant with user input for ax and bx. These are then usually marked with sufixes predef and input, respectively.
The first variant that will be presented is the one that was already discussed for a manual approach to transformations (Figure 1). The hill climbing process will automatically transform the program into the same version as already shown in Figure 2. It will do so by automatically ifnding and applying 27 transformations. This is a lot more than with the manual approach, but those were hand picked and targeted very precisely, and some of them are very complex, while here there is a lot of smaller and cheaper transformations for the same end result. During the process about 2300 transformations are tried, which took less than half a second on a 3GHz Intel processor.
The process that ran with the default structure metric as the fitness function did not simplify
the program further into a simple print, which was shown in the manual transformation example.
This is due to the fact that unrolling the loop increases the metric of the new program, and
it is therefore discarded by the process. In this case it would be required to look ahead 4
transformations to achieve an improvement of the fitness of the program. The problem, of
course, is that in a general case it is undecidable to know how many steps are required, or
indeed if there is a finite number of steps that would lead to an improvement, since this is a
variation of the halting problem [
Another variant of this program is with user inputs, instead of hard coded values. Macros are used for input operations, to avoid the specifics of interupts. The increase in the number of statements in the translated program is about ten. The transformed version of the program with inputs is shown in Figure 3. There are somewhat verbose parts that load the user input, but the core part of the algorithm is exactly the same as in the predef version. The process selected 34 transformations to achieve this version, which is inline with the slight increase of statements. On the other hand it tried almost 6000 transformations for this program, which is a significant increase. The time elapsed also doubled to about a second. However, this is natural for the process since it has a lot more statements to try transformations on.
PRINFLUSH(”num?$”); VAR < ax := 0, bx := 0, t_e_m_p := 0 >: @Read_Line_Proc( VAR t_e_m_p, Standard_Input_Port); bx := @String_To_Num(t_e_m_p); PRINT(””); PRINFLUSH(”num?$”); @Read_Line_Proc( VAR t_e_m_p, Standard_Input_Port); PRINT(””); ax := @String_To_Num(t_e_m_p); WHILE ax <> bx DO
IF ax > bx THEN ax := ax - bx ELSE bx := bx - ax FI OD; PRINFLUSH(<”res,$”>);
PRINFLUSH(ax) ENDVAR
The next experiment was to wrap the algorithm into a procedure, with a single call to it with predefined values. During the process the procedure gets inlined into the main program, the end result was the same as with gcd-predef. The increase in the number of transformations was low for this variant.
Another variant is a recursive one, with a procedure that will keep subtracting the smaller from the larger number and call itself until the numbers are the same. A diference to the version seen in gcd-predef is that this variant always ensures that ax is the larger number by swapping them when needed, which means that it always subtracts bx from ax. When this version is automatically transformed, the recursion is reduced to a while loop, as shown in Figure 4. WSL has a simultaneous assignment environment that can be seen in the Figure. Again, as with the previous examples, both the predef and input versions get transformed to the same core loop, and, again, the number of transformations tried with the second version is more than double.
WHILE ax <> bx DO
IF ax <= bx
THEN < ax := bx, bx := ax > FI; ax := ax - bx OD;
There are also several versions of the algorithm implemented in MicroJava, again with pairs of predefined values and user inputs.
One version is the same as seen in assembly – a while loop with subtraction of the smaller number from the larger number. This high-level code is then compiled into bytecode, which is translated into WSL. Unlike asm2wsl which created regular action systems, mjc2wsl creates recursive action systems, in which every call returns. It is then transformed with the same hill climbing program. The automatically transformed version (Figure 5) is again a very clear highlevel loop at the core part of the program, although it does leave a few additional stack operations. The names of the local variables are not encoded in the compiled files, so they get automated sequential names. These can mostly be simplified with additional manual transformations. The main reason they are left in the program is that sometimes the introduction of a VAR block can be a greater increase in the metrics than the removal of the stack operations.
Another version is the same as this one, just contained in a procedure. It gets transformed to the same core code as in Figure 5.
WHILE mjvm_locals_0 <> mjvm_locals_1 DO
IF mjvm_locals_0 > mjvm_locals_1
THEN mjvm_locals_0 := mjvm_locals_0 - mjvm_locals_1 FI; IF mjvm_locals_0 < mjvm_locals_1
THEN mjvm_locals_1 := mjvm_locals_1 - mjvm_locals_0 FI
OD;
The alternative version of this program, with predefined inputs, can actually be transformed into a single PRINFLUSH statement – that is the end result is correctly deduced in the process. This is dependant on the starting predefined values. The current implementation of the process is able to unroll the loop if there was only one pass through it, for instance for the starting values of 12 and 8. Already for two passes the metrics do not drop after an unroll, for instance for 20 and 8, and the result will be the same core code as with the input version.
This is diferent to the assembler programs since the implementation used two IF branches, instead of the IF/ELSE that is inherent to the assembly version. This diference is enough for the metrics to change when the loop is unrolled. An additional MicroJava program with this other type of branching was tested, and it didn’t get fully simplified either. It is arguable which of these is “better” high-level code; the first one is clear that there is no middle option and is explicit about what it does, like a specification should be. The other one is more optimal in execution since it will not do an additional check.
Next is a recursive version, shown in Figure 6, where the values are swapped if needed to ensure a is larger than b. This is the same logic as the recursive assembly program. However, unlike that version, which was transformed into a WHILE loop (Figure 7), here the process resulted in a diferent implementation of the same algorithm, with two recursive calls in which the parameters get subtracted as needed. It was not transformed into a function with a return value, since the process removed the in between stack operations and the result is only once put on the stack and only taken from the stack in the main program.
Other recursive version of the algorithm were also tried. Sadly, they do not get properly transformed to fully high level code. One problem is that the procedure does not get recognised as having two parameters, only one of them is transformed, while the other is still passed through the stack. We believe this is due to the intertwined stack operations that are sometimes prematurely optimised in the process and are then hard to fit into the expected patterns. It is int gcd(int a, int b) int t; { } } void main() { if (a == b)
return a; if (a<b) { t = a; a = b; b = t; } return gcd(a-b,b); print(gcd(8,12),3); somewhat ironic that among these is a MicroJava implementation that is almost the same as the successful transformation shown in Figure 7.
Assembly programs get translated to more than 2 times longer WSL programs; the transformed high-level versions are more than 3 times shorter on average, on these samples. It should also be noted that this is with assembly programs that have the macro definitions and bodies removed. If those were included, that ratio of improvement would be even higher.
MicroJava gets compiled to about 2.5 times more statements, each of which then get translated to around 4 WSL statements. After the transformations the number of statements is mostly in line with the original high-level programs, or in other words it is capable of obtaining the same level of structures.
The length of the process in general rises with the length of the input program, but the
correlation is not a direct one. There are exceptions both ways – some significantly longer
programs can get transformed in the same time, and sometimes short programs will take a long
time to process. Transformations with better end results are often achieved in less time. In
general, if a program is successfully transformed and simplified there are less places to test
future transformations on [
One of the most important tasks in software maintenance is the understanding of the program at hand. This can especially be hard with low-level implementations. In this paper an approach to automated restructuring into a high-level version of the same program is presented. It relies on FermaT transformation system and WSL language, and its support for semantics preserving transformations. Two tools are in charge of translation of the low-level code to WSL, asm2wsl and mjc2wsl. The process is fully automated and is based around a hill climbing algorithm which advances towards the best solution with a fitness function as the measure of quality. All the tools are open source and available under the GNU Public Licence. The presented process consists of several steps and independent tools. It can be applied to a number of diferent maintenance tasks. Since the process is flexible it can be easily adapted or integrated into other processes.
The focus of this paper is a case study of several implementations in two diferent languages of the oldest written algorithm, greatest common divisor. Several versions got automatically transformed into practically the same high-level code. Even though some of these versions used loops and some used recursive procedures, some were regular action systems, and some recursive, and that the programs that translate them have other diferences as well, they all get transformed with the same hill climbing program.
A notable transformation was made, in which one implementation of the algorithm got automatically transformed into another. The starting version was a MicroJava recursive implementation that swaps the values of the parameters when needed. The result was an implementation that has two calls and changes which parameters are passed into them (Figure 7).
On the other hand, some other recursive versions of MicroJava programs were not as much of a success. They do get transformed into a higher level and are easier to understand but there are still some low-level stack operations that remained. A maintainer who is somewhat familiar with the concepts of virtual machines that rely on stacks should be able to fully understand these.
Of course, there is a lot of space for expanding this work. More in-depth studies of diferent algorithms could reveal more about the properties of this process and how it can be improved. For instance more efort could be put into improving the transformations of stack operation to parameters and return values to recognise some of the already optimised versions. The order of the transformations could also be changed to check the possibilities of obtaining better end results.
In general, a big question is how to formulate a fitness function that will be as universal as
possible to define a program as being more understandable. In our experiments, on diferent
inputs, diferent functions would give better results. Since this is an optimisation problem, the
“no free lunch” theorem [
One of the known issues of the hill climbing algorithm is the tendency towards local optimums. This can be somewhat countered with starts from multiple random points and picking the best results from all the runs. Another option that is considered for future processes is to use a diferent searching algorithm.
The authors acknowledge financial support of the Ministry of Education, Science and Technological Development of the Republic of Serbia (Grant No. 451-03-68/2022-14/200125).