- // Rename uses of original header instructions to reflect their new
- // definitions (either from original pre-header node or from newly created
- // new header PHINodes.
- //
- // Original header instructions are used in
- // 1) Original header:
- //
- // If instruction is used in non-phi instructions then it is using
- // defintion from original heder iteself. Do not replace this use
- // with definition from new header or original pre-header.
- //
- // If instruction is used in phi node then it is an incoming
- // value. Rename its use to reflect new definition from new-preheader
- // or new header.
- //
- // 2) Inside loop but not in original header
- //
- // Replace this use to reflect definition from new header.
- for (unsigned LHI = 0, LHI_E = LoopHeaderInfo.size(); LHI != LHI_E; ++LHI) {
- const RenameData &ILoopHeaderInfo = LoopHeaderInfo[LHI];
-
- if (!ILoopHeaderInfo.Header)
- continue;
-
- Instruction *OldPhi = ILoopHeaderInfo.Original;
- Instruction *NewPhi = ILoopHeaderInfo.Header;
-
- // Before replacing uses, collect them first, so that iterator is
- // not invalidated.
- SmallVector<Instruction *, 16> AllUses;
- for (Value::use_iterator UI = OldPhi->use_begin(), UE = OldPhi->use_end();
- UI != UE; ++UI)
- AllUses.push_back(cast<Instruction>(UI));
-
- for (SmallVector<Instruction *, 16>::iterator UI = AllUses.begin(),
- UE = AllUses.end(); UI != UE; ++UI) {
- Instruction *U = *UI;
- BasicBlock *Parent = U->getParent();
-
- // Used inside original header
- if (Parent == OrigHeader) {
- // Do not rename uses inside original header non-phi instructions.
- PHINode *PU = dyn_cast<PHINode>(U);
- if (!PU)
+ // Along with all the other instructions, we just cloned OrigHeader's
+ // terminator into OrigPreHeader. Fix up the PHI nodes in each of OrigHeader's
+ // successors by duplicating their incoming values for OrigHeader.
+ TerminatorInst *TI = OrigHeader->getTerminator();
+ for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
+ for (BasicBlock::iterator BI = TI->getSuccessor(i)->begin();
+ PHINode *PN = dyn_cast<PHINode>(BI); ++BI)
+ PN->addIncoming(PN->getIncomingValueForBlock(OrigHeader), OrigPreHeader);
+
+ // Now that OrigPreHeader has a clone of OrigHeader's terminator, remove
+ // OrigPreHeader's old terminator (the original branch into the loop), and
+ // remove the corresponding incoming values from the PHI nodes in OrigHeader.
+ LoopEntryBranch->eraseFromParent();
+ for (I = OrigHeader->begin(); PHINode *PN = dyn_cast<PHINode>(I); ++I)
+ PN->removeIncomingValue(PN->getBasicBlockIndex(OrigPreHeader));
+
+ // Now fix up users of the instructions in OrigHeader, inserting PHI nodes
+ // as necessary.
+ SSAUpdater SSA;
+ for (I = OrigHeader->begin(); I != E; ++I) {
+ Value *OrigHeaderVal = I;
+ Value *OrigPreHeaderVal = ValueMap[OrigHeaderVal];
+
+ // The value now exits in two versions: the initial value in the preheader
+ // and the loop "next" value in the original header.
+ SSA.Initialize(OrigHeaderVal);
+ SSA.AddAvailableValue(OrigHeader, OrigHeaderVal);
+ SSA.AddAvailableValue(OrigPreHeader, OrigPreHeaderVal);
+
+ // Visit each use of the OrigHeader instruction.
+ for (Value::use_iterator UI = OrigHeaderVal->use_begin(),
+ UE = OrigHeaderVal->use_end(); UI != UE; ) {
+ // Grab the use before incrementing the iterator.
+ Use &U = UI.getUse();
+
+ // Increment the iterator before removing the use from the list.
+ ++UI;
+
+ // SSAUpdater can't handle a non-PHI use in the same block as an
+ // earlier def. We can easily handle those cases manually.
+ Instruction *UserInst = cast<Instruction>(U.getUser());
+ if (!isa<PHINode>(UserInst)) {
+ BasicBlock *UserBB = UserInst->getParent();
+
+ // The original users in the OrigHeader are already using the
+ // original definitions.
+ if (UserBB == OrigHeader)