Add examples of various problems mentioned.
[matthijs/projects/internship.git] / Report / Main / Problems / Challenges.tex
1 \section{Challenges and Solutions}
2 This section will describe the challenges faced during the work I have performed
3 and the solutions found for both the task itself and the challenges.
4
5 \subsection{What is MontiumC?}
6 A critical question popped up at the beginning of my internship: What is
7 MontiumC? Previously, there was no real specification of MontiumC. There was
8 documentation about the functions that could be used, some examples and a lot of
9 personal knowledge in the heads of the Recore employees, but ultimately MontiumC
10 was ``whatever the compiler eats''.
11
12 To be able to create a proper set of transformations, the constraints on the
13 input and output of that transformation process should be properly specified.
14 This entails two parts: Specifying the MontiumC language, and specifying the
15 Montium IR constraints, which is is the input to the backend.
16
17 Specifying Montium IR was relatively easy, since it is defined directly by the
18 backend. The MontiumC specification is slightly more complex. There are two
19 different angles to it: What does the compiler support, and what do we want the
20 compiler to support.
21
22 \subsubsection{What is supported?}
23 One angle for looking at MontiumC is seeing what the compiler can currently
24 compile and turn that into a formal specification. This approach works fine to
25 set a baseline for the compiler: A point to start improving the transformations
26 from. Apart from that, this initial specification is also useful in reviewing
27 existing MontiumC code and verifying existing transformations.
28
29 Existing MontiumC code is of course supported by the compiler (since it has been
30 tweaked until it worked). However, the existing code might not fully work within
31 the produced specification. This can happen in particular when existing code
32 makes use of corner cases in the compiler that have been missed in (or left out
33 of) the specification, because they will not work reliably in all cases.
34
35 The best way to detect these cases is making the compiler check its input using
36 an the specification. This way, any code operating outside of the specification
37 can be detected automatically. Writing such checks has not happened yet, mainly
38 because the impact of the new hardware on MontiumC is not quite clear yet.
39
40 Existing transformations, on the other hand, might miss a few corner cases. When
41 writing the specification, a particular feature might appear supported by the
42 compiler. On closer inspection, the transformation passes might not do
43 the right thing when faced with particular corner
44 cases, which either need to be fixed or put into the specification.
45
46 The best way to detect these cases is writing a lot of structured testing code,
47 which uses (combinations of) the features that are supported according to the
48 specification. This way, corner cases exposed by the testing code can be
49 detected automatically. A framework for this testing has been set up and
50 partially filled with small tests.
51
52 Building this initial specification did pose a number of challenges. Since
53 simply trying all possible C features to see if they are accepted by the
54 MontiumC compiler and thus valid MontiumC is a lengthy process and only useful
55 in a limited way. A more constructive way would be to examine the compiler
56 components to see what transformations are applied and from that derive the
57 specification for valid MontiumC. However, most of these components are not very
58 transparent. The Clang frontend supports a lot of C constructs and is not a
59 trivial piece of code. It also has support for Objective C and partially C++,
60 which makes it harder to see which code paths are actually used for compiling
61 MontiumC. This issue is only partially solved, meaning that there might still be
62 incorrect or missing cases in the specification.
63
64 Another problem is the complexity of the C language. Although individual
65 features can be described and supported with relative ease, combining features
66 can easily lead to complex constructs which are hard to transform into supported
67 Montium IR. This became more of an issue after adding features to the base
68 specification of MontiumC, since the base specification only supports a
69 few C features.
70
71 \subsubsection{What is wanted?}
72 A completely different angle of looking at this is from the requirements point
73 of view. What do we want MontiumC to support? This angle is even harder than the
74 previous one, since there are a lot of levels of requirements. Ideally, MontiumC
75 would not exist and our compiler would support the C language fully. However,
76 this would require a very complicated compiler (both frontend and backend).
77
78 Not only that, it is simply not possible to map all valid C programs to the
79 Montium hardware. "Regular" architectures don't suffer from this problem (as
80 much), since most instruction sets are not fundamentally different from the
81 features supported by C (or other imperative languages). This means that
82 anything is mappable, but with a simple compiler this will not result in the
83 most efficient code. In the Montium case, a lot of things simply cannot be
84 mapped on the hardware at all.
85
86 Considering that our ideal is not reachable (Though the new hardware might take
87 us a lot closer), every feature
88 considered for MontiumC was evaluated thoroughly for feasibility, both in hardware
89 and in the compiler. In practice, this meant that new language features would be
90 informally expressed and discussed, and only added to the specification after
91 being succesfully implemented. This is conforming to the incremental development
92 of MontiumC that was envisioned at the outset of its development.
93
94 To get a feeling for what MontiumC looks like, consider the fragment in
95 figure \ref{ExampleLow}. This is a piece of code that reads values from
96 one memory, multiplies them by two, and writes them back to another
97 memory. As you can see, this is an awful lot of code. This has two main
98 reasons. First, looping and memory indexing is very explicit and takes a
99 lot of instructions. Second, the code is effectively software pipelined
100 to make it run more efficiently.
101
102 In figure \ref{ExampleHigh} the same code is displayed, but this time
103 using higer level C features (for loops, arra indexing). This is the
104 level of code we are trying to achieve, but we're not there yet. It
105 should be noted that this is still not "normal" C, since we use the
106 "imul" function instead of the normal * operator. However, since the
107 Montium defines a lot of different operations, most of which have a
108 number of options (saturation, truncation, post shifting, etc.) these
109 cannot all be mapped onto normal C operators. By using a specific
110 function call for each, we can still distinguish between all the
111 different operations and add extra arguments where needed.
112
113 \subsubsection{What do we have now?}
114 The result of this work is a usable, but conservative, specification. It
115 defines the subset of features that should certainly be supported. In practice,
116 some other features will also work, but not reliably. Therefore, these are left
117 out of the specification.
118
119 It is not unlikely that the specification is still incorrect in a few places (or
120 rather, that the code does not implement the specification properly). Since
121 so far there has been not any automated checking of programs against the
122 specification, these errors have not been uncovered. Once the new hardware is
123 more clearly defined and the MontiumC specification is updated for it, this
124 checking should be added so the specification and compiler can be better
125 matched.
126
127 \begin{figure}
128         \caption{Low level MontiumC example}
129 \label{ExampleLow}
130 \begin{verbatim}
131 mem input;
132 mem output;
133 word factor;
134
135 void run(void) {
136   factor = from_int(2);
137   input  = alloc_mem(P0M0);
138   output = alloc_mem(P0M1);
139   set_base(input, 0);
140   set_offset(input, 0);
141   set_base(output, -1);
142   set_offset(output, -1);
143
144   next_cycle();
145   word in = read_mem(input);
146   word out = p0o0(imul(ra1(in), rc1(factor)))
147   add_offset(input, 1);
148   add_offset(output, 1);
149   init_loop(LC1, 8);
150   do {
151     write_mem(output, out);
152     in = read_mem(input);
153     out = p0m0(imul(ra1(in), rc1(factor)))
154     add_offset(input, 1);
155     add_offset(output, 1);
156   } while(loop_next(LC1));
157
158   write_mem(output, out);
159 \end{verbatim}
160 \end{figure}
161
162 \begin{figure}
163         \caption{High level MontiumC example}
164         \label{ExampleHigh}
165 \begin{verbatim}
166 P0M0 int input[10];
167 P0M1 int output[10];
168
169 void run(void) {
170   for (int i=0; i<10; ++i)
171     output[i] = mul(input[i], 2);
172 }
173 \end{verbatim}
174 \end{figure}
175
176 \subsection{Familiarizing with LLVM}
177 Since the frontend heavily relies on the LLVM project for doing it's work, one
178 of the first challenges was to get myself familiar with LLVM. There were two main
179 aspects to this: Getting to know my way around the LLVM codebase and getting to
180 know the LLVM community.
181
182 LLVM has a pretty large amount of documentation, I spent most of my first
183 weeks with reading tutorials and documents. Since there was already a (very
184 preliminary) version of the clang-based frontend, I also had some code to play
185 with.
186
187 During this period, it was not completely clear what the frontend should
188 be doing and what transformations should be written. To prevent circular
189 dependencies in my tasks (I can't write any code before I know what needs to be
190 written, but I can't really tell what's needed until I know how the code works,
191 which I can't effectively learn without actively working with it, etc.) I
192 started out with adapting the loop unrolling pass in LLVM to be better suited to
193 the Montium architecture. Eventually, this code didn't turn out to be
194 immediately useful because deciding when to unroll a loop and when not to turned
195 out rather hard (it's still not included currently). Working with this pass did
196 prove very insightful, however, as to how the LLVM framework is built and what its
197 possibilities are.
198
199 Additionally, during my working with the code in this internship I also produced
200 a number of patches for LLVM, containing bugfixes, some cleanup and
201 documentation improvements. Since the best way to integrate with any open source
202 project seems to be contributing code, I was giving commit access to the LLVM
203 tree not long thereafter. This access has proved very useful during the rest of
204 the internship, since it was now a a lot easier to make (simple) changes to the
205 LLVM framework to better suit the needs of Recore.
206
207 A major challenge during my internship was to find the balance between doing
208 work specifically for Recore, and doing work that is useful for LLVM in general.
209 Any changes that are directly required by the Montium frontend and the LLVM changes they
210 need are obvious. However, usually when making changes to the main LLVM
211 tree, just changing enough for Recore is not engough for LLVM. Since the LLVM
212 code must work on any program, not just MontiumC programs, extra changes are
213 required (see also parapgrah \ref{StayingGeneric}). This is also an issue of
214 building up credit within the LLVM community: The more you contribute to LLVM,
215 the more influence you have when things need changing. 
216
217 Lastly, this is also a matter of efficiency: If I have been working
218 with a particular piece of code intensively, it is more efficient for me to fix
219 a bug in that code than most others, even though the particular bug does not
220 interfere with the MontiumC frontend. In the end, I think I managed to find a
221 decent balance, though it might have been tipped slighly in favour of the LLVM
222 project.
223
224 \subsection{Working together}
225 Since the compiler plays a fairly central role in the development process at
226 Recore, I have been cooperating with a number of different people, in different
227 areas. On one end, the compiler is directly used by the DSP engineers, so a lot
228 of the requirements and wishes for the compiler come from them. Also, they are
229 often providing bug reports and other feedback, which ensures regular contact.
230
231 On the other end, I have been in contact with the developer of the backend very
232 intensively, since most changes made to either component needed changes in the
233 other one as well. Compiler changes also require hardware support, so working
234 with the hardware developers was not uncommon either. In practice, most
235 communication with the hardware developers went through the backend
236 developer, except for the design discussion concerning the new Montium
237 hardware design (also see section \ref{Pipelining} below).
238
239 In addition, discussions regarding design issues at various levels often happen
240 out in the open, which invites people with an opinion about something to
241 chime in, without the overhead of planning a seperate meeting for each
242 topic. This allows for very quick feedback on ideas from people in all areas
243 in an efficient way.
244
245 \subsection{Staying generic}
246 \label{StayingGeneric}
247 The toughest challenge by far was to fit the features and changes required by
248 Recore into code that is maintained by the LLVM project. The main problem here
249 is a clash of goals: The LLVM project aims for code that performs well for their
250 supported architectures, while Recore aims for code that performs well (or more
251 often, can compile at all) for the Montium architecture.
252
253 In general, these problems mainly occur because MontiumC and in particular
254 MontiumIR poses a number of constraints that are not present in other
255 architectures. This means that some transformations present in LLVM will violate
256 these constraints (which would result in better code on most other
257 architectures) resulting in miscompiled or uncompilable code.
258
259 In some cases, these extra constraints can be formulated in a generic way, such
260 that the LLVM code can handle architectures with or without the constraint.
261 Examples include providing Montium specific parameters through LLVM's 
262 ``\verb TargetData '' class and modifications to the loop unroller to support
263 custom policies.
264
265 In a lot of cases, however, the constraint is so Montium specific that changing
266 LLVM to support it is not feasible.
267
268 In a few of these cases, this meant that the backend was changed to support more
269 features of the LLVM IR. An example of this is finding datapath constants (which
270 are the result of a function in MontiumC, so hard to track by LLVM).
271
272 In other cases, Recore-specific transformations were added to solve these
273 problems. Examples of these are a transformation that removes all global
274 variables and passes them as arguments and return values instead, a
275 transformation that forcibly inlines all functions marked as ``\verb inline ''
276 and a transformation that limits variable lifetimes by introducing extra phi
277 nodes.
278
279 In a few more cases, the problems are still unresolved, effectively resulting in
280 additional constraints on the MontiumC language. Examples of these are
281 preventing instructions from being moved out of if/else blocks (which is
282 perfectly fine from an LLVM IR standpoint, but does not take into account the
283 extra meaning that an if statement has in MontiumIR) and removal of unused bits
284 from a constant (which could introduce more different constants than the Montium
285 has registers for them).
286
287
288 \subsection{New hardware design}
289 \label{Pipelining}
290 I've also been involved for a bit with the instruction scheduling algorithm
291 required for the new (pipelined) hardware design and the hardware design itself.
292 Even though this is completely outside of the area of my assignment, the initial
293 prototype of that scheduler was created by someone else using LLVM. Because of
294 my experience with LLVM, I have been assisting him with that.  Initially mostly
295 helping out with hints on LLVM coding, but later also with thinking about the
296 scheduler and hardware design.
297
298 I will not go into much detail about the new hardware and its scheduler here,
299 but I will highlight the most important challenges and tradeoffs.
300
301 \subsubsection{Tradeoffs}
302 In general, the most important tradeoff seems to be between flexibility and
303 everything else (code size, performance, complexity, hardware area). This
304 flexibility is defined in terms of possible instructions, present
305 connections, register files sizes, etc.
306
307 An important reason to be flexible is for programmability. If the hardware is
308 regular, making a compiler that produces optimal code gets a lot easier.
309 On the other hand, the compiler also limits flexibility. If the hardware
310 has flexibility that the compiler will never use, it's better to save
311 area and complexity by making the hardware less flexible. Exactly for this
312 reason, it is important to develop hardware and supporting software in parallel,
313 instead of using the hardware first, software later approach used with the
314 initial Montium. This allows for a much better balanced and usable design,
315 without any unused extras.
316
317 \subsubsection{Inner loop pipelining}
318 When trying to improve runtime performance, the main focus is on
319 optimizing loops, and inner loops (loops that contain no other loops) in
320 particular. Since inner loops are executed the most often (compared to
321 other loops and code), it is the most
322 efficient to optimize inner loops. Also, inner loops can most optimally
323 use the parellel processing power of the Montium, because they can be
324 software pipelined. 
325
326 Software pipelining means that the compiler will emit code that performs
327 operations that belong in different iterations of the original loop during the
328 same cycle. Since data dependencies within a loop body usually severely limit
329 the amount of operations that can be done in parallel, pipelining allows the
330 second (and further) iteration to start well before the first iteration is done.
331 This is done by dividing the loop body in a number of stages, that would
332 normally be executed sequentially. These stages are then executed in parallel,
333 but for different iterations (ie, run stage 2 of iteration i, while running
334 stage 1 of iteration i+1).
335
336 This approach allows a loop to be ran a lot faster than executing a
337 single iteration at a time. However, since the instructions for the
338 first and last few iterations (the prologue and epilogue) are distinctly
339 different from the loop "kernel", the number of instructions needed for
340 a pipelined loop can easily increase a lot.
341
342 However, all pipelined loops share a very distinct structure (first
343 stage 1, then stage 1+2, then stage 1+2+3, etc, then all stages at the
344 same time, similar for the epilogue). Also, every instruction in the
345 prologue and epilogue are a strict subset of the instructions in the
346 kernel. By adding some hardware support for exactly this structure, the
347 code size increase for the prologue and epilogue can be effectively
348 reduced to a fixed number of instructions (which take the number of stages as a
349 parameter and uses preloaded instructions with explicit stage annotation).
350
351 The tradeoff here is that this hardware is only usable specifically for these
352 inner loops, any other code will leave this extra hardware unused. However,
353 since pipelined inner loops appear to be very common, this should not be a
354 problem at all.
355
356 \subsubsection{Code compression}
357 Another very important tradeoff concerns codesize. In the old hardware, a lot of
358 flexibility in the original code was achieved by using inline functions (since
359 the hardware has only very limited support for code reuse through function
360 calls). This resulted in a lot of code duplication, which was compensated for by
361 using two level configuration registers to be able to reuse (partial)
362 instructions nonetheless (which will still need a lot of sequencer instructions,
363 but those will be a lot smaller than the full instruction).
364
365 On the new hardware, however, function calls are more powerful, which should
366 lead to a lot less code duplication. For this reason, putting every instruction
367 in configuration registers might actually take more space instead of less. It
368 should be noted that, the configuration registers of the old Montium are
369 effectively a compiler controlled cache that is mandatory and static
370 (instructions must be in the cache and the cache cannot be modified at runtime).
371 By lifting these limitations, we get a cache that is a lot more flexible.
372 However, since it is compiler controlled (as opposed to letting the hardware
373 decide what ends up in the cache), the performance of the code remains very
374 predictable (unlike traditional caches). Additionally, this has the advantage
375 that the size of the cache is no longer an upper bound on the program size, but
376 only the instruction memory is (which can be a lot bigger).
377
378 The tradeoff here is that the sequencer instructions will get a lot bigger,
379 since they need to contain a full instruction word (which would be preloaded
380 into the CRs in the old design) which can be up to a few hundred bits long.
381 Since not all sequencer instructions need to be this long (executing out of the
382 cache should be a lot shorter), different instruction lengths should be
383 supported. Also, some smart compression techniques should also be applied to
384 those long instruction words, though that can only be done once there is some
385 more application code to gather statistics about.