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.
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''.
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.
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
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.
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.
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.
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.
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.
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.
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
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).
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.
86 Considering that our ideal is not reachable (by far), every feature
87 considered for MontiumC was evaluated thoroughly for feasibility, both in hardware
88 and in the compiler. In practice, this meant that new language features would be
89 informally expressed and discussed, and only added to the specification after
90 being succesfully implemented. This is conforming to the incremental development
91 of MontiumC that was envisioned at the outset of its development.
93 To get a feeling for what MontiumC looks like, consider the fragment in
94 figure \ref{ExampleLow}. This is a piece of code that reads values from
95 one memory, multiplies them by two, and writes them back to another
96 memory. As you can see, this is an awful lot of code. This has two main
97 reasons. First, looping and memory indexing is very explicit and takes a
98 lot of instructions. Second, the code is effectively software pipelined
99 to make it run more efficiently.
101 In figure \ref{ExampleHigh} the same code is displayed, but this time
102 using higer level C features (for loops, arra indexing). This is the
103 level of code we are trying to achieve, but we're not there yet. It
104 should be noted that this is still not "normal" C, since we use the
105 "imul" function instead of the normal * operator. However, since the
106 Montium defines a lot of different operations, most of which have a
107 number of options (saturation, truncation, post shifting, etc.) these
108 cannot all be mapped onto normal C operators. By using a specific
109 function call for each, we can still distinguish between all the
110 different operations and add extra arguments where needed.
113 \caption{Low level MontiumC example}
121 factor = from_int(2);
122 input = alloc_mem(P0M0);
123 output = alloc_mem(P0M1);
125 set_offset(input, 0);
126 set_base(output, -1);
127 set_offset(output, -1);
130 word in = read_mem(input);
131 word out = p0o0(imul(ra1(in), rc1(factor)))
132 add_offset(input, 1);
133 add_offset(output, 1);
136 write_mem(output, out);
137 in = read_mem(input);
138 out = p0m0(imul(ra1(in), rc1(factor)))
139 add_offset(input, 1);
140 add_offset(output, 1);
141 } while(loop_next(LC1));
143 write_mem(output, out);
148 \caption{High level MontiumC example}
155 for (int i=0; i<10; ++i)
156 output[i] = mul(input[i], 2);
161 \subsection{Familiarizing with LLVM}
162 Since the frontend heavily relies on the LLVM project for doing it's work, one
163 of the first challenges was to get myself familiar with LLVM. There were two main
164 aspects to this: Getting to know my way around the LLVM codebase and getting to
165 know the LLVM community.
167 LLVM has a pretty large amount of documentation, I spent most of my first
168 weeks with reading tutorials and documents. Since there was already a (very
169 preliminary) version of the clang-based frontend, I also had some code to play
172 During this period, it was not completely clear what the frontend should
173 be doing and what transformations should be written. To prevent circular
174 dependencies in my tasks (I can't write any code before I know what needs to be
175 written, but I can't really tell what's needed until I know how the code works,
176 which I can't effectively learn without actively working with it, etc.) I
177 started out with adapting the loop unrolling pass in LLVM to be better suited to
178 the Montium architecture. Eventually, this code didn't turn out to be
179 immediately useful because deciding when to unroll a loop and when not to turned
180 out rather hard (it's still not included currently). Working with this pass did
181 prove very insightful, however, as to how the LLVM framework is built and what its
184 Additionally, during my working with the code in this internship I also produced
185 a number of patches for LLVM, containing bugfixes, some cleanup and
186 documentation improvements. Since the best way to integrate with any open source
187 project seems to be contributing code, I was giving commit access to the LLVM
188 tree not long thereafter. This access has proved very useful during the rest of
189 the internship, since it was now a a lot easier to make (simple) changes to the
190 LLVM framework to better suit the needs of Recore.
192 A major challenge during my internship was to find the balance between doing
193 work specifically for Recore, and doing work that is useful for LLVM in general.
194 Any changes that are directly required by the Montium frontend and the LLVM changes they
195 need are obvious. However, usually when making changes to the main LLVM
196 tree, just changing enough for Recore is not engough for LLVM. Since the LLVM
197 code must work on any program, not just MontiumC programs, extra changes are
198 required (see also parapgrah \ref{StayingGeneric}). This is also an issue of
199 building up credit within the LLVM community: The more you contribute to LLVM,
200 the more influence you have when things need changing.
202 Lastly, this is also a matter of efficiency: If I have been working
203 with a particular piece of code intensively, it is more efficient for me to fix
204 a bug in that code than most others, even though the particular bug does not
205 interfere with the MontiumC frontend. In the end, I think I managed to find a
206 decent balance, though it might have been tipped slighly in favour of the LLVM
209 \subsection{Working together}
210 Since the compiler plays a fairly central role in the development process at
211 Recore, I have been cooperating with a number of different people, in different
212 areas. On one end, the compiler is directly used by the DSP engineers, so a lot
213 of the requirements and wishes for the compiler come from them. Also, they are
214 often providing bug reports and other feedback, which ensures regular contact.
216 On the other end, I have been in contact with the developer of the backend very
217 intensively, since most changes made to either component needed changes in the
218 other one as well. Compiler changes also require hardware support, so working
219 with the hardware developers was not uncommon either. In practice, most
220 communication with the hardware developers went through the backend
221 developer, except for the design discussion concerning the new Montium
222 hardware design (also see section \ref{Pipelining} below).
224 In addition, discussions regarding design issues at various levels often happen
225 out in the open, which invites people with an opinion about something to
226 chime in, without the overhead of planning a seperate meeting for each
227 topic. This allows for very quick feedback on ideas from people in all areas
230 \subsection{Staying generic}
231 \label{StayingGeneric}
232 The toughest challenge by far was to fit the features and changes required by
233 Recore into code that is maintained by the LLVM project. The main problem here
234 is a clash of goals: The LLVM project aims for code that performs well for their
235 supported architectures, while Recore aims for code that performs well (or more
236 often, can compile at all) for the Montium architecture.
238 In general, these problems mainly occur because MontiumC and in particular
239 MontiumIR poses a number of constraints that are not present in other
240 architectures. This means that some transformations present in LLVM will violate
241 these constraints (which would result in better code on most other
242 architectures) resulting in miscompiled or uncompilable code.
244 In some cases, these extra constraints can be formulated in a generic way, such
245 that the LLVM code can handle architectures with or without the constraint.
246 In a lot of cases, however, the constraint is so Montium specific that changing
247 LLVM to support it is not feasible. In a few cases, this meant that the backend
248 was changed to support more features of the LLVM IR. In other cases, a
249 Recore-specific transformations was added to solve these problems. In a few more
250 cases, the problems are still unresolved, effectively resulting in additional
251 constraints on the MontiumC language.
253 \subsection{New hardware design}
255 I've also been involved for a bit with the instruction scheduling algorithm
256 required for the new (pipelined) hardware design and the hardware design itself.
257 Even though this is completely outside of the area of my assignment, the initial
258 prototype of that scheduler was created by someone else using LLVM. Because of
259 my experience with LLVM, I have been assisting him with that. Initially mostly
260 helping out with hints on LLVM coding, but later also with thinking about the
261 scheduler and hardware design.
263 I will not go into much detail about the new hardware and its scheduler here,
264 but I will highlight the most important challenges and tradeoffs.
266 \subsubsection{Tradeoffs}
267 In general, the most important tradeoff seems to be between flexibility and
268 everything else (code size, performance, complexity, hardware area). This
269 flexibility is defined in terms of possible instructions, present
270 connections, register files sizes, etc.
272 An important reason to be flexible is for programmability. If the hardware is
273 regular, making a compiler that produces optimal code gets a lot easier.
274 On the other hand, the compiler also limits flexibility. If the hardware
275 has flexibility that the compiler will never use, it's better to save
276 area and complexity by making the hardware less flexible. Exactly for this
277 reason, it is important to develop hardware and supporting software in parallel,
278 instead of using the hardware first, software later approach used with the
279 initial Montium. This allows for a much better balanced and usable design,
280 without any unused extras.
282 \subsubsection{Inner loop pipelining}
283 When trying to improve runtime performance, the main focus is on
284 optimizing loops, and inner loops (loops that contain no other loops) in
285 particular. Since inner loops are executed the most often (compared to
286 other loops and code), it is the most
287 efficient to optimize inner loops. Also, inner loops can most optimally
288 use the parellel processing power of the Montium, because they can be
291 Software pipelining means that the compiler will emit code that performs
292 operations that belong in different iterations of the original loop during the
293 same cycle. Since data dependencies within a loop body usually severely limit
294 the amount of operations that can be done in parallel, pipelining allows the
295 second (and further) iteration to start well before the first iteration is done.
296 This is done by dividing the loop body in a number of stages, that would
297 normally be executed sequentially. These stages are then executed in parallel,
298 but for different iterations (ie, run stage 2 of iteration i, while running
299 stage 1 of iteration i+1).
301 This approach allows a loop to be ran a lot faster than executing a
302 single iteration at a time. However, since the instructions for the
303 first and last few iterations (the prologue and epilogue) are distinctly
304 different from the loop "kernel", the number of instructions needed for
305 a pipelined loop can easily increase a lot.
307 However, all pipelined loops share a very distinct structure (first
308 stage 1, then stage 1+2, then stage 1+2+3, etc, then all stages at the
309 same time, similar for the epilogue). Also, every instruction in the
310 prologue and epilogue are a strict subset of the instructions in the
311 kernel. By adding some hardware support for exactly this structure, the
312 code size increase for the prologue and epilogue can be effectively
313 reduced to a fixed number of instructions (which take the number of stages as a
314 parameter and uses preloaded instructions with explicit stage annotation).
316 The tradeoff here is that this hardware is only usable specifically for these
317 inner loops, any other code will leave this extra hardware unused. However,
318 since pipelined inner loops appear to be very common, this should not be a
321 \subsubsection{Code compression}
322 Another very important tradeoff concerns codesize. In the old hardware, a lot of
323 flexibility in the original code was achieved by using inline functions (since
324 the hardware has only very limited support for code reuse through function
325 calls). This resulted in a lot of code duplication, which was compensated for by
326 using two level configuration registers to be able to reuse (partial)
327 instructions nonetheless (which will still need a lot of sequencer instructions,
328 but those will be a lot smaller than the full instruction).
330 On the new hardware, however, function calls are more powerful, which should
331 lead to a lot less code duplication. For this reason, putting every instruction
332 in configuration registers might actually take more space instead of less. It
333 should be noted that, the configuration registers of the old Montium are
334 effectively a compiler controlled cache that is mandatory and static
335 (instructions must be in the cache and the cache cannot be modified at runtime).
336 By lifting these limitations, we get a cache that is a lot more flexible.
337 However, since it is compiler controlled (as opposed to letting the hardware
338 decide what ends up in the cache), the performance of the code remains very
339 predictable (unlike traditional caches). Additionally, this has the advantage
340 that the size of the cache is no longer an upper bound on the program size, but
341 only the instruction memory is (which can be a lot bigger).
343 The tradeoff here is that the sequencer instructions will get a lot bigger,
344 since they need to contain a full instruction word (which would be preloaded
345 into the CRs in the old design) which can be up to a few hundred bits long.
346 Since not all sequencer instructions need to be this long (executing out of the
347 cache should be a lot shorter), different instruction lengths should be
348 supported. Also, some smart compression techniques should also be applied to
349 those long instruction words, though that can only be done once there is some
350 more application code to gather statistics about.