Linking very large programs with inadequate branch displacements

[Bill Yoder <byoder at cs dot utexas dot edu>]

Hi, All:

We've been using binutils in my research group for 3 years now in  
order to support a new microprocessor named TRIPS.  So far, things  
have gone swimmingly.

Just recently, we've hit a wall in linking very large programs.  The  
reason is that we are using the processor's branch-with-offset and  
call-with-offset instructions, consisting of a 20-bit displacement  
field, for most of our jumps.  When the target address is too far  
away, that is, when the offset from the PC is too big to fit in the  
displacement field, our linker complains in the  
trips_elf_relocate_section() back end and that's as far as we get.

What we'd like to do is to open up a hole in the bfd output section  
and insert a springboard in it, so that the offending instruction can  
instead branch to that nearby springboard and then use an absolute  
address embedded in the springboard to jump to the far-distant target.

So the question is, have others run into this problem?  I was told  
that usage of the Alpha BSR instruction might cause similar  
problems.  However, this code in the elf64_alpha_relocate_section()  
doesn't appear too hopeful:

case bfd_reloc_outofrange:
          abort ();
        }

If it were possible to determine in the linker front end which bfd  
input text sections have code symbols with very large addresses, and  
to increment the location counter for those sections in order to open  
up holes at the end of those sections, or at the beginning of the  
next section, then in relocate_section() we should be able to  
generate the springboards and fix up the relocs accordingly.

Does this approach sound feasible, or maybe just a chicken-and-egg  
situation, in which we can't allocate space for springboards until we  
know which instructions need them, but we can't know that until we've  
pinned down the target addresses?

Your guidance would be appreciated.

Bill Yoder
University of Texas at Austin
http://www.cs.utexas.edu/users/cart/trips/