Handle KilledRegisters more efficiently in LinearScan::processKills()

[DeepakRajendrakumaran]

LinearScan::processKills() accounts for a good percentage of TP regression when adding additional registers as shown below

Method	InsCountDiff	InsPercentageDiff	ContributionPercentage
processKills@LinearScan	5849967774	114.36%	17.20%

LinearScan::processKills() obtains list of registers using RefPosition->getKilledRegisters(). This currently is a regMaskTP.
We do a number of expensive operations on this regMaskTP in a loop including the following - IsNonEmpty(), genFirstRegNumFromMaskAndToggle(), >=, &=. Explore possibility of storing killedRegisters as a SingleTypeRegSet and thus improve TP.

[jakobbotsch]

A lot of the cost here is coming from the fact that there are more registers to kill, hence the loop iterates many more times. The bit set operations may be a quite small proportion of this.
It would be more interesting to investigate making the "next kill location" lazily updated as we don't expect to need need that for the vast majority of registers.

[DeepakRajendrakumaran]

A lot of the cost here is coming from the fact that there are more registers to kill, hence the loop iterates many more times. The bit set operations may be a quite small proportion of this. It would be more interesting to investigate making the "next kill location" lazily updated as we don't expect to need need that for the vast majority of registers.

Thanks for bringing this up. Kunal mentioned this too. I'll def look into it as well

[jakobbotsch]

I had an attempt at doing that last year (took me a while to find the code): https://github.com/dotnet/runtime/compare/main...jakobbotsch:runtime:lsra-lazy-fixed-ref?expand=1
I did not see the results I was expecting, but it may look better with more registers:

[dotnet-policy-service]

Tagging subscribers to this area: @JulieLeeMSFT, @jakobbotsch
See info in area-owners.md if you want to be subscribed.

[DeepakRajendrakumaran]

I had an attempt at doing that last year (took me a while to find the code): https://github.com/dotnet/runtime/compare/main...jakobbotsch:runtime:lsra-lazy-fixed-ref?expand=1 I did not see the results I was expecting, but it may look better with more registers:

So..I tried porting your changes and testing it out with latest main - 03da3d2

I do see some failures - specifically in some cases we do not resolve conflicts and end up asserting. I'm looking into it now. W.r.t improvements, I want to compare with this as base(This doesn't really add the new registers but is a dummy change which makes regMask bigger that uint64). Some initial tpdiff numbers show that your experiment improves performance but I'm loathe to put up the numbers till I fix the bugs since I can't be sure it's accurate :)