Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Random Testing of Code Generation in Compilers
KTH, School of Information and Communication Technology (ICT).
2015 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

Compilers are a necessary tool for all software development. As modern compilers are large and complex systems, ensuring that the code they produce is accurate and correct is a vital but arduous task. Correctness of the code generation stage is important. Maintaining full coverage of test cases in a compiler is virtually impossible due to the large input and output domains. We propose that random testing is a highly viable method for testing a compiler. A method is presented to randomly generate a lower level code representation and use it to test the code generation stage of a compiler. This enables targeted testing of some of the most complex components of a modern compiler (register allocation, instruction scheduling) for the first time. The design is implemented in a state-of-the-art optimizing compiler, LLVM, to determine the effectiveness and viability of the method. Three distinct failures are observed during the evaluation phase. We analyze the causes behind these failures and conclude that the methods described in this work have the potential to uncover compiler defects which are not observable with other testing approaches.

Abstract [sv]

Kompilatorer är nödvändiga för all mjukvaruutveckling. Det ärsvårt att säkerställa att koden som produceras är korrekt, eftersomkompilatorer är mycket stora och komplexa system. Kodriktigheteninom kodgenereringsstadiet (registerallokering och instruktionsschemaläggning) är särskilt viktig. Att uppnå full täckningav testfall i en kompilator är praktiskt taget omöjligt på grund avde stora domänerna för in- och utdata.Vi föreslår att slumpmässig testning är en mycket användbarmetod för att testa en kompilator. En metod presenteras för attgenerera slumpmässig kod på en lägre representationsnivå och testakodgenereringsstadiet i en kompilator. Detta möjliggör riktadtestning av några av de mest komplexa delarna i en modern kompilator(registerallokering, instruktionsschemaläggning) för förstagången.Designen implementeras i en toppmodern optimerande kompilator,LLVM, för att avgöra metodens effektivitet. Tre olika misslyckandenobserveras under utvärderingsfasen. Vi analyserar orsakernabakom dessa misslyckanden och drar slutsatsen att demetoder som beskrivs har potential att finna kompilatordefektersom inte kan observeras med andra testmetoder.

Kompilatorer är nödvändiga för all mjukvaruutveckling. Det är

svårt att säkerställa att koden som produceras är korrekt, eftersom

kompilatorer är mycket stora och komplexa system. Kodriktigheten

inom kodgenereringsstadiet (registerallokering och instruktionsschemal

äggning) är särskilt viktig. Att uppnå full täckning

av testfall i en kompilator är praktiskt taget omöjligt på grund av

de stora domänerna för in- och utdata.

Vi föreslår att slumpmässig testning är en mycket användbar

metod för att testa en kompilator. En metod presenteras för att

generera slumpmässig kod på en lägre representationsnivå och testa

kodgenereringsstadiet i en kompilator. Detta möjliggör riktad

testning av några av de mest komplexa delarna i en modern kompilator

(registerallokering, instruktionsschemaläggning) för första

gången.

Designen implementeras i en toppmodern optimerande kompilator,

LLVM, för att avgöra metodens effektivitet. Tre olika misslyckanden

observeras under utvärderingsfasen. Vi analyserar orsakerna

bakom dessa misslyckanden och drar slutsatsen att de

metoder som beskrivs har potential att finna kompilatordefekter

som inte kan observeras med andra testmetoder.

Place, publisher, year, edition, pages
2015. , 58 p.
Series
TRITA-ICT-EX, 2015:76
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:kth:diva-175852OAI: oai:DiVA.org:kth-175852DiVA: diva2:862706
Educational program
Master of Science - Embedded Systems
Examiners
Available from: 2015-10-23 Created: 2015-10-23 Last updated: 2016-05-11Bibliographically approved

Open Access in DiVA

fulltext(628 kB)31 downloads
File information
File name FULLTEXT01.pdfFile size 628 kBChecksum SHA-512
116bd9266d7a17f5626f8a35734ccb0c289fd27043ef65fb5c34ec53a8383ac859d5534049d4cbc4f4dbeef7f4805e18a9dab91b3ba1b96029ab535b51ea83be
Type fulltextMimetype application/pdf

By organisation
School of Information and Communication Technology (ICT)
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 31 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

urn-nbn

Altmetric score

urn-nbn
Total: 881 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf