RISC-V linker relaxation in lld
2022-7-10 15:0:0 Author: maskray.me(查看原文) 阅读量:29 收藏

On 2022-07-07, I added a RISC-V linker relaxation framework in ld.lld and implemented R_RISCV_ALIGN/R_RISCV_CALL/R_RISCV_CALL_PLT relaxation. The changes will be included in the next llvm-project release 15.0.0. This post describes the implementation.

See The dark side of RISC-V linker relaxation for more information about RISC-V linker relaxation.

ld.lld performs these steps (simplified):

  • Parse command line options
  • Find and scan input files (.o, .so, .a), interleaved with symbol resolution
  • Call LLVM LTO to get ELF object files
  • Global transforms (section based garbage collection, identical code folding, etc)
  • Create synthetic sections
  • Map input sections and synthetic (linker-generated) sections into output sections
  • Scan relocations
  • Finalize synthetic sections
  • Layout (addresses, thunks, SHT_RELR, symbol assignments)
  • Assign file offsets
  • Write header and sections

Problems

Relocation scanning

Relocation scanning makes dynamic relocation decisions and determines the sizes of .got, .got.plt, .plt, .rela.dyn, and .relr.dyn sections. Their address and size changes will affect subsequent sections and sections using certain linker script features. The one-pass relocation scanning scheme is tied to the whole ld.lld design and is difficult to change. Relocation scanning takes time and we want to perform it only when necessary.

Linker relaxation may make input sections smaller and nullify the current section layout. For a call code sequence, if the size decrease makes the destination closer enough to the relocation location, we need to rewrite the code sequence into a shorter form. This change may have a cascading effect and trigger further relaxation. E.g. in the following diagram consisting of three input sections, if call x (a pseudo instruction which expands to 8 bytes) in section B is shortened, it may trigger call relaxation in section A.

1
A[... call c; ...] -- B[... call x; ...] -- C[c: ...]

Symbol values

The changed section layout may change symbol values. It is rare but an output section address can use a symbol value. In the following linker script example, the size change of .mid will change the address of .high.

1
2
3
SECTIONS {
  .mid 0x10800 : { mid_start = .; *(.mid); mid_end = .; }
  .high 0x110000+(mid_end-mid_start) : { *(.high) }

Design

The main idea is to add linker relaxation to the layout phase.

  • Scan relocations
  • Finalize synthetic sections
  • Layout (relaxation, addresses, thunks, SHT_RELR, symbol assignments)
  • Assign file offsets

We assume that previous passes have fixed the sizes of dynamic linking related sections Another relocation scanning pass is added as part of relaxation to determinate:

  • for each relocation location, the replacement relocation type, the rewritten code sequence, and the number of bytes to delete
  • the size of each input code section
  • st_value and st_size for each symbol defined relative to the section

In some uncommon cases an input section may expand in a later iteration. If we choose to shrink sections at the end of one iteration, the expansion will be difficult to handle. My idea is that the section size shrink and code sequence rewrites need to be postponed after the iteration fixed point is reached.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template <class ELFT> void Writer<ELFT>::finalizeAddressDependentContent() {
  ...
  uint32_t pass = 0;
  for (;;) {
    Create thunks or call relaxOnce;
    ++pass;

    Report "not converged" if pass is too large;

    Update address-dependent sections;
    Assign addresses to sections and symbols;
  }
  if (!config->relocatable && config->emachine == EM_RISCV)
    riscvFinalizeRelax(pass);
  ...
}

Two function calls are added to finalizeAddressDependentContent: relaxOnce and riscvFinalizeRelax. The RISC-V port implements relaxOnce which calls relax on all input code sections.

1
2
3
4
5
6
7
8
9
10
11
bool RISCV::relaxOnce(int pass) const {
  ...
  bool changed = false;
  for (OutputSection *osec : outputSections) {
    if (!(osec->flags & SHF_EXECINSTR))
      continue;
    for (InputSection *sec : getInputSections(*osec, storage))
      changed |= relax(*sec);
  }
  return changed;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
static bool relax(InputSection &sec) {
  Restore original st_value for symbols relative to this section.

  std::fill_n(aux.relocTypes.get(), sec.relocations.size(), R_RISCV_NONE);
  aux.writes.clear();
  for (auto it : llvm::enumerate(sec.relocations)) {
    Relocation &r = it.value();
    const size_t i = it.index();
    const uint64_t loc = secAddr + r.offset - delta;
    uint32_t &cur = aux.relocDeltas[i], remove = 0;
    switch (r.type) {
    case R_RISCV_ALIGN: {
      remove = the number of bytes to delete;
      break;
    }
    case R_RISCV_CALL:
    case R_RISCV_CALL_PLT:
      if (i + 1 != sec.relocations.size() &&
          sec.relocations[i + 1].type == R_RISCV_RELAX)
        relaxCall(sec, i, loc, r, remove);
      break;
    
    }

    Update symbol st_value/st_size according to symbol anchors; 

    delta += remove;
    if (delta != cur) {
      cur = delta;
      changed = true;
    }
  }

  Update trailing symbol anchors;

  sec.bytesDropped = delta;
  return changed;
}

relax iterates over non-resolved relocations for this input section and sets remove to the number of bytes to delete. delta is the accumulated number of bytes to delete. It is stored in aux.relocDeltas[i] for processing in riscvFinalizeRelax.

Symbol anchors

Updating st_value and st_size for each symbol defined relative to the section uses a neat technique.

1
2
3
4
  ...
a:
  .balign 16  # R_RISCV_ALIGN(r_addend=12)
b:

In this example, there is an R_RISCV_ALIGN relocation at the point of the .balign directive. Its offset equals of symbol a's st_value. If some bytes preceding a are deleted, a's st_value needs to be decreased by that number of bytes. b has a larger st_value and its st_value needs to additionally take into account the R_RISCV_ALIGN relaxation.

To compute all st_value of symbols relative to the current input section, we maintain two sorted lists: (a) relaxable relocations (b) st_value. For each symbol, find the relocation with the largest r_offset which is smaller than the symbol's st_value, then decrease st_value by r_offset. This task is like the merge function of merge sort.

For st_size, we try to determine the final st_value+st_size, then decrease the sum by the final st_value to compute the final st_size. All st_value+st_size values can be computed in a way similar to st_value. In the implementation, I just place all initial st_value and st_value+st_size values in one sorted list. Both are indicated by a SymbolAnchor object.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct SymbolAnchor {
  uint64_t offset;
  Defined *d;
  bool end; 
};

    if (remove) {
      for (; sa.size() && sa[0].offset <= r.offset; sa = sa.slice(1)) {
        if (sa[0].end)
          sa[0].d->size = sa[0].offset - delta - sa[0].d->value;
        else
          sa[0].d->value -= delta;
      }
    }

Since we use the decrement amount (sa[0].d->value -= delta;), when starting the next iteration, we need to restore the original st_value.

Finalize relaxation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
void elf::riscvFinalizeRelax(int passes) {
  ...
  for (OutputSection *osec : outputSections) {
    if (!(osec->flags & SHF_EXECINSTR))
      continue;
    for (InputSection *sec : getInputSections(*osec, storage)) {
      RISCVRelaxAux &aux = *sec->relaxAux;
      if (!aux.relocDeltas)
        continue;

      Allocate space for the new section content to `p`;
      sec->rawData = makeArrayRef(p, newSize);

      
      
      for (size_t i = 0, e = rels.size(); i != e; ++i) {
        uint32_t remove = aux.relocDeltas[i] - delta;
        delta = aux.relocDeltas[i];
        if (remove == 0)
          continue;

        
        const Relocation &r = rels[i];
        uint64_t size = r.offset - offset;
        memcpy(p, old.data() + offset, size);
        p += size;

        
        
        
        
        int64_t skip = 0;
        if (r.type == R_RISCV_ALIGN) {
          if (remove % 4 != 0) {
            skip = r.addend - remove;
            Rewrite `skip` bytes with nop and an optional trailing c.nop;
          }
        } else if (RelType newType = aux.relocTypes[i]) {
          Rewrite code sequence for a relaxable relocation;
        }

        p += skip;
        offset = r.offset + skip + remove;
      }
      memcpy(p, old.data() + offset, old.size() - offset);

      Subtract the previous relocDeltas value from the relocation offset.
      For a pair of R_RISCV_CALL/R_RISCV_RELAX with the same offset, decrease
      their r_offset by the same delta.
    }
    memcpy(p, old.data() + offset, old.size() - offset);
  }
}

For each input code section, We iterate over its non-resolved relocations. For an R_RISCV_ALIGN associated with some bytes to delete, we copy all content from the previous location to r_offset, then skip some bytes for the next copy. 

1
2
3
4
...         # Copy all content from the previous location to r_offset
.balign 8  # R_RISCV_ALIGN(r_addend=6)
# A prefix of the NOPs may be skipped for the next memcpy
addi a0, a0, 1

Say we need to delete 2 bytes. If we use [] to indicate the copied bytes, the current and the next copy patterns will look like: 

1
2
3
4
5
old: ...]  NOP  NOP [NOP  NOP  NOP  NOP  ADDI ADDI ADDI ADDI ...]
old:               next copy

new: ...] [NOP  NOP  NOP  NOP  ADDI ADDI ADDI ADDI ...]
new:

Let's check a call relaxation case. The call pseudo instruction expands to a pair of auipc and jalr.

If auipc+jalr can be relaxed to a 4-byte jal, we ignore auipc, replace jalr with jal, and increment p and offset so that next memcpy will start copying from the first byte after jalr. The rewritten instruction starts at the first byte indicated by skip=4. 

1
2
3
4
old: ...] AUIPC AUIPC AUIPC AUIPC JALR JALR JALR JALR [.........]
          remove=4                skip=4               next copy

new: ...] JAL   JAL   JAL   JAL   [.........]

Here is a demonstration for a tail pseudo instruction which is relaxed to c.j. 

1
2
3
4
old: ...] AUIPC AUIPC AUIPC AUIPC JALR JALR JALR JALR [.........]
          remove=6                          skip=2     next copy

new: ...] C.J   C.J   [.........]

Relaxation schemes

Alignment relaxation

With 3 values we can compute the address of the relocation location: secAddr + r.offset - delta. delta is the asscumulated number of bytes to delete. It is subtracted from the original r_offset value.

The alignment is PowerOf2Ceil(r.addend + 2). The expected location after alignment is (loc + align - 1) & -align and therefore loc + r.addend - ((loc + align - 1) & -align) is the number of bytes to delete.

Call relaxation

The new instruction has 3 choices:

  • c.j: RVC and displacement is representable as an int12
  • c.jal: RV32C and displacement is representable as an int12
  • jal: displacement is representable as an int21

The first two need to delete 6 bytes and rewrite 2 bytes while the third needs to delete 4 bytes and rewrite 4 bytes.

Local-exec TLS relaxation

https://reviews.llvm.org/D129425

The 3-instruction code sequence can be relaxed to one instruction if st_value(x) < 2048 (i.e. hi20(x) == 0): 

1
2
3
4
5
6
7
8
9
10
# R_RISCV_TPREL_HI20, R_RISCV_RELAX
lui rd, %tprel_hi(x)
# R_RISCV_TPREL_ADD, R_RISCV_RELAX
add rd, rd, tp, %tprel_add(x)
# (R_RISCV_TPREL_LO12_I || R_RISCV_TPREL_LO12_S), R_RISCV_RELAX
addi rd, rd, %tprel_lo(x) || sw rs, %tprel(x)(rd)

=>

addi rd, tp, st_value(x) || sw rs, st_value(x)(rd)

lui relaxation

If ld.lld implements this, we will need quite a bit of overhead.

Relaxation against the Global Pointer

See "Relaxing Against the Global Pointer" on https://www.sifive.com/blog/all-aboard-part-3-linker-relaxation-in-riscv-toolchain.

I am of the opinion that this choice is short-sighted, so I created https://github.com/riscv-non-isa/riscv-elf-psabi-doc/issues/298 which was soon closed. However, I don't receive strong arguments supporting this scheme. I wish that interested users help me by making some measurement.


文章来源: https://maskray.me/blog/2022-07-10-riscv-linker-relaxation-in-lld
如有侵权请联系:admin#unsafe.sh