[LLVMdev] Loop simplification

[Andrew Clinton]

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