[LLD][ELF] Introduce target specific inBranchRange() function

[peter.smith]

Summary

In preparation for range extension thunks introduce a function that will check whether a branch identified by a relocation type at a source address can reach a destination.

For targets where range extension thunks are not supported the function will return true as it is not expected that branches are out of range. An implementation has been provided for ARM.

This is patch 7/11 of range thunks although as it is not hooked up it can be applied independently.

[ruiu]

ELF/Arch/ARM.cpp

227 ↗

(On Diff #104165)

In this function, you computed the exact distance between two instructions, but does this much preciseness actually needed? A few bytes difference seems negligible when you want to know whether two instructions are in +-16MiB, for example.

[peter.smith]

My preference is to be precise as I think it makes reasoning about the behavior of the linker easier. From experience with ARM's proprietary linker, which got progressively more precise the main benefits were:

• Being precise means that the same range measurement function can be used in multiple places and is consistent with the relocation range check.
• It makes it simpler to write test cases at the extremes of range, and also to explain to users why the linker has generated a range-thunk when the branch should have been in range. This is not a problem for Linux like systems, but is important in embedded systems with non-contiguous memory.

-It makes it simpler to track down bugs, as this feature is most likely to trigger with large complicated test cases that users are often reluctant to share. Having the range match the relocation overflow check is useful in ruling out some problems.

In summary I think it is worth going to the extra effort here although the benefits are more long-term.

[ruiu]

LGTM

ELF/Arch/ARM.cpp

230 ↗

(On Diff #104165)

nit: add blank line

265–267 ↗

(On Diff #104165)

maybe return abs(Src - Dst) <= Range;?

[peter.smith]

Thanks for the review, I've committed r308188. The addition of abs(unsigned - unsigned) gave me some compile warnings from clang so I decided to keep the original.

lld/trunk/ELF/Arch/ARM.cpp

public:
   void writeIgotPlt(uint8_t *Buf, const SymbolBody &S) const override;
   void writePltHeader(uint8_t *Buf) const override;
   void writePlt(uint8_t *Buf, uint64_t GotPltEntryAddr, uint64_t PltEntryAddr,
                 int32_t Index, unsigned RelOff) const override;
   void addPltSymbols(InputSectionBase *IS, uint64_t Off) const override;
   void addPltHeaderSymbols(InputSectionBase *ISD) const override;
   bool needsThunk(RelExpr Expr, uint32_t RelocType, const InputFile *File,
                   const SymbolBody &S) const override;
+  bool inBranchRange(uint32_t RelocType, uint64_t Src,
+                     uint64_t Dst) const override;
   void relocateOne(uint8_t *Loc, uint32_t Type, uint64_t Val) const override;
 };
 } // namespace
 
 ARM::ARM() {
   CopyRel = R_ARM_COPY;
   RelativeRel = R_ARM_RELATIVE;
   IRelativeRel = R_ARM_IRELATIVE;
case R_ARM_THM_JUMP24:
     // Otherwise we need to interwork if Symbol has bit 0 clear (ARM).
     if (Expr == R_PLT_PC || ((S.getVA() & 1) == 0))
       return true;
     break;
   }
   return false;
 }
 
+bool ARM::inBranchRange(uint32_t RelocType, uint64_t Src, uint64_t Dst) const {
+  uint64_t Range;
+  uint64_t InstrSize;
+
+  switch (RelocType) {
+  case R_ARM_PC24:
+  case R_ARM_PLT32:
+  case R_ARM_JUMP24:
+  case R_ARM_CALL:
+    Range = 0x2000000;
+    InstrSize = 4;
+    break;
+  case R_ARM_THM_JUMP19:
+    Range = 0x100000;
+    InstrSize = 2;
+    break;
+  case R_ARM_THM_JUMP24:
+  case R_ARM_THM_CALL:
+    Range = 0x1000000;
+    InstrSize = 2;
+    break;
+  default:
+    return true;
+  }
+  // PC at Src is 2 instructions ahead, immediate of branch is signed
+  if (Src > Dst)
+    Range -= 2 * InstrSize;
+  else
+    Range += InstrSize;
+
+  if ((Dst & 0x1) == 0)
+    // Destination is ARM, if ARM caller then Src is already 4-byte aligned.
+    // If Thumb Caller (BLX) the Src address has bottom 2 bits cleared to ensure
+    // destination will be 4 byte aligned.
+    Src &= ~0x3;
+  else
+    // Bit 0 == 1 denotes Thumb state, it is not part of the range
+    Dst &= ~0x1;
+
+  uint64_t Distance = (Src > Dst) ? Src - Dst : Dst - Src;
+  return Distance <= Range;
+}
+
 void ARM::relocateOne(uint8_t *Loc, uint32_t Type, uint64_t Val) const {
   switch (Type) {
   case R_ARM_ABS32:
   case R_ARM_BASE_PREL:
   case R_ARM_GLOB_DAT:
   case R_ARM_GOTOFF32:
   case R_ARM_GOT_BREL:
   case R_ARM_GOT_PREL:

lld/trunk/ELF/Target.h

public:
   // bits will always have the same value at runtime and we don't have to emit
   // a dynamic relocation.
   virtual bool usesOnlyLowPageBits(uint32_t Type) const;
 
   // Decide whether a Thunk is needed for the relocation from File
   // targeting S.
   virtual bool needsThunk(RelExpr Expr, uint32_t RelocType,
                           const InputFile *File, const SymbolBody &S) const;
+  // Return true if we can reach Dst from Src with Relocation RelocType
+  virtual bool inBranchRange(uint32_t RelocType, uint64_t Src,
+                             uint64_t Dst) const;
   virtual RelExpr getRelExpr(uint32_t Type, const SymbolBody &S,
                              const uint8_t *Loc) const = 0;
   virtual void relocateOne(uint8_t *Loc, uint32_t Type, uint64_t Val) const = 0;
   virtual ~TargetInfo();
 
   unsigned TlsGdRelaxSkip = 1;
   unsigned PageSize = 4096;
   unsigned DefaultMaxPageSize = 4096;

lld/trunk/ELF/Target.cpp

 
 bool TargetInfo::usesOnlyLowPageBits(uint32_t Type) const { return false; }
 
 bool TargetInfo::needsThunk(RelExpr Expr, uint32_t RelocType,
                             const InputFile *File, const SymbolBody &S) const {
   return false;
 }
 
+bool TargetInfo::inBranchRange(uint32_t RelocType, uint64_t Src,
+                               uint64_t Dst) const {
+  return true;
+}
+
 void TargetInfo::writeIgotPlt(uint8_t *Buf, const SymbolBody &S) const {
   writeGotPlt(Buf, S);
 }
 
 RelExpr TargetInfo::adjustRelaxExpr(uint32_t Type, const uint8_t *Data,
                                     RelExpr Expr) const {
   return Expr;
 }