Computer Organization and Design

David A. Patterson, John L. Hennessy

Mentioned 3

"Presents the fundamentals of hardware technologies, assembly language, computer arithmetic, pipelining, memory hierarchies and I/O"--

More on Amazon.com

Mentioned in questions and answers.

my question is: When I have something like this:

lea rax, rbp - 8

// Maybe that's an int on my stack, because I have a local "int"-variable in my code. How does the CPU know, where the data is, when I do this:

mov qword [rax], 14

I mean, it's just an address... What if I had reserved memory at 2^64 - x ?

Cant your allocated memory have this kind of address?

Or what if the stack grew until it has the same addresses as your allocated memory?

Does that happen?

The Assembler doesn't know what the number in rax is, so it can't be a MOVstack and a MOVheap, like with near and far JMPs.

How does the CPU know, where the data is, when I do this mov qword [rax], 14

Why would the CPU need to know whether the data is on the stack or or heap ? both are in the same place, the RAM.

I mean, it's just an address... What if I had reserved memory at 2^64

You won't be able to reserve memory there if the address is bigger than your address space.

Or what if the stack grew until it has the same addresses as your allocated memory ? Does that happen?

Yes it happens, it's called a stackoverflow :) and will most likely result in a segmentation fault.

The Assembler doesn't know what the number in rax is, so it can't be a MOVstack and a MOVheap

As far as I know, there are no separate instructions for accessing the stack or the heap, like I said, the stack and heap both exist in the RAM. All the CPU cares about is the address to write to or read from, however, on some architectures, those that don't have a memory-mapped I/O there are special instructions for accessing I/O registers, most architectures see I/O as just another memory address.

You should read a book about computer architecture, I recommend this one Computer Organization and Design, 4th Ed by Patterson.

Consider the following MIPS assembly (I'm using MIPS because that is what my Computer Organization and Design book uses):

beq   $s0, $s1, L1
add   $t0, $t1, $t2
...
L1: ...

Because MIPS only uses 16 bits for the PC-relative address in the beq instruction, if L1 is sufficiently far away from the beq, the assembler must replace it with two instructions (a jump has 26 bits for the address) and a new label:

bne   $s0, $s1, L2
j     L1
L2:   add $t0, $t1, $t2
...
L1: ...

If even this isn't enough, it may need multiple jumps.

The assembler doesn't know whether it needs to make this replacement until it knows the location of L1. Since it doesn't initially know the size of the beq (1 instruction or 2), how can it keep the location counter up-to-date during the first pass?

There are multiple approaches:

  • Reserve space only for one instruction and if it's found not enough, expand it.
  • Reserve enough space for the two instructions and then either fill the unused space with nop(s) or compact the code.

In either case you don't have to generate (semi-)final machine code immediately, nor do you need to rescan the source code and reassemble it, though it's possible. You can generate "intermediate" code or its representation at first and then fix it up, pretty much what the linker does.

Speaking of which [the linker], there's also another option:

  • Leave this piece for the linker to handle. It's not very hard. Nowadays compilers (e.g. Microsoft Visual C++) can do link-time code optimization.

I'd like to run more MIPS assembly programs. I can run the emulator (MARS) and I can run basic assembly programs. Now I have for instance this program to study, which is OK for my current level:

.data
prompt: .asciiz "\n Please Input a Value: "
bye: .asciiz "\n Bye!"
.globl main
.text

main:
   li $v0, 4
   la $a0, prompt
   syscall

   li $v0, 5
   syscall
   beqz $v0, end
   move $a0, $v0
   li $v0, 1
   syscall
   b main


end:
   li $v0, 4
   la $a0, bye
   syscall

   li $v0, 10
   syscall

I have 2 book that discuss the theory but they are more about the electronics and how CPU is contructed and not so much teach you how to write complete programs (the books I follow are Computer Organization and Design and a book in Swedish called Datorsystem and while these books describe fairly well the background and individual instruction, I need more pointer to complete programs that I can learn from modifying, some similar simple programs with basic i/o like the one above. Since many programs in the books make assumptions that are not realistic e.g. that a certain value already is in a certain register. Practicing on the program above is really good since it is a complete program. Can you help me?

All this assumes that you want to become a competent MIPS assembly programmer:

  • See MIPS Run is the canonical book on MIPS CPUs. This book explains the MIPS instruction set, CPU architecture and how they relate to MIPS Linux.

  • Get a MIPS cross compiler toolchain, like the free Mentor/CodeSourcery toolchain, use it to compile your favorite C/C++ programs into MIPS, and study the assembler output.

  • You can download and study a MIPS port of Linux from Timesys.

  • You can find a free and complete MIPS simulator here (MARS and SPIM are not complete enough for anything more than homework problems). If you want to run MIPS programs on cheap real hardware, start with OpenWrt.