0
\$\begingroup\$

I'm trying to better understand the entire process of coding, which involves translating the higher level languages (c++/java/python and so on) into binary data that tells the CPU to execute operations based upon its native instruction set.

My question would be how, exactly, do the assembler instructions get translated into a sequence of 1s and 0s . Where does the mapping of a line of code like, say

addi $s0, $s0, 1

becomes a binary sequence based upon the opcode (addi) and so on. Where is the related mapping table (for assembler language to specific instructions) stored and how is it used to instruct the ALU part of the processor to, well, perform tasks?

I'm sorry for posing a great deal of questions, but I hope I'm making myself clear by expanding the issue.

Thank you!

Edit: I was mainly not aware of the loader's role (mainly the OS, in most of the nowadays programs) in the entire "compile-assemble-link-LOAD (and I have to emphasize on the next part: IN MEMORY)" process; that's what I found hard to understand - the whole memory storing process. Now it makes a lot more sense that, after the program is stored in memory, the required operations are performed by the CPU following the instruction set layout and the program executes it's intended task(s).

\$\endgroup\$
4
  • \$\begingroup\$ youtube.com/watch?v=Mv2XQgpbTNE \$\endgroup\$
    – G36
    Aug 17 '19 at 19:52
  • \$\begingroup\$ For a different and very simplistic approach how an actual CPU and a higher level language can meet, take a look at the J1 Forth CPU. That CPU is made that way it has the Forth primitives as its assembly language. \$\endgroup\$
    – Janka
    Aug 17 '19 at 20:57
  • \$\begingroup\$ the Assembler has to validate the syntax of each line of code and ensure your instruction expectations ( such as DSZ decrement-and-skip-if-zero from Data General machines) are legit; also the constants (such as ADD 13) are of valid range and base; also the JUMP offsets must be validated, and the named-jumps { JMP new_start) proven to be legit; then the lookup tables let you spit out the binary. \$\endgroup\$ Aug 18 '19 at 2:56
  • \$\begingroup\$ Not really an answer, but I suggest watching Ben Eater's breadboard computer videos: youtube.com/… You'll understand it after that. \$\endgroup\$
    – Nyos
    Aug 18 '19 at 14:39
4
\$\begingroup\$

The actual binary machine code instruction set, and/or the sub-fields that compose the instruction set, are usually encoded in look-up tables (software arrays), or switch/case statements. After parsing the human-readable text into tokens, numerical forms of these tokens can then be used to index into the lookup tables for the binary encodings. The binary subfields, and offsets perhaps derived later, can then be "assembled" into binary machine code instructions by concatenation.

The very first assemblers were mostly women (job title "computer") who did this look-up manually. (reference: history of the Eniac and Mark I, and the history book "When Computers were Human", by Grier).

On the other end, in the CPU hardware, there's usually an instruction register (or many for parallel execution models) followed by a decoder (or several), which (perhaps pipelined in layers) converts bit-fields into control signals, often a vast number. Older computer were sometimes implemented using microcode, where another semi-hidden processor does the decoding of the visible machine code in software (hard-coded or pre-loaded vertical or horizontal microcode, 2 layers on some CPUs, such as the 68000).

\$\endgroup\$
1
\$\begingroup\$

The assembly instruction itself has several sub-fields in it, including the opcode, the sources and the destinations, and in some cases a short integer immediate value.

For working with source-based assembly like your example, you will 'assemble' it into an executable to run on your machine. The assembler utility parses your human-readable text and translates the sub-fields that form the instruction into binary, based on tables (that is, the instruction set) given for the architecture. These fields are packed - assembled - into instructions. Hence the term, assembly code.

So you have these three things: the instruction set, your source code, and the assembler that translates the two into an executable binary. You’ve loaded your binary into the hardware and launched the program. What’s next?

The Secret Life Of Assembly

Within the CPU itself, the assembly instructions are unpacked and decoded into low-level signals that select the operation and steer the data to and from the appropriate places. This process is called, unsurprisingly, instruction decode.

Instruction decoding is accomplished with the help of an even lower-level type of software and logic called microcode.

Microcode: CISC vs. RISC vs. Reward

CISC (Complex Instruction Set Computers) rely on microcode to implement very complex instructions. Microcode is an expanded version of the assembly opcode that is itself a programming language, stored in a special memory called a control store. A single CISC instruction maps onto many micro-instructions and takes multiple cycles to complete.

This is great for instruction density, but the downside is it that because it takes multiple microcode clock cycles to complete, so machine throughput is slower.

RISC (Reduced Instruction Set Computer) architectures like ARM and MIPS seek to avoid the microcode bottleneck by using direct (logic-based) instruction decoding, and execute most instructions in a single cycle. So machine throughput is higher.

The trade-off is the RISC instruction set is simpler and less dense than CISC, so some operations that would be one instruction on a CISC machine take multiple operations on a RISC. This makes their work-per-opcode lower, and increases pressure on the code store to keep the RISC pipeline fed.

RISC architectures mitigate this somewhat by relying on a large number of fast registers for storing operands, and large, fast cache memory to reduce instruction fetch latency.

In reality, RISC techniques have flowed back to CISC (notably x86) making them faster as well, but nevertheless they are still more complex than RISC. RISC machines have also become more complex, while still adhering to the same low-cycle-count simple instruction philosophy.

\$\endgroup\$
19
  • \$\begingroup\$ 'The assembler parses the human-readable form into the opcode and operands, which are assembled into machine instructions'. It's this exact bit that I have yet to fully understand. Where is the actual instruction set located? \$\endgroup\$
    – dreamer
    Aug 17 '19 at 19:36
  • \$\begingroup\$ @tudorarion Have you ever written a text parser that tokenizes strings? It's not a complex process. I've written a C compiler, optimizing back-ends for other compilers, and I've written many assemblers. When you ask, "where is the actual instruction set located?", this tells me you probably need a small lecture about the divisions between hardware implementation (particularly, the decoding portion if not more) and the software that translates text files into bits that can be handled by that hardware. Can you elaborate your question more? (I don't want to write a book.) \$\endgroup\$
    – jonk
    Aug 17 '19 at 19:47
  • \$\begingroup\$ I understand that the inquiry is a bit lax and I apologize for that. What I'm having a bit of a problem understanding is the actual software to hardware translation of the said instruction given to the CPU. I can dig deeper into researching bit by bit the answer given by @hotpaw2 as it seems to cover my question pretty well. Also, now I'm going through " Computer Organization and Design " by David A. Patterson and John L. Hennessy . Have you got any other reputable references similar to this one? (or any good resource for learning the basics of CS) Thanks a lot! \$\endgroup\$
    – dreamer
    Aug 17 '19 at 19:57
  • \$\begingroup\$ The Hennessy and Patterson books are currently one of the (if not the) authoritative sources on this technology. There's another good textbook that Patterson used in teaching his courses (before writing his own text). Can't remember the title, will have to hunt for it in storage. \$\endgroup\$
    – hotpaw2
    Aug 17 '19 at 20:02
  • \$\begingroup\$ @tudorarion (I've met and worked with Dr. Hennessy.) That book is pretty good and it targets software types more than hardware types. So that would seem to be perfect, to me. (Their "Computer Architecture: A Quantitative Approach" is more for hardware types.) There is another book I really like if you want to seriously dig into designing an MCU, which is "Microprocessor Design Using Verilog HDL" by Dalrymple. There, you lay out your entire instruction map (excel tables, almost) and work out an approach that includes bus design and other details. \$\endgroup\$
    – jonk
    Aug 17 '19 at 20:04
0
\$\begingroup\$

assembling the assembly language into machine code is one step completely independent of execution of machine code.

If you look at the documentation for the specific instruction set, for mips and arm and other IP vendors you go to them if the processor vendor also makes the chips like intel x86 you go there. Below I have a couple of instructions from the arm thumb instruction set,

add rd,rn,rm
and rd,rm

where d,n,m are 0-7 (registers r0 through r7).

VERY VERY brute force and crude but functional:

assuming a line from a file is in a string (C code) read from the file

char newline[256];
...
unsigned int gpr ( unsigned int ra, unsigned int *reg )
{
    if(newline[ra]!='r')
    {
        printf("syntax error\n");
        return(1);
    }
    ra++;
    if((newline[ra]<0x30)||(newline[ra]>0x37))
    {
        printf("syntax error\n");
        return(1);
    }
    *reg=newline[ra]&7;
    return(0);
}
...
        if(strncmp(newline,"add ",4)==0)
        {
            ra=4;
            if(gpr(ra,&rd)) continue;
            ra+=2;
            if(newline[ra]!=',')
            {
                printf("syntax error\n");
                continue;
            }
            ra++;
            if(gpr(ra,&rn)) continue;
            ra+=2;
            if(newline[ra]!=',')
            {
                printf("syntax error\n");
                continue;
            }
            ra++;
            if(gpr(ra,&rm)) continue;
            inst=0x1800|(rm<<6)|(rn<<3)|rd;
            printf("0x%04X add r%u,r%u,r%u\n",inst,rd,rn,rm);
        }
        if(strncmp(newline,"and ",4)==0)
        {
            ra=4;
            if(gpr(ra,&rd)) continue;
            ra+=2;
            if(newline[ra]!=',')
            {
                printf("syntax error\n");
                continue;
            }
            ra++;
            if(gpr(ra,&rm)) continue;
            inst=0x4000|(rm<<3)|rd;
            printf("0x%04X and r%u,r%u\n",inst,rd,rm);
        }

VERY inflexible too, many (not all) assemblers will allow for white space.

So if I feed this simple assembler this code

add r1,r2,r3
add r1,r2,r4
add r2,r0,r0
add r3,r0,r0
add r0,r1,r0
add r0,r0,r7
and r1,r2
add r9,r1,r3

and run it I get

0x18D1 add r1,r2,r3
0x1911 add r1,r2,r4
0x1802 add r2,r0,r0
0x1803 add r3,r0,r0
0x1808 add r0,r1,r0
0x19C0 add r0,r0,r7
0x4011 and r1,r2
syntax error

The toolchain (compiler, assembler, linker) to be useful has a file format or set of file formats used for the source code languages plus some intermediate formats so an object file format and a final binary file format and some way to communicate the linker specs, what address space has read/write memory, maybe where if any read only (rom/flash) address space. Where computer science/convention concepts .text, .data, .bss ... are located (.text being the machine code and related binary information, .data being initialized read/write memory, think variables. and .bss being zeroed read/write memory, also think variables.

The file formats used are not relevant to the processor and how it works what the processor requires is that there is logic that can feed it instructions and data on some bus which is also not relevant, but part of the processor IMPLEMENTATION. MIPS as you have noted is used by the textbooks you mentioned to make textbook/academic style processors. Every Nth computer engineering degree major will make a mips processor in college, usually in verilog or vhdl, so there are hundreds of thousands if not another order of magnitude or two number of mips implementations out there. Most using wishbone (google it) but is again not relevant to making a mips processor.

I chose a couple of very simple ARM thumb instructions, IP that you buy from ARM and put in your chip. ARM itself has many cores and every generation is a new implementation, but somewhere in that logic a fetch happens and there is an instruction latched in the logic and some logic that in some form (pseudo code shown here)

inst_add = 0;
inst_and = 0;
rd = inst[2:0];

if(inst[15:9] == 7`b0001100)
{
   inst_add = 1;
   rn = inst[5:3];
   rm = inst[8:6];
}

if(inst[15:6] == 10`b0100000000)
{
   inst_and = 1;
   rm = inst[5:3]
}

and then somewhere else the add and and implementations with flags and all that.

There is no magic to it. If you can count from 0 to 1 and understand AND, OR, NOT then you understand logic that is used to make processors, they are no more complicated than that.

You can certainly try to use discreet logic elements and draw them on paper or use schematic capture if that is still a thing or you can use an HDL, hardware design language like VHDL or Verilog (or others, yes there are others, that usually compile into VHDL or Verilog, some tools are only VHDL and Verilog is compiled into VHDL first to be used by that tool).

You can just as easily make an instruction set simulator that you can program in some programming language of your choice.

    //AND
    if((inst&0xFFC0)==0x4000)
    {
        rd=(inst>>0)&0x7;
        rm=(inst>>3)&0x7;
if(DISS) fprintf(stderr,"ands r%u,r%u\n",rd,rm);
        ra=read_register(rd);
        rb=read_register(rm);
        rc=ra&rb;
        write_register(rd,rc);
        do_nflag(rc);
        do_zflag(rc);
        return(0);
    }

Back to assemblers or language parsing in general. For various reasons a very common way to solve the problem is using bison/flex which are derived from older tools (lex,yacc)(there are other derivatives no doubt). At the end of the day the parser is this massive state machine generated by the tool For my two instruction assembler it would go character by character in the line if the first character is not an 'a' then syntax error. Then it would look at the second character and compare with n or d if neither syntax error otherwise if n then the third must be a d, the fourth a space and then into the register parsing. if the second is a d then the third a d, the fourth a space and so on. So if/when you go down this path of googling bison/flex and following a tutorial examine the c or c++ output of one of the tools and see this state machine.

There is no rule/requirement that you have to use these or any other already made parsing tools or tools that generate parsers (code that generates code like the lexx/yacc, flex/bison solutions). You can certainly come up with the parser on your own as I have done above.

while very possible to write machine code, by hand on paper or in a text editor, getting that information into a format that will then be usable by one of these tools is often not worth it, depends on the tool. gnu assembler will accept

.hword 0x1801

and you could write machine code like that if you prefer. that is still assembly language being parsed by some parser and so on...

ultimately the processor and surrounding chip and memory infrastructure, the system needs to support the processors rules for booting and such, be able to feed the processor vectors and instructions and data to make it work. Somewhere in ram or rom that 0x1801 instruction lives it is then fed into the processor as the next instruction the processor picks apart the fixed portions in this case the upper 7 bits, and from that knows to parse the operand and result registers from the rest of the instruction. MIPS as you will see is not much different there is a first place you look in a mips instruction then depending on what you find there there is a secondary opcode field, and then from there the operands.

You can go to places like opencores and find a good mips or an old arm 2/3 or some others, remember you get what you pay for, there are a couple-few of good processors there, others are well...risc-v is becoming a fad for now, will see how that goes. There are some cores out there too, gnu has tools for arm, risc-v, mips and many others. as well as there being other toolchains. you can see working implementations of a processor in an HDL. some are easy to sim with verilator or icarus or ghdl or other. and from there you can use gtkwave or some other tool to see the processor in action.

Understand that the textbooks you are reading are just textbooks. An introduction to the terms, decode, execute, etc. No reason whatsoever to assume that processors buried in chips you can buy today only have a handful of pipeline steps. You can have fewer or more or no pipeline at all. The same steps have to happen fetch, decode, etc. And again if you take 100 engineers and give them an ISA and ask them to implement it you will get somewhere between 1 and 100 different implementations, assuming all are functional. More likely to be closer to the 100 than 1.

Same goes for compilers and assemblers give 100 fully capable folks a language specification and you will get somewhere between 1 and 100 different implementations that will do the job. The task is the output how you get there can vary.

Commenting on one of the other answers. Some (CISC) processors are still microcoded, it makes sense to microcode a CISC, kinda the reason RISC exists was to not be microcoded. But if you go way back and say look at visual6502, these processors were made by hand. Some folks a very well known man in particular, but anyway would draw on paper each layer of the chip and essentially hand make/draw each transistor and the metal layers that connected them. For financial and sanity reasons it made sense that we started with CISC in that era, you make a ROM based state machine, each high level CISC instruction essentially addresses into the rom and then the rom defines the sub instructions or microcode to actually implement the high level instruction. And these are not necessarily "instructions" they could be based on implementation be a bunch of discretes or mux inputs that route data to from memory busses or alus or the register file, etc. so you needed to implement the logic in a way that you could drive it from this rom, and then after you built it if there were problems you had a chance to solve it by changing the contents of the rom and not have to spin the chip at great expense esp since it was all hand drawn. It is still true today that the bulk of the cost is the layout and generating the masks essentially. Just like pcb design it is not all automated, part manual part automated.

If you are still in school there are resources where you can use I forget the term micro foundries, some colleges have equipment to make small runs of chips at a reasonable cost and/or if you take the right class at the right school is included. But you wont get the actual chip for many months just like the real world. I have not tried one of these but would like to. Am much closer to the end of my career than the college days, but some of these resources are available to the general public as well. Cheaper than spending the several to tens of millions to use a commercial fab for hire place.

short answer. The actual implementation of a compiler, assembler, linker are at the whim of the author(s) of the tools. Generally you want to have an assembler and it comes first usually as it is used to test the processor. There are sanity and other reasons why you would want your compiler to compile into assembly and not machine code, but there are exceptions to that and some that go straight to machine code which means bytes in a file format that the linker can then read and polish. And then the linker that takes objects. you dont have to have all of these there were and probably still are assemblers that output ready to run machine code already linked if you will. Then you have to get the bytes from the "binary" into rom/ram such that the processor can be fed those ones and zeros. If you look at the computer you are reading this on, there are many layers of abstraction going on. The operating system loads a binary in a file format it has defined/dictated. It probably puts it in a virtual memory space which is sanity for the programmer. All programs run from address 0x1000 in ram for example. But in reality there is a physical address buried behind that that the processor doesnt see but the memory system does. The operating system causes the processor to be in a mode where it can execute your program for a while then some other program for a while and round and round. If you get a microcontroller and program it bare metal (doesnt mean assembly language just means no operating system) or better an emulator/simulator, you can see more of these mechanics first hand.

you can create your own or start with the lc-3 instruction set definition and create your own simulator and by hand generate the machine code and feed it into that simulator. then make an assembler in whatever your favorite langauge is and so on. there is no magic to this (ignore the text books and classes, they have a microcoded implementation for the sake of microcoding, it is massive overkill, you can implement the whole lc-3 instruction set in a few dozen lines of verilog likewise in C)

Languages like java and python run on virtual machines, can be compiled down to native machine code but java in particular was not designed for that. In some other language you create the JVM a virtual machine that executes the JAVA instruction set which is what it really is. And the JAVA compiler compiles to this binary code. The virtual machine is essentially a simulator it reads the byte sees its a particular instruction task and then you implement that task in whatever language you are using to make the virtual machine. and compile/assemble that for the native processor/system you want the jvm to run on. So C++ and JAVA dont exactly take the same path to execution on the same computer, same operating system. C, C++ and other compiled languages will end up in machine code for that target processor/system.

\$\endgroup\$
2
  • \$\begingroup\$ I kindly appreciate the thorough reply. I'm 2 years after finishing college (not in CS, that's why I started to study it independently) and I managed to get a job as a programmer at a gaming company and it surprises me how well the abstraction layer part of programming does it's job (as intended). I mean.. I can fully design and publish a C++ application without having the need to know (at a low/hardware level) how the PC interprets the high level language instructions I create. This is, I repeat, a good thing, but, on the other hand, I want to be able to explain myself the entire process. \$\endgroup\$
    – dreamer
    Aug 18 '19 at 16:19
  • \$\begingroup\$ I also won't be tasked with any part of this process but, like I said, it's good to have an idea about what goes under the hood, so to speak. I'll go through the answers provided both here as well as in the Apendix A of 'Computer Organization and Design' and make it all clear. Thank you very much and best regards! \$\endgroup\$
    – dreamer
    Aug 18 '19 at 16:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.