title: How does a linker relocate branch instructions in MIPS?
body: <h3>Background</h3>
  <p>I'm working on a 2015 CS61C (Berkeley) course project on writing a linker to link object files generated from the following subset of the MIPS instruction set.</p>
  <pre><code>Add Unsigned: addu $rd, $rs, $rt
  Or: or $rd, $rs, $rt
  Set Less Than:  slt $rd, $rs, $rt
  Set Less Than Unsigned: sltu $rd, $rs, $rt
  Jump Register:  jr $rs
  Shift Left Logical: sll $rd, $rt, shamt
  Add Immediate Unsigned: addiu $rt, $rs, immediate
  Or Immediate:   ori $rt, $rs, immediate
  Load Upper Immediate:   lui $rt, immediate
  Load Byte:  lb $rt, offset($rs)
  Load Byte Unsigned: lbu $rt, offset($rs)
  Load Word:  lw $rt, offset($rs)
  Store Byte: sb $rt, offset($rs)
  Store Word: sw $rt, offset($rs)
  Branch on Equal:    beq $rs, $rt, label
  Branch on Not Equal:    bne $rs, $rt, label
  Jump:   j label
  Jump and Link:  jal label
  Load Immediate: li $rt, immediate
  Branch on Less Than:    blt $rs, $rt, label
  </code></pre>
  <p>From this subset of instructions, I think the ones that need relocation are <code>j</code>, <code>bne</code>, <code>beq</code> instructions (<code>blt</code> is a pseudo-instruction), the latter two needing to be relocated if the label is not present in the same file.</p>
  <p>The comments of the MIPS function that does the relocation of an instruction reads</p>
  <pre><code>#------------------------------------------------------------------------------
  # function relocate_inst()
  #------------------------------------------------------------------------------
  # Given an instruction that needs relocation, relocates the instruction based
  # on the given symbol and relocation table.
  #
  # You should return error if 1) the addr is not in the relocation table or
  # 2) the symbol name is not in the symbol table. You may assume otherwise the 
  # relocation will happen successfully.
  #
  # Arguments:
  #  $a0 = an instruction that needs relocating
  #  $a1 = the byte offset of the instruction in the current file
  #  $a2 = the symbol table
  #  $a3 = the relocation table
  #
  # Returns: the relocated instruction, or -1 if error
  </code></pre>
  <p>Note that the relocation table contains addresses relative to the start of the object file being linked, while the symbol table is an aggregate of the symbol tables of all the object files being linked and contains absolute addresses.</p>
  <h3>Problem</h3>
  <ul>
  <li><p>If the instruction to be relocated is a <code>j</code> instruction, since <code>$a1</code> contains the relative address of the instruction, we find the label that needs to be relocated in the relocation table, and then find the absolute address for that label in the symbol table. We can than add (absolute address &gt;&gt; 2) as the low 26 bits of the instruction.</p>
  </li>
  <li><p>If the instruction to be relocated is <code>bne</code>, or <code>beq</code> however, I am not sure what to do, since the low order bits are supposed to be relative to PC+4, but we don't know what the absolute address of the instruction being relocated is, so we don't know what PC+4 is.</p>
  </li>
  </ul>
  <p>Looking at various <a href="https://github.com/margooka/cs61c-proj2-2/blob/master/linker-src/linker_utils.s#L107-L113" rel="nofollow noreferrer">solutions</a> online, it seems that only <code>j</code> relocations are handled.</p>
  <p>Am I missing something?</p>
  <p><strong>EDIT</strong>: We are only considering the text segment.</p>