Calculating cost of an instruction in assembly language

Question

I am reading about code generation from the dragon book. It gives a naive method to associate a cost with each target language association.

We shall assume each target-language instruction has an associated cost. For simplicity, we take the cost of an in­struction to be one plus the costs associated with the addressing modes of the operands. This cost corresponds to the length in words of the instruction. Addressing modes involving registers have zero additional cost, while those in­volving a memory location or constant in them have an additional cost of one, because such operands have to be stored in the words following the instruction.

Some examples:

• The instruction LD R0,R1 copies the contents of register R1 into register R0. This instruction has a cost of one because no additional memory words are required.
• The instruction LD R0,M loads the contents of memory location M into register R0. The cost is two since the address of memory location M is in the word following the instruction.
• The instruction LD R1,*100(R2) loads into register R1 the value given by contents(contents(100+contents(R2))). The cost is three because the constant 100 is stored in the word following the instruction. Here contents(x) denotes the contents of the register or memory location represented by x.

I understood the cost calculation for the first 2 examples. I don't get the third one. How is the cost 3? Also I don't understand the bold part in the quoted text above.

Of what I partially understood I supposed the cost of BLTZ *R3,R0 to be 3 as it is so for the similar third example above. But the cost of this is 1. How?

Note BLTZ r, L causes a jump to label L if the value in register r is less than zero, and allows control to pass to the next machine instruction if not.

Answer 1

I don't get the third one. How is the cost 3?

• 1 for the instruction
• 1 for fetching the constant 100 from the next word
• 1 for fetching the value from R2+100

cost of BLTZ *R3,R0 to be 3 as it is so for the similar third example above. But the cost of this is 1. How?

Because: Addressing modes involving registers have zero additional cost.

I don't understand the bold part in the quoted text above.

Apparently the machine code for this architecture uses a word to specify the opcode along with the register operands, and an additional word if needed for a constant.

For example LD R1,*100(R2) takes 2 words. The first specifies the operation (LD with a register-relative offset) along with the destination register R1 and the base register R2. These are bitfields in the word. The second word then contains the 100 which the cpu knows to fetch because of the opcode in the first word.

Some fixed-length architectures pack constants into the first word, but then obviously they can only have limited range. Using a separate word allows for full range.

Answer 2

I am sure others could explain this better. But however, here are some inspirations:

The costs are NOT real, they are assumed by definition of the Dragon book. To get informed about the real costs, you have to check the tables of the target architecture. See the SO wiki for the corresponding links.

So coming to the three examples by relating to your quote above:

we take the cost of an in­struction to be one

Therefore every instruction is assumed to have a cost of one!

those in­volving a memory location or constant in them have an additional cost of one

So the examples 1 to 3 have

• 1 instruction + 0 mem/const = 1
• 1 instruction + 1 mem = 2
• 1 instruction + 1 mem + 1 one const = 3

The memory addresses and the constants are encoded in the instruction OpCode separately in the additional words of the instruction prolonging the, to be fetched, OpCode bytes affecting the CPU Op/microOp processing.