[LLVMdev] Loop simplification

[Andrew Trick]

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