[JITLink] Fix splitBlock if there are symbols span across the boundary

[steven_wu]

Summary

Fix splitBlock so that it can handle the case when the block being
split has symbols span across the split boundary. This is an error
case in general but for EHFrame splitting on macho platforms, there is an
anonymous symbol that marks the entire block. Current implementation
will leave a symbol that is out of bound of the underlying block. Fix
the problem by dropping such symbols when the block is split.

[dexonsmith]

llvm/lib/ExecutionEngine/JITLink/JITLink.cpp

216–224

This doesn't seem safe in general, since anonymous symbols aren't necessarily safe to split just because they're anonymous.

I wonder if, rather than return Errors, it'd be better to trust the caller and split blocks anyway (as the code was), but truncate Symbol::size() as necessary to avoid it going past the end of the block it points at.

Two other ideas:

• Change the LinkGraph parser to set the symbol size to 0 for symbols that are generated just to allow edges to a block.
• Add a bit to Symbol that says "safe to split", which LinkGraph would set for symbols it generates just to allow edges to a block.

@lhames, WDYT?

[steven_wu]

llvm/lib/ExecutionEngine/JITLink/JITLink.cpp

216–224

So the symbol in question is the one created here:

MachOLinkGraphBuilder::addSectionStartSymAndBlock

I don't know how this one is being used but the one marked eh_frame will become redundant after eh_frame splitting. I guess we can shrink the size of section start sym to have size 0 then we can just always split the block and not worry about that. Then any symbols span across the split boundary will be Error.

[lhames]

I wonder if, rather than return Errors, it'd be better to trust the caller and split blocks anyway (as the code was), but truncate Symbol::size() as necessary to avoid it going past the end of the block it points at.

I like this as a short-term solution.

I think this issue exposes limitations in LinkGraph's current design. I'm not sure that we need/want LLVM-style users-lists for Symbols, but if we just added a ref-count to Symbols we could have a .isUnreferenced method that would be really helpful here: Clients could choose to remove unreferenced anonymous symbols (which should always be safe, since they can be recreated easily), and/or truncate named symbols, and then splitBlock could return an Error for any remaining symbols that extend past a split point.

[steven_wu]

Address review feedback after talking with Lang and Duncan offline.

[steven_wu]

Update the patch to trust user's action and update symbols to fit in the new block

[lhames]

LGTM. Thanks Steven!

llvm/lib/ExecutionEngine/JITLink/JITLink.cpp

if (*Cache == None) {
         return LHS->getOffset() > RHS->getOffset();
       });
     }
     auto &BlockSymbols = **Cache;
 
     // Transfer all symbols with offset less than SplitIndex to NewBlock.
     while (!BlockSymbols.empty() &&
            BlockSymbols.back()->getOffset() < SplitIndex) {
-      BlockSymbols.back()->setBlock(NewBlock);
+      auto *Sym = BlockSymbols.back();
+      // If the symbol extends beyond the split, update the size to be within
+      // the new block.
+      if (Sym->getOffset() + Sym->getSize() > SplitIndex)
+        Sym->setSize(SplitIndex - Sym->getOffset());
+      Sym->setBlock(NewBlock);
       BlockSymbols.pop_back();
     }
 
     // Update offsets for all remaining symbols in B.
     for (auto *Sym : BlockSymbols)
       Sym->setOffset(Sym->getOffset() - SplitIndex);
   }
 
   return NewBlock;
 }
 

llvm/unittests/ExecutionEngine/JITLink/LinkGraphTests.cpp

TEST(LinkGraphTest, SplitBlock) {
   auto &S1 = G.addDefinedSymbol(B1, 0, "S1", 4, Linkage::Strong, Scope::Default,
                                 false, false);
   auto &S2 = G.addDefinedSymbol(B1, 4, "S2", 4, Linkage::Strong, Scope::Default,
                                 false, false);
   auto &S3 = G.addDefinedSymbol(B1, 8, "S3", 4, Linkage::Strong, Scope::Default,
                                 false, false);
   auto &S4 = G.addDefinedSymbol(B1, 12, "S4", 4, Linkage::Strong,
                                 Scope::Default, false, false);
+  // Add a symbol that extends beyond the split.
+  auto &S5 = G.addDefinedSymbol(B1, 0, "S5", 16, Linkage::Strong,
+                                Scope::Default, false, false);
 
   // Add an extra block, EB, and target symbols, and use these to add edges
   // from B1 to EB.
   auto &EB = G.createContentBlock(Sec, BlockContent, 0x2000, 8, 0);
   auto &ES1 = G.addDefinedSymbol(EB, 0, "TS1", 4, Linkage::Strong,
                                  Scope::Default, false, false);
   auto &ES2 = G.addDefinedSymbol(EB, 4, "TS2", 4, Linkage::Strong,
                                  Scope::Default, false, false);
TEST(LinkGraphTest, SplitBlock) {
   EXPECT_EQ(S2.getOffset(), 4U);
 
   EXPECT_EQ(&S3.getBlock(), &B1);
   EXPECT_EQ(S3.getOffset(), 0U);
 
   EXPECT_EQ(&S4.getBlock(), &B1);
   EXPECT_EQ(S4.getOffset(), 4U);
 
+  EXPECT_EQ(&S5.getBlock(), &B2);
+  EXPECT_EQ(S5.getOffset(), 0U);
+  // Size shrinks to fit.
+  EXPECT_EQ(S5.getSize(), 8U);
+
   // Check that edges in B1 have been transferred as expected:
   // Both blocks should now have two edges each at offsets 0 and 4.
   EXPECT_EQ(llvm::size(B1.edges()), 2);
   if (size(B1.edges()) == 2) {
     auto *E1 = &*B1.edges().begin();
     auto *E2 = &*(B1.edges().begin() + 1);
     if (E2->getOffset() < E1->getOffset())
       std::swap(E1, E2);