From 6f9640d6a3d57eaa2d0467d94a7b87963fbe53d7 Mon Sep 17 00:00:00 2001 From: Vasileios Porpodas Date: Mon, 28 Feb 2022 22:34:45 -0800 Subject: [PATCH] [RegAlloc] Add a complexity limit in growRegion() to cap compilation time. 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. Differential Revision: https://reviews.llvm.org/D120752 --- llvm/lib/CodeGen/RegAllocGreedy.cpp | 10 ++++++++++ 1 file changed, 10 insertions(+) diff --git a/llvm/lib/CodeGen/RegAllocGreedy.cpp b/llvm/lib/CodeGen/RegAllocGreedy.cpp index 817aeb6..85e11d1 100644 --- a/llvm/lib/CodeGen/RegAllocGreedy.cpp +++ b/llvm/lib/CodeGen/RegAllocGreedy.cpp @@ -133,6 +133,12 @@ static cl::opt ConsiderLocalIntervalCost( "candidate when choosing the best split candidate."), cl::init(false)); +static cl::opt GrowRegionComplexityBudget( + "grow-region-complexity-budget", + cl::desc("growRegion() does not scale with the number of BB edges, so " + "limit its budget and bail out once we reach the limit."), + cl::init(10000), cl::Hidden); + static RegisterRegAlloc greedyRegAlloc("greedy", "greedy register allocator", createGreedyRegisterAllocator); @@ -784,6 +790,7 @@ bool RAGreedy::growRegion(GlobalSplitCandidate &Cand) { unsigned Visited = 0; #endif + long Budget = GrowRegionComplexityBudget; while (true) { ArrayRef NewBundles = SpillPlacer->getRecentPositive(); // Find new through blocks in the periphery of PrefRegBundles. @@ -791,6 +798,9 @@ bool RAGreedy::growRegion(GlobalSplitCandidate &Cand) { // Look at all blocks connected to Bundle in the full graph. ArrayRef 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); -- 2.7.4