On Aug 7, 2007, at 9:59 AM, Chris Lattner wrote:
>> URL: http://llvm.org/viewvc/llvm-project?rev=40883&view=rev
>> Log:
>> Begin loop index split pass.
>
> Nice!
>
>>
>> +//
>> ===------------------------------------------------------------------
>> -
>> ---===//
>> +//
>> +// LoopIndexSplit - This pass splits loop
>
> Please finish your sentence :)
ok
>
>> +//
>> +LoopPass *createLoopIndexSplitPass();
>> +
>>
>> =====================================================================
>> =
>> ========
>> --- llvm/trunk/lib/Transforms/Scalar/LoopIndexSplit.cpp (added)
>> +++ llvm/trunk/lib/Transforms/Scalar/LoopIndexSplit.cpp Mon Aug 6
>> 19:25:56 2007
>> @@ -0,0 +1,384 @@
> ..
>> +
>> +#define DEBUG_TYPE "loop-index-split"
>> +
>> +#include "llvm/Function.h"
>> +#include "llvm/Transforms/Scalar.h"
>
> This should include Transforms/Scalar first, because it is the
> "interface" to the .cpp file.
ok
>
>> +/// Find condition inside a loop that is suitable candidate for
>> index split.
>> +void LoopIndexSplit::findSplitCondition() {
>> +
>> + BasicBlock *Header = L->getHeader();
>> +
>> + for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); +
>> +I) {
>> + PHINode *PN = cast<PHINode>(I);
>> +
>> + if (!PN->getType()->isInteger())
>> + continue;
>> +
>> + SCEVHandle SCEV = SE->getSCEV(PN);
>> + if (!isa<SCEVAddRecExpr>(SCEV))
>> + continue;
>> +
>> + // If this phi node is used in a compare instruction then it
>> is a
>> + // split condition candidate.
>> + for (Value::use_iterator UI = PN->use_begin(), E = PN->use_end
>> ();
>> + UI != E; ++UI) {
>> + if (ICmpInst *CI = dyn_cast<ICmpInst>(*UI)) {
>> + SplitCondition = CI;
>> + break;
>> + }
>> + }
>
> One problem with this is that it won't find conditions that are
> derived expressions of the induction variable. Consider "if (iv+1 ==
> 17)". Because the use of the IV is actually the add, this won't pick
> it up.
>
> I'd suggest scanning the terminators in the loop body, looking for
> comparisons where one side is a loop invariant, and one side is an
> addrecexpr corresponding to this loop.
ok. Only need to check header terminator here.
> Another thing to consider: in the "non-one-iteration loop" case, you
> can actually have multiple indexes to split. The ultimate
> implementation will probably want to collect all of them for a loop
> and use a cost model to determine which is the cheapest to split
> (based on how much code would have to be duplicated).
hmm... okay
>> + // Replace split condition in header.
>> + // Transform
>> + // SplitCondition : icmp eq i32 IndVar, SplitValue
>> + // into
>> + // c1 = icmp uge i32 SplitValue, StartValue
>> + // c2 = icmp ult i32 vSplitValue, ExitValue
>> + // and i32 c1, c2
>> + bool SignedPredicate = SplitCondition->isSignedPredicate();
>
> I don't think this is right. Doesn't the signedness of the compare
> depend on the loop exit condition, not the split condition?
>
> while (i < n)
> if (i == 17)
>
> You want the signedness of the i < n comparison.
I was thinking both comparisons will have same sign but now I see. OK.
>
> Similarly, somewhere in the safety checks, you should verify that the
> exit condition really is an integer compare.
It does.
>
>> + Instruction *C1 = new ICmpInst(SignedPredicate ?
>> + ICmpInst::ICMP_SGE :
>> ICmpInst::ICMP_UGE,
>> + SplitValue, StartValue,
>> "lisplit", Terminator);
>> + Instruction *C2 = new ICmpInst(SignedPredicate ?
>> + ICmpInst::ICMP_SLT :
>> ICmpInst::ICMP_ULT,
>> + SplitValue, ExitValue, "lisplit",
>> Terminator);
>> + Instruction *NSplitCond = BinaryOperator::create(Instruction::And,
>> + C1, C2,
>> "lisplit", Terminator);
>
> Plz use BinaryOperator::createAnd(C1, C2, "lisplit", Terminator);
OK
>
>> + SplitCondition->replaceAllUsesWith(NSplitCond);
>> + SplitCondition->removeFromParent();
>> + delete SplitCondition;
>
> Instead of removeFromParent + delete, just use eraseFromParent().
good idea :)
>
>> + BranchInst *BR = dyn_cast<BranchInst>(Latch->getTerminator());
>> + BR->setUnconditionalDest(LatchSucc);
>
> If you know the terminator is a branch, use cast<BranchInst>,
> otherwise you need to check to see if BR is null.
OK, I'll add null check.
>
>> + // Now, clear latch block. Remove instructions that are
>> responsible
>> + // to increment induction variable.
>> + Instruction *LTerminator = Latch->getTerminator();
>> + for (BasicBlock::iterator LB = Latch->begin(), LE = Latch->end();
>> + LB != LE; ) {
>> + Instruction *I = LB;
>> + ++LB;
>> + if (isa<PHINode>(I) || I == LTerminator)
>> + continue;
>> +
>> + I->replaceAllUsesWith(UndefValue::get(I->getType()));
>
> This won't work if I has void type. I don't know if that is possible
> though, do to your safety predicate.
It won't have void type.. I think. I'll add check.
>
>> + I->removeFromParent();
>> + delete I;
>
> These two lines can be I->eraseFromParent();
>
>> +// If loop header includes loop variant instruction operands then
>> +// this loop can not be eliminated. This is used by
>> processOneIterationLoop().
>> +bool LoopIndexSplit::safeHeader(BasicBlock *Header) {
>> +
>> + Instruction *Terminator = Header->getTerminator();
>> + for(BasicBlock::iterator BI = Header->begin(), BE = Header->end();
>> + BI != BE; ++BI) {
>> + Instruction *I = BI;
>> +
>> + // PHI Nodes are OK.
>> + if (isa<PHINode>(I))
>> + continue;
>
> What if the phi node is live out of the loop?
>
> for (i = 0, j = 0; i < n; ++i, j = i)
> if (i == 123) ...
>
> use(j)
>
> ?
I thought, there was FIXME to check last value use.
>
>> +
>> + // SplitCondition itself is OK.
>> + if (ICmpInst *CI = dyn_cast<ICmpInst>(I)) {
>> + if (CI == SplitCondition)
>> + continue;
>> + }
>
> No need for the dyncast, just use:
hmm ok.
>
>> + if (CI == SplitCondition)
>> + continue;
>
you mean
if ( I == SplitCondition)
>
>> +// If Exit block includes loop variant instructions then this
>> +// loop may not be eliminated. This is used by
>> processOneIterationLoop().
>> +bool LoopIndexSplit::safeExitBlock(BasicBlock *ExitBlock) {
>> +
>> + Instruction *ExitCondition = NULL;
>> + Instruction *IndVarIncrement = NULL;
>> +
>> + for (BasicBlock::iterator BI = ExitBlock->begin(), BE =
>> ExitBlock->end();
>> + BI != BE; ++BI) {
>> + Instruction *I = BI;
>> +
>> + // PHI Nodes are OK.
>> + if (isa<PHINode>(I))
>> + continue;
>
> similar to the above.
>
>> + // Check if I is induction variable increment instruction.
>> + if (BinaryOperator *BOp = dyn_cast<BinaryOperator>(I)) {
>> + if (BOp->getOpcode() != Instruction::Add)
>> + return false;
>
> No need for the dyncast:
>
>> + if (I->getOpcode() != Instruction::Add)
>> + return false;
>
> should work.
>
>
>> + Value *Op0 = BOp->getOperand(0);
>> + Value *Op1 = BOp->getOperand(1);
>> + PHINode *PN = NULL;
>> + ConstantInt *CI = NULL;
>> +
>> + if ((PN = dyn_cast<PHINode>(Op0))) {
>> + if ((CI = dyn_cast<ConstantInt>(Op1)))
>> + IndVarIncrement = I;
>> + } else
>> + if ((PN = dyn_cast<PHINode>(Op1))) {
>> + if ((CI = dyn_cast<ConstantInt>(Op0)))
>> + IndVarIncrement = I;
>> + }
>> +
>> + if (IndVarIncrement && PN == IndVar && CI->isOne())
>> + continue;
>> + }
>
> It seems enough to check to see that the add has a single use, and
> that its use is a phinode in the loop header, no?
that'd also work.
>
> Looks like a great start Devang!
Thanks!
-
Devang
_______________________________________________
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
