From 3743f5e15f270bd22e26e51b996c9a415496fd09 Mon Sep 17 00:00:00 2001 From: "github-actions[bot]" <41898282+github-actions[bot]@users.noreply.github.com> Date: Fri, 13 May 2022 17:36:21 -0700 Subject: [PATCH] JIT: fix scalability issue in redundant branch optimizer (#68972) In methods with long skinny dominator trees and lots of redundant branches the jit can spend too much time trying to optimize the branches. Place a limit on the number of redundant branches with matching VNs that the jit will consider for a given branch. Fixes #66067. Co-authored-by: Andy Ayers --- src/coreclr/jit/redundantbranchopts.cpp | 18 +++++++++++++++--- 1 file changed, 15 insertions(+), 3 deletions(-) diff --git a/src/coreclr/jit/redundantbranchopts.cpp b/src/coreclr/jit/redundantbranchopts.cpp index 55568c3c743..6c96e96d5f7 100644 --- a/src/coreclr/jit/redundantbranchopts.cpp +++ b/src/coreclr/jit/redundantbranchopts.cpp @@ -106,9 +106,11 @@ bool Compiler::optRedundantBranch(BasicBlock* const block) // Walk up the dom tree and see if any dominating block has branched on // exactly this tree's VN... // - BasicBlock* prevBlock = block; - BasicBlock* domBlock = block->bbIDom; - int relopValue = -1; + BasicBlock* prevBlock = block; + BasicBlock* domBlock = block->bbIDom; + int relopValue = -1; + unsigned matchCount = 0; + const unsigned matchLimit = 4; if (domBlock == nullptr) { @@ -140,6 +142,16 @@ bool Compiler::optRedundantBranch(BasicBlock* const block) // if (domCmpVN == tree->GetVN(VNK_Liberal)) { + // If we have a long skinny dominator tree we may scale poorly, + // and in particular reachability (below) is costly. Give up if + // we've matched a few times and failed to optimize. + // + if (++matchCount > matchLimit) + { + JITDUMP("Bailing out; %d matches found w/o optimizing\n", matchCount); + return false; + } + // The compare in "tree" is redundant. // Is there a unique path from the dominating compare? // -- 2.34.1