JIT: speed up fgComputePreds (#35352)
authorAndy Ayers <andya@microsoft.com>
Fri, 24 Apr 2020 19:20:13 +0000 (12:20 -0700)
committerGitHub <noreply@github.com>
Fri, 24 Apr 2020 19:20:13 +0000 (12:20 -0700)
commitaf36c6d6cd4e8648f143d0571de776bd6dacb8e0
treed2814c3357980cc23ac1d4e8682d7774b3ed5b33
parenta8476a150aed0175b2fadbd86508c39e7247bfe9
JIT: speed up fgComputePreds (#35352)

Interaction of `fgComputePreds` and `fgAddRefPred` could be quadratic in the
number of preds.

Usually the number of preds is small (1 or 2) but in some cases seen from
compiled regular expressions it could be in the thousands. On one such case
a single call to fgComputePreds was taking ~20% of jit time.

Since we build the pred list in sorted order we can take advantage of this
to avoid searching the list for potential duplicates in `fgAddRefPred` when
it is called from `fgComputePreds` -- the only possible duplicate entry is
at the end of the list.

This doesn't address perf of subsequent calls to `fgAddRefPred` but likely
those happen somewhat randomly and are unlikely to be as costly.
src/coreclr/src/jit/block.h
src/coreclr/src/jit/flowgraph.cpp