diff --git a/llvm/include/llvm/IR/Function.h b/llvm/include/llvm/IR/Function.h --- a/llvm/include/llvm/IR/Function.h +++ b/llvm/include/llvm/IR/Function.h @@ -693,6 +693,28 @@ 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. /// diff --git a/llvm/lib/IR/Function.cpp b/llvm/lib/IR/Function.cpp --- a/llvm/lib/IR/Function.cpp +++ b/llvm/lib/IR/Function.cpp @@ -368,6 +368,18 @@ 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 //===----------------------------------------------------------------------===// diff --git a/llvm/unittests/IR/FunctionTest.cpp b/llvm/unittests/IR/FunctionTest.cpp --- a/llvm/unittests/IR/FunctionTest.cpp +++ b/llvm/unittests/IR/FunctionTest.cpp @@ -239,4 +239,211 @@ EXPECT_EQ(It, FooBB0->getIterator()); } +TEST(FunctionTest, SpliceOneBB) { + LLVMContext Ctx; + std::unique_ptr 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 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 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 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 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