[RegAlloc] Add a complexity limit in growRegion() to cap compilation time.

[vporpo]

Summary

growRegion() does not scale in code with BBs with a very large number of edges.
In such code growRegion() becomes a compile-time bottleneck, consuming 60% of
the total compilation time.
This patch adds a limit to the complexity of growRegion() by incrementing a counter
in each iteration. We bail out once the limit is reached.

[vporpo]

Improved the option's description.

[mtrofin]

Nit: can you please rephrase the commit message, last statement: the patch (correctly) doesn't place a limit on time (which would be non-deterministic), rather, it places a limit on the number of Blocks visited (deterministic).

The patch LGTM, but I'm curious, why do we end up with a bazillion edges, like what property do the blocks pointed at the edges have, like are they all going to an exit block, or in any case, is this a meaningful pattern - maybe we could avoid placement via the Hopfield Network, and instead do something simpler (and maybe it benefits the rest of the allocation)?

llvm/lib/CodeGen/RegAllocGreedy.cpp

793

You could just take Visited out of its conditional compilation block and compare it to GrowRegionComplexityBudget. I realize Visited is incremented less often than Budget is currently decremented, but it does achieve the same goal?

[vporpo]

llvm/lib/CodeGen/RegAllocGreedy.cpp

793

Yes, it would be similar I guess, but I think it is probably best to keep the counters separate as their purpose is different.

llvm/lib/CodeGen/RegAllocGreedy.cpp

CSRFirstTimeCost("regalloc-csr-first-time-cost",
               cl::init(0), cl::Hidden);
 
 static cl::opt<bool> ConsiderLocalIntervalCost(
     "consider-local-interval-cost", cl::Hidden,
     cl::desc("Consider the cost of local intervals created by a split "
              "candidate when choosing the best split candidate."),
     cl::init(false));
 
+static cl::opt<long> GrowRegionComplexityBudget(
+    "grow-region-complexity-budget",
+    cl::desc("growRegion() does not scale, so limit its budget. "
+             "Bail out if we explore this many edges."),
+    cl::init(10000), cl::Hidden);
+
 static RegisterRegAlloc greedyRegAlloc("greedy", "greedy register allocator",
                                        createGreedyRegisterAllocator);
 
 char RAGreedy::ID = 0;
 char &llvm::RAGreedyID = RAGreedy::ID;
 
 INITIALIZE_PASS_BEGIN(RAGreedy, "greedy",
                 "Greedy Register Allocator", false, false)
bool RAGreedy::growRegion(GlobalSplitCandidate &Cand) {
   // Keep track of through blocks that have not been added to SpillPlacer.
   BitVector Todo = SA->getThroughBlocks();
   SmallVectorImpl<unsigned> &ActiveBlocks = Cand.ActiveBlocks;
   unsigned AddedTo = 0;
 #ifndef NDEBUG
   unsigned Visited = 0;
 #endif
 
+  long Budget = GrowRegionComplexityBudget;
   while (true) {
     ArrayRef<unsigned> NewBundles = SpillPlacer->getRecentPositive();
     // Find new through blocks in the periphery of PrefRegBundles.
     for (unsigned Bundle : NewBundles) {
       // Look at all blocks connected to Bundle in the full graph.
       ArrayRef<unsigned> Blocks = Bundles->getBlocks(Bundle);
       for (unsigned Block : Blocks) {
+        // Limit compilation time by bailing out after we use all our budget.
+        if (Budget-- == 0)
+          return false;
         if (!Todo.test(Block))
           continue;
         Todo.reset(Block);
         // This is a new through block. Add it to SpillPlacer later.
         ActiveBlocks.push_back(Block);
 #ifndef NDEBUG
         ++Visited;
 #endif