Bug in the ICF in lld

[mraleph]

lld seems to apply ICF to two pieces of code ignoring relocations, e.g.

#include <cstdio>

struct B {
  virtual const char* getStr() {
      return "one string";
  }
};

struct C : public B {
  virtual const char* getStr() {
    return "another string";
  }
};

[[clang::noinline]] static int getInt() {
    int value;
    asm("mov $0x7, %0" : "=r" (value));
    return value;
}

int main(int argc, char* argv[]) {
  B* b = argc == 2 ? new C() : new B();
  printf("%s %d\n", b->getStr(), getInt());
  return 0;
}

When compiled like so:

$ clang++ -O3 -o /tmp/test -m32 -ffunction-sections -fdata-sections -Wl,--icf=all /tmp/test.cc

with a specific version of clang:

Fuchsia clang version 15.0.0 (https://llvm.googlesource.com/a/llvm-project c2592c374e469f343ecea82d6728609650924259)
Target: x86_64-unknown-linux-gnu

Resulting binary will SEGFAULT because B::getStr got folded with getInt and printf is trying to print 0x7 as a string:

* thread #1, name = 'test', stop reason = signal SIGSEGV: invalid address (fault address: 0x7)
    frame #0: 0xf7d4fb76 libc.so.6`___lldb_unnamed_symbol3153 + 38
libc.so.6`___lldb_unnamed_symbol3153:
->  0xf7d4fb76 <+38>: cmp    byte ptr [eax], dh
    0xf7d4fb78 <+40>: je     0xf7d4fc06                ; <+182>
    0xf7d4fb7e <+46>: inc    eax
    0xf7d4fb7f <+47>: xor    edx, edx
(lldb) bt
* thread #1, name = 'test', stop reason = signal SIGSEGV: invalid address (fault address: 0x7)
  * frame #0: 0xf7d4fb76 libc.so.6`___lldb_unnamed_symbol3153 + 38
    frame #1: 0xf7d12f39 libc.so.6`___lldb_unnamed_symbol2903 + 7145
    frame #2: 0xf7d00f35 libc.so.6`_IO_printf + 37
    frame #3: 0x0040ba99 test`main + 73
    frame #4: 0xf7ccb905 libc.so.6`__libc_start_main + 229
    frame #5: 0x0040b922 test`_start + 50

0x7 in getInt is selected so that it would match B::getStr code. If it does not crash for you - just tweak to match it by checking B::getStr:

$ buildtools/linux-x64/clang/bin/clang++ -O3 -c -o /tmp/test.o -m32 -ffunction-sections -fdata-sections /tmp/test.cc
$ objdump -rD /tmp/test.o | grep -A2 \<_ZN1B6getStrEv
00000000 <_ZN1B6getStrEv>:
   0:   b8 07 00 00 00          mov    $0x7,%eax
                        1: R_386_32     .rodata.str1.1

I have not tried debugging it but from my reading of code the problem is here:

bool ICF<ELFT>::equalsConstant(const InputSection *a, const InputSection *b) {
  // ...
  const RelsOrRelas<ELFT> ra = a->template relsOrRelas<ELFT>();
  const RelsOrRelas<ELFT> rb = b->template relsOrRelas<ELFT>();
  return ra.areRelocsRel() ? constantEq(a, ra.rels, b, rb.rels)
                           : constantEq(a, ra.relas, b, rb.relas);

Here ra.areRelocsRel() is defined as ra.rels.size(). This means if ra has no relocations whatsoever but rb has some rels we will end up comparing ra.relas and rb.relas by mistake - both of which are empty and then we will end up merging ra and rb. Instead we should have compared ra.rels (empty) to non-empty rb.rels.

/cc @MaskRay

[llvmbot]

@llvm/issue-subscribers-lld-elf

[MaskRay]

/cherry-pick 686cff1

[llvmbot]

/branch llvm/llvm-project-release-prs/issue57693

[llvmbot]

/pull-request llvm/llvm-project-release-prs#320