[lld][ELF] Relax long jump/call to short jump/call on AVR

[benshi001]

Summary

The short jump/call costs less cycles than the long jump/call.

[benshi001]

lld/test/ELF/avr-relax.s

37

These 2 jmp instructions are no relaxed, due to out of range.

lld/test/ELF/basic-avr.s

12

We should not display <unknown>, we can display the instructions via adding --mcpu=atmega328p to llvm-objdump.

[benshi001]

lld/ELF/Arch/AVR.cpp

245

Is there any better we can remove this nop ? I can only figure out the way by memcpy uint8_t *loc .

[MaskRay]

lld/ELF/Arch/AVR.cpp

245

I implemented this for RISC-V but I am unsure we should get the complexity for the less-used AVR port. This complexity is exactly what I called out in a previous patch and you said that you did not intend to implement it.

[benshi001]

lld/ELF/Arch/AVR.cpp

245

I see. I will not pursue removing the NOP any more.

And I think current form long jump -> short jump + nop is simple enough, at least 1 cycle is saved. Hopefully you will accept. ^_^

[benshi001]

ping ...

[MaskRay]

Apologies but this patch gives a feeling of overengineering for a less-popular (experimental) arch. Adding code with unclear benefits... Is it measurable?

[MaskRay]

Replacing an instruction to two likely makes the execution slower, so I think since we don't implement linker relaxation for AVR, we should not do the jmp/call rewriting as well.

[benshi001]

In D146216#4225135, @MaskRay wrote:

Replacing an instruction to two likely makes the execution slower, so I think since we don't implement linker relaxation for AVR, we should not do the jmp/call rewriting as well.

My change is measurable,

1. short jmp/call cost 1 less tick than long jmp/call
2. the nop costs 1 tick.

So the rewriting of call has neither improvement nor regression, since the nop is always executed, so there is no tick/space change.

But the rewriting of jmp does have improvement on time, since the nop is no longer executed, one tick can be saved.

[benshi001]

Here is the cost of short jmp

And this is the cost of long jmp

[benshi001]

Please refer to gun-ld,

https://sourceware.org/git/?p=binutils-gdb.git;a=blob;f=bfd/elf32-avr.c;h=702719136d09acbc8c98ec49ab8129d0f33fffa8;hb=HEAD#l2721
https://sourceware.org/git/?p=binutils-gdb.git;a=blob;f=bfd/elf32-avr.c;h=702719136d09acbc8c98ec49ab8129d0f33fffa8;hb=HEAD#l2738

gnu-ld also replace JMP to a pair of RJMP+NOP, since it does save one CPU cycle, because the NOP is never executed, it is just a padding word.

[benshi001]

ping ...

1. relax long jump to short jump + nop does can save 1 CPU cycle;
2. GNU-ld also does this optimization, as

https://sourceware.org/git/?p=binutils-gdb.git;a=blob;f=bfd/elf32-avr.c;h=702719136d09acbc8c98ec49ab8129d0f33fffa8;hb=HEAD#l2721
https://sourceware.org/git/?p=binutils-gdb.git;a=blob;f=bfd/elf32-avr.c;h=702719136d09acbc8c98ec49ab8129d0f33fffa8;hb=HEAD#l2738

[MaskRay]

Increasing the number of instructions, while it may improve performance for some processors (any number?), doesn't look right...

[benshi001]

In D146216#4263682, @MaskRay wrote:

Increasing the number of instructions, while it may improve performance for some processors (any number?), doesn't look right...

1. On all devices, long jump costs 4 bytes, and short jump + nop also cost four bytes, there is no space expansion or shrink.
2. As AVR instruction manual indicates, short jump costs 2 cycles, while long jump costs 3 cycles. So one CPU cycle is saved.

For example,

long jump _foo ; this is an unconditional jump which costs 4 bytes and 3 cpu cycle
...
short jump _foo; this is an unconditional jump which costs 2 bytes and 2 cpu cycle 
nop            ; this `nop` is just for padding the space of the replaced `long jump` , it is never executed.

In the above contrast, the nop is never executed, so short jump + nop does not waste any space, but saves one CPU cycle.

[benshi001]

lld/ELF/Arch/AVR.cpp

258

This NOP is just for padding, actually we need not handle it and left it unchanged. (However this will make llvm-objdump show an <unknown>)

[benshi001]

I can give up this patch. At least it is a tiny optimization, and have little affect on lld. But can my another patch https://reviews.llvm.org/D147364 be reviewd and accepted ?
R_AVR_LO8_LDI_GS/R_AVR_HI8_LDI_GS are still missing in lld, with them implemented, lld will be fully functional as GNU-ld, and can finally replace GNU-ld. My aim of clang+llvm+compilerrt+lld fully replace gnu toolchain, can be achieved. I really appreciate for that !

lld/ELF/Arch/AVR.cpp

 //   objcopy -O binary --only-section=.text foo output.bin
 //
 // Note that the current AVR support is very preliminary so you can't
 // link any useful program yet, though.
 //
 //===----------------------------------------------------------------------===//
 
 #include "InputFiles.h"
+#include "OutputSections.h"
 #include "Symbols.h"
 #include "Target.h"
 #include "lld/Common/ErrorHandler.h"
 #include "llvm/BinaryFormat/ELF.h"
 #include "llvm/Support/Endian.h"
 
 using namespace llvm;
 using namespace llvm::object;
 using namespace llvm::support::endian;
 using namespace llvm::ELF;
 using namespace lld;
 using namespace lld::elf;
 
 namespace {
 class AVR final : public TargetInfo {
 public:
   uint32_t calcEFlags() const override;
   RelExpr getRelExpr(RelType type, const Symbol &s,
                      const uint8_t *loc) const override;
   void relocate(uint8_t *loc, const Relocation &rel,
                 uint64_t val) const override;
+  void relocateAlloc(InputSectionBase &sec, uint8_t *buf) const override;
+  bool tryRelaxLongJumpCall(uint8_t *loc, uint64_t callAddr,
+                            uint64_t destAddr) const;
 };
 } // namespace
 
 RelExpr AVR::getRelExpr(RelType type, const Symbol &s,
                         const uint8_t *loc) const {
   switch (type) {
   case R_AVR_6:
   case R_AVR_6_ADIW:
TargetInfo *elf::getAVRTargetInfo() {
   static AVR target;
   return ⌖
 }
 
 static uint32_t getEFlags(InputFile *file) {
   return cast<ObjFile<ELF32LE>>(file)->getObj().getHeader().e_flags;
 }
 
+// Try to relax
+//     jmp _foo   ; 4-byte instruction
+// to
+//     rjmp _foo  ; 2-byte instruction
+//     nop        ; 2-byte instruction
+bool AVR::tryRelaxLongJumpCall(uint8_t *loc, uint64_t callAddr,
+                               uint64_t destAddr) const {
+  // The offset must be in range [-4094, 4096].
+  const int64_t Off = destAddr - callAddr;
+  if (Off < -4094 || Off > 4096)
+    return false;
+
+  // Set the first instruction to RCALL/RJMP.
+  const uint16_t OffCode = static_cast<uint64_t>(Off - 2) >> 1;
+  const uint16_t OpCode = read16le(loc) == 0x940c ? 0xc000 : 0xd000;
+  write16le(loc, OpCode | (OffCode & 0xfff));
+
+  // Set the second instruction to NOP.
+  write16le(loc + 2, 0);
+
+  return true;
+}
+
+void AVR::relocateAlloc(InputSectionBase &sec, uint8_t *buf) const {
+  uint64_t secAddr = sec.getOutputSection()->addr;
+  if (auto *s = dyn_cast<InputSection>(&sec))
+    secAddr += s->outSecOff;
+  for (const Relocation &rel : sec.relocs()) {
+    uint8_t *loc = buf + rel.offset;
+    const uint64_t val = SignExtend64(
+        sec.getRelocTargetVA(sec.file, rel.type, rel.addend,
+                             secAddr + rel.offset, *rel.sym, rel.expr),
+        32);
+
+    switch (rel.type) {
+    // Try to relax a long jump/call (a 4-byte instruction) to a pair of
+    // short jump/call (a 2-byte instruction) and nop (a 2-byte instruction).
+    case R_AVR_CALL:
+      if (config->relax &&
+          (getEFlags(ctx.objectFiles[0]) & EF_AVR_LINKRELAX_PREPARED) != 0)
+        if (tryRelaxLongJumpCall(loc, secAddr + rel.offset, val))
+          continue;
+      [[fallthrough]];
+
+    default:
+      relocate(loc, rel, val);
+      break;
+    }
+  }
+}
+
 uint32_t AVR::calcEFlags() const {
   assert(!ctx.objectFiles.empty());
 
   uint32_t flags = getEFlags(ctx.objectFiles[0]);
   bool hasLinkRelaxFlag = flags & EF_AVR_LINKRELAX_PREPARED;
 
   for (InputFile *f : ArrayRef(ctx.objectFiles).slice(1)) {
     uint32_t objFlags = getEFlags(f);

lld/test/ELF/avr-relax.s

+# REQUIRES: avr
+# RUN: llvm-mc -filetype=obj -triple=avr -mcpu=atmega328p %s -o %t.o
+# RUN: ld.lld %t.o -o %t0.exe -Ttext=0 --no-relax
+# RUN: llvm-objdump -d %t0.exe --mcpu=atmega328 | FileCheck %s --check-prefix=NORELAX
+# RUN: ld.lld %t.o -o %t1.exe -Ttext=0
+# RUN: llvm-objdump -d %t1.exe --mcpu=atmega328 | FileCheck %s --check-prefix=RELAX
+
+main:
+  call foo
+  rcall foo
+foo:
+  jmp foo
+  rjmp foo
+
+la0:
+  jmp la1
+  .zero 4096
+la1:
+  jmp la0
+
+# NORELAX:      <main>:
+# NORELAX-NEXT:   0: 0e 94 03 00   call  0x6
+# NORELAX-NEXT:   4: 00 d0         rcall .+0
+# NORELAX:      <foo>:
+# NORELAX-NEXT:   6: 0c 94 03 00   jmp   0x6
+# NORELAX-NEXT:   a: fd cf         rjmp  .-6
+
+# RELAX:        <main>:
+# RELAX-NEXT:     0: 02 d0         rcall .+4
+# RELAX-NEXT:     2: 00 00         nop
+# RELAX-NEXT:     4: 00 d0         rcall .+0
+# RELAX:        <foo>:
+# RELAX-NEXT:     6: ff cf         rjmp  .-2
+# RELAX-NEXT:     8: 00 00         nop
+# RELAX-NEXT:     a: fd cf         rjmp  .-6
+# RELAX:        <la0>:
+# RELAX-NEXT:     c: 0c 94 08 08   jmp   0x1010
+# RELAX:        <la1>:
+# RELAX-NEXT:  1010: 0c 94 06 00   jmp   0xc

lld/test/ELF/basic-avr.s

-# REQUIRES: avr
-# RUN: llvm-mc -filetype=obj -triple=avr-unknown-linux -mcpu=atmega328p %s -o %t.o
-# RUN: ld.lld %t.o -o %t.exe -Ttext=0
-# RUN: llvm-objdump -d %t.exe | FileCheck %s
+# RUN: llvm-mc -filetype=obj -triple=avr -mcpu=atmega328p %s -o %t.o
+# RUN: ld.lld %t.o -o %t.exe -Ttext=0 --no-relax
+# RUN: llvm-objdump -d %t.exe --mcpu=atmega328 | FileCheck %s
 
 main:
   call foo
 foo:
   jmp foo
 
 # CHECK:      <main>:
-# CHECK-NEXT:   0: 0e 94 02 00 <unknown>
+# CHECK-NEXT:   0: 0e 94 02 00   call  0x4
 # CHECK:      <foo>:
-# CHECK-NEXT:   4: 0c 94 02 00 <unknown>
+# CHECK-NEXT:   4: 0c 94 02 00   jmp   0x4