Translation and Transformation of Low Level Programs

Abstract

This thesis presents an approach for working with low level source code that enables automatic restructuring and raising the abstraction level of the programs. This makes it easier to understand the logic of the program, which in turn reduces the development time.The process in this thesis was designed to be flexible and consists of several independent tools. This makes the process easy to adapt as needed, while at the same time the developed tools can be used for other processes. There are usually two basic steps. First is the translation to WSL language, which has a great number of semantic preserving program transformations. The second step are the transformations of the translated WSL. Two tools were developed for translation: one that works with a subset of x86 assembly, and another that works with MicroJava bytecode. The result of the translation is a low level program in WSL.The primary goal of this thesis was to fully automate the selection of the transformations. This enables users with no domain knowledge to efficiently use this process as needed. At the same time, the flexibility of the process enables experienced users to adapt it as needed or integrate it into other processes. The automation was achieved with a hill climbing algorithm.Experiments that were run on several types of input programs showed that the results can be excellent. The fitness function used was a built-in metric that gives the “weight” of structures in a program. On input samples that had original high level source codes, the end result metrics of the translated and transformed programs were comparable. On some samples the result was even better than the originals, on some others they were somewhat more complex. When comparing with low level original source code, the end results was always significantly improved.

U okviru ove teze se predstavlja pristup radu sa programima niskog nivoa koji omogućava automatsko restrukturiranje i podizanje na više nivoe. Samim tim postaje mnogo lakše razumeti logiku programa što smanjuje vreme razvoja.Proces je dizajniran tako da bude fleksibilan i sastoji se od više nezavisnih alata. Samim tim je lako menjati proces po potrebi, ali i upotrebiti razvijene alate u drugim procesima. Tipično se mogu razlikovati dva glavna koraka. Prvi je prevođenje u jezik WSL,za koji postoji veliki broj transformacija programa koje očuvavaju semantiku. Drugi su transformacije u samom WSL-u. Za potrebe prevođenja su razvijena dva alata, jedan koji radi sa podskupom x86 asemblera i drugi koji radi sa MikroJava bajtkôdom. Rezultat prevođenja je program niskog nivoa u WSL jeziku.Primarni cilj ovog istraživanja je bila potpuna automatizacija odabira transformacija, tako da i korisnici bez iskustva u radu sa sistemom mogu efikasno da primene ovaj proces za svoje potrebe. Sa druge strane zbog fleksibilnosti procesa, iskusni korisnici mogu lakoda ga prošire ili da ga integrišu u neki drugi već postojeći proces.Automatizacija je postignuta pretraživanjem usponom (eng. hill climbing).Eksperimenti vršeni na nekoliko tipova ulaznih programa niskog nivoa su pokazali da rezultati mogu biti izuzetni. Za funkciju pogodnosti je korišćena ugrađena metrika koja daje “težinu” struktura u programu. Kod ulaza za koje je originalni izvorni kôd bio dostupan, krajnje metrike najboljih varijanti prevedenih i transformisanih programa su bile na sličnom nivou. Neki primeri su bolji od originala, dok su drugi bili nešto kompleksniji. Rezultati su uvek pokazivali značajna unapređenja u odnosu na originalni kôd niskog nivoa.