[llvm-commits] CVS: llvm/lib/Transforms/Scalar/LoopRotation.cpp

2007-04-09 Thread Devang Patel


Changes in directory llvm/lib/Transforms/Scalar:

LoopRotation.cpp updated: 1.1 - 1.2
---
Log message:

Only cosmetic changes. Zero functionality Change.


---
Diffs of the changes:  (+100 -97)

 LoopRotation.cpp |  197 +++
 1 files changed, 100 insertions(+), 97 deletions(-)


Index: llvm/lib/Transforms/Scalar/LoopRotation.cpp
diff -u llvm/lib/Transforms/Scalar/LoopRotation.cpp:1.1 
llvm/lib/Transforms/Scalar/LoopRotation.cpp:1.2
--- llvm/lib/Transforms/Scalar/LoopRotation.cpp:1.1 Fri Apr  6 20:20:26 2007
+++ llvm/lib/Transforms/Scalar/LoopRotation.cpp Mon Apr  9 11:11:48 2007
@@ -11,7 +11,7 @@
 //
 
//===--===//
 
-#define DEBUG_TYPE loop-rotation
+#define DEBUG_TYPE loop-rotate
 
 #include llvm/Transforms/Scalar.h
 #include llvm/Function.h
@@ -23,7 +23,6 @@
 #include llvm/Support/Debug.h
 #include llvm/ADT/Statistic.h
 #include llvm/ADT/SmallVector.h
-#include map
 
 using namespace llvm;
 
@@ -32,29 +31,28 @@
 STATISTIC(NumRotated, Number of loops rotated);
 namespace {
 
-  cl::optunsigned
-  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.addRequiredLoopInfo();
-  //AU.addPreservedLoopInfo();
 }
 
 // Helper functions
@@ -75,7 +73,7 @@
 
 /// Find Replacement information for instruction. Return NULL if it is
 /// not available.
-InsnReplacementData *findReplacementData(Instruction *I);
+RenameData *findReplacementData(Instruction *I);
 
   private:
 
@@ -87,7 +85,7 @@
 BasicBlock *NewPreHeader;
 BasicBlock *Exit;
 
-SmallVectorInsnReplacementData, MAX_HEADER_SIZE RD;
+SmallVectorRenameData, MAX_HEADER_SIZE LoopHeaderInfo;
   };
   
   RegisterPassLoopRotate X (loop-rotate, Rotate Loops);
@@ -95,6 +93,8 @@
 
 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;
@@ -109,18 +109,17 @@
   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)
@@ -135,33 +134,27 @@
   BranchInst *BI = dyn_castBranchInst(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::vectorBasicBlock * 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);
+  

[llvm-commits] CVS: llvm/lib/Transforms/Scalar/LoopRotation.cpp

2007-04-09 Thread Devang Patel


Changes in directory llvm/lib/Transforms/Scalar:

LoopRotation.cpp updated: 1.2 - 1.3
---
Log message:

More cosmetic changes.


---
Diffs of the changes:  (+18 -14)

 LoopRotation.cpp |   32 ++--
 1 files changed, 18 insertions(+), 14 deletions(-)


Index: llvm/lib/Transforms/Scalar/LoopRotation.cpp
diff -u llvm/lib/Transforms/Scalar/LoopRotation.cpp:1.2 
llvm/lib/Transforms/Scalar/LoopRotation.cpp:1.3
--- llvm/lib/Transforms/Scalar/LoopRotation.cpp:1.2 Mon Apr  9 11:11:48 2007
+++ llvm/lib/Transforms/Scalar/LoopRotation.cpp Mon Apr  9 11:21:29 2007
@@ -238,10 +238,12 @@
   for (SmallVectorRenameData, MAX_HEADER_SIZE::iterator 
  I = LoopHeaderInfo.begin(), E = LoopHeaderInfo.end(); I != E; ++I) {
 
-RenameData ILoopHeaderInfo = (*I);
+const RenameData ILoopHeaderInfo = *I;
 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;
 
@@ -249,7 +251,7 @@
 if (isaPHINode(In))
   continue;
 
-for (unsigned opi = 0; opi  In-getNumOperands(); ++opi) {
+for (unsigned opi = 0, e = In-getNumOperands(); opi != e; ++opi) {
   if (Instruction *OpPhi = dyn_castPHINode(In-getOperand(opi))) {
 if (RenameData *D = findReplacementData(OpPhi))
   C-setOperand(opi, D-PreHeader);
@@ -283,7 +285,7 @@
   for (SmallVectorRenameData, MAX_HEADER_SIZE::iterator 
  I = LoopHeaderInfo.begin(), E = LoopHeaderInfo.end(); I != E; ++I) {
 
-RenameData ILoopHeaderInfo = (*I);
+const RenameData ILoopHeaderInfo = *I;
 if (!ILoopHeaderInfo.Header)
   continue;
 
@@ -294,7 +296,7 @@
 // not invalidated.
 SmallVectorInstruction *, 16 AllUses;
 for (Value::use_iterator UI = OldPhi-use_begin(), UE = OldPhi-use_end();
- UI != UE; ++UI ) {
+ UI != UE; ++UI) {
   Instruction *U = castInstruction(UI);
   AllUses.push_back(U);
 }
@@ -307,9 +309,10 @@
   // Used inside original header
   if (Parent == OrigHeader) {
 // Do not rename uses inside original header non-phi instructions.
-if (!isaPHINode(U))
-  continue;
 PHINode *PU = dyn_castPHINode(U);
+if (!PU)
+  continue;
+
 // Do not rename uses inside original header phi nodes, if the
 // incoming value is for new header.
 if (PU-getBasicBlockIndex(NewHeader) != -1
@@ -322,13 +325,14 @@
 
   // Used inside loop, but not in original header.
   if (L-contains(U-getParent())) {
-if (U != NewPhi )
+if (U != NewPhi)
   U-replaceUsesOfWith(OldPhi, NewPhi);
 continue;
   }
 
   // Used inside Exit Block. Since we are in LCSSA form, U must be PHINode.
-  assert ( U-getParent() == Exit  Need to propagate new PHI into Exit 
blocks);
+  assert (U-getParent() == Exit 
+   Need to propagate new PHI into Exit blocks);
   assert (isaPHINode(U)  Use in Exit Block that is not PHINode); 
   
 
   PHINode *UPhi = castPHINode(U);
@@ -374,10 +378,9 @@
   for (BasicBlock::iterator I = Exit-begin(), E = Exit-end();
I != E; ++I) {
 
-if (!isaPHINode(I))
-  break;
-
 PHINode *PN = dyn_castPHINode(I);
+if (!PN)
+  break;
 
 if (PN-getBasicBlockIndex(NewPreHeader) == -1) {
   Value *V = PN-getIncomingValueForBlock(OrigHeader);
@@ -405,7 +408,8 @@
   LoopHeaderInfo.clear();
 }
 
-/// Return true if this instruction is used outside original header.
+/// Return true if this instruction is used by any instructions in the loop 
that
+/// aren't in original header.
 bool LoopRotate::usedOutsideOriginalHeader(Instruction *In) {
 
   for (Value::use_iterator UI = In-use_begin(), UE = In-use_end();
@@ -427,7 +431,7 @@
   // Since LoopHeaderInfo is small, linear walk is OK.
   for (SmallVectorRenameData, MAX_HEADER_SIZE::iterator 
  I = LoopHeaderInfo.begin(), E = LoopHeaderInfo.end(); I != E; ++I) 
-if ((*I).Original == In)
+if (I-Original == In)
   return (*I);
 
   return NULL;



___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits


[llvm-commits] CVS: llvm/lib/Transforms/Scalar/LoopRotation.cpp

2007-04-09 Thread Devang Patel


Changes in directory llvm/lib/Transforms/Scalar:

LoopRotation.cpp updated: 1.3 - 1.4
---
Log message:

Fix future bug. Of course, Chris spotted this.
Handle Argument or Undef as an incoming PHI value.


---
Diffs of the changes:  (+12 -11)

 LoopRotation.cpp |   23 ---
 1 files changed, 12 insertions(+), 11 deletions(-)


Index: llvm/lib/Transforms/Scalar/LoopRotation.cpp
diff -u llvm/lib/Transforms/Scalar/LoopRotation.cpp:1.3 
llvm/lib/Transforms/Scalar/LoopRotation.cpp:1.4
--- llvm/lib/Transforms/Scalar/LoopRotation.cpp:1.3 Mon Apr  9 11:21:29 2007
+++ llvm/lib/Transforms/Scalar/LoopRotation.cpp Mon Apr  9 11:41:46 2007
@@ -369,7 +369,6 @@
   return true;
 }
 
-
 /// 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. 
@@ -382,20 +381,22 @@
 if (!PN)
   break;
 
-if (PN-getBasicBlockIndex(NewPreHeader) == -1) {
-  Value *V = PN-getIncomingValueForBlock(OrigHeader);
-  if (isaConstant(V))
-PN-addIncoming(V, NewPreHeader);
-  else {
-RenameData *ILoopHeaderInfo = 
findReplacementData(castInstruction(V));
-assert (ILoopHeaderInfo  ILoopHeaderInfo-PreHeader  Missing New 
Preheader Instruction);
-PN-addIncoming(ILoopHeaderInfo-PreHeader, NewPreHeader);
-  }
+// There is already one incoming value from new pre-header block.
+if (PN-getBasicBlockIndex(NewPreHeader) != -1)
+  return;
+
+RenameData *ILoopHeaderInfo;
+Value *V = PN-getIncomingValueForBlock(OrigHeader);
+if (isaInstruction(V)  
+(ILoopHeaderInfo = findReplacementData(castInstruction(V {
+  assert (ILoopHeaderInfo-PreHeader  Missing New Preheader 
Instruction);
+  PN-addIncoming(ILoopHeaderInfo-PreHeader, NewPreHeader);
+} else {
+  PN-addIncoming(V, NewPreHeader);
 }
   }
 }
 
-
 /// Initialize local data
 void LoopRotate::initialize() {
   L = NULL;



___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits


[llvm-commits] CVS: llvm/lib/Transforms/Scalar/LoopRotation.cpp

2007-04-09 Thread Devang Patel


Changes in directory llvm/lib/Transforms/Scalar:

LoopRotation.cpp updated: 1.4 - 1.5
---
Log message:

Simpler for() loops.


---
Diffs of the changes:  (+17 -23)

 LoopRotation.cpp |   40 +---
 1 files changed, 17 insertions(+), 23 deletions(-)


Index: llvm/lib/Transforms/Scalar/LoopRotation.cpp
diff -u llvm/lib/Transforms/Scalar/LoopRotation.cpp:1.4 
llvm/lib/Transforms/Scalar/LoopRotation.cpp:1.5
--- llvm/lib/Transforms/Scalar/LoopRotation.cpp:1.4 Mon Apr  9 11:41:46 2007
+++ llvm/lib/Transforms/Scalar/LoopRotation.cpp Mon Apr  9 12:09:13 2007
@@ -73,7 +73,7 @@
 
 /// Find Replacement information for instruction. Return NULL if it is
 /// not available.
-RenameData *findReplacementData(Instruction *I);
+const RenameData *findReplacementData(Instruction *I);
 
   private:
 
@@ -179,13 +179,10 @@
 
   NewPreHeader = new BasicBlock(bb.nph, OrigHeader-getParent(), OrigHeader);
   BasicBlock::iterator I = OrigHeader-begin(), E = OrigHeader-end();
-  for (; I != E; ++I) {
+  PHINode *PN = NULL;
+  for (; (PN = dyn_castPHINode(I)); ++I) {
 Instruction *In = I;
 
-PHINode *PN = dyn_castPHINode(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());
@@ -235,10 +232,8 @@
   // Update new pre-header.
   // Rename values that are defined in original header to reflects values
   // defined in new pre-header.
-  for (SmallVectorRenameData, MAX_HEADER_SIZE::iterator 
- I = LoopHeaderInfo.begin(), E = LoopHeaderInfo.end(); I != E; ++I) {
-
-const RenameData ILoopHeaderInfo = *I;
+  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;
 
@@ -253,12 +248,12 @@
 
 for (unsigned opi = 0, e = In-getNumOperands(); opi != e; ++opi) {
   if (Instruction *OpPhi = dyn_castPHINode(In-getOperand(opi))) {
-if (RenameData *D = findReplacementData(OpPhi))
+if (const RenameData *D = findReplacementData(OpPhi))
   C-setOperand(opi, D-PreHeader);
   }
   else if (Instruction *OpInsn = 
dyn_castInstruction(In-getOperand(opi))) {
-if (RenameData *D = findReplacementData(OpInsn))
+if (const RenameData *D = findReplacementData(OpInsn))
   C-setOperand(opi, D-PreHeader);
   }
 }
@@ -282,10 +277,9 @@
   // 2) Inside loop but not in original header
   //
   //Replace this use to reflect definition from new header.
-  for (SmallVectorRenameData, MAX_HEADER_SIZE::iterator 
- I = LoopHeaderInfo.begin(), E = LoopHeaderInfo.end(); I != E; ++I) {
+  for(unsigned LHI = 0, LHI_E = LoopHeaderInfo.size(); LHI != LHI_E; ++LHI) {
+const RenameData ILoopHeaderInfo = LoopHeaderInfo[LHI];
 
-const RenameData ILoopHeaderInfo = *I;
 if (!ILoopHeaderInfo.Header)
   continue;
 
@@ -318,7 +312,7 @@
 if (PU-getBasicBlockIndex(NewHeader) != -1
  PU-getIncomingValueForBlock(NewHeader) == U)
   continue;
-
+
U-replaceUsesOfWith(OldPhi, NewPhi);
continue;
   }
@@ -385,7 +379,7 @@
 if (PN-getBasicBlockIndex(NewPreHeader) != -1)
   return;
 
-RenameData *ILoopHeaderInfo;
+const RenameData *ILoopHeaderInfo;
 Value *V = PN-getIncomingValueForBlock(OrigHeader);
 if (isaInstruction(V)  
 (ILoopHeaderInfo = findReplacementData(castInstruction(V {
@@ -427,13 +421,13 @@
 
 /// Find Replacement information for instruction. Return NULL if it is
 /// not available.
-RenameData *LoopRotate::findReplacementData(Instruction *In) {
+const RenameData *LoopRotate::findReplacementData(Instruction *In) {
 
   // Since LoopHeaderInfo is small, linear walk is OK.
-  for (SmallVectorRenameData, MAX_HEADER_SIZE::iterator 
- I = LoopHeaderInfo.begin(), E = LoopHeaderInfo.end(); I != E; ++I) 
-if (I-Original == In)
-  return (*I);
-
+  for(unsigned LHI = 0, LHI_E = LoopHeaderInfo.size(); LHI != LHI_E; ++LHI) {
+const RenameData ILoopHeaderInfo = LoopHeaderInfo[LHI];
+if (ILoopHeaderInfo.Original == In)
+  return ILoopHeaderInfo;
+  }
   return NULL;
 }



___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits


[llvm-commits] CVS: llvm/lib/Transforms/Scalar/LoopRotation.cpp

2007-04-09 Thread Devang Patel


Changes in directory llvm/lib/Transforms/Scalar:

LoopRotation.cpp updated: 1.5 - 1.6
---
Log message:

Do not create new pre-header. Reuse original pre-header.


---
Diffs of the changes:  (+57 -73)

 LoopRotation.cpp |  130 ---
 1 files changed, 57 insertions(+), 73 deletions(-)


Index: llvm/lib/Transforms/Scalar/LoopRotation.cpp
diff -u llvm/lib/Transforms/Scalar/LoopRotation.cpp:1.5 
llvm/lib/Transforms/Scalar/LoopRotation.cpp:1.6
--- llvm/lib/Transforms/Scalar/LoopRotation.cpp:1.5 Mon Apr  9 12:09:13 2007
+++ llvm/lib/Transforms/Scalar/LoopRotation.cpp Mon Apr  9 14:04:21 2007
@@ -33,11 +33,11 @@
 
   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 @@
 
 /// 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 @@
 BasicBlock *OrigPreHeader;
 BasicBlock *OrigLatch;
 BasicBlock *NewHeader;
-BasicBlock *NewPreHeader;
 BasicBlock *Exit;
 
 SmallVectorRenameData, MAX_HEADER_SIZE LoopHeaderInfo;
@@ -125,6 +124,9 @@
   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 @@
   // 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_castPHINode(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.
@@ 

[llvm-commits] CVS: llvm/lib/Transforms/Scalar/LoopRotation.cpp

2007-04-09 Thread Devang Patel


Changes in directory llvm/lib/Transforms/Scalar:

LoopRotation.cpp updated: 1.6 - 1.7
---
Log message:

Preserve canonical loop form.


---
Diffs of the changes:  (+55 -5)

 LoopRotation.cpp |   60 ++-
 1 files changed, 55 insertions(+), 5 deletions(-)


Index: llvm/lib/Transforms/Scalar/LoopRotation.cpp
diff -u llvm/lib/Transforms/Scalar/LoopRotation.cpp:1.6 
llvm/lib/Transforms/Scalar/LoopRotation.cpp:1.7
--- llvm/lib/Transforms/Scalar/LoopRotation.cpp:1.6 Mon Apr  9 14:04:21 2007
+++ llvm/lib/Transforms/Scalar/LoopRotation.cpp Mon Apr  9 15:19:46 2007
@@ -75,6 +75,11 @@
 /// not available.
 const RenameData *findReplacementData(Instruction *I);
 
+/// After loop rotation, loop pre-header has multiple sucessors.
+/// Insert one forwarding basic block to ensure that loop pre-header
+/// has only one successor.
+void preserveCanonicalLoopForm(LPPassManager LPM);
+
   private:
 
 Loop *L;
@@ -121,11 +126,8 @@
   if (L-getBlocks().size() == 1)
 return false;
 
-  if (!OrigHeader || !OrigLatch || !OrigPreHeader)
-return false;
-
-  if (!OrigHeader || !OrigLatch || !OrigPreHeader)
-return false;
+  assert (OrigHeader  OrigLatch  OrigPreHeader 
+  Loop is not in cannocial form);
 
   // If loop header is not one of the loop exit block then
   // either this loop is already rotated or it is not 
@@ -344,6 +346,8 @@
   // Make NewHeader as the new header for the loop.
   L-moveToHeader(NewHeader);
 
+  preserveCanonicalLoopForm(LPM);
+
   NumRotated++;
   return true;
 }
@@ -415,3 +419,49 @@
   }
   return NULL;
 }
+
+/// After loop rotation, loop pre-header has multiple sucessors.
+/// Insert one forwarding basic block to ensure that loop pre-header
+/// has only one successor.
+void LoopRotate::preserveCanonicalLoopForm(LPPassManager LPM) {
+
+  // Right now original pre-header has two successors, new header and
+  // exit block. Insert new block between original pre-header and
+  // new header such that loop's new pre-header has only one successor.
+  BasicBlock *NewPreHeader = new BasicBlock(bb.nph, OrigHeader-getParent(), 
+OrigPreHeader);
+  LoopInfo LI = LPM.getAnalysisLoopInfo();
+  if (Loop *PL = LI.getLoopFor(OrigPreHeader))
+PL-addBasicBlockToLoop(NewPreHeader, LI);
+  new BranchInst(NewHeader, NewPreHeader);
+  
+  BranchInst *OrigPH_BI = castBranchInst(OrigPreHeader-getTerminator());
+  if (OrigPH_BI-getSuccessor(0) == NewHeader)
+OrigPH_BI-setSuccessor(0, NewPreHeader);
+  else {
+assert (OrigPH_BI-getSuccessor(1) == NewPreHeader 
+Unexpected original pre-header terminator);
+OrigPH_BI-setSuccessor(1, NewPreHeader);
+  }
+  
+  for (BasicBlock::iterator I = NewHeader-begin(), E = NewHeader-end();
+   I != E; ++I) {
+Instruction *In = I;
+PHINode *PN = dyn_castPHINode(In);
+if (!PN)
+  break;
+
+int index = PN-getBasicBlockIndex(OrigPreHeader);
+assert (index != -1  Expected incoming value from Original PreHeader);
+PN-setIncomingBlock(index, NewPreHeader);
+assert (PN-getBasicBlockIndex(OrigPreHeader) == -1  
+Expected only one incoming value from Original PreHeader);
+  }
+
+  assert (NewHeader  L-getHeader() == NewHeader 
+   Invalid loop header after loop rotation);
+  assert (NewPreHeader  L-getLoopPreheader() == NewPreHeader
+   Invalid loop preheader after loop rotation);
+  assert (L-getLoopLatch() 
+   Invalid loop latch after loop rotation);
+}



___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits


[llvm-commits] CVS: llvm/lib/Transforms/Scalar/LoopRotation.cpp

2007-04-09 Thread Devang Patel


Changes in directory llvm/lib/Transforms/Scalar:

LoopRotation.cpp updated: 1.8 - 1.9
---
Log message:

Check _all_ PHINodes.


---
Diffs of the changes:  (+1 -1)

 LoopRotation.cpp |2 +-
 1 files changed, 1 insertion(+), 1 deletion(-)


Index: llvm/lib/Transforms/Scalar/LoopRotation.cpp
diff -u llvm/lib/Transforms/Scalar/LoopRotation.cpp:1.8 
llvm/lib/Transforms/Scalar/LoopRotation.cpp:1.9
--- llvm/lib/Transforms/Scalar/LoopRotation.cpp:1.8 Mon Apr  9 16:40:43 2007
+++ llvm/lib/Transforms/Scalar/LoopRotation.cpp Mon Apr  9 17:20:10 2007
@@ -366,7 +366,7 @@
 
 // There is already one incoming value from original pre-header block.
 if (PN-getBasicBlockIndex(OrigPreHeader) != -1)
-  return;
+  continue;
 
 const RenameData *ILoopHeaderInfo;
 Value *V = PN-getIncomingValueForBlock(OrigHeader);



___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits


[llvm-commits] CVS: llvm/lib/Transforms/Scalar/LoopRotation.cpp

2007-04-06 Thread Devang Patel


Changes in directory llvm/lib/Transforms/Scalar:

LoopRotation.cpp added (r1.1)
---
Log message:

Add loop rotation pass.


---
Diffs of the changes:  (+431 -0)

 LoopRotation.cpp |  431 +++
 1 files changed, 431 insertions(+)


Index: llvm/lib/Transforms/Scalar/LoopRotation.cpp
diff -c /dev/null llvm/lib/Transforms/Scalar/LoopRotation.cpp:1.1
*** /dev/null   Fri Apr  6 20:20:36 2007
--- llvm/lib/Transforms/Scalar/LoopRotation.cpp Fri Apr  6 20:20:26 2007
***
*** 0 
--- 1,431 
+ //===- LoopRotation.cpp - Loop Rotation Pass 
--===//
+ //
+ // The LLVM Compiler Infrastructure
+ //
+ // This file was developed by Devang Patel and is distributed under
+ // the University of Illinois Open Source License. See LICENSE.TXT for 
details.
+ //
+ 
//===--===//
+ //
+ // This file implements Loop Rotation Pass.
+ //
+ 
//===--===//
+ 
+ #define DEBUG_TYPE loop-rotation
+ 
+ #include llvm/Transforms/Scalar.h
+ #include llvm/Function.h
+ #include llvm/Instructions.h
+ #include llvm/Analysis/LoopInfo.h
+ #include llvm/Analysis/LoopPass.h
+ #include llvm/Transforms/Utils/Local.h
+ #include llvm/Support/CommandLine.h
+ #include llvm/Support/Debug.h
+ #include llvm/ADT/Statistic.h
+ #include llvm/ADT/SmallVector.h
+ #include map
+ 
+ using namespace llvm;
+ 
+ #define MAX_HEADER_SIZE 16
+ 
+ STATISTIC(NumRotated, Number of loops rotated);
+ namespace {
+ 
+   cl::optunsigned
+   RotateThreshold(rotate-threshold, cl::init(200), cl::Hidden,
+   cl::desc(The cut-off point for loop rotating));
+ 
+   class VISIBILITY_HIDDEN InsnReplacementData {
+   public:
+ InsnReplacementData(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:
+ bool runOnLoop(Loop *L, LPPassManager LPM);
+ virtual void getAnalysisUsage(AnalysisUsage AU) const {
+   AU.addRequiredID(LCSSAID);
+   AU.addPreservedID(LCSSAID);
+   //AU.addRequiredLoopInfo();
+   //AU.addPreservedLoopInfo();
+ }
+ 
+ // Helper functions
+ 
+ /// Do actual work
+ bool rotateLoop(Loop *L, LPPassManager LPM);
+ 
+ /// Initialize local data
+ void initialize();
+ 
+ /// 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. 
+ void  updateExitBlock();
+ 
+ /// Return true if this instruction is used outside original header.
+ bool usedOutsideOriginalHeader(Instruction *In);
+ 
+ /// Find Replacement information for instruction. Return NULL if it is
+ /// not available.
+ InsnReplacementData *findReplacementData(Instruction *I);
+ 
+   private:
+ 
+ Loop *L;
+ BasicBlock *OrigHeader;
+ BasicBlock *OrigPreHeader;
+ BasicBlock *OrigLatch;
+ BasicBlock *NewHeader;
+ BasicBlock *NewPreHeader;
+ BasicBlock *Exit;
+ 
+ SmallVectorInsnReplacementData, MAX_HEADER_SIZE RD;
+   };
+   
+   RegisterPassLoopRotate X (loop-rotate, Rotate Loops);
+ }
+ 
+ LoopPass *llvm::createLoopRotatePass() { return new LoopRotate(); }
+ 
+ bool LoopRotate::runOnLoop(Loop *Lp, LPPassManager LPM) {
+   
+   bool RotatedOneLoop = false;
+   initialize();
+ 
+   // One loop can be rotated multiple times.
+   while (rotateLoop(Lp,LPM)) {
+ RotatedOneLoop = true;
+ initialize();
+   }
+ 
+   return RotatedOneLoop;
+ }
+ 
+ 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)
+ 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.
+   if (!L-isLoopExit(OrigHeader))
+ return false;
+ 
+   BranchInst *BI = dyn_castBranchInst(OrigHeader-getTerminator());
+   if (!BI)
+ return false;
+ 
+   std::vectorBasicBlock * 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
+   // loop.