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

73

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/Transforms/Utils/CodeLayout.cpp

 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,