From 04be7a990d4bd24792d891bda51ce42432f31bbb Mon Sep 17 00:00:00 2001 From: Andy Ayers Date: Sun, 6 Mar 2022 08:27:35 -0800 Subject: [PATCH] JIT: fix scalability issue in redundant branch optimizer (#66259) 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. --- 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 e87cf76..ecd1f6c 100644 --- a/src/coreclr/jit/redundantbranchopts.cpp +++ b/src/coreclr/jit/redundantbranchopts.cpp @@ -107,9 +107,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) { @@ -164,6 +166,16 @@ bool Compiler::optRedundantBranch(BasicBlock* const block) // if (matched) { + // 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.7.4