[BOLT] Remove dependency on StringMap iteration order

Remove the usage of StringMap in places where the iteration order
affects the output since the iteration over StringMap is
non-deterministic.

Reviewed By: Amir

Differential Revision: https://reviews.llvm.org/D145194

5 files changed, 78 insertions, 67 deletions

diff --git a/bolt/include/bolt/Profile/DataReader.h b/bolt/include/bolt/Profile/DataReader.h
index cf6d24c67f11..916b4f7e218a 100644
--- a/bolt/include/bolt/Profile/DataReader.h
+++ b/bolt/include/bolt/Profile/DataReader.h
@@ -21,6 +21,7 @@
 #include "llvm/Support/ErrorOr.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/raw_ostream.h"
+#include <map>
 #include <unordered_map>
 #include <vector>
 
@@ -426,9 +427,9 @@ protected:
     FuncsToMemData[&BF] = FMD;
   }
 
-  using NamesToBranchesMapTy = StringMap<FuncBranchData>;
-  using NamesToSamplesMapTy = StringMap<FuncSampleData>;
-  using NamesToMemEventsMapTy = StringMap<FuncMemData>;
+  using NamesToBranchesMapTy = std::map<StringRef, FuncBranchData>;
+  using NamesToSamplesMapTy = std::map<StringRef, FuncSampleData>;
+  using NamesToMemEventsMapTy = std::map<StringRef, FuncMemData>;
   using FuncsToBranchesMapTy =
       std::unordered_map<const BinaryFunction *, FuncBranchData *>;
   using FuncsToMemDataMapTy =
diff --git a/bolt/lib/Passes/ReorderData.cpp b/bolt/lib/Passes/ReorderData.cpp
index f12a3eada4b1..4df6ce37596d 100644
--- a/bolt/lib/Passes/ReorderData.cpp
+++ b/bolt/lib/Passes/ReorderData.cpp
@@ -16,6 +16,7 @@
 // - estimate temporal locality by looking at CFG?
 
 #include "bolt/Passes/ReorderData.h"
+#include "llvm/ADT/MapVector.h"
 #include <algorithm>
 
 #undef  DEBUG_TYPE
@@ -172,8 +173,8 @@ DataOrder ReorderData::baseOrder(BinaryContext &BC,
 
 void ReorderData::assignMemData(BinaryContext &BC) {
   // Map of sections (or heap/stack) to count/size.
-  StringMap<uint64_t> Counts;
-  StringMap<uint64_t> JumpTableCounts;
+  MapVector<StringRef, uint64_t> Counts;
+  MapVector<StringRef, uint64_t> JumpTableCounts;
   uint64_t TotalCount = 0;
   for (auto &BFI : BC.getBinaryFunctions()) {
     const BinaryFunction &BF = BFI.second;
@@ -208,9 +209,9 @@ void ReorderData::assignMemData(BinaryContext &BC) {
 
   if (!Counts.empty()) {
     outs() << "BOLT-INFO: Memory stats breakdown:\n";
-    for (StringMapEntry<uint64_t> &Entry : Counts) {
-      StringRef Section = Entry.first();
-      const uint64_t Count = Entry.second;
+    for (const auto &KV : Counts) {
+      StringRef Section = KV.first;
+      const uint64_t Count = KV.second;
       outs() << "BOLT-INFO:   " << Section << " = " << Count
              << format(" (%.1f%%)\n", 100.0 * Count / TotalCount);
       if (JumpTableCounts.count(Section) != 0) {
diff --git a/bolt/lib/Profile/DataAggregator.cpp b/bolt/lib/Profile/DataAggregator.cpp
index 395d56b69dc5..c0f4ce258079 100644
--- a/bolt/lib/Profile/DataAggregator.cpp
+++ b/bolt/lib/Profile/DataAggregator.cpp
@@ -1729,6 +1729,7 @@ void DataAggregator::processMemEvents() {
     const Location AddrLoc(!MemName.empty(), MemName, Addr);
 
     FuncMemData *MemData = &NamesToMemEvents[FuncName];
+    MemData->Name = FuncName;
     setMemData(*Func, MemData);
     MemData->update(FuncLoc, AddrLoc);
     LLVM_DEBUG(dbgs() << "Mem event: " << FuncLoc << " = " << AddrLoc << "\n");
@@ -2241,22 +2242,24 @@ DataAggregator::writeAggregatedFile(StringRef OutputFilename) const {
       OutFile << " " << Entry.getKey();
     OutFile << "\n";
 
-    for (const StringMapEntry<FuncSampleData> &Func : NamesToSamples) {
-      for (const SampleInfo &SI : Func.getValue().Data) {
+    for (const auto &KV : NamesToSamples) {
+      const FuncSampleData &FSD = KV.second;
+      for (const SampleInfo &SI : FSD.Data) {
         writeLocation(SI.Loc);
         OutFile << SI.Hits << "\n";
         ++BranchValues;
       }
     }
   } else {
-    for (const StringMapEntry<FuncBranchData> &Func : NamesToBranches) {
-      for (const llvm::bolt::BranchInfo &BI : Func.getValue().Data) {
+    for (const auto &KV : NamesToBranches) {
+      const FuncBranchData &FBD = KV.second;
+      for (const llvm::bolt::BranchInfo &BI : FBD.Data) {
         writeLocation(BI.From);
         writeLocation(BI.To);
         OutFile << BI.Mispreds << " " << BI.Branches << "\n";
         ++BranchValues;
       }
-      for (const llvm::bolt::BranchInfo &BI : Func.getValue().EntryData) {
+      for (const llvm::bolt::BranchInfo &BI : FBD.EntryData) {
         // Do not output if source is a known symbol, since this was already
         // accounted for in the source function
         if (BI.From.IsSymbol)
@@ -2269,8 +2272,9 @@ DataAggregator::writeAggregatedFile(StringRef OutputFilename) const {
     }
 
     WriteMemLocs = true;
-    for (const StringMapEntry<FuncMemData> &Func : NamesToMemEvents) {
-      for (const MemInfo &MemEvent : Func.getValue().Data) {
+    for (const auto &KV : NamesToMemEvents) {
+      const FuncMemData &FMD = KV.second;
+      for (const MemInfo &MemEvent : FMD.Data) {
         writeLocation(MemEvent.Offset);
         writeLocation(MemEvent.Addr);
         OutFile << MemEvent.Count << "\n";
diff --git a/bolt/lib/Profile/DataReader.cpp b/bolt/lib/Profile/DataReader.cpp
index 54e4c309f4a6..edc4bf977f21 100644
--- a/bolt/lib/Profile/DataReader.cpp
+++ b/bolt/lib/Profile/DataReader.cpp
@@ -317,9 +317,11 @@ Error DataReader::readProfile(BinaryContext &BC) {
   }
 
   uint64_t NumUnused = 0;
-  for (const StringMapEntry<FuncBranchData> &FuncData : NamesToBranches)
-    if (!FuncData.getValue().Used)
+  for (const auto &KV : NamesToBranches) {
+    const FuncBranchData &FBD = KV.second;
+    if (!FBD.Used)
       ++NumUnused;
+  }
   BC.setNumUnusedProfiledObjects(NumUnused);
 
   return Error::success();
@@ -1116,8 +1118,8 @@ std::error_code DataReader::parseInNoLBRMode() {
     if (!SI.Loc.IsSymbol)
       continue;
 
-    StringMapIterator<FuncSampleData> I = GetOrCreateFuncEntry(SI.Loc.Name);
-    I->getValue().Data.emplace_back(std::move(SI));
+    auto I = GetOrCreateFuncEntry(SI.Loc.Name);
+    I->second.Data.emplace_back(std::move(SI));
   }
 
   while (hasMemData()) {
@@ -1131,14 +1133,14 @@ std::error_code DataReader::parseInNoLBRMode() {
     if (!MI.Offset.IsSymbol)
       continue;
 
-    StringMapIterator<FuncMemData> I = GetOrCreateFuncMemEntry(MI.Offset.Name);
-    I->getValue().Data.emplace_back(std::move(MI));
+    auto I = GetOrCreateFuncMemEntry(MI.Offset.Name);
+    I->second.Data.emplace_back(std::move(MI));
   }
 
-  for (StringMapEntry<FuncSampleData> &FuncSamples : NamesToSamples)
+  for (auto &FuncSamples : NamesToSamples)
     llvm::stable_sort(FuncSamples.second.Data);
 
-  for (StringMapEntry<FuncMemData> &MemEvents : NamesToMemEvents)
+  for (auto &MemEvents : NamesToMemEvents)
     llvm::stable_sort(MemEvents.second.Data);
 
   return std::error_code();
@@ -1199,15 +1201,15 @@ std::error_code DataReader::parse() {
     if (!BI.From.IsSymbol && !BI.To.IsSymbol)
       continue;
 
-    StringMapIterator<FuncBranchData> I = GetOrCreateFuncEntry(BI.From.Name);
-    I->getValue().Data.emplace_back(std::move(BI));
+    auto I = GetOrCreateFuncEntry(BI.From.Name);
+    I->second.Data.emplace_back(std::move(BI));
 
     // Add entry data for branches to another function or branches
     // to entry points (including recursive calls)
     if (BI.To.IsSymbol &&
         (!BI.From.Name.equals(BI.To.Name) || BI.To.Offset == 0)) {
       I = GetOrCreateFuncEntry(BI.To.Name);
-      I->getValue().EntryData.emplace_back(std::move(BI));
+      I->second.EntryData.emplace_back(std::move(BI));
     }
 
     // If destination is the function start - update execution count.
@@ -1215,7 +1217,7 @@ std::error_code DataReader::parse() {
     //     branches to the function start.
     if (BI.To.IsSymbol && BI.To.Offset == 0) {
       I = GetOrCreateFuncEntry(BI.To.Name);
-      I->getValue().ExecutionCount += BI.Branches;
+      I->second.ExecutionCount += BI.Branches;
     }
   }
 
@@ -1230,69 +1232,68 @@ std::error_code DataReader::parse() {
     if (!MI.Offset.IsSymbol)
       continue;
 
-    StringMapIterator<FuncMemData> I = GetOrCreateFuncMemEntry(MI.Offset.Name);
-    I->getValue().Data.emplace_back(std::move(MI));
+    auto I = GetOrCreateFuncMemEntry(MI.Offset.Name);
+    I->second.Data.emplace_back(std::move(MI));
   }
 
-  for (StringMapEntry<FuncBranchData> &FuncBranches : NamesToBranches)
+  for (auto &FuncBranches : NamesToBranches)
     llvm::stable_sort(FuncBranches.second.Data);
 
-  for (StringMapEntry<FuncMemData> &MemEvents : NamesToMemEvents)
+  for (auto &MemEvents : NamesToMemEvents)
     llvm::stable_sort(MemEvents.second.Data);
 
   return std::error_code();
 }
 
 void DataReader::buildLTONameMaps() {
-  for (StringMapEntry<FuncBranchData> &FuncData : NamesToBranches) {
-    const StringRef FuncName = FuncData.getKey();
+  for (auto &FuncData : NamesToBranches) {
+    const StringRef FuncName = FuncData.first;
     const std::optional<StringRef> CommonName = getLTOCommonName(FuncName);
     if (CommonName)
-      LTOCommonNameMap[*CommonName].push_back(&FuncData.getValue());
+      LTOCommonNameMap[*CommonName].push_back(&FuncData.second);
   }
 
-  for (StringMapEntry<FuncMemData> &FuncData : NamesToMemEvents) {
-    const StringRef FuncName = FuncData.getKey();
+  for (auto &FuncData : NamesToMemEvents) {
+    const StringRef FuncName = FuncData.first;
     const std::optional<StringRef> CommonName = getLTOCommonName(FuncName);
     if (CommonName)
-      LTOCommonNameMemMap[*CommonName].push_back(&FuncData.getValue());
+      LTOCommonNameMemMap[*CommonName].push_back(&FuncData.second);
   }
 }
 
-namespace {
 template <typename MapTy>
-decltype(MapTy::MapEntryTy::second) *
+static typename MapTy::mapped_type *
 fetchMapEntry(MapTy &Map, const std::vector<MCSymbol *> &Symbols) {
   // Do a reverse order iteration since the name in profile has a higher chance
   // of matching a name at the end of the list.
   for (const MCSymbol *Symbol : llvm::reverse(Symbols)) {
     auto I = Map.find(normalizeName(Symbol->getName()));
     if (I != Map.end())
-      return &I->getValue();
+      return &I->second;
   }
   return nullptr;
 }
 
 template <typename MapTy>
-decltype(MapTy::MapEntryTy::second) *
+static typename MapTy::mapped_type *
 fetchMapEntry(MapTy &Map, const std::vector<StringRef> &FuncNames) {
   // Do a reverse order iteration since the name in profile has a higher chance
   // of matching a name at the end of the list.
   for (StringRef Name : llvm::reverse(FuncNames)) {
     auto I = Map.find(normalizeName(Name));
     if (I != Map.end())
-      return &I->getValue();
+      return &I->second;
   }
   return nullptr;
 }
 
 template <typename MapTy>
-std::vector<decltype(MapTy::MapEntryTy::second) *> fetchMapEntriesRegex(
-    MapTy &Map,
-    const StringMap<std::vector<decltype(MapTy::MapEntryTy::second) *>>
-        &LTOCommonNameMap,
-    const std::vector<StringRef> &FuncNames) {
-  std::vector<decltype(MapTy::MapEntryTy::second) *> AllData;
+static std::vector<typename MapTy::mapped_type *>
+fetchMapEntriesRegex(MapTy &Map,
+                     const StringMap<std::vector<typename MapTy::mapped_type *>>
+                         &LTOCommonNameMap,
+                     const std::vector<StringRef> &FuncNames) {
+  std::vector<typename MapTy::mapped_type *> AllData;
   // Do a reverse order iteration since the name in profile has a higher chance
   // of matching a name at the end of the list.
   for (StringRef FuncName : llvm::reverse(FuncNames)) {
@@ -1301,21 +1302,19 @@ std::vector<decltype(MapTy::MapEntryTy::second) *> fetchMapEntriesRegex(
     if (LTOCommonName) {
       auto I = LTOCommonNameMap.find(*LTOCommonName);
       if (I != LTOCommonNameMap.end()) {
-        const std::vector<decltype(MapTy::MapEntryTy::second) *> &CommonData =
-            I->getValue();
+        const std::vector<typename MapTy::mapped_type *> &CommonData =
+            I->second;
         AllData.insert(AllData.end(), CommonData.begin(), CommonData.end());
       }
     } else {
       auto I = Map.find(Name);
       if (I != Map.end())
-        return {&I->getValue()};
+        return {&I->second};
     }
   }
   return AllData;
 }
 
-}
-
 bool DataReader::mayHaveProfileData(const BinaryFunction &Function) {
   if (getBranchData(Function) || getMemData(Function))
     return true;
@@ -1372,8 +1371,8 @@ DataReader::getMemDataForNamesRegex(const std::vector<StringRef> &FuncNames) {
 }
 
 bool DataReader::hasLocalsWithFileName() const {
-  for (const StringMapEntry<FuncBranchData> &Func : NamesToBranches) {
-    const StringRef &FuncName = Func.getKey();
+  for (const auto &Func : NamesToBranches) {
+    const StringRef &FuncName = Func.first;
     if (FuncName.count('/') == 2 && FuncName[0] != '/')
       return true;
   }
@@ -1381,13 +1380,15 @@ bool DataReader::hasLocalsWithFileName() const {
 }
 
 void DataReader::dump() const {
-  for (const StringMapEntry<FuncBranchData> &Func : NamesToBranches) {
-    Diag << Func.getKey() << " branches:\n";
-    for (const BranchInfo &BI : Func.getValue().Data)
+  for (const auto &KV : NamesToBranches) {
+    const StringRef Name = KV.first;
+    const FuncBranchData &FBD = KV.second;
+    Diag << Name << " branches:\n";
+    for (const BranchInfo &BI : FBD.Data)
       Diag << BI.From.Name << " " << BI.From.Offset << " " << BI.To.Name << " "
            << BI.To.Offset << " " << BI.Mispreds << " " << BI.Branches << "\n";
-    Diag << Func.getKey() << " entry points:\n";
-    for (const BranchInfo &BI : Func.getValue().EntryData)
+    Diag << Name << " entry points:\n";
+    for (const BranchInfo &BI : FBD.EntryData)
       Diag << BI.From.Name << " " << BI.From.Offset << " " << BI.To.Name << " "
            << BI.To.Offset << " " << BI.Mispreds << " " << BI.Branches << "\n";
   }
@@ -1396,16 +1397,20 @@ void DataReader::dump() const {
     StringRef Event = I->getKey();
     Diag << "Data was collected with event: " << Event << "\n";
   }
-  for (const StringMapEntry<FuncSampleData> &Func : NamesToSamples) {
-    Diag << Func.getKey() << " samples:\n";
-    for (const SampleInfo &SI : Func.getValue().Data)
+  for (const auto &KV : NamesToSamples) {
+    const StringRef Name = KV.first;
+    const FuncSampleData &FSD = KV.second;
+    Diag << Name << " samples:\n";
+    for (const SampleInfo &SI : FSD.Data)
       Diag << SI.Loc.Name << " " << SI.Loc.Offset << " " << SI.Hits << "\n";
   }
 
-  for (const StringMapEntry<FuncMemData> &Func : NamesToMemEvents) {
-    Diag << "Memory events for " << Func.getValue().Name;
+  for (const auto &KV : NamesToMemEvents) {
+    const StringRef Name = KV.first;
+    const FuncMemData &FMD = KV.second;
+    Diag << "Memory events for " << Name;
     Location LastOffset(0);
-    for (const MemInfo &MI : Func.getValue().Data) {
+    for (const MemInfo &MI : FMD.Data) {
       if (MI.Offset == LastOffset)
         Diag << ", " << MI.Addr << "/" << MI.Count;
       else
diff --git a/bolt/test/runtime/X86/fdata-escape-chars.ll b/bolt/test/runtime/X86/fdata-escape-chars.ll
index 3f0bb12c33ba..a5be4e4eb134 100644
--- a/bolt/test/runtime/X86/fdata-escape-chars.ll
+++ b/bolt/test/runtime/X86/fdata-escape-chars.ll
@@ -87,11 +87,11 @@ define internal void @static_symb_backslash_b() #0 {
 ; INSTR_CHECK: Exec Count  : 1
 ; INSTR_CHECK: {{([[:xdigit:]]+)}}:   callq   "symb whitespace" # Count: 1
 
-; PREAGR_FDATA_CHECK: 1 symb\ backslash\\ 0 1 symb\ whitespace 0 0 2
 ; PREAGR_FDATA_CHECK: 1 main 0 1 static\ symb\ backslash\\/1 0 0 1
 ; PREAGR_FDATA_CHECK: 1 main 0 1 symb\ whitespace 0 0 1
 ; PREAGR_FDATA_CHECK: 1 main 0 1 symb\ backslash\\ 0 0 2
 ; PREAGR_FDATA_CHECK: 1 static\ symb\ backslash\\/1 0 1 symb\ whitespace 0 0 1
+; PREAGR_FDATA_CHECK: 1 symb\ backslash\\ 0 1 symb\ whitespace 0 0 2
 
 ; PREAGR_CHECK: Binary Function "symb whitespace"
 ; PREAGR_CHECK-DAG: Exec Count  : 4