llvm dev - May 2018 - LLVM Pass To Remove Dead Code In A Basic Block

Hi all,

LLVM optimization pass gives an error "Terminator found in the middle of a
basic block!" since basic block IR may have multiple "ret"
instructions. It
seems LLVM does not accept multiple return in a basic block by default.

Is there a specific optimization or pass that I can enable to remove
unreachable codes in basic blocks?

Best,

Aaron
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180524/f38cb4b4/attachment.html>

> On 25 May 2018, at 01:46, Aaron via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> Hi all,
> 
> LLVM optimization pass gives an error "Terminator found in the middle
of a basic block!" since basic block IR may have multiple "ret"
instructions. It seems LLVM does not accept multiple return in a basic block by
default.
> 
Yes, if you’re inserting terminators in a basic block at the IR level, you’re
going to have to split it into two different blocks yourself. Essentially you’re
encountering a legaliser failure here — it’s an invariant of a BasicBlock that
there are no terminator instructions in the body, and the last instruction
should be a terminator.
> Is there a specific optimization or pass that I can enable to remove
unreachable codes in basic blocks?
> 
If you’re writing your own pass, you can do this yourself — after you insert the
return instruction, just delete the rest of the instructions in the basic block
after that instruction.

Just curious, how are you getting return instructions in the middle of a basic
block?
> Best,
> 
> Aaron
> 
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
-- Dean

Hi Dean,

Thanks for your reply.

That's exactly what I am doing, but I was looking for a default
optimization or pass implementation if there was.

I used BasicBlock::splitBasicBlock() but it puts "br" end of original
basic
block. I tried to delete the br instruction by using eraseFromParent() but
it didn't work.

I had to rewrite my own splitBasicBlock() by modifying the original one.
Just removed the br instruction creation lines.
>> Just curious, how are you getting return instructions in the middle of
a
basic block?
My code generation pass allows multiple return instruction generation since
that simplifies front-end significantly.

Here is the code if anyone would like to use it:

void CodeGenPass::DeleteDeadCode(llvm::BasicBlock * basicBlock)
{
    for (auto it = basicBlock->begin(); it != basicBlock->end(); ++it)
    {
        // Split after first return instruction.
        if (it->getOpcode() == llvm::Instruction::Ret)
        {
            ++it;
            // Split only if there is a following instruction.
            if (it != basicBlock->getInstList().end())
            {
                auto deadCodeBlock = SplitBasicBlock(basicBlock, it);
                deadCodeBlock->eraseFromParent();
            }
            return;
        }
    }
}


llvm::BasicBlock * CodeGenPass::SplitBasicBlock(llvm::BasicBlock *
basicBlock, llvm::BasicBlock::iterator it)
{
    assert(basicBlock->getTerminator() && "Block must have
terminator
instruction.");
    assert(it != basicBlock->getInstList().end() && "Can't
split block
since there is no following instruction in the basic block.");

    auto newBlock = llvm::BasicBlock::Create(basicBlock->getContext(),
"splitedBlock", basicBlock->getParent(),
basicBlock->getNextNode());

    // Move all of the instructions from original block into new block.
    newBlock->getInstList().splice(newBlock->end(),
basicBlock->getInstList(), it, basicBlock->end());

    // Now we must loop through all of the successors of the New block
(which
    // _were_ the successors of the 'this' block), and update any PHI
nodes
in
    // successors.  If there were PHI nodes in the successors, then they
need to
    // know that incoming branches will be from New, not from Old.
    //
    for (llvm::succ_iterator I = llvm::succ_begin(newBlock), E
llvm::succ_end(newBlock); I != E; ++I)
    {
        // Loop over any phi nodes in the basic block, updating the BB
field of
        // incoming values...
        llvm::BasicBlock *Successor = *I;
        for (auto &PN : Successor->phis())
        {
            int Idx = PN.getBasicBlockIndex(basicBlock);
            while (Idx != -1)
            {
                PN.setIncomingBlock((unsigned)Idx, newBlock);
                Idx = PN.getBasicBlockIndex(basicBlock);
            }
        }
    }

    return newBlock;
}


Best,

Aaron


On Thu, May 24, 2018 at 9:22 AM, Dean Michael Berris <dean.berris at
gmail.com>
wrote:
>
>
> > On 25 May 2018, at 01:46, Aaron via llvm-dev <llvm-dev at
lists.llvm.org>
> wrote:
> >
> > Hi all,
> >
> > LLVM optimization pass gives an error "Terminator found in the
middle of
> a basic block!" since basic block IR may have multiple "ret"
instructions.
> It seems LLVM does not accept multiple return in a basic block by default.
> >
>
> Yes, if you’re inserting terminators in a basic block at the IR level,
> you’re going to have to split it into two different blocks yourself.
> Essentially you’re encountering a legaliser failure here — it’s an
> invariant of a BasicBlock that there are no terminator instructions in the
> body, and the last instruction should be a terminator.
>
> > Is there a specific optimization or pass that I can enable to remove
> unreachable codes in basic blocks?
> >
>
> If you’re writing your own pass, you can do this yourself — after you
> insert the return instruction, just delete the rest of the instructions in
> the basic block after that instruction.
>
> Just curious, how are you getting return instructions in the middle of a
> basic block?
>
> > Best,
> >
> > Aaron
> >
> > _______________________________________________
> > LLVM Developers mailing list
> > llvm-dev at lists.llvm.org
> > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
> -- Dean
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180524/9eb003b9/attachment.html>