+/// safeSplitCondition - Return true if it is possible to
+/// split loop using given split condition.
+bool LoopIndexSplit::safeSplitCondition(SplitInfo &SD) {
+
+ BasicBlock *SplitCondBlock = SD.SplitCondition->getParent();
+ BasicBlock *Latch = L->getLoopLatch();
+ BranchInst *SplitTerminator =
+ cast<BranchInst>(SplitCondBlock->getTerminator());
+ BasicBlock *Succ0 = SplitTerminator->getSuccessor(0);
+ BasicBlock *Succ1 = SplitTerminator->getSuccessor(1);
+
+ // If split block does not dominate the latch then this is not a diamond.
+ // Such loop may not benefit from index split.
+ if (!DT->dominates(SplitCondBlock, Latch))
+ return false;
+
+ // Finally this split condition is safe only if merge point for
+ // split condition branch is loop latch. This check along with previous
+ // check, to ensure that exit condition is in either loop latch or header,
+ // filters all loops with non-empty loop body between merge point
+ // and exit condition.
+ DominanceFrontier::iterator Succ0DF = DF->find(Succ0);
+ assert (Succ0DF != DF->end() && "Unable to find Succ0 dominance frontier");
+ if (Succ0DF->second.count(Latch))
+ return true;
+
+ DominanceFrontier::iterator Succ1DF = DF->find(Succ1);
+ assert (Succ1DF != DF->end() && "Unable to find Succ1 dominance frontier");
+ if (Succ1DF->second.count(Latch))
+ return true;
+
+ return false;
+}
+
+/// calculateLoopBounds - ALoop exit value and BLoop start values are calculated
+/// based on split value.
+void LoopIndexSplit::calculateLoopBounds(SplitInfo &SD) {
+
+ ICmpInst *SC = cast<ICmpInst>(SD.SplitCondition);
+ ICmpInst::Predicate SP = SC->getPredicate();
+ const Type *Ty = SD.SplitValue->getType();
+ bool Sign = ExitCondition->isSignedPredicate();
+ BasicBlock *Preheader = L->getLoopPreheader();
+ Instruction *PHTerminator = Preheader->getTerminator();
+
+ // Initially use split value as upper loop bound for first loop and lower loop
+ // bound for second loop.
+ Value *AEV = SD.SplitValue;
+ Value *BSV = SD.SplitValue;
+
+ 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;
+ }
+
+ switch (ExitCondition->getPredicate()) {
+ case ICmpInst::ICMP_SGT:
+ case ICmpInst::ICMP_UGT:
+ case ICmpInst::ICMP_SGE:
+ case ICmpInst::ICMP_UGE:
+ default:
+ assert (0 && "Unexpected exit condition predicate");
+
+ case ICmpInst::ICMP_SLT:
+ case ICmpInst::ICMP_ULT:
+ {
+ switch (SP) {
+ case ICmpInst::ICMP_SLT:
+ case ICmpInst::ICMP_ULT:
+ //
+ // for (i = LB; i < UB; ++i) { if (i < SV) A; else B; }
+ //
+ // is transformed into
+ // AEV = BSV = SV
+ // for (i = LB; i < min(UB, AEV); ++i)
+ // A;
+ // for (i = max(LB, BSV); i < UB; ++i);
+ // B;
+ break;
+ case ICmpInst::ICMP_SLE:
+ case ICmpInst::ICMP_ULE:
+ {
+ //
+ // for (i = LB; i < UB; ++i) { if (i <= SV) A; else B; }
+ //
+ // is transformed into
+ //
+ // AEV = SV + 1
+ // BSV = SV + 1
+ // for (i = LB; i < min(UB, AEV); ++i)
+ // A;
+ // for (i = max(LB, BSV); i < UB; ++i)
+ // B;
+ BSV = BinaryOperator::CreateAdd(SD.SplitValue,
+ ConstantInt::get(Ty, 1, Sign),
+ "lsplit.add", PHTerminator);
+ AEV = BSV;
+ }
+ break;
+ case ICmpInst::ICMP_SGE:
+ case ICmpInst::ICMP_UGE:
+ //
+ // for (i = LB; i < UB; ++i) { if (i >= SV) A; else B; }
+ //
+ // is transformed into
+ // AEV = BSV = SV
+ // for (i = LB; i < min(UB, AEV); ++i)
+ // B;
+ // for (i = max(BSV, LB); i < UB; ++i)
+ // A;
+ break;
+ case ICmpInst::ICMP_SGT:
+ case ICmpInst::ICMP_UGT:
+ {
+ //
+ // for (i = LB; i < UB; ++i) { if (i > SV) A; else B; }
+ //
+ // is transformed into
+ //
+ // BSV = AEV = SV + 1
+ // for (i = LB; i < min(UB, AEV); ++i)
+ // B;
+ // for (i = max(LB, BSV); i < UB; ++i)
+ // A;
+ BSV = BinaryOperator::CreateAdd(SD.SplitValue,
+ ConstantInt::get(Ty, 1, Sign),
+ "lsplit.add", PHTerminator);
+ AEV = BSV;
+ }
+ break;
+ default:
+ assert (0 && "Unexpected split condition predicate");
+ break;
+ } // end switch (SP)
+ }
+ break;
+ case ICmpInst::ICMP_SLE:
+ case ICmpInst::ICMP_ULE:
+ {
+ switch (SP) {
+ case ICmpInst::ICMP_SLT:
+ case ICmpInst::ICMP_ULT:
+ //
+ // for (i = LB; i <= UB; ++i) { if (i < SV) A; else B; }
+ //
+ // is transformed into
+ // AEV = SV - 1;
+ // BSV = SV;
+ // for (i = LB; i <= min(UB, AEV); ++i)
+ // A;
+ // for (i = max(LB, BSV); i <= UB; ++i)
+ // B;
+ AEV = BinaryOperator::CreateSub(SD.SplitValue,
+ ConstantInt::get(Ty, 1, Sign),
+ "lsplit.sub", PHTerminator);
+ break;
+ case ICmpInst::ICMP_SLE:
+ case ICmpInst::ICMP_ULE:
+ //
+ // for (i = LB; i <= UB; ++i) { if (i <= SV) A; else B; }
+ //
+ // is transformed into
+ // AEV = SV;
+ // BSV = SV + 1;
+ // for (i = LB; i <= min(UB, AEV); ++i)
+ // A;
+ // for (i = max(LB, BSV); i <= UB; ++i)
+ // B;
+ BSV = BinaryOperator::CreateAdd(SD.SplitValue,
+ ConstantInt::get(Ty, 1, Sign),
+ "lsplit.add", PHTerminator);
+ break;
+ case ICmpInst::ICMP_SGT:
+ case ICmpInst::ICMP_UGT:
+ //
+ // for (i = LB; i <= UB; ++i) { if (i > SV) A; else B; }
+ //
+ // is transformed into
+ // AEV = SV;
+ // BSV = SV + 1;
+ // for (i = LB; i <= min(AEV, UB); ++i)
+ // B;
+ // for (i = max(LB, BSV); i <= UB; ++i)
+ // A;
+ BSV = BinaryOperator::CreateAdd(SD.SplitValue,
+ ConstantInt::get(Ty, 1, Sign),
+ "lsplit.add", PHTerminator);
+ break;
+ case ICmpInst::ICMP_SGE:
+ case ICmpInst::ICMP_UGE:
+ // ** TODO **
+ //
+ // for (i = LB; i <= UB; ++i) { if (i >= SV) A; else B; }
+ //
+ // is transformed into
+ // AEV = SV - 1;
+ // BSV = SV;
+ // for (i = LB; i <= min(AEV, UB); ++i)
+ // B;
+ // for (i = max(LB, BSV); i <= UB; ++i)
+ // A;
+ AEV = BinaryOperator::CreateSub(SD.SplitValue,
+ ConstantInt::get(Ty, 1, Sign),
+ "lsplit.sub", PHTerminator);
+ break;
+ default:
+ assert (0 && "Unexpected split condition predicate");
+ break;
+ } // end switch (SP)
+ }
+ break;
+ }
+
+ // Calculate ALoop induction variable's new exiting value and
+ // BLoop induction variable's new starting value. Calculuate these
+ // values in original loop's preheader.
+ // A_ExitValue = min(SplitValue, OrignalLoopExitValue)
+ // B_StartValue = max(SplitValue, OriginalLoopStartValue)
+ Instruction *InsertPt = L->getHeader()->getFirstNonPHI();
+
+ // If ExitValue operand is also defined in Loop header then
+ // insert new ExitValue after this operand definition.
+ if (Instruction *EVN =
+ dyn_cast<Instruction>(ExitCondition->getOperand(ExitValueNum))) {
+ if (!isa<PHINode>(EVN))
+ if (InsertPt->getParent() == EVN->getParent()) {
+ BasicBlock::iterator LHBI = L->getHeader()->begin();
+ BasicBlock::iterator LHBE = L->getHeader()->end();
+ for(;LHBI != LHBE; ++LHBI) {
+ Instruction *I = LHBI;
+ if (I == EVN)
+ break;
+ }
+ InsertPt = ++LHBI;
+ }
+ }
+ Value *C1 = new ICmpInst(Sign ?
+ ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
+ AEV,
+ ExitCondition->getOperand(ExitValueNum),
+ "lsplit.ev", InsertPt);
+
+ SD.A_ExitValue = SelectInst::Create(C1, AEV,
+ ExitCondition->getOperand(ExitValueNum),
+ "lsplit.ev", InsertPt);
+
+ Value *C2 = new ICmpInst(Sign ?
+ ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
+ BSV, StartValue, "lsplit.sv",
+ PHTerminator);
+ SD.B_StartValue = SelectInst::Create(C2, StartValue, BSV,
+ "lsplit.sv", PHTerminator);
+}
+
+/// splitLoop - Split current loop L in two loops using split information
+/// SD. Update dominator information. Maintain LCSSA form.