Implementing RVSDG as a dialect of MLIR

Abstract

Slutten på Dennard-skaleringen og det påfølgende skiftet til flerkjernede og heterogene prosessorarkitekturer har flyttet ansvaret for å øke ytelsen til programvare over på programmerere og verktøyene deres. Et behov for kompilatorer som automatisk kan utnytte den iboende parallelliteten i programmer og den spesialiserte maskinvaren som man finner i moderne prosessorer har derfor blitt mye viktigere. For å kunne gjennomføre slike optimaliseringer, er det viktig at kompilatoren bruker en mellomrepresentasjon (IR) som gjør det mulig å finne ut hvilken kode som kan parallelliseres.

Den regionaliserte verdi-/tilstands-avhengighetsgrafen (RVSDG) er en dataflytbasert IR. Den representerer beregninger som noder og verdi- og tilstands-avhengigheter som kanter mellom nodene. Enkelte kontrollflytstrukturer er eksplisitt representert ved hjelp av noder med regioner, som igjen inneholder subgrafer. Denne programrepresentasjonen eksponerer parallelliteten til programmer og forenkler dataflytbaserte optimaliseringer. MLIR er et rammeverk for å implementere domenespesifikke IR-er. Det inneholder standard infrastruktur og er grunnlaget for et økosystem med IR-dialekter som modellerer forskjellige domener på forskjellige abstraksjonsnivåer. Disse dialektene kan sameksistere i en gitt IR, noe som gjør det mulig å representere tradisjonell kode og akseleratorspesifikk kode i samme datastruktur.

Denne oppgaven viser at RVSDG kan representeres som en dialekt av MLIR. Dette gjøres både ved å presentere en teoretisk representasjon av RVSDG i MLIR, og ved å implementere en RVSDG-dialekt i MLIR. Denne dialekten vil gjøre RVSDG mer tilgjengelig for eksterne kompilatorprosjekter og vil samtidig gi fremtidig forskning på RVSDG tilgang til infrastrukturen og økosystemet tilbudt av MLIR.

The end of Dennard scaling and subsequent rise of multicore and heterogeneous architectures has shifted the burden of improving program performance over to programmers and their tools. In particular, creating compilers which can exploit the latent parallelism of programs has become far more important. For such optimizations to be possible, the compiler needs an intermediate representation (IR) that makes it possible to detect code that is eligible for parallelization. The Regionalized Value State Dependence Graph (RVSDG) is a data-flow centric IR that encodes a program as a graph of nodes, representing computations, connected by edges, representing data or state dependencies. Control flow constructs are represented as nodes containing regions that hold IR subgraphs. Representing a program in this manner exposes the inherent parallelism of the program and simplifies data-flow based compiler optimizations.

MLIR is a framework for creating domain specific IRs. It provides common infras- tructure as well as an ecosystem of IR dialects that each model their own domain and/or level of abstraction. These dialects are allowed to coexist in the IR, enabling progressive lowering of code and the unified representation of traditional code and accelerator-specific code.

This thesis shows empirically that RVSDG can be implemented as a dialect of MLIR, and presents both the conceptual mapping from RVSDG to MLIR and the implementation of the RVSDG dialect. Having this dialect available makes RVSDG more accessible to other compiler developers, and also gives future research into RVSDG access to the infrastructure of MLIR.