Changes in directory llvm/lib/Transforms/Utils:
CloneFunction.cpp updated: 1.40 -> 1.41
CloneModule.cpp updated: 1.21 -> 1.22
CloneTrace.cpp updated: 1.11 -> 1.12
InlineFunction.cpp updated: 1.51 -> 1.52
ValueMapper.cpp updated: 1.28 -> 1.29
ValueMapper.h updated: 1.6 -> 1.7
---
Log message:
Switch inliner over to use DenseMap instead of std::map for ValueMap. This
speeds up the inliner 16%.
---
Diffs of the changes: (+28 -25)
CloneFunction.cpp | 13 +++++++------
CloneModule.cpp | 6 +++---
CloneTrace.cpp | 4 ++--
InlineFunction.cpp | 6 +++---
ValueMapper.cpp | 20 +++++++++++---------
ValueMapper.h | 4 ++--
6 files changed, 28 insertions(+), 25 deletions(-)
Index: llvm/lib/Transforms/Utils/CloneFunction.cpp
diff -u llvm/lib/Transforms/Utils/CloneFunction.cpp:1.40
llvm/lib/Transforms/Utils/CloneFunction.cpp:1.41
--- llvm/lib/Transforms/Utils/CloneFunction.cpp:1.40 Thu Feb 1 12:48:38 2007
+++ llvm/lib/Transforms/Utils/CloneFunction.cpp Fri Feb 2 18:08:31 2007
@@ -22,11 +22,12 @@
#include "ValueMapper.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/ADT/SmallVector.h"
+#include <map>
using namespace llvm;
// CloneBasicBlock - See comments in Cloning.h
BasicBlock *llvm::CloneBasicBlock(const BasicBlock *BB,
- std::map<const Value*, Value*> &ValueMap,
+ DenseMap<const Value*, Value*> &ValueMap,
const char *NameSuffix, Function *F,
ClonedCodeInfo *CodeInfo) {
BasicBlock *NewBB = new BasicBlock("", F);
@@ -66,7 +67,7 @@
// ArgMap values.
//
void llvm::CloneFunctionInto(Function *NewFunc, const Function *OldFunc,
- std::map<const Value*, Value*> &ValueMap,
+ DenseMap<const Value*, Value*> &ValueMap,
std::vector<ReturnInst*> &Returns,
const char *NameSuffix, ClonedCodeInfo *CodeInfo)
{
assert(NameSuffix && "NameSuffix cannot be null!");
@@ -113,7 +114,7 @@
/// the function from their old to new values.
///
Function *llvm::CloneFunction(const Function *F,
- std::map<const Value*, Value*> &ValueMap,
+ DenseMap<const Value*, Value*> &ValueMap,
ClonedCodeInfo *CodeInfo) {
std::vector<const Type*> ArgTypes;
@@ -154,7 +155,7 @@
struct PruningFunctionCloner {
Function *NewFunc;
const Function *OldFunc;
- std::map<const Value*, Value*> &ValueMap;
+ DenseMap<const Value*, Value*> &ValueMap;
std::vector<ReturnInst*> &Returns;
const char *NameSuffix;
ClonedCodeInfo *CodeInfo;
@@ -162,7 +163,7 @@
public:
PruningFunctionCloner(Function *newFunc, const Function *oldFunc,
- std::map<const Value*, Value*> &valueMap,
+ DenseMap<const Value*, Value*> &valueMap,
std::vector<ReturnInst*> &returns,
const char *nameSuffix,
ClonedCodeInfo *codeInfo,
@@ -303,7 +304,7 @@
/// dead. Since this doesn't produce an exactly copy of the input, it can't be
/// used for things like CloneFunction or CloneModule.
void llvm::CloneAndPruneFunctionInto(Function *NewFunc, const Function
*OldFunc,
- std::map<const Value*, Value*> &ValueMap,
+ DenseMap<const Value*, Value*> &ValueMap,
std::vector<ReturnInst*> &Returns,
const char *NameSuffix,
ClonedCodeInfo *CodeInfo,
Index: llvm/lib/Transforms/Utils/CloneModule.cpp
diff -u llvm/lib/Transforms/Utils/CloneModule.cpp:1.21
llvm/lib/Transforms/Utils/CloneModule.cpp:1.22
--- llvm/lib/Transforms/Utils/CloneModule.cpp:1.21 Tue Jan 30 14:08:38 2007
+++ llvm/lib/Transforms/Utils/CloneModule.cpp Fri Feb 2 18:08:31 2007
@@ -29,12 +29,12 @@
Module *llvm::CloneModule(const Module *M) {
// Create the value map that maps things from the old module over to the new
// module.
- std::map<const Value*, Value*> ValueMap;
-
+ DenseMap<const Value*, Value*> ValueMap;
return CloneModule(M, ValueMap);
}
-Module *llvm::CloneModule(const Module *M, std::map<const Value*, Value*>
&ValueMap) {
+Module *llvm::CloneModule(const Module *M,
+ DenseMap<const Value*, Value*> &ValueMap) {
// First off, we need to create the new module...
Module *New = new Module(M->getModuleIdentifier());
New->setDataLayout(M->getDataLayout());
Index: llvm/lib/Transforms/Utils/CloneTrace.cpp
diff -u llvm/lib/Transforms/Utils/CloneTrace.cpp:1.11
llvm/lib/Transforms/Utils/CloneTrace.cpp:1.12
--- llvm/lib/Transforms/Utils/CloneTrace.cpp:1.11 Sat Apr 23 16:38:35 2005
+++ llvm/lib/Transforms/Utils/CloneTrace.cpp Fri Feb 2 18:08:31 2007
@@ -26,7 +26,7 @@
std::vector<BasicBlock *>
llvm::CloneTrace(const std::vector<BasicBlock*> &origTrace) {
std::vector<BasicBlock *> clonedTrace;
- std::map<const Value*, Value*> ValueMap;
+ DenseMap<const Value*, Value*> ValueMap;
//First, loop over all the Basic Blocks in the trace and copy
//them using CloneBasicBlock. Also fix the phi nodes during
@@ -92,7 +92,7 @@
/// saved in ValueMap.
///
void llvm::CloneTraceInto(Function *NewFunc, Trace &T,
- std::map<const Value*, Value*> &ValueMap,
+ DenseMap<const Value*, Value*> &ValueMap,
const char *NameSuffix) {
assert(NameSuffix && "NameSuffix cannot be null!");
Index: llvm/lib/Transforms/Utils/InlineFunction.cpp
diff -u llvm/lib/Transforms/Utils/InlineFunction.cpp:1.51
llvm/lib/Transforms/Utils/InlineFunction.cpp:1.52
--- llvm/lib/Transforms/Utils/InlineFunction.cpp:1.51 Tue Jan 30 17:22:39 2007
+++ llvm/lib/Transforms/Utils/InlineFunction.cpp Fri Feb 2 18:08:31 2007
@@ -143,7 +143,7 @@
static void UpdateCallGraphAfterInlining(const Function *Caller,
const Function *Callee,
Function::iterator FirstNewBlock,
- std::map<const Value*, Value*>
&ValueMap,
+ DenseMap<const Value*, Value*>
&ValueMap,
CallGraph &CG) {
// Update the call graph by deleting the edge from Callee to Caller
CallGraphNode *CalleeNode = CG[Callee];
@@ -156,7 +156,7 @@
E = CalleeNode->end(); I != E; ++I) {
const Instruction *OrigCall = I->first.getInstruction();
- std::map<const Value*, Value*>::iterator VMI = ValueMap.find(OrigCall);
+ DenseMap<const Value*, Value*>::iterator VMI = ValueMap.find(OrigCall);
// Only copy the edge if the call was inlined!
if (VMI != ValueMap.end() && VMI->second) {
// If the call was inlined, but then constant folded, there is no edge to
@@ -208,7 +208,7 @@
Function::iterator FirstNewBlock;
{ // Scope to destroy ValueMap after cloning.
- std::map<const Value*, Value*> ValueMap;
+ DenseMap<const Value*, Value*> ValueMap;
// Calculate the vector of arguments to pass into the function cloner,
which
// matches up the formal to the actual argument values.
Index: llvm/lib/Transforms/Utils/ValueMapper.cpp
diff -u llvm/lib/Transforms/Utils/ValueMapper.cpp:1.28
llvm/lib/Transforms/Utils/ValueMapper.cpp:1.29
--- llvm/lib/Transforms/Utils/ValueMapper.cpp:1.28 Thu Jan 11 06:24:14 2007
+++ llvm/lib/Transforms/Utils/ValueMapper.cpp Fri Feb 2 18:08:31 2007
@@ -18,9 +18,12 @@
#include "llvm/Instruction.h"
using namespace llvm;
-Value *llvm::MapValue(const Value *V, std::map<const Value*, Value*> &VM) {
+Value *llvm::MapValue(const Value *V, ValueMapTy &VM) {
Value *&VMSlot = VM[V];
if (VMSlot) return VMSlot; // Does it exist in the map yet?
+
+ // NOTE: VMSlot can be invalidated by any reference to VM, which can grow the
+ // DenseMap. This includes any recursive calls to MapValue.
// Global values do not need to be seeded into the ValueMap if they are using
// the identity mapping.
@@ -46,10 +49,10 @@
Values.push_back(cast<Constant>(MV));
for (++i; i != e; ++i)
Values.push_back(cast<Constant>(MapValue(CA->getOperand(i), VM)));
- return VMSlot = ConstantArray::get(CA->getType(), Values);
+ return VM[V] = ConstantArray::get(CA->getType(), Values);
}
}
- return VMSlot = C;
+ return VM[V] = C;
} else if (ConstantStruct *CS = dyn_cast<ConstantStruct>(C)) {
for (unsigned i = 0, e = CS->getNumOperands(); i != e; ++i) {
@@ -65,16 +68,16 @@
Values.push_back(cast<Constant>(MV));
for (++i; i != e; ++i)
Values.push_back(cast<Constant>(MapValue(CS->getOperand(i), VM)));
- return VMSlot = ConstantStruct::get(CS->getType(), Values);
+ return VM[V] = ConstantStruct::get(CS->getType(), Values);
}
}
- return VMSlot = C;
+ return VM[V] = C;
} else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) {
std::vector<Constant*> Ops;
for (unsigned i = 0, e = CE->getNumOperands(); i != e; ++i)
Ops.push_back(cast<Constant>(MapValue(CE->getOperand(i), VM)));
- return VMSlot = CE->getWithOperands(Ops);
+ return VM[V] = CE->getWithOperands(Ops);
} else if (ConstantPacked *CP = dyn_cast<ConstantPacked>(C)) {
for (unsigned i = 0, e = CP->getNumOperands(); i != e; ++i) {
Value *MV = MapValue(CP->getOperand(i), VM);
@@ -89,7 +92,7 @@
Values.push_back(cast<Constant>(MV));
for (++i; i != e; ++i)
Values.push_back(cast<Constant>(MapValue(CP->getOperand(i), VM)));
- return VMSlot = ConstantPacked::get(Values);
+ return VM[V] = ConstantPacked::get(Values);
}
}
return VMSlot = C;
@@ -105,8 +108,7 @@
/// RemapInstruction - Convert the instruction operands from referencing the
/// current values into those specified by ValueMap.
///
-void llvm::RemapInstruction(Instruction *I,
- std::map<const Value *, Value*> &ValueMap) {
+void llvm::RemapInstruction(Instruction *I, ValueMapTy &ValueMap) {
for (unsigned op = 0, E = I->getNumOperands(); op != E; ++op) {
const Value *Op = I->getOperand(op);
Value *V = MapValue(Op, ValueMap);
Index: llvm/lib/Transforms/Utils/ValueMapper.h
diff -u llvm/lib/Transforms/Utils/ValueMapper.h:1.6
llvm/lib/Transforms/Utils/ValueMapper.h:1.7
--- llvm/lib/Transforms/Utils/ValueMapper.h:1.6 Thu Apr 21 18:45:34 2005
+++ llvm/lib/Transforms/Utils/ValueMapper.h Fri Feb 2 18:08:31 2007
@@ -15,12 +15,12 @@
#ifndef VALUEMAPPER_H
#define VALUEMAPPER_H
-#include <map>
+#include "llvm/ADT/DenseMap.h"
namespace llvm {
class Value;
class Instruction;
- typedef std::map<const Value *, Value *> ValueMapTy;
+ typedef DenseMap<const Value *, Value *> ValueMapTy;
Value *MapValue(const Value *V, ValueMapTy &VM);
void RemapInstruction(Instruction *I, ValueMapTy &VM);
_______________________________________________
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
