llvm dev - Nov 2020 - StringSwitch efficiency

If the argument is unknown, it seems that SROA can essentially
optimize a long chain of bcmp(string comparison) calls to dispatches
on the argument length.
Then SimplfyCFGOpt::SimplifyBranchOnICmpChain can generate a switch
instruction which will eventually lower to a jump table.
ExpandMemCmp.cpp can generate efficient comparisons for these strings.
There are cases where multiple memory loads are produced while a
memory load can be reused,
but overall the produced code looks pretty good.

int foo(llvm::StringRef s) {
    return llvm::StringSwitch<int>(s)
      .Case("int", 5)
      .Case("bit", 3)
      .Case("bits", 7)
      .Case("string", 8)
      .Case("list", 4)
      .Case("code", 2)
      .Case("dag", 1)
      .Case("class", 4)
      .Case("def", 3)
      .Case("foreach", 9)
      .Case("defm", 1)
      .Case("defset", 0)
      .Case("multiclass", 1)
      .Case("field", 4)
      .Case("let", 3)
      .Case("in", 9)
      .Case("defvar", 1)
      .Case("if", 0)
      .Case("then", 3)
      .Case("else", 7)
      .Default(5);
}

On Sat, Oct 31, 2020 at 11:56 AM David Blaikie via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
>
> Compiler Explorer can provide LLVM's trunk libraries (choose it from
"Libraries" in the compiler tab) eg: https://godbolt.org/z/5jEj3E
>
> On Sat, Oct 31, 2020 at 6:19 AM Paul C. Anagnostopoulos via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
>>
>> Okay, now I'm just being lazy. What is the simplest way to compile
a module and produce a code listing? I'm on Windows with Visual Studio.
>>
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev


-- 
宋方睿

I used Compiler Explorer to look at the compiled code and, indeed, it is quite
good. The person who wrote that particular StringSwitch put the keywords in
frequency-of-use order, so that the sequence of same-length comparisons is
checking for the more common cases first.

At 10/31/2020 03:52 PM, Fāng-ruì Sòng wrote:
>If the argument is unknown, it seems that SROA can essentially
>optimize a long chain of bcmp(string comparison) calls to dispatches
>on the argument length.
>Then SimplfyCFGOpt::SimplifyBranchOnICmpChain can generate a switch
>instruction which will eventually lower to a jump table.
>ExpandMemCmp.cpp can generate efficient comparisons for these strings.
>There are cases where multiple memory loads are produced while a
>memory load can be reused,
>but overall the produced code looks pretty good.
>
>int foo(llvm::StringRef s) {
>    return llvm::StringSwitch<int>(s)
>      .Case("int", 5)
>      .Case("bit", 3)
>      .Case("bits", 7)
>      .Case("string", 8)
>      .Case("list", 4)
>      .Case("code", 2)
>      .Case("dag", 1)
>      .Case("class", 4)
>      .Case("def", 3)
>      .Case("foreach", 9)
>      .Case("defm", 1)
>      .Case("defset", 0)
>      .Case("multiclass", 1)
>      .Case("field", 4)
>      .Case("let", 3)
>      .Case("in", 9)
>      .Case("defvar", 1)
>      .Case("if", 0)
>      .Case("then", 3)
>      .Case("else", 7)
>      .Default(5);
>}

Awesome, yay for composition and smart compilers :-)

-Chris
> On Nov 1, 2020, at 10:07 AM, Paul C. Anagnostopoulos via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
> 
> I used Compiler Explorer to look at the compiled code and, indeed, it is
quite good. The person who wrote that particular StringSwitch put the keywords
in frequency-of-use order, so that the sequence of same-length comparisons is
checking for the more common cases first.
> 
> At 10/31/2020 03:52 PM, Fāng-ruì Sòng wrote:
>> If the argument is unknown, it seems that SROA can essentially
>> optimize a long chain of bcmp(string comparison) calls to dispatches
>> on the argument length.
>> Then SimplfyCFGOpt::SimplifyBranchOnICmpChain can generate a switch
>> instruction which will eventually lower to a jump table.
>> ExpandMemCmp.cpp can generate efficient comparisons for these strings.
>> There are cases where multiple memory loads are produced while a
>> memory load can be reused,
>> but overall the produced code looks pretty good.
>> 
>> int foo(llvm::StringRef s) {
>>   return llvm::StringSwitch<int>(s)
>>     .Case("int", 5)
>>     .Case("bit", 3)
>>     .Case("bits", 7)
>>     .Case("string", 8)
>>     .Case("list", 4)
>>     .Case("code", 2)
>>     .Case("dag", 1)
>>     .Case("class", 4)
>>     .Case("def", 3)
>>     .Case("foreach", 9)
>>     .Case("defm", 1)
>>     .Case("defset", 0)
>>     .Case("multiclass", 1)
>>     .Case("field", 4)
>>     .Case("let", 3)
>>     .Case("in", 9)
>>     .Case("defvar", 1)
>>     .Case("if", 0)
>>     .Case("then", 3)
>>     .Case("else", 7)
>>     .Default(5);
>> }
> 
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev