[LLVMdev] Loop simplification

[Andrew Trick]

On Feb 1, 2011, at 1:34 PM, Andrew Trick wrote:

> On Feb 1, 2011, at 1:08 PM, Andrew Clinton wrote:
> 
>> I have a (non-entry) basic block that contains only PHI nodes and an 
>> unconditional branch (that does not branch to itself).  Is it always 
>> possible to merge this block with it's successor and produce a 
>> semantically equivalent program?  I'm trying to undo some of the loop 
>> optimizations that LLVM has applied to my program to reduce a pair of 
>> nested loops to a single loop.
>> 
>> llvm::MergeBlockIntoPredecessor does not do what I want since it 
>> requires that the the block have a unique predecessor.
> 
> I didn't notice anything that will do what you want out-of-box, but it should not be hard to write. llvm::FoldSingleEntryPHINodes is an example of phi node replacement. But in this case, you'll need to do one in-place operand replacement for each successor phi use and call PhiNode::addIncoming for the rest. Note that multiple successor phis may use the same predecessor phi, so you should be careful of mutating the phis while iterating their uses. If you cover the trivial case first with llvm::MergeBlockIntoPredecessor, then the predecessor phis should have no uses other than successor phis. That would violate strict SSA (the CFG edge you described is a dominance frontier).

I forgot to ask why you're doing this. If the goal is to remove a branch, that would typically be handled by BranchFolder during codegen after phis have been removed. I don't see a problem forcing the CFG to be more canonical earlier, but if the successor is in a deeper loop, then you could be eliminating a preheader and forcing compensation code into the loop. In fact, I wouldn't be surprised if some loop passes might want a single preheader.

-Andy