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. Andrew
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). -Andy
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
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).Oops. I just realized you are intentionally doing loop combining. If the only other predecessor edges are back edges, then my statement above is untrue. You would have to replace all other uses of the predecessor phis (that are not successor phis) with a potentially new phi that uses itself on the backedge! -Andy
On Tue, Feb 1, 2011 at 10:08 PM, Andrew Clinton <andrew at sidefx.com> 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 don't think that's always possible. For example: if a phi in the successor has a phi in the predecessor as one of it's incoming values, then the predecessor cases have to be merged into the successor phi. However, if they share a predecessor but have different incoming values for it that can't be done.
On 02/01/2011 06:43 PM, Frits van Bommel wrote:> I don't think that's always possible. > For example: if a phi in the successor has a phi in the predecessor as > one of it's incoming values, then the predecessor cases have to be > merged into the successor phi. However, if they share a predecessor > but have different incoming values for it that can't be done.You're right. I think it's possible to avoid this (and all other?) failing cases by ensuring that the predecessor dominates the successor before trying to merge them. If the dominance relationship is not true, it may not be possible to merge them. Andrew