From 61972054f3fcaf59096799342bac9c93dd9aa432 Mon Sep 17 00:00:00 2001 From: Alexis Engelke Date: Fri, 20 Jun 2025 11:23:00 +0200 Subject: [CodeGen] Limit number of analyzed predecessors MachineBlockPlacement has quadratic runtime in the number of predecessors: in some situation, for an edge, all predecessors of the successor are considered. Limit the number of considered predecessors to bound compile time for large functions. Pull Request: https://github.com/llvm/llvm-project/pull/142584 --- llvm/lib/CodeGen/MachineBlockPlacement.cpp | 16 ++++++++++++++++ 1 file changed, 16 insertions(+) (limited to 'llvm/lib/CodeGen/MachineBlockPlacement.cpp') diff --git a/llvm/lib/CodeGen/MachineBlockPlacement.cpp b/llvm/lib/CodeGen/MachineBlockPlacement.cpp index 08fe3d47e2ff..2dbabfe345d5 100644 --- a/llvm/lib/CodeGen/MachineBlockPlacement.cpp +++ b/llvm/lib/CodeGen/MachineBlockPlacement.cpp @@ -104,6 +104,12 @@ static cl::opt MaxBytesForAlignmentOverride( "alignment"), cl::init(0), cl::Hidden); +static cl::opt PredecessorLimit( + "block-placement-predecessor-limit", + cl::desc("For blocks with more predecessors, certain layout optimizations" + "will be disabled to prevent quadratic compile time."), + cl::init(1000), cl::Hidden); + // FIXME: Find a good default for this flag and remove the flag. static cl::opt ExitBlockBias( "block-placement-exit-block-bias", @@ -1030,6 +1036,11 @@ bool MachineBlockPlacement::isTrellis( SmallPtrSet SeenPreds; for (MachineBasicBlock *Succ : ViableSuccs) { + // Compile-time optimization: runtime is quadratic in the number of + // predecessors. For such uncommon cases, exit early. + if (Succ->pred_size() > PredecessorLimit) + return false; + int PredCount = 0; for (auto *SuccPred : Succ->predecessors()) { // Allow triangle successors, but don't count them. @@ -1472,6 +1483,11 @@ bool MachineBlockPlacement::hasBetterLayoutPredecessor( if (SuccChain.UnscheduledPredecessors == 0) return false; + // Compile-time optimization: runtime is quadratic in the number of + // predecessors. For such uncommon cases, exit early. + if (Succ->pred_size() > PredecessorLimit) + return false; + // There are two basic scenarios here: // ------------------------------------- // Case 1: triangular shape CFG (if-then): -- cgit v1.2.3