liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
Integrated Code Generation
Linköping University, Department of Computer and Information Science. Linköping University, The Institute of Technology. (Pelab)
2011 (English)Doctoral thesis, monograph (Other academic)
Abstract [en]

Code generation in a compiler is commonly divided into several phases: instruction selection, scheduling, register allocation, spill code generation, and, in the case of clustered architectures, cluster assignment. These phases are interdependent; for instance, a decision in the instruction selection phase affects how an operation can be scheduled. We examine the effect of this separation of phases on the quality of the generated code. To study this we have formulated optimal methods for code generation with integer linear programming; first for acyclic code and then we extend this method to modulo scheduling of loops. In our experiments we compare optimal modulo scheduling, where all phases are integrated, to modulo scheduling where instruction selection and cluster assignment are done in a separate phase. The results show that, for an architecture with two clusters, the integrated method finds a better solution than the non-integrated method for 39% of the instances.

Our algorithm for modulo scheduling iteratively considers schedules with increasing number of schedule slots. A problem with such an iterative method is that if the initiation interval is not equal to the lower bound there is no way to determine whether the found solution is optimal or not. We have proven that for a class of architectures that we call transfer free, we can set an upper bound on the schedule length. I.e., we can prove when a found modulo schedule with initiation interval larger than the lower bound is optimal.

Another code generation problem that we study is how to optimize the usage of the address generation unit in simple processors that have very limited addressing modes. In this problem the subtasks are: scheduling, address register assignment and stack layout. Also for this problem we compare the results of integrated methods to the results of non-integrated methods, and we find that integration is beneficial when there are only a few (1 or 2) address registers available.

Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press , 2011. , 169 p.
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1375
National Category
Computer Science
URN: urn:nbn:se:liu:diva-67471ISBN: 978-91-7393-147-2OAI: diva2:416671
Public defence
2011-06-07, Visionen, Hus B, Campus Valla, Linköpings universitet, Linköping, 13:15 (English)
Available from: 2011-05-12 Created: 2011-04-13 Last updated: 2014-10-08Bibliographically approved

Open Access in DiVA

Integrated Code Generation(875 kB)961 downloads
File information
File name FULLTEXT01.pdfFile size 875 kBChecksum SHA-512
Type fulltextMimetype application/pdf
cover(189 kB)22 downloads
File information
File name COVER01.pdfFile size 189 kBChecksum SHA-512
Type coverMimetype application/pdf

Search in DiVA

By author/editor
Eriksson, Mattias
By organisation
Department of Computer and Information ScienceThe Institute of Technology
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 961 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 1016 hits
ReferencesLink to record
Permanent link

Direct link