[CA2] Instructions; Language of the computer

2.1. Introduction

컴퓨터 하드웨어에 명령을 내리기 위해, 우리는 하드웨어의 언어를 할 줄 알아야 한다.

instruction: Words of a computer’s language.
[1]instruction set: Vocabulary of computer.

instruction set Example:

• RISC: Reduced Instruction Set Computer (contrasting concept: CISC)
  • e.g. MIPS, ARM, Power PC, etc.

Computer “Architecture” defines…

• Instruction Set Architecture
  • Instruction Set
  • Operand types
  • Data Types (integers, FPs, …)
  • Memory addressing modes, …
• Registers and other state
• The interrupt/exception model
• Memory management and protection
• Virtual and physical address layout
• IO model

Chapter Goal

Know how to represent instructions.

Overview

1. Learn how to represent instructions.
2. Discover the [2]stored-program concept
3. Exercise the “forieign language” skills by writing Assembly programs & running them on the simulator that comes with this book.
4. See the impact of programming languages and compiler optimization on prformance.
5. Historical evolution of instruction sets.

2.2. Operations of the Computer Hardware

The MIPS instruction set

• Used as the example throughout the book.
• Stanford MIPS commercializd by MIPS technologies
• Typical of many modern ISAs.
• Similar ISAs have a large share of embedded core market.
  • Applications in consumer eletronics, network/storage equipment, cameras, printers, …
  • Almost 100 million MIPS processors manufactured in 2002. \cf

[ Register name, Number, Use, Call Convention ]

[2.8]

Name	Number	Use	Preserved Across a Call?
$zero	0	The constant value 0	n.a.
$at	1	Assembler Temporary	No
$v0-$v1	2-3	Values for function Results and Expression Evaluation	No
$a0-$a3	4-7	Arguments	No
$t0-$t7	8-15	Temporaries	No
$s0-$s7	16-23	Saved Temporaries	Yes
$t8-$t9	24-25	Temporaries	No
$k0-$k1	26-27	Reserved for OS Kernel	No
$gp	28	Global Pointer	Yes
$sp	29	Stack Pointer	Yes
$fp	30	Frame Pointer	Yes
$ra	31	Return Address	Yes

• 0 is zero.
• 1 is at (assembly temp).
• v(2~): 2
• a(4~): 4
• t(8~): 10
• s(16~): 8
• k: 2. Betweens.
• 28~31: Specials

암기: zavatskgsfra (?)

[ MIPS instructions ]

Category	Instruction	Example	Meaning	Comments
Arithmetic	add	add $s1,$s2,$s3	$s1 = $s2 + $s3	Three register operands
Arithmetic	subtract	sub $s1,$s2,$s3	$s1 = $s2 - $s3	Three register operands
Arithmetic	add immediate	addi $s1,$s2,20	$s1 = $s2 + 20	Used to add constants
Data transfer	load word	lw $s1,20($s2)	$s1 = Memory[$s2+20]	Word from memory to register
Data transfer	store word	sw $s1,20($s2)	Memory[$s2+20] = $s1	Word from register to memory
Data transfer	load byte	lb $s1,20($s2)	$s1 = (signed)Memory[$s2+20]	Byte from mem to reg with sign extension.
Data transfer	load byte unsigned	lbu $s1,20($s2)	$s1 = (unsigned)Memory[$s2+20]	Byte from mem to reg, unsigned.
Data transfer	load half	lh $s1,20($s2)	$s1 = Memory[$s2+20]	Halfword memory to register
Data transfer	load half unsigned	lhu $s1,20($s2)	$s1 = Memory[$s2+20]	Halfword memory to register
Data transfer	store half	sh $s1,20($s2)	Memory[$s2+20] = $s1	Halfword register to memory

Fixation of operand #s in arithmetic operators (as 3) demonstrates regularity.

This illustrates first of the three underlying principles of hardware design:

HW Design Principle 1

Design Principle 1: Simplicity favors regularity.

(form of arithmetic operations)

• Regularity makes implementation simpler
• Simplicity => high perf / low cost

Example: Changing the below C code into Assembly.

f = (g + h) - (i + j);

Compiled MIPS code (Assembly)

• $s0: f
• $s1: g
• $s2: h
• $s3: i
• $s4: j

add $t0, $s1, $s2 # temp t0 = g + h
add $t1, $s3, $s4 # temp t1 = i + j
sub $s0, $t0, $t1 # f = t0 - t1

2.3. Operands of the Computer Hardware

• registers: limited number of special locations built directly in hardware.
• [3]word: Unit of access in a computer; corresponds to the size of a register in the MIPS architecture.
• MIPS has a 32 * 32-bit register file. => word: 32 bits

HW Design Principle 2

Smaller is faster.

The reason for the limit of 32 registers:
Large number of register => Increase clock cycle time
∵ it takes longer electronic signals.

Memory Operands

• [4]data transfer instruction:
  • load: Copies data from memory to a register.
  • store: Complementary D.T.I. to load: copies data from a register to a memory.
• [5]address: A value denoting the location of a specific data element within a memory array.
• MIPS uses byte addressing: 1 Address difference leads to 1 byte location difference in memory.

• [6]Alignment restriction: Word must start at addresses that are multiples of 4.

• Base address: Starting address (of an array)
• Base register: The register added to an offset to form an address (i.e. representing base address.)
• Offset: The constant in a data transfer instruction.

Example:

g = h + A[8];

• g: $s1
• h: $s2
• A: Array of 100 words.
• Base register storing base address of A: $s3.

lw $t0, 32($s3) # Temp reg $t0 gets A[8]
add $s1, $s2, $t0 # 

Example:

A[12] = h + A[8];

• h: $s2
• Base Address of A at : $s3.

lw $t0, 32($s3) # Temp reg $t0 gets A[8]
add $t0, $s3, $t0
sw $t0, 48($s3)

Q. Why using base register is beneficial?

A. We can address wider range of memory.

• Using only 5 bits of instruction to stress the base register, we can address 2^32 byts of memory,
• whereas merely \(2^5\) bytes would be addressible did we use it not as base register, but as the address itself.

cf. Concepts

• Endianness:
  • Big endian: Put most-significant byte at least address of a word.
  • Little endian: Put least-significant byte at least address of a word.
• spilling registers: Process of putting less commonly used variables into memory.
• Registers (than memory):
  • Less access time
  • Higher throughput
  • Less energy

=> Compilers must use registers efficiently. \cf

Constants or Immediate Operators

common case fast: Using frequency to justify the inclusions of constants.

• Small constants are common.

• Immediate operand avoids a load instruction.

• addi: Avoid the load instructions from constant numbers to add a constant.
• $zero: Value zero.

addi $s3, $s3, 4 # $s3 = $s3 + 4

cf. MIPS supports negative consts => No need for subi.

2.4. Signed & Unsigned Numbers

Meh, You know.

Terms:

• binary digits: One of the two numbers in base 2, 0 or 1, that are the components of information.
• least significant bit: The rightmost bit in a MIPS word.
• most significant bit: The leftmost bit in a MIPS word.
• overflow: When the results of an operation are larger than can be represented in a register.

MIPS instructions

• lb (I format)

• lbu (I format) e.g. Representing characters.

• 2’s complement: Unsigned sum of an n-bit int and its n-bit negative is 2^n. Sign bit == MSB in this case.
  • sign extension: The leftmost bit in a MIPS word.
    • Converting m bit integer to n(>m) bit integer.
    • Signed: Replicate the most significant bit to the left.
    • Unsigned: Extend with 0s.
  • negation:
    • x: signed int.
    • \(\bar{x}\): every bit inverted of x.
    • \[x + \bar{x} = -1\]
    • \[∴ -x = \bar{x} + 1\]

2.5. Representing Instructions in the Computer

Terms

• field: Certain segments of instructions.
• instruction format: A form of representation of an instruction composed of fields of binary numbers.
• machine language: Binary representation used for communication within a computer system.
• hexadecimal: Numbers in base 16.
• opcode: The field that denotes the operation & format of an instruction.

Instruction Formats

regularity: All instructions encoded as 32-bit instruction words.

Different formats complicate decoding, but commonly allow 32-bit instructions.

HW Design Principle 3

Design Principle 3: Good design demand good compromises

• R-type(=R-format) (R: Register)
  • Instruction Fields
    • op: operation code (opcode)
    • rs: first source register number
    • rt: second src register num
    • rd: destination register num
    • shamt: shift amount (00000 for now)
    • funct: function code (extends opcode)
  • Examples:
    • Arithmetic ops.
• I-type(/format) (for immediate)
  • Instruction Fields
  • Examples:
    • Immediate arithmetic ops
    • load/store instructions
  • Usage:
    • rs: base register or second operand of assembly.
    • rt: the register (that stores the result) or first operand of assembly.
    • immediate: const(\(-2^15\) to \(2^15 - 1\)) or address(offset added to base address in rs.)
• J-type(/format) (J: Jump)
  • Instruction Fields
  • Examples:
    • Jump Instructions (j and jal)
      • Address: encode 26-bit target address
      • jal: save the address of the nxt(=following) instruction in $ra and jump to an address.

Example:

Convert this into the corresponding MIPS machine instruction.

add $t0, $s1, $s2

Solution:

• add is R-format. OPCODE/FUNCT: 0/20(hex)
• Therefore the fields are as follows:
  • opcode: 0
  • rs: $s1
  • rt: $s2
  • rd: $t0
  • shamt: 0
  • funct: 20 (hex) Thus the machine code would be as follows:

000000 10001 10010 01000 00000 100000

(0000 0010 0011 0010 0100 0000 0010 0000) as hex, 0232 4020

Example:

• C code

  A[300] = h + A[300];
  

• Assembly code (A: 4-byte array, base addr in $t1, h: $s2)

  lw $t0, 1200($t1)
  add $t0, $s2, $t0
  sw $t0, 1200($t1)
  

• Machine code
  • Instructions and formats
    • add: R
    • lw, sw: I
  • Fields:
    • add:
      • opcode/funct: 0/32
      • rs: $s2 => 18
      • rt: $t0 => 8
      • rd: 8
      • shamt: 0
    • lw, sw:
      • opcode: 35, 42
      • rs: $t1 (base reg!) => 9
      • rt: $t0 (just reg!) => 8
      • immediate: 1200.

    operation	op	rs	rt	rd	shamt	funct
    add	0	18	8	8	0	32
    lw	35	9	8	1200
    sw	43	9	8	1200

  lw->add->sw.

  100011	01001	01000	0000 0100 1011 0000
  000000	10010	01000	01000	00000	100000
  101011	01001	01000	0000 0100 1011 0000

Example:

addi $s1, $s2, 100

opcode	rs	rt	immediate
8	18(for $s2)	17(for $s1)	100

2.6. Logical Operators

Terms:

• AND: A logical bit-by-bit operation with two operands that calculates a 1 only if thre is a 1 in both operands.
  • Application: Mask bit in a word (select some bits, clear others to 0)
• OR: A logical bit-by-bit operation with two operands that calculates a 1 if there is a 1 in either operand.
  • include bits in a word.
• NOT: 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.
• NOR (NOT OR): A logical bit-by-bit operation with two operands that calculates the NOT of the OR of the two operands. That is, it calculates a 1 only if there is a 0 in both operands.
• cf. XOR: A binary bit operation that returns 1 iff the two bits differ.

Ops:

• sll: shift left logical (R)
  • rs=0 (unused)
  • e.g. sll $t2, $s0, 4 => $t2 = $s0 « 4. (sllop 0 16 10 4 (shamt) sllfunc)
• srl: shift right logical
• and, andi: and. nyum.
  • and (R) (e.g. and $t0 $s1 $s2 nyum nyum) (nyum. andop 17 18 8 0 andfunc)
  • andi (I) (e.g. andi $s1 $t0 24 => nyum nyum) (nyum. andiop 8 17 24. )
• or, ori
• nor(R): A NOR B == NOT (A OR B)
  • • noring an argument with 0 leads to not.

2.7. Instructions for Making Decisions

Terms:

• conditional branches: An instruction that requires the comparison of two values and that allows for a subsequent transfer of control to a new address in the program based on the outcome of the comparison.
• basic block: A sequence of instructions without…
  • branches (except possibly at the end) and
  • branch targets or branch labels (except possibly at the beginning).
• jump == unconditional branches
• jump (address) table: A table of addresses of alternative instruction sequences.

Ops:

• beq rs, rt, L1 (I)
  • if rs == rt, then Branch to instruction labeled L1.
• bne rs, rt, L1
  • if rs != rt, then Branch to instruction labeled L1.
• j L1
  • Unconditional jump to instruction labeled L1.
• Comparison instructions (4)
  • slt (set less than) rd, rs, rt
    • if(rs < rt) rd = 1; else rd = 0;
  • slti rt, rs, const
  • sltu (nyum.)
    • Special usage: index-out-of-bounds checking.
    • e.g.

      # see if $t0 < $s1 and $t0 >= 0, where $s1 > 0. Else, out-of-bound.
      sltu $t1, $t0, $s1
      beq $t1, $zero, IndexOutOfBounds
      

  • sltiu (nyum)

2.8. Supporting Procedures in Computer Hardware

Terms:

• procedure (‘function’): A stored subroutine that performs a specific task based on the parameters with which it is provided.
• jump-and-link instruction: An instruction that jumps to an address and simultaneously saves the address of the following instruction in a register($ra in MIPS).

• return address: A link to the calling site that allows a procedure to return to the proper address; in MIPS it is stored in register $ra.

• caller: The program that instigates a procedure and provides the necessary parameter values.
• callee: A procedure that executes a series of stored instructions based on parameters provided by the caller and then returns control to the caller.
• program counter (PC): The register containing the address of the instruction in the program being executed.
• stack: A data structure for spilling registers organized as a last-in-first-out queue.
  • push: Add element to stack.
  • pop: Remove element from stack.

• stack pointer: 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 MIPS, it is register $sp.

• global pointer: The register that is reserved to point to the static area.
• procedure frame(= activation record): The segment of a stack containing a procedure’s saved registers and local variables.
• frame pointer: A value denoting the location of the saved registers and local variables for a given procedure.
• text segment: Th segment of a UNIX object file that contains the machine language code for routines in the source file.

Concepts

Procedure Calling Step

1. Caller places params in argument registers for the procedure(callee).
   • $a0-$a3: Argument registers to pass params.
2. Caller transfer control to the callee. (This also assigns $ra the next instruction.)
   • jal Func
3. Callee acquires storage resources for the procedure
   • addi $sp, $sp, -4*n
4. Callee performs the desired task.
5. Callee puts the return value in value registers for the caller.
   • $v0-$v1: Value registers to return result values.
6. Callee returns control to the caller.
   • Done by: jr $ra.

Instructions

• jr: jump to a register specified. e.g. $ra.
• jal: jump-and-link. Jumps to an address and simultaneously saves the address of the following instruction in a register ($ra in MIPS)

Nested Procedures (non-leaf procedures)

: procedures that call others.

For nested calls, the caller needs to save on the stack:

• Its return address
• Any arguments and temporaries needed after the call.

Restore from the stack after the call.

Note: Which register values must be preserved during a procedure call? [reg table]

• $s0-$s7
• $sp, $ra(, $fp, $gp) ( () : if used.) (- stack above the stack pointer.)

Allocating Space for new Data on the Stack

How to save all the values of the registers that must be saved & can be modified?
We simply use the memory section: stack.

• Allocation of space: just add -4(=word size)*(reg size) to the $sp.
• Location of space: address via ($sp + 4*n), etc. (or sometimes $fp-4*n can be used.)
• Deallocate after loading the needed information back in the registers and restore $sp value.

Registers

• $ra (return address): A link to the calling site that allows a procedure to return to the proper address.
• $sp : A value denoting the most recently allocated address in a stack that shows whre registers should be spilled or where old register values can be found.
  • Stack GROWS from HIGHER to LOWER addresses.
• $fp: Points to the first word of the (stack) frame of a procedure. Used as a stable base register within a procedure for local memory references.

Example: Factorial Code

C code:

int fact(int n) {
  if(n<1) return 1;
  else return n * fact(n-1);
}

• argument n in $a0
• result in $v0

MIPS code:

Fact:
  slti  $t0, $a0, 1
  bne $t0, $zero, Base
  addi $sp, $sp, -1
  sw $ra, 0($sp) # This must be done!
  addi $a0, $a0, -1
  jal Fact # Because of this! Non-leaf!
  lw $ra, 0($sp)
  addi $sp, $sp, 4
  addi $a0, $a0, 1
  mul $v0, $v0, $a0
  jr $ra
Base:
  addi $v0, $zero, 1
  jr $ra

Memory Layout

• Text: program code
• static data: global variables
  • e.g. static variables in C, constant arrays and strings
  • $gp initialized to address allowing ±offsets into this segment.
• dynamic data: heap

2.9. Communicating with People

ASCII encoding: A representation of characters offered by most computers today.

characters are represented into integers 0-127 (7 bits). This consumes 1 byte.

https://en.wikipedia.org/wiki/ASCII

MIPS Instructions: (for Byte/Halfword Operations: )

Sign extending loads

• lb rt, offset(rs)
• lh rt, offset(rs)

Zero extending loads

• lbu rt, offset(rs)
• lhu ret, offset(rs)

No extending store

• sb rt, offset(rs)
• sh rt, offset(rs)

Example: String Copy (null-terminated strings)

C code:

void strcpy (char x[], char y[]) {
  int i;
  i = 0;
  while ((x[i]=y[i]) != '\0')
    i+=1;
}

• Addresses of x, y in $a0, $a1
• i in $s0

strcpy:
1 addi $sp, $sp, -1
2 sw $s0, 0($sp)
3 add $s0, $zero, $zero
Loop:
4 sll $t0, $s0, 2
5 add $t1, $t0, $a1 # addr of y[i]
6 add $t2, $t0, $a0 # addr of x[i]

7 lbu $t3, 0($t1)
8 sb  $t3, 0($t2)

9 beq $t3, $zero, Exit
10  addi $s0, $s0, 1
11  j Loop
Exit:
12  lw $s0, 0($sp)
13  addi $sp, $sp, 4
14  jr $ra

Q. The code above is a problematic code. Which line causes the problem?

A. the line 4. sll $t0, $s0, 2 causes a problem.
This does not have to be done as each entry of the arrays is a char type, using one byte, not one word.
You’d be able to simply correct the problem then.

2.10 MIPS Addressing for 32-bit Immediates & Addresses

Terms:

• PC-relative addressing: An addressing regime in which the address is the sum of the program counter (PC) and a constant in the instruction.

32-Bit immediate Operands

MIPS Instructions: (for storing 32-bit constant)

• lui rt, imme: stores the immediate value to the upper(left) 16 bits of rt.

Branch Addressing

J-type

• op (6 bits)
• address (26 bits)

Target address = (PC+4’s 31-28th bit) (addr«2)

Branch Addressing

PC-relative addressing

• op
• rs
• rt
• imme

16 bits for ±offset(=imme) in word granularity (i.e. 2^15 words)

Target Address = (PC for next instruction) + offset * 4 [byte]

2.11 Parallelism and Instructions: Synchronization

Parallel excution is easier when tasks are independent, but often they need to cooperate.

Terms:

• data race: Two memory accesses form a data race if they are from different threads to same location, at least one is a write, and they occur one after another.

Critical ability for synchronization:
Atomically read and modify a memory location.

• i.e. Nothing else can interpose itself between the read and the write of the memory location.

Could be a single instruction

• e.g. Atomic swap of register <-> memory.
• Or an atomic pair of instructions.

lock values:

• value 0: free
• value 1: locked (unavailable)

ll, sc

• ll: load linked

  ll $rt, imme($rs)

  Stores Memory[$rs+imme] to the register $rt.

  Also, the hardware internally memorize (address, value) of the Memory specified by $rs+imme. (e.g. via CPU configuration bit)

• sc: store conditional

  sc $rt, imme($rs)

  Store register $rt value to the memory with address imme($rs). (IDK: if not stored if $rt below equals 0.)

  $rt = the address specified by imme($rs) has the same value since the last ll to the address ? 1 : 0.

This ensures the atomicity of writing in the memory location specified by imme($rs).

e.g. atomic swap (in Ch.13) p.140

# Swapping contents of $s4 and the memory location specified by $s1
swap: add $t0,  $zero,  $s4 # copy exchange value
      ll  $t1,  0($s1)      # load linked ; load Mem[$s1] to register $t1, and let 'LM' map $s1 to the current value of Mem[$s1].
      sc  $t0,  0($s1)      # store conditional ; see if LM[$s1] == Mem[$s1].
                            # If true, then store $t0 value to Mem[$s1] and $t0 = 1.
                            # If false, then $t0 = 0.
      beq $t0,  $zero,  $swap # branch store fails
      add $s4,  $zero,  $t1 # put loaded value in $s4.

2.12 Translating and Starting a Program (partly covered in class.)

Terms:

• assembly language: A symbolic language that can be translated into binary machine language.
• pseudoinstruction: A common variabion of assembly language instructions often treated as if it were an instruction in its own right.
• symbol table: A table that matches names of labels to the addresses of the mmory words that instructions occupy.
• linker (=link editor): A systems program that combines independently assembled machine language programs and resolves all undefined labels into an executable file.
• executable file: 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” dos not contain that information. Relocation information may be included for the loader.
• loader: A systems program that places an objct program in main memory so that it is ready to execute.
• dynamically linked libraries (DLLs): Library routines that are linked to a program during execution.
• Java bytecode: Instruction from an instruction st designed to interpret Java programs.
• Java Virtual Machine (JVM): The program that interpretes Java bytecodes.
• Just In Tim compiler(JIT): The name commonly given to a compiler that operates at runtime, translating the interpreted code segments into the native code of the computer.

Assembler

• pseudoinstructions.

e.g.

• move
• blt

nyumnyum

2.14 Arrays versus Pointers

nyum nyum 2가지 비교 with the print.

Word List

❗단어들❗

link	단어	뜻
1	instruction set	The vocabulary of commands understood by a given architecture
2	stored-program concept	The idea that instructions and data of many types can be stored in memory as numbers, leading to the stored program computer.
3	word	The natural unit of access in a computer, usually a group of 32 bits; corresponds to the size of a register in the MIPS architecture.
4	data transfer instruction	A command that moves data between memory and registers
5	address	A value used to delineate the location of a specific data element within a memory array.
6	alignment restriction	A requirement that data be aligned in memory on natural boundaries.
—	data race	Two memory accesses form a data race if they are from different threads to same location, at least one is a write, and they occur one after another.
—	pseudoinstruction	A common variation of assembly language instructions often treated as if it were an instruction in its own right.

MIPS Green Sheet

0-1

0-2