Improve LclVar sorting throughput (dotnet/coreclr#23234)
authormikedn <onemihaid@hotmail.com>
Fri, 13 Sep 2019 14:45:05 +0000 (17:45 +0300)
committerCarol Eidt <carol.eidt@microsoft.com>
Fri, 13 Sep 2019 14:45:05 +0000 (07:45 -0700)
commit32a5dd594acd2a64ece357a3a88c0bc7f9432ed7
tree74adf2a7e669c97208db8a0dec496c67336533a3
parentd90f0878001549dec6eadcb4078fbec5f9dc08d0
Improve LclVar sorting throughput (dotnet/coreclr#23234)

* Add tracked variable accessor functions

* Delete bogus lvaSortByRefCount call

There's no need to sort at the end of lvaMarkLocalVars. Tracked variables aren't needed until liveness and that does its own sort call.

* Replace qsort with (jit)std::sort

qsort is rather cumbersome to use and inefficient. It's not a template
so it operates with void pointers that can make swapping problematic.
The comparison callback is unnecessarily complex because it has to return
-1,0,+1 when "less" style comparison functions only return true/false.
It's also impossible to inline the callback, even if it's a trivial
"return a < b;" function.

* Get rid of lvaRefSorted

While it could be slightly faster than lvaTrackedToVarNum because it stores
pointers rather than indices, it also uses more memory and it's not safe to
use beyond sorting. If new variables are added the variable table may have
to be resized and that invalidates the stored pointers.

At the same time, stop sorting untracked variables, nothing in the JIT needs
that. Collect only tracked variables in lvaTrackedToVarNum, sort them and
then "untrack" the ones that exceed the lclMAX_TRACKED limit.

* Remove bogus lvRegister checks

Variables are not sorted after LSRA has ran so these checks are not needed.

* Turn RefCntCmp/WtdRefCntCmp into real "less"

* Use functors rather than lambdas

It's too much code to put it all in the lambda so we might as well go the other way and get rid of the lambda.

* Add some comments to sort functions

* Fix comments

* Change to the real insertion sort

* Fix comments

Commit migrated from https://github.com/dotnet/coreclr/commit/42e810630af30672b000f03f9d265fc683d46f97
12 files changed:
src/coreclr/src/jit/codegencommon.cpp
src/coreclr/src/jit/codegenlinear.cpp
src/coreclr/src/jit/compiler.cpp
src/coreclr/src/jit/compiler.h
src/coreclr/src/jit/jitstd/algorithm.h
src/coreclr/src/jit/lclvars.cpp
src/coreclr/src/jit/liveness.cpp
src/coreclr/src/jit/lsra.cpp
src/coreclr/src/jit/lsrabuild.cpp
src/coreclr/src/jit/optcse.cpp
src/coreclr/src/jit/scopeinfo.cpp
src/coreclr/src/jit/ssabuilder.cpp