Skip to content

Enable more constant foldings for switch ops using assertions #113998

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Merged
EgorBo merged 6 commits into from
Mar 31, 2025
Merged

Enable more constant foldings for switch ops using assertions #113998

EgorBo merged 6 commits into from
Mar 31, 2025

Conversation

@EgorBo
Copy link
Member

@EgorBo EgorBo commented Mar 28, 2025 •
edited
Loading

Closes #113992

This PR creates global assertions for switch targets.

An example from System.Text.Json:

public static ulong GetKey(ReadOnlySpan<byte> name)
{
    int length = name.Length;
    ulong key = (ulong)(byte)length << 56;

    switch (length)
    {
        case 0: goto ComputedKey;
        case 1: goto OddLength;
        case 2: key |= MemoryMarshal.Read<ushort>(name); goto ComputedKey;
        case 3: key |= MemoryMarshal.Read<ushort>(name); goto OddLength;
        case 4: key |= MemoryMarshal.Read<uint>(name); goto ComputedKey;
        case 5: key |= MemoryMarshal.Read<uint>(name); goto OddLength;
        case 6:
            key |= MemoryMarshal.Read<uint>(name) |
                   (ulong)MemoryMarshal.Read<ushort>(name.Slice(4, 2)) << 32; goto ComputedKey;
        case 7:
            key |= MemoryMarshal.Read<uint>(name) |
                   (ulong)MemoryMarshal.Read<ushort>(name.Slice(4, 2)) << 32; goto OddLength;
        default: key |= MemoryMarshal.Read<ulong>(name) & 0x00ffffffffffffffL; goto ComputedKey;
    }

    OddLength:
    int offset = length - 1;
    key |= (ulong)name[offset] << (offset * 8);

    ComputedKey:
    return key;
}

Codegen diff (Main vs PR): https://www.diffchecker.com/cxZY6tn3/ (still not perfect, though).

Another use-case is switch over string literals. Roslyn emits a trie-like algorithm for them where we do switch over string's length and end up comparing length inside all cases:

int Trie(string x) =>
    x switch
    {
        "1" => 1,
        "11" => 11,
        "111" => 111,
        "1111" => 1111,
        "11111" => 11111,
        "111111" => 111111,
        "1111111" => 1111111,
        "11111111" => 11111111,
        _ => 0
    };

Codegen diff (Main vs PR): https://www.diffchecker.com/CeHgRf8I/

@ghost ghost added the area-CodeGen-coreclr CLR JIT compiler in src/coreclr/src/jit and related components such as SuperPMI label Mar 28, 2025
This was referenced Mar 28, 2025
Closed
Closed
Closed
Closed
@EgorBo EgorBo force-pushed the switch-assertions branch from e287095 to c7882ca Compare March 29, 2025 16:18
@EgorBo
Copy link
Member Author

EgorBo commented Mar 29, 2025

@EgorBot -amd

using BenchmarkDotNet.Attributes;

public class Bench
{
    static string[] _strings = ["1", "10", "100", "1000", "10000", "100000", "1000000"];

    [Benchmark]
    public int Sum()
    {
        int sum = 0;
        foreach (string str in _strings)
        {
            sum += str switch
            {
                "1" => 1,
                "10" => 10,
                "100" => 100,
                "1000" => 1000,
                "10000" => 10000,
                "100000" => 100000,
                "1000000" => 1000000,
                _ => -1
            };
        }
        return sum;
    }
}

@EgorBot EgorBot mentioned this pull request Mar 29, 2025
Open
@EgorBo EgorBo marked this pull request as ready for review March 29, 2025 20:23
Copilot AI review requested due to automatic review settings March 29, 2025 20:23
Copilot AI reviewed Mar 29, 2025
View reviewed changes
Copy link
Contributor

Copilot AI left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Copilot wasn't able to review any files in this pull request.

Files not reviewed (2)
  • src/coreclr/jit/assertionprop.cpp: Language not supported
  • src/coreclr/jit/compiler.h: Language not supported

@build-analysis build-analysis bot mentioned this pull request Mar 29, 2025
Closed
@EgorBo
Copy link
Member Author

EgorBo commented Mar 29, 2025 •
edited
Loading

PTAL @AndyAyersMS @dotnet/jit-contrib Diffs

I decided to implement the assertion using a NOP node in all branches as the simplest impl, but as a follow up, I want to remove this "single assertion per tree" for Global Prop and write directly into block->bbAssertionGen (or bbAssertionIn).

My first impl was writing into bbAssertionIn/bbAssertionGen but it generated less diffs, presumably because we already ran optImpliedAssertions at that point.

@EgorBo EgorBo requested a review from AndyAyersMS March 29, 2025 23:16
AndyAyersMS
AndyAyersMS approved these changes Mar 30, 2025
View reviewed changes
Copy link
Member

@AndyAyersMS AndyAyersMS left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Looks good overall. Left you a few small things to consider.

src/coreclr/jit/assertionprop.cpp
// TODO-Cleanup: We shouldn't attach assertions to nodes in Global Assertion Prop.
// It limits the ability to create multiple assertions for the same node.
GenTree* tree = gtNewNothingNode();
fgInsertStmtAtBeg(target, fgNewStmtFromTree(tree));
Copy link
Member

@AndyAyersMS AndyAyersMS Mar 30, 2025

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

You should assert there are no PHI nodes in this block (there shouldn't be any since the block has a single pred edge).

Copy link
Member Author

@EgorBo EgorBo Mar 30, 2025

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Added an assert

src/coreclr/jit/assertionprop.cpp Outdated

if (containsSwitches)
{
for (BasicBlock* const block : Blocks())
Copy link
Member

@AndyAyersMS AndyAyersMS Mar 30, 2025

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

There are unlikely to be many switches so maybe keep track of them in the initial walk?

Copy link
Member Author

@EgorBo EgorBo Mar 30, 2025

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Done

src/coreclr/jit/assertionprop.cpp Outdated
// We can only make "X == caseValue" assertions for blocks with a single edge from the switch.
BasicBlock* target = jumpTable[jmpTargetIdx]->getDestinationBlock();
if ((target->GetUniquePred(this) != switchBb) || (fgGetPredForBlock(target, switchBb)->getDupCount() > 1) ||
!BasicBlock::sameEHRegion(target, switchBb))
Copy link
Member

@AndyAyersMS AndyAyersMS Mar 30, 2025

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Do we need to bail if not same EH region? If the switch arm is a try entry still seems fine to add the assertion.

Copy link
Member Author

@EgorBo EgorBo Mar 30, 2025

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

hm.. I think you're right, relaxed

@build-analysis build-analysis bot mentioned this pull request Mar 31, 2025
Closed
@EgorBo
Copy link
Member Author

EgorBo commented Mar 31, 2025

/ba-g "azurelinux.3 timeouts"

@EgorBo EgorBo merged commit 3e9ed11 into dotnet:main Mar 31, 2025
109 of 111 checks passed
@EgorBo EgorBo deleted the switch-assertions branch March 31, 2025 09:39
thaystg pushed a commit to thaystg/runtime that referenced this pull request Apr 1, 2025
@EgorBo @thaystg
Enable more constant foldings for switch ops using assertions (dotnet…
d0f4a91 
…#113998)
@github-actions github-actions bot locked and limited conversation to collaborators May 1, 2025
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.

Reviewers

Copilot code review Copilot Copilot left review comments

@AndyAyersMS AndyAyersMS AndyAyersMS approved these changes

Assignees

@EgorBo EgorBo

Labels

area-CodeGen-coreclr CLR JIT compiler in src/coreclr/src/jit and related components such as SuperPMI

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

JIT: Switch should create assertions

2 participants

@EgorBo @AndyAyersMS