llvm/unittests/ExecutionEngine/JITLink/LinkGraphTests.cpp

   1 //===------ LinkGraphTests.cpp - Unit tests for core JITLink classes ------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "llvm/ADT/STLExtras.h"
  10 #include "llvm/ExecutionEngine/JITLink/JITLink.h"
  11 #include "llvm/Support/Endian.h"
  12 #include "llvm/Support/Memory.h"
  13 #include "gtest/gtest.h"
  14
  15 using namespace llvm;
  16 using namespace llvm::jitlink;
  17
  18 static auto RWFlags =
  19     sys::Memory::ProtectionFlags(sys::Memory::MF_READ | sys::Memory::MF_WRITE);
  20
  21 static const char BlockContentBytes[] = {
  22     0x54, 0x68, 0x65, 0x72, 0x65, 0x20, 0x77, 0x61, 0x73, 0x20, 0x6d, 0x6f,
  23     0x76, 0x65, 0x6d, 0x65, 0x6e, 0x74, 0x20, 0x61, 0x74, 0x20, 0x74, 0x68,
  24     0x65, 0x20, 0x73, 0x74, 0x61, 0x74, 0x69, 0x6f, 0x6e, 0x2c, 0x20, 0x66,
  25     0x6f, 0x72, 0x20, 0x74, 0x68, 0x65, 0x20, 0x77, 0x6f, 0x72, 0x64, 0x20,
  26     0x68, 0x61, 0x64, 0x20, 0x70, 0x61, 0x73, 0x73, 0x65, 0x64, 0x20, 0x61,
  27     0x72, 0x6f, 0x75, 0x6e, 0x64, 0x0a, 0x54, 0x68, 0x61, 0x74, 0x20, 0x74,
  28     0x68, 0x65, 0x20, 0x63, 0x6f, 0x6c, 0x74, 0x20, 0x66, 0x72, 0x6f, 0x6d,
  29     0x20, 0x4f, 0x6c, 0x64, 0x20, 0x52, 0x65, 0x67, 0x72, 0x65, 0x74, 0x20,
  30     0x68, 0x61, 0x64, 0x20, 0x67, 0x6f, 0x74, 0x20, 0x61, 0x77, 0x61, 0x79,
  31     0x2c, 0x0a, 0x41, 0x6e, 0x64, 0x20, 0x68, 0x61, 0x64, 0x20, 0x6a, 0x6f,
  32     0x69, 0x6e, 0x65, 0x64, 0x20, 0x74, 0x68, 0x65, 0x20, 0x77, 0x69, 0x6c,
  33     0x64, 0x20, 0x62, 0x75, 0x73, 0x68, 0x20, 0x68, 0x6f, 0x72, 0x73, 0x65,
  34     0x73, 0x20, 0x2d, 0x2d, 0x20, 0x68, 0x65, 0x20, 0x77, 0x61, 0x73, 0x20,
  35     0x77, 0x6f, 0x72, 0x74, 0x68, 0x20, 0x61, 0x20, 0x74, 0x68, 0x6f, 0x75,
  36     0x73, 0x61, 0x6e, 0x64, 0x20, 0x70, 0x6f, 0x75, 0x6e, 0x64, 0x2c, 0x0a,
  37     0x53, 0x6f, 0x20, 0x61, 0x6c, 0x6c, 0x20, 0x74, 0x68, 0x65, 0x20, 0x63,
  38     0x72, 0x61, 0x63, 0x6b, 0x73, 0x20, 0x68, 0x61, 0x64, 0x20, 0x67, 0x61,
  39     0x74, 0x68, 0x65, 0x72, 0x65, 0x64, 0x20, 0x74, 0x6f, 0x20, 0x74, 0x68,
  40     0x65, 0x20, 0x66, 0x72, 0x61, 0x79, 0x2e, 0x0a, 0x41, 0x6c, 0x6c, 0x20,
  41     0x74, 0x68, 0x65, 0x20, 0x74, 0x72, 0x69, 0x65, 0x64, 0x20, 0x61, 0x6e,
  42     0x64, 0x20, 0x6e, 0x6f, 0x74, 0x65, 0x64, 0x20, 0x72, 0x69, 0x64, 0x65,
  43     0x72, 0x73, 0x20, 0x66, 0x72, 0x6f, 0x6d, 0x20, 0x74, 0x68, 0x65, 0x20,
  44     0x73, 0x74, 0x61, 0x74, 0x69, 0x6f, 0x6e, 0x73, 0x20, 0x6e, 0x65, 0x61,
  45     0x72, 0x20, 0x61, 0x6e, 0x64, 0x20, 0x66, 0x61, 0x72, 0x0a, 0x48, 0x61,
  46     0x64, 0x20, 0x6d, 0x75, 0x73, 0x74, 0x65, 0x72, 0x65, 0x64, 0x20, 0x61,
  47     0x74, 0x20, 0x74, 0x68, 0x65, 0x20, 0x68, 0x6f, 0x6d, 0x65, 0x73, 0x74,
  48     0x65, 0x61, 0x64, 0x20, 0x6f, 0x76, 0x65, 0x72, 0x6e, 0x69, 0x67, 0x68,
  49     0x74, 0x2c, 0x0a, 0x46, 0x6f, 0x72, 0x20, 0x74, 0x68, 0x65, 0x20, 0x62,
  50     0x75, 0x73, 0x68, 0x6d, 0x65, 0x6e, 0x20, 0x6c, 0x6f, 0x76, 0x65, 0x20,
  51     0x68, 0x61, 0x72, 0x64, 0x20, 0x72, 0x69, 0x64, 0x69, 0x6e, 0x67, 0x20,
  52     0x77, 0x68, 0x65, 0x72, 0x65, 0x20, 0x74, 0x68, 0x65, 0x20, 0x77, 0x69,
  53     0x6c, 0x64, 0x20, 0x62, 0x75, 0x73, 0x68, 0x20, 0x68, 0x6f, 0x72, 0x73,
  54     0x65, 0x73, 0x20, 0x61, 0x72, 0x65, 0x2c, 0x0a, 0x41, 0x6e, 0x64, 0x20,
  55     0x74, 0x68, 0x65, 0x20, 0x73, 0x74, 0x6f, 0x63, 0x6b, 0x2d, 0x68, 0x6f,
  56     0x72, 0x73, 0x65, 0x20, 0x73, 0x6e, 0x75, 0x66, 0x66, 0x73, 0x20, 0x74,
  57     0x68, 0x65, 0x20, 0x62, 0x61, 0x74, 0x74, 0x6c, 0x65, 0x20, 0x77, 0x69,
  58     0x74, 0x68, 0x20, 0x64, 0x65, 0x6c, 0x69, 0x67, 0x68, 0x74, 0x2e, 0x00};
  59
  60 static ArrayRef<char> BlockContent(BlockContentBytes);
  61
  62 TEST(LinkGraphTest, Construction) {
  63   // Check that LinkGraph construction works as expected.
  64   LinkGraph G("foo", Triple("x86_64-apple-darwin"), 8, support::little,
  65               getGenericEdgeKindName);
  66   EXPECT_EQ(G.getName(), "foo");
  67   EXPECT_EQ(G.getTargetTriple().str(), "x86_64-apple-darwin");
  68   EXPECT_EQ(G.getPointerSize(), 8U);
  69   EXPECT_EQ(G.getEndianness(), support::little);
  70   EXPECT_TRUE(llvm::empty(G.external_symbols()));
  71   EXPECT_TRUE(llvm::empty(G.absolute_symbols()));
  72   EXPECT_TRUE(llvm::empty(G.defined_symbols()));
  73   EXPECT_TRUE(llvm::empty(G.blocks()));
  74 }
  75
  76 TEST(LinkGraphTest, AddressAccess) {
  77   // Check that we can get addresses for blocks, symbols, and edges.
  78   LinkGraph G("foo", Triple("x86_64-apple-darwin"), 8, support::little,
  79               getGenericEdgeKindName);
  80
  81   auto &Sec1 = G.createSection("__data.1", RWFlags);
  82   auto &B1 = G.createContentBlock(Sec1, BlockContent, 0x1000, 8, 0);
  83   auto &S1 = G.addDefinedSymbol(B1, 4, "S1", 4, Linkage::Strong, Scope::Default,
  84                                 false, false);
  85   B1.addEdge(Edge::FirstRelocation, 8, S1, 0);
  86   auto &E1 = *B1.edges().begin();
  87
  88   EXPECT_EQ(B1.getAddress(), 0x1000U) << "Incorrect block address";
  89   EXPECT_EQ(S1.getAddress(), 0x1004U) << "Incorrect symbol address";
  90   EXPECT_EQ(B1.getFixupAddress(E1), 0x1008U) << "Incorrect fixup address";
  91 }
  92
  93 TEST(LinkGraphTest, BlockAndSymbolIteration) {
  94   // Check that we can iterate over blocks within Sections and across sections.
  95   LinkGraph G("foo", Triple("x86_64-apple-darwin"), 8, support::little,
  96               getGenericEdgeKindName);
  97   auto &Sec1 = G.createSection("__data.1", RWFlags);
  98   auto &B1 = G.createContentBlock(Sec1, BlockContent, 0x1000, 8, 0);
  99   auto &B2 = G.createContentBlock(Sec1, BlockContent, 0x2000, 8, 0);
 100   auto &S1 = G.addDefinedSymbol(B1, 0, "S1", 4, Linkage::Strong, Scope::Default,
 101                                 false, false);
 102   auto &S2 = G.addDefinedSymbol(B2, 4, "S2", 4, Linkage::Strong, Scope::Default,
 103                                 false, false);
 104
 105   auto &Sec2 = G.createSection("__data.2", RWFlags);
 106   auto &B3 = G.createContentBlock(Sec2, BlockContent, 0x3000, 8, 0);
 107   auto &B4 = G.createContentBlock(Sec2, BlockContent, 0x4000, 8, 0);
 108   auto &S3 = G.addDefinedSymbol(B3, 0, "S3", 4, Linkage::Strong, Scope::Default,
 109                                 false, false);
 110   auto &S4 = G.addDefinedSymbol(B4, 4, "S4", 4, Linkage::Strong, Scope::Default,
 111                                 false, false);
 112
 113   // Check that iteration of blocks within a section behaves as expected.
 114   EXPECT_EQ(std::distance(Sec1.blocks().begin(), Sec1.blocks().end()), 2);
 115   EXPECT_TRUE(llvm::count(Sec1.blocks(), &B1));
 116   EXPECT_TRUE(llvm::count(Sec1.blocks(), &B2));
 117
 118   // Check that iteration of symbols within a section behaves as expected.
 119   EXPECT_EQ(std::distance(Sec1.symbols().begin(), Sec1.symbols().end()), 2);
 120   EXPECT_TRUE(llvm::count(Sec1.symbols(), &S1));
 121   EXPECT_TRUE(llvm::count(Sec1.symbols(), &S2));
 122
 123   // Check that iteration of blocks across sections behaves as expected.
 124   EXPECT_EQ(std::distance(G.blocks().begin(), G.blocks().end()), 4);
 125   EXPECT_TRUE(llvm::count(G.blocks(), &B1));
 126   EXPECT_TRUE(llvm::count(G.blocks(), &B2));
 127   EXPECT_TRUE(llvm::count(G.blocks(), &B3));
 128   EXPECT_TRUE(llvm::count(G.blocks(), &B4));
 129
 130   // Check that iteration of defined symbols across sections behaves as
 131   // expected.
 132   EXPECT_EQ(
 133       std::distance(G.defined_symbols().begin(), G.defined_symbols().end()), 4);
 134   EXPECT_TRUE(llvm::count(G.defined_symbols(), &S1));
 135   EXPECT_TRUE(llvm::count(G.defined_symbols(), &S2));
 136   EXPECT_TRUE(llvm::count(G.defined_symbols(), &S3));
 137   EXPECT_TRUE(llvm::count(G.defined_symbols(), &S4));
 138 }
 139
 140 TEST(LinkGraphTest, ContentAccessAndUpdate) {
 141   // Check that we can make a defined symbol external.
 142   LinkGraph G("foo", Triple("x86_64-apple-darwin"), 8, support::little,
 143               getGenericEdgeKindName);
 144   auto &Sec = G.createSection("__data", RWFlags);
 145
 146   // Create an initial block.
 147   auto &B = G.createContentBlock(Sec, BlockContent, 0x1000, 8, 0);
 148
 149   EXPECT_FALSE(B.isContentMutable()) << "Content unexpectedly mutable";
 150   EXPECT_EQ(B.getContent().data(), BlockContent.data())
 151       << "Unexpected block content data pointer";
 152   EXPECT_EQ(B.getContent().size(), BlockContent.size())
 153       << "Unexpected block content size";
 154
 155   // Expect that attempting to get already-mutable content fails if the
 156   // content is not yet mutable (debug builds only).
 157 #ifndef NDEBUG
 158   EXPECT_DEATH({ (void)B.getAlreadyMutableContent(); },
 159                "Content is not mutable")
 160       << "Unexpected mutable access allowed to immutable data";
 161 #endif
 162
 163   // Check that mutable content is copied on request as expected.
 164   auto MutableContent = B.getMutableContent(G);
 165   EXPECT_TRUE(B.isContentMutable()) << "Content unexpectedly immutable";
 166   EXPECT_NE(MutableContent.data(), BlockContent.data())
 167       << "Unexpected mutable content data pointer";
 168   EXPECT_EQ(MutableContent.size(), BlockContent.size())
 169       << "Unexpected mutable content size";
 170   EXPECT_TRUE(std::equal(MutableContent.begin(), MutableContent.end(),
 171                          BlockContent.begin()))
 172       << "Unexpected mutable content value";
 173
 174   // Check that already-mutable content behaves as expected, with no
 175   // further copies.
 176   auto MutableContent2 = B.getMutableContent(G);
 177   EXPECT_TRUE(B.isContentMutable()) << "Content unexpectedly immutable";
 178   EXPECT_EQ(MutableContent2.data(), MutableContent.data())
 179       << "Unexpected mutable content 2 data pointer";
 180   EXPECT_EQ(MutableContent2.size(), MutableContent.size())
 181       << "Unexpected mutable content 2 size";
 182
 183   // Check that getAlreadyMutableContent behaves as expected, with no
 184   // further copies.
 185   auto MutableContent3 = B.getMutableContent(G);
 186   EXPECT_TRUE(B.isContentMutable()) << "Content unexpectedly immutable";
 187   EXPECT_EQ(MutableContent3.data(), MutableContent.data())
 188       << "Unexpected mutable content 2 data pointer";
 189   EXPECT_EQ(MutableContent3.size(), MutableContent.size())
 190       << "Unexpected mutable content 2 size";
 191
 192   // Set content back to immutable and check that everything behaves as
 193   // expected again.
 194   B.setContent(BlockContent);
 195   EXPECT_FALSE(B.isContentMutable()) << "Content unexpectedly mutable";
 196   EXPECT_EQ(B.getContent().data(), BlockContent.data())
 197       << "Unexpected block content data pointer";
 198   EXPECT_EQ(B.getContent().size(), BlockContent.size())
 199       << "Unexpected block content size";
 200
 201   // Create an initially mutable block.
 202   auto &B2 = G.createMutableContentBlock(Sec, MutableContent, 0x10000, 8, 0);
 203
 204   EXPECT_TRUE(B2.isContentMutable()) << "Expected B2 content to be mutable";
 205 }
 206
 207 TEST(LinkGraphTest, MakeExternal) {
 208   // Check that we can make a defined symbol external.
 209   LinkGraph G("foo", Triple("x86_64-apple-darwin"), 8, support::little,
 210               getGenericEdgeKindName);
 211   auto &Sec = G.createSection("__data", RWFlags);
 212
 213   // Create an initial block.
 214   auto &B1 = G.createContentBlock(Sec, BlockContent, 0x1000, 8, 0);
 215
 216   // Add a symbol to the block.
 217   auto &S1 = G.addDefinedSymbol(B1, 0, "S1", 4, Linkage::Strong, Scope::Default,
 218                                 false, false);
 219
 220   EXPECT_TRUE(S1.isDefined()) << "Symbol should be defined";
 221   EXPECT_FALSE(S1.isExternal()) << "Symbol should not be external";
 222   EXPECT_FALSE(S1.isAbsolute()) << "Symbol should not be absolute";
 223   EXPECT_TRUE(&S1.getBlock()) << "Symbol should have a non-null block";
 224   EXPECT_EQ(S1.getAddress(), 0x1000U) << "Unexpected symbol address";
 225
 226   EXPECT_EQ(
 227       std::distance(G.defined_symbols().begin(), G.defined_symbols().end()), 1U)
 228       << "Unexpected number of defined symbols";
 229   EXPECT_EQ(
 230       std::distance(G.external_symbols().begin(), G.external_symbols().end()),
 231       0U)
 232       << "Unexpected number of external symbols";
 233
 234   // Make S1 external, confirm that the its flags are updated and that it is
 235   // moved from the defined symbols to the externals list.
 236   G.makeExternal(S1);
 237
 238   EXPECT_FALSE(S1.isDefined()) << "Symbol should not be defined";
 239   EXPECT_TRUE(S1.isExternal()) << "Symbol should be external";
 240   EXPECT_FALSE(S1.isAbsolute()) << "Symbol should not be absolute";
 241   EXPECT_EQ(S1.getAddress(), 0U) << "Unexpected symbol address";
 242
 243   EXPECT_EQ(
 244       std::distance(G.defined_symbols().begin(), G.defined_symbols().end()), 0U)
 245       << "Unexpected number of defined symbols";
 246   EXPECT_EQ(
 247       std::distance(G.external_symbols().begin(), G.external_symbols().end()),
 248       1U)
 249       << "Unexpected number of external symbols";
 250 }
 251
 252 TEST(LinkGraphTest, MakeDefined) {
 253   // Check that we can make an external symbol defined.
 254   LinkGraph G("foo", Triple("x86_64-apple-darwin"), 8, support::little,
 255               getGenericEdgeKindName);
 256   auto &Sec = G.createSection("__data", RWFlags);
 257
 258   // Create an initial block.
 259   auto &B1 = G.createContentBlock(Sec, BlockContent, 0x1000, 8, 0);
 260
 261   // Add an external symbol.
 262   auto &S1 = G.addExternalSymbol("S1", 4, Linkage::Strong);
 263
 264   EXPECT_FALSE(S1.isDefined()) << "Symbol should not be defined";
 265   EXPECT_TRUE(S1.isExternal()) << "Symbol should be external";
 266   EXPECT_FALSE(S1.isAbsolute()) << "Symbol should not be absolute";
 267   EXPECT_EQ(S1.getAddress(), 0U) << "Unexpected symbol address";
 268
 269   EXPECT_EQ(
 270       std::distance(G.defined_symbols().begin(), G.defined_symbols().end()), 0U)
 271       << "Unexpected number of defined symbols";
 272   EXPECT_EQ(
 273       std::distance(G.external_symbols().begin(), G.external_symbols().end()),
 274       1U)
 275       << "Unexpected number of external symbols";
 276
 277   // Make S1 defined, confirm that its flags are updated and that it is
 278   // moved from the defined symbols to the externals list.
 279   G.makeDefined(S1, B1, 0, 4, Linkage::Strong, Scope::Default, false);
 280
 281   EXPECT_TRUE(S1.isDefined()) << "Symbol should be defined";
 282   EXPECT_FALSE(S1.isExternal()) << "Symbol should not be external";
 283   EXPECT_FALSE(S1.isAbsolute()) << "Symbol should not be absolute";
 284   EXPECT_TRUE(&S1.getBlock()) << "Symbol should have a non-null block";
 285   EXPECT_EQ(S1.getAddress(), 0x1000U) << "Unexpected symbol address";
 286
 287   EXPECT_EQ(
 288       std::distance(G.defined_symbols().begin(), G.defined_symbols().end()), 1U)
 289       << "Unexpected number of defined symbols";
 290   EXPECT_EQ(
 291       std::distance(G.external_symbols().begin(), G.external_symbols().end()),
 292       0U)
 293       << "Unexpected number of external symbols";
 294 }
 295
 296 TEST(LinkGraphTest, TransferDefinedSymbol) {
 297   // Check that we can transfer a defined symbol from one block to another.
 298   LinkGraph G("foo", Triple("x86_64-apple-darwin"), 8, support::little,
 299               getGenericEdgeKindName);
 300   auto &Sec = G.createSection("__data", RWFlags);
 301
 302   // Create an initial block.
 303   auto &B1 = G.createContentBlock(Sec, BlockContent, 0x1000, 8, 0);
 304   auto &B2 = G.createContentBlock(Sec, BlockContent, 0x2000, 8, 0);
 305   auto &B3 = G.createContentBlock(Sec, BlockContent.slice(0, 32), 0x3000, 8, 0);
 306
 307   // Add a symbol.
 308   auto &S1 = G.addDefinedSymbol(B1, 0, "S1", B1.getSize(), Linkage::Strong,
 309                                 Scope::Default, false, false);
 310
 311   // Transfer with zero offset, explicit size.
 312   G.transferDefinedSymbol(S1, B2, 0, 64);
 313
 314   EXPECT_EQ(&S1.getBlock(), &B2) << "Block was not updated";
 315   EXPECT_EQ(S1.getOffset(), 0U) << "Unexpected offset";
 316   EXPECT_EQ(S1.getSize(), 64U) << "Size was not updated";
 317
 318   // Transfer with non-zero offset, implicit truncation.
 319   G.transferDefinedSymbol(S1, B3, 16, None);
 320
 321   EXPECT_EQ(&S1.getBlock(), &B3) << "Block was not updated";
 322   EXPECT_EQ(S1.getOffset(), 16U) << "Offset was not updated";
 323   EXPECT_EQ(S1.getSize(), 16U) << "Size was not updated";
 324 }
 325
 326 TEST(LinkGraphTest, TransferBlock) {
 327   // Check that we can transfer a block (and all associated symbols) from one
 328   // section to another.
 329   LinkGraph G("foo", Triple("x86_64-apple-darwin"), 8, support::little,
 330               getGenericEdgeKindName);
 331   auto &Sec1 = G.createSection("__data.1", RWFlags);
 332   auto &Sec2 = G.createSection("__data.2", RWFlags);
 333
 334   // Create an initial block.
 335   auto &B1 = G.createContentBlock(Sec1, BlockContent, 0x1000, 8, 0);
 336   auto &B2 = G.createContentBlock(Sec1, BlockContent, 0x2000, 8, 0);
 337
 338   // Add some symbols on B1...
 339   G.addDefinedSymbol(B1, 0, "S1", B1.getSize(), Linkage::Strong, Scope::Default,
 340                      false, false);
 341   G.addDefinedSymbol(B1, 1, "S2", B1.getSize() - 1, Linkage::Strong,
 342                      Scope::Default, false, false);
 343
 344   // ... and on B2.
 345   G.addDefinedSymbol(B2, 0, "S3", B2.getSize(), Linkage::Strong, Scope::Default,
 346                      false, false);
 347   G.addDefinedSymbol(B2, 1, "S4", B2.getSize() - 1, Linkage::Strong,
 348                      Scope::Default, false, false);
 349
 350   EXPECT_EQ(Sec1.blocks_size(), 2U) << "Expected two blocks in Sec1 initially";
 351   EXPECT_EQ(Sec1.symbols_size(), 4U)
 352       << "Expected four symbols in Sec1 initially";
 353   EXPECT_EQ(Sec2.blocks_size(), 0U) << "Expected zero blocks in Sec2 initially";
 354   EXPECT_EQ(Sec2.symbols_size(), 0U)
 355       << "Expected zero symbols in Sec2 initially";
 356
 357   // Transfer with zero offset, explicit size.
 358   G.transferBlock(B1, Sec2);
 359
 360   EXPECT_EQ(Sec1.blocks_size(), 1U)
 361       << "Expected one blocks in Sec1 after transfer";
 362   EXPECT_EQ(Sec1.symbols_size(), 2U)
 363       << "Expected two symbols in Sec1 after transfer";
 364   EXPECT_EQ(Sec2.blocks_size(), 1U)
 365       << "Expected one blocks in Sec2 after transfer";
 366   EXPECT_EQ(Sec2.symbols_size(), 2U)
 367       << "Expected two symbols in Sec2 after transfer";
 368 }
 369
 370 TEST(LinkGraphTest, MergeSections) {
 371   // Check that we can transfer a block (and all associated symbols) from one
 372   // section to another.
 373   LinkGraph G("foo", Triple("x86_64-apple-darwin"), 8, support::little,
 374               getGenericEdgeKindName);
 375   auto &Sec1 = G.createSection("__data.1", RWFlags);
 376   auto &Sec2 = G.createSection("__data.2", RWFlags);
 377   auto &Sec3 = G.createSection("__data.3", RWFlags);
 378
 379   // Create an initial block.
 380   auto &B1 = G.createContentBlock(Sec1, BlockContent, 0x1000, 8, 0);
 381   auto &B2 = G.createContentBlock(Sec2, BlockContent, 0x2000, 8, 0);
 382   auto &B3 = G.createContentBlock(Sec3, BlockContent, 0x3000, 8, 0);
 383
 384   // Add a symbols for each block.
 385   G.addDefinedSymbol(B1, 0, "S1", B1.getSize(), Linkage::Strong, Scope::Default,
 386                      false, false);
 387   G.addDefinedSymbol(B2, 0, "S2", B2.getSize(), Linkage::Strong, Scope::Default,
 388                      false, false);
 389   G.addDefinedSymbol(B3, 0, "S3", B2.getSize(), Linkage::Strong, Scope::Default,
 390                      false, false);
 391
 392   EXPECT_EQ(G.sections_size(), 3U) << "Expected three sections initially";
 393   EXPECT_EQ(Sec1.blocks_size(), 1U) << "Expected one block in Sec1 initially";
 394   EXPECT_EQ(Sec1.symbols_size(), 1U) << "Expected one symbol in Sec1 initially";
 395   EXPECT_EQ(Sec2.blocks_size(), 1U) << "Expected one block in Sec2 initially";
 396   EXPECT_EQ(Sec2.symbols_size(), 1U) << "Expected one symbol in Sec2 initially";
 397   EXPECT_EQ(Sec3.blocks_size(), 1U) << "Expected one block in Sec3 initially";
 398   EXPECT_EQ(Sec3.symbols_size(), 1U) << "Expected one symbol in Sec3 initially";
 399
 400   // Check that self-merge is a no-op.
 401   G.mergeSections(Sec1, Sec1);
 402
 403   EXPECT_EQ(G.sections_size(), 3U)
 404       << "Expected three sections after first merge";
 405   EXPECT_EQ(Sec1.blocks_size(), 1U)
 406       << "Expected one block in Sec1 after first merge";
 407   EXPECT_EQ(Sec1.symbols_size(), 1U)
 408       << "Expected one symbol in Sec1 after first merge";
 409   EXPECT_EQ(Sec2.blocks_size(), 1U)
 410       << "Expected one block in Sec2 after first merge";
 411   EXPECT_EQ(Sec2.symbols_size(), 1U)
 412       << "Expected one symbol in Sec2 after first merge";
 413   EXPECT_EQ(Sec3.blocks_size(), 1U)
 414       << "Expected one block in Sec3 after first merge";
 415   EXPECT_EQ(Sec3.symbols_size(), 1U)
 416       << "Expected one symbol in Sec3 after first merge";
 417
 418   // Merge Sec2 into Sec1, removing Sec2.
 419   G.mergeSections(Sec1, Sec2);
 420
 421   EXPECT_EQ(G.sections_size(), 2U)
 422       << "Expected two sections after section merge";
 423   EXPECT_EQ(Sec1.blocks_size(), 2U)
 424       << "Expected two blocks in Sec1 after section merge";
 425   EXPECT_EQ(Sec1.symbols_size(), 2U)
 426       << "Expected two symbols in Sec1 after section merge";
 427   EXPECT_EQ(Sec3.blocks_size(), 1U)
 428       << "Expected one block in Sec3 after section merge";
 429   EXPECT_EQ(Sec3.symbols_size(), 1U)
 430       << "Expected one symbol in Sec3 after section merge";
 431
 432   G.mergeSections(Sec1, Sec3, true);
 433
 434   EXPECT_EQ(G.sections_size(), 2U) << "Expected two sections after third merge";
 435   EXPECT_EQ(Sec1.blocks_size(), 3U)
 436       << "Expected three blocks in Sec1 after third merge";
 437   EXPECT_EQ(Sec1.symbols_size(), 3U)
 438       << "Expected three symbols in Sec1 after third merge";
 439   EXPECT_EQ(Sec3.blocks_size(), 0U)
 440       << "Expected one block in Sec3 after third merge";
 441   EXPECT_EQ(Sec3.symbols_size(), 0U)
 442       << "Expected one symbol in Sec3 after third merge";
 443 }
 444
 445 TEST(LinkGraphTest, SplitBlock) {
 446   // Check that the LinkGraph::splitBlock test works as expected.
 447   LinkGraph G("foo", Triple("x86_64-apple-darwin"), 8, support::little,
 448               getGenericEdgeKindName);
 449   auto &Sec = G.createSection("__data", RWFlags);
 450
 451   // Create the block to split.
 452   auto &B1 = G.createContentBlock(Sec, BlockContent, 0x1000, 8, 0);
 453
 454   // Add some symbols to the block.
 455   auto &S1 = G.addDefinedSymbol(B1, 0, "S1", 4, Linkage::Strong, Scope::Default,
 456                                 false, false);
 457   auto &S2 = G.addDefinedSymbol(B1, 4, "S2", 4, Linkage::Strong, Scope::Default,
 458                                 false, false);
 459   auto &S3 = G.addDefinedSymbol(B1, 8, "S3", 4, Linkage::Strong, Scope::Default,
 460                                 false, false);
 461   auto &S4 = G.addDefinedSymbol(B1, 12, "S4", 4, Linkage::Strong,
 462                                 Scope::Default, false, false);
 463
 464   // Add an extra block, EB, and target symbols, and use these to add edges
 465   // from B1 to EB.
 466   auto &EB = G.createContentBlock(Sec, BlockContent, 0x2000, 8, 0);
 467   auto &ES1 = G.addDefinedSymbol(EB, 0, "TS1", 4, Linkage::Strong,
 468                                  Scope::Default, false, false);
 469   auto &ES2 = G.addDefinedSymbol(EB, 4, "TS2", 4, Linkage::Strong,
 470                                  Scope::Default, false, false);
 471   auto &ES3 = G.addDefinedSymbol(EB, 8, "TS3", 4, Linkage::Strong,
 472                                  Scope::Default, false, false);
 473   auto &ES4 = G.addDefinedSymbol(EB, 12, "TS4", 4, Linkage::Strong,
 474                                  Scope::Default, false, false);
 475
 476   // Add edges from B1 to EB.
 477   B1.addEdge(Edge::FirstRelocation, 0, ES1, 0);
 478   B1.addEdge(Edge::FirstRelocation, 4, ES2, 0);
 479   B1.addEdge(Edge::FirstRelocation, 8, ES3, 0);
 480   B1.addEdge(Edge::FirstRelocation, 12, ES4, 0);
 481
 482   // Split B1.
 483   auto &B2 = G.splitBlock(B1, 8);
 484
 485   // Check that the block addresses and content matches what we would expect.
 486   EXPECT_EQ(B1.getAddress(), 0x1008U);
 487   EXPECT_EQ(B1.getContent(), BlockContent.slice(8));
 488
 489   EXPECT_EQ(B2.getAddress(), 0x1000U);
 490   EXPECT_EQ(B2.getContent(), BlockContent.slice(0, 8));
 491
 492   // Check that symbols in B1 were transferred as expected:
 493   // We expect S1 and S2 to have been transferred to B2, and S3 and S4 to have
 494   // remained attached to B1. Symbols S3 and S4 should have had their offsets
 495   // slid to account for the change in address of B2.
 496   EXPECT_EQ(&S1.getBlock(), &B2);
 497   EXPECT_EQ(S1.getOffset(), 0U);
 498
 499   EXPECT_EQ(&S2.getBlock(), &B2);
 500   EXPECT_EQ(S2.getOffset(), 4U);
 501
 502   EXPECT_EQ(&S3.getBlock(), &B1);
 503   EXPECT_EQ(S3.getOffset(), 0U);
 504
 505   EXPECT_EQ(&S4.getBlock(), &B1);
 506   EXPECT_EQ(S4.getOffset(), 4U);
 507
 508   // Check that edges in B1 have been transferred as expected:
 509   // Both blocks should now have two edges each at offsets 0 and 4.
 510   EXPECT_EQ(llvm::size(B1.edges()), 2);
 511   if (size(B1.edges()) == 2) {
 512     auto *E1 = &*B1.edges().begin();
 513     auto *E2 = &*(B1.edges().begin() + 1);
 514     if (E2->getOffset() < E1->getOffset())
 515       std::swap(E1, E2);
 516     EXPECT_EQ(E1->getOffset(), 0U);
 517     EXPECT_EQ(E2->getOffset(), 4U);
 518   }
 519
 520   EXPECT_EQ(llvm::size(B2.edges()), 2);
 521   if (size(B2.edges()) == 2) {
 522     auto *E1 = &*B2.edges().begin();
 523     auto *E2 = &*(B2.edges().begin() + 1);
 524     if (E2->getOffset() < E1->getOffset())
 525       std::swap(E1, E2);
 526     EXPECT_EQ(E1->getOffset(), 0U);
 527     EXPECT_EQ(E2->getOffset(), 4U);
 528   }
 529 }