[BOLT] Align constant islands to 8 bytes

[yota9]

Summary

AArch64 requires CI to be aligned to 8 bytes due to access instructions
restrictions. E.g. the ldr with imm, where imm must be aligned to 8 bytes.

[yota9]

Add test

[yota9]

nit

[Amir]

LGTM but I'm not an AArch64 expert. Rafael is on a vacation, so please tag someone knowledgeable from LLVM AArch64 community (e.g. git blame llvm/unittests/Support/Host.cpp in TEST(getLinuxHostCPUName, AArch64)) to double-check if it's a correct and the only constant island access restriction that needs to be enforced.

bolt/test/runtime/AArch64/constant-island-alignment.s

1 ↗

(On Diff #416698)

nit: bolt tool -> BOLT

[Amir]

Please add a PR fixing bzip2 AArch64 test: https://github.com/rafaelauler/bolt-tests/blob/main/test/AArch64/bzip2.test

[yota9]

Hello @Amir ! I've prepared the fix https://github.com/rafaelauler/bolt-tests/pull/15

[yota9]

nit

[yota9]

Hello @t.p.northover ! I would we thankful I you will review the patch while the @rafaelauler is on vacation. The very main part is located in BinaryEmitter.cpp, that is we will always emit constant island on 8 bytes alignment since currently we don't track here in BOLT is the instruction that will load data from constant island may support unaligned access or not - we will just always aligne it on 8 bytes boundaries. Thank you for your time in advance!

[Amir]

Tests pass, so I'm waiting for clearance from aarch64 reviewer

[Amir]

Accepting to unblock dependent diffs.

We'd still appreciate @t.p.northover or someone from ARM community to have a glance.

[maksfb]

@yota9, similar to my concerns on other diffs, I think it's better for regression tests to check for a specific condition and not to rely on the correct execution of the test binary. This way you will be able to run tests on other architectures.

Regarding the change itself, have you considered aligning constant islands so that they straddle a minimum number of cache lines? The trivial way to achieve this is to align them at cache line boundary, but it's not always the optimal way.

[yota9]

Hello @maksfb !

This way you will be able to run tests on other architectures.

Sure, but the testing is currently does not run aarch64 tests at all.
I don't really mind, but sometimes it is just inconvenient to make such tests. And I still would like some tests to be runnable.. I think we need to discuss the testing policy.

Regarding the change itself, have you considered aligning constant islands so that they straddle a minimum number of cache lines?

This could be discussed, but we need to check if there will be any winning in this, I don't think this is a good way just to align to cache line size, it should be more clever system, but this is beyond the goals of this review. But thank you for you suggestion anyway :)

[maksfb]

In D122065#3406049, @yota9 wrote:

I don't really mind, but sometimes it is just inconvenient to make such tests. And I still would like some tests to be runnable.. I think we need to discuss the testing policy.

It's fair to say that sometimes creating non-runnable test is way easier. However, in this case, will it be sufficient to locate the island in the output binary (e.g. with llvm-objdump) and make sure the address is aligned ({{0|8}})?

Regarding the change itself, have you considered aligning constant islands so that they straddle a minimum number of cache lines?

This could be discussed, but we need to check if there will be any winning in this, I don't think this is a good way just to align to cache line size, it should be more clever system, but this is beyond the goals of this review. But thank you for you suggestion anyway :)

Totally, I don't mean it for this diff. However, could you create a constant for the alignment (instead of sizeof(uint64_t)) that could be easily changed for running experiments?

[yota9]

@maksfb Thank you for your comments! Resolved both of them.

[yota9]

nit

[maksfb]

Overall LGTM.

I have a general concern that the estimation of the size for islands and the actual emission are decoupled and could get out of sync. At the same time, I don't have a good suggestion on how to fix it. For functions, to calculate the size we create a temporary emitter and run the same code used for real emission, get the size of the emitted code and then discard the code.

bolt/test/AArch64/constant-island-alignment.s

13

nit: place the CHECK next to the asm directive that corresponds to the island being checked. I don't know how the names are assigned for islands and if it's possible to give it a distinctive name.

[yota9]

Thank you for your review @maksfb ! I agree with your concerns but currently I don't have a good idea too. Within the time I hope we will find a solution :)

bolt/test/AArch64/constant-island-alignment.s

13

Done. The $d is the arm ABI name, there is no way to manipulate this AFAIK

bolt/include/bolt/Core/BinaryFunction.h

struct IslandInfo {
     DenseMap<const MCSymbol *, MCSymbol *> ColdSymbols;
     /// Keeps track of other functions we depend on because there is a reference
     /// to the constant islands in them.
     IslandProxiesType Proxies, ColdProxies;
     SmallPtrSet<BinaryFunction *, 1> Dependency; // The other way around
 
     mutable MCSymbol *FunctionConstantIslandLabel{nullptr};
     mutable MCSymbol *FunctionColdConstantIslandLabel{nullptr};
+
+    // Returns constant island alignment
+    uint16_t getAlignment() const { return sizeof(uint64_t); }
   };
 
   static constexpr uint64_t COUNT_NO_PROFILE =
       BinaryBasicBlock::COUNT_NO_PROFILE;
 
   /// We have to use at least 2-byte alignment for functions because of C++ ABI.
   static constexpr unsigned MinAlign = 2;
 
bool isInConstantIsland(uint64_t Address) const {
 
     auto CodeIter = Islands->CodeOffsets.upper_bound(Offset);
     if (CodeIter == Islands->CodeOffsets.begin())
       return true;
 
     return *std::prev(CodeIter) <= *DataIter;
   }
 
+  uint16_t getConstantIslandAlignment() const {
+    return Islands ? Islands->getAlignment() : 1;
+  }
+
   uint64_t
   estimateConstantIslandSize(const BinaryFunction *OnBehalfOf = nullptr) const {
     if (!Islands)
       return 0;
 
     uint64_t Size = 0;
     for (auto DataIter = Islands->DataOffsets.begin();
          DataIter != Islands->DataOffsets.end(); ++DataIter) {
for (auto DataIter = Islands->DataOffsets.begin();
       else if (NextData == Islands->DataOffsets.end())
         NextMarker = *CodeIter;
       else
         NextMarker = (*CodeIter > *NextData) ? *NextData : *CodeIter;
 
       Size += NextMarker - *DataIter;
     }
 
-    if (!OnBehalfOf)
-      for (BinaryFunction *ExternalFunc : Islands->Dependency)
+    if (!OnBehalfOf) {
+      for (BinaryFunction *ExternalFunc : Islands->Dependency) {
+        Size = alignTo(Size, ExternalFunc->getConstantIslandAlignment());
         Size += ExternalFunc->estimateConstantIslandSize(this);
+      }
+    }
+
     return Size;
   }
 
   bool hasIslandsInfo() const { return !!Islands; }
 
   bool hasConstantIsland() const {
     return Islands && !Islands->DataOffsets.empty();
   }

bolt/lib/Core/BinaryEmitter.cpp

void BinaryEmitter::emitConstantIslands(BinaryFunction &BF, bool EmitColdPart,
                                         BinaryFunction *OnBehalfOf) {
   if (!BF.hasIslandsInfo())
     return;
 
   BinaryFunction::IslandInfo &Islands = BF.getIslandInfo();
   if (Islands.DataOffsets.empty() && Islands.Dependency.empty())
     return;
 
+  // AArch64 requires CI to be aligned to 8 bytes due to access instructions
+  // restrictions. E.g. the ldr with imm, where imm must be aligned to 8 bytes.
+  const uint16_t Alignment = OnBehalfOf
+                                 ? OnBehalfOf->getConstantIslandAlignment()
+                                 : BF.getConstantIslandAlignment();
+  Streamer.emitCodeAlignment(Alignment, &*BC.STI);
+
   if (!OnBehalfOf) {
     if (!EmitColdPart)
       Streamer.emitLabel(BF.getFunctionConstantIslandLabel());
     else
       Streamer.emitLabel(BF.getFunctionColdConstantIslandLabel());
   }
 
   assert((!OnBehalfOf || Islands.Proxies[OnBehalfOf].size() > 0) &&

bolt/lib/Passes/LongJmp.cpp

for (BinaryFunction *Func : SortedFunctions) {
     uint64_t Pad =
         offsetToAlignment(DotAddress, llvm::Align(Func->getAlignment()));
     if (Pad <= Func->getMaxColdAlignmentBytes())
       DotAddress += Pad;
     ColdAddresses[Func] = DotAddress;
     LLVM_DEBUG(dbgs() << Func->getPrintName() << " cold tentative: "
                       << Twine::utohexstr(DotAddress) << "\n");
     DotAddress += Func->estimateColdSize();
+    DotAddress = alignTo(DotAddress, Func->getConstantIslandAlignment());
     DotAddress += Func->estimateConstantIslandSize();
   }
   return DotAddress;
 }
 
 uint64_t LongJmpPass::tentativeLayoutRelocMode(
     const BinaryContext &BC, std::vector<BinaryFunction *> &SortedFunctions,
     uint64_t DotAddress) {
if (Pad <= Func->getMaxAlignmentBytes())
       DotAddress += Pad;
     HotAddresses[Func] = DotAddress;
     LLVM_DEBUG(dbgs() << Func->getPrintName() << " tentative: "
                       << Twine::utohexstr(DotAddress) << "\n");
     if (!Func->isSplit())
       DotAddress += Func->estimateSize();
     else
       DotAddress += Func->estimateHotSize();
+
+    DotAddress = alignTo(DotAddress, Func->getConstantIslandAlignment());
     DotAddress += Func->estimateConstantIslandSize();
     ++CurrentIndex;
   }
   // BBs
   for (BinaryFunction *Func : SortedFunctions)
     tentativeBBLayout(*Func);
 
   return DotAddress;

bolt/test/AArch64/constant-island-alignment.s

+// This test checks that the constant island is aligned after BOLT tool.
+// In case the nop before .Lci will be removed the pointer to exit function
+// won't be alinged and the test will fail.
+
+# RUN: llvm-mc -filetype=obj -triple aarch64-unknown-unknown \
+# RUN:   %s -o %t.o
+# RUN: %clang %cflags -fPIC -pie %t.o -o %t.exe -Wl,-q \
+# RUN:    -nostartfiles -nodefaultlibs -lc
+# RUN: llvm-bolt %t.exe -o %t.bolt -use-old-text=0 -lite=0 -trap-old-code
+# RUN: llvm-objdump -d --disassemble-symbols='$d' %t.bolt | FileCheck %s
+
+.text
+.align 4
+.global
+.type dummy, %function
+dummy:
+  add x0, x0, #1
+  ret
+
+.global
+.type exitOk, %function
+exitOk:
+  mov x0, #0
+  bl exit
+
+.global _start
+.type _start, %function
+_start:
+  adrp x0, .Lci
+  ldr x0, [x0, #:lo12:.Lci]
+  blr x0
+  mov x1, #1
+  bl exit
+  nop
+# CHECK: {{0|8}} <$d>:
+.Lci:
+  .xword exitOk
+  .xword 0

bolt/test/runtime/AArch64/adrrelaxationpass.s

main:
   adr x3, br
 br:
   br x1
   .size main, .-main
 .CI:
   .word 0xff
 
 # CHECK: <main>:
-# CHECK-NEXT: adr x0, #28
+# CHECK-NEXT: adr x0, #{{[0-9][0-9]*}}
 # CHECK-NEXT: adrp x1, 0x{{[1-8a-f][0-9a-f]*}}
 # CHECK-NEXT: add x1, x1, #{{[1-8a-f][0-9a-f]*}}
 # CHECK-NEXT: adrp x2, 0x{{[1-8a-f][0-9a-f]*}}
 # CHECK-NEXT: add x2, x2, #{{[1-8a-f][0-9a-f]*}}
-# CHECK-NEXT: adr x3, #4
+# CHECK-NEXT: adr x3, #{{[0-9][0-9]*}}