+ if (IVisLT(*ExitCondition)) {
+ if (IVisLT(*SplitCondition)) {
+ /* Do nothing */
+ }
+ else if (IVisLE(*SplitCondition)) {
+ AEV = getPlusOne(SplitValue, Sign, PHTerm);
+ BSV = getPlusOne(SplitValue, Sign, PHTerm);
+ } else {
+ assert (0 && "Unexpected split condition!");
+ }
+ }
+ else if (IVisLE(*ExitCondition)) {
+ if (IVisLT(*SplitCondition)) {
+ AEV = getMinusOne(SplitValue, Sign, PHTerm);
+ }
+ else if (IVisLE(*SplitCondition)) {
+ BSV = getPlusOne(SplitValue, Sign, PHTerm);
+ } else {
+ assert (0 && "Unexpected split condition!");
+ }
+ } else {
+ assert (0 && "Unexpected exit condition!");
+ }
+ AEV = getMin(AEV, IVExitValue, Sign, PHTerm);
+ BSV = getMax(BSV, IVStartValue, Sign, PHTerm);
+
+ // [*] Clone Loop
+ DenseMap<const Value *, Value *> ValueMap;
+ Loop *BLoop = CloneLoop(L, LPM, LI, ValueMap, this);
+ Loop *ALoop = L;
+
+ // [*] ALoop's exiting edge enters BLoop's header.
+ // ALoop's original exit block becomes BLoop's exit block.
+ PHINode *B_IndVar = cast<PHINode>(ValueMap[IndVar]);
+ BasicBlock *A_ExitingBlock = ExitCondition->getParent();
+ BranchInst *A_ExitInsn =
+ dyn_cast<BranchInst>(A_ExitingBlock->getTerminator());
+ assert (A_ExitInsn && "Unable to find suitable loop exit branch");
+ BasicBlock *B_ExitBlock = A_ExitInsn->getSuccessor(1);
+ BasicBlock *B_Header = BLoop->getHeader();
+ if (ALoop->contains(B_ExitBlock)) {
+ B_ExitBlock = A_ExitInsn->getSuccessor(0);
+ A_ExitInsn->setSuccessor(0, B_Header);
+ } else
+ A_ExitInsn->setSuccessor(1, B_Header);
+
+ // [*] Update ALoop's exit value using new exit value.
+ ExitCondition->setOperand(EVOpNum, AEV);
+
+ // [*] Update BLoop's header phi nodes. Remove incoming PHINode's from
+ // original loop's preheader. Add incoming PHINode values from
+ // ALoop's exiting block. Update BLoop header's domiantor info.
+
+ // Collect inverse map of Header PHINodes.
+ DenseMap<Value *, Value *> InverseMap;
+ for (BasicBlock::iterator BI = ALoop->getHeader()->begin(),
+ BE = ALoop->getHeader()->end(); BI != BE; ++BI) {
+ if (PHINode *PN = dyn_cast<PHINode>(BI)) {
+ PHINode *PNClone = cast<PHINode>(ValueMap[PN]);
+ InverseMap[PNClone] = PN;
+ } else
+ break;
+ }
+
+ BasicBlock *A_Preheader = ALoop->getLoopPreheader();
+ for (BasicBlock::iterator BI = B_Header->begin(), BE = B_Header->end();
+ BI != BE; ++BI) {
+ if (PHINode *PN = dyn_cast<PHINode>(BI)) {
+ // Remove incoming value from original preheader.
+ PN->removeIncomingValue(A_Preheader);
+
+ // Add incoming value from A_ExitingBlock.
+ if (PN == B_IndVar)
+ PN->addIncoming(BSV, A_ExitingBlock);
+ else {
+ PHINode *OrigPN = cast<PHINode>(InverseMap[PN]);
+ Value *V2 = NULL;
+ // If loop header is also loop exiting block then
+ // OrigPN is incoming value for B loop header.
+ if (A_ExitingBlock == ALoop->getHeader())
+ V2 = OrigPN;
+ else
+ V2 = OrigPN->getIncomingValueForBlock(A_ExitingBlock);
+ PN->addIncoming(V2, A_ExitingBlock);
+ }
+ } else
+ break;
+ }
+
+ DT->changeImmediateDominator(B_Header, A_ExitingBlock);
+ DF->changeImmediateDominator(B_Header, A_ExitingBlock, DT);
+
+ // [*] Update BLoop's exit block. Its new predecessor is BLoop's exit
+ // block. Remove incoming PHINode values from ALoop's exiting block.
+ // Add new incoming values from BLoop's incoming exiting value.
+ // Update BLoop exit block's dominator info..
+ BasicBlock *B_ExitingBlock = cast<BasicBlock>(ValueMap[A_ExitingBlock]);
+ for (BasicBlock::iterator BI = B_ExitBlock->begin(), BE = B_ExitBlock->end();
+ BI != BE; ++BI) {
+ if (PHINode *PN = dyn_cast<PHINode>(BI)) {
+ PN->addIncoming(ValueMap[PN->getIncomingValueForBlock(A_ExitingBlock)],
+ B_ExitingBlock);
+ PN->removeIncomingValue(A_ExitingBlock);
+ } else
+ break;
+ }
+
+ DT->changeImmediateDominator(B_ExitBlock, B_ExitingBlock);
+ DF->changeImmediateDominator(B_ExitBlock, B_ExitingBlock, DT);
+
+ //[*] Split ALoop's exit edge. This creates a new block which
+ // serves two purposes. First one is to hold PHINode defnitions
+ // to ensure that ALoop's LCSSA form. Second use it to act
+ // as a preheader for BLoop.
+ BasicBlock *A_ExitBlock = SplitEdge(A_ExitingBlock, B_Header, this);
+
+ //[*] Preserve ALoop's LCSSA form. Create new forwarding PHINodes
+ // in A_ExitBlock to redefine outgoing PHI definitions from ALoop.
+ for(BasicBlock::iterator BI = B_Header->begin(), BE = B_Header->end();
+ BI != BE; ++BI) {
+ if (PHINode *PN = dyn_cast<PHINode>(BI)) {
+ Value *V1 = PN->getIncomingValueForBlock(A_ExitBlock);
+ PHINode *newPHI = PHINode::Create(PN->getType(), PN->getName());
+ newPHI->addIncoming(V1, A_ExitingBlock);
+ A_ExitBlock->getInstList().push_front(newPHI);
+ PN->removeIncomingValue(A_ExitBlock);
+ PN->addIncoming(newPHI, A_ExitBlock);
+ } else
+ break;