\documentclass[hyperref={pdfpagelabels=false}]{beamer}

%\setbeameroption{show notes}

\mode<presentation>
{
  %\useinnertheme{echt}
  %\useinnertheme{proef}
  \usetheme{recore}
  \setbeamercovered{transparent}
%\setbeamertemplate{footline}[frame number]
}

\usepackage[english]{babel}
\usepackage[latin1]{inputenc}
\usepackage{times}
\usepackage[T1]{fontenc}
\usepackage{acronym}
\usepackage{tikz}
\usepackage{multimedia}
\usepackage{subfigure}
\usepackage{booktabs}
% Can use a tiny fontsize
\usepackage{fancyvrb}

%\usepackage{pgfpages}
%\pgfpagesuselayout{4 on 1}[a4paper,border shrink=5mm]

%For handouts, use the following two lines:
%\usepackage{pgfpages}
%\pgfpagesuselayout{2 on 1}[a4paper,border shrink=5mm]


\title
{MontiumC Transforming}

\author {Matthijs Kooijman}

\institute[Recore Systems and University of Twente]
{
  \inst{}%
  Recore Systems
  \and
  \inst{}%
  Faculty of Electrical Engineering, Mathematics and Computer Science\\
  University of Twente
  }
  
\begin{document}

\begin{frame}
	\titlepage
\end{frame}

\begin{frame}{Contents}
  \tableofcontents
\end{frame}

\section{Introduction}
  \begin{frame}{Low Level Virtual Machine (LLVM)}
    \begin{itemize}
      \item Compiler framework.
      \item Provides:
      \begin{itemize}
        \alert<2>{\item C Frontend}
        \alert<2>{\item Intermediate representation (LLVM IR)}
        \alert<2>{\item Transformation passes}
        \item Native codegenerators
        \item JIT compilation
      \end{itemize}
      \item Very modular
    \end{itemize}
  \end{frame}

  \begin{frame}{Montium Workflow}
    \pgfdeclareimage[width=\textwidth]{Workflow}{images/Workflow}
    \pgfuseimage{Workflow}
  \end{frame}

\section{Past work}
    \begin{frame}{What is MontiumC?}
      \note{Two angles: What do we want, and what do we support.}
      \begin{itemize}
      \item Status: Specification is ongoing
      \item Challenges:
        \begin{itemize}
          \item Clang is nontransparent
          \note[item]{Clang --- A lot of special cases. Clang goal: Produce
          valid LLVM IR, which can change unexpectedly}
          \item C is complex
          \note[item]{Complex C --- A lot of corner cases}
          \item C is limited
          \note[item]{Limited C --- Need to use annotations, limited amount of types}
          \item Assembly vs. High level
          \note[item]{Tradeoffs -- Code size vs compiler complexity, clarity
          vs control, clarity vs determinism}
        \end{itemize}
      \end{itemize}
    \end{frame}

    \begin{frame}[containsverbatim]
      \begin{columns}
        \begin{column}{0.5\textwidth}
          Low level
          \begin{Verbatim}[fontsize=\tiny]
mem input;
mem output;
word factor;

void run(void) {
  factor = from_int(2);
  input  = alloc_mem(P0M0);
  output = alloc_mem(P0M1);
  set_base(input, 0);
  set_offset(input, 0);
  set_base(output, -1);
  set_offset(output, -1);

  next_cycle();
  word in = read_mem(input);
  word out = p0o0(imul(ra1(in), rc1(factor)))
  add_offset(input, 1);
  add_offset(output, 1);
  init_loop(LC1, 8);
  do {
    write_mem(output, out);
    in = read_mem(input);
    out = p0m0(imul(ra1(in), rc1(factor)))
    add_offset(input, 1);
    add_offset(output, 1);
  } while(loop_next(LC1));

  write_mem(output, out);
\end{Verbatim}
        \end{column}
        \begin{column}{0.5\textwidth}
          High level
          \begin{Verbatim}[fontsize=\tiny]
P0M0 int input[10];
P0M1 int output[10];

void run(void) {
  for (int i=0; i<10; ++i)
    output[i] = mul(input[i], 2);
}
          \end{Verbatim}
        \end{column}
      \end{columns}
    \end{frame}
    \note{} % Empty filler note page

    \begin{frame}{Using LLVM transformations}
      \begin{itemize}
        \item Challenges:
        \begin{itemize}
          \item LLVM Passes assume a lot
          \note[item]{Assumptions --- Immediates are free, reordering of
          instructions is possible, shifts are cheaper than mults}
          \item Montium has specific constraints
          \note[item]{Constraint --- Implicit cycle boundaries and ordering}
          \item Montium needs different policies
          \note[item]{Policies --- Montium has different optimality criteria (or
          sometimes feasibility criteria) than regular hardware.}
        \end{itemize}
      \end{itemize}
    \end{frame}

    \begin{frame}{Using LLVM transformations}
      \begin{itemize}
        \item Achievements:
        \begin{itemize}
          \item Allow nested functions
          \begin{itemize}
            \item Inlining
          \end{itemize}
          \item Allow local variables
          \begin{itemize}
            \item Stack slots turned into (virtual) registers.
          \end{itemize}
          \item Allow use of structs
          \begin{itemize}
            \item Promotion to multiple scalar values
          \end{itemize}
          \item Allow more different loops
          \begin{itemize}
            \item Canonicalization of loops
            \item Still requires backend support
          \end{itemize}
          \item Allow constant function parameters
          \begin{itemize}
            \item Constant propagation
          \end{itemize}
        \end{itemize}
      \end{itemize}
      \note[item]{Without transformations, MontiumC hardly exists.
      Transformations have the goal of making MontiumC bigger.}
    \end{frame}

    \begin{frame}{Creating new transformations}
      \begin{itemize}
        \item Existing LLVM transformations are not sufficient for our demands
        \item Challenges:
        \begin{itemize}
          \item Staying generic
          \note[item]{Generic --- LLVM maintained passes are a lot less work on
          the long term, but require more initial effort}
          \item New LLVM features needed
          \note[item]{Features --- Multiple return values, inlining and
          annotation attributes}
        \end{itemize}
      \end{itemize}
    \end{frame}

    \begin{frame}{Creating new transformations}
      \begin{itemize}
        \item Achievements:
        \begin{itemize}
          \item Allow global variables
          \begin{itemize}
            \item Turned into local variables
          \end{itemize}
          \item Simpler backend
          \begin{itemize}
            \item Perform canonicalizations
            \note[item]{Canonical --- Maximal SSA form, removal of global variables}
          \end{itemize}
          \item Reconfigurability
          \begin{itemize}
            \item Preserving reconfigurable variables
            \item Mainly needs backend support
          \end{itemize}
          \item Allow different constant function parameters
          \begin{itemize}
            \item Function duplication
            \item Not in use yet
            \note[item]{Function duplication challenge --- When to duplicate?}
          \end{itemize}
        \end{itemize}
      \end{itemize}
    \end{frame}

    \begin{frame}[containsverbatim]{Constant propagation}
      \begin{columns}
        \begin{column}{0.5\textwidth}
          Before
          \begin{Verbatim}[fontsize=\tiny]

int mul(int a, int b) {
  return a * b;
}

void run(void) {
  ...
  mul(x, 2);
  ...
  mul(y, 2);
  ...
}
          \end{Verbatim}
        \end{column}
        \begin{column}{0.5\textwidth}
          After
          \begin{Verbatim}[fontsize=\tiny]

int mul(int a) {
  return a * 2;
}

void run(void) {
  ...
  mul(x);
  ...
  mul(y);
  ...
}
          \end{Verbatim}
        \end{column}
      \end{columns}
      \note{Mainly useful when using library code}
    \end{frame}

    \begin{frame}[containsverbatim]{Function duplication}
      \begin{columns}
        \begin{column}{0.5\textwidth}
          Before
          \begin{Verbatim}[fontsize=\tiny]

int mul(int a, int b) {
  return a * b;
}

void run(void) {
  ...
  mul(x, 2);
  ...
  mul(y, 2);
  ...
  mul(z, 4);
  ...
  mul(w, 4);
  ...
}
          \end{Verbatim}
        \end{column}
        \begin{column}{0.5\textwidth}
          After
          \begin{Verbatim}[fontsize=\tiny]

int mul2(int a) {
  return a * 2;
}

int mul4(int a) {
  return a * 4;
}

void run(void) {
  ...
  mul2(x);
  ...
  mul2(y);
  ...
  mul4(z);
  ...
  mul4(w);
  ...
}
          \end{Verbatim}
        \end{column}
      \end{columns}
      \note{Mainly useful when values must really be constant (masks, loop
      counters)}
    \end{frame}

\section{Future work}
    \begin{frame}{Open issues}
      \begin{itemize}
        \item Debug information
        \begin{itemize}
          \item Only time for initial work
        \end{itemize}
        \item Reconfigurability
        \begin{itemize}
          \item Needs backend support
        \end{itemize}
        \item Proper inlining
        \item Memory access
        \begin{itemize}
          \item Needs backend support
        \end{itemize}
        \item Remove next\_cycle
        \begin{itemize}
          \item Backend only
        \end{itemize}
      \end{itemize}
    \end{frame}

\section{Conclusions}
  \begin{frame}{Conclusions}
    \begin{itemize}
      \item LLVM is very suitable
      \item Defining the problem is harder than solving it
      \item Three months is short, visible progress is slow
    \end{itemize}
  \end{frame}

\end{document}
