[IR][NFC] Adds BasicBlock::splice().

[vporpo]

Summary

Currently the only way to do this is to work with the instruction list directly.
This is part of a series of cleanup patches towards making BasicBlock::getInstList() private.

[aeubanks]

llvm/include/llvm/IR/BasicBlock.h

466

should add a test for this, e.g. splice(I1, I2) where I1 is right before I2 in the same block

llvm/unittests/IR/BasicBlockTest.cpp

386

this name is confusing, not sure what it's referring to

415

perhaps also test when we splice more than one instruction this way? e.g. FromI1 instead

[aeubanks]

llvm/include/llvm/IR/BasicBlock.h

466

and does the actual implementation not handle this?

[vporpo]

llvm/include/llvm/IR/BasicBlock.h

466

I am not sure. Since I am basically calling splice() internally I was relying on it being well tested. But anyway, since this is part of the BB API now, I agree that it needs a test.

llvm/unittests/IR/BasicBlockTest.cpp

386

Yeah good point.
I think I will also rename the arguments of BasicBlock::splice because Last actually refers to the iterator after tha last one. So End is a better name for it.

415

Agreed

[aeubanks]

llvm/include/llvm/IR/BasicBlock.h

466

if getInstList().splice() already handles this, then I'd say no need for this early return. would be good to double check

[vporpo]

llvm/include/llvm/IR/BasicBlock.h

466

I just checked and it won't handle this, but I don't think we can handle this either. The current behavior is that it just crashes when the iterator goes out of bounds as it never finds the End iterator. I added a test that confirms the crash.

I don't think we can handle this any better. We could add a linear-time check to test whether BeginIt is before EndIt, but I am not sure it is worth it. What do you think?

[vporpo]

Updated test names, splice() argument names and added test for EndIt before BeginIt.

[aeubanks]

llvm/include/llvm/IR/BasicBlock.h

466

I think adding an assert, even if it's linear time, would be good to help future users. can add it under expensive checks (and gate the death test too) if it's too expensive in assert builds

[vporpo]

Added expensive check that tests whether FromBeginIt is before FromEndIt.

[vporpo]

llvm/include/llvm/IR/BasicBlock.h

466

Yes the ilist splice already early returns if the iterators are equal. I removed the check from BasicBlock::splice(). I will update the patch.

[vporpo]

llvm/include/llvm/IR/BasicBlock.h

466

Hmm turns out that not all ilist splice functions check this:

void splice(iterator where, iplist_impl &L2, iterator first) {
  iterator last = first; ++last;
  if (where == first || where == last) return; // No change                                                                                                                    
  transfer(where, L2, first, last);
}
void splice(iterator where, iplist_impl &L2, iterator first, iterator last) {
  if (first != last) transfer(where, L2, first, last);
}

I am calling the second one which does not check where == first or where == last and it crashes.
I can't think of a reason why the check should be missing. I will create a separate patch for this.

[vporpo]

llvm/include/llvm/IR/BasicBlock.h

466

There seems to be a discrepancy in the way ilist's splice() works. The single-element splice() accepts a destination that is equal to the source. There is even a test on this TEST(IListTest, SpliceOne) which checks it. The multi-element splice() will crash, even if it is transferring only one element. There seems to be a lot of code relying on that, so changing this behavior needs some extended cleanup.

I think we should try to maintain this functionality for BB splice(), so we should keep the early exit check`if (ToIt == FromIt || ToIt == FromItLast)` in BasicBlock's single-element splice().

[vporpo]

Added the early-return check that I removed in a previous version.

[aeubanks]

llvm/include/llvm/IR/BasicBlock.h

466

in that case can't we just forward every call to getInstList().splice(..., From->getInstList(), ...) rather than going through the newly added 4 param BasicBlock::splice()? Or do you want to funnel then all through one method so you can keep track of all splice calls more easily?

[vporpo]

llvm/include/llvm/IR/BasicBlock.h

466

Yes, my intention was to funnel them into a single call. But either way is fine. Which one do you think is better?

[aeubanks]

llvm/include/llvm/IR/BasicBlock.h

466

it depends on how much extra work it is to keep track of 3 splice methods, vs the (admittedly very minor) duplication here with the ilist splice calls. up to you, I'll lgtm this patch either way

[vporpo]

llvm/include/llvm/IR/BasicBlock.h

466

OK let's keep it as it is then. Thanks for the review!

llvm/include/llvm/IR/BasicBlock.h

public:
   /// Also note that this doesn't preserve any passes. To split blocks while
   /// keeping loop information consistent, use the SplitBlockBefore utility
   /// function.
   BasicBlock *splitBasicBlockBefore(iterator I, const Twine &BBName = "");
   BasicBlock *splitBasicBlockBefore(Instruction *I, const Twine &BBName = "") {
     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 {
     return getBasicBlockBits().BlockAddressRefCount != 0;
   }
 
   /// Update all phi nodes in this basic block to refer to basic block \p New
   /// instead of basic block \p Old.

llvm/lib/IR/BasicBlock.cpp

BasicBlock *BasicBlock::splitBasicBlockBefore(iterator I, const Twine &BBName) {
   }
   // Add a branch instruction from  "New" to "this" Block.
   BranchInst *BI = BranchInst::Create(this, New);
   BI->setDebugLoc(Loc);
 
   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.
   for (Instruction &I : *this) {
     PHINode *PN = dyn_cast<PHINode>(&I);
     if (!PN)
       break;
     PN->replaceIncomingBlockWith(Old, New);

llvm/unittests/IR/BasicBlockTest.cpp

TEST_F(InstrOrderInvalidationTest, EraseNoInvalidation) {
   // Removing does not invalidate instruction order.
   I2->eraseFromParent();
   I2 = nullptr;
   EXPECT_TRUE(BB->isInstrOrderValid());
   EXPECT_TRUE(I1->comesBefore(I3));
   EXPECT_EQ(std::next(I1->getIterator()), I3->getIterator());
 }
 
+static std::unique_ptr<Module> parseIR(LLVMContext &C, const char *IR) {
+  SMDiagnostic Err;
+  std::unique_ptr<Module> Mod = parseAssemblyString(IR, Err, C);
+  if (!Mod)
+    Err.print(__FILE__, errs());
+  return Mod;
+}
+
+TEST(BasicBlockTest, SpliceFromBB) {
+  LLVMContext Ctx;
+  std::unique_ptr<Module> 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<Module> 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<Module> 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<Module> 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<Module> 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<Module> 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.