LLVM for the Apollo Guidance Computer
This is a modal window.
The media could not be loaded, either because the server or network failed or because the format is not supported.
Formal Metadata
| Title |
| |
| Title of Series | ||
| Number of Parts | 561 | |
| Author | ||
| License | CC Attribution 2.0 Belgium: You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor. | |
| Identifiers | 10.5446/44385 (DOI) | |
| Publisher | ||
| Release Date | ||
| Language |
Content Metadata
| Subject Area | ||
| Genre | ||
| Abstract |
|
00:00
ComputerNeuroinformatikBitFront and back endsComputer animation
00:18
Front and back endsComputerComputer wormComputer programModule (mathematics)Time domainComputer-generated imageryIterationPrototypeBlock (periodic table)Read-only memoryEquals signArchitectureNeumann boundary conditionParity (mathematics)Loop (music)Price indexExtension (kinesiology)OctahedronDecimalGeneric programmingCodeRepetitionACIDSequenceConstraint (mathematics)Data acquisitionFluid staticsLengthString (computer science)Absolute valueSpeicheradresseProgram codeComputer hardwareTable (information)IntegerWordBitNumberMereologySign (mathematics)AdditionFlagCodeField (computer science)Area1 (number)SpacetimeSound effectContent (media)MathematicsParsingParsingDirection (geometry)Point (geometry)NamespaceSemiconductor memoryComputer architectureCodierung <Programmierung>Slide ruleParity (mathematics)Programmer (hardware)Extension (kinesiology)Computer programmingIdentifiabilityComputer fileSubject indexingOnline helpOperator (mathematics)Statement (computer science)Front and back endsQuicksortCode2 (number)Endliche ModelltheorieAliasingProjective planeConstructor (object-oriented programming)Order (biology)ImplementationStructural loadNeuroinformatikShared memoryFlip-flop (electronics)Module (mathematics)Block (periodic table)Default (computer science)Arithmetic meanGeneric programmingSocial classRevision controlGame controllerOptical disc driveElectric generatorLimit (category theory)Bit error rateSingle-precision floating-point formatComplex numberRight angleArray data structurePatch (Unix)CASE <Informatik>Doubling the cubeDifferent (Kate Ryan album)Clique-widthDampingFile formatInformationHydraulic jumpHigh-level programming languageCompilation albumLatent heatLevel (video gaming)Pairwise comparisonComputer animation
09:03
Equals signString (computer science)OvalDefault (computer science)Parity (mathematics)Fluid staticsCodierung <Programmierung>Extension (kinesiology)OpcodeASCIIFlagBus (computing)CodeAddress spaceClefSoftware engineeringLogical constant8 (number)Sheaf (mathematics)SubsetFunction (mathematics)Computer fileLinker (computing)ImplementationStack (abstract data type)EmulatorPrice indexControl flowStatement (computer science)Point (geometry)Patch (Unix)Parity (mathematics)Function (mathematics)Assembly languageImplementationDirection (geometry)BitPointer (computer programming)ResultantSequenceCodeTask (computing)Series (mathematics)Form (programming)Transformation (genetics)Computer fileParsingProjective planeDivisorIntegerLinker (computing)Array data structurePerformance appraisalFlagSubject indexingLogical constantUniform resource locatorPredicate (grammar)Sign (mathematics)Patch (Unix)Statement (computer science)Validity (statistics)Object (grammar)Message passingFraction (mathematics)ExpressionString (computer science)Expandierender Graph2 (number)Operator (mathematics)1 (number)Link (knot theory)Extension (kinesiology)Sheaf (mathematics)NumberError messageMereologyFunctional (mathematics)Semiconductor memorySoftware testingAddress spaceTable (information)Order (biology)Instance (computer science)Pattern languageRaw image formatParameter (computer programming)outputTouchscreenRepresentation (politics)Software bugMatching (graph theory)Doubling the cubeAutomatic differentiationResource allocationMultiplication signWordNumeral (linguistics)Fitness functionLine (geometry)Front and back endsSingle-precision floating-point formatSpeicheradresseComputer programmingControl flowCASE <Informatik>MathematicsCodierung <Programmierung>SubsetDebuggerSlide ruleFlow separationCorrespondence (mathematics)Stack (abstract data type)Ocean currentComputer animation
17:47
Linker (computing)Compilation albumFile formatProcess (computing)Modal logicFunction (mathematics)Functional (mathematics)Object (grammar)CodeUniform resource locatorEquivalence relationSoftware testingComputer fileComputer programmingAssembly languageMultiplication signOperator (mathematics)Computer animation
19:55
Computer animation
Transcript: English(auto-generated)
00:05
Okay, thank you for coming. I'm going to speak about the Apollo guidance computer and my attempt to write an LLVM backend for it. So I'm going to introduce myself a little bit. I'm studying at the University of Bath and I joined Demicosm last year as a UKASF scholar.
00:27
I've been working primarily on LLVM backends and I started working on this AGC backend in October as a personal project. So I'm going to give a little bit of a background as to what the AGC actually is.
00:42
Can you speak louder please? I'll try. Yes, there's no speakers. So the Apollo guidance computer was designed by the MIT Instrumentation Laboratory
01:00
for use by NASA in their Apollo program. They used it as a general purpose controller in both the command module and Luna Lander for all the Apollo missions. There were actually three versions of the AGC developed, two for NASA and for actual use,
01:21
one by an ex-designer of the original AGC to show what could be done to overcome the limitations of the second Block II model. So firstly, the most important thing to know about the AGC's registers is that there was no meaningful concept of a register.
01:43
All data was mapped to memory locations and in the assembly registers were just defined as aliases to memory locations. Data and code share the same memory, so this is a von Neumann architecture. However, the memory was split into erasable and fixed memory
02:05
and code was generally infixed. So the AGC has 15 bits available to use for each 16-bit word. These were used to represent either a ones complement number or the encoding of an instruction.
02:23
The spare bit was used as an odd parity bit which allowed the hardware to detect basic bit errors. Adjacent words in memory could be used as double words. The sign bit must match, so this gave an effective 29-bit ones complement number.
02:45
Some instructions interpreted the data as fixed point and the most significant non-sign bit represented a half. This gives a range of plus one to minus one. So the instruction set architecture of the AGC
03:00
is quite a different architecture to what we're used to due to the fact that there was a lack of computing resources and also the assembly was designed for programmers and not compilers. So firstly, instructions were accumulator-based. Secondly, many instructions have a very complex operation
03:20
to squeeze in some sort of high-level constructs into such a small ISA. So for example, count, compare, and skip has an operation where the first thing it does is load the diminished absolute value of the given memory location into the accumulator, which means basically increment or decrement towards zero.
03:43
Then rewrite the original value back to the memory location because some memory locations modify their contents on write back. Finally, adjust the program counter according to the contents of the accumulator. So if it's greater than plus zero, then you add one.
04:02
If it's equal to plus zero, you add two. If it's less than minus zero, you add three. If it's equal to minus zero, you add four. Extend and index were basically used to modify the next instruction in some way.
04:21
Also, the assembly syntax was quite different to what we use now. It seems simple, but it's not GNU-like, so it's difficult for parsers. One thing to note is every single thing on this slide is a valid identifier.
04:43
So why would I choose to write an LLVM backend for this? So firstly, the original engineers that wrote the programming code for the AGC were amazingly talented. They had no help from high-level languages, and they worked with a huge code base, as you can see,
05:00
and still managed to produce safety-critical programs. However, in order to make the AGC more accessible and more understandable for people like me, it would be good to be able to program it in C. Secondly, I wanted to see how LLVM coped with generating code for this backend.
05:21
It's notably different from modern architectures, and LLVM is a powerful infrastructure, so I wondered how much could still be utilized for such a strange backend. Lastly, I wanted to see how well I would cope, because it was a totally new experience for me implementing a backend from scratch,
05:42
though I had been working on other LLVM backends. So I'm going to jump right into the implementation now. Firstly, some register definitions. I defined R0 to R7 explicitly, because these are internal flip-flops which have special meanings.
06:04
Double-word registers can also be defined here, like RD0. They're simply pairs of registers, and each double-word register will overlap with the ones before and after it. Special single-register classes are used to specify DAG operands for instructions
06:22
that use the accumulators or other special-purpose registers. Notice there's a lot of effort in documentation here. Since this was early in the project, it's all downhill from here. Generating definitions. I tried several approaches to modeling the memory of the AGC,
06:42
but in the end a simple brute-force approach seemed to work the best. So I've generated register definitions for every single memory location, and double-word memory location. And such of these registers are classified as needed by the different instruction formats.
07:00
The instruction definitions don't actually specify these register classes, but instead use immediate that actually represent the register's memory location. The reason this is is because in table gen it's hard to define. I want this integer to be represented as an octal number, and AGC requires octal numbers.
07:24
Instruction definitions are relatively simple to specify according to the specifications, but it's worth noting the addition of extra codes. So the AGC designers figured out a way to double the effective encoding space of their architecture by interpreting instructions completely differently if they're a prefix with an extend instruction.
07:43
I used the is-extra-code bit to mark instructions which are extra codes, and another decoder namespace was necessary due to the shared encoding. Another issue with decoding these instructions in general was that accumulator operands were specified as DAG operands,
08:00
but had no encoding related to them. So a fix for this is this decode-null-ops patch. So it turns out that fix-lend-decoder-emitter does not add fields that don't have bits related to them or to their tied operands, and this causes problems later on as other parts of the MC layer assume that all DAG operands are present.
08:23
So a fix was to add a flag for instructions where this is the case, and for fix-lend-decoder-emitter to add a default zero-width field to the op-info for instructions with this annotation. So another area that needed changes in generic code
08:42
was parsing of some of AGC's directives, which tripped up the ASM parser. So the AGC's $file directive operates the same way as a .file directive in that it actually includes a given file. So here I'm just parsing the rest of the statement into a file name and then using the same method to include the file as .file does.
09:09
Similarly, an equals operator works exactly the same as an equals character, so I've just duplicated the code with an extra case.
09:21
So some directives didn't trip up the ASM parser, so I implemented them instead by custom missing pseudo-instructions. So here the bank and setlock directives are handled by switching ELF sections. So bank is used to switch which memory bank the assembly is currently outputting to, and setlock is used to switch assembly output to an explicit address.
09:46
Some other directives were eraser-knocked, which are used to emit bits into the current output location, so only needed to be implemented in MC code-emitter. Just a short note on parity.
10:01
So instructions in the AGC needed a parity bit to be emitted in the least significant bit. So I accumulate the parity bit here by XORing the current parity of the next incoming bit. So this is used when emitting bits in MC code-emitter.
10:22
So dealing with extra code instructions throughout the MC layer was a tricky task. So in the ASM parser, passing an extend instruction causes a flag to be set in this check early target match predicate, and the instruction will not be emitted as an MC instruction. So the next time around when pass instruction is called,
10:42
this flag is cleared and passing extra code is set, indicating that the current instruction should be an extra code. So checking the is extra code bit after passing the next instruction indicates whether the extend plus extra code sequence is followed correctly,
11:03
and I error on both an extend followed by a non-extra code and an extra code that's not preceded by an extend. To emit an extra code instruction, the solution was simply to emit the raw bytes of extend followed by the bytes of the instruction.
11:25
Decoding an extra code instruction required testing if the decoded instruction was an extend. Then if so, taking the next instruction and decoding it using a separate extra code decoding table. Also notice masking parity bit before decoding instructions.
11:48
So finally moving on to some lowering. So some simple patterns were enough for some instructions to allow lowering to them because they had a simple DAG representation.
12:04
Other instructions required some more convincing. The multiply and divide instructions don't fit well with the corresponding DAG nodes. So specifically multiply takes two single words and produces a double word output. So it only matches an i32 multiply with sign extended inputs.
12:28
Divide, which isn't, the implementation isn't on the screen, takes one double word numerator, a single word denominator, and produces two single words, a result and a remainder. So it matches either a divide or a remainder
12:43
with a sign extended denominator and the output is a sign extend. Materialising constants was one of the most difficult parts of the back end because there's no instructions that take immediate operands. So there is a sequence of directives
13:02
that can be emitted to output a constant, but in order to expand that sequence I first had to select all instances of constants into a pseudo instruction. So to expand this pseudo instruction into a sequence
13:21
I had to create a pre-emit pass to expand pseudo instructions. Since I wanted this sequence to not be interrupted, this has to be done with add pre-emit pass to, which is the latest pre-emit pass. So when expanding the constant I take the immediate operand, first ensure that it's converted to a 15-bit ones complement value.
13:42
Next I create a new sequence of directives, first to switch the output location of the binary to the destination register, then to output raw bits at that location, and then to switch back to the original bank for the function.
14:02
Notice that there is a bug with this implementation, which is that this implies that register allocation for the given register can only be unique for the entire program, and I haven't implemented a fix for this. So if you use a constant in a register more than once, then you'll just end up with the latest constant that was lowered.
14:27
So there's quite a bit of future work. I've basically done most of the MC layer and a little bit of lowering, but several things in the Clang front end and IR transformations
14:41
produce IR that won't be lowered correctly in the ADC backend. So first, bytes cannot be assumed to be 8 bits. There are some mechanical changes to be made, but the particular problem is that generic pointers will default to i8*.
15:02
Secondly, some transformations, for example, evaluation of constant expressions, assume that 2's complement numbers are used, so producing valid code for the AGC. This is quite a likely assumption that's going to be common throughout the code base, so it might take a while to hunt down all the occurrences.
15:22
But for other restrictions, it might be worth defining a subset of C to compile for AGC. Another thing I'd like to do is make sure that the assembly output of LLVM resembles actual AGC code.
15:42
So to do this, I need to remove all GNU ALF directives and replace them with AGC directives. So there's already a project that has an assembler, and I'd like the output files to be assembled with that.
16:01
So the AGC backend can create valid object files, but a lot of the operation relies on linker functionality, and I haven't implemented a linker yet, so that needs to be done. AGC doesn't have a stack pointer, so I need to emulate a stack to use to parse arguments.
16:25
Index instruction basically is what's used for indexing in that it adds a constant value to the memory location that you give it, so it can be used to index a stack.
16:40
I want to try to lower control flow statements to the CCS instruction, which could be quite difficult. So some things I found in LLVM. So this might be obvious, but ASM parser is not flexible to non-GNU-like assembly.
17:04
Fixed-lane decoder emitter requires this decode null ops patch to function for MC instructions within operands. The lexer converts octal immediate itself without the target knowing, so the problem with the AGC backend is
17:22
all operands must be in octal form. So when the lexer converts, something proceeded with a zero to an octal integer. I don't know whether I still need to convert the immediate back to an octal or not, so I have to get the raw string that was converted first
17:42
and do it myself. And that's the end of my slides. Thank you. Any questions? Yes?
18:01
So in the end, were you able to compile the C code into the C code? So I can compile basic functions with ALU operations. I can. There are a few IR tests as well, but I still need to implement. I think function calling is the next important thing to implement
18:22
before I can actually get the program running. Anything else? You mentioned the linker. Does that mean there is a defined object file format of some sort? So the question was whether there's a defined object file format,
18:43
and the answer is no. I'm just using ELF and using that as a stand-in. I'm just thinking, back at the time, was there a linker? Or was it all in paper cards? So I guess the idea, so the question was,
19:02
was there a linker at the time? And the idea was that the way that you'd get a program to stick together was just by textually including all the other files, so a linker wasn't really needed. Is that a question?
19:23
I guess the equivalent of a linker was just using one function per event? Yeah, so the assembler did the entire job because it controlled the output location and switched banks and did that as necessary.
19:44
Anything else?