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