VM keeps doing the same redundant operations when doing many compares

[jensjoha]

This might be the same thing as https://github.com/dart-lang/sdk/issues/56828 bit I'd thought I'd create a separate issue anyway because I don't know.

In the parser I'd like to rewrite a function to something like this:

@pragma("vm:never-inline")
bool looksLikeExpressionStart(Token next) =>
    next.isIdentifier ||
    next.isKeyword && !looksLikeStatementStart(next) ||
    next.isA(TokenType.DOUBLE) ||
    next.isA(TokenType.DOUBLE_WITH_SEPARATORS) ||
    next.isA(TokenType.HASH) ||
    next.isA(TokenType.HEXADECIMAL) ||
    next.isA(TokenType.HEXADECIMAL_WITH_SEPARATORS) ||
    next.isA(TokenType.IDENTIFIER) ||
    next.isA(TokenType.INT) ||
    next.isA(TokenType.INT_WITH_SEPARATORS) ||
    next.isA(TokenType.STRING) ||
    next.isA(TokenType.OPEN_CURLY_BRACKET) ||
    next.isA(TokenType.OPEN_PAREN) ||
    next.isA(TokenType.OPEN_SQUARE_BRACKET) ||
    next.isA(TokenType.INDEX) ||
    next.isA(TokenType.LT) ||
    next.isA(TokenType.BANG) ||
    next.isA(TokenType.MINUS) ||
    next.isA(TokenType.TILDE) ||
    next.isA(TokenType.PLUS_PLUS) ||
    next.isA(TokenType.MINUS_MINUS);

(pragma added to make sure I could easily dump the assembly).

It generates code like this:

81173   ParallelMove rcx <- rbx
   0x000000000023332b <+119>:   mov    %rbx,%rcx

81174   v598 <- IntConverter(uint32->int64, v388) int64
   0x000000000023332e <+122>:   mov    %ecx,%ecx

81175   Branch if EqualityCompare(v512 T{_Smi} == v598 T{_Smi}) T{bool} goto (30, 9)
   0x0000000000233330 <+124>:   cmp    $0x1,%rcx
   0x0000000000233334 <+128>:   je     0x233439 <looksLikeExpressionStart+389>

81176   B30
81177   B9
81178   ParallelMove rcx <- rbx
   0x000000000023333a <+134>:   mov    %rbx,%rcx

81179   v597 <- IntConverter(uint32->int64, v388) int64
   0x000000000023333d <+137>:   mov    %ecx,%ecx

81180   Branch if EqualityCompare(v513 T{_Smi} == v597 T{_Smi}) T{bool} goto (31, 10)
   0x000000000023333f <+139>:   cmp    $0x2,%rcx
   0x0000000000233343 <+143>:   je     0x233439 <looksLikeExpressionStart+389>

81181   B31
81182   B10
81183   ParallelMove rcx <- rbx
   0x0000000000233349 <+149>:   mov    %rbx,%rcx

81184   v596 <- IntConverter(uint32->int64, v388) int64
   0x000000000023334c <+152>:   mov    %ecx,%ecx

81185   Branch if EqualityCompare(v514 T{_Smi} == v596 T{_Smi}) T{bool} goto (32, 11)
   0x000000000023334e <+154>:   cmp    $0x29,%rcx
   0x0000000000233352 <+158>:   je     0x233439 <looksLikeExpressionStart+389>

81186   B32
81187   B11
81188   ParallelMove rcx <- rbx
   0x0000000000233358 <+164>:   mov    %rbx,%rcx

81189   v595 <- IntConverter(uint32->int64, v388) int64
   0x000000000023335b <+167>:   mov    %ecx,%ecx

81190   Branch if EqualityCompare(v515 T{_Smi} == v595 T{_Smi}) T{bool} goto (33, 12)
   0x000000000023335d <+169>:   cmp    $0x3,%rcx
   0x0000000000233361 <+173>:   je     0x233439 <looksLikeExpressionStart+389>

81191   B33
81192   B12
81193   ParallelMove rcx <- rbx
   0x0000000000233367 <+179>:   mov    %rbx,%rcx

81194   v594 <- IntConverter(uint32->int64, v388) int64
   0x000000000023336a <+182>:   mov    %ecx,%ecx

81195   Branch if EqualityCompare(v516 T{_Smi} == v594 T{_Smi}) T{bool} goto (34, 13)
   0x000000000023336c <+184>:   cmp    $0x4,%rcx
   0x0000000000233370 <+188>:   je     0x233439 <looksLikeExpressionStart+389>

(and goes on but the pattern should be obvious by now)

It should be able to avoid the two moves every time.

With the code like (as-is):

 bool looksLikeExpressionStart(Token next) =>
     next.isIdentifier ||
     next.isKeyword && !looksLikeStatementStart(next) ||
    next.type == TokenType.DOUBLE ||
    next.type == TokenType.DOUBLE_WITH_SEPARATORS ||
    next.type == TokenType.HASH ||
    next.type == TokenType.HEXADECIMAL ||
    next.type == TokenType.HEXADECIMAL_WITH_SEPARATORS ||
    next.type == TokenType.IDENTIFIER ||
    next.type == TokenType.INT ||
    next.type == TokenType.INT_WITH_SEPARATORS ||
    next.type == TokenType.STRING ||
    optional('{', next) ||
    optional('(', next) ||
    optional('[', next) ||
    optional('[]', next) ||
    optional('<', next) ||
    optional('!', next) ||
    optional('-', next) ||
    optional('~', next) ||
    optional('++', next) ||
    optional('--', next);

it does

81177   B30
81178   B9
81179   Branch if StrictCompare:10(===, v615 T{TokenType}, v10 T{TokenType}) T{bool} goto (31, 10)
   0x0000000000233346 <+146>:   cmp    0x41bf(%r15),%rcx
   0x000000000023334d <+153>:   je     0x233427 <looksLikeExpressionStart+371>

81180   B31
81181   B10
81182   Branch if StrictCompare:10(===, v615 T{TokenType}, v13 T{TokenType}) T{bool} goto (32, 11)
   0x0000000000233353 <+159>:   cmp    0x406f(%r15),%rcx
   0x000000000023335a <+166>:   je     0x233427 <looksLikeExpressionStart+371>

81183   B32
81184   B11
81185   Branch if StrictCompare:10(===, v615 T{TokenType}, v16 T{TokenType}) T{bool} goto (33, 12)
   0x0000000000233360 <+172>:   cmp    0x4147(%r15),%rcx
   0x0000000000233367 <+179>:   je     0x233427 <looksLikeExpressionStart+371>

81186   B33
81187   B12
81188   Branch if StrictCompare:10(===, v615 T{TokenType}, v19 T{TokenType}) T{bool} goto (34, 13)
   0x000000000023336d <+185>:   cmp    0x414f(%r15),%rcx
   0x0000000000233374 <+192>:   je     0x233427 <looksLikeExpressionStart+371>

Can we please be smarter about these moves?

[dart-github-bot]

Summary: The user reports that the Dart VM performs redundant move operations when comparing multiple token types in a function. The user provides assembly code examples showing the unnecessary moves and suggests using TokenType.type instead of isA to avoid them.

[mraleph]

Yeah, it is similar problem all caused by uint32 optimization which we should probably just disable (or rewrite).

That being said: I think this code might perform better if you avoid cascade of if-s to begin with (e.g. use some lookup table based token classifier?).

I am gonna close this as duplicate for now.

[alexmarkov]

In general, narrowing int64 operations to int32/uint32 results in smaller and more efficient code on x64 and 32-bit architectures, so it is beneficial to have a narrowing optimization. Extra register moves are very cheap compared to other instructions.

We can probably solve this particular inefficiency without disabling narrowing by adding support for uint32 representation to EqualityCompare, so IntConverter instructions won't be needed. Eventually I'd like to revise our integer operations to make them more orthogonal and support wider range of representations, so maybe we should keep this issue open.