[llvm-commits] CVS: llvm/lib/Transforms/Scalar/LCSSA.cpp
Changes in directory llvm/lib/Transforms/Scalar:
LCSSA.cpp updated: 1.13 - 1.14
---
Log message:
Stop a memory leak, and update some comments.
---
Diffs of the changes: (+10 -10)
LCSSA.cpp | 20 ++--
1 files changed, 10 insertions(+), 10 deletions(-)
Index: llvm/lib/Transforms/Scalar/LCSSA.cpp
diff -u llvm/lib/Transforms/Scalar/LCSSA.cpp:1.13
llvm/lib/Transforms/Scalar/LCSSA.cpp:1.14
--- llvm/lib/Transforms/Scalar/LCSSA.cpp:1.13 Sat Jun 3 19:55:19 2006
+++ llvm/lib/Transforms/Scalar/LCSSA.cppMon Jun 5 23:28:30 2006
@@ -52,7 +52,7 @@
LoopInfo *LI; // Loop information
DominatorTree *DT; // Dominator Tree for the current Function...
DominanceFrontier *DF; // Current Dominance Frontier
-std::vectorBasicBlock* *LoopBlocks;
+std::vectorBasicBlock* LoopBlocks;
virtual bool runOnFunction(Function F);
bool visitSubloop(Loop* L);
@@ -76,8 +76,9 @@
Instruction *getValueDominatingBlock(BasicBlock *BB,
std::mapBasicBlock*, Instruction*
PotDoms);
-bool inLoopBlocks(BasicBlock* B) { return std::binary_search(
- LoopBlocks-begin(), LoopBlocks-end(), B);
}
+/// inLoop - returns true if the given block is within the current loop
+const bool inLoop(BasicBlock* B) {
+ return std::binary_search(LoopBlocks.begin(), LoopBlocks.end(), B);
}
};
RegisterOptLCSSA X(lcssa, Loop-Closed SSA Form Pass);
@@ -90,7 +91,6 @@
LI = getAnalysisLoopInfo();
DF = getAnalysisDominanceFrontier();
DT = getAnalysisDominatorTree();
- LoopBlocks = new std::vectorBasicBlock*;
for (LoopInfo::iterator I = LI-begin(), E = LI-end(); I != E; ++I) {
changed |= visitSubloop(*I);
@@ -104,9 +104,9 @@
visitSubloop(*I);
// Speed up queries by creating a sorted list of blocks
- LoopBlocks-clear();
- LoopBlocks-insert(LoopBlocks-end(), L-block_begin(), L-block_end());
- std::sort(LoopBlocks-begin(), LoopBlocks-end());
+ LoopBlocks.clear();
+ LoopBlocks.insert(LoopBlocks.end(), L-block_begin(), L-block_end());
+ std::sort(LoopBlocks.begin(), LoopBlocks.end());
SetVectorInstruction* AffectedValues = getLoopValuesUsedOutsideLoop(L);
@@ -127,7 +127,7 @@
processInstruction(*I, exitBlocks);
}
- return true; // FIXME: Should be more intelligent in our return value.
+ return true;
}
/// processInstruction -
@@ -205,7 +205,7 @@
UI != UE; ++UI) {
Instruction* use = castInstruction(*UI);
// Don't need to update uses within the loop body.
-if (!inLoopBlocks(use-getParent()))
+if (!inLoop(use-getParent()))
Uses.push_back(use);
}
@@ -242,7 +242,7 @@
for (Value::use_iterator UI = I-use_begin(), E = I-use_end(); UI != E;
++UI) {
BasicBlock *UserBB = castInstruction(*UI)-getParent();
-if (!std::binary_search(LoopBlocks-begin(), LoopBlocks-end(),
UserBB))
+if (!std::binary_search(LoopBlocks.begin(), LoopBlocks.end(), UserBB))
{
AffectedValues.insert(I);
break;
___
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/LCSSA.cpp
Changes in directory llvm/lib/Transforms/Scalar:
LCSSA.cpp updated: 1.14 - 1.15
---
Log message:
Fix some formatting, and use inLoop() when appropriate.
---
Diffs of the changes: (+3 -3)
LCSSA.cpp |6 +++---
1 files changed, 3 insertions(+), 3 deletions(-)
Index: llvm/lib/Transforms/Scalar/LCSSA.cpp
diff -u llvm/lib/Transforms/Scalar/LCSSA.cpp:1.14
llvm/lib/Transforms/Scalar/LCSSA.cpp:1.15
--- llvm/lib/Transforms/Scalar/LCSSA.cpp:1.14 Mon Jun 5 23:28:30 2006
+++ llvm/lib/Transforms/Scalar/LCSSA.cppMon Jun 5 23:36:36 2006
@@ -78,7 +78,8 @@
/// inLoop - returns true if the given block is within the current loop
const bool inLoop(BasicBlock* B) {
- return std::binary_search(LoopBlocks.begin(), LoopBlocks.end(), B);
}
+ return std::binary_search(LoopBlocks.begin(), LoopBlocks.end(), B);
+}
};
RegisterOptLCSSA X(lcssa, Loop-Closed SSA Form Pass);
@@ -242,8 +243,7 @@
for (Value::use_iterator UI = I-use_begin(), E = I-use_end(); UI != E;
++UI) {
BasicBlock *UserBB = castInstruction(*UI)-getParent();
-if (!std::binary_search(LoopBlocks.begin(), LoopBlocks.end(), UserBB))
-{
+if (!inLoop(UserBB)) {
AffectedValues.insert(I);
break;
}
___
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/LCSSA.cpp
Changes in directory llvm/lib/Transforms/Scalar:
LCSSA.cpp updated: 1.10 - 1.11
---
Log message:
Fix a bug in Phi-noded insertion. Also, update some comments to reflect what's
actually going on.
---
Diffs of the changes: (+21 -12)
LCSSA.cpp | 33 +
1 files changed, 21 insertions(+), 12 deletions(-)
Index: llvm/lib/Transforms/Scalar/LCSSA.cpp
diff -u llvm/lib/Transforms/Scalar/LCSSA.cpp:1.10
llvm/lib/Transforms/Scalar/LCSSA.cpp:1.11
--- llvm/lib/Transforms/Scalar/LCSSA.cpp:1.10 Thu Jun 1 01:07:40 2006
+++ llvm/lib/Transforms/Scalar/LCSSA.cppSat Jun 3 18:22:50 2006
@@ -36,9 +36,7 @@
#include llvm/Analysis/LoopInfo.h
#include llvm/Support/CFG.h
#include algorithm
-#include cassert
#include map
-#include vector
using namespace llvm;
@@ -69,7 +67,6 @@
AU.addRequiredID(LoopSimplifyID);
AU.addPreservedID(LoopSimplifyID);
AU.addRequiredLoopInfo();
- AU.addPreservedLoopInfo();
AU.addRequiredDominatorTree();
AU.addRequiredDominanceFrontier();
}
@@ -137,6 +134,10 @@
++NumLCSSA; // We are applying the transformation
std::mapBasicBlock*, Instruction* Phis;
+
+ // Add the base instruction to the Phis list. This makes tracking down
+ // the dominating values easier when we're filling in Phi nodes. This will
+ // be removed later, before we perform use replacement.
Phis[Instr-getParent()] = Instr;
// Phi nodes that need to be IDF-processed
@@ -150,12 +151,19 @@
Phis[*BBI] = phi;
}
+ // Phi nodes that need to have their incoming values filled.
+ std::vectorPHINode* needIncomingValues;
+
// Calculate the IDF of these LCSSA Phi nodes, inserting new Phi's where
// necessary. Keep track of these new Phi's in Phis.
while (!workList.empty()) {
PHINode *CurPHI = workList.back();
workList.pop_back();
+// Even though we've removed this Phi from the work list, we still need
+// to fill in its incoming values.
+needIncomingValues.push_back(CurPHI);
+
// Get the current Phi's DF, and insert Phi nodes. Add these new
// nodes to our worklist.
DominanceFrontier::const_iterator it = DF-find(CurPHI-getParent());
@@ -172,14 +180,14 @@
}
}
}
-
-// Get the predecessor blocks of the current Phi, and use them to hook up
-// the operands of the current Phi to any members of DFPhis that dominate
-// it. This is a nop for the Phis inserted directly in the exit blocks,
-// since they are not dominated by any members of DFPhis.
-for (pred_iterator PI = pred_begin(CurPHI-getParent()),
- E = pred_end(CurPHI-getParent()); PI != E; ++PI)
- CurPHI-addIncoming(getValueDominatingBlock(*PI, Phis),
+ }
+
+ // Fill in all Phis we've inserted that need their incoming values filled in.
+ for (std::vectorPHINode*::iterator IVI = needIncomingValues.begin(),
+ IVE = needIncomingValues.end(); IVI != IVE; ++IVI) {
+for (pred_iterator PI = pred_begin((*IVI)-getParent()),
+ E = pred_end((*IVI)-getParent()); PI != E; ++PI)
+ (*IVI)-addIncoming(getValueDominatingBlock(*PI, Phis),
*PI);
}
@@ -197,7 +205,8 @@
Uses.push_back(use);
}
- // Deliberately remove the initial instruction from Phis set.
+ // Deliberately remove the initial instruction from Phis set. It would mess
+ // up use-replacement.
Phis.erase(Instr-getParent());
for (std::vectorInstruction*::iterator II = Uses.begin(), IE = Uses.end();
___
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/LCSSA.cpp
Changes in directory llvm/lib/Transforms/Scalar:
LCSSA.cpp updated: 1.11 - 1.12
---
Log message:
Various clean-ups suggested by Chris.
---
Diffs of the changes: (+32 -30)
LCSSA.cpp | 62 --
1 files changed, 32 insertions(+), 30 deletions(-)
Index: llvm/lib/Transforms/Scalar/LCSSA.cpp
diff -u llvm/lib/Transforms/Scalar/LCSSA.cpp:1.11
llvm/lib/Transforms/Scalar/LCSSA.cpp:1.12
--- llvm/lib/Transforms/Scalar/LCSSA.cpp:1.11 Sat Jun 3 18:22:50 2006
+++ llvm/lib/Transforms/Scalar/LCSSA.cppSat Jun 3 19:02:23 2006
@@ -31,6 +31,7 @@
#include llvm/Pass.h
#include llvm/Function.h
#include llvm/Instructions.h
+#include llvm/ADT/SetVector.h
#include llvm/ADT/Statistic.h
#include llvm/Analysis/Dominators.h
#include llvm/Analysis/LoopInfo.h
@@ -51,11 +52,11 @@
LoopInfo *LI; // Loop information
DominatorTree *DT; // Dominator Tree for the current Loop...
DominanceFrontier *DF; // Current Dominance Frontier
+std::vectorBasicBlock* *LoopBlocks;
virtual bool runOnFunction(Function F);
bool visitSubloop(Loop* L);
void processInstruction(Instruction* Instr,
-const std::vectorBasicBlock* LoopBlocks,
const std::vectorBasicBlock* exitBlocks);
/// This transformation requires natural loop information requires that
@@ -71,10 +72,12 @@
AU.addRequiredDominanceFrontier();
}
private:
-std::setInstruction* getLoopValuesUsedOutsideLoop(Loop *L,
-const std::vectorBasicBlock*
LoopBlocks);
+SetVectorInstruction* getLoopValuesUsedOutsideLoop(Loop *L);
Instruction *getValueDominatingBlock(BasicBlock *BB,
- std::mapBasicBlock*, Instruction*
PotDoms);
+ std::mapBasicBlock*, Instruction*
PotDoms);
+
+bool inLoopBlocks(BasicBlock* B) { return std::binary_search(
+ LoopBlocks-begin(), LoopBlocks-end(), B);
}
};
RegisterOptLCSSA X(lcssa, Loop-Closed SSA Form Pass);
@@ -87,6 +90,7 @@
LI = getAnalysisLoopInfo();
DF = getAnalysisDominanceFrontier();
DT = getAnalysisDominatorTree();
+ LoopBlocks = new std::vectorBasicBlock*;
for (LoopInfo::iterator I = LI-begin(), E = LI-end(); I != E; ++I) {
changed |= visitSubloop(*I);
@@ -100,11 +104,11 @@
visitSubloop(*I);
// Speed up queries by creating a sorted list of blocks
- std::vectorBasicBlock* LoopBlocks(L-block_begin(), L-block_end());
- std::sort(LoopBlocks.begin(), LoopBlocks.end());
+ LoopBlocks-clear();
+ LoopBlocks-insert(LoopBlocks-end(), L-block_begin(), L-block_end());
+ std::sort(LoopBlocks-begin(), LoopBlocks-end());
- std::setInstruction* AffectedValues = getLoopValuesUsedOutsideLoop(L,
- LoopBlocks);
+ SetVectorInstruction* AffectedValues = getLoopValuesUsedOutsideLoop(L);
// If no values are affected, we can save a lot of work, since we know that
// nothing will be changed.
@@ -118,9 +122,9 @@
// Iterate over all affected values for this loop and insert Phi nodes
// for them in the appropriate exit blocks
- for (std::setInstruction*::iterator I = AffectedValues.begin(),
+ for (SetVectorInstruction*::iterator I = AffectedValues.begin(),
E = AffectedValues.end(); I != E; ++I) {
-processInstruction(*I, LoopBlocks, exitBlocks);
+processInstruction(*I, exitBlocks);
}
return true; // FIXME: Should be more intelligent in our return value.
@@ -128,7 +132,6 @@
/// processInstruction -
void LCSSA::processInstruction(Instruction* Instr,
- const std::vectorBasicBlock* LoopBlocks,
const std::vectorBasicBlock* exitBlocks)
{
++NumLCSSA; // We are applying the transformation
@@ -155,7 +158,7 @@
std::vectorPHINode* needIncomingValues;
// Calculate the IDF of these LCSSA Phi nodes, inserting new Phi's where
- // necessary. Keep track of these new Phi's in Phis.
+ // necessary. Keep track of these new Phi's in the Phis map.
while (!workList.empty()) {
PHINode *CurPHI = workList.back();
workList.pop_back();
@@ -171,12 +174,12 @@
const DominanceFrontier::DomSetType S = it-second;
for (DominanceFrontier::DomSetType::const_iterator P = S.begin(),
PE = S.end(); P != PE; ++P) {
-if (Phis[*P] == 0) {
+Instruction *Phi = Phis[*P];
+if (Phi == 0) {
// Still doesn't have operands...
- PHINode *phi = new PHINode(Instr-getType(), lcssa, (*P)-begin());
- Phis[*P] = phi;
+ Phi = new PHINode(Instr-getType(), lcssa, (*P)-begin());
- workList.push_back(phi);
+ workList.push_back(castPHINode(Phi));
}
}
}
@@ -197,9 +200,9 @@
for
[llvm-commits] CVS: llvm/lib/Transforms/Scalar/LCSSA.cpp
Changes in directory llvm/lib/Transforms/Scalar:
LCSSA.cpp updated: 1.12 - 1.13
---
Log message:
Some more clean-up, and squash an IDF-Phi related bug.
---
Diffs of the changes: (+13 -16)
LCSSA.cpp | 29 +
1 files changed, 13 insertions(+), 16 deletions(-)
Index: llvm/lib/Transforms/Scalar/LCSSA.cpp
diff -u llvm/lib/Transforms/Scalar/LCSSA.cpp:1.12
llvm/lib/Transforms/Scalar/LCSSA.cpp:1.13
--- llvm/lib/Transforms/Scalar/LCSSA.cpp:1.12 Sat Jun 3 19:02:23 2006
+++ llvm/lib/Transforms/Scalar/LCSSA.cppSat Jun 3 19:55:19 2006
@@ -50,7 +50,7 @@
LoopInfo *LI; // Loop information
-DominatorTree *DT; // Dominator Tree for the current Loop...
+DominatorTree *DT; // Dominator Tree for the current Function...
DominanceFrontier *DF; // Current Dominance Frontier
std::vectorBasicBlock* *LoopBlocks;
@@ -149,7 +149,8 @@
for (std::vectorBasicBlock*::const_iterator BBI = exitBlocks.begin(),
BBE = exitBlocks.end(); BBI != BBE; ++BBI)
if (DT-getNode(Instr-getParent())-dominates(DT-getNode(*BBI))) {
- PHINode *phi = new PHINode(Instr-getType(), lcssa, (*BBI)-begin());
+ PHINode *phi = new PHINode(Instr-getType(), Instr-getName()+.lcssa,
+ (*BBI)-begin());
workList.push_back(phi);
Phis[*BBI] = phi;
}
@@ -174,12 +175,15 @@
const DominanceFrontier::DomSetType S = it-second;
for (DominanceFrontier::DomSetType::const_iterator P = S.begin(),
PE = S.end(); P != PE; ++P) {
-Instruction *Phi = Phis[*P];
-if (Phi == 0) {
- // Still doesn't have operands...
- Phi = new PHINode(Instr-getType(), lcssa, (*P)-begin());
+if (DT-getNode(Instr-getParent())-dominates(DT-getNode(*P))) {
+ Instruction *Phi = Phis[*P];
+ if (Phi == 0) {
+// Still doesn't have operands...
+Phi = new PHINode(Instr-getType(), Instr-getName()+.lcssa,
+ (*P)-begin());
- workList.push_back(castPHINode(Phi));
+workList.push_back(castPHINode(Phi));
+ }
}
}
}
@@ -200,18 +204,11 @@
for (Instruction::use_iterator UI = Instr-use_begin(), UE =
Instr-use_end();
UI != UE; ++UI) {
Instruction* use = castInstruction(*UI);
-// Don't need to update uses within the loop body, and we don't want to
-// overwrite the Phi nodes that we inserted into the exit blocks either.
-if (!inLoopBlocks(use-getParent())
-!(std::binary_search(exitBlocks.begin(), exitBlocks.end(),
-use-getParent()) isaPHINode(use)))
+// Don't need to update uses within the loop body.
+if (!inLoopBlocks(use-getParent()))
Uses.push_back(use);
}
- // Deliberately remove the initial instruction from Phis set. It would mess
- // up use-replacement.
- Phis.erase(Instr-getParent());
-
for (std::vectorInstruction*::iterator II = Uses.begin(), IE = Uses.end();
II != IE; ++II) {
if (PHINode* phi = dyn_castPHINode(*II)) {
___
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/LCSSA.cpp
Changes in directory llvm/lib/Transforms/Scalar:
LCSSA.cpp updated: 1.7 - 1.8
---
Log message:
Extract a huge loop into a helper method. Fix a few iterator-invalidation bugs.
---
Diffs of the changes: (+115 -88)
LCSSA.cpp | 203 +++---
1 files changed, 115 insertions(+), 88 deletions(-)
Index: llvm/lib/Transforms/Scalar/LCSSA.cpp
diff -u llvm/lib/Transforms/Scalar/LCSSA.cpp:1.7
llvm/lib/Transforms/Scalar/LCSSA.cpp:1.8
--- llvm/lib/Transforms/Scalar/LCSSA.cpp:1.7Sun May 28 20:00:00 2006
+++ llvm/lib/Transforms/Scalar/LCSSA.cppWed May 31 15:55:06 2006
@@ -36,6 +36,7 @@
#include llvm/Analysis/LoopInfo.h
#include llvm/Support/CFG.h
#include algorithm
+#include iostream
#include map
#include vector
@@ -55,6 +56,9 @@
virtual bool runOnFunction(Function F);
bool visitSubloop(Loop* L);
+void processInstruction(Instruction* Instr,
+const std::vectorBasicBlock* LoopBlocks,
+const std::vectorBasicBlock* exitBlocks);
/// This transformation requires natural loop information requires that
/// loop preheaders be inserted into the CFG. It maintains both of these,
@@ -71,7 +75,9 @@
}
private:
std::setInstruction* getLoopValuesUsedOutsideLoop(Loop *L,
- std::vectorBasicBlock*
LoopBlocks);
+const std::vectorBasicBlock*
LoopBlocks);
+Instruction *getValueDominatingBlock(BasicBlock *BB,
+ std::mapBasicBlock*, Instruction*
PotDoms);
};
RegisterOptLCSSA X(lcssa, Loop-Closed SSA Form Pass);
@@ -103,113 +109,120 @@
std::setInstruction* AffectedValues = getLoopValuesUsedOutsideLoop(L,
LoopBlocks);
+ // If no values are affected, we can save a lot of work, since we know that
+ // nothing will be changed.
+ if (AffectedValues.empty())
+return false;
+
std::vectorBasicBlock* exitBlocks;
L-getExitBlocks(exitBlocks);
- // Phi nodes that need to be IDF-processed
- std::vectorPHINode* workList;
// Iterate over all affected values for this loop and insert Phi nodes
// for them in the appropriate exit blocks
- std::mapBasicBlock*, PHINode* ExitPhis;
+
for (std::setInstruction*::iterator I = AffectedValues.begin(),
E = AffectedValues.end(); I != E; ++I) {
-++NumLCSSA; // We are applying the transformation
-for (std::vectorBasicBlock*::iterator BBI = exitBlocks.begin(),
- BBE = exitBlocks.end(); BBI != BBE; ++BBI) {
- PHINode *phi = new PHINode((*I)-getType(), lcssa);
- (*BBI)-getInstList().insert((*BBI)-front(), phi);
- workList.push_back(phi);
- ExitPhis[*BBI] = phi;
-
- // Since LoopSimplify has been run, we know that all of these
predecessors
- // are in the loop, so just hook them up in the obvious manner.
- for (pred_iterator PI = pred_begin(*BBI), PE = pred_end(*BBI); PI != PE;
- ++PI)
-phi-addIncoming(*I, *PI);
-}
+processInstruction(*I, LoopBlocks, exitBlocks);
+ }
+
+ return true; // FIXME: Should be more intelligent in our return value.
+}
+
+/// processInstruction -
+void LCSSA::processInstruction(Instruction* Instr,
+ const std::vectorBasicBlock* LoopBlocks,
+ const std::vectorBasicBlock* exitBlocks)
+{
+ ++NumLCSSA; // We are applying the transformation
-// Calculate the IDF of these LCSSA Phi nodes, inserting new Phi's where
-// necessary. Keep track of these new Phi's in DFPhis.
-std::mapBasicBlock*, PHINode* DFPhis;
-for (std::vectorPHINode*::iterator DFI = workList.begin(),
- E = workList.end(); DFI != E; ++DFI) {
-
- // Get the current Phi's DF, and insert Phi nodes. Add these new
- // nodes to our worklist.
- DominanceFrontier::const_iterator it = DF-find((*DFI)-getParent());
- if (it != DF-end()) {
-const DominanceFrontier::DomSetType S = it-second;
-for (DominanceFrontier::DomSetType::const_iterator P = S.begin(),
- PE = S.end(); P != PE; ++P) {
- if (DFPhis[*P] == 0) {
-// Still doesn't have operands...
-PHINode *phi = new PHINode((*DFI)-getType(), lcssa);
-(*P)-getInstList().insert((*P)-front(), phi);
-DFPhis[*P] = phi;
+ std::mapBasicBlock*, Instruction* Phis;
+ Phis[Instr-getParent()] = Instr;
+
+ // Phi nodes that need to be IDF-processed
+ std::vectorPHINode* workList;
+
+ for (std::vectorBasicBlock*::const_iterator BBI = exitBlocks.begin(),
+ BBE = exitBlocks.end(); BBI != BBE; ++BBI) {
+PHINode *phi = new PHINode(Instr-getType(), lcssa, (*BBI)-begin());
+workList.push_back(phi);
+Phis[*BBI] = phi;
+
+// Since LoopSimplify has been run, we know that all of these predecessors
+//
[llvm-commits] CVS: llvm/lib/Transforms/Scalar/LCSSA.cpp
Changes in directory llvm/lib/Transforms/Scalar:
LCSSA.cpp updated: 1.5 - 1.6
---
Log message:
Major think-o. Iterate over all live out-of-loop values, and perform the
other calculations on each individually, rather than trying to delay it and do
them all at the end.
---
Diffs of the changes: (+37 -37)
LCSSA.cpp | 74 +++---
1 files changed, 37 insertions(+), 37 deletions(-)
Index: llvm/lib/Transforms/Scalar/LCSSA.cpp
diff -u llvm/lib/Transforms/Scalar/LCSSA.cpp:1.5
llvm/lib/Transforms/Scalar/LCSSA.cpp:1.6
--- llvm/lib/Transforms/Scalar/LCSSA.cpp:1.5Sat May 27 13:47:11 2006
+++ llvm/lib/Transforms/Scalar/LCSSA.cppSun May 28 14:33:28 2006
@@ -42,7 +42,8 @@
using namespace llvm;
namespace {
- static Statistic NumLCSSA(lcssa, Number of live out of a loop);
+ static Statistic NumLCSSA(lcssa,
+ Number of live out of a loop variables);
class LCSSA : public FunctionPass {
public:
@@ -125,50 +126,49 @@
++PI)
phi-addIncoming(*I, *PI);
}
- }
- // Calculate the IDF of these LCSSA Phi nodes, inserting new Phi's where
- // necessary. Keep track of these new Phi's in DFPhis.
- std::mapBasicBlock*, PHINode* DFPhis;
- for (std::vectorPHINode*::iterator I = workList.begin(),
- E = workList.end(); I != E; ++I) {
-
-// Get the current Phi's DF, and insert Phi nodes. Add these new
-// nodes to our worklist.
-DominanceFrontier::const_iterator it = DF-find((*I)-getParent());
-if (it != DF-end()) {
- const DominanceFrontier::DomSetType S = it-second;
- for (DominanceFrontier::DomSetType::const_iterator P = S.begin(),
+// Calculate the IDF of these LCSSA Phi nodes, inserting new Phi's where
+// necessary. Keep track of these new Phi's in DFPhis.
+std::mapBasicBlock*, PHINode* DFPhis;
+for (std::vectorPHINode*::iterator DFI = workList.begin(),
+ E = workList.end(); DFI != E; ++DFI) {
+
+ // Get the current Phi's DF, and insert Phi nodes. Add these new
+ // nodes to our worklist.
+ DominanceFrontier::const_iterator it = DF-find((*DFI)-getParent());
+ if (it != DF-end()) {
+const DominanceFrontier::DomSetType S = it-second;
+for (DominanceFrontier::DomSetType::const_iterator P = S.begin(),
PE = S.end(); P != PE; ++P) {
-if (DFPhis[*P] == 0) {
- // Still doesn't have operands...
- PHINode *phi = new PHINode((*I)-getType(), lcssa);
- (*P)-getInstList().insert((*P)-front(), phi);
- DFPhis[*P] = phi;
+ if (DFPhis[*P] == 0) {
+// Still doesn't have operands...
+PHINode *phi = new PHINode((*DFI)-getType(), lcssa);
+(*P)-getInstList().insert((*P)-front(), phi);
+DFPhis[*P] = phi;
- workList.push_back(phi);
+workList.push_back(phi);
+ }
}
}
-}
-// Get the predecessor blocks of the current Phi, and use them to hook up
-// the operands of the current Phi to any members of DFPhis that dominate
-// it. This is a nop for the Phis inserted directly in the exit blocks,
-// since they are not dominated by any members of DFPhis.
-for (pred_iterator PI = pred_begin((*I)-getParent()),
- E = pred_end((*I)-getParent()); PI != E; ++PI)
- for (std::mapBasicBlock*, PHINode*::iterator MI = DFPhis.begin(),
- ME = DFPhis.end(); MI != ME; ++MI)
-if (DT-getNode((*MI).first)-dominates(DT-getNode(*PI))) {
- (*I)-addIncoming((*MI).second, *PI);
+ // Get the predecessor blocks of the current Phi, and use them to hook up
+ // the operands of the current Phi to any members of DFPhis that dominate
+ // it. This is a nop for the Phis inserted directly in the exit blocks,
+ // since they are not dominated by any members of DFPhis.
+ for (pred_iterator PI = pred_begin((*DFI)-getParent()),
+ E = pred_end((*DFI)-getParent()); PI != E; ++PI)
+for (std::mapBasicBlock*, PHINode*::iterator MI = DFPhis.begin(),
+ ME = DFPhis.end(); MI != ME; ++MI)
+ if (DT-getNode((*MI).first)-dominates(DT-getNode(*PI))) {
+(*DFI)-addIncoming((*MI).second, *PI);
- // Since dominate() is not cheap, don't do it more than we have to.
- break;
-}
- }
-
- // FIXME: Should update all uses.
+// Since dominate() is not cheap, don't do it more than we have to.
+break;
+ }
+}
+// FIXME: Should update all uses.
+ }
return true; // FIXME: Should be more intelligent in our return value.
}
___
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/LCSSA.cpp
Changes in directory llvm/lib/Transforms/Scalar:
LCSSA.cpp updated: 1.6 - 1.7
---
Log message:
Add Use replacement. Assuming there is nothing horribly wrong with this, LCSSA
is now theoretically feature-complete. It has not, however, been thoroughly
test, and is still considered experimental.
---
Diffs of the changes: (+35 -2)
LCSSA.cpp | 37 +++--
1 files changed, 35 insertions(+), 2 deletions(-)
Index: llvm/lib/Transforms/Scalar/LCSSA.cpp
diff -u llvm/lib/Transforms/Scalar/LCSSA.cpp:1.6
llvm/lib/Transforms/Scalar/LCSSA.cpp:1.7
--- llvm/lib/Transforms/Scalar/LCSSA.cpp:1.6Sun May 28 14:33:28 2006
+++ llvm/lib/Transforms/Scalar/LCSSA.cppSun May 28 20:00:00 2006
@@ -111,6 +111,7 @@
// Iterate over all affected values for this loop and insert Phi nodes
// for them in the appropriate exit blocks
+ std::mapBasicBlock*, PHINode* ExitPhis;
for (std::setInstruction*::iterator I = AffectedValues.begin(),
E = AffectedValues.end(); I != E; ++I) {
++NumLCSSA; // We are applying the transformation
@@ -119,6 +120,7 @@
PHINode *phi = new PHINode((*I)-getType(), lcssa);
(*BBI)-getInstList().insert((*BBI)-front(), phi);
workList.push_back(phi);
+ ExitPhis[*BBI] = phi;
// Since LoopSimplify has been run, we know that all of these
predecessors
// are in the loop, so just hook them up in the obvious manner.
@@ -166,9 +168,40 @@
break;
}
}
-
-// FIXME: Should update all uses.
+
+
+
+// Find all uses of the affected value, and replace them with the
+// appropriate Phi.
+for (Instruction::use_iterator UI = (*I)-use_begin(), UE=(*I)-use_end();
+ UI != UE; ++UI) {
+ Instruction* use = castInstruction(*UI);
+
+ // Don't need to update uses within the loop body
+ if (!std::binary_search(LoopBlocks.begin(), LoopBlocks.end(),
+ use-getParent())) {
+
+for (std::mapBasicBlock*, PHINode*::iterator DI = ExitPhis.begin(),
+ DE = ExitPhis.end(); DI != DE; ++DI) {
+ if (DT-getNode((*DI).first)-dominates( \
+ DT-getNode(use-getParent())) use != (*DI).second) {
+use-replaceUsesOfWith(*I, (*DI).second);
+break;
+ }
+}
+
+for (std::mapBasicBlock*, PHINode*::iterator DI = DFPhis.begin(),
+ DE = DFPhis.end(); DI != DE; ++DI) {
+ if (DT-getNode((*DI).first)-dominates( \
+ DT-getNode(use-getParent( {
+use-replaceUsesOfWith(*I, (*DI).second);
+break;
+ }
+}
+ }
+}
}
+
return true; // FIXME: Should be more intelligent in our return value.
}
___
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/LCSSA.cpp
Changes in directory llvm/lib/Transforms/Scalar:
LCSSA.cpp updated: 1.4 - 1.5
---
Log message:
Make LCSSA insert proper Phi nodes throughout the rest of the CFG by computing
the iterated Dominance Frontier of the loop-closure Phi's. This is the
second phase of the LCSSA pass. The third phase (coming soon) will be to
update all uses of loop variables to use the loop-closure Phi's instead.
---
Diffs of the changes: (+51 -8)
LCSSA.cpp | 59 +++
1 files changed, 51 insertions(+), 8 deletions(-)
Index: llvm/lib/Transforms/Scalar/LCSSA.cpp
diff -u llvm/lib/Transforms/Scalar/LCSSA.cpp:1.4
llvm/lib/Transforms/Scalar/LCSSA.cpp:1.5
--- llvm/lib/Transforms/Scalar/LCSSA.cpp:1.4Fri May 26 19:31:37 2006
+++ llvm/lib/Transforms/Scalar/LCSSA.cppSat May 27 13:47:11 2006
@@ -36,12 +36,13 @@
#include llvm/Analysis/LoopInfo.h
#include llvm/Support/CFG.h
#include algorithm
+#include map
#include vector
using namespace llvm;
namespace {
- static Statistic NumLCSSA(lcssa, Number of times LCSSA was applied);
+ static Statistic NumLCSSA(lcssa, Number of live out of a loop);
class LCSSA : public FunctionPass {
public:
@@ -64,8 +65,7 @@
AU.addPreservedID(LoopSimplifyID);
AU.addRequiredLoopInfo();
AU.addPreservedLoopInfo();
- AU.addRequiredDominatorTree(); // Not sure if this one will actually
- // be needed.
+ AU.addRequiredDominatorTree();
AU.addRequiredDominanceFrontier();
}
private:
@@ -105,6 +105,11 @@
std::vectorBasicBlock* exitBlocks;
L-getExitBlocks(exitBlocks);
+ // Phi nodes that need to be IDF-processed
+ std::vectorPHINode* workList;
+
+ // Iterate over all affected values for this loop and insert Phi nodes
+ // for them in the appropriate exit blocks
for (std::setInstruction*::iterator I = AffectedValues.begin(),
E = AffectedValues.end(); I != E; ++I) {
++NumLCSSA; // We are applying the transformation
@@ -112,20 +117,58 @@
BBE = exitBlocks.end(); BBI != BBE; ++BBI) {
PHINode *phi = new PHINode((*I)-getType(), lcssa);
(*BBI)-getInstList().insert((*BBI)-front(), phi);
+ workList.push_back(phi);
+ // Since LoopSimplify has been run, we know that all of these
predecessors
+ // are in the loop, so just hook them up in the obvious manner.
for (pred_iterator PI = pred_begin(*BBI), PE = pred_end(*BBI); PI != PE;
++PI)
phi-addIncoming(*I, *PI);
}
+ }
-for (Value::use_iterator UI = (*I)-use_begin(), UE = (*I)-use_end();
- UI != UE; ++UI) {
- BasicBlock *UserBB = castInstruction(*UI)-getParent();
- if (!std::binary_search(LoopBlocks.begin(), LoopBlocks.end(), UserBB))
-; // FIXME: This should update the SSA form.
+ // Calculate the IDF of these LCSSA Phi nodes, inserting new Phi's where
+ // necessary. Keep track of these new Phi's in DFPhis.
+ std::mapBasicBlock*, PHINode* DFPhis;
+ for (std::vectorPHINode*::iterator I = workList.begin(),
+ E = workList.end(); I != E; ++I) {
+
+// Get the current Phi's DF, and insert Phi nodes. Add these new
+// nodes to our worklist.
+DominanceFrontier::const_iterator it = DF-find((*I)-getParent());
+if (it != DF-end()) {
+ const DominanceFrontier::DomSetType S = it-second;
+ for (DominanceFrontier::DomSetType::const_iterator P = S.begin(),
+ PE = S.end(); P != PE; ++P) {
+if (DFPhis[*P] == 0) {
+ // Still doesn't have operands...
+ PHINode *phi = new PHINode((*I)-getType(), lcssa);
+ (*P)-getInstList().insert((*P)-front(), phi);
+ DFPhis[*P] = phi;
+
+ workList.push_back(phi);
+}
+ }
}
+
+// Get the predecessor blocks of the current Phi, and use them to hook up
+// the operands of the current Phi to any members of DFPhis that dominate
+// it. This is a nop for the Phis inserted directly in the exit blocks,
+// since they are not dominated by any members of DFPhis.
+for (pred_iterator PI = pred_begin((*I)-getParent()),
+ E = pred_end((*I)-getParent()); PI != E; ++PI)
+ for (std::mapBasicBlock*, PHINode*::iterator MI = DFPhis.begin(),
+ ME = DFPhis.end(); MI != ME; ++MI)
+if (DT-getNode((*MI).first)-dominates(DT-getNode(*PI))) {
+ (*I)-addIncoming((*MI).second, *PI);
+
+ // Since dominate() is not cheap, don't do it more than we have to.
+ break;
+}
}
+ // FIXME: Should update all uses.
+
return true; // FIXME: Should be more intelligent in our return value.
}
___
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/LCSSA.cpp
Changes in directory llvm/lib/Transforms/Scalar:
LCSSA.cpp added (r1.1)
---
Log message:
Skeletal LCSSA pass. This is currently non-functional. Expect functionality
and documentation updates soo.
---
Diffs of the changes: (+159 -0)
LCSSA.cpp | 159 ++
1 files changed, 159 insertions(+)
Index: llvm/lib/Transforms/Scalar/LCSSA.cpp
diff -c /dev/null llvm/lib/Transforms/Scalar/LCSSA.cpp:1.1
*** /dev/null Fri May 26 08:58:36 2006
--- llvm/lib/Transforms/Scalar/LCSSA.cppFri May 26 08:58:26 2006
***
*** 0
--- 1,159
+ //===-- LCSSA.cpp - Convert loops into loop-closed SSA form
--===//
+ //
+ // The LLVM Compiler Infrastructure
+ //
+ // This file was developed by Owen Anderson and is distributed under the
+ // University of Illinois Open Source License. See LICENSE.TXT for details.
+ //
+
//===--===//
+ //
+ // This pass transforms loops by placing phi nodes at the end of the loops for
+ // all values that are live across the loop boundary. For example, it turns
+ // the left into the right code:
+ //
+ // for (...)for (...)
+ // if (c) if(c)
+ // X1 = ... X1 = ...
+ // else else
+ // X2 = ... X2 = ...
+ // X3 = phi(X1, X2) X3 = phi(X1, X2)
+ // ... = X3 + 4 X4 = phi(X3)
+ // ... = X4 + 4
+ //
+ // This is still valid LLVM; the extra phi nodes are purely redundant, and
will
+ // be trivially eliminated by InstCombine. The major benefit of this
+ // transformation is that it makes many other loop optimizations, such as
+ // LoopUnswitching, simpler.
+ //
+
//===--===//
+
+ #include llvm/Pass.h
+ #include llvm/Function.h
+ #include llvm/Instructions.h
+ #include llvm/Analysis/LoopInfo.h
+ #include llvm/Support/CFG.h
+ #include llvm/Transforms/Scalar.h
+ #include llvm/Transforms/Utils/BasicBlockUtils.h
+ #include iostream
+ #include set
+ #include vector
+
+ using namespace llvm;
+
+ namespace {
+ class LCSSA : public FunctionPass {
+ public:
+ LoopInfo *LI; // Loop information
+
+ // LoopProcessWorklist - List of loops we need to process.
+ std::vectorLoop* LoopProcessWorklist;
+
+ virtual bool runOnFunction(Function F);
+
+ bool visitLoop(Loop *L, Value *V);
+
+ /// This transformation requires natural loop information requires that
+ /// loop preheaders be inserted into the CFG...
+ ///
+ virtual void getAnalysisUsage(AnalysisUsage AU) const {
+ AU.addRequiredID(LoopSimplifyID);
+ AU.addPreservedID(LoopSimplifyID);
+ AU.addRequiredLoopInfo();
+ AU.addPreservedLoopInfo();
+ }
+ private:
+ void addSubloopsToWorklist(Loop* L);
+ std::setValue* loopValuesUsedOutsideLoop(Loop *L);
+ };
+
+ RegisterOptLCSSA X(lcssa, Loop-Closed SSA Form Pass);
+ }
+
+ FunctionPass *llvm::createLCSSAPass() { return new LCSSA(); }
+
+ bool LCSSA::runOnFunction(Function F) {
+ bool changed = false;
+ LI = getAnalysisLoopInfo();
+
+ for (LoopInfo::iterator I = LI-begin(), E = LI-end(); I != E; ++I) {
+ addSubloopsToWorklist(*I);
+ LoopProcessWorklist.push_back(*I);
+ }
+
+ for (std::vectorLoop*::iterator I = LoopProcessWorklist.begin(),
+E = LoopProcessWorklist.end(); I != E; ++I) {
+ std::setValue* AffectedValues = loopValuesUsedOutsideLoop(*I);
+ if (!AffectedValues.empty()) {
+ for (std::setValue*::iterator VI = AffectedValues.begin(),
+VE = AffectedValues.end(); VI != VE; ++VI)
+ changed |= visitLoop(*I, *VI);
+ }
+ }
+
+ return changed;
+ }
+
+ bool LCSSA::visitLoop(Loop *L, Value* V) {
+ // We will be doing lots of loop contains block queries. Loop::contains
is
+ // linear time, use a set to speed this up.
+ std::setBasicBlock* LoopBlocks;
+
+ for (Loop::block_iterator BB = L-block_begin(), E = L-block_end();
+BB != E; ++BB)
+ LoopBlocks.insert(*BB);
+
+ std::vectorBasicBlock* exitBlocks;
+ L-getExitBlocks(exitBlocks);
+
+ for (std::vectorBasicBlock*::iterator BBI = exitBlocks.begin(),
+BBE = exitBlocks.end(); BBI != BBE; ++BBI) {
+ PHINode *phi = new PHINode(V-getType(), lcssa);
+ (*BBI)-getInstList().insert((*BBI)-front(), phi);
+
+ for (pred_iterator PI = pred_begin(*BBI), PE = pred_end(*BBI); PI != PE;
+ ++PI)
+ phi-addIncoming(V, *PI);
+ }
+
+ for (Value::use_iterator UI = V-use_begin(), UE = V-use_end(); UI != UE;
+++UI) {
+ BasicBlock *UserBB = castInstruction(*UI)-getParent();
+ if (!LoopBlocks.count(UserBB))
+ ; // FIXME: This should update the SSA form through the rest of the
graph.
+ }
+
+
[llvm-commits] CVS: llvm/lib/Transforms/Scalar/LCSSA.cpp
Changes in directory llvm/lib/Transforms/Scalar: LCSSA.cpp updated: 1.2 - 1.3 --- Log message: Fix a copy-and-paste-o that would break some compilers. --- Diffs of the changes: (+1 -1) LCSSA.cpp |2 +- 1 files changed, 1 insertion(+), 1 deletion(-) Index: llvm/lib/Transforms/Scalar/LCSSA.cpp diff -u llvm/lib/Transforms/Scalar/LCSSA.cpp:1.2 llvm/lib/Transforms/Scalar/LCSSA.cpp:1.3 --- llvm/lib/Transforms/Scalar/LCSSA.cpp:1.2Fri May 26 16:11:53 2006 +++ llvm/lib/Transforms/Scalar/LCSSA.cppFri May 26 16:19:17 2006 @@ -48,7 +48,7 @@ DominanceFrontier *DF; // Current Dominance Frontier virtual bool runOnFunction(Function F); -bool LCSSA::visitSubloop(Loop* L); +bool visitSubloop(Loop* L); /// This transformation requires natural loop information requires that /// loop preheaders be inserted into the CFG... ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
