#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"
/// functions that will compare equal, without looking at the instructions
/// inside the function.
static unsigned profileFunction(const Function *F) {
- const FunctionType *FTy = F->getFunctionType();
+ FunctionType *FTy = F->getFunctionType();
FoldingSetNodeID ID;
ID.AddInteger(F->size());
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) {}
Func = NULL;
}
- bool &getOrInsertCachedComparison(const ComparableFunction &Other,
- bool &inserted) const {
- typedef DenseMap<Function *, bool>::iterator iterator;
- std::pair<iterator, bool> p =
- CompareResultCache.insert(std::make_pair(Other.getFunc(), false));
- inserted = p.second;
- return p.first->second;
- }
-
private:
explicit ComparableFunction(unsigned Hash)
: Func(NULL), Hash(Hash), TD(NULL) {}
- // DenseMap::grow() triggers a recomparison of all keys in the map, which is
- // wildly expensive. This cache tries to preserve known results.
- mutable DenseMap<Function *, bool> CompareResultCache;
-
AssertingVH<Function> Func;
unsigned Hash;
TargetData *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();
}
/// Compare two Types, treating all pointer types as equal.
- bool isEquivalentType(const Type *Ty1, const Type *Ty2) const;
+ bool isEquivalentType(Type *Ty1, Type *Ty2) const;
// The two functions undergoing comparison.
const Function *F1, *F2;
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;
};
}
// Any two pointers in the same address space are equivalent, intptr_t and
// pointers are equivalent. Otherwise, standard type equivalence rules apply.
-bool FunctionComparator::isEquivalentType(const Type *Ty1,
- const Type *Ty2) const {
+bool FunctionComparator::isEquivalentType(Type *Ty1,
+ Type *Ty2) const {
if (Ty1 == Ty2)
return true;
if (Ty1->getTypeID() != Ty2->getTypeID()) {
return false;
}
- switch(Ty1->getTypeID()) {
+ switch (Ty1->getTypeID()) {
default:
llvm_unreachable("Unknown type!");
// Fall through in Release mode.
case Type::IntegerTyID:
- case Type::OpaqueTyID:
case Type::VectorTyID:
// Ty1 == Ty2 would have returned true earlier.
return false;
return true;
case Type::PointerTyID: {
- const PointerType *PTy1 = cast<PointerType>(Ty1);
- const PointerType *PTy2 = cast<PointerType>(Ty2);
+ PointerType *PTy1 = cast<PointerType>(Ty1);
+ PointerType *PTy2 = cast<PointerType>(Ty2);
return PTy1->getAddressSpace() == PTy2->getAddressSpace();
}
case Type::StructTyID: {
- const StructType *STy1 = cast<StructType>(Ty1);
- const StructType *STy2 = cast<StructType>(Ty2);
+ StructType *STy1 = cast<StructType>(Ty1);
+ StructType *STy2 = cast<StructType>(Ty2);
if (STy1->getNumElements() != STy2->getNumElements())
return false;
}
case Type::FunctionTyID: {
- const FunctionType *FTy1 = cast<FunctionType>(Ty1);
- const FunctionType *FTy2 = cast<FunctionType>(Ty2);
+ FunctionType *FTy1 = cast<FunctionType>(Ty1);
+ FunctionType *FTy2 = cast<FunctionType>(Ty2);
if (FTy1->getNumParams() != FTy2->getNumParams() ||
FTy1->isVarArg() != FTy2->isVarArg())
return false;
}
case Type::ArrayTyID: {
- const ArrayType *ATy1 = cast<ArrayType>(Ty1);
- const ArrayType *ATy2 = cast<ArrayType>(Ty2);
+ ArrayType *ATy1 = cast<ArrayType>(Ty1);
+ ArrayType *ATy2 = cast<ArrayType>(Ty2);
return ATy1->getNumElements() == ATy2->getNumElements() &&
isEquivalentType(ATy1->getElementType(), ATy2->getElementType());
}
// 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()) ||
// Check special state that is a part of some instructions.
if (const LoadInst *LI = dyn_cast<LoadInst>(I1))
return LI->isVolatile() == cast<LoadInst>(I2)->isVolatile() &&
- LI->getAlignment() == cast<LoadInst>(I2)->getAlignment();
+ LI->getAlignment() == cast<LoadInst>(I2)->getAlignment() &&
+ LI->getOrdering() == cast<LoadInst>(I2)->getOrdering() &&
+ LI->getSynchScope() == cast<LoadInst>(I2)->getSynchScope();
if (const StoreInst *SI = dyn_cast<StoreInst>(I1))
return SI->isVolatile() == cast<StoreInst>(I2)->isVolatile() &&
- SI->getAlignment() == cast<StoreInst>(I2)->getAlignment();
+ SI->getAlignment() == cast<StoreInst>(I2)->getAlignment() &&
+ SI->getOrdering() == cast<StoreInst>(I2)->getOrdering() &&
+ SI->getSynchScope() == cast<StoreInst>(I2)->getSynchScope();
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() &&
CI->getAttributes() == cast<InvokeInst>(I2)->getAttributes();
- if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(I1)) {
- if (IVI->getNumIndices() != cast<InsertValueInst>(I2)->getNumIndices())
- return false;
- for (unsigned i = 0, e = IVI->getNumIndices(); i != e; ++i)
- if (IVI->idx_begin()[i] != cast<InsertValueInst>(I2)->idx_begin()[i])
- return false;
- return true;
- }
- if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(I1)) {
- if (EVI->getNumIndices() != cast<ExtractValueInst>(I2)->getNumIndices())
- return false;
- for (unsigned i = 0, e = EVI->getNumIndices(); i != e; ++i)
- if (EVI->idx_begin()[i] != cast<ExtractValueInst>(I2)->idx_begin()[i])
- return false;
- return true;
- }
+ if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(I1))
+ return IVI->getIndices() == cast<InsertValueInst>(I2)->getIndices();
+ if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(I1))
+ return EVI->getIndices() == cast<ExtractValueInst>(I2)->getIndices();
+ if (const FenceInst *FI = dyn_cast<FenceInst>(I1))
+ return FI->getOrdering() == cast<FenceInst>(I2)->getOrdering() &&
+ FI->getSynchScope() == cast<FenceInst>(I2)->getSynchScope();
+ if (const AtomicCmpXchgInst *CXI = dyn_cast<AtomicCmpXchgInst>(I1))
+ return CXI->isVolatile() == cast<AtomicCmpXchgInst>(I2)->isVolatile() &&
+ CXI->getOrdering() == cast<AtomicCmpXchgInst>(I2)->getOrdering() &&
+ CXI->getSynchScope() == cast<AtomicCmpXchgInst>(I2)->getSynchScope();
+ if (const AtomicRMWInst *RMWI = dyn_cast<AtomicRMWInst>(I1))
+ return RMWI->getOperation() == cast<AtomicRMWInst>(I2)->getOperation() &&
+ RMWI->isVolatile() == cast<AtomicRMWInst>(I2)->isVolatile() &&
+ RMWI->getOrdering() == cast<AtomicRMWInst>(I2)->getOrdering() &&
+ RMWI->getSynchScope() == cast<AtomicRMWInst>(I2)->getSynchScope();
return true;
}
SmallVector<Value *, 8> Indices1(GEP1->idx_begin(), GEP1->idx_end());
SmallVector<Value *, 8> Indices2(GEP2->idx_begin(), GEP2->idx_end());
uint64_t Offset1 = TD->getIndexedOffset(GEP1->getPointerOperandType(),
- Indices1.data(), Indices1.size());
+ Indices1);
uint64_t Offset2 = TD->getIndexedOffset(GEP2->getPointerOperandType(),
- Indices2.data(), Indices2.size());
+ Indices2);
return Offset1 == Offset2;
}
C1 == ConstantExpr::getBitCast(const_cast<Constant*>(C2), C1->getType());
}
- if (isa<InlineAsm>(V1) && isa<InlineAsm>(V2)) {
- const InlineAsm *IA1 = cast<InlineAsm>(V1);
- const InlineAsm *IA2 = cast<InlineAsm>(V2);
- return IA1->getAsmString() == IA2->getAsmString() &&
- IA1->getConstraintString() == IA2->getConstraintString();
- }
-
- unsigned long &ID1 = Map1[V1];
- if (!ID1)
- ID1 = ++IDMap1Count;
+ if (isa<InlineAsm>(V1) || isa<InlineAsm>(V2))
+ return V1 == V2;
- unsigned long &ID2 = Map2[V2];
- if (!ID2)
- ID2 = ++IDMap2Count;
+ // 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.
- 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");
- bool inserted;
- bool &result1 = LHS.getOrInsertCachedComparison(RHS, inserted);
- if (!inserted)
- return result1;
- bool &result2 = RHS.getOrInsertCachedComparison(LHS, inserted);
- if (!inserted)
- return result1 = result2;
-
- return result1 = result2 = FunctionComparator(LHS.getTD(), LHS.getFunc(),
- RHS.getFunc()).compare();
+ return FunctionComparator(LHS.getTD(), LHS.getFunc(),
+ RHS.getFunc()).compare();
}
// Replace direct callers of Old with New.
SmallVector<Value *, 16> Args;
unsigned i = 0;
- const FunctionType *FFTy = F->getFunctionType();
+ FunctionType *FFTy = F->getFunctionType();
for (Function::arg_iterator AI = NewG->arg_begin(), AE = NewG->arg_end();
AI != AE; ++AI) {
Args.push_back(Builder.CreateBitCast(AI, FFTy->getParamType(i)));
++i;
}
- CallInst *CI = Builder.CreateCall(F, Args.begin(), Args.end());
+ CallInst *CI = Builder.CreateCall(F, Args);
CI->setTailCall();
CI->setCallingConv(F->getCallingConv());
if (NewG->getReturnType()->isVoidTy()) {
// 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);
}
}