This is an archive of the discontinued LLVM Phabricator instance.

[lld][ELF] Add LOG2CEIL builtin ldscript function
ClosedPublic

Authored by irichter on Jul 17 2020, 10:38 AM.

Details

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.)

Diff Detail

Event Timeline

irichter created this revision.Jul 17 2020, 10:38 AM
irichter created this object with visibility "irichter (Isaac Richter)".
Herald added a project: Restricted Project. · View Herald TranscriptJul 17 2020, 10:38 AM
irichter edited the summary of this revision. (Show Details)Jul 19 2020, 12:51 PM
irichter updated this revision to Diff 279106.Jul 19 2020, 12:54 PM

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

irichter changed the visibility from "irichter (Isaac Richter)" to "Public (No Login Required)".
irichter edited the summary of this revision. (Show Details)Jul 19 2020, 12:59 PM

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?

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

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.

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 updated this revision to Diff 280150.Jul 23 2020, 8:55 AM
irichter set the repository for this revision to rG LLVM Github Monorepo.

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

irichter marked an inline comment as done.Jul 23 2020, 9:14 AM

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 updated this revision to Diff 280200.Jul 23 2020, 11:05 AM

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

irichter set the repository for this revision to rG LLVM Github Monorepo.Jul 23 2020, 11:48 AM
MaskRay added inline comments.Jul 23 2020, 1:17 PM
lld/ELF/ScriptParser.cpp
1339

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

Use //

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?

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.

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?

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 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.

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 updated this revision to Diff 280736.Jul 26 2020, 10:25 AM
irichter edited the summary of this revision. (Show Details)

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 added inline comments.Jul 26 2020, 12:26 PM
lld/ELF/ScriptParser.cpp
1338

Append a full stop.

1340

UINT64_C(1)

lld/test/ELF/linkerscript/operators.test
96

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

irichter updated this revision to Diff 280763.Jul 26 2020, 5:28 PM
irichter marked 5 inline comments as done.
irichter edited the summary of this revision. (Show Details)
  • Append "." to LOG2CEIL comment
  • Use UINT64_C rather than static_cast<uint64_t>
  • Remove tests for 2^16 and 2^16+1
MaskRay accepted this revision.Jul 26 2020, 8:43 PM

Looks great!

This revision is now accepted and ready to land.Jul 26 2020, 8:43 PM

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 <isaac@irichter.net>". Thanks.

This revision was automatically updated to reflect the committed changes.