Appendix A

Question 1

Instruction set architectures classification

Answer 1

By internal storage:

• accumulator architecture - operands are implicitly in accumulator
• stack architecture - operands are implicitly on top of the stack
• general-purpose register architecture - only explicit operands

By accessing memory and registers:

• register-memory architecture - any instruction can access memory
• load-store architecture - load and store instructions to access memory
• memory-memory architecture - not used anymore, all operands in memory

One special type is also extended accumulator or special-purpose register computers - more registers than just accumulator

Currently mostly used are general purpose register architectures - registers are faster than memories.

Question 2

How many registers are sufficient?

Answer 2

Depends on the effectivity of the compiler, some compilers allocate GP registers for different purposes such as expression evaluation (e.g. x86 stores the result of the 8-bit division in AL and modulus in AH).

Question 3

Types of GPR architectures

Answer 3

By number of operands:

• 2 operand format - one operand is both source and destination of the operation
• 3 operand format - one result operand, two src operands

By number of memory operands:
- multiple different amounts - from all three to none

Question 4

Memory access types

Answer 4

byte - 8 bits
half word -16 bits
words - 32 bits
double words - 64 bits

Question 5

Byte ordering

Answer 5

Big Endian - highest bits are in the end - 0,1,2,3,4,5,6,7

Little Endian - lowest bits are in the end - 7,6,5,4,3,2,1,0

Question 6

Memory alignment

Answer 6

Used for accesses higher than byte - memory is then aligned by the module operation where address if address mod access size => s = 0 (e.g. for word access address 0 and 4 is aligned and address such as 2, or 6 is misaligned access

Question 7

Addrsessing modes

Answer 7

Acutal address is called effective address

Modes:

• register - value is in register
• immidiate - constants, operand is actual value
• displacement - memory[constant + regValue]
• register indirect - memory[regValue]
• indexed - memory[reg1Value + reg2Value]
• direct/absolute - memory[constant]
• memory indirect - memory[memory[regValue]]
• autoincrement/autodecrement - memory[regValue = regValue + d/regValue = regValue - d]
• scaled - memory[constant + reg1Value + reg2Value*d]

regValue - value in register
reg1Value, reg2Value - multiple registers value
d - displacement
constant - constant value

Question 8

Types of operands

Answer 8

character - 8 bits
half word - 16 bits
word - 32 bits
single-precision floating-point - 32 bits
double-precision floating-point - 64 bits

Decimal operands

• packed and binary coded decimals - 4 bits encode 0 - 9 and 2 digits are packed in each byte
• numeric character strings - unpacked decimals
• used to precisely repersent decimals which are difficult to represent in binary (e.g. 0.1)

Question 9

Operations in instruction sets

Answer 9

• Arithmetic and logic operations - e.g. add, subtract, multiply, divide, or, and
• Data transfer - load-store
• Control - branch, jump, etc.
• System - operating system call, virtual memory management
• Floating point - floating point operations - add, subtract, multiply, divide…
• Decimal - decimal add, decimal multiply, decimal to character conversions
• String - string move, string compare
• Graphics - pixel and vertex operations

Question 10

Control flow instructions types

Answer 10

conditional branches
jumps
procedure calls
procedure returns

Question 11

Adddressing modes for control flow

Answer 11

1. PC-relative - adding displacement to program counter (PC)
   - position independent
   - instructions don`t need to be fully loaded
   - usually smaller jumps
   Register indirect jumps - when jump address is unknown at compilation time
2. case or switch statements
3. virtual functions or methods
4. higher-order functions or function pointers
5. dynamically shared libraries
   They all usually load jump address from memory

Question 12

Condition branch options

Answer 12

• Condition code - tests special bits set by ALU operations, possibly under program control
• Condition register/limited comparison - tests arbitrary register with the result of a simple comparison
• Compare and branch - Compare is part of the branch

Question 13

Procedure invocation - saving processor state

Answer 13

Storing the whole processor state in other registers (older architectures). Using load and store operations to store processor`s state (newer architectures).

Question 14

Caller saving vs. Callee saving

Answer 14

In caller saving calling procedure is responsible to save the state of the processor.
In callee saving called procedure is responsible for saving the state of the processor.

Question 15

Encoding instructions - considerations

Answer 15

1. desire to have as many registers and addressing modes as possible
2. impact of the register and addressing modes on the average instruction size and average program size
3. instructions encoded into lengths that are easy to handle in a pipelined implementation.

Question 16

Instruction sizes

Answer 16

Variable - instructions can have different sizes - x86, VAX
Fixed - instructions have the same length - RISC V, ARM, MIPS
Hybrid - instructions have different lengths however, there are only few different sizes of instructions. The size is specified by the opcode

Question 17

Compilers - golas

Answer 17

Goal:
1. valid programs must be compiled correctly
2. speed of compiled code
Other goals:
- fast compilation, debugging support, interoperability among other languages

Question 18

Compilers - structure

Answer 18

Front end per language

• Dependencies - language dependent, machine independent
• Function - transforms language to common intermediate form

High-level optimizations

• Dependencies - Somewhat language dependent, largely machine independent
• Function - loop transformation, procedure inlining…

Global optimizer

• Dependencies -Small language dependencies, machine dependencies slight
• Function - Including global and local optimizations + register allocations

Code generator

• Dependencies - Highly machine dependent, language independent
• Function - Detailed instruction selection and machine-dependent optimizations, may be included or followd by assembler

Question 19

Compilers - phase ordering problem

Answer 19

Transformations can cause irreversible change of the program structure. Thus compilers need to choose some procedures, or loops to expand inline before knowing their sizes.

Question 20

Compiler - optimizations

Answer 20

• High-level optimizations - source is fed to later optimization passes
• Local optimizations - optimizing code only within straight-line code fragment (basic block)
• Global optimizations - extends optimizations accross branches and introduces a set of transformations aimed at optimizing loops
• Register allocation - associates registers with operands
• Processor-dependent optimizations - attempt to take advantage of specific architectural knowledge

Question 21

Register allocation

Answer 21

• based on technique of graph colouring
• goal is to achieve 100% allocation of the registers for active variables
• NP-complete problem
• Works best with at least 16 GP registers

Question 22

Compiler - optimizations 2

Answer 22

• High-level - at or near source level - processor independent
  
  • procedure integration - replace procedure call by its body
• Local - within straight line code
  
  • common subexpression elimination
  • Constant propagation
  • Stack height reduction
• Global - across a branch
  
  • global common subexpression elimination
  • copy propagation
  • code motion
  • induction variable elimination
• Processor-dependent - depends on processor knowledge
  
  • Strength reduction
  • Pipeline scheduling
  • Branch offset optimization

Question 23

Allocating data

Answer 23

Stack - allocates local variables

• grows and shrinks according to calls and returns
• objects addressed relative to stack pointer
• primarily used for scalars

Global data area

• statically declared objects
• arrays and other aggregated structures

Heap

• dynamically created structures
• access through pointers

Question 24

Register allocation

Answer 24

• more effective for stack allocated ojbects rather than global variables
• almost impossible to use for heap-allocated objects => accessed via pointers
• aliased variables (in stack and global data area) are difficult to register-allocate

Question 25

Basic principle in architecture

Answer 25

frequent cases fast, rare cases correct

Question 26

Helping compiler writer

Answer 26

• Provide regularity - when it makes sense, data types, instructions and addressing modes should be orthogonal. Orthogonal => independent. E.g. for every instruction if it can run in one addressing mode, it should be capable to run also in different addressing modes
• Provide primitives, not solutions - special features to support a higher-languages are usually ineffective, or unusable
• Simplify trade-offs among alternatives
• Provide instructions that bind the quantities known at compile time as constants

Question 27

Multimedia instructions

Answer 27

SIMD - lot of problems, not much used, ignores basic principles to help the compiler writer
Alternatives - MMX, AltiVec, SSE

Question 28

Addressing in vector processors

Answer 28

Vector computers provide strided addressing, gather/scatter addressing, register indirect addressing in multiple registers

Question 29

Risc-V - registers

Answer 29

32 64-bit GPRs - x0..x31 - integer registers
32 FPRs - can hold 32-bit single-precision, or 64-bit double-precision
x0 is always 0

Question 30

Risc-V - data types

Answer 30

Integer - 8, 16, 32 and 64-bit
Floating-point - 32 single-precision, 64 double precision
Operations work on 64-bit integers and 32 and 64 bit single or double precision
When using smaller integer operations that 64 bits, zeros, or sign bits are appended

Question 31

Risc-V - addressing types

Answer 31

immidiate or displacement both with 12-bit wide fields
register indirect - placing 0 to the 12-bit displacement
absolute adressing - using x0 as base register

Question 32

Risc-V - addressing architecture

Answer 32

byte addressable memory
load-store architecture
aligned and unaligned memory accesses - unaligned access may run extremly slow

Question 33

Risc-V - instruction format

Answer 33

Fixed instruction length
Two addressing modes encoded in the opcode
7 bit primary opcode
12 bits for immidiate values, displacement, or PC-relative branches

Question 34

Risc-V - instruction types

Answer 34

R-type - register-register value - rd destination register, rs1 - register 1, rs2 register 2

I-type - immidiate values - rd - destination, rs1 - first source base register, immediate - value displacement

S-type - store, compare and branch - rs1 - base register first source, rs2 - data source to store second source, immediate - displacement offset

U-type - jump and link, jump and link registers - rd - register destination for return PC, rs1 - target address for jump and link register, immidiate - target address for jump and link