[LLVMdev] MBB Critical edges

[Evan Cheng]

Sorry I have completely dropped the ball on this. Some comments:

1. Please try using SmallVector instead of std::vector. It may be  
offer some compile time benefit unless the vector grows too large.
2. Please try to make coding style of existing code. For example, need  
a space between for and '(', also if and '('. Also please set  
indentation level to 2.
3. Please don't include iostream. Use llvm/Support/Streams.h and DOUT  
instead.
4. Please don't include Dominators.h if it's not used. Also  
MRegisterInfo.h
5. mf.getBasicBlockList().insert(mf.end(), crit_mbb);
   Just a nit pick, please use push_back(crit_mbb).
6. This chunk of code:

     /// 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;
     bool isJumpTable = false;
     while (mii != src.begin()) {
         mii--;
         // if there are no more branches, finish the loop
         if (!tii->isTerminatorInstr(mii->getOpcode())) {
             break;
         } else if (tii->isIndirectJump(mii->getOpcode())) {
             isJumpTable = true;
             continue;
         }
         // 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);
             }
         }
     }

This is almost identical to ReplaceUsesOfBlockWith(). It's probably  
better to update ReplaceUsesOfBlockWith() to include the jumptable  
updating code and use that instead. Also note it also updates  
successor list.
7.
     // 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.
Asm printer won't optimize them away but branch folding pass might. :-)

8. I am not sure if any existing pass will benefit from this. But it  
may be handy. But does it need to be a pass? Can it be a member  
function of MachineFunction?

Thanks,

Evan

On Aug 18, 2007, at 7:51 PM, Fernando Magno Quintao Pereira wrote:

>
> Hi,
>
> This pass is similar to the one in BreakCriticalEdges.cpp, but it  
> works for MachineFunction's, instead of Functions. The existence of  
> critical edges complicates many optimizations. When doing register  
> allocation, you don't necessarily have to remove critical edges (you  
> can use conventional SSA-form, for instance. See "Translating Out of  
> Static Single Assignment Form. SAS 1999"), yet, to remove them  
> should be easy.
>
> I can send a patch if you think the code is ok. I am sending you the  
> code.
>
> best,
>
> Fernando
>
>> Can you explain briefly what it does? What benefits do you expect?
>
>>> At least I think I've solved it. I had to add one method to
>>> TargetInstrInfo to tell me when an instruction is an indirect jump -
>>> TargetInstrInfo::tii.isIndirectJump(opcode). When that is the  
>>> case, I
>>> update the jump table using:
>>>
>>>     // Change jumps to go to the new basic block:
>>>     if(isJumpTable) {
>>>         mf.getJumpTableInfo()->ReplaceMBBInJumpTables(& dst,
>>> crit_mbb);
>>>     }
>>>
>>> where dst was the old basic block, and crit_mbb is the new one,
>>> created to
>>> remove a critical edge. I think this should solve the problem. If  
>>> you
>>> want, I can give you the pass to break critical edges of machine
>>> blocks,
>>> so that you guys can see if it is worth adding to LLVM's main
>>> branch. Up
>>> to now, as far as I know, there is no pass to remove critical  
>>> edges of
>>> machine functions in LLVM.
> < 
> CriticalEdgeRemoval_Fer 
> .cpp>_______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

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