[lld][ELF] Add LOG2CEIL builtin ldscript function

[irichter]

Summary

This patch adds support for the LOG2CEIL builtin function in linker scripts: https://sourceware.org/binutils/docs/ld/Builtin-Functions.html#index-LOG2CEIL_0028exp_0029

As documented for LD, and to keep compatibility, LOG2CEIL(0) returns 0 (not -inf).

The test vectors are somewhat arbitrary. We check minimum values (0-4); middle values (2^32, and 2^32+1); and the maximum value (2^64-1).

The checks for LOG2CEIL explicitly use full 64-bit values (16 hex digits). This is needed to properly verify that -inf and other interesting results aren't returned. (For some reason, all other tests in operators.test use only 14 digits.)

[irichter]

Fixed improper results for LOG2CEIL(0), updated tests to properly find the error

[MaskRay]

We don't arbitrarily add GNU ld linker script support. We add them on an as-needed basis if its functionality cannot easily replaced by other mechanism. For LOG2CEIL, it is difficult for me to think about its use cases. Can you elaborate?

[irichter]

In D84054#2161252, @MaskRay wrote:

We don't arbitrarily add GNU ld linker script support. We add them on an as-needed basis if its functionality cannot easily replaced by other mechanism.

Ah, I was following https://lld.llvm.org/ELF/linker_script.html, so I assumed that it was a bug, since the lld implementation does not agree with the ld manual, and there is no mention on the page of missing builtin functions.

For LOG2CEIL, it is difficult for me to think about its use cases. Can you elaborate?

I'm working on bare-metal MIPS, and need to generate an ELF binary loaded into memory at a fixed location by the bootloader. I need to use wired TLB entries to have the section appear at a specific VMA. To avoid using more than one TLB entry for the mapping, I use a larger-than-normal page size for that entry. (My platform's MIPS implementation allows variably-large page sizes, specifically even powers of 2, from 4k through 256m. Each TLB entry can use its own page size, so regular mappings can continue to use 4k pages, while large mappings can use tailored sizes to keep the total number of TLB entries required low.) LOG2CEIL allows me to have lld compute the desired page size, allowing me to determine the proper alignment for the following sections, ensuring that they will not be covered by the remapping.

Potential workarounds to avoid LOG2CEIL:

• Hard-code an alignment believed to be larger than possibly possibly necessary, wasting memory if the chosen alignment is larger than necessary; and checking at runtime to ensure that the alignment was sufficient
• Manually set an alignment in the linkerscript; review the output ELF after every link (possibly manually), and modify the script if necessary to fix the alignment
• Use two linker passes, running a checker to analyze the necessary alignment based on the output of the first linker pass, hard-coding the required alignment into the linker script for the second pass

[MaskRay]

I assume you will use 1 << LOG2CEIL(address) to round up to a power of 2. It is indeed cumbersome to work around it. The function should be fine.

lld/ELF/ScriptParser.cpp

1336

Add a comment that LOG2CEIL(0) is defined to be 0.

[grimar]

Yeah, it should be fine to support it. Added a suggestion about test.
(Also, please do not upload patches without a context, see https://llvm.org/docs/Phabricator.html#requesting-a-review-via-the-web-interface)

lld/test/ELF/linkerscript/operators.test

48

I think I understand why 0, 1, 2, 3, 4 values are useful to test,
but I do not see why 0x0ff/0x100/0x1ff values are?
We shouldn't just blindly copy anything from GNU.

I'd keep the min value (0), [1-4] and add a test for the max possible value (0xffffffffffffffff) probably.

[irichter]

Added comment to source noting that LOG2CEIL(0) returns 0.

[irichter]

In D84054#2168766, @grimar wrote:

Yeah, it should be fine to support it. Added a suggestion about test.

The GNU implementation uses a while loop to compute the value directly, so I somewhat understand why they chose those values.

Since I'm using the builtin (C++) functions, I'd be more worried about floating-point weirdness causing inaccuracies. (I don't think that this should be an issue, since any rounding should be in less-significant bits that won't change the final result, but I'm not 100% sure about this.) I could test every transition (e.g. 0x0f, 0x10, 0x1f, 0x20, 0x3f, 0x40, ...), but that'll be >100 tests. I took a quick look at the libc and libcxx tests for log2, but those seem much more detailed than I'd expect to find in lld.

What do you think would be sufficient?

[irichter]

Fix build issue on Windows (explicitly cast to uint64_t, don't rely on UL suffix to be equivalent)

[MaskRay]

lld/ELF/ScriptParser.cpp

1340

Use llvm::Log2_64_Ceil (llvm/Support/mathExtras.h)

Use //

[grimar]

In D84054#2169708, @irichter wrote:

I could test every transition (e.g. 0x0f, 0x10, 0x1f, 0x20, 0x3f, 0x40, ...), but that'll be >100 tests. I took a quick look at the libc and libcxx tests for log2, but those seem much more detailed than I'd expect to find in lld.

What do you think would be sufficient?

I do not think we should focus too much on this in LLD test. I think just a few values should be fine. E.g 0, 1, 2, 3, 4, 65535, 65536, uint64(-1)
@MaskRay, what do you think?

[MaskRay]

In D84054#2171513, @grimar wrote:

In D84054#2169708, @irichter wrote:

I could test every transition (e.g. 0x0f, 0x10, 0x1f, 0x20, 0x3f, 0x40, ...), but that'll be >100 tests. I took a quick look at the libc and libcxx tests for log2, but those seem much more detailed than I'd expect to find in lld.

What do you think would be sufficient?

I do not think we should focus too much on this in LLD test. I think just a few values should be fine. E.g 0, 1, 2, 3, 4, 65535, 65536, uint64(-1)
@MaskRay, what do you think?

Agree. The job is llvm::Log2_64_Ceil's unit tests.

[irichter]

In D84054#2170591, @MaskRay wrote:

Use llvm::Log2_64_Ceil (llvm/Support/mathExtras.h)

Is it preferred coding style to include the namespace in a function call, when the file already has the relevant using namespace statement? Specifically, should I be using an unqualified return Log2_64_Ceil(...);, or a qualified return llvm::Log2_64_Ceil(...); call?

[irichter]

In D84054#2171513, @grimar wrote:

I do not think we should focus too much on this in LLD test. I think just a few values should be fine. E.g 0, 1, 2, 3, 4, 65535, 65536, uint64(-1)
@MaskRay, what do you think?

I see that you suggest testing the upper bounds for 16-bits (UINT16_MAX and UINT16_MAX+1, both which should return 16). Is there any particular reason for checking this at this boundary? Why not UINT32_MAX,UINT32_MAX+1 (either instead of UINT16_MAX, or in addition thereto)? Should I also be testing UINT16_MAX+2 (should return 17) and/or UINT32_MAX+2 (should return 33)?

[grimar]

In D84054#2172962, @irichter wrote:

In D84054#2171513, @grimar wrote:

I do not think we should focus too much on this in LLD test. I think just a few values should be fine. E.g 0, 1, 2, 3, 4, 65535, 65536, uint64(-1)
@MaskRay, what do you think?

I see that you suggest testing the upper bounds for 16-bits (UINT16_MAX and UINT16_MAX+1, both which should return 16). Is there any particular reason for checking this at this boundary? Why not UINT32_MAX,UINT32_MAX+1 (either instead of UINT16_MAX, or in addition thereto)? Should I also be testing UINT16_MAX+2 (should return 17) and/or UINT32_MAX+2 (should return 33)?

I was thinking about just showing that we produce an expected result for some set of arbitrary values.
My range contains 0 (min possible value) + a few values at start to demonstrate the behavior, 2 arbitrary values somewhere in the middle just in case to confirm the behavior and the max possible value.

Regarding UINT16_MAX and UINT16_MAX+1, it was my mistake, sorry, UINT16_MAX+1 and UINT16_MAX+2, should be better to show the different result.
I also do not think it is important to stick to UINT16_MAX instead of UINT32_MAX, the idea was to test values that are not at the start nor the end of a range. So any values can be used I think.

[grimar]

In D84054#2172897, @irichter wrote:

In D84054#2170591, @MaskRay wrote:

Use llvm::Log2_64_Ceil (llvm/Support/mathExtras.h)

Is it preferred coding style to include the namespace in a function call, when the file already has the relevant using namespace statement? Specifically, should I be using an unqualified return Log2_64_Ceil(...);, or a qualified return llvm::Log2_64_Ceil(...); call?

Usually we use llvm:: prefix for stl helpers/analogs. E.g llvm::sort. For regular funtions llvm:: prefix is normally omitted.
A general rule - if you doubt - look around in the code base. llvm::Log2_64_Ceil is used in a single place, all others are using just Log2_64_Ceil. I think the latter is a preferable form for it.

[irichter]

Now using llvm::Log2_64_Ceil; also, tests are somewhat less arbitrary (middle values are now near 2^16 and 2^32, maximum is tested at UINT64_MAX.)

[MaskRay]

lld/ELF/ScriptParser.cpp

1338

Append a full stop.

1340

UINT64_C(1)

lld/test/ELF/linkerscript/operators.test

94

I think log2ceil100000000 and log2ceil100000001, no need for log2ceil10000 & log2ceil10001.

[irichter]

• Append "." to LOG2CEIL comment
• Use UINT64_C rather than static_cast<uint64_t>
• Remove tests for 2^16 and 2^16+1

[MaskRay]

Looks great!

[irichter]

In D84054#2174766, @MaskRay wrote:

Looks great!

I greatly appreciate the help and feedback from yourself and @grimar.

I don't have commit access, and would request one of you (or another committer) pushing it to master with --author "Isaac Richter <[e-mail]>". Thanks.

[grimar]

Thanks for the patch. I've committed as https://github.com/llvm/llvm-project/commit/fa1145a8d2f1bd00a60d0ed4572901d2b1403157.

lld/ELF/ScriptParser.cpp

 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/StringSet.h"
 #include "llvm/ADT/StringSwitch.h"
 #include "llvm/BinaryFormat/ELF.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/FileSystem.h"
+#include "llvm/Support/MathExtras.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/ScopedPrinter.h"
 #include <cassert>
 #include <limits>
 #include <vector>
 
 using namespace llvm;
 using namespace llvm::ELF;
if (tok == "LOADADDR") {
     StringRef name = readParenLiteral();
     OutputSection *cmd = script->getOrCreateOutputSection(name);
     cmd->usedInExpression = true;
     return [=] {
       checkIfExists(cmd, location);
       return cmd->getLMA();
     };
   }
+  if (tok == "LOG2CEIL") {
+    expect("(");
+    Expr a = readExpr();
+    expect(")");
+    return [=] {
+      // LOG2CEIL(0) is defined to be 0.
+      return llvm::Log2_64_Ceil(std::max(a().getValue(), UINT64_C(1)));
+    };
+  }
   if (tok == "MAX" || tok == "MIN") {
     expect("(");
     Expr a = readExpr();
     expect(",");
     Expr b = readExpr();
     expect(")");
     if (tok == "MIN")
       return [=] { return std::min(a().getValue(), b().getValue()); };

lld/test/ELF/linkerscript/operators.test

SECTIONS {
   . = 0xfff0;
   datasegmentalign = DATA_SEGMENT_ALIGN (0xffff, 0);
   datasegmentalign2 = DATA_SEGMENT_ALIGN (0, 0);
   _end = .;
   minus_rel = _end - 0x10;
   minus_abs = _end - _start;
   max = MAX(11, 22);
   min = MIN(11, 22);
+  log2ceil0 = LOG2CEIL(0);
+  log2ceil1 = LOG2CEIL(1);
+  log2ceil2 = LOG2CEIL(2);
+  log2ceil3 = LOG2CEIL(3);
+  log2ceil4 = LOG2CEIL(4);
+  log2ceil100000000 = LOG2CEIL(0x100000000);
+  log2ceil100000001 = LOG2CEIL(0x100000001);
+  log2ceilmax = LOG2CEIL(0xffffffffffffffff);
   logicaland1 = 0 && 0;
   logicaland2 = 0 && 1;
   logicaland3 = 1 && 0;
   logicaland4 = 1 && 1;
   logicalor1 = 0 || 0;
   logicalor2 = 0 || 1;
   logicalor3 = 1 || 0;
   logicalor4 = 1 || 1;

 # CHECK-NEXT: 00000000001000 A maxpagesize
 # CHECK-NEXT: 00000000001000 A commonpagesize
 # CHECK-NEXT: 0000000000ffff A datasegmentalign
 # CHECK-NEXT: 0000000000fff0 A datasegmentalign2
 # CHECK-NEXT: 0000000000ffe0 T minus_rel
 # CHECK-NEXT: 0000000000fff0 A minus_abs
 # CHECK-NEXT: 00000000000016 A max
 # CHECK-NEXT: 0000000000000b A min
+# CHECK-NEXT: 0000000000000000 A log2ceil0
+# CHECK-NEXT: 0000000000000000 A log2ceil1
+# CHECK-NEXT: 0000000000000001 A log2ceil2
+# CHECK-NEXT: 0000000000000002 A log2ceil3
+# CHECK-NEXT: 0000000000000002 A log2ceil4
+# CHECK-NEXT: 0000000000000020 A log2ceil100000000
+# CHECK-NEXT: 0000000000000021 A log2ceil100000001
+# CHECK-NEXT: 0000000000000040 A log2ceilmax
 # CHECK-NEXT: 00000000000000 A logicaland1
 # CHECK-NEXT: 00000000000000 A logicaland2
 # CHECK-NEXT: 00000000000000 A logicaland3
 # CHECK-NEXT: 00000000000001 A logicaland4
 # CHECK-NEXT: 00000000000000 A logicalor1
 # CHECK-NEXT: 00000000000001 A logicalor2
 # CHECK-NEXT: 00000000000001 A logicalor3
 # CHECK-NEXT: 00000000000001 A logicalor4