[IR] Adds Function::splice() member functions.

[vporpo]

Summary

This is part of a series of patches that aim at making Function::getBasicBlockList() private.

[vporpo]

Removed the splice() variant that inserts a single block.
It has the same functionality as Function::insertBasicBlockAt().

[aeubanks]

going to assume this is basically the same as the instruction splicing patch and not look at it too closely :)

[vporpo]

yes it is very similar

[RKSimon]

llvm/lib/IR/Function.cpp

378

@vporpo This is breaking on EXPENSIVE_CHECKS builds - FromBBEnd -> FromFEnd ?

[vporpo]

llvm/lib/IR/Function.cpp

378

Ooops let me fix it forward. Thanks!

[vporpo]

llvm/lib/IR/Function.cpp

378

I just pushed the fix: 66440a46b172c99399e3456a86b9e54d27ae51d0

[RKSimon]

Thanks - I'm also seeing a few unused variable warnings

llvm/unittests/IR/FunctionTest.cpp

442

I'm also seeing these build warnings:

E:\llvm\llvm-project\llvm\unittests\IR\FunctionTest.cpp(442): warning C4189: 'ToBB3': local variable is initialized but not referenced
E:\llvm\llvm-project\llvm\unittests\IR\FunctionTest.cpp(440): warning C4189: 'ToBB1': local variable is initialized but not referenced
E:\llvm\llvm-project\llvm\unittests\IR\FunctionTest.cpp(437): warning C4189: 'FromBB3': local variable is initialized but not referenced

[vporpo]

llvm/unittests/IR/FunctionTest.cpp

442

Just pushed the patch for these too 9eb5d9cbe9e53d16dbedf922259ae3643d919603. Thanks!

[RKSimon]

Thanks @vporpo !

llvm/include/llvm/IR/Function.h

public:
   void stealArgumentListFrom(Function &Src);
 
   /// Insert \p BB in the basic block list at \p Position. \Returns an iterator
   /// to the newly inserted BB.
   Function::iterator insertBasicBlockAt(Function::iterator Position, BasicBlock *BB) {
     return BasicBlocks.insert(Position, BB);
   }
 
+  /// Transfer all blocks from \p FromF to this function at \p ToIt.
+  void splice(Function::iterator ToIt, Function *FromF) {
+    splice(ToIt, FromF, FromF->begin(), FromF->end());
+  }
+
+  /// Transfer one BasicBlock from \p FromF at \p FromIt to this function
+  /// at \p ToIt.
+  void splice(Function::iterator ToIt, Function *FromF,
+              Function::iterator FromIt) {
+    auto FromItNext = std::next(FromIt);
+    // Single-element splice is a noop if destination == source.
+    if (ToIt == FromIt || ToIt == FromItNext)
+      return;
+    splice(ToIt, FromF, FromIt, FromItNext);
+  }
+
+  /// Transfer a range of basic blocks that belong to \p FromF from \p
+  /// FromBeginIt to \p FromEndIt, to this function at \p ToIt.
+  void splice(Function::iterator ToIt, Function *FromF,
+              Function::iterator FromBeginIt,
+              Function::iterator FromEndIt);
+
   /// Get the underlying elements of the Function... the basic block list is
   /// empty for external functions.
   ///
   const BasicBlockListType &getBasicBlockList() const { return BasicBlocks; }
         BasicBlockListType &getBasicBlockList()       { return BasicBlocks; }
 
   static BasicBlockListType Function::*getSublistAccess(BasicBlock*) {
     return &Function::BasicBlocks;

llvm/lib/IR/Function.cpp

 void Function::removeFromParent() {
   getParent()->getFunctionList().remove(getIterator());
 }
 
 void Function::eraseFromParent() {
   getParent()->getFunctionList().erase(getIterator());
 }
 
+void Function::splice(Function::iterator ToIt, Function *FromF,
+                      Function::iterator FromBeginIt,
+                      Function::iterator FromEndIt) {
+#ifdef EXPENSIVE_CHECKS
+  // Check that FromBeginIt is before FromEndIt.
+  auto FromFEnd = FromF->end();
+  for (auto It = FromBeginIt; It != FromEndIt; ++It)
+    assert(It != FromBBEnd && "FromBeginIt not before FromEndIt!");
+#endif // EXPENSIVE_CHECKS
+  BasicBlocks.splice(ToIt, FromF->BasicBlocks, FromBeginIt, FromEndIt);
+}
+
 //===----------------------------------------------------------------------===//
 // Function Implementation
 //===----------------------------------------------------------------------===//
 
 static unsigned computeAddrSpace(unsigned AddrSpace, Module *M) {
   // If AS == -1 and we are passed a valid module pointer we place the function
   // in the program address space. Otherwise we default to AS0.
   if (AddrSpace == static_cast<unsigned>(-1))

llvm/unittests/IR/FunctionTest.cpp

)");
   // Insert foo_bb0 into bar() just before bar_bb2.
   FooBB0->removeFromParent();
   It = BarF->insertBasicBlockAt(BarBB2->getIterator(), FooBB0);
   EXPECT_EQ(FooBB0->getPrevNode(), BarBB1);
   EXPECT_EQ(FooBB0->getNextNode(), BarBB2);
   EXPECT_EQ(It, FooBB0->getIterator());
 }
 
+TEST(FunctionTest, SpliceOneBB) {
+  LLVMContext Ctx;
+  std::unique_ptr<Module> M = parseIR(Ctx, R"(
+    define void @from() {
+     from_bb1:
+       br label %from_bb2
+     from_bb2:
+       br label %from_bb3
+     from_bb3:
+       ret void
+    }
+    define void @to() {
+     to_bb1:
+       br label %to_bb2
+     to_bb2:
+       br label %to_bb3
+     to_bb3:
+       ret void
+    }
+)");
+  Function *FromF = M->getFunction("from");
+  BasicBlock *FromBB1 = getBBWithName(FromF, "from_bb1");
+  BasicBlock *FromBB2 = getBBWithName(FromF, "from_bb2");
+  BasicBlock *FromBB3 = getBBWithName(FromF, "from_bb3");
+
+  Function *ToF = M->getFunction("to");
+  BasicBlock *ToBB1 = getBBWithName(ToF, "to_bb1");
+  BasicBlock *ToBB2 = getBBWithName(ToF, "to_bb2");
+  BasicBlock *ToBB3 = getBBWithName(ToF, "to_bb3");
+
+  // Move from_bb2 before to_bb1.
+  ToF->splice(ToBB1->getIterator(), FromF, FromBB2->getIterator());
+  EXPECT_EQ(FromF->size(), 2u);
+  EXPECT_EQ(ToF->size(), 4u);
+
+  auto It = FromF->begin();
+  EXPECT_EQ(&*It++, FromBB1);
+  EXPECT_EQ(&*It++, FromBB3);
+
+  It = ToF->begin();
+  EXPECT_EQ(&*It++, FromBB2);
+  EXPECT_EQ(&*It++, ToBB1);
+  EXPECT_EQ(&*It++, ToBB2);
+  EXPECT_EQ(&*It++, ToBB3);
+
+  // Cleanup to avoid "Uses remain when a value is destroyed!".
+  FromF->splice(FromBB3->getIterator(), ToF, FromBB2->getIterator());
+}
+
+TEST(FunctionTest, SpliceOneBBWhenFromIsSameAsTo) {
+  LLVMContext Ctx;
+  std::unique_ptr<Module> M = parseIR(Ctx, R"(
+    define void @fromto() {
+     bb1:
+       br label %bb2
+     bb2:
+       ret void
+    }
+)");
+  Function *F = M->getFunction("fromto");
+  BasicBlock *BB1 = getBBWithName(F, "bb1");
+  BasicBlock *BB2 = getBBWithName(F, "bb2");
+
+  // According to ilist's splice() a single-element splice where dst == src
+  // should be a noop.
+  F->splice(BB1->getIterator(), F, BB1->getIterator());
+
+  auto It = F->begin();
+  EXPECT_EQ(&*It++, BB1);
+  EXPECT_EQ(&*It++, BB2);
+  EXPECT_EQ(F->size(), 2u);
+}
+
+TEST(FunctionTest, SpliceLastBB) {
+  LLVMContext Ctx;
+  std::unique_ptr<Module> M = parseIR(Ctx, R"(
+    define void @from() {
+     from_bb1:
+       br label %from_bb2
+     from_bb2:
+       br label %from_bb3
+     from_bb3:
+       ret void
+    }
+    define void @to() {
+     to_bb1:
+       br label %to_bb2
+     to_bb2:
+       br label %to_bb3
+     to_bb3:
+       ret void
+    }
+)");
+
+  Function *FromF = M->getFunction("from");
+  BasicBlock *FromBB1 = getBBWithName(FromF, "from_bb1");
+  BasicBlock *FromBB2 = getBBWithName(FromF, "from_bb2");
+  BasicBlock *FromBB3 = getBBWithName(FromF, "from_bb3");
+
+  Function *ToF = M->getFunction("to");
+  BasicBlock *ToBB1 = getBBWithName(ToF, "to_bb1");
+  BasicBlock *ToBB2 = getBBWithName(ToF, "to_bb2");
+  BasicBlock *ToBB3 = getBBWithName(ToF, "to_bb3");
+
+  // Move from_bb2 before to_bb1.
+  auto ToMove = FromBB2->getIterator();
+  ToF->splice(ToBB1->getIterator(), FromF, ToMove, std::next(ToMove));
+
+  EXPECT_EQ(FromF->size(), 2u);
+  auto It = FromF->begin();
+  EXPECT_EQ(&*It++, FromBB1);
+  EXPECT_EQ(&*It++, FromBB3);
+
+  EXPECT_EQ(ToF->size(), 4u);
+  It = ToF->begin();
+  EXPECT_EQ(&*It++, FromBB2);
+  EXPECT_EQ(&*It++, ToBB1);
+  EXPECT_EQ(&*It++, ToBB2);
+  EXPECT_EQ(&*It++, ToBB3);
+
+  // Cleanup to avoid "Uses remain when a value is destroyed!".
+  FromF->splice(FromBB3->getIterator(), ToF, ToMove);
+}
+
+TEST(FunctionTest, SpliceBBRange) {
+  LLVMContext Ctx;
+  std::unique_ptr<Module> M = parseIR(Ctx, R"(
+    define void @from() {
+     from_bb1:
+       br label %from_bb2
+     from_bb2:
+       br label %from_bb3
+     from_bb3:
+       ret void
+    }
+    define void @to() {
+     to_bb1:
+       br label %to_bb2
+     to_bb2:
+       br label %to_bb3
+     to_bb3:
+       ret void
+    }
+)");
+
+  Function *FromF = M->getFunction("from");
+  BasicBlock *FromBB1 = getBBWithName(FromF, "from_bb1");
+  BasicBlock *FromBB2 = getBBWithName(FromF, "from_bb2");
+  BasicBlock *FromBB3 = getBBWithName(FromF, "from_bb3");
+
+  Function *ToF = M->getFunction("to");
+  BasicBlock *ToBB1 = getBBWithName(ToF, "to_bb1");
+  BasicBlock *ToBB2 = getBBWithName(ToF, "to_bb2");
+  BasicBlock *ToBB3 = getBBWithName(ToF, "to_bb3");
+
+  // Move all BBs from @from to @to.
+  ToF->splice(ToBB2->getIterator(), FromF, FromF->begin(), FromF->end());
+
+  EXPECT_EQ(FromF->size(), 0u);
+
+  EXPECT_EQ(ToF->size(), 6u);
+  auto It = ToF->begin();
+  EXPECT_EQ(&*It++, ToBB1);
+  EXPECT_EQ(&*It++, FromBB1);
+  EXPECT_EQ(&*It++, FromBB2);
+  EXPECT_EQ(&*It++, FromBB3);
+  EXPECT_EQ(&*It++, ToBB2);
+  EXPECT_EQ(&*It++, ToBB3);
+}
+
+#ifdef EXPENSIVE_CHECKS
+TEST(FunctionTest, SpliceEndBeforeBegin) {
+  LLVMContext Ctx;
+  std::unique_ptr<Module> M = parseIR(Ctx, R"(
+    define void @from() {
+     from_bb1:
+       br label %from_bb2
+     from_bb2:
+       br label %from_bb3
+     from_bb3:
+       ret void
+    }
+    define void @to() {
+     to_bb1:
+       br label %to_bb2
+     to_bb2:
+       br label %to_bb3
+     to_bb3:
+       ret void
+    }
+)");
+
+  Function *FromF = M->getFunction("from");
+  BasicBlock *FromBB1 = getBBWithName(FromF, "from_bb1");
+  BasicBlock *FromBB2 = getBBWithName(FromF, "from_bb2");
+  BasicBlock *FromBB3 = getBBWithName(FromF, "from_bb3");
+
+  Function *ToF = M->getFunction("to");
+  BasicBlock *ToBB1 = getBBWithName(ToF, "to_bb1");
+  BasicBlock *ToBB2 = getBBWithName(ToF, "to_bb2");
+  BasicBlock *ToBB3 = getBBWithName(ToF, "to_bb3");
+
+  EXPECT_DEATH(ToF->splice(ToBB2->getIterator(), FromF, FromBB2->getIterator(),
+                           FromBB1->getIterator()),
+               "FromBeginIt not before FromEndIt!");
+}
+#endif //EXPENSIVE_CHECKS
 } // end namespace