llvm dev - Sep 2008 - [LLVMdev] Inserting MachineBasicBlock(s) before a MachineBasicBlock

I want to be able to do two things with LLVM (both just before code
emission):

1. Insert a MachineBasicBlock just before a MachineBasicBlock.
There is a function called AddPredecessor(). However, the comment says that
it does not update the actual CFG. I want to redirect all CFG edges that are
incoming to this MachineBasicBlock to the new one I create, and add just one
outgoing edge (no branch) to the newly formed MachineBasicBlock to jump to
the original MachineBasicBlock. How can I do this?

2. Insert a bunch of MachineInstructions at arbitrary points inside a
MachineBasicBlock.
Using the BuildMI function, I can add an arbitrary instruction just before
the position of a MachineBasicBlock::iterator. After the BuildMI function,
is the MachineBasicBlock::iterator still valid? What if I want to insert an
instruction before the newly added instruction? How should I do that?

Some general questions:

Why are there multiple MachineBasicBlocks per BasicBlock? What is the
motivation behind this representation?

Is there any example in the codebase of doing the above? 

Thanks,
-- 
View this message in context:
http://www.nabble.com/Inserting-MachineBasicBlock%28s%29-before-a-MachineBasicBlock-tp19746986p19746986.html
Sent from the LLVM - Dev mailing list archive at Nabble.com.

The BranchFolding code does CFG manipulation along the lines you want,  
although not exactly.
You can probably rephrase what you want to do so that SplitMBBAt works.

On Sep 30, 2008, at 10:39 AMPDT, madiyaan wrote:
> I want to be able to do two things with LLVM (both just before code
> emission):
>
> 1. Insert a MachineBasicBlock just before a MachineBasicBlock.
> There is a function called AddPredecessor(). However, the comment  
> says that
> it does not update the actual CFG. I want to redirect all CFG edges  
> that are
> incoming to this MachineBasicBlock to the new one I create, and add  
> just one
> outgoing edge (no branch) to the newly formed MachineBasicBlock to  
> jump to
> the original MachineBasicBlock. How can I do this?
>
> 2. Insert a bunch of MachineInstructions at arbitrary points inside a
> MachineBasicBlock.
> Using the BuildMI function, I can add an arbitrary instruction just  
> before
> the position of a MachineBasicBlock::iterator. After the BuildMI  
> function,
> is the MachineBasicBlock::iterator still valid? What if I want to  
> insert an
> instruction before the newly added instruction? How should I do that?
>
> Some general questions:
>
> Why are there multiple MachineBasicBlocks per BasicBlock? What is the
> motivation behind this representation?
>
> Is there any example in the codebase of doing the above?
>
> Thanks,
> -- 
> View this message in context:
http://www.nabble.com/Inserting-MachineBasicBlock%28s%29-before-a-MachineBasicBlock-tp19746986p19746986.html
> Sent from the LLVM - Dev mailing list archive at Nabble.com.
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

>
> I want to be able to do two things with LLVM (both just before code
> emission):
>
> 1. Insert a MachineBasicBlock just before a MachineBasicBlock.
> There is a function called AddPredecessor(). However, the comment says that
> it does not update the actual CFG. I want to redirect all CFG edges that
are
> incoming to this MachineBasicBlock to the new one I create, and add just
one
> outgoing edge (no branch) to the newly formed MachineBasicBlock to jump to
> the original MachineBasicBlock. How can I do this?
Hi,

    I had an old pass to break critical edges, and I am sending you the 
code below. I Last tested it with LLVM 2.1. It inserts a basic block 
between src and dst.

Fernando

------------------------------------------------------------------

MachineBasicBlock* CriticalEdgeRemoval_Fer::SplitCriticalMachineEdge(
   MachineBasicBlock* src,
   MachineBasicBlock* dst
) {
   const BasicBlock* srcBB = src->getBasicBlock();

   MachineBasicBlock* crit_mbb = new MachineBasicBlock(srcBB);

   // modify the llvm control flow graph
   src->removeSuccessor(dst);
   src->addSuccessor(crit_mbb);
   crit_mbb->addSuccessor(dst);

   // insert the new block into the machine function.
  
src->getParent()->getBasicBlockList().insert(src->getParent()->end(),
                                                crit_mbb);

   // insert a unconditional branch linking the new block to dst
   const TargetMachine& TM = src->getParent()->getTarget();
   const TargetInstrInfo* TII = TM.getInstrInfo();
   std::vector<MachineOperand> emptyConditions;
   TII->InsertBranch(*crit_mbb, dst, (MachineBasicBlock*)0, 
emptyConditions);

   // modify every branch in src that points to dst to point to the new
   // machine basic block instead:
   MachineBasicBlock::iterator mii = src->end();
   bool found_branch = false;
   while (mii != src->begin()) {
     mii--;
     // if there are no more branches, finish the loop
     if (!TII->isTerminatorInstr(mii->getOpcode())) {
       break;
     }

     // Scan the operands of this branch, replacing any uses of dst with
     // crit_mbb.
     for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) {
       MachineOperand & mo = mii->getOperand(i);
       if (mo.isMachineBasicBlock() &&
           mo.getMachineBasicBlock() == dst) {
         found_branch = true;
         mo.setMachineBasicBlock(crit_mbb);
       }
     }
   }

   // TODO: This is tentative. It may be necessary to fix this code. Maybe
   // I am inserting too many gotos, but I am trusting that the asm printer
   // will optimize the unnecessary gotos.
   if(!found_branch) {
     TII->InsertBranch(*src, crit_mbb, (MachineBasicBlock*)0, 
emptyConditions);
   }

   /// Change all the phi functions in dst, so that the incoming block be
   /// crit_mbb, instead of src
   for(mii = dst->begin(); mii != dst->end(); mii++) {
     /// the first instructions are always phi functions.
     if(mii->getOpcode() != TargetInstrInfo::PHI)
       break;

     for (unsigned u = 0; u != mii->getNumOperands(); ++u)
       if (mii->getOperand(u).isMachineBasicBlock() &&
           mii->getOperand(u).getMachineBasicBlock() == src)
         mii->getOperand(u).setMachineBasicBlock(crit_mbb);
   }

   return crit_mbb;
}