[BOLT][NFC] Use llvm::is_contained

[Amir]

Summary

Apply the replacement throughout BOLT.

[rafauler]

LGTM

[kuhar]

FYI, by a quick scan through the patch, it seems like a likely pessimization. Currently, llvm::is_contained performs a linear scan to find the element, while .find(x) is typically O(1) or O(log n). Related discussion on this topic: https://reviews.llvm.org/D146061

[Amir]

In D145464#4194916, @kuhar wrote:

FYI, by a quick scan through the patch, it seems like a likely pessimization. Currently, llvm::is_contained performs a linear scan to find the element, while .find(x) is typically O(1) or O(log n). Related discussion on this topic: https://reviews.llvm.org/D146061

Thanks for a heads up! It'd be great to specialize is_contained for const- or log-time lookup.

bolt/lib/Core/BinaryFunction.cpp

ErrorOr<ArrayRef<uint8_t>> BinaryFunction::getData() const {
   auto *Bytes = reinterpret_cast<const uint8_t *>(SectionContents.data());
   return ArrayRef<uint8_t>(Bytes + Offset, getMaxSize());
 }
 
 size_t BinaryFunction::getSizeOfDataInCodeAt(uint64_t Offset) const {
   if (!Islands)
     return 0;
 
-  if (Islands->DataOffsets.find(Offset) == Islands->DataOffsets.end())
+  if (!llvm::is_contained(Islands->DataOffsets, Offset))
     return 0;
 
   auto Iter = Islands->CodeOffsets.upper_bound(Offset);
   if (Iter != Islands->CodeOffsets.end())
     return *Iter - Offset;
   return getSize() - Offset;
 }
 

bolt/lib/Passes/FrameAnalysis.cpp

bool FrameAnalysis::updateArgsTouchedFor(const BinaryFunction &BF, MCInst &Inst,
   auto Iter = ArgsTouchedMap.find(Function);
 
   bool Changed = false;
   if (BC.MIB->isTailCall(Inst) && Iter != ArgsTouchedMap.end()) {
     // Ignore checking CurOffset because we can't always reliably determine the
     // offset specially after an epilogue, where tailcalls happen. It should be
     // -8.
     for (std::pair<int64_t, uint8_t> Elem : Iter->second) {
-      if (ArgsTouchedMap[&BF].find(Elem) == ArgsTouchedMap[&BF].end()) {
+      if (!llvm::is_contained(ArgsTouchedMap[&BF], Elem)) {
         ArgsTouchedMap[&BF].emplace(Elem);
         Changed = true;
       }
     }
   }
   if (FunctionsRequireAlignment.count(Function) &&
       !FunctionsRequireAlignment.count(&BF)) {
     Changed = true;

bolt/lib/Passes/Instrumentation.cpp

void Instrumentation::instrumentFunction(BinaryFunction &Function,
 
   // Modified version of BinaryFunction::dfs() to build a spanning tree
   if (!opts::ConservativeInstrumentation) {
     while (!Stack.empty()) {
       BinaryBasicBlock *BB;
       const BinaryBasicBlock *Pred;
       std::tie(Pred, BB) = Stack.top();
       Stack.pop();
-      if (VisitedSet.find(BB) != VisitedSet.end())
+      if (llvm::is_contained(VisitedSet, BB))
         continue;
 
       VisitedSet.insert(BB);
       if (Pred)
         STOutSet[Pred].insert(BB);
 
       for (BinaryBasicBlock *SuccBB : BB->successors())
         Stack.push(std::make_pair(BB, SuccBB));
for (auto I = BB.begin(); I != BB.end(); ++I) {
                               FromOffset, *TargetFunc, TargetBB, ToOffset,
                               IsLeafFunction, IsInvokeBlock, FuncDesc,
                               BBToID[&BB]);
         }
         continue;
       }
       if (TargetFunc) {
         // Do not instrument edges in the spanning tree
-        if (STOutSet[&BB].find(TargetBB) != STOutSet[&BB].end()) {
+        if (llvm::is_contained(STOutSet[&BB], TargetBB)) {
           auto L = BC.scopeLock();
           createEdgeDescription(*FuncDesc, Function, FromOffset, BBToID[&BB],
                                 Function, ToOffset, BBToID[TargetBB],
                                 /*Instrumented=*/false);
           continue;
         }
         instrumentOneTarget(SplitWorklist, SplitInstrs, I, Function, BB,
                             FromOffset, *TargetFunc, TargetBB, ToOffset,
                             IsLeafFunction, IsInvokeBlock, FuncDesc,
                             BBToID[&BB], BBToID[TargetBB]);
         continue;
       }
 
       if (IsJumpTable) {
         for (BinaryBasicBlock *&Succ : BB.successors()) {
           // Do not instrument edges in the spanning tree
-          if (STOutSet[&BB].find(&*Succ) != STOutSet[&BB].end()) {
+          if (llvm::is_contained(STOutSet[&BB], &*Succ)) {
             auto L = BC.scopeLock();
             createEdgeDescription(*FuncDesc, Function, FromOffset, BBToID[&BB],
                                   Function, Succ->getInputOffset(),
                                   BBToID[&*Succ], /*Instrumented=*/false);
             continue;
           }
           instrumentOneTarget(
               SplitWorklist, SplitInstrs, I, Function, BB, FromOffset, Function,
if (!HasUnconditionalBranch && !HasJumpTable && BB.succ_size() > 0 &&
       // if it was branching to the end of the function as a result of
       // __builtin_unreachable(), in which case it was deleted by fixBranches.
       // Ignore this case. FIXME: force fixBranches() to preserve the offset.
       if (!BC.MIB->getOffset(*LastInstr))
         continue;
       FromOffset = *BC.MIB->getOffset(*LastInstr);
 
       // Do not instrument edges in the spanning tree
-      if (STOutSet[&BB].find(FTBB) != STOutSet[&BB].end()) {
+      if (llvm::is_contained(STOutSet[&BB], FTBB)) {
         auto L = BC.scopeLock();
         createEdgeDescription(*FuncDesc, Function, FromOffset, BBToID[&BB],
                               Function, FTBB->getInputOffset(), BBToID[FTBB],
                               /*Instrumented=*/false);
         continue;
       }
       instrumentOneTarget(SplitWorklist, SplitInstrs, I, Function, BB,
                           FromOffset, Function, FTBB, FTBB->getInputOffset(),