Unit 3 Flashcards
The vocabulary of commands understood by a given architecture
Instruction set
The idea that instructions and data of many types can be stored in memory as numbers and thus be easy to change, leading to the stored-program computer.
Stored-program concept
The sum of b and c is placed in a
ADD a, b, c
Similarly to the add instruction, blank computes b - c and puts the result in a
SUB a, b, c
C, or Java, or Legv8 - requires most lines of source code
Legv8
C, or Java, or Legv8 - requires 2nd most lines of source code
C
C, or Java, or Legv8 - requires least lines of source code
Java
LEGv8 operands how many fast data registers
32 registers X0…X30, XZR
LEGv8 operands how many memory doublewords
262 memory doublewords Memory[0], Memory [4], …, Memory[4,611,686,018,427,387,904]
assembly language for X1 = X2 + X3
ADD X1, X2, X3
assembly language X1 = X2 - X3
SUB X1, X2, X3
assembly language X1 = X2 + 20
ADDI X1, X2, 20
assembly language X1 = X2 - 20
SUBI X1, X2, 20
assembly language X1 = Memory[X2 + 40]
LDUR X1, [X2, 40]
assembly language Memory[X2 + 40] = X1
STUR X1, [X2, 40]
assembly language X1 = X2 & X3
AND X1, X2, X3
assembly language X1 = X2 | X3
ORR X1, X2, X3
assembly language X1 = X2 ^ X3
EOR X1, X2, X3
assembly language if (X1 == 0) go to PC + 4 + 100
CBZ X1, 25
assembly language if (X1 != 0) go to PC + 4 + 100
CBNZ X1, 25
assembly language if (condition true) go to PC + 4 + 100
B.cond 25
assembly language go to PC + 4 + 10000
B 2500
assembly language go to X30
BR X30
assembly language X30 = PC + 4; PC + 4 + 10000
BL 2500
A natural unit of access in a computer, usually a group of 32 bits.
Word
The size of a register in the LEGv8 architecture is blank
64 bits
Another natural unit of access in a computer, usually a group of 64 bits; corresponds to the size of a register in the LEGv8 architecture.
Doubleword
One major difference between the variables of a programming language and registers is the limited number of registers, typically blank on current computers, like LEGv8
32
A very large number of registers may blank the clock cycle time simply because it takes electronic signals longer when they must travel farther.
increase
A command that moves data between memory and registers.
Data transfer instruction
A value used to delineate the location of a specific data element within a memory array.
Address
The data transfer instruction that copies data from memory to a register is traditionally called blank.
load
The U in LDUR stands for blank as opposed to scaled immediate, which we explain in COD Section 2.19 (Fallacies and Pitfalls).
unscaled immediate
In an LDUR instruction, a blank is the starting address of an array in memory
base address
A blank is a register that holds an array’s base address
base register
A blank is a constant value added to a base address to locate a particular array element.
offset
Since LEGv8 addresses each byte, doubleword addresses are multiples of blank: there are blank bytes in a doubleword.
8
The instruction complementary to load is traditionally called blank
store
A requirement that data be aligned in memory on natural boundaries.
Alignment restriction
The process of putting less frequently used variables (or those needed later) into memory is called blank.
spilling registers
Also called binary bit. One of the two numbers in base 2, 0 or 1, that are the components of information.
Binary digit
The rightmost bit in an LEGv8 doubleword.
Least significant bit
The leftmost bit in an LEGv8 doubleword..
Most significant bit
Of a doubleword’s 64 bits, what is the leftmost bit numbered
63
What is the largest base ten number representable in 4 bits (assuming the “natural” representation)?
15
What is the largest base ten number representable in 8 bits (assuming the “natural” representation)?
255
What is the largest base ten number approximately representable by 32 bits (assuming the “natural” representation)?
4 billion
How is the largest base ten number representable by 64 bits calculated (assuming the “natural” representation)?
2^64 - 1
Hardware can be designed to add, subtract, multiply, and divide these binary bit patterns. If the number that is the proper result of such operations cannot be represented by these rightmost hardware bits, blank is said to have occurred.
overflow
A blank is a signed number representation where a single bit is used to represent the sign, and the remaining bits represent the magnitude.
sign and magnitude representation
A signed number representation where a leading 0 indicates a positive number and a leading 1 indicates a negative number. The complement of a value is obtained by complementing each bit (0 → 1 or 1 → 0), and then adding one to the result (explained further below).
Two’s complement
Signed versus unsigned applies to loads as well as to arithmetic. The function of a signed load is to copy the sign repeatedly to fill the rest of the register, known as a blank.
sign extension
A notation that represents the most negative value by 10 … 000two and the most positive value by 01 … 11two, leaving an equal number of negatives and positives but ending up with two zeros, one positive (00 … 00two) and one negative (11 … 11two). The term is also used to mean the inversion of every bit in a pattern: 0 to 1 and 1 to 0.
One’s complement
A notation that represents the most negative value by 00 … 000two and the most positive value by 11 … 11two, with 0 typically having the value 10 … 00two, thereby biasing the number such that the number plus the bias has a non-negative representation.
Biased notation
How is 0 represented in two’s complement?
All 0’s
A machine instruction is composed of blank, each field having several bits and representing some part of the instruction.
fields
A form of representation of an instruction composed of fields of binary numbers.
Instruction format
Binary representation used for communication within a computer system.
Machine language
How many total bits is a machine instruction?
32
Numbers in base 16.
Hexadecimal
The field that denotes the operation and format of an instruction.
Opcode
A blank is a register that receives the result of an operation.
destination register
ADD is an blank instruction with 5 fields: opcode, Rm, shamt, Rn and Rd.
“R-type”
ADDI and SUBI is an blank rather than “R-type” instruction.
“I-type” (I for immediate)
DUR and STUR are blank with op2 as an extension of the opcode field.
“D-type” formats
Today’s computers are built on what two key principles:
Instructions are represented as numbers.
Programs are stored in memory to be read or written, just like data.
Instructions are represented as numbers.
Programs are stored in memory to be read or written, just like data.
These principles lead to the blank
stored-program concept
blank can contain the source code for an editor program, the corresponding compiled machine code, the text that the compiled program is using, and even the compiler that generated the machine code.
memory
One consequence of instructions as numbers is that programs are often shipped as files of binary numbers. The commercial implication is that computers can inherit ready-made software provided they are compatible with an existing instruction set. Such blank often leads industry to align around a small number of instruction set architectures.
“binary compatibility”
LSL
shift left
«
LSL
LSR
shift right
> >
LSR
&
AND, ANDI
|
ORR, ORRI
~
NOT, EOR, EORI
A blank moves all the bits in a doubleword to the left or right, filling the emptied bits with 0s.
shift
Shifting left by i bits gives the same result as blank by 2^i
multiplying
A logical bit- by-bit operation with two operands that calculates a 1 only if there is a 1 in both operands.
AND
As you can see, AND can apply a bit pattern to a set of bits to force 0s where there is a 0 in the bit pattern. Such a bit pattern in conjunction with AND is traditionally called a blank, since the mask “conceals” some bits.
mask
A logical bit-by-bit operation with two operands that calculates a 1 if there is a 1 in either operand.
OR
A logical bit-by-bit operation with one operand that inverts the bits; that is, it replaces every 1 with a 0, and every 0 with a 1.
NOT
A logical bit-by-bit operation with two operands that calculates the exclusive OR of the two operands. That is, it calculates a 1 only if the values are different in the two operands.
EOR
This instruction means go to the statement labeled L1 if the value in register equals zero. The mnemonic CBZ stands for compare and branch if zero.
CBZ register, L1
It means go to the statement labeled L1 if the value in register does not equal zero. The mnemonic CBNZ stands for compare and branch if not zero. These two instructions are traditionally called conditional branches.
CBNZ register, L1
An instruction that tests a value and that allows for a subsequent transfer of control to a new address in the program based on the outcome of the test.
Conditional branch
A sequence of instructions without branches (except possibly at the end) and without branch targets or branch labels (except possibly at the beginning).
Basic block
the result that set the condition code had a 1 in the most significant bit;
negative (N)
the result that set the condition code was 0;
zero (Z)
the result that set the condition code overflowed
overflow (V)
the result that set the condition code had a carry out of the most significant bit or a borrow into the most significant bit.
carry (C)
EQ
(= or Equal)
HS
(≥ or Higher or Same).
HI
(> or Higher
LS
(≤ or Lower or Same)
LO
(< or Lower),
GE
(≥ or Greater than or Equal).
GT
(> or Greater Than)
LE
(≤ or Less than or Equal)
LT
(< or Less Than)
NE
(≠ or Not Equal)
Branch on minus
(B.MI): N=1;
Branch on plus
(B.PL): N=0;
Branch on overflow set
(B.VS): V=1;
Branch on overflow clear .
(B.VC): V=0
In LEGv8 assembly language, you simply append an blank to the end of one of these instructions if you want to set condition codes: ADDS, ADDIS, ANDS, ANDIS, SUBS, and SUBIS. The instruction name actually uses the term flag, so the proper name of ADDS is “add and set flags.
S
=
B.EQ
not equal
B.NE
<
B.LT or B.LO
<=
B.LE or B.LS
>
B.GT or B.HI
> =
B.GE or B.HS
How many bits are used to hold a condition code?
4
How is conditional branching performed in MIPS?
In MIPS, two registers are compared and the result of the comparison is stored in a third register.
Most programming languages have a blank statement that allows the programmer to select one of many alternatives depending on a single value.
case or switch
The simplest way to implement switch is via a sequence of conditional tests, turning the switch statement into a chain of blank
if-then-else statements.
Also called branch table. A table of addresses of alternative instruction sequences.
Branch address table
A stored subroutine that performs a specific task based on the parameters with which it is provided.
Procedure
eight parameter registers in which to pass parameters or return values.
X0-X7
one return address register to return to the point of origin.
LR (X30)
An instruction that branches to an address and simultaneously saves the address of the following instruction in a register (LR or X30 in LEGv8).
Branch-and-link instruction
The blank is needed because the same procedure could be called from several parts of the program.
return address
A link to the calling site that allows a procedure to return to the proper address; in LEGv8 it is stored in register LR (X30).
Return address
The program that instigates a procedure and provides the necessary parameter values.
Caller
A procedure that executes a series of stored instructions based on parameters provided by the caller and then returns control to the caller.
Callee
The register containing the address of the instruction in the program being executed.
Program counter (PC)
A data structure for spilling registers organized as a last-in- first-out queue.
Stack
A value denoting the most recently allocated address in a stack that shows where registers should be spilled or where old register values can be found. In LEGv8, it is register SP.
Stack pointer
Add element to stack.
Push
Remove element from stack.
Pop
temporary registers that are not preserved by the callee (called procedure) on a procedure call
X9 - X17
saved registers that must be preserved on a procedure call (if used, the callee saves and restores them)
X19 - X28
Procedures that do not call others are called blank.
leaf procedures
The register that is reserved to point to the static area.
Global pointer
Also called activation record. The segment of the stack containing a procedure’s saved registers and local variables.
Procedure frame
A value denoting the location of the saved registers and local variables for a given procedure.
Frame pointer
The segment of a UNIX object file that contains the machine language code for routines in the source file.
Text segment
Most computers today offer 8-bit bytes to represent characters, with the blank being the representation that nearly everyone follows.
American Standard Code for Information Interchange (ASCII)
blank loads a byte from memory, placing it in the rightmost 8 bits of a register.
Load byte (LDURB)
blank takes a byte from the rightmost 8 bits of a register and writes it to memory.
Store byte (STURB)
blank is a universal encoding of the alphabets of most human languages.
Unicode
The LEGv8 instruction set has explicit instructions to load and store such 16- bit quantities, called blank.
halfwords
blank loads a halfword from memory, placing it in the rightmost 16 bits of a register.
Load half (LDURH)
blank takes a halfword from the rightmost 16 bits of a register and writes it to memory.
Store half (STURH)
The LEGv8 instruction set includes the instruction blank and blank specifically to set any 16 bits of a constant in a register.
move wide with zeros (MOVZ)
move wide with keep (MOVK)
blank = Register + Branch offset
Program counter
An addressing regime in which the address is the sum of the program counter (PC) and a constant in the instruction.
PC-relative addressing
The operand is a constant within the instruction itself
Immediate addressing
The operand is a register
Register addressing
The operand is at the memory location whose address is the sum of a register and a constant in the instruction
Base addressing / displacement addressing
The branch address is the sum of the PC and a constant in the instruction
PC-relative addressing
One of several addressing regimes delimited by their varied use of operands and/or addresses.
Addressing mode
Two memory accesses form a blank if they are from different threads to same location, at least one is a write, and they occur one after another.
Data race
A symbolic language that can be translated into binary machine language
Assembly language
A common variation of assembly language instructions often treated as if it were an instruction in its own right.
Pseudoinstruction
A table that matches names of labels to the addresses of the memory words that instructions occupy.
Symbol table
A blank converts a high-level program, such as a C program, into an assembly language program.
compiler
An blank is used to convert an assembly language program to a machine language program.
assembler
Also called link editor. A systems program that combines independently assembled machine language programs and resolves all undefined labels into an executable file
Linker:
There are three steps for the linker:
Place code and data modules symbolically in memory.
Determine the addresses of data and instruction labels.
Patch both the internal and external references.
A functional program in the format of an object file that contains no unresolved references. It can contain symbol tables and debugging information. A “stripped executable” does not contain that information. Relocation information may be included for the loader.
Executable file:
A systems program that places an object program in main memory so that it is ready to execute.
Loader
Library routines that are linked to a program during execution.
Dynamically linked libraries (DLLs):
An executable file is executed after a blank places the file into main memory.
loader
Instruction from an instruction set designed to interpret Java programs.
Java bytecode
The program that interprets Java bytecodes.
Java Virtual Machine (JVM)
The name commonly given to a compiler that operates at runtime, translating the interpreted code segments into the native code of the computer.
Just In Time compiler (JIT)
When translating from C to assembly language by hand, we follow these general steps:
Allocate registers to program variables.
Produce code for the body of the procedure.
Preserve registers across the procedure invocation.
By convention, LEGv8 uses blank registers for parameter passing allocation.
8
Sequential doubleword addresses are blank apart, therefore a variable index needs to be multiplied by 8 before adding the variable index to the address.
8 bytes
Reads in a source program and translates the program to an intermediate representation.
front end
The blank checks the syntax and semantics, reporting detected errors. Via different blanks, a program may even have parts written in different languages, each read into the intermediate representation and then processed by subsequent phases.
front end
Relatively-big changes to a program that yield the same function, but may optimize a program’s performance or other metric.
high-level optimization
An example of a high-level optimization is blank, which replaces a procedure call (which can be slow) with the procedure’s actual instructions (which may yield more instructions overall, but faster performance). Another example is loop-unrolling, which replaces a loop with groups of statements, each group corresponding to a particular loop iteration.
procedure inlining
Global and local optimizations.
Global optimizer
Makes changes to instructions that may yield less code or better performance, such as not computing an expression like (9/5)C + 32 twice, but instead reusing the result.
Global optimizer
Converts the optimized intermediate representation into a processor’s machine instructions.
code generator
The last compiler phase outputs the actual processor-specific program. Much of the compiler’s optimizations are independent of any particular processor, meaning most of the sophisticated software of a compiler can be used for any processor.
code generator
A technique to get more performance from loops that access arrays, in which multiple copies of the loop body are made and instructions from different iterations are scheduled together.
Loop-unrolling
A Java keyword that allows a method to be invoked by any other method.
Public
A Java keyword that restricts invocation of a method to other methods in that package.
Protected
Basically a directory that contains a group of related classes.
Package
A method that applies to the whole class rather to an individual object. It is unrelated to static in C.
Static method
In contrast to C, Java explicitly stores an extra item in every array indicating the array’s blank
upper bound
In contrast to C, Java calls the appropriate method (procedure) based on the ____ of the calling object.
type
A register that can be used for addresses or for data with virtually any instruction.
General-purpose register (GPR)
Unconditional jump
jmp
Load ES register and a GPR from memory
les
Copy string from source to destination
movs
Jump if not zero
jnz
Move data between two registers
move
Load a byte, word, or doubleword of a string into the EAX register
lods
Total number of ARMv8 integer machine language instructions
250
Total number of ARMv8 SIMD/Vector assembly language instructions.
245
ARMv8 assembly language registers used for 32-bit operations.
W0, W1…
Number of branch instructions in LEGv8
6
Return from subroutine instruction
RET
Number of branch instructions in ARMv8
23
Branch register instruction
BR
T/F Using standard instructions can result in higher performance than using powerful instructions crafted specifically for an architecture.
True
T/F Assembly language programs are not easily portable because of the many different architectures of current and future computers.
True
Archaic term for register. On-line use of it as a synonym for “register” is a fairly reliable indication that the user has been around quite a while
Accumulator
Also called register-register architecture. An instruction set architecture in which all operations are between registers and data memory may only be accessed via loads or stores.
Load-store architecture
No registers architecture
stack architecture
register-register architecture
load-store architecture
Single register architecture
Accumulator architecture
Programming language-based architecture
High-level-language-based architecture
Reduced instruction set computer architecture
RISC architecture
An _________ processor powered the Apple Newton personal digital assistant.
ARM
The first microprocessors were precursors to the _________ architecture.
X86
The 8088 processors were used to power _________ computers in the 1980s.
IBM PC
_________, developed for use in business settings, employs English vocabulary and punctuation.
COBOL
_________, developed for IBM’s 704 computer in 1954, was one the first widely used programming languages.
FORTRAN
In the 1970s, Bell Labs built the UNIX operating system using the _________ language.
C
_________ was invented as a way to express algorithms more naturally than its predecessors, with less focus on coding.
Algol
Dynamic data structures and pointers were major contributions of _________.
LISP
_________ is currently the most popular language to teach in schools and is the standard language for business data processing applications.
Java
ex and yacc were developed as a part of the blank operating system,
UNIX
In early compilers, processes such as parsing and scanning consisted of ad hoc approaches. These processes were replaced by tools derived from blank
automata theory
Blank, unlike RISC architectures, do not use registers and therefore remove the need for register allocation.
Stack architectures
