[ELF] Make LinkerScript::assignAddresses iterative

PR42990. For `SECTIONS { b = a; . = 0xff00 + (a >> 8); a = .; }`,
we currently set st_value(a)=0xff00 while st_value(b)=0xffff.

The following call tree demonstrates the problem:

```
link<ELF64LE>(Args);
  Script->declareSymbols(); // insert a and b as absolute Defined
  Writer<ELFT>().run();
    Script->processSectionCommands();
      addSymbol(cmd);       // a and b are re-inserted. LinkerScript::getSymbolValue
                            // is lazily called by subsequent evaluation
    finalizeSections();
      forEachRelSec(scanRelocations<ELFT>);
        processRelocAux     // another problem PR42506, not affected by this patch
      finalizeAddressDependentContent(); // loop executed once
        script->assignAddresses(); // a = 0, b = 0xff00
    script->assignAddresses(); // a = 0xff00, _end = 0xffff
```

We need another assignAddresses() to finalize the value of `a`.

This patch

1) modifies assignAddress() to track the original section/value of each
  symbol and return a symbol whose section/value has changed.
2) moves the post-finalizeSections assignAddress() inside the loop
  of finalizeAddressDependentContent() and makes it iterative.
  Symbol assignment may not converge so we make a few attempts before
  bailing out.

Note, assignAddresses() must be called at least twice. The penultimate
call finalized section addresses while the last finalized symbol values.
It is somewhat obscure and there was no comment.
linkerscript/addr-zero.test tests this.

Reviewed By: ruiu

Differential Revision: https://reviews.llvm.org/D66279

llvm-svn: 369889

3 files changed, 73 insertions, 0 deletions

diff --git a/lld/test/ELF/linkerscript/symbol-assign-many-passes.test b/lld/test/ELF/linkerscript/symbol-assign-many-passes.test
new file mode 100644
index 00000000000..7e2d2d9ace8
--- /dev/null
+++ b/lld/test/ELF/linkerscript/symbol-assign-many-passes.test
@@ -0,0 +1,25 @@
+# REQUIRES: aarch64, x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64 /dev/null -o %t.o
+# RUN: ld.lld %t.o -T %s -o %t
+# RUN: llvm-nm %t | FileCheck %s
+
+## AArch64 needs thunks and has different address finalization process, so test
+## it as well.
+# RUN: llvm-mc -filetype=obj -triple=aarch64 /dev/null -o %t.o
+# RUN: ld.lld %t.o -T %s -o %t
+# RUN: llvm-nm %t | FileCheck %s
+
+# CHECK: 0000000000001004 T a
+# CHECK: 0000000000001003 T b
+# CHECK: 0000000000001002 T c
+# CHECK: 0000000000001001 T d
+# CHECK: 0000000000001000 T e
+
+SECTIONS {
+  . = 0x1000;
+  a = b + 1;
+  b = c + 1;
+  c = d + 1;
+  d = e + 1;
+  e = .;
+}
diff --git a/lld/test/ELF/linkerscript/symbol-assign-many-passes2.test b/lld/test/ELF/linkerscript/symbol-assign-many-passes2.test
new file mode 100644
index 00000000000..b8a0624ac30
--- /dev/null
+++ b/lld/test/ELF/linkerscript/symbol-assign-many-passes2.test
@@ -0,0 +1,28 @@
+# REQUIRES: arm
+# RUN: llvm-mc -arm-add-build-attributes -filetype=obj -triple=armv7a-linux-gnueabihf %S/../arm-thunk-many-passes.s -o %t.o
+# RUN: ld.lld %t.o -T %s -o %t
+# RUN: llvm-nm %t | FileCheck %s
+
+## arm-thunk-many-passes.s is worst case case of thunk generation that takes 9
+## passes to converge. It takes a few more passes to make symbol assignment
+## converge. Test that
+## 1. we don't error that "thunk creation not converged".
+## 2. we check convergence of symbols defined in an output section descriptor.
+
+# CHECK: 01011050 T a
+# CHECK: 0101104f T b
+# CHECK: 0101104e T c
+# CHECK: 0101104d T d
+# CHECK: 0101104c T e
+
+SECTIONS {
+  . = SIZEOF_HEADERS;
+  .text 0x00011000 : {
+    a = b + 1;
+    b = c + 1;
+    c = d + 1;
+    d = e + 1;
+    *(.text);
+  }
+  e = .;
+}
diff --git a/lld/test/ELF/linkerscript/symbol-assign-not-converge.test b/lld/test/ELF/linkerscript/symbol-assign-not-converge.test
new file mode 100644
index 00000000000..38f40640d92
--- /dev/null
+++ b/lld/test/ELF/linkerscript/symbol-assign-not-converge.test
@@ -0,0 +1,20 @@
+# REQUIRES: aarch64, x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64 /dev/null -o %t.o
+# RUN: not ld.lld %t.o -T %s -o /dev/null 2>&1 | FileCheck %s
+
+## AArch64 needs thunks and has different address finalization process, so test
+## it as well.
+# RUN: llvm-mc -filetype=obj -triple=aarch64 /dev/null -o %t.o
+# RUN: not ld.lld %t.o -T %s -o /dev/null 2>&1 | FileCheck %s
+
+# CHECK: error: assignment to symbol a does not converge
+
+SECTIONS {
+  . = 0x1000;
+  a = b;
+  b = c;
+  c = d;
+  d = e;
+  e = f;
+  f = .;
+}