[llvm] Remove uses of `std::vector<bool>`

[jansvoboda11]

Summary

LLVM Programmer’s Manual strongly discourages the use of std::vector<bool> and suggests llvm::BitVector as a possible replacement.

This patch does just that for llvm.

[dexonsmith]

Might be nice to stage a couple of these in whichever patch allows them to switch over, to make it clear why those APIs are needed/useful.

llvm/lib/Transforms/Utils/SampleProfileInference.cpp

313

It doesn't look like this depends on any of the other in-flight patches; if so, it'd be nice to land this (and others like it) outside of this long queue since they don't need all the pieces to land.

[jansvoboda11]

Split patches

[dexonsmith]

LGTM.

llvm/include/llvm/Analysis/BlockFrequencyInfoImpl.h

 //==- BlockFrequencyInfoImpl.h - Block Frequency Implementation --*- C++ -*-==//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // Shared implementation of BlockFrequency for IR and Machine Instructions.
 // See the documentation below for BlockFrequencyInfoImpl for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_BLOCKFREQUENCYINFOIMPL_H
 #define LLVM_ANALYSIS_BLOCKFREQUENCYINFOIMPL_H
 
+#include "llvm/ADT/BitVector.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/GraphTraits.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/SparseBitVector.h"
 #include "llvm/ADT/Twine.h"
for (auto &Jump : ProbMatrix[I]) {
       Successors[Jump.first].push_back(I);
     }
   }
 
   // To speedup computation, we maintain a set of "active" blocks whose
   // frequencies need to be updated based on the incoming edges.
   // The set is dynamic and changes after every update. Initially all blocks
   // with a positive frequency are active
-  auto IsActive = std::vector<bool>(Freq.size(), false);
+  auto IsActive = BitVector(Freq.size(), false);
   std::queue<size_t> ActiveSet;
   for (size_t I = 0; I < Freq.size(); I++) {
     if (Freq[I] > 0) {
       ActiveSet.push(I);
       IsActive[I] = true;
     }
   }
 

llvm/lib/Analysis/DevelopmentModeInlineAdvisor.cpp

 //===- DevelopmentModeInlineAdvisor.cpp - runtime-loadable model runner  --===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements a model runner using Tensorflow C APIs, allowing the
 // loading of a model from a command line option.
 //
 //===----------------------------------------------------------------------===//
 #include "llvm/Config/config.h"
 #include "llvm/Support/Casting.h"
 #if defined(LLVM_HAVE_TF_API)
 
 #include "llvm/Analysis/CallGraph.h"
+#include "llvm/ADT/BitVector.h"
 #include "llvm/Analysis/InlineSizeEstimatorAnalysis.h"
 #include "llvm/Analysis/MLInlineAdvisor.h"
 #include "llvm/Analysis/ModelUnderTrainingRunner.h"
 #include "llvm/Analysis/NoInferenceModelRunner.h"
 #include "llvm/Analysis/Utils/TFUtils.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/ManagedStatic.h"
public:
 
   /// Print the stored tensors.
   void print();
 
 private:
   StringRef LogFileName;
   const ModelUnderTrainingRunner *const MUTR;
   std::unique_ptr<Logger> L;
-  std::vector<bool> Effects;
+  BitVector Effects;
   /// There's at least one output. We'll set this to a different value if MUTR
   /// is avaliable.
   size_t OutputCount = 1;
   /// Set these 2 clearly OOB, to make sure we set them later.
   size_t DefaultDecisionPos = std::numeric_limits<size_t>::max();
   size_t DecisionPos = std::numeric_limits<size_t>::max();
 };
 

llvm/lib/Transforms/Utils/SampleProfileInference.cpp

 //===- SampleProfileInference.cpp - Adjust sample profiles in the IR ------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements a profile inference algorithm. Given an incomplete and
 // possibly imprecise block counts, the algorithm reconstructs realistic block
 // and edge counts that satisfy flow conservation rules, while minimally modify
 // input block counts.
 //
 //===----------------------------------------------------------------------===//
 
+#include "llvm/ADT/BitVector.h"
 #include "llvm/Transforms/Utils/SampleProfileInference.h"
 #include "llvm/Support/Debug.h"
 #include <queue>
 #include <set>
 
 using namespace llvm;
 #define DEBUG_TYPE "sample-profile-inference"
 
 namespace {
public:
   }
 
   /// The probability for the first successor of a unknown subgraph
   static constexpr double UnknownFirstSuccProbability = 0.5;
 
 private:
   void joinIsolatedComponents() {
     // Find blocks that are reachable from the source
-    auto Visited = std::vector<bool>(NumBlocks(), false);
+    auto Visited = BitVector(NumBlocks(), false);
     findReachable(Func.Entry, Visited);
 
     // Iterate over all non-reachable blocks and adjust their weights
     for (uint64_t I = 0; I < NumBlocks(); I++) {
       auto &Block = Func.Blocks[I];
       if (Block.Flow > 0 && !Visited[I]) {
         // Find a path from the entry to an exit passing through the block I
         auto Path = findShortestPath(I);
         // Increase the flow along the path
         assert(Path.size() > 0 && Path[0]->Source == Func.Entry &&
                "incorrectly computed path adjusting control flow");
         Func.Blocks[Func.Entry].Flow += 1;
         for (auto &Jump : Path) {
           Jump->Flow += 1;
           Func.Blocks[Jump->Target].Flow += 1;
           // Update reachability
           findReachable(Jump->Target, Visited);
         }
       }
     }
   }
 
   /// Run BFS from a given block along the jumps with a positive flow and mark
   /// all reachable blocks.
-  void findReachable(uint64_t Src, std::vector<bool> &Visited) {
+  void findReachable(uint64_t Src, BitVector &Visited) {
     if (Visited[Src])
       return;
     std::queue<uint64_t> Queue;
     Queue.push(Src);
     Visited[Src] = true;
     while (!Queue.empty()) {
       Src = Queue.front();
       Queue.pop();
private:
   }
 
   /// Find a unknown subgraph starting at block SrcBlock.
   /// If the search is successful, the method sets DstBlock and UnknownSuccs.
   bool findUnknownSubgraph(FlowBlock *SrcBlock, FlowBlock *&DstBlock,
                            std::vector<FlowBlock *> &UnknownSuccs) {
     // Run BFS from SrcBlock and make sure all paths are going through unknown
     // blocks and end at a non-unknown DstBlock
-    auto Visited = std::vector<bool>(NumBlocks(), false);
+    auto Visited = BitVector(NumBlocks(), false);
     std::queue<uint64_t> Queue;
     DstBlock = nullptr;
 
     Queue.push(SrcBlock->Index);
     Visited[SrcBlock->Index] = true;
     while (!Queue.empty()) {
       auto &Block = Func.Blocks[Queue.front()];
       Queue.pop();
void verifyWeights(const FlowFunction &Func) {
   for (auto &Jump : Func.Jumps) {
     if (Jump.Flow > 0) {
       PositiveFlowEdges[Jump.Source].push_back(Jump.Target);
     }
   }
 
   // Run BFS from the source along edges with positive flow
   std::queue<uint64_t> Queue;
-  auto Visited = std::vector<bool>(NumBlocks, false);
+  auto Visited = BitVector(NumBlocks, false);
   Queue.push(Func.Entry);
   Visited[Func.Entry] = true;
   while (!Queue.empty()) {
     uint64_t Src = Queue.front();
     Queue.pop();
     for (uint64_t Dst : PositiveFlowEdges[Src]) {
       if (!Visited[Dst]) {
         Queue.push(Dst);

llvm/tools/llvm-lto/llvm-lto.cpp

 static cl::opt<bool>
     DebugPassManager("debug-pass-manager", cl::init(false), cl::Hidden,
                      cl::desc("Print pass management debugging information"),
                      cl::cat(LTOCategory));
 
 namespace {
 
 struct ModuleInfo {
-  std::vector<bool> CanBeHidden;
+  BitVector CanBeHidden;
 };
 
 } // end anonymous namespace
 
 static void handleDiagnostics(lto_codegen_diagnostic_severity_t Severity,
                               const char *Msg, void *) {
   errs() << "llvm-lto: ";
   switch (Severity) {

llvm/tools/llvm-rc/ResourceScriptParser.cpp

Expected<std::unique_ptr<VersionInfoStmt>> RCParser::parseVersionInfoStmt() {
   }
 
   if (TypeResult->equals_insensitive("VALUE")) {
     ASSIGN_OR_RETURN(KeyResult, readString());
     // Read a non-empty list of strings and/or ints, each
     // possibly preceded by a comma. Unfortunately, the tool behavior depends
     // on them existing or not, so we need to memorize where we found them.
     std::vector<IntOrString> Values;
-    std::vector<bool> PrecedingCommas;
+    BitVector PrecedingCommas;
     RETURN_IF_ERROR(consumeType(Kind::Comma));
     while (!isNextTokenKind(Kind::Identifier) &&
            !isNextTokenKind(Kind::BlockEnd)) {
       // Try to eat a comma if it's not the first statement.
       bool HadComma = Values.size() > 0 && consumeOptionalType(Kind::Comma);
       ASSIGN_OR_RETURN(ValueResult, readIntOrString());
       Values.push_back(*ValueResult);
       PrecedingCommas.push_back(HadComma);

llvm/tools/llvm-rc/ResourceScriptStmt.h

 //===---------------------------------------------------------------------===//
 
 #ifndef LLVM_TOOLS_LLVMRC_RESOURCESCRIPTSTMT_H
 #define LLVM_TOOLS_LLVMRC_RESOURCESCRIPTSTMT_H
 
 #include "ResourceScriptToken.h"
 #include "ResourceVisitor.h"
 
+#include "llvm/ADT/BitVector.h"
 #include "llvm/ADT/StringSet.h"
 
 namespace llvm {
 namespace rc {
 
 // Integer wrapper that also holds information whether the user declared
 // the integer to be long (by appending L to the end of the integer) or not.
 // It allows to be implicitly cast from and to uint32_t in order
static bool classof(const VersionInfoStmt *S) {
     return S->getKind() == StBlock;
   }
 };
 
 class VersionInfoValue : public VersionInfoStmt {
 public:
   StringRef Key;
   std::vector<IntOrString> Values;
-  std::vector<bool> HasPrecedingComma;
+  BitVector HasPrecedingComma;
 
   VersionInfoValue(StringRef InfoKey, std::vector<IntOrString> &&Vals,
-                   std::vector<bool> &&CommasBeforeVals)
+                   BitVector &&CommasBeforeVals)
       : Key(InfoKey), Values(std::move(Vals)),
         HasPrecedingComma(std::move(CommasBeforeVals)) {}
   raw_ostream &log(raw_ostream &) const override;
 
   StmtKind getKind() const override { return StValue; }
   static bool classof(const VersionInfoStmt *S) {
     return S->getKind() == StValue;
   }

llvm/tools/llvm-readobj/ELFDumper.cpp

 //===----------------------------------------------------------------------===//
 
 #include "ARMEHABIPrinter.h"
 #include "DwarfCFIEHPrinter.h"
 #include "ObjDumper.h"
 #include "StackMapPrinter.h"
 #include "llvm-readobj.h"
 #include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/BitVector.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/PointerIntPair.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/SmallVector.h"
void GNUELFDumper<ELFT>::printHashTableSymbols(const Elf_Hash &SysVHash) {
 
   DataRegion<Elf_Word> ShndxTable(
       (const Elf_Word *)this->DynSymTabShndxRegion.Addr, this->Obj.end());
   auto Buckets = SysVHash.buckets();
   auto Chains = SysVHash.chains();
   for (uint32_t Buc = 0; Buc < SysVHash.nbucket; Buc++) {
     if (Buckets[Buc] == ELF::STN_UNDEF)
       continue;
-    std::vector<bool> Visited(SysVHash.nchain);
+    BitVector Visited(SysVHash.nchain);
     for (uint32_t Ch = Buckets[Buc]; Ch < SysVHash.nchain; Ch = Chains[Ch]) {
       if (Ch == ELF::STN_UNDEF)
         break;
 
       if (Visited[Ch]) {
         this->reportUniqueWarning(".hash section is invalid: bucket " +
                                   Twine(Ch) +
                                   ": a cycle was detected in the linked chain");
void GNUELFDumper<ELFT>::printHashHistogram(const Elf_Hash &HashTable) {
 
   if (NChain == 0 || NBucket == 0)
     return;
 
   std::vector<size_t> ChainLen(NBucket, 0);
   // Go over all buckets and and note chain lengths of each bucket (total
   // unique chain lengths).
   for (size_t B = 0; B < NBucket; B++) {
-    std::vector<bool> Visited(NChain);
+    BitVector Visited(NChain);
     for (size_t C = Buckets[B]; C < NChain; C = Chains[C]) {
       if (C == ELF::STN_UNDEF)
         break;
       if (Visited[C]) {
         this->reportUniqueWarning(".hash section is invalid: bucket " +
                                   Twine(C) +
                                   ": a cycle was detected in the linked chain");
         break;

llvm/unittests/Analysis/AssumeBundleQueriesTest.cpp

Function *F =
       Function::Create(FuncType, GlobalValue::ExternalLinkage, "test", &*Mod);
   BasicBlock *BB = BasicBlock::Create(C);
   BB->insertInto(F);
   Instruction *Ret = ReturnInst::Create(C);
   BB->getInstList().insert(BB->begin(), Ret);
   Function *FnAssume = Intrinsic::getDeclaration(Mod.get(), Intrinsic::assume);
 
   std::vector<Argument *> ShuffledArgs;
-  std::vector<bool> HasArg;
+  BitVector HasArg;
   for (auto &Arg : F->args()) {
     ShuffledArgs.push_back(&Arg);
     HasArg.push_back(false);
   }
 
   std::shuffle(ShuffledArgs.begin(), ShuffledArgs.end(), Rng);
 
   std::vector<OperandBundleDef> OpBundle;

llvm/utils/TableGen/CodeGenInstruction.h

 //===- CodeGenInstruction.h - Instruction Class Wrapper ---------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file defines a wrapper class for the 'Instruction' TableGen class.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_UTILS_TABLEGEN_CODEGENINSTRUCTION_H
 #define LLVM_UTILS_TABLEGEN_CODEGENINSTRUCTION_H
 
+#include "llvm/ADT/BitVector.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/MachineValueType.h"
 #include "llvm/Support/SMLoc.h"
 #include <cassert>
 #include <string>
 #include <utility>
 #include <vector>
 
struct OperandInfo {
       /// OperandList may not match the MachineInstr operand num.  Until it
       /// does, this contains the MI operand index of this operand.
       unsigned MIOperandNo;
       unsigned MINumOperands;   // The number of operands.
 
       /// DoNotEncode - Bools are set to true in this vector for each operand in
       /// the DisableEncoding list.  These should not be emitted by the code
       /// emitter.
-      std::vector<bool> DoNotEncode;
+      BitVector DoNotEncode;
 
       /// MIOperandInfo - Default MI operand type. Note an operand may be made
       /// up of multiple MI operands.
       DagInit *MIOperandInfo;
 
       /// Constraint info for this operand.  This operand can have pieces, so we
       /// track constraint info for each.
       std::vector<ConstraintInfo> Constraints;

llvm/utils/TableGen/GlobalISel/GIMatchTree.h

 };
 
 class GIMatchTreeVRegDefPartitioner : public GIMatchTreePartitioner {
   unsigned NewInstrID = -1;
   unsigned InstrID;
   unsigned OpIdx;
   std::vector<BitVector> TraversedEdges;
   DenseMap<unsigned, unsigned> ResultToPartition;
-  std::vector<bool> PartitionToResult;
+  BitVector PartitionToResult;
 
   void addToPartition(bool Result, unsigned LeafIdx);
 
 public:
   GIMatchTreeVRegDefPartitioner(unsigned InstrID, unsigned OpIdx)
       : InstrID(InstrID), OpIdx(OpIdx) {}
 
   std::unique_ptr<GIMatchTreePartitioner> clone() const override {