Improve allocateRegisters() and allocateRegistersMinimal() by representing and accessing local register sets in a more efficient manner

Open
#112,961 5 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Assessment

Difficulty
4/5
Estimated time
3-5 days
Newbie friendliness
35/100
Issue type
Refactor
Clarity
Mostly clear
Activity status
Stale
Tech stack
cpp
Domain
compilers, performance

Research direction

Start in src/coreclr/jit/lsra.cpp at the allocateRegisters() code around the referenced local register masks, then trace allocateRegistersMinimal() and freeRegisters(). Compare the proposed RegSetMasks representations and inspect how SingleTypeRegSet is used. Done means the affected methods avoid the reported more-than-64-register overhead while preserving register allocation behavior and improving the listed regressions.

Written by the indexing model from the issue text.

Description

area-CodeGen-coreclr

In allocateRegisters() and allocateRegistersMinimal(), we iterate through RefPositions and update regsToFree, delayRegsToFree, regsToMakeInactive, delayRegsToMakeInactive and copyRegsToFree. These are regMaskTP local variables and as such incurs significant regression with more than 64 registers.

This primarily applies to the following

    regMaskTP    regsToFree              = RBM_NONE;
    regMaskTP    delayRegsToFree         = RBM_NONE;
    regMaskTP    regsToMakeInactive      = RBM_NONE;
    regMaskTP    delayRegsToMakeInactive = RBM_NONE;
    regMaskTP    copyRegsToFree          = RBM_NONE;

In order to optimize the operations on these variables, they can be represented by

    struct RegSetMasks
    {
        SingleTypeRegSet    regsToFree              = RBM_NONE;
        SingleTypeRegSet    delayRegsToFree         = RBM_NONE;
        SingleTypeRegSet    regsToMakeInactive      = RBM_NONE;
        SingleTypeRegSet    delayRegsToMakeInactive = RBM_NONE;
        SingleTypeRegSet    copyRegsToFree = RBM_NONE;
    };

and declared as one of following

Option A

    RegSetMasks lowRegSet;
    RegSetMasks highRegSet;
    RegSetMasks *currRegSet = &lowRegSet;

Option B

  RegSetMasks intRegSet;
  RegSetMasks fltRegSet;
  RegSetMasks mskRegSet;

This will reduce the overhead due to operations on regMaskTP since we will be working on SingleTypeRegSet which is a uint64.

Methods from the list of regressed methods this is likely to improve

  • allocateRegisters()
  • allocateRegistersMinimal()
  • freeRegisters()

The effect of switching to more than 64 registers for these methods without an optimization based on profiling is shown below.

Method InsCountDiff InsPercentageDiff ContributionPercentage
allocateRegistersMinimal@LinearScan 3524107314 33.71% 10.36%
allocateRegisters@LinearScan 2453448194 23.65% 7.21%
freeRegisters@LinearScan 1676484336 62.85% 4.93%
Dominant language
C#
Stars
18.3k
Forks
5.6k
PR metrics pending

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

More from dotnet/runtime

All issues in dotnet/runtime

Similar issues

More C# issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.