#include "llvm/Instructions.h"
#include "llvm/LLVMContext.h"
#include "llvm/Module.h"
+#include "llvm/Operator.h"
#include "llvm/Pass.h"
#include "llvm/Support/CallSite.h"
#include "llvm/Support/Debug.h"
public:
static const ComparableFunction EmptyKey;
static const ComparableFunction TombstoneKey;
+ static TargetData * const LookupOnly;
ComparableFunction(Function *Func, TargetData *TD)
: Func(Func), Hash(profileFunction(Func)), TD(TD) {}
const ComparableFunction ComparableFunction::EmptyKey = ComparableFunction(0);
const ComparableFunction ComparableFunction::TombstoneKey =
ComparableFunction(1);
+TargetData *const ComparableFunction::LookupOnly = (TargetData*)(-1);
}
public:
FunctionComparator(const TargetData *TD, const Function *F1,
const Function *F2)
- : F1(F1), F2(F2), TD(TD), IDMap1Count(0), IDMap2Count(0) {}
+ : F1(F1), F2(F2), TD(TD) {}
/// Test whether the two functions have equivalent behaviour.
bool compare();
const TargetData *TD;
- typedef DenseMap<const Value *, unsigned long> IDMap;
- IDMap Map1, Map2;
- unsigned long IDMap1Count, IDMap2Count;
+ DenseMap<const Value *, const Value *> id_map;
+ DenseSet<const Value *> seen_values;
};
}
return false;
}
- switch(Ty1->getTypeID()) {
+ switch (Ty1->getTypeID()) {
default:
llvm_unreachable("Unknown type!");
// Fall through in Release mode.
// Instruction::isSameOperationAs.
bool FunctionComparator::isEquivalentOperation(const Instruction *I1,
const Instruction *I2) const {
+ // Differences from Instruction::isSameOperationAs:
+ // * replace type comparison with calls to isEquivalentType.
+ // * we test for I->hasSameSubclassOptionalData (nuw/nsw/tail) at the top
+ // * because of the above, we don't test for the tail bit on calls later on
if (I1->getOpcode() != I2->getOpcode() ||
I1->getNumOperands() != I2->getNumOperands() ||
!isEquivalentType(I1->getType(), I2->getType()) ||
if (const CmpInst *CI = dyn_cast<CmpInst>(I1))
return CI->getPredicate() == cast<CmpInst>(I2)->getPredicate();
if (const CallInst *CI = dyn_cast<CallInst>(I1))
- return CI->isTailCall() == cast<CallInst>(I2)->isTailCall() &&
- CI->getCallingConv() == cast<CallInst>(I2)->getCallingConv() &&
+ return CI->getCallingConv() == cast<CallInst>(I2)->getCallingConv() &&
CI->getAttributes() == cast<CallInst>(I2)->getAttributes();
if (const InvokeInst *CI = dyn_cast<InvokeInst>(I1))
return CI->getCallingConv() == cast<InvokeInst>(I2)->getCallingConv() &&
if (isa<InlineAsm>(V1) || isa<InlineAsm>(V2))
return V1 == V2;
- unsigned long &ID1 = Map1[V1];
- if (!ID1)
- ID1 = ++IDMap1Count;
+ // Check that V1 maps to V2. If we find a value that V1 maps to then we simply
+ // check whether it's equal to V2. When there is no mapping then we need to
+ // ensure that V2 isn't already equivalent to something else. For this
+ // purpose, we track the V2 values in a set.
- unsigned long &ID2 = Map2[V2];
- if (!ID2)
- ID2 = ++IDMap2Count;
-
- return ID1 == ID2;
+ const Value *&map_elem = id_map[V1];
+ if (map_elem)
+ return map_elem == V2;
+ if (!seen_values.insert(V2).second)
+ return false;
+ map_elem = V2;
+ return true;
}
// Test whether two basic blocks have equivalent behaviour.
return true;
if (!LHS.getFunc() || !RHS.getFunc())
return false;
+
+ // One of these is a special "underlying pointer comparison only" object.
+ if (LHS.getTD() == ComparableFunction::LookupOnly ||
+ RHS.getTD() == ComparableFunction::LookupOnly)
+ return false;
+
assert(LHS.getTD() == RHS.getTD() &&
"Comparing functions for different targets");
// that was already inserted.
bool MergeFunctions::insert(ComparableFunction &NewF) {
std::pair<FnSetType::iterator, bool> Result = FnSet.insert(NewF);
- if (Result.second)
+ if (Result.second) {
+ DEBUG(dbgs() << "Inserting as unique: " << NewF.getFunc()->getName() << '\n');
return false;
+ }
const ComparableFunction &OldF = *Result.first;
// Remove a function from FnSet. If it was already in FnSet, add it to Deferred
// so that we'll look at it in the next round.
void MergeFunctions::remove(Function *F) {
- ComparableFunction CF = ComparableFunction(F, TD);
+ // We need to make sure we remove F, not a function "equal" to F per the
+ // function equality comparator.
+ //
+ // The special "lookup only" ComparableFunction bypasses the expensive
+ // function comparison in favour of a pointer comparison on the underlying
+ // Function*'s.
+ ComparableFunction CF = ComparableFunction(F, ComparableFunction::LookupOnly);
if (FnSet.erase(CF)) {
+ DEBUG(dbgs() << "Removed " << F->getName() << " from set and deferred it.\n");
Deferred.push_back(F);
}
}