Target Machine Architecture and Instruction Costs: Defining a Computation Model
This document defines the architecture of a target machine for the purpose of calculating instruction costs in compiler design. The specifications include memory addressing, instruction formats, supported opcodes, and other relevant details for determining computational complexity.
Target Machine Architecture and Instruction Costs
Target Machine Specifications
Let's define the characteristics of our target machine for instruction cost calculations. It's a byte-addressable machine with 4 bytes per word. It has 'n' general-purpose registers (R0, R1...Rn-1). Instructions follow a two-address format:
op source, destination
Where:
opis the operation code (opcode).sourceis the source operand.destinationis the destination operand.
Supported Operations (Opcodes)
The machine supports these opcodes:
ADD: Adds the source to the destination.SUB: Subtracts the source from the destination.MOV: Moves the source to the destination.
Addressing Modes
The source and destination operands can be specified using several addressing modes:
| Mode | Form | Address Calculation | Example | Added Cost |
|---|---|---|---|---|
| Absolute | M | Memory address M | MOV R0, M |
1 |
| Register | R | Register R | ADD R0, R1 |
0 |
| Indexed | c(R) | Base address c + contents of register R | ADD 100(R2), R1 |
1 |
| Indirect Register | *R | Contents of register R | ADD *R0, R1 |
0 |
| Indirect Indexed | *c(R) | Contents of (c + contents of register R) | ADD *100(R2), R1 |
1 |
| Literal | #c | Constant value c | ADD #3, R1 |
1 |
Instruction Cost Calculation
The cost of an instruction is one word (base cost) plus an additional cost for each operand's addressing mode:
Instruction Cost = 1 + cost(source addressing mode) + cost(destination addressing mode)
Instruction Cost Examples
- Move Register to Memory (R0 → M):
MOV R0, M. Cost: 1 (base) + 1 (memory) + 0 (register) = 2 - Indirect Indexed Mode (MOV *4(R0), M):
MOV *4(R0), M. Cost: 1 (base) + 1 (indirect indexed) + 1 (memory) = 3 - Literal Mode (MOV #1, R0):
MOV #1, R0. Cost: 1 (base) + 1 (literal) + 0 (register) = 2