(THEMO~1.PDF

174 Chapter 2 Instructions: Language of the Computer FIGURE 2.48 RISC-V instruction classes, examples, correspondence to high-level program language constructs, and percentage of RISC-V instructions executed by category for the average integer and floating point S...

174 Chapter 2 Instructions: Language of the Computer FIGURE 2.48 RISC-V instruction classes, examples, correspondence to high-level program language constructs, and percentage of RISC-V instructions executed by category for the average integer and floating point SPEC CPU2006 benchmarks. Figure 3.24 in Chapter 3 shows average percentage of the individual RISC-V instructions executed. Each category of RISC-V instructions is associated with constructs that appear in programming languages: n Arithmetic instructions correspond to the operations found in assignment statements. n Transfer instructions are most likely to occur when dealing with data structures like arrays or structures. n Conditional branches are used in if statements and in loops. n Unconditional branches are used in procedure calls and returns and for case/ switch statements. These instructions are not born equal; the popularity of the few dominates the many. For example, Figure 2.48 shows the popularity of each class of instructions for SPEC CPU2006. The varying popularity of instructions plays an important role in the chapters about datapath, control, and pipelining. After we explain computer arithmetic in Chapter 3, we reveal more of the RISC-V instruction set architecture. Historical Perspective and Further 2.24 Reading This section surveys the history of instruction set architectures (ISAs) over time, and we give a short history of programming languages and compilers. ISAs include accumulator architectures, general-purpose register architectures, stack architectures, and a brief history of the x86 and ARM’s 32-bit architecture,  2.24 Historical Perspective and Further Reading 174.e1 2.24 Historical Perspective and Further Reading This section surveys the history of instruction set architectures over time, and we give a short history of programming languages and compilers. ISAs include accumulator architectures, general-purpose register architectures, stack architectures, and a brief history of ARMv7 and the x86. We also review the controversial subjects of high-level-language computer architectures and reduced instruction set computer architectures. The history of programming languages includes Fortran, Lisp, Algol, C, Cobol, Pascal, Simula, Smalltalk, C++, and Java, and the history of compilers includes the key milestones and the pioneers who achieved them. Accumulator Architectures Hardware was precious in the earliest stored-program computers. Consequently, computer pioneers could not afford the number of registers found in today’s architectures. In fact, these architectures had a single register for arithmetic instructions. Since all operations would accumulate in one register, it was called the accumulator, and this style of instruction set is given the same name. For example, accumulator Archaic EDSAC in 1949 had a single accumulator. term for register. On-line The three-operand format of RISC-V suggests that a single register is at least two use of it as a synonym for “register” is a fairly reliable registers shy of our needs. Having the accumulator as both a source operand and indication that the user the destination of the operation fills part of the shortfall, but it still leaves us one has been around quite a operand short. That final operand is found in memory. Accumulator architectures while. have the memory-based operand-addressing mode suggested earlier. It follows that the add instruction of an accumulator instruction set would look like this: Eric Raymond, The New Hacker’s Dictionary, 1991 ADD   200 This instruction means add the accumulator to the word in memory at address 200 and place the sum back into the accumulator. No registers are specified because the accumulator is known to be both a source and a destination of the operation. The next step in the evolution of instruction sets was the addition of registers dedicated to specific operations. Hence, registers might be included to act as indices for array references in data transfer instructions, to act as separate accumulators for multiply or divide instructions, and to serve as the top-of-stack pointer. Perhaps the best-known example of this style of instruction set is found in the Intel 80x86. This style of instruction set is labeled extended accumulator, dedicated register, or special-purpose register. Like the single-register accumulator architectures, one operand may be in memory for arithmetic instructions. Like the RISC-V architecture, however, there are also instructions where all the operands are registers. 174.e2 2.24 Historical Perspective and Further Reading General-Purpose Register Architectures The generalization of the dedicated-register architecture allows all the registers to be used for any purpose, hence the name general-purpose register. RISC-V is an example of a general-purpose register architecture. This style of instruction set may be further divided into those that allow one operand to be in memory (as found in accumulator architectures), called a register-memory architecture, and load-store those that demand that operands always be in registers, called either a load-store architecture Also or a register-register architecture. Figure e2.24.1 shows a history of the number of called register- registers in some popular computers. register architecture. The first load-store architecture was the CDC 6600 in 1963, considered by many An instruction set architecture in which to be the first supercomputer. RISC-V, ARMv7, ARMv8, and MIPS are more recent all operations are examples of a load-store architecture. between registers and data memory may only be accessed via loads or Number of stores. Machine general-purpose registers Architectural style Year EDSAC 1 Accumulator 1949 IBM 701 1 Accumulator 1953 CDC 6600 8 Load-store 1963 IBM 360 16 Register-memory 1964 DEC PDP-8 1 Accumulator 1965 DEC PDP-11 8 Register-memory 1970 Intel 8008 1 Accumulator 1972 Motorola 6800 2 Accumulator 1974 DEC VAX 16 Register-memory, memory-memory 1977 Intel 8086 1 Extended accumulator 1978 Motorola 68000 16 Register-memory 1980 Intel 80386 8 Register-memory 1985 ARM 16 Load-store 1985 MIPS 32 Load-store 1985 HP PA-RISC 32 Load-store 1986 SPARC 32 Load-store 1987 PowerPC 32 Load-store 1992 DEC Alpha 32 Load-store 1992 HP/Intel IA-64 128 Load-store 2001 AMD64 (EMT64) 16 Register-memory 2003 RISC-V 32 Load-store 2010 RISC-V 16 Regular-memory 2010 FIGURE e2.24.1 The number of general-purpose registers in popular architectures over the years. The 80386 was Intel’s attempt to transform the 8086 into a general-purpose register-memory instruction set. Perhaps the best-known register-memory instruction set is the IBM 360 architecture, first announced in 1964. This  2.24 Historical Perspective and Further Reading 174.e3 instruction set is still at the core of IBM’s mainframe computers—still responsible for $10 billion per year in annual sales. Register-memory architectures were the most popular in the 1960s and the first half of the 1970s. Digital Equipment Corporation’s VAX architecture took memory operands one step further in 1977. It allowed an instruction to use any combination of registers and memory operands. A style of architecture in which all operands can be in memory is called memory-memory. (In truth the VAX instruction set, like almost all other instruction sets since the IBM 360, is a hybrid, since it also has general- purpose registers.) The Intel x86 has many versions of a 64-bit add to specify whether an operand is in memory or is in a register. In addition, the memory operand can be accessed with more than seven addressing modes. This combination of address modes and register-memory operands means that there are dozens of variants of an x86 add instruction. Clearly, this variability makes x86 implementations more challenging. Compact Code and Stack Architectures When memory is scarce, it is also important to keep programs small, so architectures like the Intel x86, IBM 360, and VAX had variable-length instructions, both to match the varying operand specifications and to minimize code size. Intel x86 instructions are from 1 to 15 bytes long; IBM 360 instructions are 2, 4, or 6 bytes long; and VAX instruction lengths are anywhere from 1 to 54 bytes. One place where code size is still important is embedded applications. In recognition of this need, ARM, MIPS, and RISC-V all made versions of their instructions sets that offer both 16-bit instruction formats and 32-bit instruction formats: Thumb and Thumb-2 for ARM, MIPS-16, and RISC-V Compressed. Despite being limited to just two sizes, Thumb, Thumb-2, MIPS- 16, and RISC-V Compressed programs are about 25% to 30% smaller, which makes their code sizes smaller than those of the 80x86. Smaller code sizes have the added benefit of improving instruction cache hit rates (see Chapter 5). In the 1960s, a few companies followed a radical approach to instruction sets. In the belief that it was too hard for compilers to utilize registers effectively, these companies abandoned registers altogether! Instruction sets were based on a stack model of execution, like that found in the older Hewlett-Packard handheld calculators. Operands are pushed on the stack from memory or popped off the stack into memory. Operations take their operands from the stack and then place the result back onto the stack. In addition to simplifying compilers by eliminating register allocation, stack architectures lent themselves to compact instruction encoding, thereby removing memory size as an excuse not to program in high- level languages. Memory space was perceived to be precious again for Java, both because memory space is limited to keep costs low in embedded applications and because programs may be downloaded over the Internet or phone lines as Java applets, and smaller programs take less time to transmit. Hence, compact instruction encoding was desirable for Java bytecodes. 174.e4 2.24 Historical Perspective and Further Reading High-Level-Language Computer Architectures In the 1960s, systems software was rarely written in high-level languages. For example, virtually every commercial operating system before UNIX was programmed in assembly language, and more recently even OS/2 was originally programmed at that same low level. Some people blamed the code density of the instruction sets, rather than the programming languages and the compiler technology. Hence, an architecture design philosophy called high-level-language computer architecture was advocated, with the goal of making the hardware more like the programming languages. More efficient programming languages and compilers, plus expanding memory, doomed this movement to a historical footnote. The Burroughs B5000 was the commercial fountainhead of this philosophy, but today there is no significant commercial descendant of this 1960s radical. Reduced Instruction Set Computer Architectures This language-oriented design philosophy was replaced in the 1980s by RISC (reduced instruction set computer). Improvements in programming languages, compiler technology, and memory cost meant that less programming was being done at the assembly level, so instruction sets could be measured by how well compilers used them, in contrast to how skillfully assembly language programmers used them. Virtually all new instruction sets since 1982 have followed this RISC philosophy of fixed instruction lengths, load-store instruction sets, limited addressing modes, and limited operations. ARMv7, ARMv8, ARC, Hitachi SH, IBM PowerPC, MIPS, and, of course, RISC-V, are all examples of RISC architectures. A Brief History of the ARMv7 ARM started as the processor for the Acorn computer, hence its original name of Acorn RISC Machine. The Berkeley RISC papers influenced its architecture. One of the most important early applications was emulation of the AM 6502, a 16-bit microprocessor. This emulation was to provide most of the software for the Acorn computer. As the 6502 had a variable-length instruction set that was a multiple of bytes, 6502 emulation helps explain the emphasis on shifting and masking in the ARMv7 instruction set. Its popularity as a low-power embedded computer began with its selection as the processor for the ill-fated Apple Newton personal digital assistant. Although the Newton was not as popular as Apple hoped, Apple’s blessing gave visibility to the earlier ARM instruction sets, and they subsequently caught on in several markets, including cell phones. Unlike the Newton experience, the extraordinary success of cell phones explains why 100 billion ARM processors were shipped between 1999 and 2016. One of the major events in ARM’s history is the 64-bit address extension called version 8. ARM took the opportunity to redesign the instruction set to make it look much more like MIPS than like earlier ARM versions.  2.24 Historical Perspective and Further Reading 174.e5 A Brief History of the x86 The ancestors of the x86 were the first microprocessors, produced starting in 1972. The Intel 4004 and 8008 were extremely simple 4-bit and 8-bit accumulator-style architectures. Morse et al. describe the evolution of the 8086 from the 8080 in the late 1970s as an attempt to provide a 16-bit architecture with better throughput. At that time, almost all programming for microprocessors was done in assembly language—both memory and compilers were in short supply. Intel wanted to keep its base of 8080 users, so the 8086 was designed to be “compatible” with the 8080. The 8086 was never object-code compatible with the 8080, but the architectures were close enough that translation of assembly language programs could be done automatically. In early 1980, IBM selected a version of the 8086 with an 8-bit external bus, called the 8088, for use in the IBM PC. They chose the 8-bit version to reduce the cost of the architecture. This choice, together with the tremendous success of the IBM PC, has made the 8086 architecture ubiquitous in the PC era. The success of the IBM PC was due in part because IBM opened the architecture of the PC and enabled the PC-clone industry to flourish. As discussed in Section 2.18, the 80286, 80386, 80486, Pentium, Pentium Pro, Pentium II, Pentium III, Pentium 4, and AMD64 have extended the architecture and provided a series of performance enhancements. Although the 68000 was chosen for the Macintosh, the Mac was never as pervasive as the PC, partly because Apple did not allow Mac clones based on the 68000, and the 68000 did not acquire the same software following that which the 8086 enjoys. The Motorola 68000 may have been more significant technically than the 8086, but the impact of IBM’s selection and open architecture strategy dominated the technical advantages of the 68000 in the market. Some argue that the inelegance of the x86 instruction set is unavoidable, the price that must be paid for rampant success by any architecture. We reject that notion. Obviously, no successful architecture can jettison features that were added in previous implementations, and over time, some features may be seen as undesirable. The awkwardness of the x86 begins at its core with the 8086 instruction set and was exacerbated by the architecturally inconsistent expansions found in the 8087, 80286, 80386, MMX, SSE, SSE2, SSE3, SSE4, AMD64 (EM64T), and AVX. A counterexample is the IBM 360/370 architecture, which is much older than the x86. It dominated the mainframe market just as the x86 dominated the PC market. Due undoubtedly to a better base and more compatible enhancements, this instruction set makes much more sense than the x86 55 years after its first implementation. Extending the x86 to 64-bit addressing means the architecture may last for several more decades. Instruction set anthropologists of the future will peel off layer after layer from such architectures until they uncover artifacts from the first microprocessor. Given such a find, how will they judge today’s computer architecture? 174.e6 2.24 Historical Perspective and Further Reading A Brief History of Programming Languages In 1954, John Backus led a team at IBM to create a more natural notation for scientific programming. The goal of Fortran, for “FORmula TRANslator,” was to reduce the time to develop programs. Fortran included many ideas found in programming languages today, including assignment statements, expressions, typed variables, loops, and arrays. The development of the language and the compiler went hand in hand. This language became a standard that has evolved over time to improve programmer productivity and program portability. The evolutionary steps are Fortran I, II, IV, 77, 90, 95, 2003, 2008, and 2018. Fortran was developed for IBM’s second commercial computer, the 704, which was also the cradle of another important programming language: Lisp. John McCarthy invented the “LISt Processing” language in 1958. Its mantra is that programming can be considered as manipulating lists, so the language contains operations to follow links and to compose new lists from old ones. This list notation is used for the code as well as the data, so modifying or composing Lisp programs is common. The big contribution was dynamic data structures and, hence, pointers. Given that its inventor was a pioneer in artificial intelligence, Lisp became popular in the AI community. Lisp has no type declarations, and Lisp traditionally reclaims storage automatically via built-in garbage collection. Lisp was originally interpreted, although compilers were later developed for it. Fortran inspired the international community to invent a programming language that was more natural to express algorithms than Fortran, with less emphasis on coding. This language became Algol, for “ALGOrithmic Language.” Like Fortran, it included type declarations, but it added recursive procedure calls, nested if-then-else statements, while loops, begin-end statements to structure code, and call-by-name. Algol-60 became the classic language for academics to teach programming in the 1960s. Although engineers, AI researchers, and computer scientists had their own programming languages, the same could not be said for business data processing. Cobol, for “COmmon Business-Oriented Language,” was developed as a standard for this purpose contemporary with Algol-60. Cobol was created to be easy to read, so it follows English vocabulary and punctuation. It added records to programming languages, and separated description of data from description of code. Niklaus Wirth was a member of the Algol-68 committee, which was supposed to update Algol-60. He was bothered by the complexity of the result, and so he wrote a minority report to show that a programming language could combine the algorithmic power of Algol-60 with the record structure from Cobol and be simple to understand, easy to implement, yet still powerful. This minority report became Pascal. It was first implemented with an interpreter and a set of Pascal bytecodes. The ease of implementation led to its being widely deployed, much more than Algol-68, and it soon replaced Algol-60 as the most popular language for academics to teach programming. In the same period, Dennis Ritchie invented the C programming language to use in building UNIX. Its inventors say it is not a “very high level” programming language or a big one, and it is not aimed at a particular application. Given its birthplace, it was  2.24 Historical Perspective and Further Reading 174.e7 very good at systems programming, and the UNIX operating system and C compiler were written in C. UNIX’s popularity helped spur C’s popularity. The concept of object orientation is first captured in Simula-67, a simulation language successor to Algol-60. Invented by Ole-Johan Dahl and Kristen Nygaard at the University of Oslo in 1967, it introduced objects, classes, and inheritance. Object orientation proved to be a powerful idea. It led Alan Kay and others at Xerox Palo Alto Research Center to invent Smalltalk in the 1970s. Smalltalk-80 married the typeless variables and garbage collection from Lisp and the object orientation of Simula-67. It relied on interpretation that was defined by a Smalltalk virtual machine with a Smalltalk bytecode instruction set. Kay and his colleagues argued that processors were getting faster, and that we must eventually be willing to sacrifice some performance to improve program development. Another example was CLU, which demonstrated that an object-oriented language could be defined that allowed compile-time type checking. Simula-67 also inspired Bjarne Stroustrup of Bell Labs to develop an object-oriented version of C called C++ in the 1980s. C++ became widely used in industry. Dissatisfied with C++, a group at Sun led by James Gosling invented Oak in the early 1990s. It was invented as an object-oriented C dialect for embedded devices as part of a major Sun project. To make it portable, it was interpreted and had its own virtual machine and bytecode instruction set. Since it was a new language, it had a more elegant object-oriented design than C++ and was much easier to learn and compile than Smalltalk-80. Since Sun’s embedded project failed, we might never have heard of it had someone not made the connection between Oak and programmable browsers for the World Wide Web. It was rechristened Java, and in 1995, Netscape announced that it would be shipping with its browser. It soon became extraordinarily popular. Java had the rare distinction of becoming the standard language for new business-data-processing applications and the favored language for academics to teach programming. Java and languages like it encourage reuse of code, and hence programmers make heavy use of libraries, whereas in the past they were more likely to write everything from scratch. Several people in this history section won ACM A. M. Turing Awards, at least in part for their contributions to programming languages: John Backus (1977), John McCarthy (1971), Niklaus Wirth (1984), Dennis Ritchie (1983), Ole-Johan Dahl and Kristen Nygaard (2001), and Alan Key (2003). A Brief History of Compilers Backus and his group were very concerned that Fortran would be unsuccessful if skeptics found examples where the Fortran version ran at half the speed of the equivalent assembly language program. Their success with one of the first compilers created a beachhead that many others followed. Early compilers were ad hoc programs that performed the steps described in Section 2.15 online. These ad hoc approaches were replaced with a solid theoretical foundation for each of these steps. Each time the theory was established, a tool was built based on that theory that automated the creation of that step. 174.e8 2.24 Historical Perspective and Further Reading The theoretical roots underlying scanning and parsing derive from automata theory, and the relationship between languages and automata was known early. The scanning task corresponds to recognition of a language accepted by a finite- state automata, and parsing corresponds to recognition of a language by a push- down automata (basically an automata with a stack). Languages are described by grammars, which are a set of rules that tell how any legal program can be generated. The scanning pass of a compiler was well understood early, but parsing is harder. The earliest parsers use precedence techniques, which derived from the structure of arithmetic statements, and were then generalized. The great breakthrough in modern parsing was made by Donald Knuth in the invention of LR-parsing, which codified the two key steps in the parsing technique, pushing a token on the stack or reducing a set of tokens on the stack using a grammar rule. The strong theory formulation for scanning and parsing led to the development of automated tools for compiler constructions, such as lex and yacc, the tools developed as part of UNIX. Optimizations occurred in many compilers, and it is harder to determine the first examples in most cases. However, Victor Vyssotsky did the first papers on data flow analysis in 1963, and William McKeeman is generally credited with the first peephole optimizer in 1965. The group at IBM, including John Cocke and Fran Allan, developed many of the early optimization concepts, as well as defining and extending the concepts of flow analysis. Important contributions were also made by Al Aho and Jeff Ullman. One of the biggest challenges for optimization was register allocation. It was so difficult that some architects used stack architectures just to avoid the problem. The breakthrough came when researchers working on compilers for the 801, an early RISC architecture, recognized that coloring a graph with a minimum number of colors was equivalent to allocating a fixed number of registers to the unlimited number of virtual registers used in intermediate forms. Compilers also played an important role in the open-source movement. Richard Stallman’s self-appointed mission was to make a public domain version of UNIX. He built the GNU C Compiler (gcc) as an open-source compiler in 1987. It soon was ported to many architectures, and is used in many systems today. Further Reading Bayko, J.. “Great microprocessors of the past and present,” search for it on the http://www.cpushack. com/CPU/cpu.html. A personal view of the history of both representative and unusual microprocessors, from the Intel 4004 to the Patriot Scientific ShBoom! Kane, G. and J. Heinrich. MIPS RISC Architecture, Prentice Hall, Englewood Cliffs, NJ. This book describes the MIPS architecture in greater detail than Appendix A. Levy, H. and R. Eckhouse. Computer Programming and Architecture, The VAX, Digital Press, Boston. This book concentrates on the VAX, but also includes descriptions of the Intel 8086, IBM 360, and CDC 6600.  2.24 Historical Perspective and Further Reading 174.e9 Morse, S., B. Ravenal, S. Mazor, and W. Pohlman. “Intel microprocessors—8080 to 8086”, Computer 13 10 (October). The architecture history of the Intel from the 4004 to the 8086, according to the people who participated in the designs. Wakerly, J.. Microcomputer Architecture and Programming, Wiley, New York. The Motorola 6800 is the main focus of the book, but it covers the Intel 8086, Motorola 6809, TI 9900, and Zilog Z8000.  2.25 Self-Study 175 ARMv7. We also review the controversial subjects of high-level-language computer architectures and reduced instruction set computer architectures. The history of programming languages includes Fortran, Lisp, Algol, C, Cobol, Pascal, Simula, Smalltalk, C++, and Java, and the history of compilers includes the key milestones and the pioneers who achieved them. The rest of Section 2.24 is found online. 2.25 Self-Study Instructions as Numbers. Given this binary number: 00000001010010110010100000100011two What is it in hexadecimal format? Assuming it is an unsigned number, what is it in decimal? Does the value change if it is considered a signed number? What assembly language program does it represent? Instructions as numbers and Insecurity. Although programs are just numbers in memory, Chapter 5 shows how to tell the computer how to protect the program from being modified by labelling a portion of the address space as read-only. Clever attackers exploit bugs in C programs to nevertheless insert their own code during program execution despite the program being protected. Here is a simple string copy program that copies what the user types into a local variable on the stack. #include void copyinput (char *input) { char copy; strcpy(copy, input); // no bounds checking in strcpy } int main (int argc, char **argv) { copyinput(argv); return 0; } What happens if the user writes much more than 10 characters as input? What could be the consequence to program execution? How could this let an attacker take over program execution?