speeding up ext-tsp for huge instances

[spupyrev]

Summary

Some (rare) control-flow graphs in datacenter binaries contain many basic
blocks, e.g, >50K. In such cases, the existing implementation might take
up to several hours. This diff introduces a simple flag, MaxChainSize, that
forbid creating chains of blocks exceeding the specified size. When setting
MaxChainSize=4096, the runtime of the alg increase by ~100x on some prod
benchmarks.

Separately introducing an option to disable ext-tsp for function w/o profile
data (OFF by default). If we ever hit a runtime problem, we may turn it ON.

[spupyrev]

minor

[spupyrev]

rename

[wenlei]

When setting MaxChainSize=4096, the runtime of the alg increase by ~100x on some prod benchmarks.

Maybe I'm missing something, setting MaxChainSize=4096 is what this change does, isn't it supposed to reduce runtime of the alg?

llvm/lib/Transforms/Utils/CodeLayout.cpp

78

What's the typical chain size and how often do we actually hit 4096 limit?

[spupyrev]

sorry misspelled increase/decrease

For clang-10 binary, no functions is affected. For the larger prod binary, 2 instances are affected: One is the gigantic with 50K blocks (max chain reaches >30K), another is with 20K blocks (max chain reaches 8K). I suspect it would be safe to set the max bound to 2048 or 1024 without measurable impact on the quality.

[wenlei]

lgtm, thanks.

llvm/lib/CodeGen/MachineBlockPlacement.cpp

 static cl::opt<unsigned> TriangleChainCount(
     "triangle-chain-count",
     cl::desc("Number of triangle-shaped-CFG's that need to be in a row for the "
              "triangle tail duplication heuristic to kick in. 0 to disable."),
     cl::init(2),
     cl::Hidden);
 
 extern cl::opt<bool> EnableExtTspBlockPlacement;
+extern cl::opt<bool> ApplyExtTspWithoutProfile;
 
 namespace llvm {
 extern cl::opt<unsigned> StaticLikelyProb;
 extern cl::opt<unsigned> ProfileLikelyProb;
 
 // Internal option used to control BFI display only after MBP pass.
 // Defined in CodeGen/MachineBlockFrequencyInfo.cpp:
 // -view-block-layout-with-bfi=
if (BF.OptimizeFunction(MF, TII, MF.getSubtarget().getRegisterInfo(), MLI,
       if (MPDT)
         MPDT->runOnMachineFunction(MF);
       ChainAllocator.DestroyAll();
       buildCFGChains();
     }
   }
 
   // Apply a post-processing optimizing block placement.
-  if (MF.size() >= 3 && EnableExtTspBlockPlacement) {
+  if (MF.size() >= 3 && EnableExtTspBlockPlacement &&
+      (ApplyExtTspWithoutProfile || MF.getFunction().hasProfileData())) {
     // Find a new placement and modify the layout of the blocks in the function.
     applyExtTsp();
 
     // Re-create CFG chain so that we can optimizeBranches and alignBlocks.
     createCFGChainExtTsp();
   }
 
   optimizeBranches();

llvm/lib/Transforms/Utils/CodeLayout.cpp

 using namespace llvm;
 #define DEBUG_TYPE "code-layout"
 
 cl::opt<bool> EnableExtTspBlockPlacement(
     "enable-ext-tsp-block-placement", cl::Hidden, cl::init(false),
     cl::desc("Enable machine block placement based on the ext-tsp model, "
              "optimizing I-cache utilization."));
 
+cl::opt<bool> ApplyExtTspWithoutProfile(
+    "ext-tsp-apply-without-profile",
+    cl::desc("Whether to apply ext-tsp placement for instances w/o profile"),
+    cl::init(true), cl::Hidden, cl::ZeroOrMore);
+
 // Algorithm-specific constants. The values are tuned for the best performance
 // of large-scale front-end bound binaries.
 static cl::opt<double>
     ForwardWeight("ext-tsp-forward-weight", cl::Hidden, cl::init(0.1),
                   cl::desc("The weight of forward jumps for ExtTSP value"));
 
 static cl::opt<double>
     BackwardWeight("ext-tsp-backward-weight", cl::Hidden, cl::init(0.1),
                    cl::desc("The weight of backward jumps for ExtTSP value"));
 
 static cl::opt<unsigned> ForwardDistance(
     "ext-tsp-forward-distance", cl::Hidden, cl::init(1024),
     cl::desc("The maximum distance (in bytes) of a forward jump for ExtTSP"));
 
 static cl::opt<unsigned> BackwardDistance(
     "ext-tsp-backward-distance", cl::Hidden, cl::init(640),
     cl::desc("The maximum distance (in bytes) of a backward jump for ExtTSP"));
 
+// The maximum size of a chain created by the algorithm. The size is bounded
+// so that the algorithm can efficiently process extremely large instance.
+static cl::opt<unsigned>
+    MaxChainSize("ext-tsp-max-chain-size", cl::Hidden, cl::init(4096),
+                 cl::desc("The maximum size of a chain to create."));
+
 // The maximum size of a chain for splitting. Larger values of the threshold
 // may yield better quality at the cost of worsen run-time.
 static cl::opt<unsigned> ChainSplitThreshold(
     "ext-tsp-chain-split-threshold", cl::Hidden, cl::init(128),
     cl::desc("The maximum size of a chain to apply splitting"));
 
 // The option enables splitting (large) chains along in-coming and out-going
 // jumps. This typically results in a better quality.
public:
   bool isEntry() const { return Blocks[0]->Index == 0; }
 
   double score() const { return Score; }
 
   void setScore(double NewScore) { Score = NewScore; }
 
   const std::vector<Block *> &blocks() const { return Blocks; }
 
+  size_t numBlocks() const { return Blocks.size(); }
+
   const std::vector<std::pair<Chain *, ChainEdge *>> &edges() const {
     return Edges;
   }
 
   ChainEdge *getEdge(Chain *Other) const {
     for (auto It : Edges) {
       if (It.first == Other)
         return It.second;
for (auto &Block : AllBlocks) {
         HotChains.push_back(&AllChains.back());
       }
     }
 
     // Initialize chain edges
     AllEdges.reserve(AllJumps.size());
     for (auto &Block : AllBlocks) {
       for (auto &Jump : Block.OutJumps) {
-        const auto SuccBlock = Jump->Target;
+        auto SuccBlock = Jump->Target;
         auto CurEdge = Block.CurChain->getEdge(SuccBlock->CurChain);
         // this edge is already present in the graph
         if (CurEdge != nullptr) {
           assert(SuccBlock->CurChain->getEdge(Block.CurChain) != nullptr);
           CurEdge->appendJump(Jump);
           continue;
         }
         // this is a new edge
while (HotChains.size() > 1) {
         // Get candidates for merging with the current chain
         for (auto EdgeIter : ChainPred->edges()) {
           auto ChainSucc = EdgeIter.first;
           auto ChainEdge = EdgeIter.second;
           // Ignore loop edges
           if (ChainPred == ChainSucc)
             continue;
 
+          // Stop early if the combined chain violates the maximum allowed size
+          if (ChainPred->numBlocks() + ChainSucc->numBlocks() >= MaxChainSize)
+            continue;
+
           // Compute the gain of merging the two chains
           auto CurGain = getBestMergeGain(ChainPred, ChainSucc, ChainEdge);
           if (CurGain.score() <= EPS)
             continue;
 
           if (BestGain < CurGain ||
               (std::abs(CurGain.score() - BestGain.score()) < EPS &&
                compareChainPairs(ChainPred, ChainSucc, BestChainPred,