How to remove unused basicblocks llvm

Question

I'm trying to remove unused blocks from llvm intermediate code.

First, I build a collection of reachable basicblocks, by starting with the entry basicblock and adding all basicblock successors from their terminator instruction:

bbset.insert(bbterm->getSuccessor(i));

After that, I iterate through the unreachable basicblocks and delete them using

DeleteDeadBlock(bb);

from Utils/BasicBlockUtils.cpp

It works, but in some scenarios I get a segfault. Below is the core dump:

opt: /home/user/llvm-3.3.src/lib/Transforms/Utils/BasicBlockUtils.cpp:38: void llvm::DeleteDeadBlock(llvm::BasicBlock*): Assertion `(pred_begin(BB) == pred_end(BB) || BB->getSinglePredecessor() == BB) && "Block is not dead!"' failed.
0  opt             0x0000000001756825 llvm::sys::PrintStackTrace(_IO_FILE*) + 38
1  opt             0x0000000001756aa2
2  opt             0x000000000175651e
3  libpthread.so.0 0x00007fe1fe76dbb0
4  libc.so.6       0x00007fe1fdbaef77 gsignal + 55
5  libc.so.6       0x00007fe1fdbb25e8 abort + 328
6  libc.so.6       0x00007fe1fdba7d43
7  libc.so.6       0x00007fe1fdba7df2
8  opt             0x000000000138b004 llvm::DeleteDeadBlock(llvm::BasicBlock*) + 139
9  opt             0x0000000000d49c2e
10 opt             0x0000000001652942 llvm::FPPassManager::runOnFunction(llvm::Function&) + 290
11 opt             0x0000000001652ab2 llvm::FPPassManager::runOnModule(llvm::Module&) + 84
12 opt             0x0000000001652dd0 llvm::MPPassManager::runOnModule(llvm::Module&) + 502
13 opt             0x00000000016533a0 llvm::PassManagerImpl::run(llvm::Module&) + 244
14 opt             0x00000000016535ab llvm::PassManager::run(llvm::Module&) + 39
15 opt             0x00000000008c6cb6 main + 5698
16 libc.so.6       0x00007fe1fdb99de5 __libc_start_main + 245
17 opt             0x00000000008b8a39

Any ideas what could be the problem?

Answer 1

That's not a segfault, that's an assertion error, and it's telling you the problem: the predecessor list is not empty. You get this assertion error because DeleteDeadBlock verifies that the block you are deleting has no immediate predecessors (other than itself).

However, this test does not mean that the block is alive; for example, in this scenario (assume lines are downward-facing arrows):

entry
 /
A   B
|   |
C   D
 \ /
  E

B and D are both dead, but if you'll try to remove D before B you'll get the assertion since D has a predecessor (which isn't itself).

How to solve this? You can do one of:

1. Process the blocks in topological order
2. Remove all predecessors from the block you are about to delete (e.g. by replacing the terminator of all its predecessors with the unreachable instruction)
   • You can also do that to all the blocks you identify as dead first, and then delete them in arbitrary order

Answer 2

You can use llvm::EliminateUnreachableBlocks. It performs a depth-first-search of basic blocks, starting at the entry block. This helps identify 'live' blocks that would become 'dead' once their 'dead' predecessors are removed.