[BOLT] Towards FunctionLayout const-correctness

[FPar]

Summary

A const-qualified reference to function layout allows accessing
non-const qualified basic blocks on a const-qualified function. This
patch adds or removes const-qualifiers where necessary to indicate where
basic blocks are used in a non-const manner.

[rafauler]

LGTM

[haowei]

We are seeing clang build warnings and errors after this patch was landed. Error message:

In file included from /b/s/w/ir/x/w/llvm-llvm-project/bolt/include/bolt/Core/BinaryBasicBlock.h:18:
/b/s/w/ir/x/w/llvm-llvm-project/bolt/include/bolt/Core/FunctionLayout.h:307:62: error: no viable conversion from returned value of type 'reverse_iterator<const_iterator>' to function return type 'reverse_iterator<block_const_iterator>'
  block_const_reverse_iterator block_rbegin() const { return Blocks.rbegin(); }
                                                             ^~~~~~~~~~~~~~~
/b/s/w/ir/x/w/cipd/bin/../include/c++/v1/__iterator/reverse_iterator.h:43:28: note: candidate constructor (the implicit copy constructor) not viable: no known conversion from 'const_reverse_iterator' (aka 'reverse_iterator<llvm::bolt::BinaryBasicBlock *const *>') to 'const std::reverse_iterator<llvm::pointer_iterator<llvm::pointee_iterator<llvm::bolt::BinaryBasicBlock *const *, const llvm::bolt::BinaryBasicBlock>, const llvm::bolt::BinaryBasicBlock *>> &' for 1st argument
class _LIBCPP_TEMPLATE_VIS reverse_iterator
                           ^
/b/s/w/ir/x/w/cipd/bin/../include/c++/v1/__iterator/reverse_iterator.h:43:28: note: candidate constructor (the implicit move constructor) not viable: no known conversion from 'const_reverse_iterator' (aka 'reverse_iterator<llvm::bolt::BinaryBasicBlock *const *>') to 'std::reverse_iterator<llvm::pointer_iterator<llvm::pointee_iterator<llvm::bolt::BinaryBasicBlock *const *, const llvm::bolt::BinaryBasicBlock>, const llvm::bolt::BinaryBasicBlock *>> &&' for 1st argument
/b/s/w/ir/x/w/cipd/bin/../include/c++/v1/__iterator/reverse_iterator.h:119:5: note: candidate template ignored: requirement 'is_convertible<llvm::bolt::BinaryBasicBlock *const *const &, llvm::pointer_iterator<llvm::pointee_iterator<llvm::bolt::BinaryBasicBlock *const *, const llvm::bolt::BinaryBasicBlock>, const llvm::bolt::BinaryBasicBlock *>>::value' was not satisfied [with _Up = llvm::bolt::BinaryBasicBlock *const *]
    reverse_iterator(const reverse_iterator<_Up>& __u)
    ^
/b/s/w/ir/x/w/cipd/bin/../include/c++/v1/__iterator/reverse_iterator.h:113:14: note: explicit constructor is not a candidate
    explicit reverse_iterator(_Iter __x) : current(__x) {}

Could you take a look? If it takes a while to fix. Could you revert your change please?

Full build task: https://ci.chromium.org/ui/p/fuchsia/builders/toolchain.ci/clang-linux-x64/b8804929257456173105/overview
Full build step output: https://logs.chromium.org/logs/fuchsia/buildbucket/cr-buildbucket/8804929257456173105/+/u/clang/build/stdout

[FPar]

In D132049#3746425, @haowei wrote:

We are seeing clang build warnings and errors after this patch was landed. Error message:

In file included from /b/s/w/ir/x/w/llvm-llvm-project/bolt/include/bolt/Core/BinaryBasicBlock.h:18:
/b/s/w/ir/x/w/llvm-llvm-project/bolt/include/bolt/Core/FunctionLayout.h:307:62: error: no viable conversion from returned value of type 'reverse_iterator<const_iterator>' to function return type 'reverse_iterator<block_const_iterator>'
  block_const_reverse_iterator block_rbegin() const { return Blocks.rbegin(); }
                                                             ^~~~~~~~~~~~~~~
/b/s/w/ir/x/w/cipd/bin/../include/c++/v1/__iterator/reverse_iterator.h:43:28: note: candidate constructor (the implicit copy constructor) not viable: no known conversion from 'const_reverse_iterator' (aka 'reverse_iterator<llvm::bolt::BinaryBasicBlock *const *>') to 'const std::reverse_iterator<llvm::pointer_iterator<llvm::pointee_iterator<llvm::bolt::BinaryBasicBlock *const *, const llvm::bolt::BinaryBasicBlock>, const llvm::bolt::BinaryBasicBlock *>> &' for 1st argument
class _LIBCPP_TEMPLATE_VIS reverse_iterator
                           ^
/b/s/w/ir/x/w/cipd/bin/../include/c++/v1/__iterator/reverse_iterator.h:43:28: note: candidate constructor (the implicit move constructor) not viable: no known conversion from 'const_reverse_iterator' (aka 'reverse_iterator<llvm::bolt::BinaryBasicBlock *const *>') to 'std::reverse_iterator<llvm::pointer_iterator<llvm::pointee_iterator<llvm::bolt::BinaryBasicBlock *const *, const llvm::bolt::BinaryBasicBlock>, const llvm::bolt::BinaryBasicBlock *>> &&' for 1st argument
/b/s/w/ir/x/w/cipd/bin/../include/c++/v1/__iterator/reverse_iterator.h:119:5: note: candidate template ignored: requirement 'is_convertible<llvm::bolt::BinaryBasicBlock *const *const &, llvm::pointer_iterator<llvm::pointee_iterator<llvm::bolt::BinaryBasicBlock *const *, const llvm::bolt::BinaryBasicBlock>, const llvm::bolt::BinaryBasicBlock *>>::value' was not satisfied [with _Up = llvm::bolt::BinaryBasicBlock *const *]
    reverse_iterator(const reverse_iterator<_Up>& __u)
    ^
/b/s/w/ir/x/w/cipd/bin/../include/c++/v1/__iterator/reverse_iterator.h:113:14: note: explicit constructor is not a candidate
    explicit reverse_iterator(_Iter __x) : current(__x) {}

Could you take a look? If it takes a while to fix. Could you revert your change please?

Full build task: https://ci.chromium.org/ui/p/fuchsia/builders/toolchain.ci/clang-linux-x64/b8804929257456173105/overview
Full build step output: https://logs.chromium.org/logs/fuchsia/buildbucket/cr-buildbucket/8804929257456173105/+/u/clang/build/stdout

Sorry, I'll revert it.

[FPar]

Fix iterator conversion build failure

bolt/include/bolt/Core/BinaryBasicBlock.h

const BinaryBranchInfo &getFallthroughBranchInfo() const {
     assert(BranchInfo.size() == 2 &&
            "could only be called for blocks with 2 successors");
     return BranchInfo[1];
   };
 
   /// Return branch info corresponding to an edge going to \p Succ basic block.
   BinaryBranchInfo &getBranchInfo(const BinaryBasicBlock &Succ);
 
+  /// Return branch info corresponding to an edge going to \p Succ basic block.
+  const BinaryBranchInfo &getBranchInfo(const BinaryBasicBlock &Succ) const;
+
   /// Return branch info corresponding to an edge going to a basic block with
   /// label \p Label.
   BinaryBranchInfo &getBranchInfo(const MCSymbol *Label);
 
   /// Set branch information for the outgoing edge to block \p Succ.
   void setSuccessorBranchInfo(const BinaryBasicBlock &Succ, uint64_t Count,
                               uint64_t MispredictedCount) {
     BinaryBranchInfo &BI = getBranchInfo(Succ);

bolt/include/bolt/Core/BinaryFunction.h

public:
   bool isForwardCall(const MCSymbol *CalleeSymbol) const;
 
   /// Dump function information to debug output. If \p PrintInstructions
   /// is true - include instruction disassembly.
   void dump(bool PrintInstructions = true) const;
 
   /// Print function information to the \p OS stream.
   void print(raw_ostream &OS, std::string Annotation = "",
-             bool PrintInstructions = true) const;
+             bool PrintInstructions = true);
 
   /// Print all relocations between \p Offset and \p Offset + \p Size in
   /// this function.
   void printRelocations(raw_ostream &OS, uint64_t Offset, uint64_t Size) const;
 
   /// Return true if function has a profile, even if the profile does not
   /// match CFG 100%.
   bool hasProfile() const { return ExecutionCount != COUNT_NO_PROFILE; }

bolt/include/bolt/Core/DynoStats.h

 
 DynoStats operator+(const DynoStats &A, const DynoStats &B);
 
 /// Return dynostats for the function.
 ///
 /// The function relies on branch instructions being in-sync with CFG for
 /// branch instructions stats. Thus it is better to call it after
 /// fixBranches().
-DynoStats getDynoStats(const BinaryFunction &BF);
+DynoStats getDynoStats(BinaryFunction &BF);
 
 /// Return program-wide dynostats.
 template <typename FuncsType>
-inline DynoStats getDynoStats(const FuncsType &Funcs, bool IsAArch64) {
+inline DynoStats getDynoStats(FuncsType &Funcs, bool IsAArch64) {
   DynoStats dynoStats(IsAArch64);
   for (auto &BFI : Funcs) {
     auto &BF = BFI.second;
     if (BF.isSimple())
       dynoStats += getDynoStats(BF);
   }
   return dynoStats;
 }
 
 /// Call a function with optional before and after dynostats printing.
 template <typename FnType, typename FuncsType>
-inline void callWithDynoStats(FnType &&Func, const FuncsType &Funcs,
-                              StringRef Phase, const bool Flag,
-                              bool IsAArch64) {
+inline void callWithDynoStats(FnType &&Func, FuncsType &Funcs, StringRef Phase,
+                              const bool Flag, bool IsAArch64) {
   DynoStats DynoStatsBefore(IsAArch64);
   if (Flag)
     DynoStatsBefore = getDynoStats(Funcs, IsAArch64);
 
   Func();
 
   if (Flag) {
     const DynoStats DynoStatsAfter = getDynoStats(Funcs, IsAArch64);

bolt/include/bolt/Core/FunctionLayout.h

 #ifndef BOLT_CORE_FUNCTION_LAYOUT_H
 #define BOLT_CORE_FUNCTION_LAYOUT_H
 
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/iterator.h"
 #include "llvm/ADT/iterator_range.h"
+#include <iterator>
 
 namespace llvm {
 namespace bolt {
 
 class BinaryFunction;
 class BinaryBasicBlock;
 class FunctionLayout;
 

 /// iterating either over fragments or over BinaryFunction::begin()..end().
 class FunctionLayout {
 private:
   using BasicBlockListType = SmallVector<BinaryBasicBlock *, 0>;
   using block_iterator = BasicBlockListType::iterator;
   using FragmentListType = SmallVector<unsigned, 0>;
 
 public:
-  class FragmentIterator;
-
   class FragmentIterator
       : public iterator_facade_base<
             FragmentIterator, std::bidirectional_iterator_tag, FunctionFragment,
             std::ptrdiff_t, FunctionFragment *, FunctionFragment> {
     FragmentNum Num;
     const FunctionLayout *Layout;
 
     FragmentIterator(FragmentNum Num, const FunctionLayout *Layout)
public:
     }
 
     friend class FunctionLayout;
   };
 
   using const_iterator = FragmentIterator;
   using block_const_iterator = BasicBlockListType::const_iterator;
   using block_const_reverse_iterator =
-      BasicBlockListType::const_reverse_iterator;
+      std::reverse_iterator<block_const_iterator>;
 
 private:
   BasicBlockListType Blocks;
   /// List of indices dividing block list into fragments. To simplify iteration,
   /// we have `Fragments.back()` equals `Blocks.size()`. Hence,
   /// `Fragments.size()` equals `this->size() + 1`. Always contains at least one
   /// fragment.
   FragmentListType Fragments = {0, 0};
public:
   bool block_empty() const { return Blocks.empty(); }
   BinaryBasicBlock *block_front() const { return Blocks.front(); }
   BinaryBasicBlock *block_back() const { return Blocks.back(); }
   block_const_iterator block_begin() const { return Blocks.begin(); }
   block_const_iterator block_end() const { return Blocks.end(); }
   iterator_range<block_const_iterator> blocks() const {
     return {block_begin(), block_end()};
   }
-  block_const_reverse_iterator block_rbegin() const { return Blocks.rbegin(); }
-  block_const_reverse_iterator block_rend() const { return Blocks.rend(); }
+  block_const_reverse_iterator block_rbegin() const {
+    return block_const_reverse_iterator(block_end());
+  }
+  block_const_reverse_iterator block_rend() const {
+    return block_const_reverse_iterator(block_begin());
+  }
   iterator_range<block_const_reverse_iterator> rblocks() const {
     return {block_rbegin(), block_rend()};
   }
 
 private:
   block_const_iterator findBasicBlockPos(const BinaryBasicBlock *BB) const;
   block_iterator findBasicBlockPos(const BinaryBasicBlock *BB);
 
   friend class FunctionFragment;
 };
 
 } // namespace bolt
 } // namespace llvm
 
 #endif

bolt/include/bolt/Passes/ReorderAlgorithm.h

public:
   std::vector<ClusterTy> Clusters;
   std::vector<std::unordered_map<uint32_t, uint64_t>> ClusterEdges;
   std::vector<double> AvgFreq;
 
   /// Group the basic blocks in the given function into clusters stored in the
   /// Clusters vector. Also encode relative weights between two clusters in
   /// the ClusterEdges vector if requested. This vector is indexed by
   /// the clusters indices in the Clusters vector.
-  virtual void clusterBasicBlocks(const BinaryFunction &BF,
+  virtual void clusterBasicBlocks(BinaryFunction &BF,
                                   bool ComputeEdges = false) = 0;
 
   /// Compute for each cluster its averagae execution frequency, that is
   /// the sum of average frequencies of its blocks (execution count / # instrs).
   /// The average frequencies are stored in the AvgFreq vector, index by the
   /// cluster indices in the Clusters vector.
   void computeClusterAverageFrequency(const BinaryContext &BC);
 
virtual bool areClustersCompatible(const ClusterTy &Front,
                                      const EdgeTy &E) const = 0;
 
   // Map from basic block to owning cluster index.
   using BBToClusterMapTy =
       std::unordered_map<const BinaryBasicBlock *, unsigned>;
   BBToClusterMapTy BBToClusterMap;
 
 public:
-  void clusterBasicBlocks(const BinaryFunction &BF,
+  void clusterBasicBlocks(BinaryFunction &BF,
                           bool ComputeEdges = false) override;
   void reset() override;
 };
 
 /// This clustering algorithm is based on a greedy heuristic suggested by
 /// Pettis and Hansen (PLDI '90).
 class PHGreedyClusterAlgorithm : public GreedyClusterAlgorithm {
 protected:
public:
   ReorderAlgorithm() {}
   explicit ReorderAlgorithm(std::unique_ptr<ClusterAlgorithm> CAlgo)
       : CAlgo(std::move(CAlgo)) {}
 
   using BasicBlockOrder = BinaryFunction::BasicBlockOrderType;
 
   /// Reorder the basic blocks of the given function and store the new order in
   /// the new Clusters vector.
-  virtual void reorderBasicBlocks(const BinaryFunction &BF,
+  virtual void reorderBasicBlocks(BinaryFunction &BF,
                                   BasicBlockOrder &Order) const = 0;
 
   void setClusterAlgorithm(ClusterAlgorithm *CAlgo) {
     this->CAlgo.reset(CAlgo);
   }
 
   virtual ~ReorderAlgorithm() {}
 };
 
 /// Dynamic programming implementation for the TSP, applied to BB layout. Find
 /// the optimal way to maximize weight during a path traversing all BBs. In
 /// this way, we will convert the hottest branches into fall-throughs.
 ///
 /// Uses exponential amount of memory on the number of basic blocks and should
 /// only be used for small functions.
 class TSPReorderAlgorithm : public ReorderAlgorithm {
 public:
-  void reorderBasicBlocks(const BinaryFunction &BF,
+  void reorderBasicBlocks(BinaryFunction &BF,
                           BasicBlockOrder &Order) const override;
 };
 
 /// Simple algorithm that groups basic blocks into clusters and then
 /// lays them out cluster after cluster.
 class OptimizeReorderAlgorithm : public ReorderAlgorithm {
 public:
   explicit OptimizeReorderAlgorithm(std::unique_ptr<ClusterAlgorithm> CAlgo)
       : ReorderAlgorithm(std::move(CAlgo)) {}
 
-  void reorderBasicBlocks(const BinaryFunction &BF,
+  void reorderBasicBlocks(BinaryFunction &BF,
                           BasicBlockOrder &Order) const override;
 };
 
 /// This reorder algorithm tries to ensure that all inter-cluster edges are
 /// predicted as not-taken, by enforcing a topological order to make
 /// targets appear after sources, creating forward branches.
 class OptimizeBranchReorderAlgorithm : public ReorderAlgorithm {
 public:
   explicit OptimizeBranchReorderAlgorithm(
       std::unique_ptr<ClusterAlgorithm> CAlgo)
       : ReorderAlgorithm(std::move(CAlgo)) {}
 
-  void reorderBasicBlocks(const BinaryFunction &BF,
+  void reorderBasicBlocks(BinaryFunction &BF,
                           BasicBlockOrder &Order) const override;
 };
 
 /// This reorder tries to separate hot from cold blocks to maximize the
 /// probability that unfrequently executed code doesn't pollute the cache, by
 /// putting clusters in descending order of hotness.
 class OptimizeCacheReorderAlgorithm : public ReorderAlgorithm {
 public:
   explicit OptimizeCacheReorderAlgorithm(
       std::unique_ptr<ClusterAlgorithm> CAlgo)
       : ReorderAlgorithm(std::move(CAlgo)) {}
 
-  void reorderBasicBlocks(const BinaryFunction &BF,
+  void reorderBasicBlocks(BinaryFunction &BF,
                           BasicBlockOrder &Order) const override;
 };
 
 /// A new reordering algorithm for basic blocks, ext-tsp
 class ExtTSPReorderAlgorithm : public ReorderAlgorithm {
 public:
-  void reorderBasicBlocks(const BinaryFunction &BF,
+  void reorderBasicBlocks(BinaryFunction &BF,
                           BasicBlockOrder &Order) const override;
 };
 
 /// Toy example that simply reverses the original basic block order.
 class ReverseReorderAlgorithm : public ReorderAlgorithm {
 public:
-  void reorderBasicBlocks(const BinaryFunction &BF,
+  void reorderBasicBlocks(BinaryFunction &BF,
                           BasicBlockOrder &Order) const override;
 };
 
 /// Create clusters as usual and place them in random order.
 class RandomClusterReorderAlgorithm : public ReorderAlgorithm {
 public:
   explicit RandomClusterReorderAlgorithm(
       std::unique_ptr<ClusterAlgorithm> CAlgo)
       : ReorderAlgorithm(std::move(CAlgo)) {}
 
-  void reorderBasicBlocks(const BinaryFunction &BF,
+  void reorderBasicBlocks(BinaryFunction &BF,
                           BasicBlockOrder &Order) const override;
 };
 
 } // namespace bolt
 } // namespace llvm
 
 #endif

bolt/lib/Core/BinaryBasicBlock.cpp

 }
 
 uint64_t BinaryBasicBlock::estimateSize(const MCCodeEmitter *Emitter) const {
   return Function->getBinaryContext().computeCodeSize(begin(), end(), Emitter);
 }
 
 BinaryBasicBlock::BinaryBranchInfo &
 BinaryBasicBlock::getBranchInfo(const BinaryBasicBlock &Succ) {
-  auto BI = branch_info_begin();
-  for (BinaryBasicBlock *BB : successors()) {
-    if (&Succ == BB)
-      return *BI;
-    ++BI;
-  }
+  return const_cast<BinaryBranchInfo &>(
+      static_cast<const BinaryBasicBlock &>(*this).getBranchInfo(Succ));
 
-  llvm_unreachable("Invalid successor");
-  return *BI;
+const BinaryBasicBlock::BinaryBranchInfo &
+BinaryBasicBlock::getBranchInfo(const BinaryBasicBlock &Succ) const {
+  const auto Zip = llvm::zip(successors(), branch_info());
+  const auto Result = llvm::find_if(
+      Zip, [&](const auto &Tuple) { return std::get<0>(Tuple) == &Succ; });
+  assert(Result != Zip.end() && "Cannot find target in successors");
+  return std::get<1>(*Result);
 }
 
 BinaryBasicBlock::BinaryBranchInfo &
 BinaryBasicBlock::getBranchInfo(const MCSymbol *Label) {
   auto BI = branch_info_begin();
   for (BinaryBasicBlock *BB : successors()) {
     if (BB->getLabel() == Label)
       return *BI;

bolt/lib/Core/BinaryFunction.cpp

if (CalleeBF) {
     // Absolute symbol.
     ErrorOr<uint64_t> CalleeAddressOrError = BC.getSymbolValue(*CalleeSymbol);
     assert(CalleeAddressOrError && "unregistered symbol found");
     return *CalleeAddressOrError > getAddress();
   }
 }
 
 void BinaryFunction::dump(bool PrintInstructions) const {
-  print(dbgs(), "", PrintInstructions);
+  // getDynoStats calls FunctionLayout::updateLayoutIndices and
+  // BasicBlock::analyzeBranch. The former cannot be const, but should be
+  // removed, the latter should be made const, but seems to require refactoring.
+  // Forcing all callers to have a non-const reference to BinaryFunction to call
+  // dump non-const however is not ideal either. Adding this const_cast is right
+  // now the best solution. It is safe, because BinaryFunction itself is not
+  // modified. Only BinaryBasicBlocks are actually modified (if it all) and we
+  // have mutable pointers to those regardless whether this function is
+  // const-qualified or not.
+  const_cast<BinaryFunction &>(*this).print(dbgs(), "", PrintInstructions);
 }
 
 void BinaryFunction::print(raw_ostream &OS, std::string Annotation,
-                           bool PrintInstructions) const {
+                           bool PrintInstructions) {
   if (!opts::shouldPrint(*this))
     return;
 
   StringRef SectionName =
       OriginSection ? OriginSection->getName() : "<no origin section>";
   OS << "Binary Function \"" << *this << "\" " << Annotation << " {";
   std::vector<StringRef> AllNames = getNames();
   if (AllNames.size() > 1) {

 
 size_t BinaryFunction::computeHash(bool UseDFS,
                                    OperandHashFuncTy OperandHashFunc) const {
   if (size() == 0)
     return 0;
 
   assert(hasCFG() && "function is expected to have CFG");
 
-  BasicBlockListType Order;
+  SmallVector<const BinaryBasicBlock *, 0> Order;
   if (UseDFS)
-    Order = dfs();
+    llvm::copy(dfs(), std::back_inserter(Order));
   else
     llvm::copy(Layout.blocks(), std::back_inserter(Order));
 
   // The hash is computed by creating a string of all instruction opcodes and
   // possibly their operands and then hashing that string with std::hash.
   std::string HashString;
   for (const BinaryBasicBlock *BB : Order) {
     for (const MCInst &Inst : *BB) {

bolt/lib/Core/DynoStats.cpp

if (I == OpcodeHistogram.end()) {
           MMap.erase(First);
         }
         MMap.emplace(*Iter);
       }
     }
   }
 }
 
-DynoStats getDynoStats(const BinaryFunction &BF) {
+DynoStats getDynoStats(BinaryFunction &BF) {
   auto &BC = BF.getBinaryContext();
 
   DynoStats Stats(/*PrintAArch64Stats*/ BC.isAArch64());
 
   // Return empty-stats about the function we don't completely understand.
   if (!BF.isSimple() || !BF.hasValidProfile() || !BF.hasCanonicalCFG())
     return Stats;
 

bolt/lib/Passes/AsmDump.cpp

OS << "# FDATA: 0 [unknown] 0 "
        << "0 " << EntryExecCount << '\n';
 
   // Binary data references from the function.
   std::unordered_set<const BinaryData *> BDReferences;
   // Function references from the function (to avoid constructing call graph).
   std::unordered_set<const MCSymbol *> CallReferences;
 
   MAP->OutStreamer->emitCFIStartProc(/*IsSimple=*/false);
-  for (BinaryBasicBlock *BB : BF.getLayout().blocks()) {
+  for (const BinaryBasicBlock *BB : BF.getLayout().blocks()) {
     OS << BB->getName() << ": \n";
 
     const std::string BranchLabel = Twine(BB->getName(), "_br").str();
     const MCInst *LastInst = BB->getLastNonPseudoInstr();
 
     for (const MCInst &Instr : *BB) {
       // Dump pseudo instructions (CFI)
       if (BC.MIB->isPseudo(Instr)) {

bolt/lib/Passes/BinaryPasses.cpp

if (opts::Verbosity >= 1) {
            ++SFI, ++I)
         outs() << "  " << **SFI << " : " << (*SFI)->getExecutionCount() << '\n';
     }
   }
 
   if (!opts::PrintSortedBy.empty() &&
       !llvm::is_contained(opts::PrintSortedBy, DynoStats::FIRST_DYNO_STAT)) {
 
-    std::vector<const BinaryFunction *> Functions;
+    std::vector<BinaryFunction *> Functions;
     std::map<const BinaryFunction *, DynoStats> Stats;
 
-    for (const auto &BFI : BC.getBinaryFunctions()) {
-      const BinaryFunction &BF = BFI.second;
+    for (auto &BFI : BC.getBinaryFunctions()) {
+      BinaryFunction &BF = BFI.second;
       if (shouldOptimize(BF) && BF.hasValidProfile()) {
         Functions.push_back(&BF);
         Stats.emplace(&BF, getDynoStats(BF));
       }
     }
 
     const bool SortAll =
         llvm::is_contained(opts::PrintSortedBy, DynoStats::LAST_DYNO_STAT);
if (BC.MissedMacroFusionPairs) {
     case MFT_ALL:
       outs() << " that are going to be fixed\n";
       break;
     }
   }
 
   // Collect and print information about suboptimal code layout on input.
   if (opts::ReportBadLayout) {
-    std::vector<const BinaryFunction *> SuboptimalFuncs;
+    std::vector<BinaryFunction *> SuboptimalFuncs;
     for (auto &BFI : BC.getBinaryFunctions()) {
-      const BinaryFunction &BF = BFI.second;
+      BinaryFunction &BF = BFI.second;
       if (!BF.hasValidProfile())
         continue;
 
       const uint64_t HotThreshold =
           std::max<uint64_t>(BF.getKnownExecutionCount(), 1);
       bool HotSeen = false;
       for (const BinaryBasicBlock *BB : BF.getLayout().rblocks()) {
         if (!HotSeen && BB->getKnownExecutionCount() > HotThreshold) {

bolt/lib/Passes/CacheMetrics.cpp

 /// Build a simplified version of the call graph: For every function, keep
 /// its callers and the frequencies of the calls
 std::unordered_map<const BinaryFunction *, Predecessors>
 extractFunctionCalls(const std::vector<BinaryFunction *> &BinaryFunctions) {
   std::unordered_map<const BinaryFunction *, Predecessors> Calls;
 
   for (BinaryFunction *SrcFunction : BinaryFunctions) {
     const BinaryContext &BC = SrcFunction->getBinaryContext();
-    for (BinaryBasicBlock *BB : SrcFunction->getLayout().blocks()) {
+    for (const BinaryBasicBlock *BB : SrcFunction->getLayout().blocks()) {
       // Find call instructions and extract target symbols from each one
-      for (MCInst &Inst : *BB) {
+      for (const MCInst &Inst : *BB) {
         if (!BC.MIB->isCall(Inst))
           continue;
 
         // Call info
         const MCSymbol *DstSym = BC.MIB->getTargetSymbol(Inst);
         uint64_t Count = BB->getKnownExecutionCount();
         // Ignore calls w/o information
         if (DstSym == nullptr || Count == 0)

bolt/lib/Passes/ExtTSPReorderAlgorithm.cpp

bool compareChainPairs(const Chain *A1, const Chain *B1, const Chain *A2,
 
   // Making the order deterministic
   if (A1 != A2)
     return A1->id() < A2->id();
   return B1->id() < B2->id();
 }
 class ExtTSP {
 public:
-  ExtTSP(const BinaryFunction &BF) : BF(BF) { initialize(); }
+  ExtTSP(BinaryFunction &BF) : BF(BF) { initialize(); }
 
   /// Run the algorithm and return an ordering of basic block
   void run(BinaryFunction::BasicBlockOrderType &Order) {
     // Pass 1: Merge blocks with their fallthrough successors
     mergeFallthroughs();
 
     // Pass 2: Merge pairs of chains while improving the ExtTSP objective
     mergeChainPairs();
void concatChains(BinaryFunction::BasicBlockOrderType &Order) {
     Order.reserve(BF.getLayout().block_size());
     for (Chain *Chain : SortedChains)
       for (Block *Block : Chain->blocks())
         Order.push_back(Block->BB);
   }
 
 private:
   // The binary function
-  const BinaryFunction &BF;
+  BinaryFunction &BF;
 
   // All CFG nodes (basic blocks)
   std::vector<Block> AllBlocks;
 
   // All chains of blocks
   std::vector<Chain> AllChains;
 
   // Active chains. The vector gets updated at runtime when chains are merged
   std::vector<Chain *> HotChains;
 
   // All edges between chains
   std::vector<Edge> AllEdges;
 };
 
-void ExtTSPReorderAlgorithm::reorderBasicBlocks(const BinaryFunction &BF,
+void ExtTSPReorderAlgorithm::reorderBasicBlocks(BinaryFunction &BF,
                                                 BasicBlockOrder &Order) const {
   if (BF.getLayout().block_empty())
     return;
 
   // Do not change layout of functions w/o profile information
   if (!BF.hasValidProfile() || BF.getLayout().block_size() <= 2) {
     for (BinaryBasicBlock *BB : BF.getLayout().blocks())
       Order.push_back(BB);

bolt/lib/Passes/IdenticalCodeFolding.cpp

 //===- bolt/Passes/IdenticalCodeFolding.cpp -------------------------------===//
 //
 // 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 the IdenticalCodeFolding class.
 //
 //===----------------------------------------------------------------------===//
 
 #include "bolt/Passes/IdenticalCodeFolding.h"
 #include "bolt/Core/ParallelUtilities.h"
+#include "llvm/ADT/SmallVector.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/ThreadPool.h"
 #include "llvm/Support/Timer.h"
 #include <atomic>
+#include <iterator>
 #include <map>
 #include <set>
 #include <unordered_map>
 
 #define DEBUG_TYPE "bolt-icf"
 
 using namespace llvm;
 using namespace bolt;
bool isIdenticalWith(const BinaryFunction &A, const BinaryFunction &B,
   // Comparing multi-entry functions could be non-trivial.
   if (A.isMultiEntry() || B.isMultiEntry())
     return false;
 
   if (A.hasIslandsInfo() || B.hasIslandsInfo())
     return false;
 
   // Process both functions in either DFS or existing order.
-  const BinaryFunction::BasicBlockOrderType OrderA =
-      opts::UseDFS
-          ? A.dfs()
-          : BinaryFunction::BasicBlockOrderType(A.getLayout().block_begin(),
-                                                A.getLayout().block_end());
-  const BinaryFunction::BasicBlockOrderType OrderB =
-      opts::UseDFS
-          ? B.dfs()
-          : BinaryFunction::BasicBlockOrderType(B.getLayout().block_begin(),
-                                                B.getLayout().block_end());
+  SmallVector<const BinaryBasicBlock *, 0> OrderA;
+  SmallVector<const BinaryBasicBlock *, 0> OrderB;
+  if (opts::UseDFS) {
+    copy(A.dfs(), std::back_inserter(OrderA));
+    copy(B.dfs(), std::back_inserter(OrderB));
+  } else {
+    copy(A.getLayout().blocks(), std::back_inserter(OrderA));
+    copy(B.getLayout().blocks(), std::back_inserter(OrderB));
+  }
 
   const BinaryContext &BC = A.getBinaryContext();
 
   auto BBI = OrderB.begin();
   for (const BinaryBasicBlock *BB : OrderA) {
     const BinaryBasicBlock *OtherBB = *BBI;
 
     if (BB->getLayoutIndex() != OtherBB->getLayoutIndex())

bolt/lib/Passes/ReorderAlgorithm.cpp

void ClusterAlgorithm::computeClusterAverageFrequency(const BinaryContext &BC) {
   BinaryContext::IndependentCodeEmitter Emitter;
   if (!opts::NoThreads)
     Emitter = BC.createIndependentMCCodeEmitter();
 
   AvgFreq.resize(Clusters.size(), 0.0);
   for (uint32_t I = 0, E = Clusters.size(); I < E; ++I) {
     double Freq = 0.0;
     uint64_t ClusterSize = 0;
-    for (BinaryBasicBlock *BB : Clusters[I]) {
+    for (const BinaryBasicBlock *BB : Clusters[I]) {
       if (BB->getNumNonPseudos() > 0) {
         Freq += BB->getExecutionCount();
         // Estimate the size of a block in bytes at run time
         // NOTE: This might be inaccurate
         ClusterSize += BB->estimateSize(Emitter.MCE.get());
       }
     }
     AvgFreq[I] = ClusterSize == 0 ? 0 : Freq / ClusterSize;
   }
 }
 
 void ClusterAlgorithm::printClusters() const {
   for (uint32_t I = 0, E = Clusters.size(); I < E; ++I) {
     errs() << "Cluster number " << I;
     if (AvgFreq.size() == Clusters.size())
       errs() << " (frequency: " << AvgFreq[I] << ")";
     errs() << " : ";
     const char *Sep = "";
-    for (BinaryBasicBlock *BB : Clusters[I]) {
+    for (const BinaryBasicBlock *BB : Clusters[I]) {
       errs() << Sep << BB->getName();
       Sep = ", ";
     }
     errs() << "\n";
   }
 }
 
 void ClusterAlgorithm::reset() {
size_t GreedyClusterAlgorithm::EdgeHash::operator()(const EdgeTy &E) const {
   return Hasher(std::make_pair(E.Src, E.Dst));
 }
 
 bool GreedyClusterAlgorithm::EdgeEqual::operator()(const EdgeTy &A,
                                                    const EdgeTy &B) const {
   return A.Src == B.Src && A.Dst == B.Dst;
 }
 
-void GreedyClusterAlgorithm::clusterBasicBlocks(const BinaryFunction &BF,
+void GreedyClusterAlgorithm::clusterBasicBlocks(BinaryFunction &BF,
                                                 bool ComputeEdges) {
   reset();
 
   // Greedy heuristic implementation for the TSP, applied to BB layout. Try to
   // maximize weight during a path traversing all BBs. In this way, we will
   // convert the hottest branches into fall-throughs.
 
   // This is the queue of edges from which we will pop edges and use them to
for (BinaryBasicBlock *BB : BF.getLayout().blocks()) {
     // Create a cluster for this BB.
     uint32_t I = Clusters.size();
     Clusters.emplace_back();
     std::vector<BinaryBasicBlock *> &Cluster = Clusters.back();
     Cluster.push_back(BB);
     BBToClusterMap[BB] = I;
     // Populate priority queue with edges.
     auto BI = BB->branch_info_begin();
-    for (BinaryBasicBlock *&I : BB->successors()) {
+    for (const BinaryBasicBlock *I : BB->successors()) {
       assert(BI->Count != BinaryBasicBlock::COUNT_NO_PROFILE &&
              "attempted reordering blocks of function with no profile data");
       Queue.emplace_back(EdgeTy(BB, I, BI->Count));
       ++BI;
     }
   }
   // Sort and adjust the edge queue.
   initQueue(Queue, BF);
if (I == J) {
       continue;
     }
 
     std::vector<BinaryBasicBlock *> &ClusterA = Clusters[I];
     std::vector<BinaryBasicBlock *> &ClusterB = Clusters[J];
     if (areClustersCompatible(ClusterA, ClusterB, E)) {
       // Case 3: SrcBB is at the end of a cluster and DstBB is at the start,
       // allowing us to merge two clusters.
-      for (BinaryBasicBlock *BB : ClusterB)
+      for (const BinaryBasicBlock *BB : ClusterB)
         BBToClusterMap[BB] = I;
       ClusterA.insert(ClusterA.end(), ClusterB.begin(), ClusterB.end());
       ClusterB.clear();
       if (ComputeEdges) {
         // Increase the intra-cluster edge count of cluster A with the count of
         // this edge as well as with the total count of previously visited edges
         // from cluster B cluster A.
         ClusterEdges[I][I] += E.Count;
bool MinBranchGreedyClusterAlgorithm::areClustersCompatible(
   return Front.back() == E.Src && Back.front() == E.Dst;
 }
 
 void MinBranchGreedyClusterAlgorithm::reset() {
   GreedyClusterAlgorithm::reset();
   Weight.clear();
 }
 
-void TSPReorderAlgorithm::reorderBasicBlocks(const BinaryFunction &BF,
+void TSPReorderAlgorithm::reorderBasicBlocks(BinaryFunction &BF,
                                              BasicBlockOrder &Order) const {
   std::vector<std::vector<uint64_t>> Weight;
   std::vector<BinaryBasicBlock *> IndexToBB;
 
   const size_t N = BF.getLayout().block_size();
   assert(N <= std::numeric_limits<uint64_t>::digits &&
          "cannot use TSP solution for sizes larger than bits in uint64_t");
 
   // Populating weight map and index map
   for (BinaryBasicBlock *BB : BF.getLayout().blocks()) {
     BB->setLayoutIndex(IndexToBB.size());
     IndexToBB.push_back(BB);
   }
   Weight.resize(N);
-  for (BinaryBasicBlock *BB : BF.getLayout().blocks()) {
+  for (const BinaryBasicBlock *BB : BF.getLayout().blocks()) {
     auto BI = BB->branch_info_begin();
     Weight[BB->getLayoutIndex()].resize(N);
     for (BinaryBasicBlock *SuccBB : BB->successors()) {
       if (BI->Count != BinaryBasicBlock::COUNT_NO_PROFILE)
         Weight[BB->getLayoutIndex()][SuccBB->getLayoutIndex()] = BI->Count;
       ++BI;
     }
   }
void TSPReorderAlgorithm::reorderBasicBlocks(BinaryFunction &BF,
   // Finalize layout with BBs that weren't assigned to the layout using the
   // input layout.
   for (BinaryBasicBlock *BB : BF.getLayout().blocks())
     if (Visited[BB->getLayoutIndex()] == false)
       Order.push_back(BB);
 }
 
 void OptimizeReorderAlgorithm::reorderBasicBlocks(
-    const BinaryFunction &BF, BasicBlockOrder &Order) const {
+    BinaryFunction &BF, BasicBlockOrder &Order) const {
   if (BF.getLayout().block_empty())
     return;
 
   // Cluster basic blocks.
   CAlgo->clusterBasicBlocks(BF);
 
   if (opts::PrintClusters)
     CAlgo->printClusters();
 
   // Arrange basic blocks according to clusters.
   for (ClusterAlgorithm::ClusterTy &Cluster : CAlgo->Clusters)
     Order.insert(Order.end(), Cluster.begin(), Cluster.end());
 }
 
 void OptimizeBranchReorderAlgorithm::reorderBasicBlocks(
-    const BinaryFunction &BF, BasicBlockOrder &Order) const {
+    BinaryFunction &BF, BasicBlockOrder &Order) const {
   if (BF.getLayout().block_empty())
     return;
 
   // Cluster basic blocks.
   CAlgo->clusterBasicBlocks(BF, /* ComputeEdges = */ true);
   std::vector<ClusterAlgorithm::ClusterTy> &Clusters = CAlgo->Clusters;
   std::vector<std::unordered_map<uint32_t, uint64_t>> &ClusterEdges =
       CAlgo->ClusterEdges;
void OptimizeBranchReorderAlgorithm::reorderBasicBlocks(
   // Arrange basic blocks according to cluster order.
   for (uint32_t ClusterIndex : ClusterOrder) {
     ClusterAlgorithm::ClusterTy &Cluster = Clusters[ClusterIndex];
     Order.insert(Order.end(), Cluster.begin(), Cluster.end());
   }
 }
 
 void OptimizeCacheReorderAlgorithm::reorderBasicBlocks(
-    const BinaryFunction &BF, BasicBlockOrder &Order) const {
+    BinaryFunction &BF, BasicBlockOrder &Order) const {
   if (BF.getLayout().block_empty())
     return;
 
   const uint64_t ColdThreshold =
       opts::ColdThreshold *
       (*BF.getLayout().block_begin())->getExecutionCount() / 1000;
 
   // Cluster basic blocks.
for (uint32_t ClusterIndex : ClusterOrder) {
     // Force zero execution count on clusters that do not meet the cut off
     // specified by --cold-threshold.
     if (AvgFreq[ClusterIndex] < static_cast<double>(ColdThreshold))
       for (BinaryBasicBlock *BBPtr : Cluster)
         BBPtr->setExecutionCount(0);
   }
 }
 
-void ReverseReorderAlgorithm::reorderBasicBlocks(const BinaryFunction &BF,
+void ReverseReorderAlgorithm::reorderBasicBlocks(BinaryFunction &BF,
                                                  BasicBlockOrder &Order) const {
   if (BF.getLayout().block_empty())
     return;
 
   BinaryBasicBlock *FirstBB = *BF.getLayout().block_begin();
   Order.push_back(FirstBB);
   for (auto RLI = BF.getLayout().block_rbegin(); *RLI != FirstBB; ++RLI)
     Order.push_back(*RLI);
 }
 
 void RandomClusterReorderAlgorithm::reorderBasicBlocks(
-    const BinaryFunction &BF, BasicBlockOrder &Order) const {
+    BinaryFunction &BF, BasicBlockOrder &Order) const {
   if (BF.getLayout().block_empty())
     return;
 
   // Cluster basic blocks.
   CAlgo->clusterBasicBlocks(BF);
   std::vector<ClusterAlgorithm::ClusterTy> &Clusters = CAlgo->Clusters;
 
   if (opts::PrintClusters)

bolt/lib/Passes/StokeInfo.cpp

if (NameVec)
       NameVec->insert(std::string(BC.MRI->getName(RegIdx)));
   }
   LLVM_DEBUG(dbgs() << "\n");
 }
 
 void StokeInfo::checkInstr(const BinaryFunction &BF, StokeFuncInfo &FuncInfo) {
   MCPlusBuilder *MIB = BF.getBinaryContext().MIB.get();
   BitVector RegV(NumRegs, false);
-  for (BinaryBasicBlock *BB : BF.getLayout().blocks()) {
+  for (const BinaryBasicBlock *BB : BF.getLayout().blocks()) {
     if (BB->empty())
       continue;
 
-    for (MCInst &It : *BB) {
+    for (const MCInst &It : *BB) {
       if (MIB->isPseudo(It))
         continue;
       // skip function with exception handling yet
       if (MIB->isEHLabel(It) || MIB->isInvoke(It)) {
         FuncInfo.Omitted = true;
         return;
       }
       // check if this function contains call instruction

bolt/lib/Profile/DataAggregator.cpp

bool DataAggregator::recordTrace(
 
   // Offsets of the trace within this function.
   const uint64_t From = FirstLBR.To - BF.getAddress();
   const uint64_t To = SecondLBR.From - BF.getAddress();
 
   if (From > To)
     return false;
 
-  BinaryBasicBlock *FromBB = BF.getBasicBlockContainingOffset(From);
-  BinaryBasicBlock *ToBB = BF.getBasicBlockContainingOffset(To);
+  const BinaryBasicBlock *FromBB = BF.getBasicBlockContainingOffset(From);
+  const BinaryBasicBlock *ToBB = BF.getBasicBlockContainingOffset(To);
 
   if (!FromBB || !ToBB)
     return false;
 
   // Adjust FromBB if the first LBR is a return from the last instruction in
   // the previous block (that instruction should be a call).
   if (From == FromBB->getOffset() && !BF.containsAddress(FirstLBR.From) &&
       !FromBB->isEntryPoint() && !FromBB->isLandingPad()) {
-    BinaryBasicBlock *PrevBB = BF.getLayout().getBlock(FromBB->getIndex() - 1);
+    const BinaryBasicBlock *PrevBB =
+        BF.getLayout().getBlock(FromBB->getIndex() - 1);
     if (PrevBB->getSuccessor(FromBB->getLabel())) {
       const MCInst *Instr = PrevBB->getLastNonPseudoInstr();
       if (Instr && BC.MIB->isCall(*Instr))
         FromBB = PrevBB;
       else
         LLVM_DEBUG(dbgs() << "invalid incoming LBR (no call): " << FirstLBR
                           << '\n');
     } else {

bolt/lib/Profile/DataReader.cpp

void DataReader::convertBranchData(BinaryFunction &BF) const {
   }
 }
 
 bool DataReader::recordBranch(BinaryFunction &BF, uint64_t From, uint64_t To,
                               uint64_t Count, uint64_t Mispreds) const {
   BinaryContext &BC = BF.getBinaryContext();
 
   BinaryBasicBlock *FromBB = BF.getBasicBlockContainingOffset(From);
-  BinaryBasicBlock *ToBB = BF.getBasicBlockContainingOffset(To);
+  const BinaryBasicBlock *ToBB = BF.getBasicBlockContainingOffset(To);
 
   if (!FromBB || !ToBB) {
     LLVM_DEBUG(dbgs() << "failed to get block for recorded branch\n");
     return false;
   }
 
   // Could be bad LBR data; ignore the branch. In the case of data collected
   // in binaries optimized by BOLT, a source BB may be mapped to two output
for (std::pair<uint32_t, uint32_t> &Branch : BF.IgnoredBranches)
     if (Branch ==
         std::make_pair(static_cast<uint32_t>(From), static_cast<uint32_t>(To)))
       return true;
 
   bool OffsetMatches = !!(To == ToBB->getOffset());
   if (!OffsetMatches) {
     // Skip the nops to support old .fdata
     uint64_t Offset = ToBB->getOffset();
-    for (MCInst &Instr : *ToBB) {
+    for (const MCInst &Instr : *ToBB) {
       if (!BC.MIB->isNoop(Instr))
         break;
 
       Offset += BC.MIB->getAnnotationWithDefault<uint32_t>(Instr, "Size");
     }
 
     if (To == Offset)
       OffsetMatches = true;
if (LastInstr) {
                           << '\n');
         return false;
       }
     }
 
     // The real destination is the layout successor of the detected ToBB.
     if (ToBB == BF.getLayout().block_back())
       return false;
-    BinaryBasicBlock *NextBB = BF.getLayout().getBlock(ToBB->getIndex() + 1);
+    const BinaryBasicBlock *NextBB =
+        BF.getLayout().getBlock(ToBB->getIndex() + 1);
     assert((NextBB && NextBB->getOffset() > ToBB->getOffset()) && "bad layout");
     ToBB = NextBB;
   }
 
   // If there's no corresponding instruction for 'From', we have probably
   // discarded it as a FT from __builtin_unreachable.
   MCInst *FromInstruction = BF.getInstructionAtOffset(From);
   if (!FromInstruction) {

bolt/lib/Rewrite/BoltDiff.cpp

double getNormalizedScore(const BinaryBasicBlock &BB,
                             const RewriteInstance &Ctx) {
     if (!opts::NormalizeByBin1)
       return static_cast<double>(BB.getKnownExecutionCount()) /
              Ctx.getTotalScore();
     return static_cast<double>(BB.getKnownExecutionCount()) /
            RI1.getTotalScore();
   }
 
-  double getNormalizedScore(BinaryBasicBlock::branch_info_iterator BIIter,
+  double getNormalizedScore(BinaryBasicBlock::const_branch_info_iterator BIIter,
                             const RewriteInstance &Ctx) {
     double Score =
         BIIter->Count == BinaryBasicBlock::COUNT_NO_PROFILE ? 0 : BIIter->Count;
     if (!opts::NormalizeByBin1)
       return Score / Ctx.getTotalScore();
     return Score / RI1.getTotalScore();
   }