inserting blocks into a Function

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?

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.

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?

Sameer.

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

Great! SplitBlockPredecessors is exactly the function that I was
thinking of ... hadn't noticed the LoopSimplify pass before ...
although the pass I am working on is different, I can leave the
preheader insertion to LoopSimplify and forget about it.

I was wondering, the above function seems general enough to be
available as a utility function by itself ... but since I am not a
compiler guy myself, dunno if anyone actually ends up needing such a
function. Anyway, the LoopSimplify code's been quite helpful as a
quick intro to handling side-effects when modifying the CFG.

Thanks!
Sameer.

Great! SplitBlockPredecessors is exactly the function that I was
thinking of ... hadn't noticed the LoopSimplify pass before ...
although the pass I am working on is different, I can leave the
preheader insertion to LoopSimplify and forget about it.

Good deal! :slight_smile:

I was wondering, the above function seems general enough to be
available as a utility function by itself ... but since I am not a
compiler guy myself, dunno if anyone actually ends up needing such a
function. Anyway, the LoopSimplify code's been quite helpful as a
quick intro to handling side-effects when modifying the CFG.

Sure, if you wanted to seperate it out into the same .h and .cpp file that the split critical edges stuff lives in, I would be happy to apply the patch.

-Chris