//
//===----------------------------------------------------------------------===//
-#define DEBUG_TYPE "loop-rotation"
+#define DEBUG_TYPE "loop-rotate"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Function.h"
#include "llvm/Support/Debug.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/SmallVector.h"
-#include <map>
using namespace llvm;
STATISTIC(NumRotated, "Number of loops rotated");
namespace {
- cl::opt<unsigned>
- RotateThreshold("rotate-threshold", cl::init(200), cl::Hidden,
- cl::desc("The cut-off point for loop rotating"));
-
- class VISIBILITY_HIDDEN InsnReplacementData {
+ class VISIBILITY_HIDDEN RenameData {
public:
- InsnReplacementData(Instruction *O, Instruction *P, Instruction *H)
- : Original(O), PreHeader(P), Header(H) {}
+ RenameData(Instruction *O, Instruction *P, Instruction *H)
+ : Original(O), PreHeader(P), Header(H) { }
public:
Instruction *Original; // Original instruction
Instruction *PreHeader; // New pre-header replacement
Instruction *Header; // New header replacement
};
-
+
class VISIBILITY_HIDDEN LoopRotate : public LoopPass {
public:
+
+ // Rotate Loop L as many times as possible. Return true if
+ // loop is rotated at least once.
bool runOnLoop(Loop *L, LPPassManager &LPM);
+
+ // LCSSA form makes instruction renaming easier.
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.addRequiredID(LCSSAID);
AU.addPreservedID(LCSSAID);
- //AU.addRequired<LoopInfo>();
- //AU.addPreserved<LoopInfo>();
}
// Helper functions
/// Find Replacement information for instruction. Return NULL if it is
/// not available.
- InsnReplacementData *findReplacementData(Instruction *I);
+ RenameData *findReplacementData(Instruction *I);
private:
BasicBlock *NewPreHeader;
BasicBlock *Exit;
- SmallVector<InsnReplacementData, MAX_HEADER_SIZE> RD;
+ SmallVector<RenameData, MAX_HEADER_SIZE> LoopHeaderInfo;
};
RegisterPass<LoopRotate> X ("loop-rotate", "Rotate Loops");
LoopPass *llvm::createLoopRotatePass() { return new LoopRotate(); }
+/// Rotate Loop L as many times as possible. Return true if
+/// loop is rotated at least once.
bool LoopRotate::runOnLoop(Loop *Lp, LPPassManager &LPM) {
bool RotatedOneLoop = false;
return RotatedOneLoop;
}
+/// Rotate loop LP. Return true if it loop is rotated.
bool LoopRotate::rotateLoop(Loop *Lp, LPPassManager &LPM) {
L = Lp;
- if ( NumRotated >= RotateThreshold)
- return false;
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)
+ if (L->getBlocks().size() == 1)
return false;
if (!OrigHeader || !OrigLatch || !OrigPreHeader)
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;
// Find new Loop header. NewHeader is a Header's one and only successor
- // that is inside loop. Header's all other successors are out side the
+ // that is inside loop. Header's other successor is out side the
// loop. Otherwise loop is not suitable for rotation.
- for (unsigned index = 0; index < BI->getNumSuccessors(); ++index) {
- BasicBlock *S = BI->getSuccessor(index);
- if (L->contains(S)) {
- if (!NewHeader)
- NewHeader = S;
- else
- // Loop Header has two successors inside loop. This loop is
- // not suitable for rotation.
- return false;
- } else {
- if (!Exit)
- Exit = S;
- else
- // Loop has multiple exits.
- return false;
- }
- }
+ 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");
// Check size of original header and reject
// loop if it is very big.
// Now, this loop is suitable for rotation.
- // Copy Prepare PHI nodes and other instructions from original header
+ // 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.
// from new loop pre-header (which is a clone of original header definition).
NewPreHeader = new BasicBlock("bb.nph", OrigHeader->getParent(), OrigHeader);
- for (BasicBlock::iterator I = OrigHeader->begin(), E = OrigHeader->end();
- I != E; ++I) {
+ BasicBlock::iterator I = OrigHeader->begin(), E = OrigHeader->end();
+ for (; I != E; ++I) {
Instruction *In = I;
- if (PHINode *PN = dyn_cast<PHINode>(I)) {
+ PHINode *PN = dyn_cast<PHINode>(I);
+ if (!PN)
+ break;
- // 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);
-
- // 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.
- PHINode *NH = new PHINode(In->getType(), In->getName());
- NH->addIncoming(PN->getIncomingValueForBlock(OrigLatch), OrigHeader);
- NH->addIncoming(NPH, NewPreHeader);
- NewHeader->getInstList().push_front(NH);
-
- RD.push_back(InsnReplacementData(In, NPH, NH));
- } else {
- // This is not a PHI instruction. Insert its clone into NewPreHeader.
- // 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);
-
- // 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);
- NewHeader->getInstList().push_front(PN);
- NewHeaderReplacement = PN;
- }
- RD.push_back(InsnReplacementData(In, C, NewHeaderReplacement));
- }
+ // 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);
+
+ // 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.
+ PHINode *NH = new PHINode(In->getType(), In->getName());
+ NH->addIncoming(PN->getIncomingValueForBlock(OrigLatch), OrigHeader);
+ NH->addIncoming(NPH, NewPreHeader);
+ NewHeader->getInstList().push_front(NH);
+
+ // "In" can be replaced by NPH or NH at various places.
+ LoopHeaderInfo.push_back(RenameData(In, NPH, NH));
+ }
+
+ // Now, handle non-phi instructions.
+ for (; I != E; ++I) {
+ Instruction *In = I;
+
+ assert (!isa<PHINode>(In) && "PHINode is not expected here");
+ // This is not a PHI instruction. Insert its clone into NewPreHeader.
+ // 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);
+
+ // 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);
+ NewHeader->getInstList().push_front(PN);
+ NewHeaderReplacement = PN;
+ }
+
+ // "In" can be replaced by NPH or NH at various places.
+ 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 (SmallVector<InsnReplacementData, MAX_HEADER_SIZE>::iterator
- I = RD.begin(), E = RD.end(); I != E; ++I) {
+ for (SmallVector<RenameData, MAX_HEADER_SIZE>::iterator
+ I = LoopHeaderInfo.begin(), E = LoopHeaderInfo.end(); I != E; ++I) {
- InsnReplacementData IRD = (*I);
- Instruction *In = IRD.Original;
- Instruction *C = IRD.PreHeader;
+ RenameData ILoopHeaderInfo = (*I);
+ Instruction *In = ILoopHeaderInfo.Original;
+ Instruction *C = ILoopHeaderInfo.PreHeader;
if (C->getParent() != NewPreHeader)
continue;
for (unsigned opi = 0; opi < In->getNumOperands(); ++opi) {
if (Instruction *OpPhi = dyn_cast<PHINode>(In->getOperand(opi))) {
- if (InsnReplacementData *D = findReplacementData(OpPhi))
+ if (RenameData *D = findReplacementData(OpPhi))
C->setOperand(opi, D->PreHeader);
}
else if (Instruction *OpInsn =
dyn_cast<Instruction>(In->getOperand(opi))) {
- if (InsnReplacementData *D = findReplacementData(OpInsn))
+ if (RenameData *D = findReplacementData(OpInsn))
C->setOperand(opi, D->PreHeader);
}
}
// 2) Inside loop but not in original header
//
// Replace this use to reflect definition from new header.
- for (SmallVector<InsnReplacementData, MAX_HEADER_SIZE>::iterator
- I = RD.begin(), E = RD.end(); I != E; ++I) {
+ for (SmallVector<RenameData, MAX_HEADER_SIZE>::iterator
+ I = LoopHeaderInfo.begin(), E = LoopHeaderInfo.end(); I != E; ++I) {
- InsnReplacementData IRD = (*I);
- if (!IRD.Header)
+ RenameData ILoopHeaderInfo = (*I);
+ if (!ILoopHeaderInfo.Header)
continue;
- Instruction *OldPhi = IRD.Original;
- Instruction *NewPhi = IRD.Header;
+ Instruction *OldPhi = ILoopHeaderInfo.Original;
+ Instruction *NewPhi = ILoopHeaderInfo.Header;
// Before replacing uses, collect them first, so that iterator is
// not invalidated.
// UPhi already has one incoming argument from original header.
// Add second incoming argument from new Pre header.
- UPhi->addIncoming(IRD.PreHeader, NewPreHeader);
+ UPhi->addIncoming(ILoopHeaderInfo.PreHeader, NewPreHeader);
}
}
if (isa<Constant>(V))
PN->addIncoming(V, NewPreHeader);
else {
- InsnReplacementData *IRD = findReplacementData(cast<Instruction>(V));
- assert (IRD && IRD->PreHeader && "Missing New Preheader Instruction");
- PN->addIncoming(IRD->PreHeader, NewPreHeader);
+ RenameData *ILoopHeaderInfo = findReplacementData(cast<Instruction>(V));
+ assert (ILoopHeaderInfo && ILoopHeaderInfo->PreHeader && "Missing New Preheader Instruction");
+ PN->addIncoming(ILoopHeaderInfo->PreHeader, NewPreHeader);
}
}
}
NewPreHeader = NULL;
Exit = NULL;
- RD.clear();
+ LoopHeaderInfo.clear();
}
/// Return true if this instruction is used outside original header.
/// Find Replacement information for instruction. Return NULL if it is
/// not available.
-InsnReplacementData *LoopRotate::findReplacementData(Instruction *In) {
+RenameData *LoopRotate::findReplacementData(Instruction *In) {
- // Since RD is small, linear walk is OK.
- for (SmallVector<InsnReplacementData, MAX_HEADER_SIZE>::iterator
- I = RD.begin(), E = RD.end(); I != E; ++I)
+ // Since LoopHeaderInfo is small, linear walk is OK.
+ for (SmallVector<RenameData, MAX_HEADER_SIZE>::iterator
+ I = LoopHeaderInfo.begin(), E = LoopHeaderInfo.end(); I != E; ++I)
if ((*I).Original == In)
return &(*I);
projects / oota-llvm.git / commitdiff