-/// Rotate loop LP. Return true if the loop is rotated.
-bool LoopRotate::rotateLoop(Loop *Lp, LPPassManager &LPM) {
-
- L = Lp;
-
- OrigHeader = L->getHeader();
- OrigPreHeader = L->getLoopPreheader();
- OrigLatch = L->getLoopLatch();
-
- // If loop has only one block then there is not much to rotate.
- if (L->getBlocks().size() == 1)
- return false;
-
- assert (OrigHeader && OrigLatch && OrigPreHeader &&
- "Loop is not in canonical form");
-
- // If loop header is not one of the loop exit block then
- // either this loop is already rotated or it is not
- // suitable for loop rotation transformations.
- if (!L->isLoopExit(OrigHeader))
- return false;
-
- BranchInst *BI = dyn_cast<BranchInst>(OrigHeader->getTerminator());
- if (!BI)
- return false;
- assert (BI->isConditional() && "Branch Instruction is not condiitional");
-
- // Updating PHInodes in loops with multiple exits adds complexity.
- // Keep it simple, and restrict loop rotation to loops with one exit only.
- // In future, lift this restriction and support for multiple exits if
- // required.
- std::vector<BasicBlock *> ExitBlocks;
- L->getExitBlocks(ExitBlocks);
- if (ExitBlocks.size() > 1)
- return false;
-
- // Check size of original header and reject
- // loop if it is very big.
- if (OrigHeader->getInstList().size() > MAX_HEADER_SIZE)
- return false;
-
- // Now, this loop is suitable for rotation.
-
- // Find new Loop header. NewHeader is a Header's one and only successor
- // that is inside loop. Header's other successor is out side the
- // loop. Otherwise loop is not suitable for rotation.
- Exit = BI->getSuccessor(0);
- NewHeader = BI->getSuccessor(1);
- if (L->contains(Exit))
- std::swap(Exit, NewHeader);
- assert (NewHeader && "Unable to determine new loop header");
- assert(L->contains(NewHeader) && !L->contains(Exit) &&
- "Unable to determine loop header and exit blocks");
-
- // Copy PHI nodes and other instructions from original header
- // into original pre-header. Unlike original header, original pre-header is
- // not a member of loop.
- //
- // New loop header is one and only successor of original header that
- // is inside the loop. All other original header successors are outside
- // the loop. Copy PHI Nodes from original header into new loop header.
- // Add second incoming value, from original loop pre-header into these phi
- // nodes. If a value defined in original header is used outside original
- // header then new loop header will need new phi nodes with two incoming
- // values, one definition from original header and second definition is
- // from original loop pre-header.
-
- // Remove terminator from Original pre-header. Original pre-header will
- // receive a clone of original header terminator as a new terminator.
- OrigPreHeader->getInstList().pop_back();
- BasicBlock::iterator I = OrigHeader->begin(), E = OrigHeader->end();
- PHINode *PN = NULL;
- for (; (PN = dyn_cast<PHINode>(I)); ++I) {
- Instruction *In = I;
-
- // PHI nodes are not copied into original pre-header. Instead their values
- // are directly propagated.
- Value * NPV = PN->getIncomingValueForBlock(OrigPreHeader);
-
- // Create new PHI node with two incoming values for NewHeader.
- // One incoming value is from OrigLatch (through OrigHeader) and
- // second incoming value is from original pre-header.
- PHINode *NH = new PHINode(In->getType(), In->getName());
- NH->addIncoming(PN->getIncomingValueForBlock(OrigLatch), OrigHeader);
- NH->addIncoming(NPV, OrigPreHeader);
- NewHeader->getInstList().push_front(NH);
-
- // "In" can be replaced by NH at various places.
- LoopHeaderInfo.push_back(RenameData(In, NPV, NH));
- }
+/// RewriteUsesOfClonedInstructions - We just cloned the instructions from the
+/// old header into the preheader. If there were uses of the values produced by
+/// these instruction that were outside of the loop, we have to insert PHI nodes
+/// to merge the two values. Do this now.
+static void RewriteUsesOfClonedInstructions(BasicBlock *OrigHeader,
+ BasicBlock *OrigPreheader,
+ ValueToValueMapTy &ValueMap) {
+ // Remove PHI node entries that are no longer live.
+ BasicBlock::iterator I, E = OrigHeader->end();
+ 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;
+
+ // If there are no uses of the value (e.g. because it returns void), there
+ // is nothing to rewrite.
+ if (OrigHeaderVal->use_empty())
+ continue;