From 99e9c178cfa5a9a46d8df185f6d72b8f1e1a0981 Mon Sep 17 00:00:00 2001 From: Matthijs Kooijman Date: Wed, 2 Jul 2008 12:44:02 +0200 Subject: [PATCH] Finish presentation. --- Presentations/InternalProgress.tex | 257 ++++++++++++++++++++--------- 1 file changed, 176 insertions(+), 81 deletions(-) diff --git a/Presentations/InternalProgress.tex b/Presentations/InternalProgress.tex index 267f1be..6bbc601 100755 --- a/Presentations/InternalProgress.tex +++ b/Presentations/InternalProgress.tex @@ -77,26 +77,7 @@ \pgfuseimage{Workflow} \end{frame} -\section{Tasks} - - \subsection{Original tasks} - \begin{frame}{Original tasks} - \begin{itemize} - \item Select LLVM transformations - \item Improve and add transformations - \item Provide debugging information - \end{itemize} - \end{frame} - - \subsection{Extra tasks} - \begin{frame}{Extra tasks} - \begin{itemize} - \item What is MontiumC? - \item What is Montium IR? - \item Reconfigurable binaries - \end{itemize} - \end{frame} - +\section{Past work} \begin{frame}{What is MontiumC?} \note{Two angles: What do we want, and what do we support.} \begin{itemize} @@ -104,7 +85,8 @@ \item Challenges: \begin{itemize} \item Clang is nontransparent - \note[item]{Clang --- A lot of special cases} + \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 @@ -159,7 +141,7 @@ P0M1 int output[10]; void run(void) { for (int i=0; i<10; ++i) - output[i] = input[i] * 2; + output[i] = mul(input[i], 2); } \end{Verbatim} \end{column} @@ -167,105 +149,218 @@ void run(void) { \end{frame} \note{} % Empty filler note page - \begin{frame}{What is Montium IR?} + \begin{frame}{Using LLVM transformations} \begin{itemize} - \item Status: Initial version \item Challenges: \begin{itemize} - \item Backend is a fast moving target - \item Corner cases - \note[item]{Corner case --- global constants} - \item Hardware dependencies - \note[item]{Hardware --- Limited number of conditionals possible} + \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}{Selecting LLVM transformations} + \begin{frame}{Using LLVM transformations} \begin{itemize} - \item Status: Done - \item Challenges: + \item Achievements: \begin{itemize} - \item LLVM Passes assume a lot - \note[item]{Assumptions --- Immediates are not free} - \item Montium has specific constraints - \note[item]{Constraint --- Implicit cycle boundaries and ordering} + \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}{Improving / adding transformations} + \begin{frame}{Creating new transformations} \begin{itemize} - \item Status: Ongoing + \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 easier} - \item New LLVM features + \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}{Debugging information} + \begin{frame}{Creating new transformations} \begin{itemize} - \item Status: Not started - \item Challenges: + \item Achievements: \begin{itemize} - \item Not much LLVM support yet - \note[item]{LLVM support --- New in clang/backend, no support in - transformations yet.} - \item Transformations - \note[item]{Transformations --- Global arguments, argument addition, - removal, etc.} + \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}{Reconfigurable binaries} + \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 Status: Recently started - \item Challenges: + \item Debug information \begin{itemize} - \item Tracking variables - \note[item]{Tracking --- Through all steps of the process} - \item Loss of optimizations - \note[item]{Optimizations --- Hard to encode constraints} - \item Mostly a backend problem + \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{Work process} - \begin{frame}{Working at Recore} - \begin{itemize} - \item Smart people - \item Fast communication - \note[item]{Communication --- Mixed teams, easy to "listen in".} - \item Constructive brainstorming - \note[item]{Brainstorming --- Evaluating different ideas and approaches.} - \end{itemize} - \end{frame} - - \begin{frame}{Working with LLVM} - \begin{itemize} - \item Large community - \note[item]{Community --- Companies involved, a lot of full time - developers.} - \item Great support - \note[item]{Support --- mailing list, bug reports solved within 1/2 days.} - \item Slightly conflicting goals - \note[item]{Goals --- LLVM aims mainly at "regular" architectures.} - \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! + \item Three months is short, visible progress is slow \end{itemize} \end{frame} -- 2.30.2