GopherCon 2016: Rob Pike - The Design of the Go Assembler

thank you that's the most enthusiastic and largest response for a talk about assembly language in many years you might wonder why we're talking about the assembler and there's a reason but I'm going to come to it first of all you might ask but why do we care about assembly language at all so let's go back to 1974 quote from an IBM manual which reads the most important single thing to realize about assembler language is that it enables the programmer to use all system/360 machine functions as if he were coding in system/360 machine language now there's a lot of sort of dated aspects of that but the fundamental point is right assembler is how you talk to the machine at the very lowest level and in fact even today we still need assembly language it used to be that all you had was assembler and then what we call high level languages like Fortran and COBOL came along and sort of over time but slowly displaced them and even C for a while was argued as being you know a high level language when when you had assembler available but we still need assembler today because of this access it provides the Machine you needed to bootstrap your environment to get the stacks running to switching between contexts in the go world go routines switching is all done and similar there's a performance aspect sometimes you can just hand write code that's better then the compiler can give you and for instance in the math big package in the ghost standard library there's a fairly substantial amount of assembler because the core routines of that library are so much more efficient when you get you know cheat the compiler and do something smarter than the compiler can figure out and also sometimes there's just features in the hardware that may be new or unusual or not worth putting in the language but you can get at with assembler and that includes things like some of the new crypto instructions on the current CPUs but for me the most important thing about assembly language is it's the way that some people anyway think about the computer it's that the definition of what the instruction set is how the machine works the way we actually think about it so even if you're not an assembler programmer and I hope none of you are it's worth understanding a little bit about assembler and then just to know how the computer works that said I'm not going to actually talk very much about assembly language per se and that's actually kind of the point so first of all many of you might not know sm assembler very well so let me show you some examples in roughly chronological order here's the IBM system/360 that's the one that that quote was about and I'm don't worry about what it says just sort of look at it there's going to be a few gue stealthy slides here this is from the Apollo 11 guidance computer which was all programmed in assembler we went to the moon in assembly language here's the pv 10a this is actually well commented compared to some assemble you'll find here's a PDP 11 this is actually part of the assembler for assembly language in unix v 6 which is of course written in assembler at the time it became c later here's motorola 68000 here's the Cray one I like this one because it's from Robert gray-smith PhD thesis which brings us home so what you may notice about all of these is that although they're all different they're also all kind of the same they have a very clear common structure the assembly language tends to be in columns there's labels at the left instructions operands and comments out at the right the operands themselves tend to be things like registers or literal constants or memory addresses but they're all sent tactically fairly similar between the varieties of architecture and there's exceptions if you look at the crate example it's actually different you encode an add instruction with a plus sign like an arithmetic expression but all that's really saying under the covers is this is an add instruction and these are the registers so it's really the same kind of thing in other words if you step way way way back to me at least CPUs look pretty much the same nowadays there are counter examples but most of them and certainly all the ones that go runs on are pretty much the same if you ignore a lot of detail let's use that let's use that ignoring the detail to do something interesting in fact we can construct a common grammar for all of these machines and the realization that we could do that was about 30 years in the making so back around the mid 80s Ken Thompson and I were starting to think about what would become plan nine and Ken wrote a new C compiler which actually lived on into becoming the C compiler and the go tools up to a few years ago and that was on a sequence symmetric multiprocessor machine for the National 32,000 CPU from from national Panasonic and I think it was the first 32-bit CPU that was generally available on a microchip but Ken did some funny stuff that made not a lot of sense to some people but turned out to be really important for later because that's the kind of thing can does the compiler didn't actually generate real instructions it generated what you might think of as pseudocode and then the second program that ran on the output of the compiler which is the linker actually turned those pseudo instructions into real instructions and here's a hypothetical example we have a move instruction that's putting as literal zero into a variable and it might be come in by the time it comes out of the linker and runs on the machine something like an XOR of a temporary register to itself which will settle the bits to zero and then a store of that register into a variable I don't worry about the details it's just what comes out of the what actually the machine is running might not look exactly like what we're putting into the assembler and this process of making up what the real instructions are for the pseudo instructions we call instruction selection and a really good example of a pseudo instruction is the subroutine routine return instruction which can hey is called ret which has been ret for 30 years now but it depends what machine you're on on some machines it's actually called ret in the manuals but in others it might be jumping through a link register or an indirection through a dedicated register or other things at all and so the way to think about the assemblers it's just a way to handwrite the pseudo instructions that the compiler is actually generating and unlike most architectures in the planning world the compiler did not run the assembler it actually fed directly to the linker so the pieces look like this the top line is the sort of traditional architecture and I believe is how GCC even today still runs there's a compiler that takes the high level code turns it into a assembly language the assembler then generates the real instructions and the linker puts the pieces together to build the binary the bottom two are what the plan line architecture looks like the assembler in effect was cut in half and the first part of the assembler got stuck into the compiler and the second part of the assembler went into the linker and so what's flowing across that red line is kind of a binary representation of the pseudo instructions and all the assembler is doing in the plan line world is giving you a way to write textual versions of instructions that become the student instructions that drive the linker so this was actually kept up through many generations the plan line assemblers went along with this they were individual C programs with the at grammar one for each architecture and they were sort of a suite but they're all different programs each one was written fresh they shared code but not really it was it was kind of messy and when go started to happen in the it was at 2007 we started the go compilers were added to this pile of funnily named programs eg and 6g were the go compilers and they use the same model they fit this middle line here on this diagram and it's separation the way it was done actually had a lot of advantages for how Co was built under the covers but I don't have time to go into that today and go 1.3 we had an idea that we really wanted to get rid of all the C code and move to a go implementation but it was going to take us a while to do that but we started the process with the go 1.3 release which began by Russ took a big chunk of the linker and pulled it out and made a library called Lib blank a big piece of which was called what we call the instruction selection algorithm nowadays this library is called Abu was called Lin blank Lin and then the compiler used Lib link to generate the real instructions from the pseudo instructions in its intermediate representation and the reason there are several reasons for doing this but the most important one is it gave us a faster build because although the compiler is now doing more work because it's doing the instruction selection that the linker used to do it means that it only does it once for each library and so when you every time you in the old world would link in the funk package for instance it would do instruction selection for printf every time which is clearly silly now we do it once the linker doesn't have to and so the compiler slowed down but the builds actually sped up and the assembler can use the same design and use the Erbs library but the key point about this step is we didn't change anything for the user the input language is the same the output is the same syllabi Nury but the pieces are different so this is the old diagram I showed you right compiler assembler link is the grand old scheme the plan nine world has a compiler driving the linker or the assembler during the linker as of 1.3 it changes to this and we flip back and forth between these little so you can see the difference I'm sorry I don't animate slides well and you can see what's happened is we now have a much more traditional linker it's getting real instructions because the obsolescence structure selection has been moved from the linker into the back end of the compiler in the assembler and so now the assembler and the compiler are somewhat close of the old scheme if you include the assembler as part of the process so the new go assembler is a weird thing there's really nothing else like it but what it does is take in textual descriptions of pseudo instructions and generate real instructions for the linker so 1.5 the big step we're getting rid of seed so we've done a lot of prep with 1/3 and 1/4 but now we actually finish the job so Russ wrote a translator that generated go programs from the old C source for the go compilers and also for the linkers by the way and the old labeling caught rewritten into a suite of libraries which were collectively calling object is the portable part and then sub directories of that contain machine dependent parts that know about the details of each architecture and there's been a couple of previous presentations about this work it's an interesting story in itself Russ gave a talk a gopher con 2 years ago but it's quite out of date we actually did something quite different from what he talked about and then in gopher fest 2015 I gave a higher level but more accurate view of what really happened in 1.5 so the compilers now instead of being 6g and HD and all these other weirdly named guys they all became a single program called compile and so you run go to compile and you configure it literally by setting the standard environment variables which are officially pronounced goose and Gorge now with the same thing for the linker you got to go to a link so you set your goose you set your Gorch and now you can compile program right but some of you may be thinking how is it possible for a single compiler to handle all these architectures we know that cross compilation is really really difficult well actually it's not you set the plan for it the thing to notice here is there's only one input language it's called go and as far as the compiler is concerned there's really only one output thing which is those pseudo instructions in binary form that are being delivered to the object library so all we have to do is configure the odds library using the variables when the tool starts I'll show you how that's done in a minute now for the assembler we actually panned Trent your sorting machine translated the assemblers from C to go but it was messy and I didn't like it so I proposed that we write a single program from scratch to replace all of them do it in go and replace all those assemblers with a single program go to azzam and again goose and gore go and do all the configuring but there's a question you might have here which is that assembly language isn't go every machine has a different set of instructions that if set of registers it's not one output language how are you going to fix this well in fact they are kind of the same let me show you here's an example program this is a simple program that just adds two integers and returns the sum I'm now going to show you what the compiler prints out as pseudo instructions if you ask it with the minus S flag to show you the assembler and I've trimmed a lot of the noise there's a lot of noise if you do this but these are the instructions that actually come out pseudo instructions that come out of the stat phase of the compiler here's the 32-bit don't worry about the details again just take the Gestalt there's a 64-bit x86 also called a nd 64 there's the 32-bit arm there's a 64-bit arm there's the system 390 the IBM machine which is new to us but certainly not new to the rest of world there's a 64-bit MIPS there's a 64-bit power and you notice there's a kind of similarity here it's because they're really all the same language partly that's by design because we've just kept using essentially a national 32,000 assembler for the last 30 years and just change the machine underneath but also because of some of they really are the same they're just instructions and registers operands literals labels it's all the same stuff the only real variation that matters is that the instructions have different names the registers have different names and sometimes the offsets vary but that's just a feature of how big the word size is on the machine this all goes back to Ken's national 32,000 assembler that is national 3000 December language as Ken thinks of it adapted to a power PowerPC today and so we have all the pieces we need because we really do have the sync a common input language we have the obvious library for the backend so we can write an assembler now there's a problem with doing this which some people object to which is that if you go to the national or the the PowerPC manual and look at the assembly language it doesn't look like this it's it's got different syntax sometimes the instructions are different names because these are really pseudo instructions at some level we don't really mind though to an outsider can merely off-putting when they see goes assembler and how odd it looks all those capital letters and weird stuff but because we have this common assembly language across all these machines we get a tremendous result which I'm arriving at and so we think that's a trade-off worth making and it's not very hard plus once you learn how to program a 68000 in Ken's assembly you can program a PowerPC what's the difference so how does this work the 1.5 assembler is as I'd like to think of as the apotheosis of assemblers you give it any machine you want and it'll assembled it for you it's a new program written entirely and go it has a common lexer and parser that just takes the input language whatever you give it and then turns that instruction parses it into a data structure which describes the instruction in a binary form and delivers that to this new Aubrey which has machine dependent information in it and the core of the assembler most of the code is actually completely portable it has nothing in interest interesting information about the machines but there's a table that tells you what the instruction names are there's a table that tells you what the register names are and there's a few fiddly bits around how operands work but it's pretty straightforward and all this is configured when the program starts by looking at the value of go arch now goose comes in with some very very subtle corner cases that I don't wanna get into the fundamental part comes out of gorge and there's this internal package to the assembler called arch which creates these tables on the fly by extracting them from the abre dynamically and here is some real code this is slightly reduced for simplicity but the core of it is this this is the arch package inside the assembler this is the routine that sets up the entire assembler for an x86 architecture this actually handles both 32-bit and 64-bit there's they're the same and from this point of view and all we do is we loop over all of these I'm gonna do this yes that's a loop over the register names that have been coming out of the that are in the obvious library defined in the x86 package for the obscene and we just set up a map that maps from names of registers to their binary code as the object back egde knows about them and then we do the same things for the instructions and here these these codes are not actually instruction codes if you know assembly language they're not whether in the manual it's literally an alphabetically orderly noon for all of the things because remember these are really pseudo instructions they're not the real thing but now we know all the names of all the registers and all the instructions and so the architecture description we're going to return just contains these two maps here are the names of the instructions you recognize hair the names of the registers you recognize and a few other details which I've alighted but they're pretty straightforward that's all the information you need to assemble for those those machines in fact the parser just a string matching to look up what the instructions are you're in column one there's a word that's an instruction look it up in the instruction table it's really simple notice it just to go great no why am i editing this there we go I didn't know I could do that here's an example here's the add word instruction on the 386 that you might write in real code or see come out of the compiler it says add W ax comma BX the assembler knows the first column is the instruction so all it does is look inside the instruction the instructions list that's inside the architecture structure and indexes the map by edw and gets a code puts that in the the a name which is which is a weird name but that's what it is and then it's from and two are the two operands again look up the register as an ax look up the registers BX it's more complicated than this but that's the essence of it you just look up these words that you see on the input stuffed them into a data structure and pass them to the object library the point is this is just text processing the assembler is just doing text processing it doesn't know anything about the semantics of these machines really at all now the some validation has to do it has to make sure that they're lexically and synthetically correct that's easy that's just standard parsing techniques and so it also verifies things like operands do they belong there's a few tweaks in some ugly corner cases because some of the machines have weird upper end modes of the others don't but they're fairly easy to apply it's not a big deal the key point is that all the semantics checking is done by the object library and the basic rule is if if the probe structure which describes an instruction goes into the obviously Brera and there's no error it's because the obviously knows knows how to turn that into an instruction for the real machine and so if we can parse it and the obvious library likes it we're done that's the whole idea now this is obviously crazy but it works and we can test it and prove it so the way we did testing was remember we had the old assemblers still around they're written in C and so literally we took programs we wrote well I wrote the assembler with the obsolete bread behind it we put it together and we take the same program we compile it with the old we'd assemble it with the old assembler and the new one and we iterated until the new guy got exactly the same bits out that the previous one did and they went on to the next program and by the time we've done the whole standard package we had a working assembler and that was pretty much it that's kind of a B testing is just an amazingly great way to test them and it worked out really well I did the 386 first then I did the ambi 64 and each time I added a little bit more special casing but it got better by the time I got to the PowerPC it was actually just like in a couple hours work to do a new architecture for this assembler was so easy the most exciting and I think interesting part of this whole thing is that no point in the writing of this assembler that handles these four architectures that I look at a single hardware manual this is entirely a text processing problem based on the knowledge that the AUB's library knew all the stuff and I didn't have to that's kind of cool I think so the result is we now have a single Bell program that replaces many C and Yaak programs each of which was different so it's much easier to maintain it's much easier to maintain one program than many it's also much easier to fix bugs once rather than in every program that might have them because it's a go program it can be tested properly that's nice it's dependent on a library that the whole world depends on and so correctness is almost automatic which is very nice it's not that's overstating it but there's a big component there that's true and we have a new assembler that's almost exactly compatible with all the old ones the places where it's not is mostly where the previous assemblers had diverged and had slight variations in how certain things worked but we just completely unified it now we've made it a truly universal assembly language for all of them and portability is really easy I showed you I think all of the architectures that it can handle today when I went through those those examples of the add function and a large number of those were actually provided by the open source community and if you look at the git repository and look at the check-ins that added those new architectures you'll see that they're actually getting to be quite small check-ins to add all the information you need for a new machine it's actually quite lovely and I think a validation of the approach and I love that the open source community is now adding architectures so easily now as I said you configure the assembler by loading essentially tables that are known to the object library which is encoding of the machine architecture well can we generate tables I don't like writing tables by hand well not quite but listen the disassemblers which are not what I'm talking about but they are used by go-to P prof. and some other pieces that there actually were created at least I think all of them but at least some of them anyway by Russ one one board afternoon when he wrote a program that would take in the PDF of an instruction manual and turn into the bit patterns that are needed to encode instructions you have a machine readable description of the machine why not read it with a machine and so the disassemblers our machine generated and it's a little tricky to go the other direction it's not as easy and first one thing it has to be absolutely right if a disassembler is wrong it doesn't really matter that much you'd like it to be right but corner cases aren't as important for the other direction it's got to be 100 percent perfect and so it's a little much harder problem the other way but Russ is working on it and I suspect I hope we'd have it done by now but we don't but I hope by the end of the year you'll be able to give us the instruction manual PDF for a new architecture and we're able to turn the crank and give you a working assembler that's the goal so that means we have a largely machine generated assembler at least once this this handwritten part up front is done so in conclusion I think despite what people will tell you assembly language really is essentially the same everywhere and we've moved to the point in the world of portability where we should treat it that way and we can use those ideas to build a true common assembly language that lets you talk to the machine at the lowest level and yet not have to learn a new syntax and a new tool every time you want to to do that it also makes it much easier when you have a single environment like this to have the compiler interact with it the linker interact with it in a way that's nice and transparent and straightforward and you can do this by dynamically loading tables that are machine generated on the fly from a couple of environment variables which is it's a shame we need to but we do and one day maybe this year I hope we'll be creating those tables automatically from machine and so we have taken what is arguably one of the most non portable things out there which is assembly language and we've Chris constructed a portable solution to it and that's the go away thank you

Channel: Gopher Academy

Views: 61,749

Keywords: programming, software development, golang, gophercon

Id: KINIAgRpkDA

Length: 23min 56sec (1436 seconds)

Published: Thu Aug 18 2016

Reddit Comments

[u/andradei]

Craziest, most amazing feature I've heard of this year: parsing an architecture's assembler manual and making Go's compiler and linker know what to do to compile to said architecture without having to read a single line of said manual!

EDIT: Mispelling

[u/ops_man]

As a Golang noob this video really helped validate my decision to learn this language. I'm not a programmer by trade just hardcore linux user and hobbyist. So c and assembly have pretty much been my sword and dagger. If this video is indeed indicative of where go is going - couldn't help it - the language should see an explosive increase in adoption. Just my opinion.

Edit : correct autocorrect. Edit : looking forward to posting of more videos..Surely there's more than seven.

[u/genghisjahn]

The whole talk is great, but skip to 21m23s to have your mind blown.

[u/TheMerovius]

I loved this talk. One of my favorite details is how one of the inventors of unix advocates for converting binaries connected by text-pipes into libraries connected by binary data and function calls. :)

[u/mostlywaiting]

Does anyone know if it is possible to write functions using the go pseudo-asm language? Like, in math/big, there are plenty of func_$GOARCH.s files, but I was wondering if it would be possible to write one for use with all architectures (or for all architectures except for a specific subset), and bypass the first compiler stage.