[LLVMdev] inserting blocks into a Function

[Chris Lattner]

On Thu, 28 Apr 2005, Sameer D. Sahasrabuddhe wrote:
> Recently wrote a pass that inserts a preheader for a loop that doesn't
> have one. When I tried to run it, I ran into a problem that became
> obvious in hindsight - the PHINodes need to be updated in places where
> the incoming control-edge has changed. Is there anything else that can
> be affected when a block is inserted into the CFG?

That should be it.  Note that the -loop-simplify pass does preheader 
insertion among other things.  If you can just use it, I do recommend 
that.

> Also, planning to write a helper function which will take care of such
> issues. The general signature is:
>
> void reconnectBlocks(BasicBlock *newBlock, BasicBlock *insertBefore
>                    , std::vector<BasicBlock*> &preds
>                    , bool createBr = true)
>
> The std::vector "preds" is used to provide a list of preds for
> insertBefore, which will be reconnected to newBlock. For cases where
> all the preds will be reconnected, the function can be overloaded with
> this argument removed.
>
> The bool createBr is used to indicate whether an unconditional branch
> should be inserted from newBlock to insertBefore.

Hrm, I'm not sure exactly what this would do.

> Does such a thing already exist?
> If not, would people be interested in having such a function, or is
> this an overkill?
> Where in the LLVM sources should it end up?
> Am I missing anything, that needs to be included, or that makes it
> futile to write such a generalised function?

Some functions that are related, but not quite the same: 
BasicBlock::splitBasicBlock (splits a BB into two, connected with an 
unconditional branch).

llvm/Transforms/Utils/BasicBlockUtils.h:SplitCriticalEdge (inserts a block 
on a CFG edge from a multiple successor BB to a multiple predecessor BB).

If you look at lib/Transforms/Scalar/LoopSimplify.cpp, it includes a 
SplitBlockPredecessors function.  If desired, you could factor this out 
somehow.  It's prototype is:

BasicBlock *SplitBlockPredecessors(BasicBlock *BB, const char *Suffix,
                                    const std::vector<BasicBlock*> &Preds);

Basically, given a BB with multiple predecessors, it inserts (and returns) 
a new block, moving the predecessors in Preds to the new block and leaving 
the rest to the old block.  The loop-simplify pass uses this to do 
preheader insertion and other fun stuff.

Hope this helps,

-Chris

-- 
http://nondot.org/sabre/
http://llvm.cs.uiuc.edu/