[ProfileData] Use std::vector for ValueData (NFC) (#95194)

This patch changes the type of ValueData to
std::vector<InstrProfValueData> so that, in a follow-up patch, we can
teach getValueForSite to return ArrayRef<InstrProfValueData>.

Currently, a typical traversal over the value data looks like:

  uint32_t NV = Func.getNumValueDataForSite(VK, I);
std::unique_ptr<InstrProfValueData[]> VD = Func.getValueForSite(VK, I);
  for (uint32_t V = 0; V < NV; V++)
    Do something with VD[V].Value and/or VD[V].Count;

Note that we need to call getNumValueDataForSite and getValueForSite
separately.  If getValueForSite returns ArrayRef<InstrProfValueData>
in the future, then we'll be able to do something like:

  for (const auto &V : Func.getValueForSite(VK, I))
    Do something with V.Value and/or V.Count;

If ArrayRef<InstrProfValueData> directly points to ValueData, then
getValueForSite won't need to allocate memory with std::make_unique.

Now, switching to std::vector requires us to update several places:

- sortByTargetValues switches to llvm::sort because we don't need to
  worry about sort stability.

- sortByCount retains sort stability because std::list::sort also
  performs stable sort.

- merge builds another array and move it back to ValueData to avoid a
  potential quadratic behavior with std::vector::insert into the
  middle of a vector.

1 files changed, 9 insertions, 2 deletions

diff --git a/llvm/lib/ProfileData/InstrProf.cpp b/llvm/lib/ProfileData/InstrProf.cpp
index 0d7b027..184e2c8 100644
--- a/llvm/lib/ProfileData/InstrProf.cpp
+++ b/llvm/lib/ProfileData/InstrProf.cpp
@@ -847,19 +847,26 @@ void InstrProfValueSiteRecord::merge(InstrProfValueSiteRecord &Input,
   Input.sortByTargetValues();
   auto I = ValueData.begin();
   auto IE = ValueData.end();
+  std::vector<InstrProfValueData> Merged;
+  Merged.reserve(std::max(ValueData.size(), Input.ValueData.size()));
   for (const InstrProfValueData &J : Input.ValueData) {
-    while (I != IE && I->Value < J.Value)
+    while (I != IE && I->Value < J.Value) {
+      Merged.push_back(*I);
       ++I;
+    }
     if (I != IE && I->Value == J.Value) {
       bool Overflowed;
       I->Count = SaturatingMultiplyAdd(J.Count, Weight, I->Count, &Overflowed);
       if (Overflowed)
         Warn(instrprof_error::counter_overflow);
+      Merged.push_back(*I);
       ++I;
       continue;
     }
-    ValueData.insert(I, J);
+    Merged.push_back(J);
   }
+  Merged.insert(Merged.end(), I, IE);
+  ValueData = std::move(Merged);
 }
 
 void InstrProfValueSiteRecord::scale(uint64_t N, uint64_t D,