[IPO][SampleContextTracker] Use SmallVector to track context profiles to prevent non-determinism.

[huihuiz]

Summary

Use SmallVector instead of SmallSet to track the context profiles mapped. Doing this
can help avoid non-determinism caused by iterating over unordered containers.

This bug was found with reverse iteration turning on,
--extra-llvm-cmake-variables="-DLLVM_REVERSE_ITERATION=ON".
Failing LLVM test profile-context-tracker-debug.ll .

[wenlei]

LGTM, thanks for the fix. I used SmallSet initially, but the need for set went away later.

[huihuiz]

Thank you for the review! @wenlei , could you also help take a look at D99544 and D99549. They are in a similar vein. Thanks a lot!

llvm/include/llvm/Transforms/IPO/SampleContextTracker.h

 /// This file provides the interface for context-sensitive profile tracker used
 /// by CSSPGO.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_IPO_SAMPLECONTEXTTRACKER_H
 #define LLVM_TRANSFORMS_IPO_SAMPLECONTEXTTRACKER_H
 
-#include "llvm/ADT/SmallSet.h"
+#include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Analysis/CallGraph.h"
 #include "llvm/IR/DebugInfoMetadata.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/ProfileData/SampleProf.h"
 #include <list>
 #include <map>

 // provides interfaces used by sample profile loader to query context profile or
 // base profile for given function or location; it also manages context tree
 // manipulation that is needed to accommodate inline decisions so we have
 // accurate post-inline profile for functions. Internally context profiles
 // are organized in a trie, with each node representing profile for specific
 // calling context and the context is identified by path from root to the node.
 class SampleContextTracker {
 public:
-  using ContextSamplesTy = SmallSet<FunctionSamples *, 16>;
+  using ContextSamplesTy = SmallVector<FunctionSamples *, 16>;
 
   SampleContextTracker(StringMap<FunctionSamples> &Profiles);
   // Query context profile for a specific callee with given name at a given
   // call-site. The full context is identified by location of call instruction.
   FunctionSamples *getCalleeContextSamplesFor(const CallBase &Inst,
                                               StringRef CalleeName);
   // Get samples for indirect call targets for call site at given location.
   std::vector<const FunctionSamples *>
private:
   ContextTrieNode &promoteMergeContextSamplesTree(ContextTrieNode &NodeToPromo);
   void mergeContextNode(ContextTrieNode &FromNode, ContextTrieNode &ToNode,
                         StringRef ContextStrToRemove);
   ContextTrieNode &promoteMergeContextSamplesTree(ContextTrieNode &FromNode,
                                                   ContextTrieNode &ToNodeParent,
                                                   StringRef ContextStrToRemove);
 
   // Map from function name to context profiles (excluding base profile)
-  StringMap<ContextSamplesTy> FuncToCtxtProfileSet;
+  StringMap<ContextSamplesTy> FuncToCtxtProfiles;
 
   // Root node for context trie tree
   ContextTrieNode RootContext;
 };
 
 } // end namespace llvm
 #endif // LLVM_TRANSFORMS_IPO_SAMPLECONTEXTTRACKER_H

llvm/lib/Transforms/IPO/SampleContextTracker.cpp

 // Profiler tracker than manages profiles and its associated context
 SampleContextTracker::SampleContextTracker(
     StringMap<FunctionSamples> &Profiles) {
   for (auto &FuncSample : Profiles) {
     FunctionSamples *FSamples = &FuncSample.second;
     SampleContext Context(FuncSample.first(), RawContext);
     LLVM_DEBUG(dbgs() << "Tracking Context for function: " << Context << "\n");
     if (!Context.isBaseContext())
-      FuncToCtxtProfileSet[Context.getNameWithoutContext()].insert(FSamples);
+      FuncToCtxtProfiles[Context.getNameWithoutContext()].push_back(FSamples);
     ContextTrieNode *NewNode = getOrCreateContextPath(Context, true);
     assert(!NewNode->getFunctionSamples() &&
            "New node can't have sample profile");
     NewNode->setFunctionSamples(FSamples);
   }
 }
 
 FunctionSamples *
if (!Node)
     return nullptr;
 
   return Node->getFunctionSamples();
 }
 
 SampleContextTracker::ContextSamplesTy &
 SampleContextTracker::getAllContextSamplesFor(const Function &Func) {
   StringRef CanonName = FunctionSamples::getCanonicalFnName(Func);
-  return FuncToCtxtProfileSet[CanonName];
+  return FuncToCtxtProfiles[CanonName];
 }
 
 SampleContextTracker::ContextSamplesTy &
 SampleContextTracker::getAllContextSamplesFor(StringRef Name) {
-  return FuncToCtxtProfileSet[Name];
+  return FuncToCtxtProfiles[Name];
 }
 
 FunctionSamples *SampleContextTracker::getBaseSamplesFor(const Function &Func,
                                                          bool MergeContext) {
   StringRef CanonName = FunctionSamples::getCanonicalFnName(Func);
   return getBaseSamplesFor(CanonName, MergeContext);
 }
 
 FunctionSamples *SampleContextTracker::getBaseSamplesFor(StringRef Name,
                                                          bool MergeContext) {
   LLVM_DEBUG(dbgs() << "Getting base profile for function: " << Name << "\n");
   // Base profile is top-level node (child of root node), so try to retrieve
   // existing top-level node for given function first. If it exists, it could be
   // that we've merged base profile before, or there's actually context-less
   // profile from the input (e.g. due to unreliable stack walking).
   ContextTrieNode *Node = getTopLevelContextNode(Name);
   if (MergeContext) {
     LLVM_DEBUG(dbgs() << "  Merging context profile into base profile: " << Name
                       << "\n");
 
     // We have profile for function under different contexts,
     // create synthetic base profile and merge context profiles
     // into base profile.
-    for (auto *CSamples : FuncToCtxtProfileSet[Name]) {
+    for (auto *CSamples : FuncToCtxtProfiles[Name]) {
       SampleContext &Context = CSamples->getContext();
       ContextTrieNode *FromNode = getContextFor(Context);
       if (FromNode == Node)
         continue;
 
       // Skip inlined context profile and also don't re-merge any context
       if (Context.hasState(InlinedContext) || Context.hasState(MergedContext))
         continue;