[BOLT] Increase coverage of shrink wrapping [3/5]

[rafauler]

Summary

Add the option to run -equalize-bb-counts before shrink
wrapping to avoid unnecessarily optimizing some CFGs where profile is
inaccurate but we can prove two blocks have the same frequency.

[Amir]

Would it make sense to factor equalizeBBCounts out into a pass or BF method? (can do as a follow-up)

bolt/include/bolt/Passes/MCF.h

 //===- bolt/Passes/MCF.h ----------------------------------------*- 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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef BOLT_PASSES_MCF_H
 #define BOLT_PASSES_MCF_H
 
 namespace llvm {
 namespace bolt {
 
 class BinaryFunction;
+class DataflowInfoManager;
 
 enum MCFCostFunction : char {
   MCF_DISABLE = 0,
   MCF_LINEAR,
   MCF_QUADRATIC,
   MCF_LOG,
   MCF_BLAMEFTS
 };
 
+/// Implement the idea in "SamplePGO - The Power of Profile Guided Optimizations
+/// without the Usability Burden" by Diego Novillo to make basic block counts
+/// equal if we show that A dominates B, B post-dominates A and they are in the
+/// same loop and same loop nesting level.
+void equalizeBBCounts(DataflowInfoManager &Info, BinaryFunction &BF);
+
 /// Fill edge counts based on the basic block count. Used in nonLBR mode when
 /// we only have bb count.
 void estimateEdgeCounts(BinaryFunction &BF);
 
 /// Entry point for computing a min-cost flow for the CFG with the goal
 /// of fixing the flow of the CFG edges, that is, making sure it obeys the
 /// flow-conservation equation  SumInEdges = SumOutEdges.
 ///

bolt/include/bolt/Utils/CommandLineOpts.h

 extern llvm::cl::OptionCategory HeatmapCategory;
 
 extern llvm::cl::opt<unsigned> AlignText;
 extern llvm::cl::opt<unsigned> AlignFunctions;
 extern llvm::cl::opt<bool> AggregateOnly;
 extern llvm::cl::opt<unsigned> BucketsPerLine;
 extern llvm::cl::opt<bool> DiffOnly;
 extern llvm::cl::opt<bool> EnableBAT;
+extern llvm::cl::opt<bool> EqualizeBBCounts;
 extern llvm::cl::opt<bool> RemoveSymtab;
 extern llvm::cl::opt<unsigned> ExecutionCountThreshold;
 extern llvm::cl::opt<unsigned> HeatmapBlock;
 extern llvm::cl::opt<unsigned long long> HeatmapMaxAddress;
 extern llvm::cl::opt<unsigned long long> HeatmapMinAddress;
 extern llvm::cl::opt<bool> HotData;
 extern llvm::cl::opt<bool> HotFunctionsAtEnd;
 extern llvm::cl::opt<bool> HotText;

bolt/lib/Passes/FrameOptimizer.cpp

 
 #include "bolt/Passes/FrameOptimizer.h"
 #include "bolt/Core/ParallelUtilities.h"
 #include "bolt/Passes/BinaryFunctionCallGraph.h"
 #include "bolt/Passes/DataflowInfoManager.h"
 #include "bolt/Passes/ShrinkWrapping.h"
 #include "bolt/Passes/StackAvailableExpressions.h"
 #include "bolt/Passes/StackReachingUses.h"
+#include "bolt/Utils/CommandLineOpts.h"
 #include "llvm/Support/Timer.h"
 #include <deque>
 #include <unordered_map>
 
 #define DEBUG_TYPE "fop"
 
 using namespace llvm;
 

bolt/lib/Passes/MCF.cpp

 //===- bolt/Passes/MCF.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 functions for solving minimum-cost flow problem.
 //
 //===----------------------------------------------------------------------===//
 
 #include "bolt/Passes/MCF.h"
 #include "bolt/Core/BinaryFunction.h"
 #include "bolt/Passes/DataflowInfoManager.h"
+#include "bolt/Utils/CommandLineOpts.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/Support/CommandLine.h"
 #include <algorithm>
 #include <vector>
 
 #undef  DEBUG_TYPE
 #define DEBUG_TYPE "mcf"
 
 using namespace llvm;
 using namespace bolt;
 
 namespace opts {
 
 extern cl::OptionCategory BoltOptCategory;
 
 extern cl::opt<bool> TimeOpts;
 
 static cl::opt<bool> IterativeGuess(
     "iterative-guess",
     cl::desc("in non-LBR mode, guess edge counts using iterative technique"),
-
-    cl::Hidden, cl::cat(BoltOptCategory));
-
-static cl::opt<bool>
-    EqualizeBBCounts("equalize-bb-counts",
-                     cl::desc("in non-LBR mode, use same count for BBs "
-                              "that should have equivalent count"),
-                     cl::Hidden, cl::cat(BoltOptCategory));
 
 static cl::opt<bool> UseRArcs(
     "mcf-use-rarcs",
     cl::desc("in MCF, consider the possibility of cancelling flow to balance "
              "edges"),
     cl::Hidden, cl::cat(BoltOptCategory));
 
 } // namespace opts
createLoopNestLevelMap(BinaryFunction &BF) {
   const BinaryLoopInfo &BLI = BF.getLoopInfo();
 
   for (BinaryBasicBlock &BB : BF)
     LoopNestLevel[&BB] = BLI[&BB];
 
   return LoopNestLevel;
 }
 
-/// Implement the idea in "SamplePGO - The Power of Profile Guided Optimizations
-/// without the Usability Burden" by Diego Novillo to make basic block counts
-/// equal if we show that A dominates B, B post-dominates A and they are in the
-/// same loop and same loop nesting level.
-void equalizeBBCounts(BinaryFunction &BF) {
-  auto Info = DataflowInfoManager(BF, nullptr, nullptr);
+} // end anonymous namespace
+
+void equalizeBBCounts(DataflowInfoManager &Info, BinaryFunction &BF) {
+  if (BF.begin() == BF.end())
+    return;
+
   DominatorAnalysis<false> &DA = Info.getDominatorAnalysis();
   DominatorAnalysis<true> &PDA = Info.getPostDominatorAnalysis();
   auto &InsnToBB = Info.getInsnToBBMap();
   // These analyses work at the instruction granularity, but we really only need
   // basic block granularity here. So we'll use a set of visited edges to avoid
   // revisiting the same BBs again and again.
   DenseMap<const BinaryBasicBlock *, std::set<const BinaryBasicBlock *>>
       Visited;
for (std::vector<BinaryBasicBlock *> &Class : Classes) {
     uint64_t Max = 0ULL;
     for (BinaryBasicBlock *BB : Class)
       Max = std::max(Max, BB->getExecutionCount());
     for (BinaryBasicBlock *BB : Class)
       BB->setExecutionCount(Max);
   }
 }
 
-} // end anonymous namespace
-
 void estimateEdgeCounts(BinaryFunction &BF) {
   EdgeWeightMap PredEdgeWeights;
   EdgeWeightMap SuccEdgeWeights;
   if (!opts::IterativeGuess) {
     computeEdgeWeights<Inverse<BinaryBasicBlock *>>(BF, PredEdgeWeights);
     computeEdgeWeights<BinaryBasicBlock *>(BF, SuccEdgeWeights);
   }
   if (opts::EqualizeBBCounts) {
     LLVM_DEBUG(BF.print(dbgs(), "before equalize BB counts", true));
-    equalizeBBCounts(BF);
+    auto Info = DataflowInfoManager(BF, nullptr, nullptr);
+    equalizeBBCounts(Info, BF);
     LLVM_DEBUG(BF.print(dbgs(), "after equalize BB counts", true));
   }
   if (opts::IterativeGuess)
     guessEdgeByIterativeApproach(BF);
   else
     guessEdgeByRelHotness(BF, /*UseSuccs=*/false, PredEdgeWeights,
                           SuccEdgeWeights);
   recalculateBBCounts(BF, /*AllEdges=*/false);
 }
 
 void solveMCF(BinaryFunction &BF, MCFCostFunction CostFunction) {
   llvm_unreachable("not implemented");
 }
 
 } // namespace bolt
 } // namespace llvm

bolt/lib/Passes/ShrinkWrapping.cpp

 //===- bolt/Passes/ShrinkWrapping.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 ShrinkWrapping class.
 //
 //===----------------------------------------------------------------------===//
 
 #include "bolt/Passes/ShrinkWrapping.h"
 #include "bolt/Core/MCPlus.h"
 #include "bolt/Passes/DataflowInfoManager.h"
+#include "bolt/Passes/MCF.h"
+#include "bolt/Utils/CommandLineOpts.h"
 #include <numeric>
 #include <stack>
 
 #define DEBUG_TYPE "shrinkwrapping"
 
 using namespace llvm;
 
 namespace opts {
bool ShrinkWrapping::perform(bool HotOnly) {
   StoreDynamicCount += TotalStoreInstrs;
 
   if (!FA.hasFrameInfo(BF))
     return false;
 
   if (HotOnly && (BF.getKnownExecutionCount() < BC.getHotThreshold()))
     return false;
 
+  if (opts::EqualizeBBCounts)
+    equalizeBBCounts(Info, BF);
+
   if (BF.checkForAmbiguousJumpTables()) {
     LLVM_DEBUG(dbgs() << "BOLT-DEBUG: ambiguous JTs in " << BF.getPrintName()
                       << ".\n");
     // We could call disambiguateJumpTables here, but it is probably not worth
     // the cost (of duplicating potentially large jump tables that could regress
     // dcache misses). Moreover, ambiguous JTs are rare and coming from code
     // written in assembly language. Just bail.
     return false;

bolt/lib/Utils/CommandLineOpts.cpp

 
 cl::opt<bool>
 EnableBAT("enable-bat",
   cl::desc("write BOLT Address Translation tables"),
   cl::init(false),
   cl::ZeroOrMore,
   cl::cat(BoltCategory));
 
+cl::opt<bool> EqualizeBBCounts(
+    "equalize-bb-counts",
+    cl::desc("use same count for BBs that should have equivalent count (used "
+             "in non-LBR and shrink wrapping)"),
+    cl::ZeroOrMore, cl::init(false), cl::Hidden, cl::cat(BoltOptCategory));
+
 cl::opt<bool> RemoveSymtab("remove-symtab", cl::desc("Remove .symtab section"),
                            cl::cat(BoltCategory));
 
 cl::opt<unsigned>
 ExecutionCountThreshold("execution-count-threshold",
   cl::desc("perform profiling accuracy-sensitive optimizations only if "
            "function execution count >= the threshold (default: 0)"),
   cl::init(0),

bolt/test/X86/shrinkwrapping-do-not-pessimize.s

+# This checks that shrink wrapping does not pessimize a CFG pattern where two
+# blocks can be proved to have the same execution count but, because of profile
+# inaccuricies, we could move saves into the second block. We can prove two
+# blocks have the same frequency when B post-dominate A and A dominates B and
+# are at the same loop nesting level. This would be a pessimization because
+# shrink wrapping is unlikely to be able to cleanly move PUSH instructions,
+# inserting additional store instructions.
+
+# REQUIRES: system-linux
+
+# RUN: llvm-mc -filetype=obj -triple x86_64-unknown-unknown \
+# RUN:   %s -o %t.o
+# RUN: link_fdata %s %t.o %t.fdata
+# RUN: llvm-strip --strip-unneeded %t.o
+# RUN: %clang %cflags %t.o -o %t.exe -Wl,-q -nostdlib
+# RUN: llvm-bolt -relocs %t.exe -o %t.out -data %t.fdata \
+# RUN:     -frame-opt=all -equalize-bb-counts | FileCheck %s
+
+# Here we create a CFG pattern with two blocks A and B belonging to the same
+# equivalency class as defined by dominance relations and having in theory
+# the same frequency. But we tweak edge counts from profile to make block A
+# hotter than block B.
+  .globl _start
+  .type _start, %function
+_start:
+  .cfi_startproc
+# Hot prologue
+# FDATA: 0 [unknown] 0 1 _start 0 0 10
+  push  %rbp
+  mov   %rsp, %rbp
+  push  %rbx
+  push  %r14
+  subq  $0x20, %rsp
+b:  je  end_if_1
+# FDATA: 1 _start #b# 1 _start #end_if_1# 0 1
+if_false:
+  movq rel(%rip), %rdi  # Add this to create a relocation and run bolt w/ relocs
+c:  jmp end_if_1
+# Reduce frequency from 9 to 1 to simulate an inaccurate profile
+# FDATA: 1 _start #c# 1 _start #end_if_1# 0 1
+end_if_1:
+  # first uses of R14 and RBX appear at this point, possible move point for SW
+  mov %r14, %rdi
+  mov %rbx, %rdi
+  leaq -0x20(%rbp), %r14
+  movq -0x20(%rbp), %rdi
+  addq  $0x20, %rsp
+  pop %r14
+  pop %rbx
+  pop %rbp
+  ret
+  .cfi_endproc
+  .size _start, .-_start
+
+  .data
+rel:  .quad end_if_1
+
+# CHECK:   BOLT-INFO: Shrink wrapping moved 0 spills inserting load/stores and 0 spills inserting push/pops