Don't include Operator.h from InstrTypes.h.

[oota-llvm.git] / lib / Transforms / IPO / MergeFunctions.cpp

diff --git a/lib/Transforms/IPO/MergeFunctions.cpp b/lib/Transforms/IPO/MergeFunctions.cpp
index e2dd48458b4cf8e2118698fcbf83262ec14ac019..f74144338a611dbd31eab0eb2366a6ee79ab3c9c 100644 (file)
--- a/lib/Transforms/IPO/MergeFunctions.cpp
+++ b/lib/Transforms/IPO/MergeFunctions.cpp
@@ -55,6 +55,7 @@
 #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"
@@ -96,6 +97,7 @@ class ComparableFunction {
 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) {}
@@ -124,6 +126,7 @@ private:
 const ComparableFunction ComparableFunction::EmptyKey = ComparableFunction(0);
 const ComparableFunction ComparableFunction::TombstoneKey =
     ComparableFunction(1);
+TargetData *const ComparableFunction::LookupOnly = (TargetData*)(-1);
 
 }
 
@@ -154,7 +157,7 @@ class FunctionComparator {
 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();
@@ -189,9 +192,8 @@ private:
 
   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;
 };
 
 }
@@ -211,7 +213,7 @@ bool FunctionComparator::isEquivalentType(const Type *Ty1,
     return false;
   }
 
-  switch(Ty1->getTypeID()) {
+  switch (Ty1->getTypeID()) {
   default:
     llvm_unreachable("Unknown type!");
     // Fall through in Release mode.
@@ -284,6 +286,10 @@ bool FunctionComparator::isEquivalentType(const Type *Ty1,
 // 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()) ||
@@ -307,8 +313,7 @@ bool FunctionComparator::isEquivalentOperation(const Instruction *I1,
   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() &&
@@ -389,22 +394,21 @@ bool FunctionComparator::enumerate(const Value *V1, const Value *V2) {
       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.
@@ -659,6 +663,12 @@ bool DenseMapInfo<ComparableFunction>::isEqual(const ComparableFunction &LHS,
     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");
 
@@ -797,8 +807,10 @@ void MergeFunctions::mergeTwoFunctions(Function *F, Function *G) {
 // 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;
 
@@ -818,8 +830,15 @@ bool MergeFunctions::insert(ComparableFunction &NewF) {
 // 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);
   }
 }