[CalledValuePropagation] Just use a sorted vector instead of a set.

The set properties are never used, so a vector is enough. No
functionality change intended.

While there add some std::moves to SparseSolver.

llvm-svn: 333582

2 files changed, 17 insertions, 14 deletions

diff --git a/llvm/include/llvm/Analysis/SparsePropagation.h b/llvm/include/llvm/Analysis/SparsePropagation.h
index b9691351b5c..defcf96afb2 100644
--- a/llvm/include/llvm/Analysis/SparsePropagation.h
+++ b/llvm/include/llvm/Analysis/SparsePropagation.h
@@ -238,7 +238,7 @@ SparseSolver<LatticeKey, LatticeVal, KeyInfo>::getValueState(LatticeKey Key) {
   // If this value is untracked, don't add it to the map.
   if (LV == LatticeFunc->getUntrackedVal())
     return LV;
-  return ValueState[Key] = LV;
+  return ValueState[Key] = std::move(LV);
 }
 
 template <class LatticeKey, class LatticeVal, class KeyInfo>
@@ -250,7 +250,7 @@ void SparseSolver<LatticeKey, LatticeVal, KeyInfo>::UpdateState(LatticeKey Key,
 
   // Update the state of the given LatticeKey and add its corresponding LLVM
   // value to the work list.
-  ValueState[Key] = LV;
+  ValueState[Key] = std::move(LV);
   if (Value *V = KeyInfo::getValueFromLatticeKey(Key))
     ValueWorkList.push_back(V);
 }
@@ -318,7 +318,7 @@ void SparseSolver<LatticeKey, LatticeVal, KeyInfo>::getFeasibleSuccessors(
 
     Constant *C =
         dyn_cast_or_null<Constant>(LatticeFunc->GetValueFromLatticeVal(
-            BCValue, BI->getCondition()->getType()));
+            std::move(BCValue), BI->getCondition()->getType()));
     if (!C || !isa<ConstantInt>(C)) {
       // Non-constant values can go either way.
       Succs[0] = Succs[1] = true;
@@ -360,7 +360,7 @@ void SparseSolver<LatticeKey, LatticeVal, KeyInfo>::getFeasibleSuccessors(
     return;
 
   Constant *C = dyn_cast_or_null<Constant>(LatticeFunc->GetValueFromLatticeVal(
-      SCValue, SI.getCondition()->getType()));
+      std::move(SCValue), SI.getCondition()->getType()));
   if (!C || !isa<ConstantInt>(C)) {
     // All destinations are executable!
     Succs.assign(TI.getNumSuccessors(), true);
@@ -408,7 +408,8 @@ void SparseSolver<LatticeKey, LatticeVal, KeyInfo>::visitPHINode(PHINode &PN) {
     LatticeFunc->ComputeInstructionState(PN, ChangedValues, *this);
     for (auto &ChangedValue : ChangedValues)
       if (ChangedValue.second != LatticeFunc->getUntrackedVal())
-        UpdateState(ChangedValue.first, ChangedValue.second);
+        UpdateState(std::move(ChangedValue.first),
+                    std::move(ChangedValue.second));
     return;
   }
 
diff --git a/llvm/lib/Transforms/IPO/CalledValuePropagation.cpp b/llvm/lib/Transforms/IPO/CalledValuePropagation.cpp
index c5f6336aa2b..1d187046ba3 100644
--- a/llvm/lib/Transforms/IPO/CalledValuePropagation.cpp
+++ b/llvm/lib/Transforms/IPO/CalledValuePropagation.cpp
@@ -69,12 +69,15 @@ public:
 
   CVPLatticeVal() : LatticeState(Undefined) {}
   CVPLatticeVal(CVPLatticeStateTy LatticeState) : LatticeState(LatticeState) {}
-  CVPLatticeVal(std::set<Function *, Compare> &&Functions)
-      : LatticeState(FunctionSet), Functions(Functions) {}
+  CVPLatticeVal(std::vector<Function *> &&Functions)
+      : LatticeState(FunctionSet), Functions(std::move(Functions)) {
+    assert(std::is_sorted(this->Functions.begin(), this->Functions.end(),
+                          Compare()));
+  }
 
   /// Get a reference to the functions held by this lattice value. The number
   /// of functions will be zero for states other than FunctionSet.
-  const std::set<Function *, Compare> &getFunctions() const {
+  const std::vector<Function *> &getFunctions() const {
     return Functions;
   }
 
@@ -99,7 +102,8 @@ private:
   /// MaxFunctionsPerValue. Since most LLVM values are expected to be in
   /// uninteresting states (i.e., overdefined), CVPLatticeVal objects should be
   /// small and efficiently copyable.
-  std::set<Function *, Compare> Functions;
+  // FIXME: This could be a TinyPtrVector and/or merge with LatticeState.
+  std::vector<Function *> Functions;
 };
 
 /// The custom lattice function used by the generic sparse propagation solver.
@@ -150,11 +154,10 @@ public:
       return getOverdefinedVal();
     if (X == getUndefVal() && Y == getUndefVal())
       return getUndefVal();
-    std::set<Function *, CVPLatticeVal::Compare> Union;
+    std::vector<Function *> Union;
     std::set_union(X.getFunctions().begin(), X.getFunctions().end(),
                    Y.getFunctions().begin(), Y.getFunctions().end(),
-                   std::inserter(Union, Union.begin()),
-                   CVPLatticeVal::Compare{});
+                   std::back_inserter(Union), CVPLatticeVal::Compare{});
     if (Union.size() > MaxFunctionsPerValue)
       return getOverdefinedVal();
     return CVPLatticeVal(std::move(Union));
@@ -377,8 +380,7 @@ static bool runCVP(Module &M) {
     CVPLatticeVal LV = Solver.getExistingValueState(RegI);
     if (!LV.isFunctionSet() || LV.getFunctions().empty())
       continue;
-    MDNode *Callees = MDB.createCallees(SmallVector<Function *, 4>(
-        LV.getFunctions().begin(), LV.getFunctions().end()));
+    MDNode *Callees = MDB.createCallees(LV.getFunctions());
     C->setMetadata(LLVMContext::MD_callees, Callees);
     Changed = true;
   }