+void LoopIndexSplit::updateLoopBounds(ICmpInst *CI) {
+
+ Value *V0 = CI->getOperand(0);
+ Value *V1 = CI->getOperand(1);
+ Value *NV = NULL;
+
+ SCEVHandle SH0 = SE->getSCEV(V0);
+
+ if (SH0->isLoopInvariant(L))
+ NV = V0;
+ else
+ NV = V1;
+
+ if (ExitCondition->getPredicate() == ICmpInst::ICMP_SGT
+ || ExitCondition->getPredicate() == ICmpInst::ICMP_UGT
+ || ExitCondition->getPredicate() == ICmpInst::ICMP_SGE
+ || ExitCondition->getPredicate() == ICmpInst::ICMP_UGE) {
+ ExitCondition->swapOperands();
+ if (ExitValueNum)
+ ExitValueNum = 0;
+ else
+ ExitValueNum = 1;
+ }
+
+ Value *NUB = NULL;
+ Value *NLB = NULL;
+ Value *UB = ExitCondition->getOperand(ExitValueNum);
+ const Type *Ty = NV->getType();
+ bool Sign = ExitCondition->isSignedPredicate();
+ BasicBlock *Preheader = L->getLoopPreheader();
+ Instruction *PHTerminator = Preheader->getTerminator();
+
+ assert (NV && "Unexpected value");
+
+ switch (CI->getPredicate()) {
+ case ICmpInst::ICMP_ULE:
+ case ICmpInst::ICMP_SLE:
+ // for (i = LB; i < UB; ++i)
+ // if (i <= NV && ...)
+ // LOOP_BODY
+ //
+ // is transformed into
+ // NUB = min (NV+1, UB)
+ // for (i = LB; i < NUB ; ++i)
+ // LOOP_BODY
+ //
+ if (ExitCondition->getPredicate() == ICmpInst::ICMP_SLT
+ || ExitCondition->getPredicate() == ICmpInst::ICMP_ULT) {
+ Value *A = BinaryOperator::CreateAdd(NV, ConstantInt::get(Ty, 1, Sign),
+ "lsplit.add", PHTerminator);
+ Value *C = new ICmpInst(Sign ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
+ A, UB,"lsplit,c", PHTerminator);
+ NUB = SelectInst::Create(C, A, UB, "lsplit.nub", PHTerminator);
+ }
+
+ // for (i = LB; i <= UB; ++i)
+ // if (i <= NV && ...)
+ // LOOP_BODY
+ //
+ // is transformed into
+ // NUB = min (NV, UB)
+ // for (i = LB; i <= NUB ; ++i)
+ // LOOP_BODY
+ //
+ else if (ExitCondition->getPredicate() == ICmpInst::ICMP_SLE
+ || ExitCondition->getPredicate() == ICmpInst::ICMP_ULE) {
+ Value *C = new ICmpInst(Sign ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
+ NV, UB, "lsplit.c", PHTerminator);
+ NUB = SelectInst::Create(C, NV, UB, "lsplit.nub", PHTerminator);
+ }
+ break;
+ case ICmpInst::ICMP_ULT:
+ case ICmpInst::ICMP_SLT:
+ // for (i = LB; i < UB; ++i)
+ // if (i < NV && ...)
+ // LOOP_BODY
+ //
+ // is transformed into
+ // NUB = min (NV, UB)
+ // for (i = LB; i < NUB ; ++i)
+ // LOOP_BODY
+ //
+ if (ExitCondition->getPredicate() == ICmpInst::ICMP_SLT
+ || ExitCondition->getPredicate() == ICmpInst::ICMP_ULT) {
+ Value *C = new ICmpInst(Sign ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
+ NV, UB, "lsplit.c", PHTerminator);
+ NUB = SelectInst::Create(C, NV, UB, "lsplit.nub", PHTerminator);
+ }
+
+ // for (i = LB; i <= UB; ++i)
+ // if (i < NV && ...)
+ // LOOP_BODY
+ //
+ // is transformed into
+ // NUB = min (NV -1 , UB)
+ // for (i = LB; i <= NUB ; ++i)
+ // LOOP_BODY
+ //
+ else if (ExitCondition->getPredicate() == ICmpInst::ICMP_SLE
+ || ExitCondition->getPredicate() == ICmpInst::ICMP_ULE) {
+ Value *S = BinaryOperator::CreateSub(NV, ConstantInt::get(Ty, 1, Sign),
+ "lsplit.add", PHTerminator);
+ Value *C = new ICmpInst(Sign ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
+ S, UB, "lsplit.c", PHTerminator);
+ NUB = SelectInst::Create(C, S, UB, "lsplit.nub", PHTerminator);
+ }
+ break;
+ case ICmpInst::ICMP_UGE:
+ case ICmpInst::ICMP_SGE:
+ // for (i = LB; i (< or <=) UB; ++i)
+ // if (i >= NV && ...)
+ // LOOP_BODY
+ //
+ // is transformed into
+ // NLB = max (NV, LB)
+ // for (i = NLB; i (< or <=) UB ; ++i)
+ // LOOP_BODY
+ //
+ {
+ Value *C = new ICmpInst(Sign ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
+ NV, StartValue, "lsplit.c", PHTerminator);
+ NLB = SelectInst::Create(C, StartValue, NV, "lsplit.nlb", PHTerminator);
+ }
+ break;
+ case ICmpInst::ICMP_UGT:
+ case ICmpInst::ICMP_SGT:
+ // for (i = LB; i (< or <=) UB; ++i)
+ // if (i > NV && ...)
+ // LOOP_BODY
+ //
+ // is transformed into
+ // NLB = max (NV+1, LB)
+ // for (i = NLB; i (< or <=) UB ; ++i)
+ // LOOP_BODY
+ //
+ {
+ Value *A = BinaryOperator::CreateAdd(NV, ConstantInt::get(Ty, 1, Sign),
+ "lsplit.add", PHTerminator);
+ Value *C = new ICmpInst(Sign ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
+ A, StartValue, "lsplit.c", PHTerminator);
+ NLB = SelectInst::Create(C, StartValue, A, "lsplit.nlb", PHTerminator);
+ }
+ break;
+ default:
+ assert ( 0 && "Unexpected split condition predicate");
+ }
+
+ if (NLB) {
+ unsigned i = IndVar->getBasicBlockIndex(Preheader);
+ IndVar->setIncomingValue(i, NLB);
+ }
+
+ if (NUB) {
+ ExitCondition->setOperand(ExitValueNum, NUB);
+ }
+}
+/// updateLoopIterationSpace - Current loop body is covered by an AND
+/// instruction whose operands compares induction variables with loop
+/// invariants. If possible, hoist this check outside the loop by
+/// updating appropriate start and end values for induction variable.
+bool LoopIndexSplit::updateLoopIterationSpace(SplitInfo &SD) {
+ BasicBlock *Header = L->getHeader();
+ BasicBlock *ExitingBlock = ExitCondition->getParent();
+ BasicBlock *SplitCondBlock = SD.SplitCondition->getParent();
+
+ ICmpInst *Op0 = cast<ICmpInst>(SD.SplitCondition->getOperand(0));
+ ICmpInst *Op1 = cast<ICmpInst>(SD.SplitCondition->getOperand(1));
+
+ if (Op0->getPredicate() == ICmpInst::ICMP_EQ
+ || Op0->getPredicate() == ICmpInst::ICMP_NE
+ || Op0->getPredicate() == ICmpInst::ICMP_EQ
+ || Op0->getPredicate() == ICmpInst::ICMP_NE)
+ return false;
+
+ // Check if SplitCondition dominates entire loop body
+ // or not.
+
+ // If SplitCondition is not in loop header then this loop is not suitable
+ // for this transformation.
+ if (SD.SplitCondition->getParent() != Header)
+ return false;
+
+ // If loop header includes loop variant instruction operands then
+ // this loop may not be eliminated.
+ 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;
+
+ // SplitCondition itself is OK.
+ if (I == SD.SplitCondition)
+ continue;
+ if (I == Op0 || I == Op1)
+ continue;
+
+ // Induction variable is OK.
+ if (I == IndVar)
+ continue;
+
+ // Induction variable increment is OK.
+ if (I == IndVarIncrement)
+ continue;
+
+ // Terminator is also harmless.
+ if (I == Terminator)
+ continue;
+
+ // Otherwise we have a instruction that may not be safe.
+ return false;
+ }
+
+ // If Exiting block includes loop variant instructions then this
+ // loop may not be eliminated.
+ if (!safeExitingBlock(SD, ExitCondition->getParent()))
+ return false;
+
+ // Verify that loop exiting block has only two predecessor, where one predecessor
+ // is split condition block. The other predecessor will become exiting block's
+ // dominator after CFG is updated. TODO : Handle CFG's where exiting block has
+ // more then two predecessors. This requires extra work in updating dominator
+ // information.
+ BasicBlock *ExitingBBPred = NULL;
+ for (pred_iterator PI = pred_begin(ExitingBlock), PE = pred_end(ExitingBlock);
+ PI != PE; ++PI) {
+ BasicBlock *BB = *PI;
+ if (SplitCondBlock == BB)
+ continue;
+ if (ExitingBBPred)
+ return false;
+ else
+ ExitingBBPred = BB;
+ }
+
+ // Update loop bounds to absorb Op0 check.
+ updateLoopBounds(Op0);
+ // Update loop bounds to absorb Op1 check.
+ updateLoopBounds(Op1);
+
+ // Update CFG
+
+ // Unconditionally connect split block to its remaining successor.
+ BranchInst *SplitTerminator =
+ cast<BranchInst>(SplitCondBlock->getTerminator());
+ BasicBlock *Succ0 = SplitTerminator->getSuccessor(0);
+ BasicBlock *Succ1 = SplitTerminator->getSuccessor(1);
+ if (Succ0 == ExitCondition->getParent())
+ SplitTerminator->setUnconditionalDest(Succ1);
+ else
+ SplitTerminator->setUnconditionalDest(Succ0);
+
+ // Remove split condition.
+ SD.SplitCondition->eraseFromParent();
+ if (Op0->use_begin() == Op0->use_end())
+ Op0->eraseFromParent();
+ if (Op1->use_begin() == Op1->use_end())
+ Op1->eraseFromParent();
+
+ BranchInst *ExitInsn =
+ dyn_cast<BranchInst>(ExitingBlock->getTerminator());
+ assert (ExitInsn && "Unable to find suitable loop exit branch");
+ BasicBlock *ExitBlock = ExitInsn->getSuccessor(1);
+ if (L->contains(ExitBlock))
+ ExitBlock = ExitInsn->getSuccessor(0);
+
+ // Update domiantor info. Now, ExitingBlock has only one predecessor,
+ // ExitingBBPred, and it is ExitingBlock's immediate domiantor.
+ DT->changeImmediateDominator(ExitingBlock, ExitingBBPred);
+
+ // If ExitingBlock is a member of loop BB's DF list then replace it with
+ // loop header and exit block.
+ for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
+ I != E; ++I) {
+ BasicBlock *BB = *I;
+ if (BB == Header || BB == ExitingBlock)
+ continue;
+ DominanceFrontier::iterator BBDF = DF->find(BB);
+ DominanceFrontier::DomSetType::iterator DomSetI = BBDF->second.begin();
+ DominanceFrontier::DomSetType::iterator DomSetE = BBDF->second.end();
+ while (DomSetI != DomSetE) {
+ DominanceFrontier::DomSetType::iterator CurrentItr = DomSetI;
+ ++DomSetI;
+ BasicBlock *DFBB = *CurrentItr;
+ if (DFBB == ExitingBlock) {
+ BBDF->second.erase(DFBB);
+ BBDF->second.insert(Header);
+ if (Header != ExitingBlock)
+ BBDF->second.insert(ExitBlock);
+ }
+ }
+ }
+
+ return true;
+}
+
+