What (and Why) is a Label Table?

• A label at the beginning of an instruction associates a name with the address of that instruction.

  Example Code Fragment

      Addr
     0000000    main:                           # Start of program
     0000100                                    #
     0001000                                    # There would be code 
     0001100                                    #   leading up to this fragment...
     0010000                                    #
     0011100                                    #
     0011000    LP:      slt $t1, $s0, $s1      # $t1 = 1 if $s0 < $s1
     0011100             beq $t1, $zero, ENDLP  #
     0100000                                    #
     0100100                                    #  ...  lots of stuff here
     0101000                                    #
     0101100                                    #
     0110000             j LP                   # jump back to top of LP
     0110100    ENDLP:                          #
     0111000                                    #
     0111100                                    # ... more code follows the loop
     1000000                                    #
     1000100                                    #
  

↓
• The two-pass assembler makes two passes through the code as it translates to machine code:
  • Pass 1: Compute the address of each label and put it in a table.

    Example Table

    Label	Instruction Address
    main	00...0000000 (0)
    LP	00...0011000 (24)
    ENDLP	00...0110100 (52)

  ↓
  • Pass 2: Translate assembly code to machine code, replacing label references with addresses from the table.

    Example Translation

    j LP becomes the machine code equivalent of

    j 24/4
000010 000000...0000110     24 / 4 = 6

    beq $t1, $zero, ENDLP becomes the machine code equivalent of

    beq $t1, $zero, (52-PC)/4
000100 01000 00000 0000000000000101     (52-32)/4 = 5

    The label is replaced with a value computed from the address, rather than the address directly.

---

↓
• What does the Label Table look like in memory?
  Not as sequential, interleaved strings and addresses:
   
  

  m a i n	\0 ? ? ?	00...0000000	L P \0 ?	00...0011000	E N D L	O O P \0	00...0110100
  1000	1004	1008	100C	1010	1014	1018	101C

  How would you know where each (label, address) pair starts?

  ↓
  Instead, an array of string pointers and addresses (2D view):
   
  

  	Ptr to Label Name	Instruction Address
  1000	00001410	00...0000000	typedef struct { char * labelName; int address; } LabelEntry;
  1008	00001415	00...0011000
  1010	00001418	00...0110100
  …
  …
  1410	m a i n \0
  1415	L P \0
  1418	E N D L O O P \0

  
   
  
  ↓
  Sequential, 1D view:

  00001410	00...0000000	00001415	00...0011000	00001418	00...0110100
  1000		1008		1010
  …
  …

  m a i n \0	L P \0	E N D L O O P \0
  1410	1415	1418

  (The strings might, or might not, be laid out contiguously in memory like this.)