[llvm-commits] CVS: llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp
Changes in directory llvm/lib/Transforms/Utils:
PromoteMemoryToRegister.cpp updated: 1.97 - 1.98
---
Log message:
Fix a comment.
---
Diffs of the changes: (+1 -1)
PromoteMemoryToRegister.cpp |2 +-
1 files changed, 1 insertion(+), 1 deletion(-)
Index: llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp
diff -u llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp:1.97
llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp:1.98
--- llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp:1.97 Fri Apr 20
01:27:13 2007
+++ llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp Sat Apr 21
02:12:44 2007
@@ -142,7 +142,7 @@
return ET.properlyDominates(I1-getParent(), I2-getParent());
}
-/// dominates - Return true if BB1 dominates BB2 using the DominatorTree.
+/// dominates - Return true if BB1 dominates BB2 using the ETForest.
///
bool dominates(BasicBlock *BB1, BasicBlock *BB2) const {
return ET.dominates(BB1, BB2);
___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp
Changes in directory llvm/lib/Transforms/Utils:
PromoteMemoryToRegister.cpp updated: 1.95 - 1.96
---
Log message:
Reduce malloc/free traffic.
---
Diffs of the changes: (+8 -12)
PromoteMemoryToRegister.cpp | 20
1 files changed, 8 insertions(+), 12 deletions(-)
Index: llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp
diff -u llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp:1.95
llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp:1.96
--- llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp:1.95 Fri Mar 9
17:41:03 2007
+++ llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp Mon Mar 26
18:19:29 2007
@@ -77,7 +77,7 @@
class VISIBILITY_HIDDEN RenamePassData {
public:
RenamePassData(BasicBlock *B, BasicBlock *P,
- std::vectorValue * V) : BB(B), Pred(P), Values(V) {}
+ const std::vectorValue * V) : BB(B), Pred(P), Values(V)
{}
BasicBlock *BB;
BasicBlock *Pred;
std::vectorValue * Values;
@@ -123,7 +123,7 @@
DenseMapBasicBlock*, unsigned BBNumbers;
/// RenamePassWorkList - Worklist used by RenamePass()
-std::vectorRenamePassData * RenamePassWorkList;
+std::vectorRenamePassData RenamePassWorkList;
public:
PromoteMem2Reg(const std::vectorAllocaInst* A,
@@ -407,13 +407,12 @@
// and inserting the phi nodes we marked as necessary
//
RenamePassWorkList.clear();
- RenamePassData *RPD = new RenamePassData(F.begin(), 0, Values);
- RenamePassWorkList.push_back(RPD);
+ RenamePassWorkList.push_back(RenamePassData(F.begin(), 0, Values));
while(!RenamePassWorkList.empty()) {
-RenamePassData *RPD = RenamePassWorkList.back();
RenamePassWorkList.pop_back();
+RenamePassData RPD = RenamePassWorkList.back();
+RenamePassWorkList.pop_back();
// RenamePass may add new worklist entries.
-RenamePass(RPD-BB, RPD-Pred, RPD-Values);
-delete RPD;
+RenamePass(RPD.BB, RPD.Pred, RPD.Values);
}
// The renamer uses the Visited set to avoid infinite loops. Clear it now.
@@ -794,11 +793,8 @@
// Recurse to our successors.
TerminatorInst *TI = BB-getTerminator();
- for (unsigned i = 0; i != TI-getNumSuccessors(); i++) {
-RenamePassData *RPD = new RenamePassData(TI-getSuccessor(i), BB,
- IncomingVals);
-RenamePassWorkList.push_back(RPD);
- }
+ for (unsigned i = 0; i != TI-getNumSuccessors(); i++)
+RenamePassWorkList.push_back(RenamePassData(TI-getSuccessor(i), BB,
IncomingVals));
}
/// PromoteMemToReg - Promote the specified list of alloca instructions into
___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp
Changes in directory llvm/lib/Transforms/Utils:
PromoteMemoryToRegister.cpp updated: 1.93 - 1.94
---
Log message:
Avoid recursion. Use iterative algorithm for RenamePass().
---
Diffs of the changes: (+31 -4)
PromoteMemoryToRegister.cpp | 35 +++
1 files changed, 31 insertions(+), 4 deletions(-)
Index: llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp
diff -u llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp:1.93
llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp:1.94
--- llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp:1.93 Tue Feb 6
19:15:04 2007
+++ llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp Fri Mar 9
17:39:14 2007
@@ -72,6 +72,17 @@
}
namespace {
+
+ // Data package used by RenamePass()
+ class VISIBILITY_HIDDEN RenamePassData {
+ public:
+RenamePassData(BasicBlock *B, BasicBlock *P,
+ std::vectorValue * V) : BB(B), Pred(P), Values(V) {}
+BasicBlock *BB;
+BasicBlock *Pred;
+std::vectorValue * Values;
+ };
+
struct VISIBILITY_HIDDEN PromoteMem2Reg {
/// Allocas - The alloca instructions being promoted.
///
@@ -111,6 +122,9 @@
/// non-determinstic behavior.
DenseMapBasicBlock*, unsigned BBNumbers;
+/// RenamePassWorkList - Worklist used by RenamePass()
+std::vectorRenamePassData * RenamePassWorkList;
+
public:
PromoteMem2Reg(const std::vectorAllocaInst* A,
SmallVectorAllocaInst*, 16 Retry, DominatorTree dt,
@@ -146,6 +160,7 @@
bool QueuePhiNode(BasicBlock *BB, unsigned AllocaIdx, unsigned Version,
SmallPtrSetPHINode*, 16 InsertedPHINodes);
};
+
} // end of anonymous namespace
void PromoteMem2Reg::run() {
@@ -391,8 +406,17 @@
// Walks all basic blocks in the function performing the SSA rename algorithm
// and inserting the phi nodes we marked as necessary
//
- RenamePass(F.begin(), 0, Values);
-
+ //RenamePass(F.begin(), 0, Values);
+ RenamePassWorkList.clear();
+ RenamePassData *RPD = new RenamePassData(F.begin(), 0, Values);
+ RenamePassWorkList.push_back(RPD);
+ while(!RenamePassWorkList.empty()) {
+RenamePassData *RPD = RenamePassWorkList.back();
RenamePassWorkList.pop_back();
+// RenamePass may add new worklist entries.
+RenamePass(RPD-BB, RPD-Pred, RPD-Values);
+delete RPD;
+ }
+
// The renamer uses the Visited set to avoid infinite loops. Clear it now.
Visited.clear();
@@ -772,8 +796,11 @@
// Recurse to our successors.
TerminatorInst *TI = BB-getTerminator();
for (unsigned i = 0; i != TI-getNumSuccessors(); i++) {
-std::vectorValue* OutgoingVals(IncomingVals);
-RenamePass(TI-getSuccessor(i), BB, OutgoingVals);
+RenamePassData *RPD = new RenamePassData(TI-getSuccessor(i), BB,
+ IncomingVals);
+RenamePassWorkList.push_back(RPD);
+//std::vectorValue* OutgoingVals(IncomingVals);
+//RenamePass(TI-getSuccessor(i), BB, OutgoingVals);
}
}
___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp
Changes in directory llvm/lib/Transforms/Utils: PromoteMemoryToRegister.cpp updated: 1.94 - 1.95 --- Log message: Remove dead comments. --- Diffs of the changes: (+0 -3) PromoteMemoryToRegister.cpp |3 --- 1 files changed, 3 deletions(-) Index: llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp diff -u llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp:1.94 llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp:1.95 --- llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp:1.94 Fri Mar 9 17:39:14 2007 +++ llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp Fri Mar 9 17:41:03 2007 @@ -406,7 +406,6 @@ // Walks all basic blocks in the function performing the SSA rename algorithm // and inserting the phi nodes we marked as necessary // - //RenamePass(F.begin(), 0, Values); RenamePassWorkList.clear(); RenamePassData *RPD = new RenamePassData(F.begin(), 0, Values); RenamePassWorkList.push_back(RPD); @@ -799,8 +798,6 @@ RenamePassData *RPD = new RenamePassData(TI-getSuccessor(i), BB, IncomingVals); RenamePassWorkList.push_back(RPD); -//std::vectorValue* OutgoingVals(IncomingVals); -//RenamePass(TI-getSuccessor(i), BB, OutgoingVals); } } ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp
Changes in directory llvm/lib/Transforms/Utils:
PromoteMemoryToRegister.cpp updated: 1.92 - 1.93
---
Log message:
redesign the primary datastructure used by mem2reg to eliminate an
std::map of std::vector's (ouch!). This speeds up mem2reg by 10% on 176.gcc.
---
Diffs of the changes: (+157 -104)
PromoteMemoryToRegister.cpp | 261 ++--
1 files changed, 157 insertions(+), 104 deletions(-)
Index: llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp
diff -u llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp:1.92
llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp:1.93
--- llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp:1.92 Mon Feb 5
17:37:20 2007
+++ llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp Tue Feb 6
19:15:04 2007
@@ -32,6 +32,23 @@
#include algorithm
using namespace llvm;
+// Provide DenseMapKeyInfo for all pointers.
+namespace llvm {
+template
+struct DenseMapKeyInfostd::pairBasicBlock*, unsigned {
+ static inline std::pairBasicBlock*, unsigned getEmptyKey() {
+return std::make_pair((BasicBlock*)-1, ~0U);
+ }
+ static inline std::pairBasicBlock*, unsigned getTombstoneKey() {
+return std::make_pair((BasicBlock*)-2, 0U);
+ }
+ static unsigned getHashValue(const std::pairBasicBlock*, unsigned Val) {
+return DenseMapKeyInfovoid*::getHashValue(Val.first) + Val.second*2;
+ }
+ static bool isPod() { return true; }
+};
+}
+
/// isAllocaPromotable - Return true if this alloca is legal for promotion.
/// This is true if there are only loads and stores to the alloca.
///
@@ -74,8 +91,12 @@
/// NewPhiNodes - The PhiNodes we're adding.
///
-std::mapBasicBlock*, std::vectorPHINode* NewPhiNodes;
-
+DenseMapstd::pairBasicBlock*, unsigned, PHINode* NewPhiNodes;
+
+/// PhiToAllocaMap - For each PHI node, keep track of which entry in
Allocas
+/// it corresponds to.
+DenseMapPHINode*, unsigned PhiToAllocaMap;
+
/// PointerAllocaValues - If we are updating an AliasSetTracker, then for
/// each alloca that is of pointer type, we keep track of what to copyValue
/// to the inserted PHI nodes here.
@@ -322,23 +343,14 @@
for (SmallPtrSetPHINode*, 16::iterator I = InsertedPHINodes.begin(),
E = InsertedPHINodes.end(); I != E; ++I) {
PHINode *PN = *I;
- std::vectorPHINode* BBPNs = NewPhiNodes[PN-getParent()];
- BBPNs[AllocaNum] = 0;
-
- // Check to see if we just removed the last inserted PHI node from this
- // basic block. If so, remove the entry for the basic block.
- bool HasOtherPHIs = false;
- for (unsigned i = 0, e = BBPNs.size(); i != e; ++i)
-if (BBPNs[i]) {
- HasOtherPHIs = true;
- break;
-}
- if (!HasOtherPHIs)
-NewPhiNodes.erase(PN-getParent());
-
+ bool Erased=NewPhiNodes.erase(std::make_pair(PN-getParent(),
AllocaNum));
+ Erased=Erased;
+ assert(Erased PHI already removed?);
+
if (AST isaPointerType(PN-getType()))
AST-deleteValue(PN);
PN-eraseFromParent();
+ PhiToAllocaMap.erase(PN);
}
// Keep the reverse mapping of the 'Allocas' array.
@@ -407,26 +419,24 @@
while (EliminatedAPHI) {
EliminatedAPHI = false;
-for (std::mapBasicBlock*, std::vectorPHINode * ::iterator I =
- NewPhiNodes.begin(), E = NewPhiNodes.end(); I != E; ++I) {
- std::vectorPHINode* PNs = I-second;
- for (unsigned i = 0, e = PNs.size(); i != e; ++i) {
-if (!PNs[i]) continue;
-
-// If this PHI node merges one value and/or undefs, get the value.
-if (Value *V = PNs[i]-hasConstantValue(true)) {
- if (!isaInstruction(V) ||
- properlyDominates(castInstruction(V), PNs[i])) {
-if (AST isaPointerType(PNs[i]-getType()))
- AST-deleteValue(PNs[i]);
-PNs[i]-replaceAllUsesWith(V);
-PNs[i]-eraseFromParent();
-PNs[i] = 0;
-EliminatedAPHI = true;
-continue;
- }
+for (DenseMapstd::pairBasicBlock*, unsigned, PHINode*::iterator I =
+ NewPhiNodes.begin(), E = NewPhiNodes.end(); I != E;) {
+ PHINode *PN = I-second;
+
+ // If this PHI node merges one value and/or undefs, get the value.
+ if (Value *V = PN-hasConstantValue(true)) {
+if (!isaInstruction(V) ||
+properlyDominates(castInstruction(V), PN)) {
+ if (AST isaPointerType(PN-getType()))
+AST-deleteValue(PN);
+ PN-replaceAllUsesWith(V);
+ PN-eraseFromParent();
+ NewPhiNodes.erase(I++);
+ EliminatedAPHI = true;
+ continue;
}
}
+ ++I;
}
}
@@ -436,52 +446,58 @@
// have incoming values for all predecessors. Loop over all PHI nodes we
have
// created, inserting undef values if they are missing any incoming values.
//
- for (std::mapBasicBlock*,
[llvm-commits] CVS: llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp
Changes in directory llvm/lib/Transforms/Utils:
PromoteMemoryToRegister.cpp updated: 1.89 - 1.90
---
Log message:
Switch InsertedPHINodes back to SmallPtrSet now that the SmallPtrSet::erase
bug is fixed.
---
Diffs of the changes: (+6 -6)
PromoteMemoryToRegister.cpp | 12 ++--
1 files changed, 6 insertions(+), 6 deletions(-)
Index: llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp
diff -u llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp:1.89
llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp:1.90
--- llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp:1.89 Mon Feb 5
16:28:52 2007
+++ llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp Mon Feb 5
17:11:37 2007
@@ -115,7 +115,7 @@
private:
void MarkDominatingPHILive(BasicBlock *BB, unsigned AllocaNum,
- std::setPHINode* DeadPHINodes);
+ SmallPtrSetPHINode*, 16 DeadPHINodes);
bool PromoteLocallyUsedAlloca(BasicBlock *BB, AllocaInst *AI);
void PromoteLocallyUsedAllocas(BasicBlock *BB,
const std::vectorAllocaInst* AIs);
@@ -123,7 +123,7 @@
void RenamePass(BasicBlock *BB, BasicBlock *Pred,
std::vectorValue* IncVals);
bool QueuePhiNode(BasicBlock *BB, unsigned AllocaIdx, unsigned Version,
- std::setPHINode* InsertedPHINodes);
+ SmallPtrSetPHINode*, 16 InsertedPHINodes);
};
} // end of anonymous namespace
@@ -271,7 +271,7 @@
// dominance frontier of EACH basic-block we have a write in.
//
unsigned CurrentVersion = 0;
-std::setPHINode* InsertedPHINodes;
+SmallPtrSetPHINode*, 16 InsertedPHINodes;
std::vectorunsigned DFBlocks;
while (!DefiningBlocks.empty()) {
BasicBlock *BB = DefiningBlocks.back();
@@ -315,7 +315,7 @@
UsingBlocks.clear();
// If there are any PHI nodes which are now known to be dead, remove them!
-for (std::setPHINode*::iterator I = InsertedPHINodes.begin(),
+for (SmallPtrSetPHINode*, 16::iterator I = InsertedPHINodes.begin(),
E = InsertedPHINodes.end(); I != E; ++I) {
PHINode *PN = *I;
std::vectorPHINode* BBPNs = NewPhiNodes[PN-getParent()];
@@ -489,7 +489,7 @@
// DeadPHINodes set are removed.
//
void PromoteMem2Reg::MarkDominatingPHILive(BasicBlock *BB, unsigned AllocaNum,
- std::setPHINode* DeadPHINodes) {
+ SmallPtrSetPHINode*, 16 DeadPHINodes)
{
// Scan the immediate dominators of this block looking for a block which has
a
// PHI node for Alloca num. If we find it, mark the PHI node as being alive!
for (DominatorTree::Node *N = DT[BB]; N; N = N-getIDom()) {
@@ -630,7 +630,7 @@
//
bool PromoteMem2Reg::QueuePhiNode(BasicBlock *BB, unsigned AllocaNo,
unsigned Version,
- std::setPHINode* InsertedPHINodes) {
+ SmallPtrSetPHINode*, 16 InsertedPHINodes)
{
// Look up the basic-block in question.
std::vectorPHINode* BBPNs = NewPhiNodes[BB];
if (BBPNs.empty()) BBPNs.resize(Allocas.size());
___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp
Changes in directory llvm/lib/Transforms/Utils:
PromoteMemoryToRegister.cpp updated: 1.91 - 1.92
---
Log message:
With the last change, we no longer need both directions of mapping from
BBNumbers. Instead of using a bi-directional mapping, just use a single
densemap. This speeds up mem2reg on 176.gcc by 8%, from 1.3489 to
1.2485s.
---
Diffs of the changes: (+8 -4)
PromoteMemoryToRegister.cpp | 12
1 files changed, 8 insertions(+), 4 deletions(-)
Index: llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp
diff -u llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp:1.91
llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp:1.92
--- llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp:1.91 Mon Feb 5
17:31:26 2007
+++ llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp Mon Feb 5
17:37:20 2007
@@ -23,11 +23,11 @@
#include llvm/Instructions.h
#include llvm/Analysis/Dominators.h
#include llvm/Analysis/AliasSetTracker.h
+#include llvm/ADT/DenseMap.h
#include llvm/ADT/SmallPtrSet.h
#include llvm/ADT/SmallVector.h
#include llvm/ADT/StringExtras.h
#include llvm/Support/CFG.h
-#include llvm/Support/StableBasicBlockNumbering.h
#include llvm/Support/Compiler.h
#include algorithm
using namespace llvm;
@@ -88,7 +88,7 @@
/// BBNumbers - Contains a stable numbering of basic blocks to avoid
/// non-determinstic behavior.
-StableBasicBlockNumbering BBNumbers;
+DenseMapBasicBlock*, unsigned BBNumbers;
public:
PromoteMem2Reg(const std::vectorAllocaInst* A,
@@ -265,7 +265,11 @@
// If we haven't computed a numbering for the BB's in the function, do so
// now.
-BBNumbers.compute(F);
+if (BBNumbers.empty()) {
+ unsigned ID = 0;
+ for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
+BBNumbers[I] = ID++;
+}
// Compute the locations where PhiNodes need to be inserted. Look at the
// dominance frontier of EACH basic-block we have a write in.
@@ -289,7 +293,7 @@
// processing blocks in order of the occurance in the function.
for (DominanceFrontier::DomSetType::const_iterator P = S.begin(),
PE = S.end(); P != PE; ++P)
- DFBlocks.push_back(std::make_pair(BBNumbers.getNumber(*P), *P));
+ DFBlocks.push_back(std::make_pair(BBNumbers[*P], *P));
// Sort by which the block ordering in the function.
std::sort(DFBlocks.begin(), DFBlocks.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/Utils/PromoteMemoryToRegister.cpp
Changes in directory llvm/lib/Transforms/Utils:
PromoteMemoryToRegister.cpp updated: 1.82 - 1.83
---
Log message:
Fix some nondeterminstic behavior in the mem2reg pass that (in addition to
nondeterminism being bad) could cause some trivial missed optimizations (dead
phi nodes being left around for later passes to clean up).
With this, llvm-gcc4 now bootstraps and correctly compares. I don't know
why I never tried to do it before... :)
---
Diffs of the changes: (+38 -20)
PromoteMemoryToRegister.cpp | 58
1 files changed, 38 insertions(+), 20 deletions(-)
Index: llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp
diff -u llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp:1.82
llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp:1.83
--- llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp:1.82 Fri Nov 18
01:31:42 2005
+++ llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp Wed Apr 26
20:14:43 2006
@@ -147,7 +147,7 @@
if (AI-use_empty()) {
// If there are no uses of the alloca, just delete it now.
if (AST) AST-deleteValue(AI);
- AI-getParent()-getInstList().erase(AI);
+ AI-eraseFromParent();
// Remove the alloca from the Allocas list, since it has been processed
Allocas[AllocaNum] = Allocas.back();
@@ -331,7 +331,7 @@
if (AST isaPointerType(PN-getType()))
AST-deleteValue(PN);
- PN-getParent()-getInstList().erase(PN);
+ PN-eraseFromParent();
}
// Keep the reverse mapping of the 'Allocas' array.
@@ -377,7 +377,7 @@
// The renamer uses the Visited set to avoid infinite loops. Clear it now.
Visited.clear();
- // Remove the allocas themselves from the function...
+ // Remove the allocas themselves from the function.
for (unsigned i = 0, e = Allocas.size(); i != e; ++i) {
Instruction *A = Allocas[i];
@@ -388,9 +388,41 @@
if (!A-use_empty())
A-replaceAllUsesWith(UndefValue::get(A-getType()));
if (AST) AST-deleteValue(A);
-A-getParent()-getInstList().erase(A);
+A-eraseFromParent();
}
+
+ // Loop over all of the PHI nodes and see if there are any that we can get
+ // rid of because they merge all of the same incoming values. This can
+ // happen due to undef values coming into the PHI nodes. This process is
+ // iterative, because eliminating one PHI node can cause others to be
removed.
+ bool EliminatedAPHI = true;
+ while (EliminatedAPHI) {
+EliminatedAPHI = false;
+
+for (std::mapBasicBlock*, std::vectorPHINode * ::iterator I =
+ NewPhiNodes.begin(), E = NewPhiNodes.end(); I != E; ++I) {
+ std::vectorPHINode* PNs = I-second;
+ for (unsigned i = 0, e = PNs.size(); i != e; ++i) {
+if (!PNs[i]) continue;
+
+// If this PHI node merges one value and/or undefs, get the value.
+if (Value *V = PNs[i]-hasConstantValue(true)) {
+ if (!isaInstruction(V) ||
+ properlyDominates(castInstruction(V), PNs[i])) {
+if (AST isaPointerType(PNs[i]-getType()))
+ AST-deleteValue(PNs[i]);
+PNs[i]-replaceAllUsesWith(V);
+PNs[i]-eraseFromParent();
+PNs[i] = 0;
+EliminatedAPHI = true;
+continue;
+ }
+}
+ }
+}
+ }
+
// At this point, the renamer has added entries to PHI nodes for all
reachable
// code. Unfortunately, there may be blocks which are not reachable, which
// the renamer hasn't traversed. If this is the case, the PHI nodes may not
@@ -403,25 +435,11 @@
std::vectorBasicBlock* Preds(pred_begin(I-first), pred_end(I-first));
std::vectorPHINode* PNs = I-second;
assert(!PNs.empty() Empty PHI node list??);
-
-// Loop over all of the PHI nodes and see if there are any that we can get
-// rid of because they merge all of the same incoming values. This can
-// happen due to undef values coming into the PHI nodes.
PHINode *SomePHI = 0;
for (unsigned i = 0, e = PNs.size(); i != e; ++i)
if (PNs[i]) {
-if (Value *V = PNs[i]-hasConstantValue(true)) {
- if (!isaInstruction(V) ||
- properlyDominates(castInstruction(V), PNs[i])) {
-if (AST isaPointerType(PNs[i]-getType()))
- AST-deleteValue(PNs[i]);
-PNs[i]-replaceAllUsesWith(V);
-PNs[i]-eraseFromParent();
-PNs[i] = 0;
- }
-}
-if (PNs[i])
- SomePHI = PNs[i];
+SomePHI = PNs[i];
+break;
}
// Only do work here if there the PHI nodes are missing incoming values.
We
___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp
Changes in directory llvm/lib/Transforms/Utils:
PromoteMemoryToRegister.cpp updated: 1.80 - 1.81
---
Log message:
This needs proper dominance
---
Diffs of the changes: (+14 -5)
PromoteMemoryToRegister.cpp | 19 ++-
1 files changed, 14 insertions(+), 5 deletions(-)
Index: llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp
diff -u llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp:1.80
llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp:1.81
--- llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp:1.80 Thu Aug 4
19:57:45 2005
+++ llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp Fri Nov 18
01:29:44 2005
@@ -96,12 +96,18 @@
void run();
-/// dominates - Return true if I1 dominates I2 using the DominatorTree.
+/// properlyDominates - Return true if I1 properly dominates I2.
///
-bool dominates(Instruction *I1, Instruction *I2) const {
+bool properlyDominates(Instruction *I1, Instruction *I2) const {
if (InvokeInst *II = dyn_castInvokeInst(I1))
I1 = II-getNormalDest()-begin();
- return DT[I1-getParent()]-dominates(DT[I2-getParent()]);
+ return DT[I1-getParent()]-properlyDominates(DT[I2-getParent()]);
+}
+
+/// dominates - Return true if BB1 dominates BB2 using the DominatorTree.
+///
+bool dominates(BasicBlock *BB1, BasicBlock *BB2) const {
+ return DT[BB1]-dominates(DT[BB2]);
}
private:
@@ -168,7 +174,8 @@
// Remember the basic blocks which define new values for the alloca
DefiningBlocks.push_back(SI-getParent());
AllocaPointerVal = SI-getOperand(0);
- } else if (LoadInst *LI = dyn_castLoadInst(User)) {
+ } else {
+LoadInst *LI = castLoadInst(User);
// Otherwise it must be a load instruction, keep track of variable
reads
UsingBlocks.push_back(LI-getParent());
AllocaPointerVal = LI;
@@ -194,6 +201,7 @@
continue;
}
+
if (AST)
PointerAllocaValues[AllocaNum] = AllocaPointerVal;
@@ -348,7 +356,8 @@
for (unsigned i = 0, e = PNs.size(); i != e; ++i)
if (PNs[i]) {
if (Value *V = PNs[i]-hasConstantValue(true)) {
- if (!isaInstruction(V) || dominates(castInstruction(V), PNs[i]))
{
+ if (!isaInstruction(V) ||
+ properlyDominates(castInstruction(V), PNs[i])) {
if (AST isaPointerType(PNs[i]-getType()))
AST-deleteValue(PNs[i]);
PNs[i]-replaceAllUsesWith(V);
___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp
Changes in directory llvm/lib/Transforms/Utils:
PromoteMemoryToRegister.cpp updated: 1.81 - 1.82
---
Log message:
Implement a refinement to the mem2reg algorithm for cases where an alloca
has a single def. In this case, look for uses that are dominated by the def
and attempt to rewrite them to directly use the stored value.
This speeds up mem2reg on these values and reduces the number of phi nodes
inserted. This should address PR665: http://llvm.cs.uiuc.edu/PR665 .
---
Diffs of the changes: (+55 -0)
PromoteMemoryToRegister.cpp | 55
1 files changed, 55 insertions(+)
Index: llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp
diff -u llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp:1.81
llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp:1.82
--- llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp:1.81 Fri Nov 18
01:29:44 2005
+++ llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp Fri Nov 18
01:31:42 2005
@@ -161,6 +161,7 @@
std::vectorBasicBlock* DefiningBlocks;
std::vectorBasicBlock* UsingBlocks;
+StoreInst *OnlyStore = 0;
BasicBlock *OnlyBlock = 0;
bool OnlyUsedInOneBlock = true;
@@ -174,6 +175,7 @@
// Remember the basic blocks which define new values for the alloca
DefiningBlocks.push_back(SI-getParent());
AllocaPointerVal = SI-getOperand(0);
+OnlyStore = SI;
} else {
LoadInst *LI = castLoadInst(User);
// Otherwise it must be a load instruction, keep track of variable
reads
@@ -201,6 +203,59 @@
continue;
}
+// If there is only a single store to this value, replace any loads of
+// it that are directly dominated by the definition with the value stored.
+if (DefiningBlocks.size() == 1) {
+ // Be aware of loads before the store.
+ std::setBasicBlock* ProcessedBlocks;
+ for (unsigned i = 0, e = UsingBlocks.size(); i != e; ++i)
+// If the store dominates the block and if we haven't processed it yet,
+// do so now.
+if (dominates(OnlyStore-getParent(), UsingBlocks[i]))
+ if (ProcessedBlocks.insert(UsingBlocks[i]).second) {
+BasicBlock *UseBlock = UsingBlocks[i];
+
+// If the use and store are in the same block, do a quick scan to
+// verify that there are no uses before the store.
+if (UseBlock == OnlyStore-getParent()) {
+ BasicBlock::iterator I = UseBlock-begin();
+ for (; *I != OnlyStore; ++I) { // scan block for store.
+if (isaLoadInst(I) I-getOperand(0) == AI)
+ break;
+ }
+ if (*I != OnlyStore) break; // Do not handle this case.
+}
+
+// Otherwise, if this is a different block or if all uses happen
+// after the store, do a simple linear scan to replace loads with
+// the stored value.
+for (BasicBlock::iterator I = UseBlock-begin(),E =
UseBlock-end();
+ I != E; ) {
+ if (LoadInst *LI = dyn_castLoadInst(I++)) {
+if (LI-getOperand(0) == AI) {
+ LI-replaceAllUsesWith(OnlyStore-getOperand(0));
+ if (AST isaPointerType(LI-getType()))
+AST-deleteValue(LI);
+ LI-eraseFromParent();
+}
+ }
+}
+
+// Finally, remove this block from the UsingBlock set.
+UsingBlocks[i] = UsingBlocks.back();
+--i; --e;
+ }
+
+ // Finally, after the scan, check to see if the store is all that is
left.
+ if (UsingBlocks.empty()) {
+// The alloca has been processed, move on.
+Allocas[AllocaNum] = Allocas.back();
+Allocas.pop_back();
+--AllocaNum;
+continue;
+ }
+}
+
if (AST)
PointerAllocaValues[AllocaNum] = AllocaPointerVal;
___
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
