[BOLT] Remove dependency on StringMap iteration order

[maksfb]

Summary

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

[Amir]

What's the reason behind Counts/JumpTableCounts being a MapVector<StringRef, uint64_t in ReorderData::assignMemData but NamesToBranchesMapTy being an std::map<StringRef, FuncBranchData>?

[maksfb]

In D145194#4167432, @Amir wrote:

What's the reason behind Counts/JumpTableCounts being a MapVector<StringRef, uint64_t in ReorderData::assignMemData but NamesToBranchesMapTy being an std::map<StringRef, FuncBranchData>?

Different order of iteration over the elements. For MapVector<> it's the insertion order.

bolt/include/bolt/Profile/DataReader.h

 
 #include "bolt/Profile/ProfileReaderBase.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringSet.h"
 #include "llvm/Support/ErrorOr.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/raw_ostream.h"
+#include <map>
 #include <unordered_map>
 #include <vector>
 
 namespace llvm {
 class MCSymbol;
 
 namespace bolt {
 
FuncMemData *getMemData(const BinaryFunction &BF) const {
     return FMDI->second;
   }
 
   /// Updates the memory profile data associated with function \p BF.
   void setMemData(const BinaryFunction &BF, FuncMemData *FMD) {
     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 =
       std::unordered_map<const BinaryFunction *, FuncMemData *>;
 
   /// Dumps the entire data structures parsed. Used for debugging.
   void dump() const;
 

bolt/lib/Passes/ReorderData.cpp

 //===----------------------------------------------------------------------===//
 
 // TODO:
 // - make sure writeable data isn't put on same cache line unless temporally
 // local
 // - estimate temporal locality by looking at CFG?
 
 #include "bolt/Passes/ReorderData.h"
+#include "llvm/ADT/MapVector.h"
 #include <algorithm>
 
 #undef  DEBUG_TYPE
 #define DEBUG_TYPE "reorder-data"
 
 using namespace llvm;
 using namespace bolt;
 
for (auto &Entry : BC.getBinaryDataForSection(Section)) {
     uint64_t BDCount = BDCI == BinaryDataCounts.end() ? 0 : BDCI->second;
     Order.emplace_back(BD, BDCount);
   }
   return Order;
 }
 
 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;
     if (!BF.hasMemoryProfile())
       continue;
 
     for (const BinaryBasicBlock &BB : BF) {
       for (const MCInst &Inst : BB) {
for (const BinaryBasicBlock &BB : BF) {
           TotalCount += AccessInfo.Count;
         }
       }
     }
   }
 
   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) {
         const uint64_t JTCount = JumpTableCounts[Section];
         outs() << "BOLT-INFO:     jump tables = " << JTCount
                << format(" (%.1f%%)\n", 100.0 * JTCount / Count);
       }
     }

bolt/lib/Profile/DataAggregator.cpp

if (BinaryData *BD = BC->getBinaryDataContainingAddress(Addr)) {
       // Filter out heap/stack accesses
       continue;
     }
 
     const Location FuncLoc(!FuncName.empty(), FuncName, PC);
     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");
   }
 }
 
 std::error_code DataAggregator::parsePreAggregatedLBRSamples() {
   outs() << "PERF2BOLT: parsing pre-aggregated profile...\n";
DataAggregator::writeAggregatedFile(StringRef OutputFilename) const {
   if (BAT)
     OutFile << "boltedcollection\n";
   if (opts::BasicAggregation) {
     OutFile << "no_lbr";
     for (const StringMapEntry<std::nullopt_t> &Entry : EventNames)
       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)
           continue;
         writeLocation(BI.From);
         writeLocation(BI.To);
         OutFile << BI.Mispreds << " " << BI.Branches << "\n";
         ++BranchValues;
       }
     }
 
     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";
         ++MemValues;
       }
     }
   }
 

bolt/lib/Profile/DataReader.cpp

 
 Error DataReader::readProfile(BinaryContext &BC) {
   for (auto &BFI : BC.getBinaryFunctions()) {
     BinaryFunction &Function = BFI.second;
     readProfile(Function);
   }
 
   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();
 }
 
 std::error_code DataReader::parseInput() {
   ErrorOr<std::unique_ptr<MemoryBuffer>> MB =
       MemoryBuffer::getFileOrSTDIN(Filename);
if (std::error_code EC = Res.getError())
       return EC;
 
     SampleInfo SI = Res.get();
 
     // Ignore samples not involving known locations
     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()) {
     ErrorOr<MemInfo> Res = parseMemInfo();
     if (std::error_code EC = Res.getError())
       return EC;
 
     MemInfo MI = Res.get();
 
     // Ignore memory events not involving known pc.
     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();
 }
 
 std::error_code DataReader::parse() {
   auto GetOrCreateFuncEntry = [&](StringRef Name) {
     auto I = NamesToBranches.find(Name);
if (std::error_code EC = Res.getError())
       return EC;
 
     BranchInfo BI = Res.get();
 
     // Ignore branches not involving known location.
     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.
     // NB: the data is skewed since we cannot tell tail recursion from
     //     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;
     }
   }
 
   while (hasMemData()) {
     ErrorOr<MemInfo> Res = parseMemInfo();
     if (std::error_code EC = Res.getError())
       return EC;
 
     MemInfo MI = Res.get();
 
     // Ignore memory events not involving known pc.
     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) *>>
+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<decltype(MapTy::MapEntryTy::second) *> AllData;
+  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)) {
     std::string Name = normalizeName(FuncName);
     const std::optional<StringRef> LTOCommonName = getLTOCommonName(Name);
     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;
 
   if (getFuncSampleData(Function.getNames()) ||
       getBranchDataForNames(Function.getNames()) ||
       getMemDataForNames(Function.getNames()))
     return true;

 }
 
 std::vector<FuncMemData *>
 DataReader::getMemDataForNamesRegex(const std::vector<StringRef> &FuncNames) {
   return fetchMapEntriesRegex(NamesToMemEvents, LTOCommonNameMemMap, 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;
   }
   return false;
 }
 
 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";
   }
 
   for (auto I = EventNames.begin(), E = EventNames.end(); I != E; ++I) {
     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
         Diag << "\n" << MI.Offset << ": " << MI.Addr << "/" << MI.Count;
       LastOffset = MI.Offset;
     }
     Diag << "\n";
   }
 }
 
 } // namespace bolt
 } // namespace llvm

bolt/test/runtime/X86/fdata-escape-chars.ll

 ; INSTR_CHECK: Binary Function "main"
 ; INSTR_CHECK: Exec Count  : 1
 ; INSTR_CHECK: {{([[:xdigit:]]+)}}:   callq   "symb whitespace" # Count: 1
 ; INSTR_CHECK: {{([[:xdigit:]]+)}}:   callq   "symb backslash\" # Count: 2
 ; INSTR_CHECK: Binary Function "static symb backslash\/1(*2)"
 ; 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
 ; PREAGR_CHECK: Binary Function "symb backslash\"
 ; PREAGR_CHECK-DAG: Exec Count  : 2
 ; PREAGR_CHECK: Binary Function "static symb backslash\/1(*2)"
 ; PREAGR_CHECK-DAG: Exec Count  : 1