diff --git a/llvm/include/llvm/IR/BasicBlock.h b/llvm/include/llvm/IR/BasicBlock.h --- a/llvm/include/llvm/IR/BasicBlock.h +++ b/llvm/include/llvm/IR/BasicBlock.h @@ -453,6 +453,28 @@ return splitBasicBlockBefore(I->getIterator(), BBName); } + /// Transfer all instructions from \p FromBB to this basic block at \p ToIt. + void splice(BasicBlock::iterator ToIt, BasicBlock *FromBB) { + splice(ToIt, FromBB, FromBB->begin(), FromBB->end()); + } + + /// Transfer one instruction from \p FromBB at \p FromIt to this basic block + /// at \p ToIt. + void splice(BasicBlock::iterator ToIt, BasicBlock *FromBB, + BasicBlock::iterator FromIt) { + auto FromItNext = std::next(FromIt); + // Single-element splice is a noop if destination == source. + if (ToIt == FromIt || ToIt == FromItNext) + return; + splice(ToIt, FromBB, FromIt, FromItNext); + } + + /// Transfer a range of instructions that belong to \p FromBB from \p + /// FromBeginIt to \p FromEndIt, to this basic block at \p ToIt. + void splice(BasicBlock::iterator ToIt, BasicBlock *FromBB, + BasicBlock::iterator FromBeginIt, + BasicBlock::iterator FromEndIt); + /// Returns true if there are any uses of this basic block other than /// direct branches, switches, etc. to it. bool hasAddressTaken() const { diff --git a/llvm/lib/IR/BasicBlock.cpp b/llvm/lib/IR/BasicBlock.cpp --- a/llvm/lib/IR/BasicBlock.cpp +++ b/llvm/lib/IR/BasicBlock.cpp @@ -468,6 +468,18 @@ return New; } +void BasicBlock::splice(BasicBlock::iterator ToIt, BasicBlock *FromBB, + BasicBlock::iterator FromBeginIt, + BasicBlock::iterator FromEndIt) { +#ifdef EXPENSIVE_CHECKS + // Check that FromBeginIt is befor FromEndIt. + auto FromBBEnd = FromBB->end(); + for (auto It = FromBeginIt; It != FromEndIt; ++It) + assert(It != FromBBEnd && "FromBeginIt not before FromEndIt!"); +#endif // EXPENSIVE_CHECKS + getInstList().splice(ToIt, FromBB->getInstList(), FromBeginIt, FromEndIt); +} + void BasicBlock::replacePhiUsesWith(BasicBlock *Old, BasicBlock *New) { // N.B. This might not be a complete BasicBlock, so don't assume // that it ends with a non-phi instruction. diff --git a/llvm/unittests/IR/BasicBlockTest.cpp b/llvm/unittests/IR/BasicBlockTest.cpp --- a/llvm/unittests/IR/BasicBlockTest.cpp +++ b/llvm/unittests/IR/BasicBlockTest.cpp @@ -260,5 +260,252 @@ EXPECT_EQ(std::next(I1->getIterator()), I3->getIterator()); } +static std::unique_ptr parseIR(LLVMContext &C, const char *IR) { + SMDiagnostic Err; + std::unique_ptr Mod = parseAssemblyString(IR, Err, C); + if (!Mod) + Err.print(__FILE__, errs()); + return Mod; +} + +TEST(BasicBlockTest, SpliceFromBB) { + LLVMContext Ctx; + std::unique_ptr M = parseIR(Ctx, R"( + define void @f(i32 %a) { + from: + %fromInstr1 = add i32 %a, %a + %fromInstr2 = sub i32 %a, %a + br label %to + + to: + %toInstr1 = mul i32 %a, %a + %toInstr2 = sdiv i32 %a, %a + ret void + } +)"); + Function *F = &*M->begin(); + auto BBIt = F->begin(); + BasicBlock *FromBB = &*BBIt++; + BasicBlock *ToBB = &*BBIt++; + + auto FromBBIt = FromBB->begin(); + Instruction *FromI1 = &*FromBBIt++; + Instruction *FromI2 = &*FromBBIt++; + Instruction *FromBr = &*FromBBIt++; + + auto ToBBIt = ToBB->begin(); + Instruction *ToI1 = &*ToBBIt++; + Instruction *ToI2 = &*ToBBIt++; + Instruction *ToRet = &*ToBBIt++; + ToBB->splice(ToI1->getIterator(), FromBB); + + EXPECT_TRUE(FromBB->empty()); + + auto It = ToBB->begin(); + EXPECT_EQ(&*It++, FromI1); + EXPECT_EQ(&*It++, FromI2); + EXPECT_EQ(&*It++, FromBr); + EXPECT_EQ(&*It++, ToI1); + EXPECT_EQ(&*It++, ToI2); + EXPECT_EQ(&*It++, ToRet); +} + +TEST(BasicBlockTest, SpliceOneInstr) { + LLVMContext Ctx; + std::unique_ptr M = parseIR(Ctx, R"( + define void @f(i32 %a) { + from: + %fromInstr1 = add i32 %a, %a + %fromInstr2 = sub i32 %a, %a + br label %to + + to: + %toInstr1 = mul i32 %a, %a + %toInstr2 = sdiv i32 %a, %a + ret void + } +)"); + Function *F = &*M->begin(); + auto BBIt = F->begin(); + BasicBlock *FromBB = &*BBIt++; + BasicBlock *ToBB = &*BBIt++; + + auto FromBBIt = FromBB->begin(); + Instruction *FromI1 = &*FromBBIt++; + Instruction *FromI2 = &*FromBBIt++; + Instruction *FromBr = &*FromBBIt++; + + auto ToBBIt = ToBB->begin(); + Instruction *ToI1 = &*ToBBIt++; + Instruction *ToI2 = &*ToBBIt++; + Instruction *ToRet = &*ToBBIt++; + ToBB->splice(ToI1->getIterator(), FromBB, FromI2->getIterator()); + + EXPECT_EQ(FromBB->size(), 2u); + EXPECT_EQ(ToBB->size(), 4u); + + auto It = FromBB->begin(); + EXPECT_EQ(&*It++, FromI1); + EXPECT_EQ(&*It++, FromBr); + + It = ToBB->begin(); + EXPECT_EQ(&*It++, FromI2); + EXPECT_EQ(&*It++, ToI1); + EXPECT_EQ(&*It++, ToI2); + EXPECT_EQ(&*It++, ToRet); +} + +TEST(BasicBlockTest, SpliceOneInstrWhenFromIsSameAsTo) { + LLVMContext Ctx; + std::unique_ptr M = parseIR(Ctx, R"( + define void @f(i32 %a) { + bb: + %instr1 = add i32 %a, %a + %instr2 = sub i32 %a, %a + ret void + } +)"); + Function *F = &*M->begin(); + auto BBIt = F->begin(); + BasicBlock *BB = &*BBIt++; + + auto It = BB->begin(); + Instruction *Instr1 = &*It++; + Instruction *Instr2 = &*It++; + Instruction *Ret = &*It++; + + // According to ilist's splice() a single-element splice where dst == src + // should be a noop. + BB->splice(Instr1->getIterator(), BB, Instr1->getIterator()); + + It = BB->begin(); + EXPECT_EQ(&*It++, Instr1); + EXPECT_EQ(&*It++, Instr2); + EXPECT_EQ(&*It++, Ret); + EXPECT_EQ(BB->size(), 3u); +} + +TEST(BasicBlockTest, SpliceLastInstr) { + LLVMContext Ctx; + std::unique_ptr M = parseIR(Ctx, R"( + define void @f(i32 %a) { + from: + %fromInstr1 = add i32 %a, %a + %fromInstr2 = sub i32 %a, %a + br label %to + + to: + %toInstr1 = mul i32 %a, %a + %toInstr2 = sdiv i32 %a, %a + ret void + } +)"); + Function *F = &*M->begin(); + auto BBIt = F->begin(); + BasicBlock *FromBB = &*BBIt++; + BasicBlock *ToBB = &*BBIt++; + + auto FromBBIt = FromBB->begin(); + Instruction *FromI1 = &*FromBBIt++; + Instruction *FromI2 = &*FromBBIt++; + Instruction *FromBr = &*FromBBIt++; + + auto ToBBIt = ToBB->begin(); + Instruction *ToI1 = &*ToBBIt++; + Instruction *ToI2 = &*ToBBIt++; + Instruction *ToRet = &*ToBBIt++; + ToBB->splice(ToI1->getIterator(), FromBB, FromI2->getIterator(), + FromBr->getIterator()); + + EXPECT_EQ(FromBB->size(), 2u); + auto It = FromBB->begin(); + EXPECT_EQ(&*It++, FromI1); + EXPECT_EQ(&*It++, FromBr); + + EXPECT_EQ(ToBB->size(), 4u); + It = ToBB->begin(); + EXPECT_EQ(&*It++, FromI2); + EXPECT_EQ(&*It++, ToI1); + EXPECT_EQ(&*It++, ToI2); + EXPECT_EQ(&*It++, ToRet); +} + +TEST(BasicBlockTest, SpliceInstrRange) { + LLVMContext Ctx; + std::unique_ptr M = parseIR(Ctx, R"( + define void @f(i32 %a) { + from: + %fromInstr1 = add i32 %a, %a + %fromInstr2 = sub i32 %a, %a + br label %to + + to: + %toInstr1 = mul i32 %a, %a + %toInstr2 = sdiv i32 %a, %a + ret void + } +)"); + Function *F = &*M->begin(); + auto BBIt = F->begin(); + BasicBlock *FromBB = &*BBIt++; + BasicBlock *ToBB = &*BBIt++; + + auto FromBBIt = FromBB->begin(); + Instruction *FromI1 = &*FromBBIt++; + Instruction *FromI2 = &*FromBBIt++; + Instruction *FromBr = &*FromBBIt++; + + auto ToBBIt = ToBB->begin(); + Instruction *ToI1 = &*ToBBIt++; + Instruction *ToI2 = &*ToBBIt++; + Instruction *ToRet = &*ToBBIt++; + ToBB->splice(ToI2->getIterator(), FromBB, FromBB->begin(), FromBB->end()); + + EXPECT_EQ(FromBB->size(), 0u); + + EXPECT_EQ(ToBB->size(), 6u); + auto It = ToBB->begin(); + EXPECT_EQ(&*It++, ToI1); + EXPECT_EQ(&*It++, FromI1); + EXPECT_EQ(&*It++, FromI2); + EXPECT_EQ(&*It++, FromBr); + EXPECT_EQ(&*It++, ToI2); + EXPECT_EQ(&*It++, ToRet); +} + +#ifdef EXPENSIVE_CHECKS +TEST(BasicBlockTest, SpliceEndBeforeBegin) { + LLVMContext Ctx; + std::unique_ptr M = parseIR(Ctx, R"( + define void @f(i32 %a) { + from: + %fromInstr1 = add i32 %a, %a + %fromInstr2 = sub i32 %a, %a + br label %to + + to: + %toInstr1 = mul i32 %a, %a + %toInstr2 = sdiv i32 %a, %a + ret void + } +)"); + Function *F = &*M->begin(); + auto BBIt = F->begin(); + BasicBlock *FromBB = &*BBIt++; + BasicBlock *ToBB = &*BBIt++; + + auto FromBBIt = FromBB->begin(); + Instruction *FromI1 = &*FromBBIt++; + Instruction *FromI2 = &*FromBBIt++; + + auto ToBBIt = ToBB->begin(); + Instruction *ToI2 = &*ToBBIt++; + + EXPECT_DEATH(ToBB->splice(ToI2->getIterator(), FromBB, FromI2->getIterator(), + FromI1->getIterator()), + "FromBeginIt not before FromEndIt!"); +} +#endif //EXPENSIVE_CHECKS + } // End anonymous namespace. } // End llvm namespace.