Reapply r215966, r215965, r215964, r215963, r215960, r215959, r215958, and r215957

This reverts commit r215981, which reverted the above commits because
MSVC std::equal asserts on nullptr iterators, and thes commits
introduced an `ArrayRef::equals()` on empty ArrayRefs.

ArrayRef was changed not to use std::equal in r215986.

llvm-svn: 215987

1 files changed, 179 insertions, 110 deletions

diff --git a/llvm/lib/IR/Constants.cpp b/llvm/lib/IR/Constants.cpp
index 45a71dc6230..cb7c9e63059 100644
--- a/llvm/lib/IR/Constants.cpp
+++ b/llvm/lib/IR/Constants.cpp
@@ -803,6 +803,11 @@ ConstantArray::ConstantArray(ArrayType *T, ArrayRef<Constant *> V)
 }
 
 Constant *ConstantArray::get(ArrayType *Ty, ArrayRef<Constant*> V) {
+  if (Constant *C = getImpl(Ty, V))
+    return C;
+  return Ty->getContext().pImpl->ArrayConstants.getOrCreate(Ty, V);
+}
+Constant *ConstantArray::getImpl(ArrayType *Ty, ArrayRef<Constant*> V) {
   // Empty arrays are canonicalized to ConstantAggregateZero.
   if (V.empty())
     return ConstantAggregateZero::get(Ty);
@@ -811,7 +816,6 @@ Constant *ConstantArray::get(ArrayType *Ty, ArrayRef<Constant*> V) {
     assert(V[i]->getType() == Ty->getElementType() &&
            "Wrong type in array element initializer");
   }
-  LLVMContextImpl *pImpl = Ty->getContext().pImpl;
 
   // If this is an all-zero array, return a ConstantAggregateZero object.  If
   // all undef, return an UndefValue, if "all simple", then return a
@@ -893,7 +897,7 @@ Constant *ConstantArray::get(ArrayType *Ty, ArrayRef<Constant*> V) {
   }
 
   // Otherwise, we really do want to create a ConstantArray.
-  return pImpl->ArrayConstants.getOrCreate(Ty, V);
+  return nullptr;
 }
 
 /// getTypeForElements - Return an anonymous struct type to use for a constant
@@ -981,9 +985,14 @@ ConstantVector::ConstantVector(VectorType *T, ArrayRef<Constant *> V)
 
 // ConstantVector accessors.
 Constant *ConstantVector::get(ArrayRef<Constant*> V) {
+  if (Constant *C = getImpl(V))
+    return C;
+  VectorType *Ty = VectorType::get(V.front()->getType(), V.size());
+  return Ty->getContext().pImpl->VectorConstants.getOrCreate(Ty, V);
+}
+Constant *ConstantVector::getImpl(ArrayRef<Constant*> V) {
   assert(!V.empty() && "Vectors can't be empty");
   VectorType *T = VectorType::get(V.front()->getType(), V.size());
-  LLVMContextImpl *pImpl = T->getContext().pImpl;
 
   // If this is an all-undef or all-zero vector, return a
   // ConstantAggregateZero or UndefValue.
@@ -1075,7 +1084,7 @@ Constant *ConstantVector::get(ArrayRef<Constant*> V) {
 
   // Otherwise, the element type isn't compatible with ConstantDataVector, or
   // the operand list constants a ConstantExpr or something else strange.
-  return pImpl->VectorConstants.getOrCreate(T, V);
+  return nullptr;
 }
 
 Constant *ConstantVector::getSplat(unsigned NumElts, Constant *V) {
@@ -1469,27 +1478,21 @@ void BlockAddress::replaceUsesOfWithOnConstant(Value *From, Value *To, Use *U) {
   // and return early.
   BlockAddress *&NewBA =
     getContext().pImpl->BlockAddresses[std::make_pair(NewF, NewBB)];
-  if (!NewBA) {
-    getBasicBlock()->AdjustBlockAddressRefCount(-1);
-
-    // Remove the old entry, this can't cause the map to rehash (just a
-    // tombstone will get added).
-    getContext().pImpl->BlockAddresses.erase(std::make_pair(getFunction(),
-                                                            getBasicBlock()));
-    NewBA = this;
-    setOperand(0, NewF);
-    setOperand(1, NewBB);
-    getBasicBlock()->AdjustBlockAddressRefCount(1);
+  if (NewBA) {
+    replaceUsesOfWithOnConstantImpl(NewBA);
     return;
   }
 
-  // Otherwise, I do need to replace this with an existing value.
-  assert(NewBA != this && "I didn't contain From!");
-
-  // Everyone using this now uses the replacement.
-  replaceAllUsesWith(NewBA);
+  getBasicBlock()->AdjustBlockAddressRefCount(-1);
 
-  destroyConstant();
+  // Remove the old entry, this can't cause the map to rehash (just a
+  // tombstone will get added).
+  getContext().pImpl->BlockAddresses.erase(std::make_pair(getFunction(),
+                                                          getBasicBlock()));
+  NewBA = this;
+  setOperand(0, NewF);
+  setOperand(1, NewBB);
+  getBasicBlock()->AdjustBlockAddressRefCount(1);
 }
 
 //---- ConstantExpr::get() implementations.
@@ -1507,7 +1510,7 @@ static inline Constant *getFoldedCast(
   LLVMContextImpl *pImpl = Ty->getContext().pImpl;
 
   // Look up the constant in the table first to ensure uniqueness.
-  ExprMapKeyType Key(opc, C);
+  ConstantExprKeyType Key(opc, C);
 
   return pImpl->ExprConstants.getOrCreate(Ty, Key);
 }
@@ -1842,7 +1845,7 @@ Constant *ConstantExpr::get(unsigned Opcode, Constant *C1, Constant *C2,
     return FC;          // Fold a few common cases.
 
   Constant *ArgVec[] = { C1, C2 };
-  ExprMapKeyType Key(Opcode, ArgVec, 0, Flags);
+  ConstantExprKeyType Key(Opcode, ArgVec, 0, Flags);
 
   LLVMContextImpl *pImpl = C1->getContext().pImpl;
   return pImpl->ExprConstants.getOrCreate(C1->getType(), Key);
@@ -1919,7 +1922,7 @@ Constant *ConstantExpr::getSelect(Constant *C, Constant *V1, Constant *V2) {
     return SC;        // Fold common cases
 
   Constant *ArgVec[] = { C, V1, V2 };
-  ExprMapKeyType Key(Instruction::Select, ArgVec);
+  ConstantExprKeyType Key(Instruction::Select, ArgVec);
 
   LLVMContextImpl *pImpl = C->getContext().pImpl;
   return pImpl->ExprConstants.getOrCreate(V1->getType(), Key);
@@ -1954,8 +1957,8 @@ Constant *ConstantExpr::getGetElementPtr(Constant *C, ArrayRef<Value *> Idxs,
            "getelementptr index type missmatch");
     ArgVec.push_back(cast<Constant>(Idxs[i]));
   }
-  const ExprMapKeyType Key(Instruction::GetElementPtr, ArgVec, 0,
-                           InBounds ? GEPOperator::IsInBounds : 0);
+  const ConstantExprKeyType Key(Instruction::GetElementPtr, ArgVec, 0,
+                                InBounds ? GEPOperator::IsInBounds : 0);
 
   LLVMContextImpl *pImpl = C->getContext().pImpl;
   return pImpl->ExprConstants.getOrCreate(ReqTy, Key);
@@ -1973,7 +1976,7 @@ ConstantExpr::getICmp(unsigned short pred, Constant *LHS, Constant *RHS) {
   // Look up the constant in the table first to ensure uniqueness
   Constant *ArgVec[] = { LHS, RHS };
   // Get the key type with both the opcode and predicate
-  const ExprMapKeyType Key(Instruction::ICmp, ArgVec, pred);
+  const ConstantExprKeyType Key(Instruction::ICmp, ArgVec, pred);
 
   Type *ResultTy = Type::getInt1Ty(LHS->getContext());
   if (VectorType *VT = dyn_cast<VectorType>(LHS->getType()))
@@ -1994,7 +1997,7 @@ ConstantExpr::getFCmp(unsigned short pred, Constant *LHS, Constant *RHS) {
   // Look up the constant in the table first to ensure uniqueness
   Constant *ArgVec[] = { LHS, RHS };
   // Get the key type with both the opcode and predicate
-  const ExprMapKeyType Key(Instruction::FCmp, ArgVec, pred);
+  const ConstantExprKeyType Key(Instruction::FCmp, ArgVec, pred);
 
   Type *ResultTy = Type::getInt1Ty(LHS->getContext());
   if (VectorType *VT = dyn_cast<VectorType>(LHS->getType()))
@@ -2015,7 +2018,7 @@ Constant *ConstantExpr::getExtractElement(Constant *Val, Constant *Idx) {
 
   // Look up the constant in the table first to ensure uniqueness
   Constant *ArgVec[] = { Val, Idx };
-  const ExprMapKeyType Key(Instruction::ExtractElement, ArgVec);
+  const ConstantExprKeyType Key(Instruction::ExtractElement, ArgVec);
 
   LLVMContextImpl *pImpl = Val->getContext().pImpl;
   Type *ReqTy = Val->getType()->getVectorElementType();
@@ -2035,7 +2038,7 @@ Constant *ConstantExpr::getInsertElement(Constant *Val, Constant *Elt,
     return FC;          // Fold a few common cases.
   // Look up the constant in the table first to ensure uniqueness
   Constant *ArgVec[] = { Val, Elt, Idx };
-  const ExprMapKeyType Key(Instruction::InsertElement, ArgVec);
+  const ConstantExprKeyType Key(Instruction::InsertElement, ArgVec);
 
   LLVMContextImpl *pImpl = Val->getContext().pImpl;
   return pImpl->ExprConstants.getOrCreate(Val->getType(), Key);
@@ -2055,7 +2058,7 @@ Constant *ConstantExpr::getShuffleVector(Constant *V1, Constant *V2,
 
   // Look up the constant in the table first to ensure uniqueness
   Constant *ArgVec[] = { V1, V2, Mask };
-  const ExprMapKeyType Key(Instruction::ShuffleVector, ArgVec);
+  const ConstantExprKeyType Key(Instruction::ShuffleVector, ArgVec);
 
   LLVMContextImpl *pImpl = ShufTy->getContext().pImpl;
   return pImpl->ExprConstants.getOrCreate(ShufTy, Key);
@@ -2075,7 +2078,7 @@ Constant *ConstantExpr::getInsertValue(Constant *Agg, Constant *Val,
     return FC;
 
   Constant *ArgVec[] = { Agg, Val };
-  const ExprMapKeyType Key(Instruction::InsertValue, ArgVec, 0, 0, Idxs);
+  const ConstantExprKeyType Key(Instruction::InsertValue, ArgVec, 0, 0, Idxs);
 
   LLVMContextImpl *pImpl = Agg->getContext().pImpl;
   return pImpl->ExprConstants.getOrCreate(ReqTy, Key);
@@ -2096,7 +2099,7 @@ Constant *ConstantExpr::getExtractValue(Constant *Agg,
     return FC;
 
   Constant *ArgVec[] = { Agg };
-  const ExprMapKeyType Key(Instruction::ExtractValue, ArgVec, 0, 0, Idxs);
+  const ConstantExprKeyType Key(Instruction::ExtractValue, ArgVec, 0, 0, Idxs);
 
   LLVMContextImpl *pImpl = Agg->getContext().pImpl;
   return pImpl->ExprConstants.getOrCreate(ReqTy, Key);
@@ -2652,6 +2655,17 @@ Constant *ConstantDataVector::getSplatValue() const {
 /// work, but would be really slow because it would have to unique each updated
 /// array instance.
 ///
+void Constant::replaceUsesOfWithOnConstantImpl(Constant *Replacement) {
+  // I do need to replace this with an existing value.
+  assert(Replacement != this && "I didn't contain From!");
+
+  // Everyone using this now uses the replacement.
+  replaceAllUsesWith(Replacement);
+
+  // Delete the old constant!
+  destroyConstant();
+}
+
 void ConstantArray::replaceUsesOfWithOnConstant(Value *From, Value *To,
                                                 Use *U) {
   assert(isa<Constant>(To) && "Cannot make Constant refer to non-constant!");
@@ -2678,52 +2692,51 @@ void ConstantArray::replaceUsesOfWithOnConstant(Value *From, Value *To,
     AllSame &= Val == ToC;
   }
 
-  Constant *Replacement = nullptr;
   if (AllSame && ToC->isNullValue()) {
-    Replacement = ConstantAggregateZero::get(getType());
-  } else if (AllSame && isa<UndefValue>(ToC)) {
-    Replacement = UndefValue::get(getType());
-  } else {
-    // Check to see if we have this array type already.
-    LLVMContextImpl::ArrayConstantsTy::LookupKey Lookup(
-        cast<ArrayType>(getType()), makeArrayRef(Values));
-    LLVMContextImpl::ArrayConstantsTy::MapTy::iterator I =
-      pImpl->ArrayConstants.find(Lookup);
-
-    if (I != pImpl->ArrayConstants.map_end()) {
-      Replacement = I->first;
-    } else {
-      // Okay, the new shape doesn't exist in the system yet.  Instead of
-      // creating a new constant array, inserting it, replaceallusesof'ing the
-      // old with the new, then deleting the old... just update the current one
-      // in place!
-      pImpl->ArrayConstants.remove(this);
-
-      // Update to the new value.  Optimize for the case when we have a single
-      // operand that we're changing, but handle bulk updates efficiently.
-      if (NumUpdated == 1) {
-        unsigned OperandToUpdate = U - OperandList;
-        assert(getOperand(OperandToUpdate) == From &&
-               "ReplaceAllUsesWith broken!");
-        setOperand(OperandToUpdate, ToC);
-      } else {
-        for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
-          if (getOperand(i) == From)
-            setOperand(i, ToC);
-      }
-      pImpl->ArrayConstants.insert(this);
-      return;
-    }
+    replaceUsesOfWithOnConstantImpl(ConstantAggregateZero::get(getType()));
+    return;
+  }
+  if (AllSame && isa<UndefValue>(ToC)) {
+    replaceUsesOfWithOnConstantImpl(UndefValue::get(getType()));
+    return;
   }
 
-  // Otherwise, I do need to replace this with an existing value.
-  assert(Replacement != this && "I didn't contain From!");
+  // Check for any other type of constant-folding.
+  if (Constant *C = getImpl(getType(), Values)) {
+    replaceUsesOfWithOnConstantImpl(C);
+    return;
+  }
 
-  // Everyone using this now uses the replacement.
-  replaceAllUsesWith(Replacement);
+  // Check to see if we have this array type already.
+  LLVMContextImpl::ArrayConstantsTy::LookupKey Lookup(
+    cast<ArrayType>(getType()), makeArrayRef(Values));
+  LLVMContextImpl::ArrayConstantsTy::MapTy::iterator I =
+    pImpl->ArrayConstants.find(Lookup);
 
-  // Delete the old constant!
-  destroyConstant();
+  if (I != pImpl->ArrayConstants.map_end()) {
+    replaceUsesOfWithOnConstantImpl(I->first);
+    return;
+  }
+
+  // Okay, the new shape doesn't exist in the system yet.  Instead of
+  // creating a new constant array, inserting it, replaceallusesof'ing the
+  // old with the new, then deleting the old... just update the current one
+  // in place!
+  pImpl->ArrayConstants.remove(this);
+
+  // Update to the new value.  Optimize for the case when we have a single
+  // operand that we're changing, but handle bulk updates efficiently.
+  if (NumUpdated == 1) {
+    unsigned OperandToUpdate = U - OperandList;
+    assert(getOperand(OperandToUpdate) == From &&
+           "ReplaceAllUsesWith broken!");
+    setOperand(OperandToUpdate, ToC);
+  } else {
+    for (unsigned I = 0, E = getNumOperands(); I != E; ++I)
+      if (getOperand(I) == From)
+        setOperand(I, ToC);
+  }
+  pImpl->ArrayConstants.insert(this);
 }
 
 void ConstantStruct::replaceUsesOfWithOnConstant(Value *From, Value *To,
@@ -2763,63 +2776,75 @@ void ConstantStruct::replaceUsesOfWithOnConstant(Value *From, Value *To,
 
   LLVMContextImpl *pImpl = getContext().pImpl;
 
-  Constant *Replacement = nullptr;
   if (isAllZeros) {
-    Replacement = ConstantAggregateZero::get(getType());
-  } else if (isAllUndef) {
-    Replacement = UndefValue::get(getType());
-  } else {
-    // Check to see if we have this struct type already.
-    LLVMContextImpl::StructConstantsTy::LookupKey Lookup(
-        cast<StructType>(getType()), makeArrayRef(Values));
-    LLVMContextImpl::StructConstantsTy::MapTy::iterator I =
+    replaceUsesOfWithOnConstantImpl(ConstantAggregateZero::get(getType()));
+    return;
+  }
+  if (isAllUndef) {
+    replaceUsesOfWithOnConstantImpl(UndefValue::get(getType()));
+    return;
+  }
+
+  // Check to see if we have this struct type already.
+  LLVMContextImpl::StructConstantsTy::LookupKey Lookup(
+      cast<StructType>(getType()), makeArrayRef(Values));
+  LLVMContextImpl::StructConstantsTy::MapTy::iterator I =
       pImpl->StructConstants.find(Lookup);
 
-    if (I != pImpl->StructConstants.map_end()) {
-      Replacement = I->first;
-    } else {
-      // Okay, the new shape doesn't exist in the system yet.  Instead of
-      // creating a new constant struct, inserting it, replaceallusesof'ing the
-      // old with the new, then deleting the old... just update the current one
-      // in place!
-      pImpl->StructConstants.remove(this);
-
-      // Update to the new value.
-      setOperand(OperandToUpdate, ToC);
-      pImpl->StructConstants.insert(this);
-      return;
-    }
+  if (I != pImpl->StructConstants.map_end()) {
+    replaceUsesOfWithOnConstantImpl(I->first);
+    return;
   }
 
-  assert(Replacement != this && "I didn't contain From!");
+  // Okay, the new shape doesn't exist in the system yet.  Instead of
+  // creating a new constant struct, inserting it, replaceallusesof'ing the
+  // old with the new, then deleting the old... just update the current one
+  // in place!
+  pImpl->StructConstants.remove(this);
 
-  // Everyone using this now uses the replacement.
-  replaceAllUsesWith(Replacement);
-
-  // Delete the old constant!
-  destroyConstant();
+  // Update to the new value.
+  setOperand(OperandToUpdate, ToC);
+  pImpl->StructConstants.insert(this);
 }
 
 void ConstantVector::replaceUsesOfWithOnConstant(Value *From, Value *To,
                                                  Use *U) {
   assert(isa<Constant>(To) && "Cannot make Constant refer to non-constant!");
+  Constant *ToC = cast<Constant>(To);
 
   SmallVector<Constant*, 8> Values;
   Values.reserve(getNumOperands());  // Build replacement array...
+  unsigned NumUpdated = 0;
   for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
     Constant *Val = getOperand(i);
-    if (Val == From) Val = cast<Constant>(To);
+    if (Val == From) {
+      ++NumUpdated;
+      Val = ToC;
+    }
     Values.push_back(Val);
   }
 
-  Constant *Replacement = get(Values);
-  assert(Replacement != this && "I didn't contain From!");
+  if (Constant *C = getImpl(Values)) {
+    replaceUsesOfWithOnConstantImpl(C);
+    return;
+  }
 
-  // Everyone using this now uses the replacement.
-  replaceAllUsesWith(Replacement);
+  // Update to the new value.  Optimize for the case when we have a single
+  // operand that we're changing, but handle bulk updates efficiently.
+  auto &pImpl = getType()->getContext().pImpl;
+  pImpl->VectorConstants.remove(this);
 
-  // Delete the old constant!
-  destroyConstant();
+  if (NumUpdated == 1) {
+    unsigned OperandToUpdate = U - OperandList;
+    assert(getOperand(OperandToUpdate) == From && "ReplaceAllUsesWith broken!");
+    setOperand(OperandToUpdate, ToC);
+  } else {
+    for (unsigned I = 0, E = getNumOperands(); I != E; ++I)
+      if (getOperand(I) == From)
+        setOperand(I, ToC);
+  }
+
+  pImpl->VectorConstants.insert(this);
 }
 
 void ConstantExpr::replaceUsesOfWithOnConstant(Value *From, Value *ToV,
@@ -2836,6 +2861,25 @@ void ConstantExpr::replaceUsesOfWithOnConstant(Value *From, Value *ToV,
   Constant *Replacement = getWithOperands(NewOps);
   assert(Replacement != this && "I didn't contain From!");
 
+  // Check if Replacement has no users (and is the same type).  Ideally, this
+  // check would be done *before* creating Replacement, but threading this
+  // through constant-folding isn't trivial.
+  if (canBecomeReplacement(Replacement)) {
+    // Avoid unnecessary RAUW traffic.
+    auto &ExprConstants = getType()->getContext().pImpl->ExprConstants;
+    ExprConstants.remove(this);
+
+    auto *CE = cast<ConstantExpr>(Replacement);
+    for (unsigned I = 0, E = getNumOperands(); I != E; ++I)
+      // Only set the operands that have actually changed.
+      if (getOperand(I) != CE->getOperand(I))
+        setOperand(I, CE->getOperand(I));
+
+    CE->destroyConstant();
+    ExprConstants.insert(this);
+    return;
+  }
+
   // Everyone using this now uses the replacement.
   replaceAllUsesWith(Replacement);
 
@@ -2843,6 +2887,31 @@ void ConstantExpr::replaceUsesOfWithOnConstant(Value *From, Value *ToV,
   destroyConstant();
 }
 
+bool ConstantExpr::canBecomeReplacement(const Constant *Replacement) const {
+  // If Replacement already has users, use it regardless.
+  if (!Replacement->use_empty())
+    return false;
+
+  // Check for anything that could have changed during constant-folding.
+  if (getValueID() != Replacement->getValueID())
+    return false;
+  const auto *CE = cast<ConstantExpr>(Replacement);
+  if (getOpcode() != CE->getOpcode())
+    return false;
+  if (getNumOperands() != CE->getNumOperands())
+    return false;
+  if (getRawSubclassOptionalData() != CE->getRawSubclassOptionalData())
+    return false;
+  if (isCompare())
+    if (getPredicate() != CE->getPredicate())
+      return false;
+  if (hasIndices())
+    if (getIndices() != CE->getIndices())
+      return false;
+
+  return true;
+}
+
 Instruction *ConstantExpr::getAsInstruction() {
   SmallVector<Value*,4> ValueOperands;
   for (op_iterator I = op_begin(), E = op_end(); I != E; ++I)