Licentiatavhandling Linköping : Linköpings universitet, 2009.

No description available.

No description available.

Error messages in compilers is a topic that is often overlooked. The quality of the messages can have a big impact on development time and ease oflearning. Another method used to speed up development is to build a domainspecific language (DSL). This thesis migrates an existing framework to use TypeScript in order to speed up development time with compile-time error handling. Alternative methods for implementing a DSL are evaluated based onhow they affect the ability to generate good error messages. This is done usinga proposed list of six usability heuristics for error messages. They are also usedto perform heuristic evaluation on the error messages in the TypeScript compiler. This showed that it struggled with syntax errors but had semantic errormessages with low amount of usability problems. Finally, a method for implementing a DSL and presenting its error messages is suggested. The evaluationof said method showed promise despite the existence of usability problems. / Felmeddelanden i kompilatorer är ett ämne som ofta förbises. Kvaliténpå felmeddelanden kan ha stor påverkan på utvecklingstid och lätthetatt lära. En annan metod för att sänka utvecklingstid är att bygga ettdomänspecifikt programmeringspråk. Detta examensarbete migrerar ettexisterande ramverk till TypeScript för att snabba på utvecklingstidmed felhantering i kompileringsstadiet. Alternativa metoder för attimplementera ett DSL evalueras baserat på hur de påverkar möjlighetenatt generera bra felmeddelanden. Detta görs med en föreslagen lista avsex heuristiker för felmeddelanden. De används också för att utföra enheuristik utvärdering på felmeddelandena i TypeScriptkompilatorn. Detta visade att den har svårt för syntaxfel men hademeddelanden för semantiska fel med låg mängdanvändbarhetsproblem. Till sist föreslås en metod för att implementeraett DSL och presentera dess felmeddelanden. Evalueringen av den nämndametoden visade lovande resultat trots förekomsten av användbarhetsproblem.

The Regular Expression (RegEx) is one of the most important computer science technologies used for searching through text. Used commonly in almost every corner of computer science that is dependent on searching, it is imperative that they are made to be efficient. Usually, RegEx are implemented through the use of a process called interpretation. This thesis explores the possibility and execution time benefits of compiling the RegEx as part of the program instead of interpreting it. For this purpose, a prototype implementation was developed in the Rust programming language. Using this prototype, execution time benchmarks were performed that compare the optimised, and commonly used, interpreted variant against the thesis’ unoptimised compiled version. While the results did not determine a clear preferred method in terms of execution time, they did highlight the potential that exists in compiling RegEx. With some of the tests showing faster execution times in the prototype, there are strong arguments for future research into this field, where the compilation of RegEx can come to benefit from the optimisations present in the interpreted norm. / Regulära uttryck (EN: Regular Expression; RegEx) är en av de mest använda datalogiteknikerna för att söka igenom text. Eftersom det är använt inom många delar av datalogi så är teknikens effektivitet viktig. I norm är RegEx genomförda med en process kallad tolkning. Denna uppsats utforskar möjligheten och tidsförmåner att kompilera dessa RegEx som en del av det utomliggande programmet istället för att tolka det. För det syftet skapades en prototyp i programmeringsspråket Rust. Denna prototyp användes då för att utföra tidstest där den optimerade tolkade normen jämnfördes med avhandlingens kompilerade icke optimerade variant. De producerade resultaten visade ingen föredragen metod men betonade möjligheterna med att kompilera RegEx. Eftersom vissa av testerna visade snabbare utförande med prototypen finns det starka argument för ytterligare forskning inom detta område. På så sätt kan den kompilerade formen ta del av den utveckling som den tolkade normen redan har.

This thesis presents the design and implementation of an extension of the self-hosted Miking compiler to enable the generation of JavaScript code for different runtime environments and web browsers. Miking is a framework for developing domain-specific and general-purpose programming languages through sound language fragment composition, among other things, to create efficient compilers. Miking Core encapsulates a meta-language called Miking Lang and a fundamental functional Miking Expression language which Miking Lang itself is also lowered to. The presented backend translates Miking expressions into semantically equivalent effective, readable, sound, and correct JavaScript programs. In this report, development challenges, implementation methods, and techniques are also discussed and evaluated along with a review of the final compiler backend. Likewise, details on JavaScript-specific optimizations and pattern-matching compilation are presented, including how tail recursion is handled to enable complex Miking programs to be compiled into flexible and efficient JavaScript. / Detta examensarbete presenterar design och implementation för utveckling av Miking-kompilatorn, med syfte att möjliggöra generering av JavaScript-kod för olika exekveringsmiljöer och webbläsare. Miking är ett ramverk för att utveckla domänspecifika och generella programmeringsspråk genom sund komposition av språksfragment som kan används för att skapa effektiva kompilatorer. Miking Core ramverket innehåller ett metaspråk kallat Miking Lang, vilket ”sänks” till det mer grundläggande funktionella Miking Expression-språket. ”Sänkning” betyder i huvudsak att skriva om mer komplexa semantiska konstruktioner i form av enklare. Den backend som presenteras översätter Miking-uttryck till semantiskt ekvivalenta JavaScript program som också är effektiva, läsbara, sunda och korrekta. I denna rapport diskuteras och utvärderas även utvecklingsutmaningar, implementeringsmetod och andra tekniker som har använts under arbetet. På samma sätt presenteras detaljer om JavaScript-specifika optimeringar och mönstermatchningskompilering, inklusive hur svansrekursion hanteras för att möjliggöra kompilering av komplexa Miking-program till flexibel och effektiv JavaScript med hjälp av ”trampoline” teknik.

Instruction Scheduling is a back-end compiler optimisation technique that can provide significant performance gains. It refers to ordering instructions in a particular order to reduce latency for processors with instruction-level parallelism. At the present typical compilers use heuristics to perform instruction scheduling and solve other related non-polynomial complete problems. This thesis aims to present a machine learning-based approach to challenge heuristic methods concerning performance. In this thesis, a novel reinforcement learning (RL) based model for the instruction scheduling problem is developed including modelling features of processors such as forwarding, resource utilisation and treatment of the action space. An efficient optimal scheduler is presented to be used for an optimal schedule length based reward function, however, this is not used in the final results as a heuristic based reward function was deemed to be sufficient and faster to compute. Furthermore, an RL agent that interacts with the model of the problem is presented using three different types of graph neural networks for the state processing: graph conventional networks, graph attention networks, and graph attention based on the work of Lee et al. A simple two-layer neural network is also used for generating embeddings for the resource utilisation stages. The proposed solution is validated against the modelled environment and favourable but not significant improvements were found compared to the most common heuristic method. Furthermore, it was found that having embeddings relating to resource utilisation was very important for the explained variance of the RL models. Additionally, a trained model was tested in an actual compiler, however, no informative results were found likely due to register allocation or other compiler stages that occur after instruction scheduling. Future work should include improving the scalability of the proposed solution. / Instruktionsschemaläggning är en optimeringsteknik för kompilatorer som kan ge betydande prestandavinster. Det handlar om att ordna instruktioner i en viss ordning för att minska latenstiden för processorer med parallellitet på instruktionsnivå. För närvarande använder vanliga kompilatorer heuristiker för att utföra schemaläggning av instruktioner och lösa andra relaterade ickepolynomiala kompletta problem. Denna avhandling syftar till att presentera en maskininlärningsbaserad metod för att utmana heuristiska metoder när det gäller prestanda. I denna avhandling utvecklas en ny förstärkningsinlärningsbaserad (RL) modell för schemaläggning av instruktioner, inklusive modellering av processorns egenskaper såsom vidarebefordran, resursutnyttjande och behandling av handlingsutrymmet. En effektiv optimal schemaläggare presenteras för att eventuellt användas för belöningsfunktionen, men denna används inte i de slutliga resultaten. Dessutom presenteras en RL-agent som interagerar med problemmodellen och använder tre olika typer av grafneurala nätverk för tillståndsprocessering: grafkonventionella nätverk, grafuppmärksamhetsnätverk och grafuppmärksamhet baserat på arbetet av Lee et al. Ett enkelt neuralt nätverk med två lager används också för att generera inbäddningar för resursanvändningsstegen. Den föreslagna lösningen valideras mot den modellerade miljön och gynnsamma men inte signifikanta förbättringar hittades jämfört med den vanligaste heuristiska metoden. Dessutom visade det sig att det var mycket viktigt för den förklarade variansen i RL-modellerna att ha inbäddningar relaterade till resursutnyttjande. Dessutom testades en tränad modell i en verklig kompilator, men inga informativa resultat hittades, sannolikt på grund av registerallokering eller andra kompilatorsteg som inträffar efter schemaläggning av instruktioner. Framtida arbete bör inkludera att förbättra skalbarheten hos den föreslagna lösningen.

Query systems were recently introduced as an architecture for constructing compilers, and have shown to enable fast and efficient incremental compilation, where results from previous builds is reused to accelerate future builds. With this architecture, a compiler is composed of several queries, each of which extracts a small piece of information about the source program. For example, one query might determine the type of a variable, and another the list of functions defined in some file. The dependencies of a query, which includes other queries or files on disk, are automatically recorded at runtime. With these dependencies, query systems can detect changes in their inputs and incorporate them into the final output, while reusing old results from queries which have not changed. This reduces the amount of work needed to recompile code, which saves both time and energy. We present a new parallel execution model for query systems using work-stealing, which dynamically balances the workload across multiple threads. This is facilitated by various augmentations to existing algorithms to allow concurrent operations. Furthermore, we introduce a novel data structure that accelerates incremental compilation for common use cases. We evaluated the impact of these augmentations by implementing a compiler frontend capable of parsing and type-checking the Go programming language. We demonstrate a 10x reduction in compile times using the parallel execution mode. Finally, under certain common conditions, we show a 5x reduction in incremental compile times compared to the state-of-the-art. / Query-system är en ny arkitektur som har använts för att implementera kompilatorer för programspråk och har ett fokus på att möjliggöra snabb och effektiv inkrementell kompilering. Med denna arkitektur består en kompilator flera olika mindre funktioner, som var och en svarar på en liten fråga om källprogrammet, såsom typen av en variabel eller listan över funktioner i en fil. Genom att spåra hur dessa funktioner anropar varandra, och den data de läser, kan kompilatorer upptäcka förändringar i sina indata och utföra den minimala mängd arbete som krävs för att sammanställa dessa förändringar i utdata. Detta minskar mängden arbete som behövs för att kompilera om kod, vilket sparar både tid och energi. I denna rapport presenterar vi en ny exekveringsmodell för Query-system som möjliggör parallellism med hjälp av work-stealing. Detta underlättas av flera tillägg till befintliga algoritmer som gör det möjligt att utföra alla operationer parallellt. Utöver detta introducerar vi även en ny datastruktur som gör inkrementell kompilering snabbare för många vanliga användningsområden. Vi utvärderade effekten av dessa förändringar genom att implementera ett kompilatorgränssnitt som kan analysera och verifiera korrekthet av typer Go-programmeringsspråket. Resultaten visar en 10x reduktion i kompileringstider med hjälp av parallellkörningsläget. Vi demonstrerar även 5 gånger lägre kompileringstider vid inkrementella ändringar än vad som tidigare varit möjligt.