1 \documentclass[hyperref={pdfpagelabels=false}]{beamer}
3 %\setbeameroption{show notes}
10 \setbeamercovered{transparent}
11 %\setbeamertemplate{footline}[frame number]
14 \usepackage[english]{babel}
15 \usepackage[latin1]{inputenc}
17 \usepackage[T1]{fontenc}
20 \usepackage{multimedia}
21 \usepackage{subfigure}
23 % Can use a tiny fontsize
26 %\usepackage{pgfpages}
27 %\pgfpagesuselayout{4 on 1}[a4paper,border shrink=5mm]
29 %For handouts, use the following two lines:
30 %\usepackage{pgfpages}
31 %\pgfpagesuselayout{2 on 1}[a4paper,border shrink=5mm]
35 {MontiumC Transforming}
37 \author {Matthijs Kooijman}
39 \institute[Recore Systems and University of Twente]
45 Faculty of Electrical Engineering, Mathematics and Computer Science\\
55 \begin{frame}{Contents}
59 \section{Introduction}
60 \begin{frame}{Low Level Virtual Machine (LLVM)}
62 \item Compiler framework.
65 \alert<2>{\item C Frontend}
66 \alert<2>{\item Intermediate representation (LLVM IR)}
67 \alert<2>{\item Transformation passes}
68 \item Native codegenerators
75 \begin{frame}{Montium Workflow}
76 \pgfdeclareimage[width=\textwidth]{Workflow}{images/Workflow}
77 \pgfuseimage{Workflow}
81 \begin{frame}{What is MontiumC?}
82 \note{Two angles: What do we want, and what do we support.}
84 \item Status: Specification is ongoing
87 \item Clang is nontransparent
88 \note[item]{Clang --- A lot of special cases. Clang goal: Produce
89 valid LLVM IR, which can change unexpectedly}
91 \note[item]{Complex C --- A lot of corner cases}
93 \note[item]{Limited C --- Need to use annotations, limited amount of types}
94 \item Assembly vs. High level
95 \note[item]{Tradeoffs -- Code size vs compiler complexity, clarity
96 vs control, clarity vs determinism}
101 \begin{frame}[containsverbatim]
103 \begin{column}{0.5\textwidth}
105 \begin{Verbatim}[fontsize=\tiny]
111 factor = from_int(2);
112 input = alloc_mem(P0M0);
113 output = alloc_mem(P0M1);
115 set_offset(input, 0);
116 set_base(output, -1);
117 set_offset(output, -1);
120 word in = read_mem(input);
121 word out = p0o0(imul(ra1(in), rc1(factor)))
122 add_offset(input, 1);
123 add_offset(output, 1);
126 write_mem(output, out);
127 in = read_mem(input);
128 out = p0m0(imul(ra1(in), rc1(factor)))
129 add_offset(input, 1);
130 add_offset(output, 1);
131 } while(loop_next(LC1));
133 write_mem(output, out);
136 \begin{column}{0.5\textwidth}
138 \begin{Verbatim}[fontsize=\tiny]
143 for (int i=0; i<10; ++i)
144 output[i] = mul(input[i], 2);
150 \note{} % Empty filler note page
152 \begin{frame}{Using LLVM transformations}
156 \item LLVM Passes assume a lot
157 \note[item]{Assumptions --- Immediates are free, reordering of
158 instructions is possible, shifts are cheaper than mults}
159 \item Montium has specific constraints
160 \note[item]{Constraint --- Implicit cycle boundaries and ordering}
161 \item Montium needs different policies
162 \note[item]{Policies --- Montium has different optimality criteria (or
163 sometimes feasibility criteria) than regular hardware.}
168 \begin{frame}{Using LLVM transformations}
172 \item Allow nested functions
176 \item Allow local variables
178 \item Stack slots turned into (virtual) registers.
180 \item Allow use of structs
182 \item Promotion to multiple scalar values
184 \item Allow more different loops
186 \item Canonicalization of loops
187 \item Still requires backend support
189 \item Allow constant function parameters
191 \item Constant propagation
195 \note[item]{Without transformations, MontiumC hardly exists.
196 Transformations have the goal of making MontiumC bigger.}
199 \begin{frame}{Creating new transformations}
201 \item Existing LLVM transformations are not sufficient for our demands
204 \item Staying generic
205 \note[item]{Generic --- LLVM maintained passes are a lot less work on
206 the long term, but require more initial effort}
207 \item New LLVM features needed
208 \note[item]{Features --- Multiple return values, inlining and
209 annotation attributes}
214 \begin{frame}{Creating new transformations}
218 \item Allow global variables
220 \item Turned into local variables
222 \item Simpler backend
224 \item Perform canonicalizations
225 \note[item]{Canonical --- Maximal SSA form, removal of global variables}
227 \item Reconfigurability
229 \item Preserving reconfigurable variables
230 \item Mainly needs backend support
232 \item Allow different constant function parameters
234 \item Function duplication
236 \note[item]{Function duplication challenge --- When to duplicate?}
242 \begin{frame}[containsverbatim]{Constant propagation}
244 \begin{column}{0.5\textwidth}
246 \begin{Verbatim}[fontsize=\tiny]
248 int mul(int a, int b) {
261 \begin{column}{0.5\textwidth}
263 \begin{Verbatim}[fontsize=\tiny]
279 \note{Mainly useful when using library code}
282 \begin{frame}[containsverbatim]{Function duplication}
284 \begin{column}{0.5\textwidth}
286 \begin{Verbatim}[fontsize=\tiny]
288 int mul(int a, int b) {
305 \begin{column}{0.5\textwidth}
307 \begin{Verbatim}[fontsize=\tiny]
331 \note{Mainly useful when values must really be constant (masks, loop
335 \section{Future work}
336 \begin{frame}{Open issues}
338 \item Debug information
340 \item Only time for initial work
342 \item Reconfigurability
344 \item Needs backend support
346 \item Proper inlining
349 \item Needs backend support
351 \item Remove next\_cycle
358 \section{Conclusions}
359 \begin{frame}{Conclusions}
361 \item LLVM is very suitable
362 \item Defining the problem is harder than solving it
363 \item Three months is short, visible progress is slow