[BOLT] Fix AARCH64 registers aliasing

[yota9]

Summary

The aarch64 platform has special registers like X0_X1_X2_X3_X4_X5_X6_X7.
Using the downwars propagation this register will become a super
register for all X0..X7 and its subregisters which is not right. This
patch replaces the downwars propagation with caching all the aliases using MCRegAliasIterator.

Vladislav Khmelevsky,
Advanced Software Technology Lab, Huawei

[fhahn]

Is it possible to add a test?

[yota9]

@fhahn This is very internal function of the BOLT, so I'm not sure hot to add such a testcase

[fhahn]

In D117394#3247843, @yota9 wrote:

@fhahn This is very internal function of the BOLT, so I'm not sure hot to add such a testcase

It fixes something, so there should be a way to test this change in behavior I assume, although I have no idea about how unit tests for bolt look like.

[yota9]

@fhahn The problem was not found during bolt usage, i.e. wrong output, but accidentally while I was investigating the aarch64 indirect branch support level. Currently the bolt uses tests like "input file" -> "output file", but I don't have an example of input file where the problem might occur and I don't know the way to test particular function from bolt internals. Maybe the reviewers will give me a hint on this

[yota9]

Very gentle ping to @maksfb @rafauler @Amir :))

[maksfb]

Thanks for the fix! Please spellcheck the summary before committing.

[fhahn]

In D117394#3265252, @maksfb wrote:

Thanks for the fix! Please spellcheck the summary before committing.

There remains the question of and how this can be tested I think.

[maksfb]

In D117394#3265334, @fhahn wrote:

In D117394#3265252, @maksfb wrote:

Thanks for the fix! Please spellcheck the summary before committing.

There remains the question of and how this can be tested I think.

That's a good point. @yota9, if the testing can only be done via unit tests, we should add it. Which means we also have to add necessary changes to /bolt, as we currently don't have unit tests setup.

[yota9]

Hello @maksfb I was able to add unit tests support and to test this particular function :)

[Amir]

@yota9
That's very impressive! But can you please split out adding the unit test infrastructure to a separate diff?

[maksfb]

That's fantastic. Thank you, @yota9.

[yota9]

Reabased patch, add x86 reg aliasing test

[yota9]

Test refactor

[yota9]

Add target-specific includes under ifdef

[yota9]

Gentle ping to reviewers :)

[maksfb]

Looks great!

[rafauler]

Looks good, thanks! What are the practical implications of this for AArch64? Which pass is relying on ::getAliases()?

[yota9]

In D117394#3277884, @rafauler wrote:

Looks good, thanks! What are the practical implications of this for AArch64? Which pass is relying on ::getAliases()?

Hello @rafaelauler ! I've found out the problem while investigating the analyzeIndirectBranchFragment for aarch64..

bolt/lib/Core/MCPlusBuilder.cpp

bool MCPlusBuilder::hasUseOfPhysReg(const MCInst &MI, unsigned Reg) const {
   return false;
 }
 
 const BitVector &MCPlusBuilder::getAliases(MCPhysReg Reg,
                                            bool OnlySmaller) const {
   // AliasMap caches a mapping of registers to the set of registers that
   // alias (are sub or superregs of itself, including itself).
   static std::vector<BitVector> AliasMap;
-  static std::vector<MCPhysReg> SuperReg;
+  static std::vector<BitVector> SmallerAliasMap;
 
   if (AliasMap.size() > 0) {
     if (OnlySmaller)
-      return AliasMap[Reg];
-    return AliasMap[SuperReg[Reg]];
+      return SmallerAliasMap[Reg];
   }
+
   // Build alias map
   for (MCPhysReg I = 0, E = RegInfo->getNumRegs(); I != E; ++I) {
     BitVector BV(RegInfo->getNumRegs(), false);
     BV.set(I);
-    AliasMap.emplace_back(std::move(BV));
-    SuperReg.emplace_back(I);
+    AliasMap.emplace_back(BV);
+    SmallerAliasMap.emplace_back(BV);
+  }
+
+  // Cache all aliases for each register
+  for (MCPhysReg I = 1, E = RegInfo->getNumRegs(); I != E; ++I) {
+    for (MCRegAliasIterator AI(I, RegInfo, true); AI.isValid(); ++AI)
+      AliasMap[I].set(*AI);
   }
+
+  // Propagate smaller alias info upwards. Skip reg 0 (mapped to NoRegister)
   std::queue<MCPhysReg> Worklist;
-  // Propagate alias info upwards. Skip reg 0 (mapped to NoRegister)
   for (MCPhysReg I = 1, E = RegInfo->getNumRegs(); I < E; ++I)
     Worklist.push(I);
   while (!Worklist.empty()) {
     MCPhysReg I = Worklist.front();
     Worklist.pop();
     for (MCSubRegIterator SI(I, RegInfo); SI.isValid(); ++SI)
-      AliasMap[I] |= AliasMap[*SI];
+      SmallerAliasMap[I] |= SmallerAliasMap[*SI];
     for (MCSuperRegIterator SI(I, RegInfo); SI.isValid(); ++SI)
       Worklist.push(*SI);
   }
-  // Propagate parent reg downwards
-  for (MCPhysReg I = 1, E = RegInfo->getNumRegs(); I < E; ++I)
-    Worklist.push(I);
-  while (!Worklist.empty()) {
-    MCPhysReg I = Worklist.front();
-    Worklist.pop();
-    for (MCSubRegIterator SI(I, RegInfo); SI.isValid(); ++SI) {
-      SuperReg[*SI] = SuperReg[I];
-      Worklist.push(*SI);
-    }
-  }
 
   LLVM_DEBUG({
     dbgs() << "Dumping reg alias table:\n";
     for (MCPhysReg I = 0, E = RegInfo->getNumRegs(); I != E; ++I) {
       dbgs() << "Reg " << I << ": ";
-      const BitVector &BV = AliasMap[SuperReg[I]];
+      const BitVector &BV = AliasMap[I];
       int Idx = BV.find_first();
       while (Idx != -1) {
         dbgs() << Idx << " ";
         Idx = BV.find_next(Idx);
       }
       dbgs() << "\n";
     }
   });
 
   if (OnlySmaller)
-    return AliasMap[Reg];
-  return AliasMap[SuperReg[Reg]];
+    return SmallerAliasMap[Reg];
 }
 
 uint8_t MCPlusBuilder::getRegSize(MCPhysReg Reg) const {
   // SizeMap caches a mapping of registers to their sizes
   static std::vector<uint8_t> SizeMap;
 
   if (SizeMap.size() > 0) {
     return SizeMap[Reg];

bolt/unittests/CMakeLists.txt

 add_custom_target(BoltUnitTests)
 set_target_properties(BoltUnitTests PROPERTIES FOLDER "BOLT tests")
 
 function(add_bolt_unittest test_dirname)
   add_unittest(BoltUnitTests ${test_dirname} ${ARGN})
 endfunction()
+
+add_subdirectory(Core)

bolt/unittests/Core/CMakeLists.txt

+set(LLVM_LINK_COMPONENTS
+  BOLTRewrite
+  )
+
+add_bolt_unittest(CoreTests
+  MCPlusBuilder.cpp
+  )
+
+string(FIND "${LLVM_TARGETS_TO_BUILD}" "AArch64" POSITION)
+if (NOT ${POSITION} EQUAL -1)
+  include_directories(
+    ${CMAKE_SOURCE_DIR}/lib/Target/AArch64
+    ${CMAKE_BINARY_DIR}/lib/Target/AArch64
+  )
+
+  target_compile_definitions(CoreTests PRIVATE AARCH64_AVAILABLE)
+endif()
+
+string(FIND "${LLVM_TARGETS_TO_BUILD}" "X86" POSITION)
+if (NOT ${POSITION} EQUAL -1)
+  include_directories(
+    ${LLVM_MAIN_SRC_DIR}/lib/Target/X86
+    ${LLVM_BINARY_DIR}/lib/Target/X86
+  )
+
+  target_compile_definitions(CoreTests PRIVATE X86_AVAILABLE)
+endif()

bolt/unittests/Core/MCPlusBuilder.cpp

+#ifdef AARCH64_AVAILABLE
+#include "AArch64Subtarget.h"
+#endif // AARCH64_AVAILABLE
+
+#ifdef X86_AVAILABLE
+#include "X86Subtarget.h"
+#endif // X86_AVAILABLE
+
+#include "bolt/Rewrite/RewriteInstance.h"
+#include "llvm/BinaryFormat/ELF.h"
+#include "llvm/DebugInfo/DWARF/DWARFContext.h"
+#include "llvm/Object/ELFObjectFile.h"
+#include "llvm/Support/TargetSelect.h"
+#include "gtest/gtest.h"
+
+using namespace llvm;
+using namespace llvm::object;
+using namespace llvm::ELF;
+using namespace bolt;
+
+namespace {
+struct MCPlusBuilderTester : public testing::TestWithParam<Triple::ArchType> {
+  void SetUp() override {
+    initalizeLLVM();
+    prepareElf();
+    initializeBolt();
+  }
+
+protected:
+  void initalizeLLVM() {
+    llvm::InitializeAllTargetInfos();
+    llvm::InitializeAllTargetMCs();
+    llvm::InitializeAllAsmParsers();
+    llvm::InitializeAllDisassemblers();
+    llvm::InitializeAllTargets();
+    llvm::InitializeAllAsmPrinters();
+  }
+
+  void prepareElf() {
+    memcpy(ElfBuf, "\177ELF", 4);
+    ELF64LE::Ehdr *EHdr = reinterpret_cast<typename ELF64LE::Ehdr *>(ElfBuf);
+    EHdr->e_ident[llvm::ELF::EI_CLASS] = llvm::ELF::ELFCLASS64;
+    EHdr->e_ident[llvm::ELF::EI_DATA] = llvm::ELF::ELFDATA2LSB;
+    EHdr->e_machine = GetParam() == Triple::aarch64 ? EM_AARCH64 : EM_X86_64;
+    MemoryBufferRef Source(StringRef(ElfBuf, sizeof(ElfBuf)), "ELF");
+    ObjFile = cantFail(ObjectFile::createObjectFile(Source));
+  }
+
+  void initializeBolt() {
+    BC = BinaryContext::createBinaryContext(
+        ObjFile.get(), true, DWARFContext::create(*ObjFile.get()));
+    ASSERT_FALSE(!BC);
+    BC->initializeTarget(std::unique_ptr<MCPlusBuilder>(createMCPlusBuilder(
+        GetParam(), BC->MIA.get(), BC->MII.get(), BC->MRI.get())));
+  }
+
+  void testRegAliases(Triple::ArchType Arch, uint64_t Register,
+                      uint64_t *Aliases, size_t Count,
+                      bool OnlySmaller = false) {
+    if (GetParam() != Arch)
+      GTEST_SKIP();
+
+    const BitVector &BV = BC->MIB->getAliases(Register, OnlySmaller);
+    ASSERT_EQ(BV.count(), Count);
+    for (size_t I = 0; I < Count; ++I)
+      ASSERT_TRUE(BV[Aliases[I]]);
+  }
+
+  char ElfBuf[sizeof(typename ELF64LE::Ehdr)] = {};
+  std::unique_ptr<ObjectFile> ObjFile;
+  std::unique_ptr<BinaryContext> BC;
+};
+} // namespace
+
+#ifdef AARCH64_AVAILABLE
+
+INSTANTIATE_TEST_SUITE_P(AArch64, MCPlusBuilderTester,
+                         ::testing::Values(Triple::aarch64));
+
+TEST_P(MCPlusBuilderTester, AliasX0) {
+  uint64_t AliasesX0[] = {AArch64::W0, AArch64::X0, AArch64::W0_W1,
+                          AArch64::X0_X1, AArch64::X0_X1_X2_X3_X4_X5_X6_X7};
+  size_t AliasesX0Count = sizeof(AliasesX0) / sizeof(*AliasesX0);
+  testRegAliases(Triple::aarch64, AArch64::X0, AliasesX0, AliasesX0Count);
+}
+
+TEST_P(MCPlusBuilderTester, AliasSmallerX0) {
+  uint64_t AliasesX0[] = {AArch64::W0, AArch64::X0};
+  size_t AliasesX0Count = sizeof(AliasesX0) / sizeof(*AliasesX0);
+  testRegAliases(Triple::aarch64, AArch64::X0, AliasesX0, AliasesX0Count, true);
+}
+
+#endif // AARCH64_AVAILABLE
+
+#ifdef X86_AVAILABLE
+
+INSTANTIATE_TEST_SUITE_P(X86, MCPlusBuilderTester,
+                         ::testing::Values(Triple::x86_64));
+
+TEST_P(MCPlusBuilderTester, AliasAX) {
+  uint64_t AliasesAX[] = {X86::RAX, X86::EAX, X86::AX, X86::AL, X86::AH};
+  size_t AliasesAXCount = sizeof(AliasesAX) / sizeof(*AliasesAX);
+  testRegAliases(Triple::x86_64, X86::AX, AliasesAX, AliasesAXCount);
+}
+
+TEST_P(MCPlusBuilderTester, AliasSmallerAX) {
+  uint64_t AliasesAX[] = {X86::AX, X86::AL, X86::AH};
+  size_t AliasesAXCount = sizeof(AliasesAX) / sizeof(*AliasesAX);
+  testRegAliases(Triple::x86_64, X86::AX, AliasesAX, AliasesAXCount, true);
+}
+
+#endif // X86_AVAILABLE