Program feature impact on the treewidth of the RVSDG IR

Abstract

I denne oppgaven undersøker vi effekten av programtrekk på trebredden (treewidth) til den Regionaliserte Verdi-Tilstands Avhengighetsgrafens (RVSDG) mellomrepresentasjon (Intermediate Representation). Vi ser på hvordan programmenes egenskaper resulterer i endringer i trebredden til deres tilsvarende RVSDGer. Dette inkluderer målinger av hvordan forskjellige optimeringer påvirker programstrukturen, slik som løkkespalting (loop unrolling) og funksjonsinnfylling (function inlining). Vi presenterer også spesifikke programmer for å indusere gitte trekk som endrer trebredden, som forskjellige måter å tilordne argumenter til funksjoner på og variablers livstid (liveness). Når vi kan endre programstrukturen uten å endre semantikken, vil vi også se på kjøretiden til programmet med forskjellige trebredder for å undersøke om en sammenheng mellom trebredden og programkjøretiden eksisterer.

In this thesis we investigate program feature impact on the treewidth of the Regionalized Value State Dependency Graph (RVSDG) intermediate representation. We look at how properties of programs translate to changes in the treewidth of their corresponding RVSDGs. This includes measurements of how different optimizations affect the structure of the programs, including optimizations such as loop unrolling and function inlining. We also create programs to induce features that change the treewidth, including different ways of passing arguments to functions and liveness range of variables. Where we are able to change the structure of a program without changing its semantics, we also look at the runtime of the program with different treewidths to try to determine if any relationship between the treewidth and the runtime of the program exists.