How to insert a basic block between two block in LLVM

Question

This is similar to Inserting a block between two blocks in LLVM however the solution description is unclear to me - or better - I tried to do it like described but it does not work (for me).

What I want to do: Wherever a basic block has more then one successor, I want to insert a basic block. So if basic block A does a conditional jump to B or C, I want to insert a basic block between A and B and between A and C. And it should also work if there is a jump table.

So what I do is:

while (...) {
  // get next basic block and ensure it has at least 2 successors:
  BasicBlock *origBB = getNextBB();
  Instruction *TI = origBB->getTerminator()
  if (!TI || TI->getNumSuccessors() < 2)
    continue;

  // collect successors:
  std::vector Successors;
  for (succ_iterator SI = succ_begin(origBB), SE = succ_end(origBB); SI != SE; ++SI) {
     BasicBlock *succ = *SI;
     Successors.push_back(succ);
  }

  // now for each successor:
  for (uint32_t i = 0; i < Successors.size(); i++) {
    // Create a new basic block
    BasicBlock *BB = BasicBlock::Create(C, "", &F, nullptr);
    // F.getBasicBlockList().push_back(BB); <= this did not work, seem to result in endless loop
    IRBuilder<> IRB(BB);
    // put instructions into BB
    ... // omitted
    // then add the terminator:
    IRB.CreateBr(Successors[i]);

    // Now we have to fix the original BB to our new basic block:
    TI->setSuccessor(i, BB);
  }
}

When I run this LLVM pass I get the following error: PHI node entries do not match predecessors!

OK so I thought I have to remove the corresponding predecessor from the successor and added the following code after the setSuccessor():

origBB->replaceSuccessorsPhiUsesWith(Successors[j], BB);
BasicBlock *S = Successors[i];
S->removePredecessor(origBB);

Then however I get the error Instruction does not dominate all uses!

I am sure the solution is very simple - but I cannot find it :-(

Thanks a lot for any help or pointers!

user_12908721 · Answer

OK I am anwsering my own question here.

The comment proposing a) using splitBlock() is going into the wrong direction as it is about inserting into an edge so the result would be wrong. b) updating the phi would actually solve the issue. However this is very complex as a simple replacePhiUsesWith cannot be used - the case where A->B and A is a loop head and B a loob tail (so going back to B) will result in a compilation error, so all phis have to be carefully evaluated.

So the solution is actually very simple, which I found browsing through the source code of llvm: SplitEdge(). It does exactly what I want, inserting a a basic block between the edge of two basic blocks!

It is not obvious as the function is not documented in the doxygen class list, so other than by browsing sources and includes it cannot be found.

So here how to use it:

#include "llvm/Transforms/Utils/BasicBlockUtils.h"

void inYourFunction() {

   ...
   // Insert the new block into the edge between thisBB and a successorBB
   BasicBlock *insertedBB = SplitEdge(thisBB, successorBB);
   if (!insertedBB) {
     // SplitEdge can fail, e.g. if the successor is a landing pad
     return;
   }
   // Then put instructions into the new BB
   BasicBlock::iterator IP = newBB->getFirstInsertionPt();
   IRBuilder<>          IRB(&(*IP));
   // and then work with IRB
   // You need not to take care of the branch to successorBB - it is already there
   ...

}

Thats it, its that simple.

How to insert a basic block between two block in LLVM

1 Answers