llvm dev - Dec 2004 - [LLVMdev] Question adding dummy basic blocks

Hi,

I got a problem when I am trying to add a dummy basic block.

Let say there are two blocks, A and B.

A----->B

I am trying to generate new BB called C which is located between A and B, but
not break the edge of AB. The graph is like the following

A---->B
 \       /
   \   /
    C
There is new BB 'C' with edges AC and CB.

It is kind of like what breakcriticaledge pass does. But we just pick up basic
block(TIBB) whose the num of successor is 1 (like unconditional branch). And we
try to replace the Terminator Inst of this basic block by contrusting a
conditional branch(A to B and A to C). Meanwhile we generate a new basic block
and unconditional branch which is from C to B.

Finally, We got some problems due to PHINODE. I knew the reason, but I failed to
fix it.

The code is like the following

if( TI->getNumSuccessors() ==1){
   BasicBlock *TIBB=TI->getParent();
   BasicBlock *DestBB=TI->getSuccessor(0);

   BasicBlock *NewBB = new
BasicBlock(TIBB->getName()+DestBB->getName()+"dummy_bb",&F);
   
   new BranchInst(DestBB, NewBB);
   BranchInst *NewBr = new BranchInst(DestBB, NewBB, V_dummy);
   ReplaceInstWithInst(TI, NewBr);

// the following code, we are trying to change value of PHINODE, and trying to
find some examples to solve, but we failed
// Since the DestBB is added to one more predecessor, and we need addIncoming
value.
// TIBB got one more successor, do we need change something?
// For NewBB, we need add the incoming value from TIBB?
// For the code listed in breakcriticaledge, it makes sure. But for our case, I
don't know to do that.

Probably, the reasons are like above, but I really don't know how sovle
them.
I would appreciate if you can give me some hint. 
    

}

> > 2) For splitting BB, the way what I did is to pick up instruction
> > randomly and do splitting before this instruction. But sometime I got
> > error when I run the Pass. It seems some of instruction set cannot be
> > splitted, right? the instruction like 'phi..'. If so, how
could we check
> > this instruction to see if it can be splitted or not.
> 
> PHI nodes are special and can only be at certain places in the CFG (for
> example, the number of incoming values to a PHI must match the number of
> predecessors in the CFG.  All PHI nodes are guaranteed to start at the
> head of a block, so just split after them.
>

On Tue, 7 Dec 2004, Zhang Qiuyu wrote:
> Finally, We got some problems due to PHINODE. I knew the reason, but I
failed to  fix it.
Ok.
> The code is like the following
>
> if( TI->getNumSuccessors() ==1){
>   BasicBlock *TIBB=TI->getParent();
>   BasicBlock *DestBB=TI->getSuccessor(0);
>
>   BasicBlock *NewBB = new
BasicBlock(TIBB->getName()+DestBB->getName()+"dummy_bb",&F);
>
>   new BranchInst(DestBB, NewBB);
>   BranchInst *NewBr = new BranchInst(DestBB, NewBB, V_dummy);
>   ReplaceInstWithInst(TI, NewBr);
If you're doing CFG manipulations, a good source of inspiration for your 
work might be the llvm/lib/Transforms/Utils/SimplifyCFG.cpp file.  It 
contains code to do many transformations like this.

I imagine that the problem with the code above is that you are adding new 
edges into 'NewBB', and if it has PHI nodes, the verifier will 
(rightfully) complain.  In particular, you're breaking the invariant that 
the # of incoming PHI node values equals the number of predecessors for 
that block.

In this case, you have to decide which values should be coming into the 
block.  Usually in cases like this, they are the same values that come in 
from some other path.  Given that you want control flow from your new 
block to emulate the control flow from some other predecessor of NewBB 
(I'll call it OtherBB), you'll want something like this:

PHINode *PN;
for (BasicBlock::iterator I = NewBB->begin();
      PN = dyn_cast<PHINode>(I); ++I)
   PN->addIncomingValue(PN->getIncomingValueForBlock(OtherBB), NewBB);

-Chris

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