ca33370d7be489528e05be2e1288de9050704c19
[matthijs/projects/internship.git] / Report / Main / Problem / Challenges.tex
1 \section{Challenges and Solutions}
2 This section will describe the challenges faced during each of the tasks and the
3 solutions found for both the task itself and the challenges.
4
5 \subsection{What is MontiumC?}
6 A critical question popped up during 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 supported by the compiler (since it has been tweaked
30 until it worked). However, the existing code might not fully work within the
31 produced specification. This can happen in particular when existing code makes
32 use of corner cases in the compiler that have been missed in (or left out of)
33 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.
38
39 Existing transformations, on the other hand, might miss a few corner cases. When
40 writing the specification, a particular feature might appear supported by the
41 compiler. On closer inspection, the transformation passes might miss some corner
42 cases, which either need to be fixed or put into the specification.
43
44 The best way to detect these cases is writing a lot of structured testing code,
45 which uses (combinations of) the features that are supported according to the
46 specification. This way, corner cases exposed by the testing code can be
47 detected automatically.
48
49 Building this initial specification did pose a number of challenges. Since
50 simply trying all possible C features to see if they are accepted by the
51 MontiumC compiler and thus valid MontiumC is a lengthy process and only useful
52 in a limited way. A more constructive way would be to examine the compiler
53 components to see what transformations are applied and from that derive the
54 specification for valid MontiumC. However, most of these components are not very
55 transparent. The Clang frontend supports a lot of C constructs and is not a
56 trivial piece of code. It also has support for Objective C and partially C++,
57 which makes it harder to see which code paths are actually used for compiling
58 MontiumC. This issue is only partially solved, meaning that there might still be
59 incorrect or missing cases in the specification.
60
61 Another problem is the complexity of the C language. Although individual
62 features can be described and supported with relative ease, combining features
63 can easily lead to complex constructs which are hard to transform into supported
64 Montium IR. This became more of an issue after adding features to the base
65 specification of MontiumC, though.
66
67 \subsubsection{What is wanted?}
68 A completely different angle of looking at this, is from the requirements point
69 of view. What do we want MontiumC to support? This angle is even harder than the
70 previous one, since there are a lot of levels of requirements. Ideally, MontiumC
71 would not exist and our compiler would support the C language fully. However,
72 this would require a very complicated compiler (both frontend and backend).
73
74 Not only that, it is simply not possible to map all valid C programs to the
75 Montium hardware. "Regular" architectures don't suffer from this problem (as
76 much), since most instruction sets are not fundamentally different from the
77 features supported by C (or other imperative languages). This means that
78 anything is mappable, but with a simple compiler will not result in the most
79 efficient code. In the Montium case, a lot of things simply cannot be mapped on
80 the hardware at all.
81
82 Considering that our ideal is not reachable (by far), every feature in our
83 wanted MontiumC should be evaluated thoroughly for feasibility, both in hardware
84 and in the compiler. In practice, this meant that new language features would be
85 informally expressed and discussed, and only added to the specification after
86 being succesfully implemented. This is conforming to the incremental development
87 of MontiumC that was envisioned at the outset of its development.