From e98815469ccd2f1f1585abdc7c36042177bc26f0 Mon Sep 17 00:00:00 2001 From: Devang Patel Date: Mon, 9 Apr 2007 19:04:21 +0000 Subject: [PATCH] Do not create new pre-header. Reuse original pre-header. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@35825 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Scalar/LoopRotation.cpp | 130 +++++++++++++++------------------ 1 file changed, 57 insertions(+), 73 deletions(-) diff --git a/lib/Transforms/Scalar/LoopRotation.cpp b/lib/Transforms/Scalar/LoopRotation.cpp index fa4f7642178..4568d8325e8 100644 --- a/lib/Transforms/Scalar/LoopRotation.cpp +++ b/lib/Transforms/Scalar/LoopRotation.cpp @@ -33,11 +33,11 @@ namespace { class VISIBILITY_HIDDEN RenameData { public: - RenameData(Instruction *O, Instruction *P, Instruction *H) + RenameData(Instruction *O, Value *P, Instruction *H) : Original(O), PreHeader(P), Header(H) { } public: Instruction *Original; // Original instruction - Instruction *PreHeader; // New pre-header replacement + Value *PreHeader; // Original pre-header replacement Instruction *Header; // New header replacement }; @@ -65,7 +65,7 @@ namespace { /// Make sure all Exit block PHINodes have required incoming values. /// If incoming value is constant or defined outside the loop then - /// PHINode may not have an entry for new pre-header. + /// PHINode may not have an entry for original pre-header. void updateExitBlock(); /// Return true if this instruction is used outside original header. @@ -82,7 +82,6 @@ namespace { BasicBlock *OrigPreHeader; BasicBlock *OrigLatch; BasicBlock *NewHeader; - BasicBlock *NewPreHeader; BasicBlock *Exit; SmallVector LoopHeaderInfo; @@ -125,6 +124,9 @@ bool LoopRotate::rotateLoop(Loop *Lp, LPPassManager &LPM) { if (!OrigHeader || !OrigLatch || !OrigPreHeader) return false; + if (!OrigHeader || !OrigLatch || !OrigPreHeader) + return false; + // 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. @@ -164,42 +166,40 @@ bool LoopRotate::rotateLoop(Loop *Lp, LPPassManager &LPM) { // Now, this loop is suitable for rotation. // Copy PHI nodes and other instructions from original header - // into new pre-header. Unlike original header, new pre-header is - // not a member of loop. New pre-header has only one predecessor, - // that is original loop pre-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 new loop pre-header into these phi + // 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 new loop pre-header (which is a clone of original header definition). + // from original loop pre-header. - NewPreHeader = new BasicBlock("bb.nph", OrigHeader->getParent(), OrigHeader); + // 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(I)); ++I) { Instruction *In = I; - // Create new PHI node with one value incoming from OrigPreHeader. - // NewPreHeader has only one predecessor, OrigPreHeader. - PHINode *NPH = new PHINode(In->getType(), In->getName()); - NPH->addIncoming(PN->getIncomingValueForBlock(OrigPreHeader), - OrigPreHeader); - NewPreHeader->getInstList().push_back(NPH); - + // 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 NewPreHeader. + // second incoming value is from original pre-header. PHINode *NH = new PHINode(In->getType(), In->getName()); NH->addIncoming(PN->getIncomingValueForBlock(OrigLatch), OrigHeader); - NH->addIncoming(NPH, NewPreHeader); + NH->addIncoming(NPV, OrigPreHeader); NewHeader->getInstList().push_front(NH); - // "In" can be replaced by NPH or NH at various places. - LoopHeaderInfo.push_back(RenameData(In, NPH, NH)); + // "In" can be replaced by NH at various places. + LoopHeaderInfo.push_back(RenameData(In, NPV, NH)); } // Now, handle non-phi instructions. @@ -207,20 +207,36 @@ bool LoopRotate::rotateLoop(Loop *Lp, LPPassManager &LPM) { Instruction *In = I; assert (!isa(In) && "PHINode is not expected here"); - // This is not a PHI instruction. Insert its clone into NewPreHeader. + // This is not a PHI instruction. Insert its clone into original pre-header. // If this instruction is using a value from same basic block then // update it to use value from cloned instruction. Instruction *C = In->clone(); C->setName(In->getName()); - NewPreHeader->getInstList().push_back(C); - + OrigPreHeader->getInstList().push_back(C); + + for (unsigned opi = 0, e = In->getNumOperands(); opi != e; ++opi) { + if (Instruction *OpPhi = dyn_cast(In->getOperand(opi))) { + if (const RenameData *D = findReplacementData(OpPhi)) { + // This is using values from original header PHI node. + // Here, directly used incoming value from original pre-header. + C->setOperand(opi, D->PreHeader); + } + } + else if (Instruction *OpInsn = + dyn_cast(In->getOperand(opi))) { + if (const RenameData *D = findReplacementData(OpInsn)) + C->setOperand(opi, D->PreHeader); + } + } + + // If this instruction is used outside this basic block then // create new PHINode for this instruction. Instruction *NewHeaderReplacement = NULL; if (usedOutsideOriginalHeader(In)) { PHINode *PN = new PHINode(In->getType(), In->getName()); PN->addIncoming(In, OrigHeader); - PN->addIncoming(C, NewPreHeader); + PN->addIncoming(C, OrigPreHeader); NewHeader->getInstList().push_front(PN); NewHeaderReplacement = PN; } @@ -229,38 +245,8 @@ bool LoopRotate::rotateLoop(Loop *Lp, LPPassManager &LPM) { LoopHeaderInfo.push_back(RenameData(In, C, NewHeaderReplacement)); } - // Update new pre-header. - // Rename values that are defined in original header to reflects values - // defined in new pre-header. - for(unsigned LHI = 0, LHI_E = LoopHeaderInfo.size(); LHI != LHI_E; ++LHI) { - const RenameData &ILoopHeaderInfo = LoopHeaderInfo[LHI]; - Instruction *In = ILoopHeaderInfo.Original; - Instruction *C = ILoopHeaderInfo.PreHeader; - - // If this instruction is not from new pre-header then is not new - // pre-header then this instruction is not handled here. - if (C->getParent() != NewPreHeader) - continue; - - // PHINodes uses value from pre-header predecessors. - if (isa(In)) - continue; - - for (unsigned opi = 0, e = In->getNumOperands(); opi != e; ++opi) { - if (Instruction *OpPhi = dyn_cast(In->getOperand(opi))) { - if (const RenameData *D = findReplacementData(OpPhi)) - C->setOperand(opi, D->PreHeader); - } - else if (Instruction *OpInsn = - dyn_cast(In->getOperand(opi))) { - if (const RenameData *D = findReplacementData(OpInsn)) - C->setOperand(opi, D->PreHeader); - } - } - } - // Rename uses of original header instructions to reflect their new - // definitions (either from new pre-header node or from newly created + // definitions (either from original pre-header node or from newly created // new header PHINodes. // // Original header instructions are used in @@ -268,7 +254,7 @@ bool LoopRotate::rotateLoop(Loop *Lp, LPPassManager &LPM) { // // 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 new pre-header. + // 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 @@ -334,7 +320,7 @@ bool LoopRotate::rotateLoop(Loop *Lp, LPPassManager &LPM) { // UPhi already has one incoming argument from original header. // Add second incoming argument from new Pre header. - UPhi->addIncoming(ILoopHeaderInfo.PreHeader, NewPreHeader); + UPhi->addIncoming(ILoopHeaderInfo.PreHeader, OrigPreHeader); } } @@ -345,16 +331,15 @@ bool LoopRotate::rotateLoop(Loop *Lp, LPPassManager &LPM) { // Removing incoming branch from loop preheader to original header. // Now original header is inside the loop. - OrigHeader->removePredecessor(OrigPreHeader); + for (BasicBlock::iterator I = OrigHeader->begin(), E = OrigHeader->end(); + I != E; ++I) { + Instruction *In = I; + PHINode *PN = dyn_cast(In); + if (!PN) + break; - // Establish NewPreHeader as loop preheader. Add unconditional branch - // from original loop pre-header to new loop pre-header. Add NewPreHEader - // in loop nest. - BranchInst *PH_BI = cast(OrigPreHeader->getTerminator()); - PH_BI->setSuccessor(0, NewPreHeader); - LoopInfo &LI = LPM.getAnalysis(); - if (Loop *PL = LI.getLoopFor(OrigPreHeader)) - PL->addBasicBlockToLoop(NewPreHeader, LI); + PN->removeIncomingValue(OrigPreHeader); + } // Make NewHeader as the new header for the loop. L->moveToHeader(NewHeader); @@ -365,7 +350,7 @@ bool LoopRotate::rotateLoop(Loop *Lp, LPPassManager &LPM) { /// Make sure all Exit block PHINodes have required incoming values. /// If incoming value is constant or defined outside the loop then -/// PHINode may not have an entry for new pre-header. +/// PHINode may not have an entry for original pre-header. void LoopRotate::updateExitBlock() { for (BasicBlock::iterator I = Exit->begin(), E = Exit->end(); @@ -375,8 +360,8 @@ void LoopRotate::updateExitBlock() { if (!PN) break; - // There is already one incoming value from new pre-header block. - if (PN->getBasicBlockIndex(NewPreHeader) != -1) + // There is already one incoming value from original pre-header block. + if (PN->getBasicBlockIndex(OrigPreHeader) != -1) return; const RenameData *ILoopHeaderInfo; @@ -384,9 +369,9 @@ void LoopRotate::updateExitBlock() { if (isa(V) && (ILoopHeaderInfo = findReplacementData(cast(V)))) { assert (ILoopHeaderInfo->PreHeader && "Missing New Preheader Instruction"); - PN->addIncoming(ILoopHeaderInfo->PreHeader, NewPreHeader); + PN->addIncoming(ILoopHeaderInfo->PreHeader, OrigPreHeader); } else { - PN->addIncoming(V, NewPreHeader); + PN->addIncoming(V, OrigPreHeader); } } } @@ -397,7 +382,6 @@ void LoopRotate::initialize() { OrigHeader = NULL; OrigPreHeader = NULL; NewHeader = NULL; - NewPreHeader = NULL; Exit = NULL; LoopHeaderInfo.clear(); -- 2.11.0