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
Here's what I've got so far - it seems to work, aside from the fact that
DeleteDeadPHIs is not removing at least one dead PHI in my test program.
---------------------
static bool
mergeBlockIntoSuccessor(BasicBlock *pred, BasicBlock *succ)
{
if (succ == pred)
return false;
if (pred->getFirstNonPHI() != pred->getTerminator())
return false;
// Delete the terminator in the predecessor block
pred->getTerminator()->eraseFromParent();
// Update predecessor PHIs
for (BasicBlock::iterator it = pred->begin();
it != pred->end(); ++it)
{
PHINode *phi = dyn_cast<PHINode>(it);
UT_ASSERT(phi);
// Adjust the PHI to have the correct incoming block set
for (pred_iterator pi = pred_begin(succ);
pi != pred_end(succ); ++pi)
{
// We're a different predecessor than the predecessor block
if (*pi != pred)
{
phi->addIncoming(phi, *pi);
}
}
}
// Update successor PHIs
for (BasicBlock::iterator it = succ->begin();
succ->getFirstNonPHI() != it; ++it)
{
PHINode *phi = dyn_cast<PHINode>(it);
UT_ASSERT(phi);
UT_ASSERT(phi->getBasicBlockIndex(pred) >= 0);
Value *val = phi->getIncomingValueForBlock(pred);
PHINode *predphi = dyn_cast<PHINode>(val);
if (predphi && predphi->getParent() != pred)
predphi = 0;
phi->removeIncomingValue(pred, false);
for (pred_iterator pi = pred_begin(pred);
pi != pred_end(pred); ++pi)
{
// We're a new predecessor
if (phi->getBasicBlockIndex(*pi) < 0)
{
if (predphi)
{
UT_ASSERT(predphi->getBasicBlockIndex(*pi) >= 0);
phi->addIncoming(
predphi->getIncomingValueForBlock(*pi), *pi);
}
else
phi->addIncoming(val, *pi);
}
}
}
// Move the PHIs into the successor
succ->getInstList().splice(succ->begin(), pred->getInstList());
// Remove the predecessor block
pred->replaceAllUsesWith(succ);
// Simplify conditional branches
for (Value::use_iterator ui = succ->use_begin();
ui != succ->use_end(); ++ui)
{
Instruction *inst = dyn_cast<Instruction>(*ui);
if (inst)
ConstantFoldTerminator(inst->getParent());
}
// Clean out dead PHI nodes
DeleteDeadPHIs(succ);
return true;
}
On 02/01/2011 04:57 PM, Andrew Trick wrote:> 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 02/01/2011 05:22 PM, Andrew Clinton wrote:> Here's what I've got so far - it seems to work, aside from the fact that > DeleteDeadPHIs is not removing at least one dead PHI in my test program.PHI nodes don't seem to be cleaned up correctly since in llvm::RecursivelyDeleteDeadPHINode the algorithm can only handle single-use PHIs while my dead PHI has 2 uses (both self-references). Andrew
On Feb 1, 2011, at 2:22 PM, Andrew Clinton wrote:> Here's what I've got so far - it seems to work, aside from the fact that DeleteDeadPHIs is not removing at least one dead PHI in my test program.The hasOneUse check may be failing in your case. Do you need to call SimplifyInstruction first? I'm not sure that will help though. Your design looks mostly adequate for the simple nested loop case. I won't be able to spot all the issues upon inspection. I haven't done anything like this in LLVM either. I can add a couple comments:> --------------------- > > static bool > mergeBlockIntoSuccessor(BasicBlock *pred, BasicBlock *succ) > { > if (succ == pred) > return false; > > if (pred->getFirstNonPHI() != pred->getTerminator()) > return false; > > // Delete the terminator in the predecessor block > pred->getTerminator()->eraseFromParent();Is that sufficient to check for a side-effect free uncondition branch?> > // Update predecessor PHIs > for (BasicBlock::iterator it = pred->begin(); > it != pred->end(); ++it) > { > PHINode *phi = dyn_cast<PHINode>(it); > > UT_ASSERT(phi); > > // Adjust the PHI to have the correct incoming block set > for (pred_iterator pi = pred_begin(succ); > pi != pred_end(succ); ++pi) > { > // We're a different predecessor than the predecessor block > if (*pi != pred) > { > phi->addIncoming(phi, *pi);You need to guarantee pi->succ is a backedge of course. Handling other cases will be more involved.> } > } > } > > // Update successor PHIs > for (BasicBlock::iterator it = succ->begin(); > succ->getFirstNonPHI() != it; ++it) > { > PHINode *phi = dyn_cast<PHINode>(it); > > UT_ASSERT(phi); > UT_ASSERT(phi->getBasicBlockIndex(pred) >= 0); > > Value *val = phi->getIncomingValueForBlock(pred); > PHINode *predphi = dyn_cast<PHINode>(val); > > if (predphi && predphi->getParent() != pred) > predphi = 0; > > phi->removeIncomingValue(pred, false); > > for (pred_iterator pi = pred_begin(pred); > pi != pred_end(pred); ++pi) > { > // We're a new predecessor > if (phi->getBasicBlockIndex(*pi) < 0) > { > if (predphi) > { > UT_ASSERT(predphi->getBasicBlockIndex(*pi) >= 0); > phi->addIncoming( > predphi->getIncomingValueForBlock(*pi), *pi); > } > else > phi->addIncoming(val, *pi); > } > } > } > > // Move the PHIs into the successor > succ->getInstList().splice(succ->begin(), pred->getInstList()); > > // Remove the predecessor block > pred->replaceAllUsesWith(succ); > > // Simplify conditional branches > for (Value::use_iterator ui = succ->use_begin(); > ui != succ->use_end(); ++ui) > { > Instruction *inst = dyn_cast<Instruction>(*ui); > if (inst) > ConstantFoldTerminator(inst->getParent()); > } > > // Clean out dead PHI nodes > DeleteDeadPHIs(succ); > > return true; > }Do you need to worry about updating AliasAnalysis/MemoryDepAnalysis, DominatorTree, LoopInfo...? -Andy