Remove identical or redundant basic blocks?

Dear all,

after optimizing a small LLVM example program (i.e., with opt -O3), the resulting code contains several basic blocks, which I consider identical or redundant. For instance,

return: ; preds = %min.exit
   ret i32 0

bb15: ; preds = %min.exit
   ret i32 0

or,

bb7.i: ; preds = %bb1.i
   br label %bb3.i

bb9.i: ; preds = %bb1.i
   br label %bb3.i

I think it is safe to remove the blocks bb7.i, bb9.i, bb15 while replacing each jump to bb15 with return and jumps to bb7.i, bb9.i with bb3.i.

Is there any opt pass I can apply to the code to merge or remove these blocks?

Heinz

The branch folding pass does this, but it operates later, on the target-dependent form in llc.

Would it make sense to have a similar pass that operates on llvm main IR?

Eugene Toder wrote:

Would it make sense to have a similar pass that operates on llvm main IR?
  
The unify exit return node (-mergereturn?) pass should take care of the first example. The -simplifycfg option might take care of the second example. Both work on LLVM IR.

-- John T.

Dale is totally right, all of these blocks disappear in later
target-dependent optimizations. I have not thought about that since
eliminating these blocks requires no target-dependent information.
However, I guess it is not worth eliminating them earlier.

John, I tried your advice and executed opt (after -O3) again with
-mergereturn and -simplifycfg: The -mergereturn pass introduces
another basic block, called UnifiedReturnBlock, and replaces ret
instructions with jumps to UnifiedReturnBlock. So, it does not
eliminates any block but it creates one. (I think its task is to merge
the ret instructions (and not the blocks).)

The -simplifycfg pass does not affect my code at all. Moreover,
according to 'StandardPasses.h' I guess the pass already runs (about 4
times) as a part of -O3. I have yet not looked at the actual code of
simplifycfg but the comment in 'StandarPasses.h' says it should merge
and eliminate basic blocks.

include/llvm/Support/StandardPasses.h, line 129 (SVN-97366):
PM->add(createCFGSimplificationPass()); // Merge & remove BBs

Heinz

Branches have sufficient target-dependent aspects that you really need to deal with them at that level. For example:

ret might expand to a single instruction, a lengthy epilog, or a tail call
many targets have limits on how far a conditional branch can reach; sometimes intermediate unconditional branches are needed as steppingstones
not all targets can support all conditional branches that appear in the IR; some of them expand to multiple instructions

Since targets need to deal with this stuff in any case, it's not worth it to try to be too clever at the target-independent level. In some cases the target would have to undo whatever you did anyway.